系列文章目录

第五章计算机网络之网络层9

---

---

一、路由算法

路由与转发

网络抽象：图

图抽象：费用（Costs）

图中链路标识的权值代表网络链路中的费用（距离）
描述路径费用：从源到目的经历的每段链路的费用之和
费用越小，路径越好。
比如带宽的倒数，带宽越大，倒数越小，费用和越小，速度越快。

路由算法分类

二、链路状态路由算法

网络抽象：图

链路状态路由算法

每个路由器构建链路状态分组并且广播出去。
链路状态分组包含：与该路由器直接相连的路由的路由ID（如IP地址）和该路由直接相连的链路费用，广播出去。
广播：在链路状态算法里面是通过扩散（泛洪式），将该分组发送给所以邻居，邻居再发送给邻居，直到所有路由收集完全部分组构成完整的网络拓扑。
c(x,y)有物理链路直接相连费用则为权值，没有就置为无穷大。
D（v）：可能是最短路径也可能不是，费用值（总路费用和）
P(v)：A-B-C-D P(D)=C

Dijkstra算法

目的是找到原到目的最短路径或者通过其他路由转发那个最短路径的路由的接口
初始化：以u为例
到达w路径的最短路径没有找到：
在目前到达这些（w）结点除了找到最短路径（在N’中），没找到最短路径（不在N’中的）中的所有结点中，到达W的DW值最小的，满足该条件，则该路径就是到达W的最短路径。

Dijkstra算法：例1

Step0：初始化
找到不在当前N’所有结点，那个结点到u费用路径最小，v,w,x,y,z都不在，开始比较3，u最小，则w到u最短（则源为u到目的w最短路径找到）
将w加入N’中，更新w的邻居，比较最小：原先到达目的的费用值D or 到达最小W的费用值加w到达目的的费用值
这种迭代方法，通过5次迭代将最短路径找到。

Dijkstra算法：例2

Dijkstra算法：讨论

发生震荡时，可能B的数据报发给C后，C到D后，结果D的路由表重新计算更新，D又到C又到B，然后B路由表又重新计算，到C…
这样反复下去，直到TTL，数据报被丢弃。B的数据报始终到不了A
所以，使用该算法要采取一些机制，随机延迟链路状态更新。

三、距离向量路由算法

距离向量（Distance Vector）路由算法

Bellman-Ford举例

距离向量路由算法

异步迭代：作为每一个路由器不是同步迭代同步结束。
邻居再计算，邻居再选择是否通告邻居（邻居的邻居）。

距离向量路由算法举例（来自邻居的DV更新）

其它的邻居节点还未将自己的距离向量交换过来，所以是无穷大。
x在计算的时候，将7更新为3，根据距离向量路由算法，当x向量发生变化时候，它便会把新的向量告知给邻居。同时向量y与z也在计算，如果发生改变也会告知其邻居

最终就趋向实际dx,y,z了，将该值更新到转发表中。

距离向量DV：链路费用变化（以yz为例）

y检测到距离的改变，同理x也能检测到距离的改变
同时也会告知x,以z为例。

距离向量DV：无穷计数问题（以yz为例）

当y由4变成60时，还没告诉z，z之前告诉，z到x是5，现在y到x是60，根据距离向量路由算法得现在最短路径为5（z到x）+1（y到z）= 6

一直重复下去，直到，z发现经过y到x（51）比直接到x距离长（50），这样重复很多次，如果50或者60变成很大时候，就会出现无穷计数问题。

无穷计数的解决办法（毒性逆转）

无穷计数的解决办法（定义最大度量）

虽然可能出现无穷计数问题，但是通过定义最大度量值的方法，会在有限的交换过程中到达最终达到收敛，最终反应网络实际状态。
16跳步认为不可抵达即无穷大
在实际的网络中，交换的距离向量不是面向路由器而是网络。
前面讲算法原理用路由器结点便于理解
R2收到16时候就知道该子网不可到达了，由于，由于原先认为可达14，现在不可达，距离向量发生变化，依然会把16跳交换给R1
R1,无穷大+1=无穷大，所以还是16跳（R1由于一开始不可以到达该子网（认为大于16跳）通过R2来到子网+1转发）
到t15 R1 和 R2 知道网络不可抵达

四、层次路由

互连的AS

系统内用链路状态路由算法或者距离向量路由算法等

自治系统间（Inter-AS）路由任务

例：路由器1d的转发表设置

例：在多AS间选择

五、 Internet路由

六、RIP简介

AS内部路由

RIP协议

RIP举例

DV通知next hops（下一个路由和到达目的多少跳步）

RIP：链路失效、恢复

RIP协议适合小规模自治系统，因为最大跳为15跳
对于无穷计数，RIP发送可能性小，因为它定义了最大跳还有应用了毒性逆转计数

RIP路由表的处理

网络层通过应用层去完成
模型都是根据功能划分，尽管RIP用了应用层route-d去完成，但是它的功能是面向网络层的（route-d不能为应用层提供服务（端到端，不服务客户端和服务器））所以，RIP是网络层的协议。

七、 OSPF协议简介

OSPF（Open Shortest Path First）

OSPF优点（RIP不具备）

当大量数据要传输时候，可以把数据分散到多条路由，实现负载（流量）均衡。

分层的OSPF

这个AS边界路由器再一个子网中可以有很多个

八、 BGP协议简介

Internet AS间路由协议：BGP

好不一定是路径最短或者费用值最低，而是相关政策

BGP基础

前缀表达：子网
半永久：长期不拆除

BGP基础：分发路径信息

可达性：最终在路由表增加关于前缀网络的入口项，到达某个结点网络，通过哪一个接口将其转发出去

路径属性与BGP路由（route）

选择2b还是2c通过热土豆方式来选择

BGP路由选择

最短AS-PATH:从源出发把数据送到前缀的所描述的目的网络，所经过的自治系统越少，路径越短越好，说的是自治系统数短，并不是经过的路由器少（不一定）。
2c与2b：热土豆

BGP路由选择策略

w y 出与进只有一个链路，用静态配置就基本可以

为什么采用不同的AS内与AS间路由协议