(57)【要約】本発明の一態様において、１またはそれ以上の最短径路は、リンクステートプロトコルに従って、ソースの頂点から１またはそれ以上の宛先の頂点にコンピュータネットワークの一部を通じて決定される。そして、ネットワーク部のグラフ表現が処理される。グラフ表現は、前記頂点および頂点間の結合点を表すノードおよびエッジを含む。前記処理は、ダイクストラ型アルゴリズムに従うグラフ表現の命令を含む。ダイクストラ型アルゴリズム処理の部分集合は、候補者リスト処理を含む。これにより、ダイクストラ型アルゴリズム処理に訪れたノードの候補者リスト（ＯＳＰＦ、ＩＳ−ＩＳ）を維持し、これに命令することができる。さらに、前記候補者リスト処理は、リンクステートプロトコルのために、標準的なダイクストラアルゴリズム処理に対して最適化される。最適化された候補者リスト処理は、例えば、リンクステートプロトコルから独立した汎用のフォーマットにおけるフィボナッチノードのフィボナッチヒープのような、候補者リスト処理が汎用のフォーマットで記憶されたノードについての候補者リストを命令するものであってもよい。さらに、前記候補者リスト処理は、汎用のアプリケーションプログラムインターフェイス（ＡＰＩ）を介してアクセス可能であってもよい。この結果、候補者リスト処理は、ＯＳＰＦおよびＩＳ−ＩＳのような様々なリンクステートルーティングプロトコルを含む、様々なリンクステートプロトコルに使用可能である。
2005531222.tif 000002
【特許請求の範囲】
【請求項１】
リンクステートプロトコルに従って、ソースの頂点から１またはそれ以上の宛先である頂点にコンピュータネットワークの一部を通じて１またはそれ以上の最短径路を決定するための方法であって、
前記ネットワーク部のグラフ表現を処理するものであり、前記グラフ表現は、前記頂点および当該頂点同士をの結合を表現するノードおよびエッジを含むものであり、
それぞれ、
前記処理は、ダイクストラ型アルゴリズムに従う前記グラフ表現における命令を含み、
前記ダイクストラ型アルゴリズム処理の部分集合は、前記ダイクストラ型アルゴリズム処理において訪れたノードについての候補者リストを維持し、当該ノードに命令するための候補者リスト処理を含み、
前記候補者リスト処理は、リンクステートプロトコルについての標準的なダイクストラアルゴリズム処理に関して最適化されることを特徴とする方法。
【請求項２】
前記候補者リスト処理は、
前記リンクステートプロトコルに独立した汎用のフォーマットに記憶されるフィボナッチノードのフィボナッチヒープとしてノードの前記候補者リストを維持し、
前記リンクステートプロトコルに独立した特定のアルゴリズムに従って前記フィボナッチノードのフィボナッチヒープを処理することにより１またはそれ以上の最短径路を決定すべく、フィボナッチノードのフィボナッチヒープに命令することを含むことを特徴とする請求項１記載の方法。
【請求項３】
前記候補者リスト処理は、前記特定のリンクステートプロトコルに独立した前記フィボナッチノードのフィボナッチヒープについて前に生成された汎用の記述を初めに受け入れることを含むことを特徴とする請求項２記載の方法。
【請求項４】
前記フィボナッチノードのフィボナッチヒープについて前に生成された汎用の記述を初めに受け入れることは、一般化されたアプリケーションプログラミングインターフェイスを介して、前記前に生成された汎用の記述を受け入れることを含むことを特徴とする請求項３記載の方法。
【請求項５】
前記フィボナッチノードのフィボナッチヒープを処理するステップは、前記フィボナッチノードを考慮して、いずれのノードが前記１またはそれ以上の最短径路に含まれるかを決定することを含むことを特徴とする請求項２記載の方法。
【請求項６】
前記フィボナッチノードのフィボナッチヒープを処理するステップは、対話方式で実行される削減キー命令を含むことを特徴とする請求項２記載の方法。
【請求項７】
前記フィボナッチノードに対するポインタのリストのためのメモリを初めに配置することを含み、
前記フィボナッチノードに命令するステップは、前記フィボナッチノードに対するポインタのリストを維持することを含むことを特徴とする請求項２記載の方法。
【請求項８】
前記フィボナッチノードに命令するステップは、前記特定のリンクステートプロトコルに独立した方式で前記フィボナッチヒープに結び付けられる比較機能にアクセスすることを含むことを特徴とする請求項２記載の方法。
【請求項９】
前記リンクステートプロトコルは、リンクステートルーティングプロトコルであることを特徴とする請求項１記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、フィボナッチヒープに関し、特に、ダイクストラ型アルゴリズムを用いてコンピュータネットワークの分配を通じて最短径路を決定するインターネットリンクステートプロトコルに適用すべく特化したフィボナッチヒープの概念に関する。
【背景技術】
【０００２】
インターネット内の情報は、パケットとして送信される。インターネットにおけるパケットは、所定の長さに固定されたデータ片であり、ソースから目的地にホップバイホップでそれぞれ決められる。パケットのルーティングの動作は、パケットを次の行き先（ネクストホップ）に転送するために、径路に沿ったルータのそれぞれがパケットのヘッダ情報およびローカルのデータベースを調べることを意味する。このローカルなデータベースは、いわゆる「転送情報ベース」またはＦＩＢと呼ばれるものである。通常はテーブルとして構成されるＦＩＢにおけるエントリーは、どこでパケットが転送されるかを決める。ＦＩＢは、ルーティング情報データベースまたはＲＩＢと呼ばれる集合的データベースから引き出される。このＲＩＢは、ルータが「知っている」、つまり、アルゴリズムがＦＩＢにおけるエントリー（径路）へのＲＩＢにおけるエントリー（径路）をマップするすべてのルーティング情報の集合であり、転送に用いられる。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
ＲＩＢは、一般的に２つの方法、それらは一緒に用いられるかもしれない、により構築される。すなわち、（ａ）静的コンフィギュレーションおよび（ｂ）動的ルーティングプロトコルである。これらのプロトコルは、インターネットの部分に基づいてさらに２つのグループに細分化されるかもしれない。これらのプロトコルの命令により、外部ゲートウェイプロトコルすなわちＥＧＰは、自律管理ドメイン間のルーティングデータを分散させる能力があり、内部ゲートウェイプロトコルすなわちＩＧＰは、単一の自律ドメイン内のルーティングデータを分散させる能力がある。さらに、ＩＧＰの２つのタイプは、今日広く用いられている。すなわち、アルゴリズムの距離ベクトルタイプを用いるものおよびリンクステート方法を用いるものである。本明細書は、リンクステートＩＧＰの命令において実行されるコンピュータ計算を最適化するためのアルゴリズムの適用について述べるものである。
【課題を解決するための手段】
【０００４】
本発明の一態様において、１またはそれ以上の最短径路は、リンクステートプロトコルに従って、ソースの頂点から１またはそれ以上の宛先の頂点にコンピュータネットワークの一部を通じて決定される。そして、ネットワーク部のグラフ表現が処理される。グラフ表現は、前記頂点および頂点間の結合点を表すノードおよびエッジを含む。
【０００５】
前記処理は、ダイクストラ型アルゴリズムに従うグラフ表現の命令を含む。ダイクストラ型アルゴリズム処理の部分集合は、候補者リスト処理を含む。これにより、ダイクストラ型アルゴリズム処理に訪れたノードの候補者リストを維持し、これに命令することができる。
【０００６】
さらに、前記候補者リスト処理は、リンクステートプロトコルのために、標準的なダイクストラアルゴリズム処理に対して最適化される。最適化された候補者リスト処理は、例えば、リンクステートプロトコルから独立した汎用のフォーマットにおけるフィボナッチノードのフィボナッチヒープのような、候補者リスト処理が汎用のフォーマットで記憶されたノードについての候補者リストを命令するものであってもよい。さらに、前記候補者リスト処理は、汎用のアプリケーションプログラムインターフェイスを介してアクセス可能であってもよい。この結果、候補者リスト処理は、ＯＳＰＦおよびＩＳ−ＩＳのような様々なリンクステートルーティングプロトコルを含む、様々なリンクステートプロトコルに使用可能である。
【発明を実施するための最良の形態】
【０００７】
リンクステートプロトコル（ルーティングプロトコルのような）により表されたオブジェクトは、マルチアクセスネットワークまたはルータのいずれかである。ネットワークは、ルータに接続されてもよいが、他のネットワークに接続されるものではない。ルータは、ネットワーク（マルチアクセスインターフェイスによる）に接続されるか、他のルータ（異なる階層の１対１接続による）に接続される。コンピュータネットワークは、グラフと呼ばれる抽象数学構造における特別な場合の実行である。つまり、グラフは、ネットワークのトポロジーを表す。リンクステートプロトコルは、ルータがドメインにおけるグラフの内部表現を記憶することを許容する。
【０００８】
グラフは、頂点とエッジとを含み、頂点は、ホスト（ローカルに出発したり到着したりしないパケットを径路付けない末端システム）またはルータ（「ネクストホップ」にパケットを径路付けるシステム）のいずれかである。エッジのそれぞれは、一対の頂点を結合する。
【０００９】
ＩＧＰプロトコルは、少なくとも大きく４つの基本的特徴により定義される。
・リンクステート情報についてのフラッディング命令
・リンクステート情報の構造
・最短径路木をコンピュータ計算するためのアルゴリズム
・隣接獲得およびデータベース同期通信のためのサブプロトコル、通信のためのパケットフォーマット
【００１０】
ルータのそれぞれは、ローカルの接続性を記述して「広告」（ＬＳＡ、すなわちリンクステートアドバタイズメント）を氾濫（フラッド）させる。プロトコルは、データを保証するためのフラッディング機構がドメインを通じて送信され、ネットワークにおける特定の同じ視点をそれぞれ与えるものと定義される。標準アルゴリズムは、結果のグラフ上の最短径路木をコンピュータ計算するために用いられる。これにより、すべてのルータが最短径路をネットワークにおいて如何にするかについて同じ考えを有するときに、ホップバイホップが機能的にルーティングすることができる。
【００１１】
これらのプロトコルが「グラフ」についての抽象概念を命令する間、それぞれのプロトコルは、グラフがどのように表現され、最短径路木のコンピュータ計算をどのように行うかを定義する。「最短」は、一般的に「最低コスト」を意味し、コストは、（物理的距離のような）特定の基準を用いて決定される。このように、一般的には、グラフがどのように表現されるかについての定義は、プロトコル間で異なる。ＯＳＰＦおよびＩＳ−ＩＳプロトコルは、本明細書で例として述べられる。
【００１２】
多くのリンクステートプロトコルは、ダイクストラ型アルゴリズムを用い、最短径路をコンピュータ計算する。これらのアルゴリズムは、「候補者リスト」と呼ばれる抽象構造を参照する。候補者リストは、コンピュータ計算において訪れたノードを保持するが、最短径路が見つかったかどうかは認識しないものである。候補者リストの実行は、特定のプロトコルが使用される部分に依存する。リストは、ルータおよびホスト（頂点）またはネットワーク（エッジ）を保持する。プロトコル基準によって定義されたところによると、「リスト」は、単にルータおよびネットワークの１集合であり、さもなければ前記基準は、いずれの特定の集合の表現も必要ない。
＜リンクステートプロトコルにおけるフィボナッチヒープの使用＞
【００１３】
リンクステートルーティングプロトコルに関する本発明の一態様によれば、抽象アルゴリズムの実行は、ダイクストラ型アルゴリズムをインターネットリンクステートプロトコルにおいて記述されるルータおよびネットワークの候補者リストを最適化するために用いられる。それぞれのルーティングプロトコルは、最短径路木をコンピュータ計算すべく一致したアルゴリズムを使用する。フィボナッチヒープの使用は、コンピュータ計算のスピードを大幅に改善し、アルゴリズムがより頻繁に実行され、拘束をより少なくすることができる。
【００１４】
フィボナッチヒープの一般化された実行は、特に、インターネットリンクステートプロトコルが用いられるアルゴリズムに合わせられる。ＯＳＰＦおよびＩＳ−ＩＳにおいて、これは、ＲＦＣ２３２８（ＯＳＰＦバージョン２）のセクション１６．１およびＩＳＯ１０５８９（非結合モードのネットワークサービス（ＩＳＯ８４７３）を提供するプロトコルとともに用いるための中間システムから中間システムへのイントラドメインルーティング情報交換プロトコル）のセクションＣ．２．４において使用される候補者リストである。特定の変更例は、以下に表せる。
・フィボナッチヒープとしてリストを表現する間、インターネットリンクステートプロトコルの必要性を満足させるべく設計された一般化されたアプリケーションプログラミングインターフェイス（「ＡＰＩ」）。ＡＰＩは、例えば、ＯＳＰＦおよびＩＳ−ＩＳの最短径路コンピュータ計算の特定の要求に合わせられる。
・アルゴリズムがいずれのリンクステートプロトコルオブジェクト（例えば、ＯＳＰＦおよびＩＳ−ＩＳにおけるルータおよびネットワーク）に対し一般的な命令を行うためのアルゴリズムのデータ構造の実行。
・最小化または再帰の回避。再帰は、限られたスタック領域を有するシステムにおいて特に不利益を生じる。
・初期時間における「補助」配列の配置。配列は、固定されたサイズ、最短径路コンピュータ計算において期待される最大径路長さにおいては最大でbase-２ログである。
・異なるデータ構造におけるヒープの有用性を増大させるための比較機能の使用。
＜ＡＰＩ＞
【００１５】
一般的なＡＰＩは、以下の命令を含んでいる。
・初期化
・挿入
・削減（リラックス）キー
・最小値抽出
【００１６】
これらの命令は、インターネットルーティングの目的のために最短径路木についてコンピュータ計算するのに用いられる。ＡＰＩは、ＯＳＰＦ（ルータおよびネットワークＬＳＡ）またはＩＳ−ＩＳ（ＬＳＰおよび擬似ノードＬＳＰ）にコード変更なしで命令し、ＡＰＩは、これらの構造（「ノード」）についての汎用表記を受け入れ、どのようなノードが表れているかに関わらず、それぞれに同様の命令を行う。これにより、ＡＰＩは、多数の目的に用いることができる。例えば、ＯＳＰＦおよびＩＳ−ＩＳの双方を用いることができる。
【００１７】
「初期化」命令において、最初サイズの補助配列は、初期化機能に関するパラメータに従って配置される。
＜汎用データ構造＞
【００１８】
より詳細に後述するデータ構造は、リンクステート情報の一片を表示する一般的な方法として提供される。例えば、ＯＳＰＦルータＬＳＡまたはネットワークＬＳＡである。この構造は、フィボナッチヒープのためだけに情報特性を保持する。
【００１９】
ノードは、初期化ＡＰＩ呼び出しにヒープ「キー」のオフセットまたは他の参照を特定する値を与えることによって、ＬＳＡ表現のような、プロトコル特性データ構造に、オフセットされるまたはさもなければ参照される。これにより、さらなる命令にとって、プロトコル特性データ構造を認識することなくノードのキーを参照することができる。当該命令は、プロトコル特性データ構造にオフセットを使用し、ヒープに厳密に関係するデータにアクセスする。
【００２０】
このアルゴリズムの再帰的な実行は、多くのシステムにおけるスタック領域が有限であるおかげで、実用的ではないだろう。この実行は、フィボナッチヒープアルゴリズムの「切断された」構成における対話型バージョンを使用する。
【００２１】
上述したように、ＯＳＰＦ（Open Shortest Path First）のようなインターネットルーティングプロトコルは、ダイクストラ型コンピュータ計算において訪れた頂点の集合を表すノードの「候補者リスト」に利用される。ノードのそれぞれは、いくつかのキーを保持する。キーは、例えば、ソースからノードによって表現される頂点へのコンピュータ計算時点における最小コストを表す数値である。比較機能は、フィボナッチヒープインスタンス構造において記憶される。この機能は、２つの独立変数を要求する。すなわち、比較すべき２つのノードのキーを参照するものである。この機能は、０，−１または１を返す。すなわち、第１のキーが第２のキーに対して等しい、少ないまたは多いことをそれぞれ表すものである。リストにおいて実行される命令は、「初期化」、「挿入」、「最小値抽出」および「削減キー」に要約される。
【００２２】
特定されたフィボナッチヒープ構造のアプリケーションとともに、最短径路木のコンピュータ計算に用いられるダイクストラ型アルゴリズムは、Ｏ（ＶｌｇＶ＋Ｅ）集合とともに実行され、ＩＰネットワークのスケーラビリティが改善される。
【００２３】
命令において、アルゴリズムおよびデータ構造は、ダイクストラ型アルゴリズムのクリティカルピース、すなわち、候補者リストの表現に適用される。このアルゴリズムおよびデータ構造の適用は、最短径路（ダイクストラ型）コンピュータ計算をより効果的に行うことによって、リンクステートインターネットルーティングプロトコルにおいてスケーラビリティを増大させる結果となる。図１はアルゴリズムおよびデータ構造の機能的配置を例示する。
【００２４】
図２は汎用フィボナッチヒープの実行に関して最短径路のコンピュータ計算インターフェイスの方法を例示する。コンピュータ計算は、入力として、フラッディング過程を通じて見つけられた頂点を表すノードの集合を採用し、出力として、ネットワークを通じての最短径路（複数でもよい）を採用する。
【００２５】
図３は実行の「汎用」要素を例示する。つまり、ＩＳ−ＩＳのＬＳＰおよびＯＳＰＦのＬＳＡおよびノードのすべては、ＡＰＩを通過する際に、フィボナッチヒープのノードとして扱われる。ヒープは、多数のプロトコルに供され、同時に集合を最小化する。
【００２６】
ダイクストラ型コンピュータ計算で見つけられたグラフの頂点のそれぞれは、図４に例示するように、候補者リストにおけるノードエントリーに結び付けられる。それぞれの領域は、さらに表１において説明される。それぞれのノードは、兄弟の円形キューの部分であり、親のポインタを維持する。
【表１】
2005531222.tif 000003
【００２７】
候補者リストは、図５において例示されるように、フィボナッチループの最上位構造によって表現される。なお図５はヒープのインスタンスを表現する。このような構造の１つは、例えば、リンクステートプロトコルのそれぞれのインスタンスのために、リストインスタンスごとに具体化される。径路ノードの円形キューへのポインタは維持され、前記リストにアクセスする点となる。それぞれの領域の目的は、表２に説明される。明細書において、領域の名称および変更される名称は“名称”により示される。
【表２】
2005531222.tif 000004
【００２８】
すべての命令において、円形キューを径路付けるべくノードを動かすことは、“fn_parent”領域を０に設定し、所有するヒープの“f_min”によって指示されるキューを加えることによって達成される。
【００２９】
図５の構造のインスタンスにおける一般的な配置は、図６に例示される。インスタンス構造のいくつかの領域は、図６においては例示の明確化のために省略されている。
【００３０】
ここで、フィボナッチヒープ構造がこれを介して処理されるアプリケーションプログラミングインターフェイス（ＡＰＩ）の例について説明する。明細書において、変更される名称は、“名称”により示されるとともに、領域の名称も“名称”により示される。
＜初期化命令＞
【００３１】
ＡＰＩの定義
fibheap_init(heap, data_offset, key_offset, maxbits, comparison_function)
【００３２】
パラメータ
“heap”−フィボナッチヒープのインスタンスを表現する木構造のためのポインタ（図５参照）。
“data_offset”−データを保持するノードにおけるポインタのオフセット。
“key_offset”−キーを保持するノードにおけるポインタのオフセット。このパラメータは、キーがノード自体に対するオフセットであることを指示するとき、０であろう。
“max_bits”−いずれかのキーにおけるビットの最大値、または、最大キーにおけるbase-２ログ。
“comparison_function”−２つのキーを比較するのに用いられる機能のためのポインタ。第１および第２のキー間の関係を示すために、０より小さい値、０に等しい値、０より大きい値を返す。
【００３３】
手順
１）  “fibheap_init”全体の“f_min”および“f_nnode”の領域は、０に初期化される。
２）  “maxbits”および“comparison_function”は、フィボヒープインスタンス構造においてこれらの値を初期化するために用いられる。
３）“maxbits”ポインタのサイズの配列は、インスタンス構造に配置され、記憶される。
【００３４】
初期化命令は、図７に例示される。
＜挿入命令＞
【００３５】
ＡＰＩの定義
fibheap_insert(tree, node)
【００３６】
パラメータ
“tree”−ヒープインスタンス構造へのポインタ（図５参照）
“node”−ノード構造へのポインタ（図４参照）
【００３７】
手順
１）  新しい“node”が径路ノードの円形キューに設定される。ヒープインスタンス構造における最小ノードポインタにより参照される（図５参照）。
２）  ユーザに提供される比較機能が独立変数の“node”および現在の最小ノードを呼び出す。この機能が０より小さい値を返した場合、ヒープ構図における最小ポインタは、“node”に指示すべく設定される。
【００３８】
挿入命令の例は、図８に示される。
＜最小値抽出命令＞
【００３９】
ＡＰＩ定義
fibheap_extract(heap)；最小ノードを返す
【００４０】
パラメータ
“heap”−ヒープインスタンス構造へのポインタ（図５参照）
【００４１】
手順
１）  最小ノードは、円形キューから取り除かれる。
２）  このノードのすべての子は、径路円形キューに移される。
３）  ヒープは、以下の手順を用いて結合される。
ａ  “maxbits”ポインタのサイズのバッファ（図５参照）は０に初期化される。
ｂ  径路円形キューは、動き、親に指示するための配列において、階級がＮである場合、Ｎ次のエントリーを設定する。
ｃ  この階級のためのＮのエントリーがすでに存在する場合、ヒープは、合併され、ヒープの特性を保持する（すなわち、親より大きな子は存在しない）。
ｉ  この場合、新たなヒープの階級Ｎ＋１が当該配列におけるＮ＋１次のエントリーによって参照される。
ｄ  この手順の最後に、径路円形キューからの配列によって参照される。
４）新しい最小値は、径路円形キューを動くことによって見つけられる。
５）ノードの数が減少する。
【００４２】
この命令は、図９−１２に例示される。
＜削減キー命令＞
【００４３】
ＡＰＩ定義
fibheap_key_changed(tree, node)
【００４４】
パラメータ
“tree”−ヒープインスタンス構造へのポインタ（図５参照）
“node”−ヒープノード構造へのポインタ（図４参照）
【００４５】
手順
１．  “node”のキーが現在の最小ノードのキーより小さい場合は、“node”は、最小ノードとなる。この比較は、初期化命令において与えられる機能として行われる。
２．  “node”が径路円形キューにある場合、命令は、終了する。
３．  その他、“node”のキーが親のキーより小さい場合、“node”は、径路リストに移される。
４．  以下の手順が繰り返される。この手順が開始される前に、“pnode”が親のポインタが消去される前に移された親のノードに設定される。
ａ）  “pnode”が有効なノードに設定されていない場合、本手順は終了する。
ｂ）  “pnode”のマークが設定されていない場合、当該マークを設定して本手順を終了する。
ｃ）  その他の場合、“pnode”は、径路キューに移され、そのマークは消去されるとともに、“pnode”は親の“pnode”に設定される。
【００４６】
図１３−１６は図５の構造における削減キー命令の対話の定義を例示する。これにより、“pnode”のループ不変量、すなわち、検査を受けるだけでノードの親が規定される。単一の場合は、以下に示される再帰的定義よりルーピング手順は、限られた供給源を有するコンピュータ計算の環境において利益がある。
【００４７】
この命令における再帰的定義は、カットおよび再帰的カット命令を定義する。削減キー命令は、以下に示すように、これらの命令に置き換えられて定義される。“node”のキーが親のノードのキーより小さい場合、“node”にカットを行い、親の“node”に再帰的カットを行う。
【００４８】
＜カット命令（node）＞
ａ）  “node”を径路キューに移し、そのマークを消去する。
【００４９】
＜再帰的カット命令（node）＞
ａ）  “node”が０である場合、本手順は終了する。
ｂ）  “node”のマークが設定されていない場合、そのマークが設定され、本手順は終了する。
ｃ）  その他の場合、“node”にカットを行い、親の“node”に再帰的カットを行う。
【００５０】
フィボナッチヒープに関するダイクストラアルゴリズムは、数学ジャーナルにおいて論じられているが、フィボナッチヒープの実施の実行が遅く複雑である場合が考慮されている。特定の実行の詳細には、最小化された複雑性における達成速度が重要である。ここで、そのような実行の詳細の例について述べる。述べられる実行は、高速で、少ない複雑度を有するものである。これはＩＰ径路コンピュータ計算を速めるだけでなく、これらの実行が自身を縮小可能とするのに役立つ。
＜フィボナッチヒープに基づく理論的刊行物と実地的刊行物＞
【００５１】
最小質量のスパンニング木の決定は、グラフ問題でよく知られている。この問題に対する回答は広く示されており、ベルマンフォード（R.bellman, "On a routing problem", Q. Appl. Math, vol 16, pp.87-90,1958）、デソポ−パーぺ（D.Berksekas, "Linear Network Optimizations: Algorithms and Code", MA, Cambridge: MIT Press 1991）およびダイクストラ（E.Dijkstra, "A note two problems in connection with graphs", Numerical Math, vol.1, pp.269-271,1959）のアルゴリズムが含まれる。ダイクストラアルゴリズムは、インターネットリンクステートルーティングプロトコルにおいてルーティングのコンピュータ計算の基礎であり、本明細書においても「ダイクストラ型」アルゴリズムとして参照される。それぞれのプロトコルがアルゴリズムを適用する特定の方法を定義するからである。フレッドマンおよびタージャン（M.Fredman, R.Tarjan, "Fibonacci Heaps and their uses in improved network optimization algorithms", 1987, ACM 004-5411/87/0700-0596）はフィボナッチヒープをダイクストラに使用される候補者リスを記憶する新しい方法として提案している。そして、これがＯ(ＶｌｇＶ＋Ｅ)で制限されるアルゴリズムの理論的に最悪のケースを改善することを提案している（Cormen, Leiserson, Rivest, Introduction to Algorithms, MIT Press 1990, ISBN 0-262-03141-8, p530）。
【００５２】
フィボナッチヒープのアルゴリズムの理論的実行は、裏付けられるが、経験的証拠は、フィボナッチヒープが複雑（J.Stasko, J.Vitter, "Pairing Heaps, Experiments and Analysis", p235 paragraph 2, 1987, Communications of the ACM, Volume 30 number 3）で遅い（Rajeev Raman, "A Summary of shortest-path results", December 1996,p7）ことを理由として、実際にはその通りに利用可能ではないことを指し示している。ここでは以下のようにまとめられている。
【００５３】
「しかし、現実的な観点から、フィボナッチヒープにおける一定の要件およびプログラミングの複雑性は、多くのアプリケーションにとって通常の２進数（またはｋ配列）ヒープより望ましくないものである。このようにフィボナッチヒープは、理論的興味が支配的である。フィボナッチヒープとしての同じ償却時間限界内における多くのより簡単なデータ構造が発展すれば、実際の使用にとっても素晴らしいだろう（Cormen, Leiserson, Rivest, Introduction to Algorithms, MIT Press 1990, ISBN 0-262-03141-8, p420）。」
【００５４】
ここで、実際の限界は、インターネットリンクステートプロトコルにおける最短径路のコンピュータ計算である特定化されたドメインにおける「プログラミングの複雑性」および「一定の要件」として記述されている。この結果は、パフォーマンスの改善に重大な影響を与える。これらの要件を以下に述べる。
【００５５】
まず、一般的なフィボナッチヒープ定義は、ノードに対し少なくともＤmaxのポインタを記憶する「補足配列」の必要性を有している。ここで、Ｄmaxは、使用されるキーの集合に関する最大ログに等しい。一例に従って、有限の最大ログに基づいて補足配列の初期時間を配置する。
＜再帰的定義＞
【００５６】
一般的なフィボナッチヒープ定義は、再帰的である。多くの環境において、再帰性は、現実的ではない。一例に従って、対話の手順を形成する。例えば、一般化されたＡＰＩの「最小値抽出」命令として機能する「カット」命令は、親のノードを効果的かつ再帰的に検査し、そのノードが径路キューに移される必要があるかどうかを判断する。本例の実行は、ノードリストの経路における親のポインタをＮＵＬＬに設定する。このような対話機能は、先祖のノードにループ不変量として親のポインタの集合を用いて命令してもよい。
【００５７】
さらに、ノードごとに（例えば、左および右の兄弟ポインタおよび親のポインタのために、「マーク」表示に沿って）外部記憶を利用して、多くの簿記領域が木の維持に利用される。これは、他のデータ構造に典型的に利用されるものより多く記憶される。
【００５８】
一例に従うと、「プログラミングの複雑性」は、インターネットリンクステートルーティングプロトコルドメインにとって減少および変調され、効果的に改善されて、実行可能となる。
【００５９】
一般的なフィボナッチヒープは、コストまたは他のキーに基づいたノード参照について効果的なサポートが提供されていない。これは例えば、ＯＳＰＦにおけるルーティングコンピュータ計算のパート（２）ステップ（ｄ）に用いられ、頂点のための候補者リストノードエントリーが検索される（すなわち、頂点のための候補者リストにおけるノードエントリーがあるか否かが決定される）。この本例における欠点を「所有する」頂点における頂点のための候補者リストノードエントリー構造にポインタを保持することによって記述する。このため、最小コストのノードが参照なしに検索されるだろう。
【００６０】
「最小値抽出」命令は、直後に生じる木の合併により、「挿入」または「削減キー」命令よりも長いものとなる。これはいくつかのアプリケーション、特に、ダイクストラ型コンピュータ計算の構成において保証された境界が一般的に必要とされるものに否定的な影響を与える間、例えスパンニング木が１つだけでもコンピュータ計算が典型的にすべて同時に生じるため、リンクステートルーティングプロトコルのドメインを発行しないからである。
【００６１】
ここで、フィボナッチヒープアルゴリズムのアプリケーションおよびＯＳＰＦにおける最短径路コンピュータ計算のためのデータ構造を例示する。
＜候補者リスト表現＞
【００６２】
ＲＦＣ２３２８のセクション１６．１により参照される候補者リストは、図１７に示される相対的に単純な構造により表現される。構造におけるそれぞれの領域の目的は、表３において説明される。
【表３】
2005531222.tif 000005
【００６３】
“vertex_t”構造は単一のＯＳＰＦのＬＳＡを表現している。この構造は、ヒープにおけるこのＬＳＡを表現する“cdtlist_t”に戻ったポインタを保持する。ヒープは、効果的な参照がサポートされないため、このポインタは、パフォーマンスの増大を提供する。「ノード」の語は、本明細書おいてＬＳＡと相互交換可能に用いられ、フィボナッチヒープにおけるノードのそれぞれを意味することは、最短径路コンピュータ計算において記載されるＬＳＡを表現する。
【００６４】
次のセクションでは、ＡＮＳＩ ＣにおけるＡＰＩの定義を含むアルゴリズムを記載する。セクション１６．１においてＯＳＰＦによって用いられる命令は、「初期化」、「挿入」、「最小値抽出」および「削減キー」である。これらは、以下に示すようにＲＦＣ２３２８のセクション１６．１の実行例として用いられる。
【００６５】
ステップ１において、「初期化」は、候補者リストに用いられるデータ構造を初期化するのに用いられる。
【００６６】
ステップ２において、パート（ｄ）、バレット３、コストＤが候補者リストの頂点Ｗの現在のコストより小さい場合、「削減キー」は、リストのＷのコストを調整することに用いられる。Ｗがエントリーを有していない場合、「挿入」は、リストのＷのためのエントリーを挿入することに用いられる。
【００６７】
ステップ３において、最初コストを有する候補者リストにおけるノードが選択される。「最小値抽出」命令は、最小キーを有する候補者リストにおけるノードエントリーを抽出することに用いられる。
【００６８】
まとめると、本例のフィボナッチヒープアルゴリズムは、ＩＰ径路を計算するのに用いられるＯＳＰＦにおける特定の過程における特定の構成に適用される。ＲＦＣ２３２８のセクション１６．１におけるアルゴリズムの最適化のためのアルゴリズムの使用により、ＯＳＰＦ領域におけるＩＰ径路のコンピュータ計算に必要な時間が減少するため、スケーラビリティが劇的に改善し、ＯＳＰＦの実行における命令実行の能力が向上するという結果をもたらす。
【００６９】
ここで、他の例として、中間システム−中間システム（ＩＳ−ＩＳ）プロトコルについて説明する。ＩＳ−ＩＳプロトコルは、ＯＳＰＦに使用されるのと同様の機構を用いるリンクステートプロトコルである。ＩＳ−ＩＳプロトコルはＩＳＯ標準１０５８９に記載されている。
【００７０】
リンクステート情報は、ＬＳＰ（リンクステートパケット）の形式で氾濫（フラッド）される。ＩＳ−ＩＳは、２レベルの階層を用い、ドメインをそれぞれの「レベル」に区分する。最短径路のコンピュータ計算は、レベル１およびレベル２について独立して行われる。これらのコンピュータ計算の結果は、前方状態を維持するために、ＯＳＰＦにおけるものと同様の目的のために使用される。
【００７１】
ここで、ＩＳ−ＩＳにおける最短径路コンピュータ計算のためのフィボナッチヒープアルゴリズムの例におけるアプリケーションおよびデータ構造について説明する。ＩＳ−ＩＳに用いられるアルゴリズムは、一般的にＩＳＯ１０５８９のセクションＣ．２．４、付録Ｃに記載される。
＜ＴＥＮＴエントリー表現＞
【００７２】
最短径路コンピュータ計算において見つけられた宛先（ネットワークまたはルータ）は、ＴＥＮＴ内のエントリーである。
【００７３】
本記述に関する領域の部分集合は図１８に示され、表４に記される。表に記載されていない領域は、本記述に関係しない。
【表４】
2005531222.tif 000006
【００７４】
“dh_fnode”領域は、ＴＥＮＴに関する宛先の状態を維持する。全体のカウンタは、最短径路アルゴリズムの反復ごとに増大する。宛先がＴＥＮＴに位置したとき、“dh_fnode”領域は、カウンタの値に設定される。宛先は本記述に関しない他の形式の間で、グラフ（ネットワークまたはルータ）において見つけられた頂点の形式で表現される。それぞれの頂点は、“dh_fnode”で表現される自身のフィボナッチヒープノードを有している。
【００７５】
頂点の２つの集合は、ＴＥＮＴおよびＰＡＴＨとして維持される。ＯＳＰＦにおいて使用される候補者リストは、ＩＳ−ＩＳにおけるＴＥＮＴに、厳密ではないが、類似するものである。候補者リストは、最短径路が見つかったかどうか知らない頂点の集合を保持する。
【００７６】
ＴＥＮＴにおける頂点の集合（ＬＳＰ）は、セクションＣ．２．４から始まって記載されるアルゴリズムの以下の項目により処理される。
１）  Ｃ．２．５のステップ０において、ＴＥＮＴリストは、０に初期化される。
２）  Ｃ．２．６のステップ１、パート（ｄ）において、頂点は、（長さが）変更されたキーを有する。
３）  Ｃ．２．７のステップ２、パート（ａ）において、最小コストの頂点が、ＴＥＮＴから抽出される。
４）  Ｃ．２．７のステップ２、パート（ａ）において、頂点がＴＥＮＴに位置される。
【００７７】
上記リスト命令は、「初期化」、「削減キー」、「最小値抽出」および「挿入」にそれぞれ要約されるだろう。
【００７８】
ＩＳ−ＩＳのＴＥＮＴリストについての変更されたフィボナッチヒープアルゴリズムのアプリケーションおよびデータ構造の利点としては、
・セクションＣ２．４において定義されるアルゴリズムの実行が完了するまでに必要な時間が、大きなＩＳ−ＩＳトポロジーの存在により、大幅に減少される。
・コンピュータ計算における実行時間が減少することにより、一般的により多くのコンピュータ計算が可能になる（より正確な前状態を導く）または、拘束されることが少なくなる（中断なしで実行可能となる等）。
＜ＩＳ−ＩＳを用いた統合＞
【００７９】
要約すると、フィボナッチヒープアルゴリズムは、ＩＰ径路を計算するのに用いられるＩＳ−ＩＳリンクステートルーティングプロトコルのような、リンクステートプロトコルの特定された過程において特定の構成に適用される。ＩＳＯ１０５８９のセクションＣ．２．４におけるアルゴリズムの最適化のためのアルゴリズムの使用により、ＩＳ−ＩＳレベルにおけるＩＰ径路のコンピュータ計算に必要な時間が減少するため、スケーラビリティが劇的に改善し、ＯＳＰＦの実行における命令実行の能力が向上するという結果をもたらす。
【図面の簡単な説明】
【００８０】
【図１】データ構造およびダイクストラ型アルゴリズムにおける最短径路のコンピュータ計算を示す概念図である。
【図２】最短径路のコンピュータ計算が候補者リストについての汎用フィボナッチヒープの実行とインターフェイスをとる方法をより詳細に示す図である。。
【図３】フィボナッチヒープとして実行された図２の候補者リストの「汎用」な質を示す図である。
【図４】フィボナッチヒープの候補者リストにおける１つのノードエントリーのための構成図である。
【図５】図２のフィボナッチヒープの候補者リストの上位構造を示す図である。
【図６】図５の構造例の一般的配置を示す図である。
【図７】図５の構造における初期化命令を示す図である。
【図８】図５の構造における挿入命令を示す図である。
【図９】図５の構造における最小値抽出命令を示す図である。
【図１０】図５の構造における最小値抽出命令を示す図である。
【図１１】図５の構造における最小値抽出命令を示す図である。
【図１２】図５の構造における最小値抽出命令を示す図である。
【図１３】図５の構造における削減キー命令を示す図である。
【図１４】図５の構造における削減キー命令を示す図である。
【図１５】図５の構造における削減キー命令を示す図である。
【図１６】図５の構造における削減キー命令を示す図である。
【図１７】ＯＳＰＦインターネットリンクステートプロトコルのためのＲＦＣ２３２８のセクション１６．１により参照される候補者リストを表す構造を示す図である。
【図１８】ＩＳ−ＩＳインターネットリンクステートプロトコルに従うＴＥＮＴリストを表す構造を示す図である。
【図１】
2005531222.tif 000007
【図２】
2005531222.tif 000008
【図３】
2005531222.tif 000009
【図４】
2005531222.tif 000010
【図５】
2005531222.tif 000011
【図６】
2005531222.tif 000012
【図７】
2005531222.tif 000013
【図８】
2005531222.tif 000014
【図９】
2005531222.tif 000015
【図１０】
2005531222.tif 000016
【図１１】
2005531222.tif 000017
【図１２】
2005531222.tif 000018
【図１３】
2005531222.tif 000019
【図１４】
2005531222.tif 000020
【図１５】
2005531222.tif 000021
【図１６】
2005531222.tif 000022
【図１７】
2005531222.tif 000023
【図１８】
2005531222.tif 000024
【国際調査報告】
2005531222.tif 000025
2005531222.tif 000026