【原题】10 Network Papers that Changed the World
【译题】改变世界的10篇网络论文
【作者】George Varghese
【译者】蔡志平
【出处】《中国计算机学会通讯》第5卷 第5期 2009年5月
前言
在挑选这10篇论文时，我着重关注其改变网络世界的影响。当然，许多商用系统的影响就是改变了网络世界，因此我还要求每篇文章有一个令人难忘的创意。最后，我还注意到文章是否写得好，其写作风格和创意都经得起时间的考验。我依照（网络结构）自底向上的顺序将文章分类。由于此论文名单跨越从数据链路层到应用层的各个层次，我也希望这些论文能成为刚入门的学生把握网络系统的一个便捷且有启发性的综述。
数据链路协议
R·麦特卡尔菲和D·博格斯：《以太网：用于局域计算机网络的分布式分组交换》
R. Metcalfe and D. Boggs, " Ethernet: distributed packet switching for local computer networks", Communications of the ACM, v.19 n.7,July 1976, p.395~404
这篇关于以太网的开创性论文有很多美妙的想法并产生了深远影响。最初提出以太网时，人们并不信任随机算法，认为令牌环更可靠而且更具确定性。该文提出了一系列精妙的想法。例如，关于冲突检测的一个浅显描述——两个人在同一时刻说话就会产生冲突。事实上，冲突检测是在特定的空间和时间点上进行的。因此，不同站点将在不同的时间（爱因斯坦的幽灵）检测到冲突，因此需要确保冲突的普遍性（如果一个站点检测到冲突，所有站点也能检测到）。“回退算法”已经成为我们的新术语，文中甚至还包括了“性能分析”。虽然被称为千兆以太网的技术只是套用同样的名称，但足见早期版本的以太网（10M和100M）确实对网络技术产生了巨大的影响。尽管有些早期文章中说以太网是不可靠的，效能不佳（事实并非如此），以太网还是引领了风骚。
J·索尔则、D·克拉克和K·坡格兰：《为什么采用“环”？》
J. Saltzer, D. Clark, and K. Pogran. "Why a Ring?"， IEEE Seventh Data Communications Symposium, October 1981, pp. 211~217
在转向光纤传输的过渡期间，光纤不能像以太网所需的那样搭接，所以人们很自然考虑使用点对点连接的环。但是环有一个致命的缺陷——单点失效会导致整个环失效。在这篇极富洞察力的论文中，作者提出将逻辑拓扑（环）与物理拓扑（一个采用中央集线器来绕过失效节点的星型环）分离。这个想法被应用于包括FDDI（Fiber Distributed Data Interface，光纤分布式数据接口）在内的所有环形网络。逻辑和物理拓扑的分离以及其后的集线器、星型结构一起形成了局域网的联线方式。
A·G·福瑞瑟：《朝向一个统一的数字传输系统》
A.G. Fraser, "Towards a Universal Data Transport System", IEEE Journal on SelectedAreas in Communication, SAC-1, 5, Nov 1983
桑迪·福瑞瑟的论文有两个非常有趣的想法。首先，它为终端用户提供了一个与众不同的界面——位阀(a bit faucet )，这与大多数同学以为的惟一可能的常规报文接口不同。其次，它采用了信元和虚电路，并由此成就了ATM（Asynchronous Transfer Mode，异步传输模式）技术。无论你如何看待ATM，绝大部分的路由器内部都采用了信元交换和虚电路的思想(例如MPLS（Multi-Protocol Label Switch）中的标签)，甚至在IP（Internet Protocol）网络中也是如此。
路由协议
R·帕尔曼：《在扩展本地网上的一种生成树分布式算法》
R. Perlman, "An algorithm for distributed computation of a Spanning Tree in an Extended LAN", Proceedings of the 9th Symposium on Data Communications, v. 20, n.7, 1985, pp. 44~52
这是一篇非常漂亮的论文，但是几乎所有网络方面的教科书（包括帕尔曼本人写的教材）都没有给予这个算法及其中提出的多层子协议以应有的地位。其基本核心是提出了一种方法来构建一棵树：选择一个根，然后根据节点与根之间的最短路径确定节点的父节点。论文还提出了一个简单的分布式算法计算根和节点间的距离。然而，最麻烦的事情从一个丢失的根恢复（系统）的失效协议（所有教科书都忽略了这一点）。与距离矢量法中通过计数来克服失效的方法不同，文中提出的方法中采用了计时器，采用这种技术时很容易出错（你不妨试试自己去设计！）。除了完成有效的度量外，论文还提出了许多小的子协议，例如在网络拓扑变化后站点的整体动作，让各方都调低自己的计时器。虽然桥的概念是由马克·肯普夫（Mark Kempf）提出（一个绝妙的想法，只有一项专利而没发表任何论文），但是生成树已成为具有10亿美元的桥接产品市场的标准。虽然一些人为实现快速重构而对这一方法进行扩充做的不太漂亮，但原论文以其简洁、优雅和彻底而卓尔不群。
R·帕尔曼：《路由信息的容错广播》
R. Perlman, "Fault-Tolerant Broadcast of Routing Information", Computer Networks, vol 7, 1983, pp. 395~405
这篇经典论文被公认为派生自麦克奎兰（McQuilan）等【2】所写的实际上最早介绍链路状态路由的ARPANET论文。公平地讲，这篇论文指出了原文中的许多问题，并使得链路状态路由协议能真正工作。文中提出了一个很好的想法来解决容错问题：给发送较早信息的人回送较新的信息（而不是仅仅忽略旧信息）。它还考察了这种设想在分布式环境里的情况（很不容易分析）。尽管后来人们把基于棒棒糖的序号生成方法简化成简单的线性空间，但这篇论文依然是开放式通信系统互联参考模型（OSI，Open System Interconnection Reference Model）路由，以及后来由约翰·莫伊（John Moy）修改成的OSPF（Open Shortest Path First，开放最短路径优先）协议的基础，而大部分互联网服务提供商首选的内部网络协议正是OSPF。
Y·德拉尔和R·麦特卡尔菲：《广播数据包的反向路径转发》
Y. Dalal and R. Metcalfe, "Reverse path forwarding of broadcast packets", Communications of the ACM, v.21, n.12, Dec 1978, pp.1040~1048
也许是雅克比（Jacobi）说过的“你应该总是把一个问题反过来看”。德拉尔和麦特卡尔菲（Metcalfe）把多播传送反过来就成了接收多播。文中优雅地把多播路由树的计算简化成以多播路由源为根的最短路径路由计算。多年过后，我仍然非常喜欢这篇文章的简洁。另外，这篇论文还影响到德灵（Deering）【1】，他在其文中提出了有关以剪枝实现距离矢量组播路由选择协议（DVMRP，Distance Vector Multicast Routing Protocol）和IP多播等一系列想法。而对于IP组播，我敢说，它正卷土重来。
传输协议
R·汤姆林森：《序列号选择》
R. Tomlinson, "Selecting Sequence Numbers", Proceedings of the ACM SIGCOMM/ SIGOPS Interprocess Communications Workshop, Santa Monica, CA, March 24, 1975
关于TCP（Transmission Control Protocol）的论文绝对是经典，瑟夫（Cerf）和卡恩（Kahn）获得图灵奖显然当之无愧。他们的“3次握手”是一个绝妙而经得起时间考验的想法。如果客户端此前发送过一个序号，为防止延迟重复包，最简单的办法是让服务器记住所有发送过来的序号，但这样会极大地占用服务器内存。汤姆林森设计的一个杰出的方法（用在TCP里）是让服务器发送一个近期从未使用过的序号，并只相信能回送这个序号的客户端。这种方式很像“查问——响应”序列，不过它只用于避免重复而不是防御攻击。虽然最初的想法有些瑕疵，约根·德拉尔做了进一步的完善，但是这篇论文依旧是网络方面一个令人难忘的创意的起源。这个设计的使用次数已经无法计量，因为每次用户启动TCP连接时都要用到它。
理查德 W·沃森 ：《在可靠传输协议连接管理中的基于计时器的机制》
Richard W. Watson, "Timer-Based Mechanisms in Reliable Transport Protocol Connection Management", Computer Networks 5, 1981, pp. 47~56
与建立连接的TCP方法(用连接延迟来减少存储过去序列号的开销)相比，沃森的论文深入研究了3次握手协议的替代方案。我坚持认为学生需要研究各种经典解决方案的替代机制，例如3次握手。除此以外，基于计时的机制也影响了许多的传输层协议，如通用消息事务协议（VMTP，Versatile Message Transaction Protocol）和大量的远程过程调用（ RPC，Remote Procedure Call）协议。
网络抽象
A·贝瑞尔和B·纳尔逊：《远程程序调用的实现》
A. Birrell and B. Nelson, "Implementing Remote Procedure Calls", ACM Transactions on Computer Systems, vol. 2, No, 1, October 1984, p. 39~58
这篇论文至少在两个以上CCR(Computer Communication Review)列表中被提及。我认为这是一篇必读论文。然而，我喜欢这篇论文的原因却也许有别于他人。我喜欢它的最重要原因是因为它提出用另一种应用程序编程接口（API，Application Programming Interface）替代TCP套接字队列接口。从更基础的角度看，它提出了在主机内部（如共享内存）扩展进程间通信（IPC，Inter-Process Communication）机制，采用类似于主机间（如分布式共享内存）机制的一套想法。除提出这种新颖的抽象外，还有一些新问题必须解决（例如，主机内程序调用不需要涉及部分失效的问题）。如果要人们使用它，实现还必须进一步提高效率。作为另一细节，还应该指出这篇论文中提出的由远程程序调用消息携带中断处理句柄地址的想法，启发了主动消息【3】的思想。
N·克隆伯格、H·列维和W·斯特雷科：《远程程序调用的实现》
N. Kronenberg, H. Levy and W. Strecker, "VAX clusters: A closely-coupled distributed system," ACM Transactions on Computer Systems, vol. 4, no. 2, May 1986, pp.130~146.
据说VAX体系结构组的斯特雷科曾被要求学习网络知识，并得到了一本教科书。几个月后，他和同事们就创建了VAX机群（VAX Clusters）——这是一种通过新型局域网将一组计算机与存储设备连接的方法。他们在以太网风格的局域网上连接的方法很有趣。但其中最杰出的想法（也是只有计算机体系结构设计师才会想到的方法）是把DMA（Direct Memory Access，直接存储器访问）扩充到跨网络的RDMA(Remote Direct Memory Access，远程直接存储器访问)。另外还设计了一个非常杰出的分布式锁管理器。许多学习网络的学生可能没有意识到存储区域网（Storage Area Network ，SAN）是个10亿美元的商业市场。现在从光纤通道、Infiniband和iSCSI等中依然能找到RDMA的影子。
参考文献
【1】S. Deering and D. Cheriton,
"Multicast Routing in Datagram Internetworks and Extended LANs,"
ACM Transactions on Computer Systems, vol. 8, No. 2, May 1990, pp. 85~110
【2】J. McQuillan, I. Richer, and Eric C. Rosen,
"The New Routing Algorithm for the ARPANet" ,
IEEETransactions on Communications, 28(5), 1980, pp. 711~719
【3】T. von Eicken, D. Culler, S. Goldstein, and K. Schauser.
"Active messages: A Mechanism for integrated communication and computation",
Proceedings 19th International Symposium on Computer Architecture, 1992, pp. 256~266
评论