(57)【要約】【課題】アドホックネットワークにおいて、パケット転送処理時に発生するカーネル空間とユーザ空間とのやり取りを抑える移動通信装置を提供する。【解決手段】移動通信装置１は、経路情報を持つ経路テーブルＲＴを備える。ノードＮ１からノードＮ２宛のパケットを受けたとき（１）、カーネル空間２０内の経路判断部２２は、経路テーブルＲＴにノードＮ２宛の経路情報があるか否かを判断する（２）。経路情報がある場合、カーネル空間２０はパケットをノードＮ２へ送信する（３）。経路情報がない場合、ユーザ空間１０に経路探索を要求する。カーネル空間２０は、探索された経路情報を受けた後、パケットをノードＮ２へ送信する。以上の動作により、経路テーブルＲＴ内に経路情報がない場合のみ、カーネル空間２０とユーザ空間１０とでやり取りが発生する。【選択図】図４
2005260299.tif 000002
【特許請求の範囲】
【請求項１】
アドホックネットワークに接続可能であり、カーネル空間とユーザ空間とを有する移動通信装置であって、
前記カーネル空間は、
宛先アドレスと前記宛先アドレスに対応した経路とを含む経路情報を登録するための経路テーブルと、
宛先アドレスを有するパケットを受信する受信手段と、
前記受信手段が受信したパケットの宛先アドレスに対応した経路を前記経路テーブルから検索する経路テーブル検索手段と、
前記経路テーブル検索手段が前記経路を経路テーブルから検索できないときに経路探索要求を出力する要求手段とを備え、
前記ユーザ空間は、
前記経路探索要求を受け、オンデマンド型のルーティングプロトコルに基づいて前記経路を探索する経路探索手段を備え、
前記カーネル空間はさらに、
前記経路探索手段が探索した経路を含む経路情報を前記経路テーブルに登録する登録手段を備えたことを特徴とする移動通信装置。
【請求項２】
請求項１に記載の移動通信装置であってさらに、
前記経路情報を登録するための転送テーブルを備え、
前記登録手段は、前記経路探索手段が探索した経路を含む経路情報を前記転送テーブルに登録し、
前記移動通信装置はさらに、
前記受信手段が受信したパケットの宛先アドレスに対応した経路を前記転送テーブルから検索する転送テーブル検索手段と、
前記転送テーブル検索手段が検索した経路に前記パケットを送信するパケット送信手段とを備えたことを特徴とする移動通信装置。
【請求項３】
請求項２に記載の移動通信装置であって、
前記経路テーブル検索手段は、前記経路を経路テーブルから検索できたとき、検索した経路に対応したタイムスタンプを前記経路テーブルに登録し、
前記登録手段は、前記経路テーブルに前記経路情報を登録したとき、登録した経路情報に対応したタイムスタンプを前記経路テーブルに登録し、
前記移動通信装置はさらに、
前記経路情報に対応したタイムスタンプから所定期間が経過した経路情報を削除するテーブル更新手段を備えたことを特徴とする移動通信装置。
【請求項４】
請求項２に記載の移動通信装置であって、
前記経路探索手段は所定期間毎にメッセージをブロードキャストし、
前記ユーザ空間はさらに、
前記メッセージに対応した、経路情報を含む応答メッセージを受け、前記経路情報を前記カーネル空間に送信する手段を備え、
前記テーブル更新手段はさらに、前記送信された経路情報に基づいて、前記経路テーブル及び転送テーブルを更新することを特徴とする移動通信装置。
【請求項５】
請求項１〜４のいずれか１項に記載の手段をコンピュータに実現させるための移動通信プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、移動通信装置に関し、さらに詳しくは、アドホックネットワークに接続可能な移動通信装置に関する。
【背景技術】
【０００２】
近年、アドホックネットワーク技術の研究が企業や大学等で進められている。アドホックネットワークは、パソコンやＰＤＡや携帯電話といった複数の移動通信装置により自律的に構築される。
【０００３】
図１５を参照して、ノードＮ１１〜Ｎ１５は、移動通信装置である。エリア１１１はノードＮ１の無線到達範囲を示す。ノードＮ１１はエリア１１１内のノードＮ１２及びＮ１３と無線リンクで直接接続される。
【０００４】
さらに、ノードＮ１１はノードＮ１４及びＮ１５とマルチホップで通信できる。ノードＮ１４はエリア１１１内にはないが、ノードＮ１３のエリア１１３内にある。そのため、ノードＮ１３がノードＮ１１から送信されたパケットをノードＮ１４に中継する。同様に、ノードＮ１５はノードＮ１４のエリア１１４内にあるため、ノードＮ１３及びＮ１４がノードＮ１１のパケットをノードＮ１５へ中継する。各ノードが中継局として機能するため、アクセスポイントや基地局の設置が不要で、容易にネットワークが構築される。
【０００５】
アドホックネットワーク内のノードは自由に移動するため、ネットワークトポロジが動的に変化する。たとえばノードＮ１６がエリア１１１内に移動した場合、ノードＮ１１はノードＮ１６と通信できる。また、ノードＮ１３がエリア１１１外へ移動した場合、ノードＮ１１はノードＮ１３を中継局としてノードＮ１４及びノードＮ１５にパケットを送信できない。
【０００６】
ところで、複数の固定ノードで構成される従来の有線ネットワークでは、パケットを他のノードに送信するとき、ノード内のカーネル空間がパケット転送処理を実行する。一般的に、ノードに汎用オペレーティングシステムをインストールすることにより、パケット転送処理を実行できる。
【０００７】
図１６を参照して、ノードＮ２０がノードＮ２１にパケットを送信する場合のパケット転送処理を説明する。ノードＮ２１はノードＮ２０と同じサブネット内の隣接ノード（ＯＳＩ参照モデル第２層レベルで直接通信可能なノード）である。ノードＮ２０内のカーネル空間が転送テーブルＦＴからノードＮ２１の属するネットワークエントリを検索する。カーネル空間は検索したネットワークエントリに基づいてパケットを送信する。
【０００８】
他のサブネットＳＢのノードＮ２２にパケットを送信する場合であって、転送テーブルＦＴにノードＮ２２への経路を示すエントリ（ネットワークエントリ又はホストエントリ）が存在するとき、カーネル空間は該当エントリ内の次ホップノード情報に基づいて、パケットを転送する。具体的には、次ホップノードであるゲートウェイＧＷ１にパケットを送信する。パケットはゲートウェイＧＷ１及び複数のノードを介してノードＮ２２に到達する。
【０００９】
有線のネットワークではネットワーク内のノードは固定されており、経路が変更されない。一度転送テーブルＦＴに登録された経路情報は長期間有効である。そのため、転送テーブルＦＴを参照すればパケットを転送できる。有線ネットワークでは、同一サブネット内の全てのノードへの経路情報は１つのネットワークエントリとして転送テーブルＦＴ内に管理される。
【００１０】
しかしながら、アドホックネットワーク内のノードは有線ネットワーク内のノードのパケット転送処理機能をそのまま適用できない。アドホックネットワークでは、ノードが自由に移動し、トポロジが動的に変化する。そのため、同一サブネット内の全てのノードへの経路情報は、ノードごとのホストエントリとして転送テーブルＦＴ内に登録する必要がある。以下、詳細を説明する。
【００１１】
アドホックネットワークでは、ある時刻で隣接ノードが移動した結果、次時刻では隣接ノードでは無くなる場合がある（たとえば図１５中のノードＮ１に対するノードＮ１３）。また、ある時刻に隣接ノードではなかったノードが自ノードへ接近することで次時刻に隣接ノードになる場合がある（たとえば図１５中のノードＮ１に対するノードＮ１６）。さらに、無線リンク状態の変化により隣接ノードが変化する。このようなトポロジの動的な変化により、アドホックネットワークでは、サブネット内の他ノードへＯＳＩ参照モデル第２層レベルで直接通信が可能な場合と、中継ノード経由で通信が可能となる場合とが混在する。後者の場合、大規模なアドホックネットワークではＯＳＩ参照モデル第３層レベルでルーティングを行う必要がある。
【００１２】
ＯＳＩ参照モデル第３層レベルでルーティングを行う場合、サブネット内の全てのノードへの経路情報はノードごとにホストエントリとしてＦＴに登録される必要が生じる。上述したとおり、有線ネットワークでは同一サブネット内の全てのノードへの経路情報は一つのネットワークエントリとしてＦＴ内で管理されており、アドホックネットワーク内のノードへの経路情報管理を実現する為には有線ネットワークの場合とは異なる、即ち既存の仕組みとは異なる仕組みが必要となる。
【００１３】
さらにアドホックネットワークでは各ノードへの経路が頻繁に変更されるため、一度転送テーブルＦＴに登録された経路情報（ホストエントリ）が短い時間の後に無効となるケースが多発する。そのため、各ノードは転送テーブルＦＴ内に宛先ノードへのホストエントリが存在しない場合に経路探索処理（ルーティング）を実行する必要がある。つまり、アドホックネットワークでは、この経路探索処理機能に対応したパケット転送処理機能を持つ必要がある。
【００１４】
アドホックネットワークに対応した経路探索処理として、ＡＯＤＶ（Ad hoc On-Demand Distance Vector Routing）に代表されるオンデマンド型のルーティングプロトコルが提供されている。このオンデマンド型のルーティングプロトコルに対応したパケット転送処理については、下記（１）及び（２）が報告されている。
【００１５】
（１）経路探索処理機能をユーザ空間に実装し、経路判断については全てユーザ空間で行う。具体的には、カーネル空間でのパケット転送処理中に、カーネル空間は、送信するパケットの情報をユーザ空間に送る。ユーザ空間は受けたパケットの情報に基づいて経路を決定し、カーネル空間に報告する。カーネル空間は決定された経路を受け、パケットを転送する（下記非特許文献１参照）。
【００１６】
（２）アドホックネットワークを構成するノードに関する経路情報の全てを事前にカーネル転送テーブルに登録する。カーネル転送テーブルに経路情報のないパケットについては、ユーザ空間で経路を判断する。経路探索処理機能はユーザ空間に実装する（下記非特許文献２参照）。
【００１７】
しかしながら、（１），（２）いずれの方法も、パケット転送処理時のスループットが問題となる。具体的には、（１）では、パケットを転送するとき必ずカーネル空間とユーザ空間とでやり取りが発生する。カーネル空間とユーザ空間とのやり取りが多ければ、それだけスループットは低下する。（２）は、アドホックネットワークを構成する全てのノードのホストエントリを転送テーブルＦＴに登録する必要がある。そのため、ネットワークに参加するノードが不特定の場合に対応が困難となる。
【００１８】
さらに、アドホックネットワークに対応したパケット転送処理機能を実現するために、汎用ＯＳのカーネルコードを大幅に変更するのも好ましくない。汎用ＯＳは既に多くの移動通信装置に実装されている。よって、汎用ＯＳのカーネルコードを直接変更する場合、移動通信装置は既存の汎用ＯＳをアンインストールし、カーネルソースコードを変更しカーネルを再構築した後、再インストールしなければならない。
【００１９】
【非特許文献１】アドホック・オンデマンド・ディスタンス・ベクトル・ルーティング（Ad-hoc On-demand Distance Vector Routing）、［online］、［平成１６年２月２４日検索］、インターネット<URL: http://user.it.uu.se/~henrikl/aodv/>
【非特許文献２】ビカス・カワディア（Vikas Kawadia）外２名、「アドホックルーティングを実行するためのシステムサービス（System Services for Implementing Ad-Hoc Routing: Architecture, Implementation and Experiences）」、［online］、［平成１６年２月２４日検索］、インターネット<URL:http://black.csl.uiuc.edu/~kawadia/research.html>
【発明の開示】
【発明が解決しようとする課題】
【００２０】
本発明の目的は、パケット転送処理時に発生するカーネル空間とユーザ空間とのやり取りを抑制することでパケット転送時に発生する負荷ならびに処理遅延を軽減し、高いスループット性能を実現する移動通信装置及び移動通信プログラムを提供することである。
【００２１】
本発明の他の目的は、既存の汎用ＯＳのカーネルコードをほぼ変更せずに、アドホックネットワークでパケット転送処理時に発生するカーネル空間とユーザ空間とのやり取りを抑えることができる移動通信装置及び移動通信プログラムを提供することである。
【課題を解決するための手段及び発明の効果】
【００２２】
本発明による移動通信装置は、アドホックネットワークに接続可能であり、カーネル空間とユーザ空間とを有する移動通信装置であって、カーネル空間は、経路テーブルと、受信手段と、経路テーブル検索手段と、要求手段とを備える。経路テーブルは、宛先アドレスと宛先アドレスに対応した経路とを含む経路情報を登録するためのものである。受信手段は、宛先アドレスを有するパケットを受信する。経路テーブル検索手段は、受信手段が受信したパケットの宛先アドレスに対応した経路を経路テーブルから検索する。要求手段は、経路テーブル検索手段が経路を経路テーブルから検索できないときに経路探索要求を出力する。ユーザ空間は、経路探索手段を備える。経路探索手段は、経路探索要求を受け、オンデマンド型のルーティングプロトコルに基づいて経路を探索する。カーネル空間はさらに、登録手段を備える。登録手段は、経路探索手段が探索した経路を含む経路情報を経路テーブルに登録する。
【００２３】
本発明による移動通信装置は、受信したパケットの宛先アドレスに対応した経路を経路テーブルから検索できなかったときに経路探索を実行する。すなわち、経路を経路テーブルから検索できたときは、カーネル空間とユーザ空間との一切のやり取りが発生しない。その結果、高いスループットでパケット転送処理を実行できる。
【００２４】
好ましくは、移動通信装置はさらに、経路情報を登録するための転送テーブルを備える。また、登録手段は、経路探索手段が探索した経路を含む経路情報を転送テーブルに登録する。移動通信装置はさらに、転送テーブル検索手段と、パケット送信手段とを備える。転送テーブル検索手段は、受信手段が受信したパケットの宛先アドレスに対応した経路を転送テーブルから検索する。パケット送信手段は、転送テーブル検索手段が検索した経路にパケットを送信する。
【００２５】
汎用のオペレーションシステムを移動通信装置にインストールすることにより、転送テーブルと転送テーブル検索手段とパケット送信手段とが移動通信装置に実装される。本発明による移動通信装置は、経路探索手段により取得した経路情報を転送テーブルにも登録する。その結果、従来の汎用ＯＳのカーネルコードの標準のパケット転送機能を変更することなく、本発明で提供する上記の新規機能をモジュール等の独立した形式として追加することが可能となる。
【００２６】
好ましくは、経路テーブル検索手段は、経路を経路テーブルから検索できたとき、検索した経路に対応したタイムスタンプを経路テーブルに登録する。また、登録手段は、経路テーブルに経路情報を登録したとき、登録した経路情報に対応したタイムスタンプを経路テーブルに登録する。移動通信装置はさらに、テーブル更新手段を備える。テーブル更新手段は、経路情報に対応したタイムスタンプから所定期間が経過した経路情報を削除する。
【００２７】
この場合、移動通信装置は、経路テーブル内のタイムスタンプを参照し、所定期間を経過した古い経路情報を削除する。不要な経路情報を削除し、有効な経路情報のみを経路テーブル及び転送テーブルに登録する。
【００２８】
好ましくは、経路探索手段は所定期間毎にメッセージをブロードキャストする。ユーザ空間はさらに、メッセージに対応した、経路情報を含む応答メッセージを受け、経路情報をカーネル空間に送信する手段を備える。テーブル更新手段はさらに、送信された経路情報に基づいて、経路テーブル及び転送テーブルを更新する。
【００２９】
この場合、テーブル更新手段は、定期的に経路テーブル及び転送テーブルを更新する。その結果、経路テーブル及び転送テーブルは常に最新の経路情報を含む。そのため、パケット転送処理時におけるカーネル空間とユーザ空間とのやり取りを抑制でき、高いスループットでパケットを転送できる。
【発明を実施するための最良の形態】
【００３０】
以下、図面を参照し、本発明の実施の形態を詳しく説明する。図中同一又は相当部分には同一符号を付してその説明は繰り返さない。
【００３１】
１．アドホックネットワークの構成
初めに、本実施の形態による移動通信装置１を用いたアドホックサブネットワークの概念を説明する。図１を参照して、各ノードＮ１〜Ｎ７は移動通信装置１である。Ａｎ１〜Ａｎ７は各ノードのＩＰアドレスを示す。また、ノードＮ５の無線到達範囲１０５内にノードＮ１〜Ｎ４が存在する。本実施の形態による移動通信装置１を用いたアドホックネットワークでは、サブネットＳＢはネットワークに参加する全てのノードＮ１〜Ｎ７で構成されるものとする。なお、サブネットＳＢのＩＰアドレスをＡｓｂとする。
【００３２】
２．移動通信装置の構成
図２を参照して、図１中のノードＮ１（移動通信装置１）は、ユーザ空間１０とカーネル空間２０とを備える。カーネル空間２０は、送受信部２１Ａ及び２１Ｂと、経路判断部２２と、パケット転送部２３とを含む。送受信部２１Ａ及び２１Ｂはカーネル空間２０からユーザ空間１０及び外部とデータを送受信する。たとえば、ユーザ空間１０及び外部から宛先アドレスを有するパケットを受信する。送受信部２１Ａはたとえばソケットインタフェース経由でユーザ空間１０とデータを送受信する。
【００３３】
パケット転送部２３はパケット転送処理を実行する。パケット転送部２３は、転送テーブルＦＴ（Forwarding Table）と、転送テーブル検索部２３１と、パケット送信部２３２とを含む。転送テーブル検索部２３１は、パケットの経路を転送テーブルＦＴから検索する。転送テーブルＦＴを簡略的に表１に示す。転送テーブルＦＴのエントリは３つのフィールドを含む。なお、エントリはさらに他の複数のフィールドを含んでもよい。
【表１】
2005260299.tif 000003
【００３４】
宛先ＩＰアドレスは宛先のノード又は宛先のサブネットのＩＰアドレスである。ネットマスクは宛先ＩＰアドレスのサブネットマスクである。宛先アドレスが個別のノードを示す場合（すなわち、ホストエントリの場合）、ネットマスクには「２５５．２５５．２５５．２５５」が登録される。宛先ＩＰアドレスがサブネットを示す場合（すなわち、ネットワークエントリの場合）、対応するネットマスクとしてたとえば「２５５．２５５．２５５．０」等（クラスＣサブネットの場合）が登録される。表１のネットワークエントリ＝Ａｓｂのネットマスクがこれに該当する。
【００３５】
次ホップアドレスは宛先のノードまでの経路における隣接ノードのＩＰアドレスである。たとえば、宛先アドレスＡｎ３の次ホップアドレスはＡｎ５となっている。よって、ノードＮ１からノードＮ３へパケットを転送する場合、ノードＮ５を最初の中継局とする。
【００３６】
転送テーブル検索部２３１は、パケットに含まれる宛先ＩＰアドレスに対応した次ホップアドレスを検索する。パケット送信部２３２は、転送テーブル検索部２３１が検索した次ホップアドレスに基づいてパケットを送信する。パケット転送部２３が実行するパケット転送処理は、従来の有線ネットワークにおけるノードのパケット転送処理と同じである。
【００３７】
経路判断部２２は、パケット転送部２３がパケットを転送する前に、宛先アドレスがアドホックネットワークのサブネットに属する場合は、そのパケットの経路情報を確認する。カーネル空間２０内に経路情報がない場合、経路情報を取得して転送テーブルＦＴに登録する。宛先アドレスがアドホックネットワークのサブネットに属していない場合や、経路テーブルＲＴに宛先アドレスと一致するホストエントリが存在する場合、経路判断部２２は直ちにパケット転送部２３に制御を戻す。これらの場合、追加負荷はほとんど発生しない。経路判断部２２のサポートによりパケット転送部２３は宛先ノードがアドホックネットワーク内に存在する場合、外に存在する場合のいかんを問わずパケットを確実に転送でき、かつ、高いスループットを確保できる。
【００３８】
経路判断部２２は、経路テーブル（Routing Table）ＲＴと、経路テーブル検索部２２２と、要求部２２３と、登録部２２１とを含む。経路テーブルＲＴを表２に示す。
【表２】
2005260299.tif 000004
【００３９】
表２を参照して、経路テーブルＲＴは６つのフィールドを持つ。具体的には、フィールドとして、宛先ＩＰアドレス、ネットマスク、次ホップアドレス、インタフェースインデックス、ホップカウント、タイムスタンプを持つ。
【００４０】
経路テーブルＲＴの６つのフィールドのうち宛先ＩＰアドレスとサブネットマスクと次ホップアドレスとに登録されるホストエントリのデータは、転送テーブルＦＴ内の同じフィールドに登録されるデータと同じである。要するに、表１及び表２に示すように、転送テーブルＦＴ内のホストエントリの宛先ＩＰアドレスとサブネットマスクと次ホップアドレスは、経路テーブルＲＴ内のホストエントリのコピーである。なお、宛先ＩＰアドレスが「０．０．０．０」のエントリは、デフォルトルートである。デフォルトルートは、ノードＮ１がアドホックネットワーク経由で外部ネットワーク（有線ネットワーク等）に接続されている場合のみ存在する。表２（及び表１）の場合、ノードＮ１はノードＮ２（ＩＰアドレス＝Ａｎ２）を中継局として外部ネットワークと接続されている。
【００４１】
インタフェースインデックスには、移動通信装置１が持つ１又は複数の通信部１０３の識別子が登録される。たとえば、移動通信装置１が、通信部１０３として無線ＬＡＮとＢｌｕｅｔｏｏｔｈとを備える場合、無線ＬＡＮのインタフェースインデックスを「１」、Ｂｌｕｅｔｏｏｔｈのインタフェースインデックスを「２」とする。なお通信部１０３の識別子が汎用ＯＳで割り振られている場合、インタフェースインデックスにこの識別子の値を採用する。表２では、宛先アドレスがＡｎ６に対応したインタフェースインデックスが「２」となっている。この場合、ノードＮ１とノードＮ６とはＢｌｕｅｔｏｏｔｈで通信する。
【００４２】
ホップカウントには、宛先ＩＰアドレスに到るまでのホップ数が登録される。宛先ＩＰアドレスが隣接ノードである場合（たとえば宛先アドレス＝Ａｎ５）、ホップカウントには「１」が登録される。また、宛先ＩＰアドレスが隣接ノードの隣接ノードである場合（たとえば宛先アドレス＝Ａｎ２）、ホップカウントには「２」が登録される。タイムスタンプは対応する経路情報の有効期限を決定する目的等に利用される。経路情報が検索又は更新されたときにタイムスタンプは更新される。
【００４３】
送受信部２１Ａ又は２１Ｂがパケットを受けた場合であって、パケットの宛先アドレスがアドホックネットワークのサブネットに属しているとき、経路テーブル検索部２２２が、パケットの宛先ＩＰアドレスに対応した経路情報（ホストエントリ）を経路テーブルＲＴから検索する。検索の結果、経路テーブルＲＴに経路情報が存在しない場合、要求部２２３はユーザ空間１０に経路探索を要求する。経路テーブルＲＴに経路情報が登録されていない場合、転送テーブルＦＴにもその経路情報（次ホップアドレス）は登録されておらず、このままではパケット転送部２３はパケットを転送できないためである。
【００４４】
登録部２２１は、経路探索によりユーザ空間１０が取得した経路情報を経路テーブルＲＴ及び転送テーブルＦＴに登録する。
【００４５】
ユーザ空間１０は、アプリケーション１１と、経路探索部１２と、テーブル管理部１３とを含む。アプリケーション１１はたとえばメーラやウェブブラウザ等である。
【００４６】
経路探索部１２は、要求部２２３からの要求に応じて直ちに経路探索を実施し、経路情報を取得する。また、所定期間毎にＨｅｌｌｏメッセージをブロードキャストし、隣接ノードに関する最新の経路情報を得る。
【００４７】
テーブル管理部１３とカーネル空間２０内の登録部２２１とはテーブル更新部１３０を構成する。テーブル更新部１３０は経路テーブルＲＴ及び転送テーブルＦＴ（以下、これらをまとめてカーネル内テーブルと称する）の経路情報を管理し、不要となった経路情報を削除する。具体的には、テーブル管理部１３が経路情報の追加又は削除を決定し、登録部２２１が経路テーブルに対して経路情報を追加又は削除する。詳細は後述する。
【００４８】
図３は一般的な移動通信装置１００のハードウェア構成を示す。移動通信装置１００はＣＰＵ１０１とメモリ１０２と通信部１０３とハードディスク１０５とを備える。これらはバス１０４で相互に接続される。
【００４９】
ハードディスク１０５には、図２中のアプリケーションプログラム１１がインストールされる。また、ハードディスク１０５に汎用ＯＳをインストールし、メモリ１０２にロードされたプログラムに従ってＣＰＵ１０１が動作することにより、パケット転送部２３の機能が実現される。換言すれば、従来の移動通信装置１００に汎用ＯＳをインストールすれば、パケット転送部２３は移動通信装置１００のカーネル空間に実装される。
【００５０】
さらに、経路判断部２２を実現するためのカーネル空間モジュール（以下、追加モジュールと称する）と、経路探索部１２及びテーブル管理部１３を実現するためのユーザ空間プログラム（以下、ミドルウェアプログラムと称する）とを移動通信装置１００内のハードディスク１０５にインストールし、メモリ１０２にロードされたプログラムに従ってＣＰＵ１０１が動作することにより、経路判断部２２の機能と経路探索部１２の機能とテーブル管理部１３の機能とが実現される。
【００５１】
要するに、従来の汎用ＯＳがインストールされた移動通信装置１００に、追加モジュール及びミドルウェアプログラムをインストールすれば、その移動通信装置１００は本実施の形態による移動通信装置１になる。
【００５２】
３．動作概要
本実施の形態による移動通信装置１は、アドホックパケット転送処理とテーブル更新処理とを実行する。これらの処理により高いスループットでパケットを転送できる。
【００５３】
３．１．アドホックパケット転送処理
本実施の形態による移動通信装置１では、パケット転送部２３がパケット転送処理を実行する前に、経路判断部２２がパケットの経路情報を経路テーブルＲＴで確認する（以下、この処理を確認処理と称する）。つまり、アドホックパケット転送処理は、パケット転送処理と確認処理とを含む。
【００５４】
経路判断部２２が確認した結果、宛先アドレスがアドホックネットワークのサブネットに属していない場合、又は経路テーブルＲＴに宛先アドレスと一致するホストエントリが存在する場合、制御は経路判断部２２から直ちにパケット転送部２３に移る。すなわち、これらの場合、カーネル空間２０のみが動作し、パケットを転送する。一方、確認の結果、宛先アドレスがアドホックネットワークのサブネットに属し、かつ、経路テーブルＲＴ内に経路情報がない場合のみ、カーネル空間２０とユーザ空間１０とがやり取りした後、パケットを転送する。
【００５５】
この経路判断部２２の確認処理によりカーネル空間２０とユーザ空間１０とのやり取りを抑えるため、高いスループットを確保できる。なぜなら、アドホックパケット転送処理では、大多数のパケットがカーネル空間２０の動作のみで転送されるからである。図１中のノードＮ５がノードＮ１のパケットをノードＮ２に中継する場合のアドホックパケット転送処理について説明する。
【００５６】
図４を参照して、ノードＮ５のカーネル空間２０は、ノードＮ１からパケットを受信する（１）。カーネル空間２０内の経路判断部２２は、確認処理を実行する（２）。具体的には、宛先アドレスがアドホックネットワークのサブネットに属している場合、パケット内の宛先ＩＰアドレスＡｎ２のホストエントリを経路テーブルＲＴから検索する。経路テーブルＲＴにホストエントリが存在する場合、転送テーブルＦＴ内にも同じホストエントリが存在する。そのため、経路判断部２２は確認処理を終了する。確認処理後、パケット転送部２３は転送テーブルＦＴから宛先アドレスＡｎ２のホストエントリを検索し、ホストエントリ内の次ホップアドレス＝Ａｎ２に基づいてパケットをノードＮ２に送信する（３）。
【００５７】
以上のように、経路テーブルＲＴ内にパケットの宛先のホストエントリがある場合、カーネル空間２０のみが動作し、カーネル空間２０とユーザ空間１０とのやり取りは発生しない。そのため、高いスループットでパケットを転送できる。
【００５８】
一方、経路テーブルＲＴにホストエントリが存在しない場合、図５を参照して、経路判断部２２は、ユーザ空間１０内の経路探索部１２に経路探索を要求する（４）。要求を受けた経路探索部１２はオンデマンド型のルーティングプロトコル（たとえばＡＯＤＶ）に基づいて経路探索を実行し、ノードＮ２宛のホストエントリを取得する（５）。経路探索部１２は取得したホストエントリを経路判断部２２にソケット経由で送信する（６）。経路判断部２２は経路テーブルＲＴ及び転送テーブルＦＴにホストエントリを登録し、確認処理を終了する。確認処理後、パケット転送部２３は転送テーブルＦＴからホストエントリを検索し、ホストエントリ内の次ホップアドレス＝Ａｎ２に基づいてパケットをノードＮ２に転送する（３）。
【００５９】
以上のように、ホストエントリが経路テーブルＲＴにない場合、カーネル空間２０とユーザ空間１０とのやり取りが発生する。
【００６０】
ノード同士が通信する場合、同じ宛先の複数のパケットが連続的に発生する。最初のパケットについて図５の動作（カーネル空間２０＋ユーザ空間１０の動作）を実施し、ホストエントリを取得すれば、その後のパケットに関しては図４の動作（カーネル空間２０のみの動作）で足りる。要するに、確認処理を実行することで、カーネル空間２０とユーザ空間１０とのやり取りを抑えることができる。そのため、高いスループットでパケットを転送できる。
【００６１】
さらに、パケット転送部２３のパケット転送動作は、従来の有線ネットワークの場合と変わらない。つまり、汎用ＯＳを搭載した従来の移動通信装置は追加モジュールをインストールすれば、本実施の形態による移動通信装置１になり、高いスループットでパケットを転送できる。汎用ＯＳのカーネルコードを変更する必要はほとんどない。
【００６２】
図４及び図５では、パケットを転送する場合について説明したが、自ノードのアプリケーション１１からパケットを発信する場合も同じである。
【００６３】
３．２．テーブル更新処理
アドホックネットワークでは、ノードが自由に移動する。そのため、カーネル内テーブル（経路テーブルＲＴ及び転送テーブルＦＴ）に登録した経路情報を必要に応じて最新の経路情報に更新する必要がある。古い経路情報は既に無効になっている可能性が高く、転送時のパケット損失や大きな転送遅延を発生する可能性が高いからである。
【００６４】
カーネル内テーブルに登録された経路情報が最新のものであるほど、経路が有効である可能性も高い。換言すれば、カーネル内テーブルに登録された経路情報が最新であるほど、アドホックパケット転送処理中のカーネル空間２０とユーザ空間１０とのやり取りを抑えることができる。そのため、テーブル更新部１３０がカーネル内テーブルの経路情報を必要に応じて更新する。テーブル更新部１３０は、定期的に隣接ノード探索処理と、経路再探索処理ならびに経路情報消去処理とを実行する。
【００６５】
隣接ノード探索処理では、所定期間毎の経路探索により得た経路情報をカーネル内テーブルに登録する。図６を参照して、経路探索部１２は所定期間毎にＨｅｌｌｏメッセージをブロードキャスト送信し、隣接ノードからＨｅｌｌｏ応答メッセージを受信する（１１）。これによりテーブル更新部１３０は自ノードを取り囲む全ての双方向リンク情報を取得する。テーブル更新部１３０は取得したＨｅｌｌｏ応答メッセージに基づいてカーネル内テーブルの経路情報を更新する（１２）。このとき、経路テーブルＲＴ内の更新された経路情報のタイムスタンプも更新される。
【００６６】
経路情報消去処理では、テーブル更新部１３０は、経路テーブルＲＴ内のタイムスタンプを参照し、所定期間以上の間タイムスタンプが更新されていない満了状態の経路情報を削除する（１３）。なお、タイムスタンプは、パケット転送処理時に検索された時も更新される。
【００６７】
以下、パケット転送処理とテーブル更新処理とについて詳細を説明する。
【００６８】
４．アドホックパケット転送処理の動作フロー
アドホックパケット転送処理は、隣接する他のノードから受信したパケットを中継する場合と、自ノードからパケットを発送する場合とに分類される。前者はたとえば、図１中のノードＮ１がノードＮ７のパケットをノードＮ５へ中継する場合である。後者はたとえば、ノードＮ１がノードＮ２宛にパケットを送信する場合である。それぞれの場合におけるアドホックパケット転送処理を説明する。
【００６９】
４．１．隣接する他のノードからパケットを中継する場合
図７を参照して、ノードＮ１内のカーネル空間２０は、ノードＮ７からパケットを受信する（Ｓ１）。受信後、カーネル空間２０内の経路判断部２２は確認処理を実行する（Ｓ５）。
【００７０】
確認処理（Ｓ５）では、初めに、パケットが有する宛先ＩＰアドレスが自身の所属するアドホックサブネットに属するか否かを判断する（Ｓ５１）。経路判断部２２は、表３に示すアドホック定義テーブルを有する。
【表３】
2005260299.tif 000005
【００７１】
アドホック定義テーブルには、自身の所属するサブネットアドレス（Ａｓｂ）と、自ノードのＩＰアドレス（Ａｎ１）とが登録される。アドレスＡｓｂ及びＡｎ１は移動通信装置１が起動したときに初期設定で登録される。たとえば、起動時に、移動通信装置１に含まれる図示しない入力装置を用いて利用者がＡｓｂ及びＡｎ１を入力する。外部ファイル等にサブネットアドレス及びＩＰアドレスを登録しておき、起動時にミドルウェアプログラムがファイルの内容を読み取ってもよい。
【００７２】
ステップＳ５１で経路判断部２２は、パケットが持つ宛先アドレスＡｎ５の上位２４ビットがアドホック定義テーブル内のサブネットアドレスＡｓｂと一致するか否か判断する。ノードＮ５とノードＮ１とは同じサブネットＳＢに属するため、経路判断部２２は、宛先アドレスＡｎ５のホストエントリを経路テーブルＲＴから検索する（Ｓ５２）。
【００７３】
検索の結果、宛先アドレスＡｎ５のホストエントリが経路テーブルＲＴに存在する場合、転送テーブルＦＴ内にも宛先アドレスＡｎ５のホストエントリが存在する。そのため、ホストエントリを取得するためにカーネル空間２０とユーザ空間１０とでやり取りする必要はない。この場合、経路テーブル検索部２２２が経路テーブルＲＴ内の該当ホストエントリのタイムスタンプを更新し（Ｓ５３）、確認処理を終了する。タイムスタンプを更新することで、この宛先ノードへの経路で直近に利用されたことを示し、後述する経路情報削除処理時に経路情報が削除されるのを防ぐ。
【００７４】
確認処理が終了後、パケット転送部２３はパケット転送処理（Ｓ６）を実行する。具体的には、転送テーブル検索部２３１が転送テーブルＦＴから宛先アドレスＡｎ５のホストエントリを検索する（Ｓ６１）。パケット送信部２３２は、検索されたホストエントリが持つ次ホップアドレス＝Ａｎ５に基づいてパケットをノードＮ５へ送信する（Ｓ６２）。
【００７５】
一方、ステップＳ５２で検索した結果、経路テーブルＲＴ内に該当するホストエントリがない場合、ホストエントリを取得するためにカーネル空間２０とユーザ空間１０とでやり取りが発生する（Ｓ５４〜Ｓ５９）。具体的には、経路判断部２２内の要求部２２３が経路探索要求をユーザ空間１０に出力する（Ｓ５４）。経路探索にはある程度時間がかかる。そのため、カーネル空間２０は経路探索要求後に、パケットをカーネル空間２０内の図示しないキューバッファに格納する（Ｓ５５）。具体的には、経路判断部２２がパケット転送部２３にパケットのキューイングを要求する。要求を受けたパケット転送部２３はパケットをキューバッファに格納する。
【００７６】
ユーザ空間１０内の経路探索部１２は経路探索要求を受け、オンデマンド型のルーティングプロトコルに基づいて経路探索を実行する（Ｓ７）。経路探索部１２は経路探索により取得した宛先アドレスＡｎ５のホストエントリをカーネル空間２０にソケット経由で送信する（Ｓ８）。
【００７７】
経路判断部２２はユーザ空間１０からホストエントリを受け、登録部２２１は受けたホストエントリを経路テーブルＲＴと転送テーブルＦＴとに登録する（Ｓ５６）。なお、このときタイムスタンプも登録される。
【００７８】
続いて、キューバッファに格納されたパケットを取り出す（Ｓ５７）。複数のパケットがキューバッファに格納されている場合、カーネル空間２０はステップＳ５６で登録されたホストエントリの宛先ＩＰアドレスと宛先が一致するパケットを取り出す。
【００７９】
経路判断部２２は、取り出したパケットのパケットサイズがステップＳ５６で登録したホストエントリ内で指定されたインターフェース（パケット送信時に使用するインターフェース）のＭＴＵ（Maximum Transmission Unit）よりも大きいか否かを判断する（Ｓ５８）。各インタフェースは個別のＭＴＵ値を保有している。パケットサイズがＭＴＵよりも小さい場合、確認処理を終了する。
【００８０】
一方、パケットサイズがＭＴＵよりも大きい場合、フラグメンテーション処理を実行し（Ｓ５９）、確認処理を終了する。次ホップアドレスのノードＮ５のインタフェースに対応したパケットサイズにするためである。
【００８１】
確認処理を実行後（Ｓ５）、パケット転送部がパケット転送処理を実行する（Ｓ６）。  以上のように、経路判断部２２で確認処理を実行するため、ホストエントリが経路テーブルＲＴに存在すれば、カーネル空間２０とユーザ空間１０とのやり取りは発生しない。よって、高いスループットでパケットを転送できる。
【００８２】
４．２．自ノードからパケットを発信する場合
図８を参照して、ノードＮ１がノードＮ２宛のパケットを送信する場合、カーネル空間２０内の送受信部２１Ａは、アプリケーション１１からソケットインタフェース経由でパケットを受信する（Ｓ２）。たとえばアプリケーション１１がＷｅｂブラウザの場合、パケットはＷｅｂブラウザからＴＣＰ層に送信され、ＴＣＰ層から送受信部２１Ａに送信される。
【００８３】
パケット転送部２３は受信したパケットの宛先アドレスＡｎ２に対応したホストエントリを転送テーブルＦＴから検索する（Ｓ３）。検索後、ホストエントリの有無に関わらず、確認処理が実行される（Ｓ５）。
【００８４】
経路判断部２２は、パケットの宛先のノードＮ２がアドホックサブネットに属するか否かを判断する（Ｓ５１）。判断の結果、宛先アドレスがアドホックサブネットに属しない場合、つまり、ノードＮ２がアドホック以外のサブネット（たとえば有線ネットワーク）に属する場合、確認処理は終了する。ステップＳ５１の判断の結果、ノードＮ２がアドホックサブネットに属する場合、経路テーブル検索部２２２は宛先アドレスＡｎ２のホストエントリを経路テーブルＲＴから検索する（Ｓ５２）。検索の結果、経路テーブルＲＴ内にホストエントリが存在する場合、そのホストエントリのタイムスタンプを更新して（Ｓ５３）、確認処理を終了する。
【００８５】
経路テーブルＲＴ内にホストエントリが存在するため、転送テーブルＦＴ内にもホストエントリが存在する。パケット転送部２３は既にステップＳ３で宛先アドレスＡｎ２のホストエントリを検索している。そのため、パケット転送処理（Ｓ６）では、ステップＳ３で取得したホストエントリの次ホップアドレス＝Ａｎ５に基づいて、パケット送信部２３２がパケットを送信する（Ｓ６２）。
【００８６】
ステップＳ５２での検索の結果、経路テーブルＲＴ内にホストエントリが存在しない場合のアドホックパケット転送処理は、図７と同じである。
【００８７】
自ノードからパケットを発信する場合、確認処理（Ｓ５）の前に転送テーブルＦＴが検索される。このような動作フローにすれば、汎用ＯＳのカーネルコードを変更する必要はない。たとえば汎用ＯＳであるＬｉｎｕｘ（登録商標）において、カーネルコアの所定のフックに追加モジュールを実装すれば、カーネルコードを変更することなく図８の動作を実現できる。要するに、移動通信装置１は、汎用ＯＳのカーネルコードを変更することなく、高いスループットでパケットを転送できる。
【００８８】
５．テーブル更新処理の動作フロー
５．１．隣接ノード探索処理
隣接ノード探索処理では、移動通信装置１は、一定期間ごとに隣接ノードへＨｅｌｌｏメッセージをブロードキャスト送信後、そのＨｅｌｌｏメッセージを受信した隣接ノードからＨｅｌｌｏ応答メッセージを受信し経路情報を取得する。取得した経路情報に基づいて、テーブル更新部１３０がカーネル内テーブルの経路情報を更新する。テーブル更新部１３０内のテーブル管理部１３は、表４に示すシャドー経路テーブルＳＲＴを持つ。
【表４】
2005260299.tif 000006
【００８９】
シャドー経路テーブルＳＲＴは７つのフィールドを持つ。そのうち６つのフィールドは経路テーブルＲＴと同じデータを持つ。新たなフィールドであるステータスには、対応する経路情報の状態が登録される。経路情報のタイムスタンプから所定期間αを経過していない場合、経路情報内のステータスは「ａｃｔｉｖｅ」となる。所定期間αを経過した場合、ステータスは「ｉｎａｃｔｉｖｅ」となる。
【００９０】
テーブル更新部１３０は、隣接ノードから取得した経路情報に基づいてシャドー経路テーブルＳＲＴ内の経路情報を更新した後、カーネル内テーブルの経路情報を更新する。
【００９１】
図９を参照して、隣接ノード探索処理は、Ｈｅｌｌｏメッセージブロードキャスト送信処理（Ｓ２０）と更新処理（Ｓ２１）とを実行する。
【００９２】
図１０に時刻ｔ１０におけるアドホックネットワークを示す。図９及び図１０を参照して、ノードＮ１内の経路探索部１２は、表５に示すＨｅｌｌｏメッセージをブロードキャストする（Ｈｅｌｌｏメッセージブロードキャスト送信処理：Ｓ２０）。
【表５】
2005260299.tif 000007
【００９３】
Ｈｅｌｌｏメッセージは、自ノードＩＰアドレス（Ａｎ１）とシーケンス番号とを含む。ノードＮ１がＨｅｌｌｏメッセージを生成するごとにシーケンス番号はカウントアップされる。ステップＳ２０でノードＮ１は所定期間△ｔ１ごとにＨｅｌｌｏメッセージをブロードキャストする。たとえば所定期間△ｔ１は「１秒」である。
【００９４】
図１０中のノードＮ５はノードＮ１のＨｅｌｌｏメッセージを受信する。ノードＮ５はＨｅｌｌｏメッセージを受信してから所定期間△ｔ２経過後の時刻ｔ１１（＝ｔ１０＋△ｔ２）にＨｅｌｌｏ応答メッセージを送信する。△ｔ２>△ｔ１であり、たとえば、所定期間△ｔ２は「３秒」である。
【００９５】
図１１に時刻ｔ１１におけるアドホックネットワークを示す。ノードＮ１は１秒ごとにＨｅｌｌｏメッセージを送信するため、時刻ｔ１０から３秒後の時刻ｔ１１において、ノードＮ５はノードＮ１から３回Ｈｅｌｌｏメッセージを受ける。さらに、△ｔ２中にノードＮ５はノードＮ２〜Ｎ４からもＨｅｌｌｏメッセージを受ける。
【００９６】
ノードＮ５が生成するＨｅｌｌｏ応答メッセージを表６に示す。
【表６】
2005260299.tif 000008
【００９７】
表６を参照して、Ｈｅｌｌｏ応答メッセージは、複数の隣接ノードデータとを含む。隣接ノードデータは、時刻ｔ１０〜時刻ｔ１１の間にノードＮ５が受信したＨｅｌｌｏメッセージに基づくデータであり、具体的には、Ｈｅｌｌｏメッセージの送信元のノード（Ｎ１〜Ｎ４）に関するデータである。隣接ノードデータは、ＩＰアドレスとメッセージ受信回数と有効フラグとを持つ。ＩＰアドレスは、ノードＮ１〜Ｎ４のＩＰアドレス（Ａｎ１〜Ａｎ４）である。
【００９８】
メッセージ受信回数は、時刻ｔ１０から時刻ｔ１１の間にノードＮ５が受信したＨｅｌｌｏメッセージの回数である。受信回数はノードＮ５によりカウントされる。ノードＮ５は、同じノードから送信された同じシーケンス番号を持つ複数のＨｅｌｌｏメッセージを重複してカウントしない。それらのＨｅｌｌｏメッセージは同じタイミングで同じノードから出力されたものだからである。ノードＮ２〜Ｎ４からのＨｅｌｌｏメッセージについても同様である。
【００９９】
有効フラグは、ノードＮ５と各隣接ノードＮ１〜Ｎ４とのリンクの状態を示す。ノードＮ５と隣接ノードＮ１〜Ｎ４とのリンクが双方向に通信可能な状態（Bi-directional-link）であり、かつそのリンクが安定している場合、有効フラグは「ＯＮ」である。リンクが一方向に通信可能であったり、双方向リンクではあるが、電波障害等の影響で不安定である場合、有効フラグは「ＯＦＦ」である。Ｈｅｌｌｏ応答メッセージを送信するノードＮ５が有効フラグを決定する。なお、ノードＮ５の自ノードＩＰアドレス（Ａｎ５）はＨｅｌｌｏ応答メッセージのＩＰヘッダに含まれる。
【０１００】
ノードＮ５は、時刻ｔ１０でＨｅｌｌｏメッセージを受信してから所定期間△ｔ２経過後にＨｅｌｌｏ応答メッセージを出力する。また、時刻ｔ１０から△ｔ２が経過するまでに受信したＨｅｌｌｏメッセージの送信元ノード（Ｎ１〜Ｎ４）の全てのデータをＨｅｌｌｏ応答メッセージに含める。このため、Ｈｅｌｌｏ応答メッセージの送信頻度を軽減しネットワークへの負荷を抑制することに貢献する。この貢献によりアプリケーション１１が送受信するパケットの実効スループットを向上させることが可能となる。
【０１０１】
図９に戻って、ノードＮ１が時刻ｔ１１にノードＮ５から表５に示すＨｅｌｌｏ応答メッセージを受けたとき、テーブル更新部１３０は更新処理を実行する（Ｓ２１）。
【０１０２】
Ｈｅｌｌｏ応答メッセージを受信した後（Ｓ２１１）、ノードＮ１内のテーブル管理部１３は、Ｈｅｌｌｏ応答メッセージがノードＮ１のＩＰアドレス（Ａｎ１）を含むか否かを判断する（Ｓ２１２）。表５のＨｅｌｌｏ応答メッセージはＩＰアドレスＡｎ１を含む。換言すれば、ノードＮ１が出力したＨｅｌｌｏメッセージ内の情報を含む。そのため、ノードＮ１とノードＮ５とのリンクは、双方向に通信可能なリンクである。この場合、テーブル更新部１３０は、Ｈｅｌｌｏ応答メッセージに基づいてシャドー経路テーブルＳＲＴとカーネル内テーブルとを更新する（Ｓ２１３〜Ｓ２１６）。このようにＨｅｌｌｏメッセージの受信によってではなくＨｅｌｌｏ応答メッセージの受信によって隣接ノードへのリンク情報を獲得することで、双方向の通信が有効なリンクのみを経路として採用することを可能としている。
【０１０３】
ステップＳ２１３では、テーブル管理部１３が、Ｈｅｌｌｏ応答メッセージに含まれる経路情報がシャドーテーブルＳＲＴに既に登録されているか否かを判断する。具体的には、Ｈｅｌｌｏ応答メッセージ内の各ＩＰアドレスを宛先ＩＰアドレスに持つ経路情報がステータスが「ａｃｔｉｖｅ」のエントリとしてシャドーテーブルＳＲＴに登録されているか否か判断する。表４を参照して、宛先ＩＰアドレスがＡｎ５及びＡｎ２である経路情報はシャドーテーブルＳＲＴに既にステータスが「ａｃｔｉｖｅ」のエントリとして登録されている。そのため、カーネル内テーブルにもこれらの経路情報は登録されている。この場合、テーブル管理部１３は、シャドーテーブルＳＲＴ内のこれらの経路情報に対応したタイムスタンプをＨｅｌｌｏ応答メッセージ受信時の「ｔ１１」に更新し（Ｓ２１６）、更新処理を終了する。
【０１０４】
一方、表４を参照して、宛先ＩＰアドレスがＡｎ３及びＡｎ４の経路情報は登録されていない（Ｓ２１３）。この場合、テーブル管理部１３はこれらの経路情報をシャドー経路テーブルＳＲＴにステータスが「ｉｎａｃｔｉｖｅ」のエントリとして登録する（Ｓ２１４）。ステータスが「ｉｎａｃｔｉｖｅ」のエントリとして存在している場合（Ａｎ６）、ある所定の回数のＨｅｌｌｏ応答メッセージを受信した時点で無線リンクの品質を"安定"と見なし、そのステータスを「ａｃｔｉｖｅ」に更新する。
【０１０５】
宛先アドレスＡｎ３の経路情報は以下のように登録される。宛先ＩＰアドレスＡｎ３はホストアドレスであるため、ネットマスクは「２５５．２５５．２５５．２５５」となる。また、次ホップアドレスはＨｅｌｌｏ応答メッセージ中の自ノードＩＰアドレス「Ａｎ５」となる。インタフェースインデックスは、ノードＮ１と次ホップのノードＮ５とのインタフェースインデックス＝１となる。ノードＮ１はＨｅｌｌｏ応答メッセージを受信したときに使用したインタフェースインデックスを判断する。ホップカウントは「２」となり、タイムスタンプは「ｔ１１」となる。宛先アドレスＡｎ４の経路情報も同様に登録される。
【０１０６】
以上の更新処理により更新されたシャドー経路テーブルＳＲＴを表７に示す。
【表７】
2005260299.tif 000009
【０１０７】
ステップＳ２１４で、テーブル更新部１３０が所定の回数のＨｅｌｌｏ応答メッセージ（隣接データ３、４を含む）を連続して又は一定期間内に受信した時、テーブル更新部１３０は、ノードＮ３及びＮ４とのリンクの品質を"安定"と見なす。このとき、シャドー経路テーブルＳＲＴ内の宛先アドレスＡｎ３及びＡｎ４のステータスを「ｉｎａｃｔｉｖｅ」から「ａｃｔｉｖｅ」に更新する。更新後、テーブル更新部１３０内のテーブル管理部１３は、宛先アドレスＡｎ３及びＡｎ４の経路情報をカーネル空間２０へ送信する（Ｓ２１５）。カーネル空間２０は経路情報を受信し（Ｓ２２）、経路判断部２２内の登録部２２１は、受けた経路情報を経路テーブルＲＴ及び転送テーブルＦＴに登録する（Ｓ２３）。
【０１０８】
なお、ステップＳ２１２の判断の結果、Ｈｅｌｌｏ応答メッセージがノードＮ１のＩＰアドレスを含まない場合、ノードＮ１とＮ５とのリンクは一方向のみ通信可能なリンクである。そのため、更新処理を終了する。
【０１０９】
以上の動作により、カーネル内テーブルの隣接ノードに関する経路情報は定期的に更新される。換言すれば、カーネル内テーブルは隣接ノードに関しては常に最新の経路情報を含む。
【０１１０】
上述の内容と一部重複するが、Ｈｅｌｌｏ応答メッセージ内のメッセージ受信回数及び有効フラグに基づいて、シャドー経路テーブルＳＲＴ内の該当エントリーにおけるステータスが登録される。たとえば、Ｈｅｌｌｏ応答メッセージ中の隣接ノードデータ１（ノードＮ１のデータ）のメッセージ受信回数が「１」の場合、ノードＮ５は所定期間△ｔ２内にノードＮ１から送信された３回のＨｅｌｌｏメッセージのうち１回しかＨｅｌｌｏメッセージを受信していないことになる。この場合、ノードＮ１とノードＮ５とのリンクが不安定な状態と見なされ、テーブル管理部１３がステップＳ２１４又はステップＳ２１６でシャドー経路テーブルＳＲＴ内の宛先ＩＰアドレスＡｎ５のステータスを「ｉｎａｃｔｉｖｅ」と設定する。また、Ｈｅｌｌｏ応答メッセージ内に存在した付随的な情報である宛先ノードＡｎ２〜Ａｎ４について、Ｈｅｌｌｏ応答メッセージ中の各宛先の有効フラグを利用してステータスを設定することも可能である。たとえば、Ｈｅｌｌｏ応答メッセージ中の隣接ノードデータ３の有効フラグは「ＯＦＦ」であり、ノードＮ５にとってノードＮ３はリンクが不安定な隣接ノードであることを示している。そのため、自ノードのシャドー経路テーブルＳＲＴ内にノードＮ３に関するホストエントリが存在しない場合、テーブル管理部１３はシャドー経路テーブルＳＲＴ内の宛先ＩＰアドレスＡｎ３のステータスを「ｉｎａｃｔｉｖｅ」としてもよい。
【０１１１】
５．２．経路情報消去処理
経路情報消去処理では、経路テーブルＲＴ内のタイムスタンプを参照し、更新されていない経路情報を削除する。不要な経路情報を削除し、有効な経路情報のみをカーネル内テーブルに登録するため、アドホックパケット転送処理において、カーネル空間２０とユーザ空間１０とのやり取りを抑えることができる。その結果、高いスループットでパケットを転送する。以下、経路情報削除処理について説明する。
【０１１２】
図１２を参照して、テーブル管理部１３は、カーネル空間２０内の経路判断部２２にタイムスタンプデータを要求する。タイムスタンプデータとは、経路テーブルＲＴ内の全ての経路情報の最新のエントリ参照時刻を表すデータであり、具体的には、宛先アドレス及びタイムスタンプで構成される。経路判断部２２は、要求を受け、タイムスタンプデータを送信する（Ｓ３０２）。
【０１１３】
タイムスタンプデータを受信後、テーブル管理部１３はタイムスタンプデータに基づいてシャドー経路テーブルＳＲＴを更新する（Ｓ３０３）。ステップＳ３０３の更新により、ＳＲＴ内のタイムスタンプはＲＴ内のタイムスタンプ（図８及び図９中ステップＳ５３に相当）と同期する。なお、確認処理時に経路探索部１２が経路探索を実行したとき（図８及び図９のステップＳ７に相当）、取得した経路情報とタイムスタンプとはシャドー経路テーブルＳＲＴにも登録されている。
【０１１４】
テーブル管理部１３はシャドー経路テーブルＳＲＴ中の全てのエントリ（経路情報）に対し、最新のステータスを判断する（Ｓ３０４〜Ｓ３０９）。
【０１１５】
具体的には、シャドー経路テーブルＳＲＴの最初の経路情報を選択し（Ｓ３０４）、以下の式（１）に基づいてステータスを判断する（Ｓ３０５）。
現在時刻−タイムスタンプ>所定期間α…（１）
【０１１６】
式（１）を満たす場合、その経路情報は所定期間α中に検索又は更新されてない情報である。そのため、その経路情報のステータスを「ｉｎａｃｔｉｖｅ」にする（Ｓ３０６）。続いて、テーブル管理部１３は当該経路情報の削除要求をカーネル空間２０に送信する（Ｓ３０７）。削除要求を受けた経路判断部２２内の登録部２２１は、カーネル内テーブルの該当経路情報を削除する（Ｓ３１０）。
【０１１７】
一方、ステップＳ３０５において、式（１）を満たさない場合、その経路情報のステータスは「ａｃｔｉｖｅ」である。そのため、次の経路情報を選択し（Ｓ３０９）、ステップ３０５へ戻る。全ての経路情報についてステータスを判断した場合（Ｓ３０８）、経路情報削除処理を終了する。なお、ステップＳ３０５で「ａｃｔｉｖｅ」であると判定された経路について再経路探索を起動させることも可能である。再経路探索を起動するか否かは、トポロジの変更頻度やノードの移動速度といった環境要因に応じて決定することが望ましい。
【０１１８】
以上の動作により、カーネル内テーブルの不要な経路情報を削除できる。なお、シャドー経路テーブルＳＲＴ内の「ｉｎａｃｔｉｖｅ」の経路情報は残しておく。経路探索のときにこれらの過去の経路情報を利用した探索が可能となり、探索時間短縮ならびに探索処理で発生するネットワークへの負荷軽減などの効果が期待されるからである。
【０１１９】
以上、本実施の形態を説明したが、本発明は上述した実施の形態に限られない。たとえば、従来の汎用ＯＳのカーネルコードを変更し、図１３に示すように、パケット転送部２３の転送テーブルＦＴに経路テーブルＲＴの機能を追加し（以下経路転送テーブルＲＦＴと称する）、さらに登録部２２１及び要求部２２３を追加すれば、図２の移動通信装置１と同じ機能を実現できる。経路転送テーブルＲＦＴは、汎用ＯＳ内の転送テーブルＦＴに表２に示す経路テーブルのフィールドを追加したものである。
【０１２０】
図１４を参照して、他のノードからパケットを受けたカーネル空間２０は、確認処理を実行する（Ｓ５）。経路転送テーブルＲＦＴ内のパケットの宛先アドレスに一致するホストエントリが存在する場合（Ｓ５２）、参照した該当ホストエントリの情報に基づいてパケット送信部２３２がパケットを送信する（Ｓ６２）。一方、経路転送テーブルＲＦＴに該当ホストエントリが存在しない場合（Ｓ５２）、経路探索をユーザ空間で稼動するミドルウェアに要求する（Ｓ５４）。ユーザ空間１０から経路情報を取得後、登録部２２１が経路転送テーブルＲＦＴに経路情報を登録する（Ｓ５６１）。登録した経路情報に基づいて、パケット送信部２３２はパケットを送信する（Ｓ６２）。その他の動作については、図７と同じである。なお、自ノードのアプリケーション１１からパケットが発信された場合も、図１４の動作が実行される。
【０１２１】
以上、本発明の実施の形態を説明したが、上述した実施の形態は本発明を実施するための例示に過ぎない。よって、本発明は上述した実施の形態に限定されることなく、その趣旨を逸脱しない範囲内で上述した実施の形態を適宜変形して実施することが可能である。
【図面の簡単な説明】
【０１２２】
【図１】本発明の実施の形態による移動通信装置を用いたアドホックネットワークの構成を示す概念図である。
【図２】本発明の実施の形態による移動通信装置のハードウェア構成を示す機能ブロック図である。
【図３】図２中のＣＰＵ及びメモリの構成を示す機能ブロック図である。
【図４】本発明の実施の形態による移動通信装置のパケット転送処理動作を示す概略図である。
【図５】本発明の実施の形態による移動通信装置のパケット転送処理動作の他の例を示す概略図である。
【図６】本発明の実施の形態による移動通信装置のテーブル更新処理動作を示す概略図である。
【図７】図４及び図５の動作の詳細を示すフロー図である。
【図８】パケット転送処理の他の例を示すフロー図である。
【図９】隣接ノード探索処理の動作の詳細を示すフロー図である。
【図１０】隣接ノード探索処理を説明するための概略図である。
【図１１】隣接ノード探索処理を説明するための概略図である。
【図１２】経路情報削除処理の動作の詳細を示すフロー図である。
【図１３】本発明の実施の形態による移動通信装置の他の例の構成を示す機能ブロック図である。
【図１４】図１３に示す移動通信装置のアドホックパケット転送処理の動作を示すフロー図である。
【図１５】アドホックネットワークを説明するための概略図である。
【図１６】有線ネットワークでのパケット転送処理を説明するための概略図である。
【符号の説明】
【０１２３】
１  移動通信装置
１０  ユーザ空間
１１  アプリケーション
１２  経路探索部
１３  テーブル管理部
２０  カーネル空間
２１Ａ，２１Ｂ  送受信部
２２  経路判断部
２３  パケット転送部
１０１  ＣＰＵ
１０２  メモリ
１０３  通信部
１３０  テーブル更新部
２２１  登録部
２２２  経路テーブル検索部
２２３  要求部
２３１  転送テーブル検索部
２３２  パケット送信部
ＲＴ  経路テーブル
ＦＴ  転送テーブル
ＲＦＴ  経路転送テーブル
【図１】
2005260299.tif 000010
【図２】
2005260299.tif 000011
【図３】
2005260299.tif 000012
【図４】
2005260299.tif 000013
【図５】
2005260299.tif 000014
【図６】
2005260299.tif 000015
【図７】
2005260299.tif 000016
【図８】
2005260299.tif 000017
【図９】
2005260299.tif 000018
【図１０】
2005260299.tif 000019
【図１１】
2005260299.tif 000020
【図１２】
2005260299.tif 000021
【図１３】
2005260299.tif 000022
【図１４】
2005260299.tif 000023
【図１５】
2005260299.tif 000024
【図１６】
2005260299.tif 000025