(57)【要約】  本発明は、フレームの複数の送信元端末および/または送信先端末を含むフレームスイッチングネットワークにおいて仮想リンクをルーティングする方法に関し、フレームスイッチが物理的接続によって共に接続され、各仮想リンクが、ポイントツーポイントタイプでは、送信元端末と送信先端末との間の前記ネットワークを通る経路によって定義され、マルチポイントタイプでは、一方の送信元端末と他方の複数の送信先端末との間の前記ネットワークを通る複数の経路によって定義される。この方法は、少なくとも1つの所定のトポロジー制約条件を満たすソリューションのセットに対して少なくとも1つのコスト関数を最小化することによってリンクのルーティングを行う。
2009540713.tif 000002
【特許請求の範囲】
【請求項１】
フレームの複数の送信元端末および/または送信先端末を含むフレームスイッチングネットワークにおいて仮想リンクをルーティングするためのプロセスであって、フレームスイッチが物理的接続によって互いに接続され、各仮想リンクが、ポイントツーポイントタイプでは、送信元端末と送信先端末との間の前記ネットワークを通る経路によって定義され、マルチポイントタイプでは、送信元端末と複数の送信先端末との間の前記ネットワークを通る複数の経路によって定義され、少なくとも1つの仮想リンクに対して、
(a)  前記送信元端末と前記送信先端末との間の可能な経路のセットから、少なくとも1つの所定のトポロジー制約条件を満たす経路のサブセットを選択するステップ(250)と、
(b)  前記サブセットの中で、少なくとも1つの所与のコスト関数を最小にするポイントツーポイント仮想リンク用の経路またはマルチポイント仮想リンク用の複数の経路を決定するステップ(260)と、
(c)  このように決定された前記経路に従って前記仮想リンクをルーティングするステップ(295)と
を含むことを特徴とするルーティングプロセス。
【請求項２】
前記仮想リンクがポイントツーポイントリンクであり、前記ネットワークが別個の区域に分割される場合に、前記トポロジー制約条件が、前記送信元端末および前記送信先端末にそれぞれ接続された前記スイッチが同じ区域に属する場合、区域間の横断を禁止する制約条件(435)であり、反対の場合、前記送信元端末および前記送信先端末にそれぞれ属する区域間の単一の横断を許容する制約条件(437)が適用されることを特徴とする請求項1に記載のルーティングプロセス。
【請求項３】
前記選択するステップが、前記ネットワークの前記リンクまたはスイッチと共に同時に既にルーティングされているかまたはルーティングされるべき仮想リンクに対して可能な経路の分離および/または並置の追加のトポロジー制約条件(420)を考慮することを特徴とする請求項1または2に記載のルーティングプロセス。
【請求項４】
前記選択するステップが追加のトポロジー制約条件を考慮に入れ、各付加的なトポロジー制約条件が、同時にルーティングされるべき仮想リンクのセットを形成する経路のグループに関係し、前記グループは前記経路の複数のNsgのサブグループから構成され、前記追加の制約条件は、多くとも0≦nsg<Nsgのような数nsgのサブグループが無効にされることがあり、サブグループに属する経路の全てが前記ネットワークの同じスイッチの障害によって影響される場合にサブグループが無効にされることを表すことを特徴とする請求項1または2に記載のルーティングプロセス。
【請求項５】
前記コスト関数(440)が経路によって横切られたスイッチの数であることを特徴とする請求項2から4のいずれか１項に記載のルーティングプロセス。
【請求項６】
前記仮想リンクがマルチポイントタイプであり、前記ネットワークが別個の区域に分割される場合に、前記送信元端末および前記送信先端末にそれぞれ接続された前記スイッチが同じ区域に属する場合、区域間の横断を禁止する制約条件(5201,…,520K)が、前記リンクの前記送信元端末と送信先端末との間の可能な経路ごとに適用され、反対の場合、前記送信元端末および前記送信先端末にそれぞれ属する区域間の単一の横断を許容する制約条件が適用されることを特徴とする請求項1に記載のルーティングプロセス。
【請求項７】
前記制約条件(5201,…,520K)において、前記リンクの前記送信元と送信先端末との間の前記可能な各経路について、前記リンクまたはスイッチと共に同時に既にルーティングされているかまたはルーティングされるべき仮想リンクに対してこれらの経路の分離および/または並置の追加のトポロジー制約条件が適用されることを特徴とする請求項6に記載のルーティングプロセス。
【請求項８】
前記選択するステップが追加のトポロジー制約条件を考慮に入れ、各付加的なトポロジー制約条件が、同時にルーティングされるべき仮想リンクのセットを形成する経路のグループに関係し、前記グループが前記経路の複数のNsgのサブグループから構成され、前記追加の制約条件は、多くとも0≦nsg<Nsgのような数nsgのサブグループが無効にされることがあり、サブグループに属する前記経路の全てが前記ネットワークの同じスイッチの障害によって影響される場合にサブグループが無効にされることを表すことを特徴とする請求項6に記載のルーティングプロセス。
【請求項９】
前記コスト関数が、経路によって横切られるスイッチの数であり、送信先端末当たり少なくとも1つの候補経路を与えるために前記リンクの前記送信元端末と送信先端末との間の可能な経路のセットごとに最小化される(5301,…,530K)ことを特徴とする請求項6から8のいずれか１項に記載のルーティングプロセス。
【請求項１０】
K個の候補経路の組合せが生成され(540)、Kは前記リンクの送信先端末の数であり、各組合せが前記マルチポイントリンクの可能なルーティングソリューションに対応し、第2コスト関数が、このようにして得られた前記可能なソリューションのセットを対象に最小化される(550)ことを特徴とする請求項9に記載のルーティングプロセス。
【請求項１１】
前記第2コスト関数が、可能な各ソリューションごとに、様々な構成経路間で共有されるスイッチの数を評価することを特徴とする請求項10に記載のルーティングプロセス。
【請求項１２】
同じ機能を行うことに関与し、リンクのバンドルと呼ばれ、前記各リンクがポイントツーポイントであるリンクの少なくとも1つのグループ、および別個の区域に分割されている前記ネットワークについて、前記送信元端末および前記送信先端末にそれぞれ接続された前記スイッチが同じ区域に属する場合、区域間の横断を禁止する制約条件が、前記バンドルの前記各リンクについて、前記リンクの前記送信元端末と前記送信先端末との間の可能な経路ごとに適用され(6201,…,620N)、反対の場合、前記送信元端末および前記送信先端末にそれぞれ属する区域間の単一の横断を許容する制約条件が適用されることを特徴とする請求項1に記載のルーティングプロセス。
【請求項１３】
前記仮想リンクごとに、および前記リンクの前記送信元端末と前記送信先端末との間の前記可能な各経路について、前記リンクまたはスイッチと共に同時に既にルーティングされているかまたはルーティングされるべき仮想リンクに対してこれらの経路の分離および/または並置の追加のトポロジー制約条件が適用される(6201,…,620K)ことを特徴とする請求項12に記載のルーティングプロセス。
【請求項１４】
前記選択するステップが追加のトポロジー制約条件を考慮に入れ、各付加的なトポロジー制約条件が、同時にルーティングされるべき仮想リンクのセットを形成する経路のグループに関係し、前記グループが前記経路の複数のNsgのサブグループから構成され、前記追加の制約条件は、多くとも0≦nsg<Nsgのような数nsgのサブグループが無効にされることがあり、サブグループに属する前記経路の全てが前記ネットワークの同じスイッチの障害によって影響される場合にサブグループが無効にされることを表すことを特徴とする請求項12に記載のルーティングプロセス。
【請求項１５】
前記コスト関数が、経路によって横切られるスイッチの数であり、前記バンドルの前記各リンクについて、リンク当たり少なくとも1つの候補経路を与えるために前記リンクの前記送信元端末と前記送信先端末との間の可能な経路のセットごとに最小化される(6301,…,630N)ことを特徴とする請求項12から14のいずれか１項に記載のルーティングプロセス。
【請求項１６】
N個の候補経路の組合せが生成され(640)、ここで、Nは前記バンドルのリンクの数であり、各組合せは前記バンドルの可能なルーティングソリューションに対応し、第3コスト関数が、このようにして得られた前記可能なソリューションのセットを対象に最小化される(650)ことを特徴とする請求項15に記載のルーティングプロセス。
【請求項１７】
前記第3コスト関数が、バンドルの可能なルーティングソリューションごとに、前記ソリューションがその組合せである前記経路間で共有されるスイッチの数を評価することを特徴とする請求項16に記載のルーティングプロセス。
【請求項１８】
同じ機能を行うことに関与し、リンクのバンドルと呼ばれ、前記各リンクがマルチポイントタイプであるリンクの少なくとも1つのグループ、および別個の区域に分割されている前記ネットワークについて、前記送信元端末および前記送信先端末にそれぞれ接続された前記スイッチが同じ区域に属する場合、区域間の横断を禁止する制約条件が、前記バンドルの前記各リンクについて、前記リンクの前記送信元端末と前記送信先端末との間の可能な経路ごとに適用され(7201,…,720N)、反対の場合、前記送信元端末および前記送信先端末にそれぞれ属する区域間の単一の横断を許容する制約条件が適用されることを特徴とする請求項1に記載のルーティングプロセス。
【請求項１９】
前記仮想リンクごとに、および前記リンクの前記送信元端末と前記送信先端末との間の前記可能な各経路について、前記ネットワークの前記リンクまたはスイッチと共に同時に既にルーティングされているかまたはルーティングされるべき仮想リンクに対してこれらの経路の分離および/または並置の追加のトポロジー制約条件が適用される(7201,…,720N)ことを特徴とする請求項18に記載のルーティングプロセス。
【請求項２０】
前記選択するステップが追加のトポロジー制約条件を考慮に入れ、各付加的なトポロジー制約条件が、同時にルーティングされるべき仮想リンクのセットを形成する経路のグループに関係し、前記グループが前記経路の複数のNsgのサブグループから構成され、前記追加の制約条件は、多くとも0≦nsg<Nsgのような数nsgのサブグループが無効にされることがあり、サブグループに属する前記経路の全てが前記ネットワークの同じスイッチの障害によって影響される場合にサブグループが無効にされることを表すことを特徴とする請求項18に記載のルーティングプロセス。
【請求項２１】
前記コスト関数が、経路によって横切られるスイッチの数であり、前記バンドルの前記各リンクについて、リンク当たりおよび送信先端末当たり少なくとも1つの候補経路を与えるために前記リンクの前記送信元端末と前記送信先端末との間の可能な経路のセットごとに最小化される(7301,…,730N)ことを特徴とする請求項18から20のいずれか１項に記載のルーティングプロセス。
【請求項２２】
K1+K2+…+KNの候補経路の組合せが生成され(740)、ここで、Ki、1<i≦Nは前記バンドルの前記N個のリンクの各経路の数であり、各組合せは前記バンドルの可能なルーティングソリューションに対応し、第4コスト関数が、このようにして得られた前記可能なソリューションのセットを対象に最小化される(750)ことを特徴とする請求項21に記載のルーティングプロセス。
【請求項２３】
前記第4コスト関数が、バンドルの可能なルーティングソリューションごとに、このソリューションに対応する前記バンドルの前記リンクによって横切られるスイッチの数を評価することを特徴とする請求項22に記載のルーティングプロセス。
【請求項２４】
前記ネットワーク区域が個別の電力供給源によって供給されることを特徴とする請求項2、6、12、18のいずれか１項に記載のルーティングプロセス。
【請求項２５】
前記第2、第3、または第4コスト関数のうち1つを最小化することによって得られた前記ルーティングソリューションのセットを対象にして、前記ネットワークの最も重い負荷のスイッチのトラフィック負荷を評価する第5コスト関数が最小化されることを特徴とする請求項1から24のいずれか１項に記載のルーティングプロセス。
【請求項２６】
コンピュータ上で実行される場合、請求項1から25のいずれか1項に記載の前記プロセスのステップを実行するのに好適なソフトウェア手段を含むコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、フレームスイッチングネットワークにおけるルーティングの分野に関し、より詳細には、AFDXネットワークに関する。
【背景技術】
【０００２】
イーサネット（登録商標）ネットワークは、ローカルネットワークの中で最もよく知られたものである。それらは、全く異なったものであるが互いに互換性をもつ2つのモード、すなわち、単一の物理媒体が端末間で共有され、ランダムアクセスおよびフレーム衝突の検出を備えるいわゆる共有モード、および端末が仮想接続によってフレームを交換し、それにより衝突のないことを保証するいわゆるスイッチモードの下で機能することができる。
【０００３】
スイッチ型イーサネット（登録商標）ネットワークでは、各端末、すなわち送信元または送信先はフレームスイッチに個別に接続され、スイッチは互いに物理的接続によって接続される。より具体的には、各スイッチは、他のスイッチまたは端末カプラのポートに接続された複数のポートを有する。送信元端末と送信先端末との間の仮想接続は、ネットワークを通る経路と、その後に続く送信先端末に向けた送信元端末からのフレームで定義される。同様に、仮想接続は、これらのフレームが通過するスイッチのリストによって定義される。通過されるスイッチごとに、フレームスイッチングが、送信先アドレスに基づいて、予め決められたスイッチングテーブルによって行われる。スイッチングテーブルがスイッチ入力ポートおよびフレーム送信先アドレスに基づいて対応する出力ポートを示すため、このスイッチングテーブルは非常に簡単である。
【０００４】
フレームスイッチングネットワークの別のよく知られている実施例は、送信元と送信先との端末間に基本フレームまたはセルをルーティングするために仮想回路接続(VCC)を確立することができるATMネットワークである。
【０００５】
発明者らは、「仮想リンク」という用語を、スイッチ型イーサネット（登録商標）ネットワークにおける仮想接続またはATMネットワークにおける仮想回路接続などのフレームスイッチングネットワークのレベル-2終端間接続を指すために使用する。フレームスイッチングネットワークでは、仮想リンクは、ネットワークを通して、制御計画を用いて管理的に、または信号送信することによってルーティングされる。リンクのルーティングは、ネットワークの様々なスイッチのスイッチングテーブルを定義することと、プログラムすることとからなる。一般に、これらのスイッチングテーブルは、静的(管理ルーティング)または動的(信号送信によるルーティング)とすることができる。
【０００６】
場合によっては、仮想リンクによってサービスの一定の保証を得ることが可能である。例えば、ATMネットワークでは、CBR(固定ビットレート)サービスクラスによると、一定帯域幅および最小フローレートをリンク上で確保することができる。しかし、スイッチは所与の最大フローレートしかサポートできないため、このサービス保証はリンクのルーティングに制約条件を課す。
【０００７】
同様に、航空ニーズのために開発されたAFDX(アビオニクス全二重スイッチ型イーサネット（登録商標）)ネットワークは、仮想リンクによって帯域幅を確保することが可能なスイッチ型イーサネット（登録商標）ネットワークである。より具体的には、各仮想リンクは、フレーム間の最小間隔ならびに最大フレームサイズに関連する。さらに、フレームをルーティングする最大時間または待ち時間は、仮想リンクごとに保証される。スイッチが出力ポート当たり所与のフローレートしか保証できない場合は、仮想リンク特性の保証は再びルーティング制約条件の影響下にある。
【０００８】
本発明は、好ましくは（しかし排他的でなく）AFDXネットワークに適用される。このネットワークの詳細な説明は、非特許文献１と、本出願者の名前で出願された特許文献１とに記載されている。その主な特性を、以下簡単に要約する。
【０００９】
上述のように、AFDXネットワークはスイッチ型イーサネット（登録商標）ネットワークに基づく。それは、各端末が別個の仮想リンク上でフレームを同時に送信し受信することができる全二重ネットワークでもある。仮想リンクが、待ち時間、ストリームの物理的分離、帯域幅、およびフローレートに関して保証された特性を有するという意味で、AFDXネットワークは決定論的でもある。したがって、各仮想リンクは、終端間で確保され、送信間隔への時間断片化(帯域幅割当てギャップに関してBAGと呼ばれる)を有し、最大フレームサイズをもつ経路を具備する。フレームは、所定のジッタ許容度で各送信間隔の冒頭に送られる。最後に、AFDXネットワークは、可用性の理由で二重にされるという意味で冗長である。
【００１０】
データは、イーサネット（登録商標）フレームにカプセル化されたIPパケットの形態で送信される。古典的なイーサネット（登録商標）スイッチング(送信先イーサネット（登録商標）アドレスを使用する)とは異なり、AFDXネットワーク上のフレームスイッチングはフレームヘッダに連結された仮想リンク識別子を使用する。スイッチが入力ポートのうちの1つでフレームを受信すると、スイッチは仮想リンク識別子を読み取り、スイッチングテーブルに基づいて、フレームが送信されるべき出力ポートを決定する。スイッチは、飛行中、送信されたフレームの完全性を確認するが、フレームが不正確である場合、再送信を要求せず、不正確として検出されたフレームは除去される。仮想リンク上を搬送されるフレームは順々に番号を付けられる。受信時に、送信先端末はフレームシーケンスの完全性を確認する。
【００１１】
各仮想リンクは一方向である。フレームは一度に1つの送信元端末だけから出るが、複数の送信先に達することができる。単一の送信先だけに貢献するポイントツーポイントモードの仮想リンクは、複数の送信先に貢献するマルチポイントモードの仮想リンクと区別される。
【００１２】
図1は、端末LRU1〜LRU5およびフレームスイッチSW1，SW2を含むAFDXネットワークを概略的に示す。端末LRU3をLRU2に接続する仮想リンクVL3はポイントツーポイントタイプであり、一方、端末LRU2，LRU3に貢献する仮想リンクVL2と、端末LRU3，LRU5とに貢献するVL1とは、マルチポイントタイプであることが分かる。
【００１３】
幾つかの仮想リンクは同じ機能を行うことに関与するため、それらは互いに強く依存する。例えば、航空機の様々な航法センサの仮想リンクは同じ位置決め機能に関与する。以下、「機能バンドル」または単に「バンドル」という用語を、同じ機能に関与するポイントツーポイントまたはマルチポイントタイプの仮想リンクの任意のセットを指すために使用する。
【００１４】
ATMネットワークおよびAFDXネットワークなどのサービス保証を提供するフレームスイッチングネットワークは、仮想リンクにルーティング制約条件を課すことを必要とする。さらに、機内搭載用途、特に、航空用途では、追加の予防策が必要とされ、その結果として、通常、ルーティング制約条件が生じる。
【先行技術文献】
【特許文献】
【００１５】
【特許文献１】仏国特許出願公開第2832011号明細書
【非特許文献】
【００１６】
【非特許文献１】「AFDX protocol tutorial」www.condoreng.com
【非特許文献２】Jean-Yves Le Boudec、「Application of network calculus to guaranteed service networks」IEEE Trans. on Information Theory、44巻、3号、1998年5月
【発明の概要】
【発明が解決しようとする課題】
【００１７】
これまで、AFDXネットワークのリンクのルーティングは経験的に行われている。このタイプのルーティングは、比較的少数の仮想リンクでは許容することができる。航空システムの複雑さが増加するのにつれ、仮想リンクの数は、現在、数千に達することがある。本発明は、ルーティング制約条件を全て考慮に入れ、ネットワークの使用の安全性を最適化できる体系的で自動的なルーティングプロセスを提供するものである。
【課題を解決するための手段】
【００１８】
本発明は、物理的接続によって互いに接続される複数のフレーム送信元端末および/または送信先端末を含むフレームスイッチングネットワークにおいて仮想リンクをルーティングするためのプロセスによって定義され、各仮想リンクは、ポイントツーポイントタイプでは、送信元端末と送信先端末との間の前記ネットワークを通る経路によって定義され、マルチポイントタイプでは、送信元端末と複数の送信先端末との間の前記ネットワークを通る複数の経路によって定義される。前記プロセスは、少なくとも1つの仮想リンクに対して、
(a)  送信元端末と1つまたは複数の送信先端末との間の可能な経路のセットから、少なくとも1つの所定のトポロジー制約条件を満たす経路のサブセットを選択するステップと、
(b)  前記サブセットの中で、少なくとも1つの所与のコスト関数を最小にするポイントツーポイント仮想リンク用の経路またはマルチポイント仮想リンク用の複数の経路を決定するステップと、
(c)  このように決定された経路に従って前記仮想リンクをルーティングするステップとを含む。
【００１９】
第1代替構成によれば、前記仮想リンクがポイントツーポイントリンクであり、ネットワークが別個の区域に分割されるとき、前記トポロジー制約条件は、好ましくは、送信元端末および送信先端末にそれぞれ接続されたスイッチが同じ区域に属する場合、区域間の横断を禁止する制約条件として表され、反対の場合、前記送信元端末および送信先端末に属する区域間の単一の横断を許容する制約条件が適用される。選択するステップは、前記ネットワークの前記リンクまたはスイッチと共に同時に既にルーティングされている、またはルーティングされるべき仮想リンクに対して可能な経路の分離および/または並置の追加のトポロジー制約条件を考慮することができる。代替的に、または累積的に、選択するステップは追加のトポロジー制約条件を考慮することができ、各追加のトポロジー制約条件は、同時にルーティングされるべき仮想リンクのセットを形成する経路のグループに関係し、前記グループは前記経路の複数のNsgのサブグループから構成され、前記追加の制約条件は、多くとも0≦nsg<Nsgのような数nsgのサブグループが無効にされることがあり、サブグループに属する経路の全てが前記ネットワークの同じスイッチの障害によって影響される場合にサブグループが無効にされることを表す。
【００２０】
上述のコスト関数は、経路によって横切られるスイッチの数と等しくなるように選ぶことができる。
【００２１】
第2代替構成によれば、前記仮想リンクがマルチポイントタイプであり、ネットワークが別個の区域に分割される場合、送信元端末および前記送信先端末にそれぞれ接続されたスイッチが同じ区域に属する場合、区域間の横断を禁止する制約条件が、好ましくは、前記リンクの前記送信元端末と送信先端末との間の可能な経路ごとに適用され、反対の場合、前記送信元端末および前記送信先端末にそれぞれ属する区域間の単一の横断を許容する制約条件が適用される。上述のように、前記リンクの前記送信元端末と前記送信先端末との間の可能な各経路について、前記リンクまたはスイッチと共に同時に既にルーティングされている、またはルーティングされるべき仮想リンクに対してこれらの経路の分離および/または並置の追加のトポロジー制約条件を適用することが可能である。代替的に、または累積的に、選択するステップは追加のトポロジー制約条件を考慮することができ、各追加のトポロジー制約条件は、同時にルーティングされるべき仮想リンクのセットを形成する経路のグループに関係し、前記グループは前記経路の複数のNsgのサブグループから構成され、前記追加の制約条件は、多くとも0≦nsg<Nsgのような数nsgのサブグループが無効にされることがあり、サブグループに属する経路の全てが前記ネットワークの同じスイッチの障害によって影響される場合にサブグループが無効にされることを表す。
【００２２】
コスト関数は、経路によって横切られるスイッチの数と等しくすることができ、送信先端末当たり少なくとも1つの候補経路を与えるために前記リンクの前記送信元端末と送信先端末との間の可能な経路のセットごとに最小化されることになる。好ましくは、K個の候補経路の組合せが生成され、Kはリンクの送信先端末の数であり、各組合せは前記マルチポイントリンクの可能なルーティングソリューションに対応し、第2コスト関数が、このようにして得られた前記可能なソリューションのセットを対象に最小化される。この第2コスト関数は、可能なソリューションごとに、様々な構成経路間で共有されるスイッチの数を評価する。
【００２３】
第3代替構成によれば、同じ機能を行うことに関与し、リンクのバンドルと呼ばれ、各リンクがポイントツーポイントであるリンクの少なくとも1つのグループ、および別個の区域に分割されているネットワークについて、送信元端末および送信先端末にそれぞれ接続されたスイッチが同じ区域に属する場合、区域間の横断を禁止する制約条件が、前記バンドルの各リンクについて、前記リンクの送信元端末と送信先端末との間の可能な経路ごとに適用され、反対の場合、前記送信元端末および前記送信先端末にそれぞれ属する区域間の単一の横断を許容する制約条件が適用される。上述のように、仮想リンクごとに、および前記リンクの送信元端末と送信先端末との間の可能な各経路について、前記リンクまたはスイッチと共に同時に既にルーティングされている、またはルーティングされるべき仮想リンクに対してこれらの経路の分離および/または並置の追加のトポロジー制約条件を適用することが可能である。代替的に、または累積的に、選択するステップは追加のトポロジー制約条件を考慮することができ、各追加のトポロジー制約条件は、同時にルーティングされるべき仮想リンクのセットを形成する経路のグループに関係し、前記グループは前記経路の複数のNsgのサブグループから構成され、前記追加の制約条件は、多くとも0≦nsg<Nsgのような数nsgのサブグループが無効にされることがあり、サブグループに属する経路の全てが前記ネットワークの同じスイッチの障害によって影響される場合にサブグループが無効にされることを表す。
【００２４】
前記コスト関数は、経路によって横切られるスイッチの数と等しくなるように選ぶことができ、前記バンドルの各リンクについて、リンク当たり少なくとも1つの候補経路を与えるために前記リンクの送信元端末と送信先端末との間の可能な経路のセットごとに最小化されることになる。好ましくは、N個の候補経路の組合せが生成される。ここで、Nは前記バンドルのリンクの数であり、各組合せは前記バンドルの可能なルーティングソリューションに対応する。第3コスト関数は、このようにして得られた前記可能なソリューションのセットを対象に最小化される。第3コスト関数は、バンドルの可能なルーティングソリューションごとに、前記ソリューションがその組合せである経路間で共有されるスイッチの数を評価する。
【００２５】
第4代替構成によれば、同じ機能を行うことに関与し、リンクのバンドルと呼ばれ、各リンクがマルチポイントタイプであるリンクの少なくとも1つのグループ、および別個の区域に分割されているネットワークについて、送信元端末および送信先端末にそれぞれ接続されたスイッチが同じ区域に属する場合、区域間の横断を禁止する制約条件が、前記バンドルの各リンクについて、前記リンクの送信元端末と送信先端末との間の可能な経路ごとに適用され、反対の場合、前記送信元端末および前記送信先端末にそれぞれ属する区域間の単一の横断を許容する制約条件が適用される。上述のように、仮想リンクごとに、および前記リンクの送信元端末と送信先端末との間の可能な各経路について、前記ネットワークの前記リンクまたはスイッチと共に同時に既にルーティングされている、またはルーティングされるべき仮想リンクに対してこれらの経路の分離および/または並置の追加のトポロジー制約条件を適用することが可能である。代替的に、または累積的に、選択するステップは追加のトポロジー制約条件を考慮することができ、各追加のトポロジー制約条件は、同時にルーティングされるべき仮想リンクのセットを形成する経路のグループに関係し、前記グループは前記経路の複数のNsgのサブグループから構成され、前記追加の制約条件は、多くとも0≦nsg<Nsgのような数nsgのサブグループが無効にされることがあり、サブグループに属する経路の全てが前記ネットワークの同じスイッチの障害によって影響される場合にサブグループが無効にされることを表す。
【００２６】
前記コスト関数は、経路によって横切られるスイッチの数と等しくなるように選ぶことができ、前記バンドルの各リンクについて、リンク当たりおよび送信先端末当たり少なくとも1つの候補経路を与えるために前記リンクの送信元端末と送信先端末との間の可能な経路のセットごとに最小化されることになる。好ましくは、K1+K2+…+KNの候補経路の組合せが生成される。ここで、Ki（1<i≦N）は、前記バンドルのN個のリンクの各経路の数であり、各組合せは前記バンドルの可能なルーティングソリューションに対応する。第4コスト関数が、このようにして得られた前記可能なソリューションのセットを対象に最小化される。第4コスト関数は、バンドルの可能なルーティングソリューションごとに、このソリューションに対応するバンドルのリンクによって横切られるスイッチの数を評価する。
【００２７】
上述の代替の全てにおいて、前記ネットワーク区域は、例えば、個別の電力供給源によって供給される。
【００２８】
最後に、代替にかかわらず、好ましくは、第2、第3、または第4コスト関数のうち1つを最小化することによって得られたルーティングソリューションのセットを対象にして、ネットワークの最も重い負荷のスイッチのトラフィック負荷を評価する第5コスト関数を最小化する。
【００２９】
本発明は、さらに、コンピュータ上で実行されるとき、上述で定義されたプロセスのステップを実行するのに好適なソフトウェア手段を含むコンピュータプログラムにも関する。
【図面の簡単な説明】
【００３０】
【図１】AFDXネットワークの実施例を概略的に示す図である。
【図２】本発明の実施形態による仮想リンクルーティング方法の構成チャートを概略的示す図である。
【図３Ａ】マルチポイント仮想リンクの場合にコスト関数を最小化するための手順を示す図である。
【図３Ｂ】マルチポイント仮想リンクの場合にコスト関数を最小化するための手順を示す図である。
【図３Ｃ】マルチポイント仮想リンクの場合にコスト関数を最小化するための手順を示す図である。
【図３Ｄ】マルチポイント仮想リンクの場合にコスト関数を最小化するための手順を示す図である。
【図３Ｅ】マルチポイント仮想リンクの場合にコスト関数を最小化するための手順を示す図である。
【図４】ポイントツーポイント仮想リンクのルーティングの実施例を示す図である。
【図５】マルチポイント仮想リンクのルーティングの実施例を示す図である。
【図６】ポイントツーポイント仮想リンクのバンドルのルーティングの実施例を示す図である。
【図７】マルチポイント仮想リンクのバンドルのルーティングの実施例を示す図である。
【図８】緩和された分離制約条件に従う、仮想リンクを形成する経路のグループの実施例を示す図である。
【図９】緩和された分離制約条件下の仮想リンクのルーティングの実施例を示す図である。
【図１０Ａ】許容できるルーティング構成を示す図である。
【図１０Ｂ】許容できないルーティング構成を示す図である。
【発明を実施するための形態】
【００３１】
本発明の基本概念は、可能な経路の中から、1つの所定のトポロジー制約条件または複数の所定のトポロジー制約条件を満たすものを選択し、次にそれらの中から所定のコスト関数を最小にするものを選択することによって仮想リンクのルーティングを行うことである。
【００３２】
図2は、本発明によるルーティングプロセスの原理を示している。
【００３３】
前記プロセスは、入力において、
・ネットワークのトポロジー、すなわちエンドノード(端末)、スイッチングノード、およびノード間の物理的接続を記述するファイル210と、
・ネットワークの状態、すなわちスイッチのポートの容量、およびそれらの特性で既にルーティングされている仮想リンクを与えるファイル220と、
・ルーティングされるべき仮想リンクの特性を与えるファイル230であって、各仮想リンクが、その中に、送信元端末および1つの送信先端末(ポイントツーポイントモード)または複数の送信先端末(マルチポイントモード)にそれぞれ接続されたスイッチの識別子、送信間隔(BAG)の期間、リンク上のフレームの最大長さ、機能バンドルに属する可能な経路、および場合に応じてバンドルの識別子によって記述されるファイル230と、
・以下で詳細に説明されるトポロジー制約条件を明示するファイル240とを使用する。
【００３４】
アルゴリズムは、ステップ250において、前記ファイル240で示された1つのトポロジー制約条件または複数のトポロジー制約条件を満たす送信元端末と送信先端末との間の経路の選択を含んでいる。
【００３５】
前記アルゴリズムは、第2ステップ260において、1つのコスト関数の最小化または複数のコスト関数の最小化を連続的にまたは連帯して含んでいる。連帯最小化のため、以下で詳述されるように、複合コスト関数が上述のコスト関数の一次結合として生成され、重み係数がルーティング選択でのコストの相対的重要度を反映するように選ばれる。代わりに、コスト関数は優先順位を低減させる順に1つずつ最小化され、各最小化は前の最小化ステップによって与えられたソリューションのサブセットを対象に行われる。
【００３６】
前記コスト関数の最小化が複数の等価なソリューションを与える場合、1つのソリューションがそれらから任意に選ばれる。ステップ260の結果のソリューションは、仮想リンクがルーティングするのを可能にする1つの経路(ポイントツーポイントモード)または複数の経路(マルチポイントモード)を与える。ステップ270で、ネットワーク220の状態ファイルが更新される。アルゴリズムは、ルーティングされるべき仮想リンクが枯渇するまで繰り返して続行する。
【００３７】
ステップ280において、前記仮想リンクの全てがルーティングされていることが確認され、それらがルーティングされている場合、実施形態に従って、ネットワークの決定性の確認が、ステップ290において行われる。このステップは、従来技術、例えば、非特許文献２で知られている「ネットワーク計算法」と呼ばれるアルゴリズムによって管理される。このアルゴリズムは、ネットワークの要素ごとに、ネットワークのポイントの全てのトラフィックエンベロープと、潜在端末と、待ち行列の大きさとに基づいて計算される。決定性が、ネットワークの要素ごとに、限界のある待ち時間と、待ち行列の正確なサイズ設定とのために保証される。
【００３８】
最後に、フレームスイッチのスイッチングテーブルが、ステップ295において更新される。これらのスイッチングテーブルは、ネットワーク上のリンクのルーティングを明確に設定する。
【００３９】
前記ルーティングプロセスは、ネットワークが活性化される初回に、および/または仮想リンクを変更または追加する必要のある度に、実行することができる。
【００４０】
前記トポロジー制約条件は、2つの別個のタイプ、すなわち、絶対的制約条件および相対的制約条件である。
【００４１】
前記絶対的制約条件は、ネットワーク上の他のリンクの存在と無関係に仮想リンクのルーティングを評価する。例えば、航空機に搭載されたAFDXネットワークの場合、航空機の「左」側および「右」側に対応してネットワークの「左」側および「右」側が異なる供給バスによって供給される。1つの電源の障害が全ネットワークを危険にさらさないように、
・ネットワークの一方の側に配置された送信元端末から、反対側に配置された送信先端末に導く仮想リンクは、ネットワークの2つの側を分離する境界を一度だけ横断することができ、仮想リンクがマルチポイントタイプである場合、制約条件はリンクを形成する経路ごとに適用され、
・ネットワークの一方の側に配置された送信元端末から、同じ側に配置された送信先端末に貢献する仮想リンクは、ネットワークの2つの側を分離する境界を横断することができない
というトポロジー制約条件が課せられる。
【００４２】
この規則は、区域の任意の端末が、第3区域を通過することなく、別の区域の任意の端末に貢献することができるという条件で、ネットワークが任意の複数の別個の区域に分割され得る場合へと容易に一般化される。ネットワークの様々な区域は、例えば、個別の電力供給源によって供給される。区域内仮想リンクは当該の区域内でルーティングされ、一方、区域間仮想リンクは、第3区域を通過することなく、前記区域を分離する境界を一度だけ横断する。
【００４３】
他の前記絶対的トポロジー制約条件、例えばネットワークの要素との並置または分離などを確立することができる。これは、仮想リンクがネットワークの所与の要素(例えば、スイッチまたは物理的接続)を必ず通過するか、または反対に、仮想リンクがこの要素を避けることを指定することができることを意味する。ネットワークの複数の要素を備えた並置は仮想リンクの明確なルーティングをもたらすことができると考慮される。したがって、仮想リンクは「固定」されると言える。
【００４４】
前記相対的トポロジー制約条件は、互いに仮想リンクに関係する。したがって、仮想リンク間の並置制約条件または分離制約条件を確立することが可能である。これは、2つの仮想リンクがネットワークの同じスイッチを通過すること、または反対に2つの仮想リンクがいかなる共通のスイッチも共有しないことを指定できるということを意味する。相対的トポロジー制約条件は、同じ機能バンドルの異なる仮想リンクに関係することができ、その場合、与えられる制約条件は、分離制約条件である。相対的トポロジー制約条件は、別個の機能バンドルに属する仮想リンクに関係することもできる。両方の場合において、仮想リンクの並置/分離へのトポロジー制約条件は、前記リンクと共に同時に既にルーティングされているリンク、またはルーティングされるべきリンクに関して表すことができる。
【００４５】
前記並置および/または分離に関して表された相対的トポロジー制約条件は厳密すぎて、ルーティングソリューションを得ることができない可能性がある。この場合、これらの制約条件の幾つか、または全てでさえ、以下に示されるように緩和される。
【００４６】
前記仮想リンクの個々に独立したルーティングは予想することができないため、ルーティングが同時に行われる仮想リンクのセットが考慮される。これらの各仮想リンクは、一般に1つの経路(ポイントツーポイントリンク)、またはより多くの経路(マルチポイントリンク)を含んでいる。以下で仮想リンクのグループと呼ばれる、これらの仮想リンクを形成する経路の全ては、複数のサブグループに分割することができ、経路は複数のサブグループに属することができる。一般に、サブグループは、仮想リンクの前記セットによって与えられる機能のインスタンスに対応する。換言すると、様々なサブグループは、単一の機能の実行についてある程度の冗長度を示している。
【００４７】
前記経路のグループのサブグループの数がNsgである場合、緩和された分離制約条件が仮想リンクの前記セットに課され、それによると、0≦nsg<Nsgの場合、Nsgのうち多くともnsgのサブグループがスイッチの障害によって無効にされ得る。nsg=0の場合は、無効にされるサブグループが許容されない特定の状況に対応する。スイッチの障害は、誤りのあるスイッチもしくは存在しないスイッチ、または切り替えられたフレームの破損のいずれかを意味する。無効にされたサブグループは、経路の全てが同じスイッチの障害によって影響されるサブグループを意味する。
【００４８】
前記分離制約条件がネットワークの冗長度を考慮し、仮想リンクを形成する経路の全てに画一的な方法で適用されない限り、緩和された分離制約条件は分離制約条件よりも多くの柔軟性を与えることが理解される。
【００４９】
前記緩和された分離制約条件の実施例は下記の付録で与えられる。
【００５０】
上述のように、前記トポロジー制約条件を満足する可能性のある候補のサブセットを選択した後、ルーティングアルゴリズムは可能性のある候補の中から1つまたは複数のコスト関数を最小にする1つまたは複数のものを探索する。
【００５１】
考慮している第1コスト関数は、仮想リンクによって横断されるスイッチの数である。より具体的には、リンクがポイントツーポイントのタイプである場合、このリンクによって横断されるスイッチの数を最小にすることが求められる。リンクがマルチポイントタイプである場合、最小化は、リンクを形成する各経路について横断されたスイッチの数に関係する。横断されるスイッチが少数である場合、仮想リンクまたは前記リンクを形成する各経路の障害の確率が低減される。
【００５２】
第2コスト関数は、マルチポイント仮想リンクに関係する。第2コスト関数は、前記マルチポイントリンクを形成する経路に共有されるスイッチの数で定義される。
【００５３】
第3コスト関数は、リンクのバンドルに関係する。第3コスト関数は、同じバンドルに属する仮想リンクに共有されるスイッチの数で定義される。
【００５４】
第2または第3コスト関数の最小化により、場合に応じて、同じ仮想リンクまたは同じバンドルの仮想リンクの経路の連帯障害の確率が低減される。
【００５５】
第4コスト関数もリンクのバンドルに関係する。これは、同じバンドルの仮想リンクの全てによって横断されたスイッチの総数で定義される。
【００５６】
第5コスト関数は、ネットワークの最も負荷が重いスイッチの出力ポートのフローレートで定義される。この関数の最小化は、ネットワーク内のトラフィック負荷の分布を最適化するものである。
【００５７】
前記コスト関数のこれらの実施例は、決して限定的なものではない。特にネットワークの1つの要素または複数の要素の障害の影響を定量化するものである限り、他のコスト関数を考えることができる。
【００５８】
前記コスト関数の連続的最小化は、最適でないソリューションのセットをもたらすことができる。代替の実施形態によれば、コスト関数の一次結合は、ルーティングにおけるこれらの関数の相対的重要度を反映する重み係数によって生成され、このようにして生成された新しいコスト関数は可能なソリューションのセットを対象に最小化される。同様に、新しいコスト関数はコスト関数の積として生成することができ、各コスト関数はルーティングにおける相対的重要度を反映する指数を割り当てられる。
【００５９】
図3Aから3Eは、前記マルチポイント仮想リンクの場合にコスト関数を最小化するための手順を示す。
【００６０】
ルーティングされるべき前記仮想リンクは送信元端末E1から生じ、送信先端末R1，R2に貢献する。トポロジー制約条件を満たす経路が予め選択されていると仮定される。第1コスト関数の最小化は、送信元端末E1から送信先端末R1と、送信元端末E1から送信先端末R2とに接続する可能な各経路の中で、最小数のスイッチを横断するものを探索することによって行われる。この場合、最小数は、経路E1〜R1ならびに経路E1〜R2に対して3である。最適ソリューションが、図3Aから3Dに示される。しかし、図3Eに示されたソリューションは最適ではないことに留意されたい。確かに、それは仮想リンク全体のスイッチの数を最小化しているが、その各構成経路について最小化していない(端末E1〜R2を接続する経路は4のコストを有する)。
【００６１】
前記第2コスト関数の最小化は、4つの前のソリューションの中で、図3A、3B、および3Dに示されたものが保持されることを示す。確かに、それらについて、2つの経路間で共有するスイッチの数は1に等しいが、図3Cでは2に等しい。
【００６２】
前記第5コスト関数の最小化は、前のステップで保持された3つのソリューションの間でどれかを決定できるようにする。デフォルトによって、選ばれたソリューションが、残されているソリューションから任意に選ばれる。
【００６３】
ルーティングの問題は、前記制約条件下で1つまたは複数のコスト関数を最小化する問題になる。好ましくは、制約条件下でのコスト関数は一次不等式の形態で表され、コスト関数は決定変数の一次式である。したがって、最小化はシンプレックスアルゴリズムを使用して行うことができる。シンプレックスアルゴリズムにより以下のタイプの問題を解決できることに留意されたい。
【００６４】
【数１】
2009540713.tif 000003
【００６５】
ここで、bTは一次形式(コスト関数)を表すベクトルであり、xは決定変数のベクトル(正)であり、Aは制約マトリクスを表し、cは一定ベクトルである。
【００６６】
実際に、前記ルーティングアルゴリズムは、入力で、SSで示されるスイッチのリストと、送信元端末および送信先端末の各対について第1のものから第2のものまで行くのを可能にする経路のリストとを有し、各経路はそれが通過するスイッチの順序付きリストによって記載される。以下で、PPは指標付けされた経路のリストを示す。好ましくは、PPは、幾つかの絶対的トポロジー制約条件を、例えば個別の区域への分割に関係するものを既に満たしている経路のリストに予め変えられている。
【００６７】
次に、マトリクスCps，Cfs，Cls，Cpss（最初の3つは次元P×Sを有し、最後の1つは次元P×S×Sを有する）が生成される。ここで、Pはファイル内で指標付けされた経路の総数であり、Sはネットワークのスイッチの総数である。これらのマトリクスの要素は、
swが経路pに属する場合、Cps(p,sw)=1、そうでない場合、Cps(p,sw)=0、
swがpの最初のスイッチである場合、Cfs(p,sw)=1、そうでない場合、Cfs(p,sw)=0、
swがpの最後のスイッチである場合、Cls(p,sw)=1、そうでない場合、Cls(p,sw)=0、
sw1，sw2が経路pの連続するスイッチである場合Cpss(p,sw1,sw2)=1、そうでない場合、Cpss(p,sw1,sw2)=0
で定義され、ここで、pは2つの端末間の経路の識別子であり、sw，sw1，sw2はネットワークのスイッチの識別子である。
【００６８】
前記ルーティングアルゴリズムを簡単にするために、いずれの仮想リンクも機能的バンドルの一部であり、バンドルは必要に応じて単一のリンクに変えることができると考慮される。FFは機能的バンドルのリストを表す。
【００６９】
前記FFのバンドルfはその属性によって決定され、
・f.profileは、バンドルfが単一の仮想リンクを含む(f.profile=1)か否(f.profile=0)かを示し、
・f.ocsは、バンドルに属する仮想リンクのリスト識別子を与える。
【００７０】
前記バンドルfの仮想リンクvlはその属性によって定義され、
・vl.fは、リンクが属するバンドルの識別子を与え、
・vl.costは、仮想リンク上のトラフィックに関するコストを示し、このコストは仮想リンク上のトラフィックに関して表すことができ、このコストは、例えば、送信間隔および最大フレーム長対の関数として表すことができ、
・vl.rtedは、リンクが既にルーティングされている(vl.rted=1)かまたは否(vl.rted=0)かを示し、
・vl.txswは、送信元端末に接続されたスイッチの識別子を与え、
・vl.rxswは、送信先端末(ポイントツーポイントリンク)に接続されたスイッチの識別子、または送信先端末(マルチポイントリンク)にそれぞれ接続されたスイッチの識別子を与える。
【００７１】
前記仮想リンクvlを形成する経路bは、その属性、すなわち
・経路bが属する仮想リンクの識別子b.vlと、
・前記経路によって貢献される送信先端末に接続されたスイッチの識別子b.swDestと
によって定義される。
【００７２】
さらに、GGは、緩和された分離制約条件に従って仮想リンクを形成する経路のグループのリストを表す。前記GGの各グループgは、
グループ内で無効にされるサブグループの最大許容数を示す属性g.sgErrmaxと、
サブグループのリストg.sglistと
によって定義される。
【００７３】
最後に、SGは、前記GGの様々なグループに関係するサブグループのリストを表す。SGの各サブグループsgは、
・サブグループsgが属するグループを示す属性sg.groupと、
・このサブグループを形成する経路のリストsg.pathlistと
によって定義される。
【００７４】
以下の決定変数も導入され、全て正の値をもち、
・vlPath[vl,p]は、前記経路pが仮想リンクvlを形成する場合、1に等しく、そうでない場合、0に等しく、この経路が端末に接続されたスイッチvl.txswを出てvl.rxswのスイッチのうちの1つに到達する場合、経路pがvlを形成することに留意し、
・vlBrSw[vl,swDest,sw]は、swDestで終了する仮想リンクvlを形成する経路がスイッチswを通過する場合、1に等しく、そうでない場合、0に等しく、
・vlBrPerSw[vl,sw]は、スイッチswを通過する仮想リンクvlを形成する経路の数に等しく、
・comBrSw[vl,sw]は、仮想リンクvlを形成する複数の経路がスイッチswを通過する場合、1に等しく、
・vlSw[vl,sw]は、仮想リンクvlがスイッチswを通過する場合、1に等しく、そうでない場合、0に等しく、
・fvlPerSw[f,sw]は、スイッチswを通過する機能的バンドルfの仮想リンクの数に等しく、
・comfSw[f,sw]は、機能的バンドルfの複数の仮想リンクがスイッチswを通過する場合、1に等しく、そうでない場合、0に等しく、
・fSw[f,sw]は、機能的バンドルfの仮想リンクのうちの1つがスイッチswを通過する場合、1に等しく、そうでない場合、0に等しく、
・vlSwNb[vl,sw1,sw2]は、スイッチsw1，sw2を連続的に通過する仮想リンクvlを形成する経路の数に等しく、
・vlSw[vl,sw1,sw2]は、スイッチsw1，sw2を連続的に通過する仮想リンクvlを形成する経路がする存在する場合、1に等しく、
・trfCst[sw1,sw2]は、trfCstPast[sw1,sw2]と、ルーティングされるべき仮想リンクの現在のサブセット上で累積されたスイッチsw1，sw2間のトラフィックコストとの和であり、
・fixvl[sw1,sw2]は、前記現在のサブセットから既にルーティングされており、スイッチsw1，sw2を連続的に通過する仮想リンクが存在する場合、1に等しく、そうでない場合、0に等しく、
・sgSw[sg,sw]は、スイッチswがサブグループsgを形成する経路の全てに共有される場合、1に等しく、そうでない場合、0に等しい。
【００７５】
ソリューション(すなわち、候補仮想リンク)に課せられる基本的制約条件は、前記ソリューションを形成する経路が送信元端末から生じ、送信先端末で終了すること、すなわち、
【数２】
2009540713.tif 000004
および仮想リンクの送信先端末ごとに、送信元端末からの単一の構成経路が存在すること、すなわち、
【数３】
2009540713.tif 000005
である。
【００７６】
前記絶対的トポロジー制約条件の大部分は同じ形式とすることができる。残りの制約条件は、上述のように、最初からセットPPを制限することによって考慮される。
【００７７】
前記相対的トポロジー制約条件も、上述の決定変数に基づいて一次不等式または一次等式の形態で表すことができる。したがって、分離されるべき、すなわち、いかなる共有スイッチも共有することができない構成経路のセットIIごとに、分離制約条件は、
【数４】
2009540713.tif 000006
によって表される。
【００７８】
同様に、前記並置制約条件に従うべき、すなわち、同じスイッチを通過しなければならない構成経路のセットIIについて、
【数５】
2009540713.tif 000007
である。
【００７９】
当然、前記制約条件は、考慮されるべき分離および並置のインスタンスの全てに対して確認されなければならず、各インスタンスは決定されたセットIIに関連する。
【００８０】
代替として、前記緩和された分離制約条件が任意のグループg∈GGに使用される場合、そのような制約条件に従う仮想リンクを形成する経路が存在することになり、
【数６】
2009540713.tif 000008
であり、決定変数sgSw[sg,sw]は、以下の制約条件の
【数７】
2009540713.tif 000009
および
【数８】
2009540713.tif 000010
によって定義され、ここで、
【数９】
2009540713.tif 000011
である。
【００８１】
式(5")は、実際には、
【数１０】
2009540713.tif 000012
である場合、sgSw[sg,sw]=1であり、
そうでない場合、sgSw[sg,sw]=0である。
【００８２】
前記コスト関数も上述の決定変数に基づいて表される。
【００８３】
例えば、前記仮想リンクを形成する経路によって横切られたスイッチの数を別々に最小化するように意図された第1コスト関数CF1は、
【数１１】
2009540713.tif 000013
によって表すことができ、ここで、card(p)は番号づけされたリストpの濃度、換言すると経路pによって横切られたスイッチの数である。
【００８４】
前記各マルチポイント仮想リンクの様々な経路に共有されるスイッチの数を最小化するように意図された第2コスト関数は、
【数１２】
2009540713.tif 000014
によって表すことができることを数学的に示すことが可能である。
【００８５】
同様に、単一の前記機能的バンドルの仮想リンクに共有されるスイッチの数を最小化するように意図された第3コスト関数は、
【数１３】
2009540713.tif 000015
と書き表すことができる。
【００８６】
前記機能バンドルのリンクによって横断されたスイッチの数を最小化するよう意図された第4コスト関数は簡単に
【数１４】
2009540713.tif 000016
によって表すことができることを示すことも可能である。
【００８７】
前記第5コスト関数は、最も軽い負荷をもつスイッチを通過するように仮想リンクをルーティングするものである。ネットワークの状態ファイルおよびルーティングされるべきリンクに基づいて、2つの隣接するスイッチ間のトラフィックコストを決定することが可能である。「隣接するスイッチ」という用語は、ここでは、直接物理的リンクによって接続されたスイッチsw1，sw2を指すために使用される。より具体的には、任意の対の隣接する各スイッチsw1，sw2に対して、それらを連続的に通過する少なくとも1つの仮想リンクがあるかどうかが最初に決定され、
【数１５】
2009540713.tif 000017
である。
【００８８】
決定変数vlSw[vl,sw1,sw2]は、以下の一次制約条件の
【数１６】
2009540713.tif 000018
によってvlSwNb[vl,sw1,sw2]の関数として表される。前記一次制約条件のセットは、実際には、
vlSwNb[vl,sw1,sw2]=0の場合、vlSw[vl,sw1,sw2]=0
vlSwNb[vl,sw1,sw2]≧1の場合、vlSw[vl,sw1,sw2]=1         (12)
を意味する。
【００８９】
同様に、決定変数fixvl[sw1,sw2]は、以下の一次制約条件によって、和の
【数１７】
2009540713.tif 000019
の関数として表され、前記一次制約条件は、
【数１８】
2009540713.tif 000020
であり、ここで
【数１９】
2009540713.tif 000021
であり、ここで、F=Card(FF)である。
【００９０】
前記一次制約条件のセットは、実際には、
【数２０】
2009540713.tif 000022
の場合、fixvl[sw1,sw2]=0であり、
【数２１】
2009540713.tif 000023
の場合、fixvl[sw1,sw2]=1であることを意味する。
【００９１】
次に、前記スイッチsw2に接続されたスイッチsw1の出力ポートのトラフィックコストが、隣接するスイッチの任意の対について評価され、
【数２２】
2009540713.tif 000024
であり、ここで、trfCstPast[sw1,sw2]は、スイッチsw1、sw2間の、すなわち、スイッチsw2に接続されたスイッチsw1の出力ポートにおいて既にルーティングされている仮想リンクの全てにわたって累積されたトラフィックコストである。
【００９２】
換言すると、前記トラフィックコストの計算は、既にルーティングされているリンク(vl.rted=1)と、ルーティングされるべきリンク(vl.rted=0)とを対象に行われる。trfCstPast[sw1,sw2]の値は、固定仮想リンクによって誘導される、すなわち、ルーティングが明確であるトラフィックコストの値によって初期化される。それは、ネットワークの状態ファイルに記憶することができる。
【００９３】
次に、前記第5コスト関数は、
【数２３】
2009540713.tif 000025
として、一次制約条件の
【数２４】
2009540713.tif 000026
を課することによって、
【数２５】
2009540713.tif 000027
のように表される。
【００９４】
前記一次制約条件のセットは、実際には、スイッチsw1，sw2の任意の対について、
fixvl[swl,sw2]=1の場合、trfCstw[sw1,sw2]=trfCst[sw1,sw2]
fixvl[sw1,sw2]=0の場合、trfCstw[swl,sw2]=0                     (18)
を意味する。
【００９５】
これにより、前記決定変数trfCstw[sw1,sw2]の中で、ルーティングされるべき仮想リンクの寄与だけと、これらの間でスイッチsw1，sw2を通過するものだけとを考慮することが可能になる。
【００９６】
前記コスト関数の連帯最小化を行うことが望ましい場合、新しい関数の
【数２６】
2009540713.tif 000028
すなわち、重み係数0≦αi≦1を有する関数CFiの一次結合が生成される。これは、最終的に、決定値の形態で最適のルーティングソリューションを与える最小コスト関数CFを探索することである。複数の最適ソリューションが上述の意味で存在する場合、それらのうちの1つが任意に選ばれる。
【００９７】
代わりに、前記コスト関数は優先順位を低減させる順に1つずつ最小化することができ、各最小化は前の最小化ステップによって与えられたソリューションのサブセットを対象とする。この実施形態では、制約条件は、最小化ステップ間で考慮することができる。
【００９８】
前記コスト関数の連帯最小化によるものかまたは連続最小化によるものかにかかわらず、仮想リンクの数が多い場合、セットFFの全体最適化は非常に長い演算時間になることがある。
【００９９】
好ましくは、次に、前記セットは可能な最低の濃度をもつ個別のサブセットに分割され、相対的トポロジー制約条件およびコスト関数の最小化が各サブセット内にのみ適用される。単一の機能バンドルの仮想リンクを別々にルーティングすることができない場合は、各サブセットは必ず1つまたは複数のバンドルによって形成される。ルーティングアルゴリズムは前記サブセットに順に適用される。
【０１００】
しかし、前記サブセットの独立性が不完全となることがあることに留意されたい。したがって、コスト関数CF5の最小化は、原理上、ルーティングされるべき仮想リンクの全てを巻き込む。この場合、最小のルーティング自由度をもつ仮想リンクのサブセットが好ましく、例えば、そのサブセットのリンクは、原理上、より短いことになり、これらのサブセットはルーティングプロセスによって優先して扱われる。
【０１０１】
本発明によるルーティングの実施例を、搭載ネットワーク用として以下に与える。これらの実施例では、コスト関数は連続的に最小化される。対象としているルーティングユニットは、この場合、機能バンドルであり、仮想リンクは単一のリンクをもつバンドルであると考慮される。
【０１０２】
図4は、前記送信元端末E1と送信先端末R1との間のポイントツーポイント仮想リンク(または1リンクバンドル)のルーティングの実施例を概略的に示す。
【０１０３】
ステップ410において、前記基本的制約条件が、送信元端末と送信先端末との間の可能な経路を決定するために適用される。
【０１０４】
ステップ420において、既にルーティングされている前記仮想リンクが存在している場合、それらを考慮して相対的トポロジー制約条件が適用され、次に、ステップ430において、端末がネットワークの同じ側にあるかどうかが判定される。そうである場合、ステップ435において、非横断(区域内ルーティング)制約条件が適用され、コスト関数CF1は前の制約条件による可能なソリューションのセットを対象に最小化される。しかし、端末がネットワークの同じ側にない場合、ステップ437において、横断(1つの単一の区域間横断)制約条件が適用され、第1の場合のように、コスト関数CF1が可能なソリューションのセットを対象に最小化される。
【０１０５】
ステップ435またはステップ437が単一の前記ルーティングソリューションを与えない場合、プロセスはステップ440において残りのソリューションを対象にコスト関数CF5を最小化することによって継続される。ネットワークの状態ファイルがステップ450において更新される。
【０１０６】
図5は、前記送信元端末E1と複数のK個の送信先端末R1，R2，…，RKとの間でマルチポイント仮想リンク(または1リンクバンドル)をルーティングする実施例を概略的に示す。
【０１０７】
前記端末の対(E1，RK)ごとに、ステップ5101，5102，…，510Kにおいて、基本的制約条件が、送信元端末E1と送信先端末R1，R2，…，RKとの間で可能な経路だけを保持するように適用される。
【０１０８】
ステップ5201，5202，…，520Kにおいて、前記相対的トポロジー制約条件が、既にルーティングされているリンクを考慮に入れて、様々な経路に個々に適用される。
【０１０９】
可能な経路のK個の各セットにおいて、前記コスト関数CF1が各ステップ5301，5302，…，530Kにおいて個々に最小化される。
【０１１０】
次に、ステップ540において、前記ステップ5301，5302，…，530Kによって与えられた経路の組合せの全てがそれぞれ生成される。このようにして、当該の仮想リンクに対する可能なルーティングソリューションのセットが得られる。
【０１１１】
次に、ステップ550において、コスト関数CF2がこれらの可能なソリューションのセットを対象に最小化される。
【０１１２】
前記ステップ550が単一のソリューションを与えない場合、ステップ560において、コスト関数CF4が残りのソリューションのセットを対象に最小化される。
【０１１３】
前記ステップ560が依然として単一のソリューションを与えない場合、コスト関数CF5がステップ570において残りのソリューションのセットを対象に最小化され、ネットワークの状態ファイルがステップ580において更新される。
【０１１４】
図6はN個の前記ポイントツーポイント仮想リンクのバンドルをルーティングする実施例を概略的に示す。各リンクは送信元端末Eiから出て、送信先端末Riに貢献し、ここで1<i≦Nである。
【０１１５】
ステップ610iにおいて前記端末の対(Ei，Ri)ごとに、基本的制約条件が、送信元端末Eiと送信先端末Riとの間で可能な経路だけを保持するように適用される。
【０１１６】
ステップ620i，630i，640は、前記ステップ640において可能なルーティングソリューションの全てがリンクのバンドルに対して得られることを除いて、ステップ520K，530K，540と同等である。
【０１１７】
次に、ステップ650において、コスト関数CF3が可能な前記ソリューションのセットを対象に最小化される。
【０１１８】
前記ステップ650が単一のソリューションを与えない場合、ステップ660において、コスト関数CF4が残りのソリューションのセットを対象に最小化される。
【０１１９】
ステップ660が依然として単一の前記ソリューションを与えない場合、コスト関数CF5がステップ670において残りのソリューションのセットを対象に最小化され、ネットワークの状態ファイルがステップ680において更新される。
【０１２０】
図7は、N個の前記マルチポイント仮想リンクのバンドルをルーティングする実施例を概略的に示す。各仮想リンクVLiは送信元端末Eiから出て、Kiの送信先端末Rikに貢献し、ここで、1<i≦Nおよび1<k≦Kiである。
【０１２１】
ステップ710iにおいて、図5におけるように、前記基本的制約条件が端末の対(Ei，Rik)の全てに適用され、ここで1<k≦Kiであり、次に、ステップ720iにおいて、相対的トポロジー制約条件が適用される。
【０１２２】
ステップ720iの結果から、仮想リンクVLiを形成するための可能な経路のKiのセットPikが得られ、前記セットPikは所与の対(Ei，Rik)に関連する。
【０１２３】
ステップ730iにおいて、図5の前記ステップ5301〜530Kにおけるように、コスト関数CF1がこれらの各セットを対象に最小化される。
【０１２４】
ステップ740において、前記ステップ730iで保持された経路の全てに関する可能な組合せが、組合せごとに、対(Ei，Rik)当たり1つの経路だけが選択されるという条件で生成される。このようにして、各組合せは、保持されるK1+K2+…+KN経路に対応する。したがって、可能なルーティングソリューションのセットが様々な仮想リンクVLiに対して得られ、すなわちバンドルの可能なルーティングソリューションのセットが得られる。
【０１２５】
構成チャートの残りの部分は図6のそれと同一であり、ステップ750，760，770，780は、前記各ステップ650，660，670，680に示されたものと同一である。
【０１２６】
(付録)
前記緩和された分離制約条件は、一般に、同時にルーティングされるべき仮想リンクを形成する経路のグループに関係する。
【０１２７】
図8に、そのような経路のグループが象徴的に示す。
【０１２８】
3つの仮想リンクVL1，VL2，VL3が同時にルーティングされることになり、それらの構成経路は、
【数２７】
2009540713.tif 000029
であると仮定される。
【０１２９】
図示の実施例では、前記緩和された分離制約条件に従う経路のグループGGは、Nsg=4のサブグループの
【数２８】
2009540713.tif 000030
に分割される。
【０１３０】
前記緩和された分離制約条件は、単一のスイッチの障害によって無効にされ得るサブグループの最大数のnsg<Nsgによって表される(例えば、スイッチの障害は、サブグループsg1の経路
【数２９】
2009540713.tif 000031
に影響することになる)。換言すると、少なくともNsg-nsgのサブグループは、各々、スイッチの障害によって損なわれない少なくとも1つの経路を含む。
【０１３１】
前記緩和された分離制約条件の適用の実施例を以下に与える。飛行管理システム(FMS)と飛行管制および誘導ユニット(FCGU)との間の仮想リンクのルーティングが考慮される。飛行管理システムは、古典的に、誘導操作および飛行管理操作においてパイロットを支援する役割を果たす。飛行管制および誘導ユニットは誘導命令および飛行制御命令を算出する。
【０１３２】
航空機が2つの前記FMSシステムおよび4つのFCGU計算機を含み、各FMSシステムが、図9に示されるように、4つのFCGU計算機用の(マルチポイント)仮想リンクの送信元にあると仮定する。図示のアーキテクチャは「クロスチェック」タイプであり、各FCGU計算機は2つのFMSシステムから飛行パラメータを受信し、比較を行う。単一の計算機によって受信されたパラメータが異なる場合、計算機は誤りを指摘し、パラメータに基づく処理を行わない。安全要件は、パラメータの誤りが1つを超える計算機によって見逃されたままにならないことを必要とする。aは、FMSシステムによって送信され、正確であると仮定されたパラメータ、またはさらにそのようなパラメータのフレームを表し、a*はFCGU計算機によって受信された、不正確なパラメータ、またはさらに不正確なパラメータのフレームを表し、誤りはスイッチの障害に起因する。
【０１３３】
図10Aおよび10Bに示されるように、2つの前記不正確なパラメータ/不正確なフレームが同一である場合、計算機は両側の破損の場合(図10AのFCGU1Aならびに図10BのFCGU1AおよびFCGU2Aの場合)に誤りを検出しないことがある。この状況が1つを超える計算機について生じてはならない。したがって、図10Aに示される状況(単一の見逃された誤り)は許容できるが、図10Bのそれ(2つの見逃された誤り)は容認できない。
【０１３４】
前記グループGGは、ルーティングされるべき2つの仮想リンクの
【数３０】
2009540713.tif 000032
を形成する経路から構成されるように考慮され、グループGGは、FCGU計算機が存在するのと同数のサブグループsg1，sg2，sg3，sg4に分割され、各サブグループは対象としている計算機用のFMSシステムからの2つの経路を含む。したがって、スイッチの障害が、4つのサブグループ(Nsg=4)の中でわずか1つのサブグループ(nsg=1)しか無効にしないことが必要とされる。この緩和された分離制約条件により、わずか1つのFCGU計算機しかネットワークのスイッチの障害に起因する誤りを診断し損なわないことが保証できる。
【符号の説明】
【０１３５】
VL1  仮想リンク
LRU1  端末
SW1  フレームスイッチ
E1  送信元端末
R1  送信先端末
210，220，230，240  ファイル
250，260，270，280，290，295  ステップ
410，420，430，435，437，440，450  ステップ
5101，5201，5301，540，550，560，570，580  ステップ
6101，6201，6301，640，650，660，670，680  ステップ
7101，7201，7301，740，750，760，770，780  ステップ
GG  経路のグループのリスト
sg1  サブグループ
FMS1  飛行管理システム
FCGU1A  飛行管制および誘導ユニット
a  正確なパラメータ
a*  不正確なパラメータ
【図１】
2009540713.tif 000033
【図２】
2009540713.tif 000034
【図３Ａ】
2009540713.tif 000035
【図３Ｂ】
2009540713.tif 000036
【図３Ｃ】
2009540713.tif 000037
【図３Ｄ】
2009540713.tif 000038
【図３Ｅ】
2009540713.tif 000039
【図４】
2009540713.tif 000040
【図５】
2009540713.tif 000041
【図６】
2009540713.tif 000042
【図７】
2009540713.tif 000043
【図８】
2009540713.tif 000044
【図９】
2009540713.tif 000045
【図１０Ａ】
2009540713.tif 000046
【図１０Ｂ】
2009540713.tif 000047
【国際調査報告】
2009540713.tif 000048
2009540713.tif 000049
2009540713.tif 000050
2009540713.tif 000051
2009540713.tif 000052
2009540713.tif 000053