计算机网络 第五章 网络层

第五章 网络层

网络层概述

网络层在数据链路层提供的两个相邻端点之间的数据帧的传送功能上，进一步管理网络中的数据通信，将数据设法从源端经过若干个中间节点传送到目的端，从而向运输层提供最基本的端到端的数据传送服务。

网络层向传输层提供的服务

数据报（无连接服务）

虚电路（面向连接服务）

数据报VS虚电路

问题|数据报网络|虚电路网络
| —— | —— | —— |
电路建立|不需要|需要
寻址|每个包包含全部的源和目标地址|每个包包含简短的VC号
状态信息|路由器不保留连接状态|针对每个连接，每条VC都需要路由器保存其状态（要增加表项）
路由方式|每个数据包被单独路由（每个分组独立选路，导致路线不一样）|建立VC时选择路由（之后就不用再选路了），所有包都遵循该
路由路失效的影响|没影响，除了那些路由器崩溃期间丢失的包|穿过故障路由器的所有VC都将中断
服务质量|困难|容易，如果在预先建立每条VC时有足够的资源可分配
拥塞控制|困难|容易，如果在预先建立每条VC时有足够的资源可分配

路由算法

路由表：（地址，子网掩码，输出链路，下一跳）

• 如果子网内部使用数据报，则必须为每个到达的数据包重新做出此决定，因为自上次以来最佳路由可能已经更改
• 如果子网内部使用虚拟电路，则只有在建立新的虚拟电路时才做出路由决定。此后，数据包只遵循先前建立的路由(会话路由)。

路由算法的分类

• 非自适应算法（静态路由）
  • 不基于对当前流量和拓扑的测量或估计进行路由决策
  • 路由的选择是预先计算的，离线的，并在网络启动时下载到路由器上，之后路由表就不会变了
• 自适应算法
  • 主要根据拓扑的变化改变路由决策，通常也会反映流量的变化

最优化原则——无环

如果路由器J在从路由器I到路由器K的最优路径上，那么从J到K的最优路径也在同一条路径上

• 如果从J到K存在比r2更好的路径rx，则可以将其与r1连接以改进从I到K的路径
• 与我们的r1-r2是最优的说法相矛盾
  

汇集树

• 从所有源到目的地的最佳路由形成一个以目的地为根的树
• 不包含任何循环，因此每个数据包将在有限的跳数内传递
• 若有环存在，则路由器会对网络的拓扑有不一样的理解

最短路径算法

建立子网的加权有向图

• 节点表示路由器
• 圆弧表示通信线路

权重

• 跳数
• 地理距离(以公里为单位)
• 平均排队和传输延迟：按小时测试确定一些标准测试数据包
• 距离、带宽、平均流量、通信成本、平均队列长度、测量延迟等因素的函数

Dijkstra算法：查找给定一对路由器之间的最短路径
$O(n^{2})$，路由器不能太多，网络规模受到显示

泛洪算法

• 不需要网络信息
• 传入的数据包在每个链路上重新传输，除了传入链路
• 树状结构只会有一份到达，其他会有多份副本

问题

• 产生大量重复报文：如果不采取措施，重复报文的数量是无穷大的。

措施

• 每个报文的报头包含一个跳数计数器：
  每跳一跳，计数器递减
  当计数器为零时，丢弃该报文
  发送方初始化跳数为从源到目的的路径长度或子网直径
• 源在每个数据包中放置一个序列号（序号与源地址有关）：
  每个路由器记录每个源的最大序列，告诉哪些序列已经被看到。只flooding比当前序号更大的包，并更新记录
• 选择性洪水：
  每台路由器将接收到的数据项记录在数据中
  每个数据项包含一个版本号
  只有新的数据项会被淹没

距离矢量算法（自适应）

每台路由器维护一个表（目的地，距离，接口，下一跳）

• 到每个目的地的最短已知距离：距离可以是跳数，时延(毫秒)，…
• 使用哪条线

该表通过与邻居交换信息来更新

