数据链路层

Mar 19th, 2020

• 链路(link)是一条点到点的物理线路段，中间没有任何其他的交换结点。

  • 一条链路只是一条通路的一个组成部分

• 数据链路(data link) 除了物理线路外，还必须有通信协议来控制这些数据的传输。把实现这些协议的硬件和软件加到链路上，就构成了数据链路。目的是让通信过程变得更加可靠。

  • 现在最常用的方法是使用适配器（即网卡）来实现这些协议的硬件和软件。

  • 一般的适配器都包括了数据链路层和物理层这两层的功能。

From Signals to Frames(帧结构)

数据链路层采用了帧结构传输，当传输中有位发生错误时，只需要重新传输有错误的帧，提高了传输的效率。

数据链路的主要功能

1. 链路管理

2. 封装成帧 (帧定界)

   • 有起始帧和终止帧表示传输的开始和结束

3. 流量控制

   • 当传输的速率过快或者稍慢可以调节传输速率

4. 差错控制

   • 如带有海明校验码进行传输帧的检验和纠错

5. 透明传输

   • 下一层不需要关心帧的传输，就像数据链路层不需要关心物理层的bit传输

   • 在面向比特的传输协议中，通过在连续5个1后面插入0来转义起止符

   • 在面向字节的传输协议中，通过插入转义字节来转义起止符

6. 寻址

   • 确定接受信息的对象地址

数据链路层传送的是帧

帧的封装和拆取是互逆的操作

向网络层提供的服务

• 无确认的无连接服务

  • e.g. 以太网

  • 不需要对方在线，不需要建立连接，不需要对方应答

• 有确认的无连接服务

  • 不需要对方在线，不需要建立连接，需要对方应答

• 面向连接的服务

  • 有建立连接、相互应答、结束连接等过程

成帧

• 涉及的问题

  • 将上层(网络层)交下来的数据包按照所采用协议决定的格式，封装成一定形式的帧；

  • 考虑接收双方的同步问题（即定界）；

  • 计算帧的校验和并放入帧中一起传送给接收方；

• 协议数据单元 PDU(Protocol Data Unit)

  • 帧：在数据链路上交换数据的单位。

    

成帧方式

• 物理层编码违例法

  • 发出非0非1表示传输开始

  • 不正常，不常用

• 字符填充的首尾定界法

  • 以字节为单位进行传输

  • 以 10101011 为起止符

  • 传输的数据是8bit的倍数

  • e.g. 以太网中使用最多

• 位填充的首尾定界法

  • 以比特为单位进行传输

  • 以 0111111 为起止符

  • 传输的数据不受限制，不需要是8bit的倍数

  • e.g. 广域网中使用最多

流量控制

• 数据链路层要控制从同等实体接收PDU的速率。

• 流量控制定义：限制发送方发送速度的一种机制。使发送速率不能超过接收方能处理的速率。

• 流量控制的特点

  • 流量控制必须是动态的

    • 流量速度不仅与发方速度相关而且与网络的当前拥挤程度有关

  • 必须有某种反馈机制

    • 使发送方了解接受方的当前处理能力

差错控制

• 顺序到达

  • 指保证所有的帧最终都按正确的发送次序到达目的。

• 确认方式

  • ACK肯定确认

  • NAK否定确认

• 计时器法

  • 计时器值的设定要保证一帧到达对方并作处理后，相应的确认帧返回。

  • 如果超时则主动重发

• 检错和纠错

  • 检出传输中出现的差错；可能的话确定出错位置从而纠正错误。

数据链路层协议的作用

数据链路层只负责点对点，不参与网络层的相关 DataLink的协议使得线路传输变好了

帧传输模型

理想传输模型

最理想的情况基于两条基本假设: 1. 传输的数据不会出差错,也不会丢失 2. 不管发送方以多快的速率发送数据, 收方总来得及收下.

去掉第二条假设情况

去掉第二条假设（不管发送方以多快的速率发送数据, 收方总来得及收下），需引入流量控制。

去掉第一条假设情况

去掉第一条假设，可能会出现死锁。需要引入差错控制和超时重发机制。

组合四种的网络情况

Automatic Repeat reQuest (ARQ协议)

Stop and Wait

步骤: 1. Source transmits frame 2. Destination receives frame and replies with acknowledgement 3. Source waits for ACK before sending next frame 4. Destination can stop flow by not send ACK 5. Works well for a few large frames

• 源实体发送一个PDU，并启动一个计时器。目标实体收到后发回一个对该PDU的确认，表示同意接受下一个PDU

  • 计时器作用：防止死锁，两个相互等待

  • 计时器时间设置：略大于单程传输时间

• 源实体必须等待直到收到确认后才能发送下一个PDU；如果源实体的计时器超时后还没有收到确认，就重新发送一次。

• 目标实体能简单地用停止发送确认的方式来阻止数据流。

• 由接受方控制发送方的数据流乃是计算机网络中流量控制的一个基本方法。

详细步骤

在发送结点： (1) 从主机取一个数据帧。 (2) 将数据帧送到数据链路层的发送缓存。 (3) 将发送缓存中的数据帧发送出去（启动Timer）。 (4) 等待。 (5) 若收到由接收结点发过来的信息(此信息的格式与内容可由双方事先商定好)，则从主机取一个新的数据帧，然后转到(2)。

在接收结点： (1) 等待。 (2) 若收到由发送结点发过来的数据帧，则将其放入数据链路层的接收缓存。 (3) 将接收缓存中的数据帧上交主机。 (4) 向发送结点发一信息，表示数据帧已经上交给主机。 (5) 转到(1)。

• 举个例子：

  

Stop-and-Wait ARQ with Errors

• 设 P 是传输帧出错的概率，则传输一帧的期望为：

  • $N_x = \frac{1}{1-P}$

• 线路最大利用率为：

  • $U=\frac{1}{N_x (1+2a)}=\frac{1-P}{1+2a}$

实用的停等ARQ协议

特点：简单，效率低

• 超时重发技术

  • A发送完一个数据帧时，就启动一个超时计时器

• 重复帧问题

  • 如果是接收方的应答帧丢失(差错)，会导致发送方重复发送，出现重复帧。每个数据帧带上不同的发送序号。每发送一个新的数据帧就把它的发送序号加1，（mod 2），1 bit序号。

• 帧的编号问题

  • 序号所占用的比特数是有限的，因此，经过一段时间后，发送序号就会重复。

  • 序号占用的比特数越少，数据传输的额外开销就越小。习惯表示，ACKn 表示“第n * 1号帧已经收到，现在期望接收第n号帧。

Stop-and-Wait ARQ结论

stop-wait协议ARQ的优点比较简单，但缺点是通信信道的利用率不高，尤其是传播延时很大时，可采用连续ARQ和选择重传ARQ。

Go Back N (GBN)

• Window size W

• The sender transmits packets 0,1,2, …,W-1 and waits for up to T seconds for each of their ACKs. As soon as the receiver gets an ACK for packet 0 it transmits packet W.

• If time-out go back n and retransmit.

• 接受端只按序接收数据帧

• 每发送一个数据帧都要设置超时timer

• 因连续发送数据帧而提高了效率，但信道传输质量很差时，效率不一定优于stop-wait 协议。

• 发送端在重发表中保存所发送的每个数据帧的备份。重发表按FIFO队列操作。

• 每个数据帧包含一个唯一的序号，该序号在相应的ACK帧中返回，返回该序号时，发送端从重发表中删除该数据帧。

• 对每个出错的数据帧，接收端都产生相应的NAK帧；发送端一收到NAK,从重发表中尚未确认的第一个帧开始重新发送。

注意：上图中的累计确认方式，即 发送ACK4的时候表示前面的0-3都已经收成功收到了，所以此时只需要从第4个开始重发。

做个题：

答案：

Sliding Windows (滑动窗口)

• 前提：在连续ARQ协议中，必须对可以连续发出的最多帧数（已发出但未确认的帧）作限制，每一帧设置timer。

• 原则：循环重复使用有限的帧序号，以形成固定值（标准）

• 流量控制：

  • 发送窗口：其大小WT表示在收到对方确认的信息之前，可以连续发出的最多帧数（只有序号在窗口内的帧才可发送）

  • 接收窗口：其大小WR可以连续接收的最多数据帧数（只有序号在窗口内的帧才可以接收，否则丢弃）

• 接收窗口驱动发送窗口的转动

• 发送/接收窗口的关系式(n为序号的位数)： $W_T+W_R \leq 2^n$ $W_T \leq 2^n-1$

举个例子(转盘表示)：

举个例子(滑轨表示)： 发送方 接收方

回退N协议的最大发送窗口大小

上图考虑了一种极其特殊的情况：当接收方的ACK完全丢失的时候，此时发送方要从序号0开始重新发送，接收方却指向了下一个新的连续m的序号0，这样子当接收方收到发送方重新发送的序号0时，不能对其做出正确判断，导致存储发生重复错误。 故结论为：

• W_T=m : 当确认全部丢失时易造成混肴

