JP2006180358A - パケット転送装置、方法、およびプログラム - Google Patents

Abstract

【課題】転送経路変更の際に行われるパケット転送テーブルの検索処理を簡素化かつ高速化する。
【解決手段】パケット転送状況に応じて経路変更の可否が変化するパケット転送経路を変更する際、パケット転送装置１〜４の転送制御部２９において、パケット転送テーブル３１を検索して対象エントリのフラグ２（変更要否情報）を変更要に初期化し、この初期化から少なくとも所定期間以上経過するごとにパケット転送テーブル３１の各エントリから当該フラグ２が変更要を示す対象エントリを検索し、検索した対象エントリについて転送経路の変更可否を確認し、その変更可が確認された対象エントリについてパケットの転送経路を変更する。
【選択図】 図４

Description

本発明は、パケット転送技術に関し、特にトラヒックエンジニアリングにより転送経路を動的に変更する際、その着側のパケット転送装置でのパケット到着順序を保証する転送経路変更技術に関する。

一般的に、ＩＰネットワークでは、ＯＳＰＦ（Open Shortest Path First）などのルーチングプロトコルを用いて最短経路ベースのルーチングによるベストエフォート転送を行っている。
このような最短経路ベースのルーチングによれば、ネットワーク資源の消費を抑制しつつ、到達性を確保できるが、例えば、多数のユーザＩＰフローがある経路に集中して輻輳が発生する可能性があるなど、信頼性や通信品質の観点からは経路制御の自由度が低かった。

この問題を解決するための技術として、ＩＰネットワーク内の負荷状況に応じて動的にトラヒックを分散させるトラヒックエンジニアリングが検討されている。このようなトラヒックエンジニアリングを採用したＩＰネットワークでは、加入者ユーザ間の通信に対し、使用帯域に応じて転送経路を割り当てる。
すなわち、各パケット転送装置において、同一宛先に対して複数の転送方路を用意しておき、特定の転送方路の輻輳を検出した際に、該当経路へ転送しようとしていたパケットを代替経路に転送する。この技術により、トラヒックを各経路に分散させることが可能となり、信頼性や通信品質を向上させることが可能となる。

しかし、上述の技術では、輻輳経路上のユーザフローが別経路に無瞬断にマッピングされるため、変更経路の着側のパケット転送装置で、パケットの到着順序逆転が発生する可能性が高い。

このようなトラヒックエンジニアリングを用いる際にパケットの到着順序逆転を防止する技術として、パケット転送装置が定期的にパケット転送テーブルの各エントリの参照状況を管理し、転送経路の変更が必要になった際に、所定期間参照されていない転送テーブルエントリのみを削除あるいは更新する技術が考えられる。
これにより、連続的に転送が行われているユーザ間通信は旧経路で転送し、パケットの到着順序が発生しないと判断されるユーザ間通信から新経路にマッピングすることが可能となる。

なお、出願人は、本明細書に記載した先行技術文献情報で特定される先行技術文献以外には、本発明に関連する先行技術文献を出願時までに発見するには至らなかった。
Yuuichi Naruse et,al. "IP-in-IPv6 Overlay Networking Technology for a Terabit-class Super-network",NTT Technical Review,VOL.2,NO.3 Mar.2004 Kenichi Matsui et,al. "Cut-through Optical Path Control Technology for a Terabit-class Super-network",NTT Technical Review,VOL.2,NO.3 Mar.2004

このような従来技術では、パケットの転送状況に応じて経路変更の可否が変化するため、経路変更不可の経路については、例えば所定期間後に改めてパケット転送テーブルから当該エントリを検索して経路変更を行う必要がある。
しかしながら、経路変更の対象となる条件と転送テーブルエントリの検索キーは一対多の関係を持つ可能性もあるため、経路変更制御の対象となる転送テーブルエントリを検索するには、その検索ごとに、経路変更条件として指定された宛先ユーザアドレスなど比較的データ量の多い情報を用いてパケット転送テーブルに登録されているすべてのエントリについてその一致不一致を検査する必要があり、必要以上に制御負荷が高くなるという問題があった。

本発明はこのような課題を解決するためのものであり、転送経路変更の際に行われるパケット転送テーブルの検索処理を簡素化かつ高速化でき、トラヒックエンジニアリング時の経路変更制御負荷を削減できるパケット転送装置、方法、およびプログラムを提供することを目的としている。

このような目的を達成するために、本発明にかかるパケット転送装置は、通信ネットワークに設けられて、入力されたパケットをその宛先アドレスに基づき所定の転送経路へ転送するパケット転送装置であって、パケットの各宛先アドレスとそのパケットの転送経路を示す転送経路情報と転送経路変更の対象であるか否かを示す変更要否情報との組をエントリとして複数有するパケット転送テーブルを記憶する記憶部と、入力されたパケットの宛先アドレスに対応する転送経路情報をパケット転送テーブルから取得しその転送経路情報に応じて当該パケットを転送する転送処理部と、パケット転送テーブルの各エントリのうち転送経路変更の対象となる対象エントリについて当該宛先アドレスを持つパケットの転送経路を変更する転送制御部とを備え、転送制御部は、パケット転送テーブルを検索して対象エントリの変更要否情報を変更要に初期化する初期化手段と、初期化から少なくとも所定期間以上経過するごとにパケット転送テーブルの各エントリから当該変更要否情報が変更要を示す対象エントリを検索する変更対象検索手段と、検索した対象エントリについて転送経路の変更可否を確認する変更可否確認手段と、変更可が確認された対象エントリについてその転送経路情報の更新または当該対象エントリの削除を行うことにより当該宛先アドレスを持つパケットの転送経路を変更する経路変更手段とを有している。

この際、変更可否確認手段で、所定期間にわたり当該宛先アドレスのパケットが転送されていないどうかに基づいて当該転送経路の変更可否を判断するようにしてもよい。

さらに、パケット転送テーブルで、エントリごとに当該転送経路の変更可否を示す変更可否情報をさらに有し、転送処理部で、パケット転送テーブルの各エントリのうちパケット転送の際に参照したエントリについてその変更可否情報を変更不可に設定し、変更対象検索手段で、検索した対象エントリのうち当該変更可否情報が変更不可を示すエントリについて転送経路の変更を行わず当該変更可否情報を変更可に設定するようにしてもよい。

