JP2008167464A - Ｔｌｖに基づいたリンク状態のパケットの処理方法及び装置 - Google Patents

Abstract

【課題】古いエレメントを無駄に削除することなく、エレメントの内容における変化を認識し、プロトコルのパフォーマンスを改良する。
【解決手段】各ノードは、パーズされたＴＬＶでエンコードされたパケットを表しておりエレメントを指すポインタのリストと、エレメントを指すポインタの複製リストの木とを入力として受け付け、ポインタによって示されるリストのエレメントの各々は、埋め込まれたエレメントを指すポインタのリストと、埋め込まれたポインタの木とを含んでおり、その木は、変化がないエレメントを探す検索に用いられ、各ノードは、パーズしていない新たなパケットを表しており、エレメントを指すポインタのリストを更に入力として受け入れ、各ノードは、パーズしたＴＬＶでエンコードされたパケットを表し、エレメントを指すポインタのリストから、パーズしていないパケットを表し、エレメントを指すポインタのリストの新バージョンを生成する。
【選択図】図１

Description

本発明は、電気通信ネットワークに関するものである。より詳細には、本発明は、ＴＬＶに基づいたリンク状態のパケット（link-stated packet）を処理する方法および装置に関する。

商業目的や公共目的のための大規模ネットワークが使用頻度や複雑性が増大するにつれて、ルーティングプロトコルの現在の主流であるリンク状態のルーティングアルゴリズムは、ますます複雑になっている。一例として、ＡＴＭフォーラム団体によって決められたルーティングプロトコルであるＰ−ＮＮＩ（ＡＴＭフォーラム、ＰＮＮＩ仕様1.0、1996年、この引用を以て本願の内容とする。）が挙げられる。リンク状態のルーティングプロトコルは、ほぼ現在まで、トポロジ情報を転送するために、安価に処理され得る固定フォーマット型パケットに依存していた。前記プロトコルを将来拡張することがやがて要求されるであろうことから、タイプ−レングス−値（ＴＬＶ）でエンコードされたパケットが発展している。前記パケットのパーシングは、非常に高価なものとなる。本発明は、前記パケットを漸増的に素早く処理する新規な方法を提供する。

コンピュータのネットワーク化によって、例えば、ネーミング、アドレッシングおよびルーティング[J. Schoch, Inter-network naming, addressing and routing. In IEEE Proc. Compcon, 1978]といった様々な問題点がもたらされ、当然の如く、該問題点の様々な解決法がもたらされた。近時、ルーティングにおける焦点は、動的ルーティング、すなわち状態適合ルーティング（state-adaptive routing）へと移行している[G. Ash, J. Chen, A. Frey, B. Huang, C. Lee, G.McDonald. Real-time network routing in the AT&T network-improved servicequality at lower cost. In Globecom. AT&T Bell Laboratories, 1992; R. Callon, R. Guerin, E. Hoffman, J. Jeffords, G. Swallow. P-NNI routing hierarchy; overview and examples. P-NNI Working Group, March 1994]。前記ルーティングは、多数の構成作業を保持する他に、ネットワーク内で利用可能なリソースの変化やリンクの故障（failure）に素早く対応する。さらに、この種のルーティングは、ＡＴＭ等のＢ−ＩＳＤＮネットワーク技術を導入する際に益々必要となり[Jean-Yves Le Boudec, The Asynchronous Transfer Mode: A Tutorial. Computer Networks and ISDN Systems, 1992]、該技術によって、キャリアのネットワークと、私設のコンピュータネットワーク（privately operated computer network）との境界が曖昧となり始めている。

コンピュータネットワークの動的ルーティングに関して、様々な解決案が存在するが、未だ開発中であり、距離ベクトル型[L. Ford and D. Fulkerson, Flowsin Networks. Princeton University Press, 1962]やリンク状態型[J.M. McQuillan, I. Richer, E.C. Rosen, ARPANET routing algorithms improvement. BBNTechnical Report 3803, April 1978]が広く知られている。ルーティングの内容とサービスの要求品質における特長から、リンク状態のプロトコルが、ＡＴＭ等の技術を促す基礎として使用されている。リンク状態のルーティングプロトコルの基本的な考えは、各ノードが地域内のトポロジ情報を隣のノードに送信することにある[R. Perlman, "Interconnections", Addison-Wesley, 1992, ISBN 0-201-56322-0]。次に、この情報は、複雑な「フラディング（flooding）」機構を用いて、ネットワーク中に伝達される。前記処理の結果として、ネットワーク内の各ノードは、いわゆる「トポロジデータベース」におけるネットワークトポロジ全体のビューを具える。最新のリンク状態のルーティングプロトコルには、「階層（hierarchy）」の概念が組み入れられており、該階層において、ネットワークの一部は崩れて、離間したノードの視点における論理的ノードとなる。ノードが、地域内の利用可能なリソースにおける重大な変化を知る毎に、情報の生成およびフラディングは繰り返される。トポロジ情報の分配された断片は、リンク状態の最新情報（ＬＳＵ、link state up-dates）またはリンク状態のエレメントと呼ばれており、一意の（unique）識別子と、該ＬＳＵ内部の情報が更新される際に増加するバージョン数とを有している。さらに、前記処理が頻繁に発生し過ぎることを防止するため、減衰関数によって制御される閾値が、重大でない変化を保留する（hold back）。ノード間にて「フラディング」機構を実行することにより生じるトポロジデータベースを用いて、ユーザが所望の転送先（destination）に到達するように要求するルートが計算される。前記ルートは、例えば、パケットのフォワーディングや、コネクション型ネットワークにおけるセットアップ呼出しのルーティングにおいて使用される。

