（通信与信息系统专业论文）宽带多媒体卫星星上atm交换结构路由算法研究.pdf

：一： ：= 坚尘婆三些奎兰三兰竺兰兰堡彗苎一 ：一：一= 摘要 宽带多媒体卫星通信是当前卫星通信最为重要的一个发展方向，它一方 面是社会需求的推动，另一方面又是现代卫星通信技术发展的结果。为满足 用户所需的服务质量( q o s ) ，具有星上处理和交换功能的卫星a t m 系统成 为未来卫星通信发展的重点。以此为背景，本文就当前国内外一些典型的 a t m 交换结构中的路由算法进行分析，并提出一种基于蚂蚁算法的阻塞规 避路由算法。采用此算法的星上a t m 交换结构不仅可以使交换时延大大减 小，同时也使内部阻塞大大降低。 本文首先对四种典型的多路径a t m 交换结构及路由算法进行研究，包 括：具有自路由特点的b a t c h e r - b a n y a n 网，非自路由的c l o s 网、m i n s 网和 b e n e s 网。详细分析讨论了这些交换结构的构成方式、适用的路由算法、以 及各种路由算法的优缺点。通过比较这些交换结构和路由算法，进一步选定 本课题背景下所采用的结构b e n e s 交换网络。 在选择适合星上交换结构的路由算法时，本文提出一种具有阻塞规避 机制的蚂蚁路由算法。该算法不仅可以通过蚂蚁算法寻找最短时延路径，还 具有阻塞规避机制，可以快速预测阻塞节点，选择非阻塞路径，有效地分散 流量，减缓阻塞状态。 最后，论文结合本课题的应用背景给出了所采用的路由算法分析模型， 并通过仿真分析其工作过程和性能结果。同时，进一步总结了该路由算法的 适用范围及应用前景，并就未来宽带多媒体卫星星上a t m 交换技术的创新 提出几点设想。 关键词星上a t m 交换结构：b e n e s 网络；蚂蚁算法；阻塞规避 ：一： ：= 篁尘婆三些奎兰三兰堡占兰堡彗圣： ：一：一= a b s t r a c t b r o a d b a n dm u l t i m e d i as a t e l l i t ec o m m u n i c a t i o ni sb e l i e v e dt ob eav e r y i m p o r t a n td i r e c t i o no f t h es a t e l l i t ec o m m u n i c a t i o n ，b e c a u s eo ft h ep r o m o t i o ni n t h em a r k e tr e q u i r e m e n ta n dt h e d e v e l o p m e n t o ft h e t e c h n o l o g i e s i nm o d e r n s a t e l l i t ec o m m u n i c a t i o n t h es a t e l l i t ea t mc o m m u n i c a t i o ns y s t e mw i t ho n b o a r d p r o c e s s i n ga n do n b o a r ds w i t c h i n gb e c o m e sm o r ea n dm o r ei m p o r t a n t i nt h e f u t u r e ，i no r d e rt os u p p l yt h eq u a l i t yo fs e r v i c e ( q o s ) f o ru s e r s s o m et y p i c a l a t m s w i t c h i n gf a b r i c s ( a s f ) a n d t h e i rr o u t i n ga l g o r i t h m ，w h i c ha r ew i d e l yu s e d i nn o w a d a y s ，a r ea n a l y z e d a no n - b o a r da s fb a s e do na n ta l g o r i t h mi sp r e s e n t e d i nt h ep a p e r , w h i c hc a nr e d u c en o to n l yt h eb l o c k i n gp r o b a b i l i t y , b u ta l s ot h ec e l l a v e r a g ed e l a y f i r s t l y , t h i sp a p e rm a k e s r e s e a r c h e so nf o u rt y p i c a la t m s w i t c h i n gf a b r i c s ， s u c ha sb a t c h e r - b a n y a nn e t w o r k sw i t hs e l f - r o u t i n g 。c l o sn e t w o r k sa n dm i n s n e t w o r k sa n db e n e sn e t w o r k sw i t h n o n s e l f - r o u t i n g t h e a r t i c l e p a r t i c u l a r l y a n a l y z e dt h e i rc o n f i g u r a t i o n s ，b a s i cr o u t i n ga l g o r i t h ma n dt h ec h a r a c t e r i s t i c c o n s i d e r i n g t h e b a c k g r o u n d o fs a t e l l i t ec o m m u n i c a t i o nw ec h o o s eb e n e s n e t w o r k sf o rm o d i f i c a t i o nb y c o n t r a s t i n gt h o s e a s f s s e c o n d l y ，f o rc h o o s i n ga ne f f i c i e n tr o u t i n ga l g o r i t h mi no n b o a r da s f , w i t h c o n s i d e r i n g o n b o a r d s w i t c h i n g sr e q u i r e m e n t o f d e l a y l i m i t e d a n dl o w e r b l o c k i n gp r o b a b i l i t y , a na n t b a s e dr o u t i n ga l g o r i t h mw i t hb l o c k i n ga v o i d a n c ei s p r o p o s e d s u c ha l g o r i t h mc a nn o to n l ye x p l o r eo p t i m a lc o n n e c t i o n s ，b u ta l s o d e t e c tt h eb l o c k i n gs t a t u so nt h e s w i t c h i n ge l e m e n t s ( s e s ) ，a n dt h e nq u i c k l y n o t i c et h e i n p u tp o r t st o s h i f tt h et r a f f i ct oa na l t e r n a t ec o n n e c t i o nt o a v o i d b l o c k i n g f i n a l l y ，t h er o u t i n ga l g o r i t h mm o d e lw a sp r e s e n t e di nt h i s b a c k g r o u n d ； a c c o r d i n gt ot h e s es i m u l a t i o nr e s u l t si ta l s oa n a l y z e dt h ew o r k i n gp r o c e s sa n d p e r f o r m a n c e a tt h es a m et i m ew es u m m a r i z e di t sa p p l i c a t i o na n d f o r e g r o u n d i n t h ec o n c l u s i o nw ea l s od i s c u s s e dt h ed e v e l o p m e n to f r o u t i n ga l g o r i t h mi no n b o a r da s ff o rt h e n e x te r ab r o a d b a n dm u l t i m e d i a s a t e l l i t ec o m m u n i c a t i o n n e t w o r k i i 皇垒堡三些奎兰三兰竺圭兰堡丝兰 k e y w o r d s o n b o a r da t ms w i t c h i n gf a b r i c ，b e n e sn e t w o r k s ，a n t a l g o r i t h m ， b l o c k i n ga v o i d e n c e j i i ：一： ：= 坚尘婆三些奎兰三兰竺兰兰堡彗苎一 ：一：一= 第1 章绪论 1 1 课题背景及研究的目的和意义 多媒体卫星通信，也称宽带卫星通信，指的是通过卫星进行语音、数 据、图像和视频的处理和传送。它将成为未来全球信息结构的一个主要支 柱。宽带多媒体卫星通信是当前卫星通信最为重要的一个发展方向，它一方 面是社会需求的推动，另一方面又是现代卫星通信技术发展的结果。目前 还在高空运行的同步卫星，其星上转发器装置没有信号处理和交换的功能， 称为“透明”的卫星，它已经无法满足用户所需的服务质量( q o s ) 。因 此，具有星上处理功能的卫星a t m ( a s y n c h r o n o u st r a n s f e rm o d e 异步传递 方式) 网络成为未来卫星通信发展的熏点【2 - - 4 1 。 在同步卫星上装信号处理设备，由卫星本身执行a t m 交换功能，卫星 a t m 网就可由星上a t m 交换机与地面网络控制中一g , ( n c c ) 分担控制功能。 卫星通信技术和a t m 网络技术都具有诸多特点和优势，二者相结合形成的 综合性网络卫星a t m 网具有以下几个突出的优点： ( 1 ) 由于卫星的广域覆盖性，将其加入到a t m 网络以后，可在广阔 的地理范围内提供a t m 业务： ( 2 ) 卫星通信和a t m 网络综合以后按需分配带宽的能力更强，可以 进一步提高信道的利用率，而且还可以动态分配接入容量，不受复杂地面网 络拓扑的影响，减少了中间多次分配的环节，满足了广播、多点传送和多媒 体通信的要求； ( 3 ) 在不同地点建立a t m 网时，卫星通信能提供灵活的网络互连、 网络配置和容量分配方案； ( 4 ) 利用卫星通信的广播特性和易于( 多) 点对多点的通信特性，可 以快速建立a t m 网的( 多) 点对多点的通信； ( 5 ) 可以方便的为无法预测带宽要求和业务特征的连接分配备用信 道，这样既可以保证该连接的服务质量，又能够实现资源的充分利用； ( 6 ) 网络扩展简单、方便，只要按照用户的要求，在用户处安装a t m 地面站即可； 。 ( 7 ) 卫星可以作为地面光纤a t m 网的安全备份，在地面网出现故障 ：一： ：= 坚尘婆三些奎兰三兰竺兰兰堡彗苎一 ：一：一= 时，根据要求，通过卫星信道确定通信路由，能够快速恢复网络的拥塞问 题，提高了系统的传输性能。 将a t m 方式用于卫星通信，不仅适应通信网络向b i s d n 发展的必然 趋势，而且具有满足未来应用需求的必要性。但是，我们必须看到，将卫星 与a t m 技术结合也会面对相当大的挑战。 出于a t m 技术目前在i s d n 网络中的应用基础是高速率、低误码率光 纤信道的使用，因而在卫星环境下采用a t m 技术将面临一系列特殊的问 题。相对于地面a t m 网络所使用的光纤信道，卫星的带宽是有限的，更容 易在数据传输中发生拥塞，再加上卫星通信不可避免的长传输时延口l ，便需 要对星上a t m 结构进行相应的改进和创新，以降低交换时延，减少内部阻 塞，达到降低丢包率，满足用户所需q o s 的目的。 对星上a t m 交换结构进行改进可以从两方面来考虑： ( 1 ) 使用具有容错能力的交换网络并改善基本交换单元性能： ( 2 ) 选择更加有效的路由算法。 目前在交换网络方面的研究比较成熟，但是在路由算法方面还有待创 新，这也正是本课题研究的目的和意义所在。 1 2 国内外的发展现状 本课题研究重点是卫星a t m 交换结构内部进行选路时的最佳算法，以 下为卫星a t m 交换和相关路由算法的研究现状。 1 3 卫星a t m 的研究现状 宽带卫星技术已成为当前通信的新热点之一。现代宽带卫星系统的特点 是工作在更高频段、采用a t m 技术和主要提供多媒体和因特网业务】。早 期的宽带卫星网络是利用传统卫星( 特别是g e o ) 作透明中继的卫星a t m ( s a t m ，s a t e l l i t ea t m ) 。在美国和欧洲已经开展了利用传统卫星传输a t m 业务的实验a1 9 9 6 年，n a s a 的a c t s 卫星( a d v a n c e dc o m m u n i c a t i o nt - e c h n o l o g ys a t e l l i t e ) 进行了1 5 5 5 4 m b i t s 的a t m 试验。文献 8 】介绍了试验 情况，得出的结论是卫星a t m 能提供和地面a t m 同样的传输性能。a c t s 系统目前进入了使用。相类似比较著名的海域r a c e c a t a l i s t 、w i s d o m 等计划。卫星透明中继s - a t m 系统的特点是地球站昂贵，数量少，每一地 球站的业务量大。由于每一地球站的业务较大，这类系统不需要复杂的多址 ：一： ：= 坚尘婆三些奎兰三兰竺兰兰堡彗苎一 ：一：一= 方式就可以达到很好的信道利用率。 随着星上处理概念的提出，产生了基于星上交换的s - a t m 。星上处理 ( o b p ，o n b o a r dp r o c e s s i n g ) 概念是由欧洲空间局( e u r o p e a ns p a c ea g e n c y ) 提出。o b p 概念包括星上基带交换、中继。o b p 技术是提高卫星系 统性能的有效手段，具有如下优点1 9 j ： ( i ) 地球站复杂性减少，成本降低，发射功率降低； ( 2 ) 灵活的路由功能，可以构成灵活的网状网： ( 3 ) 减少b o d ( b a n d w i d t ho nd e m a n d ) 时延； ( 4 ) 上行链路与下行链路可以分开设计，可以改善信道的b e r 性 能。 在星上处理s a t m 系统中，卫星具有星上交换功能，不再是透明中继。 s p a c e w a y 是h u g h e s 通信公司开发的提供宽带接入的卫星通信系统，它利用g e o 星座，在使用6 6 c m 的固定超小孔径终端时，提供宽带的通信( 1 6 k b i t s 6 m b i t s ) 。在卫星有效载荷中包括数字信号再生和a t m 交换【10 1 。与之相类 似的星上a t m 交换系统有v i c es p a n ( a t & t ) ，a s t r o l i n k ( l o c k h e e dm a r t i n ) 、c y b e r s t a r ( l o r a l ) 蔫【1 1 , 1 2 1 。这类系统一般是提供宽带接入、属于接入网 范畴。与透明卫星a t m 相比，这类方案的特点是有数量众多的用户终端站 和少量的关口站。用户终端站的业务量波动比较大，因此多址接入技术对系 统的性能影响很大。另外用户终端站的价格及大小影响这一方案的推广使 用。这一方案由于利用星上交换可获得灵活的全网状的点对点和点对多点结 构。尽管利用星上交换具有很多优点，但还是有很多限制条件。众所周知， 卫星是带宽有限，质量有限的系统。此外还要经受强烈的空间辐射。因此， 必须开发能耗低，不复杂的星上处理系统，同时星上尽可能只有少数功能。 卫星通信技术和a t m 网络技术都具有诸多特点和优势。a t m 与卫星相 互取长补短的组合，既能发挥卫星投资少、见效快、通信容量大等特点，又 能充分发挥a t m 网的灵活性和适应性。卫星通信与a t m 网的综合为信息 时代的人们提供了一个随时随地随意以合理的费用获取信息的良好的宽带网 络平台1 3 1 5 。 1 4 星上a t m 交换结构及路由算法方面的研究 具有星上交换能力的通信卫星就像是一台悬挂在太空中的交换机，它 可为来自不同波束的信息提供路由交换，实现任一输入波束与任一输出波束 ：一： ：= 堕尘婆三些查兰三；兰堡当兰堡彗苎： ：= ：一= 问的通信连接，使位于多个波束覆盖区域内的所有地球站能够互相通信，从 而组成可进行星上交换的卫星通信网。在这种网络结构中，卫星是唯一的网 络交换结点，地球站则是用户与网络间的接口端点。星上a t m 交换与地面 a t m 交换是不同的，它有着自身的特点和要求。星上a t m 交换的特点如 下： ( 1 ) 由于卫星链路存在着较高的误码率，所以a t m 信元格式必须考 虑差错控制编码；这将导致不同于标准a t m 信元的信元格式； ( 2 ) 卫星信道具有带宽共享( 上行) 和广播特性( 下行) ，因此，存在着 多址接入的控制问题以及相应的多址接收的实现问题： ( 3 ) 星上交换仅需完成v p 路由交换，而且交换规模通常小于地面交 换的规模； ( 4 ) 对星上交换的拥塞控制，必须要考虑卫星链路存在较大传播时延 的影响； 此外，就星上a t m 交换的要求而言，它侧重的是星载a t m 交换机的 设计及其性能，主要包括以下这么几个方面【1 6 】： ( 1 ) 星上设备尽可能简单一一硬件的复杂性较低，硬件数目尽量要 少； ( 2 ) 具备有较高的可靠性一一在发生故障的情况下，交换机应有良好 的重构配置方案，而且重构控制算法应尽可能简单易行； ( 3 ) 体积较小和功耗较低一一集成度高，并且最大功耗不应超过数十 瓦： ( 4 ) 良好的星上交换性能一交换时延小，信元丢失率低，无内部阻 塞。当然，交换机的控制和路由算法也必须尽量简单可靠； ( 5 ) 实现多播传送的功能一交换机应允许同一信元被路由到不同的 目的波束，以便实现点对多点的通信和保持卫星链路原有的广播特性。 目前，a t m 交换结构中可用于星上的多路径交换网络主要有四种典型 类型：自路由的b a t c h e r - b a n y a n 网络以及非自路由的c l o s 型、m i n s 网络、 b e n e s 网络。其中，自路由的算法原理简单容易实现，但所需交换单元数量 多，时延大。非自路由的算法有集中式路由选择算法和分布式路由选择算法 两种。前者有很好的吞吐性能，但是对无阻塞条件要求比较高，同时对集中 控制器的处理速率要求过高，不容易实现，在实际中基本上不采用。后者算 法较复杂，但更可靠。在四种交换结构里，b e n e s 网络是最简单的容错 b a n y a n 网，在实际中被普遍采用。卫星宽带系统在采用a t m 技术提供多媒 ：一： ：= 坚尘婆三些奎兰三兰竺兰兰堡彗苎一 ：一：一= 体业务时，需要考虑减少时延、降低阻塞、保证q o s 等问题，这些算法就 为此提供了很好的解决方案引。 1 5 研究内容及结构 本论文的结构安排如下： 第1 章，绪论。主要介绍了该课题的一些应用背景，宽带多媒体卫星通 信及其星上a t m 交换发展的意义和前景，国内外在该课题上的一些发展应 用情况，并指出了星上交换结构路由算法研究的必要性。 第2 章，星上a t m 交换的基本概念。针对本课题背景，介绍了星上a t m 交换的基本原理，a t m 交换单元和a t m 交换网络的分类，卫星a t m 业务分类，以及业务的性能指标要求。 第3 章，a t m 交换结构路由算法。本章对四种典型的多路径a t m 交换 网络的基本结构及其对应的路由算法进行了详细的介绍和深入的分析。 第4 章，基于蚂蚁算法的阻塞规避路由算法。这是在本课题应用背景下 的一种新的路由算法，本章对其原理进行了详细深入的介绍，并提出一种基 于门限压出共享缓冲管理方案，与之结合，使交换时延大大降低。 第5 章，星上a t m 交换结构路由算法仿真结果分析。本章采用 o p n e t 仿真软件对蚂蚁路由算法进行仿真，分析了它的实现过程，并证明 了其在星上交换中的优越性能。本章还对星上a t m 交换技术的改进提出了 一些创新和设想。 最后，对本课题的研究内容及结果做了一个全面的总结，同时对未来的 星上交换结构设计也提出了要求。 哈尔滨工业大学t 学硕上学位论文 第2 章a t m 交换的基本概念 2 1 星上a t m 交换结构简介 本课题研究的是宽带多媒体卫星星上a t m 交换结构的路由算法。星上 交换与传统的地面a t m 交换略有不同，下面分别从星上a t m 交换原理和 交换结构方面做一下简单的介绍。 2 1 1 星上a t m 交换基本原理 a t m 交换是一种面向连接的交换方式【 o9 1 。a t m 交换的基本信息单 位为信元( c e l l ) ，信元的长度固定为5 3 字节，其中信头域为5 字节，信息负 荷域为4 8 字节。信头域主要提供由虚通路标识( v p i ) 和虚信道标识( v c i ) 共 同决定的网络路由信息 2 0 , 2 1 l 。a t m 交换机由输入输出控制电路o c o c ) 和交 换结构组成，主要完成v p i v c i 转换和路由选择两项功能，一般构成如图 2 - i 所示。v p i v c i 转换主要在a t m 交换机的i c 中根据路由表完成，路由 表中存贮了待交换信元的输入端口号、输入未经转换的v p i 和v c i 值、转 换后的v p i 和v c i 值、以及所要求的输出端口号。路由表是在信令建立过 程中建立的。i c 根据路由表将输入信元的v p i ，v c i 值转换为该信元交换 输出后所要求的v p i 和v c i 值；然后，由路由表所指示的输出端口，在信 元前面附加路由标签( r o u t i n gt a g ) ；再将信元送入交换结构。路由标签的长 度为1 字节，因此在a t m 交换结构中进行路由的a t m 信元为5 4 字节大 小。交换结构根据信元的路由标签在路由控制器的控制下( 或自选路由) 将信 元送到正确的输出端口，完成路由选择功能。由于在宽带多媒体卫星通信 中，星上交换对波束进行交换且规模不大，因此只进行v p 交换，即一个 v p 通道对应一个完整的波束。可以说，卫星上的交换机是一个功能较单一 的v p 交换机。图2 1 中给出了信元交换过程的示例。 从目前国内外的研究成果 2 2 , 2 3 看，a t m 交换结构可分为交换单元和交 换网络两大类。交换网络又分为单级交换网络和多级交换网络。交换单元规 模较小，可将多个交换单元以一定的拓扑结构连接起来构成交换网络，以满 足更大规模交换需要。 哈尔滨工业大学t 学硕上学位论文 输v p i v c i输b v p w c 交换结构内部路由 输入端口号 输出端口号 标签 ( 星上为v p l )( 星上为v p i ) l8 4 5 ( 4 )3 6 ( 3 ) r 2 22 5 6 ( 5 )5 1 5 ( 5 ) 酗 8l4 5 ( 4 )4 7 ( 4 )r 8 图2 - 1a t m 交换过程示意图 2 1 2a t m 交换单元 a t m 交换单元主要有三类实现方法，它们是c r o s s b a r 交换单元f 2 4 2 5 、 共享存储交换单元和共享总线交换单元。 c r o s s 。b a r 交换单元如图2 - 2 所示。c r o s s b a r 交换单元是内部无阻塞的 交换单元，即只要输入端口信元要求的输出端口各不相同，则需交换的信元 之间不会产生冲突，均能顺利到达所要求的输出端口。在该交换单元中所有 交叉连接点只存在两种连接状态：一种称为c r o s s 状态，它表示上下、左右 直通连接；另一种称为b a r 状态，它表示上端与右端、左端与下端相连接。 当在c r o s s 。b a r 交换单元输入端存在要求相同输出端口的信元时，就会出现 输出端口竞争冲突现象。在竞争过程中，只有一个信元竞争成功顺利到达所 要求的输出端口，其它竞争失败信元需缓冲排队等待下一个时隙进行交换。 共享存贮交换单元( 图2 - 3 ) 所有输入信元均在一个存贮器中排队缓 冲。通过对该共享存贮器读写指针的控制将输入信元送至正确的输出端口。 ：一： ：= 坚尘婆三些奎兰三兰竺兰兰堡彗苎一 ：一：一= 由于所有输入信元在同一队列中排队，因此缓冲队列的容量被所有输入信元 统计共享，这一特点使得在要求相同信元丢失率性能条件下，交换单元所要 求的缓冲队列容量最t j d 2 6 , 2 7 】。同时，任一端口输出的信元都是从同一共享存 贮器中读出的，只要共享存贮器中到达给定输出端口的逻辑虚队列非空，则 该输出端口就不会空闲。而且，在共享存贮交换单元中不存在输入队头阻塞 现象。因此，交换单元的吞吐量性能比较高。 图2 - 2c r o s s - b a r 交换单元 卜一一 一 共享 | 存储器 广 一 图2 - 3 共享存贮交换单元 图2 4 共享总线交换单元 共享总线交换单元 2 8 , 2 9 】( 图2 。4 ) 所有输入端口的信元均利用一条时分 总线和该信元所要求的输出端口控制器中的地址滤波器，被交换到正确的输 出端口。对b b 的交换单元，将一个信元的时长划分为b 个相等的时隙， 每个输入端口在固定的时隙内将信元送入时分总线，该信元被时分总线以广 播方式送至各输出端口，各输出端口控制器中的地址滤波器识别该信元的路 由标签是否与端口输出地址致。若一致，表示该信元要求从本端口输出， 则打开本端口输出控制门让信元通过：若不一致，表示该信元要求的不是本 输出端口，那么控制本端口输出控制门不让信元通过。 2 1 3a t m 交换网络 a t m 交换网络分为单级和多级两类，多级交换网络又分为单路径和多 路径两大类。单级a t m 交换网络主要有三种实现方法【”】，它们是扩充式交 换矩阵( e x t e n d e ds w i t c h i n gm a t r i x ) 、漏斗形交换网络( f u n n e l t y p en e t w o r k ) 币n 叠式交换网f h ( s h u f f l ee x c h a n g en e t w o r k ) 。 多级交换网络是近年来交换网络研究中最活跃的分支，因为它是构成 大规模a t m 交换机的基础。一般分为单路径和多路径两大类。单路径交换 网络的基础是b a n y a n 网【3 0 】。从b a n y a n 网络的任一输入端到任一输出端只 存在一条路径。b a n y a n 网的致命缺点是存在内部阻塞，最大优点是具有自 选路由特性口”a 由于信元通过b a n y a n 网所经过的交换单元数是恒定的，故 信元经交换后产生的时延相同。本课题研究的主要针对多路径a t m 交换网 络。从多路径a t m 交换网络的任一输入端口至给定的输出端口存在多条路 ：= ：一： ：= 望尘婆三些查兰三兰堡当耋堡彗圣一 ：一：一= 径。这一特性可用于减少甚至消除内部阻塞。尽管信元在给定端口之间有多 条路径可供选择，然而给定连接只能使用在信令期间确定的同一路径。具有 代表性的多路径交换网络有b a t c h e r - b a n y a n 网【3 2 】、c l o s 网、多通道互联网 ( m r n s ) 平nb e n e s 网。这四种交换网络的基本结构及其对应的路由算法将在下 一章中详细介绍。 2 2 星上a t m 业务分类 星上a t m 业务与地面a t m 业务大体相同。在地面针对各种业务的不 同特性，从通信质量上来划分，a t m 业务可以分为五类 3 3 】。对星上交换而 言，又可以将这五类业务归为三类。详细介绍如下。 2 2 1 恒定比特率业务 c b r ( c o n s t a n tb i tr a t e s ) 业务是主要用于对时延和时延抖动要求严格的 业务，比如实时话音和视频业务。 c b r 业务要求网络能提供一种均匀带宽和低时延抖动的服务。而对于 网络是否提供c b r 服务，主要是由接纳控制c a c ( c o n n e c t i o na d m i s s i o n c o n t r 0 1 ) 来决定。网络有足够的空阁带宽，c b r 服务就被接纳入网：否则拒 绝一一c b r 的业务管理主要在业务连接时刻。同时，为了保证某一个连接 的“非敌意性”，网络中应采用“漏桶法( 1 e a k yb u c k e t ) ”来监控c b r 业务流 量。 2 2 2 实时可变比特流业务 r t v b r ( r e a lt i m ev a r i a b l eb i tr a t e s ) 是主要用于对时延敏感、突发性大 的业务，如m p e g 实时视频业务，由于a t m 业务常常具有较高的突发性， 利用r t v b r 进行传输具有较大的复接增益，带宽利用率也很高。 2 2 3 非实时可变比特流业务 n r t v b r ( n o n r e a lt i m ev a r i a b l eb i tr a t e s ) 业务是适用于对时延要求不严 格的高突发性业务，n r t v b r 与r t - v b r 一样也具有较大的复接增益和较高 的带宽利用率a 可变比特流v b r 服务也需要网络提供一定的带宽。接纳控 制( c a c ) 的复杂程度与挑选一个小于业务峰值速率p c r ( p e a kc e l lr a t e ) 、大 于业务平均速率s c r ( s u s t a i n e dc e l lr a t e ) 的值有密切的关系。只有当网络能 提供该有效带宽( e q u i v a l e n tc a p a c i t y ) 时，v b r 业务才能进入a t m 网络。因 为v b r 业务并没有一直以峰值速率传输，所以其发送时可能剩余的带宽就 可分配给u b r 和a b r 业务。类似于c b r ，为了保证一个连接的“非敌意 性”，网络中应该采用“双漏桶法( d u a ll e a k yb u c k e t ) ”来监控v b r 业务流 量。 由上面可知，如果网络中仅有c b r 和v b r 业务，那么该网络就可能 不需要拥塞控制策略( t r a f f i cc o n g e s t i o nc o n t r o lm e c h a n i s m s ) 来保证业务流的 有效传输，尽管如此，由于a t m 网络中还存在u b r 和a b r 业务，所以网 络中应该采用相应的优先级方案来首先保证c b r 和v b r 业务的服务质 量。 2 2 4 无定义比特流业务 u b r ( u n s p e c i f i e db i tr a t e s ) 、j k 务适用于一些数据业务流，它们没有严格 的延时和丢失率要求。使用u b r 的业务无需定义自己的服务要求。u b r 业 务也称为“尽最大可能服务( b e s te f f o r ts e r v i e e ) ”。 由于u b r 服务不需要网络的任何监控措施，c a c 接纳控制时能更没 有带宽要求，所以只要目的地址可达到且有空闲的v c i 连接标记，那么业 务源总可以在a t m 网络中建立u b r 连接服务，由以上可以知道，u b r 连 接可能会导致网络拥塞，所以u b r 的服务性能主要由网络对拥塞的处理策 略来决定。 2 2 5 存在比特流业务 早期的网络经验表明，a t m 层的拥塞控制方案可以较大幅度地提高网 络资源的利用率，a b r ( a v a i l a b l eb i tr a t e s ) 业务是一种对网络环境变化而相 应调整源业务进网比特速率的方案。它的引入可以有效地防止网络拥塞，提 供低延时、低丢失的服务质量。a b r 业务主要是用于比u b r 业务要求更可 靠的服务环境，如重要短数据传输和计算机服务器应用等。a b r 服务的每 个连接可以规定一个最低服务速率m c r ( m i n i m u mc e l lr a t e ) 和一个峰值服 务速率p c r ，而网络通过c a c 来决定是否接纳该a b r 连接。可以预见的 是，将来的数据传输业务将主要采用a b r 服务模式。 哈尔滨工业大学t 学硕上学位论文 2 2 6 星上a t m 业务划分 在卫星通信中，可以将前述五类业务归类为三种优先级业务： ( 1 ) 最高优先级，c b r 业务； ( 2 ) 次优先级，r t v b r 业务； ( 3 ) 最低优先级业务，a b r 业务。这一业务包括传统的n r t - v b r 业 务、u b r 业务以及a b r 业务。 进行这样的划分，可以使星上交换结构中基本交换单元的缓冲管理策略 更简单有效。 2 3 星上a t m 业务的描述参数 对于卫星a t m 系统而言，其星上交换部分所提供的服务性能可以用下 述参数来表示： ( 1 ) 网络负载。定义为数据流平均到达速率与网络平均服务速率的比 值； ( 2 ) 总体信元丢失率。定义为交换中丢失的信元数与到达交换结构输 入端v 1 的信元总数的比值。信元在交换结构中被丢弃是由内部阻塞引起的； ( 3 ) 信元平均时延。定义为每一种业务的所有信元从交换结构输入端 口到输出端口经历的时延平均值。 2 4 本章小结 本章首先简单介绍了星上a t m 交换的基本原理，指出了星上a t m 交 换与地面a t m 交换的不同点。星上交换只对波束进行交换且规模不大，或 者说只进行v p 交换，即一个v p 通道对应一个完整的波束。a t m 信元在到 达星上交换结构输入端口时，先到输入输出控制电路中，根据路由表将输 入的v p i 值转换为该信元交换输出后所要求的v p i 值 然后根据路由表所 指示的输出端口，在信元前面附加路由标签( m u t i n gt a g ) ，再进入交换结 构。交换结构根据信元的路由标签在路由控制器的控制下( 或自选路由) 将 信元送到正确的输出端口，完成路由选择功能。 然后，介绍了a t m 交换单元和a t m 交换网络的分类。a t m 交换单元 主要有三类实现方法：c r o s s b a r 交换单元、共享存储交换单元和共享总线 呛尔滨工业大学工学硕士学位论文 交换单元。a t m 交换网络分为单级和多级两类，多级交换网络又分为单路 径和多路径两大类。其中，重点指出了多路径交换网络的典型分类情况： b a t c h e r b a n y a n 网、c l o s 网、多通道互联网( m i n s ) 和b e n e s 网。 接着，对a t m 业务的种类进行详细说明，并对卫星a t m 业务进行简 单分类：c b r 、r t v b r 和a b r 。 最后，介绍了星上a t m 业务的描述参数：网络负载、总体信元丢失率 和信元平均时延等。 哈尔滨工业大学t 学硕上学位论文 第3 章a t m 交换结构路由算法 具有代表性的a t m 交换结构有b a t c h e r b a n y a n 网、c l o s 网、多通道互 联网( m i n s ) 和b e n e s 网。本章对这四种交换网络的基本结构及其对应的路由 算法做详细介绍，如下。 3 1b a t c h e r b a n y a n 网络 b a t c h e r - b a n y a n 网络路由算法的研究是最早最全面的。 3 1 1b a t c h e r - b a n y a n 网络结构及其路由算法 b a t c h e r b a n y a n 网是一种自路由网络，不需要单一的路由控制器。在 b a t c h e r - b a n y a n 网中，采用多控制器来实现自路由，即各个交换单元可以独 立完成路由选择。 b a t c h e r - b a n y a n 网由b a t o h e r 排序网和b a n y a n 网组成。b a n y a n 网内部 存在阻塞，要使所有输入端口的队头信元均能无阻塞的通过b a n y a n 网，必 须满足下列条件p 4 】： ( 1 ) 所处的输入端口必须连续、密集； ( 2 ) 顺序排列在输入端口的队头信元所要求的输出端口地址必须单调 递增或递减。 通常，b a n y a n 网输入端的队头信元是随机分布的，很难满足上述条 件，因此内部阻塞不可避免。排序网络的作用就是将网络输入端随机分布的 队头信元转换为满足上述条件的信元排列，然后将经转换后的信元送入 b a n y a n 网，即可保证网络输入信元在b a n y a n 网中不会产生内部阻塞。图3 1 为8 8 b a t c h e r - b 锄v a i l 交换网络。 如果b a t c h e r - b a n y a n 网的输入端存在有要求到达同一输出端口的信元 时，b a n y a n 网的输入端会产生队头阻塞。为了克服队头阻塞，可以在排序 网和b a n y a n 网之间插入一级捕获网络构成s o r t i n g t r a p b a n y a n 网络，其 基本结构如图3 - 2 所示。捕获网络的作用就是检测输入端口是否存在输出地 址相同的信元，对于输出端口地址相同的信元只允许一个信元进入b a n y a n 网络，其它信元反馈至排序网络重新排序。 哈尔滨工业大学t 学硕上学位论文 iiii i b a t 。h e r 排序网络 ii 自路由b a n y a n 网络 l l ii i 图3 - 18 8 b a t c h e r - b a n y a n 网络结构 图3 - 2s o r t i n g t r a p b a n y a n 网络 3 1 2b a t c h e r - b a n y a n 网路由算法分析 b a t c h e r b a n y a n 网具有简单的路由算法，并且对路由控制器的压力不 大，比较容易实现。但是b a t c h e r - b a n y a n 网仍然存在缺点【3 6 q 引，如下： 第一，它不支持点到多点的连接，即不支持点到多点。由于b a t c h e r 网 是一个排序网络，它根据信元的目的地址进行排序：b a n y a n 网是一个自选 路出网，它能保证所有信元都按照路由标签所指示的地址信息到达正确的输 出端口。由此可知，对于同一标签的信元只能到达一条出线，所以它不可能 支持点到多点。 第二，它仍然会产生内部阻塞。当来自不同输入端口的信元具有相同 的输出端口时，势必会给捕获网络造成压力，反馈后的信元仍然会和后续信 元流发生碰撞，产生阻塞。 ：一： ：= 坚尘婆三些奎兰三兰竺兰兰堡彗苎一 ：一：一= 第三，b a t c h e r - b a n y a n 网不适合做大规模a t m 交换网络。一个 1 0 2 4 x 1 0 2 4 大小的交换机需要一个5 5 级的b a t c h c r 网络。当规模很大时， b a t e h e r b a n y a n 网内部级间的同步很难做到，自然也增加了其控制复杂度， 所以b a t c h e 卜b a n y a n 网的规模不能太大。 3 2c l o s 交换网络 c l o s 型多级互联网络结构规则，可扩展性良好，是设计大规模交换网 络的首选网络。 3 2 1c l o s 交换网络结构及其路由算法 c l o s 网络 3 9 1 是一种多级网络，典型的为三级网络，分为输入级，中间 级和输出级。而当容量扩大时，可以将中间级再次用一个三级网络代替，从 而构成五级网络。但是在实际应用以及理论研究中，最为广泛采用的是三级 c l o s 网络。三级c l o s 网络的典型结构如图3 - 3 所示。 圈3 - 3 三级c l o s 网络示意图 c l o s 网络的多路径是由中间交换单元提供的，中间交换单元在c l o s 网 络中起着交通安全岛的作用，其数目确定了c l o s 网络任一输入输出端口对 之间存在的路径数。c o l s 网络不具有自选路由特性。但是，通过控制中间 交换单元的连接图样，可以将电路交换的基本思想溶入a t m 交换中。同 时，通过控制中间交换单元连接图样的分配4 0 , 4 1 】，可以有效的管理虚通道连 ：一： ：= 坚尘婆三些奎兰三兰竺兰兰堡彗苎一 ：一：一= 接f v p c ) 和虚信道连接( v c c ) 的业务质量( q o s ) 。 在c