计算机网络 第四章 介质访问控制子层

第四章 介质访问控制子层

要解决：各个站点如何在不起冲突的情况下把通信完成

信道分配问题

M/M/1系统：多用户在同一个线路上发数据

• 第一个M：有多个数据包，每个数据包按照泊松分布的概率来发送

• 第二个M：每一个数据包在线路上的时间也按概率分布

• 1：只有一个线路

在周期T中有K个数据到达的概率满足泊松分布

$T$：平均等待时间（排队时间+服务时间）

$\lambda$：平均到达率(frames/sec)

$1/\mu$：平均帧长(bits/frame)

$C$：数据传输速率，信道容量(bps)，服务速率为µC(frames/sec)

静态信道分配：

把单个信道拆分成N个独立的子信道（时分复用或频分复用），每个信道的容量为${\frac{C}{N}}$

平均到达率：${\frac{\lambda}{N}}$

平均等待时间（效率较低）：

动态信道分配：

受控的多路访问：

• 有中心的（有集中的领导统一指挥）： 轮询
  必须要有主控站，若主控站出错则会导致瘫痪
  每个站发送数据不自由，需要等待轮询发送数据

• 分布式的（没有主站）： 令牌
  有令牌才可以发送数据

随机多路访问： 想发就发

协议： ALOHA,CSMA（载波侦听多路访问）,CSMA/CD（载波侦听多路访问，带冲突检测）,CSMA/CA（载波侦听多路访问，带冲突避免）

动态信道分配的五个关键假设：

• 站点：

  N个独立的站点，每个程序都要产生一些帧用于传输

  在长度为t的区间内生成一帧的概率为λt，其中λ为常数（新帧的到达率）

  一旦生成了一个帧，在这一帧被成功发送出去之前（不管是否接收，全部发送出去就行），站就会进入阻塞状态

• 单信道假设：

  所有通信的站点是分布式的

  可以用于通信的信道只有一个

  所有的站都可以发送也可以接收，接收是广播式的

  所有的站都是平等的，尽管协议软件可以为它们分配优先级

• 连续时间和分槽时间：

  • 连续时间：
    帧传输可以在任何时刻开始

  • 分槽时间：
    把时间分成很多个时间片
    每个站点只能在时间片的起始点发送
    一个时间槽可以包含0个帧（空闲插槽，谁都不发数据，带宽被浪费掉了）、1个帧（成功传输）或更多帧（产生冲突，也浪费掉了）

• 载波侦听：

  • 在尝试使用该信道之前，站点可以分辨清楚该信道是否正在使用（有没有载波）。如果处于繁忙状态，就不会发送数据，直到它闲置

  • 没有载波侦听：站点无法侦听到信道是否正在被使用。发就完了，发完之后再判断数据是否发送成功

• 冲突假设：
  如果两个站同时传输，就会产生时间上的重叠，因此信道就会毁坏
  所有的站点必须检测冲突，遇到冲突则重传

  • 有线信道： 直接检测冲突
  • 无线信道： 无法检测到冲突，需要在收到数据之后立刻发送一个ACK来推导冲突

  产生冲突后必须稍后再次将该帧进行传输

多路访问协议

ALOHA协议：

纯ALOHA：

• 每一个站点可以任意的发送数据

• 当数据发送到中心计算机之后，中心计算机就沿着下行信道把数据广播一遍，如果没收到就重传

• 如果产生冲突，发送方就等待一个随机的时间再次发送，可以实现好几个终端同时使用

假设：

• 帧的长度固定，一个帧的时间为t

• 帧的产生（包含新的帧和重传的帧）都满足泊松分布

参数：

• 吞吐量S： 每一个帧时可以平均成功传输的帧数，吞吐量越高越好
  $0\leq S\leq 1$

• 网络负载G： 每一个帧时向网络注入了多少帧的数据
  $G=\lambda（平均到达率）×T（平均等待时间）$
  $S\leq G$

在T时间内有K个数据到达的概率满足泊松分布

$P_0=P[在整个易受冲突时期内没有其他数据发送（到达时间间隔>2T）]=e^{-\lambda(2T)}=e^{-2G}$

吞吐量：$S = G×P_0 = Ge^{-2G}$

通过求导求出，当$G=0.5$，最大值为$S={\frac{1}{2e}}≈0.184$

分槽ALOHA：

将时间划分为离散的间隔，每个间隔对应一个帧，因此每个用户必须在时间槽的起始点发送数据

