WDM光传送网的选路和波长分配算法
- 格式:docx
- 大小:14.78 KB
- 文档页数:11
WDM网络中一种考虑优先级的波长分配算法
闫磊;张百成;高随祥
【期刊名称】《微电子学与计算机》
【年(卷),期】2006(23)11
【摘要】提出了一种在多优先级的情况下,基于RCL算法来提高网络流量的波长分配新算法。
文章对于具有相同优先级的光路建立请求时,采用相对容量损失的RCL 法分配波长,而对于不同优先级的光路请求,通过调整门限值来保证网络尽可能地接纳更多低优先级的网络流量。
仿真结果表明,当负载较高时,多接纳的网络流量已十分明显。
【总页数】4页(P202-204)
【关键词】WDM网络;波长分配;网络流量
【作者】闫磊;张百成;高随祥
【作者单位】中国科学院研究生院
【正文语种】中文
【中图分类】TP31
【相关文献】
1.WDM网络基于波长的一种多优先级波长分配算法 [J], 吴波;乐孜纯
2.WDM网络中一种支持优先级的波长分配算法 [J], 张品;张仕俊
3.一种公平的多优先级WDM光网络波长分配算法 [J], 刘凤洲;潘炜;罗斌;孟超
4.WDM光网络中一种备用路由下支持优先级的波长分配算法 [J], 刘凤洲;潘炜;罗
斌;孟超
5.WDM网络中备用路由下支持优先级的一种新的波长分配算法 [J], 封国剑;范俊锋;高随祥
因版权原因,仅展示原文概要,查看原文内容请购买。
WDM光网中的一种邻域加权累积的波长分配策略袁俊岭;张迪;张启坤;李旭红【摘要】针对光核心传送网中单纤场景下的路由选择与波长分配(Routing and Wavelength Assign-ment,RWA)问题,提出了一种邻域加权累积的波长分配策略.在一条路径上为一个连接请求选择波长时,将网络的所有链路归入当前路径的不同邻域中,然后根据与路径之间的距离为不同邻域赋予不同的权重,进而对每个波长在全网中被占用的个数进行加权累积,最后选择累积值最大的可用波长建立连接.仿真结果表明,相对于现有的阻塞率最低的最大使用(Most-Used)波长分配策略,所提策略具有更低的阻塞率.【期刊名称】《电讯技术》【年(卷),期】2019(059)002【总页数】6页(P151-156)【关键词】光网络;波长路由;路由与波长分配(RWA);邻域加权累积(WNA)【作者】袁俊岭;张迪;张启坤;李旭红【作者单位】郑州轻工业学院计算机与通信工程学院,郑州450002;郑州轻工业学院计算机与通信工程学院,郑州450002;郑州轻工业学院计算机与通信工程学院,郑州450002;中原工学院理学院,郑州450007【正文语种】中文【中图分类】TN929.11 引言随着光传输和光交换设备的快速发展,全光交换已成为核心传输网中的主要交换方式,其中波长路由是最成熟和最简单的交换技术。
在波长路由技术中,路由选择和波长分配问题(Routing and Wavelength Assignment,RWA)一直是一个核心研究内容[1]。
RWA问题的主要任务是,为一个连接请求它选择合适的路由并分配合适的波长。
根据应用场景的不同,RWA问题可以分为两类[2]:静态RWA问题和动态RWA问题。
在静态RWA问题中,网络中节点之间的业务量以业务矩阵的形式事先给定,需要根据业务情况在每对节点之间建立路由并分配相应数量的波长,静态RWA问题的优化目标是使得网络中总共所需要的波长数最小。
WDM光传送网的选路和波长分配算法为了克服电处理的速率“瓶颈”,宽带网络向光网络发展。
目前,光突发交换、光分组(包)交换正在积极研究中,但是距商用还较远。
已可商用的是具有光分插复用器(OADM,OpticalAdd-DropMultiplexer)和光交叉连接器(OXC,OpticalCross-Connect)的波分复用(WDM)网络。
由于是提供可调度的传送用光路,称这种网络为WDM光传送网(OTN,OpticalTransportNetwork)。
1网络结构图1是网络物理结构的一个例子,虚线内为光传送网。
图中有5个OXC:A,B,C,D,E;5个具有光接口的电设备:S1~S5;6个将OXC相连的物理链路:l1~l6。
一般一条物理链路包含一对光纤供双向运用,有的OXC间没有物理链路相连。
但更多的情况是一条物理链路包含多根光纤供不同方向运用。
一根光纤上可采用多个波长。
一般情况下,OXC不直接和电设备相连,只起光交叉连接作用。
OXC可分为无波长变换和有波长变换(也可以是部分端口有波长变换或波长变换的范围有限)两种:无波长变换的OXC的作用是将一根输入光纤上的某一波长信号连到另一根输出光纤的同一波长上,即波长是连续的;有波长变换则是将一根输入光纤上的某一波长信号连到另一根输出光纤的另一波长上。
适当地安排路由和分配波长,可为电设备间建立光路(opticalpath)。
在一根光纤上,不能为不同光路分配相同波长。
图2(a)为图1建立的光路例子。
将图2(a)的光路连接用图2(b)来表示,称为逻辑结构,也称逻辑拓扑或虚拓扑。
例如,图2(a)中,节点B与E间的光路是经节点A中的OXC转接的,在图2(b)中用O4表示。
图2(b)中,O6、O4、O1都是中间有OXC转接的。
O2、O3、O5是直接光路。
这样建立的光路对信号是透明的,即信号可以是任意方式。
实际设计中,一种需求情况是:提出所需建立的光路,为这种光路选取物理路由并分配相应的波长[1,2]。
第八章 WDM光传送网络 一、填空题 1.WDM光传送网利用(波长)组网,在光域完成信号的选路、交换。
2.全光网中任意两节点之间的通信是靠(光通道)完成的。
3.WDM光传送网中波长路由算法有两种,即(波长通道)和虚波长通道。
4.WDM光网络中的虚波长通道,每一节点采用的波长集下一节点可以实现(动态空间)复用。
5.WDM光网络中光放大段层为了实现长距离超高速传输,主要解决放大和光纤的(色散)问题。
6.波分光交换能充分利用光路的(带宽)特性,可以获得电子线路所不能实现的波分型交换网络。
7.波长光分组交换机分为三个功能块,即波长选路由功能块、(光缓存功能块)和光交换功能块。
8.全光网的管理信息主要有故障信息、(缺陷信息)和性能质量信息三种。
9.光网对不同的速率、协议、调制频率和制式的信号同时兼容,并允许几代设备(PDH/SDH/ATM/)甚至与IP技术共存。
10.WDM利用(光波长分插复用器WADM)可实现不同节点灵活地上、下波长。
11.WDM利用(光波长交叉连接WXC)实现波长路由选择,动态重构、网间互连和自愈功能。
12.光网对不同的(速率、协议、调制频率和制式)的信号同时兼容,并允许几代设备PDH/SDH/ATM/甚至与IP技术共存。
13、光交换是在(光域中)完成光交换功能,而无需将光信号转换成电信号。
14、全光型光分组交换机的光信号的(定时提取)可由(光锁相环OPLL)来完成。
二、单项选择题 1.WDM光网络中的虚波长通道属( A)路由算法。
A.分布式B.集中式C.时间式D.空间式 2.在WDM光网络中最基本的空分光交换是( D )光交换模块。
A.1×1B.1 X 2C.2 X lD.2 X 2 3.在WDM光网络中自由空间光交换是指在空间无干涉地控制光的( B )的光交换。
A.波长B.路径C.时隙D.速度 4.WDM光网络的波分复用系统中,可采用( A )的方法来实现光交换功能。
ISSN 1000-0054CN 11-2223/N 清华大学学报(自然科学版)J T singh ua Un iv (Sci &Tech ),2002年第42卷第7期2002,V o l.42,N o.731/36974-976公平的多优先级WDM 网络波长分配算法邱 松, 杨知行(清华大学电子工程系,北京100084)收稿日期:2001-10-22作者简介:邱松(1974-),男(汉),江苏,博士研究生。
通讯联系人:杨知行,教授,E-mail:yang zx@ee.tsingh 摘 要:为了支持不同的业务要求出现了支持多优先级的WD M 网络波长分配算法,但是在支持多优先级的波长分配算法中仍然存在公平性问题。
为此,该文在支持多优先级的分配限额波长分配算法的基础上令波长限额随连接距离而变化,提出了一种公平分配限额波长分配算法。
仿真结果说明这种算法有效地改善了多优先级W DM 网络波长分配算法中不同距离连接间的阻塞率差别。
关键词:波分复用网络;波长分配;多优先级;公平性中图分类号:T N 929.11文献标识码:A文章编号:1000-0054(2002)07-0974-03Fair priority -based wavelength assignment method for WDM networksQIU Song ,YANG Zhixing(Department of Electronic Engineering ,Tsinghua University ,Beij ing 100084,China )Abstract :Priority-bas ed w avelen gth ass ignment methods,such as the As signm ent Quota M ethod,have been proposed to provide different blocking probabilities for traffic w ith different p riorities.How ever ,fairness is still an important issu e in these meth ods.A new priority-based w avelength as signment m ethod nam ed the Fair Ass ignment Quota M ethod w as d eveloped to im prove the fairnes s by making the quota increase w ith distance.S imulation res ults illustrate th at th e new meth od h as more balanced blocking probabilities for path s w ith different len gth s.Key words :WDM netw ok;wavelength assign ment;priority-based ;fairness路由选择和波长分配(r outing and wavelength assig nment,RWA )问题是WDM 网络的重要部分,主要解决两个任务[1]:1)路由选择:确定一条建立连接的通路;2)波长分配:为选择的通路分配波长。
中文核心期刊WDM光网络中的组播波长分配算法研究吴启武,王建萍,周贤伟,宋宁宁(北京科技大学信息工程学院通信工程系,北京100083)摘要:组播是一种应用广泛的点到多点或多点到多点的通信方式,光层组播以其独特优势引起了人们的关注和重视。
在综合分类的基础上,对光网络组播波长分配算法的最新研究进展进行了归纳和总结,并对今后需重点研究的方向进行了展望。
关键词:W D M;光网络;组播;波长分配中图分类号:TN929.11文献标识码:A文章编号:1002-5561(2009)09-0019-04Research on multicast wavelength assignment algorithm inWDM optical networksWU Qi-wu,WANG Jian-ping,ZHOU Xian-wei,SONG Ning-ning(Department of Communication Engineering,School of Information Engineering,University of Science and Technology Beijing,Beijing100083,China)Abstract:Multicast provides a means of point-to-multipoint or multipoint-to-multipoint communication, which has several applications.Because of its specific advantage,optical multicasting arrests more attention.In this paper,the newest advance of multicast wavelength assignment algorithm in optical networks based on the integrated classification is summarized.Besides,the further direction which is critical to the problem is foreseen.Key words:WDM,optical network,multicast,wavelength assignment0引言组播是一种点到多点或多点到多点的通信,其应用十分广泛[1]。
第八章 WDM光传送网络 一、填空题 1.WDM光传送网利用(波长)组网,在光域完成信号的选路、交换。
2.全光网中任意两节点之间的通信是靠(光通道)完成的。
3.WDM光传送网中波长路由算法有两种,即(波长通道)和虚波长通道。
4.WDM光网络中的虚波长通道,每一节点采用的波长集下一节点可以实现(动态空间)复用。
5.WDM光网络中光放大段层为了实现长距离超高速传输,主要解决放大和光纤的(色散)问题。
6.波分光交换能充分利用光路的(带宽)特性,可以获得电子线路所不能实现的波分型交换网络。
7.波长光分组交换机分为三个功能块,即波长选路由功能块、(光缓存功能块)和光交换功能块。
8.全光网的管理信息主要有故障信息、(缺陷信息)和性能质量信息三种。
9.光网对不同的速率、协议、调制频率和制式的信号同时兼容,并允许几代设备(PDH/SDH/ATM/)甚至与IP技术共存。
10.WDM利用(光波长分插复用器WADM)可实现不同节点灵活地上、下波长。
11.WDM利用(光波长交叉连接WXC)实现波长路由选择,动态重构、网间互连和自愈功能。
12.光网对不同的(速率、协议、调制频率和制式)的信号同时兼容,并允许几代设备PDH/SDH/ATM/甚至与IP技术共存。
13、光交换是在(光域中)完成光交换功能,而无需将光信号转换成电信号。
14、全光型光分组交换机的光信号的(定时提取)可由(光锁相环OPLL)来完成。
二、单项选择题 1.WDM光网络中的虚波长通道属( A)路由算法。
A.分布式B.集中式C.时间式D.空间式 2.在WDM光网络中最基本的空分光交换是( D )光交换模块。
A.1×1B.1 X 2C.2 X lD.2 X 2 3.在WDM光网络中自由空间光交换是指在空间无干涉地控制光的( B )的光交换。
A.波长B.路径C.时隙D.速度 4.WDM光网络的波分复用系统中,可采用( A )的方法来实现光交换功能。
第 40卷第 10期2003年 10月计算机研究与发展J OU RNAL OF COMPU TER RESEARCH AND DEV ELOPM EN TVol 140,No 110Oct 12003收稿日期 :2002211220; 修回日期 :2003206227WDM 全光网络中实时组播的分布式路由与波长分配算法黄传河陈莘萌贾小华(武汉大学计算机学院武汉 430072 (hwanghe @public 1wh 1hb 1cn摘要在 WDM 网络中 , 由于每条链路上可用波长是动态变化的 , 在考虑波长转换延迟的条件下 , 实现实时组播连接的路由与波长分配是十分困难的 1假定WDM 网络中每条链路有多根光纤 , 只有部分结点具有波长转换器且波长转换时间是不可忽略的 , 据此提出了一种用于建立实时组播连接的分布式路由与波长分配算法 1该算法以 Prim 最小生成树算法为基础 , 生成一棵满足给定延迟时限的最小成本树 1当最小成本树不能包括所有目的结点时 , 对剩余目的结点生成一棵最短延迟树 , 然后合并两棵树得到一棵组播树 1波长分配使用最少波长转换和负载平衡策略1关键词 WDM 网络 ; 路由与波长分配 ; 组播路由 ; 延迟限制路由中图法分类号TP393101A Distributed Routing and W avelength Assignment Algorithm eal 2Time Mul2ticast in WDM All 2Optical N et worksHUAN G Chuan 2He , CHEN Xin 2Meng , and J IA (Com puter School , W uhan U niversity ,Abstract for online real 2time multicast connection setup is difficult due to the of availabilities of wavelengths on links and the consideration of wavelength con 2version delay in WDM networks 1Assuming that each link has multiple fibres , there are wavelength con 2verters only at part of nodes and the conversion delay is not negligible 1A distributed routing and wave 2length assignment algorithm for the setup of real 2time multicast connections is presented based on the above assumption 1The algorithm is based on Prim ’ s MST (minimum spanning tree algorithm 1It generates a sub 2minimal cost tree under a given delay bound first 1If there are nodes not included in the cost tree , a de 2lay tree is generated to include the rest nodes 1The two trees are merged together 1The wavelength assign 2ment uses least 2conversion and load balancing strategies 1K ey w ords WDM networks ; routing and wavelength assignment ; multicast routing ; delay bound routing1引言WDM (wavelength division multiplexing 将光纤的带宽分为互不重叠的并行通道 , 每个通道使用一个波长传输信号 1WDM 是充分利用光纤带宽的关键技术 1WDM 网络是面向连接的 , 在数据传输前 , 通信双方必须建立连接 1在 WDM 网络中建立连接包括路由选择和波长分配两个过程 , 简称为 RWA(routing and wavelength assignment 1组播是一种组通信机制 , 其发送者 (源结点将消息同时发送给一组接收者 (目的结点 1实时组播是一类特定的组播形式 , 要求在组播请求到达后尽快建立组播连接 , 同时在所建立的连接中从源结点到任一目的结点的延迟时间不超过给定的时限 1实时组播在现代计算机网络中有广泛的应用 , 例如电视会议、多媒体教学、视频点播、网上拍卖等 1建立实时组播的路由就是找到一棵以源结点为树根、包含所有目的结点的路由树 , 并且从源结点 (树根到任一目的结点 (树叶的传输时间不超过给定的时限 , 路由树的总成本最小 1寻找这种路由树的问题是 N P 2hard 问题 , 现已有一些启发式方法 [1]1在 WDM 网络中建立实时组播连接的主要困难是 :(1 每个网络结点只知道与其相连的链路上可用的波长 , 没有任何结点具有全网的拓扑结构或可用波长的信息 1(2 只有当路由请求到达一个结点时 , 才知道是否需要进行波长转换 , 而波长转换时间是不可忽略的 , 可能会使所选路径超过延迟时限而无效 1 (3 延迟和成本因素是相互独立的 , 具有最小成本的路径可能具有很长的延迟 , 反之亦然 1本文提出了一个在 WDM 网络中建立实时组播连接的分布式路由与波长分配算法 1该算法首先构造一棵最小成本树连接满足延迟限制的目的结点 1对没有连入最小成本树的结点 , 利用构造一棵最短延迟树 , 使其包含所有其余目的结点 1然后 , 将两棵树合并成一棵统一的树 1:,; ③所构造的树在满足延迟时限的条件下具有接近最优的成本 12问题定义网络用无向图 G (V , E 表示 , 其中V ={1, 2, … , N }为结点集 , E ={(i , j }是光纤链路集 , 链路 (i , j 可能包括多条光纤 , 编号为1, 2, … , k 1每条链路 (i , j 有 3个参数 :① σk ijΑ{1, 2, … , W }表示链路 (i , j 的光纤 k 上当前可用波长的集合 ;② c ij 表示使用链路 (i , j 的成本 ;③ d ij 表示链路 (i , j 的延迟时间 1链路 (i , j 上的可用波长是动态变化的 , 只有与此链路相连的两个结点确切知道当前σk ij 的值 1在建立连接时 , 为该连接的每一链路分配一根光纤及该光纤上一个当前未被使用的波长 1被分配的波长一直被占用 , 直到通信结束连接被终止 1网络中结点具有光纤交换功能 , 即从一根光纤上输入的光信号可以从输出链路的任一光纤上输出 1只有部分结点具有波长转换器 1同时假定每个波长转换器可以将任一波长转换为任一其他波长 1 R [i ]=1表示结点 i 有波长转换器 1在一条路径上的通信延迟包括链路延迟和波长转换时间两部分 1链路延迟 d ij 表示信号从结点 i 经链路 (i , j 到达结点 j 所需的时间 1波长转换时间d c i (λx , λy 表示结点 i 将波长λx (输入波长转换为波长λy (输出波长所需的时间 1假定所有波长转换器完成任何两个波长之间的转换所需时间是相同的 1如果没有进行波长转换 , 即λx =λy , 则d c i (λx , λx=01如果结点 i 没有波长转换器 , 且λx ≠ λy , 则d c i (λx , λx =∞ 1考虑建立组播连接的实时请求R =(s , D , Δ , 其中 s 是源结点 , D 是目的结点集合, Δ是延迟时限值 1组播连接是一棵树 T , T 的总成本定义为 COS T (T =(i , Tc ij 1(1 令 P (u , v T u 到结点 v 的 , u D EL A Y (u , vY (u , v =∑(i , j ∈ P (u , vd ij +∑i ∈ P (u , vd c i (λx , λy 1 (2 从树根 s 到任意结点 v 的延迟记为 D EL A Y (s , v , 树 T 的延迟定义为DEL A Y (T =max {DEL A Y (s , d , Πd ∈ D}1 (3 延迟时限条件可以表述为D EL A Y (T ≤ Δ1(4 本文所考虑的问题是设计一个分布式的路由和波长分配算法来构造一棵波长路由树 , 使得该树在满足式 (4 定义的条件下成本尽可能小 13相关研究成果最小成本树是 Steiner 树 , 加上延迟限制后 , 寻找带延迟限制的 Steiner 树是 N P 2hard 问题 [1]1关于构造最优组播树的研究已有一些结果 [1,2], 但这些结果并不能直接用于 WDM 网络 1目前关于 WDM 网络的路由与波长分配的研究主要是针对点到点通信的 1如Spath 提出了几种路由策略 [3],Jia 等人提出了一种针对静态请求、旨在使波长转换最少的 k 2cut 方法 [4]1在 WDM 网络中 , 路由算法应以链路上当前可用波长为基础 1Sahasrabuddhe 等人提出的光树概念 [5],Li [6],Pankaj [7]等人分别提出的计算需要最少波长数的路由树的方法 ,Jia 等人提出的一种为一组静态组播请求分配路由的算法 [8], 都为组播路由与波长分配问题提供了有益的借鉴 1但所有这些关于 WDM 网络的研究都是将路由 (构造树与波长分配作为独立的过程对待 , 或者假定网络状态、参数是静态不变的或具有特定的拓扑结构 1对一般的 WDM 网络上的组播它们并不适用 14分布式算法411算法基本思想本文所提出的分布式算法由两部分组成 : G enCtree 和 G enDtree 1G enCtree 以 Prim 的 MST 算法为基础 , 构造一棵最小成本树 Ctree 1其工作过程是 :每次选取一个离树最近 (按成本计算的结点 , 如果其延迟满足约束条件 , 则将其加入到树中 1如果 G enCtree 能将所有目的结点加入到 Ctree 中 , 则算法终止 1否则 , 调用过程 G enDtree1 G enDtree ,构造 Ctree 后 , 1在 1因此必须消除 Ctree 中的某些边以保证树的性质 , 同时满足延迟条件 1412数据结构路由表 CRoutab 和 DRoutab :每个结点都保存有成本路由表 CRoutab 和延迟路由表 DRoutab 1路由表中的项 CRoutab [d ]/DRoutab [d ]表示到达目的结点 d 的最小成本 /最小延迟及其可能的输出链路 , 其中第 1个链路为主链路 , 其余链路为候选链路 1路由表可以使用距离向量路由算法计算得到 1目的结点到树的距离 :在构造树时 , 为每个目的结点记录一个三元组〈 t reenode , dest , dist 〉 , 用于跟踪每个目的结点到已经构造的树的最短距离 1〈 t reenode , dest , dist 〉表示到目的结点dest 的最短距离是 dist , 它通过树上结点 t reenode 连接到树中 1可用波长链路数NL (λ :每个结点记录与其关联的链路上的可用波长1NL (λ 表示与本结点相关联的链路中波长λ可用的链路总数 , 每根光纤计算为 11413最小成本树 Ctree 的构造(1 Ctree 的构造算法 G enCtree①源结点 s 启动 G enCtree , 将 s 加入到 Ctree 中 1② s 利用 CRoutab 选择一个最近的目的结点 , 选择通往该目的结点、具有可用波长的一条输出链路 1如果主链路没有可用波长就选择一条候选链路 1然后通过所选择的链路向下一个结点发送一个 CFIND 消息 1③下一结点收到 CFIND 消息后 , 使用相同的方法选取通往选定的目的结点的输出链路 , 直到到达目的结点 1④ CFIND 消息在传递过程中收集从所构造的部分树到其他目的结点的最短路径的信息 1CFIND 消息所到达的目的结点通过所收集的三元组信息负责选取下一个加入到树 Ctree 中的目的结点 dest 及其相应的在树上的连入结点 t reenode , 然后向该树结点发送一个消息 , 由该树结点启动路径〈 t reenode , dest 〉的建立过程 1⑤每当 CFIND , 该目 Ctree 中的目的结点 1,, 并通知其进行相应的操作 1⑥重复上述过程直到没有目的结点可以加入到树中 , 这时 , 调用 G enDtree 过程 1G enCtree 用于选择目的结点的标准是最小成本 1树 Ctree 与目的结点 d 之间的最小成本距离定义为DIS T (Ct ree , d =min {COS T (t , d , Πt ∈ Ct ree , d ∈ D 2Ct ree}1(5 设所选择的输出链路为 (v , w , 则从源结点 s 经 v 到达 v 的邻结点 w 的延迟 DEL A Y (s , w 定义为 D EL A Y (s , w =D EL A Y (s , v +d vw +d c v (λv , λw , (6 该延迟在结点 v 进行计算并测试 1如果试探失败 , 发现失败的结点负责通知源结点 , 然后另外选取一个目的结点开始其连入树的操作 , 同时释放为失败的路径所预留的波长 1(2 G enCtree 的波长分配策略选择输出链路的结点负责进行分配波长 1波长分配策略为 :①输出链路任一光纤上与输入链路上相同的波长可用时 , 优先分配该光纤及波长 ;②如果该波长在所有光纤上不可用 , 则选择具有最大 N L (λ 值的波长及具有该波长的第 1根光纤 1 414最短延迟树 Dtree 的构造(1 Dtree 的构造算法 G enDtreeG enDtree 以源结点 s 为树根 , 将所有没有包含在 Ctree 中的目的结点连接起来构造一棵最短延迟树 Dtree 1在构造 Dtree 时 ,G enDtree 需考虑 3个因素 :①当最短延迟树存在时 , G enDtree 必须能够以很高的概率构造成功 ;② G enDtree 必须简单、执行速度快 , 以便能快速完成组播连接的建立 ;③所构造的延迟树 Dtree 应该易于与成本树 Ctree 合并 1Dtree 和 Ctree 可能有公共链路和结点 , 合并可能会产生回路 1G enDtree 以并行方式运行 , 构造算法为 :①对剩余的每个目的结点 d , 源结点 s 从 DR outab[d ]中的每个输出链路上发送 DFIND 消息 1②在每个中间结点 , 采用受限扩散方式 , 最多选取 K 条输出链路转发 DFIND 消息 , 直到选定的目的结点被连入 Dtree 树中 , 或者是因不能满足延迟条件或无可用波长而终止 1在中间结点 v , 选取到达目的结点 d 的输出链路的标准是到达 d 的最小延迟 1vw 的评价函数为f (w = D EL A Y (v -w Y (s (v , c v (v w ≤ Δ, ∞ , 1(7③当 DFIND 消息第 2次到达一个结点时 , G enDtree 采取下述方法处理重复的消息 :・如果本结点先前收到过 DFIND 消息 , 并且当前收到的 DFIND 消息与先前的 DFIND 消息来自不同的输入链路 , 则在两条输入链路中选择具有较长输出延迟(离开延迟的链路从树中删除 1・如果本结点的一个或多个子结点及其链路已经由先前的 DFIND 消息加入到树 Dtree 中 , 但当前的 DFIND 消息没有选择它们加入到 Dtree 中 , 则 G enDtree计算到这些邻结点的延迟以决定是否将它们保留在 Dtree 中 1决定取舍的标准是新的延迟 (当前 DFIND 消息计算结果是否比原延迟小 1当 Dtree 的一条旧链路被确定删除时 , 该链路以后的子树一同被删除 1④每个成功加入到 Dtree 的目的结点向源结点发送一个 DFOUND 消息 , 以通知源结点当前的进展状况 1(2 G enDtree 的波长分配策略①如果所选择的链路已经是 Ctree 的一条链路 , 则使用在 Ctree 中已分配的波长 ;②如果所选择的链路已经是 Dtree 的一条链路 , 则可以根据需要重新分配波长 ;③如果所选择的链路是一条新链路 , 则按 G enCtree 的分配策略进行分配 1415 Ctree 和 Dtree 的合并Ctree 和 Dtree 建立之后 , 需要将它们合并为一棵单一的树 1源结点 s 沿 Ctree 和 Dtree 的所有链路发送一个 M ER GE 消息开始合并操作 , 该消息被逐结点地进行处理 , 直到到达目的结点 1合并算法可简述为 :①如果 Ctree 和 Dtree 在结点 x 相交 , 并且分属于 Ctree 和 Dtree 的输入链路不同 , 则去掉 Ctree 的输入链路 1Ctree 中 x 的所有后继结点重新计算延迟时间 ;②如果沿合并的新树的路径不满足延迟条件 , 则算法失败终止 ;, 则 Ctree 中 , 直到到与 Dtree 的相交结点 1结论 11所构造的树包含源结点和所有目的结点 , 并且满足约束条件式 (4 , 同时具有接近最小的成本 1证明 1显然 , 所构造的树包含源结点和所有目的结点 1算法的每一步往树中增加一条链路及对应的对端结点 , 从源结点 s 到新增加结点的路径延迟不超过延迟时限 1所以从源结点到达每个目的结点的路径延迟都满足延迟约束条件式 (4 1由于 G enCtree 每次增加一条最小成本的路径到树中 , 因此每次加入到树中的是从树到目的结点的最小成本路径 1只有 G enDtree 增加的路径不具有最小成本 , 根据 Prim 算法可知 , 总的成本接近最优 1如果初始波长或者波长分配策略选择不当 , 可能会导致大量的波长转换 , 从而可能导致路径延迟超过时限 1尽管本算法在可能时试图替换部分链路或路径 , 但因为它并不为已经构造的部分树重新分配波长 , 因此仍然有可能最终不能构造出一棵满足要求的树 1当进行 Ctree 和 Dtree 的合并时 ,Ctree 的一些链路可能会被删除 , 这可能导致合并后的树无效 , 而算法并没有试图为删除的目的结点寻找候选路径 1因此存在着虽然有解但找不到解的可能 1但由于算法使用的是启发式方法 , 即选取最少转换和最小负载的方法为链路分配波长 , 因此上述情况通 764110期黄传河等 :WDM全光网络中实时组播的分布式路由与波长分配算法常可以避免 1证毕 1结论 21算法的通信复杂性是 O (n 1证明 1在 G enCtree 的路由选择过程中 ,CFIND , CFOUND 等消息的总数分别不超过 O (n , 最坏复杂性为 O (n 1在 G enDtree 中 ,DFIND 消息是以并行扩散方式传输的 , 最大消息数也是 O (n 1这样消息总数为 O (n , 所以通信复杂性不超过 O (n 1证毕 15模拟结果本文在模拟时 , 网络规模固定为 200个结点 , 网络拓扑随机生成并测试 , 直到生成一个连通的网络为止 1每条链路假定只有一根光纤 , 具有波长转换器的结点数为 50%且随机分布 1链路成本为 1~15之间的随机数 , 链路延迟为 1~10之间的随机数 , 光纤链路上的波长数为 81除非特别情况 , 假定 |D |为网络规模的 20%, 链路上波长的平均可用性定为 50%, K =11网络拓扑在模拟过程中保持不变 1本文模拟 3个算法进行比较 :SPT , MST 文提出的算法 dRWA 1SPT 和进行计算 , 成本 , D |组播连接建立时间 , 针对 |D |; , 针对波长可用性 1图 1说明了组播树成本与延迟时限Δ之间的关系 1SPT 和 MST 的曲线为常数 , 因为二者都不受Δ影响 1本文算法的曲线介于二者之间 , 其高端接近于 SPT 曲线 , 低端接近于 MST 曲线 1当Δ越小 , 越多的 MST 路径违反Δ限制而用 SPT 路径代替 1使得构造的树更宽 , 组播树成本就更高 1随着Δ的增加 , 更多的目的结点通过MST 路径连入树中 , 导致树的成本下降 1当Δ足够大时 , 不会影响路由选择 , 最终的组播树变成 MST1图 1不同Δ时的成本图 2说明树的成本与目的结点集大小间的关系 1当目的结点增加时 , 组播树包括更多的目的结点 , 导致树的成本增加 1SPT 曲线在其他两个曲线之上并上升得更快 1这是因为 SPT 不考虑路径共享 1本文算法的性能接近 MST , 二者的曲线随目的结点集的增大而增加得非常缓慢 , 因为目的结点集大 , 共享路径的可能性就大1图 2不同 |D |时的成本图 3说明树的成本与波长可用性之间的关系 1当波长可用性增大时 , 每条链路上有更多的可用波长 , , 进行波 , 降 1, (214个可用波长 , 组播树的成 1也就是说 , 当网络的负载不超过 70%时 , 路由选择与波长分配受负载影响较小1图 3不同波长可用性的成本图 4不同转换延迟的成本图 4说明树的成本与相对转换延迟之间的关系 1相对转换延迟是指波长转换时间与全网的平均链路延迟的比值 1结果显示 , 用 SPT 及本文算法构造树的成本随相对转换延迟的增加而非常缓慢地增加 ,MST 树的成本是常数 1本文算法的曲线几乎与8641计算机研究与发展 2003年10 期黄传河等 : WDM 全光网络中实时组播的分布式路由与波长分配算法1469 MST 曲线重合 , 说明当延迟时限给定之后 , 转换延迟时间主要影响建立连接的成功率 , 而对组播树成本的影响较小1 增大相对转换延迟的效果类似于减小延迟时限Δ1 图 5 说明建立连接时间与目的结点集大小之间图5不同| D | 的建立时间选择与波长分配的影响 ,并且是完全分布式的1 对于 WDM 网络中波长转换器只有部分波长转换能力的情况本文没有考虑 , 对此需要做进一步的研究1 参考文献1 Bin Wang , J C Hou1 Multicast routing and its QoS extension : (1/ 2 : 22~36 2000 , 23 (9 : 848~862 works , 2000 , 4 : 260~265 414~424 cations , 2001 , 49 (2 : 341~350 networks1 In : Proc of t he 9t h ICCCN , 20001 621~624 IEEE Communications Magazine , 1999 , 37 (2 : 67~73 X Jia , D Du , X Hu et al 1 Optimization of wavelengt h assignment 的关系1 建立时间是指最长路径上各链路的链路延迟时间的总和 ,没有计算波长转换时间1 当| D | 增大时 , 建立时间随之增大1 因为 D 是随机产生的 , 可能分布在全网范围 , 因此建立时间的增长速度远小于| D | 的增长速度1 2 3 4 5 6 图6 说明相对转换次数与波长可用性之间的关系1 相对转换次数是指总的波长转换次数与树中链路总数 ( 即所用波长的总数的比值 , 也就是平均链路 ( 即波长的转换次数1 当波长可用性增大时 , 每条链路上的可用波长增加 ,波长转换就会减少1结果显示 ,本文算法所进行的波长转换比 MST 少 , 但比 SP T 多1 当波长可用性很低时 , 需要进行波长转换的概率非常高 ,波长转换的累计时间会显著增加 ,因此会导致建立连接失败的概率增大1 7 8 图6不同波长可用性的波长转换次数 6结论本文提出了一种在 WDM 网络中建立实时组播连接的方法 ,该方法构造一棵满足延迟时限并具有接近最小成本的组播树 , 同时为树中的每条链路分配光纤与波长1该方法考虑了波长转换时间对路由 © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. J Spat h1 Dynamic routing and resource allocation in WDM trans2 port networks1 Computer Networks , 2000 , 32 (4 : 519~538 signment met hod for minimal wavelengt h conversions in WDM ing for improved performance in wavelengt h2routed networks1 cal networks1 IEEE/ ACM Trans on Networking , 1999 , 7 ( 3 : Deying Li , Xiufeng Du , Xiaodong Hu et al 1 Minimizing number for QoS multicast in WDM networks1 IEEE Trans on Communi2 L H Sahasrabuddhe , B Mukherjee1 Light trees : Optical multicast2 R K Pankaj1 Wavelengt h requirements for multicasting in all2opti2 X Jia , Ding2zhu Du , Xiao2dong Hu et al 1 A new wavelengt h as2 of wavelengt hs in multicast routing trees in WDM networks1 Net 2C P Low , Y J Lee1 Distributed multicast routing wit h end2to2end delay and delay variation constraints1 Computer Communications , Problems , algorit hms and protocols1 IEEE Network , 2000 , 14 黄传河 ,1963 年生 , 教授 , 博士生男导师 ,主要研究方向为计算机网络、分布并行处理、量子计算1 陈莘萌 ,1939 年生 ,教授 ,博士生男导师 ,主要研究方向为分布并行处理、新型计算机理论1 贾小华 ,1962 年生 ,教授 ,博士生男导师 ,主要研究方向为计算机网络、分布式系统1 。
一种公平的多优先级WDM光网络波长分配算法刘凤洲;潘炜;罗斌;孟超【摘要】文章研究了波分复用(WDM)光网络中动态业务下的波长分配问题,在无波长转换器的条件下,提出了一种加入了公平性考虑的动态门限算法.该算法在支持多优先级的动态门限法的基础上,通过更新初始优先级减少了不同距离光路连接请求间的阻塞率差别,改善了公平性.计算机仿真结果说明了该算法的有效性.【期刊名称】《光通信研究》【年(卷),期】2007(000)002【总页数】4页(P1-3,41)【关键词】波分复用;波长分配;公平性【作者】刘凤洲;潘炜;罗斌;孟超【作者单位】西南交通大学,信息科学与技术学院,四川,成都,610031;西南交通大学,信息科学与技术学院,四川,成都,610031;西南交通大学,信息科学与技术学院,四川,成都,610031;西南交通大学,信息科学与技术学院,四川,成都,610031【正文语种】中文【中图分类】TN929.11波分复用(WDM)技术以其传输容量大、对高层协议和技术适应性强、易于扩展等优点而备受青睐[1] 。
采用路由选择和波长分配的WDM光传送网被认为是下一代高速广域骨干网的最有竞争力的候选者。
路由和波长分配(Routing andWavelength Assignment ,RWA)是WDM光传送网中的重要问题,其主要任务是在光路请求的源节点和目的节点间找到一条最优路由,并在该条路由上分配波长。
由于实时和多媒体等新兴业务的出现,使得到达节点的光路建立请求可能对应不同的上层业务。
不同业务对应的光路建立请求应有不同的阻塞率要求,因此有必要将光路建立请求分成不同的优先级来处理。
文献[2]提出了一种支持优先级的波长分配算法——动态门限法,但是这种算法并没有考虑网络公平性。
所谓公平性[3~4]指的是长跳光路与短跳光路的阻塞率差别应该尽可能地小。
在WDM网络中,因为距离远的节点间的通路经过的链路多,只有这些链路同时有相同的波长空闲时才能连通,所以距离越远,节点间的阻塞率越高。
wdm波长范围摘要:一、引言二、wdm 技术的背景和基本原理三、wdm 波长范围的定义和分类四、wdm 波长范围的选择和应用五、wdm 技术在我国的发展现状及前景正文:wdm(Wavelength Division Multiplexing,波分复用)技术是一种光纤通信技术,通过将不同波长的光信号在同一光纤上传输,从而提高光纤的传输容量和传输速率。
wdm 技术已经成为光纤通信领域的重要技术之一,广泛应用于各种光纤通信网络中。
wdm 波长范围是指在wdm 技术中可以使用的波长范围。
根据国际标准,wdm 波长范围通常分为C、L、U 三个区域,其中C 区波长范围为1260-1360 nm,L 区波长范围为1530-1565 nm,U 区波长范围为1870-2000 nm。
此外,还有一些特殊的波长范围,如O 波段(1260-1360 nm)和C+L 波段(1530-1565 nm)。
wdm 波长范围的选择主要取决于所需传输容量、传输距离、光纤类型和光源类型等因素。
在实际应用中,通常会选择多个波长进行复用,以实现更高的传输容量和传输速率。
例如,DWDM(Dense Wavelength Division Multiplexing,密集波分复用)技术可以在同一光纤上传输100 多个波长,从而实现Tb/s 级别的传输速率。
近年来,wdm 技术在我国得到了快速发展,已经在长途光纤通信网络、城域光纤通信网络和数据中心等领域得到广泛应用。
我国光纤通信网络的规模和容量也在不断壮大,为wdm 技术的进一步发展和应用提供了广阔的市场空间。
总之,wdm 波长范围是wdm 技术中的一个重要概念,其选择和应用直接影响到光纤通信网络的传输容量和传输速率。
2004年4月第9卷 第2期 西 安 邮 电 学 院 学 报JOU RNA L OF XI 'AN U NI VERSIT Y O F POST AN D T ELECOM M UN ICAT IO NS A pr .2004V ol .9N o .2收稿日期:2003-08-09作者简介:康巧燕(1980-),女,福建永春人,空军工程大学电讯工程学院硕士研究生。
李维民(1960-),男,陕西西安人,空军工程大学电讯工程学院副教授。
种满东(1978-),男,陕西紫阳人,西安电子科技大学电子工程学院硕士研究生。
WDM 波长连续光网络中路由和波长分配算法研究康巧燕1,李维民1,种满东2(1.空军工程大学电讯工程学院,陕西西安 710077;2.西安电子科技大学电子工程学院,陕西西安 710071)摘要:在对W DM 波长路由光网络的路由和波长分配算法进行研究的基础上,提出一种新的自适应动态路由算法和考虑通道优先级及波长容量损失的波长分配算法,并给出具体分析及实现步骤。
该算法能有效地利用网络资源,保证负载分布的平衡,并能较好地兼顾网络资源分配的合理性。
关键词:光传送网;路由和波长分配;光通道;相对容量损失中图分类号:T N 913.7 文献标识码:A 文章编号:1007-3264(2004)02-0089-04引言在WDM 光传送网中,给定一组全光连接请求条件下,寻找源节点到目的节点的路由并给这些路由分配波长的问题称为路由和波长分配(RWA ,Routing and Waveleng th Assignment )问题。
WDM 光网络的一个核心问题就是如何选择有效的算法和协议来建立光通道,也就是如何解决RWA 问题。
在考虑到技术条件和网络建设成本的条件下,设计出一个好的RWA 算法,对减少网络阻塞概率、光通道通信所需的波长数,提高资源利用率及网络抗毁能力具有重要意义。
本文对WDM 波长路由光网络的RWA 算法进行了研究和总结,在此基础上,提出一种新的自适应动态路由算法和考虑通道优先级的波长分配算法。
试阐述WDM 网络中波长转换理论作者:朱和平来源:《建筑建材装饰》2014年第05期摘要:本文首先简要介绍了WDM网络的发展情况和研究波长转换算法的重要意义,接着总结了前人在波长变换算法的研究成果,然后与以前的理论结果相结合,提出了两个有关的波长转换问题的定理,给了详细的证明,最后总结全文,并确定下一步的研究方向。
关键词:波分复用WDM;波长转换前言自20世纪90年代以来数据业务(电子信函、会议电视、点播电视、传真等)爆炸式地增长,计算机互联网(Internet)的流量迅猛增长,人们对网络带宽和容量的需求持续稳定地增长。
WDM正是适应这种需求而迅速发展起来的。
到了上世纪的九十年代末,以掺铒光纤放大器EDFA(Erbium- Doped Fiber Amplifier)为代表的光纤放大技术和以阵列波导光栅AWG (ArrayWaveguideGrat-ing)为代表的复用与解复用器件的实用化促使波分复用技术WDM (Wavelength Division Multiplexing)和密集波分复用技术DWDM(Dense Wavelength Division Mul-tiplexing)开始商用化,形成了网络中WDM层,第二代光网络也随之走向成熟。
在今天,全光网络正在成为一种很有前途的解决方案,以满足迅速增加的带宽需求。
全光网络部署光交换机,以避免光电转换的瓶颈;使用波分复用技术,以将光带宽分为不同的信道。
两个结点之间的连接可以通过一条光纤在上面传输不同波长信道的数据。
部署在网络中某些结点上的波长转换器可以改变经过它的光信道上的波长,以此充分利用网络的可用容量。
图1展示了波长转换器的模型。
在全光网络中出现了不少值得研究的算法问题。
其中波长转换问题越来越受到研究人员的关注。
波长转换问题指,给定一组从源点到目的结点的路径,如何分配最小数目的波长给这组路径并且不产生波长冲突。
若使用了波长转换器,当经过该波长转换器时,一条路径上的波长可以转换到另一个波长。
WDM 光传送网的选路和波长分配算法为了克服电处理的速率“瓶颈” ,宽带网络向光网络发展。
目前,光突发交换、光分组 (包)交换正在积极研究中,但是距商用还较远。
已可商用的是具有光分插复用器(OADM,OpticalAdd - DropMultiplexer) 和光交叉连接器(OXC,OpticalCross- Connect)的波分复用(WDM)网络。
由于是提供可调度的传送用光路,称这种网络为 WDM 光传送网(OTN,OpticalTransportNetwork) 。
1 网络结构图 1 是网络物理结构的一个例子,虚线内为光传送网。
图中有 5 个 OXC:A,B,C,D,E;5 个具有光接口的电设备: S1〜S5; 6个将OXC相连的物理链路:11〜16。
一般一条物理链路包含一对光纤供双向运用,有的OXC间没有物理链路相连。
但更多的情况是一条物理链路包含多根光纤供不同方向运用。
一根光纤上可采用多个波长。
一般情况下,OXC不直接和电设备相连,只起光交叉连接作用。
OXC可分为无波长变换和有波长变换(也可以是部分端口有波长变换或波长变换的范围有限 )两种:无波长变换的OXC的作用是将一根输入光纤上的某一波长信号连到另一根输出光纤的同一波长上,即波长是连续的;有波长变换则是将一根输入光纤上的某一波长信号连到另一根输出光纤的另一波长上。
适当地安排路由和分配波长,可为电设备间建立光路 (opticalpath) 。
在一根光纤上,不能为不同光路分配相同波长。
图2(a)为图1建立的光路例子。
将图 2(a)的光路连接用图2(b)来表示,称为逻辑结构,也称逻辑拓扑或虚拓扑。
例如,图2(a)中,节点B与E间的光路是经节点 A中的OXC 转接的,在图2(b)中用04表示。
图2(b)中,06、04、01都是中间有 OXC转接的。
02、03、05是直接光路。
这样建立的光路对信号是透明的,即信号可以是任意方式。
实际设计中,一种需求情况是:提出所需建立的光路,为这种光路选取物理路由并分配相应的波长 [1,2]。
例如,图 2(b)中提出要建立6条光路,图2(a)就是一种选路和波长分配方案。
网络向分组化发展,图1中的电设备可以是 ATM交换机或 IP 路由器。
例如,连在端口 B2 的路由器可以通过光路 06 和连在端口 C3的路由器相连。
B2到C3可有多条路径,06 是最近的,也可以经过 04— 05— 03或04— 05— 01—02连接,但需要路由器转接,即电的多跳连接。
A与B间没有光路,至少需经 C 电跳连接一次实际设计中另一种需求情况是:提出各路由器间的所需业务量强度;设计出逻辑拓扑并为其光路选取物理路由和分配波长 [2-4]。
与根据光路需求情况进行设计相比,增加了要考虑电的多跳。
下面分别叙述两种需求情况下的选路和波长分配 (RWA) 算法。
2 基于光路的 RWA 算法光路需求的提出有 3 类:静态的、递增的和动态的。
静态RWA 问题是预先给出多条光路连接需求,计算路由和分配波长。
这种计算可以是离线(off— line)的,即不需要实时计算。
在递增情况,光路需求逐条地提出,需要为每一条作实时在线 RWA 计算。
光路数增加到一定值后,就不再增加。
对于动态情况,光路需求逐条地提出,但一条光路持续一段时间后又被拆除,要为每一条作实时 RWA 计算。
这里所谓的动态,实用中常是缓慢变化的,例如几小时甚至几天才有一次新的需求。
后两类情况的 RWA 算法常相同,只是性能评价指标不同,将在 2.2 节合在一起叙述。
2.1基于光路的静态 RWA算法基于光路的静态 RWA 算法是给定多条光路的连接需求和物理拓扑后为每条光路选取路由并分配波长。
设计时的优化目标可以是使所用的资源如波长数最小。
这个优化问题可用整数线性规划法求解[1]。
若OXC无波长变换,则将波长连续作为约束条件。
这个问题的反过来是在一定的波长数下使连接的光路数最大。
这种优化方法的复杂性随网络规模的增大而急剧增加,因此,工程上常将RWA 问题拆成选路子问题和波长分配子问题,分两步求解。
( 1 )为每条光路选取路由选路方案有两类:固定路由和备用路由 (alternaterouting) 固定路由是为每条光路选取一条固定的路由。
通常可用熟知的最短路径算法。
但是,最短路径算法的缺点是有时会使网络中某些部分过于拥挤,即某些光纤上经过的光路数过多,在波长数有限情况下会造成波长不够分配。
改进的方法是采用能使负载平衡的选路算法。
可以采用整数线性规划的优化方法使网络中一根光纤上的光路数尽量小,这为减小波长数创造了条件,但这种方法在网络规模较大时较复杂。
为此,可采用使网络负载平衡的启发式路由算法。
启发式算法是根据概念推出的优化算法,能得到较优的结果,但不一定最优。
例如,可以按某种合适次序逐条地为光路选取路由,每一条均采用某种优化的动态路由算法[5]。
备用路由是为每条光路选取多条路由,最简单的方法是选取k 条最短路径。
为多条光路的一组路由分配波长时,若发生波长数不够用,则通过置换备用路由构成另一组路由,再分配波长,直到完成要求。
如何从备用路由集选择合适的路由也是需要考虑的 [2] 。
(2)分配波长若OXC没有波长变换,则波长分配的约束条件是每条经 OXC连接的光路应是波长连续的,并且在一根光纤上不同光路需分配不同波长,优化目标是使采用的波长数量最小。
这个问题可以转化为一个辅助图G(V,E的着色问题[1],V为节点集,E为边集。
V中的每个节点相应于一条光路,这条光路如果和某些其他的光路处于同一根光纤内,则相应的节点间就有边相连。
波长分配相当于为 G 的节点着色,约束条件是相连的节点不能采用同一颜色,优化目标是使采用的颜色数最小。
这个着色问题已有有效的算法 [1] ,但较复杂。
为了简化,可以采用一些启发式算法,对多条路由逐条分配波长。
2.2基于光路的动态RWA算法对于上面讲过的递增情况,在给定的物理拓扑和最大波长数条件下,要为每一条新增光路选取路由并分配波长,优化目标为被拒绝(由于波长数不够)的百分比(相对于总增加数)尽量小;对于动态的连接请求和拆除情况,优化目标为被拒绝(或称阻塞)的概率尽量小。
这两类情况的RWA算法是在线的,当网络规模较大时,为了减小复杂性,常将选路和波长分配分两步进行;当网络规模不太大时,可以采用分层图的方法将选路和波长分配合在一起考虑[6] 。
若首先进行选路,可分为 3 类:固定路由、备用路由和自适应路由(自适应路由也可纳入前两类中,即只分成两类)固定路由通常采用最短路径。
备用路由可采用多条最短路径,在首条路由上波长资源不够时,换一条再试,与固定路由相比减小了阻塞率。
采用最短路径的缺点是有时会使网络中某些部分过于拥挤,阻塞率加大。
改进的方法是采用自适应路由[1] ,在每次选路时,根据网络的状态,使各条光纤上的光路数尽量平衡。
选定一条路由后,要为它分配波长,有多种方法 [1,2] 。
第一种方法是从该路由上已建光路所使用的波长之外,随机地另选一个波长,称为随机波长分配算法(R 算法);第二种是将波长编号,从低到高依次观察是否已在该路由上建光路使用,首先找到的波长就被使用,称为首先适合算法(FF)。
仿真表明,采用FF算法的阻塞率比采用 R算法时小。
R和FF 算法只考虑一条路由上的局部情形,还有一种最大-总数算法(Max - Sum)[1,2],其思路是按分配波长后网络中仍可容纳的光路数最大为目标来分配波长。
采用 Max - Sum算法的阻塞率优于FF算法(但有时差别不大),代价是增加复杂性。
文献 1 还叙述了其他8种波长分配算法。
对于将选路和波长分配分两步进行的算法,仿真表明,影响阻塞率的主要是选路算法。
好的选路算法会显著地减小阻塞率,而各种波长分配算法的性能差别不大。
因此,在工程上可采用一种自适应路由算法加简易的FF波长分配算法。
采用分层图(layered - graph)的方法可以将选路和波长分配一步完成⑹。
OXC中的光开关是空间域的连接,波长分配是频率域的连接,从提供通道的角度看,空域和频域的作用是一致的。
分层图将空域和频域结合起来,绘出一张新的通道图,动态RWA问题成为在分层图中选取一条通道的问题。
各种动态选路的算法都可考虑,目标是使阻塞率最小。
仿真表明,采用较好选路算法的分层图法比将选路和波长分配割裂的方法阻塞率小。
3基于运送分组业务的 RWA算法图 1 所示是电设备(例如路由器或 ATM 交换机)通过光路进行连接。
可以将所有的光路部分称为光层,其中有光交叉连接。
如果光路已经给定,则分组业务运行遇到的是一般的选路问题,但是实用中会遇到给定各分组通信设备间的业务量矩阵,要设计光路结构(称为逻辑拓扑或虚拓扑)的问题 [2 - 4,7]。
对于电设备来说,最好是各自间都建有一条光路,但是,这样设计不经济。
有的电设备间的连接可以经过其他的电设备转接,从而节省光路,图2(b)中A与B间就没有光路。
基于运送分组业务的选路和波长分配(RWA)算法是根据运送分组业务的需求来设计网络,也可分为静态和动态两种。
3.1基于运送分组业务的静态RWA算法基于运送分组业务的静态选路和波长分配(RWA)算法是在给定物理拓扑和各分组电设备间的业务量矩阵情况下设计网络,使网络性能和经济性尽量好。
从理论上说,优先目标一直要考虑所用的光纤数最小,使用的波长数最小等问题,但是这样经常很复杂。
可将问题割裂分为几步考虑,首先进行虚拓扑设计[3,4],再为虚拓扑中的光路进行选路和分配波长,最后可能反过来对第一步设计进行调整。
在设计中,也可以将光路的选路放在第一步中。
3.2基于运送分组业务的动态RWA算法在IPoverWDM网络中,可以采用MPLS侈协议标记交换)技术来实现业务量工程,解决有效利用网络资源和保证 QoS(服务质量)的问题。
在MPLS网络中,需在线建立保证带宽的路径,最好的解决方法是采用综合的动态IP与波长选路算法[8]。
这种算法是将IP网络的QoS路由技术进一步推广到IPoverWDM 网络。
4RWA设计中要考虑的附加问题上面从概念上说明了有关 RWA算法。
最基本的情况是采用无波长变换的 OXC,即对一条经OXC构成的光路有波长连续性限制。
下面对引入波长变换、抗毁、服务策略等问题作概要叙述。
4.1波长变换问题引入波长变换可使在一条光路上分配波长时更灵活,动态建立光路时阻塞率减小。
引入波长变换与无波长变换相比的得益程度与具体情况有关,有时明显,有时并不明显。
波长变换器价格较贵,而且技术上有限制。
文献 2 中研究了各种不同的配置情况:网络中只有少数节点配置有完全波长变换的OXC,称为稀疏波长变换; OXC只有部分端口具有波长变换;波长变换范围有限,如只能在几个波长间变换。