(57)【要約】スキップリストを利用してＩＰアドレス検索のためのルーティング／フォワーディングテーブルを構築する方法を提供する。その方法は、インターネットプロトコルアドレスのプレフィックス長さ範囲を予め設定された方式によって分割する過程と、プレフィックス長さ範囲の分割されたクラスターの個数に基づいた最大レベルを有し、スキップリスト内の全てのノードをポインティングするためのヘッダノードを生成する過程と、それぞれ前記分割されたプレフィックス長さ範囲をキーとして有し、前記分割されたクラスターの個数の分だけサブノードを生成する過程と、から構成される。
2004517519.tif 000002
【特許請求の範囲】
【請求項１】
スキップリストを利用してインターネットプロトコル（ＩＰ）アドレス検索のためのルーティング／フォワーディングテーブルを構築する方法において、
前記インターネットプロトコルアドレスのプレフィックス長さ範囲を予め設定された方式によって分割する過程と、
前記プレフィックス長さ範囲の分割されたクラスターの個数に基づいた最大レベルを有し、前記スキップリスト内の全てのノードをポインティングするためのヘッダノードを生成する過程と、
それぞれ前記分割されたプレフィックス長さ範囲をキーとして有し、前記分割されたクラスターの個数の分だけサブノードを生成する過程と、
からなることを特徴とする方法。
【請求項２】
それぞれのサブノードにおいて、前記プレフィックス長さによって提供されるハッシュテーブルに、対応するプレフィックス長さ範囲内のそれぞれのプレフィックス長さに対応するルートエントリを貯蔵する過程をさらに含むことを特徴とする請求項１記載の方法。
【請求項３】
前記ルートエントリは、３２ビットまたは１２８ビットであることを特徴とする請求項２記載の方法。
【請求項４】
前記サブノードの前記ヘッダノードのレベルは、無作為に設定されることを特徴とする請求項１記載の方法。
【請求項５】
前記プレフィックス長さ範囲は、固定的にまたは可変的に分割されることを特徴とする請求項１記載の方法。
【請求項６】
前記プレフィックス長さ範囲は、前記サブノードを通して全てのプレフィックス長さ範囲がカバーされるように分割されることを特徴とする請求項１記載の方法。
【請求項７】
前記ルーティング／フォワーディングテーブルは、それぞれルーティングプロセッサ及びフォワーディングエンジンに備わることを特徴とする請求項１記載の方法。
【請求項８】
スキップリストを利用するインターネットプロトコルルーティング／フォワーディングテーブルの生成方法において、
前記スキップリスト内の全てのノードを取り扱うためにそれぞれのノードをポインティングするヘッダノードを生成する過程と、
予め設定された方式によって分割されたインターネットプロトコルアドレスのプレフィックス範囲をキーとして有する複数のサブノードを生成する過程と、
それぞれのサブノードにおいて、対応するプレフィックス長さ範囲におけるプレフィックス長さ別のルートエントリを貯蔵するために、プレフィックス長さ別のハッシュテーブルを生成する過程と、
からなることを特徴とする方法。
【請求項９】
前記ハッシュテーブルに対応するプレフィックスに一致するルートエントリを貯蔵する過程をさらに含むことを特徴とする請求項８記載の方法。
【請求項１０】
前記サブノードの前記ヘッダノードのレベルは、無作為に設定されることを特徴とする請求項８記載の方法。
【請求項１１】
前記プレフィックス長さ範囲は、固定的にまたは可変的に分割されることを特徴とする請求項８記載の方法。
【請求項１２】
前記プレフィックス長さ範囲は、複数の前記サブノードを通して全てのプレフィックス長さ範囲がカバーされるように分割されることを特徴とする請求項８記載の方法。
【請求項１３】
前記ルートエントリは、３２ビットまたは１２８ビットであることを特徴とする請求項８記載の方法。
【請求項１４】
前記ヘッダノードは、＋∞キー値を有し、０から最大レベル−１までのインデックスが付けられる伝送ポインタを有することを特徴とする請求項８記載の方法。
【請求項１５】
前記ルーティング／フォワーディングテーブルは、それぞれルーティングプロセッサ及びフォワーディングエンジンに備わることを特徴とする請求項８記載の方法。
【請求項１６】
インターネットプロトコルアドレスのプレフィックス範囲の割り当てによって生成されたそれぞれのノードで設定されたプレフィックス長さによるハッシュテーブルの形態でルートエントリが貯蔵されるスキップリストを利用したルーティング／フォワーディングテーブルの検索方法において、
検索されるルートのプレフィックス長さに対応するプレフィックス範囲が設定されたノードを見つける過程と、
前記見つけたノードにおいて前記検索されるルートと同一のプレフィックス長さを有するハッシュテーブルを見つける過程と、
前記見つけたハッシュテーブルから前記検索ルートを発見する過程と、
からなることを特徴とする方法。
【請求項１７】
前記ノードを見つける過程は、
前記スキップリストのヘッダノードの最大レベルからポインティングするノードを見つける段階と、
前記見つけたノードのプレフィックス長さ範囲と前記検索ルートのプレフィックス長さを比較する段階と、
前記見つけたノードのプレフィックス長さ範囲に前記検索ルートのプレフィックス長さが該当しない場合、前記ヘッダノードの次のレベルでポインティングされるノードを見つける段階と、を含むことを特徴とする請求項１６記載の方法。
【請求項１８】
前記スキップリストは、ヘッダノード、及び減少される順で予め設定される範囲のキーを有し、それぞれのプレフィックス長さに関連したハッシュテーブルにそれぞれのプレフィックス長さに対応するルートエントリを貯蔵する複数のノードを含むことを特徴とする請求項１６記載の方法。
【請求項１９】
前記ルーティング／フォワーディングテーブルは、それぞれルーティングプロセッサ及びフォワーディングエンジンに備わることを特徴とする請求項１６記載の方法。
【請求項２０】
前記ルートエントリは、３２ビットまたは１２８ビットであることを特徴とする請求項１６記載の方法。
【請求項２１】
インターネットプロトコルアドレスのプレフィックス長さ範囲によって生成されたそれぞれのノードで設定されたプレフィックス長さによるハッシュテーブルの形態でルートエントリが貯蔵されるスキップリストを利用したルーティング／フォワーディングテーブルの更新方法において、
更新されるルートのプレフィックス長さに対応するプレフィックス範囲が設定されたノードを見つける過程と、
前記見つけたノードで前記更新されるルートと同一のプレフィックス長さを有するハッシュテーブルを検索する過程と、
前記ハッシュテーブルを発見した時、前記ハッシュテーブルにおいて該当ルートを更新する過程と、
からなることを特徴とする方法。
【請求項２２】
前記ルートを見つける過程は、
前記スキップリストのヘッダノードの最大レベルからポインティングするノードを見つける段階と、
前記見つけたノードのプレフィックス長さ範囲と前記更新されるルートのプレフィックス長さを比較する段階と、
前記見つけたノードのプレフィックス長さ範囲に前記更新されるルートのプレフィックス長さが該当しない場合、前記ヘッダノードの次のレベルでポインティングされるノードを見つける段階と、を含むことを特徴とする請求項２１記載の方法。
【請求項２３】
前記ルート更新過程は、更新されるルートを追加、変更、または削除する過程であることを特徴とする請求項２１記載の方法。
【請求項２４】
前記ハッシュテーブルが発見されない場合、前記更新されるルートと同一のプレフィックスを有するハッシュテーブルを生成する過程と、
前記生成されたハッシュテーブルに前記更新されるルートを挿入する過程と、をさらに含むことを特徴とする請求項２１記載の方法。
【請求項２５】
前記スキップリストは、ヘッダノード、及び減少される順で予め設定される範囲のキーを有し、それぞれのプレフィックス長さと関連したハッシュテーブルにそれぞれのプレフィックス長さに該当するルートエントリが貯蔵される複数のノードを含むことを特徴とする請求項２１記載の方法。
【請求項２６】
前記ルーティング／フォワーディングテーブルは、それぞれルーティングプロセッサ及びフォワーディングエンジンに備わることを特徴とする請求項２１記載の方法。
【請求項２７】
前記ルートエントリは、３２ビットまたは１２８ビットであることを特徴とする請求項２１記載の方法。
【請求項２８】
インターネットプロトコル（ＩＰ）アドレスのプレフィックス範囲の割り当てによって生成されるそれぞれのノードで予め設定されたプレフィックス長さによるハッシュテーブルの形態でルートエントリが貯蔵されるスキップリストを利用するルーティング／フォワーディングテーブルのルートルックアップ方法において、
前記スキップリストの第１ノードから始まって隣接したノードを見つける過程と、
該当ノードで目的地アドレスとそれぞれのハッシュテーブルを比較する過程と、
前記ハッシュテーブルが前記目的地アドレスを含む場合、一致するプレフィックスを最長プレフィックスとみなす過程と、
からなることを特徴とする方法。
【請求項２９】
前記ハッシュテーブルが前記目的地ＩＰアドレスを含まない場合、前記スキップリストで次のノードを見つける過程をさらに含むことを特徴とする請求項２８記載の方法。
【請求項３０】
前記スキップリストは、ヘッダノード、及び減少される順で予め設定される範囲のキーを有し、それぞれのプレフィックス長さに対応するハッシュテーブルにそれぞれのプレフィックス長さに対応するルートエントリを貯蔵する複数のノードを含むことを特徴とする請求項２８記載の方法。
【請求項３１】
前記比較過程は、
前記目的地アドレスと前記該当ノードのハッシュテーブルのうち最長プレフィックス長さを有するハッシュテーブルを比較する段階と、
前記最長プレフィックス長さを有するハッシュテーブルで目的地アドレスを見つけなかった場合、次の最長プレフィックス長さを有するハッシュテーブルと前記目的地アドレスを比較する段階と、を含むことを特徴とする請求項２８記載の方法。
【請求項３２】
前記ルーティング／フォワーディングテーブルは、それぞれルーティングプロセッサ及びフォワーディングエンジンに備わることを特徴とする請求項２８記載の方法。
【請求項３３】
前記ルートエントリは、３２ビットまたは１２８ビットであることを特徴とする請求項２８記載の方法。
【請求項３４】
高速インターネットプロトコルルータにおいて、
パケットが入出力されるフォワーディングエンジンがそれぞれ装着された複数のラインカードモジュールと、
前記パケットを内部ポート間にスイッチングするスイッチファブリックと、
ヘッダノード、及びインターネットプロトコルアドレスのプレフィックス範囲によってそれぞれ生成され、キーとして前記プレフィックス長さ範囲を有し、設定されたプレフィックス長さによるハッシュテーブルの形態でルートエントリを貯蔵するルーティングテーブルを含むルーティングプロセッサと、
から構成されることを特徴とするルータ。
【請求項３５】
高速インターネットプロトコルルータにおいて、
ヘッダノード、及びインターネットプロトコルアドレスのプレフィックス範囲によってそれぞれ生成され、キーとして前記プレフィックス長さ範囲を有し、設定されたプレフィックス長さによるハッシュテーブルの形態でルートエントリを貯蔵する複数のノードを有するスキップリスト構造を有するフォワーディングテーブルを備えるフォワーディングエンジンが装着された複数のラインカードモジュールと、
前記パケットを内部ポート間にスイッチングするスイッチファブリックと、
ルーティング動作を全般に制御するルーティングプロセッサと、
から構成されることを特徴とするルータ。
【請求項３６】
前記ルーティングプロセッサは、ヘッダノード、及びインターネットプロトコルアドレスのプレフィックス範囲によってそれぞれ生成され、前記プレフィックス長さ範囲をキーとして有し、設定されたプレフィックス長さによるハッシュテーブルの形態でルートエントリを貯蔵する複数のノードから構成されるスキップリスト構造を有するルーティングテーブルを備えることを特徴とする請求項３５記載のルータ。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、インターネット上においてパケットを目的地に伝送するためのルーティング（ｒｏｕｔｉｎｇ）技術に関し、特に、高速にインターネットプロトコル（Ｉｎｔｅｒｎｅｔ Ｐｒｏｔｏｃｏｌ： 以下、ＩＰと称する）ルートルックアップ（ｒｏｕｔｅ ｌｏｏｋｕｐ）を遂行し、ルーティング（または、フォワーディング）テーブルを管理する装置及び方法に関する。
【０００２】
【従来の技術】
現在、インターネット利用者の急増、提供されるサービスの多様化、及びＶｏＩＰ（Ｖｏｉｃｅ ｏｖｅｒ Ｉｎｔｅｒｎｅｔ Ｐｒｏｔｏｃｏｌ）などの利用分野の拡大によって、インターネットのトラヒックが急激に増加している。ギガ（Ｇｉｇａ）またはテラ（Ｔｅｒａ）級の高速ルータ（ｒｏｕｔｅｒ）において、遅延なしで目的経路を発見することによってパケットを次のホップインターフェース（ｈｏｐ ｉｎｔｅｒｆａｃｅ）に伝送することが技術的な懸案になっている。前記ルータの物理的入力インターフェースを通して伝達されるパケットの目的地経路を発見するために、最短経路のルーティング（または、フォワーディング）テーブルの維持及び検索時間の短縮が要求される。
【０００３】
従来のルータにおいて、パケットを処理し、該パケットの目的地を検索するために要する時間が伝送路を通して到達されるパケットの伝送時間に比べて高速であるので、サブネットワークまたは他のネットワークを連結する接続ノードとしてのルータの機能の遂行には問題がなかった。最近、ＰＯＳ ＯＣ−１９２（１０Ｇｂｐｓ）またはＩＰ ｏｖｅｒ ＤＷＤＭ（Ｄｅｎｓｅ Ｗａｖｅｌｅｎｇｔｈ Ｄｉｖｉｓｉｏｎ Ｍｕｌｔｉｐｌｅｘｉｎｇ）などの光ネットワークインターフェースの帯域幅が増加し、それとともに、パケットの伝送時間がルータにおける処理時間より相対的に短くなり、さらに、この帯域幅の増加は、ルータが高速インターネット上でボトルネック（ｂｏｔｔｌｅｎｅｃｋ）の主要原因を提供するという非難を招いた。前記のような技術としては、Ｋｅｓｈａｖ， Ｓ． ａｎｄ Ｓｈａｒｍａ， Ｒ．， Ｉｓｓｕｅｓ ａｎｄ Ｔｒｅｎｄｓ ｉｎ Ｒｏｕｔｅｒ Ｄｅｓｉｇｎ， ＩＥＥＥ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ Ｍａｇａｚｉｎｅ， ｐａｇｅｓ １４４−１５１，Ｍａｙ，１９９８、Ｋｕｍａｒ， Ｖ． ａｎｄ Ｌａｋｓｈｍａｎ， Ｔ． ａｎｄ Ｓｔｉｌｉａｄｉｓ， Ｄ．， Ｂｅｙｏｎｄ Ｂｅｓｔ Ｅｆｆｏｒｔ： Ｒｏｕｔｅｒ Ａｒｃｈｉｔｅｃｔｕｒｅｓ ｆｏｒ ｔｈｅ Ｄｉｆｆｅｒｅｎｔｉａｔｅｄ Ｓｅｒｖｉｃｅｓ ｏｆ Ｔｏｍｏｒｒｏｗ’ｓ Ｉｎｔｅｒｎｅｔ， ＩＥＥＥ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ Ｍａｇａｚｉｎｅ， ｐａｇｅｓ １５２−１６４，Ｍａｙ，１９９８、Ｃｈａｎ， Ｈ．， Ａｌｎｕｗｅｉｒｉ， Ｈ． ａｎｄ Ｌｅｕｎｇ， Ｖ．， Ａ Ｆｒａｍｅｗｏｒｋ ｆｏｒ Ｏｐｔｉｍｉｚｉｎｇ ｔｈｅ Ｃｏｓｔ ａｎｄ Ｐｅｒｆｏｒｍａｎｃｅ ｏｆ Ｎｅｘｔ−Ｇｅｎｅｒａｔｉｏｎ ＩＰ Ｒｏｕｔｅｒｓ， ＩＥＥＥ Ｊｏｕｒｎａｌ ｏｆ Ｓｅｌｅｃｔｅｄ Ａｒｅａｓ ｉｎ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ， Ｖｏｌ． １７， Ｎｏ．６， ｐａｇｅｓ １０１３−１０２９， Ｊｕｎｅ １９９９、Ｐａｒｔｒｉｄｇｅ， Ｃ． ｅｔ ａｌ．， Ａ ５０−Ｇｂ／ｓ ＩＰ Ｒｏｕｔｅｒ， ＩＥＥＥ／ＡＣＭ Ｔｒａｎｓ． ｏｎ Ｎｅｔｗｏｒｋｉｎｇ， ｖｏｌ． ６， ｎｏ．３， ｐａｇｅｓ ２３７−２４８， １９９８、及びＭｅｔｚ， Ｃ．， ＩＰ Ｒｏｕｔｅｒｓ： Ｎｅｗ Ｔｏｏｌ ｆｏｒ Ｇｉｇａｂｉｔ Ｎｅｔｗｏｒｋｉｎｇ， ＩＥＥＥ Ｉｎｔｅｒｎｅｔ Ｃｏｍｐｕｔｉｎｇ， ｐａｇｅｓ １４−１８， Ｎｏｖ．−Ｄｅｃ．，１９９８．に開示されている。
【０００４】
１９９０年代初めに、インターネットの技術標準を管理するＩＥＴＦ（Ｉｎｔｅｒｎｅｔ Ｅｎｇｉｎｅｅｒｉｎｇ Ｔａｓｋ Ｆｏｒｃｅ）のワーキンググループ（ｗｏｒｋｉｎｇ ｇｒｏｕｐ）は、ＩＰｖ４（ＩＰ ｖｅｒｓｉｏｎ ４）におけるＩＰアドレスを効率的に使用するＣＩＤＲ（Ｃｌａｓｓｌｅｓｓ Ｉｎｔｅｒ−Ｄｏｍａｉｎ Ｒｏｕｔｉｎｇ）という新しいＩＰアドレシング方式を導入した。これは、ＲＦＣ（Ｒｅｑｕｅｓｔ ｆｏｒ Ｃｏｍｍｅｎｔｓ ： Ｎｅｔｗｏｒｋ Ｗｏｒｋｉｎｇ Ｇｒｏｕｐ） １５１８， Ａｎ Ａｒｃｈｉｔｅｃｔｕｒｅ ｆｏｒ ＩＰ Ａｄｄｒｅｓｓ Ａｌｌｏｃａｔｉｏｎ ｗｉｔｈ ＣＩＤＲ， Ｓｅｐｔ． １９９３及びＲＦＣ １５１７， Ａｐｐｌｉｃａｂｉｌｉｔｙ Ｓｔａｔｅｍｅｎｔ ｆｏｒ ｔｈｅ Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｏｆ Ｃｌａｓｓｌｅｓｓ Ｉｎｔｅｒ−Ｄｏｍａｉｎ Ｒｏｕｔｉｎｇ （ＣＩＤＲ）， Ｓｅｐｔ． １９９３．に開示されている。
【０００５】
この場合、多様なプレフィックス（ｐｒｅｆｉｘ）長さを有するパケットにおいて対応するプレフィックスを把握し、最長プレフィックス（ｌｏｎｇｅｓｔ ｐｒｅｆｉｘ）に一致（ｍａｔｃｈｉｎｇ）するＩＰアドレスを発見するために、一般的に、トライ（ｔｒｉｅ）またはパトリシア（Ｐａｔｒｉｃｉａ： Ｐｒａｃｔｉｃａｌ Ａｌｇｏｒｉｔｈｍ ｔｏ Ｒｅｔｒｉｅｖｅ Ｉｎｆｏｒｍａｔｉｏｎ Ｃｏｄｅｄ ａｓ Ａｌｐｈａｎｕｍｅｒｉｃ）トライデータ構造に基づいたＬＰＭ（Ｌｏｎｇｅｓｔ Ｐｒｅｆｉｘ Ｍａｔｃｈｉｎｇ）アルゴリズムが使用されてきた。これは、Ｄｏｅｒｉｎｇｅｒ， Ｗ．， Ｋａｒｊｏｔｈ， Ｇ． ａｎｄ Ｎａｓｓｅｈｉ， Ｍ．， Ｒｏｕｔｉｎｇ ｏｎ Ｌｏｎｇｅｓｔ−Ｍａｔｃｈｉｎｇ Ｐｒｅｆｉｘｅｓ， ＩＥＥＥ／ＡＣＭ Ｔｒａｎｓ． ｏｎ Ｎｅｔｗｏｒｋｉｎｇ， ｖｏｌ．４， ｎｏ．１， ｐａｇｅｓ ８６−９７， Ｆｅｂ．， １９９６．に開示されている。
【０００６】
以下、表１を参照して前記ＬＭＰアルゴリズムを詳細に説明する。表１は、ルーティング（または、フォワーディング）テーブルに含まれるルーティングエントリの簡単な例を示す。ＩＰｖ４の場合に、実は前記プレフィックスが３２を超過することはできないが、表１における星印は、‘０’または‘１’からなる任意の数を詰めることを可能にする。例えば、‘０＊’は、‘０１＊’、‘０１１＊’、または‘０１０＊’を含み、残りのビットストリング（ｂｉｔ ｓｔｒｉｎｇ）がどういうものなのかは問題にならない。
【表１】
2004517519.tif 000003
【０００７】
ルーティングエントリまたはルートは、｛＜ｎｅｔｗｏｒｋ ｐｒｅｆｉｘ＞，＜ｈｏｓｔ ｎｕｍｂｅｒ＞｝からなるＩＰアドレスによって表現される。目的地ＩＰアドレスが‘１００１０１０１０００…０’である場合、この目的地ＩＰアドレスの１番目のビットは、前記ルーティングテーブルに含まれるネットワークプレフィックス（以下、簡単にプレフィックスと称する）と比較される。従って、‘０＊’、‘０１０１０＊’、‘０１０１０１＊’、及び‘０１０１０１１＊’などのプレフィックスは、自分の１番目のビットが‘０’から始まるので、除かれる。所定の目的地アドレスを残りのプレフィックスと比較する場合、プレフィックス‘１１＊’、‘１１１０＊’、及び‘１００１０１０１０１＊’は、前記目的地アドレスと２番目のビットまたは１０番目のビットで一致しないので、除かれる。次に、残りの対象プレフィックス（つまり、‘１＊’、‘１０＊’、及び‘１００１０１０１０＊’）のうち、‘１００１０１０１０＊’が前記最長プレフィックス（または、ｍｏｓｔ ｓｐｅｃｉｆｉｃ）一致ルートとして選択され、当該目的地ＩＰアドレスを有するＩＰパケットは、インターフェース‘１０’を通して隣接ルータに伝送される。
【０００８】
一方、最近発表された経路検索（ｒｏｕｔｉｎｇ ｌｏｏｋｕｐ）アルゴリズムは、メモリアクセス時間を短縮するために、使用できるプロセッサ（ルーティングプロセッサまたはフォワーディングエンジン）内のキャッシュメモリ（ｃａｃｈｅ ｍｅｍｏｒｙ）に貯蔵される。このルーティングテーブルに基づいた経路検索アルゴリズムは、効率的な検索を支援するが、ルーティングテーブルまたはフォーワーディングテーブルを変更することはできない。従って、この経路検索アルゴリズムは、変更されたルートの反映による遅延時間を生じさせる可能性がある。
【０００９】
さらに、ルーティングプロセッサにおけるルーティングテーブルは、ＤＭＡ（Ｄｉｒｅｃｔ Ｍｅｍｏｒｙ Ａｃｃｅｓｓ）カード、ＩＰＣ（Ｉｎｔｅｒ−Ｐｒｏｃｅｓｓｏｒ Ｃｏｍｍｕｎｉｃａｔｉｏｎ）カード、またはスイッチファブリックを通してコピーされて、フォワーディングエンジンにおけるフォワーディングテーブルに適用される。この時、変更されたルートのみを追加及び削除するのではなく、新しいフォワーディングテーブルを構築する必要がある。これは、追加的な時間遅延を生じさせ、さらに、ルータからのメモリアクセス要求によるメモリ帯域幅使用の増加によって、ルータの内部メモリまたはシステムバス（ｓｙｓｔｅｍ ｂｕｓ）におけるボトルネックを生じさせる可能性がある。
【００１０】
さらに、一部のアルゴリズムにおいて、最初のルーティングテーブル（または、フォワーディングテーブル）は、ルータの現在のリンク状態を示す“リンク情報（ｌｉｎｋ ｒｅａｃｈａｂｉｌｉｔｙ ｉｎｆｏｒｍａｔｉｏｎ）”を使用して構成されるべきである。従って、リンク情報を順にルーティングテーブルに挿入するためには、前もってプレフィックス長さ別に全てのルートを分類（ｓｏｒｔｉｎｇ）する追加的な作業が必要である。このようなアルゴリズムの例としては、Ｄｅｇｅｒｍａｒｋ， Ｍ．， Ｂｒｏｄｎｉｋ， Ａ．， Ｃａｒｌｓｓｏｎ， Ｓ． ａｎｄ Ｐｉｎｋ， Ｓ．， Ｓｍａｌｌ Ｆｏｒｗａｒｄｉｎｇ Ｔａｂｌｅｓ ｆｏｒ Ｆａｓｔ Ｒｏｕｔｉｎｇ Ｌｏｏｋｕｐｓ， Ｉｎ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＡＣＭ ＳＩＧＣＯＭＭ ’９７， ｐａｇｅｓ ３−１４， Ｃａｎｎｅｓ， Ｆｒａｎｃｅ， １９９７、Ｓｒｉｎｉｖａｓａｎ， Ｖ． ａｎｄ Ｖａｒｇｈｅｓｅ， Ｇ．， Ｆａｓｔｅｒ ＩＰ Ｌｏｏｋｕｐｓ ｕｓｉｎｇ Ｃｏｎｔｒｏｌｌｅｄ Ｐｒｅｆｉｘ Ｅｘｐａｎｓｉｏｎ， Ｉｎ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＡＣＭ Ｓｉｇｍｅｔｒｉｃｓ ’９８ Ｃｏｎｆ．， ｐａｇｅｓ １−１１， １９９８、Ｌａｍｐｓｏｎ， Ｂ．， Ｓｒｉｎｉｖａｓａｎ， Ｖ． ａｎｄ Ｖａｒｇｈｅｓｅ， Ｇ．， ＩＰ Ｌｏｏｋｕｐｓ ｕｓｉｎｇ Ｍｕｌｔｉｗａｙ ａｎｄ Ｍｕｌｔｉｃｏｌｕｍｎ Ｓｅａｒｃｈ， Ｉｎ ＩＥＥＥ Ｉｎｆｏｃｏｍ， ｐａｇｅｓ １２４８−１２５６， １９９８、Ｔｚｅｎｇ， Ｈ． ａｎｄ Ｐｒｙｚｙｇｉｅｎｄａ， Ｔ．， Ｏｎ Ｆａｓｔ Ａｄｄｒｅｓｓ−Ｌｏｏｋｕｐ Ａｌｇｏｒｉｔｈｍｓ， ＩＥＥＥ Ｊｏｕｒｎａｌ ｏｎ Ｓｅｌｅｃｔｅｄ Ａｒｅａｓ ｉｎ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ， Ｖｏｌ． １７， Ｎｏ． ６， ｐａｇｅｓ １０６７−１０８２， Ｊｕｎｅ， １９９９、Ｗａｌｄｖｏｇｅｌ， Ｍ．， Ｖａｒｇｈｅｓｅ， Ｇ．， Ｔｕｒｎｅｒ， Ｊ． ａｎｄ Ｐｌａｔｔｎｅｒ， Ｂ．， Ｓｃａｌａｂｌｅ Ｈｉｇｈ Ｓｐｅｅｄ ＩＰ Ｒｏｕｔｉｎｇ Ｌｏｏｋｕｐｓ， Ｉｎ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＡＣＭ ＳＩＧＣＯＭＭ ’９７， Ｃａｎｎｅｓ， Ｆｒａｎｃｅ， ｐａｇｅｓ ２５−３７， １９９７、及びＷａｌｄｖｏｇｅｌ， Ｍ．， Ｖａｒｇｈｅｓｅ， Ｇ．， Ｔｕｒｎｅｒ， Ｊ． ａｎｄ Ｐｌａｔｔｎｅｒ， Ｂ．， Ｓｃａｌａｂｌｅ Ｂｅｓｔ Ｍａｔｃｈｉｎｇ Ｐｒｅｆｉｘ Ｌｏｏｋｕｐｓ， Ｉｎ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＰＯＤＣ ’９８， Ｐｕｅｒｔｏ Ｖａｌｌａｒｔａ， ｐａｇｅ， １９９８．がある。
【００１１】
ルーティングテーブルにおいて代表的に使用されるデータ構造である“ｒａｄｉｘ ｔｒｅｅ”または“Ｐａｔｒｉｃｉａ ｔｒｉｅ”は、パケット経路を探すために要求されるメモリアクセスの数が増加するだけでなく、該当ルータの隣接ルータからルートを設定または削除することによって発生するルート変更を反映するためには、かなりの更新時間が要求される。Ｄｅｇｅｒｍａｒｋ， Ｍ．， Ｂｒｏｄｎｉｋ， Ａ．， Ｃａｒｌｓｓｏｎ， Ｓ． ａｎｄ Ｐｉｎｋ， Ｓ．， Ｓｍａｌｌ Ｆｏｒｗａｒｄｉｎｇ Ｔａｂｌｅｓ ｆｏｒ Ｆａｓｔ Ｒｏｕｔｉｎｇ Ｌｏｏｋｕｐｓ， Ｉｎ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＡＣＭ ＳＩＧＣＯＭＭ ’９７， ｐａｇｅｓ ３−１４， Ｃａｎｎｅｓ， Ｆｒａｎｃｅ， １９９７には、フォーワーディングエンジンにおいてキャッシュに貯蔵できるコンパクト（ｃｏｍｐａｃｔ）フォーワーディングテーブルが提示されているが、該当テーブルのルート変更を反映することは大変である。Ｓｒｉｎｉｖａｓａｎ， Ｖ． ａｎｄ Ｖａｒｇｈｅｓｅ， Ｇ．， Ｆａｓｔｅｒ ＩＰ Ｌｏｏｋｕｐｓ ｕｓｉｎｇ Ｃｏｎｔｒｏｌｌｅｄ Ｐｒｅｆｉｘ Ｅｘｐａｎｓｉｏｎ， Ｉｎ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＡＣＭ Ｓｉｇｍｅｔｒｉｃｓ ’９８ Ｃｏｎｆ．， ｐａｇｅｓ １−１１， １９９８によって提示された“ｃｏｎｔｒｏｌｌｅｄ ｐｒｅｆｉｘ ｅｘｐａｎｓｉｏｎ”方式（Ｕ．Ｓ． Ｐａｔｅｎｔ Ｎｏ． ６，０１１，７９５， ｉｓｓｕｅｄ ｔｏ Ｇｅｏｒｇｅ Ｖａｒｇｈｅｓｅ ａｎｄ Ｓｒｉｎｉｖａｓａｎ ａｎｄ ｅｎｔｉｔｌｅｄ Ｍｅｔｈｏｄ ａｎｄ Ａｐｐａｒａｔｕｓ ｆｏｒ Ｆａｓｔ Ｈｉｅｒａｒｃｈｉｃａｌ Ａｄｄｒｅｓｓ Ｌｏｏｋｕｐ Ｕｓｉｎｇ Ｃｏｎｔｒｏｌｌｅｄ Ｅｘｐａｎｓｉｏｎ ｏｆ Ｐｒｅｆｉｘｅｓ）及びＴｚｅｎｇ， Ｈ． ａｎｄ Ｐｒｙｚｙｇｉｅｎｄａ， Ｔ．， Ｏｎ Ｆａｓｔ Ａｄｄｒｅｓｓ−Ｌｏｏｋｕｐ Ａｌｇｏｒｉｔｈｍｓ， ＩＥＥＥ Ｊｏｕｒｎａｌ ｏｎ Ｓｅｌｅｃｔｅｄ Ａｒｅａｓ ｉｎ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ， Ｖｏｌ． １７， Ｎｏ． ６， ｐａｇｅｓ １０６７−１０８２， Ｊｕｎｅ， １９９９によって提示された高速（ｆａｓｔ）アドレス検索アルゴリズムも“ｍｕｌｔｉ−ｒｅｓｏｌｕｔｉｏｎ ｔｒｉｅ”に基づいているが、そのデータ構造は前記トライ（ｔｒｉｅ）に基づいているので、ルートの追加及び削除が容易でない。これに関連して、米国特許番号第６，０６１，７１２（Ｍｅｔｈｏｄ ｆｏｒ ＩＰ Ｒｏｕｔｉｎｇ Ｔａｂｌｅ Ｌｏｏｋ−ｕｐ）及び米国特許番号第６，０６７，５７４（Ｈｉｇｈ Ｓｐｅｅｄ Ｒｏｕｔｉｎｇ Ｕｓｉｎｇ Ｃｏｍｐｒｅｓｓｅｄ Ｔｒｅｅ Ｐｒｏｃｅｓｓ）が、Ｈｏｎｇ−Ｙｉ Ｔｚｅｎｇに許与されている。ハッシュテーブルを使用してトライ構造を２進検索ツリー（ｂｉｎａｒｙ ｔｒｅｅ）にマッピングすることによる“ｒｏｐｅ ｓｅａｒｃｈ”アルゴリズム（Ｗａｌｄｖｏｇｅｌ， Ｍ．， Ｖａｒｇｈｅｓｅ， Ｇ．， Ｔｕｒｎｅｒ， Ｊ． ａｎｄ Ｐｌａｔｔｎｅｒ， Ｂ．， Ｓｃａｌａｂｌｅ Ｈｉｇｈ Ｓｐｅｅｄ ＩＰ Ｒｏｕｔｉｎｇ Ｌｏｏｋｕｐｓ， Ｉｎ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＡＣＭ ＳＩＧＣＯＭＭ ’９７， Ｃａｎｎｅｓ， Ｆｒａｎｃｅ， ｐａｇｅｓ ２５−３７， １９９７及びＷａｌｄｖｏｇｅｌ， Ｍ．， Ｖａｒｇｈｅｓｅ， Ｇ．， Ｔｕｒｎｅｒ， Ｊ． ａｎｄ Ｐｌａｔｔｎｅｒ， Ｂ．， Ｓｃａｌａｂｌｅ Ｂｅｓｔ Ｍａｔｃｈｉｎｇ Ｐｒｅｆｉｘ Ｌｏｏｋｕｐｓ， Ｉｎ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＰＯＤＣ ’９８， Ｐｕｅｒｔｏ Ｖａｌｌａｒｔａ， ｐａｇｅ， １９９８）及び（Ｔｚｅｎｇ， Ｈ． ａｎｄ Ｐｒｙｚｙｇｉｅｎｄａ， Ｔ．， Ｏｎ Ｆａｓｔ Ａｄｄｒｅｓｓ−Ｌｏｏｋｕｐ Ａｌｇｏｒｉｔｈｍｓ， ＩＥＥＥ Ｊｏｕｒｎａｌ ｏｎ Ｓｅｌｅｃｔｅｄ Ａｒｅａｓ ｉｎ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ， Ｖｏｌ． １７， Ｎｏ． ６， ｐａｇｅｓ １０６７−１０８２， Ｊｕｎｅ， １９９９）による“ｍｕｌｔｉ−ｒｅｓｏｌｕｔｉｏｎ ｔｒｉｅ”に基づいたコンプリート（ｃｏｍｐｌｅｔｅ）プレフィックストライは、それぞれのデータ構造が前記トライに基づいているので、変更されたルートエントリの更新によって非効率的になる傾向がある。これに関連して、米国特許番号第６，０１８，５２４（Ｓｃａｌａｂｌｅ Ｈｉｇｈ Ｓｐｅｅｄ ＩＰ Ｒｏｕｔｉｎｇ Ｌｏｏｋｕｐｓ）がＪｏｎａｔｈａｎ Ｔｕｒｎｅｒ、Ｇｅｏｒｇｅ Ｖａｒｇｈｅｓｅ、及びＭａｒｃｅｌ Ｗａｌｄｖｏｇｅｌに許与されている。
【００１２】
これら以外にも、前記トライの他の変形が提示されている。例えば、検索時間を減少させるために２つのトライ（ｔｒｉｅ）を連結する“ｔｗｏ−ｔｒｉｅ”方式（Ｋｉｊｋａｎｊａｎａｒａｔ， Ｔ． ａｎｄ Ｃｈａｏ， Ｈ．， Ｆａｓｔ ＩＰ Ｌｏｏｋｕｐｓ Ｕｓｉｎｇ ａ Ｔｗｏ−ｔｒｉｅ Ｄａｔａ Ｓｔｒｕｃｔｕｒｅ， Ｉｎ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ Ｇｌｏｂｅｃｏｍ’９９， １９９９）及びトライのレベル長さを短縮させるための“ＬＣ−ｔｒｉｅｓ”（Ｎｉｌｌｓｏｎ， Ｓ． ａｎｄ Ｋａｒｌｓｏｓｏｎ， Ｇ．， ＩＰ−Ａｄｄｒｅｓｓｅｓ Ｌｏｏｋｕｐ Ｕｓｉｎｇ ＬＣ−Ｔｒｉｅｓ， ＩＥＥＥ Ｊｏｕｒｎａｌ ｏｎ Ｓｅｌｅｃｔｅｄ Ａｒｅａｓ ｉｎ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ， Ｖｏｌ．１７， Ｎｏ． １６， ｐａｇｅｓ １０８３−１０９２， １９９９）、及び“ＤＰ−ｔｒｉｅｓ”（Ｄｏｅｒｉｎｇｅｒ， Ｗ．， Ｋａｒｊｏｔｈ， Ｇ． ａｎｄ Ｎａｓｓｅｈｉ， Ｍ．， Ｒｏｕｔｉｎｇ ｏｎ Ｌｏｎｇｅｓｔ−Ｍａｔｃｈｉｎｇ Ｐｒｅｆｉｘｅｓ， ＩＥＥＥ／ＡＣＭ Ｔｒａｎｓ． ｏｎ Ｎｅｔｗｏｒｋｉｎｇ， ｖｏｌ．４， ｎｏ．１， ｐａｇｅｓ ８６−９７， Ｆｅｂ．， １９９６）も提案されている。しかしながら、ルーティングテーブル（または、フォワーディングテーブル）のルート変更の反映は依然として難しい。
【００１３】
さらに、検索時間を低減するために前述したような方式が提案されたが、ルート更新に関する問題は依然として存在する。検索時間を低減するための方法として、ハードウェア的に処理するための方法も提案されている。Ｇｕｐｔａ， Ｐ．， Ｌｉｎ， Ｓ． ａｎｄ ＭｃＫｅｏｗｎ， Ｎ．， Ｒｏｕｔｉｎｇ Ｌｏｏｋｕｐｓ ｉｎ Ｈａｒｄｗａｒｅ ａｔ Ｍｅｍｏｒｙ Ａｃｃｅｓｓ Ｓｐｅｅｄｓ， Ｉｎ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＩＥＥＥ ＩＮＦＯＣＯＭ ’９８ Ｃｏｎｆ．， ｐａｇｅｓ １２４０−１２４７， １９９８に開示したように、大容量のメモリの使用による方法が提示された。この方式は、ソフトウェア的な方法に比べて検索時間は短縮されるが、ＩＰｖ６（Ｉｎｔｅｒｎｅｔ Ｐｒｏｔｏｃｏｌ ｖｅｒｓｉｏｎ ６）に遷移する時は、メモリの容量またはコストなどの問題が依然として発生する。ＭｃＡｕｌｅｙ， Ａ． ａｎｄ Ｆｒａｎｃｉｓ， Ｐ．， Ｆａｓｔ Ｒｏｕｔｉｎｇ Ｔａｂｌｅ Ｌｏｏｋｕｐ Ｕｓｉｎｇ ＣＡＭｓ， Ｉｎ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＩＥＥＥ ＩＮＦＯＣＯＭ ’９３， Ｖｏｌ．３， ｐａｇｅｓ １３８２−１３９１， １９９３によってＣＡＭ（Ｃｏｎｔｅｎｔ Ａｄｄｒｅｓｓａｂｌｅ Ｍｅｍｏｒｙ）を使用する方法が提案されたが、ＣＡＭの高い値段のため、現在は考慮していない。Ｈｕａｎｇ， Ｎ． ａｎｄ Ｚｈａｏ， Ｓ．， Ａ Ｎｏｖｅｌ ＩＰ−Ｒｏｕｔｉｎｇ Ｌｏｏｋｕｐ Ｓｃｈｅｍｅ ａｎｄ Ｈａｒｄｗａｒｅ Ａｒｃｈｉｔｅｃｔｕｒｅ ｆｏｒ Ｍｕｌｔｉｇｉｇａｂｉｔ Ｓｗｉｔｃｈｉｎｇ Ｒｏｕｔｅｒｓ， ＩＥＥＥ Ｊｏｕｒｎａｌ ｏｎ Ｓｅｌｅｃｔｅｄ Ａｒｅａｓ ｉｎ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ， Ｖｏｌ． １７， Ｎｏ． ６， ｐａｇｅｓ １０９３−１１０４， Ｊｕｎｅ， １９９９は、メモリアクセスを低減するためにパイプライン（ｐｉｐｅｌｉｎｅ）式のメモリを使用する“ｉｎｄｉｒｅｃｔ ｌｏｏｋｕｐ”アルゴリズムを提示しているが、これもＩＰｖ６への適用は困難である。
【００１４】
【発明が解決しようとする課題】
従って、本発明の目的は、無作為抽出（ｒａｎｄｏｍｉｚｅｄ）アルゴリズムを使用してメモリアクセス時間を最小にすることができることによって、費用効率の高いメモリ使用を可能にする高速ＩＰルートルックアップ遂行及びルーティング／フォワーディングテーブル管理のための方法を提供することにある。
【００１５】
本発明の他の目的は、ルートの追加及び削除に対する変更及び管理が容易にできる高速ＩＰルートルックアップ遂行及びルーティング／フォワーディングテーブル管理のための方法を提供することにある。
【００１６】
本発明のまた他の目的は、テーブルを構成する時、入力しようとするルートのプレフィックス長さによって関連ルートを分類（ｓｏｒｔｉｎｇ）せずに、ルーティングテーブル／フォワーディングテーブルを効率的に構築することのできる高速ＩＰルータルックアップ遂行及びルーティング／フォワーディングテーブル管理のための方法を提供することにある。
【００１７】
【課題を解決するための手段】
このような目的を達成するための本発明の第１特徴によると、本発明は、所定の最大の値のキーを有するヘッダノード、及び減少される順で予め設定される固定的な（可変的な）範囲のキーを有し、それぞれのプレフィックス長さに関連したハッシュテーブルにそれぞれのプレフィックス長さに対応するルートエントリを貯蔵する複数のノードを含むスキップリストを使用して、キーとしてプレフィックス長さ範囲を有するＩＰアドレス検索方法を提供する。
【００１８】
本発明の第２特徴によると、本発明は、前記スキップリスト内の全てのノードを取り扱うために最大レベルを有するヘッダノードを生成する過程と、前記スキップリストにプレフィックス範囲をキーとして有する複数のサブノードを挿入する過程と、それぞれのサブノードにおいて、プレフィックス範囲に対応する各ノードで与えられたルートエントリを貯蔵するためのハッシュテーブルを生成する過程と、からなるスキップリストを利用するＩＰルーティングテーブル生成方法を提供する。
【００１９】
本発明の第３特徴によると、本発明は、ＩＰアドレスのプレフィックス長さ範囲によって生成されたそれぞれのノードで設定されたプレフィックス長さによるハッシュテーブルの形態でルートエントリが貯蔵されるスキップリストを利用したルーティング／フォワーディングテーブルの更新方法を提供する。この方法は、更新されるルートのプレフィックス長さに対応するプレフィックス範囲が設定されたノードを見つける過程と、前記見つけたノードで前記更新されるルートと同一のプレフィックス長さを有するハッシュテーブルを検索する過程と、前記ハッシュテーブルを発見した時、前記ハッシュテーブルにおいて該当ルートを更新する過程と、からなる。
【００２０】
本発明の第４特徴によると、本発明は、ＩＰアドレスのプレフィックス範囲の割り当てによって生成されるそれぞれのノードで予め設定されたプレフィックス長さによるハッシュテーブルの形態でルートエントリが貯蔵されるスキップリストを利用するルーティング／フォワーディングテーブルのルートルックアップ方法を提供する。この方法は、前記スキップリストの第１ノードから始まって隣接したノードを見つける過程と、該当ノードで目的地アドレスとそれぞれのハッシュテーブルを比較する過程と、前記ハッシュテーブルが前記目的地アドレスを含む場合、一致するプレフィックスを最長プレフィックスとみなす過程と、からなる。
【００２１】
【発明の実施の形態】
以下、本発明に従う好適な実施形態について添付図を参照しつつ詳細に説明する。下記の説明において、本発明の要旨のみを明確にする目的で、関連した公知機能または構成に関する具体的な説明は省略する。
【００２２】
まず、本発明が適用できるルータ及びルーティング方式に関して説明する。Ｃｈａｎ ｅｔ ａｌ． （Ａ Ｆｒａｍｅｗｏｒｋ ｆｏｒ Ｏｐｔｉｍｉｚｉｎｇ ｔｈｅ Ｃｏｓｔ ａｎｄ Ｐｅｒｆｏｒｍａｎｃｅ ｏｆ Ｎｅｘｔ−Ｇｅｎｅｒａｔｉｏｎ ＩＰ Ｒｏｕｔｅｒｓ， ＩＥＥＥ Ｊｏｕｒｎａｌ ｏｆ Ｓｅｌｅｃｔｅｄ Ａｒｅａｓ ｉｎ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ， Ｖｏｌ． １７， Ｎｏ．６， ｐａｇｅｓ １０１３−１０２９， Ｊｕｎｅ １９９９）は、高速ルータ構造の主要傾向である分散構造及び並列構造に分類され、この分類は、フォワーディングエンジンの位置によって区分される。高速バックボーン（ｂａｃｋｂｏｎｅ）ルータは、従来の集中構造より分散構造を取る傾向である。
【００２３】
図１は、本発明が適用できる分散構造を有するルータを示す図である。図１を参照すると、ルータは、パケットが入力及び出力されるフォワーディングエンジン（Ｆｏｒｗａｒｄｉｎｇ Ｅｎｇｉｎｅ： ＦＥ）が装着されたラインカードモジュール（ｌｉｎｅ ｃａｒｄ ｍｏｄｕｌｅ）１１０、初期ルーティングテーブル（ＲＴ）の構築及び該ルーティングテーブルの管理を遂行するルーティングプロセッサ（ｒｏｕｔｉｎｇ ｐｒｏｃｅｓｓｏｒ）１２０、及びパケットがルータ内において特定のポート（ｐｏｒｔ）にスイッチングされる時に使用されるスイッチファブリック（ｓｗｉｔｃｈ ｆａｂｒｉｃ）１３０から構成される。
【００２４】
ルーティングプロセッサ１２０は、最近変更されたルートを反映することによって更新されたルーティングテーブル（ＲＴ）を備える。ルーティングテーブル（ＲＴ）は、ＲＩＰ（Ｒｏｕｔｉｎｇ Ｉｎｆｏｒｍａｔｉｏｎ Ｐｒｏｔｏｃｏｌ）、ＯＳＰＦ（Ｏｐｅｎ Ｓｈｏｒｔｅｓｔ Ｐａｔｈ Ｆｉｒｓｔ）、またはＢＧＰ−４（Ｂｏｒｄｅｒ Ｇａｔｅｗａｙ Ｐｒｏｔｏｃｏｌ ４）などのルーティングプロトコルから生成されるが、これらプロトコルに限定されない。効率的な検索のために考案されたフォワーディングテーブル（ＦＴ）であるコンパクトテーブルは、ルーティングプロセッサ１２０のルーティングテーブルからコピーされる。フォワーディングテーブルは、ルートの追加及び削除の効率性を犠牲にすることによって、検索効率のみのために設計された。
【００２５】
ラインカードモジュール１１０から受信されるパケットがフォワーディングテーブル（ＦＴ）から目的経路を発見することができない場合、当該パケットは、スイッチファブリック１３０を通してルーティングプロセッサ１２０に移動して発見できなかった経路に対する問題を解決すべきである。目的地を発見した後、前記パケットは、出力ラインカードモジュール１１０に伝送されるために、再びスイッチファブリック１３０に伝送されるべきである。ルーティングプロセッサ１２０がルーティングテーブル（ＲＴ）を通しても目的経路を発見することができなかった場合、前記パケットは、ルーティングプロセッサ１２０で捨てられる。
【００２６】
一方、Ａｓｔｈａｎａ， Ａ．， Ｄｅｌｐｈ， Ｃ．， Ｊａｇａｄｉｓｈ， Ｈ．， ａｎｄ Ｋｒｚｙｚａｎｏｗｓｋｉ， Ｐ．， Ｔｏｗａｒｄｓ ａ Ｇｉｇａｂｉｔ ＩＰ Ｒｏｕｔｅｒ， Ｊ． Ｈｉｇｈ Ｓｐｅｅｄ Ｎｅｔｗｏｒｋ， ｖｏｌ． １， ｎｏ．４， ｐａｇｅｓ ２８１−２８８，１９９２及びＰａｒｔｒｉｄｇｅ ｅｔ ａｌ． （Ａ ５０−Ｇｂ／ｓ ＩＰ Ｒｏｕｔｅｒ， ＩＥＥＥ／ＡＣＭ Ｔｒａｎｓ． ｏｎ Ｎｅｔｗｏｒｋｉｎｇ， ｖｏｌ． ６， ｎｏ．３， ｐａｇｅｓ ２３７−２４８， １９９８）は、並列構造のルータに関して開示している。図２は、本発明が適用できる並列構造を有するルータを示す図である。図２に示す並列構造のルータにおいて、フォワーディングテーブル（ＦＴ）を有する各フォワーディングエンジン１１２は、ラインカードモジュール１１０において分離される。このような並列構造は、各フォワーディングエンジンにおいて並列パケット処理及びルートルックアップを取り扱うためにクライアント及びサーバー基盤のモデルを利用する。
【００２７】
ルーティングプロセッサ１２０におけるルーティングテーブルは、変更されたルートを直ちに反映して容易に維持することができるように設計されるべきである。さらに、追加または削除されるルートは、フォワーディングエンジン１１２におけるフォワーディングテーブル（ＦＴ）に最小の費用でなるべく迅速に反映されるべきである。ルートが反映されなかった場合、受信（ｉｎｃｏｍｉｎｇ）パケットは、スイッチファブリック１３０を通してルーティングプロセッサ１２０に伝送されるので、当該パケットを処理するために要求される追加的なルートを通したバイパッシング（ｂｙｐａｓｓｉｎｇ）によって伝送遅延が増加する。
【００２８】
以上、分散構造及び並列構造を参照して本発明を説明したが、他の構造を有するルータにも適用できることは、当該技術分野における通常の知識を持つ者には明らかである。
【００２９】
図３は、分散または並列構造を有するルータにおけるフォワーディングエンジン１１２の構造を示す図である。図４は、ルーティングプロセッサ１２０の構造を示す図である。
【００３０】
図３を参照すると、フォワーディングエンジン１１２は、ｎ個の入力インターフェース（ｉｎｐｕｔ ｉｎｔｅｒｆａｃｅ）、ｍ個の出力インターフェース（ｏｕｔｐｕｔ ｉｎｔｅｒｆａｃｅ）、入力インターフェースを通して入力されるパケットをバッファリングするｎ個のバッファ（ｂｕｆｆｅｒ）、該バッファに貯蔵されたパケットを等級及び種類別に分類するパケット分類器（ｐａｃｋｅｔ ｃｌａｓｓｉｆｉｅｒ）、及びフォワーディングテーブル及びパケット分類器によって分類されるパケットをフォワーディングテーブルを参照して該当出力インターフェースに伝送するルートルックアップ（ｒｏｕｔｅ ｌｏｏｋｕｐ）制御部を備える。
【００３１】
図４を参照すると、ルーティングプロセッサ１２０は、図１及び図２に示すスイッチファブリック１３０との間でパケットを送受信するｎ個の入／出力インターフェース（ｉｎｐｕｔ／ｏｕｔｐｕｔ ｉｎｔｅｒｆａｃｅ）、この入／出力インターフェースを通して入出力されるパケットをバッファし、スイッチファブリック１３０と後段のルートルックアップ及び管理制御部との間をインターフェーシングするスイッチインターフェース（ｓｗｉｔｃｈ（ｏｒ ＩＰＣ） ｉｎｔｅｒｆａｃｅ）、及びルーティングテーブル及びスイッチインターフェースから提供されるパケットをルーティングテーブルを参照してスイッチインターフェースを通じ対応する入／出力インターフェースに伝送するルートルックアップ及び管理制御部（ｒｏｕｔｅ ｌｏｏｋｕｐ ａｎｄ ｍａｉｎｔｅｎａｎｃｅ）を備える。
【００３２】
ＲＦＣ標準によると、ルーティングテーブル（または、フォワーディングテーブル）は、検索のために主に使用されるデータ構造である配列（ａｒｒａｙ）、ツリー（ｔｒｅｅ）、及びトライ（ｔｒｉｅ）及びこれらを取り扱うために使用されるアルゴリズムに対しては制約がない。しかしながら、最長プレフィックスのマッチングのために、最小のメモリアクセスが必要になり、ルーティングテーブル（または、フォワーディングテーブル）内で変更されたルートが容易に更新されるべきである。
【００３３】
このために、本発明の実施形態において無作為抽出アルゴリズム（ｒａｎｄｏｍｉｚｅｄ ａｌｇｏｒｉｔｈｍ）を利用する。この無作為抽出アルゴリズムは、実行中にランダムな選択をするアルゴリズムである。無作為抽出アルゴリズムは、全ての入力に対してうまく動作（ｗｅｌｌ−ｂｅｈａｖｅｄ）できる設計分野に主に使用されている。これは、ある入力の処理において特定の仮定に基づいて処理することでなく、確率（例えば、コイン投げ）ｐに基づいて処理する。無作為抽出アルゴリズムの長所は、その単純性及び効率性にある。
【００３４】
無作為抽出アルゴリズムに基づいた本発明によるアルゴリズムは、最小のメモリアクセス数及びルーティングテーブルの簡単な管理を提供する。ルーティングエントリの管理の場合、全体のテーブルを再構成する従来の方式の代わりに、変更されたルート情報のみを再構成する。さらに、従来の一般的なツリーまたは２進検索トライ（ｂｉｎａｒｙ ｔｒｉｅ）のようなルートルックアップアルゴリズムとは異なって、本発明によるアルゴリズムは、図５に示す目的地ＩＰアドレスのテール（ｔａｉｌ）から最長プレフィックスを検索する。
【００３５】
さらに、本発明においては、ルーティングテーブルのために、Ｐｕｇｈ， Ｗ．， Ｓｋｉｐ Ｌｉｓｔｓ： Ａ Ｐｒｏｂａｂｉｌｉｓｔｉｃ Ａｌｔｅｒｎａｔｉｖｅｓ ｔｏ Ｂａｌａｎｃｅｄ Ｔｒｅｅｓ， ＣＡＣＭ ３３（６）， ｐａｇｅｓ ６６８９−６７６， １９９０に提示されたスキップリスト（ｓｋｉｐ ｌｉｓｔ）を使用する。
【００３６】
このスキップリストは、分類（ｓｏｒｔｉｎｇ）されたｎ個のノードを有するリンクリスト（ｌｉｎｋｅｄ ｌｉｓｔ）としてみなされ、通常、“ｓｐｒａｙ ｔｒｅｅ”などの“ｂａｌａｎｃｅｄ ｔｒｅｅ”に代わったデータ構造に使用される。これは、Ｓｌｅａｔｏｒ， Ｄ． ａｎｄ Ｔａｒｊａｎ， Ｒ．， Ｓｅｌｆ−Ａｄｊｕｓｔｉｎｇ Ｂｉｎａｒｙ Ｓｅａｒｃｈ Ｔｒｅｅｓ， ＪＡＣＭ， Ｖｏｌ． ３２， Ｎｏ． ３， Ｊｕｌｙ １９８５を参照する。従って、スキップリストは、挿入及び削除の動作のための“ｂａｌａｎｃｅｄ ｔｒｅｅ”より単純で効率的である。本発明は、図６に示すように、最長プレフィックスマッチング（ｌｏｎｇｅｓｔ ｐｒｅｆｉｘ ｍａｔｃｈｉｎｇ）のために変形したスキップリスト（ｖａｒｉａｎｔ ｏｆ ｓｋｉｐ ｌｉｓｔ）を提案する。
【００３７】
図６は、本発明の実施形態によるスキップリストの変形を示す図である。図６を参照すると、各ノードは、１つまたは多数のポインタを有し、最左のノードはヘッダノード（ｈｅａｄｅｒ ｎｏｄｅ）２１０と称されるが、その理由は、検索、追加、削除、及び更新などのスキップリストの変形に対する全ての演算（ｏｐｅｒａｔｉｏｎ）がヘッダノード２１０から始まるからである。
【００３８】
ヘッダノード２１０は、キー値として＋∞を含み、次のノードを示すためにポインタを含む。ノード２２０、２３０、２４０、２５０、及び２６０のキーは、減少の順に分類（ｓｏｒｔｉｎｇ）される。各ノードのキーは、‘プレフィックス長さ範囲’または‘プレフィックス長さ値のクラスタリング（ｃｌｕｓｔｅｒｉｎｇ）’を意味し、このキーは、減少の順に挿入される。本発明の実施形態において、検索は、既存のトライまたはツリーとはまったく異なる方式であり、葉（ｌｅａｖｅｓ）から根（ｒｏｏｔ ｏｒ ｐａｒｅｎｔ）（つまり、反転したキー値シーケンス）に遂行される。
【００３９】
第２ノード２２０のキーは、３２〜２４のプレフィックス長さ範囲を有し、このプレフィックス長さ範囲に属するプレフィックス長さを有するルートは、各プレフィックス長さに対応するハッシュテーブル（ｈａｓｈ ｔａｂｌｅ）を有する。図６は、第２ノード２２０の範囲に属するルートのハッシュテーブルの例として、プレフィックス長さが３０ビットであるハッシュテーブル２２２及びプレフィックス長さが２４ビットであるハッシュテーブル２２４を示す。さらに、図６は、１７〜１２のプレフィックス長さ範囲を有する第４ノード２４０の範囲に属するルートのハッシュテーブルの例として、プレフィックス長さが１５ビットであるハッシュテーブル２４２を示す。
【００４０】
図６に示すように、多様なノードのプレフィックス長さ範囲は異なる長さ、つまり、固定的に分けられたプレフィックス範囲に固定されるが、このようなプレフィックス長さ範囲は、可変的な長さ、つまり、可変的に分けられたプレフィックス範囲を有するノードのグループ（ｇｒｏｕｐ）に分けられることもできる。Ｓｒｉｎｉｖａｓａｎ， Ｖ． ａｎｄ Ｖａｒｇｈｅｓｅ， Ｇ．， Ｆａｓｔｅｒ ＩＰ Ｌｏｏｋｕｐｓ ｕｓｉｎｇ Ｃｏｎｔｒｏｌｌｅｄ Ｐｒｅｆｉｘ Ｅｘｐａｎｓｉｏｎ， Ｉｎ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＡＣＭ Ｓｉｇｍｅｔｒｉｃｓ ’９８ Ｃｏｎｆ．， ｐａｇｅｓ １−１１， １９９８は、最善の記憶装置を提供するためにプレフィックス範囲を分割する動的プログラミング（ｄｙｎａｍｉｃ ｐｒｏｇｒａｍｍｉｎｇ）技術に関して開示する。本発明の実施形態によるアルゴリズムにおいて、類似した方式を使用してプレフィックス長さグループを分けることができる。しかしながら、図６に示す本発明の実施形態において、固定したプレフィックス長さ範囲を有することが望ましく、これによって、動的プログラミングによる追加的な計算作業負荷を避けることができる。
【００４１】
ＩＰｖ４のケースにおいて、プレフィックス長さ範囲が８に固定される場合、挿入されるノードの総数は５（１＋［３２／８］（ここで、３２はＩＰｖ４アドレスにおける最大のビット数である））になることができる。ＩＰＭＡ（Ｉｎｔｅｒｎｅｔ Ｐｅｒｆｏｒｍａｎｃｅ Ｍｅａｓｕｒｅｍｅｎｔ Ａｎｄ Ａｎａｌｙｓｉｓ ： ｈｔｔｐ：／／ｎｉｃ．ｍｅｒｉｔ．ｅｄｕ／ｉｐｍａを参照）からの実験結果から示すように、実際に参照されるプレフィックス長さの非対称的な分散（ｓｋｅｗｅｄ ｄｉｓｔｒｉｂｕｔｉｏｎ）は、実際に参照されるプレフィックス長さ分散に存在する局所性パターン（ｌｏｃａｌｉｔｙ ｐａｔｔｅｒｎ）を示す。従って、本発明において、少数のノードを使用することが可能である。例えば、図７Ａ及び図７Ｂを参照すると、１７から２７までのプレフィックス長さが最も頻繁に参照される。従って、該当プレフィックス長さを含む範囲のプレフィックス長さキー値を有する１つのノードを設定し、他のプレフィックス長さ範囲による複数のノードを設定することができる。
【００４２】
再び図６を参照すると、ヘッダノード２１０の変数‘ＭａｘＬｅｖｅｌ’は、スキップリストに属する全てのノードのうち最大のレベル値、つまり、ヘッダノードにおいて他のノードをポインティングするためのポインタの総数を示す。各ノードは、ノードｘのレベルＬでノードｘから隣接したノードまでポインティングするためのポインタを示すキー値‘ｘ−＞ｋｅｙ’（または、ｋｅｙ（ｘ））及びポインタ‘ｘ−＞ｆｏｒｗａｒｄ［Ｌ］’（または、ｎｅｘｔ（ｘ， Ｌ））を保有する。
【００４３】
ヘッダノード２１０を除いて、ノード内の各キーは、プレフィックス長さ範囲または集合（ｓｅｔ）を有する。図６において、ノード２２０は、３２乃至２４の範囲のルートエントリを有し、各プレフィックス長さは、対応するプレフィックス長さに一致するルートエントリを貯蔵するためのハッシュテーブルを有する。３２から２４までの範囲の各プレフィックス長さに対応するルートエントリが存在する場合、該当ノードは、９つの異なるハッシュテーブルをポインティングするための９つのポインタを有する。各ハッシュテーブルは、各プレフィックス長さに正確に一致するルートエントリのみを貯蔵する。これは、スキップリストの変形を‘ｋ−ａｒｙ ｈａｓｈｅｄ ｎｏｄｅ’を有するスキップリストと称する理由である。
【００４４】
本発明によるスキップリストに基づいたアルゴリズムに対する理解を容易にするために、ヘッダノードの生成及び様々なスキップリストの構築方法に関して説明する。
【００４５】
図８は、本発明の実施形態によるヘッダノードの生成方法に関して説明する図である。図８を参照すると、ヘッダノードは、＋∞キー値及びＭａｘＬｅｖｅｌ＝５（１＋［３２／８］）を有し、ここで、ＭａｘＬｅｖｅｌ＝１＋［Ｗ／ｎ］である。ＷはＩＰアドレスのビット長さ、例えば、ＩＰｖ４：３２及びＩＰｖ６：１２８であり、ｎはプレフィックス範囲である。ヘッダノードは、包括的にスキップリスト内の全てのノードを取り扱うべきであるので、ＩＰｖ４の場合、前記確率ｐが１／２であり、プレフィックス範囲が１であると、２３２に達するルートを有するデータ構造用としてＭａｘＬｅｖｅｌ＝３２が適切である。ヘッダノードは、０乃至ＭａｘＬｅｖｅｌ−１のインデックスが付けられたＭａｘＬｅｖｅｌ個の伝送ポインタを有する。本発明の実施形態において、プレフィックス範囲を固定的にまたは可変的にクラスタリングすることによって、固定プレフィックス範囲が８であると仮定する場合、ＭａｘＬｅｖｅｌ＝５が要求される。
【００４６】
ヘッダノードが生成された後、スキップリストの異なる部分に対する構築に関して図９を参照して説明する。図９は、本発明の実施形態によるスキップリストの構築動作を説明するための図である。ヘッダノードの最上位のレベルのポインタがヌル（ｎｕｌｌ）である場合、つまり、ヘッダノードのポインタに連結されたサブノードである隣接したノードが存在しない場合、前記レベルは、ポインタが隣接したノードを示すまで１ずつ減少される。図９を参照すると、３２〜２４のプレフィックス範囲値を有する第１ノード（ａ）が生成され、ヘッダノードにおいてレベル０のポインタはその第１ノードを示す。次に、２３〜１８のプレフィックス範囲を有する第２ノード（ｂ）及び１７〜１２のプレフィックス範囲を通する第３ノード（ｃ）が順次に生成される。この生成過程において、全てのプレフィックス長さ範囲をカバーすることができるように複数のノードが生成される。
【００４７】
それぞれ生成されたノードのレベルは、プログラム３に示すように、本発明による無作為抽出アルゴリズムを利用して無作為に設定される。まず、（０，１）に属する実数の乱数値が生成される。この生成された乱数値が予め設定された基準確率値（ここで、基準確率は、理想的なスキップリストの生成のためにｐ＝１／２に設定される）より小さく、生成しようとする該当ノードのレベルがＭｘＬｅｖｅｌより小さい場合、該当ノードのレベルは増加される。そうでない場合、レベル値０を有するノードが生成される。
【００４８】
このように、スキップリストにおいてプレフィックス範囲によってノードを構成した後、ルートエントリを含むルーティングテーブルが構築されるべきである。図１０Ａを参照して、ルータがプレフィックス長さ３０のルートを有する時、ルーティングテーブルを構築する方法に関して説明する。
【００４９】
図１０Ａを参照すると、ルータがプレフィックス長さ３０のルートを有する時、スキップリストにおいて３２〜２４のプレフィックス長さ範囲を有する第１ノード２２０が検索され、次に、追加されるルートエントリがハッシュテーブルの形態で挿入される。スキップリストのノードは、対応するプレフィックス長さによって異なるハッシュテーブルを有する。同一の手順によって、図１０Ｂに示すように、１７〜１２のプレフィックス範囲を有するノード２４０下でプレフィックス長さ１５のハッシュテーブルが生成されるので、プレフィックス長さ１５のルートが追加される。
【００５０】
ルーティングテーブルの生成の手順を簡略に説明すると、図１１のようである。図１１は、本発明の実施形態によるルーティングテーブル構築の過程を示す図である。段階１１ａで、スキップリスト内の全てのノードを取り扱うためのＭａｘＬｅｖｅｌを有するヘッダノードが生成される。次に、段階１１ｂで、固定分割されたプレフィックス範囲を有するノードがリストに挿入される。段階１１ｂの動作を簡略化するために、本発明は固定分割されたプレフィックス範囲を提案しているが、実際プレフィックス長さ分散が反映されるように適応的に分割されたプレフィックス範囲を設定することもできる。それから、段階１１ｃで、対応するプレフィックス範囲を有するノード下で、それぞれの所定のルートエントリのためのハッシュテーブルが生成される。本発明による新しい方式は、最短のプレフィックス長さから検索する従来の一般的なトライまたはツリー構造とは異なって、最長プレフィックス長さを有するルートから始まる検索を提供する。
【００５１】
ルータは、接続された他のルータからしばしばルート変更情報を受信する。この変更は、現在のルーティング（または、フォワーディング伝送）テーブルに反映されるべきである。前述したように新しい方式による更新作業に対して、図１２を参照して説明する。所定の変更されたルート（プレフィックス）をルーティングテーブルに反映するために、段階１２ａで、プレフィックス長さに一致するノードを発見する。それから、段階１２ｂで、変更されたルートと同一のプレフィックス長さを有するハッシュテーブルを検索する。段階１２ｃで、該当ハッシュテーブルが発見されたと確認された場合、段階１２ｄに進行して、該当ハッシュテーブル内の前記検出されたルートを更新または削除する。段階１２ｃで、該当ハッシュテーブルが存在しないと確認される場合は、段階１２ｅに進行する。段階１２ｅで、前記ルートが追加された場合、段階１２ｆに進行して、当該変更ルートと同一のプレフィックス長さを有するハッシュテーブルを生成する。それから、段階１２ｇで、変更ルートは、新しく生成されたハッシュテーブルに挿入される。前記ルートが追加されなかった場合、段階１２ｈで、当該変更ルートは捨てられる。
【００５２】
図１３及び図１４は、本発明の実施形態によるルート検索及びルート更新の過程を説明するための図である。
【００５３】
まず、図１３を参照して、プレフィックス長さ１５のルートを検索する過程を説明する。まず、同一のプレフィックス長さ１５を有するノードを発見する。この検索は、ヘッダノード２１０の最上位レベル（レベル４）から始まる（図１３の段階（１））。レベル４のポインタは、レベル４を有する次のノード、つまり、８〜１のプレフィックス長さ範囲（キー）を有するノード２６０をポインティングする（図１３段階（２））。それから、当該ルートのプレフィックス長さとノード２６０のキーとの比較が遂行される。キー値は一致せず、検索はヘッダノード２１０の同一のレベル（例えば、レベル４）に戻る（図１３の段階（３））。ヘッダノード２１０のレベルは１の分だけ減少され（図１３の段階（４））、次のレベル（レベル３）のポインタはレベル３を通する次のノード、つまり、１７〜１２のキーを有するノード２４０をポインティングする（図１３の段階（５））。ノード２４０において一致するキー値が発見された（図１３の段階（６））場合、変更されたルートのプレフィックス長さに対応するハッシュテーブルを検索する（図１３の段階（７））。ハッシュテーブルが存在する場合、次のホップ（ｈｏｐ）（図１３の段階（８））が遂行される。ハッシュテーブルが存在する場合、そのハッシュテーブルは新しいルートを追加するために生成される。
【００５４】
図１４は、次のホップ（ｈｏｐ）インターフェースが‘１０’であるプレフィックス‘１１１０１０…１’を有するルートが、ハッシュテーブルから削除されるか、それもと次のホップが‘１’である‘１１１０１１…１’に変更される多数の段階を示す。該当プレフィックス（１１１０１０…１）を検索する段階は、図１３に示す過程と類似して遂行される。
【００５５】
以下、図１５及び図１６を参照して、ルーティングテーブルから特定の目的地ＩＰアドレスのルートを検索するルートルックアップ動作を詳細に説明する。
【００５６】
図１５及び図１６は、本発明の実施形態によるルートルックアップの過程を最長プレフィックスマッチング方式（ｌｏｎｇｅｓｔ ｐｒｅｆｉｘ ｍａｔｃｈｉｎｇ ｓｃｈｅｍｅ）として定義する。この最長プレフィックスマッチング方式に基づいた検索は、ルートエントリが最長プレフィックス、例えば、ＩＰｖ４のプレフィックス長さ３２から比較されるべきであることを意味する。図１６は、本発明の実施形態による全体のルックアップ方式を説明するための図であり、ここで、目的地アドレスは、‘１１１０１０１…１’のプレフィックス長さ１５を有する。
【００５７】
図１５の段階１５ａで、ＩＰヘッダにおいてカプセル化（ｅｎｃａｐｓｕｌａｔｅｄ）した所定の目的地アドレスに対して、スキップリストの第１ノードが検索される。従って、目的地アドレスによって与えられたルートルックアップは、ヘッダノード
２１０のレベル４から始まり（図１６の段階（１））、ヘッダノード２１０のレベルは、レベル０になるまで１ずつ減少され（図１６の段階（２））、レベル０は、第１ノード２１０をポインティングするポインタを有する（図１６の段階（３））。
【００５８】
段階１５ｂで、プレフィックス長さ範囲の上位キー値、例えば、３２（現在のプレフィックス長さ）から開始して第１ノード２２０のハッシュテーブルを検索する。ハッシュテーブルが存在しない場合、前記過程は段階１５ｇに進行する。反対に、段階１５ｃで、ハッシュテーブルが存在する場合、過程は段階１５ｄに進行する。段階１５ｄで、ハッシュテーブル内で目的地アドレスに対応するプレフィックスを検索する。段階１５ｅで、検索されたプレフィックスが目的地アドレスと一致する場合、段階１５ｆで、一致したプレフィックスを最長プレフィックスとしてリターン（ｒｅｔｕｒｎ）する。一方、段階１５ｅで、プレフィックスが一致しない場合、過程は段階１５ｇに進行する。
【００５９】
段階１５ｇで、過程は、同一のプレフィックス範囲において次のハッシュテーブルを検索する。段階１５ｈで、次のハッシュテーブルが存在する場合、前記過程は、１５ｂに進行して前述した過程を繰り返す。段階１５ｈで、次のハッシュテーブルが存在しない場合、過程は段階１５ｉに進行してスキップリストにおいて隣接したノードに移動し、段階１５ｂに戻って前述した過程を当該隣接したノードにおいて繰り返す。以上のように、本発明による新しい検索方式は、従来のルートノードから始まる検索方式とは異なって、自体のハッシュテーブルを有する最長プレフィックス範囲から始まる検索に基づいている。
【００６０】
図１６を再び参照すると、まず、前述したように、スキップリストにおいてノードを探し、所定の目的地アドレスによってルートルックアップがヘッダノードから始まる（図１６の段階（１））。ヘッダノード２１０におけるレベルは、ポインタが最長プレフィックス範囲を有するノードをポインティングするレベル０になるまで減少され（図１６の段階（２））、次に、ヘッダノード２１０のポインタによってポインティングされる第１ノード２２０を横切る（図１６の段階（３））。従って、第１ノード２２０は、プレフィックス長さ３２を含むハッシュテーブルを探すために検索される。該当ハッシュテーブルが検索された場合、目的地アドレスは、一致を発見するために、そのハッシュテーブル内のプレフィックスと比較される。スキップリスト内の各ノードがノードプレフィックス範囲内の各ハッシュテーブルをポインティングするポインタアレイ（ｐｏｉｎｔｅｒ ａｒｒａｙ）を維持するので、長さ３２のプレフィックスを含むハッシュテーブルが存在しない場合、ポインタに対応するプレフィックスはヌル（ｎｕｌｌ）になる。
【００６１】
図１６の例において、第１ノード２２０は、それぞれプレフィックス長さ３０及びプレフィックス長さ２６に対応するハッシュテーブル２２２及び２２４のみを有する。従って、ハッシュテーブルを発見するために第１ノード２２０を検索する時、プレフィックス範囲における各ポインタを検査し、ヌル値を有するポインタはスキップされる。ヌル値を有しないポインタに対応するハッシュテーブルは、元の目的地アドレスと比較されて一致を探す。
【００６２】
従って、ヌル値を有する第１ポインタは、ハッシュテーブル２２２をポインティングし、目的地アドレスは、ハッシュテーブル２２２においてプレフィックスと比較される（図１６の段階４）。ハッシュテーブル２２２において目的地アドレスが検索されなかった場合、非ヌルのポインタを有する次のハッシュテーブル、つまり、プレフィックス長さ２６のハッシュテーブル２２４が、目的地アドレスと比較される（図１６の段階（５））。目的地アドレスが発見されず、第１ノード２２０においてハッシュテーブルがそれ以上存在しない場合、ノード２２０に対してルックアップは失敗になる。
【００６３】
第１ノード２２０においてルックアップが失敗した時、次の最長プレフィックス範囲を有するスキップリストにおいて次のノードを示すポインタを検索する。この例において、次の最長プレフィックス範囲を有するスキップリストにおける次のノードが第２ノード２３０であることを示すポインタがある（図１６の段階（６））。従って、どのハッシュテーブルを有するかノード２３０を検査して、ハッシュテーブルが存在しない場合、スキップリストにおいて次のノードをポインティングするノード２３０のポインタを検索する。
【００６４】
この場合、スキップリストにおいて隣接したノード２４０に移動し（図１６の（７））、図１５に示す段階によってハッシュテーブルをポインティングするポインタを発見する。目的地アドレスは、プレフィックス長さ１５のハッシュテーブル２４２においてプレフィックスと比較される（図１６の段階（８））。この比較によって一致が発生すると、ルートルックアップ動作は成功に終了する（図１６の段階（９））。最後のノード２６０の最後のハッシュテーブルにおいて目的地アドレスが発見できなかった場合、ルックアップは失敗し、対応するアドレスを有するパケットは、デフォルトルートエントリを有するルートに送られる。
【００６５】
以下、スキップリストの構築はプログラム１、２、及び３（数式１、２、３で示す）において表現され、ルートエントリの変化のスキップリストへの反映は、プログラム４、５、６、及び７（数式４、５、６、７で示す）において示し、新しいアルゴリズムの基本部分であるルートルックアップはプログラム８（数式８で示す）において示す。
【００６６】
【数１】
2004517519.tif 000004
【００６７】
【数２】
2004517519.tif 000005
【００６８】
【数３】
2004517519.tif 000006
【００６９】
【数４】
2004517519.tif 000007
【００７０】
【数５】
2004517519.tif 000008
【００７１】
【数６】
2004517519.tif 000009
【００７２】
【数７】
2004517519.tif 000010
【００７３】
【数８】
2004517519.tif 000011
【００７４】
ここで、図７Ａ及び図７Ｂを参照して、本発明によるルーティング方式の効率を説明する。図７Ａ及び図７Ｂは、インターネット上におけるプレフィックス長さ分布の測定値を示すグラフである。図７Ａ及び図７Ｂのグラフによって表現されるデータは、ＩＰＭＡ（Ｉｎｔｅｒｎｅｔ Ｐｅｒｆｏｒｍａｎｃｅ Ｍｅａｓｕｒｅｍｅｎｔ ａｎｄ Ａｎａｌｙｓｉｓ）プロジェクトで最近ＭＡＥ−ＥＡＳＴ ＮＡＰ（Ｎｅｔｗｏｒｋ Ａｃｃｅｓｓ Ｐｏｉｎｔ）において収集されたデータを示す。
【００７５】
ＩＰＭＡプロジェクトで収集された統計データは、ルートルックアップアルゴリズム開発者の研究結果を相互に分析する源泉データとして広く使用される。ＭＡＥ−ＥＡＳＴ ＮＡＰにおけるルータは、最大のルートエントリを含み、主にバックボーン（ｂａｃｋｂｏｎｅ）ルータのモデルとして使用される。ＰＡＩＸ ＮＡＰは、現在のＩＰＭＡプロジェクトで収集された最小のルートエントリを含み、主にエンタープライズ（ｅｎｔｅｒｐｒｉｓｅ）ルータのモデルとして利用される。
【００７６】
図７Ａ及び図７Ｂは、１６〜２８のプレフィックス長さが最も頻繁に参照されることを示す局所性パターン（ｌｏｃａｌｉｔｙ ｐａｔｔｅｒｎ）を示す。従って、このような観測結果は、本発明において提示された変更スキップリストに含まれるノードの数が大きく減少されることを示す。ＩＰＭＡ（ｈｔｔｐ：／／ｎｉｃ．ｍｅｒｉｔ．ｅｄｕ／ｉｐｍａ）における他の興味深い結果は、一日にＢＧＰによって追加されるか、それとも撤回されたルーティングプレフィックスの数が１，８９９，８５１（１９９７年１１月１日現在）に達することである。これは、２５ｐｒｅｆｉｘ−ｕｐｄａｔｅｓ／ｓｅｃを要求するほどに緊迫であり、変更されたルーティングプレフィックスをルーティングテーブル（または、フォワーディングテーブル）に迅速に反映することは検索時間以外に主要要素である。
【００７７】
以下、表２を参照して、本発明によるアルゴリズムと従来のアルゴリズムとの差に関して説明する。通常、アルゴリズムに対する分析は、該当アルゴリズムを処理するために要求される時間または使用するメモリに対する“ｗｏｒｓｔ−ｃａｓｅ ｃｏｍｐｌｅｘｉｔｙ”を“ｂｉｇ−Ｏ ｎｏｔａｔｉｏｎ”を使用して相互に比較する。表２は、本発明による新しいアルゴリズムによって要求される複雑度を示す。ここで、Ｎ個のルートエントリが存在し、各アドレスを表現するためにＷ個のアドレスビットが要求され、ｋはアルゴリズム依存性常数（ａｌｇｏｒｉｔｈｍ−ｄｅｐｅｎｄｅｎｔ ｃｏｎｓｔａｎｔ）である。
【００７８】
【表２】
2004517519.tif 000012
【００７９】
表２において、ベース（ｂａｓｅ）１０の他の対数（ｌｏｇａｒｉｔｈｍ）との混同を防止するために、ベース２の対数をｌｇに表現する。
【００８０】
ＩＰｖ４において、Ｗは３２に該当し、ＩＰｖ６の場合は、１２８に該当する。前記ＭＡＥ−ＥＡＳＴ及びＰＡＩＸ ＮＡＰにおいて、ルートエントリの数Ｎは、それぞれ約５０，０００及び６０，０００である。この場合、プレフィックス範囲が８であると、‘ｋ−ａｒｙ ｈａｓｈｅｄ ｎｏｄｅ’を有するスキップリストにおけるｋは４である。ＩＰｖ６の場合は１６である。
【００８１】
本発明によるアルゴリズムは、既存の検索ツリー（ｓｅａｒｃｈ ｔｒｅｅ）及びトライ（Ｐａｔｒｉｃｉａ ｔｒｉｅ またはＬＣ−ｔｒｉｅ）に比べて、テーブルの構築、追加及び削除動作の面で優れている。さらに、本発明による新しいアルゴリズムは、“Ｂｉｎａｒｙ ｈａｓｈ ｔａｂｌｅ ｓｅａｒｃｈ”（Ｗａｌｄｖｏｇｅｌ， Ｍ．， Ｖａｒｇｈｅｓｅ， Ｇ．， Ｔｕｒｎｅｒ， Ｊ． ａｎｄ Ｐｌａｔｔｎｅｒ， Ｂ．， Ｓｃａｌａｂｌｅ Ｈｉｇｈ Ｓｐｅｅｄ ＩＰ Ｒｏｕｔｉｎｇ Ｌｏｏｋｕｐｓ， Ｉｎ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＡＣＭ ＳＩＧＣＯＭＭ ’９７， Ｃａｎｎｅｓ， Ｆｒａｎｃｅ， ｐａｇｅｓ ２５−３７， １９９７）及び“Ｃｏｍｐｌｅｔｅ ｐｒｅｆｉｘ ｔｒｉｅ”（Ｔｚｅｎｇ， Ｈ． ａｎｄ Ｐｒｙｚｙｇｉｅｎｄａ， Ｔ．， Ｏｎ Ｆａｓｔ Ａｄｄｒｅｓｓ−Ｌｏｏｋｕｐ Ａｌｇｏｒｉｔｈｍｓ， ＩＥＥＥ Ｊｏｕｒｎａｌ ｏｎ Ｓｅｌｅｃｔｅｄ Ａｒｅａｓ ｉｎ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ， Ｖｏｌ． １７， Ｎｏ． ６， ｐａｇｅｓ １０６７−１０８２， Ｊｕｎｅ， １９９９）に比べて、構築時間及び追加または削除動作において優れている。さらに、表２において、新しいアルゴリズムが純粋のスキップリスト（ｐｕｒｅ ｓｋｉｐ ｌｉｓｔ）より優れていることを示す複雑度の結果を理解できる。
【００８２】
前述の如く、本発明の詳細な説明では具体的な実施形態を参照して詳細に説明してきたが、本発明の範囲は前記実施形態によって限られるべきではなく、本発明の範囲内で様々な変形が可能であるということは、当該技術分野における通常の知識を持つ者には明らかである。
【００８３】
【発明の効果】
前述してきたように、本発明によるアルゴリズムは、無作為抽出アルゴリズムを構成するスキップリスト及びハッシュテーブルを利用して、インターネットプロトコルアドレスのプレフィックス範囲によってノードを生成する。さらに、本発明は、各ノードで設定されたプレフィックス長さによるハッシュテーブルの形態でルートエントリが貯蔵されるスキップリストを利用するルーティング方式を提供することによって、経路検索時間を最小化し、関連テーブルを効率的に管理する。そうすることによって、高速経路検索が可能になる。このアルゴリズムは、将来使用されるＩＰｖ６に適用されることもできる。
【００８４】
さらに、本発明は、既存のアルゴリズムに比べて、全ての面で、特に、ルーティングテーブルまたはフォワーディングテーブルの構築、追加、及び削除動作の面で優れていることが複雑度分析結果から分かる。さらに、フォワーディングエンジンにおけるフォワーディングテーブルがルーティングプロセッサにおけるルーティングテーブルと依然として分離される分散形態のルータ構造または並列形態のルータ構造などの最近の構造に対する傾向において、全てのルートエントリでなく前記経路に沿って更新されたルートのみをルータに移すことによって、メモリ帯域幅またはシステムバスコンテンション（ｃｏｎｔｅｎｔｉｏｎ）が減少される。さらに、経路検索時間の短縮及び全てのルーティング関連テーブルを通した前記一致するルーティング情報の管理は、ＱｏＳ（Ｑｕａｌｉｔｙ ｏｆ ｓｅｒｖｉｃｅ）、マルチキャスティング、ＩＰＳｅｃなどの他の因子を通して性能向上に寄与する。
【図面の簡単な説明】
【図１】
本発明が適用できる分散形態のルータ構造を示す概略図である。
【図２】
本発明が適用できる並列形態のルータ構造を示す概略図である。
【図３】
本発明が適用できる伝送エンジンの構造を示す概略図である。
【図４】
ルーティングプロセッサの構造を示す概略図である。
【図５】
本発明の実施形態によるＬＰＭ（Ｌｏｎｇｅｓｔ Ｐｒｅｆｉｘ Ｍａｔｃｈｉｎｇ）アルゴリズムを説明するための図である。
【図６】
本発明の実施形態によるスキップリストの構造を示す図である。
【図７】
Ａは、インターネット上におけるプレフィックス長さ分布の測定値を示すグラフである。Ｂは、インターネット上におけるプレフィックス長さ分布の測定値を示すグラフである。
【図８】
本発明の実施形態によるヘッダノードの構造を示す図である。
【図９】
本発明の実施形態によるスキップリスト構築作業を説明するための図である。
【図１０】
Ａは、本発明の実施形態によってプレフィックス長さによるルーティングテーブルを構築する作業を説明するための図である。Ｂは、本発明の実施形態によってプレフィックス長さによるルーティングテーブルを構築する作業を説明するための図である。
【図１１】
本発明の実施形態によるルーティングテーブルの生成過程を示すフローチャートである。
【図１２】
本発明の実施形態によるルーティングテーブルの更新過程を示すフローチャートである。
【図１３】
本発明の実施形態によるルート検索及び更新作業を説明するための図である。
【図１４】
本発明の実施形態によるルート検索及び更新作業を説明するための図である。
【図１５】
本発明の実施形態によるルートルックアップ過程を示すフローチャートである。
【図１６】
本発明の実施形態による全体ルックアップ過程を説明するためのスキップリスト構造を示す図である。
【図１】
2004517519.tif 000013
【図２】
2004517519.tif 000014
【図３】
2004517519.tif 000015
【図４】
2004517519.tif 000016
【図５】
2004517519.tif 000017
【図６】
2004517519.tif 000018
【図７】
2004517519.tif 000019
【図８】
2004517519.tif 000020
【図９】
2004517519.tif 000021
【図１０】
2004517519.tif 000022
【図１１】
2004517519.tif 000023
【図１２】
2004517519.tif 000024
【図１３】
2004517519.tif 000025
【図１４】
2004517519.tif 000026
【図１５】
2004517519.tif 000027
【図１６】
2004517519.tif 000028
【国際公開パンフレット】
2004517519.tif 000029
2004517519.tif 000030
2004517519.tif 000031
2004517519.tif 000032
2004517519.tif 000033
2004517519.tif 000034
2004517519.tif 000035
2004517519.tif 000036
2004517519.tif 000037
2004517519.tif 000038
2004517519.tif 000039
2004517519.tif 000040
2004517519.tif 000041
2004517519.tif 000042
2004517519.tif 000043
2004517519.tif 000044
2004517519.tif 000045
2004517519.tif 000046
2004517519.tif 000047
2004517519.tif 000048
2004517519.tif 000049
2004517519.tif 000050
2004517519.tif 000051
2004517519.tif 000052
2004517519.tif 000053
2004517519.tif 000054
2004517519.tif 000055
2004517519.tif 000056
2004517519.tif 000057
2004517519.tif 000058
2004517519.tif 000059
2004517519.tif 000060
2004517519.tif 000061
2004517519.tif 000062
2004517519.tif 000063
2004517519.tif 000064
2004517519.tif 000065
2004517519.tif 000066
2004517519.tif 000067
2004517519.tif 000068
2004517519.tif 000069
2004517519.tif 000070
【国際調査報告】
2004517519.tif 000071
2004517519.tif 000072