计算机网络，顾名思义就是多台计算机相连接而形成的网络。但是这个解释非常粗略，因为「多台」可以指3台，可以指30台，也可以指300台，还可以指300000台，量变引起质变，少量的计算机我们还可以想着可以「直连」，但数量庞大的计算机如何相连就需要好好地研究了。这也是本课程的主题，即如何设计并组织这些计算机网络。

引言

首先讲为什么需要计算机网络。计算机本质上是用来进行计算的，而计算机网络中互相连接的计算机就可以实现资源共享共同完成计算的任务，不论是个人用户还是公司用户，都需要计算机网络去满足他们丰富的计算需求。

其次我们再来讲计算机网络的不同量级，从小到大可分为: 个域网（比如蓝牙，NFC，RFID）；局域网LAN（比如WiFi和以太网）；城域网（比如有线电视网络）；广域网WAN（一般由网络服务提供商负责运营，VPN也是一种广域网）；互联网络（使用路由器连接多个网络）。

上述计算机网络的分层分类，其实还只是硬件层面的，计算机网络到底是如何连接的还是没有明确。这需要从计算机网络的软件层面来谈，也就是常说的「七层协议」（自底向上分别为：物理层、数据链路层、网络层、传输层、会话层、表示层、应用层）。这个概念非常重要，因为它把网络抽象化成了一层一层的网络协议，每一层对上一层来说都是黑盒状态(也有说法是「透明的」，但我觉得它有歧义)。于是整个网络的设计问题就变成了对于每一层的设计，设计需要考虑的要素包括但不限于: 可靠性、资源分配、规模增长等等。当然原始的七层协议（也称OSI参考模型）非常教条，很少真正使用。现在用得比较多的是TCP/IP参考模性，总共四层，合并了会话层和表示层到应用层中去，并且将数据链路层和物理层并称为链路层。

最后，这一章讲了著名的网络，比如：因特网（这几乎是提起网络就必提及的东西）；802.11无线LAN（也就是常说的WiFi）；移动电话网络（移动电话网络体系结构与因特网截然不同，「蜂窝网络」、「基站」、「频分/时分/码分复用」等词都是移动电话网络里的词）；还有一些新兴网络如物联网（这现在是个很热门的研究方向）。

数据链路层

数据链路层主要关心怎么在相邻（可以是有线意义上的连接。也可以是无线但在可以通信范围内的）机器之间实现可靠有效的完整信息块（称为帧）通信。注意通信的最小单位不再是比特流而是一帧一帧的。直觉上，这好像很简单。形象地认为只要发送方把数据处理成一帧一帧的，放到信道上，接受方一帧一帧地收到后把它们还原成原始数据。我们大体上可以这么理解，但是细节的内容也需要知道。

如何把原始数据处理成帧? 我们只需要定义什么是帧即可。（计算机网络这个语境里和实际关联太大了，既定的定义不可能像数学那样天马行空自洽即可，而是需要考虑实际需求的，因此本课中说的定义实际上就是在设计网络时人们要求这样东西满足的性质）。那显而易见地，做为本层通信的最小单位，我们应该要求任何时候都能从信道中的比特流中区分出每一帧，这就要求我们在原始的比特流信息基础上，加入填充来隔断不同帧。

考虑到信道多多少少都是有差错的，因此我们需要差错控制。主要分两种：一种是检错（但不纠错，一般伴随着重传。比如各种「校验」，奇偶校验、校验和、CRC等)。另一种是纠错（也就是检错后知道怎么纠正，比如海明码）。检错常用于高质量信道，而纠错常用于低质量信道。因为低质量信道几乎接受方收到的都是有差错的，如果不带纠错的话，就只能重传，效率会极低。

上面的差错控制只在帧还能到得了对岸才起作用。如果有些帧压根直接在信道中丢失了呢？这需要进一步制定协议来处理。一个自然的想法是: 接受方每收到一帧就跟发送方确认一下，这样发送方就知道自己刚刚发的那帧已经被收到了，于是就可以继续下一帧的发送。（这个就是ARQ协议。它同时还解决了流量控制的问题）。然后考虑到通信效率问题，又把信道从「单工」升级到「全双工」（相应引入「稍待确认」），还引入了一个很重要的「滑动窗口协议」：让信道上同时有多个帧在传输而且还保证最终传输结果的有序性。