ＰＮＮＩ等の最近のルーティングプロトコルは、将来の要求に対する拡張可能な傾向に従っており、徐々に固定型パケット形式を廃止して、ＴＬＶ（タイプ−レングス−値）にてエンコードされたパケット体系（scheme）を使用し始めている。タイプは、伝送されるＴＬＶの固定部を説明し、レングスは、パケット内にて次のＴＬＶが始まるオフセットを示す。レングスが、ＴＬＶの固定部の長さを超える場合には、埋込み型ＴＬＶが提供される。一般に、最近のルーティングプロトコルにおいて、ＴＬＶにてエンコードされ、トポロジ情報を転送するパケットは、リストに再帰的に埋め込まれた任意のエレメントのリスト表現として解釈され得る。この方法は、非常にフレキシブルではあるけれども、要求されたＣＰＵに関する処理負荷を増大させる。図１は、２つのＴＬＶを視覚化し、その内の最初のＴＬＶには、他の２つのＴＬＶが埋め込まれている。

本願にて提供される解決法では、（おそらくは、再帰的にネスト(nest)構造となった）任意のエレメントのリンクされたリストへの変化を、漸増的な方法で処理できる新規のアルゴリズムが導入される。最近のルーティングプロトコルにおいて、ＴＬＶにてエンコードされ、トポロジ情報を転送するパケットは、前記ネスト構造の表現として解釈され得る。トポロジパケットは、リスト構造の変化よりもリストエレメントの内容の変化を頻繁に含むから、以前の処理されたバージョンのリストを破棄して、新しいバージョンの構造を完全に処理するのに徐々に不都合となる。本願にて導入される増分更新アルゴリズムは、古いエレメントを無駄に削除することなく、エレメントの内容における変化を認識し、プロトコルのパフォーマンスを著しく改良する。

本発明は、ノードを監視する方法に関する。該方法は、ノードに関する新しい情報を受信する工程を含む。次に、ノードに関する新しい情報を、ノードに関する古い情報と比較する工程が存在する。次に、古い情報を新しい情報で増分することによって、古い情報を新しい情報に更新する工程が存在する。

本発明は、別のノードを監視する方法に関する。該方法は、ノードのメモリにある少なくとも１つの最初のエレメントを有する、別のノードからの古いパケットを記憶する工程を含む。次に、少なくとも１つの最初のエレメントを有する、該別のノードからの新しいパケットを、ノードが受信する工程が存在する。次に、新しいパケットの最初のエレメントを、古いパケットの最初のエレメントと比較する工程が存在する。次に、もし、新しいパケットの最初のエレメントが古いパケットの最初のエレメントと異なるならば、新しいパケットの最初のエレメントは、メモリにおいて古いパケットの最初のエレメントの前に来る順序で挿入される工程が存在する。

本発明は、通信ネットワークのノードに関するものである。ノードは、自身に関する情報を別のノードへ伝送する手段を具える。ノードは、別のノードに関する情報を受信する手段を具える。また、ノードは、自身および別のノードに関する情報を維持する手段を具える。該維持する手段は、伝送する手段と受信する手段とに接続される。ノードは、別のノードから受信した新しい情報を、以前に別のノードから受信した古い情報と比較して、古い情報を新しい情報で更新する手段を具える。維持する手段は、比較して更新する手段に接続される。

本発明は、通信用のシステムに関するものである。該システムは、ノードを有するネットワークを具える。各ノードは、少なくとも１つの別のノードに接続され、接続されたノードを通じて他の全てのノードと通信する。各ノードは、別のノードと通信する手段を具える。また、各ノードは、自身および別のノードに関する情報を維持する手段を具える。該維持する手段は、通信する手段に接続される。また、各ノードは、別のノードから受信した新しい情報を、以前に別のノードから受信した古い情報と比較して、古い情報を新しい情報で増分することによって、古い情報を新しい情報で更新する手段を具える。

本発明は、通信ネットワーク用のノードに関するものである。該ノードは、自身に関する情報を別のノードに伝送する手段を具える。ノードは、別のノードに関する情報を受信する手段を具える。また、ノードは、自身および別のノードに関する情報を維持する手段を具える。該維持する手段は、伝送する手段と受信する手段とに接続される。ノードは、別のノードから受信した新しい情報を、以前に別のノードから受信した古い情報と比較して、古い情報を新しい情報で更新する手段を具える。維持する手段は、比較して更新する手段に接続される。

図を参照すると、通信用のシステム(10)が示される。ここで、図中の同じ参照数字は、幾つかの図を通じて、特に図２に対して、同様または一致した部分を示す。該システム(10)は、ノード(14)を有するネットワーク(12)を具える。各ノード(14)は、図２のように、少なくとも１つの別のノード(14)に接続されて、接続されたノード(14)を通じて、他の全てのノード(14)と通信する。各ノード(14)は、別のノード(14)と通信する手段(16)を具える。また、各ノード(14)は、自身および別のノード(14)に関する情報を維持する手段(18)を具える。維持する手段(18)は、通信する手段に接続される。また、各ノード(14)は、別のノード(14)から受信した新しい情報を、以前に別のノード(14)から受信した古い情報と比較して、古い情報を新しい情報で増分することによって古い情報を新しい情報で更新する手段(20)を具える。

通信する手段(16)は、自身に関する情報を別のノード(14)に伝送する手段(22)を具えることが望ましい。また、通信する手段(16)は、別のノード(14)に関する情報を受信する手段(24)を具えることが望ましい。維持する手段(18)は、伝送する手段(22)と受信する手段とに接続される。

