(57)【要約】本発明は、複数のノードを備える動的ネットワークに関し、ルーティング情報がネットワークのノードにおける局所ルーティングテーブルに記憶され、これらノードは、他のノードへ前記局所ルーティングテーブルを更新するための更新要求を送り、アドレスされたノードは、要求する側のノードへ、更新応答を、更新されたルーティング情報と共に送る。
2004521561.tif 000002
【特許請求の範囲】
【請求項１】
複数のノードを備える動的ネットワークにおいて、
−ルーティング情報は、前記ネットワークのノードにおける局所ルーティングテーブルに記憶され、
−前記ノードは、他のノードに前記局所ルーティングテーブルを更新するための更新要求を送り、及び
−アドレスされたノードは、前記要求する側のノードへ、更新応答を、更新されたルーティング情報と共に送る、
ことを提供する動的ネットワーク。
【請求項２】
請求項１に記載のネットワークにおいて、前記テーブルはターゲットノードのための領域を有し、前記局所ルーティングテーブルは、当該局所ルーティングテーブルの最新の更新に関するテーブル更新情報と、個々の領域の最新の更新に関する領域更新情報とを含み、前記更新要求は、前記テーブル更新情報を含み、及び前記更新応答は、前記アドレスされたノードの前記領域更新情報が前記要求する側のノードの前記テーブル更新情報よりも新しい局所ルーティング情報の項目を含むことを特徴とするネットワーク。
【請求項３】
請求項１に記載のネットワークにおいて、前記局所ルーティングテーブルは、前記ターゲットノードのための領域を含み、前記領域は、前記ネットワークトポロジの変更の新しさを特徴とするトポロジ変更情報を含むことを特徴とするネットワーク。
【請求項４】
請求項３に記載のネットワークにおいて、前記更新要求は、前記トポロジ変更情報を含み、前記アドレスされたノードから前記更新応答を入力した後の前記要求する側のノードは、前記アドレスされたノードの前記トポロジ変更情報が前記要求する側のノードの前記トポロジ変更情報よりも新しい場合、前記局所ルーティングテーブルの更新を実行することを特徴とするネットワーク。
【請求項５】
請求項１に記載のネットワークにおいて、前記テーブル更新情報及び／又は領域更新情報並びに／若しくはトポロジ変更情報は時間情報の項目であることを特徴とするネットワーク。
【請求項６】
請求項１に記載のネットワークにおいて、前記テーブル更新情報及び／又は前記領域更新情報並びに／若しくは前記トポロジ変更情報は、シーケンス番号により構成されることを特徴とするネットワーク。
【請求項７】
請求項１に記載のネットワークにおいて、前記アドレスされたノードから前記更新応答を入力した後の前記要求する側のノードは、前記アドレスされたノードのトポロジ変更情報が前記要求する側のノードのトポロジ変更情報と同じ新しさであり、前記それぞれのターゲットノードへのパス長が前記更新により短くなる場合、前記局所ルーティングテーブルの前記更新を実行することを特徴とするネットワーク。
【請求項８】
請求項１に記載のネットワークにおいて、前記アドレスされたノードから前記更新応答を入力した後の前記要求する側のノードは、前記アドレスされたノードの前記トポロジ変更情報が前記要求する側のノードのトポロジ変更情報と同じ新しさであり、予想されるターゲットノードへの前記最大のデータ送信レートは前記更新により高くなる場合、前記局所ルーティングテーブルの前記更新を実行することを特徴とするネットワーク。
【請求項９】
請求項１に記載のネットワークにおいて、前記ネットワークは、前記サブネットワークを制御する制御器を各々含む数個のサブネットワークに再分割されることができ、前記サブネットワークは、それぞれのフォワーディング端末を用いて相互接続され、及び各制御器は、前記それぞれのサブネットワーク用の中央ルーティングテーブルを記憶及び管理するように設計されることを特徴とするネットワーク。
【請求項１０】
複数のノードを有する動的ネットワークに対するルーティング方法において、
−ルーティング情報は、前記ネットワークのノードにおける局所ルーティングテーブルに記憶され、
−前記ノードは、他のノードへ前記局所ルーティングテーブルを更新するための更新要求を送り、及び
−アドレスされたノードは、前記要求する側のノードへ、更新応答を、更新されたルーティグ情報と共に送る、
ことを供給するルーティング方法。
【請求項１１】
動的ネットワークに対するノードにおいて、
−ルーティング情報は、局所ルーティングテーブルに記憶され、
−前記ノードは、他のノードへ前記局所ルーティングテーブルを更新するための更新要求を送り、及び
−前記ノードは、他の要求する側のノードへ、更新応答を、更新されたルーティング情報と共に送る、
ことを供給するノード。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、動的ネットワーク及び動的ネットワーク用のルーティング方法に関する。
【０００２】
動的ネットワークは、トポロジ（形態）が動作中に動的に変更可能なネットワークであると理解される。これは特に、アドホック（ａｄ ｈｏｃ）ネットワークを含んでいる。アドホックネットワークは、その構成及び加入者の数が所与の制限値内に定められない自己組織型ネットワークであると理解される。例えば加入者の通信装置がこのネットワークから取り去られても、ネットワークに含まれてもよい。従来の移動電話ネットワークと比べ、アドホックネットワークは固定的に設置されたインフラ（ｉｎｆｒａｓｔｒｕｃｔｕｒｅ）に基づいていない。
【０００３】
しかしながら、動的ネットワークは代わりに例えば動作中にトポロジが変更するインターネットネットワークでもよい。
【０００４】
【従来の技術】
上記アドホックネットワークは、Ｃ．Ｅ． Ｐｅｒｋｉｎｓ著の書籍「Ａｄ Ｈｏｃ Ｎｅｔｗｏｒｋｉｎｇ」Ａｄｄｉｓｏｎ Ｗｅｓｌｅｙ、５３〜６２頁から既知である。この既知のネットワークにおける各ノードは、ルーティング情報をネットワークトポロジの変更に順応させるために、このルーティング情報の更新を定期的な間隔で隣接するノードに送る。
【０００５】
【発明が解決しようとする課題】
本発明の目的は、ネットワークトポロジが変更する場合、改良されたルーティングを可能にさせる冒頭に記載の種類のネットワークを提供することである。本発明の他の目的は、関連するルーティング情報を示すことである。
【０００６】
ネットワークに関し、本目的は、複数のノードを備える動的ネットワークを用いて達成され、このネットワークにおいて、
−ルーティング情報は、ネットワークのノードにおける局所ルーティングテーブルに記憶され、
−前記ノードは、他のノードに前記局所ルーティングテーブルを更新するための更新要求を送り、及び
−アドレスされたノード（ａｄｄｒｅｓｓｅｄ ｎｏｄｅ）は、前記要求する側のノードへ、更新応答を、更新されたルーティング情報と共に送る、
ことを提供する。
【０００７】
本発明によるネットワークにおいて、ルーティング情報はネットワークのノードに記憶される。ルーティング情報は、分散化型ネットワークの場合、好ましくは全ノードに記憶される。ルーティング情報は、中央制御器を備えるクラスタネットワークの場合、好ましくは中央ノードだけに記憶される。
【０００８】
このルーティング情報は、ルーティングテーブル形式で記憶される。好ましくはノードのルーティングテーブルは、ネットワークの他の全てのノード又は当該ノードからアクセス可能なノードに対する領域を有する。所与のノードからアクセス可能なノード、すなわち送信が可能又は送信が望まれるノードは、ターゲットノードと表される。
【０００９】
個々のターゲットノードへのデータ送信が行われるに介する例えば次のノード（次のホップ）の領域に記憶されるルーティング情報は、ターゲットノードへのパス長でも、ターゲットノードへの最大の送信容量でもよい。
【００１０】
局所ルーティングテーブルを最新に保つために、好ましくはルーティングテーブルを持つノードは、定期的な間隔で他のノードに更新要求を送る。これら他のノードは、特に隣接するノードである。これら他のノードは、中央制御器を備えるクラスタネットワークの場合、特に隣接する制御器である。
【００１１】
前記更新要求は、この要求を入力するノードにノードが更新されたルーティング情報を前記要求する側のノードに送るべきことを知らせる。
【００１２】
要求の仕組みの利点は特に、この要求の仕組みがルーティング情報の結合送信を可能にすることである。個々のノードは、要求時にのみ修正されたルーティング情報を送信する。要求する場合、幾つかのトポロジの変更、すなわち２つの要求の間に起きたトポロジの変更が、要求する側のノードへ一緒に送られる。それに従って、単一のプロトコルデータユニット（ＰＤＵ）において、ネットワークトポロジにおける幾つかの変更は、要求する側のノードへ送られることができる。これは、ルーティングを目的として送信されるＰＤＵ（パケット）数の減少となる。
【００１３】
【課題を解決するための手段】
本発明は、局所ルーティングテーブルを更新するために送信されるべきデータの品質は、個々のノードが他のノードからルーティング情報を要求するので減少するという考えに基づいている。
【００１４】
請求項２に規定されるような本発明の有利な実施例は、要求する側のノードのルーティング情報を最新にする方法をアドレスされたノードに知らせるという考えに基づいている。これは、要求する側のノードへ送られるべきルーティング情報をアドレスされたノードに選択可能にさせる。これらのルーティングデータがその瞬間までの要求する側のノードのルーティング情報よりも新しい度に、これらルーティングデータは単に要求する側のノードに送信される。
【００１５】
本目的のために、局所ルーティングテーブルは、テーブル更新情報及び領域更新情報を含む。テーブル更新情報は、局所ルーティングテーブルを最新にする方法、すなわちルーティングテーブルの最新の変更が適用されたときのデータを含む。これは、例えば時間指標又はシーケンス数でもよい。領域更新情報は、ルーティングテーブルの個々の領域を最新にする方法、すなわちルーティングテーブルの個々の領域に最新の変更が適用されたときのデータを含む。この領域更新情報は再び、時間指標又はシーケンス数でもよい。これによって、テーブル更新情報は、個々のルーティングテーブルの最新の領域更新情報に対応する。
【００１６】
更新要求は、前記要求する側のノードのテーブル更新情報を含む。これは、前記要求する側のノードへ送られるべきルーティング情報をアドレスされたノードが選択することを可能にする。このアドレスされたノードは、前記要求する側のノードのルーティングテーブルを最新にする方法、すなわち前記要求する側のノードのルーティングテーブルにおいて最新の変更が行われたときを前記要求する側のノードのテーブル更新情報から知る。アドレスされたノードは、テーブル更新情報より新しい局所ルーティング情報だけを含む更新応答を前記要求する側のノードへ送る。テーブル更新情報が時間指標である場合、時間的に新しいルーティングデータだけが送信される。ルーティング情報の選択は、要求する側のノードのテーブル更新情報とアドレスされたノードのルーティングテーブルの領域の個々の領域更新情報とを比較することで行われてよい。送信されるルーティング情報の上記選択は、個々のノード間のルーティングに対し送信されるべきデータ量を減少させる。効率的なルーティング方法はこのようにして実施されることができる。
【００１７】
テーブル更新情報をアドレスされたノードへ送信することは、このテーブル更新情報が僅かな送信容量しか必要とせず、このテーブル更新情報の１つの項目だけが各ルーティングテーブル又はノードに送信されるという利点を有する。これにより、更新要求は、僅かな送信容量しか占有しない。これは特に、無線ネットワークの場合に有利である。
【００１８】
請求項３に規定されるような本発明の有利な実施例において、局所ルーティングテーブルはトポロジ変更情報を含んでいる。ネットワークトポロジの変更の新しさは、トポロジ変更情報を特徴とすることができるので、ネットワークトポロジの変更がネットワークで起きたときを示すことができる。好ましくは、局所ルーティングテーブルの各領域がトポロジ変更情報の項目を含む。これは、例えば時間指標又はシーケンス数でもよい。ネットワークトポロジの変更に関する情報がネットワークの個々のノードにわたり配布されるまでに幾らか時間を要するので、この情報を後で入力する各ノードにおいて、この情報がそれにとって新しいか、この情報を既に記憶しているか、又は例えば異なるノードから情報の新しい項目を既に受け取ったためにこの情報は既に不用であるかを識別することが可能である。これに従って、トポロジ変更情報は、局所ルーティングテーブルの効率的な更新を実行することを可能にさせる。
【００１９】
これは、請求項４に規定されるような発明の有利な実施例において、更新応答は、トポロジ変更情報を有し、局所ルーティングテーブルの個々の領域の更新は、アドレスされたノードのトポロジ変更情報が要求する側のノードのトポロジ変更情報より新しい場合に実行されることが達成される。更新要求を隣接するノードへ送信するノードは、これにより、応答を受信した後、選択的更新を実行する。要求する側のノードの個々の領域を更新することは、ネットワークトポロジにおける多くの新しい情報又は多くの最新情報がこれにより得られる場合に実行される。
【００２０】
アドレスされたノードのトポロジ変更情報が要求する側のノードのトポロジ変更情報と同じ新しさである場合、請求項７に規定されるような本発明の有利な実施例に従って、個々のターゲットノードへのパス長が更新毎に短くなる場合、この更新が実行される。
【００２１】
請求項８に規定されるような本発明の有利な実施例において、アドレスされたノードのトポロジ変更情報が要求する側のノードのトポロジ変更情報と同じ新しさであり、個々のターゲットノードへの最大のデータ送信レートが更新毎に大きくなる場合、この更新が実行される。
【００２２】
請求項７及び８に規定されるような本発明の有利な実施例が組み合わされてもよく、この場合、請求項７の条件又は請求項８の条件は、アプリケーションに依存して高い優先度を与えられてもよい。
【００２３】
請求項５の実施例は、時間情報がルーティング情報の個々の項目の新しさと無関係に比較することを可能にさせる。
【００２４】
請求項６に規定されるようなシーケンス数を持つ実施例は、特に簡単なやり方で実現されることができる。
【００２５】
それぞれのサブネットワーク用のルーティングテーブルを中央ノードに集中的に記憶するようにクラスタ（サブネットワーク）を制御する中央ノード（制御器）を持つ中央クラスタネットワークの場合に有利である。個々のサブネットワーク間の情報の送信は、ブリッジノード又はフォワーダーを介して行われる。
【００２６】
この方法に関する本発明の目的は、請求項１０の特徴をもつ方法を用いて達成される。
【００２７】
【発明の実施の形態】
本発明の幾つかの実施例は、図１から図６を含む図を参照し、以下に詳細に説明される。
【００２８】
図１は、ネットワークのルーティングノード又はステーションに記憶されるルーティングテーブルを示す。このルーティングテーブルは、全ネットワークの各ステーションに対し領域Ｔ１からＴＮと、テーブル更新情報としての時間ｔｕｐ、すなわちルーティングテーブルが最後に変更した時間とを有する。このネットワークの各個別のステーションの領域Ｔ１からＴＮは、６個の副領域１から６を有する。第１の副領域１は、それぞれのターゲットステーションの識別番号（ＩＤ）を含む。第２の副領域２は、第１の副領域１のターゲットステーション向けのデータが与えられる当該ステーションのＩＤを記憶する。これにより、いわゆる“次のホップ（ｎｅｘｔ ｈｏｐ）”である各々可能なターゲットステーションがターゲットステーションに近づく途中に常に記憶される。ターゲットステーション自体がネクストホップである場合、ターゲットステーション自体が第２の副領域２に入力される。第３の副領域３がトポロジ変更情報として領域の発生時間ｔｇｅｎを記憶する。この発生時間ｔｇｅｎは、この領域、すなわちこのターゲットステーションに対するネットワークトポロジに変更が起きたときを示す。ネットワークトポロジの変更を検出し、続いてその局部ルーティングテーブルの領域のコンテンツを変更させるステーションによって定められる。第４の副領域４は、時間ｔｒｅｇを含む。これは、領域のコンテンツの変更がネットワークトポロジの変更のせいでルーティングテーブルにおける個別のステーションにより採用される又は隣接するステーションによって知らされる変更が採用されたときを示す。第５の副領域５の各領域は、例えばターゲットステーションまでの残りのパス長のような量を含んでいる。他の量は、各領域の追加の副領域に記憶されてもよい。第６の副領域は、データがターゲットステーションに送信されることが可能な最大のデータレートを含む。このデータレートは、関連するステーションからターゲットステーションへの全ての構成パスの最大のデータレートに対応する。
【００２９】
ルーティングテーブルを常に最新に保っておくために、このルーティングテーブルを更新する更新（ＵＰＤＡＴＥ）手順が供給される。このＵＰＤＡＴＥ手順は、要求−応答構造に基づいている。各ルーティングステーションは、定期的にこの更新手順を初期化する。以後はＵＰＤＡＴＩＮＧステーション（ＵＳ）と呼ばれるこのステーションは、ＵＰＤＡＴＥ ＲＥＱＵＥＳＴメッセージを放送モードで、すぐ隣の（ルーティング）ステーションに送信する。このＵＰＤＡＴＥ ＲＥＱＵＥＳＴメッセージは、時間ｔｕｐ、すなわち要求する側のステーションの最新のテーブルを更新する瞬間を含んでいる。
【００３０】
ＵＰＤＡＴＥ ＲＥＱＵＥＳＴを受信したとき、隣接するステーションは、入力時間ｔｕｐとそれ自身のルーティングテーブルにおける個々のエントリそれぞれの登録時間ｔｒｅｇとを比較する。この比較を終えたとき、各隣接するステーションは、要求する側のステーションＵＳに（おそらくはセグメント化された）ＵＰＤＡＴＥ ＲＥＳＰＯＮＳＥメッセージを送り、このメッセージにおいて、個々のルーティングテーブルの全てのエントリが含まれ、これらエントリは、瞬間ｔｕｐの後、すなわちｔｒｅｇ＞ｔｕｐが真である瞬間に前記テーブルに入力されている。この時間ｔｕｐは、時間ｔｒｅｇとｔｕｐとが比較される前に、それぞれの隣接するステーションのクロックシステムに通例では変換されるべきであることに注意すべきである。これによって必要とされるこの状況及びステップは、一般的なルーティング手順を記載した後、明らかになる。要求する側のステーションＵＳとは無関係であるために、次のホップ端末ＩＤ及び登録時間ｔｒｅｇを除き、全ての領域が送信されるべきエントリの各々に対し送信される。
【００３１】
ＵＰＤＡＴＥ ＲＥＳＰＯＮＳＥを受信したとき、前記ＵＳは、入力されたエントリの発生時間及び量をその瞬間にそれ自身のルーティングテーブルにあるエントリの発生時間及び量と比較する。
【００３２】
新しく入力されたエントリ又は領域は、ここで“ｎｅｗ”を意味し、その瞬間まで得ている要求する側のステーションのエントリは“ＵＳ”を意味する。“ＰＬ”は、図１で明らかであるようなパス長を意味し、“ＭＴＲ”は最大の転送レートを意味する。ＭＴＲＵＳ−ＮＳは、要求する側のステーションと返答する側の隣接するステーションとの間の最大の送信レートを意味する。類推によって、ＰＬＵＳ−ＮＳは、要求する側のステーションＵＳと隣接するステーションＮＳとの間のホップの数を意味する。これは、全てのステーションがルーティングデータを供給するわけではないと考えられるからである。これによって、ルーティング手順の意味における隣接する２つのルーティングステーションは、１つ又は幾つかの非ルーティングステーションを介して互いに伝達している。
【００３３】
本発明によれば、ＵＳは単に以下の規準を満たすエントリを実行するだけである。
【数１】
2004521561.tif 000003
【００３４】
入力されたエントリに対するＵＰＤＡＴＥ規準が一旦満たされたら、その瞬間までの幾つかの領域のコンテンツは以下のように置き換えられる。
・次のホップ端末ＩＤが関連する隣接するステーションと置き換えられる。
・新しいエントリの発生時間は、
【数２】
2004521561.tif 000004
を採用する。
・新しいパス長は、ＰＬＵＳ＝ＰＬｎｅｗ＋ＰＬＵＳ−ＮＳである。
・新しい最大のデータレートは、ＭＴＲＵＳ＝ｍｉｎ（ＭＴＲｎｅｗ，ＭＴＲＵＳ−ＮＳ）である。
【００３５】
この場合においても、ステーションは、時間の比較及び置換が実行される前に、時間
【数３】
2004521561.tif 000005
をそれ自身の時間に変換しなければならない（以下の説明参照）。
【００３６】
図２は、第１の瞬間ｔ０における５つのサブネットワーク１０から１４を持つネットワークを示す。これらサブネットワーク１０から１４は、それぞれの中央制御器ＣＣ１からＣＣ５によって各々制御されている。個々のサブネットワーク１０から１４は、ブリッジノード又はフォワーダー（ｆｏｒｗａｒｄｅｒ）Ｆ１からＦ５を介して各々接続されている。ブリッジノードＦ１はサブネットワーク１０と１１とを接続し、ブリッジノードＦ２はサブネットワーク１１と１２とを接続し、ブリッジノードＦ３はサブネットワーク１１と１３とを接続し、ブリッジノードＦ４はサブネットワーク１２と１４とを接続し、ブリッジノードＦ５はサブネットワーク１３と１４とを接続する。例として、ステーションＳＴ１がサブネットワーク１１にある。サブネットワーク１０から１４は、どんな方法で他のステーション又はノード（図示せず）を含んでもよい。更に、図２は、個々のサブネットワーク間及びＣＣ２とステーションＳＴ１との間のリンクの送信レートを示す。フォワーダーＦ１を介するサブネットワーク１０とサブネットワーク１１との間の送信レートは１０Ｍｂｉｔ／ｓであり、フォワーダーＦ２を介するサブネットワーク１１とサブネットワーク１２との間の送信レートは５Ｍｂｉｔ／ｓであり、フォワーダーＦ３を介するサブネットワーク１１とサブネットワーク１３との間の送信レートは０．１Ｍｂｉｔ／ｓであり、フォワーダーＦ４を介するサブネットワーク１２とサブネットワーク１４との間の送信レートは１Ｍｂｉｔ／ｓであり、フォワーダーＦ５を介するサブネットワーク１３とサブネットワーク１４との間の送信レートは３Ｍｂｉｔ／ｓである。最後に、制御器ＣＣ２とステーションＳＴ１との間の送信レートは、５Ｍｂｉｔ／ｓである。図２において例として示されるネットワークにおけるリンクは、これによって中央制御器ＣＣ１からＣＣ５を常に通ることになる。
【００３７】
図３は、第２の瞬間ｔ１における図１の５つのサブネットワークを持つネットワークを示す。このネットワークのトポロジは、この第２の瞬間に変更する、すなわち、ステーションＳＴ１がサブネットワーク１１から隣接するサブネットワーク１０へ移動する。このサブネットワーク１０の制御器ＣＣ１とステーションＳＴ１との間の送信レートは、ここでは１０Ｍｂｉｔ／ｓである。
【００３８】
図４は、図２のサブネットワーク１１から図３に示されるサブネットワーク１０へステーションＳＴ１をシフトした結果として、制御器ＣＣ１からＣＣ５のルーティングテーブルにおける時間による変更を説明する。
【００３９】
図４のテーブルは、制御器ＣＣ１からＣＣ５の各々に対する列を含んでいる。ターゲットステーションＳＴに対する個々の制御器のルーティングテーブルの領域は、制御器ＣＣ１からＣＣ５に対し５つの異なる瞬間ｔ０からｔ４において前記列に示される。本実施例における領域は各々５つの副領域を持つ。それぞれのターゲットステーションの識別番号（ＩＤ）を含む図１に従って設けられる副領域は、図４がターゲットステーションＳＴ１に関するルーティング情報しか示さないので、図４には示されない。
【００４０】
図４における領域の上方の副領域は、ステーションＳＴ１用のデータが与えられるブリッジノード又はフォワーダーを示す。これは、このターゲットステーションＳＴ１への途中にいわゆる次のホップが単にターゲットステーションＳＴ１毎に記憶されることを意味する。上から２番目の副領域５は、ターゲットステーションまでの残りのパス長を含む。中央の副領域は、データがターゲットステーションＳＴ１に送信されることが可能な最大のデータレートを含む。このデータレートは、関連する制御器からターゲットステーションＳＴ１までの全ての構成パスの最大のデータレートに対応する。下から２番目の副領域は、トポロジ変更情報としてターゲットステーションＳＴ１に対する領域の発生時間ｔｇｅｎを供給する。この発生時間ｔｇｅｎは、ターゲットステーションＳＴ１に対するネットワークトポロジにおいて変更が起きたときを示す。ネットワークトポロジの変更を検出し、続いて局所ルーティングテーブルにおける領域のコンテンツの変更を実行するステーションにより登録される。本事例において、これはサブネットワーク１０の制御機ＣＣ１である。最も下の副領域は時間ｔｒｅｇを含む。これは、ネットワークトポロジの変更がそれぞれのステーション、すなわち本実施例ではそれぞれの制御器によってそれぞれのルーティングテーブルに含まれたとき、又は隣接するステーションによって送信される変更が採用されたときを示す。
【００４１】
本実施例において、列は、瞬間ｔ０における図２によるターゲットステーションＳＴ１及びネットワークに対する制御器ＣＣ１からＣＣ５の前記ルーティングテーブルの領域を含む。
【００４２】
瞬間ｔ１において、ターゲットステーションＳＴ１は、サブネットワーク１１からサブネットワーク１０へシフトされる。これは、図３のネットワークトポロジに対応する。これは、サブネットワーク１０の制御器ＣＣ１で識別され、それに従って、この制御器ＣＣ１は瞬間ｔ１においてそれのルーティングテーブルを変更させる。それに従って、瞬間ｔ１においてトポロジ変更情報が生じ、これはｔｇｅｎ＝１が設定されたことを意味する。ネットワークトポロジに起きた変更も瞬間ｔ１において制御器ＣＣ１によりルーティングテーブルに入力され、それに従って登録される。これはｔｒｅｇも１に設定されたことを意味する。
【００４３】
制御器ＣＣ２からＣＣ５は、瞬間ｔ１でのネットワークトポロジの変更をまだ知らない。この情報は初めにネットワーク中に配布されなければならない。これは、個々の制御器によって規則的な間隔で隣接する制御器に送られる要求を用いて、このようにして対処された制御器の関連する応答を用いて行われる。
【００４４】
制御器ＣＣ２は、瞬間ｔ２において制御器ＣＣ１からの要求に対する応答を受け取り、ネットワークトポロジの変更がＣＣ２のルーティングテーブルに入力される。瞬間ｔ１においてトポロジの変更が起こるので、ｔｇｅｎ＝１に設定される。ネットワークトポロジの変更は、瞬間ｔ２において制御器ＣＣ２によりそれのルーティングテーブルに入力され、それに従って登録される。これはｔｒｅｇが２に設定されることを意味する。
【００４５】
制御器ＣＣ３及びＣＣ４は、瞬間ｔ３において制御器ＣＣ２からの要求に対する応答を受け取り、ネットワークトポロジの変更がＣＣ３及びＣＣ４のルーティングテーブルに入力される。瞬間ｔ１においてトポロジの変更が起こるので、ｔｇｅｎ＝１に設定される。ネットワークの変更は、瞬間ｔ３において制御器ＣＣ３及びＣＣ４によりルーティングテーブルに入力され、それに従って登録される。これはｔｒｅｇが３に設定されることを意味する。
【００４６】
制御器ＣＣ５は、瞬間ｔ４において制御器ＣＣ３及び／又はＣＣ４からの要求に対する応答を受け取り、ネットワークトポロジの変更がＣＣ５のルーティングテーブルに入力される。瞬間ｔ１においてトポロジの変更が起こるので、ｔｇｅｎ＝１に設定される。ネットワークトポロジの変更は、瞬間ｔ４においてそれぞれの制御器ＣＣ５のルーティングテーブルに入力され、それに従って登録される。これはｔｒｅｇが４に設定されることを意味する。
【００４７】
他の副領域は、対応するやり方により、それぞれの瞬間ｔ１からｔ４において変更したネットワークトポロジにも適合される。
【００４８】
望むのであるなら、追加の機能が前記ルーティングを実施してもよい。ルーティングテーブルの一定期間のリフレッシュは、２つのＵＰＤＡＴＥ瞬間の間に起こるトポロジの変更がすぐに隣接するステーションに通信されるのではなく、次のＵＰＤＡＴＥ瞬間に通信されることを意味する。しかしながら、有利なことに、例えば接続パスの失敗のような特に重要な変更も、先行する要求を無しに、隣接するステーションと通信してもよい。これは、変更した領域に関する関連するエントリを含むＵＰＤＡＴＥ ＴＲＩＧＧＥＲメッセージを用いて行われる。
【００４９】
その上、トポロジの変更と次のＵＰＡＤＴＥ瞬間との間の時間を失われた現在のリンク上のデータを避けるために、このトポロジの変更を検出するノードが現在の接続を止めるために、関連するリンクのソース又は終端にＥＲＲＯＥメッセージを送ってもよい。
【００５０】
前記プロトコルで既定される時間ｔｕｐ、ｔｇｅｎ及びｔｒｅｇにおける瞬間は、様々なやり方で符号化される。明白な符号化は、多数の基本クロックモジュロ（ｂａｓｉｃ ｃｌｏｃｋ ｍｏｄｕｌｏ）として、ビットシーケンスの形式で最大値を符号化する全体のシステムクロックに関する。しかしながら、全体のシステムクロックを使用することは、ネットワークの全ステーションの同期を必要とする。（例えば規格１３９４．１のような）幾つかの通信規格は既にネットワークの全アプリケーションの同期を達成しているが、一般的に、全体のシステムクロックの利用は当然だとは思われていない。このために、全体のシステムクロックの使用が避けられる。アルゴリズムは実際、隣接するステーションがそれらの局所時間又は局所クロックの差について知らされる場合、既に十分機能的である。これに従って、隣接するステーションはお互いの一般的な局所システムクロックを知らせることを規定する。この情報交換の期間は通常、以下に更に説明されるように、極めて広くなるように選択されてもよい。これによって、クロック情報の交換は、送信リソースのごく僅かな占有を表す。各ステーションは、ステーションの局所時間と個々の隣接するステーション各々の局所時間との差を記憶する。ステーションがパラメタｔｕｐを持つＵＰＤＡＴＥ要求を受け取るとき、前記隣接するステーションのルーティングテーブルの最後の変更の瞬間をそれ自身の時間システムに変換するために、関連する隣接するステーションに関して記憶されるクロックの差をｔｕｐに加える。その後、変換されたｔｕｐは、通常のルーティング手順に従いそれ自身のルーティング入力の登録時間ｔｒｅｇと比較され、ＵＰＤＡＴＥ応答が生成される。ステーションが先行するＵＰＤＡＴＥ要求に対するＵＰＤＡＴＥ応答を受け取るとき、入力された各エントリの発生時間ｔｇｅｎは、関連する隣接するステーションとのクロック差が時間ｔｇｅｎに加えられる先行する場合のように、初めに局所時間システムに正確に変換される。その後、ルーティングアルゴリズムの通常の実施に従って、入力されたエントリがそれ自身のルーティングテーブルに含まれるかを決める。
【００５１】
２つの隣接するステーションにより記憶されるクロック差が反対の符号を持つ、すなわち、２つの隣接するステーション間のＵＰＤＡＴＥ要求及びＵＰＤＡＴＥ応答を交換する場合、あるステーションにおける正のクロック差の値を加えることが他のステーションにおける同じ正の値の減算（すなわち負の値の加算）に対応することに注意すべきである。
【００５２】
現在では普通であるクロック発生器は、マイクロ秒又はナノ秒の範囲の正確さを一般的に有する。このような時間の定義の高い正確さは、ここで論じているルーティング手順には必要ではない。送信すべきビット数を最小にするために、これによって、ステーションの初期クロックの一部しか、時間指示因子ｔｕｐ、ｔｇｅｎ及びｔｒｅｇに使用されない。
【００５３】
図５は、例として、完全な時間レジスタからの抜粋を示す。図５に示されるレジスタの間隔は１つのビットに対応する。時間値は二重に符号化され、ビットの重みは右から左へ増大するので、最上位ビット（ＭＳＢ）が一番左側に置かれる。図５においてハッチングされる、ルーティング手順のために選択されるレジスタの抜粋は２つの時間Ｔｍａｘ及びＴｍｉｎにより決められる。
【００５４】
選択されるレジスタ抜粋の上限は、その後にルーティングテーブルへのエントリが削除されなければならない最大の時間を決める。これは、ルーティング手順内の時間抜粋のモジュロ定義に基づいている。ステーションは、各時間ステップ（Ｔｐｒｅｃｉｓｉｏｎ）において、ルーティングテーブルに既に存在する各エントリを、該エントリの発生時間ｔｇｅｎが現在の局所時間（又は時間レジスタからの抜粋）に対応するかについてテストする。対応する場合、エントリは削除される。これは、そうしないと、モジュロ定義のために、１モジュロ期間後に古いエントリが再び高い確度で最新であるように見えるからである。
【００５５】
Ｔｍｉｎの大きさの次数が時間符号化の精度を決め、ＵＰＤＡＴＥ要求メッセージを送信する最小期間に基づいている。この理由は、要求する側のステーションの最新のＵＰＤＡＴＥがこの要求する側のステーションに送られるので、変更が最新のＵＰＤＡＴＥの後、短く又は長く行われたかに関係無く、全てのエントリが応答するステーションにおいて変更される。要求する側のステーションにおけるエントリの置き換えに対しても同じことが保たれている。更に正確な時間の符号化は、この点において何ら利点を与えず、単に送信容量を占めるだけである。
【００５６】
しかしながら、下位に数ビットだけ拡張された抜粋（図５において時間Ｔｐｒｅｃｉｓｉｏｎまで）は、図５において完全にハッチングされたビットだけルーティングアルゴリズムにおいて実際に処理されたとしても、前記時間ｔｕｐ、ｔｇｅｎ及びｔｒｅｇを送信及び記憶するのに選択される。あるタイミングシステムのクロックを他のタイミングシステムのクロックに変換するときの丸め誤差（ｒｏｕｎｄｉｎｇ ｅｒｒｏｒ）の伝搬効果がこの方法によって避けられる。
【００５７】
レジスタ抜粋が最終的に規定され、個々のステーションの動作中に変更することはできない。
【００５８】
しかしながら、ＵＰＤＡＴＥ要求メッセージを送信する期間に同じことは当てはまらない。ルーティング方法は、全てのステーションが同じ期間を使用する必要はない。これは、動作中に各ステーションがそれ自身のＵＰＤＡＴＥ期間を最適化する意味で用いられる。空のＵＰＤＡＴＥ応答メッセージは、例えば、ＵＰＤＡＴＥ期間が拡大される事実を示してもよい。高いトポロジ変更レート及び後続する接続中断並びにパケット損失は、ＵＰＤＡＴＥ期間の減少となるようにすべきである。これによって、ルーティング方法は、様々なシステムのシナリオ及び移動レートにそれ自身を自動的に適応させる。
【００５９】
示される符号化命令に従って、最初に作成されるステートメント、すなわち、隣接するステーション間のクロック差を決めるための情報交換が殆ど行われないステートメントがここで動機付けされてもよい。この情報交換の頻度は、いわゆる各ステーションの局所クロック発生器のクロックドリフトに従う。通常、このクロックドリフトは、クロックレジスタの最小符号化レベル（図５における最下位ビット又はＬＳＢ）よりも低い大きさの次数又は更に数個の次数からなる。しかしながら、考えられる抜粋の下限、すなわち時間Ｔｍｉｎは、図５に示されるような２つからなる少量の力によってより高くなるように選択される。クロック差に関する情報の交換は、Ｔｐｒｅｃｉｓｉｏｎの次数のシフトがクロックドリフトのせいで達成されるとき、少なくとも行われるべきである。
【００６０】
続いて、前記クロック差に関する情報の交換は、サブネットワーク又はクラスタの形式で組織される自己組織型ネットワークに関し表される。このようなネットワークの実施例は図６に示される。
【００６１】
図６のクラスタをベースとするネットワークにおいて、単一のステーション、中央制御器（ＣＣ）は、それ自身のクラスタの全ステーションに対しルーティングアルゴリズムを実行する。図６のネットワークは、５つのクラスタ２０から２４を有する。これらクラスタ２０から２４は、ＣＣ３０から３４を持つ。これは、ＣＣ３０から３４は上述されるルーティング方法において隣接していると意味する。しかしながら、ＣＣは、一般的に互いに直接通信することはできず、これらＣＣはクラスタの重複範囲にあるいわゆる転送端末（ＦＴ）を介して情報を交換しなければならない。クラスタ２０及び２２はＦＴ４０を用いて接続され、クラスタ２１及び２２はＦＴ４１を用いて接続され、クラスタ２２及び２３はＦＴ４２を用いて接続され、クラスタ２４及び２２はＦＴ４３を用いて接続される。クラスタ２０は例えば他のステーション５０を持ち、クラスタ２１は他のステーション５１及び５２を持ち、クラスタ２３は他のステーション５３及び５４を持ち、クラスタ２４は他のステーション５５から５７を持つ。
【００６２】
時間又はクロック情報は、以下のやり方でＣＣ２０と２４との間で交換される。各ＦＴ４０から４３及び各ＣＣ２０から２４は、各ＭＡＣフレームの最初に、それの完全なクロックレジスタのコピーを記憶する。その上、各ＣＣは定期的に（クロック情報の交換の期間に従って）現在のＭＡＣフレームの開始時のクロックレジスタのコピーがパラメタとして含まれるクラスタ内の放送メッセージを送信する。このメッセージを入力するＦＴは、それ自身のクロックレジスタのコピーとＣＣのクロックレジスタの入力されるコピーとの差を形成する。このようにして、これらは、ＣＣのクロックとそれ自身のクロックとの間をシフトすることを決め、この差を記憶する。同じ手順によってＦＴが一度他のＣＣとの差を決めると、２つのシフト値を減算することによって２つのＣＣのクロック差を決めることが可能である。このクロック差は続いて、特にこのために設計されたシグナリングメッセージにおける２つのＣＣに送信される。
【図面の簡単な説明】
【図１】ルーティング情報を持つルーティングテーブルを示す。
【図２】第１の瞬間に中央制御器により各々制御される５つのサブネットワークを持つ動的ネットワークを示す。
【図３】図２と比較して、隣接するサブネットワークにシフトされるネットワークのノードを持つ、第２の瞬間の図のネットワークを示す。
【図４】ネットワークノードのシフトの結果として、中央制御器のルーティングテーブルの変更の時間シーケンスを示すテーブル。
【図５】時間レジスタの一部を示す。
【図６】中央制御器により各々制御される５つのサブネットワークを持つネットワークを示す。
【国際公開パンフレット】
2004521561.tif 000006
2004521561.tif 000007
2004521561.tif 000008
2004521561.tif 000009
2004521561.tif 000010
2004521561.tif 000011
2004521561.tif 000012
2004521561.tif 000013
2004521561.tif 000014
2004521561.tif 000015
2004521561.tif 000016
2004521561.tif 000017
2004521561.tif 000018
2004521561.tif 000019
2004521561.tif 000020
2004521561.tif 000021
2004521561.tif 000022
2004521561.tif 000023
2004521561.tif 000024
2004521561.tif 000025
2004521561.tif 000026
2004521561.tif 000027
【国際公開パンフレット（コレクトバージョン）】
2004521561.tif 000028
【国際調査報告】
2004521561.tif 000029
2004521561.tif 000030
2004521561.tif 000031