9 数据链路层

数据链路层

数据链路层服务

• 主机和路由器:结点(nodes)
• 连接相邻结点的通信信道:链路(links)
  • 有线链路(wired links)
  • 无线链路(wireless links)
  • 局域网(LANs)
• 链路层(第2层)数据分组: 帧(frame)，封装网络层数据报

数据链路层负责通过一条链路从一个节点向另一个物理链路直接相连的相邻结点传送数据报。

数据链路层具体服务：

• 组帧(framing)
  • 封装数据报构成数据帧，加首部和尾部
  • 帧同步
• 链路接入(link access)
  • 如果是共享介质，需要解决信道接入(channel access)
  • 帧首部中的“MAC”地址，用于标识帧的源和目的
    • 不同于IP地址!
• 相邻结点间可靠交付
  • 在低误码率的有线链路上很少采用(如光纤，某些双绞线等)
  • 无线链路: 误码率高，需要可靠交付
• 流量控制(flow control)
  • 协调(pacing)相邻的发送结点和接收
• 差错检测(error detection)
  • 信号衰减和噪声会引起差错
  • 接收端检测到差错:
    • 通知发送端重传或者直接丢弃帧
• 差错纠正(error correction)
  • 接收端直接纠正比特差错
• 全双工和半双工通信控制
  • 全双工:链路两端结点同时双向传输
  • 半双工:链路两端结点交替双向传输

链路层的具体实现?

• 每个主机或路由器接口
• 链路层在“适配器”(即网络接口卡-NIC)中实现或者在一个芯片上实现
  • 以太网网卡，802.11网卡;
  • 以太网芯片组
  • 实现链路层和物理层
• 链接主机的系统总线
• 由硬件、软件与固件组成

网卡间通信

• 发送端:
  • 将数据报封装成帧
  • 增加差错检测比特，实现可靠数据传输和流量控制等.
• 接收端:
  • 检测差错，实现可靠数据传输和流量控制等
  • 提取数据报，交付上层协议实体

差错检测: 差错编码

