(57)【要約】【課題】  明示的マルチキャスト方式におけるパケット中継処理の負荷低減及び高速化を実現する。【解決手段】  パケット解析部１０５は、フロー固有情報取得部１０５１においてパケットを解析し、同一のフローならば同一の値となるフロー固有情報を取得する。フロー固有情報に対応する中継処理情報がキャッシュメモリ１０９に格納されている場合には、その中継処理情報を用いてパケットの中継処理を行う。対応する中継処理情報が格納されていない場合には、経路表探索部１０６により未配送の受信者アドレスに対してユニキャスト経路表を探索して送出インタフェース情報を決定し、必要に応じてパケットの複製を行い、ヘッダ情報の変更を行って、パケットを中継処理する。そして、送出インタフェース情報と、ＩＰヘッダ及び明示的マルチキャスト方式における制御情報を含むヘッダ情報の変更処理結果とを、中継処理情報としてキャッシュメモリ１０９に書き込む。【選択図】  図１
2006191468.tif 000002
【特許請求の範囲】
【請求項１】
送信者がパケット中に複数の受信者のアドレスを記述することで、前記パケットの受信者を明確に指定する明示的マルチキャスト方式のパケットを中継するパケット中継方法であって、
前記パケットを解析し、同一のフローならば同一の値となるフロー固有情報を取得するステップと、
前記取得したフロー固有情報に対応する中継処理情報に基づいて前記パケットの中継処理を行うステップと、
を有するパケット中継方法。
【請求項２】
請求項１に記載のパケット中継方法であって、
前記取得したフロー固有情報に対応する中継処理情報が記憶手段に保持されているか否かを判定するステップと、
前記フロー固有情報に対応する中継処理情報が保持されている場合に、この中継処理情報を用いて前記パケットの中継処理を行うステップと、
を有するパケット中継方法。
【請求項３】
請求項２に記載のパケット中継方法であって、
前記パケットの中継処理を行うステップにおいて、前記中継処理情報から送出インタフェース情報を取得し、必要に応じて前記パケットの複製処理及び前記パケットのヘッダ情報の変更処理を行い、この処理後のパケットを前記送出インタフェース情報に従って出力するパケット中継方法。
【請求項４】
請求項２または３に記載のパケット中継方法であって、
前記フロー固有情報に対応する中継処理情報が保持されていない場合に、未配送の受信者アドレスに対してユニキャスト経路表の検索を行い、その検索結果に基づいて送出インタフェース情報を決定するステップと、
必要に応じて前記パケットの複製処理及び前記パケットのヘッダ情報の変更処理を行い、この処理後のパケットを前記送出インタフェース情報に従って出力するステップと、
を有するパケット中継方法。
【請求項５】
請求項４に記載のパケット中継方法であって、更に、
少なくとも前記送出インタフェース情報を含む中継処理情報を、前記フロー固有情報との対応を付けて記憶手段に記憶するステップを有するパケット中継方法。
【請求項６】
請求項５に記載のパケット中継方法であって、
前記中継処理情報は、更に、前記パケットのヘッダ情報の変更処理結果の情報を含むパケット中継方法。
【請求項７】
請求項１に記載のパケット中継方法であって、
前記取得したフロー固有情報をハッシュ関数に入力してこのフロー固有情報に対応したハッシュ値を取得するステップと、
前記ハッシュ値に対応する中継処理情報が記憶手段に保持されているか否かを判定するステップと、
前記ハッシュ値に対応する中継処理情報が保持されている場合に、この中継処理情報を用いて前記パケットの中継処理を行うステップと、
を有するパケット中継方法。
【請求項８】
請求項７に記載のパケット中継方法であって、
前記パケットの中継処理を行うステップにおいて、前記中継処理情報から送出インタフェース情報を取得し、必要に応じて前記パケットの複製処理及び前記パケットのヘッダ情報の変更処理を行い、この処理後のパケットを前記送出インタフェース情報に従って出力するパケット中継方法。
【請求項９】
請求項７または８に記載のパケット中継方法であって、
前記ハッシュ値に対応する中継処理情報が保持されていない場合に、未配送の受信者アドレスに対してユニキャスト経路表の検索を行い、その検索結果に基づいて送出インタフェース情報を決定するステップと、
必要に応じて前記パケットの複製処理及び前記パケットのヘッダ情報の変更処理を行い、この処理後のパケットを前記送出インタフェース情報に従って出力するステップと、
を有するパケット中継方法。
【請求項１０】
請求項９に記載のパケット中継方法であって、更に、
少なくとも前記送出インタフェース情報を含む中継処理情報を、前記ハッシュ値との対応を付けて記憶手段に記憶するステップを有するパケット中継方法。
【請求項１１】
請求項９に記載のパケット中継方法であって、更に、
少なくとも前記送出インタフェース情報を含む中継処理情報を、前記ハッシュ値及び前記フロー固有情報との対応を付けて記憶手段に記憶するステップを有するパケット中継方法。
【請求項１２】
請求項１０または１１に記載のパケット中継方法であって、
前記中継処理情報は、更に、前記パケットのヘッダ情報の変更処理結果の情報を含むパケット中継方法。
【請求項１３】
請求項２から１２のいずれかに記載のパケット中継方法であって、
前記中継処理情報に対して有効時間が設定されている場合、
前記有効時間に基づき、前記中継処理情報が記憶手段に記憶されてからの経過時間、または前記中継処理情報が最後に参照されてからの経過時間が所定時間経過したときに、該当する中継処理情報を前記記憶手段から消去するステップを有するパケット中継方法。
【請求項１４】
請求項２から１２のいずれかに記載のパケット中継方法であって、
ユニキャスト経路表の変更があった場合に、前記中継処理情報を前記記憶手段から消去するステップを有するパケット中継方法。
【請求項１５】
送信者がパケット中に複数の受信者のアドレスを記述することで、前記パケットの受信者を明確に指定する明示的マルチキャスト方式のパケットを中継するパケット中継装置であって、
前記パケットを解析し、同一のフローならば同一の値となるフロー固有情報を取得するフロー固有情報取得手段と、
前記取得したフロー固有情報に対応する中継処理情報に基づいて前記パケットの中継処理を行う中継処理手段と、
を備えるパケット中継装置。
【請求項１６】
請求項１５に記載のパケット中継装置であって、
前記フロー固有情報に対応する中継処理情報を記憶する記憶手段と、
前記取得したフロー固有情報に対応する中継処理情報が前記記憶手段に保持されているか否かを判定する中継処理情報判定手段とを備え、
前記中継処理手段は、前記フロー固有情報に対応する中継処理情報が保持されている場合に、この中継処理情報を用いて前記パケットの中継処理を行うパケット中継装置。
【請求項１７】
請求項１５に記載のパケット中継装置であって、
前記取得したフロー固有情報をハッシュ関数に入力してこのフロー固有情報に対応したハッシュ値を取得するハッシュ値取得手段と、
前記ハッシュ値に対応する中継処理情報を記憶する記憶手段と、
前記ハッシュ値に対応する中継処理情報が記憶手段に保持されているか否かを判定する中継処理情報判定手段とを備え、
前記中継処理手段は、前記ハッシュ値に対応する中継処理情報が保持されている場合に、この中継処理情報を用いて前記パケットの中継処理を行うパケット中継装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パケットに複数の受信者の配信先を記述して配信を行う明示的マルチキャスト方式のパケット中継方法及びパケット中継装置に関する。
【背景技術】
【０００２】
明示的マルチキャスト方式のパケット中継は、一つの送信者から複数の受信者に対して通信データを含むパケットを配送するマルチキャスト通信において、パケットのオプションヘッダまたはペイロードに配信先である複数の受信者アドレス（各受信者の宛先を示すアドレス）を記述することにより、パケットを受信できるノードを送信者が明示的に指定するパケット中継方法である。明示的マルチキャスト方式における送信者は、例えば、パケットのＩＰヘッダより後ろのオプションヘッダやペイロードに、全受信者のアドレスを記述して送出する。なお、本明細書では、明示的マルチキャスト方式におけるパケットを単にパケットと記載する。
【０００３】
ここで、従来のパケット中継方法について、２つの例を示す。
（第１の従来パケット中継処理方法）
明示的マルチキャスト方式をサポートするパケット中継装置（以降、ルータと記載する）は、パケットが到着すると、パケット中の受信者アドレス毎に自己のユニキャスト経路表を検索する。そして、各受信者アドレスに対して送出インタフェースが異なる場合、ルータはそれら送出インタフェース分のパケットを複製して、それぞれ対応する送出インタフェースにパケットを出力する。このとき、ルータは、送出インタフェースから送出される各パケットに対して、ユニキャスト経路表検索の結果から送出インタフェースが同一となる受信者アドレス以外の受信者のアドレスは配送済みとみなして、配送済みのマーキングを付与するか、パケット中から削除する。
【０００４】
このとき、明示的マルチキャスト方式によっては、ルータにおいて送出しようとするパケットのＩＰヘッダの宛先アドレスが、配送済みとなった受信者のアドレスである場合がある。この場合、ルータは、配送済みとみなされた受信者アドレス以外の受信者（以降、未配送の受信者と記載）のアドレスから一つを選択し、ＩＰヘッダの宛先アドレスとして書き換える。このようにルータでは、パケット中継処理として未配送の受信者アドレスに対して前記の一連の処理を繰り返すことで、パケット配送におけるループ発生や重複配送を防止する。
【０００５】
以上の仕組みにより、明示的マルチキャスト方式では、送信者が指定した全受信者に対してパケットをマルチキャストすることができる。なお、本明細書では前述したパケット中継処理方法を第１の従来パケット中継処理方法と呼ぶことにする。また、代表的な明示的マルチキャスト方式としては、特許文献１や非特許文献１に記載のExplicit Multicast（ＸＣＡＳＴ）方式がある。
【０００６】
しかし、第１の従来パケット中継処理方法では、到着するパケット毎の未配送の受信者アドレスに対して、ユニキャスト経路表の検索処理を行うため、オーバヘッドが大きくなり、パケット中継処理の負荷が高く、また高速化が図れないという課題がある。
【０００７】
（第２の従来パケット中継処理方法）
前記第１の従来パケット中継処理方法における課題に対して、特許文献２や非特許文献２記載のパケット中継処理方法が提案されている。このパケット中継処理方法では、パケットの送信者がその送信者においてユニークとなる識別子を生成し、パケットに識別子を記述して送信する。次に、ルータにパケットが到着すると、第１の従来パケット中継処理方法に加えて、送信者の送信元アドレス及びパケットに記述された識別子及びパケットに対するユニキャスト経路表の検索結果を自身（ルータ）のキャッシュメモリに記録する。そして、それ以降前記パケットと同一フローとなるパケットが到着すると、キャッシュメモリ内のユニキャスト経路表の検索結果を利用することで、第１の従来パケット中継処理方法と比較して、パケット中継処理に対するオーバヘッドを削減する。なお、本明細書では前述した特許文献２や非特許文献２に記載のパケット中継処理方法を第２の従来パケット中継処理方法と呼ぶことにする。
【０００８】
しかし、第２の従来パケット中継処理方法では、送信者はその送信者においてユニークとなる識別子をパケットに記述することが必要となり、識別子が記述されていないパケットには第２の従来パケット中継処理方法を適用できない。また、代表的な明示的マルチキャスト方式であるＸＣＡＳＴ方式の基本仕様には、チャンネル識別子としてオプションヘッダ中に識別子を記述する領域が用意されているが、送信者におけるパケット送信の際の識別子の記述は任意であり、識別子を記述しない場合は０が指定される。従って、第２の従来パケット中継処理方法の適用範囲は限定的であり、識別子が付与されないパケットに対するパケット中継処理の高速化はできず、識別子が付与されないパケットが大量に到着した場合、パケット中継処理の処理負荷が増大するという課題がある。
【０００９】
【特許文献１】特開２０００−３５４０６３号公報
【特許文献２】特開２００１−３６５８３号公報
【非特許文献１】Internet-Draft (draft-ooms-xcast-basic-spec-05.txt)
【非特許文献２】Internet-Draft (draft-ooms-cl-multicast-02.txt)
【発明の開示】
【発明が解決しようとする課題】
【００１０】
本発明は、上記事情に鑑みてなされたもので、パケット中継処理時のオーバヘッドを削減でき、また、パケットに識別子が付与されていない場合であっても、パケット中継処理の負荷低減及び高速化を実現することが可能なパケット中継方法及びパケット中継装置を提供することを目的とする。
【課題を解決するための手段】
【００１１】
本発明は、第１に、送信者がパケット中に複数の受信者のアドレスを記述することで、前記パケットの受信者を明確に指定する明示的マルチキャスト方式のパケットを中継するパケット中継方法であって、前記パケットを解析し、同一のフローならば同一の値となるフロー固有情報を取得するステップと、前記取得したフロー固有情報に対応する中継処理情報に基づいて前記パケットの中継処理を行うステップと、を有するものである。
【００１２】
これにより、パケットのフロー固有情報と前記フロー固有情報に対応する中継処理情報に基づいてパケットの中継処理を行うことにより、パケットに識別子が付与されていない場合であっても、一度中継されたパケットと同一フローであれば、それ以降到着するパケットに対するユニキャスト経路表の検索処理を省略してパケットを中継することができる。このため、パケット中継処理におけるオーバヘッドを削減し、パケット中継処理を高速に行うことができる。
【００１３】
また、本発明は、第２に、上記第１のパケット中継方法であって、前記取得したフロー固有情報に対応する中継処理情報が記憶手段に保持されているか否かを判定するステップと、前記フロー固有情報に対応する中継処理情報が保持されている場合に、この中継処理情報を用いて前記パケットの中継処理を行うステップと、を有するものである。
【００１４】
これにより、パケットのフロー固有情報を取得し、フロー固有情報に対応する中継処理情報が保持されている場合に、この中継処理情報を用いて前記パケットの中継処理を行うことによって、パケットに識別子が付与されていない場合であっても、一度中継されたパケットと同一フローであれば、それ以降到着するパケットに対するユニキャスト経路表の検索処理を省略してパケットを中継することができる。このため、パケット中継処理におけるオーバヘッドを削減し、パケット中継処理を高速に行うことができる。
【００１５】
また、本発明は、第３に、上記第２のパケット中継方法であって、前記パケットの中継処理を行うステップにおいて、前記中継処理情報から送出インタフェース情報を取得し、必要に応じて前記パケットの複製処理及び前記パケットのヘッダ情報の変更処理を行い、この処理後のパケットを前記送出インタフェース情報に従って出力するものとする。
【００１６】
また、本発明は、第４に、上記第２または第３のパケット中継方法であって、前記フロー固有情報に対応する中継処理情報が保持されていない場合に、未配送の受信者アドレスに対してユニキャスト経路表の検索を行い、その検索結果に基づいて送出インタフェース情報を決定するステップと、必要に応じて前記パケットの複製処理及び前記パケットのヘッダ情報の変更処理を行い、この処理後のパケットを前記送出インタフェース情報に従って出力するステップと、を有するものとする。
【００１７】
また、本発明は、第５に、上記第４のパケット中継方法であって、更に、少なくとも前記送出インタフェース情報を含む中継処理情報を、前記フロー固有情報との対応を付けて記憶手段に記憶するステップを有するものとする。
【００１８】
また、本発明は、第６に、上記第５のパケット中継方法であって、前記中継処理情報は、更に、前記パケットのヘッダ情報の変更処理結果の情報を含むものとする。
【００１９】
また、本発明は、第７に、上記第１のパケット中継方法であって、前記取得したフロー固有情報をハッシュ関数に入力してこのフロー固有情報に対応したハッシュ値を取得するステップと、前記ハッシュ値に対応する中継処理情報が記憶手段に保持されているか否かを判定するステップと、前記ハッシュ値に対応する中継処理情報が保持されている場合に、この中継処理情報を用いて前記パケットの中継処理を行うステップと、を有するものである。
【００２０】
これにより、パケットのフロー固有情報を取得し、このフロー固有情報をハッシュ関数に入力してこのフロー固有情報に対応したハッシュ値を取得し、ハッシュ値に対応する中継処理情報が保持されている場合に、この中継処理情報を用いて前記パケットの中継処理を行うことによって、パケットに識別子が付与されていない場合であっても、一度中継されたパケットと同一フローであれば、それ以降到着するパケットに対するユニキャスト経路表の検索処理を省略してパケットを中継することができる。また、ハッシュ値を用いることで、中継処理情報の有無の判定をより簡易かつ高速に行うことができる。このため、パケット中継処理におけるオーバヘッドを削減し、パケット中継処理を高速に行うことができる。
【００２１】
また、本発明は、第８に、上記第７のパケット中継方法であって、前記パケットの中継処理を行うステップにおいて、前記中継処理情報から送出インタフェース情報を取得し、必要に応じて前記パケットの複製処理及び前記パケットのヘッダ情報の変更処理を行い、この処理後のパケットを前記送出インタフェース情報に従って出力するものとする。
【００２２】
また、本発明は、第９に、上記第７または第８のパケット中継方法であって、前記ハッシュ値に対応する中継処理情報が保持されていない場合に、未配送の受信者アドレスに対してユニキャスト経路表の検索を行い、その検索結果に基づいて送出インタフェース情報を決定するステップと、必要に応じて前記パケットの複製処理及び前記パケットのヘッダ情報の変更処理を行い、この処理後のパケットを前記送出インタフェース情報に従って出力するステップと、を有するものとする。
【００２３】
また、本発明は、第１０に、上記第９のパケット中継方法であって、更に、少なくとも前記送出インタフェース情報を含む中継処理情報を、前記ハッシュ値との対応を付けて記憶手段に記憶するステップを有するものとする。
【００２４】
また、本発明は、第１１に、上記第９のパケット中継方法であって、更に、少なくとも前記送出インタフェース情報を含む中継処理情報を、前記ハッシュ値及び前記フロー固有情報との対応を付けて記憶手段に記憶するステップを有するものとする。
【００２５】
また、本発明は、第１２に、上記第１０または第１１のパケット中継方法であって、前記中継処理情報は、更に、前記パケットのヘッダ情報の変更処理結果の情報を含むものとする。
【００２６】
また、本発明は、第１３に、上記第２から第１２のいずれかのパケット中継方法であって、前記中継処理情報に対して有効時間が設定されている場合、前記有効時間に基づき、前記中継処理情報が記憶手段に記憶されてからの経過時間、または前記中継処理情報が最後に参照されてからの経過時間が所定時間経過したときに、該当する中継処理情報を前記記憶手段から消去するステップを有するものとする。
【００２７】
また、本発明は、第１４に、上記第２から第１２のいずれかのパケット中継方法であって、ユニキャスト経路表の変更があった場合に、前記中継処理情報を前記記憶手段から消去するステップを有するものとする。
【００２８】
また、本発明は、第１５に、送信者がパケット中に複数の受信者のアドレスを記述することで、前記パケットの受信者を明確に指定する明示的マルチキャスト方式のパケットを中継するパケット中継装置であって、前記パケットを解析し、同一のフローならば同一の値となるフロー固有情報を取得するフロー固有情報取得手段と、前記取得したフロー固有情報に対応する中継処理情報に基づいて前記パケットの中継処理を行う中継処理手段と、を備えるものである。
【００２９】
これにより、パケットのフロー固有情報と前記フロー固有情報に対応する中継処理情報に基づいてパケットの中継処理を行うことにより、パケットに識別子が付与されていない場合であっても、一度中継されたパケットと同一フローであれば、それ以降到着するパケットに対するユニキャスト経路表の検索処理を省略してパケットを中継することができる。このため、パケット中継処理におけるオーバヘッドを削減し、パケット中継処理を高速に行うことができる。
【００３０】
また、本発明は、第１６に、上記第１５のパケット中継装置であって、前記フロー固有情報に対応する中継処理情報を記憶する記憶手段と、前記取得したフロー固有情報に対応する中継処理情報が前記記憶手段に保持されているか否かを判定する中継処理情報判定手段とを備え、前記中継処理手段は、前記フロー固有情報に対応する中継処理情報が保持されている場合に、この中継処理情報を用いて前記パケットの中継処理を行うものである。
【００３１】
これにより、パケットのフロー固有情報を取得し、フロー固有情報に対応する中継処理情報が保持されている場合に、この中継処理情報を用いて前記パケットの中継処理を行うことによって、パケットに識別子が付与されていない場合であっても、一度中継されたパケットと同一フローであれば、それ以降到着するパケットに対するユニキャスト経路表の検索処理を省略してパケットを中継することができる。このため、パケット中継処理におけるオーバヘッドを削減し、パケット中継処理を高速に行うことができる。
【００３２】
また、本発明は、第１７に、上記第１５のパケット中継装置であって、前記取得したフロー固有情報をハッシュ関数に入力してこのフロー固有情報に対応したハッシュ値を取得するハッシュ値取得手段と、前記ハッシュ値に対応する中継処理情報を記憶する記憶手段と、前記ハッシュ値に対応する中継処理情報が記憶手段に保持されているか否かを判定する中継処理情報判定手段とを備え、前記中継処理手段は、前記ハッシュ値に対応する中継処理情報が保持されている場合に、この中継処理情報を用いて前記パケットの中継処理を行うものである。
【００３３】
これにより、パケットのフロー固有情報を取得し、このフロー固有情報をハッシュ関数に入力してこのフロー固有情報に対応したハッシュ値を取得し、ハッシュ値に対応する中継処理情報が保持されている場合に、この中継処理情報を用いて前記パケットの中継処理を行うことによって、パケットに識別子が付与されていない場合であっても、一度中継されたパケットと同一フローであれば、それ以降到着するパケットに対するユニキャスト経路表の検索処理を省略してパケットを中継することができる。また、ハッシュ値を用いることで、中継処理情報の有無の判定をより簡易かつ高速に行うことができる。このため、パケット中継処理におけるオーバヘッドを削減し、パケット中継処理を高速に行うことができる。
【発明の効果】
【００３４】
本発明によれば、パケット中継処理時のオーバヘッドを削減でき、また、パケットに識別子が付与されていない場合であっても、パケット中継処理の負荷低減及び高速化を実現することができる。
【発明を実施するための最良の形態】
【００３５】
以下に示す実施形態では、明示的マルチキャスト方式として、特にＸＣＡＳＴ方式を想定して具体例を説明するが、本発明はＸＣＡＳＴ方式に依存するものではなく、他のマルチキャスト方式のパケット中継にも適用可能なものである。本発明のパケット中継方法及びパケット中継装置は、ＩＰｖ４やＩＰｖ６等のネットワークにおけるルータなどに適用可能である。
【００３６】
本実施形態の第１の態様は、明示的マルチキャスト方式において、フロー固有情報をベースとした中継処理情報を記憶する記憶領域（キャッシュメモリ）を備えることを特徴とするものである。明示的マルチキャスト方式における未知のパケットが到着すると、前述した第１の従来パケット中継処理方法に従ってパケット中継処理を行うと共に、パケットの中継処理情報をフロー固有情報に対応付けて記憶領域（キャッシュメモリ）に保持し、以後、同一フローとなるパケットが到着した場合は、フロー固有情報に対応する中継処理情報を利用してパケット中継処理を行う。
【００３７】
これにより、一度中継されたパケットと同一フローであれば、それ以降到着するパケットの未配送の受信者アドレスに対するユニキャスト経路表の検索処理を省略することができる。このため、第１の従来のパケット中継処理方法におけるオーバヘッドを削減し、パケット中継処理を削減するとともに、パケット中継処理を高速に行うことができる。
【００３８】
また、このようなパケット中継処理方法によれば、前述した第２の従来パケット中継処理方法と比較して、フロー固有情報をベースとした中継処理情報のキャッシュ機構を備えることで、第２の従来パケット中継処理方法において用いられる識別子がパケットに付与されない場合でも、パケット中継処理を高速化することができる。
【００３９】
本実施形態の第２の態様は、明示的マルチキャスト方式において、ハッシュ値をベースとした中継処理情報を記憶する記憶領域（キャッシュメモリ）を備えることを特徴とするものである。明示的マルチキャスト方式における未知のパケットが到着すると、前述した第１の従来パケット中継処理方法に従ってパケット中継処理を行うと共に、パケットのフロー固有情報からハッシュ値を取得し、パケットの中継処理情報をハッシュ値に対応付けて記憶領域（キャッシュメモリ）に保持し、以後、同一フローのパケットが到着した場合は、パケットのフロー固有情報から取得したハッシュ値に対応する中継処理情報を利用してパケット中継処理を行う。
【００４０】
これにより、上記第１の態様におけるパケット中継処理方法と同様の効果が得られると共に、第１の態様におけるフロー固有情報のみを利用したシーケンシャルな中継処理情報の検索に比べて、記憶領域（キャッシュメモリ）中の中継処理情報の検索時間を短縮することができる。
【００４１】
（第１の実施形態）
図１は本発明の第１の実施形態に係るパケット中継装置の構成を示すブロック図である。第１の実施形態のパケット中継装置１００は、複数の入力インタフェース（Ｉ／Ｆ）１０１−１〜１０１−ｎと、パケット受信部１０２と、パケット中継処理切替部１０３と、明示的マルチキャストパケット中継処理部１０４と、ユニキャスト経路表１１０と、その他パケット処理部１１１と、パケット送信部１１２と、複数の送出インタフェース（Ｉ／Ｆ）１１３−１〜１１３−ｎとを有して構成されている。また、明示的マルチキャストパケット中継処理部１０４は、パケット解析部１０５と、経路表探索部１０６と、パケット複製／ヘッダ処理部１０７と、メモリ制御部１０８と、キャッシュメモリ１０９とを有して構成される。さらに、パケット解析部１０５は、フロー固有情報取得部１０５１を備えている。
【００４２】
各入力インタフェース（Ｉ／Ｆ）１０１−１〜１０１−ｎに到来したパケットは、パケット受信部１０２で受信され、パケット中継処理切替部１０３に供給される。パケット中継処理切替部１０３は、明示的マルチキャスト方式のパケットを明示的マルチキャストパケット中継処理部１０４に供給し、それ以外のパケットをその他パケット処理部１１１に供給する。
【００４３】
明示的マルチキャストパケット中継処理部１０４において、パケット解析部１０５は、明示的マルチキャスト方式のパケットを解析する。ここで、パケット解析部１０５内のフロー固有情報取得部１０５１は、同一のフローならば同一の値となるフロー固有情報を取得する。フロー固有情報取得部１０５１は、フロー固有情報として、例えばＩＰヘッダ中の宛先アドレス／送信元アドレス、フローラベル、ＵＤＰヘッダ中の宛先ポート番号／送信元ポート番号、オプションヘッダに記述された明示的マルチキャスト方式の制御情報である全受信者のアドレス（受信者アドレス）、配送済を示すフラグ、各受信者がパケットを受信するために明示的に指定されたポート番号などを取得する。
【００４４】
次に、パケット解析部１０５は、フロー固有情報に対応する中継処理情報がキャッシュメモリ１０９内に格納されているかどうかをメモリ制御部１０８に問い合わせる。すなわち、パケット解析部１０５は、フロー固有情報取得手段及び中継処理情報判定手段の機能を有するものである。このとき、明示的マルチキャストパケット中継処理部１０４では、フロー固有情報に対応する中継処理情報がキャッシュメモリ１０９内に保持されているかどうかで処理方法が異なる。ここで、キャッシュメモリ１０９内にフロー固有情報に対応する中継処理情報が保持されていた場合を処理方法１−１、保持されていなかった場合を処理方法１−２と記述し、それぞれの処理方法を以下に説明する。
【００４５】
（処理方法１−１）：パケット中継装置１００に入力された明示的マルチキャスト方式におけるパケットに対して、キャッシュメモリ１０９内にフロー固有情報に対応する中継処理情報が保持されていた場合、パケット解析部１０５は、この中継処理情報から送出インタフェース情報を取得する。そして、送出インタフェース情報によって１つの送出インタフェースのみ特定される場合は、当該パケットをパケット解析部１０５からパケット送信部１１２を介して、送出インタフェース１１３−１〜１１３−ｎのうちの対応する送出インタフェースに出力する。
【００４６】
また、送出インタフェース情報の内容により、送出インタフェースが２つ以上ある場合は、パケット解析部１０５からパケット複製／ヘッダ処理部１０７にパケットを伝達する。パケット複製／ヘッダ処理部１０７では、中継処理情報に基づいて送出インタフェース分のパケット複製を行う。そして、ヘッダ情報変更処理として、複製したそれぞれのパケットに対して、送出インタフェースが同一となる受信者アドレス以外の受信者のアドレスを配送済みとみなして、配送済みのマーキングを付与する。また、ＩＰヘッダの宛先アドレスが配送済みとなった受信者のアドレスである場合は、未配送の受信者アドレスから一つを選択し、ＩＰヘッダの宛先アドレスに設定する。そして、ヘッダ情報変更処理後のパケットを、パケット複製／ヘッダ処理部１０７からパケット送信部１１２を介して、送出インタフェース１１３−１〜１１３−ｎのうちの対応する送出インタフェースに出力する。
【００４７】
（処理方法１−２）：パケット中継装置１００に入力された明示的マルチキャスト方式におけるパケットに対して、キャッシュメモリ１０９内にフロー固有情報に対応する中継処理情報が保持されていなかった場合、パケット解析部１０５は、当該パケットを経路表検索部１０６に伝達する。
【００４８】
経路表検索部１０６では、パケット中の未配送の受信者アドレス毎に、ユニキャスト経路表１１０の検索を行い、各未配送の受信者アドレスに対する出力すべき送出インタフェース１１３−１〜１１３−ｎを決定する。ユニキャスト経路表１１０の検索結果、１つの送出インタフェースのみ特定される場合は、当該パケットをパケット解析部１０５からパケット送信部１１２を介して、送出インタフェース１１３−１〜１１３−ｎのうちの対応する送出インタフェースに出力する。
【００４９】
また、ユニキャスト経路表１１０の検索結果により、送出インタフェースが２つ以上ある場合は、パケット解析部１０５からパケット複製／ヘッダ処理部１０７にパケットを伝達する。パケット複製／ヘッダ処理部１０７では、経路検索結果に基づいて送出インタフェース分のパケット複製を行う。そして、ヘッダ情報変更処理として、複製したそれぞれのパケットに対して、送出インタフェースが同一となる受信者アドレス以外の受信者のアドレスを配送済みとみなして、配送済みのマーキングを付与する。また、ＩＰヘッダの宛先アドレスが配送済みとなった受信者のアドレスである場合は、未配送の受信者アドレスから一つを選択し、ＩＰヘッダの宛先アドレスに設定する。そして、ヘッダ情報変更処理後のパケットを、パケット複製／ヘッダ処理部１０７からパケット送信部１１２を介して、送出インタフェース１１３−１〜１１３−ｎのうちの対応する送出インタフェースに出力する。
【００５０】
このとき、経路表検索部１０６及びパケット複製／ヘッダ処理部１０７は、パケット中の未配送の受信者アドレスに対するユニキャスト経路表１１０の検索結果と、複製したそれぞれのパケットに対して行ったＩＰヘッダ及び明示的マルチキャスト方式における制御情報を含むヘッダ情報の変更処理結果とを、中継処理情報として、パケットのフロー固有情報と共にメモリ制御部１０８を介してキャッシュメモリ１０９に書き込む。なお、中継処理情報は、フロー固有情報と対応付けて記憶しておく。
【００５１】
なお、上記処理方法１−１及び処理方法１−２において、メモリ制御部１０８は、フロー固有情報を引数として、キャッシュメモリ１０９に対する参照要求や書込み要求を処理する。上記のように、パケット解析部１０５、経路表検索部１０６、パケット複製／ヘッダ処理部１０７、メモリ制御部１０８によって中継処理手段の機能が実現される。また、キャッシュメモリ１０９が記憶手段の機能を有する。
【００５２】
図２は本発明の第１の実施形態に係るパケット中継装置のキャッシュメモリの内容を示す説明図である。キャッシュメモリ１０９には、図２に示すように、フロー固有情報とその中継処理情報から構成されるキャッシュエントリーが記憶される。また、このキャッシュエントリーに対して、有効時間が設定されて記憶される。メモリ制御部１０８は、有効時間を経過したフロー固有情報とその中継処理情報によるキャッシュエントリーを、キャッシュメモリ１０９から削除する。これにより、キャッシュメモリ１０９の容量を節約することができる。
【００５３】
また、メモリ制御部１０８は、パケット中継装置１００に入力される明示的マルチキャスト方式におけるパケットを受信する度に、キャッシュメモリ１０９内のパケットのフロー固有情報とその中継処理情報によるキャッシュエントリーの有効時間を延長する。これにより、一定時間内に入力されるパケットに対して、キャッシュエントリーをキャッシュメモリ１０９内に保持し続けることができる。
【００５４】
また、メモリ制御部１０８は、ユニキャスト経路表１１０を監視し、ユニキャスト経路表に変更があった場合、キャッシュメモリ１０９内のフロー固有情報とその中継処理情報を保持するキャッシュエントリーを消去することで、最新のユニキャスト経路に従ったパケット中継処理ができる。
【００５５】
図３は本発明の第１の実施形態に係るパケット中継装置の動作によるパケット中継方法の手順を示すフローチャートである。
パケットを受信した際に、パケット解析部１０５内のフロー固有情報取得部１０５１において、受信したパケットのフロー固有情報を取得する（ステップＳ１１）。次に、パケット解析部１０５において、メモリ制御部１０８を介して、取得したフロー固有情報に対応する中継処理情報がキャッシュメモリ１０９に格納されているか検索する（ステップＳ１２）。
【００５６】
フロー固有情報に対応する中継処理情報がキャッシュメモリ１０９に格納されている場合は、パケット解析部１０５においてその中継処理情報を取得する（ステップＳ１３）。そして、パケット解析部１０５において、取得した中継処理情報に、送出インタフェースが２つ以上あるか否かを判断する（ステップＳ１４）。
【００５７】
ここで、送出インタフェースが２つ以上ある場合は、パケット複製／ヘッダ処理部１０７において、受信したパケットに対して、ステップＳ１３で取得した中継処理情報に記述されている送出インタフェース分のパケット複製を行う。そして、複製したそれぞれのパケットに対して、ステップＳ１３で取得した中継処理情報からＩＰヘッダ及び明示的マルチキャスト方式における制御情報を含むヘッダ情報の変更処理を行い、ヘッダ情報変更処理後のパケットをパケット複製／ヘッダ処理部１０７から対応する送出インタフェースに出力する（ステップＳ１５）。
【００５８】
一方、送出インタフェースが１つである場合は、明示的マルチキャストパケット中継処理部１０４において、受信したパケットに対して何も行わず、ＩＰヘッダを参照して通常のユニキャストルーティングを行い、パケット解析部１０５から対応する送出インタフェースに出力する（ステップＳ１６）。なお、明示的マルチキャスト方式によっては、ＩＰヘッダや明示的マルチキャスト方式における制御情報に対して、何らかの処理を行う場合がある。
【００５９】
また、フロー固有情報に対応する中継処理情報がキャッシュメモリ１０９に格納されていない場合は、経路表検索部１０６において、受信したパケットに記述されている未配送の受信者アドレス毎に、ユニキャスト経路表の検索を行い、各未配送の受信者アドレスに対する出力すべき送出インタフェースを決定する（ステップＳ１７）。そして、パケット解析部１０５において、経路検索結果に送出インタフェースが２つ以上あるか判断する（ステップＳ１８）。
【００６０】
ここで、送出インタフェースが２つ以上ある場合は、パケット複製／ヘッダ処理部１０７において、送出インタフェース分のパケット複製を行う。そして、複製したそれぞれのパケットに対して必要となるＩＰヘッダ及び明示的マルチキャスト方式における制御情報を含むヘッダ情報の変更処理を行う。このとき、ユニキャスト経路表の探索結果に基づいて決定した送出インタフェース情報と、複製したそれぞれのパケットに対して行ったＩＰヘッダ及び明示的マルチキャスト方式における制御情報を含むヘッダ情報の変更処理結果とを、中継処理情報として、パケットのフロー固有情報と共にキャッシュメモリ１０９に書き込む。なお、中継処理情報は、フロー固有情報と対応付けて記憶しておく。そして、ヘッダ情報変更処理後のパケットをパケット複製／ヘッダ処理部１０７から対応する送出インタフェースに出力する（ステップＳ１９）。
【００６１】
一方、送出インタフェースが１つである場合は、明示的マルチキャストパケット中継処理部１０４において、受信したパケットに対して何も行わず、ＩＰヘッダを参照して通常のユニキャストルーティングを行う。なお、明示的マルチキャスト方式によっては、ユニキャスト経路表の探索結果に基づいて決定した送出インタフェース情報、あるいは、ＩＰヘッダや明示的マルチキャスト方式における制御情報等のヘッダ情報に対して、何らかの処理を行う場合がある。このように、送出インタフェース情報やヘッダ情報に対して何らかの処理を行う場合は、その処理結果を中継処理情報として、フロー固有情報と共にキャッシュメモリ１０９に書き込む（ステップＳ２０）。なお、中継処理情報は、フロー固有情報と対応付けて記憶しておく。
【００６２】
図４〜図６は中継処理情報の記憶形式の一例を示す図である。図４に示す第１例は、中継処理情報が、送出インタフェースの情報と、その送出インタフェースに対応する受信者のアドレスの組により構成される例である。また、図５に示す第２例は、中継処理情報が、送出インタフェースの情報と、パケットの受信者アドレスのリストの要素番号の組により構成される例である。また、図６に示す第３例は、中継処理情報が、送出インタフェースの情報と、その送出インタフェースに出力する際の、明示的マルチキャスト方式における制御情報も含むパケットのヘッダイメージの組により構成される例である。
【００６３】
この第１の実施形態によれば、一度中継されたパケットと同一フローであれば、それ以降到着するパケットに対するユニキャスト経路表の検索処理を省略することができ、パケット中継処理におけるオーバヘッドを削減することができる。また、この実施形態は、パケットに識別子が付与されていない場合であっても適用可能であり、パケット中継処理の負荷を削減し、パケット中継処理を高速に行うことができる。
【００６４】
（第２の実施形態）
図７は本発明の第２の実施形態に係るパケット中継装置の構成を示すブロック図である。第２の実施形態のパケット中継装置２００は、明示的マルチキャストパケット中継部２０４の構成が図１に示した第１の実施形態に係るパケット中継装置１００と異なる。なお、第１の実施形態と同様の構成要素には同一符号を付して説明を省略する。
【００６５】
明示的マルチキャストパケット中継部２０４のパケット解析部２０５は、フロー固有情報取得部１０５１とハッシュ関数によるハッシュテーブルを有するハッシュ関数部２０５１とを有している。このパケット解析部２０５は、フロー固有情報取得部１０５１により、同一のフローならば同一の値となるフロー固有情報を取得する。そして、取得したフロー固有情報をハッシュ関数部２０５１に供給し、ハッシュ関数部２０５１においてハッシュテーブルを参照してハッシュ値を取得する。そして、このハッシュ値を用いて、メモリ制御部２０８を介してキャッシュメモリ２０９にアクセスし、フロー固有情報のハッシュ値に対応する中継処理情報がキャッシュメモリ２０９内に格納されているかどうかを判定する。すなわち、パケット解析部２０５は、フロー固有情報取得手段、ハッシュ値取得手段及び中継処理情報判定手段の機能を有するものである。
【００６６】
第２の実施形態においても、第１の実施形態と同様に、キャッシュメモリ２０９内にフロー固有情報に対応する中継処理情報が保持されている場合は上記処理方法１−１を、保持されていない場合は上記処理方法１−２を実行する。なお、この処理方法１−１及び処理方法１−２において、メモリ制御部２０８は、フロー固有情報より求めたハッシュ値を引数として、キャッシュメモリ２０９に対する参照要求や書込み要求を処理する。
【００６７】
図８は本発明の第２の実施形態に係るパケット中継装置のキャッシュメモリの内容を示す説明図である。キャッシュメモリ２０９には、図８に示すように、ハッシュ値、フロー固有情報、中継処理情報から構成されるキャッシュエントリーが記憶される。また、このキャッシュエントリーに対して、有効時間が設定されて記憶される。メモリ制御部２０８は、有効時間を経過したフロー固有情報とその中継処理情報によるキャッシュエントリーを、キャッシュメモリ２０９から削除する。これにより、キャッシュメモリ２０９の容量を節約することができる。
【００６８】
また、メモリ制御部２０８は、パケット中継装置２００に入力される明示的マルチキャスト方式におけるパケットを受信する度に、キャッシュメモリ２０９内のパケットのフロー固有情報とその中継処理情報によるキャッシュエントリーの有効時間を延長する。これにより、一定時間内に入力されるパケットに対して、キャッシュエントリーをキャッシュメモリ２０９内に保持し続けることができる。
【００６９】
また、メモリ制御部２０８は、ユニキャスト経路表１１０を監視し、ユニキャスト経路表に変更があった場合、キャッシュメモリ２０９内のフロー固有情報とその中継処理情報を保持するキャッシュエントリーを消去することで、最新のユニキャスト経路に従ったパケット中継処理ができる。
【００７０】
図９は本発明の第２の実施形態に係るパケット中継装置の動作によるパケット中継方法の手順を示すフローチャートである。
パケットを受信した際に、パケット解析部２０５内のフロー固有情報取得部１０５１において、受信したパケットのフロー固有情報を取得する。そして、ハッシュ関数部２０５１において、フロー固有情報をハッシュテーブルのハッシュ関数に入力してハッシュ値を取得する（ステップＳ２１）。次に、パケット解析部２０５において、メモリ制御部２０８を介して、取得したフロー固有情報のハッシュ値に対応する中継処理情報がキャッシュメモリ２０９に格納されているか検索する（ステップＳ２２）。
【００７１】
なお、異なるフロー固有情報であっても、ハッシュ関数に入力すると同一のハッシュ値が得られる場合があるため、ハッシュ値のみで中継処理情報を参照すると、実際の対応関係とは異なる中継処理情報が参照されることがある。そこで、図８に示したように、キャッシュメモリ２０９にはハッシュ値及び中継処理情報とともにフロー固有情報を格納し、ハッシュ値から中継処理情報を参照する場合は、フロー固有情報を確認することで異なる中継処理情報が参照されること回避する。
【００７２】
フロー固有情報のハッシュ値に対応する中継処理情報がキャッシュメモリ２０９に格納されている場合は、パケット解析部２０５においてその中継処理情報を取得する（ステップＳ２３）。そして、パケット解析部２０５において、取得した中継処理情報に、送出インタフェースが２つ以上あるか否かを判断する（ステップＳ２４）。
【００７３】
ここで、送出インタフェースが２つ以上ある場合は、パケット複製／ヘッダ処理部１０７において、受信したパケットに対して、ステップＳ２３で取得した中継処理情報に記述されている送出インタフェース分のパケット複製を行う。そして、複製したそれぞれのパケットに対して、ステップＳ２３で取得した中継処理情報からＩＰヘッダ及び明示的マルチキャスト方式における制御情報を含むヘッダ情報の変更処理を行い、ヘッダ情報変更処理後のパケットをパケット複製／ヘッダ処理部１０７から対応する送出インタフェースに出力する（ステップＳ２５）。
【００７４】
一方、送出インタフェースが１つである場合は、明示的マルチキャストパケット中継処理部２０４において、受信したパケットに対して何も行わず、ＩＰヘッダを参照して通常のユニキャストルーティングを行い、パケット解析部２０５から対応する送出インタフェースに出力する（ステップＳ２６）。なお、明示的マルチキャスト方式によっては、ＩＰヘッダや明示的マルチキャスト方式における制御情報に対して、何らかの処理を行う場合がある。
【００７５】
また、フロー固有情報のハッシュ値に対応する中継処理情報がキャッシュメモリ２０９に格納されていない場合は、経路表検索部１０６において、受信したパケットに記述されている未配送の受信者アドレス毎に、ユニキャスト経路表の検索を行い、各未配送の受信者アドレスに対する出力すべき送出インタフェースを決定する（ステップＳ２７）。そして、パケット解析部２０５において、経路検索結果に送出インタフェースが２つ以上あるか判断する（ステップＳ２８）。
【００７６】
ここで、送出インタフェースが２つ以上ある場合は、パケット複製／ヘッダ処理部１０７において、送出インタフェース分のパケット複製を行う。そして、複製したそれぞれのパケットに対して必要となるＩＰヘッダ及び明示的マルチキャスト方式における制御情報を含むヘッダ情報の変更処理を行う。このとき、ユニキャスト経路表の探索結果に基づいて決定した送出インタフェース情報と、複製したそれぞれのパケットに対して行ったＩＰヘッダ及び明示的マルチキャスト方式における制御情報を含むヘッダ情報の変更処理結果とを、中継処理情報として、パケットのハッシュ値及びフロー固有情報と共にキャッシュメモリ２０９に書き込む。なお、中継処理情報は、フロー固有情報と対応付けて記憶しておく。そして、ヘッダ情報変更処理後のパケットをパケット複製／ヘッダ処理部１０７から対応する送出インタフェースに出力する（ステップＳ２９）。
【００７７】
一方、送出インタフェースが１つである場合は、明示的マルチキャストパケット中継処理部２０４において、受信したパケットに対して何も行わず、ＩＰヘッダを参照して通常のユニキャストルーティングを行う。なお、明示的マルチキャスト方式によっては、ユニキャスト経路表の探索結果に基づいて決定した送出インタフェース情報、あるいは、ＩＰヘッダや明示的マルチキャスト方式における制御情報等のヘッダ情報に対して、何らかの処理を行う場合がある。このように、送出インタフェース情報やヘッダ情報に対して何らかの処理を行う場合は、その処理結果を中継処理情報として、ハッシュ値及びフロー固有情報と共にキャッシュメモリ２０９に書き込む（ステップＳ３０）。なお、中継処理情報は、フロー固有情報と対応付けて記憶しておく。
【００７８】
この第２の実施形態によれば、第１の実施形態と同様、一度中継されたパケットと同一フローであれば、それ以降到着するパケットに対するユニキャスト経路表の検索処理を省略することができ、パケット中継処理におけるオーバヘッドを削減することができる。また、この実施形態は、パケットに識別子が付与されていない場合であっても適用可能であり、パケット中継処理の負荷を削減し、パケット中継処理を高速に行うことができる。第２の実施形態は、ハッシュ値を用いることにより、フロー固有情報に対応する中継処理情報の有無の判定処理（中継処理情報の検索処理）をより容易かつ高速に行うことができる。
【００７９】
上述したように、本実施形態によれば、パケットに識別子が付与されていない場合であっても、一度中継されたパケットと同一フローであれば、それ以降到着するパケットに対するユニキャスト経路表の検索処理を省略することが可能となる。これによって、パケット中継処理におけるオーバヘッドを削減するとともにパケット中継処理負荷を削減し、パケット中継処理の高速化を図ることができる。
【産業上の利用可能性】
【００８０】
本発明は、パケット中継処理時のオーバヘッドを削減でき、また、パケットに識別子が付与されていない場合であっても、パケット中継処理の負荷低減及び高速化を実現することが可能となる効果を有し、パケットに複数の受信者の配信先を記述して配信を行う明示的マルチキャスト方式のパケット中継方法及びパケット中継装置等に有用である。
【図面の簡単な説明】
【００８１】
【図１】本発明の第１の実施形態に係るパケット中継装置の構成を示すブロック図
【図２】本発明の第１の実施形態に係るパケット中継装置のキャッシュメモリの内容を示す説明図
【図３】本発明の第１の実施形態に係るパケット中継装置の動作によるパケット中継方法の手順を示すフローチャート
【図４】本実施形態に係る中継処理情報の記憶形式の第１例を示す図
【図５】本実施形態に係る中継処理情報の記憶形式の第２例を示す図
【図６】本実施形態に係る中継処理情報の記憶形式の第３例を示す図
【図７】本発明の第２の実施形態に係るパケット中継装置の構成を示すブロック図
【図８】本発明の第２の実施形態に係るパケット中継装置のキャッシュメモリの内容を示す説明図
【図９】本発明の第２の実施形態に係るパケット中継装置の動作によるパケット中継方法の手順を示すフローチャート
【符号の説明】
【００８２】
１００，２００  パケット中継装置
１０１  入力インタフェース
１０２  パケット受信部
１０３  パケット中継処理切替部
１０４，２０４  明示的マルチキャストパケット中継処理部
１０５，２０５  パケット解析部
１０６  経路表探索部
１０７  パケット複製／ヘッダ処理部
１０８，２０８  メモリ制御部
１０９，２０９  キャッシュメモリ
１１０  ユニキャスト経路表
１１１  その他パケット処理部
１１２  パケット送信部
１１３  送出インタフェース
１０５１  フロー固有情報取得部
２０５１  ハッシュ関数部
【図１】
2006191468.tif 000003
【図２】
2006191468.tif 000004
【図３】
2006191468.tif 000005
【図４】
2006191468.tif 000006
【図５】
2006191468.tif 000007
【図６】
2006191468.tif 000008
【図７】
2006191468.tif 000009
【図８】
2006191468.tif 000010
【図９】
2006191468.tif 000011