目标:

理解数据链路层服务的原理:
检错和纠错
共享广播信道：多点接入（多路访问）
链路层寻址
LAN:以太网、WLAN、VLANs
可靠数据传输，流控制: 解决

引论和服务

链路层

上下文：

数据报（分组）在不同的链路上以不同的链路协议传送：

第一跳链路：以太网
中间链路：帧中继链路
最后一跳802.11 :

不同的链路协议提供不同的服务

e.g., 比如在链路层上提供（或没有）可靠数据传送

链路层服务

成帧，链路接入：

将数据报封装在帧中，加上帧头[包括原mac地址、目标mac地址及其他字段]、帧尾部
如果采用的是共享性介质，信道接入获得信道访问权
在帧头部使用“MAC”（物理）地址来标示源和目的 [ 不同于IP地址 ]

在（一个网络内）相邻两个节点完成可靠数据传递

在低出错率的链路上（光纤和双绞线电缆）很少使用
在无线链路经常使用：出错率高

一般化的链路层服务，不是所有的链路层都提供这些服务一个特定的链路层只是提供其中一部分的服务

在相邻节点间（一个子网内）进行可靠的转发

在低差错链路上很少使用 (光纤,一些双绞线)
在高差错链路上需要进行可靠的数据传送

出错率高，如果在链路层不做差错控制工作，漏出去的错误比较高；到了上层如果需要可靠控制的数据传输代价会很大

链路层提供的服务：

流量控制：使得相邻的发送和接收方节点的速度匹配
错误检测：差错由信号衰减和噪声引起、接收方检测出的错误: 通知发送端进行重传或丢弃帧
差错纠正: 接收端检查和纠正bit错误，不通过重传来纠正错误
半双工和全双工:

半双工：链路可以双向传输，但一次只有一个方向

链路层实现位置

有很多不同的位置都会实现链路层

在每一个主机上

也在每个路由器上
交换机的每个端口上

链路层功能在“适配器”上实现 (aka network interface card NIC) 或者在一个芯片组上

以太网卡，802.11 网卡 ; 以太网芯片组
实现链路层和相应的物理层功能

接到主机的系统总线上
硬件、软件和固件的综合体

适配器通信

发送方:

在帧中封装数据报，将每个比特打出去
加上差错控制编码，实现RDT和流量控制功能等

接收方：

检查有无出错，执行 rdt和流量控制功能等
解封装数据报，将至交给上层

适配器是半自治的实现了链路和物理层功能

差错检测和纠正

错误检测

EDC=差错检测和纠正位（冗余位）

D =数据由差错检测保护，可以包含头部字段 错误检测不是100%可靠的!

协议会漏检一些错误，但是很少
更长的EDC字段可以得到更好的检测和纠正效果

奇偶校验

单bit奇偶校验: 检测单个bit级错误

2维奇偶校验：检测和纠正单个bit错误

Internet校验和

目标: 检测在传输报文段时的错误（如位翻转），（注：仅仅用在传输层）

发送方:

将报文段看成16-bit整数
报文段的校验和: 和 (1’ 的补码和)
发送方将checksum的值放在‘UDP校验和’ 字段

接收方:

计算接收到的报文段的校验和
检查是否与携带校验和字段值一致:

不一致：检出错误
一致：没有检出错误，但可能还是有错误

有更简单的检查方法全部加起来看是不是全1

检验和：CRC（循环冗余校验）

不太明白….

强大的差错检测码
将数据比特 D, 看成是二进制的数据
生成多项式G：双方协商r+1位模式（r次方）
- 生成和检查所使用的位模式

目标: 选择r位 CRC附加位R，使得

<D , R>正好被 G整除 (modulo 2)

接收方知道 G, 将<D , R> 除以 G. 如果非0余数: 检查出错误!

能检出所有少于r+1位的突发错误

实际中广泛使用（以太网、802.11 WiFi、ATM）

多点访问协议

