第四章—网络层：数据面

4.1概述

1. 网络层三大功能：
   1. 转发：
      • 将分组从一个输入链路接口转移到适当的输出链路接口的路由器本地动作
      • 路由器通过以分组首部字段的值为索引，在转发表中查询输出链路接口
   2. 路由选择：
      • 决定分组从源到目的地所采取的端到端路径，是网络范围内的过程
      • 路由器接收集中式/分布式产生的路由选择协议报文，用于配置转发表
   3. 连接建立：
      • 源到目的地沿着所选路径彼此握手，以便在分组流动之前建立起状态
2. 路由器：基于网络层字段的值做转发决定
   • 链路层交换机：基于链路层字段中的值做转发决定
3. 网络服务模型：定义了分组在发送与接收端系统之间的端到端运输特性
   • 因特网网络服务模型只提供尽力而为的服务

4.2虚电路和数据报网络

1. • 虚电路网络：在网络层提供连接服务（ATM、帧中继）
   • 数据报网络：在网络层提供无连接服务（IP）
2. 虚电路组成：
   • 源和目的主机之间的路径（一系列链路和路由器）
   • 沿着该路径每段链路的VC号（每条链路的VC号可能不同）
   • 沿着该路径的每台路由器的转发表（建立一条虚电路增加响应表项）
3. 使用不同VC号的原因
   • 减少了在分组首部中VC字段的长度
   • 不同路由器不用就VC号进行协商，简化了虚电路的建立
4. 虚电路三阶段：
   1. 虚电路建立：决定路径、为链路分配VC号，填写转发表、预留路径资源
   2. 数据传送：基于入接口和入VC号决定出接口和出VC号
   3. 虚电路拆除：删除路径路由中的转发表
5. • 信令报文：端系统、路由器之间传递的用于建立虚电路的报文
   • 信令协议：交换信令报文的协议
6. 路由转发表：
   • 虚电路：将（入接口，入VC号）映射到（出接口，出VC号）
   • 数据报：采用最长前缀匹配，将目的地址映射到链路接口

4.3路由器工作原理

1. 路由器组成：
   • 路由器转发平面：用硬件实现
     • 输入端口：将一条物理链路与路由器连接与位于入链路远端的数据链路层交互； 查询转发表决定路由器的输出端口
     • 交换结构：连接路由器的输入端口和输出端口
     • 输出端口：类似输入端口
   • 路由器控制平面：用软件实现
     • 路由选择处理器：执行路由选择协议；维护路由选择表以及连接的链路状态信息；为路由器计算转发表；执行网络管理
2. 影子副本：路由选择处理器将转发表副本存放在每个端口，避免集中式处理
3. 线路前部阻塞：输入队列中排队的分组必须等待其前面正在等待的分组被发送
4. 交换结构：
   1. 经内存交换：分组从输入端口复制到内存，再复制到输出端口缓存
   2. 经总线交换：分组通过总线发往所有输出端口，只有特定输出端口能保存
   3. 纵横式交换：能并行转发具有不同输入与输出端的分组

4.4网际协议：因特网中的转发和编址

1. 因特网网络层三组件：
   1. IP协议：网络层主要协议
   2. 路由选择协议：用于计算转发表
   3. ICMP协议：因特网控制报文协议，用于因特网的网络层差错和信息报告
2. IPv4数据报格式（首部通常为20字节）
   • 版本号：规定IP协议版本，以便让路由器确定如何解释剩余部分
   • 首部长度：以32bits为单位
   • 服务类型：区分不同类型的IP数据报
   • 数据报长度：首部加上数据的长度，以字节为单位
   • 标识：发送主机给它发送的每个数据报的标识号加1
   • 标志：指示某分片是否是数据报的最后一片，0是，1不是
   • 片偏移：确保目的主机按正确的顺序重新组转片
   • 寿命：还能经过的路由跳数，为0时该数据报必须丢弃
   • 上层协议：指示IP数据报的数据部分应该交给哪个运输层协议
   • 首部检验和：以2字节为单位，相加求和，每台路由器都要重新计算该值IP地址
   • 源IP地址
   • 目的IP地址
   • 选项：允许IP首部扩展（IPv6已删去）
   • 数据
3. 最大传送单元MTU：链路层帧能承载的最大数据量
4. IP数据报大于MTU时，路由器将其拆分成片，最终全部在端系统重新组装
5. 分片的过程
   • 标识号不变
   • 标识号只有最后一片为0，其余为1
   • 片偏移指示前面数据量大小，以8字节为单位
