第三章数据链路层 Data Link Layer

概述

基本概念

节点：主机、路由器
链路：两节点间的物理通道
数据链路：两节点之间的逻辑通道。
帧：链路层的协议数据单元，封装网络层数据包。

功能：
在物理层提供服务的基础上向网络层提供服务，其最基本的服务是源自于网络层来的数据可靠地传输到相邻节点的目标机网络层。其主要作用是加强物理层传输原始比特流的功能，将物理层提供的可能出错的物理连接改造成为逻辑上无差错的数据链路，是之对网络层表现为一条无差错的链路。

为网络层提供服务，无确认无连接服务，有确认无连接服务，有确认面向连接服务。【有连接就一定有确认】
链路管理，即连接的建立、维持、释放
组帧
流量控制（发送方）
差错控制。

封装成帧与透明传输

封装成帧

就是在一段数据的前后部分添加首部和尾部，这样就构成了一个镇。接收端在收到物理层上交的比特流后，就能根据首部和尾部的标记，从收到的比特流中识别帧的开始和结束。

帧同步：接收方应当从接收到的二进制比特流中区分出帧的起始和终止。

帧长：数据帧的总长度

MTU最大传送单元：由于不同的协议规定了数据帧的极限长度，所以对于的数据部分的最大长度也受到限制，这个最大值就叫最大传送单元。

透明传输

指不管数据是什么样的比特组合，都应当能够在链路上传播。因此，链路层就看不见有什么妨碍数据传输的东西。

组帧应用：

字符计数法：帧首部使用一个计数字段（第一个字节）来表明帧内字符数。【痛点：鸡蛋装在了一个篮子里】
字符填充法：SOH（start of header） EOT（end if transmission)：遇到了和SOH与EOT时（数据中）应当添加转义字符ESC，这样就能实现透明传输。
零比特填充法：在发送端，扫描整个信息字段，只要连续五个1就立即填入一个0。
在接收端接收到一个帧时，先找到标志字段确定边界，再用硬件对比特流进行扫描。发现五个连续的1时，九八后面的0删除。
违规编码法：用物理层的编码不会使用的编码作为帧的起始和终止。

目前普遍使用的帧同步法是比特填充法和违规编码法。

差错控制

检错编码

差错来源：传输中的差错都是由噪声引起的。
全局性：由于线路本身电气特性所产生的随机噪声，是信道固有的，随机催在的。
解决办法：提高信噪比来减少或避免干扰。
局部性：外界特定的短暂原因所造成的冲击噪声，是产生差错的主要原因。
解决办法：使用编码技术来解决。

分类：位错和帧错。
帧错由包含丢失、重复、失序三种。
差错控制（比特错）：检错编码【奇偶校验码，循环冗余码】、纠错编码【海明码】

冗余编码：在数据发送之前，先按某种关系附加上一定的冗余位，构成一个符合某一规则的码字后再发送。当腰发送的有效数据变化是，相应的冗余位也随之变化，使码字遵从不变的规则。接收端根据收到码字是否仍符合原规则，从而判断是否出错。
奇偶校验码：即检查收到的数据包的1的个数是否为奇数/偶数个。
特点：检错能力为50%。

CRC循环冗余码：

海明码：能发现双比特错误，纠正单比特错误。
工作流程
确认校验码位数r -> 确定校验码和数据的位置 -> 求出校验码的值 -> 检错并纠错

确认校验码位数
海明不等式
2^r >= k+r+1
其中r为冗余信息位，k为信息位。

eg.发送数据为101101
数据的位数 k=6
满足不等式的r最小为4
也就是101101的海明码应当有6 + 4 = 10位。其中原数据码6位，校验码4位。

确定校验码和数据的位置。校验码放在2^n的位置，即1， 2， 4， 8位。
求出校验码的值：采用异或来求。
检错并纠错：将算出的值按照第三步方法运算。

流量控制与可靠传输机制

数据链路层的流量控制

主要原因是发送方和接收方的速度不匹配，这回造成传输错误。
链路层的流量控制是点对点的，而传输层的是端到端的。

数据链路层的流量控制手段：接收方收不下就不回复确认。
传输层的手段：接收端给发送端发一个窗口公告。

