JP6148546B2 - パケット転送装置及びプログラム - Google Patents

Description

本発明は、複数のインタフェースを有するパケット転送装置における受信パケットの転送技術に関する。

ネットワークの制御として、オープンフロー技術が注目されている。オープンフロー技術を利用したネットワークにおいて、フローは、例えば、ＭＡＣアドレス、ＩＰアドレス、ポート番号等の組み合わせで識別され、フロー毎に品質（ＱｏＳ）制御や経路制御が行われる。オープンフロー・ネットワークでパケットの転送を行うパケット転送装置は、入力パケットのヘッダ情報等からフロー識別子を判定し、判定したフロー識別子と、フロー・テーブルとに基づき当該パケットを出力すべきインタフェースを決定する。例えば、フロー識別子が、送信元及び送信先ＩＰアドレスと、送信元及び送信先ポート番号の組み合わせで特定される場合、これら４つの値を所定順に並べた値がフロー識別子となる。

なお、フロー・テーブルの各エントリは、ワイルドカード、つまり、フロー識別子の一部又は全部が任意の値となることを許容しているため、１つのフロー識別子が、フロー・テーブル内の複数のエントリと一致することが生じ得る。例えば、フロー識別子が、送信元及び送信先ＩＰアドレスと、送信元及び送信先ポート番号の組み合わせで特定され、図５に示すフロー・テーブルが、パケット転送装置に設定されている場合を考える。なお、図５の"*"は、ワイルドカードであり、フロー識別子の該当する位置の値が任意の値で良いことを示している。また、番号１のエントリは、ディフォルト経路であり、総てのフロー識別子と一致するエントリである。ここで、例えば、送信元ＩＰアドレスが、（Ｘ１、Ｘ２、Ｘ３、Ｘ４）であり、送信先ＩＰアドレスが（Ｙ１、Ｙ２、Ｙ３、Ｙ４）のパケットを受信した場合、この受信パケットは、フロー・テーブルの番号１、１００、１０１及び１０２の４つのエントリと一致することになる。フロー・テーブルの各エントリには優先順位が付与されており、フロー識別子が複数のエントリに一致する場合、最も優先順位の高いエントリに従い出力インタフェースが決定される。例えば、番号１、１００、１０１及び１０２の４つのエントリのうち、最も優先順位の高いものが番号１０２のエントリである場合、この受信パケットは、インタフェースＩＦ＃３に出力されることになる。

上記の通り、ワイルドカードを許容するフロー・テーブルでは、一致するエントリが複数存在し得るため、一致するエントリの検索と、優先順位の判定に時間がかかるという問題がある。このため、非特許文献１は、ワイルドカードを許容するフロー・テーブル（以下、ワイルドカード型テーブルと呼ぶ。）と、ワイルドカードを使用せず、フロー識別子と出力インタフェースとの関係を示すフロー・テーブル（以下、完全一致型テーブルと呼ぶ。）を設ける構成を開示している。具体的には、非特許文献１は、パケットを受信した場合、まず、完全一致型テーブルにより出力インタフェースを決定し、完全一致型テーブルにエントリが無く、したがって、完全一致型テーブルでは出力インタフェースを決定できない場合に、ワイルドカード型テーブルにより出力インタフェースを決定すると共に、決定した出力インタフェースと受信したパケットのフロー識別子との対応関係を、完全一致型テーブルに追加することを開示している。

この構成により、新たなフローに属するパケットが到着した段階では、検索速度の遅いワイルドカード型テーブルが使用されるが、その後、完全一致型テーブルにエントリが追加されると、検索速度の速い完全一致型テーブルにより出力インタフェースが決定されるので、全体としての検索速度が速くなる。

Ｎ．Ｍａｔｓｕｍｏｔｏ，ｅｔ ａｌ．，"ＬｉｇｈｔＦｌｏｗ：Ｓｐｅｅｄｉｎｇ Ｕｐ ＧＰＵ−ｂａｓｅｄ Ｆｌｏｗ Ｓｗｉｔｃｈｉｎｇ ａｎｄ Ｆａｃｉｌｉｔａｔｉｎｇ Ｍａｉｎｔｅｎａｎｃｅ ｏｆ Ｆｌｏｗ Ｔａｂｌｅ"，ＨＰＳＲ２０１２

