無料Wikiサービス | デモページ
Linux Kernel(2.6)の実装に関するメモ書き
リンク
最近更新したページ
検索

アドレス解決プロトコル


IPアドレスに対応するハードウェアアドレス(MACアドレス)を解決するプロトコルとしてIPv4ではARP、IPv6ではNDPがある。Linuxではこれらのアドレス解決プロトコルのために汎用的に使えるルーチン、データ構造を用意している。

アドレス解決プロトコルは近隣のノードのMACアドレスを解決するものなので、実装ではNeighbour(近隣)という用語が使われている。

データ構造

アドレス解決プロトコルに関するデータ構造を図1に示す。

ARP,NDPなどのアドレス解決プロトコルではプロトコル毎に管理テーブル(struct neigh_table)がある。ARPはarp_tbl,NDPはnd_tblがそれぞれのstruct neigh_tableを指している。このテーブルには、エントリ管理のためのハッシュテーブルや各プロトコルのタイマ値などが格納されている。エントリ管理のためのハッシュテーブルはhash_bucketsに登録されている。このハッシュからエントリ(struct neighbour)がチェーンされている。

struct neighbourがARP/NDPエントリの実体になる。struct neighbourの末尾には検索キーであるprimary_keyがありここに、エントリのIPアドレスが格納されている。ARPならIPv4アドレス(4Byte)、NDPならIPv6アドレス(16Byte)が格納される。primary_keyのサイズはstruct neigh_tableのkey_lenに格納されている。


図1 エントリの管理

struct neighbour のフィールドを表1に示す。

表1 struct neighbourのフィールド(一部) 
フィールド
説明
next
ハッシュエントリ内でのNextチェーン
tbl
このエントリが属しているneigh_tblへのポインタ。
nud_state
Neighbourの状態。「Neighbourエントリの状態」参照。
ha
NeighbourのMACアドレス。
output
送信ルーチンのポインタ。IP層から呼び出される。
Neighbourの状態に応じてops.output,ops.connected_outputのルーチンのいずれかが設定される。
Reachable状態:
ops.connected_outputが設定される
Reachable状態以外:ops.outputが設定される
arp_queue
アドレス未解決時に解決待ちのパケットがキューイングされる。
ops
各プロトコル毎のハンドラルーチン群(struct neigh_ops)へのポインタ(表2参照)
primary_key
NeighbourのIPアドレスが格納される。この領域は0配列でneighbourがallocateされる時にプロトコルに応じたサイズで確保される。
ARP - 4Byte(IPv4アドレス)
NDP - 16Byte(IPv6アドレス)

表2 struct neigh_opsのフィールド
フィールド
説明
solicit
アドレス解決要求を行う時のルーチンが登録される。
ARP:arp_solicit() - ARP Requestを送信
NDP:ndisc_solicit() - NSを送信
error_report
アドレス解決やProbeが失敗した時のエラー処理用ハンドラが登録される。
output
IP層から呼び出されるパケット送信ルーチンが登録される。レイヤ2ヘッダをパケットに付加してパケットを送信する。
Neighbourの状態がReachable以外の時に
使用される。
Neighbourエントリへパケット送信イベントが通知され、Neighbourのアドレスが未解決の場合は本ルーチンでアドレス解決処理が開始される。解決済みの場合はNeighbourの状態に応じて状態遷移が発生する。
connected_output
IP層から呼び出されるパケット送信ルーチンが登録される。
こちらはNeighbourの状態がReachableの時に使用される。
Reachable状態ではパケット送信イベントは不要なので、単にパケットを送信するだけ。

hh_output
HardHeaderCacheが存在した時に使用される送信ルーチンが登録される。
IP層から呼びだされる。このルーチンはパケットを送信キューに積むだけなので、
IP層は呼び出す前にHardHeaderCacheからレイヤ2ヘッダをパケットにコピーしておかないといけない。通常はdev_queue_xmit()が登録されている。
HardHeaderCacheがあっても、Neighbourの状態がReachable以外の時は、送信イベントの処理が必要になるので.outputの方が使用される。
queue_xmit
Neighbourの送信ルーチン(.output,.connected_output)内で使用される送信ルーチンが登録される。通常はdev_queue_xmit()が登録されている。


Neighbourエントリの状態

Neighbourエントリは表3に示す状態を持つ。これらの状態は、もともとIPv6のNDPエントリのものだが、Neighbour部分で実装しているため、ARPについてもNDPと同じ状態遷移を行う。エントリの状態はstruct neighbourのnud_stateに格納される。

表3 Neighbourエントリの状態

