第四章 网络层(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） 可能震荡	路由环路，无穷计数
健壮性	独立计算路由表	错误可能会被传播

今朝有酒

高手云集 果断围观

铭绍

一直在看

梦雨铃

打酱油的人拉，回复下赚取积分

王言培

在撸一遍。。。

叨叨魏

这么强,支持楼主，佩服

长生美仙

排排坐

占位编辑

吕鑫

鄙视楼下的顶帖没我快，哈哈

龙飞玲

为毛老子总也抢不到沙发？！！