一种新的动态波长分配算法

无

光纤与电缆及其应用技术

Ｏｐｔｉｃａｌ

２００８年第３期

Ｎｏ．３

２００８

Ｆｉｂｅｒ＆．ＥｌｅｃｔｒｉｃＣａｂｌｅ

厂＋’＋。＋。＋、

｛网络技术｝

、一＋－＋．＋．＋．』

一种新的动态波长分配算法

徐

威

（国防科学技术大学光电科学与工程学院．长沙４１００７３）

［摘要］基于相对容量影响（ＲＣＩ）算法提出了一种新的动态波长分配算法——改进的相对容量影响算法。新算法针对ＲＣＩ算法的不足，考虑了链路容量的影响，准确地描述了分配波长对全网的影响；同时有效回避了可用信道数量少的波长，使负载更加均衡。仿真结果表明新算法具有更好的业务阻塞率性能，证明了新算法的有效性。

［关键词］ＷＤＭ光网络；动态波长分配；负载均衡；相对容量影响算法；链路容量［中图分类号］ＴＮ９１９．３

［文献标识码】Ａ

［文章编号］

１００６—１９０８（２００８）０３—００３９—０４

ＡＮｏｖｅｌＤｙｎａｍｉｃ

ｉｎ

ＷａｖｅｌｅｎｇｔｈＷＤＭＯｐｔｉｃａｌ

ＸＵＷｅｉ

ＡｓｓｉｇｎｍｅｎｔＡｌｇｏｒｉｔｈｍ

Ｎｅｔｗｏｒｋ

（ＣｏｌｌｅｇｅｏｆＯｐｔｏ－ＥｌｅｃｔｒｏｎｉｃＳｃｉｅｎｃｅａｎｄＥｎｇｉｎｅｅｒｉｎｇ，ＮａｔｉｏｎａｌＵｎｉｖｅｒｓｉｔｙｏｆＤｅｆｅｎｓｅ

ＴｅｃｈｎｏｌｏｇｙｏｆＰＬＡ，Ｃｈａｎｇｓｈａ４１００７３。Ｃｈｉｎａ）

Ａｂｓｔｒａｃｔ：Ａｎｅｗｄｙｎａｍｉｃｗａｖｅｌｅｎｇｔｈ

ａｌｇｏｒｉｔｈｍｉｓ

ｐｒｏｐｏｓｅｄ，ｔｈａｔｉｓ

ｃａｌｌｅｄ

ａｓｓｉｇｎｍｅｎｔ

ａｌｇｏｒｉｔｈｍｂａｓｅｄ

ｏｎ

ｔｈｅ

ｒｅｌａｔｉｖｅｃａｐａｃｉｔｙ

ａｔ

ｉｎｆｌｕｅｎｃｅ（ＲＣＩ）

ｉｍｐｒｏｖｅｄ

ＲＣＩａｌｇｏｒｉｔｈｍ．ＴｈｉｓｎｅｗａｌｇｏｒｉｔｈｍａｉｍｓｔｈｅｄｅｆｉｃｉｅｎｃｙｏｆＲＣＩ

ａ

ａｌｇｏｒｉｔｈｍ。ｔａｋｅｓｔｈｅｌｉｎｋｃａｐａｃｉｔｙｉｎｆｌｕｅｎｃｅｉｎｔｏｃｏｎｓｉｄｅｒａｔｉｏｎ。ＳＯｉｔｍｏｄｅｌｓｔｈｅｉｎｆｌｕｅｎｃｅｏｆａｓｓｉｇｎｉｎｇｔｈｅｎｅｔｗｏｒｋａｃｃｕｒａｔｅｌｙ．Ａｔｔｈｅｓａｍｅｅｑｕｉｐｏｉｓｅｔｈｅｌｏａｄ

ｏｎ

ｗａｖｅｌｅｎｇｔｈ

ａｒｅ

ｏｎ

ｔｉｍｅ，ｉｔ

ａｖｏｉｄｓｔｈｅｗａｖｅｌｅｎｇｔｈ

ｏｆｈａｖｉｎｇ