6. 接口：主机/路由器与链路之间的边界，主机只有一个，路由器有多个
7. IP地址：与接口相关联，具有全球唯一性（NAT后面的接口除外）
8. 子网：互联主机接口与某个路由器接口的网络
   • 子网掩码：用于划分IP地址的网络地址与主机地址
9. 因特网的地址分配策略为无类别域间路由选择CIDR
10. 使用单个网络前缀通告多个网络的能力为地址聚合、路由聚合、路由摘要
11. 默认网关：第一跳路由器地址
12. 动态主机配置协议DHCP：
    • DHCP服务器发现：新加入的主机用广播地址发送DHCP发现报文
    • DHCP服务器提供：服务器响应以广播地址发送DHCP提供报文回馈相关信息
    • DHCP请求：客户选择配置参数后向选中的服务器发送DHCP请求报文
    • DHCP ACK：服务器用DHCP ACK报文确认
13. 保留地址空间：
    10.0.0.0/8
    172.16.0.0/12
    192.168.0.0/16
14. 网络地址转换NAT：
    • 将来自NAT背后的（源IP地址，端口号）映射为NAT面向广域网的（NAT的IP地址，新端口号），即通过虚拟端口号的辅助，来扩展寻址能力
    • 通用即插即用UPnP协议是一种允许主机发现并配置邻近NAT的协议，NAT穿越正越来越多地由UPnP协议提供
15. 反对NAT的理由：
    • 端口号是用于进程编址的，而不是用于主机编址的
    • 路由器通常仅应当处理到网络层分组
    • 违反了端到端原则，即结点不应介入主机与主机的直接对话
    • 应使用IPv6来解决IP地址短缺问题
16. 因特网控制报文协议ICMP：
    • 作为IP有效载荷承载，用于主机和路由器彼此沟通网络层的信息
17. IPv6数据报格式：
    • 版本号：
    • 流量类型：类似IPv4服务类型字段
    • 流标签：用于标识一条数据报的流
    • 有效载荷长度：有效载荷的字节数
    • 下一个首部：类似IPv4上层协议字段
    • 跳限制：类似IPv4的TTL
    • 源地址：扩展到128bits
    • 目的地址：扩展到128bits
    • 数据
18. IPv6特性：
    • 将地址容量从32bits扩展到了128bits
    • 不允许中间路由器进行分片，数据报太大时直接丢弃，告知端系统分片
    • 不再计算首部检验和
    • 不再显式包含选项，而将其转移到下一个首部指出的位置上
19. IPv4向IPv6的迁移：双栈、建隧道

第五章 网络层：控制面

5.1路由选择算法

1. • 默认路由器：与主机相连接的第一跳路由器
   • 源路由器：源主机的默认路由器
   • 目的路由器：目的主机的默认路由器
2. • 全局式路由选择算法：具有全局状态信息，也叫链路状态算法
   • 分散式路由选择算法：路由随时间流逝变化缓慢
   • 动态路由选择算法：周期性地运行或直接响应拓扑或链路费用的变化
   • 负载敏感算法：链路费用会动态变化以反映出底层链路的当前拥塞水平
   • 负载迟钝算法：链路费用不明显地反映其当前拥塞水平
3. 链路状态LS算法：即Dijkstra算法
4. 距离向量DV算法：即Bellman-Ford算法
   • 每个结点都维护它自身到所有目的地的费用的估计值，作为距离向量
   • 每个结点都存储其所有邻居的距离向量的最新副本
   • 每次收到邻居点或相邻边代价变化时，检查自身是否可以更新
   • 若自身成功更新，则将更新后的距离向量发送给邻居以供其存储
   • 若自身成功更新，则将更新后的距离向量发送给邻居以供其储存
   • 可以通过增加毒性逆转来解决2个结点的无穷计数问题
5. 链路状态LS算法VS距离向量DV算法
   • 报文复杂性：LS算法每个结点向所有结点发送报文；DS算法只在相邻结点之间交换报文
   • 收敛速度：LS算法相较而言收敛较快；DS算法收敛较慢，且在收敛时会遇到路由选择环路问题
   • 健壮性：LS算法的计算在某种成都上是分离的，提供了一定的健壮性；DV算法中一个不正确的结点的计算值会影响到整个网络

• 自治系统AS：由一组通常处在相同管理控制下的路由器
• 自治系统路由选择协议：在一个自治系统内运行的路由选择算法
• 网关路由器：一个AS中负责向其他AS转发分组的路由器
• 热土豆协议：路由器总是选择一个可到目的地的AS内代价最低的网关路由器

5.2路由器中的路由选择

