计网Chapter3

1.数据链路层的概述

链路：一个结点到相邻结点的一段物理线路，中间无其他交换结点
数据链路：指把实现通信协议的硬件和软件加到链路上，构成数据链路
数据链路层的单位：帧

2.封装成帧

定义：指数据链路层给上层交付的协议数据单元添加帧头和帧尾使之成为帧
1.帧头，帧尾含有重要的控制信息
2.帧头，帧尾的作用之一是帧定界
3.帧间间隔：96比特时间
透明传输：指数据链路层对上层交付的传输数据无限制
1.面向字节的物理链路使用字节填充实现透明传输
在跟帧定界相同的数据前加上转义字符(十进制值为27,占1字节 )
2.面向比特的物理链路使用比特填充实现透明传输
零比特填充：面对连续的5个1后面填充一个0
提高帧的传输效率，应使帧的数据部分长度尽可能大些
最大传送单元MTU：数据链路层协议规定的帧的数据部分的长度上限 1500B

3.差错检测

奇偶校验：通过0/1数量的奇偶性进行检验，但若奇偶性没有变化，则会出现漏检
循环冗余校验CRC

收发双方约定好一个生成多项式 $G(x)$
发送方基于待发送的数据和生成多项式计算出差错检测码（冗余码），将其添加到待传输数据的后面一起传输
接收方通过生成多项式来计算收到的数据是否产生误码

除法作异或运算，不同则余1
发送方：

在待发送数据后添加生成多项式 $G(x)$ 最高次个0，作为被除数
以 $G(x)$ 各项系数构成比特串作为除数
二者作除法得到的余数作为冗余码添加到待发送的数据
检查余数：余数位数应与 $G(x)$ 最高次数项的次数相同，如不足，则在余数前补0
接收方：
以接收到的数据为被除数， $G(x)$ 各项系数构造的比特串作为除数
二者作除法，余数为0则判断为无误码，反之则存在误码

4.可靠传输

数据链路层向上层提供的服务：

不可靠传输服务：仅丢弃有误码的帧
可靠传输服务：想办法实现发送端发送什么，接收端就收到什么

有线链路误码率低，不要求可靠传输；
无线链路误码率高，数据链路层必须向上层提供可靠传输

可靠传输服务不仅局限于数据链路层

4.1 可靠传输的实现机制

4.1.1 停止等待协议（SW）

4.1.2 回退N帧协议（GBN）

通过n个比特给分组编号，序号取值范围为 $0——{2^n}-1$
发送方维持一个发送窗口 $W_T$ ， $1<W_T<{2^n}-1$ ，在 $W_T$ 内的序号可以被发送
接收方维持一个接收窗口 $W_R$ ， $W_R=1$ ， $W_R$ 以外的数据分组不允许接收

累积确认：接收方无需对收到的数据分组逐个确认，可接收按序到达的最后一个分组后，发送 $ACK_n$ ，表示序号为n及之前的数据分组都已确认

差错情况：

发送的分组(5,6,7,0,1)中，有一个分组(5)出现误码或丢失，接下来的分组即使被接收，也会重复发送之前已确认的最后一个分组(4)的确认分组，发送方接收到重复的确认分组后，会重新发送同样的数据分组(5,6,7,0,1)。
$W_T>2^n-1$ $W_{T} > 2^{n} - 1$ ，以n=3为例。
1. 假如 $W_T=8$ ，发送方会发送0-7号DATA，接收方发送 $ACK_7$ ，若 $ACK_7$ 丢失，发送方超时重传0-7号DATA，但此时接受窗口已经滑动到下一个0，此时接收方无法分辨新旧数据分组
2. 假如 $W_T=9$ ，发送方会发送0-7+0号DATA，此时接收方发送 $ACK_0$ ，发送方无法辨认这是第一个0号分组的确认还是第二个0号分组的确认

4.1.3 选择重传协议（SR）

