这是我在Coursera上的学习笔记。课程名称为《Computer Networks》，出自University of Washington。

由于计算机网络才诞生不久，目前正在以高速在发展，所以有些旧的教材可能都已经跟不上时代了。这门课程在2013年左右录制，知识相对还是比较新的。覆盖了计算机网络中的各个协议层，从物理层到应用层都讲得非常仔细。学完这门课程之后对计算机网络会有比较深刻的了解。

本章详细讲解了链路层的具体情况，包括重发技术、多址技术和交换技术。

• 链路层概要

  • 话题

    • 重发

    • multiple access 多址

    • 交换

• 重发

  • 话题

    • 两种处理错误的办法：一种方法是检测帧中的错误，如果有错误就将帧重新发送，另一种方法是矫正错误（上一章已经介绍了）

  • 可靠性

    • 可靠的传输应该放在哪个协议层呢？

    • 可靠性传输应该在所有的协议层上。只不过不同的协议层层贡献不同

  • ARQ自动重复请求

    • 这是增加可靠性的一种方法。WiFi和TCP必须使用

    • 规则：接受方收到消息后发送ACK标志，发送方不停的重新发送数据，直到收到了ACK

    • 通常情况下，发送方给对方发送了数据，接受方返回ACK标志。出错的情况下，发送方发送了一条消息，对方没有收到，发送方再发送一次数据，对方返回ACK标志。这样以后消息才算发送成功

  • ARQ的问题

    • 基本问题：超时应该设为多久？如何避免发送重复的帧？

    • 需要不错的性能和100%正确性

  • 超时

    • 时间不能太长也不能太短

    • 局域网的超时很简单，互联网的超时就比较复杂了。因为不同的环境所需要的超时时间是不一样的。

  • 帧重复

    • ACK丢失会造成帧的重复

    • 超时重发之后刚好收到了ACK，也会造成重复

  • 序列号

    • 为了防止帧重复，引入了帧序列

    • 序列号原本只需要1个比特就行了

    • 在帧和ACK中都加入序列，这样能防止帧的重复

  • stop-and-wait局限

    • 这样一次只允许发送一帧

  • 滑动窗口

    • 是stop-and-wait的推广形式，能够一次发送多帧

• multiplexing多址

  • 话题

    • multiplexing就是让多个用户共享网络资源

    • 最常见的场景就是多个用户使用同一条网络线路

  • TDM时分多址

    • 每个用户分配一个时间片

  • FDM频分多址

    • 每个人分配一个不同的频率

  • TDM和FDM的比较

    • TDM有时候不能发送数据，但可以达到高速

    • FDM一直都可以发送数据，但总是处于低速状态

  • TDM FDM的用途

    • 电视 收音机 FDM

    • GSM是FDM里加上TDM

  • 网络上的multiplexing

    • 网络流量是爆发性的，和电视不一样，电视的信号流量是很稳定的

    • 不同的时间负载是很不一样的

    • 由于网络的爆发性，很多时候宽带都是浪费的

  • Multiple Access

    • 类型：随机，非竞争（网络节点的流量很平稳）

