説明

多数の仮想回路を決定する方法

【目的】 本発明はネットワーク内の多数の仮想回路の経路付けに関する。
【構成】 多数の下層階をを経路づける方法が開示され、それでは多数の仮想回路がリクエストされるとき使用可能な情報が使用され、仮想回路の経路を決定する。その後、経路付け選択は、全ての仮想回路を経路づける時のコスト全体が減るようにコスト関数に従って改善される。

【発明の詳細な説明】
【0001】
【産業上の利用分野】本発明はネットワーク内の多数の仮想回路の経路付けに関する。
【0002】
【従来の技術】コンピュータシステムはネットワークに接続されたホストマシーン間で情報(例えば、データ、音声、テキスト、ビデオ等)を交換し伝達する基本的手段である。ネットワークは、リンクにより、互いに接続され、またホストに接続されたノードを有する。一般に、各リンクは双方向性であり、即ち、情報は順方向と逆方向に運ばれ、各リンクは各方向のバンド幅容量により特徴づけられる。
【0003】ネットワーク動作における重要な点は、情報がどのように経路づけられるかを考えることである。情報が2つの特定のホスト間で交換されるべきとき、双方向性経路がネットワークのそれらの間で確立される。一般に、確立される経路は、いわゆる”仮想回路”(VC)であり、それにより、ホストは情報の宛先を単に特定するだけであり、回路が宛先に接続されているかのようにネットワークは情報を配給することを意味する。情報を配給するために多くの異なるルートと技術のうちの1つが選択できるが、特定の選択はホストには関係ない。経路付けのタスクは、ノード間のリンクとノードを選択することであり、VCにより取られる経路であるリンクは、ネットワークの資源を効率的に利用するように、例えば、特定のリンクのバンド幅容量を超えることなく、できるだけ多くのVCを決定するように取られる。このことは、選択された経路のために必要なネットワークの資源の量を反映するあるコスト関数を最小にするように経路を選択することによりしばしば達成される。種々のコスト関数が使用できるが、一般にコスト関数は現在のネットワークの状態(即ち、ネットワークトポロジーとネットワークの資源の現在の割り当て)、ネットワークでの遅延等を考慮している。重要なことは、経路付けの問題は、”オンライン”即ち、将来の経路付けの需要がネットワークの資源にどのような影響を持つかの知識なしに、経路付けが実行されなければならないという点にあり、しばしばかなり複雑である。この問題は、いわゆる”ダイナミック再経路付け”技術により解決されるが、これらの技術は一般にネットワークのユーザーに提供されるサービスの質に悪影響を及ぼす。
【0004】VCを経路づけるための多くの技術が提案されている。そのような技術の1つは、最小ホップ経路付けであり、それでは、最小ノード数を通る経路が選択される。提案されている他の技術では、指数コスト関数とスケーリングが使用される。J.アスプネス等による”マシンスケジューリングと仮想回路経路付けへの応用に関するオンライン負荷バランス”(1993年5月、カリフォルニア、サンディエゴでの計算理論についてのProc.23回Annualシンポジウム)を参照。スケーリング技術では、各リンクのバンド幅容量の一部γが最初に割り当てられ、コスト関数がその割り当てられたバンド幅に与えられた経路を決定するために計算される。経路付けがその割り当てられたバンド幅でネットワーク内ではもはや達成することができないとき、より多くのバンド幅が割り当てられる。即ちγが増加させられる。一般に、リクエストされたVCに対する経路内のあるリンクのためのコストを決定するための関数は
【数1】