滑动窗口协议这个概念非常重要重要了，根据发送者的重传策略，它还可以分成三类：1位滑动窗口；回退N；选择重传。

数据链路层最接近生活的例子大概就是：家庭上网。现在主流的有两种方案：一种是重复利用原来的电话线，用电话线上网(拨号宽带)；另一种是光纤入户。（这里我们暂时不管wifi。因为wifi的「网」本质上也是通过这两种方式来的）。先来说第一种，用电话线上网其实是个有年代的词，以前上网和打电话还不能同时进行。但现在改进后，引入了ADSL模式，将高频与低频分离，这样上网电话两不耽误。（这里注意ADSL是指这种模式，真正做这事的是我们常称为「猫 Modem，调制解调」的东西，而在服务器则相应地使用DSLAM)。第二种光纤入户则不需要考虑原来的电话线的麻烦事儿了（我觉得这也是计网有些协议很繁杂的原因，因为通信是个大范围的考虑，要更换或者说升级要考虑成本，于是就有很多魔改的协议好利用原来已有的设备）。不过由于光纤里传的是光信号，因此还是要在家里装个「光猫」才能使用它，实现光信号和其他协议中的数据的转换。

还有很有意思的「客厅电视战场」：广电的有线电视、三大运营商的IPTV盒子（虽然也是「上网」看电视，但是运营商专门建了IP电视网）、互联网公司的网络电视盒子（跟用电脑看电视的原理差不多）。

介质访问控制子层

做为数据链路层的子层，它的名字有点绕口，不过它的英文名比中文名更为人熟知: Medium Access Control（MAC）。当然这不是因为口红或者电脑，而是如果曾经设置过自己家的wifi或者点开过手机或电脑上的wifi详细信息查看过，那么一定会看到有一个叫做MAC地址的 XX-XX-XX-XX-XX-XX (12个16进制数) 形式。

这个子层之所以被单列出来，一方面是因为要懂一点前面的数据链路层的知识才能理解这些内容，另一方面就是因为它太重要了！前面一章侧重在讲点到点的链路，而这一章则是侧重讲广播信道（严谨一点的术语叫: 多路访问信道），也就是同一时间有许多计算机（用户）都连接在这个信道，而且都有发送和接受帧的可能（倾向），但这个信道又只能同时传输一帧消息。因此，如何选定广播信道的下一个使用者就是MAC子层的主要任务。

最自然的想法是：如果有N个用户连接在信道上，那么就制定协议把信道资源（比如频分）均分成N等分，每个用户对信道的使用就互不干扰了，这种称为「静态信道分配」。这个想法有一个非常大的缺点：并不是所有用户都持续地要使用信道（可以想象家庭里连上wifi的智能设备，并不是时时刻刻都全部在使用的；即使是都在使用，每个用户也不是每个时间点都保持同一使用强度）。总的来说就是现在越来越普遍的情况是每个用户产生的流量独立且具有「突发性」的特点，因此静态分配并不适用，它会浪费非常多的信道资源。

于是就产生了「动态信道分配」，也叫做「多路访问(Multi-Access)协议」。最初的多路访问协议很简单，它起源于上世纪70年代的夏威夷，名为ALOHA （夏威夷语问候语：你好），这个协议只有两点：当用户有数据时就传输；当用户发现自己的数据传输失败（也就是和别的用户传输的数据产生了冲突），就随机等待一段时间后重新传输。但是由于简单，ALOHA协议（包括它的改进版分槽ALOHA）的效率并不高，信道利用率分别为18.4%和36.9%，原因也很容易想到，因为用户没有任何顾虑地就发送数据了，导致冲突发生的概率很高。

