这是我在Coursera上的学习笔记。

课程名称为《Computer Networks》，出自University of Washington。

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

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

• 链路层概要

  • 话题

    • 重发

    • multiple access 多址

    • 交换

• 重发

  • 话题

    • 两种处理错误的办法：一种方法是检測帧中的错误，假设有错误就将帧又一次发送，还有一种方法是矫正错误（上一章已经介绍了）

  • 可靠性

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

    • 可靠性传输应该在全部的协议层上。仅仅只是不同的协议层层贡献不同

  • ARQ自己主动反复请求

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

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

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

  • ARQ的问题

    • 基本问题：超时应该设为多久？怎样避免发送反复的帧？

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

  • 超时

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

    • 局域网的超时非常easy。互联网的超时就比較复杂了。由于不同的环境所须要的超时时间是不一样的。

  • 帧反复

    • 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的内部

    • 全部的线都连在一起。多台计算机使用同一条线路

  • 交换机内部

    • 交换机内部有一个矩阵，多个port能够同一时候通信

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

    • 假设缓冲区放不下。就会发生丢帧。

      这叫congestion堵塞，兴许章节会具体说明

  • 交换机的长处

    • 是HUB的替代品

    • 有更好的性能

  • 交换机转发

    • 交换机须要找到正确的目标port

  • 向后学习

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

    • 在转发的时候，假设转发表中有相应的信息。就转发给相应的port。

      假设表中没有，就转发给全部的port

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

    • 能够自己想象一下两个交换机连接在一起的情况。规则跟单个交换机是一样的。

      仅仅是一个port可能会相应多个地址

• LAN生长树

  • 话题

    • 怎样连接多个路由器，而且让他们可以正常工作

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

  • 问题-转发循环

    • 可能会有循环的连接

    • 可能会有多余的连接

    • 假设有循环连接就会发生循环转发

  • 生长树解决方式

    • 不会产生循环

  • 生长树算法

    • 规则：

      • 全部的路由器使用相同的算法

      • 该算法不须要输入參数

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

      • 总能找到最佳结果

    • 健壮性

      • 不论什么拓扑结构、零配置

      • 能自己主动适应线路故障

  • Radia Perlman

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

    • 现在在研究网络安全

  • 算法步骤

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

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

    • 关闭不在生长树上的port

  • 算法细节

    • 每一个路由器最初都觉得自己的根节点

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

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

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