1. • AS内路由选择协议（内部网关协议）：路由选择信息协议RIP，开放最短路优先OSPF
   • AS间路由选择协议（外部网关协议）：边界网关协议BGP
2. RIP协议：
   • 通常设置于下层ISP和企业网中
   • 是一种距离向量协议，运行方式类似于DV算法
   • 以经过的子网数量（跳数）作为路径费用
   • 最大费用限制为15，使得RIP的使用限制在网络直径不超过15跳的AS内
   • 每台路由器维护路由选择表（距离向量+转发表）
   • 路由选择信息在邻居间通过RIP响应报文（RIP通告）来交互
   • RIP通告大约每30秒交互一次，超过180秒不交互，默认不可达
   • RIP通告即路由选择表，路由器每次收到RIP通告后合并进自己的选择表
   • RIP使用运输层协议UDP上的端口520来实现网络层协议的信息维护
3. OSPF协议：
   • 通常设置在上层ISP中
   • 是一种链路状态协议，运行方式类似于Dijkstra算法
   • 链路的费用权值由网络管理员配置
   • 路由器向系统内的所有路由器广播路由选择信息
   • 链路状态变化时，路由器广播链路状态信息，无变化也会周期性的进行广播
   • OSPF使用IP承载，需要自行实现可靠报文传输与链路状态广播等功能
   • AS内部配置成多个区域，其中一个为主干区域，包含所有区域边界路由器
   • 分组先路由到源区域边界路由器，再通过主干路由到目的区域边界路由器
   • 具有安全，可使用等费用的多条路径，支持单播与多播，支持层次结构等优点
4. BGP协议：
   • 建立了半永久BGP TCP连接（BGP会话）的路由器对成为BGP对等方
   • 跨越AS的BGP会话为外部eBGP会话，AS内的BGP会话为内部iBGP会话
   • 不作为流量中转2的AS成为桩网络，除桩网络外的AS都具有自治系统号ASN
   • 路由器通过BGP会话交互的信息为前缀与属性值所构成的路由
   • 属性值AS-PATH包含了该路由已通过的那些AS的ASN
   • 属性栈NEXT-HOP为该路由中连接本AS的上一个AS的路由器的IP地址
   • BGP是面向策略的AS间路由选择协议，除了跳计数外没有费用的概念
   • 路由选择顺序：偏好->最短AS-PATH->最靠近NEXT-HOP->BGP标识符
5. 在AS间和AS内选择不同路由选择协议的原因：
   • 策略：AS内优先考虑代价，AS间优先考虑策略
   • 规模：AS路由选择要考虑可扩展性，AS内路由选择不需要
   • 性能：AS间路由选择能依据策略选择路径，AS内路由选择要关注于性能

5.3广播和多播路由选择

1. 用单播实现广播
   • 实现：源结点产生分组的N份副本，并利用单播路由向N个目的地址传输
   • 缺点：效率不高；接收方地址不一定为发送方所知；广播的目的是生成和更新单播路由，用目的取代手段不够明智
2. 无控制洪泛广播：
   • 实现：源节点向它的所有邻居发送分组的副本；当某结点收到一个分组时，保存并向邻居转发
   • 缺点：不能完全避免冗余分组的传播
3. 序号控制洪泛（受控洪泛）广播
   • 实现：广播分组中加入源结点地址和广播序号；每个结点维护接收到的每个广播分组的序号列表；当收到在列表中的广播分组时，直接丢弃；当收到不在列表中的分组时，保存并向邻居转发
   • 缺点：不能完全避免冗余分组的传播
4. 反向路径转发RPF（受控洪泛）广播：
   • 实现：广播分组中加入源节点地址：每个结点维护它在发送方的单播路径上的前驱结点；当收到来自非前驱结点的分组时，直接丢弃；当收到来自前驱结点的分组时，保存并向邻居转发
   • 缺点：不能完全避免冗余分组的传播
5. 生成树广播:
   • 实现：基于中心结点（汇合点/核）建立一棵生成树：每个结点维护它在生成树中的邻居；发送分组时只在生成树链路中进行
6. 多播服务：
   1. 多播分组仅被交付给网络结点的一个子集
   2. D类多播地址为表示一组接收方的单一标识
   3. 多播组为一个与D类多播地址相关联的接收方小组
   4. 使用因特网组管理协议IGMP与多播路由选择协议
7. IGMP协议：
   • 运行在一台主机和与其直接相连的路由器之间
   • membership_query报文：路由器用于查询接口上的主机已加入的多播组集合
   • membership_report 报文：主机通知路由器其加入的多播组集合
   • leave_group 报文：主机通知路由器其离开了某多播组（可以省略）
   • 当无主机响应一个具有给定组地址的查询报文时，则断定无主机还在该多播组
