《计算机网络-自顶向下方法》读书笔记-网络层篇

《计算机网络-自顶向下方法》读书笔记-网络层篇

网络层服务

通过发送主机传输给接收主机的数据分段（segment）中包含信息。发送主机负责将数据分段打包成数据报（datagram）中。

通过发送主机传输给接收主机的数据分段（segment）中包含信息。发送主机负责将数据分段打包成数据报（datagram）中。

接收主机：向传输层交付数据段（segment ）

每个主机和路由器都运行网络层协议

路由器检验所有穿越它的IP数据报的头部域

• 决策如何处理IP数据报

网络层核心功能-转发与路由

该功能允许将数据包从路由器的入线接口传输至指定的出线接口。

路由算法(协议)在该网络内部选择合适的端到端路径；转发表在当前路由器规划如何转发分组

网络层核心功能-连接建立

某些网络的重要功能

• ATM,帧中继,X.25
  数据分组传输之前两端主机需要首先建立虚拟/逻辑连接

• 网络设备(如路由器)参与连接的建立

网络层连接与传输层连接的对比

• 网络层连接: 两个主机之间(相关路由器等网络设备参与其中)
• 传输层连接: 两个应用程序之间(对中间网络设备无需透明处理)

网络层服务模型

无连接服务(connection-less service):

• 未预先指定传输路径给数据分组
  • 每个数据分组能够自主决定自己的传输路径
  • 存在着各数据分组具有不同传输路径的可能性
  • 数据报网络 datagram network

连接服务(connection service):

首先规划好数据包在源到目标之间的传输所需路径，并创建通信链路。
然后随后通过该通信链路将一系列数据包依次发送出去。
确保所有数据包采用统一的传输路线。
传输结束后切断通信链路。
虚电路网络(virtual-circuit network )

数据报与虚电路网络

虚电路网络

数据报(datagram)网络与虚电路(virtual-circuit)网络分别代表了两大类分组交换网络的技术基础

数据报网络提供网络层无连接服务

虚电路网络提供网络层连接服务

类似于传输层的无连接服务（UDP）和面向连接
服务（TCP ），但是网络层服务：

• 主机到主机服务
• 网络核心实现

虚电路: 一条从源主机到目的地的主机,类似于电路的路径(逻辑连接)

• 分组交换技术
• 各分组的数据传输充分利用了链路的全部带宽
• 在源至目的路径上依次经过的一系列网络层设备协同工作以建立虚电路功能

通信过程：

从发起呼叫开始至数据传输完成再到关闭该呼叫的过程依次经历了call setup阶段、数据传输阶段以及teardown阶段。
每个分组都携带与目标主机相关联的唯一标识符（VCID），而非直接标明目标主机地址。
路由器等网络设备会持续监控并记录每一条通过它们的虚拟通道的状态信息。
这些关键资源能够预先规划分配给相关的虚拟通道。

• 预分配资源=可预期服务性能
• 如ATM的电路仿真(CBR)

VC具体实现

每一条虚拟电路由：
1. 连接源主机至目的主机建立的一条通路
2. VCID标识符在其传输路径上的各节点处依次分配号码
3. 在传输过程中经过的每一台网络层设备（例如路由器）均依据其路由表进行操作
4. 所经过的各条虚拟通道

沿某条虚电路传输的分组，携带对应虚电路的VCID，而不是目的地址

同一条VC ，在每段链路上的VCID通常不同

路由器转发分组时依据转发表改写/替换虚电路号

转发表

VC路径上每个路由器都需要维护VC连接的状态

VC进入路由器后,路由器将VC头替换,然后转发出去

数据报网络

在缺乏网络层连接的情况下，
每个数据分组都包含其目的地址信息，
路由器依据数据分组中的目的地址进行转发操作，
基于特定的路由协议或算法构建相应的转换表，
通过检索转换表来确定下一跳节点，
确保每个数据分组能够自主选择最优路径

路由器转发表

最长前缀匹配优先：
在检索转换表中作为首要选择，在分配流量时会优先考虑具有最长前缀匹配特性的入口。

IP协议

主机、路由器网络层主要功能:

• 路径选择

  • RIP
  • OSPF
  • BGP

