互联网设计全套课件完整版电子教案最新板

1、互联网设计 互联网设计分类骨干网设计 给定节点位置和节点间流量，在网络成本最小原则下，选择每条链路的容量和流量，满足时延等要求。（试探法，求最小截边集）接入网设计有线接入（光纤、XDSL、同轴电缆等）无线接入（移动接入、固定接入）IP子网划分可参考通信网络基础（李建东，高教出版社）第七章网络设计的基本原则小的顶点度小通信传输延迟（小的直径和平均距离）简单的路由算法均匀性或对称性（点可迁）高容错性（高的连通度）可扩性可嵌入性可嵌入性嵌入即一个拓扑结构到另一个拓扑结构的映射。设G和H是两个给定的图，从G到H的嵌入就是一个从G到H的映射：V(G) V(H)使得对任何(x,y) E(G) ,它的象(x

2、,y)是H中一条(x), (y)路。G称为客图，H称为主图。衡量嵌入优劣的参数：膨胀数（客图中边被拉长的最大长度）、拥塞（用到主图中某条边的最大次数）、负载（用到主图中某一顶点的最大次数）。连通度可以分为点连通度和边连通度局部点连通度:(x,y)的最小点分离集中的顶点数局部边连通度:(x,y)的最小截边集中的边数整体点连通度整体边连通度是网络可靠性分析中最重要的参数之一。最小点分离集示例最小截边集示例网络流的概念对于容量网络N=(Dxy，c)，存在f(D),满足则称f是N中从x到y的流。最大流最小截定理：任何容量网络N中，最大流量等于最小截容量。Menger定理用 表示最小（x,y）截边集中的

3、边数；用 表示最小(x,y)分离集中的顶点数目。用 和 分别表示D中内部点不交和边不交的(x,y)路的最大条数。 则Menger定理是网络连通度理论中最重要的定理之一，在网络可靠性分析中具有重要的地位，而且可以推导出匹配理论中的Hall定理，Tutte定理和Knig定理。点可迁图的概念同构：对于两个图 和 存在两个双射满足 点可迁图的概念自同构：图D到自身的同构称为自同构，即V(D)上保相邻性条件的置换。所有这些置换构成D的自同构群，简称D的群，记为Aut(D)。确定一般图的自同构群是困难的。点可迁图的概念D是简单图， 若存在 ,满足 则称x1和x2是点相似的.若D的每对顶点都是点相似的，则称

4、D是点可迁的。循环图是点可迁的，一般图的点可迁性判定是困难的。性质：点可迁图必是正则图;点可迁图任何节点发生故障不影响其他节点。补充知识：群的概念定义：非空集合G上定义一种运算“”，满足G中任两个元素a和b，可唯一确定G中一个元素a b，且满足以下三个条件：结合律、单位元存在、逆元存在。则称G是一个群。例如全体整数对数的加法构成一个群。按元素是否有限可分为有限群和无限群。最重要的一种有限群是置换群。Cayley定理：任一个n阶有限群同构于一个n元置换群。线图设计方法设G=(V,E)是无孤立点的简单无向图（有向图），G的线图记为L(G)，其顶点集为E(G)，对G中任意两条不同的边e1和e2，它们

5、在L(G)中相邻当且仅当它们在G中相邻。线图设计方法Cayley图设计方法G是非平凡有限群，S是G中不含单位元的非空真子集，定义有向图D=(V,E)如下： V(D)=G;笛卡尔乘积法 设 和 是两个无向图，G1和G2 的笛卡尔乘积为 。其中 两个不同的顶点x1x2和y1y2 相邻当且仅当 或第一章 互联网概论 本课程主要内容1.互联网概论2.下一代互联网基础3.下一代互联网动态路由协议 4. 下一代互联网关键技术 5.未来互联网络发展趋势 6. 讨论与观摩任课教师： 、郜帅邮件：wsu shgao办公室：机械工程楼D802/D701C电话：51685364516842

6、74章提纲互联网的基本概念互联网的发展历史互联网的主要问题下一代互联网概述电信网互联网广电网 互联网是主要实现计算机和计算机之间互联互通的一种信息网络。互联网的定义国际“联合网络委员会”（FNC：Federal Networking Council） 给互联网的定义“互联网”指的是全球性的信息系统： 1.通过全球性的唯一的地址逻辑地链接在一起。这个地址是建立在“互联网协议”（IP）或今后其它协议基础之上的； 2.可以通过“传输控制协议”和“互联网协议”（TCP/IP）， 或者今后其它接替的协议或与“互联网协议”（IP）兼容 的协议来进行通信；3.可以让公共用户或者私人

7、用户使用高水平的服务，这种服务是建立在上述通信及相关的基础设施之上的。 三个方面的含义互联网是全球性的；互联网上的每一台主机都需要有“地址”；这些主机必须按照共同的规则（协议）连接在一起。本章提纲互联网的基本概念互联网的发展历史互联网的主要问题下一代互联网概述1946年世界上第一台电子计算机诞生互联网诞生的技术背景资源共享的需求推动计算机与通信结合与发展！互联网诞生的时代背景1957年，前苏联发射了人类第一颗人造地球卫星。作为响应，美国国防部组建了高级研究计划署(ARPA)，研究将科学技术应用于军事领域。 1961 年MIT的Leonard Kleinrock发表“Information Fl

