高速ネットワークのための遺伝的アルゴリズムを用いた適応型ルーティングの有効性

(1)

マルチメディア通信と分散処理ワークショップ平成10年11月

高速ネットワークのための遺伝的アルゴリズムを用いた

適応型ルーティンゲの有効性本

レオナルドパロリ，小山明夫，茂手木志保，武田利浩，横山晶-t

山形大学工学部電子情報工学科I

〒

99

2

・

8510

山形県米沢市城南

4 -

3 -

1

6 {

b

a

r

o

l

i

，

koyama

，

t

a

k

e

d

a

，

yokoyama}@eie

.

y

z

.

y

a

m

a

g

a

t

a

-

u

.

a

c

.

j

p

m

o

t

e

g

i

@

e

t

n

.

y

z

.

y

a

m

a

g

a

t

a

-

u

.

a

c

.

j

p

A

b

s

t

r

a

c

t

近年，通信ネットワーク上のトラフィックは著しく堵加している.それに伴ってネットワーク上の通信経路を制御するルーティング手法に関する研究が重要な課題となっている.高速ネットワーク上で効率の良い通信を行うには，幅鞍状態にある経路を回避し，より通信遅延時間の少ない経路を選択しなければならない.これに関して，従来のテープノレベースルーティング手法は高速ネットワークに適当ではなく，遺伝的アルゴリズム，ニューラノレネットワーク，ファジィ理論を用いた知的なノレーティング手法の有効性が報告されている.遺伝的アノレゴリズムを用いた適応型ルーティング手法として. Genetic Load Balancing Routing (GLBR)手法が提案されているが，GLBR手法では，経路を表す個体の遺伝子は，通信経路の通過するノードの並びで表現されているため遺伝的操作が困難になる.本論文では，上記の問題点を解決するために、無向グラフの形式で表されているネットワークをTreeで表現し，Treeの分岐点を個体の遺伝子として用いる新しい手法AdaptiveRouting using Genetic Algorithm (ARGA) ;を提案する.シミュレーションを行った結果，ARGA手法は GLBR手法より良い性能を示すことがわかった.

1 .

はじめに

近年，コンピュータネットワークの発展と共に，ネットワーク上のトラヒックは著しく僧加している.それに伴って生じる通信遅延に関する問題を解決するために，ネットワークの通信経路の制御，すなわちルーティング手法に関する研究が重要な課題となっている. • E仔'ectivenessof an AdaplIve RoulIng Method for High Speed Net -works UsingGenetic Algorit1uns t Leonard Barolli， Akio Koy町na，Shiho Motegi， ToshiroTaketa， Shoichi Yokoyama t Department of Electrical and Information Engineering， Yamagata University 従来のルーティング手法は，ルーティングテーブルを使用して経路を決定するものが多い.このように，ルーテイングテーブルを用いる方法をテーブルベースルーティング(TBR)という.この方法は，中間ノードに到着したパケットが出力するリンクを選択するために，ルーティングテープノレを参照する方法であるが，次のような欠点がある.ルーティングテーブルは，すべての目的地に関して，送出されるパケットに適した出カリンクを示す情報を持っているため，テーブルサイズはネットワークの規模と共に増大する.稲鞍に対処したり，故障中のリンクやノードを迂回させるために，ノレーティングテープ、ルのデータの更新が必要となり，そのためノード聞の情報の周期的な伝送が発生する[1]. 以上の理由により従来のルーティング手法TBRは高速ネットワークに適当ではなく，ニューラルネットワーク，ファジィ理論，遺伝的アルゴリズムを用いた知的なルーティング手法の有効性が報告されている [2，3，4，5， 6]. 遺伝的アルゴリズムを用いた適応型ルーティング手法としてGLBR手法

[

6 ]

ts提案されている.G LBR手法は，従来のShortestPath First (SPF)プロトコルおよび Routing lnformation Protocol (RIP)より良い性能を示している [6]. しかし， GLB R手法では，経路を表す個体の遺伝子は，通信経路の通過するノードの並びで表現されているので遺伝的操作が困難になる.そのために代替経路の生成に要する時間も長くなるという問題点がある. 本稿では，上記の問題点を解決するために，無向グラフの形式で表されているネットワークをTreeで表現し.Treeの分岐点を個体の遺伝子として用いる新しい手法AR GAを提案する.さらに，ノード数が20のネットワークに関してシミュレーションを行った結果.ARGA 手法はGLBR手法より良い性能をもつことを示す. 本論文の構成は以下のとおりである.まず，遺伝的アルゴ‘リズムの概要について述べた後.ARGA手法の提案を行う.次にシミュレーションにより.ARGA手法の性能評価を行う.最後に、結論および今後の課題について述べる. ﹁内 d ヮ ' u

