毕业设计（论文）构建可扩展网络的研究

《毕业设计（论文）构建可扩展网络的研究》由会员分享，可在线阅读，更多相关《毕业设计（论文）构建可扩展网络的研究（49页珍藏版）》请在装配图网上搜索。

1、1引言世界上有许多不同的网络，而且常常使用不同的硬件和软件。在一个网络上的用户经常需要和另一个网络上的用户通信，这就需要连接这些不同的甚至是不兼容的网络。互连的网络就称为互连网(internetwork或internet)。而因特网Internet（大写的I）是指特定的世界范围内的互连网，它被广泛的用于连接大学、政府机关、公司和个人用户。1IP网络即采用IP协议的网络，现在大部分的网络都采用这一协议。Internet是ARPANET（美国国防高级研究计划局网络）和NSFNET网络互联的基础上发展起来的。ARPANET是在60年代末期发展的，它是第一个电子的存储转发分组交换网。1969年试验性网

2、络取得成功后，逐渐发现当时的ARPANET协议不适合在多个网络上运行，于是网络工作者们对协议进行了更深入的研究，最后产生了TCP/IP模型和协议。在1983年当TCP/IP成为ARPANET上唯一正式的协议之后，ARPANET上连接的网络、机器和用户逐渐增长，当NSFNET和ARPANET互联之后，更是以指数级增长，Internet就是在此网络互联的基础上逐渐形成的。上世纪90年代中期以前，Internet上的网络包括骨干网都是由路由器构成的，它们都是采用IP协议。后来，随着用户数的剧增和对带宽要求较高的WWW应用的普及，网上的信息流量持续增加，网络的带宽资源变得十分紧张，以至于网络经常发生拥

3、塞，而ATM技术的出现则为解决Internet所面临的问题提供了希望。上世纪90年代后期，由于路由技术的发展已经使得骨干网上的路由器足以提供以前只有ATM才有的高速链路和可以预见的性能，随着高速光纤的提供，网络服务提供商（ISP）需要考虑是继续使用昂贵的结构复杂的设备，还是移植到简单的完全由路由器组成的核心网络上。在网络容量方面，网络的数据吞吐率每5到10年都有跨数量级的增加，高性能的交换机和路由器不断出现，宽带网络技术的出现也大大增加了计算机网络的容量。2Internet已成为一个重要的和无处不在的商业基础设施，这大大改变了消费者们对网络性能、安全性和服务的期望。21世纪的人类活动越来越依靠

4、网络，网络在人们的日常生活中的作用已经越来越大了。各种商务活动的运行和操作，比如说商业信函、网络视频会议、信息发布等等，必须需要网络的支持。工作之余，人们的娱乐休闲也离不开网络，比如说上网聊天、查询资料、下载电影、玩游戏等等。现代社会的需求越来越多，人们对于网络的要求也就越来越高。当进行视频会议的时候，网络的性能必须足以支持会议的进行而不会产生中断等问题；当进行数据传输的时候，人们更期望网络的传输速度得到提高并且不会产生传输的错误。网络的发展也在促进着社会的进步。网络提高了工作效率，节省了工作时间，为社会的发展起到了重要的作用。现有的互联网主要是基于IPv4协议的，这一协议的成功促进了互联网的

5、迅速发展。但是，随着互联网用户数量不断增长以及对互联网应用的要求不断提高，IPv4的不足逐渐凸现出来。其中最尖锐的问题就是不断增长的对互联网资源的巨大需求与IPv4地址空间不足的情况，目前可用的IPv4地址已经分配了70%以上，其中B类地址已经耗尽，据互联网工程任务组预测，基于IPv4的地址资源将会在2005年到2010年枯竭；另外，由于IPv4地址方案不能很好的支持地址汇聚，现有的互联网正面临路由表不断膨胀的压力；同时，对服务质量、移动性和安全性等方面的需求都迫切要求开发新一代IP协议。IPv6就是在这样一个情况下产生的。网络发展的初期，所依赖的是简单的距离矢量型路由协议和有类别的32位IP

6、地址。距离矢量路由协议包括RIP、RIPv2和IGRP，这些协议在开始的时候对于网络的应用起了至关重要的作用。然而这些技术为网络发展所提供的支持非常有限。为此，现今的网络技术的发展必须满足快速发展和不断变化的需要。随着各种网络技术的发展，网络的构建已经不仅仅局限于以前的能用就可以了的标准了。网络技术日新月异，各种软件、硬件性能的提高也在对现如今的网络架构提出更高的要求。当网络技术提高了，网络性能提升了，网络必须要有能力去适应这样的进步。网络必须具有良好的设计，良好的设计是构建一个具备可扩展能力的网络的关键。不良的设计并不是指使用了过时的协议或者功能不强的设备，而是指其限制了网络的平滑扩展能力。

7、如果任由网络按需发展，那么大多数的网络都会变得无法管理，而且更糟糕的是总有一天网络将无法再适应增长的需求。所以，如何构建一个可扩展的网络，对于未来网络的发展是至关重要的。2 IPv6的产生及其在扩展性上的益处2.1 IP危机和IPv6的产生IPv4版本的IP编址方法是我们目前正在使用的，根据IPv4的规则，将IP地址分为了A、B、C、D和E类五种形式，每类IP地址都是由32位的比特位构成的。A类和B类地址构成了75%的IPv4的地址空间，但只有少数的组织和公司能够分配到一个A类和B类网络号。C类的网络号比A类和B类的要多的多，但它们仅仅占了可能的40多亿个IP地址的12.5%，如图2-1。 C