この際、変更対象検索手段で、所定期間として、少なくとも、対象エントリの宛先アドレスを持つパケットが切替元となる旧経路を介して対向装置まで到達するのに要する伝搬遅延時間の時間長を用いるようにしてもよい。
あるいは、変更対象検索手段で、所定期間として、少なくとも、対象エントリの宛先アドレスを持つパケットが切替元となる旧経路を介して対向装置まで到達するのに要する伝搬遅延時間から切替先となる新経路を介して対向装置まで到達するのに要する伝搬遅延時間を減算して得られた差分の時間長を用いるようにしてもよい。

また、本発明にかかるパケット転送方法は、通信ネットワークに設けられたパケット転送装置により、入力されたパケットをその宛先アドレスに基づき所定の転送経路へ転送するパケット転送方法であって、パケットの各宛先アドレスとそのパケットの転送経路を示す転送経路情報と転送経路変更の対象であるか否かを示す変更要否情報との組をエントリとして複数有するパケット転送テーブルを記憶部で記憶する記憶ステップと、入力されたパケットの宛先アドレスに対応する転送経路情報をパケット転送テーブルから取得しその転送経路情報に応じて当該パケットを転送する転送処理ステップと、パケット転送テーブルの各エントリのうち転送経路変更の対象となる対象エントリについて当該宛先アドレスを持つパケットの転送経路を変更する転送制御ステップとを備え、転送制御ステップは、パケット転送テーブルを検索して対象エントリの変更要否情報を変更要に初期化する初期化ステップと、初期化から少なくとも所定期間以上経過するごとにパケット転送テーブルの各エントリから当該変更要否情報が変更要を示す対象エントリを検索する変更対象検索ステップと、検索した対象エントリについて転送経路の変更可否を確認する変更可否確認ステップと、変更可が確認された対象エントリについてその転送経路情報の更新または当該対象エントリの削除を行うことにより当該宛先アドレスを持つパケットの転送経路を変更する経路変更ステップとを有している。

この際、変更可否確認ステップで、所定期間にわたり当該宛先アドレスのパケットが転送されていないどうかに基づいて当該転送経路の変更可否を判断するようにしてもよい。

さらに、パケット転送テーブルで、エントリごとに当該転送経路の変更可否を示す変更可否情報をさらに有し、転送処理ステップで、パケット転送テーブルの各エントリのうちパケット転送の際に参照したエントリについてその変更可否情報を変更不可に設定し、変更対象検索ステップで、検索した対象エントリのうち当該変更可否情報が変更不可を示すエントリについて転送経路の変更を行わず当該変更可否情報を変更可に設定するようにしてもよい。

この際、変更対象検索ステップで、所定期間として、少なくとも、対象エントリの宛先アドレスを持つパケットが切替元となる旧経路を介して対向装置まで到達するのに要する伝搬遅延時間の時間長を用いるようしてもよい。
あるいは、変更対象検索ステップで、所定期間として、少なくとも、対象エントリの宛先アドレスを持つパケットが切替元となる旧経路を介して対向装置まで到達するのに要する伝搬遅延時間から切替先となる新経路を介して対向装置まで到達するのに要する伝搬遅延時間を減算して得られた差分の時間長を用いるようにしてもよい。

また、本発明にかかるプログラムは、通信ネットワークに設けられ、入力されたパケットをその宛先アドレスに基づき所定の転送経路へ転送するパケット転送装置のコンピュータに、パケットの各宛先アドレスとそのパケットの転送経路を示す転送経路情報と転送経路変更の対象であるか否かを示す変更要否情報との組をエントリとして複数有するパケット転送テーブルを記憶部で記憶する記憶ステップと、入力されたパケットの宛先アドレスに対応する転送経路情報をパケット転送テーブルから取得しその転送経路情報に応じて当該パケットを転送する転送処理ステップと、パケット転送テーブルの各エントリのうち転送経路変更の対象となる対象エントリについて当該宛先アドレスを持つパケットの転送経路を変更する転送制御ステップとを実行させ、転送制御ステップは、パケット転送テーブルを検索して対象エントリの変更要否情報を変更要に初期化する初期化ステップと、初期化から少なくとも所定期間以上経過するごとにパケット転送テーブルの各エントリから当該変更要否情報が変更要を示す対象エントリを検索する変更対象検索ステップと、検索した対象エントリについて転送経路の変更可否を確認する変更可否確認ステップと、変更可が確認された対象エントリについてその転送経路情報の更新または当該対象エントリの削除を行うことにより当該宛先アドレスを持つパケットの転送経路を変更する経路変更ステップとを有している。

この際、変更可否確認ステップで、所定期間にわたり当該宛先アドレスのパケットが転送されていないどうかに基づいて当該転送経路の変更可否を判断するようにしてもよい。

さらに、転送処理ステップで、パケット転送テーブルの各エントリのうちパケット転送の際に参照したエントリについて、その転送経路の変更可否を示す変更可否情報を変更不可に設定し、変更対象検索ステップで、検索した対象エントリのうち当該変更可否情報が変更不可を示すエントリについて転送経路の変更を行わず当該変更可否情報を変更可に設定するようにしてもよい。

また、変更対象検索ステップで、所定期間として、少なくとも、対象エントリの宛先アドレスを持つパケットが切替元となる旧経路を介して対向装置まで到達するのに要する伝搬遅延時間の時間長を用いるようにしてもよい。
あるいは、変更対象検索ステップで、所定期間として、少なくとも、対象エントリの宛先アドレスを持つパケットが切替元となる旧経路を介して対向装置まで到達するのに要する伝搬遅延時間から切替先となる新経路を介して対向装置まで到達するのに要する伝搬遅延時間を減算して得られた差分の時間長を用いるようにしてもよい。

本発明によれば、パケット転送状況に応じて経路変更の可否が変化するパケット転送経路を変更する際、パケット転送テーブルを検索して対象エントリの変更要否情報を変更要に初期化し、少なくとも所定期間以上経過するごとにパケット転送テーブルの各エントリから当該変更要否情報が変更要を示す対象エントリを検索し、検索した対象エントリについて転送経路の変更可否を確認し、その変更可が確認された対象エントリについてパケットの転送経路を変更するようにしたので、転送経路変更の際に必要なパケット転送テーブルの検索処理において、変更要否を示す変更要否情報を確認するだけで対象エントリを検索できる。