$P_0=P[到达时间间隔>T]=e^{-\lambda T}=e^{-G}$

当$G=1$，最大值为$S={\frac{1}{e}}≈0.368$

G=1时：
时间槽为空：37%（生成零帧的概率为$e^{-G}$）
成功发送：37%
产生冲突：26%

CSMA协议：

站点在发送之前先监听是否有载波，如果线路是忙碌的，就等待线路到空闲状态再发送

1-坚持CSMA：

• 如果信道是繁忙的，等待直到它变成空闲，然后立即传输帧

• 如果产生冲突，等待一段随机的时间，然后重新发送

• 低负载时有低延迟，高负载时有低吞吐量

非坚持CSMA：

• 如果信道繁忙，则等待随机的一段时间，然后再次检测信道（不是立即）

• 高负载时有高吞吐量

p-坚持CSMA：

• 如果信道繁忙，则等待下一个时间槽

• 如果空闲，则以p为概率发送帧，当概率为q=1-p时，它将延迟到下一个时间槽

• 重复此过程直到帧已发送或另一个站已开始发送为止

• 如果发生碰撞，则随机等待一段时间，然后重新发送

产生冲突的原因：

CDMA/CD：

当每个站点检测到冲突的时候，为了节约时间和带宽，应立即放弃当前传输；当通过危险期之后，则不可能产生冲突

带冲突检测的CSMA：

1-坚持CDMA/CD：

当某个站点检测到信道空闲时，一边立即发送数据，一边继续检测，如果检测到产生冲突，立即中止传输

信道的三种状态： 传输、竞争、空闲   单通道的CSMA/CD本质上是一个半双工系统 **无线局域网协议** * 无法检测到冲突（接收到的信号的强度是发送的百万分之一，无法检测到信号是否叠加），要使用ACK发现冲突 * 无线电发送器都有固定的覆盖范围 * 在一些无线局域网中，不是所有的站点都在其中某一个站点的覆盖范围里 * 干扰产生在接收方，而非发送方 * CSMA/CD不适用于无线局域网  (a)隐藏站问题 (b)暴露站问题 解决方法： **MACA冲突避免多路访问：** 1. A发送RTS帧(request to send)给B（30字节，包含数据长度） 2. B回答CTS帧(clear to send)给A（包含从RTS中的数据长度） 3. A接收到CTS帧后，开始数据传输 A发送RTS后，或B发送CTS后，其他站点要计算出从此刻开始到A发送完数据要用的时间，并在这段时间内保持沉默  ## 以太网(IEEE 802.3) **以太网电缆：**   **10BaseT：** * HUB 每个站点有专用的电缆连接到HUB继线器上 物理上星状结构，逻辑上总线结构；任意站发送，所有站接收 * RJ-45, 5 UTP 两对线，分别用于收和发 差分传输：减少电磁干扰 同一线对的绞合：减少近端串扰 以太网的拓扑结构：  **以太网编码：** Manchester编码：波特率是比特率的两倍

以太网MAC子层协议：

帧格式：

IEEE 802地址：

帧的长度：

二进制指数退避算法(CSMA/CA)：

时隙长度：51.2µsec

产生冲突后，每个产生冲突的站都要随机生成一个数n，接着退避n个周期，即在n个周期内不允许发送数据

第1次碰撞，随机数0~1
第2次碰撞，随机数0~3
……
第9次碰撞，随机数0~511
第10次碰撞，随机数0~1023
第11次碰撞，随机数0~1023
……
第16次碰撞，随机数0~1023

16次碰撞后，则向高层报告失败
当有较少的站发生冲突时，可以保证低延迟
当有很多的站发生冲突时，可以保证冲突在一个合理的时间间隔内解决
在1023内截断回退可以防止边界变得太大

以太网性能：

IEEE 802.3性能：
Frame length: F
Bandwith: B
Cable length: L
Speed of signal propagation: c
channel efficency = ${\frac{1}{1+2eBL/cF}}$

512位时间槽下，10Mbps的以太网的效率

交换式以太网：

交换机只将帧输出到这些帧的目的端口

• 当一个端口接收到一个帧时，检查地址字段，将帧通过高速背板（计算机内部的硬件）转发到目标端口

• 背板通常以Gbps的速度运行

• 一旦确定目的端口，就直接在线路上传输帧，以便它到达预定的站

• 其他端口甚至都不知道这个帧的存在

