メインコンテンツまでスキップ

5. ホストの概念モデル (Conceptual Model of a Host)

実装が特定の概念モデルに準拠する必要はありませんが、このセクションでは、ホストが近隣探索を理解するのに役立つ概念モデルについて説明します。ホストは概念的に、いくつかのデータ構造を維持します:

近隣キャッシュ (Neighbor Cache) - 最近トラフィックが送信された個々の近隣ノードに関するエントリのセット。エントリは近隣ノードのオンリンクユニキャストIPアドレスでキー付けされ、そのリンク層アドレス、近隣ノードがルーターかホストかを示すフラグ (本文書ではIsRouterと呼ばれる)、アドレス解決の完了を待機しているキューに入れられたパケットへのポインタなどの情報が含まれます。近隣キャッシュエントリには、到達可能性状態、未応答プローブの数、次の近隣到達不可能性検出イベントが発生する予定時刻など、近隣到達不可能性検出アルゴリズムで使用される情報も含まれています。

宛先キャッシュ (Destination Cache) - 最近トラフィックが送信された宛先に関するエントリのセット。宛先キャッシュには、オンリンクとオフリンクの両方の宛先が含まれ、近隣キャッシュへの間接参照のレベルを提供します。宛先キャッシュは、宛先IPアドレスをネクストホップ近隣ノードのIPアドレスにマッピングします。近隣キャッシュとは異なり、宛先キャッシュにはオンリンクとオフリンクの両方の宛先のエントリが含まれます。近隣キャッシュとは別に宛先キャッシュを維持することは、複数の目的を果たします。第一に、宛先キャッシュには、リンク上で隣接していない宛先のエントリを含めることができます。第二に、宛先キャッシュには、パスMTU探索、リダイレクトメッセージなどの対象となるエントリを含めることができます。

プレフィックスリスト (Prefix List) - オンリンクであるアドレスのセットを定義するプレフィックスのリスト。プレフィックスリストエントリは、ルーター広告で受信した情報から作成されます。各エントリには、プレフィックスを期限切れにするために使用される、関連する無効化タイマー値 (広告から抽出) があります。プレフィックスリストエントリには、[ADDRCONF] で指定されているように、プレフィックスをオンリンク決定および/またはアドレス自動構成に使用できるかどうかを示すフラグも含まれています。

デフォルトルーターリスト (Default Router List) - パケットを送信できるルーターのリスト。デフォルトルーターリストエントリは、近隣キャッシュのエントリを指します。デフォルトルーターを選択するアルゴリズムは、到達可能性が疑わしいルーターよりも、到達可能であることが知られているルーターを優先します。各エントリには、広告されなくなったエントリを削除するために使用される、関連する無効化タイマー値 (ルーター広告から抽出) もあります。

上記で説明した概念的なデータ構造は機能的に分離されています。実装は、最も便利な方法でそれらの一部またはすべてを自由に組み合わせることができます。このプロトコルの要件は、以下のセクションの疑似コードで上記のデータ構造を使用することで、わかりやすい方法で満たすことができます。ただし、実装の外部動作が変わらない限り、実装は代替のデータ構造を自由に使用できます。

5.1. 概念的データ構造 (Conceptual Data Structures)​

ホストが以下で説明するすべてのデータ構造を維持する必要はありませんが、このセクションでは、近隣探索を実装するのに十分なデータ構造のセットについて説明します。

5.2. 概念的送信アルゴリズム (Conceptual Sending Algorithm)​

ノードが送信するパケットを持っている場合、最初に宛先キャッシュを調べます。宛先のエントリが存在しない場合、ノードはエントリを作成し、ネクストホップ決定アルゴリズム (セクション5.2) を呼び出してそのネクストホップアドレスを初期化します。宛先キャッシュエントリが作成されると、ノードはネクストホップの近隣キャッシュエントリの状態を調べます。

近隣キャッシュエントリは、次の5つの状態のいずれかになります:

INCOMPLETE (不完全) - エントリに対してアドレス解決が現在実行されています。具体的には、近隣要請がターゲットの要請ノードマルチキャストアドレスに送信されましたが、対応する近隣広告がまだ受信されていません。

REACHABLE (到達可能) - エントリは最近 (数十秒前以内に) 到達可能であったことが知られています。最後のReachableTimeミリ秒以内に、近隣ノードへのフォワードパスが正常に機能していることの肯定的な確認が受信されました。REACHABLE状態の間、パケットが送信されても特別なアクションは実行されません。

