1.2.1　分組交換技術(shù)的研究

1.分組交換技術(shù)研究的背景

世界上第一臺(tái)電子數(shù)字計(jì)算機(jī)ENIAC出現(xiàn)在1946年，而通信技術(shù)在一戰(zhàn)和二戰(zhàn)期間已得到發(fā)展和應(yīng)用，因此通信技術(shù)的發(fā)展比計(jì)算機(jī)技術(shù)早得多。在很長(zhǎng)一段時(shí)間中，計(jì)算機(jī)技術(shù)與通信技術(shù)之間沒(méi)有交集，各自處于獨(dú)立發(fā)展的階段。當(dāng)計(jì)算機(jī)技術(shù)與通信技術(shù)都發(fā)展到一定階段，并且社會(huì)上出現(xiàn)了新的應(yīng)用需求時(shí)，人們就會(huì)產(chǎn)生將兩項(xiàng)技術(shù)交叉融合的想法。計(jì)算機(jī)網(wǎng)絡(luò)就是計(jì)算機(jī)技術(shù)與通信技術(shù)高度發(fā)展、深度融合的產(chǎn)物。

20世紀(jì)50年代初，由于美國(guó)軍方的需要，美國(guó)半自動(dòng)地面防空（Semi-Automatic Ground Environment，SAGE）系統(tǒng)要將來(lái)自世界各地軍事基地的遠(yuǎn)程雷達(dá)信號(hào)、機(jī)場(chǎng)與防空部隊(duì)的信息，通過(guò)有線與無(wú)線的通信線路傳送到位于美國(guó)本土的一臺(tái)大型機(jī)進(jìn)行處理，這項(xiàng)研究開(kāi)始了計(jì)算機(jī)技術(shù)與通信技術(shù)結(jié)合的嘗試。隨著SAGE系統(tǒng)的實(shí)現(xiàn)，美國(guó)軍方又產(chǎn)生了將分布在不同地理位置的多臺(tái)計(jì)算機(jī)通過(guò)通信線路連接成計(jì)算機(jī)網(wǎng)絡(luò)的需求。

1957年10月4日，美國(guó)報(bào)紙報(bào)道了蘇聯(lián)在拜科努爾航天中心成功發(fā)射一顆重量為83公斤的小型人造地球衛(wèi)星“史伯尼克（Sputnik）”的消息。這引起了美國(guó)的高度重視。五天之后，美國(guó)總統(tǒng)在記者招待會(huì)上表示了“嚴(yán)重不安”。兩個(gè)月后，美國(guó)總統(tǒng)向國(guó)會(huì)提出建立高級(jí)研究計(jì)劃署（Advanced Research Projects Agency，ARPA）的動(dòng)議。國(guó)會(huì)同意組建ARPA，并批準(zhǔn)了520萬(wàn)美元的儲(chǔ)備金與2億美元的項(xiàng)目總預(yù)算。盡管ARPA的辦公地點(diǎn)在美國(guó)國(guó)防部，但是它還是被定位成獨(dú)立的科研管理機(jī)構(gòu)，由非軍方人員主持，同時(shí)在科研項(xiàng)目上得到了寬松的資金支持與較高的自由度。ARPA沒(méi)有實(shí)驗(yàn)室與科學(xué)家，只是通過(guò)簽訂合同和發(fā)放許可的方式，選擇一些大學(xué)、研究機(jī)構(gòu)和公司為該機(jī)構(gòu)服務(wù)。1972年，ARPA更名為DARPA（Defense ARPA），即美國(guó)國(guó)防部高級(jí)研究計(jì)劃署。

在與蘇聯(lián)的軍事力量競(jìng)爭(zhēng)中，美國(guó)軍方發(fā)現(xiàn)需要一個(gè)專(zhuān)門(mén)用于傳輸軍事命令與控制信息的通信網(wǎng)絡(luò)。他們希望這種網(wǎng)絡(luò)在因戰(zhàn)爭(zhēng)或自然災(zāi)害導(dǎo)致部分通信設(shè)備或通信線路受到破壞的情況下，通信網(wǎng)絡(luò)仍然能利用剩余的部分繼續(xù)工作，這就是網(wǎng)絡(luò)可生存性（Network Survivability）研究的出發(fā)點(diǎn)。傳統(tǒng)的通信線路與電話交換網(wǎng)無(wú)法滿足這個(gè)要求，于是ARPA開(kāi)始籌劃啟動(dòng)新一代通信網(wǎng)絡(luò)技術(shù)——分組交換網(wǎng)的研究工作。這就是我們?cè)谟懻撚?jì)算機(jī)網(wǎng)絡(luò)時(shí)一定會(huì)涉及的分組交換概念，以及世界上第一個(gè)分組交換網(wǎng)——ARPANET產(chǎn)生的背景。

