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