ｌｅｓｓｃｈａｎｎｅｌｓｔｈａｔｕｓａｂｌｅｔｏ

ｗａｖｅｌｅｎｇｔｈｍｏｒｅｅｆｆｅｃｔｉｖｅｌｙ．Ｔｈｅｓｉｍｕｌａｔｉｏｎｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｉｔｈａｓｂｅｔｔｅｒｃａｐａｂｉｌｉｔｙｏｆｒｅｄｕｃｉｎｇ

ｐｒｏｖｅｓ

ｔｈｅｂｌｏｃｋｒａｔｅ，ｗｈｉｃｈ

Ｋｅｙ

ｉｔＳｖａｌｉｄｉｔｙ．

ｗｏｒｄｓ：ＷＤＭｏｐｔｉｃａｌｎｅｔｗｏｒｋ；ｄｙｎａｍｉｃｗａｖｅｌｅｎｇｔｈａｓｓｉｇｎｍｅｎｔ；ｌｏａｄｅｑｕａｌｉｚａｔｉｏｎ；ｒｅｌａｔｉｖｅｃａｐａｃｉｔｙｉｎｆｌｕｅｎｃｅ

ａｌｇｏｒｉｔｈｍ；ｌｉｎｋｃａｐａｃｉｔｙ

０

引言

ａｎｄ

Ｒ（Ｒａｎｄｏｍ

ＷａｖｅｌｅｎｇｔｈＡｓｓｉｇｎｍｅｎｔ），ＦＦ（Ｆｉｒｓｔ—

Ｆｉｔ），ＬＵ（Ｌｅａｓｔ—Ｕｓｅｄ），ＭＵ（Ｍｏｓｔ—Ｕｓｅｄ）。ＭＰ

路由和波长分配（ＲｏｕｔｉｎｇＷａｖｅｌｅｎｇｔｈ

（Ｍｉｎ—Ｐｒｏｄｕｃｔ），ＬＬ（Ｌｅａｓｔ—Ｌｏａｄ），ＲＣＬ（Ｒｅｌａｔｉｖｅ

Ｃａｐａｃｉｔｙ

Ａｓｓｉｇｎｍｅｎｔ，ＲＷＡ）是波分复用（ＷＤＭ）光网络的核心问题之一。研究ＲＷＡ的目的是尽可能减少所需要的波长数和降低光路请求的阻塞率。由于ＲＷＡ问题是ＮＰ完备问题，为简便起见，一般将其拆解为路由问题和波长分配问题来分别研究。常见的路由方式有固定路由（ＦＲ）、备用路由（ＦＡＲ）、自适应路由（ＡＲ）等。其中ＡＲ在优化业务阻塞率方面是最优的，但其时间复杂度很大；ＦＡＲ能有效优化业务的阻塞率，同时具有合适的时间复杂度。

目前国际上已经提出的动态波长分配算法有：

Ｌｏｓｓ）和相对容量影响（Ｒｅｌａｔｉｖｅ

Ｃａｐａｃｉｔｙ

Ｉｎｆｌｕｅｎｃｅ，ＲＣＩ）。其中ＲＣＩ算法是一种较新的算法，具有较前者更好的性能。我们对ＲＣＩ算法进行了深入研究，目的是改进其性能，使其更加准确地描述网络资源状态，进一步降低网络阻塞率，实现波长负载均衡。本文在ＲＣＩ算法基础上提出了改进的ＲＣＩ算法（ＩＲＣＩ）来求解动态业务请求下的ＲｗＡ问题。该算法的实现是基于ＦＡＲ选路策略和有限波长数、无波长变换功能的ＷＤＭ光网络。１

ＩＲＣＩ算法的提出

ＲＣＩ动态波长分配算法模型

基于ＦＡＲ选路策略的ＲＣＩ波长分配算法的基

［收稿日期］２００７—１０—２７

［作者简介丁徐威（１９８６一），男．国防科学技术大学光电

科学与工程学院本科生．

１．１

［作者地址］湖南省长沙市国防科技大学一号院七院二队

九班，４１００７３

本假设是：考虑多光纤情况时，每根光纤支持Ⅳ个

第1页下一页