关于覆盖组播中拓扑发现的研究

作者：曹佳; 鲁士文

来源：计算机研究与发展, 2006, (05): 784-790.

• 随机有向图
• 覆盖组播
• 拓扑发现
• 连通 random directed graph
• overlay multicast
• topology discovery
• connectivity

覆盖组播的主机自己完成拓扑发现和构建转发树的工作.其中一个重要问题就是上层传输路径在底层可能是迂回的.如果拓扑发现可以揭示足够的底层拓扑信息,那么就可以尽力减小迂回程度.主要探讨在随机拓扑发现策略中上述迂回程度和k值的关系.发现每个主机至少随机选择Θ(logn)个不同的其他主机进行测试,就能保证在测试拓扑中从源到任意主机是可达的;至少随机选择2.997×n0.5312个不同的其他主机就能保证从发送源到任意主机的路径长度最多是直接采用单播传输的2倍.最后通过模拟实验验证了当满足上述条件时,再增大k值已不会使覆盖组播传输路径的迂回程度有十分明显的改善.

• 出版日期2006
• 单位中国科学院大学; 中国科学院计算技术研究所