系列文章目录

什么是计算机网络？
什么是网络协议？
计算机网络的结构
数据交换之电路交换
数据交换之报文交换和分组交换
分组交换 vs 电路交换
计算机网络性能（1）——速率、带宽、延迟
计算机网络性能（2）——时延带宽积、丢包率、吞吐量/率
计算机网络体系结构概念
OSI参考模型基本概念
OSI参考模型中非端-端层（物理层、数据链路层、网络层）功能介绍
OSI参考模型中端-端层（传输层、会话层、表示层、应用层）功能介绍
TCP/IP参考模型基本概念，包括五层参考模型
网络应用的体系结构
网络应用进程通信
网络应用对传输服务的需求
Web应用之HTTP协议（涉及HTTP连接类型和HTTP消息格式）
Cookie技术
Web缓存/代理服务器技术
传输层服务概述、传输层 vs. 网络层
传输层——多路复用和多路分用
传输层——UDP简介
传输层——可靠数据传输原理之Rdt协议
传输层——可靠数据传输之流水线机制与滑动窗口协议
传输层——TCP特点与段结构
传输层——TCP的可靠数据传输
TCP连接管理（图解三次握手和四次挥手）
传输层——拥塞控制原理与解决方法
TCP的拥塞控制机制
网络层服务与核心功能
网络层服务模型——虚电路网络
网络层服务模型——数据报网络
Internet网络的网络层——IP协议之IP数据报的结构
IP分片
IP编址与有类IP地址
IP子网划分与子网掩码
CIDR与路由聚合
DHCP协议
网络地址转换(NAT)
ICMP（互联网控制报文协议）
IPv6简介
路由算法之链路状态路由算法
路由算法之距离向量路由算法
路由算法之层次路由
数据链路层概述
数据链路层——差错编码

---

---

前面介绍了数据链路层提供的差错检测或者说差错纠正服务，它们依赖于差错编码。这里介绍链路层提供的另一种服务——多路访问控制。为此，需要带大家了解多路访问控制的概念和多路访问控制(MAC)协议。

---

多路访问控制

多路访问控制主要是解决一类链路的使用问题。作为网络中的链路，大致可以分为两类：

• 点对点链路：链路只连接两个相邻的结点。比如以太网交换机与主机间的点对点链路

• 广播链路 ：特点是物理介质被共享。这种链路比较多见。比如现在广泛使用的802.11无线局域网，它的无线电频率就是被共享的

  

当大家共享物理介质进行通信的时候，必须有一个机制来协调发送数据。为此就需要一类多路访问控制(MAC)协议。

---

多路访问控制(MAC)协议介绍

在单一共享广播信道这类链路中，如果有两个或者两个以上结点同时传输时，势必会相互干扰。也就是冲突(collision)。所以在广播链路中，冲突的发生就意味着传输的一次失败。因此需要多路访问控制(MAC)协议来协调共享链路的使用。

作为多路访问控制(MAC)协议，一般有一些基本性的考虑和需求：

• 期望设计出来的MAC协议采用分布式算法决定结点如何共享信道，即决策结点何时可以传输数据
• 大家在协调的过程中，协议必须基于信道本身，通信信道共享协调信息

理想的MAC协议是什么样的？

假设给定速率为R bps的广播信道。MAC协议应该满足这些需求：

• 当只有一个结点希望传输数据时，它可以以速率 R发送
• 当有M个结点期望发送数据时，每个节点平均 发送数据的平均速率是R/M
• 完全分散控制。无需特定结点协调、无需时钟、时隙同步
• 简单不复杂

MAC协议主要分三大类：

• 信道划分(channel partitioning)MAC协议

  • 使用多路复用技术，将信道资源划分一些资源片，然后再分配下去
  • 比如：TDMA、FDMA、CDMA、WDMA等

• 随机访问(random access)MAC协议。在计算机局域网中非常多见

  • 信道不划分，允许冲突
  • 采用冲突 “恢复” 机制

