(57)【要約】  本発明は、フレームスイッチが物理的接続を通して相互に接続されると共に、複数の送信元端末及び／または前記フレームの複数の送信先端末を備えるフレーム交換ネットワークにおける仮想リンクの経路指定のための方法であって、各仮想リンクが、２地点間接続のタイプに関して、送信元端末と送信先端末との間の前記ネットワークを通る経路によって定義されると共に、各仮想リンクが、多地点間接続のタイプに関して、一方の１つの送信元端末と他方の複数の送信先端末との間の前記ネットワークを通る複数の経路によって定義される方法に関係する。方法は、ネットワークの決定性の検証を可能にするために、方向付けられたループに属する連続したスイッチの“三つの組”に関する分離制限を守りながら、リンクの経路指定を実行する。
2009542068.tif 000002
【特許請求の範囲】
【請求項１】
フレームスイッチが物理的接続を通して相互に接続されると共に、複数の送信元端末及び／または前記フレームの複数の送信先端末を備えるフレーム交換ネットワークにおける仮想リンクの経路指定のための方法であって、
各仮想リンクが、２地点間接続のタイプに関して、送信元端末と送信先端末との間の前記ネットワークを通る経路によって定義されると共に、
各仮想リンクが、多地点間接続のタイプに関して、一方の１つの送信元端末と他方の複数の送信先端末との間の前記ネットワークを通る複数の経路によって定義され、
前記方法が、
（ａ）ネットワークにおいて、それらが含むことになるスイッチの円順列の内部に方向付けられたループを検索する段階と、
（ｂ）それぞれが禁止されるルーティング経路を定義する、各方向付けられたループの中の連続したスイッチの“三つの組”を選択する段階と、
（ｃ）前記禁止される経路をたどらない仮想リンクに関する経路指定の解法を決定する段階と、
（ｄ）このように経路指定された仮想リンクに基づいて、ネットワークの決定性を検証する段階と
を有することを特徴とする経路指定方法。
【請求項２】
もし前記ネットワークの決定性が確認される場合、前記経路指定の解法に対応するスイッチングテーブルが前記スイッチに格納される
ことを特徴とする請求項１に記載の経路指定方法。
【請求項３】
前記ネットワークの決定性の検証が、仮想リンクによって横断されたスイッチの出力におけるフローエンベロープ、及びこれらのリンクに関連する待ち時間の計算を含み、このように獲得された待ち時間が、その場合に、設定された待ち時間の限度と比較される
ことを特徴とする請求項１または請求項２のいずれか一項に記載の経路指定方法。
【請求項４】
前記（ｂ）段階において、考えられるものとして最も多くの方向付けられたループに共通の“三つの組”が選択される
ことを特徴とする請求項１から請求項３のいずれか一項に記載の経路指定方法。
【請求項５】
位相幾何学的な制限によって禁止されるルーティング経路に属する“三つの組”は、優先的に選択される
ことを特徴とする請求項１から請求項４のいずれか一項に記載の経路指定方法。
【請求項６】
独立した電源によって電力を供給された異なる領域に分割されたネットワークに関する前記位相幾何学的な制限は、
−スイッチがそれぞれ同じ領域に属する仮想リンクの送信元端末及び送信先端末に接続されたときに、２つの領域の間の境界を横切るあらゆるルーティング経路と、
−スイッチがそれぞれ異なる領域に属する仮想リンクの送信元端末及び送信先端末に接続されたときに、領域の間の境界を複数回横切るあらゆるルーティング経路と
を禁止することから構成される
ことを特徴とする請求項５に記載の経路指定方法。
【請求項７】
前記フレーム交換ネットワークが、“ＡＦＤＸ”ネットワークである
ことを特徴とする請求項１から請求項６のいずれか一項に記載の経路指定方法。
【請求項８】
コンピュータ上で実行されたときに、請求項１から請求項７のいずれか一項に記載された各段階を実行するように構成されたソフトウェア手段を備える
ことを特徴とするコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、フレーム交換ネットワーク、更に詳しくはＡＦＤＸネットワークにおける経路指定の分野に関係する。
【背景技術】
【０００２】
イーサネット（登録商標）ネットワークは、最も広く知られたローカルネットワークである。それらは、ランダムアクセスとフレーム間の衝突検出によって、同じ物理的媒体が端末の間で共有される、いわゆる共有モード（shared mode）、及び、端末が仮想リンクを介してフレームを交換し、それによって衝突がないことを保証する、いわゆる交換モード（switched mode）の、相互に互換性がある２つの異なるモードの下で動作し得る。
【０００３】
交換イーサネット（登録商標）ネットワーク（switched Ethernet（登録商標） network）において、各端末、すなわち送信元端末または送信先端末は、個々に、フレームスイッチと接続されていると共に、スイッチは、物理的接続を介して相互に接続されている。更に具体的には、各スイッチは、他のスイッチのポートまたは端子連結器（terminal coupler）に接続された複数のポートを備えている。送信元端末と送信先端末との間の仮想リンクは、送信元端末が送信先端末に送信するフレームによってたどられる、ネットワークを通して方向付けられた経路として定義される。同等に、仮想リンクは、これらのフレームによって横断されるスイッチの順序付きリストによって定義される。各横断されたスイッチに関して、送信先のアドレスから、事前に準備された交換テーブルを用いてフレーム交換が成し遂げられる。この交換テーブルは、スイッチの入力ポートとフレームの送信先アドレスに応じて、それが対応する出力ポートを示すので、非常に簡単である。その次に、我々は、その交換テーブルが事前に定義されるフレーム交換ネットワークに興味を示すことになり、そして、我々は、続いて、例えば交換イーサネット（登録商標）ネットワークにおける仮想リンクのような、ネットワークにおけるレベル２の終端間接続（end-to-end）を“仮想リンク”として指定する。
【０００４】
仮想リンクに関して、サービス保証を獲得することは可能である。しかしながら、スイッチが所定の最大のスループットを支援できると仮定すると、このサービス保証は、リンクの経路指定に関して制限を課す。航空学の必要性のために開発されたＡＦＤＸ（アビオニクス全二重交換イーサネット（登録商標）：Avionics Full Duplex Switched Ethernet（登録商標））ネットワークは、仮想リンクを通して帯域幅を割り当てることができる交換イーサネット（登録商標）ネットワークの一例である。更に具体的には、最大のフレームサイズと同様に、フレームの間の最小間隔が各仮想リンクと関連付けられる。更に、フレームを転送するための最大時間、または待ち時間の限界が、各仮想リンクに関して保証される。
【０００５】
ＡＦＤＸネットワークの詳細な説明は、“www.condorencg.com”で指定されるサイト上の“ＡＦＤＸプロトコル指導書（AFDX protocol tutorial）”と題名が付けられた文書の他、出願人の名前において出願された特許出願“ＦＲ−Ａ−２８３２０１１”において発見されることになる。その主な特徴は、単に、これから思い出されることになる。
【０００６】
既に言及されているように、ＡＦＤＸネットワークは、交換イーサネット（登録商標）ネットワークに基づいている。それは、更に、各端末が異なる仮想リンクを介して同時にフレームを送信して受信することができる、全二重タイプのネットワークである。ＡＦＤＸネットワークは、更に、制限された待ち時間、フローの物理的な分離、帯域幅、及びスループットの点から見て、仮想リンクが保証された特徴を有するという意味では、決定論的（deterministic）である。これに適するための各仮想リンクは、予約済みの終端間経路、ＢＡＧＳ（Bandwidth Allocation Gaps）として指定される送信間隔への時間断片化、及び最大のフレームサイズを有する。フレームは、各送信期間の初めに所定のジッタ許容差で送信される。基礎をなすイーサネット（登録商標）ネットワークが、可用性の理由で複写されるので、最終的に、ＡＦＤＸネットワークは冗長である。データは、イーサネット（登録商標）フレーム内のカプセル化されたＩＰパケットとして送信される。（送信先のイーサネット（登録商標）アドレスを使用する）従来のイーサネット（登録商標）交換と異なり、ＡＦＤＸネットワーク上のフレーム交換は、フレームヘッダに含まれる仮想リンク識別子を使用する。スイッチが、その入力ポートの内の１つでフレームを受信するとき、それは仮想リンク識別子を読み取ると共に、交換テーブルから、それを介してフレームが送信されなければならない出力ポートを決定する。スイッチは、送信されたフレームの完全性をオンザフライ（on the fly）で検証するが、しかしながら、もしフレームが誤っている場合でも再送信を要求せず、誤っているとして検出されたフレームは取り除かれる。仮想リンク上で送信されたフレームは、順番に番号を付けられる。受信すると、送信先端末は、フレームのシーケンスの完全性を検証する。
【０００７】
各仮想リンクは、一方向だけに作用する。それは、１つの送信元端末から一度に生じ得るが、しかし、それは、いくつかの送信先端末において終わり得る。単一の送信先のみに貢献する２地点間（または、ユニキャスト)モードの仮想リンクは、いくつかの送信先に貢献する多地点間（または、マルチキャスト)モードの仮想リンクと区別される。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】仏国特許出願公開第２８３２０１１号明細書（ＦＲ−Ａ−２８３２０１１）
【非特許文献】
【０００９】
【非特許文献１】“Rene L. Cruz”著、“A calculus for network delay, Part I: network elements in isolation”及び“Calculus for network delay, Part II: network analysis”、“IEEE Transactions on Information Theory, Vol. 37, No. 1, January 1991, pages 114-141.”
【非特許文献２】“J. Grieu”著、“Analyse et evaluation de techniques de commutation Ethernet（登録商標） pour 1' interconnexion des systemes avioniques（Analysis and evaluation of Ethernet（登録商標） switching techniques for interconnecting avionic systems）”、２００４年９月２４日
【発明の概要】
【発明が解決しようとする課題】
【００１０】
図１は、端末“Ｔ１”から“Ｔ６”及びフレームスイッチ“ＳＷ１”、“ＳＷ２”を含むＡＦＤＸネットワークを概略的に例証する。端末“Ｔ３”を端末“Ｔ２”に接続する仮想リンク“ＶＬ３”は、２地点間タイプのリンクであり、一方、端末“Ｔ３”及び端末“Ｔ２”に貢献する仮想リンク“ＶＬ２”と端末“Ｔ３”から端末“Ｔ５”に貢献する仮想リンク“ＶＬ１”は、多地点間タイプのリンクである。
【００１１】
図２は、ＡＦＤＸネットワークにおけるスイッチを概略的に例証する。それは、ＦＩＦＯタイプの複数の入力バッファ２１０、フレームフィルタリング手段２２０、多重化手段２３０、及びＦＩＦＯタイプの出力バッファ２４０を備える。入力フレームは、様々な入力バッファに格納されると共に、各バッファは、入力ポート“ｅｉ”に接続されている。フィルタリング手段２２０は、承認されていない仮想リンクに対応するフレーム、誤ったフレーム、及びリンクの特性の妨害となるフレームを取り除く。多重化手段２３０は、フレームが含む仮想リンクの識別子、及び交換テーブル上の仮想リンクの識別子に応じて、フレームを様々な出力バッファ２４０の方向に方向付ける。出力バッファは、物理的接続を介してフレームを送信すると共に、各バッファは出力ポート“ｐｉ”に接続されてる。
【００１２】
ＡＦＤＸネットワークにおける仮想リンクの経路指定は、ネットワークの異なるスイッチの交換テーブルを定義することから構成される。経路指定は、異なるリンクの帯域幅制限を順守するように選択される。所定の経路指定の解法に関して、ネットワークは実際には決定論的であり、すなわち様々なリンク上の転送時間は保証された待ち時間の限度（latency bounds）より非常に少ない、ということが検証される。これを実行するために、“network calculus”と表される計算アルゴリズムが、一般的に使用され、それに関する記述は、“IEEE Transactions on Information Theory, Vol. 37, No. 1, January 1991, pages 114-141.”に発表された“A calculus for network delay, Part I: network elements in isolation”及び“Calculus for network delay, Part II: network analysis”と表題が付けられた“Rene L. Cruz”の論文において発見され得る。このアルゴリズムは、ネットワークの各要素に関して、関連のある要素の出力の最大の瞬間的なデータスループットを、非確率的な方法（non-probabilistic way）で評価する。仮想リンク“Ｌｉ”を介して送信元端末によって送信されたトラフィックは、フレームの最大の長さ、及びリンクの２つのフレームを隔てる最短時間間隔によって決まると共に、更にフローエンベロープ関数（flow envelope function）“Ｒｉ（ｔ）”と呼ばれる以下の式（１）の最大トラフィックレート関数（maximum traffic rate function）によってモデル化される。
【００１３】
【数１】
2009542068.tif 000003
【００１４】
ここで、“ｓｍａｘ”はフレームの最大サイズであると共に、“ＢＡＧ”はリンクの帯域幅割当ギャップ（bandwidth allocation gap）と呼ばれる量であり、言い換えれば、“ＢＡＧ”は前記リンクの２つのフレームを隔てる最短時間間隔である。時間間隔［ｔ０、ｔ１］の間にリンクを介して生成されるデータの量は、その場合に、簡単に以下の式のように表される。
【００１５】
【数２】
2009542068.tif 000004
【００１６】
ネットワークの各要素に関して、フローエンベロープ（flow envelope：フロー包絡線）は、この要素の出力において、入力フローエンベロープから、そして前記要素の伝達関数から決定され、更にサービス曲線（service curve）と呼ばれる。入力におけるフローエンベロープ、及び出力におけるフローエンベロープに基づいて、上側の値によって、要素の待ち行列（要素の予備の仕事）のサイズ、及びこの要素を通過するパケットにより経験される遅延を制限するということが知られている。ネットワークの各ポイントにおけるフローエンベロープは、送信元端末から始まって送信先端末まで進むことにより、その結果、段階的に計算される。仮想リンクに関連する待ち時間は、このリンクによって横断される要素において経験された遅延から、そしてもし必要であるならば、これらの要素の間の伝搬時間から推定される。そして、推定された待ち時間が、実際に、ネットワークの異なるリンクに関して、所望の保証された値と一致しているか否かが検証される。
【００１７】
待ち時間を計算するための“network calculus”アルゴリズムの応用例の記述は、２００４年９月２４日の日付が付けられると共に、“Analyse et evaluation de techniques de commutation Ethernet（登録商標） pour 1' interconnexion des systemes avioniques（Analysis and evaluation of Ethernet（登録商標） switching techniques for interconnecting avionic systems）”と表題が付けられた“J. Grieu”の論文の中に発見されることになる。
【００１８】
上述の検証方法は、ネットワークがあらゆる物理的ループを含まないかぎり、良好に機能する。反対に、もしネットワークにそのようなループが存在するならば、ループをたどるリンクの待ち時間は、決定されることができない。
【００１９】
図３は、３つのスイッチ“ＳＷ１、ＳＷ２、ＳＷ３”備えるループを含むＡＦＤＸネットワークの状況を例証する。各スイッチは、３つの物理的ポートを有し、各ポートは入力ポート及び出力ポートから構成される。スイッチ“ＳＷ１”の出力ポート“ｐ１”は、スイッチ“ＳＷ３”の入力ポート“ｅ３”に接続されている。スイッチ“ＳＷ３”の出力ポート“ｐ３”は、スイッチ“ＳＷ２”の入力ポート“ｅ２”に接続されている。スイッチ“ＳＷ２”の出力ポート“ｐ２”は、スイッチ“ＳＷ１”の入力ポート“ｅ１”に接続されている。ポート“ｐ１、ｅ３、ｐ３、ｅ２、ｐ２、ｅ１”を通過する経路“Ｃ”は、ネットワーク内で方向付けられたループを形成する。出力ポート“ｐ１”におけるフローエンベロープは、入力ポート“ｅ１”におけるフローエンベロープ、すなわち出力ポート“ｐ２”におけるフローエンベロープ、及び（“ＳＷ１”の入力における）リンク“ＶＬ１”の入力ポートのフローエンベロープに依存している。同様に、“ｐ２”におけるフローエンベロープは、順繰りに、“ｐ３”におけるフローエンベロープ、及びリンク“ＶＬ３”の入力ポートのフローエンベロープに依存している。最後に、“ｐ３”におけるフローエンベロープは、順繰りに、“ｐ１”におけるフローエンベロープ、及びリンク“ＶＬ２”の入力ポートのフローエンベロープに依存している。フローエンベロープの推定を実行する循環的な依存関係が存在すると共に、従って待ち時間の推定が不可能であるということが理解される。
【００２０】
図４は、４つのスイッチ“ＳＷ１、ＳＷ２、ＳＷ３、ＳＷ４”を備えるループを含むＡＦＤＸネットワークの状況を例証する。各スイッチは、４つの物理的ポートを有し、各ポートは入力ポート及び出力ポートから構成される。ネットワークにおいて、４つの仮想リンク“ＶＬ１”〜“ＶＬ４”が経路指定されたということがわかる。
【００２１】
“ＳＷ１”の出力ポート２３のフローエンベロープは、“ＳＷ３”の出力ポート５のフローエンベロープ、及びリンク“ＶＬ１”の入力ポートのフローエンベロープに依存している。“ＳＷ３”の出力ポート５のフローエンベロープは、“ＳＷ４”の出力ポート２３のフローエンベロープ、及びリンク“ＶＬ３”の入力ポートのフローエンベロープに依存している。“ＳＷ４”の出力ポート２３のフローエンベロープは、“ＳＷ２”の出力ポート２４のフローエンベロープ、及びリンク“ＶＬ４”の入力ポートのフローエンベロープに依存している。最後に、“ＳＷ２”の出力ポート２４のフローエンベロープは、“ＳＷ１”の出力ポート２３のフローエンベロープ、及びリンク“ＶＬ２”の入力ポートのフローエンベロープに依存している。
【００２２】
それからまた、循環的な依存関係によって、フローエンベロープ、及び、従って待ち時間は、推定されることができない。
【００２３】
循環的な依存状態を回避するために、例えばループに接続されていないスイッチの間に物理的な接続を追加するか、またはループのいくつかまたは全てのスイッチに接続された中央スイッチを追加する等、ネットワークの接続形態を変更することが知られている。両方のケースにおいて、接続形態の変更は、局所的に、仮想リンクの可能なルーティング経路の数を増やすと共に、最初の経路指定を変更することができ、そして循環的な依存状態を遮断することができる。しかしながら、それによって、新しいループが作成されないか、または新しいループの経路指定が新しい循環的な依存状態の原因とならないということは確かではない。その場合に、１つは、以前のケースに戻ったであろうと共に、ネットワークの決定性（determinism）についての検証不能は、ネットワークの接続形態の新しい複雑性に通じるであろう。
【００２４】
本発明の目的は、フレーム交換ネットワークにおいて、接続形態の変更なしで、ネットワークの決定性の確実な検証を可能にする、仮想リンクを経路指定するための方法を提案することである。
【課題を解決するための手段】
【００２５】
本発明は、フレームスイッチが物理的接続を通して相互に接続されると共に、複数の送信元端末及び／または前記フレームの複数の送信先端末を備えるフレーム交換ネットワークにおける仮想リンクの経路指定のための方法であって、各仮想リンクが、２地点間接続のタイプに関して、送信元端末と送信先端末との間の前記ネットワークを通る経路によって定義されると共に、各仮想リンクが、多地点間接続のタイプに関して、一方の１つの送信元端末と他方の複数の送信先端末との間の前記ネットワークを通る複数の経路によって定義される方法によって定義される。
【００２６】
その方法は、（ａ）ネットワークにおいて、それらが含むことになるスイッチの円順列の内部に方向付けられたループを検索する段階と、（ｂ）それぞれが禁止されるルーティング経路を定義する、各方向付けられたループの中の連続したスイッチの“三つの組”を選択する段階と、（ｃ）前記禁止される経路をたどらない仮想リンクに関する経路指定の解法を決定する段階と、（ｄ）このように経路指定された仮想リンクに基づいて、ネットワークの決定性を検証する段階とを有する。
【００２７】
もし前記ネットワークの決定性が確認される場合、その場合に、前記経路指定の解法に対応するスイッチングテーブルが前記スイッチに格納される。
【００２８】
前記ネットワークの決定性の検証は、有利に、仮想リンクによって横断されたスイッチの出力におけるフローエンベロープ、及びこれらのリンクに関連する待ち時間の計算を含み、それによって獲得された待ち時間が、その場合に、設定された待ち時間の限度と比較される。
【００２９】
有利な実施例によると、前記（ｂ）段階において、考えられるものとして最も多くの方向付けられたループに共通の“三つの組”が選択される。
【００３０】
前記（ｂ）段階において、位相幾何学的な制限によって禁止されるルーティング経路に属する“三つの組”を優先的に選択することが同様に可能である。
【００３１】
独立した電源によって電力を供給された異なる領域に分割されたネットワークに関するこの位相幾何学的な制限は、−スイッチがそれぞれ同じ領域に属する仮想リンクの送信元端末及び送信先端末に接続されたときに、２つの領域の間の境界を横切るあらゆるルーティング経路と、−スイッチがそれぞれ異なる領域に属する仮想リンクの送信元端末及び送信先端末に接続されたときに、２つの領域の間の境界を複数回横切るあらゆるルーティング経路とを禁止することから構成され得る。
【００３２】
好ましい応用例において、フレーム交換ネットワークは、“ＡＦＤＸ”ネットワークである。
【００３３】
最後に、本発明は、更に、コンピュータ上で実行されたときに、上述の方法の各段階を実行するように構成されたソフトウェア手段を備えることを特徴とするコンピュータプログラムに関係する。
【図面の簡単な説明】
【００３４】
【図１】代表的なＡＦＤＸネットワークを概略的に例証する図である。
【図２】ＡＦＤＸネットワークにおけるスイッチの構造を概略的に例証する図である。
【図３】３つのスイッチを備えるループを含むＡＦＤＸネットワークの状況を例証する図である。
【図４】４つのスイッチを備えるループを含むＡＦＤＸネットワークの状況を例証する図である。
【図５Ａ】本発明の動作原理を例証する図である。
【図５Ｂ】本発明の動作原理を例証する図である。
【図６】本発明による経路指定方法のフローチャートを例証する図である。
【図７】本発明による経路指定方法を適用するための単純化されたＡＦＤＸネットワークの例を例証する図である。
【発明を実施するための形態】
【００３５】
本発明の基本となるアイデアは、可能な経路から、ネットワークの方向付けられたループの一部分による明確な分離制限の影響を受ける経路を選択することによって、仮想リンクの経路指定を実行することである。
【００３６】
以下において、あらゆる規則正しいシーケンスの“ｌ”個のノードまたはネットワークのスイッチが、方向付けられたループとして指定されることになると共に、“Ｎ≧３”という条件で“ｌ＝ＳＷ１、ＳＷ２、．．．、ＳＷＮ”であり、“ｉ＝１、．．．、Ｎ−１”において“ＳＷｉ＋１∈Ｇ（ＳＷｉ）”であり、そして“ＳＷ１∈Ｇ（ＳＷＮ）”である。ここで、“Ｇ”は、各スイッチ“ＳＷ”と、その継承者（successor）のセット、すなわち“ＳＷ”の出力ポートに直接接続されたスイッチのセットとの対応を確立するアプリケーション（application）である。各物理的ポートが入力ポート及び出力ポートを備える全二重ネットワークにおいて、もしネットワークに方向付けられたループ“ＳＷ１、ＳＷ２、．．．、ＳＷＮ”が存在するならば、その場合に“ＳＷＮ、ＳＷＮ−１、．．．、ＳＷ１”は、反対の方向においてではあるが、同様に、方向付けられたループであるということが理解されることになる。
【００３７】
仮想リンクの経路指定を実行する前に、本発明による方法は、ネットワークの方向付けられたループの一覧表が作成される（inventory）。これを実行するために、ネットワークは、それの頂点がスイッチ及び端子であり、出力ポート−入力ポート接続が円弧である、方向付けられた図式として例証され得る。ネットワークにおける方向付けられたループを探索することは、要するに、図式の中の循環路を探索するということになる。この目的のために、図式の各頂点は、ラベル（label）によって分類される。各頂点は、その継承者（successor）に、そのラベルを送信すると共に、これらの継承者のそれぞれは、その場合に、受信されたラベルをそれ自身のラベルと連結させ、そして、それによって連結されたラベルを、それ自身の継承者に送信する。ラベルの伝播は、漸進的に続けられる。頂点がそれ自身に含まれるラベルのリストを受信するとき、循環路が特定されると共に、このリストの伝播が中止される。循環路は、その場合に、同値の部類によってグループ分けされると共に、同じ部類の方向付けられた循環路／ループは、円順列の内部とあらゆる点で等しい。同値の部類あたりに１つの方向付けられたループが、それを表すために任意に選択される。
【００３８】
方向付けられたループが特定されると、それらは、横断したスイッチの数によって分類される。我々は、図５Ａにおいて例証された、そのような方向付けられたループを考察する。ここでは、図５Ａのループは、６つのスイッチ“ＳＷ１”〜“ＳＷ６”の物理的ループに対応する。スイッチ“ＳＷｉ”においてループの中に入ると共に、次のスイッチ“ＳＷｉ＋１”において表に出てくる仮想リンク“ＶＬ”は、既に経路指定されたループ上の仮想リンクの数、及びループが仮想リンクと共有するスイッチの数にかかわらず、ループにおける循環的な依存関係を引き起こすことが可能ではない。実際には、関連したリンク“ＶＬ”は、連続したスイッチの２つの出力ポートを横断しないので、それは、これらのスイッチの出力におけるフローエンベロープの間に何の関係も引き起こさない。
【００３９】
従って、循環的な依存状態は、仮想リンクが、少なくとも３つの連続するスイッチ、すなわち少なくとも２つの共通の出力ポートを、方向付けられたループと共有するときにだけ、引き起こされることができるということが理解される。もし仮想リンクがちょうど３つのスイッチを、図５Ａの方向付けられたループと共有することが考察される場合、ループの回復（ループが戻ってくること）及びその結果としての循環的な依存状態を獲得するために、少なくともこれらの６つのリンク“ＶＬ１、．．．、ＶＬ６”が必要とされるということが知られている。一般的に、Ｎ個のスイッチの方向付けられたループに関して、依存状態は、ループに共通のちょうど３つのスイッチを有する少なくともＮ個のリンクによって獲得され得ると共に、もっと強い理由から、ループに共通の３つ以上のスイッチを有するＮ個のリンクに関して獲得され得る。ちょうど“Ｍ＞２”個のスイッチを方向付けられたループと共有するリンクに関して、そのようなリンクの“Ｅ（Ｎ／（Ｍ−２））”個のリンクが、循環的な依存関係を獲得するために必要とされ、ここで、“Ｅ（．）”は、整数値を表す。
【００４０】
我々は、ここで、所定の方向付けられたループに関して、ループの３つの連続する頂点に対応するルーティング経路が抑制されるということを仮定する。その状況は、図５Ｂにおいて例証され、ここで、破線において例証される経路“ＳＷ１、ＳＷ２、ＳＷ３”が経路指定に関して禁止される。この制限によって、循環的な依存状態を引き起こす仮想リンクによるループの回復を獲得することは、もはや可能ではない。実際には、仮想リンク“ＶＬ１”は、もはや許可されないと共に、規則として定められた制限に対応するあらゆる仮想リンクは、せいぜい経路“ＳＷ１、ＳＷ２”か、または経路“ＳＷ２、ＳＷ３”を含んでいる。いずれの仮想リンクも、及び特に“ＶＬ６”と“ＶＬ２”のいずれも、スイッチ“ＳＷ１”と“ＳＷ３”のフローエンベロープの間で、関係性が引き起こされることを可能にしない。
【００４１】
方向付けられたループの３つの所定の連続するスイッチを通過するルーティング経路を禁止することによって、循環的な依存状態のあらゆる危険性が取り除かれるということが理解される。更に、仮想リンクの経路指定の可能性の数は、比較的、それほどこの禁止令によって影響を受けない（３つのスイッチのループに関して、せいぜい３分の１の減少）。
【００４２】
１つは、上述のように、各方向付けられたループに関して、継続する。有利に、いくつかのループに共通のルーティング経路は、それらの数を減少させるために禁止される。
【００４３】
図６は、本発明による経路指定方法のフローチャートを例証する。ネットワーク６１０の接続形態の記述から、ステップ６２０において、ネットワークの円順列の内部に方向付けられた全てのループが、一覧表に記入（inventory）される。ステップ６３０において、それらは、横断したスイッチの数によって分類される。それによって獲得される方向付けられたループのそれぞれに関して、ステップ６４０において、ループの連続したスイッチの全ての“三つの組”が、その場合に、特定される。ステップ６５０において、いくつかのループに共通の“三つの組”の探索が実行される。ステップ６６０において、ループあたりに１つの“三つの組”が選択される。有利に、それは、考えられるものとして最も多くのループによって共有される“三つの組”をよく使われる順で取得することによって、選択されることになる。選択される“三つの組”は、禁止されるルーティング経路を定義すると共に、該経路を通した経路指定を禁止することによって、循環的な依存関係は、それが属するループまたは複数のループに関して壊され得る。
【００４４】
ステップ６６０において確立された制限を守りながら、ステップ６７０において、仮想リンクを経路指定することに関する解法が決定される。
【００４５】
ステップ６７０において発見された経路指定の解法に関して、ステップ６８０において、リンクによって横断されるスイッチの出力におけるフローエンベロープ、そして異なるリンクに関する待ち時間を推定することによって、ネットワークが実際に決定論的であるか否かが検査される。獲得される待ち時間は、その場合に、前記リンクに関する設定された待ち時間の限度と比較される。
【００４６】
もし決定性が確認されるならば、経路指定の解法に対応する交換テーブルが確立されると共に、スイッチに格納される。もし決定性が確認されないならば、新しい経路指定の解法がステップ６７０において試みられるか、もしくは初期設定により、破線で示されたように、禁止されるルーティング経路の新しい選択がステップ６６０において試みられる。
【００４７】
図７は、本発明による経路指定方法を例証するための単純化されたＡＦＤＸネットワークの例を例証する。
【００４８】
ネットワークは、それぞれ送信元または送信先になり得る５台の端末“Ｔ１”〜“Ｔ５”と、４つのスイッチ“ＳＷ１”〜“ＳＷ４”を備える。ネットワークの円順列の内部に方向付けられたループが特定される。
【００４９】
３つのスイッチのループに関しては、以下のようになる。
【００５０】
【数３】
2009542068.tif 000005
【００５１】
４つのスイッチのループに関しては、以下のようになる。
【００５２】
【数４】
2009542068.tif 000006
【００５３】
各々のループに関して、禁止されるルーティング経路の候補者である“三つの組”が、以下のようにリストアップされる。
【００５４】
【数５】
2009542068.tif 000007
【００５５】
循環的な依存状態のあらゆる危険性を取り除くために、ループあたりに１つの“三つの組”を選択すると共に、対応する経路を通過する経路指定を禁止することは、十分である。有利に、既に言及されたように、禁止される経路の数を減少させるために、考えられるものとして最も多くのループに共通の“三つの組”が選択される。
【００５６】
この場合には、例えば、以下のように選択される。
【００５７】
【数６】
2009542068.tif 000008
【００５８】
従って、理論的に必要とされる６つの経路の代わりに、わずか４つの経路が禁止されることになる。
【００５９】
実際には、経路指定の制限が課されるので、ネットワークの決定性を検証することだけが、仮想リンクの経路指定に関して考慮されるべき制限ではない。例えば、航空電子工学の応用において、独立した電源ソースによって電力を供給された異なる領域にネットワークを分割することが知られている。安全上の理由から、これから先は区分の制限として指定された、−もしスイッチがそれぞれ同じ領域に属する送信元端末及び送信先端末に接続されたならば、２つの領域の間の境界を横切るあらゆるルーティング経路と、−もしスイッチがそれぞれ異なる領域に属する送信元端末及び送信先端末に接続されたならば、領域の間の境界を複数回横切るあらゆるルーティング経路と、を禁止することから構成される位相幾何学的な制限が、その場合に設定される。
【００６０】
第１の段階において、区分の制限という意味で禁止されたルーティング経路のセット“Ｓ”が、一覧表に記入（inventory）される。経路指定されるべき所定の仮想リンクに関して、この制限の順守は、“Ｓ”の経路に関するリンクの分離と同等である。
【００６１】
一般的に、本発明の実施例によると、禁止された経路のセット“Ｓ”は、ネットワークの決定性の検証に関連付けられた経路指定の制限を適用する前に、利用可能であろう。方向付けられたループあたりのスイッチの“三つの組”を選択する際に、既に禁止されたセット“Ｓ”の経路に属する“三つの組”が、有利に選択されることになる。もちろん、もしループのいくつかの“三つの組”が“Ｓ”に属するならば、考えられるものとして最も多くの方向付けられたループに共通の“三つの組”が優先的に選択されることになる。このように、決定性の検証に関して除外される経路の数は、比較的少量で増加することになる。
【符号の説明】
【００６２】
２１０    入力バッファ
２２０    フレームフィルタリング手段
２３０    多重化手段
２４０    出力バッファ
Ｔ１、Ｔ２、Ｔ３、Ｔ４、Ｔ５、Ｔ６    端末
ＳＷ１、ＳＷ２、ＳＷ３、ＳＷ４、ＳＷ５、ＳＷ６    フレームスイッチ
ＶＬ１、ＶＬ２、ＶＬ３、ＶＬ４、ＶＬ５、ＶＬ６    仮想リンク
ｅ１    スイッチ“ＳＷ１”の入力ポート
ｅ２    スイッチ“ＳＷ２”の入力ポート
ｅ３    スイッチ“ＳＷ３”の入力ポート
ｐ１    スイッチ“ＳＷ１”の出力ポート
ｐ２    スイッチ“ＳＷ２”の出力ポート
ｐ３    スイッチ“ＳＷ３”の出力ポート
Ｃ    ポート“ｐ１、ｅ３、ｐ３、ｅ２、ｐ２、ｅ１”を通過する経路
【図１】
2009542068.tif 000009
【図２】
2009542068.tif 000010
【図３】
2009542068.tif 000011
【図４】
2009542068.tif 000012
【図５Ａ】
2009542068.tif 000013
【図５Ｂ】
2009542068.tif 000014
【図６】
2009542068.tif 000015
【図７】
2009542068.tif 000016
【国際調査報告】
2009542068.tif 000017
2009542068.tif 000018
2009542068.tif 000019
2009542068.tif 000020
2009542068.tif 000021
2009542068.tif 000022