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

《互联网设计全套课件完整版电子教案最新板.ppt》由会员分享，可在线阅读，更多相关《互联网设计全套课件完整版电子教案最新板.ppt（350页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、互联网设计互联网设计 互联网设计分类互联网设计分类v骨干网设计骨干网设计给定节点位置和节点间流量，在网络成本最小原则下，选择给定节点位置和节点间流量，在网络成本最小原则下，选择每条链路的容量和流量，满足时延等要求。（试探法，求最每条链路的容量和流量，满足时延等要求。（试探法，求最小截边集）小截边集）v接入网设计接入网设计有线接入（光纤、有线接入（光纤、XDSL、同轴电缆等）、同轴电缆等）无线接入（移动接入、固定接入）无线接入（移动接入、固定接入）IP子网划分子网划分可参考可参考通信网络基础通信网络基础（李建东，高教出版社）（李建东，高教出版社）第七章第七章网络设计的基本原则网络设计的基本原则v

2、小的顶点度小的顶点度v小通信传输延迟（小的直径和平均距离）小通信传输延迟（小的直径和平均距离）v简单的路由算法简单的路由算法v均匀性或对称性（点可迁）均匀性或对称性（点可迁）v高容错性（高的连通度）高容错性（高的连通度）v可扩性可扩性v可嵌入性可嵌入性可嵌入性可嵌入性v嵌入即一个拓扑结构到另一个拓扑结构的映射。嵌入即一个拓扑结构到另一个拓扑结构的映射。v设设G和和H是两个给定的图，从是两个给定的图，从G到到H的嵌入就是一个的嵌入就是一个从从G到到H的映射的映射：V(G)V(H)使得对任何使得对任何(x,y)E(G),它的象它的象(x,y)是是H中一条中一条(x),(y)路。路。G称称为客图，为

3、客图，H称为主图。称为主图。v衡量嵌入优劣的参数：膨胀数（客图中边被拉长的衡量嵌入优劣的参数：膨胀数（客图中边被拉长的最大长度）、拥塞（用到主图中某条边的最大次数）最大长度）、拥塞（用到主图中某条边的最大次数）、负载（用到主图中某一顶点的最大次数）。、负载（用到主图中某一顶点的最大次数）。连通度连通度v可以分为点连通度和边连通度可以分为点连通度和边连通度v局部点连通度局部点连通度:(x,y)的最小点分离集中的顶点的最小点分离集中的顶点数数v局部边连通度局部边连通度:(x,y)的最小截边集中的边数的最小截边集中的边数v整体点连通度整体点连通度v整体边连通度整体边连通度v是网络可靠性分析中最重要的

4、参数之一。是网络可靠性分析中最重要的参数之一。最小点分离集示例最小点分离集示例最小截边集示例最小截边集示例网络流的概念网络流的概念v对于容量网络对于容量网络N=(Dxy，c)，存在，存在f(D),满足满足则称则称f是是N中从中从x到到y的流。的流。v最大流最小截定理：任何容量网络最大流最小截定理：任何容量网络N中，最大流中，最大流量等于最小截容量。量等于最小截容量。Menger定理定理v用用表示最小（表示最小（x,y）截边集中的边数；用）截边集中的边数；用表示最小表示最小(x,y)分离集中的顶点数目。分离集中的顶点数目。v用用和和分别表示分别表示D中内部点不交和边不交的中内部点不交和边不交的(

5、x,y)路的路的最大条数。最大条数。则则vMenger定理是网络连通度理论中最重要的定理之一，在网络可定理是网络连通度理论中最重要的定理之一，在网络可靠性分析中具有重要的地位，而且可以推导出匹配理论中的靠性分析中具有重要的地位，而且可以推导出匹配理论中的Hall定理，定理，Tutte定理和定理和Knig定理。定理。点可迁图的概念点可迁图的概念v同构：对于两个图同构：对于两个图和和存在两个双射存在两个双射满足满足点可迁图的概念点可迁图的概念v自同构：图自同构：图D到自身的同构称为自同构，即到自身的同构称为自同构，即V(D)上保相邻性上保相邻性条件的置换。条件的置换。v所有这些置换构成所有这些置换

6、构成D的自同构群，简称的自同构群，简称D的群，记为的群，记为Aut(D)。v确定一般图的自同构群是困难的。确定一般图的自同构群是困难的。点可迁图的概念点可迁图的概念vD是简单图，是简单图，若存在若存在,满足满足则称则称x1和和x2是点相似的是点相似的.v若若D的每对顶点都是点相似的，则称的每对顶点都是点相似的，则称D是点可迁的。是点可迁的。v循环图是点可迁的，一般图的点可迁性判定是困难的。循环图是点可迁的，一般图的点可迁性判定是困难的。v性质：点可迁图必是正则图性质：点可迁图必是正则图;点可迁图任何节点发生故障点可迁图任何节点发生故障不影响其他节点不影响其他节点。补充知识：群的概念补充知识：群

