(57)【要約】本発明は、通信ネットワークにおける経路指定に関する。特に、本発明は、通信ネットワークおよびセルラーネットワークにおける経路指定に関する。本発明の概念は、経路指定プロセスを加速するために、ネットワークを前処理することである。この前処理は、難しいネットワーク部分を見つけ出す段階と、トリビアルなネットワーク部分をネットワークトポロジーから取り除く段階とを含む。かかる段階の結果、ネットワークは小さなサブネットワークに分割される。前処理の後に、ネットワークを通る経路を見つけ出すために、シングル経路の所定のエンドポイントがサブネットワークに加えられる。その後に、各サブネットワーク内のトラフィックが個別的に経路指定される。サブネットワーク間、あるいはエンドポイントとサブネットワークとの間のネットワーク部分内のトラフィックは、追加的な経路指定を必要とするであろう。
2004503989.tif 000002
【特許請求の範囲】
【請求項１】
所定のネットワーク要素間のデータストリームのための経路を決定することを含む、ネットワーク要素と伝送リンクとを含む通信ネットワークを通るデータストリームを経路指定するための方法であって、前記経路を決定するプロセスが
少なくとも２つの伝送リンクループに属する伝送リンクを見つけ出す段階と、
（ａ）前記見つけ出す段階において見つけ出された少なくとも１つの伝送リンクを含むループのいずれにも属さない伝送リンクとネットワーク要素とを、ネットワークから取り除き、（ｂ）前記見つけ出す段階において見つけ出された少なくとも１つの伝送リンクを含むループのいずれかに属し、かつ前記見つけ出す段階において見つけ出された多くとも２つの伝送リンクに接続されたネットワーク要素を隠し、それによって残余のネットワークが、少なくとも２つのループを含む少なくとも１つのサブエリアを含むようにする段階と、
各データストリームのために、それを通る、２つの所定のネットワーク要素間の経路を見つけ出すことができるようなサブエリアを見つけ出す段階と、
前記サブエリア内で個別的に経路指定し、もし必要ならば、前記サブエリア間、もしくは前記所定のネットワーク要素と前記サブエリアとの間のネットワーク部分内で個別的に経路指定する段階と、
を含むことを特徴とする方法。
【請求項２】
前記サブエリアを見つけ出す段階が、
前記所定のネットワーク要素そのものであるか、あるいは前記所定のネットワーク要素の近隣ネットワーク要素である、前記２つの所定のネットワーク要素の代りとなるネットワーク要素を、前記見つけ出された前記サブエリア内に見つけ出す段階を、
更に含むことを特徴とする、請求項１に記載の方法。
【請求項３】
前記サブエリアを見つけ出す段階が、
各データストリームのために、前記所定のネットワーク要素間の最短のサブエリア連鎖を見つけ出す段階を、
含むことを特徴とする、請求項１に記載の方法。
【請求項４】
前記経路指定する段階が、
主要経路とバックアップ経路とを決定する段階を、
含むことを特徴とする、請求項１に記載の方法。
【請求項５】
前記伝送リンクを見つけ出す段階が、
前記伝送リンクループを見つけ出す段階と、
少なくとも１つの共通の伝送リンクを有するループを含むエリアを見つけ出す段階と、
前記見つけ出されたループとエリアとを登録する段階と、
を含むことを特徴とする、請求項１に記載の方法。
【発明の詳細な説明】
【０００１】
（技術分野）
本発明は、通信ネットワークにおける経路指定に関する。特に、本発明は通信ネットワークおよびセルラーネットワークにおける経路指定に関する。一般に経路指定という用語は、２つのエンドポイント間でのデータストリーム経路の選択を意味している。本明細書において、経路指定はまた、ネットワーク全体の経路指定、つまりネットワーク内の全てのデータストリームを経路指定するプロセスを意味する。
【０００２】
（背景技術）
ネットワークの経路指定プロセスは、単純な仕事ではない。ネットワークは、例えば３つの主要レベル、すなわち物理レベル、経路レベル、および論理レベルに分けることができる。物理レベルは、ノードと回線とが置かれている実際の物理的ネットワークのことである。経路レベルは、チャンネル（例えばパケット）が如何にしてノードを介して経路指定されたかを明らかにする。このレベルはバックアップ経路選択の関係からも重要である。論理レベルは、シングルノード（例えばベースステーション）がどのようにネットワークを見るか、すなわちいかに透過接続を描写するかということである。経路指定の作業を行なうためには、これらの全ての階層が考慮されなくてはならない。
【０００３】
ネットワークは、数百あるいは数千ものノードを含む大きさを持つこともあり得る。上記の諸点を考慮に入れると、ネットワークの経路指定は非常に時間のかかる作業である。一般に経路指定方法は、最良もしくは最良に近い経路を計算するアルゴリズムに基づいている。高度なアルゴリズムは良い結果を生じるのが普通であるが、通常それらは時間がかかる。他方、粗いアルゴリズムから得られる結果は劣るけれども、速度は速い。現在のところ、良好な結果を迅速に得るためには、非常に高速のコンピュータが使用される。
【０００４】
経路指定の問題を幾つかの小部分に分割し、それらの小部分を個別に解決することも可能である。この場合、分割はできるだけ少数の共通のパラメータを有するエンティティに基づいて行なわれる。すなわちエンティティ間に存在するインタフェースの数ができるだけ少数になるように行なわれる。経路指定の問題を解決するもう１つの方法は階層的技法であり、この技法では、先ず始めに最重要のパラメータが解決されて固定され、その後に次の組のパラメータが解決されて固定されるといった操作が、残りのパラメータが無くなるまで繰り返される。上述の分割技法と階層的技法は、通常、両方とも時間のかかる人手による作業を必要とする。
【０００５】
高価な高速コンピュータが常に使用できるとは限らない。上等なアルゴリズムを用いて時間を多く費やすことは、あまりにも時間がかかり過ぎる。ネットワークを小さなサブネットワークに分割することは、高価で時間のかかる人手による作業を要する。しかしながら、従来のネットワークより遙かに大きく、しかも益々大きさを増しつつある新しいセルラーネットワークのためには、高速の洗練された経路指定方法が特に重要である。本発明の目的は、公知の解決方法に伴う上述の欠点を緩和して、それらの効率を高めることである。この目的は特許請求の範囲に記載した方法により達成される。
【０００６】
（発明の開示）
本発明の概念は、経路指定プロセスを加速するために、ネットワークを前処理することである。この前処理する段階は、難しいネットワーク部分を見つけ出す段階と、トリビアルなネットワーク部分をネットワークトポロジーから取り除く段階とを含む。このような段階の結果、ネットワークは小さなサブネットワークに分割される。かかる前処理段階の後に、ネットワークを通る経路を見つけ出すために、シングル経路の所定のエンドポイントがサブネットワークに加えられる。その後、各サブネットワーク内のトラフィックが個別的に経路指定される。サブネットワーク間、あるいはエンドポイントとサブネットワークとの間のネットワーク部分におけるトラフィックは、追加の経路指定を必要とするであろうが、それらは簡単に実行できる。
【０００７】
（発明を実施するための最良の形態）
以下に、添付図面の図１から図６により、本発明を更に詳細に説明する。図１は典型的な通信ネットワークの一例を示す。ネットワークを前処理する目的は、経路指定困難な部分を見つけ出すことと、トリビアルで経路指定容易な部分を取り除くことである。経路指定困難な部分をサブネットワークと呼ぶことにする。サブネットワークが見つけ出された場合の経路指定は、ネットワーク全体について経路指定するよりもずっと容易である。前処理は各サブネットワーク内で個別に経路指定することを可能にし、しかも良好かつ迅速な経路指定アルゴリズムの効果的使用を可能にする。前処理することは殆ど全ての経路指定アルゴリズムに適用可能である。前処理することに関する説明を分り易くするために、図１において、或るネットワークに属するノード（１）には正方形のマークを付けている。論旨を理解するために、以下の定義を記憶に留められたい。
１．エッジとは、所望の経路ネットワークレベル内の２つのノード間の伝送リンクのことであり、すなわち、例えば、物理リンク、論理リンク、またはＳＤＨストリームリンクを指す。
２．サイクルとは、同一ノードから出発して同一ノードで終わる、少なくとも３つのノードを含む経路のことである。或るサイクルが使用するエッジの組が、他のサイクルが使用するエッジの組と異なるならば、それらのサイクルは異なるサイクルである。
３．１つ又はそれ以上の異なるサイクルがそれを通る場合、そのエッジはメッシュエッジである。
４．メッシュとは、重なり合うサイクルを形成するメッシュエッジまたはメッシュエッジのエンドポイントノードを含むネットワーク部分のことである。ネットワーク内には幾つかの別個のメッシュが存在し得る。
【０００８】
サブネットワークを見つけ出すために、ネットワークのメッシュエッジが見つけ出されなくてはならない。メッシュエッジ（およびメッシュ）を見つけ出すための１つの方法は、エッジ彩色アルゴリズムを用いることである。背景カラーと２組のカラーとがあり、該２組のカラーはサイクルカラーおよび領域カラーと呼ばれる。最初、全てのエッジは背景カラーである。ネットワークの吟味は、探索樹がそこで創り出される任意のノード（Ｓ）（図１を参照）から始められる。探索樹は新たなエッジが見つけ出されるにつれて成長する。図１は拡がりつつある探索樹の一例を示している。最も古い枝はｂ１で、次に古い枝はｂ２で、そして最も若い枝はｂ７で示す。そこで枝が交叉する、関心の対象であるノードは、大文字Ｘ、Ｙ、Ｚで示されている。探索樹の枝が別の枝と交叉する時、サイクルが見つけ出されたことになる。このサイクルは、エッジの色をチェックすることによって吟味される。全てのエッジが背景カラーであるならば（交叉ノードＸ）、そのサイクルは新しいサイクルであって、新たなサイクルカラーで彩色される。領域カラーをもつエッジは皆無であるが、サイクルカラーをもつエッジが少なくとも１つ存在するならば（交叉ノードＹ）、そのサイクルと全ての混ざり合うサイクル内のエッジとは新たな領域カラーで彩色される。領域カラーをもつエッジが存在するならば（交叉ノードＺ）、その新しいサイクルのエッジはメッシュエッジである。この新しいサイクルと全ての混合サイクルは、同じ領域カラーで彩色される。ネットワーク全体が探索された後、全てのメッシュは異なる領域カラーで彩色され、非メッシュサイクルはサイクルカラーで彩色され、残りのエッジは背景カラーで彩色される。それぞれのメッシュとサイクルが異なる識別カラーで彩色されることは注目に価する。図２は見つけ出されたメッシュを破線で示している。これらのエッジ彩色アルゴリズムは、ユニオンファインド・アルゴリズムを用いることによって実装可能である。
【０００９】
メッシュを見つけ出した後、それらのメッシュのいずれにも属さないノードとエッジは、ネットワークから取り除くことができる。メッシュに属し、かつ２つ又はそれ以上のメッシュエッジに接続されていないノード（等級２ノード）は隠される。今やネットワークからサブネットワーク（図３）が分離された。上述のプロセスは樹状部分（２）（図１）とシングルサイクル（３）（図１）を両方とも取り除くことに注目されたい。
【００１０】
サブネットワークは、共通ノードにより、あるいはサブネットワーク間のネットワークの非メッシュ部分により、互いに接続されている。図４は上記ネットワークのサブネットワーク間の接続を示している。小円は、共通ノード（４）、もしくは２つのメッシュ間の非メッシュネットワーク部分（６）へ接続されたノード（５）であるゲートウエイノードを示している。メッシュの等級２ノードはゲートウエイノードであり得ることに注目されたい。
【００１１】
今や前処理は終了したので、それぞれのトラフィック要求のための経路が、ネットワーク全体にわたって見つけ出されなくてはならない。それぞれのトラフィック要求は、先ず始めにサブネットワーク連鎖（図４）（および非メッシュネットワーク部分）にわたって経路指定される。すなわち、適切なサブネットワークが見つけ出される。ゲートウエイノードはそれぞれのトラフィック要求のための各サブネットワークにおいて定義される。もしサブネットワークが経路の全ての所定のエンドポイントを含まないならば、サブネットワークの変更が必要である。なくなっていたエンドポイント（Ａ、Ｂ）（図５）が、サブネットワーク内の代りのエンドポイントを用いることにより、サブネットワークに加えられる。起こり得る２つの場合があるが、その第１は、１）エンドポイントノード（Ａ）が新しいエッジ（７）を介してサブネットワーク内のノード（Ａ’）に接続される場合である。この場合、メッシュの等級２ノードは接続ノードではあり得ないことに注目されたい。その第２は、２）エンドポイントノード（Ｃ）がメッシュの等級２ノードである場合である。この場合、等級２ノードからのエッジ（Ｅ１、Ｅ２）は、サブネットワークの対応するエッジ（Ｅ１＋Ｅ２）と置き換わる。
【００１２】
サブネットワーク連鎖を通る経路が見つけ出された後、それぞれのサブネットワーク内のトラフィックは、個別的に経路指定できる。元のネットワーク内で対応する経路を得るために、サブネットワークのそれぞれのエッジは、元のネットワーク内の経路と対応している。エンドポイントからサブネットワークのノードまでの接続（７、８）内のトラフィックと、サブネットワーク間の相互接続（９）内のトラフィックは、経路指定を必要とするが、これらを指定することは容易である。トラフィック要求は、実装に応じて、一時に１つずつ経路指定可能か、あるいは同時に経路指定可能である。
【００１３】
図５は前処理されたサブネットワーク内のエンドポイントＡ、Ｂ間の経路指定を示している。選択された経路（Ｓ）は太実線で、バックアップ経路（Ｒ）は点線で表してある。サブネットワーク間の相互接続は破線で囲まれている。図６は元のネットワークにおける対応する経路指定を示している。
【００１４】
図７は本発明をフロー図形式で示したものである。第１の段階（６１）はメッシングエッジを見つけ出すことである。その後、メッシュエッジのいずれにも続されていないノードと非メッシュエッジとが取り除かれる（６２）。第３の段階（６３）は、２つのメッシュエッジに接続されたノードを隠すことである。第３の段階後に、各トラフィック要求のための適切なサブネットワーク連鎖が見つけ出され（６４）、また、その要素が所定のネットワーク要素間の各経路のためのエンドポイントの代わりとなるサブネットワーク内のネットワーク要素も見つけ出される。その後の最終段階（６５）は、各サブネットワーク内で個別的に経路指定することである。また、もし必要ならば、非メッシュネットワーク部分（エンドポイント接続、サブネットワーク間の接続）内のトラフィック要求も同様に経路指定される。
【００１５】
本発明は、トリビアルなネットワーク部分が存在し、かつ小さなサブネットワークに分割することができる通信ネットワークにおいて良好に機能する。前処理することは、極めて迅速に実行可能である。本発明は経路指定のための迅速な方法を提供する。極度に高速なコンピュータは必要とされず、通常のコンピュータにより許容し得る長さの時間内に経路指定を行うことが可能である。経路指定の結果は良好である。コストが嵩み、しかも時間のかかる人手による作業は必要とされない。本発明を上述の幾つかの例によって説明したが、本発明は、これらの例に限定されるものではなく、本発明概念の範囲内においてその他の解決策においても同様に用いられることができることは明らかである。
【図面の簡単な説明】
【図１】通信ネットワークの１例を示す。
【図２】通信ネットワーク内に見つけ出されたメッシュエッジを示す。
【図３】図１に示す通信ネットワーク上のサブネットワークを示す。
【図４】図３に示すサブネットワーク間の接続を示す。
【図５】前処理されたサブネットワーク内における経路指定を示す。
【図６】通信ネットワークを通る物理的経路を示す。
【図７】本発明をフロー図で示したものである。
【図７】
2004503989.tif 000003
【国際公開パンフレット】
2004503989.tif 000004
2004503989.tif 000005
2004503989.tif 000006
2004503989.tif 000007
2004503989.tif 000008
2004503989.tif 000009
2004503989.tif 000010
2004503989.tif 000011
2004503989.tif 000012
2004503989.tif 000013
2004503989.tif 000014
2004503989.tif 000015
2004503989.tif 000016
2004503989.tif 000017
【国際調査報告】
2004503989.tif 000018
2004503989.tif 000019
2004503989.tif 000020