两种类型的链路（一个子网内部链路连接形式）：

点对点

拨号访问的PPP
以太网交换机和主机之间的点对点链路

广播（共享线路或媒体 )

传统以太网
HFC上行链路
802.11无线局域网

单个共享的广播型链路。每个节点都是可以发送的，如果多个节点同时传送， 就会****产生冲突（collision）如何解决呢，就是使用下面的协议

多路访问协议（介质访问控制协议：MAC）

理想的多路访问协议

给定：Rbps的广播信道
必要条件：

当一个节点要发送时，可以R速率发送.
当M个节点要发送，每个可以以R/M的平均速率发送
完全分布的:
没有特殊节点协调发送
没有时钟和时隙的同步
简单

MAC ( 媒体访问控制 ) 协议：分类

3大类:

信道划分

把信道划分成小片（时间、频率、编码）
分配片给每个节点专用

随机访问

信道不划分，允许冲突
冲突后恢复

依次轮流

节点依次轮流
但是有很多数据传输的节点可以获得较长的信道使用权

1. 信道划分

1.1. MAC协议：TDMA

TDMA:time division multiple access

轮流使用信道，信道的时间分为周期
每个站点使用每周期中固定的时隙(长度=帧传输时间) 传输帧
如果站点无帧传输，时隙空闲-》浪费
如：6站LAN，1、3、4有数据报，时隙2、5、6空闲

1.2. 信道划分MAC协议：FDMA

FDMA: frequency division multiple access

信道的有效频率范围被分成一个个小的频段
每个站点被分配一个固定的频段
分配给站点的频段如果没有被使用，则空闲
例如：6站LAN，1、3、4有数据报，频段2、5、 6空闲

1.3. 码分多路访问（CDMA）

CDMA (code division multiple access) :

所有站点在整个频段上同时进行传输, 采用编码原理加以区分
完全无冲突
假定:信号同步很好,线性叠加

比方

TDM:不同的人在不同的时刻讲话
FDM:不同的组在不同的小房间里通信
CDMA:不同的人使用不同的语言讲话

2. 随机存取协议

当节点有帧要发送时

以信道带宽的全部 R bps发送
没有节点间的预先协调

两个或更多节点同时传输，会发生➜冲突 “collision”

随机存取协议****规定:

如何检测冲突
如何从冲突中恢复（如：通过稍后的重传）

随机MAC协议:

时隙ALOHA
ALOHA
CSMA, CSMA/CD, CSMA/CA

2.1. 时隙ALOHA

假设

所有帧是等长的
时间被划分成相等的时隙，每个时隙可发送一帧
节点只在时隙开始时发送帧
节点在时钟上是同步的
如果两个或多个节点在一个时隙传输，所有的站点都能检测到冲突

运行

当节点获取新的帧，在下一个时隙传输
传输时没有检测到冲突，成功

节点能够在下一时隙发送新帧

检测时如果检测到冲突，失败

节点在每一个随后的时隙以概率p重传帧直到成功

优点：

节点可以以信道带宽全速连续传输
高度分布：仅需要节点之间在时隙上的同步
简单

缺点

存在冲突，浪费时隙
即使有帧要发送，仍然有可能存在空闲的时隙
节点检测冲突的时间<帧传输的时间
必须传完
需要时钟上同步

效率：当有很多节点，每个节点有很多帧要发送时，x%的时隙是成功传输帧的时隙

最好情况：信道利用率37%

2.2. 纯ALOHA(非时隙)

无时隙ALOHA：简单、无须节点间在时间上同步
当有帧需要传输：马上传输
冲突的概率增加:
- 帧在t0 发送，和其它在[t0 -1, t0 +1]区间内开始发送的帧冲突
- 和当前帧冲突的区间（其他帧在此区间开始传输）增大了一倍

效率：

P(指定节点成功) = P(节点传输) .

P(其它节点在[t0 -1, t0 ]不传) .

