功能：保证数据正确的顺序，无错和完整

1 链路层概述

信道类型

• 点对点信道
  一对一的点对点通信方式
• 广播信道
  一对多的广播通信方式，过程比较复杂。广播信道上连接的主机很多，必须使用专用的共享信道协议来协调这些主机的数据发送

数据链路层的简单模型

• 链路层地址
  LAN地址，物理地址或称为MAC地址

基本问题

封装成帧(framing)

一段数据的前后分别添加首部和尾部，构成一个帧。首部和尾部的一个重要作用就是进行帧定界

透明传输

“在数据链路层透明传送数据”,表示无论什么样的比特组合的数据都能够通过这个数据链路层

数据看不见数据链路层有什么妨碍数据传输的东西

数据链路层对于这些数据来说是透明的

• 解决透明传输问题

发送端的数据链路层在数据中出现控制字符“SOH”或“EOT”的前面插入一个转义字符“ESC”(其十六进制编码是 1B)。

字节填充(byte stuffing)或字符填充(character stuffing)——接收端的数据链路层在将数据送往网络层之前删除插入的转义字符。

如果转义字符也出现数据当中，那么应在转义字符前面插入一个转义字符。当接收端收到连续的两个转义字符时，就删除其中前面的一个。

差错检测

在传输过程中可能会产生比特差错：1 可能会变成0 ,而0也可能变成1

在一段时间内,传输错误的比特占所传输比特总数的比率称为误码率 BER (Bit Error Rate)

为了保证数据传输的可靠性,在计算机网络传输数据时,必须采用各种差错检测措施

2 PPP (Point-to-Point Protocol)

点对点协议 ，三个组成部分

• 一个将 IP 数据报封装到串行链路的方法。
• 链路控制协议 LCP (Link Control Protocol)。
• 网络控制协议 NCP (Network Control Protocol)。

3 透明传送,字节填充,零比特填充

• 字节填充

RFC1662规定的填充方法：

将信息字段中出现的每一个 0x7E 字节转变成为 2 字节序列(0x7D, 0x5E)。

若信息字段中出现一个 0x7D 的字节, 则将其转变成为 2 字节序列(0x7D, 0x5D)。

若信息字段中出现 ASCII 码的控制字符（即数值小于 0x20 的字符），则在该字符前面要加入一个 0x7D 字节，同时将该字符的编码加以改变。

• 零比特填充

• • PPP 协议用在 SONET/SDH 链路时，是使用同步传输（一连串的比特连续传送）。这时 PPP 协议采用零比特填充方法来实现透明传输。
  • 标志字段0x7E（二进制01111110）
  • 在发送端，只要发现有 5 个连续 1，则立即填入一个 0。接收端对帧中的比特流进行扫描。每当发现 5 个连续1时，就把这 5 个连续 1 后的一个 0 删除。

5 CRC差错检测，求冗余码

基于循环冗余检验(CRC)的差错检测技术

• 在发送端，先把数据划分为组。假定每组 k 个比特。
• 假设待传送的一组数据 M = 101001（现在 k = 6）。我们在 M 的后面再添加供差错检测用的 n 位冗余码一起发送。

冗余码的计算

• 用二进制的模 2 运算进行 2n 乘 M 的运算，这相当于在 M 后面添加 n 个 0。
  
• 得到的 (k + n) 位的数除以双方事先选定好的长度为 (n + 1) 位的除数 P，得出商是 Q 而余数是 R，余数 R 比除数 P 少1 位，即 R 是 n 位。
  
• 冗余码的计算举例

4 交换局域网

4.1 链路层寻址和ARP

4.2 以太网

4.2.1 概述

“统治地位”的有线LAN技术

• 造价低廉(NIC不足￥100.00)
  
• 应用最广泛的LAN技术
  
• 比令牌局域网和ATM等，简单、便宜
  
• 满足网络速率需求：10 Mbps – 10 Gbps
  
• Metcalfe的以太网草图
  

4.2.2 以太网：物理拓扑

总线(bus): 上世纪90年代中期前流行

• 所有结点在同一冲突域(collision domain) (可能彼此冲突)

星型(star)：目前主流网络拓扑

• 中心交换机(switch)
  
