保研计网复习笔记：数据链路层

数据链路层

按照IEEE标准，数据链路层可以被分为两个子层：
数据链路层 { 逻辑链路层 L L C { 成帧 流量控制 差错控制 介质访问控制层 M A C 数据链路层

\begin{cases}逻辑链路层LLC\begin{cases}成帧\\流量控制\\差错控制\end{cases}" role="presentation">\begin{cases}逻辑链路层LLC\begin{cases}成帧\\流量控制\\差错控制\end{cases}$$\text{begin{cases}逻辑链路层LLCbegin{cases}成帧流量控制差错控制end{cases}}$$

\\ 介质访问控制层MAC\end{cases} 数据链路层⎩ ⎨ ⎧​逻辑链路层LLC⎩ ⎨ ⎧​成帧流量控制差错控制​介质访问控制层MAC​

1. 差错控制

1.1 差错控制简介

1.1.1 错误的类型

single-bit error：在给定的数据单元，仅有一位发生从0到1或者1到0的变化。

burst error：数据单元中有两位或者更多位发生1到0或者0到1的错误。

• burst error并不意味这差错在连续位上出现
• The length of burst error is measured from the first corrupted bit to the last corrupted bit

1.1.2 错误检测和纠正

Detection：只看差错是否发生，只回答是否。

Correction：知道破坏位的个数，在报文中的位置

纠错方法：向前纠错，重传

1.2 块编码

1.2.1 数据字和码字

datawords：在块编码中，把报文划分成块，每块有 k 位，称为数据字datawords

codewords：并增加 r个冗余位使其长度变为 n = k + r，形成 n 位的块称为码字codewords

invaild or illegal：$2^n-2^k$冗余码

1.2.2 错误检测的条件

可以进行差错检测的条件：

• 接收方有有效码字的列表
• 原来的码字变成无效的码字

如果码字在传输中被破坏，但接收到的码字仍然是一个有效的码字，差错则无法被检测到。

1.2.3 汉明距离

Hamming distance between two words $d(x,y)$：两个相同长度的字的汉明距离是对应位不同的数量。

计算：对两个字异或后计算1的个数
$$d(000,011)=2;d(000,101)=2$$

1.2.4 最小汉明距离

minimum hamming distance：一组字中所有可能对的汉明距离的最小值。

1.2.4.1 编码方案的表示

• datawords 长度 ： k
• codewords 长度：n
• minimum hamming distance ：$d_{min}$

编码方案写成$C(n,k)$和一个单独的$d_{min}$表达式。如上的编码方案可以写成：$C(5,2),d_{min}=3$

1.2.4.2 汉明距离和错误

• 检测出s个错误，那么汉明距离满足：$d_{min}=s+1$
• 纠正s个错误，那么汉明距离满足：$d_{min}=2s+1$

1.3 线性块编码

1.3.1 线性块编码的特点

• 两个有效码字异或后得到另一个有效码字
• 线型块编码的最小汉明距离：具有最小1的个数的非0有效码字中1的个数

1.3.2 线性编码

1.3.2.1 简单奇偶校验码

• 基本思路：n = k+1。冗余位使codewords中的1的个数为偶数。
• 最小汉明距离$d_{min}=2$
• simple parity check codes单个位检错编码，不能纠正任何差错

1.3.2.2 二维奇偶校验

数据以表格形式组织，分别放在各自的行中。

对于每一行和每一列，计算出一个奇偶校验位。

two dimensional parity check可以检测出表中任意位置发生的三个差错。

1.3.2.3 汉明编码

只讨论最小汉明距离为 $d_{min}=3$ 的汉明码，它最多能检测出 2 位差错和最多纠正 1 位差错。

当$d_{min}=3$时，m和n的关系：$n=2^m-1$

汉明码要求：
{ m = r > = 3 k = n − m n = 2 m − 1

⎩ ⎨ ⎧​m=r>=3k=n−mn=2m−1​

s在正确情况下一定是0，三个校正子异或得结果

注意接收方和发送方要使用相同的等式。

生成器不关心奇偶位($q_0,q_1,...,q_n$)的错误和无差错。其他情况相应的位必须要反转，但是若出现2位错误反转后也未必正确。

1.4 循环码

1.4.1 循环校验

数据位，码字和除数等位数关系

• 数据位：k位
• 码字：n位
• 被除数补充：n-k位
• 除数：n-k+1位

1.4.2 循环码分析

一些表示：
$$\begin{gathered} 数据字d(x)码字c(x)生成多项式g(x) \\ 校正子s(x)差错e(x) \end{gathered}$$

• $s(x)\ne 0$：一位或者多位被破坏
• $s(x)=0$：
  • 没有被破坏
  • 某些位破坏但检测不出来

接收到的码字：$c(x)+e(x)$===初始发送的码字+错误项
$$\frac{接收到的码字}{g(x)}=\frac{c(x)+e(x)}{g(x)}=\frac{c(x)}{g(x)}+\frac{e(x)}{g(x)}=\frac{e(x)}{g(x)}$$

Single bit error 单个位差错：

$$\begin{gathered} e(x)=x^i \\ \frac{e(x)}{g(x)}=\frac{x^i}{g(x)} \end{gathered}$$

若g(x)有两项（一般来说），$x^0$项系数不为0，那么不能除尽，可以检错

1.5 校验和

用校验和进行简单检错的方法常用于Internet的其它高层协议中。

发送数据时，同时还发送它们的和（用于检错校验，因此称为校验和）。

校验和的步骤：【发送方】

• 报文被划分为16-bit 字。
• 校验和字的初始值设为0。
• 所有字包括校验和使用反码运算相加。
• 对累加和求反码变成校验和。
• 校验和随数据一起发送。

2. 成帧

成帧：添加发送方地址和接收方地址，成帧将一条从源端到目的端的报文分开来，或者将不同目的端的报文分开来

2.1 固定长度成帧

不需要定义帧的边界，长度本身就是限制。

2.2 可变长度成帧

帧的开始和帧的结束要加上分隔符。
方式 { 面向字符 面向位 方式

方式{面向字符面向位​

2.2.1 面向字符的协议

{ f l a g ：标志位，分隔这一帧和下一帧 H e a d e r ：源地址和目的地址 T a i l e r ：检错或者纠错冗余位

⎩ ⎨ ⎧​flag：标志位，分隔这一帧和下一帧Header：源地址和目的地址Tailer：检错或者纠错冗余位​

2.2.2 面向字的协议

需要分隔符：01111110作为分隔符，标志帧的开始和结束

位填充bit-stuffing：遇到1个0和连续5个1时，便增加一个0，不管后面的那个位是什么。额外的位被接收方移走。

3. 流量和错误控制

数据链路控制 { 成帧 流量控制 差错控制 数据链路控制

数据链路控制⎩ ⎨ ⎧​成帧流量控制差错控制​

3.1 协议

协议 { 无噪声通道 { 最简单协议 停止等待协议 噪声通道 { 停止等待 A R Q 回退 N 帧 A R Q 选择性重发 A R Q 协议

\\噪声通道\end{cases} 协议⎩ ⎨ ⎧​无噪声通道{最简单协议停止等待协议​噪声通道⎩ ⎨ ⎧​停止等待ARQ回退N帧ARQ选择性重发ARQ​​

3.1.1 无噪声通道

假设不会丢失帧，复制帧，或者损坏帧。

最简单协议不使用流量控制，Stop and Wait使用流量控制。

但是都不使用差错控制，因为是完美通道。

3.1.1.1 最简单协议

没有差错控制和流量控制。假设接收方能及时处理所有接收到的帧，不会超载。

两个驱动事件：

• 对发送方来说：触发事件为来自网络层的报文
• 对接收方来说：触发事件来自物理层

3.1.1.2 停止等待协议

如果接收方的数据帧的到达速度大于能被处理的速度，那么帧在使用前必须被存储。为避免接收方超负荷，让发送方减缓速度。

协议内容：当发送方发送了一个帧后必须停下来，直到收到来自接收方的ACK（可以继续了），然后再发送一个帧。

半双工链路

发送方两个驱动事件：

• 来自网络层的报文
• ACK

3.1.2 噪声通道

3.1.2.1 Stop-and-Wait ARQ

在停止等待协议中增加了错误控制。

错误控制的条件：

• 对数据帧增加额外的冗余位
  • 帧到达，错误，丢弃，由silence实现【注意，若是帧的序号不匹配但是是正确帧，那么也会发送ACK 】
  • 正确，保留
• 为帧编号
• 保留已发帧的副本，启动定时器，如果定时器到时且没有收到ACK那么重发该帧，保留副本并且重启定时器。
• ACK有冗余位和序列号

（1）序列号 sequence number

对帧进行编号，序列号是可以循环的。

序列号基于模2运算

有必要使用的序号是x和x+1。

（2）ACK号 acknowledgment

ACK号 = 接收到帧的序号 + 1

表示：

• 已经收到帧x
• 期待收到帧x+1

（3）设计

$S_n$：保存下一个将要发送帧的序列号

$R_n$：保存下一个期待接收的帧的序列号

/********************  发送方  ******************/
Sn = 0;
canSend = true;
while(true){
    WaitForEvent();
    if(Event(RequestToSend) and canSend){
        GetDate();
        MakeFrame();
        StoreFrame();	// 保存该帧的副本
        StartTimer();	// 计时器启动
        Sn = Sn+1;		// 指向下一帧
        canSend = fasle;
    }
    WaitForEvent();			// sleep until event occur
    if(Event(ArrivalNotification)){		// ACK arrive
        ReceiveFrame(ackNo);
        if(not corrupted and ackNo = Sn)	//有效帧
        {
            StopTimer();
            PurgeFrame(Sn-1);
            canSend = true;
        }
    }
    if(Event(TimeOut)){
        StartTimer();
        ResendFrame(Sn-1);	// 重发
    }
}

/**********************  接收方  **********************/
Rn = 0;
while (true) {
    WaitForEvent();	// 等待事件发生
    if (Event(ArrivalNotification)) { 	// Data frame arrives
        ReceiveFrame();
        if (corrupted(frame)){
            sleep();
        }
        if (seqNo == Rn) {			
            ExtractData();
            DeliverData();
            Rn = Rn + 1;
        }
        SendFrame(Rn);   	// 序号不匹配时也会发出ACK
    } 
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

停等ARQ的例子:

• 第0帧发送并确认。
• 第1帧丢失，超时后重传。重传的第1帧确认，定时器停止计时。
• 第0帧发送，但确认帧丢失。超时后，再次重传第0帧，并被确认。

（4）带宽迟延积

在一个停等ARQ系统中，带宽为1Mbps，往返传播时间是 20ms，求带宽时延积。如果帧长度为 1000bit，则链路的利用率是多少？

带宽时延积为:

​ $1\times 10^6\times 20\times 10^{-3}=20000bit$

一次往返只能发送1000bit，所以利用率为

​ $1000/20000=5\%$

大量带宽资源被浪费

3.1.2.2 回退N帧 ARQ

停止等待ARQ中大部分带宽被浪费，目标是提高传输的效率。

（1）序列号 sequence number

允许序列号有m位，模$2^m$，序列号范围是$0$~$2^m-1$

序列号可重复

（2）滑动窗口 sliding window

滑动窗口定义发送方和接收方关心的序列号范围。【发送方和接收方只需处理可能的序列号部分】
s l i d i n g   w i n d o w { 发送滑动窗口 接收滑动窗口 sliding\ window

sliding window{发送滑动窗口接收滑动窗口​

• 发送滑动窗口

窗口的最大大小是$2^m-1$

窗口分为4部分：
{ 已确认，不用保存副本 待确认帧，保存副本 能够发送，但未从网络层接收数据 直到滑动窗口才能使用

⎩ ⎨ ⎧​已确认，不用保存副本待确认帧，保存副本能够发送，但未从网络层接收数据直到滑动窗口才能使用​

三个参数：

• $S_f$：发送窗口，第一个待处理帧
• $S_n$：发送窗口，第一个待发送帧
• $S_{size}$：窗口大小，一般为$2^m-1$

有效确认到达时，发送窗口能够发送一个或者多个时隙。

• 接收滑动窗口

接收窗口是一个抽象概念，用变量 Rn定义了大小为 1 的接收窗口。正确的帧到达时，接收窗口滑动到下一个时隙。

$R_n$定义了期待接收的帧，除了$R_n$外任何失序帧到达都会被丢弃。

（3）定时器 timer

协议只使用一个定时器，第一个待处理的帧的定时器总是先到时，到时时，我们重发所有的待处理帧。

（4）Acknowledgment

如果一个帧安全有序到达，那么接收方发送一个肯定的确认

如果帧被损坏或者失序，那么接收方不响应并且丢弃所有后来的帧，直到它收到一个它期待的帧。【与停止等待ARQ区别：失序时不会发送ACK 】

接收方可为多帧发送一个累计确认cumulative acknowledgment

（5）帧的重发

定时器到时时，发送方会重发所有的待确认的帧。

（6）设计

多个帧能在前向方向传输，在反向传输多个确认。

/*****************************  回退N帧ARQ  ****************************/
Sw = 2^m - 1;	// 窗口大小
Sf = 0;			// 待处理的帧：第0帧
Sn = 0;			// 待发送的帧：第0帧

while (true) {
    waitForEvent();
    if (Event(RequestToSend)) {
        if (Sn - Sf >= Sw) {	// 窗口满了
            sleep();
        }
        GetData();
        MakeFrame(Sn);
        StoreFrame(Sn);	// 副本
        Sn = Sn + 1;
        if (timer not running) {
            StartTimer();
        }
    }
    
    if (Event(ArrivalNotification)) { // ACK arrive
        Receive(ACK);
        if (corrupted(ACK)) {
            sleep();
        }
        if ((ackNo > Sf) && (ackNo <= Sn)) { 
            while (Sf <= ackNo) {		// 累计确认
                PurgeFrame(Sf);
                Sf = Sf + 1;
            }
            StopTimer();
        }
    }
    
    if (Event(Timer)) {
        StartTimer();
        Temp = Sf;
        while (Temp < Sf) {
            sSendFrame(Temp);
            Temp = Temp + 1; 
        }
    }
}

/**********************************  接收方  ****************************************/
Rn = 0;
while(true)
{
    WaitForEvent();
    if(Event(ArrivalNotification))	//Data frame arrives
    {
        Receive(Frame);
        if(corrupted(Frame))
            Sleep();
        if(seqNo == Rn)			// If excepted frame
        {
            DeliverData();		// Deliver data
            Rn = Rn + 1;		// Slide window
            SendACK(Rn);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

（4）Go-Back-N ARQ Versus Stop- and -Wait ARQ

停止等待ARQ其实是回退N帧ARQ的一种特殊情况：只有两个序列号且窗口的大小是1

3.1.2.3 选择性重发ARQ Selective Repeat ARQ

回退N帧ARQ存在的问题：

• 接收方只有一个变量，不能解决帧失序问题
• 在有噪声通道效率低小，因为需要重发多个帧

（1）窗口大小

• 发送窗口

窗口尺度为$2^{m-1}$

窗口的缩小意味着对管道有效填充性减少，但事实上副本帧会少很多。

• 接收窗口

接收窗口大小和发送窗口一样$2^{m-1}$

允许和接收窗口一样多的帧失序到达，并保留到有一组有序帧能交付给网络层：

每个窗口位置只发送一个NAK并指明窗口中的第一个时隙

（2）设计

定时器的数量与Go-Back-N不同，每发送或者重发一个帧都需要有一个定时器，定时器也要编号：只有在这个帧的ACK达到后才会停止计时器。

Note:

• 一组连续的帧到达且从窗口开始，则可向网络层交付
• 每个窗口位置只发送一个NAK并指明窗口的第一个时隙
• 当数据被交付到网络层才发送ACK【一个窗口一个ACK，一个窗口一个NAK】

3.2 HDLC高级数据链路控制

HDLC是一种面向位的点到点和多点链路进行通信的协议。实现了ARQ

3.2.1 配置和传输模式

{ 正常响应方式 n o r m a l   r e s p o n s e   m o d e 异步平衡响应方式 a s y n c h r o n o u s   b a l a n c e d   m o d e

{正常响应方式normal response mode异步平衡响应方式asynchronous balanced mode​

• 正常响应模式

一个主站（primary station）和多个从站（secondary station）

主站只能发命令，从站只能响应。

• 异步平衡模式

每个站既是主站又是从站。

3.2.2 帧的类型

信息帧，监控帧，无编号帧
t y p e   o f f r a m e { i n f o r m a t i o n   f r a m e s , I − f r a m e s ：传输用户数据以及用户数据相关的控制信息 s u p e r v i s o r y   f r a m e s , S − f r a m e s ：传输控制信息 u n n u m b e r e d   f r a m e s , U − f r a m e s ：作为系统管理 type\ of frame

type offrame⎩ ⎨ ⎧​information frames,I−frames：传输用户数据以及用户数据相关的控制信息supervisory frames,S−frames：传输控制信息unnumbered frames,U−frames：作为系统管理​

3.2.2.1 帧的格式

3.2.2.2 控制域

• 信息帧的控制字段

如果控制字段的第一位是0，那么这是一个信息帧。

N(S)定义序号0-7

P/F是单个位，设定为1的时候有意义，意味着轮询或者终止。发送方为主站时（地址字段包含接收方的地址，意味着轮询；帧由从站发向主站时，意味着终止）

• 管理帧的控制字段

如果控制字段的前两个位是10，那么是管理帧。

管理帧没有信息字段。

最后三个位，称为N(R)，与确认号（ACK）或者否定确认（NAK）对应，取决于管理帧的类型。

code字段定义管理帧的类型：
c o d e 对管理帧类型的定义 { 准备接收 R R ： 00 不准备接收 R N R ： 10 拒收 R E J ： 01 选择性拒收 S R E J ： 11 code对管理帧类型的定义

code对管理帧类型的定义⎩ ⎨ ⎧​准备接收RR：00不准备接收RNR：10拒收REJ：01选择性拒收SREJ：11​
a. Receive Ready【RR】：编码字段是00，即ACK，N（R）即是确认号

b. Receive Not Ready【RNR】：编码字段是10，对一个或一群帧进行确认，宣布不能接收更多的帧，要求发送方减速

c. Reject 【REJ】：编码字段是01，是一个NAK帧，是一个能在回退N帧中使用的NAK，告知最后一个帧丢失或者损坏，N（R）的值是否定确认号

d. Selective Reject：编码字段是11，选择性重复ARQ的NAK帧，选择性拒收。

• 无编号帧的控制字段

无编号帧负责在连接的设备之间交换会话管理和控制信息。无编号帧包含一个信息字段，信息字段用作系统管理而不是用户数据。

4. 多路访问

上述的链路访问是假定发送方和接收方之间有专门的专用链路的。

实际上：非专用链路，数据链路层需要提供 data link control && media access control
数据链路层分成两个子层 { data link control Multiple-access resolution { 随机访问协议 受控协议 通道化协议 数据链路层分成两个子层

\end{cases} 数据链路层分成两个子层⎩ ⎨ ⎧​data link controlMultiple-access resolution⎩ ⎨ ⎧​随机访问协议受控协议通道化协议​​

4.1 随机访问协议

in random access or contention：没有任何站点是优于其他站点的，没有站点能控制其他站点。

当一个站点要发送数据时，都使用协议来决定要不要发送。

Random Access Protocol的特点：

• 站点没有规定特定的时间表
• 没有规则来规定下一个将要发送的站点是哪一个

但是一个以上的站点发送时就会产生冲突---->帧损坏

4.1.1 ALOHA

4.1.1.1 Pure ALOHA

概念：一个站点有帧要发送，那么发送这个帧。存在冲突 ----> 帧损坏 ----> 重发

纯ALOHA依赖于接收方的确认。发送后等待接收方的确认，如果超时后还未到达，站点就认为帧被损坏了。

[resend]

• back-off time：如果超时后都重发帧，那么可能再次冲突collide again，超时后随机等待一定时间wait a random amount of time。称这个时间为back-off time $T_B$

• 一个站点在经过最大次数$K_{max}$之后，必须放弃尝试，并且等待以后尝试

  

  其中超时时间$Waittimeouttime=2\times T_p$，为两倍的传输时间

  $T_B$的公式取决于实现，其中一种方法是二进制回退binary exponential back-off：

  • 每次传输随机选择0~$2^k-1$范围内的一个数，该数乘以$T_p$（最长传播时间），或者乘以$T_{fr}$，得到$T_B$的值。
  • 每一次冲突后，k的值变大，随机等待的时间变长
  • $K_{max}$的常用值是15

【脆弱时间 vulnerable time】

vulnerable time：可能发生冲突的时间

纯ALOHA的$vulnerabletime=2\times T_{fr}$

【吞吐量Throughput】

吞吐量是指每秒实际发送的，与带宽不同。

G：1个帧传输时间$T_{tf}$内，系统产生帧的平均数

S：纯ALOHA成功传输帧的平均数量
$$S=G\times e^{-2G}$$
当$G=\frac{1}{2}$时，$S_{max}=0.184$.

4.1.1.2 时隙ALOHA

在时隙ALOHA中，将时间分隔成$T_{fr}$秒的时隙，并强制站点只有在时隙开始的时候才能发送。

冲突发生在同时在一个时隙中发送的情况：

脆弱时间$vulnerabletime=T_{fr}$

【throughput】

$S=G\times e^{-G}$，当G=1时，$S_{max}=0.368$

4.1.2 载波监听（CSMA）

载波侦听多路访问CSMA(Carrier Sense Multiple Access)要求每一个站点在发送前先要监听介质，以减少冲突发生的概率。但是它不能消除冲突，冲突概依然存在的原因是传播的延迟。

$vulnerabletime=T_P$

4.1.2.1 监听策略

• 1-坚持
• 非坚持
• p坚持

4.1.3 CSMA/CD

CSMA/CD给出了检测到冲突之后的做法：
是否成功：监控介质观察 { 成功，完成发送 失败，重发 是否成功：监控介质观察

是否成功：监控介质观察{成功，完成发送失败，重发​
任意站点都可以发送帧，之后监控介质查看传送是否成功。如果成功，站点完成发送；如果不成功，说明存在冲突，需要重新发送此帧。

同时，要想监测到异常，那么要满足条件：
$$T_{fr}\ge 2T_p$$

4.1.3.1 Minimum Frame Size

满足$T_{fr}=2T_p$的，即是最小帧长。

叙述CSMA/CD的流程——

• 在开始发送帧之前，增加了持续程序
• 传输和冲突检测同时进行，持续监测两个过程：传输完成或者是监测到冲突，这两个事件都能使传输停止
• 同时，若是有检测到冲突发生，那么发送一个短小的干扰信号。

与纯ALOHA相比：

• 增加了持续程序
• 传输与冲突检测是一个过程，ALOHA的冲突检测是等待ACK
• 增加干扰

4.1.4 CSMA/CA

由于在无线网络中大量发送信号的能量在传输中丢失，所以冲突检测起不了什么作用，需要避免冲突。

避免冲突的办法：

• 帧间间隔 interframe space，IFS

监听到空闲时，并不马上发送，等待一段时间后再发送【使得源端的信号能传输到】，这段时间等于竞争时间。

IFS能定义一个站点/帧的优先权：IFS时间越短，优先级越高

• 竞争窗口 Contention Window

竞争窗口将时间分隔成时隙，选择一个随机时隙作为等待时间。

时隙个数：补偿策略中的二元指数变化。（IFS后不空闲则时隙数量加倍。）

在CSMA/CA中如果站点发现通道忙，那么不重启竞争窗口的计时器，而是停止计时器发现通道空闲时再启动计时器。

• 确认 acknowledgment

ACK+定时器

• 过程

4.2 受控访问协议

受控访问的形式：

• 预约
• 轮询
• 令牌环

4.2.1 预约

时间划分为时隙：N个站点，N个预约子时隙，每个时隙均属于一个站点。

每个时隙内先发送一个预约帧reservation station，预约完的站点可以在预约后发送数据帧。

4.2.2 轮询

Polling一个设备作为主站primary station；另一些设备作为从站secondary station;

所有的数据交换都要通过主站点进行，即使最终的目的站点是从站点。

主设备决定那个设备允许使用通道，主设备始终是一个会话的发起者。

polling：主设备希望接收数据，叫做轮询

select：主设备希望发送数据

4.2.3 令牌环

网络中的站点被组织在逻辑环中，每个站点有前驱后后继。

当前正在使用令牌的节点：令牌从前驱来，不用时往后继去

4.3 通道化

不同的站点在时域、频域、码域上正交化来共享信道
{ F D M A T D M A C D M A

⎩ ⎨ ⎧​FDMATDMACDMA​

4.3.1 FDMA

可用带宽被划分为频带，每个站点都是用分配的频带来通信。

guard bands：保护频带

4.3.2 TDMA

所有站点在时间上共享带宽。

每个站点被划分时隙，只有在该时隙才能发送数据。

4.3.3 CDMA

CDMA：

• 一个通道占用所有的带宽
• 所有节点可以同时发送，无时间限制

思想：

n个站点分配n个编码：c1,c2,…,cn

编码特性：

• 两个不同的编码相乘为0
• 自身相乘为4

5. 有线局域网——以太网

局域网(local area network LAN)应用于有限的地理范围。

5.1 IEEE Standards

IEEE将数据链路层划分为两个子层：
数据链路层的两个子层 { 逻辑链路控制层 L L C 介质访问控制层 M A C 数据链路层的两个子层

数据链路层的两个子层{逻辑链路控制层LLC介质访问控制层MAC​

5.1.1 Data Link Layer

5.1.1.1 Logical Link Control (LLC)

逻辑链路层是用来：

• 成帧
• 流量控制
• 差错控制

LLC为所有IEEE局域网提供一个单一的数据链路控制协议。

5.1.1.2 Framing

LLC定义了一个协议数据单元PDU，一定程度上与HDLC相似。

• 头部包含控制字段

  用以流量控制和差错控制

• 另外两个头部界定了使用LLC的源和目的的上层协议，称为目的业务接入点 destination service access point [DSAP]和源业务接入点source service access point [SSAP]。

HDLC中定义的帧被分为LLC子层的PDU和MAC子层的一个帧：
H D L C 帧 { L L C   P D U M A C 帧 HDLC帧

HDLC帧{LLC PDUMAC帧​

5.1.1.3 LLC的需求

LLC的目的是为需要流量控制和差错控制的上层协议提供这些服务。

IP协议不需要LLC服务。

5.1.1.4 media access control

介质访问控制层为每个局域网定义特定的访问方法。
M A C 定义的访问方法 { 以太网： C S M A / C D 令牌环：令牌传递 令牌总线局域网：令牌传递 . . . . . . MAC定义的访问方法

MAC定义的访问方法⎩ ⎨ ⎧​以太网：CSMA/CD令牌环：令牌传递令牌总线局域网：令牌传递......​

5.1.2 physical layer

每种以太网的实现都有不同的物理层规范。

5.2 标准以太网

以太网的发展：

• 标准以太网
• 快速以太网
• 千兆以太网 Gigabit Ethernet
• 10千兆以太网 Ten Gigabit Ethernet

5.2.1 MAC子层

MAC子层将上层的数据成帧并传输给物理层。

5.2.1.1 帧的格式

以太网的帧包括7个字段：preamble，start frame delimiter (10101011)，destination address, source address, Length or type, Data and padding和CRC

5.2.1.2 帧的长度

• 以太网帧的最小长度：64bytes
• 以太网帧的最大长度：1518bytes

对应到有效载荷：

• 最小的有效载荷为64 - 18 = 46
• 最大的有效载荷为1518 - 18 = 1500

5.2.1.3 地址

以太网的地址是6字节（48位）的，通常用十六进制表示，字节间用冒号断开。

Unicast，Multicast，and Broadcast Address

源地址永远是一个单播地址——帧只来自一个站点

目的地址可以是单播地址也可以是多播地址，还可以是广播地址

地址的区分和传送

{ 单播地址：地址的第一个字节的最后一位是 0 多播地址：地址的第一个字节的最后一位是 1 广播地址：地址全为 1

⎩ ⎨ ⎧​单播地址：地址的第一个字节的最后一位是0多播地址：地址的第一个字节的最后一位是1广播地址：地址全为1​

5.2.2 物理层

5.2.2.1 编码和解码

曼彻斯特编码

5.2.2.2 标准以太网分类

（1）10Base5

粗缆以太网，使用收发器，收发器负责：

• 传输
• 接收
• 检测冲突

收发器通过收发器线缆与站点相联，收发器电缆能为发送和传输提供独立的路径，冲突只会发生在粗轴电缆中。

粗轴电缆的最大长度不能超过500米。最多分成5段，使用中继器连接。

（2）10Base2

收发器是网卡的一部分。每个分段的长度最多是185米。

（4）10Base-T：双绞线以太网

使用物理星型拓扑结构，使用双绞线连接到网络集线器上。

双绞线在站点和网络集线器之间形成了两条路径（一条发送一条接收），冲突发生在集线器中。

（5）10Base-F：光纤以太网

使用星型拓扑结构将站点与网络集线器联机。

5.3 标准的改变

5.3.1 桥接以太网

以太网发展的第一步是将局域网利用网桥分割。

网桥分隔，提高了带宽，分隔了冲突域。

5.3.2 交换式以太网

多个端口的网桥可以变成N个端口的交换机，站点的带宽由交换机和站点共享。冲突域分为N个：

一个2层交换机就是一个N个端口的网桥：

5.3.3 全双工以太网

10Base5和10Base2是半双工的（10BaseT始终是全双工的）

下一步就是从交换式以太网到全双工以太网。全双工模式将一个域的能力从10Mbps增加到20Mbps。

在全双工模式中，在站点与交换机之间不是使用一条链路，而是使用两条链路：

一个用于传送，一个用于接收：

6. 无线局域网

无限LAN包括：

• IEEE802.11无线局域网
• 蓝牙

6.1 IEEE 802.11

IEEE定义的无线局域网的规范为IEEE802.11，该规范覆盖数据链路层和物理层。

6.1.1 架构

{ 基本服务集 B a s i c   s e r v i c e   s e t 扩展服务集合 E x t e n d e d   s e r v i c e   s e t

{基本服务集Basic service set扩展服务集合Extended service set​

6.1.1.1 基本服务集

基本服务集：无线网络的积木

组成：

• 固定的或者移动的站点
• 可选的中间基站，称为访问点access point（AP）

其中，带AP的为基础网络，不带AP的为特别网络

• 基础网络infrastructure network：能够向其他的BSSs发送消息
• 特别网络ad hoc：不能向其他的BSS发送数据，他们能够相互定位，并且承诺是BSS的一部分

B S S { a d   h o c { 固定的站点 移动的站点 i n f r a s t r u c t u r e   n e t w o r k { 固定的站点 移动的站点 访问点 A P BSS

\\infrastructure\ network\end{cases} BSS⎩ ⎨ ⎧​ad hoc{固定的站点移动的站点​infrastructure network⎩ ⎨ ⎧​固定的站点移动的站点访问点AP​​

6.1.1.2 扩展服务集

ESS由两个或者更多个带有AP的BSS组成。

各个BSS之间由分布式系统distribution system连接。分布式系统连接BSS中的AP。

对分布式系统没有严格限制，可以是任何类型的局域网，如：以太网。

扩展服务集ESS使用两种类型的站点：
{ 移动的 固定的

{移动的固定的​

在连接BSS时

• 可以互达的站点之间可以相互通信而不必使用AP
• 位于两个BSS的两个站点间一般要跨过两个AP

6.1.1.3 站点类型

三种站点类型：

• 不迁移
• BSS迁移
• ESS迁移

{ 不迁移 n o n − t r a n s i t i o n { 固定不移动的站点 只在 B S S 内移动 B S S 迁移 B S S − t r a n s i t i o n ：只在一个 B S S 内移动，但被限制在 E S S 内 E S S 迁移 E S S − t r a n s i t i o n ：可以从一个 E S S 移动到另一个 E S S

\\BSS迁移 BSS-transition：只在一个BSS内移动，但被限制在ESS内\\ESS迁移ESS-transition：可以从一个ESS移动到另一个ESS\end{cases} ⎩ ⎨ ⎧​不迁移non−transition{固定不移动的站点只在BSS内移动​BSS迁移BSS−transition：只在一个BSS内移动，但被限制在ESS内ESS迁移ESS−transition：可以从一个ESS移动到另一个ESS​

6.1.2 MAC子层

IEEE802.11定义了两个MAC子层：分布式协调功能（DCF）和点协调功能（PCF）

6.1.2.1 Distributed coordination function（DCF）

DCF使用的是CSMA/CA而不是CSMA/CD。

不能使用CSMA/CD的原因：

• 冲突检测对站点要求高，且带宽需求高
• 隐藏站点存在，可能检测不到冲突
• 站点间距离可能很大，信号衰减可能使得一端的站点无法侦听到另一端的冲突。

a.处理流程图

b.Frame exchange time line

1. 在发送一个帧前，源站点通过检测载波频率的能量来侦听介质
   • 在通道空闲之前使用带有补偿的持续策略
   • 站点发现通道空闲之后，他等待一个被称作**分布式帧间间隔（DIFS）的时间周期，然后发送一个叫做请求发送（RTS）**的控制帧。
2. 接收到RTS并且等待一个叫做短帧间间隔（SIFS）的短在时间后，目的站点向源站点发送清除发送CTS的控制帧，表明站点准备接收数据。
3. 在等待一个SIFS后，源站点发送数据
4. 在等待一个SIFS后，目的站点发送确认说明已经接收到帧。

由于不检测，所以无法得知是否发生冲突，所以需要ACK。

c.NAV 网络分配矢量

网络分配矢量：当一个站点发送RTS帧时，它包含了需要占据通道的时间。受到这一传送影响的站点建立一个叫做网络分配矢量NAV的计时器，该定时器指出：

在允许这些站点检测通道是否空闲之前还需要等待多长时间。即：NAV不到时，不需要侦听通道。

d.Collision During Handshaking

在RTS或者CTS正在发送时，这一期间叫做握手周期handshaking period。如果两个或者多个产生了冲突，但是没有检测冲突的机制，因此发送方在没有从接收方接收到CTS就以为产生了冲突，于是采取补偿策略并重新发送。

6.1.2.2 点协调功能（PCF）

a.PCF的概念与功能

点协调功能PCF在基础网络的BSS中是可选的。主要用作对时间敏感的传输。

PCF是集中式的，无竞争的轮询访问方式，站点依次被轮询，将数据发给AP。

b. PCF的IFS

PCF的优先级高于DCF，定义了另一套帧间间隔：

• PIFS：PIFS比DIFS短
• SIFS：和DCF中的SIFS一样

意味着：一个站点只使用DCF，而一个AP使用PCF，那么AP有优先权。

c. 重复间隔的设计

由于PCF的优先级比DCF的优先级高，可能导致只使用DCF的站点得不到对介质的访问。于是设计了重复间隔repetition interval。

重复间隔repetition interval 会持续重复，开始于一个信号帧beacon frame的特殊控制帧，终结于PC发送CF。

6.1.2.3 帧格式

MAC层包括9个字段：

6.1.3 地址

FC中的两个字段from DS和to DS定义，每个字段可能是0或者1。

定义四种情况：

• 地址1：总是下一个设备的地址
• 地址2：总是前一个设备的地址
• 如果目的地址没有被地址1定义，那么地址3是目的地址；如果源地址没有被地址2定义，那么地址3是源地址。

7. 常见网络设备

7.1 Connecting Devices

连接设备分为5类：

7.1.1 无源集线器

无源集线器只是个连接器，连接来自不同分支的线路。

在星型拓扑中，无源集线器只是一个来自不同站点的信号冲突点，集线器是冲突点。无源集线器工作在物理层以下。

7.1.2 中继器

7.1.2.1 工作层次

repeater仅工作在物理层。

7.1.2.2 功能

• 信号的重生

中继器能够接收信号，在信号变得很弱或者被破坏前，重新生成原始的位模式，然后发送新生成的信号。中继器只重新生成信号，并不放大信号。

• 连接一个局域网的两段

**中继器实际并不能连接两个局域网，连接的是同一局域网的两个分段。**所连接的网段仍然是一个局域网的一部分。中继器不能连接采用不同协议的两个局域网。

中继器可以克服10Base5以太网标准的长度限制。使用中继器连接各个网段segement。

• 没有过滤能力

过滤帧的能力：读取帧首部信息，决定是否转发，如何转发。

中继器转发每一帧，没有过滤能力。

中继器常用于星型拓扑结构中，可以多级级联。

7.1.3 有源集线器

7.1.3.1 工作层次

有源集线器是一个多端口的中继器。常用于星型拓扑中。

集线器和网线一样工作在物理层，功能和网线一样，只是将数字信号发送到其他的端口，不能识别帧首部的信息。

7.1.3.2 功能

数字信号发送到其他的端口。

7.1.3.3 带宽和广播域

• 带宽

集线器组建的以太网共享带宽，计算机数量越多，平均带宽就越低。

• 安全性

无论MAC地址是否是自己的，都能捕获。

• 冲突域

级联以后的以太网计算机处于一个冲突域内。增大了冲突的概率，每台计算机分到的带宽也降低了。

• 接口带宽

相联的接口带宽要一样。如果数据速率不一致，那么工作在较低的数据速率，因为集线器接口不能缓存帧。

7.1.4 网桥

7.1.4.1 工作层次

网桥工作在物理层和数据链路层。

• 用作物理设备时，重新生成接收到的信号。
• 作为数据链路层设备时，可以检查帧包含的MAC地址

7.1.4.2 过滤

网桥与中继器不同的地方在于网桥有过滤功能。

网桥具有一个用过过滤决策的表，有过滤作用。转发帧时必须指定端口。检查帧的目的地址。

7.1.4.3 网桥组网的特点

网桥基于MAC地址转发帧，转发之前运行CSMA/CD算法。

网桥的一个接口是一个冲突域，冲突域的数量增加，但是冲突的概率减少。

实现帧的存储转发，增加了时延。

网桥的接口可以是不同的带宽。

7.1.4.4 透明网桥

透明网桥指的是站点意识不到桥的存在。

802.1d规定了透明网桥的特点：

• 帧必须能从一个站点转发到另一个站点
• 学习帧中的地址，自动建立转发表
• 避免形成循环Loop问题

7.1.5 两层交换机

两层交换机是一个拥有许多端口并且有更好更快性能的网桥。

多端口的网桥可以给每个站点分配唯一的端口，每个站点都作为独立的实体。没有冲突。

7.1.5.1 两层交换机的特点

• 端口独享带宽，Hub是共享带宽
• 安全：交换机根据MAC地址只转发到目标端口
• 全双工通信
• 不再使用CSMA/CD
• 接口可以工作在不同的频率，交换机使用存储转发技术
• 转发广播帧：转发除了发送端口以外的其他端口

7.1.5.2 二层交换机的类型

a.存储转发式 Store and forward

从输入线路上接收帧，缓存，通过路由选择将其发送到适当的输出线路上。发送方和接收方存在延迟，增进了网络的整体一致性。

b.直通式 Cut through

利用了目的地址总是出现在MAC帧的最前面的特点。交换机识别出目的地址后就将帧转发到适当的输出线路能够达到很高的吞吐量。

7.1.6 路由器

路由表中包含了下面的信息：

• 目的地址
• 掩码
• 输出接口
• 下一跳的IP地址：说明IP数据报所经由的下一个路由器的接口地址

7.1.7 Three Layers Switches

三层交换机是路由器，但是更快且更复杂

7.2 Virtual LAN

7.2.1 VLAN的概念

通过软件而不是物理线路来配置一个局域网，称为虚拟局域网。

7.2.2 VLAN的特点

• 一个LAN可以划分为多个VLAN，每个VLAN是一个工作组。
• 允许连接在不同的交换机上的站点组成一个VLAN。
• 同一个VLAN中的站点通信时，就像他们属于同一个物理网段一样。
• VLAN将属于一个或者多个物理站点的LAN分组到一个广播域中。

7.2.3 VLAN的划分方式

基于端口：使用交换机的端口

基于MAC地址：使用48位MAC地址，规定某个MAC地址的主机属于某个VLAN

基于IP地址：32位IP地址

基于多播IP地址

7.2.4 默认VLAN

默认VLAN是交换机初始就有的VLAN，通常ID为1，所有的接口都处于这个VLAN下，这就是所有设备连接到交换机上就能相互通信的原因。

VLAN ID最多有$2^{12}$个，VLAN0和VLAN4095保留。

7.2.5 交换机的三种链路类型

• access模式：与计算机端口直连
• trunk模式：允许多个VLAN帧通过
• hybrid模式