したがって、経路変更対象となる対象エントリをパケット転送テーブルから検索する際、経路変更条件として指定された宛先ユーザアドレスなど、比較的データ量の多い情報を用いてパケット転送テーブルに登録されているすべてのエントリについて所定期間ごとにその一致不一致を検査する必要がなくなり、パケット転送テーブルの検索処理を簡素化かつ高速化できる。
これにより、トラヒックエンジニアリングなどに基づきパケット転送装置で経路変更制御を行う際、その経路管理処理に必要な負荷を削減でき、その経路変更制御の高速化を実現することが可能となる。

次に、本発明の実施の形態について図面を参照して説明する。
［通信ネットワーク］
まず、図１を参照して、本発明の一実施の形態にかかるパケット転送装置を設置した通信ネットワークのネットワークモデル例について説明する。図１は、本発明の一実施の形態にかかるパケット転送装置を設置した通信ネットワークのネットワークモデル例を示すブロック図である。

この通信ネットワークは、パケット転送装置１〜４、フレーム転送装置５，６、および光パス交換機７，８から構成され、各端末９〜２４は、各ユーザ網１Ａ〜４Ａを経由してパケット転送装置１〜４に収容されている。これらパケット転送装置１〜４間は、フレーム転送装置５，６および光パス交換機７，８によって接続されている。
端末９にはユーザ＃１というアドレスが割り当てられており、端末１０にはユーザ＃２というアドレスが割り当てられており、端末１１にはユーザ＃３というアドレスが割り当てられており、端末１２にはユーザ＃４というアドレスが割り当てられており、端末１３にはユーザ＃５というアドレスが割り当てられており、端末１４にはユーザ＃６というアドレスが割り当てられている。

また、端末１５にはユーザ＃７というアドレスが割り当てられており、端末１６にはユーザ＃８というアドレスが割り当てられており、端末１７にはユーザ＃９というアドレスが割り当てられており、端末１８にはユーザ＃１０というアドレスが割り当てられており、端末１９にはユーザ＃１１というアドレスが割り当てられており、端末２０にはユーザ＃１２というアドレスが割り当てられており、端末２１にはユーザ＃１３というアドレスが割り当てられており、端末２２にはユーザ＃１４というアドレスが割り当てられており、端末２３にはユーザ＃１５というアドレスが割り当てられており、端末２４にはユーザ＃１６というアドレスが割り当てられている。

パケット転送装置１〜４とフレーム転送装置５，６、およびパケット転送装置１〜４間は、光波長などの光パス（図示せず）で接続されている。光パス交換機７，８は、光パスをスイッチングし、各装置間の接続関係を変更する機能を有している。
フレーム転送装置５，６は、パケット転送装置１〜４間で転送されるパケットの中継処理を実施する。
端末間のパケットは、送信側端末から、発側パケット転送装置に転送された後、フレーム転送装置を経由して、着側パケット転送装置に転送され、宛先端末に転送される場合と、送信側端末から、発側パケット転送装置に転送された後、フレーム転送装置を経由せず、着側パケット転送装置に転送され、宛先端末に転送される場合がある。

パケット転送装置１〜４、フレーム転送装置５，６、および光パス交換機７，８から構成されるバックボーンネットワークをコアネットワーク２５とし、端末で構成されるネットワークをインターネット２６とする。
フレーム転送装置５，６を経由しない場合の転送はカットスルー光パス転送と呼ばれ、トラヒック需要の多いパケット転送装置間に設置される。また、トラヒック需要の変化とともに、光パス交換機の装置間接続関係を制御し、カットスルー光パス転送を実施するパケット転送装置間をトラヒック需要とともに変更させることが可能である。

図２は、本発明のパケット転送装置を設置した通信ネットワークの物理モデルおよび論理モデルの一例である。
パケット転送装置１〜４間は、複数の転送経路により接続されている。これら転送経路には、光パス（光波長、光ファイバ）により確立される物理的な転送経路と、ＩＰネットワークにおけるＩＰ経路や、ＭＰＬＳ（Multi Protocol Label Switching）ネットワークにおけるＬＳＰ（Label Switch Path）などの論理的な転送経路がある。
本実施の形態では、光パスが物理的な転送経路を、ＬＳＰが論理的な転送経路を示している。

例えば、パケット転送装置１からパケット転送装置３へは、光パス１０１、フレーム転送装置５、波長パス１０３からなる物理的な転送経路を用いて確立される論理的な転送経路ＬＳＰ１１０と、光パス１０５、フレーム転送装置６、波長パス１０７からなる物理的な転送経路を用いて確立される論理的な転送経路ＬＳＰ１１３と、光パス１０７からなる物理的な転送経路を用いて確立される論理的な転送経路ＬＳＰ１１６により接続されている。それぞれの論理的な転送経路には、その経路を識別するための経路識別子が付与される。

論理的な転送経路は、全パケット転送装置間に設置される。本実施の形態では、ＭＰＬＳネットワークのＬＳＰを採用しているため、論理的な転送経路ＬＳＰ１１０〜１３５は、パケット転送装置間にフルメッシュ状に設置される。
本実施の形態では、１本の光パスが１本の物理リンクを専有しているが、例えば、ＷＤＭ（Wavelength Division Multiplexing）などの技術を採用すると、複数本の光パスを１本の物理リンクに収容することが可能となる。

図３は、本発明のパケット転送装置を設置した図２のネットワークにおける、パケット転送装置とパケット転送装置間の転送経路の一例である。
本実施の形態では、光パス１０１、フレーム転送装置５、光パス１０３上に確立されたＬＳＰ１１０、光パス１０５、フレーム転送装置６、光パス１０７上に確立されたＬＳＰ１１３、光パス１０９上に確立されたＬＳＰ１１６が存在する。
コアネットワーク内では、ＬＳＰ番号を記述したシムヘッダによりパケットはカプセル化され、ＬＳＰ番号に応じて転送が行われる。