• 发送路由信息矢量给所有邻居(目的地，距离)
  • 周期(RIP路由信息协议:30秒)
  • 每当表发生变化时发送表格(触发更新)
  • 路由器只听邻居的信息
• 接收路由信息
  • 收到更好的路由时更新本表
  • 刷新已有路由
• 超时时删除路由表项(RIP 180秒)

计数到无穷大的问题

链路状态路由

每台路由器必须完成以下步骤

1. 发现它的邻居，了解他们的网络地址
   • HELLO数据包：
     • 广播网：广播一个特殊的HELLO数据包
     • 多址访问网络：向邻居单播HELLO数据包
   • 邻居返回一个回复，说明它是谁
     • 名称(路由id)必须是全局唯一的
   • 假节点：广播LAN为连接到其上的任何一对路由器提供了彼此的连通性。然而，把LAN建模成许多个点到点链路会增大拓扑结构，从而导致浪费消息。模拟局域网的一个更好方法来是把它看作一个节点
     
2. 为每个相邻节点设置距离或成本度量值(衡量每个相邻节点的延迟或成本)
   • 到邻居的成本可自动设置或由网络运营商配置的度量
   • 一种常用的选择是使成本与链路带宽成反比
3. 构造一个包含所有刚刚获知的链路信息包(LSP: Link-state packet链路状态数据包)
   • 何时建立LSP
     • 定期建立LSP
     • 在发生重大事件时建立LSP，如线路或邻居故障或恢复正常，或其属性发生明显变化等
4. 将这个包可靠地发送给所有其他的路由器(不只是邻居)，并接收来自所有其他路由器的信息包
   • 可靠性
     • 可靠的，有确认的分发LSP（收不到就重发）
     • 避免不同路由器使用不同版本的拓扑，导致不一致、环路、机器不可达等问题
   • 基本分发算法
     • 采用泛洪方式分发LSP
     • 防止router-router线路上的错误，所有LSP都要被确认
   • 关于LSP
     
     发送标志表明该数据包必须在所指示的线路上发送
     确认标志表明它必须在这条线路上得到确认
     
     • 序列号
       • 如果LSP是新的，则把它转发到除入境线路之外的所有其他线路上
       • 如果LSP是重复的，则将它丢弃(选择性洪泛)
       • 如果数据包的序号小于当前所看到过的来自该源路由器的最大序列号，则它将被当作过时数据包而拒绝接受，因为路由器已经有了更新的数据
       • 如果序号绕回，可能会产生混淆，的解决方案是使用一个32位的序号
       • 如果一个路由器崩溃了，那么它将丢失所有的序号记录表。如果它再从0开始， 那么，下一个数据包将被作为重复数据包而拒绝
       • 如果一个序号被破坏了，产生了差错，可能会被拒绝
     • 年龄：在每个数据包的序号之后包含一个年龄（age）字段， 并且每秒钟将年龄减1。当年龄字段的值被减到0时，来自路由器的该信息将被丢弃
       • 只有当一个路由器停机或路由器改变ID时，路由器信息才会超时
5. 计算到其他路由器的最短路径
   • 一旦路由器积累了一组完整的LSP，它就可以构建整个图
     • 每条链路被表示了两次，每个方向各表示一次，不同方向的链路可能有不同的成本
   • 在本地运行Dijkstra算法，以便构建出从本地出发到所有可能目标的最短路径
   • 该算法的结果可以安装在路由表中

相比距离矢量算法，链路状态路由算法需要更多的内存和计算。对于一个具有n个路由器的网络，每个路由器有k个邻居，那么，用于存储输入数据所要求的内存与kn成正比。

层次路由

考虑一个有720个路由器的子网：

• 无层次结构时
  • 720条路由表项
• 将子网划分为24个区域，每个区域包含30台路由器(总数为53)
  • 30条本地路由表项
  • 23条远端路由表项
• 如果选择三级层次结构，8个集群，每个集群包含9个区域，每个区域包含10台路由器(总数为25)
  • 10条本地路由表项
  • 8条到本集群内其他区域的路由表项
  • 7条远端路由表项

