首页 > 搜索 > 计算机网络最佳路由表算法,计算机网络 路由算法

计算机网络最佳路由表算法,计算机网络 路由算法

互联网 2020-11-01 00:59:56
在线算命,八字测算命理
路由选择算法

1、路由算法概述

路由算法(协议)确定去往目的网络的最佳路径

转发表确定在本路由器如何转发分组。

网络抽象:图

图:G=(N,E)

N=路由器集合,E=链路集合

关键问题:源到目的的最小费用路径是什么?

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

2、路由算法分类

分类方式一:

静态路由:手工配置、路由更新慢、优先级高

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

分类方式二:

全局式路由选择算法:所有路由器掌握完整的网络拓扑和链路费用信息。例如链路状态算法(LS,Link State)。

分散式路由选择算法:路由器值掌握物理相连的邻居以及链路费用,邻居间信息交换、运算的迭代过程。例如距离向量算法(DV,Distance-Vector)。

3、链路状态路由算法

Dijkstra算法

所有结点(路由器)掌握网络拓扑和链路费用。

    通过链路状态广播。

    所有结点拥有相同信息。

计算从一个结点(源)到达所有其他结点的最短路径。

    获得该结点的转发表

迭代:K次迭代后得到到达K个目的结点的最短路径。

符号:

c(x,y) 结点x到y的链路费用,不直接相连为记为无穷大

D(v) 从源到目的v的当前路径费用值

p(v) 沿从源到v的当前路径,v的前序结点

N' 已经找到最小费用路径的结点集合

★算法描述:

1  Initialization: 2    N' = {u} 3    for all nodes v 4      if v adjacent to u 5          then D(v) = c(u,v) 6      else D(v) = ∞ 7 8   Loop 9     find w not in N' such that D(w) is a minimum 10    add w to N' 11    update D(v) for all v adjacent to w and not in N' : 12       D(v) = min( D(v), D(w) + c(w,v) ) 13    /* new cost to v is either old cost to v or known 14     shortest path cost to w plus cost from w to v */ 

15  until all nodes in N' 

★算法复杂性:n个结点

    每次迭代需要检测所有不再集合N'中的结点w

    n(n+1)/2次比较:O(n2)

    更高效的实现:O(nlogn)

★存在问题:震荡(oscillations)

数据报可能总是路由不到A,随着TTL减少最终被丢包。通常会使用其他机制也避免震荡现象,比如引入随机延时。

4、距离向量算法

Bellman-Ford方程(动态规划)

Definedx(y) := cost of least-cost path from x to yThendx(y) = min {c(x,v) + dv(y) }where min is taken over all neighbors v of x

重点:结点获得最短路径的下一跳,该信息用于转发表中!

Dx(y)=从结点x到结点y的最小费用估计

    x维护距离向量(DV):Dx=[Dx(y): y∈N]

结点x:

    已知到达每个邻居的费用:c(x,v)

    维护其所有邻居的距离向量:Dv=[Dv(y): y∈N]

核心思想:

    每个结点不定时地将其自身的DV估计发送给其邻居。

    当x接收到邻居的新的DV估计时,即一句B-F更新其自身的距离向量估计

    Dx(y) ← minv{c(x,v) + Dv(y)}    for each node y ∊ N

    Dx(y)最终会收敛于实际的最小费用dx(y)

特点:

1、异步迭代:

    引发每次局部迭代的因素

        1)局部链路费用改变

        2)来自邻居的DV变化

2、分布式

    每个结点只有当DV变化时才通告给邻居,邻居在必要时(其DV更新后发生变化)再通告它们的邻居。

每个结点的状态变化:

等待(本地局部链路费用变化或收到邻居的DV更新)

        ↓

重新计算DV估计

        ↓

如果DV中到达任一目的距离发生改变,通告所有邻居

(回到等待……)

存在问题:无穷计数

坏消息传播得慢,当网络中存在环路时,可能会出现无穷计数问题。

解决方法:

1、毒性逆转

如果一个结点Z到达某目的X的最短路径是经过某个邻居Y,则通告给该邻居结点到达该目的的距离为无穷大。

注:涉及3个或更多结点的环路将无法用毒性逆转技术检测到。

2、定义最大度量

定义一个最大的有效费用值,如15跳步,16跳步代表无穷大。

--------------------------------------------------------------

简单总结一下,路由算法很重要!!!要好好看书哇(#^.^#)

免责声明:非本网注明原创的信息,皆为程序自动获取互联网,目的在于传递更多信息,并不代表本网赞同其观点和对其真实性负责;如此页面有侵犯到您的权益,请给站长发送邮件,并提供相关证明(版权证明、身份证正反面、侵权链接),站长将在收到邮件12小时内删除。

相关阅读

一周热门

查看更多