• W_T=m-1 : 发送序号为 0~m-2；重新发送的第一个序号是0，下一轮的第一个序号是 m-1，不会混淆——最大滑动窗口

• W_T< m-1 : 更加不会混淆

注意：这里 GBN 的编号是一开始就预留的，滑动窗口的大小收到其限制

Selective Repeat (选择重传ARQ)

• 在连续ARQ中，如果某个数据帧发生差错，后续的数据帧即使被正确地接收到，也要被丢弃，造成网络资源浪费

• 为进一步提高信道的利用率，可设法只重传出错的数据帧或计时器超时的数据帧

• 可加大接收窗口，先收下发送序号不连续但仍处在接收窗口中的那些数据帧。等到所缺序号的数据帧收到后再一并送交主机。

• 选择重传 ARQ 协议可避免重复传送那些本来已经正确到达接收端的数据帧。

• 我们付出的代价是在接收端要设置具有相当容量的缓存空间(保存窗口中正确的帧)，实现相对复杂。

选择重传ARQ协议

• 原则：只重传出错或定时器超时的数据帧

• 方法：WR > 1，暂存接受窗口中序号在出错帧之后的数据帧

• 优点：避免重传已正确传送的帧，提高信道利用率

• 缺点： 在接收端需要占用一定容量的缓存，算法相对复杂

• 接收窗口的尺寸不能超过2^(n-1)（即序号范围的1/2），否则可能造成帧的重叠。接收窗口的最大值：$W_R \leq W_T$ $W_R \leq 2^{n-1}$

接收窗口尺寸过大发生重叠举例

注：确认信号完全丢失的情况下，发送方重新发送0-3，而接收方希望得到4-7和下一个0，此时由于发送和接受的0序号相等导致接收端接收到了错误的序号0

与GBN协议对比

GBN	selective repeat
$W_T>1$ $W_R=1$	$W_T>1$ $W_R>1$
只能按顺序接受数据帧 帧出错或丢失需要丢弃该帧以其后所有帧 发送端超时需要重发出错帧及后面所有帧	发送端只需要发送出错的帧 不需要重发其后的所有帧
发送端需要为每个等待确认的帧设置定时器	发送端支持累计确认
发送窗口尺寸不能超过2^(n-1)	接受窗口不能超过2^(n-1)
接收窗口尺寸一般为1 逐个接受并返回确认信号	发送窗口尺寸一般与接收窗口尺寸相同 发送端为每一个输出缓冲区设置定时器 定时器超时则该缓冲区中的帧则被重发
发送端保持缓存来保存没有确认的帧	接收端需要相当的缓存

• 出错全部重发协议中，发送窗口的尺寸是大于1(加大接受窗口)，而接收窗口的尺寸则等于1。

• 由于接收窗口的尺寸为1，接收端只能按顺序地接受数据帧，一旦某个帧出错或丢失，只能简单地丢弃该帧及其所有的后续帧（因为发送窗口的尺寸是大于1的），不作任何确认。发送端超时后需重发出错或丢失的帧及其后续所有的帧。

• 发送端需要为每个待确认的帧各自设置一个定时器。

• 发送窗口的尺寸不能超过2^(n-1) (这里的n为序号的编码位数)，否则会造成接收端无法分辨新、旧数据帧。

• 只要求发送端保持一定数量的缓存来保存没有确认的数据帧，对接收端没有缓存的要求。但在误码率高的情况下，会大大降低信道的利用率。

归纳三种方式

$W_T$	$W_R$	滑动窗口协议
>1	=1	GBN
>1	>1	Selective Repeat
=1	=1	Stop-and-Wait

差错控制 (Error Control)

• 所谓差错，就是在通信接收端收到的数据和发送端发送的数据不一致的情况。

差错控制技术

• 在发送的数据码元序列中加入监督位，并进行某种变换，使它们和原来相互独立的数据码元之间具有某种约束关系。如果这种约束关系被破坏，则接收端就可以发现传输中的错误，甚至纠正错误。

• 变换的方法不同，就构成了不同的编码，因而产生不同的差错控制方法。

• 检错码可以发现传输错误，但不能自动纠正。

  • 主要代表：CRC循环冗余校验

• 纠错码可以自动纠正传输错误。

  • 由于实现复杂+需要更多冗余位导致传输效率降低，大部分纠错码限于1-3位纠错

  • 主要代表：Hamming Code(汉明码)，主要用来纠正1位差错

• 由于监督位需要占用传输资源，所以差错控制是以降低效率为代价的。

