计算机网络（王道考研）笔记个人整理——第三章

第三章：链路层

数据链路层：结点，链路

结点：主机、路由器

链路：网络中俩结点之间的物理通道 ，链路的传输介质有双绞线、光纤和微波，分为有线链路、无线链路。

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

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

功能：在物理层基础上向网络层提供服务

最基本的服务是将源自网络层来的数据可靠的传输到相邻节点的目标机网络层。

主要作用是加强物理层传输原始比特流 的功能，将物理层提供的可能出错的物理连接改造成为逻辑上无差错的数据链路，使之对网络层表现为一条无差错的链路

1. 

为网络层提供服务。无确认无连接服务，有确认无连接服务，有确认面向连接服务。

2. 

链路管理：连接的建立、维持、释放（用于面向连接的服务）

3. 

组帧

封装成帧

在一段数据的前后部分添加包含控制信息的首部和尾部（作用：帧定界 ），这样就构成了一个帧。接收端在收到物理层上交的比特流后，就能根据首部和尾部的标记，从而识别帧的开始和结束

帧同步

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

组帧的方法 ：字符计数法；字符填充法；零比特填充法；违规编码法

透明传输 ：指不管所传数据是什么比特组合都能在链路上传送。即没有妨碍数据传输的东西。当数据中比特组合与某一个控制信息完全一样时必须采取适当措施，使收方不会将这样的数据误认为是某种控制信息。

 1. **字符计数法** ：帧首部用一个计数字段来标明帧内字符数。
 2. 字符填充法：加上转义字符。→当传送的帧是由ascll文本文件组成时，都可以实现透明传输。非ascll码文本文件（二进制代码的程序和图像）要采用字符填充法实现透明传输。
 3. 零比特填充法：在发送端扫描整个信息字段，只要连续五个1，就立即填入1个0。在接收端收到一个帧时先找到标志字段确定边界，再用硬件对比特流进行扫描，发现连续5个1则删除后面的0。
 4. 违规编码法：

4. 

流量控制：限制发送方

数据链路层流量控制

原因：较高的发送速度和较低的接受能力不匹配，会造成传输出错

数据链路层 的流量控制是点对点的（相邻结点），控制手段是接收方收不下就不回复确认；传输层 流量控制是端到端的（主机与主句），接收端给发送端一个窗口公告

方法

   1. 

停止-等待协议

每发送一个帧就停止发送，等待对方确认，收到确认后再发送下一个帧。是一种特殊的滑动窗口协议，窗口大小=1，接收窗口=1。

   2. 

滑动窗口协议：流量控制，可靠传输（发送方自动重传）

后退N帧协议GBN （发送窗口>1，接收窗口=1）；选择重传协议SR （发送窗口>1,接收窗口>1）

停止-等待协议

原因：除了比特出差错，底层信道还会出现丢包（由物理线路故障、设备故障、病毒攻击、路由信息错误等导致数据包丢失）

前提：虽然常用全双工通信方式，但仅考虑一方发送，一方接收；不考虑数据在那一层次传送；每发送完一个分组就停止传送，等待对方确认，在收到确认后再发送下一个分组。

应用情况：无差错情况，有差错情况

无差错情况：

有差错情况：

     1. 

数据帧丢失或检测到帧出错：

       1. 发送一个帧后，必须保留副本
       2. 数据帧和确认帧必须编号

每发送一个帧启动一个计时器超时计时器重传时间比帧传输的平均RTT更长一些。

     2. 

ACK丢失（确认帧丢失）

     3. 

AXK迟到

性能：利用率低

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

T发送周期（从开始发送数据到确认收到第一个确认帧为止）

L一个周期内发送的比特数据

C发送方数据传输率

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

选择重传协议SR

滑动窗口

SR发送方：发送帧，接收确认帧ACK

       1. 从上层收到数据后，检查下一个可用于该帧的序号，如果序号位于发送窗口内则发送数据帧，否则就像GBN一样要么数据缓存，要么返回给上层之后在传输。
       2. 收到ACK后加入该帧序列在窗口内，SR发送方将该帧标记为已接受。如果该帧序号是窗口下届则窗口向前移动到具有最小序号的未确认帧处。
       3. 每个帧都有自己的超时事件，一个超时时间发送后重传一个帧

SR接收方：接收帧，发送ACK

来者不拒：确认一个正确接收的帧不管其是否按序。失序的帧将被缓存并返回确认帧，所有帧都被收到后按序交付上层，然后向前移动窗口。

