计算机网络与通信笔记(四)
四、网络层
4.1 网络层概述
- 网络层：实现主机和主机之间的通信
- 数据平面：如何转发
- 转发是指将分组从一个输入链路接口转移到适当的输出链路接口的路由器本地动作
- 转发的时间尺度很短$ (ns) $，因此采用硬件实现
- 假设某个驾驶员从武昌到汉口经过许多立交桥，转发类比于经过某个立交桥的过程
- 分组交换机上的网络层根据转发表以及分组首部信息，将分组向适当链路进行转发
- 控制平面：如何选路
- 路由选择是指确定分组从源到目的地所采取的端到端路径的网络范围处理过程
- 路由选择的时间尺度较长$ (s) $，因此采用软件实现
- 假设某个驾驶员要从武昌到汉口，路由选择类比于规划从武昌到汉口的行程
- 在全局范围为主机之间的通信进行选路，选路结果反映为分组交换机上的转发表
- 数据平面：如何转发
4.2 $ IP $协议
4.2.1 $ IPv4 $数据报格式
版本：$ 4\enspace bit $，规定数据报的$ IP $协议版本
首部长度：由于首部中含有可选字段，因此需要使用首部长度确定载荷实际开始的地方
服务类型：$ 8\enspace bit $，代表报文处理方式，每一位分别代表最小延时、最大吞吐量、最高可靠性、最小成本，只选一个
数据报长度：首部加上载荷的总长度，以字节计，理论上数据报最大长度为$ 65535 $字节，但以太网链路报文只允许$ 1500 $字节
标识、标志、片偏移：与$ IP $分片有关，但$ IPv6 $不允许在路由器上分组分片
- 链路层帧大小有限，超过时应该进行分片处理
- 将一个大数据报拆分为几个小数据报，传输后在目的主机进行重组
- 标识：$ 16\enspace bit $，网络层服务的上层传输层的同一次报文（可能超过$ 1500 $字节），使用相同标记
- 标志：$ 3bit $，$ 1 $位保留，$ 2 $位表示是否能分片，$ 3 $位（$ MF $）表示分片是否结束（$ 1 $为未结束，$ 0 $为结束）
- 片偏移：每个分片在整个报文（分组）中的位置（以8字节为度量单位）
生存时间：确保数据报不会永远在网络中循环，每当一台路由器处理数据包时，该字段值减$ 1 $，减为$ 0 $时必须丢弃该数据报
协议：当数据报到达最终目的地时才有用，指示了载荷要交付给哪个特定的运输层协议，如$ 6 $标识$ TCP $，$ 17 $标识$ UDP $
数据报中的协议号将网络层与运输层绑定在一起，报文段中的端口号将运输层和应用层绑定在一起
首部校验和：按首部的每两个字节进行校验和计算，每台路由器都要重新计算首部校验和并放置在首部校验和位中
源和目的地址
如果不包含可选字段，$ IP $数据段的首部将包含$ 20 $个字节
首部长度不定（$ 20-60 $字节），中间节点（路由器）需要消耗相当资源用于分组处理
4.2.2 $ IP $地址
- $ IP $地址的定义
- 一台主机通常只有一条链路连接到网络；当主机中的$ IP $想发送数据报时，通过该链路发送
- 主机与物理链路之间的边界叫做接口
- 路由器负责从链路上接收数据报并从其他链路转发出去，其与任意一条与其连接的链路之间的边界也叫做接口
- 每条主机和路由器都能发送和接收数据报，因此$ IP $协议要求每台主机和路由器接口都有自己的$ IP $地址
- 一个IP地址和一个接口相关联，而不是与包含该接口的主机或路由器相关联
- $ IPv4 $编址
- 每个$ IP $地址长度为$ 32 $比特，因此共有$ 2^{32} $个可能的$ IP $地址
- 通常按照点分十进制记法书写，即地址中的每个字节用十进制表示，各字节间以句点隔开，如$ 193.32.216.9 $
- 地址分类
- 大约有$ 40 $亿$ IPv4 $地址，需要分类以便于寻址和层次化构造网络
- 在同一个局域网上的主机或路由器的$ IP $地址中的网络号必须一样
- 路由器具有两个及以上的$ IP $地址，其每一个接口都有一个不同网络号的$ IP $地址
- $ A $类地址以$ 0-127 $开头，$ B $类地址以$ 128-191 $开头，$ C $类地址以$ 192-224 $开头
特殊$ IP $地址
- 全$ 0 $主机号的$ IP $地址表示网络本身，如$ 129.152.0.0 $是网络号为$ 129.152 $的$ B $类网络
- 全$ 1 $主机号的$ IP $地址表示广播地址，如$ 129.152.255.255 $是网络号为$ 129.152 $的$ B $类网络的广播地址
- 十进制$ 127 $开头的地址是回环地址，用于测试自身$ TCP $或$ IP $软件是否正常
4.2.3 子网划分
子网的定义
- 划分子网以方便地址划分、分块管理，需要从主机号中借用一部分比特作为子网号
- 网络号唯一指定主机所在网络，该网络包含若干子网
- 子网号唯一指定主机所在子网
- 主机号唯一指定子网内某台主机
子网掩码
- 将网络号和子网号相应的位置全置$ 1 $，主机号相应的位置全置$ 0 $，得到子网掩码
- 将$ IP $地址和子网掩码相与得到网络地址
- $ A $、$ B $、$ C $类地址具有默认子网掩码
| 地址分类 | 默认掩码 | 网络号比特 | 主机号比特 | 子网可容纳主机数 |
|---|---|---|---|---|
| A | 255.0.0.0 | 8 | 24 | 2^24-2 |
| B | 255.255.0.0 | 16 | 16 | 2^16-2 |
| C | 255.255.255.0 | 24 | 8 | 2^8-2 |
子网寻址：先检查目的$ IP $地址的网络号，然后检查目的$ IP $地址的子网号
当主机$ 1 $访问主机$ 2 $时，先检查主机$ 2 $是否在本网络上：将目的主机地址$ 128.30.33.138 $与本网络子网掩码$ 255.255.255.128 $相与得到$ 128.30.33.128 $不等于子网$ 1 $的网络地址$ 128.30.33.0 $，说明主机$ 2 $不在主机$ 1 $的子网中
依次查询路由器$ R_1 $的路由转发表
- 对于第一条记录，目的主机地址与子网掩码相与得到$ 128.30.33.128 $不等于$ 128.30.33.0 $
- 对于第二条记录，目的主机地址与子网掩码相与得到$ 128.30.33.128 $等于该记录的目的网络地址，因此要访问目的主机时需要访问目的网络地址，也即经过路由器$ R_1 $的接口$ 1 $进行转发
子网划分
- 确定子网个数
- 确定每个子网内的最大主机数
- 确定从主机号字段中借用的比特数，用于创建子网号字段
- 确定主机号字段中保留的比特数
- 确定原始网络号字段和主机号字段的比特数
- 检查主机号字段长度大于第3步和第4步中确定的比特数
- 设置子网号字段的最佳长度
- 创建子网掩码
- 确定有效的子网号
- 确定每个子网的$ IP $地址范围
4.2.4 无类域间路由$ CIDR $
编码格式
- $ IP $地址表示为{网络前缀，主机号}
- 斜线记法：$ 192.168.0.1/25 $表示左边$ 25 $位为网络前缀，对应子网掩码表示中的$ 192.168.0.1/255.255.255.128 $
- 简写记法：$ 10.0.0.0/10 $简写为$ 10/10 $
示例
- 假设某个地址块为$ XX.XX.XX.XX/n $，即该地址块的左边$ n $位为网络前缀，则剩余$ 32-n $位用来具体表示主机号，其地址数为$ 2^{32-n} $
- 这个$ ISP $共有$ 64 $个$ C $类网络。如果不采用$ CIDR $技术，则在与该$ ISP $的路由器交换路由信息的每一个路由器的路由表中，就需要有$ 64 $个项目。但采用地址聚合后，只需用路由聚合后的$ 1 $个项目$ 206.0.64.0/18 $就能找到该$ ISP $。
寻址方式
使用$ CIDR $编址后，路由转发表变为如下格式
最长前缀匹配
- 使用$ CIDR $时，路由表中的每个项目由网络前缀和下一跳地址组成
- 在查找路由表时可能会得到不止一个匹配结果，此时从匹配结果中选择具有最长网络前缀的路由
- 网络前缀越长，其地址块就越小，因而路由就越具体
如对于实例中，假设目的地址为$ 206.0.71.142 $，其匹配大学的地址块前缀$ 206.0.68.0/22 $，也匹配四系的地址块前缀$ 206.0.71.128/25 $，根据最长前缀匹配规则，需要匹配四系的地址块
示例（B、A、E、F、C、D）
4.2.5 网络地址转换$ NAT $
实现原理
发送数据报：将每个向外发送报文的源$ IP $地址与端口号映射为$ NAT\enspace IP $地址以及新端口号；
同时远程客户机或者服务器将以$ NAT\enspace IP $地址以及新端口号做为目的地址进行响应
- $ NAT $路由器将每一个地址转换对记录在$ NAT $转换表中
转换表的表项为：(源$ IP $地址,端口号)$ \rightarrow $($ NAT $的$ IP $地址,新端口号)
接收数据报：根据$ NAT $转换表将每个向内发送报文的$ NAT\enspace IP $地址和端口号替换为相应的源$ IP $地址以及端口号
内网主机对外网不可见；$ ISP $变更后内网地址无需变化
使用$ NAT $的变化
| 不使用$ NAT $ | 使用$ NAT $ |
|---|---|
| 主机=$ IP $ | 主机=$ IP $+端口 |
| 统一全球地址 | 全球地址+本地地址 |
| 主机访问双向公平 | 外网主机无法主动访问内网主机 |
4.2.6 $ IPv6 $数据报格式
由于$ IPv4 $地址池即将用尽，因此为了适应对大$ IP $地址空间的需求，开发了新的$ IP $协议——$ IPv6 $协议
- $ IP $地址长度被扩大为$ 128 $比特，首部长度为固定为$ 40 $字节
版本：标识$ IP $版本号，该字段值为$ 6 $时即表示$ IPv6 $协议
注意：该字段值置为$ 4 $并不能创建合法的$ IPv4 $数据报
流量类型：同$ IPv4 $中的$ TOS $字段
流标签：用于标识一条数据报的流
有效载荷长度：无符号整数，指示数据的字节数
下一个首部：标识需要交给哪个运输层协议，如$ UDP $或$ TCP $
跳限制：同$ IPv4 $中的生存时间
不存在分片与重组：中间结点不再负责分片和重组，由端结点负责
即不允许在中间路由器上进行分片与重组，只能在源和目的地执行；当路由器接收到的$ IPv6 $数据报太大时，会丢弃数据报并发回分组太大的$ ICMP $差错报文
不存在首部校验和：中间节点无需计算
不存在选项字段：首部长度固定，加速中间节点转发速度
从$ IPv4 $到$ IPv6 $
双栈技术
- 新加入的设备支持$ IPv4/IPv6 $双协议栈
- 一段链路上，如果源和目标均支持$ IPv6 $，则使用$ IPv6 $进行通信
- 如果任一方不支持$ IPv6 $，则使用$ IPv4 $进行通信
- 转换开销较大，可能会出现信息的丢失
隧道技术
- 将$ IPv6 $的数据报封装在$ IPv4 $的数据报中，即建立隧道传输$ IPv6 $数据报
4.3 路由器的工作原理
4.3.1 路由器结构
路由器基本结构
输入端口：执行物理层的线路连接功能；执行数据链路层功能；执行网络层查找功能决定输出端口
交换结构：根据输入端口查找得到的输出端口，将数据转发到对应的输出端口
输出端口：存储从交换结构接收的分组，并执行对应的链路层和物理层功能
路由选择处理器：执行控制平面功能
转发方式：如何选择输出端口
- 基于目的地转发：根据输入分组的最终目的地转发，类比于在立交桥中根据目的地决定出口
- 通用转发：除了目的地，还根据其他因素进行转发
4.3.2 输入端口
基于目的地转发
对于$ 32 $位的$ IP $地址，在转发表中可以维护每个目的地址的表项，但需要维护的表项数十分庞大
实际上，可以通过将目的地址进行分组管理，通过前缀匹配的方式进行转发
当有多个匹配项时，采用最长前缀匹配规则：寻找表中最长的匹配项
例如有如下仅包含$ 4 $个表项的转发表
前缀匹配 输出接口 $ 1100,1000,0001,0111,0001,0 $ $ 0 $ $ 1100,1000,0001,0111,0001,1000 $ $ 1 $ $ 1100,1000,0001,0111,0001,1 $ $ 2 $ 其他 $ 3 $ 对于目的地址是$ 1100,1000,0001,0111,0001,0110,1010,0001 $的分组，其匹配转发表中的第一项，因此将被转发到输出接口$ 0 $；对于目的地址是$ 1100,1000,0001,0111,0001,1000,1010,0001 $的分组，其匹配转发表中的第二项和第三项，但根据最长前缀匹配规则，将被转发到输出接口$ 1 $
4.3.3 交换结构
内存交换
- 输入和输出端口间的交换是在路由处理器的直接控制下完成
- 分组被拷贝到系统内存中，在$ CPU $的控制下转发至输出端口
- 转发速度受限于内存带宽（每个分组走两次总线）
总线交换
- 输入报文经共享总线将分组直接转发到输出端口
- 总线交换速度受限于总线带宽
内联网络交换
- 克服总线带宽限制
4.3.4 输出端口
排队现象的产生
- 设输入线路和输出线路的传输速率相同，均为$ R_{line}\enspace pkt/s $，有$ N $个输入输出端口，交换结构传送速率为$ R_{switch} $
- 当$ R_{switch}\gg R_{line} $时，可以使得输入的分组无时延地通过交换结构
输入排队
- 当$ R_{switch} $不满足$ R_{switch}\gg R_{line} $时，将使得输入端口出现分组排队
- 线头阻塞：输入队列中排队分组被位于线头的另一个分组阻塞，须等待交换结构发送
- 当两个不同输入端口的分组均要发往同一个输出端口时，其中一个分组必须等待交换结构转发完毕另一个分组
输出排队
当$ R_{switch} $超过$ R_{line} $时，需要对分组进行缓存
输出端口缓冲区溢出会导致分组的排队和丢失
缓冲区大小：对于有$ N $条$ TCP $连接经过的链路而言，缓存数量为$ B=RTT\frac{R}{\sqrt{N}} $
其中$ R $为链路容量，$ RTT $为平均往返延迟
※4.4.7 $ ICMP $协议
- 用途
- 分类
- 报文格式
- 应用
- $ Ping $命令
- $ Tracert $命令
4.5 路由协议
4.5.1 概述
什么是路由
- 路由是从源主机到目的主机的路径
- 路由是在路由器上执行的过程，包括接收路由协议、对路由进行选路
- 路由是在两个路由器间传递消息的路由协议
- 路由是在路由协议的处理下得到的路由表
什么是好的路由
- 好的路径：无环路，可收敛，费用低
- 好的路由协议：开销低（内存、带宽占用），安全性高
- 好的路由表：保存局部路由，共同构成完成路由
什么是路由器
默认路由器：一台主机连接到的路由器
源路由器：源主机的默认路由器
目的路由器：目标主机的默认路由器
给定一组路由器以及连接路由器的链路，从中找到一条从源路由器到目标路由器的好路径
例外：$ A $和$ B $之间的路径费用很低，但是二者处于两个组织之间，而这两个组织作出的路由策略不允许相互通行
路由抽象模型
该模型表示为图$ G(N,M) $
其中路由器集$ N=\{u,v,w,x,y,z\} $，链路集$ M=\{(u,v),(u,x), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z)\} $
- $ c(x,x’) $为节点$ X $和$ X’ $间边的费用，例如图中$ c(w,z)=5 $
费用可以是经济的，但也有可能和链路的带宽以及链路拥塞状况有关
路径费用$ (x_1, x_2, x_3,\cdots, x_p) = c(x_1,x_2) + c(x_2,x_3) + \cdots + c(x_{p-1},x_p) $
选路算路就是选取路径费用最低的路径
选路算法分类
按照性能目标分类
链路状态算法——基于路径成本最优
- 所有路由器都知道整个网络拓扑图以及链路的费用信息
距离向量算法——基于路径距离最短
- 每个路由器仅有与其相连链路的费用信息，通过迭代计算过程与相邻节点交换信息
- 路由信息可以更快地变化，可以响应拓扑或链路费用的变化
按照负载是否敏感分类
- 负载敏感算法：链路费用会动态地变化以反映出链路的当前状况
- 负载迟钝算法：链路费用不明显地反映链路的当前状况
4.5.2 链路状态选择算法$ LS $与$ OSPF $
迪杰斯特拉算法
- 算法概述
- 给定带权图$ G=\langle V,E,W\rangle $（所有边的权重为正值）和源路由器$ s $，找到源路由器$ s $到所有其他路由器$ t $的最小成本$ \delta(s,t) $和最小成本路径$ \langle s,\dots,t\rangle $
- 算法从结点集$ V-S $中选择当前最小成本路径估计最小的路由器$ u $，将$ u $从$ Q $中删除，并加入到$ S $中，$ u.d $就是源路由器$ s $到$ u $的最短路径的长度。这里$ Q $是一个最小优先队列，保存结点集$ V-S $
- 以每个结点为源路由器，由上述算法得到的最小生成树即可得到源路由器到其他路由器的转发表
- 前提：所有节点都知道网络拓扑和链路费用
- 所有节点具有该网络的同一个完整的视图
- 通过链路状态广播获得信息
- 目标：产生某节点的转发表
- 计算从某节点到网络中所有其它节点的最低费用，并产生转发表
- 算法复杂度为$ O(n^2) $
- 算法的问题
- 当模型采用负载流量作为路径成本，即模型为负载敏感型网络时，会产生振荡问题
- 解决方案
- 不以负载流量作为成本——无法解决高拥塞问题
- 所有的路由器不同时运行$ LS $算法
- 算法概述
- $ OSPF $协议
即$ Open\enspace Shortest\enspace Path\enspace First $协议，公开发表的最短路径优先协议
协议交互范围：工作在本自治系统域内，采用泛洪法发送消息
协议交互消息内容：与本路由器相邻的所有路由器的链路状态
协议交互时机：仅当链路状态发生变化时，采用泛洪法向所有路由器发送信息
当链路状态发生变化时，每个路由器都向本$ AS $中的所有路由器发送与本路由器相邻的所有路由器的链路状态，信息发送完毕后，所有路由器上都将有全网一致的拓扑结构图
即使链路状态未发生变化，每$ 30 $分钟广播一次链路状态
链路状态以$ OSPF $通告的形式封装在报文中，由$ IP $分组承载（协议号：$ 89 $）
$ OSPF $路由器之间的交换经过$ MD5 $鉴别，以确认$ OSPF $通告的真实性，防止伪造和篡改
4.5.3 距离向量选择算法$ DV $与$ RIP $
- 距离向量选择：$ d_x(y)=min_v{c(x,v)+d_v(y)} $
- $ RIP $路由表更新算法
- 路由器$ X $得到相邻路由器$ Y $的路由表，从而得知$ Y $到网络$ Z $的最短距离为$ N $
- 如果路由器$ X $没有到网络$ Z $的路由条目，则添加一条经由路由器$ Y $到网络$ Z $距离$ N+1 $的路由条目
- 如果路由器$ X $已有到网络$ Z $的路由条目，其距离为$ M $，如果$ M>N+1 $，则更新该条目为经由路由器$ Y $到网络$ Z $距离$ N+1 $，否则不更新
- 当链路状态改变时
- 在$ t0 $时刻，$ y $检测到链路费用变化，更新距离向量，同时将这个变化通知给它的邻居
- 在$ t1 $时刻，$ z $收到来自$ y $的更新报文并更新距离向量表，计算出到$ x $的新的最低费用，并向邻居发送它的新距离向量
- 在$ t2 $时刻，$ y $收到自$ z $的更新并更新其距离向量表，$ Y $的最低费用未变，因此$ y $不发送任何报文给$ z $
- 协议参数
- 链路费用：相邻两点链路费用为$ 1 $跳，最大费用限制为$ 15 $
- 通告周期：选路更新通告周期为$ 30 $秒
- 邻居离线：邻居离线判定周期为$ 180 $秒
- 协议端口：基于$ UDP $，端口为$ 520 $
4.5.5 域间$ BGP-4 $协议
- 层次路由
- 因特网规模过大，导致路由器无法存储每台主机的选路信息，路由表更新的报文广播将导致无剩余带宽供发送数据使用
- 将路由器聚合到一个区域，即自治系统$ AS $，在不同$ AS $内的路由器可以运行不同的自治系统内部选路协议
- 转发选路算法
- 转发表是由$ AS $内部选路算法和$ AS $间选路算法共同决定的
- $ AS $内部选路算法为内部目的地址设置转发表信息
- $ AS $内部选路算法和$ AS $间选路算法共同为外部目的地址设置转发表信息
- 假设从源到目标仅有一条路可选
- 假设$ AS1 $从$ AS $间选路协议知道子网$ x $经过网关路由器$ 1c $至$ AS3 $可达，但是通过$ AS2 $不可达
- $ AS1 $向它的所有路由器广播该可达信息
- 路由器$ 1d $知道，它的接口$ I $在到路由器$ 1c $的最低费用路径上
- 从而路由器$ 1d $将表项$ (x,I) $放入其转发表
- 假设从源到目标有多条路径可选
- 现在假设$ AS1 $知道子网$ x $可以通过$ AS3 $和$ AS2 $到达
- 为了配置转发表, 路由器$ 1d $必须决定通过哪个网关路由器转发报文（$ 1b $或$ 1c $）
- 热土豆选路: 将报文发送到最近的路由器
- $ BGP-4 $发言人
- 每一个$ AS $要选择一个路由器作为该$ AS $的$ BGP $发言人
- 两个$ BGP $发言人通过一个共享网络连接在一起
- $ BGP $发言人通过$ BGP $通告广播该自治系统$ AS $能够到达哪些网络
- 通过将多个路由前缀聚合为单一前缀并转发之达到路由通告的目的
- 发言人得知某些通告信息后，向该$ AS $内的路由器广播，路由器为之创建新的表项
- 路由通告中包含前缀（能够到达的网络前缀）、路径（到达前缀地址经过的路径）、下一跳（到达前缀地址需要经过的下一跳地址）
