UNIX Communication Notes 1 0 6 山口英 カーネルを読もう ( 8 ) 旧層における新機構 ( 2 ) 前回は、 IP 層でおこなわれる糸登各制御のメカニズムと、 そのインターフェイス、さらに経路清報をオ内するための 構造である Radix Tree について解説した。今回は引続 き、 IP 層での経路制御機溝の実装についてみていくこと にする。 Radix ee による経路検索 推奨されるようになった。これにともない、もっとも (VLSM: VariabIe Length Subnet-Mask) の利用が プネットを構成する場合は、可変長サプネットマスク インターネット・アドレスの枯渇を防ぐために、サ ・長ネットマスクへの対応 しなければならない。 る場合があり、糸登各表自体か可変長アドレスをサポート に対し、 OSI プロトコルでは可変長アドレスが使われ TCP/IP や XNS では固定長アドレスを用いているの ・長アドレスへの対応 ッシュ関数カ陏効に働きにくい。 ポートしていた TCP/IP や XNS とくらべて長く、 OSI プロトコルで使用されるアドレスは、それまでサ ・長いアドレスの取扱い である。 実装に変更された。これは、次のような条件を満たすため ルがサポートされたのを契機として Radix Tree による 路表か利用されていたが、 BSD UNIX で OSI プロトコ る。 4.3BSD UNIX まではハッシュテープルを用いた経 Radix Tree にもとづくデータ構造を用いて構成されてい 層の経路表の実装では、経路情報を格納する経路表は、 前回説明したように、 4.4BSD UNIX における IP 20 長いサプネットマスクをもっ経路情報を利用する必要 が生した。さらに、現在では CIDR (CIassIess lnter- Domain Routing) と呼ばれる、クラスの概念を取り 払った経路制御が普及したため、経路情報はつねにア ドレスとマスクを対にして言面する必要が生してきた。 ・より高速な インターネットの急な拡大により、扱うべき経路情報 カ大した。このため、数千、数万の経路欝にを取り扱 う場合も経路表を高速に検索する必要が生じた。 これらの理由により、 Radix Tree によるキ各表カ発 された。 経路表には、次の 2 つの対応が求される。 ・目的のネットワークあるいはホストのアドレス ・そこに到達するためにイつれるネットワーク・インター フェイス、およひ次に送るべき Next-Hop ホスト 経路制徊構は、逶する IP データグラムの受信ホス トに指定された IP アドレスをキーとして経路表を検索し、 そのキーにマッチした糸青報を得る処理をおこなう。現 在のインターネットでは、一 -- 級に可変長ネットマスクが用 いられている。そのため、検索処理ではキーにマッチする ↑欝にのうち、もっとも長いネットマスクをもつ情報お尺 しなけれはならない。 Radix Tree を用いた経路表では、管理している各経路 情報について、目的のネットワークあるいはホストアドレ スをピット列とみなして Radix Tree を構成し、具イ勺 な経路情報を Radix Tree の葉 (leaf) の部分に格納す る。このため、 Radix Tree を用いた経路検索では、検索 のキーとなるアドレスをピット列とみなし、そのピット列 UNIX MAGAZINE 1997.4
経路情報のないアドレスに対する経路検索は、 Radix Tree をたどり、アドレスに一致する葉が発見できないま まバックトラックを続け、最終的に根のノードに戻って こで、根にはすべて 0 のマスクが用意されてい るので、このマスクにもとづいて左の枝をたどろうとする が、そこが NULL て経路がないことカ吩かる。これによ り、経路検索の失敗か明らかになり、正しい処理がおこな 連載 /UNIX Communication N0tes—O Radix ee の実装 われる。 UNIX MAGAZINE 1997.4 ARP (Address Resolution Protocol) テープルが融合 4.4BSD UNIX では、 Radix Tree を用いた経路表と ARP テープルとの融合 る必要はないのである。 がって、経路清報窈助日・削除の処理は検索はど効率化す 除にともなう処理の発生頻度は相対的にかなり低い。した 検索が発生する可能性がある。一方、経路情報の追加・削 各 IP データグラムの転送処理がおこなわれるたびに経路 路制御職構で瀕繁におこなわれる処理は経路検索であり、 する処理のオーバーヘッドの軽減カ牲になっている。経 て実装されている。したがって、経路情報の追加・削除に関 になっても高速な検索処理が可能なことを最大の目標とし Tree を用いた経路制御欟冓は、一早する経路情報か膨大 には、検索とくらべて複雑な処理か求められる。 Radix 複雑な冓造を使っているため、ノードの追加・削除 の追加・削除・検索のための関数である。 されている。具イ勺には、 Radix Tree の初期イヒノード radix. c では、 Radix Tree に関する処理関数群が定義 体を用いている。 葉て使われる構造を区別しているが、基本的には同し構造 されている。共用体 (union) によって、根と分岐および データ構造は、 radix. h てオ冓造体 radix-node として定義 によって構成されたデータ構造である。各項点で使われる でおこなわれている。 Radix Tree は、基本的にポインタ ・ net/radix. h ・ net/radix . c 4.4BSD UNIX での Radix Tree の実装は、 されている。言い換えれば、 ARP テープルは経路表のな かの情報として椥友されているわけである。 ネットワーク・インターフェイス層において IP デー タグラムか転送される場合、目的のホストの IP アドレス からデータリンク・アドレス (Ethernet アドレスなど ) を取得する必要がある。そのための情報をイ尉寺しているの が ARP テープルである。 ARP テープルは、 4.3BSD UNIX まではカーネル内に独立したテープルとして構成 されていた。しかし、 Radix Tree を用いた経路制御職 構を導入した際、 ARP テープルも経路表に統合された。 ARP テープルにおける検索では、 IP アドレスをキーと して、対応するデータリンク・アドレスを取得する。これ は、経路表におけるホスト経路の検索と性質的に同じもの である。そこで、 ARP テープルを糸習各表に統合し、より 高速な ARP テープルの検索を実現している。 ARP テープルを経路表に統合するための基本的なアイ デアは、 ARP テープルの検索をホスト経路の検索と同一 に扱う点にある。通常のホスト糸各に対しては、使用する ゲートウェイとインターフェイスカ当されるが、糸習各表 を ARP テープルとして使う場合は、そこにデータリン ク・アドレスの情報を言当し、 ARP テープルと同し機能 を提供している。 ARP テープルク充合には、もう 1 つの冓カイ吏われて いる。経各表に RTF-CLONING フラグが付けられた経路 情報工ントリを利用して、 ARP テープルのエントリを動 的に生成するのである。 図 2 を見てはしい。この糸各表では、ローカルホスト は 133.5.16.2 / 24 で、ローカルなネットワークとして 133.5.16.0 / 24 がある。システムの起重丿 1 時 = には、 ifconfig コマンドでネットワーク・インターフェイスか初期化さ れるが、同時に ARP テープルも初期化される。具イ勺に は、経路表に対して 133.5.16.2 / 32 のエントリと、それに 対応するデータリンク・アドレスか設定される。そして、経 路表に RTF-CLONING フラグが付けられた 133.5.16 / 24 に対するエントリを用意しておく。 経路表を検索して RTF-CLONING フラグカ咐けられた 工ントリとマッチすると、その検索に使われたキーのエン トリを生成する機能がある。 CLONING ( 複製する ) とい う用語は、これに由来する。たとえば、 133.5.16.5 への ARP か発生した場合には次のような処理がおこなわれる。 23
連載 / IJN Ⅸ知恵袋ーの 図 1 ネームサーバーの言聢ファイル列 0 . 0.127. in—addr. arpa directory cache pr lmary pr lmary pr lmary /var/named f00. co ・」 p 10 . 159. 133 . in—addr. arpa root . cache f00.20 Ⅱ e f00. 10ca1host . rev ・ノレート・ネームサーノヾー 30 は f00. co. jp です。 ち一 E げることにします。 ns. foo. co. jp カ壻理するドメイン IP アドレスが 133.159.10.1 であるネームサーバーを立 なお、今回の説明のために、 ns. foo. co. jp という名前で の書式を順ら細早説していきます。 以後これら窈青報を言当するデータベース・ファイル 算機名の場合、右にいくにしたがってより上位の組織を表 機名と IP アドレスの階層構造の違いによるものてす。計 スの記去か通常と逆になっています。この理由は、計算 始まる IP アドレスを示します。逆引きの場合、 IP アドレ ことです。 10.159.133. ⅲ - addr. arpa が 133.159.10. で は、その名のとおり、 IP アドレスから引・算機名を調べる データベース・ファイル名を指定しています。逆引きと しています。次の primary 行は、逆引き用のドメインと のデータベース・ファイル名が f 。。 . zo Ⅱ e であることを示 ることを宣言し、計算機名を IP アドレスに変換するため す。最初の primary 行は、 foo ・ co ・ jp ドメインを管理す ンを指定し、そのデータベース・ファイル名を指示しま primary で始まる行はネームサーバーカ壻理するドメイ バーの情報ですから、ドメインはルート (. ) になります。 した情幸ゞ央されるドメインです。ルート・ネームサー イル名です。 2 列目の、、 . " は root. cache ファイルに言当 タベース・ファイル名を指定します。 root. cache がファ cache 行はルート・ネームサーバーの情報を収めたデー データベース・ファイルを置くことが多いようです。次の クトリを指定します。 /var/named/ ディレクトリ以下に directory 行はデータベース・ファイルがあるディレ /etc/named. boot です。図 1 を見てください。 ルを書きます。通常、ネームサーバーの設定ファイルは 最初に、ネームサーバーか起重加こ読み込む設定ファイ ネームサーバー設定ファイル すようになりますが、 IP アドレスは逆に、右にいくにし たがってより下位の細織を表します。そのため、言当去が 逆になっています。最後の primary 行はローカルホスト の逆引きの設定です。 127.0.0.1 という IP アドレスから localhost. f00. co. jp という名前を引くために必要です。 ネームサーバーの設定ファイルは以上で完了です。た だし、ネームサーバーをより強靱にしたいと考えるのであ れは、ネームサーバーを多重化し、たとえ 1 つがダウン しても代わりのネームサーバーが対応するような仕組みを 作っておくべきでしよう。成疋ファイルのなかに primary という行がありましたが、これはプライマリ・ネームサー バーの成疋ファイルてイ吏われるものです。ネームサーバー にはプライマリ・ネームサーバーとセカンダリ・ネーム サーバーがあります。プライマリ・ネームサーバーはデー タベースの元締めで、あらゆる変更はプライマリ・ネーム サーバー上でおこなわれます。セカンダリ・ネームサーバ ーは負荷分散やバックアップを目的としたミラーサーバー です。セカンダリ・ネームサーバーは定期的にプライマリ・ ネームサーバーに接続し、最新のデータベース・ファイル を取得します。 セカンダリ・ネームサーバーの設定は彳あすることにし、 まずプライマリ・ネームサーバーのデータベース・ファイ ルの書き方をみていきましよう。 計算機名から IP アドレスへ DNS データベースのレコードの書式を図 2 に示しま す。 ん e リがデータベースを検索するときのキーです。 IP アド レス・データベースなら、計算機名になります。 s 。 c ← れ佖 me はデータベースのレコードの不鶤頁を示す文字列が入 ります。 DNS データベースのレコードには、表 1 て示す ような不軽頁があります。 表 1 に示したようなレコードを総称して、資源レコー UNIX MAGAZINE 1997.4
連載 /UNIX Communication Notes— 図 2 ARP テーカレの表への統合 3 0 CLON 工 NG 13 3 . 5 . 16 / 2 4 0 2 9 13 3 . 5 . 16 . 5 / 3 2 0 : 0 : c : 1 : eb : 5d グを設定し、そのエントリを利用不能にする。 棄する場合は、経路表でのエントリに RTF-REJECT フラ は、 ARP 工ントリに設定されたタイマーを利用する。破 ( 通常 20 分 ) 以使われないと破棄される。この処理に 従来の ARP と同しように、 ARP 工ントリは一定時間 ケットを破棄し、ホスト到達不能の処理をおこなう。 ントリとして処理を進める。同時に、ペンディング・パ RTF-REJECT を設定し、経路表のなかて利用不能な工 ない場合には、経路表に追加されたエントリのフラグに 4. 一定時間か経過しても ARP 要求への応答カ唳ってこ する。 のエントリにオ褓内し、ペンディング・バケットを転送 得られた場合は、取得したデータリンク・アドレスを空 3. ARP 要求に対する応答が一定日判り ( 通常 5 秒 ) 以内に トリにイ尉寺される。 バケットはペンディング・バケットとして ARP 工ン で実際に ARP 要求の同幸凾信処理を実行し、送るべき 域は石呆されるが、その内容は空である。そして、 れる。このとき、データリンク・アドレスをオ褓内 1 ーる領 に 133.5.16.5 / 32 に対するエントリか経路表に追加さ るはすである。このエントリにマッチすると、ただち ラグの付けられた 133.5.16 / 24 のエントリにマッチす 2. 工ントリがない場合には、最終的に RTF-CLONING フ 中幻医する。 ントリがあオ L は、その情報を用いて IP データグラムを の結果、糸各表にデータリンク・アドレスを言当した工 1. ます、 133.5.16.5 / 32 に対する経路検索をおこなう。そ 24 RADISH Radix Tree を用いた経各表の実装により、きわめて 高速な経路検索が可能になるが、一見すれば分かるように コードは複雑である。これは、 BSD UNIX て扱われるプ ロトコルに OSI プロトコルが追加され、可変長アドレス への対応が必要になったこと、さらに可変長ネットマスク を扱わねばならなくなったことなどか景している。さら に、 Radix Tree は汎用性を重視して実装されたため、現 実の運用には不要なコードが含まれていてかなり読みづら い。これを改善すべく、 WIDE プロジェクトの山本和彦 氏 ( 奈良先端大 ) が RADISH というイ督はみを考案した。 これは、経路制徊部分に 4.4BSD Lite のコードを使って いる BSDI の BSD/OS 2.1 用で、扱いやすく、現実的 な運用を前提とした実装である。 概要 Radix Tree にもとづく経路表の実装では、 ・不連続なネットマスク 基本的に最大長制限のない可変長アドレス への対応が可能な実装をしていたために、きわめて複雑 になっていた。しかし、不連続なネットマスクの利用は、 CIDR が普及した現在のインターネット環境ではリ巨見実 的であり、 OSI プロトコルで扱う可変長アドレスも無限 大ではない。そこで、 RADISH では以下の 3 点をおもな 目標としている。 ・よりシンプルな実装 UNIX MAGAZINE 1997.4
0 図 1 連載 UNIX Communication Notes— Radix rn•ee による表 end 経路 表 1 一列 0 / 0 133.5.23 / 24 133.5.16 / 24 133.5 / 16 133.4 / 16 8 5 0 4 0 0 0 0 0 15 8 5 0 5 0 0 0 0 1 19 8 5 0 510 0 0 end 21 アドレス 85040000 85050000 85051000 85051700 00000000 マスク 00000000 ffffff00 ffffff00 ffff0000 ffff0000 に従って RadixTree をたどっていき、目的とする経路 情報を発見する。 こでは、 Radix Tree を用いた経剳青 報の検索のアルゴリズムについて説明する。 経路制御表の例 以降では、前回 Radix Tree の構成例として示した糸各 情報を用いて解説を進める。表 1 に例として用いる経路情 報の一覧を、図 1 にその経路情報から構成される Radix Tree を示す。 単純な検索 最初に、単純な検索について説明する。ホスト 133.5. 16.2 を受信ホストに指定した IP アドレスの中幻処理で発 生する経路検索を考えてみよう。 Radix Tree の分岐に示されている値は、イ尉寺してい る経路・情報について分岐が何ビット目で発生しているか を表している。経路情報の検索において分岐に示されて いる値は、検索キーとして与えられた IP アドレスの何 ビット目を検査するか、すなわちチェックビットの場所 を意味する。ホスト 133.5.16.2 に対する経路検索では、 UNIX MAGAZINE 1997.4 8 5 0 517 0 0 133.5.16.2 は、 16 進表記では、、 85051002 " なので、 Radix Tree をたどりながら検索キーについて検査してい 検索キーに 133.5.16.2 カイ吏われる。検索にあたっては、 各ビットの検査は次の手順でおこなわれる。 は左の枝をたどる。 じように 133.5.16.2 の 21 ビット目は 0 なので、今度 5. 次の検査ピットは 21 ピット目である。直前の検査と同 枝をたどる。 しように 133.5.16.2 の 19 ビット目は 1 なので、右の 4. 次の検査ピットは 19 ピット目である。直前の検査と同 15 ビット目は 1 なので、今度は右の枝をたどる。 3. 次の本査ビットは 15 ピット目である。 133.5.16.2 の なので、左の枝をたどる。 2. 次の分岐では、 1 ビット目を評価する。 1 ビット目は 0 ト目が 1 なので、右の枝をたどる。 1. 最初に 0 ピット目を検査する。 133.5.16.2 では 0 ピッ トマスク ffffff00 でマスクし、再度 133.5.16.0 と比 7. 次に、 133.5.16.2 に対して、そこに当されているネッ ているアドレスは 133.5.16.0 なので、直接の上交は失 かイ尉寺しているのはネットワーク経路であり、言当され ている経路報のアドレスを上交する。しかし、この葉 6. 最終的に葉に到達すると、 133.5.16.2 とそこに書かれ 較すると一致する。そこで、この経路を採用する。 21
1 島慶ー バー ( 2 ) 不一 ムサー 前回は、計算機の名前と IP アドレスを結びつけるう靖攵 わせます。たとえば、 slab. tnr. sharp. co. jp ドメインを管 ホスト・データベース、、 DNS " の概要を紹介し、 DNS の 理しているネームサーバ ーに、 altair. slab. tnr. sharp ・ co ・ jp. という名前の間合せがきたら、自分がイ尉寺しているデ 実装例としてひろく普及している BIND のインストール ータベースを検索し、対応する IP アドレスを返します。 ガ去を解説しました。 DNS を使うと、職斤に近い自糸哉 の計算機名に対応する IP アドレスの情報を公開でき、ま 下位ドメインに属する計算機名、たとえは vega ・ design ・ た同様に他糸目織の言 t. 算機名に対応する IP アドレスを調べ slab. tnr. sharp ・ co. jp. に対する間合ぜを受信したら、 de- られるようになります。 sign. slab. tnr. sharp. co. jp ドメインを管理しているネー ーに間い合わせます。逆に、上位ドメインに属 ムサーノヾ 今回は、計算機名の問合に応える、ネームサーバーと する計算機名、たとえば sirius. tnr. sharp. co. jp. に対す 呼ばれるプログラムの設定について解説します。 る間合ぜを受信したら、ルート・ネームサーバーに問い ネームサーバーの仕組み 合わせます。ルート・ネームサーノヾーとは、すべてのド メインの根本にあたるドメインを管理するネームサーバー ネームサーバーのイ督はみをおさらいしましよう。計算機 です。ルートドメインは、、 " ( ドット ) て表されます。ル は、計算機名とドメイン名の組で識別されます。引算機名 ート・ネームサーバーには、その下位ドメインである jp は糸目織内で一意であり、ドメイン名は世界中で一意である ドメインを管理するネームサーバーの情報が登録されてい ことが保証されています。したがって、引・算機名とドメイ ます。 jp ドメインのネームサーバーには、その下位ドメ ン名の組を使えば、世界中の計算機から 1 台だけを特定 インである co. jp ドメインのネームサーバーの情報が登 できます。たとえば、私の言 t 算機名は altair で、ドメイ 録されています。ドメインの階層構造を使って、最終的 ン名は slab. tnr. sharp. co. jp です。世界中てオムの計算機 に tnr. sharp. co. jp ドメインのネームサーバーにたどり着 を一意に識別するには、 altair. slab. tnr. sharp ・ co. jp と書 き、 sirius. tnr. sharp ・ co. jp を間い合わせます。 けばよいわけです。ネームサーバーの管理単位はドメイン テータベースにな情報 で、基本的にドメインごとにそれぞれネームサーバーか存 在します。 ト述したネームサーバーのイ督はみカ黝くためには、以下 ネームサーバーカ墹合を受信すると、ます間い合わさ の情報が必要です。 れた言 t 算機名のドメインを調べます。そのドメインと自 分が管理しているドメインが一致すれば、データベース ・自分のドメインの計算機名と IP アドレス から計算機名を検索して対応する IP アドレスを返しま ード位ドメインを管理するネームサーバー す。自分より下位のドメインならば、下位ドメインを管 1 各ドメインを管理するネームサーバークオ欝長はキャッシュされるので、上 理しているネームサーバーに問い合わせ、上位ドメインな 位ドメインへの間合のたびにルート・ネームサーバーへの問合ぜカ吽し らば一ヒ位ドメインを管理しているネームサーバーに間い合 ることはありません。 29 UNIX MAGAZINE 1997.4
連載 / IJN Ⅸ知恵袋ーの 図 2 レコード式 ん e リ 図 3 A レコード列 ( 1 ) IN altair PTR (PoinTeR) A (Address) 表 1 DNS の資源レコード altair. f00 . co ・」 p ・ 図 4 A レコード列 ( 2 ) IN IN SOA (Start Of Authority) NS (Name Server CNAME (CannonicaI NAME) MX (Mail eXchanger) HINFO (Host INFOrmation TXT (TeXT) WKWN (WellKnoWN service) resource—name IP アドレス 計算機名 データの始まり ネームサーノヾー 言算機の別名 電子メール酉当逶先 任意の文字列 よく知られたサービス ド (Resource Record) と呼びます。 IP アドレスなら は s 。盟℃ e - れ佖 me は、、 A " です。いくつかの資源レコー ドについては順次解説しますが、利用頻度の低いものは省 略します。興味のある方は RFC などを参照してくださ い。皿ん e はキーに対応する値です。 IP アドレス・データ べースなら IP アドレスそのものになります。 図 2 の 3 列目は資源レコードと関係するプロトコルの 不頁を示す文字列で、 IN はインターネット・プロトコル を示します。インターネット・プロトコル以、タ ) プロトコ ルに対応する資源レコードも定義されていますが、利用す る場面ははとんどないと思われるのて省略します。 2 列目 にはオプションでレコードの有第間を指定することがで きます。しかし、彳あする SOA レコードのなかで、デー タベース全体のレコードに対する有寺間を設定できるの で、通常は省略されます。有芋間については次の「デー タベースのスタート」の解説を見てください。 具体例を挙げます。 altair. foo ・ co ・ jp という計算機に 133.159.10.10 という IP アドレスを割り当てる場合、図 3 のように書きます。 altair という文字列の後ろには、暗黙のうちに foo. co. jp. という文字列が仮定されています。 foo. co ・ jp ・という 文字列の情報はネームサーバーの成疋ファイルから取られ UNIX MAGAZINE 1997.4 133 . 159.10. 10 133 . 159. 10 . 10 ています。成疋ファイルを思い出してください。 IP アド レスのデータベース・ファイル名を指定する行に、対応す るドメイン名を指定していたはすです。 31 と書いてください。もっとも、ネームサーバーが実際に postmaster@foo.co.jp ならは、 postmaster. f00. co. jp ・ ールアドレスと異なり、 @の代わりにドットを使います。 タベース管理者のメールアドレスを指定します。通常のメ やすさのために FQDN を用います。 postmaster はデー と同様にドメイン名カ黼完されます。ただし、通常は読み 書きます。末尾のドットを省略すると、 A レコードのキー は、データベースを管理するネームサーバーの計算機名を で指定されたドメイン名カ甘采用されます。 nameserver に す。省略形を用いると、ネームサーバーの設定ファイル ば foo. co. jp. ですが、通常は省略形である、、◎ " を用いま 。吻はデータベースの起点を示します。今回の例なら す。図 6 を見ながら読み進んでください。 レコードの書式を図 5 に示します。具イ列を図 6 に示しま ルはかならす SOA レコードをもつ必要があります。 SOA タベース・ファイルにはなりません。データベース・ファイ きます。しつは、前述の A レコードだけでは正しいデー 次に、データベースの始まりを示す SOA レコードを書 テータベースのスタート 述していきます。 あとは必要な数だけ、言 t 算機名と IP アドレスの組を記 Name) であるとみなさドメイン名を補完しません。 ると、その名前は FQDN (Fully Qualified Domain を付けるのを忘れないようにします。末尾にドットがあ かまいません ( 図 4 ) 。その場合、ドメイン名の取陵に もちろん、ドメイン名まで含めて計算機名を書いても
連載 /IJNIX Communication Notes— パックトラックが発生する検索 0 次に、 Radix Tree による経路検索クを徴であるバック トラック (backtrack) が発生する検索をみてみよう。ホ スト 133.5.18.9 ( 16 進表記で 85051209 ) に対する経路 検索を例に説明する。 この例で Radix Tree カ甘旨定している本査ビットであ る 0 、 1 、 15 、 19 、 21 ビット目の値をみると、 133.5.18.9 と 133.5.16.2 は同一である。したがって、 133.5.18.9 についても、根から Radix Tree をたどるステップは 133.5.16.2 とまったく同じである。最終的に 85051000 の葉にたどり着いたときにアドレスを上交するが、ネット マスクでマスクをしてから上交しても 133.5.16.0 とは一 致しない。葉に到達してアドレスを上交しても一致しない 場合は、今度は Radix Tree を逆向きにたどり始めるに れがバックトラックである ) 。具イ勺には次のような手順 になる。 1. 最初に 21 の分岐に戻るが、 こでは分岐でのマスク 指定がないので、そのまま通過し、さらに逆向きにた どる。 2. 次に 19 の分岐にくると、 ffffOOOO のマスクか書かれ ている。そこで、 133.5.18.9 に対してこのマスクを適 用し、 19 ビット目を検査する。 3. マスク処理後の 19 ピットは 0 なので、今度は分岐を 左側にたどる。 用意されない。この分岐における検査ピットは 15 ピット のマスクが用意されているが、分岐 15 にはこのマスクは 例に示した Radix Tree では、・岐 19 で ffff0000 れはならない。 ラックで正しく経路が〕尺されるように設定しておかなけ 述される。しかし、分岐に用意されるマスクは、バックト されている。分岐以下の部分木のなかの最短のマスクか記 れているマスクは、バックトラックの処理のために用意 これからも分かるように、 Radix Tree の分岐に孑定さ ので、この葉に言当されている経路 1 青報を採用する。 を適用してから再度上交する。上交した結果が一致する ないので、 133.5.18.9 にそこに言当されているマスク 5. ます 133.5.18.9 と 133.5.0.0 とを上交するが、一数し 4. そして 85050000 の葉にたどり着き、そこで上交をお 22 目なので、仮にバックトラック処理で検索キーにマスクが 適用されても、マスクが適用されない場合と同じ処理がお こなわれる。したがって、このようなマスクを設定する意 味はない。 デフォルト経路の採用 次に、デフォルト経路の採用を考えてみよう。たとえ ば、ホスト 169.111.16.4 に対する検索では、次の手順で デフォルト経路を取得する。 には根まで戻る。 分岐でも検査ピットの条件は満たされないので、最糸勺 マスクを適用しながらバックトラックを進めるが、どの 3. マスクカ甘旨定されている・分岐で 169.111.16.4 に対して で、バックトラックに入る。 2. しかし、葉においてアドレスを上交しても一致しないの ていくと、 85051000 の葉にたどり着く。 1. 通常どおり、検査ビットの状態て木を葉の方向にたどっ UNIX MAGAZINE 1997.4 ようにしなければならない。 させ、関数 rtalloc() の結果として NULL ( 0 ) を返す ストに対する経路 1 青報がないアドレスに対する検索は失敗 デフォルト経路がない場合は、目的のネットワークやホ テフォルト経路がない場合 オ絲勺されている。 マスク ffffffff をもつ経各情報として Radix Tree に きる。 4.4BSD UNIX における実装では、ホスト経路は ば、 Radix Tree での検索アルゴリズムを変えすに処理で 随するマスクが ffffffff であるような情報として扱え 較した結果が一致する経路である。つまり、経路情報に付 スト経路とは、検索キーに対して 32 ピットをすべて比 実装になっている。 Radix Tree での検索において、ホ Radix Tree におけるホスト経路の取扱いは、単純な ホスト経路の取扱い 情報を使う。 5. そこに用意されている葉がデフォルト経路であり、その たどる。 のマスクをかければ、どのアドレスもかならず左の枝を 4. 根には、すべて 0 のマスクが定義されているため、
連載 / UN Ⅸ知恵袋ーの 図 15 nslookup の実行 $ nslookup Address: 127.0.0. 1 DefauIt Server: localhost . f00. CO ・」 p > set type=soa > f00 . co ・」 p ・ ← SOA レコードの問合せを指定 ← f00. co. jp ドメインの SOA レコードを間い合わせる Server : localhost . f00. CO ・ JP Address: 127.0.0.1 f00. co ・ jp origin = Ⅱ s. f00. co . 」 p mail addr = postmaster. f00. CO ・」 p 19970200 serial refresh retry eXPIre 10800 ( 3 hours) 1800 ( 30 mins) 4320000 ( 50 days) minimum ttl = 86400 ( 1 day) f00 . co ・」 p nameserver = ns . f00. CO . 」 p ns . f00 . co ・ jp > set type=a > altair internet address 133. 159. 10 . 1 ← A レコードの間合せを指定 ← altair の A レコードを問い合わせる Server: localhost. f00 . CO ・ JP Address: 127.0.0.1 Name : altair. f00 ・ co ・」 p Address: 133. 159 .10 . 10 > set type=ptr > 10 . 10.159.133. i Ⅱー addr . arpa. Server: localhost. f00 ・ CO ・」 p Address: 127.0.0.1 ← 133.159.10.10 の PTR レコードを間い合わせる ← PTR レコードの間合せを指定 nameserver ns . f00. CO . jp 10.159.133. in—addr. arpa name altair . f00. CO ・ JP 10.10.159.133. in—addr. arpa internet address 133 . 159. 10 . 1 ns . f00. CO ・ jp # /usr/etc/in. named —f /etc/named. b00t データベースに間違いがあるとエラーを報告して終了し ますから、データベースを修正してください。問題がない ようであれは、正しく動作しているかどうかチェックし ます。 ネームサーバーのチェック ます、 /etc/resolv. conf にドメイン名とネームサーバ ーの IP アドレスを設定します。 /etc/resolv. conf は、ネ ームサーバーへの問合せ処理ルーチンか参照するファイル です。今回の例では図 14 のように言己します。 domain で計算機か所属するドメイン名を指定します。 UNIX MAGAZINE 1997.4 nameserver は、ネームサーバーカ鍾カ作している言算機 の IP アドレスです。自分自身がネームサーバーとして 重川乍しているのならばローカルホスト ( 127.0.0.1 ) 、そう でなけれはネームサーバーの IP アドレスを指定します。 nameserver 行は複数記述することができます。その場 合、最初から順にアクセスし、最初に応答のあったネーム サーバーに対して問合処理をおこないます。 ネームサーバーの重川乍チェックには nslookup コマン ドを使うのがよいでしよう。 nslookup コマンドを起動し て、 f00. co. jp の SOA レコード、 A レコード、 PTR レ コードを表示させてみます。図 15 を見てください。下線 を引いた箇戸励ゞ入力する部分です。 nslookup コマンドの詳しい解説は次回に譲りますが、 35
連載 / 旧 dy 入門ー① 図 12 メール信 件名 : Re; This 土ミ加 9 firs€谷ー加 ail to myselfl CCS 宛先 : "Freia M. <freia@center.wakayama-u.30 ・ jP> 信、引 ~ 第付、ア・い朝を、餐 ! 第 5 ~ イル編集、、表示オプジ女ン戔ウインドウ。ー 0 おはデストメ—ルてすふ、 宛先 (To) に自分自身、あとは適当な件名 (Subject) と本 それではテストメールを書いてみましよう。とりあえす テキストボックスの下には、メールの本文を書きます。 です。 にかならずしも添付ファイルか届くとはかぎらないから せん。回をあらためて説明しますが、メールの受取り人 メールの受信、返信 文を書き、ツーノレヾーの [ 送信 ] を押します。 こでメールサーノヾーでのノヾスワー ウか表示されるので、 POP3 を利用している場合には、図 10 のようなウインド 6 の画面上で [ 受信 ] ボタンを押します。メールの受信に 今度は出したばかりのメールを読んでみます。ます、図 ドを入力します。 UNIX MAGAZINE 1997.4 です。 でも同しことです。 [ 返信 ] ボタンを押したところが図 12 この例では宛先 (To) が 1 人で CC もないので、どちら 外の人たちにも返信します。 ルの宛先 (To) や CC のなかに並んでいる人で自分以 指定した返信先 (RepIy-To) だけでなく、もとのメー 全員へこのメールの差出人 (From) 、もしくは差出人が 定した返信先 (RepIy-To) のみにメールを返します。 返信このメールの差出人 (From) 、もしくは差出人力甘旨 りのガ去があります。 さらに返事を書いてみましよう。返事の書き方には 2 通 すると、図 11 のようにメールを読むことができます。 こでいくつかおもしろいことがあります。 ・宛先 (To) が e-mail アドレスだけではなく、いくらか 複雑な形式になっている。このような言己の場合、どの 部分が e-mail アドレスにあたるかはすこし分かりにく いが、◇があればその中身が e-mail アドレスであるこ と、 ( ) があればそのなかは名前であることにの場合 は違うが ) というルールがある。 件名 (Subject) が、もとのメールの件名に、、 Re : " カ咐 いたものになっている。これは Re : 以降の件名のメール に対する返答であることを示し、インターネット・メー ノレにかぎらす電子メールでの一イ勺な慣行。なお、 Re: ・・について / 関して」という意ロ ・本文内に、受け取ったメールの本文がそのまま引用さ れている。引用であることを示すために、各行の先頭 に > が付いている。これも電子メールでの慣行で、原 文を引用したうえでそれにコメントを付けて返信するの おわりに するときと変わりません。 その他の返事を出す操作自体は、 である。 が、電子メールでの基本的なコミュニケーションのガ去 ふつうにメールを送信 ルの整理のガ去など、もうすこし細かい点を補足する予定 基本操作はできるようになると思います。次回は、メー 今回説明した部分で、とりあえすメールのやりとりの です。 135 ( うえはら・てったろう和歌山大学 )