计算机网络-数据链路层

标签：发送重传局域网计算机网络校验码数据以太网链路层

3.1 基本概念

结点：主机、路由器

链路：网络中两个结点之间的物理通道，分为有线链路、无线链路

数据链路：网络中两个结点之间的逻辑通道，把实现控制数据传输协议的硬件和软件加到链路上就构成数据链路

帧：链路层的协议数据单元，封装网络层数据报

数据链路层作用：负责通过一条链路从一个结点向另一个物理链路直接相连的相邻结点传送数据报

为网络层提供服务。分为无确认无连接服务，有确认无连接服务，有确认面向连接服务
链路管理：连接的建立、维持、释放
组帧
流量控制
差错控制

3.2 封装成帧

在数据的前后部分添加首部、尾部；首部和尾部包含许多控制信息，他们一个重要作用：帧定界

透明传输：不管所传数据是什么样的比特组合，都应当能够在链路上传送。

因而当所传数据中的比特组合恰巧与某一个控制信息完全一样时，就必须采取适当的措施

1、字符计数法

痛点：一旦字数计数为错误，则会有灾难性后果

2、字符填充法

添加起始和结束符，若数据中有和起始和结束符相同的二进制数，则添加ESC表示忽略，接收时删除该字符即可

3、零比特填充法

5“1”1“0”原则：若中间的数据部分有连续的5个1，则在后面添零；接收端首先找到起始和结束，然后数据里凡是有5个1就删除后面的0

4、违规编码法

例如：

3.3 差错控制

产生原因：由于噪声引起

（全局性）由于线路本身电气特性所产生的随机噪声（热噪声），是信道固有的，随机存在的。（提高信噪比、改善传感器）
（局部性）外界特定的短暂原因所造成的冲击噪声，是产生差错的主要原因（编码技术）

分类：

位错
帧错：丢失、重复、失序

1、奇偶校验码（检错）

2、CRC循环冗余码（检错）

$$
最终发送的数据 = 要发送的数据 + 帧检验序列FCS（冗余码）
$$

计算冗余码：（1）加0：假设生成多项式的阶为r，则加r个0；

（2）模2除法：数据加0后除以多项式，余数为冗余码

$$
接收端检查：发送的数据/生成多项式 =0
$$

3、海明码（纠错）

可以发现双比特错，只能纠正单比特错

海明不等式：

$$
2^r-r-1 >= k
$$

其中r 为冗余信息位，k为信息位

步骤：

确定校验码位数r；
确定校验码和数据位置：校验码只能在2^n中
求校验码的值：确定校验码码位二进制数中1的位置，数据码位中对应位置为1的为该校验码组，对校验码和这些数据取异或，使得结果为0，得到校验码的值（简单做法数1的奇偶，偶校验）
检错并纠错：使用各校验码与各校验码组异或，值从p4-p1排序组成二进制值，转换为十进制数即为出错的位置

3.4 流量控制

数据链路层的控制手段：点到点，接收方收不下就不回复确认

传输层流量控制手段：端到端，接收端给发送端一个窗口公告

控制方法：

停止-等待协议：每发送完一个帧就停止发送，等待对方的确认，再发送下一个帧

若数据帧丢失或检测到帧出错，超时计时器（比平均RTT长）计时结束，重传（故发送帧必须保留它的副本；数据帧和确认帧必须编号）
若ACK（确认帧）丢失，超时重传，接收端丢弃重复的帧，发回确认帧
若ACK迟到，超时重传，接收端丢弃重复的帧，发回第二帧的确认帧，超时的第一帧的确认帧发送端直接丢弃

$$
信道利用率 = （L/C）/T
$$

其中,L:T内发送L比特数据；C发送方数据传输率；T发送周期，从开始发送数据到收到最后一个确认帧为止

$$
信道吞吐量 = 信道利用率 * 发送方的发送速率
$$

滑动窗口协议

后退N帧协议（GBN）：每收到一个确认信息，窗口向前移动一格

发送>1 ,接收窗口=1

GBN必须响应的三件事：

上层的调用：会检查发送窗口是否已经满，若已满，发送方会缓存这些数据，窗口不满时候再发送
GBN协议中采用累积确认方式，标明接收方已经收到N号帧和它之前的全部帧；若接收方发送帧丢失则不会接收接下来的帧
超时事件：若超时，发送方重传所有已发送但未被确认的帧