8、ow in Large Communication Nets”，第一篇有关分组交换的论文。1969年，为了能在爆发核战争时保障通信联络，美国国防部高级研究计划署ARPA资助建立了世界上第一个分组交换试验网ARPANET，连接美国四个大学。 ARPANET即为现代互联网的前身。斯坦福研究院犹他大学UCSBUCLAARPANETARPANET最初的结构TCP/IP协议的提出 1974年，Vinton Cerf和Robert Kahn提出了TCP/IP协议族，用以解决不同计算机网络的互联问题 。1981年，IP的协议规范RFC791和TCP的协议规范 RFC 793出现，并在1983年成为ARPNE

9、T的正式标准，这使ARPNET的规模迅速扩大。 互联网的诞生20世纪80年代中期，美国国家自然科学委筹建NSFNET。NSFNET是一个通用的研究网络，它将地区网络连接起来，原来连接到ARPANET 的大学电脑，转为接入 NSFNET，成为互联网的骨干网。到20世纪90年代初， NSFNET被一个更有竞争力、商业化更强的骨干网ANSNET代替，将Internet向商业用户开放。 万维网的出现服务器连接到互联网My webpageHello world!This is my first webpage!My webpageHello world!This is my first webpage!

10、My webpageHello world!This is my first webpage!超文本 1992年，欧洲粒子物理实验室提出了一个称为WWW（World Wide Web）的概念，随后一年，发布了称为Mosaic的WWW客户程序。这是Internet发展史上一个划时代的事件，因为它使得Internet从一个由科学家和研究人员使用的文本工具转变为可由普通人就可以使用的图形工具。 从IPv4到IPv6以TCP/IP协议体系为基础技术支撑的互联网在取得巨大成功的同时，也面临着越来越多的挑战和问题。直接原因：互联网规模迅速膨胀和各种新业务不断出现。根本原因：现有IPv4协议存在着诸多设计上

11、的缺陷，包括：地址空间不足配置复杂不能很好的支持语音和视频服务安全性不高移动性支持差从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已经形成了比较完善的协议体系。 本章提纲互联网的基本概念互联网的发展历史互联网的主要问题下一代互联网概述互联网通信

12、示意数据转发（路由）问题 信息在互联网上传递，有两个基本问题需要解决：一个是数据在链路上的传输；另一个就是数据在中间节点的转发。 对比：火车运行需要铁轨，还需要车站的调度如何实现快速正确的数据转发？互联网中负责对各种数据进行交换转发的设备称为路由器。路由器要实现快速正确的数据转发，有两个关键问题需要解决： 路由器应该知道向哪个方向转发数据不能南辕北辙路由器知道向哪个方向转发数据后，要快速的对数据进行处理第一个问题的解决：动态路由协议第二个问题的解决：路由器硬件体系结构、调度算法、路由查询算法等。移动性问题电信网：有线无线移动互联网的发展也遵循同样的规律安全和管理问题互联网是一个开放性的网络，在

13、给人们带来方便的同时，也存在严重的安全隐患。常见的网络安全问题：以各种方式有选择的破坏信息。如：修改、删除、伪造、冒充、制造病毒等。 在不干扰网络信息系统正常工作的情况下，进行侦听、截获、窃取、破译和业务流量分析。组播问题 从视频服务器上下载视频，假设每人占用1M带宽，10个人就是10M，那1万个人呢？ 大家用同一个地址来接收视频，1万个人也是1M带宽，这就是组播技术，即一对多，可以有效降低网络资源的消耗。多种业务支持问题不仅包括传统的数据业务，还要包括语音和视频等各种业务本章提纲互联网的基本概念互联网的发展历史互联网的主要问题下一代互联网概述互联网面临的重大技术挑战 互联网在不断演进和发展的

14、过程中，面临着重大的技术挑战，这些挑战包括：地址空间即将耗尽网络安全可信度差移动漫游能力有限可扩展性压力日增网络质量难以保障运营管理水平亟待提升主要技术路线以解决当前互联网地址短缺为出发点，在以IP为核心的现有互联网上不断“演进”的路线，通常称这一目标为“下一代互联网”。以满足未来1015年以后的互联网的发展需要为出发点，重新设计新的互联网体系结构的“革命”路线，在有些国家将此体系目标称为“未来网络”或“新一代互联网”。国内主要观点不安全论等待论落后论演进中创新论下一代互联网定义 一般来说，“下一代互联网”是指在目前互联网技术优势的基础上创新，较好解决上述重大技术挑战的新一代互联网。下一代互联

15、网主要特征网络地址资源足够丰富基础设施更加先进网络更加安全、可信、可控、可管、节能更加智能地实现人与人、物与人、物与物互联全球下一代互联网发展现状战略布局和规划措施网络建设、商用情况和产业规模关键设备、软件、系统研发和产业化进展技术、标准专利情况基础理论研究情况美国：FIND（Future Internet Design）和GENI（Global Environment for Networking Innovation）计划。欧盟：FIRE(Future Internet Research and Experimentation)计划。我国下一代互联网发展现状中国下一代互联网示范工程 建成了

16、大规模下一代互联网示范网络，包括6个主干网、2个国际交换中心、273个驻地网。关键技术研发863、支撑计划基础研究973、国家自然科学基金第二章 下一代互联网基础 本章提纲互联网的体系结构IP路由中的基本概念路由转发原理路由选择算法路由器硬件体系结构现有信息网络基本上都采用了分层的体系结构，即将其协议体系划分为若干个层次，每个层次完成特定的功能，这样，各个层次综合在一起，就可以完成一个完整的系统功能。 子网层一般又称网络接口层，负责从网络层接收IP报文并向物理网络发送，或从网络上接收物理帧，取出IP数据报并提交给网络层。网络层负责处理分组在网络中的活动，提供跨越多个网络的选路功能，并对上层屏蔽