• 解决方案：

  • 自动请求重发 (ARQ , Automatic Repeat Request）

  • 正向纠错 (FEC , Forward Error Correction）

  • 实际应用中主要用ARQ，只有单向（工）通信用FEC (如电视)

循环冗余检验CRC计算

• 待传送数据M，约定好的供差错检测用位n位和约定好的除数P(P的首位和末位一定为1)

• 在M的后面直接添加n位的0，与P进行模2除法

• 模2除法中不采用借位而是直接求 异或

• 将上面模2除法的余数拼接在M的后面进行传输

• 接收端接收到的数据与约定好的除数P进行模2除法，结果为0则正确，不为0则错误

举个例子：

• M = 1010001101，设 n = 5, P = 110101

• 加上n位0的M为 101000110100000，模 2 运算的余数 R = 01110

• 将余数 R 作为冗余码添加在数据 M 的后面为 101000110101110

• 接收方将 101000110101110 与 110101 模2运算结果为 0

• CRC循环冗余计算特点：检错能力极强，开销小，易于用编码器及检测电路实现(异或位运算对硬件友好)

  

FEC (正向纠错)

• 差错控制的重要措施：采用抗干扰编码(即纠错编码)。

• 定义

  • 码组：由n个码元(0,1)构成的每一组合

  • 信息码：代表报文的0和1

  • 监督码：插入的 "0" 和 "1"

  • （按照某种规律在信息序列中插入一定数量的新码元）

举个例子：

• 需要传输 0 或 1

• 若直接传输 0 或 1，完全不知道是否有错误发生

• 若用00代替0，11代替1，则{00,11}是准用码组，{01,10}是禁用码组，则具备1位检错能力，不具备纠错能力

• 若用000代替0，111代替1，则只有{000,111}是准用码组，具有检出两位及两位以下错码的能力，具有纠正一位错码的能力，纠正是按照最短汉明距离计算的

• 码距：指两个码组对应码位码元不同的个数

  • e.g. (000)与(010) 的码距为1，(000)与(110) 的码距为2，(000)与(111) 的码距为3

  • 由此可见，码组的最小距离越大，其抗干扰能力越强

• 汉明距离（d0） ：一个有效编码集中，任意两个码字的码间距离的最小值。即一组编码中的最小码距

• 编码关系式

  • 为了检出e个错码，要求码集的汉明距离：$d \geq e+1$

  • 为纠正t个错码，要求码集的汉明距离：$d \geq 2t+1$

  • 为了检出e个错码，同时能纠正t个错码，则应满足：$d \geq e+t+1 (e>t)$

• 计算为m位数据纠错时所需的冗余位数 r ： 数据传输的总位数是m+r，且要求 r必须能够至少表示 m+r+1 种状态。其中，一种状态表示无差错，m+r 种状态分别表示在 m+r 位每个位置上发生的差错。 由于r 位二进制数可以表示2^r种不同的状态,所以，2^r必须大于或等于 m+r+1。 $2^r\ge m+r+1$ e.g. 传输10位的数据采用汉明校验码，则需要冗余的4位。

做个题：

差错检测

• 接收方收到数据单元和CRC后，将整个码字除以给定除数（同生成CRC用的除数）。

• 如果到达的数据没有差错，接收方CRC校验器产生的余数应是0，数据被接收，如果余数非0则被拒收。

  

  注：上图中是在左端补齐，左端是末端，应该是小端存储。

纠错码

• 理论上，自动纠正每一个二进制代码的传输差错是可以做到的。但纠错码比检错码复杂得多，而且需要更多的冗余位，导致传输效率降低。为此，大部分纠错码只限于处理1位、2位或3位差错。

• 在数据通信中，最常用的纠错码是所谓“汉明码”(Hamming Code），是贝尔实验室的科学家R.W.Hamming 于1950年提出的，主要用来纠正1位差错。

  1. 自动请求重发 (ARQ , Automatic Repeat Request）

     • 自动发现差错并要求对方重发

  2. 正向纠错 (FEC , Forward Error Correction）

     • 自动发现并纠正错误

实际应用中主要用ARQ，只有单向（工）通信用FEC

面向位的协议HDLC

• 1974年，IBM的SNA采用了面向比特的 SDLC（Synchronous Data Link Control）

• 国际标准化组织把SDLC修改为高级数据链路控制 HDLC （High-Level Data Link Control）

• CCITT则把HDLC再修改后称为链路接入规程LAP（Link Access Procedure)，后改为LAPB。B即表示平衡型。

• HDLC中只有一个地址域，即从站的地址，在命令帧中，它是目的地址，在响应帧中，它是源地址。

HDLC特点

• HDLC是面向比特的数据链路控制协议的典型代表，该协议不依赖于任何一种字符编码集；

• 数据报文可透明传输，用于实现透明传输的 “0比特插入法” 易于硬件实现；

• 全双工通信，有较高的数据链路传输效率；

• 所有帧采用CRC检验，对信息帧进行顺序编号，可防止漏收或重发，传输可靠性高；

• HDLC支持的规程种类包括异步响应方式下的不平衡操作、正常响应方式下的不平衡操作、异步响应方式下的平衡操作。

HDLC Link Configurations

不平衡 Unbalanced

• One primary and one or more secondary stations，采用主从结构（有一个结点Primary管理其他结点Secondary），链路上一个主站控制多个从站，主站向从站发命令，从站向主站返回响应。

• Supports full duplex（全双工） and half duplex（半双工）

  平衡 Balanced

• Two combined stations（既是Primary又是Secondary）

• • Supports full duplex and half duplex

HDLC Station Types

Primary station 主结点 (Unbalanced)

• Controls operation of link

• Frames issued are called commands

• Maintains separate logical link to each secondary station

Secondary station 从结点

• Under control of primary station

• Frames issued called responses

Combined station 既是主又是从结点 (Balanced)

• May issue commands and responses

HDLC Transfer Modes

Frame Structure

• 帧同步机制 首位标志Flag：01111110

• All transmissions in frames

• Single frame format for all data and control exchanges

  

Flag Fields

• Delimit frame at both ends：01111110

• May close one frame and open another（01111110可以同时作为一个帧的结尾和开始）

• Receiver hunts for flag sequence to synchronize

• Bit stuffing used to avoid confusion with data containing 01111110

  • 0 inserted after every sequence of five 1s

  • If receiver detects five 1s it checks next bit

  • If 0, it is deleted

  • If 1 and seventh bit is 0, accept as flag

  • If sixth and seventh bits 1, sender is indicating abort

Bit Stuffing （位填充）

为了解决中间传输的信息遇到 01111110 的时候被误判为结束，位传输过程中会在 五个1后面加一个0，接收端在拆包的时候将5个1后面跟着的0删去。

Address Field

• Identifies secondary station that sent or will receive frame

• Usually 8 bits long

• May be extended to multiples of 7 bits

  • LSB （Least Significant Bit）of each octet indicates that it is the last octet (1) or not (0)

  • 每8位的最小位是0或1，0代表后面还有扩充地址，1代表扩充地址结束

  • 
• All ones (11111111) is broadcast

  • 全1的情况是发送广播，任何人都能接收

Control Field

• Different for different frame type

  • Information - data to be transmitted to user (next layer up)

    • Flow and error control(流控制和差错控制) piggybacked(捎带) on information frames

    • 开头第一位是 0

  • Supervisory - ARQ when piggyback not used

    • 监控帧用于差错控制和流量控制

    • 开头两位是 10

  • Unnumbered - supplementary link control

    • 开头两位是 11

• First one or two bits of control filed identify frame type

Control Field Diagram

• 8位控制码

  
• 16位控制码

  

注意里面构成：

• N(S) = Send Sequence Number

• N(R) = Receive Sequence Number

• S = Supervisory Function Bits

• M = Unnumbered Function Bits

• P/F = Poll/Final Bit

Poll/Final Bit

• Use depends on context(基于传输的内容)

• Command frame

  • P bit

  • 1 to solicit (poll) response from peer（发出请求）

• Response frame

  • F bit

  • 1 indicates response to soliciting command（发出应答）

Information Field

• Only in information and some unnumbered frames

• Variable length

• 信息帧用于传送有效信息或数据，通常简称I帧。

  • I帧以控制字第一位为“0”来标志。

• 信息帧的控制字段中的N（S）用于存放发送帧序号，以使发送方不必等待确认而连续发送多帧。

• N（R）用于存放接收方下一个预期要接收的帧的序号，N（R）=5，即表示接收方下一帧要接收5号帧，换言之，5号帧前的各帧接收到。

• N（S）和N（R）均为3位二进制编码，可取值0～7。

Frame Check Sequence Field

• FCS

• Error detection

• 16 bit CRC

• Optional 32 bit CRC

HDLC Operation

• Exchange of information(负责传输数据), supervisory(负责进行检查) and unnumbered frames(负责建立连接)

• Three phases（面向连接三步曲）

  • *Initialization

  • Data transfer

  • Disconnect

The unnumbered format

Action	Code	?	Meaning
SABME (Set Asynchronous Balanced Mode)	1111P110	C	Request logical connection
DM (Disconnect Mode)	1111F000	R	Unable to establish or maintain logical connection
UI (Unnumbered Information)	1100P000	C	Used for unacknowledged information transfer
DISC (Disconnect)	1100P010	C	Terminate logical connection
UA (Unnumbered Ack)	1100F110	R	Acknowledge SABME or DISC
FRMR (Frame Reject)	1110F001	R	Unacceptable frame report
XID (Exchange Identification)	1111*101	C/R	Exchange identification information

Operations

1. Connection Establishment

   • SABME ---->

   • <----- UA

2. Data Transfer

   • I-frames and

   • S-frames for flow and error control.

3. Disconnect

   • Either entity can issue a DISC

Examples

Practice

Internet中的数据链路层

SLIP (Serial Line IP)

1. IP数据报用字符END（0XC0）定界。（11000000）

2. 如果在IP数据中出现END字符（0XC0），就用2字节字符 0Xdb，0Xdc 代替。

3. 如果IP数据报中有字节为0Xdb，就用 0Xdb，0Xdd 代替。

存在的问题： 1. 没有类型域，只能支持IP数据报。 2. 没有校验位。

PPP( Point to Point Protocol)

特点：

• IP地址的动态分配和管理；(因为是点对点传输所以甚至可以开始时没有地址)

• 同步（面向位的同步传输）或异步（起始位+数据位+奇偶校验位+停止位）传输；

• 网络层协议的复用；

• 链路的配置、质量检测和纠错；

• 多种配置参数选项的协商。

PPP frame structure

• FLAG: 7Eh = b'01111110

• ADDR: FFh = b'11111111 直接硬编码，因为点对点不需要地址

• CONTROL: 03h = b'00000011

• PROTOCOL: PPP支持不同的协议

• CRC: 校验码

PPP状态转移图

• PPP协议通过LCP协议完成数据链路的配置和测试

• PPP协议通过NCP协议完成点对点通信设备之间网络层通信所需参数的配置

LCP协议数据报文的格式

LCP：链路配置报文举例

一次交互

• PPP不存在主从之分，两者都可以发起请求和应答

• 假设点对点通信的一端发送了一个Config-Request报文，该报文将携带多种配置选项，具体携带哪些配置选项视应用而定。

• 当对端正确接收到该报文后，如果接受该报文携带的所有配置选项，则回应一个Config-Ack报文。

  

NCP：IPCP动态地址协商

• 点对点通信的一方设置了IP地址，而另一方则通过协商从对端获取IP地址。

  

Summary of PPP

• one sender, one receiver, one link: easier than broadcast link:

  • no Media Access Control

  • no need for explicit MAC addressing

  • e.g., dialup link, ISDN line

• popular point-to-point DLC protocols:

  • PPP (point-to-point protocol)

  • HDLC: High level data link control

Real Example of PPP

PPP：RFC1661,1662,1663 对SLIP的改进，Internet的正式标准，支持差错检测、多种协议、允许连接时协商IP地址、允许身份验证...

• F：首尾标志7Eh，透明传输采用字符填充

• A：地址字段，永远为FFh，表示所有站点都可以接收

• C：控制字段，默认为03h，表示无编号帧

• 协议：指明净荷字段的包类型，支持LCP、NCP、IP、IPX、AppleTalk...

  • LCP（链路控制协议），用于建立/拆除数据链路连接、测试连接质量、协商参数...

  • NCP（网络控制协议），用于协商网络层选项，如动态分配IP地址

• 物理层：支持MODEM拨号、HDLC位串行线、SONET...

PPP non-requirements(不需要做的事)

• no error correction/recovery(不负责纠错)

  • 在TCP/IP协议族中，可靠传输由运输层的TCP协议负责，而数据链路层的PPP协议只进行检错。

  • 这就是说，PPP协议是不可靠传输协议。

• no flow control(没有流量控制)

  • 在TCP/IP协议族中，端到端的流量控制由TCP负责，因而链路层的PPP协议就不需要再重复进行流量控制了。

• out of order delivery OK(没有应答序号传输)

  • PPP不是可靠传输协议，因此不需要使用帧的序号(许多过去曾经很流行的停止等待协议或连续ARQ协议都是用序号。)

  • 在噪声比较大的环境下，如无线网络，则可以使用有序号的工作方式，这样就可以提供可靠传输服务。

• no need to support multi-point links (e.g. polling)

  • PPP协议不支持多点线路(即一个主站轮流和链路上的多个从站进行通信)，而只支持点对点的链路通信。

差错、序号等问题放在高层解决，因为网络层的传输中出错的概率很小，所以不花费时间去检查检查。

Stuffing 填充

Byte Stuffing（异步方式）

首位标志Flag为 b'01111110，这里利用字节做填充，以 7D 为转义字节，对于中间出现的 7Eh 替换为 7D,5E，对于中间出现的 7D 替换为 7D,5D：

Bit Stuffing（同步方式）

连续的5个1后面插入一个0

多路访问协议

• 对于广播信道，需要解决信道分配问题，信道的分配方案有：

  • 静态分配：如传统的FDM或TDM，如果有N个用户，把带宽或时间分成N份，每个用户静态地占用一个。

    • 缺点是不能有效地处理突发数据，有的用户无通信量时白白浪费资源。

  • 动态分配：异步时分多路复用。分为两种：

    • 随机访问（争用，contention）：只要有数据，就可直接发送，发生冲突后再采取措施解决冲突。适用于负载轻的网络，负载重时效率低。

    • 控制访问：发送站点必须先获得发送的权利，再发送数据，不会发生冲突。在负载重的网络中可获得很高的信道利用率。主要有轮转(round-robin)和预约(reservation)两种方式。

Multiple Access Links and Protocols

• Two types of “links”

  • point-to-point (single wire, e.g. PPP, SLIP)

  • broadcast (shared wire or medium; e.g. Ethernet, Wavelan, etc.)

    

Random Access protocols

• When node has packet to send

  • transmit at full channel data rate R.

  • no a priori coordination(预先的配置) among nodes

• two or more transmitting nodes -> “collision”

• random access MAC protocol specifies:

  • how to detect collisions

  • how to recover from collisions (e.g., via delayed retransmissions)

• Examples of random access MAC protocols:

  • slotted ALOHA

  • (pure) ALOHA

  • CSMA and CSMA/CD

ALOHA Protocol

• 20世纪70年代，美国夏威夷大学的ALOHA网通过无线广播信道将分散在各个岛屿上的远程终端连接到本部的主机上，是最早采用争用协议的网络。（Aramson）

Basic operation: 1. All hosts transmit on one frequency. 2. Central node sends acknowledge on the other frequency. 3. Detect collisions by timing out for ACK. 4. Recover from collision by trying after random delay.

• Too short -> large number of collision

• Too long -> under-utilization

• 两个版本：

  • 纯ALOHA协议（Pure ALOHA）：每个站点只要有数据就可发送；通过监听信道来发现是否发生冲突；若冲突，则等待一段随机时间，再重新发送。

  • 时隙ALOHA协议（Slotted ALOHA）：将信道时间分为离散的时间片，每个时间片可以用来发送一个帧。一个站点有数据发送时，必须等到下个时间片的开始才能发送。

Pure (Unslotted) Aloha

• 工作原理：每个站只要有数据发送，就可自由发送一个数据帧,但必须收到接收节点的确认信号ACK之后，才能发送下一个数据帧。

• 冲突的发生：两个以上的站同时发送报文分组，由于在时间上重叠从而造成冲突，导致发送失败。

• 冲突的解决方案：发送节点在一个timeout interval内未收到确认信号ACK,自动重发。

• 特点：简单、不需要同步

• 任意时刻直接发送不需要等待

• 发生 collision 的概率增多 (以一帧传输的时间为单位时间)

  • pkt sent at t0 collide with other pkts sent in [t0-1, t0+1]

    

    可以看出需要在发送帧的时间前后1个单位都没有其他数据发送

推导传输成功率

可以将数据帧的发送看作三个独立同分布的事件：

Slotted Aloha

• time is divided into equal size slots (= pkt trans. time)

• node with new arriving pkt: transmit at beginning of next slot

• if collision: retransmit pkt in future slots with probability p, until successful.

Slotted Aloha efficiency

• Suppose N stations have packets to send

  • each transmits in slot with probability p

  • prob. successful transmission S is:

    • by a specific single node: $S= p*(1-p)^{(N-1)}$

    • by any of N nodes: $S= Prob (only\_one\_transmits)=N*p*(1-p)^{(N-1)}$

• At best: channel use for useful transmissions 37% of time!

Aloha Summary

• Aloha protocol is very simple, and fairly robust against failure of a host.

• The protocol is distributed among the hosts.

• Under low-load, we can expect the delay to be small.

• Under high-load, a lot of time is “wasted” sending packets that collide.

Improving performance: 1. Listen for activity before sending a packet.(发送前监听) 2. Detect collisions quickly and stop transmitting.(快速检测碰撞) 3. After a collision, pick the random waiting time so as to maximize throughput.(加大吞吐量)

随机接入技术：CSMA (Carrier Sense)

• 目的：载波监听多点访问 CSMA是从ALOHA演变出的一种改进协议。采用了附加的硬件装置，每个站都能在发送数据前监听信道上其他站是否在发送数据。如在发送，则此站就暂不发送数据，从而减少了发送冲突的可能。这样就提高了整个系统的吞吐量。

• 根据监测时刻不同，及监测后采用策略的差异，可分为四种:

  • 非坚持CSMA(non-persistent CSMA)

  • 1-坚持CSMA

  • P-坚持CSMA

  • CSMA/CD:边听边发

非坚持CSMA

• 非坚持CSMA的工作原理

  • (a) 监听到数据"闲"，则发送;

  • (b) 监听到数据“忙”，则放弃监听，按一定退避算法(random delay)延迟一段时间(这就是“非坚持”的含义），返回(a)。

• 优点：采用随机重传时间减少碰撞概率。

• 缺点：延迟时间内可能会出现通道闲的情况，利用率不高。

坚持CSMA

• 坚持CSMA的工作原理

  • 坚持CSMA的特点是在监听到信道忙，仍坚持听下去，一直坚持听到信道空闲为止。

• 有两种不同的策略：

  • p-坚持CSMA

    • (a) 若信道“闲”，以0<p<1的概率发送，以概率(1-p)延迟一个随机时间段再发送。

    • (b) 信道"忙"，则继续侦听到信道闲，返回(a)。

    • 优点：P可以设置以提高效率，但很难选择。

  • 1-坚持CSMA

    • 1-坚持是p-坚持的特例：p=1的情况，一旦监听信道为闲立刻发送。

    • 优点:提高信道利用率。

    • 缺点:若有两个或更多的站同时在监听信道，则一但信道空闲就必然使这些同时发送的帧互相冲突。

几种CSMA的分析

CSMA/CD (Collision Detection)

带冲突检测的 CSMA

• 引入原因

  • 当两个帧发生冲突时，两个被损坏帧继续传送毫无意义，而且信道无法被其他站点使用，对于有限的信道来讲，这是很大的浪费。如果站点边发送边监听，在监听到冲突之后立即停止发送，可以提高信道的利用率，因此产生了CSMA/CD。

• 工作原理

  • 站点使用CSMA协议进行数据发送 (1-坚持) ；

  • 在发送期间如果检测到冲突，立即终止发送，并发出一个瞬间干扰信号，使所有的站点都知道发生了冲突；

  • 在发出干扰信号后，等待一段随机时间，再重复上述过程。

• collision detection（CD）

  • easy in wired LANs: measure signal strengths, compare transmitted, received signals -> 以太网使用 CSMA/CD

  • difficult in wireless LANs: receiver shut off while transmitting -> 无线网使用 CSMA/CA

• CSMA/CD工作流程图 上面的 强化冲突 是指 发出一个瞬间干扰信号，使得全网都知道冲突的存在，进而停止传输
• CSMA/CS 伪代码

  A: sense channel, if idle （发送之前侦听线路，空闲发送）
    then {
        transmit and monitor the channel; （边送边听）
        If detect another transmission （碰撞后退随机时间）
            then {
                abort and send jam signal; （010101交错组成）
                update # collisions;
                delay as required by exponential backoff algorithm;
                goto A
                }
                else {done with the frame; set collisions to zero}
        }
        else {wait until ongoing transmission is over and goto A}

Ethernet’s CSMA/CD (more)

• Jam Signal: make sure all other transmitters are aware of collision

• Exponential Backoff: （截断二进制指数退避）

  • Goal: adapt retransmission attempts to estimated current load

    • heavy load: random wait will be longer

  • first collision: choose K from {0,1}; delay is K * 512 bit transmission times

    • K=0 --- send instantly

    • K=1 --- wait K*512 bit transmission times

  • after second collision: choose K from {0,1,2,3}

  • after N collision: choose K from {0,1,2,3,...,2^N-1}

  • after ten or more collisions, choose K from {0,1,2,3,4,…,1023}

Efficiency of CSMA/CD

• The efficiency (the percentage of useful time) is：

  $S_max = \frac{1}{1+4.44a}$

  $a=\frac{T_{prop}}{T_{trans}}$

• Question: you want to increase the bandwidth of the network, but still want to maintain the same efficiency, what do you do?

  • Answer: Increase T_prop as well

令牌环网 Token Ring

• Token：特殊的比特模型

• 拓扑结构：点到点链路连接，构成闭合环

• 传输媒体：STP，光纤，速率4/16Mbps；

  

  

令牌环的基本原理

• 令牌沿着环旋转

• 当某站要发送时必须等到经过该站的令牌

• 当一个站发送数据时环上不再有令牌

• 帧将在环上运行一周后由发送站清除

• 发送站完成发送后释放令牌

  • 该站所发送的帧的前沿已回到本站(已绕环一圈)

  • 该站已完成其帧的发送

• 下游的第一个站就能抓住令牌并进行发送

• 逻辑上和物理上均为环型

Example： IEEE 802.5协议 令牌环操作 其中T是令牌占有标记位

令牌帧结构字段分析

包括：

• 起始、结束定界符（违例差分Manchester码）

• 访问控制字节：

  • PPP，RRR：优先级位，和优先级预约位

  • T：令牌位，帧类型标识

    • 0 表示 令牌为空，可以发送数据，发送数据则将T位改成1然后挂载数据传递下去非令牌帧

      
    • 1 表示 信息/控制帧，查看目的地址是否为自己，是自己则接收数据

  • M：监督位，防止无效帧在环路中无限循环

令牌环的优缺点

• 优点

  • 在重负载条件下有效而公平

  • 可对媒体访问进行灵活控制

    • 提供优先级和保证带宽的服务

  • 内置应答

    • 发送节点在取回帧时能肯定是否被正确接收

• 缺点

  • 在轻负载下效率较低

    • 站必须等待token的到来才能发送

  • 需要对token进行维护

    • 既不能丢失，也不能重复

IEEE 802.5 详细介绍

令牌总线 Token Bus

• CSMA/CD是一种随机争用的媒体控制方式，具有不可知的最长等待时间。

• 在工厂自动化生产中，需要一种具有可知的最长等待时间的媒体访问控制方法。

• 802.4采用总线型的物理媒体，媒体访问控制方式则采用令牌环的方式.。

  

和令牌环的区别在于物理上的布局

令牌总线IEEE802.4帧格式

• 前导码（Preamble)：用于接收方时钟同步，但最短可以只有1个字节。

• 帧首定界符和帧尾定界符（SD and ED）：用作帧定界标志，用模拟编码符号。

• 帧控制段（FC）：表示帧是数据帧还是控制帧，在控制帧中，该段则说明帧的类型；在数据帧中，则带上该帧的优先级。

• 目的/源地址：接收方/发送方地址，有16位和48位两种，但在同一局域网中所有的地址长度应相同。

• 帧检验序列（FCS）：32位循环冗余码，检验除前导码、SD和ED外的字段。

局域网

• 局域网(LAN)是在一个小区域范围内对各种数据通信设备实现互连的信息网。特点如下：

  • 地理范围有限，一般局限于单个建筑物内，也可覆盖几个建筑物。如一个企业网，范围在几公里~几十公里。

  • 传输速率比较高，延迟小，传输速率一般在10Mbps~1000Mbps，~10Gbps。

  • 传输介质通常为光缆、双绞线；无线局域网流行

  • 往往为一个单位/组织来统一管理

局域网概述

• 局域网产生的原因

  • 70~80年代，微型机发展迅速，彼此需要相互

• 通信（近距离），共享资源

• 决定局域网特性的主要技术

  • 用以传输数据的传输媒体

  • 用以连接各种设备的拓扑结构

  • 用以共享资源的媒体访问控制方法

• 局域网的典型特性

  • 高数据传输速率（10M-1000Mbps，10G）

  • 短距离（0.1-10km)

  • 低误码率（10^-8-10^-11）

局域网的拓扑结构

• 星型（Star）

  
• 环型（Ring）

  
• 总线型（Bus）

  
• 树型（Tree）

  

局域网传输介质

• 同轴电缆

  
• 双绞线

  
• 光纤

  
• 无线

  

局域网中的数据链路层

• 逻辑链路控制子层(LLC)

  • 通过提供统一格式,向网络层提供一个接口

  • 支持链路的多路访问特性，建立/释放逻辑连接，差错控制，帧序号处理

  • 屏蔽各种802网络的底层差异，如拓扑结构、介质、介质访问控制访问

• 介质访问控制子层(MAC)

  • 根据网络的拓扑结构和传输介质，不同的局域网采用不同的介质访问控制方法

  • 成帧(各种不同的帧结构)，拆帧，寻址等

  • CRC校验

典型的LAN帧结构

LLC的功能（已基本不用）

• 提供三种服务

  • 无连接的服务

  • 面向连接的服务

  • 复用

• 差错控制与流量控制

  • 类似HDLC协议，定义了三种格式

    • 信息帧

    • 监控帧

    • 无编号帧

IEEE802协议

• LLC负责不同的底层协议之间的互联，即从逻辑的层面统一物理差异

• 802.7和802.8还定义了物理层的相关技术

IEEE802参考模型及协议

• MAC子层用于描述与传输媒介有关的物理特性；

• LLC子层用于描述与传输媒介无关的物理特性。

局域网的IEEE 802系列标准

802.3 采用CSMA/CD技术的局域网(以太网)

• ALOHA系统

• ALOHA + 载波监听

• Xerox（Bob Metcalfe、David Boggs) 设计了 2.94Mbps 的采用 CSMA/CD 协议的 Ethernet

• Xerox, DEC, Intel共同制定了 10Mbps 的 CSMA/CD 以太网标准(工业标准)

• IEEE定义了采用1-坚持型CSMA/CD技术的 802.3 局域网标准，速率从1M到10Mbps，802.3标准与以太网协议略有差别。(法定标准)

• CSMA/CD 基本原理

  1. 侦听线路

  2. 空闲发送

  3. 边送边听（发送最小帧长64bytes的字节未检测到冲突，认为发送成功）

  4. 冲突后退（指数后退算法，回到1）

• CSMA/CD 冲突域

  

  • 为确保发送成功, 一台主机在发送结束之前必须能够检测到冲突

  • 最小帧长= 2*Prop*传输速率

  • Prop=L/0.77c （当时按2500m, 4个中继器计算）

  • 10Mbps以太网最小帧长为512bits(64bytes)

以太网帧格式

• Ethernet V2 是事实标准，也称为工业标准。

• IEEE802.3 是法定标准，也称为国际标准。

• Pad为填充位，当传输的数据Data不满46字节的时候填充，在接收端会去掉。

• 以太网的帧最大的大小为 DA+SA+type+Data_max+CRC=6+6+2+1500+4=1518B。

• 前面的Preamble为前导码，表示有数据要发送。

• SFD是帧开始的表示，表示网络上的主机要开始检测DA是否为自己，是自己则接收数据，不是则丢弃。

物理地址

• 物理地址、网卡地址、MAC地址、硬件地址在以太网中概念相同。

• 用6个字节表示，前三个字节为厂家代号，后三个字节为产品序列，要向OUI(Organization Unique Identifier)注册，以免重复冲突

• e.g.

  • AA:00:04 DEC

  • 00:00:0C Cisco

  • 02:60:8C 3Com

  • 08:00:07 Apple

帧类型

• 类型域 > 1500 (也就是十六进制的0x05DC)， 即为 EthernetII 帧格式，并且表示的是上层(网络层)使用的协议

  • 如 : 0x0800 表示 IP协议, 0x8138 表示 IPX协议, 0x6004表示 Decnet协议

• 否则为IEEE802.3 帧格式，即类型域(也就是IEEE802.3的长度域)小于1500

  • 这里也说明IEEE传输的数据长度不超过1500

  • 实际上EthernetV2传输的数据长度为46~1500B，IEEE802.3传输的长度为43~1497B

详细比较可见： Ethernet_II帧和802.3_Ethernet帧格式比较 Ethernet V2、802.3SAP、802.3SNAP 比较

物理层选项与标识方法

由三个字段组成，分别表示： 1. 速率，单位 Mb/s 2. 基带或宽带 3. 每段最大长度，单位 百米 或 介质类型(T, F, X)

• T for Twisted 双绞线，工程标准的长度是100m(绝对安全的距离)

• F for Fiber 光纤

• X for 电口

• 最大长度中的2实际长度为185m，2只是写着方便

常见的几种类型：

10Base2/10Base5

• 10BASE2、10BASE5是最早期的总线型局域网技术，适合于较小的单位、很少的网点，且价格较便宜。

• 不足:单点故障(一个节点故障影响整段通讯)、扩展困难、可靠性较差。

  

10BaseT无屏蔽双绞线

• IEEE于1990年推出新规格10BaseT,将共享内建于集线器(Hub)的内部，对外连线则采用星状布线。

• 网络上任何一段线路出现故障，不会影响到网络上其他使用者。

• 双绞线比传统的同轴电缆轻巧，在办公室中颇受欢迎。

• 缺点是易受电磁干扰，驱动距离最远仅为100米。

  

集线器

物理层功能(属于物理层不是数据链路层): 1. 信号的再生和再定时 2. 检测碰撞 3. 端口的扩展功能 4. 混合连接10Base5与10Base2以太网系统

• 一个口接收到了信号其他所有口输出

RJ45插头插座

• 平行线连接方式

  • 采用同一种标准进行连接，通常是T-568B，内部不交叉

  • 一般而言，平行线用于连接Hub或Switch

• 交叉线连接方式

  • 双绞线两头采取不同标准，一端T-568B，另一端T-568A与水晶头进行连接，四对线内部都要交叉

  • 用于对等的两个通信设备的直连，因为对等的通信设备的接口定义通常采用同一标准

10BaseF光纤

• 同轴电缆由于电气衰减及电磁干扰，隔离效果较差，使得局域网的距离受到限制。当网络系统较大或需要较大频宽传输信息时，选择以光纤为主干的网络。

• 光纤的直径减小到只有一个波长8~10μm，可使光线一直向前传播，光源一般为激光，称单模光纤。衰减小，传输远，容量大。

• 可以存在多条不同角度入射的光线，直径一般为50~100 μm ，光源一般为发光二极管，称多模光纤。传输距离短。

• 10Base-F使用标准的62.5/125μm的多模光纤和ST标准连接器。

以太网中传播时延

传输媒体	电磁波在该媒体中的传播速度
粗缆(同轴电缆)	0.77c (2.31e5 km/s)
细缆(同轴电缆)	0.65c (1.95e5 km/s)
双绞线	0.59c (1.77e5 km/s)
光纤	0.66c (1.98e5 km/s)
AUI电缆	0.65c (1.95e5 km/s)

10M以太网组网规则(冲突域)

• 允许5个网段

• 在信道上只允许4个中继器

• 其中3个网段可以放置节点

• 另2个网段除了中继器链路外，不能有任何节点

• 以上组成1个冲突域，最大节点数为1024，最大传输距离为2500米

共享冲突域的情况

快速以太网(Fast Ethernet)

• IEEE802.3u 协议

• 100BaseT是10BaseT的真正继承者，100BaseT保留了大多数10BaseT的布线规则和CSMA/CD介质访问方式，具有以下特点:

  • 从传统10BaseT以太网的升级较容易，投资少，与现有10BaseT网的集成也很简单。

  • 众多厂家支持，产品价格相对较低。

  • 安装和配置简单，现有的管理工具依然可用。

• 特点：

  • 采用CSMA/CD媒体访问控制方式和802.3帧格式，兼容性好，容易布线

  • 100BASE-TX采用两对5类双绞线

  • 100BASE-T4采用四对3类双绞线

  • 网络最大长度250m(10M以太网是2500m，由于速度提高了，为了保持传输的帧的长度不变，需要将传输的距离缩小10倍)

• 缺点:在一个冲突域中传输距离有限。

100M以太网传输介质

100M以太网中继器组网规则

• 对于I类中继器，只允许连接1个中继器，每段最长100米

  • I类中继器:支持不同编码的介质，延迟:0.7us

• 对于II类中继器，最多允许2个中继器，可以由两段各100米长的链路及5米长的中继器链路 (缺省)

  • II类中继器:只支持相同编码的介质，延迟:0.46us

  • 中继器是Hub，但是可以接交换机Switch

快速以太网Hub组网跨距

快速以太网光纤(MMF)组网跨距

FastEthernet组网可能潜在的问题

• 共享的网络直径太大

• 在3类UTP上传输100BaseTx

• 在只有2对线的UTP上传输 100BaseT4

• 100BaseT4、100BaseTx和 10BaseTx端口不匹配

共享型以太网存在的问题

• 受CSMA/CD约束，每个站点平均带宽为系统带宽/n，n为该冲突域的站点数

• 每一时刻只能要求一个发送者，在站点数增加到一定程度时，网络效率极低

• 冲突域的覆盖范围有限

• 安全性极差

网桥

• 网桥:是一种数据链路层的网络设备，具有存储-转发装置，根据帧的目的MAC地址，通过查找地址表(转发表)进行转发。(有CPU、内存)

• 连接网段构成具有多个冲突域的系统，从而实现系统地理范围的扩展

• 把一个冲突域分割成多个冲突域，从而实现系统带宽的扩展，在一个网络中运行多机同时发送

• 具有容错功能，支持802.1D标准(STP)

• 过滤信息、提高网络安全

• 构成一个广播域

冲突域和广播域

简单来说：冲突域就是能否两台机器同时发送数据

网桥的工作原理

三个功能：

• 地址学习

• 帧转发

• 消除拓扑循环

MAC地址表

• 多口的网桥=交换机

• 交换机内部都有一张MAC地址表

• MAC地址是唯一标识主机的，在某些地方又称为 物理地址

  

地址学习：

• 最初交换机的MAC地址表为空

• 逆向学习法 : 若收到的帧源地址不在表中，则插入到表中，作为以后转发的路径。

• 泛洪法 : 对于目的MAC地址，如地址表没有记录，数据帧从其它所有端口转发出去(除入口之外)，识别数据帧的源MAC地址，学习MAC地址和端口对应关系，并记录下来。

地址转发：

• 通过MAC地址表实现数据帧的单点转发

交换机(Switch)

• 在原理上相当于多口的网桥

• 网桥通常利用软件进行交换，而交换机则用硬件进行交换，两者方法:存储转发、直通式

特点： 1. 每个端口都占带宽 2. 系统最大带宽可达端口带宽的N倍 3. 支持全双工，可不受CSMA/CD的约束，用Switch串接，在理论上距离是无限的

直通交换方式是以太网交换机可以在各端口间交换数据。它在输入端口检测到一个 数据包(帧)时，检查该包的包头，获取包的目的地址，启动内部的动态查找表转换成 相应的输出端口，在输入与输出交叉处接通，把数据包直通到相应的端口，实现交换功能。 通常情况下，**直通交换方式只检查数据包的包头即前14个字节=Preamble的7字节+SFD的1字节+目的地址的6字节。

全双工以太网

• 利用2对线同时发送和接收帧，不受CSMA/CD限制。

• 传输距离较半双工模式要长。

• 在链路的两个方向上同时进行收发操作，从而使其链路的总带宽提高到一倍。

• 基于Switch技术，要求点对点满足，接Hub不行。

• 不需要载波侦听，不需要冲突监测。不受以太网冲突域的限制。

• 提高网络性能、扩展网络距离。

Switch+Hub组网跨距

交换网络性能问题

Multicast, broadcast, unknown destination 报文成为广播域网络的最大问题。

广播风暴

特点：

• 广播报文可能会消耗掉整个带宽资源。

• 任何设备都需要接受广播报文，解开后提交给主机，消耗每台主机的资源，而且不安全。

解决方法: 流量本地化

• LAN 广播可以用路由器/多层交换机进行隔离

• 多层交换机:L3/L4 交换机

• LAN广播可以用交换机通过Vlan划分，进行隔离

• 这里交换机是L2交换机，VLAN是数据链路层概念

VLAN(Virtual LAN)

• 在使用交换设备的网络中，使用VLAN技术能有效地把用户的分为若干个虚拟工作组，而不用考虑地理分布。

  

VLAN的标准

• 1996年3月，IEEE802.1因特网工作分会完成了VLAN标准的初步研究 ，制定了IEEE802.1Q/P

• VLAN的帧标记的标准格式由802.1Q协议规定

• 802.1p协议规定了多媒体应用中所要求的业务量等级及其控制规程，还提供了动态控制组播组的通信功能。

LAN和VLAN的区别

• LAN和VLAN的主要区别和优势有:

  • VLAN工作在ISO模型的第2层

  • VLAN提供控制网络广播的方法

  • 网络管理员可以把用户划入VLAN，管理方便

  • VLAN可以通过隔离通信域而提高网络的安全性

• 通过使用VLAN技术，可以按交换机端口、MAC地址、协议进行逻辑分组。

• 可以把一个交换机或多个相连的交换机的端口和用户划分为不同的组，VLAN可以跨越一栋建筑、多个互连的建筑，甚至城域网。

二层交换机和三层交换机的区别

• 不同VLAN就是不同的广播域，互联需要网络层设备路由器。

• 不同VLAN之间的连接靠第3层交换。

• L2交换机需要外接路由器进行互联。

• L3交换机就是带路由功能的交换机。

VLAN划分方法

• 按交换机的端口划分

  • 可以通过配置的形式明确指定端口所属的VLAN。

  • 特点:配置简单、含义明确、与实际联系紧密，应用广泛。目前用的多是这种方式。

  • 
• 按MAC地址划分

  • 通过MAC地址指定端口所属的VLAN，需要服务器和客户端的支持;和转发表配合可实现VLAN-端口的转换。

  • 特点:安全性高、配置比较烦琐，应用较少。

  • 
• 按数据类型划分

• 按组播地址划分

• 以上几种方式的组合

配置静态 VLAN

帧中的VLAN标记

• 跨交换机之间的通讯需要引入标记tag:IEEE 的802.1q.

  

带标记帧的传输过程

对端交换机根据802.1Q中的VLANID来区分正确的VLAN,然后向该VLAN包含的端口转发 e.g. 截获的报文中含有 IEEE802.1q字段，其中包含的VLANID=2：

以太网的自动协商

• 工作于点到点的链路上，无全网协商概念

• 协商在链路初始化时进行

• 协商信令与普通数据是分开的

• 每个设备向其他设备“通告”其功能，并按照公共功能集合选择合适的配置

• 不能协商站点间的布线类型

• 不支持非以太网系统

自动协商优先级

优先级	物理规格	连通
1	1000BaseT	全双工
2	1000BaseT	半双工
3	100BaseT2(已经不用)	全双工
4	100BaseTx	全双工
5	100BaseT2(已经不用)	半双工
6	100BaseT4(已经不用)	半双工
7	100BaseTx	半双工
8	10BaseT	全双工
9	10BaseT	半双工

链路冗余

1. 为了提高冗错性，交换机往往通过多条链路连接上层交换机，假设其中一条链路断了，可以有另外一条备用。 2. 如果交换机接收到一个广播包，则向所有两条上行链路上转发，核心层交换机接收到以后，互相转发，这样最终形成环路，带来网络风暴。

生成树协议(STP)

• 生成树协议(spanning-tree protocol)由IEEE802.1d标准定义。

• 生成树协议的作用是为了提供冗余链路，解决网络环路问题。

• 生成树协议通过SPA(生成树算法)生成一个没有环路的网络，当主要链路出现故障时，能够自动切换到备份链路，保证网络的正常通信。

• STP利用BPDU(Bridge Protocol Data Unit，网桥协议数据单元)在交换机之间交流网络拓扑信息。

• STP BPDU是一种二层协议数据单元。目的MAC是多播地址01-80-c2-00-00-00(Bridge_group_addr)，所有支持STP协议的交换机都会接受并处理收到的BPDU。

生成步骤： Embed a tree that provides a single unique path to each destination: 1) Select a single bridge as a root bridge 选择一个序列号(可设置)最小的网桥作为根 1) Each bridge calculates the distance of the shortest path to the root bridge 2) Each LAN identifies a designated bridge, the bridge closest to the root. It will forward packets to the root. 3) Each bridge determines a root port, which will be used to send packets to the root 4) Identify the ports that form the spanning tree