差错编码基本原理: D→DR，其中R为差错检测与纠正比特(冗余比特）

差错编码不能保证100%可靠!

差错编码的检错能力

• 差错编码可分为 检错码 与 纠错码
• 对于检错码，如果编码集的汉明距离ds=r+1，则该差错编码可以检测r位的差错

• 例如，编码集{0000,0101,1010,1111}的汉明距离d=2, 可以100%检测1比特差错
  • 对于纠错码，如果编码集的汉明距离d=2r+1，则该差错编码可以纠正r位的差错

• 例如，编码集{000000,010101,101010,111111}的汉明距离d=3，可以纠正1比特差错，如100010 纠正为 101010。

奇偶校验码

Internet校验和(Checksum)

• 发送端:
  • 将“数据”(校验内容)划分为16位的二进制“整数”序列
  • 求和(sum): 补码求和(最高位进位的“1”,返回最低位继续加)
  • 校验和(Checksum):sum的反码
  • 放入分组(UDP、TCP、IP)的校验和字段
• 接收端:
  • 与发送端相同算法计算
  • 计算得到的”checksum”:
    • 为16位全0(或sum为16位全1): 无错
    • 否则: 有错

循环冗余校验码(CRC)

多路访问控制(MAC)协议

两类“链路”:

• 点对点链路
  • 拨号接入的PPP
  • 以太网交换机与主机间的点对点链路
• 广播链路(共享介质)
  • 早期的总线以太网
  • HFC的上行链路
  • 802.11无线局域网

• 单一共享广播信道
• 两个或者两个以上结点同时传输: 干扰(interference)
  • 冲突(collision)
    • 结点同时接收到两个或者多个信号→接收失败!
• 多路访问控制协议(multiple access control protocol)
  • 采用分布式算法决定结点如何共享信道，即决策结点何时可以传输数据
  • 必须基于信道本身，通信信道共享协调信息!
    • 无带外信道用于协调

理想MAC协议

• 给定: 速率为 R bps 的广播信道
• 期望:
  1. 当只有一个结点希望传输数据时, 它可以以速率R发送.
  2. 当有 M 个结点期望发送数据时，每个节点平均发送数据的平均速率是R/M
  3. 完全分散控制:
     • 无需特定结点协调
     • 无需时钟、时隙同步
  4. 简单

MAC协议分类

三大类:

• 信道划分(channel partitioning)MAC协议
  • 多路复用技术
  • TDMA、FDMA、CDMA、WDMA等
• 随机访问(random access)MAC协议
  • 信道不划分，允许冲突
  • 采用冲突“恢复”机制
• 轮转(“taking turns”)MAC协议
  • 结点轮流使用信道

TDMA: time division multiple access

• “周期性”接入信道
• 每个站点在每个周期，占用固定长度的时隙(e.g.长度=分组传输时间)
• 未用时隙空闲(idle)
  • 例如:6-站点LAN，1,3,4传输分组，2,5,6空闲

FDMA: frequency division multiple accesss

• 信道频谱划分为若干频带(frequency bands)
• 每个站点分配一个固定的频带
• 无传输频带空闲
  • 例如:6站点LAN，1,3,4频带传输数据,2,5,6频带空闲。

随机访问MAC协议

• 当结点要发送分组时:
  • 利用信道全部数据速率R发送分组
  • 没有事先的结点间协调
• 两个或多个结点同时传输:→“冲突”
• 随机访问MAC协议需要定义:
  • 如何检测冲突
  • 如何从冲突中恢复(e.g.,通过延迟重传)
• 典型的随机访问MAC协议:
  • 时隙(sloted)ALOHA
  • ALOHA
  • CSMA、CSMA/CD、CSMA/CA

时隙ALOHA协议

假定:

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

运行:

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

优点:

• 单个结点活动时，可以连续以信道全部速率传输数据
• 高度分散化:只需同步时隙
• 简单

缺点:

• 冲突，浪费时隙
• 空闲时隙
• 结点也许能以远小于分组传输时间检测到冲突
• 时钟同步

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

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

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->oo= 1/(2e)= 0.18

效率比时隙ALOHA协议更差!

CSMA协议

• 载波监听多路访问协议CSMA (carrier sense multiple access)
• 发送帧之前，监听信道(载波):
  • 信道空闲:发送完整帧
  • 信道忙:推迟发送
    • 1-坚持CSMA
    • 非坚持CSMA
    • P-坚持CSMA
• 冲突可能仍然发生:信号传播延迟
• 继续发送冲突帧:浪费信道资源

CSMA/CD协议

• CSMA/CD: CSMA with Collision Detection
  • 短时间内可以检测到冲突.
  • 冲突后传输中止，减少信道浪费
• 冲突检测:
  • 有线局域网易于实现:测量信号强度，比较发射信号与接收信号
  • 无线局域网很难实现:接收信号强度淹没在本地发射信号强度下

“边发边听，不发不听”

为保证能监听到冲突，必须满足：
L/R>=2d_max/v

CSMA/CD效率

CSMA/CD 效率远优于 ALOHA，并且简单、分散!

轮转访问MAC协议

• 信道划分MAC协议:
  • 网络负载重时，共享信道效率高，且公平
  • 网络负载轻时，共享信道效率低!
• 随机访问MAC协议:
  • 网络负载轻时，共享信道效率高，单个结点可以利用信道的全部带宽
  • 网络负载重时，产生冲突开销
• 轮转访问MAC协议:
  • 综合两者的优点!

- 轮询(polling):

• 主结点轮流“邀请从属结点发送数据
• 典型应用:
  • “哑(dumb)”从属设备
• 问题:
  • 轮询开销
  • 等待延迟
  • 单点故障

- 令牌传递(token passing):

• 控制令牌依次从一个结点传递到下一个结点
• 令牌:特殊帧
• 问题:
  • 令牌开销
  • 等待延迟
  • 单点故障

MAC协议总结

• 信道划分MAC协议: 时间、频带、码片划分
  • TDMA、FDMA、CDMA
• 随机访问MAC协议:
  • ALOHA,S-ALOHA,CSMA,CSMA/CD
  • CSMA/CD应用于以太网
  • CSMA/CA应用802.11无线局域网
• 轮转访问MAC协议:
  • 主结点轮询; 令牌传递
  • 蓝牙、FDDI、令牌环网