计算机网络之数据链路层(全)

[复习提示]

王道：本章是历年考试中考查的重点。要求在了解数据链路层基本概念和功能的基础上，重点掌握滑动窗口机制、三种可靠传输协议、各种MAC协议、HDLC协议和PPP协议，特别是CSMA/CD协议和以太网帧格式，以及局域网的争用期和最小帧长的概念、二进制指数退避算法。此外，中继器、网卡、集线器、网桥和局域网交换机的原理及区别也要重点掌握。

一、数据链路层的功能

• 为网络层提供服务
• 链路管理
• 帧定界、帧同步与透明传输
• 流量控制（对发送方控制）
• 差错控制

注：

为网络层提供服务

1. 无确认的无连接服务。
2. 有确认的无连接服务。
3. 有确认的面向连接服务。 

无确认的无连接服务是指源机器向目标机器发送独立的帧，目标机器并不对这些帧进行确认。 事先并不建立逻辑连接，事后也不用释放逻辑连接。当错误率很低时，这一类服务非常合适，这时恢复任务可以留给上面的各层来完成。这类服务对于实时通信也是非常合适的，因为实时通信中数据的迟到比数据损坏更不好。若由于线路上有噪声而造成某一帧丢失，则数据链路层并不会检测这样的丢帧现象，也不会回复。

• 为防止在传输过程中帧丢失，在可靠的数据链路层协议中，发送方对发送的每个数据帧设计一个定时器，当计时器到期而该帧的确认帧仍未到达时，发送方将重发该帧。
• 为保证接收方不会接收到重复帧，需要对每个发送的帧进行编号；
• 海明码和循环冗余校验码都用于差错控制。
• 为终端结点隐蔽物理传输的细节是物理层的功能，数据链路层不必考虑如何实现无差别的比特传输；

二、组帧

组帧的目的：是为了在出错时只重发出错的帧，而不必重发全部数据，从而提高效率。

• 字符计数法（如：第一个帧：51239，第二个帧：7123456。。。）
• 字符填充的首尾定界符法
• 零比特填充的首尾标志法（遇到5个“1”后，就插入一个“0”）
• 违规编码法

 字符计数法

违规编码法： 在物理层进行比特编码时，通常采用违规编码法。例如，曼彻斯特编码方法将数据比特“1”编码成“高一低”电平对，将数据比特“0”编码成“低一高”电平对，而“高一高”电平对和“低一低”电平对在数据比特中是违规的（即没有采用）。

三、差错控制

实际通信链路都不是理想的，比特在传输过程中可能会产生差错，1可能会变成0，0也可能会变成1，这就是比特差错。比特差错是传输差错中的一种，本节仅讨论比特差错。

检错编码 

• 奇偶校验码（附加一个校验元后，数量为奇数个或偶数个）
• 循环冗余码（CRC）

CRC

计算实际发送的数据：

1）为原始数据M0加0（加r位）;

2）加0后的原始数据模2除以G(x)位串；

3）用结果的余数替代1）中加的0; 

校验是否出错：

1）用收到的二进制序列模2除以G(x)位串；

2）余数为0则没有出错；

正向例题：设G(x)=1101（即r=3)，待传送数据M=101001（即m=6)

101001000 

发送出的数据为： 101001001,共有m+r位。

反向例题：在数据传输过程中，若接收方收到的二进制比特序列为10110011010，接收双方采用的生成多项式为G(x)=x^4+x^3+1,则该二进制比特序列在传输中是否出错？如果未出现差错，那么发送数据的比特序列和CRC检验码的比特序列分别是什么？

 G(x)=1*x^4+1*x^3+0*x^2+0*x^1+1*x^0

纠错编码 

•  海明码

效信息的位数：n，

校验位的位数：k，

n+k≤2^k-1（若要检测两位错，则需再增加1位校验位，即k+1位）

海明距离：两个合法编码（码字）的对应比特取值不同的比特数称为这两个码字的码距 （如001和000的码距是1）

检测D位错，需要码距D+1

纠错D位，需要码距2D+1

一般来说，数据的传输差错是由噪声引起的。通信信道的噪声可以分为两类:热噪声和冲击噪声。热噪声一般是信道固有的，引起的差错是随机差错，可以通过提高信噪比来降低它对数据传的影响。冲击噪声一般是由外界电磁干扰引起的，引起的差错是突发差错，它是引起传输差错的主要原因，无法通过提高信噪比来避免。

四、流量控制与可靠传输机制

• 停止-等待流量控制
• 滑动窗口流量控制
• 可靠传输机制 

停止-等待流量控制：发送方每发送一帧，都要等待接收方的应答信号，之后才能发送下一帧；