また、パケット転送装置１と端末９はリンク１２７を経由して接続されており、パケット転送装置１と端末１０はリンク１２８を経由して接続されており、パケット転送装置１と端末１１はリンク１２９を経由して接続されており、パケット転送装置１と端末１２はリンク１３０を経由して接続されており、パケット転送装置１と端末１７はリンク１３１を経由して接続されており、パケット転送装置１と端末１８はリンク１３２を経由して接続されており、パケット転送装置１と端末１９はリンク１３３を経由して接続されており、パケット転送装置１と端末２０はリンク１３４を経由して接続されている。

［パケット転送装置］
次に、図４を参照して、本発明の一実施の形態にかかるパケット転送装置について説明する。図４は、本発明の一実施の形態にかかるパケット転送装置の構成を示すブロック図である。ここでは、パケット転送装置１を例として説明するが、他のパケット転送装置２〜４についても同様の構成を有している。

パケット転送装置１は、入力インタフェース部２７、転送処理部２８、転送制御部２９、出力インタフェース部３０で構成される。これら各部は、ＣＰＵでプログラムを実行することによりハードウェアとプログラムとを協働させて機能部を実現させる演算処理部（図示せず）や、上記プログラムや後述するパケット転送テーブル３１などの各種情報を記憶するハードディスクやメモリなどの記憶装置（図示せず）、さらにはネットワークを介して各種パケットを送受信する通信インタフェース部（図示せず）から構成されている。

入力インタフェース部２７は、受信したフレームのヘッダ領域がＭＰＬＳのシムヘッダであった際は、そのフレームをコアフレームと判断し、シムヘッダを除去することでデカプセル化してユーザパケットを抽出し、そのユーザパケットを転送処理部２８へ転送する機能と、受信したフレームのヘッダ領域がユーザアドレスであった際は、そのフレームをユーザパケットと判断し、転送処理部２８へ転送する機能とを有している。

転送処理部２８は、パケット転送テーブル３１を保有している。
パケット転送テーブル３１は、受信したユーザパケットの宛先ユーザアドレスから、出力先のＬＳＰを示すＬＳＰ番号、当該宛先ユーザアドレスを転送する転送経路の切替可否を示すフラグ１（変更可否情報）、および当該宛先ユーザアドレスを転送する転送経路の切替要否を示すフラグ２（変更要否情報）を導く機能を有している。
転送処理部２８は、入力インタフェース部２７から受信したユーザパケットの宛先ユーザアドレスをキーとしてパケット転送テーブル３１を検索し、そのユーザパケットの出力先ＬＳＰ番号を導く機能と、ユーザパケットを転送するごとに、パケット転送テーブル３１においてヒットしたエントリのフラグ１をセットして変更不可と設定する機能を有している。

図５は、本実施の形態にかかるパケット転送装置で用いるパケット転送テーブルの構成例である。
パケット転送テーブル３１において、通常時は各エントリは経路変更対象外でありそれぞれのフラグ２はすべてリセット状態（変更対象外）にあり、経路変更制御時のみフラグ２がセットされて変更対象となるエントリが存在する。本実施の形態では、宛先ユーザアドレス＃９および＃１０におけるエントリ更新要求が発生していることになる。

転送制御部２９は、変更経路管理テーブル３２およびタイマ３３を保有している。
図６は、本実施の形態にかかるパケット転送装置で用いる変更経路管理テーブルの構成例である。変更経路管理テーブル３２は、例えば外部から受信した、ある宛先ユーザアドレスに関する出力先ＬＳＰの経路変更通知に記述されていた、宛先ユーザアドレスおよび変更後のＬＳＰ番号を指示情報として保有する機能を有している。
タイマ３３は、所定期間ごとにタイマ値を増加させる機能を有している。本実施の形態では、例えば１ミリ秒ごとにタイマ値を１増加させる。

転送制御部２９は、ある宛先ユーザアドレスに関する出力先ＬＳＰの経路変更通知について、その経路変更通知の宛先ユーザアドレスおよびＬＳＰ番号の組を変更経路管理テーブル３２に追加する機能と、その宛先ユーザアドレスを検索キーとして転送処理部２８のパケット転送テーブル３１を検索し、ヒットしたエントリのフラグ１をリセットするとともにフラグ２をセットする機能（初期化手段）と、タイマ３３のタイマ値が予め定められた規定値に達した際に、転送処理部２８のパケット転送テーブル３１においてフラグ２がセットされている対象エントリを検索する機能（変更対象検索手段）とを有している。

さらに、転送制御部２９は、ヒットした対象エントリのフラグ１がリセット状態かどうかチェックして当該エントリの経路変更可否を確認する機能（変更可否確認手段）と、経路変更可であればそのエントリに記述されたＬＳＰ番号を変更経路管理テーブル３２に保存されているＬＳＰ番号に書き換え、変更経路管理テーブル３２からその宛先ユーザアドレスおよびＬＳＰ番号に関する情報を削除する機能（経路変更手段）と、タイマ３３のタイマ値を初期化する機能とを有している。

タイマ値の初期化は、経路変更通知に応じて処理を開始し、最初にフラグ１をリセットするとともにフラグ２をセットした後に１回実行される。
その後、タイマ３３の規定値に応じた所定期間が経過した後に経路変更処理が行われて各対象エントリに対する処理が一巡するごとにタイマ値が初期化される。この規定値は、パケット転送遅延時間の異なる経路間で経路変更を行ってもパケット到着順序が保証される十分な時間を規定する値を用いればよい。

出力インタフェース部３０は、出力リンク特定テーブル３４を保有している。
図７は、本実施の形態にかかるパケット転送装置で用いる出力リンク特定テーブルの構成例である。出力リンク特定テーブル３４は、ヘッダ情報から、出力リンクを特定する機能を有している。
出力インタフェース部３０は、転送処理部２８から受信したパケットの宛先アドレスをキーに出力リンク特定テーブル３４を検索し、対応するフレームを出力リンクへ送信する機能と、受信したフレームのシムヘッダに記述されたＬＳＰ番号をキーに出力リンク特定テーブル３４を検索し、対応するフレームを出力リンクへ送信する機能を有している。

