2022年数据交换网络中洪泛算法系统的实现和性能分析 2.pdf

《2022年数据交换网络中洪泛算法系统的实现和性能分析 2.pdf》由会员分享，可在线阅读，更多相关《2022年数据交换网络中洪泛算法系统的实现和性能分析 2.pdf（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据交换网络中洪泛算法系统的实现和性能分析任杰 51090104036 通信与信息系统一、洪泛算法的概念和特点. 21.1 路由算法概述. 21.2 路由算法评价标准. 21.3 洪泛算法的算法分析. 2二、洪泛算法的实现过程. 22.1 洪泛算法具体流程. 22.2 单次洪泛算法的实现流程. 32.2.1 初始化阶段 . 32.2.2 路由建立阶段. 32.2.3 数据转发阶段. 32.2.4 算法流程总分析. 32.3 多次洪泛算法的更新. 3三、洪泛算法的具体性能分析. 33.1 洪泛算法的时间复杂度分析. 33.2 洪泛算法的空间复杂度分析. 43.3 总体算法的分析. 4名师资料总结

2、 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 4 页 - - - - - - - - - 这是一个多人合作作业。旨在更清楚地理解在网络数据传输过程中信道参数，拥塞等对通信系统性能的影响。 这个作业的最终成品为一个多媒体演示软件和相应的技术文档。 本文主要讨论的内容是数据交换网络中路由算法之一洪泛算法的具体实现以及其算法的性能分析。一、洪泛算法的概念和特点1.1 路由算法概述路由算法是数据交换网络中较为重要的一部分，其设置的优劣与否会大大影响数据交换的成功率和传输速度。 而路由算法的

3、研究也随着时间有着较大的发展空间。到目前为止， 已经应用在现实生活中的路由算法主要包括了一下几种：基于静态路由表的路由分组技术，基于最短路径的dijkstra 算法和基于动态规划的Floyd 算法，基于可靠性保证的洪泛算法等。而每个算法都由其特殊的优劣有着不同的适用范围。而本文研究的是在保证准确性前提下使用的洪泛算法。1.2 路由算法评价标准路由算法的设计为了达到更好的用户体验效果，要求路由算法具有以下几个特点：优化；简单低耗；健壮稳定；快速聚合；灵活性。由于现实网络的具体情况是随时间变化而有可能有较大变化的，而优秀的路由算法要求能够很快很好的适应最新的情况要求； 同时路由算法作为数据交换网络

4、中的基础算法，也要求不能占有很大的资源和带宽， 具有简单和低耗的特点。 对于出现硬件错误等情况的出现，路由算法也必须仍然能够处理，由于路由器作为网络连接的节点处，其失效往往会造成较大的损失和影响，所以也要求路由算法的健壮性。同样，基于以上特点建立的路由算法与同时需要以上述作为评价标准，通过对于 dijkstra 和 floyd 算法的分析可以看出好的路由算法必然同时满足了以上要求。1.3 洪泛算法的算法分析洪泛（ Flooding）算法，故名思意，将需要传递的信息像洪水泛滥的情形一样传递下去， 从而最终保证传到需要的目的节点。其算法相当的简单， 当每个路由器接收到信息时， 判断其是否第一次接收

5、到， 如果是第一次接收到的话则相与自己相连通的所有节点传输该信息，如果不是的话则自动抛弃该信息。以后的所有路由器都遵循同一个原则， 从而将该信息传输到目的节点。 此算法的核心在于判断是否为第一次接受的信息。 由于传递不具有方向性， 而是单一的相所有相连节点进行信息的传递， 则很容易发生信息成环的传递结果，这个时候如果不判断是否第一次接收到此信息的时候就会导致信息风暴的产生，导致信息在某两台或多个计算机中循环重复传递，大大占用带宽和资源。二、洪泛算法的实现过程2.1 洪泛算法具体流程名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - -

6、名师精心整理 - - - - - - - 第 2 页，共 4 页 - - - - - - - - - 洪泛算法作为一个路由算法， 其最终的目标是对于一个不清楚状况的数据交换网络能够迅速而高效的进行信息内容的交换。这就决定了洪泛算法的基础是在一个没有具体权值的具体图中进行搜索和信息传递。而洪泛算法的结果应该包括了每个节点的路由表的建立和最终点到点传输方向的建立。2.2 单次洪泛算法的实现流程洪泛算法应该基于三个步骤：初始化阶段，路由建立阶段，数据转发阶段。下面分每个阶段进行算法的设计和描述2.2.1 初始化阶段初始化阶段（ Initialization Phase）中具体又分为两步：第一步，各个

7、节点广播节点信息的报文NIP；第二步，收到 NIP 报文的节点将其相关信息存储到邻居信息表 NIT 中。通过初始化阶段以后每个节点就能获得其与哪些节点直接相连，并能得到初始化阶段每两个节点之间的连接时延作为图的权值；2.2.2 路由建立阶段路由建立阶段（ Routing Building Phase）分为 3 步：第一步，源信息节点查找其 RPT 表，若它是 RREP报文 SNL 中的一个节点，则直接沿某RREP 的确定路径进行信息的转发， 否则就广播一个新的RREQ，相当于将具体信息传递给下一个节点；第二步，节点 Ni接收到 RREQ 后查找 RPT 表， 若它是直接沿该 RREP确定的路径

8、向上一层回复RREP，否则将报文的 TTL 减一，表示已经经过了一个节点跳，当 TTL 小于 0 时认为该信息已经传递大于限定的长度，自动抛弃该信息；第三步等待一个固定的t 时间，若来自同源节点有转发能耗更小的RREQ，则将目前得到的最小来自同源节点的报文进行保存，等待转发，直到RREQ 到达 Sink。第四步：节点Ni丢弃该报文，同时将报文信息记录在自身的数组中，以待以后进行判断是否接收过。2.2.3 数据转发阶段数据转发阶段（ Data Forwarding Phase ）分为 3 步：第一步，源点收到RREP后沿该 RREP 指定的路径相后发送数据报文；第二步。当Ni剩余能耗不够转发DP

9、 时，则其广播 RP报文，收到该文的节点是在NIT 中将 Ni状态改为 Dead，若Ni是一个使用的节点，想该路径中的邻居节点向自己在路径中的上一跳节点发送RR 报文，并将 RPT 表中对应的 RREP信息删除，直到报文到达该路径的起点。当源点接收到此 RP 后，转第二步。2.2.4 算法流程总分析通过了以上三步的路由建立过程，对于一个不知道每个边的图能够获得较好的路由结果，同时对于数据能够迅速的传递给目标节点。2.3 多次洪泛算法的更新洪泛算法的使用往往是在数据交换网络刚刚建立的时候，而对于一个已经建立好的数据交换网络， 其很多状态是能够进行推测和描述的。此时洪泛算法就不具有其应有的优势，而

10、应使用其他路由算法进行更替，获得更好的路由结果。三、洪泛算法的具体性能分析洪泛算法的算法性能分析主要分为时间复杂度的分析和空间复杂度的分析。3.1 洪泛算法的时间复杂度分析名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 4 页 - - - - - - - - - 对于一个总共有N 个节点的稀疏图，其边远小于N 的平方，对于每一个节点，由于其传递的信息收到与其相连的边的限制，所以其传出的次数小于其邻边数 M。对于 N 个节点深度的搜索过程来说，其时间复杂度约为O(MN)，相

11、比于floyd 算法 O（N3）和 disjkstra 算法 O(N2)的复杂度来说，具有较好的时间阈值。3.2 洪泛算法的空间复杂度分析由于数据传输的过程来说， 每个节点需要保存一个与图节点相关的栈来进行数据报文的保存，则其空间复杂度为O（N2） 。也具有较好的复杂度。3.3 总体算法的分析由于程序算法尚没有使用相关的语言进行实现，所以暂时难以对其具体的时间和空间占用进行定量分析，这也是下一步需要努力完成的方向。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 4 页 - - - - - - - - -