互联网设计全套课件电子教案板.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,互联网设计,互联网设计分类,骨干网设计,给定节点位置和节点间流量，在网络成本最小原则下，选择每条链路的容量和流量，满足时延等要求。（试探法，求最小截边集）,接入网设计,有线接入（光纤、,XDSL,、同轴电缆等）,无线接入（移动接入、固定接入）,IP,子网划分,可参考,通信网络基础,（李建东，高教出版社）第七章,网络设计的基本原则,小的顶点度,小通信传输延迟（小的直径和平均距离）,简单的路由算法,均匀性或对称性（点可迁）,高容错性（高的连通度）,可扩性,可嵌入性,可嵌入性,嵌入即一个拓扑结构到另一个拓扑结构的映射。,设,G,和,H,是两个给定的图，从,G,到,H,的嵌入就是一个从,G,到,H,的映射,：,V(G),V(H),使得对任何,(x,y),E(G),它的象,(x,y),是,H,中一条,(,(x),(y),路。,G,称为客图，,H,称为主图。,衡量嵌入优劣的参数：膨胀数（客图中边被拉长的最大长度）、拥塞（用到主图中某条边的最大次数）、负载（用到主图中某一顶点的最大次数）。,连通度,可以分为点连通度和边连通度,局部点连通度,:(x,y),的最小点分离集中的顶点数,局部边连通度,:(x,y),的最小截边集中的边数,整体点连通度,整体边连通度,是网络可靠性分析中最重要的参数之一。,最小点分离集示例,最小截边集示例,网络流的概念,对于容量网络,N=(D,xy,，,c),，存在,f,(D),满足,则称,f,是,N,中从,x,到,y,的流。,最大流最小截定理：任何容量网络,N,中，最大流量等于最小截容量。,Menger,定理,用 表示最小（,x,y,）截边集中的边数；用 表示最小,(x,y),分离集中的顶点数目。,用 和 分别表示,D,中内部点不交和边不交的,(x,y),路的最大条数。,则,Menger,定理是网络连通度理论中最重要的定理之一，在网络可靠性分析中具有重要的地位，而且可以推导出匹配理论中的,Hall,定理，,Tutte,定理和,K,nig,定理。,点可迁图的概念,同构：对于两个图 和,存在两个双射,满足,点可迁图的概念,自同构：图,D,到自身的同构称为自同构，即,V(D),上保相邻性条件的置换。,所有这些置换构成,D,的自同构群，简称,D,的群，记为,Aut(D),。,确定一般图的自同构群是困难的。,点可迁图的概念,D,是简单图，若存在,满足,则称,x,1,和,x,2,是点相似的,.,若,D,的每对顶点都是点相似的，则称,D,是点可迁的。,循环图是点可迁的，一般图的点可迁性判定是困难的。,性质：点可迁图必是正则图,;,点可迁图任何节点发生故障不影响其他节点,。,补充知识：群的概念,定义：非空集合,G,上定义一种运算“,”，满足,G,中任两个元素,a,和,b,，可唯一确定,G,中一个元素,a b,，且满足以下三个条件：结合律、单位元存在、逆元存在。则称,G,是一个群。例如全体整数对数的加法构成一个群。,按元素是否有限可分为有限群和无限群。,最重要的一种有限群是置换群。,Cayley,定理：任一个,n,阶有限群同构于一个,n,元置换群。,线图设计方法,设,G=(V,E),是无孤立点的简单无向图（有向图），,G,的线图记为,L(G),，其顶点集为,E(G),，对,G,中任意两条不同的边,e,1,和,e,2,，它们在,L(G),中相邻当且仅当它们在,G,中相邻。,线图设计方法,Cayley,图设计方法,G,是非平凡有限群，,S,是,G,中不含单位元的非空真子集，定义有向图,D=(V,E),如下：,V(D)=G;,笛卡尔乘积法,设 和 是两个无向图，,G,1,和,G,2,的笛卡尔乘积为,。其中,两个不同的顶点,x,1,x,2,和,y,1,y,2,相邻当且仅当 或,第一章 互联网概论,本课程主要内容,1.,互联网概论,2.,下一代互联网基础,3.,下一代互联网动态路由协议,4.,下一代互联网关键技术,5.,未来互联网络发展趋势,6.,讨论与观摩,任课教师：、郜帅,邮件：,wsu,shgao,办公室：机械工程楼,D802/D701C,电话：,51685364/13520238867,51684274/13811229737,本章提纲,互联网的基本概念,互联网的发展历史,互联网的主要问题,下一代互联网概述,电信网,互联网,广电网,互联网,是主要实现计算机和计算机之间互联互通的一种信息网络。,互联网的定义,国际“联合网络委员会”（,FNC,：,Federal Networking Council,）给互联网的定义,“,互联网”指的是全球性的信息系统：,1.,通过全球性的唯一的地址逻辑地链接在一起。这个地址是建立在“互联网协议”（,IP,）或今后其它协议基础之上的；,2.,可以通过“传输控制协议”和“互联网协议”（,TCP/IP,），或者今后其它接替的协议或与“互联网协议”（,IP,）兼容 的协议来进行通信；,3.,可以让公共用户或者私人用户使用高水平的服务，这种服务是建立在上述通信及相关的基础设施之上的。,三个方面的含义,互联网是全球性的；,互联网上的每一台主机都需要有“地址”；,这些主机必须按照共同的规则（协议）连接在一起。,本章提纲,互联网的基本概念,互联网的发展历史,互联网的主要问题,下一代互联网概述,1946,年世界上第一台电子计算机诞生,互联网诞生的技术背景,资源共享的需求,推动计算机与通信结合与发展！,互联网诞生的时代背景,1957,年，前苏联发射了人类第一颗人造地球卫星。作为响应，美国国防部组建了高级研究计划署,(ARPA),，研究将科学技术应用于军事领域。,1961,年,MIT,的,Leonard Kleinrock,发表“,Information Flow in Large Communication Nets”,，第一篇有关分组交换的论文。,1969,年，为了能在爆发核战争时保障通信联络，美国国防部高级研究计划署,ARPA,资助建立了世界上第一个分组交换试验网,ARPANET,，连接美国四个大学。,ARPANET,即为现代互联网的前身。,斯坦福,研究院,犹他,大学,UCSB,UCLA,ARPANET,ARPANET,最初的结构,TCP/IP,协议的提出,1974,年，,Vinton Cerf,和,Robert Kahn,提出了,TCP/IP,协议族，用以解决不同计算机网络的互联问题。,1981,年，,IP,的协议规范,RFC791,和,TCP,的协议规范,RFC 793,出现，并在,1983,年成为,ARPNET,的正式标准，这使,ARPNET,的规模迅速扩大。,互联网的诞生,20,世纪,80,年代中期，美国国家自然科学委筹建,NSFNET,。,NSFNET,是一个通用的研究网络，它将地区网络连接起来，原来连接到,ARPANET,的,大学电脑,，,转为,接入,NSFNET,，成为互联网的骨干网。,到,20,世纪,90,年代初，,NSFNET,被一个更有竞争力、商业化更强的骨干网,ANSNET,代替，将,Internet,向商业用户开放。,万维网的出现,服务器,连接到互联网,My webpage,Hello world!,This is my first webpage!,My webpage,Hello world!,This is my first webpage!,My webpage,Hello world!,This is my first webpage!,超文本,1992,年，欧洲粒子物理实验室提出了一个称为,WWW,（,World Wide Web,）的概念，随后一年，发布了称为,Mosaic,的,WWW,客户程序。这是,Internet,发展史上一个划时代的事件，因为它使得,Internet,从一个由科学家和研究人员使用的文本工具转变为可由普通人就可以使用的图形工具,。,从,IPv4,到,IPv6,以,TCP/IP,协议体系为基础技术支撑的互联网在取得巨大成功的同时，也面临着越来越多的挑战和问题。,直接原因：互联网规模迅速膨胀和各种新业务不断出现。,根本原因：现有,IPv4,协议存在着诸多设计上的缺陷，包括：,地址空间不足,配置复杂,不能很好的支持语音和视频服务,安全性不高,移动性支持差,从,IPv4,到,IPv6,互联网的标准化组织,IETF,从,20,世纪,90,年代就着手制订下一代网际协议,IPv6,。,1996,年，描述,IPv6,及其支持协议的,RFC,出现（,这些,RFC,基本上都已经被新的标准所代替,）。,1998,年，新的描述,IPv6,的协议标准,RFC 2460,取代了旧的,RFC 1883,，新的描述,IPv6,地址结构的,RFC 2373,代替了,RFC 1884,，而这个,RFC,在,2003,年又被,RFC 3513,所代替。,目前,IPv6,已经形成了比较完善的协议体系。,本章提纲,互联网的基本概念,互联网的发展历史,互联网的主要问题,下一代互联网概述,互联网通信示意,数据转发（路由）问题,信息在互联网上传递，有两个基本问题需要解决：一个是数据在链路上的传输；另一个就是数据在中间节点的转发。,对比：火车运行需要铁轨，还需要车站的调度,如何实现快速正确的数据转发？,互联网中负责对各种数据进行交换转发的设备称为路由器。,路由器要实现快速正确的数据转发，有两个关键问题需要解决：,路由器应该知道向哪个方向转发数据,不能南辕北辙,路由器知道向哪个方向转发数据后，要快速的对数据进行处理,第一个问题的解决：,动态路由协议,第二个问题的解决：路由器硬件体系结构、调度算法、路由查询算法等。,移动性问题,电信网：有线,无线,移动,互联网的发展也遵循同样的规律,安全和管理问题,互联网是一个开放性的网络，在给人们带来方便的同时，也存在严重的安全隐患。,常见的网络安全问题：,以各种方式有选择的破坏信息。如：修改、删除、伪造、冒充、制造病毒等。,在不干扰网络信息系统正常工作的情况下，进行侦听、截获、窃取、破译和业务流量分析。,组播问题,从视频服务器上下载视频，假设每人占用,1M,带宽，,10,个人就是,10M,，那,1,万个人呢？,大家用同一个地址来接收视频，,1,万个人也是,1M,带宽，这就是组播技术，即一对多，可以有效降低网络资源的消耗。,多种业务支持问题,不仅包括传统的数据业务，还要包括语音和视频等各种业务,本章提纲,互联网的基本概念,互联网的发展历史,互联网的主要问题,下一代互联网概述,互联网面临的重大技术挑战,互联网在不断演进和发展的过程中，面临着重大的技术挑战，这些挑战包括：,地址空间即将耗尽,网络安全可信度差,移动漫游能力有限,可扩展性压力日增,网络质量难以保障,运营管理水平亟待提升,主要技术路线,以解决当前互联网地址短缺为出发点，在以,IP,为核心的现有互联网上不断“演进”的路线，通常称这一目标为“下一代互联网”。,以满足未来,10,15,年以后的互联网的发展需要为出发点，重新设计新的互联网体系结构的“革命”路线，在有些国家将此体系目标称为“未来网络”或“新一代互联网”。,国内主要观点,不安全论,等待论,落后论,演进中创新论,下一代互联网定义,一般来说，“下一代互联网”是指在目前互联网技术优势的基础上创新，较好解决上述重大技术挑战的新一代互联网。,下一代互联网主要特征,网络地址资源足够丰富,基础设施更加先进,网络更加安全、可信、可控、可管、节能,更加智能地实现人与人、物与人、物与物互联,全球下一代互联网发展现状,战略布局和规划措施,网络建设、商用情况和产业规模,关键设备、软件、系统研发和产业化进展,技术、标准专利情况,基础理论研究情况,美国：,FIND,（,Future Internet Design,）和,GENI,（,Global Environment for Networking Innovation,）计划。,欧盟：,FIRE(Future Internet Research and Experimentation),计划。,我国下一代互联网发展现状,中国下一代互联网示范工程,建成了大规模下一代互联网示范网络，包括,6,个主干网、,2,个国际交换中心、,273,个驻地网。,关键技术研发,863,、支撑计划,基础研究,973,、国家自然科学基金,第二章 下一代互联网基础,本章提纲,互联网的体系结构,IP,路由中的基本概念,路由转发原理,路由选择算法,路由器硬件体系结构,现有信息网络基本上都采用了分层的体系结构，即将其协议体系划分为若干个层次，每个层次完成特定的功能，这样，各个层次综合在一起，就可以完成一个完整的系统功能。,子网层一般又称网络接口层，负责从网络层接收,IP,报文并向物理网络发送，或从网络上接收物理帧，取出,IP,数据报并提交给网络层。,网络层负责处理分组在网络中的活动，提供跨越多个网络的选路功能，并对上层屏蔽底层具体子网技术的细节。,传输层主要为两台主机上的应用程序提供端到端的通信。在,IP,网络中，有两个传输协议：,TCP,（,Transmission Control Protocol,，传输控制协议）和,UDP,（,User Datagram Protocol,，用户数据报协议）。,应用层处理特定应用程序细节，为用户完成各种网络服务。,本章提纲,互联网的体系结构,IP,路由中的基本概念,路由转发原理,路由选择算法,路由器硬件体系结构,路由器,路由器是工作在网络层上，可以连接不同类型的网络，能够选择数据传送路径并对数据进行转发的网络设备。从通信的角度看，路由器是一种中继系统。,路由表,路由器在接收到数据时，要对其传输路径进行选择。为了实现这一目标，路由器需要维护一个称为“路由表”的数据结构,。,路由表包含若干条目，供路由器选路时查询数据传输路径。,路由表中的一个条目至少要包含：,数据的目的地址（通常是目的主机所在网络的地址）,下一跳路由器（即从本路由器出发按所给路径到给定目的地所要通过的下一个路由器）的地址,相应的网络接口,一般情况下还应该有标志位等内容。,泛洪（,Flooding）,源路由,选路策略和选路机制,选路策略（,Routing Policy,）：根据数据包的目的地和网络的拓扑结构选择一条最佳路径，把对应不同目的地的最佳路径存放在路由表中；,选路机制（,Routing Mechanism,）：搜索路由表，决定向哪个接口转发数据，并执行相应的操作；,选路策略只影响路由表的内容，比如对同一个目的地址来说，由于选路策略的不同，最佳路径可能会不一样，但这并不影响选路机制的执行过程，只是会对其执行的结果产生影响。,IP,网络地址结构,指,IP,地址（包括,IPv4,和,IPv6）,的编址方式。,通常把地址空间分为网络号和主机号两部分，当路由器在进行路径选择时，一般按照目的网络来查询，这样既可以降低路由表规模，也可以提高路由查询效率。,早期,IPv4,网络把地址分为,A、B、C、D、E,五类，浪费了大量的地址空间，并造成路由效率低下。为解决这些问题，出现了,CIDR,（,Classless InterDomain Routing,，无类别域间路由）机制，即不再严格的对,IP,地址类别进行区分，,IP,地址网络号长度也不再固定。,IPv6,地址的编址方式与,CIDR,类似，也是不限定网络号空间的长度，因此有很强的灵活性。,IP,网络地址结构对路由选择和路由查询都有很大的影响。,自治系统和路由域,由于,Internet,规模太大，分布范围太广，所以路由表中对应每一个目的网络都有一个条目是不可能的；同样，也不可能采用一个全局的路由算法或协议。因此，,Internet,将整个网络划分为若干个相对自治的局部系统，即自治系统（,AS，Autonomous System）。,自治系统,可以定义为同一机构下管理的路由器和网络的集合。,一个自治系统内部还可以再划分几个小的路由域，也称作区域。,内部网关协议和外部网关协议,路由协议可以分为内部网关协议（,IGP,，,Interior Gateway Protocol,）和外部网关协议（,EGP,，,Exterior Gateway Protocol,）两大类。,内部网关协议是用于自治系统内部的动态路由协议,RIP,（,Routing Information Protocol,，路由信息协议）,OSPF,（,Open Shortest Path First,，开放最短路径优先）；,外部网关协议是用于自治系统之间拓扑信息交换的路由协议,BGP,（,Border Gateway Routing Protocol,，边界网关路由协议）。,路由选择算法,路由算法是指路由器获得对网络拓扑结构的认知，并为数据包选择正确传输路径的方法或者策略。,一个理想的路由算法至少应该具备以下几点特征：完整性和正确性；简单性；健壮性；公平性；最佳性。,路由算法的分类。,静态路由选择和动态路由选择,按照能否自动适应网络拓扑结构的变化，可以将选路策略分为静态路由选择和动态路由选择两大类。,静态路由选择并不是表示路由表一成不变，只是说明路由器不是通过彼此之间动态交换路由信息来建立和更新路由表的。,动态路由选择是通过网络中路由器间的相互通信来传递路由信息，利用接收到的路由信息自动更新路由表。,距离矢量路由选择协议和链路状态路由选择协议,距离矢量路由选择协议基于距离矢量路由算法。其基本思想是路由器周期地和相邻路由器交换路由表中的信息。这种信息是由若干（,V，D）,对组成的表项，其中，,V,代表矢量，指出该路由器可以达到的目的地；,D,表示去往目标,V,的距离。各个路由器根据收到的信息重新计算到各目的节点的距离，对自己的路由表进行修正。,链路状态路由选择协议也被称为最短路径优先协议，它基于链路状态路由算法。采用这种协议的路由器都要维护一张可以表示整个网络拓扑结构的无向图,G（V，E），,在图,G,中，节点,V,表示路由器，边,E,表示连接路由器的链路，因此,G,又可以称为,L-S（,链路-状态）图，各路由器的路由表通过,L-S,图计算。,本章提纲,互联网的体系结构,IP,路由中的基本概念,路由转发原理,路由选择算法,路由器硬件体系结构,路由转发原理,处理器,内存,接口1,接口2,接口,n,查询路由表,本章提纲,互联网的体系结构,IP,路由中的基本概念,路由转发原理,路由选择算法,路由器硬件体系结构,距离矢量路由算法,（1）各路由器对自己的路由表进行初始化，把与自己直接相连网络的距离设为0（在某些具体实现中也设为1，这只是一个初始值设定的问题），然后周期性地向外广播其路由表的内容。,（2）路由器,Ri,收到相邻路由器,Rj,的距离矢量信息后，对自己的路由表进行修正。,若,Rj,的距离矢量信息中所包含的目的节点,v,a,在,Ri,的路由表中没有，则在,Ri,的路由表中增加一个目的节点为,v,a,的条目，,令,d,ia,=d,ja,+1,，,并把到节点,v,a,的下一跳路由器设为,Rj,。,若到,Rj,目的节点,v,b,的路由比,Ri,到目的节点,v,b,的路由短，则令,d,ib,=d,jb,+1,，并把到节点,v,b,的下一跳路由器设为,Rj,。,Ri,到目的节点,v,c,最短路径上的下一跳是,Rj,。如果,Rj,的路由表中不再包含到的,v,c,路由，则在,Ri,中也应该把去往,v,c,的路由删掉；如果,Rj,到,v,c,的距离发生了变化，则,Ri,修改路由表中到,v,c,的距离，令,d,ic,=d,jc,+1,。,距离矢量路由算法在理论上是可以正常工作的，但在实际中存在着一个严重的缺陷：尽管它可以收敛到正确的路由，但它对好消息传播的快，而对坏消息则传播的慢。,总的来说，距离矢量路由选择协议的优点是易于实现，但难以适应网络拓扑的剧烈变动或者大型的网络环境。,链路状态路由算法,链路状态路由算法的基本步骤如下：,（1）每一个路由器（节点）启动后，首先执行对相邻节点的发现工作，并获取它们的地址。,（2）各路由器主动测试到每一个相邻路由器的链路时延或成本，并根据测试结果设置相关链路的状态。,（3）各路由器构造自己的,L-S（Link-State，,链路状态）信息包，,L-S,信息的内容包括本路由器的标号、本路由器的邻居路由器列表、本路由器到各邻居路由器的链路状态（时延或成本）、该,L-S,信息包的序号和生存时间等。,（4）各路由器向所有参与链路状态交互的路由器广播其,L-S,信息，可以是周期性地发送，也可在链路状态发生变化时发送。,（,5,）每个路由器在收到所有的,L-S,信息后，可以构造或更新表示整个网络拓扑结构的图,G（V，E），,顶点,V,表示路由器，边,E,表示连接路由器的链路；这时路由器就可以用,Dijkstra,算法从图,G,中计算出到所有目的路由器的最短路径，也就是构造以自己为根节点的,SPF,树。,Dijkstra,算法简介,设目的节点（就构造,SPF,树而言，是根节点）为,k,，任一条链路,（,i,，,j,）,的长度为,d,ij,，每个节点到,k,的最短路径长度估计为,D,ik,；定义所有节点的集合为,A,，定义集合,P,A,，并设定集合的初始值为,P=,k,。,在算法迭代的过程中，如果,D,ik,已经变成一个确定值，则将,i,标记为固定点，并将其加入集合,P,。在算法的每一步迭代中，在,P,以外的节点中，选择与目的节点,k,最近的节点加入到,P,中，算法的具体步骤如下：,Dijkstra,算法简介,（,1,）,P,=,k,D,kk,=,0,，,D,jk,=,d,jk,（若,j,和,k,不相邻，）,（,2,）求解使 成立的,i,，即寻找下一个和目的节点最近的节点；令 ，若,P,=,A,，算法结束。,（,3,）对所有 ，置 ，返回步骤（,2,）,本章提纲,互联网的体系结构,IP,路由中的基本概念,路由转发原理,路由选择算法,路由器硬件体系结构,集中式单（多）,CPU+,总线结构,缺陷,CPU,要负责整体系统的控制管理、路由计算和数据转发等各项功能，存在计算瓶颈。,所有接口卡的数据都要争用总线，存在数据交换瓶颈,。,分布式多,CPU+,总线结构,特点,路由计算和转发分离：主控,CPU,负责整个系统的控制管理和路由计算（即运行路由协议，维护和更新路由表）；线卡上的,CPU,负责查询路由表，对数据进行转发。,部分地克服了总线瓶颈，即如果数据的接收和发送都在一个线卡上，就不用争用总线；若数据的接收和发送涉及不同的线卡，还是会出现总线争用问题。,分布式多,CPU,+,Crossbar,结构,特点,路由计算和转发分离。,采用,Crossbar,的交换结构（,Switch Fabric），,每个输入端口和输出端口之间都有一个交叉开关，只要数据流彼此不相关，就可以实现无阻塞的交换，解决了总线争用问题。,基本上解决了路由器吞吐量的问题。,交叉开关的设计和调度算法是研究的重点和难点。,路由器硬件体系结构发展总结,共享总线 交叉开关,路由计算与转发分离,第三章 路由查询,第一部分概述,影响,IP,网络性能的关键因素,链路速度,路由器的吞吐量,包转发速率,对路由变化的快速适应性,采用光纤等技术提高链路速度,在路由器中采用大容量的交换结构以提高吞吐量,采用高效的路由查询算法和硬件路由查询方案提高包转发速率（,路由查询,）,优化各种动态路由协议,解决方案,路由查询定义,设分组的目的地址为,D，,包含长度为,W,的比特数。,设路由前缀为,P，,包含的比特数为0,W，L(P),表示前缀长度。,地址,D,匹配前缀,P,的含义：地址,D,的前,L(P),位比特值与前缀,P,完全相同。,给定一个路由前缀集合,P,A,，,集合含有,N,个路由前缀，到达分组的目的地址为,D，,路由的最长前缀匹配查找定义为：在前缀集合,P,A,中搜索到的前缀,P,m,满足：,目的地址,D,匹配前缀,P,m,；,在集合,P,A,中不存在其他的前缀,P，,满足,D,匹配,P，,且,L(P)L(P,m,),为什么是最长前缀匹配而不是精确匹配,CIDR,等机制的引入：,IP,地址是无类别的，从,IP,地址不能判断出其网络前缀长度；,IPv6,单播地址也是无类别的。,最长前缀匹配给路由查询带来很大的困难，因为不仅要考虑前缀的值，还要考虑前缀的长度。,传统的关键字查找算法不能直接用于路由查询。,W.Doeringer,G.Karjoth,and M.Nassehi,“Routing on longest matching prefixes,”,IEEE/ACM Trans.Networking,vol.4,pp.8697,Feb.1996.,路由查询算法分类,按照采用的数据结构和实现方式，大致可以分为：,基于检索树（,Trie）,查找,基于硬件,TCAM,查找,分段查找,哈希表查找,Cache,命中查找等。,按照路由查询的依据，可以分为：,基于路由前缀值的查找,基于路由前缀长度的查找,路由查询算法评价标准,时间复杂度（查找速度）,空间复杂度（占用的存储空间）,更新复杂度（增加、删除、变更路由表条目时，路由表的更新速度）,可扩展性,注意，上述复杂度一般是指最坏情况下的复杂度。,第二部分各种路由查询算法,路由前缀值的线性查找,所有路由前缀按照线性链表的方式组织。,查询时要遍历路由表中的所有表项，并记录查询过程中匹配的最长路由前缀项，一直到最后一项为止。,时间复杂度,O(N)，,空间复杂度,O(N)，,插入/删除路由前缀条目的复杂度为,O(1)。,如果使用有序链表，即把路由前缀按照长度大小排列，可以提高路由查询的平均速度，但更新复杂度上升。此时，时间复杂度,O(N)，,空间复杂度,O(N)，,插入/删除路由前缀条目的复杂度为,O(N)。,基本的二叉检索树（,Trie）,路由前缀按照二叉树的结构来组织。,树中的每个节点含有路由前缀的1比特信息，并根据下一个比特生成两个子节点。,在树的非空节点处，存放该节点对应的下一跳信息。,在进行最长前缀匹配时，首先根据路由前缀的比特信息遍历二叉树，达到最终匹配的叶子节点处，最后读出存储在叶子节点中的下一跳路由信息。,基本二叉检索树的一个例子,在查找的过程中，有可能出现多个前缀匹配的情况，如上图中的(,A,C),和(,B,D,E)，,这时要选择最长的前缀。,在查找时要记录当前最匹配的路由前缀，一直到叶子节点或者节点没有合适的分支为止。例如，对于地址111*，按照上图的例子，当查到,B,时，由于是匹配的，所以就记录下相应的信息，继续向下查询，没有更匹配的路由前缀，所以此时,B,就是最长匹配的路由前缀。,这种查找实际上是地址前缀长度空间的线性查找。因为是按照单个比特的顺序来查询的。,很显然，使用基本的二叉检索树进行路由查询时，时间复杂度与树的深度（在这种算法中就等于路由前缀的最大长度）有关。如果最大可能的路由前缀长度为,W，,则最坏情况下的查找时间复杂度为,O(W)。,最坏情况下的空间复杂度为,O(N*W),。,更新复杂度为,O(W)。,更新时需要先进行查找，找到之后进行相应的增删操作就可以了（包括中间节点和叶子节点两种情况）。,在,IPv4,中最多需要32次查找，在,IPv6,中最多需要128次查找,。,路径压缩,Trie,该算法是对基本二叉检索树的改进，最早起源于,Patricia,算法，后来,Sklower,对,Patricia,算法做了改进，使之可以用于路由查询。,其基本思想是去掉输出为1的中间节点，压缩叶子节点的路径，将叶子节点提升到最近一级父节点的下一层。这样，每个中间节点都有两个输出。,由于有可能去掉了一些包含路由前缀的中间节点，所有某些节点会有多个路由前缀。,由于去掉了一些节点，某些比特将被忽略，所以节点要维护一个变量，用于维持下一个要检查的比特位。,路径压缩,Trie,对稀疏的基本,Trie,有明显的压缩效果，但对稠密的则作用不大。,路径压缩,Trie,不能从本质上降低树的深度，在最坏情况下它的时间复杂度仍然为,O(W)。,路径压缩,Trie,的空间复杂度为,O(N)，,因为这种,Trie,中,N,个叶子节点对应,N1,个内部节点。,路径压缩,Trie,更新算法的复杂度也是,O(W)，,其动态性比基本,Trie,要差，因为当需要加入或者删除叶子节点时，会导致其对应的若干条路径上的叶子节点位置发生变化。,这种算法在,BSD,系统上得到了实现（,Radix,树），并随着,BSD,的推广而得到广泛应用。,多比特检索树（,Trie）,在基本的二叉检索树中每次检查一个比特，即一级对应1个比特；如果让每一级对应多个比特，就可以大大降低树的深度。也就能够降低路由查询的时间复杂度。,每一级对应的比特数被称为查找步宽。同一级的步宽可以一样，也可以不一样。前者实现起来比较简单，但浪费存储空间，后者实现复杂一些，但是会节省一定的存储空间。,因为一次查找多个比特，因此不能处理任意长度的路由前缀，一般要使用前缀扩展。,每一级的步宽都是2,第一级的步宽是2,第二级三个节点步宽是2，一个节点步宽是1,对于上图中绿色部分，如何应用多比特检索？,前缀扩展：将一条较短的路由前缀展开成多条较长的路由前缀集，这些前缀集的转发信息就是原来地址前缀所对应的转发信息。也就是扩展后的路由前缀要继承原来前缀的转发信息。例如，1*可以扩展为10*和11*。,对于,Trie,中不能直接应用多比特树的地方，可以先进行前缀扩展，使应用多比特树的局部成为一个满的子树。,由于步宽大于等于1，使检索树的深度明显降低，所以多比特检索树的时间复杂度比基本二进制,Trie,或路径压缩,Trie,要低，具体的数值与每一级步宽有关。当每一级步宽都是,K,时（这是多比特检索树中最简单的情况），时间复杂度为,O(W/K)。,时间复杂度降低的代价就是空间复杂度的上升，每一个中间节点都需要包含2,k,个指针（每一级步宽都是,K），,最差情况下每加入一个新前缀，需要插入,W/K,个中间节点，从而需要占用空间,O(,2,k,*W/K)，,所以空间复杂度为,O(N*,2,k,*W/K)。,更新时需要进行一次路由查找，然后更新节点的指针，最差情况下需要更新2,k-1,指针，所以更新复杂度为,O(,2,k,W/K)。,对于多比特检索树来说，当步宽为1时，就成为基本二叉检索树或路径压缩树,，,当步宽达到,W,时，时间复杂度为,O(1)，,但空间复杂度变为,O(2,W,)。,很显然，多比特检索树的主要问题就是引入了很多冗余路由前缀，占用了大量存储空间，所以对它的优化是研究的一个重点，例如有些人就提出了步宽选择策略，也有人提出了一些压缩算法。,实际进行压缩时可以考虑互联网地址分布的特点，例如长度1624之间的前缀数最多。,叶子扩展的概念,路由前缀长度空间的二分查找,Trie,树算法的实质是地址前缀长度空间的线性查找：先检查第1个（1,k）,个比特，再检查第2个（,k+12k）,个比特，一直到路由前缀的最大长度为止。,文献“,Scalable high-speed prefix matching,，Marcel Waldvogel,George Varghese,Jon Turner,Bernhard Plattner，ACM Transactions on Computer Systems,2001”,提出了地址前缀长度空间的二分查找法。,基本思想是把所有路由前缀按照其长度分为不同的前缀集合，每个前缀集合内采用哈希算法查找；查询时，从长度位,W/2,的集合开始，采用二分查找法。,图中节点对应的是前缀集合，而不是某个或某几个比特位,为了保证该算法的正确性，需要引入一个被成为,Marker,的表项。考虑下面的例子。有4个地址前缀：0*、1*、00*、110*。现查找110*。,路由前缀长度空间的二分查找在路由查询方面的时间复杂度为,O(logW)，,对,IPv4,来说，最多需要5次查询，对,IPv6,来说，最多需要7次查询。,对于每个前缀，最多可能需要,logW,个,Marker，,因此，算法的空间复杂度为,O(N*logW)。,路由更新比较麻烦，其复杂度为,O(N*logW)，,因为最坏情况下更新一个前缀可能影响,N-1,个前缀，而一个前缀又有可能对应,logW,个,Maker。,哈希算法也是该算法中的关键问题。,TCAM,TCAM（Ternary Content Address Memory）,是一种新型的存储器，存放一系列路由表项，为到来的每一个分组并行查找所有的路由前缀。因此，它的路由查询只需要一次内存访问，若有多个匹配表项，经过优先级比较后，确定路由信息。,路由管理比较复杂，路由表的动态删除和更新会导致,TCAM,中存放大量的碎片。,成本昂贵，功耗比较大，存储容量小。,这实际上是一种硬件查找方法。,基于分段的查找,这种方案实际上是多比特检索树的具体硬件实现方案。典型的是,Gupta,等人提出的,DIR-24-8-BASIC,查找算法。,DIR-24-8-BASIC,算法是把,IPv4,地址空间分为长度分别为24和8的两部分（,TBL24,和,TBLlong），,最大内存访问次数为2，采用硬件流水线技术可以用1次内存访问。第一部分是2,24,16,M,个表项；第二部分256个表项。,因为是基于多比特检索树，因此需要进行前缀扩展。,第一级中的节点携带的指针信息指示可能存在于第2级中的一棵子树。,缓存（,Cache）,策略,缓存策略是指把最近查找过的目的地址和路由下一跳信息放在缓存之中，当,IP,分组达到时，先从缓存中查找，找不到时再执行最长前缀匹配策略。,显然，数据包的相关度越大，这种方法的有效性就越高。,缓存的命中率是这种策略的一个关键。由于缓存容量有限，且数据日益多样化，缓存的命中率大大降低。,哈希查找,哈希(,Hash),算法在路由查询中应用的时候，通过查找建立的哈希索引，来找到对应的路由前缀。,理论上讲，哈希算法的时间复杂度和空间复杂度都很低，但实际上很难找到一个完美的或者近似完美的哈希函数。另外，路由更新也往往会导致哈希表的重建。,一般来说，把整个路由表做为一个哈希表是不切实际的，可以在局部范围内应用哈希算法。如在前缀长度空间的二分查找中，就可以在同一前缀长度的前缀集合内应用哈希算法。,其他路由查询算法,层压缩树,地址区间的二分查找法,多路和多列查询算法等,第三部分路由查询算法的评测,算法,时间复杂度,空间复杂度,更新复杂度,基本二叉检索树,O(W),O(N*W),O(W),路径压缩检索树,O(W),O(N),O(W),多比特检索树,O(W/K),O(2,K,*N*W/K),O(W/K+2,K,),前缀长度空间的二分查找,O(logW),O(N*logW),O(N*logW）,基本算法在时间复杂度等方面的比较,其他需要考虑的方面,算法的可扩展性。即路由前缀长度增加后，不能使查询的复杂度大幅度上升。,路由前缀长度空间的二分查找的扩展性比较好，从,IPv4,到,IPv6,后，最差情况下的查询次数从5升到7。,各种基于检索树的查找算法可扩展性一般，多比特查找树可以通过增加,K,的方法来降低时间复杂度，但会带来空间复杂度的大幅度上升。不过也可以通过分段的方法来部分地解决这方面的问题。,对路由查询算法实际评