流量控制的方法

停止-等待协议
滑动窗口协议：发送窗口大小=1，接收窗口大小=1
后退N帧协议（GBN）：发送窗口大小>1，接收>1
选择重传协议（SR）：发送>1，接收>1.

可靠传输、滑动窗口、流量控制

可靠传输：发送端发什么，接收端接受什么。
流量控制：控制发送速率，使得接收方有足够的缓冲空间来接收一个帧。
滑动窗口解决：流量控制：接收方收不下就不回复确认，想发也发不了。
可靠传输：发送方会自动重发丢失的数据帧。

停止-等待协议

Why？：
除了比特出错，底层信道还会出现丢包问题。
为了实现流量控制。
研究停等协议的前提：
虽然现在常用全双工通信方式，但是为了讨论问题方便，仅考虑一方发送，一方接收。
因为实在讨论可靠传输的原理，所以并不考虑数据是在哪一层上传送的。
“停止-等待”就是没发送完一个分组就停止发送，等待对方确认，在收到确认后再发送下一个分组。
停等协议有几种应用情况。
无差错和有差错情况。

信道利用率 = （T内发送L比特数据/发送方数据传输率）/发送周期

后退N帧协议 GBN

流水线技术，会连续的发送很多数据帧。
需求：要增加序号范围，且发送方需要缓存多个分组。
发送窗口：发送方维持一组连续的允许发送的帧的序号。
接收窗口：接收方维持一组连续的允许接收帧的序号。

ACK:即确认收到了某帧。

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

上层的调用
上层要发送数据时，发送方先检查发送窗口是否已满，如果未满，则产生一个帧并将其发送。如果窗口已满，发送方只需要将数据返回给上层，按时上层窗口已满。上层等一会再发送。
收到了一个ACK
GBN协议中，对n号帧的确认采用累积确认的方式，标明接收方已经收到n号帧和它之前的全部帧。
超时事件
协议的名字为后退N帧/回退N帧，来源于出现丢失和时延过长帧时发送方的行为。就像再停等协议中一样，定时器将再次用于恢复数据帧或确认帧的丢失。如果出现超时，发送方重传所有已发送但未被确认的帧。

GBN接收方要做的事

如果正确收到n号帧，并且按序，那么接收方为n帧发送一个ACK，并将该帧中的数据部分交付给上层。
其余情况都丢弃帧，并按照最近按序接收的帧重新发送ACK。接收方无需缓存任何丢失帧，只需要维护一个信息：expectedseqnum（下一个按序接收的帧序号）。

滑动窗口长度：
如果采用n个比特对帧进行编号，那么发送窗口的尺寸应当满足：
1 <= W~T~<=2ⁿ-1.

GBN特性：

累积确认（偶尔捎带确认）
接收方只按顺序接收帧，不按顺序就丢弃。
确认序列号最大的，按序到达的帧。
发送窗口最大为2ⁿ-1，最小1.

选择重传协议 SR

GBN的弊端：累积确认->批量重传的问题
解决办法：设置单个确认，同时加大接收窗口，设置接收缓存，缓存乱序到达的帧。

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

上层的调用
从上层收到数据后，SR发送方检查下一个可用于该帧的序号，如果序号位于发送窗口内，则发送数据帧；否则就像GBN一样，要么将数据缓存，要么返回给上层后再传输。
收到了一个ACK
如果收到ACK，加入该帧序号在窗口内，则SR发送方将哪个被确认的帧标记为已接收。如果该帧序号是窗口的下界（滑动窗口最左端），则窗口向前移动到具有最小序号的未确认帧处。如果窗口移动了并且有序号在窗口内的未发送帧，则发送这些帧。
超时事件
每个帧都有自己的定时器，一个超时事件发生后只重传一个帧。

SR接收方要做的事：
来者不拒:
SR接收方将确认一个正确接收的帧而不管其是否按序。失序的帧将被缓存，并返回给发送方一个该帧的确认帧**【收谁确认谁】**，知道所有帧（即序号更小的帧）皆被收到为止，这时才可以将一批帧按照顺序交付给上层，然后向前移动滑动窗口。