状態
説明
NUD_NONE
Neighbourが作成された直後の状態。アドレス解決処理すら始まっていない。アドレス解決処理が始まるとNUD_INCOMPLETEになる。
NUD_INCOMPLETE
アドレス未解決の状態。
ARPRequestやNS(Neighbour Solicitation)を送信してアドレス解決処理を行なっている状態。
NUD_REACHABLE
アドレス解決が完了した直後の状態。
近隣に対してRequestを送って、Replyが返って来たので、近隣と双方向通信ができたという意味でRachableと呼ばれる。
NUD_STALE
NUD_REACHABLEになってreachable_time(*1)経過すると本状態に遷移する。
アドレス解決後時間がたち
、しばらく近隣との間で双方通信をしていないので、まだ本当に双方向通信できるのか疑わしい状態であることを意味する。この状態でNeighbourに対して送信が発生するとNUD_DELAYに遷移するが、そのままNeighbourに対して送信がないとNUD_STALEのままでいつづける。この状態のままgc_staletime経過するとこのNeighbourエントリはあまり使われていないということでガーベージコレクトされる。
NUD_DELAY
NUD_STALE状態のNeighbourにパケットを送信すると本状態になる。
Probeを始めるまでの猶予期間(*2)。
NUD_PROBE
NUD_DELAY状態でdelay_probe_time経過すると本状態になり、Probe処理を行なう。
Probe状態では
アドレス解決処理と同様にARPRequestやNS(Neighbour Solicitation)を送信して応答を待つ(アドレス解決とは異なりユニキャストで送信)。これは、しばらくNeighbourとの双方向通信を行なっていなかったので、再度通信してみてNeighbourがダウンしていないかを調べるために行なっている(*3)。Probeで応答が返れば再度NUD_REACHABLE状態に戻る(*4)。応答がなければNeighbourエントリは削除される(NUD_FAILEDになる)。
NUD_FAILED
アドレス解決(もしくはNUD)に失敗した状態
(*1) reachable_timeはbase_reachable_timeを0.5〜1.5倍した値で乱数で変動する。
(*2)
NDPのプロトコルではNeighbourと双方向通信を行なってNeighbourが生きていることを確認するProbeは、NeighbourとのTCP通信などでも代用できる(Ackが返れば双方向通信できたことが確認できるため)。NUD_STALE=>NUD_DELAYに遷移した時の通信がNeighbourとのTCP通信だったらProbe動作を省略できるので、そのためにこの猶予期間が存在する。この猶予期間の間にAckが返ればProbeを飛ばしてNUD_REACHABLEに遷移できる。ただし、このHintを受けてProbeを飛ばす動作はオプションなのでLinuxでは NUD_DELAY状態があるだけで、実際にHintの受信処理はないみたい。
(*3) この動作はNDPではNUD(Neighbour Unreachability Detection)と呼ばれる。
(*4) 通信し続けるNeighbourの状態はReachable->Stale->Delay->Probe->Reachable->...の遷移を繰りかえすことになる。

パケット送信ルーチン

表2に示す通り、IP層に提供されるパケット送信ルーチンには3種類(.output,.connected_output,hh_output)ある。これらのルーチンがIP層からどのように呼び出されるかを図2に示す。

IP層の送信処理でNextHopに対してHardHeaderCache(*1)がない場合はdst->neighbour->output()でパケットを送信しようとする。neighbour->outputにはNeighbourエントリの状態に応じてstruct neighbourの.outputもしくは.connected_outputのルーチンが登録されている。

HardHeaderCacheが存在した場合は、キャッシュからレイヤ2ヘッダをパケットにコピーした後、hh->hh_output()でパケットを送信する。hh_outputにはNeighbourエントリの状態に応じてstruct neighbourの.outputもしくは.hh_outputのルーチンが登録されている。HardHeaderCacheが存在して、NeighbourもReachableの場合は、パケット送信イベントの通知も不要でレイヤ2ヘッダもコピーされるだけなので送信処理が軽くなる(.hh_output())。

(*1) Linuxでは一度作成したレイヤ2ヘッダをキャッシュしておき、次回からコピーするだけでよいようにしている。キャッシュはstruct dst_entryの.hhにチェーンされている。



図2 パケット送信ルーチン


関連ルーチン

neigh_lookup(tbl, pkey, dev)
指定tblからpkey,devにマッチするNeighbourエントリを検索する。

__neigh_lookup(tbl, pkey, dev, create)
Neighbourエントリの検索マクロ。
neigh_lookup()のWrapper。
create = 1の場合は、エントリが見つからなかった場合、neigh_create()でエントリを作成する。