しかしながら、非特許文献１に記載の構成においては同じフローに属するパケットの出力順序が、入力順序とは異なることが生じ得る。例えば、図６に示す様に、同一のフローに属するパケットＡ、Ｂ、Ｃ、Ｄ及びＥをその記載順で受信したものとする。なお、このフローのフロー識別子に対するエントリは、完全一致型テーブルには存在しないものとする。第１決定部は、完全一致型テーブルでは出力インタフェースを決定できないため、このフローに属するパケットを、ワイルドカード型テーブルにより出力インタフェースを決定する第２決定部に出力する。ここで、最初に第２決定部に出力されたパケットＡの出力インタフェースを第２決定部が決定し、その結果が完全一致型テーブルに反映されるまでに、パケットＢ、Ｃも第２決定部に出力されたものとする。

この場合、その後のパケットＤ、Ｅは、検索速度の速い完全一致型テーブルにより出力インタフェースが決定されるため、図６に示す様に、パケットＢ、ＣよりパケットＤ、Ｅが先に出力され、入力順序とは異なる順序で同一フローに属するパケットが出力されることが生じ得る。

本発明は、出力するインタフェースを決定するための時間が長くなることを防ぎつつ、同一フローに属するパケットを入力順序と同一順序で出力するパケット転送装置を提供するものである。

本発明の一側面によると、複数のインタフェースを有するパケット転送装置であって、フロー識別子とインタフェースの関係を示す第１情報と、フロー識別子の部分とインタフェースの関係を示す第２情報を保持する保持手段と、受信した第１パケットのヘッダ情報に基づき前記第１パケットのフロー識別子を判定する判定手段と、前記第１パケットのフロー識別子と前記第１情報に基づき前記第１パケットを出力するインタフェースを決定し、決定したインタフェースから前記第１パケットを出力させる第１決定手段と、前記第１決定手段が前記第１パケットを出力するインタフェースを決定できない場合、前記第１パケットのフロー識別子と前記第２情報に基づき前記第１パケットを出力するインタフェースを決定し、決定したインタフェースから前記第１パケットを出力させる第２決定手段と、前記第２決定手段が前記第１パケットを出力するインタフェースを決定した場合、前記第１パケットのフロー識別子と前記第２決定手段が決定したインタフェースとの関係を前記第１情報に追加する様に更新する更新手段と、を備えており、前記第１決定手段は、前記第１情報により前記第１パケットを出力するインタフェースを決定できない場合、前記第１パケットの受信後、前記更新手段が前記第１情報を更新するまでに受信した前記第１パケットと同じフロー識別子の第２パケットについては、前記第２決定手段に出力するインタフェースを決定させず、前記第２決定手段が前記第１パケットを出力するインタフェースを決定して出力させた後に、当該インタフェースから出力させることを特徴とする。

出力するインタフェースを決定するための時間が長くなることを防ぎつつ、同一フローに属するパケットを入力順序と同一順序で出力することができる。

一実施形態によるパケット転送装置の概略的な構成図。 一実施形態による完全一致型テーブルを示す図。 一実施形態によるワイルドカード型テーブルを示す図。 一実施形態による待機パケットテーブルを示す図。 一実施形態によるワイルドカード型テーブルを示す図。 パケット順序の入れ替わりの説明図。

以下、本発明の例示的な実施形態について図面を参照して説明する。なお、以下の各図においては、実施形態の説明に必要ではない構成要素については図から省略する。

図１は、本実施形態によるパケット転送装置の概略的な構成図である。パケット転送装置１は、複数のインタフェースを有し、各インタフェースで受信したパケットをバッファ部１０に保存する。フロー判定部１１は、受信パケットのヘッダ情報から当該受信パケットが属するフローのフロー識別子を判定し、判定したフロー識別子１１と、当該受信パケットのバッファ部１０での保存位置を第１決定部１２に出力する。本実施形態では、フロー識別子は、受信パケットが入力されたインタフェースと、受信パケットのヘッダ情報に含まれる送信元及び送信先ＭＡＣアドレス、送信元及び送信先ＩＰアドレス、送信元及び送信先ポート番号との組み合わせとする。なお、ＭＡＣアドレスとは、レイヤ２アドレスであり、ＩＰアドレスとはレイヤ３アドレスである。しかしながら、フロー識別子に使用する情報は、上記情報の一部であっても良い。さらに、上記情報の総て又は一部と、他の値、例えば、ＶＬＡＮ（仮想ローカル・エリア・ネットワーク）の識別子等を使用しても良い。