8、类 B类 12.5% 25%A类50%D类和E类12.5% 图2-1 IP分配 Fig.2-1 IP distribution C类的地址只能容纳254台主机，根本不能满足那些不能获得A类和B类地址的大的公司和组织的需要。即使有了更多的A类、B类和C类地址，太多的网络地址也会使Internet路由器在巨大的路由表的重压下瘫痪。即使是采用了子网划分技术，IP编址的有类别系统最终也不能很好的扩展来高校的处理全球对Internet的连接需求。早在1992年，Internet工程任务组（IETF）就开始考虑两个特别的问题：剩余的、尚未分配的IPv4网络地址的耗尽问题；路由表急剧增大的问题。当时的B类地

9、址空间正处在耗尽的边缘，而且随着Internet的发展，Internet的路由表大小在迅速大量的增加，随着更多的地址加入到Internet，新的网络信息的大量充斥威胁到了Internet路由器的处理能力。20世纪90年代初期，基于地址掩码的理念而提出的CIDR有效的、暂时的缓解了这些致命的问题。CIDR的体系化特性大大提高了IPv4的可扩展性。但是实际上，不管是1985年采用的子网划分、1987年采用的可变长度子网掩码还是CIDR的体系化结构，都不能解决IPv4的一个简单的问题：没有足够的地址空间来满足未来的需要。拥有大约40亿个可用空间，IPv4地址空间看起来好像是足够大的。但是，这对于未来

10、的移动网络设备和可进行IP寻址的家用电器来说，是远远不够的。随后，IPv4地址危机的短期解决方案得到了进一步的发展。其中包括私有地址和NAT技术。然而，对IP地址短缺问题的最终解决方案是引入了用128个比特位来表示IP地址的IPv6。由于能提供超额满足需求的地址空间，IPv6最终将取代IPv4。2.2 IPv6的特性IPv6地址是针对接口和接口组而不针对节点的128个比特位的标识符，它存在着3种通用类型的地址：单播-用于单个接口的标识符。发送给单播地址的分组将被传输到由该地址所标识的接口；任播-用于一组接口（通常属于不同节点）的标识符。发送给任播地址的分组将被传输到该地址组中最近的接口；组播-

11、用于一组接口（通常属于不同节点）的标识符。发送给组播地址的分组被传输到该地址组中的所有接口。为了将128个比特位的地址写成人们容易阅读的形式，IPv6废弃了点分十进制表示法，而使用十六进制格式。因此，IPv6地址可以被写作32个十六进制数字，用冒号在中间进行分隔。例如： 1080：0000：0000：0000：0008：0800：200C：417A。在每个16比特的值中起始0可以省略，所以上面的地址可以写成：1080：0：0：0：8：800：200C：417A。在当前的计划中，连接Internet的IPv6节点将使用称为可聚合的全球单播地址，该地址对应于我们熟悉的IPv4全局地址。IPv6全球

12、单播地址有3层体系分级：公众拓扑-提供Internet连通性的供应商的集合；场点拓扑-本地级别，对应于不提供到外部节点连通性的组织；接口标识符-具体到某个节点单一接口的级别。这个3层体系包含了下面的字段，地址格式见图5.2。FP字段（3个比特）-用来标识地址的类型；TLA ID字段（13个比特）-用来标识在路由选择体系中最高级别的负责地址分配的权威机构；Res字段（8个比特）-保留字段，以便TLA或NLA ID能够随着未来发展的需要进行扩展。目前，该字段的值必须为0。NLA ID字段（24个比特）-各个已经分配了TLA ID的组织用它来生成编址体系和标识场点；SLA ID字段（16个比特）-各

13、组织用来生成自己的本地编址体系和标识子网；接口ID字段（64个比特）-用来标识链路上的各个接口。类似于IPv4地址的主机部分。3138241664FPTLA IDResNLA IDSLA IDInterface ID公众拓扑场点拓扑接口标识符图2-2 IPv6地址格式Fig.2-2 IPv6 address format对于已经在IPv4投入较多的组织来说，要转移到一个全新的架构上来并不是一件很容易的事情。只要IPv4仍然可行，我们将会避免使用IPv6。毕竟新的协议需要新的软件、新的硬件和新的管理方法。很可能在未来几年，IPv4和IPv6将会共存，但IPv6必将取代IPv4。IPv6的出现，对

14、于构建可扩展网络有了很大的帮助。最重要的是它提供了更多的IP地址供我们使用，而且它自身的特性非常适合于IP地址的扩展能力。通过提供了私有程序的加密和系统之间的认证能力，IPv6的安全性也比IPv4有了一定的提高。42.3 IPv6的技术优势同IPv4相比较，IPv6在地址容量、安全性、网络管理、移动性及服务质量等方面有明显的改进，它是下一代互联网可采用的比较合理的协议。IPv6继承了IPv4的优点，摒弃了IPv4的缺点，IPv6与IPv4是不兼容的，按IPv6同其他所有的TCP/IP协议族中的协议兼容，即IPv6完全可以取代IPv4。2.3.1 简化报头结构IPv6报头的结构比IPv4简单得多

15、，IPv6报头删除了IPv4报头中许多不常用的域，放入了可选项，这些可选项有更严格的定义。IPv4和IPv6的报头结构分别见图2-3和2-4。IPv4中有10个固定长度的域，2个地址空间和若干个选项，IPv6中只有6个域和2个地址空间。虽然IPv6报头占40B，是IPv4报头的1.6倍，但因为其长度是固定的（IPv4的报头是变长的），所以不需要消耗过多的内存容量。IPv6中所有的扩展能力都采用扩展报头实现。5扩展报头是基于这样一个原理：大多数信息包只需要简单处理，有基本报头的信息就够了；在网络层需要额外信息的信息包可以把这些信息编码到扩展报头，这种处理方式提高了数据包的处理效率。2.3.2 提