滑动窗口的长度：
发送窗口最好等于接收窗口。
一般为2^n-1.

重点总结：

对数据帧逐一确认，收一个确认一个
只重传出错帧。
接收方有缓存。

介质访问控制技术

传输数据使用的两种链路

点对点链路：两个相邻节点通过一个链路项链，没有第三者。
应用：PPP协议，常用于广域网。

广播式链路：所有主机共享通信介质。
应用：早期的总线以太网、无线局域网，常用于局域网。
典型拓扑结构：总线型、星型。

介质访问控制

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

分类：

静态划分信道 -- 信道划分介质访问控制

频分多路复用FDM
时分多路复用TDM
波分多路复用WDM
码分多路复用CDM

动态分配信道

轮询访问介质访问控制 -> 令牌传递协议
随机访问介质访问控制

ALOHA协议
CSMA协议
CSMA/CD协议
CSMA/CA协议

信道划分介质访问控制：

虽然使用一条共享信道，但是通过多路复用技术组合进行传输，提高了信道的利用率。
FDM：
用户在分配到一定的频带后，在通信过程中自始至终都占用这个频带。频分复用的所有用户在同样的时间占用不同的频宽资源。
特点：充分利用传输介质带宽，系统效率较高；由于技术比较成熟，实现也比较容易。
TDM：
将时间划分为一段段登场的时分复用帧（TDM帧）。每一个时分复用的用户在每一个TDM帧中占用固定序号的时隙。所有用户轮流占用信道。
缺点是利用率低，所以衍生出STDM（统计时分复用）：
每一个STDM帧中的时隙数小于连接在集中器上的用户数。各用户有了数据就随时法网集中器的输入缓存，然后集中器按顺序依次扫描输入缓存，把缓存中的输入数据放入STDM帧中，一个STDM帧满了就发出。STDM帧不是固定分配时隙，而实按需动态分配。
CDM：
CDMA 码分多址是码分复用的一种方式：
一比特分为多个码片/芯片（chip），每一个站点被只当一个唯一的m位的芯片序列。
发送1时站点发送芯片序列，0时发送芯片序列的反码（通常为-1）。
如何不冲突：多个站点同时发送数据的时候，要求各个站点芯片序列相互正交。
如何合并：各路数据在信道中被线性相加。
如何分离：合并的数据和源站规格化内积。

轮询访问介质访问控制

包括轮询协议和令牌传递协议。
轮询：选一个代表接管控制所有传输。
TIP：轮询的开销随着服务的节点增多，需要用于查询是否发送的数据帧也就越多，会造成一定的开销。等待延迟就是因为这是轮流的询问，所以难免某个节点需要发送数据，但主节点还在较远的有需求的节点那边，导致需求得不到立即响应。单点故障即主节点宕机。

令牌传递协议：在节点之间没有手法数据的需求时，令牌在节点之间循环。
发送数据的流程：

当一个节点需要时就可以获得这个令牌，并修改令牌的状态。
再将令牌与数据帧结合，让其在节点构成的环之间流动。
不是目的地的节点收到令牌也不接收，直接掠过，目标节点收到信息并复制一份到本地（传输完成），因为是个闭环，所以发送节点最后得到令牌。
最后，发送令牌的节点对令牌的内容进行检查，如果发现数据出错还要重新发一边。

随机访问介质访问控制

所有用户都可以随机发送信息，发送时可以占用全部带宽，理论上个人使用时比静态分配信道的速度更快。

ALOHA协议：
纯ALOHA协议缺点：太随机，信道利用效率低。
如何检测冲突？
如果发生冲突，接收方就会检测出差错，然后不予确认，发送方在一定时间内收不到就判断发送冲突。
如何解决
超时后等一随机事件再重传。

时隙ALOHA协议：
相对于纯ALOHA协议，就是固定了发送的时间，提高了效率。

CSMA协议：
CS：carrier sense，载波侦听/监听，每一个站在发送数据之前要检测下总线是否有其他计算机在发送数据。
MA：multiple access，多点接入，表示许多计算机以多点接入的方式连接在一根总线上。