パケット転送装置の図示しない保持部は、完全一致型テーブル１６と、ワイルドカード型テーブル１７を保持している。なお、ワイルドカード型テーブル１７は、上述した様に、フロー識別子の部分と出力すべきインタフェースの関係を示すエントリを含むもの、つまり、フロー識別子の部分一致により出力すべきインタフェースを決定するための情報である。なお、ここでの部分一致とは、全く一致しない場合、つまり、ディフォルト経路を含むものとする。図３に本実施形態のワイルドカード型テーブル１７の例を示す。なお、図３において番号１のエントリはディフォルト経路である。例えば、インタフェース＃５で、送信元ＩＰアドレスが、（Ｘ１、Ｘ２、Ｘ３、Ｘ４）であり、送信先ＩＰアドレスが（Ｙ１、Ｙ２、Ｙ３、Ｙ４）のパケットを受信した場合、この受信パケットは、番号１、１００から１０３の５つのエントリに該当することになる。例えば、この５つのエントリの中で優先順位が一番高いものが番号１０２のエントリであると、この受信パケットは、インタフェースＩＦ＃３から出力される。なお、ワイルドカード型テーブル１７は、パケット転送装置の運用者が設定、或いは、フローの設定を示す他の装置からのシグナリングにより生成される。

一方、完全一致型テーブル１６は、フロー識別子と、出力すべきインタフェースとの関係を示すエントリを含むもの、つまり、フロー識別子の完全一致により出力すべきインタフェースを決定するための情報である。図２に本実施形態の完全一致型テーブル１６の例を示す。なお、本実施形態においては、一致するエントリの検索を高速化するために、フロー識別子そのものの値と、出力すべきインタフェースとの関係を示すのではなく、フロー識別子のハッシュ関数によるハッシュ値とインタフェースの関係を示すものとしている。つまり、完全一致型テーブル１６はハッシュ・テーブルである。なお、異なるフロー識別子が同じハッシュ値になることが確率的に存在するため、本実施形態においては、フロー識別子そのものの値も完全一致型テーブル１６に含め、検索後の確認に使用する。さらに、本実施形態において、完全一致型テーブル１６は、状態フィールドを有している。この状態フィールドは、"Ａ"、"Ｂ"、"Ｃ"の３つの値を有する。

なお、値"Ａ"は、フロー識別子とインタフェースの対応関係を完全一致型テーブル１６は有し、よって、完全一致型テーブル１６により当該フロー識別子が示すフローに属するパケットの出力インタフェースを決定できることを示している。また、値"Ｂ"は、フロー識別子とインタフェースの対応関係が完全一致型テーブル１６には含まれておらず、よって、完全一致型テーブル１６により当該フロー識別子が示すフローに属するパケットの出力インタフェースを決定できないことを示している。さらに、値"Ｃ"は、フロー識別子とインタフェースの対応関係が完全一致型テーブル１６には現在含まれていないが、当該フロー識別子とインタフェースの対応関係が完全一致型テーブル１６に追加されることを待っている状態であることを示している。例えば、図２の完全一致型テーブル１６においては、ハッシュ値がＨ２及びＨ１００であるフロー識別子の状態フィールドの値は"Ａ"であり、インタフェースＩＦ＃２及びＩＦ＃１が出力先であることが示されている。これに対して、その状態フィールドの値が"Ｂ"及び"Ｃ"である、ハッシュ値がＨ１及びＨ３であるフロー識別子については、その出力先が示されていない。なお、完全一致型テーブル１６へのエントリの追加、削除等の完全一致型テーブル１６の更新は、テーブル管理部１４が後述する様に行う。

第１決定部１２は、フロー判定部１１からフロー識別子等の情報を受け取ると、完全一致型テーブル１６の状態フィールドから、当該フロー識別子に対応する受信パケットの出力インタフェースを完全一致型テーブル１６により決定できるかを判定する。決定できる場合、つまり、当該フロー識別子に対応するエントリの状態フィールドが"Ａ"である場合、第１決定部１２は、当該フロー識別子に対応する受信パケットの出力インタフェースを完全一致型テーブル１６により決定し、決定した出力インタフェースと、受信パケットのバッファ部１０での保存位置を示す出力情報を読出部１５に出力する。これに対して、当該フロー識別子に対応するエントリの状態フィールドが"Ｂ"である場合、第１決定部１２は、フロー判定部１１から受け取ったフロー識別子等の情報を第２決定部１３に出力する。また、このとき、第１決定部１２は、状態フィールドが"Ｂ"であるフロー識別子を受け取ったことをテーブル管理部１４に通知し、テーブル管理部１４は、完全一致型テーブル１６の当該フロー識別子に対応するエントリの状態フィールドの値を"Ｃ"に変更する。