拥塞控制算法

拥塞控制（多点之间）：拥塞控制是一个全局问题
流量控制（两点之间）：流量控制是为了确保一个快速的发送方不能比接收方更快地持续传输数据

拥塞控制的方法：

• Network Provisioning网络扩容
• Traffic-aware routing流量敏感路由
• Admission Control许可证控制
• Traffic throtting调节流量
• Load shedding负载脱落

流量敏感路由

一般的路由方案：

• 采用固定的链路权值，可以适应拓扑的变化，但不能适应负载的变化

流量敏感路由：

• 将链路权值设置为链路带宽和传播延迟加上测量的负载或平均排队延迟的函数
• 危险：路由表可能会剧烈振荡，导致路由不稳定和许多潜在的问题
• 如果忽略负载，只考虑带宽和传播延迟，则不会出现这种问题
• 在Internet路由协议中，一般不会根据负载调整路由

许可证控制

广泛用于虚电路网络

• 除非网络能够承载新的流量且不会阻塞，否则不要建立新的虚拟电路
• 流量描述:根据其速率和形状(漏桶或令牌桶)进行描述
• 也可以结合流量敏感路由，将绕过流量热点的路由作为设置过程的一部分
  

负载脱落

当拥塞迫在眉睫时，网络必须告诉发送方放慢传输速度

• 路由器必须确定拥塞何时接近，最好是在拥塞到来之前
  • 输出链路的利用率
  • 路由器内部排队数据包的缓冲
  • 丢失的数据包数量
  • 指数加权移动平均(EWMA)

Qos

影响网络质量的因素包括传输链路的带宽、报文传送时延和抖动、以及丢包率等，它们也就成为了QoS的度量指标。

带宽
带宽也称为吞吐量，是指在一个固定的时间内（1秒），从网络一端传输到另一端的最大数据位数，也可以理解为网络的两个节点之间特定数据流的平均速率。带宽的单位是比特/秒（bit/s）。在网络中，有两个常见的与带宽有关的概念：上行速率和下行速率。上行速率是指用户向网络发送信息时的数据传输速率，下行速率是指网络向用户发送信息时的传输速率。

时延
时延是指一个报文或分组从网络的发送端到接收端所需要的延迟时间，一般由传输延迟及处理延迟组成。

抖动
抖动用来描述延迟变化的程度，也就是最大延迟与最小延迟的时间差。抖动对于实时性的传输是一个重要参数，特别是语音和视频等实时业务是极不容忍抖动的，抖动会造成话音或视频的断续。

丢包率
丢包率是指在网络传输过程中丢失报文的数量占传输报文总数的百分比。少量的丢包对业务的影响并不大。使用TCP传送数据可以处理少量的丢包，因为TCP允许丢失的信息重发。但大量的丢包会影响传输效率。

流量整形

流量整形是一种控制发送速率和数量的机制。通过流量整形能够调节数据传输速度减少拥塞。

有两种类型的流量整形算法：

• 漏桶算法
• 令牌桶

漏桶算法

假设我们有一个桶，我们希望以随机的速率向桶中倒水，并以恒定的速率从桶中取水。因此我们需要在桶底部打一个固定大小的洞，这样来保证水流处的速率是恒定的。由于桶的体积有限，因此倒满后就停止。

水流入的速率可以改变，但输出的速率是恒定的。这种平滑输出流量的方法称为漏桶技术。突发进入的流量存储在桶中，并以稳定的速率输出。

上图中，假设主机产生突发流量，速率是每秒12M，持续两秒。总共24M的数据。5秒后，又开始以每秒2M的速率发送数据，持续3秒，总共发了6M数据。最终经过了10秒，主机一共发了30M数据。通过漏桶最终可以平滑这些流量，以每秒3M的数据，持续10秒，平滑的输出这些数据。如果没有漏桶，最开始的突发流量可能会使系统因流量突增出现问题。

令牌桶算法

令牌桶算法的原理是系统会以一个恒定的速度往桶里放入令牌，而如果请求需要被处理，则需要先从桶里获取一个令牌，当桶里没有令牌可取时，则拒绝服务。