如果收到窗口序号外（小于窗口下界）的帧返回ACK。

滑动窗口长度

发送窗口最好等于接收窗口

避免二义性：Wtmax=Wrmax=2^(n-1)

只重传超时帧

后退N帧协议（GBN）

弊端：如果出现错误帧，该帧后的所有帧都要重传，损失较大。

解决办法：设置单个确认，同时加大接收窗口，设置接收缓存，缓存乱序到达的帧。

GBN发送方

     1. 上层调用：上层要发送数据时，发送方先检查发送窗口，如果窗口未满，则产生一个帧并发送；如果已满，只需将数据返回。（实际发送时发送方可以缓存这些数据）
     2. 收到ACK：累计确认，标明接收方已经收到n号帧和它之前的全部帧
     3. 超时协议：重传所有已发送但未被确认的帧。

GBN接收方

正确收到N帧并按序为其发送一个ACK，并将该帧中的数据部分交付上层。

其余情况丢弃帧并为最近按序接收的帧重新发送ACK。（发送方会重传所有已发送但未确认的最大序号的帧）。接收方无需缓存失序帧，只需维护信息expectedseqnum。

窗口尺寸

尺寸过大接收方可能无法区别新帧和旧帧。采用n个比特对帧编号，发送方1≤Wt≤（2^n）-1，接收方窗口大小为1

5. 

差错控制（差错、位错）

差错：由噪声引起

全局性：由于线路本身电气特性产生随机噪声 ，是信道固有的，随即存在的。解决办法：提高信噪比（传感器）

局部性：外部特定的短暂原因造成的冲击噪声 。解决：利用编码技术解决。

分为帧错 （丢失、重复、失序）和位错 （比特位出错，1变为0或0变为1）。

差错控制（比特错/位错）：冗余码技术

冗余编码：数据发送前按某种关系附加一定冗余位 ，构成一个符合某一规则的码字后在发送。当要发送的有效数据变化，相应冗余位也变化，使码字遵从不变的规则。接收端根据码字是否符合原规则判断是否出错。

 1. 检错编码：奇偶校验码，循环冗余码CRC
 2. 纠错编码：海明码

奇偶校验码

构成：n-1位信息元和1位校验员

采用奇校验：1的个数位奇数

采用偶校验：1的个数为偶数

特点：只能检查出奇数个比特错误，检错能力为50%

CRC循环冗余码

差错被丢弃，因此凡是接收端数据链路层接收的帧均无差错，但并不是可靠传输（发送端发送什么，接收端就接收到什么）。

纠错编码：海明码

发现双比特错，纠正单比特错。

工作原理：动一发而牵全身

工作流程：

   1. 

确定校验码位数r

   2. 

确定校验码和数据位置

   3. 

求出校验码值

算法：如p3第3位是1，D2，3，4第三位也是1，取实际值进行异或加和（相异为1，相同为0）求出p3。

   4. 

检验并纠错

101101海明码为0010011101

假设第五位即D2出错

数据链路层编码针对单个编码的同步问题，物理层针对一组比特的差错问题

差错控制（帧错）

传输数据链路

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

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

介质访问控制

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

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

含义：将使用介质的每个设备与来自同一信道上的其他设备的通信隔离开，把时域和频域资源合理地分配给网络上的设备。

多路复用技术：多个信号组合在一条物理信道上传输，使多个计算机或终端设备共享信道资源，提高信道利用率。

频分多路复用FDM（并行）

用户在分配到一定频带后在通信过程中自始至终都占用这个频带。用户在相同时间占用不同带宽 资源。

优点：充分利用传输介质带宽，系统效率高；技术成熟，实现简单。

时分多路复用TDM（并发）

将时间划分为一段段等长的时分复用帧（TDM帧），每一份时分用户在每一个TDM帧中占用固定序号的时隙，所有用户轮流占用信道。

统计时分复用STDM

集中器：将低速用户连接，数据集中后发送给高速线路

每一个STDM帧的时隙数小于连接在集中器上的用户数。各用户有了数据就随时发送集中器的输入缓存，然后集中器按序扫描输入缓存，把缓存中的输入数据放入STDM帧中。一个STDM帧满了就发出。STDM帧不是固定分配时隙，而是按需动态分配。

波分多路复用WDM

即光的频分多路复用。在一根光纤中传输不同波长的光信号，由于波长不同，所以各路光信号互不干扰，最后再用波长分解复用器将各路波长分解出来。