冲突域：

HUB：
所有站都在同一冲突域中(按照CSMA/CD进行通信)

Switch：
每个端口都是自己独立的冲突域
如果电缆是全双工，站和端口都可以在同一时间发送一个帧，不可能发生冲突，不需要CSMA/CD
如果电缆是半双工，站和端口必须与CSMA/CD竞争传输

快速以太网

802.3u（提升了十倍的以太网）：

保留所有旧的帧格式、接口和过程规则，向后兼容现有的以太网局域网

将比特时间从100ns减少到10ns，使用4B/5B编码方案

将最大电缆长度减少10倍

所有快速以太网系统都使用继线器和交换机

快速以太网电缆：

100Base-TX：

需要2对双绞线(5类UTP，带宽125MHz)

• 一对是从计算机到继线器/交换机
• 另一对从继线器/交换机到计算机

4B/5B编码方式：125 * 4/5 = 100Mbps

互联设备：

继线器(半双工通信)

• 输入的线路逻辑连接，形成一个单一的冲突域（280m，电缆长度为原来的十分之一）
• 所有的标准规则，包括二进制指数回退算法都仍然适用，所以系统就像老式的以太网一样工作
• 继线器不允许100Base-FX

交换机(全双工通信)
传入帧被缓冲并传递到目的地
100Base-FX电缆太长，不符合碰撞算法，必须连接到交换机

10Mbps & 100Mbps自动配置：

• 802.3u提供了一种方法让两站之间协商速度(10mbps或100mbps) 和 双工性(半双工(CSMA/CD)或全双工(无冲突))
• 大多数快速以太网产品都使用这个特性来自动配置自己，优先100M全双工

千兆以太网

802.3z：

使以太网速度再快10倍

保持向后兼容所有现有以太网标准

• 包含单播和多播的无确认的数据报服务
• 使用之前的48位地址模式
• 保持相同的帧格式，包括最小和最大长度

千兆以太网电缆：

交换机(全双工模式)

• 由于不存在竞争，因此不使用CSMA/CD协议
• 电缆的最大长度由信号强度问题决定
• 交换机支持自动配置

继线器(半双工模式)

• 模拟经典以太网
  • 电气上连接内部所有线路形成一个总线
  • 产生冲突是可能的，所以需要CSMA/CD协议
• 问题:半径25米，变得更短了
• 解决方案：
  • 载波扩充
    在正常帧后添加padding，将帧扩展到512字节(padding由发送硬件添加，由接收硬件移除)
  • 帧突发
    允许发送方在一次传输中传输多个帧的连接序列，接收方再将每个帧取出来，如果级联起来的整个突发仍然小于512个字节，则硬件会再次对它进行填充
    使得网络半径保持在200米

流量控制：

控制帧：

• 一端发送一个类型为0x8808的特殊的控制帧到另一端，告诉它暂停一段时间
• data字段的前两个字节给出command，后面的字节提供参数。
• 使用PAUSE帧，512ns~33.6ms

无线局域网

802.11体系结构

802.11协议栈

CSMA/CA

802.11 MAC层与以太网不同

• 无线电永远是半双工的
• 接收信号比发射信号弱$10^6$倍，冲突检测机制不起作用

使用CSMA/CA协议避免冲突

• 当一个站有帧要发送时:
  • 监听并等待直到通道空闲，然后再等待一个短的时间DIFS
  • 随机回退(0~15个时间槽)：从回退时间开始倒数，当有其他帧在发送时则暂停倒数，当计数器达到0时再发送这一帧
  • 如果帧通过，目的地发送一个短的ACK
  • 缺少ACK则会被推断为冲突或其他错误，将回退时间加倍（范围0~31）后并再次尝试（如以太网中的指数回退）直到成功发送帧或达到重传的最大次数

信道侦听

物理侦听：

• 检查媒体是否有有效的信号

虚拟侦听：

• 每个帧携带一个NAV，数据帧的NAV包括发送数据和ACK所需的时间
• 每个站通过跟踪NAV(网络分配矢量)来保存信道使用时间的逻辑记录

• 由于NAV，802.11的RTS/CTS不能解决暴露站的问题。C收到B发送的RTS，根据NAV，它将在B的数据帧传输的整个过程中（包括传输ACK）退避，而不能发送给D
• 而MACA协议将允许同一覆盖范围内两对主机同时通信

提高成功传输的概率（可靠性）

速率的自动调节

