（运筹学与控制论专业论文）有负载限制的sonet环上的路由.pdf

有负载限制的逆向旋转环上的路由 摘要 随着互联网传输和多媒体数据通信的飞速发展，同步光学网络( s o n e t ) 作为一种更快，更有效和更低费用的传输技术现逐渐为更多的网络服务提供商 所采用。同步光学网络( s o n e t ) 的基本结构是s o n e t 环，它通过安装在环 节点上的加减多路器( a d m s ) 来发送、接受和中继信息。这些多路器的容量决 定了s o n e t 环实际的带宽，即一般情况下，每个s o n e t 环都存在一个带宽限 制( 容量) c ，使得环上每个链接都不能够通过多于c 单位的需求传送。 在s o n e t 环的设计和应用中出现了许多富有挑战的问题，例如环负载问 题，逆向旋转环上负载平衡的路由问题和节点容量有限的环上路由问题。这些 问题实质上都是组合优化中经典的整数多商品流问题，一般是i n p 困难的，但 在一些特殊情形下是多项式时间可精确求解的。当s o n e t 环是无向环时，截 准则在问题求解和近似算法设计中起到了关键作用：但当s o n e t 环是有向环 时，这个准则失去了效用，此时，基于线性规划的舍入技术成为算法设计的重要 方法，在逆向旋转s o n e t 环负载平衡问题的算法研究中采用这个方法获得了 一些好的结果。 本文主要考虑s o n e t 环应用过程中提出的一个组合最优化问题：在有负 载限制的逆向旋转环上，给定一组信息发送需求，每个需求都可以沿其发点和 收点之间的两个可能的路径之一( 顺时针或逆时针) 进行传送，我们需要确定 一个路由方案，即确定哪些需求被传送以及沿哪个方向传送，使其满足环容量 限制并使得被传送的需求数目( 通过量) 达到最大。我们把这个问题称为有负 载限制的逆向旋转s o n e t 环上的路由问题( 简记为l r r r ) 。 通过对线性规划舍入技术的精巧应用，我们给出了s o n e t 环上l 砌m 问 题的一个多项式时间算法。该算法在至多超出环容量一个单位的前提下，得到 了一个需求通过量不少于最优值的路由方案。对这一算法的进一步修改，可以 得到l r r r 问题的一个性能比为l 一击的近似算法，这一结果符合应用的要 求。就我们所知，目前对l r r r 问题的研究很少。根据该问题的特点，我们在算 法设计中对现有的算法技术做了许多修改和推广，并使用了无向环中的一些技 巧。这些改进在通讯网络的算法理论和实际应用中都将有很好的意义。 关键词：s o n e t 环：路由：舍入技术：多项式时间算法：近似算法 r o u t i n gi nc o u n t e rr o t a t e ds o n e tr i n g w i t hl o a dr e s t r i c t i o n a b s t r a c t w i t ht h ee x p l o s i o no fi n t e r n e tt r a f f i ca n dm u l t i m e d i ad a t ac o m m u n i c a t i o n ， t h es y n c h r o n o u so p t i c a ln e t w o r k ( s o n e t ) h a sb e e na d o p t e db ym a n yn e t w o r k s e r v i c ep r o v i d e r sa saf a s t e r ，m o r ee f f i c i e n t ，a n dl e s se x p e n s i v et r a n s p o r tt e c h n o l - o g y t h eu n d e r l y i n ga r c h i t e c t u r eo fs o n e ti ss u p p o r t e db ys o n e tr i n g s ，i n w h i c hr i n gn o d e ss e n d ，r e c e i v ea n dr e l a ym e s s a g e sv i aa d do rd r o pm u l t i p l e x - e r s ( a d m s ) i n s t a l l e do nt h e s en o d e s t h ea c t u a lb a n d w i d t ha v a i l a b l ea l o n gt h e s o n e t r i n gi sd e t e r m i n e db yt h ec a p a c i t yo ft h e s em u l t i p l e x e r s ，s oi ng e n e r a l ， t h e r ei sac a p a c i t yr e s t r i c t i o n ，d e n o t e db ya ni n t e g e rc ，s u c ht h a tn oh n ko ft h e r i n gm a yc s x i ym o r et h a ncu n i t so ft r a f f i c t h e r ea r em a n yc h a l l e n 百n gp r o b l e m si nd e s i g n i n ga n do p e r a t i n go fs o n e t r i n g ，s u c ha sr i n gl o a dp r o b l e m ，l o a d - b a l a n c e dr o u t i n gp r o b l e mi nu n d i r e c t e do r c o u n t e rr o t a t e ds o n e t r i n g s a sw e l la sn o d e - c a p a c i t a t e dr i n gr o u t i n gp r o b - l e m i nf a c t ，t h e s ep r o b l e m sf a l li n t ot h es c o p eo ft h ec l a s s i c a li n t e g e rm u l t i c o m m o d i t yf l o wp r o b l e mi nc o m b i n a t o r i a lo p t i m i z a t i o n ，w h i c ha r ei ng e n e r a l n p h a r d h o w e v e r ，i ns o m es p e c i a lc a s e s ，t h e s ep r o b l e m sa r ee x a c t l ys o l v a b l ei n p o l y n o m i a lt i m e w h e ns o n e tr i n gi su n d i r e c t e d ，c u tc r i t e r i o np l a y sac r u c i a l r o l ei nc h a r a c t e r i z i n gt h es o l u t i o n so rd e s i g n i n ga p p r o x i m a t i o na l g o r i t h m s b u t w h e ns o n e t r i n gi sd i r e c t e d t h ec r i t e r i o nf 址l st ow o r k i ns u c hc a s e l p b a s e d r o u n d i n gt e c h n i q u eb e c o m e sa ni m p o r t a n tt e c h n i q u ef o rs o l v i n gt h ep r o b l e m s ， w h i c hh a sb e e nd e r i v e ds o m eg o o dr e s u l t so nl o a d - b a l a n c e dr o u t i n gp r o b l e m s t h em a i np r o b l e mc o n c e r n e di no u rt h e s i si sa no p t i m i z a t i o np r o b l e ma r i s i n g f r o mt h eo p e r a t i o no fs o n e t r i n g s ：i nc o u n t e rr o t a t e ds o n e tr i n gw i t hl o a d r e s t r i c t i o n t h e r ei sal i s to ft r a f f i cd e m a n d se a c ho fw h i c hm a yb er o u t e di no n e o ft h et w op o s s i b l e ( c l o c k w i s ea n dc o u n t e r - c l o c k w i s e ) w a y sb e t w e e ni t ss o u r c e a n di t ss i n k ，w en e e dt oi d e n t i f yar o u t i n gs c h e m e ：t h a ti s it od e t e r m i n ew h i c h s u b s e to fd e m a n d sa n dw h i c hd i r e c t i o n sf o rt h e mt ob et r a n s m i t t e d ，s u b j e c t e d t ot h en n gc a p a c i t yr e s t r i c t i o n ，s u c ht h a tt h en u m b e ro fd e m a n d st r a n s m i t t e d ( t h et h r o u g h o u to ft h er o u t i n g ) i sm a x i m u m t h i sp r o b l e mi sc a l l e dr o u t i n gi n c o u n t e rr o t a t e ds o n e t r i n gw i t hl o a dr e s t r i c t i o n ( l r r r ) b ya ne l e g a n ta p p l i c a t i o no fl pr o u n d i n gt e c h n i q u e ，w ep r o v i d eap o l y n o - m i a lt i m ea l g o r i t h mf o rl r r rp r o b l e mi nc o u n t e rr o t a t e ds o n e t r i n g w i t h av i o l a t i o no ft h er i n gc a p a c i t yb ya tm o s to n e ，t h ea l g o r i t h mg i v e sr i s et oa r o u t i n gs c h e m ew i t ht h en u m b e ro ft r a n s m i t t e dd e m a n d sn oi e s st h a nt h eo p t i m u m w i t hs o m ef a r t h e rm o d i f i c a t i o n s ，w eg e ta na p p r o x i m a t i o na l g o r i t h mf o r l r r r ，o fw h i c hp e r f o r m a n c eg u a r a n t e ei s1 一土c + i ，a n dt h i sr e s u l ta c c o r d sw i t h t h er e q u i r e m e n t so fa p p l i c a t i o n t oo u rb e s tk n o w l e d g e ，t h e r ea r ef e wr e s u l t s o nt h es t u d yo fr o u t i n gp r o b l e m su n d e rt h er i n gc a p a c i t yr e s t r i c t i o n i no u r a l g o r i t h m ，s o m em o d i f i c a t i o n sa n dg e n e r a l i z a t i o n so ft h ee x i s t i n gt e c h n i q u e s _ a r e p r o p o s e d ，a n ds o m ea p p r o a c h e st ot h er e l a t e dp r o b l e m si nu n d i r e c t e dr i n ga r e a l s oe m p l o y e d ，i nv i e wo ft h ec h a r a c t e r i s t i c so ft h el r r rp r o b l e m t h e s ei m p r o v e m e n t sa r em e an i n g f u li nb o t ha l g o r i t h m i ct h e o r ya n dp r a c t i c a la p p l i c a t i o n s i nc o m m u n i c a t i o nn e t w o r k s k e y w o r d s ：s o n e tr i n g ；r o u t i n g ；r o u n d i n gt e c h n i q u e ；p o l y n o m i o a l t i m ea l g o r i t h m ；a p p r o x i m a t i o na l g o r i t h m 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含未获得 或其他教育机构的学位或证书使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：卦效江签字日期：功澎年r 月拥 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，有权保留 并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。 本人授权学校可以将学位论文的全部或部分内容编入有关数据库进行检索，可 以采用影印、缩印或扫描等复制手段保存、汇编学位论文。同时授权中国科学 技术信息研究所将本学位论文收录到中国学位论文全文数据库，并通过网络 向社会公众提供信息服务。( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 邵效 导师签字：亏亏爱 签字日期：沁富年歹月玎日 签字日期：细湃3 - 月7 e t 第1 章引言 1 1 组合优化 组合优化是离散数学中最年轻也是最活跃的领域之一，大概在5 0 多年前它 才变成一个独立的学科。它日趋繁荣的一个主要原因就在于现实生活中的众多 问题能够明确地表达成抽象的组合优化问题。其理论体系根植于线性规划理论， 并且同离散数学、概率论、理论计算机科学有着很强的联系。 简单来说，组合优化是在一个有限集合中搜寻一个最优对象。通常来说，这 个有限集合有一个简洁的表示( 比如一个图) ，但是我们所面对的对象常常是巨 大的一说的更精确些，它是随着表示的规模呈指数增长的( 比如图所有的匹配 或者所有的哈密顿回路) 。因此一个接一个地搜索所有的对象然后选取最好的 对象不是一个好的选择。自然地，我们就需要去寻求更有效的方法。 在2 0 世纪6 0 年代，e d m o n d s 1 】提出这样一个思想，称一个方法是有效的 如果它的运行时间是被一个表示的规模的多项式所界定的。从那以后，这个准 则赢得了广泛的接受，一个重要的推动原因是e d m o n d s 找到了几个重要的组合 优化问题的多项式时间算法( 比如匹配问题) 。我们把多项式时间可求解的问题 所在的类记作是p 。 大约在1 9 7 0 年，c o o k 和k a r p 发现几个其它的著名组合优化问题( 包括 旅行售货商问题) 在一个更大更自然的问题类( n p 类) 中是最困难的，由此 使我们对组合优化领域有了更进一步的认知。n p 类包含大部分的组合优化问 题。n p 中任何问题都能够被多项式时间归约到这种n p 完备问题。所有的 n p 完备问题在这样一个意义下都是等价的，也就是它们中任一个是多项式时 间可解的那么可以推断出它们中所有的都是多项式时间可解的。 至此以后，几乎每一个组合优化问题被证明要么是多项式时间可解的要么 是n p 完备的一并且这些问题中没有一个问题被证明是二者同时成立的。这就 聚焦成一个巨大的未解之谜：这两个性质是不相交的( 等价地，p c n p ) 还是它 们是一致的( p = n p ) ? 如上所说，组合优化中的一些问题是能够在多项式时间内找到最优解的。 但是，大部分的问题是n p 困难的，这些问题迫使我们去走下述三条道路中的 有负载限制的逆向旋转环上的路由 一条：选择一个保证能够产生一个最优解的枚举方法；或者应用一个运行时间 是多项式的近似算法；或者采取某种类型的启发式搜索技术，这种搜索技术在 解的精度或者运行时间方面没有任何先验保证。 1 2通讯网络中的组合优化 组合优化在通讯网络中的经典应用可以追溯到最短路在互联网络路由中的 使用和支撑树在桥接局域网结构中的使用。在通讯网络中，组合优化被用于网 络设计和管理中以满足不同的实际需求。组合优化在网络中的典型应用通常涉 及问题的数学模型，这个数学模型有一个目标以减少网络调度成本或者操作成 本，或以提供更好的服务质量或者改进网络性能。这些问题，往往需要我们对 它们的数学结构要有新的洞察、新的方法和有效的求解技术。 网络研究中的繁荣产生了许多新的问题，比如在光学网络、无线a dh o c 网 络、传感器网络、移动通讯网络和卫星网络的研究发展中都产生出的一些重要 的组合优化问题。常见的网络问题包括媒体存取控制，路由最优化，拓扑控制， 资源分配和管理，不同无线网络中提供的服务质量，光学网络中的光路建立等 等。对于不同的问题，通常来说我们所采用的特定的组合优化技术是相当不一 样的。通常的研究步骤是首先开始于网络问题、分析它的内在结构、研究它的 计算复杂性、然后对其给出一个有效的解。 组合优化在通讯网络中的一些具体的应用可以参看 2 】。 1 3环上路由问题 随着互联网传输和多媒体数据通信的飞速发展，引入高带宽服务和开发能 在几秒钟内传输几千兆数字化数据的光学传输设备已经成为通讯网络设计中最 新最主要的关注点。新的服务需要具有更加巨大传输容量的网络，而且对网络 设计来说新的技术要比现在使用的网络更多的考虑容错。 。传输网络的传统设计模式主要是利用多路技术提高各网络中心设备的利 用。但是，几千兆字节的系统就必须考虑可靠性问题。任何一个部分能够传输如 此多的通信量因此它的故障能够使给定的需求在网络中产生相当比例的损失， 并由此产生相应的收入损失。 在众多使网络更具生存性的方案中，自修复环的概念是最吸引人的概念之 一。在这个方案中，网络节点和链接在一个环上被连接在一起，因此一旦一个节 2 有负载限制的逆向旋转环上的路由 点或者是一个链接出现故障时，大部分的通信量能够被恢复。推动这个方案的 技术是基于光传输的同步光学网络( s o n e t ) 标准，它的基本结构是s o n e t 环。s o n e t 作为一种更快，更有效和更低费用的传输技术现逐渐为更多的网 络服务提供商所采用 3 】。设计基于光纤技术的大规模网络的新兴模式是使用 s o n e t 环连接聚类不同的节点然后在这些s o n e t 环上建立起一个网络。f 4 1 和 5 对这个标准做了较为详细的论述。 目前，s o n e t 传输标准考虑三种不同的生存环设计：( 两条光纤) 单方向 环，两条光纤和四条光纤双方向环。根据环上不同位置间需求的通信量的数量， 环上相邻位置间的距离，s o n e t 设备的费用和光纤设备的费用的不同，通常是 在这三种设计中选取一个最为经济的设计。 在由s o n e t 产生的网络设计中出现了许多富有挑战的问题，例如其中 最直接的一个问题是确定出一个成本效率的s o n e t 环生存网络。一般一个 s o n e t 环的费用依赖于它的容量( 或者是比特率) ，因此自然地就产生了这样 一个问题：对一个环网络上的需求找一个路由使得为了容纳这个通信量所需的 总容量尽可能的小。这个问题一般被称作是环负载问题。本文在后面将做具体 介绍。 1 4本文的主要结构 在本章中，我们介绍了所研究问题的实际背景和所立足的研究方法。在第 二章中，本文给出复杂性理论和近似算法的基本概念以及多商品流的一些基本 结论。在第三章中，综述介绍了环上三个问题的研究结果，包括一些相应的复 杂性结果，定理和算法等等。第四章中，详细介绍了有负载限制的逆向旋转环 上的路由问题以及我们的主要结果。 3 第2 章一些概念和结论 2 1复杂性理论的基本概念 答案是“是”或者是“否”的问题被称为判定问题。把判定问题看作是语 言( 也就是， o ，1 ) 。的一个子集) 通常会更方便些。语言由所有编码判定i ；1 题“是”实例的字符串组成。 定义2 1 一个语言l n p 如果存在一个多项式p 和一个多项式时间有界图 灵机m ( 被称为验证者) 满足对任何字符串z o ，1 ) ： 1 如果x l ，那么存在一个长度是多项式有界( 也就是，l y l p ( i z l ) ) 的字 符串y ( 证据) 使得m ( z ，y ) 接受，并且 2 如果z 重l ，那么对任何满足i y l p ( i x i ) 的字符串y ，m ( x ，y ) 拒绝。 帮助确定x 是一个“是”实例的字符串y 被称作是一个是证据，有时还被称 作是证明或者是解。因此，用语言来说，n p 是具有“简短，能很快证实的”是 证据的语言类。 如果给定了能够求解某个问题的算法，通常我们能够用它来求解一些其它 的相似问题。问题间的这种联系，通常可以用下述多项式时间归约的概念来刻 画。 定义2 2 令l 1 和l 2 是n p 中两个语言。我们称l 1 多项式时间归约到l 2 ( 记 作是l l5l 2 ) 如果存在一个多项式时间图灵机t ，给定一个字符串x 0 ，1 ) 。， 它输出另一个字符串y 并且满足z l l 当且仅当y l 2 。 显然，由定义2 2 和多项式的性质，如果l 15l 2 并且如是多项式时间可 判定的，那么l 也是多项式时间可判定的。 定义2 3 一个语言是n p 困难的如果对每一个语言l n p ，l 75l 。一 个语言l 是n p 完备的如果l n p ，并且三是n p 一困难的。 有负载限制的逆向旋转环上的路由 在己的一个多项式时间算法能够推出n p 中每个语言都有一个多项式时间 算法( 也就是，它推出p = n p ) 的意义下，一个n p 完备的语言l 是n p 中 一个最困难的语言。 。 由定义2 3 ，要直接证明一个问题是n p 一完备的是很困难的。但是由定义 2 2 ，如果我们有了一个已经是n p 完备的问题，要证明其它问题的n p 一完备性 就变得相对简单了，只需给出从这个问题到我们所要讨论问题的一个多项式归 约就可以了。关键性的突破是c o o k 6 】对适定性问题( s a t ) 给出了n p 完备性 证明。k a r pf 7 1 随即证明了一些已知问题的n p 一完备性( 例如，哈密顿圈问题， 划分问题和旅行售货商问题) 。以已经被证明是n p 完备的问题作为出发点，越 来越多的问题被证明是n p 一完备的。此外，除了少数( 重要的) 问题以外，出现 在n p 中的绝大部分问题已经被分类为属于p 或者是属于n p 完备的。 考虑到又大又非常不同的n p 完备问题集合中这么多年来还没有一个问题 已经产生出一个多项式时间算法，所以人们广泛地认为p n p ，也就是，不存 在判定一个n p 完备语言的多项式时间算法。 p n p 猜想有着深刻的哲学意义，它断言对一个数学命题找一个证明要 比对这个命题仅仅验证一个给定证明的正确性在本质上更加困难。 2 2n p 最优化问题和近似算法 下述n p 一最优化问题的定义是由c r e s c e n z i 和p a n c o n e s i 【8 】给出的。 定义2 4 一个n p 一最优化问题由以下部分组成： 一个在多项式时间内可识别的有效实例集合d n 。我们假定一个输入中所 有给定的数都是有理数，因为我们的计算模型不能够处理无限精确的算 术。定义一个实例i d n 的规模( s i z e ) ( 用i i 表示) 为将出现在这个实 例中的所有数都写成二进制所需要的位数。 每个实例i d 有一个可行解集合品( ，) 。我们需要品( j ) 0 ，并且每 个解s ( ，) 的长度是有i j r i 的多项式界的。而且，存在一个多项式时间 算法，给定一对( i ，8 ) ，它判定是否有s s h ( ，) 。 存在一个多项式时间可计算的目标函数o b j n ，它对每对( i ，s ) 分配一个非 负有理数，这里，是一个实例而8 是，的一个可行解。目标函数常常有一 个自然解释，例如费用，长度，重量，等等。 6 有负载限制的逆向旋转环上的路由 最后，被指定为是一个最小化问题或者是一个最大化问题。 n 的单位费用实例限制被称作是的基数版本。 一个最小化( 最大化) 问题实例的一个最优解是一个达到最小( 最大) 目标 函数值的可行解。我们用o p t n ( i ) 表示实例，的一个最优解的目标函数值。当 我们能够明确我们所研究问题的一个一般实例时我们将简记为o p t 。 对每一个n p 一最优化问题，通过给出最优解的一个界限我们能够自然地使 它与一个判定问题发生联系。因此，n p 一最优化问题的判定版本n 由( j ，j e 7 ) 组 成，这里，是的一个实例而b 是一个有理数。如果是一个最小化( 最大 化) 问题，那么判定问题的答案是“是”当且仅当存在，的一个费用b ( b ) 的可行解。如果是这样，我们将称( ，b ) 是一个“是”实例；否则我们将称它是 一个“否”实例。 显然，n 的一个多项式时间算法能够帮助求解判定版本一通过计算一个最 优解的费用然后与b 做比较。反过来，对判定版本建立的困难性对n 延续。实 际上通过证明它的判定版本是n p 困难的就可以建立起一个n p 最优化问题 的困难性。稍微滥用一下符号，我们也称最优化问题是n p 困难的。 p n p 猜想指出n p 困难问题是没有多项式时间算法的。因此我们退而 求其次，希望在一个有效的时间( 即多项式时间) 内一找到一个“接近”最优解 的可行解。由此产生了近似算法的概念，其正式的定义对于最小化问题和最大 化问题略有不同。 定义2 5 ( 近似算法) 令是一个最小化( 最大化) 问题。令e o 并令 p = 1 + e ( j d = 1 一e ) 。称一个算法a 是问题的一个近似算法，如果对的 任何一个实例，它都输出一个目标函数值为a ( i ) 的可行解，并且a ( i ) 满足 a ( i ) 一o p t ( ) i e o p t ( i ) ( 2 1 ) 在这个情形下，称p 是近似算法a 的性能保证或者是最坏性能比，也称为算法 a 的近似度。 注意对于最小化问题，( 2 1 ) 中的不等式变为a ( i ) ( 1 + e ) o p t ( ，) ，而对 于最大化问题，( 2 1 ) 中的表达式变为a ( i ) ( 1 一e ) o p t ( i ) 。另外还需注意对 于最小化问题最坏性能比p = 1 + e 是一个大于或者等于l 的实数，而对于最大 7 有负载限制的逆向旋转环上的路由 化问题最坏性能比p = 1 一是区间 0 ，1 中的一个实数。实数p 被看作是近似 算法性能的一个度量。易见，p 越接近于1 ，近似算法的性能越好。 自然，我们希望近似算法的性能保证越高越好，这就产生了多项式时间近 似方案的概念，具体的定义如下。 定义2 6 ( 近似方案) 令是一个最小化( 最大化) 问题。 问题的一个近似方案是由问题在0 e 1 上的所有1 + e ( 1 一e ) 一近 似算法a 。构成的算法族。 问题的一个多项式时间近似方案( p t a s ) 是其时间复杂性为输入规模 的多项式的近似方案。 问题的一个完全多项式时间近似方案( f p t a s ) 是其运行时间为输入 规模和l e 的多项式的近似方案。 2 3多商品流和边不相交的路 有向图中一个发点5 一个收点t 的最大流问题是组合优化中的一个经典问 题，已经找到它的多项式时间精确算法。如果所有的弧容量都是整数，那么存 在着有效的算法可以保证输出的最大流也为整数值。而且最大流值恰好等于分 离s 和t 的最小截容量。如果限制所有的容量都为l ，最大流问题就变为寻找弧 不交的路问题。 但是在实践中，人们不仅仅对连接只有一对发点和收点的流或路感兴趣， 而且还可能会对同时连接几对发点和收点的流或路感兴趣。在大型的通讯网络 和运输网络中，我们可能会遇到在同一网络中同时在几对不同的顶点间传送几 种信息或者是货物。k a l a b a 和j u n c o s a 9 】早在1 9 5 6 年就给出了多商品流问题 在通讯网络中的应用。一个最近的实践需求产生在超大规模集成电路设计中， 要求人们将几对插脚通过芯片上的导线连接起来，同时还要满足使得导线遵循 着给定的网格并且连接不同的插脚的导线间不会相交。这些实践问题就导致了 多商品流问题( 亦简称为多流问题) 和不相交路问题。 具体到有向图上，多商品流问题就是对于一个有边容量的无向图，针对 几对顶点对( 一对顶点对就被称为是一个商品) 中的每对顶点( s ，t ) 寻找一个 s 一一流，使得通过任何一条边的各商品的总流量不超过该边的容量。出于技术 8 有负载限制的逆向旋转环上的路由 上的原因，我们一般用第二个有向图来指定这些顶点对，当我们需要寻找一个 s 一流时，在这个有向图中我们有一条从8 到t 的边。正式的定义是： 在无向图中可以类似定义多商品流问题，具体的定义是： 通常我们将g 中的边称作是供应边( s u p p l ye d g e s ) ，而把日中的边称作是 需求边( d e m a n de d g e s ) 或者是商品( c o r n m o d i t i e s ) 。多商品流问题有时也被称 作是分数路由问题。如果要求z ，是整数值的，就称其为整数多商品流或者是路 由问题；如果要求2 x f 是整数值的，就称其为半整多商品流或者是半整路由问 题。如果让三1 ，b 三1 并因此迫使o ，是0 1 值的，那么我们又将问题称作是 边不相交路问题。因而，边不相交问题可以叙述成：在g 中是否对每条需求边 ，e ( h ) 都存在一条连接它的发点和收点的路并且使得这i e ( h ) i 条路是边不 相交的。 早在上世纪3 0 、4 0 年代，许多学者就已进开始提出多商品流问题或与多商 品流问题密切相关的一些问题。自上世纪5 0 年代起学者们逐步研究发现，大部 9 有负载限制的逆向旋转环上的路由 分的针对单一商品的流和路问题有效的多面体和多项式时间方法是不能拓展使 用到多商品的流和路问题中来的。通过持续的研究发现，一般来说多商品流问 题若有整数解则有半整解，如有半整解则有分数解，但反之不然【l o 】。 分数( 有向或者无向) 多商品流问题有一个自然的线性规划形式，因此应 用任何多项式时间线性规划算法可以对它进行求解。t a r d o s 【1 1 通过证明有 f 0 ，士1 ) 约束矩阵的任何线性规划是强多项式时间可解的，证明了分数多商品流 问题是强多项式时间可解的。o n a g a 1 2 】则给出了分数多商品流问题有解的充 要条件。 定义2 9 多商品流问题的一个实例( g ，h ，u ，b ) 满足距离准则( d i s t a n c ec r i t e - r i o n ) ，如果对每个z ：e ( c ) _ r + 有 b ( f ) d i s t ( a 加，t ) 札( e ) z ( e ) ( 2 孔 ，= ( 8 ，t ) e ( 日) e e e ( a ) ( 在无向情形，必须用 s ，) 替换( s ，) ) 。 可以将距离准则的左端项理解为解关于边费用z 的费用的一个下界，而将 右端项理解为是最大可能费用的一个上界。 定理2 1 0 ( o n a g a ，1 9 7 0 ) 距离准则是( 有向或者无向) 多商品流问题有解的充 要条件 证明：令k = le ( h ) i ，则对i = 1 ，k ，令r 表示由所有有向8 i 一如路构成 的集合。那么多商品流问题有解当且仅当存在满足以下条件的a t p 0 ( 对于 i = l ，k 和p 只) 妇= b ( f i ) 对于i = 1 ，七 尸r 对于e e ( g ) 由f a r k a s 引理，这等价于：对所有的y l ，y k r + 和z ：e ( a ) _ r + 如果 y i z ( e ) 对i = l ，k 和p r ， ( 2 3 ) e e p 1 0 e u 一 p x p 入 慨 七曲 有负载限制的逆向旋转环上的路由 那么 七 y i b ( f i ) z ( e ) u ( e ) i = 1 e e ( g ) 现在我们假定选取每个玑为满足条件( 2 3 ) 的最大值。那么玑等于。pz ( e ) 取 遍所有p r 的最小值，也就是d i s t ( e 名) ( 5 t ，) 。因此这个条件就等于( 2 2 ) 。 口 因为可以将边不相交路问题看作是u 三1 ，b 三1 和具有整数性约束的多商 品流问题，所以由定理2 1 0 可知距离准则是边不相交路问题有解的必要条件。 另外一重要的必要条件是下述条件： 定义2 1 1 ( 有向或者无向) 边不相交路问题的一个实例( g ，日) 满足截条 件( c u tc r i t e r i o n ) 如果对每个x v ( g ) 在有向情形：i 砝( x ) i i 螗( x ) i ，或者 在无向情形：i 如( x ) i i 妇( x ) f 。 推论2 1 2 对于( 有向或者无向) 边不相交路问题的一个实例( g ，日) ，下述蕴 含关系成立：( g ，日) 有一个解j ( g ，h ) 满足距离准则号( g ，h ) 满足截条件 证明：第一个蕴含关系由定理2 1 0 可得。对于第二个蕴含关系，注意到截条件 恰好是距离准则的一个特殊情形，也就是与x v ( c ) 相联系的下述权函数 z c e ，：= 三：萋嵩e 矿( x ) ( 有向情形) 或者e 双x ) ( 无向情形) 口 一般来说上述蕴含关系反过来是不成立的。具体的例子详见 1 3 】。 在一些情况下添加下述欧拉条件( e u l e rc o n d i t i o n ) 是有很有帮助的： 定义2 1 3 一个无向图g 被称作是欧拉的如果每个顶点的度都是偶数。一个有 向图g 是欧拉的如果对每个 v ( a ) 都有1 6 + ( u ) i = 1 6 一( u ) i 。 计算复杂性理论出现后，学者们陆续证明了整数多商品流问题的许多子问 题都是n p 困难的。因此人们对整数多商品流问题研究的重点放在如何对问题 加以限制以便在多项式时间内找到该问题的最优解，或在n p 困难的情况下寻 有负载限制的逆向旋转环上的路由 求好的近似解。到目前为止学者们发现一些情形下的整数或者半整数多商品流 问题是可以有效解决的，特别是当顶点具有特殊的结构或者图是平面的或更一 般的可以嵌入一些特殊的曲面。在无向图情形，经常被用到的一个结论是下述 著名的o k a m u r a - s e y m o u r 1 4 】定理： 定理2 1 4 ( o k a m u r a 和s e y m o u r ，1 9 8 1 ) 令( g ，日) 是无向边不相交路问题的一 个实例，这里g + 日是欧拉的，供应图g 是平面的，并且所有的需求边的端点 都位于g 的外部面那么( g ，h ) 有解当且仅当截准则成立 1 2 第3 章环上路由问题及其发展现状 3 1介绍 同步光学网络( s o n e t ) 是一种更快，更有效和费用更低的传输技术，它 的基本结构是s o n e t 环。设计基于光纤技术的大规模网络的新兴模式是使用 s o n e t 环连接聚类不同的节点然后在这些s o n e t 环上建立起一个网络。在 光纤网络中，因为光学放大器基本上是单方向操作的，所以光纤中的光传输是 单方向的。为了有更强的容错性能，通常光纤环还需有附加的传输容量以错误 保护。s o n e t 环上的节点通过加减多路器( a d m s ) 来发送、接受和中继信息。 虽然光纤本身实际上能提供无限的带宽，但是s o n e t 环实际能够获取的带宽 由这些多路器的容量所决定。因而对每个s o n e t 环，一般地都存在一个容量 c ，使得环上每个链接都不能够传送多于c 单位的需求。 s o n e t 环通常有三种不同的构成：( 两条光纤) 单方向环，两条光纤和四条 光纤双方向环。因而s o n e t 环大体上可以分为两种，有向环( 单方向环，又称 作是逆向旋转环) 和无向环( 双方向环) 。为了更好的区分，以下我们将无向环 简称为环，而将有向环称作是逆向旋转环。 在网络设计的不同时期，我们对s o n e t 环关注的目标是不同的：构建 s o n e t 环时，我们是要确定将哪些节点通过s o n e 口环连接在一起以满足日常 的需求，同时要使得产生的费用尽可能小；s o n e t 环构建好投入使用后，一个 重要的问题就是，当有传送需求到来时；我们必须判断在现有的容量下，能否传 送所有的需求，以及如果能够的话该如何传送；一旦现有容量不够的情况，这就 产生了另一个问题，在容量限制下，我们如何选取一些需求来传送以使某个目 标( 例如传送需求的数目) 为最大。实际上，需求还可分为静态的和动态的，也 就是事先可知的和事先不可知的。 因此在实际中根据环的结构和目标的不同，关于s o n e t 环产生了不同的 问题，其中有些问题引起了持续的关注。以下我们主要介绍三个问题：第一个 是环负载问题，即在满足所有传送需求的情况下使所需的容量为最小，c o s a r e s 和s a n i e e 证明它是n p 困难的并给出了一个2 近似算法，s c h r i j v e r ，s e y m o u r 和w i i 龃e r 给出了一实用性能非常好的近似算法，随后k h a n n a 给出了一个 有负载限制的逆向旋转环上的路由 p t a s ：第二个问题是逆向旋转环上的负载平衡路由问题，对于需求都是单位1 的情形，w i l f o n g 和w i n l d e r 利用精妙的线性规划舍入技术给出了该问题的多 项式时间精确算法；而对于需求权重不同的情形，w a n 和y a n g 证明该问题是 n p 一困难的并给出了一个p t a s 。第三个问题是节点容量有限的环上路由问题， 即在节点容量的限制下寻找该问题的解或者给出否定答案，f r a n k 等给出了这 个问题在无向环上的有解的充要条件并在有解的条件下给出了一个强多项式时 间算法。值得指出的是，这三个问题在本质上都是整数多商品流问题，一般来 说，这种问题是n p 完备的( 这类问题的一个综述可以参看【1 5 1 ) ，但是在一些 特殊的情形下是可以多项式时间精确求解的。 3 2 环负载问题 我们假定一个无向s o n e t 环由n 个从0 到n 一1 顺时针标号的节点组成。 所有涉及环上节点的运算都进行模n 运算。用c f i j 表示一对节点间( 比如i 和 j ) 的需求。用麟表示最大的需求。给定环上一个节点子集x ，我们用d ( x ) 表示这个子集的总需求，也就是d ( x ) = i j x 1 的情形，c o s a r e s 1 4 有负载限制的逆向旋转环上的路由 和s a n i e e 1 7 证明了环负载问题是n p - 困难的并给出了一个2 一近似算法。以下 的证明来自 1 8 】。 定理3 2 环负载问题是n p 一困难的。 证明：首先将环负载问题变为一个判定问题，这需要给实例添加上一个目标值 t ，并问是否存在一个满足t 的西。 接下来我们给出从划分问题到环负载判定问题的多项式时间归约。划分 问题是指给定m 个正整数8 1 ，8 m 后，问是否能够将它们分成两组使得这 两组的总和相等。划分问题已经被证明是n p - 完备的( 参看【1 9 】p 2 2 3 ) 。令 礼= m + 3 ，对1 霄；取盔m + 2 = 口i ，并令厶+ 1 m + 2 = d m + 2 ，l + 3 = e