連載：インターネット・サイエンスの歴史人物館（7）ポール・バラン

自律的パケット・ルーティングの確立

ポール・バランは、核攻撃に耐えられる通信網を考察し、メッセージを分割して多数のデジタル回路（ノード）に分散して伝送するネットワークを実現しようとした。メッセージを分割したブロックにタグをつけて届け先でメッセージを再現するアイデアは、レオナード・クラインロックも考案していたが、バランは各ノードでメッセージ・ブロックが最短経路を自動的に選択するルータの基本原理を考案し、インターネットの礎を築いた。バランが構想した中央制御に頼らないメッシュ型の分散ネットワークは、膨大なアクセスを支える今日のインターネットを支えている。

UNIVACとミサイル開発を経験

ポール・バランは1926年4月29日にポーランドで生まれ、2歳の時に両親とともに米国に移民した。両親はマサチューセッツ州ボストンでしばらく働き、ペンシルバニア州フィラデルフィアで食品雑貨店を営むようになった。バランは食品雑貨店を手伝いながら地元の高校を卒業し、ドレクセル大学で1949年に電気工学の学位を取得した。バランは、1946年に最初の電子計算機ENIACを完成したジョン・モークリとプレスパー・エッカートが1948年12月に設立したエッカート＝モークリ・コンピュータ・カンパニー（EMCC）に入社し、最初の商用コンピュータUNIVACの真空管やゲルマニウム・ダイオードをテストする仕事に就いた。

バランは1950年にカリフォルニア州ロサンゼルスに移り、レイモンド・ローゼン・エンジニアリング・プロダクツ社に就職した。かれは1955年にエヴェリン・マーフィーと結婚し、ヒューズ・エアクラフトのシステム部門に転職した。　バランはヒューズで、レーダーのデータ処理システムの仕事をしながら、カリフォルニア大学ロサンゼルス校の夜間コースに通いコンピュータとトランジスタを研究し、ミニットマン核ミサイルの制御システムの設計にも携わるようになった。

ランドで国防通信網の研究者に

1959年に工学修士号を取得したバランは、ランド・コーポレーションの数学部門のコンピュータ・サイエンス課の職を得た。ランドは、第2次世界大戦中に発達したオペレーションズ・リサーチに関する研究を継続するために、非営利の研究機関として1948年に設立された。ソ連が1949年8月に最初の核実験を行ってから、米国空軍は全米のレーダー基地の情報をコンピュータで処理して、迎撃管制や兵器制御に活用する防空システム構想の実現に、マサチューセッツ工科大学（MIT）とランドの研究者を動員した。SAGEと呼ばれたこのシステムの配備は1958年7月に始まり、1963年までに全米23ヵ所にコンピュータ・センターが開設されることになっていた。

しかし、ソ連が1957年10月4日に人工衛星スプートニク（Sputnik-1）の打ち上げに成功すると、大陸横断弾道ミサイルによる攻撃が可能だと考えられるようになり、冷戦の緊張感は極度に高まった。バランは核攻撃の可能性を考えるうちに、SAGEの通信システムが分断されると、指揮管制システムが機能不全に陥ることに気づいた。

核攻撃は、先制攻撃に対する即時報復能力によって抑止されると考えられていた。しかし、1回の攻撃で指揮管制システムを破壊して報復攻撃能力を著しく低下させることができるのであれば、先制攻撃で相手の抑止力を削ぐことが可能になる。バランは、核攻撃を受けても機能し続ける通信網が実現できれば、先制攻撃をしかけても優位に立つ可能性はなくなると考えた。

分散型通信ネットワークのアイデア

通常の電話回線網は、中心点のハブから車輪のスポークのように回線が八方に広がり、地域ごとにハブを設置して、ハブとハブを長距離回線で相互接続する。このようなネットワークでは、ハブが破壊されると、その地域の通信は機能不全に陥る。無線通信ではこのような事態を回避できそうだが、地球の上空で電波を反射する電離層の近傍で核爆発を起こすと、大量の帯電粒子が発生し無線通信は数時間にわたり不能になると考えられた。

【図版】集中型ネットワークとクラスタ型ネットワーク（Paul Baran「On Distributed Communications: I Introduction to Distributed Communications Networks」Memorandum RM-3240-PR、August 1964 P2）
http://www.rand.org/pubs/research_memoranda/2006/RM3420.pdf