• IP协议

  • 寻址规约
  • 数据报(分组)格式
  • 分组处理规约

• ICMP协议

  • 差错报告
  • 路由器命令

IP数据报格式

| 服务类型(8bit)| 指示期望获得哪种类型的服务
1 .仅当采用网络区分服务(DiffServ)机制时才被应用
2.通常情况下不使用（除非第2字节对应字段值为00H） |
| 总长度(16bit)| 描述单个IP分组的总字节数（包含首部字段与数据部分）
1. 单个IP分组的最大总长度为65535个字节
2.最小的IP分组首部字段大小为20B
3. 因此单个IP分组可承载的最大数据量为65535 - 20 = 65515B |
| 生存时间TTL(8bit)| 表示该IP分组在网络内部可穿越的最大路由器数目（或最大跳数）
1.每当路由器转发一个IP分组时, TTL字段值递减1
2.若TTL=0，则表示该路由器将丢弃该IP分组 |
| 协议(8bit)|标识所封装的具体协议类型，并支持相应的复用与解密流程 |

| 首部校验和(16位) | 完成对IP数据包头部信息的完整性校验
1.在计算校验和时,将该字段设为全零值
2.使用补码加法计算各字段之和,并将该和的反码作为首部校验字段
3.按跳距逐一计算并核验每一分组 |