7、的概念v定义：非空集合定义：非空集合G上定义一种运算上定义一种运算“”，满足，满足G中任两中任两个元素个元素a和和b，可唯一确定，可唯一确定G中一个元素中一个元素ab，且满足以下，且满足以下三个条件：结合律、单位元存在、逆元存在。则称三个条件：结合律、单位元存在、逆元存在。则称G是一是一个群。例如全体整数对数的加法构成一个群。个群。例如全体整数对数的加法构成一个群。v按元素是否有限可分为有限群和无限群。按元素是否有限可分为有限群和无限群。v最重要的一种有限群是置换群。最重要的一种有限群是置换群。vCayley定理：任一个定理：任一个n阶有限群同构于一个阶有限群同构于一个n元置换群。元置换群。线

8、图设计方法线图设计方法v设设G=(V,E)是无孤立点的简单无向图（有向图），是无孤立点的简单无向图（有向图），G的线图记的线图记为为L(G)，其顶点集为，其顶点集为E(G)，对，对G中任意两条不同的边中任意两条不同的边e1和和e2，它们在，它们在L(G)中相邻当且仅当它们在中相邻当且仅当它们在G中相邻。中相邻。线图设计方法线图设计方法Cayley图设计方法图设计方法vG是非平凡有限群，是非平凡有限群，S是是G中不含单位元的非空真子集，定义中不含单位元的非空真子集，定义有向图有向图D=(V,E)如下：如下：V(D)=G;笛卡尔乘积法笛卡尔乘积法设设和和是两个无向图，是两个无向图，G1和和G2 的

9、笛卡尔乘的笛卡尔乘积为积为。其中。其中两个不同的顶点两个不同的顶点x1x2和和y1y2 相邻当相邻当且仅当且仅当或或第一章第一章 互联网概论互联网概论 本课程主要内容本课程主要内容1.互联网概论互联网概论2.下一代互联网基础下一代互联网基础3.下一代互联网动态路由协议下一代互联网动态路由协议4.下一代互联网关键技术下一代互联网关键技术5.未来互联网络发展趋势未来互联网络发展趋势6.讨论与观摩讨论与观摩任课教师：任课教师：、郜帅、郜帅邮件：邮件：办公室：机械工程楼办公室：机械工程楼D802/D701C电话：电话：51685364/1352023886751684274/13811229737本章

10、提纲本章提纲互联网的基本概念互联网的基本概念互联网的发展历史互联网的发展历史互联网的主要问题互联网的主要问题下一代互联网概述下一代互联网概述电信网电信网互联网互联网广电网广电网 互联网互联网是主要实现计算机和计算机之间互联互通是主要实现计算机和计算机之间互联互通的一种信息网络。的一种信息网络。互联网的定义互联网的定义v国际国际“联合网络委员会联合网络委员会”（FNC：FederalNetworkingCouncil）给互联网的定义给互联网的定义“互联网互联网”指的是全球指的是全球性的信息系统：性的信息系统：1.通过全球性的唯一的地址逻辑地链接在一起。这个地址是建通过全球性的唯一的地址逻辑地链接

11、在一起。这个地址是建立在立在“互联网协议互联网协议”（IP）或今后其它协议基础之上的；）或今后其它协议基础之上的；2.可以通过可以通过“传输控制协议传输控制协议”和和“互联网协议互联网协议”（TCP/IP），），或者今后其它接替的协议或与或者今后其它接替的协议或与“互联网协议互联网协议”（IP）兼容）兼容的协的协议来进行通信；议来进行通信；3.可以让公共用户或者私人用户使用高水平的服务，这种服务可以让公共用户或者私人用户使用高水平的服务，这种服务是建立在上述通信及相关的基础设施之上的。是建立在上述通信及相关的基础设施之上的。三个方面的含义三个方面的含义v互联网是全球性的；互联网是全球性的；v互

12、联网上的每一台主机都需要有互联网上的每一台主机都需要有“地址地址”；v这些主机必须按照共同的规则（协议）连接在这些主机必须按照共同的规则（协议）连接在一起。一起。本章提纲本章提纲互联网的基本概念互联网的基本概念互联网的发展历史互联网的发展历史互联网的主要问题互联网的主要问题下一代互联网概述下一代互联网概述1946年世界上第一台电子计算机诞生年世界上第一台电子计算机诞生互联网诞生的技术背景互联网诞生的技术背景资源共享的需求资源共享的需求推动计算机与通信结合与发展！推动计算机与通信结合与发展！互联网诞生的时代背景互联网诞生的时代背景v1957年，前苏联发射了人类第一颗人造地球卫星。作为响应，年，前