であり、ここで、Cl (x,Δx)は経路内のリンクlに対するコストであり、aは定数、xl は使用中のリンクのバンド幅容量の分数であり、Δxl はVCによりリクエストされるリンクのバンド幅容量の分数である。
【0005】
【発明の概要】しかしながら、これらの技術は欠点がある。特に、我々が認識した問題は、従来の経路付けの方法が”多数のVCリクエスト”が存在する状況で使用できる情報を考慮していないことであった。そのような状況では、あるときには、ネットワークはVCを確立するための2以上のリクエストを同時に受信する。従来の方法では、VCに対する多数のリクエストのうちの1つに単に応答して、他のリクエストによる需要を決定するためのチェックなしに、例えば、先入れ先出し原理に従って、リクエストされたVCを決定している。こうして、経路付けは、真に上記の”オンライン”形式であり、他のリクエストが同時に受信されたという事実の結果として更なるネットワーク経路付けによる需要がどれだけあるかについての情報をネットワークは持たない。
【0006】本発明によれば、仮想回路に対するリクエストにより経路づけを行う際に、同時にリクエストされた仮想回路についてのその情報が使用できるのは有利であるという認識であった。従って、各リクエストが1以上のパラメーターにより特定される仮想回路の同時のリクエストの組を、複数のリクエストの1以上のパラメーターの関数としてその組の各リクエストに対して経路づけることにより、経路づける方法が開示される。本発明の一実施例では、同時リクエストの組が、1以上のパラメーターにしたがって並べられリクエストがその順番に経路づけられる。本発明の特徴によれば、仮想回路の多数のリクエストから使用可能な情報をより広く活用するようにローカルサーチを用いることにより経路付けが改善できる。
【0007】
【実施例】図1は、本発明によるネットワークの構造を示す。ホスト102−i(i=1、2、・・・)はネットワーク106を介して情報を交換する。ネットワーク106は、ノード108−j(j=1、2、・・・)を互いに接続し、ホスト102−iに接続するリンク110−k(k=1,2,・・・)を具備する。ノード対は1以上のリンクにより接続されていてもよい。
【0008】図1のネットワーク106は中央経路付けシステムであり、ネットワーク106は、そこで中央経路付けリクエストプロセッサ111の使用を通して経路付けのための完全な情報を利用する。リクエストプロセッサ111はホスト102−i(i=1,2,・・・)と接続され、ネットワークの状態について完全な情報をえる。こうして、ネットワークを通る何らかの経路(即ち。何らかの経路のために必要な付加的なネットワーク資源)に対するコストが決定でき、以下に説明する本発明の方法を使用して、図1のネットワーク106内の全てのVCが、ある基準、例えば決定されるバンド幅の全体量を最大化する観点で効率的に経路付けされる。
【0009】図2は、本発明の経路付け方法のフローチャートを示す。図2のステップ200で、あるときに、ネットワークはVCを確立するためのimax (imax =0,1,2,・・・)のリクエストの組に応答しなければならない。各個別のリクエストVCireq(i=1,・・・、imax )は1以上のパラメーターにより特定される。例えば、各VCireq はソースホストSi 、宛先ホストDi 、送信方向にリクエストされるバンド幅Bif、及び逆方向にリクエストされる帯域Birにより特定される。こうして、VCireq=(Si ,Di ,Bif,Bir)である。
【0010】図2のステップ205では、多数のVCリクエストがある状況で使用可能な情報が経路付けに際して使用される。特に、リクエストの組のうちの各個々のリクエストに対して、経路はその組の複数のリクエストの1以上のパラメーターの関数に従って選択される。本方法の実施例は、共通に譲渡され、同時に出願された同時継続米国出願”永久仮想回路の経路付けの方法”に述べられており、それは引用によりここに組み込まれる。この実施例では、リクエストのパラメーター、例えば、バンド幅に従ってリクエストを最初に並べ(順序づけ)、その後、指数コスト関数を用いてリクエストを経路づけることにより、永久VC(時間、あるいは日の間動作するように設計された切り換えVCとは反対に、年のオーダーの間動作し確立されたままであるように設計されたVC)を経路づけている。順序づけのプロセスでは、これらのリクエストのうち、コスト関数に従って最多のネットワーク資源を要求し、こうして経路付けに際して最多の柔軟性を要求するものが最初に経路づけられる。経路付けの目的が、バンド幅を保存することであれば、要求された全体のバンド幅(順方向と逆方向)の大きい順にVCireqを並べることが有利であり、その結果大きなバンド幅を要求するリクエストを、あるリンクのバンド幅容量を超える危険性を増加させることなく収納することができる。
【0011】当業者は多数の(切り換えあるいは永久)VCリクエストが存在する状況で使用可能な情報が種々の手法で、必ずしも指数関数ではない種々のコスト関数と共に使用できるということを認識するであろう。例えば、リクエストは先入れ先出しに基づいているが、リクエストの組のうちのリクエストの平均バンド幅要求が何であるかについての知識を用いて経路づけすることもできる。こうして、特定のリクエストが経路づけられるとき、経路付けのためのコスト関数は、リクエストがその組の他のリクエストに比べて大きいあるいは小さいバンド幅を要求するか否かを反映することができ、それにより、大きなバンド幅を必要とするリクエストに対する他のリンク上のバンド幅を保存するように、比較的小さいバンド幅を必要とするリクエストをほとんど容量一杯に近いリンク上に経路づける。
【0012】ステップ205に戻って、一旦経路Pの組が決定されると、オプションとしてのローカルサーチが以下のように実行され、経路選択の組を改善する。図2の方法のステップ275で、リクエストの組は経路Pの組上で経路付けされる。
【0013】ステップ265のオプションローカルサーチは、経路の選択を改善するために使用され、全てのVCを経路づけるための全体のコストを減少させることができる。ステップ265のローカルサーチの一実施例でのステップは図3のフローチャートに示される。ステップ305では、変数が初期化される。特に、Pは、経路付け方法、例えば、図2の方法により決定されるimax VCリクエストと関連する経路{p1 ,p2 ,・・・,pimax}の組として定義される。経路付けのための最良の経路の現在の組は、P* 内に格納され、最良の経路の現在の組を決定するコストはC* である。初めに、P* =P、C* =C(P)であり、ここで、Cは以下に説明する第二のコスト関数であり、それは全てのVCireqを経路づけるコストを決定する。ステップ310では、インプフラグ(impflag)と呼ばれるフラグが0にセットされ、カウンタi(i=1,2、・・・,imax )は1にセットされる。
【0014】
【外1】


