《计网》数据链路层

数据链路层概述

为网络层提供服务
- 无确认的无连接服务【适用于实时通信或误码率较低的通信信道-以太网】
- 有确认的无连接服务【适用于误码率较高的通信信道-无线通信】
- 有确认的有连接的服务【适用于对可靠性，实时性要求较高的场合】
使用点对点信道的数据链路层
- 封装成帧
- 差错检测
- 可靠传输
使用广播信道的数据链路层
- 共享式以太网的媒体接入控制协议CSMA/CD
- 802.11局域网的媒体接入控制协议CSMA/CA
数据链路层的互连设备
- 网桥和交换机的工作原理
- 集线器（物理层互连设备）与交换机的区别

组帧【封装成帧】

封装成帧是指数据链路层给上层交付的协议数据单元添加帧头和帧尾使之称为帧
- 帧头和帧尾中包含有重要的控制信息
- 帧头和帧尾的作用之一就是帧定界
为了提高帧的传输效率，应使帧的数据部分的长度尽可能大些
考虑差错控制等多种因素，每种数据链路层协议都规定了帧的数据部分的长度上限，即最大传送单元MTU
透明传输是指数据链路层对上层交付的传输数据没有任何限制，就好像数据链路层不存在一样
组帧方法：比特填充法+违规编码法
- 字符计数法
  - 在帧头部使用一个计数字段来表明帧内字符数
  - 缺点
    - 如果计数字段出错，就失去了帧定界划分的依据【计数字段的脆弱性】
- 使用字符填充的首位定界法
  - SOH表示帧的首部开始，EOT表示帧的结束
  - 在特殊字符前面填充一个转义字符ESC来区分
  - 接收方收到数据会删除ESC然后得到原来的数据
  - 缺点
    - 实现复杂与不兼容
- 使用比特填充的首位标志法
  - 使用0111 1110 表示一帧的开始和结束
  - 在数据中如果出现连续的5个1，就插入一个0
  - 比特法很容易用硬件实现，性能优于字符填充法
- 违规编码法
  - 在物理层进行比特编码时，通常采用违规编码法
  - 局域网IEEE 802标注采用这个方法
  - 违规编码法不需要填充技术，只适合于采用冗余编码的特殊编码环境

差错检测

检错编码和纠错编码
- 检错码只能检测出帧在传输过程中出现了差错，但不能定位错误，因此无法纠错错误
- 纠错码可以进行前向纠错，但是开销比较大，在计算机网络中比较少使用
检错编码分类
- 奇偶校验码
  - 在待发送的数据后面添加1位校验码，使整个数据中1的个数为奇数或偶数
    - 如果有奇数个位发生误码，可以检测出误码
    - 如果有偶数个位发生误码，不能检查出误码（漏检）
- 循环冗余校验CRC
  - CRC有很好的检错能力（漏检率非常低）
  - 计算比较复杂，但非常易于用硬件实现，因此被广泛应用于数据链路层
  - CRC具有纠错能力，但数据链路层只使用了他的检错功能，检测到帧出错直接丢弃
  - 计算举例
纠错编码分类
- 海明码
  - 实现原理
    - 在有效信息位中加入几个校验码组成海明码
    - 把海明码的每个二进制位分配到几个奇偶校验组中
    - 当某一位出错后，就会引起有关的几个校验位的值发生变化
  - 该方法不但可以发现错位，还能指出错位的位置
  - 可以纠正一位差错
  - 纠错d位，需要码距2d+1的编码
  - 检错d位，需要码距d+1的编码

可靠传输的基本概念

数据链路层向上层提供的服务类型
- 不可靠传输服务
  - 仅丢弃有误码的帧，其他什么也不做
- 可靠传输服务
  - 想办法实现发送什么，接收端就收到什么
一般情况，有线链路的误码率比较低，为了减小开销，并不要求数据链路层向上提供可靠传输服务。即使出现误码，可靠传输由上层处理
传输差错还包括分组丢失，分组失序，分组重复
- 分组丢失，分组失序及分组重复一般不会出现在数据链路层，而出现在上层
可靠传输服务并不局限于数据链路层，其他各层也可以实现可靠传输
可靠传输的实现比较复杂，开销大，是否使用可靠传输取决于应用需求

三种可靠传输机制

SW协议	发送窗口 = 接受窗口 = 1
GBN协议	1<发送窗口$\leq2^n-1$；接受窗口 = 1
SR协议	1<发送窗口$\leq2^n-1$；1<接受窗口$\leq$发送窗口

停止等待协议SW

