第四章 网络层

关注的是如何把网络层数据报送达目的主机
两个重要功能：

• 转发：路由器都有路由转发表，使用网络层首部地址字段作为键，查表确定将分组转发到哪条链路
• 路由选择：路由器运行路由协议，在网络上收集计算路由需要的信息，计算路由后存储到路由转发表
  另一个重要功能：
  连接建立：从源主机到目的主机的一条路径，每个经过的网络设备都要参与
  根据是否在网络层提供连接服务分为：
• 虚电路VC：仅在网络层提供连接服务
• 数据报网络：仅在网络层提供无连接服务

数据报网络

按目的主机地址进行路由选择的网络
如：因特网
无连接
每个分组作为独立的数据报进行传送
每个数据报带有源和目的主机地址
发送与接收顺序不一定相同，路径不一定一致，接受方需要排序生成原始报文
出现差错由传输层协议，即端系统解决，只维护转发信息

虚电路网络

为网络层逻辑连接，并不需要分配独立资源
仅在建立VC时需要路由选择
虚电路分组通过某链路时占用全部带宽
分组不包含源和目的地址，仅含有一个VCID
虚电路标识VCID：网络设备根据分组携带的VCID判断所属的虚电路，从而决策转发
往往用于数据通信网络
按序到达接收端
为避免交换大量信息，与缩短VCID长度，同一条VC在路径上的各个链路有不同VCID，因此网络设备需要记录VCID间接续关系
根据实用时间：

• 永久型虚电路：建立时间可忽略
• 交换型虚电路：临时建立，通信结束立即拆除
  与数据报网络主要差别：
  将顺序控制，差错控制和流量控制等功能交由网络来完成还是端系统完成

异构网络互连

异构网络：通信技术与运行协议不同的网络
实现异构网络互连：

• 协议转换：利用中间设备实现异构网络间的数据分组转换与转发，可以在物理层外任一层实现
• 构建虚拟互联网络：在现有异构网络的基础上建立同构虚拟互联网络，只封装，提取和转发虚拟互联网络分组
  IP网络是虚拟互联网，Internet是利用IP的最大互联网络，由网络层实现网络互连
  隧道技术：解决同构网络互连
  网络互联设备：
• 物理层：中继器，集线器
• 数据链路层：交换机，网桥
• 网络层：路由器
• 网络层以上：网关

路由器

分布式路由查询：

每个输入端口都存有转发表副本

输入端口：

有缓存排队功能，从物理端口接收到的信号，还原成数据链路层帧，提取IP数据报，根据IP地址检索路由表，决定交换到哪个输出端口
交换结构：将输入端口的IP数据报交换到指定输出端口

• 基于内存交换：性能和价格最低
• 基于总线交换：同时一个分组通过，其他等待
• 基于网络交换：性能和价格最高

输出端口

• 有缓存排队功能，通常先到先服务FCFS
• 从队列取出进行数据链路层帧封装，通过物理线路发送
• 排队到达一定大小，其后到达分组被丢弃

路由处理器

执行路由器各种指令

• 检索路由表过程如果有一条路由项匹配成功：选择该接口转发
• 没有匹配项：通过默认路由接口转发
• 多个匹配项：最长前缀匹配选择

网络层拥塞控制

网络拥塞

需要传输的总量大于传输能力，导致缓冲区满，无法接收到新分组，即发生拥塞
网络负载在膝点附近，吞吐量和分组平均延迟达到理想平衡，网络使用效率最高
在网络层，拥塞控制同样是通过限制端系统向网络发送数据的速率来实现

• 拥塞预防：增加网络资源
• 拥塞消除：减小网络负载
  流量控制与拥塞控制：
• 流量控制：
  • 主要考虑：接收端的数据处理能力
  • 目的：使发送端发送速率低于接收端接收能力
• 拥塞控制：
  • 主要考虑：端系统之间的网络环境
  • 目的：使网络负载低于网络传送能力

常用的拥塞控制措施

流量感知路由