转发过程 即保留某些支路设置状态为Blocking，平时不开通以防出现环路，在RP之间的线路出现问题的时候将这些支路作为备份开通，即Blocking->Forwarding。

链路聚合(Truck)

• 链路聚合，也称trunk，交换机把一组链路聚合起来，使得这些链路像一条链路——聚合协议。(802.3ad)

• 这些端口称为聚合端口。

• 用于提高网络容量和可用性

• 该标准仅应用于全双工以太网链路

  • 所有链路必须以同一速率工作，带宽翻倍

网桥(交换机)小结

• 工作在数据链路层(主要是MAC)，检查帧的MAC地址进行转发，也称透明网桥。

• 隔离冲突域，扩大网络跨距

• 过滤通信量，减轻局域网负荷，一定程度提高安全性

• 具有自学习功能(逆向学习法，backward learning)，根据源地址及端口确定地址表。

• 为解决环路问题，802.1d网桥标准中，制定了一个在每个网桥上运行的生成树协议。提供可靠性。

• 用网桥连接的网络构成一个广播域。

Gigabit Ethernet 千兆以太网

• 主干采用千兆以太网的好处:千兆位以太网(半双工)将提供 10 倍于快速以太网的性能并与现有的 10/100 以太网兼容:

  • 最大帧长1518B，最小64B，重试上限16次，后退上限10次，Jam信号(告知冲突的信号)32b，帧间隙96b。

