ip路由技术综述

《ip路由技术综述》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、IP路由技术综述因特X的高速增长给路由系统带来了巨大的压力。IP路由查找操作已经成为路由器转发性能乃至因特X整体性能的主要瓶颈之一。本文通过深入研究业界提出的关于IP路由的多种解决方案，提出了IP路由未来的发展方向。关键词：因特X；IP；路由查找；一、IP协议简介　　IP(InterProtocol)协议是TCP/IP协议族中两个最重要的协议之一。IP协议是以信息包为基础的协议，位于OSI七层模型中的X络层，同时还有地址解析协议ARP，逆地址解析协议RARP，Inter控制报文协议ICMP(InterControlMessageProtocol)与之配套使

2、用。Ip协议通过计算机X络交换数据、处理寻址、分割、拼接及协议信号分解，它是所有其他IP协议套件的基础。　　IP协议工作在X络层，它与数据链路层形成了鲜明的对比。X络层的功能是将源端发出的分组经各种途径送到目的端，数据链路层仅将数据帧从导线的一端送到其另一端。可见X络层是处理端到端数据传输的最底层。因此，决定了IP路由寻址最根本的任务就是进行地址转换[1]。　　IP协议的路由功能是由路由器实现的的。路由器其实是一种专用计算机，具有CPU、内存和X络接口等硬件，能在多个X络和介质之间提供X络互联的能力。一个典型的X络，包含了一定量的局域X和广域X，在这种路由

3、器连接的X络中，有一个选择最短路径进行通信的问题，如果某条通道坏了，有选择另一条通道把信息传送出去的能力，我们称之为路由路径选择[2]。路由器工作在OSI七层模型的X络层，它通过执行路由算法，路径选择将报文分组从物理连接的一端传送到另一端，最终实现点到点的通信。概括起来，路由器的基本功能有两个：一是直接将报文发送到正确的目的地；二是维持路由器用来决定正确路径的路由选择表。二、IP协议的路由　　IP协议的路由功能是由路由器实现的的，当路由器接收到一个报文，它抽出报文中的目的地址，然后，从目的地址中找出目的地的X络号查找路由选择表寻找与目的地址中X络相匹配的项

4、。每个路由选择表项包含了用来转发报文的接口信息，也就是到目的地路径中的下一个路由器的地址。路由器的第二个工作，是维持路由选择表。这些表是由X络管理者创建的，或通过与其它路由器交换路由信息创建。当一个路由器初始引导时，它只知道与它直接相连的接口，如果X络中的路由器正在运行路由选择协议，当路由器知道与它相邻接的路由器相连的X络时，新的路由表表项将被创建每个路由选择表表项都被标识一个字符，该字符表示路由信息的源端。1．路由查找　　整个路由过程中，查表算法的优劣直接影响了当前和未来因特XX络的整体性能。当前，因特X的规模、链路速度、带宽、流量等都呈指数级增长[3]

5、，这对路由器中IP路由查找算法对大容量路由表处理的适应性以及报文转发查表的能力提出了更高要求。路由器是构成因特X的中间节点，其转发性能决定了因特X的整体性能。因此，IP路由查找操作已经成为了当前路由器转发性能的瓶颈之一[4]。其实路由查找问题本身很简单，但由于其对性能要求很高，因此有很大的难度。通常评价IP路由查表算法的标准主要有高速查找、内存需求小、更新时间短、实现的灵活性强、能够处理真实的大容量路由表以及预处理时间短等。IP路由查找方案可以分为以下几类：（1）基于精确匹配的改进方案：这种方案一般效率不高，为了找到最佳结果，一般需要log2N步（N为路由

6、表项的数目）；（2）层次方案：这是普遍采用的一种查找方案，在BSD内核中得到实现。它最坏情况下的复杂度为O（ultin等。这些算法的基本思想是根据前缀值的二进制位构建二叉树，在检索时用目标地址作为索引，在二叉树中遍历；当找到一个匹配的前缀时，将其作为到目前为止所发现的最长前缀，继续搜索更长的匹配前缀，直到再没有分支可以搜索时，搜索结束，此时所记录的最长前缀就是所要寻找的最长前缀匹配。　　在基于多分支的算法二叉树算法中，每个搜索步骤能够将第一步开始的整个232搜索空间减少一半，而多叉树可以令每个搜索步骤减少更多的搜索空间。此类算法的典型有LCTrie树算法、

7、受控前缀扩展算法。可变分支数目的多分支Trie树结构，其搜索过程与二叉树类似，只是由一位比较变成了多位比较以决定下一步搜索的子树。　　Srinivasan对分支数目和层次数目的选取做了详细的分析，并提出了多分支树的一般结构，所有基于Trie树的算法都可以看作是该一般结构的特例或变形。此外他还提出了前缀扩展技术，以耗费更多内存为代价来避免最长前缀匹配所带来的回溯问题。　　其它软件算法有前缀维度上的二分搜索算法、最差性能受限的近似最优路由查找算法、多路前缀值范围搜索树算法等。这些算法并不是对整个前缀地址空间进行搜索，因此对于地址宽度的敏感性较低。前者的搜索时间

8、复杂度是O(log2yofIPAddressLookupAlgor