一、网络层设计的基本问题

网络层需要解决的问题：

• 如何将源端数据包送到接收方？

基本问题：

• 如何选择好的传输路径；
• 如何选择路由器，避免拥塞；
• 如何连接不同的网络；

网络层运行环境：

网络层提供给传输层的服务：

• 向上提供的服务应独立于实现；
• 屏蔽路由器数量、类型和拓扑；
• 统一编址方案；

无连接和有连接服务：

• 无连接：

  
  • 数据报网络
  • 路由表
  • 路由算法

• 面向连接：

  
  • 虚电路
  • 标签交换

无连接和面向连接的比较：

问题	面向连接	无连接
电路建立	不需要	需要
寻址	每个包包含全部的源和目的地址	每个包包含简短的VC号
状态信息	路由器不保留连接状态	针对每个连接，每条VC都需要路由器保存其状态
路由方式	每个数据包单独路由	建立VC时选择路由，所有包都遵循该路由
路由器失效的影响	没影响，除了路由器崩溃时丢失的包	穿过故障路由器的所有VC中断
服务质量	困难	容易，如果在建立VC时有足够的资源
拥塞控制	困难	容易，如果在建立VC时有足够的资源

二、路由算法

• 路由和转发：

  • 转发：数据包到达时采取的动作；
  • 路由：决定使用哪一条路径；

• 路由算法需要满足的特性：

  • 正确性、简单性

  • 鲁棒性：应对主机、路由器、线路的失败，拓扑变化；

  • 稳定性：算法是否能快速收敛；

  • 公平性和有效性：通常是相互矛盾的目标；

    

路由算法分类：

• 非自适应算法：不会根据当前测量或估计的流量和拓扑结构调整路由决策；又叫做静态路由；
• 自适应算法；又叫做动态路由；

2.1 最优化原则

如果路由器J在从路由器B到M的最优路径上，那么从J到M的最优路径也遵循同样的规则；

汇集树：从源节点到所有指定目标的最优路径的集合构成了一棵以源节点为根的树

2.2 最短路径算法：Dijkstra算法

功能：找到源节点和其他所有其他节点之间的最短路径；

限制条件：所有边的权重为正；

算法初始化：

1. dist: 表示从源节点s到其他节点的距离，初始为 dist(s)=0, dist(v)=∞；
2. weight(i, j)：表示节点i与节点j之间的权重；
3. Q: 初始化为包含图中所有节点的队列。算法执行完毕后，Q为空；
4. S: 初始化为空，包含所有算法访问过的节点。运行完毕后包含所有网络中的节点。

算法执行流程：

1. 如果Q不为空，则从Q中取出一个有最小dist值的节点，用v表示（第一个选中的节点一定是源节点）；
2. 将节点v从队列Q中去掉;
3. 把节点v放入集合S中；
4. 更新节点v的所有邻居节点的距离，对于邻居节点u，更新方式如下
   1. 如果 dist(v) + weight(u, v) < dist(u)，则说明对于邻居节点u，存在更短的可达路径，则更新dist(u) = dist(v) + weight(u, v);
   2. 否则，不更新；
5. 遍历完Q中所有的节点，直到Q为空。

算法伪代码：

时间复杂度：最坏情况：O(n2)，其中n为图中节点个数。

Dijkstra的最优性：

• 最短路径的子路径也一定是最短路径；
• Dijkstra算法是贪婪算法，每当节点v被放入集合S时，*dist[v]*都是v到源节点s的最短距离；

2.3 泛洪算法

机制：

• 每个路由器只有本地信息，而不是网络全貌，即路由器没有边权重信息；
• 将每一个入境数据包发送到除了到达线路之外的所有出境线路；

问题：产生重复的数据包；

解决方案：

• 增加跳计数器字段；
• 路由器跟踪转发过的数据包，避免重复转发；

优势：

• 确保数据包能够传送到网络中的每个节点；
• 利于广播

用途：

• 泛洪算法可以作为其他路由算法的基本构件，用来测量线路权重等信息；

2.4 距离矢量算法

动态算法：

• 实时更新网络中存在的路径和权重，发现新加入的节点；
  • 距离矢量路由；
  • 链路状态路由；

距离矢量路由：

• 最初ARPANET使用的算法；

过程：

1. 节点每隔固定时长向邻居发送一个列表，该表包含它到每个目标的延迟估计值；
2. 节点根据自己到邻居节点的延迟，以及邻居节点到其他节点的延迟，估算出自己到全网任意节点的延迟；

