(57)【要約】ネットワークリソースの共有におけるグローバルな公平性を維持しながらネットワークスループットを最大にするルーティングおよび帯域幅割り当てシステム。収集されたグローバルなネットワーク情報から、各ルータ（１１０〜１１８）のルーティングテーブルおよび帯域幅割り当てポリシーが計算される。実施形態によっては、この計算はマルチコモディティフロー法を適用してネットワークリソースの「最大公平」割り当てを提供することを含む。実施形態によっては、各ルータ（１１０〜１１８）がグローバルネットワーク情報を収集し、そのルータ自体のルーティングおよび帯域幅割り当てテーブルをローカルに生成するが、中央の制御ユニットが計算を実行し、その結果を各ルータ（１１０〜１１８）に分配することもできる。計算されたルーティングテーブルはマルチパス（１２２および１２４）を含むことができ、その結果、リンクの使用率を高め、リンク障害に対するロバスト性を増すことができる。
2006527537.tif 000002
【特許請求の範囲】
【請求項１】
複数のネットワークノード、ネットワークノード間の複数の通信リンク、および制御ユニットを含み、前記複数のネットワークノードが複数のホストネットワークノードと複数のルータネットワークノードを含むネットワーク通信環境において、前記制御ユニットがルーティング情報を生成する方法であって、
前記ネットワーク通信環境に関するトポロジー情報を受信すること、
ノード間通信情報を受信すること、ならびに
少なくとも一部は前記受信したトポロジー情報および前記受信したノード間通信情報に基づいて、少なくとも１つのルータネットワークノードに対するルーティング情報を計算すること
を含むことを特徴とする方法。
【請求項２】
前記ネットワーク通信環境は仮想プライベートネットワークを含み、インターネットへの通信リンクをさらに含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記ネットワーク通信環境はネイバーフッドネットワークを含み、インターネットへの通信リンクをさらに含むことを特徴とする請求項１に記載の方法。
【請求項４】
前記ネットワーク通信環境は階層的通信環境であり、前記複数の通信リンクの少なくとも１つはネットワークノード間の仮想通信リンクを含み、前記仮想通信リンクは複数の物理通信リンクを含むことを特徴とする請求項１に記載の方法。
【請求項５】
前記ネットワーク通信環境はインターネットサービスプロバイダピアリング環境を含むことを特徴とする請求項４に記載の方法。
【請求項６】
前記複数の通信リンクの少なくとも１つはポイントツーポイントリンク、ブロードキャストリンク、有線リンク、無線リンク、電気リンク、光ファイバリンク、赤外線リンク、および電波リンクからなるグループから選択されることを特徴とする請求項１に記載の方法。
【請求項７】
前記複数の通信リンクの少なくとも１つは、複数の物理通信リンクを含む仮想通信リンクと、複数のシングルホップ通信リンクを含むマルチホップ通信リンクとを含むグループから選択されることを特徴とする請求項１に記載の方法。
【請求項８】
前記制御ユニットは前記複数のネットワークノードのうちの１つであることを特徴とする請求項１に記載の方法。
【請求項９】
前記複数のネットワークノードのうちの少なくとも１つは、ホストネットワークノードであり、かつルータネットワークノードであることを特徴とする請求項１に記載の方法。
【請求項１０】
トポロジー情報を受信することは、少なくとも１つのルータネットワークノードからトポロジー情報を受信することを含むことを特徴とする請求項１に記載の方法。
【請求項１１】
トポロジー情報を受信することは、前記ルータネットワークノードに接続された少なくとも１つの通信リンクの容量と、前記ルータネットワークノードに接続された通信リンクに接続された少なくとも１つの他のネットワークノードの識別情報とを含むグループから選択された受信情報を含むことを特徴とする請求項１０に記載の方法。
【請求項１２】
ノード間通信情報を受信することは、少なくとも１つのホストネットワークノードからノード間通信情報を受信することを含むことを特徴とする請求項１に記載の方法。
【請求項１３】
ノード間通信情報を受信することは、前記ホストネットワークノードから他のネットワークノードへの絶対予想フローレートと、前記ホストネットワークノードから他のネットワークノードへの相対予想フローレートとを含むグループから選択された情報を受信することを含み、前記予想フローレートは前記ホストネットワークノードから他のネットワークノードへの予想されるフローレートに関係していることを特徴とする請求項１２に記載の方法。
【請求項１４】
ルーティング情報を計算することは、前記受信したトポロジー情報から前記ネットワーク通信環境のマップを作成することを含むことを特徴とする請求項１に記載の方法。
【請求項１５】
ルーティング情報を計算することは、前記受信したノード間通信情報を正規化することを含むことを特徴とする請求項１に記載の方法。
【請求項１６】
ノード間通信情報を受信することは、１対の予想フローレートを受信することを含み、前記１対の第１の要素は第１のネットワークノードから第２のネットワークノードへの予想フローレートであり、前記１対の第２の要素は前記第２のネットワークノードから前記第１のネットワークノードへの予想フローレートであり、ルーティング情報を計算することは前記１対のうちの小さい方のフローレートだけを使用することを含むことを特徴とする請求項１に記載の方法。
【請求項１７】
ノード間通信情報を受信することは、ソースネットワークノードから宛先ネットワークノードへの予想フローレートを受信することを含み、ルーティング情報を計算することは、共通の宛先ネットワークノードを有する１組の予想フローレートを単一の予想フローレートとして取り扱うことを含むことを特徴とする請求項１に記載の方法。
【請求項１８】
前記複数の通信リンクは複数の無線リンクを含み、第１の無線通信リンク上のフローは第２の無線通信リンク上のフローと干渉し、ルーティング情報を計算することは、前記第２の無線通信リンク上に割り当てられたフローを制約して前記干渉を抑制することを含むことを特徴とする請求項１に記載の方法。
【請求項１９】
ルーティング情報を計算することは、ある通信リンクを介してルーティングされる、割り当てられたフローレートの一部を制約することを含むことを特徴とする請求項１に記載の方法。
【請求項２０】
ルーティング情報を計算することは、あるルータネットワークノードを経由してルーティングされる、割り当てられたフローレートの一部を制約することを含むことを特徴とする請求項１に記載の方法。
【請求項２１】
ルーティング情報を計算することは、前記受信したトポロジー情報および前記受信したノード間通信情報に最大公平アルゴリズムを適用することを含むことを特徴とする請求項１に記載の方法。
【請求項２２】
最大公平アルゴリズムを適用することは、１対のネットワークノードに対する予想フローレートを計算することを含むことを特徴とする請求項２１に記載の方法。
【請求項２３】
最大公平アルゴリズムを適用することは、予想フローレートに対する割り当てられたフローレートの比の最小値を最大にするという制約条件の下に、前記ネットワーク通信環境内の割り当てられるフローレートの和を最大にすることを含むことを特徴とする請求項２２に記載の方法。
【請求項２４】
少なくとも１つのルータネットワークノードに対するルーティング情報を計算することは、前記制御ユニットに対するルーティング情報を計算することを含むことを特徴とする請求項１に記載の方法。
【請求項２５】
少なくとも１つのルータネットワークノードに対するルーティング情報を計算することは、前記制御ユニットとは異なるルータネットワークノードに対するルーティング情報を計算することを含み、前記方法は、
前記計算されたルーティング情報を前記ルータネットワークノードに送信すること
をさらに含むことを特徴とする請求項１に記載の方法。
【請求項２６】
少なくとも１つのルータネットワークノードに対するルーティング情報を計算することは、マルチパスルーティング情報を計算することを含み、前記マルチパスルーティング情報は、前記ルータネットワークノードから宛先ネットワークノードへの複数のパスに対するルーティング確率を含むことを特徴とする請求項１に記載の方法。
【請求項２７】
前記制御ユニットがルーティング情報を生成する前記方法であって、
前記ネットワーク通信環境に対する更新済みトポロジー情報を受信すること、
更新済みノード間通信情報を受信すること、ならびに
少なくとも一部は前記受信した更新済みトポロジー情報および前記受信した更新済みノード間通信情報に基づいて、少なくとも１つのルータネットワークノードに対する更新済みルーティング情報を計算すること
をさらに含むことを特徴とする請求項１に記載の方法。
【請求項２８】
更新済みトポロジー情報を受信すること、更新済みノード間通信情報を受信すること、および更新済みルーティング情報を計算することは、定期的に実施されることを特徴とする請求項２７に記載の方法。
【請求項２９】
更新済みルーティング情報を計算することは、更新済み情報を提供しないネットワークノードを考慮から除外することを含むことを特徴とする請求項２７に記載の方法。
【請求項３０】
前記制御ユニットがルーティング情報を生成する前記方法であって、
少なくとも一部は前記受信したトポロジー情報および前記受信したノード間通信情報に基づいて、少なくとも１つのルータネットワークノードに対する帯域幅割り当て情報を計算することをさらに含むことを特徴とする請求項１に記載の方法。
【請求項３１】
帯域幅割り当て情報を計算することは、前記受信したトポロジー情報から前記ネットワーク通信環境のマップを作成することを含むことを特徴とする請求項３０に記載の方法。
【請求項３２】
帯域幅割り当て情報を計算することは、前記受信したノード間通信情報を正規化することを含むことを特徴とする請求項３０に記載の方法。
【請求項３３】
ノード間通信情報を受信することは、１対の予想フローレートを受信することを含み、前記１対の第１の要素は第１のネットワークノードから第２のネットワークノードへの予想フローレートであり、前記１対の第２の要素は前記第２のネットワークノードから前記第１のネットワークノードへの予想フローレートであり、帯域幅割り当て情報を計算することは、前記１対のうちの小さい方のフローレートだけを使用することを含むことを特徴とする請求項３０に記載の方法。
【請求項３４】
ノード間通信情報を受信することは、ソースネットワークノードから宛先ネットワークノードへの予想フローレートを受信することを含み、帯域幅割り当て情報を計算することは、共通の宛先ネットワークノードを有する１組の予想フローレートを単一の予想フローレートとして取り扱うことを含むことを特徴とする請求項３０に記載の方法。
【請求項３５】
帯域幅割り当て情報を計算することは、前記受信したトポロジー情報および前記受信したノード間通信情報に最大公平アルゴリズムを適用することを含むことを特徴とする請求項３０に記載の方法。
【請求項３６】
最大公平アルゴリズムを適用することは、１対のネットワークノードに対する予想フローレートを計算することを含むことを特徴とする請求項３５に記載の方法。
【請求項３７】
最大公平アルゴリズムを適用することは、予想フローレートに対する割り振られたフローレートの比の最小値を最大にするという制約条件の下に、前記ネットワーク通信環境内の割り当てられるフローレートの和を最大にすることを含むことを特徴とする請求項３６に記載の方法。
【請求項３８】
少なくとも１つのルータネットワークノードに対する帯域幅割り当て情報を計算することは、前記制御ユニットの帯域幅割り当て情報を計算することを含むことを特徴とする請求項３０に記載の方法。
【請求項３９】
少なくとも１つのルータネットワークノードに対する帯域幅割り当て情報を計算することは、前記制御ユニット以外のルータネットワークノードに対する帯域幅割り当て情報を計算することを含み、前記方法は、
前記計算された帯域幅割り当て情報を前記ルータネットワークノードに送信すること
をさらに含むことを特徴とする請求項３０に記載の方法。
【請求項４０】
少なくとも１つのルータネットワークノードに対する帯域幅割り当て情報を計算することは、前記ルータネットワークノードから発信する通信リンクに関して、前記ルータネットワークノードに着信する通信リンクを介して受信される帯域幅の割り当てを計算することを含むことを特徴とする請求項３０に記載の方法。
【請求項４１】
前記制御ユニットがルーティング情報を生成する前記方法であって、
前記ネットワーク通信環境に対する更新済みトポロジー情報を受信すること、
更新済みのノード間通信情報を受信すること、および
少なくとも一部は前記受信した更新済みトポロジー情報および前記受信した更新済みノード間通信情報に基づいて、少なくとも１つのルータネットワークノードに対する更新済み帯域幅割り当て情報を計算すること
をさらに含むことを特徴とする請求項３０に記載の方法。
【請求項４２】
更新済みトポロジー情報を受信すること、更新済みノード間通信情報を受信すること、および更新済み帯域幅割り当て情報を計算することは、定期的に実施されることを特徴とする請求項４１に記載の方法。
【請求項４３】
更新済み帯域幅割り当て情報を計算することは、更新済み情報を提供しないネットワークノードを考慮から除外することを含むことを特徴とする請求項４１に記載の方法。
【請求項４４】
前記制御ユニットがルーティング情報を生成する前記方法であって、
ネットワークノードに対する優先度情報を受信することをさらに含み、
帯域幅割り当て情報を計算することは、前記ネットワークノードからの帯域幅に優先度を付与することを含むことを特徴とする請求項３０に記載の方法。
【請求項４５】
帯域幅予約係数を受信することをさらに含み、
帯域幅割り当て情報を計算することは、少なくとも一部は前記帯域幅予約係数によって決定される、使用可能な帯域幅の一部だけを割り当てることを含むことを特徴とする請求項３０に記載の方法。
【請求項４６】
ネットワーク通信環境における制御ユニットがルーティング情報を生成する方法を実施するためのコンピュータ実行可能な命令を含むコンピュータ読取り可能記憶媒体であって、前記方法は、
前記ネットワーク通信環境に対するトポロジー情報を受信すること、
ノード間通信情報を受信すること、および
少なくとも一部は前記受信したトポロジー情報および前記受信したノード間通信情報に基づいて、少なくとも１つのルータネットワークノードに対するルーティング情報を計算すること
を含むことを特徴とするコンピュータ読取り可能記憶媒体。
【請求項４７】
複数のネットワークノード、ネットワークノード間の複数の通信リンク、および制御ユニットを含み、前記複数のネットワークノードが複数のホストネットワークノードおよび複数のルータネットワークノードを含むネットワーク通信環境において、ルータネットワークノードが前記ルータの発信通信リンクに情報をルーティングする方法であって、
前記ネットワーク通信環境に関するトポロジー情報を前記制御ユニットに送信すること、
前記制御ユニットからルーティング情報を受信すること、
前記制御ユニットから帯域幅割り当て情報を受信すること、
少なくとも一部は前記受信したルーティング情報に基づいて、情報を送信するための発信通信リンクを選択すること、および
少なくとも発信通信リンクが輻輳している場合は、少なくとも一部は前記受信した帯域幅割り当て情報に基づいて、前記発信通信リンクの帯域幅を、着信通信リンクを介して受信される情報の間で割り当てること
を含むことを特徴とする方法。
【請求項４８】
前記ルータの発信通信リンクの少なくとも１つは、ポイントツーポイントリンク、ブロードキャストリンク、有線リンク、無線リンク、電気リンク、光ファイバリンク、赤外線リンク、および電波リンクからなるグループから選択されることを特徴とする請求項４７に記載の方法。
【請求項４９】
前記ルータの発信通信リンクの少なくとも１つは、複数の物理通信リンクを含む仮想通信リンクと、複数のシングルホップ通信リンクを含むマルチホップ通信リンクとを含むグループから選択されることを特徴とする請求項４７に記載の方法。
【請求項５０】
前記ルータネットワークノードは、ホストネットワークノードであり、かつルータネットワークノードであることを特徴とする請求項４７に記載の方法。
【請求項５１】
トポロジー情報を送信することは、前記ルータネットワークノードに接続された少なくとも１つの通信リンクの容量と、前記ルータネットワークノードに接続された通信リンクに接続された少なくとも１つの他のネットワークノードの識別情報とを含むグループから選択された情報を送信することを含むことを特徴とする請求項４７に記載の方法。
【請求項５２】
ルーティング情報を受信することは、マルチパスルーティング情報を受信することを含み、前記マルチパスルーティング情報は、前記ルータネットワークノードから宛先ネットワークノードへの複数のパスのルーティング確率を含むことを特徴とする請求項４７に記載の方法。
【請求項５３】
帯域幅割り当て情報を受信することは、前記ルータネットワークノードから発信する通信リンクに関して、前記ルータネットワークノードに着信する通信リンクを介して受信される帯域幅の割り当てを受信することを含むことを特徴とする請求項４７に記載の方法。
【請求項５４】
前記ルータネットワークノードが前記ルータの発信通信リンクに情報をルーティングする前記方法であって、
前記ネットワーク通信環境に関する更新済みトポロジー情報を前記制御ユニットに送信すること、
前記制御ユニットから更新済みルーティング情報を受信すること、および
前記制御ユニットから更新済み帯域幅割り当て情報を受信すること
をさらに含むことを特徴とする請求項４７に記載の方法。
【請求項５５】
更新済みトポロジー情報を送信すること、更新済みルーティング情報を受信すること、および更新済み帯域幅割り当て情報を受信することは、定期的に実施されることを特徴とする請求項５４に記載の方法。
【請求項５６】
前記ルータネットワークノードが前記ルータの発信通信リンクに情報をルーティングする前記方法であって、
少なくとも一部は発信通信リンクの未割り当ての帯域幅の量に基づいて、情報を送信するための前記発信通信リンクを選択することをさらに含むことを特徴とする請求項４７に記載の方法。
【請求項５７】
ネットワーク通信環境におけるルータネットワークノードが前記ルータの発信通信リンクに情報をルーティングする方法を実施するためのコンピュータ実行可能な命令を含むコンピュータ読取り可能記憶媒体であって、前記方法が、
前記ネットワーク通信環境に関するトポロジー情報を制御ユニットに送信すること、
前記制御ユニットからルーティング情報を受信すること、
前記制御ユニットから帯域幅割り当て情報を受信すること、
少なくとも一部は前記受信したルーティング情報に基づいて、情報を送信するための発信通信リンクを選択すること、および
少なくとも発信通信リンクが輻輳している場合は、少なくとも一部は前記受信した帯域幅割り当て情報に基づいて、前記発信通信リンクの帯域幅を、着信通信リンクを介して受信される情報の間で割り当てること
を含むことを特徴とするコンピュータ読取り可能記憶媒体。
【請求項５８】
複数のネットワークノード、ネットワークノード間の複数の通信リンク、および制御ユニットを含み、前記複数のネットワークノードが複数のホストネットワークノードおよび複数のルータネットワークノードを含むネットワーク通信環境において、ホストネットワークノードが前記制御ユニットに情報を提供する方法であって、
ノード間通信情報を収集すること、
前記収集されたノード間通信情報を前記制御ユニットに送信すること、
更新済みノード間通信情報を収集すること、および
前記収集された更新済みノード間通信情報を前記制御ユニットに送信すること
を含むことを特徴とする方法。
【請求項５９】
前記ホストネットワークノードは、ホストネットワークノードであり、かつルータネットワークノードであることを特徴とする請求項５８に記載の方法。
【請求項６０】
ノード間通信情報を収集することは、前記ホストネットワークノードから他のネットワークノードへの絶対予想フローレートと、前記ホストネットワークノードから他のネットワークノードへの相対予想フローレートとを含むグループから選択された情報を収集することを含み、前記予想フローレートは前記ホストネットワークノードから他のネットワークノードへの予想されるフローレートに関係していることを特徴とする請求項５８に記載の方法。
【請求項６１】
更新済みノード間通信情報を収集すること、およびそれらを送信することは定期的に実施されることを特徴とする請求項５８に記載の方法。
【請求項６２】
ホストネットワークノードが前記制御ユニットに情報を提供する前記方法であって、
前記ホストネットワークノードに関する優先度情報を前記制御ユニットに送信すること
をさらに含むことを特徴とする請求項５８に記載の方法。
【請求項６３】
ネットワーク通信環境におけるホストネットワークノードが制御ユニットに情報を提供する方法を実施するためのコンピュータ実行可能な命令を含むコンピュータ読取り可能記憶媒体であって、前記方法が、
ノード間通信情報を収集すること、
前記収集されたノード間通信情報を前記制御ユニットに送信すること、
更新済みノード間通信情報を収集すること、および
前記収集された更新済みノード間通信情報を前記制御ユニットに送信すること
を含むことを特徴とするコンピュータ読取り可能記憶媒体。
【請求項６４】
ルーティング情報を生成するための制御ユニットシステムであって、
ネットワーク通信環境に関するトポロジー情報を受信し、ノード間通信情報を受信するように構成された通信受信装置と、
前記ネットワーク通信環境における少なくとも１つのルータネットワークノードに対するルーティング情報を、少なくとも一部は受信したトポロジー情報および受信したノード間通信情報に基づいて計算するように構成されたプロセッサと、
前記プロセッサによって計算されたルーティング情報を含むルーティング情報データ構造と
を含むことを特徴とする制御ユニットシステム。
【請求項６５】
前記ルータネットワークノードは前記制御ユニットシステムとは異なるものであり、前記制御ユニットシステムは、
計算されたルーティング情報を前記ルータネットワークノードに送信するように構成された通信送信装置
をさらに含むことを特徴とする請求項６４に記載の制御ユニットシステム。
【請求項６６】
前記プロセッサは前記ルータネットワークノードに対する帯域幅割り当て情報を、少なくとも一部は前記受信したトポロジー情報および前記受信したノード間通信情報に基づいて計算するようにさらに構成され、前記制御ユニットシステムは、
前記プロセッサによって計算された帯域幅割り当て情報を含む帯域幅割り当てデータ構造
をさらに含むことを特徴とする請求項６４に記載の制御ユニットシステム。
【請求項６７】
前記ルータネットワークノードは前記制御ユニットシステムとは異なるものであり、前記制御ユニットシステムは、
計算された帯域幅割り当て情報を前記ルータネットワークノードに送信するように構成された通信送信装置
をさらに含むことを特徴とする請求項６６に記載の制御ユニットシステム。
【請求項６８】
前記ルータの発信通信リンクに情報をルーティングするためのルータネットワークノードシステムであって、
複数の発信通信リンクと、
複数の着信通信リンクと、
ネットワーク通信環境に関するトポロジー情報を送信するように構成された通信送信装置と、
ルーティング情報を受信し、帯域幅割り当て情報を受信するように構成された通信受信装置と、
受信したルーティング情報を含むルーティング情報データ構造と、
受信した帯域幅割り当て情報を含む帯域幅割り当てデータ構造と、
少なくとも一部は前記受信したルーティング情報に基づいて、情報を送信するための発信通信リンクを選択するように構成され、少なくとも発信通信リンクが輻輳している場合は、少なくとも一部は前記受信した帯域幅割り当て情報に基づいて、前記発信通信リンクの帯域幅を、着信通信リンクを介して受信される情報の間で割り当てるように構成されたルーティングプロセッサと
を含むことを特徴とするルータネットワークノードシステム。
【請求項６９】
情報を提供するためのホストネットワークノードシステムであって、
ノード間通信情報を収集するように構成された収集装置と、
収集されたノード間通信情報を含むノード間通信データ構造と、
収集されたノード間通信情報を送信するように構成された通信送信装置と
を含むことを特徴とするホストネットワークノードシステム。
【請求項７０】
情報を提供するための前記ホストネットワークノードシステムであって、
前記ホストネットワークノードに関する優先度情報を含む優先度データ構造をさらに含み、前記通信送信装置は、前記優先度情報を送信するようにさらに構成されることを特徴とする請求項６９に記載のホストネットワークノードシステム。
【請求項７１】
ネットワーク通信環境において、ルーティング情報を生成し使用するためのシステムであって、
複数のホストネットワークノードおよび複数のルータネットワークノードを含む複数のネットワークノードと、
ネットワークノード間の複数の通信リンクと、
前記ネットワーク通信環境に関するトポロジー情報を受信し、かつノード間通信情報を受信するように構成された通信受信装置、少なくとも一部は受信したトポロジー情報および受信したノード間通信情報に基づいて少なくとも１つのルータネットワークノードに関するルーティング情報を計算するように構成されたプロセッサ、前記プロセッサによって計算されたルーティング情報を含むルーティング情報データ構造、ならびに計算されたルーティング情報を送信するように構成された通信送信装置を含む制御ユニットと、
前記ネットワーク通信環境に関するトポロジー情報を送信するように構成された通信送信装置、ルーティング情報を受信するように構成された通信受信装置、受信したルーティング情報を含むルーティング情報データ構造、および少なくとも一部は前記受信したルーティング情報に基づいて、情報を送信するための発信通信リンクを選択するように構成されたルーティングプロセッサを含む前記ルータネットワークノードと、
ノード間通信情報を収集するように構成された収集装置、収集されたノード間通信情報を含むノード間通信データ構造、および収集されたノード間通信情報を送信するように構成された通信送信装置を含むホストネットワークノードと
を含むことを特徴とするシステム。
【請求項７２】
前記制御ユニットの前記プロセッサは、前記ルータネットワークノードに対する帯域幅割り当て情報を、少なくとも一部は受信したトポロジー情報および受信したノード間通信情報に基づいて計算するようにさらに構成され、
前記制御ユニットは前記プロセッサによって計算された帯域幅割り当て情報を含む帯域幅割り当てデータ構造をさらに含み、
前記ルータネットワークノードの前記通信受信装置は帯域幅割り当て情報を受信するようにさらに構成され、
前記ルータネットワークノードは受信した帯域幅割り当て情報を含む帯域幅割り当てデータ構造をさらに含み、
前記ルーティングプロセッサは、少なくとも発信通信リンクが輻輳している場合は、少なくとも一部は前記受信した帯域幅割り当て情報に基づいて、前記発信通信リンクの帯域幅を、着信通信リンクを介して受信した情報の間で割り当てるようにさらに構成されることを特徴とする請求項７１に記載のシステム。
【請求項７３】
ホストネットワークノードに対するノード間通信情報データ構造を含むコンピュータ読取り可能記憶媒体であって、前記ノード間通信情報データ構造は、
前記ホストネットワークノードとは異なる第２のネットワークノードを識別するデータを含む第１のデータフィールドと、
前記ホストネットワークノードから前記第２のネットワークノードへの通信の予想フローレートを表すデータを含む第２のデータフィールドと
を含むことを特徴とするコンピュータ読取り可能記憶媒体。
【請求項７４】
予想フローレートを表す前記第２のデータフィールド中の前記データは、前記ホストネットワークノードから前記第２のネットワークノードへの絶対予想フローレートと、前記ホストネットワークノードから前記第２のネットワークノードへの相対予想フローレートとを含むグループから選択され、前記予想フローレートは、前記ホストネットワークノードから他のネットワークノードへの予想されるフローレートに関係していることを特徴とする請求項７３に記載のノード間通信情報データ構造。
【請求項７５】
前記ノード間通信情報データ構造であって、
前記ホストネットワークノードとは異なり、また前記第２のネットワークノードとも異なる第３のネットワークノードを識別するデータを含む第３のデータフィールドと、
前記ホストネットワークノードから前記第３のネットワークノードへの通信の予想フローレートを表すデータを含む第４のデータフィールドと
をさらに含むことを特徴とする請求項７３に記載のノード間通信情報データ構造。
【請求項７６】
前記ノード間通信情報データ構造であって、
前記ホストネットワークノードに関する優先度情報を表すデータを含む第３のデータフィールド
をさらに含むことを特徴とする請求項７３に記載のノード間通信情報データ構造。
【請求項７７】
ルータネットワークノードに対するマルチパスルーティング情報データ構造を含むコンピュータ読取り可能記憶媒体であって、前記マルチパスルーティング情報データ構造は、
宛先ネットワークノードを識別するデータを含む第１のデータフィールドと、
前記ルータネットワークノードから前記宛先ネットワークノードへの第１のパスを識別するデータを含む第２のデータフィールドと、
第１のパスのルーティング確率を表すデータを含む第３のデータフィールドと、
前記ルータネットワークノードから前記宛先ネットワークノードへの第２のパスを表すデータを含む第４のデータフィールドと、
前記第２のパスのルーティング確率を表すデータを含む第５のデータフィールドと
を含むことを特徴とするコンピュータ読取り可能記憶媒体。
【請求項７８】
前記マルチパスルーティング情報データ構造であって、
第１のパスを識別する前記第２のデータフィールド中の前記データは、前記ルータネットワークノードから前記宛先ネットワークノードへの前記第１のパス上の次のホップの識別子を含むことを特徴とする請求項７７に記載のマルチパスルーティング情報データ構造。
【請求項７９】
前記マルチパスルーティング情報データ構造であって、
第２の宛先ネットワークノードを識別するデータを含む第６のデータフィールドと、
前記ルータネットワークノードから前記第２の宛先ネットワークノードへのパスを識別するデータを含む第７のデータフィールドと
をさらに含むことを特徴とする請求項７７に記載のマルチパスルーティング情報データ構造。
【請求項８０】
ルータネットワークノードに対する帯域幅割り当て情報データ構造を含むコンピュータ読取り可能記憶媒体であって、前記帯域幅割り当て情報データ構造は、
前記ルータネットワークノードの発信通信リンクを表すデータを含む第１のデータフィールドと、
前記ルータネットワークノードの着信通信リンクを介して受信した、前記発信通信リンクに対する帯域幅の割り当てを表すデータを含む第２のデータフィールドと
を含むことを特徴とするコンピュータ読取り可能記憶媒体。
【請求項８１】
前記帯域幅割り当て情報データ構造であって、
前記ルータネットワークノードの第２の発信通信リンクを表すデータを含む第３のデータフィールドと、
前記ルータネットワークノードの着信通信リンクを介して受信した、前記第２の発信通信リンクに対する帯域幅の割り当てを表すデータを含む第４のデータフィールドと
をさらに含むことを特徴とする請求項８０に記載の帯域幅割り当て情報データ構造。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は一般に、コンピュータネットワーク通信に関し、より詳細には、ルーティング情報および帯域幅割り当て情報を提供することに関する。
【背景技術】
【０００２】
着信パケットを受信したとき、ルータはそのパケットをどの発信リンク上に送信すべきかを決定する。インターネットのルータは一般に、そのルータからパケットの宛先への最短パスに基づいてこの決定を行う。ルータは独立にかつローカルに、パケットの宛先へのこの最短パスを計算する。ルータは、発信リンクの待ち時間、それらのリンクの容量、各リンク上の現在の負荷など様々なルーティングメトリックを考慮することができるが、ルータはインターネット中のエンドホスト間の実際の通信パターンとは独立に発信パスを選択する。
【０００３】
ルーティングプロトコルにおけるこの独立でローカルな意思決定プロセスは、インターネットの拡張可能性にとって極めて重要なものであった。すなわち、新しいルータおよび新しいリンクは、インターネット全体のルーティング決定を再計算する必要なしに容易に追加される。しかし、このルーティングプロセスではまた、複数のルータが同一の最短パスを使用することを選択し、他のパスを十分に使用しないまま残しておくとき、不要な共有ボトルネックなどの非効率性が生ずる可能性がある。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
ローカルなルーティングの決定は、明らかに不公平になることも多い。すなわち、ローカルなルーティングの決定は、他のデータフローに対する不十分さを犠牲にして、あるデータフローの通信特性を拡張する。データネットワークにおいて広く受け入れられている公平性の尺度は「最大最小公平性（ｍａｘ−ｍｉｎ  ｆａｉｒｎｅｓｓ）」と呼ばれている。リソースの最大最小公平割り当てでは、ある消費者のリソースの割り当てを増加させると必ず、より少ない割り当てを有する消費者に不利益をもたらすことになる。フェアキューイングやラウンドロビンなどのパケットスケジューリングアルゴリズムは、単一のボトルネックリンクまたはルータを超える、データフローに関する最大最小公平性を概算する。しかし、このようなローカルなフローごとの公平性は、通常グローバルには不公平になる。なぜならば、通信ノード（ホストまたはルータ）の中には、いくつかの通信フローをサポートしているものがあるからである。
【０００５】
ネットワークによっては、マルチパスルーティングが可能である。その場合、ルータは、確実に最短なパス以外のパスに沿って発信パケットを送信することができる。マルチパスルーティングにより、単一の最短パスルーティングより極めて高いネットワークスループットが可能になる。マルチパスルーティングはまた、リンク障害に対しても単一の最短パスルーティングでは実現できないロバスト性をもたらす。残念ながら、マルチパスルーティングの現在のフローごとのまたはローカルな帯域幅割り当て実装では、従来の単一パスルーティングプロトコルよりもさらに不公平になることもある。
【課題を解決するための手段】
【０００６】
前述のことを考慮して、本発明は、ネットワークリソースの共有におけるグローバルな公平性を維持しながらネットワークスループットを最大にするルーティングおよび帯域幅割り当てシステムを提供する。収集されたグローバルネットワーク情報（例えば、ノード間通信パターンやネットワークトポロジー）から、各ネットワークルータに対するルーティングテーブルおよび帯域幅割り当てポリシーが計算される。実施形態によっては、この計算は、マルチコモディティフロー法を適用してネットワークリソースの「最大公平」割り当てを提供することを含む。
【０００７】
いくつかの実施形態では、各ルータがグローバルネットワーク情報を収集し、そのルータ自体のルーティングと帯域幅割り当てテーブルをローカルに生成するが、中央の高信頼制御ユニットが計算を実施し、その結果を各ルータに分配することにより、計算とセキュリティの両方に関して、ルータは、より単純で安価になり得る。
【０００８】
本発明の諸実施形態は、優先度レベルによって差別化されたデータフローを適切に考慮する。また、計算される帯域幅ポリシーでは、すべてのネットワーク帯域幅を割り当てる必要があるわけではなく、予期せぬ需要の急増を処理するためにある程度の帯域幅を未割り当てのまま残しておくことができる。計算されるルーティングテーブルは複数のパスを含むことができ、結果的にリンクの使用率が高まり、リンク障害に対するロバスト性がもたらされる。
【０００９】
状況によっては、ルーティングおよび帯域幅割り当てテーブルを計算する間に、ノード間通信パターンが集約されることがある。例えば、インターネットサービスプロバイダ（ＩＳＰ）間の通信フローを集約することによって、より正確な結果が得られる。なぜならば、ＩＳＰ間の通信フローは、エンドホスト間の個々のフローの変化と比べて時間的により緩やかに変化するからである。ゲートウェイによってインターネットに接続された企業ネットワークの場合は、ゲートウェイを通過する通信だけを管理することによって許容できる結果が得られる。
【００１０】
添付の特許請求の範囲は本発明の特徴を詳細に記載したものであるが、本発明ならびに本発明の目的および利点は、以下の詳細な説明を添付の図面と併せて読むことによって最も良く理解できるはずである。
【発明を実施するための最良の形態】
【００１１】
図面に関して、図中同一の参照番号は同一の要素を表す。また、本発明は適切なコンピューティング環境で実装されるものとして示されている。以下の説明は本発明の諸実施形態に基づいてなされるものであり、本明細書において明示的に示されていない代替実施形態に関して本発明を制限するものと解釈すべきものではない。本説明のセクションＩでは、例示的なルーティングおよび帯域幅割り当てアーキテクチャを提示する。セクションＩＩでは、本発明とともに使用できる１つのメトリックとしてのノード要求公平性を定義する。セクションＩＩＩでは、ノード要求公平性のマルチコモディティフロー実装を提示する。最後に、セクションＩＶでは、本発明の実施形態のシミュレーション結果を提示する。
【００１２】
以下の説明では、別途指示していない場合は、本発明を１つまたは複数のコンピューティング装置によって実施される諸動作の処理およびシンボリックな表示に関連して説明する。したがって、コンピュータ実行される（computer-executed）と呼ばれることもある、このような処理および動作は、データを構造化された形で表す電気信号からなるコンピューティング装置の処理ユニットによる処理を含むことが理解されるであろう。この処理は、コンピューティング装置のメモリシステム内の各位置においてデータを変換または維持するが、それにより当業者には良く知られた方法によって装置の動作を再構成あるいは変更する。データが維持されるデータ構造は、データの形式によって定義された特定の特性を有するメモリの物理的な位置である。本発明は前述の文脈で説明されるが、当業者には理解されるように、それは制限を意図するものではない。例えば、以下で説明する様々な処理および動作は、ハードウェアの形で実装することもできる。
【００１３】
（セクションＩ：例示的ルーティングおよび帯域幅割り当てアーキテクチャ）
本発明は、ネットワークリソースの共有におけるグローバルな公平性を維持しながら、ネットワークスループットを最大にするルーティングおよび帯域幅割り当てシステムを提供する。収集されたグローバルなネットワーク情報（例えば、ノード間通信パターンやネットワークトポロジーなど）から、ルーティングテーブルおよび帯域幅割り当てポリシーが、各ネットワークルータに対して計算される。
【００１４】
例えば、インターネットルータによって一般的に使用されているローカルな意思決定に対する、本発明によるグローバルな情報の使用の利点が図１に示されている。図１において、ネットワーク通信環境１００はデータフローのソースと宛先を含む。これらのソースと宛先は、「ホスト」１０２、１０４、１０６、および１０８とラベル付けされている。ルータ１１０、１１２、１１４、１１６、および１１８は、ソースホストからデータフローを受信し、そのフローを宛先ホストに送信する。図１の「ホスト」および「ルータ」のラベル付けは、単に本議論における便宜上のものであり、装置によってはホストとルータの両方の機能を果たすものもある。
【００１５】
ホスト１０２がホスト１０４と通信しようとしたとき、データフローの最短パス、すなわち現在のインターネットルータによって選択されるはずのパスは、ルータ１１０および１１２を通過する、１２０とラベル付けされたパスである。ホスト１０６がホスト１０８と通信しようとしたときは、その最短データパス１２２もまたルータ１１０および１１２を通過する。したがって、最短パスルーティングによって、ルータ１１０および１１２を接続するリンクに不要なボトルネックが生じる。このボトルネックは不要である。なぜならば、最短パスルーティングを用いることにより、ホスト１０６と１０８の間の代替パス１２４は選択されたパス１２２より長いので、代替パス１２４が使用されないまま残されるからである。本発明の方法は、グローバルネットワーク情報を使用してこのような不要なボトルネックの生成を回避し、結果としてネットワークの使用効率を高めるものである。
【００１６】
図２は、本発明を実装するための例示的アーキテクチャを示す。ネットワークホスト１０２、１０４、１０６、および１０８は、（データフロー２０２によって示されているように）それらの予想される通信要求に関する情報を、中央制御ユニット２００に定期的に送信する。ネットワークルータ１１０、１１２、１１４、１１６、および１１８は、ネットワークトポロジー情報を制御ユニット２００に定期的に送信する（データフロー２０４）。制御ユニット２００はこのネットワーク情報を使用して、グローバルに効率的かつ公平なルーティング決定を行う。次いで、制御ユニット２００はルーティングおよび帯域幅割り当てテーブルを各ルータに送信する（同じくデータフロー２０４）。受信したルーティングおよび帯域幅割り当てテーブルを使用して、ルータは制御ユニット２００のグローバルに効率的で公平なポリシーを実施する。セクションＩの残りの部分では、実装上の考慮事項および図２のアーキテクチャの詳細を提示する。
【００１７】
図２のアーキテクチャは、あらゆるネットワークに広く適用可能であるが、制御ユニット２００によって収集されるデータの量、ならびにその情報からルーティングおよび割り当てポリシーを形成するために使用される計算の量は、ネットワークの規模とともに増大することに留意されたい。したがって、本発明の方法は比較的小規模なネットワーク（例えば、わずか数百台のルータからなるネットワーク）に対して最も容易に実装される。しかしこのことは、少なくとも２つの理由から、本発明の適用範囲を厳しく制限するものではない。第１に、比較的小規模なネットワークの内部でルーティングと割り当てを最適化することは、それ自体が価値のある目標になる。本発明の方法の対象となる小規模なネットワークの例には、インターネットへのファイアウォールを備えた企業の仮想プライベートネットワーク、ホストが相互に通信しゲートウェイによってインターネットへのアクセスを共有する有線または無線のネイバーフッドネットワーク、およびＩＳＰ間のピアリング（peering）などがある。次の例はまた、なぜ本発明が厳しく制限されないかの第２の理由を示す。例えば、多くの大規模ネットワークは小規模ネットワークの階層構造としてモデル化することができる。この場合、本発明は階層構造の適切なレベルに適用することができる。例えば、ＩＳＰピアリングの場合は、各ＩＳＰは単一のノードとしてモデル化される。また、各ＩＳＰのネットワークの実装に関する実際の詳細は、各ＩＳＰを接続するリンクに関するルーティングおよび割り当てポリシーに大きく影響を与えることはない。
【００１８】
図２のホスト１０２、１０４、１０６、および１０８、ルータ１１０、１１２、１１４、１１６、および１１８、ならびに制御ユニット２００は、任意のアーキテクチャであってもよい。図３は、本発明をサポートする例示的コンピュータシステムを一般的に示す構成図である。図３のコンピュータシステムは適切な環境のほんの一例に過ぎず、本発明の使用の範囲または機能に関していかなる制限を課すことも示唆するものではない。コンピューティング装置１０２、１１０、および２００のいずれについても、図３に示された各コンポーネントのいずれか１つまたはその組合せに関して何らかの依存性または要件を有しているものと解釈すべきではない。本発明は、他の多くの汎用または専用のコンピューティング環境または構成とともに使用することができる。本発明とともに使用するのに適した周知のコンピューティングシステム、環境、および構成の例には、これらに限られるものではないが、パーソナルコンピュータ、サーバ、ハンドヘルドまたはラップトップ装置、タブレット装置、マルチプロセッサシステム、マイクロプロセッサベースのシステム、セットトップボックス、プログラマブル家電、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータ、および上記のシステムまたは装置のいずれかを含む分散コンピューティング環境などが含まれる。その最も基本的な構成では、コンピューティング装置１０２は一般に、少なくとも１つの処理ユニット３００およびメモリ３０２を含む。メモリ３０２は、（ＲＡＭなどの）揮発性、（ＲＯＭやフラッシュメモリなどの）不揮発性、またはその両者の組合せであってもよい。この最も基本的な構成は、図３では破線３０４によって示されている。コンピューティング装置１０２は追加の機構および機能を備えることができる。例えば、コンピューティング装置１０２は、これに限られるものではないが、磁気および光ディスクならびにテープなど（取外し可能または取外し不可能な）追加の記憶装置を備えることができる。このような追加の記憶装置は、図３では取外し可能な記憶装置３０６および取外し不可能な記憶装置３０８によって示されている。コンピュータ記憶媒体には、コンピュータ読取り可能命令、データ構造、プログラムモジュール、その他のデータなどの情報を記憶するための任意の方法または技術で実装された、揮発性および不揮発性、取外し可能および取外し不可能な媒体が含まれる。メモリ３０２、取外し可能な記憶装置３０６、および取外し不可能な記憶装置３０８などはすべて、コンピュータ記憶媒体の例である。コンピュータ記憶媒体には、これらに限られるものではないが、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリなどのメモリ技術製品、ＣＤ−ＲＯＭ、ＤＶＤなどの光記憶装置、磁気カセット、磁気テープ、磁気ディスク記憶装置などの磁気記憶装置、ならびに所望の情報を記憶するために使用でき、コンピューティング装置１０２によってアクセスできる他の任意の媒体が含まれる。このようなコンピュータ記憶媒体は、コンピューティング装置１０２の一部であってもよい。コンピューティング装置１０２はまた、この装置が他の装置と通信することを可能にする通信チャネル３１０を含むことができる。通信チャネル３１０は通信媒体の例である。通信媒体は一般に、コンピュータ読取り可能命令、データ構造、プログラムモジュール、または他のデータを、搬送波または他の伝送機構などの被変調データ信号の形で実施するとともに、任意の情報配信媒体を含む。「被変調データ信号」という用語は、情報を信号の形で符号化するように設定または変更された１つまたは複数の信号特性を有する信号を意味する。制限の意味ではなく例として、通信媒体には、有線ネットワークや直接有線接続などの有線媒体、および音響、無線周波数（ＲＦ）、赤外線、その他の無線媒体などの無線媒体が含まれる。本明細書で使用される「コンピュータ読取り可能媒体」という用語には、記憶媒体と通信媒体の両方が含まれる。コンピューティング装置１０２はまた、キーボード、マウス、ペン、音声入力装置、タブレット、タッチ入力装置などの入力装置３１２を含むことができる。ディスプレイ（タッチ入力装置と一体のこともある）、スピーカ、プリンタなどの出力装置３１４を含むこともできる。これらの装置はすべて当技術分野では周知であり、ここで詳細を論ずる必要はない。
【００１９】
図４は、図２のアーキテクチャにおけるホストノード１０２などのホストノードによって使用可能な例示的な方法を表す。ステップ４００において、ホストノード１０２はそのノード間通信のニーズに関する情報を収集し、ステップ４０２において、収集した情報を制御ユニット２００に送信する。
【００２０】
ノード間通信情報は、様々な実施形態において様々な形態を取る。図５はその一例である。情報５００は、ホストノード１０２を識別し、ホストノード１０２から他のホストノードに送信されるデータの予想量を識別する。当技術分野では、これらのデータフローを推定するための多くの方法が知られている。ホストノード１０２が実際にはルータである場合、およびデータフローが他のルータへのデータフローの履歴平均を表す場合には、これらの推定値は極めて正確になり得るとだけ述べておけば十分であろう。
【００２１】
セクションＩＩＩではノード間通信情報５００の詳細な分析を提示する。ここでは、各ホストノードによって生成される情報５００の量が、小規模なネットワークにおいては少ないこと、その量がネットワーク中のホストノードの数に比例することに留意されたい。
【００２２】
図４に戻って、ステップ４０４において、ホストノード１０２はホストノード１０２のデータフローの優先度を制御ユニット２００に通知することができる。図５の例では、ホストノード１０２を起点とするすべてのデータフローに優先度２が割り当てられている。他の実施形態では、各データフローにそれ自体の優先度が割り当てられる。これらの優先度の割当てを調整する機構が存在する必要がある。そうでなければ、どのホストノードもみな、優先度が無意味になるまでそれ自体のフローの優先度を高めるはずである。あるシナリオでは、優先度は、ホストノードと制御ユニット２００の間の契約上の合意を可能な限り反映させるような形で、制御ユニット２００によって設定される。このシナリオでは、ホストノード１０２は優先度を制御ユニット２００に通知する必要はない。他のシナリオでは、制御ユニット２００以外の機関が優先度を設定し、優先度情報を各ホストノードに送信する。当技術分野では周知のように、ホストノード１０２から送信される優先度情報５００には認証証明書が添付され、通知された優先度が合法的に割り当てられたことを保証する。
【００２３】
ステップ４０６において、ホストノード１０２は上記のプロセスを繰り返す。繰返しは定期的に実施することができる。あるいは、ノード間通信情報５００が変化した場合に常に呼び出すようにすることもできる。
【００２４】
図２のアーキテクチャにおける例示的ルータ、例えばルータ１１０では、図６ａおよび図６ｂにおいて示された方法が使用される。ステップ６００において、ルータ１１０はそのルータに最も近いネットワーク環境１００の部分のトポロジーに関する情報を収集し、ステップ６０２において、収集したネットワークトポロジー情報を制御ユニット２００に送信する。
【００２５】
収集されたトポロジー情報は、周知のリンク記述告知（Ｌｉｎｋ  Ｓｔａｔｅｍｅｎｔ  Ａｎｎｏｕｎｃｅｍｅｎｔ）の形を取ることができる。図７は、ルータ１１０によって収集されたトポロジー情報７００の例を示す。情報７００は、このトポロジー情報を提供するルータを識別し、次いでこのルータ１１０に接続された通信リンクのテーブルを提示する。各通信リンクについて、リンクの容量、リンクの他端におけるルータの識別情報、およびリンクの現在の状態が与えられる。
【００２６】
図６ａに戻って、ルータ１１０は、ステップ６０４およびステップ６０６においてそれぞれ、制御ユニット２００からルーティングテーブルおよび帯域幅割り当てテーブルを受信する。これらのテーブルの例については、図９から１２に関連して後で論ずる。
【００２７】
ルータ１１０が着信データパケットを受信したとき、ステップ６０８において、ルータ１１０は、受信したルーティングテーブルを使用してそのデータパケットについての発信リンクを選択する。実施形態によっては、制御ユニット２００は、必ずしもネットワーク環境１００のすべての通信リンクについてのすべての帯域幅を割り当てるとは限らない。未割り当ての帯域幅は予備であり、ステップ６１０において発信パケットを送信するために呼び出される。予備の帯域幅は、予期しない、またはめったに起こらない要求の急増を処理するために有用なものである。
【００２８】
ほとんどの場合、ルータ１１０は制御ユニット２００から受信したルーティングテーブルだけを利用し、受信した帯域幅割り当てテーブルは無視する。しかし、ステップ６１２において、ルータ１１０の発信通信リンクの１つが輻輳してきた場合は、ルータ１１０は帯域幅割り当てテーブルを使用して、輻輳している発信リンク上の帯域幅を着信データパケット間で割り当てる。そうすることによって、ルータ１１０はネットワーク環境１００の他のルータとともに、制御ユニット２００によって生成されたグローバルな公平性ポリシーを実施する。
【００２９】
上記のホストノード１０２と同様に、ステップ６１４において、ルータ１１０は上記の方法のステップを繰り返す。ルータ１１０は、更新済みのトポロジー情報を、定期的に、またはトポロジー情報７００が変化した場合に送信する。
【００３０】
制御ユニット２００は、ルーティングおよび帯域幅割り当てテーブルを生成することによって、そのグローバルな効率性および公平性ポリシーを成文化する。制御ユニット２００によって使用可能な例示的方法が、図８ａおよび８ｂに示されている。ステップ８００において、制御ユニット２００は、図６ａのステップ６０２においてルータによって送信されたトポロジー情報７００を受信する。次に、ステップ８０２において、制御ユニット２００は受信したトポロジー情報７００を使用して、ネットワーク環境１００のマップを作成する。ステップ８０２のこの説明は、例示のためだけのものであることに留意されたい。ローカルなトポロジーの記述７００の組を、論理的な全体に（into a logical whole）編集するための多くの技術が周知であるが、これらの技術のすべてが、ネットワークマップの作成を必要とするとは限らないことに留意されたい。
【００３１】
ステップ８０４において、制御ユニット２００は、図４のステップ４０２においてホストによって送信されたノード間通信情報５００を受信する。実施形態によっては、次いで制御ユニット２００は、ステップ８０６においてこの情報５００を正規化する。正規化には、予想データフローレートを各ホストの総予想出力トラフィックのパーセンテージとして表現することが含まれる。正規化については、後のセクションＩＩＩで論ずる。
【００３２】
ステップ８０８は、もう１つのオプションステップである。要求の不正申告を防ぐために、制御ユニット２００は、ノードＡによって報告されたノードＢに向かうデータフロー要求と、ノードＢによって報告されたノードＡに向かうデータフロー要求とを比較する。次に、制御ユニット２００は、２つの要求値のうちの大きい方を小さい方で置き換える。後のセクションＩＩＩで論ずるように、この単純な置換えにより、利己的なホストノードが帯域幅のより大きな割り当てを受けるためにそのノードの要求を水増しする誘因を除去する。
【００３３】
図４のステップ４０４に関連して上述したように、データフローには優先度を割り当てることができる。制御ユニット２００は、ステップ８１０においてこの優先度情報を受信する。優先度情報が受信されない場合、制御ユニット２００はすべてのデータフローを同一の優先度であるものとして取り扱う。
【００３４】
制御ユニット２００は、ネットワーク環境１００において使用できる帯域幅のすべてを割り当てる必要があるというわけではなく、むしろ緊急の使用のために若干の帯域幅を確保しておくことができる。図８ｂのステップ８１２では、制御装置２００は、予備として確保しておく使用可能な帯域幅の割合を示す係数を受信する。もちろん、係数の一部が一日の時刻とともに変化し、様々な通信リンクが様々な予約係数を有するなど、より綿密な予約手順が可能である。
【００３５】
ステップ８１４および８１６において、制御ユニット２００は、受信したノード間通信情報５００および受信したトポロジー情報７００を使用して、ネットワーク環境１００における各ルータに対するルーティングおよび帯域幅割り当てテーブルを計算する。制御ユニット２００は、グローバルなネットワーク効率やネットワークリソースの公平な共有など、特定のネットワークポリシーの目標を達成するような方法でこれらの計算を実施する。これらの計算方法が非常に複雑になり得ること、およびそれらが本発明の方法についての理解の中心になることから、それらの詳細な議論は後のセクションＩＩおよびＩＩＩに委ねる。
【００３６】
ステップ８１８および８２０において、制御ユニット２００は計算結果のルーティングおよび帯域幅割り当てテーブルを各ルータに送信する。これらのテーブルの指示に従うことによって、ルータは制御ユニット２００のグローバルな効率性や公平な共有のポリシーを実施する。
【００３７】
ステップ８２２は、制御ユニット２００が上記のプロセスを、定期的にあるいは着信情報５００および７００が変化した場合に必要に応じて繰り返すことを示す。例えば、制御ユニット２００はすべてのルータを対象とするタイマを設定して、そのリンク状態情報７００をリフレッシュすることができる。ルータ１１０が適時の報告に失敗した場合は、制御ユニット２００はそのルータ１１０およびそれに関連するリンクを、現在のトポロジーから削除することができる。（タイマ値はリフレッシュ期間の倍数でなければならない）。タイムアウトまでは、ネットワーク環境１００の影響を受けない部分は機能し続ける。タイムアウト時に、制御ユニット２００はルーティングおよび帯域幅割り当てテーブルを再計算し（ステップ８１４および８１６）、影響を受けるルータに新しいテーブルを配信する（ステップ８１８および８２０）。ルータ１１０の障害に応答するために制御ユニット２００が必要とする時間は、既存のリンク状態プロトコル（link state protocol）に対するものと同じである。
【００３８】
図２から８に関する上述の説明は、ホスト、ルータ、および制御ユニットの論理的な機能を説明しているものと見なすことができる。ネットワーク環境１００においては、単一の物理的な装置は、これらの機能の２つ、または３つすべてを実施することができる。各ルータは、それ自体のノード間通信情報５００およびトポロジー情報７００を受信し、それに従って、そのルータ自体のルーティングおよび帯域幅割り当てテーブルを計算することができる。しかし、中央の制御ユニット２００が、ネットワーク環境１００における他のルータに対するステップ８１４および８１６の計算を実施することがより好ましいことも多い。中央制御ユニット２００は、維持がより容易である。また、信頼性の観点を見ても、制御ユニット２００の方が分散した一組のルータより、はるかに容易に保護し認証することができる。
【００３９】
中央制御ユニット２００が、単一障害点またはルーティングのボトルネックになることを心配する必要はない。なぜならば、制御ユニット２００は単なる制御エンティティであり、ルーティングのボトルネックにはなり得ないからである。また、既知の技術を使用して、制御ユニット２００が故障した場合に引き継ぐためのバックアップ制御ユニットを配置することもできる。あるシナリオでは、各ルータはすべてのルータの中央制御ユニットとして動作することができ、故障したルータの代替またはそれらを引き継ぐルータとして動作することができる。
【００４０】
上記の技術の一例として、図９のネットワーク環境１００を考える。この図では、各ノード１０２、１０４、１０６、および１０８はホストであり、ルータでもある。ホスト／ルータノード１０２の予想されるノード間通信要求は、図５に示されたものとする。すなわち、各ホスト／ルータノード１０４、１０６、および１０８に対し、ホスト／ルータノード１０２は、２５０Ｋｂｐｓのトラフィックを送信すると予想される。ネットワーク環境１００は、ホスト／ルータノード１０２をホスト／ルータノード１０４、１０６に直接接続する通信リンクを備えるが、ホスト／ルータノード１０８に対してはその様な直接リンクは存在しない。各通信リンクは、予想される要求を十分に上回る、例えば１Ｍｂｐｓの容量を有する。
【００４１】
本発明の方法によって作成され、ホスト／ルータノード１０２に送信される１つの可能なルーティングテーブルが、図１０に示されている。予想されるように、ホスト／ルータノード１０２からその隣接ノード１０４および１０６へのトラフィックは、仲介なしに直接送信される。
【００４２】
非隣接ノード１０８へのトラフィックのルーティングは、より興味深いものである。単一の最短パスを選択するのではなく、ルーティングテーブル１０００は、トラフィックを２つのパスの間で均等に分割し、半分がノード１０４を通過し残りの半分がノード１０６を通過するように指定する。この「マルチパス」ルーティングよる解決は、ネットワークリソースの使用率を大幅に高める。しかし、マルチパスルーティングは、パケットが順不同に配信されることにより、トランスポート層プロトコルに問題を提起する。この問題に対するいくつかの解決策が提案されてきた。しかし、それらの解決策のいずれもが、まだこの分野での支配的な地位を獲得していない。
【００４３】
他の例として図１１を考える。この図は、集約データフローレートが、ルータ１１０に着信することを示す。これらのレートは、制御ユニット２００（図１１には示されていない）によって、ノード間通信情報５００およびローカルトポロジー情報７００を処理する際に計算される。これらの集約データレートから、制御ユニット２００は図１２の帯域幅割り当てテーブル１２００を作成する。ルータ１１０に接続された発信通信リンク（テーブル１２００における「ルーティング方向」）が輻輳し始めたとき、ルータ１１０は、帯域幅割り当てテーブル１２００を参照して、その発信リンクの帯域幅のうちのどの程度を各着信リンクに入ってくるトラフィックに割り振るべきかを決定する。
【００４４】
従来のパケットスケジューリングアルゴリズムと異なり、本発明は個々のデータフローを追跡する必要がなく、各着信通信リンク上の集約トラフィックフローを追跡するだけでよいことに留意されたい。このことにより、制御ユニット２００によって維持される状態情報の量が削減されることによって、図８ｂのステップ８１４および８１６における計算が単純化される。状態情報の量を最小化することは、ルータ設計における重要な技術上の課題である。従来のパケットスケジューリングアルゴリズムではデータフローの数に比例する状態情報の量（システム中のノードの数の２乗オーダかそれ以上になり得る）が必要になるが、本発明の方法では、あるルータに隣接するルータの数に比例する状態情報量を使用することになり、その量ははるかに少ないものになる。
【００４５】
（セクションＩＩ：ノード要求の公平性）
このセクションでは、ルーティングおよび帯域幅割り当てテーブルを計算する際に、制御ユニット２００によって使用できる１つのメトリックであるノード要求の公平性を定義する。ノード要求の公平性についての動機付けは、インターネットのために提案されたローカルな、フローごとのパケットスケジューリングアルゴリズムが、グローバルな公平性を提供するようには設計されておらず、また実際に提供してもいないという観察結果から生じたものである。図１３ａ、１３ｂ、および１３ｃはこの観察結果を示す。これらの図では、ネットワーク環境１００の各通信リンクは１０００Ｋｂｐｓの容量を有している。ホスト／ルータノード１０４、１０６、および１０８は各々、ホストノード１０２と可能な最大レートで通信しようとしている。ホスト／ルータノード１０４、１０６、および１０８は、複数のパスが使用可能な場合は、それらのトラフィックをその複数のパス上にルーティングする機能を備えている。
【００４６】
図１３ａでは、２つの中間ルータノード１１０および１１２が各々、ローカルなフローごとの公平性ポリシーを適用する。その結果、中央のホスト／ルータノード１０６は、他の２つのホスト／ルータノード１０４および１０８を犠牲にして不公平に大きな割合のネットワーク帯域幅を受け取ることになる。
【００４７】
リソース割り当てにおけるこの不公平性は、中央のホスト／ルータノード１０６だけが複数のデータパスにアクセスできるという事実から生じるのかもしれない。しかし、そのことが不公平性の原因ではない。単一パスルーティング割り当ては、結果的に図１３ｂのデータフローを生じることになり、割り当ては同様に不公平になる。
【００４８】
図１３ｂの不公平性は、単に右端のホスト／ルータノード１０８への帯域幅割り当てを５００Ｋｂｐｓに削減することによって解決できる。その結果、どのホスト／ルータノード１０４、１０６、１０８もすべて同一のスループットになるが、ネットワーク容量の望ましくない浪費という明白な犠牲を払うことになる。ホスト／ルータノード１０８のこの「処置（punishment）」は、他の２つのホスト／ルータノード１０４および１０６の利益にはならない。
【００４９】
図１３ｃは、このシナリオでの最適なルーティングおよび帯域幅割り当てを示す。ネットワークのスループットは図１３ａおよび図１３ｂの場合と同一であるが（１３ａ：５００Ｋｂｐｓ＋１０００＋５００＝２０００Ｋｂｐｓ、１３ｂ：５００Ｋｂｐｓ＋５００＋１０００＝２０００Ｋｂｐｓ、１３ｃ：６６７Ｋｂｐｓ＋６６７＋６６７＝２０００（丸めて））、図１３ｃでは各ホスト／ルータノード１０２、１０４、および１０６は、最大限の公平な帯域幅割り当てを受ける。この望ましいルーティングおよび帯域幅共有は、マルチパスルーティングとグローバルな帯域幅割り当ての両方を使用したことによる。これらは、ノード要求の公平メカニズムの主要な要素である。
【００５０】
直感的には、ノード要求の公平性は、ルーティングパス制約がまったく無い場合のグローバルな最大最小公平性と見なすことができる。その場合、（データフローではなく）ノードが共有／競争エンティティになる。言い換えると、ノード要求の公平なルーティングおよび帯域幅割り当ては、マルチパスルーティングを使用することができ、各ノードの最小スループットを最大にすることができる。それに対して、図１３ｂのルーティングおよび帯域幅割り当ては、単一パスルーティングの制約に従って各ノードの最小スループットを最大にするが、この制約のために、図１３ｃのより高い最小スループット（６６７Ｋｂｐｓ）が達成できなくなる。
【００５１】
（セクションＩＩＩ：ノード要求の公平性のマルチコモディティフローの実装）
ノード要求の公平なルーティングおよび帯域幅割り当て解決策を計算する１つの方法は、マルチコモディティフローに関する確立された方法を使用することである。マルチコモディティフロー問題では、いくつかの異なるコモディティが共有通信ネットワークを介して送信される。ネットワークは、（「エッジ」と呼ばれる）リンクによって接続された各ノードからなり、各リンクは、特定の容量を有している。各コモディティは、ソース、宛先、および要求のレベルを有する。ネットワークを移動するコモディティは複数の部分に分割することができ、任意のノードで再結合することができるが、コモディティのソースおよび宛先ノードを除けば、各ノードには同一量のコモディティが入り、出て行く必要がある。
【００５２】
マルチコモディティフロー問題は、様々な目的に使用することができる。２つの共通する目的は、フローの和の最大化、すなわち最大スループットフローと、最小フローの最大化、すなわち最大コンカレントフローである。ノード要求の公平問題をマルチコモディティフローにマップするために、通信ネットワークはグラフとして表され、１対のノード間の総通信フローは単一のコモディティとして表される。次いで、マルチコモディティフロー問題が、最大コンカレントフローについて解かれる。
【００５３】
マルチコモディティフロー問題を解くことは、大規模ネットワークを対象とするよりも小規模ネットワークを対象とする方がより実用的である。しかし、どのようなサイズのネットワークに対しても、マルチコモディティフロー解決策は、比較できる実際に達成可能な任意の結果に対して最適な条件を定義する。
【００５４】
マルチコモディティフロー問題は、線形計画として実際にモデル化することができる。線形計画の定数と変数をそれぞれ、以下の表１と表２に示す。
【００５５】
【表１】
2006527537.tif 000003
【００５６】
【表２】
2006527537.tif 000004
【００５７】
下記の線形計画法の制約の組（１）は、任意のエッジ上の任意のコモディティの有向フローが正でなければならないことを指定する。制約の組（２）は、任意のエッジ上のすべてのコモディティフローの和がそのエッジの容量を越えることができないことを指定する。制約の組（３）は、フローの維持を行う。すなわち、任意のコモディティについて、そのコモディティのソースおよび宛先ノードを除く、任意のノードに入る量と出て行く量は等しくなる。組（４）はコモディティｋの総フロー（total flow）を、コモディティｋのソースを出て行くコモディティｋの正味の量（net amount）として定義する。組（４）は線形計画の制約ではない。  
xi,j,k≧0    ∀k, ∀(i, j)∈E             (1)
【００５８】
【数１】
2006527537.tif 000005
【００５９】
【数２】
2006527537.tif 000006
【００６０】
【数３】
2006527537.tif 000007
【００６１】
補助の制約を付加することによって追加の機能を組み込むことができる。例えば、以下の分散制約によりリンクおよびノードの障害から保護される。  
【００６２】
【数４】
2006527537.tif 000008
【００６３】
上記の分散制約の第１のセットは、最大でも任意のフローの一部α１だけが単一のリンクに沿ってルーティングされることを保証する。これにより、リンク障害に対する回復力を追加する。第２のセットは、最大でも任意のフローの一部α２だけが特定のノードを通過してルーティングされることを保証することによって、ノード障害から保護する。
【００６４】
以下の線形計画の目的関数は、最大スループットフローを定義する。  
【００６５】
【数５】
2006527537.tif 000009
【００６６】
最大コンカレントフロー目的関数を指定することによって、線形計画は、割り当てられる各要求の部分を最大化する。これは簡略に、公平の定式化（fair formulation）と呼ばれる。この定式化において、λは、すべてのフローに割り当てられた要求の最小部分を与える。 
max λ
wkλ = fk    ∀k
【００６７】
リソース共有における絶対的な公平性（すなわち、等しい使用量）と最大使用率の間には、固有の競合関係が存在する。最大最小公平性は、この競合関係を線形計画法のＮ回の繰返しによって処理する。ここで、Ｎはネットワークにおけるノードの数である。各繰返しにおいて、線形計画は残りのリソースを公平に最大限利用しようと試みる。計算上の効率のために、本発明の各実施形態は、線形計画法の２回の繰返しだけを使用することができる。最初に、λに対する最大コンカレントフローを解き、次いで、どのコモディティもすべて、少なくともスループットλを受け取るという制約に従って最大スループットフローを解く。
【００６８】
【数６】
2006527537.tif 000010
【００６９】
これは、最大公平定式化（max-fair formulation）と呼ばれる。後のセクションＩＶのシミュレーションでは、最大公平定式化がネットワーク使用率を大幅に高めることが示される。
【００７０】
ネットワーク環境１００が無線リンクを含む場合、リンク干渉により１対の通信ノードが他の対の通信を妨げることが起こり得る。この場合、線形計画モデルは起こり得る干渉を反映するように修正することができる。１組の線形制約条件としてリンク干渉を定式化することによって、このモデルはマルチホップ無線ネットワークにまで拡大適用することができる。制約条件は以下のようになる。ここで、Sは非干渉リンクの最大集合のインデックスを示す。
【００７１】
【数７】
2006527537.tif 000011
【００７２】
図８ａのステップ８０６に関連して上で論じたように、ホストノードはその要求を（例えば、図５のノード間通信情報５００などのように）絶対レートで指定することができるが、制御ユニット２００はこれらの要求を、ホストノードの全ての要求に対するパーセンテージの形に正規化することができる。これらの正規化された要求は、このモデルの重みwkになる。正規化により重みが得られ、ノード要求の公平性が達成される。また、すべてのホストノードは、任意の数の通信フローに分割される同一の総集約要求（total aggregate demand）を有する。もちろん、ホストノードが要求を報告しない場合は、制御ユニット２００はそのホストノードのために帯域幅を予約することはない。
【００７３】
要求を正規化することによって、本モデルは容易に優先度処理に対応する。ホスト１０２のデータフローの重要性が２倍になった場合には、このモデルは、他のノードの要求を１００％に正規化したままで、単にホスト１０２の要求だけを２００％に正規化する。下記のセクションＩＶでは、このチューニングにより、本モデルが相対的に差別化されたサービスを実現できることが示される。
【００７４】
上記の線形計画モデルに関係する計算は、モデル化されるネットワークの規模とともに増大するが、非常に大規模なネットワークでも、そのネットワークをより小規模なネットワークの階層構造として取り扱うことによって合理的にモデル化することができる。上述のＩＳＰピアリングの場合は、階層化による単純化が適切である。なぜならば、構成要素である各フローが急速に出入りした場合でも、集約ＩＳＰ間トラフィックは長いタイムスケールでのみ変化するからである。ゲートウェイの向こうにある隣接ネットワークのシナリオでは、ゲートウェイを通過するデータフローだけをモデル化することによって、モデルを単純化することができる。
【００７５】
ネットワークを階層的に取り扱うことにより単純化したモデルでは、モデルに提示された下の階層レベルにおいて、トラフィックをどのように取り扱うかに関する問題が、未解決のまま残されている。この問題に対処する１つの方法は、ハイブリッドアプローチを用いることである。単純なモノリシックなアプローチでは、ノード要求の公平モデルは、各ノードの指定された要求に対してだけ帯域幅の使用を最適化する。ネットワークがフル負荷の状態になった場合、要求分配（demand distribution）において指定されていないどのようなトラフィックの急増も捨てられる。もちろん、モデルに提示された下の階層レベルにおけるどのようなトラフィックも、この指定されていない要求に含まれ、したがって捨てられる。単純に要求分配を再計算することは、好ましい解決策にはならない。なぜならば、特に要求の急増が短時間で終了する場合には、許容できない待ち時間が生じる可能性があるからである。このような急増に対処するために、ハイブリッドアプロ−チでは全体のネットワーク容量の一部だけにノード要求の公平モデルを適用する。残りの部分は急増のために取っておかれる。各ルータは、要求急増の間にこの予約された帯域幅を要求する必要が生じた場合には、従来のベストエフォートのルーティングを使用する。
【００７６】
ハイブリッドアプローチは、この特定のシナリオが示唆するよりも、より一般的に適用可能である。上記のモデルをこれらの「小さな」フローに適用した結果が、小さなフローをルーティングおよび帯域幅割り当て計算に含める計算コストより価値がないときはいつでも、ハイブリッドアプローチは有用になる。例えば、ネットワーク環境１００の多くは、これらの小さなフローを適切に提供するために十分な帯域幅を確保できる余裕を持つ。したがって、小さなフローを上記の計算に含めることによって提供される保証は、これらの環境における通信の品質にほとんど何も追加しないことになる。ハイブリッドアプローチをシミュレーションした結果は、下記のセクションＩＶにおいて示される。
【００７７】
ノード要求の公平メカニズムによって生成されたルーティングおよび帯域幅割り当てテーブルは望ましい特性を有しているので、これらのテーブルによって示唆されるパスに沿ってパケットを送信することは各個別のノードの最大の利益となる。このことは、最大公平メカニズムがあらゆるリンクを飽和させるという事実から簡単に導かれる。このメカニズムがsからdまでパスpに沿って送信するように示唆するどのような要求も、他のいずれかのパスに沿った場合にはより多くの輻輳に遭遇するはずである。
【００７８】
残念なことに、トポロジーによっては、ノードはその真の要求を不正に申告することによってその帯域幅割り当てを増大させることができる。その一例が図１４ａおよび図１４ｂに示されている。ホスト１０２および１０４がホスト１０６に通信しようとしており、それぞれのリンク容量が２００Ｋｂｐｓおよび１０００Ｋｂｐｓであると想定する。ホスト１０２および１０４の両方がその要求を正直に申告した場合には、最大最小公平ルーティング（この場合は最大公平ルーティングでもある）は図１４ａのように示される。残念なことに、ホスト１０４がその要求をホスト１０２だけに申告した場合には、帯域幅割り当ては図１４ｂに示したようになるはずである。この図では、ホスト１０４にはホスト１０６への追加の１００Ｋｂｐｓの帯域幅が与えられている。この不正申告の問題は、上述のゲートウェイシナリオでは、各ノードがただ１つの要求しか有していないので発生することはないが、より一般的な設定では不正申告は問題の原因になり得る。
【００７９】
この不正申告の問題に対処するために、制御ユニット２００は申告されたws,d（ｓからｄへの要求）をmin{ws,d, wd,s}で置き換える。この変更により、送信側と受信側の両方に割り当てられる帯域幅の有効な要求仕様は対称になる。この改良により、考慮中のもののようなある種のＤｏＳ攻撃に対する防御が提供される。
【００８０】
上で作成された線形計画モデルは、結果として非常に多くの変数、すなわちｎ個のノ−ド、ｍ本のエッジを有するネットワークに対してｎ（ｎ−１）ｍ個の変数を生じることになる。よりコンパクトな定式化により、ノード要求公平メカニズムのスケーラビリティが向上する。コンパクトな定式化では、共通の宛先を有する全てのコモディティを、複数のソースを有する単一のコモディティにまとめる。変数は異なるが結果は同一になる。コンパクトな定式化により、変数の最大数がｎｍにまで低減される。このコンパクトな定式化は、下記のセクションＩＶで示されるシミュレーションで使用される。
【００８１】
コンパクトな定式化に関する変数を、以下の表３に示す。表の後に最大公平線形計画のコンパクト版を示す。コンパクトな定式化では、分散制約条件は考慮されていない。なぜならば、この場合は共通の宛先を共有するエッジに沿ったフローが判別不能だからである。
【００８２】
【表３】
2006527537.tif 000012
【００８３】
【数８】
2006527537.tif 000013
【００８４】
（セクションＩＶ：シミュレーション結果）
このセクションでは、２種類のノード要求公平メカニズムをシミュレーションした結果を示す。第１の種類では公平目的関数（最大コンカレントフロー）を使用し、第２の種類では最大公平目的関数を使用する。シミュレーションされるネットワーク環境は１９６ノードまでの２次元グリッドからなり、すべてのリンク容量は１に設定されている。このシミュレーションの目的は、ノード要求公平メカニズムがネットワークのスループット、帯域幅共有の公平性、およびマルチパスルーティングの効率にどのような影響を与えるかを理解することである。このシミュレーションはまた、ノード要求公平性を用いて差別化サービスをどのように提供することができるかも調査する。どちらの種類のノード要求公平メカニズムも、インターネットで現在使用されている従来型の単一、最短パスルーティングと比較される。
【００８５】
このセクションでは、１対のノード間の集約されたトラフィックを「フロー」と呼ぶ。ネットワークスループットは、すべてのフロースループットの和として定義される。これは、最大スループットフローの目的関数を表す。
【００８６】
もちろん、すべてのリンク容量の和は、可能なスループットについての上限を形成する。この上限を実際に達成する通信パターンは望ましいものではない。なぜならば、その通信パターンは、図１５に示されるように、ノード対の大部分を枯渇させることになるからである。
【００８７】
リンク容量を浪費することは低スループットの明白な原因であり、明らかに望ましくないものである。低スループットの他の原因は、長いパスを通過するフローへの帯域幅の割り当てである。同一のエンドツーエンドスループットに対して、長いパスを有するフローは短いパスを有するフローが必要とするより、より多くのリンクからの容量を必要とする。長いパスフローが一連の短いパスフローとリンクを共有するとき、長いパスに割り振られる帯域幅の量を増加させることは、そのすべての短いパスフローに対する使用可能な帯域幅を減少させることになる。このことは全体のスループットを低下させるが、これは長いパスフローと短いパスフローの間の適切なポリシートレードオフに関係することであり、この結果は必ずしも望ましくないものとは限らない。
【００８８】
一様に（uniformly）分布したノード間要求という特別な場合に関して、図１６は最大可能スループット、最大公平スループット、公平スループット、および単一最短パス（ＳＳＰ）スループットを示す。複数の最短パスが存在する場合は、シミュレーションではランダムにその１つを選択する。ＳＳＰについては、各ルータは公平でローカルなフローごとの帯域幅共有ポリシーを適用する。この公平な割り当てが完全にはネットワークの容量を使用しないことは驚くには当たらない。長いパスフローと短いパスフローの間のトレードオフに関する上記の議論から、最大スループットと最大公平スループットの間のギャップが、最大割り当てによって短いパスフローに積極的に供給することに起因していることが理解できよう。
【００８９】
図１７は要求分布を変化させることによるスループットへの影響を示す。一様分布（uniform distribution）とスロープ２のジップ分布（a slope-2 Zipf distribution）の両方のノード対要求をシミュレーションする。（比較のために、ＡＯＬユーザからのサイト訪問の分布は、スロープ２．０７のジップ分布である）。使用可能な帯域幅の半分がノード要求公平メカニズムによって割り当てられ、使用可能な帯域幅の他の半分が一様要求（uniform demands）のＳＳＰを用いて割り当てられるように確保されているハイブリッドモードについてもシミュレーションを行う。
【００９０】
図１７は、公平および最大公平メカニズムの両方に関して、ジップ分布の結果が一様分布の結果に非常によく類似していることを示している。ジップ分布および一様分布の公平スループットはどちらも、ＳＳＰスループットよりわずかによい結果を示す。ハイブリッドの場合は最良のスループットが得られるが、これは（ジップでも一様でもない）要求分布の結果である。上で論じたゲートウェイシナリオに関して、ハイブリッド、最大公平の場合には、帯域幅の半分未満をゲートウェイリンクに割り当てる。ゲートウェイリンクは急速に飽和し、残りの帯域幅は高いスループットを生じる短いフローに充てられる。
【００９１】
図１８は、要求分布の変化のネットワーク使用率への影響をプロットしたものである。ジップ要求分配の裾の重い（heavy-tailed）特性により、指定された宛先で非常に不均一な分布が生じる可能性があり、最も人気のある宛先のまわりにボトルネックが生じて全体の使用率が低下する可能性がある。
【００９２】
ルーティングおよび帯域幅割り当てポリシーを評価する場合、達成されるスループットが唯一の関連する基準になる。より高いスループットであることは、要求満足度の低下を犠牲にしている場合には、必ずしも良いこととは限らない。上記のモデルでは、λがまさにその要求満足度の指標である。図１９ａおよび１９ｂは、様々な設定の下で達成されるλを比較したものである。平均フローを要求で除算したもの（平均λ）が、最大公平およびＳＳＰに対してプロットされている。ハイブリッドの結果は低レベルの要求満足度を示すが、それはハイブリッド要求分布が単一のゲートウェイに注目しているからである。一様公平メカニズム（uniform fair mechanism）はＳＳＰの要求満足度を平均で３８％高める。また、ジップ公平はＳＳＰを平均で２５％高める。最大公平メカニズムが平均λを何倍も改善することは驚くには当たらない。一様要求分布の下では、平均λはスループットに正確に比例する。ジップ要求の下では（図１９ｂに示されるように）、最大公平で割り当てられた帯域幅は、多くの小さな要求に著しく過剰に供給することによって、非常に大きな平均λをもたらす結果となる。
【００９３】
最大公平方式は最大最小公平性を完全には実施しない。最初の最大コンカレントフローを解決した後で不公平が生じる程度を、正規化されたノード要求は過剰供給されないという追加の制約、すなわち fk≦wk ∀k、が存在する場合と存在しない場合の両方でシミュレーションする。スループットおよび平均λを対象とした結果を、それぞれ図２０ａおよび２０ｂに示す。驚くべき結果は、これらの過剰供給制約に従う最大公平スループットが、ほぼ公平スループットのレベルまで低下することである。したがって、過剰供給制約だけでも、スループットを最大にする際に生じる短いパスへの偏りの多くを排除するのに十分だということになる。平均λにノードの数を乗算すると一様分布要求のスループットに等しくなるので、図２０ｂの平均λのプロットは同じデータに関する異なる視点を示す。図２０ｂでは、過剰供給制約により、公平な定式化での成長をより密接に追跡する最大公平定式化での成長率がもたらされる。このことは、過剰供給制約によって短いパスへの偏りが十分除去されるという他の証拠である。
【００９４】
最短の単一パスルーティングは、リンクメトリックに従って任意のパケットによる待ち時間を最小にする。マルチコモディティフローの定式化は、パスの長さに関する上限をまったく含まない。直感的には、各マルチパスの長さは対応する最短パスの長さに近づくことが予想される。なぜならば、マルチパスが多くの不要なリンクを使用した場合、他のフローが使用できる帯域幅を減少させることになり、おそらくはグローバルな最適状態にはおよばない帯域幅割り当てを生じる結果となるからである。これは、スループット最大化の目的関数とは異なる目的関数の下で短いパスへの偏りになる。
【００９５】
マルチパスルーティング中にパケットが通る平均パス長は、ｉからｊに流れ、ソースがｓで宛先がｄのフローを表す変数｛xi,j,s,d｝を使用して定義される。fs,dはソースｓから宛先ｄへの総フローを示すものとする。このとき、ｓからｄへの平均パス長は、
【００９６】
【数９】
2006527537.tif 000014
【００９７】
となる。ｓからｄへの距離で除算することによってマルチパスのストレッチ、すなわち、平均パス長が最短の単一パスより長くなる倍率が与えられる。一様要求分布の仮定を用いた２５ノードまでのグリッド上でのシミュレーションでは、ストレッチは常に１である。マルチパスルーティングは追加の待ち時間を招くものではない。また、マルチパスルーティングは短いパスへの偏りに関する直感を確認するものである。
【００９８】
上記のセクションＩＩＩでは、分散制約の追加について論じた。このセクションＩＶに示されたシミュレーション結果はそのような分散制約に基づくものではないが、マルチパスはいずれにしても完全に分散する。マルチパスの分散（dispersion）を評価するために平均分散メトリックを定義する。ｓとｄの間のフローの分散（variance）を、
【００９９】
【数１０】
2006527537.tif 000015
【０１００】
とする。次に、ｓからｄへの平均分散を、ｓとｄの間の距離をVars,dで除算したものとする。この定義に対するある直感を与えるために、マルチパスが単純にｋ個の分離された最短パスの各々に沿ってトラフィックの１／ｋ部分をルーティングしているものと想定する。このとき、平均分散は単にｋとなるはずである。
【０１０１】
図２１は、一様要求の６×６グリッドトポロジー上のフローに対する平均分散メトリックの分布をプロットしたものである。半分を越えるフローが、２を超える平均分散を有している。このことは、そのフローのマルチパスに沿ったあるリンクに障害があったとしても、フローの多くが重要なスループットを継続するはずであることを示唆する。
【０１０２】
エンドホスト間のサービスは、それらの要求仕様によって差別化することができる。シミュレーションのために、２５ノードグリッドトポロジーの中央のノードを優位ノードとして選択し、そのノードの要求が他のノードの要求より２倍重要だと見なされるものとする。したがって、この優位ノードとの間で通信される要求は２倍される。シミュレーションによると、通常ノードのλは０．４０から０．３６にわずかに減少するが、優位ノードのλは０．４０から０．７２に増加し、１．８倍の増加になる。これはまさしく望ましい結果である。すなわち、優位ノードは通常ノードの２倍の帯域幅を受け取ることになり、結果として要求仕様が正しく反映されたことになる。さらに、通常のノードの帯域幅は、優位ノードを受け入れるためにほんのわずか減少するだけである。優位ノードの数を増加させたシミュレーションでは、そのことにより通常ノードの帯域幅および全体ネットワークのスループットがどの程度減少するのかを示す。図２２ａおよび２２ｂは、優位ノードの数が増加するに伴い、優位ノードと通常ノードの要求満足レベルはどちらも徐々に低下するが、優位ノードは常に通常ノードの２倍の帯域幅を受け取ることを示している。したがって、本発明の方法は、単に要求分配を変化させるだけで差別化サービスをサポートすることができる。
【０１０３】
本発明の原理を適用できる多くの可能な実施形態を考慮して、各図面に即した本明細書に記載の諸実施形態が例示のためだけのものであり、本発明の範囲を制限するものと見なすべきではないことを理解されたい。例えば、当業者ならば、本発明の趣旨を逸脱することなく例示の実施形態を拡張して、階層および混合アーキテクチャのネットワークを取り扱うことができることが理解されよう。本発明はソフトウェアモジュールまたはコンポーネントに関して記載されているが、当業者ならば、それらがハードウェアコンポーネントによって均等的に置き換え可能であることが理解されよう。したがって、本明細書に記載の本発明は、このような実施形態のすべてを添付の特許請求の範囲およびその均等物の範囲の中に含むことができることを企図したものである。
【図面の簡単な説明】
【０１０４】
【図１】最短パスルーティングがどのようにして無用なルーティングボトルネックの原因になり得るかを示す通信環境の構成図である。
【図２】本発明の実施形態をサポートする例示的アーキテクチャの構成図である。
【図３】本発明をサポートする例示的コンピュータシステムを一般的に示す概略図である。
【図４】図２のアーキテクチャのホストネットワークノードによって使用できる例示的方法の流れ図である。
【図５】図２のアーキテクチャのホストネットワークノードによって提供されるノード間通信情報のデータ構造図である。
【図６ａ】図２のアーキテクチャのルータネットワークノードによって使用できる例示的方法の流れ図である。
【図６ｂ】図２のアーキテクチャのルータネットワークノードによって使用できる例示的方法の流れ図である。
【図７】図２のアーキテクチャのルータネットワークノードによって提供されるネットワークトポロジー情報のデータ構造図である。
【図８ａ】図２のアーキテクチャの制御ユニットによって使用できる例示的方法の流れ図である。
【図８ｂ】図２のアーキテクチャの制御ユニットによって使用できる例示的方法の流れ図である。
【図９】他の３つのホストネットワークノードにデータを送信する第１のホストネットワークノードを含む例示的通信環境のフローレート図である。
【図１０】図９の環境のあるホストネットワークノードに対して生成される例示的マルチパスルーティングテーブルのデータ構造図である。
【図１１】ルータネットワークノードに着信する集約データフローを示すフローレート図である。
【図１２】図１１の中央のルータネットワークノードに対して生成された例示的帯域幅割り当てテーブルのデータ構造図である。
【図１３ａ】ローカルなフローごとの公平性ポリシーを使用した例示的通信システムのフローレート図である。
【図１３ｂ】単一パスルーティングポリシーを使用した、図１３ａと同一の通信システムのフローレート図である。
【図１３ｃ】ノード要求公平性ポリシーを使用した、図１３ａと同一の通信システムのフローレート図である。
【図１４ａ】ホストネットワークノードがその真の要求を報告する場合の、例示的通信環境のフローレート図である。
【図１４ｂ】あるホストネットワークノードがその要求を不正に報告した場合の、図１４ａと同一の環境のフローレート図である。
【図１５】最大の可能なスループットを達成する帯域幅割り当てポリシーによって引き起こされるノード対の帯域幅枯渇状況をグラフに示した図である。
【図１６】様々な帯域幅割り当てポリシーによって達成されるスループットをグラフに示した図である。
【図１７】要求の分配の関数としてスループットをグラフに示した図である。
【図１８】要求の分配の関数として使用可能な帯域幅の使用率をグラフに示した図である。
【図１９ａ】様々な条件およびポリシーの下での帯域幅要求満足度をグラフに示した図である。
【図１９ｂ】ジップ要求の下で、最大公平帯域幅割り当てポリシーが小さな要求にどの程度過剰供給し得るかを示す図である。
【図２０ａ】正規化されたノード要求は過剰に供給されないという制約を含む場合とその制約を含まない場合について、最大公平帯域幅割り当てポリシーによって達成されるスループットをグラフ表示した図である。
【図２０ｂ】図２０ａと同一の制約を含む場合とその制約を含まない場合について、帯域幅要求満足度をグラフ表示した図である。
【図２１】一様要求のフローに対し、本発明の方法によって達成可能な平均マルチパス分散の分布を棒グラフで示した図である。
【図２２ａ】いくつかのノードの要求を満たすことが他のノードの要求を満たすことより２倍重要だと考えられるときの、帯域幅要求満足度をグラフ表示した図である。
【図２２ｂ】図２２ａと同一条件の下でのスループットをグラフ表示した図である。
【図１】
2006527537.tif 000016
【図２】
2006527537.tif 000017
【図３】
2006527537.tif 000018
【図４】
2006527537.tif 000019
【図５】
2006527537.tif 000020
【図６ａ】
2006527537.tif 000021
【図６ｂ】
2006527537.tif 000022
【図７】
2006527537.tif 000023
【図８ａ】
2006527537.tif 000024
【図８ｂ】
2006527537.tif 000025
【図９】
2006527537.tif 000026
【図１０】
2006527537.tif 000027
【図１１】
2006527537.tif 000028
【図１２】
2006527537.tif 000029
【図１３ａ】
2006527537.tif 000030
【図１３ｂ】
2006527537.tif 000031
【図１３ｃ】
2006527537.tif 000032
【図１４ａ】
2006527537.tif 000033
【図１４ｂ】
2006527537.tif 000034
【図１５】
2006527537.tif 000035
【図１６】
2006527537.tif 000036
【図１７】
2006527537.tif 000037
【図１８】
2006527537.tif 000038
【図１９ａ】
2006527537.tif 000039
【図１９ｂ】
2006527537.tif 000040
【図２０ａ】
2006527537.tif 000041
【図２０ｂ】
2006527537.tif 000042
【図２１】
2006527537.tif 000043
【図２２ａ】
2006527537.tif 000044
【図２２ｂ】
2006527537.tif 000045
【国際調査報告】
2006527537.tif 000046
2006527537.tif 000047