JPS63207242A - パケツト交換網のル−テイング制御方式 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は、パケット交換網のルーティング制御方式に関
し、特に回線のキュー長異常時における迂回制御に好適
なルーティング制御方式に関する。

〔従来の技術〕

端末から送出された電文は、加入者線を通して交換機に
伝送され、ここでパケットに組立てられた後、交換機の
メモリに蓄積される。メモリに蓄積さ汎たパケットは、
他の端末から送出されたパケットとともにパケット多重
され、高速伝送路に送出される。パケットは、制御情報
に従ってパケット交換網を伝送され、受信端末が収容さ
れているパケット交換機に送達されるが、その伝送経路
は一定ではなく、パケット交換網の状態により別々の経
路を選択することが可能である。すなわち、その時刻に
おける網内の輻幀状態を調べ、空いている経路を選択す
ることができる。これを、ルーティング制御と呼ぶ。従
って、ルーティング制御を行っている場合には、特定の
経路のみが混雑し過ぎて、輻稜することはない。

従来、ルーティング制御を行うための基準としては、（
イ）パケット伝送時間の遅延を最小にする。

（ロ）パケット伝送距離を最小にする、等がある。

一般には、パケット交換網の各リンクに上記基準に相当
した重みを付け、その重みを最小化するようなルーティ
ング制御を行う。

パケット交換網のルーティング制御方式として、例えば
、文献”　Ｔ　ａｎｅｎｂａｕｍ著ｒ　Ｃｏｍｐｕｔｅ
ｒ　　Ｎ　ｅｔｖｏｒｋｓＪに記載されている方式があ
るが、これによれば、各交換機が自局の回線の方路状態
としてのキュー長状態を監視し、それが異常である場合
には、他の回線のキューにつなぎ替えて、迂回させてい
る。

しかし、従来のルーティング制御方式では、ルーティン
グ上の安定性について配慮していないため、単純に迂回
すると、その影響が全宛先交換機に及び°、多数の宛先
交換機において着パケットの順序逆転が発生したり、あ
るいは迂回先の回線にトラヒックが集中したりする可能
性があった。

〔発明が解決しようとする問題点〕

このように、従来のルーティング制御方式においては、
ある回線のキュー長異常等により他の回線に迂回する場
合、その回線が異常状態であれば機械的に他の空きない
しキュー長の短い回線に迂回していた。すなわち、この
ときには、迂回を宛先交換機ごとに段階的に行う等の配
慮は行われておらず、その回線を送出方向とする全宛先
交換機を対象として迂回を行っているため、迂回先の回
線にトラヒックが集中する可能性が大となっている。ま
た、ルーティング変更時の安定性が悪く、かつ全ての宛
先交換機において、パケットの到着順序の反転が起こる
確率が増大している。

本発明の目的は、これら従来の問題を改善し、全ての宛
先交換機においてトラヒックの集中やパケットの到着順
序の逆転が発生せず、ルーティング変更時に高い安定性
でパケットを迂回させることができるパケット交換網の
ルーティング制御方式を提供することにある。

〔問題点を解決するための手段〕

上記目的を達成するため、本発明によるパケット交換網
のルーティング制御方式は、各々複数の宛先交換機を通
過するパケットを送信する２以上の回線の中の１つの回
線からパケットを送出する場合に、該回線のキュー長が
所定値を越えて異常を生じたとき、上記複数の宛先交換
機の中の特定の宛先交換機のパケットのみを他の回線に
迂回させ、キュー長異常が継続するときには、さらに他
の宛先交換機を選択して、該交換機のパケットも他の回
線に迂回させ、キュー長異常が解消したときには、上記
迂回した宛先交換機のパケットを元に戻すことに特徴が
ある。

〔作　　用〕

本発明においては、送出しようとしている回線で、キュ
ー長異常、つまりキュー長が規定値より大になった場合
に、その回線で送出する宛先交換機を単位として、それ
ごとに段階的に迂回することにより、特定の宛先交換機
へのパケットの集中やパケットの到達順序の逆転を防止
している。

