ATM网络虚通道路由规划问题的一种新解法.pdf

20叭年4月 通信学报 w22№4 第恐卷第4期 JOURNAL 0F伽NA州s】【T】啪0FC0删UMCAllONS ADril000l ATM网络虚通道路由规划问题的一种新解法 郭伟，席裕庚 (上海交通大学自动化研究所．上海200030 摘要：本文对A1M网络虚通道路由规划问题(vPR)进行了分析．并将此类问题转化为一类瓶颈 多选择整数规划问题(BMc口)，针对此类问题特点提出了一种新的有效的求解方案。在改进的启 发式群局部搜索基础上，采用分枝剪枝方法得到精确解。仿真结果与局部搜索、禁忌搜索等方法 的比较表明本文方法是非常有效的。 关键词：虚通道路由规划；瓶颈多选择整数规划；局部搜索；分枝剪枝 中国分类号：吲919 文献标识码：A 文章编号：1000一436xf2001)04—0101一邮 A眦wmethodforVPmute programprobl锄 inATMnetworks CUOW矾ⅪYu-咿g 0f (hl吕limte AIlkIn“蚰．吲 iJia岫培u血v啪时，目un咖i删，c岫) d dleVP ATMnetwo山i8 The isn孙8一 At曲埘：III“8p8per a砌yzedpmblem fou把pr(唔rar”胛洲em(VPR)in f。rⅡledi廊}abndof c|m瑚te^s— dc n州e丘醅6ve删曲0d he面出edu吕把rⅧsearchandⅡ皓b咖1chand 0f曲epfoUem，a ba蹄d∞iⅢ严wed eut to 0f捌鸵arch IIlet}·0d r洲b i3—恍rrbedg虬山e甜obmoptitIlal∞Ⅲonomlp删wit}I出e曲md曲orl in andtabI|∞amhmetl】0ds，吐他m汕oddi8 p8per鸵eⅡBVery出；舐ve andcut Keywor凼：VPR；BMCⅢ；localsea曲；b舢ch l 引言 近年来，随着不同领域中新型的富于吸引力的多媒体业务的出现，人们已经投入了大量 的研究工作到ATM网的建设中。为了方便对业务流的控制和网络资源管理，ATM网络引入了 J。目前vP拓扑结构的优化问题已成为ATM网络研究的热点之一。vP vP(virtualpatll)的概念_l 拓扑结构优化的问题主要有vP终端的选择、vP带宽的确定及vP路由的规划。其中为呼叫建 J，不存在多项式的优化算 立连接服务的路由规划技术，简称vPR问题，是一个NP完全问题_2 法，因此寻找好的多项式近似算法就成为研究的主要内容。 文献[2]提出了两种基于最小路由的算法。一种是最小路由分流算法，将VP的流