本発明は、通信ネットワーク(12)に関する。通信ネットワーク(12)は、第１ノード(14a)を具える。第１ノード(14a)は、接続された第２ノード(14b)と通信する手段(16)を具える。また、第１ノード(14a)は、自身、第２ノード(14b)および第３ノード(14c)に関する情報を維持する手段(18)を具える。維持する手段(18)は、通信する手段に接続される。また、第１ノード(14a)は、第２ノード(14b)から受信した新しい情報を、以前に第２ノード(14b)から受信した古い情報と比較して、古い情報を新しい情報で増分することによって、古い情報を新しい情報で更新する手段(20)を具える。

また、通信ネットワーク(12)は、第１ノード(14a)に接続される第２ノード(14b)を具える。第２ノード(14b)は、接続された第１ノード(14a)および第３ノード(14c)と通信する手段(16)を具える。また、第２ノード(14b)は、自身、第１および第３ノードに関する情報を維持する手段(18)を具える。維持する手段(18)は、通信する手段に接続される。また、第２ノード(14b)は、第１または第３ノードから受信した新しい情報を、以前に第１または第３ノードから受信した古い情報とそれぞれ比較して、古い情報を新しい情報で増分することによって、古い情報を新しい情報で更新する手段(20)を具える。

通信ネットワーク(12)は、第２ノード(14b)に接続され、第２ノード(14b)を通じて第１ノード(14a)と通信する第３ノード(14c)を具える。第３ノード(14c)は、第２ノード(14b)と通信する手段(16)を具える。第３ノード(14c)は、自身、第１ノード(14a)および第２ノード(14b)に関する情報を維持する手段(18)を具える。維持する手段(18)は、通信する手段に接続される。また、第３ノード(14c)は、第２ノード(14b)から受信した新しい情報を、以前に第２ノード(14b)から受信した古い情報とそれぞれ比較して、古い情報を新しい情報で増分することによって、古い情報を新しい情報で更新する手段(20)を具える。各ノード(14)は、スイッチまたはルータであることが望ましい。

本発明は、通信ネットワーク(12)用のノード(14)に関する。該ノード(14)は、自身に関する情報を別のノード(14)に伝送する手段(22)を具える。ノード(14)は、別のノード(14)に関する情報を受信する手段(24)を具える。また、ノード(14)は、自身および別のノード(14)に関する情報を維持する手段(18)を具える。維持する手段(18)は、伝送する手段(22)および受信する手段(24)に接続される。ノード(14)は、別のノード(14)から受信した新しい情報を、以前に別のノード(14)から受信した古い情報と比較して、古い情報を新しい情報で更新する手段(20)を具える。維持する手段(18)は、比較して更新する手段(20)に接続される。

伝送する手段(22)は、自身に関するＴＬＶパケット(30)の情報を別のノード(14)に伝送する手段(22)を具えることが望ましい。受信する手段(24)は、別のノード(14)に関するＴＬＶパケット(30)の情報を受信する手段(24)を具えることが望ましい。維持する手段(18)は、自身および別のノード(14)に関するＴＬＶパケット(30)の情報を維持する手段(18)を具えることが望ましい。比較して更新する手段(20)は、別のノード(14)から受信した新しいＴＬＶパケット(30)の情報を、以前に別のノード(14)から受信した古いＴＬＶパケット(30)の情報と比較して、古いＴＬＶパケット(30)の情報を新しいＴＬＶパケット(30)の情報で更新する手段(20)を具えることが望ましい。

本発明は、ノード(14)を監視する方法に関する。該方法は、ノード(14)に関する新しい情報を受信する工程を含む。次に、ノード(14)に関する新しい情報を、ノード(14)に関する古い情報と比較する工程が存在する。次に、古い情報を新しい情報で増分することによって、古い情報を新しい情報で更新する工程が存在する。

更新する工程は、新しい情報が古い情報と異なる場合に、古い情報を新しい情報で増分することによって、古い情報を新しい情報で更新する工程を含むことが望ましい。また、更新する工程は、新しい情報が古い情報と異なる場合に、新しい情報を古い情報に挿入する工程を含むことが望ましい。さらに、更新する工程は、新しい情報に存在しない情報の全てを削除する工程を含むことが望ましい。また、更新する工程は、新しい情報の順番に一致するように、古い情報を配列し直す工程を含むことが望ましい。

本発明は、別のノード(14)を監視する方法に関する。該方法は、ノード(14)のメモリにある少なくとも１つの最初のエレメントを有する、別のノード(14)からの古いパケット(30b)を記憶する工程を含む。次に、図２に示すように、少なくとも１つの最初のエレメント(29a)を有する、該別のノード(14)からの新しいパケット(30a)を、ノード(14)が受信する工程が存在する。次に、図６に示すように、新しいパケット(30a)からの最初のエレメント(29a)を、古いパケットの最初のエレメント(28a)と比較する工程が存在する。次に、図７に示すように、もし新しいパケット(30a)の最初のエレメント(29a)が古いパケット(30b)の最初のエレメント(28a)と異なるならば、新しいパケット(30a)の最初のエレメント(29a)は、メモリにおいて古いパケット(30b)の最初のエレメント(28a)の前にくる順序で挿入される工程が存在する。

古いパケット(30b)は、メモリにある該古いパケット(30b)の最初のエレメント(28a)に続く順序にある、少なくとも１つの第２のエレメント(28b)を有していることが望ましく、新しいパケット(30a)は、該新しいパケット(30a)の最初のエレメント(29a)に続く順序にある、少なくとも１つの第２のエレメント(29b)を有していることが望ましい。更に、図８に示すように、比較する工程の後に、新しいパケット(30a)の第２のエレメント(29b)を、古いパケット(30b)の第２のエレメント(28b)と比較する過程が存在する。

