4 网络层

4.1 网络层服务

网络层：从发送主机向接收主机传送数据段（segment），发送主机将数据段封装到数据报（datagram）中；接收主机向传输层交付数据段（segment）。每个主机和路由器都运行网络层协议（非端到端的），路由器检验所有穿越它的IP数据报的头部域，以决策如何处理IP数据报。

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

• 转发(forwarding)：将分组从路由器的输入端口转移到合适的输出端口
  • 转发表确定在本路由器如何转发分组
• 路由(routing)：确定分组从源到目的经过的路径
  • 路由算法(协议)（routing algorithms）确定通过网络的端到端路径

某些网络（如ATM, 帧中继, X.25）的重要功能：连接建立——数据分组传输之前两端主机需要首先建立虚拟/逻辑连接。网络设备（如路由器）参与连接的建立。

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

• 网络层连接：两个主机之间 (路径上的路由器等网络设备参与其中)

• 传输层连接：两个应用进程之间（对中间网络设备透明）

无连接服务(connection-less service)：如数据报网络(datagram network)

• 不事先为系列分组的传输确定传输路径

• 每个分组独立确定传输路径

• 不同分组可能传输路径不同

连接服务(connection service)：如虚电路网络(virtual-circuit network)

• 首先为系列分组的传输确定从源到目的经过的路径 (建立连接)

• 然后沿该路径（连接）传输系列分组，系列分组传输路径相同

• 传输结束后拆除连接

数据报网络与虚电路网络是典型两类分组交换网络

类似于传输层的无连接服务（UDP）和面向连接服务（TCP），但是网络层服务既有主机到主机的服务，也有网络核心的实现

4.2 虚电路网络

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

• 分组交换

• 每个分组的传输利用链路的全部带宽（实际的电路交换利用的是链路的部分资源，频率或时隙等）

• 源到目的路径经过的网络层设备共同完成虚电路功能

通信过程：呼叫建立(call setup)→数据传输→拆除呼叫

• 1.初始呼叫 –> 2. 呼叫到达 –> 3.接受呼叫 –> 4.呼叫建立 –> 5.数据流开始 –> 6.接收数据

每条虚电路包括：

1. 从源主机到目的主机的一条路径
2. 虚电路号 (VCID)， 沿路每段链路一个编号
3. 沿路每个网络层设备（如路由器），利用转发表记录经过的每条虚电路
   • 沿某条虚电路传输的分组，携带对应虚电路的VCID，而不是目的地址。因为同一条VC ，在每段链路上的VCID通常不同。路由器转发分组时依据转发表改写/替换虚电路号。

虚电路经过的每个网络设备（如路由器），维护每条经过它的虚电路连接状态

链路、网络设备资源(如带宽、缓存等)可以面向VC进行预分配

虚电路信令协议(signaling protocols)：用于VC的建立、维护与拆除 (路径选择)；应用于虚电路网络，如ATM、帧中继 (frame-relay) 网络等；目前的Internet不采用

4.3 数据报网络

数据报网络是网络层无连接的，所以每个分组携带目的地址，路由器根据分组的目的地址转发分组。

路由器基于路由协议/算法构建转发表，检索转发表转发数据报，而转发表更新导致了每个分组独立选路。

转发表确定在本路由器如何转发分组，所以对于Internet网络来说，路由器就需要保存40多亿IP地址，显然检索效率会大大降低，所以它维护的是一个地址范围(聚合转发表入口)。如：

最长前缀匹配优先：在检索转发表时，优先选择与分组目的地址匹配前缀最长的入口（entry）。

数据报网络与VC网络对比：

4.4 IP协议

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

• 路由协议进行路径选择，生成路由表

• IP协议做出了寻址规约(conventions)，定义了数据报(分组)格式以及分组处理规约

• ICMP(互联网控制报文)协议提供差错报告、路由器“信令”

ICMP协议相当于IP协议的伴随协议，实现IP协议的同时一般也要实现ICMP协议

4.4.1 IP数据报

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