17、底层具体子网技术的细节。传输层主要为两台主机上的应用程序提供端到端的通信。在IP网络中，有两个传输协议：TCP（Transmission Control Protocol，传输控制协议）和UDP（User Datagram Protocol ，用户数据报协议）。应用层处理特定应用程序细节，为用户完成各种网络服务。本章提纲互联网的体系结构IP路由中的基本概念路由转发原理路由选择算法路由器硬件体系结构路由器路由器是工作在网络层上，可以连接不同类型的网络，能够选择数据传送路径并对数据进行转发的网络设备。从通信的角度看，路由器是一种中继系统。 路由表路由器在接收到数据时，要对其传输路径进行选择。为了实

18、现这一目标，路由器需要维护一个称为“路由表”的数据结构。路由表包含若干条目，供路由器选路时查询数据传输路径。路由表中的一个条目至少要包含：数据的目的地址（通常是目的主机所在网络的地址）下一跳路由器（即从本路由器出发按所给路径到给定目的地所要通过的下一个路由器）的地址相应的网络接口一般情况下还应该有标志位等内容。 泛洪（Flooding）源路由选路策略和选路机制选路策略（Routing Policy）：根据数据包的目的地和网络的拓扑结构选择一条最佳路径，把对应不同目的地的最佳路径存放在路由表中；选路机制（Routing Mechanism）：搜索路由表，决定向哪个接口转发数据，并执行相应的操作；

19、选路策略只影响路由表的内容，比如对同一个目的地址来说，由于选路策略的不同，最佳路径可能会不一样，但这并不影响选路机制的执行过程，只是会对其执行的结果产生影响。 IP网络地址结构指IP地址（包括IPv4和IPv6）的编址方式。通常把地址空间分为网络号和主机号两部分，当路由器在进行路径选择时，一般按照目的网络来查询，这样既可以降低路由表规模，也可以提高路由查询效率。 早期IPv4网络把地址分为A、B、C、D、E五类，浪费了大量的地址空间，并造成路由效率低下。为解决这些问题，出现了CIDR（Classless InterDomain Routing ，无类别域间路由）机制，即不再严格的对IP地址类别

20、进行区分，IP地址网络号长度也不再固定。IPv6地址的编址方式与CIDR类似，也是不限定网络号空间的长度，因此有很强的灵活性。IP网络地址结构对路由选择和路由查询都有很大的影响。 自治系统和路由域由于Internet规模太大，分布范围太广，所以路由表中对应每一个目的网络都有一个条目是不可能的；同样，也不可能采用一个全局的路由算法或协议。因此，Internet将整个网络划分为若干个相对自治的局部系统，即自治系统（AS，Autonomous System）。自治系统可以定义为同一机构下管理的路由器和网络的集合。 一个自治系统内部还可以再划分几个小的路由域，也称作区域。 内部网关协议和外部网关协议

21、路由协议可以分为内部网关协议（IGP，Interior Gateway Protocol）和外部网关协议（EGP，Exterior Gateway Protocol）两大类。内部网关协议是用于自治系统内部的动态路由协议 RIP（Routing Information Protocol ，路由信息协议 ） OSPF（Open Shortest Path First，开放最短路径优先 ）；外部网关协议是用于自治系统之间拓扑信息交换的路由协议 BGP（Border Gateway Routing Protocol ，边界网关路由协议 ）。 路由选择算法路由算法是指路由器获得对网络拓扑结构的认知，并为

22、数据包选择正确传输路径的方法或者策略。一个理想的路由算法至少应该具备以下几点特征：完整性和正确性；简单性；健壮性；公平性；最佳性。路由算法的分类。静态路由选择和动态路由选择按照能否自动适应网络拓扑结构的变化，可以将选路策略分为静态路由选择和动态路由选择两大类。静态路由选择并不是表示路由表一成不变，只是说明路由器不是通过彼此之间动态交换路由信息来建立和更新路由表的。 动态路由选择是通过网络中路由器间的相互通信来传递路由信息，利用接收到的路由信息自动更新路由表。 距离矢量路由选择协议和链路状态路由选择协议距离矢量路由选择协议基于距离矢量路由算法。其基本思想是路由器周期地和相邻路由器交换路由表中的信

23、息。这种信息是由若干（V，D）对组成的表项，其中，V代表矢量，指出该路由器可以达到的目的地；D表示去往目标V的距离。各个路由器根据收到的信息重新计算到各目的节点的距离，对自己的路由表进行修正。链路状态路由选择协议也被称为最短路径优先协议，它基于链路状态路由算法。采用这种协议的路由器都要维护一张可以表示整个网络拓扑结构的无向图G（V，E），在图G中，节点V表示路由器，边E表示连接路由器的链路，因此G又可以称为L-S（链路-状态）图，各路由器的路由表通过L-S图计算。 本章提纲互联网的体系结构IP路由中的基本概念路由转发原理路由选择算法路由器硬件体系结构路由转发原理 处理器内存接口1接口2接口n查