あるいはまた、図１０に示すように、古いパケット(30b)は、メモリにある該古いパケット(30b)の最初のエレメント(28a)に続く順序にある、少なくとも１つの第２のエレメント(28b)を有しており、新しいパケット(30a)は、最初のエレメント(29a)に続く順序の追加のエレメント(29b)を有していない。また、比較する工程の後に、古いパケット(30b)の第２のエレメント(28b)をメモリから削除する過程が存在する。あるいはまた、記憶する工程は、別のノード(14)からの古いＴＬＶパケット(30)を記憶する工程を含むことが望ましい。更に、受信する工程は、少なくとも１つの最初のエレメント(29a)を有する新しいＴＬＶパケット(30)を、ノード(14)が受信する工程を含む。また、比較する工程は、新しいＴＬＶパケット(30)の最初のエレメント(29a)を古いＴＬＶパケットの最初のエレメント(28a)と比較する工程を含む。更に、挿入工程は、もし、新しいＴＬＶパケット(30)の最初のエレメント(29a)が古いＴＬＶパケットの最初のエレメント(28a)と異なるならば、新しいＴＬＶパケット(30)の最初のエレメント(29a)は、メモリにおいて古いＴＬＶパケット(30)の最初のエレメント(28a)の前に来る順序で挿入される工程を含む。前述の記載より分かるように、最初のエレメント及び第２のエレメントは、パケットのどのエレメントのことを言ってもよい。

システム(10)は、リンク状態のルーティングを用い、図３に視覚化されるノード（ルータ又はスイッチなど）のネットワークに適用される。このようなネットワークは、現在幅広く利用されている。図によると、各ルータ／スイッチは、トポロジデータベースを維持して、到着パケットの効率的なルーティング又は接続セットアップの要求を可能にする。適用されたルーティングが獲得する質は、利用できるリンクリソースにおける供給停止や変更など、リンクの状態に変更がある場合、現在のトポロジのビューに基づいて、瞬時にその決定を適合させる各ノードの能力による。この場合、隣接するルータは、その現在のトポロジを表すネットワークをＬＳＵメッセージでフラディングする。リンク状態のルーティングプロトコルにおける「フラディング」パケットの発生及び処理は、非常に時間が重要な問題である。入ってくるパケットは、必要に応じて、トポロジデータベースで処理及び記憶されなければならず、適当であれば、出来るだけ早くフラディングされなければならない。

一般的には、最新のリンク状態のルーティングは、以下の特長を示している。
１）ルーティング最新情報を単一ノードで発生させる周波数は、ネットワーク全体で発生されるＬＵＳの量と比べて低い。
２）パケットは、「リストのリスト(lists-of-lists)」としてエンコードされる。このことは一般には、ＴＬＶをフォーマットすることにより達成されるが、これに限定されるものではない。
３）別のノードからパケットを受信するノードは、常に、フラディングの本質によるエレメントの順番を保ちながら、パケットを再生成できなければならない。エレメントの順番が変えられると、パケットのセマンティクスが変更され、オーセンチケーションに用いられる潜在的サインが無効になる可能性がある。
４）発行された結果的リンク状態最新情報パケットバージョン(issued consequent link state update packet versions)のほとんどは、リストエレメントの内容（リンクに利用できるリソースの量等）の変化だけを保持し、パケットの構造（リンクを追加したり取り外したりすること等）をそれほど大きく変化させない。
５）パケットの構造を変化させることは、プロトコルの内部状態及び処理ロードにおける重要な変化を暗示している。例えば、リンクを表すエレメントを取り外すと、ネットワークにおける内部の到着可能性を再計算する必要が生じる。それとは対照的に、リンクのメトリクス(metrics)等、エレメントに保持される内部最新情報が、プロトコルの状態にとって重要な変化を表すことはあまりない。

方法の記述
表記法
リスト定義
1： エレメントのリスト（このようなリストや、それらのリスト上の異なるオペレーションの複雑さの順番は、コンピュータサイエンスではよく知られており、例えば、(ヌース著, “The Art of Computer Programming”; アール タージャン著, "Data Structures & Network Algorithms", Bell Laboratories, 1991, ISBN 0-89871-187-8)などの多くの所に記載されてきた。
1.el_x： リスト１のエレメントｘ
1.el_x[NEXT]： リスト１内のエレメントｅｌ_ｘの後にくる新しいエレメント
1.el_x[PREV]： リスト１内のエレメントｅｌ_ｘの前にくる以前のエレメント
1.el_x.kids： ｘの子（ｘに埋め込まれている）であるエレメントを指すポインタのリスト
1.el_x.kidsTree： ｘの子の複製リストの木（後で定義する）
1.el_x.property： エレメントは、ＵＳＥＤ又はＮＯＴ_ＵＳＥＤの「プロパティ」でマークできる。

オペレーション
LENGTH(1)： リスト１内のエレメント数を元へ戻す
INSERT(1,el_x,el_y)： エレメントｘを、リスト１のエレメントｙの前に挿入する
REMOVE(1,el_x)： エレメントｘをリスト１から取り外す
FIRST(1)： ポインタをリスト１上の最初のエレメントに戻す
POINTER(el_x)： ポインタを、&ｅｌ_ｘと略記されるエレメントｘに戻す
FREE(el_x)： エレメントｘを壊す
el_x:=el_y： エレメントｘの内容をエレメントｙの内容で更新する。ｅｌ_ｘ==ｅｌ_ｙでなければ無効（後で定義する）
el_x==el_y： エレメントｘの内容は、エレメントｙの内容に等しい。更に、ｘに埋め込まれた子の内容、順番及び数は、ｙに埋め込まれた子の内容、順番及び数に等しい。