• 可以支持虚拟网VLAN标准 802.1Q 以及优先级标准 802.1p。

• 千兆以太网已成为构成局域网主干的主流技术。

问题：

在采用CSMA/CD的MAC子层中，碰撞检测时间与网络的最大距离成正比，在 10BASE-5中，最大距离为2500m，间隙时间为51.2微秒，最小帧长为512比特。在100BASE-T中，最大距离为250m，帧格式不变，即间隙时间为5.12微秒。按此规律，千兆以太网的最大距离为25m。

解决方案：

• 半双工方式 (CSMA/CD)

  • 载波扩展(carrier extension)

    • 使最小帧长仍保持64bytes , 通过填充一些特殊字符，使MAC帧的发送长度(争用期)增大为512bytes(4096b) ,最大网络跨距可达200m.

  • 帧突发功能(frame bursting)

    • 很多短帧时，第一帧采用载波扩展(填充)，随后在一定时间内连续发送多个MAC短帧，最大突发长度为8192字节。

• 全双工(不使用CSMA/CD)

千兆以太网跨距(最大距离)

• IEEE802.3z (8B/6T 1000Base-X)

  • 1000BaseLX 波长:860~1270 μm

    • MMF 62.5μm 550M

    • MMF 50μm 550M

    • SMF 10μm 5KM

  • 1000BaseSX 波长:770~860 μm

    • MMF 62.5μm 275M

    • MMF 50 μm 550M

  • 1000BaseCX

    • TW型 STP 25M

