计算机网络: 数据链路层

Posted on Edited on In , Word count in article: 1.5k Reading time ≈ 5 mins.

数据链路层

提供的服务或功能

  • 成帧Framing：将数据包封装成帧
  • 介质访问控制(Media Access Control, MAC)协议：规定帧在链路上传输的规则，用于协调多个节点的帧传输
  • 可靠交付：在无线环境下，可以提供纠错能力；在有线这种不那么容易出错的环境下，可能不会提供可靠交付服务
  • 差错检测和纠正：比传输层、网络层更加复杂，且用硬件实现

差错检测和纠正

  • 奇偶校验码：
  • 循环冗余校验(Cyclic Redundancy Check, CRC)码：

多路访问问题

  • 多路访问问题在于，大多数通信链路是广播链路，即是共享信道的，任何一台设备发送的报文可以被多个节点收到，但同一时间应该只有一台设备能够占有该信道，否则就会互相干扰 多路访问控制(Multiple Access Control, MAC)协议就是用来解决多路访问问题的

  • 信道划分协议(Channel Partitioning Protocol)：将共享信道根据某种属性分为多个子信道并按需分配出去 这类协议保证绝对不会发生冲突且绝对公平地分配资源

    • 时分多路复用(Time Division Mutiplexing, TDM)：将时间平等地分给接入共享信道的主机，会极大限制主机的平均发送速率，且降低了信道的使用率 虽然主机能在其时间段内能占用全部的带宽，但其平均速率需要除以节点数 一个主机必须等到它的专有时隙才能发送数据，即使只有它需要占用信道
    • 频分多路复用(Frequency Division Mutiplexing, FDM)：将信道划分为不同的频段，仍会限制主机的平均发送速率，且降低信道的带宽使用率 主机只能占有一个频段，每个频段的带宽只有总带宽除以节点数这么多 一个主机最多只能占有一个频段的带宽而无法完全占有信道，即使只有它需要占用信道
    • 码分多址(Code Division Multiple Access, CDMA)：为每个节点分配不同的编码，使得节点可以克服上述的问题

  • 随机接入协议(Random Access Protocol)：传输节点总是完全占有信道地发送，发生碰撞时，随机地决定一个重发时延，直到发送出去为止 这类协议通常不能避免碰撞，但具有较高的信道资源利用率，且对每一个节点可能不是公平的

    • 时隙ALOHA(Slotted ALOHA)：这个协议将时间轴划分为多个时间帧，每个节点要发送数据时，在下一个时隙开始时发送，并在时隙结束前检测是否发生碰撞，若发生碰撞，则以一定的概率p决定下一个时隙是否重传 一个节点成功发送前经过的时隙数量N ∼ G(p)，即P(N=k) = (1−p)k − 1p 缺点在于，需要对所有节点保持同步

    • 非时隙ALOHA(Pure ALOHA)：与时隙ALOHA的区别在于，不用进行同步，但一个节点成功发送前经过k个时隙的概率为P(N=k) = (1−p)2(k−1)p，效率为时隙ALOHA的一半

    • 带碰撞检测的载波侦听多路访问(Carrier Sense Multiple Access with Collision Detection, CSMA/CD)：要求主机主动地避免和别的主机发生冲突，具体来说，要实现载波侦听和碰撞检测 载波侦听即，每个节点在发送帧之前先侦听信道，等待没有其它节点占用信道时，才发送 碰撞检测即，虽然每个节点都会侦听，但信号的传输是有延迟的，可能存在多个节点“同时”(一个节点发送后还未传播到另一个想要发送的节点那儿)检测到信道为空，并“同时”发送帧；碰撞检测在于，一旦检测到碰撞发生，则停止发送帧，然后以指数增长的延迟决定什么时候重发帧 效率为$\begin{align}\frac1{1+5d_{prop}/d_{trans}}\end{align}$，其中的延迟分别为传播延迟和传输延迟

    • 带碰撞避免的载波侦听多路访问(CSMA with Collision Avoidance, CSMA/CA)：无线网络是不能使用CSMA/CD的，因为发送出去的帧必须完整发出，无法检测碰撞，因此CSMA/CA采用在广播前尽量避免碰撞的策略，它不会进行冲突检测，而是发出数据后通过链路层确认来决定是否重发

      • 在发送方检测到信道为空闲时，等待一个分布式帧间间隔(Distributed Inter-frame Space, DIFS)再发送
      • 接收方收到后，会等待短帧间间隔(Short Inter-frame Space, SIFS)后回应一个确认帧
      • 如果因为冲突、或其它原因，接收方没有收到确认帧，则像CSMA一样以指数增长的延迟重发

      虽然CA比CD多了一个DIFS，但它仍可能出现问题，即两个主机互相隐藏，但都需要向中间的第三方主机发送帧，这时将发生碰撞 解决这个问题依赖于无线接入点(Access Point, AP)，它是一个仲裁机构，所有需要广播的必须向AP发送RTS(Request To Send)控制帧，表示请求发送，在没有发生冲突时，AP才会完整接收到RTS帧，并广播回应CTS(Clear To Send)控制帧，表示允许发送；发送RTS的主机接收到后可以发送数据帧，其它主机接收到CTS后则会推迟访问共享信道