<table>
    <tr>
        <td>0</td><td/><td/><td/>
        <td>4</td><td/><td/><td/>
        <td>8</td><td/><td/><td/>
        <td>12</td><td/><td/><td/>
        <td>16</td><td/><td/><td/>
        <td>20</td><td/><td/><td/>
        <td>24</td><td/><td/><td>31</td>
    </tr>
    <tr>
        <td colspan="4"><b>版本号</b>：<br/>4→IPv4<br/>6 → IPv6</td>
        <td colspan="4"><b>首部长度</b>：IP分组首部长度，以4字节为单位</td>
        <td colspan="8"><b>服务类型(TOS)</b>：<br/>指示期望获得哪种类型的服务，只有在网络提供区分服务时使用，一般情况下不使用，Internet不提供区分服务，所以通常IP分组里该值为00H</td>
        <td colspan="16"><b>总长度</b>：<br/>IP分组的总字节数(首部+数据)<br/>最大65535B，最小20B</td>
    </tr>
    <tr>
        <td colspan="16" rowspan="2"><b>标识</b>：IP协议利用一个计数器，每产生IP分组计数器加1，作为该IP分组的标识</td>
        <td colspan="3"><b>标志位</b>：<br/>DF(Don'tFragment)为1禁止分片；为0允许分片;<br/>MF(MoreFragment)为1非最后一片；为0最后一片(或未分片)</td>
        <td colspan="12" rowspan="2"><b>片偏移</b>：<br/>一个IP分组分片封装原IP分组数据的
相对偏移量，片偏移字段以8字节为单位</td>
    </tr>
    <tr>
        <td>保留</td>
        <td>DF</td>
        <td>MF</td>
    </tr>
    <tr>
        <td colspan="8"><b>生存时间(TTL)</b>：<br/>IP分组在网络中可以通过的路由器数(跳步数)，路由器转发一次分组，TTL减1；如果TTL=0，路由器则丢弃该IP分组并向源主机发送一个ICMP数据包</td>
        <td colspan="8"><b>协议</b>：<br/>指示IP分组封装的是哪个协议的数据包，它实现复用/分解<br/>6为TCP，表示封装的为TCP段；17为UDP，表示封装的是UDP数据报</td>
        <td colspan="16"><b>首部检验和</b>：<br/>实现对IP分组首部的差错检测。计算校验和时，该字段置全0；采用反码算数运算求和，和的反码作为首部校验和字段；逐跳计算、逐跳校验</td>
    </tr>
    <tr align="center">
        <td colspan="32"><b>源IP地址</b>：标识发送分组的源主机/路由器(网络接口)的IP地址</td>
    </tr>
    <tr align="center">
        <td colspan="32"><b>目的IP地址</b>：标识接收分组的目的主机/路由器(网络接口)的IP地址</td>
    </tr>
    <tr align="center">
        <td colspan="24"><b>选项字段</b>：长度可变，范围在1~40B之间：携带安全、源选路径、时间戳和路由记录等内容，但实际上很少被使用</td>
        <td colspan="8"><b>填充</b>：范围在0~3B之间：补齐整个首部，符合32位对齐，即保证首部长度是4字节的倍数</td>
    </tr>
    <tr align="center">
        <td colspan="32">数据</td>
    </tr>
</table>

4.4.2 IP分片

最大传输单元(MTU)：链路层数据帧可封装数据的上限。不同链路的MTU不同，所以就导致一个分组在一条链路上可以传输，但在下一条链路上传输可能需要被拆分。

1个IP分组分为多片IP分组，IP分片到达目的主机后进“重组”(reassembled)

IP首部的相关字段用于标识分片以及确定分片的相对顺序：总长度、标识、标志位和片偏移

分片过程：假设原IP分组总长度为L，待转发链路的MTU为M。若L>M，且DF=0，则可以/需要分片。通常分片时，每个分片的标识复制原IP分组的标识，除最后一个分片，其他分片均分为MTU允许的最大分片。

一个最大分片可封装的数据应该是8的倍数，因此，一个最大分片可封装的数据为：$\displaystyle d=\lfloor\frac {M-20} 8\rfloor\times 8$

需要的总片数为：$\displaystyle n=\lceil\frac {L-20} d \rceil$

每片的片偏移字段取值为：$\displaystyle F_i=\frac d 8 \times (i-1),\; 1\le i\le n$

每片的总长度字段为：$L_i=\begin{cases} d+20 & 1\le i\le n \\ L-(n-1)d & i=n \end{cases}$

每片的MF标志位为：$MF_i=\begin{cases}1&1\le i\lt n \\ 0 & i=n\end{cases}$

4.4.3 IP编址

接口(interface)：主机/路由器与物理链路的连接。它实现网络层功能。

IP地址：32比特(IPv4)编号标识主机、路由器的接口。IP地址与每个接口关联，由于一个主机通常只有一个接口，所以通常也叫主机地址而不是接口地址。

路由器通常有多个接口，而主机通常只有一个或两个接口 (e.g.，有线的以太网接口，无线的802.11接口)

将IP地址的高位比特称为网络号(NetID)，低位比特称为**主机号(HostID) **。

IP子网：IP地址具有相同网络号的设备接口，不跨越路由器（第三及以上层网络设备）可以彼此物理联通的接口。

4.4.4 有类IP地址

“有类”编址：

• A类地址 (50%)：NetID(8位) HostID(24位)，最高位为0

  0.0.0.0~127.255.255.255

• B类地址 (25%)：NetID(16位) HostID(16位)，最高两位为10

  128.0.0.0~191.255.255.255

• C类地址 (12.5%)：NetID(24位) HostID(8位)，最高三位为110

  192.0.0.0~223.255.255.255

• D类地址 (6.25%)：32位HostID，最高四位为1110

  224.0.0.0~239.255.255.255

• E类地址 (6.25%)：32位HostID，最高四位为1111

  240.0.0.0~255.255.255.255

D类地址不再区分网络号和主机号，用于标识互联网中的一组主机，这些主机理论上可以分布在互联网的每个地方。只能作为目的地址，称为多播地址。

E类地址保留，作为研究使用。

4.4.4.1 特殊IP地址

4.4.4.2 私有IP地址

4.4.5 IP子网划分与子网掩码

子网划分：ABC类IP子网还是过大，继续划分一个IP子网为更小范围网络。

IP地址：高位比特为网络号(NetID) ；原网络主机号部分高位比特为子网号(SubID)；低位比特为主机号(HostID)。

子网掩码：形如IP地址，也是32位，写成点分十进制形式。取值：NetID、SubID位全取1，HostID位全取0

• A网的默认子网掩码为：255.0.0.0

• B网的默认子网掩码为：255.255.0.0

• C网的默认子网掩码为：255.255.255.0

• 借用3比特划分子网的B网的子网掩码为：255.255.224.0

利用子网地址+子网掩码准确确定子网大小，将IP分组的目的IP地址与子网掩码按位与运算，提取子网地址。

例：目的IP地址：172.32.1.112，子网掩码：255.255.254.0

172.32.1.112 = 10101100 00100000 00000001 01110000

255.255.254.0= 11111111 11111111 11111110 00000000

位与运算：10101100 00100000 00000000 00000000 = 172.32.0.0

• 子网地址：172.32.0.0(子网掩码：255.255.254.0)
• 地址范围：172.32.0.0~172.32.1.255
• 可分配地址范围：172.32.0.1~172.32.1.254
• 广播地址：172.32.1.255

子网的划分会导致一些损失，因为使得每个子网的开头(子网地址)和末尾(广播地址)的地址不能分配给路由器或主机使用，但带来了性能的提升。

4.4.6 CIDR与路由聚集

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

• 消除传统的 A 类、B 类和 C 类地址界限：NetID+SubID→Network Prefix (Prefix)可以任意长度。

• 融合子网地址与子网掩码，方便子网划分：无类地址格式：a.b.c.d/x，其中x为前缀长度

  例如：子网201.2.3.64，255.255.255.192 → 201.2.3 .64/26

• 提高IPv4 地址空间分配效率
• 提高路由效率： 将多个子网聚合为一个较大的子网，构造超网(supernetting)；路由聚合(route aggregation)

选用更具体的路由：最长前缀匹配优先！路由聚合以后，如果聚合后的子网缺少了一部分，则在路由器的路由表中一定会有多条路由表项，于是在路由的时候就需要最长前缀匹配优先。

4.5 DHCP协议

动态主机配置协议(DHCP：Dynamic Host Configuration Protocol)：

• 从服务器动态获取：IP地址、子网掩码、默认网关地址、DNS服务器名称与IP地址

• “即插即用”

• 允许地址重用

• 支持在用地址续租

• 支持移动用户加入网络

DHCP工作过程：

• 主机广播“DHCP discover”(发现报文)
• DHCP服务器利用“DHCP offer” (提供报文) 进行响应
• 主机请求IP地址：“DHCP request” (请求报文)
• DHCP服务器分配IP地址：“DHCP ack” (确认报文)

DHCP协议在应用层实现：请求报文封装到UDP数据报中 –> IP广播 –> 链路层广播(e.g. 以太网广播)

DHCP服务器构造ACK报文：包括分配给客户的IP地址、子网掩码、默认网关、DNS服务器地址

4.6 NAT

设计动机：

• 只需从ISP申请一个IP地址：由于IPv4地址耗尽
• 本地网络设备IP地址的变更，无需通告外界网络
• 变更ISP时，无需修改内部网络设备IP地址
• 内部网络设备对外界网络不可见，即不可直接寻址(安全)

实现：

1. 替换：利用(NAT IP地址,新端口号)替换每个外出IP数据报的(源IP地址,源端口号)
2. 记录：将每对(NAT IP地址, 新端口号)与(源IP地址, 源端口号)的替换信息存储到NAT转换表中
3. 替换：根据NAT转换表，利用(源IP地址, 源端口号)替换每个进入内网IP数据报的(目的IP地址,目的端口号)，即(NAT IP地址, 新端口号)

NAT存在的争议：

• 路由器应该只处理第3层功能，但NAT更改了第四层的数据。
• 违背端到端通信原则：传输层是端到端的，即对第三层设备路由器等应该是透明的，应用开发者必须考虑到NAT的存在，e.g., P2P应用
• 地址短缺问题应该由IPv6来解决

NAT穿透的解决方案：

1. 静态配置NAT，将特定端口的连接请求转发给服务器。
   • 例如(138.76.29.7, 2500)总是转发给(10.0.0.1, 25000)
2. 利用UPnP(Universal Plug and Play)互联网网关设备协议 (IGD-Internet Gateway Device )自动配置。
   • 学习到NAT公共IP地址(138.76.29.7)，然后在NAT转换表中，(自动)增删端口映射
3. 中继(如Skype)。NAT内部的客户与中继服务器建立连接；外部客户也与中继服务器建立连接；中继服务器桥接两个连接的分组。

4.7 ICMP

互联网控制报文协议 ICMP (Internet Control Message Protocol)支持主机或路由器完成差错(或异常)报告和网络探询。

4.7.1 ICMP报文

• 差错报告报文 (5种)
  • 目的不可达：无法到达目的或已到达但无法交付给目的
  • 源抑制(Source Quench)：用于网络层的拥塞控制，路由器发现缓存已满时构造此类报文发给源主机，但目前的Internet中并无此类拥塞控制
  • 超时/超期：TTL超时后，路由器丢弃报文并构造此类报文发给源主机
  • 参数问题：报文头部某些字段头问题
  • 重定向 (Redirect)：在路由器看来此报文不应由自己来转发，而应由其他路由器转发
• 网络探询报文
  • 回声(Echo)请求与应答报文(Reply)：探测网络是否可达
  • 时间戳请求与应答报文：获取时间戳

几种 ICMP 报文已不再使用：信息请求与应答报文；子网掩码请求和应答报文；路由器询问和通告报文

几种不发送 ICMP差错报告报文的特殊情况：

• 对ICMP差错报告报文不再发送 ICMP差错报告报文

• 除第1个IP数据报分片外，对所有后续分片均不发送ICMP差错报告报文

• 对所有多播IP数据报均不发送 ICMP差错报告报文

• 对具有特殊地址（如127.0.0.0 或 0.0.0.0）的IP数据报不发送ICMP 差错报告报文

4.7.2 ICMP报文格式

ICMP报文封装到IP数据报中传输

ICMP差错报告报文数据封装

• IP数据报的数据字段是UDP数据报时，前8个字节就是整个UDP头
• IP数据报的数据字段是TCP数据报时，前8个字节包含了源地址、源端口号，目的地址、目的端口号等重要信息

4.7.3 ICMP的应用：Traceroute

探测路径上的所有路由器：

1. 源主机向目的主机发送一系列UDP数据报：第1组IP数据报TTL =1，第2组IP数据报TTL=2, …。要保证目的端口号为不可能使用的端口号。

2. 这样当第n组数据报(TTL=n)到达第n个路由器时：路由器丢弃数据报，向源主机发送携带路由器名称和IP地址信息的ICMP报文(type=11, code=0)。当ICMP报文返回到源主机时，记录RTT

3. 停止准则：UDP数据报最终到达目的主机，目的主机返回“目的端口不可达”ICMP报文 (type=3,code=3)，此时源主机停止。

4.8 IPv6

最初动机：32位IPv4地址空间已分配殆尽

其他动机：改进首部格式——支持快速处理/转发数据报；支持QoS

4.8.1 IPv6数据报格式

固定长度的40字节基本首部

不允许分片：只能由源主机分，目的主机组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

<table>
    <tr>
        <td>0</td><td/><td/><td/>
        <td>4</td><td/><td/><td/>
        <td>8</td><td/><td/><td/>
        <td>12</td><td/><td/><td/>
        <td>16</td><td/><td/><td/>
        <td>20</td><td/><td/><td/>
        <td>24</td><td/><td/><td>31</td>
    </tr>
    <tr>
        <td colspan="4"><b>版本号</b></td>
        <td colspan="8"><b>优先级(priority)</b>：标识数据报的优先级</td>
        <td colspan="20"><b>流标签(flow Label)</b>: 标识同一“流”中的数据报</td>
    </tr>
    <tr>
        <td colspan="16"  align="center"><b>载荷长度</b>：最大64KB</td>
        <td colspan="8"><b>下一个首部</b>：标识下一个选项首部或上层协议首部(如TCP首部)。如果有扩展首部则指向扩展首部位置，同时每个扩展首部的此字段指向下个扩展首部，最后一个扩展首部指向上层协议首部</td>
        <td colspan="8"><b>跳步限制</b>: 对应于TTL</td>
    </tr>
    <tr align="center">
        <td colspan="32"><b>源IP地址</b>(128位)</td>
    </tr>
    <tr align="center">
        <td colspan="32"><b>目的IP地址</b>(128位)</td>
    </tr>
    <tr align="center">
        <td colspan="32">载荷（扩展首部+数据）</td>
    </tr>
</table>

与IPv4相比的变化：

• 校验和(checksum)：彻底移除，以减少每跳处理时间
• 选项(options)：允许，但是从基本首部移出，定义多个选项首部，通过“下一个首部”字段指示
• ICMPv6：新版ICMP
  • 附加报文类型，e.g. “Packet Too Big”——分组过大直接丢弃，发送此报文
  • 多播组管理功能

4.8.2 IPv6地址

IPv6地址表示形式

• 一般形式：1080:0:FF:0:8:800:200C:417A

• 压缩形式：FF01:0:0:0:0:0:0:43，压缩→FF01::43

• IPv4-嵌入形式：0:0:0:0:0:FFFF:13.1.68.3 或 ::FFFF:13.1.68.3

• 地址前缀：2002:43c:476b::/48

  IPv6不再使用掩码，统一使用CIDR

• URLs：http://[3FFE::1:800:200C:417A]:8000

IPv6基本地址类型

• 单播(unicast)：一对一通信

• 多播(multicast)：一对多通信

• 任意播(anycast)：一对一组之一（最近一个）通信

没有广播地址，定义为一个特殊的多播地址。

不可能在某个时刻所有路由器同时被更新为IPv6，所以IPv4和IPv6路由器共存，使用隧道协议使其共存。

隧道(tunneling)：IPv6数据报作为IPv4数据报的载荷进行封装，穿越IPv4网络

4.9 路由算法

网络抽象：图G = (N, E)，N = 路由器集合，E = 链路集合

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

图的抽象在网络领域应用很广泛 e.g.:P2P，其中，N是 peers集合，而E是TCP连接集合

关键问题：源到目的（如u到z）的最小费用路径是什么？

路由算法：寻找最小费用路径的算法

路由算法分类

• 静态路由：手工配置；路由更新慢；优先级高

• 动态路由：路由更新快；定期更新；及时响应链路费用或网络拓扑变化

• 全局信息：所有路由器掌握完整的网络拓扑和链路费用信息。e.g. 链路状态(LS)路由算法

• 分散(decentralized)信息：路由器只掌握物理相连的邻居以及链路费用，邻居间信息交换、运算的迭代过程。e.g. 距离向量(DV)路由算法

4.9.1 链路状态路由算法

Dijkstra 算法

• 所有结点(路由器)掌握网络拓扑和链路费用：通过“链路状态广播”；所有结点拥有相同信息

• 计算从一个结点(“源”)到达所有其他结点的最短路径：获得该结点的转发表

• 迭代：k次迭代后，得到到达k个目的结点的最短路径

c(x,y)：结点x到结点y链路费用；如果x和y不直接相连，则=∞

D(v)：从源到目的v的当前路径费用值

p(v)：沿从源到v的当前路径，v的前序结点

N’：已经找到最小费用路径的结点集合

1
2
3
4
5
6
7
8
9
10
11
12
13
14

初始化:
N' = {u}
for 所有结点v
	if v毗邻u
		then D(v) = c(u,v)
	else D(v) = ∞

Loop
	找出不在 N’中的w ，满足D(w)最小
	将w加入N'
	更新w的所有不在N’中的邻居v的D(v) :
 		D(v) = min( D(v), D(w) + c(w,v) )
	 /*到达v的新费用或者是原先到达v的费用，或者是已知的到达w的最短路径费用加上w到v的费用 */
until 所有结点在N’中

算法存在震荡(oscillations)可能：假设链路费用是该链路承载的通信量。初始为图1，此时会认为图2的代价更小，更新路由表为图2，又认为图3的代价更小，更新路由表为图3，又认为图2的代价更小，如此往复。如果一个B发往A的数据报恰好遇上了每次更新路由表，那么它将一直在B和B和D之间转发，直到TTL耗尽。

4.9.2 距离向量路由算法

核心：Bellman-Ford方程(动态规划)

令d~x~(y)=从x到y最短路径的费用（距离），则d~x~(y) = min~v~ {c(x,v) + d~v~(y) }

x到邻居v的费用 + 从邻居v到达目的y的费用（距离），在x的所有邻居v中取最小值

重点：结点获得最短路径的下一跳, 该信息用于转发表中

由于从结点x到结点y的最小费用未知，则需要对其估计，D~x~(y) = 从结点x到结点y的最小费用估计。x维护距离向量(DV)：D~x~ = [D~x~(y): y є N ]

结点x已知到达每个邻居的费用为c(x,v)，就能维护其所有邻居的距离向量：D~v~ = [D~v~(y): y є N ]

核心思想：每个结点不定时地将其自身的DV估计发送给其邻居，当x接收到邻居的新的DV估计时，即依据B-F更新其自身的距离向量估计：D~x~(y) ← min~v~{c(x,v) + D~v~(y)} for each node y ∊ N。D~x~(y)将最终收敛于实际的最小费用 d~x~(y)。

距离向量路由算法的特点：

• 异步迭代：引发每次局部迭代的因素：局部链路费用改变或来自邻居的DV更新。

• 分布式：每个结点只当DV变化时才通告给邻居，邻居在必要时（其DV更新后发生改变）再通告它们的邻居。

好消息(链路费用降低)传播快，坏消息(链路费用增大)传播慢——无穷计数问题

消除无穷计数问题：

• 毒性逆转(poisoned reverse)：如果一个结点到达某目的的最小费用路径是通过某个邻居，则通告给该邻居结点到达该目的的距离为无穷大
• 定义最大度量(maximum metric)：定义一个最大的有效费用值，如15跳步，16跳步表示∞

4.8.3 层次路由

将任意规模网络抽象为一个图计算路由过于理想化，标识所有路由器，将整个网络抽象成一个“扁平”网络在实际网络（尤其是大规模网络）中不可行：

• 网络规模：考虑6亿目的结点的网络：路由表几乎无法存储，路由计算过程的信息（e.g. 链路状态分组、DV）交换量巨大，会淹没链路。

• 管理自治：每个网络的管理可能都期望自主控制其网内的路由；互联网(internet) = 网络之网络(network of networks)

为此提出了层次路由。

聚合路由器为一个区域——自治系统AS(autonomous systems)：同一AS内的路由器运行相同的路由协议(算法)

• 自治系统内部路由协议(“intra-AS” routing protocol)：只知道自己系统内的网络拓扑结构。

• 不同自治系统内的路由器可以运行不同的AS内部路由协议

网关路由器(gateway router)：在不同AS之间路由，位于AS“边缘”；通过链路连接其他AS的网关路由器

自治系统间(Inter-AS)路由任务：

• 确定路由器应该将该数据报转发给哪个网关路由器：网关路由器必须学习到哪些目的网络可以通过那个邻网到达，并将这些网络可达性信息传播给本网络内部路由器。
• 到达某网络有多条路径，需要去确定在多AS间选择。策略：热土豆路由：将分组发送给最近的网关路由器.

4.8.4 Internet路由

Internet采用层次路由

AS内部路由协议也称为内部网络协议IGP(interior gateway protocols)，最常见的AS内部路由协议：

• 路由信息协议：RIP(Routing Information Protocol)

• 开放最短路径优先：OSPF(Open Shortest Path First)

• 内部网关路由协议：IGRP(Interior Gateway Routing Protocol)：Cisco私有协议

4.8.4.1 RIP

基于距离向量路由算法：

• 距离度量：跳步数 (max = 15 hops)，每条链路1个跳步

• 每隔30秒，邻居之间交换一次DV，成为通告(advertisement)

• 每次通告：最多25个目的子网(IP地址形式)

链路失效、恢复：如果180秒没有收到通告则推断邻居/链路失效，经过该邻居的路由不可用，重新计算路由；向邻居发送新的通告；邻居再依次向外发送通告（如果转发表改变）；可能发生无穷计数问题 (定义最大度量技术)；毒性逆转技术用于预防乒乓(ping-pong)环路(另外：无穷大距离 = 16 hops)

适用于小规模的自治系统，超过15跳的系统RIP不再适用。

RIP路由表是利用一个称作route-d (daemon)的应用层进程进行管理，告报文周期性地通过UDP数据报发送。

4.8.4.2 OSPF

OSPF (Open Shortest Path First) “开放”：公众可用，非私有。

采用链路状态路由算法

• LS分组扩散（通告）
• 每个路由器构造完整的网络(AS)拓扑图
• 利用Dijkstra算法计算路由
• OSPF通告中每个入口对应一个邻居
• OSPF通告在整个AS范围泛洪，OSPF报文直接封装到IP数据报中

与OSPF极其相似的一个路由协议：IS-IS路由协议

OSPF优点：

• 安全(security)：所有OSPF报文可以被认证(预防恶意入侵)
• 允许使用多条相同费用的路径 (RIP只能选一条)：负载均衡
• 对于每条链路，可以针对不同的TOS设置多个不同的费用度量 (e.g., 卫星链路可以针对“尽力”(best effort) ToS设置“低”费用；针对实时ToS设置“高”费用)：实现不同类型数据的分流
• 集成单播路由与多播路由：多播OSPF协议(MOSPF) 与OSPF利用相同的网络拓扑数据
• OSPF支持对大规模AS分层(hierarchical)

分层的OSPF：两级分层

• 局部区(Area)，主干区(Backbone)
  • 链路状态通告只限于区内
  • 每个路由器掌握所在区的详细拓扑
  • 只知道去往其他区网络的“方向” (最短路径)
• 区边界路由器(Area Border Routers)：“汇总”到达所在区网络的距离，通告给其他区边界路由器。
• 主干路由器(Backbone Routers)：在主干区内运行OSPF路由算法。
• AS边界路由器(AS boundary routers)：连接其他AS。

4.8.4.3 BGP

Internet AS间路由协议：边界网关协议BGP (Border Gateway Protocol)，事实上的标准域间路由协议，将Internet “粘合”为一个整体的关键。

BGP为每个AS提供了一种手段：

• eBGP：从邻居AS获取子网可达性信息.

• iBGP：向所有AS内部路由器传播子网可达性信息.
• 基于可达性信息与策略，确定到达其他网络的 “好”路径

容许子网向Internet其余部分通告它的存在。

BGP会话(session)：两个BGP路由器 (“Peers”)交换BGP报文：实现通告去往不同目的前缀（prefix）的路径 **(路径向量(path vector)协议)。报文交换基于半永久的TCP**连接。

BGP报文：

• OPEN：与peer建立TCP连接，并认证发送方
• UPDATE：通告新路径 (或撤销原路径)
• KEEPALIVE：在无UPDATE时，保活连接；也用于对OPEN请求的确认
• NOTIFICATION：报告先前报文的差错；也被用于关闭连接

当AS3通告一个前缀给AS1时：AS3承诺可以将数据报转发给该子网；AS3在通告中会聚合网络前缀。

路径属性与BGP路由：通告的前缀信息包括BGP属性：前缀+属性= “路由”

两个重要属性：

• AS-PATH(AS路径)：包含前缀通告所经过的AS序列。e.g., AS 67,AS 17

• NEXT-HOP(下一跳)：开始一个AS-PATH的路由器接口，指向下一跳AS。

  可能从当前AS到下一跳AS存在多条链路

BGP路由选择，基于策略(policy-based) 路由：网关路由器收到路由通告后，利用其输入策略(import policy)决策接受/拒绝该路由。e.g., 从不将流量路由到AS x。

路由器可能获知到达某目的AS的多条路由，基于以下准则选择：

1. 本地偏好(preference)值属性：策略决策(policydecision)
2. 最短AS-PATH
3. 最近NEXT-HOP路由器：热土豆路由(hot potato routing)
4. 附加准则

• A,B,C是提供商网络/AS(provider network/AS)

• X,W,Y是客户网络(customer network/AS)

• W,Y是桩网络(stub network/AS)：只与一个其他AS相连
• X是双宿网络(dual-homed network/AS)：连接两个其他AS X不期望经过他路由B到C的流量，因此，X不会向B通告任何一条到达C的路由
• A向B通告一条路径：AW
• B向X通告路径：BAW
• B不应该向C通告路径BAW，因为B路由CBAW的流量没有任何“收益”，因为W和C均不是B的客户。B期望强制C通过A向W路由流量；期望只路由去往/来自其客户的流量！

采用不同的AS内与AS间路由协议的原因：

• 策略(policy)：
  • inter-AS：期望能够管理控制流量如何被路由，谁路由经过其网络等.
  • intra-AS：单一管理，无需策略决策
• 规模(scale)：
  • 层次路由节省路由表大小，减少路由更新流量
  • 适应大规模互联网
• 性能(performance)：
  • intra-AS：侧重性能
  • inter-AS：策略主导