2.分組交換概念的提出

在討論ARPANET的產(chǎn)生時(shí)，必然涉及蘭德公司與約瑟夫·利克萊德（J.C.R.Licklider）、拉里·羅伯茨（Larry Roberts）、保羅·巴蘭（Paul Baran）、唐納德·戴維斯（Donald Davies）等計(jì)算機(jī)科學(xué)家。實(shí)際上，分組交換概念與技術(shù)的研究是由三組科學(xué)家并行開(kāi)展的。

（1）MIT與約瑟夫·利克萊德、拉里·羅伯茨的研究工作

MIT（麻省理工學(xué)院）在計(jì)算機(jī)網(wǎng)絡(luò)與分組交換技術(shù)方面早期的研究工作主要集中在1961～1967年。貢獻(xiàn)比較突出的兩位科學(xué)家是約瑟夫·利克萊德與拉里·羅伯茨。

20世紀(jì)50年代，約瑟夫·利克萊德作為MIT計(jì)算機(jī)系的副教授參加了SAGE系統(tǒng)的研究工作（如圖1-3所示）。這對(duì)于他在1962年提出星際計(jì)算機(jī)網(wǎng)絡(luò)（Intergalactic Computer Network）的概念有很大幫助。在有關(guān)星際計(jì)算機(jī)網(wǎng)絡(luò)的備忘錄中，他描述了在全球范圍內(nèi)將很多計(jì)算機(jī)互聯(lián)起來(lái)，使每個(gè)人從任何地點(diǎn)都能共享數(shù)據(jù)與程序的設(shè)想。

圖1-3　約瑟夫·利克萊德與MIT的SAGE研究室

ARPA的信息處理辦公室（Information Processing Techniques Office，IPTO）主要負(fù)責(zé)計(jì)算機(jī)網(wǎng)絡(luò)、超級(jí)計(jì)算機(jī)等研究課題。1962年，約瑟夫·利克萊德離開(kāi)MIT加入ARPA，并在后來(lái)成為IPTO的首席執(zhí)行官。他關(guān)于計(jì)算機(jī)網(wǎng)絡(luò)的設(shè)想正好和ARPA的“網(wǎng)絡(luò)可生存性”項(xiàng)目的研究目標(biāo)一致。他的星際計(jì)算機(jī)網(wǎng)絡(luò)的思想對(duì)ARPANET的研究產(chǎn)生了重要的影響。

另一位在分組交換理論研究方面做出重要貢獻(xiàn)的科學(xué)家是拉里·羅伯茨。1963年，拉里·羅伯茨在MIT獲得博士學(xué)位之后加入MIT林肯實(shí)驗(yàn)室。他在1961年發(fā)表了論文“Information Flow in Large Communication Network”，全面闡述了分組交換的思想。1965年，拉里·羅伯茨與合作者在分組交換技術(shù)上邁出了劃時(shí)代的一步。他們將位于MIT與加州的兩臺(tái)分時(shí)計(jì)算機(jī)系統(tǒng)通過(guò)電話線路連接起來(lái)，實(shí)現(xiàn)了存取數(shù)據(jù)、運(yùn)行程序。他們的研究工作第一次向世人證實(shí)了分組交換理論的可行性。當(dāng)時(shí)，他們將計(jì)算機(jī)之間相互傳送文件的通信規(guī)約稱(chēng)為協(xié)議（Protocol）。

1967年10月，作為ARPA的首席科學(xué)家，勞倫斯·羅伯茨提交了第一個(gè)分組交換網(wǎng)ARPANET研究計(jì)劃，并組織完成了ARPANET結(jié)構(gòu)與通信協(xié)議的規(guī)劃、設(shè)計(jì)工作。

（2）蘭德公司與保羅·巴蘭的研究工作

1948年5月，蘭德（Research and Development，RAND）公司在美國(guó)加州圣莫尼卡成立，它是美國(guó)政府在二戰(zhàn)后成立的一個(gè)戰(zhàn)略研究機(jī)構(gòu)。當(dāng)時(shí)，蘭德公司的研究工作的重點(diǎn)是冷戰(zhàn)時(shí)期的軍事戰(zhàn)略問(wèn)題。1960年，美國(guó)國(guó)防部授權(quán)蘭德公司尋找一種有效的通信網(wǎng)絡(luò)解決方案。