【0015】ステップ315ー340が各連続するVCireqに対して繰り返される。全てのi(i=1,2,...,imax )が潜在的再経路付けのために調べられたとき、インプフラグは経路付けの改善が可能かどうかを知るためにチェックされる。インプフラグが0ならば、いずれのVCireqの他の経路付けによっても全てのVCireqの経路付けのコストが減少せず、そのサーチは終了される。ステップ345に示されるように、インプフラグが1にセットされていれば、1つのVCireqに対する他の経路付け(即ち、新しい最短経路)が存在し、経路付けコストの最大の減少をもたらす。ステップ355で、P* に反映された新しい最低のコスト経路はPとなる。今やVCireqがコストC(P* )でPに従って経路づけられる。ステップ310−355が、コストを減少させる新しい経路が見つからなくなるまで繰り返される。
【0016】第二のコスト関数は、
【数2】


として選択されることが有利である。ここで、式の中の変数は、式1に関して定義され、各指数項と線形項の合計は関連する経路が外側の合計内でリンクを使用するように全てのVCireqに渡っている。こうして、第二のコスト関数は関連する経路上の多数のVCireqを経路づける全体のコストを与える。
【0017】図3のステップは、いわゆる”どん欲な”帰納的な方法を反映し、それでは各VCireqに対する各可能な他の経路が、何であれ、他の経路のどれが最大量だけ経路付けコストを減少させるかを知るために調べられる。その後この他の経路がVCと関連する新しい経路として選択される。このプロセスは、何れのVCreqに対する他の経路も全てのリクエストを経路づけるコストを減少させなくなるまで繰り返される。当業者は、他のサーチ基準を使用する他のローカルサーチが使用できることを認識できるであろう。例えば、全てのVCreqを経路づけるコストを最大に減少させるものを見つけるために全ての他の経路を通るサーチに代えて、いくらかの量だけコスト減少させる最初の他の経路を単に見つけるだけで十分であってもよい。その後、サーチは単に次のVCireqに進む。この”どん欲でない”帰納的な方法は別に解空間をサーチし、”どん欲な”帰納的な方法よりよい”ローカルミニマム”に潜在的に収束することができる。これは、ネットワークの現在の状態と経路づけられるべきVCireqのリストに大いに依存する。
【0018】図4は、分散ネットワークの構造を示し、それはノード418−mとリンク420−nを具備し、本発明の方法が適用されている。ネットワーク416は、分散経路付けシステムであり、各ノード418−mは周期的に状態情報を交換する。この状態情報は、あるノードから各隣のノードまでリンク上の使用可能なあるいは使用中のネットワーク資源の量を反映する。こうして、ネットワークを通してのある経路に対するコストが決定できる。しかしながら、VCireqが確立され、あるいは裂かれた速度に関して状態情報が急速に伝搬しなければ、情報は不完全である(たとえば、日時が決められる)。こうして、各ノードはネットワークの状態の異なる記述を持ち、今記述はローカルネットワーク状態と呼ばれる。上記の方法は、不完全な状態情報(即ちローカルネットワーク状態)が使用されることを除いて分散経路付けシステム内で使用できる。しかしながら、(図2のステップ275の経路付けの例に関して)VCireqが実際に経路付けされるべき時、不完全な情報に基づいて決定された経路はもはや使用することはできない(例えば、最も最近の状態情報が受信されてからリンクの容量が用い尽くされている)場合があることに注意すべきである。成功裏に経路付けされないVCに対するリクエスト、たとえば選択された経路が使用できないリクエストは、リクエストの次の組に含めてもよいし、あるいはリクエストの新たな組を形成してもよい。分散経路付けシステムで経路付けするとき、リクエストの組の全体が経路付けされるまで、ローカルネットワークの状態を更新しないことは有利であることに注意すべきである。これにより、図3のサーチルーチンのような手順が終了できることが保証される。
【0019】この開示は、多数VCリクエスト状況に置いて使用可能な情報を用いて多数仮想回路リクエストを経路づける方法を説明する。個々に開示された方法は、特定のハードウェアあるいはソフトウェアを参照することなしに説明された。代わって、方法は、当業者が使用可能なハードウェアとソフトウェアを容易に適応させ、あるいは特定の応用のために好ましく適応させることが可能なように説明した。
【図面の簡単な説明】
【図1】本発明の中央経路付けネットワークを示す図である。
【図2】実施例におけるステップのフローチャートである。
【図3】本発明のローカルサーチの特徴のステップのフローチャートである。
【図4】本発明による分散経路付けネットワークを示す図である。
【符号の説明】
101 リクエストプロセッサ
102−1,...,102−5 ホスト
108−1,...,108−3 ノード
412−1,...,412−5 ホスト
418−1,...,418−3 ノード

