# F.13 历史回顾与参考文献 本附录认为，应用领域差异很大的互连网络，从处理器芯片内的片上网络，到连接全球计算机的广域网，都有许多共同关注点。因此，互连概念按统一框架介绍，不以应用划界。但它们的历史截然不同，对相似问题采用不同解决方案，就是证明。不同领域研究群体之间缺少充分交流，无疑也促成了实现方法的多样性。下面列举相关读物。涵盖 WAN 和 LAN 的优秀通论包括 Davie、Peterson 和 Clark［1999］以及 Kurose 和 Ross［2001］；面向多处理器与集群 SAN 的优秀教材有 Duato、Yalamanchili 和 Ni［2003］及 Dally 和 Towles［2004］。Pinkston［2004］专门论述互连死锁处理的章节很有价值。Jantsch 和 Tenhunen［2003］编辑的多核处理器与 SoC 片上网络著作，也值得阅读。 ## 广域网 广域网是最早的数据互连网络。Internet 的前身 ARPANET 于 1969 年连接美国各地获得政府高级研究计划局 ARPA 资助的计算机科学系。最初设想是底层提供可靠通信；实际底层故障经验，促成了能容忍失败的 TCP/IP，成为今天互联网的基础。Vint Cerf 与 Robert Kahn 因在 20 世纪 70 年代中期开发 TCP/IP，获得 ACM 软件奖。Kahn［1972］是介绍 ARPANET 思想的早期文献；Stevens［1994–1996］的经典著作适合进一步学习 TCP/IP。 1975 年 ARPANET 大约有 100 个网络，1983 年只有 200 个。1995 年 Internet 已覆盖全球 50,000 个网络，其中约一半在美国。此后很难再统计网络数量，但 IP 主机从 1995 到 2000 年增长 15 倍，2000 年底达到一亿台，此后增长更快。多数服务商动态分配 IP，许多 LAN 使用私有地址，多数网络又支持无线连接，使主机总数几乎无法计算。2005 年 7 月，Internet Systems Consortium（www.isc.org）估计互联网主机超过 3.5 亿台，预计年增长约 25%。虽然 ARPANET、NSFNET 等政府网络奠定了基础，商业部门后来接手，使互联网蓬勃发展。但重大创新仍可能更多来自政府资助研究，而非商业部门；美国国家科学基金会 GENI，即 Global Environment for Network Innovation，计划就是一例。 互联网最令人振奋的应用是万维网。1989 年，CERN 程序员 Tim Berners-Lee 为信息访问开发它。1992 年，伊利诺伊大学的年轻程序员 Marc Andreessen 开发图形界面 Mosaic，大受欢迎，后来成为 Netscape 创始人之一，推动商用浏览器普及。1995 年 5 月本书第二版出版时，网页超过 30,000 个，每两个月翻倍；写第三版时已超过 13 亿个。2005 年 12 月，Web 服务器接近 7500 万台，当年增长 30%。 ATM 曾试图成为统一、终极的通信标准，既支持数据，也支持数字语音即电话。从技术上，它结合了分组交换与电路交换的优点，还很好地支持服务质量（QoS）。Alles［1995］提供了良好综述。1995 年，人们毫不怀疑 ATM 代表该领域未来；十年后，高昂设备与培训成本几乎击垮 ATM，人们回归简单的 TCP/IP。LAN 领域输给以太网家族也是重大打击：ATM 传输前要建立连接，而以太网分组交换延迟明显更低。后来虽引入 ATM 无连接服务器补救，却昂贵且构成 LAN 的集中瓶颈。 WAN 如今依赖光纤。光纤技术进展如此迅速，带宽常未被充分利用。主要原因是**波分复用**（WDM）商业化，一根光纤能在不同波长同时传多条数据流，一代即三至五年内带宽提高三个数量级；Senior［1993］是光纤通信方面的良好教材。但 IP 路由器仍可能成为瓶颈。链路速率 10–40 Gbit/s、大型核心路由器有数千端口时，必须在几十纳秒内处理分组。最费时的是路由，IP 地址的定义与分配方式，使每个分组通常都要在树结构中复杂搜索。网络处理器因此成为实现路由和分组过滤的高性价比方案，通常类似 RISC，具有大量硬件线程，并使用 local store 而非 缓存。 ## 局域网 ARPA 在 WAN 上的成功，直接促成最流行的 LAN。Xerox Palo Alto Research Center 的许多研究者，在大学时就受 ARPA 资助，了解网络价值。1974 年，该群体创造了今日桌面计算机先驱 Alto［Thacker 等 1982］和今天的 LAN 以太网［Metcalfe 和 Boggs 1976］。David Boggs、Butler Lampson、Ed McCreight、Bob Sprowl 和 Chuck Thacker 后来都成为计算机科学与工程名家，获得大量奖项。 最初以太网为 3 Mbit/s，对当时计算机仿佛是无限通信带宽，依靠有线电视行业的互连技术。专门微码使 Alto 经以太网的往返延迟达到 50 μs，至今仍不算差。Boggs 的业余无线电经验，促成无中央仲裁器的设计：使用前先侦听，冲突后改变退避时间。 DEC、Intel 与 Xerox 宣布 10 Mbit/s 以太网标准，是商业成功的关键。这一宣布绕过了漫长的 IEEE 标准化过程，IEEE 最终仍发布了 802.3 以太网标准。 数种试图替代以太网的方案都失败了。FDDI 委员会耗时过久才达成标准，接口昂贵，而且在交换机已开始便宜时仍用共享介质。ATM 则一方面 LAN 版标准化太慢，另一方面如前所述，无连接服务器延迟高、表现差，也错失机会。InfiniBand 因下述原因也受挫。以太网因此继续绝对主导 LAN，也凭高带宽低成本，在高性能计算市场与 SAN 有力竞争。其在高端系统中的主要缺点，是延迟相对高，多数接口卡不支持所需协议。 吸取以往失败经验，LAN 更新主要围绕以太网扩展，包括更低成本的非屏蔽双绞线（UTP）、交换互连、更高链路速率，以及无线等新领域。几乎所有新 PC 主板和笔记本都提供 100/1000 Mbit/s 快速／千兆以太网端口，多数笔记本还有 54 Mbit/s 无线以太网。将家电、机顶盒、台式机、笔记本连接到共享互联网出口的家庭有线或无线 LAN，也很常见。Spurgeon［2006］提供了优秀的在线以太网技术及历史综述。 ## 系统区域网络 Clos［1953］为电话交换局提出了最早一批无阻塞多级互连之一。后来，SAN 的许多早期发明来自大规模并行处理器（MPP）。早期代表 Illiac IV 是 20 世纪 70 年代初的 SIMD 阵列，64 个处理单元在当时已属“大规模”，以基于二维 torus 的拓扑互连，支持邻居通信。Cosmic Cube 则用以太网接口芯片，在六维立方体中连接 64 个处理器；非相邻节点通过中间节点存储转发，逐步送到目的地。80 年代中期 Connection Machine 规模大得多，包含 64K 个 1 位处理单元，也用超立方体及存储转发。此后互连网络显著进步。 20 世纪 70 至 90 年代，大量研究首先优化拓扑，后来转向路由、交换、仲裁与流控。最初主要追求性能，少顾实现限制和贯穿各层的问题。许多奇特拓扑虽有有趣性质，却使路由复杂。超立方体从中脱颖而出，80 年代十分流行，但 90 年代以后几乎从 MPP 消失。Dally［1990］的性能模型促成这一变化：若实现受导线数限制，低维拓扑在相同导线预算下能用更宽链路，性能优于高维。许多设计者跟随这一趋势，假定设计受导线限制，尽管多数实现当时及现在实际上受引脚限制。90 年代后采用低维拓扑的超级计算机包括 Intel Paragon、Cray T3D、Cray T3E、HP AlphaServer、Intel ASCI Red、IBM Blue Gene/L。 另一些设计者则选择双向 MIN，令交换机数少于节点数。最流行的是 Leiserson［1985］最初提出的胖树，首次用于 Connection Machine CM-5，后来用于 IBM ASCI White 和 ASC Purple。若干基于 Transputer 的欧洲并行计算机也采用这种间接拓扑，Quadrics 继承了其中一些特征。Myrinet 也不断演进，Myrinet 2000 将胖树作为主要拓扑。实际上，当时多数SAN，包括 Myrinet、InfiniBand、Quadrics，以及计划中的 PCI Express Advanced Switching，都基于胖树。 拓扑虽然最显眼，其他功能也显著影响性能。Holt［1972］的奠基工作引起人们对计算机系统死锁性质的关注。Merlin 和 Schweitzer［1980］、Gunther［1981］提出早期存储转发无死锁技术。Kermani 和 Kleinrock［1979］首先提出虚拟 cut-through 流水交换，Dally 和 Seitz［1986］以虫孔加以改进，显著降低轻负载延迟及拓扑对消息延迟的影响。虫孔最初优于虚拟 cut-through，主要因为流控粒度小于分组，高带宽链路不再那么受交换机可用存储带宽限制。现在通常更偏好虚拟 cut-through，因为其 HOL 阻塞影响较小、吞吐量更高，而集成技术已允许每链路实现许多分组缓冲。 Tamir 和 Frazier［1992］以动态分配多队列概念，为 VOQ 奠定基础。同一时期 Dally［1992］提出虚拟通道，这对更高效的无死锁路由，以及减少拥塞、提高吞吐量的流控技术至关重要。Duato［1993］的新理论同样重要：只需一个“逃逸”虚拟通道，就能在避免死锁的同时实现完全自适应路由；此前，所需通道数随维数指数增长。Pinkston 和 Warnakulasuriya［1997］进一步表明，死锁实际可能极少发生，为恢复型路由提供支持。Scott 和 Goodman［1994］是最早分析流水化通道价值的研究者之一，使链路带宽不依赖飞行时间。这些创新广泛用于历代高性能互连。例如 IBM Blue Gene/L 使用虚拟 cut-through、每链路四虚拟通道、一个逃逸通道的完全自适应路由，以及流水化链路。 MPP 只占信息技术市场很小且仍缩小的一部分，逐渐让位于刀片服务器和集群。美国 ASC（Advanced Simulation and Computing）计划，原称 ASCI（Accelerated Strategic Computing Initiative），推动设计了一系列性能越来越强、造价 5000 万至 1 亿美元的独一无二 MPP。后来许多机器本质上是更低成本的 SMP 集群；Pfister［1998］与 Sterling［2001］给出两种集群视角。2005 年 TOP500 中近 75% 已是集群。不过，每一代 MPP 乃至集群，都因规模及其他扩展因素产生新问题，推动互连研究。例如，最简单的源路由难以扩展到大系统；胖树随着网络增大需要更长链路，这促使 Blue Gene/L 选择可用有界长度链路实现的三维 torus 与分布式路由。 ## 存储区域网络 系统区域网络最初面向单机房或单楼层，距离几十至几百米，用于 MPP 和集群。后来 SAN 也被用作**存储区域网络**的缩写，即用网络技术连接存储设备与计算服务器。如今许多人说 SAN，指的就是存储网络。2006 年最广泛的例子是 Fibre Channel（FC），有仲裁环 FC-AL、交换式 FC-SW 等多种形式。不仅磁盘阵列通过 FC 连服务器，还有磁盘直接用 FC 链路接交换机，以享受交换网络更高带宽及互连能力。 2000 年 10 月，InfiniBand Trade Association 公布 1.0 规范［InfiniBand Trade Association 2001］，由 Intel、HP、IBM、Sun 等推动，面向高性能计算，以点到点链路、交换机和自己的协议取代 PCI。其特征同时适合连接集群的系统区域网络，以及连接阵列和服务器的存储区域网络，因而也面临两面竞争。存储领域主要对手是迅速改进的以太网。IETF 提出 **iSCSI**，在 IP 网络传送 SCSI 命令［Satran 等 2001］。由于大量生产的以太网交换机和接口卡成本更低，千兆以太网主导中低端市场。InfiniBand 推出缓慢、份额小，还延迟了原生支持它的芯片组开发；NIC 仍须插入 PCI 或 PCI-X 总线，未兑现取代 PCI 的承诺。 最终取代 PCI 的是另一个 I/O 标准 **PCI Express**。与 InfiniBand 类似，它也是交换网络，但使用点到点串行链路。它保留 PCI 软件兼容性，大幅简化迁移；又受益于大规模生产，用于桌面机连接一块或多块高端显卡，深受玩家欢迎。如今每块 PC 主板都提供一个或多个 x16 PCI Express 接口。它绝对主导 I/O接口，但当时标准并不支持处理器间通信。 **Advanced Switching Interconnect（ASI）** 可能成为 PCI Express 的补充。它兼容 PCI Express，可直接连接当时主板，同时支持处理器间通信与 I/O。支持者相信它终会在数据中心以统一网络取代 SAN 和 LAN，但讽刺的是，人们也曾这样评价 InfiniBand。详细讨论见 Pinkston 等［2003］。此外，新的磁盘接口 **Serial Advanced Technology Attachment（SATA）**，用串行信号取代并行 IDE，提高带宽。市场大多数磁盘采用它，但 Fibre Channel 仍很活跃；事实上，InfiniBand 在 SAN 的许多承诺，是 FC 先实现的，扩大了后者市场份额。 有人认为，以太网、PCI Express、SATA 分别占据 LAN、I/O 接口、磁盘接口的优势；其他存储网络竞争者的命运还取决于多种因素。计算机体系结构的妙处，是这种问题不会永远停留在重复论点、毫无定论的学术争论。竞争在市场上展开，资金雄厚而富有才华的团队全力塑造未来。技术不断变化，也会奖励敏锐或幸运的人；技术与贯彻执行的最佳组合，常决定商业成功。谁胜谁负，至少下一轮如何，时间会揭晓。 ## 片上网络 与其他领域相比，OCN 还处于起步阶段。直到 20 世纪 90 年代末，连接片内 缓存、寄存器堆、ALU 等功能单元，通常仍用追求低延迟的专用链路，或追求简单的共享总线。后来单芯片互连设备数增加，片内长连线的长度与延迟增加、芯片功耗提高，必须更有组织地共享片上带宽，遂产生 network-on-chip 概念。Agarwal［Waingold 等 1997］与 Dally［Dally 1999；Dally 和 Towles 2001］最早认识到这一点。他们认为，路由分组的 OCN 可让许多通信流高效共享日益丰富的导线资源，并通过模块化缓解 Ho、Mai 和 Horowitz［2001］指出的横跨芯片的片内连线延迟问题，还能改善故障隔离与容错。Taylor 等［2005］随后描述设计挑战，并提出以五元组刻画 OCN 延迟的模型。Bertozzi 等［2005］提出包含完整综合流程的设计方法。此后大量研发投入，使 OCN 成为微体系结构热点。 千禧年以来，带 OCN 的多核与 tile 设计日益普及。Pinkston 和 Shin［2005］综述了早期系统。多数设计利用交换式 OCN 简化布线的优点：核或 tile 之间的路径能在设计早期精确定义和优化，改善功耗与性能。核或 tile 四边通常有数万条导线作为“引脚”，因此可用导线资源换取网络性能，采用很宽的通道并行发送数据，而不是在固定窄通道上串行化；宽度还可能按功率管理需求增减。 环、mesh 与交叉开关容易用平面芯片工艺实现，也容易定义路由，所以是早期交换式 OCN 的常见选择。未来一颗芯片可能通过三维集成连接几十至几百个异构核或 tile，这种趋势是否持续，值得关注。处理器微体系结构已因应用需求和工艺进步而大幅演变，我们也期待片上网络出现同样重大的体系结构改进。