ポインタ
定義：
*p： リストのエレメントを指すポインタｐ
NULL： 未定義ポインタ値
オペレータ：
CONTENT(p)： ｐが指すエレメントの内容。*ｐと略記される
p1=p2： ｐ１がポインタｐ２と同じエレメントを指すならば真
p1!=p2： ｐ１=ｐ２でなければ真

プライマリーキー順序づけ
このような順序づけは、異なるエレメントが、リンクやノードなどの異なるタイプの情報を表すという事実のため、常に行われる。同じタイプのエレメントは、それらを区別するリンク又はノードＩＤのような独自のフィールドにより再び識別される。しかし、アルゴリズムは、順序づけが「弱い」ときでも作動し、複製を作製する。しかし、高い割合の複製（順序づけの観点からは、等しいエレメントであるということ）は、木の葉をリストに退化(degenerate)させる原因となり、アルゴリズムの利点を弱める。
#： エレメントのための順序づけ総数
el_l=<el 2： ｅｌ_ｌ#ｅｌ_２が定義されるならば真
el_l>=el 2： ｅｌ_ｌ#ｅｌ_２が定義されるならば真
el_l=el 2： ｅｌ_ｌ=<ｅｌ_２且つｅｌ_ｌ>=ｅｌ_２
el_l<el 2： ｅｌ_ｌ=<ｅｌ_２でｅｌ_ｌ=ｅｌ_２でない
el_l>el 2： ｅｌ_ｌ>=ｅｌ_２でｅｌ_ｌ=ｅｌ_２でない

複製のリスト
定義：
1′： エレメントを指すポインタの空でないリスト。但し、１′におけるｘ、１′における各ｙについて、*ｘ=*ｙは真
オペレーション：
#： 複製リストの順序づけ総数。１′_１#１′_２は、*ＦＩＲＳＴ(１′_１)#*ＦＩＲＳＴ(１′_２)と定義される

木
t#： 順序づけ＃を用い、ｔと略記された複製を指すポインタのリストの２分木若しくは別の種類のアンバランスソートされた又はバランスソートされた木（このような木や、それらの木の上の異なるオペレーションの複雑さの順番は、コンピュータサイエンスではよく知られており、例えば、(ヌース著, “The Artof Computer Programming”; アール タージャン著, "Data Structures & Network Algorithms", Bell Laboratories, 1991, ISBN 0-89871-187-8)などの多くの所に記載されてきた。）

単純な例として、このような木は、２分木、つまり、含まれるエレメントを示すポインタ及び「左右」のポインタにより、各ノードが構成される木として想像することができる。「左」のポインタは、より小さいエレメントを含む木の葉を指し、「右」のポインタは、より大きいエレメントを持つ葉を指す。一例として、以下に概略的に表される式を用いることができる。

このような木は、サーチ操作の順番を減らすのに用いられる。サーチ操作に平均でＮ／２回の比較を要する、Ｎ個のエレメントのソートされていないリストに比べて、バランスがとれた木の上でエレメントを見つけるには、平均でＬＯＧ＿２（Ｎ）ステップかかる（「バランスがとれた」とは、根の左側及び右側にあるエレメントの数が大体同じであるという意味であり、このような条件は、適当な最新のアルゴリズムを用いて確実なものにされる）。
INSERT(t,1′)： １′をｔに挿入せよ
REMOVE(t,1′)： １′をｔから取り外せ
FIND(t,1′)： ｔの上でリスト１′を見つけよ

複雑なオペレーション
MOVE(1,t,*el_x,*el_y)： エレメントｘを指すポインタを、リスト１におけるその現在位置から、エレメントｙを指すポインタの前へ移動せよ。木ｔの上のエレメントｘのプロパティをＵＳＥＤに設定せよ。
INSERT(t,*el_x)： エレメントｘを指すポインタを木ｔ内の複製リストに挿入せよ。複製リストが存在しなければ、まずそれを作製して、木に挿入せよ。プロパティをＵＳＥＤに設定せよ。
REMOVE(t,*el_x)： エレメントｘを指すポインタを、木ｔ内の複製リストから取り外せ。複製リストが空になれば、それを木から取り外せ。
FIND(t,*el_x,property)： 必要とされるプロパティを具えた木ｔの上のエレメント＝ｅｌ_ｘを指すポインタを見つけよ。木の上になければ、ＮＵＬＬに戻る。

入力
この方法は、入力として、パーズされたＴＬＶにエンコードされたパケットを表すエレメントを指すポインタのリストである‘ＬｉｓｔＯｌｄ’、及びこれらのエレメントを指すポインタの複製リストの木である‘ＴｒｅｅＯｌｄ’を受け付ける。指されるリストのエレメントは、それぞれ、埋め込まれたエレメントを指すポインタのリスト（空かもしれない）と、これらのエレメントを指すポインタの木とを同時に含む。リストは、エレメント（これらはリソートできない）の順番を保ち、木は、変化しなかったエレメントを見つけるするための速いサーチを許す。全てのエレメントは、ＮＯＴ＿ＵＳＥＤのプロパティが設定されている。第２の入力である‘ＬｉｓｔＮｅｗ’として、新しい、パーズされていないパケットを表すエレメントを指すポインタが提供される。リストのエレメントは、埋め込まれたエレメントの木を含まず、リストは、含まれたエレメントの順番の後で初めてトラバースされる。これによって、パーズされていない「生の」パケットを入力として用いることが可能になる。このようなパケットは、一般的に、図３に表される最新のリンク状態のルーティングプロトコルを実行する装置のインターフェース上で受信されている。
定義：
ListOld: エレメントを指すポインタのリスト
ListNew: エレメントを指すポインタのリスト
TreeOld: 複製リストの木

