ネットワークノード
少なくとも１つのネットワークインタフェース(15)を有するネットワークノード(2)であって、少なくとも１つのネットワークインタフェース(15)の少なくとも１つを通じて他の複数のネットワークノード(3,4)への複数のネットワークリンク(5)を形成するように構成される。複数のネットワークリンク(5)の各々は、他の複数のネットワークノードのうち隣接するもの(3)の１つへのリンクである。ネットワークノード(2)はネットワークリンクを通じて関連する隣接ネットワークノード(3)に送信されるデータが正しく受信されたかどうかを判別するように構成される。ネットワークノードは、所与のネットワークリンク(5)を通じて隣接ノード(3)に送信されたデータが正しく受信されていないという最初の判別をした場合には、ネットワークノード(2)が当該隣接ノードに当該所与のネットワークリンクを通じて所定期間データを送信しないよう、メモリ内の当該ネットワークリンクについてのエントリを所定期間一時的に無効化し、所定期間の経過後に当該エントリを再有効化する。ネットワークノードは、当該所与のネットワークリンクを通じて当該隣接ネットワークノードへ送信されたデータが正しく受信されていないとの判別をさらにした場合、当該エントリをメモリ(11)から削除する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はネットワークノード、ネットワークノードのネットワーク、及びネットワークノードの動作方法に関し、非限定的ながら、特に、無線メッシュネットワークに用いられることができるようなネットワークノード、ネットワークノードのネットワーク、及びネットワークノードの動作方法に関する。
【背景技術】
【０００２】
無線メッシュネットワーク（ＷＭＮ）は、動的な自己組織化、自己設定、及び自己修復によって特徴付けられる、マルチホップで、インフラストラクチャのないネットワークである。これらの特徴により、ＷＭＮは、非常に多様な環境において高速、高信頼性、及びコスト効率の良いネットワーク配備をサポートし、また、固定及び移動ユーザに対してよりよいカバレージ及び容量を提供することが可能である。そのため、ＷＭＮは障害復旧、商業的環境及び私的環境における広範囲の用途を実現することができる。１つの典型例は、可搬型セルラネットワークの堅牢性(robustness)と迅速な配備をより増強し、災害時の復旧及び他のミッションクリティカルな状況において効率的かつ堅牢なサービスを提供するためにＷＭＮインフラストラクチャを用いる、エリクソンレスポンスプログラムである。
【０００３】
特に無線メッシュネットワークにおいて、また他のネットワークにおいても、各ネットワークノードが、自身と直接リンクを有するノード、つまり自身の隣接ノードを判別可能であることが望ましい。既存の隣接ノードの検出手法は、http://tools.ietf.org/html/draft-ietf-manet-nhdp-07で入手可能な、Clausenらの「モバイルアドホックネットワーキング(MANET)近隣発見プロトコル(NHDP) （草稿） ietf-manet-nhdp-07」, IETF (Internet Engineering Task Force)に記載されるような、周期的なハードビート（すなわちHELLO）メッセージの交換によるソフトステートメカニズムに基づいている。無線メッシュネットワーク内の各ノードは、自身の複数のインタフェース各々について周期的なHELLOメッセージを生成する。各HELLOメッセージはそのインタフェースを特定するとともに、そのノードの他のインタフェースを報告する。各HELLOメッセージは、インタフェースのインタフェース情報ベースのリンクリポジトリからの情報と、ノードのノードリポジトリからの情報とを含んでいる。
【０００４】
HELLOメッセージは、HELLO INTERVALとして知られる一定間隔で積極的に送信される。この間隔は固定であっても動的であってもよい。例えば、制御トラフィックによるネットワーク輻輳を軽減するため、この間隔を延ばす(back off)ことができる。HELLOメッセージはまた、ノード自身やその隣接ノードの変化に応じて、反応的な方法で送信されてもよい。
【０００５】
特定の間隔（隣接ノード期間満了間隔:Neighbour Expiration Interval）内に隣接ノードからのHELLOメッセージが受信されなければ、そのノードは自身の隣接ノードと連絡不能であると仮定されるであろう。
【０００６】
単純さと堅牢さにより、最適化リンクステートルーティングプロトコル(OLSR)及びアドホックオンデマンド距離ベクトル(AODV)ルーティングのような既存のルーティングプロトコルの大半は、この隣接ノード検出手法を用いている。
【０００７】
隣接ノードへの接続性を記述するリンクレイヤ情報が利用可能であれば（すなわち、リンクレイヤ確認応答の欠如などによる接続性の喪失）、隣接ノード状態を維持するために、この情報をHELLOメッセージからの情報に加えて用いてもよい。
【０００８】
例えば、IEEE802.11において、再送を最大回数おこなってもパケットを送信に失敗した場合、インジケータが送信の失敗を表すようになる。これは、アクティブな次ホップへのリンクの喪失を表す。そのような通知を受け取ると、ノードは自身の隣接リポジトリから隣接ノードを除去する。
【０００９】
HELLOメッセージに加え、アドホックオンデマンド距離ベクトル(AODV)[4]ノードが、自身の隣接ノードからのパケットを受動的にリスンし、隣接ステータスを判別する。隣接ノードへの有効なルートがあるにもかかわらず、(ALLOWED HELLO LOSS * HELLO INTERVAL)ミリ秒を超えてその隣接ノードからのデータパケットが受信されていない場合、そのノードは当該隣接ノードが現在喪失しているものと仮定する。
【００１０】
HELLOメッセージに基づく隣接ノード検出手法の主な懸案事項は検出レイテンシである。ノードは、隣接ステートタイマが満了するまで待たないと、隣接ノードの変化に気付くことができない。典型的な実装において、このタイムアウトはおよそ６秒程度である。そのようなレイテンシは一般に許容範囲を超えるものである。
【００１１】
ごく最近になって浮上してきた別の懸案事項は、HELLOメッセージのサイズが過大かもしれないということである。無線ネットワークにおいて帯域は少ないため、周期的なメッセージは小さくあるべきである。
【００１２】
リンクレイヤからの通知は不当な隣接ノード除去を引き起こしうる。リンク破損又は隣接ノード喪失に加え、リンクレイヤ通知はチャネル輻輳のような他のいくつかの理由によって発生しうる。隣接ノードへのチャネルが輻輳している場合、リンクが不当に除去されるかもしれない。
【００１３】
ノード又はネットワークにデータ送信が存在しない場合に受動的な監視データフロー(Passively Monitoring Data Flows)が適用不能であることは明らかである。さもなくば、ノードの隣接リポジトリは隣接ノードが発見されるごとに徐々に「攪拌(churn)」され、送信データが無くなったならばタイムアウトするであろう。
【発明の概要】
【００１４】
本発明の第１の見地によれば、他の複数のネットワークノードと接続可能な少なくとも１つのネットワークインタフェースを有するネットワークノードであって、前記少なくとも１つのネットワークインタフェースを通じて前記他の複数のネットワークノードへの複数のネットワークリンクを形成するように構成され、前記複数のネットワークリンクの各々は前記他の複数のネットワークノードのうち隣接するものの１つへのリンクであり、前記ネットワークノードは前記ネットワークリンクを通じて関連する隣接ネットワークノードに送信されるデータが正しく受信されたかどうかを判別するように構成され、
前記ネットワークノードは、前記複数のネットワークリンクの各々について、各ネットワークリンクが接続されている前記隣接ネットワークノードのＩＤに関するデータを有するエントリを、使用時に保存するように構成されたメモリを有し、前記ネットワークノードは前記メモリ内の前記エントリに応じて前記他の複数のネットワークノードへデータを送信するように構成され、
前記ネットワークノードは、所与のネットワークリンクを通じて隣接ノードに送信されたデータが正しく受信されていないという最初の判別をした場合には、前記ネットワークノードが該隣接ノードに該所与のネットワークリンクを通じて所定期間データを送信しないよう、前記メモリ内の該ネットワークリンクについてのエントリを前記所定期間一時的に無効化し、前記所定期間の経過後は、前記ネットワークノードが該隣接ノードに該所与のネットワークリンクを通じてデータを送信できるように該エントリを再有効化し、
前記ネットワークノードは、該所与のネットワークリンクを通じて該隣接ネットワークノードへ送信されたデータが正しく受信されていないとの判別をさらにした場合には、前記ネットワークノードがもはや該隣接ネットワークノードを隣接ネットワークノードとして取り扱わず、該所与のネットワークリンクを通じてそれ以上データを送信しないように、該エントリを前記メモリから削除するように構成されたネットワークノードが提供される。
【００１５】
これにより、明らかに存在しなくなったコネクションは削除することを可能としながら、過渡的な問題についてはコネクションを完全に削除する段階へ移行することなしに無視することが可能になる。リンク喪失の検出はさらに正確である。
【００１６】
ネットワークノードは、前記最初の判別と前記さらなる判別の間に、所与のネットワークリンクを通じて隣接ノードに送信されたデータが正しく受信されていないとの中間判別が少なくとも１回なされると、所定期間中は前記ネットワークノードが該所与のネットワークリンクを通じて前記隣接ノードへデータを送信しないよう、前記メモリ内の前記ネットワークリンクについての前記エントリを前記所定期間一時的に無効化し、前記所定期間の経過後は、前記ネットワークノードが前記所与のネットワークリンクを通じて前記隣接ノードにデータを送信することができるように前記エントリを再有効化する、ように構成されてもよい。従って、システムは、あるエントリが最終的に削除される前に、そのエントリを複数回無効化することができる。
【００１７】
最初の判別時と中間判別時とでは、エントリが無効化される所定期間を異ならせてもよい。連続して判別されるごとに所定期間が増加することが好ましい。前記さらなる判別は、前記所定期間が閾値に達するごとに１回実行することができる。そのような場合、前記所定期間は連続する判別ごとに指数的に増加しても良い。この、指数的な待ち時間(backoff)は、チャネルの競合のような、所与のリンクに影響を与える一時的な問題については、隣接ノードを用いるある程度の反復的な試行を許し、繰り返し故障しているリンクについては機能していない確率が乗法的に増加することが理解されるので、有用である。
【００１８】
ネットワークノードは、データが繰り返し正しく受信されない場合にのみ判別を行うように構成されてもよい。ネットワークノードは障害カウンタを有してもよく、ネットワークノードは、データが正しく受信されない度に前記カウンタを増加させ、前記カウンタが閾値に達した際に前記判別を行うように構成される。
【００１９】
このような統計的な処理を行うことで、（リンクが繰り返し故障するごとにしか故障通知が送信されないので）故障通知の処理に係るオーバヘッドの急激な増加を回避できるほか、時折生じるパケット障害に起因する誤った通知（従前の有線ネットワークよりも無線ネットワークでのほうがパケットの損失が起こりやすい）を回避できるという利点がある。
【００２０】
前記メモリは、使用時に、各エントリの一部として現在の所定期間とこれまでなされた判別の回数を保存するように構成されてもよい。ネットワークノードはさらに、判別がなされると、その回数に関する前記メモリの内容に基づく指数的な係数を現在の所定期間に関するエントリに乗じ、その結果を新たな所定時間として保存するように構成された乗算器を有してもよい。ネットワークノードはさらに、前記新たな所定期間が閾値を超えたか判別するように構成された比較器を有してもよい。
【００２１】
本発明は、有線ネットワークよりもそのようなリンクを有しうる環境であることを考慮すれば、特に無線ネットワーク、具体的には無線ネットワークに適用可能である。そのため、前記ネットワークインタフェースの少なくとも１つは無線ネットワークインタフェースであってよい。
【００２２】
ネットワークノードは、前記ネットワークノードがネットワーク内の他のノードにどのようにデータを送信するかを決定するために用いる、ルーティングテーブルを格納するためのメモリと、エントリの判別又は再有効化の度に前記ルーティングテーブルを更新するように構成されたルーティングプロセッサを有してよい。
【００２３】
ネットワークノードは、判別を行うと、判別後に更新される前記ルーティングテーブルに基づいて、問題のデータを別のネットワークリンクを通じて再送するように構成されてもよい。ネットワークノードは、所与のデータパケットに対し、予め定められた最大回数までこのような再送を行うように構成されてもよい。
【００２４】
本発明の第２の見地によれば、本発明の第１の見知に係るネットワークノードを複数有するネットワークが提供される。ネットワークは、本発明の第１の見知に係らないネットワークノードを必要に応じて有してもよい。
【００２５】
本発明の第３の見地によれば、他の複数のネットワークノードを有するネットワークにおけるネットワークノードの動作方法であって、
前記ネットワークノードのネットワークインタフェースを通じて他の複数のネットワークノードへの複数のネットワークリンクであって、各々が前記他の複数のネットワークノードの１つへのリンクである複数のネットワークリンクを形成するステップと、
前記ネットワークノードが、前記複数のネットワークリンクの各々について、各ネットワークリンクが接続されている隣接ネットワークノードのＩＤに関するデータを有するエントリを保存するステップと、
前記複数のエントリを用い、前記複数のネットワークリンクを通じてデータを送信するステップと、
前記複数のネットワークリンクを通じて送信されたデータが正しく受信されたか判別するステップと、
所与のネットワークリンクを通じて隣接ノードに送信されたデータが正しく受信されていないという最初の判別に応じて、前記ネットワークノードが該隣接ノードに該所与のネットワークリンクを通じて所定期間データを送信しないよう、該ネットワークリンクについてのエントリを前記所定期間一時的に無効化し、前記所定期間の経過後は、前記ネットワークノードが該隣接ノードに該所与のネットワークリンクを通じてデータを送信できるように該エントリを再有効化するステップと、
該所与のネットワークリンクを通じて該隣接ネットワークノードへ送信されたデータが正しく受信されていないとのさらなる判別に応じて、前記ネットワークノードがもはや該隣接ネットワークノードを隣接ネットワークノードとして取り扱わず、該所与のネットワークリンクを通じてそれ以上データを送信しないように、該エントリを削除するステップと、を有する方法が提供される。
【００２６】
方法は、前記最初の判別と前記さらなる判別との間に、所与のネットワークリンクを通じて隣接ノードに送信されたデータが正しく受信されていないとの中間判別が少なくとも１回なされると、所定期間中は前記ネットワークノードが該所与のネットワークリンクを通じて前記隣接ノードへデータを送信しないよう、前記ネットワークリンクについての前記エントリを前記所定期間一時的に無効化し、前記所定期間の経過後は、前記ネットワークノードが前記所与のネットワークリンクを通じて前記隣接ノードにデータを送信することができるように前記エントリを再有効化するステップ、をさらに有してもよい。従って、システムは、あるエントリが最終的に削除される前に、そのエントリを複数回無効化することができる。
【００２７】
最初の判別時と中間判別時とでは、エントリが無効化される所定期間を異ならせても良い。連続して判別されるごとに所定期間が増加することが好ましい。前記さらなる判別は、前記所定期間が閾値に達するごとに１回実行することができる。そのような場合、前記所定期間は連続する判別ごとに指数的に増加しても良い。この、指数的な待ち時間(backoff)は、チャネルの競合のような、所与のリンクに影響を与える一時的な問題については、隣接ノードを用いるある程度の反復的な試行を許し、繰り返し故障しているリンクについては機能していない確率が乗法的に増加することが理解されるので、有用である。
【００２８】
ネットワークノードは、データが繰り返し正しく受信されない場合にのみ判別を行うように構成されてもよい。ネットワークノードは故障カウンタを有してもよく、ネットワークノードは、データが正しく受信されない度に前記カウンタを増加させ、前記カウンタが閾値に達した際に前記判別を行うように構成される。
【００２９】
このような統計的な処理を行うことで、（リンクが繰り返し故障するごとにしか故障通知が送信されないので）故障通知の処理に係るオーバヘッドの急激な増加を回避できるほか、時折生じるパケット障害に起因する誤った通知（従前の有線ネットワークよりも無線ネットワークでのほうがパケットの損失が起こりやすい）を回避できるという利点がある。
【００３０】
本発明は、有線ネットワークよりもそのようなリンクを有しうる環境であることを考慮すれば、特に無線ネットワーク、具体的には無線ネットワークに適用可能である。そのため、前記ネットワークインタフェースの少なくとも１つは無線ネットワークインタフェースであってよい。
【００３１】
方法は、前記ネットワークノードがネットワーク内の他のノードにどのようにデータを送信するかを決定するために用いるルーティングテーブル、を格納するステップと、エントリの判別又は再有効化の度に前記ルーティングテーブルを更新するように構成されたルーティングプロセッサを有してよい。
【００３２】
方法は、判別を行うと、判別後に更新される前記ルーティングテーブルに基づいて、問題のデータを別のネットワークリンクを通じて再送するように構成されてもよい。方法は、所与のデータパケットに対し、予め定められた最大回数まで再送を行うステップを有してもよい。
【図面の簡単な説明】
【００３３】
【図１】本発明の一実施形態に係るネットワークノードを用いる無線メッシュネットワークの一例を示す図である。
【図２】図１のネットワークに用いられているような、本発明の第１の実施形態に係るネットワークノードを模式的に示す図である。
【図３】図２のノードからのパケット送信動作を示すフローチャートである。
【図４】図２のネットワークノードのパケット障害時動作を示すフローチャートである。
【図５】図２のネットワークノードのルーティング動作を示すフローチャートである。
【発明を実施するための形態】
【００３４】
図１は、本発明の第１の実施形態に係る複数のネットワークノード２，３，４を有する無線メッシュネットワークを示す図である。
【００３５】
ネットワーク１は、都市の近隣に広がっており、公園、図書館、複数の店舗、コーヒーショップ、及び無線インターネットプロバイダ(WISP)を包含している。各ノードは複数の無線リンク５によって複数の隣接ノードに接続されている。所与のノード（例えば図書館の中のネットワークノード２とする）について、ネットワークノード２が直接リンク５を有する複数のノードは隣接ネットワークノード３として知られ、それらは所与のネットワークノードに１つのネットワーク「ホップ」だけで直接接続されている。残りの、ネットワークノード２に複数ホップで接続されているネットワークノードは、非隣接ノード４である。ネットワークノード２は、隣接ノード３の１つを介してデータを送信してこれら非隣接ノードと通信しなければならない。
【００３６】
図２は、本発明の第１の実施形態に係るネットワークノード２を模式的に示す図である。ネットワークノード２は、コンピュータ関連装置（不図示）とデータを送受信するためのデータインタフェース１０と、そのようなデータが送受信される無線ネットワークインタフェース１５を有する。無線インタフェースは典型的にはIEEE 802.11 a/b/g (WIFI)又はIEEE 802.16 (MiMAX)準拠のインタフェースであり、アンテナ１６に接続される。
【００３７】
ネットワークノード２はさらに、パケット形式の入力データを取得するルーティングプロセッサ１２を有している。データパケットはそれぞれ、宛先ネットワークノードを示す。ルーティングの分野で通常なされるように、ルーティングプロセッサは、各データパケットをどの隣接ノード３に送信すべきかを解明する。そのために、ルーティングプロセッサはノード２のメモリに保持されるルーティングテーブル１３を用いる。このテーブルはどの隣接ネットワークノードを通じてどのネットワークノードに到達できるのかを示す。
【００３８】
ネットワークノードは自身のメモリに、自分が接続されている隣接ネットワークノード３のテーブル１１も格納している。新たなノードがネットワークに参加するにつれ、このテーブルは更新される。テーブル内のエントリの性質については、以下で詳細に説明する。
【００３９】
添付図面の図３に、ネットワークノードがさらに遠方に送信するためのデータパケットを受信した際の機能を示す。ステップ１００で、ネットワークノードはデータインタフェース１０でデータパケットを受信する。そして、ルーティングプロセッサ１２は、ステップ１０２で、ルーティングテーブル１３でパケットの宛先を調べ、そのパケットを送信する適切な隣接ネットワークノード３があるかどうか決定する。もし適切な隣接ネットワークノードがなければ、ステップ１０６でそのパケットを破棄する。
【００４０】
一方、適切な隣接ネットワークノードがあれば、ステップ１０６でルーティングプロセッサ１２はその適切な隣接ネットワークノードを選択してパケットを送信待ち行列に入れる。パケットが送信されると、ネットワークノードは（ステップ１０８で）そのパケットが正しく送信されたかどうかを判別する。ルーティングプロセッサ１２は、そのパケットを送信した隣接ノードからの確認応答（あるいは、代替実施形態では、自身のＭＡＣレイヤからの確認応答）をリスンすることにより、この判別を行う。ＭＡＣレイヤは、パケットが正しく送信(dispatch)されたかどうかを確認するために、自身のルーティングプロセスに対して確認応答を送信することもできる。確認応答が１つも受信されなければ、ネットワークノードはステップ１１０で、詳細を図４に示す障害時処理モードに入る。ネットワークノードのオペレーティングシステムのパケット転送処理はこの方法を、オペレーティングシステムに実装されているパケット障害インタフェース（ＰＦＩ）を通じて開始する。
【００４１】
この障害時処理方法はステップ１５０で開始し、ネットワークノードは障害が生じたパケットが送信された隣接ノード３のアドレスを判別する。ステップ１５２で、このアドレスは、適切な隣接ネットワークノード３及び関連リンクに関するエントリを見つけるために隣接リスト１１と比較される。ステップ１５４で、エントリが存在することを確かめるためのチェックが行われ、もし存在しない場合には、その隣接ノードへのリンクはすでに使用停止状態にあるため、障害時処理方法においてさらに行うべき処理はなく、ステップ１５６で方法は図３に復帰する。
【００４２】
リスト１１に隣接ネットワークノード３に対するエントリが存在していたものとすると、障害時処理方法は継続する。次の２つの統計的処理ステップ１５８は必須でない。これらステップでは、そのリンクに対する障害回数をカウントする変数failure_cntがステップ１６０でインクリメントされる。そして、ステップ１６２では、failure_cntカウンタが閾値FAILURE_REPORTING_THRESと比較される。failure_cntによって示される障害回数が閾値以下ならば、行動を起こすには発生した誤りが不十分であり、障害時処理方法はそれ以上何もせずに制御が図３に復帰する。
【００４３】
しかし、閾値に達した場合または統計的処理ステップが用いられない場合には、ステップ１６４においてリスト１１中のエントリが一時的に無効化される。以下で説明するように、この無効化は不活性化タイマを現時点よりも後に設定することで生じる。エントリ内の様々なデータ項目もまた更新される。エントリが無効化された回数をカウントするdisable_cntがインクリメントされ、エントリが再有効化されるべき時間を示すeb_timerが現時点に対して無効化期間eb_timer_interval・ｅdisable_cntを加えた時間に設定される。ここで、eb_timer_intervalは一定時間であり、ｅは自然対数の底(2.718..)である。統計的処理ステップ１５８が用いられる場合、障害回数failure_cntはゼロにリセットされる。
【００４４】
ステップ１６６で、無効化期間が閾値EB_INTERVAL_MAXと照合される。無効化期間が閾値より大きい場合、ステップ１６８で、リスト１１内のその隣接エントリは削除される。これは、ネットワークノード２と、関連する隣接ネットワークノード３との間のリンクが破棄されたことに他ならないため、もはやそのリンクを通じてデータが送信されることはない。そして、方法は図３に復帰する。
【００４５】
無効化期間が閾値未満なら、方法は単純に図３の方法に復帰する。
【００４６】
図４に示す障害時処理方法の結果がどうであれ、この方法が１回完了するごとに、図３に示す方法はステップ１１２に進む。ここで、ルーティングプロセッサ１２は、ルーティングテーブルを更新しなくてはならないことをルーティング通知インタフェース（ＲＮＩ）に通知される。ルーティングテーブルは、図４により詳細に示すようにして再計算される。
【００４７】
ステップ１８０で、現在のルーティングテーブル１３が空にされ、ステップ１８２でリスト１１からの隣接ノードに対するエントリがルーティングテーブルに追加される。従って、ステップ１６８で削除された隣接ノードなしで更新される。
【００４８】
ステップ１８４で方法は、ルーティングテーブル内の各エントリに対して開始され、ステップ１８６で、現在判別しているエントリがテーブルの終わりを示すマーカNULLかどうかが判別される。もしそうであれば、ルーティングテーブルは全ての適切な隣接ノード３に対するルートを有しており、従って、適切なアルゴリズムを用いて非隣接ノード４へのルートを決定する（ステップ１８８）ために、ルーティングアルゴリズムを用いることができる。
【００４９】
さもなければ、方法はステップ１９０に進み、ここで方法はタイムアウトタイマ(timeout timer)が現在の隣接ノードについて満了しているかどうかを判別する。タイムアウトタイマはHELLOメッセージ又はデータパケット確認応答が隣接ノードから受信されてからの時間を示し、関連リンク５が有効であることのバックアップチェックの機能を果たす。タイムアウトタイマが満了していれば、ステップ１９２でそのノードが隣接リスト１１から削除され、またルーティングテーブルに追加もされずに、方法はルーティングテーブル内の次のエントリに移行する。
【００５０】
さもなければ、ステップ１９４でルーティングプロセッサは、時刻eb_timerが現時刻を過ぎているかどうかを判別し、もし過ぎていればノードが無効化され、従ってルーティングテーブルに追加されない。そのため、無効化されたノードは直接送信されているデータから無効化され、それらはeb_timerで与えられる時間が経過したかどうかに基づいてルーティングテーブルから除外される。そして方法はルーティングテーブル内の次のエントリに進む。
【００５１】
eb_timerを過ぎれば、隣接リスト内のエントリは無効化されなくなり、最初のホップとして利用可能となる（すなわち、そのエントリは依然として隣接ノード３に関連している）。従って、ステップ１９６で、エントリはルーティングテーブル内で、隣接ノードに直接到達可能であることを示すようになる。
【００５２】
ルーティングテーブルの再計算が終わると、データパケットを再送信すべきかどうかを判別可能となる（図３、ステップ１１４）。そのパケットが最後に送信されてからルーティングテーブルが変更されているかもしれないことを考えれば、代替ルートを用いた方が成功する可能性が高いであろう。各パケットは、最大でMAX_REFWD_TIMEを上限とした回数、ルーティング参照ステップ（ステップ１０２）に戻される。再送信が試行された回数を、パケットのヘッダに記録することができる。回数が超過した場合、パケットは破棄される。
【００５３】
ネットワークノードが上述のステップ１０８でパケットが正しく送信されたと判別した場合、隣接ノード３へのリンクは機能している。従って、ステップ１１６でタイムアウトタイマは現在の時刻に所定間隔nb_timer_interval加えた時刻にリセットされ、リンクが無効化された回数を表す変数disable_cntはゼロに設定される。そして、ネットワークノード２は次のパケットを待つ。
【技術分野】
【０００１】
本発明はネットワークノード、ネットワークノードのネットワーク、及びネットワークノードの動作方法に関し、非限定的ながら、特に、無線メッシュネットワークに用いられることができるようなネットワークノード、ネットワークノードのネットワーク、及びネットワークノードの動作方法に関する。
【背景技術】
【０００２】
無線メッシュネットワーク（ＷＭＮ）は、動的な自己組織化、自己設定、及び自己修復によって特徴付けられる、マルチホップで、インフラストラクチャのないネットワークである。これらの特徴により、ＷＭＮは、非常に多様な環境において高速、高信頼性、及びコスト効率の良いネットワーク配備をサポートし、また、固定及び移動ユーザに対してよりよいカバレージ及び容量を提供することが可能である。そのため、ＷＭＮは障害復旧、商業的環境及び私的環境における広範囲の用途を実現することができる。１つの典型例は、可搬型セルラネットワークの堅牢性(robustness)と迅速な配備をより増強し、災害時の復旧及び他のミッションクリティカルな状況において効率的かつ堅牢なサービスを提供するためにＷＭＮインフラストラクチャを用いる、エリクソンレスポンスプログラムである。
【０００３】
特に無線メッシュネットワークにおいて、また他のネットワークにおいても、各ネットワークノードが、自身と直接リンクを有するノード、つまり自身の隣接ノードを判別可能であることが望ましい。既存の隣接ノードの検出手法は、http://tools.ietf.org/html/draft-ietf-manet-nhdp-07で入手可能な、Clausenらの「モバイルアドホックネットワーキング(MANET)近隣発見プロトコル(NHDP) （草稿） ietf-manet-nhdp-07」, IETF (Internet Engineering Task Force)に記載されるような、周期的なハードビート（すなわちHELLO）メッセージの交換によるソフトステートメカニズムに基づいている。無線メッシュネットワーク内の各ノードは、自身の複数のインタフェース各々について周期的なHELLOメッセージを生成する。各HELLOメッセージはそのインタフェースを特定するとともに、そのノードの他のインタフェースを報告する。各HELLOメッセージは、インタフェースのインタフェース情報ベースのリンクリポジトリからの情報と、ノードのノードリポジトリからの情報とを含んでいる。
【０００４】
HELLOメッセージは、HELLO INTERVALとして知られる一定間隔で積極的に送信される。この間隔は固定であっても動的であってもよい。例えば、制御トラフィックによるネットワーク輻輳を軽減するため、この間隔を延ばす(back off)ことができる。HELLOメッセージはまた、ノード自身やその隣接ノードの変化に応じて、反応的な方法で送信されてもよい。
【０００５】
特定の間隔（隣接ノード期間満了間隔:Neighbour Expiration Interval）内に隣接ノードからのHELLOメッセージが受信されなければ、そのノードは自身の隣接ノードと連絡不能であると仮定されるであろう。
【０００６】
単純さと堅牢さにより、最適化リンクステートルーティングプロトコル(OLSR)及びアドホックオンデマンド距離ベクトル(AODV)ルーティングのような既存のルーティングプロトコルの大半は、この隣接ノード検出手法を用いている。
【０００７】
隣接ノードへの接続性を記述するリンクレイヤ情報が利用可能であれば（すなわち、リンクレイヤ確認応答の欠如などによる接続性の喪失）、隣接ノード状態を維持するために、この情報をHELLOメッセージからの情報に加えて用いてもよい。
【０００８】
例えば、IEEE802.11において、再送を最大回数おこなってもパケットを送信に失敗した場合、インジケータが送信の失敗を表すようになる。これは、アクティブな次ホップへのリンクの喪失を表す。そのような通知を受け取ると、ノードは自身の隣接リポジトリから隣接ノードを除去する。
【０００９】
HELLOメッセージに加え、アドホックオンデマンド距離ベクトル(AODV)[4]ノードが、自身の隣接ノードからのパケットを受動的にリスンし、隣接ステータスを判別する。隣接ノードへの有効なルートがあるにもかかわらず、(ALLOWED HELLO LOSS * HELLO INTERVAL)ミリ秒を超えてその隣接ノードからのデータパケットが受信されていない場合、そのノードは当該隣接ノードが現在喪失しているものと仮定する。
【００１０】
HELLOメッセージに基づく隣接ノード検出手法の主な懸案事項は検出レイテンシである。ノードは、隣接ステートタイマが満了するまで待たないと、隣接ノードの変化に気付くことができない。典型的な実装において、このタイムアウトはおよそ６秒程度である。そのようなレイテンシは一般に許容範囲を超えるものである。
【００１１】
ごく最近になって浮上してきた別の懸案事項は、HELLOメッセージのサイズが過大かもしれないということである。無線ネットワークにおいて帯域は少ないため、周期的なメッセージは小さくあるべきである。
【００１２】
リンクレイヤからの通知は不当な隣接ノード除去を引き起こしうる。リンク破損又は隣接ノード喪失に加え、リンクレイヤ通知はチャネル輻輳のような他のいくつかの理由によって発生しうる。隣接ノードへのチャネルが輻輳している場合、リンクが不当に除去されるかもしれない。
【００１３】
ノード又はネットワークにデータ送信が存在しない場合に受動的な監視データフロー(Passively Monitoring Data Flows)が適用不能であることは明らかである。さもなくば、ノードの隣接リポジトリは隣接ノードが発見されるごとに徐々に「攪拌(churn)」され、送信データが無くなったならばタイムアウトするであろう。
【発明の概要】
【００１４】
本発明の第１の見地によれば、他の複数のネットワークノードと接続可能な少なくとも１つのネットワークインタフェースを有するネットワークノードであって、前記少なくとも１つのネットワークインタフェースを通じて前記他の複数のネットワークノードへの複数のネットワークリンクを形成するように構成され、前記複数のネットワークリンクの各々は前記他の複数のネットワークノードのうち隣接するものの１つへのリンクであり、前記ネットワークノードは前記ネットワークリンクを通じて関連する隣接ネットワークノードに送信されるデータが正しく受信されたかどうかを判別するように構成され、
前記ネットワークノードは、前記複数のネットワークリンクの各々について、各ネットワークリンクが接続されている前記隣接ネットワークノードのＩＤに関するデータを有するエントリを、使用時に保存するように構成されたメモリを有し、前記ネットワークノードは前記メモリ内の前記エントリに応じて前記他の複数のネットワークノードへデータを送信するように構成され、
前記ネットワークノードは、所与のネットワークリンクを通じて隣接ノードに送信されたデータが正しく受信されていないという最初の判別をした場合には、前記ネットワークノードが該隣接ノードに該所与のネットワークリンクを通じて所定期間データを送信しないよう、前記メモリ内の該ネットワークリンクについてのエントリを前記所定期間一時的に無効化し、前記所定期間の経過後は、前記ネットワークノードが該隣接ノードに該所与のネットワークリンクを通じてデータを送信できるように該エントリを再有効化し、
前記ネットワークノードは、該所与のネットワークリンクを通じて該隣接ネットワークノードへ送信されたデータが正しく受信されていないとの判別をさらにした場合には、前記ネットワークノードがもはや該隣接ネットワークノードを隣接ネットワークノードとして取り扱わず、該所与のネットワークリンクを通じてそれ以上データを送信しないように、該エントリを前記メモリから削除するように構成されたネットワークノードが提供される。
【００１５】
これにより、明らかに存在しなくなったコネクションは削除することを可能としながら、過渡的な問題についてはコネクションを完全に削除する段階へ移行することなしに無視することが可能になる。リンク喪失の検出はさらに正確である。
【００１６】
ネットワークノードは、前記最初の判別と前記さらなる判別の間に、所与のネットワークリンクを通じて隣接ノードに送信されたデータが正しく受信されていないとの中間判別が少なくとも１回なされると、所定期間中は前記ネットワークノードが該所与のネットワークリンクを通じて前記隣接ノードへデータを送信しないよう、前記メモリ内の前記ネットワークリンクについての前記エントリを前記所定期間一時的に無効化し、前記所定期間の経過後は、前記ネットワークノードが前記所与のネットワークリンクを通じて前記隣接ノードにデータを送信することができるように前記エントリを再有効化する、ように構成されてもよい。従って、システムは、あるエントリが最終的に削除される前に、そのエントリを複数回無効化することができる。
【００１７】
最初の判別時と中間判別時とでは、エントリが無効化される所定期間を異ならせてもよい。連続して判別されるごとに所定期間が増加することが好ましい。前記さらなる判別は、前記所定期間が閾値に達するごとに１回実行することができる。そのような場合、前記所定期間は連続する判別ごとに指数的に増加しても良い。この、指数的な待ち時間(backoff)は、チャネルの競合のような、所与のリンクに影響を与える一時的な問題については、隣接ノードを用いるある程度の反復的な試行を許し、繰り返し故障しているリンクについては機能していない確率が乗法的に増加することが理解されるので、有用である。
【００１８】
ネットワークノードは、データが繰り返し正しく受信されない場合にのみ判別を行うように構成されてもよい。ネットワークノードは障害カウンタを有してもよく、ネットワークノードは、データが正しく受信されない度に前記カウンタを増加させ、前記カウンタが閾値に達した際に前記判別を行うように構成される。
【００１９】
このような統計的な処理を行うことで、（リンクが繰り返し故障するごとにしか故障通知が送信されないので）故障通知の処理に係るオーバヘッドの急激な増加を回避できるほか、時折生じるパケット障害に起因する誤った通知（従前の有線ネットワークよりも無線ネットワークでのほうがパケットの損失が起こりやすい）を回避できるという利点がある。
【００２０】
前記メモリは、使用時に、各エントリの一部として現在の所定期間とこれまでなされた判別の回数を保存するように構成されてもよい。ネットワークノードはさらに、判別がなされると、その回数に関する前記メモリの内容に基づく指数的な係数を現在の所定期間に関するエントリに乗じ、その結果を新たな所定時間として保存するように構成された乗算器を有してもよい。ネットワークノードはさらに、前記新たな所定期間が閾値を超えたか判別するように構成された比較器を有してもよい。
【００２１】
本発明は、有線ネットワークよりもそのようなリンクを有しうる環境であることを考慮すれば、特に無線ネットワーク、具体的には無線ネットワークに適用可能である。そのため、前記ネットワークインタフェースの少なくとも１つは無線ネットワークインタフェースであってよい。
【００２２】
ネットワークノードは、前記ネットワークノードがネットワーク内の他のノードにどのようにデータを送信するかを決定するために用いる、ルーティングテーブルを格納するためのメモリと、エントリの判別又は再有効化の度に前記ルーティングテーブルを更新するように構成されたルーティングプロセッサを有してよい。
【００２３】
ネットワークノードは、判別を行うと、判別後に更新される前記ルーティングテーブルに基づいて、問題のデータを別のネットワークリンクを通じて再送するように構成されてもよい。ネットワークノードは、所与のデータパケットに対し、予め定められた最大回数までこのような再送を行うように構成されてもよい。
【００２４】
本発明の第２の見地によれば、本発明の第１の見知に係るネットワークノードを複数有するネットワークが提供される。ネットワークは、本発明の第１の見知に係らないネットワークノードを必要に応じて有してもよい。
【００２５】
本発明の第３の見地によれば、他の複数のネットワークノードを有するネットワークにおけるネットワークノードの動作方法であって、
前記ネットワークノードのネットワークインタフェースを通じて他の複数のネットワークノードへの複数のネットワークリンクであって、各々が前記他の複数のネットワークノードの１つへのリンクである複数のネットワークリンクを形成するステップと、
前記ネットワークノードが、前記複数のネットワークリンクの各々について、各ネットワークリンクが接続されている隣接ネットワークノードのＩＤに関するデータを有するエントリを保存するステップと、
前記複数のエントリを用い、前記複数のネットワークリンクを通じてデータを送信するステップと、
前記複数のネットワークリンクを通じて送信されたデータが正しく受信されたか判別するステップと、
所与のネットワークリンクを通じて隣接ノードに送信されたデータが正しく受信されていないという最初の判別に応じて、前記ネットワークノードが該隣接ノードに該所与のネットワークリンクを通じて所定期間データを送信しないよう、該ネットワークリンクについてのエントリを前記所定期間一時的に無効化し、前記所定期間の経過後は、前記ネットワークノードが該隣接ノードに該所与のネットワークリンクを通じてデータを送信できるように該エントリを再有効化するステップと、
該所与のネットワークリンクを通じて該隣接ネットワークノードへ送信されたデータが正しく受信されていないとのさらなる判別に応じて、前記ネットワークノードがもはや該隣接ネットワークノードを隣接ネットワークノードとして取り扱わず、該所与のネットワークリンクを通じてそれ以上データを送信しないように、該エントリを削除するステップと、を有する方法が提供される。
【００２６】
方法は、前記最初の判別と前記さらなる判別との間に、所与のネットワークリンクを通じて隣接ノードに送信されたデータが正しく受信されていないとの中間判別が少なくとも１回なされると、所定期間中は前記ネットワークノードが該所与のネットワークリンクを通じて前記隣接ノードへデータを送信しないよう、前記ネットワークリンクについての前記エントリを前記所定期間一時的に無効化し、前記所定期間の経過後は、前記ネットワークノードが前記所与のネットワークリンクを通じて前記隣接ノードにデータを送信することができるように前記エントリを再有効化するステップ、をさらに有してもよい。従って、システムは、あるエントリが最終的に削除される前に、そのエントリを複数回無効化することができる。
【００２７】
最初の判別時と中間判別時とでは、エントリが無効化される所定期間を異ならせても良い。連続して判別されるごとに所定期間が増加することが好ましい。前記さらなる判別は、前記所定期間が閾値に達するごとに１回実行することができる。そのような場合、前記所定期間は連続する判別ごとに指数的に増加しても良い。この、指数的な待ち時間(backoff)は、チャネルの競合のような、所与のリンクに影響を与える一時的な問題については、隣接ノードを用いるある程度の反復的な試行を許し、繰り返し故障しているリンクについては機能していない確率が乗法的に増加することが理解されるので、有用である。
【００２８】
ネットワークノードは、データが繰り返し正しく受信されない場合にのみ判別を行うように構成されてもよい。ネットワークノードは故障カウンタを有してもよく、ネットワークノードは、データが正しく受信されない度に前記カウンタを増加させ、前記カウンタが閾値に達した際に前記判別を行うように構成される。
【００２９】
このような統計的な処理を行うことで、（リンクが繰り返し故障するごとにしか故障通知が送信されないので）故障通知の処理に係るオーバヘッドの急激な増加を回避できるほか、時折生じるパケット障害に起因する誤った通知（従前の有線ネットワークよりも無線ネットワークでのほうがパケットの損失が起こりやすい）を回避できるという利点がある。
【００３０】
本発明は、有線ネットワークよりもそのようなリンクを有しうる環境であることを考慮すれば、特に無線ネットワーク、具体的には無線ネットワークに適用可能である。そのため、前記ネットワークインタフェースの少なくとも１つは無線ネットワークインタフェースであってよい。
【００３１】
方法は、前記ネットワークノードがネットワーク内の他のノードにどのようにデータを送信するかを決定するために用いるルーティングテーブル、を格納するステップと、エントリの判別又は再有効化の度に前記ルーティングテーブルを更新するように構成されたルーティングプロセッサを有してよい。
【００３２】
方法は、判別を行うと、判別後に更新される前記ルーティングテーブルに基づいて、問題のデータを別のネットワークリンクを通じて再送するように構成されてもよい。方法は、所与のデータパケットに対し、予め定められた最大回数まで再送を行うステップを有してもよい。
【図面の簡単な説明】
【００３３】
【図１】本発明の一実施形態に係るネットワークノードを用いる無線メッシュネットワークの一例を示す図である。
【図２】図１のネットワークに用いられているような、本発明の第１の実施形態に係るネットワークノードを模式的に示す図である。
【図３】図２のノードからのパケット送信動作を示すフローチャートである。
【図４】図２のネットワークノードのパケット障害時動作を示すフローチャートである。
【図５】図２のネットワークノードのルーティング動作を示すフローチャートである。
【発明を実施するための形態】
【００３４】
図１は、本発明の第１の実施形態に係る複数のネットワークノード２，３，４を有する無線メッシュネットワークを示す図である。
【００３５】
ネットワーク１は、都市の近隣に広がっており、公園、図書館、複数の店舗、コーヒーショップ、及び無線インターネットプロバイダ(WISP)を包含している。各ノードは複数の無線リンク５によって複数の隣接ノードに接続されている。所与のノード（例えば図書館の中のネットワークノード２とする）について、ネットワークノード２が直接リンク５を有する複数のノードは隣接ネットワークノード３として知られ、それらは所与のネットワークノードに１つのネットワーク「ホップ」だけで直接接続されている。残りの、ネットワークノード２に複数ホップで接続されているネットワークノードは、非隣接ノード４である。ネットワークノード２は、隣接ノード３の１つを介してデータを送信してこれら非隣接ノードと通信しなければならない。
【００３６】
図２は、本発明の第１の実施形態に係るネットワークノード２を模式的に示す図である。ネットワークノード２は、コンピュータ関連装置（不図示）とデータを送受信するためのデータインタフェース１０と、そのようなデータが送受信される無線ネットワークインタフェース１５を有する。無線インタフェースは典型的にはIEEE 802.11 a/b/g (WIFI)又はIEEE 802.16 (MiMAX)準拠のインタフェースであり、アンテナ１６に接続される。
【００３７】
ネットワークノード２はさらに、パケット形式の入力データを取得するルーティングプロセッサ１２を有している。データパケットはそれぞれ、宛先ネットワークノードを示す。ルーティングの分野で通常なされるように、ルーティングプロセッサは、各データパケットをどの隣接ノード３に送信すべきかを解明する。そのために、ルーティングプロセッサはノード２のメモリに保持されるルーティングテーブル１３を用いる。このテーブルはどの隣接ネットワークノードを通じてどのネットワークノードに到達できるのかを示す。
【００３８】
ネットワークノードは自身のメモリに、自分が接続されている隣接ネットワークノード３のテーブル１１も格納している。新たなノードがネットワークに参加するにつれ、このテーブルは更新される。テーブル内のエントリの性質については、以下で詳細に説明する。
【００３９】
添付図面の図３に、ネットワークノードがさらに遠方に送信するためのデータパケットを受信した際の機能を示す。ステップ１００で、ネットワークノードはデータインタフェース１０でデータパケットを受信する。そして、ルーティングプロセッサ１２は、ステップ１０２で、ルーティングテーブル１３でパケットの宛先を調べ、そのパケットを送信する適切な隣接ネットワークノード３があるかどうか決定する。もし適切な隣接ネットワークノードがなければ、ステップ１０６でそのパケットを破棄する。
【００４０】
一方、適切な隣接ネットワークノードがあれば、ステップ１０６でルーティングプロセッサ１２はその適切な隣接ネットワークノードを選択してパケットを送信待ち行列に入れる。パケットが送信されると、ネットワークノードは（ステップ１０８で）そのパケットが正しく送信されたかどうかを判別する。ルーティングプロセッサ１２は、そのパケットを送信した隣接ノードからの確認応答（あるいは、代替実施形態では、自身のＭＡＣレイヤからの確認応答）をリスンすることにより、この判別を行う。ＭＡＣレイヤは、パケットが正しく送信(dispatch)されたかどうかを確認するために、自身のルーティングプロセスに対して確認応答を送信することもできる。確認応答が１つも受信されなければ、ネットワークノードはステップ１１０で、詳細を図４に示す障害時処理モードに入る。ネットワークノードのオペレーティングシステムのパケット転送処理はこの方法を、オペレーティングシステムに実装されているパケット障害インタフェース（ＰＦＩ）を通じて開始する。
【００４１】
この障害時処理方法はステップ１５０で開始し、ネットワークノードは障害が生じたパケットが送信された隣接ノード３のアドレスを判別する。ステップ１５２で、このアドレスは、適切な隣接ネットワークノード３及び関連リンクに関するエントリを見つけるために隣接リスト１１と比較される。ステップ１５４で、エントリが存在することを確かめるためのチェックが行われ、もし存在しない場合には、その隣接ノードへのリンクはすでに使用停止状態にあるため、障害時処理方法においてさらに行うべき処理はなく、ステップ１５６で方法は図３に復帰する。
【００４２】
リスト１１に隣接ネットワークノード３に対するエントリが存在していたものとすると、障害時処理方法は継続する。次の２つの統計的処理ステップ１５８は必須でない。これらステップでは、そのリンクに対する障害回数をカウントする変数failure_cntがステップ１６０でインクリメントされる。そして、ステップ１６２では、failure_cntカウンタが閾値FAILURE_REPORTING_THRESと比較される。failure_cntによって示される障害回数が閾値以下ならば、行動を起こすには発生した誤りが不十分であり、障害時処理方法はそれ以上何もせずに制御が図３に復帰する。
【００４３】
しかし、閾値に達した場合または統計的処理ステップが用いられない場合には、ステップ１６４においてリスト１１中のエントリが一時的に無効化される。以下で説明するように、この無効化は不活性化タイマを現時点よりも後に設定することで生じる。エントリ内の様々なデータ項目もまた更新される。エントリが無効化された回数をカウントするdisable_cntがインクリメントされ、エントリが再有効化されるべき時間を示すeb_timerが現時点に対して無効化期間eb_timer_interval・ｅdisable_cntを加えた時間に設定される。ここで、eb_timer_intervalは一定時間であり、ｅは自然対数の底(2.718..)である。統計的処理ステップ１５８が用いられる場合、障害回数failure_cntはゼロにリセットされる。
【００４４】
ステップ１６６で、無効化期間が閾値EB_INTERVAL_MAXと照合される。無効化期間が閾値より大きい場合、ステップ１６８で、リスト１１内のその隣接エントリは削除される。これは、ネットワークノード２と、関連する隣接ネットワークノード３との間のリンクが破棄されたことに他ならないため、もはやそのリンクを通じてデータが送信されることはない。そして、方法は図３に復帰する。
【００４５】
無効化期間が閾値未満なら、方法は単純に図３の方法に復帰する。
【００４６】
図４に示す障害時処理方法の結果がどうであれ、この方法が１回完了するごとに、図３に示す方法はステップ１１２に進む。ここで、ルーティングプロセッサ１２は、ルーティングテーブルを更新しなくてはならないことをルーティング通知インタフェース（ＲＮＩ）に通知される。ルーティングテーブルは、図４により詳細に示すようにして再計算される。
【００４７】
ステップ１８０で、現在のルーティングテーブル１３が空にされ、ステップ１８２でリスト１１からの隣接ノードに対するエントリがルーティングテーブルに追加される。従って、ステップ１６８で削除された隣接ノードなしで更新される。
【００４８】
ステップ１８４で方法は、ルーティングテーブル内の各エントリに対して開始され、ステップ１８６で、現在判別しているエントリがテーブルの終わりを示すマーカNULLかどうかが判別される。もしそうであれば、ルーティングテーブルは全ての適切な隣接ノード３に対するルートを有しており、従って、適切なアルゴリズムを用いて非隣接ノード４へのルートを決定する（ステップ１８８）ために、ルーティングアルゴリズムを用いることができる。
【００４９】
さもなければ、方法はステップ１９０に進み、ここで方法はタイムアウトタイマ(timeout timer)が現在の隣接ノードについて満了しているかどうかを判別する。タイムアウトタイマはHELLOメッセージ又はデータパケット確認応答が隣接ノードから受信されてからの時間を示し、関連リンク５が有効であることのバックアップチェックの機能を果たす。タイムアウトタイマが満了していれば、ステップ１９２でそのノードが隣接リスト１１から削除され、またルーティングテーブルに追加もされずに、方法はルーティングテーブル内の次のエントリに移行する。
【００５０】
さもなければ、ステップ１９４でルーティングプロセッサは、時刻eb_timerが現時刻を過ぎているかどうかを判別し、もし過ぎていればノードが無効化され、従ってルーティングテーブルに追加されない。そのため、無効化されたノードは直接送信されているデータから無効化され、それらはeb_timerで与えられる時間が経過したかどうかに基づいてルーティングテーブルから除外される。そして方法はルーティングテーブル内の次のエントリに進む。
【００５１】
eb_timerを過ぎれば、隣接リスト内のエントリは無効化されなくなり、最初のホップとして利用可能となる（すなわち、そのエントリは依然として隣接ノード３に関連している）。従って、ステップ１９６で、エントリはルーティングテーブル内で、隣接ノードに直接到達可能であることを示すようになる。
【００５２】
ルーティングテーブルの再計算が終わると、データパケットを再送信すべきかどうかを判別可能となる（図３、ステップ１１４）。そのパケットが最後に送信されてからルーティングテーブルが変更されているかもしれないことを考えれば、代替ルートを用いた方が成功する可能性が高いであろう。各パケットは、最大でMAX_REFWD_TIMEを上限とした回数、ルーティング参照ステップ（ステップ１０２）に戻される。再送信が試行された回数を、パケットのヘッダに記録することができる。回数が超過した場合、パケットは破棄される。
【００５３】
ネットワークノードが上述のステップ１０８でパケットが正しく送信されたと判別した場合、隣接ノード３へのリンクは機能している。従って、ステップ１１６でタイムアウトタイマは現在の時刻に所定間隔nb_timer_interval加えた時刻にリセットされ、リンクが無効化された回数を表す変数disable_cntはゼロに設定される。そして、ネットワークノード２は次のパケットを待つ。
【特許請求の範囲】
【請求項１】
他の複数のネットワークノードと接続可能な少なくとも１つのネットワークインタフェースを有するネットワークノードであって、前記少なくとも１つのネットワークインタフェースを通じて前記他の複数のネットワークノードへの複数のネットワークリンクを形成するように構成され、前記複数のネットワークリンクの各々は前記他の複数のネットワークノードのうち隣接するものの１つへのリンクであり、前記ネットワークノードは前記ネットワークリンクを通じて関連する隣接ネットワークノードに送信されるデータが正しく受信されたかどうかを判別するように構成され、
前記ネットワークノードは、前記複数のネットワークリンクの各々について、各ネットワークリンクが接続されている隣接ネットワークノードのＩＤに関するデータを有するエントリを、使用時に記録するように構成されたメモリを有し、前記ネットワークノードは前記メモリ内の前記エントリに応じて前記他の複数のネットワークノードへデータを送信するように構成され、
前記ネットワークノードは、所与のネットワークリンクを通じて隣接ノードに送信されたデータが正しく受信されていないという最初の判別をした場合には、前記ネットワークノードが該隣接ノードに該所与のネットワークリンクを通じて所定期間データを送信しないよう、前記メモリ内の該ネットワークリンクについてのエントリを前記所定期間一時的に無効化し、前記所定期間の経過後は、前記ネットワークノードが該隣接ノードに該所与のネットワークリンクを通じてデータを送信できるように該エントリを再有効化するように構成され、
前記ネットワークノードは、該所与のネットワークリンクを通じて該隣接ネットワークノードへ送信されたデータが正しく受信されていないとの判別をさらにした場合には、前記ネットワークノードがもはや該隣接ネットワークノードを隣接ネットワークノードとして取り扱わず、該所与のネットワークリンクを通じてそれ以上データを送信しないように、該エントリを前記メモリから削除するように構成されることを特徴とするネットワークノード。
【請求項２】
前記ネットワークノードは、前記最初の判別と前記さらなる判別の間に、所与のネットワークリンクを通じて隣接ノードに送信されたデータが正しく受信されていないとの中間判別が少なくとも１回なされると、所定期間中は前記ネットワークノードが該所与のネットワークリンクを通じて前記隣接ノードへデータを送信しないよう、前記メモリ内の前記ネットワークリンクについての前記エントリを前記所定期間一時的に無効化し、前記所定期間の経過後は、前記ネットワークノードが前記所与のネットワークリンクを通じて前記隣接ノードにデータを送信することができるように前記エントリを再有効化する、ように構成されることを特徴とする請求項１記載のネットワークノード。
【請求項３】
前記最初の判別時と前記中間判別時とでは、エントリが無効化される所定期間が異なることを特徴とする請求項２記載のネットワークノード。
【請求項４】
前記所与のネットワークリンクを通じて隣接ノードに送信されたデータが正しく受信されていないとの判別が連続してなされるごとに前記所定期間が増加することを特徴とする請求項３記載のネットワークノード。
【請求項５】
前記所与のネットワークリンクを通じて隣接ノードに送信されたデータが正しく受信されていないとの判別が連続してなされるごとに前記所定期間が指数関数的に増加することを特徴とする請求項４記載のネットワークノード。
【請求項６】
前記最初の判別がなされてからの、所与のネットワークリンクを通じて隣接ノードに送信されたデータが正しくされたかどうかの判別を、前記所定期間が閾値に達するごとに１回実行することを特徴とする請求項３乃至請求項５のいずれか１項に記載のネットワークノード。
【請求項７】
データが繰り返し正しく受信されない場合にのみ、所与のネットワークリンクを通じて隣接ノードに送信されたデータが正しく受信されているかどうかの判別を行うように構成されることを特徴とする請求項１乃至請求項６のいずれか１項に記載のネットワークノード。
【請求項８】
前記ネットワークノードはさらに障害カウンタを有し、データが正しく受信されない度に前記障害カウンタを増加させるとともに、前記障害カウンタが閾値に達した際に前記判別を行うように構成されることを特徴とする請求項７記載のネットワークノード。
【請求項９】
前記少なくとも１つのネットワークインタフェースの少なくとも１つは無線ネットワークインタフェースであることを特徴とする請求項１乃至請求項８のいずれか１項に記載のネットワークノード。
【請求項１０】
前記ネットワークノードが、ネットワーク内の前記他の複数のネットワークノードにどのようにデータを送信するかを決定するために、前記ネットワークノードの使用時にルーティングテーブルを格納するためのメモリと、エントリの判別又は再有効化の度に前記ルーティングテーブルを更新するように構成されたルーティングプロセッサとを有することを特徴とする請求項１乃至請求項９のいずれか１項に記載のネットワークノード。
【請求項１１】
前記ネットワークノードは、前記所与のネットワークリンクを通じて隣接ノードに送信されたデータが正しく受信されていないとの判別を行うと、該判別後に更新される前記ルーティングテーブルに基づいて、該データを別のネットワークリンクを通じて再送するように構成されることを特徴とする請求項１乃至請求項１０のいずれか１項に記載のネットワークノード。
【請求項１２】
前記ネットワークノードは、データの各パケットを予め定められた最大回数まで再送するように構成されることを特徴とする請求項１１記載のネットワークノード。
【請求項１３】
請求項１乃至請求項１２のいずれか１項に記載のネットワークノードを複数有するネットワーク。
【請求項１４】
他の複数のネットワークノードを有するネットワークにおけるネットワークノードの動作方法であって、
前記ネットワークノードのネットワークインタフェースを通じて他の複数のネットワークノードへの複数のネットワークリンクであって、各々が前記他の複数のネットワークノードの１つへのリンクである複数のネットワークリンクを形成するステップと、
前記ネットワークノードが、前記複数のネットワークリンクの各々について、各ネットワークリンクが接続されている隣接ネットワークノードのＩＤに関するデータを有するエントリを保存するステップと、
前記複数のエントリを用い、前記複数のネットワークリンクを通じてデータを送信するステップと、
前記複数のネットワークリンクを通じて送信されたデータが正しく受信されたか判別するステップと、所与のネットワークリンクを通じて隣接ノードに送信されたデータが正しく受信されていないという最初の判別に応じて、前記ネットワークノードが該隣接ノードに該所与のネットワークリンクを通じて所定期間データを送信しないよう、該ネットワークリンクについてのエントリを前記所定期間一時的に無効化し、前記所定期間の経過後は、前記ネットワークノードが該隣接ノードに該所与のネットワークリンクを通じてデータを送信できるように該エントリを再有効化するステップと、
該所与のネットワークリンクを通じて該隣接ネットワークノードへ送信されたデータが正しく受信されていないとのさらなる判別に応じて、前記ネットワークノードがもはや該隣接ネットワークノードを隣接ネットワークノードとして取り扱わず、該所与のネットワークリンクを通じてそれ以上データを送信しないように、該エントリを削除するステップと、を有することを特徴とする方法。
【請求項１５】
前記方法は、前記最初の判別と前記さらなる判別の間に、所与のネットワークリンクを通じて隣接ノードに送信されたデータが正しく受信されていないとの中間判別が少なくとも１回なされると、所定期間中は前記ネットワークノードが該所与のネットワークリンクを通じて前記隣接ノードへデータを送信しないよう、前記メモリ内の前記ネットワークリンクについての前記エントリを前記所定期間一時的に無効化し、前記所定期間の経過後は、前記ネットワークノードが前記所与のネットワークリンクを通じて前記隣接ノードにデータを送信することができるように前記エントリを再有効化するステップを有することを特徴とする請求項１４記載の方法。
【請求項１６】
前記最初の判別時と前記中間判別時とでは、エントリが無効化される所定期間が異なることを特徴とする請求項１５記載の方法。
【請求項１７】
前記所与のネットワークリンクを通じて隣接ノードに送信されたデータが正しく受信されていないとの判別が連続してなされるごとに前記所定期間が指数関数的に増加することを特徴とする請求項１６記載の方法。
【請求項１８】
前記最初の判別がなされてからの、所与のネットワークリンクを通じて隣接ノードに送信されたデータが正しくされたかどうかの判別を、前記所定期間が閾値に達するごとに１回実行することを特徴とする請求項１６又は請求項１７に記載の方法。
【請求項１９】
データが繰り返し正しく受信されない場合にのみ、所与のネットワークリンクを通じて隣接ノードに送信されたデータが正しく受信されているかどうかの判別が行われることを特徴とする請求項１４乃至請求項１８のいずれか１項に記載の方法。
【請求項２０】
前記方法が、ルーティングテーブルを格納するステップと、ネットワーク内の前記他の複数のネットワークノードにどのようにデータを送信するかを決定するために前記ルーティングテーブルを用いるステップと、エントリの判別又は再有効化の度に前記ルーティングテーブルを更新するステップとを有することを特徴とする請求項１４乃至請求項１９のいずれか１項に記載の方法。
【請求項２１】
前記方法が、前記所与のネットワークリンクを通じて隣接ノードに送信されたデータが正しく受信されていないとの判別に応じて、該データを別のネットワークリンクを通じて再送するステップを有することを特徴とする請求項１４乃至請求項２０のいずれか１項に記載の方法。
【請求項２２】
前記方法が、所与のデータパケットに対し、予め定められた最大回数まで再送を行うステップを有することを特徴とする請求項２１記載の方法。
【請求項１】
他の複数のネットワークノードと接続可能な少なくとも１つのネットワークインタフェースを有するネットワークノードであって、前記少なくとも１つのネットワークインタフェースを通じて前記他の複数のネットワークノードへの複数のネットワークリンクを形成するように構成され、前記複数のネットワークリンクの各々は前記他の複数のネットワークノードのうち隣接するものの１つへのリンクであり、前記ネットワークノードは前記ネットワークリンクを通じて関連する隣接ネットワークノードに送信されるデータが正しく受信されたかどうかを判別するように構成され、
前記ネットワークノードは、前記複数のネットワークリンクの各々について、各ネットワークリンクが接続されている隣接ネットワークノードのＩＤに関するデータを有するエントリを、使用時に記録するように構成されたメモリを有し、前記ネットワークノードは前記メモリ内の前記エントリに応じて前記他の複数のネットワークノードへデータを送信するように構成され、
前記ネットワークノードは、所与のネットワークリンクを通じて隣接ノードに送信されたデータが正しく受信されていないという最初の判別をした場合には、前記ネットワークノードが該隣接ノードに該所与のネットワークリンクを通じて所定期間データを送信しないよう、前記メモリ内の該ネットワークリンクについてのエントリを前記所定期間一時的に無効化し、前記所定期間の経過後は、前記ネットワークノードが該隣接ノードに該所与のネットワークリンクを通じてデータを送信できるように該エントリを再有効化するように構成され、
前記ネットワークノードは、該所与のネットワークリンクを通じて該隣接ネットワークノードへ送信されたデータが正しく受信されていないとの判別をさらにした場合には、前記ネットワークノードがもはや該隣接ネットワークノードを隣接ネットワークノードとして取り扱わず、該所与のネットワークリンクを通じてそれ以上データを送信しないように、該エントリを前記メモリから削除するように構成されることを特徴とするネットワークノード。
【請求項２】
前記ネットワークノードは、前記最初の判別と前記さらなる判別の間に、所与のネットワークリンクを通じて隣接ノードに送信されたデータが正しく受信されていないとの中間判別が少なくとも１回なされると、所定期間中は前記ネットワークノードが該所与のネットワークリンクを通じて前記隣接ノードへデータを送信しないよう、前記メモリ内の前記ネットワークリンクについての前記エントリを前記所定期間一時的に無効化し、前記所定期間の経過後は、前記ネットワークノードが前記所与のネットワークリンクを通じて前記隣接ノードにデータを送信することができるように前記エントリを再有効化する、ように構成されることを特徴とする請求項１記載のネットワークノード。
【請求項３】
前記最初の判別時と前記中間判別時とでは、エントリが無効化される所定期間が異なることを特徴とする請求項２記載のネットワークノード。
【請求項４】
前記所与のネットワークリンクを通じて隣接ノードに送信されたデータが正しく受信されていないとの判別が連続してなされるごとに前記所定期間が増加することを特徴とする請求項３記載のネットワークノード。
【請求項５】
前記所与のネットワークリンクを通じて隣接ノードに送信されたデータが正しく受信されていないとの判別が連続してなされるごとに前記所定期間が指数関数的に増加することを特徴とする請求項４記載のネットワークノード。
【請求項６】
前記最初の判別がなされてからの、所与のネットワークリンクを通じて隣接ノードに送信されたデータが正しくされたかどうかの判別を、前記所定期間が閾値に達するごとに１回実行することを特徴とする請求項３乃至請求項５のいずれか１項に記載のネットワークノード。
【請求項７】
データが繰り返し正しく受信されない場合にのみ、所与のネットワークリンクを通じて隣接ノードに送信されたデータが正しく受信されているかどうかの判別を行うように構成されることを特徴とする請求項１乃至請求項６のいずれか１項に記載のネットワークノード。
【請求項８】
前記ネットワークノードはさらに障害カウンタを有し、データが正しく受信されない度に前記障害カウンタを増加させるとともに、前記障害カウンタが閾値に達した際に前記判別を行うように構成されることを特徴とする請求項７記載のネットワークノード。
【請求項９】
前記少なくとも１つのネットワークインタフェースの少なくとも１つは無線ネットワークインタフェースであることを特徴とする請求項１乃至請求項８のいずれか１項に記載のネットワークノード。
【請求項１０】
前記ネットワークノードが、ネットワーク内の前記他の複数のネットワークノードにどのようにデータを送信するかを決定するために、前記ネットワークノードの使用時にルーティングテーブルを格納するためのメモリと、エントリの判別又は再有効化の度に前記ルーティングテーブルを更新するように構成されたルーティングプロセッサとを有することを特徴とする請求項１乃至請求項９のいずれか１項に記載のネットワークノード。
【請求項１１】
前記ネットワークノードは、前記所与のネットワークリンクを通じて隣接ノードに送信されたデータが正しく受信されていないとの判別を行うと、該判別後に更新される前記ルーティングテーブルに基づいて、該データを別のネットワークリンクを通じて再送するように構成されることを特徴とする請求項１乃至請求項１０のいずれか１項に記載のネットワークノード。
【請求項１２】
前記ネットワークノードは、データの各パケットを予め定められた最大回数まで再送するように構成されることを特徴とする請求項１１記載のネットワークノード。
【請求項１３】
請求項１乃至請求項１２のいずれか１項に記載のネットワークノードを複数有するネットワーク。
【請求項１４】
他の複数のネットワークノードを有するネットワークにおけるネットワークノードの動作方法であって、
前記ネットワークノードのネットワークインタフェースを通じて他の複数のネットワークノードへの複数のネットワークリンクであって、各々が前記他の複数のネットワークノードの１つへのリンクである複数のネットワークリンクを形成するステップと、
前記ネットワークノードが、前記複数のネットワークリンクの各々について、各ネットワークリンクが接続されている隣接ネットワークノードのＩＤに関するデータを有するエントリを保存するステップと、
前記複数のエントリを用い、前記複数のネットワークリンクを通じてデータを送信するステップと、
前記複数のネットワークリンクを通じて送信されたデータが正しく受信されたか判別するステップと、所与のネットワークリンクを通じて隣接ノードに送信されたデータが正しく受信されていないという最初の判別に応じて、前記ネットワークノードが該隣接ノードに該所与のネットワークリンクを通じて所定期間データを送信しないよう、該ネットワークリンクについてのエントリを前記所定期間一時的に無効化し、前記所定期間の経過後は、前記ネットワークノードが該隣接ノードに該所与のネットワークリンクを通じてデータを送信できるように該エントリを再有効化するステップと、
該所与のネットワークリンクを通じて該隣接ネットワークノードへ送信されたデータが正しく受信されていないとのさらなる判別に応じて、前記ネットワークノードがもはや該隣接ネットワークノードを隣接ネットワークノードとして取り扱わず、該所与のネットワークリンクを通じてそれ以上データを送信しないように、該エントリを削除するステップと、を有することを特徴とする方法。
【請求項１５】
前記方法は、前記最初の判別と前記さらなる判別の間に、所与のネットワークリンクを通じて隣接ノードに送信されたデータが正しく受信されていないとの中間判別が少なくとも１回なされると、所定期間中は前記ネットワークノードが該所与のネットワークリンクを通じて前記隣接ノードへデータを送信しないよう、前記メモリ内の前記ネットワークリンクについての前記エントリを前記所定期間一時的に無効化し、前記所定期間の経過後は、前記ネットワークノードが前記所与のネットワークリンクを通じて前記隣接ノードにデータを送信することができるように前記エントリを再有効化するステップを有することを特徴とする請求項１４記載の方法。
【請求項１６】
前記最初の判別時と前記中間判別時とでは、エントリが無効化される所定期間が異なることを特徴とする請求項１５記載の方法。
【請求項１７】
前記所与のネットワークリンクを通じて隣接ノードに送信されたデータが正しく受信されていないとの判別が連続してなされるごとに前記所定期間が指数関数的に増加することを特徴とする請求項１６記載の方法。
【請求項１８】
前記最初の判別がなされてからの、所与のネットワークリンクを通じて隣接ノードに送信されたデータが正しくされたかどうかの判別を、前記所定期間が閾値に達するごとに１回実行することを特徴とする請求項１６又は請求項１７に記載の方法。
【請求項１９】
データが繰り返し正しく受信されない場合にのみ、所与のネットワークリンクを通じて隣接ノードに送信されたデータが正しく受信されているかどうかの判別が行われることを特徴とする請求項１４乃至請求項１８のいずれか１項に記載の方法。
【請求項２０】
前記方法が、ルーティングテーブルを格納するステップと、ネットワーク内の前記他の複数のネットワークノードにどのようにデータを送信するかを決定するために前記ルーティングテーブルを用いるステップと、エントリの判別又は再有効化の度に前記ルーティングテーブルを更新するステップとを有することを特徴とする請求項１４乃至請求項１９のいずれか１項に記載の方法。
【請求項２１】
前記方法が、前記所与のネットワークリンクを通じて隣接ノードに送信されたデータが正しく受信されていないとの判別に応じて、該データを別のネットワークリンクを通じて再送するステップを有することを特徴とする請求項１４乃至請求項２０のいずれか１項に記載の方法。
【請求項２２】
前記方法が、所与のデータパケットに対し、予め定められた最大回数まで再送を行うステップを有することを特徴とする請求項２１記載の方法。
【図２】
【図３】
【図４】
【図５】
【図１】
【図３】
【図４】
【図５】
【図１】
【公表番号】特表２０１２−５０６１７９（Ｐ２０１２−５０６１７９Ａ）
【公表日】平成２４年３月８日（２０１２．３．８）
【国際特許分類】
【出願番号】特願２０１１−５３１３６５（Ｐ２０１１−５３１３６５）
【出願日】平成２０年１０月１６日（２００８．１０．１６）
【国際出願番号】ＰＣＴ／ＥＰ２００８／０６４０００
【国際公開番号】ＷＯ２０１０／０４３２６５
【国際公開日】平成２２年４月２２日（２０１０．４．２２）
【出願人】（５９８０３６３００）テレフオンアクチーボラゲット エル エム エリクソン（パブル） (2,266)
【Ｆターム（参考）】
【公表日】平成２４年３月８日（２０１２．３．８）
【国際特許分類】
【出願日】平成２０年１０月１６日（２００８．１０．１６）
【国際出願番号】ＰＣＴ／ＥＰ２００８／０６４０００
【国際公開番号】ＷＯ２０１０／０４３２６５
【国際公開日】平成２２年４月２２日（２０１０．４．２２）
【出願人】（５９８０３６３００）テレフオンアクチーボラゲット エル エム エリクソン（パブル） (2,266)
【Ｆターム（参考）】
[ Back to top ]