• 速率慢下来后就会使用更强大的调制方法，降低噪音的破坏力
• 如果传输的帧损耗很小，站点可以偶尔测试一个更高的速率，看看是否应该使用它

802.11允许帧被分割成片段

• 每个片段有单独的编号和单独的校验和
• 使用停等协议，一问一答

节省电源

信标帧

• 客户端可以进入省电模式，AP将缓存数据流量
• 为了检查入境流量，客户端在每次信标帧来时苏醒过来，并检查作为信标帧一部分的流量图
• 这张图告诉客户是否有为它缓冲的流量
• 如果有，则客户给AP发送一个poll消息，示意AP将缓冲的流量发送过来
• 在接收了缓冲的流量之后， 客户可以再回去打盹，直到下一个新标帧被发送出来时苏醒。

APSD(自动省电交付)

• 在客户端发送帧到AP后才将其缓存的帧发送到客户端

QoS：802.11中的IFS(帧间间隔)

• SIFS：
  发完一个数据后，等一下再发另外一个帧（ACK帧、其他控制帧序列，如RTS和CTS、fragment），它们时间的时间间隔就是SIFS

• AIFS1（仲裁帧间隔）：
  PCF、语音或其他高优先级的流量

• DIFS(DCF)：
  常规数据帧

• AIFS4：
  可以延迟到常规流量之后发送的背景流量

QoS：TXOP（传输机会）

两个站:6Mbps和54M bps
它们每个站每次都能发送一帧，平均都能获得5.4Mbps的带宽
快的站点的速率会被慢的站点拖累

使用TXOP：
每个站得到等量的通话时间（有n个站，则每个站的吞吐量为速率的n分之一）
上述例子中，它们分别获得3Mbps和27Mbps

802.11 帧结构

数据帧

控制帧：RTS、CTS、ACK
管理帧

802.2:LLC(Logical Link Control)

• 运行在802.3和其他802协议之上
  • 通过向网络层提供单一格式和接口，隐藏各种802网络之间的差异
• LLC提供三种服务选项
  • 不可靠的数据报服务(尽力数据报服务)
  • 确认数据报服务(差错控制)
  • 可靠的面向连接的服务(差错控制和流量控制)

数据链路层交换

网桥

问题

• 每个局域网使用不同的帧格式
• 局域网不以相同的数据速率运行
• 不同的802局域网具有不同的最大帧长
• 安全性：无线网络在数据链路层支持加密，以太网不支持
• QoS(服务质量:802.11,802.16)

透明/自学习网桥

工作在混杂模式

• 接受它所连接的所有局域网上传输的每一帧

站表

• 列出每个可能的目的地址，并告诉它属于哪个局域网(LAN)

传入帧的路由过程：

• 如果目的局域网和源局域网相同，则丢弃该帧
  
• 如果目的局域网和源局域网已知且不一致，则转发该帧
• 如果目的局域网未知或是组播/广播地址，则采用泛洪算法
  • 泛洪算法：对于每个发向未知目标地址的入境帧，网桥将它输出到所有的端口，但它来的那个输入端口除外

站表：逆向学习

每个表项主要包括：MAC地址，端口号，时间戳

初始化

• 当网桥第一次插上电源时，所有哈希表都是空的

添加

• 网桥以混杂模式运行，因此它们可以看到在它们的任何局域网上发送的每一帧

• 通过查看源地址，它们可以知道哪台机器在哪个局域网上可访问

• 动态拓扑：
  站表的每个表项增设一个arrive time域，每当创建一个哈希表条目时，帧的到达时间就会记录在条目中
  当源地址已经在表中的帧到达时，它的条目将被更新为当前时间
  定期扫描哈希表并清除所有超过几分钟的条目

  • 如果将一台计算机从局域网中拔下，在大楼里四处移动，然后在其他地方重新插上电源，不需要任何人工干预，几分钟内它就会恢复正常工作
• 这种算法还意味着，如果一台机器安静了几分钟，发送给它的任何流量都必须被淹没，直到它下次自己发送一帧，网桥会修改哈希表中的值，或等到被清除

生成树网桥

拓扑中的循环：为了提高可靠性，一些站点在局域网之间并联使用两个或多个网桥，这种安排引入了一些问题，因为它在拓扑中建立了循环

生成树网桥：
网桥之间相互通信，并使用到达每个局域网的生成树覆盖实际的拓扑结构
使用这种生成树，从每个局域网到每个局域网只有一条路径，环路是不可能存在的
为了构造一个虚拟的无环拓扑结构，局域网之间的一些潜在连接被忽略了