16、供近乎无限的地址空间(1) 共有2128个不同的IPv6地址。即全球可以分配地址数为340282366920938463463374607431768211456个。版本长度服务类型数据包长度数据包ID分段标志分段偏移值生存期协议校验和源IP地址目的IP地址IP选项 图2-3 IPv4的报头结构 Fig.2-3 Structure of the IPv4 datagram head 版本业务流类型流标签净荷长度下一报头跳数上限源IP地址目的IP地址 图2-4 IPv6的报头结构 Fig.2-4 Structure of the IPv6 datagram head扣除一些地址使用上的特殊规定，

17、IPv6可以让地球上的每个人拥有有效可用地址约1600万个。如果按土地面积来分配，1平方厘米可获得22乘1020个地址。IPv6地址耗尽的机会是很小的，在可预见的很长时期内，IPv6的128位地址长度形成的巨大的地址空间，能够为所有可以想像出的网络设备提供一个全球唯一的地址。IPv6充足的地址空间，将极大的满足那些伴随着网络智能设备的出现而对地址增长的需求。2.3.3 提供网络层的安全保证IPv6把IPSec作为必备协议，解决了网络层端到端数据传输的安全问题。IPSec作为新一代互联网安全标准，是IETF为提高IP协议的安全性而专门制定的。实际上，IPSec是一种协议套件，可以无缝的为IP提供

18、安全特性，如提高访问控制。数据源的身份验证、数据完整性检查、机密性保证以及抗重播攻击等。IPSec协议主要包括：验证头（AF）、封装安全载荷（ESF）、Internet密钥交换（IKE），以及强制转码类型等相关组件。见图2-5。IPSec可以为IPv6网络环境下的网络层数据传输提供各种安全服务。通信双方为实现通信保护必须维护所需的安全策略和安全联盟，任何第三方如果没有关于此次通信的安全参数，不可能伪造或偷窥通信数据。安全参数的协商与获取可以通过手工方式进行，也可以采用密钥交换协议自动实现。网络基础设施的完善，可以保证安全参数的可靠协商，进而能够最大程度的保证网络层的通信安全。封装安全载荷验证头

19、加密算法验证算法解释域密钥管理策略图2-5 IPSec协议的运行Fig.2-5 Running of IPSec protocol2.3.4 支持即插即用功能即插即用是指无需任何人工干预，就可以将一个节点插入IPv6网络并在网络中启动。IPv6使用了两种不同的机制来支持即插即用的网络连接：启动协议（BOOTP）和动态主机配置协议（DHCP）。这两种机制允许IP节点从特殊的BOOTP服务器或者DHCP服务器获取配置信息。这些协议采用状态自动配置，即服务器必须保持每个节点的状态信息，并管理这些保存的信息。状态自动配置的问题在于，用户必须保持和管理特殊的自动配置服务器，以便管理所有状态，即所允许的连

20、接及当前连接的相关信息。除了状态自动配置，IPv6还采用了一种被称为无状态自动配置的自动配置服务。无状态自动配置要求本地链路支持组播，而且网络接口能够发送和接受组播包。无状态自动配置过程要求节点采用如下步骤：一是进行自动配置的节点必须确定自己的链路本地地址。二是必须验证该链路本地地址在链路上的唯一性。三是节点必须确定需要配置的信息，该信息可能是节点的IP地址，或者是其他配置信息，或者两者皆有。如果需要IP地址，节点必须确定是使用无状态自动配置过程，还是使用状态自动配置过程来获得。32.3.5 提供更高的服务质量保证基于IPv4的Internet设计之初，只有一种简单的服务质量，即采用“尽最大努

21、力”传输，从原理上讲，文本传输、静态图像等传输对服务质量QoS并无要求，因此QoS是无保证的。随着IP网上多媒体业务的增加，如IP电话、视频点播（VOD）、电视会议等实时应用，对传输延时和延时抖动均有严格的要求。IPv6数据包的格式包含一个8位的业务流类型和一个新的20位的流标签。最早在RFC1883中定义了4位的优先级字段，可以区分16个不同的优先级。后来，在RFC2460里改为8位的类别字段，其数值及如何使用还没有定义。它的目的是允许发送业务流的源节点和转发业务流的路由器在数据包上加标记，并进行除默认处理之外的不同处理，一般来说，在所选择的链路上，可以根据开销、带宽、延时或其他特性对数据包

22、进行特殊的处理。一个流是以某种方式相关联的一系列信息包，IP层必须以相关的方式对待它们。决定信息包属于同一流的参数包括：源地址、目的地址、QoS、身份验证及安全性。IPv6中流的概念的引入，仍然是无连接协议基础上的。一个流可以包括几个TCP连接，它的目的地址可以是单个节点，也可以是一组节点。IPv6的中间节点接收到一个信息包时，通过验证它的流标签，就可以判断它属于哪个流，然后就可以知道信息包的QoS需求，并进行快速转发。2.3.6 IPv6在移动通信领域的应用移动IPv6协议为用户提供可移动的IP数据服务，让用户可以在世界各地都使用同样的IPv6地址，非常适合未来的无线上网。IPv6是下一代互