このように、本実施の形態では、パケット転送装置１〜４において、パケット転送状況に応じて経路変更の可否が変化するパケット転送経路を変更する際、パケット転送テーブル３１を検索して対象エントリのフラグ２（変更要否情報）を変更要に初期化し、少なくとも所定期間以上経過するごとにパケット転送テーブル３１の各エントリから当該フラグ２が変更要を示す対象エントリを検索し、検索した対象エントリについて転送経路の変更可否を確認し、その変更可が確認された対象エントリについてパケットの転送経路を変更するようにしたので、転送経路変更の際に必要なパケット転送テーブル３１の検索処理において、変更要否を示すフラグ２を確認するだけで対象エントリを検索できる。

したがって、経路変更対象となる対象エントリをパケット転送テーブルから検索する際、経路変更条件として指定された宛先ユーザアドレスなど、比較的データ量の多い情報を用いてパケット転送テーブルに登録されているすべてのエントリについて所定期間ごとにその一致不一致を検査する必要がなくなり、パケット転送テーブルの検索処理を簡素化かつ高速化できる。
これにより、トラヒックエンジニアリングなどに基づきパケット転送装置で経路変更制御を行う際、その経路管理処理に必要な負荷を削減でき、その経路変更制御の高速化を実現することが可能となる。

［パケット転送動作］
次に、図３および図８を参照して、本実施の形態にかかるパケット転送装置の動作として、パケット転送動作について説明する。図８は、本実施の形態にかかるパケット転送装置のパケット転送動作を示す説明図である。

まず、ユーザ＃１の端末９とユーザ＃９の端末１７の間で通信が開始されたと仮定し、端末９から端末１７間へ送信されたパケットをユーザパケット２０１とする。
パケット転送装置１は、リンク１２７から、ユーザパケット２０１を、入力インタフェース部２７で受信する。入力インタフェース部２７は、受信したパケットがユーザパケットであると判断し、転送処理部２８へ転送する。

転送処理部２８は、ユーザパケット２０１を入力インタフェース部２７から受信した際に、その宛先ユーザアドレスであるユーザ＃９を検索キーとしてパケット転送テーブル３１を参照し、出力先転送経路を識別するためのＬＳＰ１１０が記述されたエントリ３５を検出し、エントリ３５のフラグ１（変更可否情報）をチェックし、変更可を示すリセット状態「０」に設定されているためこれを変更不可を示すセット状態「１」に設定する。
また、エントリ３５に記述されていた情報から、ユーザパケット２０１に対して、ＬＳＰ１１０の転送情報が記述されたシムヘッダを付与し、コアフレーム２０２を生成する。そして、転送処理部２８は、コアフレーム２０２を出力インタフェース部３０へ送信する。

出力インタフェース部３０は、コアフレーム２０２のシムヘッダ情報であるＬＳＰ１１０を検索キーとして出力リンク特定テーブル３４を参照して光パス１０１を特定し、コアフレーム２０２を光パス１０１へ出力する。

続いて、ユーザ＃１の端末９とユーザ＃２の端末１０の間で通信が開始されたと仮定し、端末９から端末１０間へ送信されたパケットをユーザパケット２０３とする。
パケット転送装置１は、リンク１２７から、ユーザパケット２０３を、入力インタフェース部２７で受信する。入力インタフェース部２７は、受信したパケットがユーザパケットであると判断し、転送処理部２８へ転送する。

転送処理部２８は、ユーザパケット２０３を入力インタフェース部２７から受信した際に、その宛先ユーザアドレスであるユーザ＃２を検索キーとしてパケット転送テーブル３１を参照する。この際、検出したエントリにＬＳＰ番号の記述がないため、パケット転送装置１自身が収容するユーザ宛のパケットであると判断し、ユーザパケット２０３をそのまま出力インタフェース部３０へ送信する。
出力インタフェース部３０は、ユーザパケット２０３の宛先アドレスであるユーザ＃２を検索キーとして出力リンク特定テーブル３４を参照し、出力リンク１２８を特定し、ユーザパケット２０３をリンク１２８へ出力する。

最後に、端末１７と端末９の間で通信が開始されたと仮定し、端末１７から端末９へ送信されたパケットをユーザパケット２０４とする。
ユーザパケット２０４は、パケット転送装置３において、シムヘッダを付与され、コアフレーム２０５としてパケット転送装置１へ送信される。
パケット転送装置１は、光パス１０１から、コアフレーム２０５を、入力インタフェース部２７で受信する。入力インタフェース部２７は、受信したパケットがコアフレームであると判断し、コアフレーム２０５のシムヘッダを除去することでユーザパケット２０４を抽出し、転送処理部２８へ転送する。

転送処理部２８は、ユーザパケット２０４を入力インタフェース部２７から受信した際に、その宛先ユーザアドレスであるユーザ＃１を検索キーとしてパケット転送テーブル３１を参照する。
この際、検出したエントリにＬＳＰ番号の記述がないため、パケット転送装置１自身が収容するユーザ宛のパケットであると判断し、ユーザパケット２０４をそのまま出力インタフェース部３０へ送信する。
出力インタフェース部３０は、ユーザパケット２０４の宛先アドレスであるユーザ＃１を検索キーとして出力リンク特定テーブル３４を参照し、出力リンク１２７を特定し、ユーザパケット２０４をリンク１２７へ出力する。

［経路変更動作］
次に、図９および図１０を参照して、本実施の形態にかかるパケット転送装置の動作として、経路変更動作について説明する。図９は、本実施の形態にかかるパケット転送装置の経路変更動作を示す説明図である。図１０は、本実施の形態にかかるパケット転送装置の経路変更処理を示すフローチャートである。
前述したパケット転送装置のパケット転送動作では、図８において、端末９と端末１７の間の通信はＬＳＰ１１０で示される転送経路を用いていた。ここでは、図９に示すように、所定の経路変更通知に基づいて、上記の通信の転送経路をＬＳＰ１１６で示される転送経路に変更する場合を例として説明する。

パケット転送装置１の転送制御部２９は、経路変更通知に応じて、図１０の経路変更処理を開始する。まず、経路変更通知に含まれる、宛先ユーザアドレスがユーザ＃９で検出される転送テーブルエントリのＬＳＰ番号をＬＳＰ１１６へ変更する指示情報と、宛先ユーザアドレスがユーザ＃１０で検出される転送テーブルエントリのＬＳＰ番号をＬＳＰ１１６へ変更する指示情報を、宛先ユーザアドレス「ユーザ＃９」を検索キーとしてＬＳＰ１１６を導くエントリと、宛先ユーザアドレス「ユーザ＃１０」を検索キーとしてＬＳＰ１１６を導くエントリとし、変更経路管理テーブル３２に保存する。

