(57)【要約】本発明は、トラフィック分散を有するパケット網（Ｎ１）、例えば自律システムにおけるデータパケット（ＩＰパケット）のルーティングに関する。本発明の枠内では、データパケット（ＩＰパケット）の転送ないしはルーティングは、データパケット（ＩＰパケット）のアクセスインタフェースについての情報（Ｋ１）と、出口インタフェースについての情報（Ｋ２）とに基づいて行われる。これらの２つの情報（Ｋ１，Ｋ２）は、例えば、データパケット（ＩＰパケット）の入口インタフェースにおいて情報フィールドないしはラベル（ＩＬ，ＥＬ）として前置される。本発明により、トラフィック分散の意味で、手頃なコストおよび限定された複雑さでフレキシブルかつループのないルーティングが可能になる。
2005536163.tif 000002
【特許請求の範囲】
【請求項１】
ルータによって形成される、トラフィック分散を有するパケット網（Ｎ１）にてデータパケットをルーティングする方法において、
データパケット（ＩＰパケット）をパケット網（Ｎ１）の内部ルータによって転送し、
当該のデータパケット（ＩＰパケット）の転送を少なくとも、データパケット（ＩＰパケット）のパケット網（Ｎ１）へのアクセスインタフェースについての情報（Ｋ１）と、データパケット（ＩＰパケット）がデータ網（Ｎ１）を離れるべき出口インタフェースについての情報（Ｋ２）とに基づいて行うことを特徴とする、
データパケットをルーティングする方法。
【請求項２】
前記のアクセスインタフェースにてデータパケット（ＩＰパケット）に識別情報を付与し、
該識別情報に基づき、内部ルータにより、前記のアクセスインタフェースおよび出口インタフェースを識別する、
請求項１に記載の方法。
【請求項３】
前記識別情報には、前記のアクセスインタフェースおよび出口インタフェースに対するネットワークアドレスまたは識別子（Ｋ１，Ｋ２）が含まれる、
請求項２に記載の方法。
【請求項４】
前記のアクセスインタフェースにてデータパケット（ＩＰパケット）に少なくとも１つの情報フィールド（ＩＬ，ＥＬ）を付与し、
前記の内部ルータにより、１つまたは複数の情報フィールド（ＩＬ，ＥＬ）から、パケット（ＩＰパケット）のパケット網（Ｎ１）へのアクセスインタフェースについての情報（Ｋ１）と、出口インタフェースについての情報（Ｋ２）とを取り出す、
請求項３に記載の方法。
【請求項５】
前記データパケット（ＩＰパケット）に情報フィールドを付与し、
該情報フィールドは、ヘッダまたはトレーラとしてデータパケットに付け加えられ、
前記情報フィールドは、アクセスインタフェースおよび出口インタフェースの識別子（Ｋ１，Ｋ２）を含む、
請求項４に記載の方法。
【請求項６】
前記のデータパケット（ＩＰパケット）に２つの情報フィールド（ＩＬ，ＥＬ）を付与し、
該情報フィールド（ＩＬ，ＥＬ）をそれぞれヘッダまたはトレーラとしてデータパケット（ＩＰパケット）に付け加え、
一方の情報フィールド（ＩＬ）はアクセスインタフェースの識別子（Ｋ１）を、他方の情報フィールド（ＥＬ）は出口インタフェースの識別子（Ｋ２）を含む、
請求項４に記載の方法。
【請求項７】
少なくとも１つの情報フィールド（ＩＬ，ＥＬ）にビット列（ＬＣ*）を付け加えるかまたは前置し、
該ビット列により、情報フィールド（ＩＬ，ＥＬ）を情報フィールドとして識別する、
請求項５または６に記載の方法。
【請求項８】
前記の入口インタフェースにてデータパケット（ＩＰパケット）に少なくとも１つの情報フィールド（ＩＬ，ＥＬ）を付与し、
該情報フィールド（ＩＬ，ＥＬ）を出口インタフェースにて元のように除去する、
請求項５から７までのいずれか１項に記載の方法。
【請求項９】
少なくとも１つの情報フィールド（ＩＬ，ＥＬ）をＭＰＬＳラベルによって得る、
請求項４から８までのいずれか１項に記載の方法。
【請求項１０】
前記識別情報を、データパケット形式の枠内で設けられたフィールドに書き込む、
請求項３に記載の方法。
【請求項１１】
前記の出口インタフェースを識別子（Ｋ２）によって参照し、
パケット網（Ｎ１）を横断した後にデータパケット（ＩＰパケット）を転送すべきネットワーク（Ｎ３）のネットワークアドレスに基づいて出口インタフェースの識別子（Ｋ２）を識別し、
ネットワークアドレスに基づき、入口インタフェースにおけるテーブルを用いて、出口インタフェースの識別子（Ｋ２）の識別する、
請求項１から１０までのいずれか１項に記載の方法。
【請求項１２】
前記のアクセスインタフェースにてデータパケット（ＩＰパケット）に識別情報を付与し、
該識別情報に基づき、内部ルータによってアクセスインタフェースを識別し、
該識別情報は、アクセスインタフェースのネットワークアドレスまたは識別子（Ｋ１）を含んでおり、
内部ルータは、データパケットから抽出されるアドレス情報に基づいて出口インタフェースについての情報（Ｋ２）を求める、
請求項１に記載の方法。
【請求項１３】
前記内部ルータにより、データパケット（ＩＰパケット）から抽出したアドレス情報に基づいて、アクセスインタフェースについての情報（Ｋ１）および出口インタフェースについての情報（Ｋ２）を求める、
請求項１に記載の方法。
【請求項１４】
前記のデータパケット（ＩＰパケット）の転送をルーティングテーブルによって行い、該ルーティングテーブルにより、データパケット（ＩＰパケット）のパケット網（Ｎ１）へのアクセスインタフェースについての情報と、また出口インタフェースについての情報（Ｋ２）とを次ホップに対するネットワークアドレスに割り当てる、
請求項１から１３までのいずれか１項に記載の方法。
【請求項１５】
前記のアクセスインタフェースにて、フロー識別する情報フィールドをデータパケット（ＩＰパケット）に付与し、
データパケット（ＩＰパケット）の転送を、内部ルータにより、前記情報フィールドにしたがって行う、
請求項１から１４までのいずれか１項に記載の方法。
【請求項１６】
パケット網（Ｎ１）における内部ルータにおいて、
データパケット（ＩＰパケット）のパケット網（Ｎ１）へのアクセスインタフェースについての情報（Ｋ１）と、出口インタフェースについての情報（Ｋ２）とが次ホップに対するネットワークアドレスに割り当てられることを特徴とする、
請求項１から１５までのいずれか１項に記載の方法を実施するための内部ルータ。
【請求項１７】
パケット網（Ｎ１）のエッジルータにおいて、
パケット網（Ｎ１）を横断した後、データパケット（ＩＰパケット）を転送すべきネットワーク（Ｎ３）のネットワークアドレスに基づいて、データパケット（ＩＰパケット）の出口インタフェースの識別子（Ｋ２）を識別するためのテーブルを有することを特徴とする、
請求項１１に記載の方法を実施するためのエッジルータ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、トラフィック分散（Verkerverteiling）を有するパケット網においてデータパケットをルーティングする方法、エッジルータ（Randrouter）および内部ルータに関する。
【０００２】
ネットワーク技術者ならびにルーティングおよびインターネットエキスパートの重要な仕事の領域の１つはパケット網を発展させることである。この発展の重要な目標は、パケット網を介して広範で多彩なサービスを提供できるようにすることである。
【０００３】
データ伝送するための従来の適用の他に、例えば電話（例えばボイスオーバーＩＰ）およびリアルタイムでの画像情報の伝送（例えばビデオオンデマンド、ビデオ会議）などのリアルタイム性が要求されるますます多くのサービスを、パケット網を介して実現すべきである。ここから新たな要求がパケット網に対して発生する。リアルタイム性が要求されるサービスに対して品質特性を維持することが最も重要である（この関連においてquality of service 略してQoSがしばしば問題になる）。
【０００４】
現在最も広く知られたパケット網は、ＩＰ（Internet Protocol）プロトコルに基づいている。その成果の大部分は、それが比較的複雑でないことと、そのフレキシビリティが高いこととによって説明される。この両者は、ＩＰネットワークにおいてパケットを搬送する仕方に由来する。
【０００５】
ＩＰネットワーク内ではパケットは、そのＩＰアドレスに基づいてルーティングされる。ほとんどの場合、このルーティングは、ホップベースで行われる。すなわち、個々のルータは、パケットアドレスに基づいて宛先、すなわち通例は別のルータを識別し、この別のルータに各パケットが転送されるのである。複数のルータからなるチェーンを介する伝送の終わりにはパケットは宛先アドレスに配達される。多くの場合にあの宛先アドレスは、ホストまたはゲートウェイである。
【０００６】
個々のルータは、通例、次ホップないしはつぎの区間を越える、伝送パスに関連する情報を有しない。これによってルーティングテーブルの維持および管理は、比較的コストがかからないのである。さらにこの方法は、択一的な宛先および標準的な宛先を次ホップに対して設けることができるという点でフレキシブルである。ここでこれらにより、例えば、障害時またはアドレスが未知の際にパケットの伝達が保証されるのである。
【０００７】
従来のルーティング技術によるＩＰネットワークは、リアルタイムトラフィックに適していない。パケットの遅延および損失は、十分に強力なコントロールの支配下にないため、リアルタイム伝送に必要な品質特性を保証することはできないのである。
【０００８】
伝送パラメタをより良好にコントロールする方法には、リアルタイム要求を有するサービスに対して伝送容量をリザーブすることと、ネットワークにおける伝送パスを前もって設定しておくこととがある。ＩＰネットワークにおける帯域幅をリザーブするために、ＲＳＶＰ（Resource Reservation Protocol）シグナリングプロトコルが開発されている。このＲＳＶＰプロトコルは、例えば伝送パスの決定を可能にするＭＰＬＳ（Multiprotocol Label Switching）プロトコルと一緒に使用される。このＭＰＬＳプロトコルでは、パケットがネットワークに入ると、エッジルータＬＳＲ（Label Switching Router）により、このパケットにラベルが割り当てられ、このラベルにより、このパケットに対し、このネットワークを通るパスＬＳＰ（Label Switched Path）が決定される。この場合、内部ルータＬＳＲ（Label Switched Router）によるこのパケットの転送は、このラベルによって決定されたパスＬＳＰに相応して行われるのである。
【０００９】
パス選択は、ＡＴＭ（Asychroneous Transfer Mode）技術の枠内でも行われ、ＩＰネットワークに対してＩＰデータグラムのSource Route Optionを用いて行うことができる。しかしながら実践的にはこのSource Route Optionがサポートされることはまれである。
【００１０】
パスのリザーブは、ＱｏＳ伝送について保証することができるが、極めて複雑であり、（「最善の努力（best effort）」のパケット網に比べて）フレキシビリティが損なわれてしまう。
【００１１】
本発明の課題は、従来の方法の欠点を回避しながら、パケット網を介してＱｏＳ伝送という意味での効率的なルーティングを行うことである。
【００１２】
この課題は、請求項１に記載の方法、請求項１６に記載のエッジルータ、および請求項１７に記載の内部ルータによって解決される。
【００１３】
本発明の枠内では、トラフィック分散を有するパケット網においてデータパケットをルーティングする方法が提案される。本発明の方法では、データパケットをデータネットワークの内部ルータによって転送ないしはルーティングし、ここでこのパケットの転送ないしはルーティングを、少なくとも２つの情報に基づいて行う。これらの２つの情報のうちの１つは、データパケットがこのパケット網に到達するインタフェースないしはノードであり、また２つ目の情報は、データパケットがこのパケット網を離れるべきインタフェースないしはノードである。ＡＴＭ技術またはＭＰＬＳ技術のような従来技術とは異なり、このパケット網を通る完全なパスは決定されない。固定されるのは、データパケットがデータネットワークにアクセスする点と、データパケットがこのデータネットワークを再び離れる点ないしはインタフェースとだけである。このパケット網内部では、トラフィック分散によって処理される。すなわち、ルータは、データパケットの転送に対して択一的な選択肢をあらかじめ与えられ、これらのルータは、例えば、リンク故障の際、またはこのルーティングに対する択一的なパスを介する統計的な分散の枠内でこれらの択一的な選択肢を使用可能である。データパケットの入口ないしは出口点（すなわち、データパケットがこのネットワークに入るないしはこのネットワークを再び離れるインタフェース）を決定するため、識別情報、例えば、エッジノードにおける識別子（Kennung）ないしはエッジノードのポートを付与することができる。この場合、このような識別子は、データパケットがこのパケット網に到達する、ないしはこのパケット網を離れるノードないしはノードのポートを表す。
【００１４】
ここで内部ルータないしは内部ノードは、このパケット網を通るデータパケットの転送に関連しており、また内部ルータないしは内部ノードには入口または出口ノードと等しくないすべてのルータないしはノードが含まれる。別のネットワークに対してインタフェース機能を有し、かつトポロジー的にネットワークのエッジに位置するルータの集合は、エッジルータと称される。この場合にこれと補集合をなすルータは、コアルータと称される。この用語の使い方の枠内では内部ルータとコアルータとは同一でない。例えばデータパケットのパスが、このパケット網を通るルーティングの際に複数のコアルータを介して導かれる場合、データパケットがネットワークに入るないしはこのネットワークを出る２つのコアルータだけが、ここの説明の意味での内部ルータでもあるのである。
【００１５】
パケットネットワークは、部分ネットワークまたはサブネットワークとすることができる。ＩＰ（Internet Protocol）システムには、全体ネットワークが自律システムないしは「autonomous system」と称されるネットワークに分割されるネットワークアーキテクチャもある。本発明のネットワークは、例えば、自律システムまたはサービスプロバイダ（例えば、ＩＳＰ：internet service provider）の管轄領域における全体ネットワークの一部とすることができる。部分ネットワークの場合には、部分ネットワークにおけるトラフィックコントロールを介して、また部分ネットワーク間の効率的な通信を介して、転送に対するサービスパラメタを全体ネットワークにわたって決定することができる。
【００１６】
このパケット網では、トラフィック分散が行われる。この際にデータネットワークのルータは、トラフィックを択一的なつぎのステーションないしはホップに分散することができる。この分散は例えば、パケット毎またはフロー毎に行うことができる。択一的なルートないしはパスを介するルーティングは、接続区間が故障した場合またはデータトラフィックを均一に分散させることを目的として行うことができる。本発明により、入口および出口点についての情報に基づいてデータパケットの転送についてのローカルな判定を行うことができる。データパケットがパケット網に入る際には、通例、このデータパケットのパスは固定的に決定されない。
【００１７】
本発明は、伝送パスが完全に決定される方法と比較して格段にフレキシブルであるという利点を有する。ネットワークのエッジにおけるアクセスコントロールによって保証することができるのは、到来するトラフィックが、このネットワーク内で、ＱｏＳレベルを有する伝送を可能にする境界内にとどまることである。ネットワーク内でのトラフィック分散により、個々のリンクにおいて狭いパスが発生しないようにすることができる。パケットのループなどの従来のパケット網の問題は回避される。
【００１８】
発信情報をルータの転送判定に組み入れることによって、古典的なＩＰルーティングないしはＥＣＭＰ（equal cost multipath）の場合よりも、極めて多様なパスが可能になる。これに結び付いたルーティングテーブルの複雑さの増大は、ルーティングテーブルを入口点および出口点に関連した情報（例えば入口および出口ノード番号）に削減することによって、１ネットワークにおいて小さく維持することができ、結果的に得られるルーティングテーブルは、通例、古典的なＩＰルーティングの場合よりも小さくなる。ＭＰＬＳとは異なり、パスを明示的に構成する必要はなく、すべてのネットワークノードは、マルチパスを自律的に利用し尽くすことができ、これによってトラフィック分散またはエラーに対する迅速なローカルの応動を達成することできる。
【００１９】
入口および出口点についての情報を内部ルータに供給するため、以下に３つの例を説明する。
【００２０】
例えば、データパケットの入口点に１つまたは複数の情報フィールドないしはラベルを付与することができ、ここでこれはデータパケットの入口および出口点についての情報を含む。この情報フィールドないしはこれらの情報フィールドは、ヘッダないしはトレーラとしてデータパケットに前置するか、またはデータパケットに継ぎ足すことができる。この場合、１情報フィールドが入口点についておよび出口点について情報を含むことも、専用の情報フィールドがそれぞれ入口点ないしは出口点についての情報をそれぞれ含むことも共に可能である。これらの情報フィールドないしはラベルにはビット列を前置して、情報フィールドを情報フィールドとしてしるしを付けることができる。１つのオプションは、ＭＰＬＳラベルによって処理し、入口ノードおよび出口ノードのペア毎にＭＰＬＳラベルを付与することである。この場合、ラベル毎に相異なる択一的なパスをデータネットワーク内で決定する。このネットワーク内でルーティングする際、内部ルータはラベルを識別し、ラベルに所属するどのパスにこの内部ルータがデータパケットを転送するかについてローカルに判定を行うことができる。有利にはエンドツーエンドフローのデータパケット、すなわち発信および宛先アドレス情報（例えばＩＰアドレスおよび場合によってはＴＣＰポート番号）が同じ複数のデータパケットを同じパスに沿ってルーティングし、これによってデータパケットの順序を維持する。
【００２１】
データネットワークの入口ノードないしは入口ルータにおいてデータパケットに追加される情報フィールドは、出口点ないしは出口ルータで元のように除去することができる。内部ルータでは、例えば、ルーティングテーブルを維持することができ、ここでこれらのルーティングテーブルにより、データパケットのアクセスインタフェースについての情報および出口インタフェースについての情報が、データパケットの転送に対するアドレスと関係付けられる。この場合、このようなテーブルにはアクセスインタフェースおよび出口インタフェースのペアに対して、データパケットの次ホップに対するアドレスが含まれる。さらに、内部ルータから延びているリンクにおける遅延または障害の場合のバックアップないしはトラフィック分散という意味で、別の択一的なアドレスを上記のテーブルに配置することができる。古典的に編成されるテーブルの代わりに、例えば、木構造に相応して設けられる最新のサーチ構造およびアルゴリズムによるサーチを実行することも可能である。
【００２２】
データパケットに対するアクセスインタフェースないしは出口インタフェースについての情報を入口ノードから内部ルータに伝達する別のオプションは、データパケットの不要で既存のフィールドを使用することである。例えば、ＩＰデータグラムのSource-Route-Optionを使用して、データパケットの入口および出口インタフェースに対するアドレス情報を記憶することが考えられる。この場合、これらの情報は、ネットワークに入る際にデータグラムに書き込まれ、ルーティング判定中に内部ノードによってデータグラムから抽出される。アクセスインタフェースないしは出口インタフェースについての情報は、このネットワークを離れる際にデータパケットのフィールドから元のように除去して、これらのフィールドを再び元々の目的に利用できるようにする。
【００２３】
３つの可能性は、内部ノードにより、データパケットから抽出したアドレス情報に基づいて、データパケットに対するアクセス点および指示された出口点を識別することである。
【００２４】
パケット網に対するデータパケットのアクセスインタフェースについての情報を決定するため、およびデータパケットがデータ網を離れるべき出口インタフェースについての情報を決定するために、入口点と出口点とで異なる手法を使用することも可能である。
【００２５】
例えば、パケットがこのネットワークに入る際、このパケットは、入口ノードの識別子を有する情報フィールドを有することが可能である。この場合、内部ルータはこの識別子を抽出して、例えばテーブルを用いて出口ノードを決定する。入口インタフェースないしは出口インタフェースに関連する２つの情報を決定するために異なる手法を別に組み合わせることも同様に可能である。
【００２６】
本発明を以下、図面に基づき、実施例の枠内で詳しく説明する。ここで、
図１は、パケット網の簡略化した図を示しており、
図２は，図１の例示的なネットワークに対する従来のルーティングテーブルを示しており、
図３は、本発明にしたがってラベルを使用した場合の概略図を示しており、
図４は、本発明によるルーティングテーブルを示している。
【００２７】
図１にはパケット網Ｎ１の簡略化された図が示されている。パケット網Ｎ１にはネットワークＮ２〜Ｎ４が接続されている。ネットワークＮ１〜Ｎ４により、加入者局ないしは端末装置Ｔ１〜Ｔ９は互いに通信することができる。ここでは３つずつの端末装置がネットワークＮ２，Ｎ３およびＮ４にそれぞれ接続されている（Ｔ１〜Ｔ３，Ｔ４〜Ｔ６，Ｔ７〜Ｔ９）。パケット網Ｎ１にはノードＫ１，Ｋ２およびＫ３が含まれており、これらは接続線路ないしはリンクＬ１２，Ｌ１３およびＬ２３を介して互いに接続されている。図２の最も上のテーブルには発信ネットワークおよび宛先ネットワークからなるさまざまなペアに対して２つずつのバスが示されている。第１に示されているパスは、ルーティングに対する優先的なパスであり、このルーティングは中間局ないしはホップの（最小）数によって決まる。第２のパスは、１つずつの択一的なパスであり、これは例えば、障害時またはパスが狭い場合に応急手段として利用することができる。ここでは例示的にネットワークＮ２からネットワークＮ３へのデータ伝送を考察する。「最小コスト（least cost）」パスはノードＫ１およびＫ２を介して通じている。択一的なパスはリンクＬ１２を回避し、これはこのパスが転送チェーンＫ１−Ｋ３−Ｋ２が有することによって行われる。この択一的なパスは、例えばリンクＬ１２が故障時に利用される。
【００２８】
図２の第２〜４のテーブルは、ノードＫ１，Ｋ２およびＫ３における従来のルーティングテーブルを示している。宛先に対してそれぞれつぎの局ないしは次ホップが示されており、また最も上のテーブルに指定されたパスに相応して択一的な選択肢が示されている。ノードＫ１におけるルーティングテーブルに相応して、ネットワークＮ１宛てのデータパケットは、接続されたネットワークＮ１に直接（ローカルに）伝送することができる。このような状況はこのテーブルにおいて、「ローカル」という語を有するフィールドによって示されている。ネットワークＮ３宛てのデータパケットは有利にはノードＫ２にルーティングされる。択一的な宛先としてノードＫ３がテーブルに示されている。これに類似してネットワークＮ４宛てのデータパケットは有利にはノードＫ３にルーティングされ、択一的にはノードＫ２にルーティングされる。これに相応してノードＫ２およびＫ３に対するルーティングテーブルを理解することができる。
【００２９】
ルーティングテーブルのこの組合せによって、例えば、ネットワークＮ２からネットワークＮ３に宛てられ、ノードＫ１においてネットワークＮ１に入るデータパケットは、まず、ノードＫ３に転送され、つぎにここから再びノードＫ１に戻されることも可能である。例えば、有利なパスおよび択一的なパスを介してパケット網Ｎ１内でより良好に能力を活用することを目的として負荷分散（ロードバランシング）を行う場合にこのような事態が発生し得る。例えばデータパケットが基本的に８０％の確率で有利なパスに沿ってルーティングされ、２０％の確率で択一的なパスを介してルーティングされる場合、このような事態は０．２＊０．２＊１００ ＝ ４％の確率で発生する。すなわちループが発生するのである。ループは殊につぎのような場合には回避しなければならない。すなわちパケット網Ｎ１の境界においてＱｏＳ保証の点からトラフィック制限およびトラフィックコントロールが行われる場合には回避しなければならないのである。
【００３０】
この問題は、マルチパスを制限しない場合には、パケットの宛先アドレスだけを考慮する古典的なＩＰルーティングによっては解決できない。この実施例では、ループのない転送を保証するため、少なくとも２つのノードにおいて択一的なパスを除去しなければならない。これは同時に、コストパラメタを手動で調整するＥＣＭＰ（Equal Cost Mutipath）のようなメカニズムによっておよびＥＩＧＲＰ（Enhanced Interior Gateway Routing Protocol）およびunequal cost multipath routingによって達成することができる最大のマルチパスである。
【００３１】
宛先ベースの転送（desitination based routing）を回避するためのオプションは、例えばＭＰＬＳコンセプトの枠内で、伝送パスをあらかじめ設定することである。この場合、パスを参照するいくつかのビット（「ラベル」）を各ＩＰパケットに前置する。しかしながらＭＰＬＳの欠点は、途中でパスの別のノードが、ネットワーク入口におけるルータ（「入口ルータ」（ingress router））の元々のパス選択をもはや変更できないことである。
【００３２】
図３にはパケット網Ｎ１内でルーティングするための情報フィールドないしはラベルの本発明による処理の仕方が示されている。ここではパケット網Ｎ１ならびにネットワークＮ２およびＮ３が示されている。ネットワークＮ２からネットワークＮ３に伝送すべきデータパケットは、ノードＫ１において、すなわちネットワーク入口において変更される。このデータパケットにはヘッダとしてラベルＥＬ（ＥＬ：Egress Label  出口ラベルを表す）と、ＩＬ（ＩＬ：Ingress Label  入口ラベルを表す）とが前置される。ラベルＩＬには入口ルータ（ingress router）の識別子が含まれ、またラベルＥＬには上記のデータパケットがこのネットワークを再び離れるべきである出口ルータ（egress router）の識別子が含まれる。オプションでは付加的なビット列ＬＣ*（ＬＣ：label codeラベルコードを表す）により、ラベルＩＬおよびＥＬをラベルとして特徴付けることも可能である。図３ではこのようなラベルＥＬ，ＩＬおよびＬＣを有するＩＰパケットが示されており、これらはこのデータパケットがネットワークＮ１に入る際にノードＫ１において付け加えられ、ネットワークＮ１から出る際にノードＫ２において元のように除去される。
【００３３】
ラベルＥＬおよびＩＬは、ＩＬの場合にはノードＫ１の番号を含み、またＥＬに対してはノードＫ２の番号を含む。これらのノード番号は、これらのネットワークノードを実装する際にあらかじめ設定して、考察するパケット網ないしは自律システム（英語の文献ではAutonomous Systemという表現がしばしば見受けられる）内でこれらのノード番号がそれぞれ一意であるようにする。ラベルＩＬとして、このネットワークの各入口ノードは、その固有のノード番号を使用することができる。出口ノードのノード番号ないしはラベルＥＬの決定は、古典的なパケット網ルーティング情報、例えばパケットにエントリされている宛先ＩＰアドレスに基づいて行うことができる。つぎに決定した出口ノードのノード番号がラベルＥＬとして使用される。
【００３４】
このネットワーク内ではデータパケットのヘッダにおける発信アドレスおよび宛先アドレスをもはや考慮しない。つぎのノードの決定は、パケットに前置された情報ヘッダＩＬおよびＥＬ（または組み合わされたただ１つのラベル）だけに基づいて行われる。これにより、ルーティングテーブルは格段に小さくなる。さらに情報フィールドＩＬおよびＥＬを擬似的なＭＰＬＳラベルに組み合わせることにより、パケットの伝送形式をＭＰＬＳ互換に維持することができる。
【００３５】
図４は、本発明のルーティングテーブルを図１の実施例に対して示している。ノードＫ１，Ｋ２およびＫ３にはノード番号ないしはノード識別子ＫＮ１，ＫＮ２およびＫＮ３がそれぞれ割り当てられている。入口ノード、例えばノードＫ１は、それ自体のノード番号、すなわちノードＫ１用のＫＮ１を、ラベルＩＬに対して使用する。ラベルＥＬに対するノード識別子は、テーブルに基づいて決定される。この場合に外部のネットワークに接続されているＮ１における各ネットワークノードは、出口ノードを決定するためのテーブルを有する。このようなテーブルの例は、図４の最も上のテーブルによって示されている。データパケットをネットワークＮ２からネットワークＮ３に伝送する場合、入口ノードＫ１は、図４の上記のテーブルから出口ノードＫ２に対するノード番号ＫＮ２を抽出する。この場合、このノード番号ＫＮ２がラベルＥＬとして使用される。このテーブルでは、ネットワークＮ２，Ｎ３およびＮ４はそれらのネットワークノードと、これを介して到達可能な別のすべてのネットワークを代理する。ＥＬを決定するためのテーブルは、ほぼＢＧＰルーティングテーブル（ＢＧＰ：Border Gateway Protocol）のサイズを有する。これに相応して、ラベルＥＬを決定するためのサーチコストも同様に、ＢＧＰプロトコルを用いて次ホップを決定する場合と同様に手頃である。
【００３６】
図４の残りのテーブルは、図２のルーティングテーブルと類似の、本発明の方法によるテーブルである。これらのルーティングテーブルはここでは入口−出口ノードペア毎に１エントリを有する。パケットが複数のノードのうちの１ノードにおいてネットワークＮ１を離れる場合、ラベルは元のように除去され、つぎのノードが外部のルーティングプロトコル（刊行物では外部ゲートウェイプロトコル（external gateway protocol）、略してＥＰＧがふつうである）を介して決定される。ＢＧＰ（border gateway protocol）プロトコルは、この目的のためにしばしば使用される。例えば、データパケットをネットワークＮ２からネットワークＮ３に伝送する。入口ノードＫ１は出口ノードＫ２を決定し、入口および出口ノードの識別子ＫＮ１およびＫＮ２をデータパケットにラベルとして前置する。図４のノードＫ１に対するルーティングテーブルに相応して、出口入口ラベルペアＫＮ２およびＫＮ１に対して有利な次ノードはＫ２である。択一的にはこのデータパケットはノードＫ３にルーティングされる。最初のケースでは（図４の第の３テーブルにしたがい）ノードＫ２よってつぎのホップがＥＧＰプロトコルを用いて決定される（ここで星印は、なんらかのノード識別子に対するプレースホルダである）。つぎのケース（図４の最も下のテーブル）ではノードＫ３により、ノードＫ２がつぎのホップとして決定される。ここには択一的なホップないしは択一的なアドレスはない。これにより、上記のループが回避される。
【００３７】
ノード番号の付与は、ネットワークノードを実装する際に手動で行われる。しかしながら有利であるのは、自動化されたメカニズムである。このためにルータ間にプロトコルを流すことができ、このプロトコルによってこれらのルータがノード番号について自力で合意し（例えば、考察するネットワークにおいてそのＩＰアドレスをソートすることによる）、引き続いて出口ラベルＥＬを決定するテーブルが相互に分配される。動作中のネットワークに新たなノードを入れる場合、これらノードは都度まだ占有されていないつぎのノード番号を得ることができる。以前に切り離したネットワークを動作中に統合するためには一般に別のメカニズムが必要である。
【００３８】
自動的な自己コンフィギュレーションとは択一的に、例えばネットワーク管理の枠内において中央の局により、コンフィギュレーションすることも可能である。このためにネットワークをまず通常のＩＰルーティング動作でスタートさせる。引き続きネットワーク管理を介してノード番号を付与し、その後はじめてラベルを付けるため、およびトラフィックを複数のパスに分配するためのプロセスをスタートさせる。
【００３９】
ローカルにおいてパケットをさまざまなパスに自由に分配することによって、セマンティックに関連するパケット（例えば同じＴＣＰコネクションの複数のパケット）の順序が障害を受けないようにするため、ネットワーク入口のノードによって付加的に別のフィールドＦＩ（フロー識別子flow identifier）をラベルに付け加えることができ、これは例えばパケットの発信および宛先アドレス（例えばＩＰアドレスおよび場合によってポート番号）から算出される値を含む。この場合、このネットワークにおける別のノードは、フィールドＦＩの値毎に、関連するパス決定をダイナミックなテーブルに記憶するか、またはこれら系統的なやり方で（例えばＦＩの値の範囲を分割することによって）ＦＩ値に所定のルートを割り当てる。ＦＩとパス決定との間の割り当ては、エラーの場合、各ノードにおいてローカルにダイナミックに変更することができる。
【００４０】
ルーティングテーブルは、種々のアルゴリズムを用いて中央で算出してすべてのノードに分配することができるか、または各ノードにおいて自律的に、例えばＯＳＰＦ（Open Shortest Path First）プロトコルで交換されるLink-State-Informationを用いて算出することができる。
【００４１】
ここで説明した方法は、ラベルにおいて入口／出口番号を伝達することなしに使用することも可能である。このためには、各ネットワークノードに別の２つのテーブルを設け、これらのテーブルによってネットワークノードがパケット毎に、相応する情報をそれ自体で計算することができるようにする。ここでＥＬテーブルは上で図４に基づいて説明したＥＬに相応する。ＥＧＰにおいて対称的なルーティングが保証される場合、相応するＩＬテーブルは、外部（ＥＧＰ）ルーティングテーブルから同様に作成することができる。ここで対称的なルーティングとは、データパケットのパスが、伝送方向について不変である、すなわち、データパケットヘッダにおける発信と宛先アドレスとの交換に無関係であることである。ＩＬテーブルを作成する際には発信アドレスは、アクセスインタフェースないしはアクセスノードに関係付けられる。データパケットに対してアクセスインタフェースが求められ、ここでこれはＥＧＰにより、データパケットの発信アドレスを宛先アドレスとして有するデータパケットに対する出口インタフェースないしは出口ノードが決定されることによって行われる。ルーティングの対称性に起因して、決定した上記のインタフェースないしは決定したノードは、このデータパケットのアクセスインタフェースないしはアクセスノードである。
【００４２】
セキュリティ上の理由から、ネットワークに入る際にＩＰパケットの発信アドレスと物理的な入口点とを一致させることができるかというチェックがいずれにせよ所望されることが多いため、対称的なルーティングに対する要求が将来的に標準的に満たされる可能性もある。
【００４３】
上記のコンセプトは、入口ラベルＩＬだけで実現することも可能である。この場合、ローカルのルーティングテーブルは、出口ラベルＥＬの代わりに通常のネットワークアドレスを含むことになり、相応に大きくなり得るが、ネットワーク入口ノードについて出口ラベルを調べることが省略され得る。
【図面の簡単な説明】
【００４４】
【図１】簡略化したパケット網の図である。
【図２】図１の例示的なネットワークに対する従来のルーティングテーブルを示す図である。
【図３】本発明にしたがってラベルを使用した場合の概略図である。
【図４】本発明によるルーティングテーブルを示す図である。
【図１】
2005536163.tif 000003
【図２】
2005536163.tif 000004
【図３】
2005536163.tif 000005
【図４】
2005536163.tif 000006
【手続補正書】
【提出日】平成16年10月5日(2004.10.5)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ルータによって形成される、トラフィック分散を有するパケット網（Ｎ１）にて、データパケットのループを回避するためにデータパケットをルーティングする方法において、
データパケット（ＩＰパケット）をパケット網（Ｎ１）の内部ルータによって転送し、  データパケットを転送するために択一的な選択肢が設けられており、
当該のデータパケット（ＩＰパケット）の転送を少なくとも、データパケット（ＩＰパケット）のパケット網（Ｎ１）へのアクセスインタフェースについての情報（Ｋ１）と、データパケット（ＩＰパケット）がパケット網（Ｎ１）を離れるべき出口インタフェースについての情報（Ｋ２）とに基づいて行うことを特徴とする、
データパケットをルーティングする方法。
【請求項２】
前記のアクセスインタフェースにてデータパケット（ＩＰパケット）に識別情報を付与し、
該識別情報に基づき、内部ルータにより、前記のアクセスインタフェースおよび出口インタフェースを識別する、
請求項１に記載の方法。
【請求項３】
前記識別情報には、前記のアクセスインタフェースおよび出口インタフェースに対するネットワークアドレスまたは識別子（Ｋ１，Ｋ２）が含まれる、
請求項２に記載の方法。
【請求項４】
前記のアクセスインタフェースにてデータパケット（ＩＰパケット）に少なくとも１つの情報フィールド（ＩＬ，ＥＬ）を付与し、
前記の内部ルータにより、１つまたは複数の情報フィールド（ＩＬ，ＥＬ）から、パケット（ＩＰパケット）のパケット網（Ｎ１）へのアクセスインタフェースについての情報（Ｋ１）と、出口インタフェースについての情報（Ｋ２）とを取り出す、
請求項３に記載の方法。
【請求項５】
前記データパケット（ＩＰパケット）に情報フィールドを付与し、
該情報フィールドは、ヘッダまたはトレーラとしてデータパケットに付け加えられ、
前記情報フィールドは、アクセスインタフェースおよび出口インタフェースの識別子（Ｋ１，Ｋ２）を含む、
請求項４に記載の方法。
【請求項６】
前記のデータパケット（ＩＰパケット）に２つの情報フィールド（ＩＬ，ＥＬ）を付与し、
該情報フィールド（ＩＬ，ＥＬ）をそれぞれヘッダまたはトレーラとしてデータパケット（ＩＰパケット）に付け加え、
一方の情報フィールド（ＩＬ）はアクセスインタフェースの識別子（Ｋ１）を、他方の情報フィールド（ＥＬ）は出口インタフェースの識別子（Ｋ２）を含む、
請求項４に記載の方法。
【請求項７】
少なくとも１つの情報フィールド（ＩＬ，ＥＬ）にビット列（ＬＣ*）を付け加えるかまたは前置し、
該ビット列により、情報フィールド（ＩＬ，ＥＬ）を情報フィールドとして識別する、
請求項５または６に記載の方法。
【請求項８】
前記の入口インタフェースにてデータパケット（ＩＰパケット）に少なくとも１つの情報フィールド（ＩＬ，ＥＬ）を付与し、
該情報フィールド（ＩＬ，ＥＬ）を出口インタフェースにて元のように除去する、
請求項５から７までのいずれか１項に記載の方法。
【請求項９】
少なくとも１つの情報フィールド（ＩＬ，ＥＬ）をＭＰＬＳラベルによって得る、
請求項４から８までのいずれか１項に記載の方法。
【請求項１０】
前記識別情報を、データパケット形式の枠内で設けられたフィールドに書き込む、
請求項３に記載の方法。
【請求項１１】
前記の出口インタフェースを識別子（Ｋ２）によって参照し、
パケット網（Ｎ１）を横断した後にデータパケット（ＩＰパケット）を転送すべきネットワーク（Ｎ３）のネットワークアドレスに基づいて出口インタフェースの識別子（Ｋ２）を識別し、
ネットワークアドレスに基づき、入口インタフェースにおけるテーブルを用いて、出口インタフェースの識別子（Ｋ２）の識別する、
請求項１から１０までのいずれか１項に記載の方法。
【請求項１２】
前記のアクセスインタフェースにてデータパケット（ＩＰパケット）に識別情報を付与し、
該識別情報に基づき、内部ルータによってアクセスインタフェースを識別し、
該識別情報は、アクセスインタフェースのネットワークアドレスまたは識別子（Ｋ１）を含んでおり、
内部ルータは、データパケットから抽出されるアドレス情報に基づいて出口インタフェースについての情報（Ｋ２）を求める、
請求項１に記載の方法。
【請求項１３】
前記内部ルータにより、データパケット（ＩＰパケット）から抽出したアドレス情報に基づいて、アクセスインタフェースについての情報（Ｋ１）および出口インタフェースについての情報（Ｋ２）を求める、
請求項１に記載の方法。
【請求項１４】
前記のデータパケット（ＩＰパケット）の転送をルーティングテーブルによって行い、該ルーティングテーブルにより、データパケット（ＩＰパケット）のパケット網（Ｎ１）へのアクセスインタフェースについての情報と、また出口インタフェースについての情報（Ｋ２）とを次ホップに対するネットワークアドレスに割り当てる、
請求項１から１３までのいずれか１項に記載の方法。
【請求項１５】
前記のアクセスインタフェースにて、フロー識別する情報フィールドをデータパケット（ＩＰパケット）に付与し、
データパケット（ＩＰパケット）の転送を、内部ルータにより、前記情報フィールドにしたがって行う、
請求項１から１４までのいずれか１項に記載の方法。
【請求項１６】
パケット網（Ｎ１）における内部ルータにおいて、
データパケット（ＩＰパケット）のパケット網（Ｎ１）へのアクセスインタフェースについての情報（Ｋ１）と、出口インタフェースについての情報（Ｋ２）とが次ホップに対するネットワークアドレスに割り当てられることを特徴とする、
請求項１から１５までのいずれか１項に記載の方法を実施するための内部ルータ。
【国際調査報告】
2005536163.tif 000007
2005536163.tif 000008
2005536163.tif 000009
2005536163.tif 000010
2005536163.tif 000011
2005536163.tif 000012