13、苏联发射了人类第一颗人造地球卫星。作为响应，美国国防部组建了高级研究计划署美国国防部组建了高级研究计划署(ARPA)，研究将科学技，研究将科学技术应用于军事领域。术应用于军事领域。v1961年年MIT的的LeonardKleinrock发表发表“InformationFlowinLargeCommunicationNets”，第一篇有关分组交换的论，第一篇有关分组交换的论文。文。v1969年，为了能在爆发核战争时保障通信联络，美国国防部年，为了能在爆发核战争时保障通信联络，美国国防部高级研究计划署高级研究计划署ARPA资助建立了世界上第一个分组交换试资助建立了世界上第一个分组交换试验网验网AR

14、PANET，连接美国四个大学。，连接美国四个大学。ARPANET即为现代即为现代互联网的前身。互联网的前身。斯坦福研究院犹他大学UCSBUCLAARPANETARPANET最初的结构最初的结构TCP/IP协议的提出协议的提出 v1974年，年，VintonCerf和和RobertKahn提出了提出了TCP/IP协议族，用以解决不同计算机网络的互联问题协议族，用以解决不同计算机网络的互联问题。v1981年，年，IP的协议规范的协议规范RFC791和和TCP的协议规范的协议规范RFC793出现，并在出现，并在1983年成为年成为ARPNET的正式标的正式标准，这使准，这使ARPNET的规模迅速扩大

15、。的规模迅速扩大。互联网的诞生互联网的诞生v20世纪世纪80年代中期，美国国家自然科学委筹建年代中期，美国国家自然科学委筹建NSFNET。vNSFNET是一个通用的研究网络，它将地区网络连是一个通用的研究网络，它将地区网络连接起来，原来连接到接起来，原来连接到ARPANET的的大学电脑大学电脑，转为转为接入接入NSFNET，成为互联网的骨干网。，成为互联网的骨干网。v到到20世纪世纪90年代初，年代初，NSFNET被一个更有竞争力、被一个更有竞争力、商业化更强的骨干网商业化更强的骨干网ANSNET代替，将代替，将Internet向向商业用户开放。商业用户开放。万维网的出现万维网的出现服务器服务

16、器连接到互联网连接到互联网My webpageHello world!This is my first webpage!My webpageHello world!This is my first webpage!My webpageHello world!This is my first webpage!超文本超文本1992年，欧洲粒子物理实验室提出了一个称为年，欧洲粒子物理实验室提出了一个称为WWW（WorldWideWeb）的概念，随后一年，发布了称为）的概念，随后一年，发布了称为Mosaic的的WWW客户程序。这是客户程序。这是Internet发展史上一个划时代发展史上一个划时代的事件

17、，因为它使得的事件，因为它使得Internet从一个由科学家和研究人员使用从一个由科学家和研究人员使用的文本工具转变为可由普通人就可以使用的图形工具的文本工具转变为可由普通人就可以使用的图形工具。从从IPv4到到IPv6v以以TCP/IP协协议议体体系系为为基基础础技技术术支支撑撑的的互互联联网网在在取取得得巨巨大大成成功功的同时，也面临着越来越多的挑战和问题。的同时，也面临着越来越多的挑战和问题。v直接原因：互联网规模迅速膨胀和各种新业务不断出现。直接原因：互联网规模迅速膨胀和各种新业务不断出现。v根本原因：现有根本原因：现有IPv4协议存在着诸多设计上的缺陷，包括：协议存在着诸多设计上的缺

18、陷，包括：地址空间不足地址空间不足配置复杂配置复杂不能很好的支持语音和视频服务不能很好的支持语音和视频服务安全性不高安全性不高移动性支持差移动性支持差从从IPv4到到IPv6v互互联联网网的的标标准准化化组组织织IETF从从20世世纪纪90年年代代就就着着手手制制订订下下一一代代网际协议网际协议IPv6。v1996年年，描描述述IPv6及及其其支支持持协协议议的的RFC出出现现（这这些些RFC基基本本上都已经被新的标准所代替上都已经被新的标准所代替）。）。v1998年年，新新的的描描述述IPv6的的协协议议标标准准RFC 2460取取代代了了旧旧的的RFC1883，新新的的描描述述IPv6地地

19、址址结结构构的的RFC2373代代替替了了RFC1884，而这个，而这个RFC在在2003年又被年又被RFC3513所代替。所代替。v目前目前IPv6已经形成了比较完善的协议体系。已经形成了比较完善的协议体系。本章提纲本章提纲互联网的基本概念互联网的基本概念互联网的发展历史互联网的发展历史互联网的主要问题互联网的主要问题下一代互联网概述下一代互联网概述互联网通信示意互联网通信示意数据转发（路由）问题数据转发（路由）问题 信息在互联网上传递，有两个基本问题需要解决：信息在互联网上传递，有两个基本问题需要解决：一个是数据在链路上的传输；另一个就是数据在中一个是数据在链路上的传输；另一个就是数据在中