當(dāng)時(shí)保羅·巴蘭在蘭德公司的數(shù)學(xué)學(xué)部計(jì)算機(jī)科學(xué)分部工作。他最有興趣的研究課題是在受到核攻擊之后，如何維持網(wǎng)絡(luò)的通信能力。1962年，保羅·巴蘭為蘭德公司撰寫(xiě)了11份報(bào)告，討論了分組交換（Packet Switching）與存儲(chǔ)轉(zhuǎn)發(fā)（Store and Forward）的基本工作原理，其中影響最大的是1964年3月發(fā)表的論文“On Distributed Communication Networks”。保羅·巴蘭利用計(jì)算機(jī)和容錯(cuò)技術(shù)設(shè)計(jì)了比電話交換網(wǎng)更為健壯的通信網(wǎng)絡(luò)。不過(guò)，當(dāng)時(shí)他的許多同事對(duì)計(jì)算機(jī)知識(shí)了解甚少，因此多數(shù)人認(rèn)為他的研究成果沒(méi)有意義。美國(guó)軍方就依據(jù)巴蘭的設(shè)想開(kāi)展試驗(yàn)的問(wèn)題與AT&T公司接觸時(shí)，遭到AT&T公司的強(qiáng)烈反對(duì)。當(dāng)保羅·巴蘭在AT&T總部的一次會(huì)議上闡述他關(guān)于將數(shù)據(jù)報(bào)文“分組”傳送的想法時(shí)，一位高管打斷他：“等一等，小伙子。你真的是說(shuō)在信號(hào)還沒(méi)有傳輸?shù)搅硪欢藭r(shí)就拆線嗎？”這一點(diǎn)也不奇怪，因?yàn)锳T&T的技術(shù)人員已經(jīng)習(xí)慣于模擬語(yǔ)音電話通信的“面向連接”服務(wù)模式。當(dāng)時(shí)電話交換機(jī)采用的是人工接線，如果一位用戶(hù)從洛杉磯給紐約的一位同事打電話，洛杉磯的接線員首先將用戶(hù)線接到交換機(jī)上，呼叫紐約的電話交換機(jī)；紐約的接線員接收到呼叫后，將被呼叫的用戶(hù)線接到交換機(jī)之后，通信雙方才可以通話。通話結(jié)束之后，洛杉磯與紐約交換機(jī)的接線員才可以拆線。這與保羅·巴蘭提出的分組交換有根本的區(qū)別。

盡管AT&T公司最終沒(méi)有接受這位年輕人的建議，但是保羅·巴蘭還是繼續(xù)研究這個(gè)問(wèn)題，撰寫(xiě)學(xué)術(shù)論文，進(jìn)一步完善自己的設(shè)計(jì)思想。圖1-4是對(duì)分組交換網(wǎng)理論做出重要貢獻(xiàn)的計(jì)算機(jī)科學(xué)家保羅·巴蘭。

（3）NPL與唐納德·戴維斯的研究工作

在1967年下半年舉行的ACM SIGOPS會(huì)議上，英國(guó)國(guó)家物理實(shí)驗(yàn)室（National Physical Laboratory，NPL）的唐納德·戴維斯在論文中描述了一個(gè)類(lèi)似的網(wǎng)絡(luò)系統(tǒng)。他引用了保羅·巴蘭的研究成果，并且在NPL建立了一個(gè)實(shí)驗(yàn)系統(tǒng)。這個(gè)實(shí)驗(yàn)系統(tǒng)證實(shí)了分組交換概念的正確性。圖1-5是對(duì)分組交換網(wǎng)理論做出重要貢獻(xiàn)的科學(xué)家唐納德·戴維斯。

圖1-4　保羅·巴蘭

圖1-5　唐納德·戴維斯和他的實(shí)驗(yàn)系統(tǒng)

分組交換概念的產(chǎn)生得益于這三部分科學(xué)家前期的理論研究和實(shí)驗(yàn)工作。

3.分組交換技術(shù)的研究

早期構(gòu)建通信網(wǎng)絡(luò)通常采用兩種基本拓?fù)洌?span id="tva406c" class="yanse">集中式（Centralized）和非集中式（Decentralized），相應(yīng)的拓?fù)錁?gòu)型如圖1-6所示。在集中式網(wǎng)絡(luò)中，所有節(jié)點(diǎn)都與中心節(jié)點(diǎn)相連，節(jié)點(diǎn)之間交換的數(shù)據(jù)都通過(guò)中心節(jié)點(diǎn)轉(zhuǎn)發(fā)。如果中心節(jié)點(diǎn)損壞或工作不正常，全網(wǎng)的通信就會(huì)癱瘓。非集中式網(wǎng)絡(luò)使用了多個(gè)中心節(jié)點(diǎn)，相當(dāng)于將多個(gè)集中式網(wǎng)絡(luò)連接起來(lái)。當(dāng)時(shí)美國(guó)的通信系統(tǒng)基本上都采用非集中式網(wǎng)絡(luò)結(jié)構(gòu)。非集中式網(wǎng)絡(luò)仍然無(wú)法克服集中式結(jié)構(gòu)的固有缺點(diǎn)。在大型網(wǎng)絡(luò)中，中心節(jié)點(diǎn)一般都會(huì)成為網(wǎng)絡(luò)系統(tǒng)可靠性的瓶頸。