接收端检测到数据分组有误码时，将器丢弃并等待发送方的超时重传
对于误码率较高的点对点链路，为使发送方尽快重传，可给发送方发生NAK（拒绝）分组
为了让接收方能够判断所收到的数据分组是否重复
- 给数据分组编号，只需要1个比特编号，即编号0和1
为了让发送方能够判断所收到的ACK分组是否重复
- 需要给ACK分组编号，只需要1个比特编号
- 数据链路层一般不会出现ACK分组迟到的情况
- 在数据链路层实现停止-等待协议可以不用给ACK分组编号
超时计时器设置的重传时间一般略大于从发送方到接收方的平均往返时间
- 在数据链路层点对点的往返时间好确认，重传时间好确认
- 在运输层，由于端到端往返时间不确定，重传时间不好确认
当往返时延RTT远大于数据帧发送时延TD时【如卫星链路】，信道利用率非常低
若出现重传，则对于传送有用的数据信息来说，信道利用率还要降低
为了克服该协议信道利用率低的缺点，可以使用GBN和SR协议
这些协议也叫做自动重传请求ARQ
- ARQ通过接收方请求发送方重传出错的数据帧来恢复出错的帧
例题

回退N帧协议GBN【Go-back-N】

例题

选择重传协议SR

例题

点对点协议PPP

PPP协议的组成
- 链路控制协议LCP
- 网络控制协议NCP
- 一个将IP数据报封装到串行链路的方法
PPP两端的网络层可以运行不同的网络层协议，但仍然能使用同一个PPP进行通信
PPP提供差错检测单不提供纠错能力，是不可靠的传输协议
PPP支持PAP和CHAP认证
- CHAP的安全性更高
- PAP在传输密码时是明文，CHAP在传输过程中传输哈希值
- PAP认证通过两次握手实现，CHAP通过三次握手
PPP可用于拨号连接，支持动态分配IP地址
PPP和HDLC协议均是数据链路层协议
HDLC是面向比特的数据链路层协议，PPP协议是面向字节的协议

媒体接入控制

媒体接入控制MAC
- 共享信道要着重考虑的一个问题就是如何协调多个发送和接受站点对一个共享传输媒体的占用，即MAC(Medium Access Control)
- MAC的内容就是，采取一定的措施，使得两对结点之间的通信不会发生互相干扰的情况
分类
要点
- 随着技术的发展，交换技术的成熟和成本的减低，具有更高性能的使用点对点链路和链路层交换机的交换式局域网在有线领域已完全取代了共享式局域网，但由于无线信道的广播特性，无线局域网仍然使用的是共享媒体技术

静态划分信道

信道复用
- 复用是通信技术中的一个重要概念
- 复用就是通过一条物理线路同时传输多路用户的信号
- 当网络中传输媒体的传输容量大于多条单一信道传输的总通信量时
- 可利用复用技术在一条物理线路上建立多条通信信道来充分利用传输媒体的带宽

静态划分信道分类

频分多路复用FDM

FDM的所有用户同时占用不同的频带资源并行通信
FDM和TDM的比较
- TDM抗干扰能力强，可以逐级再生整形，避免干扰的累积
- TDM数字信号比较容易实现自动转换
- FDM适合传输模拟信号，TDM适合传输数字信号

时分多路复用TDM

TDM的所有用户在不同的时间占用同样的频带宽度
TDM介质的位速率大于单个信号的位速率
可分为同步时分多路复用和异步时分多路复用（又称统计时分复用）
- 同步时分多路复用是一种静态时分复用技术，预先分配时间片（时隙）
- 异步时分多路复用是一种动态时分复用技术，动态分配时间片

波分多路复用WDM

超分多路复用CDM

CDM是另一种共享信道的方法
由于CDM主要用于多址接入，常用的名词为码分多址CDMA
与FDM和TDM不同，CDM的每一个用户可以在同样的时间使用同样的频带进行通信
由于各用户使用经过特殊挑选的不同码型，因此各用户之间不会造成干扰
CDM最初用于军事通信，这种系统所发送的信号有很强的抗干扰能力频谱，不易被敌人发现
随技术进步，CDMA设备价格和体积都大幅度下降，因而现在已经广泛应用于民用的移动通信中
CDMA中，每一个比特时间再划分为m个短的间隔，称为码片
通常m=64或128
使用CDMA的每一个站被指派一个唯一的mbit码片序列
- 一个站如果要发送比特1，则发送他自己的m bit码片序列
- 一个站如果要发送比特0，则发送他自己的m bit 码片序列的二进制反码
码片序列的挑选原则
- 分配给每个站的码片序列必须各不相同，实际采用伪随机序列
- 分配给每个站的码片序列必须相互正交（内积 = 0）
- 向量S表示站S的码片序列，向量T表示其他站的码片序列
- $S\cdot T = 0$
- $S\cdot \bar{T} = 0$
- $S \cdot S = l$
- $S \cdot \bar{S} = -l$
例题

随机接入协议分类

胜利者通过争用获得信道，从而获得信息的发送权，又称争用型协议
CSMA是指载波监听多址接入，并不适用确认机制
CSMA/CD是指载波监听多址接入/碰撞检测
- 对CSMA的改进，最早的共享信道以太网适用的信道访问控制协议
- 不适用确认机制
CSMA/CA是指载波监听多址接入/碰撞避免
- 是802.11局域网采用的无线信道访问控制协议
- 802.11局域网在使用CSMA/CA的同时，还使用停止-等待协议
- 无线信道的通信质量远不如有线信道，因此无线站点每发送完一个数据帧后，要等到收到对方的确认帧后才能继续发送下一帧
CSMA/CD和CSMA/CA的区别
- CSMA/CD
  - 可以检测冲突，但无法避免
  - 用于总线形以太网
  - 通过电缆中的电压变化来检测