20、间节点的转发。间节点的转发。对比：火车运行需要铁轨，还需要车站的调度对比：火车运行需要铁轨，还需要车站的调度如何实现快速正确的数据转发？如何实现快速正确的数据转发？v互联网中负责对各种数据进行交换转发的设备称为路由器。互联网中负责对各种数据进行交换转发的设备称为路由器。v路由器要实现快速正确的数据转发，有两个关键问题需要解路由器要实现快速正确的数据转发，有两个关键问题需要解决：决：v路由器应该知道向哪个方向转发数据路由器应该知道向哪个方向转发数据不能南辕北辙不能南辕北辙v路由器知道向哪个方向转发数据后，要快速的对数据进行处理路由器知道向哪个方向转发数据后，要快速的对数据进行处理v第一个问题的解

21、决：第一个问题的解决：动态路由协议动态路由协议v第二个问题的解决：路由器硬件体系结构、调度算法、路由第二个问题的解决：路由器硬件体系结构、调度算法、路由查询算法等。查询算法等。移动性问题移动性问题v电信网：有线电信网：有线无线无线移动移动v互联网的发展也遵循同样的规律互联网的发展也遵循同样的规律安全和管理问题安全和管理问题v互联网是一个开放性的网络，在给人们带来互联网是一个开放性的网络，在给人们带来方便的同时，也存在严重的安全隐患。方便的同时，也存在严重的安全隐患。v常见的网络安全问题：常见的网络安全问题：以各种方式有选择的破坏信息。如：修改、删除、以各种方式有选择的破坏信息。如：修改、删除、

22、伪造、冒充、制造病毒等。伪造、冒充、制造病毒等。在不干扰网络信息系统正常工作的情况下，进行在不干扰网络信息系统正常工作的情况下，进行侦听、截获、窃取、破译和业务流量分析。侦听、截获、窃取、破译和业务流量分析。组播问题组播问题从视频服务器上下载视频，假设每人占用1M带宽，10个人就是10M，那1万个人呢？大家用同一个地址来接收视频，1万个人也是1M带宽，这就是组播技术，即一对多，可以有效降低网络资源的消耗。多种业务支持问题多种业务支持问题不仅包括传统的数据业务，还要包括语音和视频等各种业务本章提纲本章提纲互联网的基本概念互联网的基本概念互联网的发展历史互联网的发展历史互联网的主要问题互联网的主要

23、问题下一代互联网概述下一代互联网概述互联网面临的重大技术挑战互联网面临的重大技术挑战互联网在不断演进和发展的过程中，面互联网在不断演进和发展的过程中，面临着重大的技术挑战，这些挑战包括：临着重大的技术挑战，这些挑战包括：地址空间即将耗尽地址空间即将耗尽网络安全可信度差网络安全可信度差移动漫游能力有限移动漫游能力有限可扩展性压力日增可扩展性压力日增网络质量难以保障网络质量难以保障运营管理水平亟待提升运营管理水平亟待提升主要技术路线主要技术路线v以解决当前互联网地址短缺为出发点，在以以解决当前互联网地址短缺为出发点，在以IP为核心的现有互联网上不断为核心的现有互联网上不断“演进演进”的路的路线，通

24、常称这一目标为线，通常称这一目标为“下一代互联网下一代互联网”。v以满足未来以满足未来1015年以后的互联网的发展需年以后的互联网的发展需要为出发点，重新设计新的互联网体系结构要为出发点，重新设计新的互联网体系结构的的“革命革命”路线，在有些国家将此体系目标路线，在有些国家将此体系目标称为称为“未来网络未来网络”或或“新一代互联网新一代互联网”。国内主要观点国内主要观点v不安全论不安全论v等待论等待论v落后论落后论v演进中创新论演进中创新论下一代互联网定义下一代互联网定义一般来说，一般来说，“下一代互联网下一代互联网”是指在目是指在目前互联网技术优势的基础上创新，较好解前互联网技术优势的基础上

25、创新，较好解决上述重大技术挑战的新一代互联网。决上述重大技术挑战的新一代互联网。下一代互联网主要特征下一代互联网主要特征v网络地址资源足够丰富网络地址资源足够丰富v基础设施更加先进基础设施更加先进v网络更加安全、可信、可控、可管、节能网络更加安全、可信、可控、可管、节能v更加智能地实现人与人、物与人、物与物更加智能地实现人与人、物与人、物与物互联互联全球下一代互联网发展现状全球下一代互联网发展现状v战略布局和规划措施战略布局和规划措施v网络建设、商用情况和产业规模网络建设、商用情况和产业规模v关键设备、软件、系统研发和产业化进展关键设备、软件、系统研发和产业化进展v技术、标准专利情况技术、标准