(2)

2 .

遺伝的アルゴリズム

遺伝的アノレゴリズム

(

G

A

:G

e

n

e

t

i

c

A

l

g

o

r

i

t

h

m

)

とは，自然淘汰や突然変異といった生物進化のメカニズムや自然遺伝子に着想を得たものであり，環境と個体の相互作用を評価関数でモデル化したアルゴリズムである.遺伝的アルゴリズムでは、解の候補は個体で表される.各個体が外部環境にどの程度適応しているかは適応度によって表され，適応度は各個体が持つ染色体によって決定される.遺伝的アルゴリズムでは，適応度の高い個体ほど外部環境に適応しているとみなす.各個体は，適応度によって次の世代に子孫を残す確率が決められる.そして，選択，交文，突然変異という遺伝的操作によって遺伝的要素の組み換えが行われる.その結果，次の世代の個体集団が生成される [7，8].遺伝的アルゴリズムの処理手順を図1に示す. 初期世代の個体集団の生成新しい世代の個体集団の生成図l 遺伝的アルゴリズムの処理手順

F

i

g

.

1 GA

f

t

o

w

c

h

a

r

t

.

3.ARGA手法

このセクションでは，

ARGA

手法の提案を行う.

A-H

F 図2 ノード数8のネットワークモデル Fi

g

.

2 N

e

t

w

o

r

k

m

o

d

e

l

w

i

t

h

8

n

o

d

e

s

.

A

s<ラiく?~~

ご叫

"

そ

こ

;

〈

J

3

2

ム H S-D~H

o.~~ご2F-H

。

マ

二

2 -

H

ぺi

二

:

-

H

図3 ネットワークモデノレの

T

r

e

表現

F

i

g

.

3

N

e

t

w

o

r

k

T

r

e

m

o

d

e

l.

3 .

1.ネットワークの

T

r

e

表現遺伝的アルゴリズムをルーティング手法に適用するために，ネットワーク上の通信経路を個体で表現する必要がある.そのために，

ARGA

手法では，無向グラフで表されたネットワークを

T

r

e

で表現する. 図2にノード数 8のネットワークモデルを示す.このネットワークモデルについて，出発ノードを

A

，目的ノードをH としたときの到達可能な全ての経路は，図 3 のような

T

r

e

で表される.この

T

r

e

の重複する分岐点 (図3の網掛け部分)をまとめた

T

r

e

を新たに作成し，各分岐点にそれぞれ番号(丸数字で表す)をつけたものを図4に示す.このモデルを圧縮

T

r

e

モデルと呼ぶ.

ARGA

手法では，図4における分岐点を遺伝子として扱い，その遺伝子の並びによって表される染色体から経路を導く.

3 .

2 .

遺伝子コーディング

GLBR

手法では，通信経路の通過ノードの並びをそのまま遺伝子としてコーディングしている.この場合，安易に遺伝的操作を行うと，実際には存在しないリンクを含む経路や，同じノードを何回も通る経路とし、う実際のネットワーク上の経路として成り立たない経路を表す個体を生成しやすい.また，通過するノード数によって染色体の長さが変化するため，遺伝子数の異なる個体同士の交文が複雑になる.さらに，各遺伝子は隣接する遺伝 ρ h u n ノ﹄

(3)

G - H F-一一G一一-H

て

F

二

G - H

興

4 i

二

Hー図4 圧縮Treeモデノレ Fig.4 Reduc巴dTr巴巴model. O 2 3 4 5 6 7 ￨ A I B l o l E I C I F I G I H I a)GLBR手法:通過するノードを遺伝子として表現 Chromosome of GLBR method.

￨

庇

cl

促￨割引

EIHE I

品￨品￨附

