网络层关注的是如何将源端数据包一路送到接收方

为了将数据包送到接收方，可能沿途要经过许多跳（hop）中间路由器

数据链路层只是将帧从线路一边传送到另一边

网络层是处理端到端数据传输的最底层

为了实现这个目标，网络层必须知道网络拓扑结构（即所有路由器和链路的集合），并从中选择适当的路径。同时，网络层还必修仔细选择路由器。避免某些通信线路和路由器负载过重，而其他线路和路由器空闲。最后，当源端和接收方位于不同网络时，网络层还需要再解决些问题

OSI 参考模型

通信子网

网络层设计问题

存储-转发数据包交换

机制

如果一台主机要发送一个数据包，它就将数据包传输给最近的路由器，路由器可能在它自己的 LAN 上，也可能在一条通向 ISP 的点到点链路上
在该数据包到达路由器，并且路由器的链路层完成了对它校验和的验证之后，它先被存储在路由器上
然后沿着路径被转发到下一个路由器，直至到达目标主机

注意

网络层负责将数据包从源端路由到目的地
路由算法是决定数据包接下来去哪里的软件的一部分（例如，哪个输出线路，广播信道上的哪个节点）
对于无线网络，路由决策是针对每个数据报进行的。对于面向连接的网络，路由决策在电路建立时设置一次

提供给传输层的服务

网络层通过网络层/传输层接口向传输层提供服务

网络层服务的目标

向上提供的服务应该独立于路由器技术
应该向传输层屏蔽路由器的数量、类型和拓扑关系
传输层可用的网络地址应该有一个统一编址方案，甚至可以跨越 LAN 和 WAN

问题

网络层应该提供面向连接的服务还是无连接的服务
错误 / 流量控制是网络层还是传输层的事？

Internet 社团

路由器的任务仅仅是传送数据包
网络（子网）从本质上讲总是不可靠的
主机需要自己来完成错误控制（错误检测和纠正）和流量控制任务
网络层再做一遍不会带来更大的好处
- 端-端论点，每个数据包必须携带完整的目标地址，因为每个数据包的运送独立于它前面的那些数据包（如果有的话）
TCP/IP 互联网在实现时是无连接的，但为用户提供连接

电话公司

面向连接的方法是正确的
用户不需要主机中的错误/流量控制协议
用户需要可靠、无故障的服务
服务质量是主要因素

无连接服务的实现

如果提供的是无连接的服务，那么所有的数据包都被独立地注入到网络中，并且每个数据包独立路由，不需要提前建立任何设置

数据包通常称为数据报（datagram），对应的网络称为数据报网络

如果使用了面向连接的服务，那么在发送数据包之前，必须首先建立起一条从源路由器到目标路由器之间的路径

这个连接称为虚电路（VC, virtuall circuit），对应的网络称为虚电路网络

每一台路由器都有一个内部表，指明了针对每一个可能的目标地址应该将数据包发送到哪里
每个表项由两部分组成：目标地址、通往目标地址所用的出境线路（直连线路）

管理这些路由表并做出路由选择的算法称为路由算法（routing algorithm）

IP 协议（Internet Protocol）是整个Internet的基础，它是无连接网络服务的重要范例

每个数据包携带一个目标 IP 地址，路由器使用该地址来单独转发每一个数据包
IPv4 数据包的地址是 32 位，IPv6 数据包的地址是 128 位

面向连接服务的实现

当建立一个连接时，从源机器到目标机器之间的一条路径就被当作这个连接的一部分确定了下来，并且保存在这些中间路由器的表中
所有需要在这个连接上通过的流量，都使用这条路径
当连接被释放之后，虚电路也随之消失
在面向连接的服务中，每个数据包包含一个标识符，指明了它属于哪一条虚电路

连接标识符 1 的数据包来自于 H1，将被发送到路由器 C，并赋予连接标识符 1
H3 也希望与 H2 建立连接，新增第二行，因为 A 可以区分数据包来自 H1 还是 H3 但 C 无法区分，基于这个原因，A 给第二个连接的出境流量分配一个不同的连接标识符

标签交换（label switching）

虚电路

请求连接，在每个数据可以传输前请求
每个数据包携带一个 VC 标识符（不是目标主机ID）
在源端-目标地址路径上的每个路由器为每个经过的连接维护状态
传输层连接只涉及到两个端系统
可以为虚电路分配链路（link）、路由器资源（带宽、缓冲）

一种面向连接的网络服务例子是多协议标签交换（MPLS）

主要被用在 Internet 的 ISP 网络，IP 数据包被一个有 20 位连接标识或标签的 MPLS 头包裹着
MPLS 往往对客户端是隐藏的，客户看不到这些标签，ISP 用它来为超大流量建立长期的连接
但是，当服务质量变得很重要而且还需要协助其他 ISP 完成流量管理任务时，ISP 的作用越来越突出

虚电路与数据报网络的比较

在网络内部，数据报和虚电路网络之间存在着几个方面的权衡

建立时间和地址解析时间
- 使用虚电路需要一个建立阶段，这个阶段计划费时间也消耗资源
- 在数据报网络中，不需要建立电路，但路由器需要执行一个更为复杂的查找过程以便找到目标表项
开销和带宽
- 如果数据包相当短，在每个数据包中都包括完整的目标地址可能意味着大量的协议开销，因而造成带宽资源的浪费
路由器内存所要求的表空间的数量
- 数据报网络中，针对每一个可能的目标地址都要求有一个表项
- 虚电路网络中，只要为每一条虚电路提供一个表项即可

其他方面

从保证服务质量以及避免网络拥塞的角度来看，虚电路有一定的优势，因为在建立连接时，资源可以提前预留（比如缓冲区控件、带宽和 CPU 周期）
路由器崩溃，虚电路网络中，经过该路由器的连接都不得不中断，而在数据报网络中，丢失的数据包可以立即重传
数据报还允许路由器平衡网络流量，因为一个长序列数据包的传输路径可以在序列传输的中途改变

路由算法

路由和转发

路由即对使用哪一条路径做出决策，而转发则是当一个数据包到达时应该采取什么动作

可以把路由器想象成内部有两个进程
- 一个进程在每个数据包到达的时候对其进行处理，它在路由表中查找该数据包所对应的出境线路，这个进程即为转发（forwarding）
- 另一个进程负责生成和更新路由表，这正是路由算法发挥作用的地方

路由算法

路由涉及以下问题：

在将数据包转发给路由器 K 时，路由器应该使用哪条线路
目标：确定通过网络从源到目的地的“好”路径（路由器序列）

路由算法（routing algorithm）是网络层软件的一部分，它负责确定一个入境数据包应该被发送到哪一条输出线路上

路由算法的特性

正确性（correctness）、简单性（simplicity）
鲁棒性（robustness）
- 一旦一个重要网络投入运行，它有可能需要连续运行数年而不能出现波及系统范围的失败，部分组件可能失败（链路、路由器）
- 路由算法应该能够处理各种各样的硬件和软件发生故障，还有拓扑结构和流量方面的各种变化，而且不能要求所有主机都停止所有的工作
稳定性（stability）
- 一个稳定的路由算法能达到平衡，并且保持平衡状态。因此它应该迅速收敛，在路由器算法到达平衡之前，通信可能无法正常运行
公平性（fairness）、有效性（efficiency）
- 时常是矛盾的

路由算法分类

非自适应算法（nonadaptive algorithm）

不会根据当前测量或者估计的流量和拓扑结构，来调整路由决策
使用的路由选择是预先在离线情况下计算好，并在网络启动时被下载到路由器中的。有时也称为静态路由（static routing）
无法响应故障，所以静态路由对于路由选择已经清楚的场合非常有用

自适应算法（adaptive algorithm）

使用动态信息（当前流量、拓补结构、延迟等）来选择路由
改变路由决策以便反映出拓扑结构的变化，通常也会反映出流量的变化情况
在多个方面有所不同
- 获取信息的来源（本地，相邻路由器，所有路由器）
- 改变路径的时间（每当拓扑发生变化时，每隔△t秒随负载变化）
- 路由优化度量（距离，跳数，估计的传输时间）

优化原则（optimality principle）

如果路由器 J 在从路由器 I 到路由器 K 的最优路径上，那么从 J 到 K 的最优路径也必定遵循同样的路由

汇集树

作为优化原则的一个直接结果，从所有的源到一个制定目标的最优路径的集合构成了一棵以目标节点为根的汇集树（sink tree）

图中的距离度量是跳数
所有路由算法的目标是为所有路由器找到这样的汇集树，并根据汇集树来转发数据包

汇集树不一定是唯一的：有可能存在具有相同路径长度的其他汇集树