举例：

1. 图b的前4列代表J从邻居节点接收到的延迟矢量；
2. 估算自己到邻居节点A, I, H, K的延迟分别为8, 10, 12, 6；
3. 则可获得第5列的路由表；

无穷计算问题：

• 整个网络最佳路径的寻找过程必须收敛；
• 距离矢量算法的收敛速度可能很慢；
• 好消息传播的块，坏消息传播的慢；
  • 好消息：
    • A刚开始停机，则所有其他节点认为A的距离为无穷大（黑点）。A开机后，通过四次路由表交换，所有其他节点知道了自己到A的距离；
    • 
  • 坏消息：
    • 节点A宕机，与B的距离变为无穷大，而B会尝试通过C来达到A，以此类推。需要无穷多次路由表交换，才能使得B,C,D,E四个节点把与A的距离设置为无穷大；
    • 
• 问题核心：当X告诉Y它有一条通往某个地方的路径，Y无从知道自己是否已经在这条路径上；

2.5 链路状态路由

避免无穷计算问题，已经成为Internet应用最为普遍的算法；

该算法将完整的拓扑结构发送给每一个节点，节点运行Dijkstra算法找到从本地到每一个其他节点的最短路径；

算法过程：

1. 发现邻居
   1. 节点启动时，首要问题是找出哪些节点是它的邻居；
   2. 发送Hello数据包，线路另一端应答;
   3. 要求：所有节点有唯一的名字；
2. 设置链路成本；
   1. 与带宽成反比或延迟等；
   2. 可以发送ECHO数据包，要求对方立即返回，测量往返时间除以2；
3. 构造链路状态包
   1. 发送方标识符：说明是哪个节点发送的链路状态包
   2. 序号：说明是第几个包
   3. 年龄：避免信息过时
   4. 邻居列表以及到这些邻居的成本
4. 分发链路状态包；
   1. 泛洪；为了控制泛洪的规模，序号随着每一个新数据包的发出而逐一递增，如果接收端看到的数据包的序号小于当前所看到过的来自该原路由器的最大序号，即丢弃；
   2. 年龄字段：随着时间的增长而递减，降为0后，该路由信息被丢弃；
      • 避免错误/过时的路由信息的影响；
5. 计算新路由
   1. 在本地运行Dijkstra算法，构建出从本地出发到所有可能目标的最短路径；
   2. 复杂度高于距离矢量路由；

2.6 层次路由

随着网络规模增长，路由表变长；

• 对于大型网络，10000个路由器，每个路由器都需要10000个表项，增大了路由查询的困难和存储资源消耗；
• 路由器划分区域，组成簇，区，群等；
• 720个路由器=》720个表项；均匀分成24区，每区30个路由器=》53个表项。
  

开销：路由长度增长；

• 层数和路由长度的增长之间有折中效应；
• （Kamoun 和 Kleinrock 1979）发现，对于N个路由器的网络，最优的层数是ln N层

2.7 广播路由

主机需要给其他多个或者全部主机发送消息，如直播等

泛洪；

基于汇集树的方法：逆向路径转发

• 汇集树：基于最短路径组成的树，没有环路
• 检查数据包的到达路径是否是在生成树上，如果是，保留；不是，丢弃

2.8 组播路由

主机把数据发送给几个其他主机；

• 接收方个数相对于整个网络规模很小（区别于广播）；
• 基于剪裁生成树实现，把不通往组成员的链路从树中删掉；

2.9 移动主机路由

针对笔记本电脑等移动设备：

• 路由一个数据包到移动主机，首先要找到这个主机；
• 每个主机都有一个永久的家乡位置，家乡位置的一个主机做为家乡代理
• 

2.10 自组织网络路由

路由器本身也是移动的场景；

• 地震现场紧急救援、战场上的军事车辆等，又称为ad hoc网络；
• 主要挑战：网络拓扑不断变化；
• AODV（按需距离矢量路由算法）

路由发现

• 只有当某个节点要发数据给目标节点的时候才找路径，使用泛洪方法；
• 泛洪数据包到达目标节点后，目标节点生成路由应答包，反向传输，构造路由。

路由维护；

• 节点周期性的向周围的邻居发送Hello数据包，如果邻居没有回复，则节点认为该邻居离开，以此更新路由表。