在连续ARQ协议中，发送窗口的大小≤窗口总数-1。

滑动窗口流量控制：

• 停止-等待协议：发送窗口大小=1，接收窗口大小=1。
• 后退N帧协议（GBN）：发送窗口大小>1，接收窗口大小=1。
• 选择重传协议（SR）：发送窗口大小>1，接收窗口大小>1。
• 接收窗口的大小为1时，可保证帧的有序接收。
• 发送窗口+接收窗口≤帧序号

可靠传输机制 ：

• 确认
• 重传

信道最大利用率例题：一个信道的数据传输速率为4kb/ s ，单向传播时延为30ms，如果使停止﹣等待协议的信道最大利用率达到80%，那么要求的数据帧长度至少为（)。
(L/C) / (L/C+ 2R)= L/(L+ 2RC)= L/(L + 2x30msx4kb/s)= 80%，得出L = 960bit。

GBD

• GBN一般采用累积确认，如果收到了对5号帧的确认意味着接收方已收到1~5号帧，因此发送方仅需要重传后面的帧
• 在后退N帧的协议中，序列号个数不小于MAX_ SEQ+ 1,题中发送窗口的大小是32,那么序列号个数至少33个
• 后退N帧的ARQ协议中，发送窗口WT≤(2^n)-1。

SR

• 在选择重传协议中，若采用n比特对帧进行编号，为避免接收端向前移动窗口后，新的窗口
  与旧的窗口产生重叠，接收窗口的最大尺寸应该不超过序号范围的一半，即WR≤2^(n-1)
• 数据链路层采用选择重传协议(SR)传输数据，发送方已发送0~3号数据帧，现已收到1号帧的确认，而0、2号帧依次超时，则此时需要重传的帧数是(2)。重传0和2

五、介质访问控制 

采用一定的措施，使得两对节点之间的通信不会互相干扰。

信道划分介质访问控制 （静态分配信道）

• 频分多路复用/ FDM（类似并行）
• 时分多路复用/ TDM（类似并发）
• 波分多路复用/ WDM（光的频分多路复用）
• 码分多路复用/ CDM（主要用于无线通信系统，特别是移动通信系统。)

没有码分多路复用

 TDM与FDM相比，抗干扰能力强，可以逐级再生整形，避免干扰的积累，而且数字信号比较容易实现自动转换，所以根据FDM和TDM的工作原理，FDM适合于传输模拟信号，TDM适合于传输数字信号。

 随机访问介质访问控制（动态分配信道）

所有用户可随机发送信息。发送信息时占全部带宽。

• ALOHA协议
• CSMA协议
• CSMA/CD协议
• CSMA/CA协议 
• 轮询访问：令牌传递协议（谁有令牌谁老大）

ALOHA协议

• 纯 ALOHA协议
• 时隙ALOHA协议。

CSMA协议

• 1-坚持CSMA(监听到信道忙后，继续坚持监听信道；监听到信道空闲后，发送帧的概率为1，即立刻发送数据。)
• 非坚持CSMA(一个结点要发送数据时，首先监听信道；如果信道空闲，那么立即发送数据；如果信道忙，那么放弃监听，等待一个随机的时间后再重复上述过程。)
• p-坚持CSMA( p,1-p,p,1-p )

CSMA/CD协议

• 适用于总线型网络和半双工网络
• “先听后发，边听边发，冲突停发，随机重发”。
• 碰撞检测（Collision Detection)就是边发送边监听，如果监听到了碰撞，则立即停止数据发送，等待一段随机时间后，重新开始尝试发送数据。
• CSMA/CD协议中定义的冲突检测时间(即争议期)是指，信号在最远两个端点之间往返传输的时间。
• 最短帧长等于争用期时间内发出的比特数。因此当传输速率提高时，可减少电缆介质的长度(使争用期时间减少，即以太网端到端的时延减小)，或增加最短帧长。
• 最小帧长=总线传播时延x数据传输速率x2
• CSMA/CD协议已成功应用于使用有线连接的局域网

 CSMA/CD协议  

• 广泛应用于无线局域网

以太网的二进制回退算法：一般来说， 在第i (i<10)次碰撞后，站点会在0到2^i-1中之间随机选择一个数M，然后等待M倍的争用期再发送数据。在达到10次冲突后，随机数的区间固定在最大值1023上，以后不再增加。如果连续超过16次冲突，那么丢弃。

CSMA/CD与CSMA/CA主要区别：