在GBN的基础上做出改进， $W_R$ 应大于1，以便接收方手下失序到达但无误码且序号落在窗口的数据分组。不可采用累积确认。
在SR协议中，一般情况， $W_R=W_T$
$W_T$ 必须满足 $1<W_T\leq2^n-1$
若 $W_T=1$ ，则是SW协议
若 $W_T>2^n-1$ ，则无法分辨新旧分组
$W_R$ 必须满足 $1<W_R\leq W_T$
若 $W_R=1$ ，则是GBN协议
若 $W_R>W_T$ ，则无意义
$W_T+W_R\leq2^n$

5. 点对点协议PPP

目前使用最广泛的点对点数据链路层协议
为在点对点链路传输各种协议数据报提供了一个标准方法：

对各种协议数据报的封装方法（封装成帧）
链路控制协议LCP（用于建立、配置以及测试数据链路的连接）
一套网络控制协议NCPs（其中包含的每一个协议支持不同的网络层协议）

帧格式：

标志字段（Flag）：PPP帧的定界符，取值为0x7E
地址字段（Address）：取值为0xFF，预留，当前无作用
控制字段（Control）：取值为0x03，预留
协议字段（Protocol）：指明帧的数据部分送交哪个协议处理
1. 取值0x0021表示：帧的数据部分为IP数据报
2. 取值0xC021表示：帧的数据部分为LCP分组
3. 取值0x8021表示：帧数据部分为NCP分组
帧检验序列（Frame Check Sequence)：CRC计算出的校验位

透明传输

面向字节的异步链路——字节填充法
发送方：
1. 出现的每一个7E（定界符）字节转变成2字节序列（7D，5E）
2. 出现的每一个7D（转义字符）字节转变成2字节序列（7D，5D）
3. 出现的每一个ASCII码控制字符（数值小于0x20），在该字符前插入一个7D字节，原字节编码加上0x20
面向比特的同步链路——零比特填充法

差错检测

生成多项式： $G(x)=X^{16}+X^{12}+X^5+1$

工作状态：

6.媒体接入控制

基本概念

MAC：共享信道要着重考虑如何协调多个发送和接收站点对一个共享传输媒体的占用

静态划分信道（物理层）

码分复用CDM
每一个比特时间再划分为m个短的间隔，一个间隔称为一个码片。通常，m=64 or 128
使用CDMA（码分多址）的每一个站被指派唯一的m bit码片序列

发送比特1，则发送m bit码片序列
发送比特0，则发送码片序列的二进制反码
通常来说，1称为+1，0称为-1
挑选原则：

码片序列必须各不相同
码片序列必须相互正交（规格化内积为0）
1. $S*T=\frac{1}{m}*\sum_{i=1}^{m}S_i*T_i=0$
2. $S*S=1,S*\overline{T}=0,S*\overline{S}=-1$

随机接入

CSMA/CD 载波监听多址接入/碰撞检测

工作原理：

多点接入：多个主机接入一条总线，竞争使用
载波监听：发送前检测总线，若空闲96比特时间，则立即发送；若忙，则持续检测至空闲96比特时间再重新发送
碰撞检测：边发送边检测，若检测到碰撞立即停止，退避一段随机时间再重新发送

争用期：发送帧的主机最多经过以太网端到端往返传播时延 $2\tau$ 就可检测到本次传输是否碰撞
以太网规定 $2\tau=512比特时间$ ，对于10Mbps的以太网， $2\tau=51.2{\mu}s$

最小帧长： $争用期*信道带宽（数据发送速率）$ 在10Mbps以太网下，最小帧长为512b即64字节
小于最小帧长的帧都认为是因为碰撞异常的可丢弃帧
最大帧长：防止主机长时间占线。
以太网V2的MAC帧最大长度为1518字节（1500字节数据）
插入VLAN标记的802.1Q帧最大长度为1522字节（1500字节数据）