24、询路由表本章提纲互联网的体系结构IP路由中的基本概念路由转发原理路由选择算法路由器硬件体系结构距离矢量路由算法 （1）各路由器对自己的路由表进行初始化，把与自己直接相连网络的距离设为0（在某些具体实现中也设为1，这只是一个初始值设定的问题），然后周期性地向外广播其路由表的内容。（2）路由器Ri收到相邻路由器Rj的距离矢量信息后，对自己的路由表进行修正。若Rj的距离矢量信息中所包含的目的节点va在Ri的路由表中没有，则在Ri的路由表中增加一个目的节点为va的条目，令dia=dja+1，并把到节点va的下一跳路由器设为Rj 。若到Rj目的节点vb的路由比Ri到目的节点vb的路由短，则令dib=dj

25、b+1 ，并把到节点vb的下一跳路由器设为Rj 。 Ri到目的节点vc最短路径上的下一跳是Rj 。如果Rj的路由表中不再包含到的vc路由，则在Ri中也应该把去往vc的路由删掉；如果Rj到vc的距离发生了变化，则Ri修改路由表中到vc的距离，令dic=djc+1 。距离矢量路由算法在理论上是可以正常工作的，但在实际中存在着一个严重的缺陷：尽管它可以收敛到正确的路由，但它对好消息传播的快，而对坏消息则传播的慢。总的来说，距离矢量路由选择协议的优点是易于实现，但难以适应网络拓扑的剧烈变动或者大型的网络环境。 链路状态路由算法 链路状态路由算法的基本步骤如下：（1）每一个路由器（节点）启动后，首先执行

26、对相邻节点的发现工作，并获取它们的地址。（2）各路由器主动测试到每一个相邻路由器的链路时延或成本，并根据测试结果设置相关链路的状态。（3）各路由器构造自己的L-S（Link-State，链路状态）信息包，L-S信息的内容包括本路由器的标号、本路由器的邻居路由器列表、本路由器到各邻居路由器的链路状态（时延或成本）、该L-S信息包的序号和生存时间等。（4）各路由器向所有参与链路状态交互的路由器广播其L-S信息，可以是周期性地发送，也可在链路状态发生变化时发送。 （5）每个路由器在收到所有的L-S信息后，可以构造或更新表示整个网络拓扑结构的图G（V，E），顶点V表示路由器，边E表示连接路由器的链路；

27、这时路由器就可以用Dijkstra算法从图G中计算出到所有目的路由器的最短路径，也就是构造以自己为根节点的SPF树。 Dijkstra算法简介 设目的节点（就构造SPF树而言，是根节点）为k，任一条链路（i，j）的长度为dij，每个节点到k的最短路径长度估计为Dik；定义所有节点的集合为A，定义集合PA，并设定集合的初始值为P=k。 在算法迭代的过程中，如果Dik已经变成一个确定值，则将i标记为固定点，并将其加入集合P。在算法的每一步迭代中，在P以外的节点中，选择与目的节点k最近的节点加入到P中，算法的具体步骤如下：Dijkstra算法简介（1）P=k, Dkk=0，Djk=djk（若j和k不

28、相邻， ）（2）求解使 成立的i， ，即寻找下一个和目的节点最近的节点；令 ，若P=A，算法结束。（3）对所有 ，置 ，返回步骤（2）本章提纲互联网的体系结构IP路由中的基本概念路由转发原理路由选择算法路由器硬件体系结构集中式单（多）CPU+总线结构缺陷CPU要负责整体系统的控制管理、路由计算和数据转发等各项功能，存在计算瓶颈。所有接口卡的数据都要争用总线，存在数据交换瓶颈。分布式多CPU+总线结构特点路由计算和转发分离：主控CPU负责整个系统的控制管理和路由计算（即运行路由协议，维护和更新路由表）；线卡上的CPU负责查询路由表，对数据进行转发。部分地克服了总线瓶颈，即如果数据的接收和发送都在

29、一个线卡上，就不用争用总线；若数据的接收和发送涉及不同的线卡，还是会出现总线争用问题。分布式多CPU+Crossbar结构特点路由计算和转发分离。采用Crossbar的交换结构（Switch Fabric），每个输入端口和输出端口之间都有一个交叉开关，只要数据流彼此不相关，就可以实现无阻塞的交换，解决了总线争用问题。基本上解决了路由器吞吐量的问题。交叉开关的设计和调度算法是研究的重点和难点。路由器硬件体系结构发展总结共享总线 交叉开关路由计算与转发分离第三章 路由查询 第一部分概述影响IP网络性能的关键因素链路速度路由器的吞吐量包转发速率对路由变化的快速适应性采用光纤等技术提高链路速度在路由器

30、中采用大容量的交换结构以提高吞吐量采用高效的路由查询算法和硬件路由查询方案提高包转发速率（路由查询）优化各种动态路由协议解决方案路由查询定义设分组的目的地址为D，包含长度为W的比特数。设路由前缀为P，包含的比特数为0W，L(P)表示前缀长度。地址D匹配前缀P的含义：地址D的前L(P)位比特值与前缀P完全相同。给定一个路由前缀集合PA，集合含有N个路由前缀，到达分组的目的地址为D，路由的最长前缀匹配查找定义为：在前缀集合PA中搜索到的前缀Pm满足：目的地址D匹配前缀Pm；在集合PA中不存在其他的前缀P，满足D匹配P，且L(P)L(Pm)为什么是最长前缀匹配而不是精确匹配CIDR等机制的引入：IP

31、地址是无类别的，从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查找分段查找哈