• 轮转(“taking turns”)MAC协议

  • 结点轮流使用信道

---

随机访问MAC协议

在随机访问MAC协议中，当结点要发送分组时，会利用信道全部数据速率R发送分组，动态性很强，没有事先的结点间协调。因此就可能出现冲突（两个或多个结点同时传输）。所以随机访问MAC协议需要定义：

• 如何检测冲突
• 如何从冲突中恢复 (e.g., 通过延迟重传)

典型的随机访问MAC协议：

• 时隙(sloted)ALOHA
• ALOHA
• CSMA、CSMA/CD、CSMA/CA

---

时隙ALOHA协议

假定：

• 所有帧大小相同
• 时间被划分为等长的时隙 (每个时隙可以传输1个帧)
• 结点只能在时隙开始时刻 发送帧
• 结点间时钟同步
• 如果2个或2个以上结点在 同一时隙发送帧，结点即 检测到冲突

运行过程：

• 当结点有新的帧时，在下 一个时隙(slot)发送
  • 如果无冲突：该结点可以在下一个时隙继续发送新的帧
  • 如果冲突：该结点在下 一个时隙以概率p重传该帧，直至成功

下面看一下示意性的示例：

假设网络中有三个结点，共享一个广播链路。

• C表示冲突，E表示空闲，S表示发送成功

• 优点：

  • 单个结点活动时，可以 连续以信道全部速率传输数据，也就是占用信道的全部资源
  • 高度分散化：只需同步时隙
  • 整个协议非常简单

• 缺点:

  • 很容易发生冲突，浪费时隙
  • 结点也许能以远小于分组传输时间检测到冲突
  • 必须要求所有结点时钟同步

效率(efficiency)：长期运行时，成功发送帧的时隙所占 比例 (很多结点，有很多帧待发送)。

• 假设: N个结点有很多帧 待传输，每个结点在每个 时隙均以概率p发送数据。
• 对于给定的一个结点，在 一个时隙将帧发送成功的 概率= p(1-p)N-1；对于任意结点成功发送帧 的概率= Np(1-p)N-1
• 最大效率: 求得使Np(1- p)N-1最大的p* ，对于很多结点，求 Np* (1-p*)N-1当N趋近无穷时的极限，可得 最大效率= 1/e = 0.37。
• 也就是说，时隙ALOHA协议中，信道被成功利用的时间仅占37%！

显然时隙ALOHA协议的效率并不能让人满意。

---

ALOHA协议

• 非时隙(纯)Aloha：更加简单，因为无需进行时钟同步

• 每个结点当有新的帧生成时，就会立即发送

• 因此冲突的可能性增大了

  • 在t0时刻发送帧，会与在[t0 -1, t0+1]期间其他结点发送的帧冲突

    

---

CSMA协议

载波监听多路访问协议 CSMA (carrier sense multiple access)最大的改进地方在于：

• 发送帧之前，监听信道 (载波)。如果信道空闲，就发送完整帧；如果信道忙则推迟发送。

但是冲突仍然可能发生。另外，信号传播延迟的存在也会导致冲突的发生。这时如果继续发送数据，就会浪费信道资源。

如果发送数据的同时就能判断有没有冲突就很好了，在发现冲突后就终止后面数据的传输，能够很好的提高信道的效率。这时，CSMA/CD协议就出现了。

---

CSMA/CD协议

CD（Collision Detection）强调在发送数据帧的同时可以检测冲突。换句话说，就是短时间内可以检测到冲突。在冲突后中止传输，就能减少信道浪费。

对于这个协议的冲突检测机制：

• 有线局域网易于实现：通过测量信号强度，比较发射信号与接收信号
• 无线局域网很难实现：信号衰减很快。接收信号强度淹没在本地发射信号强度下

把这样的特性概括为：“边发边听，不发不听”

例题：

CSMA/CD协议的效率比ALOHA更高。