多播路由表结构和查找算法

摘要

该文主要讨论在多播通信模型下有效的路由表结构和查找算法.单播路由表查找仅是对目的地址做最长前缀匹配查找,而多播路由表的查找则不同,它除了同目的组地址有关,根据不同的路由结构还可能同源地址相关,需建立多播路由树.多播路由树在结构上可以分为基于源的转发树（有源树）和基于组的转发树（共享树）,两种不同的结构也对应不同的多播路由表结构和查找算法.该文分别给出了这两种不同结构下的几种路由表结构和相应的查找算法,其中在基于组转发树的结构下给出了线性哈希的算法,在基于源转发树的结构下给出了四种路由表结构和相应的查找算法,分别是：对源地址的Patricia树查找和对组地址的二分查找;对源地址的LC树查找和对组地址的二分查找;对源地址的LC树查找和对组地址的动态哈希查找;对源地址和组地址做合并的Union算法查找.最后还给出了实验结果和性能分析.

目录

1.引言

1.1多播通信的背景和意义

1.2 IP多播发展简史

1.3 IP多播研究的几个主要方面

1.4路由表查找算法设计要考虑的问题

2.多播路由概述

2.1 IP多播目的组地址

2.2 IP多播的范围

2.3多播组的加入和退出

2.4 IP多播路由的分类

2.5多播路由选择协议介绍

3.单播路由查找

3.1单播路由表结构和最长前缀匹配

3.2单播路由表查找

4.多播路由查找

4.1基于组转发树结构的多播路由表查找

4.2基于源转发树结构的多播路由表查找

4.2.1多播路由表的结构组织

4.2.2对源地址的最长前缀匹配

4.2.3对组地址的完全匹配

4.2.4基于源转发树结构的多播路由表查找算法

5.多播路由表查找算法的实现

5.1线性哈希的实现

5.2 Patricia树+二分查找算法的实现

5.3 LC树+二分查找算法的实现

5.4 LC树+动态算法的实现

5.5 Union算法的实现

6.算法实验结果和性能分析

6.1测试用例的设计

6.2同一算法对不同分布的数据的适应性和算法性能

6.3不同算法对相同分布的数据的性能比较

7.结论

参考文献

致谢