第五章 数据链路层与局域网

{
数据链路层服务
差错控制
多路访问控制协议
局域网
点对点链路协议
}

数据链路层提供的服务内容

结点：主机、路由器。
链路：网络中两个结点之间的物理通道，链路的传输介质主要有双绞线、光纤。可以分为有线链路和无线链路。
数据链路：网络中两个结点之间的逻辑通道，把实现控制数据传输协议的硬件和软件加到链路上就构成数据链路。

数据链路层：负责通过一条链路，从一个结点向另一个物理链路直接相连的相邻结点，传送网络层数据报，中间不经过任何其他交换结点。

数据链路在物理链路之上，基于通信协议来控制数据帧传输的逻辑数据通路，实现数据链路层协议的典型硬件实体是：网络适配器（NIC,网卡）

数据链路层的传输单元称为帧。
数据链路层提供的服务：组帧、链路接入、可靠交付、差错控制。

1）组帧
帧头(帧首)：发送结点和接收结点的地址信息、定界字符。
帧尾：用于差错检测的差错编码。

2）链路接入
物理链路可以分为点对点链路和广播链路。
点对点链路：发送结点和接收结点独占信道。
广播链路：通信链路被多个结点共享。

3）可靠交付
无线链路（出错率高）：支持可靠数据传输。
光纤、双绞线（出错率低）：不提供可靠数据传输服务。

4）差错控制
数据链路层帧在物理媒介上的传播过程，可能会出现比特翻转的差错。
误比特率：出现差错的比特数/传输比特总数

差错控制

{
差错控制的基本方式
差错控制的基本原理
差错控制的检错与纠错能力
典型的差错编码
}

差错控制的基本方式

信号在信道传输过程中，会受到各种噪声的干扰，从而导致传输差错。
随机噪声——随机差错或独立差错
冲击噪声——突发差错。
通常是连续或成片的信息差错，差错之间具有相关性，差错通常集中发生在某段信息。突发错误发生的第一位错误与最后一位错误之间的长度称为突发长度。

差错控制：通过差错编码技术，实现对信息传输差错的检测，并基于某种机制运行差错纠正和处理。

基本方式： 检错重发、前向纠错、反馈校验、检错丢弃。

一、检错重发：利用差错编码。 （重发数据加以纠正 ）
发送端：待发送数据进行差错编码，然后发送。
接收端：利用差错编码检测数据是否出错。若出错，接收端请求发送端重发数据加以纠正。

二、前向纠错(Forward Error Correction，FEC )：利用纠错编码。 （检错、定位、纠正。 ）
发送端：对数据进行纠错编码，然后发送。 接收端：收到数据，利用纠错编码进行差错检测，且纠错。 适用：单工链路、对实时性要求比较高的应用。

三、反馈校验：（数据返回）
接收端：将收到的数据原封不动发回发送端。
发送端：通过对比接收端反馈的数据与发送的数据确认接收端是否正确接收的已发送数据。若有不同，立即重传数据。
优点：原理简单，易于实现，无须差错编码；
缺点：需要相同传输能力的反向信道，传输效率低，实时性差。

四、检错丢弃：(实时性较高的系统 )
网络应用对可靠性要求不高，可以采用不纠正出错数据，直接丢弃错误数据。适用于实时性较高的系统。

差错编码的基本原理

香农信道编码定理指出：对于一个给定的有干扰信道，只要发送端以低于信道容量C的数据速率R发送信息，则一定存在一种编码方法，使得编码错误概率P随着码长n的增加而按指数下降至任意小的值。

差错编码原理：在待传输(或待保护)数据信息基础上，附加一定的冗余信息，该冗余信息建立起数据信息的某种关联关系，将数据信息以及附加的冗余信息一同发送到接收端，接收端可以检测冗余信息表征的数据信息的关联关系是否存在。如果存在则没有错误，否则就有错误。

例如：发送端向接收端发送2位数据信息，如果不进行差错编码，则接收端可能接收到00、01、10、11。
如果进行差错编码：
增加2位冗余信息，
冗余信息：对数据的复制。
经过差错编码后，4个码字分别为： 0000、0101、1010、1111 接收端收到码字后，如果发生了1位差错，比如收到1011，10和11不满足复制关系，则断定出现差错。

差错控制的检错与纠错能力

不同差错编码的检错和纠错能力不同。
差错编码的检错或纠错能力与编码集的汉明距离有关。
汉明距离：两个等长码字之间，对应位数不同的位数。
0 1 1 0 0 1 0 1
1 0 0 1 1 1 0 1
汉明距离dc=5

编码集：差错编码的所有有效码字的集合。
编码集的汉明距离：编码集中任意两个码字之间汉明距离的最小值，记为ds
编码集{10000111，10010110，10100101，10110100}
ds=min{2，2，4，4，2，2}
ds＝2