改进的协议引入了「载波侦听(carrier sense)」机制，也就是发送数据前先检查是否有其他用户在使用信道。如果有，那么根据不同的处理办法CSMA又可以分为以下三种：1-坚持CSMA：如果检测到有其他用户在使用信道，那么持续监听，知道信道空闲后，就立即发送自己的数据帧。p-坚持CSMA：与1-坚持不同的是，知道信道空闲后，以概率p发送自己的数据帧。非坚持CSMA：在检测到其他用户在使用信道后，停止监听，随即等待一段时间，再重复这整个过程，直到它监听时信道恰好是空闲的。

进一步改进协议，还可以再引入「冲突检测」机制，在发送前除了检查是否有其他用户在使用信道，还要检查自己发送的数据帧是否遇到冲突，全称叫做「带冲突检测和载波侦听的多路访问机制 (CSMA/CD)」。冲突检测的方式是：在开始发信号的一段时间（具体来说是2倍的最远信号传播时间）内持续监测信道上刚刚已经发送的一部分数据帧是否产生了冲突。还有一些协议干脆设置成让冲突不可能出现：比如位图协议、令牌传递、二进制倒计数等（我都没看）。

MAC子层有两个著名（现在还在广泛使用的）例子：无线局域网(WLAN)、（经典以及交换）以太网。

无线局域网：虽然说是MAC例子，但它并不是上述协议无脑使用，它也根据自身的特点，又引入了很多新的技术（协议）。比如说，我们之前的假设中默认了「载波侦听」和「冲突检测」是可以实现的，然而在无线局域网的情景中：存在着「隐藏终端问题($A \to B \gets C$)」和「暴露终端问题($A \gets B \leftrightarrow C \to D$)」，使得「载波侦听」机制不可靠；由于无线电的接收信号比发射信号弱上一百万倍，压根无法在发射信号的同时接收这么弱的信号，因此无线电几乎就是「半双工」的，于是「冲突检测」也不能使用。最早的解决无线局域网中的这些麻烦的协议是MACA（Collision Avoidance），它主要思想是发送方诱使接受方发出一个短帧CTS，以提醒接收方周围的用户保持静默（一段随机的时间）。不过不管是MACA还是RTS/CTS都很少被使用，现在802.11（无线局域网的一个标准）用的是带有物理侦听和虚拟侦听的CSMA/CA，它为不同的帧规定了不同的时间间隔（指的是该帧发送出去后发送方空闲一段时间来检查信道是否被使用）。

以太网：以太网是有线局域网，在交换机出现前，（经典）以太网用长电缆连接所有计算机，因此为了确认信道中的某个帧的源与目的地，电缆上的每台计算机都分配了一个48位地址（MAC地址!）。不过用单根电缆连接这样的操作鲁棒性不好，交换机的出现弥补了这种缺点。而且交换机内部每个端口有自己独立的冲突域，因此（交互）以太网可以做到全双工，冲突不可能发生。之后为了增大带宽，又改进了电缆的标准，从快速以太网，到千兆以太网、万兆以太网。因为性能优越、结构简单、易于维护、与广泛使用的TCP/IP的兼容性等优点，（而且因为以太网的硬件设施如集线器。交换机很难一下子被丢弃），以太网经久不衰。

网络层

网络层开始解释网络之所以为网络的原因，因为它关注的是如何将源端数据包沿着网络中的路径一路送到接收方，而数据链路层只是将帧从某段线路的一端传到另一端。同时网络层在七层模型中处于中间的过渡位置，而且可以认为它几乎只有一个主要的IP协议，因此它让整个协议栈看起来就像是一个漏斗形状。

网络层需要向它的上层传输层提供服务，服务主要有两种：一种为基于虚电路（virtual circuit）的面向连接的服务，它与电话系统很相似，一旦建立连接，后续的数据传输就非常自然顺畅了；另一种是基于数据报（datagram）的无连接服务，它与邮局系统相似，对于每一个数据报都需要考虑它如何传送。当然不管是哪一种服务，都需要进行路径的选择，这由路由算法（routing algorithm）来决定，它是网络层最主要的内容。