• CSMA/CD可以检测冲突，但无法避免；CSMA/CA发送数据的同时不能检测信道上有无冲突，本结点处没有冲突并不意味着在接收结点处就没有冲突，只能尽量避免。
• 传输介质不同。CSMA/CD用于总线形以太网，CSMA/CA用于无线局域网802.11a/b/g/n等。
• 检测方式不同。CSMA/CD通过电缆中的电压变化来检测；而CSMA/CA采用能量检测、载波检测和能量载波混合检测三种检测信道空闲的方式。
• 总结：CSMA/CA协议的基本思想是在发送数据时先广播告知其他结点，让其他结点在某段时间内不要发送数据，以免出现碰撞。CSMA/CD协议的基本思想是发送前监听，边发送边监听，一旦出现碰撞马上停止发送。

六、局域网

基础概念

局域网的主要特点如下:

• 为一个单位所拥有，且地理范围和站点数目均有限。
• 所有站点共享较高的总带宽( 即较高的数据传输速率)。
• 较低的时延和较低的误码率。
• 各站为平等关系而非主从关系。
• 能进行广播和组播。

局域网常见拓扑结构：

• ①星形结构;
• ②环形结构;
• ③总线形结构;
• ④星形和总线形结合的复合型结构。

三种特殊的局域网拓扑实现如下:

• 以太网(目前使用范围最广的局域网)。逻辑拓扑是总线形结构，物理拓扑是星形或拓展星形结构。
• 令牌环(Token Ring, IEEE 802.5)。 逻辑拓扑是环形结构，物理拓扑是星形结构。
• FDDI (光纤分布数字接口，IEEE 802.8)。 逻辑拓扑是环形结构，物理拓扑是双环结构。

以太网与IEEE 802.3

IEEE802.3标准是一种基带总线形的局域网标准，它描述物理层和数据链路层的MAC子层的实现方法。

以太网采用两项措施以简化通信：①采用无连接的工作方式，不对发送的数据帧编号，也不要求接收方发送确认，即以太网尽最大努力交付数据，提供的是不可靠服务，对于差错的纠正则由高层完成；②发送的数据都使用曼彻斯特编码的信号，每个码元的中间出现一次电压转换，接收端利用这种电压转换方便地把位同步信号提取出来。

1.以太网的传输介质与网卡

以太网常用的传输介质有4种：粗缆、细缆、双绞线和光纤。

2.以太网的MAC帧 

• 以太网的MAC协议提供无连接的不可靠服务
• 全世界的每块网卡在出厂时都有一个唯一的代码，称为介质访问控制（MAC）地址，这个地址用于控制主机在网络上的数据通信。
• 12个十六进制数表示，如02-60-8c-e4-b1-21，高24位为厂商代码，低24位为厂商自行分配
• 地址：通常使用6字节（48bit）地址（MAC地址）。
• 类型：2字节，指出数据域中携带的数据应交给哪个协议实体处理。
• 数据：46～1500字节，包含高层的协议消息。由于CSMA/CD算法的限制，以太网帧必须满 
• 填充：0~46字节，当帧长太短时填充帧，使之达到64字节的最小长度。
• 校验码(FCS)：4字节，校验范围从目的地址段到数据段的末尾，算法采用32位循环冗余码（CRC），不但需要检验MAC帧的数据部分，还要检验目的地址、源地址和类型字段，但不校验前导码。

 3.高速以太网

快速以太网仍然使用CSMA/CD协议，它采用（保持最短帧长不变）而将最大电缆长度减少到100m的方法，使以太网的数据传输速率提高至100Mb/s。

速率达到或超过100Mb/s的以太网称为高速以太网。

• （1）100BASE-T以太网（以太网是在双绞线上传送100Mb/s基带信号的星形拓扑结构以太网）
• （2）吉比特以太网
• （2）10吉比特以太网 （光纤）

	是否工作在全双工	是否工作在半双工	速度	是否使用CSMA/CD
100BASE-T以太网	√	√	100Mb/s	在半双工方式下使用（全双工方式不需要）
吉比特以太网	√	√	1Gb/s	在半双工方式下使用（全双工方式不需要）
10吉比特以太网	√	×	10Gb/s	不用

吉比特以太网的物理层有两个标准：IEEE 802.3z和IEEE 802.3ab，前者采用光纤通道，后者采用4对UTP5类线。 

IEEE802.11无线局域网

1.无线局域网的组成

有固定基础设施无线局域网

• CSMA/CA协议
• Wi-Fi
• 无线局域网的基本服务区的范围直径一般不超过100m
• 802.11使用星形拓扑，其中心称为接入点（Access Point,AP）

无固定基础设施移动自组织网络