• 每个结点一个单独冲突域(结点间彼此不冲突)
  
• 总线(bus): 同轴电缆&&星型(star)

4.2.3 以太网：不可靠、无连接服务

无连接(connectionless)：发送帧的网卡与接收帧的网卡间没有“握手”过程。

不可靠(unreliable)：接收网卡不向发送网卡进行确认

• 差错帧直接丢弃，丢弃帧中的数据恢复依靠高层协议 (e.g., TCP)，否则，发生数据丢失。

以太网的MAC协议采用二进制指数退避算法的CSMA/CD。

4.2.4 CSMA/CD(Carrier Sense Multiple Access with Collision Detection)

协议的工作过程，最短帧长与争用期的关系(重点)

概念

载波监听多点接入/碰撞检测：

• 多点接入
  许多计算机以多点接入的方式连接在一根总线上
• 载波监听
  每一个站在发送数据之前先要检测一下总线上是否有其他计算机在发送数据，如果有，则暂时不要发送数据，以免发生碰撞
• 碰撞检测
  计算机边发送数据边检测信道上的信号电压大小

原理

载波监听

碰撞检测

随机退避

4.2.4.3 工作过程(从与广播信道相连的网卡角度)

1. NIC从网络层接收数据报，创建数据帧,并放入帧适配器缓存中
2. 监听信道：

• NIC监听到信道闲，则开始发送帧
• NIC监听到信道忙，则一直等待到信道闲，然后发送帧

发送过程中,NIC监视来自其他使用该广播信道的适配器的信号能量的存在(即边发送边检测)

3. 没有检测到其他结点的数据发送,NIC发送完整个帧,发送成功

4. 如果NIC检测到其他结点传输数据，则中止发送，并发送堵塞信号(jam signal)

5. 中止发送后，NIC进入二进制指数退避：

• 第m次连续冲突后：
  •取n = Min(m, 10)
  •NIC 从{0,1,2, …, 2n-1}中随机选择一个数K
  •NIC等待K·512比特的传输延迟时间，再返回第2步
  
• 连续冲突次数越多，平均等待时间越长。
  
• 争用期

• • 最先发送数据帧的站，在发送数据帧后至多经过时间 2 （两倍的端到端时延）就可知道发送的数据帧是否遭受了碰撞。
  • 以太网的端到端往返时延 2 称为争用期，或碰撞窗口。
  • 经过争用期这段时间还没有检测到碰撞，才能肯定这次发送不会发生碰撞
  • 长度
    以太网争用期的时间取为51.2微秒
    对于 10 Mb/s 以太网，在争用期内可发送512 bit，即 64 字节。因此，也可以说争用期是512比特时间。
    以太网在发送数据时，若前 64 字节没有发生冲突，则后续的数据就不会发生冲突

• 最短有效帧长

• • 如果发生冲突，就一定是在发送的前 64 字节之内
  • 以太网规定了最短有效帧长为 64 字节
  • 若要发送的数据非常少，则必须加入一些填充字节，使帧长不小于64字节
  • 凡长度小于 64 字节的帧都是由于冲突而异常中止的无效帧

4.2.5 以太网帧结构

发送端网卡将IP数据报(或其他网络层协议分组)封装到以太网帧中：

各个字段意义

• 前导码(Preamble)(8B):

• • 7个字节的10101010，第8字节为10101011
  • 用于发送端与接收端的时钟同步

• 目的MAC地址、源MAC地址(各6B):

• • 如果网卡的MAC地址与收到的帧的目的MAC地址匹配，或者帧的目的MAC地址为广播地址(FF-FF-FF-FF-FF-FF)，则网卡接收该帧，并将其封装的网络层分组交给相应的网络层协议
  • 否则，网卡丢弃(不接收)该帧

• 类型(Type)(2B): 指示帧中封装的是哪种高层协议的分组 (如，IP数据报、Novell IPX数据报、AppleTalk数据报等)
  
• 数据(Data)(46-1500B): 指上层协议载荷

• • R=10Mbps，RTTmax=512μs，Lmin / R = RTTmax
  • Lmin=512bits=64B，Datamin=Lmin-18=46B

• CRC(4B): 循环冗余校验码

• • 丢弃差错帧