路由算法的设计不是随意的。网络上节点（路由器）和边（链路）众多，如何计算出一条从源端到接受方的合适路径呢？首先路由算法必须满足正确性；其次它需要满足稳定和高效性，即在规定时间内计算（收敛）出一条可以到达接受方的路径；同时我们要考虑到网络上并不仅有一个数据包在传送，而是有很多个数据包同时存在在网络中，因此路径中的路由器选择也必须谨慎，避免不同通信线路和路由器负载严重不均；最后我们还希望路由算法具有鲁棒性，能应对系统中一些拓扑结构和流量方面的变化。

最简单的路由算法应该是泛洪算法（flooding），顾名思义，它的意思是让路由器将每一个入境数据包发送到所有出境线路，这样理论上所有路由器都能接收到所有数据包，但是这样做的代价是会产生大量重复的数据包，完全不适合在稍大型网络中使用。不过泛洪算法确实有一些优点，比如它非常适用于无线广播形式，而且它的鲁棒性非常好（因为即使多条线路被毁，只要存在一条可达路径，泛洪算法都能找到）。再复杂一点的路由算法有最短路径算法，核心就是Dijkstra算法（迪杰斯特拉，这个英文名我至少听过5种版本的读法），该算法要求给定一个完整网络视图并且图中无负权值。后一个要求很好满足，因为一般计算最短路径用的衡量标准是距离、带宽、平均延迟等不可能为负的量，但是前一个要求就比较苛刻了，它无形中规定网络是静态的，因此实用性不高。

因此提出动态路由算法：距离矢量算法和链路状态算法。距离矢量算法也称分布式Bellman-Ford算法（RIP协议），每个路由器维护一张记录了当前到网络中其他所有路由器的最短路径长的路由表，并且算法执行过程中，路由器并不需要知道整个网络的拓扑结构也不学要知道自己在网路中的位置，只需要把自己的路由表发送给它的所有邻居即可。不过这个算法存在一个「无穷计算问题」，即网络中某节点宕机或被毁坏时，其他路由器需要很长一段时间后才能知道「哦这个路由器坏了」这个坏消息，因此该算法鲁棒性不好，某些情况下收敛极慢。因为距离矢量算法的这个致命缺点，1979年之后ARPANET就改用链路状态算法了，现在的大型网络应用最为广泛的路由算法都是它的变种（如OSPF）。它的核心思想退回到Dijkstra算法，也就是每个路由器了解网络的完整拓扑，不同的是它采用数据包来传递链路状态，以达到动态效果。由于要保存整个网络拓扑并且在本地运行Dijkstra算法，链路状态算法需要更多的内存和计算。虽然理论上大型网络上运行这个算法是存在问题的，但是实际场合中这个算法工作得很好，主要归功于它没有慢收敛问题。

除了路由算法外，本章还重点讲了不同网络互联的问题，这也是著名的IP协议提出的契机。因为在数据链路层的许多种（小型）网络需要相互连接构成一个较大型的网络时，就需要有一个公共层来隐藏他们之间的差异，这也可以解释为什么网络层在协议栈中看起来非常狭窄。IP协议规定了路由器来连接不同网络，也就是说在每个网络的边界，路由器会将一个网络上传递的信息（广义上的信息，因为可能有数据包也可能有虚电路还可能有其他的形式）转换成可以在另一个网络传递的信息。这种转换可能会非常复杂，因为不同网络的通信标准差异会非常大，有时候甚至是矛盾的。

由于IP协议是希望做为一个公共层来连接不同网络，那么IP协议相应地就为所有连接起来的网络中的不同主机和路由器都分配了一个全局的IP地址。可是IPv4的地址只有32位，也就是最多2^32^（约等于43亿）个不同IP地址，要知道全球人口数量远超这个数值，再加上用来中转信息的众多路由器，这么点IP地址就有点捉襟见肘。为了解决地址短缺的问题提出IPv6，它有128位地址（2^128^这个数字真的很大，它可以为地球上每平方米面积提供近10^26^地址，这甚至超过了阿伏伽德罗常数）。不过在从IPv4向IPv6迁移的漫长过程中，需要有一个短期应急方案，即网络地址转换（NAT）。它允许将网络流量分为内部与外部，只有在路由外部流量时才要求IP地址为全局唯一的，而在内部路由流量时，IP地址可以重复，这时的IP地址也称私有地址或保留地址。这也就是为什么许多家庭终端路由器的IP地址都是192.168.1.1。