图抽象

由算法的图抽象：

图中的每个节点代表一个路由器
图的每条边是代表一条通信线路或物理链路
- 链路成本：延迟，成本，拥塞等级
选择给定路由器对之间的路由：找到“好”路径
- 通常意味着最小成本路径
- 其他可能的定义

最短路径算法

常用，因为简单易懂

最短路径度量（路径长度）

跳数（hop）
物理距离
平均排队和传输延迟
带宽
平均流量
通信成本

Dijkstra 算法

这种算法能找出网络中一个源节点到全部目标节点的最短路径

迪杰斯特拉算法（或变体，SPF 最短路径优先算法）的基本思路是

选择源，并将列表中连接到源的节点考虑进来
选择距离最近的节点

加权无向图上的算法

泛洪（flooding）

泛洪是孤立路由的一种形式，不选择特定的路线。将每一个入境数据包发送到除了该数据包到达的那条线路以外的每条出境线路

为了防止数据包永久循环，每个路由器递减包头中包含的跳计数器。只要跳计数器递减到零，路由器就丢弃该数据包

减少循环

让每个源路由器在接收到来自数据的数据包时设置一个序号
每个路由器为每个源路由器准备一张表，记录已经观察到的来自源路由器的序号
如果入境数据包在这张表中，它就不能再被泛洪到其他路由器
- 为防止表无限膨胀，每个表使用一个计数器 k 作为参数，表示直到 k 的所有序号都已经观察到了

用途

确保数据包能被传送到网络中的每个节点

有效的广播手段，一些无线路由算法利用了这个特性

泛洪途径的鲁棒性非常好

即使路由器被炸成碎片（战争地区），泛洪也能找到一条路径（如果存在），使得数据包到达目的地

泛洪需要的安装很少，路由器仅仅需要知道自己的邻居即可

泛洪可以作为其他路由算法的基本构建
泛洪还可用作其它路由算法进行比较的性能度量

发送路由更新，因为更新不能依赖路由器表的正确性

理论上选择所有的路径，选出最短的那条路径

距离矢量路由

也被称为分布式 Bellman-Ford 路由算法，最初 APPANET 使用的路由算法，也曾被用于 Internet，相应的协议名为 RIP 协议

工作原理

每个路由器维护一张表（即一个矢量），表中列出了当前已知的到每个目标的最佳距离，以及所使用的链路。这些表通过领居之间相互交换信息而不断被更新，最终每个路由器都了解到达每个目的地的最佳链路
每个路由器知道自己到邻居的距离（成本）
- 跳数：1 跳
- 传播延迟：通过发送回应请求（ECHO request），返回加上时间戳的数据包
路由器周期性地和邻居交换路由表
接收到路由表更新后，对表中的每个目的地
- 用邻居表的值加上本地到邻居表的成本和本地的表比较
- 如果通过邻居的路径成本更低，那么路由器更新本地表以将数据包转发给邻居

D-V 路由例子

无穷计数问题

整个网络最佳路径的寻找过程称为收敛（convergence）

距离矢量路由总是能够收敛到正确的答案，但速度可能非常慢

好消息传得快，坏消息传得慢（无穷计数问题）

无穷计数问题（count-to-infinity）

（a）假定 A 最初处于停机状态，所有其他路由器都知道这一点；当 A 启动时，其他的路由器通过矢量交换知道了这一点
- 如果一个网络中最长路径是 N 跳，那么经过 N 次交换后，每个路由器都将知道新恢复的链路和路由器
（b）假定所有线路和路由器最初都是正常工作的；突然 A 停机了，或者 A 和 B 之间的链路断了

没有一个路由器具有一个比它所有邻居的最小值还大于 1 的值，逐渐所有的路由器都会趋向无穷大，但是所需交换的次数依赖于代表无穷大的数值。由于这样的原因，明智的做法是将无穷大设置为最长的路径加 1

问题的核心

当 X 告诉 Y 它有一条通往某个地方的路径，Y 无从知道自己是否已在这条路径上

尝试解决

带有染毒逆向的水平分裂法（Split horizon with poisoned reverse）RFC 1058

链路状态路由

1979 年以前 APPANET 一直使用距离矢量路由算法，而在此之后则改为使用链路状态路由算法

距离矢量算法的问题

当网络拓扑结构发生变化后距离矢量路由算法需要太长时间才能收敛到稳定状态（无穷计数问题）
高优先级路由更新数据包很大，对流量造成不利影响
网络适应拥塞的速度太慢，对小变化的反应太快
平均队列长度用于估计延迟
- 仅当所有线路具有相同的容量（capacity）和传输延迟（propagation delay）时才有效
- 不考虑数据包大小的不同

每个路由器维护一个数据库，描述每个路由器之间的的拓扑结构和链路延迟。也就是说，每个路由器都会跟踪链接和节点的完整图形

避免由于所有路由器获取其他路由器的信息而导致无穷计数问题
每个路由器都使用 SPF 算法根据数据库中的当前值计算最短路径
因为每个路由器都使用相同的信息进行计算，所以可以做出更好的路由决策

每一个路由器必须完成以下事情，算法才能正常工作

发现它的邻居节点，并了解其网络地址
设置到每个邻居节点的距离或者成本度量值
构造一个包含所有刚刚获知的链路信息包
将这个包发送给所有其他的路由器，并接收来自其他所有路由器的信息包
计算出到每个其他路由器的最短路径

实际上，算法将完整的拓扑结构分发给了每一个路由器。然后每个路由器运行 Dijkstra 算法就可以找出从本地到每一个其他路由器的最短路径

发现邻居

当一个路由器启动时，它的第一个任务是找出哪些路由器时它的邻居

为了实现这个目标，它只需在每一条点到点线路上发送一个特殊的 HELLO 数据包

线路另一端的路由器应该返回一个应答说明自己是谁，这些名字必须是全局唯一的

当两个或多个路由器通过一个广播链路（比如一个交换机、环或经典以太网）

（a）一个广播 LAN 直接与三个路由器 A、C、F 连接。每个路由器都连接到一个或多个其他的路由器上
- 广播 LAN 为连接到其上的任何一对路由器提供了彼此的连通性
- 然而，把 LAN 建模成许多个点到点链路会增大拓扑结构，从而导致浪费消息
（b）引入节点 N 和 A、C、F 连接，LAN 上的一个指定路由器（designated router）被选中替代 N 运行路由协议

设置链路成本

到邻居的成本可自动设置或由网络运营商配置的度量

一种常用的选择是使成本与链路带宽成反比
1Gbps-1，100Mbps-10

如果网络在地理上分散，链路的延迟可以作为成本的组成部分，这样才能更好地选择较短链路上的路径

确定这种延迟的最直接方法是通过线路给另一边发送一个特殊的 ECHO 数据包，要求对方立即发回
通过测量往返时间再除以 2，发送路由器可以得到一个合理的延迟估算值

构造链路状态包

数据包的内容：发送方的标识符（ID）、序号（Seq）、年龄（Age）、邻居列表

对每个邻居，同时给出到这个邻居的延迟

构造链路状态包很容易，难确定的是什么时候构造

周期性地创建数据包
每当发生重要事情时才创建数据包
- 比如当一条线路断掉或一个邻居节点停机

分发链路状态包

基本思路是使用泛洪将链路状态数据包分发给所有路由器

为了控制泛洪规模，每个数据包都包含一个序号，序号随着每一个新数据包发送而逐一递增
路由器记录下它所看到的所有（源路由器、序号）对。当一个新的链路状态数据包到达时，路由器检查这个新来的数据包是否已经出现在列表中
- 如果是新数据包，则把它转发到除入境线路之外的所有其它线路上
- 如果是重复数据包，则把它丢弃
- 如果数据包的序号小于当前所有看到过的来自该源路由器的最大序号，则它将被当作过时数据包而拒绝接受，因为路由器已经有了更新的数据

年龄（age）字段

问题

如果序号绕回，可能会产生混淆
如果一个路由器崩溃了，它将丢失所有的序号记录表
如果一个序号被破坏

解决方案：

在每个数据包的序号之后包含一个年龄（age）字段，并且每秒钟将年龄减 1 。当年龄字段的值被减到 0 时（路由器链路状态数据库），来自路由器的该信息将被丢弃
在初始泛洪过程中，每个路由器也要递减 age 字段，这样可以确保没有数据包丢失，也不会无限生存下去（如果一个数据包的 age 为 0，则被丢弃）

改进