截断二进制指数退避算法
$随机退避时间=争用期2\tau*随机数r，r\in\{0-2^k-1\},k=Min\{重传次数，10\}$

重传次数	k	离散整数集合{0,1,···, $2^k-1$ }	可能的退避时间
1	1	{0,1}	$02\tau,12\tau$
2	2	{0,1,2,3}	$02\tau,12\tau,22\tau,32\tau$
12	10	{0,···,1023}	$02\tau,···,10232\tau$

以太网的信道利用率：
理想情况下的极限信道利用率：
$S_{max}=\frac{T_0}{T_0+\tau}=\frac{1}{1+\alpha}$
$\alpha=\frac{\tau}{T_0},\tau尽可能小，指端到端的距离受限，T_0尽可能大，指数据帧长尽可能的长$

CSMA/CA

802.11无线局域网使用CSMA/CA协议，同时还使用停止等待协议实现可靠传输（包含确认机制）
802.11标准规定：所有站点必须持续检测到信道空闲一段指定时间后才能发送帧
帧间间隔：

短帧间间隔SIFS $(28{\mu}s)$ :用于分隔开属于一次对话的各帧
DCF帧间间隔DIFS $(128{\mu}s)$ :用来发送数据帧和管理帧

退避算法的使用情况：

发送数据帧前检测信道忙状态
每一次重传数据帧前
每一次成功发送数据帧后要连续发送下一帧，避免长时间占用信道

信道预约：

虚拟载波监听：

7.MAC地址，IP地址，ARP协议

1.MAC地址

概念：用于媒体接入控制的地址，具体来说，每个主机发送的帧中必须携带发送主机和接收主机的地址。
一般固化在网卡的电可擦可编程只读存储器EEPROM中，也被称为硬件地址

也被称为物理地址，但不属于物理层
严格来说，MAC地址是对网络上各接口的唯一标识

表示方式：

XX-XX-XX-XX-XX-XX，如00-0C-CF-93-8C-92
XX:XX:XX:XX:XX:XX，如00:0C:CF:93:8C
XXXX.XXXX.XXXX，如000C.CF93.8C92

地址格式：
第一字节的b1位：

0：全球管理
1：本地管理
第一字节的b0位：
0：单播
1：多播

2.IP地址

IP地址是Internet上的主机和路由器所使用的地址，标识两部分信息：

网络编号：标识Internet上数以百万计的网络
主机编号：标识同一网络上不同主机（或路由器各接口）

数据包转发过程中：

源IP地址和目的IP地址保持不变
源MAC地址和目的MAC地址随网络和链路的变化而变化

3.ARP协议

源主机在自己的ARP高速缓存表中查找目的主机的IP地址和MAC地址，若有，则封装MAC帧发送；若无，则发送ARP请求（广播）

目的主机收到请求后，先记录源主机的IP地址和MAC地址，再发送ARP响应（IP地址和MAC地址） 到源主机

作用范围：逐段链路或逐个网络

还存在用于检查ip地址冲突的无效ARP、免费ARP
存在ARP欺骗（攻击）问题

8.集线器和交换机的区别

集线器HUB
1. 早期以太网的互连设备
2. 工作在OSI体系结构的物理层
3. 扩大、转发接收到的信号
4. 使用集线器作为互连设备的以太网仍属于共享总线式以太网，连接起来的所有主机仍共享一条总线
交换机SWITCH
1. 目前以太网中使用最广泛的互连设备
2. 工作在OSI体系结构的数据链路层（也包括物理层）
3. 根据MAC地址对帧进行转发
4. 使用交换机作为互连设备的以太网（交换式以太网），可以根据MAC地址过滤帧，隔离了碰撞域
5. 交换机的每一个接口是一个独立的碰撞域
6. 交换机隔离碰撞域但不隔离广播域（VLAN除外）
7. 即插即用，帧交换表通过自学习算法建立
8. 转发方式：存储转发、直通交换