滑动窗口的长度: 若采用n个比特对帧编号，那么发送窗口的尺寸W_T应满足

$$
1<= W_T <= 2^n -1
$$

选择重传协议（SR）：发送窗口>1,接收窗口>1

SR发送方必须响应的三件事：

上层的调用：与GBN一样
如果收到ACK，加入该帧序号在窗口内，则SR发送方将那个被确认的帧标记为已接收；若该帧序号是窗口的下界，则窗口向前移动到具有最小序号的未确认帧处，继续发送新窗口内的未发送帧
超时事件：每个帧都有定时器，超时重传错误帧

SR接收方必须响应的事：失序的帧也会被缓存，并返回确认帧，直到下界帧被收到为止；若收到了窗口序号外的帧（小于窗口下界），则返回ACK确认帧

滑动窗口的长度：发送窗口最好等于接收窗口（大了会溢出，小了没意义）

$$
W_Tmax = W_Rmax = 2^(n-1)
$$

3.5 介质访问控制

内容：采取一定的措施，使得两对节点之间的通信不会发生互相干扰的情况

3.5.1 信道划分介质访问控制

频分复用：不同用户占有不同的频带，传输互不干扰

时分复用

改进的时分复用——统计时分复用STDM

波分多路复用：使用光的频分多路复用

码分多路复用

3.5.2 随机访问介质访问控制

ALOHA协议

纯ALOHA协议：不监听信道，不按时间槽发送，想发就发；检测到冲突就重发

时隙ALOHA协议（控制想发就发的随意性）：把时间分成若干个相同的时间片，所有用户在时间片开始时刻接入网络信道，若发生冲突，一个即刻发送，另外的则必须等到下一个时间片开始时刻再发送。

纯ALOHA协议比时隙ALOHA协议的吞吐量更低，效率更低

CSMA协议

CS（carrier sense）：载波监听，根据总线上的电压摆动值判断是否总线上有多个站点发送信息

MA(multiple access)：多点接入

1-坚持CSMA：空闲则直接传输，忙则一直监听，冲突则等待一个随机长时间再监听

当多点站点发送信息时，一定会冲突

非坚持CSMA：空闲则直接传输，忙则等待一个随机长时间再监听

减少冲突的可能性

p-坚持CSMA：空闲则以p概率直接传输，不必等待；概率1-p等待到下一个时间槽再传输；忙则等待一个随机长时间再监听

既能像非坚持算法那样减少冲突，又能像1-坚持算法那样减少媒体空闲时间

CSMA/CD协议

CD(collision detection)：碰撞检测

传播时延对载波监听的影响

截断二进制指数规避算法确定碰撞后的重传时机

确定基本退避时间为2τ；定义重传次数为k，k=min{重传次数，10}
从离散的集合[0,1,...,2^k - 1]中随机取一个数r，则重传延迟时间为 r*2τ
当重传16次仍不能成功时，说明网络太拥挤，人为此帧永远无法正确发出

最小帧长问题：帧的传输时延至少要两倍于信号在总线中的传播时延

$$
帧长(bit)/数据传输速率 >= 2\tau
$$

以太网的最小帧长为64B，凡是小于最小帧长的帧会填充

CSMA/CA协议

CA(collision avoidance)：碰撞避免

CSMA/CA应用于无线局域网、CSMA/CD应用于总线式以太网（有线）

隐蔽站问题：A和C都检测不到信号，认为信道空闲时，同时向终端B发送数据帧，就会导致冲突

协议工作过程：

发送数据前，先检测信道是否空闲
空闲则发出RTS(request to send)，RTS包含发射端的地址、接收端的地址、下一份数据将持续发送的时间等信息；接收端响应CTS(clear to send)
发送端接收到CTS后，开始发送数据帧（同时预约信道：发送方告知其他站点自己要传多久数据）
接收端收到数据帧后，用CRC检验数据，正确则响应ACK帧
发送方收到ACK就可以进行下一个数据帧的发送，若没有则一直重传至规定重发次数为止（使用截断二进制指数规避算法）

3.5.3 轮询介质访问控制

轮询协议：主机依次询问从机是否发送数据

令牌传递协议

令牌在环形道传输->修改令牌,添加数据->接收机复制令牌的数据->返回发送方->发送方还原令牌

令牌：一个特殊格式的MAC控制帧，不含任何信息
每个结点都可以在一定时间内获得发送数据的权力，并不能无限制地持有令牌
应用于令牌环网（物理星型拓扑、逻辑环形拓扑）
令牌传送方式的网络常用于负载较重、通信量较大的网络中