•  自组网络
• 没有AP
• 各结点之间地位平等，中间结点都为转发结点，因此都具有路由器的功能。
• 由移动站构成的网络拓扑可能随时间变化得很快，因此在固定网络中行之有效的一些路由选择协议对移动自组网络已不适用，需引起特别的关注

2.802.11局域网的MAC帧

• 1)MAC首部，共30字节。帧的复杂性都在MAC首部。
• 2)帧主体，即帧的数据部分，不超过2312字节。它比以太网的最大长度长很多。
• 3）帧检验序列FCS是尾部，共4字节。

 VLAN-虚拟局域网

 一般有三种划分VLAN的方法

• ①基于端口，将交换机的若干端口划为一个逻辑组，这种方法最简单、最有效，如果主机离开了原来的端口，那么就可能进入一个新的子网。
• ②基于MAC地址，按MAC地址将一些主机划分为一个逻辑子网，当主机的物理位置从一个交换机移动到另一个交换机时，它仍然属于原来的子网。
• ③基于IP地址，根据网络层地址或协议划分VLAN，这样VLAN就可以跨越路由器进行扩展，将多个局域网的主机连接在一起。

 VLAN建立在交换技术基础上，以软件方式实现逻辑分组与管理，VLAN中的计算机不受物理位置的限制。当计算机从一个VLAN转移到另一个VLAN时，只需简单地通过软件设定，而无需改交在网络中的物理位置。同一个VLAN的计算机不一定连接在相同的物理网段，它们可以连接在相同的交换机上，也可以连接在不同的局域网交换机上，只要这些交换机互连即可。

广域网

• 广域网不等于互联网。互联网可以连接不同类型的网络(既可以连接局域网，又可以连接广域网)，通常使用路由器来连接。广域网是单一的网络，通常使用结点交换机连接各台主机(或路由器)，而不使用路由器连接网络。其中结点交换机在单个网络中转发分组，而路由器在多个网络构成的互联网中转发分组。
• 广域网的通信子网主要使用分组交换技术，将分布在不同地区的局域网或计算机系统互连起
  来，达到资源共享的目的。
• 广域网所使用的传输方式是(存储转发式)。
• TCP/IP协议族主要包括TCP、IP、 ICMP、IGMP、ARP、RARP、UDP、DNS、FTP、HTTP等。
   

PPP协议 

PPP协议有三个组成部分:

1)链路控制协议(LCP)。 一种扩展链路控制协议，用于建立、配置、测试和管理数据链路。
2)网络控制协议(NCP)。PPP协议允许同时采用多种网络层协议，每个不同的网络层协议
要用一个相应的NCP来配置，为网络层协议建立和配置逻辑连接。
3) 一个将IP数据报封装到串行链路的方法。IP数据报在PPP帧中就是其信息部分，这个信
息部分的长度受最大传送单元(MTU)的限制。

PPP是一-种面向字节的协议，所有的帧长度都是整数个字节，使用一种特殊的字符填充法完
成数据的填充。

PPP协议的特点: 

1) PPP提供差错检测但不提供纠错功能，只保证无差错接收(通过硬件进行CRC校验)。它是不可靠的传输协议，因此也不使用序号和确认机制。
2)它仅支持点对点的链路通信，不支持多点线路。
3) PPP只支持全双工链路。
4) PPP 的两端可以运行不同的网络层协议，但仍然可使用同一个PPP进行通信。
5) PPP是面向字节的，当信息字段出现和标志字段一致的比特组合时，PPP有两种不同的处理方法:若PPP用在异步线路(默认)，则采用字符填充法；若PPP用在SONET/SDH等同步线路，则协议规定采用硬件来完成比特填充(和HDLC的做法一样)。

数据链路层设备

交换机（就是多端口网桥）

• 就传播时延而言：路由器> 交换机 >集线器
• 局域网交换机实现的主要功能在物理层和数据链路层 
• 交换机能隔离冲突域，工作在全双工状态，使网络中多对结点同时通信（支持多用户同时通信），提高了网络的利用率，这是交换机的优点。
• 一个交换机，对于10Mb/s 的半双工端口，端口带宽为10Mb/s；若端口速率保持不变，则全双工端口带宽为20Mb/s。
• 在使用以太网交换机( 默认工作在全双工)来连接这些主机，虽然在每个端口到主机的带宽还是10Mb/s,但由于一个用户在通信时是独占而不是和其他网络用户共享传输媒体的带宽，因此拥有N个端口的交换机的总容量为Nx10Mb/s。
• 若是半双工交换机,因此拥有N对10Mb/s端口的半双工交换机的总容量为Nx 10Mb/s，其中N =24/2=12， 总容量为120Mb/s