DF (Don't Fragment)
MF (More Fragment)
DF = 1：将该IP分组的数据分割；
DF = 0：不将该IP分组的数据分割
MF = 1：表示该IP分组不是最后一片；
MF = 0：表示该IP分组是最后一片（或未进行分割） |
| 片偏移(13bit) | 封装该IP分组数据相对于其所在片段的相对偏移值 |
片偏移字段占用了8字节字段 |

IP分片

该网络通道具备最大传输单元（MTU）限制—在链路层中可以封装的数据量具有特定的最大值，并且各网络通道对应的MTU大小各异

大IP分组向较小MTU链路转发时， 可以被“分片” (fragmented)

• 将一个IP分组划分为多片IP分组。
  • 当IP分片到达目标主机后，完成重组过程（reassembled）。

IP首部的相关字段用于标识分片以及确定分片的相对顺序

• 总长度、标识、标志位和片偏移

设原IP数据包总长度为L，则目标链路的最大传输单元大小为M。当数据包长度超过目标链路MTU容量且无数据校验位时，则必须将数据包分割成多个小数据包进行传输。在数据包分割过程中，在每个新生成的小数据包中都复制原始数据包的所有元数据。在一般情况下，默认会将前若干个小数据包分割至最大可能的数据单元大小（即MTU允许的最大值）。为了确保传输过程中的完整性与可靠性需求，在编码过程中应遵循每8个字节作为一个独立的数据块的原则来处理最后一个剩余的部分。

需要的总片数为:

每片片偏移字段取值为

每片的总长度字段为

每片MF标志位为:

IP编址

接口(interface): 主机/路由器与物理链路的连接

• 负责完成网络层各项功能任务 *
• 一般情况下路由器设计都采用多接口配置 *
• 通常情况下设备最多支持一个或两个网络接口以确保稳定的通信连接 (例如：常见的有线eth口端口以及无线802.11n/g/b/w等)

IP地址: 32比特(IPv4)编号标识主机、路由器的接口

IP地址与每个接口关联

IP地址:

• 网络号(NetID) – 高位比特
• 主机号(HostID) – 低位比特

IP子网

• IP地址遵循同网络段设备接口。
• 直接连接到同一台路由器的接口是不跨越路由器（ router以上层设备）可以彼此物理联通的接口。

IP子网划分与子网掩码

“有类”编码
如图:

特殊IP地址

私有IP地址

子网划分

IP地址:

网络号(NetID) – 高位位
子网号(SubID) – 对应的主机号的高位部分
主机号(HostID) – 低位位

如何确定是否划分了子网？利用多少位划分子网？

• 子网掩码

形如IP地址:

• 32位
• 点分十进制形式

取值：

• NetID、 SubID位
• HostID位全取0

将IP分组的目的IP地址与子网掩码按位与运算，提取子网地址

无类域间路由(CIDR: Classless InterDomain Routing)

• 破除传统对A型、B型和C型地址区别的限制
  • NetID与SubID结合生成的网络前缀（Prefix）具有可变长度的能力
  • 通过融合子网地址与子网掩码信息来实现对网络分区的简便划分
  • 无类别地址采用a.b.c.d/x的形式表示其中x代表前缀位数

子网201.2.3.64， 255.255.255.192→201.2.3.64/26

无类域间路由(CIDR: Classless InterDomain Routing)

• 优化IPv4地址空间的分配效率
  • 提升网络路由性能
  • 通过多网聚合技术整合多个子网
  • 实施超网构建策略

当一个子网无法完成全部的聚合时,系统将通过边缘节点发送报告请求,该请求将采用最长前缀匹配机制以确保接收方能够正确解析 incoming messages.

路由算法

路由算法通过设置转发表来得到应用

网络可以抽象成图

其中
N = 路由器集合
E = 链路集合

费用(Costs):每段链路的费用可以总是1,或者是宽带的倒数、拥塞程度等.

静态路由VS动态路由?
静态路由:

• 手工配置
• 路由更新慢
• 优先级高

动态路由:

• 定期更新
• 及时响应链路费用或网络拓扑变化

全局信息VS分散信息?
全局信息:

• 所有路由器掌握完整的网络拓扑和链路费用信息

分散信息:

• 路由器仅了解直接连接的网络设备及其对应的链路费用。
  • 网络设备间的互操作性与数据处理流程是动态协调的关键。

链路状态路由算法

Dijkstra算法:
数据结构有实现,这里直接上代码:

    #include<stdio.h>
    #include<stdlib.h>
    #define max 11000000000
    int a[1000][1000];
    int d[1000];//d表示某特定边距离
    int p[1000];//p表示永久边距离
    int i,j,k;
    int m;//m代表边数
    int n;//n代表点数
    int main()
    {
    scanf("%d%d",&n,&m);
    int min1;
    int x,y,z;
    for(i=1;i<=m;i++)
    {
    scanf("%d%d%d",&x,&y,&z);
    a[x][y]=z;
    a[y][x]=z;
    }
    for(i=1;i<=n;i++)
        d[i]=max1;
    d[1]=0;
    for(i=1;i<=n;i++)
    {
        min1=max1;
        for(j=1;j<=n;j++)
            if(!p[j]&&d[j]<min1)
            {
                min1=d[j];
                k=j;
            }
        p[k]=j;
        for(j=1;j<=n;j++)
            if(a[k][j]!=0&&!p[j]&&d[j]>d[k]+a[k][j])
                d[j]=d[k]+a[k][j];
    }
    for(i=1;i<n;i++)
    printf("%d->",p[i]);
    printf("%d\n",p[n]);
    return0;
    }

复杂性分析和优化见数据结构

链路状态路由算法的震荡:

距离向量路由算法

Bellman-Ford方程（动态规划的一种）
定义为：
其中d_x(y)定义为从节点x到节点y的最短路径费用（距离）。
则根据上述定义可知，d_x(y)= min{ c(x,v)+d_v(y)}。

Dx(y) = 从结点x到结点y的最小费用估计

• x维护距离向量(DV): Dx = [Dx(y): y є N ]
  结点x:

• 对于每一个邻居x来说，c(x, v)代表从节点x到节点v的费用； * 维护所有邻居y的距离向量Dv = [Dv(y): y ∈ N]； 核心思想是基于上述方法构建的数据结构。

• 每个节点定期传递其自身的DV估计给邻居。

• 每当节点x从其邻居接收新的DV估计值时（按照B-F方法），会更新自身所记录的距离向量估计值。

• 该算法通过这种方式确保了Dx(y)最终收敛于真实最小费用dx(y)。

异步迭代:

• 引发每次局部迭代的因素

  • 局部链路费用改变
  • 来自邻居的DV更新
    分布式:

• 每个结点只当DV变化时才通告给邻居

  • 邻居在必要时（其DV更新后发生改变）再通告它们的邻居

无穷计数问题

见示意图

解决方案
毒性逆转(poisoned reverse):

当一个节点(如Z)旨在达到某一目标(如X)时的最低费用路径由其邻居(如Y)决定，则：

* 通告给该邻居结点到达该目的的距离为无穷大

毒性逆转无法根本上消除无穷计数问题，在复杂网络环境中。这种措施在面对极其复杂的网络时将失去作用。

定义最大度量
定义一个最大的有效费用值,如15跳步,16跳步表示无穷.

具体过程见示意图

层次路由

网络规模： 考虑6亿目的结点的网络

• 该路由表严重超出存储能力。
  • 在路由计算过程中, 数据交换规模庞大(如链路状态分组与距离向量DV), 导致通信路径受限。

管理自治:

• 每个网络的管理者普遍期望独立管理其内部路由
  • 全球互联网体系等于由众多子网络组成的网格状架构

聚合路由器为一个区域：自治系统AS(autonomous systems)

同一AS内的路由器运行相同的路由协议(算法)

• 该系统的内部路由协议采用了"internal route protocol"策略。
• 各自治网络中的路由器可配置各自使用的AS内部路由协议。

网关路由器(gatewayrouter):

• 位于AS“边缘”
• 通过链路连接其他AS的网关路由器

转发表由AS内部路由算法和AS间路由算法共同配置

• 通过AS内部路由算法对目标网络的AS内部路由入口进行配置(entries)
  • 通过结合使用AS内部和间域路由算法对目标网络的外部路径进行统一配置

自治系统之间（inter-AS）的路由操作
当某路由器位于AS1内部接收到一个目的地址属于AS1外部的数据包时：

• 路由器应该将该数据报转发给哪个网关路由器呢?

假设AS1通过AS间路由协议学习到：子网x通过AS3和AS2均可到达

• 在配置转发表时，路由器1d需要确定如何将前往子网x的数据包发送至哪个网关？
  • 该任务同样由AS间路由协议来完成。

热土豆路由: 将分组发送给最近的网关路由器.

RIP协议

AS内部路由协议也称为内部网络协议IGP(interiorgatewayprotocols)

• 主要采用哪种AS内部路由协议

  • 其中一种重要的相关协议是RIP（Routing Information Protocol）

  • 另一种关键的方案是开放最短路径优先算法（OSPF），它基于Bellman-Ford算法

  • 第三种主要的是内部网关路由协议（IGRP），它基于距离向量机制

    • Cisco私有协议

RIP
早于1982年随BSD-UNIX操作系统发布

• 基于距离向量的路由算法
  • 计算方式：hop计数 (最大值设为15跳), 每条链路计为一跳（防止无穷计数）
  • 每隔30秒间隔内, 邻居会互相发送一次DV信息, 并将其标记为广告
  • 每次发布DV时会包含最多25个目的子网地址（以IP格式表示）

RIP示例

注意，在路由器之间的交换信息中包含了一个额外的下一跳信息字段，在传统的距离向量路由算法中并未采用这一机制。当某个路由器接收到自己的下一跳时（即该字段指向自身），这就相当于阻止了该信息进一步传播的效果

RIP链路的失效和恢复信息
如果180秒没有收到通告→邻居/链路失效

• 该路由已无法通过相邻节点
  • 对路径进行重新评估
  • 向相邻节点发布新消息
  • 相邻节点将依次向外传播此消息（若表征发生变化）
  • 失效信息能否迅速覆盖整个网络？
  • 这一情况可能导致无限递增的计数问题
  • 防御机制中的韧性逆转技术用于防止……另外，在这种机制下定义的最大距离为16个跳数。

RIP路由表的实现：该协议采用一个称为route-d（daemon）的应用层进程来完成。UDP数据报传输过程是定期进行的。

RIP协议适用于小规模AS,以为最大跳步15.

OSPF协议

采用链路状态路由算法

• LS分组的传播（通告）
  • 每个路由器构建自身AS域内的完整拓扑图。
  • 采用Dijkstra算法计算内部路由信息。
  • OSPF通告消息中的每个入口字段对应一个相邻路由器。
  • OSPF通告消息在全AS范围内广播。
  • OSPF数据包直接嵌入IP数据帧中。
  • 与OSPF极为类似的另一个路由协议是IS-IS。

OSPF优点
安全(security): 所有OSPF报文可以被认证(预防恶意入侵)

• 支持配置允许多条具有相同费用值的路由路径（rip不允许同时存在两条以上）

  • 每个链路都可以配置多个不同TOS对应的费用度量参数
    • 卫星链路通常配置低优先级（best effort）时延参数
    • 实时传输（real time）则需设定较高的延迟限制
  • 可实现单播与多播路由策略以优化数据传输效率

• MOSPF协议支持多路转发，并基于相同的网络拓扑数据与传统的OSPF协议相一致。

• OSPF遵循hierarchical AS层级结构以实现对大规模AS的组织。

OSPF分层示例:

两级分层

• 链路状态信息仅限于区域内传播
• 路由器能够获取所在区域完整的网络架构信息
• 只知道到达其他区域网络的方向信息（以最短路径为主）

BGP路由协议

边界网关协议BGP (Border GatewayProtocol):事实上的标准域间路由协议

• 将Internet “粘合”为一个整体的关键

B GP通过特定机制为每个Autonomous System（AS）提供了关键功能：
*e B GP通过接口与相邻AS交互以获取互达性数据：
*i B GP负责将当前区域内的网络状态更新通知到所有内部路由器：
基于互达性和策略评估结果，识别出通往其他网络区域的最优化路径：
通过通告机制，在整个Internet体系中清晰标识出该子网络的位置和存在状态：

BGP会话(session): 两个BGP路由器 (“ Peers” )交换BGP报文:

• 按照指定的不同目的前缀（prefix）的路径（‘路径向量(path vector)’协议）通告该段路由信息。
• 报文交换通过半永久的TCP连接实现数据传输。

BGP报文:

• OPEN: 通过与peer建立TCP连接以进行身份验证
• UPDATE: 通知新的路由信息（也可撤销现有路由）
• KEEPALIVE: 在未发布route updates的情况下维持连接存活，并可核实OPEN请求的状态
• NOTIFICATION: 反馈先前报文中出现的错误信息，并可终止会话

当AS3发布一个前缀给AS1时:

• AS3负责将数据报传输至该子网
• AS3在通告中会收集相关网络前缀

BGP分发路径信息:
如示意图:

在3a与1c之间, AS3利用eBGP会话向AS1发送前缀可达性信息.

• 1c则可通过iBGP向AS1内的全部路由器发送新的前缀可达性信息。
  • 1b可能进一步通过其至2a的eBGP会话向AS2通告新的可达性信息。
  • 当路由器接收到新的前缀可达性时，则会在其转发表中添加该前缀的路由项。

通告的前缀信息包括BGP属性

• 前缀+属性= “ 路由”

两个重要属性:

• AS-PATH（AS路径）：由前缀通告所经过的一系列 AS 构成；例如：AS 67、AS 17。

• NEXT-HOP（下一跳）：处于一个 AS-PATH 中的路由器接口，并连接到下一个 跳转点。

  • 可能从当前AS到下一跳AS存在多条链路(如图中2b和2c)

骨干网关路由器接收路由信息后依据其输入策略（import policy）决定是否接收该条目的 routes：例如：从不将流量发送至AS x

• 基于政策导向的路由

  • 该路由器通常会知道到达某个特定AS有多条路由
  • 根据以下标准选择：

  1. 本地偏好(preference)值属性: 策略决策(policy
     decision)

  2. 最短AS-PATH

  3. 最近NEXT-HOP路由器: 热土豆路由(hot potato
     routing)

  4. 附加准则

路由选择策略示例:

A向B通告一条路径： AW

B向X通告路径： BAW

B是否应该向C通告路径BAW呢?

• 绝不会将任何流量（特别是与目标节点相关的）发送至CBAW节点。
  • 期望迫使节点C必须将所有经过节点A的流量导向目标节点W。
  • 希望仅限于与自身直接相连的节点之间的通信。

为什么采取不同的AS内与AS间路由协议
策略(policy):

• inter-AS: 值得注意的是，在该领域中旨在实现对流量路径选择以及确定哪些设备或路径允许其在网络内的传输。
  • intra-AS: 在此范围内实施单一化的网络管理架构，并且无需采取复杂的策略决策过程。

规模(scale):

• 层次路由节省路由表大小，减少路由更新流量
• 适应大规模互联网

性能(performance):

• intra-AS: 侧重性能
• inter-AS: 策略主导