生物の脳は部分的に損傷しても、その部分を迂回して神経回路網を維持する。バランは脳神経の学識を得るため、MITの神経生理学者ウォーレン・マッカローを訪ねた。マッカローは1943年に、「神経活動に内在する論理計算」を著し、神経回路網を形成しているニューロンの信号の入出力が数学的規則に従うことを示し、ジョン・フォン・ノイマンなどデジタル・コンピュータのパイオニアに影響を与えた。

バランは、脳の神経回路は複数の経路をもつ同じような役割を果たす論理素子のネットワークで、部分的な障害で全体が機能不全に陥ることがないことを理解した。バランは神経回路に近いネットワーク・モデルを、分散ネットワーク（distributed network）と名づけた。

多数のノードを経由して情報を伝達するこのモデルは、アナログ信号を扱う電話交換機には不向きなネットワークだが、情報を０と１で伝達するデジタル信号は多数のノードを経由しても品質はほとんど劣化しない。しかも、コンピュータによる転送処理は、リレー型の電話交換機よりも格段に速い。

【図版】分散型ネットワーク（Paul Baran「On Distributed Communications: I Introduction to Distributed Communications Networks」Memorandum RM-3240-PR、August 1964 P2）
http://www.rand.org/pubs/research_memoranda/2006/RM3420.pdf

バランの研究は1960年末に小規模なプロジェクトに発展し、核攻撃に対して耐久性をもつネットワークを構成する各ノードに要求される必要最低限の伝送路の数を検討した。そして、324ノード（18Ｘ18ノード）の格子状のネットワークについて、攻撃に対する耐久性をモンテカルロ・シミュレーションで調べた。バランはその結果、各ノードが3か4の接続冗長性を備えていれば、耐久性は確保できることを確認した。

【図版】冗長レベル3のリンクと冗長レベル4のリンク（Paul Baran「On Distributed Communications: I Introduction to Distributed Communications Networks」Memorandum RM-3240-PR、August 1964 P4）
http://www.rand.org/pubs/research_memoranda/2006/RM3420.pdf

ルーティング・テーブルとアルゴリズムを開発

この当時ベル電話研究所はT-1 PCM多重通信システムで、通常の電話回線で1秒間に150万ビットのデジタル・データを送信できることを示していたが、約1,800mごとに信号増幅器を配備する必要があった。マイクロ波による無線通信は低コストだと考えられていたが、約30kmごとに中継局を配備する必要があり、雨天で信号が減衰する問題を抱えていた。また、衛星通信は可能だったが、静止衛星ではないため常時通信には向かなかった。

バランは、伝送速度が異なるこれらの通信手段を相互接続する方法を考え、メッセージを標準的なメッセージ・ブロックに分割して、それぞれのブロックに宛名と送り主の住所と標識を付加することを思いついた。郵便局員はポストから収集した手紙を仕分けして、それぞれの手紙の束を目的地に最短経路で向かうトラックで送り出す。バランはこの作業を小規模なコンピュータに担わせれば、分散ネットワークでメッセージ・ブロックのルーティングを自動化できると考えた。

【図版】メッセージ・ブロック（Paul Baran「On Distributed Communications: I Introduction to Distributed Communications Networks」Memorandum RM-3240-PR、August 1964 P22）
http://www.rand.org/pubs/research_memoranda/2006/RM3420.pdf

バランが考案した仕組みでは、まず各メッセージ・ブロックに経由したノードの数（ホップ数）を加算方式で記録し、各ノードが全てのノードから届いたメッセージ・ブロックのホップ数を表に記録できるようにする。ノードのメモリが記憶する表には、近接するノードへのリンク（行）ごとに全てのノード（列）から届くメッセージのホップ数を記録させる。ノードのプログラムは、送り出すメッセージのアドレスと表の最小ホップ数をマッチングさせて、最短経路を示すリンクを選択する。

バランはこの仕組みを「ホットポテト探索的ルーティング（Hot-Potato Heuristic Routing）と名付けた。熱い焼き芋をすぐに手放すイメージで、ノードは届いたメッセージ・ブロックを素早く送り出す。最初に選択したリンクが混雑していたり破壊されている場合は、次善のリンクを自動的に選ぶ。

国防通信網の挫折

メッセージを分割してノードのメモリに蓄えてから転送する蓄積交換（store-forward）型の時分割多重通信（time division multhiplexing）の研究は、MITの大学院生だったレオナード・クラインロックが1961年5月に発表した博士論文で先鞭をつけた。バランは同様のアイデアで研究を進めていたが、ルーティング・テーブルを活用するアルゴリズムにより自己学習するネットワークと自律的な最短経路探索を実現し、適応型蓄積交換ルーティング（adaptive store-forward routing）を実現する仕組みに発展させていた。

