0.本章思维导图：
数据链路层使用的信道：
点对点信道：使用一对一的点对点通信方式
广播信道：使用一对多的广播通信方式，过程比较复杂，需要专用的协议来协调
1.使用点对点信道的数据链路层
1.1数据链路和帧
链路(物理链路)：从一个结点到相邻结点的一段物理线路，中间没有任何其他的交换节点
链路是一条路径的一个组成部分：两台计算机之间的通信路径需要许多链路
数据链路(逻辑链路)：把实现了这些通信协议的硬件和软件加到链路上，就构成了数据链路(物理线路+协议)
网络适配器：既有硬件也包括软件，实现了通信协议，包括了数据链路层和物理层两层的功能
规程：数据链路层中，规程等同于协议
帧：点对点信道数据链路层的协议数据单元
数据链路层通信时的主要步骤：
(1)结点A的数据链路层把网络层交下来的IP数据报添加首部和尾部封装成帧
(2)结点A把封装好的帧发送给结点B的数据链路层
(3)若结点B的数据链路层收到的帧无差错，则从收到的帧中提取IP数据报上交给网络层；否则丢弃这个帧
特点：数据链路层不用考虑物理层如何实现，所以就相当与对等层水平传输
$\color{red}{*}$1.2三个基本问题
1.封装成帧：
封装成帧：就是在一段数据前后分别添加首部和尾部，确定帧的界限，然后就构成了一个帧
添加首部和尾部的作用：进行帧定界(确定帧的界限)；包含许多必要的控制信息
帧长：帧的数据部分加上帧首部和帧尾部的长度
最大传送单元MTU：链路层协议规定的所能传送的帧的数据部分长度上限
帧格式：
帧界定的方法：可用特殊的帧定界符，在ACSCII码中，用SOH表示帧的首部开始，EOT表示帧的结束
帧界定的作用：判断收到的帧是否完整，不完整则丢弃
2.透明传输：
透明传输：不管什么数据，都能完整无差错的通过这个数据链路层，数据链路层对数据没有妨碍，数据链路层对数据时透明的
透明传输中的问题：若数据中的某个字节的二进制代码恰好组成了帧界定符，就会出现错误
解决方法：字节填充，在控制字符和特殊字符前插入一个转义字符"ESC"，而真正的首部和尾部前不加
3.差错检测：
比特差错：在传输中可能会产生比特差错，1可能变0，0可能变1
误码率：在一段时间，传输错误的比特占所有传输比特总数的比率，与信噪比有关
\(\color{red}{*}\)循环冗余校验(CRC)：
原理：在发送端，先把数据划分为组，假定每组k个比特，若传输一组数据M=101001(k=6)，在M后添加供差错检测用的n位冗余码后一起发送，共发送(k+n)位，接收方用收到的数据除P，若余数为0则表示没有差错
冗余码计算方法：在M后面添加n个0，得到（k+n）位的数除以选定好的除数p，得出商Q，余数R，将余数R作为冗余码，添加到M后
例：k=6，M=101001，设n=3，除数P=1101，被除数是101001000，计算后得到商Q=110100，余数R=001
帧校验序列(FCS)：为差错检验而添加的冗余码；就是计算后得到的余数R
生成多项式：一种方便的表示循环冗余校验过程的方法
例：P=1101->P(X)=X³+X²+1(最高位对应X³，最低位对应Xº)
传输差错的分类：
比特差错：1变0，0变1
帧丢失：丢失某个帧
帧重复：某个帧收到多次
帧失序：后发送的帧反而先到达接收端
CRC的局限性：只能实现无比特差错，不能实现无传输差错，只能判断收到的数据是否正确，其余均无法判断，并不是可靠传输
无差错接受：接收端数据链路层接受的帧，都能认为在传输过程中没有产生差错
可靠传输：发送端发送什么，接收端就收到什么
2.点对点协议PPP
对于点对点的链路，目前使用最广泛的是PPP协议
2.1 PPP协议的特点
作用域：用户计算机和ISP通信时所使用的数据链路层协议
PPP协议应满足的需求：
(1)简单：对数据链路层的帧，不需要纠错、序号、流量控制，简单作为首要要求；收到帧进行CRC检验，无差错则接收，反之丢弃
(2)封装成帧：必须规定特殊的字符作为帧定界符，使接收端从收到的比特流中准确找出帧的开始和结束位置
(3)透明性：必须保证数据传输的透明性，要能解决碰巧出现和帧定界符一样的比特组合的问题
(4)多种网络层协议：必须能够在同一条物理链路上同时支持多种网络层协议的运行，如IP等；在局域网和路由器上同样如此
(5)多种类型链路：必须能够在多种链路上运行
(6)差错检验：必须能够对接收端收到的帧进行检测，并立即丢弃有差错的帧
(7)检测连接状态：必须能够自动检测链路是否处于正常工作状态
(8)最大传送单元：必须对每一种类型的点对点链路设置MTU的标准默认值；促进各种实现之间的互操作性，若高层协议发送的分组数据部分超过MTU值，则丢弃并返回差错
(9)网络层地址协商：必须提供一种机制使通信的两个网络层的实体能够通过协商知道或能够配置彼此的网络层地址
(10)数据压缩协商：必须提供方法来协商使用数据压缩算法
PPP的特点：不支持多点线路，只支持点对点的链路通信，只支持全双工链路
PPP协议不需要的功能：纠错、流量控制、序号、多点线路、半双工或单工链路（只工作在点对点链路）
PPP协议的组成：
(1)将IP数据报封装到串行链路的方法；PPP支持异步链路，也支持面向比特的同步链路；IP数据报在PPP帧中数据部分，收到MTU限制
(2)用来建立、配置和测试链路连接的链路控制协议LCP
(3)网络控制协议NCP，其中每一个协议支持不同的网络层协议
2.2PPP协议的帧格式
首部和尾部分别为4个字段和2个字段
标志字段F：规定为0x7E，表示一个帧的开始或结束，就是帧的定界符
地址字段A：规定为0xFF
控制字段C：规定为0x03
协议字段：
(1)当协议字段为0x0021时，PPP帧的信息字段就是IP数据报。
(2)当协议字段为0xC021时，PPP帧的信息字段就是PPP链路控制协议LCP的数据。
(3)当协议字段为0x8021时，PPP帧的信息字段就是网络层的控制数据。
信息字段：长度可变，不超过1500字节
帧减压序列FCS：CRC中使用的冗余码
透明传输问题： 当信息字段中出现和标志字段一样的比特(0x7E)组合时，就必须采取一些措施使这种形式上和标志字段一言的比特组合不出现在信息字段中。
异步传输-字符填充：
- 当PPP使用异步传输时，它把转移符定义为0x7D，并使用字节填充。
- RFC1662规定了如下填充方法：
(1)把信息字段中出现的每一个0x7E字节转变为2字节序列(0x7D，0x5E)。
(2)若信息字段中出现一个0x7D的字节(即出现了和转义字符一样的比特组合)，则把转义字符0x7D转变为2字节序列(0x7D，0x5D)。
(3)若信息字段中出现ASCII码的控制字符(即数值小于0x20的字符)，则在该字符前面要加入一个0x7D字节，同时将该字符的编码加以改变。例如，出现0x03(在控制字符中是“传输结束”ETX)就要把它转变为2字节序列的(0x7D，0x31)。
- 由于在发送端进行了字节填充，因此在链路上传送的信息字节数就超过了原来的信息字节数。但接收端在接收到数据后再进行与发送端字节填充相反的变换，就可以正确地恢复出原来的信息。
\(\color{red}{*}\)同步传输-零比特填充：
- 当PPP使用同步传输时，使用零比特填充。
- 零比特填充的具体方法：
(1)在发送端先扫描整个信息字段(通常使用硬件实现，但也可以用软件实现，但是会慢一些)。
(2)只要发现有5个连续的1，则立即填入一个0。
(3)接收端在收到一个帧时，先找到标志字段F以确定帧的边界，接着再用硬件对其中的比特流进行扫描，每当发现5个连续1时，就把5个连续1后的一个0删除，以还原成原来的信息比特流。
- 因此通过这种零比特填充后的数据，就可以保证在信息字段中不会出现连续6个1。
2.3PPP协议的工作状态
3.使用广播信道的数据链路层
3.1局域网的数据链路层
局域网的特点：网络为一个单位所拥有，且地理范围和站点数目均有限
局域网的优点：
(1)具有广播功能，从一个站点可方便的访问全网；局域网上主机共享局域网上各种硬件和软件资源
(2)便于系统的扩展和演变，各设备的位置可灵活调整和改变
(3)提高了系统的可靠性、可用性和生存性
\(\color{red}{*}\)局域网的拓扑结构：总线网、环形网、星形网
媒体共享技术：
静态划分信道：频分复用、时分复用、波分复用、码分复用；代价较高，不适合局域网使用
动态媒体接入控制(多点接入)：
随机接入：所有用户可随机发送信息，若发生碰撞(冲突)，会使这些发送失败，需要解决碰撞的网络协议
受控接入：用户不能随机发送信息而必须服从一定的控制，如多点线路探询(轮询)
以太网的两个标准：DIX Ethernet V2；IEEE 802.3
数据链路层的两个子层：
逻辑链路控制(LLC)：靠近网络层，看不见下面的局域网，为网络层提供统一的接口，已经过时
媒体接入控制(MAC)：靠近物理层，存放与接入媒体有关的内容
适配器的作用：
网络适配器又被称为网卡
包含了数据链路层和物理层两层的功能
适配器的重要功能：(1)进行串行\并行转换、(2)对数据进行缓存、(3)在计算机的操作系统安装设备驱动程序、(4)实现以太网协议
计算机通过配置器和局域网通信：
$\color{red}{*}$3.2 CSMA\CD协议
总线的特点：当一台主机发送数据时，总线上所有主机都能检测到这个数据，就是广播通信方式
为使通信简便采取的措施：
(1)采用无连接工作方式，不必先建立连接就可以直接发送数据；适配器对数据帧不编号，不要求发回确认；因此，以太网提供尽最大努力交付，是不可靠交付；收到差错帧则丢弃，是否重传由高层决定，和以太网无关；同一时间只允许一台主机发送数据；使用CSMA/CD协议
(2)发送的数据使用曼切斯特编码
CSMA/CD协议要点：
(1)多点接入：说明是总线型网络
(2)载波监听：检测总线上有没有其他计算机也在发送；每个主机必须不停的检测信道，发送前检测是为了获得发送权，发送中检测是为了及时发现碰撞
(3)碰撞检测：边发松边监听，也叫冲突检测；发生碰撞就立即停止发生，等待一段随机时间后再次发送
发生碰撞的原因：电磁波在1km电缆的传播时延为5μs，在这段时间其他主机发送数据无法检测到，就会导致之后某时刻发送冲突
适用环境：双向交替通信(半双工通信)
以太网的发送不确定性：每一个站在自己发送数据之后一段时间内，存在遭遇碰撞的可能，这段时间是不确定的，取决于离另一个发送站的距离，因此无法保证一定能把自己的数据帧成功发送出去
\(\color{red}{*}\)争用期(碰撞窗口)：以太网端到端的往返时间2τ；经过争用期没检测到碰撞，才能肯定这次发送不会发送碰撞
截断二进制指数退避算法：用来确定碰撞后重传的时机，不是信道空闲就立即再次发送，而是推迟一个随机的时间
具体流程：
(1)规定了基本退避时间为争用期2τ，具体的争用期时间是51.2μs；对于10Mbit/s以太网，争用期内能发送512bit，即64字节，也可以说争用期是512比特时间。
(2)从离散的整数集合[0,1,...,(2^k-1)]中随机取一个数，记为r，重传应推后r倍的争用期，k=min(重传次数，10)
(3)当重传16次仍不成功时，丢弃该帧，向高层报告
凡长度小于64字节的帧都是由于冲突而异常终止的无效帧
强化碰撞：当发现碰撞时，处理立即停止发送数据外，还要继续发送32bit或48bit的人为干扰信号，使所有用户都知道发生了碰撞
帧间最小间隔：9.6μs，即96比特时间，使刚收到数据帧的站的接受缓存来得及清理，做好接收下一帧的准备
CSMA/CD协议要点：
(1)准备发送：适配器从网络获得一个分组，加上首部和尾部组成以太网帧，放入以太网缓存中，发送前先检测信道
(2)检测信道：若检测到信道忙，则不停检测，直到信道转为空闲；若检测到信道空闲，并在96比特时间内保持空闲，就发送这个帧
(3)在发送过程中仍不停检测信道，边发送边监听。这里有两种可能：
发送成功：争用期内未检测到碰撞。这个帧一定能发送成功。发送完毕后回到(1)
发送失败：争用期内检测到碰撞。立即停止发送，并按规定发送人为干扰信号(强化碰撞)，执行指数退避算法，等待r倍512比特时间后，返回步骤(2)；若重传16次仍不成功，停止重传并向上报错
3.3使用集线器的星形拓扑
\(\color{red}{*}\)集线器的特点：
(1)使用集线器的以太网在逻辑上仍是一个总线网，各站共享逻辑上的总线，还是使用CSMA/CD协议，在同一时刻只允许一个站发送数据
(2)一个集线器有多个接口，因此一个集线器很像一个多接口转发器
(3)集线器工作在物理层，仅简单的转发比特，不进行碰撞检测
(4)有专用的芯片，能自适应串音回波抵消
每次只能发送一个信号，工作在物理层，只对比特进行转发不进行检测
3.4以太的网信道利用率
以太网信道的利用率：由于会发生碰撞，实际利用率达不到100%
成功发送一个帧占用信道的时间：T0+τ
参数a：
a=τ/T0 是单程端到端时延τ与帧的发送时间T0之比
a->0表示一发生碰撞就能立即检测出来并停止发送，而a越大，争用期占比越大，使信道利用率降低
因此a的值越小越好；当数据率一定时，以太网连线的长度受到限制，同时以太网的帧长不能太短
极限信道利用率Smax：
Smax=T0/(T0+τ)=1/1+a
只有参数a远小于1才能得到尽可能高的极限信道利用率
3.5以太网的MAC层
MAC地址：
定义：又叫物理地址或硬件地址；就是适配器的标识符，用48位二进制数来标识网卡的硬件地址，表示为6个16进制数，在局域网内具有唯一性
I/G位：地址字段第一个字节的最低位；为0表示单个站地址、为1表示组地址，用来进行多播
G/L位：地址字段第一个字节的最低第二位；为0表示全球管理、为1表示本地管理
适配器的过滤功能：适配器收到MAC帧后检查帧中目的地址，若发往本站则收下，否则丢弃
发往本站的帧：
(1)单播帧：一对一，即收到的帧的MAC地址与本站的硬件地址相同
(2)广播帧：一对全体，即发送给本局域网上所有站点的帧(全1地址)
(3)多播帧：一对多，即发送给本局域网上一部分站点的帧
MAC帧格式：
以太网数据帧长度：64~1518
各字段含义：
类型：用来标志上一层使用的是什么协议
数据：长度在46~1500字节
FCS：帧检验序列，使用CRC检验
填充字段：当数据字段长度小于46字节时，MAC子层会在数据字段后面加入一个整数字节的填充字段，以保证MAC帧长不小于64字节
插入的8字节：从MAC子层传到物理层时要在帧前插入8字节，由硬件生成
前同步码：7字节；使接收端的适配器在接收MAC帧时能迅速调整时钟频率，使其和发送端时钟同步
帧开始定界符：定义为10101011；用来表示帧开始
无效的MAC帧：
(1)帧的长度不是整数个字节
(2)用收到的帧检验序列FCS查出差错
(3)收到的帧的MAC客户数据长度不在46~1500字节之间，或MAC帧长度不在64~1518
4.扩展以太网
物理扩展：集线器、光纤
4.2在数据链路层扩展以太网
网桥：对收到的帧根据MAC帧目的地址查找地址表进行转发和过滤
交换机：工作在数据链路层，实质就是一个多接口网桥
\(\color{red}{*}\)特点：交换机上的主机是全双工工作，不会产生冲突，交换机中存有地址表通过自学习算法建立，交换机上所有端口在同一个广播域上
帧转发方式：
直通：收到帧之后直接转发，不必事先把整个数据帧缓存，但也不对帧进行检验
存储转发：将所有帧都收到后进行检查，然后再发送
\(\color{red}{*}\)交换机的自学习功能：
地址表的形成：收到未知的地址后，存储源地址和接口的对应关系，向除来源端口的其它端口广播，目的地址不符则丢弃，否则接收并回复，收到回复后存储对应关系；地址表有有效时间，超过有效时间则失效
生成树协议STP：解决无限循环的问题
4.3虚拟局域网
虚拟局域网（VLAN）：是一些局域网网段构成的与物理位置无关的逻辑组
\(\color{red}{*}\)VLAN标记：在MAC帧的源地址和类型间插入4字节的VLAN标记，交换机收到帧后只向所属VLAN转发，而不进行广播
最大帧长变为1522字节(1518+4)
习题
3.网络适配器的作用是什么？工作在哪一层？
解：适配器是用来实现数据链路层和物理层这两层的协议的硬件和软件；工作在数据链路层和物理层
4.数据链路层的三个基本问题为什么必须解决？
解：帧定界是分组交换的必然要求；透明传输避免消息符号与帧定界符混淆；差错检验防止差错的无效帧浪费后续路由上的传输和处理资源
14.常用的局域网的网络拓扑有哪些种类？现在最流行的是哪种结构？为什么早期的以太网选择总线拓扑结构而不是星形拓扑结构，但现在却改为使用星形拓扑结构？
解：星形网、总线网、环形网、树形网；现在最流行星形结构的拓扑；因为早期可靠的星形拓扑结构较贵，人们都认为无源的总线结构更可靠
$\color{red}{*}$19.以太网使用的CSMA/CD协议是以争用方式接入到共享信道。这与传统的时分复用TDM相比优缺点如何？
解：传统时分复用是静态时隙分配，均匀高负荷时信道利用率高，低负荷或负荷不均匀时资源浪费较大；CSMA/CD动态使用空闲资源，低负荷时信道利用率高，但控制复杂，高负荷时信道冲突大
20.假定1km长的CSMA/CD网络的数据率为1Gb/s。设信号在网络上的传播速率为200000km/s。求能够使用此协议的最短帧长。
解：对于1km长的电缆，单程传播时间为1/200000=5μs，来回传播时间即为10μs，所以最小帧的发射时间不能小于10μs，以1Gb/s速率工作，10μs能发送的比特数为10*10^-6 *1*10^9=10000.因此，最短帧长是10000位
27.有10个站连接到以太网上。试计算一下三种情况下每一个站所能得到的带宽。（1）10个站都连接到一个10Mb/s以太网集线器；（2）10个站都连接到一个100Mb/s以太网集线器；（3）10个站都连接到一个10Mb/s以太网交换机。
解：(1)10个站共享10MB/s (2)10个站共享100MB/s (3)每个站独享10MB/s
29.以太网交换机有何特点？用它怎样组成虚拟局域网？
解：以太网交换机工作在数据链路层，可实现透明交换；虚拟局域网是由一些局域网网段组成的与物理位置无关的逻辑组，这些网段具有某些共同需求。虚拟局域网协议允许在MAC帧中插入一个4字节的VLAN标记，用来指明发送该帧的工作站属于哪一虚拟局域网
30.
解：最大吞吐量为1100Mbit/s。三个系中各有一台主机分别访问两个服务器和通过路由器上网。其他主机在系内通信。9+2=11
33.如图，以太网交换机有6个接口，分别连接5台主机和一个路由器，完成下表
解：