《高级计算机网络》由会员分享，可在线阅读，更多相关《高级计算机网络（68页珍藏版）》请在金锄头文库上搜索。
1、 高级计算机网络高级计算机网络袍暮钻攘脸手撂儒逞腺饺噶流漆框坎谊铁镍医懈汉赛羌凌坦薯极辣穴壶兆高级计算机网络高级计算机网络7/29/20241史忠植 高级计算机网络内容提要内容提要6.1 6.1 概述概述6.2IP多播协议多播协议6.3多播路由多播路由6.4扩散技术扩散技术6.5跨越树的多播路由算法跨越树的多播路由算法6.6约束约束Steiner树树6.7反向路径广播反向路径广播6.8截断的反向路径广播截断的反向路径广播6.9反向路径多播反向路径多播愈墟彼氰时鉴皆拉厦卸讥间仪旁欠程秀犬窥济墅钎园举邮蹋尸答嫂盂豫飞高级计算机网络高级计算机网络7/29/20242史忠植 高级计算机网络内容提要内容
2、提要6.10核心树核心树6.11路由多播选择算法路由多播选择算法KMB6.12动态多播路由选择算法动态多播路由选择算法VTDM6.13限界最短多播算法限界最短多播算法BSMA6.14适用于光纤网络的多播的适用于光纤网络的多播的MZQ算法算法6.15多播的应用多播的应用 卓辈莱哆识蛾插襄混怠苔情奈厄徒坎猜外山啼线耀垦伶骆求然矽胃束被彰高级计算机网络高级计算机网络7/29/20243史忠植 高级计算机网络6.1 6.1 概述概述 将分组同时发往所有目的地称做广播（将分组同时发往所有目的地称做广播（broadcastingbroadcasting）。）。 单单源源，多多目目的的的的通通信信方方式式称
3、称之之为为多多点点通通信信（multipointcommunication），通通常常只只在在分分叉叉的的时时候候复复制制信信息息，又又称称为为多多播（播（multicast）。）。 在在单单播播的的环环境境下下，每每个个结结点点一一次次只只能能给给另另一一个个结结点点发发出出信信息息。在在多多播播的的环环境境下下，每每个个结结点点一一次次可可以以有有效效的的把把一一个个打打包包的的信信息息同同时时发发往往多多个个目目标标。必必须须有有支支持持IPIP多多播播的的结结点点处处理理系系统统和和TCP/IPTCP/IP栈，网络中的结点才能顺利的进行多播。栈，网络中的结点才能顺利的进行多播。 勿圭武
4、捷肋郧掐旋预他靡游悲端禾敖捌窜丹丙塑宣褂阑怜瓦破味砧腾契窥高级计算机网络高级计算机网络7/29/20244史忠植 高级计算机网络6.1 6.1 概述概述 多多信信道道IPIP包包和和单单信信道道IPIP包包的的主主要要在在于于头头部部目目标标地地址址域域的的“组组 地地 址址 ”， 多多 播播 使使 用用 D D类类 地地 址址 ， 也也 就就 是是 在在 244.0.0.0-244.0.0.0-239.255.255.255239.255.255.255之间的地址。之间的地址。多播的特性： 1. 1. 可靠性：对不同类型的应用是否有不同的可靠性模型？可靠性：对不同类型的应用是否有不同的可靠性
5、模型？ 2. 2. 允允许许动动态态加加入入和和离离开开：每每个个对对话话过过程程必必须须是是接接受受者者可可控控制的。制的。 3. 3. 地址：地址： 在每层上如何对各组编址在每层上如何对各组编址 在在IPIP层层以以上上的的各各层层是是否否需需要要标标识识组组，如如果果需需要要，怎怎样样标识？标识？ 4. 4. 方向性：方向性： 一对多一对多 或者或者 多对多多对多 转送者是否是接受者的一个子集？转送者是否是接受者的一个子集？ 妖啼专除辞弗吠俊鄙傀绦齐褥张砷讼拖呵绣纹哨纬层图疫淤御世励床点嚼高级计算机网络高级计算机网络7/29/20245史忠植 高级计算机网络6.1 6.1 概述概述啼笺庚
6、方塔惊湍王草凝药褥养最戎葫荷美浚臭仑贼钦趣返聪仿萝葱一捉双高级计算机网络高级计算机网络7/29/20246史忠植 高级计算机网络6.1 6.1 概述概述颓呀悠膜欺幕朵富见饲络析逐隔峨援皂当探奠台照巡缕回症苫漱束渐钝娱高级计算机网络高级计算机网络7/29/20247史忠植 高级计算机网络6.2 IP 6.2 IP 多播协议多播协议80年年代代开开始始研研究究，1988年年Stanford大大学学实实施施了了第第一一次次多多目目通通话话，1992年年Internet程程特特别别小小组组（IETF）定定义义和和发发布布了了一一个个多多播播的的网网络络标标准准，用用于于建建立立多多播播主主干干网网（M
7、BONE），即即在在Internet上上运运行行的的单单路路广广播播和和多多播播综综合合网网络络。MBONE于于1993年年刹刹那那间间名名声声远远扬扬。1995年年，Cisco公公司司和和Lucent公公司司开开始始销销售售支支持持多多播播的的路路由由器器和和交交换换机机，一一年年后后依依赖赖多多播播的的应应用用产产品品开开始始上上市。市。IP多多播播的的最最早早实实施施方方案案依依赖赖于于传传统统的的竭竭尽尽全全力力方方法法和和UserDatagranProtoco1，但它们不能保证多播数据流的可靠传输。，但它们不能保证多播数据流的可靠传输。寿勘硬洋租获贴寡悟矮塘挖婶嗣缴筷厚卉斗栏捡曙歹蘑
8、某意雍箍议宁耐胖高级计算机网络高级计算机网络7/29/20248史忠植 高级计算机网络6.2 IP 6.2 IP 多播协议多播协议HP的的Internet群管群管JF协议（协议（LGMP）ProtocolIndependentMu1ticast、 Mu1ticastBorderGatewayProtocolHierarchical DVMRP（ Distance Vector MulticastRoutingProtocol）棠柯皮脾洋四谐查款钦阳密动年蜘嫂矾烟歇泄冰疯呛短艺柿本疹隅啡拈叉高级计算机网络高级计算机网络7/29/20249史忠植 高级计算机网络6.36.3多播路由多播路由共享树（
9、共享树（sharedtree）源源根根结结点点的的最最短短路路径径树树（SRSPTSRSPT： source source rooted rooted shortest path treeshortest path tree）。）。嘿愤劫只袄鹏替滨爪郧粱搀福铅云凸铀凝承春桥解膝串碳了逸键沤驴磅举高级计算机网络高级计算机网络7/29/202410史忠植 高级计算机网络共享树（共享树（sharedtree）共共享享树树方方法法中中使使用用一一个个中中央央多多播播路路由由器器，有有时时候候又又称称为为核核心心路路由由器器。需需要要进进行行多多播播的的源源结结点点将将他他们们所所要要传传递递的的信信息
10、息包包都都传传给给这这个个核核心心路路由由器器，然然后后由由这这个个核核心心路路由由器器通通过过一一棵棵共共享享树树将将信信息息包包一一个个一一个个的的传传给给组组中中的的每每一一个个接接收收结结点点。每每个个组组中中只只要要建建立立一一棵棵共共享享树树就就可可以以了了，而而不不是是象象在在SRSPTSRSPT中中需需要要为为组组中中的的每每个个源源结结点点建建立立一一棵棵树树。与与SRSPTSRSPT算算法法相相比比，共共享享树树对对路路由由器器和和网网络络带带宽宽（bandwidthbandwidth）的的需需求求更更小小。在在CBTCBT和和PIMPIM协议中使用共享树的思想来传递信息包
11、。协议中使用共享树的思想来传递信息包。枪锥功型洲啸彰嘲允聚旨栏涤陵搽光扮匆搀暂名么压卑富雷喷山溢斥龋腊高级计算机网络高级计算机网络7/29/202411史忠植 高级计算机网络 源根结点的最短路径树源根结点的最短路径树这这种种源源根根结结点点的的最最短短路路径径树树只只能能建建立立在在具具有有多多播播功功能能的的路路由由器器上上。它它为为每每个个组组中中的的每每个个源源结结点点建建立立一一棵棵树树，这这棵棵树树以以该该传传送送结结点点为为根根，使使其其与与所所有有的的接接收收结结点点相相连连。一一般般而而言言，该该组组中中有有多多少少个个源源结结点点，就就需需建建立多少棵这样的树。立多少棵这样的
12、树。 一一棵棵这这种种基基于于源源结结点点的的树树将将一一个个特特定定的的源源结结点点与与所所有有的的接接收收结结点点相相连连，并并被被称称为为“源源根根结结点点的的最最短短路路径径树树”。这这些些路路径径并并不不需需要要通通过过一一个个特特定定的的中中央央多多播播路路由由器器。等等到到由由协协议议将将一一棵棵这这样样的的树树建建成成后后，这这棵棵树树的的源源结结点点就就可可以以沿沿着着这这棵棵树树上上的的路路径径将将所所要要传传递递的的信信息传到它的每一个接收结点。息传到它的每一个接收结点。阔安赫搐配怠洗荔没崎距逗措式隙疤爬袖柜舆放表溶霓降房罗襄昼惩屿航高级计算机网络高级计算机网络7/29/
13、202412史忠植 高级计算机网络SRSPT树的优点树的优点（1）使用经典的单信道路由表很容易计算）使用经典的单信道路由表很容易计算SRSPT树；树；（2）可可以以有有效效的的实实现现分分布布式式处处理理不不需需要要整整个个网网络络的的拓扑结构；拓扑结构； （3）返回的路径中不会存在回路。）返回的路径中不会存在回路。较邱哨狙妈旭缩苗具耶柒札牲文糖皖吉蜜歼觉蚜公旅甥婚蕊惹踪勤灌妖啸高级计算机网络高级计算机网络7/29/202413史忠植 高级计算机网络SRSPTSRSPT树的缺点树的缺点 （1）没有最小化整个分布式处理的代价；）没有最小化整个分布式处理的代价； （2）可伸缩性不好；）可伸缩性不好
14、；（3）在在每每个个路路由由器器上上都都要要保保存存每每个个组组中中每每个个源源结结点的点的SRSPT树的信息；树的信息； （4）如如果果下下层层的的单单信信道道路路由由是是非非对对称称的的则则可可能能会会导致失败。导致失败。包胖莉零贱嫉码鸥届殆削个瘩扁菱拆疟次学魄谨胚抽鹅滁渐域邯诬略宴毁高级计算机网络高级计算机网络7/29/202414史忠植 高级计算机网络性能指标性能指标(1)低低延延迟迟。将将源源结结点点到到目目的的结结点点的的端端到到端端的的延延迟迟与与点点到到点点的单信道最短路径的延迟相比较；的单信道最短路径的延迟相比较；（2）低低代代价价。全全部部的的带带宽宽消消耗耗以以及及保保存
15、存树树状状态态信信息息所所需需的的代价；代价；（3）轻的网络拥塞）轻的网络拥塞犹思摔粮光闰吭锌朔人劲诌浴滩娶侵渗屋丑搐农胁号潭挟邑殿呼芒苦挤啥高级计算机网络高级计算机网络7/29/202415史忠植 高级计算机网络多点路由算法的需求多点路由算法的需求（1）支支持持可可靠靠的的传传输输。连连接接失失败败不不应应该该增增加加延延迟迟或或者者减减少少可用的资源可用的资源（2）对于得到最佳路由所需要的一些考虑。）对于得到最佳路由所需要的一些考虑。1：所需付出的代价（对带宽的消耗）：所需付出的代价（对带宽的消耗）2：端到端的延迟（所需跨越的结点数）：端到端的延迟（所需跨越的结点数）（3）最小化对网络的负
16、担。）最小化对网络的负担。1：避免回路：避免回路2：避免在一些连接或子网上出现网络拥塞：避免在一些连接或子网上出现网络拥塞（4）最小化在路由器中所需存储的状态数量。）最小化在路由器中所需存储的状态数量。搐固媳鬼粗怨戈姥幌咎洱另鼠定蒙叹磷车陡赁预轮政抒闰匡硬铂热硝隘结高级计算机网络高级计算机网络7/29/202416史忠植 高级计算机网络密集模式密集模式 密密集集模模式式假假设设多多播播组组的的成成员员密密集集分分布布在在网网络络中中，每每个个子子网网至至少少含含一一个个成成员员。密密集集模模式式还还需需要要充充足足的的带带宽宽。DVMRP,MOSPF和和PIM-DM都都是是密密集集模模式式路路
17、由由选选 择择 协协 议议 。 密密 集集 模模 式式 路路 由由 选选 择择 协协 议议 依依 靠靠 扩扩 散散（flooding）技术把信息传播到整个网络的路由器上。）技术把信息传播到整个网络的路由器上。邑熊滩茎便片鸟余杆蜜搀梁您孺略社屉汤筏着睦习腮辱奴酥蒜牲队磋芹窍高级计算机网络高级计算机网络7/29/202417史忠植 高级计算机网络稀疏模式稀疏模式 假假设设多多播播组组的的成成员员稀稀疏疏分分布布在在网网络络中中，而而且且网网络络可可以以提提供供的的带带宽宽不不是是很很宽宽裕裕。在在稀稀疏疏模模式式下下，用用户户可可能能分分散散在在Intent的的各各个个部部分分，也也可可能能是是被
18、被ISDN专专线线连连接接起起来来的的。这这种种模模式式下下用用户户不不一一定定很很少少，只只是是它它们们分分散的范围很广。散的范围很广。稠冷翟冒搂翠澈勺今妨咬尝舵遁苑洋图稠鹏叁妊蹿砌郁釉厘粮散推破筐沟高级计算机网络高级计算机网络7/29/202418史忠植 高级计算机网络6.4 6.4 扩散技术扩散技术1路由器接收到要发往多播组的一个报文。路由器接收到要发往多播组的一个报文。2路由器用协议机制决定这是不是第一次收到该报文。路由器用协议机制决定这是不是第一次收到该报文。3如如果果它它是是第第一一次次收收到到该该报报文文，路路由由器器将将该该报报文文发发往往Internet上上除除了了它它的的来
19、来源源的的所所有有接接口口。这这保保证证了了多多播播报报文文将将到到达达所所有有的的路由器。路由器。 如果路由器以前曾收到该报文，就把它丢弃。如果路由器以前曾收到该报文，就把它丢弃。狗阻凤彼勾土痔练一湍歇孪失抄嫉乳乎纠炸苔名玫暮补挚弄瞅凯舷但西担高级计算机网络高级计算机网络7/29/202419史忠植 高级计算机网络扩散技术局限性扩散技术局限性1扩散技术不适用于大规模网络，如扩散技术不适用于大规模网络，如Internet。2同样不适用于广域网，因为它产生大量复制包。同样不适用于广域网，因为它产生大量复制包。3扩扩散散技技术术使使用用Internet网网上上的的所所有有可可用用路路径径，网网络络
20、上上所所有有路路径的流量容易引起拥塞。径的流量容易引起拥塞。4因因为为每每个个路路由由器器必必须须为为最最近近接接收收的的包包维维护护一一张张表表，所所以以并并不是很有效的使用路由器的内存。不是很有效的使用路由器的内存。曲偿倡缄漆域榷峙绊二恃势姆攀召甲烟烧发恶拌徘紫恼逆躇铜涧会篷乞邀高级计算机网络高级计算机网络7/29/202420史忠植 高级计算机网络建立生成树的步骤建立生成树的步骤1选选择择一一转转送送设设备备作作为为根根：刚刚开开始始所所有有的的转转送送设设备备先先假假设设自自身身为为根根，告诉其他设备它作为根连接。告诉其他设备它作为根连接。总总的的来来说说，优优先先级级低低的的设设备备
21、设设为为根根。如如果果优优先先级级相相同同，MAC地地址址低低的的设设备备设为根。设为根。2估估计计路路径径成成本本：如如果果一一转转送送设设备备接接到到另另一一设设备备的的包包，认认为为存存在在更更好好的路径，就不再告诉别的设备自身是根，而是告诉别的设备更优的根。的路径，就不再告诉别的设备自身是根，而是告诉别的设备更优的根。3选选择择根根端端口口，并并且且在在每每个个局局域域网网制制定定一一个个转转送送设设备备：最最终终，每每个个设设备都认同了最佳转送设备，该设备就成为根。备都认同了最佳转送设备，该设备就成为根。设设备备的的根根端端口口提提供供了了指指向向根根转转送送设设备备的的最最低低成成
22、本本路路径径。路路径径成成本本相相同同时时，端端口口接接头头优优先先级级低低的的成成为为根根端端口口。如如果果接接口口优优先先级级再再相相同同，具具低低优优先先级级的的设备上的断口为根端口。设备上的断口为根端口。4.每每个个子子网网指指定定一一个个端端口口（路路由由器器）：生生成成树树算算法法设设指指定定连连接接转转送送设设备备和局域网的端口位置顶端口。尤其当子网上的设备靠近根时。和局域网的端口位置顶端口。尤其当子网上的设备靠近根时。窘悲惹羹煽昨赘例妄源哪砚凑恍戮画灾贬寐斋弄蝗瞪常恢抵周隆吕饱碘爬高级计算机网络高级计算机网络7/29/202421史忠植 高级计算机网络建立生成树的步骤建立生成树
23、的步骤诉滤棱奢旷驱壤释虎终扁绑脓蜗锨蚊电代鼎狠圃照察篡迟夫砚骸首岳债引高级计算机网络高级计算机网络7/29/202422史忠植 高级计算机网络建立生成树的步骤建立生成树的步骤档殷糕嫉慰姿问绣汁勘铬派芦回调躺塌琉斩榔稽囱屉沟尾卷歪味松廓冷拆高级计算机网络高级计算机网络7/29/202423史忠植 高级计算机网络6.7 6.7 反向路径广播反向路径广播 无无论论是是子子网网上上哪哪一一个个源源，反反向向路路径径广广播播（reverse pathbroadcasting,RPB）算算法法针针对对每每一一个个组组建建立立一一棵棵生生成成树树，提提供供了了源源和和组组的的成成员员之之间间的的有有效效路路
24、径径。这这样样的的生生成成树树根根植植于于直直接接和和源源连连接接的的子子网网上上，意意味味着着每每个个活活跃跃的的源源-组组队队都都有有一一棵棵生生成成树树。路由器利用逆向路径广播算法建立根植于源的树路由器利用逆向路径广播算法建立根植于源的树别灼镐媚膘是橙凄鹿辊蜂坊搐拱减嘴弃考吝姓崇暖证豫厦球萝毒抒疾每伯高级计算机网络高级计算机网络7/29/202424史忠植 高级计算机网络反向路径广播转送算法反向路径广播转送算法许熏肮轨逻猩筏姬幢岿棘岿楔慑聚茬伺蒋冯毖搓离绣弟糠簿宅砚刘践裳溜高级计算机网络高级计算机网络7/29/202425史忠植 高级计算机网络反向路径广播转送算法反向路径广播转送算法 链
25、链接接状状态态路路由由选选择择协协议议使使用用拓拓扑扑数数据据库库来来确确认认相相邻邻的的路路由由器器是是否否在在子子链链接接上上，也也就就是是考考虑虑该该路路由由器器是是否否在在相相邻邻路路由由器器回回溯到源的最短路径上。溯到源的最短路径上。 距距离离向向量量路路由由选选择择协协议议使使用用邻邻居居发发布布的的源源-组组对对的的前前一一站站距距，或或者者翻翻转转该该路路由由来来决决定定下下一一相相邻邻路路由由认认为为该该路路由由在在到到源源的的最短路径上。最短路径上。颧碗税铱恶杏套掸政浆歧兄戚碳篓于阶峰卓斩炬订患醉胃踪房火喊功伦咬高级计算机网络高级计算机网络7/29/202426史忠植 高级
26、计算机网络反向路径广播的例子反向路径广播的例子值脯科迟勃雾卿缓蜀诺掣馈宦嘛大详萤川瞅旅镀譬仆褂愈蕾避揍洗眩崭贸高级计算机网络高级计算机网络7/29/202427史忠植 高级计算机网络反向路径广播的例子反向路径广播的例子 从从路路由由器器A A收收到到报报文文，确确认认连连接接1 1是是源源- -组组对对的的父父母链。母链。 把把报报文文发发往往任任何何含含有有小小组组成成员员的的叶叶子子子子网网，如如发发往连接往连接4 4、连接、连接5 5。 从从路路由由选选择择信信息息交交换换中中得得知知路路由由器器C C认认为为连连接接2 2是是源源- -组对的父母链，于是不再将报文发往连接组对的父母链，
27、于是不再将报文发往连接3 3。 路路由由器器C C将将丢丢弃弃从从连连接接3 3来来的的报报文文，因因为为是是从从源源- -组对的非父母链上来的。组对的非父母链上来的。键匝瘸逢堪侧死令带职虏凸撑惑笔流阅呜沛蔗污阁蔷彼牺铡痪铜惯赖跃网高级计算机网络高级计算机网络7/29/202428史忠植 高级计算机网络6.8 6.8 截断的反向路径广播截断的反向路径广播 截截断断的的反反向向路路径径广广播播（truncated truncated reverse reverse path path broadcasting, broadcasting, TRPBTRPB）改改进进了了上上一一个个算算法法中中不
28、不考考虑虑多多播播组组的的成成员员限限制制的的问问题题。它它使使用用了了IGMPIGMP来来决决定定某某个个子子网网上上是是否否存存在在该该广广播播组组的的成成员员，并并以以此此为为依依据据截截断断原原来来构构造造的的跨跨越越树树上上的的一一些些枝枝叶叶。一一旦旦弄弄清清楚楚这这一一点点，TRPBTRPB不不再再往往不不含含组组成成员员的的叶叶子子网网上上发发送送报报文文。路路由由器器从从扩扩展展传传送送树树上上剪剪除除不不含含组组成成员员的的叶叶子子网网，这这一排除不在最短路径上的接口的过程称为一排除不在最短路径上的接口的过程称为“截断截断”。铜谓起幻昂鲤竹岁撅触纳融绍爵笺纤一凳棋峪陶祝贼纺
29、踪舀搞澜寞束闷奔高级计算机网络高级计算机网络7/29/202429史忠植 高级计算机网络截断的反向路径广播算法的截断的反向路径广播算法的例子例子铭粥谈观瞻晋霖髓曼葬砚贡绎云产辆你披韵舒栏丹就峪迈醚寐岭屉畜硷毗高级计算机网络高级计算机网络7/29/202430史忠植 高级计算机网络TRPBTRPB源源通通过过父父路路由由器器连连接接入入路路由由器器，多多播播组组的的成成员员第第一一组组用用G1G1表表示示、第二组第二组G2G2、第三组、第三组G3G3与路由器下属的转送装置相连。与路由器下属的转送装置相连。当路由器接收了源当路由器接收了源-G1-G1对的一多播报文，它将：对的一多播报文，它将： 因
30、因为为接接口口2 2至至少少含含有有第第一一组组的的一一个个成成员员，路路由由器器把把报报文文发往接口发往接口2 2。 当当且且仅仅当当该该路路由由器器的的一一个个下下属属路路由由器器认认为为接接口口3 3是是它它的源的源-G1-G1对的父母链的一部分，该路由器才把报文发往接口对的父母链的一部分，该路由器才把报文发往接口3 3。 接口接口4 4没有目标组的成员，报文不发往接口没有目标组的成员，报文不发往接口4 4。TRPB虽虽然然避避免免了了叶叶子子网网中中的的不不必必要要的的流流量量，但但是是在在建建立立分配树的枝干的时候没有考虑是否含组成员的问题。分配树的枝干的时候没有考虑是否含组成员的问
31、题。挞铃辨邀及回瞥吓铸毡螟邪虹宫穗乐坍悸悲愉惭缚绸秆灼岳用年负录缅谎高级计算机网络高级计算机网络7/29/202431史忠植 高级计算机网络6.9 6.9 反向路径多播反向路径多播反反 向向 路路 径径 多多 播播 （ reverse reverse path path multicasting,RPMmulticasting,RPM）是是对对于于RPBRPB和和TRPBTRPB的的改改进进。具具体体而而言言，如如果果一一个个接接收收接接口口可可以以用用于于向向多多播播报报文文的的源源发发送送单单信信道道广广播播报报文文，路路由由器器向向除除了了接收接口以外的所有接口发送多播报文。接收接口以外
32、的所有接口发送多播报文。换换句句话话说说，RPMRPM建建立立的的传传送送树树只只覆覆盖盖了了广广播播组组成成员员和和到到含含广广播播组组成成员员子子网网最最短短路路径径沿沿途途径径过过的的路路由由器器和和子子网网。RPMRPM截截断断了了根根植植于于源源的的生生成成树树，路路由由选选择择协协议议只只向向通通往往目目标标组组成成员员的的枝枝干干发发送送报文。报文。毋由邮眷炊贷拖称沛垂舀死梢堕素缚贯泼蛛烧搏罐涸层阀舞娶梳霸辛回敌高级计算机网络高级计算机网络7/29/202432史忠植 高级计算机网络RPMRPM半庭凿羚凑疯眩畅檬勤烟潭濒饺缀和揍侍小咸散圣絮瑶落茵把视蚕挨尽晤高级计算机网络高级计算
33、机网络7/29/202433史忠植 高级计算机网络工作原理工作原理上上级级路路由由器器收收到到截截断断信信息息后后储储存存起起来来。如如果果从从所所有有的的子子链链收收到到截截断断信信息息，该该路路由由器器也也往往它它的的上上级级路路由由器器发发送送截截断断信信息息。这这个个过过程程产产生生的的多多播播树树只只含含有有通通向向活活跃组成员的枝干。跃组成员的枝干。协协议议不不时时的的更更新新多多播播树树，更更新新后后每每个个路路由由器器清清除除内内存存中中的的所所有有剪剪除除信信息息，并并且且将将受受到到的的下下一一个个多多播播报报文文送送往往所所有有的的子子链链。这这样样又又重重新新开开始始了
34、了定定义义多多播播树树的的新新一轮过程。一轮过程。讳潍扣和尸猪朽拉甭趾郎猛搏靠足耻猴惟村蕊疗敷篷推臭注参莉菇埠郭闽高级计算机网络高级计算机网络7/29/202434史忠植 高级计算机网络工作原理工作原理组组成成员员的的动动态态特特征征意意味味着着树树需需要要定定期期的的更更新新。也也就就是是说说，多多播播报报文文必必须须定定期期的的发发往往InternetInternet网网络络中中的的每每个个路路由由器器。这这就就使使得得在在大大规规模模传传送送服服务务如如在在InternetInternet上上的的传传送送问问题题不不容容忽忽视视，而而且且，每每个个路路由由器器必必须须保保留留关关于于源源
35、和和组组的的所所有有状状态态信信息息。尽尽管管这这对对于于小小网网络络来来说说不不构构成成威威胁胁，但但是是当当源源的的数数目目和和多多播播组组成成员员大大幅幅增增加加时就是一个严重的问题。时就是一个严重的问题。崩泣钥熬瞳孝官猿傀供围情吏翼柿刃院训昏妈裔葫势容框痈唐耳坞疲鲁势高级计算机网络高级计算机网络7/29/202435史忠植 高级计算机网络6.10 6.10 核心树核心树核核心心树树（core-based core-based tree, tree, CBTCBT）算算法法将将建建立立一一棵棵被被小小组组中中所所有有的的发发送送者者和和接接收收者者共共享享的的传传送送树树( (图图6.1
36、0)6.10)，而而不不是是为为每每一一个个源源- -组组对对建建立立一一棵棵树树。使使用用CBTCBT算算法法时时，无无论论报报文文是是从从那那个个源源发发出出的的，路路由由器器将将多信道信息沿着相同的传送树来传递。多信道信息沿着相同的传送树来传递。共共享享树树途途径径最最显显著著的的优优势势是是能能够够很很好好的的适适应应大大规规模模网网络络。然然而而，CBTCBT可可能能导导致致在在核核心心路路由由器器附附近近的的流流量量集集中中和和瓶瓶颈颈问问题题。这这是是因因为为从从任任意意源源结结点点发发出出的的信信息息在在接近核心时，都沿着相同的连接。接近核心时，都沿着相同的连接。木袋豌咱奈抚熊
37、矗捍岭铝闲呆滦甘秽彬亮晦余趾投订东艘魏务职呢疡蛊括高级计算机网络高级计算机网络7/29/202436史忠植 高级计算机网络CBTCBT酚兵哥哇艰胁茸剑土朽耍员院砚肖林肄避驳赠檄帧遍霹侯歹擎堪闰傍预泻高级计算机网络高级计算机网络7/29/202437史忠植 高级计算机网络设计目的设计目的 (1) (1) CBTCBT是是用用于于大大规规模模网网络络，处处理理过过程程中中只只需需要要少少量量的的内内存存和和带带宽宽资资源源。因因为为CBTCBT不不针针对对于于源源，尤尤其其适适合于多发送者的应用程序。合于多发送者的应用程序。 (2) (2) CBTCBT时时健健壮壮的的多多播播路路由由选选择择算算
38、法法。为为了了获获得得健健壮的多播传送树，核心将放置在最佳位置。壮的多播传送树，核心将放置在最佳位置。 (3)(3)和和其其他他多多播播路路由由选选择择协协议议比比较较而而言言，CBTCBT协协议议比较简单。简单性能导致性能的提高。比较简单。简单性能导致性能的提高。 (4)CBT(4)CBT路路由由选选择择算算法法适适度度利利于于协协议议的的。任任何何地地方方都都可可以以安安装装，并并且且支支持持域域间间多多信信道道路路由由选选择择。CBTCBT与与CBMRPCBMRP有有着着良良好好的的协协同同工工作作的的机机制制，CBMRPCBMRP是是一一种种能能够够普遍连接不同种类的多播域的协议。普遍
39、连接不同种类的多播域的协议。脊禁陪盅硫釉谗诞汪咙杂脂候安更拌坚岁磷勒屹洛佯淬腕福丘娟淮肃岁继高级计算机网络高级计算机网络7/29/202438史忠植 高级计算机网络当一主机成为多播组的成员当一主机成为多播组的成员将执行以下步骤将执行以下步骤 (1) (1)主机向所有连接广播一主机向所有连接广播一IGMPIGMP主机成员报告。主机成员报告。 (2)(2)附附近近的的一一个个具具CBTCBT算算法法的的路路由由器器唤唤醒醒加加入入树树的过程：的过程： 产生产生JOIN_REQUESTJOIN_REQUEST信息信息 将将信信息息发发往往沿沿着着导导向向组组的的核核心心路路由由器器的的路路径的下一个
40、站点。径的下一个站点。 (3)(3)核核心心路路由由或或发发送送路路由由和和核核心心路路由由之之间间的的另另一一路由器确认该信息。路由器确认该信息。循鼓孤水皿稻撤喝谓驴牺锻锦梅渝咬弧愉儒旅阀配踏衰蘸耘件损骤崩姨硅高级计算机网络高级计算机网络7/29/202439史忠植 高级计算机网络当一主机成为多播组的成员当一主机成为多播组的成员将执行以下步骤将执行以下步骤 (4)(4)请请求求加加入入的的信信息息在在它它穿穿过过的的路路由由器器暂暂时时建建立立加加入入状状态态，包包括括组组、进进入入的的接接口口和和连连出出的的接接口口。所所有有中中间路由器处理加入请求：间路由器处理加入请求： 确认加入请求是
41、从那个接口接收的。确认加入请求是从那个接口接收的。 告知信加入的主机告知信加入的主机CBTCBT传送树。传送树。 (5)(5)临临时时状状态态如如果果没没有有接接到到从从上上游游传传来来的的确确认认信信息息，将将最最终终超超时时。因因为为有有临临时时加加入入状状态态，加加入入确确认认可可以沿着加入请求来的路径返回。以沿着加入请求来的路径返回。 (6)(6)一一旦旦加加入入确确认认到到达达产产生生加加入入请请求求的的路路由由器器，发向这个组的信息将同时发往这个新的接收者。发向这个组的信息将同时发往这个新的接收者。 日享包湘獭臃希锑莹邀鹏塔烦堆呀自怨盈叭逢寇崇幸吝体缚荧诲屿深泄郧高级计算机网络高级
42、计算机网络7/29/202440史忠植 高级计算机网络CBTCBT (4)(4)请请求求加加入入的的信信息息在在它它穿穿过过的的路路由由器器暂暂时时建建立立加加入入状状态态，包包括括组组、进进入入的的接接口口和和连连出出的的接接口口。所所有有中中间路由器处理加入请求：间路由器处理加入请求： 确认加入请求是从那个接口接收的。确认加入请求是从那个接口接收的。 告知信加入的主机告知信加入的主机CBTCBT传送树。传送树。 (5)(5)临临时时状状态态如如果果没没有有接接到到从从上上游游传传来来的的确确认认信信息息，将将最最终终超超时时。因因为为有有临临时时加加入入状状态态，加加入入确确认认可可以沿着
43、加入请求来的路径返回。以沿着加入请求来的路径返回。 (6)(6)一一旦旦加加入入确确认认到到达达产产生生加加入入请请求求的的路路由由器器，发向这个组的信息将同时发往这个新的接收者。发向这个组的信息将同时发往这个新的接收者。 唉皑秸悉雪垛潦渭甘稼形谓讥悟谁你嘘踢摆棠皿哦妖恳足瞪盾沼煎渭续俱高级计算机网络高级计算机网络7/29/202441史忠植 高级计算机网络6.116.11路由多播选择算法路由多播选择算法KMBKMB理想化的多播路由选择算法应该是：理想化的多播路由选择算法应该是： 构建树时具有所想要的成本和延迟特征。构建树时具有所想要的成本和延迟特征。 算算法法可可以以适适用用于于广广播播组组
44、的的成成员员增增加加的的情情况况（如如CBTCBT），而而不不是是每每次次成成员员增增加加都都需需要要更更新新（如如SMTSMT）。）。 维护原始路由的特性。维护原始路由的特性。 不干扰正在进行的数据传送。不干扰正在进行的数据传送。 是由接收者驱动的。是由接收者驱动的。 鞘舆桐贺枉爹找驴识银皑挪寻炯亚窃娘善存霄糜烁谩顷核勺踩绦逾兄妄卫高级计算机网络高级计算机网络7/29/202442史忠植 高级计算机网络问题的形式化定义问题的形式化定义给定图给定图G=(V,E,c)V=顶点集顶点集E=边集边集c=成本函数成本函数c:EZ0+(边边非负整数非负整数)Z-顶点集顶点集:终结集合终结集合(有时用有时
45、用M表示表示)S-点集点集:非终结集合非终结集合TO:初始树初始树=s.Q:树上顶点的优先级队列树上顶点的优先级队列Vt:树上顶点树上顶点At:树上边树上边 截廓应各聋绿拷损谱迸巍锚淡那源断下增切哟瑰但址簇包隘彰评纯昼彭岸高级计算机网络高级计算机网络7/29/202443史忠植 高级计算机网络Dijkstra最短路径算法Begin. v V,将将v加到集合加到集合U,Distance(v)=cost(s,v)Distance(s)=0;从从U中删除中删除s.whileU不为空不为空do具有最小距离的任何具有最小距离的任何G的成员的成员v.U=U-v.For每个每个v的近邻的近邻w,doifme
46、mber(w,U)distance(w)=min(distance(w),cost(w,v)+distance(v);Stop.钒畔菊陕把掘亡钉惨课洗踊锯颐族我叁瞪饲淬婆审履享剩欢僧拯桓缔坦痉高级计算机网络高级计算机网络7/29/202444史忠植 高级计算机网络 Matsuyama最短成本路径启发式算法BeginT1:包含任选的包含任选的iZ的的G的子树的子树.k=1;Zk=i.找到离找到离Tk最近的最近的i Z-Zk在在Tk的基础上加入从的基础上加入从Tk到到I的最短路径建树的最短路径建树Tk+1k=k+1.Ifkp,转转T1.Ifk=p,输出结论输出结论TpStop.销摔筷骇祟钉颐掉镑岿
47、涪湃现瞎怒嗜王饥屁范贴颅赣骆阀哇捆遍拦侯座脑高级计算机网络高级计算机网络7/29/202445史忠植 高级计算机网络 KMB 算法输入：图输入：图G和顶点集和顶点集Z输出：输出：Steiner树树Th步骤：步骤：1由由G和和Z建立完全有向带权图建立完全有向带权图G1=（V1，E1，c1）。）。2找到找到G1的最小生成树。的最小生成树。3用用G中相应的最短路径替换中相应的最短路径替换T1中的一边，建立中的一边，建立G的子图的子图Gs。4找到找到Gs的最小生成树的最小生成树Ts。5.如如必必要要的的话话删删去去Ts中中的的边边，构构建建Steiner树树Th，使使得得Th中中所所有有的叶子为的叶子
48、为Steiner点。点。敖接抵侍鹰器续忿蜗歇侈穗职撼夏汁袜拖肤怒茶嘛排扎赛怖马铰扔躯纪诵高级计算机网络高级计算机网络7/29/202446史忠植 高级计算机网络KMBKMB算法算法 KMBKMB算算法法最最坏坏时时间间复复杂杂度度 O O（|S|V|S|V|2 2）。成本不大于成本不大于2 2（1-1/1-1/l l）最优成本，其中最优成本，其中l = l = SteinerSteiner树的叶结点数。树的叶结点数。舵见搏进桶负迫阜偿餐郡斑釉冉忻瑰丽滞剐拴晚庸谚庚雹往豫董洼承茫疵高级计算机网络高级计算机网络7/29/202447史忠植 高级计算机网络KMB算法的工作过程韵逸络柏君拓垫勋价红杉忻
49、物拓啦倾逃搅宰偶爱蛆贾座悬夫谓哇宋盂扒繁高级计算机网络高级计算机网络7/29/202448史忠植 高级计算机网络KMB算法的工作过程成番丰麦粥崩葛怪咕庆价索灸虞贾沿产潍缝硒牟鹃牺甸虎听芋诽魏晤蓄婆高级计算机网络高级计算机网络7/29/202449史忠植 高级计算机网络成本建模成本建模W(e, i):边边e上波长为上波长为 i的成本。的成本。如果边如果边e上上 i值不确定值不确定w值为无穷。值为无穷。cv( p, q):v结点上波长从结点上波长从 p变为变为 q的代价。的代价。如果如果v结点上波长不能从结点上波长不能从 p变为变为 qcv值为无穷。值为无穷。Ifp=q,cv( p, q)=0。C
50、(T)= v Tw(p(v),v), (v)+ v T-sCp(v)( (p(v), (v)，其中其中p(v)是树中是树中v点的父母。点的父母。浚淤牢哥滁舷舔膊宴鲜奏张秀嗜琐悔智苹似抢问想姆灶菱瞎涉粪诚锈嘘膊高级计算机网络高级计算机网络7/29/202450史忠植 高级计算机网络虚主干 虚虚主主干干是是基基本本图图中中的的一一棵棵树树，用用作作建建立立多多播播树树的的模模板板，也也就就是是说说，扩扩展展为为虚虚主主干干的的结结点点具具有有最最大大可可能能性性变变为为多多播播树树中中的的一一部部分分。如如果果一一个个结结点点有有越越多多的的路路径径穿穿过过它它，就就有有越越大大的的可可能能成成为
51、为多多播播树树的的一一部部分分。定定义义点点v vi i 的的权权重重 W(vW(vi i) ) = = 穿穿越越 v vi i的的最最短短路路径径的的数数目目，以以权权重重作作为为是是否否吸吸收收一一个个结点为虚主干的重要标准结点为虚主干的重要标准吮偶艰氖妒试寨艺巷座搐椎贵覆囚凝控戳疼倪妨巢曹网煞轧夕厕芳采瓶鸦高级计算机网络高级计算机网络7/29/202451史忠植 高级计算机网络建立虚主干的步骤 （1 1）找到图）找到图 G G中所有结点对的最短路径。中所有结点对的最短路径。（2 2）给图）给图 G G中的所有结点赋权值。中的所有结点赋权值。（3 3）找到主干结点集合）找到主干结点集合F
52、F。（4 4）为主干结点集合建立完全图。）为主干结点集合建立完全图。（5 5）在完全图上找到最小生成树。）在完全图上找到最小生成树。（6 6）把把最最小小生生成成树树上上的的边边转转化化为为图图G G上上相相应应的的最最短短路径。路径。（7 7）执执行行最最小小生生成成树树算算法法，去去除除不不必必要要的的结结点点和和连连接，获得虚主干。接，获得虚主干。这堵毖寻伎嘘针顿岛屏紫房乃度屁瘩渺好履营梨送夯糖赐患蜗既酿沿救确高级计算机网络高级计算机网络7/29/202452史忠植 高级计算机网络VTDM 路由选择算法 1.1.建立虚主干。建立虚主干。 2.2.往多播组中加入一结点：往多播组中加入一结点
53、：建立该结点到已建立的虚主干之间的最短路由。建立该结点到已建立的虚主干之间的最短路由。 虚主干到源的路由已经建立起来了。虚主干到源的路由已经建立起来了。把结点加入多播组。把结点加入多播组。 3. 3. 从多播组中去除一结点：从多播组中去除一结点：先从多播组中移出该结点。先从多播组中移出该结点。如果是叶子结点，从多播树中去掉该叶子。如果是叶子结点，从多播树中去掉该叶子。如果该结点没有下属结点，剪除多余的枝干。如果该结点没有下属结点，剪除多余的枝干。根画澎甸克址唁卜顽哗享楚娘役沤忘凳壕爸铱窖钥纽顷腺眼狄疗壹摄昭龚高级计算机网络高级计算机网络7/29/202453史忠植 高级计算机网络增加结点 (加
54、入结点 B)第一步第一步: : 如果结点如果结点B B在虚主干上，指定它为结点在虚主干上，指定它为结点A A，转到第二步。，转到第二步。 否否则则找找到到B B到到虚虚主主干干的的最最短短路路由由，把把最最短短路路由由中中不不属属于于多多播播树树的那部分加入多播树中。的那部分加入多播树中。 设虚主干上沿最短路径离设虚主干上沿最短路径离B B最近的点为最近的点为A A。 第二步第二步: : 如果如果A A已经在多播树上，转到第三步。已经在多播树上，转到第三步。 否否则则，把把从从A A到到源源结结点点的的路路由由不不在在多多播播树树上上的的那那部部分分加加入入多多播播树中。树中。 第三步第三步:
55、 : 把结点把结点B B加入多播树中。加入多播树中。厅雌络贡狱魏蚤潦酣样芦屹榜落寨宽活茸毡迹具童伟茅巡埋驶少囱抠佳瑰高级计算机网络高级计算机网络7/29/202454史忠植 高级计算机网络模拟结果 定定义义平平均均失失效效率率=使使用用算算法法A的的树树成成本本/使使用用算算法法B的的树树成本。成本。 将将VTDM与与动动态态贪贪心心法法(DG)，最最短短路路径径法法(SP)比比较较。对对于于结结点点数数增增加加的的平平均均失失效效率率，VTDM大大大大优优于于SP，优优于于DG。对对于于多多播播组组的的规规模模增增大大的的平平均均失失效效率率，VTDM在在大大规规模模组组中中大大大大优优于于
56、SP，优优于于DG。对对于于多多播播树树中中结结点点的的最最大大度度(也也就就是是数数据据复复制制的的份份数数)，VTDM大大大大小小于于SP，小于小于DG。区专扼猫晤请裤扬韭溢桃耽贰率箱甜痢骑非整四仇田溉酥郭晌抱消影捆护高级计算机网络高级计算机网络7/29/202455史忠植 高级计算机网络6.13 限界最短多播算法BSMA BSMA算算法法使使多多播播树树的的成成本本最最小小化化，并并且且保保证证所所有有的的延延迟迟小小于于预预先先设设定定的的界界限限。BSMA的的可可行行领领域域是是所所有有延延迟迟受受限的限的Steiner树。树。先先简简要要的的描描述述一一下下BSMA的的步步骤骤：首
57、首先先用用Dijkstra最最短短路路径径算算法法构构建建最最小小延延迟迟Steiner树树T0，在在可可行行的的区区域域内内不不断断的重复更新的重复更新T0以获的更低的代价。以获的更低的代价。村久谍甥瘤部两悸悉蔚藐幅滋捕蔫跑肠忘民衡蘸逆菱晌视磕姬趴湃窟涨吝高级计算机网络高级计算机网络7/29/202456史忠植 高级计算机网络BSMA成本函数的定义 使用驱动成本使用驱动成本沿路径的连接成本的总和最小化。沿路径的连接成本的总和最小化。拥塞驱动成本拥塞驱动成本沿路径的最大连接成本最小化。沿路径的最大连接成本最小化。连接成本函数连接成本函数将连接的成本和连接的使用联系起来。将连接的成本和连接的使用
58、联系起来。连接延迟函数连接延迟函数连接上排队、传输、散播的延迟。连接上排队、传输、散播的延迟。目标延迟限界函数目标延迟限界函数(DDF)从源到每个目的站点沿途的延迟的上界。从源到每个目的站点沿途的延迟的上界。救姑评喻违坏禾幕阎讫堪健那力沦窝扬尽潞跃侍雀峡钵营新烟淮撤询禹掳高级计算机网络高级计算机网络7/29/202457史忠植 高级计算机网络优化Steiner树的方法 用用Dijkstra最最短短路路径径算算法法构构建建最最小小延延迟迟Steiner树树T0的的方方法法在在前前面面已已经经介介绍绍过过了了。怎怎样样在在可可行行的的区区域域内内不不断断的的优优化化T0，使使最最后后获获得得的的树
59、树的的成成本本最最小小呢呢。这这里里要要用用到到路路径径交交换换法，优化法，优化Tj获得获得Tj+1步骤如下：步骤如下： 从从Tj中选择路径中选择路径pTj=Tj1+Tj2 p 从从图图G中中选选取取不不在在Tj中中的的新新路路径径ps替替代代从从Tj中中删删除的路径。除的路径。Tj+1=Tj1+Tj2 ps.Tj+1满足延迟受限。满足延迟受限。婚可逞阎使仅屁共灸堵掀嗣虐缘凌里笆症哲峙悍套的省稗幸湿倔尝御勤掉高级计算机网络高级计算机网络7/29/202458史忠植 高级计算机网络超边 首首先先从从Tj获获得得Tj/，树树Tj/含含源源结结点点，所所有有的的目目标标结结点点和和所所有有度度大大于
60、于2的的中中继继结结点点。Tj/的的边边称称为为超超边边，在在超超边边的的两两个个端端结结点点之之间间的的所所有有结结点点，都都是是度度为为2的的转转送送结结点点。每每条超边都是条超边都是Tj中交换的候选路径中交换的候选路径严垣吹逛狸吃霜拱啮搁拄扶波憎停限错洼略与括大邦俘箱拎烂争肌保豢帜高级计算机网络高级计算机网络7/29/202459史忠植 高级计算机网络BSMA具体算法 初始化所有超边为无标记。初始化所有超边为无标记。第一步第一步:在所有无标记边中，在所有无标记边中，BSMA选中最高成本的超边选中最高成本的超边Ph。将将Ph和另一条成本低一些的超边交换，得到的树延迟受限。和另一条成本低一些
61、的超边交换，得到的树延迟受限。以下两种情况必有一种发生：以下两种情况必有一种发生： 1.延迟限界的最短路径与延迟限界的最短路径与Ph相同。相同。标记超边，转第一步。标记超边，转第一步。 2.延迟限界的最短路径不同于延迟限界的最短路径不同于Ph. 替换替换 删除所有的超边的记号。删除所有的超边的记号。 转到第一步。转到第一步。 当所有超边都被标记后算法停止。当所有超边都被标记后算法停止。浊馏举他叭倔谓臃峪丹乾规屿教民猫存又拷刹巴数抓丁挫得幅像蜂滓憾掳高级计算机网络高级计算机网络7/29/202460史忠植 高级计算机网络BSMA动态递增动态递增 BSMA动动态态递递增增的的计计算算子子树树Tj1
62、和和Tj2之之间间的的k条条最最短短路路径径。当当构构成成延延迟迟限限界界树树的的最最短短路路径径找找到到后后决决定定K，以以下下两两个条件满足的时候，最短路径递增构建停止：个条件满足的时候，最短路径递增构建停止：1.新发现的最短路径和刚删除的等长。新发现的最短路径和刚删除的等长。2.新发现的最短路径使新树不超过延迟限界。新发现的最短路径使新树不超过延迟限界。扩扩展展的的Dijkstra算算法法用用于于构构建建两两子子树树间间的的最最短短路路径径，而而不不是是两两点点之之间间的的最最短短路路径径。在在Tj1中中，一一个个伪伪源源结结点点s与与所所有有结结点点相相连连。在在Tj2中中，一一个个伪
63、伪目目标标d所所有有结结点点相相连连。最最短短路路径算法始于径算法始于s终止于终止于d。约危揽邑贱艾鹿宛煽锯铜影证窟姬噪跋层寒顷赵捕辙盔篆争诣岭抠材粘憾高级计算机网络高级计算机网络7/29/202461史忠植 高级计算机网络贪心路径交换 增益增益=进行了一轮路径交换以后所减少的成本。进行了一轮路径交换以后所减少的成本。c = Tj 的的成成本本，c_prime = Tj+1的的成成本本，增增益益 = c -c_prime。BSMATj中中所所有有可可能能的的路路径径交交换换对对的的增增益益，而而后后选选择择一个具有最大增益的交换对。一个具有最大增益的交换对。BSMA继续贪心交换法，继续贪心交换
64、法，直到最大增益为直到最大增益为0时结束。时结束。这种贪心途径的时间复杂度更高，为这种贪心途径的时间复杂度更高，为O（kn3log（n）。）。钡袋罚莆妥尾厕菇伤吮迭苑不监驳彦猴枫湃旺剖讣追替鹃拖莫厂俭增条姥高级计算机网络高级计算机网络7/29/202462史忠植 高级计算机网络 6.14 适用于光纤网络的多播的MZQ算法 1：限限制制的的波波长长转转化化：每每个个结结点点有有能能力力将将一一个个输输入入波波长转化为一组输出波长长转化为一组输出波长2：稀稀疏疏的的波波长长转转化化：一一个个输输入入波波长长可可以以被被转转化化为为任任意的输出波长，但只有少数的几个结点拥有这样的能力。意的输出波长，
65、但只有少数的几个结点拥有这样的能力。3：稀稀疏疏的的分分裂裂：只只有有一一部部分分结结点点能能够够将将所所有有的的信信息息复本传输出去，其余结点没有这样的分裂能力。复本传输出去，其余结点没有这样的分裂能力。4：MZQ算算法法假假设设在在每每条条链链路路上上总总是是有有足足够够的的波波长长。在在具具有有分分裂裂能能力力的的结结点点上上构构造造多多播播树树。在在这这样样的的树树中中，一一个没有分裂能力的结点最多只能有一个子结点。个没有分裂能力的结点最多只能有一个子结点。停苑掠味体肉诬轨谱技昧副瞳肋念灌扁泣酵侯靶详闷监色经乾芭墟穆氮汪高级计算机网络高级计算机网络7/29/202463史忠植 高级计算
66、机网络 MZQ路由算法 1算法运行过程中保持着三个结点集合：算法运行过程中保持着三个结点集合：(1)V：树树上上可可以以用用来来向向外外生生长长的的结结点点（具具有有分分裂裂能能力力的结点）的结点）(2)V1：树树上上无无法法用用来来向向外外生生长长的的结结点点（不不具具有有分分裂裂能力的结点）能力的结点）(3)UV：目目前前为为止止，没没有有被被包包括括进进任任何何树树中中的的终终端端结结点。点。2从从UV集合中挑选离树最近的结点。集合中挑选离树最近的结点。3在一个多播树中包括进尽可能多的目的结点。在一个多播树中包括进尽可能多的目的结点。4如如果果先先前前的的那那棵棵树树还还不不能能使使所所
67、有有的的结结点点包包括括进进去去，那那算法就循环调用以生成另一棵多播树。算法就循环调用以生成另一棵多播树。螟师埠漏嘉积粕柿绣芭卢出拾顿主琐萧贾凸敲晒歇绚心帛破忱烂宴况瘩磁高级计算机网络高级计算机网络7/29/202464史忠植 高级计算机网络 MZQMZQ算法的波长分配算法的波长分配 1.性能度量性能度量(1)波长的数目波长的数目(2)带宽的总量（信道总数）带宽的总量（信道总数）2.在每条链路上维持两个计数器在每条链路上维持两个计数器(1)I：使用的最高波长索引：使用的最高波长索引(2)N：使用的波长数目：使用的波长数目3.在每条链路上的波长数目没有限制在每条链路上的波长数目没有限制夏膏氮仍缔
68、偷积曹介彭净咽馒听意闺瞪继循果拧喝浅豺绥屏季毖砰赋寇耸高级计算机网络高级计算机网络7/29/202465史忠植 高级计算机网络 MZQMZQ算法的波长分配算法的波长分配 4.在波长的分配中使用首先适配算法在波长的分配中使用首先适配算法在所有光纤网络中的多播采用在所有光纤网络中的多播采用MZQ算法算法,可以得到如下结果：可以得到如下结果：(1)由于使用多播的方法，带宽（由于使用多播的方法，带宽（bandwidth）可节省）可节省50%(2)多播可将所需使用的波长（多播可将所需使用的波长（wavelength）数目减少）数目减少60%(3)即即使使整整个个网网络络中中不不存存在在具具有有分分裂裂能
69、能力力的的结结点点，使使用用多多播播算算法法也也能使消耗的带宽（能使消耗的带宽（bandwidth）的数目减少）的数目减少43%到到45%(4)只只要要有有不不超超过过75%的的结结点点具具有有分分裂裂能能力力，整整个个系系统统就就能能取取得得和和所所有结点都具有分裂能力的系统同样的性能。有结点都具有分裂能力的系统同样的性能。宜汗抄渴妻籍忽德公炯佯顺渭诀傍脆三跃汪石苫婪皮葛等氢潞拧桅渺纤垒高级计算机网络高级计算机网络7/29/202466史忠植 高级计算机网络 6.15 多播的应用 信息发布信息发布 视频会议视频会议 远程学习远程学习 发现资源发现资源 公司内部的资源共享公司内部的资源共享 历瞅粟写淖郝叭押荫猾吊骂离驭榨趋斤拜闯阀樟焰边矛曾揭秸佳赂卖绥煌高级计算机网络高级计算机网络7/29/202467史忠植 高级计算机网络 谢谢! THANK YOU做瓶昏煽亥吝醋殿阔滨刺圭蝴拜艘一蒂关伐囱鸥炭嵌酝捍娃筐挂皖怖巍慑高级计算机网络高级计算机网络7/29/202468史忠植 高级计算机网络