8. 软状态机制：
   • 状态若未被显式地更新，则通过超时事件被删除
9. 多播路由选择算法：
   • 目标：发现一棵链路的树连接了所以某多播组的路由器
   • 实现：使用组共享树（即基于核心），维护代价小，发送代价可能不是最优；使用基于源的树，维护代价大，发送代价为最优
10. 因特网中的多播路由选择
    • 距离向量多播路由选择协议DVMRP：反向路径转发+剪枝
    • 协议无关多播路由选择协议PIM：稠密模式类似DVMRP；稀疏模式使用聚焦点来建立多播分发树

第六章 链路层（协议栈中软硬件交流的地方）链路、接入网和局域网

6.1 链路层概述

1. 结点：运行链路层协议的任何设备（主机、路由器、交换机、WIFI接入点）
   链路：沿着通信路径连接相邻结点的通信信道
2. 链路层提供的服务：
   1. 成帧
   2. 链路接入，使用媒体访问控制协议MAC
   3. 可靠交付，通过确认与重传实现
   4. 差错检测与纠正，用硬件实现
3. 网络适配器（网卡）：类似于I/O设备，连接在PCI上，包含控制器和物理传输线路
4. 大部分链路层在硬件中实现，部分在软件中实现，链路层是软硬件结合的地方

6.2差错检测和纠正技术

1. 使用差错检测和纠正比特EDC来增强数据D，可以尽可能地检测出比特差错
2. 一维奇偶校验：包含附加比特，使得1的总数是偶数；二维奇偶校验：划分i行j列，对每行每列使用一维奇偶校验
3. 前向纠错：接收方检测差错并纠正；后向纠错：接收方检测差错并请求重传来恢复
4. 检验和方法：将数据划分为k比特的序列，相加后取反
5. 循环冗余检测CRC：
   • 所有加减采用异或方式进行
   • 对r+1位的生成多项式（二进制串）
   • 在数据后添加r个0，然后除以生成多项式
   • 用所得余数替换数据后添加的r个0，即得CRC编码（多项式编码）
   • 每个CRC标准都能保证检测出最多r比特的差错和任何奇数个的比特差错

6.3 多路访问链路和协议

1. 多路访问协议：用于协调多个发送和接收结点对一个共享广播信道的访问
2. 理想多路访问协议的特性：
   • 仅有一个结点有数据要发送时，应能让他使用到全部的带宽
   • 多个结点有数据要发送时，平均吞吐量应大致相等
   • 协议是分散的，不会因某主结点故障而使整个系统崩溃
   • 协议简单，实现不昂贵
3. 信道划分协议：
   1. 时分多路复用TDM：时间划分为时间帧，帧划分为时隙
   2. 频分多路复用FDM：信道划分为不同频段
   3. 码分多址CDMA：每个结点用其唯一编码来编码数据，可同时传输消除碰撞
4. 随机接入协议：
   1. 时隙ALOHA：有新帧要发送时，在下一个时隙开始时传输整个帧；若出现碰撞，则之后的每次重传以概率p进行；效率定义为长期运行中成功时隙的份额，约为0.37
   2. 纯ALOHA： 有新帧要发送时，立即传输整个帧；若出现碰撞，则之后的每次传输以概率p进行；效率为时隙ALOHA的一半，约为0.185
   3. 载波侦听多路访问CSMA：
      • 结点传输前先侦听信道，检测到一小段时间没有传输时才开始传输
      • 信道传播时延越大，结点不能及时侦听到传输的机会越大
   4. 具有碰撞检测的载波侦听多路访问CSMA/CD
      • 检测到碰撞立即停止传输
      • 效率为$1/(1+5\cdot d_{prop}/d_{trans})$
   5. 二进制指数后退算法：
      • 经历n次碰撞后，随机从{0,1,2...,2n−1}\{0,1,2...,2^n-1\}{0,1,2...,2n−1}中选取k值，然后等待发送512比特所需时间的k倍
5. 轮流协议：
   1. 轮询：
      1. 主结点轮询到的结点才可以传输
      2. 能传输的帧的最大数量由主结点通知
   2. 令牌传递：
      1. 持有令牌的结点才可以传输
      2. 无帧可发或发送完一个帧，将令牌传递给下一个结点

5.4 交换局域网

1. MAC地址：（LAN地址、物理地址）
   • 格式：6字节，以十六进制数表示为xx-xx-xx-xx-xx-xx
   • 性质：没有两块适配器具有相同的地址；FF-FF-FF-FF-FF-FF为广播地址
   • 必要性：可以支持各种网络层协议（不只是IP协议）