协议思想：发送帧之前，监听信道。信道空闲时，发送完整帧，忙时推迟发送。

局域网

Local Area Network：简称LAN，是指在某一区域内由多台计算机互联成的计算机组，使用广播信道。

局域网的概念

特点：

覆盖的地理范围较小，只在一个相对独立的局部范围内连接，如一座或集中的建筑群内。
使用专门铺设的传送介质（双绞线、同轴电缆）进行联网，数据传输速率高（10Mbps~10Gbps）。
通信延迟时间短，误码率低，可靠性较高。
各站位平等关系，共享传播信道。
多采用分布式控制和广播式通信，能进行广播和组播。

决定局域网的主要要素为：网络拓扑，传输介质和介质访问控制方法。

局域网拓扑结构：
有星形拓扑、总线型拓扑、环形拓扑、树型拓扑。常采用总线型拓扑。

传播介质：
有线局域网常采用双绞线、同轴电缆、光纤。
无限局域网则是电磁波。

LAN介质访问控制方法：
CSMA/CD：常用于总线型局域网，也用于树型网络。
令牌总线：常用于总线型局域网，也用于树型网络。
他是把总线型和树型网络中的各个工作站按照一定顺序（如按接口地址大小）排列形成一个逻辑环。只有令牌持有者才能控制总线，才有发送信息的权力。
令牌环：用于环形局域网，如令牌环网。

LAN的分类

以太网：以太网是应用最为广泛的局域网，包括标准以太网（10Mbps），快速以太网（100Mbps），千兆以太网（1000Mbps)和10G以太网，他们都符合IEEE802.3系列标准规范。逻辑拓扑总线型，物理拓扑是星型或拓展星型。使用CSMA/CD。
令牌环网：物理上采用了星形拓扑结构，逻辑上是环形拓扑结构，不常用。
FDDI（Fiber Distributed Data Interface）：物理上采用了双环拓扑结构，逻辑上是环形拓扑结构。
ATM（Asynchronous Transfer Mode）：较新型的单元交换技术，使用53字节固定长度的单元进行交换。
无线局域网络（Wireless Local Area Network; WLAN)：采用IEEE 802.11标准。

IEEE 802标准

802.3：以太网介质访问控制协议（CSMA/CD）及物理层技术规范。
802.5：令牌环网（Token-Ring）的介质访问控制协议及物理层技术规范。
802.8：光纤技术咨询组，提供有关光纤联网的技术咨询。
802.11：WLAN的介质访问控制协议及物理层技术规范。

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

LLC子层：负责识别网络层协议，然后对他们进行封装。LLC包头告诉数据链路层一单帧被接收到时，应当对数据包作何处理。为网络层提供服务：无确认无连接、面向连接、带确认无连接、高速传送。

MAC子层：主要功能包括数据帧的封装/卸载，帧的寻址和识别，帧的接收与发送，链路的管理，帧的差错控制等。MAC子层的存在屏蔽了不同物理链路种类的差异性。

以太网

概念：以太网（Ethernet）指的是由Xerox公司创建并由Xerox、Intel和DEC公司联合开发的基带总线局域网规范，是当今现有局域网采用的最通用的通信协议标准。以太网使用CSMA/CD协议。

以太网在局域网各种技术中占统治性地位：

造价低廉。
是应用最广泛的局域网技术。
比令牌环网、ATM网便宜，简单
满足网络速率要求：10Mbps~10Gbps

无连接：发送方和接收方之间无“握手过程”。
不可靠：不对发送方的数据帧编号，接收方不向发送方进行确认，差错帧直接丢弃，差错纠正由高层负责。
即：以太网只是先无差错接收，不实现可靠传输。

标准：
DIX Ethernet V2：第一个局域网产品规约。
IEEE 802.3： 802委员会802.3工作组指定的第一个IEEE的以太网标准（帧格式有改动）

以太网的发展：

粗同轴电缆->细同轴电缆 -> 双绞线+集线器
物理拓扑：总线型->星型

适配器和MAC地址：
计算机与外界有局域网的连接是通过通信适配器（网卡）的。