すなわち、本発明のルーティング制御方式では、ある回
線がキュー長異常を発生した場合、ルーティングテーブ
ルからその回線を用いてパケットを送出している宛先交
換機のうちキュー長異常を起こした回線と同じ中継ホッ
プ数を持つ交換機、ないしは中継ホップ数が１つだけ大
きい他の回線を持つ宛先交換機を選択し、さらに適当な
アルゴリズムに従って１つの交換機を決定する。そして
、その宛先交換機が他に同一中継ホップ数を持つときに
は、そちらの交換機にキュー長異常を起こした回線のト
ラヒックを迂回し、また中継ホップ数が１だけ大きい宛
先交換機の場合には、その宛先交換機のトラヒックを２
つに分けるようにルーティングテーブルを変更するので
ある。また、上記制御によってトラヒックが迂回された
回線がキュー長異常を起こした場合には、このような処
理が行われていることを前提にして判断することにより
、逆方向の処理を行って迂回していたトラヒックを元に
戻すか、あるいはさらに迂回の処理を行う。

このように、本発明の制御によれば、各回線のトラヒッ
ク量に応じて適切な迂回処理を段階的に行うことが可能
である。

〔実施例〕

以下、本発明の一実施例を１図面により詳細に説明する
。

第２図は、本発明が適用されるパケット交換網の構成図
であり、第３図は第２図におけるパケット交換機１のル
ーティングテーブルを示す図であ机 第２図のパケット交換網においては５１〜９の番号が付
けられたパケット交換機が、それぞれ回線ａ□、Ｑ２．
・・・・・により接続されている。

ここでは、パケット交換機１に収容されている回線Ｑｌ
ｙＱ２のキュー長異常について、説明する。

パケット交換機１は、他のパケット交換機２〜９宛のパ
ケットを回線Ｑ１＋Ｑ２を介して送信するが、その場合
、第３図に示すルーティングテーブル１００の値に従っ
て送信するものとする。

ルーティングテーブル１００は、各宛先交換機にパケッ
トを送信する際に回線Ｑ１を用いた場合の中継ホレプ数
１０１と、回線Ｑ２を用いた場合の中継ホップ数１０２
と、実際の送信方路１０３の各値を格納している。例え
ば、交換機２に対して回線Ｑ、を介して送信するときの
中継ホップ数は１、回線ｎ２を介して送信するときの中
継ホップ数は３でるため、実際の送信方路はＱｌである
ことを示している。同じようにして、交換機３に対して
回線Ｑ１を介して送信するときのホップ数は２１回線ｆ
ｉ２を介して送信するときのホップ数は４であるため、
実際の送信方路はＱｌである。

また、宛先交換機５の場合には、回線Ｑ１とΩ２の中継
ホップ数が共に同じ値２であるため、実際の方路として
Ω１と０２の両方が用いられている。

このことは、宛先交換機８および９に対しても同じであ
って、回８１１１＋ｎ２を介して送信した場合、交換機
８へはホップ数３、交換機９へはホップ数４であって、
いずれも同一値である。

第４図は、第２図におけるパケット交換機１〜９の一般
的なハードウェア構成例を示す図である。

ここでは５パケツト交換＃！に１のみが示されているが
、他の゛パケット交換機もこれとほぼ同じ構成である。

交換機１内では、交換処理のための命令群および各加入
者や中継回線等の必要なデータを格納するメモリ１６と
、上記命令群を実行するプロセッサ１７と、加入者回線
または中継回線を上記メモリ１６およびプロセッサ１７
に結合するための回線インタフェースアダプタ１９１〜
１９４とが、バス１８を介して互いに接続されている。

パケット交換機１は、通常、複数の加入者回線と複数の
中継回線を収容しており、これらの各回線から受信する
パケットは、回線インタフェースアダプタ１９１〜１９
４を経由してメモリ１Ｇ上に一旦菩積された後、プロセ
ッサ１７が各パケットごとにその宛先に応じて送出回線
を選択し、該当する回線インタフェースアダプタ１９１
〜１９４を経由して送出する。メモリ１６上には、第３
図に示すルーティングテーブル１００が格納されており
、プロセッサ１７はこのルーティングテーブル１００を
参照することにより、送出回線を選択する。

回線インタフェースアダプタ１９１〜１９４には、各々
の回線アダプタに生じている送出待ちキューＱ　ｆ　＋
　Ｑ　ｇ　＋およびＱｈが設けられ、プロセッサ１７は
これらのキューＱを参照して迂回処理を実行する。

第１図は、本発明の一実施例を示すルーティング制御の
処理ブローチヤードである。ここでは、第４図に示すパ
ケット交換機１内のプロセッサ１７により実施さハる命
令ステップ列が示される。

