(57)【要約】【課題】  トライ検索を実行する前に、各ルーティングプロトコル別に挿入された順序に応ずる検索をまず実行し、挿入された順序に応ずる検索に失敗した場合、既存のトライ検索を実行するルーティングシステム及びルートアップデート方法を提供する。【解決手段】  本発明に係るルーティングシステム及びルートアップデート方法は、ルーティングテーブル内の各エントリーに各ルーティングプロトコルによるエントリーが挿入された順序の情報を格納してから、ルーティングモジュールを再起動するとき、前記格納されたルートの挿入された順序に応じてプレフィックス検索を実行し、プレフィックス検索実行の結果、プレフィックスマッチングが起こった場合、該当ルートエントリーをアップデートし、プレフィックスマッチングが失敗した場合には、一般的なトライ構造により検索を実行して、ルートのアップデートすることにより、ルート探索回数の減少効果を得られる。【選択図】  図４
2007195180.tif 000002
【特許請求の範囲】
【請求項１】
トライ（Trie）構造を有するルーティングテーブルのルートアップデート方法において、
ルーティングテーブル内の各ルートエントリーに、ルーティングプロトコル別にルートエントリーが挿入された順序に関する情報を格納する段階と、
ルーティングモジュールが再起動するときに、前記格納されたルートエントリーの挿入された順序に応じてプレフィックス検索を実行する段階と、
前記プレフィックス検索実行の結果、プレフィックスマッチングが起こった場合、当該ルートエントリーをアップデートする段階と、を備えることを特徴とするルートアップデート方法。
【請求項２】
前記プレフィックス検索実行の結果、プレフィックスマッチングが失敗した場合、
前記トライ構造による検索を実行する段階をさらに備えることを特徴とする請求項１に記載のルートアップデート方法。
【請求項３】
前記ルーティングプロトコルは、ＲＩＰ（Routing Information Protocol）、ＯＳＰＦ（Open Shortest Path First）プロトコル 、ＢＧＰ（Border Gateway Protocol）のうち少なくと１つを含むことを特徴とする請求項１に記載のルートアップデート方法。
【請求項４】
前記ルーティングテーブル内の各エントリーは、ルーティングプロトコル別に該ルートエントリーの挿入順序上の以前、以後に挿入されたルートエントリーとの接続情報を含むことを特徴とする請求項１に記載のルートアップデート方法。
【請求項５】
前記接続情報は、ダブルリンクリスト（double linked list）形態で表現されることを特徴とする請求項４に記載のルートアップデート方法。
【請求項６】
前記トライ構造は、２進（Binary）トライ、パトリシア（Patricia）トライ、経路圧縮トライ、マルチビットトライ、ＬＣ−トライのうちの１つであることを特徴とする請求項１に記載のルートアップデート方法。
【請求項７】
トライ構造を有するルーティングテーブルのルートアップデート方法において、
ルーティングテーブル内の各ルートエントリーに各ルーティングプロトコル別にルートエントリーが挿入された順序に関する情報を格納する段階と、
ルーティングモジュールが再起動するとき、前記格納されたルートエントリーが挿入された順序に応じてプレフィックス検索を実行する段階と、
前記プレフィックス検索実行の結果、プレフィックスマッチングが起こった場合、当該ルートエントリーをアップデートし、プレフィックスマッチングが失敗した場合、前記トライ構造による検索を実行する段階と、を備えることを特徴とするルートアップデート方法。
【請求項８】
前記ルーティングテーブル内の各ルートエントリーは、ルーティングプロトコル別に該ルートエントリーの挿入順序上の以前、以後に挿入されたルートエントリーとの接続情報を含むことを特徴とする請求項７に記載のルートアップデート方法。
【請求項９】
各ルートエントリーに各ルーティングプロトコル別に該ルートエントリーが挿入された順序に関する情報をトライ構造で格納するルーティングテーブルと、
再起動するとき、前記格納されたルートエントリーの挿入された順序に応じてプレフィックス検索を実行し、前記プレフィックス検索実行の結果、プレフィックスマッチングが起こった場合、当該ルートエントリーをアップデートするルーティングモジュールと、を備えることを特徴とするルーティングシステム。
【請求項１０】
前記ルーティングモジュールは、
ＲＩＰによって前記ルーティングテーブルの各ルートエントリーに対するアップデートを行うＲＩＰルーティングモジュールと、
ＯＳＰＦプロトコルによって前記ルーティングテーブルの各ルートエントリーに対するアップデートを行うＯＳＰＦルーティングモジュールと、
ＢＧＰによって前記ルーティングテーブルの各ルートエントリーに対するアップデートを行うＢＧＰルーティングモジュールと、を備えることを特徴とする請求項９に記載のルーティングシステム。
【請求項１１】
前記ルーティングモジュールは、前記プレフィックス検索実行の結果、プレフィックスマッチングが失敗した場合、前記トライ構造によって検索を実行することを特徴とする請求項９に記載のルーティングシステム。
【請求項１２】
前記ルーティングテーブルは、ルーティングプロトコル別に挿入順序上の以前、及び以後に挿入されたルートエントリーとの接続情報を含む少なくとも１つのルートエントリーを備えることを特徴とする請求項９に記載のルーティングシステム。
【請求項１３】
前記接続情報は、ダブルリンクリスト（double linked list）形態で表現されることを特徴とする請求項１２に記載のルーティングシステム。
【請求項１４】
前記トライ構造は、２進トライ、パトリシアトライ、経路圧縮トライ、マルチビットトライ、ＬＣ−トライのうち１つであることを特徴とする請求項９に記載のルーティングシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ルーティングシステム及びルートアップデート方法に関し、より具体的には、トライ（Trie）構造のルーティング管理においてトライ検索を実行する前に、ルーティングプロトコル別に挿入された順序にに基づく探索をまず実行する、ルーティングシステム及びルートアップデート方法に関する。
【背景技術】
【０００２】
ルーティングシステムは、３階層アドレスによってパケットを目的地までの最適経路上にある次のノードへ転送する役割を担当する。ルーティングシステムは、一般的に、複数のラインカード、バックプレーン（backplane）、及びＣＰＵ部分により構成される。ラインカードは、多様なリンク技術を採用している互いに異なるネットワークとルーティングシステムとを物理的に接続する。ＣＰＵは、ルーティングプロトコルを使用し、ルーティングテーブルを生成、及び管理し、さらにネットワーク管理システムとのインターフェーシングを行う。バックプレーンは、複数のラインカードとＣＰＵ間を互いに接続する。
【０００３】
ルーティングシステムは、規模や用途によって多様な種類があるが、共通的に次のような動作を行う。
【０００４】
まず、外部からパケットを受信したルーティングシステムのラインカードが当該リンク階層を終了させ、受信したパケットに異常があるか否かを検査する。例えば、イーサネット（登録商標）の場合には、ラインガードはＣＲＣ（Cyclic Redundancy Code）検査をしたりする。また、ＡＴＭ（Asynchronous  Transfer Mode）の場合には、パケットで受信したセルの組み合わせを検査したりする。次に、ルーティングシステムはＩＰヘッダーに対するエラーを検査し、目的地ＩＰアドレスを読み出した後、ルーティングテーブルから出力ポート情報を把握するために、ＬＰＭ（Longest Prefix Matching）ルックアップ（lookup）を行う。ここで、ＬＰＭは、受信したパケットの目的地ＩＰアドレスとルーティングテーブルの全てのルートエントリーとを比較するルックアップ過程を通して、ルートエントリーのネットワークアドレスのプレフィックス部分が目的地アドレスと一致する全てのルートエントリーのうち、プレフィックスの長さが最も長いルートエントリーを受信したパケットのルーティング情報として選択する方法を言う。
【０００５】
一旦、ルーティングシステムがＩＰアドレスルックアップに成功すると、ＩＰヘッダーのＴＴＬ（Time To Live）値を順次的に減少させ、新しいヘッダーチェックサム（Header Checksum）を計算し、ヘッダーを修正する。その後、ルーティングシステムはバックプレーンを介してパケットを出力ポートへ送信し、出力ラインカードでは、パケットにリンク階層ヘッダーを付加し、次のルーティングシステム（または目的地ホスト）へパケットを送信する。仮に、このような過程でエラーが生じた場合、ルーティングシステムはＩＣＭＰ（Internet Control Message Protocol）エラーメッセージをパケットが発信されたホストへ送信し、ルーティングに失敗したことを通知する。
【０００６】
ルーティングシステムの性能を向上させるために様々な研究が進行されており、また、ＩＰフォワーディング過程における高速化の目標の１つであるＩＰアドレスルックアップ処理についても多くの研究があった。それらのうち代表的なものとして、Ｔｒｉｅ基盤方法、ハシング（Hashing）基盤方法、２進探索（binary search）基盤方法、及びハードウェア基盤方法などが含まれる。
【０００７】
Ｔｒｉｅを基とする方法は、レベルの数を減らすために、言い換えればメモリアクセス回数の減らすために１ビット当たり１レベルを構成する元のＴｒｉｅを、マルチビット当たり１レベルに圧縮する方法である。Ｔｒｉｅでは、最も長い経路のレベル個数が最大メモリアクセス回数である。
【０００８】
２進探索技法は、ｅｘａｃｔマッチングに使われるもので、ＬＰＭに使用するときには、プレフィックスの一部を変形して形成された配列（sorted array）を使用する。一方、ハードウェアを基とする方法の中には、代表的なものとしてＣＡＭ（Content-Addressable Memory）を利用する方法がある。この方法は、最も速いが価格が高く、また、ルートエントリーの数が数Ｋ未満であるという短所がある。
【０００９】
パトリシア−トライは、ルート（route）を追加したり削除する場合において、フォワーディングを効率的に行うのに利用される。ＯＳＰＦ（Open Shortest Path First）プロトコル、またはＢＧＰ（Border Gateway Protocol）のようなルーティング実行モジュールが再起動（restart）される場合、ルーティングテーブル上のルートエントリーのうち、再起動したルーティング実行モジュールでアップデートされたルートエントリーは、その内容が利用可能であるか否かについて検査されなければならない。このとき、ＯＳＰＦプロトコルやＢＧＰなどのプロトコルは、ｇｒａｃｅｆｕｌ−ｒｅｓｔａｒｔをサポートするために、一定時間全てのルートエントリーを有効なルートエントリーとして認定する。そして、更新されたルートエントリーだけを使用するようにするために、ルート情報を他の外部ルーティングシステムから受信する。ここで、ｇｒａｃｅｆｕｌ−ｒｅｓｔａｒｔは、再起動するルーティングモジュールの影響を最小化する機能をいう。もし、ｇｒａｃｅｆｕｌ−ｒｅｓｔａｒｔがなければ、ルーティングモジュールが再起動するとき、ルートの再算定及び広範囲なルートアップデートに起因して、好ましくないネットワーク動作状態が引き起こされる。
【００１０】
一方、Ｔｒｉｅ基盤のルーティング管理においては、ｎ個のルート情報が以前に存在したとすれば、ＯＳＰＦプロトコルまたはＢＧＰなどによってアップデートされるルート情報を探索する時間Ο（log n）が必要である。これは、新しいルートが追加または削除される場合にも同様であり、当該プロトコルによる多くのルートエントリーが存在すれば、システムの性能を低下させるという問題が発生する。
【００１１】
【特許文献１】大韓民国公開特許第２００２−５１８１２号明細書
【発明の開示】
【発明が解決しようとする課題】
【００１２】
本発明は、前述のような問題点を解決するためになされたもので、その目的は、トライ検索を実行する前に、ルーティングプロトコル別に挿入された順序に応ずる検索をまず実行し、挿入された順序に応ずる検索に失敗した場合、既存のトライ検索を実行するようにするルーティングシステム及びルートアップデート方法を提供することにある。
【課題を解決するための手段】
【００１３】
前記目的を達成するために、本発明の一態様に係るルートアップデート方法は、ルーティングテーブル内の各ルートエントリーにルーティングプロトコル別に、該ルートエントリーが挿入された順序に関する情報を格納する段階と、ルーティングモジュールが再起動するとき、前記格納されたルートエントリーの挿入された順序に応じてプレフィックス検索を実行する段階と、前記プレフィックス検索の実行結果、プレフィックスマッチングが起こった場合、当該ルートエントリーをアップデートする段階と、を備えることを特徴とする。
【００１４】
前記プレフィックス検索の実行結果、プレフィックスマッチングが失敗した場合、前記トライ構造による検索を実行する段階をさらに備えることができる。
【００１５】
前記ルーティングプロトコルは、ＲＩＰ（Routing Information Protocol）、ＯＳＰＦ（Open Shortest Path First）プロトコル、ＢＧＰ（Border Gateway Protocol）のうち少なくと１つを含む。
【００１６】
前記ルーティングテーブル内の各ルートエントリーは、ルーティングプロトコル別に該ルートエントリーの挿入順序上の以前及び以後に挿入されたルートエントリーとの接続情報を含む。
【００１７】
前記接続情報は、ダブルリンクリスト（double linked list）形態で表現される。
【００１８】
前記トライ構造は、２進（Binary）トライ、パトリシア（Patricia）トライ、経路圧縮トライ、マルチビットトライ、ＬＣ−トライのうちいずれか１つである。
【００１９】
また、本発明の他の態様に係るルートアップデート方法は、ルーティングテーブル内の各ルートエントリーにルーティングプロトコル別に該ルートエントリーが挿入された順序に関する情報を格納する段階と、ルーティングモジュールが再起動するとき、前記格納されたルートエントリーの挿入された順序に応じてプレフィックス検索を実行する段階と、前記プレフィックス検索の実行結果、プレフィックスマッチングが起こった場合、当該ルートエントリーをアップデートし、プレフィックスマッチングが失敗した場合、前記トライ構造による検索を実行する段階と、を備えることを特徴とする。
【００２０】
また、本発明のさらに他の態様に係るルーティングシステムは、各ルートエントリーにルーティングプロトコル別にルートが挿入された順序に関する情報をトライ構造で格納するルーティングテーブルと、再起動するとき、前記格納されたルートエントリーの挿入された順序に応じてプレフィックス検索を実行し、前記プレフィックス検索実行の結果、プレフィックスマッチングが起こった場合、当該ルートエントリーをアップデートするルーティングモジュールと、を備えることを特徴とする。
【発明の効果】
【００２１】
本発明は、新しいルートエントリーのルーティングプロトコルに挿入された順序を格納し、ルーティングモジュールが再起動するとき、これを用いてルートエントリーをアップデートすることによって、ルーティング検索に要する時間を減らすことができる。
【発明を実施するための最良の形態】
【００２２】
以下、本発明に係る好適な実施形態について図面を参照して詳細に説明する。
【００２３】
図１は、本発明の実施形態が適用されるＩＰルーティングテーブルアップデートのためのパトリシアトライ構造の一例を示す図である。
【００２４】
トライを基盤とする代表的アルゴリズムとして、図１に示すパトリシア−トライ（Patricia-trie）が挙げられる。パトリシア−トライは、ＢＳＤ（Berkeley Software Distribution）系列のユニックスや既存の多くのルーティングシステムが使用している方法である。パトリシア−トライは、ルーティングテーブルをツリー（tree）構造で作成し、ツリーのルート（root）から葉（leaf）までの経路が１つのルーティングエントリーとなるようにする。ここで、パケットの目的地ＩＰアドレスとマッチングされる最も長い経路（path）を探すと、それがＬＰＭ（Longest Prefix Matching）となる。パトリシア−トライは、メモリ使用を大きく低減し、ＩＰｖ４の場合、最大３２回のメモリアクセスが必要であり、ＩＰｖ６の場合、最大１２８番のメモリアクセスが必要である。
【００２５】
図１は、ＩＰアドレスがビット３２からビット６３に該当するパケットをパトリシアトライ構造を用いたルーティングテーブルルックアップ手続を示す。ここで、直角四角形は、内部ノード（internal node）を、丸い四角形は、リーフノード（leaf node）を意味する。ルックアップ過程は、入力されたパケットのビット３２と図１のパトリシアトライ構造の最上位から順次的に比較してリーフノードに到達すれば、そのリーフノード値と受信パケットのＩＰアドレス値とを比較し、マッチングされる場合、該当ノードを用いてＩＰパケットをフォワーディングするネットワークインタフェースを探せるようになる。
【００２６】
図２は、本発明の実施形態が適用されるＩＰルーティングテーブルアップデートのための様々なトライ構造を示す図である。
【００２７】
図２の各トライは、同じサンプルプレフィックスを用いて構成されたものである。
【００２８】
図２ａは２進トライ（Binary Trie）構造を示し、プレフィックスをＴｒｉｅのノードに格納する方式である。２進トライの場合、Ο（Ｗ）のメモリアクセス回数が必要である。図２ｂは経路圧縮トライ（Path Compressed Trie）構造を示し、空きノードであり且つ１つのチャイルド（child）を有するノードを圧縮させて、最大メモリアクセス回数を減少させる方式である。図２ｃはマルチビットトライを示し、メモリアクセス回数を減少させるために、１つのノードが有することができるチャイルドの個数を増やす方法である。この方法において、Ｋ−ビットトライの場合、メモリアクセス回数はΟ（Ｗ／Ｋ）に減少するが、Ｔｒｉｅの格納方法が複雑となるという短所がある。図２ｄのＬＣ（Level Compressed）−Ｔｒｉｅの場合、既存のトライに比べてさらにコンパクト（compact）化した構成が可能になったが、依然として最大Ο（Ｗ／Ｋ）のメモリアクセスが必要である。
【００２９】
図１及び図２に示すように、一般的なトライ基盤アルゴリズムは、レベルの数を減少させるために、言い換えればメモリアクセス回数を減少させるために１ビット当たり１レベルを構成する元のトライをマルチビット当たり１つのレベルに圧縮する。。トライ構造では、最も長い経路のレベル個数が最大メモリアクセス回数となる。
【００３０】
このようなトライ構造は、ルーティングルックアップ処理のみならず、ルートエントリーのアップデート処理にも同様の原理で適用される。
【００３１】
図３は、本実施形態によるルーティングシステムのブロック図である。
【００３２】
本発明に係るルーティングシステムは、ＲＩＰルーティングモジュール３１０と、ＯＳＰＦルーティングモジュール３２０と、ＢＧＰルーティングモジュール３３０と、ルーティングテーブル３４０とを備えて構成される。
【００３３】
ＲＩＰルーティングモジュール３１０は、ルーティングテーブル３４０を参照してＲＩＰルーティングを行う。ここで、ＲＩＰ（Routing Information Protocol）は、例えば企業の構内通信網（Local Area Network, ＬＡＮ）、またはそのようなＬＡＮにより接続されるグループのような、独立的なネットワーク内でルーティング情報管理のために広範囲に使用されるプロトコルである。ＲＩＰの使用により、ルーティングシステム内のゲートウエー（gateway）ホストは、全てのルーティングテーブルを最も近くの隣接するホストに３０秒毎に送信する。隣接するホストは、順次に、その情報を次の隣接するホストに渡す。、このような送信は、そのネットワーク内の全てのホストが同じルーティング経路情報を有するまで繰り返される。ＲＩＰは、ネットワーク距離を決定する方法として、ホップの合計を使用する（これに対し、他のプロトコルは、タイミングまでも含む、さらに精巧なアルゴリズムを使用する）。ネットワーク内においてルーティングシステムを有している各ホストは、パケットを送信する次のホストを決定するために、ルーティングテーブル情報を使用する。ＲＩＰは、小規模且つ同種のネットワークでは有効な解決策であると考えられるが、より複雑で規模が大きいネットワークにおいては、ＲＩＰが全てのルーティングテーブルを３０秒毎に転送することは、ネットワーク内に莫大な量の追加ロードの負荷を与えるという短所がある。
【００３４】
ＯＳＰＦルーティングモジュール３２０は、ルーティングテーブルを参照してＯＳＰＦプロトコルによってルーティングを行うブロックである。
【００３５】
ここで、ＯＳＰＦプロトコルの全般的な動作について説明する。
【００３６】
１９８０年代中頃に、ＲＩＰが大規模で異質なネットワーク間でのルーティングを実行することについて限界に達したとき、ＩＥＴＦ（Internet Engineering Task Force）は、ＳＰＦ（Shortest Path First）アルゴリズムを基盤とするインターネットに適用するためのＩＰネットワーク用ルーティングアルゴリズムを開発し、その結果、ＯＳＰＦ（Open Shortest Path First）プロトコルが作り出された。
【００３７】
ＯＳＰＦプロトコルを使用するとき、ルーティングテーブルの変更やネットワーク内の様々な変化を感知したホストは、全てのホストが同じルーティング情報を有することができるようにするために、直ちにその情報をネットワーク内の他の全てのホストに通知する。ルーティングテーブル全体を送るＲＩＰとは異なり、ＯＳＰＦプロトコルを使用するホストは、ただ変更された部分だけを送る。ＲＩＰでは、３０秒毎にルーティングテーブルを隣接するホストに送るが、ＯＳＰＦプロトコルは、変更が生じたときに限って、変更された情報をマルチキャスト（ｍｕｌｔｉ−ｃａｓｔ）する。
【００３８】
ＯＳＰＦプロトコルは、単純にホップ数を数えることではなく、追加的なネットワーク情報を考慮したリンク状態でのパスクラス（ｐａｔｈ  ｃｌａｓｓ）を基とする。また、ＯＳＰＦプロトコルは、ユーザが自身の好みによっていくつかの経路に対して優先権を付与できるように、特定のホストルータを設定できるようにする。ＯＳＰＦプロトコルは、１つのネットワークがさらに細分され得るように、多様なネットワークサブネットマスクをサポートする。ＯＳＰＦプロトコル内でのルータと終端ステーション間の通信のために、ＲＩＰがサポートされる。既に多くのネットワークがＲＩＰを使用しているため、ルータ製作業者は、もともとＯＳＰＦプロトコルのために設計されたルータ内にＲＩＰのサポートも共に含める傾向にある。
【００３９】
ＯＳＰＦプロトコルは、全ての仕様が公開（Open）されており、ＲＦＣ１２４７（以後にＲＦＣ１５８３；ＯＳＰＦ  Ｖｅｒｓｉｏｎ２に代替）として発表された。
【００４０】
ＯＳＰＦプロトコルは、ＲＩＰとは異なり、ルーティングアルゴリズムを適合させるための階層を有している。それらの階層の中には、最も大きい階層であるＡＳ（Autonomous System）があるが、これは、共通的なルーティング戦略を共有しつつ、１つの管理システムにより管理されるネットワーク集積として定義される。１つのＡＳは、さらに複数の地域（ＡＲＥＡ）に分けられるが、これは、連続的なネットワーク及びアクセスシステムの集積として表現される。１つのＡＳ内で、このような地域を接続するネットワークはバックボーンネットワークと呼ばれ、このような階層に従ってルータの種類が区分される。それらのルータは、内部ルータ、地域境界ルータ、バックボーンルータ、ＡＳ境界ルータなどを含む。
【００４１】
内部ルータ（Internal Router）は、或る１地域に属するネットワークに直接接続するルータをいい、バックボーンネットワークに接続したルータも含まれる。地域境界ルータ（Area Border Router）は、地域とバックボーンネットワークとを接続させるルータをいい、このルータは、接続された地域に対する経路情報を要約してバックボーンネットワークに転送する。そして、バックボーンネットワークを介してこの情報が他の地域境界ルータに分配される（図１：ルータ４、１０、１１及び１２）。
【００４２】
また、バックボーンルータ（Backbone Router）は、バックボーンネットワークに接続した全てのルータをいい、これには、地域境界ルータ及びバックボーンネットワークに属する内部ルータが含まれる。ＡＳ境界ルータ（AS Boundary Router）は、他のＡＳに属するルータと経路情報を交換するルータをいい、このような経路情報は、ＡＳ外部経路として全てのＡＳに転送される。このようなＡＳ境界ルータに対する経路は、ＡＳに属する全てのルータに通知される。
【００４３】
ＯＳＰＦルータは、最初のブーティングのときにハロー（Hello）パケットを交換することによって、隣接するルータを互いに認識できるようになる。これにより、ある特定のネットワークに接続される複数のルータの中から、そのネットワークを代表してそのネットワークに関する経路情報を生成及び分配する責任を負う代表（representative）ルータを指定する。代表ルータは、同期を合わせるために新しく認識されたルータと経路情報を交換する。ＯＳＰＦルータは、自身の経路テーブルに関する情報をＬＳＡ（Link State Advertisement）というデータアーチテクチャーを通じて周期的に、又はルータの状態が変わるときに送信する。その結果、ＬＳＡは、該当地域の全てのルータに通知される。これにより、１地域に属する全てのルータは、同じ情報を共有するようになる。
【００４４】
地域間の情報共有は、次のように行われる。地域境界ルータは、ＡＳのバックボーンネットワークに接続されているため、他の地域境界ルータと地域についての要約（Summary）情報を交換することによって、ＡＳのトポロジー（Topology）と他の地域に関する情報とを獲得することができる。これにより、自身の地域に属しない全ての目的地に対する経路を計算することができる。この計算された経路は、内部ルータに送信される。これにより、内部ルータは、他の地域に属する目的地へパケットを転送するとき、どの地域境界ルータで転送すべきかを決定することができる。
【００４５】
他のＡＳに対する外部経路情報を知っているＡＳ境界ルータは、ＡＳを経由して情報を転送できるので、このような外部経路情報は、スタブ（Stub）地域を除いて、全ての地域境界ルータにより地域要約情報の形態で内部ルータへ転送される。このような理由で、他のＡＳに接続されるＡＳ境界ルータの位置は、スタブ地域に属するルータを除く全てのルータに通知される。その結果、ＡＳ外部へ情報を転送できるようになる。
【００４６】
ＯＳＰＦルータは、上述したような方式で、トポロジーデータベースを構築するための地域内部、地域外部、ＡＳ外部の経路に関する情報を得る。そして、全ての経路に対して自身からの最短経路ツリー（Shortest Path Tree）を計算し、且つこれを経路テーブルに維持するために、トポロジーデータベースにＳＰＦアルゴリズムを適用して、パケットの中継を行う。
【００４７】
ＢＧＰルーティングモジュール３３０は、ドメイン間のルーティングプロトコルであるＢＧＰによってルーティングを行うモジュールである。
【００４８】
ここで、ＢＧＰ（Border Gateway Protocol）の動作方式は、次の通りである。
【００４９】
まず、互いに異なるＡＳ（管理ドメイン）に属するＢＧＰルータが通信を行うためには、それらは他のネットワークによって中継されることなく、１つのネットワークで直接接続されなければならない。また、１つのＡＳ内に複数のＢＧＰルータが存在する場合、ＢＧＰルータは、そのＡＳに対する一貫性のある情報を有するようにするため、及びＡＳ外部通路としての役割を行うようにするために、互いを認識し、情報を交換しなければならない。
【００５０】
ＢＧＰルータが他のＢＧＰルータと接続されるときには、自身が有している経路テーブルの全ての内容を最初に交換し、その後は、変化したものだけを交換する。このとき、ＢＰＧルータは特定の目的地に対する全ての適する経路を維持しているが、その中の最適の経路だけを経路更新メッセージによって送信する。このような情報の交換は、ＴＣＰ（Transmission Control Protocol）を通じて確実に実行される。
【００５１】
ＢＧＰは、ＲＩＰと同じ距離値（Distance Vector）を基本とするルーティングアルゴリズムであるが、目的地までの経路値を転送するのではなく、目的地まで到達するのに経由するＡＳのルーティング順序を転送する。そのため、距離値アルゴリズムが有している無限経路値（Counting to Infinity）の問題を有していない。
【００５２】
上述したＲＩＰルーティングモジュール３１０、ＯＳＰＦルーティングモジュール３２０、ＢＧＰルーティングモジュール３３０は、再起動（restart）する場合、ルーティングテーブル上のルートエントリーのうち該当プロトコルによりアップデートされたルートエントリーに対してその有効性を検査する。しかしながら、これらのルーティングモジュールは、再起動するとき、ｇｒａｃｅｆｕｌ−ｒｅｓｔａｒｔをサポートするために一定時間すべてのルートエントリーを有効なルートエントリーとして認定した後、他の外部ルータから受信して更新されたルートエントリーのみを使用する。したがって、このようなｇｒａｃｅｆｕｌ−ｒｅｓｔａｒｔ機能により、外部から受信したルートエントリーは、既存のルートエントリーと一致する確率が高い。
【００５３】
したがって、本実施形態に係るルーティングモジュール、すなわちＲＩＰルーティングモジュール３１０、ＯＳＰＦルーティングモジュール３２０、ＢＧＰルーティングモジュール３３０は、２進探索を実行する前に、プロトコル別にルートエントリーが挿入された順序を格納し、その後、プロトコルが再起動する場合、２進探索を実行する前に、以前に挿入されたルートエントリーとその次に挿入されるルートエントリーとの比較を優先的に行い、２つのルートエントリーが同一なら、２進探索を行わないようにする。
【００５４】
このために、ルーティングテーブル３４０の各ルートエントリーは、ルーティングプロトコル別にルートエントリーが挿入された順序に関する情報を含む。そして、ダブルリンクリスト（double linked list）を使用して以前に挿入されたルートエントリーと接続関係を形成する。
【００５５】
図４は、本実施形態によるルーティングトライの構造を示す。
【００５６】
図４から分かるように、ルーティングテーブルは、既存のルーティングテーブルが有してする情報のほかに、プロトコル４０１別にルーティングエントリーが挿入された順序に関する情報４１１を格納する。すなわち、図４のトライ構造の最上位に位置するプレフィックス(ｉ)に対するルーティングエントリーは、ＢＧＰプロトコルにより挿入されたエントリーであり、ＢＧＰプロトコルによる挿入順序は、（ｉ）番目であることが分かる。図４のトライ構造は、最も一般的な２進トライ場合であってもよく、前述したようなパトリシアトライ、経路圧縮トライ、マルチビットトライ、ＬＣ−トライなどであってもよい。
【００５７】
したがって、プレフィックス（ｋ−１）がＯＳＰＦルーティングモジュールにより（ｋ−１）番目にアップデートされたルートエントリーであるとすれば、次回のＯＳＰＦプロトコルによるルートエントリーが追加される場合、トライ探索（２進探索またはその変形探索）などを用いて検索する代わりに、プレフィックスｋに対するルートエントリー位置情報を用いてまず検索を実行するようになる。
【００５８】
仮に、挿入順序を用いたルートエントリー検索が失敗すれば、既存の方法であるトライ探索を用いて探索を実行するようになる。この場合、探索回数が１回増加するものであって、挿入順序情報を利用しない場合の平均的な比較回数がｔなら、挿入順序情報を利用した場合における比較回数がｔ＋１となる。しかし、挿入順序情報を用いて成功する場合まで考慮すれば、統計的な比較回数は、ｔより非常に減少した値を有するようになる。
【００５９】
本発明によれば、新たなルートエントリーの挿入された順序は各ルーティングプロトコルにより予め格納され、ルーティングモジュールを再起動するときには、ルートエントリーは格納された順序を使用して更新されるので、ルーティングの検索時間を短縮することができる。
【００６０】
本発明は様々な実施形態の統合で記載されているが、上述した実施形態に限定されず、各種の置換、変形及び変更が可能であることは、本発明が属する技術分野における通常の知識を有する者にとって明らかである。上述の記載は、添付した特許請求の範囲の精神と範囲内にある置換や変形、及び変更を受け入れることができるものとして記載している。
【図面の簡単な説明】
【００６１】
【図１】本発明の実施形態が適用されるＩＰルーティングテーブルアップデートのためのパトリシアトライ（Trie）構造の一例を示す図である。
【図２】本発明の実施形態が適用されるＩＰルーティングテーブルアップデートのための様々なトライ構造を示す図である。
【図３】本発明の実施形態によるルーティングシステムのブロック構成を示す図である。
【図４】本発明の実施形態によるルーティングトライの構造を示す図である。
【符号の説明】
【００６２】
３００  ルーティングシステム
３１０  ＲＩＰルーティングモジュール
３２０  ＯＳＰＦルーティングモジュール
３３０  ＢＧＰルーティングモジュール
３４０  ルーティングテーブル
４１１  プロトコル別に挿入された順序
【図１】
2007195180.tif 000003
【図２】
2007195180.tif 000004
【図３】
2007195180.tif 000005
【図４】
2007195180.tif 000006