また、同時に、宛先ユーザアドレス「ユーザ＃９」を検索キーとしてパケット転送テーブル３１を検索して（ステップ３００）、ヒットしたエントリ３８のフラグ１（変更可否情報）をリセット状態「０」（変更可）に設定するとともに、フラグ２（変更要否情報）をセット状態「１」（変更要）に設定し（ステップ３０１：初期化手段）、宛先ユーザアドレス「ユーザ＃１０」を検索キーとしてパケット転送テーブル３１を検索して（ステップ３００）、ヒットしたエントリ３９のフラグ１（変更可否情報）をリセット状態「０」（変更可）に設定するとともにフラグ２（変更要否情報）をセット状態「１」（変更要）に設定する（ステップ３０１：初期化手段）。

続いて、転送制御部２９はタイマ３３を初期化して計時を開始する（ステップ３１０）。本実施の形態では、タイマ３３は規定値に基づき所定期間として１００ミリ秒を計測し、１００ミリ秒ごとにリセットされる（ステップ３１１）。

この所定期間として、経路変更対象となる対象エントリの宛先アドレスのパケットが、少なくとも当該パケット転送装置から切替元となる旧経路を介して転送先となるパケット転送装置などの対向装置まで到達するのに要する伝搬遅延時間以上の時間長を用いれば、過去に転送したパケットがすべて対向装置へ到達完了しているタイミングで経路変更動作を行うことになり、より安全な経路変更動作を実現できる。

あるいは、所定期間として、経路変更対象となる対象エントリの宛先アドレスのパケットが、切替元となる旧経路を介して対向装置まで到達するのに要する伝搬遅延時間から、切替先となる新経路を介して対向装置まで到達するのに要する伝搬遅延時間を減算して得られた差分以上の時間長を用いれば、旧経路を介して過去に転送したパケットと新経路を介して転送を開始したパケットの対向装置での到着順序が入れ替わらない（追い越さない）タイミングで経路変更動作を行うことになり、より安全な経路変更動作を実現できる。

このようにして、転送制御部２９は、ステップ３０１でのフラグの初期化以降において、少なくとも所定期間が経過するごとに経路変更制御を実施する。なお、経路変更制御を実施する間隔については、少なくとも所定期間以上すなわちパケット到着順序が保証される期間以上であればよく、一定の周期で実施する必要はない。例えば、所定期間について、対向パケット転送装置との間でＩＣＭＰ（Internet Control Message Protocol）のｐｉｎｇ（Packet InterNet Groper）パケットを定期的に送受信するなどして、対向パケット転送装置間のＲＴＴ（Round Trip Time：往復転送遅延時間）を算出し、このＲＴＴの変動に応じて動的に変更してもよい。

転送制御部２９は、タイマ３３が規定値に達した際（ステップ３１１：ＹＥＳ）、転送処理部２８のパケット転送テーブル３１においてフラグ２がセット（変更要）されているエントリを検索する（ステップ３１２：変更対象検索手段）。
この検索で対象エントリとしてエントリ３８がヒットした場合（ステップ３１３：ＹＥＳ）、検索したエントリ３８のフラグ１をチェックする（ステップ３１４：変更可否確認手段）。

ここで、ステップ３１０でタイマ３３が初期化されてからステップ３１１でタイマ３３が規定値に達するまでの所定期間に、エントリ３８が参照されておらず当該経路でパケット転送がなく、経路変更が安全に行える場合、エントリ３８のフラグ１はリセット状態（変更可）のままとなる。
このように、当該エントリ３８のフラグ１がリセット状態にある場合（ステップ３１４：ＹＥＳ）、当該エントリ３８を、変更経路管理テーブル３２に記述された情報に基づき更新する（ステップ３１５：経路変更手段）。ここでは、ＬＳＰ番号がＬＳＰ１１０からＬＳＰ１１６に更新される。この際、更新処理した指示情報に対応する変更経路管理テーブル３２内のエントリ３６を削除するとともに、フラグ２をリセット状態「０」（変更対象外）に設定する。

そして、転送制御部２９は、転送処理部２８のパケット転送テーブル３１において当該エントリ３８以降に記載されたエントリからフラグ２がセット（変更要）されているエントリの検索を再開する（ステップ３１７）。
この検索で対象エントリとしてエントリ３９がヒットした場合（ステップ３１８：ＹＥＳ）、ステップ３１４へ戻って、検索したエントリ３９のフラグ１をチェックする（ステップ３１４）。

ここで、ステップ３１０でタイマ３３が初期化されてからステップ３１１でタイマ３３が規定値に達するまでの期間に、エントリ３９が参照されて当該経路でパケット転送が行われ、経路変更が安全に行えない場合、エントリ３９のフラグ１はセット状態（変更不可）となっている。
このように、当該エントリ３９のフラグ１がセット状態にある場合（ステップ３１４：ＮＯ）、次にタイマ３３が規定値に達するまでの期間で経路変更が安全に行えるか否か再確認するため、そのフラグ１をリセット状態「０」（変更可）に設定する（ステップ３１６：変更対象検索手段）。
この結果、経路変更直前のパケット転送テーブル３７に対し、変更直後のパケット転送テーブルはパケット転送テーブル４０となり、エントリ３８，３９はそれぞれエントリ４１，４２に更新される。

この後、転送制御部２９は、転送処理部２８のパケット転送テーブル３１において当該エントリ３９以降に記載されたエントリからフラグ２がセット（変更要）されているエントリの検索を再開する（ステップ３１７）。この検索で対象エントリがヒットしなかった場合（ステップ３１８：ＮＯ）、ステップ３１０へ戻ってタイマ３３を初期化し、タイマが規定値に達するごとに周期的に前述したステップ３１２〜３１８の処理を繰り返し実行する。
ステップ３１３において、フラグ２がセット（変更要）されているエントリが存在しなかった際は（ステップ３１３：ＮＯ）、一連の経路変更処理を終了する。このとき、変更経路管理テーブル３２にはエントリが存在しないはずである。