1）对于检错编码，编码集的汉明距离ds=r+1，则该差错编码可以检测r位的差错。
例：发送2位数据信息，差错编码采取一次重复码(冗余信息是数据的一次复制) 编码集{0000，0101，1010，1111}（下划线位为冗余信息） ds=2，因此可以检测出来1位差错。

2）对于纠错编码，如果编码集的汉明距离ds=2r+1，则该差错编码可以纠正r位的差错。
例：发送2位数据信息，差错编码采取二次重复码(冗余信息是数据的两次复制) 编码集{000000，010101，101010，111111}（下划线位为冗余信息）
ds=3，因此可以检测出来1位差错。

几种典型的差错编码：奇偶校验码、循环冗余码 。
“异或”逻辑运算：符号
位值相同，结果为0： 1异或1=0；0异或0=0
位值不相同，结果为1： 1异或0=1；0异或1=1

奇偶校验码：最简单的检错码。利用1为冗余信息实现差错检测。
分类：奇校验码、偶校验码。
1、奇校验码编码过程：1位冗余位的取值为“0”或“1”，使得编码后的码字中1的个数为奇数，满足下列式子：
例如：数据10110111，采用奇校验码编码后的码字位：101101111

奇偶校验码
优点：编码简单、编码效率高、开销最小的检错编码；
缺点：检错率不高。

二、循环冗余码（Cyclic Redundancy Check,CRC码）：在数据链路层广泛应用的差错编码。

基本思想：将二进制位串看成是系数为0或1的多项式的系数。
例如：100101有6位，写成一个多项式。位串的数字就是每个多项式的系数。
备注：任何数的0次方，均为1。
多项式：1x5+0x4+0x3+1x2+0x1+1x0=x5+x2+1

例：假设CRC编码采用的生成多项式G(x)=x4+x+1，请为位串10111001进行CRC编码

第一步：写出多项式对应的位串：10011（5位）
第二步：5-1的值是我们需要在待编码位串后面添加0的个数：添加4个0待编码位串： 10111001——101110010000
第三步：用得到的新的待编码位串(101110010000)除以多项式对应的比特串(10011)。

“异或”逻辑运算 位值相同，结果为0； 位值不相同，结果为1；

第四步：求得的余数(1001)添加在待编码位串后，即为CRC编码后的码 101110011001

多路访问控制协议

{
信道划分mac协议
随机访问mac协议
受控接入mac协议
}

数据链路层使用的信道：
方式一：点对点信道，一对一通信方式，信道被双方独享。
方式二：广播信道，一对多通信方式，信道上连接的点很多，信道被结点共享。多路访问控制(Multiple Access Control,MAC)协议来协调结点的数据发送。

多路访问控制的内容：采取一定的措施，使得结点之间的通信不会发生干扰的情况。

信道划分mac协议

MAC协议的根本任务：解决信道的共享问题。
多路复用技术是实现物理信道共享的经典技术。
多路复用的基本思想：将信道资源(频域、时域、波长、编码)划分后，分配给不同的结点，各结点通信时只使用其分配到的资源，从而实现了信道共享，并避免了多结点通信时的相互干扰。
信道划分MAC协议：利用多路复用技术实现信道共享的MAC协议。

一、频分多路复用（Frequency-division multiplexing，FDM） ：也称频分复用。频域划分制，在频域内将信道带宽划分为多个子信道，并利用载波调制技术，将原始信号调制到对应的某个子信道的载波信号上，使得同时传输的多路信号在整个物理信道带宽的允许范围内频谱不重叠，从而共用一个信道。

一、频分多路复用FDM
优点：分路简单，目前模拟通信中长采用，特别是有线和微波通信。
缺点：
信号之间相互干扰，即串扰；
所需设备随输入路数增大而增多；
不提供差错检测，不便于性能监测。

二、时分多路复用（Time-Division Multiplexing，TDM）:也称时分复用。时域划分制，将通信信道的传输信号在时域內划分为多个等长的时隙，每路信号占用不同的时隙，在时域上不重叠，使多路信号合用单一的通信信道，从而实现信道共享。TDM系统的接收端，根据各路信号在通信信道上所占用的时隙分离、还原信号。

二、时分多路复用（TDM）
1、同步时分多路复用(Synchronism Time-Division Multiplexing,STDM)
按照固定顺序把时隙分配给各路信号。
2、异步时分多路复用(Asynchronism Time-Division Multiplexing,ATDM)
统计时分多路复用(Statistic Time-Division Multiplexing,STDM)
大量数据发送的用户分配较多的时隙，不保证每个用户得到固定的时隙。时隙和用户间没有固定的对应关系。