32、希表查找Cache命中查找等。按照路由查询的依据，可以分为：基于路由前缀值的查找基于路由前缀长度的查找路由查询算法评价标准时间复杂度（查找速度）空间复杂度（占用的存储空间）更新复杂度（增加、删除、变更路由表条目时，路由表的更新速度）可扩展性 注意，上述复杂度一般是指最坏情况下的复杂度。第二部分各种路由查询算法路由前缀值的线性查找所有路由前缀按照线性链表的方式组织。查询时要遍历路由表中的所有表项，并记录查询过程中匹配的最长路由前缀项，一直到最后一项为止。时间复杂度O(N)，空间复杂度O(N)，插入/删除路由前缀条目的复杂度为O(1)。如果使用有序链表，即把路由前缀按照长度大小排列，可以提高路由查

33、询的平均速度，但更新复杂度上升。此时，时间复杂度O(N)，空间复杂度O(N)，插入/删除路由前缀条目的复杂度为O(N)。基本的二叉检索树（Trie）路由前缀按照二叉树的结构来组织。树中的每个节点含有路由前缀的1比特信息，并根据下一个比特生成两个子节点。在树的非空节点处，存放该节点对应的下一跳信息。在进行最长前缀匹配时，首先根据路由前缀的比特信息遍历二叉树，达到最终匹配的叶子节点处，最后读出存储在叶子节点中的下一跳路由信息。基本二叉检索树的一个例子在查找的过程中，有可能出现多个前缀匹配的情况，如上图中的(A,C)和(B,D,E)，这时要选择最长的前缀。在查找时要记录当前最匹配的路由前缀，一直到叶

34、子节点或者节点没有合适的分支为止。例如，对于地址111*，按照上图的例子，当查到B时，由于是匹配的，所以就记录下相应的信息，继续向下查询，没有更匹配的路由前缀，所以此时B就是最长匹配的路由前缀。这种查找实际上是地址前缀长度空间的线性查找。因为是按照单个比特的顺序来查询的。很显然，使用基本的二叉检索树进行路由查询时，时间复杂度与树的深度（在这种算法中就等于路由前缀的最大长度）有关。如果最大可能的路由前缀长度为W，则最坏情况下的查找时间复杂度为O(W)。最坏情况下的空间复杂度为O(N*W) 。更新复杂度为O(W)。更新时需要先进行查找，找到之后进行相应的增删操作就可以了（包括中间节点和叶子节点两种

35、情况）。在IPv4中最多需要32次查找，在IPv6中最多需要128次查找。路径压缩Trie该算法是对基本二叉检索树的改进，最早起源于Patricia算法，后来Sklower对Patricia算法做了改进，使之可以用于路由查询。其基本思想是去掉输出为1的中间节点，压缩叶子节点的路径，将叶子节点提升到最近一级父节点的下一层。这样，每个中间节点都有两个输出。由于有可能去掉了一些包含路由前缀的中间节点，所有某些节点会有多个路由前缀。由于去掉了一些节点，某些比特将被忽略，所以节点要维护一个变量，用于维持下一个要检查的比特位。路径压缩Trie对稀疏的基本Trie有明显的压缩效果，但对稠密的则作用不大。路径

36、压缩Trie不能从本质上降低树的深度，在最坏情况下它的时间复杂度仍然为O(W)。路径压缩Trie的空间复杂度为O(N)，因为这种Trie中N个叶子节点对应N1个内部节点。路径压缩Trie更新算法的复杂度也是O(W)，其动态性比基本Trie要差，因为当需要加入或者删除叶子节点时，会导致其对应的若干条路径上的叶子节点位置发生变化。这种算法在BSD系统上得到了实现（Radix树），并随着BSD的推广而得到广泛应用。多比特检索树（Trie）在基本的二叉检索树中每次检查一个比特，即一级对应1个比特；如果让每一级对应多个比特，就可以大大降低树的深度。也就能够降低路由查询的时间复杂度。每一级对应的比特数被称

37、为查找步宽。同一级的步宽可以一样，也可以不一样。前者实现起来比较简单，但浪费存储空间，后者实现复杂一些，但是会节省一定的存储空间。因为一次查找多个比特，因此不能处理任意长度的路由前缀，一般要使用前缀扩展。每一级的步宽都是2 第一级的步宽是2 第二级三个节点步宽是2，一个节点步宽是1对于上图中绿色部分，如何应用多比特检索？前缀扩展：将一条较短的路由前缀展开成多条较长的路由前缀集，这些前缀集的转发信息就是原来地址前缀所对应的转发信息。也就是扩展后的路由前缀要继承原来前缀的转发信息。例如，1*可以扩展为10*和11*。对于Trie中不能直接应用多比特树的地方，可以先进行前缀扩展，使应用多比特树的局部

38、成为一个满的子树。由于步宽大于等于1，使检索树的深度明显降低，所以多比特检索树的时间复杂度比基本二进制Trie或路径压缩Trie要低，具体的数值与每一级步宽有关。当每一级步宽都是K时（这是多比特检索树中最简单的情况），时间复杂度为O(W/K)。时间复杂度降低的代价就是空间复杂度的上升，每一个中间节点都需要包含2k个指针（每一级步宽都是K），最差情况下每加入一个新前缀，需要插入W/K个中间节点，从而需要占用空间O(2k *W/K)，所以空间复杂度为O(N*2k *W/K)。更新时需要进行一次路由查找，然后更新节点的指针，最差情况下需要更新2k-1指针，所以更新复杂度为O(2k W/K)。对于多比

