4.9路由算法

网络图中的关键问题：

源到目的的最小费用路径是什么？

费用可以用带宽的倒数、拥塞程度等表示(越小越好)

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

路由算法的分类：

静态路由：

手工配置、路由更新慢

优先级高

动态路由：

路由更新快(定期更新、及时响应链路费用或网络拓扑变化)

全局信息：

所有路由器掌握完整的网络拓扑和链路费用信息

e.g.链路状态(LS)路由算法

分散信息：

路由器只掌握物理相连的邻居以及链路费用

e.g.距离向量(DV)路由算法

链路状态路由算法：

伪代码:

 

Dijkstra存在的问题：

 存在震荡的可能(摆动现象)：

 

 

距离向量路由算法：

 

如：

存在的问题：直接到达邻居的费用不是最小的...

该算法的重点：节点只需要获得最短路径的下一跳，该信息用于转发表中

过程:

特点：

 

距离向量路由算法的实例：

 

 距离向量算法中的链路费用发生变化：

(1)路径费用变小

 

(2)路径费用变大

引发无穷计数问题

解决方法：

1.毒性逆转：

思考：毒性逆转能彻底解决无穷计数问题吗？

2.定义最大度量

层次路由：

存在的问题：

层次路由：(自治系统内和自治系统之间)

聚合路由器为一个区域->自治系统AS

互连的AS：

自治系统间的路由任务：

1.学习目的网络可以通过哪些网络到达

2.将这些网络可达性信息传播给其内部路由器

例子：

1.单个AS

 

2.在多AS间选择

 

 

4.10 Internet路由：

AS内部路由协议也称为内部网络协议IGP(interior gateway protocols)

常间的AS内部路由协议：

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

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

3.内部网关路由协议：IGRP(interior Gateway Routing Protocol)（Cisco的私有协议）

 

RIP协议(小规模)：

基于距离向量路由算法：

 

RIP举例：

RIP：链路失效、恢复

180s内没有收到通过->邻居/链路失效。此时：

 

RIP路由表的处理：

 

OSPF协议：

基于链路状态路由算法

特点：

 

OSPF相对于RIP的优点：

 

分层的OSPF：

 

 

 

(AS边界路由器相当于网关路由器,在一个AS内可以有多个)

 

自治系统间的协议：

边界网关协议 BGP(一种矢量路由协议)：事实上的标准域间路由协议

 

eBGP->external BGP（通常物理直连）

iBGP->internal BGP (不一定物理直连，但一定要TCP可达)

 

 

BGP的基础：

前缀：可以用来表示一个子网的概念

例子：

分发路径信息：

分发路径信息的内容：路径属性与BGP路由

BGP路由选择：

  

BGP的路由选择策略：

 

客户网络和提供商网络的区别：

客户网络不提供过路流量传输

 

 

 

 

 

总结：为什么要采用不同的AS内与AS间路由协议？