• Multiple Access

  • 话题

    • 多个节点如何共享一个连接，比如Wifi

    • 假设没有设置主节点，也就是一个分布式系统

    • 学习MAC协议，Multiple Access Control protocol。它是经典以太网的基础。注意，数据的传输是爆发性的。
      

  • ALOHA协议

    • 岛屿之间设立了无线网络，节点在什么时候应该发送数据

    • 简单的想法：当节点需要发送的时候就马上发送，如果有冲突，就等待一个随机的时间并重新发送

    • 这样的话，有些帧可能会丢失

    • 所以这种方法效率不是很高

  • CSMA(Carrier Sense Multiple Access)

    • 改进了ALOHA，在发送之前先监听是否有动静。这种方法适合有线，不适合无线。因为可能两个设备能收到AP信号，但是这两个设备之间无法传输信号。

    • 这种方法能避免冲突吗？为什么？

    • 由于延迟，还是有可能会发生冲突

    • 如果一次只发送一个包的话，可以减少冲突

  • CSMA/CD(with Collision Detection)

    • 可以减少冲突。在发送的时候如果检测到冲突，就立即停止发送

  • CSMA/CD复杂性

    • 假设A节点到B节点的延迟是D秒，那么节点能监听到冲突的时间是2D秒（因为有一个来回）

    • 所以需要将帧的长度延长到2D秒。让帧能够检测到冲突

    • 以太网最小帧是64字节

  • CSMA持久性

    • 如果另外的节点在发送数据，自己的节点应该怎么办

    • 想法：等待对方发送完毕，自己再发送

    • 问题是，如果有多个节点都在等待对方发送完毕，那么依然有可能产生冲突

    • 更好的办法：如果有N个节点在等待，那么设置每个节点发送的概率为1/N

  • BEB Binary Exponential Backoff

    • 第一次冲突，等待0 ~ 1帧的时间

    • 第二次冲突，等待0 ~ 3帧的时间

    • 第三次冲突，等待0 ~ 7帧的时间

    • 这种方法在实际应用中效率高

  • 传统以太网，IEEE 802.3

    • 多台计算机共用一条线路

  • 以太网帧的格式

    • 有preamble、目标地址，源地址，类型，数据，留空，CRC错误检测

    • Preamble | Destination address | Source address | Type | Data | Pad | Checksum

  • 现代以太网

    • 基于交换机，不是multiple access，但是还是称为以太网

• 无线多址

  • 话题

    • 多个无线节点如何共享同一个连接（其实就是共享Wifi信号）

    • 类似于传统以太网

  • 无线的复杂性

    • 无线比有线还要复杂

    • 节点之间信号覆盖是不一样的，不是所有的节点都能接收到另外节点的消息，所以不适合Carrier Sense （CSMA）

    • 节点无法通过监听信号来检测冲突来避免冲突

  • 不同的覆盖区域

    • 举例：A - B - C - D， A能到B,B能到C，A不能到C

  • 隐藏终端

    • 当A向B发送数据的时候，C就是隐藏的终端

    • 这种情况下，A无法监听到C的冲突

  • 显式终端

    • 当B向A发送数据，C向D发送数据时，B和C就是显式终端，能检测到冲突

    • 这种情况我们想要的是能够让两个节点之间同时发送数据来提高性能

  • 节点在发送的时候无法监听

    • 所以无线在冲突的时候需要浪费更多的时间

  • 解决方案：MACA

    • 使用短握手来代替CSMA，802.11使用了改良版的MACA

    • 规则

      • 发送方发送RTS（request-to-send，和帧长度一样）

      • 接收方回复CTS（clear-to-send，和帧长度一样）

      • 发送方听到CTS的时候再发送帧（sender transmit the frame while nodes hearing the CTS stay silent）

    • 使用了RTS/CTS依然有冲突的可能，但是很少会发生

  • MACA-隐藏终端

    • 情形：A要向B发送数据，C也要向B发送数据。

    • A先向B发送RTS，B回应CTS，A和C都收到了CTS，C没有发送RTS却收到了CTS，所以知道自己现在不能发送数据。而A可以正常发送数据

  • MACA-显式终端

    • 情形：B要向A发送数据，C要向D发送数据

    • B先向A发送了RTS，C向D发送了RTS，B和C也都收到了对方的RTS

    • A回应CTS，只有B能收到，D回应CTS，只有C能够收到

    • 这样就保证了两路无线能同时发送数据了

  • 802.11就是Wifi

  • 802.11物理层

    • 使用20/40MHz的通道，802.11b/g/n是2.4GHz，802.11a/n是5GHz

    • OFDM调制（除了legacy 802.11b）

      • 不同的频幅相位有不同的信噪

      • 速率在6～54Mbps之间。有些大于这个速度的路由器使用了多天线、多通道技术

  • 802.11链路层

    • 多址使用了CSMA/CA，可选RTS/CTS

    • 帧使用了ACK，使用 ARQ协议重发帧

    • 由于加入了AP，帧头部中使用了3个地址

    • 帧格式：Frame control | Duration | Address1(recipient) | Address2(transmitted) | Address3 | Sequence | Data | Check sequence

    • 使用CRC32进行错误检测

    • 还有更多特性：比如加密、省电控制

  • 802.11 CSMA/CA 多址

    • 发送方在帧之间等待随机的时间，来避免冲突

  • 802.11的未来

    • 很可能成为互联网的基础

    • 物理层发生革新，提升速度

    • 无缝连接做得更好