拥塞预防
网络被抽象成无向带权图
根据权值，将网络流量引导到不同链路
权值：以带宽，延迟，负载为变量的函数
频繁切换引导到的链路会产生振荡
解决振荡：

• 多路径路由：流量分散到多个链路上，保证负载不会太大，即减少切换
• 缓慢转移流量

准入控制

广泛用于VC的拥塞预防
基本思想：如果建立新虚电路会导致拥塞，则拒绝
通过平均流量和瞬时流量判断是否有能力接受新VC，比如10Mbit/s链路，按瞬时流量，只能建立1Mbit/sVC，但这样会导致带宽利用率低，因此需要考虑平均流量

流量调节

通过调整发送方发送速率来消除拥塞
即某个网络结点感知到发生拥塞时，通知上游网络结点降低发送效率
需要解决的问题：

• 如何感知拥塞：通过过去一段时间的平均排队延迟与瞬时排队延迟加权组合
• 如何把拥塞信息通知到上游结点：
  • 抑制分组：将某分组源地址作为目的地址，发送抑制分组，同时修改其一个标志位，避免被传输过程中，再次选择来发送抑制分组
  • 背压：由于抑制分组传输时间可能较长，让抑制分组在每一跳都发挥抑制作用，直到源结点，拥塞缓解更快，但是需要中间设备有更大缓冲区

负载脱落

清除拥塞
有选择的主动丢弃一些数据报
应该丢掉哪些：
序号较小的数据报更有价值，可以帮助发送窗口滑动
在视频应用丢弃序号更大的数据报

Internet网络层

一种数据报网络
主要包括

• 网际协议IP
• 路由协议
• 互联网控制报文协议ICMP

IPv4

最核心

IP数据报分片

当路由器要将一个IP数据报转发至某个输出端口，而数据报总长超过链路的最大传输单元MTU，路由器将根据分片标志DF确定如何处理：

• DF=0：进行分片
• DF=1：丢弃
  路由器只负责分片，由目的主机的IP重组
  重组过程：

1. 根据分片首部的标识字判断是否属于同一IP数据报
2. 通过分片字段MF=1判断不是最后一个分片
3. 根据分片的偏移字段判断先后顺序
4. 结合数据报长度字段，判断是否缺少分片
   相关计算公式见P146

IPv4编址

一台主机可能有多个IP地址，如内外网
路由器每个接口都有一个IP地址

IP子网

早期为定长前缀，称为分类地址
IP地址/24
其中/24为子网掩码
前24位为前缀Prefix或网络部分NetID，描述归属的网络
另一部分为后缀Postfix或主机部分HostID，表示网络内唯一地址
现在主流为无类地址，前缀长度可变

分类地址

ABC分配给主机，路由器
D作为组播地址
E地址保留
ABC占总量87.5%

• A类：
  • 前缀8位：0xxxxxxx
  • 首字节：0-127
  • 总共有2^7个A类网络
  • IP地址总数：2^24
• B类：
  • 前缀16位：10（后跟14个x）
  • 首字节：128-191
  • 总共有2^14
  • IP地址总数：2^16
• C类：
  • 前缀24位：110（后跟21个x）
  • 首字节：192-223
  • 总共有2^21
  • IP地址总数：2^8
• D类：
  • 1110（后跟28个x）
• E类：
  • 1111（后跟28个x）

特殊地址

• 本地主机地址：
  • 0.0.0.0/32：本网范围内表示本机
  • 0.0.0.0/0：用于路由表表示默认路由
• 有限广播地址：
  • 255.255.255.255/32：用于在子网中广播信息
• 回送地址：
  • 127.0.0.0/8：用于发送给源主机
• 内网地址：
  • A类：10.0.0.0/8
  • B：172.16.0.0/12
  • C：192.128.0.0/16

无类地址CIDR

不存在网络类别
a.b.c.d/x

子网划分

前缀越长，子网越小

• 超网化：将较小子网，减少前缀，合并成较大的子网
• 子网化：超网化逆过程
  子网掩码：32位，前缀长度的位数，全为1，其他位全为0
