(57)【要約】課題  ユニキャストの場合に、受信したパケットに余計な情報を付与することがなく、また、マルチキャストの場合に、複数の上流ノードから同一のマルチキャストパケットを送信されるような場合でも、ループを検出してネットワークがループによって輻輳状態になることを防ぐ。解決手段  受信したパケットがノード自身が一度送信したパケットかどうかを判定し、送信済みであれば廃棄を行う。送信済みでなければ次受信時における送信済み判定のために、パケットを一意に識別するための情報を記録した上で、パケットの送信を行う。このことにより、ループ発生時のパケットの無限コピーを防ぐ。
2008146730.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークと接続するネットワークインターフェイスと、
ネットワークからパケットを受信するパケット受信部と、
ネットワークに対してパケットを送信するパケット送信部とを持つノード装置であって、
送信済みのパケットに関するパケットを識別するための識別情報を記録するための通過パケット記録データベースと、
通過パケット記録データベースを参照し、未送信の前記受信パケットをパケット送信部へと送るパケット重複判定部を有することを特徴とするノード装置。
【請求項２】
前記パケット重複判定部は、
前記通過パケット記録データベースを参照し、受信したパケットが送信済みかどうかを判定し、送信済みでない場合、受信パケットをパケット送信部へと送ることを特徴とする請求項１に記載のノード装置。
【請求項３】
前記パケット重複判定部は、
受信したパケットの受信時刻を、当該パケットの送信前又は送信後に記録することを特徴とする請求項１又は請求項２に記載のノード装置。
【請求項４】
前記パケット重複判定部は、
受信したパケットの送信時刻を、当該パケットの送信の際に記録することを特徴とする請求項１又は請求項２に記載のノード装置。
【請求項５】
前記通過パケット記録データベースにおいて、
送信済みパケットの識別情報をフロー毎に区別して記録を行い、
前記パケット重複判定部において、
受信したパケットがどのフローに属するかを識別し、前記通過パケット記録データベース中の同一のフローに属する識別情報に基づき当該受信したパケットが送信済みかの判定を行うことを特徴とする請求項１から請求項４のいずれか１項に記載のノード装置。
【請求項６】
前記パケットを識別するための識別情報として、パケットのペイロードを用いることを特徴とする請求項１から請求項５のいずれか１項に記載のノード装置。
【請求項７】
前記パケットを識別するための識別情報として、パケットのペイロードのハッシュ値を用いることを特徴とする請求項１から請求項５のいずれか１項に記載のノード装置。
【請求項８】
前記パケットを識別するための識別情報として、ＲＴＰヘッダ中のシーケンス番号を用いることを特徴とする請求項１から請求項５のいずれか１項に記載のノード装置。
【請求項９】
前記パケットを識別するための識別情報として、ＩＰヘッダ中の識別子およびフラグメントオフセットの組を用いることを特徴とする請求項１から請求項５のいずれか１項に記載のノード装置。
【請求項１０】
前記通過パケット記録データベースは、
送信済みのパケットに関するパケットを識別するための識別情報として、当該パケットのペイロードのハッシュ値やペイロードの一部分を記録し、
前記パケット重複判定部は、
前記識別情報として受信したパケットのペイロードのハッシュ値やペイロードの一部分を用い、前記通過パケット記録データベースを参照し、受信したパケットが送信済みかどうかを判定し、送信済みの場合に、前記識別情報として前記受信したパケットのペイロード全体を用い、受信したパケットが送信済みかどうかを判定することを特徴とする請求項１から請求項５のいずれか１項に記載のノード装置。
【請求項１１】
前記通過パケット記録データベース上に記録されている送信済みのパケットに関するパケットを識別するための識別情報を、そのパケットの受信時刻又は送信時刻からあらかじめ定められたタイムアウト時間経過後に、削除するデータベースメンテナンス部を有することを特徴とする請求項１から請求項１０のいずれか１項に記載のノード装置。
【請求項１２】
前記パケット重複判定部において、受信したパケットがすでに送信済みであったと判断されたときに、受信パケットの受信時刻又は送信時刻と、通過パケット記録データベース中の該当するパケットの受信時刻又は送信時刻との時間差を用いて前記タイムアウト時間を決めるタイムアウト値決定部を有することを特徴とする請求項１１に記載のノード装置。
【請求項１３】
前記タイムアウト値決定部において、前記時間差の統計情報を用いてタイムアウト時間を決めることを特徴とする請求項１２に記載のノード装置。
【請求項１４】
前記タイムアウト値決定部は、
タイムアウト時間に上限値を設け、現在のタイムアウト時間と前記時間差の比較を行い、前記時間差の方が小さい場合に前記時間差を用いて新たなタイムアウト時間を決定することを特徴とする請求項１１から請求項１３のいずれか１項に記載のノード装置。
【請求項１５】
前記タイムアウト値決定部は、
タイムアウト時間に下限値を設け、現在のタイムアウト時間と前記時間差の比較を行い、前記時間差の方が大きい場合に前記時間差を用いて新たなタイムアウト時間を決定することを特徴とする請求項１１から請求項１３のいずれか１項に記載のノード装置。
【請求項１６】
前記通過パケット記録データベース上に記録されている送信済みのパケットに関する識別情報の数が予め定められている最大値を超えたときに、通過パケット記録データベース上から、最大数を超過した数の識別情報を受信時刻又は送信時刻が古い順に削除するデータベースメンテナンス部を有することを特徴とする請求項１１に記載のノード装置。
【請求項１７】
前記通過パケット記録データベースにおいて、パケットの送信回数をパケットを識別するための識別情報との組で記録し、前記パケット重複判定部において、受信パケットが送信済みであると判定されたときに、前記通過パケット記録データベース中の送信回数を参照し、送信回数が予め定められた最大送信回数超えていないとき、前記通過パケット記録データベース中の送信回数の値を一つ増加させ、パケット送信部へと送ることを特徴とする請求項１から請求項１６のいずれか１項に記載のノード装置。
【請求項１８】
あらかじめ定められたパケットを識別する識別情報に基づき、受信したパケットの識別情報が前記識別情報に一致するときに、サンプリングパケット記録データベースを参照し、受信したパケットが送信済みかどうかを判定するサンプリングパケット重複判定部と、
前記サンプリングパケット重複判定部により送信済みかどうかの判定が行われ、送信済みではないと判定された受信パケットを記録するサンプリングパケット記録データベースと、
パケット受信部から送られてきたパケットを前記サンプリングパケット重複判定部に送り、前記サンプリングパケット重複判定部において、受信したパケットが送信済みであると判定されたとき、以降受信パケットをパケット重複判定部へと送るセレクタとを有することを特徴とする請求項１から請求項１７のいずれか１項に記載のノード装置。
【請求項１９】
前記パケット重複判定部は、
所定の時間、受信したパケットが未送信であると判定した場合、又は、判定したパケット数が所定の回数に達した場合、前記セレクタに対し、前記セレクタが以降受信したパケットをサンプリングパケット重複判定部へと送るよう指示を出すことを特徴とする請求項１８に記載のノード装置。
【請求項２０】
前記通過パケット記録データベースは、
送信済みのパケットに関するパケットを識別するための識別情報として、当該パケットの一部又は全部のハッシュ値を記録し、
前記パケット重複判定部は、
前記識別情報として受信したパケットの一部又は全部のハッシュ値を用い、前記通過パケット記録データベースを参照し、受信したパケットが送信済みかどうかを判定し、
送信済みの場合に、以降受信パケットをサンプリングパケット重複判定部へと送るセレクタと、
あらかじめ定められたパケットを識別する識別情報に基づき、受信したパケットの識別情報が前記識別情報に一致するときに、サンプリングパケット記録データベースを参照し、受信したパケットが送信済みかどうかを判定するサンプリングパケット重複判定部と、
前記サンプリングパケット重複判定部により送信済みかどうかの判定が行われ、送信済みではないと判定された受信パケットの一部又は全部のハッシュ値を記録するサンプリングパケット記録データベースとを有することを特徴とする請求項１から請求項１８のいずれか１項に記載のノード装置。
【請求項２１】
前記サンプリングパケット重複判定部は、
所定の時間、受信したパケットが未送信あると判定した場合、又は、判定したパケット数が所定の回数に達した場合、前記セレクタに対し、前記セレクタが以降受信したパケットを前記パケット重複判定部へと送るよう指示を出すことを特徴とする請求項２０に記載のノード装置。
【請求項２２】
受信したパケットのパケットサイズを測定することにより、単位時間当たりのトラフィック量を測定する流量測定部と、
前記流量測定部により測定された単位時間当たりのトラフィック量を用いてループ発生の判定を行う流量判定部と、
パケット受信部から送られてきたパケットを前記流量測定部に送り、前記流量判定部において、ループが発生していると判定されたとき、以降受信パケットをパケット重複判定部へと送るセレクタとを有することを特徴とする請求項１から請求項１８のいずれか１項に記載のノード装置。
【請求項２３】
前記流量判定部において、単位時間当たりのトラフィック量が予め定められた閾値を超えている場合にループが発生していると判定することを特徴とする請求項２２に記載のノード装置。
【請求項２４】
前記ノード装置において、
過去のトラフィック量の記録を行う流量記録部を有し、
前記流量判定部において、
流量記録部を参照しトラフィック量の増加が閾値を超えているかの判定を行い、
前記セレクタにおいて、
前記トラフィック量の増加が閾値を超えたと判定されたとき、以降受信パケットをパケット重複判定部へと送ることを特徴とする請求項２２又は請求項２３に記載のノード装置。
【請求項２５】
前記流量判定部において、前記流量記録部中に記録されている過去のトラフィック量の統計処理を行い、求められた統計値を用いてループ発生の判定を行うことを特徴とする請求項２４に記載のノード装置。
【請求項２６】
パケットの受信を行い、パケットのヘッダ情報に基づき、パケットの転送を行うパケット転送方法であって、
送信済みのパケットに関するパケットを識別するための識別情報を記録するステップと、
前記記録済みの識別情報を参照し、未送信の前記受信パケットを送信対象とするステップを持つことを特徴とするパケット転送方法。
【請求項２７】
未送信の前記受信パケットを送信対象とする前記ステップにおいて、
前記通過パケット記録データベースを参照し、受信したパケットが送信済みかどうかを判定し、送信済みでない場合、受信パケットを送信対象とすることを特徴とする請求項２６に記載のパケット転送方法。
【請求項２８】
未送信の前記受信パケットを送信対象とする前記ステップにおいて、
受信したパケットの受信時刻を、当該パケットの送信前又は送信後に記録することを特徴とする請求項２６又は請求項２７に記載のパケット転送方法。
【請求項２９】
未送信の前記受信パケットを送信対象とする前記ステップにおいて、
受信したパケットの送信時刻を、当該パケットの送信の際に記録することを特徴とする請求項２６又は請求項２７に記載のパケット転送方法。
【請求項３０】
前記送信済みパケットの識別情報を記録するステップにおいて、
送信済みパケットの識別情報をフロー毎に区別して記録を行い、
前記受信パケットが送信済みであるかを判定するステップにおいて、
受信したパケットがどのフローに属するかを識別し、同一のフローに属する識別情報に基づき当該受信したパケットが送信済みかの判定を行うことを特徴とする請求項２６から請求項２９のいずれか１項に記載のパケット転送方法。
【請求項３１】
前記パケットを識別するための識別情報として、パケットのペイロードを用いることを特徴とする請求項２６から請求項３０のいずれか１項に記載のパケット転送方法。
【請求項３２】
前記パケットを識別するための識別情報として、パケットのペイロードのハッシュ値を用いることを特徴とする請求項２６から請求項３０のいずれか１項に記載のパケット転送方法。
【請求項３３】
前記パケットを識別するための識別情報として、ＲＴＰヘッダ中のシーケンス番号を用いることを特徴とする請求項２６から請求項３０のいずれか１項に記載のパケット転送方法。
【請求項３４】
前記パケットを識別するための識別情報として、ＩＰヘッダ中の識別子およびフラグメントオフセットの組を用いることを請求項２６から請求項３０のいずれか１項に記載のパケット転送方法。
【請求項３５】
送信済みのパケットに関するパケットを識別するための識別情報として、当該パケットのペイロードのハッシュ値やペイロードの一部分を記録するステップを有し、
送信済みでない場合に受信パケットを送信対象とする前記ステップにおいて、
前記識別情報として受信したパケットのペイロードのハッシュ値やペイロードの一部分を用い、前記記録済みの識別情報を参照し、受信したパケットが送信済みかどうかを判定し、送信済みの場合に、前記識別情報として前記受信したパケットのペイロード全体を用い、受信したパケットが送信済みかどうかを判定することを特徴とする請求項２６から請求項３４のいずれか１項に記載のパケット転送方法。
【請求項３６】
前記記録されている送信済みのパケットに関するパケットを識別するための識別情報を、そのパケットの受信時刻又は送信時刻からあらかじめ定められたタイムアウト時間経過後に、削除するステップを有することを特徴とする請求項２６から請求項３０のいずれか１項に記載のパケット転送方法。
【請求項３７】
前記受信パケットが送信済みであるかを判定するステップにおいて、
受信したパケットがすでに送信済みであったと判断されたときに、受信パケットの受信時刻又は送信時刻と、該当するパケットの受信時刻又は送信時刻との時間差を用いて前記タイムアウト時間を決めるステップを有することを特徴とする請求項３６に記載のパケット転送方法。
【請求項３８】
前記タイムアウト時間を決定するステップにおいて、
前記時間差の統計情報を用いてタイムアウト時間を決めることを特徴とする請求項３７に記載のパケット転送方法。
【請求項３９】
タイムアウト時間に上限値を設け、現在のタイムアウト時間と前記時間差の比較を行い、前記時間差の方が小さい場合に前記時間差を用いて新たなタイムアウト時間を決定することを特徴とする請求項３６から請求項３８のいずれか１項に記載のパケット転送方法。
【請求項４０】
タイムアウト時間に下限値を設け、現在のタイムアウト時間と前記時間差の比較を行い、前記時間差の方が大きい場合に前記時間差を用いて新たなタイムアウト時間を決定することを特徴とする請求項３６から請求項３８のいずれか１項に記載のパケット転送方法。
【請求項４１】
前記記録されている送信済みのパケットに関する識別情報の数が予め定められている最大値を超えたときに、最大数を超過した数の識別情報を受信時刻又は送信時刻が古い順に削除するステップを有することを特徴とする請求項３８に記載のパケット転送方法。
【請求項４２】
前記送信済みパケットの識別情報を記録するステップにおいて、
パケットの送信回数をパケットを識別するための識別情報との組で記録し、
前記受信パケットが送信済みであるかを判定するステップにおいて、
受信パケットが送信済みであると判定されたときに、前記記録済みの識別情報との組で記録されている送信回数を参照し、送信回数が予め定められた最大送信回数超えていないとき、前記送信回数の値を一つ増加させ、パケットを送信対象とすることを特徴とする請求項２６から請求項４１のいずれか１項に記載のパケット転送方法。
【請求項４３】
あらかじめ定められたパケットを識別する識別情報に基づき、受信したパケットの識別情報が前記識別情報に一致するときに、サンプリングパケット記録データベースを参照し、受信したパケットが送信済みかどうかを調べることによりループ発生の検出を行うステップと、
前記ステップにより送信済みかどうかの判定が行われ、送信済みではないと判定された受信パケットをサンプリングパケット記録データベースに記録するステップと、
パケットの受信時に、前記ステップでループ発生の検出がなされていないときには前記サンプリングパケット記録データベースを用いたループ判定を行い、また、前記ステップでループ発生が検出されているときには、前記全受信パケットが送信済みであるかの判定を行うステップを有することを特徴とする請求項２６から請求項４２のいずれか１項に記載のパケット転送方法。
【請求項４４】
前記全受信パケットが送信済みであるかの判定を行うステップにおいて、
所定の時間、受信したパケットが未送信であると判定した場合、又は、判定したパケット数が所定の回数に達した場合、サンプリングパケット記録データベースを参照し、受信したパケットが送信済みかどうかを調べることによりループ発生の検出を行うステップに戻ることを特徴とする請求項４３に記載のパケット転送方法。
【請求項４５】
送信済みのパケットに関するパケットを識別するための識別情報として、当該パケットの一部又は全部のハッシュ値を記録するステップを有し、
送信済みでない場合に受信パケットを送信対象とする前記ステップにおいて、
前記識別情報として受信したパケットの一部又は全部のハッシュ値を用い、前記記録済みの識別情報を参照し、受信したパケットが送信済みかどうかを判定し、
送信済みの場合に、あらかじめ定められたパケットを識別する識別情報に基づき、受信したパケットの識別情報が前記識別情報に一致するときに、前記サンプリングパケット記録データベースを参照し、受信したパケットが送信済みかどうかを判定するステップと、
前記サンプリングパケット記録データベースを参照し、受信したパケットが送信済みかどうかを判定する前記ステップにより送信済みかどうかの判定が行われ、送信済みではないと判定された受信パケットの一部又は全部のハッシュ値をサンプリングパケット記録データベース記録するステップとを有することを特徴とする請求項２６から請求項４２のいずれか１項に記載のパケット転送方法。
【請求項４６】
前記サンプリングパケット記録データベースを参照し、受信したパケットが送信済みかどうかを判定する前記ステップにおいて、
所定の時間、受信したパケットが未送信あると判定した場合、又は、判定したパケット数が所定の回数に達した場合、送信済みでない場合に受信パケットを送信対象とする前記ステップに戻ることを特徴とする請求項４５に記載のパケット転送方法。
【請求項４７】
受信したパケットのパケットサイズを測定することにより、単位時間当たりのトラフィック量を測定するステップと、
前記ステップにより測定された単位時間当たりのトラフィック量を用いてループ発生の判定を行うステップと、
パケットの受信時に、前記ステップでループ発生の検出がなされていないときには前記トラフィック量を用いたループ判定を行い、また、前記ステップでループ発生が検出されているときには、前記全受信パケットが送信済みであるかの判定を行うステップを有することを特徴とする請求項２６から請求項４６のいずれか１項に記載のパケット転送方法。
【請求項４８】
前記トラフィック量を用いてループ判定を行うステップにおいて、
単位時間当たりのトラフィック量が予め定められた閾値を超えている場合にループが発生していると判定することを特徴とする請求項４７に記載のパケット転送方法。
【請求項４９】
前記パケット転送方式において、
過去のトラフィック量の記録を行うステップを有し、
前記トラフィック量を用いてループ判定を行うステップにおいて、
記録されている過去トラフィック量を参照しトラフィック量の増加が閾値を超えているかを調べることでループ発生の判定を行うことを特徴とする請求項４７又は請求項４８に記載のパケット転送方法。
【請求項５０】
前記トラフィック量を用いてループ判定を行うステップにおいて、
前記記録されている過去のトラフィック量の統計処理を行い、求められた統計値を用いてループ発生の判定を行うことを特徴とする請求項４９に記載のパケット転送方法。
【請求項５１】
ネットワークと接続するネットワークインターフェイスと、
ネットワークからパケットを受信するパケット受信部と、
ネットワークに対してパケットを送信するパケット送信部とを持つノード装置上で実行されるパケット転送プログラムであって、
前記ノード装置に、
送信済みのパケットに関するパケットを識別するための識別情報を記録するための通過パケット記録データベースを参照し、未送信の前記受信パケットをパケット送信部へと送るパケット重複判定処理を実行させることを特徴とするパケット転送プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワーク中に誤ってループ経路が発生した時に、受信したパケットがノード自身が一度送信したパケットかどうかを判別し、送信済みであれば廃棄を、そうでなければ送信を行うことにより、パケットの無限コピーを防ぐノード装置、パケット転送方法及びパケット転送プログラムに関する。
【背景技術】
【０００２】
ブロードバンドネットワークの普及に伴い、関連技術による狭帯域ネットワークでは困難であった高画質映像配信サービスの実現可能性が現実的となってきた。また映像パケットの配信にマルチキャスト技術を用いることで、サーバやネットワークの帯域を節約しつつ、多数のユーザへの配信が可能となっている。【０００３】
しかし、マルチキャストにはループ経路が発生したときにネットワーク全体に致命的影響を与えてしまうという課題がある。ループ経路は、ネットワーク管理者の設定ミスやネットワークトポロジー変化時の過渡的な状態で発生する可能性がある。図２８は、ノード１５、１７、１８の間でループ経路が生じている状態を示している。ノード１５が送信したパケットのうちノード１７に送信したパケットは、ノード１８を経由して、再度ノード１５に戻ってくるため、これらのノード間を生存時間が経過するまで回り続けることになる。しかも上流側であるノード１２側からノード１５に到着するパケットも次々とこのループ経路に向かって送信されることになる。このようにループ経路を構成するリンクの帯域が浪費されるばかりではなく、ノード１５は受信したパケットを下流であるノード１６へも送信するため、下流側であるノード１６，１９，２０へのリンクの帯域も浪費されるという問題がある。【０００４】
ループによる帯域の浪費を抑えるために、ＲＰＦ（Ｒｅｖｅｒｓｅ  Ｐａｔｈ  Ｆｏｒｗａｒｄｉｎｇ）チェック（非特許文献１）という手法が用いられている。これは、パケットの送信元アドレスを参照し、送信元アドレスがどの方向から来るのが正しいのかを自身の経路表を用いて調べ、正しい方向から来たパケットを転送するという手法である。【０００５】
すなわち、ユニキャストテーブルは宛先ノードアドレス及びネクストホップのアドレスを有し、マルチキャストテーブルは宛先ノードアドレス、次転送先ノードアドレス、送信元ノードアドレス及び上流ノードアドレスを有する。当該ユニキャストテーブルを持つノードは、マルチキャストテーブルを最初に生成する際に、送信元ノードアドレスを当該ユニキャストテーブルを参照して宛先ノードアドレスとして検出し、ネクストホップのアドレスを取得し、上流アドレスとして設定する。【０００６】
図２８を用いて説明すると、ここでノード１１から送信されるマルチキャストパケットは、ノード１５にとってノード１２が直前の上流ノードとなるので、ノード１２に接続されているインタフェースから受信したパケットを転送し、ノード１８に接続されているインタフェースからのパケットは破棄するように設定することとなる。このようにマルチキャストパケットを受信するインタフェースを限定することで、ループ経路発生時のトラフィックの増大を防いでいた。【０００７】
特許文献１では、加入者端末から送出されるフレームをカプセル化し、ＰＥスイッチが自己のアドレスを付与した新たなフレームを構成し、受信したフレームに自己のアドレスがついていればループにより同一フレームを受信したと判断し、破棄するという手法が記載されている。
【特許文献１】特願２００３−０９１２４１
【非特許文献１】ＲＦＣ２２０１
【発明の開示】
【発明が解決しようとする課題】
【０００８】
しかし、非特許文献１や特許文献１等に記載の関連技術による手法は、以下に示すような問題を有していた。【０００９】
第１に、マルチキャストツリーの切り替えに時間がかかるという問題や、また、マルチキャスト冗長配信を実現することができないという問題があった。関連技術においては、ネットワーク上にループが発生したときに、ループにより再到着したパケットを再度送信を行わないように、パケットを受信するインタフェースをひとつに限定していた。これにより、ループの発生により誤った方向からパケットが配信されてきた場合、受信するインタフェースが異なることを検出できるため、パケットの廃棄が可能であり、このことで、ループの発生に伴うパケットの再送信を防止することができた。しかし、このような関連技術による手法は、マルチキャストテーブルを再構築する必要があったからである。【００１０】
例えば、非特許文献１を一例とする関連技術による手法では、障害発生時における切り替えなどに時間がかかるという問題があった。例えば、図２９においてノード１２からノード１５へのリンクに障害が発生したときに、ノード１３からノード１５へのリンクを使用するようマルチキャストツリーを切り替えるケースを考える。パケット転送の停止時間を短くするために、仮にすばやく切り替えたとしても、ＲＰＦチェックで用いる経路表の更新が完了していないと、ノード１５はノード１３からのパケットを受信し転送することができないという問題があった。ここでの経路表は一般にユニキャストの経路表が用いられることが多く、ユニキャストのルーティングプロトコルを用いて構成される。また、マルチキャストツリーの構築プロセスとは別プロセスとして動作させる両者を短時間のうちに終わらせることは難しいという問題があった。また、この障害に対処するために、ノード１５は予めノード１２およびノード１３の両方からパケットを受信するという手法も、ＲＰＦチェックを行っているが故に採用できなかった。【００１１】
第２に、例えば、特許文献１を一例とする関連技術による方法で抑止できるループ経路は、新たなフレームを構成するＰＥルータを含む形で形成されている必要があるため、ＰＥ（Ｐｒｏｖｉｄｅｒ  Ｅｄｇｅ）ルータを含まないようなループ経路が構成された場合、この方式では対応できないという問題があった。また、特許文献１を一例とする関連技術による方法方法では、途中のルータ（ＰＥスイッチ）が、受信したパケットに自身のアドレスを付与することになるため、ＩＰアドレスにフィールドを追加する必要があることから、パケット長が転送可能な最大パケット長を超える場合があり、この場合、フラグメント等の追加処理によって負担が増大するという問題があった。すなわち、受信したパケットに余計な情報を付与するため、ユニキャストの場合に処理負担が増大していた。【００１２】
このように、関連技術による方法手法のみでは複数のインタフェースからマルチキャストパケットの受信を行うことができないという問題があった。すなわち、マルチキャストにおいて、複数の上流ノードから同一のマルチキャストパケットを送信されるような場合にループを検出できないため、ネットワークがループによって輻輳状態になることを防止できないという問題があった。【００１３】
これらのことから、受信インタフェースを限定する方法に代わるループによるパケットの無限コピーを防止するための手法が求められている。【００１４】
（発明の目的）
本発明の目的は、受信インタフェースを限定せずに、ループ検出を行う方法を提供することにある。すなわち、ユニキャストの場合には、受信したパケットに余計な情報を付与することがなく、また、マルチキャストの場合には、複数の上流ノードから同一のマルチキャストパケットを送信されるような場合でも、ループを検出するノード装置、検出方法及び検出プログラムを提供することにある。
【課題を解決するための手段】
【００１５】
本発明によるノード装置は、外部のネットワークと接続するネットワークインターフェイスと、外部のネットワークからパケットを受信するパケット受信部と、外部のネットワークに対してパケットを送信するパケット送信部とを持つノード装置であって、送信済みのパケットに関するパケットを識別するための識別情報を記録するための通過パケット記録データベースと、通過パケット記録データベースを参照し、未送信の受信パケットをパケット送信部へと送るパケット重複判定部を含む。【００１６】
本発明によるパケット転送方法は、パケットの受信を行い、パケットのヘッダ情報に基づき、パケットの転送を行うパケット転送方法であって、送信済みのパケットに関するパケットを識別するための識別情報を記録するステップと、記録済みの識別情報を参照し、未送信の受信パケットを送信対象とするステップを含む。【００１７】
本発明によるパケット転送プログラムは、ネットワークと接続するネットワークインターフェイスと、ネットワークからパケットを受信するパケット受信部と、ネットワークに対してパケットを送信するパケット送信部とを持つノード装置上で実行されるパケット転送プログラムであって、ノード装置に、送信済みのパケットに関するパケットを識別するための識別情報を記録するための通過パケット記録データベースを参照し、未送信の受信パケットをパケット送信部へと送るパケット重複判定処理を実行させる。
【発明の効果】
【００１８】
本発明は、上記手段によって、ループの発生を検出できる。そして、ループの発生により再到着したパケットを破棄する制御を行えば、ループによるネットワークが輻輳状態になることを防ぐことができる。【００１９】
従って、より詳細には、マルチキャストの場合に、複数の上流ノードから同一のマルチキャストパケットを送信されるような場合でも、マルチキャストテーブルを再構築することなくループを検出できる。【００２０】
また、ユニキャストの場合に、受信したパケットに余計な情報を付与することなくループを検出することができる。
【図面の簡単な説明】
【００２１】
【図１】本発明の第１の実施の形態におけるノード装置を示す構成図である。
【図２】第１の実施の形態におけるノード装置１のハードウェア構成例を示すブロック図である。
【図３】第１の実施の形態におけるパケット転送処理の動作を示すフローチャートである。
【図４】第１の実施の形態におけるＲＴＰパケットにおけるＲＴＰヘッダ１０００の各フィールドの構成を示す図である。
【図５】第１の実施の形態におけるＩＰパケットにおけるＩＰヘッダ２０００の各フィールドの構成を示す図である。
【図６】第１の実施の形態におけるＲＴＰパケットが、ＩＰパケットに変換される際の分割例を示した図である。
【図７】本発明の第２の実施の形態におけるノード装置を示す構成図である。
【図８】第２の実施の形態におけるループ防止部１１の動作を示すフローチャートである。
【図９】第２の実施の形態におけるＵＤＰパケットにおけるＵＤＰヘッダの各フィールドの構成を示す図である。
【図１０】本発明の第３の実施の形態におけるノード装置を示す構成図である。
【図１１】第３の実施の形態における管理部２１の動作を示すフローチャートである。
【図１２】本発明の第４の実施の形態におけるノード装置を示す構成図である。
【図１３】第４の実施の形態におけるノード装置１の動作を示すフローチャートである。
【図１４】第４の実施の形態によるサンプリング処理及び判定処理におけるサンプリングパケット重複判定部５１１のより詳細な動作を示すフローチャートである。
【図１５】第４の実施の形態によるセレクタ制御処理におけるサンプリングパケット重複判定部５１１のより詳細な動作を示すフローチャートである。
【図１６】本発明の第５の実施の形態におけるノード装置１の動作を示すフローチャートである。
【図１７】第５の実施の形態によるサンプリング処理及び判定処理におけるサンプリングパケット重複判定部５１１のより詳細な動作を示すフローチャートである。
【図１８】本発明の第６の実施の形態におけるノード装置１の機能構成を示すブロック図である。
【図１９】第６の実施の形態におけるノード装置１の動作を示すフローチャートである。
【図２０】第６の実施の形態によるパケット重複判定部１１２のより詳細な動作を示すフローチャートである。
【図２１】本発明の第７の実施の形態におけるノード装置１の動作を示すフローチャートである。
【図２２】第７の実施の形態によるサンプリング処理及び判定処理におけるサンプリングパケット重複判定部５１１のより詳細な動作を示すフローチャートである。
【図２３】本発明の第８の実施の形態におけるノード装置の構成を示すブロック図である。
【図２４】第８の実施の形態における通過パケット記録データベース１１１が記憶する情報テーブル１１１ａの構成を示す図である。
【図２５】第８の実施の形態におけるノード装置１の動作を示すフローチャートである。
【図２６】本発明の第９の実施の形態におけるノード装置を示す構成図である。
【図２７】第９の実施の形態によるノード装置１の動作を示すフローチャートである。
【図２８】関連技術のＩＰマルチキャストにおいてループ経路が発生していることを示すネットワーク図である。
【図２９】関連技術のＩＰマルチキャストにおいてマルチキャストツリーの切り替えが発生していることを示すネットワーク図である。
【発明を実施するための最良の形態】
【００２２】
（第１の実施の形態）
（構成の説明）
図１は、本発明の第１の実施の形態によるノード装置の機能構成を示すブロック図である。【００２３】
図１において、本実施の形態のノード装置１は、ループパケットの再送信を防止するためのループ防止部１１と、ループ防止部を管理するための管理部２１と、ネットワークインターフェイス４１〜４ｍ経由でループ防止部１１とパケットの送受信を行うパケット受信部３１およびパケット送信部３２と、外部のネットワークと接続するためのネットワークインターフェイス４１−４ｍを備える。【００２４】
なお、パケット送信部３２は、宛先ノードアドレス及びネクストホップのアドレスを有するユニキャストテーブル３２１と、宛先ノードアドレス、次転送先ノードアドレス、送信元ノードアドレス及び上流ノードアドレスを有するマルチキャストテーブル３２２を備える。【００２５】
ループ防止部１１は、受信したパケットが重複しているかどうかを判定するパケット重複判定部１１２と、受信したパケットを記憶しておくための通過パケット記録データベース１１１と、受信したパケットの識別子を抽出するパケット識別子抽出部１１３とを有する。【００２６】
また、管理部２１は、通過パケット記録データベースから受信してから一定時間経過したパケットを削除するデータベースメンテナンス部２１１と、適切なタイムアウト値を計算しデータベースメンテナンス部２１１にその値を通知するタイムアウト値決定部２１３と、パケット重複判定部１１２、データベースメンテナンス部２１１、タイムアウト値決定部２１３の各部に現在時刻を通知するリアルタイムクロック２１２とを有する。【００２７】
ここで、ノード装置１のハードウェア構成の説明をする。【００２８】
図２は、本実施の形態によるノード装置１のハードウェア構成例を示すブロック図である。【００２９】
図２を参照すると、本発明によるノード装置１は、一般的なコンピュータ装置と同様のハードウェア構成によって実現することができ、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）１００１、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）等のメインメモリであり、データの作業領域やデータの一時退避領域に用いられる主記憶部１００２、ネットワーク８を介してデータの送受信を行う通信制御部１００３、周辺機器と接続してデータの送受信を行うインタフェース部１００４、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、磁気ディスク、半導体メモリ等の不揮発性メモリから構成されるハードディスク装置である補助記憶部１００５、本情報処理装置の上記各構成要素を相互に接続するシステムバス１００６等を備えている。【００３０】
本発明によるノード装置１は、その動作を、ノード装置１内部にそのような機能を実現するプログラムを組み込んだ、ＬＳＩ（Ｌａｒｇｅ  Ｓｃａｌｅ  Ｉｎｔｅｇｒａｔｉｏｎ）等のハードウェア部品からなる回路部品を実装してハードウェア的に実現することは勿論として、上述した各構成要素の各機能を提供するプログラムを、コンピュータ処理装置上のＣＰＵ１００１で実行することにより、ソフトウェア的に実現することができる。【００３１】
すなわち、ＣＰＵ１００１は、補助記憶部１００７に格納されているプログラムを、主記憶部１００２にロードして実行し、ノード装置１の動作を制御することにより、上述した各機能をソフトウェア的に実現する。【００３２】
本実施の形態のノード装置１は、マルチキャストテーブル３２２を最初に生成する際に、送信元ノードアドレスをユニキャストテーブル３２１を参照して宛先ノードアドレスとして検出し、ネクストホップのアドレスを取得し、上流アドレスとして設定する機能を有する。【００３３】
（動作の説明）
図１のループ防止部１１および管理部２１の動作を、図３を用いて説明を行う。図３は、本実施の形態によるループ防止部１１および管理部２１の動作を示すフローチャートである。【００３４】
パケット重複判定部１１２は、パケット受信部３１からパケット識別子抽出部１１３を介してパケットＰが送られてくるのを待つ（ステップＳ１０１）。【００３５】
パケットが送られてきた場合、パケット識別子抽出部１１３がパケットの識別子を抽出し、パケット重複判定部１１２は、リアルタイムクロック（ＲＴＣ）２１２からその際の現在時刻ｔｐを取得する（ステップＳ１０２）。【００３６】
次にパケット重複判定部１１２は、受信したパケットＰのペイロードと同一のペイロードを持つパケットが通過パケット記録データベース１１１中に存在しないかどうかを調べる（ステップＳ１０３）。【００３７】
通過パケット記録データベース１１１中に受信パケットＰと同一のペイロードを持つパケットが存在しない場合、パケットＰをパケット送信部３２へと送る（ステップＳ１０４）。【００３８】
さらにパケットＰとステップＳ１０２で取得した受信時刻ｔｐを一組として、通過パケット記録データベース１１１へと記録し（ステップＳ１０５）、ステップＳ１１０へと進む。【００３９】
一方、ステップＳ１０３の処理において通過パケット記録データベース１１１中に受信パケットＰと同一のペイロードを持つパケットＰｏが存在した場合、タイムアウト値決定部２１３は、パケットＰｏの受信時刻ｔｏを通過パケット記録データベース１１１から取得し、時間差ｔｐ−ｔｏを求め、その値をα倍した値をｔｄとする（ステップＳ１０６）。【００４０】
ここでαの値は、１．０≦αとなる値を事前に設定しておくものとする。この値は、伝送遅延の変動分（ジッター）を考慮した係数であり、伝送遅延に対してジッターが最大１０％程度見込まれるのであれば、α＝１．１とする。【００４１】
次に、タイムアウト値決定部２１３は、現在のタイムアウト値Ｔとｔｄの比較を行い（ステップＳ１０７）、ｔｄの方が大きい場合に、ｔｄを新たなタイムアウト値Ｔと定める（ステップＳ１０８）。【００４２】
次に、データベースメンテナンス部２１１においてパケットＰの廃棄を行う（ステップＳ１０９）。【００４３】
ステップＳ１１０では、通過パケット記録データベース１１１上のパケットのうち、受信時刻と現在時刻との差がタイムアウト値以上のパケットをデータベースメンテナンス部２１１が削除する。【００４４】
なお、ステップＳ１０５とステップＳ４０４の順序が入れ替わってもよい。また、通過パケット記録データベース１１１への現在時刻ｔｐの記録を、パケットの送信時（ステップＳ１０５）ではなく、パケットの受信時（ｔｐ取得時（ステップＳ１０２））に行ってもよい。さらに、ステップＳ１０５において取得している受信時の現在時刻ｔｐは、ステップＳ１０４においてステップＳ１０２と同様にして送信時の現在時刻ｔｐを取得することによって、送信時の現在時刻ｔｐであってもよい。【００４５】
また、ステップＳ１０７において用いるタイムアウト値Ｔに上限値を設けてもよいし、または、ステップＳ１０７において現在のタイムアウト値Ｔとｔｄの比較を行い、ｔｄの方が小さい場合に、ｔｄを新たなタイムアウト値Ｔと定めてもよく、この場合に新たなタイムアウト値Ｔの下限値を設けてもよい。【００４６】
パケットを一意に識別するための識別情報として、パケットのペイロードを用いていたが、パケットのペイロードのハッシュ値を用いてもよい。ペイロードのハッシュ値を用いることで、ハッシュ値を計算するステップが余分に必要になるが、パケット重複判定部における送信済みかどうかの判定処理の負荷が少なくなる。また一パケットあたりの識別情報のサイズが小さくなるので、通過パケット記録データベースのサイズを小さくすることができる。【００４７】
また、パケットを一意に識別するための識別情報として、図４に示すＲＴＰヘッダ１０００中のシーケンス番号フィールド（１０１２）に格納されている値であるシーケンス番号１０１２を用いてもよい。【００４８】
また、図５中のＩＰヘッダ２０００における識別子２０２１、およびフラグメントオフセット２０２３の値の組を、前述の例でのＲＴＰヘッダ１０００におけるシーケンス番号１０１２の代わりに使ってもよい。【００４９】
前述の方法では、ＲＴＰヘッダ１０００を利用するために、ＲＴＰパケット単位での処理になっていた。ＲＴＰパケットのサイズが大きい場合、ＩＰヘッダ２０００を付与する段階で分割されて、送信される（図６）。分割されたデータを受信先で再度組み立てる時に用いるのが、図５のＩＰヘッダ２０００中の識別子フィールド２０２１およびフラグメントオフセットフィールド２０２３である。図６に示すＵＤＰヘッダ３０００、ＩＰヘッダ２０００、データ４０１１を有するパケット４０００中において、分割されたパケット群４１００，  ４２００，  ４３００は同一の識別子を持つ。また、フラグメントオフセットフィールド２０２３には、先頭フラグメントである図６中のパケット４１００では０の値が、その他のパケット４２００、４３００では、その相対位置が８オクテットを単位とする値が格納される。これらの値の組を用いることで、ＩＰレベルでのパケットを一意に識別することが可能である。【００５０】
（第１の実施の形態の効果）【００５１】
本実施の形態によれば、スタティック（Ｓｔａｔｉｃ）に１つ、または複数の上流ノードが与えられるノードにおいて、ループの発生により再到着したパケットを破棄することにより、ネットワークがループによって輻輳状態になることを防ぐことができる。【００５２】
従って、本実施の形態によれば、マルチキャストの場合に、複数の上流ノードから同一のマルチキャストパケットを送信されるような場合でも、マルチキャストテーブルを再構築することなくループを検出できるため、ネットワークがループによって輻輳状態になることを防ぎ、ユニキャストの場合に、受信したパケットに余計な情報を付与することがなくパケット長が伸びずに済むため、フラグメントが起こりにくく、また、ループ発生時のトラヒックを削減することができる。【００５３】
また、本実施の形態によれば、パケットＰｏの受信時刻ｔｏを通過パケット記録データベース１１１から取得し、時間差ｔｐ−ｔｏを求め、その値をα倍した値をｔｄとし、現在のタイムアウト値Ｔとｔｄの比較を行い、例えば、ｔｄの方が大きい場合に、ｔｄを新たなタイムアウト値Ｔと定め、通過パケット記録データベース１１１上のパケットのうち、受信時刻と現在時刻との差がタイムアウト値以上のパケットを削除するため、受信したパケットを記録しておく通過パケット記録データベース１１１のメモリ量を抑制できる。【００５４】
一度受信したパケットを通過パケット記録データベース１１１に記録しておき、通過パケット記録データベース１１１に記録されたものと同一のパケットを再度受信した際に、当該サイド受信したパケットを廃棄する場合、受信したパケットを記録しておくためのメモリ量が膨大になることから、一度記録したパケットを、ある程度の時間の経過後、メモリ上から削除する必要がある。このとき、一度記録したパケットをどのタイミングでメモリ上から削除すればよいか、適切な値を決めるための方法がない場合、もし、早く削除してしまうとループの発生により再受信したパケットが過去に一度受け取っていたかどうかを判断することができない。一方、もし削除するまでの時間が長い場合、大量のパケットをメモリ上に記録しておく必要があるため、大量のメモリが必要になる。また、パケットを受信するたびに、メモリ上の過去に受信したパケットと重複判定を行う必要があるため、処理負荷が大きくなる。しかし、本実施の形態によれば、本実施の形態によって副次的に生じうるこのような問題も上記説明したように解決することができる。【００５５】
また、ステップＳ１１０における、通過パケット記録データベース上からパケットを削除する処理は以下のようにしてもよい。すなわち、予め通過パケット記録データベース１１１に記録可能なパケットの識別情報の最大数を定めておき、この最大数を超えたときに超過分の識別情報を受信時刻が古い順に削除する。通過パケット記録データベース１１１は実際にはメモリ上などに構築される。メモリは、記憶容量が有限であり、また通過パケット記録データベース１１１以外の用途にも使用されるため、この方法を用いることで他の処理に影響を与えないという効果がある。またこの方法と前述の方法を組み合わせて使用してもよい。【００５６】
（第２の実施の形態）
（構成の説明）
次に、本発明の第２の実施の形態の構成について図７を参照して詳細に説明する。【００５７】
図７を参照すると、通過パケット記録データベース１１１の代わりに、フロー単位通過パケット記録データベース１２１〜１２ｎまでを有する点、およびフロー識別部１１４を有する点が、第１の実施の形態と異なる。【００５８】
フロー単位通過パケット記録データベース１２１〜１２ｎには、フロー毎に分けて送信済みパケットが記録される。【００５９】
フロー識別部１１４は、パケット受信部３１からパケット識別子抽出部１１３を介して受け取ったパケットのヘッダを参照し、パケットがどのフローに属しているかの判別を行う機能と、さらに、受信パケットをパケット重複判定部１１２へ送る際に、特定したフローに関する情報もあわせて通知する機能とを有する。【００６０】
パケットがどのフローに属するかは、パケットの送信元アドレス、宛先アドレス、送信元ポート番号、宛先ポート番号のいずれかの値もしくはいずれかの値の組を用いることで識別可能である。例えば、ネットワーク層のプロトコルにＩＰを使用している場合には、図５のＩＰヘッダ２０００中の送信元アドレスフィールド２０４１，宛先アドレスフィールド２０５１を参照することでそれぞれ送信元アドレス２０４１、宛先アドレス２０５１を知ることができる。またトランスポート層のプロトコルにＵＤＰを使用している場合には、図９のＵＤＰヘッダ３０００中の送信元ポート番号フィールド３０１１，宛先ポート番号フィールド３０１２を参照することでそれぞれ送信元ポート番号３０１１、宛先ポート番号３０１２を知ることができる。【００６１】
パケット重複判定部１１２では、フロー識別部１１４により通知されたパケットがどのフローに属しているかという情報に基づき、対応するフロー単位通過パケット記録データベース１２１〜１２ｎ中の送信済みパケットの識別情報を用いて、受信パケットが送信済みかどうかの判定を行う。【００６２】
（動作の説明）
図７のループ防止部１１の動作を、図８を用いて説明を行う。図８は、本実施の形態によるループ防止部１１の動作を示すフローチャートである。【００６３】
ループ防止部１１が、送信済みパケットの識別情報をフロー毎に分けてフロー単位通過パケット記録データベース１２１〜１２ｎに保存する（ステップＳ２０１）。【００６４】
フロー識別部１１４が、パケット受信部３１からパケット識別子抽出部１１３を介して受け取ったパケットのヘッダを参照し、パケットがどのフローに属しているかの判別を行い（ステップＳ２０２）、受信パケット及び特定したフローに関する情報をパケット重複判定部１１２へ送る（ステップＳ２０３）。【００６５】
パケット重複判定部１１２が、フロー識別部１１４により通知されたパケットがどのフローに属しているかという情報に基づき、対応するフロー単位通過パケット記録データベース１２１〜１２ｎ中の送信済みパケットの識別情報を用いて、受信パケットが送信済みか否かの判定を行い（ステップＳ２０４）、まだ送信を行っていないパケットをパケット送信部３２に送り（ステップＳ２０５）、送信済みのパケットを廃棄する（ステップＳ２０６）。【００６６】
（第２の実施の形態の効果）
本実施の形態によれば、送信済みパケットの識別情報をフロー毎に分けてフロー単位通過パケット記録データベース１２１〜１２ｎに保存しておき、パケット重複判定部１１２が、フロー識別部１１４により通知されたパケットがどのフローに属しているかという情報に基づき、対応するフロー単位通過パケット記録データベース１２１〜１２ｎ中の送信済みパケットの識別情報を用いて、受信パケットが送信済みかどうかの判定を行うため、受信パケットが送信済みか否かを判定する判定処理の負荷を軽減できる。【００６７】
（第３の実施の形態）
（構成の説明）
次に、本発明の第３の実施の形態について図１０を参照して詳細に説明する。【００６８】
図１０を参照すると、タイムアウト値決定部２１３の代わりに、時間差計算部２１４および時間差統計処理部２１５を有する点が、第１の実施の形態とは異なる。【００６９】
時間差計算部２１４は、パケット重複判定部１１２から重複していると判定されたパケットの受信時刻ｔｐと同一のペイロードを持つパケットＰｏの受信時刻ｔｏとの時間差ｔｓを求め、求めた時間差ｔｓを時間差統計処理部２１３へと通知する。【００７０】
時間差統計処理部２１５は、時間差計算部２１４から通知される時間差ｔｓを用いて統計処理を行い、タイムアウト値Ｔを決定する。ここでの統計処理の例としては、あらかじめ決められた回数だけ時間差ｔｓが時間差計算部２１４から通知されるのを待ち、それらの値の平均ｍおよび分散σ２を求める。次に、求めた平均ｍおよび分散σ２を正規分布の確率分布関数Ｆ（ｘ）に適用し、Ｆ（ｘ）  ＝０．９９となるｘを求め、その値をタイムアウト値Ｔとする。時間差ｔｓが正規分布に従うとした場合、ループにより再到着するパケットのうち９９％のパケットははじめに受信したときより起算して、この時間内に届くということを示している。ここで求められたタイムアウト値Ｔは、時間差統計処理部２１４からデータベースメンテナンス部２１１へ通知され、データベース中のパケットのライフタイム管理に利用される。【００７１】
（動作の説明）
図１０の管理部２１の動作を、図１１を用いて説明を行う。図１１は、本実施の形態による管理部２１の動作を示すフローチャートである。【００７２】
時間差計算部２１４が、パケット重複判定部１１２から重複していると判定されたパケットの受信時刻ｔｐと同一のペイロードを持つパケットＰｏの受信時刻ｔｏとの時間差ｔｓを求め（ステップＳ３０１）、求めた時間差ｔｓを時間差統計処理部２１３へと通知する（ステップＳ３０２）。【００７３】
時間差統計処理部２１５が、時間差計算部２１４から通知される時間差ｔｓの値の平均ｍおよび分散σ２を確率分布関数Ｆ（ｘ）に適用して求めた、Ｆ（ｘ）  ＝０．９９となるｘによりタイムアウト値Ｔを算出する（ステップＳ３０３）。【００７４】
データベースメンテナンス部２１１が、当該タイムアウト値Ｔを用い、データベース中のパケットのライフタイムを管理する（ステップＳ３０４）。【００７５】
（第３の実施の形態の効果）
本実施の形態によれば、時間差統計処理部２１５が、時間差計算部２１４から通知される時間差ｔｓを用いて統計処理を行い、タイムアウト値Ｔを決定し、データベースメンテナンス部２１１が、当該タイムアウト値Ｔを用い、データベース中のパケットのライフタイムを管理することにより、所要時間内に到着するパケットが所定の確率でループにより再到着したものであると判定できる。【００７６】
（第４の実施の形態）
（構成の説明）
次に、本発明の第４の実施の形態について図１２を参照して詳細に説明する。【００７７】
図１２を参照すると、第１の実施の形態に加えて、セレクタ６１およびループ検出部５１を有する点が異なる。【００７８】
ループ検出部５１は、サンプリングパケット重複判定部５１１およびサンプリングパケット記録データベース５１２から構成される。【００７９】
セレクタ６１は、ループ防止部１１及びループ検出部５１からの指示に従い、パケット受信部３１から受け取ったパケットを、サンプリングパケット重複判定部５１１、もしくはパケット識別子抽出部１１３を介したパケット重複判定部１１２のいずれかに送る。【００８０】
サンプリングパケット重複判定部５１１は、セレクタ６１から送られてきたパケットのサンプリング処理を行い、サンプリングパケット記録データベース５１２に記録されているサンプリングパケットを参照し、サンプリング対象となったパケットが送信済みであるか否かの判定を行う。なお、本実施の形態におけるサンプリングの処理とは、全受信パケットのうちの一部の受信パケットを対象としてパケットが送信済みであるか否かの判定を行うものである。ここでのサンプリング処理は、次のような方法で行う。パケットのペイロードのハッシュ値を求め、求めたハッシュ値を予め定められた数Ｎで割り、その剰余が予め決められた数Ｓと一致したとき、そのパケットをサンプリング対象として抽出する。ループが発生していることを検出するためには、一度サンプリング対象となったパケットが、ループの発生により再度ノード装置１に到着したときに、再到着したパケットが必ずサンプリング対象となる必要がある。ループ経路により再到着したパケットは、ヘッダ中の一部のフィールドを除き、初めて到着したときと違いはないため、前述のサンプリング方法を用いることで目的を達成できる。【００８１】
サンプリングパケット重複判定部５１１は、前述の方法でパケットが送信済みであると判定することによってループを検出したら、セレクタ６１に対し、セレクタ６１が以降受信したパケットをパケット識別子抽出部１１３を介してパケット重複判定部１１２へと送るよう指示を出す。【００８２】
サンプリングパケット重複判定部５１１は、前述の方法で送信済みでないと判定したパケットをサンプリングパケットとしてサンプリングパケット記録データベース５１２に記録する。【００８３】
パケット重複判定部１１２は、サンプリングパケット重複判定部５１１によるループ検出後に、全ての受信パケットに対して、すでに送信済みであるか否かの判定を行い、まだ送信を行っていない場合に送信を行う。【００８４】
（動作の説明）
図１２のノード装置１の動作を、図１３を用いて説明を行う。図１３は、本実施の形態によるノード装置１の動作を示すフローチャートである。【００８５】
セレクタ６１が、パケット受信部３１から受け取ったパケットを、サンプリングパケット重複判定部５１１に送る（ステップＳ４０１）。【００８６】
サンプリングパケット重複判定部５１１は、セレクタ６１から送られてきたパケットのサンプリング処理を行い（ステップＳ４０２）、サンプリングパケット記録データベース５１２に記録されているサンプリングパケットを参照し、サンプリング対象となったパケットが送信済みであるか否かの判定処理を行う（ステップＳ４０３）。【００８７】
サンプリングパケット重複判定部５１１は、前述の方法でパケットが送信済みであると判定することによってループを検出したら、セレクタ６１に対し、セレクタ６１が以降受信したパケットをパケット識別子抽出部１１３を介してパケット重複判定部１１２へと送るよう指示を出す（ステップＳ４０４）。【００８８】
パケット重複判定部１１２が、サンプリングパケット重複判定部５１１によるループ検出後に、セレクタ６１からの全ての受信パケットに対して、すでに送信済みであるか否かの判定を行い（ステップＳ４０５）、まだ送信を行っていないパケットをパケット送信部３２に送り（ステップＳ４０６）、送信済みのパケットを廃棄する（ステップＳ４０７）。【００８９】
ここで、ステップＳ４０２におけるサンプリング処理及びステップＳ４０３における判定処理を図１４を用いてより詳細に説明する。図１４は、サンプリング処理及び判定処理におけるサンプリングパケット重複判定部５１１のより詳細な動作を示すフローチャートである。【００９０】
サンプリングパケット重複判定部５１１は、セレクタ６１から送られてきたパケットのペイロードのハッシュ値を求め（ステップＳ５０１）、ハッシュ値を予め決められた値Ｎで割った剰余が、予め決められた値Ｓであるパケットを抽出する（ステップＳ５０２）。また、サンプリングパケット重複判定部５１１は、セレクタ６１から送られてきたパケットのペイロード中の特定のフィールドの値が予め決められた値であるパケットを抽出してもよい（ステップＳ５０１、Ｓ５０２）。【００９１】
その後、サンプリングパケット重複判定部５１１は、抽出したパケットを対象としてサンプリングパケット記録データベース５１２に記録されているサンプリングパケットを参照し（ステップＳ５０３）、ペイロードやシーケンス番号も同一か否か比較することによって、セレクタ６１から送られてきたパケットの重複判定をする（ステップＳ５０４）。【００９２】
すなわち、サンプリングパケット重複判定部５１１は、例えば、パケットのハッシュが１０で割った際の余りが１であったとすると、該当する余りが１であるパケットだけを、サンプリングパケット記録データベース５１２に記録されているサンプリングパケットを参照し、ペイロードやシーケンス番号も同一か否かを比較することによって、重複判定をする。この場合、セレクタ６１から送られてきたパケットの１０個に１個の割合で重複判定が行われる。【００９３】
ここで、ステップＳ４０４におけるセレクタ制御処理を図１５を用いてより詳細に説明する。図１５は、セレクタ制御処理におけるサンプリングパケット重複判定部５１１のより詳細な動作を示すフローチャートである。【００９４】
ループが検出されない場合に、パケット受信部３１から受け取ったパケットをサンプリングパケット重複判定部５１１に送るセレクタ６１に対し、サンプリングパケット重複判定部５１１は、ループを検出した場合、セレクタ６１が以降受信したパケットをパケット識別子抽出部１１３を介してパケット重複判定部１１２へと送るよう指示を出す（ステップＳ６０１）。【００９５】
セレクタ６１は、サンプリングパケット重複判定部５１１からの指示に基づいて、パケット受信部３１から受け取ったパケットの送信先をパケット重複判定部１１２に切替える（ステップＳ６０２）。【００９６】
パケット重複判定部１１２は、所定の時間、パケット重複を検出しない場合、パケット受信部３１から受け取ったパケットをパケット重複判定部１１２に送るセレクタ６１に対し、セレクタ６１が以降受信したパケットをサンプリングパケット重複判定部５１１へと送るよう指示を出す（ステップＳ６０３）。なお、セレクタ６１に対する当該指示は、パケット重複判定部１１２において、パケット監視数が所定の回数以上に達した場合や、１０回連続で重複が発生しなかった場合等に行われてもよい。【００９７】
セレクタ６１は、パケット重複判定部１１２からの指示に基づいて、パケット受信部３１から受け取ったパケットの送信先をサンプリングパケット重複判定部５１１に切替える（ステップＳ６０４）。【００９８】
なお、本実施の形態は、例えば、前述の第２、第３の実施の形態等と組み合わせることも可能である。【００９９】
（第４の実施の形態の効果）
ループの検出と、ループ経路により再到着するパケットの再送信の抑制とを別々に行うことにより、ループ未発生時の処理負荷の抑制を実現している。【０１００】
すなわち、本実施の形態によれば、サンプリングパケット記録データベース５１２にサンプリングパケットを記録するので、サンプリングパケット記録データベース５１２に記録するデータ量が抑制され、比較処理の負担が軽減される。【０１０１】
また、本実施の形態によれば、サンプリングパケット重複判定部５１１が、セレクタ６１から送られてきたパケットのハッシュ値のサンプリング処理を行い、サンプリングパケット記録データベース５１２に記録されているサンプリングパケットのハッシュ値を参照し、サンプリング対象となったハッシュ値に係るパケットが送信済みであるか否かの判定を行うため、処理負担が軽減される。【０１０２】
また、パケットのハッシュを１０で割った際の余りが１であるパケットを抽出する場合においてループが発生した際、１０分の１の確率で、サンプリング対象でなかったパケットをサンプリングパケット記録データベース５１２に記録されているパケットであると誤判定してしまうが、本実施の形態では、サンプリング処理したパケットに対してペイロードやシーケンス番号も一致するか否かを比較することにより、より確実にループの発生を検出できる。【０１０３】
（第５の実施の形態）
次に、本発明の第５の実施の形態について説明する。【０１０４】
本実施の形態は、第４の実施の形態と同様の構成を有するが、通常はペイロードのハッシュ値やペイロードの一部分を対象として比較処理を行い、当該比較処理でループが検出された場合にペイロード全体の比較処理を行ってループ検出を行う点で第４の実施の形態と異なるため、相違する点を中心に以下説明する。【０１０５】
（動作の説明）
図１６は、本実施の形態によるノード装置１の動作を示すフローチャートである。【０１０６】
まず、通常はセレクタ６１が、パケット受信部３１から受け取った全てのパケットをパケット重複判定部１１２に送り（ステップＳ７０１）、パケット重複判定部１１２が、受信した全てのパケットを対象とし、パケットの一部分であるペイロード中の特定のフィールドの値若しくはペイロードのハッシュ値を求め（ステップＳ７０２）、通過パケット記録データベース１１１のペイロード中の特定のフィールドの値若しくはペイロードのハッシュ値を参照して一致するか否かを判定する（ステップＳ７０３）。【０１０７】
パケット重複判定部１１２は、一致しない場合に、当該ペイロード中の特定のフィールドの値若しくはペイロードのハッシュ値を通過パケット記録データベース１１１に記録し、当該ペイロードに係るパケットをパケット送信部３２に送る（ステップＳ７０４）。【０１０８】
また、パケット重複判定部１１２は、一致する場合に、ループを検出したと暫定的に判定し、セレクタ６１に対し、セレクタ６１が以降受信したパケットをサンプリングパケット重複判定部５１１へと送るよう指示を出す（ステップＳ７０５）。【０１０９】
サンプリングパケット重複判定部５１１は、セレクタ６１から送られてきたパケットのハッシュ値のサンプリング処理を行い（ステップＳ７０６）、サンプリングパケット記録データベース５１２に記録されているサンプリングパケットを参照し、サンプリング対象となったパケットが送信済みであるか否かの判定処理を行う（ステップＳ７０７）。【０１１０】
サンプリングパケット重複判定部５１１は、所定の時間、パケット重複を検出しない場合、セレクタ６１に対し、セレクタ６１が以降受信したパケットをパケット重複判定部１１２へと送るよう指示を出す（ステップＳ７０８）。なお、セレクタ６１に対する当該指示は、サンプリングパケット重複判定部５１１において、パケットの監視数が所定の回数以上に達した場合や、１０回連続で重複が発生しなかった場合等に行われてもよい。またサンプリングパケット重複判定部５１１は、ステップＳ７０７において当該サンプリング対象となったパケットが送信済みであると判定した場合、当該パケットを廃棄する（ステップＳ７０９）。【０１１１】
ここで、ステップＳ７０５におけるサンプリング処理及びステップＳ７０７における判定処理を図１７を用いてより詳細に説明する。図１７は、サンプリング処理及び判定処理におけるサンプリングパケット重複判定部５１１のより詳細な動作を示すフローチャートである。【０１１２】
サンプリングパケット重複判定部５１１は、セレクタ６１から送られてきたパケットのペイロードのハッシュ値を求め（ステップＳ８０１）、例えば、当該ハッシュ値を１０で割った余り（特定フィールドの値）がａであるか否かを判定し（ステップＳ８０２）、ａであるパケットを抽出する（ステップＳ８０３）。【０１１３】
その後、サンプリングパケット重複判定部５１１は、抽出したパケットを対象としてサンプリングパケット記録データベース５１２に記録されているサンプリングパケットを参照し、特定フィールドの値がａでありペイロードが同一のパケットの有無を判定することによって、セレクタ６１から送られてきたパケットの重複判定をする（ステップＳ８０４）。【０１１４】
サンプリングパケット重複判定部５１１は、ステップＳ８０２において特定フィールドの値がａでなかったパケットをパケット送信部３２に送り（ステップＳ８０７）、また、ステップＳ８０４において重複しなかったパケットのａの値とペイロードを組にしてサンプリングパケット記録データベース５１２に記録し（ステップＳ８０５）、当該パケットをパケット送信部３２に送る（ステップＳ８０６）。【０１１５】
サンプリングパケット重複判定部５１１は、ステップＳ８０４において重複したパケットを廃棄するモードに移行する（ステップＳ８０８）。【０１１６】
（第５の実施の形態の効果）
本実施の形態によれば、パケット重複判定部１１２が、受信した全てのパケットを対象とし、パケットの一部分であるペイロード中の特定のフィールドの値若しくはペイロード等のハッシュ値を求め、通過パケット記録データベースのハッシュ値を参照して一致するか否かを判定するため、処理負担が軽減される。【０１１７】
また、本実施の形態によれば、パケット重複判定部１１２は、求めたハッシュ値を通過パケット記録データベース１１１に記録するため、記録に要する容量を抑制できる。【０１１８】
また、本実施の形態によれば、通過パケット記録データベース１１１に記録するデータ量が抑制されるため、比較処理の負担が軽減される。【０１１９】
また、本実施の形態によれば、サンプリングパケット重複判定部５１１は、抽出したパケットのａの値とペイロードを組にしてサンプリングパケット記録データベース５１２に記録するため、記録に要する容量を抑制できる。【０１２０】
また、本実施の形態によれば、サンプリングパケット記録データベース５１２に記録するデータ量が抑制されるため、比較処理の負担が軽減される。【０１２１】
（第６の実施の形態）
次に、本発明の第６の実施の形態について説明する。【０１２２】
（構成の説明）
本実施の形態は、第４の実施の形態と同様の構成を有するが、パケット検出部においてサンプリング処理を行わず、受信したパケットすべてを比較対象としている点、およびパケット検出部における比較処理において、ペイロード中の特定のフィールドの値若しくはペイロードのハッシュ値を比較対象として用いている点で第４の実施の形態と異なるため、相違する点を中心に以下説明する。【０１２３】
図１８は、本実施の形態によるノード装置の機能構成を示すブロック図である。【０１２４】
図１８を参照すると、本実施の形態によるループ検出部５１が、サンプリングパケット重複判定部５１１およびサンプリングパケット記録データベース５１２ではなく、パケット重複仮判定部５１３およびループ検出用パケット記録データベース５１４を備える点で第４の実施の形態と相違する。【０１２５】
パケット重複仮判定部５１３は、セレクタ６１から送られてきた全てのパケットを対象とし、パケットの一部分であるペイロード中の特定のフィールドの値若しくはペイロードのハッシュ値を求め、ループ検出用パケット記録データベース５１４のペイロード中の特定のフィールドの値若しくはペイロードのハッシュ値を参照して一致するか否かを判定する。【０１２６】
ここで、パケット重複仮判定部５１３は、一致しない場合に、当該ペイロード中の特定のフィールドの値若しくはペイロードのハッシュ値をループ検出用パケット記録データベース５１４に記録し、当該ペイロードに係るパケットをパケット送信部３２に送る。【０１２７】
また、パケット重複仮判定部５１３は、一致する場合に、ループを検出したと暫定的に判定し、セレクタ６１に対し、セレクタ６１が以降受信したパケットをパケット重複判定部１１２へと送るよう指示を出す。【０１２８】
本実施の形態によるパケット重複判定部１１２は、セレクタ６１からパケット識別子抽出部１１３を介して送られてきたパケットを対象とし、通過パケット記録データベース１１１に記録されているパケットを参照し、ペイロードの比較を行い、当該送られてきたパケットが送信済みであるか否かの判定処理を行う。【０１２９】
本実施の形態によるセレクタ６１は、通常、パケット受信部３１から受け取った全てのパケットをパケット重複仮判定部５１１に送る。【０１３０】
（動作の説明）
図１９は、本実施の形態によるノード装置１の動作を示すフローチャートである。【０１３１】
まず、通常はセレクタ６１が、パケット受信部３１から受け取った全てのパケットをパケット重複仮判定部５１３に送り（ステップＳ９０１）、パケット重複仮判定部５１３が、セレクタ６１から送られてきた全てのパケットを対象とし、パケットの一部分であるペイロード中の特定のフィールドの値若しくはペイロードのハッシュ値を求め（ステップＳ９０２）、ループ検出用パケット記録データベース５１４のペイロード中の特定のフィールドの値若しくはペイロードのハッシュ値を参照して一致するか否かを判定する（ステップＳ９０３）。【０１３２】
ここで、パケット重複仮判定部５１３は、一致しない場合に、当該ペイロード中の特定のフィールドの値若しくはペイロードのハッシュ値をループ検出用パケット記録データベース５１４に記録し、当該ペイロードに係るパケットをパケット送信部３２に送る（ステップＳ９０４）。【０１３３】
また、パケット重複仮判定部５１３は、一致する場合に、ループを検出したと暫定的に判定し、セレクタ６１に対し、セレクタ６１が以降受信したパケットをパケット重複判定部１１２へと送るよう指示を出す（ステップＳ９０５）。【０１３４】
本実施の形態によるパケット重複判定部１１２は、セレクタ６１からパケット識別子抽出部１１３を介して送られてきたパケットを対象とし、通過パケット記録データベース１１１に記録されているパケットを参照し（ステップＳ９０６）、ペイロードの比較を行い、当該送られてきたパケットが送信済みであるか否かの判定処理を行う（ステップＳ９０７）。【０１３５】
本実施の形態によるパケット重複判定部１１２は、所定の時間、パケット重複を検出しない場合、セレクタ６１に対し、セレクタ６１が以降受信したパケットをパケット重複仮判定部５１３へと送るよう指示を出す（ステップＳ９０８）。なお、セレクタ６１に対する当該指示は、本実施の形態によるパケット重複判定部１１２において、パケットの監視数が所定の回数以上に達した場合や、１０回連続で重複が発生しなかった場合等に行われてもよい。また、本実施の形態によるパケット重複判定部１１２は、ステップＳ９０７において当該送られてきたパケットが送信済みであると判定した場合、当該パケットを廃棄する（ステップＳ９０９）。【０１３６】
ここで、ステップＳ９０７における判定処理を図２０を用いてより詳細に説明する。図２０は、判定処理におけるパケット重複判定部１１２のより詳細な動作を示すフローチャートである。【０１３７】
まず、パケット重複判定部１１２は、抽出したパケットを対象として通過パケット記録データベース１１１に記録されているパケットを参照し、ペイロードが同一のパケットの有無を判定することによって、セレクタ６１から送られてきたパケットの重複判定をする（ステップＳ１００１）。【０１３８】
パケット重複判定部１１２は、ステップＳ１００１において重複しなかったパケットのペイロードを通過パケット記録データベース１１１に記録し（ステップＳ１００２）、当該パケットをパケット送信部３２に送る（ステップＳ１００３）。【０１３９】
また、パケット重複判定部１１２は、ステップＳ１００１において重複であると判定されたパケットを廃棄する（ステップＳ１００４）。【０１４０】
（第６の実施の形態の効果）
第４の実施の形態と同様に、ループの検出と、ループ経路により再到着するパケットの再送信の抑制とを別々に行うことにより、ループ未発生時の処理負荷の抑制を実現している。【０１４１】
すなわち、本実施形態によれば、パケット重複仮判定部５１３においてループが検出されるまでは、ペイロード中特定のフィールドの値もしくはペイロードのハッシュ値を用いて比較処理を行っている。このことにより常にペイロード全体を比較する第一の実施形態に対し、比較処理の負荷を軽減できる。【０１４２】
（第７の実施の形態）
次に、本発明の第７の実施の形態について説明する。【０１４３】
本実施の形態は、第４の実施の形態と同様の構成を有するが、パケットのハッシュ値を対象としてサンプリング処理及びループ検出を行う点で第４の実施の形態と異なるため、相違する点を中心に以下説明する。【０１４４】
（動作の説明）
図２１は、本実施の形態によるノード装置１の動作を示すフローチャートである。【０１４５】
まず、通常はセレクタ６１が、パケット受信部３１から受け取った全てのパケットをパケット重複判定部１１２に送り（ステップＳ１１０１）、パケット重複判定部１１２が、受信した全てのパケットを対象とし、パケットの一部分であるペイロード中の特定のフィールドの値若しくはペイロード等のハッシュ値を求め（ステップＳ１１０２）、通過パケット記録データベースのハッシュ値を参照して一致するか否かを判定する（ステップＳ１１０３）。【０１４６】
パケット重複判定部１１２は、一致しない場合に、当該求めたハッシュ値を通過パケット記録データベース１１１に記録し、当該求めたハッシュ値に係るパケットをパケット送信部３２に送る（ステップＳ１１０４）。【０１４７】
また、パケット重複判定部１１２は、一致する場合に、ループを検出したと暫定的に判定し、セレクタ６１に対し、セレクタ６１が以降受信したパケットをサンプリングパケット重複判定部５１１へと送るよう指示を出す（ステップＳ１１０５）。【０１４８】
サンプリングパケット重複判定部５１１は、セレクタ６１から送られてきたパケットのハッシュ値のサンプリング処理を行い（ステップＳ１１０６）、サンプリングパケット記録データベース５１２に記録されているサンプリングパケットのハッシュ値を参照し、サンプリング対象となったハッシュ値に係るパケットが送信済みであるか否かの判定処理を行う（ステップＳ１１０７）。【０１４９】
サンプリングパケット重複判定部５１１は、所定の時間、パケット重複を検出しない場合、セレクタ６１に対し、セレクタ６１が以降受信したパケットをパケット重複判定部１１２へと送るよう指示を出す（ステップＳ１１０８）。なお、セレクタ６１に対する当該指示は、サンプリングパケット重複判定部５１１において、ハッシュ値の監視数が所定の回数以上に達した場合や、１０回連続で重複が発生しなかった場合等に行われてもよい。【０１５０】
ここで、ステップＳ１１０６におけるサンプリング処理及びステップＳ１１０７における判定処理を図２２を用いてより詳細に説明する。図２２は、サンプリング処理及び判定処理におけるサンプリングパケット重複判定部５１１のより詳細な動作を示すフローチャートである。【０１５１】
サンプリングパケット重複判定部５１１は、セレクタ６１から送られてきたパケットのペイロードのハッシュ値を求め（ステップＳ１２０１）、例えば、当該ハッシュ値を１０で割った余りの値（特定フィールドの値）がｂであるか否かを判定し（ステップＳ１２０２）、ハッシュ値のパケットを抽出する（ステップＳ１２０３）。【０１５２】
その後、サンプリングパケット重複判定部５１１は、抽出したパケットのハッシュ値を対象としてサンプリングパケット記録データベース５１２に記録されているサンプリングパケットのハッシュ値を参照し、当該ハッシュ値を１０で割った余りの値（特定フィールドの値）がｂであるハッシュ値の有無を判定することによって、セレクタ６１から送られてきたパケットの重複判定をする（ステップＳ１２０４）。【０１５３】
サンプリングパケット重複判定部５１１は、ステップＳ１２０２において余りの値がｂでなかったハッシュ値に係るパケットをパケット送信部３２に送り（ステップＳ１２０７）、また、ステップＳ１２０３において重複しなかったハッシュ値をサンプリングパケット記録データベース５１２に記録し（ステップＳ１２０５）、当該パケットをパケット送信部３２に送る（ステップＳ１２０５）。【０１５４】
サンプリングパケット重複判定部５１１は、ステップＳ１２０３において重複したハッシュ値に係るパケットを廃棄するモードに移行する（ステップＳ１２０８）。【０１５５】
（第７の実施の形態の効果）
本実施の形態によれば、パケット重複判定部１１２が、受信した全てのパケットを対象とし、パケットの一部分であるペイロード中の特定のフィールドの値若しくはペイロード等のハッシュ値を求め、通過パケット記録データベース１１１内のハッシュ値を参照して一致するか否かを判定するため、処理負担が軽減される。【０１５６】
また、本実施の形態によれば、パケット重複判定部１１２は、求めたハッシュ値を通過パケット記録データベース１１１に記録するため、記録に要する容量を抑制できる。【０１５７】
また、本実施の形態によれば、通過パケット記録データベース１１１に記録するデータ量が抑制されるため、比較処理の負担が軽減される。【０１５８】
また、本実施の形態によれば、サンプリングパケット重複判定部５１１は、抽出したパケットのハッシュ値をサンプリングパケット記録データベース５１２に記録するため、記録に要する容量を抑制できる。【０１５９】
また、本実施の形態によれば、サンプリングパケット記録データベース５１２に記録するデータ量が抑制されるため、比較処理の負担が軽減される。【０１６０】
（第８の実施の形態）
次に、本発明の第８の実施の形態について説明する。【０１６１】
前述の第１の実施の形態では、送信済みのパケットが再度到着した場合に送信を行わないため、個々のパケットがそれぞれ一回ずつしか送信されない。これに対し、本実施の形態は、個々のパケットを予め決められた回数だけ送信する点で第１の実施の形態と相違する。【０１６２】
（構成の説明）
図２３は、本実施の形態におけるノード装置の構成を示すブロック図である。【０１６３】
図２３を参照すると、本実施の形態による通過パケット記録データベース１１１は、通過パケット記録データベース１１１に記録されるパケットにカウンタ情報１１１２を付与するカウンタ１１１１を有する。【０１６４】
本実施の形態による通過パケット記録データベース１１１が記憶する情報テーブル１１１ａの構成例を図２４に示す。【０１６５】
カウンタ１１１１は、例えば、パケットがループ防止部１１からパケット送信部３２に送信される際に、パケットの送信回数の所定の閾値と当該パケットのカウンタ情報１１１２を比較し、指定回数以内（所定の閾値以下）場合にカウンタ情報１１１２の値を増やし、指定回数より大きい（所定の閾値より大きい）場合に当該パケットを廃棄する機能を有する。【０１６６】
（動作の説明）
図２５は、本実施の形態によるノード装置１の動作を示すフローチャートである。【０１６７】
通過パケット記録データベース１１１において、パケットの送信回数をパケットを一意に識別するための識別情報との組で記録する（ステップＳ１３０１）。【０１６８】
パケット重複判定部は、受信パケットが送信済みであると判定した時に、通過パケット記録データベース１１１中の送信回数（カウンタ情報１１１２）を参照し、送信回数が予め定められた最大送信回数（所定の閾値）を超えていないとき（ステップＳ１３０２）、カウンタ１１１１によって通過パケット記録データベース１１１中の送信回数の値を一つ増加させ、受信パケットをパケット送信部３２へと送る（ステップＳ１３０３）。【０１６９】
パケット重複判定部は、一方、送信回数が予め定められた最大送信回数（所定の閾値）を超えているとき、受信パケットを廃棄する（ステップＳ１３０４）。【０１７０】
（第８の実施の形態の効果）【０１７１】
本実施の形態によれば、個々のパケットを例えば二回ずつ送信するといったことが実現できる。前述の第１の実施の形態において述べた識別情報としてパケットのペイロードのハッシュ値を用いる方法では、低い確率ではあるものの、異なるパケットであるがペイロードのハッシュ値が一致するケースが起こりえるため、本来送信すべきパケットを送信済みであると誤検出してしまう可能性がある。しかし、本実施の形態による方式を用いることで、下流へと送信するトラフィックの量は多くなるが、誤検出の影響を抑えることができる。【０１７２】
（第９の実施の形態）
（構成の説明）
次に、本発明の第９の実施の形態について図２６を参照して詳細に説明する。【０１７３】
図２６を参照すると、セレクタ６１および流量監視部７１を新たに有する点で第１の実施の形態と異なる。【０１７４】
セレクタ６１は、流量監視部７１からの指示に従い、パケット受信部３１から受け取ったパケットを、流量測定部７１１もしくはパケット重複判定部１１２のいずれかに送る機能を有する。【０１７５】
流量監視部７１は、流量測定部７１１、流量記録部７１２および流量判定部７１３を備える。【０１７６】
流量測定部７１１は、セレクタ６１から送られてきた受信パケットのサイズの累計を記録しておき、単位時間ごとに累計値を流量測定部７１１および流量記録部７１２へと送る機能を有する。前記累計値は、単位時間当たりに受信したパケットサイズの合計であるので、以降トラフィック量と呼ぶことにする。【０１７７】
流量記録部７１２は、流量測定部７１１から送られてきたトラフィック量を送られてきた時刻とともに記録しておく機能を有する。【０１７８】
流量判定部７１３では、流量測定部７１１から送られてきた現在のトラフィック量、および流量記録部７１２に記録されている過去のトラフィック量に基づいてループ発生の有無を判断する機能と、ループが発生している場合にはセレクタ６１に対し、セレクタ６１が以降受信したパケットをパケット重複判定部１１２へと送るよう指示を行う機能とを有する。【０１７９】
前記ループ発生の判定では、具体的には以下のような判断基準を用いる。
条件Ａ：一単位時間前のトラフィック量に比べ、現在のトラフィック量の増分が閾値Ａより大きい。【０１８０】
ループが発生するとトラフィック量は加速度的に増加するため、上記の条件Ａを用いることでループ発生の検出が可能である。しかし、マルチキャストパケットの転送が新規に開始される時も、この条件が当てはまるため、この条件ではループが発生したと誤検出してしまう可能性がある。この誤検出を防ぐためには、以下の条件を合わせて用いてもよい。
条件Ｂ：現在のトラフィック量が閾値Ｂの値を超えている。【０１８１】
また事前に、正常時、ノード装置１をどの程度のトラフィック量が通過するかがわかっている場合には、条件Ｂを用いてもよい。【０１８２】
また流量記録部７１２に記録されている過去のトラフィック量について統計処理を行い、得られた値を用いた条件を使用してもよい。たとえば、過去のトラフィック量の分布が正規分布に従うと仮定したとき、過去のトラフィック量の平均値をｍ、分散をσ２としたとき、
条件Ａ：現在のトラフィック量の値がｍ＋３σよりも大きい。【０１８３】
この条件を満たす場合、３σの法則より現在のトラフィック量が過去の統計値と比べて大きすぎるということを示している。【０１８４】
（動作の説明）
図２７は、本実施の形態によるノード装置１の動作を示すフローチャートである。【０１８５】
セレクタ６１が、流量監視部７１からの指示に従い、パケット受信部３１から受け取ったパケットを流量測定部７１１に送る（ステップＳ１４０１）。【０１８６】
流量測定部７１１が、セレクタ６１から送られてきた受信パケットのサイズの累計を記録しておき、単位時間ごとに累計値（トラフィック量）を流量測定部７１１および流量記録部７１２へと送る（ステップＳ１４０２）。【０１８７】
流量記録部７１２が、流量測定部７１１から送られてきたトラフィック量を、送られてきた時刻とともに記録する（ステップＳ１４０３）。【０１８８】
流量判定部７１３が、流量測定部７１１から送られてきた現在のトラフィック量、および流量記録部７１２に記録されている過去のトラフィック量に基づいてループ発生の有無を判断し（ステップＳ１４０４）、ループが発生している場合にはセレクタ６１に対し、セレクタ６１が以降受信したパケットをパケット重複判定部１１２へと送るよう指示を行う（ステップＳ１４０５）。【０１８９】
セレクタ６１は、流量判定部７１３からの指示に基づいて、パケット受信部３１から受け取ったパケットの送信先をパケット重複判定部１１２に切り替える（ステップＳ１４０６）。【０１９０】
パケット重複判定部１１２が、サンプリングパケット重複判定部５１１によるループ検出後に、セレクタ６１からの全ての受信パケットに対して、すでに送信済みであるか否かの判定を行い（ステップＳ１４０７）、まだ送信を行っていないパケットをパケット送信部３２に送り、所定の時間、パケット重複を検出しない場合、パケット受信部３１から受け取ったパケットをパケット重複判定部１１２に送るセレクタ６１に対し、セレクタ６１が以降受信したパケットをサンプリングパケット重複判定部５１１へと送るよう指示を出し（ステップＳ１４０８）、一方、送信済みのパケットを廃棄する（ステップＳ１４０９）。【０１９１】
なお、ステップＳ１４０４においてループが発生していない場合、流量複判定部５１３は、現在のトラフィック量を流量記録部７１２に記録し、当該パケットをパケット送信部３２に送る（ステップＳ１４１０）。【０１９２】
なお、本実施の形態は、例えば、前述の上記第２、第３、第８の実施の形態等と組み合わせることも可能である。【０１９３】
（第９の実施の形態の効果）【０１９４】
本実施の形態では、第４の実施の形態と同様にループの検出と、ループ経路により再到着するパケットの再送信の抑制とを別々に行うことにより、ループ未発生時の処理負荷の抑制を実現している。【０１９５】
（第１０の実施の形態）
本発明の第１０の実施の形態は、通常は第１の実施の形態における処理を行い、ループを検出した場合に第２の実施の形態における処理を行うものである。すなわち、本実施の形態は、第２の実施の形態のように、常時、フロー毎にパケットの重複判定処理を行うことは処理負担が大きいため、通常は第１の実施の形態のようにフローとは無関係にパケットの重複判定処理を行い、当該重複判定処理においてループを暫定的に検出した場合に、第２の実施の形態のようにフロー単位でパケットの重複判定処理を行うものである。【０１９６】
以上好ましい実施の形態（及び実施例）を参照して本願発明を説明したが、本願発明は上記実施の形態（及び実施例）に限定されるものでない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。【０１９７】
この出願は、２００７年５月２９日に出願された日本出願特願２００７−１４１６２４を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【産業上の利用可能性】
【０１９８】
主に、映像配信等に用いられるＩＰマルチキャストの転送を行うためのルータ装置、スイッチ装置への実装が考えられる。その他パケット転送を行う種々の装置への適用が可能である。
【図１】
2008146730.tif 000003
【図２】
2008146730.tif 000004
【図３】
2008146730.tif 000005
【図４】
2008146730.tif 000006
【図５】
2008146730.tif 000007
【図６】
2008146730.tif 000008
【図７】
2008146730.tif 000009
【図８】
2008146730.tif 000010
【図９】
2008146730.tif 000011
【図１０】
2008146730.tif 000012
【図１１】
2008146730.tif 000013
【図１２】
2008146730.tif 000014
【図１３】
2008146730.tif 000015
【図１４】
2008146730.tif 000016
【図１５】
2008146730.tif 000017
【図１６】
2008146730.tif 000018
【図１７】
2008146730.tif 000019
【図１８】
2008146730.tif 000020
【図１９】
2008146730.tif 000021
【図２０】
2008146730.tif 000022
【図２１】
2008146730.tif 000023
【図２２】
2008146730.tif 000024
【図２３】
2008146730.tif 000025
【図２４】
2008146730.tif 000026
【図２５】
2008146730.tif 000027
【図２６】
2008146730.tif 000028
【図２７】
2008146730.tif 000029
【図２８】
2008146730.tif 000030
【図２９】
2008146730.tif 000031
【手続補正書】
【提出日】平成21年3月30日(2009.3.30)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ネットワークと接続するネットワークインターフェイスと、
ネットワークからパケットを受信するパケット受信部と、
ネットワークに対してパケットを送信するパケット送信部とを持つノード装置であって、
送信済みのパケットに関するパケットを識別するための識別情報を記録するための通過パケット記録データベースと、
通過パケット記録データベースを参照し、未送信の前記受信パケットをパケット送信部へと送るパケット重複判定部と、
前記通過パケット記録データベース上に記録されている送信済みのパケットに関するパケットを識別するための識別情報を、そのパケットの受信時刻又は送信時刻からあらかじめ定められたタイムアウト時間経過後に、削除するデータベースメンテナンス部を有することを特徴とするノード装置。
【請求項２】
前記パケット重複判定部において、受信したパケットがすでに送信済みであったと判断されたときに、受信パケットの受信時刻又は送信時刻と、
通過パケット記録データベース中の該当するパケットの受信時刻又は送信時刻との時間差を用いて前記タイムアウト時間を決めるタイムアウト値決定部を有することを特徴とする請求項１に記載のノード装置。
【請求項３】
前記パケット重複判定部は、
前記通過パケット記録データベースを参照し、受信したパケットが送信済みかどうかを判定し、送信済みでない場合、受信パケットをパケット送信部へと送ることを特徴とする請求項１又は請求項２に記載のノード装置。
【請求項４】
前記パケット重複判定部は、
受信したパケットの受信時刻を、当該パケットの送信前又は送信後に記録することを特徴とする請求項１から請求項３の何れかに記載のノード装置。
【請求項５】
前記パケット重複判定部は、
受信したパケットの送信時刻を、当該パケットの送信の際に記録することを特徴とする請求項１から請求項３の何れかに記載のノード装置。
【請求項６】
前記通過パケット記録データベースにおいて、
送信済みパケットの識別情報をフロー毎に区別して記録を行い、
前記パケット重複判定部において、
受信したパケットがどのフローに属するかを識別し、前記通過パケット記録データベース中の同一のフローに属する識別情報に基づき当該受信したパケットが送信済みかの判定を行うことを特徴とする請求項１から請求項５のいずれか１項に記載のノード装置。
【請求項７】
前記パケットを識別するための識別情報として、パケットのペイロードを用いることを特徴とする請求項１から請求項６のいずれか１項に記載のノード装置。
【請求項８】
前記パケットを識別するための識別情報として、パケットのペイロードのハッシュ値を用いることを特徴とする請求項１から請求項６のいずれか１項に記載のノード装置。
【請求項９】
前記パケットを識別するための識別情報として、ＲＴＰヘッダ中のシーケンス番号を用いることを特徴とする請求項１から請求項６のいずれか１項に記載のノード装置。
【請求項１０】
前記パケットを識別するための識別情報として、ＩＰヘッダ中の識別子およびフラグメントオフセットの組を用いることを特徴とする請求項１から請求項６のいずれか１項に記載のノード装置。
【請求項１１】
前記通過パケット記録データベースは、
送信済みのパケットに関するパケットを識別するための識別情報として、当該パケットのペイロードのハッシュ値やペイロードの一部分を記録し、
前記パケット重複判定部は、
前記識別情報として受信したパケットのペイロードのハッシュ値やペイロードの一部分を用い、前記通過パケット記録データベースを参照し、受信したパケットが送信済みかどうかを判定し、送信済みの場合に、前記識別情報として前記受信したパケットのペイロード全体を用い、受信したパケットが送信済みかどうかを判定することを特徴とする請求項１から請求項６のいずれか１項に記載のノード装置。
【請求項１２】
（削除）
【請求項１３】
前記タイムアウト値決定部において、前記時間差の統計情報を用いてタイムアウト時間を決めることを特徴とする請求項２に記載のノード装置。
【請求項１４】
前記タイムアウト値決定部は、
タイムアウト時間に上限値を設け、現在のタイムアウト時間と前記時間差の比較を行い、前記時間差の方が小さい場合に前記時間差を用いて新たなタイムアウト時間を決定することを特徴とする請求項１から請求項１１又は請求項１３のいずれか１項に記載のノード装置。
【請求項１５】
前記タイムアウト値決定部は、
タイムアウト時間に下限値を設け、現在のタイムアウト時間と前記時間差の比較を行い、前記時間差の方が大きい場合に前記時間差を用いて新たなタイムアウト時間を決定することを特徴とする請求項１から請求項１１又は請求項１３のいずれか１項に記載のノード装置。
【請求項１６】
前記通過パケット記録データベース上に記録されている送信済みのパケットに関する識別情報の数が予め定められている最大値を超えたときに、通過パケット記録データベース上から、最大数を超過した数の識別情報を受信時刻又は送信時刻が古い順に削除するデータベースメンテナンス部を有することを特徴とする請求項１に記載のノード装置。
【請求項１７】
前記通過パケット記録データベースにおいて、パケットの送信回数をパケットを識別するための識別情報との組で記録し、前記パケット重複判定部において、受信パケットが送信済みであると判定されたときに、前記通過パケット記録データベース中の送信回数を参照し、送信回数が予め定められた最大送信回数超えていないとき、前記通過パケット記録データベース中の送信回数の値を一つ増加させ、パケット送信部へと送ることを特徴とする請求項１から請求項１１又は請求項１３から請求項１６のいずれか１項に記載のノード装置。
【請求項１８】
ネットワークと接続するネットワークインターフェイスと、
ネットワークからパケットを受信するパケット受信部と、
ネットワークに対してパケットを送信するパケット送信部とを持つノード装置であって、
送信済みのパケットに関するパケットを識別するための識別情報を記録するための通過パケット記録データベースと、
通過パケット記録データベースを参照し、未送信の前記受信パケットをパケット送信部へと送るパケット重複判定部と、
あらかじめ定められたパケットを識別する識別情報に基づき、受信したパケットの識別情報が前記識別情報に一致するときに、サンプリングパケット記録データベースを参照し、受信したパケットが送信済みかどうかを判定するサンプリングパケット重複判定部と、
前記サンプリングパケット重複判定部により送信済みかどうかの判定が行われ、送信済みではないと判定された受信パケットを記録するサンプリングパケット記録データベースと、
パケット受信部から送られてきたパケットを前記サンプリングパケット重複判定部に送り、前記サンプリングパケット重複判定部において、受信したパケットが送信済みであると判定されたとき、以降受信パケットをパケット重複判定部へと送るセレクタとを有することを特徴とするノード装置。
【請求項１９】
前記パケット重複判定部は、
所定の時間、受信したパケットが未送信であると判定した場合、又は、判定したパケット数が所定の回数に達した場合、前記セレクタに対し、前記セレクタが以降受信したパケットをサンプリングパケット重複判定部へと送るよう指示を出すことを特徴とする請求項１８に記載のノード装置。
【請求項２０】
前記通過パケット記録データベースは、
送信済みのパケットに関するパケットを識別するための識別情報として、当該パケットの一部又は全部のハッシュ値を記録し、
前記パケット重複判定部は、
前記識別情報として受信したパケットの一部又は全部のハッシュ値を用い、前記通過パケット記録データベースを参照し、受信したパケットが送信済みかどうかを判定し、
送信済みの場合に、以降受信パケットをサンプリングパケット重複判定部へと送るセレクタと、
あらかじめ定められたパケットを識別する識別情報に基づき、受信したパケットの識別情報が前記識別情報に一致するときに、サンプリングパケット記録データベースを参照し、受信したパケットが送信済みかどうかを判定するサンプリングパケット重複判定部と、
前記サンプリングパケット重複判定部により送信済みかどうかの判定が行われ、送信済みではないと判定された受信パケットの一部又は全部のハッシュ値を記録するサンプリングパケット記録データベースとを有することを特徴とする請求項１８に記載のノード装置。
【請求項２１】
前記サンプリングパケット重複判定部は、
所定の時間、受信したパケットが未送信あると判定した場合、又は、判定したパケット数が所定の回数に達した場合、前記セレクタに対し、前記セレクタが以降受信したパケットを前記パケット重複判定部へと送るよう指示を出すことを特徴とする請求項２０に記載のノード装置。
【請求項２２】
受信したパケットのパケットサイズを測定することにより、単位時間当たりのトラフィック量を測定する流量測定部と、
前記流量測定部により測定された単位時間当たりのトラフィック量を用いてループ発生の判定を行う流量判定部と、
パケット受信部から送られてきたパケットを前記流量測定部に送り、前記流量判定部において、ループが発生していると判定されたとき、以降受信パケットをパケット重複判定部へと送るセレクタとを有することを特徴とする請求項１から請求項１１又は請求項１３から請求項１７のいずれか１項に記載のノード装置。
【請求項２３】
前記流量判定部において、単位時間当たりのトラフィック量が予め定められた閾値を超えている場合にループが発生していると判定することを特徴とする請求項２２に記載のノード装置。
【請求項２４】
前記ノード装置において、
過去のトラフィック量の記録を行う流量記録部を有し、
前記流量判定部において、
流量記録部を参照しトラフィック量の増加が閾値を超えているかの判定を行い、
前記セレクタにおいて、
前記トラフィック量の増加が閾値を超えたと判定されたとき、以降受信パケットをパケット重複判定部へと送ることを特徴とする請求項２２又は請求項２３に記載のノード装置。
【請求項２５】
前記流量判定部において、前記流量記録部中に記録されている過去のトラフィック量の統計処理を行い、求められた統計値を用いてループ発生の判定を行うことを特徴とする請求項２４に記載のノード装置。
【請求項２６】
パケットの受信を行い、パケットのヘッダ情報に基づき、パケットの転送を行うパケット転送方法であって、
送信済みのパケットに関するパケットを識別するための識別情報を記録するステップと、
前記記録済みの識別情報を参照し、未送信の前記受信パケットを送信対象とするステップと、
前記記録されている送信済みのパケットに関するパケットを識別するための識別情報を、そのパケットの受信時刻又は送信時刻からあらかじめ定められたタイムアウト時間経過後に、削除するステップを持つことを特徴とするパケット転送方法。
【請求項２７】
前記受信パケットが送信済みであるかを判定するステップにおいて、
受信したパケットがすでに送信済みであったと判断されたときに、受信パケットの受信時刻又は送信時刻と、該当するパケットの受信時刻又は送信時刻との時間差を用いて前記タイムアウト時間を決めるステップを有することを特徴とする請求項２６に記載のパケット転送方法。
【請求項２８】
未送信の前記受信パケットを送信対象とする前記ステップにおいて、
前記通過パケット記録データベースを参照し、受信したパケットが送信済みかどうかを判定し、送信済みでない場合、受信パケットを送信対象とすることを特徴とする請求項２６又は請求項２７に記載のパケット転送方法。
【請求項２９】
未送信の前記受信パケットを送信対象とする前記ステップにおいて、
受信したパケットの受信時刻を、当該パケットの送信前又は送信後に記録することを特徴とする請求項２６から請求項２８の何れかに記載のパケット転送方法。
【請求項３０】
未送信の前記受信パケットを送信対象とする前記ステップにおいて、
受信したパケットの送信時刻を、当該パケットの送信の際に記録することを特徴とする請求項２６から請求項２８の何れかに記載のパケット転送方法。
【請求項３１】
前記送信済みパケットの識別情報を記録するステップにおいて、
送信済みパケットの識別情報をフロー毎に区別して記録を行い、
前記受信パケットが送信済みであるかを判定するステップにおいて、
受信したパケットがどのフローに属するかを識別し、同一のフローに属する識別情報に基づき当該受信したパケットが送信済みかの判定を行うことを特徴とする請求項２６から請求項３０のいずれか１項に記載のパケット転送方法。
【請求項３２】
前記パケットを識別するための識別情報として、パケットのペイロードを用いることを特徴とする請求項２６から請求項３１のいずれか１項に記載のパケット転送方法。
【請求項３３】
前記パケットを識別するための識別情報として、パケットのペイロードのハッシュ値を用いることを特徴とする請求項２６から請求項３１のいずれか１項に記載のパケット転送方法。
【請求項３４】
前記パケットを識別するための識別情報として、ＲＴＰヘッダ中のシーケンス番号を用いることを特徴とする請求項２６から請求項３１のいずれか１項に記載のパケット転送方法。
【請求項３５】
前記パケットを識別するための識別情報として、ＩＰヘッダ中の識別子およびフラグメントオフセットの組を用いることを請求項２６から請求項３１のいずれか１項に記載のパケット転送方法。
【請求項３６】
送信済みのパケットに関するパケットを識別するための識別情報として、当該パケットのペイロードのハッシュ値やペイロードの一部分を記録するステップを有し、
送信済みでない場合に受信パケットを送信対象とする前記ステップにおいて、
前記識別情報として受信したパケットのペイロードのハッシュ値やペイロードの一部分を用い、前記記録済みの識別情報を参照し、受信したパケットが送信済みかどうかを判定し、送信済みの場合に、前記識別情報として前記受信したパケットのペイロード全体を用い、受信したパケットが送信済みかどうかを判定することを特徴とする請求項２６から請求項３５のいずれか１項に記載のパケット転送方法。
【請求項３７】
（削除）
【請求項３８】
前記タイムアウト時間を決定するステップにおいて、
前記時間差の統計情報を用いてタイムアウト時間を決めることを特徴とする請求項２７に記載のパケット転送方法。
【請求項３９】
タイムアウト時間に上限値を設け、現在のタイムアウト時間と前記時間差の比較を行い、前記時間差の方が小さい場合に前記時間差を用いて新たなタイムアウト時間を決定することを特徴とする請求項２６から請求項３６又は請求項３８のいずれか１項に記載のパケット転送方法。
【請求項４０】
タイムアウト時間に下限値を設け、現在のタイムアウト時間と前記時間差の比較を行い、前記時間差の方が大きい場合に前記時間差を用いて新たなタイムアウト時間を決定することを特徴とする請求項２６から請求項３６又は請求項３８のいずれか１項に記載のパケット転送方法。
【請求項４１】
前記記録されている送信済みのパケットに関する識別情報の数が予め定められている最大値を超えたときに、最大数を超過した数の識別情報を受信時刻又は送信時刻が古い順に削除するステップを有することを特徴とする請求項３８に記載のパケット転送方法。
【請求項４２】
前記送信済みパケットの識別情報を記録するステップにおいて、
パケットの送信回数をパケットを識別するための識別情報との組で記録し、
前記受信パケットが送信済みであるかを判定するステップにおいて、
受信パケットが送信済みであると判定されたときに、前記記録済みの識別情報との組で記録されている送信回数を参照し、送信回数が予め定められた最大送信回数超えていないとき、前記送信回数の値を一つ増加させ、パケットを送信対象とすることを特徴とする請求項２６から請求項３６又は請求項３８から請求項４１のいずれか１項に記載のパケット転送方法。
【請求項４３】
パケットの受信を行い、パケットのヘッダ情報に基づき、パケットの転送を行うパケット転送方法であって、
送信済みのパケットに関するパケットを識別するための識別情報を記録するステップと、
前記記録済みの識別情報を参照し、未送信の前記受信パケットを送信対象とするステップと、
あらかじめ定められたパケットを識別する識別情報に基づき、受信したパケットの識別情報が前記識別情報に一致するときに、サンプリングパケット記録データベースを参照し、受信したパケットが送信済みかどうかを調べることによりループ発生の検出を行うステップと、
前記ステップにより送信済みかどうかの判定が行われ、送信済みではないと判定された受信パケットをサンプリングパケット記録データベースに記録するステップと、
パケットの受信時に、前記ステップでループ発生の検出がなされていないときには前記サンプリングパケット記録データベースを用いたループ判定を行い、また、前記ステップでループ発生が検出されているときには、前記全受信パケットが送信済みであるかの判定を行うステップを有することを特徴とするパケット転送方法。
【請求項４４】
前記全受信パケットが送信済みであるかの判定を行うステップにおいて、
所定の時間、受信したパケットが未送信であると判定した場合、又は、判定したパケット数が所定の回数に達した場合、サンプリングパケット記録データベースを参照し、
受信したパケットが送信済みかどうかを調べることによりループ発生の検出を行うステップに戻ることを特徴とする請求項４３に記載のパケット転送方法。
【請求項４５】
送信済みのパケットに関するパケットを識別するための識別情報として、当該パケットの一部又は全部のハッシュ値を記録するステップを有し、
送信済みでない場合に受信パケットを送信対象とする前記ステップにおいて、
前記識別情報として受信したパケットの一部又は全部のハッシュ値を用い、前記記録済みの識別情報を参照し、受信したパケットが送信済みかどうかを判定し、
送信済みの場合に、あらかじめ定められたパケットを識別する識別情報に基づき、受信したパケットの識別情報が前記識別情報に一致するときに、前記サンプリングパケット記録データベースを参照し、受信したパケットが送信済みかどうかを判定するステップと、
前記サンプリングパケット記録データベースを参照し、受信したパケットが送信済みかどうかを判定する前記ステップにより送信済みかどうかの判定が行われ、送信済みではないと判定された受信パケットの一部又は全部のハッシュ値をサンプリングパケット記録データベース記録するステップとを有することを特徴とする請求項４３に記載のパケット転送方法。
【請求項４６】
前記サンプリングパケット記録データベースを参照し、受信したパケットが送信済みかどうかを判定する前記ステップにおいて、
所定の時間、受信したパケットが未送信あると判定した場合、又は、判定したパケット数が所定の回数に達した場合、送信済みでない場合に受信パケットを送信対象とする前記ステップに戻ることを特徴とする請求項４５に記載のパケット転送方法。
【請求項４７】
受信したパケットのパケットサイズを測定することにより、単位時間当たりのトラフィック量を測定するステップと、
前記ステップにより測定された単位時間当たりのトラフィック量を用いてループ発生の判定を行うステップと、
パケットの受信時に、前記ステップでループ発生の検出がなされていないときには前記トラフィック量を用いたループ判定を行い、また、前記ステップでループ発生が検出されているときには、前記全受信パケットが送信済みであるかの判定を行うステップを有することを特徴とする請求項２６から請求項３６又は請求項３８から請求項４６のいずれか１項に記載のパケット転送方法。
【請求項４８】
前記トラフィック量を用いてループ判定を行うステップにおいて、
単位時間当たりのトラフィック量が予め定められた閾値を超えている場合にループが発生していると判定することを特徴とする請求項４７に記載のパケット転送方法。
【請求項４９】
前記パケット転送方式において、
過去のトラフィック量の記録を行うステップを有し、
前記トラフィック量を用いてループ判定を行うステップにおいて、
記録されている過去トラフィック量を参照しトラフィック量の増加が閾値を超えているかを調べることでループ発生の判定を行うことを特徴とする請求項４７又は請求項４８に記載のパケット転送方法。
【請求項５０】
前記トラフィック量を用いてループ判定を行うステップにおいて、
前記記録されている過去のトラフィック量の統計処理を行い、求められた統計値を用いてループ発生の判定を行うことを特徴とする請求項４９に記載のパケット転送方法。
【請求項５１】
ネットワークと接続するネットワークインターフェイスと、
ネットワークからパケットを受信するパケット受信部と、
ネットワークに対してパケットを送信するパケット送信部とを持つノード装置上で実行されるパケット転送プログラムであって、
前記ノード装置に、
送信済みのパケットに関するパケットを識別するための識別情報を記録するための通過パケット記録データベースを参照し、未送信の前記受信パケットをパケット送信部へと送るパケット重複判定処理と、
前記通過パケット記録データベース上に記録されている送信済みのパケットに関するパケットを識別するための識別情報を、そのパケットの受信時刻又は送信時刻からあらかじめ定められたタイムアウト時間経過後に、削除するデータベースメンテナンス処理
を実行させることを特徴とするパケット転送プログラム。
【請求項５２】
前記パケット記録データベースにおいて、送信済みのパケットに関するパケットを識別するための識別情報を、パケットの送信時刻または受信時刻の順に記録することを特徴とする請求項１から請求項５の何れかに記載のノード装置。
【請求項５３】
前記データベースメンテナンス部において、記通過パケット記録データベース上に記録されている送信済みのパケットに関するパケットを識別するための識別情報を、削除する際に先頭から順に削除することを特徴とする請求項５２に記載のノード装置。
【国際調査報告】
2008146730.tif 000032
2008146730.tif 000033
2008146730.tif 000034
2008146730.tif 000035