IGFI b)ARGA手法:分岐点を遺伝子として表現 Chromosome of ARGA m沼山od. 図5経路“A，B，D，EιF，G，H"を表す染色体 Fig. 5 Chromosom巴for“A，B，D，E，C，F，G，H" route 子と相互作用するため，染色体中の一つの遺伝子をランダムに変化させるとし、う突然変異の処理が難しくなる. ARGA手法では，ネットワークのTree表現の各分岐点につけられた番号を遺伝子座の番号とし，各分岐点のノードを遺伝子として扱う.遺伝子座とは染色体の位置を表すものである.遺伝子を分岐点で表現すると，染色体に含まれる遺伝子数は通過ノード数に関係なく一定に保たれ，交叉が簡単になる.また，各遺伝子は隣接する遺伝子と相互作用しないため，突然変異を個体に施しやすくなる.このように，一般的な遺伝的操作が適用しやすいものとなり， GLBR手法の遺伝的操作が複雑になるという問題点を解決することができる.また，多様な個体を生成することが可能になるため，効率的なルーティングサーチを行える.そのため，より速く新しい経路を探し出すことができる. 図2に示したネットワーク上の通信経路“A，B，D，E，C， F，G，H"を表す染色体を図 5に示す.図 5(b)の網掛け部分は，使用している分岐点を表す遺伝子座の中で，現在選択されているノードを表している. 3.3.遺伝的操作個体を選択する方法については，ランク戦略とエリート保存戦略の二つを併用する.ランク戦略とは，適応度によって各個体をランクづけし，あらかじめ各ランクに対して決められた確率で子孫を残せるようにする方法である.エリート保存戦略とは，個体集団中で最も適応度の高い個体をそのまま次の世代に残す方法である. 交叉方法は，経路を表す個体が交文によって著しく接されることがないように，交叉位置が一つである単一交叉を用いる.交文位置は，選択された2個体聞の共通の遺伝子座の中からランダムに選ぶ. 突然変異を起こす個体は，個体集団の中からランダムに選択する.突然変異が進化に影響を及ぼすようにするため，突然変異を施す遺伝子は，現在使用している分岐点を表す遺伝子座の中からランダムに選択する. 各個体の適応度は，個体が表す通信経路の遅延時間が短いほど高いものとし，遅延時間の逆数で表す.

3 .

4 .

ルーティング ARGA手法では，適応型アルゴリズムである分散型ノレーティングと始点制御ルーティングを用いる. 分散・適応型ルーティングとは，ネットワークの大域情報と局所情報を併用し，現在のトラフィックやトポロジーに基づいてルーティングの決定を行う方法である. この方法によって，ネットワーク環境に適応したルーティングを行うことができる. 始点制御ルーティングとは，パケットを送信するノードにおいて最終目的地までの完全な経路を決定するルーテイング手法である.始点制御ノレーティングでは，送信ノードが通信経路を知っているため，複数のパスを使ってデータを流すことが可能になる.また，大域的なトラフィックの把握ができるため，効率の良い経路選択が可能になる.

4 .

シミュレーション

このセクションでは， ARGA手法と GLBR手法についてシミュレーションを行い，結果を比較する.

4 .

1 .

シミュレーション方法シミュレーションに用いるネットワークは図6に示すノード数

2

0

のモデルである.このネットワークについて，出発ノードをA，目的ノードをTとするときのTree 表現を図

7

に示す. シミュレーションでは，ノード Aからノード Tへパケットの送信を行うものと仮定する.各リンクにはそれぞれ遅延時間を設定し，最初にネットワーク内で最も遅延時間の短い経路を用いて通信を行っているものとする. 次に通信に用いている経路上のリンクに急激な輯鞍状態を起こし，幅鞍リンクを回避する新しい経路の探索を行円 t

・

円 f L H

(4)

T F 図6 ノード数20のネットワークモデル Fig.6 Networ¥cmod巴1with 20 nodes. 表1 わせる.新しい経路として用いることのできる経路の許容範囲としては，全経路725のうち，ランクが上位 10 位までの遅延時間の経路を設定する.遺伝的操作は，許容範囲の遅延時間の経路を探し出すか，世代数2∞ を満たすまで繰り返す.二つの手法を比較するため，初期世代の個体集団は同ーのものを用意する.シミュレーションで用いるパラメータは表1のようになる.また，計測するデータを以下に示す. (a)ルーティングアルゴリズムの性能に関するパラメーター遺伝的操作の平均回数:Gα ー許容範囲の経路を探せなかった割合(%):Nr -参照した個体数の割合 (%):Pr ー参照した経路の種類の割合(%):Tr ー最終的に得られた経路の平均ランク :

Ra

(b)遺伝的操作に要する時間に関するデーター遺伝的操作l回に要する時間(msec):

GT

a -解が得られるまでに要する時間(msec): P1;α

4 .

2 .

シミュレーション結果シミュレーションは表

1