在局域网中，硬件地址又称为物理地址，或MAC地址。（标识符）
MAC地址：每个适配器有一个全球唯一的48位二进制地址，前24位代表厂家（IEEE规定），后24位厂家自己指定。常用6个十六进制数表示，如02-60-8c-e4-b1-21

以太网MAC帧：
MAC层指的是数据链路层，之前提到数据链路层将上一层ip数据包加头加尾。
其中，头是目标地址（6bytes），源地址（6bytes），类型（2bytes）
尾部是FCS（帧检验序列）（4bytes）
前导码不是MAC帧的衣部分，目的是使始终同步。
MAC帧的最长长度是1500是默认的。

所以做常用的MAC帧是以太网V2的格式：
前导码（8 bytes，不算入数据帧中）+目的地址（6 bytes）+源地址（6 bytes）+类型（2 bytes）+ 数据（46~1500 bytes）+FCS（4 bytes）。

10BASE-T以太网：
是传送基带信号的双绞线以太网，T代表采用双绞线，现10BASE-T采用的是无屏蔽双绞线（UTP），传输速率是10Mbps。
物理上采用星型拓扑，逻辑上总线型，每段双绞线最长100m。采用曼彻斯特编码。采用CSMA/CD介质访问控制。

100BASE-T以太网：
速率大于等于100Mbps的以太网成为告诉以太网。
100BASE-T在双绞线上传送100Mbps基带信号的星型拓扑以太网，仍使用IEEE802.3的CSMA/CD协议。支持全双工和半双工，可在全双工方式下工作而无冲突。

吉比特以太网：
在光纤或双绞线上传送1Gbps信号，与100BASE-T差不多。

10吉比特：
在光纤上传送10Gbps信号。

无线局域网

802.11的MAC帧头格式：
帧控制（2 byte）+生存周期ID（2 byte）+地址1（6 bytes）+地址2（6 byte）+地址3（6 byte）+序列控制（2 byte）+地址4（6 byte）
四个地址分别是：
RA接收端，TA发送端，DA目的地址，SA源地址

分类：有固定基础设施无线局域网和无固定基础设施无线局域网的自组织网络。

广域网

概述

广域网（WAN，Wide Area Network），通常跨接很大的物理范围，所覆盖的范围从几十公里到几千公里，它能连接多个城市或国家，或横跨几个洲并能提供远距离通信，形成国际性的远程网络。
广域网的通信子网主要使用分组交换技术。广域网的通信子网可以利用公用分组交换网、卫星通信网和无线分组交换网，它将分布在不同地区的局域网或计算机系统互连起来，达到资源共享的目的。如Internet是世界范围内最大的广域网。

PPP协议 Point-to-Point Protocol

PPP协议是目前使用最广泛的数据链路层协议，拨号基本都是PPP协议。且仅支持全双工链路。

PPP协议需要满足的要求：

简单：对于链路层的帧，无需纠错，无需编号，无需流量控制。
封装成帧：帧定界符。
透明传输：与帧定界符一样比特组合的数据应该如何处理：异步线路用字节填充，同步线路用比特填充。
多种网络层协议：封装的IP数据报可以采用多种协议。
多种类型链路：串/并行，同/异步，电/光。
差错检测：错就丢弃。
检测连接状态：链路是否正常工作。
最大传送单元：数据部分最大长度MTU。
网络层地址协商：知道通信双方的网络层地址
数据压缩协商

PPP协议不需要满足的要求：纠错、流量控制、序号、不支持多点线路。

PPP协议的三个组成部分：

一个将IP数据报封装到串行链路（同步串行/异步串行）的方法。
链路控制协议LCP：建立并维护数据链路连接。【身份验证】
网络控制协议NCP：PPP可支持多种网络层协议，每个不同的网络层协议都要一个相应的NCP来配置，为网络层协议建立和配置逻辑连接。

PPP协议的帧格式：
F（1 byte) + A (1 byte) + C (1 byte) + 协议 (2 byte) + 信息部分（不超过1500 byte） + FCS (2 byte) + F (1 byte)

F:标志，A：地址，C：控制
FAC+协议称为首部，FCS+F称为尾部。F为帧定界符。

HDLC协议 High-Level Data Link Control

