(57)【特許請求の範囲】
【請求項１】
複数の通信ノードを含む通信ネットワークにおいてパケットを管理する方法であって：
パケット・ヘッダを含むパケットを受信する段階であって、前記パケット・ヘッダは前記パケットを一意的に識別するパケット識別子を含む、段階と；
前記パケット識別子に基づいて、第一の通信ノードによって受信された前記パケットのパケット型を判別する段階と；
前記パケットが重複パケットであると判別されたときには前記パケットをドロップする；または
前記パケットが返送パケットまたは新規パケットであると判別されたときには、前記パケットがループに捉えられるのを防ぐ仕方で、前記パケットを隣接通信ノードにルーティングする段階とを含む、
方法。
【請求項２】
前記判別する段階が：
前記パケット識別子を、前記第一の通信ノードにおいて受信されたパケットに対応するパケット識別子のリストと比較し；
前記比較に基づいて、前記パケットと同じパケット識別子を有する別のパケットが前記第一の通信ノードにおいて受信されたことがあるかどうかを判定し；
前記パケットと同じパケット識別子をもつ別のパケットが前記第一の通信ノードにおいて受信されたことがあると判定されるとき、前記パケット・ヘッダに含まれる通過履歴に基づいて前記第一の通信ノードが前記パケットを転送したことがあるかどうかを判定することを含む、
請求項１記載の方法。
【請求項３】
前記通過履歴が、前記パケットを転送したことのある通信ノードの集合を同定するよう構成されたリストまたはブルーム・フィルタのビット・シーケンスを含む、請求項２記載の方法。
【請求項４】
前記ルーティングする段階が：
前記第一の通信ノードの隣接通信ノードの集合から前記パケットを転送する転送先の第二の通信ノードを選択し；
前記パケット・ヘッダに含まれる通過履歴に基づいて前記第二の通信ノードが前記パケットを転送したことがあるかどうかを判定し；
前記第二の通信ノードが前記パケットを転送したことがないと判定される場合には前記パケットを前記第二の通信ノードに転送する、または
前記第二の通信ノードが前記パケットを転送したことがあると判定される場合には前記パケットを転送する転送先の代替的な隣接通信ノードを選択するの一方を行う、
ことを含む、
請求項１記載の方法。
【請求項５】
前記判別する段階は、前記パケット識別子に基づいて、前記パケットが前記第一の通信ノードにおいて以前に受信されたことがないと判定することを含む、請求項１記載の方法。
【請求項６】
前記パケットを前記隣接通信ノードに転送するのに先立って、前記パケット・ヘッダに含まれる通過履歴を、前記第一の通信ノードのノード識別子を含めるよう更新する段階をさらに含む、請求項５記載の方法。
【請求項７】
複数の通信ノードを含む通信ネットワークにおいてパケットを管理する方法であって：
パケット・ヘッダを含むパケットを受信する段階であって、前記パケット・ヘッダは前記パケットを一意的に識別するパケット識別子を含む、段階と；
前記パケット識別子に基づいて、第一の通信ノードによって受信された前記パケットのパケット型を判別する段階と；
前記パケットが重複パケットであると判別されたときは前記パケットをドロップし；
前記パケットが返送パケットまたは新規パケットであると判別されたときは、
前記パケットを転送する転送先の第一の隣接通信ノードを選択し；
前記パケット・ヘッダに含まれる通過履歴に基づいて前記第一の隣接通信ノードが前記パケットを以前に転送したことがあることを判別し；
前記第一の隣接通信ノードが前記パケットを以前に転送したことがあることを判別された場合に、前記パケットを転送する転送先の第二の隣接通信ノードを選択し；
前記通過履歴に基づいて、前記第二の隣接通信ノードが前記パケットを以前に転送したことがないことを判別し、その後、前記パケットを前記第二の隣接通信ノードにルーティングする、
段階とを含む、
方法。
【請求項８】
前記ドロップする段階が、前記重複パケットが前記パケット・ヘッダにおいて指定される宛先ノードに到達する前に、前記重複パケットを前記通信ネットワーク内での流通から除去することを含む、請求項１記載の方法。
【請求項９】
通信ネットワークにおいてパケットを管理するシステムであって、前記通信ネットワークに含まれる複数の通信ノードを有しており、各通信ノードは処理装置を有しており、前記処理装置は：
その処理装置に対応する通信ノードによって受信されたパケットのパケット型を、複数のパケット識別子および前記パケットのパケット・ヘッダに含まれるパケット識別子に基づいて判別し；
前記パケットが重複パケットであると判別されたときには前記パケットをドロップし；あるいは；
前記パケットが返送パケットまたは新規パケットであると判別されたときには、前記パケットがループに捉えられるのを防ぐ仕方で、前記パケットを隣接通信ノードにルーティングするよう構成されている、
システム。
【請求項１０】
前記判別する処理が：
前記パケット識別子を、前記対応する通信ノードにおいて受信されたパケットに対応する前記複数のパケット識別子のリストと比較し；
前記比較に基づいて、前記パケットと同じパケット識別子を有する別のパケットが前記対応する通信ノードにおいて受信されたことがあるかどうかを判定し；
前記パケットと同じパケット識別子をもつ別のパケットが前記対応する通信ノードにおいて受信されたことがあると判定されるとき、前記パケットの前記パケット・ヘッダに含まれる通過履歴に基づいて前記対応する通信ノードが前記パケットを転送したことがあるかどうかを判定することを含む、
請求項９記載のシステム。
【請求項１１】
前記ルーティングする処理が：
前記パケット・ヘッダに含まれる通過履歴に基づいて、前記隣接通信ノードが前記パケットを転送したことがないことを判定し；
前記パケットを前記隣接通信ノードに転送することを含む、
請求項９記載のシステム。
【請求項１２】
前記処理装置がさらに、各新規パケットの対応するパケット・ヘッダに含まれる通過履歴を、前記対応する通信ノードのノード識別子を含めるよう更新するよう構成されている、請求項９記載のシステム。
【請求項１３】
前記通過履歴がブルーム・フィルタのビット・シーケンスを含み、前記処理装置が前記通過履歴を更新する処理が：
前記対応する通信ノードのノード識別子に対して前記ブルーム・フィルタに関連付けられたk個の既知のハッシュ関数を計算して、前記ブルーム・フィルタ中のk個の対応する配列位置を決定し；
前記ブルーム・フィルタ中の前記k個の対応する配列位置のそれぞれにおけるビットを、すでに1に設定されていなければ、1に設定することを含む、
請求項１２記載のシステム。
【請求項１４】
前記対応する通信ノードが第一の通信ノードであり、
前記通過履歴が、対応する新規パケットを転送したことのある通信ノードに対応するノード識別子のリストを含み；
前記処理装置が前記通過履歴を更新する処理が、前記処理装置が、対応する新規パケットを転送する前に、ノード識別子の前記リストに前記第一の通信ノードのノード識別子を追加することを含む、
請求項１２記載のシステム。
【請求項１５】
通信ノードに、該通信ノードを含む通信ネットワークにおいてパケットを管理するための動作を実行させる命令を記憶している非一時的なコンピュータ可読記憶媒体であって、前記動作は：
パケット・ヘッダを含むパケットを受信する段階であって、前記パケット・ヘッダは前記パケットを一意的に識別するパケット識別子を含む、段階と；
前記パケット識別子に基づいて、第一の通信ノードによって受信された前記パケットのパケット型を判別する段階と；
前記パケットが重複パケットであると判別されたときには前記パケットをドロップする；または
前記パケットが返送パケットまたは新規パケットであると判別されたときには、前記パケットがループに捉えられるのを防ぐ仕方で、前記パケットを隣接通信ノードにルーティングする段階とを含む、
非一時的なコンピュータ可読記憶媒体。
【請求項１６】
前記パケット・ヘッダが、前記パケットを転送したことのある通信ノードの集合を同定するよう構成された通過履歴を含む、請求項１５記載の非一時的なコンピュータ可読記憶媒体。
【請求項１７】
請求項１６記載の非一時的なコンピュータ可読記憶媒体であって、前記通過履歴がブルーム・フィルタのビット・シーケンスを含み、前記判別する段階が、前記パケットが重複パケットであると判別されるときに前記通信ノードのノード識別子が前記ブルーム・フィルタに存在しないと判定することを含み、該存在しないと判定することが：
前記ノード識別子に対して前記ブルーム・フィルタに関連付けられたk個の既知のハッシュ関数を計算して、前記ブルーム・フィルタ中のk個の対応する配列位置を決定し；
前記k個の対応する配列位置が1のビットまたは0のビットのどちらを含むかを検査し；
前記k個の対応する配列位置の少なくとも一つが0のビットを含む場合に、前記ノード識別子が前記ブルーム・フィルタに存在しないと判定することを含む、
非一時的なコンピュータ可読記憶媒体。
【請求項１８】
請求項１６記載の非一時的なコンピュータ可読記憶媒体であって、
前記通信ノードが第一の通信ノードであり、
前記通過履歴が、前記パケットを転送したことのある通信ノードに対応するノード識別子のリストを含み；
前記判別する段階が、前記パケットが重複パケットであると判別されるときに前記第一の通信ノードのノード識別子がノード識別子の前記リストに存在しないと判定することを含む、
非一時的なコンピュータ可読記憶媒体。
【請求項１９】
前記ドロップする段階が、前記重複パケットが前記パケット・ヘッダにおいて指定される宛先ノードに到達する前に、前記重複パケットを前記通信ネットワーク内での流通から除去することを含む、請求項１５記載の非一時的なコンピュータ可読記憶媒体。
【請求項２０】
前記パケット識別子が：前記パケットの源によって前記パケットに割り当てられる一意的なシーケンス番号、前記源からの前記パケットの出発時間を示すタイムスタンプおよびハッシュ値のうちの少なくとも一つを含む、請求項１５記載の非一時的なコンピュータ可読記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本稿で論じる実施形態は通信ネットワークにおけるパケット管理に関する。
【背景技術】
【０００２】
一部の通信ネットワークにおけるリンクには損失がある。これはつまり、いくつかのデータ・パケットが伝送中に失われることがあるということである。データ・パケットの受け取りを確認するさまざまな機構が存在している。たとえば、そのような通信ネットワークにおいて、受信通信ノードがデータ・パケットの受信を受取確認するためにACKメッセージを送信通信ノードに送りうるリンク層受取確認（ACK:  acknowledgement）機構を設けることができる。しかしながら、ACKメッセージも失われることがある。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
損失のある通信ネットワークにおける信頼性を改善するためにさまざまなマルチパス・データ転送プロトコルが存在している。そのようなマルチパス・データ転送プロトコルを実装する通信ネットワークでは、第一のノードが第一のルートまたは経路に沿って第二のノードにデータ・パケットを送ってもよい。第一のノードが第二のノードからACKメッセージを受信しない場合には、第一のノードは異なるルートまたは経路に沿って第三のノードにデータ・パケットを再送してもよい。場合によっては、第一のノードが第二のノードからACKメッセージを受け取っていなかったとしても、第二のノードに送られたパケットはさらに別のノードに転送されるために第二のノードに無事到着していたこともありうる。この例では、第三のノードに送られた再送パケットは、第二のノードに送られ、第二のノードによって転送されるパケットの複製である。既存のマルチパス・データ転送プロトコルは、信頼できる形で重複パケットを検出し、および／またはループされたパケットから重複パケットを見きわめることができないので、重複パケットが通信ネットワークにおける輻輳を増大させたり、および／または、ループを防止するためにルートがポイズニングされたり更新されたりすることができないことがある。
【０００４】
本願で請求される主題は、何らかの欠点を解決するまたは上記のような環境においてのみ動作する実施形態に限定されるものではない。むしろ、この背景は、本稿に記載されるいくつかの実施形態が実施されうる一つの例示的な技術領域を例解するために与えられているのである。
【課題を解決するための手段】
【０００５】
ある実施形態のある側面によれば、複数の通信ノードを含む通信ネットワークにおいてパケットを管理する方法が記述される。本方法は、パケット・ヘッダを含むパケットを受信する段階を含んでいてもよい。パケット・ヘッダはパケットを一意的に識別するパケット識別子を含んでいてもよい。本方法はまた、パケット識別子に基づいて、第一の通信ノードによって受信されたパケットのパケット型を判別することをも含んでいてもよい。本方法はまた、パケットが重複パケットであると判別されたときにそのパケットをドロップする、またはパケットが返送パケットまたは新規パケットであると判別されたときに、そのパケットがループに捉えられるのを防ぐ仕方で、そのパケットを隣接通信ノードにルーティングすることをも含んでいてもよい。
【０００６】
前記実施形態の目的および利点は少なくとも請求項において具体的に記載される要素、特徴および組み合わせによって実現され、達成される。
【０００７】
上記の概括的な記述および以下の詳細な記述はいずれも例示的であり説明的であり、特許請求される本発明を制約するものではないことは理解しておくべきである。
【図面の簡単な説明】
【０００８】
例示的な実施形態は、付属の図面の使用を通じてさらに具体的かつ詳細に記述され、説明される。
【図１】パケットが伝送されうる例示的な通信ネットワークを示す図である。
【図２】図１の通信ネットワークを通じて伝送されうる例示的なパケットを示す図である。
【図３】図１の通信ネットワークに含まれていてもよい例示的な通信ノードのブロック図である。
【図４】パケットのパケット・ヘッダに含まれていてもよい例示的なブルーム・フィルタを概念的に示す図である。
【図５】図１の通信ネットワークにおいてパケットを管理する例示的な方法の流れ図である。
【図６】図１の通信ネットワークにおいてパケットを管理するもう一つの例示的な方法の流れ図である。
【図７】ＡおよびＢは、図６の方法を実装する通信ネットワークのシミュレートされたパフォーマンス特性を描く棒グラフである。みな本稿に記載される少なくともいくつかの実施形態に従って構成される。
【発明を実施するための形態】
【０００９】
本発明の実施形態を付属の図面を参照しつつ説明する。
【００１０】
図１は、本稿に記載される少なくともいくつかの実施形態に従って構成される、パケットが伝送されうる例示的な通信ネットワーク１００を示している。通信ネットワーク１００は、通信媒体（ラベルなし）を介して通信上一緒に結合された複数の通信ノード（以下「ノード」）１０１〜１０７を含む。
【００１１】
通信媒体は電気的、光学的および／または無線のデータ信号を搬送するのに好適ないかなる媒体をも含みうる。たとえば、通信媒体は、これに限られないが、ワイヤ、光ファイバー、無線チャネルまたは他の好適な通信媒体を含んでいてもよい。
【００１２】
通信ネットワーク１００はいかなる好適なネットワーク・トポロジーを有していてもよい。「ネットワーク・トポロジー」は一般に、通信ネットワーク１００内のノード１０１〜１０７がどのように相互接続されているかを記述する。例示的なネットワーク・トポロジーはこれに限られないが、リング・トポロジー、ハブとスポーク・トポロジーおよびメッシュ・トポロジーまたはその任意の組み合わせを含む。よって、図１に示されるネットワーク・トポロジーは単に例として与えられているのであって、本発明を限定するものと解釈すべきではない。
【００１３】
いくつかの実施形態では、通信ネットワーク１００は、冗長性のためにノード１０１〜１０７の間に複数の経路を含んでいてもよい。たとえば、図１に示されるように、ノード１０１とノード１０７の間には二つの経路が存在する。具体的には、ノード１０１とノード１０７の間の一つの経路はノード１０２、１０３、１０４、１０５および１０６を含む。ノード１０１とノード１０７の間の相対的により短い経路はノード１０２、１０５および１０６を含む。冗長性は故障耐性を提供しうる。たとえば、ノード１０２とノード１０５の間の通信リンクに障害がある場合、ノード１０１から送られてノード１０７に宛てられたデータは、故障した通信リンクを迂回するために、ノード１０２、１０３、１０４、１０５および１０６を含む相対的により長い経路に沿ってノード１０７に送られてもよい。
【００１４】
ノード１０１〜１０７のそれぞれは、少なくとも一つの隣接ノード１０１〜１０７を有していてもよい。本稿で使うところの「隣接ノード」とは、介在するノードなしに別のノードに結合されているノードを指してもよい。たとえば、ノード１０２は、ノード１０１、１０３および１０５を含む三つの隣接ノードを含む。さらに、図１は七つのノード１０１〜１０７を示しているが、より一般には、通信ネットワーク１００は、七つ未満のノードまたは七つより多いノードも含め、事実上任意の数のノード１０１〜１０７を含んでいてもよい。代替的または追加的に、ノード１０１〜１０７のそれぞれは、ルータ、スイッチまたは他の通信ノードを含んでいてもよい。さらに、いくつかの実施形態では、ノード１０１〜１０７のそれぞれは一意的なノード識別子を有していてもよい。
【００１５】
ノード１０１〜１０７は、通信ネットワーク１００において他のノード１０１〜１０７とデータを交換するよう構成されていてもよい。たとえば、ノード１０１〜１０７の任意のものは、ノード１０１〜１０７のうち別の一つにデータを送るよう構成されていてもよく、ノード１０１〜１０７のうち前記別のものは前記データを受け取るよう構成されていてもよい。データの起点となるノード１０１〜１０７は源ノードと称されてもよく、データが宛てられるノード１０１〜１０７は宛先ノードと称されてもよい。
【００１６】
源ノードと宛先ノードが隣接ノードどうしでない場合、データは、宛先ノードに到達する前に、一つまたは複数の介在ノードによって転送されてもよい。具体的には、ノード１０１〜１０７のうち所与の一つがノード１０１〜１０７のうち異なるものを宛先ノードとして同定するデータを受信する場合、前記ノードのうち前記所与の一つはそのデータをノード１０１〜１０７の別のものに転送してもよい。各介在ノードは、データの進行経路における「ホップ」と称されてもよい。上記ですでに述べたように、時に、源ノードと宛先ノードの任意の所与の対の間に複数の経路があることがあり、介在ノードは、通信ネットワーク１００における帯域幅要求を最小限にするために、すべての経路で同時にではなく、一時には一つの経路を通じてデータを転送しようと試みてもよい。
【００１７】
データは、伝送のために、源ノードから宛先ノードへのパケットとしてパケット化されてもよい。同じ源ノードからの異なるパケットは、下記でより詳細に論じる、各パケットに関連付けられたパケット識別子によって識別されてもよい。パケット識別子を含むパケットの例について、ここで図２を参照して述べる。
【００１８】
図２は、本稿に記載される少なくともいくつかの実施形態に従って構成される、図１の通信ネットワーク１００を通じて伝送されうる例示的なパケット２００を示している。図２に示されるように、パケット２００はヘッダ２０１およびペイロード２０２を含んでいてもよい。
【００１９】
図１および図２を併せて参照するに、ヘッダ２０１は、通信ネットワーク１００内でパケット２００を扱うための情報を含んでいてもよい。たとえば、ヘッダ２０１は源識別子（ID）２０３、パケットID  ２０４、宛先ID  ２０５および／または通過履歴２０６を含んでいてもよい。
【００２０】
源ID  ２０３は、ノード１０１〜１０７の特定の一つを、そのパケット２００が発した源ノードとして同定してもよい。源ID  ２０３は、これに限られないが、源ノードのノード識別子、源ノードのインターネット・プロトコル（IP:  Internet  Protocol）アドレス、源ノードの媒体アクセス制御（MAC:  Media  Access  Control）アドレスなどまたはその任意の組み合わせを含んでいてもよい。
【００２１】
パケットID  ２０４は、そのパケットが同じ源ノードから発する他のパケットから識別されうるよう、パケット２００を一意的に同定しうる。パケットID  ２０４は、これに限られないが、パケット２００の源ノードによってパケット２００に割り当てられる一意的なシーケンス番号、源ノードからのそのパケットの出発時間を示すタイムスタンプのようなタイムスタンプ、ハッシュ値またはその任意の組み合わせを含んでいてもよい。
【００２２】
宛先ID  ２０５はパケット２００の意図される宛先ノードを同定してもよい。宛先ID  ２０５はたとえば、宛先ノードのノード識別子、宛先ノードのIPアドレス、宛先ノードのMACアドレスなどまたはその任意の組み合わせを含んでいてもよい。
【００２３】
通過履歴２０６は、パケット２００を以前に転送した通信ノードの集合を同定するよう構成されてもよい。通過履歴２０６はこれに限られないが、パケット２００を転送したことのあるノード１０１〜１０７に対応するノード識別子のリスト、ブルーム・フィルタなどを含んでいてもよい。パケット２００が源ノードを初めて出るときには、いくつかの実施形態では、通過履歴２０６は空であってもよい。しかしながら、以下でより詳細に述べるように、パケット２００を別のノードに転送する各ノードが、対応するノードのノード識別子を含めるよう通過履歴を更新してもよい。
【００２４】
ヘッダ２０１は一般に、通信ネットワーク１００内でパケット２００を扱い、経路制御するための情報を含む。対照的に、ペイロード２０２は、通信ネットワーク１００内で源ノードから宛先ノードにルーティングされるデータを含む。パケット２００のペイロード２０２は図２では打ち切られた形で示されており、図では、ヘッダ２０１に比べて相対的に小さくなっているが、一般には、パケット・ペイロードは所与のパケットの大半を占有することがあり、対応するヘッダは所与のパケットの比較的小さな部分しか占有しない。
【００２５】
図１に戻ると、いくつかの実施形態によれば、ノード１０１〜１０７の間の通信リンクには損失があることがある。これはつまり、一部のパケットが、対応する宛先ノードに到達する前に失われることがあるということである。ノード１０１〜１０７によって実装される通信プロトコルは、データ・パケットの受信を受取確認するためにさまざまな機構の任意の一つまたは複数を含んでいてもよい。たとえば、受信ノードが送信者ノードからのパケットの受信に応答して送信者ノードにACKメッセージを送るリンク層受取確認（ACK）機構を実装することができる。しかしながら、パケット自身と同様に、ACKメッセージおよび／または他の受取確認メッセージも失われることがある。よって、ACK機構および／または他の受取確認機構の有効性は制限される。
【００２６】
よって、ノード１０１〜１０７は、所与の経路を介して送られたパケットについてACKメッセージが受信されない場合にノード１０１〜１０７が代替経路を介してパケットを再送する、マルチパス・ルーティング・プロトコルを実装してもよい。たとえば、ノード１０２が、ノード１０１を源ノードとしノード１０７を宛先ノードとして同定するパケットを受信する場合、ノード１０２はまず、ノード１０５および１０６を含む相対的により短い経路を介してそのパケットをノード１０７に転送しようと試みてもよい。ノード１０２がノード１０５にパケットを送ったのち、かつたとえば指定された時間期間が経過したのちに、ノード１０５からACKメッセージを受信しない場合、ノード１０２はそのパケットを、ノード１０３、１０４、１０５および１０６を含む相対的により長い経路に沿って、ノード１０７に再送してもよい。
【００２７】
一部のACKメッセージが失われることがあるので、ノード１０２がノード１０５からパケットの到着を確証するACKメッセージを受け取らなくても、ノード１０２から最初にノード１０５に送られたパケットがノード１０５に到着していることもありうる。この例では、ノード１０２が代替経路を介して、たとえばノード１０３および１０４を介してパケットを再送する場合、再送パケットは「重複パケット」だと考えられる。通信ネットワーク１００内の別のパケット、たとえばノード１０５に無事到着しているパケットの複製だからである。重複パケットは通信ネットワークを輻輳させ、一般に望ましくないものである。
【００２８】
重複パケットはパケットの一つの型である。パケットの他の型は、新規パケット、返送パケットおよびループされたパケットを含む。新規パケットは、ノード１０１〜１０７の所与のものによって以前に受信や転送されていないデータを含むパケットを含む。返送パケットは、そのパケットが進行していた経路において行き止まりに到達したために、前のホップ／ノードに意図的に返されたパケットを含む。パケットを前のホップに返送することによって、前のホップは、代替経路を使ってそのパケットをその意図された宛先に転送しようと試みることができる。ループされたパケットは、以前にそのパケットをすでに転送したことのあるノードに転送されたパケットであり、意図的にそのノードに返送されたのでないパケットを含む。
【００２９】
本稿に記載されるいくつかの実施形態は、パケットID  ２０４および／または通過履歴２０６のようなパケット・ヘッダに含まれる情報に基づいて、重複パケット、返送パケットおよび新規パケットを同定してもよい。新規パケットおよび返送パケットはルーティングされうる一方、重複パケットはドロップされてもよい。それにより本稿で記載されるように、ループが防止される。
【００３０】
たとえば、ノード１０２は、所与のパケットIDをもつパケットをノード１０５に転送してもよく、ノード１０５からACKメッセージを受信しないことに応答して、ノード１０３にそのパケットのコピーを転送してもよい。ノード１０３はそのパケットのそのコピーをノード１０４に転送し、ノード１０４はそのパケットのそのコピーをノード１０５に転送する。前記パケットおよび前記パケットの前記コピーはいずれも同じパケットIDを含んでいてもよい。
【００３１】
前記パケットおよび前記パケットの前記コピーの両方が結果的にノード１０５に到達する場合、最初に受信されたほうはノード１０５によって新規パケットと考えられてもよく、一方、二番目に受信されるほうはノード１０５によって重複パケットと考えられてもよい。たとえば、ノード１０５が前記パケットの前記コピーより前に前記パケットを受信する場合、ノード１０５は前記パケットのヘッダを解析して、ノード１０５が以前に前記パケットのヘッダに含まれるパケットIDをもつパケットを受信していないと判別することによって、前記パケットが新規パケットであると判別してもよい。次いでノード１０５は前記パケットを転送して、ノード１０５によって受信され転送されたパケットのパケットIDの記録を、転送された前記パケットのパケットIDを含めるよう更新してもよい。前記パケットのその後に受信されるコピーのヘッダはノード１０５によって解析されて、前記パケットの前記コピーのヘッダ内のパケットIDをパケットIDの記録と比較することによって、前記パケットの前記コピーが先に受信されたパケットに対する重複パケットであると判別してもよい。
【００３２】
しかしながら、前記パケットの前記コピーが前記パケットより先にノード１０５によって受信される場合、ノード１０５は前記パケットの前記コピーのヘッダを解析して、前記パケットの前記コピーが新規パケットであると判定してもよく、次いで前記パケットの前記コピーを転送してパケットIDの記録を、前記パケットの前記コピーのパケットIDを含めるよう更新してもよい。その後受信される前記パケットのヘッダは解析され、前記パケットが、先に受信された前記パケットの前記コピーに関して重複パケットであると判定してもよい。
【００３３】
識別された重複パケットは、ノード１０２から直接受信されるパケットであろうとノード１０３およびノード１０４を通じて転送された前記パケットの前記コピーであろうと、ドロップされてもよい。重複パケットをドロップすることは、該重複パケットがパケット・ヘッダにおいて指定される宛先ノードに到達する前に、たとえば該重複パケットを転送しないことによって、該重複パケットを通信ネットワーク１００内での流通から除去することを含んでいてもよい。
【００３４】
先述したように、ループされたパケットは、そのパケットを以前にすでに転送したノードに転送されたものであり、そのノードに意図的に返されたのではないパケットを含む。たとえば、ノード１０２はノード１０３に、ノード１０７を宛先ノードとして同定するパケットを転送することがある。ノード１０３はそのパケットをノード１０４に転送してもよく、ノード１０４は次いでそのパケットをノード１０５に転送してもよい。ノード１０５がそのパケットをノード１０２に転送するならば、そのパケットはループされたパケットとなる。ループは、いくつかの実施形態によれば、パケット・ヘッダに含まれていてもよい通過履歴に基づいて回避されうる。
【００３５】
たとえば、そのパケットを転送する各ノードが、そのパケットの通過履歴を、当該転送ノードを同定するよう更新してもよい。こうして、先の例を続けると、パケットをノード１０２に転送し戻すのに先立って、ノード１０５はパケットの通過履歴を解析して、ノード１０２、１０４および１０６を含むその隣接ノードの一つまたは複数が以前にそのパケットを転送したことがあるかどうかを解析してもよい。ノード１０２および１０４が以前にそのパケットを転送したことがあり、ノード１０６は以前にそのパケットを転送したことがないと判定するのに応答して、ノード１０５はそのパケットをノード１０６に転送してもよく、それによりループ生成を回避しうる。
【００３６】
返送パケットは、そのパケットが進行していた経路において行き止まりに到達したために前のホップ／ノードに意図的に返送されたパケットを含んでいてもよい。たとえば、源ノードとしてのノード１０３は、宛先ノードとしてのノード１０７に宛てられたパケットを生成してもよい。ノード１０３はそのパケットをノード１０２に送ってもよい。そのパケットの受信に応答して、ノード１０２はパケットIDの記録を、そのパケットのパケットIDを含めるよう更新してもよく、そのパケットの通過履歴を、ノード１０２のノード識別子を含めるよう更新してもよく、次いでそのパケットをノード１０１に転送してもよい。ノード１０１は図示した実施形態ではパケットをノード１０７に届けるという点では行き止まりなので、ノード１０１は次いで、そのパケットを、ノード１０２に返送してもよい。ノード１０２が返送パケットを受信したのち、ノード１０２は、パケットのパケットIDおよび通過履歴に基づいて、ノード１０２が以前にそのパケットを受信し、転送したことがあり、よってそのパケットが返送パケットであると判定してもよい。次いでノード１０２はそのパケットを、本稿で記載されるようなループを生成することなく、たとえばそのパケットをノード１０５に転送することによって、ノード１０７に転送しようと試みてもよい。
【００３７】
図３は、本稿に記載される少なくともいくつかの実施形態に従って構成される、図１の通信ネットワーク１００に含まれていてもよい例示的なノード３００のブロック図である。ノード３００は、たとえば図１のノード１０１〜１０７のいずれかに対応してもよい。図３に示されるように、ノード３００は処理装置３０２ならびにメモリ３０４およびストレージ３０６のような一つまたは複数のコンピュータ可読記憶媒体を含んでいてもよい。ノード３００はさらに通信インターフェース３０８を含んでいてもよい。
【００３８】
処理装置３０２、メモリ３０４、ストレージ３０６および通信インターフェース３０８は、通信バス３１０を介して通信上結合されていてもよい。通信バス３１０はこれに限られないが、メモリ・バス、ストレージ・インターフェース・バス、バス／インターフェース・コントローラ、インターフェース・バスなどまたはその任意の組み合わせを含みうる。
【００３９】
処理装置３０２は、図５および図６に関して後述される通信ネットワークにおいてパケットを管理する方法のような、本稿に記載される方法または動作の一つまたは複数を実行するよう構成されていてもよい。処理装置３０２は、メモリ３０４にロードされたまたはストレージ３０６に記憶されたコンピュータ命令――時にコンピュータ実行可能命令および／またはコンピュータ可読命令とも称される――を実行することによって、そのような方法または動作を実行するよう構成されていてもよい。処理装置３０２はこれに限られないが、プロセッサ、マイクロプロセッサ、コントローラ、マイクロコントローラ、中央処理ユニット（CPU）または他の好適な処理装置を含みうる。
【００４０】
メモリ３０４は、ランダム・アクセス・メモリ（RAM）または他の揮発性記憶のような揮発性記憶を含んでいてもよい。メモリ３０４はパケットIDキャッシュ３１２およびノードIDキャッシュ３１４を含んでいてもよい。
【００４１】
パケットIDキャッシュ３１２は、ノード３００によって受信され、他のノードに転送されたパケットのパケットIDの記録を含んでいてもよい。パケットIDキャッシュ３１２は、パケットが受信されたあとで、該パケットのパケットIDに基づいて、ノード３００が同じパケットIDをもつ何らかのパケットを以前に受信し、転送したことがあるかどうかを判定するために、ノード３００によって使用されてもよい。その判定はさらに、パケットの源IDに基づいていてもよい。その場合、パケットIDキャッシュ３１２はさらに、以前に受信して転送したことのあるパケットの源IDを含んでいてもよく、および／またはパケットIDキャッシュ３１２中のパケットIDが対応する源IDによってインデックス付けされるまたは他の仕方で整理されていてもよい。
【００４２】
ノードIDキャッシュ３１４は、ノード３００のノード識別子および／またはノード３００の各隣接ノードのノード識別子を含んでいてもよい。代替的または追加的に、ノードIDキャッシュ３１４は、ノード３００によって受信されるパケットに含まれる通過履歴について使われるブルーム（Bloom）・フィルタに関連するk個の既知のハッシュ関数を含んでいてもよい。ノードIDキャッシュ３１４は、パケットが受信された後で、そのパケットの通過履歴に基づいて、ノード３００が単にその特定のパケットと同じパケットIDを含むパケットを以前に転送したことがあるかどうかだけではなく、ノード３００が以前にその特定のパケットを転送したことがあるかどうかを判定するために、ノード３００によって使用されてもよい。
【００４３】
ストレージ３０６は、これに限られないが、読み出し専用メモリ（ROM）、電気的に消去可能かつプログラム可能な読み出し専用メモリ（EEPROM）、半導体記憶デバイス、光学式記憶デバイス、磁気記憶デバイスまたは他の好適な不揮発性記憶といった不揮発性記憶を含んでいてもよい。図３の図示した実施形態では、ストレージ３０６はルーティング・アプリケーション３１６を含む。ルーティング・アプリケーション３１６は、本稿に記載される方法および／または処理の一部または全部を実行するために処理装置３０２によって実行可能なコンピュータ命令を含んでいてもよい。いくつかの実施形態では、ルーティング・アプリケーション３１６は、処理装置３０２によって実行される前にメモリ３０４中にロードされてもよいし、および／またはルーティング・アプリケーション３１６は、メモリ３０４にロードされることなく、ストレージ３０６から１行ずつ処理装置３０２によって実行されてもよい。代替的または追加的に、パケットIDキャッシュ３１２およびノードIDキャッシュ３１２の一方または両方のコピーがストレージ３０６に記憶されてもよい。
【００４４】
通信インターフェース３０８は、通信リンクを通じた一つまたは複数の他のノードとの通信を容易にするよう構成されていてもよい。通信インターフェース３０８はこれに限られないが、ネットワーク・インターフェース・カード、ネットワーク・アダプター、ローカル・エリア・ネットワーク（LAN）アダプターまたは他の好適な通信インターフェースを含みうる。
【００４５】
図４は、本稿に記載される少なくともいくつかの実施形態に従って構成される、パケットのパケット・ヘッダに含まれうる例示的なブルーム・フィルタ４００を概念的に示している。ブルーム・フィルタ４００は、たとえばパケットの通過履歴としてパケットのパケット・ヘッダ中に含まれていてもよく、図２のパケット２００の通過履歴２０６に関して概括的に上述したような、そのパケットを以前に転送したことのある通信ノードの集合を同定するよう構成されていてもよい。
【００４６】
これらおよびその他の実施形態において、ブルーム・フィルタ４００は一般に、ある要素がある集合の一員であるかどうかを試験するために使用されうるn個のビットのビット・シーケンスまたは配列を含んでいてもよい。図４の例では、nは18であり、ブルーム・フィルタ４００は、所与のノードがそのパケットを以前に転送したことのあるノードの集合の一員であるかどうかを判定するために、パケット中の通過履歴として特に使用されてもよい。要素、あるいはこの場合にはノードは、その集合に追加されてもよいが、その集合から除去されることはない。
【００４７】
最初、ブルーム・フィルタ４００中のm個のビットまたは配列位置のそれぞれは0に設定されてもよい。いくつかの実施形態では、ブルーム・フィルタ４００には、k個の異なるハッシュ関数が関連付けられていてもよく、そのそれぞれが、ノードまたは各ノードに関連付けられた一意的に識別するデータを、一様なランダム分布をもってm個の配列位置のうちの対応するものにマッピングする――あるいはハッシュする――。次いで、k個の結果として得られる配列位置は1に設定されてもよい。図４の例では、kは3であり、k個の異なるハッシュ関数が所与のノードのノード識別子に適用され、該所与のノード、またはより詳細には該所与のノードのノード識別子をブルーム・フィルタ４００に追加してもよい。
【００４８】
より詳細には、たとえば図４に関し、三つの要素x、y、zがブルーム・フィルタ４００において同定される。三つのハッシュ関数kが三つの要素x、y、zのそれぞれのノード識別子に適用されて、ノード識別子のそれぞれが図４に示されるように三つの対応する配列位置にマッピングされてもよい。図示した実施形態では、各識別子に対応する三つの配列位置が1に設定されている。
【００４９】
たとえばノードwが、対応するパケットを転送したことのあるノードx、y、zの集合の一員であるかどうかを試験するために、ノードwに対応するノード識別子を含めることについてブルーム・フィルタ４００に問い合わせするために、ノードwのノード識別子に三つにハッシュ関数kが適用されてもよく、三つの対応する配列位置が得られてもよい。その各位置は図４に示されている。図４から、ノードwに対応する最初の二つの配列位置のそれぞれが1に設定されており、一方、第三の配列位置が0に設定されていることが見て取れる。ノードwに対応する第三の配列位置が0に設定されているので、ノードwのノード識別子はブルーム・フィルタ４００に追加されておらず、よってノードwは対応するパケットを転送したことのあるノードの集合の一員ではない。より一般に、任意の時点において、所与のノードまたはノード識別子に対応するブルーム・フィルタ４００中の何らかの配列位置が1でなく0に設定されていたら、たとえ所与のノードまたはノード識別子に対応する他の配列位置のすべてが1に設定されていたとしても、所与のノードは対応するパケットを以前に転送したことのあるノードの集合の一員ではないと判定されてもよい。
【００５０】
図５は、本稿に記載される少なくともいくつかの実施形態に従って構成される、図１の通信ネットワークにおいてパケットを管理する例示的な方法５００の流れ図である。方法５００はいくつかの実施形態では、全体的にまたは部分的に、図１の通信ネットワーク１００のノード１０１〜１０７の一つまたは複数または図３のノード３００のような通信ネットワークの一つまたは複数のノードによって実装されてもよい。簡単のため、方法５００は、第一の通信ノード（「第一のノード」）によって実行されるものとして論じられる。方法５００は、ブロック５０１〜５０４の一つまたは複数によって示されるような、一つまたは複数のステップ、工程または動作を有していてもよい。
【００５１】
ブロック５０１では、パケットが受信される。たとえば、パケットは、別のノードから前記第一のノードによって受信されてもよい。パケットは、図２のヘッダ２０１のようなパケット・ヘッダを含んでいてもよい。パケット・ヘッダは、図２のパケットID  ２０４のような、パケットを一意的に識別するパケットIDを含んでいてもよい。
【００５２】
ブロック５０２において、第一のノードによって受信されたパケットのパケット型が、パケットのパケットIDに基づいて判別されてもよい。パケット型はたとえば、重複、返送または新規を含んでいてもよく、よって、パケットのパケット型の判別は、そのパケットが重複パケットであるか、返送パケットであるか、新規パケットであるかを判別することを含んでいてもよい。
【００５３】
パケットIDに基づいてパケットのパケット型を判別することは、パケットIDを第一のノードにおいて受信された諸パケットに対応するパケット識別子のリストと比較し；前記比較に基づいて、そのパケットと同じパケットIDを有する別のパケットが第一のノードにおいて受信されたことがあるかどうかを判定し；そのパケットと同じパケット識別子をもつ別のパケットが第一の通信ノードにおいて受信されたことがあると判定されるとき、パケット・ヘッダに含まれる通過履歴に基づいて第一のノードがそのパケットを転送したことがあるかどうかを判定することを含んでいてもよい。これらおよびその他の実施形態において、通過履歴は、そのパケットを転送したことのある通信ノードの集合を同定するよう構成されたリストまたはブルーム・フィルタを含んでいてもよい。
【００５４】
代替的または追加的に、パケット識別子に基づいてパケットのパケット型を判別することは、パケット識別子に基づいてそのパケットが第一のノードにおいて以前に受信されたことがないと判定することを含んでいてもよい。
【００５５】
図５に戻ると、ブロック５０３において、パケットが重複パケットであると判定される場合、そのパケットはドロップされてもよい。先述したように、重複パケットをドロップすることは、該重複パケットがパケット・ヘッダにおいて指定される宛先ノードに到達する前に、該重複パケットを通信ネットワーク内での流通から除去することを含んでいてもよい。
【００５６】
あるいはまた、ブロック５０４において、そのパケットが返送パケットまたは新規パケットであると判別される場合、そのパケットがループに捉えられるのを防ぐ仕方で、そのパケットは隣接ノードにルーティングされてもよい。そのパケットがループに捉えられるのを防ぐ仕方でそのパケットを隣接ノードにルーティングすることは：第一のノードの隣接ノードの集合からそのパケットを転送する転送先の第二のノードを選択し；パケット・ヘッダに含まれる通過履歴に基づいて第二のノードがそのパケットを転送したことがあるかどうかを判定し；第二のノードがそのパケットを転送したことがないと判定される場合にはそのパケットを第二のノードに転送するまたは第二のノードがそのパケットを転送したことがあると判定される場合にはそのパケットを転送する転送先の代替的な隣接ノードを選択するの一方を行う、ことを含んでいてもよい。通過履歴に基づいて第二のノードがそのパケットを以前に転送したことがあるかどうかを判定することは、本稿で述べたように、第一のノードのノード識別子が通過履歴に含まれているかどうかが判定されうるのと同様の仕方で、そのパケットの通過履歴に第二のノードのノード識別子が含まれているかどうかを判定することを含んでいてもよい。
【００５７】
より一般的には、パケットがループに捉えられるのを防ぐ仕方でそのパケットを隣接ノードにルーティングすることは、そのパケットの通過履歴に基づいてその隣接ノードがそのパケットを転送したことがないことを判別し；そのパケットをその隣接ノードの転送することを含んでいてもよい。
【００５８】
当業者は、本稿に開示されるこのおよび他のプロセスおよび方法のために、該プロセスおよび方法において実行される機能が異なる順序で実装されてもよいことを理解するであろう。さらに、概説されるステップおよび動作は単に例として与えられているのであって、開示される実施形態の本質から外れることなく、該ステップおよび動作の一部が任意的であることもあり、より少数のステップおよび動作に組み合わされてもよく、あるいは追加的なステップおよび動作に展開されてもよい。
【００５９】
たとえば、パケットが新規パケットであると判別される場合、方法５００はさらに、そのパケットを隣接ノードに転送するのに先立って、通過履歴を、第一のノードのノード識別子を含めるように更新することを含んでいてもよい。このおよびその他の実施形態において、方法５００はさらに：そのパケットを転送する転送先の異なる隣接ノードを選択し；前記通過履歴に基づいて前記異なる隣接ノードがそのパケットを以前に転送したことがあることを判別し；前記異なる隣接ノードがそのパケットを以前に転送したことがあることを判別するのに応答して、その代わりに、そのパケットを転送する転送先の前記隣接ノードを選択し；前記通過履歴に基づいて前記隣接ノードがそのパケットを以前に転送したことがないことを判別することを含んでいてもよい。
【００６０】
方法５００が新規パケットの通過履歴を更新することを含むいくつかの実施形態では、通過履歴はブルーム・フィルタを含んでいてもよい。このおよび他の実施形態において、通過履歴を、第一のノードのノード識別子を含めるよう更新することは、第一のノードのノード識別子に対してブルーム・フィルタに関連付けられたk個の既知のハッシュ関数を計算して、ブルーム・フィルタ中のk個の対応する配列位置を決定することを含んでいてもよい。次いで、ブルーム・フィルタ中のk個の対応する配列位置のそれぞれにおけるビットが、すでに1に設定されていなければ、1に設定されてもよい。
【００６１】
方法５００が新規パケットの通過履歴を更新することを含む他のいくつかの実施形態では、通過履歴はその新規パケットを転送したことのあるノードに対応するノード識別子のリストを含んでいてもよい。このおよび他の実施形態において、通過履歴を、第一のノードのノード識別子を含めるよう更新することは、新規パケットを転送する前に、新規パケットのノード識別子のリストに、第一のノードのノード識別子を追加することを含んでいてもよい。
【００６２】
もう一つの例として、いくつかの実施形態では、パケット型の判別は、そのパケットのパケットIDおよび以前に受信されたパケットのパケットIDの両方に基づいていてもよい。以前に受信されたパケットのパケットIDは、図３のメモリ３０４および／またはストレージ３０６のようなコンピュータ可読記憶媒体に記憶されていてもよい。パケットIDは、たとえば図３のパケットIDキャッシュ３１２のようなパケットIDキャッシュの形でコンピュータ可読記憶媒体中に記憶されてもよい。これらおよび他の実施形態において、パケットのパケット型を判別することは：そのパケットのパケットIDをそれらのパケットIDと比較し；前記比較に基づいて、そのパケットと同じパケットIDをもつ別のパケットが第一のノードにおいて受信されたことがあるかどうかを判定し；そのパケットと同じパケット識別子をもつ別のパケットが対応する通信ノードにおいて受信されたことがあると判定された場合、そのパケットのパケット・ヘッダに含まれる通過履歴に基づいて第一のノードがそのパケットを転送したことがあるかどうかを判定することを含んでいてもよい。
【００６３】
いくつかの実施形態では、通過履歴はブルーム・フィルタを含んでいてもよい。これらおよび他の実施形態において、パケットのパケット型を判別することは、第一のノードのノード識別子がブルーム・フィルタに存在しないことを判定すること（そのときそのパケットは重複パケットであると判定される）を含んでいてもよく、それは：そのノード識別子に対してそのブルーム・フィルタに関連付けられたk個の既知のハッシュ関数を計算してブルーム・フィルタ中のk個の対応する配列位置を決定し；ブルーム・フィルタ中のk個の対応する配列位置が1のビットまたは0のビットのどちらを含むかを検査し；k個の対応する配列位置の少なくとも一つが0のビットを含む場合にそのノード識別子がブルーム・フィルタに存在しないと判定することを含む。
【００６４】
他の実施形態では、通過履歴は、そのパケットを転送したことがある通信ノードに対応するノード識別子のリストを含んでいてもよい。このおよび他の実施形態では、パケットのパケット型を判別することは、第一のノードのノード識別子がノード識別子のリストに存在しないことを判別すること（そのときそのパケットが重複パケットであると判別される）を含んでいてもよい。
【００６５】
図６は、本稿に記載される少なくともいくつかの実施形態に従って構成される、図１の通信ネットワークにおいてパケットを管理するもう一つの例示的な方法６００の流れ図である。方法６００はいくつかの実施形態では、全体的にまたは部分的に、図１の通信ネットワーク１００のノード１０１〜１０７の一つまたは複数または図３のノード３００のような通信ネットワークの一つまたは複数のノードによって実装されてもよい。簡単のため、方法６００は、図３のノード３００によって実行されるものとして論じられる。しかしながら、より詳細には、方法６００の一部または全部は、ノード３００の処理装置３０２によって実行されてもよい。方法６００は、ブロック６０１〜６０９の一つまたは複数によって示されるような、一つまたは複数のステップ、工程または動作を有していてもよい。
【００６６】
図３および図６を併せて参照するに、ブロック６０１では、パケット６１０が受信される。図６のブロック６０１は概括的に図５のブロック５０１に対応しうる。そのパケットは、別のノードからノード３００によって受信されてもよい。パケットは、図２のヘッダ２０１のようなパケット・ヘッダを含んでいてもよい。パケット・ヘッダは、図２のパケットID  ２０４のような、パケットを一意的に識別するパケットIDを含んでいてもよい。
【００６７】
ブロック６０２および６０３において、ノード３００は、パケット６１０のパケット型を、受信されたパケット６１０のパケットIDに基づいて判別してもよい。図６のブロック６０２および６０３の一つまたは複数は概括的に図５のブロック５０２に対応しうる。
【００６８】
具体的には、ブロック６０２において、ノード３００は、パケット６１０と同じパケットIDをもつ別のパケットがノード３００によって以前に受信されたことがあるかどうかを判定してもよい。たとえば、ノード３００は、パケット６１０のパケットIDを、パケットIDキャッシュ３１２と比較してマッチを探してもよい。パケット６１０と同じパケットIDをもつ別のパケットがノード３００によって受信されたことがなければ、ノード３００はブロック６０２においてパケット６１０が新規パケット６１０Ａであると判別してもよく、ブロック６０４においてパケットのパケット・ヘッダ中に含まれる通過履歴を更新してもよい。
【００６９】
あるいはまた、ブロック６０２において、パケット６１０と同じパケットIDをもつ別のパケットがノード３００によって受信されたことがあると判定される場合、ノード３００はブロック６０３において、パケット６１０がノード３００によって転送されたことがあるかどうかを判定してもよい。ブロック６０３の判定は、パケット６１０の通過履歴に基づいていてもよい。たとえば、ノード３００は、ノード３００のノード識別子を、パケット６１０の通過履歴と比較して、ノード３００のノード識別子が通過履歴に含まれているかどうかに基づいてノード３００がパケット６１０を転送したことがあるかどうかを判定してもよい。ブロック６０３の判定の個別的詳細は、通過履歴がブルーム・フィルタを含むかパケット６１０を以前に転送したことのあるノードに対応するノード識別子のリストを含むかに依存して異なっていてもよい。
【００７０】
ブロック６０３において、ノード３００がパケット６１０を転送したことがないと判定される場合、ノード３００は、パケット６１０が重複パケット６１０Ｂであると判別してもよく、ブロック６０５において重複パケット６１０Ｂをドロップしてもよい。ブロック６０５は概括的に図５のブロック５０３に対応しうる。
【００７１】
他方、ブロック６０３において、ノード３００がパケット６１０を以前に転送したことがあると判定される場合、ノード３００は、パケット６１０が返送パケット６１０Ｂであると判別してもよい。
【００７２】
ブロック６０６〜６０９において、パケット６１０が新規パケット６１０Ａまたは返送パケット６１０Ｃ（以下では概括的に「パケット６１０Ａ／６１０Ｃ」）であると判別されている場合、ノード３００はパケット６１０Ａ／６１０Ｃがループに捉えられるのを防ぐ仕方でパケット６１０Ａ／６１０Ｃを隣接ノードにルーティングしてもよい。ブロック６０６〜６０９の一つまたは複数が概括的に図５のブロック５０４に対応しうる。
【００７３】
より詳細には、ブロック６０６において、ノード３００は、パケット６１０Ａ／６１０Ｃを転送する転送先の隣接ノードを選択してもよい。
【００７４】
ブロック６０７では、ノード３００は、選択された隣接ノードがパケット６１０Ａ／６１０Ｃを転送したことがあるかどうかを判定してもよい。選択された隣接ノードがパケット６１０Ａ／６１０Ｃを転送したことがあるかどうかを判定することは、選択された隣接ノードのノード識別子がそのパケットの通過履歴に含まれているかどうかを判定することを含んでいてもよい。選択された隣接ノードのノード識別子がそのパケットの通過履歴に含まれていない場合に、選択された隣接ノードがパケット６１０Ａ／６１０Ｃを転送したことがないと判定されてもよい。選択された隣接ノードのノード識別子がそのパケットの通過履歴に含まれている場合は、選択された隣接ノードがパケット６１０Ａ／６１０Ｃを以前に転送したことがあると判定されてもよい。
【００７５】
ブロック６０８では、選択された隣接ノードがパケット６１０Ａ／６１０Ｃを転送したことがないと判定された場合に、ノード３００はパケット６１０Ａ／６１０Ｃを選択された隣接ノードに転送してもよい。
【００７６】
あるいはまた、ブロック６０７における、選択された隣接ノードがパケット６１０Ａ／６１０Ｃを以前に転送したことがあるかどうかの判定は、パケット６１０Ａ／６１０Ｃを選択された隣接ノードに転送することがループを生じさせることを示してもよい。よって、ブロック６０９において、ノード３００は、そのパケットを転送する転送先の代替的な隣接ノードを選択してもよく、方法６００はブロック６０７に戻ってもよい。
【００７７】
本稿に開示されるいくつかの実施形態は、図５〜図６の方法５００および６００の一つまたは複数に含まれる動作、たとえば図５に示されるブロック５０１〜５０４の一つまたは複数によって例示される動作、図６のブロック６０１〜６０９の一つまたは複数によって例示される動作および／またはそれらの変形などを実行するためにプロセッサまたは処理装置によって実行可能なコンピュータ命令が記憶されているコンピュータ可読記憶媒体を含む。コンピュータ可読記憶媒体は、図３のメモリ３０４および／またはストレージ３０６に含まれていてもよい。代替的または追加的に、前記動作を実行する前記プロセッサまたは処理装置は図３の処理装置３０２を含んでいてもよい。
【００７８】
本稿に開示されるいくつかの実施形態は、図５〜図６の方法５００および６００の一つまたは複数に含まれる動作、たとえば図５に示されるブロック５０１〜５０４の一つまたは複数によって例示される動作、図６のブロック６０１〜６０９の一つまたは複数によって例示される動作および／またはそれらの変形などをノードに実行させるコンピュータ命令を実行するよう構成されたプロセッサを含む。前記プロセッサ、コンピュータ命令およびノードはそれぞれたとえば図３の処理装置３０２、ルーティング・アプリケーション３１６およびノード３００に対応してもよい。
【００７９】
本稿に開示されるいくつかの実施形態は、通信ネットワークにおいてパケットを管理するシステムを含む。システムは、通信ネットワークに含まれる複数のノードを含む。各ノードは、複数のパケットIDを記憶するよう構成されたコンピュータ可読記憶媒体を含んでいてもよい。各パケットIDは、対応するノードによって受信される対応するパケットを一意的に識別する。各ノードは、所与のパケットについて、図５〜図６の方法５００および６００の一つまたは複数に含まれる動作、たとえば図５に示されるブロック５０１〜５０４の一つまたは複数によって例示される動作、図６のブロック６０１〜６０９の一つまたは複数によって例示される動作および／またはそれらの変形などを実行することによって、通信ネットワークにおいてパケットを管理するよう構成された処理装置を含んでいてもよい。通信ネットワークは、図１の通信ネットワーク１００に対応してもよく、ノードは図１および図３のノード１０１〜１０７および／またはノード３００に対応してもよい。コンピュータ可読記憶媒体は図３のメモリ３０４および／またはストレージ３０６に対応してもよい。コンピュータ可読記憶媒体上に記憶される複数のパケットIDは図３のパケットIDキャッシュ３１２に含まれていてもよい。処理装置は図３の処理装置３０２に対応してもよい。
【００８０】
図７のＡおよびＢは、本稿に記載される少なくともいくつかの実施形態に従って構成される、図６の方法を実装する通信ネットワークのシミュレートされたパフォーマンス特性を描く棒グラフである。図７のＡ〜Ｂのシミュレートされたパフォーマンス特性は、IEEE802.11リンク層を通じて通信するランダムに配置された非モバイル・ノードおよび各ノードから一つのコントローラに送られるデータ・トラフィックについて、OMNESTとして知られるシミュレーション・ソフトウェアを使って計算された。
【００８１】
シミュレートされたパフォーマンス特性は、図７のＡにおける送信されたフレームおよび図７のＢにおける送達比を含む。シミュレートされたパフォーマンス特性は、三つの型のパケット・ルーティング・プロトコルについて与えられている。該三つの型は、標準的なIP転送、国際公開WO2011/013165A1に記載されるマルチパス・パケット・ルーティング・プロトコルおよび本稿に記載されるマルチパス・パケット・ルーティング・プロトコルを含む。上記のパケット・ルーティング・プロトコルはそれぞれタイプ１、タイプ２およびタイプ３として図７のＡ〜Ｂに示されている。
【００８２】
図７のＡに示されるように、本稿で記載したタイプ３のマルチパス・パケット・ルーティング・プロトコルの実施形態は、タイプ２のマルチパス・ルーティング・プロトコルに比べて、たとえば重複パケットを識別してドロップすることにより、送信されるフレーム総数を実質的に削減しうる。一方、タイプ１の標準的なIP転送に比べると、送信されるフレーム総数をわずかに増やすだけである。図７のＢに示されるように、本稿で記載したタイプ３のマルチパス・パケット・ルーティング・プロトコルの実施形態の信頼性、たとえば送達比は、タイプ２のマルチパス・パケット・ルーティング・プロトコルの信頼性と同様でありえ、タイプ１の標準的なIP転送の信頼性よりも実質的によい。
【００８３】
本稿に記載される実施形態は、以下で詳細に論じるような、さまざまなコンピュータ・ハードウェアまたはソフトウェア・モジュールを含む特殊目的または汎用のコンピュータの使用を含んでいてもよい。
【００８４】
本稿に記載される実施形態は、コンピュータ実行可能命令またはデータ構造を担持するまたは記憶しているコンピュータ可読媒体を使って実装されてもよい。そのようなコンピュータ可読媒体は、汎用または特殊目的コンピュータによってアクセスされうるいかなる利用可能な媒体であってもよい。限定ではなく例として、そのようなコンピュータ可読媒体は、RAM、ROM、EEPROM、CD-ROMまたは他の光ディスク記憶、磁気ディスク記憶または他の磁気記憶デバイスまたはコンピュータ実行可能命令またはデータ構造の形の所望されるプログラム・コードを担持もしくは記憶するために使用でき汎用もしくは特殊目的コンピュータによってアクセスできる他の任意の媒体を含む有形のコンピュータ可読記憶媒体を含んでいてもよい。上記のものの組み合わせもコンピュータ可読媒体の範囲内に含まれうる。
【００８５】
コンピュータ実行可能命令はたとえば、汎用コンピュータ、特殊目的コンピュータまたは特殊目的処理装置に、ある機能または一群の機能を実行させる命令およびデータを含む。主題は構造的な特徴および／または方法論的な工程に固有の言語で記述されてきたが、付属の請求項において定義される主題は必ずしも上記の特定の特徴または工程に限定されないことは理解しておくものとする。むしろ、上記の個別的な特徴および工程は請求項を実装する例示的な形として開示されているのである。
【００８６】
本稿での用法では、「モジュール」または「コンポーネント」の用語は、コンピューティング・システム上で実行されるソフトウェア・オブジェクトまたはルーチンを指しうる。本稿に記載される種々のコンポーネント、モジュール、エンジンおよびサービスは、コンピューティング・システム上で実行されるオブジェクトまたはプロセスとして（たとえば別個のスレッドとして）実装されてもよい。本稿に記載されるシステムおよび方法は、好ましくはソフトウェアにおいて実装されるが、ハードウェアまたはソフトウェアとハードウェアの組み合わせにおける実装も可能であり、考えられている。本稿において、「コンピューティング・エンティティ」は、本稿で先に定義した任意のコンピューティング・システムまたはコンピューティング・システム上で走る任意のモジュールもしくはモジュレットの組み合わせであってよい。
【００８７】
本稿に記載されるあらゆる例および条件付きの言辞は読者が本発明および当該技術を発達させるために発明者によって寄与される概念を理解するのを助ける教育上の目的のために意図されており、そのように個別的に記載されている例および条件に限定することなく解釈されるものとする。本発明の実施形態について詳細に記述してきたが、本発明の精神および範囲から外れることなく、それにさまざまな変更、置換および改変ができることは理解しておくべきである。
【００８８】
以上の実施例を含む実施形態に関し、さらに以下の付記を開示する。
（付記１）
複数の通信ノードを含む通信ネットワークにおいてパケットを管理する方法であって：
パケット・ヘッダを含むパケットを受信する段階であって、前記パケット・ヘッダは前記パケットを一意的に識別するパケット識別子を含む、段階と；
前記パケット識別子に基づいて、第一の通信ノードによって受信された前記パケットのパケット型を判別する段階と；
前記パケットが重複パケットであると判別されたときには前記パケットをドロップする；または
前記パケットが返送パケットまたは新規パケットであると判別されたときには、前記パケットがループに捉えられるのを防ぐ仕方で、前記パケットを隣接通信ノードにルーティングする段階とを含む、
方法。
（付記２）
前記判別する段階が：
前記パケット識別子を、前記第一の通信ノードにおいて受信されたパケットに対応するパケット識別子のリストと比較し；
前記比較に基づいて、前記パケットと同じパケット識別子を有する別のパケットが前記第一の通信ノードにおいて受信されたことがあるかどうかを判定し；
前記パケットと同じパケット識別子をもつ別のパケットが前記第一の通信ノードにおいて受信されたことがあると判定されるとき、前記パケット・ヘッダに含まれる通過履歴に基づいて前記第一の通信ノードが前記パケットを転送したことがあるかどうかを判定することを含む、
付記１記載の方法。
（付記３）
前記通過履歴が、前記パケットを転送したことのある通信ノードの集合を同定するよう構成されたリストまたはブルーム・フィルタを含む、付記２記載の方法。
（付記４）
前記ルーティングする段階が：
前記第一の通信ノードの隣接通信ノードの集合から前記パケットを転送する転送先の第二の通信ノードを選択し；
前記パケット・ヘッダに含まれる通過履歴に基づいて前記第二の通信ノードが前記パケットを転送したことがあるかどうかを判定し；
前記第二の通信ノードが前記パケットを転送したことがないと判定される場合には前記パケットを前記第二の通信ノードに転送する、または
前記第二の通信ノードが前記パケットを転送したことがあると判定される場合には前記パケットを転送する転送先の代替的な隣接前記ノードを選択するの一方を行う、
ことを含む、
付記１記載の方法。
（付記５）
前記判別する段階は、前記パケット識別子に基づいて、前記パケットが前記第一の通信ノードにおいて以前に受信されたことがないと判定することを含む、付記１記載の方法。
（付記６）
前記パケットを前記隣接通信ノードに転送するのに先立って、前記パケット・ヘッダに含まれる通過履歴を、前記第一の通信ノードのノード識別子を含めるよう更新する段階をさらに含む、付記５記載の方法。
（付記７）
前記パケットを転送する転送先の異なる隣接通信ノードを選択し；
前記通過履歴に基づいて前記異なる隣接通信ノードが前記パケットを以前に転送したことがあることを判別し；
前記異なる隣接通信ノードが前記パケットを以前に転送したことがあることを判別するのに応答して、その代わりに、前記パケットを転送する転送先の前記隣接通信ノードを選択し；
前記通過履歴に基づいて、前記隣接通信ノードが前記パケットを以前に転送したことがないことを判別することをさらに含む、
付記６記載の方法。
（付記８）
前記ドロップする段階が、前記重複パケットが前記パケット・ヘッダにおいて指定される宛先ノードに到達する前に、前記重複パケットを前記通信ネットワーク内での流通から除去することを含む、付記１記載の方法。
（付記９）
通信ネットワークにおいてパケットを管理するシステムであって、前記通信ネットワークに含まれる複数の通信ノードを有しており、各通信ノードは処理装置を有しており、前記処理装置は：
対応する通信ノードによって受信されたパケットのパケット型を、複数のパケット識別子および前記パケットのパケット・ヘッダに含まれるパケット識別子に基づいて判別し；
前記パケットが重複パケットであると判別されたときには前記パケットをドロップし；あるいは；
前記パケットが返送パケットまたは新規パケットであると判別されたときには、前記パケットがループに捉えられるのを防ぐ仕方で、前記パケットを隣接通信ノードにルーティングするよう構成されている、
システム。
（付記１０）
前記判別する処理が：
前記パケット識別子を、前記対応する通信ノードにおいて受信されたパケットに対応する前記複数のパケット識別子のリストと比較し；
前記比較に基づいて、前記パケットと同じパケット識別子を有する別のパケットが前記対応する通信ノードにおいて受信されたことがあるかどうかを判定し；
前記パケットと同じパケット識別子をもつ別のパケットが前記対応する通信ノードにおいて受信されたことがあると判定されるとき、前記パケットの前記パケット・ヘッダに含まれる通過履歴に基づいて前記対応する通信ノードが前記パケットを転送したことがあるかどうかを判定することを含む、
付記９記載のシステム。
（付記１１）
前記ルーティングする処理が：
前記パケット・ヘッダに含まれる通過履歴に基づいて、前記隣接通信ノードが前記パケットを転送したことがないことを判定し；
前記パケットを前記隣接通信ノードに転送することを含む、
付記９記載のシステム。
（付記１２）
前記処理装置がさらに、各新規パケットの対応するパケット・ヘッダに含まれる通過履歴を、前記対応する通信ノードのノード識別子を含めるよう更新するよう構成されている、付記９記載のシステム。
（付記１３）
前記通過履歴がブルーム・フィルタを含み、前記処理装置が前記通過履歴を更新する処理が：
前記対応する通信ノードのノード識別子に対して前記ブルーム・フィルタに関連付けられたk個の既知のハッシュ関数を計算して、前記ブルーム・フィルタ中のk個の対応する配列位置を決定し；
前記ブルーム・フィルタ中の前記k個の対応する配列位置のそれぞれにおけるビットを、すでに1に設定されていなければ、1に設定することを含む、
付記１２記載のシステム。
（付記１４）
前記対応する通信ノードが第一の通信ノードであり、
前記通過履歴が、対応する新規パケットを転送したことのある通信ノードに対応するノード識別子のリストを含み；
前記処理装置が前記通過履歴を更新する処理が、前記処理装置が、対応する新規パケットを転送する前に、ノード識別子の前記リストに前記第一の通信ノードのノード識別子を追加することを含む、
付記１２記載のシステム。
（付記１５）
通信ノードに、該通信ノードを含む通信ネットワークにおいてパケットを管理するための動作を実行させる命令を記憶している非一時的なコンピュータ可読記憶媒体であって、前記動作は：
パケット・ヘッダを含むパケットを受信する段階であって、前記パケット・ヘッダは前記パケットを一意的に識別するパケット識別子を含む、段階と；
前記パケット識別子に基づいて、第一の通信ノードによって受信された前記パケットのパケット型を判別する段階と；
前記パケットが重複パケットであると判別されたときには前記パケットをドロップする；または
前記パケットが返送パケットまたは新規パケットであると判別されたときには、前記パケットがループに捉えられるのを防ぐ仕方で、前記パケットを隣接通信ノードにルーティングする段階とを含む、
非一時的なコンピュータ可読記憶媒体。
（付記１６）
前記パケット・ヘッダが、前記パケットを転送したことのある通信ノードの集合を同定するよう構成された通過履歴を含む、付記１５記載の被一時的なコンピュータ可読記憶媒体。
（付記１７）
付記１６記載の非一時的なコンピュータ可読記憶媒体であって、前記通過履歴がブルーム・フィルタを含み、前記判別する段階が、前記パケットが重複パケットであると判別されるときに前記通信ノードのノード識別子が前記ブルーム・フィルタに存在しないと判定することを含み、該存在しないと判定することが：
前記ノード識別子に対して前記ブルーム・フィルタに関連付けられたk個の既知のハッシュ関数を計算して、前記ブルーム・フィルタ中のk個の対応する配列位置を決定し；
前記k個の対応する配列位置が1のビットまたは0のビットのどちらを含むかを検査し；
前記k個の対応する配列位置の少なくとも一つが0のビットを含む場合に、前記ノード識別子が前記ブルーム・フィルタに存在しないと判定することを含む、
非一時的なコンピュータ可読記憶媒体。
（付記１８）
付記１６記載の非一時的なコンピュータ可読記憶媒体であって、
前記通信ノードが第一の通信ノードであり、
前記通過履歴が、前記パケットを転送したことのある通信ノードに対応するノード識別子のリストを含み；
前記判別する段階が、前記パケットが重複パケットであると判別されるときに前記第一の通信ノードのノード識別子がノード識別子の前記リストに存在しないと判定することを含む、
非一時的なコンピュータ可読記憶媒体。
（付記１９）
前記ドロップする段階が、前記重複パケットが前記パケット・ヘッダにおいて指定される宛先ノードに到達する前に、前記重複パケットを前記通信ネットワーク内での流通から除去することを含む、付記１５記載の非一時的なコンピュータ可読記憶媒体。
（付記２０）
前記パケット識別子が：前記パケットの源によって前記パケットに割り当てられる一意的なシーケンス番号、前記源からの前記パケットの出発時間を示すタイムスタンプおよびハッシュ値のうちの少なくとも一つを含む、付記１５記載の非一時的なコンピュータ可読記憶媒体。
【符号の説明】
【００８９】
１００  通信ネットワーク
１０１〜１０７  ノード
２００  パケット
２０１  ヘッダ
２０２  ペイロード
２０３  源ID
２０４  パケットID
２０５  宛先ID
２０６  通過履歴
２０２  データ
３００  ノード
３０２  処理装置
３０４  メモリ
３０６  ストレージ
３０８  通信インターフェース
３１２  パケットIDキャッシュ
３１４  ノードIDキャッシュ
３１６  ルーティング・アプリケーション
４００  ブルーム・フィルタ
５００  方法
５０１  パケットを受信
５０２  パケットのパケット種別を決定
５０４  ループを生じることなくパケットを隣接ノードに経路制御
５０３  パケットをドロップ
６００  方法
６１０  パケット
６０１  パケットを受信
６０２  同じパケットIDのパケットが以前に受信されたか？
６０３  そのパケットがノードによって以前に転送されたか？
６０４  通過履歴を更新
６０５  パケットをドロップ
６０６  パケットを転送する隣接ノードを選択
６０７  選択された隣接ノードはそのパケットを以前に転送したか？
６０８  パケットを選択された隣接ノードに転送
６０９  パケットを転送する代わりの隣接ノードを選択
６１０Ａ  新規パケット
６１０Ｂ  重複パケット
６１０Ｃ  返送パケット
【図１】
0006264743.tif 000002
【図２】
0006264743.tif 000003
【図３】
0006264743.tif 000004
【図４】
0006264743.tif 000005
【図５】
0006264743.tif 000006
【図６】
0006264743.tif 000007
【図７】
0006264743.tif 000008