バランは1961年夏に空軍関係者向けに覚え書きを執筆し、ランドの通信専門家と議論を重ねて信奉者を獲得する活動を続け、AT&Tの幹部の説得に動き出した。しかし、AT&Tの幹部はバランが電話回線を理解していないと考え、分割されたメッセージが最短経路を探索して電話網を徘徊するアイデアを拒否し続けた。

バランは自分の構想に対する批判に応えるために、報告書を執筆することを決め。議論を重ねながら11冊の報告書を記述して、1964年3月に発行されたIEEEの通信システムの論文集で発表した。ランドは、バランが提示した方法以外に攻撃に耐えられ柔軟なユーザ間通信を実現できる手段はないと判断し、1965年8月に空軍に対して蓄積交換型ネットワークを構築する開発プロジェクトを正式に提案した。空軍はこの提案を受け入れたが、国防総省はプロジェクトを新たに設立された国防通信局（DCA）に担当させることを決めた。国防通信局はデジタル技術が理解できず、AT&Tも否定的な姿勢を示し続けたため、バランは分散ネットワークの実現を諦めざる得なくなった。

インターネットへのバランの貢献

バランが挫折感をおぼえた頃、ランド・コーポレーションからスピンアウトしたサンタモニカのシステム開発（System Developement Corporation：SDC）とボストン近郊のMITリンカーン研究所は、タイムシェアリング・システムOSを搭載した2台のコンピュータで、プログラムの接続実験を時分割多重通信で行う準備を進めていた。この大陸横断ワイド・エリア・ネットワーク（WAN）の実験では、ARPA情報処理技術部（IPTO）の要請でリンカーン研究所のローレンス・ロバーツが中心的な役割を果たしていた。ロバーツは65年秋にMITで開催されたタイムシェアリングのシンポジウムで、英国物理学研究所（NPL）のドナルド・ワッツ・デービスにWANの実験について話した。

デービスは65年12月に、蓄積交換型のデジタル通信網の青写真を描き、66年にロンドンで開催された会議でその構想を発表した。デービスの講演を聴いた英国国防省（Ministry of Defense）の人物はデービスに、米国のバランが極めて似たネットワークを提案していることを伝えた。ロバーツは66年12月にARPA IPTOのチーフサイエンティストになり、67年10月に開催された米コンピュータ学会（ACM）のOSの会議でARPANETの構想を発表した。デービスはこの会議で、メッセージ・ブロックを「パケット」と表現し、バランの「分散コミュニケーションについて」の論文に言及した。

ロバーツは、この会議で初めてバランの研究を知った。ロバーツは核攻撃に耐久性をもつネットワークの構築を目指していたわけではなかったが、タイムシェアリング・システムによる蓄積交換型の時分割多重通信を実現する上で、バランが考案した自律的なルーティングを実現するテーブルとアルゴリズムを採用した。バランは、コンピュータの時分割（time sharing）システムと通信の時分割（time division）システムを結びつける方法を、誰よりも早く見いだしコンピュータ・シミュレーションで検証していた。ARPANETはバランが描いた分散ネットワークとして離陸したわけではなかったが、TCP／IPによりインターネットはメッシュ化あるいはグリッド化の方向に向かい、膨大なユーザ・アクセスの負荷分散を支えている。

シリコンバレーの起業家に

ポール・バランは1968年にランド・コーポレーションを辞し、シリコンバレーで未来研究所（Institute for the Future）を設立して、通信業界向けにテクノロジーとビジネスの動向を予測するコンサルティング事業を始めた。バランは1972年にケーブルデータ・アソシエーツ（Cabledata Associates, Inc.）の共同設立者となり、ケーブルTV、高速モデム、衛星通信などに特化した複数の企業（Comprint、Equatorial Communications Co.、Telebit、Packet Technologies）の母体になった。バランはまた、1986年に電気料金の遠隔計測網などを手がけるメトリコム（Metricom, Inc.）の共同設立者となり、1989には対話型FAXを事業化するインターファックス（InterFax, Inc.）を設立、さらに1992年にはCom21を創業してブロードバンド向けケーブルモデム事業を立ち上げた。バランは約150の論文を書き、40の特許を取得した。バランは1990年にIEEEからアレキサンダー・グラハム・ベル・メダルを授与され、翌91年にマルコニー・インターナショナル・フェローシップ賞を贈呈された。

■■■