23、联网的基础和灵魂，它将为互联网换上一个简捷、高效的引擎，不仅可以解决IPv4的地址短缺问题，而且可以使互联网摆脱日益复杂、难以管理和控制的局面，从而使互联网变得更加稳定、可靠、高效和安全。3 IPv6下的路由技术3.1 路由查找路由表的项目数变得越来越大，怎样设法减小路由表的查找时间成为一个非常重要的问题。在路由表中必须使用很好的数据结构和使用先进的快速查找算法。为了减缓骨干路由表的增长速度，提高IP地址空间的利用率，Internet工作组IETF于1993年提出了“无类域间路由”（CIDR）的概念。CIDR屏弃了传统基于类的地址分配方法，在分配网络号时可以是任意长度，这样就提高了IP地址的利

24、用率。但同时由于地址前缀的长度可以任意，路由查找时必须进行最长前缀匹配，这就增加了路由查找问题的复杂度。随着Internet的规模不断增大，其流量以每四年一倍的速度递增，线路速率每六个月增长一倍，到2005年骨干节点的流量达到100Tbps。骨干网线路的高速化，使路由器处理报文的时间要求越来越高，路由查找已经成为制约路由器性能的瓶颈，其困难在于要进行最长匹配前缀。3.2 IPv6中的路由查找算法尽管IPv6的地址空间与IPv4相比有许多不同之处，但整个地址空间还是层次性结构，仍然存在类似于IPv4的CIDR地址结构下的路由合并，IPv6路由查找同样是最长的网络前缀匹配问题，而且IPv6本身地址

25、宽度的增加使得最长前缀匹配问题变得更加突出。骨干IP路由器的主要瓶颈是在转发表中查找某个路由所耗的时间，随着链路速度的提高和IPv6的应用，这一问题日益成为告诉路由查找表以确保线速率转发的瓶颈。在IPv6网络下要得到较好的路由必须使算法更适用于IPv6的结构。目前IPv6下路由查找算法大多数是由IPv4查找算法的改进得来的。3.2.1 目前的路由算法现今IPv4下的路由查找算法已经变得很成熟了，主要的查找算法有：基于地址前缀值的路由查找算法和基于地址前缀长度的路由查找算法两类。基于地址前缀值的路由查找算法的特点是通过对整个地址前缀空间进行地址关键字穷举来进行地址前缀长度的查找。线形匹配查找算法

26、、地址区域二分法以及CAM硬件实现方法是属于此种方法；基于地址前缀长度的路由查找算法的出发点是在前缀长度空间内进行查找，与基于地址前缀值查找算法类似，查找过程可以使用线形遍历法，也可以使用二分法遍历法。目前使用最多的二进制Tries树查找算法、多分支Tries查找算法都属于此种方法。二进制Tries树查找算法用二进制Tries结构来表示地址前缀是路由查找的一个常用的方法。Tries采用一种基于树的数据结构，通过前缀中每一位比特的值来决定树的分支。路径压缩Tries树结点中可能包含多个地址前缀。与二进制Tries树相比，路径压缩Tries树前缀结点处需要保存地址前缀的比特串。查找过程与二进制Tr

27、ies树类似，但是在结点选取分支时考虑的是比特位变量所指示的比特位。当查找过程遇到前缀结点时，需要进行前缀匹配操作。当到达叶子结点或者是前缀匹配操作失败时，查找过程终止，查找结果是查找过程中已被记录的最长匹配前缀。3.2.2 路由算法对IPv6的适应由于新一代IP协议IPv6使用长度为128位的地址，它给本来已经很复杂的最长匹配全追查找带来了更大的困难，对于目前的32位计算机系统来说，访问一个128位地址就需要进行4次读写操作，查找速度会大大降低。已有的IPv6算法大致可分为TCAM硬件查找、哈希查找、分段查找等方式，但这些算法都不能完全满足IPv6的查找需要。虽然它们本身适应了IPv6对大地

28、址空间的要求。但是要把IPv4查找算法直接扩展到IPv6是不可行的，因为IPv6查找缺乏实际的路由前缀和路由前缀分布的统计规律并且它们针对IPv6查找所需存储空间是令人难以接受的。（1）基于地址前缀值的路由查找算法Tries树的查找复杂度为O（W/k）。如果W从32增加到128，在k不发生变化的前提下，算法的查找性能将下降到原来的1/4。为了能够提高查找性能，唯一的做法就是增大k。但是，从算法存储容量的复杂度来看，增加k势必会增加算法的存储空间，从而影响算法在实际系统中的使用。因此，Tries树在可扩展性方面较差。由于前缀长度二分查找法的查找算法复杂度为O（log2W）,W为关键字长度，因此相

29、对而言它受地址长度变化的影响要小得多，对于IPv4地址，查找过程需要5次访问内存，到了IPv6查找过程需要7次内存访问，因此查找性能没有发生很大的下降。对于地址区域的二分查找法来说，查找的算法复杂度为O（log2N），N为访问的关键字个数因此，查找性能只与关键字的个数有关，而与关键字的长度无关。所以，地址区域二分查找法的性能受到IPv6协议变化的影响也不大。基于分段的查找方案来自于多比特查找树算法，将多比特查找树中的节点通过简单的地址映射与路由表项的硬件存储地址关联，从而达到高速的查找速率。典型的查找算法是专门针对IPv4路由查找的DIR24-8方案。分段式硬件查找算法具有查表速率快、结构简单

30、、易于实现等优点（2）基于地址前缀长度的路由查找算法目前，对IPv4地址前缀长度匹配的路由算法的一些改进的主要思想是把最长前缀匹配问题变为最窄匹配问题，算法时间复杂度为O（log2W），空间复杂度为O（N），更新的时间复杂度为O（N），N为前缀数量；算法借助12bit的索引将前缀集合非为多个小集合进行查找，以此来减少时间和空间的复杂度。但是必须指出，针对128bit的IPv6路由查找，16bit的索引前缀作用很小。之后改进的算法通过引入地址间距的概念，实现了前缀的快速更新。改进后算法的查找时间复杂度为O（logkN）,空间复杂度为O（kNlogkN）,更新时间复杂度为O（klogkN）。但是算