将网络接口想象成一个桶，正在往其中注水，水龙头的速率为R，水桶容量为B。桶内只能累积固定容量的令牌，即B，以均匀的速度来生产令牌。如果需要发送数据包，就从桶内申请令牌，如果桶内没有令牌，则必须等待更多的令牌到达才能发送数据包，或者直接被丢弃。

假设某个计算机的突发速率为M，那么令牌桶所允许的突发时间S的计算公式为：
B + RS = MS

分片

IPv4协议

基本概念

IPv4协议，网际协议版本4，一种无连接的协议，是互联网的核心，也是使用最广泛的网际协议版本，其后继版本为IPv6

internet协议执行两个基本功能

• 寻址(addressing)
• 分片(fragmentation)

IPv4数据报格式

• 版本： 4bit ，表示采用的IP协议版本
• 首部长度： 4bit，表示整个IP数据报首部的长度
• 区分服务： 8bit ，该字段一般情况下不使用
• 总长度： 16bit ，表示整个IP报文的长度,能表示的最大字节为2^16-1=65535字节
• 标识： 16bit ， IP软件通过计数器自动产生，每产生1个数据报计数器加1；在ip分片以后，用来标识同一片分片
• 标志： 3bit，目前只有两位有意义。
  MF，置1表示后面还有分片，置0表示这是数据报片的最后1个；
  DF，不能分片标志，置0时表示允许分片
• 片偏移： 13bit，表示IP分片后，相应的IP片在总的IP片的相对位置
• 生存时间TTL(Time To Live) ：8bit,表示数据报在网络中的生命周期，用通过路由器的数量来计量，即跳数（每经过一个路由器会减1）
• 协议：8bit，标识上层协议（TCP/UDP/ICMP…）
• 首部校验和：16bit ，对数据报首部进行校验，不包括数据部分
• 源地址：32bit，标识IP片的发送源IP地址
• 目的地址：32bit，标识IP片的目的地IP地址
• 选项：可扩充部分，具有可变长度，定义了安全性、严格源路由、松散源路由、记录路由、时间戳等选项
• 填充：用全0的填充字段补齐为4字节的整数倍

数据报分片

分片原因

数据报长度大于传输链路的MTU

MTU（Maximum Transmission Unit）, 最大传输单元

• 链路MTU
• 路径MTU (Path MTU)

分片策略

• 允许途中分片：根据下一跳链路的MTU实施分片
• 不允许途中分片：发出的数据报长度小于路径MTU（路径MTU发现机制）

重组策略

• 途中重组，实施难度太大
• 目的端重组（互联网采用的策略）
• 重组所需信息：原始数据报编号、分片偏移量、是否收集所有分片

IPv4分片策略

• IPv4分组在传输途中可以多次分片
  • 源端系统，中间路由器（可通过标志位设定是否允许路由器分片，DF标志位）
• IPv4分片只在目的IP对应的目的端系统进行重组
• IPv4分片、重组字段在基本IP头部
  • 标识、标志、片偏移

注：分组 (packet) 与 帧(frame)的关系

路由聚合

最长匹配原则

IP地址

NAT

NAT（Network Address Translator，网络地址转换）是用于在本地网络中使用私有地址，在连接互联网时转而使用全局 IP 地址的技术。NAT实际上是为解决IPv4地址短缺而开发的技术。

工作机制

如下图所示，以 10.0.0.10 的主机与 163.221.120.9 的主机进行通信为例讲解 NAT 的工作机制。利用 NAT，途中的 NAT 路由器将发送源地址从 10.0.0.10 转换为全局的 IP 地址（202.244.174.37）再发送数据。反之，当响应数据从 163.221.120.9 发送过来时，目标地址（202.244.174.37）先被转换成私有 IP 地址 10.0.0.10 以后再被转发。

