距离矢量路由组播协议

1距离矢量路由组播协议北京理工大学计算机学院DistanceVectorMulticastRoutingProtocol---DVMRP(Class07111304,SchoolofComputerScience,BeijingInstituteofTechnology,Beijing100081)AbstractIPMulticastprovidesalleffectivemechanismforcommunicationandtransmission.Itcanfullymakeuseoftheresourceofthenetwork,optimizetheperformanceofthenetworkandenablesomedistributedapplications，Whichcan’tberealizedbyunicastorbroadcast.Thedistancevectorroutingalgorithmisusedtofollowdifferentpruningstrategies.Thebasicalgorithmisreversepathforwarding.However,oncearouternoanyhosttogroupinterest,andthereisnoconnectiontoneedtoreceiveothersroutersonthemulticastmessage,thenitshouldwithprunemessageasreceivedinresponsetoamulticastmessage,telltheneighborsdonotsendthemessagetogivemyselftosendanymessagefromthegroup.Ifarouteritselfisconnectedtothehostthatisn’tthememberofthegroup,andfromitspreviousforwardingmulticastmessageonallroutershavingreceivedsuchamessagepruning,italsotopruneamessageinresponseto.Throughthisrecursivemethod,thefinalpruningofaspanningtree.Distancevectormulticastroutingprotocolisamulticastroutingprotocol.KeywordsMulticasting;distantvectormulticastrouting;摘要组播技术提供了一种有效的通信、传输方式，它可以充分利用网络资源，优化网络性能，使那些用单播或广播不可行的新型增值应用成为可能[1]。采用距离矢量路由算法，遵循不同的修剪策略。基本算法是逆向路径转发。然而，一旦一个路由器没有任何主机对某个组感兴趣，并且没有连接到需要接收该组播消息的其它路由器，那么它要用PRUNE消息作为接收组播消息的响应，告诉发送该消息的邻居不要再给自己发送任何来自该组的消息。如果一个路由器自己所连的主机没有一个属于该组成员，并且从它以前转发组播消息的所有线路都接收了这样的一个修剪消息，那么它也同样以PRUNE消息来响应。通过这种递归方式，最终修剪出一颗生成树。距离矢量组播路由协议就是以这种方式工作的组播路由协议。关键词组播；距离矢量路由算法；修剪树；逆向路径转发组播技术提供了一种有效的通信、传输方式，它可以充分利用网络资源，优化网络性能，使那些用单播或广播不可行的新型增值成为可能。比如多人游戏或者体育赛事视频直播到几个观看点，这样的应用将数据包发送给多个接收者。除非组的规模很小，否则每个接收者单独发不同的数据包代价会很昂贵。另一方面，如果在一个有百万节点组成的网络当中有一个由1000个机器组成的组，采用广播技术发送数据包显然也是一种浪费，因为大多数接收者对广播的消息并不感兴趣（甚至最糟糕的是他们虽然感兴趣，但不应该看到这些消息）。因此，我们需要有一种办法能够给明确定义的组发送消息，这些组的成员数量虽然很多，但相比整个网络规模却小很多。为了将数据包传递给组的成员同时又有效利用带宽，数据包可沿着生成树发送。然而，最佳生成树的使用取决于组的的密度分布。密集分布指接收者遍布在网络的大部分区域；稀疏分布指大部分网络都不属于组。如果组的分布是密集的，那么广播是一个良好的开端，因为他能有效的把数据包发到网络的每一个角落。但广播可能将到达一些不属于该组成员的路由器，因而也是一种浪费。密集模式下利用组播方式传输、通信首先需建立生成树，然后修剪生成树得到一颗有效生成树，该树只用到那些抵达组成员真正需要的链路。生成树的修剪方式有许多种，距离矢量路由算法便是众2多生成树修剪方式重的一种。其基本算法是逆向路径转发。组播路由协议是一个以距离矢量路由算法工作的组播路由协议。本文写作思路如下：先描述组播相关内容，比如其概念、工作方式以及其分类等等。其次在讲述距离矢量路由算法，给出其概念以及分析其存在的问题，通过举例详细分析。最后，讲述距离矢量路由组播协议相关内容。在本文写作过程当中我引用了文献[1][2][3]，以及参考课本内容。1.组播与距离矢量路由算法1.1组播的几个概念IP组播(也称多址广播或多播)技术，是一种允许一台或多台主机(组播源)发送单一数据包到多台主机(一次的，同时的)的TCP／IP网络技术。组播作为一点对多点的通信，是节省网络带宽的有效方法之一[1]。组播路由的前提：主机一路由协议存在于网络中的客户端、服务器以及路由器之间。使用这些协议，接收端(主机)可通告其直接相连的路由器表示它们对当前网络中其它主机发送的组播数据流感兴趣IGMP为组播路由提供了一个基本的环境。利用IGMP协议，组播路由器可以判断在与自己连接的任何一个网络上，是否存在组播组的成员。IGMP的工作方式主要分为两个阶段。○1建立组成员，当主机加入一个新的组播组时，它把一个IGMP报文发送给直连路由器，通告其成为组成员。本地组播路由器收到这个报文后，向互联网上的其它组播路由器传播这个组成员信息，以建立必要的路由。○2刷新组成员，直连路由器周期性的询问本地子网上的主机，以便确定当前各个组中有哪些主机，如果经过若干轮询问之后，某个组始终没有成员，直连路由器就认为该组中不再有本网络中的主机，于是停止向其它组播路由器通告该组的成员信息。密集模式(DM)组播路由协议：组播路由协议用于生成由组播源到组播组所有成员间的分布树。根据组播组成员在网络中的分布情况，可以把组播路由协议分为密集模式协议和稀疏模式协议。密集模式Dense—Mode(DM)假设组播组的成员密集分布在网络中，每个子网至少含有一个成员。密集模式组播路由协议依靠泛洪算法(Flooding)把信息传递给每个路由器的所有接口。密集模式下的距离矢量组播路由协议DVMRP(DistanceVectorMulticastRoutingProtoc01)是典型的密集模式组播路由协议。DVMRP采用“扩散／剪枝”机制。通过逆向路径转发ReservePathForwarding(RPF)检查，动态的创建最短路径树ShortestPathTree(SPT)。图1(a)网络中有两个组：组1和组2.有些路由器连接的主机属于其中的一个组或者同时属于两个组，如图所示。最左边的一颗生成树如图1(b)所示。此树可用于广播，对于组播来说则过度了，这从下面显示的两个修剪版本可见一斑。在图1(c)中，所有不通往组1成员的主机的链路已被删除，结果是一颗针对最左边路由器发送到组1的生成树。数据包的转发只能沿着这棵树进行，可见这比广播树有效，因为这里只有7条链路而不是10条链路。图1(d)显示了一颗针对组2修剪后的组播生成树。相比广播树，它也更加有效，此时只有5条链路，这个例子表明，不同的组播树有不同的生成树。图1组播例稀疏模式Sparse—Mode(SM)组播适用于组播组成员稀疏分布，而带宽不是很宽裕的网络中。这种模式下用户数量不一定很少，但分布范围较广。稀疏模式在网络中构建一些虚拟的数据交换地点作为汇聚点RP。RP负责管理数据源和接收者之间的通信。组播源端向组成员发送数据前必须在RP进行注册，然后把数据发向RP；接收端为了接收数据，需要通过最近的路由器加入到RP中，建立从RP到接收者的共享树。RP接收并复制数据，沿着共享树路径把数据转发给接收者。复制仅仅在共享树的分枝进行，而且这个过程能自动重复直到数据到达最终目的地。组播转发：在组播模型中，源主机向IP信息包目的地址段内的组播组地址所表示的任意主机组传送信息。和单播模型相反，组播路由器不能把转发决定建立在信息包中的目的地址基础上。这些路由器必须将组播信息包转发到多个外部接口上，以便能传送到所有的接收站点。上述要求使得组播转发过程比单播转发过程更为复杂。下面介绍逆向路径转发(RPF)的概念，这一概念是组播转发过程的基础。逆向路径转发：实际上，所有的组播路由协议利用RPF或输入接口检查的某些形式作为决定是否转发或丢弃输入的组播信息包的主要机制。当组播信息包到达路由器时，路由器对信息包进行RPF检查。如果RPF检查成功了，信息包被转发，否则，它被丢弃。当信息通过有源橱的时候，RPF检查机制进行如下工作：l.路由器检查到达组播信息包的源地址，以确定此信息包经过的是什么接口，这些接口是否在从源到此的路径上2．如果信息包在可返回源的接口上到达，则RPF检查成功，且信息包被转发。3.如果RPF检查失败，丢弃组播信息包。组播路由器如何确定哪些接口是在可以返回源站点的路由上取决于所使用的组播路由协议。在一些实例中，组播路由协议维护分隔的组播路由表，并使用这张表来进行RPF检查。DVMRP就是一个很好的例子。图2举例说明了RPF检查的过程。本例使用分隔的组播路由表图2RPF检查例来自源1.1.1.1的组播信息包在接口S0被收到。组播路由表的检查显示指定的接口应该是S1，而不是S0。因此RPF检查失败，组播信息包被丢弃。图3是来自源1.1.1.1的组播信息包到达路由器的另一个例子，这一次通过了接口S1。图3RPF检查例1.2距离矢量路由算法距离矢量路由算法简介[2]：距离矢量路由选择算法也称为BellmanFord算法和FordFulkerson算法，它最初用于ARPANET路由协议中。并用于因特网的早期版本，称为RIP。在该算法中．每个路由器维持有一张子网中每个以其他路由器为索引的路由选择表．表中的每一个项目都对应于子网中的每个路由器。此表项有两个部分，即希望使用的到目的地的输出线路和估计到达目的地所需要的时间或距离。距离的度量可能是跳数，或者其它因素。举例：假设使用延迟作为距离度量，并且路由器知道它到达每个邻居的延迟。每隔T毫秒，每个路由器向它的邻居发送一个列表，该列表包含了它到每一个目标的延迟估计值；同时，它也从每个邻居那里接收到一个类似的表。想象一个路由器接收了来自邻居X的延迟为m毫秒，那么它也能明白在mXi毫秒之内经过X可以到达路由器i。对每个邻居都执行这样的计算，最终可以发现每个目标的最佳估计值，然后在新的路由表中使用这个最佳估计值以及对应的出境线路，在上述到目标距离的计算过程中没有使用老的路由表。这个更新过程如图4所示。其中图4(a)显示了一个网络。图4(b)的前4列显示了J从邻居路由器接收到的延迟矢量。A声称它到B有12毫秒的延迟，到C有25毫秒的延迟，等等。假定J已经测量和估计了它到邻居A、I、H和K的延迟分别为8、10、12和6毫秒。现在考虑J如何计算它到路由器G的新路径。图4距离矢量路由算法例它知道在8毫秒之内可以到达A，并且A声称可以在18毫秒内到达G，所以J知道，如果它将那些目标地址为G的数据包转发给A的话，那么到G的延迟为26毫秒。类似的，它计算出经过I、H和K到达G的延迟分别为41（即31+10）、18（即6+12）和37（即31+6）毫秒，所用的路径是经过H的