缺点：

令牌开销
等待延迟
单点故障

3.6 局域网基本概念和体系结构

特点：

使用广播信道
使用专门铺设的传输介质进行联网，数据传输率高（10Mb/s~10Gb/s）
通信延迟时间短，误码率低，可靠性高
各站为平等关系，共享传输信道
多采用分布式控制和广播式通信，能进行广播和组播

局域网拓扑结构

局域网的分类

1、以太网（Ethernet）

由Xerox公司创建并由Xerox、Intel和DEC公司开发的基带总线局域网规范

符合IEEE802.3系列标准、DIX Ethernet V2(第一个局域网产品)规约；（两者帧格式有区别）
使用CSMA/CD
满足网络速率要求：10Mb/s-10Gb/s；造价低廉
只实现无差错接收，不实现可靠传输（错误数据直接丢弃）
逻辑上总线型，物理上星型

适配器和MAC地址：计算机与外界有局域网通过通信适配器连接；在局域网中，硬件地址又称为物理地址（或称为MAC地址），每个适配器都有一个全球唯一的48位二进制地址，前24代表厂家，后24位厂家自己指定

以太网MAC帧格式（以太网V2格式）

为什么没有结束界定符？因为采用的是曼彻斯特编码，只要适配器的电平不发生变化即可说明帧结束

与IEEE 802.3的区别：

第三个字段是长度/类型
当长度/类型字段值小于0x0600时，数据字段必须装入LLC子层

高速以太网

速率>=100Mb/s的以太网

10BASE-T以太网：T表示双绞线，是传送基带信号的采用无屏蔽双绞线的以太网，传输速率是100Mb/s；每段双绞线最长为100米；采用曼彻斯特编码；仍使用IEEE 802.3的CSMA/CD协议，支持全双工和半双工，可在全双工方式下工作无冲突

吉比特以太网：在光纤或双绞线上传送1Gb/s信号；支持全双工和半双工，可在全双工方式下工作无冲突
10吉比特以太网：在光纤上传送10Gb/s信号；只支持全双工，无争用问题

2、无线局域网(Wireless Local Area Network, WLAN)

采用IEEE802.11标准

802.11的MAC帧头格式

无线局域网的分类：

1、有固定基础设施的无线局域网：通过路由器等设备

2、无固定基础设施的无线局域网的自组织网络：由多个主机形成的网络，可以接收、发送和转发

3、令牌环网：物理上采用了星形拓扑结构，逻辑上是环形拓扑结构，采用IEEE802.5标准（较少使用）

4、FDDI网（Fiber Distributed Date Interface）：物理上采用双环拓扑结构，逻辑上是环形拓扑结构（IEEE802.8）

5、ATM网（Asynchronous Transfer Mode）:较新型的单元交换技术

IEEE 802标准（1980年2月制定）

IEEE 802标准所描述的局域网参考模型只对应OSI参考模型的数据链路层和物理层，同时将数据链路层分为逻辑链路层LLC子层和介质访问控制MAC子层

3.7 链路层设备

冲突域：当两台设备同时通信时会发生冲突的区域

广播域：站点发出一个广播信号，所有能接收到这个信号的设备范围称为一个广播域

物理层扩展以太网

链路层扩展以太网

网桥、交换机

根据MAC帧的目的地址进行转发和过滤（或者丢弃、即过滤）

网段：指一个计算机网络中使用同一物理设备（传输介质、中继器、集线器等）能够直接通信的那一部分

网桥优点：

过滤通信量
扩大了物理范围
提高了可靠性

网桥分类

1、透明网桥：指以太网上的站点并不知道所发送的帧将经过哪几个网桥，是一种即插即用设备--自学习

2、源路由网桥：在发送帧时，把详细的最佳路由信息（路由最少/时间最短）放在帧的首部

交换机的两种交换方式

交换机（多接口网桥）可以独占传输媒体带宽

直通式交换机：查完目的地址（6B）就立刻转发；延迟小，可靠性低，无法支持具有不同速率的端口的交换

存储转发式交换机：将帧放入高速缓存，并检查是否正确，正确则转发，错误则丢弃

标签：发送,重传,局域网,计算机网络,校验码,数据,以太网,链路层
From： https://www.cnblogs.com/eecsCodeStar/p/16980713.html