先ず、回線Ｑ、とＱ２のキュー長をカウントしくステッ
プ２０１）、もしそれらのキュー長に差がある場合（い
ま、回線Ｑ１のキュー長が１回線愈２のキュー長よりも
大であるとする）（ステップ２０２）、キュー長の大き
い回線に対して、既に迂回処理を行っているか否かを調
べる（ステップ２０４）、前述の第３図に示すルーティ
ングテーブル１００は、迂回処理を未だ行っていない場
合である。以下、迂回処理を行っていない１ＩＪＩ合（
つまり、ステップ２０５以下）について、述べる。

この場合には、先ず同一宛先で、トラヒックを２以上の
方路に分けている（以下、これを負荷分散と呼ぶ）宛先
パケット交換機を、第３図に示すルーティングテーブル
１００から求める（ステップ２０５）。第２図および第
３図から明らかなように、負荷分散されている宛先交換
機としては、交換機５，８および９である。これらのう
ちから。

適当なアルゴリズムに従って１つを選択する（ステップ
２０６）。いま、その選択された交換機を９とする。負
荷分散を止めて、キュー長の小さい回線のみを送信方路
にする（ステップ２０７）。

第５図（ａ）（ｂ）は、゛交換機９に対するパケットの
経路を示す図である。パケット交換機１から回線Ωｌ、
Ω２を介して宛先交換機９に送信されるパケットは、通
常、第５図（ａ）に示すように、経路Ｆｔつまり回線ａ
１から交換機２，３．４を経由して交換機９に達し、ま
た経路Ｆ２つまり回線ｎ２から交換機６，７．８を経由
して交換機９に達する。両経路Ｆ１ｔＦ２とも、中継ホ
ップ数が４と同じであるため、パケットを半分ずつ送信
することにより、負荷を分散するのが通常である。

しかし、本実施例によるルーティング制御では、この宛
先交換機９に対する回ＩＲＱ　ｔと回線Ｑ２に負荷を振
り分ける処理を中止するのである。すなわち、宛先交換
機９に対する送信方路として、回ＩＩＡΩ見をルーティ
ングテーブル１００の送信方路の登録１０３から外すこ
とになる。その結果、第５図（ｂ）の実線で示すように
、経路Ｆ２のみとなる。すなわち、第５図（、）で宛先
交換機９に対してＦｌとＦ２の２つの経路を介してパケ
ットを送信していたが、１つの経路Ｆ２のみとなったの
で、その結果として、パケット交換機１の回ｍＱｌの負
荷が減少することになる。

次に、上述のルーティング制御を行った結果、まだ回Ｖ
ＩＡ　Ｑ　１のキュー長が回線ａ２のキュー長よりも大
であれば、同じような制御を宛先交換機８および５に対
しても順次行う必要がある。もし、宛先交換機８および
５に対しても、上述の処理を行って、その結果、トラヒ
ックの分散をしている交換機がなくなった場合には、回
線ａ２の中継ホップ数が回ｖＡＱ　ｌより１だけ大きな
宛先交換機に対して、トラヒックの振り分けを行う（ス
テップ２０８．２０９）。

中継ホップ数が回ｔｌＡ　Ｑ　１より１つ大きい宛先交
換機に対して、トラヒックを振り分ける場合、具体的に
は、ルーティングテーブル１００の中に回ｎＱＬより１
つ大きい回線Ｑ２を持つ交換機は４のみであるため、宛
先交換機４の送信方路として四線Ｑ２を登録する。

一方、回線Ｑ１ｙＱ２のキュー長に差がある場合、既に
キュー長大の回線０１に迂回しているときには５１つの
交換機に迂回しているならばその交換機の迂回を、また
２つ以上の交換機に迂回しているならばそれらの中から
１つを選択してその交換機の迂回を、直ちに中止する（
ステップ２１０）。この処理を繰り返し行って、迂回し
た宛先交換機のパケットを元に戻す。

第６図は、本発明の他の実施例を示すルーティングテー
ブルの内容を示す図である。

前述の実施例では、宛先交換機までの中継ホップ数１０
１および１０２について、その値を変更することはなか
ったが、本実施例では、キュー長異常が発生した場合に
は、該当方路の全ての宛先交換機までの中継ホップ数を
１だけ増加し、そのときの中継ホップ数から、送出方路
を変更することができる。例えば、最初、第３図のルー
ティングテーブル１００を持っていた交換Ｉａ１におい
て、回線Ｑ１の送信キューにキュー長異常が生じた場合
、第３図のテーブルの回線Ｑ、の中継ホップ数を全宛先
交換機について１だけ加算する。その結果を示したもの
が、第６図である。この加算結果により、テーブル１０
０において送信方路に変更が生じる宛先交換機は、４，
５，８．９の各パケット交換機である。すなわち、交換
機４では両回線の中継ホップ数が等しくなったため、実
際の送信方路は負荷を振り分ける必要があり、また交換
機５，８および９では両回線の中継ホップ数に差が生じ
たため、ホップ数の小さい回線Ｑ２を送信方路にする必
要がある。

