哈工大计算机网络课程网络层协议详解之:路由算法概述与链路状态路由算法

这篇具有很好参考价值的文章主要介绍了哈工大计算机网络课程网络层协议详解之:路由算法概述与链路状态路由算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

哈工大计算机网络课程网络层协议详解之:路由算法概述与链路状态路由算法

在前面的小节中,我们介绍了网络中路由器的路由与转发等功能。我们说作为网络层,从功能上来说,核心功能就是要实现路由和转发。 对于转发来说,实际上就是路由器根据存储的转发表,将目的地址转发到对应的输出链路上去。在这个过程中,完成转发的重要依据,就是转发表,而转发表中的路由信息,就来自于路由算法。 通过路由算法来计算合适的路由信息,存储在转发表中,供后续转发时检索。

总而言之,路由的功能对于网络层来说非常重要,如果没有路由算法来确定路由信息,网络层设备就无法确定接收的数据报应该如何转发到目的地址。

网络抽象:图

作为各种路由算法,首先都是将网络结构抽象成一个图的结构,如下所示。图的数据结构包含了一系列的节点,用N来表示,节点之间用线连起来表示边,用E来表示。图的抽象在网络领域应用应该说是非常广泛的。

哈工大计算机网络课程网络层协议详解之:路由算法概述与链路状态路由算法

除了顶点和边,还可以对边设定数值,这些数值被成为边的权重。在网络应用中,这些权重被抽象成表示链路传输的代价:cost(x, x’) = 链路(x, x’)的费用,比如图中c(w, z) = 5。实际上,这些权重可以根据网络的不同应用场景来设置,比如可以真实的表示链路的造价成本、带宽的倒数,或者拥塞程度等。

有个上述的权重/费用后,在描述从源主机到目的主机经过的路径费用,就是每条路径的费用之和。

哈工大计算机网络课程网络层协议详解之:路由算法概述与链路状态路由算法

有了上述的目标函数后,路由问题就被抽象成了,如何得到源到目的(如u到z)的最小路径费用是什么?

因此,路由算法就是寻找源到目的之间最小费用路径的算法。

路由算法分类

静态路由 vs 动态路由

静态路由:

  • 手工配置。

    网络管理员根据对网络的掌握,进行手工配置路由转发规则。

  • 路由更新慢。

    必须要手动更新

  • 优先级高

动态路由:

  • 基于路由算法计算得到,路由更新快

    网络中的路由器可以快速计算得到新的路由信息,从而快速更新自身的转发表

  • 周期性更新

  • 及时响应链路费用或网络拓扑变化。

    一旦网络链路费用或者拓扑结构发生变化,通过动态路由计算后,能够及时地响应这种变化。

全局信息 vs 分散信息

即路由算法是只需要局部信息,还是需要全局信息。

全局信息:

  • 所有路由器掌握完整地网络拓扑和链路费用信息
  • 最具有代表性的算法:链路状态(LS)路由算法

分散信息:

  • 路由器只掌握物理相连的邻居以及链路费用
  • 邻居间信息交换、运算的迭代过程
  • 最具代表性的算法:距离向量(DV)路由算法

链路状态路由算法

熟悉数据结构的朋友应该知道,在图结构中求最短路径,一个比较经典的方法就是Dijkstra算法,而链路状态路由算法也恰好就是基于Dijkstra最短路径算法来求解的。

Dijkstra算法在求从一个节点出发,到其他节点的网络最短路径时,需要掌握图的完整拓扑信息和链路费用。 实际上,链路状态路由算法中的链路状态这个词的来历,就反应了我们怎么样保证所有的路由器都能够掌握这张图完整的拓扑信息。

链路状态算法要求每一个路由器,都要构造一个链路状态分组,并进行广播。 这个链路状态分组包含这个路由器与之相连的所有邻居路由器的IP地址,以及与这个路由器直接相连的链路费用。此时,任何路由器都会收集网络中所有其他路由器广播出来的链路状态分组,因此,路由器就可以基于这些链路状态分组中的链路状态信息,构造出完整的网络拓扑结构和链路费用信息。

这样,每个路由器都可以根据它所获取的信息,抽象出完整的网络拓扑结构图和链路费用信息,利用Dijkstra算法计算最短路径。

总结来说就是:

  • 所有节点(路由器)掌握网络拓扑和链路费用
    • 广播链路状态信息
    • 每个路由器获取其他路由器广播的链路状态信息,最终所有节点拥有相同的信息
  • 每个路由器根据其获取的信息,抽象出完整的网络拓扑结构和链路费用,计算从一个节点(“源”)到达所有其他节点的最短路径
    • 获得该节点的转发表
  • 迭代:K次迭代后,得到到达K个目的节点的最短路径(Dijkstra算法的特性)

