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に示す。

フィールド	説明
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アドレス)

フィールド	説明
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)に失敗した状態

パケット送信ルーチン

表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にチェーンされている。

関連ルーチン

neigh_lookup(tbl, pkey, dev)

__neigh_lookup(tbl, pkey, dev, create)

neigh_create(tbl, pkey, dev)

neigh_resolve_output(skb)

/* 
 * 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)

/* レイヤ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;

__neigh_event_send(neigh, skb)