• IEEE802.3ab

  • 1000BaseT 5类 UTP (4 pairs) 100M

802.3ae: 万兆以太网10G

• 兼容802.3标准中定义的最小和最大以太网帧长度

• 仅支持全双工方式：速度太快半双工无法实现

• 使用点对点链路和结构化布线组建星型物理结构的局域网

• 支持802.3ad链路汇聚协议

• 定义两种PHYs(物理层规范) * LAN(局域网) PHY和 WAN(广域网) PHY

• 定义将MAC/PLS的数据传送速率对应到WAN PHY数 据传送速率的适配机制

• 定义支持特定物理介质相关接口(PMD)的物理层 规范，包括多模光纤和单模光纤以及相应传送距离

IEEE802.3以太网标准总结(用于查表)

数字表示传输速度，单位是“Mbps”，最后的一个数字表示单段网线长度(基准单位是10m)，Base表示“基带”的意思，Broad 代表“带宽”。

• 10Base-5使用粗同轴电缆，最大网段长度为500m，基带传输方法。

• 10Base-2使用细同轴电缆，最大网段长度为185m，基带传输方法。

• 10Base-T使用双绞线电缆，最大网段长度为100m。

• 1Base-5使用双绞线电缆，最大网段长度为500m，传输速度为 1Mbps。

