(57)【特許請求の範囲】
【請求項１】
ネットワークドメインのエッジノードであって、
前記ネットワークドメインは、複数のフローに属するデータユニットを受信し、該データユニットを前記ネットワークドメイン内にルーティングする少なくとも１つの発信元ノードと、前記ネットワークドメインを介して前記データユニットをルーティングする複数の内部ルータと、前記データユニットを前記ネットワークドメインの外にルーティングする少なくとも１つの宛先ノードとを有しており、前記複数の内部ルータの内の少なくとも１つは、輻輳状態になっているかどうかを検出し、もし前記輻輳状態になっているなら、ルーティングするデータユニットに輻輳マークを付けるように構成されており、前記エッジノードは前記宛先ノードとして動作するように構成されており、
前記エッジノードは制御要素を含み、
前記制御要素は、
前記エッジノードに到着する輻輳マークが付けられたデータユニットの存在を検出する部分と、
輻輳制御処理を起動することにより、輻輳マークが付けられたデータユニットの存在の検出に対して反応する部分とを有する輻輳処理機能を実行するように構成され、
前記輻輳制御処理は、
１ａ）  前記発信元ノードに１つ以上のフローを終了させる命令を送信してトラフィック負荷を低減させる処理と、
１ｂ）  所定の時間待ち合わせ、次いで輻輳マークが付けられたデータユニットが依然として前記エッジノードに到着しているかどうかを判定する処理と、
１ｃ）  前記輻輳マークが付けられたデータユニットが依然として到着しているなら、前記１ａ）と１ｂ）を繰り返す処理
を含むことを特徴とするエッジノード。
【請求項２】
前記制御要素は、
前記輻輳制御処理が前記輻輳マークが付けられたデータユニットの検出に応じて、負荷低減パラメータの値を設定する処理と、
前記命令を、前記負荷低減パラメータの値に従って、前記発信元ノードに１つ以上のフローを終了させるように指示するように構成する処理とをさらに有するように構成されていることを特徴とする請求項１に記載のエッジノード。
【請求項３】
前記制御要素は、前記負荷低減パラメータが絶対負荷と相対負荷の内の１つにより表現されるように構成されていることを特徴とする請求項２に記載のエッジノード。
【請求項４】
前記制御要素は、前記輻輳制御処理がさらに、どのフローが輻輳により影響を受けるのかを検出するフロー検出ルーチンを含むように構成され、
前記命令が前記負荷低減パラメータの値に従って前記フローの内のどれが終了させられることになるのかのフローの表示を含むことを特徴とする請求項２又は３に記載のエッジノード。
【請求項５】
前記制御要素は、前記輻輳制御処理がさらに、どのフローを終了させるのかを選択するフロー選択ルーチンを含むように構成され、
前記命令が前記選択されたフローの表示を含むことを特徴とする請求項４に記載のエッジノード。
【請求項６】
前記輻輳マークが付けられたデータユニットは第１のマーカ或は第２のマーカを有し、
前記第１のマーカは内部ノードのトラフィック負荷が第１の負荷閾値を越えることを示し、
前記第２のマーカは内部ノードのトラフィック負荷が前記第１の負荷閾値より高い負荷に対応する第２の負荷閾値を越えることを示し、
前記制御要素は、前記輻輳制御処理がさらに、前記第１のマーカを検出するのに応じて前記負荷低減パラメータを第１の負荷低減値に設定し、前記第２のマーカを検出するのに応じて前記負荷低減パラメータを第２の負荷低減値に設定する処理を含むように構成され、
前記第２の負荷低減値は前記第１の負荷低減値より大きい負荷低減に対応する値であることを特徴とする請求項２乃至５のいずれか１項に記載のエッジノード。
【請求項７】
前記制御要素は、前記第２の負荷低減値が前記第２の負荷閾値と前記第１の負荷閾値との差に等しい負荷低減に対応するように構成されることを特徴とする請求項６に記載のエッジノード。
【請求項８】
前記制御要素は、前記第２の負荷低減値が前記第２の負荷閾値と前記第１の負荷閾値との差を前記第２の負荷閾値によって除算した商に等しい負荷低減に対応するように構成されることを特徴とする請求項６に記載のエッジノード。
【請求項９】
前記制御要素は、前記輻輳制御処理がさらに
５ａ）前記発信元ノードに１つ以上のフローを終了させる前記命令を送信して一時的な第１の負荷低減値に対応するトラフィック負荷を低減させ、
５ｂ）前記所定の時間待ち合わせ、次いで前記第１のマーカを含む輻輳マークが付けられたデータユニットが依然として前記エッジノードに到着しているかどうかを判定し、
５ｃ）前記第１のマーカが依然として検出されるなら、前記負荷低減パラメータを以前の一時的な値より小さい新しい一時的な第１の負荷低減値に設定し、前記５ａ）と５ｂ）を繰り返す手順を有するように構成されることを特徴とする請求項６乃至８のいずれか１項に記載のエッジノード。
【請求項１０】
前記制御要素は、前記以前の一時的な値より小さい新しい一時的な第１の負荷低減値に設定する処理が、継続的に設定される一時的な第１の負荷低減値の全体的な手順での合計値が前記第２の負荷低減値以下であるように構成されることを特徴とする請求項９に記載のエッジノード。
【請求項１１】
前記制御要素は、前記所定の時間が固定値であるように構成されることを特徴とする請求項１乃至１０のいずれか１項に記載のエッジノード。
【請求項１２】
前記所定の時間は適応的な時間であり、
前記制御要素は、前記所定の時間に対する適応ルーチンが備えられるように構成されることを特徴とする請求項１乃至１０のいずれか１項に記載のエッジノード。
【請求項１３】
前記制御要素は、前記輻輳処理機能が前記発信元ノードから前記宛先ノードまでのデータユニット伝播時間の表示を判断するルーチンを有するように構成され、
前記適応ルーチンが前記データユニット伝播時間の表示に基づいて前記所定の時間を適応させるように構成されることを特徴とする請求項１２に記載のエッジノード。
【請求項１４】
前記データユニット伝播時間の表示を判断するルーチンは、周期的リフレッシュメッセージと、専用照会／応答メッセージと、前記発信元ノードと前記宛先ノードとの間で交換されるキープアライブ・シグナリングメッセージとの内の１つ以上を監視する処理を含むことを特徴とする請求項１３に記載のエッジノード。
【請求項１５】
ネットワークドメインの内部ルータであって、
前記ネットワークドメインは、複数のフローに属するデータユニットを受信し、該データユニットを前記ネットワークドメイン内にルーティングする少なくとも１つの発信元ノードと、前記ネットワークドメインを介して前記データユニットをルーティングする複数の内部ルータと、前記データユニットを前記ネットワークドメインの外にルーティングする少なくとも１つの宛先ノードとを有しており、前記内部ルータは、
前記内部ルータの負荷が第１の負荷閾値または前記第１の負荷閾値より高い第２の負荷閾値を超えるかどうかを検出し、トラフィック負荷が前記第１の負荷閾値を超えるなら、第１のマーカを含む輻輳マーク付きデータユニットを生成し、前記トラフィック負荷が前記第２の負荷閾値を超えるなら、第２のマーカを含む輻輳マーク付きデータユニットを生成するように構成された制御要素を有することを特徴とする内部ルータ。
【請求項１６】
ネットワークドメインの宛先ノードを制御する方法であって、
前記ネットワークドメインは、複数のフローに属するデータユニットを受信し、該データユニットを前記ネットワークドメイン内にルーティングする少なくとも１つの発信元ノードと、前記ネットワークドメインを介して前記データユニットをルーティングする複数の内部ルータと、前記データユニットを前記ネットワークドメインの外にルーティングする少なくとも１つの宛先ノードとを有しており、前記複数の内部ルータの内の少なくとも１つは、輻輳状態になっているかどうかを検出し、もし前記輻輳状態になっているなら、ルーティングするデータユニットに輻輳マークを付けるように構成されており、前記方法は、輻輳処理機能を実行する工程を有し、
前記輻輳処理機能は、
エッジノードに到着する輻輳マークが付けられたデータユニットの存在を検出する部分と、
輻輳制御処理を起動することにより、輻輳マークが付けられたデータユニットの存在の検出に対して反応する部分とを有し、
前記輻輳制御処理は、
１ａ）  前記発信元ノードに１つ以上のフローを終了させる命令を送信してトラフィック負荷を低減させる処理と、
１ｂ）  所定の時間待ち合わせ、次いで輻輳マークが付けられたデータユニットが依然として前記エッジノードに到着しているかどうかを判定する処理と、
１ｃ）  前記輻輳マークが付けられたデータユニットが依然として到着しているなら、前記１ａ）と１ｂ）を繰り返す処理を含むことを特徴とする方法。
【請求項１７】
前記輻輳制御処理は、
前記輻輳マークが付けられたデータユニットの検出に応じて、負荷低減パラメータの値を設定する処理と、
前記命令を、前記負荷低減パラメータの値に従って、前記発信元ノードに１つ以上のフローを終了させるように指示するように構成する処理とをさらに有することを特徴とする請求項１６に記載の方法。
【請求項１８】
前記負荷低減パラメータが絶対負荷と相対負荷の内の１つにより表現されることを特徴とする請求項１７に記載の方法。
【請求項１９】
前記輻輳制御処理がさらに、どのフローが輻輳により影響を受けるのかを検出するフロー検出ルーチンを含み、
前記命令が前記負荷低減パラメータの値に従って前記フローの内のどれが終了させられることになるのかのフローの表示を含むことを特徴とする請求項１７又は１８に記載の方法。
【請求項２０】
前記輻輳制御処理がさらに、どのフローを終了させるのかを選択するフロー選択ルーチンを含み、
前記命令が前記選択されたフローの表示を含むことを特徴とする請求項１９に記載の方法。
【請求項２１】
前記輻輳マークが付けられたデータユニットは第１のマーカ或は第２のマーカを有し、
前記第１のマーカは内部ノードのトラフィック負荷が第１の負荷閾値を越えることを示し、
前記第２のマーカは内部ノードのトラフィック負荷が前記第１の負荷閾値より高い負荷に対応する第２の負荷閾値を越えることを示し、
前記輻輳制御処理がさらに、前記第１のマーカを検出するのに応じて前記負荷低減パラメータを第１の負荷低減値に設定し、前記第２のマーカを検出するのに応じて前記負荷低減パラメータを第２の負荷低減値に設定する処理を含み、
前記第２の負荷低減値は前記第１の負荷低減値より大きい負荷低減に対応する値であることを特徴とする請求項１７乃至１９のいずれか１項に記載の方法。
【請求項２２】
前記第２の負荷低減値が、前記第２の負荷閾値と前記第１の負荷閾値との差に等しい負荷低減に対応することを特徴とする請求項２１に記載の方法。
【請求項２３】
前記第２の負荷低減値が、前記第２の負荷閾値と前記第１の負荷閾値との差を前記第２の負荷閾値によって除算した商に等しい負荷低減に対応することを特徴とする請求項２１に記載の方法。
【請求項２４】
前記輻輳制御処理はさらに
５ａ）前記発信元ノードに１つ以上のフローを終了させる前記命令を送信して一時的な第１の負荷低減値に対応するトラフィック負荷を低減させ、
５ｂ）前記所定の時間待ち合わせ、次いで前記第１のマーカを含む輻輳マークが付けられたデータユニットが依然として前記エッジノードに到着しているかどうかを判定し、
５ｃ）前記第１のマーカが依然として検出されるなら、前記負荷低減パラメータを以前の一時的な値より小さい新しい一時的な第１の負荷低減値に設定し、前記５ａ）と５ｂ）を繰り返す手順を有することを特徴とする請求項２１乃至２３のいずれか１項に記載の方法。
【請求項２５】
前記以前の一時的な値より小さい新しい一時的な第１の負荷低減値に設定する処理は、継続的に設定される一時的な第１の負荷低減値の全体的な手順での合計値が前記第２の負荷低減値以下であるように構成されることを特徴とする請求項２４に記載の方法。
【請求項２６】
前記制御要素は、前記所定の時間が固定値であるように構成されることを特徴とする請求項１６乃至２５のいずれか１項に記載の方法。
【請求項２７】
前記所定の時間は適応的な時間であり、
前記制御要素は、前記所定の時間に対する適応ルーチンが備えられるように構成されることを特徴とする請求項１６乃至２５のいずれか１項に記載の方法。
【請求項２８】
前記輻輳処理機能が、前記発信元ノードから前記宛先ノードまでのデータユニット伝播時間の表示を判断するルーチンを有し、
前記適応ルーチンが前記データユニット伝播時間の表示に基づいて前記所定の時間を適応させるように構成されることを特徴とする請求項２７に記載の方法。
【請求項２９】
前記データユニット伝播時間の表示を判断するルーチンは、周期的リフレッシュメッセージと、専用照会／応答メッセージと、前記発信元ノードと前記宛先ノードとの間で交換されるキープアライブ・シグナリングメッセージとの内の１つ以上を監視する処理を含むことを特徴とする請求項２８に記載の方法。
【請求項３０】
ネットワークドメインの内部ルータを制御する方法であって、
前記ネットワークドメインは、複数のフローに属するデータユニットを受信し、該データユニットを前記ネットワークドメイン内にルーティングする少なくとも１つの発信元ノードと、前記ネットワークドメインを介して前記データユニットをルーティングする複数の内部ルータと、前記データユニットを前記ネットワークドメインの外にルーティングする少なくとも１つの宛先ノードとを有しており、
前記内部ルータの負荷が第１の負荷閾値または前記第１の負荷閾値より高い第２の負荷閾値を超えるかどうかを検出する工程と、
トラフィック負荷が前記第１の負荷閾値を超えるなら、第１のマーカを含む輻輳マーク付きデータユニットを生成し、前記トラフィック負荷が前記第２の負荷閾値を超えるなら、第２のマーカを含む輻輳マーク付きデータユニットを生成する工程とを有することを特徴とする方法。
【請求項３１】
プログラマブルなネットワークノードで請求項１６乃至３０のいずれか１項に記載の方法を実行するように構成されたプログラムコード部を有することを特徴とするプログラム。
【請求項３２】
請求項３１に記載のプログラムを格納する記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は１つ以上の発信元ノードと複数の内部ルータと１つ以上の宛先ノードとを有するネットワークドメインのエッジノード、そのようなネットワークドメインの内部ルータ、及び、エッジノートと内部ルータの通信制御方法に関するものである。
【背景技術】
【０００２】
通信分野では、パケット交換トランスポートが広く使用されている。最近は、ＩＰベースのトランスポート・ソリューションがより多くの注目を集めている。ＩＰはインターネットプロトコルを意味する。ＩＰへの関心は、少なくとも一部はＩＰ技術の柔軟性と広い展開に起因している。しかし、電話網などの通信ネットワークは、従来のＩＰネットワークと比較して異なる特性を有する。なぜなら、通信ネットワークでは、簡単、安価に、かつ規定されたサービス品質（ＱｏＳ）を提供できることが通常望まれるからである。サービス品質要件のために、トラフィック輻輳制御が、通信ネットワークでは重要である。
【０００３】
ＩＰネットワークでＱｏＳを提供する概念の１つは、シグナリングによるデータパスに沿ったルータでのリソースの予約である。一例として、標準化団体であるインターネット技術標準化委員会（ＩＥＴＦ）は、ＩＰルータでリソースを予約し、インターネットにおいてリアルタイムトラフィックと非リアルタイムトラフィックでの統合化サービスを提供するために、ＲＳＶＰ（ネットワーク資源予約プロトコル）と呼ばれるシグナリングプロトコルの仕様を定めている（非特許文献１、２、３参照）。この技術では、リアルタイムトラフィックフローを送信する前に、ＲＳＶＰシグナリングメッセージで、データパスに沿った各ルータでリソースを予約する。リソースがデータパスに沿った各ルータで首尾よく予約された場合、リアルタイムフローがネットワークに入るのを許可される。
【０００４】
この方法は、データパスに沿った各ルータの中にフロー毎に予約状態を格納する必要がある。予約状態はソフト状態であり、これは、周期的にリフレッシュメッセージを送信することによってリフレッシュしなければならないことを意味する。予約状態がリフレッシュされない場合、その予約状態とそれに対応するリソースは、タイムアウト時間後解除される。予約は、明示的なティアダウンメッセージによっても解除されてもよい。フロー毎の状態の助けを借りて、ＲＳＶＰメッセージは常に、データパスに沿ってアップストリームおよびダウンストリームに続く。それゆえ、標準ルーティングプロトコルと相互に作用することができる。トラフィックが、例えば、ルータの過負荷のためにルート変更される場合には、リフレッシュメッセージが新しいデータパスでの予約を行なう。各ルータにフロー毎の状態を格納することにより、ローカルパスの修復実行可能性を与えている。ルート変更後、新しいパスに望まれるすべてのフローをサポートするのに十分なリソースがない場合、フローの一部は終了されることがある。
【０００５】
各ルータにおいてフロー毎の状態を格納および保持すると、大規模ネットワークでは問題になる。その場合、フローの数それゆえ予約状態の数が多くなることがある。ＲＳＶＰのこの拡張性の問題に応えて、ＩＥＴＦは、集まったフローに対する予約を可能にするＲＳＶＰ集約方法の仕様を定めている（非特許文献４参照）。各フロー要求に対して、集約予約状態は必ずしも作成されたり、変更されたり、リフレッシュもされる必要はない。
【０００６】
ＲＳＶＰ集約方法は、集まったレベルだけでアドミッション制御の判定をする能力があり、これは、再ルーティング後、新しいパスに十分なリソースがない場合、集合として一緒に取り扱われる全フローが終了されることを意味する。
【０００７】
大規模ネットワークでＱｏＳを提供する手段として、ＤｉｆｆＳｅｒｖ（Differentiated Services）と呼ばれるアーキテクチャが提案された（非特許文献５参照）。ＤｉｆｆＳｅｒｖアーキテクチャにおいては、フロー毎のベースでなく集合体にサービスを提供し、ネットワークのエッジノードにフロー毎の状態情報ができるだけ多く保持されるようにシステムを構成し、集約状態情報のみを内部ノードに保持することによって、拡張性を達成する。サービスの差別化は、いわゆるＤＳ（Differentiated Services）フィールドと呼ばれるＩＰヘッダの中の特定のフィールドを用いて達成する。パケットは、ＤｉｆｆＳｅｒｖエッジノードでホップごとの振る舞い（ＰＨＢ、Per-Hop Behaviour）グループに分類される。パケットは、メッセージヘッダのＤＳフィールドに示されたＰＨＢに従って、ＤｉｆｆＳｅｒｖルータで処理される。ＤｉｆｆＳｅｒｖアーキテクチャは、ドメイン外のデバイスが動的にリソース予約をしたり、またはネットワークリソースの利用可能性の示唆を受信することに関して、どのようにも仕様を定めていない。実際のところ、サービスプロバイダは、顧客から受け入れるトラフィックのパラメータを静的に定める申し込み時サービスレベルアグリーメント（ＳＬＡ）を頼りにしている。
【０００８】
ＤｉｆｆＳｅｒｖネットワークは、拡張可能なやり方でリアルタイムトラフィックに対してＱｏＳを提供する。ＤｉｆｆＳｅｒｖは、トラフィックがドメインエッジで制限される静的アーキテクチャであり、内部ノードは適正な規模で設計されなければならない。ドメイン内の再ルーティングによる過負荷に対処する動的メカニズムがないので、少なくとも一定レベルまでのＱｏＳ保証を提供するために、平均負荷に対して内部ノードとリンクの規模を過大にする必要がある。
【０００９】
ＩＥＴＦのＮＳＩＳ（Next Steps In Signalling）ワーキンググループは、ＩＰネットワークの新しいシグナリング要件に対処するプロトコルに取り組んでいる（非特許文献６参照）。ＮＳＩＳのＱｏＳシグナリング・アプリケーション・プロトコルはＲＳＶＰに似ているが、異なるＱｏＳモデルのサポートなどのいくつかの付加的な特徴を有している。ＱｏＳモデルの１つは、ＲＭＤ（Resource Management in DiffServ）である。ＲＭＤは、ＤｉｆｆＳｅｒｖネットワークに対する拡張性のあるアドミッション制御方法を定めている。ＲＭＤは、輻輳状況では相当数のフローを終了させ、残りのフローに対して所要のＱｏＳを維持できるようにする輻輳制御機能も含んでいる。
【００１０】
ＡＴＭまたはＳＤＨなどの通信で使用される他の技術と比べた、ＩＰネットワークおよび他の一部のパケット交換ネットワークの重要な特徴は、ＩＰルーティングプロトコルがトポロジの変化に自動的に適応することであり、例えば、リンクまたはノードが故障した場合、トラフィックを自動的に再ルーティングする。しかしながら、例えば、帯域幅の不足のせいで、新しいパスが再ルーティングされたフローのすべてをサポートすることができないことがあるので、問題が起こることがある。そのような状況では、輻輳管理が望まれる。
【００１１】
ＲＭＤは、ＤｉｆｆＳｅｒｖドメインのエッジノードに、内部ルータで発生している輻輳について通知する機能を規定している。この通知は、過負荷に比例した、内部ルータにおけるＤＳフィールド内のデータパケットの“再マーキング（remarking）”に基づいている。次いで、エッジノートでマークの付いたパケットの数を測定し、トラフィック負荷を減らす必要がある場合、一部のフローに対する終了メッセージを送信することができる。
【００１２】
輻輳に対応するアルゴリズムは、例えば非特許文献７および８に記載されている。
【００１３】
そのようなアルゴリズムで遭遇する問題は、輻輳を軽減するために必要以上にフローを終了させることによって、輻輳状態に過剰反応する傾向があることである。これは、過剰反応のせいで実際の負荷が所望のレベル以下に落ちるのでアンダーシュートとも呼ばれる。
【００１４】
特許文献１は、過剰反応の問題への対処法を記載している。記載されているシステムでは、ドメインの内部ルータが過負荷に比例してパケットにマークを付けてから、シグナリングされた過負荷を格納する。言い換えると、内部ルータまたは内部ノードは、測定した過負荷に関する“メモリ”形態を有する。次いでこの記憶された情報は、その後に新しいパケットにマークを付けるときに考慮される。さらに、内部ルータは、過負荷の程度に比例して転送するデータユニットにマークを付け、宛先ノードは、過負荷の程度を測定するためにマーク付きのデータユニットを数える。
【先行技術文献】
【特許文献】
【００１５】
【特許文献１】国際公開第２００６／０５２１７４号パンフレット
【非特許文献】
【００１６】
【非特許文献１】Ｒ．ブラーデン他（R. Braden et al.）、「リソース予約プロトコル（ＲＳＶＰ）バージョン１“機能仕様”（Resource Reservation Protocol（ＲＳＶＰ） - version 1 "Functional Specification"）」、ＲＦＣ２２０５、１９９７年９月
【非特許文献２】Ｒ．ブラーデン他（R. Braden et al.）、「インターネットアーキテクチャにおける統合サービス：概要（Integrated Services in the Internet Architecture: an Overview）」、ＲＦＣ１６３３、１９９４年
【非特許文献３】Ｊ．ロクラウスキ（J. Roclawski）、ＩＥＴＦ統合サービスでのＲＳＶＰの使用（The Use of RSVP with IETF Integrated Services）、ＲＦＣ２２１０、１９９７年９月
【非特許文献４】ＲＦＣ３１７５、２００１年９月
【非特許文献５】ＲＦＣ２４７５、１９９８年
【非特許文献６】ＲＦＣ３７２６、２００４年４月
【非特許文献７】アンドラス  シサスザール（Andras Csaszar）、アッチラ  タカクス（Attila Takacs）、ロバート  スザボ（Robert Szabo）、ブロラ  レクセピ（Vlora Rexhepi）、ゲオルギオス  カラギアニス（Georgios Karagiannis）、「オンデマンドＲＭＤによる深刻な輻輳の処理（Severe Congestion Handling with Resource Management DiffServ on Demand）」、ネットワーキング２００２予稿集−第２回国際ＩＦＩＰ−ＴＣ６ネットワーキング会議、ＩＮＣＳ第２３４５巻、４４３−４５４頁、２００２年、イタリア  ピサ
【非特許文献８】ラルス  ウェストベルグ（Lars Westberg）、アンドラス  シサスザール（Andras Csaszar）、ゲオルギオス  カラギアニス（Georgios Karagiannis）、アダム  マルクエッタント（Adam Marquetant）、デヴィッド  パルテイン（David Partain）、オクタビアン  ポップ（Octavian Pop）、ブロラ  レクセピ（Vlora Rexhepi）、ロバート  スザボ（Robert Szabo）、アッチラ  タカクス（Attila Takacs）、「ＲＭＤ（Resource Management in DiffServ）：機能および性能挙動概要（Resource Management in DiffServ (RMD): A Functionality and Performance Behavior Overview）」、ＰｆＨＳＮ２００２予稿集−第７回高速ネットワーク用プロトコルの国際ワークショップ、ＩＮＣＳ第２３３４巻、１７−３４頁、２００２年、ドイツ  ベルリン
【発明の概要】
【発明が解決しようとする課題】
【００１７】
本発明の目的は、１つ以上の発信元ノードと、複数の内部ルータと、１つ以上の宛先ノードを備えるネットワークドメインにおける、特に内部ルータを単純化するという観点から改良した輻輳対応方法を提供することである。好ましくは、アンダーシュートを引き起こさない、即ち、必要以上にフローを終了させずに、良好な輻輳対応処理を実現することも目的とする。
【課題を解決するための手段】
【００１８】
独立請求項の主題はその目的に解決策を与えている。有利な実施例は、従属請求項に記載されている。
【００１９】
本発明の基本的な実施例によれば、エッジノードがネットワークドメインに設けられる。そのネットワークドメインは、そのネットワークドメインに入ってくる複数のフローに属するデータユニットを受信し、それをルーティングする発信元ノードと、ネットワークドメインを介してそのデータユニットをルーティングする複数の内部ルータと、データユニットをそのネットワークドメインの外にルーティングする少なくとも１つの宛先ノードとを備える。複数の内部ルータの中の少なくとも１つは、輻輳状態になっているかどうかを検出し、輻輳状態になっているなら、ルーティングされるデータユニットに輻輳マークを付けるように構成される。なお、内部ルータのすべてがこの機能を有する必要があるわけではないが、各内部ルータがこのように動作できることは好ましいことである。ルーティングされるデータユニットへの輻輳マーク付けは、例えば、ルーティングされるデータユニットのヘッダの所定のフィールドに特定の値を設定することなどによって達成される。本発明のエッジノードは、宛先ノードとして動作するように構成され、輻輳マーク付きデータユニットの存在を検出する部分と、輻輳制御処理を起動することにより輻輳マーク付きデータユニットの存在の検出に対応する部分とを備える輻輳処理機能を実行する制御要素を備える。その輻輳制御処理は、発信元ノードに１つ以上のフローを終了させる命令を送信してトラフィック負荷を減少させ、所定の時間待ち、次いで輻輳マーク付きデータユニットがエッジノードに依然として到着しているかどうかを判定し、輻輳マーク付きデータユニットが依然として到着しているなら、送信と待機を繰り返す処理を含む。
【００２０】
トラフィック負荷を減らすためにおそらく更なる命令を送信する前に所定の時間を待ち合わせることによって、そのような命令が送信されてから命令が実際に実行され効果を生じるまでの遅延を考慮に入れることができる。言い換えると、上記の概念は、宛先ノードによる負荷低減命令の送信からその命令への反応を宛先ノードが測定できる時点までに一定の遅延があることを認識している。その遅延には、命令が発信元ノードに到達するまでに要する時間と、発信元ノードが命令に従うまでに要する時間と、命令に従った後に発信元ノードからドメインに注入されたデータユニットが再び宛先ノードに到達するまでに要する時間とを含む。遅延期間内に更なる低減命令を送信しないことで、輻輳マーク付きデータユニットの受信に対する過剰反応に起因するアンダーシュートを非常に簡単なやり方で避けることができる。即ち、ドメインの内部ルータを特に適合させる必要がない、つまり内部ルータを簡単なままに保つことができる。
【００２１】
好ましい実施例に従えば、１つ以上の内部ルータが、負荷が第１の負荷閾値または第１の負荷閾値より高い第２の負荷閾値を超えるかどうかを検出し、トラフィック負荷が第１の負荷閾値を超えるなら第１のマーカを含む輻輳マーク付きデータユニットを生成し、そのトラフィック負荷が第２の負荷閾値を超えるなら、第１のマーカとは異なる第２のマーカを含む輻輳マーク付きデータユニットを生成できるように構成される。一方、宛先ノードは、その輻輳制御処理が、受信データユニット内の第１のマーカの検出に応えて、負荷低減パラメータを第１の負荷低減値に設定し、受信データユニット内の第２のマーカの検出に応えて、第２の負荷低減値に設定するように構成されてもよい。ここで、第２の負荷低減値は第１の負荷低減値より大きな負荷低減に対応する。
【００２２】
この概念の利点は効果的な輻輳制御を非常に簡単な手段で達成できる点にある。即ち、内部ルータは、到来するトラフィックに対して２つの異なる負荷閾値を区別し、それに応じてルーティングされるデータユニットにマークを付けることができる必要があるだけである。過負荷または輻輳に比例してデータユニットにマークを付ける必要はなく、例えば、マーク付けを段階的やり方で行うことが可能なので、即ち、一度各閾値を超えると、それ以降ルーティングされる全てのデータユニットは、それに応じてマークを付けられる。このように、内部ルータを簡単なやり方で実現することができる。もちろん、それでもなお、この概念を比例的なマーク付けの概念と組み合わせることは可能である。即ち、一度所与の閾値を超えると、内部ノードが、過負荷または輻輳の程度に比例して、転送データユニットの一部だけにマークを付けることも可能である。
【００２３】
いずれにしても、２つの異なる負荷閾値を設け、それに応じて大幅または小幅の負荷低減を命じるように宛先ノードを構成することによって、内部ルータや宛先ノードに複雑なメカニズムを何ら実装する必要なしに、効果的な輻輳応答が提供できる。例えば、内部ルータで比例的なマーク付けを実行する必要がないし、次いでそのような比例的なマーク付けされたデータユニットに基づいて、宛先ノードで輻輳の程度の測定を実行する必要もない。
【００２４】
なお、２つの閾値と２つの対応する負荷低減値を設けることは、単なる一例であり、この概念をより多くの数の閾値やそれに応じたより多くの数の関連する負荷低減値にももちろん適用できる。例えば、今述べた２つの閾値に加えて、第２の閾値より大きな負荷を表す第３の閾値を設けることができ、それに応じて、宛先ノードは、第２の負荷低減値より大幅な負荷減少に対応する第３の負荷低減値に対応する負荷低減命令を送信することによって、第３の閾値を表す第３のマーカに応答するように構成できる。
【図面の簡単な説明】
【００２５】
【図１】発信元ノード、宛先ノード、及び複数の内部ルータを備えるネットワークドメインの概要を示す図である。
【図２】本発明の実施例に従うエッジノードの概要を示すブロック図である。
【図３】本発明の基本的方法の実施例を示すフローチャートである。
【図４】本願のエッジノードの別の実施例の概要を示すブロック図である。
【図５】本発明の別の方法の実施例のフローチャートである。
【図６】本発明のまた別の方法の実施例のフローチャートである。
【図７】本発明の実施例に従う内部ルータの実施例の概要を示すブロック図である。
【図８】内部ルータを制御する方法の実施例のフローチャートである。
【発明を実施するための形態】
【００２６】
以下、添付図面を参照して本発明の特定の実施例について説明する。
【００２７】
その実施例は、請求の範囲にその概要が示される全体的な発明の概念の例として見られることだけを意図しており、これらの発明の概念の開示を限定する効果を持つものではない。その実施例は、当業者によりよい理解を提供する役目を果たすだけである。
【００２８】
図１はネットワークドメイン１０の概要を示し、ネットワークドメイン１０はそれに入ってくる複数のフローに属するデータユニットを受信してルーティングする発信元ノード１１を備える。ネットワークドメイン１０はさらに、ネットワークドメイン１０を介してデータユニットをルーティングする複数の内部ルータ１３、１４、１５と、ネットワークドメイン１０外にデータユニットをルーティングする宛先ノード１２とを備える。
【００２９】
本願の明細書と請求の範囲において、用語“ネットワークドメイン”は、今説明した構成、即ち、１つ以上の発信元ノードと、複数の内部ルータと、１つ以上の宛先ノードとを有する何らかのノード構成を表現するために総称的に使用される。このような状況から、ネットワークドメインは、自ネットワークでルータを有し、発信元ノードと宛先ノードは他のネットワークに対する適切なゲートウェイサーバにより提供されるネットワークでもよいし、あるいは、ネットワークドメインはより大きなネットワークのサブディビジョンでもよい。また、様々なプロトコルおよび様々な技術との関連で、ネットワークにより送信されるデータのサブディビジョンは、パケット、セル、セグメント、プロトコルデータユニット等のような様々な名前を有することがあり、本願明細書と請求の範囲で使用する用語「データユニット」は総称であり、より大きなデータ量のこのようなサブディビジョンのいずれにもかかわるものである。
【００３０】
図１の例では、リンク故障１９が内部ルータ１４と１５の間で発生し、内部ルータ１４を通過していた発信元ノード１１から宛先ノード１２への全トラフィックは、内部ルータ１３と１５によりパス１６、１７、１８経由で再ルーティングされなければならないと仮定している。この再ルーティングの結果として、過負荷または輻輳状態が内部ルータ１３で発生することがあろう。
【００３１】
図１の実施例では、１つ以上の内部ルータが、自装置が輻輳状態になっているかどうかを検出し、輻輳状態が検出された場合、それに応じて自装置がルーティングするデータユニットに輻輳マークを付けるように構成されていると仮定している。輻輳状態は、何らかの適切なまたは所望のやり方で定義されてもよく、同様に、輻輳マーク付けも、何らかの適切なまたは所望のやり方で行われてもよい。例えば、輻輳状態は、待ち行列に入れる前の着信トラフィックのデータレートを測定する一方、この値を閾値と比較することにより決定してもよい。同様に、輻輳状態は、バッファの待ち行列の長さを測定し、この値を対応する閾値と比較することにより規定してもよい。夫々の場合において、閾値を超える場合には、輻輳状態が存在すると判定される。ルーティングされるデータユニットへの輻輳を表すマーク付けは、例えば、ルーティングされるデータユニットのヘッダに適切な情報を設定することによってなされる。一例として、ＩＰデータユニットを使用するとき、ＩＰヘッダの中のＤｉｆｆＳｅｒｖコードポイント（ＤＳＣＰ、DiffServ Code Point）または明示的輻輳通知（ＥＣＮ：Explicit Congestion Notification）フィールドを、輻輳を表わすために適切に設定してもよい。
【００３２】
データユニットの輻輳マーク付け手順は、何らかの適切なまたは所望のやり方で行われてもよく、例えば、過負荷に比例して行われてもよいし、段階的やり方で行われてもよい。比例的なマーク付けは、過負荷の程度を測定し、その程度に従って転送データユニットの一部だけにマークを付けることを意味する。段階的マーク付けは、一度閾値を超えると、全ての転送データユニットにマークを付けることを意味する。第３の選択肢は、内部ノードが閾値を超えるパケットにマークを付けることでもよい。
【００３３】
図２は、本発明の実施例に従うエッジノードの概要例のブロック図を示す。エッジノード１２は、宛先ノードとして動作するように構成されており、図１に示されている。エッジノード１２は、ネットワークドメイン１０からデータユニット１２４を受信する入力バッファ１２１と、ネットワークドメイン１０の外に転送されるデータユニットを保持する出力バッファ１２２とを備える。エッジノード１２はさらに制御要素１２３を備え、制御要素１２３は、エッジノード１２に到着する輻輳マーク付きデータユニットの存在を検出する部分と、輻輳制御処理を起動することにより輻輳マーク付きデータユニットの存在の検出に対応する部分とを有する輻輳処理機能を実行するように構成されている。輻輳制御処理は、発信元ノード１１に１つ以上のフローを終了させる命令１２５を送信してトラフィック負荷を減少させる処理と、所定の時間Ｔrelax待ち合わせ、次いで輻輳マーク付きデータユニットが依然としてエッジノード１２に到着しているかどうかを判定する処理とを有する。輻輳マーク付きデータユニットが依然として到着しているなら、命令１２５を送信し、時間Ｔrelax待ち合わせるステップが繰り返される。
【００３４】
この手順は図３に示されており、ステップＳ３１で輻輳マーク付きデータユニットが到着しているかどうかを判定し、到着している場合、ステップＳ３２とＳ３３が実行されて、負荷低減命令を発信元ノードに送信し、次いで時間Ｔrelax待ち合わせる。その後、ステップＳ３１では、輻輳マーク付きデータユニットが到着しているかどうかを再び判定し、到着している場合、ステップＳ３２とＳ３３が繰り返される。到着していない場合、手順は、輻輳マーク付きデータユニットが到着しているかどうかを判定し続けるため、基本的にループして元に戻るが、ステップＳ３４では、例えば、外部割込みによって手順を終了する可能性も示している。
【００３５】
なお、図２に示されている制御要素１２３は、何らかの適切なまたは所望のやり方で提供されてもよい。例えば、それは、ネットワークノード用の周知の種類のマイクロプロセッサでもよく、そのプロセッサは、本発明の新規な概念を実施するようにプログラムされる。このような状況から、本発明は、プログラマブル・ネットワーク・ノードで実行されるとき、本発明の方法を実行するように構成されたプログラムコード部を備えるコンピュータプログラムとしても実施されてもよい。さらに、本発明は、本発明の方法を実施するように構成されているコンピュータプログラムを備えた、データキャリアなどのコンピュータプログラム製品として実施されてもよい。
【００３６】
他方、制御要素１２３は、輻輳処理機能を実現する専用ハードウェア要素から構成されてもよいし、ハードウェアとソフトウェアの適切な組み合わせも備えてもよい。
【００３７】
またなお、図２に示されているエッジノード１２は、本発明の説明に関連する機能だけを表しており、簡潔にするためにネットワークノードの他の周知の要素を示していない。
【００３８】
宛先ノードから発信元ノードに送信されるノードの低減命令は、何らかの適切なまたは所望のやり方で構成されてもよい。その命令は、例えば、宛先ノードと発信元ノードとの間を専用のシグナリングメッセージによって送信されてもよく、そのようなシグナリングメッセージは、ＩＰなどのたぶん同じプロトコルを用いて、データユニットと同じパスにより送信されてもよいし、あるいはまた、そのようなシグナリングメッセージは、専用シグナリングパスによるか、または、専用シグナリングプロトコルを用いるかの内、少なくともいずれかにより送信されてもよい。
【００３９】
命令情報自体は、適切なまたは望ましいように、種々のやり方で選択されてもよい。例えば、２つの値の内の１つの値を取ることができる簡単なバイナリ信号でもよく、その場合には、１つの値が“低減”を表わし、別の値が“低減なし”を表わす。発信元ノードが低減を表わす信号を受信すると、所定の値だけ、例えば、減少がプリセットされたデータレートに対応する量だけ、トラフィックを低減させ、次いで発信元ノードは、所望の負荷低減を達成するために処理している全フローの中から選択を行なう。その選択動作は、何らかの適切なまたは所望のやり方、例えば、フローのランダム選択などによって、多くのフローを終了し所望の低減を達成するまで行われてもよい。
【００４０】
本願明細書と請求の範囲の文脈では、用語“フロー”は、特定の送信元識別子および宛先識別子、例えば、送信元アドレスおよび送信先アドレスによって特定されるデータユニットに関するものとして包括的には理解される。送信元識別子および宛先識別子は、ポート番号などのさらなる要素も有してもよい。その結果として、リアルタイムデータフローまたはＴＣＰデータフローは、本願の中で言及する一般的なフローの一例である。
【００４１】
上記のように、宛先ノードから発信元ノードに送信される命令は、例えば、１ビットだけで符号化される簡単なバイナリ情報でもよい。しかし、命令がより多くの情報を備えることは好ましい。好適な実施例によれば、制御要素１２３は、輻輳制御処理は輻輳マーク付きデータユニットの検出に応じて負荷低減パラメータの値の設定する処理をさらに備えるように構成され、そして、その命令は、発信元ノードに負荷低減パラメータの値に従って１つ以上のフローを終了させるように命令するようにするのである。言い換えると、負荷低減パラメータは、負荷をどのくらい減らすべきかをより正確に区別する。これは種々のやり方で行うことができる。例えば、負荷低減パラメータは、異なる負荷低減の程度を表わす事前構成の調節係数を用いて表わすことができる。例えば、低減値に段階を付けることができ、その場合、第１の値が小幅の所定の調節Ａに相当し、第２の値がより大幅の調節２×Ａに相当し、第３の値がさらに大幅の調節３×Ａに相当し、その命令は第１、第２または第３の値を夫々含み、発信元ノードは、それに応じて適切な数のフローを終了させることによって負荷を低減するように構成される。
【００４２】
より好ましくは、制御要素および輻輳制御処理は、負荷低減パラメータが絶対負荷または相対負荷によって表わされるように構成される。言い換えると、負荷は、例えば、データレートなどの絶対値で測定されてもよく、命令は、それに応じて絶対負荷によって、例えば、絶対データレート値による低減情報を含むことができる。また負荷は、相対表現で、例えば、総負荷に対する百分率として表されてもよい。一例として、相対負荷は、多数のフローが原因となる負荷に対する割合として表されてもよい。この場合、発信元ノードは、総負荷（例えば、フローによって提供された合計データレート）を表示された割合だけ減少させるまで、その数の中からフローを終了させることができる。
【００４３】
好適な実施例によれば、宛先ノードの制御要素と輻輳制御処理はさらに、どのフローが影響を受けているかを検出するフロー検出ルーチンが備えられ、発信元ノードへの命令が負荷低減パラメータの値に従って、フロー中の１つ以上のどのフローが終了されることになるのかのフローの表示を備えるようにされる。言い換えると、例えば、図３の例を見ると、ステップＳ３１とＳ３２との間に、輻輳によって影響を受けるフローの検出を行なうことを含む更なるステップがあることが好ましい。この意味することは、輻輳マーク付きデータユニットを検出した後、宛先ノードの制御要素と輻輳制御処理が、どのフローが輻輳マークを含んでいるか、即ち、どのフローが輻輳を示すマーキングを搬送しているかを識別することである。フローは、その送信元の表示と送信先表示によって識別される。例えば、この検出ルーチンは、一定期間内に受信したデータユニットを検査することと、輻輳マーキングを搬送するデータユニットすべてのフロー識別子の記録することを含むと良い。このようにして決定されたフロー識別子は、次いで命令と一緒に発信元ノードに送信され、発信元ノードが表示されたグループの中のフローを終了できるようにする。どのフローを終了すべきかに関する決定は、発信元ノードまたは宛先ノードで行われてもよい。その決定が発信元ノードで行われる場合、輻輳によって影響を受けたフローの識別子より多くの情報を与える必要はない。しかし、別の実施例によれば、宛先ノードの制御要素と輻輳制御処理がどのフローを終了させるべきか選択するフロー選択ルーチンも備え、その場合、発信元ノードへの命令が選択されたフローの表示を備えるように宛先ノードが構成される。この実施例の利点は、選択プロセスが宛先ノードで実行されるので、発信元ノードの制御手順を簡単に保ち続けられることである。
【００４４】
既に先に詳述したように、どのフローを終了すべきかに関する選択プロセスは、何らかの適切なまたは所望のやり方で行ってもよい。例えば、影響を受けたフローをランダムに選択し、そのフローの負荷を（例えばデータレートの点から）測定し、選択したフローを終了させるときの負荷低減を判断し、次いでその終了が負荷低減パラメータの設定値によって望まれている減少につながるかどうかを判断する処理でもよい。所望の負荷減少が達成されない場合、多くのフローの終了を考慮して所望の負荷減少を達成するまで、ランダム選択とこれに続く判断の処理が繰り返される。このようにして選択されたフローは、次いで実際の終了のために発信元ノードに通知される。
【００４５】
当然ながら、他の形態のフローの選択も可能であり、例えば、フローの個々の負荷を測定し、フローを負荷に従って最大負荷から最小負荷まで分類することが可能である。この場合、その選択処理は、最大負荷を有するフローの選択から始まり、そのフローの終了の負荷減少に対する効果を調べ、所望の負荷減少が達成されるまで、最大負荷から最小負荷に向けてフローを選択する。この選択手順の利点は、所望の負荷減少を達成するのに、結果的に、終了させられるフローをできる限り最小限にする点にある。
【００４６】
終了すべきフローを選択する別の基準は、フローのタイプに基づいてもよい。言い換えると、その選択処理では、フロータイプ識別子（例えば、リアルタイムフロー、非リアルタイムフロー）をさらに考慮し、フロータイプに依存した選択処理を行なうことができる。例えば、その選択処理は、非リアルタイムフローだけを終了させることにより始めてもよい。フロータイプに基づく選択は、上記のランダム選択または負荷への寄与に基づく選択とも組み合わされてもよい。
【００４７】
なお、フロー識別情報は、発信元ノードにどの命令が処理されるべきかを知らせる手段としても使用されてもよい。これについては、以下でより詳細に説明する。簡単な状況では、ネットワークドメインは１つだけ発信元ノードを有する。この場合、１つ以上の宛先ノードはそれぞれ、負荷低減命令をその発信元ノードに送信する。これに対して、ネットワークドメインが複数の発信元ノードを備える場合、命令を送信する複数の宛先ノードとその命令を受信する発信元ノードとの間で信頼できる通信を確保する様々な可能性がある。１つの可能性は、ネットワークドメインを流れるデータユニットがそのデータユニットをネットワークドメインへと注入した発信元ノードの表示を備えることである。この場合、輻輳マーク付きデータユニットを受信する宛先ノードは、そのデータユニットがどのフローに属するかを識別できるだけでなく、それがどの発信元ノードから来たのかも識別できる。それに応じて、その情報に基づいて、負荷低減命令が適切な発信元ノードに送信される。代替形態として、データユニットが発信元ノードを識別する表示を持たないシステム、またはそのような情報が使用されていない場合は、各宛先ノードは、複数のフローの中のどの１つ以上のフローが終了させられることになるのかの少なくともフローの表示、または終了させられる特定のフローの表示とともにその命令を、全ての発信元ノードに送信してもよい。この場合、各発信元ノードは、自装置が命令の正しい受信者かどうかを判定するために、識別されたフローと自装置が処理しているフローを比較してもよい。正しい受信者である場合、適切なフローを終了させ、正しい受信者でない場合、単にその命令を無視する。
【００４８】
負荷低減パラメータの値の設定に関しては、原理的には何らかの適切なまたは所望のやり方で行われるとよい。例えば、前述のやり方で、輻輳閾値を超えるとネットワークドメインの内部ルータが比例的にデータユニットにマークを付けるように構成されているなら、宛先ノードの制御要素と輻輳処理機能が、各影響を受けたフローのマーク付きおよびマーク無しのデータユニット数を数え、それによってマーク付きとマーク無しのデータユニットとの間の関係に基づく過負荷の程度の表示を受信し、輻輳または過負荷の程度を判定するように構成されてもよい。この場合、負荷低減パラメータの値は、それに応じて、例えば、負荷または輻輳の測定された程度に比例して、設定されてもよい。本願の導入部で詳述したように、内部ルータが過負荷の程度に比例してデータユニットにマークを付けるようにネットワークドメインの内部ルータを構成する概念は、先行技術から周知であり、ここでの更なる説明は必要ない。
【００４９】
本発明の好適な実施例によれば、内部ルータそれに加えて過負荷状況を検出するように構成された宛先ノードの制御手順を単純化することができるために、次の新しい概念が開示される。内部ノードを例えば図７の例に示すように、図８を参照して説明する制御手順を持つように構成してもよい。
【００５０】
図７は内部ルータを示し、この内部ルータは、ルーティングされるデータユニット７２０を受信する入力バッファ７１０と、転送されるデータユニット７２１を出力する出力バッファ７１１と、データユニットの受信と転送の動作を制御する制御要素７１２とを備える。図２の例と同様に、そのようなルータのこれら以外の周知の要素は、説明を簡潔にするために示されていない。
【００５１】
制御要素７１２は、内部ルータの負荷が第１の負荷閾値ｔｈ１または第２の負荷閾値ｔｈ２を超えるかどうかを検出するように構成された部分７１２１を備えている。ここで、第２の負荷閾値ｔｈ２は第１の負荷閾値ｔｈ１より大きい。その負荷は、例えば、待ち行列に入れる前に、到着するデータユニット７２０のデータレートに関して測定されてもよい。その閾値は、従って、絶対表現、即ち、負荷値として、または、相対表現、例えば、所定の負荷値に対する割合として表されてもよい。図７の内部ルータはさらに、制御要素７１２内に、トラフィック負荷が第１の負荷閾値ｔｈ１を超える場合、第１のマーカＬ１を備える輻輳マーク付きデータユニットを生成し、そのトラフィック負荷が第２の負荷閾値ｔｈ２を超える場合、第１のマーカと異なる第２のマーカＬ２を備える輻輳マーク付きデータユニットを生成する部分７１２２を備える。図７の例では、第１の負荷閾値ｔｈ１を超えるが第２の負荷閾値ｔｈ２を超えないと仮定しているので、出力データユニット７２１にＬ１のマークが付いている。
【００５２】
制御プロセスの一例が図８に示されている。第１のステップＳ８１では、負荷が第２の閾値ｔｈ２を超えるかどうかを判定する。もし超えるなら、ステップＳ８２を見ると、出力データユニットにＬ２のマークが付けられ、処理はループして始めに戻る。もし負荷ｔｈ２を超えないなら、手順はステップＳ８３に進み、そこで閾値ｔｈ１を超えるかどうかを判断する。もし超えている場合には、ステップＳ８４を見ると、出力データユニットにＬ１のマークが付けられ、その手順はループして始めに戻る。ｔｈ１も超えない場合、ステップＳ８５で手順を終了すべきかどうか、例えば、外部割込みに基づき判定し、手順が続く場合、処理はループして始めに戻る。
【００５３】
なお、図８の制御方法は、データユニットのマーク付けが段階的やり方で行われる、即ち、一度、所与の閾値を超えると、出力データユニットのすべてがそれに応じてマークを付けられるので、都合よく簡単である。この例では比例的なマーク付けはない。図８の制御方法は、図７に示されている内部ルータの制御法の一例である。しかし、図７の内部ルータは、比例的なマーク付けを含むやり方でも動作してもよいことに留意されたい。例えば、要素７１２１は、閾値ｔｈ１或はｔｈ２を超えるかどうかを判定するだけでなく、閾値を超える程度も同時に測定し、要素７１２２が、それぞれの閾値を超える程度に対応した割合で出力データユニットにマークを付けてもよい。
【００５４】
両方の場合に、宛先ノードとして動作するエッジノードは、次のように構成されるのが好ましい。宛先ノードは、輻輳制御処理が第１のマーカＬ１の検出に応じて、負荷低減パラメータを第１の負荷減少値ＬＲ1に設定する処理と、第２のマーカＬ２の検出に応じて、第２の負荷減少値ＬＲ2に設定する処理とを備えるように構成されてもよい。第２の負荷減少値ＬＲ2は、第１の負荷減少値ＬＲ1より大幅の負荷減少に相当する。
【００５５】
この概念の一例が図５の方法の実施例に示されている。第１のステップＳ５００では、輻輳マーク付きデータユニットが存在するかどうかを判定する。もし存在しないなら、システムは、ステップ５１０経由でループして始めに戻るが、ステップ５１０で、例えば、外部割込みに基づいて、手順を終了すべきかどうかを判定する。輻輳マーク付きデータユニットが存在するなら、ステップＳ５０１でマーキングがＬ１のマーキングかどうかを判定する。そうであるなら、手順はステップ５０６に進み、そこで負荷低減パラメータを第１の値ＬＲ1に設定する。次いで、ＬＲ1に従って負荷減少を達成するために、ステップ５０７で、手順は影響を受けたフロー（即ち、どのフローがＬ１マーキングを搬送するか）を識別し、どのフローを終了させるかを選択する。さらに、対応する命令が次いで発信元ノードに送信される。その後、期間ＴrelaxがステップＳ５０８で設定され、その間、待ち合わせが行われる。即ち、それ以上の輻輳マーク付きデータユニットの受信への反応は行われない。
【００５６】
待ち合わせ期間Ｔrelaxが満了後、ステップＳ５０９で、Ｌ１を含む輻輳マーク付きデータユニットがまだ到着しているかどうかを判定する。まだ到着しているなら、負荷低減パラメータの設定と発信元ノードへの負荷低減命令の送信の処理を繰り返すために、手順はループしてステップＳ５０６に戻る。Ｌ１を含むデータユニットがもう到着していないなら、手順はループしてステップＳ５００に戻る。
【００５７】
他方、ステップＳ５０１で輻輳マーク付きデータユニットがＬ２のマーキングを含んでいる判定された場合、手順はステップＳ５０２〜Ｓ５０４へと進む。それらのステップは、ステップＳ５０６およびＳ５０８と基本的に同じであるが、ステップＳ５０２では負荷低減パラメータが第２の値ＬＲ2に設定される点が異なり、第２の値ＬＲ2はＬＲ1より大幅の負荷減少を表わす。ステップＳ５０４に続くステップＳ５０５で、Ｌ２のマーキングを搬送するデータユニットが依然として到着しているかどうかを判定し、それが到着している場合、システムはループしてステップＳ５０２に戻り、負荷低減パラメータをＬＲ2に設定するステップ、次いで適切な命令を発信元ノードに送信するステップを繰り返す。これに対して、Ｌ２を搬送するデータユニットがもう到着していない場合、手順はステップＳ５０９に進み、Ｌ１を搬送するデータユニットがひょっとして到着しているかどうかを判定する。この重大さは、ＬＲ2がＬ２に関係しており、Ｌ２は閾値ｔｈ１より大きい閾値ｔｈ２に関係していて、ｔｈ１はＬ１とＬＲ1に関係していることにある。即ち、ステップＳ５０３で与えられるＬＲ2の減少が過負荷の内部ルータをｔｈ２未満への負荷減少に導くなら、負荷がまだｔｈ１より上にある、即ち、Ｌ１のマークの付いたデータユニットが出力される可能性があるので、ステップＳ５０６〜Ｓ５０８に従って負荷をさらに減少させる手順が続くべきである。
【００５８】
今説明した実施例は次の利点を有する。宛先ノードがマーカＬ２を含む輻輳マーク付きデータユニットを受信すると、ｔｈ２を超える過負荷が発生していると判断することができる。Ｌ１を含むデータユニットが到着する場合、ｔｈ１を超える過負荷が発生していると判断することができる。ｔｈ２がｔｈ１より大きい負荷に相当するという知識に基づき、負荷の程度を表わすいかなる測定も実行する必要なしに、それに相当するより大幅の負荷低減を（即ち、ＬＲ2に基づく）開始できる。その結果、内部ルータも宛先ノードも先行技術に比較して簡単化できる。
【００５９】
次に、第１および第２の負荷低減値を選択する例を提示する。
【００６０】
２レベルのデータユニットマーキングの概念を使用すると、マーキングは特定の測定を実行する必要なしに、内部ルータの負荷の程度についての情報を提供する。即ち、データユニットがＬ１のマークを付けられると、負荷がｔｈ１とｔｈ２との間にあることがわかる。さらに、Ｌ２のマーキングが検出されると、負荷はｔｈ２を超えることがわかる。
【００６１】
ｔｈ１とｔｈ２は、ｔｈ１が少しの過負荷に関係するのに対して、ｔｈ２が徹底的な負荷の減少を必要とする大きい過負荷に関係するように選択されるのが好ましい。例えば、ｔｈ１が最適負荷値の５％上にあるように設定されてもよいのに対して、ｔｈ２は最適負荷値の１０％上にあるように設定されてもよい。当然ながら、これらは単なる例であり、他の選択も可能である。
【００６２】
既に前述したように、ｔｈ１およびｔｈ２は何らかの適切なまたは所望のやり方で表現されてもよい。例えば、それらは、絶対負荷値として、例えば、データレートとして表現されてもよいし、相対値として、例えば、絶対上限負荷に対する割合として表現されてもよい。なお、本発明に従って、本願を適用するネットワークドメインのすべての内部ルータは、同じｔｈ１およびｔｈ２の値を使用するのが好ましい。このため、ネットワークドメインの異なる内部ルータが異なる性能を有する場合、ｔｈ１とｔｈ２を所与の絶対最大性能に対する相対値として表現することが好ましい。
【００６３】
既に述べたように、宛先ノードがＬ２マーク付きのデータユニットを受信する場合、内部ルータの負荷はｔｈ２を超えると結論することができる。負荷を減少させるとき、負荷を急激に減少させることが望ましいが、ｔｈ１より下にしないことが好ましい。なぜならｔｈ１より下にすると、アンダーシュートをもたらすかもしれないからである。その結果として、Ｌ２データユニットが受信された場合に設定される第２の負荷減少値を、第２の負荷閾値ｔｈ２と第１の負荷閾値ｔｈ１との差に等しい負荷低減に相当する値に選択することが好ましい。即ち、この係数だけ負荷を減少させることによって、負荷がｔｈ１以下に落ちないことが保証される。
【００６４】
同じ効果を達成する別のやり方は、第２の負荷減少値を、第２の負荷閾値ｔｈ２と第１の負荷閾値ｔｈ１との差を第２の負荷閾値ｔｈ２で除算して得られる商に等しい、即ち、（ｔｈ２−ｔｈ１）／ｔｈ２に等しい負荷低減に相当するように選択することである。本発明が複数の宛先ノードを有するネットワークドメインに適用される場合、第２の負荷閾値をこのように選択することが好ましい。一例をあげると、ｔｈ１とｔｈ２が絶対最大負荷の相対値として、例えば、それぞれ５０％と６０％と表現されると仮定してもよい。この場合、第２の負荷減少値は、（６０−５０）／６０＝１／６に設定される。その結果、負荷減少値に従って負荷を減少させるためにフローを選択するエッジノードは、影響を受けたフローのすべての合計負荷（例えば、合計データレート）を判断し、次いで合計負荷が１／６だけ減少するようにフローの数を減らす。
【００６５】
宛先ノードは、Ｌ１マーク付きのデータユニットを受信すると、内部ルータの負荷がｔｈ１とｔｈ２との間にあると結論することができる。結果として、第１の負荷減少値は、第２の負荷減少値より小さい幅の負荷低減に相当する。その理由は、上記の例を用いて、ｔｈ２−ｔｈ１に相当する負荷低減は、負荷をｔｈ１以下に確実に減少させ、これによってアンダーシュートの原因となるからである。第１の負荷減少値の値は、第２の負荷減少値に対して、何らかの適切なまたは所望のやり方で選択、例えば、１／２、１／３、１／４等のような一定の割合で選択されてもよい。
【００６６】
別の実施例によれば、宛先ノードの制御要素と輻輳制御処理は、負荷低減パラメータを第１の負荷減少値ＬＲ1に設定するステップが２回以上繰り返されるなら、即ち、時間Ｔrelax後もＬ１を含むデータユニットが依然として受信されるなら、ＬＲ1の値が各繰り返しにおいて連続的に低減されるように構成される。言い換えると、輻輳制御処理とは、発信元ノードに一時的な第１の負荷減少値ＬＲ1（ｉ）に相当する終了命令を送信し、次いで所定の時間Ｔrelax待ち合わせ、続いて第１のマーカＬ１を含む輻輳マーク付きデータユニットが依然として到着しているかどうかを判定し、第１のマーカが依然として検出される場合、負荷低減パラメータを、前の一時的な第１の負荷減少値ＬＲ1（ｉ）より小さい新しい一時的な第１の負荷減少値ＬＲ1（ｉ＋１）に設定し、次いで命令を送信しＴrelax待ち合わせるステップを繰り返す手順を備えるようなものである。
【００６７】
これは、例えば、図６の例に見ることができ、この例は、図５に示されている方法の変形例である。図５の対応するステップと同一の図６のステップは、同じ参照番号を付けているので、新しい説明は必要ない。図６の例と図５の例との違いは次の点である。即ち、ステップＳ５０１で輻輳マーク付きデータユニットがＬ１マーカを持っていると判断した後、ステップＳ５１１で値ｉが“０”に設定される。続いて、図５のステップＳ５０６に対応するステップＳ５１２では、負荷低減パラメータは、第１の値ＬＲ1（ｉ）＝ＬＲ1（０）に設定される。次いでステップＳ５０７で、終了すべきフローが選択され、対応する命令が送信される。その後、ステップＳ５１３で、ｉが“１”だけ増やされる。次いで、Ｓ５０８で、待ち合わせ期間Ｔrelaxが始まる。ステップＳ５０９の後、この方法がループしてステップＳ５１２に戻るなら、新しい第１の負荷低減パラメータＬＲ1（ｉ）＝ＬＲ1（１）に設定される。ここで、一般にＬＲ1（ｉ＋１）＜ＬＲ1（ｉ）である。なお、図６の方法では、ステップＳ５０５でのＬ２マーク付きのデータユニットが受信されていないとの判定に続いて、ステップＳ５１４でｉの値を再設定する。
【００６８】
ＬＲ1に常に減少する値を選択することの重要さは、負荷がｔｈ１とｔｈ２との間にあるとわかったなら、負荷を低減させる各ステップは、負荷をｔｈ１未満に落とす可能性を高くすることにある。それゆえ、アンダーシュートを回避するために、負荷低減値ＬＲ1を、連続する各繰り返しで小さくするのが好ましい。
【００６９】
後に続くＬＲ1（ｉ）の値の減少の決め方は、何らかの適切なまたは所望のやり方で選択されてもよい。例えば、ＬＲ1（ｉ）はＬＲ1（０）／（ｉ＋１）と選択されてもよい。好適な実施例によれば、前の一時的な値ＬＲ1（ｉ）より小さい新しい一時的な第１の負荷減少値ＬＲ1（ｉ＋１）の設定は、連続的に設定された一時的な第１の負荷低減値の数列全体の合計が、第２の負荷低減値ＬＲ2以下であるべきであるように構成される。例えば、ＬＲ2がｔｈ２−ｔｈ１に相当するように選択された場合、ＬＲ1（ｉ）を通しての合計は、ｔｈ２−ｔｈ１以下であるべきことが好ましい。なお、連続的に設定された一時的な第１の負荷低減値の数列全体の合計は次のように表わされる。
【００７０】
【数１】
0004768857.tif 000002
【００７１】
本発明の概要と上記の実施例においては、宛先ノードによる負荷低減命令の送信から宛先ノードがその命令を送信した効果を実際に判定できるまでの遅延を考慮に入れるために、待ち合わせ期間Ｔrelaxが設けられている。待ち合わせ期間Ｔrelaxは、何らかのの適切なまたは所望のやり方で選択されてもよい。例えば、固定値に設定されてもよい。即ち、宛先ノードとして動作するエッジノードが設置されるとき、Ｔrelaxは、例えば、考慮中のネットワークドメインのエッジノード間で測定した遅延時間などに基づいて選択された固定値に設定される。一例として、ネットワークドメインのエッジノード間の平均伝播遅延がＴである場合、Ｔrelaxは２Ｔより幾分大きい値、例えば、２．５Ｔに設定されてもよい。
【００７２】
好適な実施例によれば、所定の時間Ｔrelaxは適応可能な値であり、宛先ノードの制御要素と輻輳応答手順は、時間Ｔrelaxに対する適応ルーチンが設けられるように構成される。この適応ルーチンは、発信元ノードから宛先ノードまでのデータユニットの伝播時間の表示を決定し、そのデータユニットの伝播時間のその表示に基づいてＴrelaxを適応させるルーチンを含むことが好ましい。表示を決定するルーチンは、発信元ノードと宛先ノードとの間で交換される周期的なリフレッシュメッセージと専用照会／応答メッセージとキープアライブ・シグナリング・メッセージとの内、少なくともいずれかを監視する処理を有するとよい。これについては、次の例に関して説明する。
【００７３】
上述のように、時間Ｔrelaxは、命令送信からその命令の効果を観察できるまでの遅延を考慮に入れる働きをする。それゆえ、その値は宛先ノードと発信元ノードとの間のメッセージ交換に関係する伝播遅延または往復時間（ＲＴＴ）に基づいて、調整されるのが好ましいはずである。なお、発信元ノードでのフロー終了の影響は終了されていないフローのデータユニットで伝播し、これらのデートユニットが宛先ノードに到達するのに要する時間は、ネットワークドメインを通るパスに沿ったルーティングとキューイングの遅延のために、平均伝播時間より実際のところ長いことがある。その結果として、所定の待ち合わせ期間Ｔrelaxは、伝播遅延より大幅に長く、例えば、３×ＲＴＴ〜５×ＲＴＴに設定されるとよい。
【００７４】
ネットワークドメインの特質と利用されるプロトコルおよびルーチンとに依存して、伝播遅延またはＲＴＴを決定するために異なるアプローチが使用されてもよい。例えば、ソフト状態を使用する（ＲＳＶＰまたはＮＳＩＳシグナリングプロトコルのような）プロトコルが使用されるなら、予約状態を保持するためにリフレッシュメッセージが使用される。これらのメッセージは通常、周期的に送信され、ＲＴＴ測定に使用する好機を提供する。同様に、専用照会／応答メッセージが、ＲＴＴの値を導出するために使用されてもよい。ＮＳＩＳでは、照会メッセージが定義され、宛先ノードから発信元ノードに送信されてもよい。応答として、発信元ノードは、対応する応答メッセージを宛先ノードに返信する。この場合、宛先ノードは、照会の送信から応答の受信までの遅延を測定でき、この測定値をＲＴＴの推定値として使用することができる。
【００７５】
ＲＴＴを評価する別の実行可能性は、ネットワークドメインのエッジノード間で送信されるキープアライブ・シグナリング・メッセージの使用でもよい。そのようなキープアライブ・シグナリング・メッセージに基づいて、各宛先ノードは、自ノードと他の何らかのエッジノードとの間の伝播遅延値またはＲＴＴ値のテーブルを保持してもよい。
【００７６】
Ｔrelaxの値を更新する別のアプローチは、ＲＴＴの最悪の推定値を使用する。ドメイン内・ルーティング・プロトコル（ＵＳＰＦ、ＩＳ−ＩＳなど）が使用されている場合、シグナリングメッセージによってＲＴＴを測定する代わりに、そのプロトコルのルーチンデータベースを使用してもよい。そのようなデータベースを使用して、任意のエッジノードのペア間の実際のパスを推定でき、リンク待ち行列長さ属性にアクセスすることによって、最悪のＲＴＴを計算できる。
【００７７】
図４は制御要素１２３の好適な実施例を示す。参照番号１２３１は、輻輳マーク付きデータユニットを受信しているかどうかを判定する部分を指すが、現在Ｔrelaxの待ち合わせ中でない、即ち、システムが待ち合わせ期間にない場合だけ、この判定が行なわれる。参照番号１２３２は、終了すべきトラフィックの量を計算する部分、即ち、輻輳マーク付きデータユニットが検出された場合、負荷低減パラメータの値を設定する部分を指す。参照番号１２３３は、影響を受けるフローを識別し、負荷低減値に従う負荷低減をもたらすためにどのフローを終了すべきかを選択する部分を指す。部分１２３３は、例えば、終了させる候補のフローについての情報ベースに関連付けられてもよく、その候補フローは、その発信元ノードに従ってグループ化されてもよい。負荷低減値が設定された後、部分１２３３は、所望の負荷減少を実現するために必要な数のフローを選択する。参照番号１２３５は、命令送信から命令の効果を測定できるまでの遅延を推定する部分に関する。例えば、それは、上記の概念の１つ以上を使用するＲＴＴ推定器でもよい。部分１２３５は、例えば、発信元ノードの機能としてＲＴＴ推定値の情報ベースを保持してもよい。参照番号１２３４は、待ち合わせ期間Ｔrelaxを計算または設定する部分を指し、待ち合わせ期間Ｔrelaxは、部分１２３５によって行われる推定に基づき、かつ、部分１２３３で選択されたフローに基づくのが好ましい。時間Ｔrelaxは、例えば、選択されたフローの中の最大ＲＴＴに設定されてもよい。即ち、選択されたフローに関係する発信元ノードの中のどの発信元ノードが最も離れているか、即ち、最大のＲＴＴを有するかが判定され、次いでこのＲＴＴはＴrelaxとして設定される。Ｔrelaxの設定値は、例えば、タイマでカウントダウンされてもよい。その場合、タイマがカウントダウンしている限り、部分１２３１の動作が不能にされる。なお、部分１２３３の選択動作は、格納された最小のＲＴＴを有するフローを部分１２３３が終了のために選択するように、要素１２３５の情報ベースに保持されるＲＴＴ推定値に依存すると良い。
【００７８】
図４に示す制御要素１２３３の要素１２３１〜１２３５は、ハードウェア要素、プログラマブルプロセッサで実行されるソフトウェア要素、またはハードウェアとソフトウェアの組み合わせとして提供されてもよい。
【００７９】
上記の概念は、発信元ノードと内部ルータと宛先ノードとを有するネットワークドメインの何らかの適切な環境で適用することができる。ＤｉｆｆＳｅｒｖ（Differentiated Services）のような、或は、より具体的にはＲＭＤ（Resource Management in DiffServ）のような導入部で説明した概念を使用するネットワークドメインの環境において、本発明を適用することを特に想定している。その概念は、ＲＳＶＰまたはＮＳＩＳシグナリングプロトコルとの関連でも適応されてもよい。
【００８０】
本発明について具体的な実施例を参照して説明したが、これらの実施例は、当業者によりよい理解を提供するだけの役目を果たし、発明を限定する効果を持つことを意図していない。本発明の保護の範囲は、独立請求項の用語によって規定される。参照番号は、請求項を読み易くするのに役立つが、限定する効果をもつものではない。
【図１】
0004768857.tif 000003
【図２】
0004768857.tif 000004
【図３】
0004768857.tif 000005
【図４】
0004768857.tif 000006
【図５】
0004768857.tif 000007
【図６】
0004768857.tif 000008
【図７】
0004768857.tif 000009
【図８】
0004768857.tif 000010