（通信与信息系统专业论文）基于软交换的数字集群系统组播路由算法的研究.pdf

摘要 集群通信系统是一种专用移动通信系统，具有适合于指挥调度、应急联 动等多种重要场合的群呼、组呼等点对多点通信的功能。为了更好的发挥集 群通信系统的作用，跨区域联网已成为必然要求。软交换技术独立于高度专 业化的硬件设备，其特点是控制和业务相分离、呼叫和承载相分离，这样带 来的好处是组网更加灵活，同时易于添加新业务。可见利用软交换作为集群 通信系统的交换方式已是必然趋势。组呼作为集群通信系统的重要功能在指 挥调度方面起了重要作用。组呼在传输网中往往表现为组播，所以针对集群 通信系统的特点提出适合该系统的组播路由算法是非常关键的问题。 本文首先提出了一种新的基于软交换的集群通信系统的组网方式。在新 结构中引入了分组数据库和路由服务器，并采用区域资源集中管理的方案， 从而更有利于发挥软交换技术的灵活性与高效性。 然后提出了最长最短路径约束组播路由算法( l s p c ) 。目前组播路由算 法往往考虑整体开销最小而忽略了单一路径的开销问题，所以很难保证每一 路径的q o s 。虽然目前已有很多q o s 约束组播路由算法，但为了适应集群 通信系统的某些方面的q o s 要求还有很多工作要做。最长最短路径组播路 由算法通过首先计算组播组的最短路径树，然后对各条路径进行比较排序， 并选择最长的最短路径作计算路由的起始树，并依次将其它各条路径的端点 重新连接到该初始树。其中的约束条件是后来连接的路径不能超过最长的最 短路径并且在该条件下整个树的开销最小。 最后本文基于l s p c 组播路由算法提出了一种时延反馈组播路由算法。 该部分首先提出了一种对数据包在路由端口转发时延的分析方法。该方法分 为两步，先通过m m 1 m 排队模型对某一时刻业务量进行分析，然后在假 设每个数据包定长的基础上进行分析，进而得到数据包的排队时延与业务数 量的关系。基于时延估计及l s p c 算法提出了时延反馈最长最短路径路由算 法( d f l s p c ) 。该算法通过对链路时延的估计来进行链路切换。该算法的 提出解决了链路时延参数铡量困难的问题，同时也保证了链路的q o s 。 关键词数字集群；软交换；组呼；组播；组播路由算法 哈尔滨工业大学工学硕士学位论文 a b s t r a c t t r u n k i n gc o m m u n i c a t i o ns y s t e mi sap r i v a t ec o m m u n i c a t i o ns y s t e m i t h a sa s e r i e so f s p e c i a lf u n c t i o n s ，s u c h a sf l e e t - c a l l ，g r o u p c a l le t c ，w h i c ha r es u i t a b l et o d i s p a t c ha n dh a n d l ee m e r g e n c ys i t u a t i o n i no r d e rt om a k e t h et r u n k i n gs y s t e m p l a y am o r ei m p o r t a n tr o l e ，i n t e r c o n n e e t i o no ft r u n k i n gs y s t e mi sa b s o l u t e l y n e c e s s a r y s o f t s w i t c h i si n d e p e n d e n to fh i 舀d ys p e c i a l i z e dh a r d w a r e t h ef e a t u r e o fs o f l s w i t c hi st h et w os e p a r a t i o n sw h i c ha r ec o n t r o la n ds e r v i c e ，c a l l i n ga n d b e a r i n g s ot h e s o f l s w i t c hh a sm o r ef l e x i b i l i t yi nn e t w o r kc o n s t r u c t i o na n d a d d i n gn e ws e r v i c e a n di t i sa no v e r w h e l m i n gt r e n dt oc h o o s et h es o f l s w i t c h n e t w o r ka st h es w i t c h e dn e t w o r k a sa n i m p o r t a n t f e a t u r eo fr e t a k i n g c o m m u n i c a t i o ns y s t e m ，g r o u p - c a l lp l a y sa ni m p o r t a n tr o l ei nd i s p a t c h i n g t h e g r o u p c a l la l w a y sa c t s a sm u i t i e a s ti nt r a n s m i s s i o nn e t w o r k s ot op r o p o s ea m u l t i c a s t r o u t i n ga l g o r i t h m i sv e r yi m p o r t a n t f i r s t l y , t h i st h e s i sp r o p o s e san e w n e t w o r kc o n s t r u c t i o na r c h i t e c t u r ew h i c h i n t r o d u c e sg r o u pd a t a b a s ea n dr o u t i n gs e r v e r f u r t h e r m o r e ，b ya d o p t i n gr e g i o n r e s o u r c e sc e n t r a l i z e dm a n a g e m e n ts c h e m e ，i ti se a s i e rt od i s p l a yt h ef l e x i b i l i t y a n dh i g he f f i c i e n c yo fs o f t s w i t c h s e c o n d l y ，an e w m u l t i c a s tr o u t i n ga l g o r i t h mc a l l e dl o n g e s ts h o r t e s tp a t h c o n s t r a i n t a l g o r i t h m ( l s p c ) i sp r o p o s e d t h e c u r r e n tm u l t i c a s t r o u t i n g a l g o r i t h m sc o n s i d e rt h eo v e r a l lc o s to ft h em u l t i c a s tt r e ea n di g n o r et h es i n g l e r o u t ec o s t ，w h i c hc a nn o t g u a r a n t e et h eq o s o f e v e r yr o u t t h o u g ht h e r ea r eal o t o f q o s c o n s t r a i n tm u l t i c a s t r o u t i n ga l g o r i t h m s ，m o r ew o r k s h o u l db ed o n et of i n d ab e t t e rw a yo f r o u t i n gt h a ti sm o r es u i t a b l et ot h eq o sr e q u i r e m e n ti nt r a n k i n g c o m m u n i c a t i o ns y s t e m i nl o n g e s ts h o r t e s tp a t hm u l t i c a s tr o u t i n ga l g o r i t h m ，t h e s h o r t e s tp a t ht r e ei sc a l c u l a t e df i r s t b yf i n d i n gt h el o n g e s tp a t hi nt h es h o r t e s t p a t ht r e ea sas t a r t i n gt r e e ，t h e na d d i n gt h eo t h e rd e s t i n a t i o nr o u t e rn o d e si nt u r n a c c o r d i n g t h el o n g e s tc o s tf i r s tr u l e w h e n a d d i n gn e w r o u t et ot h em u l t i c a s tt r e e ， o n ec o n s t r a i n tt h a ts h o u l db em e ti st h en o d e l a t e r c o n n e c t i n g t ot h es o u r c er o u t e r n o d es h o u l dn o th a s l a r g e rc o s tt h a nt h es t a r t i n gt r e e t h e nu n d e rt h i sc o n s t r a i n t m a k et h et r e e so v e r a l lc o s ta ss n l a l la s p o s s i b l e - 一 哈尔滨工业大学工学硕士学位论文 f i n a l l y ，d e l a yf e e d b a c km u l t i c a s ta l g o r i t h mc a l l e dd e l a y f e e d b a c kl o n g e s t s h o r t e s tp a t hc o n s t r a i n ta l g o r i t h m ( d f l s p c 、b a s e do nl s p ci sp r o p o s e d b y p r o v i d i n gan e wq u e u i n ga n a l y s i s s c h e m ew ec a na n a l y s i st h er e t r a n s m i s s i o n d e l a yo ft h ep a c k e t sb yr o u t e r t h e r ea r et w os t e p si nt h en e wr c t r a n s m i s s i o n d e l a ya n a l y s i ss c h e m e f i r s t ，t h i sp a r ta n a l y z e s t h es e r v i c en u m b e rb yt h e m m i m q u e u em o d e l t h e nb ya s s u m i n gt h ep a c k e t sa r ea l l 、 d t ht h es a m e l e n g t h ，t h i sp a p e re s t i m a t e st h er e l a t i o n s h i pb e t w e e nq u e u i n gd e l a ya n dt r a f f i c t u n o u n t b a s e do nt h e d e l a y e s t i m a t i o ns c h e m ea n dl s p ca l g o r i t h m ，t h e d f l s p ca l g o r i t h mi s p r o p o s e d b ye s t i m a t i n gt h ed e l a y , t h e r o u t ei st h e n d e t e r m i n e dw h e t h e rt os w i t c ho v e ro rn o t ，w h i c hn o to n l ys o l v e st h ep r o b l e mo f t h ed i f f i c u l t yi nm e a s u r i n gt h el i n kd e l a yb u ta l s og u a r a n t e e st h el i n k sq o s k e y w o r d s d i g i t a lt r u n k i n g ，s o r s w i t c h ，g r o u p c a l l ，m u l t i c a s t ， m u l t i c a s t a l g o r i t h m i i i - 哈尔滨工业大学工学硕士学位论文 1 1 课题背景 第1 章绪论 集群通信系统是一种专用移动通信系统，它采用多信道共用因而有利于 集中建网。设施共享能够使我们有效利用有限资源，这在提高频谱利用率， 降低成本等方面有着重大的意义。集群通信系统可集指挥调度、电话、数据 传输等多种功能于一体i ”，因而有着广泛的应用场合。集群通信与公众移动 通信相比较，有一系列特殊功能，特别是在指挥调度及安全性等方面有其独 特的优点，如群呼、组呼、动态重组、直通、强拆等。同时其快速的接入速 度更是公网通信中难以达到的。 近年来，虽然公众移动通信系统发展迅速，但是公众移动通信系统仍不 能代替集群通信系统。这是因为：( 1 ) 一些专用部门如铁路、交通、公安等 独立性很强，在相应业务范围内要求保证无障碍通信，雨这一点公众移动通 信系统很难做到，同时公众移动通信系统也无法提供动态分组呼叫、优先呼 叫、限时通话、脱网工作等功能：( 2 ) 在对于高效处理紧急突发事件、信息 安全保密等事件的苛刻要求方面，集群系统也占据了不可替代韵地位；( 3 ) 集群系统把分散在各专用系统的用户频率集中起来为多个用户共享，具有自 动选择信道功能，它是共享资源、分担费用、共用信道设备及服务的多用 途、高性能的无线调度通信系统。 借鉴国际集群体制标准，制定符合中国国情的集群体制标准。开发和研 制具有自主知识产权的数字集群通信系统是非常迫切和必要的，限于中国无 线通信产业发展水平，当时选择了多种国外的集群技术方案作为中国的集群 通信体制。然而，军队、公安及政府等重要部门，对指挥调度的安全性、保 密性具有极高的要求，所以国外的现有几种集群标准并不能直接应用到中国 的重要部门。 近年来跨区域通信已越来越体现出来其重要性，对于数字集群系统同样 也需要各基站跨区域的互联，这就涉及到传输与交换问题。随着i p ( i m e m c t p r o t o c 0 1 ) 技术的进一步发展，利用i p 网络作为传输网进行互联已成为系统 联网的必然发展趋势。同时由于现在基于电路交换的p s t n ( p u b l i cs w i t c h e d t e l e p h o n en e t w o r k ) 网络，其互操作和连接只建立在网络层，网络层之上的 哈尔滨工业大学工学硕士学位论文 媒体控制要依赖于硬件系统【2 1 ，所以如果要提供新业务要对所有的交换机进 行改造，同时要更改协议，这不但周期长而且成本高。软交换将呼州控制功 能从媒体网关( 传输层) 中分离出来【3 1 ，通过软件实现基本呼叫控制功能， 包括呼叫选路、管理控制、连接控制( 建立拆除会话) 和信令互通，其核 心是一个采用标准化协议和应用编程接口a p l ( a p p l i e a t i o np r o g r a mi n t e r f a c e ) 的开放体系结构【4 1 。软交换所实现的功能相当于传统交换机中的呼叫控制功 能。随着软交换技术的不断发展与成熟，把软交换作为集群通信系统中的交 换方式具有重大的意义。 集群通信系统的指挥调度等应用特点决定了点对多点通信方式在该系统 通信方式中的重要地位，而组呼更是点对多点通信方式中的典型应用，其它 呼叫方式都可以看作组呼的特例。同时由于跨系统协作的重要性，进一步研 究组呼技术的跨系统实现问题有着很大的实际意义。集群通信系统的组呼在 传输网中往往表现为组播技术，所以有必要研究集群通信系统的跨系统传输 时传输网中的组播技术。在组播技术中，组播源把数据包发送到特定组播 组，而只有属于该组播组的成员才能接收到相应的数据包【5 1 。因此组播技术 提高了网络的利用率，极大地节省了网络资源。由于对应用在集群通信系统 中的组播有严格的实时性要求，并且接收者之间的延迟差别也需控制在一定 的范围之内，所以针对集群通信系统中的组播技术要有相应的q o s ( q u a l i t y o f s e r v i c e ) 保证。 1 2 国内外研究现状与分析 1 2 1 集群通信技术 集群通信系统是移动通信系统的一个重要分支。它的发展主要经历了三 个阶段陋】：2 0 世纪五六十年代的无线电对讲机方式，通信的双方或多方在 约定的频点使用对讲机完成通话；七八十年代由单多频道、单多基地台构 成的模拟通信系统；九十年代的以t d m a ( t i m ed i v i s i o nm u l t i p l ea d d r e s s l 方 式为主的数字集群通信系统，其承载网络基本上都是电路交换方式的网络。 而目前正要经历第四次变革，变革将体现在多方面。如其承载网络将是分组 网络、交换方式采用软交换等等。 为避免各种不同系统的相互干扰并提高通信质量及实现更高的系统容量 和频谱利用率，1 9 9 8 年3 月，国际电信联盟i t u ( i n t e r n a t i o n a l t e l e e o m m u n i c a t i o nu n i o n ) 根据世界各国提交的集群通信系统标准共制订了 a p c o2 5 ( a s s o c i a t e dp u b l i cc o m m u n i c a t i o n so f f i c e r s2 5 即a r o j e e t2 5 ) ， t e t r a p o ls y s t e me d a c s ( b n h a n c e dd i g i t a la c c e s s c o m m u n i c a t i o ns y s t e m ) ， e d a c s ，t e t r a ( t e r r e s t r i a l t r u n k e d r a d i o ) ，d i m r s ( d i g i t a li n t e g r a t e d m o b i l er a d i os y s t e m ，即i d e n ) ，i d r a ( i n t e g r a t e dd i s p a t c hr a d i os y s t e m ) ， g e o t e k 等七个数字集群通信系统的国际标准【7 】。 我国于1 9 8 9 年开始引进模拟集群系统，1 9 9 0 年投入使用，1 9 9 3 年已得 到了较快的发展。但是，从1 9 9 5 年以后发展滞缓，到1 9 9 9 年全国模拟集群 系统信道总数不超过1 万，用户总数大约只有2 0 万。一方面，由于集群系 统的用户少，生产厂家也相对较少，其市场狭小，所以价格居高不下；另一 方面，各部门还未能充分体现资源、设备、服务的共享和集中维护管理。为 推动集群通信系统在我国的建设和应用，2 0 0 0 年1 2 月2 8 日，信息产业部 正式批准发布了s j t 1 1 2 2 8 - 2 0 0 0 数字集群移动通信系统体制的电子行业 推荐标准。标准主要参照国际标准t e t r a ( 体制a ) 和m o t o r o l a 公司提出 的美国国家标准i d e n ( 体制b ) ，确定了两种集群通信体制。体制a 面向 专用调度和共用集群通信网，体制b 主要适用予共用集群通信网。同时标 准规定了集群通信系统的工作频段为8 0 6 m h z 一8 2 1 m h z 8 5 1 m h 8 6 6 m h z ，双工频率间隔为4 5 m h z 。 2 0 0 4 年1 1 月2 日我国信息产业部科技司发布了信科函 2 0 0 4 1 4 9 号“关 于基于g s m 技术的数字集群系统总体技术要求等4 项通信标准技术参 考性文件的通知”，确定了华为和中兴公司的g t 8 0 0 ( g s m t d s c d m a ) 和 g o t a ( g l o b a lo p e nt r u n k m ga r c h i t e c t u r e ) 两个数字集群通信系统的通信标准技 术参考性文件的编号i ”。从而国内自主研发韵g t 8 0 0 和g o t a 两个数字集群 通信系统获得了第一步的认可。g t s 0 0 的空中接口采用g s m ( g l o b a ls y s t e m f o rm o b i l e c o m m u n i c a t i o n ) 无线技术，能够提供集群呼叫方式以及多秘业 务。g o t a 的空中接口采用扩频与码分多址无线技术，提供集群呼叫方式以 及丰富的业务，支持大区制、小区制等多种方式组网。 1 2 2 软交换技术 软交换为基于包交换的下一代交换网络的语音和多媒体业务提供控制功 窒玺些三些奎耋三耋堡圭耋簦丝塞 ， f 指1 9 ，同时软交换也更有利于传统电信网络与分组网络的融合 1 。通常情况 下软交换被定义为提供一系列功能( 如呼叫连接、控制、路由等 的一个软 件平台【1 1 1 。软交换实现了两个重要的分离业务控制与呼叫控制的分 离，呼叫控制与业务承载的分离。软交换控制器支持多种协议，如 i s u p s i g t r a n 、s i p 、m g c p m e g a c o 、h 3 2 3 等协议【1 2 】。软交换系统中一般含 有业务服务器，软交换控制器与业务服务器的接口一般用p a r l a ya p l i x 3 或者 s i p t “1 。正是由于支持多种协议及具有通用的接口使得软交换能够很方便地 融入多种业务。 软交换概念于1 9 9 7 年由贝尔实验室提出。国际上i e t f ( i n t e r n e t e n g i n e e r i n gt a s kf o r c e ) 、i t u - tf i n t e r n a t i o n a lt e l e c o m m u n i c a t i o nu n i o n t e l e c o m m u n i c a t i o ns t a n d a r d i z a t i o ns e c t o r ) 、s o f l s w i t c ho r g ( 软交换组织) 等组 织对软交换及协议的研究工作一直起着积极的主导作用，许多关键协议都已 制定完成1 1 5 。1 9 9 9 年5 月，国际软交换协会i s c ( i n t e r n a t i o n a ls o f l s w i t c h c o s s o r t i u m ) 成立。i s c 目前已有近1 8 0 个成员，国际上太多数知名的电信设 备制造商，如阿尔卡特、思科、朗讯科技、西门子、富士通、诺基亚、爱立 信、北电网络等和一些电信运营商如美国韵l e v e l 3 、q w a s t 、a t & t ，日本 的n t t 等均为该协会成员。软交换自从提出以来便得到了业界的广泛认同和 重视。在短短的几年中，国际上已经经历了3 个阶段：实验室阶段、市场推 广阶段、大规模应用阶段1 1 6 。在软交换设备制造领域，国外知名厂商主要 有：爱立信、思科、北电、阿尔卡特、西门子。 西门子的s u r p a s s 方案已被多个运营商采用，如越南电信、英国电信 ( b t ) 、芬兰s o n e r a 、泰国亚洲电信、葡萄牙电信、德l 雪m e d i a w a y 、南美 t e l e m a r 、希腊o t e 和中国台湾的中华电信等旧。 爱立信e n g i n e 的核心网络建立在3 g p p 体系架构之上，具备可扩展的 能力，支持全新的s i p 业务。可根据用户韵分布情况来决定资源的分配。目 前商用e n g i n e 中的每一个媒体网关都承载着每周3 5 0 0 万次以上的通话 j 8 ，1 9 1 。 思科公司在充分调研s p r i n t ，a t m 和德国电信等运营商及客户基础上， 耗时4 年研发出y c r s l 系统【2 们。c r s - 1 在提供高速带宽的同时，也能够提 供诸如q o s ，安全和可管理性等的高性能。目前，s p r i n t 己经开始在自己的 核心网络上部署t c r s - 1 系统，思科与其它全球性电信运营商在c r s 1 系统 上的合作依然在延续和深化。 1 9 9 9 年下半年，我国网络与交换标准研究组启动了软交换项目的研究； 堕堡堡三些奎耋三兰堡圭兰堡丝圣 2 0 0 1 年1 2 月，信息产业部科技司印发了软交换设备总体技术要求参考性 技术文件；网络与交换标准研究组在积极制定有关信令网关、媒体网关、相 关协议的技术规范，网络开放式体系架构和设备单元的测试规范；高科技 “8 6 3 ”计划列项软交换系统在移动和多媒体应用的研究。 同时国内的中兴、华为、大唐也都参与到软交换的研发行列中。软交换 在互联网中的应用发展迅速，但在专用移动通信系统中还没有其应用。 中兴通讯自1 9 9 8 年即投入下一代网络产品的研究和开发，并全程参与了 中国五大运营商所开展的软交换项目建设，现已提出了整体方案并推出了相 关系统设备 2 1 , 2 2 l 。 华为基于软交换的w c d m a 核心网络日趋成熟。2 0 0 4 年4 月5 日，中国移 动通信集团公司在北京金融街总部正式宣布：由华为公司独家提供业界领先 水平的移动软交换( m s cv 9 ) 核心网产品，新建中国移动全国3 l 省的t 1 汇接 网络。2 0 0 4 年4 月1 9 日，广东移动宣布采用华为g 9 系统承建广东( 广州、深 圳) 二级汇接网。同时华为u s y s 已在中国、荚国、文莱、智利、巴西等1 0 多个国家和地区成功商用，获得全球领先的市场份额。 2 0 0 3 年3 月，由大唐电信自主研发的o p e n s p s s 3 0 0 0 软交换设备顺利获得 信息产业部颁发的入网试用证。 1 2 3 组播路由技术 组播技术是信息发送者沿着组播树向多个接收者发送相同信息的通信技 术1 2 毛“j ，它是集群通信系统中实现跨区域组呼、群呼等点对多点通信的关键 技术。组播技术主要分为组播路由协议和组播路由算法两大部分【2 5 1 。组播 路由协议运行于组播路由器之间，负责构建组播树和转发路由组播包。组播 路由器通过组播路由协议来决定是否进入组播树中。组播路由算法是计算组 播树的具体执行过程。 按照组播路由协议使用的范围可以分为域内组播路由协议和域间组播路 由协议。域内组播路由协议有协议无关组播一稀琉模式( p i m 。s m ) 【2 6 l 、协 议无关组播一密集模式( p i m d m ) 2 7 , 2 8 、距离矢量组播路由协议 ( d v m r p ) 、开放式组播路径最短优先( m o s p f ) 【2 9 1 、基于中心树的组播 路由协议( c b t ) p w 等。域间组播路由协议有多协议边界网关协议 ( m b g p ) 、多点传送源发现协议( m s d p ) 等。 为了将组播数据传送到所有的组成员，组播路由器之间需要建立和维护 堕查堡三些奎耋三兰堡圭兰堡篓兰 ，一 组播树。早期的路由协议中的组播树是以源节点为根建立数据流，后来的组 播路由协议中提出了以核心节点为根建立核心树韵组播树方案q “。因此按 照构建组播树方法的不同，组播路由协议又可以分成有源树和共享树协议。 有源树协议为同一个组播会话中的每个组播源构建一个最短路径组搔生成 树，显然有源树传输过程中每个组播源都可以获得自己最佳的传输路径，但 其代价是要多次计算组播树。而共享树协议需要在网络中选取某一点作为公 共的根节点，然后再构建一棵生成树，各个组播会话的组播数据均沿着一个 公共的组播树发送p “。 组播路由算法按组播树的构造方法可以分为最短路径算法、最小生成树 算法、s t c i n e r 树算法等；按是否有q o s 约束分为有约束组播路由算法和无 约束路由组播算法；按是否由一点集中进行路由计算还是由多点计算分为集 中式算法和分布式算法。 最短路径树算法的思想比较简单，其目的是使最终算得的组播树实现从 组播源到目的地都是最短路径。d i j k s t r a 算法旧和b c u m a n - f o r d 算法【3 4 】是目 前两个比较著名的最短路径算法。所以对于有个目标节点的组播，只需 要应用次最短路径算法即可，可见该算法比较简单。虽然最短路径树算 法得到的是源和目的的最短路径，但是对于整个组播来说的往往链路共享效 果不好。 最小生成树是针对广播而言的，即适合整个网络的节点都有所属成员时 的情况( 此时在集群通信系统中表现为跨系统全呼) 。为了得到最小生成 树，人们设计了很多算法，最著名的有p r i m 算法【3 5 】和k r u s k a l 算法【3 6 1 。 当组播树的计算以最小化整个组播树的开销为目标时便归结为寻找 s t e i n c r 树问题【3 w ，寻找s t c i n e r 树问题是n p 完全问题p a , 3 9 ，所以目前提出 的大部分算法都是启发式算法。目前比较典型的s t c i n c r 树算法有k m b 算 法州1 、b m s a 算法等。在b m s a 算法中是以链路韵时延开销为代价并通过 d i j k s t r a 最短路径算法计算最短路径树，然后通过反复地替换更小的组播树 分支直到没有最优分支可以替换的方法来优化组播树的开销【4 1 1 。另外的启 发式算法还有巾算法【4 2 1 、c k m b 算法【4 3 l 、k o m p e l l a 算法、m p h 算法h 4 】 和a d h 算法等等。 具有q o s 约束组播路由问题的目标是寻求满足q o s 要求的最小组播 树，使该树覆盖所有的组成员，同时使网络费用达到最小，这等价于求解带 约束的最小s t e i n c r 树问题。目前已有很多带有q o s 约束的启发式算法，即 寻找有约束条件的最小组播树【4 5 1 。时延约束最小开销树被称为带有约束条 堕堡鎏三些奎兰三兰璺圭兰堡竺塞 件的s t e i n e r 树【4 6 】。 通过计算路由的方式可以将组播路由算法分为集中式路由算法与分布式 路由算法【4 7 1 。集中式路由算法也称为源路由算法，在该方案中每个节点都 维持着整个区域的信息，包括网络拓扑结构和各个链路的状态。基于这些全 局信息，源节点进行路由计算。源节点计算完路由后沿所选路径发送信息以 便通知各路由节点其前后节点进而保证信息的正确传输。分布式路由算法的 优点是把算法的执行分布到各个路由节点上，这样就降低了各个节点的负 担。虽然分布式路由算法每一步的计算量小，但不适合集中管理。 1 3 本章的主要研究内容和结构 本文将主要研究如何把软交换这一技术应用到集群通信系统中，然后 以基于软交换技术的集群系统跨区域组呼为背景重点对组播路由算法进行 研究。主要研究内容如下： ( 1 ) 基于软交换的集群通信系统的组网问题如何把软交换技术应用到集 群通信系统中来是本文要研究的一个问题。软交换技术是一神新兴的交换技 术，传统的交换方式在随着人们需求的增长已经表现出来了新业务开发周期 长、增值效率低，融入新设备费用高等问题，所以研究基于软交换的组网方 式有很大的现实意义。软交换技术的发展目前还有很多需要完善的地方，如 组网方式的研究、软交换中关键设备的互通方式等等问题。本文将具体针对 集群通信系统在指挥调度方面的特殊性来提出适合于快速呼叫建立及点对多 点的链路共享等问题的具体组网解决方案。该方案既要考虑到终端通信的快 速建立，同时也要考虑到在提高业务连接快速性的基础上如何提高系统的可 靠性。 ( 2 ) 组播路由问题在前面所提的系统组网方案的基础上研究组播踌由算 法。在目前的路由算法中已有基于q o s 约束的路由算法，包括单播和组播 两种情况。然而各种算法往往都是重点考虑如何使组播树的整体开销最小， 这样往往忽略了单一路径的开销问题，既可能导致虽然组播树的开销很小但 组播树中的某一条或几条路径的开销较大的情况，这样在链路条件稍微变化 一些时就可能出现相应的链路不满足q o s 要求。所以本文将重点研究如何 在得到整体开销较小的组播树的同时并为开销较大的路径留出适量开销余量 的路由算法。 本文主要结构如下： 堕尘鎏三些查兰三耋堡圭兰堡篁塞 第2 章中提出一种基于软交换的集群通信系统的组网方案。在新方案 中引入分组数据库及路由服务器两个网络设备，分组数据库存储网络中的 组呼成员的相关信息，这样就可以对组呼成员进行准确定位。路由服务器 掌握链路的全局状态信息( 包括网络的拓扑结构及链路状态) ，从而路由服 务器可集中计算通信的路由。上述设备的引入可以更好地保证i p 网络通信 的q o s 。 第3 章对目前的组播路由算法进行研究，指出目前组播路由算法往往 是以全局最优为目标而忽略了每一单独路径的情况，所以本章提出了最长 最短路径约组播路由算法( l s p c ) ，从而更好地兼顾了局部路径的开销问 题。 第4 章在提出了一种以转发路由端口排队数据包数目进行时延估计的 方法，通过时延估计来决定是否进行路径切换。然后通过结合l s p c 算法提 出了时延反馈最长最短路径约束组播路由算法( d f l s p c ) 。 最后部分为本文的结论部分。在结论中对本文提出的组网结构及所提出 的路由算法进行总结，并对今后进一步在本研究方向进行深入研究进行展 望。 第2 章基于软交换的集群系统 软交换技术凭借其呼叫建立灵活，易于新业务的快速应用等特点而被作 为n g n e x tg e n e r a t i o nn e t w o r k ) 的核心技术，同时集群通信系统的传输网 络的i p 化也将使得软交换技术作为各选的重要交换技术。 软交换之所以区别于传统电话网和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 ) 网络的“硬交换”是由于软交换只是通过系统将主叫方和被叫方的i p 网内 传输层地址( 其中包括i p 地址和u d p 端口) 互相交换郴l ，而不需要任何 电路交换单元来建立端到端的连接。同时，用户话音流由下层承载网( i p 网) 来实现，而i p 网络是基于包交换的非连接网络，并支持端到端的透明 访问。由于软交换技术分离了业务实现功能，采用了开放式应用程序接口 a p i ，使业务提供者可以基于统一、开放的接口提供更多业务，也便于在交 换机中灵活引入新业务。软交换有助于传统p s t n 网络与i p 网络的融合， 并可向下一代网络顺利演进。 集群通信系统在指挥调度等方面的特殊应用使得点对多点的通信方式尤 为重要，并且点对多点的通信业务占了系统业务的很大份额。正是由于数字 集群系统的特殊应用背景也就产生了其特殊的要求，如要有快速的呼叫建立 时间要求，高可靠性等。而目前的点对多点的组播路由技术在实现上存在着 路由计算速度较慢，业务接入时间长等缺点，所以本章将在基于软交换的集 群通信系统的基础上对点对多点的通信方式的实现进行研究。在实现点对多 点通信时重点考虑改变组网结构来更好地满足专网的跨系统点对多点通信的 实现a 本文通过在集群通信系统结构上引入分组数据库及路由服务器，从而 通过区域集中的方式来获取链路状态并计算组播路由来保证路由计算的快速 性及准确性。 2 1 基于软交换的集群通信系统总体组网结构设计 集群通信系统在组网时要充分考虑到专网的特殊性，如组呼所占的重要 地位，同时要考虑由于集群通信系统指挥调度对呼酬建立时间及系统可靠性 的严格要求。 软交换系统的呼叫和媒体传输相分离的分层结构有利于新业务的开展， 能够更好地适应未来不断增长的需求。图2 - 1 为基于软交换网络的集群通信 堕堑鍪三些查兰三兰堡圭兰堡至吝 。 系统的组网示意图。在设计总体组网结构时为了适应集群通信系统通信建立 快速及系统可靠性高等方面的要求及点对多点通信的特点，所以在该组网方 案中引入了分组数据库及路由服务器。 图2 1 基于软交抉的集群通信组网结构 f i g 2 1a r c h i t e c t u r eo f r e t a k i n gs y s t e mb a s e do l ls o r s w i t c h 图2 1 中各关键设备【4 9 ，s o l 简单介绍如下： ( 1 ) 软交换控制器软交换控制器是软交换网络中的核心设备，它独立于 底层承载协议，主要完成呼叫控制、接入协议适配、业务提供、接口地址 解析及转换、语音处理、资源控制等功能。同时可将传统p s t n 网中的话 音和中继电路接入到软交换网络中，实现t d m ( t i m ed i v i s i o nm u l t i p l e x i n g ) 数据到l p 分组的转换。通过与业务层设备业务服务器及s c p ( s c r v i c c c o n t r o lp o i n t ) 的协作，可以向用户提供电路交换机的所有业务、多媒体业 务、传统智能业务以及个性化的i p 增值业务。 ( 2 ) 中继网关在一个纯粹的i p 网络中，中继网关和信令网关可以说是 没有必要存在的，但是由于i p 网络不可能同时取代所有的p s t n ，所以需 要i p 网络和p s t n 共存。中继网关和信令网关就是为了实现i p 网络和 哈尔滨工业大学工学硕士学位论文 p s t n 互通的设备。中继网关，就是完成电路中继和分组网上的媒体流的转 换。中继网关的系统控制方面采用了冗余和容错设计技术，核心部件采用 热备份，大大提高了系统可靠性。 ( 3 ) 信令网关七号信令网关是处于传统电路交换网与分组数据网之间的 网关，可有效实现电路交换网和基于分组网的信令转换和互通。七号信令 网关在电路交换网侧接收和发送标准的s s 7 ( s i g n a l i n gs y s t e mn o 7 ) 信令消 息，在分组网侧采用i e t f 信令传送工作组标准的适配层协议和传输层协 议，具有适配能力强、安全性好、可靠性高的优点。 ) ， 同时用。) 来表示m ) 的开销，则c 口) = 。) ，。：) ，一，氐。) 。整个 组播树的平均路径开销可表示为 i ：y 垃 。岛r l 进一步组播路径开销平衡度m r c b 定义如下 ( 3 - 7 ) 哈尔滨工业大学工学硕士学位论文 m r c b 2丕(m，一-白)2ed2 丕( 啊，一差e d 半) 2 ( 3 墙) * e dm 如果以最短路径组播树的各条路径开销为基数对其它算法获得的组播树 进行规一化处理，可得相对组播路径开销平衡度r m r c b 。设通过最短路径 算法算得的最短路径树为t = 丁( 蹦，丁j ) ，r ( ) ，通过另一种路由算 法算得的组播树为，= 。) ，。一，) ，则 整个组播树的相对平均路径开销可表示为 一c r t ：生逝( 3 - 9 ) 为 即 r m r c b 2 e d 案一历2 e d 一番虹竽) 2 ( s 枷)o ( ，哳)。【b ，k ) 叶e d 引入组播路径开销平衡度m r c b 的意义是通过计算脚c 8 可以衡量各条 路径的开销总体差异程度，进而衡量各个终端的q o s 差异程度。 3 3 1l s p c 算法的数学描述 l s p c 组播算法的基本思想；尽量减少开销最大的路径开销同时尽力做 到链路共享是l s p c 算法的基本思想。例如共有村个组成员路由节点，首 先利用最短路径算法计算各个组成员目的路由节点与源端路由节点的最短路 径开销，然后选择开销最大的路径作为初始组播树，再以最短路径算法依次 向初始组播树上添加其它目的节点，添加的顺序是到源端路由节点最短路径 开销最大的节点优先添加。添加新节点的约束是后来添加的节点到源组播路 由节点的开销都不能大于初始组播树，即耍小于等于最长最短路径，同时在 该条件下得到的组播树开销尽可能的最小。 对于给定的图g ( v ，e ) ，组播信源路由节点为组播组为d v ，同时 用丁表示组播树，对所有链路毛t 的可用带宽约束为钆 6 皿。，各条路径的 最大时延为k ，则有 烈p ( ，) ) = 卿 屯m( 3 - 1 1 ) 堕玺鎏三些查兰三兰鎏圭兰竺兰兰 t a p ( o ) = 勺k ( 3 1 2 ) p ( 1 ) e t ( hv k p ( f ) 设组播树r 中的最短路径算得的最大开销为p u )