9.交换机自学习和转发帧的流程

行为	表1	表2
A->B	登记，盲目转发	登记，盲目转发
B->A	登记，明确转发	收不到
E->A	登记，明确转发	登记，明确转发

登记的过程称为自学习
盲目转发的情况在于帧交换表中不存在目的MAC地址，需要通过泛洪来寻址
MAC地址与交换机接口的对应关系并非永久性，所以每条记录存在生命周期
如下为交换表1经过上述操作后的新表1

MAC地址	接口
A	1
B	3
E	4

如下为交换表2经过上述操作后的新表2

MAC地址	接口
A	1
E	3

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

增加冗余链路的优点：提高以太网的可靠性
缺点：

广播风暴：大量消耗网络资源，使网络无法正常转发其他数据帧
主机收到重复的广播帧：大量消耗主机资源
交换机的帧交换表震荡

生成树协议STP ：为了使交换机增加冗余链路的情况下避免网络环路带来的各种问题

无论交换机间采用怎样的物理连接，交换机都能自动计算并构建一个逻辑上无环路的网络，逻辑拓扑结构为树型
树型逻辑拓扑要连通整个网络
当物理拓扑发生变化时，交换机将重新进行生成树的计算

11.虚拟局域网VLAN

11.1 概述

交换式以太网规模的扩大，广播域随之扩大，而巨大的广播域会造成广播风暴、难以管理和维护还有潜在的安全问题

虚拟局域网VLAN：将局域网内的设备划分成与物理位置无关的逻辑组，逻辑组中有共同的需求

11.2 VLAN的实现机制

两个前置要求：

IEEE 802.1 Q帧：基于以太网的MAC帧进行扩展，插入4字节的VLAN标记

VLAN标记的最后12比特称为VLAN标识符VID，唯一标识以太网帧属于哪一个VLAN
取值范围： $0-2^{12}-1/0-4095$ $0 - 2^{12} - 1 / 0 - 4095$
有效取值范围： $1-4094$ $1 - 4094$ (0,4095不用来表示VLAN)
802.1 Q帧由交换机处理
1. 交换机收到普通以太网帧时，插入VLAN标记转变成802.1 Q帧，“打标签”
2. 转发802.1 Q帧，可能会删除VLAN标记转变成普通以太网帧，“去标签”
交换机的端口类型
前置：交换机各端口的缺省VLAN ID
1. 思科交换机：Native VLAN，即本征VLAN
2. 华为交换机：Port VLAN ID，即端口VLAN ID，简记为PVID（网课中所采用）
1. Access
  1. 一般用于连接用户计算机，只属于一个VLAN，PVID值与端口所属VLAN的ID相同
  2. 接收处理方法：接受普通以太网帧，进行 ”打标签“，VID取值与端口PVID相等
  3. 发送处理方法：若帧中VID与端口的PVID相等，则 “去标签”并转发
2. Trunk
  1. 一般用于交换机之间或交换机与路由器互连，可属于多个VLAN，用户可设置Trunk端口的PVID（默认是1）
  2. 发送处理方法：
    - 对VID=PVID的帧，“去标签”再转发
    - VID!=PVID的帧，直接转发
  3. 接收处理方法：
    - 接收“未打标签”的帧，根据接收端口的PVID给帧”打标签“，VID=端口PVID
    - 接收“已有标签的帧”
3. Hybrid（华为）
  1. 既用于交换机之间或交换机与路由器互连，也可用于交换机与用户计算机互连
  2. 属于多个VLAN，可自设定PVID值
  3. 发送处理方法：
    - 查看帧VID是否在端口“去标签”列表中
    - 若存在，则“去标签”后转发
    - 不存在则直接转发
  4. 接受处理方法：
    - 接收“未打标签”的帧，根据接收端口的PVID给帧”打标签“，VID=端口PVID
    - 接收“已有标签的帧”