このように、本実施の形態では、パケット転送装置１〜４において、パケット転送状況に応じて経路変更の可否が変化するパケット転送経路を変更する際、パケット転送テーブル３１を検索して対象エントリのフラグ２（変更要否情報）を変更要に初期化し、少なくとも所定期間以上経過するごとにパケット転送テーブル３１の各エントリから当該フラグ２が変更要を示す対象エントリを検索し、検索した対象エントリについて転送経路の変更可否を確認し、その変更可が確認された対象エントリについてパケットの転送経路を変更するようにしたので、転送経路変更の際に必要なパケット転送テーブル３１の検索処理において、変更要否を示すフラグ２を確認するだけで対象エントリを検索できる。

したがって、経路変更対象となる対象エントリをパケット転送テーブルから検索する際、経路変更条件として指定された宛先ユーザアドレスなど、比較的データ量の多い情報を用いてパケット転送テーブルに登録されているすべてのエントリについて所定期間ごとにその一致不一致を検査する必要がなくなり、パケット転送テーブルの検索処理を簡素化かつ高速化できる。
これにより、トラヒックエンジニアリングなどに基づきパケット転送装置で経路変更制御を行う際、その経路管理処理に必要な負荷を削減でき、その経路変更制御の高速化を実現することが可能となる。

また、経路変更可否を判断する際、パケット転送ごとにセットされるフラグ１（変更可否情報）と、パケット転送遅延時間の異なる経路間で経路変更を行ってもパケット到着順序が保証される十分な時間を計時するタイマ３３とを用いることにより、極めて簡素な処理および構成で経路変更可否を確実に判断できる。
なお、以上では、経路変更を安全に実行できるか否かについて、フラグ１とタイマ３３を用いて判断する場合を例として説明したが、これに限定されるものではなく、他の経路更新可否判断手段を用いてもよく、前述と同様の作用効果が得られる。

本発明の一実施の形態にかかるパケット転送装置を設置した通信ネットワークのネットワークモデル例を示すブロック図である。 本発明のパケット転送装置を設置した通信ネットワークの物理モデルおよび論理モデルの一例である。 本発明のパケット転送装置を設置した図２のネットワークにおける、パケット転送装置とパケット転送装置間の転送経路の一例である。 本発明の一実施の形態にかかるパケット転送装置の構成を示すブロック図である。 本実施の形態にかかるパケット転送装置で用いるパケット転送テーブルの構成例である。 本実施の形態にかかるパケット転送装置で用いる変更経路管理テーブルの構成例である。 本実施の形態にかかるパケット転送装置で用いる出力リンク特定テーブルの構成例である。 本実施の形態にかかるパケット転送装置のパケット転送動作を示す説明図である。 本実施の形態にかかるパケット転送装置の経路変更動作を示す説明図である。 本実施の形態にかかるパケット転送装置の経路変更処理を示すフローチャートである。

符号の説明

１，２，３，４…パケット転送装置、１Ａ〜４Ａ…ユーザ網、５，６…フレーム転送装置、７，８…光パス交換機、９〜２４…端末、２５…コアネットワーク、２６…インターネット、２７…入力インタフェース部、２８…転送処理部、２９…転送制御部、３０…出力インタフェース部、３１…パケット転送テーブル、３２…変更経路管理テーブル、３３…タイマ、３４…出力リンク特定テーブル、３５，３６，３８，３９，４１，４２…エントリ、３７…パケット転送テーブル（経路変更直前）、４０…パケット転送テーブル（経路変更直後）、１０１〜１０９…光パス、１１０〜１３５…ＬＳＰ、２０１，２０３，２０４…ユーザパケット、２０２，２０５…コアフレーム。

Claims (15)

1. 通信ネットワークに設けられて、入力されたパケットをその宛先アドレスに基づき所定の転送経路へ転送するパケット転送装置であって、
   パケットの各宛先アドレスとそのパケットの転送経路を示す転送経路情報と転送経路変更の対象であるか否かを示す変更要否情報との組をエントリとして複数有するパケット転送テーブルを記憶する記憶部と、
   入力されたパケットの宛先アドレスに対応する転送経路情報を前記パケット転送テーブルから取得しその転送経路情報に応じて当該パケットを転送する転送処理部と、
   前記パケット転送テーブルの各エントリのうち転送経路変更の対象となる対象エントリについて当該宛先アドレスを持つパケットの転送経路を変更する転送制御部と
   を備え、
   前記転送制御部は、前記パケット転送テーブルを検索して前記対象エントリの変更要否情報を変更要に初期化する初期化手段と、少なくとも所定期間以上経過するごとに前記パケット転送テーブルの各エントリから当該変更要否情報が変更要を示す対象エントリを検索する変更対象検索手段と、検索した前記対象エントリについて転送経路の変更可否を確認する変更可否確認手段と、変更可が確認された対象エントリについてその転送経路情報の更新または当該対象エントリの削除を行うことにより当該宛先アドレスを持つパケットの転送経路を変更する経路変更手段とを有する
   ことを特徴とするパケット転送装置。
2. 請求項１に記載のパケット転送装置において、
   前記変更可否確認手段は、前記所定期間にわたり当該宛先アドレスのパケットが転送されていないどうかに基づいて当該転送経路の変更可否を判断することを特徴とするパケット転送装置。
3. 請求項２に記載のパケット転送装置において、
   前記パケット転送テーブルは、前記エントリごとに当該転送経路の変更可否を示す変更可否情報をさらに有し、
   前記転送処理部は、前記パケット転送テーブルの各エントリのうちパケット転送の際に参照したエントリについてその変更可否情報を変更不可に設定し、
   前記変更対象検索手段は、検索した対象エントリのうち当該変更可否情報が変更不可を示すエントリについて転送経路の変更を行わず当該変更可否情報を変更可に設定することを特徴とするパケット転送装置。
4. 請求項１に記載のパケット転送装置において、
   前記変更対象検索手段は、前記所定期間として、少なくとも、対象エントリの宛先アドレスを持つパケットが切替元となる旧経路を介して対向装置まで到達するのに要する伝搬遅延時間の時間長を用いることを特徴とするパケット転送装置。