当一个链路状态数据包被泛洪到一个路由器时，它并没有立即被排入队列等待传输。相反，它首先被放到一个保留区中等待一段时间，如果在这个数据包被转发出去之前，另一个来自于同一个源路由器的链路状态数据包也到来了，那么就比较它们的序号。
- 如果两个数据包的序号相等，则丢弃重读数据包
- 如果两者不相等，则丢弃老的数据包
为了防止线路产生错误导致丢包和错包，所有的链路状态数据包都要被确认

计算新路由

一旦路由器已经积累了全部的链路状态数据包之后，它就可以构造出完整的网络图，因为每条链路都已经被表示出来了。事实上，每条链路被表示了两次，每个方向各表示一次。不同方向的链路可能有不同的成本。最短路径计算可找到从 A 到 B 与从 B 到 A 不同的路径

现在可以在路由器本地运行 Dijkstra 算法，以便构建出从本地出发到所有可能目标的最短路径。这个算法的运行结果告诉路由器到达每个目的地能够走哪条链路。这个信息被安装在路由表中，而且恢复正常操作

链路状态路由总结

需要更多的内存和计算
- 在大型网络中运行这个算法依然是个问题
没有慢收敛问题
- 在许多实际场合，链路状态路由算法工作地很好

应用

许多 ISP 使用中间系统到中间系统（IS-IS, Intermediate System-Intermediate System）链路状态协议
开放最短路径优先（OSPF, Open Shortest Path First）

层次路由（hierarchical/hierarchy）

区域（reigon）-簇（cluster）-区（zone）-群（group）-…

广播路由（broadcast）

同时给全部目标地址发送一个数据包称为广播（braodcasting）

实现广播

广播网络
- 设置一个特殊的地址作为“所有主机地址”
非广播网络
- 给每个目标地址单独发送数据包（单播unicast）
  - 浪费带宽
- 泛洪
  - 产生太多数据包，浪费带宽
- 多目标路由（multidestination outing）
- 生成树（spanning tree）
  - 网络的一个子集，包含所有的路由器，但没有任何环路
  - 汇集树是生成树的一种
- 逆向路径转发（RPF, reverse path forwarding）

组播路由（multicast）

距离矢量组播路由协议（DVMRP）

基于核心树（core-based trees）的技术

任播路由（anycast）

也叫选播

移动主机路由（mobile host）

家乡位置（home location）
家乡地址（home address）
家乡代理（home agent）

自组织网络路由（ad hoc network）

Ad hoc 按需距离矢量路由算法（AODV）

网络互联（internetwork）

internet

将两个或多个网络连接起来

Internet

更通用的术语，由不同硬件和协议组成

存在着许多不同的网络

PAN、LAN、MAN、WAN
- 以太网（Ethernet）、802.11、802.16、固定和移动电话网络

梅特卡夫定律（Metcalfe）

一个具有 $N$ 个结点的网络的价值等于节点之间的连接数，或者 $N^2$
这意味着大型网络比小型网络更有价值，因为它们允许更多的连接，所以始终有将小型网络联结起来的激励

网络如何不同

何以连接网络

两种基本选择

可以制造设备，它能将每种网络的数据包翻译或转换成每个其他类别网络的数据包
尝试在不同网络的上面加一个间接层，并且构造一个公共层来解决这个问题
两种情况下，新设备被放置在网络之间的边界上

Cerf 和 Kahn 提出用一个公共层来隐藏所有网络的差异

IP 提供了一种通用的数据包格式，所有路由器都认识这种数据包，因而这种数据包几乎可以通过所有的网络传递
- 计算机网络、电话（telephone）网络、传感器（sensor）网络

连接网络的不同设备

中继器（repeater）、集线器（hub） —— 物理层

只是将比特从一根导线移动到另一根导线，它们大多是模拟设备

网桥（bridge）、交换机（switch） —— 数据链路层

可以被用来构建网络，只能处理轻微的协议转换
- 例如，在 10、100、1000 Mbps 以太网交换机之间传递帧

路由器（router） —— 网络层

能够连接两个网络

用一个公共的网络层来互连不同的网络

帧结构

网络协议操作

路由情况和交换（或桥接）的本质区别

在路由器上，数据包被从帧中提取出来，数据包中的网络地址被用来决定把它转发到哪里
- 路由器不必了解交换机所使用的链路层协议
在交换机（或网桥）上，整个帧是根据其MAC地址传送的
- 交换机不必了解正在被交换的数据包所采用的网络层协议

引入网桥的目的就是用它们将不同类型的网络连接起来，或者至少把不同类型的局域网连接在一起

把一个LAN的帧翻译成另一个LAN的帧，这样工作并不理想

现在，网桥主要用于在数据链路层连接相同类型的网络
路由器在网络层连接不同的网络

仅当有一个公共网络层时，网络互联才能工作

IP、IPX、SNA、AppleTalk
IPv4、IPv6

可以处理多个网络协议的路由器称为多协议路由器（multipeotocol router）

但是具有不同网络协议的网络很难在两者之间进行转换
隧道是一个常见的特例

隧道（tunneling）

源主机和目标主机所在的网络类型完全相同，但中间却隔着一个不同类型的网络

整个数据包被封装在中间不同类型的网络协议中，之后在另一侧被恢复
避免了翻译数据包

隧道类比

隧道被广泛用于连接那些因使用其他网络而被隔离的主机和网络。结果生成的网络就是所谓的覆盖（overlay）网络，因为它有效地覆盖在基础网络之上

隧道的缺点是无法到达位于隧道之下网络的主机，因为数据包无法送隧道中间逃生

这个限制变成了虚拟专用网络（VPN, Virtual Private Networks）的优势
VPN 就是一个提供安全措施的简单覆盖网络

互联网路由

互联网络的路由所面临的问题

内部网络可能使用不同的路由算法
网络由不同的运营商运行，运营商对于什么是通过网络的好路径有不同的想法
一个运营商甚至可能不希望另一个运营商了解它网络的路径细节
互联网络可能比构成它的任何一个网络都大。因此它或许需要采用层次结构的扩展性较好的路由算法，即使没有一个网络需要使用层次结构路由

两级路由算法

在每个网络中，使用一个域内（intradomain）或内部网关协议（interior gateway protocol）进行路由
- 链路状态路由、距离矢量路由
为了让数据包跨越构成互联网的网络，就需要用到域间（interdomain）或外部网关协议（exterior protocol），边界网关路由协议（BGP, Border Gateway Protocol）
网络可能全部使用不同的域内协议，但必须使用相同的域间协议

自治系统 AS（Autonomous System）

每个网络独立于所有其他网络运营，因此这样的网络通常称为一个自治系统 AS（Autonomous System）
AS 的良好默认模型是 ISP 网络
- 事实上，一个 ISP 网络或许由多个 AS 组成

路由策略（routing policy）

在 Internet 上，一大决定因素是 ISP 之间的商业安排
- 每个 ISP 可能因替其他 ISP 承载流量而收取或接收相应的费用
另一个因素在于，如果国际互联网络的路由需要跨越国界
- 各国的法律可能会突然开始发挥作用
所有这些非技术因素都包裹在一个路由策略概念中，控制着自治网络自主选择所用的路由

数据包分段

每个网络或者链路都会限制其数据包的最大长度，这种限制来自多方面的原因

硬件（比如以太网帧的长度限制）
操作系统（比如所有的缓冲区都是 512 字节）
协议（比如数据包长度字段中的位数）
遵从某个国家（或国际）标准
期望将错误引入的重传次数减少到某种程度
期望防止数据包占用信道时间太长

路径 MTU

路径上的最大的数据包大小称为路径最大传输单元（MTU, Path Maximun Transmission Unit）

源端通常不知道数据包通过网络到达接收方的路径，因此也不知道路径 MTU 的大小
即使源端知道路径 MTU，数据包在无连接网络中也是独立路由的，比如 Internet。这种路由意味着路径可能会突然改变，因而意外地更改路径 MTU

分段（Fragment）

允许路由器将数据包拆分成段，将每个段作为一个独立的网络层数据包发送

数据包交换网络把段重新整合起来非常麻烦

两种对立策略
- 透明分段（non-Transparent Fragment）
- 非透明分段（Transparent Fragment）

透明分段

从该网络一直到最终的目标途中的每个网络都感觉不到曾经发生过分段

一个网络中，进入路由器对一个数据包进行分段，同一网络中的出口路由器将这些分段重新组装成原始数据包

问题

出口路由器必须知道什么时候它已经接收到了全部的段
- 每个分段中必须提供一个计数字段 / 结束标志位
所有的数据包必须经过同一个出口路由器才能进行重组
- 路由收到了限制
需要缓冲
开销（当一个数据包需要通过一系列的小数据包网络时，需要多次被分段和重组）

非透明分段

