IMP: インターネットルータの祖先

2.11BSD

先日の2.11BSDのエントリでも触れたが、IMP（Interface Message Processor）に対応するコード（/sys/netimp/）があって驚いた。ということでそこからIMPとは何者かを探っていきたい。特に今回調べたのは、IMPとホスト間のプロトコルである、1822ホストアクセスプロトコルについてである。

この図は1969年のARPANETのネットワークトポロジを示している*1。現在地球上を網の目のように覆っているインターネットも、当時はたった四つのサイトの計算機をつないだものでしかなかった。さて、各サイトにあるIMPとは何だろうか。IMPはインターネットルータの祖先であり、後にPSN（Packet Switch Node）と呼ばれるようになった*2。

ARPANETは全米各地に存在するさまざまに異なるアーキテクチャの大型計算機を相互接続し、科学者間で資源を共有しようというモチベーションで始まった。そして、まだまだ非力だったホストの計算機資源をプロトコル処理に奪われるのを嫌って、外付けの安い機械にやらせましょうという背景で登場したのがIMPだった。ルーティングやフロー制御など通信の面倒な処理はIMPに押しつけ、ホストは単純なネットワーキング処理だけを担ったのである。ブツとしてはHoneywell 516というミニコンがベースになっており、外観は「Interface Message Processor (IMP) Honeywell 516」などから拝むことができる（その後いくつかのバリエーションが登場している）。

IMPの仕様はBBN Report 1822で定められており、その由来からIMPのプロトコルは1822プロトコルと呼ばれる。IMPはストアアンドフォワード型のパケットスイッチ機能を提供している。ホストが送信したメッセージは、IMPにてパケットに分割されて宛先に送られる。受信側のIMPはパケットからメッセージを再構築すると、RFNM (Request For Next Message)を返信する。送信ホストがRFNMを受信すると次のメッセージが送信可能になる。経路中でパケットが損失した場合、IMPが再送処理を行うが、何らかの理由で再送できない場合は送信側のIMPからRFNMの代わりにIncomplete Transmissionメッセージが返る。

メッセージは96bitから8159bitの可変長であり、その先頭の96bitはリーダ（leader）と呼ばれていた。もちろんヘッダのことであるが、当時はこちらの方が通りがよかったのだろうか。8159bitとは切りが悪いが実際はpaddingされて8160bitになる。パケットの最大サイズは1008bitだったので、((8160 - 96) / 1008)で最大8パケットに分割された。

リーダの定義はif_imp.hにある。

/*
 * Structure of IMP 1822 long leader.
 */
struct control_leader {
        u_char  dl_format;      /* leader format */
        u_char  dl_network;     /* src/dest network （未使用）*/
        u_char  dl_flags;       /* leader flags */
        u_char  dl_mtype;       /* message type */
        u_char  dl_htype;       /* handling type */
        u_char  dl_host;        /* host number */
        u_short dl_imp;         /* imp field */
        u_char  dl_link;        /* link number （BBN report 1822ではmessage idの前半8bitということに）*/
        u_char  dl_subtype;     /* message subtype */
};

struct imp_leader {
               struct  control_leader il_dl;
#define il_format       il_dl.dl_format
#define il_network      il_dl.dl_network
#define il_flags        il_dl.dl_flags
#define il_mtype        il_dl.dl_mtype
#define il_htype        il_dl.dl_htype
#define il_host         il_dl.dl_host
#define il_imp          il_dl.dl_imp
#define il_link         il_dl.dl_link
#define il_subtype      il_dl.dl_subtype
               u_short il_length;      /* message length */
};

ホストのアドレスであるが、8bitのホスト番号dl_hostと16bitのIMP番号dl_impの合計24bitで構成されていた。BBN report 1822ではメッセージの識別に12bitのメッセージIDを使うとある。TCP/IPのポート番号に近い考えだろうか。dl_linkがそれに相当するが、ちょっと使われ方が違うような。

余談になるが、その後、1822ホストアクセスプロトコルを拡張した1822LがRFC 851で提案されている（The ARPANET 1822L Host Access Protocol）。Lはlogicalの意味。1822ではARPANET上の物理ポート位置でアドレッシングされていたけど、論理的なホスト名（16bit整数）が使えるように拡張された。アドレスはIMP番号8bit、ホスト番号6bitに縮小され、実質的なホスト数は15000弱になってしまった。RFC 851には1822の24bitアドレスについて「These fields are quite large, and the ARPANET will never use more than a fraction of the available address space.」と書かれている。IPv4アドレス枯渇とか騒がれている昨今からすると、非常に牧歌的である。また、1822LはC/30 IMPのみでサポートされた。他のIMPは搭載メモリが足りなくて実装できなかったようだ。2.11BSDが対応しているのはオリジナルの1822だけのようだ。さらにRFC 1005（The ARPANET AHIP-E Host Access Protocol (Enhanced AHIP)）ではIPデータグラムをARPANETで使うための拡張について提案されている。余談ついでに記念すべきRFC 1はIMPに関するメモだったりする。

2.11BSDの場合、ユーザレベルのプログラミングは当然BSDソケットを使う訳だが、アドレスファミリはAF_IMPLINKになる。Mac OS Xのヘッダファイルを見てびっくり。まだAF_IMPLINKが残っているのね。glibcにはない。

今日はここまで。具体的にソースコードを追うのは次回で。

最後になるが、当時の資料を探していて、U.TexasのChris Edmondson-Yurkanan教授のTHINK Protocolsというページを見つけた。BBN report 1822を含めていろいろ貴重な資料がありそうなので、後でじっくり読みたい。

インターネットの起源

インターネットの起源

*1:ARPANETが役割を終えて停止したのが1989年？なので、20年間存在したことになる。

*2:PSNはホストインタフェースとして1822以外にX.25もサポートするようになった。