26、专利情况v基础理论研究情况基础理论研究情况美国：美国：FIND（FutureInternetDesign）和）和GENI（GlobalEnvironmentforNetworkingInnovation）计划。）计划。欧盟：欧盟：FIRE(FutureInternetResearchandExperimentation)计划。计划。我国下一代互联网发展现状我国下一代互联网发展现状v中国下一代互联网示范工程中国下一代互联网示范工程建成了大规模下一代互联网示范网络，包括建成了大规模下一代互联网示范网络，包括6个主干网、个主干网、2个国际交换中心、个国际交换中心、273个驻地网。个驻地网。v关键技术

27、研发关键技术研发863、支撑计划、支撑计划v基础研究基础研究973、国家自然科学基金、国家自然科学基金第二章第二章 下一代互联网基础下一代互联网基础 本章提纲本章提纲v互联网的体系结构互联网的体系结构vIP路由中的基本概念路由中的基本概念v路由转发原理路由转发原理v路由选择算法路由选择算法v路由器硬件体系结构路由器硬件体系结构v现有信息网络基本上都采用了分层的体系结构，即现有信息网络基本上都采用了分层的体系结构，即将其协议体系划分为若干个层次，每个层次完成特将其协议体系划分为若干个层次，每个层次完成特定的功能，这样，各个层次综合在一起，就可以完定的功能，这样，各个层次综合在一起，就可以完成一个

28、完整的系统功能。成一个完整的系统功能。v子子网网层层一一般般又又称称网网络络接接口口层层，负负责责从从网网络络层层接接收收IP报报文文并并向向物物理理网网络络发发送送，或或从从网网络络上上接接收收物物理理帧帧，取取出出IP数数据据报报并并提提交交给网络层。给网络层。v网网络络层层负负责责处处理理分分组组在在网网络络中中的的活活动动，提提供供跨跨越越多多个个网网络络的的选路功能，并对上层屏蔽底层具体子网技术的细节。选路功能，并对上层屏蔽底层具体子网技术的细节。v传传输输层层主主要要为为两两台台主主机机上上的的应应用用程程序序提提供供端端到到端端的的通通信信。在在IP网网络络中中，有有两两个个传传

29、输输协协议议：TCP（Transmission ControlProtocol，传传输输控控制制协协议议）和和UDP（UserDatagramProtocol，用户数据报协议）。用户数据报协议）。v应用层处理特定应用程序细节，为用户完成各种网络服务。应用层处理特定应用程序细节，为用户完成各种网络服务。本章提纲本章提纲v互联网的体系结构互联网的体系结构vIP路由中的基本概念路由中的基本概念v路由转发原理路由转发原理v路由选择算法路由选择算法v路由器硬件体系结构路由器硬件体系结构v路由器路由器路由器是工作在网络层上，可以连接不同类型的网络，能路由器是工作在网络层上，可以连接不同类型的网络，能够选择

30、数据传送路径并对数据进行转发的网络设备。从够选择数据传送路径并对数据进行转发的网络设备。从通信的角度看，路由器是一种中继系统。通信的角度看，路由器是一种中继系统。v路由表路由表路由器在接收到数据时，要对其传输路径进行选择。为了路由器在接收到数据时，要对其传输路径进行选择。为了实现这一目标，路由器需要维护一个称为实现这一目标，路由器需要维护一个称为“路由表路由表”的数的数据结构据结构。路由表包含若干条目，供路由器选路时查询数据传输路径。路由表包含若干条目，供路由器选路时查询数据传输路径。路由表中的一个条目至少要包含：路由表中的一个条目至少要包含：数据的目的地址（通常是目的主机所在网络的地址）数据

31、的目的地址（通常是目的主机所在网络的地址）下一跳路由器（即从本路由器出发按所给路径到给定目的地所要通下一跳路由器（即从本路由器出发按所给路径到给定目的地所要通过的下一个路由器）的地址过的下一个路由器）的地址相应的网络接口相应的网络接口一般情况下还应该有标志位等内容。一般情况下还应该有标志位等内容。泛洪（泛洪（Flooding）源路由源路由v选路策略和选路机制选路策略和选路机制选路策略（选路策略（RoutingPolicy）：根据数据包的目的地和网络）：根据数据包的目的地和网络的拓扑结构选择一条最佳路径，把对应不同目的地的最的拓扑结构选择一条最佳路径，把对应不同目的地的最佳路径存放在路由表中；佳