P(其它节点在[t0 , t0 +1不传] = p . (1-p)N-1 . (1-p)N-1 = p . (1-p)2(N-1)

选择最佳的p、N趋向无穷大… = 1/(2e) = 17.5%

效率比时隙ALOHA更差了!

2.3. CSMA(载波侦听多路访问)

Aloha: 如何提高ALOHA的效率 : 在发之前不管有无其他节点在传输

CSMA: 在传输前先侦听信道:

如果侦听到信道空闲，传送整个帧
如果侦听到信道忙，推迟传送

SCMA冲突：

冲突仍然可能发生: 由传播延迟造成：两个节点可能侦听不到正在进行的传输

冲突: 整个冲突帧的传输时间都被浪费了，是无效的传输(红黄区域)

注意：传播延迟（距离）决定了冲突的概率（距离越远时间越长，冲突发生的可能性越大）

节点依据本地的信道使用情况来判断全部信道的使用情况所以基本是听不到的

2.4. CSMA/CD(冲突检测) [ 目前局域网使用 ]

载波侦听CSMA：和在CSMA中一样发送前侦听信道
没有传完一个帧就可以在短时间内检测到冲突
冲突发生时则传输终止，减少对信道的浪费

冲突检测CD技术，有线局域网中容易实现：

检测信号强度，比较传输与接收到的信号是否相同
通过周期的过零点检测

以太网CSMA/CD算法思想

适配器获取数据报，创建帧
发送前：侦听信道CS
1 )闲：开始传送帧
2 )忙：一直等到闲再发送
发送过程中，冲突检测CD
1 )没有冲突:成功
2 )检测到冲突:放弃,之后尝试重发
发送方适配器检测到冲突，
除放弃外，还发送一个Jam信号，所有听到冲突的适配器也是如此
强化冲突：让所有站点都知道冲突
如果放弃，适配器进入指数
退避状态
在第m次失败后，适配器随机选择一个{0，1，2，， 2^m-1}中K，等待K*512位时，然后转到步骤2

算法目标： 适配器试图适应当前负载，在一个变化的碰撞窗口中随机选择时间点尝试重发

举例：

首次碰撞：在{0，1}选择K；延迟K*512位时

第2次碰撞：在{0，1，2，3}选择K

第10次碰撞：在{0，1，2，3，……，1023}选择 K

CSMA/CD效率

比ALOHA更好的性能，而且简单，廉价，分布式！

2.5. 无线局域网中的 MAC： CSMA/CA

冲突: 2+ 站点（AP或者站点）在同一个时刻发送

802.11: CSMA – 发送前侦听信道

不会和其它节点正在进行的传输发生冲突

802.11: 没有冲突检测!

无法检测冲突：自身信号远远大于其他节点信号
即使能CD：冲突!=成功
目标: avoid collisions: CSMA/C(ollision)A(voidance)
- 无法CD，一旦发送一股脑全部发送完毕，不CD
- 为了避免无CD带来的信道利用率低的问题，事前进行冲突避免

发送方：

如果站点侦测到信道空闲持续DIFS长，则 传输整个帧 (no CD)
如果侦测到信道忙碌，那么 选择一个随机回退值，并在信道空闲时递减该值；如果信道忙碌，回退值不会变化到数到0时（只生在信道闲时）发送整个帧如果没有收到ACK, 增加回退值，重复2

802.11 接收方

如果帧正确，则在SIFS后发送ACK

(无线链路特性，需要每帧确认；例如：由于隐藏终端问题，在接收端可能形成干扰,接收方没有正确地收到。链路层可靠机制)

在count down时，侦听到了信道空闲为什么不发送，而要等到0时在发送

2个站点有数据帧需要发送，第三个节点正在发送
LAN CD：让2者听完第三个节点发完，立即发送
冲突：放弃当前的发送，避免了信道的浪费于无用冲突帧的发送
代价不昂贵

WLAN : CA