• 10Broad-36使用同轴电缆(RG-59/U CATV)，最大网段长度为 3600m，是一种宽带传输方式。

• 10Base-F使用光纤传输介质，传输速度为10Mbps。

• 100BASE-TX是一种使用5类数据级无屏蔽双绞线或屏蔽双绞线的

  快速以太网技术。

• 100BASE-FX是一种使用光缆的快速以太网技术，可使用单模和多模光纤(62.5μm和125μm)，多模光纤连接的最大距离为550m。 单模光纤连接的最大距离为3000m。

• 100BASE-T4是一种可使用3,4,5类无屏蔽双绞线或屏蔽双绞线的快速以太网技术。

• 1000BASE-SX系列采用低成本短波的CD(compact disc，光盘激光器)或者VCSEL(Vertical Cavity Surface Emitting Laser，垂直腔体表面发光激光器)发送器。

• 1000BASE-LX系列则使用相对昂贵的长波激光器。

• 1000BASE-CX系列则打算在配线间使用短跳线电缆把高性能服务器和高速外围设备连接起来。

高速局域网技术FDDI

FDDI (Fiber Distributed Data Interface) 特征

• 使用多模光纤作为传输介质

• MAC协议与 Token Ring 类似

• 100M的速率

• 采用4B5B编码方法

  • 32中组合中的16种表示数据，3种表示定界符，2种表示控制，3种表示硬件信号，8种保留。

• 最大距离200公里

• 最多1000个站点

• 通常作为连接LAN的主干网络

逻辑上是环路，而且还支持双环，即一个环路上的某一段断开可以通过内环和外环的连接形成新的环状网络： 但是由于现在以太网的普及，Ethernet到FDDI Ring之间还需要一个Bridge进行网络的转换，成本高，所以FDDI已经不用了。

异步传输模式ATM

• ATM(异步传输模式)，是一种面向连接的快速分组交换技术，采用统计时分复用 STDM 方式，建立在硬件交换的基础上。

  • 面向连接就是需要预先建立连接和断开连接。

• ATM将信息分成固定大小的信元cell，长度53字节，3个byte为信头，48个byte为静荷。

• 类似于分组交换，但不使用分组交换的差错校检功能以提高速度。

• 它兼有分组交换的可调带宽和高速度，以及电路和帧交换固有的低时延。

• 但因为成本高且维护困难也不再使用。

无线局域网IEEE802.11

• IEEE 802.11 是一个有固定基础设施的无线局域网的国际标准。

• IEEE 802.11 是个相当复杂的标准。但简单地说，802.11 就是无线以太网的标准:

  • 它使用星形拓扑，其中心叫做 接入点 AP (Access Point)

  • 在MAC层使用 CSMA/CA 协议

• 凡使用 802.11 系列协议的局域网又称为 Wi-Fi Wireless-Fidelity，意思是“无线保真度”。

几种常用的 802.11 无线局域网