31、法的查找和更新复杂度都与前缀的数量有关，并且算法实现过于复杂，不易于硬件实现。63.3 路由查找算法的评价和比较路由查找算法要达到对IPv6的很好的适应性，必须要在缓存策略、压缩策略、前缀扩展、独立前缀转化等各个方面都有很好的性能。表3-1是对各路由算法性能的比较。就目前来看，减少查找次数，不能完全避免查找，只是降低核心路由器的负担，或者降低单一路由器查找的次数（使用Cache）。使用Cache的方法在未来几年内会慢慢消亡，至少在中等汇聚层以上的路由器中，主要原因是网络增长的速度大于硬件性能提升的速度。要研究更快的路由查找算法，如Tries算法、CAM方法和DIR24-8结构。Tries算法使

32、用Multi-bit tries或unibit tries数据结构，和高速内存、流水线同时使用，这种算法因为内存耗费大很难扩展到下一代IP地址IPv6。CAM方案是目前最好的选择，但是过于昂贵而且很难升级，目前没有支持IPv6的CAM。DIR24-8结构是一种用空间换时间的方法，在IPv4下很实用而用于IPv6则空间耗费太大而无法实施。此外还存在LC Tries、基于前缀长度的二分查找、基于地址空间的二分查找等相关算法，这些算法为下一代路由算法提供了很好的设计思路和优化策略。 表3-1 算法性能比较Tab. 3-1 Comparison of arithmetic performance算法名

33、称一次查找所需访问存储器次数所需存储空间转发表更新性能是否适用于IPv6多比特树扩展级数很大，可选用扩展前缀级数步长越大，更新速度越慢不适用，存储空间太大压缩树前缀长度与页面中节点个数有关较小很慢不适用基于前缀长度的二分查找Log2(前缀长度数目)较小1（理想情况）适用基于前缀区间的二分查找Log2(2*前缀长度个数+1)较小慢适用TCAM1较小1（理想情况）适用4 路由选择协议在可扩展网络中的作用处于网络核心层的路由器应该具有快速转发的能力，以保证一个自治系统内所有的网络和其子网都能被传输到。在核心层路由器上的路由协议必须具备这样的能力。所以选择合适的路由协议是非常重要的。目前所流行的几种路

34、由选择协议，包括了RIP（路由信息协议）、IGRP（内部网关路由协议）、EIGRP（增强型内部网关路由协议）和OSPF（开放最短路径优先）等，这些路由选择协议的特点各不相同，在构建网络中应该合理的应用和取舍。理解各种路由协议的工作原理以及它们的特点是非常重要的。4.1 路由介绍及其工作原理路由这个术语是用来说明将数据包从一个设备通过网络发往另一个处在不同网络上的设备。路由器并不关心主机，它们只关心都有什么网络，以及如何寻找通往这些网络的最佳路径。目的主机的逻辑网络地址（即IP地址）是用来保证数据包可以通过路由的方式到达目的网络，路由器来选择哪条路径是最佳路径，然后根据目的主机的硬件地址（即网卡

35、的地址，又称MAC地址），将数据包发送到该主机上。路由器的作用是至关重要的，没有路由器，就无法将数据包发送到其他的网络中去，路由器的功能强大到可以将数据流路由到所有网络中去。现今的互联网中，路由器是非常重要的设备组件。要完成对数据包的路由，路由器首先必须要了解以下几个内容：目的地址、相邻路由器、所有到达远程网络的路由路径、到达远程网络的最佳路径以及对路由信息的维护和验证工作。路由器可以从相邻的路由器或者是管理员那里认识远程网络，然后会建立一个路由表，实际上就是一个记录了如何到达远程网络的信息的数据库。如果和远程网络是直接相连的，那路由器就可以直接获得到达该网络的路径。如果网络没有直接和路由器互

36、连，路由器则需要去学习如何到达该网络，所采用的方法只有两种：静态路由方式和动态路由方式。静态路由方式是指由人工手动向路由表中输入所有的网络位置。动态路由方式则是运用路由协议在路由器之间进行通信，来通告到达远程网络的路径。在动态路由中，如果某一个网络出现改变，那么路由协议将自动的把这些变动通告给所有的路由器。而在静态路由中，必须要管理员手工的去改变所有路由器上的路由信息。静态路由的方式不适合于一个大型的网络，因为要手工的去对所有网络中的路由器进行更改是非常繁琐和复杂的。所以在现如今的大型网络中，通常都是采用静态和动态两种方式同时运用的。 下面我们来用一个例子具体介绍一下IP路由选择的过程。见图4

37、-1。在这个例子中,主机A执行一个Ping的命令到主机B,路由的工作将会分为以下几个步骤:(1)Ping命令所依赖的是因特网控制报文协议（ICMP）。ICMP将创建一个回应请求数据包。(2)ICMP将此数据包传递给因特网协议，即IP协议，然后IP协议会再创建一个数据包，在这个数据包中，包含了源IP地址、目的IP地址和一个值为01h的协议字段。这些内容的作用是告知目的地主机将该数据包交给ICMP协议来处理。192.168.0.2192.168.1.2主机A主机BE0 192.168.0.1E1 192.168.1.1图4-1 IP路由工作原理Fig.4-1 Working principle o