避免在任何一个中间路由器上重新组合分段。一旦一个数据包已经被分段，则每个段都被当做原始的数据包一样来对待，重组过程只在目标主机上进行

路由器所做的工作比较少，IP 就是以这种方式工作的

缺点

要求每个主机都能够重新组装
携带小片段的开销直到目的地（因为每个片段都必须有一个头）
如果丢失了任何一个分片，整个包都将丢失

一个完整的设计要求分段可以重新构建原数据流的方式编号

IP 采用的设计思想是
- 给每一个段一个数据包序号（所有的数据包都携带）、一个数据包内的绝对字节偏移量、和一个指明是否到达数据包末尾的标志位

段到达目的地后可以被放置在一个缓冲区中以便重组，即使这些分段到达的顺序凌乱不堪
当段要穿过一个 MTU 更小的网络时，还可以被路由器再次进行分段
数据包的重传（如果所有的段都没有收到）可以被分割成不同的段
段可以任意大小，最小的段是一个字节加上数据包头
在所有情况下，接收方只需简单地使用数据包的序号和段偏移量即可把数据放置在合适的位置，并利用数据包结束标志位来确定何时有了一个完整的数据包

问题

因为段的存在，开销可能比透明分段高
分段不利于性能，因为除了增加头开销，数据包的丢失概率也增加了；任何一个段的丢失都将导致整个数据包的丢失；而且对于主机而言，分比不分带来了更大的突发

路径 MTU 发现（path MTU discovery）

工作原理

每个 IP 数据包发出时在它的头设置一个比特，指示不允许对该数据包实施分段操作
如果一个路由器接收的数据包太大，它就生成一个报错数据包并发给源端，然后丢弃该数据包
- ICMP [Type 3, Code 4] 消息包含了 MTU
当源端收到报错数据包它就使用报错数据包携带的信息重新将出错数据包分段，每个段足够小到报错路由器能够处理
如果沿着路径前进又遇到一个 MTU 更小的路由器，那么重复上述过程

路径 MTU 发现的优点是源端知道应该发送多长的数据包了

如果路由器和路径 MTU 发生改变，新的报错数据包将被触发返回，因而源端将适应新的路径。然而，仍然需要在源端和接收方之间实施分段，除非更高层次的协议了解路径 MTU，并把适量的数据传给IP。TCP 和 IP 通常是一起实现的，因而能够传递这类信息。即使其他协议不是这样实现，仍然可以把分段移出网络，让主机承担

缺点是有可能增加发送数据包的启动延迟

在任何数据被传递到目的地之前，探讨路径并且找出该路径 MTU 所花的时间可能需要不止一个往返延迟
- 更好的设计：每个路由器把那些超出其 MTU 的数据包简单地拦腰截断，这样一来将确保接收方尽可能快地了解MTU（从传递过来的数据量），同时接收到了部分数据

Internet 的网络层

10 大原则 RFC 1958

保证工作（make sure it works）
保持简单（keep it simple）
明智选择（make clear choices）
模块开发（exploit modularity）
期望异构性（expect heterogeneity）
避免静态选项和参数（avoid static options and parameters）
寻找好的而不是完美的设计（look for a good design; it need not be perfect）
严格发送，宽容接收（be strict when sending and tolerant when receiving）
考虑可扩展性（think about scalability）
考虑性能和成本（consider performance and cost）

在网络层，可以把 Internet 看作是一种相互关联的网络或自治域（自治系统）集合。没有真正的结构，但存在几个主要骨干网。这些都是由高带宽线路和快速路由器组成。这些骨干网中最大的一个称为一级网络（Tier 1 networks），每个骨干网都与它连接，进而到达其他骨干网。连接到骨干网上的是 Internet 服务提供商（ISP, Internet Service Provider），它为家庭和企业、数据中心和服务器托管设施，以及区域（中级）网络提供 Internet 接入服务。

将整个 Internet 黏合在一起的正是网络层协议，即 Internet 协议（IP, Internet Protocol）

IP 在设计之初就把网络互联作为目标
IP 的任务是提供一种尽力而为（best-effort）地把数据包从源端传输到接收方的方法（即不提供任何保证），无须考虑这些机器是否在同一个网络，也不必担心它们之间是否还有其他网络

Internet 中的通信过程

传输层获取数据流，并且将数据流拆分成段，以便作为IP数据包发送
- 理论上，每个数据包最多可容纳 64 KB ，但实际上，数据包通常不超过 1500 字节（以太网帧）
IP 路由器转发每个数据包穿过 Internet ，沿着一条路径把数据包从一个路由器转发到下一个路由器，直到数据包到达目的地
当所有的数据段最终都抵达目标机器，它们被网络层重新组装还原成最初的数据报
然后该数据报被网络层传给传输层
- 在接收方，网络层将数据交给应用层，再由传输层交给接收进程

TCP/IP 协议栈

Internet 体系结构沙漏

协议数据单元封装

网络字节序

经常出现的一个问题是不同的机器以不同的方式表示整数

大端序（Big Endian），最高有效字节在最低地址处（左边）
小端序（Little Endian），最高有效字节在最高地址处

与所有网络协议一样，标准指定每个字段中所有位的含义，根据字节和位的顺序

Internet 定义大端序为标准字节序，用于指向 Internet 数据报的字段

IPv4 协议

每个 IP 数据报包含两个部分：一个头和一个正文（有效载荷）

头由一个 20 字节的定长部分和一个可选的变长部分组成

4 bit 版本（version）

记录了数据报属于协议哪个版本，IPv4 / IPv6

4 bit IHL

指明了头到底有多长（以 32 位字长度为单位）
最小值为 5，表明没有可选项；最大值为 15，把头的长度限制为最大 60 字节
实际用来指出数据的起始部分

8 bit 区分服务（differentiated services）

前 6 位用来标记数据包的服务类别，后2位用来携带显式拥塞通知信息（数据包是否经历拥塞）

16 bit 总长度（total length）

包含了该数据报中的所有内容，即头和数据
最大长度是 65535 个字节

16 bit 标识（identification）

让目标主机确定一个新到达的分段属于哪一个数据报
同一个数据报的所有段包含同样的标识（分段）

1 bit 未使用
1 bit DF （Don’t Fragment）

不允许路由器分割该数据报
路径 MTU（完整到达/返回报错消息）

1 bit MF （More Fragment）

代表更多的段，除了最后一个段以外，其他所有的段都必须设置这一位
接收方可以知道什么时候一个数据报的所有分段都已经到达了

13 bit 分段偏移量（fragment offset）

指明了该段在当前数据报中的位置
除了数据报的最后一个段以外，其他所有段的长度必须是 8 字节的倍数
每个数据报最多有 $2^{13} = 8192$ 个段，支持 total length 字段限制的最大数据包
identification、MF、fragemnt offset 协同工作，实现分段操作

8 bit 生存期（TTL, time to live）

限制数据包生存期的计数器（跳计数器）
避免数据包永远滞留在网络中

8 bit 协议（protocol）

指明了将数据包交给哪个传输进程
ICMP:1 00000001
IGMP:2 00000010
TCP :6 00000110
UDP :17 00010001
OSPF:89 01011001

16 bit 头检验和（header checksum）

校验保护
每一跳必须重新计算校验和字段，以内至少有个字段总是不断在改变（TTL）

32 bit 源地址（source address）
32 bit 目标地址（destination address）

表示源网络接口和目标网络接口的 IP 地址

0~40*8 选项（options）

选项字段的设计意图是提供一种途径，允许后续版本协议包含一些原设计中没有出现的信息，以便实验人员尝试新的想法、避免为那些不常使用的信息分配头字段
选项字段用来将整个选项长度填充到4字节的倍数
每个选项字段的第一个字节是一个标识码，标明了该选项类别。有的选项后面跟着 1 字节的选项长度字段，然后是一个或多个数据字节

IP 嵌入式数据报包含源发送端（不是转发网关）和目标的唯一地址

分段举例

IP 地址

IPv4 的一个明确特征是它的 32 位地址

Internet 上的每台主机和每个路由器都有一个 IP 地址，可用在 IP 数据包的 source address 和 destination address 字段

一个 IP 地址并不真正指向一台主机，而是指向一个网络接口

每个 IP 地址都是唯一的

地址由 32 位标识符组成
Internet 软件将地址转换成名字，将名字转换成地址；低层协议通常使用地址而不是名字
地址编码其网络地址和主机号，这种组合是唯一的：原则上，Internet 中没有两台机器具有相同的 IP 地址

IPv4 地址举例

前缀（prefix）

点分十进制表示法（dotted decimal notation）

