第四章 网络层(4)-路由协议、选路算法

明日无尘

路由协议概述

路由器提供了异构网互联的机制，实现将一个网络的数据包发送到另一个网络。而路由就是指导IP数据包发送的路径信息。路由协议就是在路由指导IP数据包发送过程中事先约定好的规定和标准。
路由表要求



层次路由

当因特网过大时，路由器无法存储数亿主机的选路信息，路由表广播会导致可用数据带宽低。
因此可以将因特网按层次划分出子网，路由也相应划分出不同的自治系统（AS），每一个自治系统都运行自己内部的选路协议。
划分层次后，每个路由器中都需要保存两个转发表，一个是AS内部选路算法，另一个是AS间选路算法。
因特网是ISP（Internet服务供应商）的网络，每个ISP都有它自己的路由器网络，通常一个ISP中的路由器以及互联他们的链路构成一个AS，也有某些ISP会划分出多个AS。
自治系统间路由器的任务

假设AS1中的路由器收到一个数据报，其目的地址在AS1之外


AS1的任务：

• 需要知道通过AS2可以到达哪些目的地，通过AS3可以到达哪些目的地
  
• 将这些可达性信息向AS1中的所有路由器传播
  

场景1：从源到目标仅有一条路可选


假设AS1从AS间选路协议知道子网X经AS3 (网关1c) 可达，但是通过AS2不可达。

• AS1向它的所有路由器广播该可达信息。
  
• 路由器1d 知道，它的接口I在到路由器1c的最低费用路径上。
  
• 从而路由器1d将表项 (X,I)放入其转发表。
  

场景2:从源到目标有多条路可选


现在假设AS1知道子网X可以通过 AS3和AS2到达。

• 为了配置转发表, 路由器 1d 必须决定通过哪个网关路由器转发报文（1b或1c）。
  
• 这也是自治系统间选路协议必须解决的问题。
  
• 热土豆选路：将报文通过最低费用接口I发送到最近路由器。(x，I)放入1d的路由转发表。
  

就像烫手山芋一样，尽快抛出去
链路状态选路算法和OSPF协议

本质上为图问题的求解，将网络拓扑结构映射为图
OSPF：一种链路状态协议，使用洪泛链路状态信息和Dijkstra最低开销路径算法。用于因特网中自治系统内部的路由选择。
链路状态选路算法（LS）

性能目标：基于路径成本最优
符号定义:

• c(x,y): 从节点x到节点y的链路费用；如果x和y不是直连的，则 c(x,y) = ∞
  
• D(v): 随着算法进行本次迭代，从源节点到目的v的最低费用路径的费用
  
• p(v): 从源节点到v沿着当前最低费用路径的前一节点
  
• N': 节点子集。v在N'中，从源节点到路径的最低费用路径已知
  

每一行挑选D(v)最小的节点加入N'，然后对行数据进行更新，得到下一行的D(v)、p(v)
Dijkstra's(迪克斯特拉)算法

链路状态选择算法用的是迪克斯特拉算法，也就是最短路径生成树算法
前提-所有节点都知道网络拓扑和链路费用

• 通过链路状态广播获得信息
  
• 所有节点具有该网络的同一个完整的视图
  

目标-产生某节点的转发表

• 计算从某节点到网络中所有其他节点的最低费用
  
• 为该节点提供转发表
  

算法复杂性

• 对于第一次迭代：需要搜索所有的n个节点以确定出节点w，w不在N'中且具有最低费用。
  
• 在所有迭代中需要搜索的节点总数为n(n+1)/2 ，所以链路状态算法在最差情况下复杂性为O(n2)。
  
• 该算法的一种更复杂的实现，使用一种叫做堆的数据结构，其计算复杂性为O(nlogn)。
  

Dijkstra's(迪克斯特拉)算法可能存在的问题



对于流量敏感型链路来说，可能出现震荡现象。
比如C结点向A结点发出数据，B结点认为流量过多，于是重新计算选路变为转发至D再给A，然而接着D可能也会判定流量过多，再次重新计算选路转发至B再给A。
震荡解决方案

强制链路费用不依赖于所承载的流量

• 无法解决高拥塞的问题，不可接受
  

确保所有的路由器不同时运行LS算法

• 因特网上的路由器能够自同步
  
• 随机化路由器发送链路通告的时间
  

OSPF保证所有节点知道网络拓扑和链路费用的方法

洪泛法：本路由器向本AS中所有路由器发送信息。
消息内容：与本路由器相邻的所有路由器的链路状态。
发送时机：当链路状态发生变化时开始发送。
距离向量选路算法和RIP协议

在OSPF的路由交换过程当中，结点之间需要两两进行路由协议交换，而距离向量选路算法（Distance-Vector）中，只需要在相邻的结点之间交换路由协议。
RIP协议（Routing Information Protocol）是一个典型的使用距离向量选路算法的协议。
Bellman-Ford方程

d_{x}\left( y \right)=min_{v}\left\{ c\left( x,v \right)+d_{v}\left( y \right) \right\}
d_{x}\left( y \right) 是从结点x到结点y的最低开销路径的开销，v是x的某一个相邻结点， c\left( x,v \right) 是x到v的直接距离


RIP路由选择环路

链路状态改变时的特点：
好消息传的快：当某一结点与它邻居的链路开销降低时，该结点会更新其距离向量，如果最低开销路径的开销发生变化，则该结点会通知新的距离向量，该情况下DV算法可以很快迭代至静止状态。
坏消息传得慢：可能出现路由选择环路，导致无穷计数

• 初始状态下z至x最小开销为5。
  
• 某一时刻x与y距离变为60，则y按照原本的路由表中y-z为1、z至x最小开销为5的记录（因为y不知道z至x的最小开销路径其实是需要通过y自己的），所以认为y至x最小开销应变为1+5=6，然后将此距离表转发给z。
  
• z收到新的距离表后，z按照原本的路由表中z-y为1、z至x最小开销路径需要先路过y的记录，认为此时z至x最小开销为1+6=7，更新距离表并发给y。
  

如此会导致开销计算出现路由选择环路，需要进行长时间的迭代。
DV算法毒性逆转

在原本情况中，z通告给y的路由表应表示z至x的最小开销为5，但在毒性逆转中，如果z至x的最小开销路径第一步是经过y，那么z通告给y的路由表则表示z至x的最小开销为 \infty ，这是一个”善意的小谎言“。

• 某一时刻x与y距离变为60，因为y以为z至x的最小开销为 \infty ，因此不会考虑让y至x的路径通过z，而是直接让y至x的最小开销刷新为60，然后把此新消息通告给z。
  
• z收到后会更新z至x的最小开销为50，同时因为此最小开销路径不再第一步经过y，因此不会再撒前面所说的谎，直接告诉y，z至x的最小开销为50。
  
• y收到后则可更新y至x的最小开销为51。
  

事实上毒性逆转并未真正解决无穷计数问题，当涉及到更多结点时，路由选择环路无法被毒性逆转检测到。所以实际情况中会使用LS和DV算法进行互补。
RIP协议重要参数

链路费用：相邻两点链路费用为1“跳”，最大费用限制为15
通告周期：选路更新通告周期为30秒
邻居离线：邻居离线判定周期为180秒
协议端口：基于UDP，端口为520
LS与DV的比较

LS	DV
报文数量	O(nE)	邻居数
收敛速度	O（n2） 可能震荡	路由环路，无穷计数
健壮性	独立计算路由表	错误可能会被传播