32、路径存放在路由表中；选路机制（选路机制（RoutingMechanism）：搜索路由表，决定向哪）：搜索路由表，决定向哪个接口转发数据，并执行相应的操作；个接口转发数据，并执行相应的操作；选路策略只影响路由表的内容，比如对同一个目的地址来选路策略只影响路由表的内容，比如对同一个目的地址来说，由于选路策略的不同，最佳路径可能会不一样，但说，由于选路策略的不同，最佳路径可能会不一样，但这并不影响选路机制的执行过程，只是会对其执行的结这并不影响选路机制的执行过程，只是会对其执行的结果产生影响。果产生影响。vIP网络地址结构网络地址结构指指IP地址（包括地址（包括IPv4和和IPv6）的编址方式。的编

33、址方式。通常把地址空间分为网络号和主机号两部分，当路由器在进行路径选通常把地址空间分为网络号和主机号两部分，当路由器在进行路径选择时，一般按照目的网络来查询，这样既可以降低路由表规模，也择时，一般按照目的网络来查询，这样既可以降低路由表规模，也可以提高路由查询效率。可以提高路由查询效率。早早期期IPv4网网络络把把地地址址分分为为A、B、C、D、E五五类类，浪浪费费了了大大量量的的地地址址空空 间间，并并 造造 成成 路路 由由 效效 率率 低低 下下。为为 解解 决决 这这 些些 问问 题题，出出 现现 了了CIDR（ClasslessInterDomainRouting，无无类类别别域域间

34、间路路由由）机机制制，即即不不再再严严格格的的对对IP地地址址类类别别进进行行区区分分，IP地地址址网网络络号号长长度度也也不不再再固固定。定。IPv6地地址址的的编编址址方方式式与与CIDR类类似似，也也是是不不限限定定网网络络号号空空间间的的长长度度，因此有很强的灵活性。因此有很强的灵活性。IP网络地址结构对路由选择和路由查询都有很大的影响。网络地址结构对路由选择和路由查询都有很大的影响。v自治系统和路由域自治系统和路由域由于由于Internet规模太大，分布范围太广，所以路由表中对规模太大，分布范围太广，所以路由表中对应每一个目的网络都有一个条目是不可能的；同样，也应每一个目的网络都有一

35、个条目是不可能的；同样，也不可能采用一个全局的路由算法或协议。因此，不可能采用一个全局的路由算法或协议。因此，Internet将整个网络划分为若干个相对自治的局部系统，即自治将整个网络划分为若干个相对自治的局部系统，即自治系统（系统（AS，AutonomousSystem）。）。自治系统自治系统可以定义为可以定义为同一机构下管理的路由器和网络的集合。同一机构下管理的路由器和网络的集合。一个自治系统内部还可以再划分几个小的路由域，也称作一个自治系统内部还可以再划分几个小的路由域，也称作区域。区域。v内部网关协议和外部网关协议内部网关协议和外部网关协议路由协议可以分为内部网关协议（路由协议可以分为

36、内部网关协议（IGP，InteriorGatewayProtocol）和外部网关协议（和外部网关协议（EGP，ExteriorGatewayProtocol）两大类。）两大类。v内部网关协议是用于自治系统内部的动态路由协议内部网关协议是用于自治系统内部的动态路由协议RIP（RoutingInformationProtocol，路由信息协议，路由信息协议）OSPF（OpenShortestPathFirst，开放最短路径优先，开放最短路径优先）；）；v外部网关协议是用于自治系统之间拓扑信息交换的路由协议外部网关协议是用于自治系统之间拓扑信息交换的路由协议BGP（BorderGatewayRout

37、ingProtocol，边界网关路由协议，边界网关路由协议）。）。v路由选择算法路由选择算法路由算法是指路由器获得对网络拓扑结构路由算法是指路由器获得对网络拓扑结构的认知，并为数据包选择正确传输路径的的认知，并为数据包选择正确传输路径的方法或者策略。方法或者策略。一一个个理理想想的的路路由由算算法法至至少少应应该该具具备备以以下下几几点点特特征征：完完整整性性和和正正确确性性；简简单单性性；健壮性；健壮性；公平性；公平性；最佳性。最佳性。路由算法的分类。路由算法的分类。v静态路由选择和动态路由选择静态路由选择和动态路由选择按按照照能能否否自自动动适适应应网网络络拓拓扑扑结结构构的的变变化化，可

38、可以以将将选选路路策策略略分分为为静静态态路路由由选选择择和和动动态态路路由由选选择择两两大大类。类。静态路由选择并不是表示路由表一成不变，只是静态路由选择并不是表示路由表一成不变，只是说明路由器不是通过彼此之间动态交换路由信息说明路由器不是通过彼此之间动态交换路由信息来建立和更新路由表的。来建立和更新路由表的。动态路由选择是通过网络中路由器间的相互通信动态路由选择是通过网络中路由器间的相互通信来传递路由信息，利用接收到的路由信息自动更来传递路由信息，利用接收到的路由信息自动更新路由表。新路由表。v距离矢量路由选择协议和链路状态路由选择协议距离矢量路由选择协议和链路状态路由选择协议距离矢量路由