5. 請求項１に記載のパケット転送装置において、
   前記変更対象検索手段は、前記所定期間として、少なくとも、対象エントリの宛先アドレスを持つパケットが切替元となる旧経路を介して対向装置まで到達するのに要する伝搬遅延時間から切替先となる新経路を介して対向装置まで到達するのに要する伝搬遅延時間を減算して得られた差分の時間長を用いることを特徴とするパケット転送装置。
6. 通信ネットワークに設けられたパケット転送装置により、入力されたパケットをその宛先アドレスに基づき所定の転送経路へ転送するパケット転送方法であって、
   パケットの各宛先アドレスとそのパケットの転送経路を示す転送経路情報と転送経路変更の対象であるか否かを示す変更要否情報との組をエントリとして複数有するパケット転送テーブルを記憶部で記憶する記憶ステップと、
   入力されたパケットの宛先アドレスに対応する転送経路情報を前記パケット転送テーブルから取得しその転送経路情報に応じて当該パケットを転送する転送処理ステップと、
   前記パケット転送テーブルの各エントリのうち転送経路変更の対象となる対象エントリについて当該宛先アドレスを持つパケットの転送経路を変更する転送制御ステップと
   を備え、
   前記転送制御ステップは、前記パケット転送テーブルを検索して前記対象エントリの変更要否情報を変更要に初期化する初期化ステップと、少なくとも所定期間以上経過するごとに前記パケット転送テーブルの各エントリから当該変更要否情報が変更要を示す対象エントリを検索する変更対象検索ステップと、検索した前記対象エントリについて転送経路の変更可否を確認する変更可否確認ステップと、変更可が確認された対象エントリについてその転送経路情報の更新または当該対象エントリの削除を行うことにより当該宛先アドレスを持つパケットの転送経路を変更する経路変更ステップとを有する
   ことを特徴とするパケット転送方法。
7. 請求項６に記載のパケット転送方法において、
   前記変更可否確認ステップは、前記所定期間にわたり当該宛先アドレスのパケットが転送されていないどうかに基づいて当該転送経路の変更可否を判断することを特徴とするパケット転送方法。
8. 請求項７に記載のパケット転送方法において、
   前記パケット転送テーブルは、前記エントリごとに当該転送経路の変更可否を示す変更可否情報をさらに有し、
   前記転送処理ステップは、前記パケット転送テーブルの各エントリのうちパケット転送の際に参照したエントリについてその変更可否情報を変更不可に設定し、
   前記変更対象検索ステップは、検索した対象エントリのうち当該変更可否情報が変更不可を示すエントリについて転送経路の変更を行わず当該変更可否情報を変更可に設定する
   ことを特徴とするパケット転送方法。
9. 請求項６に記載のパケット転送方法において、
   前記変更対象検索ステップは、前記所定期間として、少なくとも、対象エントリの宛先アドレスを持つパケットが切替元となる旧経路を介して対向装置まで到達するのに要する伝搬遅延時間の時間長を用いることを特徴とするパケット転送方法。
10. 請求項６に記載のパケット転送方法において、
    前記変更対象検索ステップは、前記所定期間として、少なくとも、対象エントリの宛先アドレスを持つパケットが切替元となる旧経路を介して対向装置まで到達するのに要する伝搬遅延時間から切替先となる新経路を介して対向装置まで到達するのに要する伝搬遅延時間を減算して得られた差分の時間長を用いることを特徴とするパケット転送方法。
11. 通信ネットワークに設けられ、入力されたパケットをその宛先アドレスに基づき所定の転送経路へ転送するパケット転送装置のコンピュータに、
    パケットの各宛先アドレスとそのパケットの転送経路を示す転送経路情報と転送経路変更の対象であるか否かを示す変更要否情報との組をエントリとして複数有するパケット転送テーブルを記憶部で記憶する記憶ステップと、
    入力されたパケットの宛先アドレスに対応する転送経路情報を前記パケット転送テーブルから取得しその転送経路情報に応じて当該パケットを転送する転送処理ステップと、
    前記パケット転送テーブルの各エントリのうち転送経路変更の対象となる対象エントリについて当該宛先アドレスを持つパケットの転送経路を変更する転送制御ステップと
    を実行させ、
    前記転送制御ステップは、前記パケット転送テーブルを検索して前記対象エントリの変更要否情報を変更要に初期化する初期化ステップと、少なくとも所定期間以上経過するごとに前記パケット転送テーブルの各エントリから当該変更要否情報が変更要を示す対象エントリを検索する変更対象検索ステップと、検索した前記対象エントリについて転送経路の変更可否を確認する変更可否確認ステップと、変更可が確認された対象エントリについてその転送経路情報の更新または当該対象エントリの削除を行うことにより当該宛先アドレスを持つパケットの転送経路を変更する経路変更ステップとを有する
    ことを特徴とするプロクラム。
12. 請求項１１に記載のプロクラムにおいて、
    前記変更可否確認ステップは、前記所定期間にわたり当該宛先アドレスのパケットが転送されていないどうかに基づいて当該転送経路の変更可否を判断することを特徴とするプロクラム。
13. 請求項１２に記載のプロクラムにおいて、
    前記転送処理ステップは、前記パケット転送テーブルの各エントリのうちパケット転送の際に参照したエントリについて、その転送経路の変更可否を示す変更可否情報を変更不可に設定し、
    前記変更対象検索ステップは、検索した対象エントリのうち当該変更可否情報が変更不可を示すエントリについて転送経路の変更を行わず当該変更可否情報を変更可に設定する
    ことを特徴とするプロクラム。
14. 請求項１１に記載のプロクラムにおいて、
    前記変更対象検索ステップは、前記所定期間として、少なくとも、対象エントリの宛先アドレスを持つパケットが切替元となる旧経路を介して対向装置まで到達するのに要する伝搬遅延時間の時間長を用いることを特徴とするプロクラム。
15. 請求項１１に記載のプロクラムにおいて、
    前記変更対象検索ステップは、前記所定期間として、少なくとも、対象エントリの宛先アドレスを持つパケットが切替元となる旧経路を介して対向装置まで到達するのに要する伝搬遅延時間から切替先となる新経路を介して対向装置まで到達するのに要する伝搬遅延時間を減算して得られた差分の時間長を用いることを特徴とするプロクラム。
    

Images