39、特检索树来说，当步宽为1时，就成为基本二叉检索树或路径压缩树，当步宽达到W时，时间复杂度为O(1)，但空间复杂度变为O(2W)。很显然，多比特检索树的主要问题就是引入了很多冗余路由前缀，占用了大量存储空间，所以对它的优化是研究的一个重点，例如有些人就提出了步宽选择策略，也有人提出了一些压缩算法。实际进行压缩时可以考虑互联网地址分布的特点，例如长度1624之间的前缀数最多。叶子扩展的概念路由前缀长度空间的二分查找Trie树算法的实质是地址前缀长度空间的线性查找：先检查第1个（1k）个比特，再检查第2个（k+12k）个比特，一直到路由前缀的最大长度为止。文献“Scalable high-speed

40、 prefix matching，Marcel Waldvogel,George Varghese,Jon Turner, Bernhard Plattner ，ACM Transactions on Computer Systems, 2001”提出了地址前缀长度空间的二分查找法。基本思想是把所有路由前缀按照其长度分为不同的前缀集合，每个前缀集合内采用哈希算法查找；查询时，从长度位W/2的集合开始，采用二分查找法。图中节点对应的是前缀集合，而不是某个或某几个比特位为了保证该算法的正确性，需要引入一个被成为Marker的表项。考虑下面的例子。有4个地址前缀：0*、1*、00*、110*。现查找

41、110*。路由前缀长度空间的二分查找在路由查询方面的时间复杂度为O(logW)，对IPv4来说，最多需要5次查询，对IPv6来说，最多需要7次查询。对于每个前缀，最多可能需要logW个Marker，因此，算法的空间复杂度为O(N*logW)。路由更新比较麻烦，其复杂度为O(N*logW)，因为最坏情况下更新一个前缀可能影响N-1个前缀，而一个前缀又有可能对应logW 个Maker。哈希算法也是该算法中的关键问题。TCAMTCAM（Ternary Content Address Memory）是一种新型的存储器，存放一系列路由表项，为到来的每一个分组并行查找所有的路由前缀。因此，它的路由查询只需

42、要一次内存访问，若有多个匹配表项，经过优先级比较后，确定路由信息。路由管理比较复杂，路由表的动态删除和更新会导致TCAM中存放大量的碎片。成本昂贵，功耗比较大，存储容量小。这实际上是一种硬件查找方法。基于分段的查找这种方案实际上是多比特检索树的具体硬件实现方案。典型的是Gupta等人提出的DIR-24-8-BASIC查找算法。DIR-24-8-BASIC算法是把IPv4地址空间分为长度分别为24和8的两部分（TBL24和TBLlong），最大内存访问次数为2，采用硬件流水线技术可以用1次内存访问。第一部分是22416M个表项；第二部分256个表项。因为是基于多比特检索树，因此需要进行前缀扩展。

43、第一级中的节点携带的指针信息指示可能存在于第2级中的一棵子树。缓存（Cache）策略缓存策略是指把最近查找过的目的地址和路由下一跳信息放在缓存之中，当IP分组达到时，先从缓存中查找，找不到时再执行最长前缀匹配策略。显然，数据包的相关度越大，这种方法的有效性就越高。缓存的命中率是这种策略的一个关键。由于缓存容量有限，且数据日益多样化，缓存的命中率大大降低。哈希查找哈希(Hash)算法在路由查询中应用的时候，通过查找建立的哈希索引，来找到对应的路由前缀。理论上讲，哈希算法的时间复杂度和空间复杂度都很低，但实际上很难找到一个完美的或者近似完美的哈希函数。另外，路由更新也往往会导致哈希表的重建。一般来