38、f the IP routing(3)IP协议将判断目的地IP地址是处在本地网络中，还是处在一个远程网络上。(4)当IP协议断定这是一个远程请求，这个数据包将会被发送到默认网关。在本例中，主机A的默认网关配置为192.168.0.1。要能够从主机A发送数据包到默认网关，首先必须知道路由器E0口的硬件地址（即MAC地址）。因为数据包是被下传给网络7层模型中的第二层数据链路层，形成帧之后发送给路由器的E0口。在本地网络中，主机之间的通信只可以通过硬件地址来进行。(5)主机检查自身的ARP缓存记录，查看是否默认网关的IP地址已经被解析为硬件地址。如果已经被解析，数据包将被发送到数据链路层以形成帧。如

39、果没有被解析，主机将会向整个本地网络发送一个ARP广播，来搜索192.168.0.1的硬件地址。路由器将响应这一请求，并提供E0口的硬件地址，之后主机将缓存这个地址，同时路由器也会将主机A的硬件地址缓存到自己的ARP缓存中。(6)在得到了默认网关的地址之后，数据包将会被发送到路由器上，路由器接收这个数据包并且提取出帧中的数据，从中查看目的网络的IP地址。(7)因为目的主机B的IP地址是192.168.1.2,路由器将在路由表中查找是否记录了192.168.1.0的网络。如果没有该网络的路由记录，路由器将丢弃这个数据包，之后会向主机A发送一个带有“destination network unav

40、ailable”信息的ICMP数据包，来通告主机A目的地址不可达。(8)如果路由器在路由表中找到了目的网络的路由记录，数据包将被交到路由器的相应输出接口。在本例中为E1接口。(9)此时路由器需要知道目的主机的MAC地址。如果在缓冲区中有目的主机IP地址的硬件地址解析，那么数据包将被封装成帧之后发送出去。如果ARP缓冲区中没有该目的地址的硬件地址记录，路由器将从E1口发送一个ARP的请求，来搜索192.168.1.2的主机的MAC地址。(10)在确定了目标主机B的MAC地址之后，路由器E1口将把该数据发送出去。目标主机B得到数据之后，从帧中提取出数据包，并将此数据包交给ICMP协议来处理。(11

41、)ICMP协议在确定这是个请求回应之后，会发送一个新的数据包来应答该请求。(12)之后的过程和之前的请求回应过程是一样的。7即便是在一个非常大型的网络当中，这样的处理过程也是同样的，只是会经过更多的路由器的传递罢了。4.2 路由协议和自治系统在互联网中经常使用两种类型的路由选择协议，分别是内部网关协议（IGP）和外部网关协议（EGP）。运行于企业网络内部的协议被称为内部网关协议（IGP），它的例子包括RIPv1、RIPv2、IGRP、EIGRP、OSPF和IS-IS。IGP被用于在同一个自治系统（AS）中的路由器之间交换路由选择信息。在企业或自治系统之外运行的路由选择协议被称为外部网关协议（E

42、GP），EGP被用于在AS之间进行通信，通常是在ISP之间交换路由信息，某些情况下也用于客户的自治系统和服务提供商网络（ISP）之间通信。目前最常用的EGP协议是边界网关协议（BGP）。所谓自治系统，是指一个基于共同管理域下的网络集合。互联网是由一些较小的、独立的网络联合起来组成的。每个这类小网络都可以由不同的组织机构拥有和管理。这些独立网络的管理人员都想要自行管理他们的系统，但因为一个组织机构的路由和安全策略可能会与另一个组织机构的有冲突，所以互连网络被划分为小的区域，即自治系统（AS）。每个AS通常代表一个独立的组织机构，并应用它自己的路由协议和安全策略。而且每个AS都有一个标识号，由In

43、ternet注册机构或网络服务提供商（ISP）分配，其范围是1到65535。64512到65535范围的AS号码是留做私用的，类似与私有IP地址的用法。因为可用的AS号码都是有限的，所以任何组织和机构如果想要获得一个AS号码，必须提供相关的理由。目前，Internet地址授权委员会（IANA）执行的政策是连接到单个服务提供商并共享该服务商路由策略的组织机构可以使用64512到65535之间的私有AS号码。这些私有的AS号码只能出现在该服务提供商的网络中，在从该网络外出时将被服务提供商的注册AS号码替换掉。2图4-2形象的解释了IGP和EGP在所有AS之间的应用。椭圆区域内表示所有的路由器是在一

44、个自治系统下,每个自治系统有相应的AS号码。在每一个自治系统内，各路由器之间所运行的是IGP协议，即OSPF、RIP和IGRP。在自治系统和自治系统之间，运行的是BGP协议，即外部网关协议。 BGP BGP BGP IGRPAS 78 OSPFAS 45 RIPAS 355 图4-2 自治系统 Fig.4-2 Autonomy System4.3 三类IGP内部网关协议目前的内部网关协议大致上可以分为三类：距离矢量路由选择协议、链路状态路由选择协议和混合型路由选择协议。4.3.1 距离矢量路由选择协议距离矢量路由选择协议通过判断距离来查找到达远程网络的最佳路径。数据包每通过一个路由器，被称为一

45、跳。使用最少的跳数量到达远程网络的路由被认为是最佳路由。矢量用来表明指向远程网络的方向。邻近的路由器之间通过互相发送自己的路由表来达到互相通告的目的。RIP、RIPv2和IGRP是几个目前最常见的距离矢量路由选择协议。距离矢量路由选择算法发送完整的路由选择表到相邻的路由器，然后相邻的路由器会将接收到的路由表项与自己原有的路由表进行组合，以完善路由器的路由表。路由器接收到的更新只是来自于相邻的路由器对于远程网络的信息，而并没有实地去亲自查找。某个网络可能会有多个链路可以到达同一个远程网络。如果出现这一情况，管理距离将会被首先作为筛选的标准。如果管理距离值是相同的，路由协议就会使用其他的度量值来决