のパラメータで行った.論文スペースの関係上，表 2，表 3に，交叉率 70%，突然変図7 図6のネットワークモデルのTree表現 Fig.7 Network Tree mod巴lofFig.6 異率 8%の場合のシミュレーション結果を示す.記号“*" は計測値が lmsec以下であることを示す.各ノ4ラメータに関して，

ARGA

手法の方が

GLBR

手法よりも良い結果となる.これらの値は，個体数が捕えるのに伴って良くなる.また，処理時間に関しでも

ARGA

手法の方が短く，良い結果となる. 次に，

ARGA

手法と

GLBR

手法とをシミュレーションステップ数で比較した結果を図8に示す.縦軸は求められた経路の遅延時間，横軸はシミュレーションステップ数である.図8は，急激な幅鞍状態が起こった場合に，輔鞍を回避している最適な経路(許容範囲内の経路)を探し出すのに，どのくらいのステップ数を要しているかを表している.図中の網掛け部分は許容範囲の遅延時間を表している.シミュレーションステップは次のような3 つの部分に分かれている. Step1 Step11 St巴pIII 通信を行っている状態急激な幅鞍が起こった状態新しい通信経路を探している状態 n x u n ノ臼

(5)

表2 アルゴリズムの性能に関する結果 Table2 Resultsof a1goritluns perfoπnance. 個体数10 個体数20 ARGA GLBR ARGA GLBR G .. 7.4 12.4 1.8 7.5 Nr 0.0 0.0 0.0 0.0 Pr 10.2 17.1 4.9 20.7I Tr 3.2 3.0 3.8 3.4 R .. 5.4 6.1 4.4 4.7 表3 遺伝的操作に要する時間に関する結果 Table 3 ResultsofGA operation time. 個体数 10 個体数20 ARGA GLBR ARGA GLBR 最大 86.0 180.0 781.0 1516.0 G九 _{放小} 俳ヨ事 12.0 15.0 (msec) _{平均} ₁₆_.₅ ₄₄_.₀ ₁₄₄_.₀ ₃₅₄_.₆ 綾大 1141.0 3195.0 1735.0 6836.0 PT. _{綾小} ₆_.₀ ₈_.₀ ₃₁_.₀ ₃₉_.₀ (msec) _{平均} ₁₂₀_.₆ ₄₀₄_.₆ ₂₇₉_.₀ _569.₁ 図8より，許容解を得るまでに必要とした遺伝的操作回数はARGA手法の方が少ないため，より速く許容解を導いているといえる.また，各世代においても， ARGA 手法の方が短い遅延時間の経路を導いていることがわかる. 表4に示すように両手法とも，最終的に導いた経路はランクが閉じ7位の経路であるが，途中経過に差が出ていることがわかる.表4の中の番号は，遺伝的操作によって得られた個体の遅延時聞が変化した場所を示す. A2-A5が提案手法ARGAについて， G2-G6が従来手法GLBRについてのものである (A，l Glに関しては省略). ARGA手法では，世代数が7の時点でランクが7位の経路“

A

，

B

，

n

，

C

，

E

，

H

，

L

，

N

，

S

，

T

"

を導き，操作が終わっている.この段階で， GLBR手法によって導き出された経路はランクが36位の経路“A，B，D，H，L，N，M旦Q，R，S，T"である. このように，世代数が閉じ場合で比較してみると， ARGA手法の方がGLBR手法より遅延時間の短い経路を見つけており，輯鞍状態にあるリンクを避けていることがわかる.

5 .

性能評価

ARGA手法の有効性および遺伝的操作に要する時間について評価する. 5.1.ARGA手法の有効性表3の結果より， ARGA手法について以下のことがいえる. 40.0 35.0 30.0 E 25.0 ARGA手法一一一 GLBR手法ーーーー ~ 20.0 胤則 15.0 10.0 5.0 0.0: 0 ₁₀ ₁₅ ₂₀ ₂₅ 噺 - l ll 世代数 111 Simulation Step 図8 GLBR手法及びARGA手法の比較評価 Fig.8 Perfonnance comparison fOT GL8R and ARGA methods. -解を得るまでの時聞が短く，ネットワーク環境の変化により速く適応したルーティングを行うことが可能である. -新しい経路を探せない確率が0.0%であるので，アノレゴリズムの信頼性が高い. .試す経路の数が少なくてすむため，ネットワークに与える負荷も少ない. ・多様な経路を生成できるため，探索効率が良く，最終的に得られる解の質も高い. 以上より， ARGA手法の方がGLBR手法よりもルーティングアルゴリズムの性能が良いといえる.

5 .

2 .