出力
この方法は、ＴＬＶでエンコードされたパケットの以前のバージョンを表すリストから、その新しいバージョンを、迅速に、増分的に発生させるものである。新しい表示は、各エレメントの中に、埋め込まれたエレメントのリストだけでなく、その木も含んでいる。この特長により、パケットの新しいバージョンが増分的に再びパーズされる必要があるとき、この方法の出力をその入力として用いることが可能になる。
方法：
インカップデイト(INCUPDATE)
001 (INPUT/OUTPUT ListOld : エレメントを指すポインタのリスト;
INPUT ListNew : エレメントを指すポインタのリスト;
INPUT/OUTPUT TreeOld : 複製リストの木;)
005 定義：
Found: エレメントを指すポインタ;
InsertP: エレメントを指すポインタ;
RunnerNew: エレメントを指すポインタ;
コード：
010 InsetP:=FIRST(ListOld);
RunnerNew:FIRST(ListNew);
WHILE RunnerNew!=NULL DO
BEGIN
Found:=NULL;
015 Found:=FIND(TreeOld,RunnerNew,NOT USED);
IF Found!=NULL THEN
BEGIN
IF Found = InsertP THEN
BEGIN
020 InsertP := *InsertP[NEXT];
ELSE
MOVE(ListOld,TreeOld,Found,InsertP);
END IF;
END IF;
025 IF NOT *Found == *RunnerNew THEN
BEGIN
*Found:=*RunnerNew;
INCUPDATE(*Found.kids,
*RunnerNew.kids,
030 *Found.kidsTree );
END IF;
*Found.property=USED;
ELSE
INSERT(OldList,RunnerNew,InsertP);
035 INSERT(OldTree,RunnerNew);
END IF;
RunnerNew := *RunnerNew[NEXT];
END WHILE;
WHILE InsertP!=NULL DO
040 REMOVE(OldList,InsertP);
REMOVE(OldTree,InsertP);
FREE(InsertP);
InsertP:= *InsertP[NEXT];
END WHILE;

動作の例
この章では、所定アルゴリズムの動作を、いくつかの簡単な図面を用いて図解している。全ての事例をカバーしているが、アルゴリズムの再帰的構造だけは、エレメントの新しいバージョンの内容は古いバージョンの中に同じく維持されていると仮定しているので、省略している。これは前記所定アルゴリズムの２５−３０行目はカバーしないが、マップしている。含まれているエレメントの一次キーの全部が一意的であって、従って同じ一次キーのエレメントの待ち行列の木にではなく、２分探索樹（binary search）へ縮退する場合には、更にＴｒｅｅＯｌｄ木が示される。

図面は頁の上部には、古い、パーズしたバージョンのデータ構造を示し、頁の下部にはパケットの新しい、パーズしないバージョンを示している。パーズされたバージョンは、元のパケット中のシーケンスを維持しているエレメントの待ち行列と、迅速な検索に使用され、更新工程の間、使用済と未使用のエレメントを記録している木とから構成される。図面のシーケンスは、アルゴリズムによって実行される工程と、それが適当な構造に及ぼす影響を説明する。図面自体は、リストと、ポインターと、パケットを所定プロトコルの速やかな理解のため、かなり概略的に示している。＃が意味している関係、即ち旧パケットのエレメント１に対する関係と、新パケットのエレメント１’に対する関係で、１＝１’が真のとき、エレメントは同じパターンで満たされる。やや単純化しすぎた表現であるが、同一パターンのエレメントは、「同一」のエレメントである。

図１は、コンピュータの記憶部の実際の構造に基づいて、図５の一部を理解できる限り図解したものである。「エレメント」の構造は、リンク状態のプロトコルの場合、恐らくはリンクを表している。リンクはここでは一意的にポートで特定されており、遠隔ノードは、「エレメント形式」の値で成分を示す。エレメントのリストを作るため、「前のエレメント」と「次のエレメント」の成分が使われる。リストは再帰的であるから、成分「子（複数）」は、各構造において埋め込まれたエレメントの予想されるリストを示している。「木」と名付けた索引付け構造は、索引の付いたエレメントのポインターで構成され、「左の子」と「右の子」の２つのポインターは迅速な検索のための２分検索木を形成する。図面の下部は、パケットの新たに到着したバージョンを図解しており、再帰的ではないからコンピュータの記憶部ではバイトのシーケンスで示されている。形式１のエレメントは図面上部の待ち行列に記憶された第１エレメントと同一であるから、認識され形式２の次のエレメントがそれに続く。最終的にアルゴリズム中でポインターとして働く異なった変数は、適当な形式に対するポインターとして示される。