标准	频段	数据速率	物理层	优缺点
802.11b (1999年)	2.4 GHz	最高11 Mbit/s	扩频	最高数据率较低，价格最低，信号传播距离最远，且不易受阻碍。
802.11a (1999年)	5 GHz	最高54 Mbit/s	OFDM	最高数据率较高，支持更多用户同时上网，价格最高，信号传播距离 较短，且易受阻碍。
802.11g (2003年)	2.4 GHz	最高54 Mbit/s	OFDM	最高数据率较高，支持更多用户同时上网，信号传播距离最远，且不 易受阻碍，价格比802.11b贵。
802.11n (2009年)	2.4 / 5 GHz	最高600 Mbit/s	MIMO OFDM	使用多个发射和接收天线达到更高 的数据传输率。当使用双倍带宽(40 MHz)时速率可达600 Mbit/s。

CSMA/CA 协议

• 无线局域网不能简单地搬用CSMA/CD协议。这里主要有两个原因:

  • “碰撞检测”要求一个站点在发送本站数据的同时，还必须不间断地检测信道，但接收到的信号强度往往会远远小于发送信号的强度，边送边听的设计成本较高，在无线局域网的设备中要实现这种功能就花费过大。

  • 即使能够实现碰撞检测的功能，并且在发送数据时检测到信道是空闲的时候，在接收端仍然有可能发生碰撞。

无线局域网(Wireless LAN)问题

• WLAN设备中要实现边送边听的全双工功能花费过大。各个站点发出的信号范围有限，因此会造成:

  • 隐藏站点问题(hidden station problem):图(a)中，A向B发送时，由于C听不到误以为可发送数据，造成B接收失败，而A无法监测到。在发送数据时检测到信道是空闲的，在接收端仍然有可能发生冲突。

    • 
  • 暴露站点问题(exposed station problem):图(b)中，B向A发送时，C听到信道忙误认为它不能向D发送数据，实际上并不影响A和D两站的接收。应同时允许多点同时通信。

    • 

CSMA with Collision Avoidance(CSMA/CA)

• 无线局域网不能使用 CSMA/CD，而只能使用改进的 CSMA 协议。

• CSMA/CA(避免冲突的CSMA协议)是WLAN采用的介质访问控制协议，其相应的国际标准为IEEE 802.11。

• 改进的办法是把 CSMA 增加一个碰撞避免 CA(Collision Avoidance)功能。

• 802.11 就使用 CSMA/CA 协议，同时还增加使用停止等待协议。

CSMA/CA Protocol

• 送出数据前，监听媒体状态，如信道空闲，再等待一段随机的时间后依然没有人使用，才送出数据。

• 发送方先激发(RTS)接收方发送一个短帧(CTS)，使接收方周围的站点不会在即将到来的数据帧期间发送数据而导致冲突 (避免冲突)。

• 当多个站点同时向一个站点激发时仍会发生冲突，在预定时间内没有收到CTS的发送方采用二进制指数退避算法，在等待一随机时间后再次重试。

  • CSMA/CA 的 二进制指数退避算法 和之前的有区别。

• CSMA/CA: 信道预约

  • 发送站: 发出短的 RTS幀 (request to send) 预约信道

  • 接收站: 应答短的 CTS幀 (clear to send) 同意预约

• CTS为发送站保留信道,起了通知其它(可能隐蔽的)站点的效果

• 避免了隐蔽站点造成的冲突

  

CSMA/CA协议的基本流程图

CSMA/CA算法归纳

1) 若站点最初有数据要发送(而不是发送不成功再进行重传)，且检测到信道空闲，在等待时间DIFS后，就发送整个数据帧。 2) 否则，站点就要等检测到信道空闲并经过时间DIFS后，执行CSMA/CA协议的退避算法，启动退避计数器。在退避计数器减少到零之前，一旦检测到信道忙，就冻结退避计时器。一旦信道空 闲，退避计时器就进行倒计时。 3) 当退避计时器时间减少到零时(这时信道只可能是空闲的)，站点就发送整个的帧并等待确认。 4) 发送站若收到确认，就知道已发送的帧被目的站正确收到了。这时如果要发送第二帧，就要从上面的步骤(2)开始，执行 CSMA/CA协议的退避算法，随机选定一段退避时间。若源站在规 定时间内没有收到确认帧ACK(由重传计时器控制这段时间)，就 必须重传此帧(再次使用CSMA/CA协议争用接入信道)，直到收 到确认为止，或者经过若干次的重传失败后放弃发送。

802.11 局域网的 MAC 帧

• 802.11帧共有三种类型 : 控制帧、数据帧和管理帧

• 帧控制格式

  • RTS - 1011

  • CTS - 1100

  • ACK - 1101

• 四个地址(这里可能说不明白具体看下面例子)

  • 地址1: AP receive this frame——目的地址

  • 地址2: AP transmit this frame——源地址

  • 地址3: 指向的路由器的地址

  • 地址4: used for ad hoc mode——自主网络，主要在军队中单兵作战，通过几个节点形成自主网络

    

Practice

某局域网采用CSMA/CD协议实现介质访问控制，数据传输速率为10MBPS,主机甲和主机乙之间的距离为2KM，信 号传播速度是200000KM/S.请回答下列问题，并给出计算过程。请求出: (1) 若主机甲和主机乙发送数据时发生冲突，则从开始发送数据时刻起，到两台主机均检测到冲突时刻止，最短需经多长时间?最长需经过多长时间?(假设主机甲和主机乙发送数据过程中，其他主机不发送数据)

• 1km/200000km/s*2=1e-5s

• 2倍

  (2) 若网络不存在任何冲突与差错，主机甲总是以标准 的最长以大网数据锁(1518字节)向主机乙发送数据，主机乙每成功收到一个数据锁后，立即发送下一个数据锁，此时主机甲的有效数据传输速率是多少?(不考虑以太网锁的前导码)

• 发送1518B的数据帧所用时间(传输延迟) =1518×8 bits/10 Mbps=1214.4μs；（1分）

• 发送64B的确认帧所用时间(传输延迟) =64×8bits/10Mbps=51.2μs；（1分）

• 主机甲从发送数据帧开始到收完确认帧为止的时间记为T总，则T总=1214.4+51.2+2×10=1285.6 μs；（1分）

• 在1285.6μs内发送的有效数据长度=1518B-18B=1500B=12000bits；（1分）

• 因此，主机甲的有效数据传输速率=12000bits/1285.6μs ≈9.33Mbps。（1分）

在一个采用CSMA/CD协议的网络中，传输介质是一根完整的电缆，传输速率为1Gbps，电缆中的信号传播速度是200000km/s。若最小数据帧长度减少800比特，则最远的两个站点之间的距离至少需要( )。

• 最短帧长=2L10^9(b/s)÷200 000000m/s=10*L(bit)

• 帧长减少800bit则距离减少800/10=80m

对于100Mbps的以太网交换机，当输出端口无排队，以直通交换方式转发一个以太网帧(不包括前导码)时，引入的转发延迟至少是( )。 A.0us B.0.48us C.5.12us D.121.44us

由于不需要考虑前导码，只需要检查目的地址的6B**，所以最短的传输延迟是0.48us。

2014年全国统考34题:某以太网拓扑及交换机 当前转发表如下图所示，主机00-e1-d5-00-23-a1向 主机00-e1-d5-00-23-c1发送1个数据帧，主机00- e1-d5-00-23-c1收到该帧后，向主机00-e1-d5-00- 23-a1发送1个确认帧，交换机对这两个帧的转发 端口分别是( )。 A. {3}和{1} B.{2,3}和{1} C.{2,3}和{1,2} D.{1,2,3}和{1}

第一次发送时因为没有目标地址所以采用泛洪法——发送给除自己以外的所有主机 交换机从源地址学习到了第一台主机所以第二次发送回程时地址表里面已经有主机MAC，所以对点发送 所以选B

36.下列关于CSMA/CD 协议的叙述中，错误的是() A.边发送数据帧，边检测是否发生冲突 B.适用于无线网络，以实现无线链路共享 C.需要根据网络跨距和数据传输速率限定最小帧长 D.当信号传播延迟趋近0 时，信道利用率趋近100%

显然，无线网络使用的是CSMA/CA，所以选B

37.下列关于交换机的叙述中，正确的是 () A.以太网交换机本质上是一种多端口网桥 B.通过交换机互连的一组工作站构成一个冲突域 C.交换机每个端口所连网络构成一个独立的广播域 D.以太网交换机可实现采用不同网络层协议的网络互联

A直接正确 B是构成广播域不是冲突域 C是构成独立的冲突域 D：交换机主要用来实现多个局域网的互联，但是交换机工作在数据链路层，互联的局域网的物理层和数据链路层可以运行不同的协议，而数据链路层以上的高层必须采用相同的协议

36.下列选项中，对正确接收到的数据帧进行确认的MAC协议是 A.CSMA B.CDMA C.CSMA/CD D.CSMA/CA

需要确认的只有 CSMA/CA ，其有ACK帧

Reference

1. tech-faq | PPP (Point-to-Point Protocol)

2. csdn | 点对点协议PPP的特点

3. IEEE 802.5 详细介绍

4. Ethernet_II帧和802.3_Ethernet帧格式比较

5. Ethernet V2、802.3SAP、802.3SNAP 比较

6. 802.11帧格式