为了后续对算法描述的便利,先列出使用的符号说明:

  • c(x, y):节点x到节点y链路费用,如果x和y不直接相连,则=∞
  • D(v): 从源到目的节点v的当前路径费用值
  • p(v):沿从源到目的节点v的前序节点
  • N‘:已经找到最小费用路径的结点集合

Dijkstra算法

Dijkstra算法的伪代码过程如下所示,与数据结构中图的求最短路径的算法过程是类似的。
哈工大计算机网络课程网络层协议详解之:路由算法概述与链路状态路由算法

首先初始化时将当前节点u放入到N’中,并遍历图中除u节点外的其他节点,如果是u的邻居节点,则计算链路费用D(v),如果不是邻居节点,这u节点到该节点的路径费用初始化为无穷大D(v) = ∞。

接着进入一个循环迭代过程。

首先找出刚刚计算的D(w)中,不在N‘集合中,且D(w)值最小的节点w。

找到后,将该节点w加入到N’中,相当于从邻居节点中,找到链路费用最小的邻居节点。

接下来,再计算w节点的所有不在N’集合中的邻居节点的链路费用。其中,D(v) = min(D(v), D(w) + c(w,v))。这个公式也好理解,因为我始终是要找u节点到其他所有节点的最短路径,所有每个D(v)保存的都应该是节点u到当前节点的最小值。

最后重复这个过程,直到所有的节点都包含在了N‘集合中,表示已经找到了所有其他节点的最短路径。

Dijkstra算法示例

假设有下图的网络拓扑结构,我们计算节点u到网络中其他各节点的最短路径。

  1. 首先将节点u加入到已确定最短路径节点集合N’,计算节点u的邻居节点的路径长度D(X)=5、D(W)=3、D(V)=7,并初始化其他节点的D(y)、D(Z) = ∞

  2. 选取节点u邻居节点的最短路径D(w) = 3,的节点W加入N‘,继续计算w节点的邻居节点(不在集合N’中邻居节点)的路径长度。

    这里节点x在u->w->x的路径下D(x) = 7 < 原先从u->x的路径D(x)=5,所以仍然保留D(x) = 5。这也就是上面公式D(v) = min(D(v), D(w) + c(w,v))。而对于节点v来说,路径u->w->v的D(v) = 6 < 原先从u->v的路径D(v) = 7,因此节点v的最短路径D更新为D(v) = 6。

  3. 在节点w的邻居节点中,路径最短的节点是v,加入集合N‘中,继续计算v节点的邻居节点的路径长度。

  4. 同样的,这次取的邻居节点的最短路径是节点y,加入集合N’,此时D(y) = 10。继续计算y节点的邻居节点的路径长度。

  5. 最短路径是节点z,加入集合N‘,此时D(z) = 12。

  6. 最终,集合N’已经包含网络中所有节点,则遍历结束,此时节点对应的D(x)保存的就是节点u到当前节点的最短路径。

整体的流程记录如下图所示,每次红圈圈选出来的都是每一步的最短路径节点。

哈工大计算机网络课程网络层协议详解之:路由算法概述与链路状态路由算法

示例2,整理的流程步骤跟上述类似。

哈工大计算机网络课程网络层协议详解之:路由算法概述与链路状态路由算法

在示例2中我们最终可以得到的节点u到网络中其他各节点的最短路径树为:

哈工大计算机网络课程网络层协议详解之:路由算法概述与链路状态路由算法

这个最短路径树获取后,对于节点u来说,会把这个信息反映到最终的转发表中:

哈工大计算机网络课程网络层协议详解之:路由算法概述与链路状态路由算法

利用这个转发表,路由器u就知道如果需要将数据报发送到网络中其他节点时,应该走什么样的最短路径。比如要把数据送往路由器v,就可以通过u->v这个接口转发出去,如果要把数据送往路由器x、y、w、z,则都是通过u->x的接口转发出去。这就实现了基于Dijkstra算法的链路状态路由算法。

Dijkstra算法讨论

算法复杂性:n个节点

  • 每次迭代:需要检测所有不在集合N‘中的节点w
  • n(+1)/2次比较:时间复杂度O(n²)
  • 更高效的实现:O(nlogn)

链路状态路由算法的基础是每个节点都需要获取到整个网络的完整拓扑结构,这个在网络规模比较大时,很难适用。因此,接下来我们还会继续介绍距离向量路由算法,以及层次化路由算法。文章来源地址https://www.toymoban.com/news/detail-507962.html

