【手続補正書】
【提出日】平成24年11月28日(2012.11.28)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ネットワークを介してパケットを経路指定する方法であって、前記ネットワークのノードにおいて、
（ａ）前記パケット（Ｐ）を受信するステップ（Ｓ１）であり、
前記ノードが、それぞれが少なくとも１つのリンクＩＤと関連付けられている複数の発信リンク（２０）を利用することができ、前記複数のリンク（２０）のうちの少なくとも１つが複数のリンクＩＤと関連付けられており、
前記パケット（Ｐ）が、状態変数と、前記ネットワークを通る経路を形成する個々のリンクと関連付けられたリンクＩＤの集合を符号化している経路指定情報とを含み、
前記符号化が、フォールスポジティブの可能性を有する、リンクＩＤが前記リンクＩＤの集合のメンバであるかどうかの検査に使用される確率的データ構造の形態であるステップと、
（ｂ）前記複数の発信リンク（２０）のそれぞれについて、
（ｉ）リンクが複数のリンクＩＤと関連付けられている場合に、前記受信されたパケット（Ｐ）からの前記状態変数またはステップ（ｃ）で決定される新しい状態変数を使って、ステップ（ｂ）（ｉｉ）のための前記関連付けられたリンクＩＤとしてどのリンクＩＤを使用すべきか判定するステップ（Ｓ４）、ならびに
（ｉｉ）前記データ構造を前記リンクと関連付けられたリンクＩＤのメンバであるかどうか検査するステップ（Ｓ５）と、
（ｃ）前記受信されたパケット（Ｐ）からの前記状態変数に少なくとも部分的に基づいて、新しい状態変数を決定するステップ（Ｓ７）と、
（ｄ）前記ステップ（ｂ）（ｉｉ）で前記データ構造のメンバとしての前記リンクと関連付けられたリンクＩＤを有すると判定された各リンクに沿って、前記経路指定情報と前記新しい状態変数とを含む前記パケット（Ｑ）を転送するステップ（Ｓ８）と
を含み、
ステップ（ｂ）（ｉｉ）の前記検査において発生するフォールスポジティブによりループが発生し、前記ノードで同じパケットが受信される場合に、ステップ（ａ）において再度受信され、かつ、ステップ（ｂ）（ｉｉ）の検査のための前記関連付けられたリンクＩＤを決定するためにステップ（ｂ）（ｉ）において再度使用される前記状態変数が、同じパケットが以前前記ノードにより受信されたことがあるためにステップ（ｃ）の実行を通して更新され、ループの再出現を回避する確率を増加する方法。
【請求項２】
前記データ構造がブルームフィルタを含む請求項１に記載の方法。
【請求項３】
前記ステップ（ａ）で受信される前記パケットが指標値を含み、前記指標値を使用して関数を決定し、前記決定された関数を使用し、前記状態変数を前記関数への入力として前記ステップ（ｂ）（ｉ）の前記判定を行い、前記ステップ（ｄ）で転送される前記パケットが前記指標値を含む、請求項１または２に記載の方法。
【請求項４】
前記複数のリンクがそれぞれ複数のリンクＩＤと関連付けられている請求項１〜３のいずれか一項に記載の方法。
【請求項５】
前記複数のリンクがそれぞれ同数のリンクＩＤと関連付けられている請求項４に記載の方法。
【請求項６】
前記パケットにより搬送される有効期間変数を前記状態変数として使用する請求項１〜５のいずれか一項に記載の方法。
【請求項７】
前記各リンクが前記ノードと前記ネットワークの個々の別のノードとの間の個々の通信経路を表し、前記リンクと関連付けられたリンクＩＤが前記通信経路または前記別のノード、あるいは前記通信経路と前記別のノードの両方を識別する、請求項１〜６のいずれか一項に記載の方法。
【請求項８】
ネットワークを介してパケットを経路指定する方法であって、前記ネットワークを通る経路に沿った複数のノードのそれぞれにおいて、請求項１〜７のいずれか一項に記載の方法を実行するステップを含む方法。
【請求項９】
請求項８に記載の方法において使用される前記経路指定情報を提供する方法であって、前記ネットワークを通る前記経路に沿った前記複数のノードのそれぞれについて、（Ａ）前記状態変数が、前記ステップ（ｃ）で前記経路に沿った前の各ノードによりどのように更新されるかに従って、前記状態変数が前記ノードに到達するときに前記状態変数が何になるか判定するステップと、（Ｂ）前記経路の一部を形成する発信リンクごとに、（ｉ）前記リンクに複数のリンクＩＤが関連付けられている場合に、前記ステップ（Ａ）で判定された前記状態変数を使って、ステップ（Ｂ）（ｉｉ）のための前記関連付けられたリンクＩＤとしてどのリンクＩＤを使用すべきか選択するステップと、（ｉｉ）前記リンクと関連付けられたリンクＩＤを前記経路指定情報の前記データ構造へと符号化するステップとを含む方法。
【請求項１０】
前記ネットワークのノードとしてまたは前記ネットワークの前記ノードの一部として使用されてネットワークを介してパケット（Ｐ）を経路指定する装置であって、前記ノードが、それぞれが少なくとも１つのリンクＩＤと関連付けられている複数の発信リンク（２０）を利用することができ、前記複数のリンク（２０）のうちの少なくとも１つが複数のリンクＩＤと関連付けられており、前記パケット（Ｐ）が、状態変数と、前記ネットワークを通る経路を形成する個々のリンクと関連付けられたリンクＩＤの集合を符号化している経路指定情報とを含み、前記符号化が、フォールスポジティブの可能性を有する検査であって、リンクＩＤが前記リンクＩＤの集合のメンバであるかどうかの検査に使用される確率的データ構造の形態であり、当該装置が、
（ａ）前記パケット（Ｐ）を受信する手段（２）と、
（ｂ）前記複数の発信リンク（２０）のそれぞれについて、
（ｉ）前記リンクに複数のリンクＩＤが関連付けられている場合に、前記受信されたパケット（Ｐ）からの前記状態変数または決定手段（ｃ）で決定される新しい状態変数を使って、ステップ（ｂ）（ｉｉ）のための前記関連付けられたリンクＩＤとしてどのリンクＩＤを使用すべきか判定するステップと、
（ｉｉ）前記データ構造を前記リンクと関連付けられたリンクＩＤのメンバであるかどうか検査するステップと
を実行する手段（４、８、１０、１２、１４）と、
（ｃ）前記受信されたパケットからの前記状態変数に少なくとも部分的に基づいて、新しい状態変数を決定する手段（６）と、
（ｄ）前記ステップ（ｂ）（ｉｉ）で、前記データ構造のメンバとしての前記リンクと関連付けられたリンクＩＤを有すると判定された各リンクに沿って、前記経路指定情報と前記新しい状態変数とを含む前記パケット（Ｑ）を転送する手段（１６、１８）と
を備え、
ステップ（ｉｉ）の前記実行手段（ｂ）により実行される前記検査において発生するフォールスポジティブによりループが発生し、前記ノードで同じパケットが受信される場合に、前記受信手段（ａ）において再度受信され、かつ、ステップ（ｉｉ）の前記検査のための前記関連付けられたリンクＩＤを決定するためにステップ（ｉ）において前記実行手段（ｂ）により再度使用される前記状態変数が、同じパケットが以前前記ノードにより受信されたことがあるために更新され、ループの再出現を回避する確率を増加する装置。
【請求項１１】
前記データ構造がブルームフィルタを含む請求項１０に記載の装置。
【請求項１２】
前記受信する手段（ａ）によって受信される前記パケットが指標値を含む場合に、前記実行する手段（ｂ）が前記指標を使って関数を決定するように構成されており、前記ステップ（ｉ）の前記判定が、前記状態変数を前記関数への入力として、前記決定された関数を使って行われ、前記転送する手段（ｄ）によって転送される前記パケットが前記指標値を含む、請求項１０または１１に記載の装置。
【請求項１３】
請求項８に記載の方法において使用される前記経路指定情報を提供するための装置であって、前記ネットワークを通る前記経路に沿った前記複数のノードのそれぞれについて、（Ａ）前記状態変数が前記ステップ（ｃ）で前記経路に沿った前の各ノードによりどのように更新されるかに従って、前記状態変数が前記ノードに到達するときに前記状態変数が何になるか判定し、（Ｂ）前記経路の一部を形成する発信リンクごとに、（ｉ）前記リンクに複数のリンクＩＤが関連付けられている場合に、前記ステップ（Ａ）で判定された前記状態変数を使って、ステップ（Ｂ）（ｉｉ）のための前記関連付けられたリンクＩＤとしてどのリンクＩＤを使用すべきか選択し、（ｉｉ）前記リンクと関連付けられたリンクＩＤを前記経路指定情報の前記データ構造へと符号化する手段を備える装置。
【請求項１４】
請求項１〜９のいずれか一項に記載の方法を実行するように装置を制御するためのプログラムであって、記憶媒体や伝送媒体といったキャリア媒体上に格納されるプログラム。
【請求項１５】
請求項１４に記載のプログラムを含む記憶媒体。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００１９
【補正方法】変更
【補正の内容】
【００１９】
本発明の第１の態様によれば、ネットワークを介してパケットを経路指定する方法であって、ネットワークのノードにおいて、（ａ）パケットを受信するステップであり、ノードはそれぞれが少なくとも１つのリンクＩＤと関連付けられている複数の発信リンクを利用することができ、複数のリンクのうちの少なくとも１つが複数のリンクＩＤと関連付けられており、パケットは、状態変数と、ネットワークを通る経路を形成する個々のリンクと関連付けられたリンクＩＤの集合を符号化している経路指定情報とを含み、符号化は、フォールスポジティブの可能性を有する、リンクＩＤがリンクＩＤの集合のメンバであるかどうかの検査に使用される確率的データ構造の形態であるステップと、（ｂ）複数の発信リンクのそれぞれについて、（ｉ）リンクが複数の関連付けられたリンクＩＤを有する場合に、受信されたパケットからの状態変数またはステップ（ｃ）で決定される新しい状態変数を使って、ステップ（ｂ）（ｉｉ）のための関連付けられたリンクＩＤとしてどのリンクＩＤを使用すべきか判定するステップと、（ｉｉ）データ構造をリンクと関連付けられたリンクＩＤのメンバであるかどうか検査するステップと、（ｃ）受信されたパケットからの状態変数に少なくとも部分的に基づいて新しい状態変数を決定するステップと、（ｄ）ステップ（ｂ）（ｉｉ）で、データ構造のメンバとしてのリンクと関連付けられたリンクＩＤを有すると判定された各リンクに沿って、経路指定情報および新しい状態変数を含むパケットを転送するステップとを含み、ステップ（ｂ）（ｉｉ）の前記検査において発生するフォールスポジティブによりループが発生し、前記ノードで同じパケットが受信される場合に、ステップ（ａ）において再度受信され、かつ、ステップ（ｂ）（ｉｉ）の検査のための前記関連付けられたリンクＩＤを決定するためにステップ（ｂ）（ｉ）において再度使用される前記状態変数が、同じパケットが以前前記ノードにより受信されたことがあるためにステップ（ｃ）の実行を通して更新され、ループの再出現を回避する確率を増加する方法が提供される。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００２６
【補正方法】変更
【補正の内容】
【００２６】
上述したように、ステップ（ｃ）で決定される新しい状態変数は、ステップ（ｂ）（ｉ）でどのリンクＩＤを使用すべきか判定するのに使用され得る。したがって、状態変数を受信し、当該状態変数を直接使って、どのリンクＩＤまたは経路指定表を使用すべきか決定し、次いで状態変数を更新するのではなく、ノードにおいて受信し次第状態変数を更新し、更新された状態変数を、どのリンクＩＤまたは経路指定表を使用すべきか決定する際に使用することができるはずである。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００３０
【補正方法】変更
【補正の内容】
【００３０】
本発明の第４の態様によれば、ネットワークを介してパケットを経路指定するネットワークのノードとしてまたはその一部として使用するための装置であって、ノードはそれぞれが少なくとも１つのリンクＩＤと関連付けられている複数の発信リンクを利用することができ、複数のリンクのうちの少なくとも１つが複数のリンクＩＤと関連付けられており、パケットは、状態変数と、ネットワークを通る経路を形成する個々のリンクと関連付けられたリンクＩＤの集合を符号化している経路指定情報とを含み、符号化は、フォールスポジティブの可能性を有する、リンクＩＤがリンクＩＤの集合のメンバであるかどうかの検査に使用される確率的データ構造の形態であり、装置は、（ａ）パケットを受信する手段と、（ｂ）複数の発信リンクのそれぞれについて、（ｉ）リンクが複数の関連付けられたリンクＩＤを有する場合に、受信されたパケットからの状態変数または決定手段（ｃ）で決定される新しい状態変数を使って、ステップ（ｂ）（ｉｉ）のための関連付けられたリンクＩＤとしてどのリンクＩＤを使用すべきか判定するステップと、（ｉｉ）データ構造をリンクと関連付けられたリンクＩＤのメンバであるかどうか検査するステップとを実行する手段と、（ｃ）受信されたパケットからの状態変数に少なくとも部分的に基づいて新しい状態変数を決定する手段と、（ｄ）ステップ（ｂ）（ｉｉ）で、データ構造のメンバとしてのリンクと関連付けられたリンクＩＤを有すると判定された各リンクに沿って、経路指定情報および新しい状態変数を含むパケットを転送する手段とを備え、ステップ（ｉｉ）の前記実行手段（ｂ）により実行される前記検査において発生するフォールスポジティブによりループが発生し、前記ノードで同じパケットが受信される場合に、前記受信手段（ａ）において再度受信され、かつ、ステップ（ｉｉ）において前記検査のための前記関連付けられたリンクＩＤを決定するためにステップ（ｉ）において前記実行手段（ｂ）により再度使用される前記状態変数が、同じパケットが以前前記ノードにより受信されたことがあるために更新され、ループの再出現を回避する確率を増加する装置が提供される。