(57)【特許請求の範囲】
【請求項１】
パケットの交換装置であって、
他の交換装置と経路情報を交換して経路テーブルを作成する手段と、
新たなフローが発生した際、経路テーブルに基づき、該フローに属するパケットの送信に使用するインタフェースを決定する手段と、
を備えており、
前記経路テーブルを作成する手段は、宛先ネットワークに至る経路から、
あらかじめ決められた経路選択基準での第１の最適経路を求め、
さらに、前記経路テーブルを作成する手段は、前記第１の最適経路以外の経路に対応するインタフェースと接続している交換装置から、前記宛先ネットワークへの最適経路を前記経路選択基準で求め、該最適経路で自装置が含まれていない第２の最適経路を求め、
前記第１および第２の最適経路に対応するインタフェースを、前記宛先ネットワークに対するパケットを送信可能なインタフェースとした経路テーブルを作成する、
交換装置。
【請求項２】
各インタフェースに送信しているトラフィック量を計測する手段と、
計測したトラフィック量と閾値に基づき、各インタフェースが輻輳状態であるか否かを判定する手段とを、さらに、備えており、
前記インタフェースを決定する手段は、輻輳状態ではないインタフェースから、新たなフローに属するパケットの送信に使用するインタフェースを決定する、
請求項１に記載の交換装置。
【請求項３】
前記インタフェースを決定する手段は、インタフェースが輻輳状態になったとしても、それ以前に該インタフェースを使用すると決定したフローに属するパケットについては、該インタフェースへの送信を継続する、
請求項１または２に記載の交換装置。
【請求項４】
請求項１から３のいずれか１項に記載の交換装置として、コンピュータを機能させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パケットネットワークにおけるパケットの経路の制御技術に関する。
【背景技術】
【０００２】
ルータやスイッチと呼ばれるパケットの交換装置で構成されるパケットネットワークにおいては、通常、交換装置同士が経路情報を交換して経路テーブルを作成し、これにより、受信したパケットを送出すべきインタフェースの判定を行っている（例えば、非特許文献１及び２、参照。）。
【０００３】
また、ネットワークのトラフィック状況に応じ、より細かく経路制御を行うため、パケットの宛先アドレスのみで送出すべきインタフェースの判定を行うのではなく、フロー単位、つまり、例えば、パケットの宛先アドレス、宛先ポート番号、送信元アドレス及び送信元ポート番号の組合せで、送出すべきインタフェースの判定を行うフロー・ルーティングが提案されている（例えば、非特許文献３、参照。）。
【０００４】
【非特許文献１】Ｊ．Ｍｏｙ、“ＯＳＰＦ  Ｖｅｒｓｉｏｎ  ２”、ＲＦＣ２３２８、１９９８年４月
【非特許文献２】Ｒ．Ｃａｌｌｏｎ、“Ｕｓｅ  ｏｆ  ＯＳＩ  ＩＳ−ＩＳ  ｆｏｒ  Ｒｏｕｔｉｎｇ  ｉｎ  ＴＣＰ／ＩＰ  ａｎｄ  Ｄｕａｌ  Ｅｎｖｉｒｏｍｅｎｔｓ”、ＲＦＣ１１９５、１９９０年１２月
【非特許文献３】Ｄｒ．Ｌａｗｒｅｎｃｅ  Ｇ．Ｒｏｂｅｒｔｓ、“Ｔｈｅ  Ｎｅｘｔ  Ｇｅｎｅｒａｔｉｏｎ  ｏｆ  ＩＰ−Ｆｌｏｗ  Ｒｏｕｔｉｎｇ”、［ｏｎｌｉｎｅ］、２００３年７月２９日付、Ｃａｓｐｉａｎ  Ｎｅｔｗｏｒｋｓ、［平成２０年５月１３日検索］、インターネット＜ＵＲＬ：ｈｔｔｐ：／／ｗｗｗ．ｐａｃｋｅｔ．ｃｃ／ｆｉｌｅｓ／ＦｌｏｗＰａｐｅｒ／ＮｅｘｔＧｅｎｅｒａｔｉｏｎｏｆＩＰ-ＦｌｏｗＲｏｕｔｉｎｇ．ｈｔｍ＞
【発明の開示】
【発明が解決しようとする課題】
【０００５】
例えば、図１に示す構成において、交換装置１から見て、ネットワーク６への合計コストは、リンク１２を通る経路に対しては１０であり、リンク１３を通る経路に対しては４０であるため、交換装置１は、ネットワーク６宛てのパケットをリンク１２に、つまり、インタフェース（ＩＦ）ｂに送出する。
【０００６】
ここで、交換装置１が受信するネットワーク６宛てのパケットが、リンク１２の帯域以上となった場合、通常、交換装置１は、リンク１２の帯域を超える部分のパケットを廃棄する。パケットの廃棄を極力回避するため、他の経路の使用を考えることができるが、コストが最低ではない経路にパケットを送信した場合、ループ・パケットの発生、つまり、ある２つ以上の交換装置を順に回るようにパケットが転送されてしまう状態になる可能性がある。ループ・パケットは、その最大転送ホップ数を超えることで廃棄されるが、この場合、無駄にネットワークの帯域を消費するのみで、従来通り、直ちに交換装置において廃棄しておいた方が有利である。しかしながら、ループ・パケットが発生しない経路も存在し、ループ・パケットが発生しない経路であれば、交換装置において廃棄するのではなく、この経路にパケットを送信することでパケットの廃棄を抑えることが可能になる。
【０００７】
したがって、本発明は、従来技術より廃棄されるパケット数を低減し、かつ、ループ・パケットの発生を抑えるパケットの交換装置と、この交換装置としてコンピュータを機能させるプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明におけるパケットの交換装置によれば、
他の交換装置と経路情報を交換して経路テーブルを作成する手段と、新たなフローが発生した際、経路テーブルに基づき、該フローに属するパケットの送信に使用するインタフェースを決定する手段とを備えており、前記経路テーブルを作成する手段は、宛先ネットワークに至る経路から、あらかじめ決められた経路選択基準での最適経路と、前記最適経路以外の経路のうち、該経路において隣に位置する他の交換装置から前記宛先ネットワークに至る前記経路選択基準での最適経路に自装置が含まれていない経路とを求め、求めた経路に対応するインタフェースを、前記宛先ネットワークに対するパケットを送信可能なインタフェースとした経路テーブルを作成することを特徴とする。
【０００９】
本発明の交換装置における他の実施形態によれば、
各インタフェースに送信しているトラフィック量を計測する手段と、計測したトラフィック量と閾値に基づき、各インタフェースが輻輳状態であるか否かを判定する手段とを、さらに、備えており、前記インタフェースを決定する手段は、輻輳状態ではないインタフェースから、新たなフローに属するパケットの送信に使用するインタフェースを決定することも好ましい。
【００１０】
また、本発明の交換装置における他の実施形態によれば、
パケットの交換装置であって、他の交換装置と経路情報を交換して経路テーブルを作成する手段と、新たなフローが発生した際、経路テーブルに基づき、該フローに属するパケットの送信に使用するインタフェースを決定する手段と、各インタフェースに送信しているトラフィック量を計測する手段と、計測したトラフィック量と閾値に基づき、各インタフェースが輻輳状態であるか否かを判定する手段とを備えており前記経路テーブルを作成する手段は、インタフェースが輻輳状態となったとき、各交換装置から見た各宛先ネットワークへの、あらかじめ決められた経路選択基準での最適経路に、該インタフェースに対応するリンクを含ませないようにするため、該インタフェースに対応するリンクのコスト値を変更して変更後のコスト値を、又は、該インタフェースに対応するリンクの削除を他の交換装置に通知し、変更後のコスト値により、又は、該リンクが削除されたものとして経路テーブルを更新することを特徴とする。
【００１１】
さらに、本発明の交換装置における他の実施形態によれば、
前記インタフェースを決定する手段は、インタフェースが輻輳状態になったとしても、それ以前に該インタフェースを使用すると決定したフローに属するパケットについては、該インタフェースへの送信を継続することも好ましい。
【００１２】
また、コンピュータを上記交換装置として機能させるプログラムが提供される。
【発明の効果】
【００１３】
ある宛先ネットワークに至る最適経路以外の経路は、ループ・パケット発生の可能性があるが、該経路で自装置に隣接する他の交換装置から、この宛先ネットワークに至る最適経路に自装置が含まれていない経路は、ループ・パケットが発生しない経路であるため、これら経路も含めた経路テーブルを作成する。これにより、あるインタフェースが輻輳状態となったとしても、経路テーブルが示すループ・パケットの発生しない他の経路を使用することができ、パケットの廃棄数を抑えることができる。また、送信インタフェースが輻輳状態となったときに、このインタフェースに対応するリンクが、実質的に削除されたものとして各交換装置で経路テーブルを更新する様に構成することで、新たなフローは、輻輳状態であるリンクを含まないその時点での最適経路、つまりループ・パケットの発生しない経路に流されることになり、これにより、パケット廃棄数を抑えることができる。
【発明を実施するための最良の形態】
【００１４】
本発明を実施するための最良の実施形態について、以下では図面を用いて詳細に説明する。図１は、本発明による経路制御を実行するネットワークの構成図である。図１によると、コスト１０のリンク１２は交換装置１と交換装置２を接続し、コスト１０のリンク１３は交換装置１と交換装置３を接続し、コスト１０のリンク３４は交換装置３と交換装置４を接続し、コスト２０のリンク２４は交換装置２と交換装置４を接続している。また、交換装置１はネットワーク５とコスト１０のリンクで接続し、交換装置２はネットワーク６と、交換装置３はネットワーク７と、交換装置４はネットワーク８と接続している。なお、交換装置１は、インタフェース（ＩＦ）ａでネットワーク５と接続し、ＩＦｂでリンク１２と接続し、ＩＦｃでリンク１３と接続している。
【００１５】
各交換装置は、非特許文献１や２に記載の、リンクステート型ルーティングプロトコルを用いて経路情報、具体的には、自装置に接続されているリンクと、そのリンクのコスト及び接続先である他の交換装置のインタフェースについての情報等を交換する。図２は、交換装置１が従来の交換装置である場合に、交換装置１が生成する経路テーブルである。図２に示す様に、従来の交換装置は、宛先ネットワークごとに、あらかじめ決められた経路選択基準での最適経路、本実施形態においては、各リンクのコストの合計値が最低となる経路を求め、その経路に対応するインタフェースを経路テーブルとして保存する。
【００１６】
図３は、本発明による交換装置１が生成する経路テーブルを示す図である。本発明による交換装置は、まず、従来と同じ方法で、宛先ネットワークまでの経路を求め、各経路に対応するインタフェースを求める。このうち、この宛先ネットワークに対する、あらかじめ決められた経路選択基準での最適経路に対応するインタフェースと、そのコストを、それぞれ、経路テーブルに設定する。なお、経路選択基準としては公知の種々の方法が適用可能である。
【００１７】
続いて、この宛先ネットワークへの最適経路以外の各経路について、交換装置は、ループ・パケット発生の有無を調べる。具体的には、最適経路以外の経路に対応するインタフェースと接続している交換装置から、この宛先ネットワークへの最適経路を求め、この最適経路に自装置が含まれている場合には、ループ・パケットが発生し、含まれていない場合にはループ・パケットが発生しないものと判定する。ループ・パケットが発生しない場合には、その経路に対応するインタフェースとコストを、それぞれ、経路テーブルに設定する。
【００１８】
例えば、図１の交換装置１において、ネットワーク６へは、ＩＦｂとｃを含む経路が可能であり、最適経路はＩＦｂであるため、ＩＦｂとそのコスト“１０”を、経路テーブルに設定する。続いて、最適経路ではないＩＦｃについて、ＩＦｃと接続している交換装置３からネットワーク６への最適経路を求める。この場合、最適経路は、リンク１３とリンク１２を通る経路であり交換装置１が経路に含まれているため、ループ・パケットが発生すると判断できる。よって、ＩＦｃに対応する経路は、経路テーブルには設定しない。
【００１９】
同様に、図１の交換装置１において、ネットワーク８へは、ＩＦｂとｃを含む経路が可能であり、最適経路はＩＦｃであるため、ＩＦｃと、そのコスト“２０”を、経路テーブルに設定する。続いて、最適経路ではないＩＦｂについて、ＩＦｂと接続している交換装置２からネットワーク８への最適経路を求める。この場合、最適経路は、リンク２４を通る経路であり交換装置１が経路に含まれていないため、ループ・パケットは発生しないと判断でき、よって、ＩＦｂとそのコスト“３０”を、経路テーブルに設定する。
【００２０】
また、本発明による交換装置は、各インタフェースに送信しているトラフィック量を監視する。各インタフェースには、例えば、その最大帯域のある割合として、閾値があらかじめ設定されており、交換装置は、あるインタフェースに送信しているトラフィック量が、このインタフェースに対する閾値を超えている場合、このインタフェースが輻輳状態であると、つまり、このインタフェースに対応するリンクが輻輳状態であると判定する。そして、新たなフローが発生した場合、経路テーブルにある、このフローの宛先ネットワークに対するインタフェースのうち、輻輳状態ではないインタフェースから、この新たに発生したフローに属するパケットの送信に使用するインタフェースを決定し、この新たなフローと決定したインタフェースの対応関係を転送テーブルに設定する。以後、交換装置は、この新たなフローに属するパケットを受信した場合、転送テーブルに従い送信を行う。つまり、フローに属するパケットの送信に使用すると決定したインタフェースは、その後のインタフェースの輻輳状態の変化により変更はしない。なお、この決定は、最適な経路の順番で、つまり、コストが低いものから順に行うことが好ましい。
【００２１】
例えば、図４に示す経路テーブルを有する状態において、ネットワークＡ宛の新たなフローが発生したとする。この新たなフローが発生した時点において、ＩＦａ１が輻輳状態になければ、交換装置はこの新たなフローに属するパケットに対してはＩＦａ１を使用すると決定し、この新たなフローとＩＦａ１の組を転送テーブルに設定する。以後、交換装置は、この新たなフローに属するパケットを受信した場合、たとえ受信した時点においてＩＦａ１が輻輳状態であったとしても、転送テーブルに従い、この受信したパケットをＩＦａ１に送信する。しかしながら、ＩＦａ１が輻輳状態であるときに、ネットワークＡ宛の他の新たなフローが発生した場合、交換装置は、次にコストが低いＩＦａ３が輻輳状態でなければ、この他の新たなフローに属するパケットに対してはＩＦａ３を使用すると決定し、この他の新たなフローとＩＦａ３の組を転送テーブルに設定する。以後、交換装置は、この他の新たなフローに属するパケットを受信した場合、たとえ受信した時点においてＩＦａ１が輻輳状態でなくなっていたとしも、転送テーブルに従い、この受信したパケットをＩＦａ３に送信する。なお、可能な経路が総て輻輳状態である場合に発生したフローのパケットについては廃棄する。
【００２２】
なお、フローとは、端末間の個々の通信を示す単位であり、例えば、宛先アドレスと送信元アドレスの組により、または、宛先アドレス、宛先ポート番号、送信元アドレス及び送信元ポート番号の組で特定されるものである。
【００２３】
以上、本発明においては、交換装置が、最適経路のみならず、ループ・パケットが発生しない代替経路をあらかじめ検索し、最適経路と代替経路の両方を示す経路テーブルを作成し、フローが発生して時点における各インタフェースの輻輳状態に基づき、このフローに使用する経路を決定する。これにより、ループ・パケットの発生を防ぎつつ、廃棄されるパケット数を抑えることが可能になる。
【００２４】
続いて、本発明の他の実施形態について説明する。本実施形態において、交換装置は、図２に示す、従来と同じ経路テーブルを作成して保存し、新たなフローが発生した場合、経路テーブルに基づき、この新たに発生したフローに属するパケットの送信に使用するインタフェースを決定し、この新たなフローと決定したインタフェースの対応関係を転送テーブルに設定する。以後、交換装置は、この新たなフローに属するパケットを受信した場合、転送テーブルに従い送信を行う。また、本実施形態における交換装置は、インタフェースが輻輳状態となった場合、転送テーブルに基づき、当該インタフェースに送信しているフローについては、当該インタフェースへの送信を維持しつつ、当該インタフェースに対応するリンクが削除されたことを、他の交換装置に通知して他の交換装置に経路テーブルを更新させ、自装置においても輻輳状態にあるインタフェースが削除されたものとして経路テーブルを更新する。これにより、輻輳状態となったインタフェースに対応するリンクを含む経路は、各交換装置から見た、各宛先ネットワークへの最適経路には含まれなくなり、よって、輻輳状態となった後に生じた新たなフローは、この輻輳状態であるリンクを含まない他の経路を使用して転送することになり、パケット廃棄を回避する。なお、輻輳状態となったインタフェースが削除されたものとして全交換装置は経路テーブルを更新しているため、更新後の経路テーブルによるパケットの転送において、ループ・パケットが発生することはない。
【００２５】
また、輻輳状態であったインタフェースが輻輳状態ではなくなった場合、交換装置は、このインタフェースを追加して経路テーブルを更新すると共に、このインタフェースの追加を他の交換装置に通知して、他の交換装置にも経路テーブルを更新させる。
【００２６】
なお、インタフェースが輻輳状態となったときに、このインタフェースが削除されたものとして扱い、輻輳状態であるインタフェースが輻輳状態ではなくなったときに、このインタフェースが追加されたものとして扱うのではなく、コストを変更して実質的に削除された様に扱う形態であっても良い。つまり、インタフェースが輻輳状態となったときに、このインタフェースのコストを非常に大きな値に変更し、変更後の値を他の交換装置に通知することで、各交換装置から見た、各宛先ネットワークへの最適経路に、このインタフェースに対応するリンクが含まれない様にする形態であっても良い。この場合、輻輳状態であったインタフェースが輻輳状態ではなくなった場合、このインタフェースに対応するリンクのコストを元の値に戻し、この元の値を他の交換装置に通知することになる。
【００２７】
なお、上記、非常に大きな値には、例えば、ネットワーク内のリンクに付与されているコストの最大値に、ネットワーク内にあるリンク数を乗じた値以上の値や、ネットワーク内にある全リンクのコストの合計値以上の値等を使用することができる。
【００２８】
以上、本実施形態においては、輻輳状態となった時点において、輻輳状態となったリンクに存在するフローについては、転送テーブルにより、このリンクでの送信を維持する一方、このリンクを含む経路に新たなフローが流れないように、このリンクが削除されたものとして、あるいは、このリンクのコストを非常に大きな値に変更して、経路テーブルを更新し、同時に、このリンクの削除又は変更後のコスト値を他の交換装置に通知して、他の交換装置においても経路テーブルを更新させる。これにより、新たなフローを、ループ・パケットが発生せず、かつ、輻輳状態のリンクを含まない他の経路に流すことができ、よってパケット廃棄を抑えることができる。
【００２９】
図５は、本発明による交換装置のブロック図である。図５において、インタフェース４１は、パケットの送受信を行い、交換処理部４２は、新たなフローに属するパケットをはじめて受信した場合、経路テーブル４３を参照して、この新たなフローに属するパケットを送信するインタフェース４１の決定を行い、この新たなフローと決定したインタフェース４１の対応関係を転送テーブル４６に設定する。以後、交換処理部４２は、このフローに属するパケットを受信した場合、転送テーブル４６が示すインタフェース４１から送信を行う。トラフィック監視部４４は、インタフェース４１が送信するパケットのトラフィック量を監視してルーティング制御部４５に通知し、ルーティング制御部４５は、交換処理部４２及びインタフェース４１経由で、他の交換装置と経路情報を交換して経路テーブル４３を作成する。
【００３０】
最初の実施形態において、ルーティング制御部４５は、図３及び４に示す経路テーブル４３を作成し、トラフィック監視部４４からの通知に基づき、輻輳の発生を判定し、輻輳状態であるインタフェースを交換処理部４２に通知する。交換処理部４２は、新たなフローが発生した場合、経路テーブル４３と、インタフェースの輻輳状態に基づき、この新たなフローに属するパケットを送信する経路、つまり、インタフェースを決定する。
【００３１】
また、後の実施形態において、ルーティング制御部４５は、輻輳状態のインタフェースが発生した場合、上述した様に、このインタフェースに対応するリンクが削除されたものとし、あるいは、このリンクのコストを非常に大きな値に変更し、削除又は変更後のコストを他の交換装置に通知すると共に、経路テーブル４３を更新する。また、輻輳状態のインタフェースが輻輳状態ではなくなった場合、ルーティング制御部４５は、このインタフェースを追加し、あるいは、このインタフェースのコストを元の値に戻して経路テーブルを更新すると共に、このインタフェースに対応するリンクの追加、あるいは、このリンクの元のコスト値を他の交換装置に通知する。
【００３２】
なお、本発明による交換装置は、コンピュータを図５の各部として機能させるプログラムにより実現することができる。これらコンピュータプログラムは、コンピュータが読み取り可能な記憶媒体に記憶されて、又は、ネットワーク経由で配布が可能なものである。
【図面の簡単な説明】
【００３３】
【図１】本発明による経路制御方法を実行するネットワークの構成図である。
【図２】従来の交換装置による経路テーブルである。
【図３】本発明による交換装置が生成する経路テーブルを示す図である。
【図４】本発明の経路制御方法を説明する図である。
【図５】本発明による交換装置のブロック図である。
【符号の説明】
【００３４】
１、２、３、４、５１  交換装置
５、６、７、８  ネットワーク
１２、１３、２４、３４  リンク
４１  インタフェース
４２  交換処理部
４３  経路テーブル
４４  トラフィック監視部
４５  ルーティング制御部
４６  転送テーブル
【図１】
0005071245.tif 000002
【図２】
0005071245.tif 000003
【図３】
0005071245.tif 000004
【図４】
0005071245.tif 000005
【図５】
0005071245.tif 000006