三、波分多路复用（ Wave Division Multiplexing, WDM）：也称波分复用，广泛用于光纤通信。实质是一种频分多路复用。因在光纤通信中，光载波频路很高，通常用光的波长来代替频率讨论，所以叫做波分多路复用。 波分多路复用是指在一根光纤中，传输多路不同波长的光信号，由于波长不同，所以各路光信号互不干扰，最后利用波长解复用器将各路波长的光载波分解出来。
在光纤通信中，为了实现长距离的高速传输，通常采用波分多路复用和光纤放大器。

四：码分多路复用（Code Division Multiplexing, CDM）：又称码分复用，通过利用更长的相互正交的码组分别编码各路原始信息的每个码元，使得编码后的信号在同一信道中混合传输，接收端利用码组的正交特性分离各路信号，从而实现信道共享。是一种扩频的通信形式。
相互正交：
码组1：{1,0,1}
码组2：{0,1,0}
1×0+0×1+1×0=0

随机访问MAC协议

随机访问MAC协议：所有用户都可以根据自己的意愿随机地向信道上发送信息。没有其他用户：发送成功。 有两个或两个以上用户都发送信息：产生冲突或碰撞，用户发送信息失败。每个用户随机退让一段时间后，再次尝试，直至成功。

有两个或两个以上用户都发送信息：产生冲突或碰撞，用户发送信息失败。每个用户随机退让一段时间后，再次尝试，直至成功。

一、ALOHA协议：最早的，最基本的无线数据通信协议。
ALOHA协议分类：纯ALOHA、 时隙ALOHA 。（只说不听 ）
1、纯ALOHA工作原理：
任何一个站点有数据发送时就可以直接发送至信道。 发送数据后对信道进行侦听：
如果收到应答信号，说明发送成功；
否则说明发生冲突，等待一个随机时间重新发送，直到成功为止。

1、纯ALOHA的性能
G网络负载：表示在一帧的发送时间内发送的平均帧数。
S吞吐率：在一帧的发送时间内成功发送的平均帧数。

网络负载不能大于0.5

2、时隙ALOHA：把信道时间划分为离散的时隙，每个时隙为发送一帧所需的时间，每个通信站点只能在每个时隙开始的时刻发送帧。如果在一个时隙内发送帧出现冲突，下一个时隙以概率p重发该帧，直到帧发送成功。p不能为1，否则会出现死锁。 死锁：僵持。

1、时隙ALOHA性能 G：网络负载 S：吞吐率

二、载波监听多路访问协议(先听后说) （Carrier Sense Multiple Access,CSMA） 通过硬件装置，即载波监听装置，使通信站发送数据之前，监听信道上其他站点是否在发送数据，如果在发送，则暂时不发送。 根据监听策略不同：非坚持CSMA；1-坚持CSMA；P-坚持CSMA

三、带冲突检测的载波监听多路访问协议（先听后说，边听边说） （Carrier Sense Multiple Access/Collision Detection,CSMA/CD） 基本原理：通信站使用CSMA协议进行数据发送；在发送期间如果能检测到碰撞，立即终止发送，并发出一个冲突强化信号，使所有通信站点都知道冲突的发生。 发出冲突强化信号后，等待一个随机时间，再重复上述过程。

工作状态分为：传输周期、竞争周期、空闲周期。 信道有3种状态：传输状态、竞争状态、空闲状态。

在使用CSMA/CD协议实现多路访问控制时，需要满足下列约束关系：

受控接入MAC协议

{
集中式控制
分散式
}
受控接入：各个用户不能随意的接入信道而必须服从一定的控制，分为集中式控制和分散式控制。

一、集中式控制：系统有一个主机负责调度其他通信站接入信道，从而避免冲突。方法：轮询。

二、分散式控制：方法是令牌技术。
令牌是一种特殊的帧，代表了通信站使用信道的许可。在信道空闲时一直在信道上传输。一个通信站想要发送数据就必须首先获得令牌。

令牌环的操作过程：
1、网络空闲时，只有一个令牌在环路上绕行。
2、当一个站点要发送数据时，必须等待并获得一个令牌，将令牌的标志位置为“1”，随后便可发送数据。
3、环路中的每个站点边转发数据，边检查数据帧中的目的地址，若为本站点的地址，便读取其中所携带的数据。 4、数据帧绕环一周返回时，发送站将其从环路上撤销，即“自生自灭”。
5、发送站点完成数据发送后，重新产生一个令牌传至下一个站点，以使其他站点获得发送数据帧的许可权。

令牌丢失和数据帧无法撤销是环网上最严重的两种错误。

局域网

{
数据链路层寻址与ARP
以太网
交换机
虚拟局域网
}

局域网(LAN)：一般采取广播的方式，局部区域网络，覆盖面积小，网络传输 速率高，传输的误码率低。