动态拓扑

• BPDU (Bridge Protocol Data Unit,38bytes)
  • 网桥定期（一般2s）组播一个消息(组播地址：MAC 01:80:c2:00:00:00)出它的所有端口，这个消息不能被转发，它包括:
    • 基于网桥自己的MAC地址的ID
    • 它认为是根的ID
    • 到根的距离
• 根桥（全网）
  • 选择ID最低的网桥作为根，交换足够多的消息后，所有网桥都会对根达成一致
• 根端口（网桥中）
  • 记住到根的最短路径，如果有多条等效路径，则选择ID最低的过桥路径
• 指派端口（局域网中）
  • 在同一个局域网中的，离根最近的端口，等价着选最小ID的
  • 不是根端口也不是指派端口，则会处于阻塞状态，不收发数据
• 阻塞端口
  • 不发送也不接收数据
• 算法在正常运行时继续运行，自动检测拓扑变化并更新树

Repeaters（中继器）, Hubs（集线器）, Bridges（网桥）, Switches（交换机）, Routers（路由器） and Gateways（网关）

• 中继器：
  中继器是模拟设备，主要用来处理自己所连的线缆上的信号。在一个线缆上出现的信号被清理、放大，然后再被放到另一个线缆上。中继器并不理解帧、数据包或帧头，它们只知道把比特编码成电压的符号

• 集线器：
  集线器有许多条输入线路，它将这些输入线路连接在一起。从任何一条线路上到达的帧都被发送到所有其他的线路上。如果两帧同时到达，它们将会冲突，则要遵循CSMA/CD
  集线器与中继器不同，它们（通常）不会放大入境信号，并且可以有多个输入线路，但是，两者之间的差别并不大。与中继器一样，集线器也是物理层设备，因而它不会检查链路层地址，也不以任何方式使用该地址

• 网桥：
  网桥连接两个或多个局域网，一个现代网桥有多个端口。网桥要能够理解什么是帧，接收帧后检查校验和是否正确，不正确则丢弃，正确则根据帧头的源地址和目的地址，按照洪泛算法等进行工作

• 交换机：
  交换机就是网桥

• 路由器：
  当一个数据包进入到路由器时，帧头和帧尾被剥掉，帧的有效载荷字段中的数据包被传给路由软件，路由软件利用数据包的头信息来选择输出线路

• 传输网关：
  传输网关将两台使用了不同面向连接传输协议的计算机连接起来

• 应用网关：
  应用网关能理解数据的格式和内容，并且可以将消息从一种格式转换为另一种格式

网桥的站表一般都是通过软件实现（哈希表），然而以太网速度很快，查表的速度可能跟不上，因此有如下解决办法：

• 使用专用的VLSI（Very Large Scale Integration超大规模集成）芯片（CAM内容访问存储器，直接和表项中所有的元素进行比较），查找和更新站表条目只需几微秒
• 缓冲区：如果帧发送的速度比重传的速度快，交换机可能会耗尽缓冲区并开始丢弃帧
• 直通式交换机： 见到目的地址便开始转发，边接收边转发，接收和发送的速度要一样快

虚拟局域网

使用虚拟局域网的原因：

• 广播风暴：广播帧/组播帧会在全网进行发送，或单播帧发往一个不存在或暂不知的地址时要用洪泛算法
  • 局域网容量被这些帧占用
  • 机器在处理和丢弃所有正在广播的帧时都瘫痪了
• 安全
  • 许多部门都有不希望有信息传递到部门之外

虚拟局域网：

VLAN ID：

• 在交换机中，配置表显示哪些VLAN可以通过哪些端口访问
  • 每个端口分配一个VLAN ID
    此方法仅适用于端口上的所有机器属于同一VLAN的情况
  • 每个MAC地址分配一个VLAN ID
    当帧到达时，交换机提取MAC地址并在表中查找该帧来自哪个VLAN
  • 为每个第三层协议或IP地址分配一个VLAN ID

802.1Q帧格式：

• VLAN protocol ID (16 bits)帧类型： 0x8100，表示802.1Q帧（带颜色的一帧）
• Pri (3 bits)：表示优先级
• CFI (1 bit)
• VLAN Identifier (12 Bits)：表示颜色
• 802.1Q Max frame length: 1522 bytes

……未完待续♬