4 个字节中的每个写成十进制，取值范围从 0 到 255
32 位 16 进制地址 80D00297 写成 128.208.2.151
最低 IP 地址为 0.0.0.0，最高 IP 地址为 255.255.255.255

前缀

每个 32 位地址由高位的可变长网络和低位的主机两部分数据组成
同一网络上（比如以太局域网）的所有主机，其地址的网络值是相同的，这意味着一个网络对应一块连续的IP地址空间，这块地址空间就称为地址的前缀（prefix）
前缀的书写给出了块的最低 IP 地址和块的大小
- 块大小由网络部分的位数决定；地址中主机部分的剩余位数可以有所变化
- 这意味着，块的大小必须是 2 的幂次方

按照惯例，网络地址的书写格式是前缀IP地址后跟一个斜线，斜线后是网络部分的位长度

如果前缀包含 $2^8$ 个地址，留下了 24 位用于网络部分，写成 128.208.0.0/24
斜线读作 slash
因为前缀长度仅从 IP 地址无法判断出来，路由协议必须把前缀携带给路由器
前缀长度相当于网络部分中 1 的二进制掩码，以这格式书写时称为子网掩码（subnet mask），它可以与一个 IP 地址进行 AND 操作，以便提取出该 IP 地址的网络部分

IP 前缀为 128.208.0.0/24
子网掩码为 255.255.55.0

层次化地址

优点

路由器仅仅根据地址的网络部分即可转发数据包，只要每个网络都有一个唯一的地址块
- 对路由器来说网络地址的主机部分并不重要，因为同一网络上的所有主机都在同一个方向，只有当数据包到达它们的目的地网络后才被转发到正确的主机
- 需要维护的路由表的大小减少

缺点

一个主机的 IP 地址取决于它位于网络上的位置
- 以太网地址可用于世界上任何地方，但每个 IP 地址属于一个特定的网络，路由器只能传递注定要到该网络上某个地址的数据包。比如移动IP这样的设计必须支持主机在网络之间移动，但同时保持相同的 IP 地址
层次结构浪费了地址，除非精心管理地址空间
- 如果给网络分配大块的地址，将有很多被分配但不会使用

子网（subnet）

地址分配

为了避免冲突，网络地址的管理由一个称为Internet域名和地址分配机构（ICANN, Internet Corporation for Assigned Names and Number）的非营利性公司负责
ICANN 一次把部分地址空间授权给各区域机构，这些机构再把 IP 地址发放给 ISP 和其他公司

子网划分（subnetting）

在内部将一个网络块分成几个部分供多个内部网络使用，但对外部世界仍然像单个网络一样
分割一个大型网络得到的一系列结果网络（比如以太网）称为子网（subnet）

子网划分例子

一个/16地址空间被分割成几片
这种分割并不要求均匀，但每片必须对齐以便可以把较低的任何位用作地址的主机部分

块的一半（/17）分配给了艺术系
四分之一（/18）分配给了电机工程学系
八分之一（/19）分配给了艺术系

子网成分（properties）

路由器决定将数据包转发到哪个子网

当数据报到达时，路由器会查看该数据包的目标地址，并检查它属于哪个子网
- 路由器把数据包的目标地址与每个子网的掩码进行 AND 操作，看结果是否对应于某个前缀

决定入境数据包

哪个子网

例子

在网络外面，子网的划分是不可见的，因此分配一个新的子网不需要联系ICANN或者改变任何外部数据库

决定出境数据包

本地（local）还是远端（remote）网络

CIDR —— 无类域间路由

路由表爆炸

ISP 和骨干路由器之间的路由必须知道通过哪些方式可到达每个网络，这里没有简单的默认路由可用。这些核心路由器处在一个 Internet 默认自由区（default-free zone）
Internet 包含上百万的网络，产生一个巨大的路由表
此外，路由算法要求每个路由器与其他路由器交换有关它能到达的地址信息。表越大，需要通信和处理的信息量也越大

路由聚合（aggregation）

减小路由表的大小
不同的路由器可以知道一个给定 IP 地址的不同大小前缀
把多个小前缀的地址块合并成一个大前缀的地址块，这个合并过程称为路由聚合
由此产生的较大前缀地址块有时称为超网（supernet），以便有别于地址块的分割

无类域间路由（CIDR） RFC 4632

有了地址聚合，IP 地址可包含大小不等的前缀，同样一个 IP 地址，一台路由器把它当做 /22 的一部分对待（其中包含 $2^{10}$ 个地址），另一台路由器把它当做一个更大的 /20 一部分对待（其中包含 $2^{12}$ 个地址）。这是因为每个路由器有相应的前缀信息，这个设计和子网划分协同工作，统称为无类域间路由（CIDR, Classless Inter-Domain Routing）

工作原理

路由表由（IP 地址, 子网掩码, 出境线路）的三元组组成
- 当一个数据包到达时，路由器扫描路由表以便确定目的地是否在前缀的地址块内
当一个数据包到达时，首先提取其目标 IP 地址。然后（在概念上）路由表按照条目进行扫描，对目标地址作掩码操作并与路由表条目进行比较以寻找匹配
- 真正一个表项一个表项地扫描表，将会相当冗长乏味
- 人们设计了复杂的算法来加快地址匹配过程（Ruiz-Sanchez）；商用路由器使用了定制的 VLSI。这些算法被嵌入到了硬件中
有可能多个具有不同前缀的表项得到匹配，在这种情况下，使用具有最长前缀的表项（最长匹配前缀）
因此，如果有一个匹配 /20 掩码的表项，同时还有一个匹配 /24 掩码的表项，则使用 /24 表项来查询数据包的出境线路

例子

伦敦路由器示意图

最长匹配前缀（longest matching prefix）

前缀允许重叠，规则是数据包按最具体路由器的方向发送，即具有最少IP地址的最长匹配前缀（longest matching prefix）

分配和特殊寻址

分类寻址

IP 被分为 5 个类别，这种分配称为分类寻址（classful addressing）

A 类地址：128 个网络，每个网络 1600 万台主机
B 类地址：16384 个网络，每个网络 65536 台主机
C 类地址：200 万个网络，每个网络多达 256 台主机（不过有些地址是特殊的）
D 类地址：支持 Internet 组播，即数据包被直接发送给多台主机
E 类地址：111 开头的保留地址，以备将来使用

层次化设计，但与 CIDR 不同：地址块的大小是固定的，因此有很多地址的浪费

引入了子网，以便在一个组织内部灵活分配地址快
引入 CIDR 技术来减小全局路由表的大小

特殊 IP 地址

0.0.0.0 最低的地址，代表本机，指的是当前网络
255.255.255.255 最高的地址，用来标识指定网络中的所有主机，允许在本地网络上广播，通常是局域网
127.xx.yy.zz 保留给回环测试用，测试网络软件

NAT —— 网络地址转换

动态 IP 地址

为一台连在网上并使用网络的计算机动态分配一个 IP 地址，而且在该主机不活跃时收回分配给它的 IP 地址；然后该 IP 地址可以被分配给另一台活跃的计算机

对于使用拨号连接的家庭用户，解决 IP 地址问题的一个方法是在电话呼叫并登陆时动态分配 IP 地址，并在会话结束时将 IP 地址返还
- 客户希望持续在线
- ADSL 或线缆上的 Internet 服务（永久 IP 地址和月租费）

网络地址转换 NAT（RFC 3022）

NAT 的基本思想是 ISP 为每个家庭或每个公司分配一个或少量 IP 地址，用这个 IP 地址来传输 Internet 流量

在客户网络内部，每台计算机有唯一的 IP 地址，该地址主要用来路由内部流量
当一个数据包需要离开客户网络，发向其他 ISP 时，它必须执行一个地址转换，把唯一的内部 IP 地址转换成那个共享的公共 IP 地址

保留的 IP 地址（reserved）

地址转换使用了 IP 地址的三个范围，这些地址已经被声明为私有化。任何网络可以在内部随意地使用这些地址。仅有的规则是不允许包含这些地址的数据包出现在 Internet 上

ip	hosts
1.0.0.0 – 10.255.255.255 /8	16,777,216 hosts
172.16.0.0 – 172.31.255.255 /12	1,048,576 hosts
192.168.0.0 – 192.168.255.255/16	65,536 hosts

NAT 操作过程

每台机器都有一个形如 10.x.y.z 的地址

当一个数据包离开客户端时，它首先要通过一个 NAT 盒子（NAT box）

NAT 盒子将内部的IP源地址转换成该客户所拥有的真实IP地址
NAT 盒子通常与防火墙组合成一个单一设备，防火墙提供了一种安全机制（仔细地控制着进出客户网络的流量）
NAT 盒子还有可能集成到路由器或者 ADSL 调制解调器中