44、说，把整个路由表做为一个哈希表是不切实际的，可以在局部范围内应用哈希算法。如在前缀长度空间的二分查找中，就可以在同一前缀长度的前缀集合内应用哈希算法。其他路由查询算法层压缩树地址区间的二分查找法多路和多列查询算法等第三部分路由查询算法的评测算法时间复杂度空间复杂度更新复杂度基本二叉检索树O(W)O(N*W)O(W)路径压缩检索树O(W)O(N)O(W)多比特检索树O(W/K)O(2K*N*W/K)O(W/K+2K)前缀长度空间的二分查找O(logW)O(N*logW)O(N*logW）基本算法在时间复杂度等方面的比较其他需要考虑的方面算法的可扩展性。即路由前缀长度增加后，不能使查询的复杂度大幅

45、度上升。路由前缀长度空间的二分查找的扩展性比较好，从IPv4到IPv6后，最差情况下的查询次数从5升到7。各种基于检索树的查找算法可扩展性一般，多比特查找树可以通过增加K的方法来降低时间复杂度，但会带来空间复杂度的大幅度上升。不过也可以通过分段的方法来部分地解决这方面的问题。对路由查询算法实际评测的方法测试数据：包括路由前缀和目的地址序列两部分。路由前缀的生成有三种方法典型数据生成，即采用骨干路由器统计的实际路由表，测试结果更有实际意义。随机生成，测试结果可以反映算法的平均性能。拓扑结构生成，模拟互联网拓扑结构生成测试数据。目的地址序列的生成有两种方法随机地址生成加权随机地址生成，即按照互联网

46、实际目的地址的分布情况进行加权。被测算法指具体被评测的路由查询算法参考算法是指用来参照对比的基本路由查询算法，如路径压缩Trie等。测试执行则是从查询的时间复杂度、空间复杂度、更新复杂度等几个方面进行测试。测试结果反映被测算法在各个评价标准方面的性能。路由查询和路由更新的分析模型一般来说，为了提高路由查询的速度，往往采用比较复杂的数据结构，这就造成路由更新的效率很低。路由查询和路由更新都要访问路由表，由于读写的冲突，它们对路由表的访问一般是互斥的。通常考虑的是路由更新对路由查询的影响。路由查询和路由更新之间的定量关系，还没有一个明确的结论。一个简单的分析模型路由查询请求的到达一般是泊松分布；路

47、由更新的则未必是，具体的分布目前还没有定论，为了简单起见，可以假设也是泊松到达。实际中路由查询请求的到达率要远大于路由更新请求到达率。一般来说，路由更新请求不会被丢弃，但路由查询请求就不一定了，如果网络拥塞，或者分组排队时间过长，都有可能造成分组被丢弃，自然路由查询请求也就被丢弃了。在实际路由器中，路由查询和路由更新一般没有优先级区别。可以把路由表做为一个服务者，它的服务时间是一般分布。路由更新的服务时间一般要大于路由查询的服务时间。第四部分流分类简介流分类概述根据一定的分类规则，检查IP数据包中的多个字段，对IP包进行分类，并应用不同的处理策略。也称为IP包分类或者IP分类。需求：防火墙策略

48、路由服务质量流量计费等。检查的字段：源地址和目的地址源端口和目的端口协议(IPv4)、下一个首部(IPv6)业务类型(IPv6)流标签(IPv6)等。处理策略：是否转发数据包；向哪里转发数据包；数据包应该得到什么样的服务；相应流量数据包应该收取多少费用等。流分类一般要检查IP数据包中的多个字段（域），而路由查询只检查目的IP地址字段，如果把路由查询看作是一维检索的话，那么流分类就是多维检索。实际上也可以把路由查询看成是流分类的一个特例。流分类的数学定义每一条流分类规则R和数据包首部H中的d个域（维）有关，相应地可以把每一条规则划分为d个分量（可以假设每一分量有W个比特）。我们称规则R和首部H匹

49、配，当且仅当H的每一个域Hi和R相应的域Ri匹配。H可能匹配规则库RS中的多条规则（即发生规则冲突），因此要为每一条规则赋予一个优先级。流分类实质上就是在RS中搜索给定数据包首部H的最佳匹配规则的过程。通常，最佳匹配规则指优先级最高的规则。给定一个流分类规则集合RS，集合含有N个规则，设到达的数据包首部为H，规则集合中可能存在多个规则Ri匹配H。对于每一条规则，赋予一个优先级prii，用pri(R) 来表示。则流分类的数学定义为：在流分类规则集合RS中搜索规则Rm满足以下条件：数据包首部H匹配规则Rm在规则集合RS中不存在另外的规则R，满足H匹配R，且pri(R) 大于pri(Rm) 流分类算

50、法的类别直接查找存储器，预处理时建立线性的数据结构，通过查找线性数据结构和一些处理获得最终结果。包括线性查找、TCAM、Cross-producting、位向量（BV）、RFC （Recursive Flow Classification）等。其中Cross-producting、位向量等算法利用了计算几何中点定位问题的思想； RFC 算法则是利用了映射和分段的思想，即可以把IP分类看成是从数据包首部中的S比特到T比特的一个集合的映射，同时引入分段以降低对存储容量的需求（实际上多维归并为一维）。基于查找树，预处理时建立以查找树为中心的数据结构，有分层查找树、集合归并查找树、网格查找树、智能分层

51、查找树等。分层查找树是一维Trie的扩展，从d维中选任一维生成第一级二进制Trie，对于该Trie中每一个与第一维匹配的节点（有些节点是因为树的生成而引入的），再按照第二维建立另一个二叉树，反复这一过程直到完成对每一维的处理，时间复杂度为Wd，空间复杂度为NdW；其他算法基本上属于在此基础上的改进。利用哈希表。流分类算法的评价时间复杂度，即查找速度快，包括最坏情况、平均情况、统计情况等，一般也是用内存访问次数来衡量；空间复杂度，即占用内存小；易于更新，包括完全更新、增量更新等。第四章 RIPng RIP简介RIP（Routing Information Protocol，路由信息协议）是一种基

52、于距离矢量路由选择算法的内部网关路由协议。RIP的版本有RIPv1、 RIPv2和RIPng，前两者用于IPv4， RIPng用于IPv6。RIP最大的特点就是简单，但难以用于大型的网络。RIP的发展历史Xerox公司和加州大学伯克利分校在80年代初都开发了RIP的早期版本。1988年的RFC 1058对RIP协议做了说明，后来被称为RIPv1。1998年，IETF推出了RIP改进版本的正式标准RFC 2453，即RIPv2：支持子网掩码信息；支持路由对象标志；支持路由更新鉴别。1997年IETF推出了下一代RIP协议RIPng的建议标准RFC 2080。第一部分 RIP的工作过程概 述RIP

53、是一种典型的基于距离矢量路由算法的动态路由协议，所以它的工作过程实际上就是距离矢量路由算法的具体化。运行RIP的路由器维持一个到网络中可能目的地的路由表，包含目的地址和跳数等信息。路由器周期性地向它直接相连的网络邻居发送它的RIP路由表，即距离矢量（V，D）信息。每一个接收者都修正自己RIP路由表中的距离矢量，并向它自己的邻居直接转发，最终使所有的路由器都知道别的路由器的情况。RIPv1分组格式基于UDP，端口号520RIPv2分组格式基于UDP，端口号520RIPng分组格式基于UDP，端口号521 RIP路由器信息交互过程 当在路由器A的某接口上启动RIP后，接口以多播形式（RIPng使用

54、多播地址FF02:9，RIPv2使用）向邻居发送信息请求，请求邻居给自己发送RIP路由表信息；邻居B接收到路由表信息请求，发送整个RIP路由表信息对请求进行响应；路由器A和路由器B在启动后就开始周期发送，周期更新；路由器A检测到路由变化时，以多播形式向邻居发送触发更新，通知邻居路由的变化情况。距离矢量的计算RIP度量的单位是跳数，其单位是1，也就是规定每一条链路的成本为1，而不考虑链路的实际带宽、时延等因素，RIP最多允许15跳。RIP利用度量来表示它和所有已知目的地间的距离。当一个RIP更新报文到达时，接收方路由器和自己的RIP路由表中的每一项进行比较，并按照距离矢量路由算法对自己的RIP路

55、由表进行修正。 第二部分 RIP定时器定时器分类周期更新定时器：用来激发RIP路由器路由表的更新，每个RIP节点只有一个更新定时器，设为30s。每隔30s路由器会向其邻居广播自己的路由表信息。每个RIP路由器的定时器都独立于网络中其他路由器，因此它们同时广播的可能性很小。超时定时器：用来判定某条路由是否可用。每条路由有一个超时定时器，设为180s。当一条路由激活或更新时，该定时器初始化，如果在180s之内没有收到关于那条路由的更新，则将该路由置为无效。定时器分类清除定时器：用来判定是否清除一条路由。每条路由有一个清除定时器，设为120s。当路由器认识到某条路由无效时，就初始化一个清除定时器，如

56、果在120s内还没收到这条路由的更新，就从路由表中将该路由删除。延迟定时器：为避免触发更新引起广播风暴而设置的一个随机的延迟定时器，延迟时间为15s。定时器的作用触发路由更新 识别无效路由 清除无效路由 第三部分RIP路由表的建立和维护过程一个IPv6网络的例子RIP路由表的建立过程RIP路由表的维护累加至无穷问题。解决方案：视野分离（水平分割）带毒性逆转的视野分离触发更新视野分离基本思想：如果A的某条路由是从B学来的，则它向B通告的RIP信息中将不会包含这条路由。带毒性逆转的视野分离基本思想：A如果从B学习了一条路由，则在它给B的RIP信息中，将包含这条路由，只不过将度量设成16。触发更新触

57、发更新要求路由器不管30s周期更新定时器中还剩多少时间，每当它改变一个路由度时，就立即广播一个更新消息，从而加快收敛速度。 RIPng总结优点：简单，易用，管理方便局限性：跳数限制：15跳为最大值“无穷”计数：收敛速度慢静态度量：无法根据网络性能进行选路第五章 OSPFv3 OSPF简介OSPF（Open Shortest Path First，开放最短路径优先协议 ）是一种基于链路状态路由选择算法的内部网关路由协议。OSPF的版本有OSPFv1、 OSPFv2和OSPFv3，前两者用于IPv4， OSPFv3用于IPv6。OSPF的功能比RIP强大的多，适用于比较大型的网络，但也很复杂。OS

58、PF的发展历史1989年的RFC 1131是描述OSPF的第1个IETF标准，这个版本被称为OSPFv1。 1998年形成了OSPFv2的最终标准RFC 2328。 IETF在1999年12月发布了基于IPv6的OSPF路由协议标准RFC 2740，被称为OSPFv3。 OSPF的基本思想每个OSPF路由器都维护一个用于跟踪网络状态的链路状态数据库（LSDB），各路由器通过链路状态信息的交换实现LSDB的一致。 OPSF基于Dijkstra算法和自治系统中路由器的链路状态进行路由计算，得到最短路径。LSDB和LSALSDB（Link State DataBase ）是每个OSPF路由器都要维护

59、的一个数据库，用于描述、记录网络的拓扑结构，实际上就是一张完整的网络图，路由器可以按照该图计算出全部的最短路由。LSDB的每一个记录称为LSA（Link State Advertisement ）。LSA用于描述网络拓扑结构中每一条链路的相关信息，包括接口描述符（链路标号）、链路状态信息等。第一部分 区域划分划分3个区域的自治系统区域划分的目的降低LSDB的大小。减少LSA交互的数量。减轻路由计算量。区域的分类主干域（0域）普通域（非0域）虚连接区域划分中的注意事项不同区域的LSDB是不一样的；某个区域的详细拓扑结构对其他区域来说是不可见的；区域边界路由器可以同时属于多个域，其中肯定有主干域。

60、OSPF路由器分类区域内部路由器（Internal Router，IR） 区域边界路由器（Area Border Router，ABR） 主干路由器 （Backbone Router，BR） 自治系统边界路由器 （AS Boundary Router，ASBR） OSPF路由选择分类 域内路由域间路由自治系统外部路由 域内路由域间路由第二部分 呼叫协议呼叫协议简介呼叫协议是通过路由器周期性地发送Hello包来实现的。它的作用主要包括两点：建立和维护OSPF路由器之间的邻居关系。在广播和NBMA网络中选取指派路由器DR（Designed Router ）和备份指派路由器BDR（Backup De