(57)【要約】【課題】  パケットのルーティング方法及びシステムを提供する。【解決手段】  出所エッジデバイスは、外部通信ネットワークから受信したデータパケットの行先アドレスプレフィックスに対応するネクストホップのアドレスを決定し、該ネクストホップに対応するターゲットエッジデバイスのアドレス及びネットワークインタフェースを決定し、該ターゲットエッジデバイスへ宛てた伝送パケットを生成する。伝送パケットは、受信したデータパケット、決定したネクストホップのアドレス、及び決定したターゲットエッジデバイスのネットワークインタフェースを含む。生成された伝送パケットは、出所エッジデバイスから、内外部通信ネットワークを介してデバイスリンク層レベルでターゲットエッジデバイスへ送られる。データパケットは、そのネクストホップアドレスに基づいてターゲットエッジデバイスのネットワークインタフェースへ転送される。【選択図】      図１
2005244983.tif 000002
【特許請求の範囲】
【請求項１】
パケットを、１またはそれ以上の内部通信ネットワークを介して分散された、そしてダイナミックな手法でルーティングする方法であって、上記各内部通信ネットワークは１またはそれ以上のエッジデバイスを含み、上記各エッジデバイスは上記内部ネットワークを１またはそれ以上の外部通信ネットワークに接続し、上記内部及び外部通信ネットワークはパケット交換方式であり、上記方法は、
出所エッジデバイスにおいて、外部通信ネットワークからデータパケットを受信するステップと、
上記出所エッジデバイスにおいて、上記受信されたデータパケットの行先アドレスプレフィックスに対応するネクストホップのアドレスを決定するステップと、
を含み、
上記方法が更に、
上記出所エッジデバイスにおいて決定された上記ネクストホップに対応するターゲットエッジデバイスのアドレス及びネットワークインタフェースを決定するステップと、
上記出所エッジデバイスにおいて決定された上記ターゲットエッジデバイスにアドレス指定された、且つ上記受信されたデータパケット、上記決定されたネクストホップアドレス、及び上記決定されたターゲットエッジデバイスのネットワークインタフェースを含む伝送パケットを生成するステップと、
上記生成された伝送パケットを、上記出所エッジデバイスから、１またはそれ以上の内部通信ネットワークを介してデータリンク層レベルで、上記決定されたターゲットエッジデバイスへ伝送するステップと、
上記ターゲットエッジデバイスにおいて、上記受信された伝送パケットから、上記データパケット、上記ネクストホップアドレス、及び上記ターゲットエッジデバイスのネットワークインタフェースを分離するステップと、
上記データパケットを、上記ネクストホップアドレスに基づいて、上記ターゲットエッジデバイスのネットワークインタフェースを介して転送するステップと、
を含むことを特徴とする方法。
【請求項２】
上記データパケットを上記ターゲットエッジデバイスのネットワークインタフェースから転送するステップは、
上記ネクストホップアドレスが、個別アドレスであるのか、またはネットワークアドレスであるのかを決定するステップ、
を含み、
上記ネクストホップアドレスが個別アドレスである場合には、上記データパケットを上記ネクストホップアドレスへ送り、
上記ネクストホップアドレスがネットワークアドレスである場合には、上記データパケットをその中に含まれる行先アドレスへ送る、
ことを特徴とする請求項１に記載の方法。
【請求項３】
ネットワークルーティング情報及びネットワークスイッチング情報が１またはそれ以上の上記エッジデバイス内に維持されており、上記ルーティング情報は行先アドレスプレフィックス及び対応するネクストホップアドレスを含み、上記ネットワークスイッチング情報は上記ネクストホップのアドレス及び上記対応するターゲットエッジデバイスのアドレス及びネットワークインタフェースを含むことを特徴とする請求項１または２に記載の方法。
【請求項４】
上記エッジデバイスが、外部通信ネットワークから新しい、または変化したネットワークルーティング情報を受信した時に、当該エッジデバイスに維持されているネットワークルーティング情報及び／または上記スイッチング情報が更新され、上記受信されたネットワークルーティング情報及び関連ネットワークスイッチング情報から更新パケットが形成され、そして上記更新パケットが１またはそれ以上の他のエッジデバイスへ送られることを特徴とする請求項３に記載の方法。
【請求項５】
上記エッジデバイスが上記更新パケットを受信した時に、もし必要ならば、上記受信された更新パケットに基づいて、当該エッジデバイスに維持されているネットワークルーティング情報及び／または上記スイッチング情報が更新されることを特徴とする請求項４に記載の方法。
【請求項６】
上記受信された更新パケット内に含まれる上記ネットワークルーティング情報は、当該エッジデバイスが接続されている１またはそれ以上の上記外部ネットワークへ転送されることを特徴とする請求項５に記載の方法。
【請求項７】
第１の内部通信ネットワークと第２の内部通信ネットワークとの間で上記伝送パケット及び更新パケットを伝送するために当該両内部通信ネットワークはゲートウェイによって接続され、上記ゲートウェイは、上記両内部通信ネットワークのためのルーティング及びスイッチング情報を別々に維持していることを特徴とする請求項１−６の何れか１つに記載の方法。
【請求項８】
上記ゲートウェイが、第１の内部通信ネットワークから更新パケットを受信した時に、
もし必要ならば、上記ゲートウェイが維持している上記第１の内部通信ネットワークのルーティング及び／またはスイッチング情報を更新し、
上記スイッチング情報内に含まれる上記ターゲットエッジデバイスのネットワークインタフェースを、上記ゲートウェイのネットワークインタフェースに置換することによって上記受信された更新パケットを変更し、
上記変更された更新パケットを、上記第２の内部通信ネットワークの１またはそれ以上のエッジデバイスへ伝送し、そして
もし必要ならば、上記変更された更新パケットを受信した上記エッジデバイスが維持している上記ルーティング及び／またはスイッチング情報を更新する、
ことを特徴とする請求項７に記載の方法。
【請求項９】
伝送パケットを、上記変更された更新パケットを受信した上記第２の内部通信ネットワークのエッジデバイスから、上記第１の内部通信ネットワークのターゲットエッジデバイスへ送り、上記伝送パケットのターゲットエッジデバイスのネットワークインタフェースを上記ゲートウェイのネットワークインタフェースに置換するステップと、
上記ゲートウェイが維持しているスイッチング情報によって、上記受信された伝送パケットのターゲットエッジデバイスのネットワークインタフェースを決定するステップと、
上記伝送パケット内に含まれる上記ゲートウェイのネットワークインタフェースを、上記決定されたターゲットエッジデバイスのネットワークインタフェースに置換するステップと、
上記伝送パケットを、上記ゲートウェイから当該ターゲットエッジデバイスへ転送するステップと、
を含むことを特徴とする請求項８に記載の方法。
【請求項１０】
出所エッジデバイスが、外部通信ネットワークからマルチキャスト型のデータパケットを受信した時に、上記データパケットが上記ターゲットエッジデバイスのマルチキャストネットワークインタフェースへ伝送されることを特徴とする請求項１−９の何れか１つに記載の方法。
【請求項１１】
１またはそれ以上のエッジデバイス及び／またはゲートウェイには、サービスクラス特定待ち行列が設けてあることを特徴とする請求項１−１０の何れか１つに記載の方法。
【請求項１２】
上記１またはそれ以上の内部及び／または外部通信ネットワークは、ＩＰネットワークであることを特徴とする請求項１−１１に記載の方法。
【請求項１３】
パケットを、分散された、そしてダイナミックな手法でルーティングするシステムであって、上記システムは、
パケット交換方式である１またはそれ以上の内部通信ネットワーク（ＳＶ１、…、ＳＶＮ）と、
パケット交換方式である１またはそれ以上の外部通信ネットワーク（ＵＶ１、…、ＵＶＮ）と、
上記外部通信ネットワークからデータパケットを受信するための１またはそれ以上のエッジデバイス（ＲＬ１、…、ＲＬＮ）と、
を含み、上記各エッジデバイスは、上記内部通信ネットワークと共に、上記内部通信ネットワークを上記外部通信ネットワークの１またはそれ以上のエッジデバイスに接続するように構成されており、上記１またはそれ以上のエッジデバイスは、
上記受信されたデータパケットの行先アドレスプレフィックスに対応するネクストホップアドレスを決定するルーティングテーブル（ＲＴ１、…、ＲＴＮ）を含み、
上記１またはそれ以上のエッジデバイス（ＲＬ１、…、ＲＬＮ）が更に、
上記受信されたデータパケットの決定されたネクストホップに対応するターゲットエッジデバイスのアドレス及びネットワークインタフェースを決定するスイッチングテーブル（ＫＴ１、…、ＫＴＮ）と、
上記決定されたターゲットエッジデバイスにアドレス指定され、且つ上記受信されたデータパケット、上記決定されたネクストホップのアドレス、及び上記決定されたターゲットエッジデバイスのネットワークインタフェースを含む伝送パケットを生成する伝送パケット生成手段（１）と、
上記受信された伝送パケットから、上記データパケット、上記ネクストホップアドレス、及び上記ターゲットエッジデバイスのネットワークインタフェースを分離する伝送パケット分離手段（２）と、
上記データパケットを、上記ネクストホップアドレスに基づいて、上記ターゲットエッジデバイスのネットワークインタフェースを介して転送するデータパケット転送手段（３）と、
上記生成された伝送パケットを上記出所エッジデバイスから、上記１またはそれ以上の内部通信ネットワークを介してデータリンク層レベルで、上記決定されたターゲットエッジデバイスへ伝送する伝送パケット伝送手段（４）と、
を含むことを特徴とするシステム。
【請求項１４】
上記データパケット転送手段（３）が、
上記ネクストホップアドレスが、個別アドレスであるのか、またはネットワークアドレスであるのかを決定し、上記ネクストホップアドレスが個別アドレスである場合には上記データパケットを上記ネクストホップアドレスへ送り、上記ネクストホップアドレスがネットワークアドレスである場合には上記データパケットをその中に含まれる行先アドレスへ送るアドレス手段（３１）を含む、
ことを特徴とする請求項１３に記載のシステム。
【請求項１５】
上記１またはそれ以上のルーティングテーブル（ＲＴ１、…、ＲＴＮ）は、行先アドレスプレフィックス及びそれらに対応する上記ネクストホップのアドレスを含むネットワークのルーティング情報を維持するように構成されていることを特徴とする請求項１３または１４に記載のシステム。
【請求項１６】
上記１またはそれ以上のスイッチング指定テーブル（ＫＴ１、…、ＫＴＮ）は、ネクストホップのアドレス及びそれらに対応する上記ターゲットエッジデバイスのアドレス及びネットワークインタフェースを含むネットワークのスイッチング情報を維持するように構成されていることを特徴とする請求項１５に記載のシステム。
【請求項１７】
上記１またはそれ以上のエッジデバイス（ＲＬ１、…、ＲＬＮ）は更に、上記エッジデバイスが上記外部ネットワークから上記ネットワークの新しい、または変化したルーティング情報を受信した時に、当該エッジデバイスのルーティングテーブル及びスイッチングテーブルを更新し、受信された上記ネットワークのルーティング情報及び上記ネットワークの関連スイッチング情報から更新パケットを生成し、そして上記生成された更新パケットを１またはそれ以上の他のエッジデバイスへ伝送する更新手段（５）を含むことを特徴とする請求項１６に記載のシステム。
【請求項１８】
上記１またはそれ以上の更新手段（５）は、もし必要ならば、上記更新手段が受信した上記更新パケットに基づいて、当該更新手段を含むエッジデバイスのルーティングテーブル及びスイッチングテーブルを更新するように構成されていることを特徴とする請求項１７に記載のシステム。
【請求項１９】
上記１またはそれ以上の更新手段（５）は更に、上記更新手段が受信した上記更新パケット内に含まれるネットワークのルーティング情報を、当該更新手段を含むエッジデバイスが接続されている１またはそれ以上の上記外部ネットワークへ転送するように構成されていることを特徴とする請求項１８に記載のシステム。
【請求項２０】
上記システムが更に、
第１の内部通信ネットワークと第２の内部通信ネットワークとの間で伝送パケット及び更新パケットを伝送するために、当該両内部通信ネットワークを接続する１またはそれ以上のゲートウェイ（ＧＷ）を含み、
上記ゲートウェイが、
上記第１の内部通信ネットワークのルーティング及びスイッチング情報を維持する第１のルーティングデータベース（ＤＢ１）と、
上記第２の内部通信ネットワークのルーティング及びスイッチング情報を維持する第２のルーティングデータベース（ＤＢ２）と、
を含むことを特徴とする請求項１３−１９の何れか１つに記載のシステム。
【請求項２１】
上記１またはそれ以上のゲートウェイ（ＧＷ）が更に、
上記ゲートウェイが上記第１の内部通信ネットワークから更新パケットを受信した時に、必要に応じて、上記第１のルーティングデータベースを更新するデータベース更新手段（６）と、
上記スイッチング情報内に含まれる上記ターゲットエッジデバイスのネットワークインタフェースを、当該ゲートウェイのネットワークインタフェースに置換することによって上記受信された更新パケットを変更する変更手段（７）と、
上記変更された更新パケットを、上記第２の内部通信ネットワークの１またはそれ以上のエッジデバイスへ伝送する変更された更新パケット伝送手段（８）と、
を含み、
上記１またはそれ以上の更新手段（５）は、もし必要ならば、上記更新手段が受信した上記変更された更新パケットに基づいて、当該更新手段を含むエッジデバイスのルーティングテーブル及びスイッチングテーブルを更新するように構成されていることを特徴とする請求項２０に記載のシステム。
【請求項２２】
上記１またはそれ以上のゲートウェイ（ＧＷ）が更に、
内部通信ネットワークのエッジデバイスから受信した伝送パケットのターゲットエッジデバイスのネットワークインタフェースをルーティングデータベースによって決定し、上記伝送パケット内に含まれる上記ゲートウェイのネットワークインタフェースを上記決定されたターゲットエッジデバイスのネットワークインタフェースに置換し、そして上記伝送パケットを上記ゲートウェイから上記ターゲットエッジデバイスへ転送する置換手段（９）を含み、
上記受信された伝送パケットのターゲットエッジでのネットワークインタフェースは、当該伝送パケットが上記出所エッジデバイスから送られる時には上記ゲートウェイのネットワークインタフェースに置換されている、
ことを特徴とする請求項２１に記載のシステム。
【請求項２３】
上記１またはそれ以上のエッジデバイス及び／またはゲートウェイは、サービスクラス特定待ち行列を含むことを特徴とする請求項１３−２２の何れか１つに記載のシステム。
【請求項２４】
上記１またはそれ以上の内部及び／または外部ネットワークは、ＩＰネットワークであることを特徴とする請求項１３−２３の何れか１つに記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は遠隔通信（テレコミュニケーション、以下、単に通信という）に関する。特定的には、本発明は、分散された、且つダイナミックな手法でパケットをルーティングするための新規な、且つ進歩した方法及びシステムに関する。
【背景技術】
【０００２】
インターネットプロトコル（ＩＰ）を実現するネットワークのような、パケット交換通信ネットワークのためのルーティング方式が数多く知られている。
【０００３】
通信ネットワークは、１組のノードと、それらを接続している媒体とからなる。パケット交換通信ネットワークにおいては、出所（ソース）ノードから行先（デスティネーション）ノードまで伝送されるデータは、通常は１組のデータパケットに分割され、各データパケットは行先ノードまでそれ自体のルートを介して伝送される。出所ノード及び行先ノードが異なるネットワーク内に位置していることが一般的であるから、データパケットは幾つかの異なるネットワークを介して伝播し得る。
【０００４】
従来技術においては、個々のネットワークはルーティング機能を遂行する多くのノード、即ちルーターを備えていることが一般的である。データパケットが出所ノードから行先ノードまで伝播する時に、それは１つのルーターから別のルーターまで伝播する。各ルーターは、１組の行先アドレスプレフィックス、及びそれらに対応するネクストホップアドレスを含むルーティングテーブルを維持している。“ネクストホップ”とは、データパケットをその行先へ送る時に、次に導くと有利なルーターのことである。パケットがあるルーターに到着すると、そのルーターはデータパケットの行先ノードの行先アドレスを読み取る。典型的には、もし読み取った行先アドレスがこのルーターと同一のネットワーク内に位置していなければ、ルーターはルーティングテーブルから行先アドレスのネットワーク部分に対応する、即ちそのデータパケットの行先アドレスプレフィックスに対応するネクストホップアドレスを検索し、データパケットをその決定されたネクストホップへ送る。
【０００５】
ネクストホップとして機能するルーターは、同じことを行う。このようにして、データパケットは、それが行先ノードと同一のネットワーク内に位置しているルータに到着するまで１つのルーターから別のルーターへ送られ、当該ルーターがデータパケットを直接行先アドレスへ伝送する。決定されるネクストホップは、その時点におけるルーターとは異なるネットワーク内に位置していても差し支えない。しかしながら、決定されるネクストホップはその時点におけるルーターと同一のネットワーク内に位置していることが多く、そのためにデータパケットは個々のネットワークを通る時に幾つかの異なるルーターを介して伝播する。各ルーターは、それ自体ルーティング決定を行う。
【０００６】
上述した従来技術のルーティングのさまざまな変形が知られている。ここ数年の間に、いわゆるＣＩＤＲ（クラスレス・インタードメイン・ルーティング）アドレス指定が一般的になってきた。この方式においては、ルーティングテーブルの１組の行先アドレスプレフィックスが、ネットワークトポロジに基づいて１つのグループにグループ化される。これによって、ルーティングテーブル内のエントリの数を減少させることができる。しかしながら、これは、若干の行先アドレスを、ルーティングテーブルの幾つかの異なる行先アドレスプレフィックスに対応させる可能性がある。この場合、ルーティングテーブルの幾つかの異なる行先アドレスプレフィックスから、最も適するもの、即ち最長のものを選択しなければならない。もし、例えば208.12.16/20と208.12.21/24とを二者択一するのであれば、より長い、即ち24ビット長の208.12.21/24が選択される。この演算を最長一致演算、または最長一致プレフィックス演算と呼ぶ。
【０００７】
しかしながら、この従来のルーティングに伴う問題は、各ルーターにおいて各パケット毎にルーティング決定を行うために、効率が低いことである。ＩＰネットワークの場合、ルーティング決定はＬ３層レベル（レベル３、Ｌ３）、即ちネットワーク層レベルで行われるが、そのために障害の検出、それらの探知、及びそれらの回復もＬ３層レベルで遂行しなければならない。これは、例えばこれらの手順をＬ２層レベル（レベル２、Ｌ２）、即ちデータリンク層レベルで行うことができるような状況と比較した場合、極めて低速である。更に、ルーティングノードの数が多くなれば、支え得る性能を達成するためにルーターは必然的に極めて複雑になる。
【０００８】
上述した従来のルーティングの他に、いわゆるフロールーティングも知られている。しかしながら、この方式においては、異なる流れを分類しなければならず、また各流れの状態データを各ルーター内に維持しなければならないので、ルーターが非常に複雑になる。更にたとえフロールーティングであっても、障害の検出、それらの探知、及びそれらからの回復は、低速のＬ３層レベルで遂行しなければならない。
【０００９】
更に、いわゆるＭＰＬＳ（マルチプロトコル・ラベル・スイッチング）が公知である。しかしながら、それを使用するには、全ネットワークの部分がＭＰＬＳをベースとしている必要がある。更に、各経路の状態を各ルーター内に維持しなければならず、ルーターを極めて複雑にする。更に、ＭＰＬＳルーティングの場合には、ＴＥ（トラフィック・エンジニアリング）ルーティング及び障害許容限度が複雑である。ネットワークが大きく、多くの品質クラスが存在する場合には経路の数が大幅に増加する。更に、ＭＰＬＳルーティングは予め構成された経路を使用するので、ダイナミックスが制限される。
【発明の開示】
【発明が解決しようとする課題】
【００１０】
本発明の目的は、上述した欠陥を排除する、またはそれらを少なくとも大幅に軽減する新しい方法及びシステムを提供することである。本発明の１つの特定の目的は、パケット交換通信ネットワークにおいて、分散された、そしてダイナミックな手法でパケットをルーティングすることができる方法及びシステムを提供することである。
【課題を解決するための手段】
【００１１】
本発明においては、パケットのルーティングは、１またはそれ以上の内部通信ネットワークを介して、分散された、そしてダイナミックな手法で遂行される。各内部通信ネットワークは１またはそれ以上のエッジデバイスを含む。各エッジデバイスは、内部ネットワークを、１またはそれ以上の外部通信ネットワークに接続する。内部及び外部ネットワークはパケット交換方式である。
【００１２】
“内部通信ネットワーク”とは、本発明によってルーティングを実現する通信ネットワークのことである。“外部通信ネットワーク”とは、本発明のルーティングを実現しない通信ネットワークのことである。“エッジデバイス”とは、ネットワークの周辺に配置されている、即ちそれ自体のネットワークの他に若干の他のネットワークのノードにも接続されているノードのことである。
【００１３】
データパケットは、外部通信ネットワークから出所エッジデバイスによって受信される。出所エッジデバイスは、受信したデータパケットの行先アドレスプレフィックスに対応するネクストホップアドレスを決定する。“出所エッジデバイス”とは、外部通信ネットワークからデータパケットを受信するエッジデバイスのことをいう。従って、内部通信ネットワークのどのエッジデバイスも、出所エッジデバイスとして機能することができる。
【００１４】
次に、本発明によれば、出所エッジデバイスが決定したネクストホップに対応するターゲットエッジデバイスのアドレス及びネットワークインタフェースが決定される。次いで出所エッジデバイスは、決定されたターゲットエッジデバイスにアドレス指定された伝送パケットを生成する。この伝送パケットは、受信されたデータパケット、決定されたネクストホップのアドレス、及び決定されたターゲットエッジデバイスのネットワークインタフェース、即ちポートを含む。“ターゲットエッジデバイス”とは、生成された伝送パケットがアドレス指定されているエッジデバイスのことである。従って、内部通信ネットワークのどのエッジデバイスも、ターゲットエッジデバイスとして機能することができる。
【００１５】
次に、生成された伝送パケットが出所エッジデバイスから決定されたターゲットエッジデバイスへ、１またはそれ以上の内部通信ネットワークを介してデータリンク層レベルで伝送される。
【００１６】
ターゲットエッジデバイスにおいて、受信された伝送パケットから、データパケット、ネクストホップアドレス、及びターゲットエッジデバイスのネットワークインタフェースが分離される。次いで、ネクストホップアドレスに基づいて、データパケットはターゲットエッジデバイスのネットワークインタフェースを介して転送される。
【００１７】
本発明の一実施の形態においては、ターゲットエッジデバイスのネットワークインタフェースからデータパケットを転送する際に、ネクストホップアドレスが個別アドレスであるのか、またはネットワークアドレスであるのかが決定される。それが個別アドレスである場合には、データパケットはネクストホップアドレスへ送られる。それがネットワークアドレスである場合には、データパケットはその中に含まれる行先アドレスへ送られる。
【００１８】
本発明の一実施の形態においては、１またはそれ以上のエッジデバイス内に、行先アドレスプレフィックス及び対応するネクストホップアドレスを含むネットワークルーティング情報と、ネクストホップアドレス及び対応するターゲットエッジデバイスのアドレス及びネットワークインタフェースを含むネットワークのスイッチング情報とが維持されている。
【００１９】
本発明の一実施の形態においては、エッジデバイスが外部通信ネットワークから新しい、または変化したネットワークルーティング情報を受信すると、そのエッジデバイスが維持しているルーティング及び／またはスイッチング情報が更新され、受信されたネットワークルーティング情報及び関連ネットワークスイッチング情報から更新パケットが生成される。この更新パケットは、１またはそれ以上の他のデバイスへ送られる。
【００２０】
本発明の一実施の形態においては、エッジデバイスが更新パケットを受信すると、もし必要ならば、受信された更新パケットに基づいて、当該エッジデバイスが維持しているネットワークルーティング及び／またはスイッチング情報が更新される。
【００２１】
本発明の一実施の形態においては、受信された更新パケット内に含まれるネットワークルーティング情報は、当該エッジデバイスが接続されている１またはそれ以上の外部ネットワークへ送られる。
【００２２】
本発明の一実施の形態においては、ゲートウェイによって第１の内部通信ネットワークを第２の内部通信ネットワークに接続し、当該ネットワークの間で伝送パケット及び更新パケットを伝送するように構成されている。ゲートウェイ内には、両内部ネットワークのためのルーティング情報及びスイッチング情報が別々に維持されている。
【００２３】
本発明の一実施の形態においては、ゲートウェイが第１の内部通信ネットワークから更新パケットを受信すると、もし必要ならば、ゲートウェイ内に維持されている第１の内部通信ネットワークのルーティング及び／またはスイッチング情報が更新され、受信された更新パケットがそのターゲットエッジデバイスのネットワークインタフェースを当該ゲートウェイのネットワークインタフェースに置換することによって変更され、変更された更新パケットが第２の外部通信ネットワークの１またはそれ以上のエッジデバイスへ伝送され、そしてもし必要ならば、変更された更新パケットを受信したエッジデバイスが維持しているネットワークのルーティング及び／またはスイッチング情報が更新される。
【００２４】
本発明の一実施の形態においては、伝送パケットは、伝送パケットのターゲットエッジデバイスのネットワークインタフェースがゲートウェイのネットワークインタフェースに置換され、更新パケットを受信した第２の内部通信ネットワークの出所エッジデバイスから第１の内部通信ネットワークのターゲットエッジデバイスへ伝送される。伝送パケットは、先ずゲートウェイのネットワークインタフェースへ伝送される。ゲートウェイが維持しているスイッチング情報が、受信された伝送パケットのターゲットエッジデバイスのネットワークインタフェースを決定するために使用される。伝送パケット内に含まれるゲートウェイのネットワークインタフェースは、決定されたターゲットエッジデバイスのネットワークインタフェースに置換される。最後に、伝送パケットは、ゲートウェイから当該ターゲットエッジデバイスへ転送される。
【００２５】
本発明の一実施の形態においては、出所エッジデバイスが外部通信ネットワークからデータパケットを受信すると、それをターゲットエッジデバイスのマルチキャストネットワークインタフェースへ伝送する。
【００２６】
本発明の一実施の形態においては、１またはそれ以上のエッジデバイス及び／またはゲートウェイ内にサービスクラス特定待ち行列が設けられている。
【００２７】
本発明の一実施の形態においては、１またはそれ以上の内部及び／または外部通信ネットワークは、インターネットプロトコル（ＩＰ）を実現する通信ネットワークであるＩＰネットワークである。
【発明の効果】
【００２８】
従来技術と比較して、本発明は極めて効率的な分散したルーターを実現できることが長所である。この効率は、内部通信ネットワークに到来するパケットに対して１つのルーティング決定だけが行われるという事実に基づいている。換言すれば、パケットが出所エッジデバイスに到着すると、同時にそのパケットをどのターゲットエッジデバイスにルーティングするかが決定される。得られたルーティング解答に基づいて、パケットは内部通信ネットワークを介してＬ２層レベルでターゲットエッジデバイスへ直接伝送される。従って、従来のルーティングにおけるように、パケットは、それぞれがＬ３層レベルで新しいルーティング決定を行う幾つかの異なるルーターを介して伝播しない。
【００２９】
更に、本発明によるルーティングは、出所エッジデバイスからターゲットエッジデバイスまでのパケットの伝送が全てＬ２層レベルで行われ、Ｌ２層レベルにおける障害の検出、それらの探知、及びそれらからの回復はミリ秒程度で遂行される（従来技術におけるように、これらの手順をＬ３層レベルにおいて遂行する場合よりもかなり高速である）ので、耐障害性が極めて高い。
【発明を実施するための最良の形態】
【００３０】
図１は、本発明の一方法例のフローチャートである。本方法によれば、パケットは１またはそれ以上の内部パケット交換通信ネットワークを介して、分散された、且つダイナミックな手法でルーティングされる。
【００３１】
例示した図１の方法においては、ステップ１０において、出所エッジデバイスが、データパケットを外部パケット交換通信ネットワークから受信する。次にステップ１１において、出所エッジデバイスは、受信したデータパケットの行先アドレスプレフィックスに対応するネクストホップアドレスを決定する。
【００３２】
ステップ１２において、出所エッジデバイスは更に、決定したネクストホップに対応するターゲットエッジデバイスのアドレス及びネットワークインタフェースを決定する。次いでステップ１３において、出所エッジデバイスは、決定したターゲットエッジデバイスにアドレス指定された伝送パケットを形成する。この伝送パケットは、受信されたデータパケット、決定されたネクストホップアドレス、及び決定されたターゲットエッジデバイスのネットワークインタフェースを含む。次のステップ１４において、出所エッジデバイスは形成した伝送パケットを、決定されたターゲットエッジデバイスへ、１またはそれ以上の内部通信ネットワークを介してデバイスリンク層レベルで伝送する。
【００３３】
ステップ１５において、ターゲットエッジデバイスは、受信した伝送パケットから、データパケット、ネクストホップアドレス、及びターゲットエッジデバイスのネットワークインタフェースを分離する。最後にステップ１６において、ネクストホップアドレスが個別アドレスであるのか、またはネットワークアドレスであるのかを決定する。個別アドレスである場合には、即ち、次のルーターのアドレスである場合には、データパケットは、ターゲットエッジデバイスのネットワークインタフェースを介してネクストホップアドレスへ転送される。ネットワークインタフェースである場合には、即ち、データパケットの最終受信者がそのターゲットエッジデバイスのネットワークインタフェースと同一のサブネットワーク内に位置している場合には、データパケットはその中に含まれる行先アドレスへ、そのターゲットエッジデバイスのネットワークインタフェースを介して直接転送される。
【００３４】
図２ａは、本発明の一システム例の一般的なレベルにおける構成要素を示す図である。図２ｂは、図２ａに示すエッジデバイスＲＬ１の構成要素例をより詳細に示している。図２ａに示されている残余のエッジデバイスも、図２ｂに対応する。図２ｃは、図２ａに示すゲートウェイＧＷの構成要素例をより詳細に示す図である。図２ａ、２ｂ、及び２ｃに示すシステムは、パケットを、分散された、そしてダイナミックな手法でルーティングすることを可能にする。
【００３５】
図２ａ、２ｂ、及び２ｃに示すシステム例は、パケット交換内部通信ネットワークＳＶ１、ＳＶ２、及びパケット交換外部通信ネットワークＵＶ１、ＵＶ２、ＵＶ３、ＵＶ４、及びＵＶ５を含む。更に、図２ａ、２ｂ、及び２ｃに示すシステム例は、外部通信ネットワークからデータパケットを受信するためのエッジデバイスＲＬ１、ＲＬ２、ＲＬ３、ＲＬ４、及びＲＬ５を含む。エッジデバイスＲＬ１、ＲＬ２、及びＲＬ３が内部通信ネットワークＳＶ１に関連付けられ、エッジデバイスＲＬ４及びＲＬ５が内部通信ネットワークＳＶ２に関連付けられて図示されている。
【００３６】
図２ａにおいては、図を明瞭にするために、各エッジデバイスＲＬが１つの外部通信ネットワークＵＶに接続されているように示されているが、１またはそれ以上のエッジデバイスを幾つかの外部通信ネットワークに接続できることをも理解されよう。図２ａ、２ｂ、及び２ｃに示すシステム例においては、内部通信ネットワークＳＶ１、ＳＶ２、及び外部通信ネットワークＵＶ１、ＵＶ２、ＵＶ３、ＵＶ４、及びＵＶ５は、ＩＰネットワークである。各エッジデバイスは、例えば、ＢＧＰ（ボーダー・ゲートウェイ・プロトコル）インタフェースを介して、ＯＳＰＦ（オープン・ショーテスト・パス・ファースト）インタフェースを介して、またはＩＳＩＳ（インターメディエットシステム・トゥ・インターメディエットシステム）インタフェースを介してのような、それ自体は公知の手法で外部通信ネットワークに接続することができる。
【００３７】
更に、図２ａ、２ｂ、及び２ｃに示すシステム例においては、各エッジデバイスＲＬ１、ＲＬ２、ＲＬ３、ＲＬ４、及びＲＬ５は、受信したデータパケットの行先アドレスプレフィックスに対応するネクストホップアドレスを決定するためのルーティングテーブルＲＴ１、ＲＴ２、ＲＴ３、ＲＴ４、及びＲＴ５をそれぞれ含んでいる。更に、ルーティングテーブルＲＴ１、ＲＴ２、ＲＴ３、ＲＴ４、及びＲＴ５は、行先アドレスプレフィックス、及びそれらに対応するネクストホップアドレスを含むネットワークのルーティング情報を維持するように構成されている。ルーティングテーブルは、公知の適用可能な記述、または例えば最長一致演算を使用して実現することができる。
【００３８】
更に、図２ａ、２ｂ、及び２ｃに示すシステム例においては、各エッジデバイスＲＬ１、ＲＬ２、ＲＬ３、ＲＬ４、及びＲＬ５は、受信したデータパケットの決定されたネクストホップに対応するターゲットエッジデバイスのアドレス、及びターゲットエッジデバイスのネットワークインタフェース（このネットワークインタフェースを介してそのネクストホップが到達することができる）を決定するためのスイッチングテーブルＫＴ１、ＫＴ２、ＫＴ３、ＫＴ４、及びＫＴ５をそれぞれ含んでいる。更に、スイッチングテーブルＫＴ１、ＫＴ２、ＫＴ３、ＫＴ４、及びＫＴ５は、ネクストホップアドレス、及びそれらに対応するターゲットエッジデバイスのアドレス及びネットワークインタフェースを含むネットワークのスイッチング情報を維持するように構成されている。スイッチングテーブルのネットワークインタフェースは、例えばエッジデバイス特定数（例えば、エッジデバイスのポートにインデックスを付けることによって生成することができる）であることができる。
【００３９】
例えば、データパケットは、外部通信ネットワークＵＶ１から、内部通信ネットワークＳＶ１のエッジデバイスＲＬ１によって受信される。この場合、エッジデバイスＲＬ１のルーティングテーブルＲＴ１が使用され、そのデータパケットの行先アドレスプレフィックスに対応するネクストホップが、例えば、外部通信ネットワークＵＶ３内に位置しているルーターＲであることが決定される。その場合、エッジデバイスＲＬ１のスイッチングテーブルＫＴ１が使用され、当該ネクストホップＲに対応するターゲットエッジデバイスが、内部通信ネットワークＳＶ１（そのアドレス及びネットワークインタフェースは、スイッチングテーブルＫＴ１から明白である）のエッジデバイスＲＬ３であることが決定される。
【００４０】
更に、図２ａ、２ｂ、及び２ｃに示すシステム例においては、各エッジデバイスＲＬ１、ＲＬ２、ＲＬ３、ＲＬ４、及びＲＬ５は、決定されたターゲットエッジデバイスにアドレス指定された伝送パケットを生成するための伝送パケット生成手段１を含む。伝送パケットは、受信されたデータパケット、決定されたネクストホップのアドレス、及び決定されたターゲットエッジデバイスのネットワークインタフェースを含む。更に、各エッジデバイスＲＬ１、ＲＬ２、ＲＬ３、ＲＬ４、及びＲＬ５は、受信した伝送パケットから、データパケット、ネクストホップのアドレス、及びターゲットエッジデバイスのネットワークインタフェースを分離するための伝送パケット分離手段２を含む。例えば、ＩＰネットワークの場合には、伝送パケット内にネクストホップアドレスとして、当該ＩＰネクストホップアドレス、または適当なアドレスインデックスを使用できることを理解されたい。例えば、もし32ビット長のＩＰアドレスの代わりに10乃至16ビット長のインデックスを使用すれば、内部通信ネットワーク内で転送される伝送パケットをかなり短縮することができる。
【００４１】
更に、図２ａ、２ｂ、及び２ｃに示すシステム例においては、各エッジデバイスＲＬ１、ＲＬ２、ＲＬ３、ＲＬ４、及びＲＬ５は、データパケットを、ネクストホップアドレスに基づいて、ターゲットエッジデバイスのネットワークインタフェースを介して送るためのデータパケット転送手段３を含む。このデータパケット転送手段３は、ネクストホップアドレスが、個別アドレスであるのか、またはネットワークアドレスであるのかを決定して、それが個別アドレスである場合にはデータパケットをネクストホップアドレスへ送り、それがネットワークアドレスである場合にはデータパケットをその中に含まれる行先アドレスへ送るアドレス手段３１を含む。
【００４２】
更に、図２ａ、２ｂ、及び２ｃに示すシステム例は更に、生成した伝送パケットを出所エッジデバイスから、１またはそれ以上の内部通信ネットワークを介してデータリンク層レベルで、決定されたターゲットエッジデバイスへ伝送するための伝送パケット伝送手段４を含む。
【００４３】
更に、図２ａ、２ｂ、及び２ｃに示すシステム例においては、各エッジデバイスＲＬ１、ＲＬ２、ＲＬ３、ＲＬ４、及びＲＬ５は、ネットワークの新しい、または変化したルーティング情報を外部ネットワークから受信すると、当該エッジデバイスのルーティング及びスイッチングテーブルを更新し、受信したネットワークのルーティング情報及びそのネットワークの関連スイッチング情報から更新パケットを生成し、そして生成した更新パケットを１またはそれ以上の他のエッジデバイスへ伝送する更新手段５を含む。
【００４４】
ルーティング及びスイッチングテーブルは、例えば、エッジデバイスが例えば第１及び第２のルーティング及びスイッチングテーブルを含むように実現することができる。第１のルーティング及びスイッチングテーブルは受信したルーティング情報に基づいて更新されるが、第２のルーティング及びスイッチングテーブルは、受信したルーティング情報が新しいターゲットネットワークまたは既知のネットワークへのより有利なルートを含む場合に限って更新される。その場合、第１のルーティング及びスイッチングテーブルは同一ターゲットへの幾つかのルートを決定するが、第２のルーティング及びスイッチングテーブルは、例えばより有利なルートのような、１つのルートだけを決定する。
【００４５】
更に、更新手段５は、もし必要ならば、他のエッジデバイスから受信した更新パケットに基づいて、当該更新手段を含むエッジデバイスのルーティング及び更新テーブルを更新し、また受信した更新パケット内に含まれるネットワークのルーティング情報を、当該更新手段を含むエッジデバイスが接続されている１またはそれ以上の外部ネットワークへ転送するように構成されている。ネットワークのルーティング情報は、それ自体は公知の適用可能な標準インタフェースを使用して、エッジデバイスから外部通信ネットワークへ伝送することができる。
【００４６】
更に、図２ａ、２ｂ、及び２ｃに示すシステム例は、内部通信ネットワークＳＶ１と内部通信ネットワークＳＶ２との間で伝送パケット及び更新パケットを伝送するために、両ネットワークを接続しているゲートウェイＧＷを含む。ゲートウェイＧＷは、内部通信ネットワークＳＶ１のルーティング及びスイッチング情報を維持するためのルーティングデータベースＤＢ１と、内部通信ネットワークＳＶ２のルーティング及びスイッチング情報を維持するためのルーティングデータベースＤＢ２とを含んでいる。ゲートウェイＧＷは更に、ゲートウェイが内部通信ネットワークＳＶ１またはＳＶ２から上述した順序で更新パケットを受信した時に、必要に応じて、ルーティングデータベースＤＢ１またはＤＢ２を更新するためのデータベース更新手段６を含む。ゲートウェイＧＷは更に、スイッチング情報を含むターゲットエッジデバイスのネットワークインタフェースを、ゲートウェイＧＷのネットワークインタフェースに置換することによって、受信した更新パケットを変更するための変更手段７を含む。
【００４７】
更に、図２ａ、２ｂ、及び２ｃに示すシステム例においては、ゲートウェイＧＷは変更した更新パケットを、内部通信ネットワークＳＶ１またはＳＶ２の１またはそれ以上のエッジデバイスへ伝送するための変更済み更新パケット伝送手段８を含む。更に、エッジデバイス内に配列されている更新手段５は、もし必要ならば、それが受信した変更済みの更新パケットに基づいて、その更新手段５を含むエッジデバイスのルーティング及びスイッチングテーブルを更新するように構成されている。更に、ゲートウェイＧＷは、ルーティングデータベースによって、内部通信ネットワークのエッジデバイスから受信した伝送パケットのターゲットエッジデバイスのネットワークインタフェースを決定し（出所エッジデバイスがその伝送パケットを送る時には、受信した伝送パケットのターゲットエッジデバイスのネットワークインタフェースはゲートウェイのネットワークインタフェースに置換されている）、伝送パケット内に含まれるゲートウェイのネットワークインタフェースを決定されたターゲットエッジデバイスのネットワークインタフェースに置換し、そして伝送パケットをゲートウェイからそのターゲットエッジデバイスへ転送するための置換手段９を含む。
【００４８】
更に、図２ａ、２ｂ、及び２ｃに示すシステム例においては、エッジデバイスＲＬ１、ＲＬ２、ＲＬ３、ＲＬ４、及びＲＬ５、及びゲートウェイＧＷは、サービスクラス特定待ち行列を含む。待ち行列の間にサービスクラスに適切に奉仕するための順番を割当てる適用可能な方法（それ自体は公知である）を使用することができる。内部ネットワークがパケット特定情報を伝送する手段になっている場合には、これらの手段を使用することができる。そのようになっていない場合には、例えば、生成される伝送パケットに、パケット特定サービスクラス情報を付加することができる。
【００４９】
更に、図２ａ、２ｂ、及び２ｃに示すシステム例においては、出所エッジデバイスは、外部通信ネットワークからマルチキャスト型データパケットを受信すると、それをエッジデバイスの所定のマルチキャストネットワークインタフェースへ伝送する。エッジデバイスが、外部通信ネットワークから受信したデータパケットがマルチキャスト型であることを認識すると、それを、トラフィック型が内部通信ネットワークによって支えられているという事実に依存して、例えばマルチキャストまたは同報の何れかの型であるとしてその内部通信ネットワークへ送ることができる。更に、パケットは、実際のネットワークインタフェースでない、且つ全てのエッジデバイスに一致する所定のマルチキャストポートへ送られる。これは、例えば、スイッチングテーブルがマルチキャスト／同報アドレス及びマルチキャストポートを含むように実現することができる。エッジデバイスがマルチキャストポートにアドレス指定されたパケットを受信すると、そのパケットは、マルチキャスト樹木が走る外部通信ネットワークを介してそのネットワークのインタフェースへ伝送される。この目的のために、エッジデバイスには、例えばマルチキャストアドレスをそのエッジデバイスのネットワークインタフェースの数表示として記述する特定のテーブルを設けることができる。各ポート自体は、実際のマルチキャストパケットのネクストホップへのルーティングを遂行する。マルチキャストトラフィックの制御は、例えば、外部通信ネットワークに関して公知の適用可能な標準インタフェースによって実現することができる。
【００５０】
本発明は、上述した単なる例示のための実施の形態に限定されるものではない。本発明は、特許請求の範囲に記載されている本発明の範囲内において多くの変更が可能である。
【図面の簡単な説明】
【００５１】
【図１】本発明の一方法を示すフローチャートである。
【図２ａ】本発明の一システムの概要図である。
【図２ｂ】本発明の１つのエッジデバイスをより詳細に示す図である。
【図２ｃ】本発明の１つのゲートウェイをより詳細に示す図である。
【符号の説明】
【００５２】
１    伝送パケット生成手段
２    伝送パケット分離手段
３    データパケット転送手段
４    伝送パケット伝送手段
５    更新手段
６    データベース更新手段
７    変更手段
８    変更済み更新パケット伝送手段
９    置換手段
３１    アドレス手段
ＤＢ    データベース
ＧＷ    ゲートウェイ
ＫＴ    スイッチングテーブル
Ｒ      ルーター
ＲＬ    エッジデバイス
ＲＴ    ルーティングテーブル
ＳＶ    内部通信ネットワーク
ＵＶ    外部通信ネットワーク
【図１】
2005244983.tif 000003
【図２ａ】
2005244983.tif 000004
【図２ｂ】
2005244983.tif 000005
【図２ｃ】
2005244983.tif 000006