NAT 应答问题

当应答数据包返回时，NAT盒子如何知道该用哪一个地址来替代？

TCP/UDP 端口（port）
- 大多数 IP 数据包携带 TCP/UDP 有效载荷
- 两个协议的头都包含了一个源端口和一个目标端口字段
- 端口是 16 位整数，指示 TCP 连接从哪里开始以及到哪里结束
- 这些端口字段为 NAT 提供了工作所需的字段

TCP 连接建立

当一个进程希望与另一个远程进程建立 TCP 连接时，它把自己绑定到一个本地机器尚未使用的 TCP 端口上

该端口称为源端口（source port），它告诉 TCP 代码凡是属于该连接的入境数据包都应该发送给该端口。

这个进程还要提供一个目标端口（destination port），以指明数据包传输到远程机器上之后应该交给谁处理

0~1023 之间的端口都是保留端口，用于一些知名服务

比如端口 80 是 Web 服务器使用的端口，所以远程客户能找到 Web 服务器进程

每个出境 TCP 消息都包含一个源端口和一个目标端口

这两个端口合起来标识了客户机和服务器两端正在使用该连接的一对进程

映射源端口

利用源端口（source port）字段，可以解决映射问题。任何时候当出境数据包进入 NAT 盒子，其源地址 10.x.y.z 被客户的真实IP地址所取代，而且 TCP 的源端口字段被一个索引值取代，该索引值指向 NAT 盒子的地址转换表中的 65536 个表项之一

该表项包含了原来的IP地址和原来的源端口

最后，NAT 盒子重新计算 IP 头和 TCP 头的校验和，并将校验和插入到数据包中
之所以要替换 source port 域，是因为来自机器 10.0.0.1 和 10.0.0.2 连接可能碰巧使用了同一个端口，比如都使用了 5000，所以仅使用 source port 还不足以唯一性地标识发送进程

当一个数据包从 ISP 到达 NAT 盒子时，source port 从TCP头中提取出来，并被用作为索引值查找 NAT 盒子的映射表。找到对应的表项后，从该表项提取出内部 IP 地址和原来的TCP source port，并将它们插入到数据包中。然后重新计算 IP 和 TCP 校验和，并插入到数据包中。最后将该数据包传递给客户内部的路由器，它使用 10.x.y.z 地址进行正常的路由。

类比为电话和接线员

NAT 问题

NAT 违反了 IP 的结构模型
NAT 打破了 Internet 的端-端的连接模型，即任何一个主机可在任何时间给任何一台其他主机发送数据包
NAT 将 Internet 从一个无连接网络改变成一个面向连接网络特有的形式
NAT 违反了最基本的协议分层规则：第 $k$ 层不应该对第 $k+1$ 层在本层的有效载荷字段中放什么作任何假设
Internet 上的进程并不一定必须使用 TCP 或 UDP
有些应用以规定的方式使用多个 TCP/IP 连接或者 UDP 端口

标准的文件传输协议（FTP, File Transfer Protocol）在数据包正文插入 IP 地址，接收方正文中提取出这些地址，并使用它们。NAT 对此一无所知

由于 TCP source port 字段 16 位长，至多只有 65536 台机器可以被映射到同一个 IP 地址上（前 4096 个端口被保留用作特殊的用途）

IPv6

目标

即使地址空间的分配效率不高，也能支持几十亿台主机（Support billions of hosts, even with inefficient address allocation）
降低路由表大小（Reduce the size of the routing tables）
简化协议，使路由器更快速地处理数据包（Simplify the protocol, to allow routers to process packets faster）
提供更好的安全（认证和隐私）（Provide better security （authentication and privacy））
更加关注服务类型，特别是针对实时数据（Pay more attention to the type of service, particularly for real-time data）
辅助指定范围内的组播（Aid multicasting by allowing scopes to be specified）
主机漫游时无需改变地址（Make it possible for a host to roam without changing its address）
允许协议向未来演进（Allow the protocol to evolve in the future）
允许新老协议共存多年（Permit the old and new protocols to coexist for years）

主要的 IPv6 头

4 bit 版本（Version）：IPv6 是 6 （0110），IPv4 是 4
8 bit 区分服务（Differentiated services）
20 bit 流标签（Flow label）: 最初创建用于提供实时应用程序特殊服务
16 bit 有效载荷长度（Payload length）
8 bit 下一个头（Next header）
8 bit 跳数限制（Hop limit）: IPv4 的 TTL
128 bit 源地址（Source address）
128 bit 目标地址（Destination address）

IPv6 地址

16 个字节被分成 8 组 4 个十六进制数字，组之间用冒号隔开

8000:0000:0000:0000:0123:4567:89AB:CDEF
十六进制不区分大小写

优化方法：

在一个组内可以省略前导 0，0123 可以写成 123
16 个 0 构成的一个或多个组可以用一对冒号来代替，但 :: 只能出现一次，8000:123:4567:89AB:CDEF
IPv4 地址现在可以写成一对冒号再加上老式的点分十进制数，比如 ::192.31.20.46

扩展头

用于大型数据报（巨型报）的逐跳扩展头

路由扩展头

IPv4 和 IPv6 的转换

双栈路由器（dual stack）
隧道（tunelling）

Internet 控制协议

IP 协议依靠多种辅助协议来实现必要的控制和路由功能：

控制功能 ICMP
组管理 IGMP
设置路由表 RIP, OSPF, BGP, PIM, …

ICMP —— Internet 控制消息协议

Internet Control Message Protocol

路由器严密监视 Internet 操作，当路由器在处理一个数据包的过程中发生了意外，可通过 ICMP 向数据包的源端报告有关时间

ICMP 还可以用来测试 Internet

每一种 ICMP 消息类型都被封装在一个 IP 数据包中

ICMP 的目标

错误报告
简单请求

分层

从分层的角度来看，ICMP 是一种独立的协议，位于 IP 之上并使用 IP 传输消息
实际上，ICMP 是 IP 的组成部分，所有 IP 模块必须支持 ICMP 协议
ICMP 数据报封装在 IP 数据报中，IP 按照与 TCP 和 UDP 数据报相同的方式处理 ICMP

消息封装

ICMP 消息被封装为 IP 数据报

ICMP 消息格式

4 byte 头（header）

1 byte 类型（Type）: ICMP 消息的类型
1 byte 码（Code）: ICMP 的子类型
2 bytes 校验和（Checksum）: 和 IP 头校验和类似，校验和计算整个 ICMP 消息
- 如果没有格外的数据，4 bytes 将被设置为 0
- 每个 ICMP 消息至少 8 bytes 长

ICMP 消息类型

信息消息，发送方向另一台机器（主机或网关）发送请求并且期待回答
- 例如，主机可能想知道网关是否还活着
错误指示消息，主机或网关上的IP软件在处理 IP 数据报时遇到问题
- 例如，它可能无法将数据报路由到其目的地，或者可能不得不丢弃一个帧

ICMP 请求消息

Request 主机发送给路由或另一个主机
Reply 返回给发送请求的主机

ICMP 请求举例

ICMP 的请求 / 响应目的

ICMP请求回显（echo request）和回显响应（echo reply）对网络调试很有用

如果机器 A 向机器 B 发送请求回显消息，机器 B 需要用回显响应来响应请求
大多数系统提供发送和接收 ICMP 回显消息的应用程序
在 UNIX 中，ping 允许用户检查机器是否可达并正常工作
因为 ICMP 消息与其他 IP 数据报一样处理，ICMP 回显消息测试任何主机的可达性。另外，因为 ICMP 是 IP 的组成部分，所有主机和网关必须实现 ICMP

请求举例 —— Echo

ping 由内核直接处理
每个 ping 都被转换成 ICMP Echo Request
每个被 ping 的主机都回应一个 ICMP Echo Reply

时间戳消息

ICMP 时间戳消息用于估计机器之间的传输延迟并同步时钟

包括接受和发送时间戳允许发送主机确定发送和处理请求的事件比例
通过对几条消息的测量值进行平均，发送方可以估计本地时钟和远程机器之间的偏移量
注意：将局域网内所有机器的时钟同步到几毫秒以内是完全 ok 的
测量网络的性能

请求举例 —— 时间戳

系统（主机或路由器）询问另一个系统当前时间
时间以当天凌晨UTC（协调世界时）后的毫秒为单位测量
发送方发送请求（request），接收方响应回应（reply）

消息格式

错误消息

ICMP错误消息报告错误状况
通常在丢其数据报时发送
错误消息通常从ICMP传递到应用程序

消息格式