到了这里,关于哈工大计算机网络课程网络层协议详解之:路由算法概述与链路状态路由算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 哈工大计算机网络课程局域网详解之:交换机概念

    在介绍完局域网中最具代表性的以太网技术后,接下来我们继续来看一下在局域网中使用非常广泛也是非常重要的网络设备:交换机。 本节主要面向以太网来介绍其中使用的交换机。 作为以太网交换机来说,是一个典型的数据链路层设备,可以实现对链路层数据帧的存储-转

    2024年02月15日
    浏览(47)
  • 哈工大计算机网络课程局域网详解之:无线局域网

    本节介绍一下平时经常使用的一个无线局域网技术,也就是通常我们使用的wifi。 wifi是IEEE 802.11这样一个系列标准所定义的无线局域网。作为802.11局域网来说,实际上存在很多版本: 802.11b 2.4-2.5GHz免费频段(unliebensed spectrum) 最高速率:11Mbps 物理层采用直接序列扩频(DSSS)

    2024年02月15日
    浏览(47)
  • 哈工大计算机网络课程网络层协议详解之:路由算法概述与链路状态路由算法

    在前面的小节中,我们介绍了网络中路由器的路由与转发等功能。我们说 作为网络层,从功能上来说,核心功能就是要实现路由和转发。 对于转发来说,实际上就是路由器根据存储的转发表,将目的地址转发到对应的输出链路上去。在这个过程中,完成转发的重要依据,就

    2024年02月11日
    浏览(41)
  • 哈工大计算机网络课程网络层协议详解之:互联网控制报文协议(ICMP)

    在互联网中,IP数据报的传输很容易出现差错,当出现差错时,最简单的处理办法就是对该IP数据报进行丢弃。但是,并不是直接丢弃就完了,为了让源主机感知到数据报出现差错,当数据报被丢弃时,IP网络会借助于ICMP协议,向发送数据报的源主机发送一个ICMP差错报文。本

    2024年02月12日
    浏览(49)
  • 哈工大计算机网络课程数据链路层协议详解之:多路访问控制(MAC)协议

    在上一小节介绍完数据链路层功能和所提供的服务后,接下来我们介绍一个在 数据链路层非常重要的一个协议:多路访问控制MAC协议。 多路访问控制主要是为了解决一类链路的使用问题。作为网路中的链路,大致可以分为以下两类: 点对点链路 顾名思义,链路只连接两个相

    2024年02月15日
    浏览(53)
  • 哈工大计算机网络课程网络安全基本原理详解之:消息完整性与数字签名

    这一小节,我们继续介绍网络完全中的另一个重要内容,就是消息完整性,也为后面的数字签名打下基础。 首先来看一下什么是报文完整性。 报文完整性,也称为消息完整性(message integrity),有时也称为报文/消息认证(或报文鉴别),目标: 证明报文确实来自声称的发送

    2024年02月15日
    浏览(44)
  • 哈工大计算机网络传输层协议详解之:TCP协议

    哈工大计算机网络课程传输层协议详解之:可靠数据传输的基本原理 哈工大计算机网络课程传输层协议详解之:流水线机制与滑动窗口协议 哈工大计算机网络课程传输层协议详解之:拥塞控制原理剖析 点对点通信 一个发送方、一个接收方 可靠的、按序的字节流 流水线机制

    2024年02月10日
    浏览(43)
  • 哈工大计算机网络传输层协议详解之:可靠数据传输的基本原理

    哈工大计算机网络课程传输层协议详解之:流水线机制与滑动窗口协议 哈工大计算机网络课程传输层协议详解之:TCP协议 哈工大计算机网络课程传输层协议详解之:拥塞控制原理剖析 什么是可靠? 不错、不丢、不乱 可靠数据传输协议 可靠数据传输对应用层、传输层、链路

    2024年02月12日
    浏览(42)
  • 哈工大计算机网络传输层详解之:流水线机制与滑动窗口协议

    哈工大计算机网络课程传输层协议详解之:可靠数据传输的基本原理 哈工大计算机网络课程传输层协议详解之:TCP协议 哈工大计算机网络课程传输层协议详解之:拥塞控制原理剖析 在上一节中我们逐步分析了可靠传输协议的设计过程,最后讲到rdt3.0的设计和实现机制。但是

    2024年02月10日
    浏览(41)
  • 哈工大 计算机系统 二进制炸弹实验报告

    实验报告 实 验(三) 题     目  Binary Bomb          二进制炸弹   专       业      计算机学院          学    号               班    级                学       生              指 导 教 师                实 验 地 点        实 验 日 期     

    2023年04月15日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包