(57)【要約】【課題】  回線の輻輳情報を負荷分散処理条件に加えることにより、トラヒックを適切に分散できるルート選択処理を可能とする技術を提供する。【解決手段】  パケットを複数の方路へ選択的に伝送して負荷分散を行う際、受信したパケットから宛先アドレス及び送信元アドレスを抽出し、各方路から受信される制御情報に基づいて輻輳状況を検出し、この輻輳状況を示す輻輳情報を求め、前記宛先アドレス、送信元アドレス及び輻輳情報に基づいて方路を決定して該方路にパケットを出力する。【選択図】          図４
2005252766.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークを介してパケットを伝送する際に複数の方路への負荷分散を行う伝送装置であって、
受信したパケットから宛先アドレス及び送信元アドレスを抽出するアドレス抽出部と、
各方路から受信される制御情報に基づいて輻輳状況を検出し、この輻輳状況を示す輻輳情報を求める輻輳検出部と、
前記宛先アドレス、送信元アドレス及び輻輳情報に基づいて方路を決定する方路決定部と、
前記方路決定部で決定した方路にパケットを出力する送信制御部とを備える伝送装置。
【請求項２】
前記方路決定部が、送信元アドレスと宛先アドレスのハッシュ値を求め、該ハッシュ値と輻輳情報とに対応した方路をルーティングテーブルから索出する請求項１に記載の伝送装置。
【請求項３】
前記ルーティングテーブルが、負荷分散を行う複数の方路に対応した複数のルーティング情報をそれぞれ複数の領域に格納しており、
前記方路決定部が、該ルーティングテーブルの各領域にハッシュ値を割り当て、前記宛先アドレス及び送信元アドレスのハッシュ値と対応する領域を選択し、この選択した領域のルーティング情報から前記宛先アドレスに対応する方路を索出する請求項２に記載の伝送装置。
【請求項４】
ネットワークを介してパケットを伝送する際に複数の方路への負荷分散を行う伝送装置にて運用される方法であって、
受信したパケットから宛先アドレス及び送信元アドレスを抽出するステップと、
各方路から受信される制御情報に基づいて輻輳状況を検出し、この輻輳状況を示す輻輳情報を求めるステップと、
前記宛先アドレス、送信元アドレス及び輻輳情報に基づいて方路を決定するステップと、
前記決定した方路にパケットを出力するステップを
含む伝送方法。
【請求項５】
ネットワークを介してパケットを伝送する際に複数の方路への負荷分散を行う伝送装置をノードとして含むネットワークシステムであって、
前記伝送装置が、
受信したパケットから宛先アドレス及び送信元アドレスを抽出するアドレス抽出部と、
各方路から受信される制御情報に基づいて輻輳状況を検出し、この輻輳状況を示す輻輳情報を求める輻輳検出部と、
前記宛先アドレス、送信元アドレス及び輻輳情報に基づいて方路を決定する方路決定部と、
前記方路決定部で決定した方路の次のノードにパケットを出力する送信制御部とを備えるネットワークシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークを介してパケットを転送する技術に関する。
例えば、本発明は、ＩＰネットワーク網におけるＩＰパケットルーター装置のＩＰパケットフォワーディング処理に関する。
【背景技術】
【０００２】
近年、ＩＰパケットのトラヒックの急増に伴い、ＩＰネットワークの拡大やネットワークリソースの効率的な活用、伝送品質の向上が要求されている。
【０００３】
従来の技術では、ＩＰネットワークにおけるトラヒックの経路は、ネットワーク設計により定まっていた。従ってＩＰネットワーク網のトラヒックが変化し、ネットワークパス間でのバランスが崩れてくると、ネットワーク管理者によるネットワークパス見直しや、再構築の必要が生じていた。
【０００４】
図３に、従来のトラヒックフローの例を示す。
この図に示すＩＰスイッチ（ルーター）は、ＩＰネットワークのユーザ拠点との境界に設けたエッジルータである。
【０００５】
ここで、ルーターαに接続された端末Ａ，Ｂ，ＣからＩＰネットワークを介してルーターβに接続されている端末Ｘに対して、大量のデータ送信を実施したとする。この場合、ルーターαでは、宛先アドレス(ＤＡ：Destination Address)を用いて方路検索を行い、
接続ポートを決定する。従って同じ相手先ＩＰアドレスへの全てのパケットが同じ経路を介してルーターβに伝送される事となる。即ち、ルーターαとルーターβ間には、複数のパスが存在するにも関らず、１本のパスに対してトラヒックが集中し、パケットの転送遅延の発生、もしくはパケットロスが発生する原因となっていた。
【０００６】
そして、このトラヒックの集中による問題を解決するため、同一の相手先アドレスへのパケットを複数ルートに分散して伝送する所謂負荷分散処理（Load balancing 処理）も
用いられる様になってきた。
【０００７】
この負荷分散処理を行ったトラヒックフローを図１２に示す。図１１と同様にルーターαには端末Ａ，Ｂ，Ｃから端末Ｘに対しての大量のデータ転送が要求されている。この場合、ルーターαでは負荷分散処理が実施される為に、其々の端末Ａ，Ｂ，Ｃからのパケットは、異なる経路を用いてルーターβに伝送される。つまり、複数のパスに負荷を分散して転送する事により、ネットワーク効率を高めることができる。
【０００８】
この負荷分散処理を実現する為には、例えば図１３に示す様な構成のルーター９０が用いられている。同図に示す様に従来のルーター９０は、複数のルーティングテーブルを記憶した記憶部９５や、ルーティングテーブルインターフェイス９４、ハッシュ演算部９３等からなる方路決定部を備えている。
【０００９】
ルーター９０は、パケットを受信すると、ＩＰヘッダ抽出部９１にて宛先アドレス（ＤＡ）と送信元アドレス(ＳＡ：Source Address)を抽出し、ハッシュ演算部９３へと渡す。
【００１０】
ハッシュ演算部９３では、ＤＡ及びＳＡを元にハッシュ演算（例えばＣＲＣ演算）を行い、演算結果として求めたハッシュ値をルーティングテーブルインターフェイス９４に送信する。該ルーティングテーブルインターフェイス９４は、記憶部９５のルーティングテ
ーブルを検索して前記ハッシュ値と対応する出力方路情報を求める。
【００１１】
ルーティングテーブルインターフェイス９４により得られた出力方路情報に基づいて送信制御部９６は、パケットバッファ９２からのパケットを対応する送信ポート９７から送信する。
【００１２】
本願発明に関連する先行技術として、例えば、下記の特許文献１及び２に開示される技術がある。
【特許文献１】特開２００３−２１８９１４号公報
【特許文献２】特開平９−２７０８０１号公報
【発明の開示】
【発明が解決しようとする課題】
【００１３】
上述した技術では、入力されるパケットのＤＡ及びＳＡにのみ基づいて出力方路を求めている為、選択された回線が輻輳状態にある場合も想定できる。
このため、ＤＡ及びＳＡのみに基づいた負荷分散処理では、選択したルートが輻輳状態であってもこの回線にパケットを送出する事になり、輻輳を助長する場合があった。
【００１４】
そこで本発明では、回線の輻輳情報を負荷分散処理条件に加えることにより、トラヒックを適切に分散できるルート選択処理を可能とする技術の提供を目的とする。
【課題を解決するための手段】
【００１５】
本発明の伝送装置は、ネットワークを介してパケットを伝送する際に複数の方路への負荷分散を行う伝送装置であって、
受信したパケットから宛先アドレス及び送信元アドレスを抽出するアドレス抽出部と、
各方路から受信される制御情報に基づいて輻輳状況を検出し、この輻輳状況を示す輻輳情報を求める輻輳検出部と、
前記宛先アドレス、送信元アドレス及び輻輳情報に基づいて方路を決定する方路決定部と、
前記方路決定部で決定した方路にパケットを出力する送信制御部とを備える。
前記方路決定部は、送信元アドレスと宛先アドレスのハッシュ値を求め、該ハッシュ値と輻輳情報とに対応した方路をルーティングテーブルから索出しても良い。
【００１６】
前記ルーティングテーブルは、負荷分散を行う複数の方路に対応した複数のルーティング情報をそれぞれ複数の領域に格納しており、
前記方路決定部は、該ルーティングテーブルの各領域にハッシュ値を割り当て、前記宛先アドレス及び送信元アドレスのハッシュ値と対応する領域を選択し、この選択した領域のルーティング情報から前記宛先アドレスに対応する方路を索出しても良い。
【００１７】
前記方路決定部が、前記輻輳情報に基づいて前記各領域のハッシュ値の割り当てを変更することにより、輻輳状態に応じて選択される領域を変えても良い。
【００１８】
前記方路決定部は、各方路から受信した輻輳情報に応じ、輻輳が生じている方路の前記割り当てを減らすことで、輻輳している方路へのルーティング量を減らし、負荷バランスをとっても良い。
【００１９】
また、前記パケットを複数の受信ポートから受信し、これと対応する複数の送信ポートから送信する場合、
前記送信制御部が、前記各送信ポートにおいてどの領域のルーティング情報に基づく方路への送信パケットがどれだけ送信されたかを示す情報である送信統計情報を前記輻輳検
出部に通知し、
前記輻輳検出部が、各受信ポートから得られる制御情報を常時又は定期的に監視し、この制御情報に基づいて負荷の高い受信ポートを求め、前記送信統計情報に基づいてこの負荷の高い受信ポートと対応する送信ポートにおいて送信量の多いパケットの方路を求め、この方路を示す情報を輻輳情報として方路決定部に通知しても良い。
【００２０】
前記パケットを複数の受信ポートから受信し、これと対応する複数の送信ポートから送信する場合、
前記送信制御部が、前記各送信ポートにおいてどの領域のルーティング情報に基づく方路への送信パケットがどれだけ送信されたかを示す情報である送信統計情報を前記輻輳検出部に通知し、
前記輻輳検出部が、各受信ポートから得られる制御情報を常時又は定期的に監視し、この制御情報に基づいて負荷の高い受信ポートを求め、前記送信統計情報に基づいてこの負荷の高い受信ポートと対応する送信ポートにおいて送信量の多いパケットの方路を索出したルーティングテーブルの領域を求め、この領域を示す情報を輻輳情報として方路決定部に通知し、
前記方路決定部が、この輻輳情報に示された領域の前記割り当てを減らすことで、輻輳している方路へのルーティング量を減らし、負荷バランスをとっても良い。
【００２１】
また、本発明の伝送方法は、
ネットワークを介してパケットを伝送する際に複数の方路への負荷分散を行う伝送装置にて運用される際、
受信したパケットから宛先アドレス及び送信元アドレスを抽出するステップと、
各方路から受信される制御情報に基づいて輻輳状況を検出し、この輻輳状況を示す輻輳情報を求めるステップと、
前記宛先アドレス、送信元アドレス及び輻輳情報に基づいて方路を決定するステップと、
前記決定した方路にパケットを出力するステップを
含む。
【００２２】
前記方路を決定するステップにおいて、送信元アドレスと宛先アドレスのハッシュ値を求め、該ハッシュ値と輻輳情報とに対応した方路をルーティングテーブルから索出しても良い。
【００２３】
また、前記伝送方法において、前記ルーティングテーブルが、負荷分散を行う複数の方路に対応した複数のルーティング情報をそれぞれ複数の領域に格納しており、前記各ルーティングテーブルの各領域にハッシュ値を割り当てておき、
前記方路を決定するステップにおいて、前記宛先アドレス及び送信元アドレスのハッシュ値と対応する領域を選択し、この選択した領域のルーティング情報から宛先アドレスに対応する方路を索出しても良い。
【００２４】
前記方路を決定するステップにおいて、前記輻輳情報に基づき前記各領域のハッシュ値の割り当てを変更することにより、輻輳状態に応じて選択される領域を変えても良い。
【００２５】
また、前記パケットを複数の受信ポートから受信し、これと対応する複数の送信ポートから送信する場合、
前記各送信ポートにおいてどの領域のルーティング情報に基づく方路への送信パケットがどれだけ送信されたかを示す情報である送信統計情報を前記輻輳検出部に通知するステップを更に備え、
前記輻輳情報を求めるステップにおいて、各受信ポートから得られる制御情報を常時又
は定期的に監視し、この制御情報に基づいて負荷の高い受信ポートを求め、前記送信統計情報に基づいてこの負荷の高い受信ポートと対応する送信ポートにおいて送信量の多いパケットの方路を求め、この方路を示す情報を輻輳情報として方路決定部に通知しても良い。
【００２６】
前記パケットを複数の受信ポートから受信し、これと対応する複数の送信ポートから送信する場合、
前記各送信ポートにおいてどの領域のルーティング情報に基づく方路への送信パケットがどれだけ送信されたかを示す情報である送信統計情報を前記輻輳検出部に通知するステップを更に備え、
前記輻輳情報を求めるステップにおいて、各受信ポートから得られる制御情報を常時又は定期的に監視し、この制御情報に基づいて負荷の高い受信ポートを求め、前記送信統計情報に基づいてこの負荷の高い受信ポートと対応する送信ポートにおいて送信量の多いパケットの方路を索出したルーティングテーブルの領域を求め、この領域を示す情報を輻輳情報として方路決定部に通知し、
前記方路を決定するステップにおいて、この輻輳情報に示された領域の前記割り当てを減らすことで、輻輳している方路へのルーティング量を減らし、負荷バランスをとっても良い。
【００２７】
また、本発明のネットワークシステムは、ネットワークを介してパケットを伝送する際に複数の方路への負荷分散を行う伝送装置をノードとして含み、
該伝送装置が、
受信したパケットから宛先アドレス及び送信元アドレスを抽出するアドレス抽出部と、
各方路から受信される制御情報に基づいて輻輳状況を検出し、この輻輳状況を示す輻輳情報を求める輻輳検出部と、
前記宛先アドレス、送信元アドレス及び輻輳情報に基づいて方路を決定する方路決定部と、
前記方路決定部で決定した方路の次のノードにパケットを出力する送信制御部とを備える。
【００２８】
図３は、本発明の原理説明図である。同図に示す伝送装置１０は、アドレス抽出部１６や、輻輳検出部２５、方路決定部１７、送信制御部１８を備えている。
【００２９】
加入者側からパケットが入力されると伝送装置１０は、アドレス抽出部１６にて該パケットのヘッダ情報から方路検索で使用する宛先アドレス及び送信元アドレスの情報を抽出する。パケットデータとの関連付けを行う為にフローＩＤを付加し、方路決定部１７へ通知する。伝送装置１０は、方路検索結果が求まるまでの間、パケットデータを方路決定部１７に渡したアドレス情報と同一のフローＩＤと共に、パケットバッファ６に格納させる。
【００３０】
方路決定部１７には、負荷分散に応じたルーティング情報を格納した複数の領域を有するルーティングテーブルを記憶部５に記憶している。
【００３１】
輻輳検出部２５は、送信制御部が送信ポート２２から各方路へ出力したパケットの送信統計情報と、ポーズ監視部８が各受信ポート１４にて受信される制御情報（バックプレッシャ情報）とに基づいて各方路の輻輳状況を求め、この輻輳状況に応じた輻輳情報を方路決定部１７に通知する。
【００３２】
方路決定部１７は、テーブル選択部１５が、ＤＡ及びＳＡのハッシュ演算値と、輻輳情報とに基づいて方路検索に用いるルーティングテーブルの領域を決定し、この領域のルー
ティング情報についてＤＡによる方路検索を行い、当該パケットを出力する方路を決定し、この方路へ出力するための出力方路情報と前記フローＩＤを送信制御部１８に通知する。
【００３３】
送信制御部１８のスケジューラ２４は、パケットバッファ６を介して共有メモリ２３に格納されたパケットデータのうち前記フローＩＤと対応するパケットデータを前記出力方路情報に基づいて対応する送信ポート２２から送信する。
このように本発明の構成であれば、以下の２つのポイントにより、課題解決の作用が期待できる。
【００３４】
（１）図３の方路決定部に示す如く、ＩＰヘッダー情報のＤＡ情報だけで方路検索動作を行うのではなく、ＤＡ，ＳＡに対するハッシュ演算値を用い、複数の前記領域の中から使用する領域を選択し、この選択した領域のルーティング情報によって出力方路検索を行っている。従って、ＩＰネットワーク上の一つのサーバーに対して、複数の端末より一斉にアクセスした場合においても、全てのパケットデータが同一のパスを使用する事を避け、複数のパスに振り分けて通信すること（負荷分散）が可能となる。
【００３５】
（２）方路決定部による方路検索処理は、受信ポートでのバックプレッシャ計測値と送信ポートでの送信統計情報に基づく輻輳情報によって選択される領域に基づくものであり、実際のネットワーク負荷に基づく負荷分散処理を行う事が可能となる。
【発明の効果】
【００３６】
本発明は、回線の輻輳情報を負荷分散処理条件に加えることにより、トラヒックを適切に分散できるルート選択処理を可能とする技術を提供できる。
【発明を実施するための最良の形態】
【００３７】
以下、図面を参照して本発明を実施するための最良の形態について説明する。以下の実施の形態の構成は例示であり、本発明は実施の形態の構成に限定されない。
図１は、本発明に係る伝送装置（ＩＰネットワークにおけるＩＰスイッチ、例えばルーター）を用いたネットワークシステムの概略構成図、図２はこのパケット伝送システムの機能ブロック図である。
【００３８】
この図に示す伝送装置１０，２０は、ＩＰネットワークのユーザ拠点との境界に設けたエッジルータである。
【００３９】
ここで、ルーター１０に接続された端末２ａ，２ｂ，２ｃからＩＰネットワークを介してルーター２０に接続されている端末２ｘに対して、大量のパケットを送信した場合について説明する。この場合、ルーター１０は、従来から用いられるＩＰヘッダー中の宛先アドレス(ＤＡ：Destination Address)によりルーティングテーブルを検索して、送信ポー
トを決定するフォワーディング機能に加え、パケットのＩＰヘッダーに含まれる宛先アドレス(ＤＡ)及び送信元アドレス(ＳＡ：Source Address)に対する演算値、ならびに回線輻輳状態に基づく輻輳情報を用いて、ルーティングテーブルに含まれる複数の領域から前記検索に用いる領域を選択する機能を有する。これによりルーター１０は、各回線の負荷バランスを図りながら出力方路決定を行う。
【００４０】
図４は、本発明に係る伝送装置１０の要部説明図であり、パケットを最大８方路へ選択的に転送することにより負荷分散を行うＩＰフォワーディング処理部分の機能ブロックを示している。なお、伝送装置２０については、伝送装置１０と同一の構成であるので説明を省略する。
【００４１】
同図に示すように、この伝送装置１０は、ＩＰフォワーディング処理のため、テーブル検索部（方路決定部に相当）１７、パケットバッファ６、ヘッダ抽出部（アドレス抽出部に相当）１６、送信制御部１８、受信制御部１９、輻輳検出部２５を備えている。
【００４２】
この受信制御部１９は、受信バッファ１３や、ポーズ監視部８を有している。
受信バッファ１３−１〜１３−ｎは、複数の受信ポート１４−１〜１４−ｎで各方路から受信したパケットをそれぞれ格納している。
【００４３】
ポーズ監視部８は、各方路から受信される制御情報（バックプレッシャ情報）を常時又は定期的に監視し、輻輳検出部２５に通知する。例えば、輻輳が発生して滞留パケットが増えた場合、対向装置（各方路においてリンクを挟んで装置１０と対向する次のノード）は、ポーズパケットを伝送装置１０に送信して送信の一次停止を要求する。ポーズ監視部８は、この送信停止要求を受信する時間（フロー制御時間）・頻度をポート毎に監視して統計をとり、この制御情報に基づく情報（制御統計情報）を定期的に輻輳検出部２５へと通知する。
【００４４】
ヘッダ抽出部１６は、前記受信バッファ１３を介して受信したパケットのヘッダ情報から宛先アドレス及び送信元アドレスを抽出する。
輻輳検出部２５は、後述の如くポーズ監視部８からの制御統計情報と、送信制御部１８からの送信統計情報とに基づいて輻輳情報を求め、この輻輳情報をテーブル検索部１７に通知する。この輻輳情報は、後述の如く、領域判定部１５における閾値変更情報として用いられる。
【００４５】
テーブル検索部１７は、前記宛先アドレス、送信元アドレス及び輻輳情報に基づいて方路を決定する。このとき、テーブル検索部１７のハッシュ演算部２１が、送信元アドレスと宛先アドレスのハッシュ値を求め、領域判定部１５がこのハッシュ値と輻輳情報とに対応した方路をルーティングテーブルから索出する。このルーティングテーブルは、記憶部５に記憶されており、負荷分散を行う方路に応じた複数のルーティング情報をそれぞれ複数（本例では８個）の領域に格納している。この複数の領域は、一つのルーティングテーブルが有する複数の領域として記憶されているものでも良いし、独立して複数のテーブルとして記憶されているものでも良い。また、この複数の領域は、物理的に特定の位置に存在するものに限らず、アドレスやラベル、格納の順序等によって一連の情報であること（どの領域の情報であるか）が特定できるように格納されたものでも良い。
【００４６】
領域判定部１５は、この各領域に予めハッシュ値の範囲を割り当て、前記ハッシュ演算部２１が求めたハッシュ値と対応する領域を選択し、この選択した領域のルーティング情報を参照して前記宛先アドレスと対応する方路を索出する。このとき、領域判定部１５は、輻輳情報に基づいて前記各領域のハッシュ値の割り当てを変更することにより、輻輳状態に応じて選択される領域を変えるようにしている。これにより、輻輳状態に応じた負荷分散が行われるようにしている。例えば、輻輳が生じた方路に係る領域の割り当てを減らし、輻輳が生じていない方路に係る領域の割り当てを増やすことにより、輻輳している方路へのルーティング量を減らし、負荷バランスをとる。
【００４７】
パケットバッファ６は、前記テーブル検索部１７でテーブル検索を行い、情報を得る間パケットを待たせる為のバッファである。
【００４８】
図５は、本実施形態の伝送装置によるパケット伝送の手順（伝送方法）の説明図である。
伝送装置１０は、対向装置から送られたパケットを受信ポート１４−１〜１４−ｎで受信し（ステップ１、以下Ｓ１のように略記する）、これが転送対象のパケットであれば（
Ｓ２）、このパケットデータを受信バッファ１３−１〜１３−ｎに格納し（Ｓ３）、このパケットデータからＩＰヘッダ抽出部にてＩＰヘッダー情報（ＤＡ，ＳＡ）を抽出する（Ｓ４）。このとき伝送装置１０は、抽出元のパケットデータとの関連付けを行う為に該ＩＰヘッダ情報にフローＩＤを付加し、このＩＰヘッダ情報をテーブル検索部１７へ通知する（Ｓ５）。また伝送装置１０は、方路検索結果が求まるまでの間、抽出元のパケットデータをテーブル検索部１７に渡したアドレス情報と同一のフローＩＤと共にパケットバッファ６に格納させる（Ｓ６）。
【００４９】
一方、ポーズ監視部８は、ステップ２で受信したパケットがポーズパケットか否かを監視し、ポーズパケットであれば制御統計情報を求めてテーブル検索部１７に通知する（Ｓ７）。輻輳検出部２５は、この制御統計情報と送信制御部からの送信統計情報とに基づいて輻輳情報を求め、テーブル検索部１７に通知する（Ｓ８）。
【００５０】
また、テーブル検索部１７のハッシュ演算部は、前記ＤＡとＳＡのハッシュ値を求め、領域判定部１５に通知する（Ｓ９）。領域判定部１５は、このＤＡ及びＳＡのハッシュ演算値と、輻輳情報とに基づいてルーティングテーブルの領域を選択する（Ｓ１０）。そして、インターフェイス４を介してこの選択した領域のルーティング情報を参照し、ＤＡによる方路検索を行い、当該パケットを出力する方路を決定し、この方路へ出力するための情報（出力方路情報）と前記ヘッダ情報に付加されていたフローＩＤを送信制御部１８に通知する（Ｓ１１）。一方、これと同時にパケットバッファ６からパケットデータが送信制御部１８に入力される（Ｓ１２）。
【００５１】
送信制御部１８は、インターフェイス９を介してフローＩＤが一致する出力方路情報とパケットデータとを対応付けて共有メモリ２３に保存する（Ｓ１３）。
【００５２】
送信制御部１８のスケジューラ１１は、共有メモリ２３に格納されたパケットデータを対応する出力方路情報に示される送信ポート２２から送信する（Ｓ１４）。このときスケジューラ１１による制御は、特に限定されるものではなく、既知のスケジューラ制御（例えば、RR: Round Robin, WRR: Weighted Round Robin）を用いてパケットを送信バッファ１２−１〜１２−ｎに振り分け、送信ポート２２−１〜２２−ｎからそれぞれ送信する。
【００５３】
また、送信制御部１８は、各送信ポートにおいてどの領域のルーティング情報に基づく方路への送信パケットがどれだけ送信されたかを示す情報である送信統計情報を求め、これを領域判定部１５へ通知する（Ｓ１５）。
【００５４】
以上説明した流れにおける主要な機能の詳細について以下で説明する。
（Ｉ）テーブル検索部の機能。
図６は、テーブル検索部１７の説明図である。
記憶部５に記憶されたルーティングテーブルの各領域ａ１〜ａ８には、それぞれ負荷分散のために異ならせたルーティング情報を蓄えられており、テーブル検索部１７は、この領域ａ１〜ａ８の何れかから選択的にＤＡに対する方路を検索する事により、出力すべき方路、即ち出力方路情報を得る事が出来る。
【００５５】
このテーブルを検索する為のキー情報（ＲＡＭのアドレス情報）は、領域判定部１５と、ＩＰアドレステーブル３により生成される。
ＩＰアドレステーブル３は、ＩＰヘッダー中の宛先アドレス（ＤＡ）と、このＤＡに係る出力方路情報を記憶しているルーティングテーブル上のポインタ値とを対応付けて記憶している。なお、本実施実施のＩＰアドレステーブル３は、ＣＡＭ（Content Addressable Memory）を用いて構成している。
【００５６】
本実施形態のテーブル検索部１７では、ＤＡとルーティング情報のフレキシブルな関連付けを行う事ができるようにしている。
【００５７】
一般的には、ＤＡに対応したポインタ値を用いてルーティングテーブルを検索する事により出力方路情報、付加ラベル情報を得るが、その場合、ＤＡに対して１：１のルーティング情報となり、負荷分散処理ができない。
【００５８】
そこで、本構成では、領域判定部１５での判定結果も用いて方路検索を行う。領域判定部１５は、ハッシュ演算部２１から宛先アドレス（ＤＡ）及び送信元アドレス（ＳＡ）のハッシュ値を受け、これに基づいて領域判定を行い、０ｈから７ｈまでの８通りの判定結果を出力する。
【００５９】
この領域判定部１５における領域判定の仕組みを図７に示す。
図７（Ａ）に示すように、ハッシュ演算部２１では、入力される宛先アドレス（ＤＡ）３２ｂｉｔと送信元アドレス（ＳＡ）３２ｂｉｔの計６４ｂｉｔについて、ハッシュ演算（ＣＲＣ−１６演算）を行い、１６ｂｉｔの演算結果（０〜６５５３５／１０進）を得る。なお、本実施形態では、ハッシュ演算としてＣＲＣ−１６を行い１６ｂｉｔの演算結果を得たが、ハッシュ演算にＣＲＣ−８等を用い、異なる精度の結果を得るようにしても良い。この精度は、負荷分散する方路数等に応じて任意に設定できる。また、演算方法としてＣＲＣ演算を用いず、ＳＡ３２ｂｉｔのＭＳＢからＬＳＢの文字の並びを逆にしたものと、ＤＡ３２ｂｉｔとでＥＯＲをとって３２ｂｉｔの値にし、更に上位１６ｂｉｔと下位１６ｂｉｔとのＥＯＲをとって１６ｂｉｔの値を得る等、他の演算方法を採る事も可能である。
【００６０】
これらの演算により得られた値は、領域判定部１５にて０ｈ〜７ｈのどの領域に属する値かを判定する。
この領域判定部１５では、０〜６５５３５までの値（即ち１６ｂｉｔ）を８つの範囲Ｘに分割する７つの閾値Ａ〜Ｇを設定（記憶）している。領域判定部１５は、この７つの閾値Ａ〜Ｇを、後述する送信制御部、受信制御部から通知される情報に基づいて変化させることで、この範囲Ｘを変更する。
【００６１】
領域判定部１５による判定は、図７（Ｂ）の表に示す通り、ハッシュ演算部２１からのハッシュ演算値が、どの範囲Ｘに属するかを求め、求めた範囲の判定値を出力する。即ち、ハッシュ演算値が、０以上閾値Ａ未満であれば判定値０ｈを出力し、閾値Ａ以上閾値Ｂ未満であれば１ｈを出力し、・・・閾値Ｇ以上６５５３５以下であれば７ｈを出力する。領域判定部１５は、この判定値に基づいて方路検索に用いるテーブルを選択する。例えば、判定値０ｈ〜７ｈとルーティングテーブルの領域ａ１〜ａ８とがそれぞれ対応付けられている場合、即ち領域ａ１〜ａ８にそれぞれ前記ハッシュ値の範囲Ｘが割り当てられている場合、ハッシュ演算値と対応する領域が選択される。
【００６２】
本実施形態において、記憶部５のルーティングテーブルは、図１０に示すようにＤＡに対する出力方路情報が複数の領域にそれぞれ記憶されている。例えば、あるＤＡに対する出力方路情報が＃１−１〜＃１−８の８個記憶されており、このうち＃１−１が領域ａ１の出力方路情報、＃１−２が領域ａ２の出力方路情報、・・・＃１−８が領域ａ８の出力方路情報となっている。
【００６３】
そしてテーブル検索部１７は、ＩＰアドレステーブル３から得たＤＡに対するポインタ値に前記判定値を加えてアドレス情報を生成し、記憶部５のルーティングテーブルを検索してこのアドレス情報に対応する出力方路情報を得る。テーブル検索部１７は、この結果得られた出力方路情報と判定値を該ＤＡのフロー情報と共に送信制御部１８に通知する。
【００６４】
（II）送信制御部の機能
図８に送信制御部１８の構成を示す。
送信制御部１８の共有メモリインターフェイス部９では、テーブル検索部１７から通知されるフローＩＤに対応するパケットデータをパケットバッファ６から読み出し、共有メモリに書き込む。一方、該インターフェイス部９は、出力方路情報とエリア判定情報（判定値）をスケジューラ部２４に通知する。通知を受けたスケジューラ部２４は、既知の技術であるスケジューリング手法により対応する送信バッファ１２−１〜１２−ｎにそれぞれ、共有メモリ２３のパケットデータをエリア判定情報と共に転送する。なお、大量のデータを扱う場合、この部分をクロスバースイッチ等の大規模スイッチにて構成する事も可能である。
【００６５】
送信バッファ１２−１〜１２−ｎは、それぞれ送信ポート２２−１〜２２−ｎに対応している。パケットデータは、この送信バッファ１２−１〜１２−ｎを介して、各ポート２２−１〜２２−ｎに出力される。また、各送信バッファ１２−１〜１２−ｎでは、パケットデータと共に通知されるエリア判定情報を終端し、送出するパケットがどの領域のルーティングテーブルの検索によるものかの統計処理を行う。各送信ポートの統計処理結果は、輻輳検出部２５へと通知される。
【００６６】
（III）受信制御部の機能
受信制御部１９では、図４に示す通り、各受信ポートにて検出される対向装置からのフロー制御時間を監視・計測するポーズ監視部８を持つ。
【００６７】
対向装置からは、回線が輻輳した滞留パケットが増えた場合、ポーズパケットを用いて送信の一次停止を要求してくる。ポーズ監視部８では、この送信停止要求を受信する時間・頻度をポート毎に統計をとり監視する。得られた情報は、定期的に輻輳検出部２５へと通知される。
【００６８】
（IV）輻輳検出部における輻輳検出処理
図９に示す通り、送信制御部１８は、送信パケットと共に転送されてくるエリア判定情報を元に、周期的にどのテーブル領域にてルート検索されたパケットが多いか、即ち各送信ポートにおける前記領域別のパケット数の情報（送信統計情報）を輻輳検出部２５に通知する。
【００６９】
また、受信制御部１９は、回線輻輳時に受信されるポーズパケットにより対向装置から制御されるポーズ時間を周期的に監視し、各受信ポートにおける単位時間当たりのポーズ制御発生頻度の情報（制御統計情報）を輻輳検出部２５に通知する。
【００７０】
そして輻輳検出部２５では、これら送信統計情報と制御情報とから輻輳状況を認識する。つまり、輻輳検出部２５は、送信統計情報からポーズ制御発生頻度の高い受信ポートを検出すると、対応する送信ポート（同じ対向装置と接続しているポート）において送信パケット量の多い領域を求める。これによりこの領域に基づく方路に輻輳が発生していることが認識できるので、この領域を示す情報を輻輳情報としてテーブル検索部１７の領域判定部１５に通知する。
【００７１】
（Ｖ）領域判定部内での閾値処理
領域判定部１５は、輻輳検出部２５から輻輳情報を受信した場合、この輻輳状態に示される領域を狭めるように閾値を変更する。即ち、該領域のハッシュ値の割り当てを減らし、該領域が選択される確率を減少させる。この制御により、他の領域の割り当てが増える、即ち他の領域が選択される確率が増えることになり、輻輳した方路へのパケットが他の
方路へルーティングされる。この結果、負荷の高いポートからのパケットの送信を減らし、それ以外のポートへのパケット送信を増やすことができる。
【００７２】
以上のように本実施形態によれば、ＩＰフォワーディング処理において、ＩＰヘッダー（ＳＡ，ＤＡ）と輻輳情報を用い、回線輻輳状態を加味した複数方路へのトラヒックバランシング処理（負荷分散処理）が可能となる。
【００７３】
ここで言う、回線輻輳状態を加味したバランシング処理とは、各ポートに対応するネットワーク上のバックプレッシャ発生頻度監視を行い、輻輳情報をテーブル検索部にフィードバックする事によるものである。即ち、輻輳が検出されたポートへの送信を単に停止し他のポートからの送信を行うのでは無く、回線の輻輳状況に応じてテーブル検索部で輻輳回線が選択される確率を落とす事により、パケットを送信する方路を制御するものである。これにより刻々と変化する回線負荷を考慮した負荷分散処理を伴うフォワーディング処理を行う事が可能となり、ネットワークの効率的な使用（各ネットワークパス間でのトラヒックの均質化）を可能とする。これにより、ＩＰネットワークのパフォーマンス向上に寄与するところが大きい。
【００７４】
従って、回線の輻輳状態監視結果情報を負荷分散処理条件に加える事により、複数のネットワークパスのトラヒック負荷を分散し、転送効率を上げつつネットワークの負荷変動に追従した柔軟なルート選択処理を行う事が可能となる。
【００７５】
〈その他の実施形態〉
本発明は、上述の図示例にのみ限定されるものではなく、本発明の要旨を逸脱しない範囲内において種々変更を加え得ることは勿論である。
【００７６】
例えば、以下に付記した構成であっても上述の実施形態と同様の効果が得られる。また、これらの構成要素は可能な限り組み合わせることができる。
【００７７】
（付記１）
ネットワークを介してパケットを伝送する際に複数の方路への負荷分散を行う伝送装置であって、
受信したパケットから宛先アドレス及び送信元アドレスを抽出するアドレス抽出部と、
各方路から受信される制御情報に基づいて輻輳状況を検出し、この輻輳状況を示す輻輳情報を求める輻輳検出部と、
前記宛先アドレス、送信元アドレス及び輻輳情報に基づいて方路を決定する方路決定部と、
前記方路決定部で決定した方路にパケットを出力する送信制御部とを備える伝送装置。（１）
【００７８】
（付記２）
前記方路決定部が、送信元アドレスと宛先アドレスのハッシュ値を求め、該ハッシュ値と輻輳情報とに対応した方路をルーティングテーブルから索出する付記１に記載の伝送装置。（２）
【００７９】
（付記３）
前記ルーティングテーブルが、負荷分散を行う複数の方路に対応した複数のルーティング情報をそれぞれ複数の領域に格納しており、
前記方路決定部が、該ルーティングテーブルの各領域にハッシュ値を割り当て、前記宛先アドレス及び送信元アドレスのハッシュ値と対応する領域を選択し、この選択した領域のルーティング情報から前記宛先アドレスに対応する方路を索出する付記２に記載の伝送
装置。（３）
【００８０】
（付記４）
前記方路決定部が、前記輻輳情報に基づいて前記各領域のハッシュ値の割り当てを変更することにより、輻輳状態に応じて選択される領域を変える付記３に記載の伝送装置。
【００８１】
（付記５）
前記方路決定部が、各方路から受信した輻輳情報に応じ、輻輳が生じている方路の前記割り当てを減らすことで、輻輳している方路へのルーティング量を減らし、負荷バランスをとる付記４に記載の伝送装置。
【００８２】
（付記６）
前記パケットを複数の受信ポートから受信し、これと対応する複数の送信ポートから送信する場合に、
前記送信制御部が、前記各送信ポートにおいてどの領域のルーティング情報に基づく方路への送信パケットがどれだけ送信されたかを示す情報である送信統計情報を前記輻輳検出部に通知し、
前記輻輳検出部が、各受信ポートから得られる制御情報を常時又は定期的に監視し、この制御情報に基づいて負荷の高い受信ポートを求め、前記送信統計情報に基づいてこの負荷の高い受信ポートと対応する送信ポートにおいて送信量の多いパケットの方路を求め、この方路を示す情報を輻輳情報として方路決定部に通知する付記５に記載の伝送装置。
【００８３】
（付記７）
前記パケットを複数の受信ポートから受信し、これと対応する複数の送信ポートから送信する場合に、
前記送信制御部が、前記各送信ポートにおいてどの領域のルーティング情報に基づく方路への送信パケットがどれだけ送信されたかを示す情報である送信統計情報を前記輻輳検出部に通知し、
前記輻輳検出部が、各受信ポートから得られる制御情報を常時又は定期的に監視し、この制御情報に基づいて負荷の高い受信ポートを求め、前記送信統計情報に基づいてこの負荷の高い受信ポートと対応する送信ポートにおいて送信量の多いパケットの方路を索出したルーティングテーブルの領域を求め、この領域を示す情報を輻輳情報として方路決定部に通知し、
前記方路決定部が、この輻輳情報に示された領域の前記割り当てを減らすことで、輻輳している方路へのルーティング量を減らし、負荷バランスをとる付記４に記載の伝送装置。
【００８４】
（付記８）
ネットワークを介してパケットを伝送する際に複数の方路への負荷分散を行う伝送装置にて運用される方法であって、
受信したパケットから宛先アドレス及び送信元アドレスを抽出するステップと、
各方路から受信される制御情報に基づいて輻輳状況を検出し、この輻輳状況を示す輻輳情報を求めるステップと、
前記宛先アドレス、送信元アドレス及び輻輳情報に基づいて方路を決定するステップと、
前記決定した方路にパケットを出力するステップを
含む伝送方法。（４）
【００８５】
（付記９）
前記方路を決定するステップにおいて、送信元アドレスと宛先アドレスのハッシュ値を
求め、該ハッシュ値と輻輳情報とに対応した方路をルーティングテーブルから索出する付記８に記載の伝送方法。
【００８６】
（付記１０）
前記ルーティングテーブルが、負荷分散を行う複数の方路に対応した複数のルーティング情報をそれぞれ複数の領域に格納しており、前記各ルーティングテーブルの各領域にハッシュ値を割り当てておき、
前記方路を決定するステップにおいて、前記宛先アドレス及び送信元アドレスのハッシュ値と対応する領域を選択し、この選択した領域のルーティング情報から宛先アドレスに対応する方路を索出する付記９に記載の伝送方法。
【００８７】
（付記１１）
前記方路を決定するステップにおいて、前記輻輳情報に基づき前記各領域のハッシュ値の割り当てを変更することにより、輻輳状態に応じて選択される領域を変える付記１０に記載の伝送方法。
【００８８】
（付記１２）
前記パケットを複数の受信ポートから受信し、これと対応する複数の送信ポートから送信する場合に、
前記各送信ポートにおいてどの領域のルーティング情報に基づく方路への送信パケットがどれだけ送信されたかを示す情報である送信統計情報を前記輻輳検出部に通知するステップを更に備え、
前記輻輳情報を求めるステップにおいて、各受信ポートから得られる制御情報を常時又は定期的に監視し、この制御情報に基づいて負荷の高い受信ポートを求め、前記送信統計情報に基づいてこの負荷の高い受信ポートと対応する送信ポートにおいて送信量の多いパケットの方路を求め、この方路を示す情報を輻輳情報として方路決定部に通知する付記１１に記載の伝送方法。
【００８９】
（付記１３）
前記パケットを複数の受信ポートから受信し、これと対応する複数の送信ポートから送信する場合に、
前記各送信ポートにおいてどの領域のルーティング情報に基づく方路への送信パケットがどれだけ送信されたかを示す情報である送信統計情報を前記輻輳検出部に通知するステップを更に備え、
前記輻輳情報を求めるステップにおいて、各受信ポートから得られる制御情報を常時又は定期的に監視し、この制御情報に基づいて負荷の高い受信ポートを求め、前記送信統計情報に基づいてこの負荷の高い受信ポートと対応する送信ポートにおいて送信量の多いパケットの方路を索出したルーティングテーブルの領域を求め、この領域を示す情報を輻輳情報として方路決定部に通知し、
前記方路を決定するステップにおいて、この輻輳情報に示された領域の前記割り当てを減らすことで、輻輳している方路へのルーティング量を減らし、負荷バランスをとる付記１０に記載の伝送方法。
【００９０】
（付記１４）
ネットワークを介してパケットを伝送する際に複数の方路への負荷分散を行う伝送装置をノードとして含むネットワークシステムであって、
前記伝送装置が、
受信したパケットから宛先アドレス及び送信元アドレスを抽出するアドレス抽出部と、
各方路から受信される制御情報に基づいて輻輳状況を検出し、この輻輳状況を示す輻輳情報を求める輻輳検出部と、
前記宛先アドレス、送信元アドレス及び輻輳情報に基づいて方路を決定する方路決定部と、
前記方路決定部で決定した方路の次のノードにパケットを出力する送信制御部とを備えるネットワークシステム。（５）
【図面の簡単な説明】
【００９１】
【図１】本発明に係るネットワークシステムの概略構成図
【図２】ネットワークシステムの機能ブロック図
【図３】本発明の原理説明図
【図４】伝送装置の機能を示すブロック図
【図５】伝送方法の説明図
【図６】テーブル検索部の説明図
【図７】領域判定部における領域判定の説明図
【図８】送信制御部の説明図
【図９】輻輳検出の説明図
【図１０】ルーティングテーブルの説明図
【図１１】従来のＩＰネットワークの説明図
【図１２】従来の負荷分散処理の説明図
【図１３】従来のルータの構成を示すブロック図
【符号の説明】
【００９２】
２ａ，２ｂ，２ｃ，２ｘ  端末
３    アドレステーブル
４    インターフェイス
５    記憶部
６    パケットバッファ
８    ポーズ監視部
９    共有メモリインターフェイス部
１０，２０  伝送装置（ルーター）
１１  スケジューラ
１２（１２−１〜１２−ｎ）    送信バッファ
１３（１３−１〜１３−ｎ）    受信バッファ
１４（１４−１〜１４−ｎ）    受信ポート
１５  領域判定部
１６  ヘッダ抽出部（アドレス抽出部）
１７  テーブル検索部（方路決定部）
１８  送信制御部
１９  受信制御部
２１  ハッシュ演算部
２２（２２−１〜２２−ｎ）    送信ポート
２２ａ      送信ポート
２２  送信ポート
２３  共有メモリ
２４  スケジューラ部
２５  輻輳検出部
【図１】
2005252766.tif 000003
【図２】
2005252766.tif 000004
【図３】
2005252766.tif 000005
【図４】
2005252766.tif 000006
【図５】
2005252766.tif 000007
【図６】
2005252766.tif 000008
【図７】
2005252766.tif 000009
【図８】
2005252766.tif 000010
【図９】
2005252766.tif 000011
【図１０】
2005252766.tif 000012
【図１１】
2005252766.tif 000013
【図１２】
2005252766.tif 000014
【図１３】
2005252766.tif 000015