ICMP 错误消息包含整个 IP 头和有效载荷的前 8 个字节（通常为 UDP/TCP ）

经常使用的 ICMP 错误消息

目的不可达的子类型

错误消息举例 —— 端口不可达

RFC 792：如果在目标主机中，IP 模块由于指定的协议模块或进程端口未处于活动状态而无法传送数据报，目标主机可能会向源主机发送目标不可达消息

Windows控制台命令 —— tracert

TTL 递增，发现从主机到目的地的路径上的 IP 地址
路由器返回超时消息

ARP —— 地址解析协议

Address Resolution Protocol

每一块网络接口卡（NIC）在出厂时配置了一个唯一的 48 位以太网地址

协议数据单元封装

以太网II 中的 TCP/IP 数据包

ARP 与 RARP

Internet 基于 IP
数据链路协议（以太网，FDDI，ATM）可能有不同的（MAC）地址

ARP 和 RARP 协议执行 IP 地址和 MAC 地址之间的转换

讨论广播 LAN 的 ARP，特别是以太网 LAN

映射问题

将 Internet 地址映射到物理地址的问题称为地址解析问题

每个以太网设备有自己唯一号码，更换网卡就更换了物理地址
物理地址 6 bytes 长，太大而无法在 Internet 地址内复用
可以在不中断服务的情况下降新机器添加到网络中
但是，添加主机不应该要求现有重新配置现有主机以通知新机器的加入

ARP 地址转换

ARP 请求（Request）

广播询问哪个路由137的硬件地址

ARP 回应（Reply）

路由137响应请求，返回的数据中包含自己的硬件地址

ARP 包格式

ARP 举例

ARP 缓存

由于为每个 IP 数据报发送 ARP 请求/回应效率低下，主机维护当前 ARP 缓存，20 分钟后过期

ARP 代理

主机或路由器响应从连接的另一个网络上的主机的 ARP 请求

关于 ARP

一些系统（包括Linux）上，主机定期根据 ARP 缓存发送 ARP 请求，刷新 ARP 缓存内容，但也增加了流量

免费 ARP（gratuitous ARP）: 一个主机发送一个 ARP 请求自己的 IP 地址

网络上应该不会有任何应答，这个广播数据包的副作用是其他主机在 ARP 缓存中加入一个映射表项
如果意外地收到了一个应答，说明两台机器被分配了相同的 IP 地址
检测 IP 地址是否已经被分配

ARP 的脆弱性

由于 ARP 没有对请求或响应进行认证，因此可以伪造 ARP 请求和响应
ARP 是无状态的：可以在没有相应的 ARP 请求的情况下发送 ARP 响应
根据 ARP 协议规范，接收 ARP 数据包的节点（请求或响应）必须使用源字段中的信息更新其本地 ARP 缓存，如果接收节点已在其ARP缓存中具有源IP地址的条目。（适用于 ARP 请求数据包和 ARP 响应数据包）
利用

一个伪造的 ARP 请求或响应可以用来更新伪造远程系统中的 ARP 缓存条目（ARP Poisoning 中毒）
可以用来将 IP 流量重定向到其他主机

分层：不同的视角

Windows控制台命令 —— arp

1
2
3

-a   显示所有ARP缓存
-d * 删除所有ARP缓存
-s   加入一条静态条目

DHCP —— 动态主机配置协议

Dynamic Host Configuration Protocol

采用 DHCP 时，每个网络必须有一个 DHCP 服务器负责地址配置

手动配置 TCP/IP 的问题

管理开销

需要跟踪所有 IP 分配
需要手动输入 IP 设置

坏的或重复的 IP 地址

将出现错误

在子网间移动

需要手动更改 IP 设置

用 DHCP 来配置 TCP/IP

DHCP 的好处

集中管理
自动为客户端提供地址信息
更容易排查故障

DHCP 可以提供的设置

网络适配器的IP地址
子网掩码
默认网关
其他参数 —— DNS, WINS, …

BOOTP RFC 951/1048/1084

bootstrap 协议（BOOTP）

从 1985 年起
主机可以在启动时配置其 IP 参数
3 个服务
- IP 地址分配
- 检测服务器的 IP 地址
- 由客户机加载和执行的文件的名称（启动文件名）

不仅分配 IP 地址，还分配默认路由器、网络掩码等
作为 UDP 消息发送（UDP 端口 67（服务器）和 68（主机））

DHCP

动态主机配置协议

从 1993 年起
BOOTP 的扩展
使用和 BOOTP 相同的的端口
扩展
- 支持 IP 地址的临时分配（租赁lease）
- DHCP 客户端可以获取操作所需的所有的 IP 配置参数
DHCP 是动态分配 IP 地址的首选机制
DHCP 可以与 BOOTP 客户端进行互操作

路由器的 DHCP 中继

DHCP 利用了 BOOTP 定义的消息协议和配置技术，包括分配 IP 地址的能力
这种相似性允许现有路由器在子网之间中继 DHCP 消息 / BOOTP 消息
因为这个，单个 DHCP 服务器可以处理多个子网的 IP 寻址

BOOTP 交互

BOOTP 可以用来从无盘工作站下载内存映像（memory image）
分配给主机的 IP 地址是静态的

简化的 DHCP 交互

BOOTP/DHCP 消息格式

许多 DHCP 信息是以选项的形式被发送的

子网掩码、名称服务器，路由器，主机名，域名，转发开/关，默认 IP TTL，广播地址，静态路由，以太网封装，DHCP 消息类型，DHCP 更新时间，DHCP 重新绑定，时间 SMTP 服务器，SMTP 服务器，…

DHCP 选项域格式

客户机-服务器通信

IP 租赁

发现（Discover）和提供（Offer）

当没有 DHCP 服务器在线时

客户机等待 1 秒钟
客户机在第 9,3,16 秒重新广播，之后随机间隔广播
客户机每 5 分钟重试一次

IP 租赁更新

客户机广播 DHCP REQUEST 消息
- 当租赁期过了 50% 的时候
DHCP 服务器返回 DHCP ACK
当客户机尝试租先前的 IP 地址时，就会出现 DHCP ACK
- IP 地址不再可用
- 客户机移动到另一个子网
- 如果收到了一个 DHCP ACK，客户机就进入请求 IP 租赁的过程

IP 租赁释放

由客户端发起释放（RELEASE）

分层视角

确定配置选项
IP 地址和掩码始终是 IP 配置的一部分
其他选项包括
- 默认网关
- 域名系统（DNS）服务器
- Windows Internet 名称（WINS）服务器
- 基于 TCP/IP 名称解析的 NetBIOS

Windows命令行 —— ipconfig

/?           Display help message
/all         Display full configuration information
/release     Release the IP address for the specified adapter
/renew       Renew the IP address for the specified adapter
/flushdns    Purges the DNS Resolver cache
/registerdns Refreshes all DHCP leases and re-registers DNS names
/displaydns  Display the contents of the DNS Resolver Cache.

标签交换和 MPLS *

ISP 用来在它们的网络之间移动 Internet 流量

多协议标签交换（MPLS）在每个数据包前面增加一个标签，路由器根据数据包标签而不是数据包目的地址实施转发

2.5 层协议

MPLS 介于 IP 网络层协议和 PPP 链路层协议之间

不是一个真正的第 3 层协议，因为它依赖 IP 或其他网络层地址来建立标签路径
不是一个真正的第 2 层协议，因为它既可以在多跳之间转发数据包，也不是一条单一链路

标签交换路由器（LSR, Label Switched Router）
标签边缘路由器（LER, Label Edge Router）
转发等价类（FEC, Forwarding Equivalence Class）

OSPF —— 内部网关路由协议

域内路由（intradomain routing） - 内部网关协议（IGP, interior gateway protocol）

域间路由（interdomain routing） - 外部网关协议（EGP, exterior gateway protocol）

Internet 上的内部网关协议

RIP 路由信息协议（Routing Information Protocol）

采用距离矢量的设计思想，基于分布式 Bellman-Ford 算法，继承自 APPANET
在小型网络中运作良好
无穷计数问题，收敛速度较慢

OSPF 开放最短路径优先（Open Shortest Path First）

一个链路状态协议，1990 年成为标准，IETF
借鉴了 IS-IS （中间系统到中间系统，已成为 ISO 标准）

设计要求

算法必须发表在公开文献中
新的协议必须支持多种距离度量，包括物理距离、延迟等
必须是一个动态算法，能够自动而且快速地适应网络拓扑变化
必须支持基于服务类型的路由。新的协议必须能够区分实时流量和其他流量，并使用不同的路由方法
必须实现负载均衡，即把负载分散到多条线路上
必须支持层次化系统，不要求路由器知道完整的拓扑结构也能很好地工作
要求提供适度的安全性
对于那些通过隧道连接到Internet的路由器，新协议也必须能够对它们进行处理