46、定到达远程网络的最佳路径。所谓的管理距离，是用来衡量接收来自相邻路由器上路由选择信息的可信度的，简写为AD。一个管理距离是一个从0到255的整数值，0是最可信赖的，代表的是路由器直连的网络的管理距离。而255则表示不会有数据流过这个路由。如果两个被通告的到同一网络的路由具有相同的管理距离值，那么路由协议的度量值（如跳计数或者链路的带宽值）将被用来寻找到达远程网络的最佳路径。被通告的带有最低度量值的路由将放置在路由表中。如果两个被通告的路由具有相同的管路距离及度量值，那么路由选择协议将会对这一远程网络使用负载均衡（即所发送的数据包会平分到每个链路上）。表4-1给出了各种路由协议的默认管理距离。由

47、下表可以看出，如果某个网络是直接与路由器连接的，则路由器将一直使用这个接口连接到这个网络。如果管理员配置了一个静态的路由，路由器将确信使用这个路由，而忽略掉从其他路由协议所学习到的相关路由。静态路由的管理距离是可以修改的，默认时使用的AD值是1。如果在一个路由器上，分别使用了一个静态的路由，一个RIP通告的路由和一个IGRP通告的路由都表明可以到达某一远程网络，那么在默认的时候，路由器将一直使用静态路由，除非是修改了静态路由的AD值。 表4-1 默认的管理距离 Tab. 4-1 Default administration distance路由源默认AD连接接口0静态路由1EIGRP90IGR

48、P100OSPF110RIP120External EIGRP170未知255如果到达某一远程网络存在有多条链路，而且这几条链路的AD值是相同的，其他的度量值也相同，那么路由协议将会使用负载均衡来向远程网络传输数据。比如说RIP只使用跳计数来决定到达某个互联网络的最佳路径；如果RIP发现对于同一个远程网络，存在有不止一个链路可用，并且它们又都具有相同的跳计数，那么路由器将自动的执行循环负载均衡。RIP可以对多达6个相同开销的链路实现负载均衡（默认时为4个）。然而，当两个到达某一远程网络的链路具有不同的带宽但是又具有相同的跳计数，使用这种类型的路由度量将会带来一定的问题。在图4-3中，给出了两条

49、到达远程网络172.16.10.0的链路。由于网络172.16.30.0是一个T1链路,它的带宽是1.544Mb/s,而网络172.16.20.0是一个56K的链路，在这个时候我们更希望路由器选择T1链路而不是56K的链路。但是，由于跳计数是RIP路由选择协议唯一使用的度量，所以，这两个链路将被视为是具有等同开销的链路，这种情况就被称为是针孔拥塞。 T1 56K图4-3 针孔拥塞 Fig.4-3 Pinhole congestion网络172.16.10.0172.16.30.0172.16.20.0理解距离矢量路由选择协议在它的启动时会做些什么是很重要的。在图4-4中，四个路由器在启动它们的

50、路由表中只有与它们直接相连的网络的表项。当距离矢量路由选择协议在每台路由器上正常运行后，路由表将会使用从相邻路由器得到的所有的路由信息来完成更新。每台路由器将从路由器上的每个激活的接口发送出它们完整的路由表。每台路由器的路由表都包含有网络号、输出接口和可达网络的跳计数。见表4-2。 172.16.30.0 E0 S0 S0 E0 S1 S0 E0 172.16.10.0 B 172.16.20.0 C 172.16.40.0 DA F0/0 172.16.50.0图4-4 距离矢量路由选择协议的网络Fig.4-4 The network of distance vector routing p

51、rotocols在所有路由器将自己的路由表和相邻的路由器进行完同步更新之后，将会将更新后的路由表项加入到自己的路由表中，借此便可以了解整个远程网络的有关信息。这一过程称为会聚。会聚之后的路由表包含了此整个互连网络中所有网络的信息，因此是完整的。见表4-3。在这个表中，每台路由器上的路由表中都会保存有关远程网络的信息，如网络号、路由器发送数据包到达此网络的接口号和到达此网络的跳计数或度量值。当路由器处于会聚状态的时候，没有数据被进行传递。所以越快的会聚时间对于网络的性能越有好处。表4-2 各路由器路由表Tab. 4-2 The routing tables 路由表A 路由表B 路由表C 路由表D

52、172.16.10.0F0/00172.16.10.0E00172.16.20.0E00172.16.40.0S00172.16.20.0S00172.16.30.0S00172.16.50.0E00172.16.40.0S10 表4-3 会聚后的路由表 Tab. 4-3 Routing tables after assembled 路由表A 路由表B 路由表C 路由表D172.16.10.0F0/00172.16.10.0E00172.16.20.0E00172.16.40.0S00172.16.10.0F0/01172.16.10.0S00172.16.30.0S00172.16.50.0

53、E00172.16.30.0F0/02172.16.30.0S01172.16.40.0S10172.16.10.0S02172.16.40.0F0/02172.16.40.0S01172.16.10.0S01172.16.10.0S01172.16.50.0F0/03172.16.50.0S02172.16.50.0S11172.16.30.0S01距离矢量路由选择协议会通过定期的广播路由更新信息到所有激活的接口，来跟踪互联网络中的任何变化。这个广播包包含着整个路由表。尽管这种工作方式会占用一定的CPU的进程和链路的带宽，但它是可以正常的工作的。可是如果其中的某一个网络出现故障导致瘫痪，距离