概述：HDLC协议是一个在同步网上传输数据、面向比特的数据链路层协议，他是由ISO根据IBM公司的SDLC（Synchronous Data Link Control）协议扩展开发而成的。

数据报文可透明传输，用于实现透明传输的”0比特插入法“易于硬件实现。
采用全双工通信
所有帧采用CRC校验，对信息帧进行顺序编号，可防止漏收或重份，传输可靠性高。

HDLC的站：
包含主站、从站、复合站。

主站的主要功能是发送命令（包含数据信息）帧、接收响应帧，并负责对整个链路的控制系统的初启、流程的控制、差错检测或恢复等。
从站的主要功能是接收由主站发来的命令帧，向主站发送响应帧，并且配合主站参与差错恢复等链路控制。
复合站的主要功能是技能发送，又能接收命令帧和响应帧，并且负责整个链路的控制。

三种数据操作方法：

正常响应方式
异步平衡方式
异步响应方式

HDLC的帧格式：
标志F（8 bit）+ 地址A（8 bit）+ 控制C（8 bit）+ 信息info
(长度可变）+ FCS （16 bit） + 标志F（8 bit）

去掉首尾的F就是透明传输区间，再去掉末尾的FCS就是FCS检验区间。

TIP:

信息帧的第一位是0，用来传输数据信息，或使用捎带技术对数据进行确认。
监督帧10，用于流量控制和差错控制，执行对信息帧的确认、请求重发和请求暂停发送等功能。
无编号帧11，用于提供对链路的建立、拆除等多种功能。

PPP协议与HDLC协议对比。

PPP、HDLC都只支持全双工链路。
都可以实现透明传输，都可以实现差错检测，但不纠正差错。

链路层设备

集线器 Hub

可以扩展以太网，但是集线器会无脑将一个设备的所有消息转发到集线器所连的所有设备，所以会将所连接的所有设备变成一个大的冲突域，同时只能由两台设备进行通信，且设备越多，冲突越多。由此诞生了网桥。

网桥 Bridge

使用网桥时，由于网桥会根据mac地址进行过滤，所以不会形成冲突域。
网桥根据MAC帧的目的地址对帧进行转发和过滤。当网桥收到一个帧时，并不向所有接口转发此帧，而是先检查此阵的目的MAC地址，然后再确定将该帧转发到哪一个接口，或者把它丢弃（过滤）。

网桥的优点：

过滤通信量，增大吞吐量。
提高了物理范围。
提高了可靠性。
可互联不同物理层、不同MAC子层和不同速率的以太网。
网段：一般指一个计算机网络中使用同一个物理层设备（传输介质、中继器、集线器等）能够直接通讯的那一部分。

网桥的分类：

透明网桥：通过自学习来构建转发表。每一个通过网桥的数据包都会被记录下网桥收到数据时数据对于的地址和网桥自己的接口。通过大量的数据包构造的缓存，网桥就可以知道哪个数据包在哪个接口，以后如果要传送数据包就知道要往哪个接口发送数据包了。
原路由网桥：再发送时，直接将最佳路径放在帧首部。那么网桥如何获得最佳路径？通过广播方式向目标地址发送广播，此时可能会经过不同路由产生的不同的路径，目的地址收到后再将每一条路径都发送一个响应帧给网桥，网桥经过对比就知道哪个接口最快了。

交换机：

网桥接口越来越多，网桥就变成了交换机：

以太网交换机的两种交换方式：

直通式交换机：查完目的地址（6B）就立刻转发：
延迟低，可靠性低，无法支持具有不同速率的端口的交换。
存储转发式交换机：将帧放入高速缓存，并检查是否正确，正确则转发，错误则丢弃：
延迟大，可靠性高，可以支持具有不同速率的端口的交换。

冲突域和广播域：

冲突域：在同一个冲突与中的每一个节点都能收到所有被发送的帧。简单的说就是同一时间内只有一台设备发送信息的范围。
广播域：网络中能接收任一设备发出的广播帧的所有设备的集合。简单的说，如果站点发出一个广播信号，所有能接收到这个信号的设备范围称为一个广播域。

第三章 数据链路层 Data Link Layer

概述