第２決定部１３は、第１決定部１２からフロー識別子等の情報を受け取ると、ワイルドカード型テーブル１７により、当該フロー識別子に対応する受信パケットの出力インタフェースを決定し、決定した出力インタフェースと、受信パケットのバッファ部１０での保存位置を示す出力情報を読出部１５に出力する。また、このとき、第２決定部１３は、テーブル管理部１４に、当該フロー識別子と決定した出力インタフェースとの関係を通知する。テーブル管理部１４は、第２決定部１３から通知されたフロー識別子に対応する、完全一致型テーブル１６のエントリの出力インタフェースのフィールドに、第２決定部１３から通知されたインタフェースを追加し、さらに、当該エントリの状態フィールドを"Ｃ"から"Ａ"に変更する。また、この更新を、第１決定部１２に通知する。

第１決定部１２は、フロー判定部１１から受け取ったフロー識別子に対応する、完全一致型テーブル１６のエントリの状態フィールドが"Ｃ"である場合、フロー判定部１１から受け取ったフロー識別子とバッファ部１０の保存位置を待機パケットテーブル１８として保存する。図４に待機パケットテーブル１８の例を示す。待機パケットテーブル１８は、フロー識別子毎に、対応するパケットのバッファ部１０への保存位置を、その受信順序と共に示すものである。なお、本実施形態においては、完全一致型テーブル１６と同様に、フロー識別子そのものの値ではなく、そのハッシュ値を使用する。例えば、図４においては、ハッシュ値がＨ１であるフロー識別子に属するパケットを、当該フロー識別子に対応する完全一致型テーブル１６のエントリの状態フィールドが"Ｃ"となった後に４つ受け取り、最初に受け取ったパケットがバッファ部１０の位置Ｐ１に、２番目に受け取ったパケットがバッファ部１０の位置Ｐ４に、３番目に受け取ったパケットがバッファ部１０の位置Ｐ８に、４番目に受け取ったパケットがバッファ部１０の位置Ｐ２０に保持されていることが示されている。

第１決定部１２は、テーブル管理部１４が完全一致型テーブル１６にフロー識別子に対応する出力インタフェースを追加すると、待機パケットテーブルの当該フロー識別子に対応するエントリに示されるパケットについて、その出力インタフェースと保存位置を含む出力情報を、その受信順に読出部１５に出力する。つまり、図４のハッシュ値Ｈ１に対応する完全一致型テーブル１６のエントリに、出力インタフェースが追加された場合、第１決定部１２は、保存位置Ｐ１、Ｐ４、Ｐ８、Ｐ２０の順で、その出力インタフェースを読出部１５に通知する。なお、第１決定部１２は、読出部１５に通知する出力インタフェースを、テーブル管理部１４又は第２決定部１３から受け取る。或いは、第１決定部１２が、完全一致型テーブル１６のテーブル管理部１４による更新後に、完全一致型テーブル１６を検索して取得しても良い。読出部１５は、第１決定部１２及び第２決定部１３からの出力情報に従い、バッファ部１０からパケットをその通知順に読み出して、出力情報で指定されるインタフェースに読み出したパケットを出力する。

以上、新規のフローに属するパケットが到達した場合、その最初のパケットのみが第２決定部１３により出力インタフェースの決定が行われ、その後に受信する当該フローに属するパケットについては、第２決定部１３が出力インタフェースを決定するまでバッファ部１０において保持される。また、その際、受信順序を示す情報として、待機パケットテーブル１８を作成して保持しておく。そして、これらバッファ部１０に保持されたパケットは、第２決定部１３が出力インタフェースを決定すると、その受信順序に従いバッファ部１０から読み出されて決定した出力インタフェースに送信される。さらに、それ以後の当該フローに属するパケットについては、第１決定部１２が出力インタフェースを決定する。よって、速度の遅い第２決定部１３による出力インタフェースの決定は、各フローの最初のパケットのみであり、それ以後のパケットについては、速度の速い第１決定部１２が出力インタフェースの決定を行うため、全体としての出力インタフェースの決定速度を短くできる。さらに、同じフローのパケットの出力順序が入力順序と異なることを防ぐことができる。本実施形態においては、第１決定部１２によるテーブルの検索処理と、第２決定部１３によるテーブルの検索処理を同期させる必要がなく、簡易な回路構成とすることができる。また、第２決定部１３が出力インタフェースを決定するまで、バッファ部１０に保持されるのは、第２決定部１３が出力インタフェースを決定しているフローに属するパケットのみであり、他のフローに属するパケットは影響を受けない。