54、矢量路由选择协议的慢会聚问题便会造成矛盾的路由表和路由环路。路由环路的发生是由于每台路由器不能同时或接近同时的完成路由表的更新。假设图4-5中网络5发生了故障。所有的路由器都知道要到达网络1需要经过路由器E。在路由器A的路由表中，有一条到达网络5的路径，需要通过路由器B。当网络1的故障发生之后，路由器E将通告路由器C网络1不可达。此时路由器C将会在路由表中去掉通过路由器E到达网络1的那一表项。但是，此时的路由器A、B和D都还不知道关于网络1的情况。于是他们照旧发送出自己的更新路由信息。最后，路由器C会送出自己的路由更新，并导致B停止通向网络1的路由。但此时路由器A和路由器D仍然没有得到更新，对

55、于它们来说，显然网络1依然是可以通过路由器B到达的，其度量值为3。当路由器A按照常规那样每30秒发生送自己的路由更新信息，在这个信息里面仍然包含着有网络1可以到达的信息，那么这时路由器B和路由器D又都会接收到网络1仍然可以通过路由器A到达的好消息。于是，路由器B和路由器D也会送出网络1可达的信息。任何一个以网络1为目的地的数据包将会到达路由器A，再到达路由器B，然后再返回路由器A，这就形成了路由环路。8 A B C E D 图4-5 路由环路Fig.4-5 Loop circuit of routing 网络1要避免在网络中出现路由环路的问题，可以有以下几种解决办法：(1)使用最大跳计数路由环

56、路的问题可以简单的描述为无穷大计数问题。它是由于在通告网络的通信和传播的广播中包含错误的信息所造成的。如果不使用一些人工的方式去干预，数据包每通过一个路由器的跳计数的增长会具有不确定性。解决这个问题的其中一个方式是定义最大的跳计数。比如说，RIP允许的最大跳计数是15，所以任何需要经过16跳或16跳之后到达的网络，都会被认为是不可达的。也就是说在循环通过路由器15次之后，目标网络将会被认为是无效的。最大跳计数可以控制一个路由表项在达到多大的值后变成无效的或者不可信的。这一解决方案实质上并没有把环路从网络中去除掉，数据仍然会在环路里面进行循环的传输，直到达到了一个最大的跳计数之后被宣布无效。(2

57、)使用水平分割水平分割也是一种解决路由环路问题的方法。它是通过在距离矢量路由选择协议网络中强制信息的传送规则，来减少不正确路由信息和路由管理开销的产生。具体的做法是限制路由器不能将信息发送回接收信息的方向。简言之，路由选择协议区分网络路由信息是哪个接口获得的，一旦这个判断被确定下来，它将不会再把有关这一路由的信息再发送回同一接口。这将阻止路由器A发送有关的从路由器B处接收的更新信息返回到路由器B。5以上两种处理方法，是目前在距离矢量路由选择协议中最常见的方案。综合了这两种解决方案，我个人认为实际上还可以使用下面这样的方法。第一种方法是在时间上去判断网络是否是无效的不可达的，如果是在一个非常大型

58、的网络中，假如所使用的路由器非常的多，那么有可能造成这样一种情况，数据包在还没有到达目的网络的时候，就已经达到了最大的跳计数，即便目标网络是可用的可达到的，那么数据包也将会被认为是无法被送达的，进而造成原本有效的路由信息被判断为无效。第二种方法是强制不让路由信息被返回到它的来的方向，这一方法比第一种方法的好处在于，不会产生数据包被循环传送的问题。但相应的，在其他路由器将自己的最新的关于失效网络的路由更新传送给发送方路由器之前，发送方路由器依旧是无法得到目的网络已经失效了的信息，进而又再次向目的方网络发送数据包，造成时间上的延误和无效数据占用带宽的现象发生。通过对这两种解决方法的分析，我觉得可以

59、有这样一种解决方案。当一个路由器已经接收到了来自于它下一跳路由器发送来的关于失效网络的信息，那么，当这个路由器再接收到从上一跳路由器发送而来的请求到达失效网络的数据包时，它将这个数据包丢弃，并同时向发送方路由器发送一个目的网络已经不可达的信息，发送方在接收到这个信息之后，将此信息添加到自己的路由表中，并且同时通告给任何想要请求到达失效网络的路由器。这样的方法不仅可以从根本上去除掉路由环路的问题，并且也可以及时的使任何没有获得最新的路由更新的路由器，在第一时间将失效网络的路由信息从自己的路由表中删除掉。同时，我又考虑到了另一个问题。假设在图3.5中的网络，如果路由器E和网络1之间仅仅是接口出现了

60、问题，这一问题可能是由于接口接触不良，从而导致路由器E和网络1的连接时断时续。那么，路由器E就会不断的更新自己的路由表，并且在每次发送路由更新的时候，所发送的信息中关于网络1的可达性也时好时坏，这样的话网络就很难到达路由信息的会聚，并且不断翻动的接口可能会导致网络瘫痪。所以我认为，一旦路由器接收到了一条远程网络失效的信息，在将其添加到自己的路由表以更新之后，就启动一个定时器，在这个时间段内不得再对这条路由信息做出更改。这样的话，可以避免一个路由器在接收到正确的路由信息之后，又被其他不正确的信息所影响，从而进一步避免了路由环路问题的产生。在分析了什么是距离矢量路由选择协议之后，我们再进一步研究以下几种距离矢量路由选择协议。4.3.2 路由信息协议(RIP)路由信息协议(RIP)是一个真正的距离矢量路由选择协议。它每隔30秒钟就送出自己的完整的路由表到所有激活的接口。RIP只使用跳计数