• 主机所在的子网地址：主机地址与子网掩码按位与运算
• 子网内广播地址：主机地址与子网掩码按位或运算
• 注意：可使用的ip地址数量-2，即广播地址与子网地址
• 例题见P151.152

路由聚合

路由器转发表原理：
将到达的IP数据报的目的IP地址与路由表的每项的子网掩码按位与运算，获得主机地址，再与路由表项的网络地址进行匹配
如果匹配成功的表项超过一条，则选择前缀最长的那个匹配项，即最长前缀匹配优先原则
如果没有匹配，则在默认路径转发
路由聚合：
将具有相同下一跳地址与接口，并且在一个大子网的多个路由表项合为一个
例题见P154

动态主机配置协议DHCP

组织被分配到网络地址块后，通过动态主机配置协议DHCP给组织内主机和路由器接口动态分配IP地址
DHCP在应用层实现，传输层UDP
工作流程：

1. 运行DHCP服务器，端口号67
2. 新接入的主机运行DHCP客户，端口号68
3. 客户向67端口发送DHCP发现Discover报文，以找到DHCP服务器
   • 目的IP地址255.255.255.255
   • 源IP地址0.0.0.0
4. 服务器收到DHCP发现报文后，发送DHCP提供Offer报文
   • 目的IP同上
   • 包含了分配的
     • ip地址
     • 子网掩码
     • 默认网关
     • 本地域名服务器ip地址
5. 主机收到提供报文后，发送DHCP请求Request报文
   • 目的ip同上
   • 可能会收到多个服务器的提供报文，选择其中一个作为自己ip地址
   • 广播通知所有服务器，告知使用或未使用
6. 被选定的服务器发送DHCP确认ACK

网络地址转换NAT

用于缓解IPv4地址耗尽
运行在在私有网络的边缘路由器
同时连接内部私有网络和公共互联网
从私有网络出去的数据报会记录替换关系在NAT转换表
通过查询NAT转换表，替换进私有网络的IP数据报的IP地址与端口号，实现私有网络中的主机与公共网络通信

NAT穿透技术

由于NAT不能接受外网主机主动发起的通信，即对内网屏蔽
引入NAT穿透技术：
在NAT转换表建立内网到外网的映射，使内网服务以公网地址的身份暴露出去
如何建立：

• 静态NAT配置：人工配置
• 动态：内网主机主动发现NAT，请求NAT完成配置，比较典型的是UPnP协议

互联网控制报文协议ICMP

IP的一部分
用于在主机和路由器间实现差错信息报告与可达性（ping）等网络探询
也就是两类报文类型
包括两个字段

• type
• code

IPv6

去掉IPv4首部分片字段，经过MTU较小链路直接丢弃，并给源主机发送ICMP反馈分组太大

IPv6地址

• 首部40字节
• 地址长度128位，由8组4位16进制数组成
• 连续多组全0用::代替，且只能代替一次
• 另一种形式：低32位写成IPv4形式
• 分为三种
  • 单播地址
  • 组播：仅能作为目的地址，给一个组内广播
  • 任播：同上，但只能给组内某个

IPv4到IPv6迁移

• 双协议栈：
  • 结点同时支持双协议
  • 通过DNS查询感知另一个结点提供什么服务
• 隧道：
  • 解决路径上有不同这种，结点，转换协议信息丢失
  • 如两头IPv6，则将整个IPv6数据报作为负载放入IPv4数据报中
  • 该IPv4数据报源与目的地址为隧道头尾结点地址

路由算法与路由协议

默认路由器：主机通过局域网直接相连的路由器
默认网关：默认路由器对应该主机的接口
将网络抽象为带权无向图G=(N,E)

• N：结点的集合
• E：边的集合
• 权值：链路的费用或距离
  结点x,y之间的权值用c(x,y)表示，之间不存在边，则权值为♾️，如a-b-c则c(a,c)=♾️
  其路径为｛a,b,c｝
  最佳路由即最短路径
  路由选择算法分为：