• 网络被分为私网和公网两个部分，NAT网关设置在私网到公网的路由出口位置，双向流量必须都要经过NAT网关
• 网络访问只能先由私网侧发起，公网无法主动访问私网主机
• NAT 路由器在两个访问方向上完成两次地址的转换或翻译，出方向做源信息替换，入方向做目的信息替换；
• NAT 路由器的存在对通信双方是保持透明的；
• NAT 路由器为了实现双向翻译的功能，需要维护一张关联表，把会话的信息保存下来。

动态NAT表项：
在内部本地地址转换的时候，在地址池中选择一个空闲的，没有正在被使用的地址，来进行转换，一般选择的是在地址池定义中排在前面的地址，当数据传输或者访问完成时就会放回地址池中，以供内部本地的其他主机使用。如果这个地址正在被使用的时候，是不能被另外的主机拿来进行地址转换的。

静态NAT表项：

IPv6

• 版本（Version）：4 bit，值为 6（二进制值为 0110）表示 IPv6 报文。
• 流量类别（Traffic Class）：8 bit，这相当于 IPv4 协议中的 ToS 字段。但是，考虑到 ToS 字段这些年的发展，现在都用来做区分服务等级（Differentiated Class of Service，DiffServ）了。所以，即使这个字段和旧的 ToS 字段有些相似，它们的名字要比所传送的值更能确切地反映目前的用处。
• 流标签（Flow Label）：20 bit，IPv6 中新增。流标签可用来标记特定流的报文，以便在网络层区分不同的报文。转发路径上的路由器可以根据流标签来区分流并进行处理。由于流标签在 IPv6 报文头中携带，转发路由器可以不必根据报文内容来识别不同的流，目的节点也同样可以根据流标签识别流，同时由于流标签在报文头中，因此使用 IPSec 后仍然可以根据流标签进行 QoS 处理。
• 有效载荷长度（Payload Length）：16 bit，以字节为单位的 IPv6 载荷长度，也就是 IPv6 报文基本头以后部分的长度（包括所有扩展头部分）。IPv4 的总长度字段是 16 位的，但 IPv6 的有效载荷长度字段却是 20 位，这就意味着该字段能够指定更长的有效载荷（1 048 575 字节，相对 IPv4 中只有 65 535 字节）（本句源自《 TCP / IP 路由技术 》，有误）。
• 下一报头（Next Header）：8 bit，用来标识当前头（基本头或扩展头）后下一个头的类型。此域内定义的类型与 IPv4 中的协议域值相同。IPv6 定义的扩展头由基本头或扩展头中的扩展头域链接成一条链。这一机制下处理扩展头更高效，转发路由器只处理必须处理的选项头，提高了转发效率。
• 跳数限制（Hop Limit）：8 bit，和 IPv4 中的 TTL 字段类似。每个转发此报文的节点把此域减 1，如果此域值减到 0 则丢弃。注意：IPv4 中的 TTL 设计之初是以秒（s）为单位的，但实际使用时跟 IPv6 中的 Hop Limit 一样，是以跳数为单位。
• 源地址（Source Address）：128 bit，报文的源地址。
• 目的地址（Destination Address）：128 bit，报文的目的地址。

ICMP (Internet Control Message Protocol)

ICMP协议是一个网络层协议。
一个新搭建好的网络，往往需要先进行一个简单的测试，来验证网络是否畅通；但是IP协议并不提供可靠传输。如果丢包了，IP协议并不能通知传输层是否丢包以及丢包的原因。
所以我们就需要一种协议来完成这样的功能–ICMP协议。

ICMP的功能

1. 确认IP包是否成功到达目标地址
2. 通知在发送过程中IP包被丢弃的原因

如下图所示：

ICMP的报文格式

ICMP报文分两类，即ICMP差错报告报文和ICMP询问报文

ARP (Address Resolution Protocol)

ARP的功能和操作原理

ARP是用来将IP地址解析为MAC地址的协议。主机或三层网络设备上会维护一张ARP表，用于存储IP地址和MAC地址的映射关系，一般ARP表项包括动态ARP表项和静态ARP表项。