OSPF 支持 3 种网络

两个路由器间的点到点链路（如 SONET）
多路访问广播网络（大多数局域网）
多路访问网络（包交换的广域网）（multiaccess）

这里的多路访问网络是一个拥有多个路由器的网络，每个路由器都可以直接与其他路由器通信，这是一种常见的 LAN/WAN 属性

OSPF 的工作方式本质上是对一张图进行操作：将一组实际网络、路由器和线路抽象到一个有向图中，图中的每条弧有一个权值（距离、延迟）
两台路由器之间的点到点连接可以用一对弧来标识，每个方向上一个，两个方向上的权值可以不同。广播（multiaccess）网络用一个节点表示，加上网络上每台路由器用一个节点表示

等价成本多路径（ECMP, Equal Cost MultiPath）

有可能协议会发现多个同样短的路径，OSPF 记住最短路径集合，并在报文转发期间把流量分摊到这些路径上

OSPF 区域（area）

将庞大的 AS 划分成编号的区域
每个区域是一个网络，或者一组互连的网络
区域不能重叠，但是也不必面面俱到，也就是说有些路由器可能不属于任何一个区域
全部属于一个区域的路由器称为内部路由器（internal router）
区域是单个网络的一种泛化形式，在区域外部能见到的是它的目的地而不是拓扑结构

OSPF 骨干区域（backbone area）

每个 AS 有一个骨干区域，称为 0 号区域
该区域中的路由器称为骨干路由器（backbone router）
所有的区域都必须连接到骨干区域，连接方式有可能会通过隧道进行
每个连接到两个或更多区域的路由器称为区域边界路由器（border router），它必须是骨干区域的一部分
- 区域边界路由器的工作任务：概括本区域的目的地信息并注入到与自己连接的其他区域。这种概括包括成本信息，但不包括区域内部的所有拓扑细节
- 传递成本信息可以使得其他区域内的主机找到进入本区域的最好区域边界路由器
- 不传递拓扑信息可以减少流量和简化其他区域路由器的最短路径计算

存根区域（stub area）

如果只有一个边界路由器通往区域外，甚至路由信息概要都不需要传递
通往该区域外部目的地的路由总是被指令“前往边界路由器”，这类区域称为存根区域（stub area）

AS - Autonomous system 自治域

AS 边界路由器（AS boundary router）

把通往其它 AS 的外部路由注入到本区域
然后外部路由就可呈现为可以通过 AS 边界路由器可达的目的地，该路由器当然会有某种成本
外部路由可以注入一个或更多个 AS 边界路由器

自治域、区域和各种路由器之间的关系

链路状态算法

每个区域内的路由器由相同的链路状态数据库，并运行相同的最短路径算法
- 其主要工作是计算从自身出发到每个其他路由器和整个AS内网络的最短路径
- 根据距离或其他属性进行计算

OSPF 路由

区域内（intra-area）
区域间（inter-area）
- 从源所在区域到骨干区域
- 穿过骨干区域到目标区域
- 到达目的地
跨域（inter-AS）

OSPF 路由步骤：

当一台路由器启动时，它在所有点到点线路上发送 HELLO 消息，并且通过 LAN 将 HELLO 消息组播到一个包含所有其他路由器的组。每台路由器从应答消息中得知谁是自己的邻居。同一个 LAN 上的路由器都是邻居
在邻接的路由器之间相互交换信息

OSPF 要求从每个 LAN 中选举一台路由器作为指定路由器（designated router）
指定路由器与本 LAN 上的所有其他路由器都是邻接的，并且与它们交换信息
实际上，它就是一个代表本 LAN 的单个节点

路由状态更新

每台路由器周期性地泛洪 LINK STATE UPDATE 消息到它的每台邻接路由器
- 这些消息给出了它的状态信息，并提供了拓扑数据库用到的成本信息
这些泛洪消息需要被确认，以保证它们的传输可靠性
- 每条消息都有一个序号，路由器据此判断一条入境 LINK STATE UPDATE 消息的新旧
当一条线路启用、停止或其成本发生改变时，路由器也要发送 LINK STATE UPDATE 消息
所有这些消息都是以 IP 数据包的形式直接被发送出去

通过泛洪法，每个路由器把它与其他路由器和网络的链路以及链路成本告诉给它所在区域中的所有其他路由器。这些信息使得每台路由器都可以构建出它所在区域的拓扑图，并计算最短路径

骨干区域也是这样工作的
而且，为了计算出从每个骨干路由器到每个其他路由器的最佳路由，路由器还要接受来自每个区域边界路由器的信息。最佳路由信息又被传回到区域边界路由器，区域边界路由器再将这些信息在本区域内广播。利用这些信息，内部路由器可以选择通往区域外目的地的最优路由，包括通往骨干区域的最佳出口路由

OSPF 数据包的头格式

OSPF 的 5 类消息

BGP —— 边界网关路由协议*

在一个 AS 内部，推荐使用的路由协议是 OSPF 和 IS-IS

在 AS 之间，则可以使用 BGP（Border Gateway Protocol, 边界网关协议）

在自治域之间路由（interdomain routing）
BGP 考虑政治、安全和经济因素

BGP 政策

政策通常被手动配置到每个 BGP 路由器中（或包含某种脚本）。它们不是协议本身的一部分
可能的路由限制

教育网路不承载商业流量
五角大楼发出的流量永远不要走经过伊拉克的路径
使用 TeliaSonera 而不用 Verizon，因为前者更便宜
不要使用澳大利亚的 AT&T，因为它的性能太差
起止于苹果的流量不应该经过谷歌中转

路由策略

BGP 基础

BGP 是距离矢量协议的一种形式，但它与域内距离矢量协议（如 RIP ）有很大的不同

用策略而不是最小距离来选择使用哪些路由
BGP 不仅维护到每个目的地的成本，而且每个 BGP 路由器还跟踪所使用的路径
- 路径由下一跳路由器和一系列 AS 或 AS 路径组成，这些自治系统或者相应的路径序列是该路由器必须遵守的
- 这种方法称为路径矢量协议（path vector protocol）

一对 BGP 路由器通过建立 TCP 连接而相互通信

这种方法既提供了可靠的通信，也隐藏了正在穿越的网络细节

BGP 路由通告的传播

中间的 ISP 为左右两个 ISP 提供中转服务

路由器如何为每个目的地选择使用哪条路由

三种策略

优先选择通过对等网络的路由，而不是通过中转提供商的路由
将“短路径更好”作为默认规则
优先选择具有 ISP 内最小成本的路由
- 称为提前退出（early exit）或热土豆路由（hot-potato routing）
- 副作用是使得路由呈现不对称性

Internet 组播*

IP 用 D 类 IP 地址来支持一对多通信，或组播（multicasting）

每个 D 类地址标识了一组主机
总共有 28 位可用于标识组播组，因此网络中可同时并存 250 万个组
IP 地址 224.0.0.0/24 范围内的地址保留用作本地网络组播

ip	description
224.0.0.1	All systems on a LAN
224.0.0.2	All routers on a LAN
224.0.0.5	All OSPF routers on a LAN
224.0.0.251	All DNS servers on a LAN

IGMP (RFC 3376)

Internet 组管理协议（IGMP, Internet Group Management Protocol）

一个进程要求它的主机加入到某个指定的组中，它也可以要求它的主机离开该组
每台主机跟踪记录当前它的哪些进程属于哪些组
- 当一台主机上的最后一个进程离开一个组时，该主机就不再属于这个组
大约每分钟一次，每个组播路由器向它所在LAN上的所有主机发送一个查询数据包（使用本地组播地址 224.0.0.1 ），要求这些主机报告自己当前属于哪些组
- 组播路由器可能与标准的路由器在同一台机器上，也可能分属两台机器
每个主机收到查询消息后，返回一个响应包，其中包括了自己感兴趣的所有 D 类地址
- 查询包和响应包都使用了 IGMP 协议

PIM

协议独立组播协议（PIM, Protocol Independent Protocol）

几个组播路由协议中的任何一个都可用于建立组播生成树，该树给出了一条从发送方到组内所有成员的路径
AS 内主要使用 PIM
密集模式 PIM
- 修剪的逆向路径转发树
- 成员分布在网络各处，如数据中心把文件分发给多个服务器
稀疏模式 PIM
- 类似于核心树
- 内容提供商向它 IP 网络上的用户组播 TV
- 变体：特定源组播 PIM（Source-Specific Multicast PIM）可用来优化只有一个发送方的情况