圖1-6　集中式和非集中式網(wǎng)絡(luò)的拓?fù)錁?gòu)型

保羅·巴蘭提出了第三種設(shè)計(jì)方案——分布式網(wǎng)絡(luò)（Distributed Network）結(jié)構(gòu)。他的基本設(shè)計(jì)思想是：分布式網(wǎng)絡(luò)中沒(méi)有中心交換節(jié)點(diǎn)，網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)都通過(guò)通信線路與若干個(gè)相鄰節(jié)點(diǎn)連接，形成一個(gè)網(wǎng)狀結(jié)構(gòu)。圖1-7給出了分布式網(wǎng)絡(luò)的拓?fù)錁?gòu)型。顯然，這是一種分布式、高度容錯(cuò)的網(wǎng)狀結(jié)構(gòu)。

圖1-7　分布式網(wǎng)絡(luò)的拓?fù)錁?gòu)型

保羅·巴蘭建議在新的通信系統(tǒng)中采用分組交換技術(shù)。他想象在一個(gè)沒(méi)有中心節(jié)點(diǎn)的網(wǎng)絡(luò)中，節(jié)點(diǎn)之間傳輸?shù)臄?shù)據(jù)按事先規(guī)定的格式封裝在一種稱(chēng)為分組（Packet）或包的傳輸單元中。分組包含源節(jié)點(diǎn)與目的節(jié)點(diǎn)的地址。源節(jié)點(diǎn)與目的節(jié)點(diǎn)之間可以有多條傳輸路徑。每一條路徑都是由多個(gè)中間轉(zhuǎn)發(fā)節(jié)點(diǎn)與通信線路組成。當(dāng)分組到達(dá)一個(gè)轉(zhuǎn)發(fā)節(jié)點(diǎn)時(shí)，按照“存儲(chǔ)轉(zhuǎn)發(fā)”的思路，這個(gè)轉(zhuǎn)發(fā)節(jié)點(diǎn)先將分組接收、存儲(chǔ)起來(lái)，判斷分組傳輸正確之后，啟動(dòng)路由算法（Routing Algorithm）為每個(gè)分組選擇到達(dá)目的節(jié)點(diǎn)“最佳”的下一個(gè)轉(zhuǎn)發(fā)節(jié)點(diǎn)，然后將分組發(fā)送到下一個(gè)轉(zhuǎn)發(fā)節(jié)點(diǎn)，直至到達(dá)目的節(jié)點(diǎn)。節(jié)點(diǎn)的路由算法可以根據(jù)相鄰的節(jié)點(diǎn)與線路的狀態(tài)決定路由。如果路徑中有節(jié)點(diǎn)損壞或線路忙，分組可以繞過(guò)故障節(jié)點(diǎn)，選擇其他傳輸路徑，最終總會(huì)到達(dá)目的節(jié)點(diǎn)。

在討論分組交換概念的形成過(guò)程時(shí)，有一些細(xì)節(jié)值得注意。保羅·巴蘭1926年出生于波蘭，1959年獲UCLA電氣工程碩士學(xué)位。在進(jìn)入蘭德公司之前，保羅·巴蘭曾經(jīng)在美國(guó)Eckert-Mauchly公司工作，參與早期UNIVAC計(jì)算機(jī)研制工作，有著良好的計(jì)算機(jī)技術(shù)背景。唐納德·戴維斯1924年出生于英國(guó)，在倫敦帝國(guó)學(xué)院獲數(shù)學(xué)、物理雙學(xué)位。1947年，唐納德·戴維斯進(jìn)入NPL，在圖靈的領(lǐng)導(dǎo)下研制英國(guó)第一臺(tái)計(jì)算機(jī)Pilot ACE。從保羅·巴蘭與唐納德·戴維斯的教育經(jīng)歷中可以看到：正是由于他們有良好的計(jì)算機(jī)知識(shí)背景，又能夠開(kāi)拓性地將計(jì)算機(jī)與通信知識(shí)融合，才能夠在計(jì)算機(jī)網(wǎng)絡(luò)理論方面取得舉世矚目的研究成果。