码分多路复用CDM

码分多址（CDMA）使码分复用的一种方式。

1个比特分为多个码片\芯片，每一个站点被指定一个唯一的m位芯片序列。即发送1时站点发送芯片序列，发送0时发送芯片序列反码。

多个站点同时发送数据时，要求各个站点芯片序列相互正交。

合并：各路数据在信道中线性相加。

分离：合并的数据和源站规格化内积。

动态分配信道：动态媒体介入控制/多点接入

轮询访问介质访问控制（令牌传递协议）

信道划分介质访问控制协议：

基于多路复用技术划分资源。

网络负载重时：共享信道效率高，且公平

网络负载轻：共线信道效率低。

随机访问MAC协议：（冲突）

用户根据意愿随机发送消息，可独占信道带宽。网络负载重：产生冲突开销。网络负载轻：共享信道效率高，单个结点可利用信道全部带宽。

轮询访问MAC协议/轮流协议/轮转访问MAC协议：既不产生冲突，又要发送时占全部带宽

轮询协议：主节点轮流邀请从属节点发送数据。缺点：轮询开销；等待延迟；单点故障

令牌传递协议：一个特殊格式的MAC控制帧，不含任何信息。

控制信道的使用，确保同一时刻只有一个结点独占信道。

每一个结点都可以在一定时间内获得发送数据的权力，并不是无线持有令牌。

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

应用：令牌环网（物理星型拓扑，逻辑环形拓扑），常用于负载较重、通信量较大的网络

随机访问介质访问控制（用户随机发送信息，占全部带宽）：ALOHA协议，CSMA协议，CSMA\CD协议，CSMA\CA协议

纯ALOHA协议

不监听信道，不按时间槽发送，随机重发。

检测：发送冲突时，接收方检测出差错，不予确认，发送方一定时间内收不到确认就判断冲突

解决：超时后随机事件再重传

时隙ALOHA协议

把时间分成若干个相同时间片，所有用户在时间片开始时刻同步接入网络信道，若冲突，必须等到下一个时间片开始时刻在发送

纯ALOHA协议比时隙ALOHA协议吞吐量低，效率更低；纯ALOHA想发就发，而时隙ALHA协议必须等到下一时间片。

载波监听多路访问协议CSMA

CS：载波监听，每一个站在发送数据前要检测一下总线上是否有其他计算机发送数据。

几个站同时在总线上发送数据时，总线上的信号电压摆动值增大。

MA：多点接入，表示许多计算机以多点接入的方式连接在一根总线上。

监听结果：信道空闲→发送完整帧（1-坚持CSMA，非坚持CSMA，p-坚持CSMA）;信道忙→推迟发送

1-坚持CSMA

坚持指的是对于监听信道忙之后的坚持监听

空闲则直接传输，不必传输；忙则一直监听，知道空闲马上传输。如果有冲突，则等待一个随机长的时间再监听。

优点：只要空闲马上发送，避免媒体利用率冲突

缺点：假如有俩个或俩个以上的数据要发送，冲突不可避免。

非坚持CSMA

监听信道忙之后不继续监听

空闲则直接传输；忙则等待一个随机时间后再监听。

优点：采用随机重发延迟时间可以减少冲突发生的可能性。

缺点：可能存在大家都在延迟等待过程中，使得媒体可能处于空闲状态，媒体使用率降低。

p-坚持CSMA

指的是对于监听信道空闲的处理

思想：如果一个主机要发送信息，它先监听信道。空闲则以p概率直接传输，概率1-p等待下一个时间槽再传输；忙则等待一个随机事件再监听。

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

缺点：发送冲突依然坚持发送数据帧，造成浪费。

载波监听多点接入/碰撞检测协议CSMA/CD（总线式以太网）

CS：发送数据之前 和发送数据时 都要检测总线上是否有其他计算机在发送数据

MA：多点接入，表示许多计算机以多点接入的方式连接在一根总线上。总线型网络 。

CD：碰撞检测，适配器边发送数据边检测信道上信号电压变化情况。（半双工网络）

传播时延对载波监听的影响：端到端有传播时延t，因此端可能监听不到电压变化；

只要经过2t时间还没有检测到碰撞，就能肯定这次发送不发生碰撞。

