(57)【特許請求の範囲】
【請求項１】
パケットフォワーディング方法であって、
リンクの総数が2の整数乗であると決定するステップであって、前記リンクの総数が、追加された仮想的なリンクの数とデータパケットをフォワーディングするための実際のリンクの数との総和である、ステップと、
前記データパケットのハッシュ値を計算し、前記ハッシュ値を前記リンクの総数で割った余りを計算するステップと、
前記ハッシュ値を前記リンクの総数で割った前記余りが仮想的なリンクに対応する場合、前記データパケットの別のハッシュ値を計算し、余りを計算する前記ステップに戻り、前記データパケットのハッシュ値を前記リンクの総数で割った余りが実際のリンクに対応するまで上記の動作を循環的に実行し、前記実際のリンク上で前記データパケットをフォワーディングするか、または前記ハッシュ値を前記リンクの総数で割った前記余りが仮想的なリンクに対応する場合、前記データパケットの前記ハッシュ値を前記実際のリンクの数で割った余りを計算し、前記ハッシュ値を前記実際のリンクの前記数で割った前記余りに対応する実際のリンク上で前記データパケットをフォワーディングするステップと、
前記ハッシュ値を前記リンクの総数で割った前記余りが実際のリンクに対応する場合、前記実際のリンク上で前記データパケットをフォワーディングするステップとを含む、方法。
【請求項２】
前記データパケットのハッシュ値を計算する前記ステップが、
前記データパケットからフィールドの一部を抽出することと、
フィールドの抽出された一部によって形成されたバイトシーケンスに対して巡回冗長検査を実行して前記ハッシュ値を計算することとを含む請求項1に記載の方法。
【請求項３】
パケットフォワーディング方法であって、
リンクの総数が2の整数乗であると決定するステップであって、前記リンクの総数が、追加された仮想的なリンクの数とデータパケットをフォワーディングするための実際のリンクを拡張することによって形成された仮想的なサブリンクの数との総和である、ステップと、
前記データパケットのハッシュ値を計算し、前記ハッシュ値を前記リンクの総数で割った余りを計算するステップと、
前記ハッシュ値を前記リンクの総数で割った前記余りが仮想的なリンクに対応する場合、前記データパケットの別のハッシュ値を計算し、余りを計算する前記ステップに戻り、前記データパケットのハッシュ値を前記リンクの総数で割った余りが実際のリンクの仮想的なサブリンクのうちの1つに対応するまで上記の動作を循環的に実行し、前記実際のリンク上で前記データパケットをフォワーディングするか、または前記ハッシュ値を前記リンクの総数で割った前記余りが仮想的なリンクに対応する場合、前記データパケットのハッシュ値を仮想的なサブリンクの前記数で割った余りを計算し、前記ハッシュ値を仮想的なサブリンクの前記数で割った前記余りに対応する仮想的なサブリンクを形成するために拡張された実際のリンク上で前記データパケットをフォワーディングするステップとを含む、方法。
【請求項４】
前記ハッシュ値を前記リンクの総数で割った前記余りが前記仮想的なサブリンクのうちの1つに対応する場合、前記仮想的なサブリンクのうちの前記1つを形成するために拡張された前記実際のリンク上で前記データパケットをフォワーディングするステップをさらに含む請求項3に記載の方法。
【請求項５】
前記リンクの総数が2の整数乗であると決定する前記ステップの前に、
データパケットをフォワーディングするための前記実際のリンクの各々を拡張することによって形成されるべき仮想的なサブリンクの数を決定するステップと、
前記仮想的なサブリンクの決定された数に前記実際のリンクの数を掛けて積を取得し、2の整数乗を得るために前記積に足される加算する値を決定するステップと、
前記加算する値が予め設定された値未満である場合、前記加算する値を追加されるべき仮想的なリンクの数として使用し、前記加算する値が予め設定された値を超える場合、前記実際のリンクの各々を拡張することによって形成されるべき仮想的なサブリンクの別の数を決定し、仮想的なサブリンクの前記別の数に関して加算する値を決定するステップとをさらに含み、
前記リンクの総数が2の整数乗であると決定する前記ステップが、前記リンクの総数が前記積と前記加算する値との総和であると決定することを含む請求項3または4に記載の方法。
【請求項６】
前記データパケットのハッシュ値を計算する前記ステップが、
前記データパケットからフィールドの一部を抽出することと、
フィールドの抽出された一部によって形成されたバイトシーケンスに対して巡回冗長検査を実行して前記ハッシュ値を計算することとを含む請求項3または4に記載の方法。
【請求項７】
リンクの総数が2の整数乗であると決定するように構成されたリンク決定ユニットであって、前記リンクの総数が、追加された仮想的なリンクの数とデータパケットをフォワーディングするための実際のリンクの数との総和である、リンク決定ユニットと、
前記データパケットのハッシュ値を計算し、前記ハッシュ値を前記リンクの総数で割った余りを計算するように構成された余り計算ユニットであって、前記リンクの総数が、前記リンク決定ユニットによって決定される、余り計算ユニットと、
前記余り計算ユニットによって取得された、ハッシュ値を前記リンクの総数で割った余りが仮想的なリンクに対応する場合、前記データパケットの別のハッシュ値の計算および前記別のハッシュ値を前記リンクの総数で割った余りの計算を前記余り計算ユニットに通知するように構成された通知ユニット、ならびに前記余り計算ユニットおよび前記通知ユニットが、前記データパケットのハッシュ値を前記リンクの総数で割った余りが実際のリンクに対応するまで上記の動作を循環的に実行するとき、実際のリンク上で前記データパケットをフォワーディングするように構成されたフォワーディングユニット、または前記余り計算ユニットによって取得された、ハッシュ値を前記リンクの総数で割った余りが仮想的なリンクに対応する場合、前記データパケットの前記ハッシュ値を前記実際のリンクの前記数で割った余りの計算を前記余り計算ユニットに通知するように構成された通知ユニット、ならびに前記ハッシュ値を前記実際のリンクの数で割った前記余りに対応する実際のリンク上で前記データパケットをフォワーディングするように構成されたフォワーディングユニットであって、前記余りが、前記余り計算ユニットによって取得される、フォワーディングユニットとを含み、
前記フォワーディングユニットが、前記余り計算ユニットによって取得された、前記ハッシュ値を前記リンクの総数で割った前記余りが実際のリンクに対応する場合、前記実際のリンク上で前記データパケットをフォワーディングするようにさらに構成される、パケットフォワーディングデバイス。
【請求項８】
前記余り計算ユニットが、前記データパケットからフィールドの一部を抽出し、フィールドの抽出された一部によって形成されたバイトシーケンスに対して巡回冗長検査を実行して前記ハッシュ値を計算するように構成される請求項7に記載のデバイス。
【請求項９】
リンクの総数が2の整数乗であると決定するように構成されたリンク決定ユニットであって、前記リンクの総数が、追加された仮想的なリンクの数とデータパケットをフォワーディングするための実際のリンクを拡張することによって形成された仮想的なサブリンクの数との総和である、リンク決定ユニットと、
前記データパケットのハッシュ値を計算し、前記ハッシュ値を前記リンクの総数で割った余りを計算するように構成された余り計算ユニットであって、前記リンクの総数が、前記リンク決定ユニットによって決定される、余り計算ユニットと、
前記余り計算ユニットによって取得された、前記ハッシュ値を前記リンクの総数で割った前記余りが仮想的なリンクに対応する場合、前記データパケットの別のハッシュ値の計算および前記別のハッシュ値を前記リンクの総数で割った余りの計算を前記余り計算ユニットに通知するように構成された通知ユニット、ならびに前記余り計算ユニットおよび前記通知ユニットが、前記データパケットのハッシュ値を前記リンクの総数で割った余りが実際のリンクの仮想的なサブリンクのうちの1つに対応するまで上記の動作を循環的に実行するとき、前記実際のリンク上で前記データパケットをフォワーディングするように構成されたフォワーディングユニット、または前記余り計算ユニットによって取得された、前記ハッシュ値を前記リンクの総数で割った前記余りが仮想的なリンクに対応するとき、前記データパケットの前記ハッシュ値を仮想的なサブリンクの前記数で割った余りの計算を前記余り計算ユニットに通知するように構成された通知ユニット、ならびに前記ハッシュ値を仮想的なサブリンクの前記数で割った前記余りに対応する仮想的なサブリンクを形成するために拡張された実際のリンク上で前記データパケットをフォワーディングするように構成されたフォワーディングユニットであって、前記余りが、前記余り計算ユニットによって取得される、フォワーディングユニットとを含む、パケットフォワーディングデバイス。
【請求項１０】
前記フォワーディングユニットが、前記余り計算ユニットによって取得された、前記ハッシュ値を前記リンクの総数で割った前記余りが前記仮想的なサブリンクのうちの1つに対応する場合、前記仮想的なサブリンクのうちの前記1つに対応する実際のリンク上で前記データパケットをフォワーディングするようにさらに構成される請求項9に記載のデバイス。
【請求項１１】
前記リンク決定ユニットが、データパケットをフォワーディングするための前記実際のリンクの各々を拡張することによって形成されるべき仮想的なサブリンクの前記数を決定し、前記仮想的なサブリンクの決定された数に実際のリンクの数を掛けて積を取得し、2の整数乗を得るために前記積に足される加算する値を決定し、前記加算する値が予め設定された値未満である場合、前記加算する値を追加されるべき仮想的なリンクの数として用い、前記リンクの総数が前記積と前記加算する値との総和であると決定し、前記加算する値が予め設定された値を超える場合、前記実際のリンクの各々を拡張することによって形成されるべき仮想的なサブリンクの別の数の決定に戻り、前記仮想的なサブリンクの前記別の数に関して前記加算する値を決定するようにさらに構成される請求項9または10に記載のデバイス。
【請求項１２】
前記余り計算ユニットが、前記データパケットからフィールドの一部を抽出し、フィールドの抽出された一部によって形成されたバイトシーケンスに対して巡回冗長検査を実行して前記ハッシュ値を計算するように構成される請求項9または10に記載のデバイス。
【請求項１３】
第1の通信デバイスおよび第2の通信デバイスを含み、前記第1の通信デバイスと前記第2の通信デバイスとの間に複数の実際のリンクが存在し、
前記第1の通信デバイスが、請求項7から12のいずれか一項に記載のパケットフォワーディングデバイスであるパケットフォワーディングシステム。
【請求項１４】
第1の通信デバイスおよび複数の第2の通信デバイスを含み、前記第1の通信デバイスと前記複数の第2の通信デバイスの各々との間に1つの実際のリンクが存在し、
前記第1の通信デバイスが、請求項7から12のいずれか一項に記載のパケットフォワーディングデバイスであるパケットフォワーディングシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、中華人民共和国の国家知識産権局に2014年3月27日に出願した、「PACKET FORWARDING METHOD, SYSTEM AND DEVICE」と題した中国特許出願第201410120857.7号の優先権を主張するものであり、この特許出願の内容は、その全体が参照により本明細書に組み込まれる。
【０００２】
本発明は、通信テクノロジーの分野に関し、特に、パケットフォワーディング方法、パケットフォワーディングシステム、およびパケットフォワーディングデバイスに関する。
【背景技術】
【０００３】
クラウドテクノロジーの発展により、送信され、処理されるデータの量がますます大きくなり、ネットワークデバイスおよびユーザデバイスによって必要とされる帯域幅が増やされる。ユーザデバイスの必要を満たすためにネットワーク帯域幅をどのようにして改善すべきかが、解決されるべき緊急の問題になる。現在、ネットワーク帯域幅は、主として以下の2つの方法で改善される。第1の方法においては、単一の物理リンクの処理能力が、たとえば、より優れた処理性能を有するチップおよびより優れた送信性能を有する光ファイバを使用して改善される。第2の方法においては、全体の処理および送信能力を改善するために、負荷が複数の低速な物理デバイスおよび複数の低速なリンクによって分担される。第1の方法と比較して、第2の方法は、信頼性および拡張性の点で明らかな利点を有する。したがって、第2の方法を使用するテクノロジーは、現在のネットワークに広く適用されており、「ロードシェアリング(Load Sharing、LS)」または「ロードバランシング(Load Balancer、LB)」と呼ばれる可能性がある。
【０００４】
従来技術のロードシェアリング方法によれば、データパケットを送信するためのリンクが、データパケットの情報の一部に対して特定の計算を実行すること、たとえば、情報の一部のハッシュ値を実際の物理リンクの数で割った数に対して剰余演算を実行することによって決定される。しかし、この方法においては、実際の物理リンクの数が2の整数乗でない場合、「ロードシェアリング」は、剰余演算が原因で大きな偏りを持ち、したがって、トラフィックが、一様に分散され得ない。トラフィックが一様に分散されない場合、たとえば、リンクが負荷で一杯になり、トラフィックが増やされ続ける場合、リンク上のパケットが失われる可能性があり、それによって、サービスに影響を与える。
【発明の概要】
【課題を解決するための手段】
【０００５】
トラフィックを一様に分散し、サービスへの影響を減らすために、本発明の実施形態によってパケットフォワーディング方法、パケットフォワーディングシステム、およびパケットフォワーディングデバイスが提供される。
【０００６】
第1の態様においては、
リンクの総数が2の整数乗であると決定するステップであって、リンクの総数が、追加された仮想的なリンクの数とデータパケットをフォワーディングするための実際のリンクの数との総和である、ステップと、
データパケットのハッシュ値を計算し、ハッシュ値をリンクの総数で割った余りを計算するステップと、
ハッシュ値をリンクの総数で割った余りが仮想的なリンクに対応する場合、データパケットの別のハッシュ値を計算し、余りを計算するステップに戻り、データパケットのハッシュ値をリンクの総数で割った余りが実際のリンクに対応するまで上記の動作を循環的に実行し、実際のリンク上でデータパケットをフォワーディングするか、またはハッシュ値をリンクの総数で割った余りが仮想的なリンクに対応する場合、データパケットのハッシュ値を実際のリンクの数で割った余りを計算し、ハッシュ値を実際のリンクの数で割った余りに対応する実際のリンク上でデータパケットをフォワーディングするステップと、
ハッシュ値をリンクの総数で割った余りが実際のリンクに対応する場合、実際のリンク内でデータパケットをフォワーディングするステップとを含むパケットフォワーディング方法が、本発明の実施形態によって提供される。
【０００７】
本発明の実施形態の第1の態様の第1のあり得る実装においては、データパケットのハッシュ値を計算するステップが、
データパケットからフィールドの一部を抽出することと、
フィールドの抽出された一部によって形成されたバイトシーケンスに対して巡回冗長検査を実行してハッシュ値を計算することとを含む可能性がある。
【０００８】
第2の態様においては、
リンクの総数が2の整数乗であると決定するように構成されたリンク決定ユニットであって、リンクの総数が、追加された仮想的なリンクの数とデータパケットをフォワーディングするための実際のリンクの数との総和である、リンク決定ユニットと、
データパケットのハッシュ値を計算し、ハッシュ値をリンクの総数で割った余りを計算するように構成された余り計算ユニットであって、リンクの総数が、リンク決定ユニットによって決定される、余り計算ユニットと、
余り計算ユニットによって取得された、ハッシュ値をリンクの総数で割った余りが仮想的なリンクに対応する場合、データパケットの別のハッシュ値の計算および別のハッシュ値をリンクの総数で割った余りの計算を余り計算ユニットに通知するように構成された通知ユニット、ならびに余り計算ユニットおよび通知ユニットが、データパケットのハッシュ値をリンクの総数で割った余りが実際のリンクに対応するまで上記の動作を循環的に実行するとき、実際のリンク上でデータパケットをフォワーディングするように構成されたフォワーディングユニット、または
余り計算ユニットによって取得された、ハッシュ値をリンクの総数で割った余りが仮想的なリンクに対応する場合、余り計算ユニットがデータパケットのハッシュ値を実際のリンクの数で割った余りを計算することを通知するように構成された通知ユニット、ならびにハッシュ値を実際のリンクの数で割った余りに対応する実際のリンク上でデータパケットをフォワーディングするように構成されたフォワーディングユニットであって、余りが、余り計算ユニットによって取得される、フォワーディングユニットとを含み、
フォワーディングユニットが、余り計算ユニットによって取得された、ハッシュ値をリンクの総数で割った余りが実際のリンクに対応する場合、実際のリンク上でデータパケットをフォワーディングするようにさらに構成される、パケットフォワーディングデバイスが、本発明の実施形態によって提供される。
【０００９】
本発明の実施形態の第2の態様の第1のあり得る実装において、余り計算ユニットは、データパケットからフィールドの一部を抽出し、フィールドの抽出された一部によって形成されたバイトシーケンスに対して巡回冗長検査を実行してハッシュ値を計算するように構成される可能性がある。
【００１０】
第3の態様においては、
リンクの総数が2の整数乗であると決定するステップであって、リンクの総数が、追加された仮想的なリンクの数とデータパケットをフォワーディングするための実際のリンクを拡張することによって形成された仮想的なサブリンクの数との総和である、ステップと、
データパケットのハッシュ値を計算し、ハッシュ値をリンクの総数で割った余りを計算するステップと、
ハッシュ値をリンクの総数で割った余りが仮想的なリンクに対応する場合、データパケットの別のハッシュ値を計算し、余りを計算するステップに戻り、データパケットのハッシュ値をリンクの総数で割った余りが実際のリンクの仮想的なサブリンクのうちの1つに対応するまで上記の動作を循環的に実行し、実際のリンク上でデータパケットをフォワーディングするステップ、または
ハッシュ値をリンクの総数で割った余りが仮想的なリンクに対応する場合、データパケットのハッシュ値を仮想的なサブリンクの数で割った余りを計算し、ハッシュ値を仮想的なサブリンクの数で割った余りに対応する仮想的なサブリンクを形成するために拡張された実際のリンク上でデータパケットをフォワーディングするステップとを含むパケットフォワーディング方法が、本発明の実施形態によって提供される。
【００１１】
本発明の実施形態の第3の態様の第1のあり得る実装においては、方法が、
リンクの総数をハッシュ値で割った余りが仮想的なサブリンクのうちの1つに対応する場合、仮想的なサブリンクのうちの1つを形成するために拡張された実際のリンク上でデータパケットをフォワーディングするステップをさらに含む可能性がある。
【００１２】
本発明の実施形態の第3の態様または第3の態様の第1のあり得る実装を参照すると、本発明の実施形態の第3の態様の第2のあり得る実装においては、リンクの総数が2の整数乗であると決定するステップの前に、方法が、
データパケットをフォワーディングするための実際のリンクの各々を拡張することによって形成されるべき仮想的なサブリンクの数を決定するステップと、
仮想的なサブリンクの決定された数に実際のリンクの数を掛けて積を取得し、2の整数乗を得るために積に足される加算する値を決定するステップと、
加算する値が予め設定された値未満である場合、加算する値を追加されるべき仮想的なリンクの数として使用し、加算する値が予め設定された値を超える場合、実際のリンクの各々を拡張することによって形成されるべき仮想的なサブリンクの別の数を決定することに戻り、仮想的なサブリンクの別の数に関して加算する値を決定するステップとをさらに含む可能性があり、
リンクの総数が2の整数乗であると決定するステップが、リンクの総数が積と加算する値との総和であると決定することを含む可能性がある。
【００１３】
本発明の実施形態の第3の態様または第3の態様の第1のあり得る実装を参照すると、本発明の実施形態の第3の態様の第3のあり得る実装においては、データパケットのハッシュ値を計算するステップが、
データパケットからフィールドの一部を抽出することと、
フィールドの抽出された一部によって形成されたバイトシーケンスに対して巡回冗長検査を実行してハッシュ値を計算することとを含む可能性がある。
【００１４】
第4の態様においては、
リンクの総数が2の整数乗であると決定するように構成されたリンク決定ユニットであって、リンクの総数が、追加された仮想的なリンクの数とデータパケットをフォワーディングするための実際のリンクを拡張することによって形成された仮想的なサブリンクの数との総和である、リンク決定ユニットと、
データパケットのハッシュ値を計算し、ハッシュ値をリンクの総数で割った余りを計算するように構成された余り計算ユニットであって、リンクの総数が、リンク決定ユニットによって決定される、余り計算ユニットと、
余り計算ユニットによって取得された、ハッシュ値をリンクの数で割った余りが仮想的なリンクに対応する場合、データパケットの別のハッシュ値の計算および別のハッシュ値をリンクの総数で割った余りの計算を余り計算ユニットに通知するように構成された通知ユニット、ならびに余り計算ユニットおよび通知ユニットが、データパケットのハッシュ値をリンクの総数で割った余りが実際のリンクの仮想的なサブリンクのうちの1つに対応するまで上記の動作を循環的に実行するとき、実際のリンク上でデータパケットをフォワーディングするように構成されたフォワーディングユニット、または
余り計算ユニットによって取得された、ハッシュ値をリンクの数で割った余りが仮想的なリンクに対応するとき、データパケットのハッシュ値を仮想的なサブリンクの数で割った余りの計算を余り計算ユニットに通知するように構成された通知ユニット、ならびにハッシュ値を仮想的なサブリンクの数で割った余りに対応する仮想的なサブリンクを形成するために拡張された実際のリンク上でデータパケットをフォワーディングするように構成されたフォワーディングユニットであって、余りが、余り計算ユニットによって取得される、フォワーディングユニットとを含むパケットフォワーディングデバイスが、本発明の実施形態によって提供される。
【００１５】
本発明の実施形態の第4の態様の第1のあり得る実装においては、フォワーディングユニットが、余り計算ユニットによって取得された、ハッシュ値をリンクの総数で割った余りが仮想的なサブリンクのうちの1つに対応する場合、仮想的なサブリンクのうちの1つに対応する実際のリンク上でデータパケットをフォワーディングするようにさらに構成される可能性がある。
【００１６】
本発明の実施形態の第4の態様または第4の態様の第1のあり得る実装を参照すると、本発明の実施形態の第4の態様の第2のあり得る実装においては、リンク決定ユニットが、データパケットをフォワーディングするための実際のリンクの各々を拡張することによって形成された仮想的なサブリンクの数を決定し、仮想的なサブリンクの決定された数に実際のリンクの数を掛けて積を取得し、2の整数乗を得るために積に足される加算する値を決定し、加算する値が予め設定された値未満である場合、加算する値を追加されるべき仮想的なリンクの数として用い、リンクの総数が積と加算する値との総和であると決定し、加算する値が予め設定された値を超える場合、実際のリンクの各々を拡張することによって形成される仮想的なサブリンクの別の数の決定に戻り、仮想的なサブリンクの別の数に関して加算する値を決定するようにさらに構成される可能性がある。
【００１７】
本発明の実施形態の第4の態様または第4の態様の第1のあり得る実装を参照すると、本発明の実施形態の第4の態様の第3のあり得る実装においては、余り計算ユニットが、データパケットからフィールドの一部を抽出し、フィールドの抽出された一部によって形成されたバイトシーケンスに対して巡回冗長検査を実行してハッシュ値を計算するように構成される可能性がある。
【００１８】
第5の態様においては、第1の通信デバイスおよび第2の通信デバイスを含み、第1の通信デバイスと第2の通信デバイスとの間に複数の実際のリンクが存在し、
第1の通信デバイスが、本発明の実施形態の第2の態様、または第2の態様の第1のあり得る実装、または本発明の実施形態の第4の態様、または第4の態様の第1から第3までのあり得る実装のいずれか1つによるパケットフォワーディングデバイスであるパケットフォワーディングシステムが、本発明の実施形態によって提供される。
【００１９】
第6の態様においては、パケットフォワーディングシステムが、本発明の実施形態によって提供され、パケットフォワーディングシステムは、第1の通信デバイスおよび複数の第2の通信デバイスを含み、第1の通信デバイスと複数の第2の通信デバイスの各々との間に1つの実際のリンクが存在し、
第1の通信デバイスは、本発明の実施形態の第2の態様、または第2の態様の第1のあり得る実装、または本発明の実施形態の第4の態様、または第4の態様の第1から第3までのあり得る実装のいずれか1つによるパケットフォワーディングデバイスである。
【００２０】
本発明の実施形態の1つの場合では、通信デバイスが、データパケットのハッシュ値をリンクの決定された総数で割った余りを計算する。リンクの総数は、2の整数乗であり、追加された仮想的なリンクの数とデータパケットをフォワーディングするための実際のリンクの数との総和である可能性がある。ハッシュ値をリンクの総数で割った余りが仮想的なリンクに対応する場合、データパケットの別のハッシュ値が計算され、プロセスは別のハッシュ値およびリンクの総数に基づいて余りを計算するステップに戻され、データパケットのハッシュ値をリンクの減らされた総数で割った余りが実際のリンクに対応するまで上記の動作を循環的に実行する。そして、データパケットが、実際のリンク内でフォワーディングされる。代替的に、ハッシュ値をリンクの総数で割った余りが仮想的なリンクに対応する場合、データパケットのハッシュ値を実際のリンクの数で割った余りが計算され、データパケットが余りに対応する実際のリンク内でフォワーディングされる。このようにして、データパケットができる限り実際のリンクに一様に分散される可能性があり、それによって、トラフィックを一様に分散させ、サービスへの影響を減らすように、仮想的なリンクを追加し、余りを計算することによって、データパケットが特定の実際のリンク内でフォワーディングされる可能性がある。
【００２１】
本発明の実施形態の別の場合では、通信デバイスが、データパケットのハッシュ値をリンクの決定された総数で割った余りを計算する。リンクの総数は、2の整数乗であり、追加された仮想的なリンクの数と、データパケットをフォワーディングするための実際のリンクを拡張することによって形成された仮想的なサブリンクの数との総和である可能性がある。ハッシュ値をリンクの総数で割った余りが仮想的なリンクに対応する場合、データパケットの別のハッシュ値が計算され、プロセスは別のハッシュ値に基づいて余りを計算するステップに戻され、データパケットのハッシュ値をリンクの減らされた総数で割った余りが実際のリンクを拡張するために形成された仮想的なサブリンクのうちの1つに対応するまで上記の動作を循環的に実行する。そして、データパケットが、実際のリンク内でフォワーディングされる。代替的に、ハッシュ値をリンクの総数で割った余りが仮想的なリンクに対応する場合、ハッシュ値を実際のリンクを拡張することによって形成されたすべての仮想的なサブリンクの数で割った余りが計算され、データパケットが余りに対応する仮想的なサブリンクを形成することに及ぶ実際のリンク内でフォワーディングされる。このようにして、データパケットが最終的に特定の実際のリンク内でフォワーディングされる可能性があり、データパケットができる限り実際のリンクに一様に分散される可能性があり、それによって、トラフィックを一様に分散させ、サービスへの影響を減らすように、実際のリンクが仮想的なサブリンクへと拡張され、仮想的なリンクが追加され、余りが計算される。
【００２２】
本発明の実施形態または従来技術における技術的な解決策をより明瞭に説明するために、以下で、実施形態を説明するために必要とされる添付の図面を簡単に紹介する。明らかに、以下の説明における添付の図面は、本発明の一部の実施形態または従来技術を示すに過ぎず、当業者は、創造的な努力なしにこれらの添付の図面からその他の図面を導き出すことがやはり可能である。
【図面の簡単な説明】
【００２３】
【図１ａ】本発明の実施形態による通信システムの概略構造図である。
【図１ｂ】本発明の実施形態による通信システムの概略構造図である。
【図２ａ】本発明の実施形態によるパケットフォワーディング方法の流れ図である。
【図２ｂ】本発明の実施形態によるパケットフォワーディング方法の流れ図である。
【図３】本発明の応用の実施形態による、どの実際のリンクがデータパケットをフォワーディングするかを決定するプロセスを示す概略図である。
【図４ａ】本発明の実施形態によるその他のパケットフォワーディング方法の流れ図である。
【図４ｂ】本発明の実施形態によるその他のパケットフォワーディング方法の流れ図である。
【図５】本発明の応用の実施形態による、どの実際のリンクがデータパケットをフォワーディングするかを決定する別のプロセスを示す概略図である。
【図６】本発明の実施形態によるパケットフォワーディングデバイスの概略構造図である。
【図７】本発明の実施形態による通信デバイスの概略構造図である。
【発明を実施するための形態】
【００２４】
以降、本発明の実施形態の技術的な解決策が、本発明の実施形態の図面に関連して明瞭かつ完全に説明される。明らかに、説明される実施形態は、本発明の実施形態の一部であり、すべてではない。創造的な努力なしに本発明の実施形態に基づいて当業者によって得られるすべてのその他の実施形態は、本発明の保護範囲内に入るものである。
【００２５】
パケットフォワーディング方法が、本発明の実施形態に従って提供され、主として、図1aまたは図1bに示される通信システムに適用され得る。図1aに示される通信システムは、通信デバイス1および複数の通信デバイス2(すなわち、図1aの通信デバイス21から通信デバイス2m)を含み、通信デバイス1は、異なるリンクを介して複数の通信デバイス2に接続される。図1bに示される通信システムは、通信デバイス1および通信デバイス2を含み、通信デバイス1は、複数のリンク(たとえば、m個のリンク)を介して通信デバイス2と通信し得る。
【００２６】
実施形態による方法は、図1aまたは図1bに示される通信システムの通信デバイス1によって実行される。方法は、主に、データパケットをフォワーディングするための実際のリンクの数が2の整数乗でない場合を対象とする。方法の流れ図が、図2aおよび図2bに示され、方法は、以下を含む。
【００２７】
ステップ101において、リンクの総数Nが2の整数乗であると決定され、リンクの総数Nは、仮想的なリンクの数Pとデータパケットをフォワーディングするための実際のリンクの数Mとの総和である。
【００２８】
データパケットを受信すると、通信デバイス(たとえば、通信デバイス1)はどのリンクがデータパケットをフォワーディングするために使用されるかを決定する必要があり、それから、データパケットをフォワーディングすることを理解されたい。実施形態においては、データパケットをフォワーディングするためのリンクを決定するプロセスで、通信デバイスがパケットをフォワーディングする実際のリンクの数が2の整数乗である場合、データパケットのハッシュ値を実際のリンクの数で割った余りがリンクを決定するために計算される。通信デバイスがパケットをフォワーディングする実際のリンクの数が2の整数乗でない場合、1つがデータパケットをフォワーディングするために使用されるリンクの総数が、上のステップの前に決定される。特に、仮想的なリンクの数Pおよび実際のリンクの数Mの総和が2の整数乗に等しいように、P個の仮想的なリンクが実際のリンクに基づいて追加される可能性がある。
【００２９】
その後の計算を容易にするために、通信デバイスは、実際のリンクおよび仮想的なリンクに番号を振る可能性がある。たとえば、実際のリンクから仮想的なリンクに向かって、リンクは、0、1、2、...、N-1と番号を振られる可能性がある。
【００３０】
ステップ102において、データパケットのハッシュ値が計算される。
【００３１】
ステップ103において、ステップ102において計算されたハッシュ値をリンクの総数Nで割った余りが計算される。
【００３２】
特に、通信デバイスは、最初に、データパケットからフィールドの一部を抽出し、たとえば、5つ組み(すなわち、送信元IPアドレス、送信先IPアドレス、送信元ポート、送信先ポート、およびプロトコル番号)などの複数のフィールドをデータパケットの先頭から抽出する可能性がある。別のパケット、たとえば、トンネルパケット(tunnel packet)に関して、通信デバイスは、トンネルパケットの外部レイヤ(external layer)から5つ組みを抽出するのみでなく、トンネルパケットの内部レイヤ(internal layer)からその他のフィールドを補足的なフィールドとして抽出する可能性もある。そして、フィールドの抽出された部分が、バイトシーケンスを形成するために特定の順序で並べられ、巡回冗長検査(Cyclic redundancy check、CRC)が、ハッシュ値を計算するためにバイトシーケンスに対して実行される。
【００３３】
ハッシュ値を得た後、通信デバイスは、ハッシュ値を使用してリンクの総数Nに対して剰余計算を実行する、すなわち、ハッシュ値をリンクの総数Nで割った余りを計算する可能性がある。ハッシュ値をリンクの総数で割った余りが仮想的なリンクに対応する場合、図2aに示されるようにステップ104が実行されるか、または図2bに示されるようにステップ105が実行される。ハッシュ値をリンクの総数Nで割った余りが実際のリンクに対応する場合、ステップ106が実行される、すなわち、データパケットが実際のリンク内でフォワーディングされる。第1のハッシュ値をリンクの総数Nで割った余りは、0、1、2、...、およびN-1を含む。上述のリンクの番号と組み合わせて、余りがリンクの番号と同じである場合、通信デバイスは、余りがリンクに対応すると判定する。ハッシュ値をリンクの総数で割った余りが仮想的なリンクに対応するとき、上記の動作が循環的に実行される必要があり、それによって、計算の量を増やす。できる限り計算の量を減らすために、図2Bに示される実施形態が採用され得る。
【００３４】
ステップ104において、データパケットの別のハッシュ値が計算され、プロセスは、別のハッシュ値に基づいてステップ103に戻り、すなわち、データパケットの特定のハッシュ値をリンクの総数で割った余りが実際のリンクに対応するまで、別のハッシュ値をリンクの総数Nで割った余りが計算され、データパケットが、実際のリンク内でフォワーディングされる。
【００３５】
ステップ104において別のハッシュ値を計算するための方法はステップ102においてハッシュ値を計算するための方法と同様であることに留意されたい。2つのハッシュ値は、それぞれ、データパケットのフィールドの一部によって形成されたシーケンスに基づいて得られる。しかし、2つのハッシュ値を計算する際は、異なるフィールドが、データパケットから抽出される可能性があり、または、異なるハッシュ計算方法が、抽出されたフィールドによって形成されたシーケンスのために使用される可能性がある。
【００３６】
ステップ105において、データパケットのハッシュ値をデータパケットの実際のリンクの数で割った余りが計算される。ハッシュ値を実際のリンクの数で割った余りが特定の実際のリンクに対応するので、通信デバイスは、ハッシュ値を実際のリンクの数で割った余りに対応する実際のリンク上でデータパケットをフォワーディングする。ここで、データパケットのハッシュ値は、ステップ103において余りを計算するためのハッシュ値と同じであるかまたは異なる可能性がある。特に、このステップにおいては、ステップ102において計算されたハッシュ値が、ステップ105において余りを計算するためのハッシュ値として直接使用される可能性があり、その他のフィールドが、データパケットから抽出される可能性があり、ハッシュ計算が、別のハッシュ値を得るために実行されるか、または別の異なるハッシュ値が、ハッシュ値を計算するためにステップ102において抽出されたフィールドに基づいて別のハッシュ計算方法を使用して取得される。
【００３７】
加えて、ステップ101からステップ104のサイクルを余りにも多く繰り返すことを避けるために、特定の実施形態においては、ステップ101からステップ104までのサイクルの回数が予め設定された値を超えた後もハッシュ値をリンクの総数で割った余りが仮想的なリンクにまだ対応する場合、通信デバイスは、ステップ105を実行し続けることに留意されたい。
【００３８】
本発明の実施形態において、通信デバイスは、データパケットのハッシュ値をリンクの決定された総数で割った余りを計算する。リンクの総数は、2の整数乗であり、追加された仮想的なリンクの数とデータパケットをフォワーディングするための実際のリンクの数との総和である可能性がある。ハッシュ値をリンクの総数で割った余りが仮想的なリンクに対応する場合、データパケットの別のハッシュ値が計算され、プロセスは別のハッシュ値に基づいて余りを計算するステップに戻る。データパケットのハッシュ値をリンクの減らされた総数で割った余りが実際のリンクに対応するまで上記の動作を循環的に実行し、データパケットが、実際のリンク上でフォワーディングされる。代替的に、ハッシュ値をリンクの総数で割った余りが仮想的なリンクに対応する場合、データパケットのハッシュ値を実際のリンクの数で割った余りが計算され、データパケットが、余りに対応する実際のリンク上でフォワーディングされる。このようにして、データパケットが最終的に特定の実際のリンク上でフォワーディングされる可能性があり、データパケットができる限り実際のリンクに一様に分散される可能性があり、それによって、トラフィックを一様に分散させ、サービスへの影響を減らすように、仮想的なリンクが追加され、余りが計算される。
【００３９】
図3に示されるように、図2bに示されたパケットフォワーディング方法が、以降で特定の実施形態を使用して示される。実施形態において、通信デバイスがデータパケットをフォワーディングする実際のリンク(灰色で塗りつぶされたブロックは図3において実際のリンクを示す)の数は、3であり、1つの仮想的なリンク(破線のブロックは図3において仮想的なリンクを示す)が、実際のリンクの数と仮想的なリンクの数との総和が4、すなわち、2の整数乗に等しいように追加される可能性がある。これらのリンクは、0から3までの番号を振られる。
【００４０】
第1に、データパケットを受信するとき、通信デバイスは、データパケットから5つ組みを抽出し得る。ハッシュ値1を計算するために、5つ組みを並べることによって形成されたバイトシーケンスに対してCRCが実行される。ハッシュ値1を4に等しいリンクの総数で割った余りが、計算される。得られた余りが0から2までの間である場合、0から2が実際のリンクの番号にそれぞれ対応するので、データパケットが、それぞれの実際のリンク内でフォワーディングされる。
【００４１】
第2に、余りが3である場合、3が仮想的なリンクの番号に対応するので、別の余りが計算される必要がある。特に、フィールドの別の部分が、ハッシュ値2を得るためにデータパケットから抽出される可能性がある。ハッシュ値を実際のリンク2の数で割った余りが、0から2までの間の余りを得るために計算される。0から2までの間の余りは、特定の実際のリンクの番号に確実に対応する。データパケットが、それぞれの実際のリンク内でフォワーディングされる。その他の実施形態においては、元のハッシュ値1または別の新しく計算されたハッシュ値2が、実際のリンクの数に対する余りを計算するために使用される可能性がある。
【００４２】
別のパケットフォワーディング方法が、本発明の実施形態に従って提供され、主として、図1aまたは図1bに示される通信システムに適用され得る。本発明の実施形態による方法は、図1aまたは図1bに示される通信システムの通信デバイス1によって実行される。方法は、主に、データパケットをフォワーディングするための実際のリンクの数が2の整数乗でない場合を対象とする。図4aおよび図4bに示されるように、方法は、以下を含む。
【００４３】
ステップ201において、リンクの総数Nが2の整数乗であると決定され、リンクの総数Nは、追加された仮想的なリンクの数Pと、データパケットをフォワーディングするための実際のリンクを拡張することによって形成された仮想的なサブリンクの数との総和である。
【００４４】
データパケットを受信すると、通信デバイス(たとえば、通信デバイス1)はどのリンクがデータパケットをフォワーディングするために使用されるかを決定する必要があり、それから、データパケットをフォワーディングすることを理解されたい。実施形態においては、データパケットをフォワーディングするためのリンクを決定するプロセスで、通信デバイスがパケットをフォワーディングする実際のリンクの数が2の整数乗でない場合、1つがデータパケットをフォワーディングするために使用されるリンクの総数が始めに決定される。特に、複数の実際のリンクがそれぞれ拡張され、すなわち、複数の実際のリンクの各々が複数の仮想的なサブリンクへと拡張され、たとえば、各実際のリンクが3つの仮想的なサブリンクへと拡張される。そして、すべての実際のリンクを拡張することによって形成された仮想的なサブリンクの数(すなわち、すべての拡張された仮想的なサブリンクの数)と仮想的なリンクの数との総和が2の整数乗であるように、P個の仮想的なリンクが仮想的なサブリンクに基づいて追加される。実際のリンクを拡張する際、それぞれの実際のリンクが拡張される必要があり、異なる実際のリンクを拡張することによって形成される仮想的なサブリンクの数は同じであることに留意されたい。
【００４５】
リンクの総数を決定する前に、通信デバイスは、それぞれの実際のリンクを拡張することによって形成されるべき仮想的なサブリンクの数と、追加されるべき仮想的なリンクの数とを決定する可能性がある。特定の実施形態において、通信デバイスは、以下の方法で動作を実行する可能性がある。
【００４６】
第1に、データパケットをフォワーディングするためのそれぞれの実際のリンクを拡張することによって形成されるべき仮想的なサブリンクの数が決定される。たとえば、初期値が決定され、それから、仮想的なサブリンクの決定された数が積を得るために実際のリンクの数を乗算される。2の整数乗を得るために積に足される加算する値が、決定される。加算する値が予め設定された値(たとえば、3または2)未満である場合、加算する値が追加されるべき仮想的なリンクの数として使用され、リンクの総数が積と加算する値との総和であると決定される。加算する値が予め設定された値を超える場合、それぞれの実際のリンクを拡張することによって形成されるべき仮想的なサブリンクの別の数が決定され、仮想的なサブリンクの別の数のための加算する値が決定されることを理解されたい。そして、仮想的なサブリンクの別の数に基づいて得られた加算する値が、予め設定された値と比較され、対応する処理が、比較結果に基づいて実行される。得られた加算する値が予め設定された値未満になるまで、上記の動作が循環的に実行される。その後の計算を容易にするために、通信デバイスは、実際のリンクの仮想的なサブリンクおよび仮想的なリンクに番号を振る可能性がある。たとえば、実際のリンクの仮想的なサブリンクから仮想的なリンクに向かって、リンクは、0、1、2、...、およびN-1と番号を振られ、実際のリンクは、0からM-1まで番号を振られる。
【００４７】
ステップ202において、データパケットのハッシュ値が計算される。
【００４８】
ステップ203において、ステップ202において計算されたハッシュ値をリンクの総数Nで割った余りが計算される。
【００４９】
特に、通信デバイスは、最初に、データパケットからフィールドの一部、たとえば、5つ組み(すなわち、送信元IPアドレス、送信先IPアドレス、送信元ポート、送信先ポート、およびプロトコル番号)を抽出し、それから、フィールドの抽出された一部を特定の順序で並べてバイトシーケンスを形成し、バイトシーケンスに対して巡回冗長検査を実行してハッシュ値を計算する可能性がある。
【００５０】
ハッシュ値を得た後、通信デバイスは、ハッシュ値を使用してリンクの総数Nに対して剰余計算を実行し得る。ハッシュ値をリンクの総数で割った余りが仮想的なリンクに対応する場合、図4aに示されるようにステップ204が実行されるか、または図4bに示されるようにステップ205が実行される。ハッシュ値をリンクの総数Nで割った余りが仮想的なサブリンクに対応する場合、ステップ206が実行される。ハッシュ値をリンクの総数Nで割った余りは、0、1、2、...、およびN-1を含む。上述の仮想的なサブリンクの番号および仮想的なリンクの番号と組み合わせて、余りが仮想的なサブリンクの番号のうちの1つまたは仮想的なリンクの番号と同じである場合、通信デバイスは、余りが特定の仮想的なサブリンクまたは特定の仮想的なリンクに対応すると判定する。
【００５１】
ステップ204において、データパケットの別のハッシュ値が計算され、プロセスは別のハッシュ値に基づいてステップ203に戻る。すなわち、ステップ203を実行する際、ハッシュ値をリンクの総数で割った余りが実際のリンクの特定の仮想的なサブリンクに対応するまで、別のハッシュ値をリンクの総数で割った余りが計算される。そして、データパケットが、対応する実際のリンク内でフォワーディングされる。
【００５２】
ステップ204において別のハッシュ値を計算するための方法はステップ202においてハッシュ値を計算するための方法と同様であることに留意されたい。2つのハッシュ値は、それぞれ、データパケットのフィールドの一部によって形成されたシーケンスに基づいて得られる。2つのハッシュ値を計算する際は、異なるフィールドが、データパケットから抽出される可能性があり、または、異なるハッシュ計算方法が、抽出されたフィールドによって形成されたシーケンスのために使用される可能性がある。
【００５３】
ステップ205において、データパケットのハッシュ値を仮想的なサブリンクの数、すなわち、すべての実際のリンクを拡張することによって形成されたすべての仮想的なサブリンクの数で割った余りが、計算され、データパケットが、ハッシュ値を仮想的なサブリンクの数で割った余りに対応する仮想的なサブリンクを形成するために拡張された実際のリンク内でフォワーディングされる。ここで、データパケットのハッシュ値は、ステップ203において余りを計算するためのハッシュ値と同じであるかまたは異なる可能性がある。特に、このステップにおいては、通信デバイスが、データパケットからフィールドの別の部分を新しく抽出し、ハッシュ計算が、別のハッシュ値を得るために実行されるか、またはハッシュ値を計算するステップ202において抽出されたフィールドに基づいて別のハッシュ値計算方法を使用して別のハッシュ値を計算する。
【００５４】
加えて、ステップ201からステップ204のサイクルを余りにも多く繰り返すことを避けるために、特定の実施形態においては、ステップ101からステップ104までのサイクルの回数が予め設定された値を超えた後もハッシュ値をリンクの総数で割った余りが仮想的なリンクにまだ対応する場合、通信デバイスは、ステップ205を実行し続けることに留意されたい。
【００５５】
ステップ206において、データパケットが、特定の仮想的なサブリンクに対応する実際のリンク内でフォワーディングされる。余りが特定の仮想的なサブリンクに対応する場合、特定の仮想的なサブリンクに対応する実際のリンクを決定するプロセスにおいて、ステップ202において得られた余りが、商を得るために1つの実際のリンクを拡張して形成された仮想的なサブリンクの数で割られ、商の整数部が、特定の実際のリンクの番号に対応し、それによって、仮想的なサブリンクに対応する実際のリンクを得る。
【００５６】
図2aおよび図2bに示された実施形態においては、実際のリンクの数と仮想的なリンクの数との総和が2の整数乗であるように、仮想的なリンクが実際のリンクに基づいて追加される必要があることに留意されたい。しかし、追加されるべき仮想的なリンクの数が多い場合、計算の量が増やされる。できる限り計算の量を減らすために、図4aまたは図4bに示された実施形態による方法が採用され得る。
【００５７】
実施形態において、通信デバイスは、データパケットのハッシュ値をリンクの決定された総数で割った余りを計算する。リンクの総数は、2の整数乗であり、追加された仮想的なリンクの数と、データパケットをフォワーディングするための実際のリンクを拡張することによって形成された仮想的なサブリンクの数との総和である可能性がある。ハッシュ値をリンクの総数で割った余りが仮想的なリンクに対応する場合、データパケットの別のハッシュ値が計算され、プロセスは別のハッシュ値に基づいて余りを計算するステップに戻る。データパケットのハッシュ値をリンクの減らされた総数で割った余りが実際のリンクの特定の仮想的なサブリンクに対応するまで上記の動作を循環的に実行し、データパケットが、実際のリンク上でフォワーディングされる。代替的に、ハッシュ値をリンクの総数で割った余りが仮想的なリンクに対応する場合、パケットのハッシュ値を実際のリンクのすべての仮想的なサブリンクの数で割った余りが計算され、データパケットが余りに対応する仮想的なサブリンクを形成するために拡張された実際のリンク上でフォワーディングされる。このようにして、データパケットが最終的に特定の実際のリンク上でフォワーディングされる可能性があり、データパケットができる限り実際のリンクに一様に分散される可能性があり、それによって、トラフィックを一様に分散させ、サービスへの影響を減らすように、実際のリンクが仮想的なサブリンクへと拡張され、仮想的なリンクが追加され、余りが計算される。
【００５８】
図5に示されるように、図4bに示されたパケットフォワーディング方法が、以降で特定の実施形態を使用して説明される。実施形態において、通信デバイスがデータパケットをフォワーディングする(実線によって示される)実際のリンクの数は、9であり、実際のリンクは、0から8まで番号を振られる。仮想的なサブリンクの数と仮想的なリンクの数との総和が64、すなわち、2の整数乗に等しいように、それぞれの実際のリンクが7つの仮想的なサブリンクへと拡張され、それから、(破線によって示される)1つの仮想的なリンクが追加される必要がある。これらのリンクは、0から63までの番号を振られる。
【００５９】
第1に、データパケットを受信するとき、通信デバイスは、データパケットから5つ組みを抽出し得る。ハッシュ値1を計算するために、5つ組みを並べることによって形成されたバイトシーケンスに対してCRCが実行される。ハッシュ値1を64に等しいリンクの総数で割った余りが、計算される。得られたハッシュ値が0から62までの間である場合、0から62までが実際のリンクの仮想的なサブリンクの番号にそれぞれ対応するので、余りが、商の整数部を得るために、1つの実際のリンクを拡張することによって形成された7に等しい仮想的なサブリンクの数で割られ、整数部は、特定の実際のリンクの番号に対応する可能性がある。そして、データパケットが、対応する実際のリンク内でフォワーディングされる。
【００６０】
第2に、余りが63である場合、63が仮想的なリンクの番号に対応するので、別の余りが計算される必要がある。特に、フィールドの別の部分が、ハッシュ値2を得るためにデータパケットから抽出される可能性がある。ハッシュ値2を63に等しい仮想的なサブリンクの数で割った余りが、0から62までの間の余りを得るために計算される。余りは、特定の実際のリンクの特定の仮想的なサブリンクの番号に確実に対応し、そして、対応する実際のリンクが、決定される。データパケットが、決定された実際のリンク上でフォワーディングされる。その他の実施形態においては、元のハッシュ値1または別の新しく計算されたハッシュ値2が、リンクの減らされた総数に対する余りを計算するために使用される可能性がある。
【００６１】
本発明の実施形態、すなわち、通信デバイス1によるパケットフォワーディングデバイスが、さらに提供される。実施形態によるデバイスは、図2aまたは図2bに示された流れ図に従ってパケットをフォワーディングし得る。図6は、以下を含むデバイスの概略構造図である。
【００６２】
リンク決定ユニット10は、リンクの総数Nが2の整数乗であると決定するように構成され、リンクの総数は、追加された仮想的なリンクの数とデータパケットをフォワーディングするための実際のリンクの数との総和である。リンク決定ユニット10は、仮想的なリンクの数Pと実際のリンクの数Mとの総和が2の整数乗であるように、実際のリンクに基づいてP個の仮想的なリンクを追加し得る。その後の計算を容易にするために、実際のリンクおよび仮想的なリンクが番号を振られる可能性がある。たとえば、実際のリンクから仮想的なリンクに向かって、リンクは、0、1、2、...、およびN-1と番号を振られる。
【００６３】
余り計算ユニット11は、データパケットのハッシュ値を計算し、ハッシュ値をリンクの総数で割った余りを計算するように構成され、リンクの総数は、リンク決定ユニット10によって決定される。ハッシュ値を計算するプロセスで、余り計算ユニットは、データパケットからフィールドの一部を抽出し、フィールドの抽出された一部によって形成されたバイトシーケンスに対して巡回冗長検査を実行してハッシュ値を計算し得る。
【００６４】
通知ユニット12は、余り計算ユニット11によって得られたハッシュ値をリンクの総数で割った余りが仮想的なリンクに対応する場合、データパケットの別のハッシュ値の計算および別のハッシュ値に基づく余りの計算を余り計算ユニット11に通知するように構成される。特に、余り計算ユニット11は、別のハッシュ値をリンクの総数で割った余りを計算するように通知される。
【００６５】
フォワーディングユニット13は、余り計算ユニット11および通知ユニット12が、データパケットのハッシュ値をリンクの減らされた総数で割った余りが実際のリンクに対応するまで上記の動作を循環的に実行するとき、データパケットを実際のリンク上でフォワーディングするように構成される。フォワーディングユニット13は、余り計算ユニット11によって得られたハッシュ値をリンクの総数で割った余りが実際のリンクに対応する場合、実際のリンク上でデータパケットをフォワーディングするようにさらに構成される。
【００６６】
代替的に、その他の特定の実施形態において、通知ユニット12は、余り計算ユニット11によって得られたハッシュ値をリンクの総数で割った余りが仮想的なリンクに対応する場合、余り計算ユニット11がデータパケットのハッシュ値を実際のリンクの数で割った余りを計算することを通知するように構成される。この場合、フォワーディングユニット13は、ハッシュ値を実際のリンクの数で割った余りに対応する実際のリンク上でデータパケットをフォワーディングするように構成され、余りは、余り計算ユニット11によって取得される。この場合、実際のリンクの余りを計算するためのハッシュ値は、リンクの総数の余りを計算するためのハッシュ値と同じであるかまたは異なる可能性がある。
【００６７】
別の特定の実施形態においては、通知ユニット12およびフォワーディングユニット13がステップ101からステップ104までを余りにも多く繰り返し実行することを避けるために、通知ユニット12およびフォワーディングユニット13のステップ101からステップ104までのサイクル動作の回数が予め設定された値を超えた後もハッシュ値をリンクの総数で割った余りが仮想的なリンクにまだ対応する場合、通知ユニット12およびフォワーディングユニット13は、ステップ105を実行し続ける可能性がある。
【００６８】
実施形態においては、データパケットが最終的に特定の実際のリンク内でフォワーディングされる可能性があり、データパケットができる限り実際のリンクに一様に分散される可能性があり、それによって、トラフィックを一様に分散させ、サービスへの影響を減らすように、通信デバイスが仮想的なリンクを追加し、余りを計算し得る。
【００６９】
本発明の実施形態による通信デバイスが、さらに提供される。実施形態によるデバイスは、図2に示された流れ図に従ってデータパケットをフォワーディングする可能性があり、そのデバイスの概略構造図が、図7に示される。通信デバイスは、プロセッサ21、送信機22、および受信機23を含み、これらは、バスに接続される。通信デバイスは、メモリをさらに含み得る。
【００７０】
メモリは、送信機22から受信されたデータを記憶し、プロセッサ21によってデータを処理するための必要なファイルなどの情報を記憶するために使用される。送信機22および受信機23は、通信デバイスがその他のデバイスと通信するポートである。
【００７１】
プロセッサ21は、受信機23がデータパケットを受信するとき、リンクの総数Nが2の整数乗であると決定することであって、リンクの総数が、追加された仮想的なリンクの数とデータパケットをフォワーディングするための実際のリンクの数との総和である、決定すること、データパケットのハッシュ値を計算すること、ハッシュ値をリンクの総数で割った余りを計算すること、ハッシュ値をリンクの総数で割った余りが仮想的なリンクに対応する場合、データパケットの別のハッシュ値を計算し、別のハッシュ値に基づいて余りを計算し、特に、別のハッシュ値をリンクの総数で割った余りを計算すること、データパケットのハッシュ値をリンクの減らされた総数で割った余りが実際のリンクに対応するまで上記の動作を循環的に実行すること、および実際のリンク上でデータパケットをフォワーディングするように送信機22に通知することを行うように構成される。代替的に、ハッシュ値をリンクの総数で割った余りが仮想的なリンクに対応する場合、プロセッサ21は、データパケットのハッシュ値を実際のリンクの数で割った余りを計算し、ハッシュ値を実際のリンクの数で割った余りに対応する実際のリンク上でデータパケットをフォワーディングするように送信機22に通知するように構成される。この場合、実際のリンクの数の余りを計算するためのハッシュ値は、リンクの総数の余りを計算するためのハッシュ値と同じであるかまたは異なる可能性がある。
【００７２】
プロセッサ21は、ハッシュ値をリンクの総数で割った余りが実際のリンクに対応する場合、実際のリンク上でデータパケットをフォワーディングするように送信機22に通知するようにさらに構成される。このようにして、データパケットが最終的に特定の実際のリンク内でフォワーディングされる可能性があり、データパケットができる限り実際のリンクに一様に分散される可能性があり、それによって、トラフィックを一様に分散させ、サービスへの影響を減らすように、仮想的なリンクが追加される可能性があり、余りが計算される。
【００７３】
プロセッサ21は、仮想的なリンクの数Pと実際のリンクの数Mとの総和が2の整数乗であるように、実際のリンクに基づいてP個の仮想的なリンクを追加し得る。その後の計算を容易にするために、実際のリンクおよび仮想的なリンクが番号を振られる可能性がある。たとえば、実際のリンクから仮想的なリンクに向かって、リンクは、0、1、2、...、およびN-1と番号を振られる。ハッシュ値を計算するプロセスにおいて、プロセッサ21は、データパケットからフィールドの一部を抽出し、フィールドの抽出された一部によって形成されたバイトシーケンスに対して巡回冗長検査を実行してハッシュ値を計算する可能性がある。
【００７４】
本発明の実施形態、すなわち、通信デバイス1による別のパケットフォワーディングデバイスが、さらに提供される。実施形態によるデバイスは、図4に示された流れ図に従ってパケットをフォワーディングする可能性があり、そのデバイスの概略構造図は、図6と同様である。パケットフォワーディングデバイスは、以下を含む。
【００７５】
リンク決定ユニットは、リンクの総数Nが2の整数乗であると決定するように構成され、リンクの総数は、追加された仮想的なリンクの数とデータパケットをフォワーディングするための実際のリンクを拡張することによって形成された仮想的なサブリンクの数との総和である。
【００７６】
リンク決定ユニットは、リンクの総数を決定する前に、データパケットをフォワーディングするためのそれぞれの実際のリンクを拡張することによって形成される仮想的なサブリンクの数を決定し、仮想的なサブリンクの決定された数に実際のリンクの数を掛けて積を取得し、2の整数乗を得るために積に足される加算する値を決定し、加算する値が予め設定された値未満である場合、加算する値を追加されるべき仮想的なリンクの数として用い、リンクの総数を積と加算する値との総和として決定し、加算する値が予め設定された値を超える場合、それぞれの実際のリンクを拡張することによって形成されるべき仮想的なサブリンクの別の数を決定し、仮想的なサブリンクの別の数に関して加算する値を決定する可能性がある。
【００７７】
リンク決定ユニットは、データパケットをフォワーディングするための複数の実際のリンクの各々を複数の仮想的なサブリンクに拡張する可能性があり、たとえば、複数の実際のリンクの各々が、3つの仮想的なサブリンクへと拡張され、それから、リンク決定ユニットは、すべての実際のリンクを拡張することによって形成された仮想的なサブリンクの数(すなわち、すべての仮想的なサブリンクの数)と仮想的なリンクの数との総和が2の整数乗であるように、これらの仮想的なサブリンクに基づいてP個の仮想的なリンクを追加する可能性がある。その後の計算を容易にするために、リンク決定ユニットは、実際のリンクの仮想的なサブリンクおよび仮想的なリンクに番号を振る可能性がある。たとえば、実際のリンクの仮想的なサブリンクから仮想的なリンクに向かって、リンクは、0、1、2、...、およびN-1と番号を振られ、実際のリンクは、0からM-1まで番号を振られる可能性がある。
【００７８】
余り計算ユニットは、データパケットのハッシュ値を計算し、ハッシュ値をリンクの総数で割った余りを計算するように構成され、リンクの総数は、リンク決定ユニットによって決定される。特に、余り計算ユニットは、データパケットからフィールドの一部を抽出し、フィールドの抽出された一部によって形成されたバイトシーケンスに対して巡回冗長検査を実行してハッシュ値を計算するように構成される。
【００７９】
通知ユニットは、余り計算ユニットによって取得された、ハッシュ値をリンクの総数で割った余りが仮想的なリンクに対応する場合、データパケットの別のハッシュ値の計算および別のハッシュ値に基づく余り計算の計算を余り計算ユニットに通知するように構成される。すなわち、余り計算ユニットは、別のハッシュ値をリンクの減らされた総数で割った余りを計算する可能性がある。
【００８０】
フォワーディングユニットは、余り計算ユニットおよび通知ユニットが、データパケットのハッシュ値をリンクの減らされた総数で割った余りが実際のリンクの特定の仮想的なサブリンクに対応するまで上記の動作を循環的に実行するとき、実際のリンク上でデータパケットをフォワーディングするように構成される。
【００８１】
フォワーディングユニットは、ハッシュ値をリンクの総数で割った余りが特定の仮想的なサブユニットに対応する場合、特定の仮想的なサブリンクに対応する実際のリンク上でデータパケットをフォワーディングするようにさらに構成され、余りは、余り計算ユニットによって取得される。
【００８２】
代替的に、特定の実施形態において、通知ユニットは、余り計算ユニットによって取得された、ハッシュ値をリンクの数で割った余りが仮想的なリンクに対応するとき、データパケットのハッシュ値を仮想的なサブリンクの数で割った余りの計算を余り計算ユニットに通知するように構成される。この場合、フォワーディングユニットは、ハッシュ値を仮想的なサブリンクの数で割った余りに対応する仮想的なサブリンクを形成するために拡張された実際のリンク上でデータパケットをフォワーディングするように構成され、余りは、余り計算ユニットによって取得される。この場合、仮想的なサブリンクの数の余りを計算するためのハッシュ値は、リンクの総数の余りを計算するためのハッシュ値と同じであるかまたは異なる可能性がある。
【００８３】
別の特定の実施形態においては、通知ユニットおよびフォワーディングユニットがステップ201からステップ204までを余りにも多く実行することを避けるために、通知ユニット12およびフォワーディングユニット13のステップ101からステップ104までのサイクル動作の回数が予め設定された値を超えた後もハッシュ値をリンクの総数で割った余りが仮想的なリンクにまだ対応する場合、通知ユニットおよびフォワーディングユニットは、ステップ205を実行し続ける可能性がある。
【００８４】
余りが特定の仮想的なサブリンクに対応する場合、仮想的なサブリンクに対応する実際のリンクを決定するプロセスにおいて、フォワーディングユニットは、余り計算ユニットによって取得された余りを1つの実際のリンクを拡張することによって形成された仮想的なサブリンクの数で割って商を得る可能性があり、商の整数部は、実際のリンクの番号に対応する可能性があり、それによって、仮想的なサブリンクに対応する実際のリンクを得る。
【００８５】
実施形態においては、データパケットが最終的に特定の実際のリンク内でフォワーディングされる可能性があり、データパケットができる限り実際のリンクに一様に分散される可能性があり、それによって、トラフィックを一様に分散させ、サービスへの影響を減らすように、通信デバイスが実際のリンクを拡張し、仮想的なリンクを追加し、余りを計算し得る。さらに、方法によって、より少ない仮想的なリンクが追加される。
【００８６】
本発明の実施形態による通信デバイスが、さらに提供される。実施形態によるデバイスは、図4に示された流れ図に従ってパケットをフォワーディングする可能性があり、そのデバイスの概略図は、図7と同様である。通信デバイスは、プロセッサ、送信機、および受信機を含み、これらは、バスに接続される。加えて、通信デバイスは、メモリをさらに含み得る。
【００８７】
メモリは、送信機から受信されたデータを記憶し、プロセッサによってデータを処理するための必要なファイルなどの情報を記憶するために使用される。送信機および受信機は、通信デバイスがその他のデバイスと通信するポートである。
【００８８】
プロセッサは、送信機がデータパケットを受信するとき、リンクの総数Nが2の整数乗であることを決定することであって、リンクの総数が、データパケットをフォワーディングするための実際のリンクを拡張することによって形成された仮想的なサブリンクの数と追加された仮想的なリンクの数との総和である、決定すること、データパケットのハッシュ値を計算し、ハッシュ値をリンクの総数で割った余りを計算すること、ハッシュ値をリンクの総数で割った余りが仮想的なリンクに対応する場合、データパケットの別のハッシュ値を計算し、別のハッシュ値に基づいて余り計算を実行する、すなわち、別のハッシュ値をリンクの総数で割った余りを計算すること、データパケットのハッシュ値をリンクの減らされた総数で割った余りが実際のリンクの特定の仮想的なサブリンクに対応するまで上記の動作を循環的に実行すること、および実際のリンク上でデータパケットをフォワーディングするように送信機に通知することを行うように構成される。代替的に、別の特定の実施形態において、プロセッサは、ハッシュ値をリンクの総数で割った余りが仮想的なリンクに対応する場合、データパケットのハッシュ値を仮想的なサブリンクの数で割った余りを計算し、ハッシュ値を仮想的なサブリンクの数で割った余りに対応する仮想的なサブリンクを形成するために拡張された実際のリンク上でデータパケットをフォワーディングするように送信機に通知するように構成される。この場合、仮想的なサブリンクの数に対する余りを計算するためのハッシュ値は、リンクの総数に対する余りを計算するためのハッシュ値と同じであるかまたは異なる可能性がある。
【００８９】
プロセッサは、ハッシュ値をリンクの総数で割った余りが特定の仮想的なサブリンクに対応する場合、特定の仮想的なサブリンクに対応する実際のリンク上でデータパケットをフォワーディングするように送信機に直接通知するようにさらに構成される。このようにして、データパケットが最終的に特定の実際のリンク内でフォワーディングされる可能性があり、データパケットができる限り実際のリンクに一様に分散される可能性があり、それによって、トラフィックを一様に分散させ、サービスへの影響を減らすように、実際のリンクが拡張され、仮想的なリンクが追加され、余りが計算される。さらに、この方法によって、より少ない仮想的なリンクが追加される。
【００９０】
プロセッサは、リンクの総数を決定する前に、データパケットをフォワーディングするための実際のリンクのうちの1つを拡張することによって形成されるべき仮想的なサブリンクの数を決定し、仮想的なサブリンクの決定された数に実際のリンクの数を掛けて積を取得し、2の整数乗を得るために積に足される加算する値を決定し、加算する値が予め設定された値未満である場合、加算する値を追加されるべき仮想的なリンクの数として用い、リンクの総数が積と加算する値との総和であると決定し、加算する値が予め設定された値を超える場合、実際のリンクのうちの1つを拡張することによって形成されるべき仮想的なサブリンクの別の数を決定し、仮想的なサブリンクの別の数に関して加算する値を決定する可能性がある。
【００９１】
リンクの総数を決定する際、プロセッサは、データパケットをフォワーディングするための複数の実際のリンクの各々を複数の仮想的なサブリンクに拡張する可能性があり、たとえば、複数の実際のリンクの各々は、3つの仮想的なサブリンクへと拡張され、それから、プロセッサは、すべての実際のリンクを拡張することによって形成された仮想的なサブリンクの数(すなわち、すべての仮想的なサブリンクの数)と仮想的なリンクの数との総和が2の整数乗であるように、仮想的なサブリンクに基づいてP個の仮想的なリンクを追加する可能性がある。その後の計算を容易にするために、リンク決定ユニットは、実際のリンクを拡張することによって形成された仮想的なサブリンクおよび仮想的なリンクに番号を振る可能性がある。たとえば、実際のリンクを拡張することによって形成された仮想的なサブリンクから仮想的なリンクに向かって、リンクは、0、1、2、...、およびN-1と番号を振られ、実際のリンクは、0からM-1まで番号を振られる。ハッシュ値を計算する際、プロセッサは、データパケットからフィールドの一部を抽出し、フィールドの抽出された一部によって形成されたバイトシーケンスに対して巡回冗長検査を実行してハッシュ値を計算する可能性がある。余りが特定の仮想的なサブリンクに対応するとき、特定の仮想的なサブリンクを形成するために拡張された実際のリンクを決定するプロセスにおいて、プロセッサは、余り計算ユニットによって取得された余りを1つの実際のリンクを拡張することによって形成された仮想的なサブリンクの数で割って商を得る可能性があり、商の整数部は、特定の実際のリンクの番号に対応する可能性があり、それによって、仮想的なサブリンクに対応する実際のリンクを得る。
【００９２】
本発明の実施形態によるパケットフォワーディングシステムが、さらに提供される。パケットフォワーディングシステムの概略構造図が、図1bに示される。パケットフォワーディングシステムは、第1の通信デバイス(すなわち、通信デバイス1)および第2の通信デバイス(すなわち、通信デバイス2)を含む。第1の通信デバイスと第2の通信デバイスとの間でデータパケットをフォワーディングするように構成された複数の実際のリンクが、存在する。第1の通信デバイスは、上のデバイスの実施形態によるデータパケットフォワーディングデバイスまたは通信デバイスと同じ構造を有し、その構造は、本明細書において説明されない。
【００９３】
本発明の実施形態による別のパケットフォワーディングシステムが、さらに提供される。パケットフォワーディングシステムの概略構造図が、図1aに示される。パケットフォワーディングシステムは、第1の通信デバイス(すなわち、通信デバイス1)および複数の第2の通信デバイス(すなわち、通信デバイス21から2m)を含む。第1の通信デバイスと複数の第2の通信デバイスの各々との間でデータパケットをフォワーディングするように構成された実際のリンクが、存在する。第1の通信デバイスは、上のデバイスの実施形態によるデータパケットフォワーディングデバイスまたは通信デバイスと同じ構造を有し、その構造は、本明細書において説明されない。
【００９４】
当業者は、上の実施形態による方法のステップのすべてまたは一部がプログラムによって命令される関連するハードウェアによって実行される可能性があることを理解し得る。プログラムは、コンピュータ可読ストレージ媒体、たとえば、読み出し専用メモリ(ROM)、ランダムアクセスメモリ(RAM)、磁気ディスク、または光ディスクに記憶される可能性がある。
【００９５】
本発明の実施形態によるパケットフォワーディング方法、パケットフォワーディングシステム、およびパケットフォワーディングデバイスが、上で詳細に説明されている。本発明の原理および実装方法が、特定の実施形態を使用して明瞭にされ、実施形態の説明は、本発明の方法およびその重要な概念を理解することのみを目的とする。加えて、当業者は、本発明の概念に従って特定の実装方法および応用範囲を変え得る。要約すれば、本明細書は、本発明を限定するように意図されていない。
【符号の説明】
【００９６】
10  リンク決定ユニット
11  余り計算ユニット
12  通知ユニット
13  フォワーディングユニット
21  プロセッサ
22  送信機
23  受信機
【図１ａ】
0006448660.tif 000002
【図１ｂ】
0006448660.tif 000003
【図２ａ】
0006448660.tif 000004
【図２ｂ】
0006448660.tif 000005
【図３】
0006448660.tif 000006
【図４ａ】
0006448660.tif 000007
【図４ｂ】
0006448660.tif 000008
【図５】
0006448660.tif 000009
【図６】
0006448660.tif 000010
【図７】
0006448660.tif 000011