(57)【特許請求の範囲】
【請求項１】
リンクを通して相互接続された多数のノードの１つ以上のドメインを含むメッシュネットワークにおいて、選択されたドメインに少なくとも１つのゲートウェイがあって、その選択されたドメインを別のネットワークに接続し、その１つ以上のドメイン及びそれら多数のノード及びそれらのリンクは、トポロジーの一部分であり、前記少なくとも１つのゲートウェイの選択されたゲートウェイに対する一次及びバックアップルーティング経路のセットにアクセスすることを含み、その選択されたゲートウェイに対する各一次及びバックアップルーティング経路は、その選択されたゲートウェイと、前記選択されたドメインのノードに対するその選択されたゲートウェイへのルートとを含むスパニングツリーを備えるものであり、更に、
１つ以上のスケジューリングサイクルにわたりメッシュネットワークの１つ以上のノードにより使用されるべき１つ以上のスケジュールにアクセスし、
ノード間の１つ以上のリンクの状態及び１つ以上のスケジュールに基づき、前記選択されたゲートウェイに対する一次又はバックアップルーティング経路の選択されたルーティング経路へ切り換え、及び
前記メッシュネットワークの少なくとも一部分におけるルートをその選択されたルーティング経路に基づいて変更させる、
ことを含む、トポロジー管理システムによって実行される方法。
【請求項２】
リンクを通して相互接続された多数のノードの１つ以上のドメインを含むメッシュネットワークにおいて、１つ以上のドメイン及びそれら多数のノード及びそれらのリンクは、トポロジーの一部分であり、選択されたドメインに対して少なくとも１つのゲートウェイがあってその選択されたドメインを別のネットワークに接続し、少なくとも１つのゲートウェイの選択されたゲートウェイに対する一次及びバックアップルーティング経路のセットを決定し、その選択されたゲートウェイに対する各一次及びバックアップルーティング経路は、その選択されたゲートウェイと、前記選択されたドメインのノードに対するその選択されたゲートウェイへのルートと、を含むスパニングツリーを備え、
前記選択されたドメインの他のゲートウェイに対する一次及びバックアップルーティング経路のセットの決定を遂行し、
１つ以上のスケジューリングサイクルにわたって前記メッシュネットワークのノードにより使用されるべき１つ以上のスケジュールを決定し、及び
前記メッシュネットワークのノードへ情報を送信し、ノードの情報は、少なくとも、ノードに対する一次及びバックアップルーティング経路、及び選択されたドメインのノードに対する１つ以上のスケジュールを記述するものである、トポロジー管理システムによって実行される方法。
【請求項３】
前記選択されたゲートウェイに対して一次及びバックアップルーティング経路のセットを決定することを更に含む請求項１に記載の方法、或いは前記選択されたゲートウェイに対して一次及びバックアップルーティング経路のセットを決定することが、少なくとも、次のこと：即ち、
前記選択されたゲートウェイに直接隣接するリンクを、ツリーの根に接続されるツリーのステムとして指定し、そして根は、前記選択されたゲートウェイであり；
各ステムを、全てのブランチの連合が前記選択されたドメインのノードを含むまで、ブランチへと成長させ；及び
各ブランチを、前記選択されたドメインをカバーする完全スパニングツリーが生じるまで、成長させる、
ことを遂行することによって遂行される、請求項２に記載の方法。
【請求項４】
親ノードへの直接的なホップリンクを経て他の親ノードへリーフノードを移動することでより小さなホップカウントが生じる場合には、少なくとも他の親ノードへリーフノードを移動することによってブランチのリーフノードを最適化することを更に含む、請求項３に記載の方法。
【請求項５】
前記スパニングツリーの数は、ステムの数に等しく、これは、前記選択されたゲートウェイへのノード当りのルートの数に等しい、請求項３又は４のいずれかに記載の方法。
【請求項６】
前記選択されたドメインの各ノードに対して、前記選択されたゲートウェイへのスパニングツリーの多数の経路のプライオリティを、少なくとも、次のこと：即ち、
前記選択されたゲートウェイへのホップカウントの数が最も少ない経路に最高のプライオリティをセットし；
等しいホップカウント状態のタイを切断してその状態の１つの経路を高いプライオリティの経路としてセットし；及び
最高のプライオリティの経路を一次経路と称する；
ことにより識別することを更に含む、請求項３から５のいずれか１項に記載の方法。
【請求項７】
前記タイの切断は、更に、次のもの：即ち、ノードの重み；予想トラフィック需要がスパニングツリー間でできるだけ等しく分担されること；及びランダムな指定；のうちの１つ以上を使用することによりタイを切断することを含む、請求項６に記載の方法。
【請求項８】
前記一次及びバックアップルーティング経路のリンクスケジュールを最適化することを更に含む、請求項１から７のいずれか１項に記載の方法。
【請求項９】
複数のゲートウェイを含む１つ以上のドメインの各々に対して、
前記一次及びバックアップルーティング経路のセットにアクセスし、１つ以上のスケジュールにアクセスし、ルートを切り換え及び生じさせることは、ドメイン内の複数のゲートの各々に対して遂行され；及び
複数のゲートウェイの各々に対するスパニングツリーは、対応するドメイン内のノードをスパンする；
請求項１から８のいずれか１項に記載の方法。
【請求項１０】
１つ以上のスケジュールは、繰り返しスケジュールへと順序付けされる構築送信セットを含む、請求項１から９のいずれか１項に記載の方法。
【請求項１１】
少なくとも送信セットを構築しそしてその構築された送信セットを繰り返しスケジュールへと順序付けすることにより１つ以上のスケジューリングサイクルにわたりメッシュネットワークの１つ以上のノードにより使用されるべき１つ以上のスケジュールを決定することを更に含む、請求項１から１０のいずれかに記載の方法。
【請求項１２】
前記送信セットの構築及び順序付けは、次のこと：即ち、
各スケジュールサイクルにおいて、各リンクには少なくとも１つの送信の機会が与えられねばならず；
あるリンクは、他のリンクより重要であると考えねばならず且つ各スケジュールサイクルにおいてより多くの機会が与えられねばならず；
スケジューリングサイクルの各スロットにおいて送信セットを識別し且つ構築し、その送信セットは、同じ瞬間にアクティブとなる最大数のバラバラのリンクで構築され；
メッシュネットワーク内の全てのリンクをカバーできるサイクル当りの最小スロット数を識別し；及び／又は
端−端遅延を保証するためにスケジュールサイクルにおける送信セットの順序を識別することによりスケジューリングサイクルの各スロットに送信セットを指定する；
ことの１つ以上を含む、請求項１０に記載の方法。
【請求項１３】
メッシュネットワーク内のあるノードにより遂行される方法であって、バーチャル接続及びトラフィックフローを使用して、受信したクライアントデータを、メッシュネットワークのリンクを経て転送することを更に含む、請求項１から１２のいずれか１項に記載の方法。
【請求項１４】
前記バーチャル接続を使用することは、クライアントデータに対する到来トラフィックを、バーチャル接続識別子により識別されるバーチャル接続へとマッピングすることを含む、請求項１３に記載の方法。
【請求項１５】
前記バーチャル接続及びトラフィックフローを使用することは、更に、ユーザデータをカプセル化することを含み、ユーザデータは、次のフィールドを含むヘッダを備えたフレームへとカプセル化され、
0006535387.tif 000003
ここで、ＩＤ＝識別である、請求項１３又は１４のいずれか１項に記載の方法。
【請求項１６】
あるノードによって遂行される方法であって、前記あるノードは、トラフィックをフローとして取り扱い、そのフローは、サービスクオリティプライオリティ識別及びバーチャル接続識別によって分離され、そして前記切り換えは、ローカル負荷及び混雑状態情報に基づいて、一次及びバックアップルーティング経路からの事前計算されたルート代替物を使用してトラフィックのローカル転送を生じさせる、請求項１から１５のいずれか１項に記載の方法。
【請求項１７】
前記ローカル転送は、更に、次のこと：即ち、
事前計算された経路優先度、及び各経路のボトルネックリンクの状態を使用することにより、一次及びバックアップルーティング経路からの経路を前記あるノードとしての入口ノードにより選択し；
各プライオリティクラスに基づいて異なる転送判断を実行し；
ルート計算により設定された優先度に基づき最良の利用可能な経路を含むローカル転送テーブルを使用して転送判断を実行し；
トポロジー構成情報及びネットワーク状態情報に基づいてローカル転送テーブルを形成し及び維持し、これは、新たなトポロジー構成が受け取られるたびに及び新たな状態情報がネットワークから受け取られて、１つ以上のリンク故障、リンク混雑、及び／又は他の異常を指示するたびに、テーブルを更新することを含み；
入口ノードを通るトラフィックフローごとに代替的ルーティング経路の利用性を前記あるノードとしての入口ノードにより推定し；
転送判断を実行するときにスパニングツリー識別子及びメッシュネットワーク識別子のみを前記あるノードとしての中間ノードにより検査し；
複数のフレームをプライオリティ情報に基づいて出力ポートにおいて正しいキューへ指定し；及び／又は
ボトルネックリンクの容量を分担するのではなく低プライオリティトラフィックを代替的経路へ強制するために厳密なプライオリティキューを目標として使用し、この使用は、前記分担が公平に遂行されるように行われる；
ことの１つ以上を含む、請求項１６に記載の方法。
【請求項１８】
前記切り換えは、次のこと：即ち、
経路再選択負荷バランシングを入口ノードだけに適用し、中間ノードは、最初に選択された経路変更せず；
経路状態情報に基づき代替的事前計算経路をプライオリティリストから選択し；
経路再選択負荷バランシングは、フローベースであり、完全なフローは、代替的経路に再指向され；
経路再選択負荷バランシングは、プライオリティベースであり、プライオリティの最も高いフローが最初に最も適したルーティング経路を取得し、プライオリティが２番目に高いフローが次に良好な利用可能なルートを取得し、そして残りのフローを通してこのプロセスを続け；
経路再選択負荷バランシングにおいて、プライオリティの高いトラフィックフローが、プライオリティの低いトラフィックフローを無効化するか、或いはプライオリティの高いトラフィックフローが、プライオリティの低いトラフィックフローを無効化し且つその先を越し；
逆マルチプレクシングに基づく負荷バランシングを適用して、低プライオリティのバルク及びベストエフォートトラフィックをパケットベース形態でバランスさせ；
逆マルチプレクシングに基づく負荷バランシングを低プライオリティトラフィックのみに適用し；
逆マルチプレクシングに基づく負荷バランシングにおいて、利用可能な全ての経路を使用し；
逆マルチプレクシングに基づく負荷バランシングは、パケットベースであり、到来する各パケットは、混雑の少ない経路に指向され；及び／又は
パケットにシーケンス番号を付し、ドメインの出口ノードで再順序付けを行う；
ことの１つ以上を含む１つ以上のオンデマンド動的負荷バランシング方法を遂行する、請求項１から１７のいずれか１項に記載の方法。
【請求項１９】
前記切り換え及びルーティングを行わせることは、更に、ハイアラーキー欠陥回復システムを実施することを含み、一次アクションは、１つ以上のスパニングツリーにおいて欠陥の場合に代替的事前計算ルーティング経路にトラフィックをリルートすることであり、そして二次アクションは、折れたスパニングツリーを回復することである、請求項１から１８のいずれか１項に記載の方法。
【請求項２０】
欠陥検出は、イベントベースであり、そして欠陥は、欠陥ポイントからメッシュネットワークの全てのノードへブロードキャストされるリンク状態更新メッセージをトリガーする、請求項１９に記載の方法。
【請求項２１】
前記ハイアラーキー欠陥回復システムの実施は、更に、高速ローカルリルートを遂行することを含み、切断リンク上を送信されるべきトラフィックは、代替的事前計算ルーティング経路に沿って再指向され、それにより、欠陥ポイントのノードは、パケットをアドホックバイパス経路セグメントに沿って望ましい行先に向かってリルートし始める、請求項１９又は２０のいずれか１項に記載の方法。
【請求項２２】
前記高速ローカルリルートの遂行は、更に、次のこと：即ち、
各ノードは、メッシュネットワークルートドメインの各行先ノードに対して経路優先度を維持し；
ゲートウェイとノードとの間の一次ルーティング経路の優先度は、集中型コントローラにより指定及び構成され；
ノード間の経路優先度は、スパニングツリーを経てのホップカウントに従ってノードそれ自体により計算され；
経路優先度は、ノードが新たなルーティング構成又はリンククオリティ変化レポートを受け取るたびに更新され；
パケットの現在経路が切断リンクによりブロックされた場合には、ノードの動作リンクを経てパケット行先へ至る代替的スパニングツリーに対して経路優先度をチェックし、そして代替的スパニングツリーが見つかった場合には、その代替的スパニングツリーを経てパケットをリルートする；
ことの１つ以上を含む再選択スパニングツリー方法を遂行することを含む、請求項２１に記載の方法。
【請求項２３】
パケット行先への代替的スパニングツリーがない場合、又は代替的スパニングツリーが、あまり適していない遅延、ホップカウント又は容量を伴う経路に通じる場合には、「隣接部へのトス」手順が使用され、パケットは、必ずしも事前計算経路のいずれにも属さない動作リンクを経て隣接部へ送信され、この隣接部は、次のものを使用してパケットの元々のスパニングツリーを経てパケットを行先へルーティングでき：即ち、
各切断リンクに対する適格な隣接部及び影響を受けるスパニングツリー・行先ノード対は、構成又はリンク状態変化に基づいて各ノードにより計算され、そして選択ルールは、次の通りであり：即ち、
「隣接部へのトス」ノードとこのノードとの間のリンクは、フェイルしたスパニングツリーに属さず；及び
「隣接部へのトス」ノードと行先ノードとの間の経路は、このノードを含まない；
請求項２２に記載の方法。
【請求項２４】
前記高速ローカルリルートを遂行することは、更に、プライオリティリストからの次に利用可能な経路によりローカル転送テーブルに基づいて修正ルートを選択する経路再選択を含む、請求項２１から２３のいずれか１項に記載の方法。
【請求項２５】
高速ローカルリルートを遂行することは、更に、経路欠陥が持続するか又はネットワークに現在多数の欠陥があることに応答してローカルスパニングツリーリペアを遂行することを含み、ルーティング経路に対するローカル修正は、次のこと：即ち、
スパニングツリーの切断リンクを、スパニングツリーに元々属さない動作リンクに置き換え；
当該ノード間のシグナリングがルーティング構造のローカル再アレンジを生じ；
ゲートウェイへの経路の上流リンクの１つが切断した場合には各ノードが潜在的な交換リンクに関する情報を維持し、そしてノードは、ルーティングトポロジー変化の際にこの情報を更新し；
各切断スパニングツリーに対して、適当な交換候補は、切断ポイントからスパニングツリーに沿って上流へのノード及び下流へのノードを直接接続するリンクであり；
ローカルスパニングツリーリペア手順は、ゲートウェイに向いた切断リンクを伴う開始ノードにより開始され、そしてその開始ノードは、リンクの下流エンドポイントリペアノードへのリペアリンクをアクチベートする信号を送信し；及び／又は
リペアノードは、それの転送優先度を更新し、新たなリンクを使用するようにルーティングし、そしてリペアしたスパニングツリーについて他のノードに通知する；
ことの１つ以上を含むものが実行される、請求項２４に記載の方法。
【請求項２６】
前記高速ローカルリルートを遂行することは、更に、欠陥状態が永久的と思われるほど長時間続くのに応答して、全てのルーティング経路を再計算し、１つ以上の新たなスケジュールを計算し、そして全ネットワークを、その再計算されたルーティング経路及び計算された１つ以上の新たなスケジュールに基づいて再構成することを含む、請求項２５に記載の方法。
【請求項２７】
ネットワーク内にローカル欠陥識別及びリンク状態情報を配布することを更に含む、請求項１から２６のいずれか１項に記載の方法。
【請求項２８】
前記ネットワーク内にローカル欠陥識別及びリンク状態情報を配布することは、更に、次のこと：即ち、
リンク及び経路の両状態を監視し；
リンクの動作状態は、ワイヤレス物理的レイヤから受け取った状態指示に基づき；
周期的なハローメッセージを使用して全ての隣接ノードへの全てのリンクを経ての隣接ノードへの到達性を検証し；
主として、プライオリティ特有の出力キュー長さにより混雑を推定し；
リンク状態更新メッセージを使用して全メッシュネットワーク内にリンク状態情報を配布し、ノードが著しいリンク状態変化又はリンクのトラフィック負荷の変化を検出したときにノードがリンク状態更新メッセージを送信し；
リンク状態更新メッセージは、制御平面において、リンク状態更新メッセージで特定されるスパニングツリーに沿って伝播され、そして各ノードは、受け取ったリンク状態更新メッセージを、そのリンク状態更新メッセージが受け取られたところの隣接部を除いて、それ自身の隣接部へ転送し；及び／又は
各リンク状態イベントに対して、ノードは、当該リンクを横断する全てのスパニングツリーに沿ってリンク状態更新メッセージを送信する；
ことの１つ以上を含む、請求項２７に記載の方法。
【請求項２９】
前記方法は、一方向性及び両方向性の両クライアントトラフィックをサポートする、請求項１から２８のいずれか１項に記載の方法。
【請求項３０】
前記方法は、同じルーティング経路又は異なるルーティング経路のいずれかを通して両方向性トラフィックの上流及び下流方向のルーティングをサポートする、請求項１から２９項のいずれか１項に記載の方法。
【請求項３１】
前記方法は、更に、少なくとも前記切り換えを遂行し且つエネルギー最適化に一部分基づいてルーティングを遂行させることを含む、請求項１から３０項のいずれか１項に記載の方法。
【請求項３２】
前記エネルギー最適化は、次のこと：即ち、
ノード及びリンクレベルでエネルギー節約を行うエネルギー節約制御モジュールを実行し；
前記エネルギー節約制御モジュールの動作をクライアントレイヤと整合し、どのクライアントノードが潜在的なスリーパーであるか指示することを含み；
前記エネルギー節約制御モジュールは、どのクライアントノードが潜在的なスリーパーであるかそれ自身で学習し；
前記エネルギー節約制御モジュールは、クライアントレイヤに潜在的なスリーパーを提案し；
ノードは、その内部自己診断に基づいて遮断を要求でき；
潜在的なスリープノードが指示されると、そのノードは、進行中のトラフィックに影響することなくノードをスリープさせることを許すように全スパニングツリーにおけるリーフノードとなるよう強制され；
新たなトポロジー構成情報を配布し、そしてアクチベーションの後に、ノードをスリープさせ；
ある基準に基づいてウェイクアップ手順を遂行し；
リンクレベルエネルギー節約をトポロジー最適化において考慮し；及び／又は
エネルギー節約制御モジュールプロセスは、保守の目的でも行われ、そして保護スキームをアクチベートする必要なくノードの率直な遮断を与える；
ことの１つ以上を含む、請求項３１に記載の方法。
【請求項３３】
前記トポロジーは、第１トポロジーであり、メッシュネットワークに１つ以上の変化が生じて、第２トポロジーを生成し；
前記方法は、更に、選択されたドメインの全てのゲートウェイに対する一次及びバックアップルーティング経路のセットの決定を再遂行し、且つ１つ以上のスケジュールの決定を再遂行することを含み；及び
前記情報の送信は、第１トポロジー構成から第２トポロジー構成への移行を同期させるように遂行される；請求項２に記載の方法。
【請求項３４】
前記メッシュネットワークは、ワイヤレスメッシュネットワークである、請求項１から３３のいずれか１項に記載の方法。
【請求項３５】
前記メッシュネットワークは、ワイヤレスメッシュネットワークであり、そして多数のノードは、ミリメータ波リンクを使用して互いに通信する、請求項１から３４のいずれか１項に記載の方法。
【請求項３６】
光学的メッシュネットワークにおいて遂行される、請求項１から３３のいずれか１項に記載の方法。
【請求項３７】
リンクを通して相互接続された多数のノードの１つ以上のドメインを含むメッシュネットワークにおいて、選択されたドメインに少なくとも１つのゲートウェイがあって、その選択されたドメインを別のネットワークに接続し、１つ以上のドメイン及びそれら多数のノード及びそれらのリンクは、トポロジーの一部分であり、少なくとも１つのゲートウェイの選択されたゲートウェイに対する一次及びバックアップルーティング経路のセットにアクセスするための手段を備え、その選択されたゲートウェイに対する各一次及びバックアップルーティング経路は、その選択されたゲートウェイと、前記選択されたドメインのノードに対するその選択されたゲートウェイへのルートとを含むスパニングツリーを備えるものであり；更に、
１つ以上のスケジューリングサイクルにわたりメッシュネットワークの１つ以上のノードにより使用されるべき１つ以上のスケジュールにアクセスする手段；
ノード間の１つ以上のリンクの状態及び１つ以上のスケジュールに基づき、前記選択されたゲートウェイに対する一次又はバックアップルーティング経路の選択されたルーティング経路へ切り換える手段；及び
前記メッシュネットワークの少なくとも一部分におけるルートをその選択されたルーティング経路に基づいて変更させる手段；
を備えた装置。
【請求項３８】
リンクを通して相互接続された多数のノードの１つ以上のドメインを含むメッシュネットワークにおいて、１つ以上のドメイン及びそれら多数のノード及びそれらのリンクは、トポロジーの一部分であり、選択されたドメインに対して少なくとも１つのゲートウェイがあってその選択されたドメインを別のネットワークに接続し、少なくとも１つのゲートウェイの選択されたゲートウェイに対する一次及びバックアップルーティング経路のセットを決定するための手段を備え、その選択されたゲートウェイに対する各一次及びバックアップルーティング経路は、その選択されたゲートウェイと、前記選択されたドメインのノードに対するその選択されたゲートウェイへのルートとを含むスパニングツリーを備え；更に、
前記選択されたドメインの他のゲートウェイに対する一次及びバックアップルーティング経路のセットの決定を遂行するための手段；
１つ以上のスケジューリングサイクルにわたってメッシュネットワークのノードにより使用されるべき１つ以上のスケジュールを決定するための手段；及び
メッシュネットワークのノードへ情報を送信するための手段；
を備え、ノードの情報は、少なくとも、ノードに対する一次及びバックアップルーティング経路、及び選択されたドメインのノードに対する１つ以上のスケジュールを記述するものである、装置。
【請求項３９】
請求項３から３６のいずれかに記載の方法を遂行するための手段を更に備えた、請求項３７又は３８のいずれか１項に記載の装置。
【請求項４０】
請求項３７から３９のいずれかに記載の装置を備えたベースステーション。
【請求項４１】
請求項３７から３９のいずれかに記載の装置を備えたメッシュネットワーク集中型コントローラ。
【請求項４２】
請求項３７から３９のいずれかに記載の装置を１つ以上備えた通信ネットワーク。
【請求項４３】
請求項１から３６のいずれかに記載の方法を実行するためのプログラムコードを含むコンピュータプログラム。
【請求項４４】
前記コンピュータプログラムは、コンピュータに使用するために実施されるコンピュータプログラムコードを保持するコンピュータ読み取り可能な媒体を備えたコンピュータプログラム製品である、請求項４３に記載のコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般的に、ワイヤレス通信に関するもので、より詳細には、ワイヤレス通信における自己編成ネットワークに関する。
【背景技術】
【０００２】
本章は、以下に開示する発明に対する背景又は状況を与えることを意図している。ここでの説明は、追求できるが必ずしもこれまでに想像、具現化又は説明されたものではない概念を含むかもしれない。それ故、特に指示のない限り、本章での説明は、本出願の説明に対する従来技術でもないし、又、本章に含ませることで従来技術として認められるものでもない。本明細書及び添付図面に見られる略語は、以下、詳細な説明章の主部分に続いて定義される。
【０００３】
モバイルブロードバンドトラフィックは、２０２０年までに１０００倍も成長することが予想される。５Ｇとしても知られている次世代の偏在する超広帯域巾通信システムは、２０２０年以降生じるであろうスループット及びレイテンシー需要を満足するネットワーク緻密化を伴うことになる。２０２０年までに、小型のセルは、（２０１０年に比して）１０００倍まで成長すると予想され且つ２０３０年までに１０，０００倍になるであろう全データボリュームのトラフィックの大半を搬送することが予想される。
【０００４】
従って、小型セルの配備は、慣習的なマクロセルの配備より桁数の多いサイトとなるためにモバイル運営者にとって最大の課題の１つとなる。これは、屋外の配備について特に言えることである。５Ｇ小型セルの最終ホップバックホール（last hop backhaul）は、必要に応じて追加容量を注入できる融通性のある有機的な仕方で、費用効果の高い配備を行うことができねばならない。バックホールは、数ギガビットのスループットを与え、ミリ秒レベルの最大レイテンシーを有し、高い入手性及び信頼性を有す、費用効果の高い拡張性を有し、配備が容易であり、管理が容易であり、トラフィックに基づく動的な拡張性及び最適化を有し、フォームファクタが小さく、そしてＴＣＯ（総所有コスト）が低い、といった重要な５Ｇバックホール要件を全て満足しなければならない。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
この種の要件は、５Ｇラストマイルバックホールのための特殊な解決策を必要とする。更に、セル数の増加は、ネットワークの複雑さを生じる。これは、ひいては、費用効果の高い仕方で運営者にとってネットワークの運営を計画し、管理し及び最適化する困難さを増大する。実際に、将来の５Ｇ小型セルネットワークは、詳細なネットワーク計画なしに増殖的に配備されることが予想される。自己編成ネットワーク（ＳＯＮ）の概念は、ネットワーク設計、配備及び運営段階を自動化することにより運営コスト及び努力を最小化するために運営者により実現可能な技術と考えられる。
【０００６】
他方、５Ｇ小型セル間を接続するためのメッシュネットワークの使用は、元来、メッシュトポロジーにおける別のルートを経て信頼性及び融通性の増加を与える。しかしながら、５Ｇ小型セルのためのメッシュネットワーク及び他の技術をどのように使用すれば、５Ｇ運営者の高い期待を満足できるかは、現在、明確でない。
【課題を解決するための手段】
【０００７】
本章は、例示を含むもので、限定を意図していない。
【０００８】
規範的実施形態において、方法は、リンクを通して相互接続された多数のノードの１つ以上のドメインを含むメッシュネットワークにおいて、選択されたドメインに少なくとも１つのゲートウェイがあってその選択されたドメインを別のネットワークに接続し、その１つ以上のドメイン及びそれら多数のノード及びそれらのリンクは、トポロジーの一部分であり、少なくとも１つのゲートウェイの選択されたゲートウェイに対する一次及びバックアップルーティング経路のセットにアクセスすることを含む。その選択されたゲートウェイに対する各一次及びバックアップルーティング経路は、その選択されたゲートウェイと、前記選択されたドメインのノードに対するその選択されたゲートウェイへのルートとを含むスパニングツリーを備えるものである。又、この方法は、１つ以上のスケジューリングサイクルにわたってメッシュネットワークの１つ以上のノードにより使用されるべき１つ以上のスケジュールにアクセスすることを含む。又、この方法は、ノード間の１つ以上のリンクの状態及び１つ以上のスケジュールに基づき、前記選択されたゲートウェイに対する一次又はバックアップルーティング経路の選択されたルーティング経路へ切り換えることを含む。この方法は、メッシュネットワークの少なくとも一部分におけるルートをその選択されたルーティング経路に基づいて変更させることも含む。
【０００９】
実施形態の付加的な例は、プロセッサにおいて実行されたときに前記方法を遂行するためのコードを含むコンピュータプログラムを包含する。このコンピュータプログラムは、コンピュータに使用するために実施されるコンピュータプログラムコードを保持するコンピュータ読み取り可能な媒体を含むコンピュータプログラム製品である。
【００１０】
実施形態の更に別の例は、リンクを通して相互接続された多数のノードの１つ以上のドメインを含むメッシュネットワークにおいて、選択されたドメインに少なくとも１つのゲートウェイがあってその選択されたドメインを別のネットワークに接続し、１つ以上のドメイン及びそれら多数のノード及びそれらのリンクは、トポロジーの一部分であり、少なくとも１つのゲートウェイの選択されたゲートウェイに対する一次及びバックアップルーティング経路のセットにアクセスするための手段を備え、その選択されたゲートウェイに対する各一次及びバックアップルーティング経路は、その選択されたゲートウェイと、前記選択されたドメインのノードに対するその選択されたゲートウェイへのルートとを含むスパニングツリーを備えるものであり；更に、１つ以上のスケジューリングサイクルにわたりメッシュネットワークの１つ以上のノードにより使用されるべき１つ以上のスケジュールにアクセスする手段；ノード間の１つ以上のリンクの状態及び１つ以上のスケジュールに基づき、前記選択されたゲートウェイに対する一次又はバックアップルーティング経路の選択されたルーティング経路へ切り換える手段；及びメッシュネットワークの少なくとも一部分におけるルートをその選択されたルーティング経路に基づいて変更させる手段；を備えた装置である。
【００１１】
装置の一例は、１つ以上のプロセッサ、及びコンピュータプログラムコードを含む１つ以上のメモリを備えている。１つ以上のメモリ及びコンピュータプログラムコードは、１つ以上のプロセッサとで、装置が、少なくとも、次のこと、即ち、リンクを通して相互接続された多数のノードの１つ以上のドメインを含むメッシュネットワークにおいて、選択されたドメインに少なくとも１つのゲートウェイがあってその選択されたドメインを別のネットワークに接続し、その１つ以上のドメイン及びそれら多数のノード及びそれらのリンクは、トポロジーの一部分であり、前記少なくとも１つのゲートウェイの選択されたゲートウェイに対する一次及びバックアップルーティング経路のセットにアクセスし、その選択されたゲートウェイに対する各一次及びバックアップルーティング経路は、その選択されたゲートウェイと、前記選択されたドメインのノードに対するその選択されたゲートウェイへのルートとを含むスパニングツリーを備えるものであり；更に、１つ以上のスケジューリングサイクルにわたりメッシュネットワークの１つ以上のノードにより使用されるべき１つ以上のスケジュールにアクセスし；ノード間の１つ以上のリンクの状態及び１つ以上のスケジュールに基づき、前記選択されたゲートウェイに対する一次又はバックアップルーティング経路の選択されたルーティング経路へ切り換え；及び前記メッシュネットワークの少なくとも一部分におけるルートをその選択されたルーティング経路に基づいて変更させ；ことを遂行させるように構成される。
【００１２】
コンピュータプログラム製品の一例は、コンピュータに使用するために実施されるコンピュータプログラムコードを保持するコンピュータ読み取り可能な媒体を含む。コンピュータプログラムコードは、リンクを通して相互接続された多数のノードの１つ以上のドメインを含むメッシュネットワークにおいて、選択されたドメインに少なくとも１つのゲートウェイがあってその選択されたドメインを別のネットワークに接続し、１つ以上のドメイン及びそれら多数のノード及びそれらのリンクは、トポロジーの一部分であり、少なくとも１つのゲートウェイの選択されたゲートウェイに対する一次及びバックアップルーティング経路のセットにアクセスするためのコードを備え、その選択されたゲートウェイに対する各一次及びバックアップルーティング経路は、その選択されたゲートウェイと、前記選択されたドメインのノードに対するその選択されたゲートウェイへのルートとを含むスパニングツリーを備えるものであり；更に、１つ以上のスケジューリングサイクルにわたりメッシュネットワークの１つ以上のノードにより使用されるべき１つ以上のスケジュールにアクセスするためのコード；ノード間の１つ以上のリンクの状態及び１つ以上のスケジュールに基づき、前記選択されたゲートウェイに対する一次又はバックアップルーティング経路の選択されたルーティング経路へ切り換えるためのコード；及びメッシュネットワークの少なくとも一部分におけるルートをその選択されたルーティング経路に基づいて変更させるためのコード；を備えている。
【００１３】
方法の別の例は、リンクを通して相互接続された多数のノードの１つ以上のドメインを含むメッシュネットワークにおいて、１つ以上のドメイン及びそれら多数のノード及びそれらのリンクは、トポロジーの一部分であり、選択されたドメインに対して少なくとも１つのゲートウェイがあってその選択されたドメインを別のネットワークに接続し、少なくとも１つのゲートウェイの選択されたゲートウェイに対する一次及びバックアップルーティング経路のセットを決定し、その選択されたゲートウェイに対する各一次及びバックアップルーティング経路は、その選択されたゲートウェイと、前記選択されたドメインのノードに対するその選択されたゲートウェイへのルートとを含むスパニングツリーを備え、前記選択されたドメインの他のゲートウェイに対する一次及びバックアップルーティング経路のセットの決定を遂行し、１つ以上のスケジューリングサイクルにわたりメッシュネットワークのノードにより使用されるべき１つ以上のスケジュールを決定し、及びメッシュネットワークのノードへ情報を送信し、ノードの情報は、少なくとも、ノードに対する一次及びバックアップルーティング経路、及び選択されたドメインのノードに対する１つ以上のスケジュールを記述するものである。
【００１４】
付加的な実施形態は、プロセッサで実行されるときに前記方法を遂行するためのコードを含むコンピュータプログラムを包含する。このコンピュータプログラムは、コンピュータに使用するために実施されるコンピュータプログラムコードを保持するコンピュータ読み取り可能な媒体を含むコンピュータプログラム製品である。
【００１５】
装置の更に別の例は、リンクを通して相互接続された多数のノードの１つ以上のドメインを含むメッシュネットワークにおいて、１つ以上のドメイン及びそれら多数のノード及びそれらのリンクは、トポロジーの一部分であり、選択されたドメインに対して少なくとも１つのゲートウェイがあってその選択されたドメインを別のネットワークに接続し、少なくとも１つのゲートウェイの選択されたゲートウェイに対する一次及びバックアップルーティング経路のセットを決定するための手段を備え、その選択されたゲートウェイに対する各一次及びバックアップルーティング経路は、その選択されたゲートウェイと、前記選択されたドメインのノードに対するその選択されたゲートウェイへのルートとを含むスパニングツリーを備え；更に、前記選択されたドメインの他のゲートウェイに対する一次及びバックアップルーティング経路のセットの決定を遂行するための手段；１つ以上のスケジューリングサイクルにわたりメッシュネットワークのノードにより使用されるべき１つ以上のスケジュールを決定するための手段；及びメッシュネットワークのノードへ情報を送信するための手段；を備え、ノードの情報は、少なくとも、ノードに対する一次及びバックアップルーティング経路、及び選択されたドメインのノードに対する１つ以上のスケジュールを記述するものである。
【００１６】
装置の一例は、１つ以上のプロセッサ、及びコンピュータプログラムコードを含む１つ以上のメモリを備えている。１つ以上のメモリ及びコンピュータプログラムコードは、１つ以上のプロセッサとで、装置が、少なくとも、次のこと、即ち、リンクを通して相互接続された多数のノードの１つ以上のドメインを含むメッシュネットワークにおいて、１つ以上のドメイン及びそれら多数のノード及びそれらのリンクは、トポロジーの一部分であり、選択されたドメインに対して少なくとも１つのゲートウェイがあってその選択されたドメインを別のネットワークに接続し、少なくとも１つのゲートウェイの選択されたゲートウェイに対する一次及びバックアップルーティング経路のセットを決定し、その選択されたゲートウェイに対する各一次及びバックアップルーティング経路は、その選択されたゲートウェイと、前記選択されたドメインのノードに対するその選択されたゲートウェイへのルートとを含むスパニングツリーを備え、前記選択されたドメインの他のゲートウェイに対する一次及びバックアップルーティング経路のセットの決定を遂行し、１つ以上のスケジューリングサイクルにわたりメッシュネットワークのノードにより使用されるべき１つ以上のスケジュールを決定し、及びメッシュネットワークのノードへ情報を送信し、ノードの情報は、少なくとも、ノードに対する一次及びバックアップルーティング経路、及び選択されたドメインのノードに対する１つ以上のスケジュールを記述するものである、ことを遂行するようにさせるよう構成される。
【００１７】
コンピュータプログラム製品の一例は、コンピュータに使用するために実施されるコンピュータプログラムコードを保持するコンピュータ読み取り可能な媒体を含む。コンピュータプログラムコードは、リンクを通して相互接続された多数のノードの１つ以上のドメインを含むメッシュネットワークにおいて、１つ以上のドメイン及びそれら多数のノード及びそれらのリンクは、トポロジーの一部分であり、選択されたドメインに対して少なくとも１つのゲートウェイがあってその選択されたドメインを別のネットワークに接続し、少なくとも１つのゲートウェイの選択されたゲートウェイに対する一次及びバックアップルーティング経路のセットを決定するためのコードを含み、その選択されたゲートウェイに対する各一次及びバックアップルーティング経路は、その選択されたゲートウェイと、前記選択されたドメインのノードに対するその選択されたゲートウェイへのルートとを含むスパニングツリーを備え；更に、前記選択されたドメインの他のゲートウェイに対する一次及びバックアップルーティング経路のセットの決定を遂行するためのコード；１つ以上のスケジューリングサイクルにわたりメッシュネットワークのノードにより使用されるべき１つ以上のスケジュールを決定するためのコード；及びメッシュネットワークのノードへ情報を送信するためのコード；を含み、ノードの情報は、少なくとも、ノードに対する一次及びバックアップルーティング経路、及び選択されたドメインのノードに対する１つ以上のスケジュールを記述するものである。
【図面の簡単な説明】
【００１８】
【図１】幾つかの実施形態が具現化されるシステムの１つの考えられる非限定例のブロック図である。
【図２】ＷＭＮ送信セットを例示するもので、８つの送信セットＴ１ないしＴ８の各々に対しＴＤＤ形態においてアクティブである同時にバラバラ(disjoint)のリンクのグループを示す。
【図３】ある実施形態におけるトポロジー管理機能アーキテクチャーの一例を示す。
【図４】トポロジー管理プロセスフローの一例を示すもので、規範的方法の動作、コンピュータ読み取り可能なメモリで実施されるコンピュータプログラムインストラクションの実行結果、ハードウェアで実施されるロジックにより遂行される機能、及び／又は幾つかの規範的な実施形態により機能を遂行するための相互接続された手段を例示する。
【図５Ａ】５Ｇ小型セルネットワーク２０ノードトポロジーに対するルーティングスキームの一例としてステム、ブランチ及びスパニングツリーを例示する。
【図５Ｂ】図５Ａのステム、ブランチ及びスパニングツリーのツリー構造図である。
【図５Ｃ】図５Ａのステム、ブランチ及びスパニングツリーのテーブル表示である。
【図６】ＷＭＮフレームヘッダフィールドのテーブルである。
【図７】多段欠陥管理スキームを例示する。
【図８】動的ルート最適化使用ケースの一例を示す。
【図９】８×８グリッドＳＷＭＮの一例を示す。
【図１０】図９からの８×８グリッドＳＷＭＮにおけるＧＷ１８の一次経路を示す。
【図１１】一次経路の経路長さを示すチャートである。
【図１２】リンク重み分布を示すチャートである。
【図１３】調整された送信セットを可視化したものである。
【図１４】送信セットリンクオーバーラップカウントのマトリクスである。
【図１５】ゲートウェイノード（ＧＷ）を経て固定ネットワークに接続されたＷＭＮルートドメインを含むＷＭＮシステムアーキテクチャーの一例を示すもので、小型セルは、通常、マクロセルサイトでＷＭＮノード（ＷＮ）及びＧＷと共同配置される。
【図１６】ＭＤＳＴ計算手順の一例を示すもので、規範的方法の動作、コンピュータ読み取り可能なメモリで実施されるコンピュータプログラムインストラクションの実行結果、ハードウェアで実施されるロジックにより遂行される機能、及び／又は幾つかの規範的な実施形態により機能を遂行するための相互接続された手段を例示する。
【図１７】ヒープを初期化するＧＥＮＳＴＥＭＳ初期化アルゴリズムの一例を示す。
【図１８】ＧＲＯＷ手順の一例を示す。
【図１９】図１８のＧＲＯＷ手順を使用して、１つのＧＷを伴うノードの５×４規則的グリッドネットワークに対して生成されるステムの一例を示す。
【図２０】ステムを全スパニングツリーへと成長させるＧＥＮＴＲＥＥ手順の一例を示す。
【図２１】図２０のＧＥＮＴＲＥＥ手順を使用して全スパニングツリーへと成長した図１９のステムの一例を示す。
【図２２】リーフノードを、より良い親ノード（それが利用できる場合は）へ移動するＴＡＩＬＯＰＴ手順を示す。
【図２３】ローカルＳＴリペアのアクションを例示するもので、左側では、ＩＮがＲＮでもあり、そして右側では、ＩＮがＳＴのリペアを別のノードに求めねばならない。
【図２４】小型セルバックホールのための自己編成ネットワーク概念を遂行する論理フロー図であって、規範的方法の動作、コンピュータ読み取り可能なメモリで実施されるコンピュータプログラムインストラクションの実行結果、ハードウェアで実施されるロジックにより遂行される機能、及び／又は規範的な実施形態により機能を遂行するための相互接続された手段を例示する。
【図２５】小型セルバックホールのための自己編成ネットワーク概念を遂行する論理フロー図であって、規範的方法の動作、コンピュータ読み取り可能なメモリで実施されるコンピュータプログラムインストラクションの実行結果、ハードウェアで実施されるロジックにより遂行される機能、及び／又は規範的な実施形態により機能を遂行するための相互接続された手段を例示する。
【発明を実施するための形態】
【００１９】
「規範的」という語は、ここでは、「例、事例又は例示として働く」ことを意味する。「規範的」としてここに述べる実施形態は、必ずしも、他の実施形態よりも好ましい又は好都合であると解釈されるべきではない。この詳細な説明で述べる全ての実施形態は、当業者が発明を利用できるようにするために設けられたもので、請求の範囲に規定される本発明の範囲を限定するものではない。
【００２０】
上述したように、５Ｇ小型セル間を接続するためのメッシュネットワークの使用は、元来、メッシュトポロジーにおける別のルートを経て信頼性及び融通性の増加を与えるが、５Ｇ運営者の基準を満足するためにそのような実施をどのように行うかが明確でない。ここでは、例えば、５Ｇ運営者の高い期待を満足できる５Ｇ小型セルのための革新的なワイヤレスバックホール解決策を開示する。自己最適化ワイヤレスメッシュネットワークと称される自己編成及び自己最適化小型セルワイヤレスメッシュバックホール解決策の概念が、例えば、その革新的性質を特徴付ける特殊な内蔵特徴と共に、ここに開示される。幾つかの規範的な実施形態がおそらく使用されるシステムが説明された後に、これら技術の付加的な説明が提示される。
【００２１】
図１は、本発明の幾つかの規範的実施形態が具現化される規範的システムを示す。図１において、ユーザ装置（ＵＥ）１１０は、無線ネットワーク１００とワイヤレス通信する。ユーザ装置１１０は、１つ以上のプロセッサ１２０、１つ以上のメモリ１２５、及び１つ以上のトランシーバ１３０を備え、それらは、１つ以上のバス１２７を通して相互接続される。１つ以上のトランシーバ１３０は、１つ以上のアンテナ１２８に接続される。１つ以上のメモリ１２５は、コンピュータプログラムコード１２３を含む。１つ以上のメモリ１２５及びコンピュータプログラムコード１２３は、１つ以上のプロセッサ１２０とで、ユーザ装置１１０がここに述べる１つ以上の動作を遂行するようにさせるよう構成される。
【００２２】
無線ネットワーク１００は、ｎ個のｅＮｏｄｅＢ（ｅＮＢ）２２０−１、２２０−２、及び２２０−ｎを備え、そしてＳＯＮ（自己編成ネットワーク）ノード２１０を備えている。ｅＮｏｄｅＢ２２０−１の内部要素についてここで説明し、ｅＮｏｄｅＢ２２０−２及び２２０−ｎは同様であると仮定する。ｅＮｏｄｅＢ２２０−１は、１つ以上のプロセッサ１５０−１、１つ以上のメモリ１５５−１、１つ以上のネットワークインターフェイス（Ｎ／Ｗ  Ｉ／Ｆ(ｓ)）１６１−１、及び１つ以上のトランシーバ１６０−１を備え、これらは、１つ以上のバス１５７−１を通して相互接続される。１つ以上のトランシーバ１６０−１は、１つ以上のアンテナ１５８−１に接続される。１つ以上のメモリ１５５−１は、コンピュータプログラムコード１５３−１を含む。規範的実施形態において、１つ以上のメモリ１５５−１及びコンピュータプログラムコード１５３−１は、１つ以上のプロセッサ１５０−１とで、ｅＮｏｄｅＢ２２０−１がここに述べる１つ以上の動作を遂行するようにさせるよう構成される。一例において、例えば、ＳＯＮモジュール２３０−１は、ここに述べる機能の幾つか、多数又は全部を遂行するように実施され（例えば、機能を遂行するための手段として）、そしてハードウェアで（例えば、ゲートアレイ又は半導体回路においてプロセッサ１５０−１の一部分として）実施されるか、コンピュータプログラムコード１５３−１の一部分として実施されるか、或いはハードウェア又はコンピュータプログラムコード１５３−１のある組み合せとして実施される。１つ以上のネットワークインターフェイス１６１−１は、ネットワーク１７３、１７５のようなネットワークを経て通信する。一例において、ネットワーク１７３、１７５の一方又は両方がバックホールリンク１８２であると考えられる。
【００２３】
ＳＯＮノード２１０は、１つ以上のプロセッサ１８０、１つ以上のメモリ１９５、及び１つ以上のネットワークインターフェイス（Ｎ／Ｗ  Ｉ／Ｆ(ｓ)）１９０を備え、これらは、１つ以上のバス１８７を通して相互接続される。１つ以上のメモリ１９５は、コンピュータプログラムコード１９７を含む。一例において、１つ以上のメモリ１９５及びコンピュータプログラムコード１９７は、１つ以上のプロセッサ１８０とで、ＳＯＮノード２１０がここに述べる１つ以上の動作を遂行するようにさせるよう構成される。一例において、例えば、ＳＯＮモジュール２３０−２は、ここに述べる機能の幾つか、多数又は全部を遂行するように（例えば、機能を遂行するための手段として）実施され、そしてハードウェアで（例えば、ゲートアレイ又は半導体回路においてプロセッサ１８０の一部分として）実施されるか、コンピュータプログラムコード１８０の一部分として実施されるか、或いはハードウェア又はコンピュータプログラムコード１８０のある組み合せとして実施される。ＳＯＮノード２１０は、任意であるが、ここに述べる１つ以上のアクションに対して集中的実施で使用される。１つ以上のネットワークインターフェイス１９０は、ネットワーク１７３、１７５のようなネットワークを経て通信する。
【００２４】
ｅＮｏｄｅＢ２２０は、バックホールリンク１８２の一部分である、例えば、ネットワーク１７３を使用して通信する。ネットワーク１７３は、ワイヤード又はワイヤレス或いはその両方であり、そして例えば、Ｘ２インターフェイスを実施する。ＳＯＮノード２１０は、ネットワーク１７５を使用して、ｅＮｏｄｅＢ２２０と通信する。ネットワーク１７５は、ワイヤード又はワイヤレス或いはその両方である。
【００２５】
ｅＮＢ２２０−１は、他の（例えば、小型セルの）ｅＮＢ２２０−２ないし２２０−ｎにゲートウェイ（ＧＷ）サービスを提供するマクロｅＮＢである。以下に述べるように、ネットワーク１００がサブネットワークへと区画化されるように他の（例えば、下位の）ｅＮＢ２２０のセットにＧＷサービスを提供する多数のｅＮＢ２２０が存在する。典型的に、例えば、１つ以上のリンク２１６を経てｅＮＢ２２０及び／又はＳＯＮノード２１０が接続されるコアネットワーク（ＣＮ）２１５が存在することに注意されたい。ＣＮ２１５は、多数の異なる要素を含み、その一例が、ＭＭＥ、ＳＧＷ及び／又はＯＡＭである。又、ＣＮ２１５は、インターネットのようなネットワーク２２５にも接続される。
【００２６】
コンピュータ読み取り可能なメモリ１５５及び１９５は、ローカルの技術環境に適したタイプであり、適当なデータストレージ技術、例えば、半導体ベースのメモリ装置、フラッシュメモリ、磁気メモリ装置及びシステム、光学的メモリ装置及びシステム、固定メモリ及び取り外し可能なメモリを使用して実施される。プロセッサ１５０及び１８０は、ローカルの技術環境に適したタイプであり、非限定例として、汎用コンピュータ、特殊目的コンピュータ、マイクロプロセッサ、デジタル信号プロセッサ（ＤＰＳ）、及びマルチコアプロセッサアーキテクチャーに基づくプロセッサ、の１つ以上を含む。
【００２７】
本発明の幾つかの規範的実施形態を具現化するための１つの適当な非限定の技術的状況を以上に紹介したが、付加的な実施形態の紹介及び説明を以下に詳細に行う。説明を容易にするため、本開示を章に分割する。
【００２８】
第１章．序文
５Ｇネットワークでは、小型セルアクセスポイントの街路レベル配備、及び例えば、掲示板、街灯柱、及び他の電柱におけるそれらの搬送解決策が仮定される。ｍｍＷ無線技術は、バックホールのための必要容量、帯域巾及びレイテンシー性能を与えるが、視線接続を要求する。従って、リンク性能は、一時的障害物、天候条件、及びマストの揺れにより影響を受ける。街灯柱等のマストの揺れに対抗するために電気的なビーム操向が使用されるが、それに加えて、別のルートへの高速再接続を行うために動的なネットワークレベル経路回復が必要となる。５Ｇ小型セルバックホール解決策は、ネットワーク故障及びリンク劣化に対して高速な回復を与えねばならない。ネットワークの融通性及び信頼性の目標レベルに到達するために、マイクロ秒レベルの保護切り換え及び故障回復が仮定される。又、ユーザトラフィックの動的な変化及び変動に効果的に対抗するため負荷バランス及びトラフィック最適化に対して同じレベルの応答時間が期待される。起源から行先まで（例えば、移動ユーザからコアネットワークのアプリケーションサーバーまで及びその逆）の端−端性能が考慮されるので、ネットワーク故障及びトラフィック混雑に対する高速且つ動的な反応をネットワーク規模でサポートすることが重要である。
【００２９】
甚だしい数の接続ノードがあるので、５Ｇ小型セルバックホールネットワークは、配備、管理及び拡張が容易でなければならない。ＯＰＥＸ及びＩＭＰＥＸコストダウンを保持するには、運営者によるネットワーク構築及び運営段階中の人間管理行動を最小にしなければならない。
【００３０】
大容量ペンシルビーム（例えば、他の波長に比して極めて細い）ミリメータ波（ｍｍＷ）リンクに基づくワイヤレスメッシュネットワーク（ＷＭＮ）は、５Ｇネットワークにおける小型セルバックホールのための魅力的な解決策を提供する。空間的ＴＤＭＡの利点を取り入れることで、ネットワーク容量を効率的に利用することができる。しかしながら、５Ｇ遅延目標を満足できるリンクスケジューリング及びルーティングメカニズムを開発することが課題となっている。更に、ルーティング及びリンクスケジューリングは、相互に強く結び付いているが、同時に最適化することが非常に困難である。又、メッシュルーティング技術は、小型セルの状況において顕著なものとなるワイヤレスリンクの劣化及びネットワークトラフィック負荷の変動に迅速に適応させるために負荷バランス能力も組み込んでいなければならない。
【００３１】
全ての小型セルノードがメッシュで相互接続され且つ一度にアンテナセクタ当たり１つの隣接ノードしか指さない区分化細ビームのビーム操向ワイヤレスバックホール無線が各ノードに設けられた５Ｇ小型セルネットワークでは、ネットワークスループットを最大にするためにアクティブにすることのできる同時トランスポートリンクのグループを識別し且つ最適化する必要がある。図２を参照すれば、この図は、ＷＭＮ送信セットの例示で、８つの送信セットＴ１ないしＴ８の各々に対してＴＤＤ形態でアクティブとなることのできる同時にバラバラのリンクのグループを示している。ノード２８０−１は、マクロセル（例えば、ｅＮＢ２２０−１を有する）であり、ノード２８０−２ないし２８０−７は、小型セル（例えば、ｅＮＢ２２０−２ないし２２０−７を各々有する）である。ノード２８０間には１１個の考えられるリンク２８０がある。図２は、一度に１つの隣接部しかない（即ち１つのセクタしかない）状態で、ノードがＴＤＤ形態で通信するときに、ワイヤレスバックホールメッシュ接続５Ｇ小型セルネットワークの問題スペースを示している。これは、一度に１つの隣接部に向かって操向できる細ビームのビーム操向ワイヤレスバックホール無線部が各ノードに設けられたときにノード当りのワイヤレスバックホールコストを最小にする。マクロセル２８０−１は、全ての下位の５Ｇ小型セル２８０−２ないし２８０−７に対するゲートウェイとして働く。
【００３２】
図２に示すように、同時にバラバラのワイヤレスバックホールリンクの各グループは、送信セットと称される。一例として、８つの送信セット（Ｔ１ないしＴ８）が図１に示されている。規範的なスケジュールサイクルは、（Ｔ１、Ｔ６、Ｔ８、Ｔ３、Ｔ２、Ｍ）であり、ここで、Ｍは、新たな隣接部に対してスキャンすべき監視スロットである。各送信セットに対して、次のリンクがアクティブとなる。Ｔ１については、リンク２９０−２、２９０−３、２９０−８及び２９０−１１；Ｔ２については、リンク２９０−１、２９０−４、２９０−６及び２９０−９；Ｔ３については、リンク２９０−２、２９０−４、２９０−７及び２９０−９；Ｔ４については、リンク２９０−３、２９０−５、２９０−７及び２９０−９；Ｔ５については、リンク２９０−１、２９０−３及び２９０−１１；Ｔ６については、リンク２９０−６、２９０−８及び２９０−１０；Ｔ７については、リンク２９０−３、２９０−８及び２９０−１０；及びＴ８については、リンク２９０−３、２９０−７及び２９０−１０。
【００３３】
この開示では、例えば、図２に示す５Ｇ小型セルネットワークのワイヤレストランスポートの性能及び効率を最大にする緊密結合のルーティング及びスケジューリング解決策で５Ｇ小型セルバックホールのために最適化された革新的ネットワーク概念が提案される。この提案される概念は、ネットワーク故障に対する高速自律保護を与え、ユーザトラフィック変動に対抗する動的な負荷バランスを与え、且つ配備、管理及び拡張が容易である。
【００３４】
第２章．追加の序文
ＴＤＭベースのトランスポート技術は、レガシー移動通信システムに対してベースステーションサイトとコアネットワークとの間に基本的且つ弾力性のあるトランスポートサービスを提供する。しかしながら、それらのシステムは、動的な容量割り当て及びアクセス容量に関してはかなり融通性がなく、多量の非同期のトラフィック量を取り扱うことができない。従って、バックホール部分のパケットベース技術が、その容量柔軟性、低コスト及び高管理性特徴のために不可避となる。現在、最も一般的なパケットベースのバックホール技術は、キャリアイーサネット（登録商標）トランスポート、プレインＩＰトランスポート及びＩＰ／ＭＰＬＳトランスポートである。
【００３５】
キャリアイーサネットは、本質的に、イーサネットトランスポートを、大きく、複雑で且つ過酷な運営者ネットワーク環境により適したものにするためのプレーンイーサネットに対する改善のセットである。最も一般的なキャリアイーサネット技術は、プロバイダーブリッジング（ＰＢ）、プロバイダーバックボーンブリッジング（ＰＢＢ）、及びプロバイダーバックボーンブリッジング−トラフィックエンジニアリング（ＰＢＢ−ＴＥ）である。典型的に、キャリアイーサネットプロトコルは、ルーピング及び不要なブロードキャストストームを防止するためスパニングツリープロトコルを一緒に実行する必要がある。又、サービスクオリティ（ＱｏＳ）は、キャリアイーサネットでは問題であるが、ＰＢＢ及びＰＢＢ−ＴＥでは状態が良好になる。キャリアイーサネット解決策の弾力性は、エラーの検出遅延及び使用するスパニングツリープロトコルの収斂時間に大きく依存する。合成検出及び収斂の典型的な値は、ラピッドスパニングツリープロトコル及びイーサネットＯＡＭでは、ほぼ１秒である。これは、先の章で注目したように、将来の５Ｇネットワークに対する本来の要求より数十も悪い。
【００３６】
３Ｇ以降、移動通信システムは、固定のトランスポートに対してＩＰをサポートしてきた。ＩＰは、トランスポートレイヤプロトコルＴＣＰ（送信コントロールプロトコル）、ＵＤＰ（ユーザデータグラムプロトコル）又はＳＣＴＰ（ストリームコントロール送信プロトコル）に関連して使用される。ＩＰは、当然、ルーティング情報を配布するためにルーティングプロトコルを要求する。ＯＳＰＦ（オープンショーテストパスファースト）、ＩＳ−ＩＳ（中間システム対中間システム）、及びＢＧＰ（ボーダーゲートウェイプロトコル）は、全て、異なるバックホールネットワークに見られる。サービスクオリティについて、ＩＰは、ホップごと又はドメインごとの目標値に従ってパケットスケジューリングを制御するＤｉｆｆＳｅｒｖ（微分型サービス）及びＩｎｔＳｅｒｖ（積分型サービス）スキームを使用する。又、ＩＰは、デフォールトルーティング及びリンク重み付けのような制御プロトコルを通して幾つかのトラフィックエンジニアリング能力を提供する。ＩＰネットワークの弾力性は、エラーの検出遅延及び使用するルーティングプロトコルの収斂時間に大きく依存する。このルーティングプロトコルの典型的な値は、ＩＧＰ（内部ゲートウェイプロトコル）では数秒であり、そしてＢＧＰでは数十秒であり、これも、５Ｇバックホールでは受け容れられない。
【００３７】
ＩＰ／ＭＰＬＳは、おそらく、最も使用される運営者コアトランスポート技術である。ＭＰＬＳは、実際には、到来するパケットに特殊なシムヘッダでタグ付けした後に、それらシムヘッダのラベルをＭＰＬＳクラウドにわたって切り換えてＭＰＬＳトンネルを形成するレイヤ２．５プロトコルである。ＭＰＬＳトンネルは、ＬＤＰ（ラベル配布プロトコル）を使用することにより生成でき、これは、次いで、トポロジー知識のためのルーティングプロトコルを、完全に手動で、或いはＲＶＳＰ−ＴＥ（リソース予約プロトコルトラフィックエンジニアリング）を使用するＰＣＥ（経路計算要素）と共に、必要とする。バックホールネットワークについては、ＩＰ／ＭＰＬＳは、例えば、アグリゲーションネットワークを経てベースステーションのクラスターをそれに対応するコントローラに接続するのに使用されるレイヤ３及びレイヤ２ＶＰＮ（バーチャルプライベートネットワーク）のような多数の接続サービスを提供する。又、ＭＰＬＳは、トンネル生成及び到来トラフィック取り扱いに関しても広範なトラフィックエンジニアリング能力を提供する。ＭＰＬＳ（ＤＳ−ＴＥ）ネットワークのサービスクオリティは、ＤｉｆｆＳｅｒｖで取り扱われる。ＭＰＬＳネットワークの弾力性は、極めて良好で、収斂も速いが、最良の性能を得るために手動の構成を必要とする。典型的な値は、ＭＰＬＳ経路保護では数百ミリ秒であり、そしてＭＰＬＳ  ＦＲＲ（高速リルート）では約５０ミリ秒であるが、以下の例では、パケットドロップなしに且つ再送信の必要なしにマイクロ秒の値を得ることができる。両ＭＰＬＳ方法は、保護経路又はリンクの事前構成を要求する。別の可能性は、より自動化されたが、リンクが切断した後に制御平面のルーティングプロトコルが収斂した後でなければ収斂しないＬＤＰを使用することであるが、本発明の革新では、保護経路の選択が、動的であり、オンデマンドであり、そして保護のための余分な容量を割り当てる必要なく自動的に実行される。更に、ＭＰＬＳ−ＴＰでは、ＧＭＰＬＳベースの制御平面が使用され、これは、ＬＳＰシグナリングのためにＲＳＶＰ−ＴＥに依存する。
【００３８】
要約すれば、ワイヤードネットワークのために設計されたトラフィックエンジニアリング特徴を伴うルーティング解決策は、静的なワイヤレスメッシュネットワーク（ＳＷＭＮ）には直接的に適用できない。ＳＷＭＮルーティングのための参照規格の１つは、ＩＥＥＥ８０２．１１ｓ（情報テクノロジーのためのＩＥＥＥ規格−システムローカルエリアネットワークと都市エリアネットワークとの間でのテレコミュニケーション及び情報交換−特定要件、パート１１：ワイヤレスＬＡＮ媒体アクセス制御（ＭＡＣ）及び物理的レイヤ（ＰＨＹ）仕様書、ＩＥＥＥ規格８０２．１１−２０１２、セクション１３．１０、ページ１３８２−１４１３を参照）に規定されたハイブリッドワイヤレスプロトコル（ＨＷＭＰ）であり、これは、先験的トポロジーツリー構築をオンデマンドルート発見と結合するものである。本発明では、事前計算ツリーを配備する考え方が共有される。Ｓ．アバロン及びＧ．Ｄ．スタシ著の“A new MPLS-based forwarding paradigm for multi-radio wireless mesh network”、ＩＥＥＥトランザクションズ・オン・ワイヤレスコミュニケーションズ、第１２巻、第８号、第３９６８−３９７９ページ、２０１３年において、“resilient directed acyclic subgrah”方法は、中間の転送ノードでもトラフィックの分割を許す負荷バランシングスキームと結合される。このスキームは、既知の最大トラフィック強度を縁ノードにもつホーストラフィックモデルを仮定している。更に、ネットワークトポロジーは、比較的固定であり、そしてノードが追加又は除去されるとき（一時的を含めて）しか変化しないと考えられる。対照的に、以下に述べる技術では、実際のトラフィック負荷及び優勢なネットワーク容量に従ってトラフィックが分割される。更に、技術は、以下に述べるように、除去されないが、例えば、午前と午後との間にトラフィックピークレートが変動するノードに向けられる。実際の負荷に従って、トラフィックを分割する方向に向けて、Ｇ．キャプデホーラット、Ｆ．ラロカ、及びＰ．ベルラゼナ著の“Optimal multipath forwarding in planned wireless mesh networks”コンピュータコミュニケーションズ、第３８巻、第０号、第３６−４９ページ、２０１４年は、“minimum queue length load-balancing”を提案しており、これは、各ネットワークリンクの平均キュー長さを表わす機能の初期測定ベース学習に依存するものである。又、混雑を推定するために、本発明ではキュー長さも監視される。しかしながら、ここに提示する技術では、キュー長さスレッシュホールドのオーバークロスは、必要に応じてトラフィック分割をトリガーするためにリアルタイムで明確にシグナリングされる。又、バックプレッシャールーティング（Ｊ．ナヌツ、Ｊ．バランダ、及びＪ．マンギュー著の“A self-organized backpressure routing scheme for dynamic small cell deployment”、アドホックネットワーク、第２５巻、パートＡ、第１３０−１４０ページ、２０１５年２月を参照）は、ルーティング判断のためにキューバックログを使用するが、性能保証は与えない。
【００３９】
空間的ＴＤＭＡ（ＳＴＤＭＡ）ＳＷＭＮでは、ルーティングをリンクスケジューリングと共に考慮しなければならず、これは、ルート計算とスケジュール計算との間の相互作用による負荷バランシングスキームを提示しているＷ．Ｊ．ヤン、Ｙ．リー、及びＢ．Ｃキム著の“Joint link scheduling and routing for load balancing in STDMA wireless mesh networks”、インターナショナル・ジャーナル・オブ・コミュニケーション・ネットワーク・アンド・インフォメーション・セキュリティ（ＩＪＣＮＩＳ）、第６巻、第３号、２０１４年に言及されたものである。最小のままのリンク容量を最大にすることを目的とするこの解決策は、静的なリンク容量を仮定し、そしてリンクスケジュールにおけるスロット順序を無視する。ここに提示されるある技術では、ルートの事前計算がリンク容量に関して最小の仮定をする。むしろ、本発明では、ルートの多様性による容量低下に対して準備が試みられる。本発明のリンクスケジューリングは、事前に計算された一次経路における最大の端−端遅延を最小にすることを目的とする。本発明のルート事前計算という句は、ルーティングツリーの「ステム」を生成し、これは、Ｉ．アムドーニ、Ｃ．アジー及びＰ．マイネ著の“Joint routing and STDMA-based scheduling to minimize delay in grid wireless sensor networks”、ＣｏＲＲ、第ａｂｓ／１４０２．７０１７巻、２０１４年の“dominating trees”と若干同様であるが、本発明のケースでは、リンクスケジューリングとの一体化が、高速両方向性のゲートウェイ経路を生成し、一方、センサネットワークでは、上流方向だけに最適化することに関心がもたれる。
【００４０】
メッシュトポロジーでのサービス利用性に対するｍｍＷリンクの壊れ易さの影響は、次のものにおいて考慮されている。Ａ．ジャバー、Ｊ．Ｐ．ローレル、Ｖ．Ｓ．フロスト、及びＪ．Ｐ．スターベン著の“Survivable millimeter-wave mesh networks”、コンピュータコミュニケーションズ、第３４巻、第１６号、第１９４２−１９５５ページ、２０１１年；及びＮ．ヤブド、Ｅ．リヨン、Ｍ．ジンク、及びＴ．ウォルフ著の“Adaptive wireless mesh networks: Surviving weather without sensing it”、コンピュータコミュニケーションズ、第５４巻、第０号、第１２０−１３０ページ、２０１４年。リンクの不安定さを克服するため、他のものの中でもリンクメトリックにビットエラー率（ＢＥＲ）を付加する先験的且つ予想的ルーティングプロトコルが提案されている。同様に、本発明では、リンク状態情報の利用性が仮定されるが、この情報を全ネットワークに広めることを伴い、この情報は、例えば、保護経路を経て欠陥リンクをバイパスするために中断ポイントで瞬間的に使用される。ここでは、カラーツリー（欠陥、ＩＥＥＥ／ＡＣＭ  Ｔｒａｎｓ．Ｎｅｔｗ、第１７巻、第１号、第３４６−３５９ページ、２００９年２月）を使用して、バラバラの経路を最大限与えることができるが、他の多数の望ましい経路のプロパティが犠牲になる。
【００４１】
ＳＷＭＮのリンクスケジューリング問題に対してここに提示される技術の動機は、次のものから見出される。タシラス、Ｌ、エフレミド、Ａ著のJointly Optimal Routing and Scheduling in Packet Radio Networks、ＩＥＥＥトランザクションズ・オン・インフォメーション・セオリー、第３８巻、第１号、１９９２年１月。このＩＥＥＥ論文は、繰り返しスケジュールを使用せず、最小退避時間−メトリックを定義する。ルーティング及びスケジューリングのジョイント最適化を取り扱う研究論文は、典型的に、それらがその状況において最良のスケジュールを達成することを証明するよう試みる。ここでの幾つかの例において、経路の所与の収集に対する従来の端−端（Ｅ２Ｅ）遅延基準を満足するスケジュールが許され、そして充分な計算リソースがある場合は、実現可能なスケジュールをほぼ常に得ることができる。この種の問題は、タスクがある規定のトランスポート容量を（例えば、トラフィック推定に従って）ノード対間に与えるべきであるケースとして早期に公式化されている。リンクスケジュール、例えば、リンク着色を割り当てて、実現可能なスケジュール及びリニアプログラミング（ＬＰ）を見出し、カラースロットの巾を同調させ、そしてルート（例えば、整数ＬＰ（ＩＬＰ））を計算するために良く知られた幾つかの最適化アルゴリズムが使用される。このプロセスは、反復的であり、例えば、第１に、リンクスケジュールを割り当て、次いで、ルーティングを行い、そして解決策が受け容れられない場合は、ルーティングボトルネックに関する情報を使用してリンクスケジュールを再割り当てし、リルートし、等々である。このタイプのリンクスケジューリング及びルーティング方法に伴う欠点は、計算費用がかかり、更に最適化要求を含ませることで、より複雑になることである。更に、それにより生じる容量共有は、極めて厳格であり、そしてトラフィック需要の変化に反応できない。欠陥許容は、更に、特殊な配慮を必要とし、例えば、リソース予約を伴う事前構成の保護経路を必要とする。
【００４２】
全体的にみれば、既存のルーティング及びスケジューリング技術は、著しく変動するトラフィック負荷、種々のフロープライオリティ及び不安定なリンク容量を考慮しつつ、どのように遅延保障を与え且つネットワークリソースの最も効率的な使用をするかの問題に対して部分的な回答しか与えないと思われる。本解決策の一例は、小型セルバックホーリングに適用できるより包括的な実際的なｍｍＷのＷＭＮ解決策に向かう試みである。規範的ルーティング及びリンクスケジューリングの実施は、リソース消費の全ての計算（スパニングツリー、ルーティングテーブル、及びリンクスケジュール）を前もって遂行できるので、極めて取るに足らないことである。更に、そのような計算は、ネットワークの外部で専用及び集中型コンピューティングリソースにおいて遂行することができる。リアルタイムで行うべくネットワークノードに残されているのは、転送判断並びに到達性及び混雑情報の監視を行うことだけである。これは、高速リンクに対しても低コスト及び電力効率の良い実施ができねばならない。
【００４３】
更に、トランスポートネットワークに現在使用されている技術によりサポートされるネットワーク異常（例えば、接続の切断及び混雑状態）に対する最高速の回復及び反応時間は、典型的に、慣習的なＳＤＨネットワークの５０ｍｓ回復時間要求から、典型的なＩＰプロトコルのケースの更に長い時間まで、数ミリ秒又は数秒のレベルである。
【００４４】
第３章．規範的実施形態
（例えば）反応時間の改善に向かう目的では、自己編成小型セルワイヤレスメッシュバックホール（ＷＭＮ）解決策の概念的枠組みが、例えば、先験的ルート事前計算を迅速反応自己治癒及び自己最適化メカニズムと結合できる特殊な内蔵トラフィックエンジニアリング特徴のセットと共に、ここに開示される。自己治癒は、非常に高速且つ柔軟なネットワークレベル自律的欠陥管理を含む。自己最適化は、認証、動的及び拡張可能なネットワークトポロジー最適化、柔軟なサービスクオリティ（ＱｏＳ）、混雑管理、及びトラフィック負荷バランシングを伴う自律的バックホールノード配備及び構成を含む。これらのメカニズムは、メッシュネットワークの内部でトラフィックフローの非常に柔軟な制御及び操向を行えるようにし、従って、所与の時間にトラフィックの自動ＱｏＳ認識最適化を可能にし、メッシュネットワークの全トランスポート容量を最適に利用できるようにする。
【００４５】
実施例においてペンシルビームｍｍＷリンク及び迅速ビーム操向に基づくＷＭＮが仮定される。ｍｍＷアンテナ実施は、全カバレージ又はセクタベースである。電子ビーム操向は、ネットワークの追加のコスト節減、高信頼性及び単純な拡張のために多数のリンクを同じ装置でサポートできるようにする。
【００４６】
バックホールネットワークは、例えば、最大２００個のノードより成るドメインと称される独立したサブネットワークに分割される。現実の例において、１つのドメインは、小型セル（例えば、マイクロ又はピコベースステーション）が配備される都市エリアのある部分をカバーする。各ドメインは、他のトランスポートネットワークへのアクセスを与えるゲートウェイ（ＧＷ）と称される１つ又は多数の特殊な要素を有する。多数のドメインを一緒に結合して広いエリアを形成することができる。
【００４７】
より特定すれば、一例において、メッシュネットワークのハイアラーキー定義を次のように生成することができる。
−エリアは、中央コントローラにより制御されるドメインのグループである。
−ドメインは、ルーティング経路を生成するために共通のリンクスケジュール及びスパニングツリーオーバーレイを有するノードのグループである。ドメインは、少なくとも１つのゲートウェイを含まねばならず、これは、ドメインにおける唯一のノードである。
−物理的トポロジーは、発見される物理的リンクで形成されるトポロジーである（例えば、中央コントローラに報告され且つ中央コントローラに知られるが、必ずしもスケジュールされない）。
−アクティブなトポロジーは、物理的なトポロジーにおけるスケジュールされたリンクを含む。
【００４８】
高速のエラーなし保護スイッチング及び動的な負荷バランシングに対して、革新の１つの例は、起源から１つのドメイン内の行先、即ち部分的メッシュトポロジーを形成するバックホールノードの限定サブネットワークへの別のルーティング経路の事前計算セットを使用することである。これらのルートは、あるトポロジーに対して事前に計算され、そして動的及びローカルトラフィック状況に基づいてローカル転送及び負荷バランシング判断のためにドメイン内の全てのノードへ配布される。本説明において、バックグランド事前計算は中央エンティティで遂行されるが、ここに述べる技術は集中型解決策に限定されない。
【００４９】
幾つかの実施形態において、各起点−行先対のための一次経路及び１組のバックアップ経路を生成できるルーティング方法が提案される。更に、欠陥に対する迅速な即座の反応を保証し、次いで、変化した状況に対する最適な適応を保証するために異なる時間スケールで作用する種々の保護及び回復方法を含むハイアラーキー型欠陥回復システムが説明される。このルーティング方法の背後にある１つの原理は、ツリーが最大数に近いノードのバラバラのルートを与えて、弾力性を発揮させると共に、負荷バランスを可能にするように構成された多数のスパニングツリーに基づくものである。
【００５０】
方法の一例は、次の要素の１つ以上を含む。以下に述べる１３個の要素があり、その各々が番号で指示される。
【００５１】
この要素については、ネットワークが、より小さな限定サイズのサブネットワーク（ドメインと称される）に分割され、そこで、独立したルーティング及びスケジューリングが遂行される。リンク／ノード欠陥に対する高速の応答は、代替物及びローカル状態情報の事前計算リストから最良の利用可能なルーティング経路を選択することにより保証される。
【００５２】
ここに提案するが非限定である１つの最大サイズは、２００個のノードである。本発明では、解決スペースをこの数のノードに限定することにより、計算が高速で（例えば、リアルタイム応答を与える）、迅速に収斂し、そしてマイクロ秒レベルの高速スイッチング及び短いレイテンシー（例えば、多数の無線ホップを経て起点と行先との間に数ミリ秒の往復遅延がある）についての必要な性能を与える方法を構成することができる。
【００５３】
この要素について、例えば、図３には、利用可能なトランスポートリソースの最適な使用及び共有を可能にするトポロジー管理システム／モジュールが開示される。図３は、ある実施形態におけるトポロジー管理機能アーキテクチャーの一例である。
【００５４】
トポロジー管理機能３１０は、例えば、ノード間の相互作用及びトラフィックに基づいて、ドメインへのノードの分割を最適化する。多数のドメインを、共通トポロジー管理のエリアへと結合することができる。
【００５５】
トポロジーマネージャー３１０のトポロジー管理は、ＷＭＮの自律的増殖的配備並びにＷＭＮの自己編成及び自己最適化をサポートするのに必要な機能を含むと共に、ネットワーク管理に必要な他の機能を含む。メイン機能は、アクセス制御、トポロジー最適化、ルート及びリンクスケジュール計算、バーチャル接続のプロビジョニング、エネルギー節約制御、及び構成管理を含む。
【００５６】
トポロジーオプチマイザー３２０は、次のことを遂行する。
○どのリンクがアクティブネットワークに含まれ、どれが含まれないかのアクティブトポロジーを決定し；
○必要に応じてＷＭＮドメインを分割及び合併することによりネットワークトポロジーを最適化し；
○ネットワークノードに対してノード識別子を割り当て；及び
○新たなＧＷが必要かどうか及びどこで必要かを指示する。
【００５７】
ルート計算３２５（以下の要素（４）の説明も参照）は、次のことを遂行する。
○物理的ＷＭＮトポロジーが変化するときに新たなスパニングツリー（ＳＴ）を計算し；及び
○リンクスケジュール及びＳＴ構造を使用して、ネットワークの各起点−行先対についてＳＴの優先度を指定する。
【００５８】
リンクスケジュール計算３３０は、ＷＭＮトポロジー及び／又はＳＴが変化するときに新たなリンクスケジュールを計算する（以下の５も参照）。
【００５９】
エネルギー節約コントローラ３３５は、エネルギー節約機能を管理する（以下の要素１２の説明も参照）。
【００６０】
ＶＣプロビジョニング３４０は、ＷＭＮにおけるバーチャル接続オーバーレイを管理する。
【００６１】
ＷＭＮコンフィギュレータ３５０は、新たなＷＭＮリンクトポロジー、ルーティング、及びリンクスケジュール情報からＷＭＮ構成をコンポーズする。
【００６２】
ネットワーク状態モニタ３７０は、次のことを遂行する。
○ＷＭＮからの受信メッセージに基づいて最新の状態ビューをコンポーズし；
○どの状態情報をいつ他のモジュールへ転送するか決定し（例えば、ネットワーク状態監視機能の一部分がＧＷに存在し、これが状態情報を更なる集中処理のためにアグリゲートし）；及び
○性能監視（ＰＭ）データベース３６５を経て性能監視情報を外部ネットワーク管理システムへ報告する。
【００６３】
アクセスコントロール３４５は、新たなＷＭＮノードを認証するためのＡＡＡ（認証、許可及びアカウント）インフラストラクチャーを備えている。アクセスコントロールという語は、外部ＡＡＡ及び他の同様のネットワーク管理機能への接続を指す。
【００６４】
トポロジーデータベース３５５は、ネットワークトポロジーの提示、即ちノード、それらの位置（物理的又は相対的）、及びそれらがどのリンクを経て一緒にどのように接続されるかを含む。
【００６５】
トポロジー管理システム／モジュール、特に、ＶＣプロビジョニングは、外部ネットワークマネージメントシステム（ＮＭＳ）によりＮＭＳエージェント３６０を経て制御される。
【００６６】
実施については、集中型エンティティ（ここでは、ＷＣＣ、ＷＭＮ集中型コントローラと称される）が仮定される（例えば、ＳＯＮノード２１０のＳＯＮモジュール２３０−２）。全てのバックグランド計算及び制御タスクの世話をする集中型制御エンティティをもつことにより、ＷＭＮノードハードウェアの要件を緩和することができる。というのは、全てのＣＰＵ（中央処理ユニット）及びメモリ集中計算が特殊なサーバーで遂行されるからである。更に、ＷＣＣは、多数のＷＭＮドメインとで共有できるので、ＣＰＵリソースをより効率的に利用することができる。又、集中型コントローラは、必要な全ての情報が一箇所にあるので、ＷＭＮドメイン間最適化を良好に制御することができる。
【００６７】
分散型実施（例えば、ｅＮＢ２２０のＳｏＮモジュール２３０−１を使用する）も考えられるが、一貫した仕方で全てのノードに対する必要な情報を収集する必要がある。全てのノードが同じ情報を有していなければならず、さもなければ、システムは、安定な状態に収斂できない。
【００６８】
図４を参照すれば、トポロジー管理プロセスフローの一例が示されている。この図は、規範的方法の動作、コンピュータ読み取り可能なメモリで実施されるコンピュータプログラムインストラクションの実行結果、ハードウェアで実施されるロジックにより遂行される機能、及び／又は幾つかの規範的な実施形態により機能を遂行するための相互接続された手段を例示する。図４のブロックは、例えば、ＳＯＮノード２１０のＳＯＮモジュール２３０−２によって遂行され、これは、ＳＯＮノード２１０がブロックを遂行するようにさせる。それ故、ＳＯＮモジュール２３０−２及びＳＯＮノード２１０は、例えば、ＷＣＣとして働き、そしてこの仮定が以下で使用される。
【００６９】
図４において、ブロック４０５、４１５、４２５、４３５、４４５、４５５及び４７０は、データを示し、そして他のブロックは、機能である。ブロック４１０において、ＷＣＣ（エリアデータ４０５の物理的リンクを使用する）は、エリア区画化を遂行し、そしてドメインデータ４１５の物理的リンクを生成する。ブロック４２０において、ＷＣＣは、（データ４１５を使用して）リンク切断４２０を遂行して、ドメインデータ４２５のアクティブリンクを生成する。ブロック４３０のＷＣＣは、（データ４２５を使用して）ルート計算を遂行して、ドメインデータ４３５のスパニングツリーを生成する。ＷＣＣは、（データ４３５を使用して）ブロック４４０の計算をスケジュールし、ドメインデータ４４５のリンクスケジュールを生成する。ブロック４５０において、ＷＣＣは、異なるＳＴを使用してクライアントトラフィックがＷＭＮドメインを経てどのようにトランスポートされるかであるＶＣプロビジョニング４５０を遂行し、ドメインデータ４５５のバーチャル接続を生成する。ＷＣＣは、データ４３５、４４５及び４５５を使用してブロック４６０の構成を遂行し、ドメインデータ４７０に構成メッセージを生成する。それらの構成メッセージは、ドメインへ送られて、ドメインを再構成させる。
【００７０】
３）ルーティング及びスケジューリングの問題（ドメイン内の）が２つの部分、即ち、先ず、ドメイン内のいわゆる一次ルーティング経路の適当なセットを見出すこと、次いで、それらの経路に対してリンクスケジュールを最適化すること、に分割される解決策のこの要素について一例を開示する。
【００７１】
４）この要素は、各５Ｇ小型セルノードに対して多数のルーティング経路を識別するルーティングスキームを含む。このルーティングスキームは、次のように実施される。
【００７２】
ルーティングスキームは、高速欠陥回復及び負荷バランシングのために全ての起点−行先対について一次及びバックアップルーティング経路を生成する。多数のスパニングツリーが構成され、それらのツリーは、最大数に近いノードのバラバラのルートを与え、弾力性を与えると共に、負荷バランシングを可能にする。
【００７３】
ゲートウェイ（ＧＷ）に直接隣接するリンクは、最も重要なリンクであり、それらの各リンクは、ＧＷである根(root)に接続された「ステム（幹）」と称される。各ステムは、ネットワークの全てのノードがカバーされるまでブランチ（枝）へと同時に成長する。全ブランチの連合は、トポロジーの全ノードを含む。
【００７４】
各ブランチは、全トポロジーをカバーし且つリーフ（葉）ノードを最適化する完全スパニングツリーへと成長する。一例として、リーフノードを別の親ノードへ移動することで（利用できる親への直接的なホップリンクがあることで）ＧＷへの小さなホップカウントが生じる場合には、リーフノードが移動される。スパニングツリーの数は、ステムの数に等しく、ステムの数は、ＧＷへのノード当りのルート(route)の数に等しい。
【００７５】
ノードごとに、次のことを行うことによりＧＷへの多数のルート又は経路のプライオリティを識別する。
○先ずＧＷへのホップカウントによる（例えば、最も高いプライオリティは、最も少ないホップカウントである）；
○ノードの重みを使用することで等しいホップカウント状態での束縛を切断し；及び
○最も高いプライオリティの経路は、一次経路と称される。
【００７６】
図５Ａは、５Ｇ小型セルネットワーク２０ノードトポロジーのためのここに提案するルーティングスキームの一例におけるステム、ブランチ及びツリー概念を示す。即ち、２０個のノード２８０があり、そのうちのゲートウェイノードが２８０−１である。３つのゲートウェイ（ＧＷ）リンク１、２及び３があり、それ故、３つのステム２３０−１（ステム１）、２３０−２（ステム２）及び２３０−３（ステム３）がある。リンク２９０の合計数は、３２である。ステム２９０−１、２９０−２及び２９０−３に各々対応する３つのブランチ５３０−１、５３０−２及び５３０−３が示されている。
【００７７】
図５Ｂは、図５Ａにおけるステム、ブランチ及びスパニングツリーのツリー構造図である。３つのステム５３０−１、５３０−２及び５３０−３は、ツリー５９０においてブランチとして見られる。図５Ｃは、図５Ａにおけるステム、ブランチ及びスパニングツリーのテーブル表示である。図５Ｃは、一次経路における１９のリンクを示す。一次経路という考え方は、遅延に敏感なトラフィックに対するものである。目標は、遅延（又は遅延変化）に敏感なトラフィックに対して、ここに述べる実施形態が予想可能なＱｏＳ（リンクスケジューリング、一次経路及びプライオリティキューによりほぼ保証された）を提供できることである。
【００７８】
リンク５９０及びノード５８０の両方に重みを使用して、使用ケース及び現実の配備に対するルート計算を更に最適化し且つ調整することができる。デフォールトでは、全てのリンクが等しく且つ全てのノードが等しい。リンクの重みを使用して、例えば、低及び高（例えば、ｍａｘ）容量リンク（例えば、１０−１００Ｍビット／ｓ対１−１０Ｇビット／ｓ）を区別することができる。ノードの重みを使用して、セルの異なるサイズ／容量を、例えば、それらの仮定した合成トラフィックスループットに基づいて分離することができる。
【００７９】
多数のＧＷを有するドメインでは、前記手順がＧＷごとに適用される。これは、実際上、各ノードから全てのゲートウェイへの多数の代替経路があって、ＧＷ欠陥に対する保護スキームを提供する状態を導く。
【００８０】
５）この要素については、先ず、送信セットを構成し、次いで、それらに、最適なＥ２Ｅ遅延を保証するための繰り返しスケジュールを命令するＳＷＭＮスケジューラが開示される。
【００８１】
各スケジューラサイクルにおいて、各リンクには、ＳＷＭＮスケジューラにより送信するための少なくとも１つの機会が与えられねばならない。
【００８２】
あるリンクは、他のリンクより重要であって、各スケジュールサイクルに、より多くの機会が与えられねばならず、例えば、ＧＷリンク、及び以下に述べる一次経路上にあるリンクがそうである。
○少なくとも１つの一次経路を保持するリンクは、一次経路を保持しないリンクよりも重要であり；
○保持する一次経路の数に従って重みが与えられるリンク及びそれより高い重みをもつリンクは、更に重要であり；及び
○重要なリンクは、スケジュールサイクル当たり少なくとも２回スケジュールされる。
【００８３】
ＳＷＭＮスケジューラは、各スロットの送信セットを識別し、そしてそれを、最大数のバラバラのリンクと共に構成する（バラバラのリンクは、同じ瞬間にアクティブにすることができる）。一例として、本発明では、以下に述べるように、送信セットを調整するためのＧｒｅｅｄｙ［ａｒｇｕｍｅｎｔ］及びＧｒｅｅｄｙＴｗｉｃｅ［ａｒｇｕｍｅｎｔ］方法が提案される（他の同様の方法も適用できる）。
【００８４】
常に送信セットを生成するＧｒｅｅｄｙ［］方法は、下記の通りである。
【００８５】
最も高い重みの最初のリンクから下降順に全てのリンクを通して進む。
【００８６】
各リンクに対して、リンクを取得できるかどうか決定する。
○リンクは、それまで含まれていたものからバラバラにされるか？
○このリンクと以前に選択されたリンクとの干渉を追加し、干渉マトリクス［Ｉi,j］で支援されるか？例えば、Ｉi,jは、リンクｉ（Ｌi）の送信がリンクｊ（Ｌj）と干渉するかどうか指示するバイナリ数であり、イエスであれば、Ｉi,j＝１、そしてノーであれば、Ｉi,j＝０である。
【００８７】
ＧｒｅｅｄｙＴｗｉｃｅ［］方法は、Ｇｒｅｅｄｙ［］方法と共に、以下に述べるように２回（２段階で）遂行される。
【００８８】
第１段階では、Ｇｒｅｅｄｙ［ａｒｇｕｍｅｎｔ］ファンクションコールのアーギュメントに指定されたリンクを選択しない。
【００８９】
第１段階の結果が最大であることを保証するものはないので、Ｇｒｅｅｄｙ［］方法が繰り返され、今度は、全てのリンクを含む。
【００９０】
Ｔ1＝ＧｒｅｅｄｙＴｗｉｃｅ［Φ］、第１の送信セットが識別される。
【００９１】
Ｔ2＝ＧｒｅｅｄｙＴｗｉｃｅ［Ｔ1］、Ｔ1におけるリンクを回避するように試み、第２の送信セットが識別される。
【００９２】
Ｔ3＝ＧｒｅｅｄｙＴｗｉｃｅ［Ｔ1∪Ｔ2］、第３の送信セットが識別される。
【００９３】
そしてこのプロセスは、付加的な送信セットを通して続けられる。
【００９４】
ＳＷＭＮスケジューラは、ＷＭＮの全てのリンクをカバーするサイクル当りの最小スロット数を識別する。
【００９５】
ＳＷＭＮスケジューラは、最適なＥ２Ｅ遅延を保証するためにスケジュールサイクルにおける送信セットの順序を識別することによりスケジュールサイクルの各スロットに送信セットを指定する。最適化目標は、例えば、最大Ｅ２Ｅ遅延を最小にするか又は平均Ｅ２Ｅ遅延を最小にすることである。
【００９６】
６）全体的方法の別の考えられる要素は、トポロジー構成情報を１つのドメインのノードに配布しそしてあるトポロジー構成から別のトポロジー構成への移行を同期させる方法である。この移行は、データ平面の動作に影響するものではない（例えば、パケットドロップは生じない）。トポロジー構成情報は、次のものを含む。
【００９７】
ａ）スパニングツリーの形態の事前計算されたルート代替物、即ちＳＴ構造の仕様及びＷＭＮノード（ＷＮ）特有のＳＴ優先度。各ＳＴは、それ自身の識別子（ＳＴＩＤ）を有する。各ＷＭＮノードは、独特のＷＭＮノードアドレス（ＷＮＩＤ）を有する。
【００９８】
ｂ）スケジュール情報。
【００９９】
ｃ）一般的構成及び認証情報。
【０１００】
７）別の考えられる要素は、ＷＭＮを経てクライアントデータを転送するためのバーチャルコネクション（ＶＣ）及びトラフィックフローの使用に関するものである。
【０１０１】
例えば、入口ノードは、到来するトラフィックを、ＶＣ識別子（ＶＣＩＤ）により識別されるＶＣへとマッピングする。このマッピングは、トラフィック入口ポートＬ２及び／又はＬ３ヘッダ、例えば、イーサネットＭＡＣアドレス並びにＶＬＡＮＤ  ＩＤ及びＰＣＰ（プライオリティコードポイント）、又はＩＰアドレス及びＤＳＣＰ（区別化サービスコードポイント）フィールドに基づいて遂行される。
【０１０２】
ユーザデータは、必要な転送情報を含むＷＭＮフレーム（概念の中）へとカプセル化される。出口ノードは、フレームからＷＭＮヘッダを除去し、そしてユーザデータグラムをクライアントポートへ転送する。図６は、ＷＭＮフレームヘッダフィールドのテーブルである。
【０１０３】
ユーザデータグラムの順序正しい配信については、出口ノードがフレームの再シーケンシングの世話をする。
【０１０４】
８）全方法の要素の別の例は、トラフィックの取り扱いである。トラフィックは、フローとして取り扱われる。フローは、ＱｏＳプライオリティ（ＰＲＩＯ）及びバーチャルコネクションＩＤにより分離される。事前に計算されたルート代替物を使用しそしてローカル負荷及び混雑状態情報に基づくトラフィックのローカル転送。
【０１０５】
大まかなレベルにおいて、入口ＷＮは、事前に計算された経路優先度及び各経路のボトルネックリンクの状態を使用することにより経路を選択する。転送は、ＱｏＳ認識であり、即ちプライオリティクラスごとに異なる転送判断がなされる。
【０１０６】
ＷＮにおける転送判断は、ローカル転送テーブルを使用してなされる。最良の利用可能な経路は、ルート計算により設定される優先度に基づく。第１優先度のルートが利用できないか、混雑が激しいか、又はトラフィック転送に充分な空き容量がない場合には、二次経路が選択され、等々である。
【０１０７】
各ＷＭＮノードは、トポロジー構成情報及びネットワーク状態情報に基づいてローカル転送テーブルを形成しそして維持する。このテーブルは、新たなトポロジー構成が受け取られるたびに、及び例えば、リンク欠陥、リンク混雑又は他の異常を示す新たな状態情報がネットワークから受け取られるたびに、更新される。
【０１０８】
入口ＷＮは、トラフィックフローごとに代替ルーティング経路の適用性を推定する。この推定は、リンクの動作及び混雑状態に関する情報、並びに利用可能なリンク／経路キャパシタンス、公称経路遅延、及びフローの容量要求に基づくものである。リンク状態情報は、全ＷＭＮに配布される。リンクの動作状態は、ワイヤレス物理的レイヤから受け取られる状態指示及びＷＭＮ内部制御メッセージに基づく。混雑は、主として、出力キューの長さにより推定される。
【０１０９】
あるプライオリティの新たなフローに対して経路を選択し、及び既存の流れを別の経路へ移動すべきかどうか判断するために、割り当て／保持手順がフローに指定される。経路選択のための二次基準は、ネットワークにおける以前のフロー選択履歴及び全体的負荷バランスを含む。
【０１１０】
最も高いプライオリティのトラフィックは、常に、考えられる最良の経路を得る。中間ノードは、転送判断をするときにＳＴＩＤ及びＷＮＩＤのみを検査する。即ち、入り口において最初に選択されるルートは、経路に欠陥がない限り中間ノードにおいて変化がない（以下の要素（１０）の説明を参照）。
【０１１１】
プライオリティ情報（ＰＲＩＯ）は、フレームを出力ポートの正しいキューに指定するのに使用される。ボトルネックリンクの容量を公平に分配するのではなく低いプライオリティのトラフィックを別の経路に強制する目標として厳密なプライオリティキューが使用される。更に、低いプライオリティフローの間では、重み付けされた公平なキュー（ＷＦＱ）に従ってトラフィックがスケジュールされる。
【０１１２】
９）この要素は、オンデマンド動的負荷バランシング方法に関する。これらの方法は、次の１つ以上を含む。
【０１１３】
経路再選択負荷バランシングは、入口ノードのみに適用される。中間ノードは、最初に選択された経路を変更しない（欠陥の場合以外；以下の要素（１０）を参照）。初期経路選択の場合と同じ解決策が使用され、経路状態情報に基づいて、事前計算された別の経路がプライオリティリストから選択される。
【０１１４】
経路再選択負荷バランシングは、フローに基づく。完全なフローは、別の経路に再指向される。経路再選択負荷バランシングは、プライオリティにも基づく。最も高いプライオリティのフローは、先ず、最適なルーティング経路を得、２番目に最も高いプライオリティは、次に良好な利用可能なルートを得、等々となる。経路再選択負荷バランシングでは、高いプライオリティのトラフィックは、低いプライオリティのトラフィックフローを無効化し及びその先を越す（又は低いプライオリティのトラフィックフローを単に無効化する）。先を越すとは、高いプライオリティのトラフィックフローが基本的に低いプライオリティのトラフィックフローに置き換わることを意味する。これは、もちろん、ルートに著しい混雑が生じたときに起きる。さもなければ（無効化については）、最も高いプライオリティのトラフィックが最適な最高速のルートを使用したときに、低いプライオリティのトラフィックは、あまり適さない経路（より大きな遅延に直面した）に単に再指向される。
【０１１５】
逆マルチプレクシングに基づく負荷バランシング（ＩＭＬＢ）は、プライオリティの低いバルク又はベストエフォートトラフィックをパケットベース形態でバランスさせるように適用される。ＩＭＬＢは、プライオリティの低いトラフィックのみに適用される（完全な低プライオリティ（ベストエフォート）フローは、負荷バランシングにとって大き過ぎ、従って、高プライオリティのトラフィックを不必要にブロックすることがあるので）。
【０１１６】
ＩＭＬＢでは、利用可能な全経路が使用される。ＩＭＬＢは、パケットに基づく（フローではない）。各到来パケットは、最小混雑経路に向けられる。パケットは、シーケンス番号が付けられる。ドメイン出口ノードにおいて再順序付けが遂行される。
【０１１７】
１０）この要素は、欠陥に対して高速で直ちに反応し、次いで、変化状態に対して最適に適応することを保証するために異なる時間スケールで動作する種々の保護及び回復方法を含むハイアラーキー型欠陥回復システムを包含する。高速欠陥検出及びパケットごとのリンククオリティ監視が事前計算の保護経路と結合されてほぼヒットレスの保護及び回復スキームが得られる。一次アクションは、トラフィックを事前計算ルーティング経路へリルートし、そして二次アクションは、壊れたＳＴを回復することである。
【０１１８】
欠陥検出は、イベントに基づく。欠陥、例えば、ｍｍＷ無線リンク上の弱い受信信号は、欠陥ポイントからネットワーク内の全てのノードにブロードキャストされるリンク状態更新メッセージをトリガーする。このように、ノードは、どのルーティング経路が欠陥により影響を受けそしてその後のパケット転送に使用してはならないかを知る。
【０１１９】
欠陥が検出されると、図７に示すハイアラーキー型欠陥回復スキームが適用される。欠陥状態に基づいて、回復メカニズムの１つがトリガーされる。種々のメカニズムによりとられる時間スケールは、数マイクロ秒から数十秒まで変化する。
【０１２０】
図７は、通常の状態７０５を示す。リンク欠陥／悪化７１０がある場合には、ローカルリルーティング７２５（約数マイクロ秒の時間スケール７３０で）又は経路再選択７５０（約数ミリ秒の時間スケール７４０で）を遂行することができる。多数の欠陥／持続的な又は激しい悪化７４５がある場合には、ローカルＳＴリペア７７０が遂行される（数秒の時間スケール７７５で）。リンクが回復した（７５５）場合には、フローは、７５０へ進む。これは、約数秒の時間スケール７７５で生じる。持続的な多数の欠陥７８０が存在する場合には、ＭＤＳＴ再生７６０が遂行され、これは、数十秒より長い時間スケール７８５で生じる。
【０１２１】
高速ローカルリルーティング（ＦＬＲＲ）（例えば、参照番号７２５）は、別の事前計算ルーティング経路に沿って壊れたリンク上を送信されるトラフィックの再指向を含み、即ち欠陥ポイントのノードは、アドホック、バイパス経路セグメントに沿って望ましい行先に向かってパケットをリルートし始める。明確に構成されたバイパス保護は必要とされない。というのは、ルート計算が全ての必要なトポロジー情報を与えるからである。ローカルリルートは、フロー入口ノードにおける経路再選択の前に、欠陥経路における残りの輸送中パケットが失われるのを防止することを目的とする。ＦＬＲＲは、２つの別の方法、即ちＳＴ再選択(Reselect ST)、及び隣接部へのトス(Toss to Neighbor)を含む。
【０１２２】
ＳＴ再選択（ＲＳＴ）に関して、各ノードは、ＷＭＮルーティングドメインの各行先ノードに対する経路優先度を維持する。ＧＷとＷＮとの間の一次経路の優先度が集中型コントローラ（例えば、ＳＯＮモジュール２３０）により指定され及び構成される。ＷＮ間の経路優先度は、ノードそれ自体によりＳＴを経てホップカウントに従って計算される。これらの優先度は、ノードが新たなルーティング構成又はリンククオリティ変化レポートを受け取るたびに更新される。パケットの現在経路が、壊れたリンクによりブロックされた場合には、ノード上の動作リンクを経てパケット行先へ至る別のＳＴに対して経路優先度がチェックされる。１つが見つかると、そのＳＴを経てパケットがリルートされる。
【０１２３】
「隣接部へのトス（Ｔ２Ｎ）」について、パケット行先への別のＳＴがない場合、又は別のＳＴが、最適には遠く及ばない遅延、ホップカウント又は容量を伴う経路へ導く場合には、「隣接部へのトス」手順を使用することができる。次いで、事前計算経路のいずれかに必ずしも属していない動作リンクを経て、パケットをパケットのオリジナルＳＴを経て行先へルーティングできる隣接部へパケットが送信される。
【０１２４】
各壊れたリンク及び影響を受けるＳＴと行先ノードとの対のための適格なＴ２Ｎ隣接部が構成又はリンク状態変化時に各ノードにより計算される。選択ルールは、例えば、次の通りである。
ａ）Ｔ２Ｎノードとこのノードとの間のリンクは、欠陥ＳＴに属しておらず；及び
ｂ）Ｔ２Ｎノードと行先ノードとの間の経路は、このノードを含まない。
【０１２５】
ルーティングループを防止するために、パケットプライオリティ依存リルートカウンタ値がフレーム生成時にセットされる。各リルート時に、この値がデクリメントされる。この値がゼロになると、パケットがドロップする。
【０１２６】
経路再選択７５０において、プライオリティリストからの次に利用できる経路によりローカル転送テーブルに基づいて修正ルートが選択される。
【０１２７】
ローカルＳＴリペア（ＬＳＴＲ）７７０について、経路欠陥が持続するか、又はネットワークに多数の同時欠陥が存在する（例えば、参照番号７４５）場合には、ルーティング経路に対してローカル修正がなされる。ＳＴにおける壊れたリンクは、最初にＳＴに属していない動作リンクに置き換えられる。当該ノード間のシグナリングは、ルーティング構造のローカル再アレンジを生じる。各ＷＮは、ＧＷへの経路上の上流リンクの１つが切れた場合に潜在的な交換リンクに関する情報を維持する。経路選択及びＴ２Ｎ隣接部の事前計算のように、ＷＮは、ルーティングトポロジー変化の際にこの情報を更新する。各々の壊れたＳＴについて、適当な交換候補は、切断ポイントからＳＴに沿ってＷＮを上流に及び別のＷＮを下流に直接接続するリンクである。ＬＳＴＲ手順は、ＧＷに向かって切断リンクを伴うノード（開始ノードＩＮ）で開始される。ＩＮは、リンクの下流終点ノード（リペアノードＲＮ）へのリペアリンクをアクチベートするための信号を送信する。ＲＮは、新たなリンクを使用するためにその転送優先度及びルートを更新し、そして他のノードにリペアされたＳＴを通知する。
【０１２８】
図２３は、ローカルＳＴリペアのアクションを例示する。左側２３００では、ノード２０−１は、ＩＮがＲＮでもあることを示す。左側２３００では、リンク１０−１は、現在ＳＴにあるが、ノード２０−２へのリンク１０−２は、そうではない。リンク１０−１上の“Ｘ”は、リンク１０−１があるポイントで切断されることを指示し、そしてノード２０−１は、ＩＮ及びＲＮの両方として働いて、リンク１０−２をイネーブルするようにＳＴをスイッチする（参照番号３０で示す）。ＲＮ（ノード２０−１）は、新たなリンクを使用するようにその転送優先度及びルートを更新し、そしてリペアされたＳＴについて他のノードに通知する。
【０１２９】
右側では、ＩＮ（ノード２０−１）は、ＳＴをリペアするように別のノード（ノード２０−５）に求めねばならない。リンク１０−２上の“Ｘ”は、リンク１０−２（現在ＳＴの一部分）があるポイントで切断されることを指示し、そしてＩＮ（ノード２０−１）は、リンク１０−３、１０−４及びノード２０−３を経てＲＮ（ノード２０−５）へ「リペア？」メッセージ５０を送信する。ＲＮは、リンク１０−５が現在ＳＴの一部分になると、「リペアＯＫ」メッセージ６０を返送する。従って、参照番号４０で示すように、リンク１０−２は、リンク１０−５へスイッチされる。ＲＮ（ノード２０−５）は、新たなリンクを使用するようにその転送優先度及びルートを更新し、そしてリペアされたＳＴについて他のノードに通知する。
【０１３０】
最終的に、欠陥状態が長時間続く（即ち、永久的であると考えられる）場合には、全てのルーティング経路が再計算され、そして全ネットワークが再構成される。これは、ＭＤＳＴ７６０において生じる。リンクが長時間切断したままである場合には、エンドノードは、リンクが除去されたと考え、トポロジー変化レポートを集中型コントローラ（ＳＯＮモジュール２３０のような）へ送信する。１つ以上のレポートを受信した後、集中型コントローラは、その報告された欠陥リンク及びノードが省略された新たなトポロジーを使用してルートを計算する。更新された構成がノードへ送信される。
【０１３１】
保護経路への切り換えは、欠陥状態が現われる前に、リンククオリティ予想メカニズム及びスマートトラフィックエンジニアリングを使用して先験的に遂行することができる。プライオリティの高いトラフィックは、プライオリティの低いトラフィックの先を越すことができる。
【０１３２】
１１）この要素は、ネットワークドメイン内でローカル欠陥指示及びリンク状態情報を配布する方法を含む。
【０１３３】
リンク及び経路の両状態が監視され、そしてリンクの動作状態は、ワイヤレス物理的レイヤから受け取られた状態指示に基づく。周期的な「ハロー(Hello)」メッセージは、全ての隣接部への全てのリンクを経ての隣接部ＷＮへの到達性を検証するのに使用される。混雑は、主として、プライオリティ特有の出力キュー長さにより推定される。
【０１３４】
リンク状態情報は、リンク状態更新（ＬＳＵ）メッセージを使用して全ＷＭＮ内に配布される。ＷＮは、著しいリンク状態変化（即ち、リンク容量の変化を意味するリンク欠陥又は悪化）又はリンク上のトラフィック負荷の変化を検出したときにＬＳＵを送信する。ＬＳＵは、ＬＳＵメッセージで指定されるＳＴに沿って制御平面内に伝播される。各ＷＮは、受信したＬＳＵを、そのＬＳＵを受信したところの隣接部を除いて、それ自身の隣接部（即ち、ＳＴにおける親及び子）へ転送する。従って、ＬＳＵは、ＬＳＵの元々の送信者ＷＮをルーツとする（及びそれにより到達可能な）ＳＴのサブツリーに存在する全てのＷＮへ「ツリーキャスト(tree-casted)」される。
【０１３５】
各リンク状態イベントについて、ＷＮは、当該リンクを横断する全てのＳＴに沿ってＬＳＵを送信する。これは、他の全てのＷＮが多数のＳＴを通してＬＳＵを受信することを意味し、これは、負荷によるか又はＳＴ接続の切断によるか又はネットワーク内のリンク欠陥によるＬＳＵメッセージ損失に対して頑健性を与える。
【０１３６】
１２）この要素は、一方向性及び両方向性の両クライアントトラフィック（例えば、ノード又はゲートウェイのいずれかのＷＭＮシステムへ供給されるトラフィック）、並びに同じルーティング経路を通るか又は異なるルーティング経路を通る両方向トラフィックの上流及び下流方向のルートに対するサポートを与える。後者の選択肢は、負荷バランシングの良好な機会を与える。
【０１３７】
１３）この要素は、エネルギー効率の良い使用及びトランスポートリソースの最適化を可能にするエネルギー最適化モジュールを含む。
【０１３８】
例えば、エネルギー節約コントロールモジュール（ＥＣＭ）は、ＷＭＮノード及びリンクレベルにおいてエネルギー節約の世話をする。その動作は、クライアントレイヤと整合されねばならず、例えば、管理レイヤは、どのクライアントノードが潜在的なスリーパーであるか指示する。或いは又、ＥＣＭは、それ自身でこれを学習し（例えば、ノードは、ほとんどの時間アイドルであり）、そしてクライアントレイヤに対する潜在的なスリーパーを提案する。又、ＷＮは、その内部自己診断に基づき遮断を要求することもできる。
【０１３９】
潜在的なスリーピングノードが指示されたとき、それらは、全てのスパニングツリーにおいてリーフノードであるよう強制され、ＷＭＮを、進行中のトラフィックに影響を及ぼさずにスリープ状態にするのを許す。新たなトポロジー構成情報が配布され、そしてアクチベーション後に、ＷＭＮノードがスリープ状態とされる。
【０１４０】
ＥＣＭは、ウェイクアップ手順を含む。更に、リンクレベルエネルギー節約は、トポロジー最適化を考慮する。ＥＣＭは、クライアントレイヤからの情報に基づいてオプチマイザー（例えば、トポロジーオプチマイザー３２０）を案内する。又、ＥＣＭプロセスは、メンテナンスの目的でフォローされ、保護スキームをアクチベートする必要なくノードの率直な遮断を与える。
【０１４１】
スケジューリングスキームの一例がアペンディックスＡに詳細に述べられている。ルーティング及び欠陥回復スキームの一例がアペンディックスＢに詳細に述べられている。
【０１４２】
第４章．考えられる規範的実施形態及び考えられる規範的効果
１つの考えられる技術は、特定のＨＷ要求をもたない純粋なＳＷベースのものである（例えば、図１のコンピュータプログラムコード１５３及び／又は１９７を使用する）。ＳＷＭＮノードＳＷは、ＧＷノード及び通常の非ＧＷノードに対して同じである。これは、ベースステーション、サイトルーター又はワイヤレスバックホール無線装置のいずれかに存在する。バックグランドルート計算、リンクスケジューリング、トポグラフィー最適化及びエネルギー効率最適化の役割を果たす集中型エンティティ、即ちＷＭＮ集中型コントローラ（ＷＣＣ）（例えば、ＳＯＮモジュール２３０の一部分として実施される）は、ゲートウェイノードに存在するか、又はネットワークのどこかに存在する（例えば、クラウド実施）。
【０１４３】
ここに提案するルーティング及びリンクスケジューリングの実施は、リソース消費の全ての計算（スパニングツリー、ルーティングテーブル、及びリンクスケジュール）を前もって遂行できるので、極めて取るに足らないことである。更に、そのような計算は、ネットワークの外部で、例えば、専用及び集中型コンピューティングリソースにおいて遂行することができる。リアルタイムで行うべくＷＭＮノードに対して残されているのは、転送判断並びに到達性及び混雑情報の監視を行うことだけである。これは、高速リンクに対しても低コスト及び電力効率の良い実施ができねばならない。
【０１４４】
ここに述べる実施形態に適用できる非限定使用ケースの例について以下に説明する。
【０１４５】
使用ケース１．利用性の高いバックホール接続
小型セルは、大量に配備され、そしてツリー、ディジーチェーン、等の慣習的なバックホールトポロジーは、拡張可能でないか、又は運営者が希望するレベルの利用性及び信頼性を与えない。小型セルのワイヤレスバックホールに対する高い利用性及び信頼性を許すために、各ノードは、ゲートウェイへの、又はもし可能であれば、アグリゲーションノードへの少なくとも１つの別のルートを有していなければならない。換言すれば、比較的コストの掛かるプロビジョニングである１＋１又は２＋０のホットスタンバイ構成のようなリンク冗長性に焦点を当てるのではなく、利用性及び信頼性を高めるために（部分的）メッシュ接続ネットワークをレバレッジすることに焦点を当てねばならない。良く知られたように、ホットスタンバイとは、一次及び二次無線リンクが同時に動作する冗長性の方法である。多くの場合、無線部は、同じアンテナを共有する。両方のリンクに対してデータが複写され、両方が同じ情報をリアルタイムで転送するようにする。１＋１の構成では、リンクの一方がアクティブであり、そして他方がスタンバイモード（典型的にアクティブに受信するが、送信器がターンダウンされる）である。アクティブなリンクがフェイルすると、スタンバイユニットがアクチベートされる。２＋０の構成では、冗長性なしにポイントＡからポイントＢへ２つの独立した一次リンクが存在する。
【０１４６】
個々のバックホール接続に対し９９．５〜９９．９９％（パーセント）のレベルの合理的な利用性及び信頼性が要求されるが、バックホールネットワークでは、「５つの９」のような高いレベルの信頼性がしばしば必須となる（考えられるマクロオーバーレイの効果を含めて）。これらの要求は、高いプライオリティのトラフィックに対するルート多様性の保護、環境条件（天候）に対する保護、無線経路上の一時的な物体、及び装置欠陥の異なるレベルを含む。
【０１４７】
使用ケース２．低レイテンシーバックホール
レイテンシーは、将来の移動システムに対する重要なパラメータ、及び将来のバックホールネットワークに対する重要な課題の１つでもある。低い端−端レイテンシーが多数のサービスにより要求される。プライオリティの高いトラフィックに対する単一方向性の全パケットトランスポート遅延は、アクセスの固定部分、アグリゲーション及びバックボーン遅延を含めて、２０ｍｓまでと予想される。前記数値にはキュー遅延が含まれず、プライオリティの低いトラフィックは、著しく長い遅延に遭遇する。ここに提案するＬＴＥ（−Ａ）の目標は、１〜１０ｍｓである。５Ｇでは、端−端レイテンシーが、１ｍｓのレンジにおいて、更に短くなければならない。従って、最終ホップバックホールネットワーク接続にわたる数ｍｓ（ミリ秒）の範囲のレイテンシーに対する比較的厳格な要求を仮定しなければならない。個々のバックホールリンク接続は、数百μｓの最大レイテンシーをサポートしなければならない。
【０１４８】
使用ケース３．小型セルの配備
移動運営者は、自身の成長するワイヤレスネットワークの容量を拡張するため小型セルベースステーションを配備する。所与の地理的エリアに配備されるべき小型セルの数は、マクロセルの数より著しく多くなる。慣習的なマクロセルベースのネットワークプランニング及びトポロジー管理は、迅速で且つ費用効果の高い配備モデルに対する運営者の要望を扱うには不充分である。例えば、新たなノードを追加する場合には、運営者は、全てのネットワーク接続を前もって、且つエンジニアトラフィックを、負荷変動を受け容れるように手動で、事前計画する必要があり、小型セルを大量に配備することはあまり有効でもないし効率的でもない。又、多くの場合、小型セルは、ワイヤードバックホールトランスポート解決手段へのアクセスが限定された街灯柱及び電柱のような場所に配備され、ワイヤレスバックホールプロビジョニングが標準的（通常）である。配備に労力集中のワイヤレスバックホールリンク整列及び隣接部発見が必要となる場合には、非常に多数の小型セルを迅速に且つコスト効率良く配備するよう良好なビジネスケースを得ることが（不可能でない場合には）正に課題となる。小型セルが典型的にマクロセルより高い桁の大きさに達するＨｅｔＮｅｔトポロジーは、管理も複雑である。慣習的な簡単なハブ・アンド・スポーク、ツリー、又はリングトポロジーが、信頼性及び利用性の高い弾力性バックホールネットワークの必要性を満足することは困難である。運営者は、配備が容易であると共に自己最適化トポロジー管理能力でネットワーク弾力性を可能にする小型セルバックホール解決策を要求する。
【０１４９】
小型セル配備の重要な特徴は、ノード及びリンクの数が多いために、典型的なマクロセルラー配備とは逆に、アンテナの整列を含めてバックホールリンクの計画性及び最適化性が低いことが望まれることである。更に、バックホール観点から、ノードの最適配置は、非常に困難である。小型セルワイヤレスバックホールネットワークでは、最も望ましい特徴の１つは、サイトに対してバックホール要素を現場に設置した後に自律的ネットワーク確立及びシステム始動を可能にする自動リンク整列である。ノードに対する厳密なサイト位置、装置の配置、及び他のノードへの接続を事前計画する要求をある程度緩和することができる。
【０１５０】
小型セルの配備では、設置されるノードの数が著しく増加するときに、簡単且つ迅速な「ドロップ・アンド・リーブ(Drop-and-Leave)」の現場設置が要求される。新たなノードは、既存のネットワークに対する手動リンク整列及び構成を行わずに自律的に追加される必要がある。パワーアップ後に、ノードは、それらのワイヤレスリンクの範囲内で他のノードへの接続を自律的に発見及び確立し、それらを認証し、及びアドホックワイヤレスメッシュネットワークを生成することが予想される。手動構成は、ノード及びサイト識別（例えば、ＧＮＳＳ座標、ノードＩＤ）のみに限定されねばならない。ノードは、準備ができたことを設置者に指示する。指示の後に、設置者は、次のサイト位置へ移動することができる。
【０１５１】
自己配備メッシュバックホールのための重要な自動配備特徴は、次のものを含む。
○自動ワイヤレスリンク整列（例えば、手動作業なし）；
○自律的隣接部発見及び接続設定；
○ネットワークパラメータの認証及び自己構成；
○バックホールネットワークの生のトラフィックに影響しないノード挿入／削除；及び
○アドホックネットワークトポロジーの管理及び最適化。
【０１５２】
特に屋外のようなセルラー配備に小型セルを導入すると、実際の配備努力に関連した新たな課題が生じる。小型セルノードの全部ではないが、その多くは、屋上より下、典型的に、街灯柱又は電柱及び建物の側部にマウントされることが予想される。これらの位置にアクセスするには、新たな小型セルノード及びそれに関連したバックホール又はトランスポートの安全な設置及び構成を容易にするために街路及び歩行者通行路、例えば、歩道を一時的に閉鎖することをしばしば必要とする。トランスポートがワイヤレス技術を利用する場合には、小型セルノードの設置時間が著しく増加する。というのは、アクセスレイヤの無線部及びトランスポートの無線部の両方を配備しそしてその両方のアンテナを整列しなければならないからである。トランスポートレイヤ無線部のアンテナを整列するのは、大容量及び低レイテンシー接続の場合にしばしばそうであるように、特に、指向性の強いアンテナをもつ高周波無線部が使用される場合に、時間浪費である。トランスポート無線アンテナの整列に費やされる余計な時間は、アクセスレイヤの無線アンテナの場合よりしばしば顕著である。というのは、それらの整列は、クオリティの高いトランスポートリンクを保証するために厳密な正しさを得ることがしばしば重要だからである。又、トランスポート無線アンテナの整列は、整列を正しく且つできるだけ迅速に遂行するためにリンクの各端に一人づつ、２人の設置者をしばしば必要とする。この余計な努力は、運営者にとってより高い配備コストを招く。それらのコストは、ネットワークの小型セルノードの数が増加するにつれて上昇する。
【０１５３】
使用ケース４．動作中のネットワーク変化
初期の配備が確立されると、ネットワークの変化も考慮しなければならない。例えば、カバレージを拡張するか又は容量を追加するための新たなノードの追加、所与の位置におけるカバレージ又は容量需要の変化によるノードの除去、或いは故障、保守又はエネルギー節約活動によるノードの除去が含まれる。これらの形式の変化に対する再構成は、主として自動でなければならない。新たなノードは、手動での構成を行わずに既存のネットワークに自律的に追加される必要がある。従って、新たなノードを既存のネットワークに含ませるには、隣接部発見、認証、初期整列、構成、プロビジョニング及び最適化について言えば、ネットワークを最初に配備するときと同じ手順をたどらねばならない。既存のネットワークから削除又は除去すべきノードについては、削除又は除去は、計画されたイベント又は計画されないイベントのいずれでもよい。計画されたイベントは、例えば、エネルギーを保存するためにノードがスリープモードに入るとき、又はスケジュールされた保守イベントのためにノードがトポロジーから除去されるときである。計画されないイベントは、停電、リンク閉塞、又はノード作動不良、等である。
【０１５４】
使用ケース５．バックホールネットワークトポロジー最適化
自己最適化ワイヤレスメッシュバックホールモジュールを伴う小型セルは、運営者が、ＨｅｔＮｅｔ配備内に新たな小型セルを容易に追加できるようにする。新たな小型セルが設置されるたびに、最適なバックホール接続及びネットワークトポロジーは、自律的に再構成される。ネットワークトポロジー最適化メカニズムは、種々のトポロジー関連イベント、例えば、ノード挿入又は除去、一時的又は永久的リンク停止、ネットワーク混雑、ノード故障又は保守、ドメイン分割又は合併、あるノードをスリープ状態に入れるようなエネルギー節約アクション、等を取り扱う場所になければならない。
【０１５５】
小型セルネットワークが若干のノードしか有していないときには、それらを１つの単一ドメインにグループ編成しそして各ノードに対する遅延／レイテンシー最適化通信経路を構成することが容易である。益々多くの（数十の）小型セルがネットワークに追加されるときには、単一ドメインを伴うネットワークトポロジーが最適な通信経路を得ることが困難である。１つのポイントにおいて、ドメインは、各ドメインに最適なサイズを維持するために２つに分割する必要がある。比較的少数のノードを各々伴う多数のドメインが存在するあるケースでは、ドメインを合併することで、ネットワークトポロジー最適化のために高い効率を得ることができる。
【０１５６】
小型セルを迅速且つ高い費用効果で自己最適化式に配備するという運営者の期待を満足するために、本発明では、次のことが可能なワイドエリアトポロジー最適化メカニズムが必要になる。
認証を伴う自律的なノード挿入及び除去；
間に大量のトラフィックを有するノードを１つのドメインへ一緒に入れる；
遅延／レイテンシー最適化通信経路を維持；
最適なドメインサイズを自動的に維持；
最適なアクティブトポロジーの維持、隣接部到達性の維持（到達可能な各隣接部を接続する必要はない）；
多ドメインネットワークトポロジー最適化、例えば、（変化する）トラフィックニーズに基づきあるドメインから別のドメインへあるノードを移動；
バックホールネットワーク混雑トラフィック負荷バランシング及びリルート最適化；
ノード及びリンクフェイルオーバートラフィック最適化；
オファーされた負荷ニーズを満足させるバックホール容量割り当てを最適化するネットワーク負荷適応；
計画されたイベント（例えば、ノードの保守、エネルギー節約スリープモード、等）のための予防的ネットワークトポロジー適応；及び／又は
停電、天候等の環境ファクタによるネットワーク停電回復。
【０１５７】
使用ケース６．トラフィック操向及び負荷最適化
小型セルネットワークにおいて、トラフィック又は与えられる負荷は、イベント駆動式に変動する。例えば、ラッシュアワー中に、オフィスビルディング内へ及びオフィスビルディング外へ移動する。図８は、１つの小型セルノード（ｅＮＢ）が午前中に高いトラフィックピークレートを経験するが、他のノードは、午後に高いトラフィックピークレートを経験するような動的なルート最適化能力の一例を示す。バックホールネットワークは、リンク負荷を適切にバランスさせるためにトラフィックを適宜に移動できねばならない。
【０１５８】
図８に示すように、参照番号８３０は、ノード２８０−１（例えば、マクロｅＮＢ）と２つのノード２８０−２及び２８０−３（各々小型セルｅＮＢ）との間の通常のトラフィックフローを示す。参照番号８２０−１は、リンク（例えば、バックホールリンク）を示し、そして矢印のサイズは、フローの量を示す。通常のトラフィックフロー８３０は、ノード２８０−２へのリンク８２０−２（例えば、バックホールリンク）と、ノード２８０−３へのリンク８２０−３（例えば、別のバックホールリンク）との間で均一に分割される。トラフィックピークレート８１０も示されており、これは、午前中のトラフィックピークレート８１０−１及び午後のトラフィックピークレート８１０−２を示す。明らかなように、ビジーｅＮＢは、午前中のトラフィックピークレート８１０−１に対するノード２８０−２のｅＮＢであり（参照番号８４０を参照）、そしてリンク８２０−３を経てマクロノード２８０−１から小型セルノード２８０−３へ送信されるトラフィックフローに比して、より多くのトラフィックフローがリンク８２０−２を経てマクロノード２８０−１から小型セルノード２８０−２へ送信される。又、小型セルノード２８０−３（ピークトラフィックレートが低い）から小型セルノード２８０−２のビジーｅＮＢに向かって別のリンク８２０−４があることにも注意されたい。対照的に、ビジーｅＮＢは、午後のトラフィックピークレート８１０−２に対するノード２８０−３のｅＮＢであり（参照番号８５０を参照）、そしてリンク８２０−２を経てマクロノード２８０−１から小型セルノード２８０−２へ送信されるトラフィックフローに比して、より多くのトラフィックフローがリンク８２０−３を経てマクロノード２８０−１から小型セルノード２８０−３へ送信される。この状態におけるリンク８２０−４は、小型セルノード２８０−２（ピークトラフィックレートが低い）から、小型セルノード２８０−３のビジーｅＮＢに向かう。この例は、ダウンリンクがトラフィックピークレートの一次ドライバであることを仮定しているが、アップリンクにも同様の技術を適用できることに注意されたい。
【０１５９】
要求されるダイナミズムの別の例は、トラフィックのアドホック変化を含む。例えば、スポーツゲーム中に、スポーツ競技場内にトラフィックが集中する。しかしながら、ゲームが終了すると、トラフィックの大半は、酒場や、駐車場や、公共交通、等へ移動する。バックホールを含む小型セルネットワークは、これらの変化に経済的に対抗できることが必要である。
【０１６０】
１日の時刻及びイベント駆動の動的ルート最適化例では、小型セルバックホールネットワークのための幾つかの重要なシステムレベル要件が、本発明により、次のようにリストされる：
【０１６１】
小型セルバックホールネットワークは、トラフィックリルート及び負荷バランシングアルゴリズムでトラフィック変動に動的に対抗するように設計されねばならず；
【０１６２】
ネットワーク内のみ使用のトランスポート容量は、経時変化トラフィックニーズに従ってノード間でネットワークの合計スループット容量を動的に分担することにより使用のために解放され；
【０１６３】
単一ネットワークドメインの合計スループットは、例えば、リンク負荷状態及びクライアントトラフィックプロフィールに基づいて最適化され；
【０１６４】
混雑し及び悪化したリンクは、１つ以上の別の経路でバイパスされねばならず；及び
【０１６５】
全ての経路が混雑したときの最終的ケースでは、ネットワークは、バックホールに入るトラフィックを一時的に減少するために小型セルノード及びサーバーゲートウェイに通知することができる。
【０１６６】
使用ケース７．停電及び悪化についての保護
接続が得られない時間は、停電であり、ここでの重要なメトリックは、停電と停電との間の平均時間、及び平均停電時間である。停電は、装置又は電源の故障、或いはワイヤレスリンクに対する障害物、例えば、激しい雨、木又は乗物により引き起こされる。小型セルバックホールに関連した停電の別の潜在的原因は、バックホールユニットの小さな移動がワイヤレス解決手段の高利得アンテナの不整列を引き起こす「柱の揺れ(pole sway)」である。弾力性は、停電から迅速に回復し又はそれらを完全に回避するための接続の能力である。その技術は、バッテリバックアップ、装置の冗長性、又は多数のルーティングオプションを伴うトポロジーを含む。そのような技術を実施することは、一般的に、コストを高め、従って、高い利用性と低いコストとの間でバランスをとらねばならない。小型セルトランスポートネットワークニーズは、種々のネットワーク要素の故障及びノード間のリンクの悪化に対して頑健でなければならない。
【０１６７】
小型セルは、ノード又はノードに接続されたリンク内に内蔵される冗長性のある高コストのマクロセルと対になるように設計されない。代替経路を伴うネットワークトポロジーは、故障に対する高い弾力性を達成するための方法である。小型セルの初期配備中には、ポイント対マルチポイント、ディジーチェーン又はツリーのような簡単なトポロジーであって、ノード又はリンクの故障中にトラフィックをリルートするための代替経路をもたないものが良い。より多くの小型セルが配備された後、運営者が自身の配備したネットワークに対してより多くの保護及び弾力性を要求するときには、本発明により、ネットワークトポロジーがリング及びメッシュのような代替経路をもつものへと進化することが期待される。
【０１６８】
ワイヤレストランスポートは、小型セルトランスポートレイヤに対して使用されることが期待される。高い周波数の無線部は、おそらく、高い周波数ではより多くのスペクトルが利用できることにより高い容量が与えられるために使用される。環境ファクタによる潜在的なＲＦリンク悪化又は停電は、それら周波数における問題である。それらの悪化は、例えば、激しい雨や雪による停電を引き起こす可変の及び潜在的に高い減衰、時間と共に木が成長するように現われそして街路（例えば、電柱）レベルでＲＦリンクに障害を及ぼし始める観葉植物の存在、並びにＲＦリンクが確立された場合に建物及び他の物体からの反射に依存する構造物の反射及び吸収ロスを含む。又、エリア内の他のワイヤレスリンクからのＲＦ干渉によってもリンク悪化が生じる。
【０１６９】
運営者は、ワイヤレスリンクが悪化したがまだ完全な停電になっていない場合にリルート及び負荷バランシングの使用を要求すると予想される。例えば、リンクの利用可能容量は、一時的な激しい雨による減衰で制限されることがある。これは、トランスポートレイヤに混雑を引き起こし、そしておそらく、トラフィック配送のレイテンシーを高める。このケースでは、そのような状態が検出され、そして悪化したリンクを通してある程度のトラフィックを維持しつつ、トラフィックの一部分をリルートできねばならない。どれほど多くのトラフィックをリルートすべきか及びどのトラフィックをリルートすべきかの判断は、種々のトラフィックプライオリティ又はＱｏＳ分類に依存する。リルート及び負荷バランシングメカニズムの組み合せは、これらのケースを取り扱う。
【０１７０】
典型的なセル半径が数百メーター以下程度に過ぎない小型セル配備では、大規模な天候事象により多数のリンクが影響を受ける。単一リンクでは前記と同じメカニズムが適用されるが、同じ経路への多数のリンクに対して全てのトラフィックをルーティングして混雑を生じることがないように負荷バランシングのための追加の考慮が要求される。
【０１７１】
性能低下を引き起こす環境的な要因がなくても複雑なメッシュトポロジーにおいて特定のノードに充分なトラフィックが通過するときにはリルート又は負荷バランシングのための１つの最終的な使用ケースが生じる。メッシュ構造は、メッシュの単一ノード又はブランチが混雑状態になることがないよう保証するためにトラフィックの入念な負荷バランシングを必要とする。
【０１７２】
使用ケース８．エネルギー節約使用ケース
運営者にとっての典型的な重要なコストは、エネルギー費用である。トラフィックの成長に関わらず合計エネルギー消費を平坦化することが重要である。エネルギー費用をカットすることは、運転コストを含むだけでなく、社会的責任も含む。
【０１７３】
ＳＯＮに対する３ＧＰＰ  ＴＲ  ３６．９０２は、次のようなエネルギー節約（ＥＳ）使用ケースを有する：
【０１７４】
ネットワークにより提供される容量が任意の時間点における必要なトラフィック需要にできるだけ厳密に一致する場合にはエネルギー費用のカットを実現でき（３ＧＰＰ  ＴＲ３６．９０２）；及び
【０１７５】
エネルギー節約を通しての運営費用のカット（３ＧＰＰ  ＴＲ３６．９０２）。
【０１７６】
小型セルは、低電力低コストの無線ベースステーションであり、その一次設計目的は、付加的な容量注入及び優れたセルラーカバレージを与えることである。しかしながら、チェックしないままであると、大規模の小型セル配備は、ネットワークのエネルギー消費を実質的に増大し、著しい環境的及び経済的影響を伴う。
【０１７７】
小型セル及びワイヤレスバックホールは、両方とも、著しい電力を消費するので、本発明では、全小型セルクラスターに対するエネルギー消費について全体論的及び革新的見解をもつ必要がある。ネットワークは、どのノード及びリンクをスリープさせるか、ウェイクアップさせるか、小型セルトポロジーを最適化するか、及びそれに応じてトラフィックをルーティング及びスケジューリングさせるか、インテリジェントに判断する必要がある。又、ノードは、低いスループットをサポートする低い変調及びコードレートをもち且つ低い送信電力しか要求しない低エネルギー消費モードにすることもでき、そして基本帯域処理が減少されてもよい。このケースでは、低いアクセストラフィックが予想され、そして他のトラフィックは、低エネルギー消費モードで動作するノードから離れるように操向されねばならない。
【０１７８】
第５章．考えられる商業的影響、利益及び技術的効果
ここに述べる規範的ＳＷＭＮ実施形態は、多様な自己最適化特徴、柔軟なＱｏＳ（サービスクオリティ）、混雑制御及び管理、広範な負荷バランシング、及びトラフィック管理特徴を提供することができる。これらのメカニズムは、メッシュネットワーク内でトラフィックフローの高度に柔軟な制御及び操向を許し、従って、所与の時間におけるトラフィックの自動ＱｏＳ認識最適化を可能にし、メッシュネットワークの全トランスポート容量を最適に利用できるようになる。ここに述べる規範的実施形態に対する運営者の幾つかの利益、ひいては、高い商業的価値は、次の１つ以上を含む。
【０１７９】
１）ＳＷＭＮは、ワイヤレストランスポートネットワークに通常関連する詳細なリンク構成作業の量を減少することができる。
【０１８０】
２）ＳＷＭＮは、ファイバアクセスが利用できない各ノードに対してより多くのマウント位置を使用する柔軟性を可能にする。
【０１８１】
３）ＳＷＭＮは、５Ｇ小型セルに対してワイヤレストランスポートレイヤを自律的に配備しそしてノード間の接続を最適化することを経て配備スタッフによる最適化努力を減少する。
【０１８２】
４）ネットワークトポロジーは、既存のトラフィック、例えば、追加された新たなノード、除去されるか又はエネルギー節約状態にされた既存のノードに影響を及ぼすことなく変更することができる。これは重要である。というのは、小型セルネットワークが、典型的に、ホットスポットからスタートして、トラフィックの増加に従ってセル密度をゆっくり増加することにより、有機的に成長するからである。
【０１８３】
５）ＳＷＭＮは、トラフィックフローの混雑及び欠陥状態がＱｏＳ、ネットワーク負荷及び環境条件に基づいて再構成されるリアルタイムネットワーク最適化を可能にする。
【０１８４】
アペンディックスＡ：スケジューリングスキームの一例
本章は、ＳＷＭＮスケジューラの一例に関する。ＳＷＭＮスケジューラの考え方を例示するために、図９に示す８×８ＳＷＭＮの例について考える。ノード１８、３１及び５３は、ゲートウェイ（ＧＷ）ノードとして働き、そしてＧＷリンク（ＧＷノードの周りの大きなライン、例えば、ＧＷノード３１については２３から３１、３１から３９、３１から３２、及び３１から３０；ＧＷノード１８については１０から１８、１８から２６、１８から１９、及び１７から１８；及びＧＷノード５３については４５から５３、５３から６１、５４から５４、及び５２から５３）は、スケジューリングのための最も重要なリンクであるとする。
【０１８５】
各ノードは、最適なＧＷへの独特の一次経路を有する。図９からの８×８グリッドＳＷＭＮにおける一次経路を示す図１０を参照されたい。ＧＷノード１８で終る一次経路は、図９に黒い線で示され、そして次のホップ：１から９、９から１７、１７から１８、１７から２５、２５から３３、４２から３４、３４から３５、３４から２６、２６から２７、２６から１８、１８から１０、１０から１１、１０から２、２から３、１８から１９、１９から２０、２０から２１、２０から１２、及び１２から４を含む。一次経路は、一次スパニングツリーにより決定される。図１０の黒い線の構造体は、スパニングツリーではなく、むしろ、それは、ＧＷノード１８から生じる４つの異なるスパニングツリーの断片から形成される。少なくとも１つの一次経路を搬送するリンク（より黒い、太い線）は、何も搬送しない線より重要である。
【０１８６】
参照番号１０１０で示すように、ノード５は、最も近いＧＷまで５ホップ離れている。即ち、ノード１８においてＧＷまでホップ５−１３、１３−２１、２１−２０、２０−１９及び１９−１８；ノード３１においてＧＷまでホップ５−６、６−７、７−１５、１５−２３及び２３−３１。又、（短い構造体を使用する）５ホップをもつ更に２つの経路があることにも注意されたい：即ち、ノード５から、ノード１３、２１、２９、３０を通して、ノード３１まで；及びノード５から、ノード４、３、２、１０を通して、ノード１８まで。参照番号１０２０で示すように、ノード５７は、最も近いＧＷ、ノード５３まで５ホップ離れており：即ち、ノード５７から、ノード５８、５９、６０、６１を通して、ノード５３まで；及びノード５７から、ノード４９、５０、５１、５２を通して、ノード５３まで。
【０１８７】
この例では、６４個のノードがあり、そのうちの３つは、ＧＷであり、従って、６１個の一次経路がある。一次経路のセットは、全ての経路の小さなサブセットを形成する。これらの経路は、図１１に示す種々の長さ（ホップで測定された）を有する。参照番号１１１０は、ノード５から最も近いＧＷ（１８又は３１）まで５ホップ離れていることを示している。
【０１８８】
このネットワークグラフは、１１２個のリンクを有する。これらのリンクは、それらが搬送する一次経路の数に従って重みが与えられる。高い重みをもつリンクは、重要度が高い。これらのリンクは、重みに従う順序で常に取り扱われる。図１２は、リンク重みの分布を示す。最初の６７個のリンクは、少なくとも１つの一次経路を搬送し、そして残りの４５個のリンクは、一次経路を搬送しない（６７＋４５＝１１２）。
【０１８９】
ＧｒｅｅｄｙＴｗｉｃｅ［］方法（上述した）を実行して、この例の８×８グリッドの小型セルネットワークに対して５つの送信セットを仕組む。
Ｔ1＝ＧｒｅｅｄｙＴｗｉｃｅ［Φ］；
Ｔ2＝ＧｒｅｅｄｙＴｗｉｃｅ［Ｔ1］、Ｔ1におけるリンクの回避を試みる；
Ｔ3＝ＧｒｅｅｄｙＴｗｉｃｅ［Ｔ1∪Ｔ2］；及び
このプロセスは、追加の送信セットを通して続けられる。特に、このプロセスは、Ｔ1∪Ｔ2∪Ｔ3・・・が各リンクを含むときに終了となり、そしてこの例では、Ｔ5において終了となる。
【０１９０】
これらの送信セットは、できるだけバラバラであり、そしてそれらの連合は、全グラフであり、これは、それらがスケジューリングサイクルに対して良好な構築ブロックを形成することを意味する。図１３は、調整された送信セット：３１個のリンクを有するＴ1 １３１３−１；３０個のリンクを有するＴ2 １３１０−２；３０個のリンクを有するＴ3 １３１０−３；２９個のリンクを有するＴ4 １３１０−４；３０個のリンクを有するＴ5 １３１０−５；全てのリンクを有するＴ6 １３１０−６の可視化を示す。対応する送信セットを作り上げるリンクは、黒い線である。全てのリンクを有する送信セットＴ6 １３１０−６は、全て黒い線でマークされることに注意されたい。
【０１９１】
ここで、調整された送信セットからスケジュールサイクルにどのように到達するかの一例を示す。図１４に示すマトリクスのａijエントリは、Ｔi及びＴjの両方に共通なリンクの数を含む。送信セットＴ1、Ｔ2、Ｔ3及びＴ4は、ほとんどバラバラであり、一方、Ｔ5は、２３個の共通のリンクを有するという意味でＴ1と同様である。
【０１９２】
この規範的な８×８グリッドの小型セルネットワークでは、８個の送信セットのスケジュールサイクル（ＧＷの最大度数の２倍）が必要であると決定された。従って、ここで、別の３つの送信セットを仕組むことが必要となる。例えば、Ｔ6、Ｔ7及びＴ8は、次のように仕組まれる。
Ｔ6＝ＧｒｅｅｄｙＴｗｉｃｅ［Ｔ1∩Ｔ5∪Ｚ］
Ｔ7＝ＧｒｅｅｄｙＴｗｉｃｅ［(Ｔ1∩Ｔ5)∪(Ｔ1∩Ｔ6)∪(Ｔ2∩Ｔ5)∪(Ｔ2∩Ｔ6) ∪Ｚ］
Ｔ8＝ＧｒｅｅｄｙＴｗｉｃｅ［Ｕ3i=1Ｕ3i=1(Ｔ1∩Ｔ4+i)∪Ｚ］
【０１９３】
Ｚは、重みがゼロのリンクのセットである。最終的に、この規範的な８×８小型セルグリッドネットワークの各ノードに対する最適なＥ２Ｅ遅延を生成できるスケジューリングサイクルにおける順序を決定するためにそれら８個の全送信セットをシャフルすることにより簡単な徹底的なサーチが行われる。
【０１９４】
アペンディックスＢ．ルーティング及び失敗回復スキームの例
このアペンディックスは、ルーティングスキームのための付加的な情報を含み、そして参照を容易にするために多数の章に分割される。
【０１９５】
多数のバラバラのスパニングツリーに基づくルーティングに関しては、先ず、ＷＭＮシステムアーキテクチャーについて述べ、そして小型セルのラストマイルバックホーリングの文脈においてＷＭＮのためのルーティング要件を検討する。次いで、考えられる多数のバラバラのスパニングツリー（ＭＤＳＴ）ルート計算アルゴリズムを特定する。
【０１９６】
Ａ．小型セルバックホールにおけるＷＭＮルーティング
図１５を参照すれば、この図は、ゲートウェイノード（ＧＷ）２８０−１及び２８０−２を経て固定ネットワーク２２５に接続されたＷＭＮルーティングドメイン１５２０を含むＷＭＮシステムアーキテクチャーの一例を示し、ここで、小型セル２８０−３ないし２８０−１１は、通常、マクロセルサイトのＷＭＮノード（ＷＮ）及びＧＷと同じ位置にある。ノード２８０は、ｅＮＢ２２０であると考えられることに注意されたい。ＧＷノード２８０−１及び２８０−２は、リンク２１６−１及び２１６−２を経てネットワークノード１５１５−１及び１５１５−２（例えば、ＳＧＷ）に接続される。ネットワークノード１５１５は、固定ネットワーク１５２５（例えば、コアネットワーク）に接続される。又、ＷＣＣ１５１０は、固定ネットワーク１５２５内にあるか又はそこに接続される。ＷＣＣ１５１０の実施に関しては、これは、図１のＳＯＮモジュール２１０として実施することができる。
【０１９７】
通常のＷＭＮノード（ＷＮ）は、ポイント対ポイントｍｍＷリンク２９０を経て互いに接続され、そして最良のリンクのみが通信に使用されるので、トポロジーは、やや低いノード度数をもつ部分メッシュに限定される。この例では、ＷＣＣ１５１０は、経路計算、リンクスケジューリング及びＷＭＮトポロジー管理を行う。ＷＣＣ１５１０は、固定ネットワーク１５２５のどこか深部に存在するか、或いはＷＣＣ１５１０は、ＧＷ２８０−１又は２８０−２の一方と同じ位置とされる。
【０１９８】
上述したように、小型セルバックホールのケースでは、単一のＷＭＮドメインにおけるノードの最大数は、おそらく、数十程度であり、従って、限定された拡張性しか必要とされない。このため、例えば、故障に対して高速反応を可能にするが、同時に、拡張性を数百ノードに限定できる設計選択を行うことができる。この限定は、このケースでは重大な欠点とは考えられない。というのは、単一のＧＷの容量は、限定された数の小型セルしかサポートできず、大きなマルチＧＷ  ＷＭＮは、ドメイン当たり数個のＧＷしかない小さなドメインに分割できるからである。この目的で特定のＷＭＮトポロジー管理アルゴリズムが使用される。これらアルゴリズムの説明は、本書の範囲外である。
【０１９９】
ＧＷリンクの利用は、ＷＭＮ性能の決定ファクタの１つである。ほとんどのトラフィックは、ＧＷ２８０−１及び２８０−２を経てＷＭＮへ流れ込み又はＷＭＮから流れ出るので、ＧＷリンクスループットを最大にするように試みる必要がある。更に、ＧＷリンク（ＧＷ２８０−１、２８０−２に接続するリンク２９０）は、おそらく混雑のための位置であり、従って、負荷バランシング及び他の混雑軽減方法は、ＧＷリンクから別のところへトラフィックを移動できねばならない。それ故、本発明では、ＧＷリンク特有のスパニングツリー（ＳＴ）に基づくルーティングメカニズムを使用することを決定した。そのような各ＳＴは、ＧＷをルーツとし、そしてルートは、常に、１つの子だけであり、これは、ＧＷに隣接するＷＮの１つである。このように、混雑したＧＷリンクからの移動するトラフィックは、トラフィックを別のＳＴに割り当てるだけであることを意味する。更に、それらのＳＴが充分にバラバラである場合には、それらは、最大数のバラバラの経路をＷＮのためのＧＷに与えねばならない。
【０２００】
５Ｇ小型セルバックホールにおける最も重要な性能メトリックの１つは、往復遅延であり、これは、ルートに依存するだけでなく、リンクスケジュールにも大きく依存する。この問題に対する１つの解決策は、ルーティングタスク及びリンクスケジューリングタスクを分離し、そして一次経路と称される経路のあるセットのみに対してエッジ対エッジ遅延を最適化することによりリンクスケジューリングタスクを容易にすることである。これら一次経路は、ＭＤＳＴ計算から生じる最良の経路であり、それらは、リンクスケジュール最適化手順への入力として与えられる。リンクスケジューリングアルゴリズムの説明は、本書の範囲外である。
【０２０１】
Ｂ．ＭＤＳＴ計算
ここでは、集中型計算を使用することによってバラバラのスパニングツリーを生成する方法の一例を提示する。本発明のケースでは、リンクスケジュールが集中型要素（ＷＣＣ）により計算されるので、分散型ルート計算の使用は、ほとんど意味をなさない。しかしながら、ここに例示するアルゴリズムを分散型形態へ変換することは些細なことであり、従って、そのような変換の説明は、ここでは省略する。集中型ＭＤＳＴルート計算アルゴリズムの主たる手順が図１６に示されている。この図は、規範的方法の動作、コンピュータ読み取り可能なメモリで実施されるコンピュータプログラムインストラクションの実行結果、ハードウェアで実施されるロジックにより遂行される機能、及び／又は幾つかの規範的実施形態に従って機能を遂行するための相互接続された手段を示している。このフローは、ＷＣＣ１５１０により、例えば、ＳＯＮノード２１０のＳＯＮモジュール２３０−２を使用して遂行されることに注意されたい。
【０２０２】
与えられたネットワークトポロジー１６１０を使用し、そして１つのゲートウェイに対してＳＴごとにステムを生成することにより、ＭＤＳＴ計算がスタートされる（ブロック１６１５）。ステムとは、他のステムとでノード（全ＳＴにより共有される根を除いて）又はリンクを共有しないＳＴの一部分である。無向グラフＧのスパニングツリーＴは、Ｇの全頂点を含むツリーであるサブグラフである。他の根ノードを除くネットワークの全てのノードは、あるステムに属していなければならない。ステムをホップごとに並列に同時に成長させることにより、ＭＤＳＴ計算の最終結果が、バラバラの経路を与えるＳＴを含むことを保証することができる。
【０２０３】
ステム成長ステップ１６２０は、ＧＷリンクごとにＳＴを生成し、そしてＳＴ計算アルゴリズムの重要な要素であるヒープを初期化（ステップ１６２０）することによりスタートされる。初期化アルゴリズム（ＧＥＮＳＴＥＭＳ()）は、図１７に示されている。ここで、ＳＴに対するデータ構造（図１７の７行目のｍｄｓｔ）及びｈｅａｐｉｔｅｍを有すると仮定する。各ｈｅａｐｉｔｅｍは、ヒープアイテムが処理されるときに必要になる３つのパラメータｉｄ、ｐａｒｅｎｔ及びｔｒｅｅを有する。
【０２０４】
初期化の後に、実際のステム成長を実行するためにＧＲＯＷ()手順が呼び出される（図１６のブロック１６２５を参照）。ＧＲＯＷ手順は、図１８に示されている。ヒープからのトップアイテムは、ヒープが空になるまで１つ１つ処理される。各アイテムに対して、ノードが依然割り当てられていないかどうかチェックされ、もしそうであれば、ノードは、ｈｅａｐｉｔｅｍにより指示された親の子としてＳＴに追加される。最終的に、新たなノードがリーフノードだけでなければならない（ｃｏｎｔｉｎｕｅ()によりチェックされる）ことを考えない限り、新たなツリーメンバーの割り当てられていない隣接部がヒープに追加される。このアルゴリズムの知能は、ｈｅａｐｉｔｅｍクラスのための適当な比較方法を有することにあり、例えば、根ノードへのホップカウント又は経路コストは、一次比較キーとして、及びツリーの濃度は、二次比較キーとして使用することができる。これは、例えば、ホップカウントが使用される場合に、ノードは、最短経路ホップカウントの順序でステムに追加されることを意味する。
【０２０５】
図１９は、図１８のＧＲＯＷ手順を使用して、１つのＧＷ８２０−６をもつノード８２０の５×４正規グリッドネットワークに対して生成されたステムの例である。４つのステム１９１０−１、１９１０−２、１９１０−３及び１９１０−４が存在する。
【０２０６】
最終的なステップとして、各ステムは、同じＧＲＯＷ()手順を使用することにより完全ＳＴへと成長する。これは、ステムの隣接ボードでヒープ構造を初期化することにより行われる（図２０に示すＧＥＮＴＲＥＥ()手順）。５×４正規グリッドネットワークに対するＧＥＮＴＲＥＥ()手順の結果が図２１に示されている。スパニングツリー２１１０−１、２１１０−２、２１１０−３及び２１１０−４は、ＧＥＮＴＲＥＥ()手順から得られたもので、各々、ステム１９１０−１、１９１０−２、１９１０−３及び１９１０−４に対応する。ゲートウェイ８２０−６からノード８２０−２０へ進むために、スパニングツリー２１１０−１及び２１１０−３に対してそれらの間に５つのホップがあり、そしてスパニングツリー２１１０−２及び２１１０−４に対してそれらの間に７つのホップがある。その結果、スパニングツリー２１１０−１又は２１１０−３の１つがノード８２０−２０の一次経路として選択され、そして他の３つのスパニングツリーがノード８２０−２０のバックアップ経路として選択される。タイの場合には一次経路を選択するために多数の可能性がある。例えば、次のような各々別々又は結合が可能である。
１．ノードの重みを使用：最も高い重みをもつノードが選択され、そしてノードの重みは、例えば、デフォールトでもよいし、トラフィック統計データで決定されてもよい；
２．予想されるトラフィック需要がＳＴ間でできるだけ等しく分担され；及び
３．ステットソン・ハリソン法（即ち、ランダム指定による）。
【０２０７】
ＳＴ間のトラフィック需要をバランスさせる努力の裏にある原理は、小型セルバックホールシステムにおいて、ＷＭＮのトラフィックのほとんどがＧＷノードを通して進むという仮定に基づく。そのようなケースでは、ＧＷリンクは、おそらく、トラフィック混雑の位置であり、従って、それらの間にトラフィックを分散させるよう試みるのが有意義である。各ＧＷリンクは、１つのＳＴにしか属さないので、ＳＴ間でトラフィックのバランスをとることにより拡散を容易に行うことができる。
【０２０８】
ＧＥＮＴＲＥＥ()を使用する実行において、ホップカウントが一次分類キーとして使用され、そして二次キーは、ＧＷリンクにおけるトラフィック負荷の推定であった。推定については、トラフィックフローが最短の経路を通して進行し、そして各ＷＮは、同じ需要を生じると仮定する。トラフィック負荷を二次キーとして使用することは、軽い負荷推定をもつステムを、そうでないものより大きく成長させる。しかしながら、ほとんどのケースでは、最終的なＭＤＳＴ構造に対する影響が必ずしも顕著でない。
【０２０９】
ＧＲＯＷ()手順は、グローバルな見解なしに動作するので、特に、ＧＥＮＴＲＥＥ()から呼び出されたときには発散し過ぎることがある。従って、それにより生じるツリーは、主として、根ノードから最も離れた部分に幾つかのあまり適していない経路を含むことになる。これは、より良好な親が利用できればそれにリーフノードを移動する簡単な最適化手順ＴＡＩＬＯＰＴ()（図２２を参照）で固定される。
【０２１０】
Ｃ．一次経路割り当て
ルート計算の最終段階は、好ましいＧＷ及びそのＧＷへのルートがノードごとに指定される一次経路割り当てである。これは、２つのステップで行われる。第１に、１つのＧＷへの明らかに最良の経路を１つだけ有するノードがそれらの経路及びＧＷに割り当てられる。実際に、経路の割り当ては、ノードごとに一次ＳＴを定義することにより行われる。第２に、２つ以上の等コスト経路を有するノードが割り当てられ、予想されるトラフィック需要がＳＴ間にできるだけ等しく分割されるようにする。各ノードのデフォールト値、又はトラフィック統計データにより決定された値を使用することができる。
【０２１１】
ＳＴ間のトラフィック需要をバランスさせる努力の背後にある原理は、小型セルバックホールシステムにおいて、ＷＭＮのトラフィックのほとんどがＧＷノードを通して進むという仮定に基づく。そのようなケースでは、ＧＷリンクは、おそらく、トラフィック混雑の位置であり、従って、それらの間にトラフィックを分散させるよう試みるのが有意義である。各ＧＷリンクは、１つのＳＴにしか属さないので、ＳＴ間でトラフィックのバランスをとることにより拡散を容易に行うことができる。又、これは、アクティブな負荷バランシングを極めて容易にし、即ちトラフィックを１つの混雑したＳＴから別のものへ移動することで、ＧＷリンク混雑を自動的に緩和させねばならない。
【０２１２】
アペンディックスＣ．付加的な例及びコメント
要素の事前計算に関して、ＳＴ及びリンクスケジュールは、ＷＣＣによりドメインごとに事前計算されるが、それらは、ネットワークがアクティブであるときに再計算することができる。トポロジーに対して計算されたルート及びスケジュール情報は、その情報が判断実行に使用される前にこのドメインにおいて全てのノードに配布され、即ちノードは、この事前に計算された（例えば、半静的な）情報、及びリンク状態（例えば、「ＯＫ」、「混雑」、「切断」）に関する収集した（例えば、動的な）状態情報を使用して、転送、保護及び負荷バランシングアクションをローカルで実行する。
【０２１３】
トポロジーが変化するとき、例えば、新たなノードが配備又は除去されるか或いは１つのリンクが長期間切断するときは（前記マルチレベル保護スキームの最終段階を参照）、ＷＣＣは、その新たに変化したトポロジーに対するルーティング経路及びリンクスケジュールを再計算する。このとき、トラフィックは、古いルート及びスケジュール情報を使用して古いトポロジーに依然ある。例えば、ＷＣＣにより指令される所与の時間に、全てのノードは、古いルート及びスケジュールから同期状態で移動して、その新たなトポロジーに対して今や最適化された新たなルート及びスケジュールを使用する。
【０２１４】
従って、事前計算とは、ルートオプションが、リルート判断実行に使用される前に計算されることを意味し、即ちルートオプションは、転送／リルート／負荷バランシングの判断がいずれかのノードで遂行されるときに既に利用できる。
【０２１５】
ルート計算のための「トラフィック統計データ」では、例えば、ネットワーク運営者が長期間にわたり収集する所与のエリアにおいてトラフィックの振舞い（及び／又はトラフィックのプロフィール）に関する長期間の統計データのような幾つかの一般的情報が存在することを意味する。例えば、あるホットスポットエリア、例えば、都市ブロックは、ラッシュアワー時又は少なくとも他のエリア等において激しいトラフィックに直面する。例えば、図８を参照されたい。この（例えば、歴史的な）情報は、ルート及び／又はリンク計算を案内するためにシステムに供給される。原理的に、この情報は、ＮＭＳによる動作中に更新され、そしてＷＣＣにより、少なくともあるレベルで、収集される。
【０２１６】
この種のトラフィック統計データは、全てのノードが等しくそして同じプライオリティ及び重みを有するというデフォールトより良好な初期ルート及びスケジュールのセットを与えることができる。
【０２１７】
動的な即座のトラフィック情報は、ローカル転送及び負荷バランシング判断を遂行するときだけノードにより使用される。ノードは、入口リンクにおける到来データ、及びそれらの入口リンクの各々においてどれほどの容量が既に使用されているかを監視し、そしてそれに基づいて転送判断を実行し：即ち一次経路が動作し、充分な容量があり且つ混雑していない場合には、一次ルーティング経路が使用される。さもなければ、二次バックアップルーティング経路が選択され、等々となる。（全ての経路は、一次経路選択中にルート計算プロセスにおいてプライオリティ順にされることを想起されたい。）
【０２１８】
図２４は、小型セルバックホールに対する自己編成ネットワーク概念を遂行するための論理フロー図である。図２４は、更に、規範的方法の動作、コンピュータ読み取り可能なメモリで実施されるコンピュータプログラムインストラクションの実行結果、ハードウェアで実施されるロジックにより遂行される機能、及び／又は規範的実施形態により機能を遂行するための相互接続された手段を示している。図２４は、典型的に、ｅＮＢ２２０のようなノードによって遂行されるが、分散されたＷＣＣにより（例えば、図１のｅＮＢ２２０におけるＳＯＮモジュール２３０−１として）遂行されてもよい。参照し易くするため、図２４のブロックは、ネットワークノードにより遂行されると仮定する。以下の例において、図２４のフローは、例１と称されることに注意されたい。
【０２１９】
ブロック２４１０において、ノードは、次のことを遂行する：即ち、リンクを通して相互接続される多数のノードの１つ以上のドメインを含むメッシュネットワークにおいて、選択されたドメインには、その選択されたドメインを別のネットワークに接続する少なくとも１つのゲートウェイがあり、１つ以上のドメイン、それらの多数のノード及びそれらのリンクは、トポロジーの一部分であり、少なくとも１つのゲートウェイのうちの選択されたゲートウェイに対する一次及びバックアップルーティング経路のセットにアクセスし、その選択されたゲートウェイに対する各一次及びバックアップルーティング経路は、前記選択されたドメインのノードに対してその選択されたゲートウェイ及びその選択されたゲートウェイへのルートを含むスパニングツリーを備えている。ブロック２４２０において、ノードは、１つ以上のスケジューリングサイクルにわたってメッシュネットワークの１つ以上のノードにより使用されるべき１つ以上のスケジュールにアクセスすることを遂行する。ブロック２４３０において、ノードは、ノード間の１つ以上のリンクの状態及び１つ以上のスケジュールに基づき、前記選択されたゲートウェイに対して一次又はバックアップルーティング経路の選択された１つへのスイッチングを遂行する。ブロック２４４０において、ノードは、メッシュネットワークの少なくとも一部分におけるルーティングを前記選択されたルーティング経路に基づいて変更させることを遂行する。
【０２２０】
図２５は、小型セルバックホールに対する自己編成ネットワーク概念を遂行するための論理フロー図である。図２５は、更に、規範的方法の動作、コンピュータ読み取り可能なメモリで実施されるコンピュータプログラムインストラクションの実行結果、ハードウェアで実施されるロジックにより遂行される機能、及び／又は規範的実施形態によって機能を遂行するための相互接続された手段を示している。図２５は、典型的に、ＷＣＣ（例えば、ＳＯＮノード２１０）のようなコントローラ、又は他のネットワークコントローラにより遂行される。以下の例において、図２５のフローは、例２と称されることに注意されたい。
【０２２１】
ブロック２５１０において、コントローラは、次のことを遂行する：即ち、リンクを通して相互接続される多数のノードの１つ以上のドメインを含むメッシュネットワークにおいて、１つ以上のドメイン、それらの多数のノード及びそれらのリンクは、トポロジーの一部分であり、選択されたドメインに対して、その選択されたドメインを別のネットワークに接続する少なくとも１つのゲートウェイがあり、その少なくとも１つのゲートウェイのうちの選択されたゲートウェイに対する一次及びバックアップルーティング経路のセットを決定し、その選択されたゲートウェイに対する各一次及びバックアップルーティング経路は、前記選択されたドメインのノードに対してその選択されたゲートウェイ及びその選択されたゲートウェイへのルートを含むスパニングツリーを備えている。ブロック２５２０において、コントローラは、次のことを遂行する：即ち、前記選択されたドメインの他のゲートウェイに対して一次及びバックアップルーティング経路のセットの決定を遂行する。コントローラは、ブロック２５３０において、１つ以上のスケジューリングサイクルにわたりメッシュネットワークのノードにより使用されるべき１つ以上のスケジュールの決定を遂行する。ブロック２５４０において、コントローラは、メッシュネットワークのノードへの情報の送信を遂行し、ノードの情報は、少なくとも、ノードの一次及びバックアップルーティング経路、並びに前記選択されたドメインのノードの１つ以上のスケジュールを記述する。
【０２２２】
付加的な例は、次の通りである。
例３：選択されたゲートウェイに対して一次及びバックアップルーティング経路のセットを決定することを更に含む例１の方法、又はその選択されたゲートウェイに対して一次及びバックアップルーティング経路のセットを決定することが、少なくとも、次のこと：即ち、
選択されたゲートウェイに直接隣接するリンクを、ツリーの根に接続されるツリーのステムとして指定し、そして根は、選択されたゲートウェイであり；
各ステムを、全てのブランチの連合が前記選択されたドメインのノードを含むまで、ブランチへと成長させ；及び
各ブランチを、前記選択されたドメインをカバーする完全スパニングツリーが生じるまで、成長させる、
ことを遂行することによって遂行される例２の方法。
【０２２３】
例４：親ノードへの直接的なホップリンクを経て他の親ノードへリーフノードを移動することで小さなホップカウントが生じる場合には、少なくとも他の親ノードへリーフノードを移動することによってブランチのリーフノードを最適化することを更に含む、例３の方法。
【０２２４】
例５：スパニングツリーの数は、ステムの数に等しく、これは、前記選択されたゲートウェイへのノード当りのルートの数に等しい例３又は４のいずれかの方法。
【０２２５】
例６：前記選択されたドメインの各ノードに対して、前記選択されたゲートウェイへのスパニングツリーの多数の経路のプライオリティを、少なくとも、次のこと：即ち、
前記選択されたゲートウェイへのホップカウントの数が最も少ない経路に最高のプライオリティをセットし；
等しいホップカウント状態のタイを切断してその状態の１つの経路を高いプライオリティの経路としてセットし；及び
最高のプライオリティの経路を一次経路と称する；
ことにより識別することを更に含む、例３から５のいずれかの方法。
【０２２６】
例７：タイの切断は、更に、次のもの：即ち、ノードの重み；予想トラフィック需要がスパニングツリー間でできるだけ等しく分担されること；及びランダムな指定；のうちの１つ以上を使用することによりタイを切断することを含む例６の方法。
【０２２７】
例８：一次及びバックアップルーティング経路のリンクスケジュールを最適化することを更に含む、例１から７のいずれかの方法。
【０２２８】
例９：複数のゲートウェイを含む１つ以上のドメインの各々に対して、
前記一次及びバックアップルーティング経路のセットにアクセスし、１つ以上のスケジュールにアクセスし、ルートを切り換え及び生じさせることは、ドメイン内の複数のゲートの各々に対して遂行され；及び
複数のゲートウェイの各々に対するスパニングツリーは、対応するドメイン内のノードをスパンする；
例１から８のいずれか１つの方法。
【０２２９】
例１０：１つ以上のスケジュールは、繰り返しスケジュールへと順序付けされる構築送信セットを含む、例１から９のいずれか１つの方法。
【０２３０】
例１１：少なくとも送信セットを構築しそしてその構築された送信セットを繰り返しスケジュールへと順序付けすることにより１つ以上のスケジューリングサイクルにわたってメッシュネットワークの１つ以上のノードにより使用されるべき１つ以上のスケジュールを決定することを更に含む、例１から１０のいずれか１つの方法。
【０２３１】
例１２：送信セットの構築及び順序付けは、次のこと：即ち、
各スケジュールサイクルにおいて、各リンクには少なくとも１つの送信の機会が与えられねばならず；
あるリンクは、他のリンクより重要であると考えねばならず且つ各スケジュールサイクルにおいてより多くの機会が与えられねばならず；
スケジューリングサイクルの各スロットにおいて送信セットを識別し且つ構築し、その送信セットは、同じ瞬間にアクティブとなる最大数のバラバラのリンクで構築され；
メッシュネットワーク内の全てのリンクをカバーできるサイクル当りの最小スロット数を識別し；及び／又は
端−端遅延を保証するためにスケジュールサイクルにおける送信セットの順序を識別することによりスケジューリングサイクルの各スロットに送信セットを指定する；
ことの１つ以上を含む、例１０の方法。
【０２３２】
例１３：メッシュネットワークのあるノードにより遂行される方法であって、バーチャル接続及びトラフィックフローを使用して、受信したクライアントデータを、メッシュネットワークのリンクを経て転送することを更に含む、例１から１２のいずれか１つの方法。
【０２３３】
例１４：前記バーチャル接続を使用することは、クライアントデータに対する到来トラフィックを、バーチャル接続識別子により識別されるバーチャル接続へとマッピングすることを含む、例１３の方法。
【０２３４】
例１５：前記バーチャル接続及びトラフィックフローを使用することは、更に、ユーザデータをカプセル化することを含み、ユーザデータは、次のフィールドを含むヘッダを備えたフレームへとカプセル化され、
0006535387.tif 000002
ここで、ＩＤ＝識別である、例１３又は１４のいずれかの方法。
【０２３５】
例１６：あるノードによって遂行される方法であって、あるノードは、トラフィックをフローとして取り扱い、フローは、サービスクオリティプライオリティ識別及びバーチャル接続識別によって分離され、そしてスイッチングは、ローカル負荷及び混雑状態情報に基づいて、一次及びバックアップルーティング経路からの事前計算されたルート代替物を使用してトラフィックのローカル転送を生じさせる、例１から１５のいずれか１つの方法。
【０２３６】
例１７：前記ローカル転送は、更に、次のこと：即ち、
事前計算された経路優先度、及び各経路のボトルネックリンクの状態を使用することにより、一次及びバックアップルーティング経路からの経路を前記あるノードとしての入口ノードにより選択し；
各プライオリティクラスに基づいて異なる転送判断を実行し；
ルート計算により設定された優先度に基づき最良の利用可能な経路を含むローカル転送テーブルを使用して転送判断を実行し；
トポロジー構成情報及びネットワーク状態情報に基づいてローカル転送テーブルを形成し及び維持し、これは、新たなトポロジー構成が受け取られるたびに及び新たな状態情報がネットワークから受け取られて、１つ以上のリンク故障、リンク混雑、及び／又は他の異常を指示するたびに、テーブルを更新することを含み；
入口ノードを通るトラフィックフローごとに代替的ルーティング経路の利用性を前記あるノードとしての入口ノードにより推定し；
転送判断を実行するときにスパニングツリー識別子及びメッシュネットワーク識別子のみを前記あるノードとしての中間ノードにより検査し；
前記フレームを前記プライオリティ情報に基づいて出力ポートにおいて正しいキューへ指定し；及び／又は
ボトルネックリンクの容量を分担するのではなく低プライオリティトラフィックを代替的経路へ強制するために厳密なプライオリティキューを目標として使用し、この使用は、前記分担が公平に遂行されるように行われる；
ことの１つ以上を含む、例１６の方法。
【０２３７】
例１８：前記スイッチングは、次のこと：即ち、
経路再選択負荷バランシングを入口ノードだけに適用し、中間ノードは、最初に選択された経路変更せず；
経路状態情報に基づき代替的事前計算経路をプライオリティリストから選択し；
経路再選択負荷バランシングは、フローベースであり、完全なフローは、代替的経路に再指向され；
経路再選択負荷バランシングは、プライオリティベースであり、プライオリティの最も高いフローが最初に最も適したルーティング経路を取得し、プライオリティが２番目に高いフローが次に良い利用可能なルートを取得し、そして残りのフローを通してこのプロセスを続け；
経路再選択負荷バランシングにおいて、プライオリティの高いトラフィックフローが、プライオリティの低いトラフィックフローを無効化するか、或いはプライオリティの高いトラフィックフローが、プライオリティの低いトラフィックフローを無効化し且つその先を越し；
逆マルチプレクシングに基づく負荷バランシングを適用して、低プライオリティのバルク及びベストエフォートトラフィックをパケットベース形態でバランスさせ；
逆マルチプレクシングに基づく負荷バランシングを低プライオリティトラフィックのみに適用し；
逆マルチプレクシングに基づく負荷バランシングにおいて、利用可能な全ての経路を使用し；
逆マルチプレクシングに基づく負荷バランシングは、パケットベースであり、到来する各パケットは、混雑の少ない経路に指向され；及び／又は
パケットにシーケンス番号を付し、ドメインの出口ノードで再順序付けを行う；
ことの１つ以上を含む１つ以上のオンデマンド動的負荷バランシング方法を遂行する、例１から１７のいずれか１つの方法。
【０２３８】
例１９：前記スイッチング及びルーティングを行わせることは、更に、ハイアラーキー欠陥回復システムを実施することを含み、一次アクションは、１つ以上のスパニングツリーにおいて欠陥の場合に代替的事前計算ルーティング経路にトラフィックをリルートすることであり、そして二次アクションは、折れたスパニングツリーを回復することである、例１から１８のいずれか１つの方法。
【０２３９】
例２０：欠陥検出は、イベントベースであり、そして欠陥は、欠陥ポイントからメッシュネットワークの全てのノードへブロードキャストされるリンク状態更新メッセージをトリガーする、例１９の方法。
【０２４０】
例２１：ハイアラーキー欠陥回復システムの実施は、更に、高速ローカルリルートを遂行することを含み、切断リンク上を送信されるべきトラフィックは、代替的事前計算ルーティング経路に沿って再指向され、それにより、欠陥ポイントのノードは、パケットをアドホックバイパス経路セグメントに沿って望ましい行先に向かってリルートし始める、例１９又は２０のいずれか１つの方法。
【０２４１】
例２２：前記高速ローカルリルートの遂行は、更に、次のこと：即ち、
各ノードは、メッシュネットワークルートドメインの各行先ノードに対して経路優先度を維持し；
ゲートウェイとノードとの間の一次ルーティング経路の優先度は、集中型コントローラにより指定及び構成され；
ノード間の経路優先度は、スパニングツリーを経てのホップカウントに従ってノードそれ自体により計算され；
経路優先度は、ノードが新たなルーティング構成又はリンククオリティ変化レポートを受け取るたびに更新され；
パケットの現在経路が切断リンクによりブロックされた場合には、ノードの動作リンクを経てパケット行先へ至る代替的スパニングツリーに対して経路優先度をチェックし、そして代替的スパニングツリーが見つかった場合には、その代替的スパニングツリーを経てパケットをリルートする；
ことの１つ以上を含む再選択スパニングツリー方法を遂行することを含む例２１の方法。
【０２４２】
例２３：パケット行先への代替的スパニングツリーがない場合、又は代替的スパニングツリーが、あまり適していない遅延、ホップカウント又は容量を伴う経路に通じる場合には、「隣接部へのトス」手順が使用され、パケットは、必ずしも事前計算経路のいずれにも属さない動作リンクを経て隣接部へ送信され、この隣接部は、次のものを使用してパケットの元々のスパニングツリーを経てパケットを行先へルーティングでき：即ち、
各切断リンクに対する適格な隣接部及び影響を受けるスパニングツリー・行先ノード対は、構成又はリンク状態変化に基づいて各ノードにより計算され、そして選択ルールは、次の通りであり：即ち、
「隣接部へのトス」ノードとこのノードとの間のリンクは、フェイルしたスパニングツリーに属さず；及び
「隣接部へのトス」ノードと行先ノードとの間の経路は、このノードを含まない；
例２２の方法。
【０２４３】
例２４：高速ローカルリルートを遂行することは、更に、プライオリティリストからの次に利用可能な経路によりローカル転送テーブルに基づいて修正ルートを選択する経路再選択を含む、例２１から２３のいずれか１つの方法。
【０２４４】
例２５：高速ローカルリルートを遂行することは、更に、経路欠陥が持続するか又はネットワークに現在多数の欠陥があることに応答してローカルスパニングツリーリペアを遂行することを含み、ルーティング経路に対するローカル修正は、次のこと：即ち、
スパニングツリーの切断リンクを、スパニングツリーに元々属さない動作リンクに置き換え；
当該ノード間のシグナリングがルーティング構造のローカル再アレンジを生じ；
ゲートウェイへの経路の上流リンクの１つが切断した場合には各ノードが潜在的な交換リンクに関する情報を維持し、そしてノードは、ルーティングトポロジー変化の際にこの情報を更新し；
各切断スパニングツリーに対して、適当な交換候補は、切断ポイントからスパニングツリーに沿って上流へのノード及び下流へのノードを直接接続するリンクであり；
ローカルスパニングツリーリペア手順は、ゲートウェイに向いた切断リンクを伴う開始ノードにより開始され、そしてその開始ノードは、リンクの下流エンドポイントリペアノードへのリペアリンクをアクチベートする信号を送信し；及び／又は
リペアノードは、それの転送優先度を更新し、新たなリンクを使用するようにルーティングし、そしてリペアしたスパニングツリーについて他のノードに通知する；
ことの１つ以上を含むものが実行される、例２４の方法。
【０２４５】
例２６：高速ローカルリルートを遂行することは、更に、欠陥状態が永久的と思われるほど長時間続くのに応答して、全てのルーティング経路を再計算し、１つ以上の新たなスケジュールを計算し、そして全ネットワークを、その再計算されたルーティング経路及び計算された１つ以上の新たなスケジュールに基づいて再構成することを含む、例２５の方法。
【０２４６】
例２７：ネットワーク内にローカル欠陥識別及びリンク状態情報を配布することを更に含む、例１から２６のいずれか１つの方法。
【０２４７】
例２８：ネットワーク内にローカル欠陥識別及びリンク状態情報を配布することは、更に、次のこと：即ち、
リンク及び経路の両状態を監視し；
リンクの動作状態は、ワイヤレス物理的レイヤから受け取った状態指示に基づき；
周期的なハローメッセージを使用して全ての隣接ノードへの全てのリンクを経ての隣接ノードへの到達性を検証し；
主として、プライオリティ特有の出力キュー長さにより混雑を推定し；
リンク状態更新メッセージを使用して全メッシュネットワーク内にリンク状態情報を配布し、ノードが著しいリンク状態変化又はリンクのトラフィック負荷の変化を検出したときにノードがリンク状態更新メッセージを送信し；
リンク状態更新メッセージは、制御平面において、リンク状態更新メッセージで特定されるスパニングツリーに沿って伝播され、そして各ノードは、受け取ったリンク状態更新メッセージを、そのリンク状態更新メッセージが受け取られたところの隣接部を除いて、それ自身の隣接部へ転送し；及び／又は
各リンク状態イベントに対して、ノードは、当該リンクを横断する全てのスパニングツリーに沿ってリンク状態更新メッセージを送信する；
ことの１つ以上を含む、例２７の方法。
【０２４８】
例２９：前記方法は、一方向性及び両方向性の両クライアントトラフィックをサポートする、例１から２８のいずれか１つの方法。
【０２４９】
例３０：前記方法は、同じルーティング経路又は異なるルーティング経路のいずれかを通して両方向性トラフィックの上流及び下流方向のルーティングをサポートする、例１から２０のいずれか１つの方法。
【０２５０】
例３１：前記方法は、更に、少なくともスイッチングを遂行し且つエネルギー最適化に一部分基づいてルーティングを遂行させることを含む、例１から３０の少なくとも１つの方法。
【０２５１】
例３２：前記エネルギー最適化は、次のこと：即ち、
ノード及びリンクレベルでエネルギー節約を行うエネルギー節約制御モジュールを実行し；
エネルギー節約制御モジュールの動作をクライアントレイヤと整合し、どのクライアントノードが潜在的なスリーパーであるか指示することを含み；
エネルギー節約制御モジュールは、どのクライアントノードが潜在的なスリーパーであるかそれ自身で学習し；
エネルギー節約制御モジュールは、クライアントレイヤに潜在的なスリーパーを提案し；
ノードは、その内部自己診断に基づいて遮断を要求でき；
潜在的なスリープノードが指示されると、そのノードは、進行中のトラフィックに影響することなくノードをスリープさせることを許すように全スパニングツリーにおけるリーフノードとなるよう強制され；
新たなトポロジー構成情報を配布し、そしてアクチベーションの後に、ノードをスリープさせ；
ある基準に基づいてウェイクアップ手順を遂行し；
リンクレベルエネルギー節約をトポロジー最適化において考慮し；及び／又は
エネルギー節約制御モジュールプロセスは、保守の目的でも行われ、そして保護スキームをアクチベートする必要なくノードの率直な遮断を与える；
ことの１つ以上を含む、例３１の方法。
【０２５２】
例３３：トポロジーは、第１トポロジーであり、メッシュネットワークに１つ以上の変化が生じて、第２トポロジーを生成し；
前記方法は、更に、選択されたドメインの全てのゲートウェイに対する一次及びバックアップルーティング経路のセットの決定を再遂行し、且つ１つ以上のスケジュールの決定を再遂行することを含み；及び
前記情報の送信は、第１トポロジー構成から第２トポロジー構成への移行を同期させるように遂行される；例２の方法。
【０２５３】
例３４：メッシュネットワークは、ワイヤレスメッシュネットワークである、例１から３３のいずれか１つの方法。
【０２５４】
例３５：メッシュネットワークは、ワイヤレスメッシュネットワークであり、そして多数のノードは、ミリメータ波リンクを使用して互いに通信する、例１から３４のいずれか１つの方法。
【０２５５】
例３６：光学的メッシュネットワークにおいて遂行される、例１から３３のいずれか１つの方法。
【０２５６】
例３７：リンクを通して相互接続された多数のノードの１つ以上のドメインを含むメッシュネットワークにおいて、選択されたドメインに少なくとも１つのゲートウェイがあって、その選択されたドメインを別のネットワークに接続し、１つ以上のドメイン及びそれら多数のノード及びそれらのリンクは、トポロジーの一部分であり、少なくとも１つのゲートウェイの選択されたゲートウェイに対する一次及びバックアップルーティング経路のセットにアクセスするための手段を備え、その選択されたゲートウェイに対する各一次及びバックアップルーティング経路は、その選択されたゲートウェイと、前記選択されたドメインのノードに対するその選択されたゲートウェイへのルートとを含むスパニングツリーを備えるものであり；更に、
１つ以上のスケジューリングサイクルにわたりメッシュネットワークの１つ以上のノードにより使用されるべき１つ以上のスケジュールにアクセスする手段；
ノード間の１つ以上のリンクの状態及び１つ以上のスケジュールに基づき、前記選択されたゲートウェイに対する一次又はバックアップルーティング経路の選択されたルーティング経路へ切り換える手段；及び
前記メッシュネットワークの少なくとも一部分におけるルートをその選択されたルーティング経路に基づいて変更させる手段；
を備えた装置。
【０２５７】
例３８：リンクを通して相互接続された多数のノードの１つ以上のドメインを含むメッシュネットワークにおいて、１つ以上のドメイン及びそれら多数のノード及びそれらのリンクは、トポロジーの一部分であり、選択されたドメインに対して少なくとも１つのゲートウェイがあってその選択されたドメインを別のネットワークに接続し、少なくとも１つのゲートウェイの選択されたゲートウェイに対する一次及びバックアップルーティング経路のセットを決定するための手段を備え、その選択されたゲートウェイに対する各一次及びバックアップルーティング経路は、その選択されたゲートウェイと、前記選択されたドメインのノードに対するその選択されたゲートウェイへのルートとを含むスパニングツリーを備え；更に、
前記選択されたドメインの他のゲートウェイに対する一次及びバックアップルーティング経路のセットの決定を遂行するための手段；
１つ以上のスケジューリングサイクルにわたってメッシュネットワークのノードにより使用されるべき１つ以上のスケジュールを決定するための手段；及び
メッシュネットワークのノードへ情報を送信するための手段；
を備え、ノードの情報は、少なくとも、ノードに対する一次及びバックアップルーティング経路、及び選択されたドメインのノードに対する１つ以上のスケジュールを記述するものである、装置。
【０２５８】
例３９：例３から３６の方法のいずれかを遂行するための手段を更に備えた例３７又は３８のいずれか１つの装置。
【０２５９】
例４０：例３７から３９のいずれか１つの装置を備えたベースステーション。
【０２６０】
例４１：例３７から３９のいずれか１つの装置を備えたメッシュネットワーク集中型コントローラ。
【０２６１】
例４２：例３７から３９のいずれか１つの装置を１つ以上備えた通信ネットワーク。
【０２６２】
例４３：例１から３６のいずれかに記載の方法を実行するためのプログラムコードを含むコンピュータプログラム。
【０２６３】
例４４：前記コンピュータプログラムは、コンピュータに使用するために実施されたコンピュータプログラムコードを保持するコンピュータ読み取り可能な媒体を備えたコンピュータプログラム製品である、例４３に記載のコンピュータプログラム。
【０２６４】
ここに述べる実施形態は、ソフトウェア（１つ以上のプロセッサで実行される）、ハードウェア（例えば、特定用途向け集積回路）或いはソフトウェア及びハードウェアの結合で具現化される。規範的実施形態では、ソフトウェア（例えば、アプリケーションロジック、インストラクションセット）は、種々の従来のコンピュータ読み取り可能な媒体のいずれかに維持される。本書に関しては、「コンピュータ読み取り可能な媒体」とは、インストラクション実行システム、装置、又はデバイス、例えば、コンピュータにより又はそれらに関連して使用するためのインストラクションを含み、記憶し、通信し、伝播し又はトランスポートできる媒体又は手段であり、コンピュータの一例が、例えば、図１に示されて説明された。コンピュータ読み取り可能な媒体は、インストラクション実行システム、装置、又はデバイス、例えば、コンピュータにより又はそれらに関連して使用するためのインストラクションを含み、記憶し、及び／又はトランスポートできる媒体又は手段であるコンピュータ読み取り可能な記憶媒体を含む。コンピュータ読み取り可能な記憶媒体は、伝播信号は含まない。
【０２６５】
必要に応じて、ここに述べる異なる機能が異なる順序で及び／又は互いに同時に遂行されてもよい。更に、必要に応じて、前記機能の１つ以上が任意であってもよいし、合成されてもよい。
【０２６６】
本発明の種々の観点は、独立請求項に記載されるが、本発明の他の観点は、請求項に明確に記載した組み合せだけではなく、ここに述べる実施形態及び／又は従属請求項からの特徴と、独立請求項の特徴との他の組み合せも含む。
【０２６７】
以上、本発明の規範的実施形態について説明したが、それらの説明は、限定的な意味で考えてはならないことにも注意されたい。むしろ、特許請求の範囲に規定された本発明の範囲から逸脱せずに多数の種々の変更や修正がなされ得る。
【０２６８】
明細書及び／又は添付図面に見られる略語は、次のように定義される：即ち、
５Ｇ：第５世代
ＡＡＡ：認証、許可及びアカウンティング
ＢＥＲ：ビットエラー率
ＢＧＰ：ボーダーゲートウェイプロトコル
ＢＴＳ：ベーストランシーバステーション
ＣＡＰＥＸ：資本支出
ＣＣＳ：ケンブリッジ通信システム
ＣＰＵ：中央処理ユニット
ＣＮ：コアネットワーク
ＤｉｆｆＳｅｒｖ：微分型サービス
ＤＳＣＰ：微分型サービスコードポイント
ＤＳ−ＴＥ：ＤｉｆｆＳｅｒｖ認識トラフィックエンジニアリング(例えば、ＭＰＬＳ)
Ｅ２Ｅ：端−端
ＥＣＭ：エネルギー節約制御モジュール
ｅＮＢ（又はｅＮｏｄｅＢ）：進化型ノードＢ（例えば、ＬＴＥベースステーション）
ＥＳ：エネルギー節約
ＦＲＲ：高速リルート（例えば、ＭＰＬＳ）
ＦＬＲＲ：高速ローカルリルート
Ｇｂｉｔ／ｓ：ギガビット／秒
ＧｉＭＭｉｃ：Ｇビット／秒ＭＷＲマイクロメッシュクラウド概念
ＧＭＰＬＳ：一般化ＭＰＬＳ
ＧＮＳＳ：グローバルナビゲーション衛星システム
ＧＷ：ゲートウェイ（例えば、ノード）
ＨｅｔＮｅｔ：異種ネットワーク
ＨＷ：ハードウェア
ＨＷＭＰ：ハイブリッドワイヤレスメッシュプロトコル
ＩＤ：識別子
Ｉ／Ｆ：インターフェイス
ＩＧＰｓ：内部ゲートウェイプロトコル
ＩＬＰ：整数線型プログラミング
ＩＭＬＢ：逆マルチプレクス負荷バランシング
ＩＭＰＥＸ：実施費用
ＩＮ：開始ノード
ＩｎｔＳｅｒｖ：統合サービス
ＩＰ：インターネットプロトコル
ＩＳ−ＩＳ：中間システム対中間システム
ＬＤＰ：ラベル分布プロトコル
ＬＰ：線型プログラミング
ＬＳＰ：ラベルスイッチ経路
ＬＳＴＲ：ローカルスパニングツリーリペア
ＬＳＵ：リンク状態更新
ＬＴＥ：長期進化
ＬＴＥ−Ａ：長期進化−アドバンスト
ＭＡＣ：メディアアクセスコントロール
ｍａｘ：最大
ＭＢｉｔ／ｓ：メガビット／秒
ＭＭＥ：移動管理エンティティ
ｍｍＷ：ミリメータ波
ＭＰＬＳ：マルチプロトコルラベルスイッチング
ｍｓ：ミリ秒
ＮＭＳ：ネットワーク管理システム
Ｎ／Ｗ：ネットワーク
ＯＡＭ：運転、管理及び保守
ＯＰＥＸ：運転費用
ＯＳＰＦ：最短経路最初にオープン
ＰＢ：プロバイダーブリッジング
ＰＢＢ：プロバイダーバックボーンブリッジング
ＰＢＢ−ＴＥ：プロバイダーバックボーンブリッジングトラフィックエンジニアリング
ＰＣＥ：経路計算要素
ＰＣＰ：プライオリティコードポイント
ＰＭ：性能監視
ＰＲＩＯ：フロープライオリティフィールド
Ｌ２：レイヤ２（例えば、データリンクレイヤ）
Ｌ３：レイヤ３（例えば、ネットワークレイヤ）
ＱｏＳ：サービスクオリティ
ＲＦ：高周波
ＲＮ：リペアノード
ＲＲＣＴＲ：リルートカウンタフィールド
ＲＳＴ：スパニングツリー再選択
ＲＶＳＰ−ＴＥ：リソース予約プロトコルトラフィックエンジニアリング
Ｒｘ：受信器
ＳＣＴＰ：ステム制御送信プロトコル
ＳＤＨ：同期デジタルハイアラーキー
ＳＥＱ：シーケンス番号フィールド
ＳＧＷ：サービングゲートウェイ
ＳＯＮ：自己編成ネットワーク
ＳＴ：スパニングツリー
ＳＴＤＭＡ：空間時分割多重アクセス
ＳＴＩＤ：スパニングツリー識別子
ＳＷ：ソフトウェア
ＳＷＭＮ：静的ワイヤレスメッシュネットワーク、
自己編成ワイヤレスメッシュネットワークでもある
Ｔ２Ｎ：隣接部へのトス
ＴＣＯ：総所有コスト
ＴＣＰ：送信制御プロトコル
ＴＣＲ：トポグラフィー変更レポート
ＴＤＤ：時分割デュープレックス
ＴＤＭＡ：時分割多重アクセス
ＴＥ：トラフィックエンジニアリング
ＵＤＰ：ユーザデータグラムプロトコル
Ｔｘ：送信器
ＵＤＰ：ユーザデータグラムプロトコル
ＵＥ：ユーザ装置（例えば、ワイヤレス、典型的移動装置）
ＶＣ：バーチャル接続
ＶＣＩＤ：バーチャル接続（フロー）識別子
ＶＰＮ：バーチャルプライベートネットワーク
ＶＴＴ：フィンランド・テクニカル・リサーチセンター
ＷＣＣ：ＷＭＮ集中型コントローラ
ＭＤＳＴ：多数のバラバラなスパニングツリー
ＷＦＱ：重み付けされた公平なキュー
ＷＭＮ：ワイヤレスメッシュネットワーク
ＷＮ：ＷＭＮノード
ＷＮＩＤ：ＷＭＮノードＩＤ
【符号の説明】
【０２６９】
１１０：ユーザ装置（ＵＥ）
１２０：プロセッサ
１２３：コンピュータプログラムコード
１２５：メモリ
１２７：バス
１３０：トランシーバ
１５０−１：プロセッサ
１５３−１：コンピュータプログラムコード
１５５−１：メモリ
１５７−１：バス
１５８−１：アンテナ
１６０−１：トランシーバ
１６１−１：ネットワークインターフェイス
１７３、１７５：ネットワーク
１８０：プロセッサ
１８２：バックホールリンク
１８７：バス
１９０：ネットワークインターフェイス
１９５：メモリ
１９７：コンピュータプログラムコード
２１０：ＳＯＮ（自己編成ネットワーク）ノード
２１５：ＣＮ
２１０：ＳＯＮノード
２２０−１、２２０−２、２２０−ｎ：ｅＮｏｄｅＢ（ｅＮＢ）
２２５：インターネット／ネットワーク
２３０−１、２３０−２：ＳＯＮノード
２３０−２：ＳＯＮモジュール
２８０−１：マクロセル
２８０−２ないし２８０−７：下位の小型セル
２９０：リンク
Ｔ１ないしＴ８：送信セット
３１０：トポロジーマネージャー
３２０：トポロジーオプチマイザー
３２５：ルート計算
３３０：リンクスケジュール計算
３３５：エネルギー節約コントロール
３４０：ＶＣプロビジョニング
３４５：アクセスコントロール
３５０：ＷＭＮコンフィギュレータ
３５５：トポロジーデータベース
３６０：ＮＭＳエージェント
３６５：ＰＭデータベース
３７０：ＮＷ状態モニタ
５３０：ブランチ
５８０：ノード
５９０：ツリー
【図１】
0006535387.tif 000004
【図２】
0006535387.tif 000005
【図３】
0006535387.tif 000006
【図４】
0006535387.tif 000007
【図５Ａ】
0006535387.tif 000008
【図５Ｂ】
0006535387.tif 000009
【図５Ｃ】
0006535387.tif 000010
【図６】
0006535387.tif 000011
【図７】
0006535387.tif 000012
【図８】
0006535387.tif 000013
【図９】
0006535387.tif 000014
【図１０】
0006535387.tif 000015
【図１１】
0006535387.tif 000016
【図１２】
0006535387.tif 000017
【図１３】
0006535387.tif 000018
【図１４】
0006535387.tif 000019
【図１５】
0006535387.tif 000020
【図１６】
0006535387.tif 000021
【図１７】
0006535387.tif 000022
【図１８】
0006535387.tif 000023
【図１９】
0006535387.tif 000024
【図２０】
0006535387.tif 000025
【図２１】
0006535387.tif 000026
【図２２】
0006535387.tif 000027
【図２３】
0006535387.tif 000028
【図２４】
0006535387.tif 000029
【図２５】
0006535387.tif 000030