RWA算法中爱尔兰业务模型的一种实现方法
来源:步遥情感网
第18卷第1期 2013年1月 西安 邮 电大 学 学报 VoI.18 NO.1 JOURNAL 0F XI’AN UNIVERSITY OF POSTS AND TEI EC0MMUNICATIONS Jan.2013 RWA算法中爱尔兰业务模型的一种实现方法 张引发,彭炳斌,王鲸鱼,刘 涛 (西安通信学院光通信实验室,陕西西安710106) 摘 要:基于对爱尔兰(Erlang)业务模型中业务到达时间和业务持续时间生成方法的分析,通过在光网络链路中加 入时间戳信息来模拟业务的建立和拆除过程,从而在光网络路由波长分配(Routing and Wavelength Assignment, RwA)算法中建立起一个具体的爱尔兰业务模型;给出基于此模型的光网络首次命中(First—fit)RWA算法流程并进 行算法仿真,结果显示模型有效。 关键词:爱尔兰业务;时间戳;光网络;路由波长分配 中图分类号:TN913.7 文献标识码:A 文章编号:1007 3264(2013)01 0026—04 Implement of an Erlang Service Model in RWA Algorithm ZHANG Yinfa,PENG Bingbin,WANG Jingyu,LIU Tao (Optical Communication Laboratory,Xi’an Communications Institute,Xi’an 710106,China) Abstract:Based on analyzing the generation way of a service’S arrival time and its holding time in Erlang service model and by adding time—stamp information to the optical network link to simulate the process of establishment and demolition services,an Erlang service model in optical network routing and wavelength assignment algorithm was proposed.A procedure of First—fit RWA algo— rithm in optical network based on this model was given。The effectiveness of this model was con— firmed by the algorithm simulation. Keywords:Erlang service,time—stamp,optical network,routing and wavelength assignment 光网络阻塞率是衡量光网络路由波长分配 (Routing and Wavelength Assignment,RWA)算法 首次命中(First—fit)RWA算法是光网络路由 波长分配中的经典算法,所有可用波长被统一编 号,接着按照编号顺序从可用波长中按照Dijkstra 最短路径算法寻找最短路径 。 ,并将发现的第一 个能找到最短路径的波长分配给光路请求。 本文拟在分析爱尔兰业务特征的基础上,提出 一性能优劣的一个重要指标Ⅲ】 ],爱尔兰(Erlang)业 务模型是光网络RwA算法中常用的业务模型,用 于检验在不同网络负载情况下网络的阻塞率。在 爱尔兰业务模型中,业务的到达过程服从泊松分 布,业务的持续时间服从指数分布。 种在光网络RWA算法中建立爱尔兰业务模型的 诸多文献使用爱尔兰业务模型对算法性能进 方法,即通过在光网络链路中加入时间戳信息来模 行仿真验证 。 ],然而这些文献只是简单的说明算 法使用的业务模型属于爱尔兰业务模型,目前尚 拟爱尔兰业务的模型,设计基于此模型的光网络 First—fit RWA算法,并用于对美国国家科学基金会 网络(National Science Foundation Network,NSF— 无文献探讨并给出具体的爱尔兰业务模型在光网 络RwA算法实现过程。 收稿日期:2012-12 3 NET)拓扑进行仿真,以验证模型的有效性。 基金项目:中国人防基金资助项目(201 2JY002—260) 作者简介:张引发(1964一),男,教授,从事光网络安全研究。E mail:yinfazhang@163.com 彭炳斌(1987),男,硕士研究生,研究方向为光网络安全,E—mail:wycpbb@163.COrn 第18卷第1期 张引发,彭炳斌,王鲸鱼,等:RWA算法中爱尔兰业务模型的一种实现方法 ・27・ 元素构成,依次为SEmi,D[ ],Arrivaltime[m], —1 爱尔兰业务特征分析 1.1 业务到达和业务持续时间分析 爱尔兰业务模型中,所有到达业务服从参数为 Service—time[m]。SEmi和Dim]分别表示业务请求 的起始节点和目的节点,均服从[1,V]上的整数均 匀分布,通过均匀分布函数由计算机随机生成, Arrivaltime[m]和Service—time[m]分别由式(2) —的泊松分布,参数 也叫做业务到达率,而单次业 务的平均保持时间服从参数为1/fl的负指数分布。 单从到达业务服从参数为 的泊松分布并不能 和式(3)生成。 2.2业务拆除和业务建立 为便于计算,将网络拓扑图的信息存储在一个 抽象出具体的业务到达时间,因此需要找出参数 与时间的关系。 如果在单位时间间隔内事件出现的次数服从 参数为 的泊松分布,即单位时间内该事件出现k 次的概率为 ) 口 ^ P(X—k)一 (k一0,1,2,…), (1) ! 那么,相继两个事件出现的间隔时间服从参数为 的指数分布口 ,因此第m个业务请求Requset[m] 的到达时间表示为 Arrival—time[m]一 m一1 Arrivaltime[x]+exprnd(2), (2) X=1 其中exprnd( )表示一个服从参数为 的指数分布 的随机数,编写算法时可由计算机随机产生。 Requset[m]的业务持续时间服从参数为1/p 的指数分布,所以业务持续时间为 Servicetime[m]一exprnd(1/p)。 (3) 1.2网络负载和网络阻塞率 基于爱尔兰业务模型的网络负载为 Load= /p(erlang)。 (4) 分析业务到达率为 ,网络负载从aerlang到 rerlang时的网络阻塞率。令参数 一0,1/fl的取值 范围为[a/ ,r/0],依次统计不同网络负载的网络 阻塞率,假设有N个业务请求,当N个业务请求处 理完毕,没有成功分配路由波长的业务数量 为N—block,那么网络的阻塞率即为 P—N block/N×10O%。 (5) 2业务模型的建立及实现 实现爱尔兰业务模型的关键在于如何模拟业 务的到来,以及业务的拆除,以释放业务占用的资 源。不妨对网络拓扑图中的每一段链路中加入一 个时间戳,用于模拟业务的建立和拆除过程。 2.1业务生成 假设网络拓扑有V个节点,Request[m]由四个 邻接矩阵G中,G的生成规则为 f0, , G(i,J)一 1, ≠ 且i,J之间有物理链路, (6) linf,i@j且i, 之间没有物理链路, 其中i、J表示网络拓扑图G中的两个节点,inf表示 无穷大。 设置G的时间戳矩阵为G_time,以G-time(/,J) 表示G中起始节点为i,终端节点为 的链路的时间 戳。时间戳表示该段链路的业务结束时间。若 Requset[m]的到达时间Arrival—time[m]大于链路 G(i,J)的时间戳Gtime(/,J),说明该链路上旧的业 务已经过期,可被拆除,新的业务可在该段链路上 建立,由此生成一个新的可用拓扑图G—new。拓扑 图G—new中每一段链路的值 Gnew(/,J)一 f0, J, 1.Arrival—time[m ̄>G_time(i, )且G(i, ):1,(7) linf,其它。 业务RequsetEm]将在新图G—new中寻找最短 路径,并在找到最短路径集pathEm]后建立新业 务。建立业务的方法是将path[m]中对应的链路 G(i, )的时间戳G—time(i,J)更新为Requset[ ] 的业务到达时间Arrival—time[m]与业务持续时间 Servicetime[m]之和,即 Gtime(/,J)一 Arrivaltime[m]+Service—time[m]。 (8) 时间戳的更新过程同时完成了旧业务的拆除 和新业务的建立。 2.3基于爱尔兰业务模型的RWA算法设计 假定业务请求总数为N,光网络中可用波长数 为W,以N—block表示阻塞业务的数量,则基于爱尔 兰业务模型的光网络First—fit RWA算法的实现流 程如图1所示。 算法开始后,首先将Request[ ]的Arrival— time[m]与第1个波长的时间戳G—time[1]按照式 (7)作比较,生成G—new,然后在G—new中寻找最短 路径。如果能找到最短路径,则更新G—time[1]中 ・28・ 西安邮电大学学报 最短路径经过的链路的时间戳,完成业务的建立过 程;如果找不到最短路径,则对下一个波长重复进 行以上步骤。如果将"LU个波长都遍历完毕仍找不 到最短路径,则该业务阻塞,开始为下一个业务请 求寻找可用的路由波长。当业务请求都处理完毕 时算法结束。 图1 基于爱尔兰业务模型的First-fit RWA算法 3仿真与分析 为验证所建模型的有效性,使用MATLAB软 件对Fist—fit RWA算法在如图2所示的包含14个 节点,21条链路的NSFNET网络上进行仿真验证。 仿真参数如下:网络拓扑图中每段链路包含1条双 向光纤,假设网络节点没有波长转换功能,业务到 达率 一5,1/9的变化范围为Ez,40],1/卢的变化间 隔为1,即网络负载的取值范围为[1O,200],业务请 求次数N分别取1万和1O万。按照业务生成方 法,在N分别为1万和1O万时各生成了39组业务 请求,然后在波长数叫分别为5和10时执行算法, 由此得到网络阻塞率(图3和图4)。 图2 NSFNET拓扑图 0・7 O 6 蝴 eI j 舯‘ 0 5 纂o. ’ 蛊 0.3 _ ̄.。 0・2 j 0 J { 一 , 厂 l - — _.争_—_-州=、v=l5 (O .一-●● 一‘0 20 40 60 80 l00 12O l40 1 6O 1 80 200 负载/erlang ,。。 ,d ’ 。, 。 。} 善 , |- Il—●—w=I— ' ? 1 …一 ・・-● 负 ̄]erlang 图4业务总数』v为1O万次的网络阻塞率 图3给出了业务总数N为1万次,训分别为5 和1O时网络的阻塞率,图4给出了业务总数N为 10万次,波长数叫分别为5和1O时网络的阻塞率。 两图的对比结果显示,网络阻塞率曲线基本一致。 由计算机生成的39组1万次业务和39组1O万次 业务都具有爱尔兰业务特征,同时具有随机性,而 得到的阻塞率曲线基本一致,说明该模型能够有效 检验RWA算法的性能。业务总数为1万次得到的 网络阻塞率曲线波动较大,业务总数为10万次时得 第18卷第1期 张引发,彭炳斌,王鲸鱼,等:RWA算法中爱尔兰业务模型的一种实现方法 ・29・ 到的网络阻塞率曲线较为平坦,说明当网络的业务 总数足够大时,阻塞率所反映的情况更符合实际。 可以推断,当业务总数更大时,得到的网络阻塞率 曲线将更为平坦。 [4]柳刚.基于PCE的WSON光网络RWA分配策略与仿 真I-J-1.光通信技术,2012,36(11):22—24. [5]李酷,金春慧,何荣希.WDM网络中一种新的有效波 长分配算法[J].小型微型计算机系统,2006,27(7): 1182—1184. 4 总结 使用时间戳来实现光网络RWA算法中爱尔兰 [6]李蔚,黄德修,刘德明,等.光网络中一种快速动态负荷 均衡的波长路由算法[J].通信学报,2005,26(9): 60—66. [7]NGO SON—HONG,JIANG XIAOHONG,HORIGU- CHI SUSUMU.Ant—Based Alternate Routing in All— 业务模型的建立,模拟了业务的拆除和建立过程, 并设计了基于此模型的First—fit RWA算法流程, 在NSFNET网络拓扑图中就不同的网络负载进行 Optical WDM Networks[J].IEICE Transactions on Communications,2006,89(3):748—755. 了模型的仿真验证。仿真结果显示1万次业务总数 得到的网络阻塞率与1O万次业务总数得到的网络 阻塞率基本一致,说明所给方法能较好模拟光网络 RWA算法中的爱尔兰业务模型。 参 考 文 献 [8] RANDHAWA R,SOHAL J S.Static and dynamic routing and wavelength assignment algorithms for fu— ture transport networks[J].Optik-International Jour— nal for Light and Electron Optics,2010,121(8): 702—710. [9]孙立炜,林峰.基于业务的光接入网路由选择算法[J]. 现代电子技术,2012,35(9):110一l12. [11 杨立春,巩稼民,蒋杰伟,等.WDM网络中一种新的波 长分配算法[J].西安邮电学院学报,2009,14(1): 57—6O. [1o]SKORIN—KAPOV N.Routing and Wavelength As— signment in Optical Networks Using Bin Packing Based Algorithms[J].European Journal of Operation— al Research,2007,177(2):l167-1179. [2] 瞿燕英,雷震甲.基于AS0N的智能光网络关键技术 的研究[J].电子科技,2004,17(2):15-18. 赵艳梅,顾畹仪,等.适用于WDM全光网的自 [31 李培源,[11]周品,赵新.MATLAB数学建模与仿真[M].北京:国 防工业出版社,2009:242—243. 适应路由与波长分配算法[J].北京邮电大学学报, 2005,28(6):69—72. [责任编辑:王辉] (上接第25页) cal Handoff in Integrated CDMA [4] Jae-Woo So.VertiHybrid Networks[C]∥IEEE International Confer— ence on Communications,2008:2480—2484. and WLAN Systems[J].AEU—International Journal of Electronics and Communications,2008,62(6): 478—482. [9]章杰侈.垂直切换中的网络选择算法比较[J].论文选 粹,2011(7):43—46. [5] 何晴,陈光.一种基于模糊控制的3G—WLAN垂直切 换算法[J].科技通报,2010,26(2):261-264. [6] 朱辉.改进的异构无线网垂直切换算法[J].西安邮电 学院学报,2012,17(1):38—41. [101贺听,李斌.异构无线网络切换技术[M].北京:北京邮 电大学出版社,2008:256—268. [11]柴蓉,肖敏,唐伦,等.异构网络垂直切换性能参数分 析及算法研究[J].重庆邮电大学学报:自然科学版, 2010,22(1):63—70. [7] Ying—Hong Wang,Chih—Peng Hsu,Kuo—Feng Huang, Wei—Chia Huang.Handoff Decision Scheme with [12]邓中亮,王晖,朱宇佳.一种基于异构网络的自适应垂 Guaranteed QoS in Heterogeneous Network[C]∥ First IEEE International Conference on Ubi—Media Computing,2008:138—143. 直切换算法[J].现代电子技术,2010(4):114一I17. [13]吴素珍.异构网络垂直切换判决策略的研究[D].海 口:海南大学,2011:34—40. Z,Fracchia R,Gosteau J,et a1.Vertica1 Handover [81 DaiCriteria and Algorithm in IEEE 802.11 and 802.16 [责任编辑:孙书娜]