为了使数据链路层更好地适应多种局域网标准，IEEE802委员会将局域网的数据链路层拆分为两个子层：
逻辑链路控制(Logical Link Control ,LLC)子层（名存实亡）
介质访问控制MAC子层

数据链路层寻址与ARP

一、MAC地址(物理地址、局域网地址)：MAC地址具有唯一性，每个接口（网络适配器）对应一个MAC地址。
1、以太网和IEEE 802.11无线局域网，使用的MAC地址长度为6字节。共有2^48个可能的MAC地址。
6字节的MAC地址通常采用十六进制表示法，每个字节表示一个十六进制数， 用 -或:连接起来。
例如：00-2A-E1-76-8C-39 或 00:2A:E1:76:8C:39
补充：十六进制：1,2,3,4,5,6,7,8,9,A,B,C,D,E,F

2、MAC地址空间的分配由电气和电子工程师协会( Institute of Electrical and Electronics Engineers，IEEE)统一管理。 2^24的MAC地址块，自己分配后24位。

3、MAC广播地址 FF-FF-FF-FF-FF-FF

二、地址解析协议（ Address Resolution Protocol ,ARP）：根据本网内目的主机的或默认网关的IP地址获取其MAC地址。

地址解析协议(ARP) ARP的基本思想：在每一台主机中设置专用内存区域，称为ARP高速缓存(也称为ARP表)，存储该主机所在局域网中其他主机和路由器的IP地址与MAC地址的映射关系，并且这个映射表要经常更新。ARP通过广播ARP查询报文，来询问某目的IP地址对应的MAC地址，即知道本网内某主机的IP地址， 可以查询得到其MAC地址。

以太网

以太网：是到目前为止最流行的有线局域网技术，几乎占领着现有的有线 局域网市场。(IEEE802.3)

一、以太网成功的原因：
1、以太网是第一个广泛部署的高速局域网。
2、令牌环网、FDDI、ATM比以太网更加复杂、昂贵。
3、以太网在数据速率方面比FDDI、ATM毫不逊色。
4、以太网硬件价格极其便宜，网络造价成本低。

二、经典的以太网是采用粗同轴电缆连接的总线型以太网（10Base-5）
1、数据传输速率为10Mbit/s，无连接不可靠。
2、在一个冲突域中传播时延为51.2μs,所以以太网最短帧长为64字节。
3、网段和网段之间用中继器连接，最多有4个中继器。
4、MAC协议采用CSMA/CD协议。

以太网帧结构

除数据部分：18字节。 以太网帧最短64字节，那么数据字段最短46字节。

1、目的地址和源地址：MAC地址；
2、类型：标识上层协议。0x0800：IP数据报；
3、数据：封装的上层协议的分组；
4、CRC：校验采用循环冗余校验。

以太网技术

一、交换机：应用最广泛的数据链路层设备

以太网交换机的自学习
1、以太网交换机有4个端口，各连接一台计算机，其MAC地址分别是ABCD。
2、一开始，以太网交换机里面的转发表是空白的。
3、A向B发送一个帧，从端口1进入交换机。
4、交换机先查询转发表，没找到往哪里转发该帧。
5、交换机就把这个帧的源MAC地址A和端口1写入交换表，完成第一次学习。
6、除向端口1以外所有端口泛洪(广播)这个帧。

以太网交换机的优点 ：
消除冲突、支持异质链路 、网络管理 。

虚拟局域网：
虚拟局域网(Virtual Local Area Network,VLAN) 虚拟局域网是一种基于交换机（必须支持VLAN功能）的逻辑分割（或限制）广播域的局域网应用形式。以软件的方式划分和管理局域网中的工作组，限制接收广播信息的主机数，不会因为传播过多的广播信息而引起性能的恶化。

划分虚拟局域网的方法：
基于交换机端口划分
基于mac地址划分
基于上层协议的地址及类型划分

点对点链路协议

{
点对点协议（PPP）
HDLC协议
}

点对点协议(Point to Point Protocol,PPP)：全世界使用得最多的点对点链路协议。

PPP主要提供3类功能：
1）成帧：确定一帧的开始和结束，支持错误检测。
2）链路控制协议(Link Control Protocol,LCP)
启动线路、检测线路、协商参数、关闭线路。
3）网络控制协议(Network Control Protocol,NCP): 协商网络层选项

不要求PPP实现的功能：
1）差错纠正 2）流量控制 3）按序交付

PPP提供透明传输服务
无论上层协议的分组中包含什么样的位串或字节，都应该能够通过PPP传输。 使用字节填充(Byte Stuffing)技术。

PPP协议的帧格式（7或8或9或10 + 信息长度）

HDLC协议

高级数据链路控制(High-level Data Link Control,HDLC)：应用于点对点链路和点对多点链路，面向位的协议。

HDLC帧格式 （固定的字节数有6个字节）