39、选择协议基于距离矢量路由算法。其基本思想是路由器距离矢量路由选择协议基于距离矢量路由算法。其基本思想是路由器周期地和相邻路由器交换路由表中的信息。这种信息是由若干（周期地和相邻路由器交换路由表中的信息。这种信息是由若干（V，D）对组成的表项，其中，对组成的表项，其中，V代表矢量，指出该路由器可以达到的目代表矢量，指出该路由器可以达到的目的地；的地；D表示去往目标表示去往目标V的距离。各个路由器根据收到的信息重新计的距离。各个路由器根据收到的信息重新计算到各目的节点的距离，对自己的路由表进行修正。算到各目的节点的距离，对自己的路由表进行修正。链路状态路由选择协议也被称为最短路径优先协议，它基于链

40、路状态链路状态路由选择协议也被称为最短路径优先协议，它基于链路状态路由算法。采用这种协议的路由器都要维护一张可以表示整个网络拓路由算法。采用这种协议的路由器都要维护一张可以表示整个网络拓扑结构的无向图扑结构的无向图G（V，E），），在图在图G中，节点中，节点V表示路由器，边表示路由器，边E表表示连接路由器的链路，因此示连接路由器的链路，因此G又可以称为又可以称为L-S（链路链路-状态）图，各路状态）图，各路由器的路由表通过由器的路由表通过L-S图计算。图计算。本章提纲本章提纲v互联网的体系结构互联网的体系结构vIP路由中的基本概念路由中的基本概念v路由转发原理路由转发原理v路由选择算法路由选择

41、算法v路由器硬件体系结构路由器硬件体系结构路由转发原理路由转发原理 处理器处理器内存内存接口接口1接口接口2接口接口n查询路由表查询路由表本章提纲本章提纲v互联网的体系结构互联网的体系结构vIP路由中的基本概念路由中的基本概念v路由转发原理路由转发原理v路由选择算法路由选择算法v路由器硬件体系结构路由器硬件体系结构距离矢量路由算法距离矢量路由算法（1）各路由器对自己的路由表进行初始化，把与自己直）各路由器对自己的路由表进行初始化，把与自己直接相连网络的距离设为接相连网络的距离设为0（在某些具体实现中也设为（在某些具体实现中也设为1，这只，这只是一个初始值设定的问题），然后周期性地向外广播其路由

42、是一个初始值设定的问题），然后周期性地向外广播其路由表的内容。表的内容。（2）路由器）路由器Ri收到相邻路由器收到相邻路由器Rj的距离矢量信息后，对的距离矢量信息后，对自己的路由表进行修正。自己的路由表进行修正。若若Rj的距离矢量信息中所包含的目的节点的距离矢量信息中所包含的目的节点va在在Ri的路由的路由表中没有，则在表中没有，则在Ri的路由表中增加一个目的节点为的路由表中增加一个目的节点为va的条目，的条目，令令dia=dja+1，并把到节点并把到节点va的下一跳路由器设为的下一跳路由器设为Rj。若到若到Rj目的节点目的节点vb的路由比的路由比Ri到目的节点到目的节点vb的路由短，的路由短

43、，则令则令dib=djb+1，并把到节点，并把到节点vb的下一跳路由器设为的下一跳路由器设为Rj。Ri到目的节点到目的节点vc最短路径上的下一跳是最短路径上的下一跳是Rj。如果。如果Rj的路由表中不再包含到的的路由表中不再包含到的vc路由，则在路由，则在Ri中也应该中也应该把去往把去往vc的路由删掉；如果的路由删掉；如果Rj到到vc的距离发生了变化，的距离发生了变化，则则Ri修改路由表中到修改路由表中到vc的距离，令的距离，令dic=djc+1。v距离矢量路由算法在理论上是可以正常工作距离矢量路由算法在理论上是可以正常工作的，但在实际中存在着一个严重的缺陷：尽的，但在实际中存在着一个严重的缺陷

44、：尽管它可以收敛到正确的路由，但它对好消息管它可以收敛到正确的路由，但它对好消息传播的快，而对坏消息则传播的慢。传播的快，而对坏消息则传播的慢。v总的来说，距离矢量路由选择协议的优点是总的来说，距离矢量路由选择协议的优点是易于实现，但难以适应网络拓扑的剧烈变动易于实现，但难以适应网络拓扑的剧烈变动或者大型的网络环境。或者大型的网络环境。链路状态路由算法链路状态路由算法v链路状态路由算法的基本步骤如下：链路状态路由算法的基本步骤如下：（1）每一个路由器（节点）启动后，首先执行对相邻）每一个路由器（节点）启动后，首先执行对相邻节点的发现工作，并获取它们的地址。节点的发现工作，并获取它们的地址。（2

