（通信与信息系统专业论文）区域编码标记交换网络的性能仿真分析.pdf

摘要 摘要 下一代因特网将成为未来疑础信息网络。它不仅具有原因特刚的灵活性、t j 扩 展性等优点，还将向宽带化、保证q o s 、支持组播和多媒体等方向发展。f n j 现订 的用于支持下一代因特网的协议，如i p v 6 两jm p l s j | 。岜们自身的缺陷都难以 满足一1 - 一代因特网的需要。为了弥补i p v 6 和m p l s 的缺陷本文引入并研究种 新的标记交换体制区域编码标记交换( r e g i o n a lc o d el a b e ls w i t c h i r i 譬r c l s ) 。 本文首先研究当前因特网的拓扑结构在此基础上提出一种因特网的层次性区 域划分方案，并介绍在这种层次性的骨干网络中进行路由查找的简单方法。其次， 本文还对最近提出的各种快速口查找算法进行分析，并对基于这些算法的l p 路由 器和基于标记交换的r c l s 路由器在操作复杂度、内存需求、路由表更新复杂度 以及可扩展性方面的性能进行比较。分析结果表明r c l s 路由器的查找和更新更 为简单，所需存储器容量更小且具有更强的可扩展性。在对单个路由器分析的基 础上，利用o p n e t 建立起一个网络仿真模型，通过仿真比较r c l s 网络和1 p 网 络的性能。仿真表明，r c l s 网络与i p 网络相比，具有更小的端到端时延、时延 抖动以及更高的吞吐量。最后，本文以v p n 为例，通过r c l sv p n 的具体实现方 案表明r c l s 网络对于网络的具体应用的支持。 关键字：下一代因特网区域编码标记交换路山查找虚拟专用网 垒! ! ! ! ! !一 a b s t r a c t t h en e x tg e n e r a t i o ni n t e m e t ( n g i ) i sb e c o m i n gt h ei n f o r m a t i o ni n f r a s t r u c t u r e n e t w o r ko ft h ef u t u r e i n h e r i t e dt h ec h a r a c t e r i s t i c so ff l e x i b i l i t ya n ds c a l a b i l i t yo ft h e c u r r e n ti n t e r n e t t h en g lw i l la l s oe v o l v et oi n c l u d et h ef e a t u r e so fb r o a d b a n d ，0 0 s p r o v i s i o n ，a n d m u l t i c a s ta n dm u l t i m e d i a a p p l i c a t i o ns u p p o r t b u t t h e p r o t o c o l s d e v e l o p e d t o s u p p o r tt h en g ls u c ha s i p v 6a n dm p l s ，f o rt h e i ro w nd e f i c i e n c i e s ， c a n n o ts a t i s f yt h en e e do ft h en g l s u c c e s s f u l l y t om a k e su pt h ed e f i c i e n c i e so f 1 p v 6 a n dm p l s ，an e wl a b e ls w i t c h i n ga r c h i t e c t u r en a m e dr e g i o n a lc o d el a b e ls w i t c h i n g ( r c l s ) i si n t r o d u c e da n di n v e s t i g a t e di nt h i st h e s i s a f t e rt h ei n t r o d u c t i o no fr c l s ，t h e t o p o l o g yo f t h ei n t e m e ti sf i r s t l ys t u d i e di nt h i s t h e s i s ，b a s e do nw h i c h ，ah i e r a r c h i c a la r e ad i v i s i o ns c h e m eo fi n t e m e ti sp r o p o s e da n da s i m p l er o u t i n gl o o k u pa l g o r i t h m i nt h i sh i e r a r c h i c a lb a c k b o n en e t w o r ki s p r e s e n t e d s e c o n d l y , a l lk i n d so fr e c e n t l yp r o p o s e dh i g hs p e e di pr o u t i n gl o o k u pa l g o r i t h m a r e a n a l y z e d ，a n dt h ep e r f o r m a n c eo fi p r o u t e r sa n dr c l sr o u t e r si s c o m p a r e di n t h e a s p e c t so fc o m p l e x i t yo fl o o k i n gu po p e r a t i o n ，c o m p l e x i t yo fu p d a t i n g ，d e m a n do f m e m o r y , s c a l a b i l i t ya n ds oo n - t h ec o m p a r i s o ns h o w s t h a tt h eo p e r a t i o no fl o o k u pa n d u p d a t ei ss i m p l e ra n dt h ed e m a n do fm e m o r y i ss m a l l e ri nr c l sr o u t e r st h a nt h o s ei n i pr o u t e r s ，a n dr c l sr o u t e r sa r em o r es c a l a b l et h a ni pr o u t e r s o nt h eb a s i so ft h e a n a l y s i so fs i n g l er o u t i n gn o d e ，an e t w o r ks i m u l a t i o nm o d e li sc r e a t e du s i n go p n e t ， a n dac o m p a r i s o ni sa l s om a d eb e t w e e nt h ep e r f o r m a n c eo fi pn e t w o r ka n dr c l s n e t w o r k t h r o u g hs i m u l a t i o n s t h es i m u l a t i o nr e s u l t ss h o w t h a tr c l sn e t w o r kh a sl o w e r e n d t o e n dd e l a y , d e l a yj i t t e ra n dh i g h e rt h r o u g h p u tt h a ni pn e t w o r k f i n a l l y , av p n r e a l i z a t i o ns c h e m ei nr c l sn e t w o r ki sd e s i g n e dt os h o wt h es u p p o r to fr c l sn e t w o r k t os o m es p e c i f i e da p p l i c a t i o n s k e y w o r d s ：n e x tg e n e r a t i o n n e t w o r k n g l r e g i o n a l c o d el a b e l s w i t c h i n g r c l s r o u t i n gl o o k u p v i r t u a lp r i v a t en e t w o r k v p n 创新性声明 本人声明所呈交的论文是我个人在导师的指导下进行的研究工作及所取得的 研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文 中不包含其它人已经发表或撰写过的研究成果：也不包含为获得西安f 乜子科技大 学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志所做的任 何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： i ! 当! 盘! 诌同期：1 21 1 垒! ! ：生 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印、或其它复制手段保存论文。( 保密的论 文在解密后遵守此规定) 本学位论文属于保密，在一年解密后适用本授权书。 本人签名：丝逃 导师签名 日期：型! 生! ! ：生 第1 章绪论 第1 章绪论 随着因特网应用的飞速发展和网络用户的指数性增长，现有的因特网为用，1 所提供的服务，已越来越难以满足用户对业务的要求。因而，不仅只有原因特刚 的灵活性、可扩展性等优点，还将向宽带化、保证q o s 、支持组播和多媒体等方 向发展的下一代因特网( n e x tg e n e r a l i o ni n t e r n e i n g l ) 必将成为未来的挞础信息 网络。 而作为现有因特网基础的i p v 4 ，由于自身所存在的私t 种缺点无法为n g i 提供 很好的支持，因而如何融合电信网和数据网的优点，通过对现有网络技术进行改 良，设计一种适用于下一代因特网应用的网络体系结构，成为所有网络研究工作 者共同追求的目标。 1 1i p v 4 存在的问题 现有的因特网是基于t c p i p 协议。而随着因特网的迅猛发展和用户需求的多 样化，口协议的当前版本i p v 4 已经无法适应因特网发展的要求。这主要表现在以 下的几个方面： 1 地址空间不足 因特网面临一个非常迫切的问题是，碑v 4 地址已经接近枯竭。根据互联网结构 委员会( i a b ) 的统计【1 l ，截止到2 0 0 1 年9 月，因特网用户所占用的口地址已达 到整个碑地址空问的2 6 ，虽然因特网采用了n a t 、c i d r 等技术以减缓i p v 4 地 址耗尽的速度，但是i p 地址的占用仍以每年7 的速度递增。因而扩展网络可用的 地址空间已经成为新的网络体制所需要首先考虑的问题。 2 路由表规模过大 随着因特网的迅速发展，接入因特网的各种用户网络越来越多，导致骨干路由 器的路由表规模不断增大。特别是采用c i d r 技术后，虽然增加了可分配的i p v 4 地址，却也导致骨干路由器的路出表规模进一步增大。当前某些因特网骨干路山器 的路由表中包含的表项的数目已经超过1 0 万项，且仍保持一种强力的增长势头， 如图1 1 。如此巨大的路由表，不仅占据了大量的存储空问，而且导致路由表存取 速度降低，影响分组的路由转发性能。同时，大规模的路由表还导致路由更新所需 传输的数据增多，从而增加了路由协议的链路开销。 3 分组转发速度慢 传统的i p 分组路由器采用存储、查找、转发的方式，随着网络设备处理能力的 提升，以及快速分组交换技术的提出，口分组的转发速度有了大幅度的提升。但是， 由于i p v 4 地址分配方式的原因，其路由查找方式仍然采用最长前缀匹配 ( 1 0 n g e s t - p r e f i x - m a t c h ) 。最长前缀匹配查找具有查找速度慢、内存访问次数多的缺 区域编码标记交换网络的性能仿真分析 点当路由表的规模很大时，这些缺点尤其明显。 4 路由器处理复杂 i p v 4 协议体系是在2 0 多年阿设计的。随着技术的发展，当前网络环境与那个 叫候网络环境相比发生了巨大的变化，无论是路由器的处理能力、还是链路带宽与 链路质量都有了很大的提升。原来需要在i p 层提供的功能( 如分组头校验) ，完全 可以依赖低层来保证，因而新的协议体系可以简化对分组的处理。 5 缺乏q o s 保障机制 现在的因特网用户( 特别是商业用户) 要求网络必须为用户业务提供某种程 度的q o s 保障，而i p v 4 协议体系对这方面的考虑是不充分的。尽管当前许多协议 ( 如r s v p ) 和算法被提出，希望能在i p v 4 的协议体系基础上更好的支持q o s ， 但是在实践中都没有取得良好的效果。 i 2 i p v 4 的两种替代方案 i p v 4 本身固有的缺陷，迫使人们寻求新的体制来对下一代因特网进行支持。 现有的i p v 4 的替代方案主要有i p v 6 和m p l s 。 1 2 1l p v 6 l p v 6 是i p v 4 的一个更新版本。i p v 6 将i p 地址从3 2 位扩展到了1 2 8 位，从而 为因特网用户提供了一个“无限大”的地址空间。i p v 6 简化了原i p v 4 分组头的格 式，使用了一种定长的分组头格式，以方便分组的处理。i p v 6 通过扩展头的形式 来实现分组的分段功能和原口v 4 中的选项功能，并在头中添加了一个“f l o w l a b e l ” 域，以提供对q o s 的支持。 然而由于i p v 6 相对于i p v 4 是一种革命性的变化，它的引入对原有网络的改动 太大：另一方面，i p v 6 网络中的路由器对于分组的路由查找仍是基于最长前缀匹 配，巨大的工p 地址，反而增加了路由器对分组进行查找的复杂度，这严重地限制 了路由器的处理能力和吞吐量，不利于网络的扩展。因而，虽然1 p v 6 早在1 9 9 5 年底就提交协议规范并获得i e t f 批准，但直到现在l p v 6 却一直没有获得大规模 的商业应用。 1 2 2m p l s 2 0 世纪9 0 年代中沏，a t m 交换机引入到了i n t e r n e t 的骨干网中代替了传统的 多叻、议路l j j 器丽成为网络结点的核心部分。为了实现r p 与a t m 技术的结台，各 大公司和组织纷纷提出了各自的i po v e ra t m 方案。如东芝公司的c s r ( c e l l s w i t c h i n gr o u t e r ) ，i p s i l o n 公司的i ps w i t c h i n g ，c i s c o 公司的t a gs w i t c h i n g ，n o r t e l 公司的v n s 及a t mf o r u m 提出的m p o a 等。而i e t f 综合这几大厂家和组织的 建议，制定了多协议标记交换( m u l t i p r o t o c o ll a b e ls w i t c h i n g m p l s ) 。 第1 章绪论 m p l s 吸收了面向连接的优点，首先将业务流按其特性分成类( f e c ) ，并j j 一个长度固定的称作标记的数来标识，以信令协议的方式通知后续结点，建立专 门通道，使后续的结点按照协议分配的标识交换分组，而不必对此分组珥进行i p 层的路由选择。 m p l s 中业务流分组所使用的标记是由标记分发协议( l a b e ld i s t r i b u t i o n p r o t o c o i l d p ) 完成的。标记分发协议( l d p ) 是将网络层信息映射到数据链路层， 从而建立标记交换路径( l s p ) 所使用的一系列过程和消息。其主要功能就是将# j ； 记的使用情况在唰络中相应结点问传播，并确定该标记所对应的服务方式。l d p 将每个转发等价类( f e c ) 和一条它所创建的标记交换路径( l s p ) 对应起来。进 入l s p 的分组将按照预先的约定( 由标记分发协议l d p 实现) 被转发。 m p l s 引入了第二层交换，简化了转发操作，因而能够提高分组的转发速率。 但是，m p l s 仍然需要标记分配协议为业务流建立虚通路连接，而建立和维护大量 的虚通路连接需要占用大量的网络资源，这加重了骨干网交换设备和接入设备的 工作量和实现复杂度，使其成为骨干网的瓶颈。同时，它还要求业务接入点支持 信令，并要求用户终端提供用户业务流的各种q o s 参数，对终端和业务接入点的 要求也相应提高。 1 3 区域编码标记交换体制 针对i p v 6 和m p l s 各自的缺点，我们提出了一种新的基于区域编码的标i 己交 换( r e g i o n a lc o d el a b e ls w i t c h i n g r c l s ) 方案。 1 3 1 r c l s 方案的思想 该方案将因特网进行区域划分，并借鉴电信网的地址编码方式，为每一个区域 分配一个唯一的固定长度的编码。区域间以一个骨干标记交换网进行互连。该标 记交换网主要由边缘标记交换机( 包括输入标记交换机、输出标已交换机) 和核 心标记交换机组成，如图1 1 所示。 当分组在区域的内部传输时，维持原有的i p v 4 协议不变。当分组要进行跨区 传输时，由区域的边缘标记交换机( 即图1 ，l 中的接入标记路t 妇l l 交换机) 对分 组打上一个标记，标记中包含源和1 7 1 的区的区号。在骨干网上，核心交换机可仪 根据分组的标记来对其进行转发。当分组离开骨干网而到达目的区域时，再由目 的区域的边缘标已交换机将其标记去掉，并以口分组的形式将其传到目的主机。 区域编码标记交换网络的性能仿真分析 图1 1 区域编码标记交换网络 当因特网的区域划分完成( 也就是说当所有的网络用户都被明确的划分到某一 个区域内部) 以后，r c l s 就可以进入它的第二个发展阶段。在该阶段，要求整 个因特网中的每台设备( 包括用户主机) 都要能识别r c l s 标记。r c l s 作为网络 层的一个子层，而融合到t c p i p 协议族当中。这时标识一台主机的地址已不再是 单纯的i p 地址，而变成了区域编g 马+ i p 地址。通过这种方式，可以完成对弹地址 的扩展。 1 3 2r c l s 的标记格式 r c l s 的标记位于i p 分组头与链路层帧头之间，总长度为8 个字节。该交换 标记的格式如图1 2 。该标记头中的各个域解释如下： v e r ( 4 b i t ) ：版本号 q o sc p ( 8 b i t ) ：服务质量编码点，用于标记用户所要求的服务质量的类别 f ( i b i t ) ：单播组播指示位。f 为0 表示该标记分组为单播分组，f 为l 表 示该分组为组播分组 t t l ( s b i t ) ：生存期 s o u r c ea r e ac o d e ( 2 0 b i t ) ：源区域号 d e s t i n a t i o na r e ac o d e ( 2 0 b i t ) ：目的区域号 r e v ( 3 b i t ) ：保留未用 t 。88 。l ! 哩! ! 一一i 上l _ ! ! so urc ear e acodo des t in a t io nar e acode 图1 2 r c l s 标记格式 1 - tl 第1 章绪论 1 3 3r c l s 的优点 r c l s 也是通过引入二层标记交换来实现分组的高速转发的但与m p l s 不旧 的是r c l s 是面向无连接的其在标记网络边缘处进行的区域编码的解析足通过 目的i p 地址与目的区域编码的映射或类似d n s 的域名解析过程来实现的，而不需 要象m p l s 在核心交换机之问使用标记分配协议动态地为每个业务流分配标记， “无缝地”继承1 p 分组的无连接传送方式，同时又发挥了m p l s 利用标记实现快 速分组交换的优点。 r c l s 对于因特嗣进行了区域划分不同的区域分有不同的编码，且区域之问 网络相互不熏叠。因而该体制下的网络中的每一台主机的标识可以从单纯的i p 地 址扩展为区域编码+ 口地址，从而解决了i p v 4 地址匮乏的问题。 r c l s 方案的另一个优点在于它是对现有网络的改良，它对于网络的改动较 小。变化主要集中在骨干网络，而外围的网络仍采用传统的i p v 4 的方式工作。这 一方面保护了原有的网络投资，另一方面又使得当前因特网可以比较平缓的向下 一代因特网过渡。 1 4 本文所做工作 本文结合国家“8 6 3 ”研究项目“标记交换新体制的研究”，对区域编码标已 交换的一些具体实现方案和区域编码标记交换网络相对于p 网络的性能进行了深 入的研究。主要完成了以下工作： 分析并研究了r c l $ 网络的层次化拓扑结构； 研究了i p 路由器中的各种快速路由查表算法，比较了i p 路由器和r c l s 路由器在吞吐量、实现复杂度和可扩展性等方面的性能： 通过仿真从全网的角度分析了r c l s 网络和i p 网络相比，在分组端到端 时延、分组时延抖动等方面的性能； 研究了p 网络中v p n 的各种实现方案，分析比较了l p 网络和r c l s 网 络在构造v p n 方面的差别。根据r c l s 网络的特点，设计了基于r c l s 网络的v p n 实现方案； 利用o p n e t 建立了一个r c l s 网络的仿真模型，该模型为以后的仿真工 作提供了一个平台，进一步的仿真可以以该模型为基础构造。 第2 章r c l s 网绪的层次化结构 第2 章r c l s 网络的层次化结构 2 1 斟特网的结构性矛盾 因特网由2 0 世纪6 0 年代的a r p a n e t 发展至今，历经4 0 年，已经成为一 个拥有数千万用户( 甚至更多) 的庞大i 叫络。与因特网用户规模的飞速发展相刈 应的是因特网体系结构发展的相对滞后。自1 9 8 0 年，斯坦福火学完成了t c p i p 的设计开发工作以来，基于t c p i p 的因特网体系结构便一直没有发生大的变化。 这种平面性的网络体系结构与当前因特网层次化的拓扑结构形成了对鲜明的矛 盾。 2 1 1 平面性的网络体系结构 基于t c p i p 的因特网可以看作是互连在一起的多个子网络或者l l t 做自治域 ( a u t o n o m o u ss y s t e m a s ) 的集合。所谓的自治域是指一个对内服从统一管理、 运行相同的路由协议，对外具有相同路由策略的网络。自治域在内部使用i g p ( 如 o s p f 、r i p ) 路由协议，而在域问则采用e g p ( 如b g p - - 4 ) 路由协议。 在因特网中，任何一个具有一定规模，内部具有统一管理，运行相同路由协 议，服从同一路由策略的大公司、组织以及运营商的网络都可以申请成为一个自 治域。由i a n a 为每一个自治域分配一个1 6 位的自治域号。所有的自治域无论大 小都是平等的，因而基于自治域的因特网事实上是一种平面性的体系结构。 自治域间的这种平面体系结构可以从它们间的连接特性上得到体现。由于 b g p 的u p d a t e 消息除了包含网络可达性信息之外，还包含了到达该网络所经由 的路径信息( a s p a t ha t t r i b u t e ) 。因此r a m e s h 通过收集和分析网络中间结点所收 到的u p d a t e 消息分析了网络中a s 间的连接特性【“。 r a m e s h 首先根据自治域的连接度数将因特网中的自治域分成四类，分别用 c c ，表示。它们各自的连接度数和在网络中所占的比例如表2 1 。r a m e s h 的分 析表明，从功能上讲，g 对应于洲际骨干提供商，c 对应于大的区域提供商或国 家网络，g 对应于较小的区域提供商或一个城域网络，而e 则对应于较大的校园 网络或公司的内部网。 表2 1 白治域的分类 l ：i 、li c 善l 。ci ：1 1 1 芒。 粥，：渊删：州i ：? 1 l il 。t1 - 一1 k lt l j ”。 1 l2 i 二- i ji ” 10 jl 4 jj 1jl i 一i? ”“ 8 区域编码标记交换网络的性能仿真分析 表2 2 各类自治域间的连接 i ic il jil j“ l 。ll0 0 i 二i i l u j lu l j 6 4i l i ? 、l j i jil t ；1 ) i - ) t ) 、，i ”二j 6 l j i l i j0 3 4l ( j1 6 4 l 1l l i i ，s 显然，从网络拓扑角度讲，c ，c 。分别代表网络的四个层次，然而它们之间 的连接却缺乏明显的层次性。表2 2 列出了不同类别的自治域间的链路占总链路 数目的百分比。从表2 2 可以看出，绝大多数的c d 中的自治域是直接与g 和e 的 自治域相连的也就是说自治域间跨层连接的现象非常普遍，一个自治域并不是 通过一个上层自治域连入网络的，自治域问是一种平面连接。 2 1 2 层次性的网络拓扑结构 网络的拓扑主要有三种类型：集中式拓扑( c e n t r a l i z e dt o p o l o g y ) 、分散式拓 扑( d e c e n t r a l i z e dt o p o l o g y ) 和分布式拓扑( d i s t r i b u t e dt o p o l o g y ) 。如图2 1 ，集 中式网络拓扑具有一个中心结点，其他的所有结点都直接连接到该中心结点：分 散式拓扑是一种树性结构，这种拓扑存在一个根结点，根结点连接到几个分支结 点，而所有的子结点都是通过分支结点连入网络；分布式网络拓扑则没有集中式 拓扑和分散式拓扑那样的中心结点，所有结点以平等的身份互联。 集中式拓扑的网络建设最为简单，所需的连接数也最少。假设网络中的结点 数为n ，则集中式拓扑所需的连接数为n 一1 ，而分布式拓扑所需要的连接数为 nxd 2 ，其中d 是结点的平均度数。但从健壮性考虑，分布式拓扑最抗攻击， 集中式拓扑则最脆弱，一旦集中式网络的中心结点收到攻击，整个网络便会陷入 瘫痪。而分散式拓扑介于二者之间。 恻2 1 网络拓扑类型 第2 章r c l s 网络的层次化结构 9 而当前的因特网是一种结合 了分散式拓扑和分布式拓扑特点 的一种类树结构，如图2 2 。 因特网的拓扑大致可以分为 三至四个层次。每个层次的结点 之间采用一种分布式的网络拓扑 连接而每个结点又向下连入下 一级的骨干。如果我们将同一层 次的骨干网络看作是一个结点， 则因特网的拓扑便形成一种逻辑 上的树形结构。 以我国的教育网( c e r n e t ) 为例，如图2 。4 。北京作为 c e r n e t 的国际接口，向外分别 连至香港、日本、美国等地，它 与国外的其它结点一起构成了最 高层的国际骨干网。而国内北京、 上海、西安等八个城市的结点组 成了c e r n e t 的国家骨干网络， 该国家骨干在北京接入到国际骨 图2 2 因特网拓扑示意图 图2 3 中国教育网( c e r n e t ) 骨干拓扑 干。北京、上海、西安等八个城市又向外辐射形成以各自为核心的一个区域骨干， 由区域骨干再按入到各个学校的校园网。由此可见，因特网的拓扑具有很强的层 次性。 2 1 , 3 二者之间的矛盾 自治域主要是从管理的角度考虑而划分的一种区域。i a n a 为服从统一管理的 一组网络提供一个自治域号，而不 理会该网络的拓扑结构。如：= c e r n e t 的网络虽然包含两个明= = = 显的拓扑层次，但对外可能只显示： 为一个自治域。因而因特网实际上 ；：= ： 是在层次性拓扑结构的基础上维3 ： 持着一个平面性的体系结构。：= ： 在这个平面性的体系结构中。：= ： 因特网p 地址的分配也是与网络 _ n t h 一t 。 。， 图2 4 路由表的增长 区域编码标记交换网络的性能仿真分析 的拓扑无关的。i a n a 应各个地区互联网管理机构( 如a p n i c ，r i p e 等) 的请求 分配i p 地址块。由于一个地区互联网管理机构( 如a p n i c ) 每次只能申请到有 限的一段i p 地址，因此一个地区所占用的i p 地址空间是不连续的，也就是说i p 地址并未与因特网的拓扑相绑定，骨干网络的路由器无法凭借分组的部分i p 地 址( 如i p 地址的前8 位) 判断目的子网在因特网中的位置。 网络的这种体系结构使得骨干网络的每一个路由结点都必须维护一张全因特 网的路由表，而不能利用网络拓扑的层次性进行路由的汇聚和路由信息的屏蔽。 这便导致骨干路由器中的路由表规模随着网络的扩张而呈现一种近似指数的增长 f 3 】，如图2 4 。并且为了传播这种路山信息，而在网络中增加的路由开销也越来越 大。 而r c l s 则从网络拓扑具有层次性这一实际情况出发，根据网络当前的拓扑 情况，通过仔细的规划，将网络化分成三个层次。这种层次性的划分，简化了网 络的操作。 2 2 r c l s 网络的层次性划分 2 2 1r c l s 网络的三个层次 基于因特网拓扑当前的特点，r c l s 将其骨干划分成了三个层次，分别称为 全球骨干( g l o b a lb a c k b o n e ) ，地区骨干( r e g i o n a lb a c k b o n e ) 和区域骨干( a r e a b a c k b o n e ) ，如图2 5 。 全球骨干网山互联在一起的全球各个国家负责国际转发的路由结点组 成，如北京、纽约、伦敦、东京等地的国际路由结点： 地区骨干网由一个地区( 一个或多个国家) 的国家级骨干结点组成，如 我围园家骨干由位于北京、上海、广州、沈阳、南京、武汉、成都、西 安等8 个城市的核心结点组成：在这些结点之阳j 构成非完全的网状结构， 它们通过一个或多个出口结点( 北京、上海、广州) 接入到全球骨干网： 区域骨干网则由更低层的r c l s 标记路由器组成，这些路由器由一个或多 个出口结点连接到地区骨干。例如在我国的国家骨干网络中，全国3 1 个 省f 1 丁 以上述8 个核心结点为中心划分为8 个大区网络，这其中的每个 大区网络便是+ 个区域骨干。 所_ f i ( 的区域通过边界路由器接入到区域骨干网。区域f u j 的通信必须要经山区 域骨f 二嘲，剖咩区域骨干网川的通信必须要经过地区骨干网，而地区骨干网日j 的 燧信要经过国际骨干网。我们把一个地区骨干网及其下接的所有网络称为一个大 区，而把一个区域骨干网及其下接的所有网络称为一个次大区。 第2 章r c l s 网络的层次化结构 幽2 5r c l s 网络的层次划分 2 2 2 区域划分方案 在标记交换网络中，路由器通过标记头中携带的2 0 比特长的目的区域号来识 别分组要到达的目的区域，并根据该区域号来进行转发。出于r c l s 将骨干网络 分为三层，与之相应的这2 0 位的区域编码也应分为三层。前i 位用于表示目的区 域位于哪个大区，中间j 位用于表示目的区域位于该大区下的哪个次大区，而后k 位用于表示目的地址位于该次大区下的具体哪个区域。 j 1 j k 【。-一一，。，。一 + 一 2 0bit + 幽2 6 区域编码的层次划分 对于大区的划分，主要从区域划分的公平性、有效性和合理性方面考虑。由 于区域号码是一种宝贵的资源，因此大区的规划必须合理高效，尽量避免区域号 码的浪费。考虑到全球政治经济发展的不平衡，以及人口分布的不均，建议将全 球划分成6 3 个大区( 即设定i = 6 ) ，各个大区的覆盖范围及区号的分配出i a b 的 各个下属机构( 如r i p e ，a p n i c ) 负责规划。而前6 位都为0 的区域号( 共1 6 3 8 4 个) 用于控制消息的专用标签。 对于次大区和区域的划分，则主要从网络拓扑的角度出发。每个大区根掘其 拓扑的不同，可以自行规定应进一步划分的次大区数和区域数( 既可自行对区域 号码的后1 4 位进行解释) 。由于在一个大区，往往有多家运营商为该大区下的用 户服务，而这些运营商之问可能仅在几个大的城市存在互通的接口，因此在划分 次大区和区域的时候还要考虑运营商的因素。 假设整个中国的网络被划分为一个大区。以中国为例，我们给出次大区和区 域的一种划分方案。当前中国国家范围的骨干运营商主要有c h i n a n e t 、 c e r n e t 等8 家，而每一个骨干网又将全国大致划分成8 个子区，因此我们设定 区域编码标记交换网络的性能仿真分析 j = 8 。这样中国大区下可支持的次大区数目便最多为2 5 6 。我们将各大供应商下 属的每个子区划分为一个次大区，这样实际分配的次大区号为6 4 个，约为最大可 分配数目的四分之，为将来可能出现新的服务提供商预备了号码空间。而每个 次大区又可进一步分为6 4 个区域。因此，按照行政区划，大概每个地级市范围的 网络便如分为一个区域，独享一个特定的区域号；而几个县级市可合并，构成一 个区域，共享一个区域号。 2 2 3 区域前缀 类似于口网络中的网络前缀，我们在r c l s 网络中定义区域前缀的概念。一 个区域前缀p 由一个区域号n 和一个掩码m 组成。如果分组的区域号a ，满足 a m = n 。则我们说a 与p 相匹配，否则称a 与p 不匹配。例如北京作为中国 区域骨干的一个骨干结点，假如它的前缀是0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 ，其中“6 ”， 表示前缀长度为6 ，则区域号0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 与该前缀匹配，而 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 与该前缀不匹配。骨干网络中的每个路由结点都具有两 个前缀，每个前缀对应于一级路由表。与网络的层次性拓扑相对应，分组在结点 中进行一种层次化的路由查找。 2 3 层次化的路由查找 为了正确的转发分组，r c l s 网络中的每个路由结点必须维持一张路由转发 表。该表用于指示到达某个目的区域去的分组应该从哪个端口进行转发。如果每 一个区域号在转发表中都对应一个表项，如表2 3 ，则这样的一个转发表所包含的 表项数目为2 ”= 1 m 。 表2 3r c l s 的一级转发表 目的区域编码转发端口 0 0 0 0 0 0 ，0 0 0 0 0 0 0 0 ，0 0 0 0 0 12 0 0 0 0 0 0 ，0 0 0 0 0 0 0 0 ，0 0 0 0 0 2l 1 1 1 1 1 l ，1 1 1 1 1 1 1 l ，1 1 1 1 1 ln 由于r c l s 对网络进行了层次性的划分， r c l s 的路由结点可以通过两级查找的方式 来减小转发表的规模。以r c l s 地区骨干网 络的一个结点为例，如图2 ，7 中的灰色结点 a 。假设该结点所处的太区的区域前缀为 0 0 0 0 0 1 0 0 0 0 0 0 0 ，0 0 0 0 0 0 6 ，而结点a 下接的 次大区的区域前缀为0 0 0 0 0 1 ，0 0 0 0 0 0 1 图2 7r c l s 网络的层次化路由 第2 章r c l s 网络的层狄化结构 0 0 0 0 0 0 1 4 。则该结点维持如表2 4 所示的一张两级的转发表。其中一级表中的“目 的区域编码”项填写的是区域编码的中问8 位，而二级表中的“目的区域编码” 项填写的是区域编码的后6 位。 在r c l s 网络中，当结点a 收到一个分组后，结点a 先将分组的目的区域号 与该结点的一级区域前缀匹配如果匹配失败，晚明浚分组的目的区域跟结点a 处于不同的一级大区，这时结点将分组转发给缺省路由器b ，山结点b 送入命球 骨干进行路由。如果分组的目的区域号与结点a 的一级区域前缀匹配成功，则通 过查找结点a 的一级转发表，来获知分组的转发端口。如果通过查找一级表发现 分组的目的区域号与结点a 的二级区域前缀匹配，则通过查找结点a 的二级路由 表来最终确定分组的转发端口。 表2 4r c l s 的两级转发表 级别前缀目的区域编码转发端口 0 0 0 0 0 0 0 01 10 0 0 0 0 1 + 0 0 0 0 0 0 0 1本区域 1 1 1 1 1 1 1 ln _o o o 0 0 0o 2 0 0 0 0 0 1 ，0 0 0 0 0 0 0 1 ，+ 0 0 0 0 0 12 1 1 1 l l lm 采用这种方法，可以大大减少路由表的存储空问。对于结点a ，它所需维护 的表项总数为2 ，+ 2 2 ”= 1 6 k 。如果每个表项占据一个字节，则所需的存储空 削仅为1 6 k b ，这么小的存储空间完全可以放在高速的片内缓存( 如c a c h e ) 甩， 从而加快了处理速度。 在上述的查找过程中，结点对一个分组最多要经过两次查表来判断分组的转 发端口，而在实际的实现过程 中，可以通过利用硬件判决器 使分组的查表次数降为一次。 结点对于一个到达的分组，先 通过判决器来判断分组的目的 区域号是否与结点的两级区域 前缀匹配，如果只与高级区域 前缀匹配，则查找一级表，如 果与两级区域前缀都匹配则查 图2 8硬件实现的一次性查表 缺省j _ 山 区域编码标记交换网络的性能仿真分析 找二：级表，否则若匹配失败将分组发送给缺省路由，如图2 8 。 图中的判决器可以用一个简单的逻辑电路来实现。由于一次查表需要一次存 储器的读取，而从处理时延的角度看，硬件实现的判决器的速度远快于存储器的 读取速度，所以采用该方法，可以使所需的存储器读取次数降为l ，从而大大加 快分组的处理速度。 第3 章r c l s 与i p 的性能比较 第3 章r c l s 与i p 的性能比较 随着i n t e m e t 的迅猛发展，骨二t 二网上路由器的接口速率越来越高。在使川 o c 一1 9 2 的链路的骨干网上，链路速率已达到1 0 g b p s ，这一速率要求核心路由器l p 端口具有高于2 0 m p p s i4 】的分组交换能力。l 虬此如何实规i n t e r n e t 中分纽的快速转发 已成为个i ) f 究的热点。 为了实现在高速链路上的线速转发，当d u 主要有两种解决思路：采用标记交 换技术或采用高性能的d 路由器。前者的思想是给分组或信元女n 上短而定长的标 记，以标记交换来代替传统路由器对于i p 分组头部的复杂处理，从而可以实现分 组的快速转发。而随着近年来硬件技术的发展和路由器处理速度的提高，一些研 究人员提出利用高速i p 路由器同样可以实现分组的线速转发。然而山于i p 路由器 对分组的查找处理始终是基于最大前缀匹配，因此其性能的提升受到了很大的限 制。 本章分析了现有的i p 高速路由器技术，并利用仿真比较了采用标记交换的 r c l s 网络和使用高速路由器的口网络的性能。 3 1i p 高速路由器 3 1 1 路由器结构的发展 路由器的发展经历了多种结构类型。早期的路由器由一个处理器( c p u ) 和多 个与共享总线连接的线卡( l i f i ec a r d ) 组成，如图3 1 。处理器实现路由协议、创 建路由表并完成路出查找。所有从线卡进入系统的数据包通过共享总线送到处理 器，由处理器处理包头，然后做出转发的决定。随后数据包再次通过共享总线送 至目的线卡的接口，然后传输到网络的下一结点或目的网络。这种路由器结构的 局限是处理器必须处理每个数据包，且每个数据包必须通过总线两次，最终限制 了系统的吞吐量，即总线与处理器都构成瓶颈。 幽3 l 共享总线式跆由器结构 区域编码标记交换网络的性能仿真分析 为了克服传统路由器的瓶颈，现代高速的p 路由器使用交换结构( s w i t c h i n g f a b r i c ) 替代共享总线结构，如图3 2 。这种交换结构可以并行地转发多个不同来 源、不同目的地的i p 数据包，因而大大提高了路由器的转发性能。除此之外，高 速路由器还在每块线卡中增加了专用处理器，用于路由查找处理，而主处理器 ( r o u t i n gp r o c e s s o r ) 只负责实现路由协议和创建路由表。这样转发大部分口 数据包便可不再借助于主处理器，从而有效地将转发功能分布到每块线卡上。 线卡上添加的这部分专用处理器称为转发引擎( f o r w a r d i n ge n g i n e ) ，转发 引擎通过运算某种路由查表算法来对i p 分组进行查找处理。尽管转发引擎结构的 利用极大地提高了转发效率，但不断增加的端口速度远远超过了转发引擎处理的 能力。这种压力，迫使人们研究更为快速高效的i p 路由查表算法。 图3 2 交换结构式路由器 3 1 2i p 快速路由查表算法 近年来，研究人员提出了大量的碑路由查找算法，这些算法都基于最长地址 前缀匹配。根据不同算法所采用的思想。可大致划分基于树的算法、基于比