路由
动态路由
若某个设定好的路径无法使用时,现存的节点必须决定另一个传送资料到目的地的路径。他们通常使用以下两种形式的路由协定来达成:距离向量算法与连线状态算法。所有路由算法几乎都可以分类到这两种算法中。
距离向量算法
距离向量算法 使用Bellman-Ford算法。对于每一条网络上节点间的路径,算法指定一个“成本”给它们。节点会选择一条总成本(经过路径的所有成本总和)最低的路径,用来把资料从节点甲送到节点乙。
此算法非常的简单。当某节点初次启动时,将只知道它的邻居节点(直接连接到该节点的节点)与到该节点的成本。(这些资讯、目的地列表、每个目的地的总成本,以及到某个目的地所必须经过的“下一个节点”,构成路由表,或称距离表。)每个节点定时地将目前所知,到各个目的地的成本的资讯,送给每个邻居节点。邻居节点则检查这些资讯,并跟目前所知的资讯做比较;如果到某个目的地的成本比目前所知的低,则将收到的资讯加入自己的路由表。经过一段时间后,网络上得所有节点将会了解到所有目的地的最佳“下一个节点”与最低的总成本。
当某个节点断线时,每个将它当作某条路径的“下一个节点”的节点会将该路由资讯舍弃,再建立新的路由表资讯。接着,他们将这些资讯告诉所有相邻的节点,再找出到所有可抵达的目的地之新路径。
连线状态算法
在 连线状态算法中 ,每个节点拥有网络的图谱(一个图)。每个节点将自己可以连接到的其他节点资讯传送到网络上所有的节点,而其他节点接着各自将这个资讯加入到图谱中。每个路由器即可根据这个图谱来决定从自己到其它节点的最佳路径。
完成这个动作的算法——Dijkstra算法——建立另一种数据结构——树。节点产生的树将自己视为根节点,且最后这棵树将会包含了网络中所有其他的节点。一开始,此树只有根节点(节点自己)。接着在树中已有的节点的邻居节点且不存在树中的节点集合中,选取一个成本最低的节点加入此树,直到所有节点都存入树中为止。
这棵树即用来建立路由表、提供最佳的“下一个节点”等,让节点能跟网络中其它节点通讯。
路由算法的比较
在小型网络中,距离向量路由协定十分简单且有效率,且只需要些微的管理。然而,它们的规模性不好,且收敛性质也十分差,因此促进了较复杂但规模性较好的连线状态路由协定的开发,以使用在较大型的网络。距离向量路由协定也有无限计数问题(count-to-infinity problem,见[1] (英文) )。
连线状态路由协定的主要优点是在限制的时间内,对于连线改变(例如断线)的反应较快。而且连线状态路由协定在网络上所传送的封包也比距离向量路由协定的封包小。距离向量路由协定必须传送一个节点的整个路由表,但连线状态路由协定的封包只需要传输该节点的邻居节点资讯即可。因此,这些封包小到不会占用可观的网络资源。连线状态路由协定的主要缺点则是比距离向量路由协定需要较多的储存空间与较强的计算能力。
路由协定与可被绕送协定
有时路由协定与可被绕送协定常会令人混淆:
可被绕送协定 :任何一个提供足够的网络层位址资讯让封包可被从一个装置转送到另一个,而不需要知道来源到目的地的整条路径的网络通讯协定。“可被绕送协定”定义了封包的格式与封包字段的使用方式。封包通常从一个终端系统被递送到另一个。IP是一个可被绕送协定,而以太网路是一个不可被绕送协定的例子。
路由协定 :在网络间交换 路由资讯 ,让路由器可动态建立路由表的通讯协定。传统的IP路由十分简单,因为它使用 下一个节点路由方法 ,也就是路由器只需要考虑将封包送到哪一个“下一个节点”,而不需考虑到目的地的整条路径。
虽然动态路由可能非常复杂,但它使得互联网十分有弹性,且让互联网的规模自从采用IP以后成长了超过八个数量级。
路由度量 (routing metric)包含了被路由算法使用来决定哪一条路径较另一条路径好的所有数值。度量可能包括许多资讯,例如带宽、延迟、经过节点数、路径成本、负载、MTU、可靠性及传输成本等。路由表只储存最佳的可能路径,但连线状态或拓扑数据库可能储存其他相关的资讯。
当路由器从不同的路由协定里发现有多个能抵达相同目的地的不同路径时,它们使用称为 管理距离 (administrative distance)的特性来选择最佳的路径。管理距离定义了路由协定的可靠程度。每个路由协定按照管理距离值,由最可靠到最不可靠排列来区分优先级。
依照路由器与其他自治系统的关系,有许多种类的路由协定:
Ad hoc网络路由协定 出现在没有或一点点基础的网络。参见Ad hoc路由协定列表以获得提议中的协定。
内部闸道协定 ( IGP s)在单一的自治系统中交换路由资讯。常见的范例包括:
外部闸道协定 ( EGP s)在不同的自治系统中交换路由资讯。EGP包括:
注释
^ 在许多思科的广告文件中,EIGRP 不是一种连线状态路由协定,也不是任何一种混合式的协定。
参见
路由算法
偏向路由(en:Deflection routing)
政策路由(en:Policy based routing)
虫洞路由(en:Wormhole routing)
适应性路由(en:Adaptive routing)
特别的设计
与封包转送有关,但与路径选择无关的条目
数种尺度路由的数学复杂性
延展网络 路由模式
RPSL
HSLS(en:Hazy-Sighted Link State Routing Protocol)
OSPF(一个连线状态路由协定)
模糊逻辑路由(en:Fuzzy routing)
地理式路由(en:Geographic routing)
参考资料
Kurose, James E. and Ross, Keith W. Computer Networking. Benjamin/Cummings. 2004. ISBN 978-0-321-22735-5.
Doyle, Jeff. Routing TCP/IP, Volume I, Second Ed.. Cisco Press. 2005. ISBN 978-1-58705-202-6. Ciscopress ISBN 978-1-58705-202-6
免责声明:以上内容版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。感谢每一位辛勤著写的作者,感谢每一位的分享。
- 有价值
- 一般般
- 没价值