45、）各路由器主动测试到每一个相邻路由器的链路时）各路由器主动测试到每一个相邻路由器的链路时延或成本，并根据测试结果设置相关链路的状态。延或成本，并根据测试结果设置相关链路的状态。（3）各路由器构造自己的）各路由器构造自己的L-S（Link-State，链路状态）信息链路状态）信息包，包，L-S信息的内容包括本路由器的标号、本路由器的邻居路信息的内容包括本路由器的标号、本路由器的邻居路由器列表、本路由器到各邻居路由器的链路状态（时延或成本）由器列表、本路由器到各邻居路由器的链路状态（时延或成本）、该、该L-S信息包的序号和生存时间等。信息包的序号和生存时间等。（4）各路由器向所有参与链路状态交互的

46、路由器广播其）各路由器向所有参与链路状态交互的路由器广播其L-S信信息，可以是周期性地发送，也可在链路状态发生变化时发送。息，可以是周期性地发送，也可在链路状态发生变化时发送。（5）每个路由器在收到所有的）每个路由器在收到所有的L-S信息后，可以构造或更新信息后，可以构造或更新表示整个网络拓扑结构的图表示整个网络拓扑结构的图G（V，E），），顶点顶点V表示路由器，表示路由器，边边E表示连接路由器的链路；这时路由器就可以用表示连接路由器的链路；这时路由器就可以用Dijkstra算法算法从图从图G中计算出到所有目的路由器的最短路径，也就是构造以中计算出到所有目的路由器的最短路径，也就是构造以自己为

47、根节点的自己为根节点的SPF树。树。Dijkstra算法简介算法简介设目的节点（就构造设目的节点（就构造SPF树而言，是根节点）为树而言，是根节点）为k，任一，任一条链路条链路（i，j）的长度为的长度为dij，每个节点到，每个节点到k的最短路径长度估的最短路径长度估计为计为Dik；定义所有节点的集合为；定义所有节点的集合为A，定义集合，定义集合PA，并设定，并设定集合的初始值为集合的初始值为P=k。在算法迭代的过程中，如果在算法迭代的过程中，如果Dik已经变成一个确定值，则已经变成一个确定值，则将将i标记为固定点，并将其加入集合标记为固定点，并将其加入集合P。在算法的每一步迭代。在算法的每一步

48、迭代中，在中，在P以外的节点中，选择与目的节点以外的节点中，选择与目的节点k最近的节点加入到最近的节点加入到P中，算法的具体步骤如下：中，算法的具体步骤如下：Dijkstra算法简介算法简介（1）P=k,Dkk=0，Djk=djk（若（若j和和k不相邻，不相邻，）（2）求解使）求解使成立的成立的i，即寻找下一个和，即寻找下一个和目的节点最近的节点；令目的节点最近的节点；令，若，若P=A，算法结束。，算法结束。（3）对所有）对所有，置，置，返回步骤，返回步骤（2）本章提纲本章提纲v互联网的体系结构互联网的体系结构vIP路由中的基本概念路由中的基本概念v路由转发原理路由转发原理v路由选择算法路由选

49、择算法v路由器硬件体系结构路由器硬件体系结构v集中式单（多）集中式单（多）CPU+总线结构总线结构缺陷缺陷CPU要负责整体系统的控制管理、路由计算和数要负责整体系统的控制管理、路由计算和数据转发等各项功能，存在计算瓶颈。据转发等各项功能，存在计算瓶颈。所有接口卡的数据都要争用总线，存在数据交换所有接口卡的数据都要争用总线，存在数据交换瓶颈瓶颈。v分布式多分布式多CPU+总线结构总线结构特点特点路由计算和转发分离：主控路由计算和转发分离：主控CPU负责整个系统的负责整个系统的控制管理和路由计算（即运行路由协议，维护和控制管理和路由计算（即运行路由协议，维护和更新路由表）；线卡上的更新路由表）；线

50、卡上的CPU负责查询路由表，负责查询路由表，对数据进行转发。对数据进行转发。部分地克服了总线瓶颈，即如果数据的接收和发部分地克服了总线瓶颈，即如果数据的接收和发送都在一个线卡上，就不用争用总线；若数据的送都在一个线卡上，就不用争用总线；若数据的接收和发送涉及不同的线卡，还是会出现总线争接收和发送涉及不同的线卡，还是会出现总线争用问题。用问题。v分布式多分布式多CPU+Crossbar结构结构特点特点路由计算和转发分离。路由计算和转发分离。采用采用Crossbar的交换结构（的交换结构（SwitchFabric），），每个每个输入端口和输出端口之间都有一个交叉开关，只输入端口和输出端口之间都有一