1. 主机A首先查看自己的ARP缓存表，确定其中是否包含有主机B对应的ARP表项。如果找到了对应的MAC地址，则主机A直接利用ARP表中的MAC地址，对IP数据包进行帧封装，并将数据包发送给主机B。
2. 如果主机A在ARP表中找不到对应的MAC地址，则将缓存该数据报文，然后以广播方式发送一个ARP请求报文。ARP请求报文中的发送端IP地址和发送端MAC地址为主机A的IP地址和MAC地址，目标IP地址和目标MAC地址为主机B的IP地址和全0的MAC地址。由于ARP请求报文以广播方式发送，该网段上的所有主机都可以接收到该请求，但只有被请求的主机（即主机B）会对该请求进行处理。
3. 主机B比较自己的IP地址和ARP请求报文中的目标IP地址，当两者相同时进行如下处理：将ARP请求报文中的发送端（即主机A）的IP地址和MAC地址存入自己的ARP表中。之后以单播方式发送ARP响应报文给主机A，其中包含了自己的MAC地址。
4. 主机A收到ARP响应报文后，将主机B的MAC地址加入到自己的ARP表中以用于后续报文的转发，同时将IP数据包进行封装后发送出去。

补充：将MAC地址解析为IP地址的协议为RARP

ARP的报文格式

代理ARP

代理ARP的原理就是当出现跨网段的ARP请求时，路由器将自己的MAC返回给发送ARP广播请求发送者，实现MAC地址代理（善意的欺骗），最终使得主机能够通信。

DHCP (Dynamic Host Configuration Protocol)

在DHCP的帮助下，可以动态地给网络上的任何设备或节点分配一个互联网协议IP地址，使它们可以使用这个IP进行通信。网络管理员的任务是将大量的IP地址手动分配给网络中的所有设备。然而，在DHCP中，这个任务是自动化的，是集中管理，而不是手工管理。无论是小型本地网络还是大型企业网络都实现了DHCP。DHCP的基本目标是为主机分配一个唯一的IP地址。

• DHCP Discover：由客户端发出，用来发现DHCP服务器。
• DHCP Offer：由DHCP服务器发出，告诉客户端，我可以提供IP地址。
• DHCP Request：由客户端发出，告诉对应的DHCP服务器，我需要IP地址。
• DHCP ACK：由DHCP服务器发出，提供客户端响应的IP地址。

DHCP Relay

DHCP Relay：DHCP中继（也叫做DHCP中继代理），其可以实现在不同子网和物理网段之间处理和转发DHCP信息的功能
如果DHCP客户端与DHCP服务器在同一个物理网段，则客户机可以正确地获得动态分配的IP地址。
如果不在同一个物理网段，则需要DHCP Relay（DHCP中继代理）

DHCP Relay原理

当DHCP Client启动并进行DHCP初始化时，它会在本地网络广播配置请求报文
如果本地网络存在DHCP Server，则可以直接进行DHCP配置，不需要DHCP Relay
如果本地网络没有DHCP Server，则与本地网络相连的具有DHCP Relay功能的网络设备收到该广播报文后，将进行适当处理并转发给指定的其它网络上的DHCP Server
DHCP Server根据DHCP Client提供的信息进行相应的配置，并通过DHCP Relay将配置信息发送给DHCP Client，完成对DHCP Client的动态配置

• 事实上，从开始到最终完成配置，需要多个这样的交互过程：
  • DHCP Relay设备修改DHCP消息中响应字段，把DHCP的广播包改成单播包，并负责在服务器与客户机直接转换
  • 三层交换机可以作为DHCP Relay代理

OSPF

内部网关协议
特点：拓扑结构发生变化后，可以快速地自动绕开有故障的路由器和线路，选择一个迂回路由

• 每个AS（自治系统）划分为若干个区域，每个区域都有一个4字节编号
• 因此每个AS都有一个唯一的骨干网，骨干网的编号为0，其他所有的区域都与之相连
• 在一个区域内部，每一个路由器都有完全相同的链路状态数据库，并使用相同的最短路由算法
• 连接两个区域的路由器必须有两套链路状态数据库

BGP

外部网关协议