收稿日期:2008-05-31
基金项目:国家高技术研究发展计划项目(2003AA781011);辽宁省自然科学基金资助项目(20072022)·作者简介:杜 荔(1962-),女,辽宁沈阳人,东北大学副教授·
第30卷第4期2009年4月东北大学学报(自然科学版)Journal of Northeastern University (Natural Science )Vol .30,No .4
Apr .2009
ASON 中一种新的动态路由和波长分配算法
杜 荔,孟艳楼,毕晓红
(东北大学信息科学与工程学院,辽宁沈阳 110004)
摘 要:在A SO N 中的网络节点不具备波长变换能力且光纤中复用的波长数有限的情况下,针对为到达的业务请求动态选路和波长分配问题,提出了一种新的动态路由和波长分配算法(N -RWA )·该算法中设计了一种同时考虑节点跳数和当前网络状态的合理适应度函数,并将遗传算法和最小影响波长分配算法相结合,实现对传统RWA 算法的改进·仿真结果表明,与传统的RWA 算法相比,N -RWA 算法在保证全网业务负
载均衡的同时,大大降低了网络阻塞的可能性·
关 键 词:自动交换光网络;路由和波长分配;最小影响;遗传算法;进化代数
中图分类号:T N 915 文献标识码:A 文章编号:1005-3026(2009)04-0518-04
A New Dynamic Routing /Wavelength Assignment Algorithm in AS ON
DU Li ,MENG Yan -lou ,B I Xiao -hong
(School of Info rma tio n Science &Engineering ,N ortheastern U niversity ,Shenyang 110004,
China .
Correspondent :D U Li ,E -mail :duli @ise .neu .edu .cn )
A bstract :Considering the conditions that the nodes are unable to convert the w aveleng th and that the number of multiplex wavelengths is limited in optical fibres ,a new routing /w aveleng th assig nment (N -RWA )algorithm is proposed to solve dynamically the routing and w aveleng th assig nment problem for the arrival of service request .In the new algorithm a rational fitness function is designed taking account simultaneously of the number of hops in a lightpath and the current netw ork conditions and the genetic algorithm is in combination with least influence w aveleng th assignment algorithm ,thus improving the conventio nal RWA algo rithm .Simulation results showed that N -RWA can significantly reduces the blocking probability in com parison w ith the conventional RWA algorithm w ith balanced load kept o n in the w hole netwo rk .Key words :ASON (automatically sw itched optical netw ork );routing /wavelength assig nment ;least influence ;genetic algorithm ;evolution generation 自动交换光网络(ASON )是在信令网控制之下完成光传送网内光通道连接和自动交换功能的新型网络[1],代表未来网络技术的发展方向·而RWA 问题是指当一个连接请求到来时,为连接请求计算路由并分配波长的问题,是ASON 中的关键技术之一[2]·针对不同的业务特性和连接请求方式,RWA 问题的研究主要分为静态和动态RWA 问题[3]·由于RWA 问题是NP -C 问题,因而为降低问题复杂度,一般将RWA 问题分为路由问题和波长分配问题来研究[4]·
当前路由选择策略包括固定路由(fixed routing ,FR )、固定可选路由(fixed alternate
routing ,FAR )和自适应路由(alternate routing ,
AR )[5]·波长分配算法主要有首次命中(
first fit ,FF )、最小负载(least loaded ,LL )、最小影响(least influence ,LI )、相对容量损失(relative capacity loss ,RC L )等·在ASON 智能光网络中,静态RW A 算法通常是在建网初期对静态网络业务的规划方法,一般可采用整数线性规划方法实现[6]
·而动态RWA 算法通常是在网络运行期间对动态网络业
务的规划方法,其算法的优化目标通常是尽量减小网络的阻塞概率[7]·
文献[8]针对静态RWA问题讨论了波长优化问题,但其算法只是考虑到了静态路由的情况,没考虑在实际应用中动态路由和波长分配所带来的复杂性·文献[9]设计了一种新颖的遗传算法来解决动态的路由和波长分配问题,但它在设计适应度函数时只考虑了路由的跳数,因而很容易造成全网负载的不均衡·本文提出的N-RWA算法将遗传算法和最小影响波长分配算法相结合,并在设计时充分考虑了节点跳数和当前的网络状态,有效地降低了阻塞率,均衡了网络负载,从而可以更好地达到应用于ASON光网络的目的·
1 算法模型描述
本算法中:L代表网络中的链路总数目; L(p)代表通路p上的所有链路集合;L ch(l,λ)代表链路l在波长λ上的剩余信道数;P ch(p,λ)代表任意通路p在波长λ上的可用信道数,如果L ch(l,λ)=P ch(p,λ),称l为通路p的瓶颈;P＊代表新到达的业务请求对应的路由;A(P＊)代表通路P＊上的可用波长集;G(P＊)代表与P＊有共享链路,且仍具有可用信道的通路集合,并且可用信道数目总数不小于1,相当于P＊的邻域·
P ch(p,λ)=min l∈L(p)·(1)最小影响算法的优化目标为
min λ∈A(p＊)∑
p∈G(p＊)∑
l∈L(p)∩L(p＊)
D(L c h(l,λ), P ch(p,λ))·(2)定义1 选取满足式(3)的路由和波长分配给新到达的业务:
R p(P＊,λ)=∑
l∈L(p)∩L(P＊)
D(L ch(l,λ),
P ch(p,λ))·(3)式中:R p(P＊,λ)表示当波长λ分配给P＊时,对P＊与通路p共享链路的影响;D(A,B)代表指示函数·当A=B时,D(A,B)取值为1;否则, D(A,B)取值为0·
定义2 N-RWA算法中染色体编码:A b= (P i,H ij,λm),b=1,2,…,n·P i中i为新到达的业务请求对应的备用路由的个数,P i∈P＊;H ij中j表示与通路P i有共享链路且仍具有可用信道的通路数目,H ij∈G(P＊);λm中的m表示通路P＊的可用波长数目,λm∈A(P＊)·染色体中(P i,λm)为RWA问题的一个可行解·
定义3 N-RWA算法中适应度函数:
f=
1
h+α×R p(P＊,λ)·
(4)式中:h表示通路P＊的跳数;0<α<1·
适应度函数综合考虑了节点跳数和网络中最小影响,作为优化目标函数,减小网络的阻塞率·N-RWA算法的目标是选取适应度值最大的(P i, H ij,λm)作为算法的优化目标·
定义4 算法中初始群体大小为n,最大遗传进化代数为g·群体规模越大,群体中个体的多样性越高,算法陷入局部解的危险性就越小·
2 N-RWA算法描述
2.1 查找路由
利用ksp-disjoint路由算法查找出任意两点间的路由k条[10]·某条动态连接请求到达时,从路由计算得到的路由集中找到与此相关的路由集P i,在网络中找到与路由集P i有相关链路的路由集合G(P＊)·
2.2 创建初始种群
将可用波长随机分给路由P i,按照编码规则(P i,H ij,λm)形成初始种群·种群规模的大小不仅决定了初始解的多少,而且确定了每代运算的搜索空间,因此直接影响着最优解的质量·种群规模越大,其最优解的质量也就越好;但是种群规模太大,会使算法的运算时间大幅增长,使得不具备实际效用,太小则难以求出合理解·在种群中随机产生一定数量的个体,然后从中挑出较好的个体构成初始群体A,A中的数目为I·
2.3 选择最优个体
采用最佳个体保存法(elitist model)[11]和适应度比例法(fitness propo rtional model)相结合的选择方法,即在群体交叉、变异之前,先选出最佳个体,直接复制到下一代中,其余个体的选择采用比例选择法·
对于规模为I的群体A,个体a j的选择概率为
q=f(a j)∑
I
i=1
f(a i)·(5)式中:f(a j)为个体a j∈A的适应值;i=1,2,3,…,I·
这种随机选择策略确保低质量的个体能被选择用来产生新的个体,并且能够使过快收敛于某个局部最优解的危险性降低·
2.4 交叉操作
交叉操作在遗传算法中起到至关重要的全局
519
第4期 杜 荔等:ASON中一种新的动态路由和波长分配算法
搜索作用,交叉操作是在随机选取的两个染色体之间通过交换相同基因位完成的,其作用在于将原有的优良基因遗传给下一代个体,并生成包含更复杂基因结构的新个体·
根据这一特点,针对所研究的问题,采用染色体的单点交叉方式,选择染色体中的基因位λ作为交叉点,从群体中随机选择两个个体,并产生一个[0,1]区间均匀分布的伪随机数r c,若r c
p c,则不进行交叉操作,在每一代新的群体中,对p c×n%个染色体进行交叉操作·在交叉操作中,交叉概率越高,群体中新结构的引入越快,易于得到优良个体但也易于破坏优良个体;而交叉概率太低则可能导致搜索阻滞·
2.5 变异操作
变异概率是变异算子的核心组成之一,也是决定算法找到最优解能力的重要影响因素之一·适当的变异概率能够保证群体的多样性,防止遗传算法的过早收敛,从而得到更为合理和精确的解·在本文中设定对前两个基因位P i,H ij进行变异操作,基因位λm保持不变,变异操作分以下两个步骤进行·
1)计算个体发生变异的概率,以原始的变异概率p v(一般取为0.001～0.02)为基础,可计算出群体中个体发生变异的概率p v(a j)·产生一个[0,1]区间均匀分布的伪随机数r v,若r v
2)计算发生变异个体的基因变异的概率p′v:
p′v=
p v
p v(a j)·
(6)
变异操作的具体过程:对选中的个体基因位P i或H ij进行变异时,在P i或H ij对应的路由上任选一条链路并将其切断,再用Dijkstra方法得到新的路由,然后用新个体代替旧个体·在变异操作中,变异概率太小,可能使某些基因位过早丢失的信息无法恢复;而变异概率过高,则遗传搜索将变成随机搜索·
2.6 终止条件
最大遗传进化的代数为g,g是遗传算法运行结束条件的一个参数,它表示遗传算法运行到指定的进化代数之后就停止运行,并将当前群体中的最佳个体作为所求问题的最优解输出·本文
通过设置进化代数来终止算法的运行·3 N-RWA性能分析
为了验证算法的性能,对该算法进行了仿真,仿真时采用的拓扑如图1所示[12]·拓扑图中共有14个节点,21条链路,节点之间采用8根单向光纤进行连接,每根光纤复用的波长数为8个,每个波长带宽均采用2.5Gb/s,各条链路的代价如图1中所示·同时假设网点没有波长转换能力·仿真时设初始群体为30,最大进化代数为100,交叉概率和变异概率分别取0.5～0.99和0.001～0.02之间的数·
图1 仿真拓扑
Fig.1 Topology of sim ulation
在动态业务下,全网中的连接请求服从到达率为λ的泊松分布,即在某一时间间隔T内有k 个连接请求到达·光路建立后的服务时间服从均值为1/μ的负指数分布,连接请求随机分布在网络中各个节点上·如果有N个连接请求加载到网络中,那么业务负载是N×λ×μ(爱尔兰)·从图2中看出,随着进化代数的增加,适应度函数也逐渐变大,从而可以获得高质量的最优解·从图3
图2 进化代数对适应度函数的影响Fig.2 Influence of number of evolved generations
on fitness function
图3 不同算法的阻塞率比较
Fig.3Comparison of blocking probability
between different algorithm s
520东北大学学报(自然科学版) 第30卷
中看出,N -RWA 算法在阻塞率方面明显优于传统的最短路径距离(shortest path distance ,SPD )路由算法和最好适应(best fit ,BT )波长分配算法的组合·
4 结 论
遗传算法是一种全局性自适应的搜索算法,
非常适合解决NP -C 问题,本文正是利用了改进的遗传算法求解智能光网络中动态路由和波长分配问题·在算法设计上把遗传算法和最小影响波长分配算法有效结合,给出了考虑节点的跳数和网络状态的适应度函数,均衡了网络负载,因而与传统算法相比表现出了更好的性能·参考文献:
[1]
Zhu N ,S un H J .A distribu ted strategy for dynamic routing and w avelength assignment in ASON network [J ].IEEE Transparent Optical Networks ,2005,1(7):201-204.
[2]
Banerjee D ,M ukherj ee B .A practical app roach for routing and w avelength ass ignment in large w avelength -routed optical networks [J ].IEEE Jou rnal on Sel ected Areas in
Commu nicati ons ,1996,14(5):903-908.
[3]
Chu X W ,Li B .Dynamic routing and w avelength assignment in the presence of w avelength conversion for all -optical netw ork s [J ].IEEE /ACM Trans actions on Networking ,2005,13(3):704-715.
[4]
Ramaswami R ,
Sivarajan K .Routing and wavelength
assignment in all -optical networks [J ].IEEE /ACM Trans actions on Networking ,1995,3(2):489-500.
[5]
李
,金春慧,何荣希·一种实现负载均衡的波长选路算法[J ]·东北大学学报:自然科学版,2005,26(2):118-121·
(Li Zhe ,
Jin C hun -hui ,He Rong -xi .Efficient load
equalization rou ting algorithm [J ].Journal o f Northeaster n University :Natu ral Science ,2005,26(2):118-121.)[6]
W ang Y ,T ee H ,M eng H L .A tabu search algorithm for static routing and w avel ength assignm ent problem [J ].IEEE Com mun ication Letters ,2005,9(9):841-843.
[7]
Kim J ,Lee C ,Harsha S .Route -metric -based dynamic routing and w avel ength ass ignment for multifiber WDM networks [J ].IEEE Journa l on Selected Areas in
Comm unications ,2006,24(12):56-68.
[8]
Nina S ,M l aden K .Static routing and w avelength assignment in wavelength routed WDM networks [J ].IEEE Mel econ ,2006,5(16):692-695.
[9]
Bis bal D .Dynamic routing and wavelength assignment in optical netw orks by means of genetic al gorithms [J ].Photonic Network C omm unications ,2004,7(1):43-58.
[10]
赵太飞,李乐民,虞红芳·基于k -最短路由的mesh 光网络p 圈构造方法[J ]·计算机应用研究,2007,24(11):278-280·(Zhao Tai -fei ,Li Le -min ,Yu Hong -fang .New algorithm of finding good candidate cycles based on k -shortest -routing in optical mesh
netw ork [J ].App licati on
Res earch of
C omp uters ,2007,24(11):278-280.)
[11]
殷新春,杨洁·基于遗传算法的S 盒的构造[J ]·计算机应用研究,2007,24(3):91-93·(Yin Xin -chun ,Yang Jie .Construction of S -boxes based on genetic algorithm [J ].App lication Res earch of C omp uters ,2007,24(3):91-93.)
[12]
Indira S ,Vaidehil V ,S ubhashini A .Performance anal ysis of modified DORA for constraint based WDM networks [J ].IEEE C om munic a tions an d Networking ,2007,2(22):244-249.
521
第4期 杜 荔等:ASON 中一种新的动态路由和波长分配算法
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]。例如，图2(b)中提出要建立6条光路，图2(a)就是一种选路和波长分配方案。 网络向分组化发展，图1中的电设备可以是ATM交换机或IP路由器。例如，连在端口B2的路由器可以通过光路O6和连在端口C3的路由器相连。B2到C3可有多条路径，O6是最近的，也可以经过O4―O5―O3或O4―O5―O1―O2连接，但需要路由器转接，即电的多跳连接。A与B间
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
路由波长分配（RWA）算法的研究现状 班级：2010211117 学号：10210518 姓名：刘芷若 1. 前言 波分复用（Wavelength Division Multiplexing—WDM）网络利用了光纤传输链路的巨大带宽，随着WDM技术日趋成熟，WDM传输技术已经进入实用化和商用化阶段。WDM全光通信网是光纤通信未来发展的主要方向之一。由于光网络对传输信号的速率和格式透明，具有灵活的波长选路和动态资源配置能力，可以实现网络的动态重构，被认为是通信网络升级的首选方案。如何利用现有的和即将敷设的光纤连网，构成未来高速、大容量、多业务的WDM 网络已经成为光通信领域中的一个重大问题。WDM网络节点处采用光分插复用器（OADM）或光交叉连接设备（OXC）在光层建立光连接，即光通道（optical path），为高层的多个逻辑电网络提供了高速、大容量的信息传送平台。光通道的建立，要求在传送网的物理结构中选择一条由业务源点到宿点的路由，并为其分配一定的波长信道（参见图1.1）。考虑到波长资源的重利用以及提高网络的阻塞性能，优化光通道的选路和波长分配（Routing and Wavelength Assignment —RW A）方案成为光通道层设计的核心问题。RW A解决如何寻找一条合适的光通道并合理地分配通道所使用的波长，使有限的资源充分发挥作用，以提供尽可能大的通信容量。 2.RWA算法的分类 WRON被认为是构建下一代光网络的候选方案之一。但是由于网络资源有限(如波长数、收发器数目等)，不可能在网络中为每一节点对都建立一条直接相连的光路，因此针对不同的网络需求，需要考虑对现有可用资源进行高效利用和优化设计。WRON的核心问题是优化设计光路的选路和波长分配，寻找一条合适的光路并为之合理地分配波长，使有限的资源充分发挥作用，以提供尽可能大的通信容量。根据光通道连接请求的特点，可以把RWA问 题分成静态和动态两类。 (1)静态RWA(SRWA)问题：网络的业务类型是静态的，而且当所有连接建立好之后，连接将保持不变。光通道连接请求是预先给出的，因此要求离线计算路由和分配波长，而不需要实时计算。SR—WA问题的研究适合广域网(或骨干网)，因为对于广域网来说，其业务流量基本是确定的。SRWA的输出结果是所有的源一目的节点对之间的光通道的路由以及给这些光通道分配的波长。 (2)动态RWA(DRWA)问题：光通道连接请求是逐条提出的，而且一条光通道持续一段时间后又被拆除，因此需要为每一条光通道做实时RWA计算。对于DRWA问题，对光通道建立请求的处理通常有两种策略：可重构型策略和不可重构型策略。所谓可重构型策略，就是当网络拥塞发生的时候，光网络的逻辑拓扑可以进行重构，以消除拥塞情况。但是这样的操作可能会中断很多现有的连接，而且需要对网络节点之间的光通道进行大量的调整(拆除或者重新建立)，因此不适合大规模的网络。而不可重构型策略，则在拥塞发生的时候不能重构光通道，只能拒绝该请求。
波长分配方法 随着波分复用技术的应用，几个光信号可在单根光纤传输。这种技术可以更有效的利用光纤的巨大力量，但也带来了新的网络设计和管理问题，尤其是当波长转换节点中没有可能的。考虑在这样的网络中的路由和波长分配问题，一旦路线是固定的波长分配基本上是一个图着色问题。对于一个给定的图着色算法，在当前的研究中较主流的有贪婪算法，穷举搜索，模拟退火以及遗传算法。都是相当不错的路由和波长分配性能，本文主要介绍在路由选择确定的情况下的波长分配问题，且着重从贪婪算法和穷举搜索算法来讲述波长分配方法。 在本文中，我们集中在WDM网络路由和波长分配问题。当多个信号共享相同的纤维，他们必须使用不同的波长。现有的技术设置了一个上限的波长数。因此，我们认为，导致建立一个给定的连接在与最低数量的波长网络设置的问题。在制定的最优化问题，取决于是否有可能在波长转换节点或没有。如果波长转换的最佳解决方案是可能的只是最大限度地减少了使用的通道的链接的最大数量。路由问题是在正常的电路交换网络，在唯一的限制因素是对每一个环节通道数相同。 另一方面，如果波长转换不能在节点完成后，这便产生了优化问题新的约束。每个连接使用上沿线的各个环节相同的波长。一个可行的解决方案使用小于或等于各个环节的波长数比有可用的，没有两个连接共享一个共同的联系具有相同的波长。 也可以使用波长转换网络。在本文中不讨论这种网络，因此，我们假定波长转换不能在任何节点完成。我们还假设没有任何的网络动态重构的需要，即连接设置是静态的。 路由和波长分配问题是紧密联系在一起。我们首先要确定每个连接的线路（即路由），然后尝试使用最小数量的波长来进行波长分配。这样做，这样反复的进行着色尝试目的在于对路由连接不改变的同时使用最少的颜色来完成全图的着色。同时，在实践中以求找到比现有技术使用更加少颜色的着色方案。 在路由和波长分配过程是代表在图1。在左边是一个物理网络。中间的是固定路由波长分配图，右侧的图是图着色方案，其中的节点表示连接，按来源目的地对应表示，和邻居节点的连接（表示之间存在共享），如果且仅当相应的连接有着一些共同的联系。为了避免在网络图波长的冲突，邻居节点总是有不同的颜色。 图 1 实例网络以及波长分配过程 两个节点之间的最短路径可以通过使用如Dijkstra算法或Floyd算法。这两种算法具有相同的复杂度为O，如果每个节点对之间的路径进行搜索。在实践中，Floyd算法通常会好一点，由于常系数较小。