2. 地址解析协议ARP：
   1. ARP为同一子网上的主机和路由器将IP地址解析为MAC地址
   2. 主机和路由器的每一个接口都有其ARP表，存储IP地址到MAC地址的映射
   3. ARP表中的项目通过ARP查询、响应报文来更新，且具有寿命值TTL
   4. ARP查询、响应报文包括：发送方IP、接收方IP、发送方MAC、接收方MAC
   5. ARP查询报文在广播帧中发送，ARP响应报文在标准帧中发送
   6. ARP是跨越链路层和网络层的协议
3. 发送数据报的过程：
   1. 主机查询ARP表，是否具有对应IP地址的MAC地址
   2. 若未在ARP表中查到相应表项，使用ARP查询报文在子网中进行广播
   3. ARP查询报文中包含目的IP地址和目的MAC地址FF-FF-FF-FF-FF-FF
   4. 子网中所有适配器拆封ARP查询报文的帧，将其上交给自身的ARP模块
   5. 主机检查自身IP地址是否与目的IP地址相匹配，匹配则回应ARP响应报文
   6. 路由器检查目的IP地址是否应由自己转发，是则回应ARP响应报文
   7. 源主机收到ARP响应报文后，把IP地址到MAC地址的映射插入ARP表
   8. 主机向目的MAC地址发送链路层帧
   9. 所有适配器都会处理到达自身的帧，但只将MAC地址符合要求的帧上交
4. 以太网的变革：
   1. 同轴电缆+转发器->集线器星型拓扑->交换机星型拓扑
   2. 转发器：物理层设备，在输入端接收信号并在输出端再生信号，使得传输更长距离
   3. 集线器：物理层设备，作用于比特，放大传输其受到的信号
   4. 交换机：链路层设备，作用于帧，不会出现碰撞
5. 以太网帧结构：
   1. 数据字段：46-1500字节，超过需要分片，少于则需要填充
   2. 目的地址：目的适配器的MAC地址6字节
   3. 源地址：源适配器的MAC地址6字节
   4. 类型字段：上层协议号2字节（类比TCP端口号、IP协议字段）
   5. CRC：循环冗余检测码4字节
   6. 前同步码：前7字节为10101010用唤醒和同步，最后一字节10101011
6. 以太网的差错检验：
   • 使用CRC校验收到的帧，通过则保留，不通过则丢弃
   • 不管校验结构如何，都不会反馈校验信息
7. 以太网标准：例 100BASE-T 代表 100Mbps 传输速率的基带以太网，媒介为双绞铜线
8. 链路层交换机：
   1. 本身不具有MAC地址，对于子网中的主机和路由器是透明的
   2. 全双工，交换机和结点可以同时向对方发送帧而不产生碰撞
   3. 把接收的所有帧的源MAC地址到接口的映射加入交换机表，并加注当前时间
   4. 接收的帧的目的MAC地址在交换机表中时，按照映射转发到特定接口
   5. 接收的帧的目的MAC地址不在交换机表中时，广播该帧
   6. 及时删除交换机表中已经老化的映射
9. 链路层交换机的性质：
   • 消除碰撞，使得最大聚合带宽为交换机所有接口速率之和
   • 隔离异质链路，使得不同链路能以不同速率在不同媒体上运行
   • 强化安全，检测异常适配器并断开连接
   • 方便管理，收集带宽使用的统计数据、碰撞率和流量类型等，提供管理员使用
10. 交换机毒化：
    • 向交换机发送大量具有不同伪造源MAC地址的分组
    • 交换机表被伪造表项填充满，导致大部分合法分组被广播
    • 嗅探器从而俘获到合法分组
11. 交换机VS路由器
    • 交换机：
      • 优点：即插即用、更高的分组过滤和转发速率
      • 缺点：拓扑有生成树限制、无法抵抗广播风暴
    • 路由器：
      • 优点：拓扑无生成树限制、防火墙保护可以抵抗广播风暴
      • 缺点：不是即插即用、对分组的处理时间更长
12. 虚拟局域网：
    • 通过单一的物理局域网基础设施来定义多个虚拟局域网
    • 交换机维护一张端口到VLAN的映射表
    • 交换机软件仅在属于相同VLAN的端口之间交付帧
    • 不用VLAN之间需要通过路由器联系
    • 合并不同交换机上的相同VLAN可以使用端口互连或干线连接
    • 扩展以太网帧格式802.1Q添加4字节VLAN标签用于跨越VLAN干线
    • VLAN标签：2字节标签协议标识符、12比特VLAN标识符、3比特优先权