パケット中継装置
【課題】ルータ等のパケット中継装置において、輻輳が発生する危険性を極めて少なくする。
【解決手段】パケット破棄検出部17は、出力ポート12-1〜12-k毎に、その出力ポートから出力されたパケットの破棄を検出する。振り分け処理部18は、パケット破棄検出部17の検出結果に基づいて出力ポート毎の輻輳度合いを算出し、輻輳度合いが閾値を超える第１の出力ポートについては、パケットの振り分け先にする第２の出力ポートを選択すると共に、その輻輳度合いに基づいて、パケットを第１、第２の出力ポートに振り分ける際の振り分け比率を算出する。パケット転送部13は、入力ポート11-1〜11-jから入力された、宛先が第１の出力ポートに対応するパケットを、振り分け処理部18で算出された振り分け比率に従って第１の出力ポートと第２の出力ポートとに振り分ける。
【解決手段】パケット破棄検出部17は、出力ポート12-1〜12-k毎に、その出力ポートから出力されたパケットの破棄を検出する。振り分け処理部18は、パケット破棄検出部17の検出結果に基づいて出力ポート毎の輻輳度合いを算出し、輻輳度合いが閾値を超える第１の出力ポートについては、パケットの振り分け先にする第２の出力ポートを選択すると共に、その輻輳度合いに基づいて、パケットを第１、第２の出力ポートに振り分ける際の振り分け比率を算出する。パケット転送部13は、入力ポート11-1〜11-jから入力された、宛先が第１の出力ポートに対応するパケットを、振り分け処理部18で算出された振り分け比率に従って第１の出力ポートと第２の出力ポートとに振り分ける。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パケットを中継するルータ、L3（レイヤー３）スイッチ等のパケット中継装置に関する。
【背景技術】
【０００２】
近年のデータ通信利用者の著しい増加に伴って、インターネット等のネットワークを流れるデータは急激に増加している。インターネットは、IP(Internet Protocol)により経路制御を行うネットワークであり、ネットワーク上には、パケットを中継するためのルータ等のパケット中継装置が多数存在する。
【０００３】
パケット中継装置では、RIP(Routing Information Protocol)や、OSPF(Open Shortest Path First)などのルーティングプロトコルを使用して、相手IPアドレス毎にコストの和が最小となる最適経路を計算し、ルーティングテーブルに経路情報として記録する。パケット中継装置は、パケットを受信すると、その宛先IPアドレスに基づいてルーティングテーブルから経路情報を検索し、この経路情報によって特定される出力ポートからパケットを送出する。尚、ルーティングテーブルの内容は、定期的または経路情報に変更が発生した場合に更新される。
【０００４】
上記したようなRIPやOSPFといった既存のルーティングプロトコルに依存したパケット中継装置が利用する経路は、最適経路として求めた唯一の経路であるため、その経路にトラヒックが集中した場合には、パケット中継装置に輻輳が発生し、パケットが破棄されてしまうという問題がある。また、パケットが破棄されると、再送処理が行われるため、遅延時間が増加してしまうという問題も発生する。
【０００５】
そこで、このような問題点を解決するため、次のような技術が提案された（例えば、特許文献１参照）。特許文献１に記載されている技術では、先ず、隣接ルータ間のリンクのトラフィック量に基づいて上記リンクに輻輳が発生しているか否かを判定する。そして、輻輳が発生している場合には、上記リンクを含む輻輳部分を限定する。その後、上記輻輳部分を迂回する負荷分散経路を検索し、この検索した負荷分散経路と輻輳部分を含む元々の経路との両方の経路を用いてパケットをルーティングする。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００３−２４４１９６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
特許文献１に記載されている技術によれば、負荷分散経路と元々の経路との２つ経路に負荷を分散させることができるので、輻輳が発生する危険性を少なくすることができる。しかし、特許文献１には、どのような比率で負荷分散経路と元々の経路とにパケットを振り分けるかについては全く記載されておらず、輻輳が発生する危険性を十分には少なくすることができないという問題があった。例えば、元々の経路のトラフィック量が非常に大きい場合に、負荷分散経路へのパケットの振り分け率が小さいと、輻輳状態が改善されないこともある。
【０００８】
[発明の目的]
そこで、本発明の目的は、輻輳が発生する危険性を十分には少なくすることができないという課題を解決したパケット中継装置を提供することにある。
【課題を解決するための手段】
【０００９】
本発明にかかる第１のパケット中継装置は、
パケットを入力する複数の入力ポートと、
パケットを出力する複数の出力ポートと、
前記出力ポート毎に、その出力ポートから出力されたパケットの破棄を検出するパケット破棄検出部と、
該パケット破棄検出部の検出結果に基づいて前記出力ポート毎の輻輳度合いを算出し、該算出した輻輳度合いが閾値を超える第１の出力ポートについては、パケットの振り分け先にする第２の出力ポートを前記複数の出力ポートの中から選択すると共に、前記第１の出力ポートの輻輳度合いに基づいて、宛先が前記第１の出力ポートに対応するパケットを前記第１の出力ポートと前記第２の出力ポートとに振り分ける際の振り分け比率を算出する振り分け処理部と、
前記入力ポートから入力された宛先が前記第１の出力ポートに対応するパケットを、前記振り分け処理部で算出された振り分け比率に従って前記第１の出力ポートと前記第２の出力ポートとに振り分けるパケット転送部とを備える。
【００１０】
本発明にかかるパケット中継方法は、
パケットを入力する複数の入力ポートと、パケットを出力する複数の出力ポートと、パケット転送部と、パケット破棄検出部と、振り分け処理部とを備えたコンピュータが実行するパケット中継方法であって、
前記パケット破棄検出部が、前記出力ポート毎に、その出力ポートから出力されたパケットの破棄を検出し、
前記振り分け処理部が、前記パケット破棄検出部の検出結果に基づいて前記出力ポート毎の輻輳度合いを算出し、該算出した輻輳度合いが閾値を超える第１の出力ポートについては、パケットの振り分け先にする第２の出力ポートを前記複数の出力ポートの中から選択すると共に、前記第１の出力ポートの輻輳度合いに基づいて、宛先が前記第１の出力ポートに対応するパケットを前記第１の出力ポートと前記第２の出力ポートとに振り分ける際の振り分け比率を算出し、
前記パケット転送部が、前記入力ポートから入力された宛先が前記第１の出力ポートに対応するパケットを、前記振り分け処理部で算出された振り分け比率に従って前記第１の出力ポートと前記第２の出力ポートとに振り分ける。
【００１１】
本発明にかかるプログラムは、
パケットを入力する複数の入力ポートと、パケットを出力する複数の出力ポートとを備えたコンピュータをパケット中継装置として機能させるためのプログラムであって、
前記コンピュータを、
該パケット破棄検出部の検出結果に基づいて前記出力ポート毎の輻輳度合いを算出し、該算出した輻輳度合いが閾値を超える第１の出力ポートについては、パケットの振り分け先にする第２の出力ポートを前記複数の出力ポートの中から選択すると共に、前記第１の出力ポートの輻輳度合いに基づいて、宛先が前記第１の出力ポートに対応するパケットを前記第１の出力ポートと前記第２の出力ポートとに振り分ける際の振り分け比率を算出する振り分け処理部、
前記入力ポートから入力された宛先が前記第１の出力ポートに対応するパケットを、前記振り分け処理部で算出された振り分け比率に従って前記第１の出力ポートと前記第２の出力ポートとに振り分けるパケット転送部として機能させる。
【発明の効果】
【００１２】
本発明によれば、輻輳が発生する危険性を十分に少なくすることができるという効果を得ることができる。
【図面の簡単な説明】
【００１３】
【図１】本発明の第１の実施の形態にかかるルータの構成例を示すブロック図である。
【図２】ルーティング14の内容例を示す図である。
【図３】ヘッダ情報管理部15の処理例を示すフローチャートである。
【図４】パケット破棄検出部17の処理例を示すフローチャートである。
【図５】振り分け処理部18の処理例の一部を示すフローチャートである。
【図６】振り分け処理部18の処理例の残りの部分を示すフローチャートである。
【図７】パケット転送部13の処理例を示すフローチャートである。
【図８】パケット破棄検出部17の動作を説明するための図である。
【図９】輻輳が解消される様子を示した図である。
【図１０】本発明の第２の実施の形態にかかるルータの構成例を示す図である。
【図１１】ホップ数調査部19の処理例を示すフローチャートである。
【発明を実施するための形態】
【００１４】
次に、本発明の実施の形態について図面を参照して詳細に説明する。
【００１５】
[本発明の第１の実施の形態]
図１を参照すると、本発明の第１の実施の形態にかかるルータ１は、複数の入力ポート11-1〜11-jと、複数の出力ポート12-1〜12-kと、パケット転送部13と、ルーティングテーブル14と、ヘッダ情報管理部15と、管理テーブル16と、パケット破棄検出部17と、振り分け処理部18とを備えている。
【００１６】
入力ポート11-1〜11-jには、隣接ルータ（図示せず）からのパケットが入力される。出力ポート12-1〜12-kからは、隣接ルータへのパケットが出力される。
【００１７】
ルーティングテーブル14には、図２に示すように、パケットの宛先（IPアドレス）に関連付けて、該当するパケットの出力先にする本来の出力ポートのポート番号（通常時）が記録されている。更に、本実施の形態のルーティングテーブル14は、パケットを元々の出力ポート以外の出力ポートにも振り分ける際に出力先にする出力ポートのポート番号（振り分け時）と、振り分け比率とが記録できるようになっている。振り分け比率は、通常時に出力先にしている元々の出力ポートと、振り分け時に出力先にする出力ポートとへ、どのような比率でパケットを振り分けるのかを示すものである。図２の例は、宛先がA1のパケットは、出力ポート番号P12-1の出力ポートへ出力され、宛先がA2のパケットは、出力ポート番号がP12-2, P12-kの出力ポートに、X:Yの比率で振り分けられることを示している。
【００１８】
パケット転送部13は、入力ポート11-1〜11-jから入力されたパケットの出力先にする出力ポートを、パケットの宛先とルーティングテーブル14の内容とに基づいて決定し、その出力ポートへパケットを出力する。
【００１９】
ヘッダ情報管理部15は、出力ポート12-1〜12-kに対応する送出パケット数カウンタ15-1〜15-kを備えており、入力ポート11-1〜11-jを介してパケットが入力されると、ルーティングテーブル14を参照してパケットの出力先にする出力ポートを求め、その出力ポートに対応する送出パケット数カウンタのカウント値をインクリメント（本実施の形態では+1）する。更に、ヘッダ情報管理部15は、入力されたパケットのIPヘッダ内のプロトコルフィールドがTCP(Transmission Control Protocol)であれば、そのパケットのヘッダ情報を管理テーブル16に記録すると共に、上記パケットをパケット破棄検出部17に渡す。尚、入力されたパケットが、コネクションで最初のパケットである場合には、そのヘッダ情報を管理テーブル16に記録する処理を行うだけで、パケットをパケット破棄検出部17に渡す処理は行わない。また、入力されたパケットがコネクションの切断を指示すものである場合は、上記コネクションに関連するヘッダ情報（宛先IPアドレス、宛先ポート番号、送信元IPアドレス及び送信元ポート番号が上記パケットと同じヘッダ情報と、宛先IPアドレス、宛先ポート番号、送信元IPアドレス及び送信元ポート番号が上記パケットの送信元IPアドレス、送信元ポート番号、宛先IPアドレス及び宛先ポート番号に入れ替わっているヘッダ情報）を管理テーブル16から削除する。
【００２０】
パケット破棄検出部17は、出力ポート12-1〜12-kに対応する破棄検出カウンタ17-1〜17-kを備えている。そして、ヘッダ情報管理部15からパケットが渡されると、そのパケットと、管理テーブル16に記録されているヘッダ情報とに基づいて自ルータ１から出力したパケットがネットワーク上で破棄されたか否かを判定する。そして、破棄されたと判定した場合は、ヘッダ情報管理部15から渡されたパケットと、ルーティングテーブル14の内容とに基づいて、破棄されたパケットを出力した出力ポートを求め、その出力ポートに対応する破棄検出カウンタのカウント値をインクリメントする。
【００２１】
振り分け処理部18は、下記(A)〜(F)の機能を有する。
【００２２】
(A)出力ポート12-1〜12-kそれぞれの輻輳度合いを算出する機能。本実施の形態では、一定時間の間に出力ポート12-a（１≦ａ≦ｋ）から出力されたパケットの総数に対する、上記一定時間の間に出力ポート12-aから出力されて破棄されたパケットの割り合いを示すパケット破棄検出率を出力ポート12-aの輻輳度合いとする。ここで、出力ポート12-aから出力されたパケットの総数をT、破棄されたパケット数をNとすると、パケット破棄検出率Paは、次式（ａ）に示すものとなる。
【００２３】
Ｐa＝Ｎa／Ｔa ……（１）
【００２４】
なお、輻輳度合いはこれに限られるものではなく、一定時間の間に破棄されたパケットの数などを使用することもできる。また、一定時間の間に出力ポート12-aから出力されたパケットの総数および破棄されたパケットの数は、それぞれ送出パケット数カウンタ15-aおよび破棄検出カウンタ17-aを参照することにより求めることができる。
【００２５】
(B) 出力ポート12-1〜12-k毎に、そのパケット破棄検出率が予め定められている第１の閾値Th1を超えているか否かを判定する機能。
【００２６】
(C)パケット破棄検出率が閾値Th1を超えている出力ポート12-aについては、他の出力ポートの中からパケットの振り分け先にする出力ポート12-b（１≦ｂ≦ｋ）を選択する機能。本実施の形態では、パケット破棄検出率が最も小さい出力ポートを振り分け先の出力ポートとして選択する。
【００２７】
(D)宛先が上記出力ポート12-aに対応するパケットを、上記出力ポート12-aと上記出力ポート12-bとに振り分ける際の振り分け比率を算出する機能。本実施の形態では、出力ポート12-a、12-bの重みA, Bをそれぞれ式（２）、（３）により算出し、A：Bを振り分け比率とする。
【００２８】
Ａ＝１−Ｐa ……（２）
Ｂ＝Ｐa ……（３）
なお、Ｐaは前述したように、出力ポート12-aのパケット破棄検出率である。
【００２９】
(E)振り分け先の出力ポート12-bのポート番号と、パケットの振り分け比率A：Bとを、出力ポート12-aと対応する宛先に関連付けてルーティングテーブル14に記録する機能。
【００３０】
(F)出力ポート12-1〜12-k毎に、そのパケット破棄検出率が予め定められている第２の閾値Th2未満であるか否かを判定し、閾値Th2未満の出力ポートについては、ルーティングテーブル14に振り分け先の出力ポートのポート番号が設定されているか否かを判定し、設定されている場合には、ルーティングテーブル16から振り分け先の出力ポートのポート番号およびパケットの振り分け比率を削除する機能。なお、第１、第２の閾値Th1,Th2は、Th1＞Th2の関係を有している。
【００３１】
パケット転送部13、ヘッダ情報管理部15、パケット破棄検出部17、及び、振り分け処理部18はCPU（中央処理装置）により実現可能であり、その場合には例えば次のようにする。CPUをパケット転送部13、ヘッダ情報管理部15、パケット破棄検出部17、及び、振り分け処理部18として機能させるためのプログラムを記録したディスク、半導体メモリ、その他の記録媒体を用意し、CPUに上記プログラムを読み取らせる。CPUは、読み取ったプログラムに従って自身の動作を制御することにより、自CPU上にパケット転送部13、ヘッダ情報管理部15、パケット破棄検出部17、及び、振り分け処理部18を実現する。
【００３２】
次に、本実施の形態の動作について詳細に説明する。
【００３３】
入力ポート11-1〜11-jから入力されたパケットは、パケット転送部13およびヘッダ情報管理部15に渡される。
【００３４】
これにより、パケット転送部13は、渡されたパケットの宛先と、ルーティングテーブル14の内容とに基づいて、パケットの出力先にする出力ポートを決定し、決定した出力ポートからパケットを出力する。このパケットは、隣接ルータとの間の経路を介して隣接ルータへ転送される。
【００３５】
一方、ヘッダ情報管理部15は、パケットが渡されると、出力ポート12-1〜12-k毎の送出パケット数カウンタ15-1〜15-kの内の、上記パケットの出力先になる出力ポートと対応するカウンタのカウント値をインクリメントする（図３のステップＳ31）。なお、パケットの出力先となる出力ポートは、ルーティングテーブル14から検索できる。
【００３６】
その後、ヘッダ情報管理部15は、パケットのIPヘッダ内のプロトコルフィールドの内容がTCPになっているか否かを判定する（ステップＳ32）。そして、プロトコルフィールドの内容がUDP(User datagram Protocol)など、TCP以外のものであった場合（ステップＳ32がNO）は、パケットを破棄する（ステップＳ33）。
【００３７】
これに対して、プロトコルフィールドの内容がTCPである場合（ステップＳ32がYES）は、現在処理対象にしているパケットと同一コネクションのパケットのヘッダ情報が管理テーブル16に記録されているか否かを判定する（ステップＳ34）。この判定は、宛先IPアドレス、宛先ポート番号、送信元IPアドレス、及び、送信元ポート番号が、現在処理対象にしているパケットと同一のヘッダ情報、または、宛先IPアドレス、宛先ポート番号、送信元IPアドレス、及び、送信元ポート番号が上記パケットの送信元IPアドレス、送信元ポート番号、宛先IPアドレス、及び、宛先ポート番号に入れ替わっているヘッダ情報が記録されているか否かを判定することにより行う。
【００３８】
ここで、プロトコルフィールドがTCPになっているパケットのヘッダ情報だけを管理テーブル16に記録しているのは、後述するように、本実施の形態では、パケットの破棄をTCPによる再送パケット及び確認応答パケット（ACKパケット）に基づいて検出するようにしているからである。
【００３９】
そして、現在処理対象にしているパケットとコネクションが同一のヘッダ情報が管理テーブル16に記録されていない場合（ステップＳ34がNO）は、上記パケットのヘッダ情報を管理テーブル16に記録すると共に、ヘッダ情報に関連付けてACK到着フラグを記録する（ステップＳ35）。ACK到着フラグは、上記ヘッダ情報を含んだパケットに対するACKパケットが到着しているか否かを示すものであり、初期状態では、ACK到着フラグは“０”となっている。即ち、初期状態においては、ACK到着フラグは、ACKパケットが到着していないことを表示している。
【００４０】
これに対して、コネクションが同一のヘッダ情報が管理テーブル16に記録されている場合（ステップＳ34がYES）は、パケットのヘッダ情報およびACK到着フラグを管理テーブル16に記録すると共に、上記パケットをパケット破棄検出部17に渡す（ステップＳ36，37）。
【００４１】
パケット破棄検出部17は、ヘッダ情報管理部15からパケットが渡されると、そのヘッダ部にACKフラグが立っているか否か、即ちACKフラグが“１”になっているか否かを判定する（図４のステップＳ41）。
【００４２】
そして、ACKフラグが“０”の場合（ステップＳ41がNOの場合）は、処理対象にしているパケットが送信側から再送されたパケットであるか否かを判定する（ステップＳ42）。この判定は、現在処理対象にパケットと同一コネクションのヘッダ情報であって、確認応答番号およびシーケンス番号が上記パケットと同一のヘッダ情報が管理テーブル16に記録されているか否かに基づいて行う。
【００４３】
そして、処理対象にしているパケットが再送パケットでない場合（ステップＳ42がNO）は、パケット破棄検出部17は、その処理を終了する。これに対して、処理対象にしているパケットが再送パケットである場合（ステップＳ42がYES）は、パケットが破棄されたものと判定し、出力ポート12-1〜12-k毎に設けられている破棄検出カウンタ17-1〜17-kの内の、上記パケットの出力先となる出力ポートに対応する破棄検出カウンタをインクリメントする（ステップＳ43)。今、例えば、図８(A)に示すように、送信側ノードから受信側ノードに対してパケットP1を送信したが、ルータR2でパケットP1が破棄されたとすると、送信側ノードはACKパケットが戻ってこないので、パケットP1を再送することになる。このような場合、ルータR3~R5内のパケット破棄検出部17では、ステップＳ42の判定結果がYESとなり、パケットP1が破棄されたと判定される。
【００４４】
また、ヘッダ情報管理部15から渡されたパケットにACKフラグが立っている場合、即ち、ヘッダ情報管理部15から渡されたパケットがACKパケットである場合（ステップＳ41がYES）は、管理テーブル16に記録されているACK到着フラグの内の、上記ACKパケットによって正常受信を知らせようとしているパケットのヘッダ情報と関連付けられているACK到着フラグが“１”になっているか否かを判定する（ステップＳ44）。なお、上記ACK到着フラグが関連付けられているヘッダ情報は、上記ACKパケットと同一コネクションのパケットのヘッダ情報の内の、確認応答番号が上記ACKパケット中のシーケンス番号と一致するヘッダ情報である。
【００４５】
そして、ACK到着フラグが“０”の場合（ステップＳ44がNO）は、受信側ノードにおいて、パケットが正常に受信され、ACKパケットが返されたことになるので、ACK到着フラグを“１”に変更する（ステップＳ46）。
【００４６】
これに対して、ACK到着フラグが“１”の場合（ステップＳ44がYES）は、パケットが破棄されたと判定し、出力ポート12-1〜12-k毎の破棄検出カウンタ17-1〜17-kの内の、ACKパケットによって正常受信を通知しようとしたパケットを出力した出力ポートに対応する破棄検出カウンタをインクリメントする（ステップＳ45）。今、例えば図８（Ｂ）に示すように、送信側ノードから受信側ノードに対してパケットP1〜P4が連続して送信され、パケットP2がルータR2において破棄されたとする。TCPが適用されている受信側ノードでは、パケットP1を受信することにより、パケットP1に対するACKパケットACK１を送信側ノードへ返す。その後、受信側ノードは、パケットP2がルータR2で破棄されているので、パケットP3を受信する。TCPが適用されている受信側ノードでは、パケットの受信時、受信に成功した最後のパケットに対するACKパケットを送信側ノードに送信する。この例の場合、受信に成功した最後のパケットは、パケットP1であるので、受信側ノードは、パケットP3, P4の受信時にも、パケットP1の受信時に送信したACKパケットACK1を送信側ノードに返す。このような場合、ルータR3〜R5内のパケット破棄検出部17では、ステップＳ44の判定結果がYESとなり、パケットが破棄されたと判定する。
【００４７】
次に、図５、図６のフローチャートを参照して振り分け処理部18の処理を説明する。振り分け処理部18は、一定時間毎に、図５、図６のフローチャートに示す処理を実行する。
【００４８】
先ず、振り分け処理部18は、出力ポート12-1〜12-kの内の１つに注目し、注目している出力ポート（例えば、出力ポート12-a）のパケット破棄検出率Paを算出する（ステップＳ51,Ｓ53）。具体的には、出力ポート12-aに対応する送出パケット数カウンタ15-aのカウント値Taと、破棄検出カウンタ17-aのカウント値Naとを入力し、前出の式（１）に示す演算を行うことにより、出力ポート12-aのパケット破棄検出率Pa＝Na／Taを算出する。その後、振り分け処理部18は、次の出力ポートに注目し、前述した処理と同様の処理を行う。
【００４９】
全ての出力ポート12-1〜12-kに対して前述した処理と同様の処理を行うと（ステップＳ52がYES）、振り分け処理部18は、再び出力ポート12-1〜12-kの内の１つに注目し、注目している出力ポート（例えば、出力ポート12-a）のパケット破棄検出率Paが予め定められている第１の閾値Th1を超えているか否かを判定する（ステップＳ54，Ｓ56）。
【００５０】
そして、パケット破棄検出率Paが第１の閾値Th1を超えている場合（ステップＳ56がYES）は、他の出力ポート（出力ポート12-a以外の出力ポート）の中からパケットの振り分け先にする出力ポート12-bを１つ選択する（ステップＳ57）。本実施の形態では、出力ポート12-a以外の出力ポートの中から、パケット破棄検出率が最も小さな出力ポートを振り分け先の出力ポート12-bとして選択する。
【００５１】
その後、振り分け処理部18は、宛先が出力ポート12-aに対応するパケットを、出力ポート12-aと振り分け先の出力ポート12-bとに振り分ける際の振り分け比率を算出する（ステップＳ58）。具体的には、前出の式（２）、（３）に示した演算を行うことにより、出力ポート12-a,12-bに対する重みA＝1−Pa、B＝Paを算出し、A：B＝（1−Pa）：Paをパケットの振り分け比率とする。
【００５２】
次に、振り分け処理部18は、本来なら出力ポート12-aを出力先にするパケットが、出力ポート12-bへも振り分けられるようにするため、ルーティングテーブル16の内容を更新する（ステップＳ59）。具体的には、ルーティングテーブル14に記録されている宛先（IPアドレス）の内の、通常時の出力先が出力ポート12-aとなっている宛先に関連付けて、出力ポート12-bのポート番号と、パケットの振り分け比率（1−Pa）：Paを記録する。このように、ルーティングテーブル14に振り分け先の出力ポート12-bのポート番号と、振り分け比率（1−Pa）：Paとを記録することにより、通常は出力ポート12-aに振り分けられるパケットの一部が、出力ポート12-bに振り分けられることになる。ここで、出力ポート12-aのパケット破棄検出率Paが大きくなるほど、出力ポート12-aに振り分けられるパケットの割合を少なくすることができるので、ルータ１が配置されているネットワークにおいて輻輳が発生する危険性を極めて少なくすることができる。
【００５３】
その後、振り分け処理部18は、次の出力ポートに注目し（ステップＳ54）、前述した処理と同様の処理を行う。
【００５４】
ステップＳ56において、出力ポート12-aのパケット破棄検出率Paが第１の閾値Th1を超えていると判定された場合が上述した処理が行われる。これに対して、ステップＳ56において、パケット破棄検出率Paが閾値Th1以下であると判定された場合（ステップＳ56がNO）は、次のような処理が行われる。
【００５５】
振り分け処理部18は、ステップＳ56において、出力ポート12-aのパケット破棄検出率Paが閾値Th1以下であると判定すると、図６のフローチャートに示すように、パケット破棄検出率Paが第２の閾値Th2未満か否かを判定する（ステップＳ62）。
【００５６】
そして、出力ポート12-aのパケット破棄検出率Paが第２の閾値Th2以上である場合（ステップＳ62がNO）は、図５のステップＳ54の処理に戻り、次の出力ポートを注目する。これに対して、パケット破棄検出率Paが第２の閾値Th2未満である場合（ステップＳ62がYES）は、ルーティングテーブル14を参照し、出力ポート12-aのポート番号（通常時）に関連付けて、振り分け先の出力ポートのポート番号および振り分け率が記録されているか否かを判定する（ステップＳ63）。
【００５７】
そして、記録されていない場合は、図５のステップＳ54の処理に戻り、次の出力ポートに注目する。これに対して、記録されている場合は、出力ポート12-bのポート番号および振り分け比率をルーティングテーブル14から削除する（ステップＳ64）。これにより、出力ポート12-bへはパケットが振り分けられなくなり、通常時に使用する本来の出力ポート12-aのみにパケットが振り分けられるようになる。その後、振り分け処理部18は、図５のステップＳ54の処理に戻り、次の出力ポートに注目する。
【００５８】
上述した処理を繰り返し行い、未注目の出力ポートがなくなると（図５のステップＳ55がYES）と、振り分け処理部18は、図６のフローチャートに示すように、送出パケット数カウンタ15-1〜15-kおよびパケット破棄検出カウンタ17-1〜17-kをクリアし（ステップＳ61）、その処理を終了する。
【００５９】
次に、図７のフローチャートを参照してパケット転送部13の動作を説明する。
【００６０】
パケット転送部13は、入力ポート11-1〜11-jを介してパケットが入力されると、先ず、パケットから宛先（IPアドレス）を抽出する（ステップＳ71）。その後、パケット転送部13は、ステップＳ71で抽出した宛先をキーにしてルーティングテーブル14を検索する（ステップＳ72）。
【００６１】
そして、検索結果が通常時にパケットの出力先にする本来の出力ポートのポート番号だけである場合（ステップＳ73がNO）は、上記本来の出力ポートにパケットを出力する（ステップＳ74）。
【００６２】
これに対して、検索結果に、本来の出力ポートのポート番号に加え、振り分け先の出力ポートのポート番号および振り分け比率も含まれている場合（ステップＳ73がYES）は、本来の出力ポートと振り分け先の出力ポートとの内の、どちらをパケットの出力先にするかを決定する（ステップＳ75）。パケットの出力先の決定方法としては、種々の方法を採用することができ、例えば、次のような方法を採用することができる。パケットの振り分けを開始してから現時点までに、本来の出力ポートに出力したパケット数、および、振り分け先の出力ポートに出力したパケット数をカウントする第１及び第２のカウンタを用意する。パケットの出力先を決定する際には、上記第１、第２のカウンタのカウント値に基づいて、どちらの出力ポートにパケットを出力した方が、実際のパケットの振り分け比率が、ルーティングテーブル14に設定されている振り分け比率に近くなるか判定し、近くなると判定した方の出力ポートをパケットの出力先に決定する。その後、パケット転送部13は、通常時に使用する出力ポートと振り分け先の出力ポートとの内の、ステップＳ75で出力先に決定された出力ポートにパケットを出力する（ステップＳ76）。
【００６３】
例えば、ルーティングテーブル14の内容が図２に示すものであり、パケットの宛先が「A1」である場合には、出力ポート12-1のみにパケットが出力される。これに対して、パケットの宛先が「A2」の場合は、通常時に使用される出力ポート12-2と振り分け先の出力ポート12-kとに、X：Yの比率でパケットが出力される。
【００６４】
図９は、トラフィックの集中が解消される様子を示した図である。尚、図９に示したルータR1〜R6は、図１に構成を有するものである。
【００６５】
図９(A)に示すように、ルータR3にトラフィックが集中すると、同図(B)に示すように、ルータR3に輻輳が発生する。その後、同図(C)に示すように、ルータR1がパケットをルータR2に向けて出力する。このパケットは、輻輳が発生しているルータR3において破棄される。その後、ルータR1内のパケット破棄検出部17は、同図(D)に示すように、パケットが破棄されたことを検出する。そして、ルータR2へパケットを送信するための出力ポートのパケット破棄検出率が前述した第１の閾値Th1を超えている場合は、ルータR1内の振り分け処理部18がルーティングテーブル14の内容を変更し、同図(E)に示すように、元々使用していた出力ポートと振り分け先の出力ポートとにパケットを振り分けて出力する。
【００６６】
[第１の実施の形態の効果]
本実施の形態によれば、輻輳が発生する危険性を十分に少なくすることができるという効果を得ることができる。その理由は、パケット破棄検出率（輻輳度合い）が第１の閾値Th1を上回る出力ポート12-aのパケット破棄検出率に基づいて、宛先が出力ポート12-aに対応するパケットを、上記出力ポート12-aと振り分け先の出力ポート12-bとに振り分ける際の振り分け比率を算出する振り分け処理部18を備えているからである。
【００６７】
また、本実施の形態では、輻輳度合いが最も少ない出力ポートを振り分け先の出力ポートとしているので、振り分け先の出力ポートの輻輳度合いが大きくなり、輻輳が発生する危険性を少なくすることができる。
【００６８】
[本発明の第２の実施の形態]
次に、本発明にかかるルータの第２の実施の形態について説明する。本実施の形態は、通常時に使用される本来の出力ポートと、振り分け先の出力ポートとにパケットを振り分ける際の振り分け比率を、パケットの破棄を検出した出力ポートのパケット破棄検出率だけでなく、パケットの破棄を検出したルータからパケットを破棄したルータまでのホップ数も考慮して決定するようにしたことを特徴とする。
【００６９】
図１０を参照すると、本実施の形態にかかるルータ1aは、パケット破棄検出部17の代わりにパケット破棄検出部17aを備えている点、振り分け処理部18の代わりに振り分け処理部18aを備えている点、ホップ数調査部19が追加されている点、及び、ホップ数記憶部20が追加されている点で図１に示したルータ１と相違している。
【００７０】
パケット破棄検出部17aは、自ルータ1aから出力したパケットが破棄されたことを検出した場合、ホップ数調査部19に対して、自ルータ1aからパケットを破棄したルータまでのホップ数を調査することを指示する機能を有する。より具体的には、図４のステップＳ43でパケットが破棄されたことを検出した場合は、ヘッダ情報管理部15から渡されたパケット（再送パケット）から宛先を抽出し、抽出した宛先を宛先として含んだホップ数調査指示をホップ数調査部19に渡す。また、ステップＳ45でパケットが破棄されたことを検出した場合は、ヘッダ情報管理部15から渡されたパケット(ACKパケット)から送信元を抽出し、抽出した送信元を宛先として含んだホップ数調査指示をホップ数調査部19に渡す。
【００７１】
ホップ数調査部19は、パケット破棄検出部17aから宛先を含んだホップ数調査指示が渡されると、自ルータ1aからパケットを破棄したルータまでのホップ数を調査するため、宛先を上記パケット破棄検出部17aから渡された宛先とし、送信元を自ルータ1aのIPアドレスとしたホップ数調査用パケットを、そのTTL(Time to Live)を1，2，3・・・と１つずつ増やしながら、パケット転送部13を介してネットワークへ送出し、そのパケットに対する確認応答パケットがあるか否かを確認する。そして、確認応答パケットがなくなったTTLの値を、自ルータ1aからパケットを破棄したルータまでのホップ数と認識し、そのホップ数と、上記ホップ数調査用パケットの宛先に対応した出力ポートのポート番号と関連付けてホップ数記憶部20に記録する。
【００７２】
また、ホップ数調査部19は、ホップ数調査用パケットをパケット転送部13を介して受信した場合、TLLが「１」であれば、それに対する確認応答パケットをパケット転送部13を介してホップ数調査用パケットの送信元に返信する。
【００７３】
パケット転送部13は、ホップ数調査部19から渡されたホップ数調査用パケットを、出力ポート12-1〜12-kの内の、上記ホップ数調査用パケットの宛先に対応した出力ポートから出力する。また、パケット転送部13は、ホップ数調査用パケットに対する確認応答パケットを受信した場合には、それをホップ数調査部19に渡す。
【００７４】
振り分け処理部18aは、パケット破棄検出率が第１の閾値Th1を超えている出力ポートに対する重みAと、パケットの振り分け先とする出力ポートに対する重みとを式（４）、（５）により算出し、A：Bを上記２つの出力ポートへのパケットの振り分け比率とする。
【００７５】
Ａ＝１−（Ｐa＋１／Ｍ） ……（４）
Ｂ＝Ｐa＋１／Ｍ ……（５）
尚、式（４）、（５）において、Mは、自ルータ1aからパケットを破棄したルータまでのホップ数、Ｐaはパケット破棄検出率である。
【００７６】
ここで、自ルータからパケットを破棄したルータまでのホップ数が少ないほど、自ルータから出力したパケットが破棄される危険性が高くなる。そこで、本実施の形態では、パケット破棄検出率が閾値Th1を超える出力ポートとパケットの振り分け先にする出力ポートへのパケットの振り分け比率を上記式（４）、（５）に示すものとし、パケットを破棄したルータまでのホップ数が少ない場合ほど、パケット破棄検出率が閾値Th1を超える出力ポートに振り分けるパケット数を少なくしているので、輻輳が発生する危険を第１の実施の形態よりも更に少なくすることができる。
【００７７】
次に、本実施の形態の動作について説明する。ここでは、第１の実施の形態との相違部分について説明する。
【００７８】
パケット破棄検出部17aは、図４のステップＳ43でパケットが破棄されたと判定した場合は、第１の実施の形態のパケット破棄検出部17が行う処理に加え、ヘッダ情報管理部15から渡されたパケット（再送パケット）から宛先を抽出し、抽出した宛先を宛先として含んだホップ数調査指示をホップ数調査部19に渡す。また、ステップＳ45でパケットが破棄されたと判定した場合は、第１の実施の形態のパケット破棄検出部17が行う処理に加え、ヘッダ情報管理部15から渡されたパケット(ACKパケット)から送信元を抽出し、抽出した送信元を宛先として含んだホップ数調査指示をホップ数調査部19に渡す。
【００７９】
ホップ数調査部19は、パケット破棄検出部17aから宛先を含んだホップ数調査指示が渡されると、TLLを「１」、宛先をホップ数調査指示中の宛先、送信元を自ルータ1aのIPアドレスとしたホップ数調査用パケットを作成し、それをパケット転送部13に渡す（図１１のステップＳ111、S112）。その後、ホップ数調査部19は、確認応答パケットの受信待ち状態になる。一方、ホップ数調査部19からホップ数調査用パケットを渡されたパケット転送部13は、ルーティングテーブル14を参照し、ホップ数調査用パケットを該当する出力ポートから出力する。
【００８０】
ルータ1aから出力されたホップ数調査用パケットは、隣接ルータで受信される。隣接ルータ内のパケット転送部13は、受信したホップ数調査用パケットをホップ数調査部19に渡すと共に、ルーティングテーブル14を参照し、該当する出力ポートを介して隣接ノードに送信する。尚、ホップ数調査用パケットを出力する際にはそのTTLを−１してから出力する。また、−１したことにより、TTLが「０」になった場合には、ホップ数調査用パケットを出力ポートから出力することなく、破棄する。また、パケット転送部13からホップ数調査用パケットを渡されたホップ数調査部19は、そのTTLが「１」であれば、確認応答パケットをパケット転送部13に渡し、ホップ数調査用パケットの送信元のルータ1aへ返信する。尚、ホップ数調査用パケットを受信したノードが、ルータ1aからのパケットを破棄した輻輳しているノードである場合は、ホップ数調査用パケットが破棄され、確認応答パケットがルータ1aに返送されない可能性が高い。
【００８１】
一方、ホップ数調査用パケットの送信元ルータ1a内のパケット転送部13は、ホップ数調査用パケットに対する確認応答パケットを受信すると、それをホップ数調査部19に渡す。確認応答パケットの受信待ち状態にあるホップ数調査部19は、ホップ数調査用パケットを送信してから一定時間内に確認応答パケットを受信した場合（図１１のステップＳ113がYES）は、TTLをインクリメントしたホップ数調査用パケットを作成し、パケット転送手段13に渡す（ステップＳ116、S112）。
【００８２】
これに対して、一定時間が経過しても確認応答パケットを受信できなかった場合（ステップＳ114がYES）は、現時点のTTLの値を、自ルータ1aからパケットを破棄したルータまでのホップ数と認識し、そのホップ数とホップ数調査用パケットを出力した出力ポートのポート番号とを関連付けてホップ数記憶部20に記録する（ステップＳ115）。
【００８３】
次に、振り分け処理部18aの動作を説明する。図１に示した第１の実施の形態の振り分け処理部18との相違点は、図５のステップＳ58の処理だけであるので、以下では、この点についてだけ説明する。
【００８４】
本実施の形態では、振り分け処理部18aは、ステップＳ58において、前出した式（４）、（５）に示す演算を行うことにより、パケット破棄検出率が閾値Th1を超えた出力ポート12-aと、パケットの振り分け先にする出力ポート12-bとの重みA，Bを算出し、A：Bを振り分け比率とする。その他の動作は、図１に示した振り分け処理部18aと同じである。
【００８５】
[第２の実施の形態の効果]
本実施の形態によれば、第１の実施の形態よりも更に輻輳が発生する危険性を少なくすることができる。その理由は、パケット破棄検出率が第１の閾値Th1を超える出力ポート12-aと振り分け先の出力ポート12-bへパケットを振り分ける際の振り分け比率を算出する際、自ルータ1aからパケットを破棄したルータまでのホップ数も考慮して振り分け比率を算出する振り分け処理部18aを備えているからである。
【産業上の利用可能性】
【００８６】
本発明は、ルータ、L3スイッチなどのパケット中継装置に利用可能である。
【符号の説明】
【００８７】
1, 1a ルータ
11-1〜11-j 入力ポート
12-1〜12-k 出力ポート
13 パケット転送部
14 ルーティングテーブル
15 ヘッダ情報管理部
15-1〜15-k 送出パケット数カウンタ
16 管理テーブル
17,17a パケット破棄検出部
17-1〜17-k パケット破棄検出カウンタ
18, 18a 振り分け処理部
19 ホップ数調査部
20 ホップ数記憶部
【技術分野】
【０００１】
本発明は、パケットを中継するルータ、L3（レイヤー３）スイッチ等のパケット中継装置に関する。
【背景技術】
【０００２】
近年のデータ通信利用者の著しい増加に伴って、インターネット等のネットワークを流れるデータは急激に増加している。インターネットは、IP(Internet Protocol)により経路制御を行うネットワークであり、ネットワーク上には、パケットを中継するためのルータ等のパケット中継装置が多数存在する。
【０００３】
パケット中継装置では、RIP(Routing Information Protocol)や、OSPF(Open Shortest Path First)などのルーティングプロトコルを使用して、相手IPアドレス毎にコストの和が最小となる最適経路を計算し、ルーティングテーブルに経路情報として記録する。パケット中継装置は、パケットを受信すると、その宛先IPアドレスに基づいてルーティングテーブルから経路情報を検索し、この経路情報によって特定される出力ポートからパケットを送出する。尚、ルーティングテーブルの内容は、定期的または経路情報に変更が発生した場合に更新される。
【０００４】
上記したようなRIPやOSPFといった既存のルーティングプロトコルに依存したパケット中継装置が利用する経路は、最適経路として求めた唯一の経路であるため、その経路にトラヒックが集中した場合には、パケット中継装置に輻輳が発生し、パケットが破棄されてしまうという問題がある。また、パケットが破棄されると、再送処理が行われるため、遅延時間が増加してしまうという問題も発生する。
【０００５】
そこで、このような問題点を解決するため、次のような技術が提案された（例えば、特許文献１参照）。特許文献１に記載されている技術では、先ず、隣接ルータ間のリンクのトラフィック量に基づいて上記リンクに輻輳が発生しているか否かを判定する。そして、輻輳が発生している場合には、上記リンクを含む輻輳部分を限定する。その後、上記輻輳部分を迂回する負荷分散経路を検索し、この検索した負荷分散経路と輻輳部分を含む元々の経路との両方の経路を用いてパケットをルーティングする。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００３−２４４１９６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
特許文献１に記載されている技術によれば、負荷分散経路と元々の経路との２つ経路に負荷を分散させることができるので、輻輳が発生する危険性を少なくすることができる。しかし、特許文献１には、どのような比率で負荷分散経路と元々の経路とにパケットを振り分けるかについては全く記載されておらず、輻輳が発生する危険性を十分には少なくすることができないという問題があった。例えば、元々の経路のトラフィック量が非常に大きい場合に、負荷分散経路へのパケットの振り分け率が小さいと、輻輳状態が改善されないこともある。
【０００８】
[発明の目的]
そこで、本発明の目的は、輻輳が発生する危険性を十分には少なくすることができないという課題を解決したパケット中継装置を提供することにある。
【課題を解決するための手段】
【０００９】
本発明にかかる第１のパケット中継装置は、
パケットを入力する複数の入力ポートと、
パケットを出力する複数の出力ポートと、
前記出力ポート毎に、その出力ポートから出力されたパケットの破棄を検出するパケット破棄検出部と、
該パケット破棄検出部の検出結果に基づいて前記出力ポート毎の輻輳度合いを算出し、該算出した輻輳度合いが閾値を超える第１の出力ポートについては、パケットの振り分け先にする第２の出力ポートを前記複数の出力ポートの中から選択すると共に、前記第１の出力ポートの輻輳度合いに基づいて、宛先が前記第１の出力ポートに対応するパケットを前記第１の出力ポートと前記第２の出力ポートとに振り分ける際の振り分け比率を算出する振り分け処理部と、
前記入力ポートから入力された宛先が前記第１の出力ポートに対応するパケットを、前記振り分け処理部で算出された振り分け比率に従って前記第１の出力ポートと前記第２の出力ポートとに振り分けるパケット転送部とを備える。
【００１０】
本発明にかかるパケット中継方法は、
パケットを入力する複数の入力ポートと、パケットを出力する複数の出力ポートと、パケット転送部と、パケット破棄検出部と、振り分け処理部とを備えたコンピュータが実行するパケット中継方法であって、
前記パケット破棄検出部が、前記出力ポート毎に、その出力ポートから出力されたパケットの破棄を検出し、
前記振り分け処理部が、前記パケット破棄検出部の検出結果に基づいて前記出力ポート毎の輻輳度合いを算出し、該算出した輻輳度合いが閾値を超える第１の出力ポートについては、パケットの振り分け先にする第２の出力ポートを前記複数の出力ポートの中から選択すると共に、前記第１の出力ポートの輻輳度合いに基づいて、宛先が前記第１の出力ポートに対応するパケットを前記第１の出力ポートと前記第２の出力ポートとに振り分ける際の振り分け比率を算出し、
前記パケット転送部が、前記入力ポートから入力された宛先が前記第１の出力ポートに対応するパケットを、前記振り分け処理部で算出された振り分け比率に従って前記第１の出力ポートと前記第２の出力ポートとに振り分ける。
【００１１】
本発明にかかるプログラムは、
パケットを入力する複数の入力ポートと、パケットを出力する複数の出力ポートとを備えたコンピュータをパケット中継装置として機能させるためのプログラムであって、
前記コンピュータを、
該パケット破棄検出部の検出結果に基づいて前記出力ポート毎の輻輳度合いを算出し、該算出した輻輳度合いが閾値を超える第１の出力ポートについては、パケットの振り分け先にする第２の出力ポートを前記複数の出力ポートの中から選択すると共に、前記第１の出力ポートの輻輳度合いに基づいて、宛先が前記第１の出力ポートに対応するパケットを前記第１の出力ポートと前記第２の出力ポートとに振り分ける際の振り分け比率を算出する振り分け処理部、
前記入力ポートから入力された宛先が前記第１の出力ポートに対応するパケットを、前記振り分け処理部で算出された振り分け比率に従って前記第１の出力ポートと前記第２の出力ポートとに振り分けるパケット転送部として機能させる。
【発明の効果】
【００１２】
本発明によれば、輻輳が発生する危険性を十分に少なくすることができるという効果を得ることができる。
【図面の簡単な説明】
【００１３】
【図１】本発明の第１の実施の形態にかかるルータの構成例を示すブロック図である。
【図２】ルーティング14の内容例を示す図である。
【図３】ヘッダ情報管理部15の処理例を示すフローチャートである。
【図４】パケット破棄検出部17の処理例を示すフローチャートである。
【図５】振り分け処理部18の処理例の一部を示すフローチャートである。
【図６】振り分け処理部18の処理例の残りの部分を示すフローチャートである。
【図７】パケット転送部13の処理例を示すフローチャートである。
【図８】パケット破棄検出部17の動作を説明するための図である。
【図９】輻輳が解消される様子を示した図である。
【図１０】本発明の第２の実施の形態にかかるルータの構成例を示す図である。
【図１１】ホップ数調査部19の処理例を示すフローチャートである。
【発明を実施するための形態】
【００１４】
次に、本発明の実施の形態について図面を参照して詳細に説明する。
【００１５】
[本発明の第１の実施の形態]
図１を参照すると、本発明の第１の実施の形態にかかるルータ１は、複数の入力ポート11-1〜11-jと、複数の出力ポート12-1〜12-kと、パケット転送部13と、ルーティングテーブル14と、ヘッダ情報管理部15と、管理テーブル16と、パケット破棄検出部17と、振り分け処理部18とを備えている。
【００１６】
入力ポート11-1〜11-jには、隣接ルータ（図示せず）からのパケットが入力される。出力ポート12-1〜12-kからは、隣接ルータへのパケットが出力される。
【００１７】
ルーティングテーブル14には、図２に示すように、パケットの宛先（IPアドレス）に関連付けて、該当するパケットの出力先にする本来の出力ポートのポート番号（通常時）が記録されている。更に、本実施の形態のルーティングテーブル14は、パケットを元々の出力ポート以外の出力ポートにも振り分ける際に出力先にする出力ポートのポート番号（振り分け時）と、振り分け比率とが記録できるようになっている。振り分け比率は、通常時に出力先にしている元々の出力ポートと、振り分け時に出力先にする出力ポートとへ、どのような比率でパケットを振り分けるのかを示すものである。図２の例は、宛先がA1のパケットは、出力ポート番号P12-1の出力ポートへ出力され、宛先がA2のパケットは、出力ポート番号がP12-2, P12-kの出力ポートに、X:Yの比率で振り分けられることを示している。
【００１８】
パケット転送部13は、入力ポート11-1〜11-jから入力されたパケットの出力先にする出力ポートを、パケットの宛先とルーティングテーブル14の内容とに基づいて決定し、その出力ポートへパケットを出力する。
【００１９】
ヘッダ情報管理部15は、出力ポート12-1〜12-kに対応する送出パケット数カウンタ15-1〜15-kを備えており、入力ポート11-1〜11-jを介してパケットが入力されると、ルーティングテーブル14を参照してパケットの出力先にする出力ポートを求め、その出力ポートに対応する送出パケット数カウンタのカウント値をインクリメント（本実施の形態では+1）する。更に、ヘッダ情報管理部15は、入力されたパケットのIPヘッダ内のプロトコルフィールドがTCP(Transmission Control Protocol)であれば、そのパケットのヘッダ情報を管理テーブル16に記録すると共に、上記パケットをパケット破棄検出部17に渡す。尚、入力されたパケットが、コネクションで最初のパケットである場合には、そのヘッダ情報を管理テーブル16に記録する処理を行うだけで、パケットをパケット破棄検出部17に渡す処理は行わない。また、入力されたパケットがコネクションの切断を指示すものである場合は、上記コネクションに関連するヘッダ情報（宛先IPアドレス、宛先ポート番号、送信元IPアドレス及び送信元ポート番号が上記パケットと同じヘッダ情報と、宛先IPアドレス、宛先ポート番号、送信元IPアドレス及び送信元ポート番号が上記パケットの送信元IPアドレス、送信元ポート番号、宛先IPアドレス及び宛先ポート番号に入れ替わっているヘッダ情報）を管理テーブル16から削除する。
【００２０】
パケット破棄検出部17は、出力ポート12-1〜12-kに対応する破棄検出カウンタ17-1〜17-kを備えている。そして、ヘッダ情報管理部15からパケットが渡されると、そのパケットと、管理テーブル16に記録されているヘッダ情報とに基づいて自ルータ１から出力したパケットがネットワーク上で破棄されたか否かを判定する。そして、破棄されたと判定した場合は、ヘッダ情報管理部15から渡されたパケットと、ルーティングテーブル14の内容とに基づいて、破棄されたパケットを出力した出力ポートを求め、その出力ポートに対応する破棄検出カウンタのカウント値をインクリメントする。
【００２１】
振り分け処理部18は、下記(A)〜(F)の機能を有する。
【００２２】
(A)出力ポート12-1〜12-kそれぞれの輻輳度合いを算出する機能。本実施の形態では、一定時間の間に出力ポート12-a（１≦ａ≦ｋ）から出力されたパケットの総数に対する、上記一定時間の間に出力ポート12-aから出力されて破棄されたパケットの割り合いを示すパケット破棄検出率を出力ポート12-aの輻輳度合いとする。ここで、出力ポート12-aから出力されたパケットの総数をT、破棄されたパケット数をNとすると、パケット破棄検出率Paは、次式（ａ）に示すものとなる。
【００２３】
Ｐa＝Ｎa／Ｔa ……（１）
【００２４】
なお、輻輳度合いはこれに限られるものではなく、一定時間の間に破棄されたパケットの数などを使用することもできる。また、一定時間の間に出力ポート12-aから出力されたパケットの総数および破棄されたパケットの数は、それぞれ送出パケット数カウンタ15-aおよび破棄検出カウンタ17-aを参照することにより求めることができる。
【００２５】
(B) 出力ポート12-1〜12-k毎に、そのパケット破棄検出率が予め定められている第１の閾値Th1を超えているか否かを判定する機能。
【００２６】
(C)パケット破棄検出率が閾値Th1を超えている出力ポート12-aについては、他の出力ポートの中からパケットの振り分け先にする出力ポート12-b（１≦ｂ≦ｋ）を選択する機能。本実施の形態では、パケット破棄検出率が最も小さい出力ポートを振り分け先の出力ポートとして選択する。
【００２７】
(D)宛先が上記出力ポート12-aに対応するパケットを、上記出力ポート12-aと上記出力ポート12-bとに振り分ける際の振り分け比率を算出する機能。本実施の形態では、出力ポート12-a、12-bの重みA, Bをそれぞれ式（２）、（３）により算出し、A：Bを振り分け比率とする。
【００２８】
Ａ＝１−Ｐa ……（２）
Ｂ＝Ｐa ……（３）
なお、Ｐaは前述したように、出力ポート12-aのパケット破棄検出率である。
【００２９】
(E)振り分け先の出力ポート12-bのポート番号と、パケットの振り分け比率A：Bとを、出力ポート12-aと対応する宛先に関連付けてルーティングテーブル14に記録する機能。
【００３０】
(F)出力ポート12-1〜12-k毎に、そのパケット破棄検出率が予め定められている第２の閾値Th2未満であるか否かを判定し、閾値Th2未満の出力ポートについては、ルーティングテーブル14に振り分け先の出力ポートのポート番号が設定されているか否かを判定し、設定されている場合には、ルーティングテーブル16から振り分け先の出力ポートのポート番号およびパケットの振り分け比率を削除する機能。なお、第１、第２の閾値Th1,Th2は、Th1＞Th2の関係を有している。
【００３１】
パケット転送部13、ヘッダ情報管理部15、パケット破棄検出部17、及び、振り分け処理部18はCPU（中央処理装置）により実現可能であり、その場合には例えば次のようにする。CPUをパケット転送部13、ヘッダ情報管理部15、パケット破棄検出部17、及び、振り分け処理部18として機能させるためのプログラムを記録したディスク、半導体メモリ、その他の記録媒体を用意し、CPUに上記プログラムを読み取らせる。CPUは、読み取ったプログラムに従って自身の動作を制御することにより、自CPU上にパケット転送部13、ヘッダ情報管理部15、パケット破棄検出部17、及び、振り分け処理部18を実現する。
【００３２】
次に、本実施の形態の動作について詳細に説明する。
【００３３】
入力ポート11-1〜11-jから入力されたパケットは、パケット転送部13およびヘッダ情報管理部15に渡される。
【００３４】
これにより、パケット転送部13は、渡されたパケットの宛先と、ルーティングテーブル14の内容とに基づいて、パケットの出力先にする出力ポートを決定し、決定した出力ポートからパケットを出力する。このパケットは、隣接ルータとの間の経路を介して隣接ルータへ転送される。
【００３５】
一方、ヘッダ情報管理部15は、パケットが渡されると、出力ポート12-1〜12-k毎の送出パケット数カウンタ15-1〜15-kの内の、上記パケットの出力先になる出力ポートと対応するカウンタのカウント値をインクリメントする（図３のステップＳ31）。なお、パケットの出力先となる出力ポートは、ルーティングテーブル14から検索できる。
【００３６】
その後、ヘッダ情報管理部15は、パケットのIPヘッダ内のプロトコルフィールドの内容がTCPになっているか否かを判定する（ステップＳ32）。そして、プロトコルフィールドの内容がUDP(User datagram Protocol)など、TCP以外のものであった場合（ステップＳ32がNO）は、パケットを破棄する（ステップＳ33）。
【００３７】
これに対して、プロトコルフィールドの内容がTCPである場合（ステップＳ32がYES）は、現在処理対象にしているパケットと同一コネクションのパケットのヘッダ情報が管理テーブル16に記録されているか否かを判定する（ステップＳ34）。この判定は、宛先IPアドレス、宛先ポート番号、送信元IPアドレス、及び、送信元ポート番号が、現在処理対象にしているパケットと同一のヘッダ情報、または、宛先IPアドレス、宛先ポート番号、送信元IPアドレス、及び、送信元ポート番号が上記パケットの送信元IPアドレス、送信元ポート番号、宛先IPアドレス、及び、宛先ポート番号に入れ替わっているヘッダ情報が記録されているか否かを判定することにより行う。
【００３８】
ここで、プロトコルフィールドがTCPになっているパケットのヘッダ情報だけを管理テーブル16に記録しているのは、後述するように、本実施の形態では、パケットの破棄をTCPによる再送パケット及び確認応答パケット（ACKパケット）に基づいて検出するようにしているからである。
【００３９】
そして、現在処理対象にしているパケットとコネクションが同一のヘッダ情報が管理テーブル16に記録されていない場合（ステップＳ34がNO）は、上記パケットのヘッダ情報を管理テーブル16に記録すると共に、ヘッダ情報に関連付けてACK到着フラグを記録する（ステップＳ35）。ACK到着フラグは、上記ヘッダ情報を含んだパケットに対するACKパケットが到着しているか否かを示すものであり、初期状態では、ACK到着フラグは“０”となっている。即ち、初期状態においては、ACK到着フラグは、ACKパケットが到着していないことを表示している。
【００４０】
これに対して、コネクションが同一のヘッダ情報が管理テーブル16に記録されている場合（ステップＳ34がYES）は、パケットのヘッダ情報およびACK到着フラグを管理テーブル16に記録すると共に、上記パケットをパケット破棄検出部17に渡す（ステップＳ36，37）。
【００４１】
パケット破棄検出部17は、ヘッダ情報管理部15からパケットが渡されると、そのヘッダ部にACKフラグが立っているか否か、即ちACKフラグが“１”になっているか否かを判定する（図４のステップＳ41）。
【００４２】
そして、ACKフラグが“０”の場合（ステップＳ41がNOの場合）は、処理対象にしているパケットが送信側から再送されたパケットであるか否かを判定する（ステップＳ42）。この判定は、現在処理対象にパケットと同一コネクションのヘッダ情報であって、確認応答番号およびシーケンス番号が上記パケットと同一のヘッダ情報が管理テーブル16に記録されているか否かに基づいて行う。
【００４３】
そして、処理対象にしているパケットが再送パケットでない場合（ステップＳ42がNO）は、パケット破棄検出部17は、その処理を終了する。これに対して、処理対象にしているパケットが再送パケットである場合（ステップＳ42がYES）は、パケットが破棄されたものと判定し、出力ポート12-1〜12-k毎に設けられている破棄検出カウンタ17-1〜17-kの内の、上記パケットの出力先となる出力ポートに対応する破棄検出カウンタをインクリメントする（ステップＳ43)。今、例えば、図８(A)に示すように、送信側ノードから受信側ノードに対してパケットP1を送信したが、ルータR2でパケットP1が破棄されたとすると、送信側ノードはACKパケットが戻ってこないので、パケットP1を再送することになる。このような場合、ルータR3~R5内のパケット破棄検出部17では、ステップＳ42の判定結果がYESとなり、パケットP1が破棄されたと判定される。
【００４４】
また、ヘッダ情報管理部15から渡されたパケットにACKフラグが立っている場合、即ち、ヘッダ情報管理部15から渡されたパケットがACKパケットである場合（ステップＳ41がYES）は、管理テーブル16に記録されているACK到着フラグの内の、上記ACKパケットによって正常受信を知らせようとしているパケットのヘッダ情報と関連付けられているACK到着フラグが“１”になっているか否かを判定する（ステップＳ44）。なお、上記ACK到着フラグが関連付けられているヘッダ情報は、上記ACKパケットと同一コネクションのパケットのヘッダ情報の内の、確認応答番号が上記ACKパケット中のシーケンス番号と一致するヘッダ情報である。
【００４５】
そして、ACK到着フラグが“０”の場合（ステップＳ44がNO）は、受信側ノードにおいて、パケットが正常に受信され、ACKパケットが返されたことになるので、ACK到着フラグを“１”に変更する（ステップＳ46）。
【００４６】
これに対して、ACK到着フラグが“１”の場合（ステップＳ44がYES）は、パケットが破棄されたと判定し、出力ポート12-1〜12-k毎の破棄検出カウンタ17-1〜17-kの内の、ACKパケットによって正常受信を通知しようとしたパケットを出力した出力ポートに対応する破棄検出カウンタをインクリメントする（ステップＳ45）。今、例えば図８（Ｂ）に示すように、送信側ノードから受信側ノードに対してパケットP1〜P4が連続して送信され、パケットP2がルータR2において破棄されたとする。TCPが適用されている受信側ノードでは、パケットP1を受信することにより、パケットP1に対するACKパケットACK１を送信側ノードへ返す。その後、受信側ノードは、パケットP2がルータR2で破棄されているので、パケットP3を受信する。TCPが適用されている受信側ノードでは、パケットの受信時、受信に成功した最後のパケットに対するACKパケットを送信側ノードに送信する。この例の場合、受信に成功した最後のパケットは、パケットP1であるので、受信側ノードは、パケットP3, P4の受信時にも、パケットP1の受信時に送信したACKパケットACK1を送信側ノードに返す。このような場合、ルータR3〜R5内のパケット破棄検出部17では、ステップＳ44の判定結果がYESとなり、パケットが破棄されたと判定する。
【００４７】
次に、図５、図６のフローチャートを参照して振り分け処理部18の処理を説明する。振り分け処理部18は、一定時間毎に、図５、図６のフローチャートに示す処理を実行する。
【００４８】
先ず、振り分け処理部18は、出力ポート12-1〜12-kの内の１つに注目し、注目している出力ポート（例えば、出力ポート12-a）のパケット破棄検出率Paを算出する（ステップＳ51,Ｓ53）。具体的には、出力ポート12-aに対応する送出パケット数カウンタ15-aのカウント値Taと、破棄検出カウンタ17-aのカウント値Naとを入力し、前出の式（１）に示す演算を行うことにより、出力ポート12-aのパケット破棄検出率Pa＝Na／Taを算出する。その後、振り分け処理部18は、次の出力ポートに注目し、前述した処理と同様の処理を行う。
【００４９】
全ての出力ポート12-1〜12-kに対して前述した処理と同様の処理を行うと（ステップＳ52がYES）、振り分け処理部18は、再び出力ポート12-1〜12-kの内の１つに注目し、注目している出力ポート（例えば、出力ポート12-a）のパケット破棄検出率Paが予め定められている第１の閾値Th1を超えているか否かを判定する（ステップＳ54，Ｓ56）。
【００５０】
そして、パケット破棄検出率Paが第１の閾値Th1を超えている場合（ステップＳ56がYES）は、他の出力ポート（出力ポート12-a以外の出力ポート）の中からパケットの振り分け先にする出力ポート12-bを１つ選択する（ステップＳ57）。本実施の形態では、出力ポート12-a以外の出力ポートの中から、パケット破棄検出率が最も小さな出力ポートを振り分け先の出力ポート12-bとして選択する。
【００５１】
その後、振り分け処理部18は、宛先が出力ポート12-aに対応するパケットを、出力ポート12-aと振り分け先の出力ポート12-bとに振り分ける際の振り分け比率を算出する（ステップＳ58）。具体的には、前出の式（２）、（３）に示した演算を行うことにより、出力ポート12-a,12-bに対する重みA＝1−Pa、B＝Paを算出し、A：B＝（1−Pa）：Paをパケットの振り分け比率とする。
【００５２】
次に、振り分け処理部18は、本来なら出力ポート12-aを出力先にするパケットが、出力ポート12-bへも振り分けられるようにするため、ルーティングテーブル16の内容を更新する（ステップＳ59）。具体的には、ルーティングテーブル14に記録されている宛先（IPアドレス）の内の、通常時の出力先が出力ポート12-aとなっている宛先に関連付けて、出力ポート12-bのポート番号と、パケットの振り分け比率（1−Pa）：Paを記録する。このように、ルーティングテーブル14に振り分け先の出力ポート12-bのポート番号と、振り分け比率（1−Pa）：Paとを記録することにより、通常は出力ポート12-aに振り分けられるパケットの一部が、出力ポート12-bに振り分けられることになる。ここで、出力ポート12-aのパケット破棄検出率Paが大きくなるほど、出力ポート12-aに振り分けられるパケットの割合を少なくすることができるので、ルータ１が配置されているネットワークにおいて輻輳が発生する危険性を極めて少なくすることができる。
【００５３】
その後、振り分け処理部18は、次の出力ポートに注目し（ステップＳ54）、前述した処理と同様の処理を行う。
【００５４】
ステップＳ56において、出力ポート12-aのパケット破棄検出率Paが第１の閾値Th1を超えていると判定された場合が上述した処理が行われる。これに対して、ステップＳ56において、パケット破棄検出率Paが閾値Th1以下であると判定された場合（ステップＳ56がNO）は、次のような処理が行われる。
【００５５】
振り分け処理部18は、ステップＳ56において、出力ポート12-aのパケット破棄検出率Paが閾値Th1以下であると判定すると、図６のフローチャートに示すように、パケット破棄検出率Paが第２の閾値Th2未満か否かを判定する（ステップＳ62）。
【００５６】
そして、出力ポート12-aのパケット破棄検出率Paが第２の閾値Th2以上である場合（ステップＳ62がNO）は、図５のステップＳ54の処理に戻り、次の出力ポートを注目する。これに対して、パケット破棄検出率Paが第２の閾値Th2未満である場合（ステップＳ62がYES）は、ルーティングテーブル14を参照し、出力ポート12-aのポート番号（通常時）に関連付けて、振り分け先の出力ポートのポート番号および振り分け率が記録されているか否かを判定する（ステップＳ63）。
【００５７】
そして、記録されていない場合は、図５のステップＳ54の処理に戻り、次の出力ポートに注目する。これに対して、記録されている場合は、出力ポート12-bのポート番号および振り分け比率をルーティングテーブル14から削除する（ステップＳ64）。これにより、出力ポート12-bへはパケットが振り分けられなくなり、通常時に使用する本来の出力ポート12-aのみにパケットが振り分けられるようになる。その後、振り分け処理部18は、図５のステップＳ54の処理に戻り、次の出力ポートに注目する。
【００５８】
上述した処理を繰り返し行い、未注目の出力ポートがなくなると（図５のステップＳ55がYES）と、振り分け処理部18は、図６のフローチャートに示すように、送出パケット数カウンタ15-1〜15-kおよびパケット破棄検出カウンタ17-1〜17-kをクリアし（ステップＳ61）、その処理を終了する。
【００５９】
次に、図７のフローチャートを参照してパケット転送部13の動作を説明する。
【００６０】
パケット転送部13は、入力ポート11-1〜11-jを介してパケットが入力されると、先ず、パケットから宛先（IPアドレス）を抽出する（ステップＳ71）。その後、パケット転送部13は、ステップＳ71で抽出した宛先をキーにしてルーティングテーブル14を検索する（ステップＳ72）。
【００６１】
そして、検索結果が通常時にパケットの出力先にする本来の出力ポートのポート番号だけである場合（ステップＳ73がNO）は、上記本来の出力ポートにパケットを出力する（ステップＳ74）。
【００６２】
これに対して、検索結果に、本来の出力ポートのポート番号に加え、振り分け先の出力ポートのポート番号および振り分け比率も含まれている場合（ステップＳ73がYES）は、本来の出力ポートと振り分け先の出力ポートとの内の、どちらをパケットの出力先にするかを決定する（ステップＳ75）。パケットの出力先の決定方法としては、種々の方法を採用することができ、例えば、次のような方法を採用することができる。パケットの振り分けを開始してから現時点までに、本来の出力ポートに出力したパケット数、および、振り分け先の出力ポートに出力したパケット数をカウントする第１及び第２のカウンタを用意する。パケットの出力先を決定する際には、上記第１、第２のカウンタのカウント値に基づいて、どちらの出力ポートにパケットを出力した方が、実際のパケットの振り分け比率が、ルーティングテーブル14に設定されている振り分け比率に近くなるか判定し、近くなると判定した方の出力ポートをパケットの出力先に決定する。その後、パケット転送部13は、通常時に使用する出力ポートと振り分け先の出力ポートとの内の、ステップＳ75で出力先に決定された出力ポートにパケットを出力する（ステップＳ76）。
【００６３】
例えば、ルーティングテーブル14の内容が図２に示すものであり、パケットの宛先が「A1」である場合には、出力ポート12-1のみにパケットが出力される。これに対して、パケットの宛先が「A2」の場合は、通常時に使用される出力ポート12-2と振り分け先の出力ポート12-kとに、X：Yの比率でパケットが出力される。
【００６４】
図９は、トラフィックの集中が解消される様子を示した図である。尚、図９に示したルータR1〜R6は、図１に構成を有するものである。
【００６５】
図９(A)に示すように、ルータR3にトラフィックが集中すると、同図(B)に示すように、ルータR3に輻輳が発生する。その後、同図(C)に示すように、ルータR1がパケットをルータR2に向けて出力する。このパケットは、輻輳が発生しているルータR3において破棄される。その後、ルータR1内のパケット破棄検出部17は、同図(D)に示すように、パケットが破棄されたことを検出する。そして、ルータR2へパケットを送信するための出力ポートのパケット破棄検出率が前述した第１の閾値Th1を超えている場合は、ルータR1内の振り分け処理部18がルーティングテーブル14の内容を変更し、同図(E)に示すように、元々使用していた出力ポートと振り分け先の出力ポートとにパケットを振り分けて出力する。
【００６６】
[第１の実施の形態の効果]
本実施の形態によれば、輻輳が発生する危険性を十分に少なくすることができるという効果を得ることができる。その理由は、パケット破棄検出率（輻輳度合い）が第１の閾値Th1を上回る出力ポート12-aのパケット破棄検出率に基づいて、宛先が出力ポート12-aに対応するパケットを、上記出力ポート12-aと振り分け先の出力ポート12-bとに振り分ける際の振り分け比率を算出する振り分け処理部18を備えているからである。
【００６７】
また、本実施の形態では、輻輳度合いが最も少ない出力ポートを振り分け先の出力ポートとしているので、振り分け先の出力ポートの輻輳度合いが大きくなり、輻輳が発生する危険性を少なくすることができる。
【００６８】
[本発明の第２の実施の形態]
次に、本発明にかかるルータの第２の実施の形態について説明する。本実施の形態は、通常時に使用される本来の出力ポートと、振り分け先の出力ポートとにパケットを振り分ける際の振り分け比率を、パケットの破棄を検出した出力ポートのパケット破棄検出率だけでなく、パケットの破棄を検出したルータからパケットを破棄したルータまでのホップ数も考慮して決定するようにしたことを特徴とする。
【００６９】
図１０を参照すると、本実施の形態にかかるルータ1aは、パケット破棄検出部17の代わりにパケット破棄検出部17aを備えている点、振り分け処理部18の代わりに振り分け処理部18aを備えている点、ホップ数調査部19が追加されている点、及び、ホップ数記憶部20が追加されている点で図１に示したルータ１と相違している。
【００７０】
パケット破棄検出部17aは、自ルータ1aから出力したパケットが破棄されたことを検出した場合、ホップ数調査部19に対して、自ルータ1aからパケットを破棄したルータまでのホップ数を調査することを指示する機能を有する。より具体的には、図４のステップＳ43でパケットが破棄されたことを検出した場合は、ヘッダ情報管理部15から渡されたパケット（再送パケット）から宛先を抽出し、抽出した宛先を宛先として含んだホップ数調査指示をホップ数調査部19に渡す。また、ステップＳ45でパケットが破棄されたことを検出した場合は、ヘッダ情報管理部15から渡されたパケット(ACKパケット)から送信元を抽出し、抽出した送信元を宛先として含んだホップ数調査指示をホップ数調査部19に渡す。
【００７１】
ホップ数調査部19は、パケット破棄検出部17aから宛先を含んだホップ数調査指示が渡されると、自ルータ1aからパケットを破棄したルータまでのホップ数を調査するため、宛先を上記パケット破棄検出部17aから渡された宛先とし、送信元を自ルータ1aのIPアドレスとしたホップ数調査用パケットを、そのTTL(Time to Live)を1，2，3・・・と１つずつ増やしながら、パケット転送部13を介してネットワークへ送出し、そのパケットに対する確認応答パケットがあるか否かを確認する。そして、確認応答パケットがなくなったTTLの値を、自ルータ1aからパケットを破棄したルータまでのホップ数と認識し、そのホップ数と、上記ホップ数調査用パケットの宛先に対応した出力ポートのポート番号と関連付けてホップ数記憶部20に記録する。
【００７２】
また、ホップ数調査部19は、ホップ数調査用パケットをパケット転送部13を介して受信した場合、TLLが「１」であれば、それに対する確認応答パケットをパケット転送部13を介してホップ数調査用パケットの送信元に返信する。
【００７３】
パケット転送部13は、ホップ数調査部19から渡されたホップ数調査用パケットを、出力ポート12-1〜12-kの内の、上記ホップ数調査用パケットの宛先に対応した出力ポートから出力する。また、パケット転送部13は、ホップ数調査用パケットに対する確認応答パケットを受信した場合には、それをホップ数調査部19に渡す。
【００７４】
振り分け処理部18aは、パケット破棄検出率が第１の閾値Th1を超えている出力ポートに対する重みAと、パケットの振り分け先とする出力ポートに対する重みとを式（４）、（５）により算出し、A：Bを上記２つの出力ポートへのパケットの振り分け比率とする。
【００７５】
Ａ＝１−（Ｐa＋１／Ｍ） ……（４）
Ｂ＝Ｐa＋１／Ｍ ……（５）
尚、式（４）、（５）において、Mは、自ルータ1aからパケットを破棄したルータまでのホップ数、Ｐaはパケット破棄検出率である。
【００７６】
ここで、自ルータからパケットを破棄したルータまでのホップ数が少ないほど、自ルータから出力したパケットが破棄される危険性が高くなる。そこで、本実施の形態では、パケット破棄検出率が閾値Th1を超える出力ポートとパケットの振り分け先にする出力ポートへのパケットの振り分け比率を上記式（４）、（５）に示すものとし、パケットを破棄したルータまでのホップ数が少ない場合ほど、パケット破棄検出率が閾値Th1を超える出力ポートに振り分けるパケット数を少なくしているので、輻輳が発生する危険を第１の実施の形態よりも更に少なくすることができる。
【００７７】
次に、本実施の形態の動作について説明する。ここでは、第１の実施の形態との相違部分について説明する。
【００７８】
パケット破棄検出部17aは、図４のステップＳ43でパケットが破棄されたと判定した場合は、第１の実施の形態のパケット破棄検出部17が行う処理に加え、ヘッダ情報管理部15から渡されたパケット（再送パケット）から宛先を抽出し、抽出した宛先を宛先として含んだホップ数調査指示をホップ数調査部19に渡す。また、ステップＳ45でパケットが破棄されたと判定した場合は、第１の実施の形態のパケット破棄検出部17が行う処理に加え、ヘッダ情報管理部15から渡されたパケット(ACKパケット)から送信元を抽出し、抽出した送信元を宛先として含んだホップ数調査指示をホップ数調査部19に渡す。
【００７９】
ホップ数調査部19は、パケット破棄検出部17aから宛先を含んだホップ数調査指示が渡されると、TLLを「１」、宛先をホップ数調査指示中の宛先、送信元を自ルータ1aのIPアドレスとしたホップ数調査用パケットを作成し、それをパケット転送部13に渡す（図１１のステップＳ111、S112）。その後、ホップ数調査部19は、確認応答パケットの受信待ち状態になる。一方、ホップ数調査部19からホップ数調査用パケットを渡されたパケット転送部13は、ルーティングテーブル14を参照し、ホップ数調査用パケットを該当する出力ポートから出力する。
【００８０】
ルータ1aから出力されたホップ数調査用パケットは、隣接ルータで受信される。隣接ルータ内のパケット転送部13は、受信したホップ数調査用パケットをホップ数調査部19に渡すと共に、ルーティングテーブル14を参照し、該当する出力ポートを介して隣接ノードに送信する。尚、ホップ数調査用パケットを出力する際にはそのTTLを−１してから出力する。また、−１したことにより、TTLが「０」になった場合には、ホップ数調査用パケットを出力ポートから出力することなく、破棄する。また、パケット転送部13からホップ数調査用パケットを渡されたホップ数調査部19は、そのTTLが「１」であれば、確認応答パケットをパケット転送部13に渡し、ホップ数調査用パケットの送信元のルータ1aへ返信する。尚、ホップ数調査用パケットを受信したノードが、ルータ1aからのパケットを破棄した輻輳しているノードである場合は、ホップ数調査用パケットが破棄され、確認応答パケットがルータ1aに返送されない可能性が高い。
【００８１】
一方、ホップ数調査用パケットの送信元ルータ1a内のパケット転送部13は、ホップ数調査用パケットに対する確認応答パケットを受信すると、それをホップ数調査部19に渡す。確認応答パケットの受信待ち状態にあるホップ数調査部19は、ホップ数調査用パケットを送信してから一定時間内に確認応答パケットを受信した場合（図１１のステップＳ113がYES）は、TTLをインクリメントしたホップ数調査用パケットを作成し、パケット転送手段13に渡す（ステップＳ116、S112）。
【００８２】
これに対して、一定時間が経過しても確認応答パケットを受信できなかった場合（ステップＳ114がYES）は、現時点のTTLの値を、自ルータ1aからパケットを破棄したルータまでのホップ数と認識し、そのホップ数とホップ数調査用パケットを出力した出力ポートのポート番号とを関連付けてホップ数記憶部20に記録する（ステップＳ115）。
【００８３】
次に、振り分け処理部18aの動作を説明する。図１に示した第１の実施の形態の振り分け処理部18との相違点は、図５のステップＳ58の処理だけであるので、以下では、この点についてだけ説明する。
【００８４】
本実施の形態では、振り分け処理部18aは、ステップＳ58において、前出した式（４）、（５）に示す演算を行うことにより、パケット破棄検出率が閾値Th1を超えた出力ポート12-aと、パケットの振り分け先にする出力ポート12-bとの重みA，Bを算出し、A：Bを振り分け比率とする。その他の動作は、図１に示した振り分け処理部18aと同じである。
【００８５】
[第２の実施の形態の効果]
本実施の形態によれば、第１の実施の形態よりも更に輻輳が発生する危険性を少なくすることができる。その理由は、パケット破棄検出率が第１の閾値Th1を超える出力ポート12-aと振り分け先の出力ポート12-bへパケットを振り分ける際の振り分け比率を算出する際、自ルータ1aからパケットを破棄したルータまでのホップ数も考慮して振り分け比率を算出する振り分け処理部18aを備えているからである。
【産業上の利用可能性】
【００８６】
本発明は、ルータ、L3スイッチなどのパケット中継装置に利用可能である。
【符号の説明】
【００８７】
1, 1a ルータ
11-1〜11-j 入力ポート
12-1〜12-k 出力ポート
13 パケット転送部
14 ルーティングテーブル
15 ヘッダ情報管理部
15-1〜15-k 送出パケット数カウンタ
16 管理テーブル
17,17a パケット破棄検出部
17-1〜17-k パケット破棄検出カウンタ
18, 18a 振り分け処理部
19 ホップ数調査部
20 ホップ数記憶部
【特許請求の範囲】
【請求項１】
パケットを入力する複数の入力ポートと、
パケットを出力する複数の出力ポートと、
前記出力ポート毎に、その出力ポートから出力されたパケットの破棄を検出するパケット破棄検出部と、
該パケット破棄検出部の検出結果に基づいて前記出力ポート毎の輻輳度合いを算出し、該算出した輻輳度合いが閾値を超える第１の出力ポートについては、パケットの振り分け先にする第２の出力ポートを前記複数の出力ポートの中から選択すると共に、前記第１の出力ポートの輻輳度合いに基づいて、宛先が前記第１の出力ポートに対応するパケットを前記第１の出力ポートと前記第２の出力ポートとに振り分ける際の振り分け比率を算出する振り分け処理部と、
前記入力ポートから入力された宛先が前記第１の出力ポートに対応するパケットを、前記振り分け処理部で算出された振り分け比率に従って前記第１の出力ポートと前記第２の出力ポートとに振り分けるパケット転送部とを備えたことを特徴とするパケット中継装置。
【請求項２】
請求項１記載のパケット中継装置において、
前記出力ポートの輻輳度合いは、一定時間の間に前記出力ポートから出力されたパケットの総数と、前記一定時間の間に前記出力ポートから出力されて破棄されたパケットの数との比率を示すパケット破棄検出率であることを特徴とするパケット中継装置。
【請求項３】
請求項１または２記載のパケット中継装置において、
前記振り分け処理部は、前記第２の出力ポートを選択する際、前記複数の出力ポートの内の、最も輻輳度合いが少ない出力ポートを選択することを特徴とするパケット中継装置。
【請求項４】
請求項１，２または３記載のパケット中継装置において、
前記振り分け処理部は、前記振り分け比率を算出する際、前記第１の出力ポートの輻輳度合いと、自装置からパケットを破棄したパケット中継装置までのホップ数とに基づいて振り分け比率を算出することを特徴とするパケット中継装置。
【請求項５】
請求項４記載のパケット中継装置において、
前記振り分け比率は、前記第１の出力ポートの輻輳度合いが大きいほど、前記第１の出力ポートへ振り分けられるパケット数を少なくし、自装置からパケットを破棄したパケット中継装置までのホップ数が小さいほど、前記第１の出力ポートへ振り分けられるパケット数を少なくするものであることを特徴とするパケット中継装置。
【請求項６】
請求項１乃至５の何れか１項に記載のパケット中継装置において、
前記パケット破棄検出部は、同一コネクションにおいて再送されたパケットを検出した場合は、前記再送されたパケットの宛先に対応する出力ポートから出力されたパケットが破棄されたと判定し、同一コネクションにおいて同一パケットに対するACK応答を複数検出した場合は、前記ACK応答の送信元に対応する出力ポートから出力されたパケットが破棄されたと判定することを特徴とするパケット中継装置。
【請求項７】
パケットを入力する複数の入力ポートと、パケットを出力する複数の出力ポートと、パケット転送部と、パケット破棄検出部と、振り分け処理部とを備えたコンピュータが実行するパケット中継方法であって、
前記パケット破棄検出部が、前記出力ポート毎に、その出力ポートから出力されたパケットの破棄を検出し、
前記振り分け処理部が、前記パケット破棄検出部の検出結果に基づいて前記出力ポート毎の輻輳度合いを算出し、該算出した輻輳度合いが閾値を超える第１の出力ポートについては、パケットの振り分け先にする第２の出力ポートを前記複数の出力ポートの中から選択すると共に、前記第１の出力ポートの輻輳度合いに基づいて、宛先が前記第１の出力ポートに対応するパケットを前記第１の出力ポートと前記第２の出力ポートとに振り分ける際の振り分け比率を算出し、
前記パケット転送部が、前記入力ポートから入力された宛先が前記第１の出力ポートに対応するパケットを、前記振り分け処理部で算出された振り分け比率に従って前記第１の出力ポートと前記第２の出力ポートとに振り分けることを特徴とするパケット中継方法。
【請求項８】
パケットを入力する複数の入力ポートと、パケットを出力する複数の出力ポートとを備えたコンピュータをパケット中継装置として機能させるためのプログラムであって、
前記コンピュータを、
該パケット破棄検出部の検出結果に基づいて前記出力ポート毎の輻輳度合いを算出し、該算出した輻輳度合いが閾値を超える第１の出力ポートについては、パケットの振り分け先にする第２の出力ポートを前記複数の出力ポートの中から選択すると共に、前記第１の出力ポートの輻輳度合いに基づいて、宛先が前記第１の出力ポートに対応するパケットを前記第１の出力ポートと前記第２の出力ポートとに振り分ける際の振り分け比率を算出する振り分け処理部、
前記入力ポートから入力された宛先が前記第１の出力ポートに対応するパケットを、前記振り分け処理部で算出された振り分け比率に従って前記第１の出力ポートと前記第２の出力ポートとに振り分けるパケット転送部として機能させるプログラム。
【請求項１】
パケットを入力する複数の入力ポートと、
パケットを出力する複数の出力ポートと、
前記出力ポート毎に、その出力ポートから出力されたパケットの破棄を検出するパケット破棄検出部と、
該パケット破棄検出部の検出結果に基づいて前記出力ポート毎の輻輳度合いを算出し、該算出した輻輳度合いが閾値を超える第１の出力ポートについては、パケットの振り分け先にする第２の出力ポートを前記複数の出力ポートの中から選択すると共に、前記第１の出力ポートの輻輳度合いに基づいて、宛先が前記第１の出力ポートに対応するパケットを前記第１の出力ポートと前記第２の出力ポートとに振り分ける際の振り分け比率を算出する振り分け処理部と、
前記入力ポートから入力された宛先が前記第１の出力ポートに対応するパケットを、前記振り分け処理部で算出された振り分け比率に従って前記第１の出力ポートと前記第２の出力ポートとに振り分けるパケット転送部とを備えたことを特徴とするパケット中継装置。
【請求項２】
請求項１記載のパケット中継装置において、
前記出力ポートの輻輳度合いは、一定時間の間に前記出力ポートから出力されたパケットの総数と、前記一定時間の間に前記出力ポートから出力されて破棄されたパケットの数との比率を示すパケット破棄検出率であることを特徴とするパケット中継装置。
【請求項３】
請求項１または２記載のパケット中継装置において、
前記振り分け処理部は、前記第２の出力ポートを選択する際、前記複数の出力ポートの内の、最も輻輳度合いが少ない出力ポートを選択することを特徴とするパケット中継装置。
【請求項４】
請求項１，２または３記載のパケット中継装置において、
前記振り分け処理部は、前記振り分け比率を算出する際、前記第１の出力ポートの輻輳度合いと、自装置からパケットを破棄したパケット中継装置までのホップ数とに基づいて振り分け比率を算出することを特徴とするパケット中継装置。
【請求項５】
請求項４記載のパケット中継装置において、
前記振り分け比率は、前記第１の出力ポートの輻輳度合いが大きいほど、前記第１の出力ポートへ振り分けられるパケット数を少なくし、自装置からパケットを破棄したパケット中継装置までのホップ数が小さいほど、前記第１の出力ポートへ振り分けられるパケット数を少なくするものであることを特徴とするパケット中継装置。
【請求項６】
請求項１乃至５の何れか１項に記載のパケット中継装置において、
前記パケット破棄検出部は、同一コネクションにおいて再送されたパケットを検出した場合は、前記再送されたパケットの宛先に対応する出力ポートから出力されたパケットが破棄されたと判定し、同一コネクションにおいて同一パケットに対するACK応答を複数検出した場合は、前記ACK応答の送信元に対応する出力ポートから出力されたパケットが破棄されたと判定することを特徴とするパケット中継装置。
【請求項７】
パケットを入力する複数の入力ポートと、パケットを出力する複数の出力ポートと、パケット転送部と、パケット破棄検出部と、振り分け処理部とを備えたコンピュータが実行するパケット中継方法であって、
前記パケット破棄検出部が、前記出力ポート毎に、その出力ポートから出力されたパケットの破棄を検出し、
前記振り分け処理部が、前記パケット破棄検出部の検出結果に基づいて前記出力ポート毎の輻輳度合いを算出し、該算出した輻輳度合いが閾値を超える第１の出力ポートについては、パケットの振り分け先にする第２の出力ポートを前記複数の出力ポートの中から選択すると共に、前記第１の出力ポートの輻輳度合いに基づいて、宛先が前記第１の出力ポートに対応するパケットを前記第１の出力ポートと前記第２の出力ポートとに振り分ける際の振り分け比率を算出し、
前記パケット転送部が、前記入力ポートから入力された宛先が前記第１の出力ポートに対応するパケットを、前記振り分け処理部で算出された振り分け比率に従って前記第１の出力ポートと前記第２の出力ポートとに振り分けることを特徴とするパケット中継方法。
【請求項８】
パケットを入力する複数の入力ポートと、パケットを出力する複数の出力ポートとを備えたコンピュータをパケット中継装置として機能させるためのプログラムであって、
前記コンピュータを、
該パケット破棄検出部の検出結果に基づいて前記出力ポート毎の輻輳度合いを算出し、該算出した輻輳度合いが閾値を超える第１の出力ポートについては、パケットの振り分け先にする第２の出力ポートを前記複数の出力ポートの中から選択すると共に、前記第１の出力ポートの輻輳度合いに基づいて、宛先が前記第１の出力ポートに対応するパケットを前記第１の出力ポートと前記第２の出力ポートとに振り分ける際の振り分け比率を算出する振り分け処理部、
前記入力ポートから入力された宛先が前記第１の出力ポートに対応するパケットを、前記振り分け処理部で算出された振り分け比率に従って前記第１の出力ポートと前記第２の出力ポートとに振り分けるパケット転送部として機能させるプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【公開番号】特開２０１２−１３４５８２（Ｐ２０１２−１３４５８２Ａ）
【公開日】平成２４年７月１２日（２０１２．７．１２）
【国際特許分類】
【出願番号】特願２０１０−２８２５２７（Ｐ２０１０−２８２５２７）
【出願日】平成２２年１２月２０日（２０１０．１２．２０）
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【Ｆターム（参考）】
【公開日】平成２４年７月１２日（２０１２．７．１２）
【国際特許分類】
【出願日】平成２２年１２月２０日（２０１０．１２．２０）
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【Ｆターム（参考）】
[ Back to top ]