UNIX MAGAZINE 1997年4月号

キーフレーズ

UNIX MAGAZINE NFS 000 システム CPU 1997 -2 ネットワーク Windows クライアント ファイル 対応 -3 1996 サーバー return http:// SCSI FAX インターネット TOK Java TCP/IP SPARC プログラム -1 Windows NT FreeBSD www MHz 機能 データ 登録商標 Sun 場合 アプリケーション SPARCstation frame キャッシュ ソフトウェア () サポート 製品 ワークステーション セキュリティ フレーム Windows 95 Web WWW 利用 Server for RPC Solaris HTML シリーズ Subject -4 co.jp ファイルシステム Ultra アクセス TEL NET 4GB 100 Tel html アドレス 必要 Microsoft 命令 可能 Macintosh ディスク OOO プロトコル RISC Message 価格 情報 Alpha 処理 end 日本 できる CALL 2GB Netscape Radix 管理 実行 高速 WindowsNT バックアップ 128 root

目次ページ

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

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

0 alendar 4 ApriI 7 ~ 11 ■ IEEE lnfocom ' 97 ・神戸ポートアイランド神戸国際聳易 ◇大阪丿ごご完物楚」 : 学研斗村田正幸 (Tel 06 ー 850-6586 ) 8 ~ 11 ー Comdex Japan ' 97 ・千葉美浜区中瀬粥長メッセ ◇ソフトノヾンク・エキスボ・ジャノヾン (Tel 03 ー 5642 ー 8433 ) 8 ~ 11 ・ ICE (lnternet Commerce Expo) Georgia WorId Congress Center, Atlanta ◇ IDG ワールドエキスボ・ジャノヾン (TeI 03-5276 ー 3751 ) 14 ~ 19 ・ Germany MessegeIande, Hannover ◇ドイツ産業見本市日本代表部 (TeI 03-3363 ー 6631 ) 21 ~ 25 ■ SeyboId Seminars New York ' 97 ・ Jacob K. Javits Convention Center, New York ◇ソフレヾンク・エキスボ・ジャノヾン (Tel 03 ー 5642 ー 8433 ) 23 ~ 25 ・ lnternet 、 vorld Japan ' 97 ・千葉美浜区中瀬幕張メッセ ◇インターネットワールドジャパン事務局 (Tel 03-5562-5570 ) 5 May 5 ~ 9 ■ Net 、 vorld 十 lnterop 97 Las Vegas ・ Las Vegas ◇ソフト / ヾンク・エキスボ・ジャノヾン (Tel 03-5642-8433 ) 7 ~ 10 ■ lnternet 、 vorld Korea ' 97 ・ SeouI Yoido Exhibition Center, seoul ◇ MeckIermedia ( Tel 十 1 ー 203-226-6967 ) 13 ~ 16 ・ビジネスショウ ' 97 鯨 ・東京江東区有明東京ビッグサイト ◇日本糸営協会 (TeI 03-3403-8910 ) UNIX MAGAZINE 1997.4 ・ 4 / 1997 28 ~ 30 ■セミコン関西 97 ・躑友住之江区南港インテックス友 ◇ SEMI ジャノヾン (TeI 03 ー 3222-5755 ) 28 ~ 30 ・ ' 97 テレコム・ジャ / ヾン ( 情甬信総合展 ) 東京豊島区東池袋サンシャインシティ ◇日本糸斉新聞ネ上 (Tel 03-5255 ー 2847 ) 6 June ・ Spring CES ' 97 ( 1997 lnternational Spring Consumer EIectronics Show) ・ Georgia WorId Congress Center , At lanta ◇ Margaret CassiIly ( TeI 十 1 ー 703-907-7600 ) ー Comdex Spring ,97/ 、 Vindows World ' 97 ・ Georgia World Congress Center, Atlanta ◇ソフトバンク・エキスボ・ジャパン (Tel 03-5642 ー 8433 ) 2 ~ 6 ・ NetWorld 十 lnterop 97 Tokyo ・千葉美浜区中瀬幕張メッセ ◇ソフトノヾンク・エキスボ・ジャノヾン (Tel 03 ー 5642 ー 8433 ) 4 ~ 6 ■ビジネスショウ ' 97 大阪 ・友住之江区南港インテックス躑反 ◇日 : 釜営協会関西本部 (TeI 06-443-6093 ) 16 ~ 19 ■ COOTS ' 97 (3rd Conference 0 Ⅱ Object-Ori- ented Technologies & Systems) ・ PortIand Marriott Hotel, Portland, Oregon ◇ USENIX Conference Office ( Fax 十 1 ー 714 ー 58 & 9706 / E—mail: [email protected]/ 19 ~ 21 ・ E3 Atlanta (Electronic Entertainment Expo Atlanta 97 ) ・ Georgia World Congress Center & Georgia Dome, At- lanta ◇ IDG ワールドエキスボ・ジャパン (Tel 03 ー 5276 ー 3751 ) 25 ~ 28 ■ Windows 、 Vorld Expo Tokyo ' 97 ・千葉美浜区中瀬幕張メッセ ◇ IDG ワールドエキスボ・ジャノヾン (Tel 03-5276 ー 3751 ) 19