(57)【要約】【課題】  分散構造ルータの全てのノードが各ノードで収集されるルーティング情報を実時間で共有し、ルーティング情報に基づいてフォーワーディング情報をアグリゲーションによって動的に管理する方法を提供する。【解決手段】  分散構造ルータの全てのノードで収集されるルーティング情報を各ノードが実時間で共有し、ルーティング情報を利用してフォーワーディング情報を動的に管理することで、ルーティング情報を共有するための各ノード間のパケットフォーワーディング過程を省略することができる。また、ルーティング情報をフォーワーディングテーブルに選択的にアップデートすることによって、ノード別のフォーワーディングテーブルを効率的に管理する。さらに、２進アグリゲーションツリー(aggregation tree)を利用して各ノードのフォーワーディング情報を管理し、ルーティング情報に対応するノード情報をアグリゲーションする仮想ノードのレベルを可変的に設定することによって分散構造ルータのノード別のフォーワーディングテーブルのサイズを低減する。【選択図】    図５
2004236339.tif 000002
【特許請求の範囲】
【請求項１】
分散構造ルータにおいて、
複数のルーティングプロトコルを有する複数のルーティングノードと、
前記各ルーティングノードのルーティングプロトコルに対応する複数のルーティングプロトコルを有し、前記各ルーティングノードによって収集されたルーティング情報を他のルーティングノードと実時間で共有するスイッチングモジュールと、を有することを特徴とする分散構造ルータ。
【請求項２】
（１）ルーティングテーブルに対するアグリゲーションツリーによって生成されたフォーワーディング情報を全てのルーティングノードが共有する分散構造ルータで、ルーティングテーブルにルーティング情報が挿入される場合、そのルーティング情報に対応する挿入ノードがアグリゲーションツリーに挿入された位置を探索する過程と、
（２）予め設定された最大アグリゲーションレベル範囲内で挿入ノードの先祖ノードの有無を決定する過程と、
（３）フォーワーディングテーブルに先祖ノードに対応するフォーワーディング情報が存在し、挿入ノード及び先祖ノードのソース領域が同一であると、該先祖ノードが存在する挿入ノードの情報をフォーワーディングテーブルにアップデートしない過程と、
（４）先祖ノードが存在しない場合、最大アグリゲーションレベル範囲内でアグリゲーションレベルを再設定し、該再設定されたアグリゲーションレベルに挿入ノードを代表する仮想ノードを挿入する過程と、
（５）挿入されたルーティング情報を生成したソース領域を確認し、該ルーティング情報のソース領域が、仮想領域である場合はフォーワーディングテーブルに仮想ノードのフォーワーディング情報を挿入し、ローカル領域である場合はフォーワーディングテーブルに挿入ノードのフォーワーディング情報を挿入することによって、フォーワーディング情報を挿入する過程と、を含むことを特徴とする分散構造ルータにおけるフォーワーディング情報管理方法。
【請求項３】
新しいルーティング情報に対応する挿入ノードがアグリゲーションツリーに挿入される位置を検出して、該挿入ノードの位置に仮想ノードが存在する場合、当該挿入ノードに対応するフォーワーディング情報を挿入した後、フォーワーディングテーブルから仮想ノードに対応するフォーワーディング情報を削除する過程をさらに含む請求項２記載のフォーワーディング情報管理方法。
【請求項４】
新しいルーティング情報に対応する挿入ノードがアグリゲーションツリーに挿入される位置を検出して、該挿入ノードの位置に仮想ノードが存在し、該仮想ノードの左／右サブツリーが存在する場合、当該挿入ノードに対応するフォーワーディング情報を挿入した後、左／右サブツリーノードを再挿入し、フォーワーディングテーブルから仮想ノードに対応するフォーワーディング情報を削除する過程をさらに含む請求項２記載のフォーワーディング情報管理方法。
【請求項５】
先祖ノードの有無を決定して、挿入ノードの先祖ノードが最大アグリゲーションレベル範囲内に存在する場合、該挿入ノードの子孫ノードを探索する過程と、
挿入ノードの子孫ノードが存在する場合、挿入ノードと子孫ノードに対するフォーワーディング情報のプレフィックスの差によってアグリゲーションレベルを再設定し、挿入ノードの子孫ノードが存在しない場合、挿入ノードの先祖ノードのレベルによってアグリゲーションレベルを再設定する過程と、
再設定されたアグリゲーションレベルが０である場合、フォーワーディングテーブルに挿入ノードに対応するフォーワーディング情報を挿入する過程と、
再設定されたアグリゲーションレベルが０より大きい場合、フォーワーディングテーブルに挿入ノードを代表する仮想ノードを挿入する過程と、
挿入されたルーティング情報のソース領域を確認し、該ルーティング情報のソース領域が、仮想領域である場合はフォーワーディングテーブルに仮想ノードに対応するフォーワーディング情報を挿入し、ローカル領域である場合はフォーワーディングテーブルに挿入ノードに対応するフォーワーディング情報を挿入する過程と、を含む請求項２記載のフォーワーディング情報管理方法。
【請求項６】
先祖ノードが存在しない場合、最大アグリゲーションレベル範囲内でアグリゲーションレベルを再設定し、該再設定されたアグリゲーションレベルに挿入ノードを代表する仮想ノードを挿入する過程は、 
挿入ノードの先祖ノードが存在するか否かを判断するための探索レベル範囲を設定する過程と、
挿入ノードの先祖ノードが探索レベル範囲内に存在する場合、最大アグリゲーションレベル範囲内に挿入ノードを代表する仮想ノードの子孫ノードが存在するか否かを判断する過程と、
最大アグリゲーションレベル範囲内に挿入ノードを代表する仮想ノードの子孫ノードが存在する場合、該仮想ノードの子孫ノードのプレフィックスと挿入ノードのプレフィックスとの差によってアグリゲーションレベルを再設定する過程と、
再設定されたアグリゲーションレベルに挿入ノードの仮想ノードを挿入する過程と、を含む請求項２記載のフォーワーディング情報管理方法。
【請求項７】
ルーティングテーブルからルーティング情報が削除される場合、削除されたルーティング情報に対応する削除ノードをアグリゲーションツリーで探索する過程と、
削除ノードに対応するフォーワーディング情報がフォーワーディングテーブルに存在する場合、予め設定された最大アグリゲーションレベル範囲内で削除ノードの子孫ノードを探索する過程と、
予め設定された最大アグリゲーションレベルより低いアグリゲーションレベルに削除ノードの子孫ノードが存在する場合、該子孫ノードを仮想ノードの新しいソースノードとして変更し、予め設定された最大アグリゲーションレベルより低いアグリゲーションレベルに削除ノードの子孫ノードが存在しない場合、フォーワーディングテーブルから削除ノードに対応するフォーワーディング情報を削除する過程と、を含むことを特徴とする分散構造ルータにおけるフォーワーディング情報管理方法。
【請求項８】
削除ノードが仮想ノードを生成したソースノードである場合、その仮想ノードに対応するフォーワーディング情報によって削除ノードに対応するフォーワーディング情報を変更する過程をさらに含む請求項７記載のフォーワーディング情報管理方法。
【請求項９】
分散構造ルータにおいて、
分散構造ルータ内でフォーワーディング情報に関する複数のルーティングプロトコルを含むスイッチングモジュールと、ローカル領域を含むソース領域に対応するサービスネットワークのそれぞれに配置された複数のルーティングノードと、を含み、
前記複数のルーティングノードは、前記スイッチングモジュールを通じて仮想領域を含むソース領域に連結され、収集されたルーティング情報を管理するルーティングテーブル及びそのルーティングテーブルによって生成されたアグリゲーションツリーを実時間で共有することを特徴とする分散構造ルータ。
【請求項１０】
ルーティングテーブルに新しいルーティング情報が挿入されると、ルーティングノードは、
アグリゲーションツリーで新しいルーティング情報に対応する挿入ノードが追加される位置を識別する過程と、
挿入ノードの先祖ノードを識別するために、最大アグリゲーションレベル範囲内でアグリゲーションツリーを探索する過程と、
この探索過程で先祖ノードが識別され、挿入ノードと先祖ノードが同一のソース領域から生成された場合、該挿入ノードに対応するフォーワーディング情報をフォーワーディングテーブルにアップデートしない過程と、
前記探索過程で、先祖ノードが識別されない場合、最大アグリゲーションレベル範囲内でアグリゲーションレベルを再設定し、再設定されたアグリゲーションレベルに挿入ノードを代表する仮想ノードを挿入する過程と、
新しいルーティング情報のソース領域を確認する過程と、
新しいルーティング情報のソース領域が仮想領域である場合は、仮想ノードに対応するフォーワーディング情報を挿入する過程と、
新しいルーティング情報のソース領域がローカル領域である場合は、挿入ノードに対応するフォーワーディング情報を挿入する過程と、を実行する請求項９記載の分散構造ルータ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、分散構造ルータにおいてフォーワーディング情報を管理する方法に関し、特に、分散構造ルータの全てのノードが各ノードで収集されるルーティング情報を実時間で共有し、そのルーティング情報に基づいてフォーワーディング情報をアグリゲーション(aggregation)によって動的に管理する方法に関する。
【背景技術】
【０００２】
大容量超高速ネットワークの発展につれて、ルータは、既存の中央集中形構造から分散処理形の新しい構造に変化していく。
【０００３】
中央集中形ルータにおいて、中央のプロセッサは、ルーティングプロトコルを具現し、このルーティングプロトコルによって収集されたルーティング情報を管理する。例えば、中央のプロセッサは、ルーティングテーブルを計算し、それぞれのラインカードにルーティングテーブルを分配する。従って、ラインカードは、中央のプロセッサによって計算されたルーティングテーブルに基づいてフォーワーディングを遂行する。
【０００４】
一方、分散処理形ルータは、中央のプロセッサに集中された作業を複数のプロセッサに分散処理させる。従って、分散処理形ルータは、中央集中形ルータに比べて大容量のデータ処理ができる。例えば、分散処理形ルータは、ルーティングプロトコルを管理する第１プロセッサ、ルーティングテーブルを計算する第２プロセッサ、及びパケットフォーワーディングを管理する第３プロセッサを別々に備える。これらそれぞれのプロセッサは、該当作業を分散処理することによって、ルーティング性能が向上する。
【０００５】
ルーティングノード(routing node: ＲＮ)は、それぞれのサブネットワークを支援するためのルーティングテーブル及びそれぞれのルーティング経路を処理するためのプロセッサを含む。分散構造ルータにおいて、このようなＲＮは、他のＲＮのルーティングテーブルを全体的に管理することによって、使用者に１つのルータとして見られる。
【０００６】
各ＲＮの入／出力プロセッサは、ルーティングプロトコル、管理プロセッサ及びルーティングテーブルを含むシステムプロセッサ領域と、フォーワーディングテーブルを含むネットワーク領域とに区分される。各ＲＮのシステムプロセッサは、ルーティング情報を収集し、ルーティング経路を計算することによって得られたフォーワーディングテーブルを管理し、他の入／出力プロセッサとルーティングテーブルを共有する一連の過程を遂行する。一方、ネットワークプロセッサは、フォーワーディングテーブルに基づいてローカル領域に連結されたネットワーク装備間にデータを伝送する。従って、分散構造ルータは、大容量のデータを迅速に処理すべきである。
【０００７】
分散構造ルータにおいて、各ＲＮは、大容量のデータを迅速に処理するために他のＲＮとフォーワーディングを共有する必要がある。例えば、従来は、任意の１つのＲＮが全てのＲＮのフォーワーディングテーブルを全体的に管理するために、各ＲＮが他のＲＮとフォーワーディングテーブルを交換している。結果的に、分散構造ルータにおいて、各ＲＮは、フォーワーディングテーブルを貯蔵するための大容量のメモリを備えなければならず、これは、パケットフォーワーディングという不要のオーバーヘッドを生じさせる。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
本発明は、上記のような従来の問題点を解決するために案出され、本発明の第１目的は、分散構造ルータにおいて各ノードがルーティング情報を共有するためにパケットをフォーワーディングすることによって発生する内部トラヒックの増加を防止する分散構造ルータ及びその方法を提供することにある。
【０００９】
本発明の第２目的は、分散構造ルータの全てのノードで収集されるルーティング情報を各ノードが実時間で共有する分散構造ルータ及びその方法を提供することにある。
【００１０】
本発明の第３目的は、分散構造ルータのノード別のフォーワーディングテーブルのサイズを低減するようにフォーワーディング情報を管理するルータ及びその方法を提供することにある。
【００１１】
本発明の第４目的は、分散構造ルータの全てのノードで収集されるルーティング情報を各ノードが実時間で共有する分散構造ルータのノード別フォーワーディング情報を管理するルータ及びその方法を提供することにある。
【００１２】
本発明の第５目的は、分散構造ルータのルーティング情報に対応するノード及びルーティング情報をアグリゲーションする仮想ノードから構成された２進アグリゲーションツリー(aggregation tree)を利用して各ノードのフォーワーディング情報を管理するルータ及びその方法を提供することにある。
【００１３】
本発明の第６目的は、仮想ノードのアグリゲーションレベルを可変的に設定することによってフォーワーディング情報を効率的に管理するルータ及びその方法を提供することにある。
【課題を解決するための手段】
【００１４】
このような目的を達成するための本発明は、分散構造ルータにおいて、複数のルーティングプロトコルを有する複数のルーティングノードと、各ルーティングノードのルーティングプロトコルに対応する複数のルーティングプロトコルを有し、各ルーティングノードによって収集されたルーティング情報を他のルーティングノードと実時間で共有するスイッチングモジュールと、を有することを特徴とする。
【００１５】
そして、本発明は、（１）ルーティングテーブルに対するアグリゲーションツリーによって生成されたフォーワーディング情報を全てのルーティングノードが共有する分散構造ルータで、ルーティングテーブルにルーティング情報が挿入される場合、そのルーティング情報に対応する挿入ノードがアグリゲーションツリーに挿入された位置を探索する過程と、（２）予め設定された最大アグリゲーションレベル範囲内で挿入ノードの先祖ノードの有無を決定する過程と、（３）フォーワーディングテーブルに先祖ノードに対応するフォーワーディング情報が存在し、挿入ノード及び先祖ノードのソース領域が同一であると、該先祖ノードが存在する挿入ノードの情報をフォーワーディングテーブルにアップデートしない過程と、（４）先祖ノードが存在しない場合、最大アグリゲーションレベル範囲内でアグリゲーションレベルを再設定し、該再設定されたアグリゲーションレベルに挿入ノードを代表する仮想ノードを挿入する過程と、（５）挿入されたルーティング情報を生成したソース領域を確認し、該ルーティング情報のソース領域が、仮想領域である場合はフォーワーディングテーブルに仮想ノードのフォーワーディング情報を挿入し、ローカル領域である場合はフォーワーディングテーブルに挿入ノードのフォーワーディング情報を挿入することによって、フォーワーディング情報を挿入する過程と、を含むことを特徴とする分散構造ルータにおけるフォーワーディング情報管理方法を提案する。
【００１６】
この方法は、新しいルーティング情報に対応する挿入ノードがアグリゲーションツリーに挿入される位置を検出して、該挿入ノードの位置に仮想ノードが存在する場合、当該挿入ノードに対応するフォーワーディング情報を挿入した後、フォーワーディングテーブルから仮想ノードに対応するフォーワーディング情報を削除する過程をさらに含むことができる。また、新しいルーティング情報に対応する挿入ノードがアグリゲーションツリーに挿入される位置を検出して、該挿入ノードの位置に仮想ノードが存在し、該仮想ノードの左／右サブツリーが存在する場合、当該挿入ノードに対応するフォーワーディング情報を挿入した後、左／右サブツリーノードを再挿入し、フォーワーディングテーブルから仮想ノードに対応するフォーワーディング情報を削除する過程をさらに含むことができる。さらに、先祖ノードの有無を決定して、挿入ノードの先祖ノードが最大アグリゲーションレベル範囲内に存在する場合、該挿入ノードの子孫ノードを探索する過程と、挿入ノードの子孫ノードが存在する場合、挿入ノードと子孫ノードに対するフォーワーディング情報のプレフィックスの差によってアグリゲーションレベルを再設定し、挿入ノードの子孫ノードが存在しない場合、挿入ノードの先祖ノードのレベルによってアグリゲーションレベルを再設定する過程と、再設定されたアグリゲーションレベルが０である場合、フォーワーディングテーブルに挿入ノードに対応するフォーワーディング情報を挿入する過程と、再設定されたアグリゲーションレベルが０より大きい場合、フォーワーディングテーブルに挿入ノードを代表する仮想ノードを挿入する過程と、挿入されたルーティング情報のソース領域を確認し、該ルーティング情報のソース領域が、仮想領域である場合はフォーワーディングテーブルに仮想ノードに対応するフォーワーディング情報を挿入し、ローカル領域である場合はフォーワーディングテーブルに挿入ノードに対応するフォーワーディング情報を挿入する過程と、を含むようにしてもよい。
【００１７】
また、先祖ノードが存在しない場合、最大アグリゲーションレベル範囲内でアグリゲーションレベルを再設定し、該再設定されたアグリゲーションレベルに挿入ノードを代表する仮想ノードを挿入する過程は、挿入ノードの先祖ノードが存在するか否かを判断するための探索レベル範囲を設定する過程と、挿入ノードの先祖ノードが探索レベル範囲内に存在する場合、最大アグリゲーションレベル範囲内に挿入ノードを代表する仮想ノードの子孫ノードが存在するか否かを判断する過程と、最大アグリゲーションレベル範囲内に挿入ノードを代表する仮想ノードの子孫ノードが存在する場合、該仮想ノードの子孫ノードのプレフィックスと挿入ノードのプレフィックスとの差によってアグリゲーションレベルを再設定する過程と、再設定されたアグリゲーションレベルに挿入ノードの仮想ノードを挿入する過程と、を含むことができる。
【００１８】
本発明によれば、さらに、ルーティングテーブルからルーティング情報が削除される場合、削除されたルーティング情報に対応する削除ノードをアグリゲーションツリーで探索する過程と、削除ノードに対応するフォーワーディング情報がフォーワーディングテーブルに存在する場合、予め設定された最大アグリゲーションレベル範囲内で削除ノードの子孫ノードを探索する過程と、予め設定された最大アグリゲーションレベルより低いアグリゲーションレベルに削除ノードの子孫ノードが存在する場合、該子孫ノードを仮想ノードの新しいソースノードとして変更し、予め設定された最大アグリゲーションレベルより低いアグリゲーションレベルに削除ノードの子孫ノードが存在しない場合、フォーワーディングテーブルから削除ノードに対応するフォーワーディング情報を削除する過程と、を含むことを特徴とする分散構造ルータにおけるフォーワーディング情報管理方法を提案する。この方法において、削除ノードが仮想ノードを生成したソースノードである場合、その仮想ノードに対応するフォーワーディング情報によって削除ノードに対応するフォーワーディング情報を変更する過程をさらに含むことができる。
【００１９】
本発明によれば、この他に、分散構造ルータにおいて、分散構造ルータ内でフォーワーディング情報に関する複数のルーティングプロトコルを含むスイッチングモジュールと、ローカル領域を含むソース領域に対応するサービスネットワークのそれぞれに配置された複数のルーティングノードと、を含み、その複数のルーティングノードは、スイッチングモジュールを通じて仮想領域を含むソース領域に連結され、収集されたルーティング情報を管理するルーティングテーブル及びそのルーティングテーブルによって生成されたアグリゲーションツリーを実時間で共有することを特徴とする。そして、ルーティングテーブルに新しいルーティング情報が挿入されると、ルーティングノードは、アグリゲーションツリーで新しいルーティング情報に対応する挿入ノードが追加される位置を識別する過程と、挿入ノードの先祖ノードを識別するために、最大アグリゲーションレベル範囲内でアグリゲーションツリーを探索する過程と、この探索過程で先祖ノードが識別され、挿入ノードと先祖ノードが同一のソース領域から生成された場合、該挿入ノードに対応するフォーワーディング情報をフォーワーディングテーブルにアップデートしない過程と、前記探索過程で、先祖ノードが識別されない場合、最大アグリゲーションレベル範囲内でアグリゲーションレベルを再設定し、再設定されたアグリゲーションレベルに挿入ノードを代表する仮想ノードを挿入する過程と、新しいルーティング情報のソース領域を確認する過程と、新しいルーティング情報のソース領域が仮想領域である場合は、仮想ノードに対応するフォーワーディング情報を挿入する過程と、新しいルーティング情報のソース領域がローカル領域である場合は、挿入ノードに対応するフォーワーディング情報を挿入する過程と、を実行することを特徴とする。
【発明の効果】
【００２０】
本発明は、分散構造ルータの全てのノードで収集されるルーティング情報を各ノードが実時間で共有し、このルーティング情報を利用してフォーワーディング情報を動的に管理することによって、ルーティング情報を共有するための各ノード間のパケットフォーワーディング過程を省略することができるという効果がある。また、そのルーティング情報をフォーワーディングテーブルに選択的にアップデートすることによって、ノード別のフォーワーディングテーブルを効率的に管理することができるという利点がる。さらに、本発明は、２進アグリゲーションツリー(aggregation tree)を利用して各ノードのフォーワーディング情報を管理し、ルーティング情報に対応するノード情報をアグリゲーションする仮想ノードのレベルを可変的に設定することによって分散構造ルータのノード別のフォーワーディングテーブルのサイズを低減することができるという利点がある。
【発明を実施するための最良の形態】
【００２１】
以下、本発明の好適な実施形態について添付図を参照しつつ詳細に説明する。下記の説明において、本発明の要旨のみを明確にする目的で、関連した公知機能又は構成に関する具体的な説明は省略する。
【００２２】
図１は、分散構造ルータ１００に対する例示図である。特に、図１の分散構造ルータは、ギャラクシーＩＰルータ(Galaxy IP Router)の例を示す。
【００２３】
図１を参照すると、分散構造ルータ１００は、スイッチングモジュール(switching module: ＳＷＭ)１５０によって互いに連結される複数のルーティングノード(Routing Nodes: ＲＮ)１１０，１２０，１３０，１４０を含む。ＲＮ１１０，１２０，１３０，１４０のそれぞれは、入出力プロセッサ(Input Output Processor: ＩＯＰ)１１１を備え、ＩＯＰ１１１は、２つの物理的な媒体(Physical Medium Device: ＰＭＤ)ＰＭＤ−Ａ１１２及びＰＭＤ−Ｂ１１３からパケットを受信するように設計されている。
【００２４】
ＲＮ１１０，１２０，１３０，１４０は、それぞれ対応するサブネットワーク(sub-network)を支援するための固有のルーティングテーブル(own routing table)及びルーティング経路を処理するための固有のプロセッサ(own processors)を有する。ＲＮ１１０，１２０，１３０，１４０は、独自的なルーティングプロトコルを実行し、独自的なフォーワーディング(forwarding)を遂行する。しかしながら、ＲＮ１１０，１２０，１３０，１４０は、使用者の観点から１つのルータとして認識される。従って、ＲＮ１１０，１２０，１３０，１４０は、ＳＷＭ１５０を通じて連結された他のＲＮ１１０，１２０，１３０，１４０のルーティングテーブルを全体的に管理する。ＲＮ１１０，１２０，１３０，１４０のいずれか１つに連結された物理的なサブネットワークをローカル領域(local area)Ｂと称し、ＳＷＭ１５０を通じてＲＮ１１０，１２０，１３０，１４０間が連結されて形成されたネットワークを仮想領域(virtual area)Ａと称する。
【００２５】
図２は、分散構造ルータ１００の通常的なプロセス構造を示す図であり、特に、分散構造ルータ１００が４つのＲＮを有する場合、各ＲＮのＩＯＰ(IOP#1、IOP#2、IOP#3、IOP#4)１０，２０，３０，４０によって遂行されるプロセス構造及びＳＷＭ５０とＩＯＰ１０，２０，３０，４０との間の連結状態を示す。
【００２６】
図２を参照すると、ＩＯＰ＃１(１０)は、複数のルーティングプロトコル(ripd(11)、ospfd(12)、bgpd(13)、isisd(14))、ＩＯＰ管理プロセッサ(Galaxy Loosely Unified Environment Daemon: GLUED)１５、ルーティングテーブル１６、及びフォーワーディングテーブル１７を含む。
【００２７】
ルーティングプロトコル１１，１２，１３，１４は、それぞれ固有の収集基準によってルーティング情報を収集する。ルーティングテーブル１６は、ルーティング情報を貯蔵し、フォーワーディングテーブル１７は、ルーティングテーブル１６に貯蔵されたルーティング情報を計算して得られたフォーワーディング情報を貯蔵する。
【００２８】
ＩＯＰ管理プロセッサ(GLUED)１５は、ルーティングプロトコル１１，１２，１３，１４で収集されたルーティング情報をルーティングテーブル１６に貯蔵し、このルーティング情報を計算して得られたフォーワーディング情報をフォーワーディングテーブル１７に貯蔵し、ルーティングテーブル１６及びフォーワーディングテーブル１７を管理する。さらに、ＩＯＰ管理プロセッサ１５は、ルーティングテーブル１６によって貯蔵されている収集されたルーティング情報をＳＷＭ５０を通じてＩＯＰ２０，３０，４０に通知する。
【００２９】
ＩＯＰ＃１(１０)は、ルーティングプロトコル１１，１２，１３，１４、ＩＯＰ管理プロセッサ１５及びルーティングテーブル１６を含むシステムプロセッサ(system processor)領域６０とフォーワーディングテーブル１７を含むネットワークプロセッサ(network processor)領域７０とに区分される。システムプロセッサ領域６０は、ルーティング情報の収集、ルーティング経路の計算によるフォーワーディングテーブル管理及び他のＩＯＰ２０，３０，４０のルーティングテーブルの共有のための一連の処理過程を遂行し、ネットワークプロセッサ領域７０は、フォーワーディングテーブル１７に貯蔵された情報によってローカル領域に連結されたネットワーク装備間のフォーワーディングを遂行する。従って、分散構造ルータは、大容量のデータをより迅速に処理することができる。
【００３０】
図１及び図２に示すように、分散構造ルータ１００において大容量のデータをより迅速に処理するためには、各ＲＮ１０，２０，３０，４０が他のＲＮ１０，２０，３０，４０とフォーワーディングテーブルを共有すべきである。このために、従来の分散構造ルータ１００においては、各ＲＮ１０，２０，３０，４０がフォーワーディングテーブルをＳＷＭ１５０を通じて他のＲＮ１０，２０，３０，４０と相互伝送することで、各ＲＮが全てのＲＮ１０，２０，３０，４０のフォーワーディングテーブルを全体的に管理することができるようにしていた。例えば、分散構造ルータ１００が１０個のＲＮを有し、それぞれのＲＮが固有の１０,０００個のフォーワーディングエントリ(forwarding entries)を有すると仮定する場合、各ＲＮは、１００,０００(＝１０,０００(ＲＮ当りのフォーワーディングエントリ)×１０(ＲＮ))のフォーワーディングエントリを管理しなければならない。従って、従来の分散構造ルータ１００は、１００,０００以上のフォーワーディングエントリを含むフォーワーディングテーブルを貯蔵するために、大容量の記憶空間を必要とし、パケットフォーワーディング伝送に不要のオーバーヘッドが発生するという問題点があった。
【００３１】
図３は、本発明による分散構造ルータのプロセス構造の一例を示す図である。一般的に、分散構造ルータは、複数のＩＯＰ(Input Output Processor)を含み、１つのスイッチングモジュール(ＳＷＭ)によってＩＯＰ間に情報を交換する。図３に示す構成は、他のルーティングノード２２０(IOP#2)，２３０(IOP#3)等は簡略化のために省き、１つのＩＯＰ(IOP#1)２１０及びＳＷＭ２５０のみを示した構造である。
【００３２】
図３を参照すると、本発明による分散構造ルータのプロセス構造は、ＩＯＰ＃１(２１０)のシステムプロセッサ領域２６０にアグリゲーションツリー(aggregation tree)２１８を含むことができる。アグリゲーションツリー２１８は、本出願の出願人による大韓民国特許出願(出願番号２００２−７５７０１)に説明されているように、分散構造ルータの各ＩＯＰによって管理されるフォーワーディング情報及びルーティング情報に対応するノード、及びフォーワーディング情報及びルーティング情報をアグリゲーションする仮想ノード(delegation node)を含む。
【００３３】
ＳＷＭ２５０は、ルーティングプロトコル(ripd(251)、ospfd(252)、bgpd(253)、Dglued(254))を含む。ルーティングプロトコル(ripd(251)、ospfd(252)、bgpd(253)、Dglued(254))は、対応するＩＯＰ内のルーティングプロトコル(ripd(211)、ospfd(212)、bgpd(213)、glued(214))と内部的に連結(internal peer connection)される。
【００３４】
従って、ＳＷＭ２５０は、このような連結(internal peer connection)を通じて各ＩＯＰのルーティングプロトコル別に収集されたルーティング情報を実時間で共有し、ＩＯＰのルーティング情報を他のＩＯＰに提供する。結果的に、本発明による分散構造ルータにおいて、ルーティングプロトコル間の連結(internal peer connection)によって全てのＩＯＰが同一のルーティング情報を共有することができる。
【００３５】
図３の例において、ＩＯＰ＃１(２１０)及びＳＷＭ２５０に含まれたＲＴＭ(Routing Table Manage)モジュール２１５，２５５は、各ルーティングプロトコル２１１，２１２，２１３，２１４及び２５１，２５２，２５３，２５４から得られたルーティング情報を全体的に管理し、ルーティング情報の優先順位を管理する。
【００３６】
図４Ａは、本発明によってフォーワーディング情報を管理するために生成されたアグリゲーションツリーの各ノード別の管理データ構造を示す。図４Ａを参照すると、本発明によってフォーワーディング情報を管理するためのアグリゲーションツリーの各ノードは、該当フォーワーディング情報がフォーワーディングされるアドレスであるＰＲＥＦＩＸ、ＰＲＥＦＩＸの長さを示すＬＥＮＧＴＨ、ノードのアグリゲーションレベルを示すＡＧＧＲＥＧＡＴＩＯＮ＿ＬＥＶＥＬ、ノードが仮想ノードである場合、該ノードの属するソースノード(例えば、仮想ノードを生成したノード)情報を示すＩＮＤＥＸ、フォーワーディング情報のタイプを示すＴＹＰＥ、フォーワーディング情報を生成したＲＮを示すＳＯＵＲＣＥ ＩＯＰ、フォーワーディング情報がローカルフォーワーディングテーブルに貯蔵されているか否かを示すＦＴ ＦＬＡＧ、及び一般の２進ツリーのリンク情報(例えば、親ノード(parent node)を識別するためのインジケータＰＡＲＥＮＴ、左側サブツリーを示すデータフィールドであるＬ＿ＳＵＢＴＲＥＥ、右側サブツリーを示すデータフィールドであるＲ＿ＳＵＢＴＲＥＥ)を含む。ノード別の管理データは、アグリゲーションツリーがアップデートされる場合に共にアップデートして管理する。
【００３７】
アグリゲーションレベルは、運営者によってデフォルトレベル(つまり、最大レベル)に設定され、ルータの運営によってデフォルトレベル内で可変する。つまり、ネットワーク状態によってアグリゲーションレベルを動的に再設定することができるので、再設定されたダイナミックレベル(dynamic level)内でルーティング情報をアグリゲーションした仮想ノードを生成することができる。
【００３８】
ＩＮＤＥＸは、ノードが仮想ノードである場合、該仮想ノードを生成したソースノードを示す。ＩＮＤＥＸは、仮想ノードからソースノードを探すことのできる情報を提供する。例えば、仮想ノードの左側子ノード(left child node)の右側子ノードから仮想ノードを生成した場合、一般的に、左側子ノードは‘０’値を有し、右側子ノードは‘１’値を有するので、仮想ノードのＩＮＤＥＸは‘０１’になる。
【００３９】
ＴＹＰＥは、ＩＯＰ２１０内で該当フォーワーディング情報を生成したルーティングプロトコルの種類(例えば、ＢＧＰ、ＳＤＰＦ、ＲＩＰ)を示す。仮想ノードの場合、ＴＹＰＥは、実際フォーワーディング情報と区別するための別途のタイプ(Delegation)を指定し、他のタイプ(例えば、ＢＧＰ、ＳＤＰＦ、ＲＩＰ)のフォーワーディング情報より低い優先順位を有する。仮想ノードは仮想のフォーワーディング情報であるので、ルーティングプロトコルによって生成される実際のフォーワーディング情報に高い優先順位が与えられる。
【００４０】
フォーワーディング情報のタイプを設定するために、ルーティングノードは、フォーワーディング情報のソース領域を確認する。フォーワーディング情報がローカル領域から生成された場合、ＲＮは、フォーワーディング情報を生成したプロセッサの種類によってフォーワーディング情報のタイプを設定する。フォーワーディング情報が仮想領域から生成された場合、ＲＮは、仮想のタイプを設定してフォーワーディング情報が仮想であることを示す。従って、ＲＮは、フォーワーディング情報のＰＲＥＦＩＸを分析し、その分析結果、ＰＲＥＦＩＸが私設ＩＰ(internet protocol)アドレスである場合、対応するフォーワーディング情報が仮想領域から伝達されていると判断する。そうでない場合は、対応するフォーワーディング情報がローカル領域から生成されていると判断する。
【００４１】
私設（プライベート）ＩＰアドレスは、所定のローカルネットワークで使用できるアドレスを示し、ローカルネットワーク内に連結されたノードを識別するためのアドレス情報である。従って、私設ＩＰアドレスは、ローカルネットワークの外部では使用することができない。一般的に、分散構造ルータは、分散構造ルータに含まれたＲＮを識別するために、各ＲＮに私設ＩＰアドレスを与える。従って、本発明においては、各ＲＮの私設ＩＰアドレスを利用してフォーワーディング情報のソース領域を確認する。
【００４２】
図４Ｂは、本発明によってフォーワーディング情報を管理するために生成されたアグリゲーションツリー構造の例を示す図である。このアグリゲーションツリーは、２進ツリーである。ルーティング情報の挿入及び削除によるアグリゲーションツリーのアップデートは、図９Ａ、図９Ｂ、図１０Ａ及び図１０Ｂを参照して後で具体的に説明する。
【００４３】
本発明において、本発明の性能検証のために使用されるリアル(real)ＢＧＰ(border gateway protocol)コアルーティングテーブルのルーティングエントリは、図４Ｃのようにプレフィックス(prefix)長さ(length)１５〜２４の地点に集中的に分布する。従って、プレフィックス長さ分布の分析は、仮想ノードのアグリゲーションレベルをデフォルトレベルに制限することによって、動的にフォーワーディング情報のアグリゲーション及び削除(retrieve)時のアルゴリズムオーバーヘッドを低減することができる。
【００４４】
本発明によると、図１に示すギャラクシーＩＰルータがマルチ−ラック(multi-rack)に拡張される時、各ラックに存在するＳＷＭのＲＴＭ(routing table manager)２５５は、自分が管理する全てのＩＯＰのルーティングテーブルを管理し、これは、ＩＯＰ間のフォーワーディング情報アグリゲーションがラック間のフォーワーディング情報アグリゲーションに容易に拡張されるようにする。
【００４５】
図５は、新しく挿入されたルーティング情報を管理する本発明の方法を例示したフローチャートである。
【００４６】
図５を参照すると、図３に示すような本発明の分散構造ルータにおいて、ＲＮに新しいルーティング情報が追加されると(段階１１１０)、ＲＮは、追加されたルーティング情報に対応する挿入ノード(insertion node)の位置を探索する(段階１１２０)。つまり、追加されるルーティング情報のプレフィックス長さと同一の長さを有するノードを探索するまで、予め設定されたアグリゲーションツリーの最上位ノード(root node)から２進探索(binary search)を反復遂行する。挿入ノードの位置が探索されると、ＲＮは、挿入ノードの位置に仮想ノードが存在するか否かを確認する(段階１１３０)。段階１１３０の確認結果、挿入ノードの位置に仮想ノードが存在しないと確認される場合、つまり、該当位置が空いている場合、追加されるルーティング情報に対応する挿入ノードを該当位置に挿入する(段階２０００)。
【００４７】
段階１１３０の確認結果、挿入ノードの位置に仮想ノードが存在する場合、該仮想ノードに対応するフォーワーディング情報を削除して挿入ノードの位置を確保し(段階１６００)、挿入ノードを挿入する(段階２０００)。
【００４８】
このために、仮想ノードの左／右サブツリー(left/right subtree)が存在するか否かを確認する(段階１４００)。仮想ノードの左／右サブツリーが存在しない場合、ＲＮは、フォーワーディングテーブルから仮想ノードに対応するフォーワーディング情報を削除する(段階１７００)。仮想ノードの左／右サブツリーが存在する場合、この仮想ノードは、左／右サブツリーを構成するノードを代表するノードであるので、当該仮想ノードに対応するフォーワーディング情報を削除する(段階１６００)前に、その左／右サブツリーを構成するノードを再挿入すべできる(段階１５００)。左／右サブツリーを構成するノードを再挿入するためには、図５の全体挿入過程を再び遂行する。これを通常的に循環関数(recursive function)と称する。つまり、仮想ノードの左／右サブツリーが存在すると判断された場合は、段階１５００の再挿入過程を遂行した後、フォーワーディングテーブルから仮想ノードに対応するフォーワーディング情報を削除する(段階１６００)。
【００４９】
前述したように、挿入ノードの位置に仮想ノードが存在する場合は、段階１４００〜段階１７００を通じて仮想ノードに対応するフォーワーディング情報を挿入ノードと取り替える(段階２０００)。
【００５０】
図６Ａないし図６Ｃは、段階２０００を具体的に示す。
【００５１】
図６Ａを参照すると、ＲＮは、挿入ノードに対応するフォーワーディング情報を挿入する前に、挿入ノードを代表する仮想ノードを挿入するための位置を検出するために、アグリゲーションできる最大レベル(defaultlevel)範囲内で挿入ノードの先祖ノード(ancestor node)を探す(段階２００１)。
【００５２】
段階２００１の結果、挿入ノードの先祖ノードが検出されなかった場合（段階２００３）、挿入ノードのデフォルト探索レベル(default search level)を設定する(段階２００５)。デフォルト探索レベルは、数式１によって算出される。
【００５３】
［数１］
searchlevel = defaultlevel＊２−１
【００５４】
ＲＮは、挿入ノードを代表する仮想ノード挿入時に発生するエラーを低減するために、探索レベル(search level)内に挿入ノードの先祖ノードが存在するが否かを確認する(段階２００７)。
【００５５】
段階２００７の確認結果、探索レベル内に挿入ノードの先祖ノードが存在しない場合、デフォルトレベルに挿入ノードを代表する仮想ノードを挿入する(段階２１７０)。該当探索レベルに挿入ノードの先祖ノードが存在する場合、仮想ノードによって代表される子孫ノードの有無を確認するために、探索レベルに対するデフォルトレベル内で仮想ノードの子孫ノード(descendant node)を探索する(段階２００９)。
【００５６】
デフォルト探索レベル内に挿入ノードの子孫ノードが存在しない場合（段階２１１０）、段階２１７０で、デフォルト探索レベルに挿入ノードの仮想ノードを挿入する。しかしながら、挿入ノードの子孫ノードが存在する場合は、アグリゲーションできるレベルをダイナミック（動的）レベルに再設定し(段階２１３０)、ダイナミックレベルに仮想ノードを挿入する(段階２１５０)。ここで、アグリゲーションレベルを再設定する方法は、数式２に例示された方法を利用することが望ましい。
【００５７】
［数２］
dynamiclevel = GetNodePrefixLength(insertion node)
−GetDistPrefixLength(insertion node、desendant node)
【００５８】
ここで、‘GetNodePrefixLength’は、挿入ノードのプレフィックス長さを計算する関数であり、‘GetDistPrefixLength’は、挿入ノードとその子孫ノードとのプレフィックス長さの差が発生する位置を計算する関数である。
【００５９】
例えば、挿入ノードのプレフィックス長さが１８であり、挿入ノードとその子孫ノードとのプレフィックス長さの差が発生する位置が１９である場合、数式２によってダイナミックレベルは１になる(１＝１９−１８)。従って、挿入ノードの仮想ノードは、挿入ノードのレベルより１つだけ高い上位レベルに生成される。
【００６０】
段階２００５ないし段階２１７０によってアグリゲーションツリーの所定の位置に挿入ノードを代表する仮想ノードを挿入した後、該挿入されたルーティング情報をフォーワーディングテーブルに貯蔵するかどうかを判断するために、ルーティング情報のソース領域を確認する(段階２１９０)。確認結果、ルーティング情報のソース領域が仮想領域(virtual aera)である場合、フォーワーディングテーブルにルーティング情報を代表する仮想ノード情報を挿入する(段階２２１０)。ルーティング情報のソース領域がローカル領域である場合は、フォーワーディングテーブルにルーティング情報に対応する挿入ノード情報を挿入する(段階２２３０)。
【００６１】
図６Ｂは、段階２００１の結果、挿入ノードの先祖ノードが存在する場合に対する処理過程を示す。
【００６２】
図６Ａ、図６Ｂ及び図６Ｃを参照すると、挿入ノードの先祖ノードが存在すると、所定のアルゴリズム(Select Delegation Level)(図６Ｃに示す)によって仮想ノードを挿入するダイナミックレベル(Delegation Lvel)を選択する(段階２３００)。アルゴリズム(Select Delegation Level)は、挿入ノードの先祖ノードが予めフォーワーディングテーブルにアップデートされ、かつ、挿入ノード及びその先祖ノードが同一のＩＯＰによって生成された場合、フォーワーディングテーブルにアップデートする過程を省略するために、ダイナミックレベルを仮想の値(−１)に設定する(図６Ｃの段階２３５０ないし段階２３７０)。
【００６３】
ダイナミックレベル(Delegation Level)は、０と比較される(段階２４１０)。
【００６４】
ダイナミックレベル(Delegation Level)が０であると、挿入ノードを代表する仮想ノードを挿入することができず、フォーワーディングテーブルに挿入ノード情報を直接挿入する(段階２５１０)。
【００６５】
ダイナミックレベル(Delegation Level)が０より小さい場合は、ルーティング情報のソース領域をもう一度確認して(段階Ｓ２５３)、ルーティング情報のソース領域がローカル領域である場合のみに、フォーワーディングテーブルに挿入ノード情報をアップデートする(段階２５５０)。ルーティング情報のソース領域が仮想領域である場合、ＲＮは、フォーワーディングテーブルにアップデートする過程を省略して次の段階に進行する。この場合、アグリゲーションプロセスは、フォーワーディングテーブルによるオーバーヘッドを低減させる効果がある。
【００６６】
ダイナミックレベル(Delegation Level)が０より大きい場合、ＲＮは、ダイナミックレベルに挿入ノードの仮想ノードを挿入する(段階２４３０)。ＲＮは、挿入されたルーティング情報のソース領域を確認して(段階２４５０)、ルーティング情報のソース領域が仮想領域である場合は、フォーワーディングテーブルに仮想ノード情報を挿入し(段階２４７０)、ルーティング情報のソース領域がローカル領域である場合は、フォーワーディングテーブルに挿入ノード情報を挿入する(段階２４９０)。
【００６７】
図６Ｃは、段階２３００のアルゴリズムをより詳細に示す。図６Ｃを参照すると、仮想ノードを挿入するダイナミックレベルを選択するために、挿入ノードの子孫ノードの有無の検出(段階２３１０)によってアグリゲーションレベルを別に再設定する。まず、挿入ノードの子孫ノードを探索して(段階２３２０)、挿入ノードの子孫ノードが存在すると、数式２によってダイナミックレベル、つまり、アグリゲーションレベルを再設定する(段階２３３０)。つまり、挿入ノードのプレフィックス長さ及び挿入ノードとその子孫ノードとのプレフィックスの差が発生する位置情報によってアグリゲーションレベルを再設定する。一方、段階２３２０で挿入ノードの子孫ノードが存在しない場合は、挿入ノードの先祖ノードのレベルをアグリゲーションレベルに設定する(段階２３４０)。
【００６８】
そして、挿入ノードの先祖ノードが予めフォーワーディングテーブルにアップデートされ(段階２３５０)、挿入ノード及びその先祖ノードが同一のＩＯＰから生成された場合(段階２３６０)、フォーワーディングテーブルアップデート過程を省略するために、ダイナミックレベルを仮想の値(−１)に設定する(段階２３７０)。
【００６９】
図７は、削除されたルーティング情報を管理する本発明の方法を例示するフローチャートである。
【００７０】
図７を参照すると、１つのＲＮのルーティングテーブルからルーティング情報が削除されると(段階５１００)、ＲＮは、削除されたルーティング情報に対応するノード(以下、削除ノード(deletion node)と称する)の位置を探索する(段階５２００)。この段階は、ルーティングテーブルに新しいルーティング情報が挿入された場合にその挿入ノードの位置を探索する過程と類似している。つまり、削除されるルーティング情報のプレフィックス長さと同一の長さを有するノードを探索するまで、予め設定されたアグリゲーションツリーの最上位ノード(root node)から２進探索(binary search)を反復遂行する。
【００７１】
削除ノードの位置が探索されると、ＲＮは、削除ノードが仮想ノードを生成したソースノードであるか否かを確認し(段階５３００)、削除ノードがソースノードである場合は、仮想ノードを削除することによって削除ノードの削除の効果を得るために、仮想ノードに対応するフォーワーディング情報を削除ノードのフォーワーディング情報に変更する(段階５４００)。
【００７２】
ＲＮは、削除ノードがフォーワーディングテーブルにアップデートされているか否かを確認し(段階５５００)、削除ノードがフォーワーディングテーブルにアップデートされていない場合は、削除過程を終了する。一方、削除ノードがフォーワーディングテーブルにアップデートされている場合は、デフォルトレベル範囲内で削除ノードの子孫ノードを探索し(段階５６００)、削除ノードの子孫ノードが存在する場合は、子孫ノードを仮想ノードの新しいソースノードに変更する(段階５８００)。これは、１つの仮想ノードが複数の子孫ノードを代表している場合、仮想ノードのソースノードの削除によって残りの子孫ノードを代表する仮想ノードの損失を防止するためである。
【００７３】
段階５６００及び段階５７００の結果、前記範囲内に削除ノードの子孫ノードが存在しない場合、ＲＮは、フォーワーディングテーブルから削除ノードに対応するフォーワーディング情報を削除する(段階５９００)。
【００７４】
図８Ａないし図８Ｇは、フォーワーディング情報を動的に管理する本発明の方法に対するアルゴリズムの例を示す。
【００７５】
図８Ａは、図５の処理過程を疑似コード(pseudo code)で表現し、図８Ｂは、図５の段階１２００及び図７の段階５２００を疑似コードで表現し、図８Ｃは、図６Ａの処理過程を疑似コードで表現し、図８Ｄは、図６Ａの段階２１５０及び段階２１７０で仮想ノードを挿入する過程を疑似コードで表現し、図８Ｅは、図６Ｂの処理過程を疑似コードで表現し、図８Ｆは、図６Ｃの処理過程を疑似コードで表現し、図８Ｇは、図７の処理過程を疑似コードで表現する。図８Ａないし図８Ｇに対する具体的な説明は、図５ないし図７を参照した説明部分に記載されているので、その具体的な説明は省略する。図８Ａないし図８Ｇに示すアルゴリズム処理方式は１つの実施例に過ぎず、このようなアルゴリズムを多様に変更して実行できることは自明である。
【００７６】
図９Ａないし図１０Ｂは、本発明によるフォーワーディング情報管理方法を説明する図であり、デフォルトレベルが２である場合に挿入されたフォーワーディング情報及び削除されたフォーワーディング情報を管理する方法を説明する。図９Ａ及び図９Ｂは、挿入されたフォーワーディング情報を管理する方法を説明する図であり、図１０Ａ及び図１０Ｂは、削除されたフォーワーディング情報を管理する方法を説明する図である。
【００７７】
図９Ａないし図１０Ｂのアグリゲーションツリーにおいて、ＰＲＥＦＩＸは、ノードに対応するフォーワーディング情報がフォーワーディングされるアドレスを示し、ノード識別の機能を有する。ＳＯＵＲＣＥ ＩＯＰは、挿入ノードを生成したルーティングノードのソースＩＯＰを示し、ＦＥは、フォーワーディング情報がフォーワーディングテーブルに貯蔵されているか否かを示す。従って、ＦＥのマーキング部分は、フォーワーディング情報がフォーワーディングテーブルに存在することを示す。ＩＮＤＥＸは、 フォーワーディングされるノードが仮想ノードである場合、仮想ノードを生成したソースノードを示し、ＬＥＶＥＬは、フォーワーディングされるノードのアグリゲーションレベルを示す。
【００７８】
図９Ａを参照すると、何の情報も登録されていない状態で、ＩＯＰ＃１(２１０)にフォーワーディングアドレスが３である新しいルーティング情報が挿入された場合、ＩＯＰ＃１(２１０)の制御部は、ルーティング情報をＩＯＰ＃１(２１０)のアグリゲーションツリーに挿入する。つまり、ノード３をアグリゲーションツリーに挿入する。この挿入ノードのプレフィックスが２であるので、プレフィックスが０である仮想ノードを３のプレフィックスを有する挿入ノードより２レベル上位に追加する。プレフィックスが０である仮想ノードのソースノードが挿入ノード３(つまり、プレフィックスが３である挿入ノード)であるので、仮想ノードのＩＮＤＥＤＸは“００”になる。挿入ノード３及びプレフィックスが０であるこの仮想ノードは、同一のソース(つまり、ルーティングノードＩＯＰ＃１(２１０))を有するので、フォーワーディングテーブルには挿入ノード３に関する情報が貯蔵される。
【００７９】
一方、本発明の分散構造ルータにおいて、他のノードＩＯＰ＃２、ＩＯＰ＃３、ＩＯＰ＃４は、ＩＯＰ＃１(２１０)のルーティング情報(例えば、アグリゲーションツリー２１８)を共有し、各ノードは、他のノードと自分のルーティングテーブルに貯蔵されたルーティング情報を共有する。図９Ａの例において、ＩＯＰ＃２(２２０)は、ＩＯＰ＃１(２１０)のルーティングテーブル２１６に貯蔵されたルーティング情報を共有する。これは、以下の例にも同一に適用される。
【００８０】
図９Ａを参照すると、ＩＯＰ＃２(２２０)のアグリゲーションツリーはＩＯＰ＃１(２１０)のアグリゲーションツリーと同一であり、フォーワーディングテーブル情報のみが異なる。つまり、ＩＯＰ＃１(２１０)は、ローカル領域に新しいルーティング情報が挿入されたので、挿入ノード３の情報をフォーワーディングテーブル２１７に貯蔵し、ＩＯＰ＃２(２２０)は、仮想領域に新しいルーティング情報が挿入されたので、仮想ノード０の情報をフォーワーディングテーブルに貯蔵する。
【００８１】
図９Ｂは、仮想ノード０がＩＯＰ＃２(２２０)のフォーワーディングテーブルに予め貯蔵された状態で、ＩＯＰ＃２(２２０)のローカル領域にプレフィックスが７であるルーティング情報が挿入された場合の例を示す。
【００８２】
ＩＯＰ＃２(２２０)の制御部は、挿入ノード７の位置を探索した後、デフォルトレベル２によって挿入ノード７の先祖ノードを探索する。次に、ＩＯＰ＃２(２２０)の制御部は、ノード1を挿入ノード７の先祖ノードとして検出する。ノード1は、ＩＯＰ＃１(２１０)の挿入ノード３を検出するために経る先祖ノードである。従って、ノード７に対する仮想ノードは、先祖ノード１でない、挿入ノード７の仮想ノードとして機能するノード４の位置に挿入される。前述したように、本発明においては、アグリゲーションレベルが可変的であり、可変的に再設定されたアグリゲーションレベルをダイナミックレベルと称する。
【００８３】
図９Ｂに示すように、ＩＯＰ＃１(２１０)のアグリゲーションツリー２１８に挿入ノード７及び先祖ノード４が両方とも追加され、ノード４及びノード７のソース領域が仮想領域であるので、ノード７の仮想ノード４をＩＯＰ＃１(２１０)のフォーワーディングテーブルにアップデートする。
【００８４】
一方、ＩＯＰ＃２(２２０)の制御部は、ローカル領域にノード７が挿入された場合であるので、挿入ノード７に関する情報をフォーワーディングテーブルにアップデートする。
【００８５】
以下、図１０Ａ及び図１０Ｂを参照して、本発明によるルーティング情報削除過程を説明する。
【００８６】
図１０Ａを参照すると、仮想ノード０は、ＩＯＰ＃１(２１０)のローカル領域において生成されたノード３、ノード４、ノード５及びノード６を代表している。ノード０のソースノードがノード３である場合、ルーティングノード２１０(ＩＯＰ＃１)のフォーワーディングテーブルにノード３、ノード４、ノード５及びノード６に関する情報がアップデートされ、ルーティングノード２２０(ＩＯＰ＃２)のフォーワーディングテーブルにはノード０のみがアップデートされる。
【００８７】
図１０Ｂは、図１０Ａに示すルーティングツリー２１０，２２０のアグリゲーションツリーから、仮想ノード０のソースノードであるノード３が削除された場合を示す。
【００８８】
本発明において、仮想ノードのソースノードが削除される場合、フォーワーディングテーブルから削除されたソースノードのフォーワーディング情報、つまり、削除ノードのフォーワーディング情報を削除し、仮想ノードのソースノードのみを変更し、仮想領域では何の変更も遂行しない。
【００８９】
図１０Ｂに示すように、仮想ノード０のソースノードであるノード３が削除された場合、ＩＯＰ＃１(２１０)の制御部は、仮想ノード０のソースノードをノード４に変更する。一方、ルーティングノード２２０(ＩＯＰ＃２)の制御部は、ルーティングノード２２０のフォーワーディングテーブルに仮想ノード０の情報のみが貯蔵されるので、ルーティングノード２２０のフォーワーディングテーブルに対して別途の作業を遂行する必要がない。
【００９０】
図１１Ａないし図１１Ｄは、本発明によるフォーワーディング情報の動的管理方法の効果を立証するためのテスト結果である。
【００９１】
本テスト結果を得るために、１つのＳＷＭ及び２つのＩＯＰを備えるギャラクシーシステム、及びhttp://www.telstra.net/ops/bgptable.htmlまたはhttp://www.bgp.protaro.netから提供されるコア(core)ＢＧＰルータのルーティングテーブルエントリを利用して、５３,０００個のルーティングエントリを挿入し、このルーティングエントリの一定比率をフラップ(flap)するテストを遂行する。
【００９２】
図１１Ａは、挿入されるエントリの順序が本発明の効果に影響を与えるか否かを測定するためのテスト結果を示す。１０回にかけて昇順で整列されたサンプルエントリの順序をランダムに変更しながら、６つのデフォルトレベルを適用し、サンプルエントリを挿入した結果を示す。図１１Ａを参照すると、フォーワーディングエントリ(forwarding entries)の個数は、６０〜１１０の範囲である。従って、本発明のアグリゲーション性能は、フォーワーディングエントリの挿入順序の影響をほとんど受けない。
【００９３】
図１１Ｂは、６つのデフォルトレベルを適用した場合のオーバーヘッド測定結果を示すグラフである。図１１Ａ及び図１１Ｂを参照すると、ルータの性能及びオーバーヘッドを考慮するとき、本発明は、デフォルトレベルが３以下である時に最も効果的であることが分かる。
【００９４】
図１１Ｃは、５３,０００のコアＢＧＰルーティングエントリの０％〜７０を削除するとき、フォーワーディングテーブルに残存するフォーワーディングエントリの個数を示すグラフである。図１１Ｃを参照すると、コアＢＧＰエントリを単純に挿入し、削除比率が０％である場合、約２６％〜７７％のフォーワーディングエントリが減少される。
【００９５】
図１１Ｄは、Agilent Router Testerを利用して実際インターネット環境の性能の測定結果を示すグラフである。Agilent Router Testerは、ネットワークトポロジー(topology)またはネットワークの影響範囲(reachability)が持続的に変化する動的のルーティング条件下でルータの性能を測定する。図１１Ｄは、ルータがルーティング情報の変化をフォーワーディングテーブルに反映する時間(convergence time)に焦点を合わせてテスト結果を示す。この“BGP4 flap convergence time”テストは、ネットワークトポロジーまたはネットワーク影響範囲の変化によって主ルータ(primary router)がドロップ(drop)された場合、主ルータを新しいルータに変更するための時間(traffic redirect convergence time)を測定する。当該テストは、３つのＲＮを使用して遂行される。３つのＲＮのうち２つは、ＲＮの後ろの同一のネットワークの影響範囲を通知し、残りの１つのＲＮは、通知されたネットワークにデータトラヒック(data traffic)を生成する。図１１Ｄに示す遂行時間(convergence time)測定結果から、フォーワーディングテーブルの修正の最小化のために仮想ノードの実際ソースノードを削除する時に仮想ノードのソースノードの情報のみを変更する時に、遂行時間(convergence time)が低減される。
【００９６】
以上、本発明を具体的な実施形態を参照して詳細に説明してきたが、本発明の範囲は前述の実施形態によって限られるべきではなく、本発明の範囲内で様々な変形が可能であるということは、当該技術分野における通常の知識を持つ者には明らかである。
【図面の簡単な説明】
【００９７】
【図１】分散構造ルータの例示図。
【図２】分散構造ルータの通常的なプロセス構造を示す図。
【図３】本発明による分散構造ルータのプロセス構造の一例を示す図。
【図４Ａ】本発明によってフォーワーディング情報を管理するために生成されたアグリゲーションツリーの各ノード別管理データ構造の例を示す図。
【図４Ｂ】本発明によってフォーワーディング情報を管理するために生成されたアグリゲーションツリー構造の例を示す図。
【図４Ｃ】プレフィックス長さ別のプレフィックス分布を示すグラフ。
【図５】追加されたルーティング情報を管理する本発明の方法を例示するフローチャート。
【図６Ａ】フォーワーディング情報を追加する本発明の過程を例示するフローチャート。
【図６Ｂ】フォーワーディング情報を追加する本発明の過程を例示するフローチャート。
【図６Ｃ】フォーワーディング情報を追加する本発明の過程を例示するフローチャート。
【図７】削除されたルーティング情報を管理する本発明の方法を例示するフローチャート。
【図８Ａ】フォーワーディング情報を動的に管理する本発明の方法に対するアルゴリズムの例を示す。
【図８Ｂ】フォーワーディング情報を動的に管理する本発明の方法に対するアルゴリズムの例を示す。
【図８Ｃ】フォーワーディング情報を動的に管理する本発明の方法に対するアルゴリズムの例を示す。
【図８Ｄ】フォーワーディング情報を動的に管理する本発明の方法に対するアルゴリズムの例を示す。
【図８Ｅ】フォーワーディング情報を動的に管理する本発明の方法に対するアルゴリズムの例を示す。
【図８Ｆ】フォーワーディング情報を動的に管理する本発明の方法に対するアルゴリズムの例を示す。
【図８Ｇ】フォーワーディング情報を動的に管理する本発明の方法に対するアルゴリズムの例を示す。
【図９Ａ】追加されたフォーワーディング情報を管理する本発明の方法を説明する図。
【図９Ｂ】追加されたフォーワーディング情報を管理する本発明の方法を説明する図。
【図１０Ａ】削除されたフォーワーディング情報を管理する本発明の方法を説明する図。
【図１０Ｂ】削除されたフォーワーディング情報を管理する本発明の方法を説明する図。
【図１１Ａ】本発明によるフォーワーディング情報動的管理方法の効果を立証するためのテスト結果を示すテーブル。
【図１１Ｂ】本発明によるフォーワーディング情報動的管理方法の効果を立証するためのテスト結果を示すグラフ。
【図１１Ｃ】本発明によるフォーワーディング情報動的管理方法の効果を立証するためのテスト結果を示すグラフ。
【図１１Ｄ】本発明によるフォーワーディング情報動的管理方法の効果を立証するためのテスト結果を示すグラフ。
【図１】
2004236339.tif 000003
【図２】
2004236339.tif 000004
【図３】
2004236339.tif 000005
【図４Ａ】
2004236339.tif 000006
【図４Ｂ】
2004236339.tif 000007
【図４Ｃ】
2004236339.tif 000008
【図５】
2004236339.tif 000009
【図６Ａ】
2004236339.tif 000010
【図６Ｂ】
2004236339.tif 000011
【図６Ｃ】
2004236339.tif 000012
【図７】
2004236339.tif 000013
【図８Ａ】
2004236339.tif 000014
【図８Ｂ】
2004236339.tif 000015
【図８Ｃ】
2004236339.tif 000016
【図８Ｄ】
2004236339.tif 000017
【図８Ｅ】
2004236339.tif 000018
【図８Ｆ】
2004236339.tif 000019
【図８Ｇ】
2004236339.tif 000020
【図９Ａ】
2004236339.tif 000021
【図９Ｂ】
2004236339.tif 000022
【図１０Ａ】
2004236339.tif 000023
【図１０Ｂ】
2004236339.tif 000024
【図１１Ａ】
2004236339.tif 000025
【図１１Ｂ】
2004236339.tif 000026
【図１１Ｃ】
2004236339.tif 000027
【図１１Ｄ】
2004236339.tif 000028