读算法简史：从美索不达米亚到人工智能时代09网络互联

1.斯普特尼克1号 1.1.Sputnik 1 1.2.1957年10月4日，苏联向地球轨道发射了世界上第一颗人造卫星 1.3.是一个包裹在直径仅60厘米的金属球体中的无线电发射器 1.3.1.4根无线电天线被固定于球体的中部 2.分组交换 2.1.在分组交换之前，通信网络依赖于专用的端到端连接 2.1.1.这种方式常见于有线电话网络 2.1.2.由于计算机通常发送的是零散的短消息，以这种方式建立专用的端到端连接会使网络资源利用率很低 2.1.3.分组交换消除了保留端到端路径的需要，因而提供了对网络链路的有效利用 2.2.在分组交换中，单个讯息被切割成若干段 2.2.1.每一段都放在一个数据包中 2.2.1.1.这些数据包在网络中是独立路由的 2.2.2.网络通过一系列中继段(hop)将数据包从源头传输到目的地 2.2.3.策略的缺点是链路可能会变得拥堵(congested) 2.2.3.1.当传输中的数据包抵达某个繁忙的传出链路时，传输就需要排队，进而导致延迟和拥堵 2.3.分组交换数据网络类似于公路网 2.3.1.由多个数据包组成的单个讯息类似于一个开往目的地的车队 2.3.2.车辆的行驶不需要提前独占整个路线，它们只需要在道路畅通时插进来 2.3.3.它们甚至可能走不同的路线到达目的地 2.3.4.每辆车都尽其所能地在网络中找到自己的路 2.4.序列号是数据包在讯息中的序数(1、2、3……) 2.4.1.目标计算机使用序列号来按照正确的顺序组装负载 2.4.2.标尾包含用于检查错误的信息和数据包结束的标记 2.5.网络中的计算机不断地在它们的连接上监测传入的数据包 2.5.1.当收到一个数据包时，计算机会处理它 2.5.2.从标头读取数据包目的地的ID 2.5.2.1.如果接收的计算机不是最终目的地，那么设备将在能抵达该目的地的最快路由链路上重新发送数据包 2.5.3.使用哪条链路是通过路由表(routing table)决定的 2.6.分组交换是分布式(distributed)算法的一个实例 2.6.1.分布式算法运行在多台、独立但相互合作的计算机上 2.6.2.每台计算机都执行自己的单独任务，这在某种程度上有助于实现整个宏大的规划 2.7.用来填充路由表的算法是分组交换系统的一个基本组成部分 2.7.1.路由(routing)算法决定如何以最佳方式填充路由表 2.7.2.路由算法决定了数据包该去往哪里 2.8.分组交换网络的好处之一是面对问题时的鲁棒性(robustness) 2.8.1.如果一个链路出现故障或者变得过度拥堵，计算机可以检测到数据包排队长度的增加，并调整其路由表，以避免卡住 2.9.分组交换的缺点是数据包的传递时间是不可预测的 2.9.1.分组交换是一种“尽力而为”的服务 2.10.1966年的小型马克1号NPL网络 2.10.1.世界上第一个分组交换网络 3.阿帕网 3.1.1962年，ARPA的信息处理技术办公室(Information Processing Tech-niques Offi ce，IPTO)成立 3.1.1.IPTO的职责是资助信息技术（也就是计算机和软件）的研究和开发 3.1.2.办公室的首任主任是J. C. R.利克里德 3.1.2.1.1963年，他提议建立一个“星际计算机网络”(Intergalactic Computer Network)，使多台计算机能够隔着很远的距离也可以进行协同运行 3.1.2.2.他在1965年出版的《未来的图书馆》(Libraries of the Future)一书中提出，纸质书应该被能接收、显示和处理信息的电子设备所取代 3.1.3.IPTO的项目经理拉里·罗伯茨(Larry Roberts)编制了一份建造计算机网络的询价书 3.1.3.1.这个新网络被称为阿帕网(ARPANET) 3.2.MIT的MAC（Multiple Access Computing，多路接入计算）项目 3.2.1.一台主计算机可以被多达30个用户同时使用 3.2.2.每个用户都有自己的专用终端(terminal)，包括一个键盘和一个屏幕 3.3.1969年10月29日，“阿波罗11号”登月的3个月后，查利·克兰(Charley Kline)在阿帕网上发送了第一条信息 3.3.1.克兰是加利福尼亚大学洛杉矶分校(University of California, Los Angeles，UCLA)伦纳德·克兰罗克(Leonard Kleinrock)团队的一名学生程序员 3.3.2.他的意图是向位于400英里外SRI的一台计算机发送“登录”(LOGIN)指令 3.4.阿帕网是最早使用分组交换(packet-switching)的网络之一 3.4.1.这项技术是由保罗·巴兰(Paul Baran)和唐纳德·戴维斯(Donald Davies)各自独立发明的 3.4.2.巴兰是一名波兰裔美国电气工程师，他在1964年为兰德公司工作时发表了这个想法 3.5.为了降低基础设施成本，每台计算机都与少数几台其他计算机相连 3.6.最初的四节点分组交换阿帕网增长缓慢但稳定，平均每月增加一个节点（即计算机站点） 3.7.最早的ARPANET路由算法通过交换路径延迟时间的信息来进行决策 3.7.1.除了路由表之外，每台计算机还要维护一个延迟时间表（delay table） 3.7.2.所有的计算机都定期地将它们的延迟时间表发送给所有的邻居计算机 3.7.3.在收到邻居计算机的延迟时间表后，计算机会加上将一个数据包发送到邻居那里所需要的时间 3.7.4.路径的延迟时间可以用到达目的地的中继段数来衡量，也可以统计沿路径排队的数据包的数量 3.8.阿帕网既不是世界上第一个计算机网络，也不是唯一的一个 3.8.1.它还是成了地球上最大的计算机网络——互联网——的鼻祖 3.9.1972年10月，在华盛顿举行的国际计算机通信大会(International Computer Communication Conference，ICCC)上，阿帕网进行了首次公开演示 3.10.1983年，阿帕网的原始通信协议NCP被TCP/IP所取代 3.10.1.迪杰斯特拉的寻路算法开始用于数据包路由 3.10.2.寻找城市间最短路线的算法现在更常被用来确定数据包穿越互联网的最快路径 3.11.阿帕网于1990年正式退役 3.11.1.在那时，它仅仅是全球互联网络集合中的一个网络 4.鲍勃·泰勒 4.1.鲍勃·泰勒在1970年创立了施乐公司帕洛阿尔托研究中心(Palo Alto Research Center，PARC)的计算机科学实验室 4.2.该中心开发了一种低成本的分组交换网络技术，用于互联单个建筑内的计算机 4.2.1.以太网(Ethernet) 4.2.2.现在是世界上最常用的有线计算机网络标准 4.3.该实验室还发明了点击式图形用户界面(graphical user interface)，这种界面后来在苹果的Mac计算机和微软的Windows操作系统中无处不在 4.4.泰勒于1983年离开PARC，后来为数字设备公司(Digital Equipment Corporation)建立了一个研究中心 4.4.1.于1996年退休，于2017年去世 5.网络互联 5.1.开放架构网络(open-architecture networking) 5.2.TCP/IP的发明人温特·瑟夫和罗伯特·卡恩 5.2.1.他们吸收了其他网络发烧友的反馈，瑟夫和卡恩的大纲像滚雪球一样，变成了详细的技术规范 5.2.2.该规范将成为传输控制协议/互联网协议(Transmission Control Protocol/Internet Protocol，TCP/IP)的第一个版本 5.2.3.瑟夫和卡恩认为TCP/IP协议能够解决不同计算机网络之间相互连接的问题 5.3.TCP/IP的第一次试验发生在1976年8月27日 5.3.1.一台计算机被安装在一辆被亲切地称为“面包车”的SRI送货卡车上 5.4.1977年11月22日的实验预示了互联网的来临 5.5.TCP/IP最明显的元素是计算机节点全球统一的命名约定 5.5.1.计算机的互联网协议地址(address)可以在网络上作为它的唯一标识 5.5.2.IP地址由用点隔开的4个数字组成 5.6.如今，TCP/IP是计算机在互联网上传输和接收讯息的协议 5.7.TCP/IP使全球范围内一个个不同的计算机网络得以相互连通 5.7.1.互联网上不存在中央控制器 5.7.2.只要计算机遵守TCP/IP协议和命名约定，它们就可以加入网络中 5.7.3.在2005年至2018年期间，互联网共有39亿用户，超过世界人口的一半 5.8.美国互联网的主干现在是美国国家科学基金会网络(National Science Foundation Network，NSFNET)