図２には、古く、再帰的バージョンのパケットが、父エレメント１中に子らを囲んでいない４エレメントを含んでいるとき、スタート状態が示されている。エレメントの待ち行列と、検索に使われる木構造が示される。更新工程では、全てのエレメントは「未使用」であり、それ故木エレメント（tree elements）は、一致するリストエレメント（list elements）をポイントする。アルゴリズムの「Ｐを挿入」と「Ｒｕｎｎｅｒ Ｎｅｗ」の両方のポインターは、適当なパケットバージョンの第１エレメントに初期化される。この図面では、新パケットの１つのエレメントが、リストの上で、そして旧パケットの同じ場所に見つかる場合をカバーしている。アルゴリズムは１６〜１８行目の枝を真であると認定する。図６は新しいパケットバージョンの第１エレメントの処理後の状況を示す。木「Ｔｒｅｅ Ｏｌｄ」エレメントが、その特性を「ＵＳＥＤ」へ変えることによって行う検索には、もはや使用されない場合を除いて、古いパケットのどの部分も変化しない。図面はこの事実を、エレメントのリスト中からポインターをなくすることによって示している。この図面は、全く新しいエレメントがパケットの新バージョン中に見い出され、そして「Ｐを挿入」の前で、木の上に挿入された場合に該当する。これはアルゴリズム中で１６行目の枝によって、それ自身が偽であることを証明している。

図７は、その後のデータ構造を示しており、既知のエレメントがパケット中の新しい位置へ現れる場合を含んでいる。１６行目の枝は真であり、１８行目は偽である。移動したエレメント１．３は木上へＵＳＥＤのマークを施す。

図８は図１と同等な場合を含んでいる。

図９は図６と同等な場合を含んでいる。

図１０は、３９行目からスタートするループの機能を示している。新バージョンにはもはや存在しない、旧パケット中のエレメントは、すべてリストの最後から押し出され抹消される。本件の場合、エレメント１．４だけがリスト、そしてキーから取り除かれる必要がある。

図１１は、アルゴリズムが終了した後のデータを示している。リストは、新パケットの構造を表し、全部のエレメントは木「Tree Old」の上にあって、USEDのマークが付される。

シーケンスになって到着するパケットの最適化
リンク状態のプロトコルを使用し、リンク状態に続く次のバージョンの通常状態で動作するネットワークでは、パケットはギャップを開けずに、シーケンスになって到着する。リンク状態パケットのあらゆるバージョンが、各エレメントにビットを設定し、エレメント自体又はそこへ埋め込まれた任意のエレメントが、最終のバージョンから変更したか否かを表示しているときは、２５行目の比較は省略できると仮定する。例えばバイト方向( bite-wise )へ２つのバージョンの同一エレメントの内容を比較することに代えて、パーズ木( parser )の実行を著しく改良できる１つのビットを記載するだけでよい。

以下の説明は、上記したアルゴリズムのいくつかの可能な応用を追加説明するものである。

１：方法を、特にリンク状態のルーティング( routing )プロトコルへ適用した。そして、一般的にはリスト中のリストを使って、任意のコンピューターへの応用に適用した。この場合、ノード又はコンピューターを追加する必要はない。ノード自体、又はコンピューター自体にリストが存在する。リストは、ノード又はコンピューターの記憶部に、データ構造の形式で格納されている。新リストが入ってきて、ノード又はコンピューターのメモリー中に既にあるリストと、どのように相違するか判断する必要が生じたとき、上記したアルゴリズムは、旧リストのエレメントを上記した新リストのエレメントによって増分させ、旧リストのエレメントを新リストのエレメントに更新する。例えば、ネットワーク中の他のノード又はコンピュータに関する情報を格納したパケットの代わりに、リストは、コンピューター援助図面に関する情報を収容でき、新リストは、コンピューター援助図面に関する情報を備えたノード又はコンピューターに収容される。上記したパケット情報が、実行又は更新されたのと実質的に同じように、新リストによって、旧リストを増分することによって、新リストは旧リストの更新に使用される。

２：パケット形式が拡張された、方法を使用して、あるエレメントと、埋め込まれた全エレメントは変更されないで、パケットバージョンがシーケンスとなっていつ到着するのかを、又はその中のどれが変更されたかを表示する。前述した追加的に可能な応用の中で記載したとおり、上記アルゴリズムを有する一つのノード又はコンピューターが必要となるにすぎない。この場合には、アルゴリズムはエレメントの何れかのアスペクトが変更されたか否かの判断に使用される。その判断は、例えば、パケット中の所定位置にあるバイトであって、該バイトに関連する１或いは複数のエレメントが、ノード或いはコンピュータのメモリ中に既に存在するパケットの１或いは複数のエレメントと同一か否かを表示するバイトを観察して行う。もしバイトが変更なしを示す値であるとき、アルゴリズムは次の１或いは複数の次のバイトに対して、直ちに実行する。もしそのバイトが、エレメント中に変更があることを示すときは、アルゴリズムは新しい１或いは複数のエレメントを、既に存在する位置へ、又は複数のエレメントと比較し、旧の１或いは複数のエレメントを、新の位置又は複数のエレメントによって増分し、旧の位置又は複数のエレメントを更新する。このようにして、位置又は複数のエレメントの検査が、例えばスイッチによって進めることができる。

３：使用済み( USED )特性の代わりに、二つの木を用いる方法を使用する。その場合、１５行目の各エレメントは、新しい木にコピーされ、特性を変更する代わりにTree Oldから削除される。アルゴリズムの終わりには、新しい木は、空のTree Oldと置き換わる。木に挿入し削除するある種のシナリオは非常に安価であるが、しかし、検索費用は木が大きいときにはかさむ。しかし、この技術はアルゴリズムを改良することができる。

４：エレメントの検索と比較を高速に行う木の代わりに、ハッシュ又は他の形式の符号付け構造の方法を使用する（ヌース著「コンピュータープログラム技術」ADIS.WESL.1973）。この場合、ハッシュ又は他の形式のインデックス構造の使用は、アルゴリズム中の２分木を、最高の検索と、再吟味中のエレメントの比較のためのものに置き換える。これはエレメントが、ノードあるいはコンピューターのグループ、又は単一のノード又はコンピュータに関するものか否かにかかわらず、任意の形式のリスト又は、パケット化されたエレメントの情報について起こりうる。