重传时机：截断二级制规避算法

    1. 确定基本退避时间为争用期2t
    2. 定义参数k，重传次数≤10时，k=重传次数；重传次数>10，k=10
    3. 从离散的整数集合[0,1…2^k-1]中随机取数r，重传所需时间为r倍的基本退避时间。为2r t。
    4. 当重传次数到16次，说明网络太拥挤，认为此帧无法正确发出，抛弃此帧并向高层报错

最小帧长：避免发完后才检测到碰撞

最小帧长=总线传播时延 数据传输速率 2=2t*数据传输速率

以太网规定凡小于64B的都是由于冲突而异常终止的无效帧

载波监听多点接入/碰撞避免协议CSMA/CA（无线局域网

缺点：无法做到360°全面检测碰撞；隐蔽站（A，C认为信道空闲，同时向B发送数据则冲突）

思想：

  1. 发送数据前检测信道空闲。空闲则发出RTS，RTS包括发送端地址，接收端地址、下一份数据将持续发送的时间；信道忙则等待。
  2. 接收端收到RTS，响应CTS。
  3. 发送端收到CTS后，开始发送数据帧。（同时预约信道，告知其他站点自己要传多久数据）。
  4. 接收端收到数据帧后，用CRC检验数据是否正确，正确则响应ACK帧
  5. 发送方收到ACK就可以进行下一个数据帧的发送，若没有则一直重传至规定重发次数为止（二进制指数规避算法来确定随机的推迟时间）

CSMA/CD和CSMA/CA异同

相同：先监听再发送。

不同：

  1. 传输介质不同。前者用于总线式以太网（有线），后者用于无线局域网（无线）。
  2. 载波检测方式不同：因传输介质不同，检测方式也不同。前者通过电缆中电压变化检测，碰撞时电压随着变化；而CSMA/CA采用能量检测（ED）、载波检测（CS）和能量载波混合检测三种检测信道空闲的方式。
  3. 前者检测冲突，后者避免冲突，出现冲突后都会进行有限重传。

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

* 特点： 

覆盖地理范围小，只在一个相对独立的局部范围内联。如一座或集中的建筑群内
使用专门铺设的传输介质进行联网，数据传输速率高
通信延迟时间短，误码率低，可靠性高
各站平等，共享传播信道
多采用分布式控制和广播式信道，能进行广播和组播

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

局域网拓扑结果

星型拓扑：中心结点是控制中心，俩结点通信最多俩步，传输速度块，网络构型简单，便于控制和管理；但网络可靠性低，共享能力差，但有单点故障问题。

总线型拓扑：可靠性高、网络节点间响应速度快、共享资源能力强、设备投入量少、成本低、安装使用方便，单点故障影响小。

环型拓扑：系统中通信设备和线路比较节省。有单点故障问题，不便于扩充，响应时间长，信息传输效率较低。

树型拓扑：易于拓展，易于隔离故障；有单点故障。

分类：有线局域网（常用介质：双绞线、同轴电缆、光纤），无线局域网（常用介质：电磁波）

局域网介质访问控制方法

CSMA/CD,常用于总线型局域网，也用于树型网络。

令牌总线，常用于总线型局域网，也用于树型网络。

令牌环，用于环形局域网，如令牌环网。

局域网分类

以太网：应用最广泛。包括标准以太网（10Mbps）、快速以太网（100Mbps），千兆以太网和10G以太网。都符合IEEE802.3系列标准规范。逻辑拓扑是总线型，物理拓扑是星型或拓展星型。使用CSMA/CD.

令牌环网：物理上采用星型拓扑结构，逻辑是环形拓扑

FDDI网：物理上采用双环拓扑，逻辑是环形拓扑

ATM网：较新型单元交换技术，使用53字节固定长度的单元进行交换

无线局域网：采用IEEE802.11标准

IEEE802标准

是IEEE802 LAN/MAN标准委员会指定的局域网、城域网技术标准。

IEEE802.3：以太网 介质访问控制协议及物理层技术规范。

IEEE802.5：令牌环网 的介质访问控制协议及物理层技术规范。

IEEE802.8：光纤技术资询组，提供有关光线联网的技术咨询。FDDI网

IEEE802.11：无线局域网 的介质访问控制协议及物理层技术规范。

MAC子层和LLC子层

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

LLC负责识别和封装网络层协议。LLC报头告诉数据链路层一旦帧倍接收到时，应当对数据包做何处理。为网络层提供服务：无确认无连接、面向连接、待确认无连接、高速传送。

