网络端到端连接路由和时隙选择算法孙俊,狄小康(华中科技大学,湖北武汉430074)SDH摘要:SDH设备种类较多,各种设备的交叉有不同的限制.文章提出了既能满足限制条件又能优化使用资源的端到端连接路由和时隙选择算法.关键词:SDH;网络;交叉连接;路由算法;优化;端到端连接中图分类号:TN929.1文献标识码:ASDHnetworkendtoendconnectionroutingandtimeslotselectionalgorithmAbstract:There’remanytypesofSDHequipmentsandeachequipmenthasitsowncross2connectionlimitation.Aroutingandtimeslotselectionalgorithmisproposedinthispaperwhichcanestablishanend2to2endconnectioninSDHnetworkssatisfyingtheconstraintKeywords:SDH;network;cross2connection;routing2algorithm;optimization;end2to2endSDH网络管理系统从底向上可分为网元层、网络层和业务层等.其中网络层的端到端连接功能是非常重要的,它能够组织协调网元层,并向业务层提供建立业务的服务.如果没有端到端连接功能,那么建立一个业务时就需要人工安排路由,然后一个网元一个网元地进行操作.这个过程不仅耗时,而且容易出错.因此,已有不少大的通信公司,如北电、朗讯等在他们的网管软件中实现了端到端连接功能.有了这个功能,建立一条业务只需要用鼠标点击几下即可.但是由于SDH设备从155Mbitƒs到10Gbitƒs类型较多,设备有不同的限制,增加了实现端到端自动路由功能的复杂性,所以网管软件实际运行中还存在计算时间较长,资源使用不够优化等问题.本文给出了一个统一的网元交叉限制模型和能够优化使用资源的路由算法.网元交叉限制模型及优化1SDH网元通常按照其处理的最大STM速率等级划分,有155、622、2.5和10Gbitƒs等设备.155和622Mbitƒs设备由于交叉容量小,一般只用一个交叉模块,提供高阶和低阶的全交叉.到了收稿日期:2002202201作者简介:孙俊(1970-),男,湖北宜昌人,博士研究生,研究方向为全光网络孙俊:SDH网络端到端连接路由和时隙选择算法组两个两纤复用段保护环(BLSR)的2.5GbitƒsADM,实现全交叉需要2016×2016的VC12级的交叉矩阵.在这种高速率等级的SDH设备中实现全交叉是不经济也是不必要的,因为网元中的交叉并不全是低阶交叉,所以实际设备往往采用多级交叉的方法.图1是网元交叉模型的示意细的算法描述.为描述方便,首先介绍几个用到的术语和概念的定义.·时隙表示法用“高阶时隙号.低阶时隙号”来表示.其中高阶时隙号是VC4端口号.因为一个VC4可包含一个VC4或3个TUG3,而一个TUG3可包含一个VC3或21个VC12,所以低阶时隙号采用3×21表示法.例如,“3”表示第3个VC4端口中的VC4时隙,“3.2”表示第3个VC4端口中的第2个TUG3时隙,“3.2.6”表示第3个VC4端口中的第2个TUG3中第6个VC12.·LowOnHigh队列存放多个用来实现低阶交叉的高阶VC4端口号对.·LowNormal队列存放多个使用了高阶到低阶通道的高阶VC4端口号.·HLN表示高低阶通道数,是网元交叉的一个限制条件.下面是算法的伪码描述.CreateCross(){输入待交叉的源和宿时隙;if(高阶交叉){if(源和宿时隙都与高阶交叉矩阵相连)按图2(a)进行交叉,不占用高阶到低阶通道;elseif(源和宿时隙都与低阶交叉矩阵相连)按图2(b)进行交叉,不占用高阶到低阶通道;elseif(源和宿时隙与不同交叉矩阵相连){if(HLN=0)无法建立交叉,返回;按图2(c)进行交叉,占用一个高阶到低阶通道,HLN减1;}7VC4,低阶指VC3和VC12.高阶交叉矩阵能完成VC4级的交叉,其外部VC4端口称为高阶VC4端口.低阶交叉矩阵能完成VC4、VC3和VC12级的交叉,其外部VC4端口称为低阶VC4端口两个交叉矩阵之间有内部VC4端口相连,称为高低阶通道.这种结构既能实现部分的低阶交叉满足实际需要,又能节省成本,不过也增加了操作的图1SDH网元交叉模型图2给出了4种类型的网元交叉形式.对于低图24种类型的网元交叉形式阶交叉,当源和宿低阶信号都是与高阶交叉盘相连时,通常会按图2(d)的方式进行交叉.如果有较多的这样的交叉,高阶矩阵到低阶矩阵的通道将占用较多,而实际上这些低阶信号并没有上下到本地要尽量少用高阶矩阵到低阶矩阵的通道资源,因为它是网元交叉系统的一个瓶颈.如果这两个低阶时隙在各自的高阶VC4时隙中的序号相同,并且高阶时隙中没有低阶时隙经过...