STALE (古い) - エントリは最近到達可能であったことが知られていますが、最近確認が受信されていません。STALE状態の間、パケットが送信されるまでアクションは実行されません。パケットが送信されると、ノードは実装に応じて、エントリをDELAYまたはPROBE状態に遷移します。

DELAY (遅延) - エントリは最近到達可能であったことが知られており、最後のDELAY_FIRST_PROBE_TIME秒以内にパケットが送信されました。DELAY状態に入ってからDELAY_FIRST_PROBE_TIME秒以内に到達可能性確認が受信されない場合、近隣要請を送信し、状態をPROBEに変更します。プローブの送信を遅らせることで、上位層プロトコルが到達可能性確認を提供する機会を与えます。

PROBE (プローブ) - 到達可能性確認が受信されるまで、RetransTimerミリ秒ごとに近隣要請を再送信することによって、到達可能性確認が積極的に求められています。

近隣キャッシュには、さまざまなタイマー、カウンタなど、近隣到達不可能性検出アルゴリズムを実行するために必要な情報も保持されます。

近隣ノードにパケットを送信する場合、ノードは近隣キャッシュエントリに含まれる状態情報を使用して、その近隣ノードにトラフィックを送信する前に何かを行う必要があるかどうかを判断します。以下の疑似コードは、送信アルゴリズムを示しています:

if (宛先キャッシュエントリが存在する) {
    next hop = 宛先キャッシュの next_hop;
} else {
    next hop = ネクストホップ決定 (セクション5.2);
    宛先キャッシュエントリを作成;
}

if (next hopの近隣キャッシュエントリが存在する) {
    if (近隣キャッシュエントリの状態 == INCOMPLETE) {
        近隣キャッシュエントリにパケットをキュー;
        /* アドレス解決はすでに進行中 */
    }
    if (近隣キャッシュエントリの状態 == REACHABLE) {
        パケットを送信;
    }
    if (近隣キャッシュエントリの状態 == STALE) {
        パケットを送信;
        近隣キャッシュエントリの状態をDELAYに設定;
        近隣キャッシュエントリのタイマーをDELAY_FIRST_PROBE_TIMEに設定;
    }
    if (近隣キャッシュエントリの状態 == DELAY) {
        パケットを送信;
        /* タイマーはすでに設定されている */
    }
    if (近隣キャッシュエントリの状態 == PROBE) {
        パケットを送信;
        /* 近隣到達不可能性検出が進行中 */
    }
} else {
    近隣キャッシュエントリを作成;
    近隣キャッシュエントリの状態をINCOMPLETEに設定;
    if (リンク層アドレスが容易に利用可能) {
        リンク層アドレスを設定;
        近隣キャッシュエントリの状態をSTALEに設定;
        パケットを送信;
    } else {
        近隣キャッシュエントリにパケットをキュー;
        アドレス解決を開始;
    }
}

5.3. ガベージコレクションとタイムアウト要件 (Garbage Collection and Timeout Requirements)​

近隣キャッシュ、宛先キャッシュ、およびプレフィックスリストは、ガベージコレクションとタイムアウトが必要です。ただし、特定のタイムアウト期間は意図的に指定されていません。タイムアウト期間は、古い情報を維持することとその情報を更新するコストとの間で合理的なバランスを提供するように選択する必要があります。一般に、タイムアウト期間は、キャッシュ内容のスラッシングを防ぐのに十分な長さである必要がありますが、長期的な古さを防ぐのに十分な短さである必要があります。

概念的な実装では、次のルールを使用する場合があります:

  • 近隣キャッシュエントリは、STALE状態に遷移した後、少なくともReachableTimeで指定された時間だけ残るべきです (SHOULD)。ただし、実装がエントリを再利用するために何らかの形式のガベージコレクションアルゴリズムを使用する場合、それらはより長く残ることができます。INCOMPLETE状態のエントリは、そのような延長期間残る必要はありません。

  • 宛先キャッシュエントリは、可能な限り長く (つまり、無期限に) キャッシュに残るべきです (SHOULD)。ただし、特定の期間は実装依存です。実装は、宛先へのより良いルートを指定するリダイレクトメッセージが受信された場合、宛先キャッシュエントリを無効にすべきです (SHOULD)。

  • プレフィックスリストのエントリは、ルーター広告で指定された寿命に従ってタイムアウトします。エントリの寿命は、新しいルーター広告が到着したときに更新されます。

  • デフォルトルーターリストのエントリは、ルーター広告で指定されたルーター寿命に従ってタイムアウトします。ルーター寿命がゼロの受信されたルーター広告は、ルーターをデフォルトルーターリストから直ちに削除する必要があることを示します。

に最終更新