IP协议是用于互联网数据传输的，其实在互联网中还有许多辅助的控制协议，比较主要的有：ICMP协议、ARP协议和DHCP协议。ICMP协议因为生存期（TTL）参数的巧妙设置，可以被用来测试互联网的连接性；ARP（地址解析协议）用来将IP地址映射到数据链路层的地址；DHCP（动态主机配置协议）用来为主机分配一个空闲的IP地址。还有一些协议如MPLS（多协议标签交换）并不严格地属于网络层，但它可以也可以完成将IP数据包在不同网络之间传输的任务。

传输层

传输层在网络层提供的服务之上，把数据传递服务从两台计算机之间扩展到了两台计算机上的进程之间。从操作系统的角度看，在传输层之上的应用层处于的是用户模式，而传输层虽然处于内核模式，但是程序员可以通过系统调用（套接字或者API）来使用其提供的服务，反观传输层之下的诸如网络层等对于程序员来说过于遥远了，毕竟这些层与管理着线缆、路由器、网关的运营商关系更为紧密。

因为网络层IP协议提供的服务质量是不可靠的，即只能保证「尽力而为」，而不能保证所有数据包都能正确及时地到达目的地。因此传输层一个很重要的任务就是考虑如何在不可靠的网络服务之上完成连接管理工作。并不是说在网络层做不到可靠的传输，而是根据著名的「端到端原则」（End-to-End Principle），网络层中的协议不可能为了去提供更多的服务保障而被设计得很复杂，这样做代价太大了，也就是常说的「可以但没必要」。因此传输时端-端就要负起保障服务的责任，比如说要差错控制、拥塞控制、流量控制等等。当然之前的层中也会有一些操作对这些服务保障有些帮助（比如无线传输时的确认重传机制），但是最终还是靠端-端来确保整个传输机制可以正常工作。

互联网有两个主要的传输协议：UDP与TCP。UDP（User Data Protocol）协议非常省事儿，它是一个不可靠的面向无连接的数据报服务。没有确认重传、没有检查数据报是否遗漏、是否乱序、也没有流量控制。因此UDP更像是直接在IP的基础上，对数据包进行包装，再加上两个端口号指示数据报的来路和去向，仅此而已。因此它非常适用于那些对实时性要求比较高的交互，如视频通话等。

TCP（Transmission Control Protocol）则提供了一个可靠的、面向连接的、端到端的字节流传输服务。之所以是「字节流」，是因为TCP提供的可靠服务使得网络层需要传输的数据包全部都按时守序地到达另一端，因此抽象来看，就是一个持续稳定的字节流。因为是面向连接的，因此使用TCP协议交互的双方，首先需要建立连接（「三次握手」：SYN，SYN/ACK，ACK），交互完成后还需要释放连接（「四次挥手」：FIN，ACK，FIN，ACK），虽然实际的协议比这里写的复杂，但是也可以看出TCP协议从连接开始就需要仔细而充分地考虑各种情况。解决完连接的问题，TCP协议还需要进行流量控制和拥塞控制。流量控制主要是防止发送者淹没接收者，使用的技术诸如停止等待、大小可变的滑动窗口等之前都有提及。拥塞控制则是为了防止发送者淹没网络。其实拥塞并不是坏事，因为这代表了网络的带宽被充分地利用了，只不过需要将拥塞程度控制在一定范围内才不至于使网络瘫痪。一个比较原始的拥塞控制方法是AIMD（Additive Increasing， Multiplicative Decreasing），主要思想就是通过调整发送方的发送窗口大小，控制网络线路恰好再满载但不丢包的状态周围来回震荡。之后的一些改进协议TCP Tahoe， TCP Reno又加入了慢启动、拥塞避免、快速重传快速恢复等技术，让传输协议更加高效健壮。