无法CD，一旦发送就必须发完，如冲突信道浪费严重，代价高昂
思想：****尽量事先避免冲突，而不是在发生冲突时放弃然后重发
听到发送的站点，分别选择随机值，回退到0发送

不同的随机值，一个站点会胜利
失败站点会冻结计数器，当胜利节点发完再发

无法完全避免冲突的情况

两个站点相互隐藏

• A,B 相互隐藏，C在传输

• A,B选择了随机回退值

• 一个节点如A胜利了，发送

• 而B节点收不到，顺利count down到0 发送

• A,B的发送在C附近形成了干扰

选择了非常靠近的随机回退值：

• A,B选择的值非常近

• A到0后发送

• 但是这个信号还没到达B时

• B也到0了，发送

• 冲突

冲突避免

思想: 允许发送方“预约”信道，而不是随机访问该信道: 避免长数据帧的冲突（可选项）

发送方首先使用CSMA向BS发送一个小的RTS分组
BS广播 clear-to-send CTS，作为RTS的响应
CTS能够被所有涉及到的节点听到

采用小的预约分组，可以完全避免数据帧的冲突

3. 轮流(Taking Turns)MAC协议

信道划分MAC协议:

共享信道在高负载时是有效和公平的
在低负载时效率低下下只能等到自己的时隙开始发送或者利用1/N的信道频率发送
- 当只有一个节点有帧传时，也只能够得到1/N个带宽分配

随机访问MAC协议

在低负载时效率高：单个节点可以完全利用信道全部带宽
高负载时：冲突开销较大，效率极低，时间很多浪费在冲突中

轮流协议： 有2者的优点!

论询:

主节点邀请从节点依次传送
从节点一般比较“dumb”

缺点:

轮询开销：轮询本身消耗信道带宽
等待时间：每个节点需等到主节点轮询后开始传输，即使只有一个节点，也需要等到轮询一周后才能够发送
单点故障：主节点失效时造成整个系统无法工作

令牌传递

控制令牌( token)循环从一个节点到下一个节点传递
令牌报文：特殊的帧

缺点

令牌开销：本身消耗带宽
延迟：只有等到抓住令牌，才可传输
单点故障 (token)：
- 令牌丢失系统级故障，整个系统无法传输
- 复杂机制重新生成令牌

链路层和局域网

引论和服务

相关术语:

链路层

上下文：

链路层服务

链路层实现位置

适配器通信

差错检测和纠正

错误检测

奇偶校验

Internet校验和

检验和：CRC（循环冗余校验）

多点访问协议

理想的多路访问协议

MAC ( 媒体访问控制 ) 协议：分类

1. 信道划分

1.1. MAC协议：TDMA

1.2. 信道划分MAC协议：FDMA

1.3. 码分多路访问（CDMA）

2. 随机存取协议

2.1. 时隙ALOHA

2.2. 纯ALOHA(非时隙)

2.3. CSMA(载波侦听多路访问)

2.4. CSMA/CD(冲突检测) [ 目前局域网使用 ]

2.5. 无线局域网中的 MAC： CSMA/CA

3. 轮流(Taking Turns)MAC协议

总结：

LANs

引论 和 服务

相关术语:

链路层

上下文：

链路层服务

链路层实现位置

适配器通信

差错检测和纠正

错误检测

奇偶校验

Internet校验和

检验和：CRC（循环冗余校验）

多点访问协议

理想的多路访问协议

MAC ( 媒体访问控制 ) 协议：分类

1. 信道划分

1.1. MAC协议：TDMA

1.2. 信道划分MAC协议：FDMA

1.3. 码分多路访问（CDMA）

2. 随机存取协议

2.1. 时隙ALOHA

2.2. 纯ALOHA(非时隙)

2.3. CSMA(载波侦听多路访问)

2.4. CSMA/CD(冲突检测) [ 目前局域网使用 ]

2.5. 无线局域网中的 MAC： CSMA/CA

3. 轮流(Taking Turns)MAC协议

总结：

LANs

引论和服务