• 无竞争多址

  • 话题
    

    • 基于轮流而不是基于随机

  • 随机多址的问题

    • CSMA在低负载的时候能很好地工作，但是在高负载的时候有些浪费

  • TTMA协议 turn-take multiple access protocol，轮流多址

    • 定义了一种按顺序发送的机制。能让每个节点都有机会发送

    • 排序方式有token ring和节点地址

  • Token Ring

    • Token代表了发送权限，在节点之间轮流传递

  • 轮流的优点

    • 减少冲突，在高负载的情况下增加效率

    • 每个节点发送的机会都是一样的

  • 轮流的缺点

    • 太复杂

    • 有更多出错的可能，比如Token丢失了怎么办

• LAN交换

  • 话题

    • 如何通过交换机来实现多址

  • 交换以太网

    • 所有的计算机都连接到交换机上，所有的计算机之间都能互相通信

  • 交换机里有什么

    • 交换机是工作在链路层的，路由器工作在链路层和网络层

  • HUB的内部

    • 所有的线都连在一起，多台计算机使用同一条线路

  • 交换机内部

    • 交换机内部有一个矩阵，多个端口可以同时通信

    • 交换机需要缓冲。有时候多台计算机同时向同一个端口发送数据

    • 如果缓冲区放不下，就会发生丢帧。这叫congestion阻塞，后续章节会详细说明

  • 交换机的优点

    • 是HUB的替代品

    • 有更好的性能

  • 交换机转发

    • 交换机需要找到正确的目标端口

  • 向后学习

    • 为了得到转发表，交换机记下输入帧的地址

    • 在转发的时候，如果转发表中有对应的信息，就转发给对应的端口。如果表中没有，就转发给所有的端口

  • 多个交换机之间的向后学习

    • 可以自己想象一下两个交换机连接在一起的情况。规则跟单个交换机是一样的。只是一个端口可能会对应多个地址

• LAN生长树

  • 话题

    • 如何连接多个路由器，并且让他们能够正常工作

    • 而且路由器之间不会出现循环

  • 问题-转发循环

    • 可能会有循环的连接

    • 可能会有多余的连接

    • 如果有循环连接就会发生循环转发

  • 生长树解决方案

    • 不会产生循环

  • 生长树算法

    • 规则：

      • 所有的路由器使用同样的算法

      • 该算法不需要输入参数

      • 路由器之间能并行操作，相互发送消息

      • 总能找到最佳结果

    • 健壮性

      • 任何拓扑结构、零配置

      • 能自动适应线路故障

  • Radia Perlman

    • 发明了ARPANET的路由，交换机生长树算法，链路状态路由

    • 如今在研究网络安全

  • 算法步骤

    • 选举根节点（地址最小的交换机为根节点）

    • 使用最短的路径从根节点开始生长（如果有路径一样长的节点，就使用地址最小的节点）

    • 关闭不在生长树上的端口

  • 算法细节

    • 每个路由器最初都认为自己的根节点

    • 每个路由器隔一段时间都向邻居节点发送更新消息：地址、根节点地址、距根节点的跳数

    • 路由器转发的时候使用距离最短的端口

  • 在生长树生成的拓扑结构下不会发生循环转发