• 全局式路由选择算法：每个路由器在计算路由时，获取完整网络拓扑信息，比如LS算法
• 分布式路由选择算法：结点只需获取与其相连的链路费用，以及邻结点告知的到达其他结点最短距离，比如DV算法

链路状态路由选择算法LS

周期性收到其他路由器广播的链路状态分组，并存储进链路状态数据库，构建网络拓扑图
求最短路径经典算法Dijkstra算法：

• D(v)：源结点到目的结点v的当前路径距离
• P(v)：路径上v的除源结点外前序结点
• S：初始只有源结点，存储从源结点到该结点的最短路径结点集合
  最短路径即求最小D(v)的结点集合
  例题见P163

距离向量路由选择算法DV

每个结点测得与所有邻居结点的距离，并与其到达每个目标结点的最短距离，以距离向量的形式交换给所有邻居结点
每个结点以此计算并更新到每个目标结点的最短距离，并将新的距离向量通告给所有邻居，直到不再改变
每个路由器异步计算
算法的基础是B-F方程：

• 令dx(y)为x到y路径的最低费用
• 令v为x的邻居
• 则dx(y)等于最小的c(x,v)+dv(y)
• Dx(y)：x的距离向量，结点x估计自己到y的最短距离
• 每次收到距离变化与距离向量，会重新计算，最后收敛于dx(y)
• DV初始化距离向量
• 例题见P166
  无穷计数问题：来回跑
  解决方案：
• 毒性逆转：通过给v发送距离向量是，申明自己与目标结点距离♾️解决
• 定义最大跳数：超过则距离向量为无穷大

层次化路由选择

由于LS和DV算法大量交换网络信息，降低带宽，而且收敛慢，对于大规模网络不可用
层次化路由选择：

• 将互联网划分成多个自治系统AS
• 每个AS运行相同的路由协议和选择算法
  网关路由器：
• 与其他AS互连的路由器
• 其上运行自治系统间路由选择协议，用于交换可达性信息，如该AS可到哪些子网
  AS内部只用确定到达网关路由器的最短路径
  即分为两层：
• 自治系统内路由选择
• 自治系统间路由选择

Internet路由选择协议

层次化路由选择

• 内部网关协议IGP
  • 路由信息协议RIP
  • 开放最短路径优先协议OSPF
• 外部网关协议EGP
  • 边界网关协议BGP

RIP

应用于较小的AS
在 UDP 报文段中传输
基于DV算法
度量路径采用跳数
费用：源路由器和目的子网间经过的子网数，即路由器数量，也就是跳数
只能用于内径不超过15的AS内使用，即一个子网到另一个最多不超过15跳，16表示无穷大
最多25个子网
每个路由器都有转发表，转发表对比 DV 添加了下一跳信息 避免了无穷计数现象
会将转发表通过RIP 通告的形式交给所有邻居，邻居根据收到的 RIP通告更新转发表
例题见 P169

OSPF

应用于较大的AS
基于 LS 算法，即 Dijkstra 算法求最短路径
在 IP 数据报中传输
OSPF 权值可以是跳数也能是带宽
每台路由器周期性，或在链路费用发生变化时，向 AS 内所有路由器广播链路状态分组
一个 OSPF 自治系统可以配置成多个区域，各自独立运行 OSPF 算法
即路由器分为：

• 区域边界路由器
• 主干路由器
• AS 边界路由器

BGP

功能：

• 从相邻AS获取可达性信息
• 向AS内部所有路由器传播某子网可达性信息
• 基于上面，决定到达某子网最佳理由
  由应用层实现
  传输层 TCP
  运行于网关路由器
  BGP会话：过 179 端口连接另一路由器，即 BGP 对等方，并发送 BGP 报文
  AS 内部为 iBGP 会话，外部为 eBGP 会话
  重要属性：
• ASN：每个 AS 全局唯一的自治系统号
• AS-PATH：到达指定前缀需要经过的 AS 路径
• NEXT-HOP：开始 AS-PATH 的第一跳
  规则：

1. 查看 AS 网络管理员设置本地偏好值
2. 若相同，选最短 AS-PATH
3. 若相同，选最近 NEXT-HOP