MAC功能包括帧的封装/卸妆，帧的寻址和识别，帧的接收与发送，链路管理，帧的差错控制。它的存在屏蔽了不同物理链路种类的差异性。

以太网Ethernet

基带总线局域网规范。最通用的局域网通信协议标准，使用CSMA/CD技术。

优点：造价低廉；应用最广泛的局域网技术；便宜简单；满足网络速率要求10Mb/s~10Gb/s。

标准：DIX Ethernet第一个局域网产品（以太网）规约；IEEE802.3第一个IEEE以太网标准。（帧格式有略微改动）

10BASE-T以太网

时传送基带信号的双绞线以太网，T表示采用双绞线，现10BASE-T采用的是无屏蔽双绞线，传输速率10Mb/s，每段双绞线最长100m，采用CSMA/CD介质访问控制。采用曼彻斯特编码。

适配器与MAC地址

计算机与外界局域网的连接是通过通信适配器 的。适配器上装有处理器和存储器（包括RAM和ROM），ROM上有计算机硬件地址MAC地址。

硬件地址又称为物理地址或MAC地址。每个适配器有一个全球唯一48位二进制地址，前24位代表厂家（由IEEE）规定，后24位厂家主机指定。常用6个十六进制数表示。

以太网MAC帧

常用MAC帧是以太网v2格式。

MTU链路层最大数据单元：1500

IP数据报最短为64字节

与IEEE802.3区别：第三个字段是长度/类型，当长度/类型字段值小于0x0600，数据字段必须装入LLC子层

告诉以太网：速率≥100Mb/s

100BASE-T以太网：在双绞线上传送100Mb/s基带信号的星型拓扑以太网，支持全双工（无冲突）和半双工。

吉比特以太网：在光纤或双绞线上传送1Gb/s信号。支持全双工和半双工。

10吉比特：光纤上传送10Gb/s信号。只支持全双工。

IEEE802.11无线局域网通用标准

802.11的MAC帧头格式

无线局域网分类

有固定基础设施无线局域网

无固定基础设施无线局域网的自组织网络

广域网

广域网的通信子网主要使用分组交换技术。广域网的通信子网可以利用公用分组交换网、卫星交换网、卫星通信网和无线分组交换网，它将分布在不同地区的局域网或计算机系统互连，达到资源共享的目的。如因特网是世界范围内最大的广域网。

点对点协议ppp

最广泛的数据链路层协议，只支持全双工。应用：用户使用拨号电话接入因特网。

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

无须满足：纠错；流量控制；对帧编序号；不支持多点线路。

三个组成部分：

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

帧格式：

高级数据链路控制协议HDLC

是一个在同步网上传输数据，面向比特的数据链路层协议，由ISO开发

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

采用全双工通信。

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

主站、从站、复合站

主站：发送命令帧，接收响应帧，并负责对整个链路的控制系统的初启、流程的控制、差错检测或恢复

从站：接收主站命令帧，发送相应帧，配合主站参与差错恢复等链路控制。

复合站：既当主站又当从站

三种数据操作方式

正常响应

异步平衡

异步响应

帧格式

信息帧 （I）第一位为0，用于传输数据信息，或使用捎带技术对数据确认

监督帧 （S）10用于流量控制和差错控制、执行对信息帧的确认、请求重发、请求暂停发送

无编号帧 （U）11用于提供链路建立、拆除等多种控制功能

异同

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

扩展以太网

物理层扩展以太网:主机-光纤调制器-光纤调制器-集线器

链路层扩展以太网：网桥根据MAC帧目的地址对帧转发和过滤，当网桥收到帧不向所有接口转发此帧，二是先检查此帧的目的MAC地址，然后再确定该帧转发到哪一个接口，或是把它丢弃。

网桥优点：过滤通信量，增大吞吐量；扩大了物理范围；提高可靠性；可互连不同物理层，不同MAC子层和不同速率的以太网

网桥分类：

1. 透明网桥：即插即用（自学习算法），指以太网上的站点不知道发送的帧将经过的网桥
2. 源路由网桥：发送帧时把详细的最佳路由信息放在帧的首部中。源站以广播方式向欲通信的目的站发送一个发现帧

多接口网桥：以太网交换机，每一个端口的区域都叫冲突域。

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

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

存储转发式交换机：将帧放入高速缓存，并检查，正确则转发，错误则丢弃。（延迟大，可靠性高，可以支持具有不同速率端口的交换）

冲突域与广播域