なお、上記実施形態においては、完全一致型テーブル１６に状態フィールドを設けていたが、フロー識別子と状態フィールドとの関係を、完全一致型テーブル１６とは異なるテーブルにて管理することもできる。また、上記実施形態においては、バッファ部１０において一括して受信パケットをバッファリングし、第１決定部１２や、第２決定部１３にはフロー識別子及びバッファ部１０への保存位置のみを通知していたが、第１決定部１２や、第２決定部１３に実際のパケットを出力する形態であっても良い。さらに、完全一致型テーブル１６については、ハッシュ値ではなく、実際のフロー識別子と、出力インタフェースとの関係を示すものであっても良い。

Claims (6)

1. 複数のインタフェースを有するパケット転送装置であって、
   フロー識別子とインタフェースの関係を示す第１情報と、フロー識別子の部分とインタフェースの関係を示す第２情報を保持する保持手段と、
   受信した第１パケットのヘッダ情報に基づき前記第１パケットのフロー識別子を判定する判定手段と、
   前記第１パケットのフロー識別子と前記第１情報に基づき前記第１パケットを出力するインタフェースを決定し、決定したインタフェースから前記第１パケットを出力させる第１決定手段と、
   前記第１決定手段が前記第１パケットを出力するインタフェースを決定できない場合、前記第１パケットのフロー識別子と前記第２情報に基づき前記第１パケットを出力するインタフェースを決定し、決定したインタフェースから前記第１パケットを出力させる第２決定手段と、
   前記第２決定手段が前記第１パケットを出力するインタフェースを決定した場合、前記第１パケットのフロー識別子と前記第２決定手段が決定したインタフェースとの関係を前記第１情報に追加する様に更新する更新手段と、
   を備えており、
   前記第１決定手段は、前記第１情報により前記第１パケットを出力するインタフェースを決定できない場合、前記第１パケットの受信後、前記更新手段が前記第１情報を更新するまでに受信した前記第１パケットと同じフロー識別子の第２パケットについては、前記第２決定手段に出力するインタフェースを決定させず、前記第２決定手段が前記第１パケットを出力するインタフェースを決定して出力させた後に、当該インタフェースから出力させることを特徴とするパケット転送装置。
2. 前記保持手段は、フロー識別子について、当該フロー識別子とインタフェースの関係が前記第１情報に存在することを示す第１の値と、当該フロー識別子とインタフェースの関係が前記第１情報に存在しないことを示す第２の値と、当該フロー識別子とインタフェースの関係が前記第１情報に存在しないが、追加待ちであることを示す第３の値と、を少なくとも示す第３情報をさらに保持しており、
   前記第１決定手段は、前記第１パケットのフロー識別子に対する前記第３情報が前記第１の値を示す場合、前記受信したパケットを出力するインタフェースを決定し、
   前記第２決定手段は、前記第１パケットのフロー識別子に対する前記第３情報が前記第２の値を示す場合、前記受信したパケットを出力するインタフェースを決定し、
   前記更新手段は、前記第１パケットのフロー識別子に対する前記第３情報が前記第２の値を示す場合、当該第３情報を前記第３の値に更新し、前記第２決定手段が前記第１パケットを出力するインタフェースを決定すると、当該第３情報を前記第１の値に更新することを特徴とする請求項１に記載のパケット転送装置。
3. 前記第１情報は、フロー識別子のハッシュ値とインタフェースの関係を示すハッシュ・テーブルであり、前記第３情報は、前記ハッシュ・テーブルに含まれることを特徴とする請求項２に記載のパケット転送装置。
4. 前記第１決定手段は、前記第１情報により前記第１パケットを出力するインタフェースを決定できない場合、前記第２パケットの受信順序を示す第４情報を作成し、前記第２決定手段が前記第１パケットを出力するインタフェースを決定して出力させた後に、前記第４情報が示す受信順序と同じ順番で、前記第２パケットを当該インタフェースから出力させることを特徴とする請求項１から３のいずれか１項に記載のパケット転送装置。
5. 前記第４情報は、前記第２パケットのフロー識別子のハッシュ値に対して、前記第２パケットの受信順序とバッファへの保存位置とを示すハッシュ・テーブルであることを特徴とする請求項４に記載のパケット転送装置。
6. 請求項１から５のいずれか１項に記載のパケット転送装置としてコンピュータを機能させることを特徴とするプログラム。

Images