遺伝的操作に要する時間遺伝的操作に要する時間は， ARGA手法の方がGLBR 手法よりも短いことが表3からわかる.これは， GLBR 手法では遺伝的操作が複雑になっているためである.以下に両手法の手続きの相違を示す. 交叉 ARGA:生成された個体はすべて経路として成り立つ. GLBR: 生成された個体が，同じノードを複数回通過している可能性があり，それらの確認と処理が必要になる.

(6)

-29-表4 各世代数に関する比較 Table 4 Comparison for巴achgenerationnumber. ARGA GLBR 世代数 _{書号} _{経路} _{遅匙} _フンク _{番号} _{経路} _{遅延} _フンク 1 A2 ABDCEHLNMPOQRST 26.5 175 G2 ABDCEHIJLNMPOQRST 28.9 203 2 A3 ABDHLKMPOQRST 20.9 54 4 A4 ABDHLKMPQRST 17.3 19 G3 ABDHEHLNMPQRST 21.2 69 5 G4 ABDHLNMPQRST 20.0 36 7 A5 ABDCEHLNST 14.7 7 10 G5 ABDHLK加lPQRST 17.3 19 24 G6 ABDCEHLNST 14.7 7 突然変異 ARGA:生成された個体はすべて経路として成り立つ. GLBR: 変化させた遺伝子(ノード)が，実際にはつながっていない遺伝子(ノード)である可能性があり，それらの確認と処理が必要になる. 上述のように.ARGA手法にはGLBR手法で必要とする整合性の確認という処理がないため，交叉や突然変異の処理が簡単になり，解を得までの時聞が短くなる.

6 .

おわりに

本稿では，遺伝的アノレゴリズムを用いた新しいノレーティングアルゴリズムを提案し，その性能評価を行った. まず、GLBR手法はSPFプロトコノレ及びRIPプロトコルより，よい振舞いを示すことを述べた。また，提案したARGA手法と GLBR手法の比較を行った.動的ルーティングでは，より短い処理時間でネットワーク環境に適応した経路を導くことが重要である.ARGA手法はこの点を満足しており、 GLBR手法よりも性能の良い手法であることを示した.また、 ARGA手法はTr巴eモデルを用いているのでルーティング・ループを防ぐことができる. 今後は本手法をATMネットワークのルーティングに適用する研究を行いたい. ARGA手法は小規模ネットワークあるいは中規模ネットワークに対して良い性能を持つ. しかし、大規模ネットワークに対して染色体が長くなるため遺伝的操作に時聞がかかる。これを解決するために我々は新たな分散ルーティング手法の提案を行いたい.

謝辞

本研究の支援に対して日本学術振興会に感謝致します。

R

e

f

e

r

e

n

c

e

s

[1] C.Baransel， W.Dobosiewicz， and P.Gburzynski. Routing in Multihop Packet Switching Networks: Gb/sChallenge IEEE Network， 9(3):38-60， May/June 1995.

[2] C.Wang and P.N.Weissler.The use of Artificial N巴uralNet

-works forOptimal Message Routing. IEEE Network Mag.，

9(2):16-24， M幻"Ch/April 1995.

[3] J.Kha1fet and P.Chemouil. Application of Fuzzy Control to Adaptiv巴TrafficRouting in Te1ephon巴Networks.Informa

-tionandDecision Tech.，19(4):339-348，1994.

[4]L.Barolli， A.Greca， A.Koyama， and S.Yokoyama. A Strat -egy for Policing and Routing of ATM Networks Traffic Us

-ing Fuzzy Set Theory.Proc.of IEEE MICCIISPACS'97，

S4.2.1-S4.2.8，1997.

[5]L.Baro凶， A.Koyama， S.Motegi， and S.Yokoyama. Use of Fuzzy Logic組dGen巴ticAlgorithrns for Policing and Rout

-ing in ATM Networks. D1COMO'98 Symposium，lPSJ Sym. posium Series， 98(8):25-32， 1998.

[6]棟朝雅晴，高井昌彰，佐藤義治.遺伝的アルゴリズムによる負荷分散機構を有する適応型ルーティング情報処理学会論文誌，39(2):219-227，Feb刊ary1998.

[7] D.E.Go1dberg.Genetic Algorithms in Search， Optimization，

and Machine Learning. Addison-Wesley Publishing Com-pany， Inc.， 1989. [8] M.Srinivas and L. M. Patnaik. Genetic Algorithms: A Sur -vey.COMPUTER， 28(5):17・26，1994. 向日 u n ペ U