neigh_create(tbl, pkey, dev)
Neighbourエントリ(struct neighbour)を作成してハッシュに登録する。
エントリ作成の際は、tblにあらかじめ登録されていたコンストラクタを呼び出して初期化を行う。

neigh_resolve_output(skb)
Neighbourが非Reachable状態の時の送信処理。アドレス未解決の状態も含まれる。
通常、struct neigh_opsの.outputに登録されており、Neighbourの状態に応じてneigh_suspect()でNeighbourの送信ハンドラ(neigh->output)にコピーされる。

アドレス未解決ならアドレス解決処理を開始する。アドレス解決済みだったなら、Neighbourの状態遷移を行いレイヤ2ヘッダを付加してパケットを送信する。

/* 
 * Neighbourにパケット送信のイベント発生を通知する。
 * アドレス未解決だったならパケットはneigh->arp_queueにキューイングされ、
 * アドレス解決処理が開始する。(この場合、if内は実行されない)
 * Stale状態だったならDelay状態へ遷移してif内の処理を実行して
 * パケットを送信する。
 */
if (!neigh_event_send(neigh, skb)) {
    /* アドレス解決済みだった場合 */

    /*
     * dev->hard_header()でネットワークデバイスに応じた
     * レイヤ2(MAC)ヘッダを付加する。
     *   hard_headerはEthernetならeth_header()。
     */
    if (dev->hard_header_cache && !dst->hh) {
        /* hard_header_cacheが有効なデバイスで
         * 宛先にキャッシュ(dst->hh)がまだ作成されていなければ
         * neigh_hh_init()でキャッシュを作成する
         */
        if (!dst->hh)
            neigh_hh_init(neigh, dst, dst->ops->protocol);
        err = dev->hard_header(skb, dev, ntohs(skb->protocol),
                               neigh->ha, NULL, skb->len);
    } else {
        err = dev->hard_header(skb, dev, ntohs(skb->protocol),
                               neigh->ha, NULL, skb->len);
    }
    /* パケットの送信
     * ARP,NDPともqueue_xmitにはdev_queue_xmit()が登録されている
     */
    if (err >= 0)
        rc = neigh->ops->queue_xmit(skb);
    else
        goto out_kfree_skb;
}

neigh_connected_output(skb)
NeighbourがReachable状態の場合の送信処理
通常、struct neigh_opsの.connected_outputに登録されており(*1)、Reachable状態になるとneigh_connect()でNeighbourの送信ハンドラ(neigh->output)にコピーされる。

レイヤ2ヘッダを付加して送信するだけ。
/* レイヤ2ヘッダ付加 */
err = dev->hard_header(skb, dev, ntohs(skb->protocol),
                       neigh->ha, NULL, skb->len);
/* パケット送信 */
if (err >= 0)
    err = neigh->ops->queue_xmit(skb);
else {
    err = -EINVAL;
    kfree_skb(skb);
}
return err;

(*1) Ethernetデバイスではhard_header_cacheを行う(dst毎にレイヤ2ヘッダをキャッシュしておく)ようになっており、この場合、ARP,NDPとも.connected_outputにはneigh_resolve_output()を登録するようになっている。このため、Ethernet上のARP,NDPではNeighbourの状態によらずneigh_connected_output()は使われない。毎回 neigh_resolve_output()を呼ぶようにしているのは、HardHeaderCacheを作成するため。一旦、HardHeaderCacheが作られてしまえば、IP層からはdst->neighbour->output()ではなくhh->hh_output()で送信されるようになる。

__neigh_event_send(neigh, skb)
Neighbourエントリにパケット送信が発生したことを通知するルーチン。

Neighbourの状態に応じて以下の処理を行う。以下の状態以外では何もしない。

(1) NUD_NONE:
NUD_INCOMPLETEに遷移してアドレス解決処理を開始する。
送信しようとしていたパケットはアドレス解決するまで、neigh->arp_queueにキューイングしておく。
(2) NUD_INCOMPLETE:
すでにアドレス解決処理中なので、送信しようとしていたパケットをneigh->arp_queueにキューイングしてアドレス解決が済むのを待つ。
(3) NUD_STALE:
NUD_DELAYへ遷移する。(Probe開始のトリガとなる)

(1),(2)のケースでパケットがキューイングされた場合は、本ルーチンは1を返す。(3)のケースでパケットが送信可能な場合は0が返る。


最終更新 2006/08/07 20:25:11 - kztomita
(2006/08/03 12:59:13 作成)
添付ファイル
neighbour.png - kztomita
output.png - kztomita