解説のための上記実施例について本発明を詳しく説明したが、その詳細説明は単に上記目的のためであること、そして当業界において通常の知識を有する者であれば、特許請求の範囲に記載された発明以外は、発明の思想と範囲から離れることなく実施変更が可能なことは理解されるべきである。

本発明のノードの概要図である。 複数のノードを有するシステムの概要図である。 ＴＬＶパケットの例である。 古いパケットを新しいパケットと比較する概要図であり、ここで、比較されるエレメントは、同じ位置の同じものである。 本発明に関して可能なメモリ構造の概要図である。 古いパケットを新しいパケットと比較する概要図であり、ここで、比較されるエレメントは、古いパケットに関する新しいエレメントである。 古いパケットを新しいパケットと比較する概要図であり、ここで、新しいパケットにおいて古いパケットと同じエレメントが新たな位置に存在する。 古いパケットを新しいパケットと比較する概要図であり、ここで、比較されるエレメントは、同じ位置の同じものである。 古いパケットを新しいパケットと比較する概要図であり、ここで、比較されるエレメントは、新しいパケットの最後にある新しいエレメントである。 古いパケットを新しいパケットと比較する概要図であり、ここで、新しいパケットにて現れない古いパケットのエレメントは、古いパケットの最後にあって、削除される予定である。 古いパケットを新しいパケットと比較する概要図であり、ここで、古いパケットは、増分変換を行なった後の新しいパケットと一致する。

符号の説明

(10)通信システム
(12)通信ネットワーク
(16)通信する手段
(18)情報を維持する手段
(20)古い情報を新しい情報で更新する手段
(22)伝送手段
(24)受信手段
(30)ＴＬＶパケット

Claims (2)

1. 複数のノードであって、各々のノードがそれら複数のノードに関するトポロジーデータベースを保持している複数のノードと、
   複数のノードが、リンクステートプロトコルを用いてＴＬＶパケットでお互いに通信するネットワークとを具えており、
   ＴＬＶパケットは、リストのリストとしてエンコードされたエレメントのシーケンスを有しており、
   各ノードは、その他のノードからＴＬＶパケットを受信して、そのＴＬＶパケットを再生成し、そのエレメントのシーケンスを保ち、
   複数のノードは、エレメントの内容に関して変化だけを保持する結果的リンク状態更新ＴＬＶパケットを送信し、
   各ノードは、パーズされたＴＬＶでエンコードされたパケットを表し、エレメントを指すポインタのリストと、パーズされたＴＬＶでエンコードされたそのパケットのそれらエレメントを指すポインタの複製リストの木とを入力として受け付け、それらポインタによって示されるリストのエレメントの各々は、埋め込まれたエレメントを指すポインタのリストと、それら埋め込まれたエレメントを指すポインタの木とを含んでおり、ポインタのそのリストはエレメントのシーケンスを保っており、その木は、変化がないエレメントを探す検索に用いられ、
   各ノードは、パーズしていない新たなパケットを表し、エレメントを指すポインタのリストを更に入力として受け入れ、エレメントの内容に関する変化を用いて、パーズしたＴＬＶでエンコードされたパケットを表すエレメントを指すポインタのリストから、パーズしていないパケットを表す、エレメントを指すポインタのリストの新しいバージョンを生成し、
   新しいバージョンのエレメントの各々は、埋め込まれたエレメントのリストと、それら埋め込まれたエレメントの木とを有しており、複数のノードは、前記新しいバージョンをその他のノードに送って、その他のノードはそれらのトポロジーデータベースを更新する電気通信システム。
2. 複数のノードの各々のノードが、それら複数のノードのトポロジーに関するトポロジーデータベースを保持する工程と、
   リンクステートプロトコルを用いて、リストのリストとしてエンコードされたエレメントのシーケンスを有するＴＬＶパケットで複数のノードが互いに通信するネットワークを通じて、各ノードがその他のノードからＴＬＶパケットを受信する工程と、
   各ノードが、受信したＴＬＶパケットを再生成し、エレメントのシーケンスを保つ工程と、
   前記複数のノードが、エレメントの内容に関して変化だけを保持する結果的リンク状態更新ＴＬＶパケットを送信する工程と、
   パーズされたＴＬＶエンコードパケットを表すエレメントを指すポインタのリストと、そのパーズされたＴＬＶエンコードパケットのそれらエレメントを指すポインタの複製されたリストの木とを、各ノードが入力として受け付ける工程であって、それらポインタで示されるそのリストのエレメントの各々は、埋め込まれたエレメントを指すポインタのリストと、それら埋め込まれたエレメントを指すポインタの木とを含んでおり、ポインタのそのリストは、エレメントのシーケンスを保っており、その木は、変化がないエレメントを見つける検索に用いられる工程と、
   さらに、パーズされていない新たなパケットを表すエレメントを指すポインタのリストを、各ノードが入力として受け付ける工程と、
   各ノードが、エレメントの内容の変化を用いて、パーズされたＴＬＶエンコードパケットを表すエレメントを指すポインタのリストから、パーズされていないパケットを表すエレメントを指すポインタのリストの新しいバージョンを生成し、新しいバージョンのエレメントの各々は、埋め込まれたエレメントのリストと、それら埋め込まれたエレメントの木とを有している工程と、
   前記複数のノードは、前記新しいバージョンをその他のノードに送って、その他のノードはそれらのトポロジーデータベースを更新する工程とを含む電気通信方法。

Images