【特許請求の範囲】
【請求項1】 仮想回路に対するリクエストの組を経路づける方法であって、仮想回路に対するリクエストの組を受信するステップと、ここで、各リクエストは1以上のパラメーターにより特定され、及び複数の前記リクエストの1以上のパラメーターの関数として前記リクエストの組の各リクエストを経路づけるステップとを含む方法。
【請求項2】 ネットワークにおいて仮想回路に対するリクエストを経路づける方法であって、リクエストの組を受信するステップと、ここで、前記リクエストの組の各リクエストは前記ネットワークを通して永久仮想回路を経路づけるリクエストを表し、各リクエストは1以上のパラメーターにより特定され、及び第一の関数に従って選択された前記ネットワークを通る経路上に各リクエストを経路づけるステップと、ここで前記経路は各リクエストを特定する前記パラメーターを満足し、前記第一の関数は複数の前記リクエストの前記パラメーターの関数であるを含む方法。
【請求項3】 前記ネットワークは前記ネットワークの状態を有し、前記方法は、前記選択された経路を反映するように前記ネットワークの状態を更新するステップを更に含む請求項2記載の方法。
【請求項4】 前記経路付けするステップに先立ち前記1以上のパラメータの関数に従う順番で前記リクエストを確立するステップを更に具備し、前記経路付けステップは前記順番で前記リクエストを経路付けする請求項2記載の方法。
【請求項5】 前記ネットワークは、リンクの組とノードの組を具備し、ここで、第一のノードと第二のノードは前記リンクの組の1以上のリンクにより接続され、前記ネットワークを通る各選択された経路はリンクの組により特定される請求項2記載の方法。
【請求項6】 各選択された経路は第一のホストと第二のホストを接続する請求項2記載の方法。
【請求項7】 前記選択された経路の1つに対して他の経路を選択するステップと、前記他の経路を用いて第二の関数の値を決定するステップと、及び前記選択された経路を用いて前記第二の関数の値を決定するステップとを含み、前記他の経路が前記選択された経路と比べて前記第二の関数の値を改善すれば、前記他の経路で前記選択された経路を置換するステップとを更に含む請求項2記載の方法。
【請求項8】 他の経路を選択するステップと、前記第二の関数の値を決定するステップと、及び置換するステップを、他の経路の選択が前記第二の関数を改善しなくなるまで繰り返すステップを更に含む請求項7記載の方法。
【請求項9】 前記ネットワークは前記ネットワークの状態を有し、前記第二の関数は前記パラメーターの1以上のものと前記ネットワークの状態との関数である請求項7記載の方法。

【図1】
image rotate


【図2】
image rotate


【図4】
image rotate


【図3】
image rotate


【公開番号】特開平7−271688
【公開日】平成7年(1995)10月20日
【国際特許分類】
【出願番号】特願平7−65412
【出願日】平成7年(1995)3月24日
【出願人】(390035493)エイ・ティ・アンド・ティ・コーポレーション (130)
【氏名又は名称原語表記】AT&T CORP.