(57)【要約】  １個のＯＦＣ（ＯｐｅｎＦｌｏｗ  Ｃｏｎｔｒｏｌｌｅｒ）が複数のＯＦＳ（ＯｐｅｎＦｌｏｗ  Ｓｗｉｔｃｈ）を管理するネットワークが複数あり、それらの組み合わせにより大きなネットワークが形成されているオープンフローネットワークシステムにおいて、複数あるＯＦＣ同士が相互に連携する構成要素や処理手順を必要とせず、閉路を形成するようなフローエントリの登録を未然に防止する。具体的には、ＯＦＣは、経路計算後、その計算結果のフローエントリをＯＦＳのフローテーブルにテスト用のフローエントリとして仮登録する。その後、ＯＦＳは、この仮登録フローエントリに従ってテストパケットを流す。ＯＦＳは、テストパケットがループせずにルーティングされた場合にそれを検出し、初めて当該フローエントリを本登録する。ＯＦＳは、テストパケットがループした場合（閉路を形成した場合）にもそれを検出し、仮登録フローエントリを削除し、ＯＦＣに対しエラーを返す。
2012066830.tif 000002
【特許請求の範囲】
【請求項１】
パケットを受信し、フローテーブルに登録されたフローエントリに従って前記パケットを転送するスイッチと、
前記スイッチからの問い合わせに応じて、前記フローテーブルにフローエントリを登録するコントローラと
を含み、
前記スイッチは、
受信パケットがテストパケットか否かを確認する手段と、
前記受信パケットがテストパケットでない場合、前記フローテーブルの既存のフローエントリの中に、前記受信パケットにマッチするフローエントリがあるか否かを確認する手段と、
前記受信パケットにマッチするフローエントリがない場合、前記コントローラに問い合わせる手段と、
前記コントローラから仮登録されたフローエントリを基に、テストパケットを生成する手段と、
前記受信パケットを保留し、前記コントローラから仮登録されたフローエントリに従い、前記テストパケットを転送し、閉路形成を検出するためのテストを開始する手段と、
テストの結果、閉路形成を検出した場合、前記コントローラから仮登録されたフローエントリを破棄する手段と
を具備する
閉路形成未然防止システム。
【請求項２】
請求項１に記載の閉路形成未然防止システムであって、
前記コントローラは、
前記スイッチから問い合わせを受けた際、経路を計算する手段と、
テストを一意に識別可能なテストＩＤを生成する手段と、
前記スイッチに、経路計算結果に基づくフローエントリを仮登録する手段と
前記仮登録されるフローエントリの中に、アクションフィールドとテストＩＤフィールドとを設ける手段と、
前記アクションフィールドに、仮登録である旨の内容のデータを格納する手段と、
前記テストＩＤフィールドに、前記テストＩＤの値を格納する手段と
を具備する
閉路形成未然防止システム。
【請求項３】
請求項２に記載の閉路形成未然防止システムであって、
前記スイッチは、
テストパケットを生成する際、当該テストパケットに、基本ヘッダ部とテストデータ部とを設ける手段と、
前記基本ヘッダ部のサービスタイプフィールド及びプロトコルタイプフィールドに、テストパケットである旨を示す値を格納する手段と、
前記基本ヘッダ部の生存時間フィールドに、前記受信パケットに記されていた値を転記する手段と、
前記テストデータ部のテストＩＤフィールドに、前記コントローラから仮登録されたフローエントリに記載されているテストＩＤを格納する手段と、
前記テストデータ部のテスト成否フラグフィールドに、テスト未完のステータスであることを示す値を格納する手段と、
前記テストデータ部の通過ＯＦＳ情報フィールドに、前記スイッチのＭＡＣアドレス及びポート番号の値を格納する手段と
を更に具備する
閉路形成未然防止システム。
【請求項４】
請求項３に記載の閉路形成未然防止システムであって、
前記スイッチは、
前記受信パケットがテストパケットである場合、前記テストパケットのテスト成否フラグフィールドの値を参照する手段と、
前記テストパケットのテスト成否フラグフィールドに値がセットされていないか、値が０である場合、テスト処理中であると判断し、生存時間フィールドの値が０か否かを確認する手段と、
前記テストパケットの生存時間フィールドの値が０であった場合、パケットの生存期限切れであると判断し、テスト失敗と判断する手段と、
前記テストパケットの生存時間フィールドの値が０でない場合、前記フローテーブルの既存のフローエントリの中に、前記テストパケットにマッチするフローエントリがあるか否かを確認する手段と、
前記テストパケットにマッチするフローエントリがある場合、当該フローエントリのテストＩＤフィールドに、前記テストパケットのテストＩＤフィールドに記されている値と同一の値があるか否かを確認する手段と、
同一の値があった場合、閉路が形成されたと判断し、テスト失敗と判断する手段と、
同一の値がない場合、現段階では閉路は形成されていないと判断し、当該フローエントリの転送先がホストであるか否かを確認する手段と、
当該フローエントリの転送先がホストである場合、閉路を形成しておらずルーティングできると判断し、テスト成功と判断する手段と、
テスト結果を表す値を、前記テストパケットのテスト成否フラグフィールドに格納する手段と、
前記テストパケットの通過ＯＦＳ情報フィールドの末尾のＭＡＣアドレスを参照して、前記テストパケットを１つ前に経由したスイッチに転送し、テストを完了する手段と
を更に具備する
閉路形成未然防止システム。
【請求項５】
請求項４に記載の閉路形成未然防止システムであって、
前記スイッチは、
前記テストパケットにマッチするフローエントリがない場合、前記コントローラに問い合わせる手段と、
前記コントローラからフローエントリが仮登録された場合、或いは、前記テストパケットにマッチするフローエントリの転送先がホストでない場合、当該フローエントリのテストＩＤフィールドに、前記テストパケットのテストＩＤフィールドに記されている値を記入する手段と、
前記テストパケットの通過ＯＦＳ情報フィールドに、前記スイッチのＭＡＣアドレス及びポート番号の値を格納する手段と、
前記テストパケットの生存時間フィールドの値を１減算する手段と、
当該フローエントリに従い、前記テストパケットを転送し、テストを継続する手段と
を更に具備する
閉路形成未然防止システム。
【請求項６】
請求項４又は５に記載の閉路形成未然防止システムであって、
前記スイッチは、
前記テストパケットのテスト成否フラグフィールドに０以外の値がセットされている場合、前記テストパケットの通過ＯＦＳ情報フィールドの末尾から、前記スイッチのＭＡＣアドレスを削除する手段と、
前記フローテーブルに登録されているフローエントリの中から、前記テストパケットのテストＩＤフィールドに記されている値と同一の値がテストＩＤフィールドに記されているフローエントリを検索する手段と、
検出されたフローエントリのアクションフィールドを参照して、当該フローエントリが仮登録のフローエントリか本登録のフローエントリかを判断する手段と、
当該フローエントリが仮登録のフローエントリであった場合、前記テストパケットのテスト成否フラグを参照する手段と、
前記テストパケットのテスト成否フラグフィールドにテスト成功を表す値が入っている場合、当該フローエントリを本登録のフローエントリに更新する手段と、
前記テストパケットのテスト成否フラグフィールドにテスト失敗を表す値が入っている場合、当該フローエントリを削除する手段と、
当該フローエントリが本登録のフローエントリであった場合、テストの成否に関わらず、当該フローエントリのテストＩＤフィールドから、前記テストパケットのテストＩＤフィールドに記載されているテストＩＤの値を削除する手段と、
前記テストパケットの通過ＯＦＳ情報フィールドを参照し、１個以上のＭＡＣアドレスがあるか否かを確認する手段と、
前記テストパケットの通過ＯＦＳ情報フィールドに１個以上のＭＡＣアドレスがある場合は、前記テストパケットの通過ＯＦＳ情報フィールドの末尾のＭＡＣアドレスを持つスイッチに前記テストパケットを転送し、テストを継続する手段と、
前記テストパケットの通過ＯＦＳ情報フィールドに１個もＭＡＣアドレスがない場合、前記テストパケットの生成元のスイッチに戻ってきたと判断し、前記テストパケットのテスト成否フラグフィールドを参照して、テストの成否を確認する手段と、
テストが成功していた場合、前記保留していた受信パケットを、本登録のフローエントリに従って転送する手段と、
テストが失敗していた場合、前記保留していた受信パケットを破棄し、前記コントローラに対してエラーを返す手段と、
前記テストパケットを破棄し、テストを完了する手段と
を更に具備する
閉路形成未然防止システム。
【請求項７】
受信パケットがテストパケットか否かを確認する手段と、
前記受信パケットがテストパケットでない場合、フローテーブルの既存のフローエントリの中に、前記受信パケットにマッチするフローエントリがあるか否かを確認する手段と、
前記受信パケットにマッチするフローエントリがある場合、当該フローエントリに従って、前記受信パケットを転送する手段と、
前記受信パケットにマッチするフローエントリがない場合、コントローラに問い合わせる手段と、
前記コントローラから仮登録されたフローエントリを基に、テストパケットを生成する手段と、
前記受信パケットを保留し、前記コントローラから仮登録されたフローエントリに従い、前記テストパケットを転送し、閉路形成を検出するためのテストを開始する手段と、
テストの結果、閉路形成を検出した場合、前記コントローラから仮登録されたフローエントリを破棄する手段と
を具備する
スイッチ。
【請求項８】
フローテーブルに登録されたフローエントリに従ってパケットを転送するスイッチから受信パケットについての問い合わせを受けた際、経路を計算する手段と、
テストを一意に識別可能なテストＩＤを生成する手段と、
前記スイッチに、経路計算結果に基づくフローエントリを仮登録する手段と
前記仮登録されるフローエントリの中に、アクションフィールドとテストＩＤフィールドとを設ける手段と、
前記アクションフィールドに、仮登録である旨の内容のデータを格納する手段と、
前記テストＩＤフィールドに、前記テストＩＤの値を格納する手段と
を具備する
コントローラ。
【請求項９】
スイッチにより実施される閉路形成未然防止方法であって、
受信パケットがテストパケットか否かを確認することと、
前記受信パケットがテストパケットでない場合、前記フローテーブルの既存のフローエントリの中に、前記受信パケットにマッチするフローエントリがあるか否かを確認することと、
前記受信パケットにマッチするフローエントリがある場合、当該フローエントリに従って、前記受信パケットを転送することと、
前記受信パケットにマッチするフローエントリがない場合、コントローラに問い合わせることと、
前記コントローラから仮登録されたフローエントリを基に、テストパケットを生成することと、
前記受信パケットを保留し、前記コントローラから仮登録されたフローエントリに従い、前記テストパケットを転送し、閉路形成を検出するためのテストを開始することと、
テストの結果、閉路形成を検出した場合、前記コントローラから仮登録されたフローエントリを破棄することと
を含む
閉路形成未然防止方法。
【請求項１０】
受信パケットがテストパケットか否かを確認するステップと、
前記受信パケットがテストパケットでない場合、フローテーブルの既存のフローエントリの中に、前記受信パケットにマッチするフローエントリがあるか否かを確認するステップと、
前記受信パケットにマッチするフローエントリがある場合、当該フローエントリに従って、前記受信パケットを転送するステップと、
前記受信パケットにマッチするフローエントリがない場合、前記コントローラに問い合わせるステップと、
前記コントローラから仮登録されたフローエントリを基に、テストパケットを生成するステップと、
前記受信パケットを保留し、前記コントローラから仮登録されたフローエントリに従い、前記テストパケットを転送し、閉路形成を検出するためのテストを開始するステップと、
テストの結果、閉路形成を検出した場合、前記コントローラから仮登録されたフローエントリを破棄するステップと
をスイッチに実行させるためのプログラムを格納するための
記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、閉路形成未然防止システムに関し、特にオープンフロー（ＯｐｅｎＦｌｏｗ）ネットワークにおける閉路形成未然防止システムに関する。
【背景技術】
【０００２】
ネットワーク通信の経路制御方式の１つとして、通信機器の制御プロトコルであるオープンフロー（ＯｐｅｎＦｌｏｗ）技術を使用した経路制御方式が研究されている。オープンフロー技術による経路制御が行われるネットワークを、オープンフローネットワークと呼ぶ。【０００３】
オープンフローネットワークでは、ＯＦＣ（ＯｐｅｎＦｌｏｗ  Ｃｏｎｔｒｏｌｌｅｒ）等のコントローラが、ＯＦＳ（ＯｐｅｎＦｌｏｗ  Ｓｗｉｔｃｈ）等のスイッチのオープンフローテーブル（ＯｐｅｎＦｌｏｗ  Ｔａｂｌｅ）を操作することによりスイッチの挙動を制御する。コントローラとスイッチの間は、コントローラがオープンフロープロトコルに準拠した制御メッセージを用いてスイッチを制御するためのセキュアチャネル（Ｓｅｃｕｒｅ  Ｃｈａｎｎｅｌ）により接続されている。【０００４】
オープンフローネットワークにおけるスイッチとは、オープンフローネットワークを形成し、コントローラの制御下にあるエッジスイッチ及びコアスイッチのことである。オープンフローネットワークにおける入力側エッジスイッチでのパケット（通信データ）の受信から出力側エッジスイッチでの送信までのパケットの一連の流れをフロー（Ｆｌｏｗ）と呼ぶ。【０００５】
オープンフローテーブルとは、所定のルール（マッチ条件）に適合するパケット群（パケット系列）に対して行うべき所定のアクション（処理内容）を定義したフローエントリ（Ｆｌｏｗ  ｅｎｔｒｙ）が登録されたテーブルである。【０００６】
フローエントリのルールは、パケットの各プロトコル階層のヘッダ（ｈｅａｄｅｒ）領域に含まれる宛先アドレス（Ｄｅｓｔｉｎａｔｉｏｎ  Ａｄｄｒｅｓｓ）、送信元アドレス（Ｓｏｕｒｃｅ  Ａｄｄｒｅｓｓ）、宛先ポート（Ｄｅｓｔｉｎａｔｉｏｎ  Ｐｏｒｔ）、送信元ポート（Ｓｏｕｒｃｅ  Ｐｏｒｔ）のいずれか又は全てを用いた様々な組合せにより定義され、区別可能である。なお、上記のアドレスには、ＭＡＣアドレス（Ｍｅｄｉａ  Ａｃｃｅｓｓ  Ｃｏｎｔｒｏｌ  Ａｄｄｒｅｓｓ）やＩＰアドレス（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ  Ａｄｄｒｅｓｓ）を含むものとする。また、上記に加えて、入口ポート（Ｉｎｇｒｅｓｓ  Ｐｏｒｔ）の情報も、フローエントリのルールとして使用可能である。【０００７】
フローエントリのアクションは、「特定のポートに出力する」、「廃棄する」、「ヘッダを書き換える」といった動作を示す。例えば、スイッチは、フローエントリのアクションに出力ポートの識別情報（出力ポート番号等）が示されていれば、これに該当するポートにパケットを出力し、出力ポートの識別情報が示されていなければ、パケットを破棄する。或いは、スイッチは、フローエントリのアクションにヘッダ情報が示されていれば、当該ヘッダ情報に基づいてパケットのヘッダを書き換える。【０００８】
オープンフローネットワークにおけるスイッチは、フローエントリのルールに適合するパケット群に対して、フローエントリのアクションを実行する。【０００９】
オープンフロー技術の詳細については、非特許文献１、２に記載されている。【００１０】
現在のところ、オープンフロー技術は、研究段階から実用段階への過渡期にある。このような状況においては、既存のレガシーネットワークを一括してオープンフローネットワークに置き換えることは余りない。大半の事例（ケース）において、既存ネットワークの一部をオープンフロー対応のものに置き換え、小規模環境にてパイロットテストを行うのが通常である。【００１１】
また、このようなパイロットテストには大きな予算は投入されず、限られた予算で実施されるのが普通である。このような状況において、既存技術の「単一コントローラ方式」では新たなＯＦＣを一台用意する必要があり、コスト上の障害となっていた。【００１２】
また、パイロットテストの段階では、多種多様なベンダからＯＦＣやＯＦＳを調達して、ベンチマークをとるのが普通である。しかしながら、既存技術の「経路計算装置連携方式」では、経路計算装置の通信規格が現時点で統一されていないため、そもそも多種多様なベンダの製品が混在するネットワークを構築できないという障害があった。【００１３】
また、一方で、現状におけるオープンフローネットワーク環境（オープンフローネットワークシステム）は、パイロットテスト目的の小規模環境が大半であることから、大規模環境で生じうる問題に対し、十分な考慮がされていない状況でもある。【００１４】
このような状況から、新規の装置を必要とせず、また、各種ベンダのＯＦＣ／ＯＦＳが混在可能で、大規模ネットワークとなっても軽量な処理で、閉路（ループ）の形成を未然防止する手法が望まれていた。【００１５】
［ネットワークの構成例］
従来の課題を説明するに当たり、まず、図１を用いて、オープンフローネットワークシステムの構成例について説明する。【００１６】
図１に示されたオープンフローネットワークシステムでは、１個のＯＦＣが複数のＯＦＳを管理する小規模ネットワークが複数あり、それらの組み合わせにより、大規模ネットワークが形成されている。【００１７】
当該オープンフローネットワークシステムは、ホスト（ｈｏｓｔ  ｃｏｍｐｕｔｅｒ）１０（１０−ｉ、ｉ＝１〜ｘ：ｘは総台数）と、ＯＦＳ１１（１１−ｊ、ｊ＝１〜ｙ：ｙは総台数）と、ＯＦＣ１２（１２−ｋ、ｋ＝１〜ｚ：ｚは総台数）を含む。【００１８】
小規模ネットワークでは、１個のＯＦＣ１２が複数のＯＦＳ１１を管理している。小規模ネットワークの各々は、最上位のＯＦＳ１１を介して、他の小規模ネットワークと接続し、大規模ネットワークを形成する。【００１９】
ホスト１０−１、ホスト１０−２、ホスト１０−３、及びホスト１０−４は、それぞれＯＦＳ１１−２及びＯＦＳ１１−３にＬＡＮケーブル等の通信回線で接続されている。ＯＦＳ１１−２及びＯＦＳ１１−３は、それぞれＬＡＮケーブル等の通信回線でＯＦＳ１１−１に接続されている。ＯＦＣ１２−１は、ＯＦＳ１１−１、ＯＦＳ１１−２、及びＯＦＳ１１−３に対する経路計算やフローエントリ登録等の管理を行うものとする。同様に、ホスト１０−５、ホスト１０−６、ホスト１０−７、及びホスト１０−８は、それぞれＯＦＳ１１−５及びＯＦＳ１１−６にＬＡＮケーブル等の通信回線で接続されている。ＯＦＳ１１−５、ＯＦＳ１１−６は、それぞれＬＡＮケーブル等の通信回線でＯＦＳ１１−４に接続されている。ＯＦＣ１２−２は、ＯＦＳ１１−４、ＯＦＳ１１−５、及びＯＦＳ１１−６に対する経路計算やフローエントリ登録等の管理を行うものとする。同様に、ホスト１０−９、ホスト１０−１０、ホスト１０−１１、及びホスト１０−１２は、それぞれＯＦＳ１１−８及びＯＦＳ１１−９にＬＡＮケーブル等の通信回線で接続されている。ＯＦＳ１１−８及びＯＦＳ１１−９は、それぞれＬＡＮケーブル等の通信回線でＯＦＳ１１−７に接続されている。ＯＦＣ１２−３は、ＯＦＳ１１−７、ＯＦＳ１１−８、及びＯＦＳ１１−９に対する経路計算やフローエントリ登録等の管理を行うものとする。ＯＦＳ１１−１、ＯＦＳ１１−４、及びＯＦＳ１１−７は、ＬＡＮケーブル等により接続されている。【００２０】
本構成において、ＯＦＣ１２−１とＯＦＣ１２−２とＯＦＣ１２−３は、相互に情報をやり取りする構成要素や処理手順を持たない。すなわち、例えば、ＯＦＣ１２−３が、ＯＦＳ１１−７にどのようなフローエントリを登録したのかを、ＯＦＣ１２−１とＯＦＣ１２−２が検知する構成要素や処理手順はないということである。【００２１】
［フローエントリの形式］
ＯＦＳ１２（１２−ｊ、ｊ＝１〜ｙ）の各々には、図２で示される形式のフローエントリが複数登録されている。【００２２】
［従来のフローエントリの形式］
図２に示すように、フローエントリは、大きく、「ルール」フィールド（領域）、「アクション」フィールド、「統計情報」フィールドの３つのフィールドを有する。【００２３】
「ルール」フィールドには、パケット種別、パケット送信元ホストアドレス、パケット送信先ホストアドレス等のルール（マッチ条件）が記される。パケット種別のフィールドには、「ＩＰｖ４」（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ  ｖｅｒｓｉｏｎ  ４）や「ＩＰｖ６」（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ  ｖｅｒｓｉｏｎ  ６）等の情報が記される。【００２４】
「アクション」フィールドには、「破棄」や「ＯＦＳ１２−ｎ（ｎは任意）に転送」等、ルールに合致するパケットを受け取った際にどのように処理するかを示すアクション（処理内容）が記される。【００２５】
「統計情報」フィールドには、処理したパケットの累計数等の統計情報が記される。【００２６】
第１の例として、あるＯＦＳにおいて、「ルール」フィールドに発信元として「１９２．１６８．１０．＊」、アクションとして「破棄」と記されたフローエントリがフローテーブルに登録されている場合を考える。なお、「＊」は、ワイルドカード（ｗｉｌｄ  ｃａｒｄ）であり、任意の長さの任意の文字（０文字以上の文字列）を意味する。すなわち、「＊」の部分は、何でも良い。この場合、受信パケットの送信元ＩＰアドレスの先頭に「１９２．１６８．１０」の部分が含まれていれば、当該受信パケットは、当該フローエントリとマッチすることになる。当該ＯＦＳに、「１９２．１６８．１０．３４」からのパケットが到着した場合、そのパケットは、当該フローエントリにマッチし、破棄処理が行われる。【００２７】
第２の例として、あるＯＦＳにおいて、「ルール」フィールドに発信元として「＊．＊．＊．＊」、発信先として「１９２．１６８．２０．＊」、アクションとして「ＯＦＳ１２−ｎに転送「と記されたフローエントリがフローテーブルに登録されている場合を考える。当該ＯＦＳに「１９２．１６８．１０．２３」から「１９２．１６８．２０．２５」宛に発行されたパケットが到着した場合、当該フローエントリにマッチし、ＯＦＳ１２−ｎに宛てて転送処理が行われる。なお、当該ＯＦＳは、フローテーブルに登録されているフローエントリのいずれにもマッチしないパケットを受け取った場合、ＯＦＣに対し、フローエントリの登録を求める。ＯＦＣは、適宜、効率的な経路の計算等をして、当該パケットをどのようにルーティングするかを定義したフローエントリを当該ＯＦＳに登録する。当該ＯＦＳは、このフローエントリに従って受け取ったパケットを処理する。【００２８】
［閉路の構成］
次に、図３を用いて、図１のようなネットワーク構成においては閉路が構成され得ることについて説明する。【００２９】
図３に示すネットワークは、ホスト２０（２０−ｉ、ｉ＝１〜ｘ）と、ＯＦＳ２１（２１−ｊ、ｊ＝１〜ｙ）と、ＯＦＣ２２（２２−ｋ、ｋ＝１〜ｚ）を含む。【００３０】
ホスト２０（２０−ｉ、ｉ＝１〜ｘ）は、図１のホスト１０（１０−ｉ、ｉ＝１〜ｘ）に相当する。ＯＦＳ２１（２１−ｊ、ｊ＝１〜ｙ）は、図１のＯＦＳ１１（１１−ｊ、ｊ＝１〜ｙ）に相当する。ＯＦＣ２２（２２−ｋ、ｋ＝１〜ｚ）は、図１のＯＦＣ１１（１１−ｋ、ｋ＝１〜ｚ）に相当する。ホスト２０（２０−ｉ、ｉ＝１〜ｘ）、ＯＦＳ２１（２１−ｊ、ｊ＝１〜ｙ）、及びＯＦＣ２２（２２−ｋ、ｋ＝１〜ｚ）は、ネットワーク２００（２００−ｌ、ｌ＝１〜ｗ：ｗは小規模ネットワークの総数）に属する。ホスト２０−１及びＯＦＳ２１−１及びＯＦＣ２２−１は、ネットワーク２００−１に属するものとする。ＯＦＳ２１−２、ＯＦＣ２２−２、ホスト２０−４、ホスト２０−５、ＯＦＳ２１−４、及びＯＦＣ２２−４は、ネットワーク２００−２に属するものとする。ホスト２０−２及びホスト２０−３及びＯＦＳ２１−３及びＯＦＣ２２−３は、ネットワーク２００−３に属するものとする。ホスト２０−６及びＯＦＳ２１−５及びＯＦＣ２２−５は、ネットワーク２００−４に属するものとする。【００３１】
ネットワーク２００−１には、「１９２．１６８．１．０」なるネットワークアドレスが与えられているものとする。ネットワーク２００−２には、「１９２．１６８．２．０」なるネットワークアドレスが与えられているものとする。ネットワーク２００−３には、「１９２．１６８．３．０」なるネットワークアドレスが与えられているものとする。ネットワーク２００−４には、「１９２．１６８．４．０」なるネットワークアドレスが与えられているものとする。ホスト２０−１には、「１９２．１６８．１．５」なるアドレスが与えられているものとする。ホスト２０−２には、「１９２．１６８．３．１０」なるアドレスが与えられているものとする。ホスト２０−３には、「１９２．１６８．３．２１」なるアドレスが与えられているものとする。ホスト２０−６には、「１９２．１６８．４．８」なるアドレスが与えられているものとする。また、ＯＦＳ２１−１には、「１９２．１６８．１．＊宛のパケットは、ホストに転送。他のアドレス宛のパケットは、ＯＦＳ２１−２に転送。」という旨のフローエントリがフローテーブルに登録されているものとする。ＯＦＳ２１−２には、「１９２．１６８．２．＊宛のパケットは、ホストに転送。他のアドレス宛のパケットは、ＯＦＳ２１−３に転送。」という旨のフローエントリがフローテーブルに登録されているものとする。ＯＦＳ２１−３には、「１９２．１６８．３．＊宛のパケットは、ホストに転送。」という旨のフローエントリがフローテーブルに登録されているものとする。ＯＦＳ２１−４には、「１９２．１６８．２．＊宛のパケットは、ホストに転送。他のアドレス宛のパケットは、ＯＦＳ２１−５に転送。」という旨のフローエントリがフローテーブルに登録されているものとする。ＯＦＳ２１−５には、「１９２．１６８．４．＊宛のパケットは、ホストに転送。」という旨のフローエントリがフローテーブルに登録されているものとする。【００３２】
この場合、ホスト２０−１は、ホスト２０−２宛のパケットを発行すると、まずＯＦＳ２１−１に送信する。ＯＦＳ２１−１は、フローエントリに従い、ホスト２０−２宛のパケットをＯＦＳ２１−２に転送する。ＯＦＳ２１−２は、フローエントリに従い、ホスト２０−２宛のパケットをＯＦＳ２１−３に転送する。ＯＦＳ２１−３は、フローエントリに従い、ホスト２０−２宛のパケットをホスト２０−２に転送する。これにより、ホスト２０−２宛のパケットは、目的のホストに到着する。すなわち、ホスト２０−１からホスト２０−２宛のパケットについては、ＯＦＳ２１−１、ＯＦＳ２１−２、及びＯＦＳ２１−３を経由する経路（ルート）が確立している。【００３３】
また、ホスト２０−４或いはホスト２０−５は、ホスト２０−６宛のパケットを発行すると、まずＯＦＳ２１−４に送信する。ＯＦＳ２１−４は、フローエントリに従い、ホスト２０−６宛のパケットをＯＦＳ２１−５に転送する。ＯＦＳ２１−５は、フローエントリに従い、ホスト２０−６宛のパケットをホスト２０−６に転送する。すなわち、ホスト２０−４或いはホスト２０−５からホスト２０−６宛のパケットについては、ＯＦＳ２１−４、ＯＦＳ２１−５を経由する経路が確立している。【００３４】
このような場合に、ホスト２０−３から発行されたホスト２０−６宛のパケットについて、どのようにルーティングされるかを考える。ホスト２０−３は、ホスト２０−６宛のパケットを発行すると、まずＯＦＳ２１−３に送信する。しかし、ＯＦＳ２１−３には、受け取ったパケットにマッチするフローエントリが登録されていない。【００３５】
したがって、ＯＦＳ２１−３は、当該パケットの処遇について、ＯＦＣ２２−３に問い合わせることとなる。しかし、ＯＦＣ２２−３は、他のＯＦＣがそれぞれの管理するＯＦＳに対してどのようにフローエントリを設定したのかを検知する構成要素や処理手順を持たない。【００３６】
仮に、ＯＦＣ２２−３は、経路計算ルーチンに従い、経路を計算した結果を基に、当該パケットをＯＦＳ２１−４に転送するのが妥当であるとした場合、ＯＦＳ２１−３に対しては、例えば、「１９２．１６８．３．＊宛のパケットは、ホストに転送。他のアドレス宛のパケットは、ＯＦＳ２１−４に転送。」という旨のフローエントリを新規に登録することになる。この場合、「ＯＦＳ２１−３→ＯＦＳ２１−４」の経路２４−１が確立する。ＯＦＣ２２−３は、当該パケットをＯＦＳ２１−４に転送する。ＯＦＳ２１−４は、ＯＦＳ２１−５を経由して、当該パケットをホスト２０−６に転送する。【００３７】
一方で、仮に、ＯＦＣ２２−３は、経路計算ルーチンに従い、経路を計算した結果を基に、当該パケットをＯＦＳ２１−１に転送するのが妥当であるとした場合は、ＯＦＳ２１−３に対し、例えば、「１９２．１６８．３．＊宛のパケットは、ホストに転送。他のアドレス宛のパケットは、ＯＦＳ２１−１に転送。」という旨のフローエントリを新規に登録することになる。この場合、「ＯＦＳ２１−３→ＯＦＳ２１−１」の経路２４−２が確立する。ＯＦＣ２２−３は、当該パケットをＯＦＳ２１−１に転送する。ＯＦＳ２１−１は、当該パケットが既存のフローエントリにマッチするため、当該パケットをＯＦＳ２１−２に転送する。ＯＦＳ２１−２も、当該パケットが既存のフローエントリにマッチするため、当該パケットをＯＦＳ２１−３に転送する。ＯＦＳ２１−３は、当該パケットが新規に登録されたフローエントリにマッチするため、当該パケットをＯＦＳ２１−１に転送する。このように、「ＯＦＳ２１−１→ＯＦＳ２１−２→ＯＦＳ２１−３→ＯＦＳ２１−１」の閉路２５−１が形成されたため、目的のホストには到着しない。【００３８】
以上より、他のＯＦＣが管理するＯＦＳにパケットを転送する場合に、当該ＯＦＳの先でどのようなフローエントリが既に登録されているのかを検知する構成要素や処理手順がない場合、閉路が形成される可能性がある。【００３９】
［閉路の種類］
なお、閉路の種類としては、図４Ａに示すパターンと、図４Ｂに示すパターンとの２種類が考えられる。図４Ａ、図４Ｂに示すホスト３０（３０−ｉ、ｉ＝１〜ｘ）は、図１のホスト１０（１０−ｉ、ｉ＝１〜ｘ）に相当する。図４Ａ、図４Ｂに示すＯＦＳ３１（３１−ｊ、ｊ＝１〜ｙ）は、図１のＯＦＳ１１（１１−ｊ、ｊ＝１〜ｙ）に相当する。【００４０】
［パターン１］
図４Ａに示すパターンでは、ホスト３０−１からパケットを受けたＯＦＳ３１−１において、当該パケットが新規に登録されたフローエントリにマッチし、新規に登録されたフローエントリに従って転送された結果、ＯＦＳ３１−２に到着する。ＯＦＳ３１−２及びＯＦＳ３１−３において、当該パケットが既存のフローエントリにマッチし、既存のフローエントリに従って転送された結果、ＯＦＳ３１−２及びＯＦＳ３１−３を経てＯＦＳ３１−１に戻ってくるため、ＯＦＳ３１−１、ＯＦＳ３１−２、及びＯＦＳ３１−３の間で閉路が形成されてしまう。【００４１】
［パターン２］
図４Ｂに示すパターンでは、ホスト３０−２からパケットを受けたＯＦＳ３１−４において、当該パケットが新規に登録されたフローエントリにマッチし、新規に登録されたフローエントリに従って転送された結果、ＯＦＳ３１−４及びＯＦＳ３１−５を経てＯＦＳ３１−６に到着する。ＯＦＳ３１−６、ＯＦＳ３１−７、及びＯＦＳ３１−８において、当該パケットが既存のフローエントリにマッチし、既存のフローエントリに従って転送された結果、ＯＦＳ３１−７及びＯＦＳ３１−８を経てＯＦＳ３１−６に戻ってくるため、ＯＦＳ３１−６、ＯＦＳ３１−７、及びＯＦＳ３１−８の間で閉路が形成されてしまう。【００４２】
［閉路形成への従来対応］
このような閉路形成問題に対し、従来は、図５に示す「単一コントローラ方式」や、図６に示す「経路計算装置連携方式」が提案され実装されてきた。【００４３】
［単一コントローラ方式］
図５に示す「単一コントローラ方式」は、図１の各要素に加え、ＯＦＣ１２−１、ＯＦＣ１２−２、及びＯＦＣ１２−３を統括するＯＦＣ１２−４を追加する構成である。この構成では、例えば、ＯＦＣ１２−１は、パケットの経路を計算するに当たって、ＯＦＣ１２−４に問い合わせる。ＯＦＣ１２−４は、ＯＦＣ１２−３やＯＦＣ１２−４が既に設定した経路を加味し、閉路を形成しないようなフローエントリをＯＦＣ１２−２に伝える。しかし、「単一コントローラ方式」の欠点として、ネットワーク規模が大きくなった場合に、各ＯＦＣが設定したフローエントリの情報量や、経路導出の際に計算が必要となる組み合わせの量が膨大となり、ＯＦＣ１２−４での負荷が高くなるという課題があった。【００４４】
［経路計算装置連携方式］
図６に示す「経路計算装置連携方式」は、図１の各要素に加え、ＯＦＣ１２−１上で動作する経路計算部１２１−１、及びＯＦＣ１２−２上で動作する経路計算部１２１−２、及びＯＦＣ１２−３上で動作する経路計算部１２１−３が、相互に設定済みフローエントリの情報をやり取りし、経路計算に活用可能とする仕組みを追加する構成である。この構成では、例えば、ＯＦＣ１２−１は、パケットの経路を計算するに当たって、ＯＦＣ１２−２及びＯＦＣ１２−３に対して、関係するフローエントリの情報を問い合わせる。しかし、「経路計算装置連携方式」においても、ネットワーク規模が大きくなった場合に、通信するＯＦＣの数や、それぞれのＯＦＣから受け取る経路情報の数が膨大となる。また、それらを組み合わせての計算が必要となるため、ＯＦＣ１２−１での負荷が高くなるという課題があった。
【先行技術文献】
【非特許文献】
【００４５】
【非特許文献１】“ＴｈｅＯｐｅｎＦｌｏｗＳｗｉｔｃｈＣｏｎｓｏｒｔｉｕｍ”，［ｏｎｌｉｎｅ］，インターネット（ＵＲＬ：ｈｔｔｐ：／／ｗｗｗ．ｏｐｅｎｆｌｏｗｓｗｉｔｃｈ．ｏｒｇ／）
【非特許文献２】“ＯｐｅｎＦｌｏｗ  Ｓｗｉｔｃｈ  Ｓｐｅｃｉｆｉｃａｔｉｏｎ，  Ｖｅｒｓｉｏｎ  １．０．０”，［ｏｎｌｉｎｅ］，Ｄｅｃｅｍｂｅｒ  ３１，２００９，インターネット（ＵＲＬ：ｈｔｔｐ：／／ｗｗｗ．ｏｐｅｎｆｌｏｗｓｗｉｔｃｈ．ｏｒｇ／ｄｏｃｕｍｅｎｔｓ／ｏｐｅｎｆｌｏｗ−ｓｐｅｃ−ｖ１．０．０．ｐｄｆ）
【発明の概要】
【００４６】
本発明の目的は、オープンフロー（ＯｐｅｎＦｌｏｗ）ネットワークにおいて、テストパケットにより、事前に閉路の形成をチェックし、その結果をフローエントリ登録に反映する閉路形成未然防止システムを提供することである。
【００４７】
本発明に係る閉路形成未然防止システムは、パケットを発行するホストと、パケットを受信し、フローテーブルに登録されたフローエントリに従ってパケットを転送するスイッチと、スイッチからの問い合わせに応じて、フローテーブルにフローエントリを登録するコントローラとを含む。スイッチは、受信パケットがテストパケットか否かを確認（チェック）する処理部と、受信パケットがテストパケットでない場合、フローテーブルの既存のフローエントリの中に、受信パケットにマッチするフローエントリがあるか否かを確認する処理部と、受信パケットにマッチするフローエントリがない場合、コントローラに問い合わせる処理部と、コントローラから仮登録されたフローエントリを基に、テストパケットを生成する処理部と、受信パケットを保留し、コントローラから仮登録されたフローエントリに従い、テストパケットを転送し、閉路形成を検出するためのテストを開始する処理部と、テストの結果、閉路形成を検出した場合、コントローラから仮登録されたフローエントリを破棄する処理部とを具備する。
【００４８】
本発明に係る閉路形成未然防止方法は、フローテーブルに登録されたフローエントリに従ってパケットを転送するスイッチにより実施される。本発明に係る閉路形成未然防止方法では、受信パケットがテストパケットか否かを確認する。受信パケットがテストパケットでない場合、フローテーブルの既存のフローエントリの中に、受信パケットにマッチするフローエントリがあるか否かを確認する。受信パケットにマッチするフローエントリがない場合、コントローラに問い合わせる。コントローラから仮登録されたフローエントリを基に、テストパケットを生成する。受信パケットを保留し、コントローラから仮登録されたフローエントリに従い、テストパケットを転送し、閉路形成を検出するためのテストを開始する。テストの結果、閉路形成を検出した場合、コントローラから仮登録されたフローエントリを破棄する。
【００４９】
本発明に係るプログラムは、受信パケットがテストパケットか否かを確認するステップと、受信パケットがテストパケットでない場合、フローテーブルに登録された既存のフローエントリの中に、受信パケットにマッチするフローエントリがあるか否かを確認するステップと、受信パケットにマッチするフローエントリがある場合、当該フローエントリに従って、受信パケットを転送するステップと、受信パケットにマッチするフローエントリがない場合、コントローラに問い合わせるステップと、コントローラから仮登録されたフローエントリを基に、テストパケットを生成するステップと、受信パケットを保留し、コントローラから仮登録されたフローエントリに従い、テストパケットを転送し、閉路形成を検出するためのテストを開始するステップと、テストの結果、閉路形成を検出した場合、コントローラから仮登録されたフローエントリを破棄するステップとをスイッチに実行させるためのプログラムである。なお、本発明に係るプログラムは、記憶装置や記憶媒体に格納することが可能である。
【００５０】
本発明では、ＯＦＣ等のコントローラ同士が連携することを必要とせず、閉路の形成を未然に防止できる。
【図面の簡単な説明】
【００５１】
【図１】オープンフローネットワークシステムの構成例を示す図である。
【図２】従来のフローエントリの形式を説明するための図である。
【図３】オープンフローネットワークシステムの構成において閉路が構成され得る状況を説明するための図である。
【図４Ａ】閉路のパターン１を示す図である。
【図４Ｂ】閉路のパターン２を示す図である。
【図５】従来の単一コントローラ方式を説明するための図である。
【図６】従来の経路計算装置連携方式を説明するための図である。
【図７】本発明におけるフローエントリの形式を説明するための図である。
【図８】本発明におけるテストパケットの形式を説明するための図である。
【図９】本発明におけるテスト、成否判断、結果反映を説明するための図である。
【図１０Ａ】ＯＦＳの処理ルーチンを説明するためのフローチャートである。
【図１０Ｂ】ＯＦＳの処理ルーチンを説明するためのフローチャートである。
【図１０Ｃ】ＯＦＳの処理ルーチンを説明するためのフローチャートである。
【図１１】ＯＦＳの内部構成例を示す図である。
【図１２】ＯＦＳの内部構成の1つであるテストパケット生成部の詳細を説明するための図である。
【図１３】ＯＦＳの内部構成の1つであるテスト実行部の詳細を説明するための図である。
【発明を実施するための形態】
【００５２】
以下に、本発明の実施形態について添付図面を参照して説明する。
本発明は、図１に示すようなオープンフローネットワークシステムを対象としている。
【００５３】
図１に示されたオープンフローネットワークシステムでは、１個のＯＦＣが複数のＯＦＳを管理する小規模ネットワークが複数あり、それらの組み合わせにより、大規模ネットワークが形成されている。
【００５４】
当該オープンフローネットワークシステムは、ホスト１０（１０−ｉ、ｉ＝１〜ｘ：ｘは総台数）と、ＯＦＳ１１（１１−ｊ、ｊ＝１〜ｙ：ｙは総台数）と、ＯＦＣ１２（１２−ｋ、ｋ＝１〜ｚ：ｚは総台数）を含む。
【００５５】
小規模ネットワークでは、１個のＯＦＣ１２が複数のＯＦＳ１１を管理している。小規模ネットワークの各々は、最上位のＯＦＳ１１を介して、他の小規模ネットワークと接続し、大規模ネットワークを形成する。
【００５６】
［本発明におけるフローエントリの形式］
図７は、本発明で用いるフローエントリの形式である。本発明におけるフローエントリは、図２のフローエントリを拡張し、「テストＩＤ」フィールドを追加したものである。
【００５７】
図７に示すように、本発明におけるフローエントリは、大きく、「ルール」フィールド、「アクション」フィールド、「統計情報」フィールド、「テストＩＤ」フィールドの４つのフィールドを有する。
【００５８】
「ルール」フィールドには、パケット種別、パケット送信元ホストアドレス、パケット送信先ホストアドレス等のルール（マッチ条件）が記される。パケット種別のフィールドには、「ＩＰｖ４」（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ  ｖｅｒｓｉｏｎ  ４）や「ＩＰｖ６」（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ  ｖｅｒｓｉｏｎ  ６）等の情報が記される。
【００５９】
「アクション」フィールドには、「破棄」や「ＯＦＳ１２−ｎ（ｎは任意）に転送」等、ルールに合致するパケットを受け取った際にどのように処理するかを示すアクション（処理内容）が記される。
【００６０】
「統計情報」フィールドには、処理したパケットの累計数等の統計情報が記される。
【００６１】
「テストＩＤ」フィールドには、テストを一意に判別可能な「テストＩＤ」が記される。
【００６２】
［本発明におけるテストパケットの形式］
図８は、本発明で用いるテストパケットの形式である。ここでは、テストパケットが「ＩＰｖ４」に準拠する場合を例に説明する。
【００６３】
テストパケットは、基本ヘッダ部と、テストデータ部を有する。
【００６４】
テストパケットは、基本ヘッダ部に、「サービスタイプ」（ＴＯＳ：Ｔｙｐｅ  Ｏｆ  Ｓｅｒｖｉｃｅ）フィールドと、「プロトコル」（Ｐｒｏｔｏｃｏｌ）フィールドを含む。
【００６５】
「サービスタイプ」フィールドは、パケットが転送される際に重視するサービスを一意に判別可能な「サービス種別」を格納できるサイズを持つものとする。
【００６６】
「プロトコル」フィールドは、上位プロトコルを一意に判別可能な「プロトコル番号」を格納できるサイズを持つものとする。
【００６７】
「サービスタイプ」フィールド及び「プロトコル」フィールドは、それぞれのフィールドの値の組み合わせにより、本発明に係る閉路検出用テストパケットであることを表す。すなわち、「サービスタイプ」フィールド及び「プロトコル」フィールドは、本発明に係る閉路検出用テストパケットであるか否かの判別に用いられる。
【００６８】
また、テストパケットは、テストデータ部に、「テストＩＤ」フィールドと、「テスト成否フラグ」フィールドと、「通過ＯＦＳ情報」フィールドを含む。
【００６９】
「テストＩＤ」フィールドは、テストを一意に判別可能な「テストＩＤ」を格納できるサイズを持つものとする。例えば、ＯＦＣは、当該ＯＦＣのＭＡＣアドレス及び時刻等からユニーク（ｕｎｉｑｕｅ）な「テストＩＤ」を生成する。
【００７０】
「テスト成否フラグ」フィールドは、テスト未完了を表す「０」、テストが成功して完了したことを表す「１」、テストが失敗して完了したことを表す「２」、パケットの生存期限（有効期限）切れによりルーティングが完了しなかったことを表す「３」の４つの状態を表現できるサイズ（例えば、２ｂｉｔ）を持つものとする。
【００７１】
「通過ＯＦＳ情報」フィールドは、ＭＡＣアドレス及びポート番号を複数格納できるサイズを持つものとする。ＭＡＣアドレス及びポート番号は、ＯＦＳ１台分のアドレス情報である。すなわち、ＯＦＳ１台につき、ＭＡＣアドレス及びポート番号の組を１つ持つ。この「通過ＯＦＳ情報」フィールドには、テストパケットがテスト中に経由したＯＦＳのＭＡＣアドレスを順に格納するものとする。なお、この「通過ＯＦＳ情報」フィールドは、基本ヘッダ部にある「生存時間」（ＴＴＬ：Ｔｉｍｅ  Ｔｏ  Ｌｉｖｅ）フィールドの値で示される数だけアドレス情報を格納できる。すなわち、この「通過ＯＦＳ情報」フィールドにおけるアドレス情報のエントリ数の上限は、「生存時間」フィールドの値で示される。
【００７２】
［動作の説明］
次に、図９を参照して、（Ａ）テストの実施例、（Ｂ）成否判断の実施例、（Ｃ）結果反映の実施例の順に説明する。
【００７３】
［（Ａ）テストの実施例］
図９に示すオープンフローネットワークシステムは、ホスト４０（４０−ｉ、ｉ＝１〜ｘ）と、ＯＦＳ４１（４１−ｊ、ｊ＝１〜ｙ）と、ＯＦＣ４２（４２−ｋ、ｋ＝１〜ｚ）を含む。
【００７４】
ここで、ホスト４０（４０−ｉ、ｉ＝１〜ｘ）は、図１のホスト１０（１０−ｉ、ｉ＝１〜ｘ）に相当する。ＯＦＳ４１（４１−ｊ、ｊ＝１〜ｙ）は、図１のＯＦＳ１１（１１−ｊ、ｊ＝１〜ｙ）に相当する。ＯＦＣ４２（４２−ｋ、ｋ＝１〜ｚ）は、図１のＯＦＣ１１（１１−ｋ、ｋ＝１〜ｚ）に相当する。ホスト４０（４０−ｉ、ｉ＝１〜ｘ）、ＯＦＳ４１（４１−ｊ、ｊ＝１〜ｙ）、及びＯＦＣ４２（４２−ｋ、ｋ＝１〜ｚ）は、ネットワーク４００（４００−ｌ、ｌ＝１〜ｗ）に属する。ホスト４０−１、ＯＦＳ４１−１、及びＯＦＳ４１−２は、ネットワーク４００−１に属し、ＯＦＣ４２−１は、ＯＦＳ４１−１、ＯＦＳ４１−２を管理しているものとする。同様に、ＯＦＳ４１−３は、ネットワーク４００−２に属し、ＯＦＣ４２−２は、ＯＦＳ４１−３を管理しているものとする。同様に、ホスト４０−２、ＯＦＳ４１−４、及びＯＦＳ４１−５は、ネットワーク４００−３に属し、ＯＦＣ４２−３は、ＯＦＳ４１−４及びＯＦＳ４１−５を管理しているものとする。
【００７５】
（１）ステップＡ０１
ホスト４０−１は、ホスト４０−２宛のパケットをＯＦＳ４１−１に送信する。ＯＦＳ４１−１は、パケットを受け取った際、フローテーブルに登録されたフローエントリの中に、パケットに記された転送先アドレス・転送元アドレスの値がマッチするフローエントリがあるかないかを判断する。
【００７６】
（２）ステップＡ０２
ＯＦＳ４１−１は、既存のフローエントリには、パケットに記された転送先アドレス・転送元アドレスの値がマッチするフローエントリが無いので、ＯＦＣ４２−１に問い合わせる。ＯＦＣ４２−１は、ネットワーク４００−２及びネットワーク４００−３において、どのようなフローエントリが設定されているかを検知する構成要素や処理手順を持たない。ＯＦＣ４２−１は、経路計算ルーチンに従い、経路を計算する。ＯＦＣ４２−１は、その計算結果をフローエントリとしてＯＦＳ４１−１に登録する際、このフローエントリを仮登録のフローエントリとする。ＯＦＣ４２−１は、仮登録であることが判別可能となるように、仮登録のフローエントリの「アクション」フィールドに、例えば、「ＴＥＳＴＦＯＲＷＡＲＤ」といった仮登録である旨を示す内容のデータを記すものとする。また、ＯＦＣ４２−１は、当該ＯＦＣ４２−１のＭＡＣアドレス及び時刻等からユニークな「テストＩＤ」を生成し、「テストＩＤ」フィールドに「テストＩＤ」を格納する。
【００７７】
（３）ステップＡ０３
ＯＦＳ４１−１では、元々ホスト４０−１から受け取ったパケットを一時保持する。また、ＯＦＳ４１−１は、図８に示す形式に準じたテストパケットを生成する。ＯＦＳ４１−１は、テストパケットを生成する際、基本ヘッダ部の「サービスタイプ」フィールド及び「プロトコル」フィールドに、本閉路形成テストに用いるパケット（テストパケット）であることを判別可能な値を格納する。また、ＯＦＳ４１−１は、基本ヘッダ部の「生存時間」フィールドに、元々受け取ったパケットに記されていた値を転記する。また、ＯＦＳ４１−１は、テストデータ部の「テストＩＤ」フィールドに、ＯＦＣ４２−１により生成された「テストＩＤ」（すなわち、仮登録されたフローエントリに記載されている「テストＩＤ」）を格納するものとする。また、ＯＦＳ４１−１は、テストデータ部の「テスト成否フラグ」フィールドに、テスト未完のステータスであることを示す値（例えば、「０」）を格納する。また、ＯＦＳ４１−１は、テストデータ部の「通過ＯＦＳ情報」フィールドに、ＯＦＳ４１−１のＭＡＣアドレス及びポート番号の値を格納する。
【００７８】
（４）ステップＡ０４
ＯＦＳ４１−１は、上記のようにして生成されたテストパケットを、仮登録されたフローエントリに従って、ＯＦＳ４１−２宛に転送する。
【００７９】
（５）ステップＡ０５
ＯＦＳ４１−２は、到着したパケットのサービスタイプとプロトコルタイプの値をチェックすることで、テストパケットが到着したことを検知する。ＯＦＳ４１−２は、テストパケットのテストデータ部の「通過ＯＦＳ情報」フィールドに、ＯＦＳ４１−２のＭＡＣアドレス及びポート番号の値を追加する。ＯＦＳ４１−２は、自身のフローテーブルの既存のフローエントリの中に、テストパケットの転送先アドレス・転送元アドレスの値がマッチするフローエントリがあるかないかを判断する。ここでは、ＯＦＳ４１−２は、自身のフローテーブルの既存のフローエントリの中に、テストパケットの転送先アドレス・転送元アドレスの値がマッチするフローエントリがあるので、当該フローエントリの「テストＩＤ」フィールドに、当該テストパケットの「テストＩＤ」フィールドと同一の値（テストＩＤ）が記されていないかをチェックする。ＯＦＳ４１−２は、当該フローエントリの「テストＩＤ」フィールドに、当該テストパケットの「テストＩＤ」フィールドと同一の値が記されていない場合、当該フローエントリの「テストＩＤ」フィールドに、当該テストパケットの「テストＩＤ」フィールドに記されている値（テストＩＤ）を記入する。ＯＦＳ４１−２は、既に、当該フローエントリの「テストＩＤ」フィールドに、当該テストパケットの「テストＩＤ」フィールドと同一の値が記されている場合、閉路が形成されたことになるため、この時点でテスト失敗としてテストを完了する。ここでは、テスト失敗ではないものとして、テストを継続する。
【００８０】
（６）ステップＡ０６
ＯＦＳ４１−２は、テストパケットを、マッチした既存のフローエントリに従って、ＯＦＳ４１−３宛に転送する。
【００８１】
（７）ステップＡ０７
ＯＦＳ４１−３は、到着したパケットのサービスタイプとプロトコルタイプの値をチェックすることで、テストパケットが到着したことを検知する。ＯＦＳ４１−３は、テストパケットの「通過ＯＦＳ情報」フィールドに、ＯＦＳ４１−３のＭＡＣアドレス及びポート番号の値を追加する。ＯＦＳ４１−３は、自身のフローテーブルの既存のフローエントリの中に、テストパケットの転送先アドレス・転送元アドレスの値がマッチするフローエントリがあるかないかを判断する。
【００８２】
（８）ステップＡ０８
ＯＦＳ４１−３は、自身のフローテーブルの既存のフローエントリの中に、テストパケットの転送先アドレス・転送元アドレスの値がマッチするフローエントリがないので、ＯＦＣ４２−２に仮登録のフローエントリ設定を依頼する。ＯＦＣ４２−２は、具備する経路計算ルーチンにより経路の計算を行う。ＯＦＣ４２−２は、その計算結果をフローエントリとしてＯＦＳ４１−３に登録する際、このフローエントリを仮登録のフローエントリとする。また、ＯＦＣ４２−２は、ステップＡ０３と同様に、仮登録であることが判別可能となるように、仮登録のフローエントリの「アクション」フィールドに、例えば、「ＴＥＳＴＦＯＲＷＡＲＤ」といった内容のデータを記すものとする。
【００８３】
（９）ステップＡ０９
ＯＦＳ４１−３は、仮登録のフローエントリの「テストＩＤ」フィールドに、当該テストパケットの「テストＩＤ」フィールドに記されている値を格納する。
【００８４】
（１０）ステップＡ１０
ＯＦＳ４１−３は、テストパケットを、仮登録されたフローエントリに従って、ＯＦＳ４１−４宛に転送する。
【００８５】
（１１）ステップＡ１１
ＯＦＳ４１−４は、到着したパケットのサービスタイプとプロトコルタイプの値をチェックすることで、テストパケットが到着したことを検知する。ＯＦＳ４１−４は、テストテストパケットの「通過ＯＦＳ情報」フィールドに、ＯＦＳ４１−４のＭＡＣアドレス及びポート番号の値を追加する。ＯＦＳ４１−４は、自身のフローテーブルの既存のフローエントリの中に、テストパケットの転送先アドレス・転送元アドレスの値がマッチするフローエントリがあるかないかを判断する。ここでは、ＯＦＳ４１−４は、マッチするフローエントリがあるので、ステップＡ０５と同様に、当該フローエントリの「テストＩＤ」フィールドに、当該テストパケットの「テストＩＤ」フィールドと同一の値が記されていないかをチェックする。ＯＦＳ４１−４は、当該フローエントリの「テストＩＤ」フィールドに、当該テストパケットの「テストＩＤ」フィールドと同一の値が記されていない場合、当該フローエントリの「テストＩＤ」フィールドに、当該テストパケットの「テストＩＤ」フィールドに記されている値を記入する。ＯＦＳ４１−４は、既に、当該フローエントリの「テストＩＤ」フィールドに、当該テストパケットの「テストＩＤ」フィールドと同一の値が記されている場合、閉路が形成されたことになるため、この時点でテスト失敗としてテストを完了する。ここでは、テスト失敗ではないものとして、テストを継続する。
【００８６】
（１２）ステップＡ１２
ＯＦＳ４１−４は、テストパケットを、マッチした既存のフローエントリに従って、ＯＦＳ４１−５宛に転送する。
【００８７】
（１３）ステップＡ１３
ＯＦＳ４１−５は、到着したパケットのサービスタイプとプロトコルタイプの値をチェックすることで、テストパケットが到着したことを検知する。ＯＦＳ４１−５は、テストテストパケットの「通過ＯＦＳ情報」フィールドにＯＦＳ４１−４のＭＡＣアドレス及びポート番号の値を追加する。ＯＦＳ４１−５は、自身のフローテーブルの既存のフローエントリの中に、テストパケットの転送先アドレス・転送元アドレスの値がマッチするフローエントリがあるかないかを判断する。ここでは、ＯＦＳ４１−５は、マッチするフローエントリがあるので、ステップＡ０５、ステップＡ１１と同様に、当該フローエントリの「テストＩＤ」フィールドに、当該テストパケットの「テストＩＤ」フィールドと同一の値が記されていないかをチェックする。ＯＦＳ４１−５は、当該フローエントリの「テストＩＤ」フィールドに、当該テストパケットの「テストＩＤ」フィールドと同一の値が記されていない場合、当該フローエントリの「テストＩＤ」フィールドに、当該テストパケットの「テストＩＤ」フィールドに記されている値を記入する。ＯＦＳ４１−５は、既に、当該フローエントリの「テストＩＤ」フィールドに、当該テストパケットの「テストＩＤ」フィールドと同一の値が記されている場合、閉路が形成されたことになるため、この時点でテスト失敗としてテストを完了する。ここでは、テスト失敗ではないものとして、テストを継続する。
【００８８】
（１４）ステップＡ１４
ＯＦＳ４１−５は、テストパケットを、マッチした既存のフローエントリに従って、ホスト４０−２に転送する。
【００８９】
［（Ｂ）成否判断の実施例］
（Ａ）のステップＡ０１からステップＡ１４は、閉路が生成されなかった事例（ケース）の実施例である。
【００９０】
ステップＡ１３、ステップＡ１４において、ＯＦＳは、送信元ホストと異なるホストに転送可能であることが判断できるため、この時点でテスト成功とし、テストパケットの「テスト成否フラグ」フィールドに、テストが成功して完了したことを示す値「１」を格納するものとする。
【００９１】
一方、テストが失敗する事例（ケース）では、自身のフローテーブルの既存のフローエントリの中に、テストパケットとマッチするフローエントリがあり、当該フローエントリの「テストＩＤ」フィールドとテストパケットの「テストＩＤ」フィールドとに、同一の値（テストＩＤ）が記されている場合は、既に一度通った経路に再び入ったこととなり、閉路が形成されてしまったことになる。
【００９２】
したがって、この場合、ＯＦＳは、テストパケットの「テスト成否フラグ」フィールドに、テストが失敗して完了したことを示す値「２」を格納するものとする。また、図９では示されていないが、テストパケットの転送において「生存時間」（ＴＴＬ）フィールドの値が０となった場合は、パケットの生存期限（有効期限）が切れたことになるため、生存期限（有効期限）切れで失敗したことを示す値（例えば、「３」）を格納するものとする。本事例については、後述する「ＯＦＳの処理ルーチン」（図１０Ａ参照）において別途説明する。
【００９３】
［（Ｃ）結果反映の実施例］
上記の（Ａ）（Ｂ）の実施例のように、テストパケットを転送し続けることにより、いずれかのＯＦＳにおいて、テストが成功／失敗して完了する。ＯＦＳは、テスト結果を反映させるために、テスト結果の値を「テスト成否フラグ」フィールドに詰めた後、テストパケットとフローエントリのクリーンナップ（ｃｌｅａｎ  ｕｐ）処理を行う。
【００９４】
［テストパケットのクリーンナップ処理］
ＯＦＳは、クリーンナップ処理の対象がテストパケットの場合、当該テストパケットのテストデータ部の「通過ＯＦＳ情報」フィールドの末尾に、自身のＭＡＣアドレスが記載されているので、このＭＡＣアドレスを削除する。
【００９５】
［本登録のフローエントリのクリーンナップ処理］
ＯＦＳは、クリーンナップ処理の対象が本登録のフローエントリの場合、テストの成否に関わらず、当該フローエントリの「テストＩＤ」フィールドから、自身に該当するテストＩＤを削除し、テスト中に付与したデータを削除する。
【００９６】
［仮登録のフローエントリのクリーンナップ処理］
ＯＦＳは、クリーンナップ処理の対象が仮登録のフローエントリの場合、テストの成否に応じてクリーンナップ処理を行う。例えば、ＯＦＳは、テスト失敗の場合、仮登録のフローエントリ自体を削除する。また、ＯＦＳは、テスト成功の場合、仮登録のフローエントリの「アクション」フィールドを書き換えて、仮登録のフローエントリから本登録のフローエントリに更新する。
【００９７】
ＯＦＳは、上記のようにして、テスト結果を、テストパケットとフローエントリに反映する。
【００９８】
以上のクリーンナップ処理が完了すると、ＯＦＳは、テストパケットのテストデータ部の「通過ＯＦＳ情報」フィールドの末尾に記載されているＭＡＣアドレスを基に、当該ＭＡＣアドレスを持つＯＦＳに当該テストパケットを転送する。
【００９９】
転送先のＯＦＳも、クリーンナップ処理を行う。これを繰り返すことにより、最終的にテストパケットにＭＡＣアドレスが１個も記載されていない状態となる。このとき、テストパケットは、生成元のＯＦＳに戻ってきたことになる。ここで、ＯＦＳは、テスト成功の場合には、当該ＯＦＳでペンディング（ｐｅｎｄｉｎｇ：未解決、保留）としていたパケットを、上記の（Ａ）（Ｂ）（Ｃ）のようにして本登録したフローエントリに従って転送する。また、ＯＦＳは、テスト失敗の場合には、ペンディングとしていたパケットを破棄して経路計算を実施したＯＦＣにエラーを返す。
【０１００】
上記（Ａ）（Ｂ）（Ｃ）の実施例は、図７で示されるフローエントリと、図８で示されるテストパケットと、図１０Ａ〜図１０Ｃで示されるＯＦＳの処理ルーチンにより実現可能となる。ＯＦＳの処理ルーチンは、ファームウェア（ＦＷ：Ｆｉｒｍｗａｒｅ）として実装される。
【０１０１】
［ＯＦＳの処理ルーチン］
図１０Ａ、図１０Ｂ、及び図１０Ｃを用いて、ＯＦＳの処理ルーチンについて説明する。
【０１０２】
（１）ステップＢ０１
ＯＦＳは、パケットを受け取ったとき、パケットのヘッダ部の「サービスタイプ」、「プロトコル」を参照することにより、テストパケットか否かを確認（チェック）する。
【０１０３】
（２）ステップＢ０２
ＯＦＳは、受け取ったパケットがテストパケットでない場合、パケットのヘッダ部の「送信元アドレス」、「宛て先アドレス」を基に、自身のフローテーブルの既存のフローエントリの中に、マッチするフローエントリがあるかないかを判断する。
【０１０４】
（３）ステップＢ０３
ＯＦＳは、マッチするフローエントリがある場合は、そのエントリに従って転送等の処理をする。
【０１０５】
（４）ステップＢ０４
ＯＦＳは、マッチするフローエントリがない場合は、ＯＦＣに経路を問い合わせる。ＯＦＣは、経路を計算し、テストＩＤを生成する。
【０１０６】
（５）ステップＢ０５
ＯＦＣは、計算結果を基に、ＯＦＳにフローエントリを仮登録する。ＯＦＣは、当該フローエントリの「アクション」フィールドに、仮登録による転送である旨を記す。また、ＯＦＣは、当該フローエントリの「テストＩＤ」フィールドに、生成したテストＩＤを記す。
【０１０７】
（６）ステップＢ０６
ＯＦＳは、テストパケットを生成する。テストパケットの生成については、ステップＡ０３で説明した通りである。
【０１０８】
（７）ステップＢ０７
ＯＦＳは、元々受け取ったパケットを、ペンディング扱いとして保持しておき、ステップＢ０６で生成したテストパケットを、ステップＢ０５で仮登録したフローエントリに従って転送する。これにより、テストが開始したことになる。
【０１０９】
（８）ステップＢ０８
また、ＯＦＳは、ステップＢ０１において、受け取ったパケットがテストパケットである場合は、テスト処理中、或いは、テスト結果の反映処理中であるか、テスト成否フラグの値を参照して判断する。
【０１１０】
（９）ステップＢ０９
ＯＦＳは、ステップＢ０８において、「テスト成否フラグ」フィールドに値がセットされていない（或いは、値が０である）場合は、テスト処理中であると判断し、「生存時間」フィールドの値が０か否かを確認する。
【０１１１】
（１０）ステップＢ１０
ＯＦＳは、ステップＢ０９において、「生存時間」フィールドの値が０であった場合は、パケットの生存期限（有効期限）切れであると判断する。
【０１１２】
（１１）ステップＢ１１
ＯＦＳは、ステップＢ０９において、「生存時間」フィールドの値が０でない場合は、パケットのヘッダ部の「送信元アドレス」、「宛て先アドレス」を基に、自身のフローテーブルの既存のフローエントリの中に、マッチするフローエントリがあるかないかを判断する。
【０１１３】
（１２）ステップＢ１２
ＯＦＳは、ステップＢ１１において、マッチするフローエントリがある場合、当該フローエントリの「テストＩＤ」フィールドに、テストパケットの「テストＩＤ」フィールドに記されている値と同一の値があるか否かを確認する。
【０１１４】
（１３）ステップＢ１３
ＯＦＳは、ステップＢ１２において、同一の値があった場合は、閉路を検出したことになるため、テスト失敗と判断する。
【０１１５】
（１４）ステップＢ１４
ＯＦＳは、ステップＢ１２において、同一の値が無い場合は、現段階では閉路は形成されていないと判断し、当該フローエントリの転送先がホストであるか否かを確認する。
【０１１６】
（１５）ステップＢ１５
ＯＦＳは、ステップＢ１４において、当該フローエントリの転送先がホストである場合、閉路を形成しておらず、ルーティングできることを検出したことになるため、テスト成功と判断する。
【０１１７】
（１６）ステップＢ１６
ＯＦＳは、テスト結果を表す値を、テストパケットの「テスト成否フラグ」フィールドに格納する。ここでは、ＯＦＳは、ステップＢ１０を経由した場合は、生存期限（有効期限）切れで失敗したことを表す「３」を、テストパケットの「テスト成否フラグ」フィールドに格納する。また、ＯＦＳは、ステップＢ１３を経由した場合は、閉路が形成されて失敗したことを表す「２」を、テストパケットの「テスト成否フラグ」フィールドに格納する。また、ＯＦＳは、ステップＢ１５を経由した場合は、成功を表す「１」を、テストパケットの「テスト成否フラグ」フィールドに格納する。
【０１１８】
（１７）ステップＢ１７
ＯＦＳは、テストパケットのテストデータ部の「通過ＯＦＳ情報」フィールドの末尾のＭＡＣアドレスを参照して、テストパケットを１つ前に経由したＯＦＳに転送し、この時点でテストを完了する。
【０１１９】
（１８）ステップＢ１８
ＯＦＳは、ステップＢ１１において、マッチするフローエントリがない場合は、ＯＦＣに経路を問い合わせる。ＯＦＣは、経路を計算する。
【０１２０】
（１９）ステップＢ１９
ＯＦＣは、計算結果を基に、ＯＦＳにフローエントリを仮登録する。ＯＦＣは、当該フローエントリの「アクション」フィールドに、仮登録による転送である旨を記す。
【０１２１】
（２０）ステップＢ２０
ＯＦＳは、フローエントリにテストＩＤを格納する。このとき、既に別のフローエントリが格納されている場合は、別のテストを実行中ということである。通常、テストは短い時間で完了するため、当該テストが完了するのを待ち、既存のテストＩＤがクリーンナップ処理により削除されてから、当該テストパケットのテストＩＤを格納する。ここでは、ＯＦＳは、ステップＢ１４を経由した場合は、マッチしたフローエントリの「テストＩＤ」フィールドに、テストパケットの「テストＩＤ」フィールドに記されている値を記す。また、ＯＦＳは、ステップＢ１９を経由した場合は、仮登録されたフローエントリの「テストＩＤ」フィールドに、テストパケットの「テストＩＤ」フィールドに記されている値を記す。
【０１２２】
（２１）ステップＢ２１
ＯＦＳは、テストパケットの「通過ＯＦＳ情報」フィールドに、自ＯＦＳのＭＡＣアドレス及びポート番号を記載し、テストパケットの「生存時間」フィールドの値を１減算し、エントリに従って転送する。
【０１２３】
（２２）ステップＢ２２
また、ステップＢ０８において、「テスト成否フラグ」フィールドに、テスト成功を表す値、或いは、テスト失敗を表す値がセットされていた場合（０以外の値がセットされている場合）は、テスト結果の反映処理中であるということである。ＯＦＳにおいて、テストパケットのテストデータ部の「通過ＯＦＳ情報」フィールドの末尾のＭＡＣアドレスを見ると、当該ＯＦＳのＭＡＣアドレスが記載されているはずである。ＯＦＳは、テストパケットのテストデータ部の「通過ＯＦＳ情報」フィールドの末尾から、自身のＭＡＣアドレスを削除する。
【０１２４】
（２３）ステップＢ２３
ＯＦＳは、自身のフローテーブルに登録されているフローエントリの中から、テストパケットの「テストＩＤ」フィールドに記されている値と同一の値が「テストＩＤ」フィールドに記されているフローエントリを探す。
【０１２５】
（２４）ステップＢ２４
ＯＦＳは、見つかったフローエントリの「アクション」フィールドを参照して、当該フローエントリが仮登録のフローエントリか本登録のフローエントリかを判断する。
【０１２６】
（２５）ステップＢ２５
ＯＦＳは、ステップＢ２４の結果、当該フローエントリが仮登録のフローエントリであった場合、テストパケットの「テスト成否フラグ」を参照する。
【０１２７】
（２６）ステップＢ２６
ＯＦＳは、ステップＢ２５の結果、「テスト成否フラグ」フィールドにテスト成功を表す値が入っていれば、仮登録のフローエントリを本登録のフローエントリに更新する。すなわち、ＯＦＳは、当該フローエントリの「アクション」フィールドに記された仮登録である旨を示す内容のデータを、本登録である旨を示す内容のデータに更新する。例えば、ＯＦＳは、当該フローエントリの「アクション」フィールドから、仮登録である旨を示す内容のデータを削除するようにしても良い。
【０１２８】
（２７）ステップＢ２７
ＯＦＳは、ステップＢ２５の結果、「テスト成否フラグ」フィールドにテスト失敗を表す値が入っていれば、当該フローエントリを削除する。
【０１２９】
（２８）ステップＢ２８
ＯＦＳは、ステップＢ２４の結果、当該フローエントリが本登録のフローエントリであった場合、テストの成否に関わらず、当該フローエントリの「テストＩＤ」フィールドから、テストパケットの「テストＩＤ」フィールドに記載されているテストＩＤの値を削除する。
【０１３０】
（２９）ステップＢ２９
ＯＦＳは、テストパケットのテストデータ部の「通過ＯＦＳ情報」フィールドを参照し、１個以上のＭＡＣアドレスがあるか否かを確認する。
【０１３１】
（３０）ステップＢ３０
ＯＦＳは、ステップＢ２９において、１個以上のＭＡＣアドレスがある場合は、「通過ＯＦＳ情報」フィールドの末尾のＭＡＣアドレスを持つＯＦＳにテストパケットを転送する。
【０１３２】
（３１）ステップＢ３１
ステップＢ２９において、１個もＭＡＣアドレスがない場合は、テストパケット生成元のＯＦＳに戻ってきたということである。ＯＦＳは、テストパケットの「テスト成否フラグ」フィールドを参照して、テストの成否を確認する。
【０１３３】
（３２）ステップＢ３２
ＯＦＳは、ステップＢ３１において、テストが成功していた場合、ステップＢ０７においてペンディングとしていたパケットを、フローエントリに従って転送する。また、ＯＦＳは、テストパケットを破棄する。
【０１３４】
（３３）ステップＢ３３
ＯＦＳは、ステップＢ３１において、テストが失敗していた場合、ステップＢ０７においてペンディングとしていたパケットを破棄し、ＯＦＣに対してエラーを返す。また、ＯＦＳは、テストパケットを破棄する。
【０１３５】
［本発明の効果］
本発明では、テストパケットにより、事前に閉路の形成をチェックし、その結果をフローエントリ登録に反映できる。そのため、ＯＦＣ等のコントローラ同士が連携することを必要とせず、閉路の形成を未然に防止できる。
【０１３６】
また、本発明では、閉路形成テスト処理において、ＯＦＣやＯＦＳの数に対して線形以上の処理量の増加があるような計算要素がない。そのため、ネットワークの規模が大きくなっても、閉路形成テストが軽量な処理により実行できる。
【０１３７】
［ＯＦＳの内部構成例］
図１１を参照して、本発明に係る閉路形成未然防止システムにおけるＯＦＳの内部構成例について説明する。
【０１３８】
ＯＦＳ１１（１１−ｊ、ｊ＝１〜ｙ）の各々は、テストパケット確認部１１１と、フローエントリ確認部１１２と、問い合わせ処理部１１３と、テストパケット生成部１１４と、テスト実行部１１５と、仮登録フローエントリ破棄部１１６を備える。
【０１３９】
テストパケット確認部１１１は、受信パケットがテストパケットか否かを確認する。
【０１４０】
フローエントリ確認部１１２は、受信パケットがテストパケットでない場合、フローテーブルの既存のフローエントリの中に、受信パケットにマッチするフローエントリがあるか否かを確認する。
【０１４１】
問い合わせ処理部１１３は、受信パケットにマッチするフローエントリがない場合、ＯＦＣ１２（１２−ｋ、ｋ＝１〜ｚ）に問い合わせる。
【０１４２】
テストパケット生成部１１４は、ＯＦＣ１２（１２−ｋ、ｋ＝１〜ｚ）から仮登録されたフローエントリを基に、テストパケットを生成する。
【０１４３】
テスト実行部１１５は、受信パケットを保留し、ＯＦＣ１２（１２−ｋ、ｋ＝１〜ｚ）から仮登録されたフローエントリに従い、テストパケットを転送し、閉路形成を検出するためのテストを開始する。
【０１４４】
仮登録フローエントリ破棄部１１６は、テストの結果、閉路形成を検出した場合、ＯＦＣ１２（１２−ｋ、ｋ＝１〜ｚ）から仮登録されたフローエントリを破棄する。
【０１４５】
なお、テストパケット確認部１１１、フローエントリ確認部１１２、問い合わせ処理部１１３、テストパケット生成部１１４、テスト実行部１１５、及び仮登録フローエントリ破棄部１１６は、相互に連携可能であるものとする。
【０１４６】
［テストパケット生成部の詳細］
図１２を参照して、テストパケット生成部１１４の詳細について説明する。
【０１４７】
テストパケット生成部１１４は、フィールド設定部１１４１と、テストパケット判別情報管理部１１４２と、ＴＴＬ管理部１１４３と、テストＩＤ管理部１１４４と、テスト結果情報初期化部１１４５と、通過ＯＦＳ情報管理部１１４６を備える。
【０１４８】
フィールド設定部１１４１は、テストパケットを生成する際、当該テストパケットに、基本ヘッダ部とテストデータ部とを設ける。
【０１４９】
テストパケット判別情報管理部１１４２は、基本ヘッダ部のサービスタイプフィールド及びプロトコルタイプフィールドに、テストパケットである旨を示す値を格納する。
【０１５０】
ＴＴＬ管理部１１４３は、基本ヘッダ部の生存時間フィールドに、受信パケットに記されていた値を転記する。
【０１５１】
テストＩＤ管理部１１４４は、テストデータ部のテストＩＤフィールドに、ＯＦＣ１２（１２−ｋ、ｋ＝１〜ｚ）から仮登録されたフローエントリに記載されているテストＩＤを格納する。
【０１５２】
テスト結果情報初期化部１１４５は、テストデータ部のテスト成否フラグフィールドに、テスト未完のステータスであることを示す値を格納する。
【０１５３】
通過ＯＦＳ情報管理部１１４６は、テストデータ部の通過ＯＦＳ情報フィールドに、ＯＦＳ１１（１１−ｊ、ｊ＝１〜ｙ）のＭＡＣアドレス及びポート番号の値を格納する。
【０１５４】
［テスト実行部の詳細］
図１３を参照して、テスト実行部１１５の詳細について説明する。
【０１５５】
テスト実行部１１５は、テスト成否フラグ確認部１１５１と、ＴＴＬ確認部１１５２と、テストＩＤ確認部１１５３と、転送先確認部１１５４と、テスト結果情報管理部１１５５と、テストパケット転送部１１５６を備える。
【０１５６】
テスト成否フラグ確認部１１５１は、受信パケットがテストパケットである場合、テストパケットのテスト成否フラグフィールドの値を確認し、テストパケットのテスト成否フラグフィールドに値がセットされていないか、又は値が０である場合、テスト処理中であると判断する。
【０１５７】
ＴＴＬ確認部１１５２は、テスト処理中である場合、生存時間フィールドの値が０か否かを確認する。ＴＴＬ確認部１１５２は、テストパケットの生存時間フィールドの値が０であった場合、パケットの生存期限切れであると判断し、テスト失敗と判断する。また、ＴＴＬ確認部１１５２は、テストパケットの生存時間フィールドの値が０でない場合、図１１のフローエントリ確認部１１２と連携して、フローテーブルの既存のフローエントリの中に、テストパケットにマッチするフローエントリがあるか否かを確認する。
【０１５８】
テストＩＤ確認部１１５３は、テストパケットにマッチするフローエントリがある場合、当該フローエントリのテストＩＤフィールドに、テストパケットのテストＩＤフィールドに記されている値と同一の値があるか否かを確認し、同一の値があった場合、閉路が形成されたと判断し、テスト失敗と判断する。
【０１５９】
転送先確認部１１５４は、同一の値がない場合、現段階では閉路は形成されていないと判断し、当該フローエントリの転送先がホストであるか否かを確認し、当該フローエントリの転送先がホストである場合、閉路を形成しておらずルーティングできると判断し、テスト成功と判断する。
【０１６０】
テスト結果情報管理部１１５５は、テスト結果を表す値を、テストパケットのテスト成否フラグフィールドに格納する。
【０１６１】
テストパケット転送部１１５６は、テストパケットの通過ＯＦＳ情報フィールドの末尾のＭＡＣアドレスを参照して、テストパケットを１つ前に経由したＯＦＳ１１（１１−ｊ、ｊ＝１〜ｙ）に転送し、テストを完了する。
【０１６２】
［テストパケット未登録の場合］
以下に、テストパケットが未登録の場合における処理について説明する。
【０１６３】
図１１の問い合わせ処理部１１３は、テストパケットにマッチするフローエントリがない場合、ＯＦＣ１２（１２−ｋ、ｋ＝１〜ｚ）に問い合わせる。
【０１６４】
図１２のテストＩＤ管理部１１４４は、ＯＦＣ１２（１２−ｋ、ｋ＝１〜ｚ）からフローエントリが仮登録された場合、或いは、テストパケットにマッチするフローエントリの転送先がホストでない場合、当該フローエントリのテストＩＤフィールドに、テストパケットのテストＩＤフィールドに記されている値を記入する。
【０１６５】
図１２の通過ＯＦＳ情報管理部１１４６は、テストパケットの通過ＯＦＳ情報フィールドに、ＯＦＳ１１（１１−ｊ、ｊ＝１〜ｙ）のＭＡＣアドレス及びポート番号の値を格納する。
【０１６６】
図１２のＴＴＬ管理部１１４３は、テストパケットの生存時間フィールドの値を１減算する。
【０１６７】
図１３のテストパケット転送部１１５６は、当該フローエントリに従い、テストパケットを転送し、テストを継続する。
【０１６８】
［テスト実行済みの場合］
以下に、テストが実行済みの場合における処理について説明する。
【０１６９】
図１２の通過ＯＦＳ情報管理部１１４６は、テストパケットのテスト成否フラグフィールドに０以外の値がセットされている場合（テスト未完了ではない場合）、テストパケットの通過ＯＦＳ情報フィールドの末尾から、ＯＦＳ１１（１１−ｊ、ｊ＝１〜ｙ）のＭＡＣアドレスを削除する。
【０１７０】
図１１のフローエントリ確認部１１２は、フローテーブルに登録されているフローエントリの中から、テストパケットのテストＩＤフィールドに記されている値と同一の値がテストＩＤフィールドに記されているフローエントリを検索する。検出されたフローエントリのアクションフィールドを参照して、当該フローエントリが仮登録のフローエントリか本登録のフローエントリかを判断する。当該フローエントリが仮登録のフローエントリであった場合、図１３のテスト成否フラグ確認部１１５１と連携して、テストパケットのテスト成否フラグを参照する。テストパケットのテスト成否フラグフィールドにテスト成功を表す値が入っている場合、当該フローエントリを本登録のフローエントリに更新する。テストパケットのテスト成否フラグフィールドにテスト失敗を表す値が入っている場合、当該フローエントリを削除する。当該フローエントリが本登録のフローエントリであった場合、図１２のテストＩＤ管理部１１４４と連携して、テストの成否に関わらず、当該フローエントリのテストＩＤフィールドから、テストパケットのテストＩＤフィールドに記載されているテストＩＤの値を削除する。
【０１７１】
図１３のテストパケット転送部１１５６は、テストパケットの通過ＯＦＳ情報フィールドを参照し、１個以上のＭＡＣアドレスがあるか否かを確認する。テストパケットの通過ＯＦＳ情報フィールドに１個以上のＭＡＣアドレスがある場合は、テストパケットの通過ＯＦＳ情報フィールドの末尾のＭＡＣアドレスを持つＯＦＳ１１（１１−ｊ、ｊ＝１〜ｙ）にテストパケットを転送し、テストを継続する。テストパケットの通過ＯＦＳ情報フィールドに１個もＭＡＣアドレスがない場合、テストパケットの生成元のＯＦＳ１１（１１−ｊ、ｊ＝１〜ｙ）に戻ってきたと判断し、テスト結果情報管理部１１５５と連携して、テストパケットの生成元のＯＦＳ１１（１１−ｊ、ｊ＝１〜ｙ）に戻ってきた場合、テストパケットのテスト成否フラグフィールドを参照して、テストの成否を確認する。テストが成功していた場合、保留していた受信パケットを、本登録のフローエントリに従って転送する。テストが失敗していた場合、保留していた受信パケットを破棄し、ＯＦＣ１２（１２−ｋ、ｋ＝１〜ｚ）に対してエラーを返す。その後、テストパケットを破棄し、テストを完了する。
【０１７２】
［ＯＦＣの内部構成例］
図１４を参照して、本発明に係る閉路形成未然防止システムにおけるＯＦＣの内部構成例について説明する。
【０１７３】
ＯＦＣ１２（１２−ｋ、ｋ＝１〜ｚ）の各々は、経路計算部１２１と、テストＩＤ生成部１２２と、フローエントリ仮登録部１２３を備える。
【０１７４】
経路計算部１２１は、ＯＦＳ１１（１１−ｊ、ｊ＝１〜ｙ）から問い合わせを受けた際、経路を計算する。
【０１７５】
テストＩＤ生成部１２２は、テストを一意に識別可能なテストＩＤを生成する。
【０１７６】
フローエントリ仮登録部１２３は、ＯＦＳ１１（１１−ｊ、ｊ＝１〜ｙ）に、経路計算結果に基づくフローエントリを仮登録する。このとき、フローエントリ仮登録部１２３は、仮登録されるフローエントリの中に、アクションフィールドとテストＩＤフィールドとを設ける。アクションフィールドには、仮登録である旨の内容のデータを格納する。テストＩＤフィールドには、テストＩＤの値を格納する。
【０１７７】
［ハードウェアの例示］
ホスト１０（１０−ｉ、ｉ＝１〜ｘ）及びＯＦＣ１２（１２−ｋ、ｋ＝１〜ｚ）の例として、ＰＣ（パソコン）、アプライアンス（ａｐｐｌｉａｎｃｅ）、ワークステーション、メインフレーム、スーパーコンピュータ等の計算機を想定している。他にも、ホスト１０（１０−ｉ、ｉ＝１〜ｘ）の例として、携帯電話機、スマートフォン、スマートブック、カーナビ（カーナビゲーションシステム）、携帯型ゲーム機、家庭用ゲーム機、携帯型音楽プレーヤー、ハンディターミナル、ガジェット（電子機器）、双方向テレビ、デジタルチューナー、デジタルレコーダー、情報家電（ｉｎｆｏｒｍａｔｉｏｎ  ｈｏｍｅ  ａｐｐｌｉａｎｃｅ）、ＰＯＳ（Ｐｏｉｎｔ  ｏｆ  Ｓａｌｅ）端末、ＯＡ（Ｏｆｆｉｃｅ  Ａｕｔｏｍａｔｉｏｎ）機器、店頭端末・高機能コピー機、デジタルサイネージ（Ｄｉｇｉｔａｌ  Ｓｉｇｎａｇｅ：電子看板）等も考えられる。ホスト１０（１０−ｉ、ｉ＝１〜ｘ）及びＯＦＣ１２（１２−ｋ、ｋ＝１〜ｚ）は、車両や船舶、航空機等の移動体に搭載されていても良い。なお、ホスト１０（１０−ｉ、ｉ＝１〜ｘ）及びＯＦＣ１２（１２−ｋ、ｋ＝１〜ｚ）は、端末やサーバに限らず、中継機器や周辺機器でも良い。また、ホスト１０（１０−ｉ、ｉ＝１〜ｘ）及びＯＦＣ１２（１２−ｋ、ｋ＝１〜ｚ）は、計算機等に搭載される拡張ボードや、物理マシン上に構築された仮想マシン（ＶＭ：Ｖｉｒｔｕａｌ  Ｍａｃｈｉｎｅ）でも良い。
【０１７８】
ＯＦＳ１１（１１−ｊ、ｊ＝１〜ｙ）の例として、ネットワークスイッチ（ｎｅｔｗｏｒｋ  ｓｗｉｔｃｈ）を想定している。ネットワークスイッチの例として、Ｌ３スイッチ（ｌａｙｅｒ  ３  ｓｗｉｔｃｈ）、Ｌ４スイッチ（ｌａｙｅｒ  ４  ｓｗｉｔｃｈ）、Ｌ７スイッチ／アプリケーションスイッチ（ｌａｙｅｒ  ７  ｓｗｉｔｃｈ）、或いは、マルチレイヤスイッチ（ｍｕｌｔｉ−ｌａｙｅｒ  ｓｗｉｔｃｈ）等が考えられる。その他、ＯＦＳ１１（１１−ｊ、ｊ＝１〜ｙ）の例として、ルータ（ｒｏｕｔｅｒ）、プロキシ（ｐｒｏｘｙ）、ゲートウェイ（ｇａｔｅｗａｙ）、ファイアウォール（ｆｉｒｅｗａｌｌ）、ロードバランサ（ｌｏａｄ  ｂａｌａｎｃｅｒ：負荷分散装置）、帯域制御装置／セキュリティ監視制御装置（ｇａｔｅｋｅｅｐｅｒ）、基地局（ｂａｓｅ  ｓｔａｔｉｏｎ）、アクセスポイント（ＡＰ：Ａｃｃｅｓｓ  Ｐｏｉｎｔ）、通信衛星（ＣＳ：Ｃｏｍｍｕｎｉｃａｔｉｏｎ  Ｓａｔｅｌｌｉｔｅ）、或いは、複数の通信ポートを有する計算機等も考えられる。
【０１７９】
図示しないが、上記のようなホスト１０（１０−ｉ、ｉ＝１〜ｘ）、ＯＦＳ１１（１１−ｊ、ｊ＝１〜ｙ）、及びＯＦＣ１２（１２−ｋ、ｋ＝１〜ｚ）は、プログラムに基づいて駆動し所定の処理を実行するプロセッサと、当該プログラムや各種データを記憶するメモリと、ネットワークとの通信に用いられるインターフェースによって実現される。
【０１８０】
上記のプロセッサの例として、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）、ネットワークプロセッサ（ＮＰ：Ｎｅｔｗｏｒｋ  Ｐｒｏｃｅｓｓｏｒ）、マイクロプロセッサ（ｍｉｃｒｏｐｒｏｃｅｓｓｏｒ）、マイクロコントローラ、或いは、専用の機能を有する半導体集積回路（ＩＣ：Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）等が考えられる。
【０１８１】
上記のメモリの例として、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、ＥＥＰＲＯＭ（Ｅｌｅｃｔｒｉｃａｌｌｙ  Ｅｒａｓａｂｌｅ  ａｎｄ  Ｐｒｏｇｒａｍｍａｂｌｅ  Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）やフラッシュメモリ等の半導体記憶装置、ＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）やＳＳＤ（Ｓｏｌｉｄ  Ｓｔａｔｅ  Ｄｒｉｖｅ）等の補助記憶装置、又は、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）等のリムーバブルディスクや、ＳＤメモリカード（Ｓｅｃｕｒｅ  Ｄｉｇｉｔａｌ  ｍｅｍｏｒｙ  ｃａｒｄ）等の記憶媒体（メディア）等が考えられる。また、バッファ（ｂｕｆｆｅｒ）やレジスタ（ｒｅｇｉｓｔｅｒ）でも良い。或いは、ＤＡＳ（Ｄｉｒｅｃｔ  Ａｔｔａｃｈｅｄ  Ｓｔｏｒａｇｅ）、ＦＣ−ＳＡＮ（Ｆｉｂｒｅ  Ｃｈａｎｎｅｌ  −  Ｓｔｏｒａｇｅ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、ＮＡＳ（Ｎｅｔｗｏｒｋ  Ａｔｔａｃｈｅｄ  Ｓｔｏｒａｇｅ）、ＩＰ−ＳＡＮ（ＩＰ  −  Ｓｔｏｒａｇｅ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）等を用いたストレージ装置でも良い。
【０１８２】
なお、上記のプロセッサ及び上記のメモリは、一体化していても良い。例えば、近年では、マイコン等の１チップ化が進んでいる。従って、電子機器等に搭載される１チップマイコンが、上記のプロセッサ及び上記のメモリを備えている事例が考えられる。
【０１８３】
上記のインターフェースの例として、ネットワーク通信に対応した基板（マザーボード、Ｉ／Ｏボード）やチップ等の半導体集積回路、ＮＩＣ（Ｎｅｔｗｏｒｋ  Ｉｎｔｅｒｆａｃｅ  Ｃａｒｄ）等のネットワークアダプタや同様の拡張カード、アンテナ等の通信装置、接続口（コネクタ）等の通信ポート等が考えられる。
【０１８４】
また、ネットワークの例として、インターネット、ＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、無線ＬＡＮ（Ｗｉｒｅｌｅｓｓ  ＬＡＮ）、ＷＡＮ（Ｗｉｄｅ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、バックボーン（Ｂａｃｋｂｏｎｅ）、ケーブルテレビ（ＣＡＴＶ）回線、固定電話網、携帯電話網、ＷｉＭＡＸ（ＩＥＥＥ  ８０２．１６ａ）、３Ｇ（３ｒｄ  Ｇｅｎｅｒａｔｉｏｎ）、専用線（ｌｅａｓｅ  ｌｉｎｅ）、ＩｒＤＡ（Ｉｎｆｒａｒｅｄ  Ｄａｔａ  Ａｓｓｏｃｉａｔｉｏｎ）、Ｂｌｕｅｔｏｏｔｈ（登録商標）、シリアル通信回線、データバス等が考えられる。
【０１８５】
なお、ホスト１０（１０−ｉ、ｉ＝１〜ｘ）、ＯＦＳ１１（１１−ｊ、ｊ＝１〜ｙ）、及びＯＦＣ１２（１２−ｋ、ｋ＝１〜ｚ）は、物理マシン上に構築された仮想マシン（Ｖｉｒｔｕａｌ  Ｍａｃｈｉｎｅ（ＶＭ））でも良い。
【０１８６】
また、ホスト１０（１０−ｉ、ｉ＝１〜ｘ）、ＯＦＳ１１（１１−ｊ、ｊ＝１〜ｙ）、及びＯＦＣ１２（１２−ｋ、ｋ＝１〜ｚ）内の各部（内部構成）は、モジュール（ｍｏｄｕｌｅ）、コンポーネント（ｃｏｍｐｏｎｅｎｔ）、或いは専用デバイス、又はこれらの起動（呼出）プログラムでも良い。
【０１８７】
但し、実際には、これらの例に限定されない。
【０１８８】
＜まとめ＞
以上のように、本発明では、オープンフロー（ＯｐｅｎＦｌｏｗ）ネットワークにおける閉路形成を未然に防止する。
【０１８９】
具体的には、本発明は、１個のＯＦＣが複数のＯＦＳを管理するネットワークが複数あり、それらの組み合わせにより大きなネットワークが形成されているオープンフローネットワークシステムにおいて、複数あるＯＦＣ等のコントローラ同士が相互に連携する構成要素や処理手順を必要とせず、閉路を形成するようなフローエントリの登録を未然に防止する。
【０１９０】
本発明では、ＯＦＣで導出したフローエントリをＯＦＳに登録するに先立って、閉路が形成されることがないか評価する。
【０１９１】
また、本発明では、経路評価を仮登録のフローエントリ及びテストパケットを用いて実施する。
【０１９２】
また、本発明では、経路評価に際して、テストパケットの挙動のモニタリングする構成要素や処理手順、又は結果を収集して分析する構成要素や処理手順を必要とせず、テストパケットとＯＦＳ群の相互作用だけにより、テストの開始からテスト結果の判定、テスト結果の反映に至るまで、自律的に実施できる。
【０１９３】
本発明は、ＯＦＣのソフトウェアの更新、及び、ＯＦＳのファームウェアの更新のみで実現できる。
【０１９４】
本発明は、オープンフローネットワークシステムにおける閉路形成のテストに利用できる。
【０１９５】
以上、本発明の実施形態を詳述してきたが、実際には、上記の実施形態に限られるものではなく、本発明の要旨を逸脱しない範囲の変更があっても本発明に含まれる。
【０１９６】
なお、本出願は、日本出願番号２０１０−２５７７８１に基づく優先権を主張するものであり、日本出願番号２０１０−２５７７８１における開示内容は引用により本出願に組み込まれる。
【図１】
2012066830.tif 000003
【図２】
2012066830.tif 000004
【図３】
2012066830.tif 000005
【図４Ａ】
2012066830.tif 000006
【図４Ｂ】
2012066830.tif 000007
【図５】
2012066830.tif 000008
【図６】
2012066830.tif 000009
【図７】
2012066830.tif 000010
【図８】
2012066830.tif 000011
【図９】
2012066830.tif 000012
【図１０Ａ】
2012066830.tif 000013
【図１０Ｂ】
2012066830.tif 000014
【図１０Ｃ】
2012066830.tif 000015
【図１１】
2012066830.tif 000016
【図１２】
2012066830.tif 000017
【図１３】
2012066830.tif 000018
【国際調査報告】
2012066830.tif 000019
2012066830.tif 000020
2012066830.tif 000021