(57)【特許請求の範囲】
【請求項１】
スキップリストを利用してインターネットプロトコル（ＩＰ）アドレス検索のためのルーティング／フォワーディングテーブルを構築する方法において、
前記インターネットプロトコルアドレスのプレフィックス長さ範囲を予め設定された方式によって分割する過程と、
前記プレフィックス長さ範囲の分割されたクラスターの個数に基づいた最大レベルを有し、前記スキップリスト内の全てのノードをポインティングするためのヘッダノードを生成する過程と、
それぞれ前記分割されたプレフィックス長さ範囲をキーとして有し、前記分割されたクラスターの個数の分だけサブノードを生成する過程と、
からなることを特徴とする方法。
【請求項２】
それぞれのサブノードにおいて、前記プレフィックス長さによって提供されるハッシュテーブルに、対応するプレフィックス長さ範囲内のそれぞれのプレフィックス長さに対応するルートエントリを貯蔵する過程をさらに含むことを特徴とする請求項１記載の方法。
【請求項３】
前記ルートエントリは、３２ビットまたは１２８ビットであることを特徴とする請求項２記載の方法。
【請求項４】
前記サブノードの前記ヘッダノードのレベルは、無作為に設定されることを特徴とする請求項１記載の方法。
【請求項５】
前記プレフィックス長さ範囲は、固定的にまたは可変的に分割されることを特徴とする請求項１記載の方法。
【請求項６】
前記プレフィックス長さ範囲は、前記サブノードを通して全てのプレフィックス長さ範囲がカバーされるように分割されることを特徴とする請求項１記載の方法。
【請求項７】
前記ルーティング／フォワーディングテーブルは、それぞれルーティングプロセッサ及びフォワーディングエンジンに備わることを特徴とする請求項１記載の方法。
【請求項８】
スキップリストを利用するインターネットプロトコルルーティング／フォワーディングテーブルの生成方法において、
前記スキップリスト内の全てのノードを取り扱うためにそれぞれのノードをポインティングするヘッダノードを生成する過程と、
予め設定された方式によって分割されたインターネットプロトコルアドレスのプレフィックス範囲をキーとして有する複数のサブノードを生成する過程と、
それぞれのサブノードにおいて、対応するプレフィックス長さ範囲におけるプレフィックス長さ別のルートエントリを貯蔵するために、プレフィックス長さ別のハッシュテーブルを生成する過程と、
からなることを特徴とする方法。
【請求項９】
前記ハッシュテーブルに対応するプレフィックスに一致するルートエントリを貯蔵する過程をさらに含むことを特徴とする請求項８記載の方法。
【請求項１０】
前記サブノードの前記ヘッダノードのレベルは、無作為に設定されることを特徴とする請求項８記載の方法。
【請求項１１】
前記プレフィックス長さ範囲は、固定的にまたは可変的に分割されることを特徴とする請求項８記載の方法。
【請求項１２】
前記プレフィックス長さ範囲は、複数の前記サブノードを通して全てのプレフィックス長さ範囲がカバーされるように分割されることを特徴とする請求項８記載の方法。
【請求項１３】
前記ルートエントリは、３２ビットまたは１２８ビットであることを特徴とする請求項８記載の方法。
【請求項１４】
前記ヘッダノードは、＋∞キー値を有し、０から最大レベル−１までのインデックスが付けられる伝送ポインタを有することを特徴とする請求項８記載の方法。
【請求項１５】
前記ルーティング／フォワーディングテーブルは、それぞれルーティングプロセッサ及びフォワーディングエンジンに備わることを特徴とする請求項８記載の方法。
【請求項１６】
インターネットプロトコルアドレスのプレフィックス範囲の割り当てによって生成されたそれぞれのノードで設定されたプレフィックス長さによるハッシュテーブルの形態でルートエントリが貯蔵されるスキップリストを利用したルーティング／フォワーディングテーブルの検索方法において、
検索されるルートのプレフィックス長さに対応するプレフィックス範囲が設定されたノードを見つける過程と、
前記見つけたノードにおいて前記検索されるルートと同一のプレフィックス長さを有するハッシュテーブルを見つける過程と、
前記見つけたハッシュテーブルから前記検索ルートを発見する過程と、
からなることを特徴とする方法。
【請求項１７】
前記ノードを見つける過程は、
前記スキップリストのヘッダノードの最大レベルからポインティングするノードを見つける段階と、
前記見つけたノードのプレフィックス長さ範囲と前記検索ルートのプレフィックス長さを比較する段階と、
前記見つけたノードのプレフィックス長さ範囲に前記検索ルートのプレフィックス長さが該当しない場合、前記ヘッダノードの次のレベルでポインティングされるノードを見つける段階と、
を含むことを特徴とする請求項１６記載の方法。
【請求項１８】
前記スキップリストは、ヘッダノード、及びプレフィックス長さの減少される順で予め設定される範囲のキーを有し、それぞれのプレフィックス長さに関連したハッシュテーブルにそれぞれのプレフィックス長さに対応するルートエントリを貯蔵する複数のノードを含むことを特徴とする請求項１６記載の方法。
【請求項１９】
前記ルーティング／フォワーディングテーブルは、それぞれルーティングプロセッサ及びフォワーディングエンジンに備わることを特徴とする請求項１６記載の方法。
【請求項２０】
前記ルートエントリは、３２ビットまたは１２８ビットであることを特徴とする請求項１６記載の方法。
【請求項２１】
インターネットプロトコルアドレスのプレフィックス長さ範囲によって生成されたそれぞれのノードで設定されたプレフィックス長さによるハッシュテーブルの形態でルートエントリが貯蔵されるスキップリストを利用したルーティング／フォワーディングテーブルの更新方法において、
更新されるルートのプレフィックス長さに対応するプレフィックス範囲が設定されたノードを見つける過程と、
前記見つけたノードで前記更新されるルートと同一のプレフィックス長さを有するハッシュテーブルを検索する過程と、
前記ハッシュテーブルを発見した時、前記ハッシュテーブルにおいて該当ルートを更新する過程と、
からなることを特徴とする方法。
【請求項２２】
前記ルートを見つける過程は、
前記スキップリストのヘッダノードの最大レベルからポインティングするノードを見つける段階と、
前記見つけたノードのプレフィックス長さ範囲と前記更新されるルートのプレフィックス長さを比較する段階と、
前記見つけたノードのプレフィックス長さ範囲に前記更新されるルートのプレフィックス長さが該当しない場合、前記ヘッダノードの次のレベルでポインティングされるノードを見つける段階と、を含むことを特徴とする請求項２１記載の方法。
【請求項２３】
前記ルート更新過程は、更新されるルートを追加、変更、または削除する過程であることを特徴とする請求項２１記載の方法。
【請求項２４】
前記ハッシュテーブルが発見されない場合、前記更新されるルートと同一のプレフィックスを有するハッシュテーブルを生成する過程と、
前記生成されたハッシュテーブルに前記更新されるルートを挿入する過程と、をさらに含むことを特徴とする請求項２１記載の方法。
【請求項２５】
前記スキップリストは、ヘッダノード、及びプレフィックス長さの減少される順で予め設定される範囲のキーを有し、それぞれのプレフィックス長さと関連したハッシュテーブルにそれぞれのプレフィックス長さに該当するルートエントリが貯蔵される複数のノードを含むことを特徴とする請求項２１記載の方法。
【請求項２６】
前記ルーティング／フォワーディングテーブルは、それぞれルーティングプロセッサ及びフォワーディングエンジンに備わることを特徴とする請求項２１記載の方法。
【請求項２７】
前記ルートエントリは、３２ビットまたは１２８ビットであることを特徴とする請求項２１記載の方法。
【請求項２８】
インターネットプロトコル（ＩＰ）アドレスのプレフィックス範囲の割り当てによって生成されるそれぞれのノードで予め設定されたプレフィックス長さによるハッシュテーブルの形態でルートエントリが貯蔵されるスキップリストを利用するルーティング／フォワーディングテーブルのルートルックアップ方法において、
前記スキップリストの第１ノードから始まって隣接したノードを見つける過程と、
該当ノードで目的地アドレスとそれぞれのハッシュテーブルを比較する過程と、
前記ハッシュテーブルが前記目的地アドレスを含む場合、一致するプレフィックスを最長プレフィックスとみなす過程と、
からなることを特徴とする方法。
【請求項２９】
前記ハッシュテーブルが前記目的地ＩＰアドレスを含まない場合、前記スキップリストで次のノードを見つける過程をさらに含むことを特徴とする請求項２８記載の方法。
【請求項３０】
前記スキップリストは、ヘッダノード、及びプレフィックス長さの減少される順で予め設定される範囲のキーを有し、それぞれのプレフィックス長さに対応するハッシュテーブルにそれぞれのプレフィックス長さに対応するルートエントリを貯蔵する複数のノードを含むことを特徴とする請求項２８記載の方法。
【請求項３１】
前記比較過程は、
前記目的地アドレスと前記該当ノードのハッシュテーブルのうち最長プレフィックス長さを有するハッシュテーブルを比較する段階と、
前記最長プレフィックス長さを有するハッシュテーブルで目的地アドレスを見つけなかった場合、次の最長プレフィックス長さを有するハッシュテーブルと前記目的地アドレスを比較する段階と、を含むことを特徴とする請求項２８記載の方法。
【請求項３２】
前記ルーティング／フォワーディングテーブルは、それぞれルーティングプロセッサ及びフォワーディングエンジンに備わることを特徴とする請求項２８記載の方法。
【請求項３３】
前記ルートエントリは、３２ビットまたは１２８ビットであることを特徴とする請求項２８記載の方法。
【請求項３４】
高速インターネットプロトコルルータにおいて、
パケットが入出力されるフォワーディングエンジンがそれぞれ装着された複数のラインカードモジュールと、
前記パケットを内部ポート間にスイッチングするスイッチファブリックと、
ヘッダノード、及びインターネットプロトコルアドレスのプレフィックス範囲によってそれぞれ生成され、キーとして前記プレフィックス長さ範囲を有し、設定されたプレフィックス長さによるハッシュテーブルの形態でルートエントリを貯蔵する複数のノードを有するスキップリスト構造を有するルーティングテーブルを含むルーティングプロセッサと、
から構成されることを特徴とするルータ。
【請求項３５】
高速インターネットプロトコルルータにおいて、
ヘッダノード、及びインターネットプロトコルアドレスのプレフィックス範囲によってそれぞれ生成され、キーとして前記プレフィックス長さ範囲を有し、設定されたプレフィックス長さによるハッシュテーブルの形態でルートエントリを貯蔵する複数のノードを有するスキップリスト構造を有するフォワーディングテーブルを備えるフォワーディングエンジンが装着された複数のラインカードモジュールと、
前記パケットを内部ポート間にスイッチングするスイッチファブリックと、
ルーティング動作を全般に制御するルーティングプロセッサと、
から構成されることを特徴とするルータ。
【請求項３６】
前記ルーティングプロセッサは、ヘッダノード、及びインターネットプロトコルアドレスのプレフィックス範囲によってそれぞれ生成され、前記プレフィックス長さ範囲をキーとして有し、設定されたプレフィックス長さによるハッシュテーブルの形態でルートエントリを貯蔵する複数のノードから構成されるスキップリスト構造を有するルーティングテーブルを備えることを特徴とする請求項３５記載のルータ。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、インターネット上においてパケットを目的地に伝送するためのルーティング(routing)技術に関し、特に、高速にインターネットプロトコル(Internet Protocol: 以下、ＩＰと称する)ルートルックアップ(route lookup)を遂行し、ルーティング(または、フォワーディング)テーブルを管理する装置及び方法に関する。
【０００２】
【従来の技術】
現在、インターネット利用者の急増、提供されるサービスの多様化、及びＶｏＩＰ(Voice over Internet Protocol)などの利用分野の拡大によって、インターネットのトラヒックが急激に増加している。ギガ(Giga)またはテラ(Tera)級の高速ルータ(router)において、遅延なしで目的経路を発見することによってパケットを次のホップインターフェース(hop interface)に伝送することが技術的な懸案になっている。前記ルータの物理的入力インターフェースを通して伝達されるパケットの目的地経路を発見するために、最短経路のルーティング(または、フォワーディング)テーブルの維持及び検索時間の短縮が要求される。
【０００３】
従来のルータにおいて、パケットを処理し、該パケットの目的地を検索するために要する時間が伝送路を通して到達されるパケットの伝送時間に比べて高速であるので、サブネットワークまたは他のネットワークを連結する接続ノードとしてのルータの機能の遂行には問題がなかった。最近、ＰＯＳ ＯＣ−１９２(10Gbps)またはＩＰ ｏｖｅｒ ＤＷＤＭ(Dense Wavelength Division Multiplexing)などの光ネットワークインターフェースの帯域幅が増加し、それとともに、パケットの伝送時間がルータにおける処理時間より相対的に短くなり、さらに、この帯域幅の増加は、ルータが高速インターネット上でボトルネック(bottleneck)の主要原因を提供するという非難を招いた。前記のような技術としては、Keshav, S. and Sharma, R., Issues and Trends in Router Design, IEEE Communications Magazine, pages 144-１５1,May,1998、Kumar, V. and Lakshman, T. and Stiliadis, D., Beyond Best Effort: Router Architectures for the Differentiated Services of Tomorrow's Internet, IEEE Communications Magazine, pages １５2-164,May,1998、Chan, H., Alnuweiri, H. and Leung, V., A Framework for Optimizing the Cost and Performance of Next-Generation IP Routers, IEEE Journal of Selected Areas in Communications, Vol. 17, No.6, pages 1013-1029, June 1999、Partridge, C. et al., A 50-Gb/s IP Router, IEEE/ACM Trans. on Networking, vol. 6, no.3, pages 237-248, 1998、及びMetz, C., IP Routers: New Tool for Gigabit Networking, IEEE Internet Computing, pages 14-18, Nov.-Dec.,1998.に開示されている。
【０００４】
１９９０年代初めに、インターネットの技術標準を管理するＩＥＴＦ(Internet Engineering Task Force)のワーキンググループ(working group)は、ＩＰｖ４(IP version 4)におけるＩＰアドレスを効率的に使用するＣＩＤＲ(Classless Inter-Domain Routing)という新しいＩＰアドレシング方式を導入した。これは、RFC(Request for Comments : Network Working Group) 1518, An Architecture for IP Address Allocation with CIDR, Sept. 1993及びRFC 1517, Applicability Statement for the Implementation of Classless Inter-Domain Routing (CIDR), Sept. 1993.に開示されている。
【０００５】
この場合、多様なプレフィックス(prefix)長さを有するパケットにおいて対応するプレフィックスを把握し、最長プレフィックス(longest prefix)に一致(matching)するＩＰアドレスを発見するために、一般的に、トライ(trie)またはパトリシア(Patricia: Practical Algorithm to Retrieve Information Coded as Alphanumeric)トライデータ構造に基づいたＬＰＭ(Longest Prefix Matching)アルゴリズムが使用されてきた。これは、Doeringer, W., Karjoth, G. and Nassehi, M., Routing on Longest-Matching Prefixes, IEEE/ACM Trans. on Networking, vol.4, no.1, pages 86-97, Feb., 1996.に開示されている。
【０００６】
以下、表１を参照して前記ＬＭＰアルゴリズムを詳細に説明する。表１は、ルーティング(または、フォワーディング)テーブルに含まれるルーティングエントリの簡単な例を示す。ＩＰｖ４の場合に、実は前記プレフィックスが３２を超過することはできないが、表１における星印は、‘０’または‘１’からなる任意の数を詰めることを可能にする。例えば、‘０＊’は、‘０１＊’、‘０１１＊’、または‘０１０＊’を含み、残りのビットストリング(bit string)がどういうものなのかは問題にならない。
【表１】
0003790217.tif 000002
【０００７】
ルーティングエントリまたはルートは、{＜network prefix＞,＜host number＞}からなるＩＰアドレスによって表現される。目的地ＩＰアドレスが‘１００１０１０１０００…０’である場合、この目的地ＩＰアドレスの１番目のビットは、前記ルーティングテーブルに含まれるネットワークプレフィックス(以下、簡単にプレフィックスと称する)と比較される。従って、‘０＊’、‘０１０１０＊’、‘０１０１０１＊’、及び‘０１０１０１１＊’などのプレフィックスは、自分の１番目のビットが‘０’から始まるので、除かれる。所定の目的地アドレスを残りのプレフィックスと比較する場合、プレフィックス‘１１＊’、‘１１１０＊’、及び‘１００１０１０１０１＊’は、前記目的地アドレスと２番目のビットまたは１０番目のビットで一致しないので、除かれる。次に、残りの対象プレフィックス(つまり、‘１＊’、‘１０＊’、及び‘１００１０１０１０＊’)のうち、‘１００１０１０１０＊’が前記最長プレフィックス(または、most specific)一致ルートとして選択され、当該目的地ＩＰアドレスを有するＩＰパケットは、インターフェース‘１０’を通して隣接ルータに伝送される。
【０００８】
一方、最近発表された経路検索(routing lookup)アルゴリズムは、メモリアクセス時間を短縮するために、使用できるプロセッサ(ルーティングプロセッサまたはフォワーディングエンジン)内のキャッシュメモリ(cache memory)に貯蔵される。このルーティングテーブルに基づいた経路検索アルゴリズムは、効率的な検索を支援するが、ルーティングテーブルまたはフォーワーディングテーブルを変更することはできない。従って、この経路検索アルゴリズムは、変更されたルートの反映による遅延時間を生じさせる可能性がある。
【０００９】
さらに、ルーティングプロセッサにおけるルーティングテーブルは、ＤＭＡ(Direct Memory Access)カード、ＩＰＣ(Inter-Processor Communication)カード、またはスイッチファブリックを通してコピーされて、フォワーディングエンジンにおけるフォワーディングテーブルに適用される。この時、変更されたルートのみを追加及び削除するのではなく、新しいフォワーディングテーブルを構築する必要がある。これは、追加的な時間遅延を生じさせ、さらに、ルータからのメモリアクセス要求によるメモリ帯域幅使用の増加によって、ルータの内部メモリまたはシステムバス(system bus)におけるボトルネックを生じさせる可能性がある。
【００１０】
さらに、一部のアルゴリズムにおいて、最初のルーティングテーブル(または、フォワーディングテーブル)は、ルータの現在のリンク状態を示す“リンク情報(link reachability information)”を使用して構成されるべきである。従って、リンク情報を順にルーティングテーブルに挿入するためには、前もってプレフィックス長さ別に全てのルートを分類(sorting)する追加的な作業が必要である。このようなアルゴリズムの例としては、Degermark, M., Brodnik, A., Carlsson, S. and Pink, S., Small Forwarding Tables for Fast Routing Lookups, In Proceedings of ACM SIGCOMM '97, pages 3-14, Cannes, France, 1997、Srinivasan, V. and Varghese, G., Faster IP Lookups using Controlled Prefix Expansion, In Proceedings of ACM Sigmetrics '98 Conf., pages 1-11, 1998、Lampson, B., Srinivasan, V. and Varghese, G., IP Lookups using Multiway and Multicolumn Search, In IEEE Infocom, pages 1248-1256, 1998、Tzeng, H. and Pryzygienda, T., On Fast Address-Lookup Algorithms, IEEE Journal on Selected Areas in Communications, Vol. 17, No. 6, pages 1067-1082, June, 1999、Waldvogel, M., Varghese, G., Turner, J. and Plattner, B., Scalable High Speed IP Routing Lookups, In Proceedings of ACM SIGCOMM '97, Cannes, France, pages 25-37, 1997、及びWaldvogel, M., Varghese, G., Turner, J. and Plattner, B., Scalable Best Matching Prefix Lookups, In Proceedings of PODC '98, Puerto Vallarta, page, 1998.がある。
【００１１】
ルーティングテーブルにおいて代表的に使用されるデータ構造である“ｒａｄｉｘ ｔｒｅｅ”または“Ｐａｔｒｉｃｉａ ｔｒｉｅ”は、パケット経路を探すために要求されるメモリアクセスの数が増加するだけでなく、該当ルータの隣接ルータからルートを設定または削除することによって発生するルート変更を反映するためには、かなりの更新時間が要求される。Degermark, M., Brodnik, A., Carlsson, S. and Pink, S., Small Forwarding Tables for Fast Routing Lookups, In Proceedings of ACM SIGCOMM '97, pages 3-14, Cannes, France, 1997には、フォーワーディングエンジンにおいてキャッシュに貯蔵できるコンパクト(compact)フォーワーディングテーブルが提示されているが、該当テーブルのルート変更を反映することは大変である。Srinivasan, V. and Varghese, G., Faster IP Lookups using Controlled Prefix Expansion, In Proceedings of ACM Sigmetrics '98 Conf., pages 1-11, 1998によって提示された“controlled prefix expansion”方式(U.S. Patent No. 6,011,795, issued to George Varghese and Srinivasan and entitled Method and Apparatus for Fast Hierarchical Address Lookup Using Controlled Expansion of Prefixes)及びTzeng, H. and Pryzygienda, T., On Fast Address-Lookup Algorithms, IEEE Journal on Selected Areas in Communications, Vol. 17, No. 6, pages 1067-1082, June, 1999によって提示された高速(fast)アドレス検索アルゴリズムも“multi-resolution trie”に基づいているが、そのデータ構造は前記トライ(trie)に基づいているので、ルートの追加及び削除が容易でない。これに関連して、米国特許番号第６,０６１,７１２(Method for IP Routing Table Look-up)及び米国特許番号第６,０６７,５７４(High Speed Routing Using Compressed Tree Process)が、Hong-Yi Tzengに許与されている。ハッシュテーブルを使用してトライ構造を２進検索ツリー(binary tree)にマッピングすることによる“rope search”アルゴリズム(Waldvogel, M., Varghese, G., Turner, J. and Plattner, B., Scalable High Speed IP Routing Lookups, In Proceedings of ACM SIGCOMM '97, Cannes, France, pages 25-37, 1997及びWaldvogel, M., Varghese, G., Turner, J. and Plattner, B., Scalable Best Matching Prefix Lookups, In Proceedings of PODC '98, Puerto Vallarta, page, 1998)及び(Tzeng, H. and Pryzygienda, T., On Fast Address-Lookup Algorithms, IEEE Journal on Selected Areas in Communications, Vol. 17, No. 6, pages 1067-1082, June, 1999)による“multi-resolution trie”に基づいたコンプリート(complete)プレフィックストライは、それぞれのデータ構造が前記トライに基づいているので、変更されたルートエントリの更新によって非効率的になる傾向がある。これに関連して、米国特許番号第６,０１８,５２４(Scalable High Speed IP Routing Lookups)がJonathan Turner、George Varghese、及びMarcel Waldvogelに許与されている。
【００１２】
これら以外にも、前記トライの他の変形が提示されている。例えば、検索時間を減少させるために２つのトライ(trie)を連結する“two-trie”方式(Kijkanjanarat, T. and Chao, H., Fast IP Lookups Using a Two-trie Data Structure, In Proceedings of Globecom'99, 1999)及びトライのレベル長さを短縮させるための“ＬＣ-ｔｒｉｅｓ”(Nillson, S. and Karlsoson, G., IP-Addresses Lookup Using LC-Tries, IEEE Journal on Selected Areas in Communications, Vol.17, No. 16, pages 1083-1092, 1999)、及び“ＤＰ-ｔｒｉｅｓ”(Doeringer, W., Karjoth, G. and Nassehi, M., Routing on Longest-Matching Prefixes, IEEE/ACM Trans. on Networking, vol.4, no.1, pages 86-97, Feb., 1996)も提案されている。しかしながら、ルーティングテーブル(または、フォワーディングテーブル)のルート変更の反映は依然として難しい。
【００１３】
さらに、検索時間を低減するために前述したような方式が提案されたが、ルート更新に関する問題は依然として存在する。検索時間を低減するための方法として、ハードウェア的に処理するための方法も提案されている。Gupta, P., Lin, S. and McKeown, N., Routing Lookups in Hardware at Memory Access Speeds, In Proceedings of IEEE INFOCOM '98 Conf., pages 1240-1247, 1998に開示したように、大容量のメモリの使用による方法が提示された。この方式は、ソフトウェア的な方法に比べて検索時間は短縮されるが、ＩＰｖ６(Internet Protocol version 6)に遷移する時は、メモリの容量またはコストなどの問題が依然として発生する。McAuley, A. and Francis, P., Fast Routing Table Lookup Using CAMs, In Proceedings of IEEE INFOCOM '93, Vol.3, pages 1382-1391, 1993によってＣＡＭ(Content Addressable Memory)を使用する方法が提案されたが、ＣＡＭの高い値段のため、現在は考慮していない。Huang, N. and Zhao, S., A Novel IP-Routing Lookup Scheme and Hardware Architecture for Multigigabit Switching Routers, IEEE Journal on Selected Areas in Communications, Vol. 17, No. 6, pages 1093-1104, June, 1999は、メモリアクセスを低減するためにパイプライン(pipeline)式のメモリを使用する“indirect lookup”アルゴリズムを提示しているが、これもＩＰｖ６への適用は困難である。
【００１４】
【発明が解決しようとする課題】
従って、本発明の目的は、無作為抽出(randomized)アルゴリズムを使用してメモリアクセス時間を最小にすることができることによって、費用効率の高いメモリ使用を可能にする高速ＩＰルートルックアップ遂行及びルーティング／フォワーディングテーブル管理のための方法を提供することにある。
【００１５】
本発明の他の目的は、ルートの追加及び削除に対する変更及び管理が容易にできる高速ＩＰルートルックアップ遂行及びルーティング／フォワーディングテーブル管理のための方法を提供することにある。
【００１６】
本発明のまた他の目的は、テーブルを構成する時、入力しようとするルートのプレフィックス長さによって関連ルートを分類(sorting)せずに、ルーティングテーブル／フォワーディングテーブルを効率的に構築することのできる高速ＩＰルータルックアップ遂行及びルーティング／フォワーディングテーブル管理のための方法を提供することにある。
【００１７】
【課題を解決するための手段】
このような目的を達成するための本発明の第１特徴によると、本発明は、所定の最大の値のキーを有するヘッダノード、及び減少される順で予め設定される固定的な(可変的な)範囲のキーを有し、それぞれのプレフィックス長さに関連したハッシュテーブルにそれぞれのプレフィックス長さに対応するルートエントリを貯蔵する複数のノードを含むスキップリストを使用して、キーとしてプレフィックス長さ範囲を有するＩＰアドレス検索方法を提供する。
【００１８】
本発明の第２特徴によると、本発明は、前記スキップリスト内の全てのノードを取り扱うために最大レベルを有するヘッダノードを生成する過程と、前記スキップリストにプレフィックス範囲をキーとして有する複数のサブノードを挿入する過程と、それぞれのサブノードにおいて、プレフィックス範囲に対応する各ノードで与えられたルートエントリを貯蔵するためのハッシュテーブルを生成する過程と、からなるスキップリストを利用するＩＰルーティングテーブル生成方法を提供する。
【００１９】
本発明の第３特徴によると、本発明は、ＩＰアドレスのプレフィックス長さ範囲によって生成されたそれぞれのノードで設定されたプレフィックス長さによるハッシュテーブルの形態でルートエントリが貯蔵されるスキップリストを利用したルーティング／フォワーディングテーブルの更新方法を提供する。この方法は、更新されるルートのプレフィックス長さに対応するプレフィックス範囲が設定されたノードを見つける過程と、前記見つけたノードで前記更新されるルートと同一のプレフィックス長さを有するハッシュテーブルを検索する過程と、前記ハッシュテーブルを発見した時、前記ハッシュテーブルにおいて該当ルートを更新する過程と、からなる。
【００２０】
本発明の第４特徴によると、本発明は、ＩＰアドレスのプレフィックス範囲の割り当てによって生成されるそれぞれのノードで予め設定されたプレフィックス長さによるハッシュテーブルの形態でルートエントリが貯蔵されるスキップリストを利用するルーティング／フォワーディングテーブルのルートルックアップ方法を提供する。この方法は、前記スキップリストの第１ノードから始まって隣接したノードを見つける過程と、該当ノードで目的地アドレスとそれぞれのハッシュテーブルを比較する過程と、前記ハッシュテーブルが前記目的地アドレスを含む場合、一致するプレフィックスを最長プレフィックスとみなす過程と、からなる。
【００２１】
【発明の実施の形態】
以下、本発明に従う好適な実施形態について添付図を参照しつつ詳細に説明する。下記の説明において、本発明の要旨のみを明確にする目的で、関連した公知機能または構成に関する具体的な説明は省略する。
【００２２】
まず、本発明が適用できるルータ及びルーティング方式に関して説明する。Chan et al. (A Framework for Optimizing the Cost and Performance of Next-Generation IP Routers, IEEE Journal of Selected Areas in Communications, Vol. 17, No.6, pages 1013-1029, June 1999)は、高速ルータ構造の主要傾向である分散構造及び並列構造に分類され、この分類は、フォワーディングエンジンの位置によって区分される。高速バックボーン(backbone)ルータは、従来の集中構造より分散構造を取る傾向である。
【００２３】
図１は、本発明が適用できる分散構造を有するルータを示す図である。図１を参照すると、ルータは、パケットが入力及び出力されるフォワーディングエンジン(Forwarding Engine: ＦＥ)が装着されたラインカードモジュール(line card module)１１０、初期ルーティングテーブル(ＲＴ)の構築及び該ルーティングテーブルの管理を遂行するルーティングプロセッサ(routing processor)１２０、及びパケットがルータ内において特定のポート(port)にスイッチングされる時に使用されるスイッチファブリック(switch fabric)１３０から構成される。
【００２４】
ルーティングプロセッサ１２０は、最近変更されたルートを反映することによって更新されたルーティングテーブル(ＲＴ)を備える。ルーティングテーブル(ＲＴ)は、ＲＩＰ(Routing Information Protocol)、ＯＳＰＦ(Open Shortest Path First)、またはＢＧＰ−４(Border Gateway Protocol 4)などのルーティングプロトコルから生成されるが、これらプロトコルに限定されない。効率的な検索のために考案されたフォワーディングテーブル(ＦＴ)であるコンパクトテーブルは、ルーティングプロセッサ１２０のルーティングテーブルからコピーされる。フォワーディングテーブルは、ルートの追加及び削除の効率性を犠牲にすることによって、検索効率のみのために設計された。
【００２５】
ラインカードモジュール１１０から受信されるパケットがフォワーディングテーブル(ＦＴ)から目的経路を発見することができない場合、当該パケットは、スイッチファブリック１３０を通してルーティングプロセッサ１２０に移動して発見できなかった経路に対する問題を解決すべきである。目的地を発見した後、前記パケットは、出力ラインカードモジュール１１０に伝送されるために、再びスイッチファブリック１３０に伝送されるべきである。ルーティングプロセッサ１２０がルーティングテーブル(ＲＴ)を通しても目的経路を発見することができなかった場合、前記パケットは、ルーティングプロセッサ１２０で捨てられる。
【００２６】
一方、Asthana, A., Delph, C., Jagadish, H., and Krzyzanowski, P., Towards a Gigabit IP Router, J. High Speed Network, vol. 1, no.4, pages 281-288,1992及びPartridge et al. (A 50-Gb/s IP Router, IEEE/ACM Trans. on Networking, vol. 6, no.3, pages 237-248, 1998)は、並列構造のルータに関して開示している。図２は、本発明が適用できる並列構造を有するルータを示す図である。図２に示す並列構造のルータにおいて、フォワーディングテーブル(ＦＴ)を有する各フォワーディングエンジン１１２は、ラインカードモジュール１１０において分離される。このような並列構造は、各フォワーディングエンジンにおいて並列パケット処理及びルートルックアップを取り扱うためにクライアント及びサーバー基盤のモデルを利用する。
【００２７】
ルーティングプロセッサ１２０におけるルーティングテーブルは、変更されたルートを直ちに反映して容易に維持することができるように設計されるべきである。さらに、追加または削除されるルートは、フォワーディングエンジン１１２におけるフォワーディングテーブル(ＦＴ)に最小の費用でなるべく迅速に反映されるべきである。ルートが反映されなかった場合、受信(incoming)パケットは、スイッチファブリック１３０を通してルーティングプロセッサ１２０に伝送されるので、当該パケットを処理するために要求される追加的なルートを通したバイパッシング(bypassing)によって伝送遅延が増加する。
【００２８】
以上、分散構造及び並列構造を参照して本発明を説明したが、他の構造を有するルータにも適用できることは、当該技術分野における通常の知識を持つ者には明らかである。
【００２９】
図３は、分散または並列構造を有するルータにおけるフォワーディングエンジン１１２の構造を示す図である。図４は、ルーティングプロセッサ１２０の構造を示す図である。
【００３０】
図３を参照すると、フォワーディングエンジン１１２は、ｎ個の入力インターフェース(input interface)、ｍ個の出力インターフェース(output interface)、入力インターフェースを通して入力されるパケットをバッファリングするｎ個のバッファ(buffer)、該バッファに貯蔵されたパケットを等級及び種類別に分類するパケット分類器(packet classifier)、及びフォワーディングテーブル及びパケット分類器によって分類されるパケットをフォワーディングテーブルを参照して該当出力インターフェースに伝送するルートルックアップ(route lookup)制御部を備える。
【００３１】
図４を参照すると、ルーティングプロセッサ１２０は、図１及び図２に示すスイッチファブリック１３０との間でパケットを送受信するｎ個の入／出力インターフェース(input/output interface)、この入／出力インターフェースを通して入出力されるパケットをバッファし、スイッチファブリック１３０と後段のルートルックアップ及び管理制御部との間をインターフェーシングするスイッチインターフェース(switch(or IPC) interface)、及びルーティングテーブル及びスイッチインターフェースから提供されるパケットをルーティングテーブルを参照してスイッチインターフェースを通じ対応する入／出力インターフェースに伝送するルートルックアップ及び管理制御部(route lookup and maintenance)を備える。
【００３２】
ＲＦＣ標準によると、ルーティングテーブル(または、フォワーディングテーブル)は、検索のために主に使用されるデータ構造である配列(array)、ツリー(tree)、及びトライ(trie)及びこれらを取り扱うために使用されるアルゴリズムに対しては制約がない。しかしながら、最長プレフィックスのマッチングのために、最小のメモリアクセスが必要になり、ルーティングテーブル(または、フォワーディングテーブル)内で変更されたルートが容易に更新されるべきである。
【００３３】
このために、本発明の実施形態において無作為抽出アルゴリズム(randomized algorithm)を利用する。この無作為抽出アルゴリズムは、実行中にランダムな選択をするアルゴリズムである。無作為抽出アルゴリズムは、全ての入力に対してうまく動作(well-behaved)できる設計分野に主に使用されている。これは、ある入力の処理において特定の仮定に基づいて処理することでなく、確率(例えば、コイン投げ)ｐに基づいて処理する。無作為抽出アルゴリズムの長所は、その単純性及び効率性にある。
【００３４】
無作為抽出アルゴリズムに基づいた本発明によるアルゴリズムは、最小のメモリアクセス数及びルーティングテーブルの簡単な管理を提供する。ルーティングエントリの管理の場合、全体のテーブルを再構成する従来の方式の代わりに、変更されたルート情報のみを再構成する。さらに、従来の一般的なツリーまたは２進検索トライ(binary trie)のようなルートルックアップアルゴリズムとは異なって、本発明によるアルゴリズムは、図５に示す目的地ＩＰアドレスのテール(tail)から最長プレフィックスを検索する。
【００３５】
さらに、本発明においては、ルーティングテーブルのために、Pugh, W., Skip Lists: A Probabilistic Alternatives to Balanced Trees, CACM 33(6), pages 6689-676, 1990に提示されたスキップリスト(skip list)を使用する。
【００３６】
このスキップリストは、分類(sorting)されたｎ個のノードを有するリンクリスト(linked list)としてみなされ、通常、“spray tree”などの“balanced tree”に代わったデータ構造に使用される。これは、Sleator, D. and Tarjan, R., Self-Adjusting Binary Search Trees, JACM, Vol. 32, No. 3, July 1985を参照する。従って、スキップリストは、挿入及び削除の動作のための“balanced tree”より単純で効率的である。本発明は、図６に示すように、最長プレフィックスマッチング(longest prefix matching)のために変形したスキップリスト(variant of skip list)を提案する。
【００３７】
図６は、本発明の実施形態によるスキップリストの変形を示す図である。図６を参照すると、各ノードは、１つまたは多数のポインタを有し、最左のノードはヘッダノード(header node)２１０と称されるが、その理由は、検索、追加、削除、及び更新などのスキップリストの変形に対する全ての演算(operation)がヘッダノード２１０から始まるからである。
【００３８】
ヘッダノード２１０は、キー値として＋∞を含み、次のノードを示すためにポインタを含む。ノード２２０、２３０、２４０、２５０、及び２６０のキーは、減少の順に分類(sorting)される。各ノードのキーは、‘プレフィックス長さ範囲’または‘プレフィックス長さ値のクラスタリング(clustering)’を意味し、このキーは、減少の順に挿入される。本発明の実施形態において、検索は、既存のトライまたはツリーとはまったく異なる方式であり、葉(leaves)から根(root or parent)(つまり、反転したキー値シーケンス)に遂行される。
【００３９】
第２ノード２２０のキーは、３２〜２４のプレフィックス長さ範囲を有し、このプレフィックス長さ範囲に属するプレフィックス長さを有するルートは、各プレフィックス長さに対応するハッシュテーブル(hash table)を有する。図６は、第２ノード２２０の範囲に属するルートのハッシュテーブルの例として、プレフィックス長さが３０ビットであるハッシュテーブル２２２及びプレフィックス長さが２４ビットであるハッシュテーブル２２４を示す。さらに、図６は、１７〜１２のプレフィックス長さ範囲を有する第４ノード２４０の範囲に属するルートのハッシュテーブルの例として、プレフィックス長さが１５ビットであるハッシュテーブル２４２を示す。
【００４０】
図６に示すように、多様なノードのプレフィックス長さ範囲は異なる長さ、つまり、固定的に分けられたプレフィックス範囲に固定されるが、このようなプレフィックス長さ範囲は、可変的な長さ、つまり、可変的に分けられたプレフィックス範囲を有するノードのグループ(group)に分けられることもできる。Srinivasan, V. and Varghese, G., Faster IP Lookups using Controlled Prefix Expansion, In Proceedings of ACM Sigmetrics '98 Conf., pages 1-11, 1998は、最善の記憶装置を提供するためにプレフィックス範囲を分割する動的プログラミング(dynamic programming)技術に関して開示する。本発明の実施形態によるアルゴリズムにおいて、類似した方式を使用してプレフィックス長さグループを分けることができる。しかしながら、図６に示す本発明の実施形態において、固定したプレフィックス長さ範囲を有することが望ましく、これによって、動的プログラミングによる追加的な計算作業負荷を避けることができる。
【００４１】
ＩＰｖ４のケースにおいて、プレフィックス長さ範囲が８に固定される場合、挿入されるノードの総数は５(1+[32/8](ここで、３２はＩＰｖ４アドレスにおける最大のビット数である))になることができる。ＩＰＭＡ(Internet Performance Measurement And Analysis : http://nic.merit.edu/ipmaを参照)からの実験結果から示すように、実際に参照されるプレフィックス長さの非対称的な分散(skewed distribution)は、実際に参照されるプレフィックス長さ分散に存在する局所性パターン(locality pattern)を示す。従って、本発明において、少数のノードを使用することが可能である。例えば、図７Ａ及び図７Ｂを参照すると、１７から２７までのプレフィックス長さが最も頻繁に参照される。従って、該当プレフィックス長さを含む範囲のプレフィックス長さキー値を有する１つのノードを設定し、他のプレフィックス長さ範囲による複数のノードを設定することができる。
【００４２】
再び図６を参照すると、ヘッダノード２１０の変数‘ＭａｘＬｅｖｅｌ’は、スキップリストに属する全てのノードのうち最大のレベル値、つまり、ヘッダノードにおいて他のノードをポインティングするためのポインタの総数を示す。各ノードは、ノードｘのレベルＬでノードｘから隣接したノードまでポインティングするためのポインタを示すキー値‘x->key’(または、key(x))及びポインタ‘x->forward[L]’(または、next(x, L))を保有する。
【００４３】
ヘッダノード２１０を除いて、ノード内の各キーは、プレフィックス長さ範囲または集合(set)を有する。図６において、ノード２２０は、３２乃至２４の範囲のルートエントリを有し、各プレフィックス長さは、対応するプレフィックス長さに一致するルートエントリを貯蔵するためのハッシュテーブルを有する。３２から２４までの範囲の各プレフィックス長さに対応するルートエントリが存在する場合、該当ノードは、９つの異なるハッシュテーブルをポインティングするための９つのポインタを有する。各ハッシュテーブルは、各プレフィックス長さに正確に一致するルートエントリのみを貯蔵する。これは、スキップリストの変形を‘k-ary hashed node’を有するスキップリストと称する理由である。
【００４４】
本発明によるスキップリストに基づいたアルゴリズムに対する理解を容易にするために、ヘッダノードの生成及び様々なスキップリストの構築方法に関して説明する。
【００４５】
図８は、本発明の実施形態によるヘッダノードの生成方法に関して説明する図である。図８を参照すると、ヘッダノードは、＋∞キー値及びＭａｘＬｅｖｅｌ＝５(1+[32/8])を有し、ここで、ＭａｘＬｅｖｅｌ＝１＋［Ｗ／ｎ］である。ＷはＩＰアドレスのビット長さ、例えば、ＩＰｖ４：３２及びＩＰｖ６：１２８であり、ｎはプレフィックス範囲である。ヘッダノードは、包括的にスキップリスト内の全てのノードを取り扱うべきであるので、ＩＰｖ４の場合、前記確率ｐが１／２であり、プレフィックス範囲が１であると、２３２に達するルートを有するデータ構造用としてＭａｘＬｅｖｅｌ＝３２が適切である。ヘッダノードは、０乃至ＭａｘＬｅｖｅｌ−１のインデックスが付けられたＭａｘＬｅｖｅｌ個の伝送ポインタを有する。本発明の実施形態において、プレフィックス範囲を固定的にまたは可変的にクラスタリングすることによって、固定プレフィックス範囲が８であると仮定する場合、ＭａｘＬｅｖｅｌ＝５が要求される。
【００４６】
ヘッダノードが生成された後、スキップリストの異なる部分に対する構築に関して図９を参照して説明する。図９は、本発明の実施形態によるスキップリストの構築動作を説明するための図である。ヘッダノードの最上位のレベルのポインタがヌル(null)である場合、つまり、ヘッダノードのポインタに連結されたサブノードである隣接したノードが存在しない場合、前記レベルは、ポインタが隣接したノードを示すまで１ずつ減少される。図９を参照すると、３２〜２４のプレフィックス範囲値を有する第１ノード(ａ)が生成され、ヘッダノードにおいてレベル０のポインタはその第１ノードを示す。次に、２３〜１８のプレフィックス範囲を有する第２ノード(ｂ)及び１７〜１２のプレフィックス範囲を通する第３ノード(ｃ)が順次に生成される。この生成過程において、全てのプレフィックス長さ範囲をカバーすることができるように複数のノードが生成される。
【００４７】
それぞれ生成されたノードのレベルは、プログラム３に示すように、本発明による無作為抽出アルゴリズムを利用して無作為に設定される。まず、(０,１)に属する実数の乱数値が生成される。この生成された乱数値が予め設定された基準確率値(ここで、基準確率は、理想的なスキップリストの生成のためにｐ＝１／２に設定される)より小さく、生成しようとする該当ノードのレベルがＭｘＬｅｖｅｌより小さい場合、該当ノードのレベルは増加される。そうでない場合、レベル値０を有するノードが生成される。
【００４８】
このように、スキップリストにおいてプレフィックス範囲によってノードを構成した後、ルートエントリを含むルーティングテーブルが構築されるべきである。図１０Ａを参照して、ルータがプレフィックス長さ３０のルートを有する時、ルーティングテーブルを構築する方法に関して説明する。
【００４９】
図１０Ａを参照すると、ルータがプレフィックス長さ３０のルートを有する時、スキップリストにおいて３２〜２４のプレフィックス長さ範囲を有する第１ノード２２０が検索され、次に、追加されるルートエントリがハッシュテーブルの形態で挿入される。スキップリストのノードは、対応するプレフィックス長さによって異なるハッシュテーブルを有する。同一の手順によって、図１０Ｂに示すように、１７〜１２のプレフィックス範囲を有するノード２４０下でプレフィックス長さ１５のハッシュテーブルが生成されるので、プレフィックス長さ１５のルートが追加される。
【００５０】
ルーティングテーブルの生成の手順を簡略に説明すると、図１１のようである。図１１は、本発明の実施形態によるルーティングテーブル構築の過程を示す図である。段階１１ａで、スキップリスト内の全てのノードを取り扱うためのＭａｘＬｅｖｅｌを有するヘッダノードが生成される。次に、段階１１ｂで、固定分割されたプレフィックス範囲を有するノードがリストに挿入される。段階１１ｂの動作を簡略化するために、本発明は固定分割されたプレフィックス範囲を提案しているが、実際プレフィックス長さ分散が反映されるように適応的に分割されたプレフィックス範囲を設定することもできる。それから、段階１１ｃで、対応するプレフィックス範囲を有するノード下で、それぞれの所定のルートエントリのためのハッシュテーブルが生成される。本発明による新しい方式は、最短のプレフィックス長さから検索する従来の一般的なトライまたはツリー構造とは異なって、最長プレフィックス長さを有するルートから始まる検索を提供する。
【００５１】
ルータは、接続された他のルータからしばしばルート変更情報を受信する。この変更は、現在のルーティング(または、フォワーディング伝送)テーブルに反映されるべきである。前述したように新しい方式による更新作業に対して、図１２を参照して説明する。所定の変更されたルート(プレフィックス)をルーティングテーブルに反映するために、段階１２ａで、プレフィックス長さに一致するノードを発見する。それから、段階１２ｂで、変更されたルートと同一のプレフィックス長さを有するハッシュテーブルを検索する。段階１２ｃで、該当ハッシュテーブルが発見されたと確認された場合、段階１２ｄに進行して、該当ハッシュテーブル内の前記検出されたルートを更新または削除する。段階１２ｃで、該当ハッシュテーブルが存在しないと確認される場合は、段階１２ｅに進行する。段階１２ｅで、前記ルートが追加された場合、段階１２ｆに進行して、当該変更ルートと同一のプレフィックス長さを有するハッシュテーブルを生成する。それから、段階１２ｇで、変更ルートは、新しく生成されたハッシュテーブルに挿入される。前記ルートが追加されなかった場合、段階１２ｈで、当該変更ルートは捨てられる。
【００５２】
図１３及び図１４は、本発明の実施形態によるルート検索及びルート更新の過程を説明するための図である。
【００５３】
まず、図１３を参照して、プレフィックス長さ１５のルートを検索する過程を説明する。まず、同一のプレフィックス長さ１５を有するノードを発見する。この検索は、ヘッダノード２１０の最上位レベル(レベル４)から始まる(図１３の段階(１))。レベル４のポインタは、レベル４を有する次のノード、つまり、８〜１のプレフィックス長さ範囲(キー)を有するノード２６０をポインティングする(図１３段階(２))。それから、当該ルートのプレフィックス長さとノード２６０のキーとの比較が遂行される。キー値は一致せず、検索はヘッダノード２１０の同一のレベル(例えば、レベル４)に戻る(図１３の段階(３))。ヘッダノード２１０のレベルは１の分だけ減少され(図１３の段階(４))、次のレベル(レベル３)のポインタはレベル３を通する次のノード、つまり、１７〜１２のキーを有するノード２４０をポインティングする(図１３の段階(５))。ノード２４０において一致するキー値が発見された(図１３の段階(６))場合、変更されたルートのプレフィックス長さに対応するハッシュテーブルを検索する(図１３の段階(７))。ハッシュテーブルが存在する場合、次のホップ(hop)(図１３の段階(８))が遂行される。ハッシュテーブルが存在する場合、そのハッシュテーブルは新しいルートを追加するために生成される。
【００５４】
図１４は、次のホップ(hop)インターフェースが‘１０’であるプレフィックス‘１１１０１０…１’を有するルートが、ハッシュテーブルから削除されるか、それもと次のホップが‘１’である‘１１１０１１…１’に変更される多数の段階を示す。該当プレフィックス(１１１０１０…１)を検索する段階は、図１３に示す過程と類似して遂行される。
【００５５】
以下、図１５及び図１６を参照して、ルーティングテーブルから特定の目的地ＩＰアドレスのルートを検索するルートルックアップ動作を詳細に説明する。
【００５６】
図１５及び図１６は、本発明の実施形態によるルートルックアップの過程を最長プレフィックスマッチング方式(longest prefix matching scheme)として定義する。この最長プレフィックスマッチング方式に基づいた検索は、ルートエントリが最長プレフィックス、例えば、ＩＰｖ４のプレフィックス長さ３２から比較されるべきであることを意味する。図１６は、本発明の実施形態による全体のルックアップ方式を説明するための図であり、ここで、目的地アドレスは、‘１１１０１０１…１’のプレフィックス長さ１５を有する。
【００５７】
図１５の段階１５ａで、ＩＰヘッダにおいてカプセル化(encapsulated)した所定の目的地アドレスに対して、スキップリストの第１ノードが検索される。従って、目的地アドレスによって与えられたルートルックアップは、ヘッダノード２１０のレベル４から始まり(図１６の段階(１))、ヘッダノード２１０のレベルは、レベル０になるまで１ずつ減少され(図１６の段階(２))、レベル０は、第１ノード２１０をポインティングするポインタを有する(図１６の段階(３))。
【００５８】
段階１５ｂで、プレフィックス長さ範囲の上位キー値、例えば、３２(現在のプレフィックス長さ)から開始して第１ノード２２０のハッシュテーブルを検索する。ハッシュテーブルが存在しない場合、前記過程は段階１５ｇに進行する。反対に、段階１５ｃで、ハッシュテーブルが存在する場合、過程は段階１５ｄに進行する。段階１５ｄで、ハッシュテーブル内で目的地アドレスに対応するプレフィックスを検索する。段階１５ｅで、検索されたプレフィックスが目的地アドレスと一致する場合、段階１５ｆで、一致したプレフィックスを最長プレフィックスとしてリターン(return)する。一方、段階１５ｅで、プレフィックスが一致しない場合、過程は段階１５ｇに進行する。
【００５９】
段階１５ｇで、過程は、同一のプレフィックス範囲において次のハッシュテーブルを検索する。段階１５ｈで、次のハッシュテーブルが存在する場合、前記過程は、１５ｂに進行して前述した過程を繰り返す。段階１５ｈで、次のハッシュテーブルが存在しない場合、過程は段階１５ｉに進行してスキップリストにおいて隣接したノードに移動し、段階１５ｂに戻って前述した過程を当該隣接したノードにおいて繰り返す。以上のように、本発明による新しい検索方式は、従来のルートノードから始まる検索方式とは異なって、自体のハッシュテーブルを有する最長プレフィックス範囲から始まる検索に基づいている。
【００６０】
図１６を再び参照すると、まず、前述したように、スキップリストにおいてノードを探し、所定の目的地アドレスによってルートルックアップがヘッダノードから始まる(図１６の段階(１))。ヘッダノード２１０におけるレベルは、ポインタが最長プレフィックス範囲を有するノードをポインティングするレベル０になるまで減少され(図１６の段階(２))、次に、ヘッダノード２１０のポインタによってポインティングされる第１ノード２２０を横切る(図１６の段階(３))。従って、第１ノード２２０は、プレフィックス長さ３２を含むハッシュテーブルを探すために検索される。該当ハッシュテーブルが検索された場合、目的地アドレスは、一致を発見するために、そのハッシュテーブル内のプレフィックスと比較される。スキップリスト内の各ノードがノードプレフィックス範囲内の各ハッシュテーブルをポインティングするポインタアレイ(pointer array)を維持するので、長さ３２のプレフィックスを含むハッシュテーブルが存在しない場合、ポインタに対応するプレフィックスはヌル(null)になる。
【００６１】
図１６の例において、第１ノード２２０は、それぞれプレフィックス長さ３０及びプレフィックス長さ２６に対応するハッシュテーブル２２２及び２２４のみを有する。従って、ハッシュテーブルを発見するために第１ノード２２０を検索する時、プレフィックス範囲における各ポインタを検査し、ヌル値を有するポインタはスキップされる。ヌル値を有しないポインタに対応するハッシュテーブルは、元の目的地アドレスと比較されて一致を探す。
【００６２】
従って、ヌル値を有する第１ポインタは、ハッシュテーブル２２２をポインティングし、目的地アドレスは、ハッシュテーブル２２２においてプレフィックスと比較される(図１６の段階４)。ハッシュテーブル２２２において目的地アドレスが検索されなかった場合、非ヌルのポインタを有する次のハッシュテーブル、つまり、プレフィックス長さ２６のハッシュテーブル２２４が、目的地アドレスと比較される(図１６の段階(５))。目的地アドレスが発見されず、第１ノード２２０においてハッシュテーブルがそれ以上存在しない場合、ノード２２０に対してルックアップは失敗になる。
【００６３】
第１ノード２２０においてルックアップが失敗した時、次の最長プレフィックス範囲を有するスキップリストにおいて次のノードを示すポインタを検索する。この例において、次の最長プレフィックス範囲を有するスキップリストにおける次のノードが第２ノード２３０であることを示すポインタがある(図１６の段階(６))。従って、どのハッシュテーブルを有するかノード２３０を検査して、ハッシュテーブルが存在しない場合、スキップリストにおいて次のノードをポインティングするノード２３０のポインタを検索する。
【００６４】
この場合、スキップリストにおいて隣接したノード２４０に移動し(図１６の(７))、図１５に示す段階によってハッシュテーブルをポインティングするポインタを発見する。目的地アドレスは、プレフィックス長さ１５のハッシュテーブル２４２においてプレフィックスと比較される(図１６の段階(８))。この比較によって一致が発生すると、ルートルックアップ動作は成功に終了する(図１６の段階(９))。最後のノード２６０の最後のハッシュテーブルにおいて目的地アドレスが発見できなかった場合、ルックアップは失敗し、対応するアドレスを有するパケットは、デフォルトルートエントリを有するルートに送られる。
【００６５】
以下、スキップリストの構築はプログラム１、２、及び３（数式１、２、３で示す）において表現され、ルートエントリの変化のスキップリストへの反映は、プログラム４、５、６、及び７（数式４、５、６、７で示す）において示し、新しいアルゴリズムの基本部分であるルートルックアップはプログラム８（数式８で示す）において示す。
【００６６】
【数１】
0003790217.tif 000003
【００６７】
【数２】
0003790217.tif 000004
【００６８】
【数３】
0003790217.tif 000005
【００６９】
【数４】
0003790217.tif 000006
【００７０】
【数５】
0003790217.tif 000007
【００７１】
【数６】
0003790217.tif 000008
【００７２】
【数７】
0003790217.tif 000009
【００７３】
【数８】
0003790217.tif 000010
【００７４】
ここで、図７Ａ及び図７Ｂを参照して、本発明によるルーティング方式の効率を説明する。図７Ａ及び図７Ｂは、インターネット上におけるプレフィックス長さ分布の測定値を示すグラフである。図７Ａ及び図７Ｂのグラフによって表現されるデータは、ＩＰＭＡ(Internet Performance Measurement and Analysis)プロジェクトで最近ＭＡＥ−ＥＡＳＴ ＮＡＰ(Network Access Point)において収集されたデータを示す。
【００７５】
ＩＰＭＡプロジェクトで収集された統計データは、ルートルックアップアルゴリズム開発者の研究結果を相互に分析する源泉データとして広く使用される。ＭＡＥ−ＥＡＳＴ ＮＡＰにおけるルータは、最大のルートエントリを含み、主にバックボーン(backbone)ルータのモデルとして使用される。ＰＡＩＸ ＮＡＰは、現在のＩＰＭＡプロジェクトで収集された最小のルートエントリを含み、主にエンタープライズ(enterprise)ルータのモデルとして利用される。
【００７６】
図７Ａ及び図７Ｂは、１６〜２８のプレフィックス長さが最も頻繁に参照されることを示す局所性パターン(locality pattern)を示す。従って、このような観測結果は、本発明において提示された変更スキップリストに含まれるノードの数が大きく減少されることを示す。ＩＰＭＡ(http://nic.merit.edu/ipma)における他の興味深い結果は、一日にＢＧＰによって追加されるか、それとも撤回されたルーティングプレフィックスの数が１,８９９,８５１(1997年11月1日現在)に達することである。これは、２５ｐｒｅｆｉｘ-ｕｐｄａｔｅｓ／ｓｅｃを要求するほどに緊迫であり、変更されたルーティングプレフィックスをルーティングテーブル(または、フォワーディングテーブル）に迅速に反映することは検索時間以外に主要要素である。
【００７７】
以下、表２を参照して、本発明によるアルゴリズムと従来のアルゴリズムとの差に関して説明する。通常、アルゴリズムに対する分析は、該当アルゴリズムを処理するために要求される時間または使用するメモリに対する“worst-case complexity”を“big-O notation”を使用して相互に比較する。表２は、本発明による新しいアルゴリズムによって要求される複雑度を示す。ここで、Ｎ個のルートエントリが存在し、各アドレスを表現するためにＷ個のアドレスビットが要求され、ｋはアルゴリズム依存性常数(algorithm-dependent constant)である。
【００７８】
【表２】
0003790217.tif 000011
【００７９】
表２において、ベース(base)１０の他の対数(logarithm)との混同を防止するために、ベース２の対数をｌｇに表現する。
【００８０】
ＩＰｖ４において、Ｗは３２に該当し、ＩＰｖ６の場合は、１２８に該当する。前記ＭＡＥ−ＥＡＳＴ及びＰＡＩＸ ＮＡＰにおいて、ルートエントリの数Ｎは、それぞれ約５０,０００及び６０,０００である。この場合、プレフィックス範囲が８であると、‘k-ary hashed node’を有するスキップリストにおけるｋは４である。ＩＰｖ６の場合は１６である。
【００８１】
本発明によるアルゴリズムは、既存の検索ツリー(search tree)及びトライ(Patricia trie またはLC-trie)に比べて、テーブルの構築、追加及び削除動作の面で優れている。さらに、本発明による新しいアルゴリズムは、“Binary hash table search”(Waldvogel, M., Varghese, G., Turner, J. and Plattner, B., Scalable High Speed IP Routing Lookups, In Proceedings of ACM SIGCOMM '97, Cannes, France, pages 25-37, 1997)及び“Complete prefix trie”(Tzeng, H. and Pryzygienda, T., On Fast Address-Lookup Algorithms, IEEE Journal on Selected Areas in Communications, Vol. 17, No. 6, pages 1067-1082, June, 1999)に比べて、構築時間及び追加または削除動作において優れている。さらに、表２において、新しいアルゴリズムが純粋のスキップリスト(pure skip list)より優れていることを示す複雑度の結果を理解できる。
【００８２】
前述の如く、本発明の詳細な説明では具体的な実施形態を参照して詳細に説明してきたが、本発明の範囲は前記実施形態によって限られるべきではなく、本発明の範囲内で様々な変形が可能であるということは、当該技術分野における通常の知識を持つ者には明らかである。
【００８３】
【発明の効果】
前述してきたように、本発明によるアルゴリズムは、無作為抽出アルゴリズムを構成するスキップリスト及びハッシュテーブルを利用して、インターネットプロトコルアドレスのプレフィックス範囲によってノードを生成する。さらに、本発明は、各ノードで設定されたプレフィックス長さによるハッシュテーブルの形態でルートエントリが貯蔵されるスキップリストを利用するルーティング方式を提供することによって、経路検索時間を最小化し、関連テーブルを効率的に管理する。そうすることによって、高速経路検索が可能になる。このアルゴリズムは、将来使用されるＩＰｖ６に適用されることもできる。
【００８４】
さらに、本発明は、既存のアルゴリズムに比べて、全ての面で、特に、ルーティングテーブルまたはフォワーディングテーブルの構築、追加、及び削除動作の面で優れていることが複雑度分析結果から分かる。さらに、フォワーディングエンジンにおけるフォワーディングテーブルがルーティングプロセッサにおけるルーティングテーブルと依然として分離される分散形態のルータ構造または並列形態のルータ構造などの最近の構造に対する傾向において、全てのルートエントリでなく前記経路に沿って更新されたルートのみをルータに移すことによって、メモリ帯域幅またはシステムバスコンテンション(contention)が減少される。さらに、経路検索時間の短縮及び全てのルーティング関連テーブルを通した前記一致するルーティング情報の管理は、ＱoＳ(Quality of service)、マルチキャスティング、ＩＰＳｅｃなどの他の因子を通して性能向上に寄与する。
【図面の簡単な説明】
【図１】  本発明が適用できる分散形態のルータ構造を示す概略図である。
【図２】  本発明が適用できる並列形態のルータ構造を示す概略図である。
【図３】  本発明が適用できる伝送エンジンの構造を示す概略図である。
【図４】  ルーティングプロセッサの構造を示す概略図である。
【図５】  本発明の実施形態によるＬＰＭ(Longest Prefix Matching)アルゴリズムを説明するための図である。
【図６】  本発明の実施形態によるスキップリストの構造を示す図である。
【図７】  Ａは、インターネット上におけるプレフィックス長さ分布の測定値を示すグラフである。Ｂは、インターネット上におけるプレフィックス長さ分布の測定値を示すグラフである。
【図８】  本発明の実施形態によるヘッダノードの構造を示す図である。
【図９】  本発明の実施形態によるスキップリスト構築作業を説明するための図である。
【図１０】  Ａは、本発明の実施形態によってプレフィックス長さによるルーティングテーブルを構築する作業を説明するための図である。Ｂは、本発明の実施形態によってプレフィックス長さによるルーティングテーブルを構築する作業を説明するための図である。
【図１１】  本発明の実施形態によるルーティングテーブルの生成過程を示すフローチャートである。
【図１２】  本発明の実施形態によるルーティングテーブルの更新過程を示すフローチャートである。
【図１３】  本発明の実施形態によるルート検索及び更新作業を説明するための図である。
【図１４】  本発明の実施形態によるルート検索及び更新作業を説明するための図である。
【図１５】  本発明の実施形態によるルートルックアップ過程を示すフローチャートである。
【図１６】  本発明の実施形態による全体ルックアップ過程を説明するためのスキップリスト構造を示す図である。
【図１】
0003790217.tif 000012
【図２】
0003790217.tif 000013
【図３】
0003790217.tif 000014
【図４】
0003790217.tif 000015
【図５】
0003790217.tif 000016
【図６】
0003790217.tif 000017
【図７】
0003790217.tif 000018
【図８】
0003790217.tif 000019
【図９】
0003790217.tif 000020
【図１０】
0003790217.tif 000021
【図１１】
0003790217.tif 000022
【図１２】
0003790217.tif 000023
【図１３】
0003790217.tif 000024
【図１４】
0003790217.tif 000025
【図１５】
0003790217.tif 000026
【図１６】
0003790217.tif 000027