本実施例においては、これらの送信方路の変更を一度に
行わず、適当なアルゴリズｌ−により上記宛先交換機４
，５，８．９から１つを先ず選択し、送信方路を変更す
る。この結果、キュー長異常が解消されなければ、さら
に残りの該当宛先交換機から１つを選択する。キュー長
異常が解消されない限り、この処理を繰り返すのである
。該当する宛先交換機の全てについて、送信方路の変更
を行っても、キュー長異常が解消されないときには、中
継ホップ数にさらに】だけ加算して、その結果から上述
と同じ処理を行って送信方路を変更する。

このように、本発明のパケット交換網のルーティング制
御においては、各交換機が自局の回線のキュー状態を参
照して送出方路を決定する場合に、複数の方略に分散し
ているか、あるいは中継ホップ数が１だけ異なる方路を
持つ宛先交換機に限って、１度の処理で１つの宛先交換
機の送出方路のみを変更するため、ルーティング方路の
変更によるトラヒックの偏りの振動する確率を減少させ
ることができるとともに、ルーティング制御を詳細に実
施することができる。

〔発明の効果〕

以上説明したように、本発明によれば、宛先交換機を単
位として、回線のキュー長異常の状態に応じ、宛先交換
機ごとに段階的に迂回を行うので、迂回光にトラヒック
が集中したり、または宛先交換機でパケットの到達順序
の逆転が生じたりすることがなく、ルーティング変更時
の安定性を高めることが可能である。

【図面の簡単な説明】

第１図は本発明の一実施例であるパケット交換機のルー
ティング制御の処理フローチャート、第２図は本発明が
“適用されるパケット交換網の構成例を示す図、第３図
は第２図の各交換機に備えら九るルーティングテーブル
例を示す図、第４図は第２図におけるパケット交換機の
ハードウェア構成例を示す図、第５図は本発明における
通信経路の変更例を示す図、第６図は本発明の他の実施
例であるルーティングテーブルの図である。 １：パケット交換機、１６：メモリ、１７：プロセッサ
、１８：バス、１９１〜１９４：回線インタフェースア
ダプタ、１００ニル−ティングテーブル、１０１，１０
２：各回線ごとの中継ホップ数、１０３：実際の送信方
路−ＱｆｙＱｇ＋Ｑｈ：回線キュー、Ｆｌ、Ｆｚ：通信
経路。 第　　２　　　図 第　　　３　　　図 第　　　４　　図 ■ 中継回線 第　　　５゛　　図 （ａ） 第　　６　　　図

Claims (1)

1. 【特許請求の範囲】 １、各宛先交換機までの中継交換機数を記憶したルーテ
   ィングテーブルを備え、該ルーティングテーブルの内容
   と回線ごとのキュー長状態を参照してパケットの送出方
   路を決定するパケット交換網のルーティング制御方式に
   おいて、各々複数の宛先交換機を通過するパケットを送
   信する２以上の回線の中の１つの回線からパケットを送
   出する場合に、該回線のキュー長が所定値を越えて異常
   を生じたとき、上記複数の宛先交換機の中の特定の宛先
   交換機のパケットのみを他の回線に迂回させ、キュー長
   異常が継続するときには、さらに他の宛先交換機を選択
   して、該交換機のパケットも他の回線に迂回させ、キュ
   ー長異常が解消したときには、上記迂回した宛先交換機
   のパケットを元に戻すことを特徴とするパケット交換網
   のルーティング制御方式。 ２、上記特定宛先交換機を選択する場合、キュー長異常
   が生じていないときには、宛先交換機までの中継交換機
   数が最小の回線にパケットを送出し、キュー長異常が生
   じたときには、該キュー長異常が生じた回線の各宛先交
   換機までの中継交換機数を１ずつ増加して、その結果の
   数値に基づいて迂回する宛先交換機を選択することを特
   徴とする特許請求の範囲第１項記載のパケット交換網の
   ルーティング制御方式。