- CSMA/CA
  - 发送数据的同时不能检测信道上有无冲突
  - 用于无线局域网
  - 采用能量检测，载波检测和能量载波混合检测三种检测信道空闲的方式

CSMA协议

信道状态	1-坚持CSMA	非坚持CSMA	p-坚持CSMA
空闲	立即发送数据	立即发送数据	以概率p发送数据，以概率1-p推迟到下一个时隙
忙	继续坚持侦听	放弃侦听，等待一个随机的时间再侦听	持续侦听，直到信道空闲

总线网使用的协议【CSMA/CD协议】

多址接入MA、碰撞检测CD、载波监听CS的概念

不适用于无线网络

征用期（碰撞期）

最大帧长

【首部+尾部+数据载荷最小开始=64，即最小帧长】

信道利用率

信号传播延迟趋于0时，信道利用率接近100%

MA、CD、CS的协作

最小帧长

截断二进制的指数退避算法

考虑到了网络负载对冲突的影响

帧发送流程

无线局域网使用的协议【CSMA/CA】

CSMA/CA为什么不能用于无线网？

帧间间隔IFS（InterFrame Space）

退避算法工作原理

CSMA/CA是什么

CSMA/CA的工作原理

退避算法示意

虚拟载波监听

令牌传递协议

令牌环网络有一个令牌不停地在环中流动，只有获得了令牌的主机才能发送数据，因此不存在冲突
令牌环网使用令牌在各个节点之间传递来分配信道的使用权，每个节点都可在一定的时间内获得发送数据的权利，而非无限制地持有令牌
同一时刻，环上只有一个数据在传输
网上所有节点只共享网络带宽
数据从一个节点到另一个节点的时间可以计算
最坏情况
- 一个站点获得令牌和发送数据中的时间 = 所有站点传送令牌和发送帧时间总和

MAC地址

基本概述

IEEE802局域网的MAC地址发送顺序

IEEE802局域网的MAC地址格式

以太网和802的MAC帧示意图

ARP（address resolution protocol）协议

IP地址到MAC地址的映射
ARP主要内容
- ARP的作用范围
  - 逐段链路或逐个网络（子网）使用
  - 硬件地址只有本地意义，每当路由器将IP数据报转发到一个具体的网络时，都需要重新封装源硬件地址和目的硬件地址
  - 路由器在收到分组后，剥离该分组的数据链路层协议头，然后在分组被转发前，给分组加上一个新的链路层协议头
  - ARP请求是广播发送
  - ARP响应式单播发送
ARP过程
- 目的主机在本局域网
  - 先在ARP高速缓存中查看有无目的IP地址与MAC地址的映射
  - 有，则把硬件地址写入MAC帧，然后通过局域网把该MAC帧发往此硬件地址
  - 无，通过广播ARP请求分组，在获得目的主句的ARP响应分组后，将目的主机的IP地址与硬件地址写入ARP告诉缓存
- 目的主机不在本局域网
  - 将IP分组发给本局域网的路由器，先通过上述方式获得路由器的IP地址和硬件地址的映射关系

交换机

以太网交换机的概述

以太网交换机自学习和转发帧的过程

以太网交换机工作在数据链路层（也包括在物理层）
以太网交换机收到帧后，在帧交换表中查找帧的目的MAC地址所对应的接口号，然后通过该接口转发帧
以太网交换机是一种即插即用的设备，刚上电启动时其内部的帧交换表是空的
随着网络各主机间的通信，以太网交换机通过自学习算法自动逐渐建立起帧交换表
例题

以太网交换机生成树协议STP

集线器和交换机的对比

局域网和广域网

以太网：802。3局域网称为以太网
10BASE-T的传输媒体是双绞线

	广域网	局域网
覆盖范围	很广、常跨区域	较小、通常在一个区域内
连接方式	节点之间都是点到点连接，但为了提高网络的可靠性，一个结点交换机往往与多个节点交换机相连	普遍采用多点接入技术
OSI参考模型层次	三层：物理层，数据链路层，网络层	两层：物理层，数据链路层
联系与相似点	广域网和局域网都是互联网的重要组成构建，从互联网的角度看，二者平等连接到一个广域网和一个局域网上的主机在该网内进行通信，只需要使用其网络的物理地址
着重点	强调资源共享，通信子网主要使用分组交换技术	强调数据传输

虚拟局域网VLAN

VLAN概述

虚拟局域网VLAN是一种将局域网内的设备划分成域物理位置无关的逻辑组的技术，这些逻辑具有某些系统的需求
三种划分方法
- 基于端口
- 基于MAC地址
- 基于IP地址
VLAN的优点
- 有效共享网络资源
- 简化网络管理
- 提高网络安全性

VLAN的实现机制

IEEE 802.1Q帧