计算机网络---数据链路层

功能

数据链路层主要作用是加强物理层传输原始比特流的功能，将物理层提供的可能出错的物理连接改造为逻辑上无差错的数据链路，使之对网络层表现为一条无差错的链路。（物理上肯定有一些差错，但是可以通过修改，改为逻辑上无差错）

任务：负责将数据报通过链路从一个节点传输到相邻的节点

• 三个基本功能：
  • 封装成帧
  • 透明传输
  • 差错检测

封装成帧

• 基本概念：
  将一段数据的前后分别添加首部和尾部，就构成了帧。

  注意：首部和尾部中含有很多控制信息（如 检验序列等），它们的一个重要作用是确定帧的界限，即帧定界。

透明传输

如果在数据中心恰好出现与帧定界符相同的比特组合，会导致帧提前结束而丢弃后面的数据。所以引入了“透明传输”。

• 基本概念：
  透明传输就是不管所传的数据是什么样的比特组合（透明的，看不见里面的数据），都应当能在链路上传送。
• 基本方法：
• 字符计数法：
  在帧头部使用一个计数字段来标明帧内字符数。
• 字符填充的首尾定界符法：
  • 在特殊字符前面填充一个转义字符(DLE)来加以区分，以实现数据的透明传输。接收方收到转义字符后，就知道其后面紧跟的是数据信息，而不是控制信息。
  • 数据中有可能出现转义字符，所以要在转义字符前再插入一个转义字符。

• 比特填充的首尾标志法：
  由于使用01111110（6个1）来标志一帧的开始和结束，故发送方只要在数据中遇到5个连续的“1”时，自动在其后插入一个“0”；接收方每收到5个连续的“1”时，自动删除后面紧跟的“0”，以恢复原信息。

  比特填充法很容易由硬件来实现，性能优于字符填充法。

• 违规编码法：
  • 在物理层进行比特编码时，通常采用违规编码法。
  • 例如，曼彻斯特编码方法中“高-高”电平对和“低-低”电平对在数据比特中是违规的（即 没有采用）。可以借用这些违规编码序列来定界帧的起始和终止。
  • 局域网IEEE 802标准就采用了这种方法

  • 适用性：
    只适用于采用冗余编码的特殊编码环境

    冗余码是一种所用符号数或信号码元数比表示信息所必需的数目多的代码
    常用的组帧方法是比特填充法和违规编码法。

差错控制（检测）

通常利用编码技术进行差错控制，主要有两类：自动重传请求(Automatic Retransmission reQuest, ARQ)和前向纠错(Forward Error Correction, FEC)
在ARQ方式中，接收端检测出差错时，就设法通知发送端重发，直到接收到正确的码字为止。
在FEC方式中，接收端不但能发现差错，而且能确定二进制数码的错误位置，从而加以纠正。
因此，差错控制又可分为检错编码(Error-Detecting Code)和纠错编码(Error-Crrecting Code)

检错编码

检错编码都采用冗余编码技术，其核心思想是在有效数据（信息位）被发送前，先按某种关系附加一定的冗余位，构成一个符合某一规则的码字后再发送。

• 奇偶校验码：

  奇偶校验码是奇校验码和偶校验码的统称，是一种最基本的检错码

  • 由n-1位信息元和1位校验元组成。
  • 奇（偶）校验码：使n位码字中“1”的个数为奇（偶）数，从而在一个比特改变后检错。

• 循环冗余码(CRC)：（可以检测出所有的单比特错误）（带有r个校验位的多项式编码可以检测到所有长度小于等于r的突发性错误）

  循环冗余码(Cyclic Redundancy Code, CRC)又称多项式码。（1101为\(x^3+x^2+1\)）

  • 步骤：

    假设一个帧有m位，其对应的多项式为M(x)，发送方和接收方事先商定一个r+1位除数，欲求出一个r位的帧检验序列（冗余码）。

    • 加0。在帧的低位端加上r个0（因为 余数为r位，最后要加余数凑冗余码）。（即 加上除数多项式的阶，如 1000的阶为x^3，所以阶为3）
    • 模2除（异或运算）。用除数(r+1位)除(m+r)位的帧，可以得出r位的余数R（即为冗余码）

    • 发送数据：数据帧+冗余码（组合起来 不是加减）

      在数据后面添加上的冗余码称为帧检验序列(Frame Check Sequence, FCS)，CRC与FCS并不等同，FCS可以用CRC这种方法得出，当CRC并非是获得FCS的唯一方法。

  • 检验：
    相除余数为0，则没有差错，就接受。

    注意：仅用CRC差错检测技术只能做到无差错接受（即 接受的帧非常接近于1的概率没有产生差错）（有差错的帧就丢弃而不接受）
    要做到“可靠传输”（即 发送什么就收到什么）就必须再加上确认和重传机制。

纠错编码

在数据通信的过程中，解决差错问题的一种方法是在每个要发送的数据块上附加足够的冗余信息，使接收方能够推导出发送方实际送出的应该是什么样比特串。

• 海明码：能发现双比特错，但只能纠正单比特错。
• m个信息位，插入r个校验位，组成m+r位码字，必须满足\(2^r≥m+r+1\)（即 \(2^r\)个校验码需要覆盖所有信息全长 加上 一个成功的状态）

情况	海明距离
检测n位错误	n+1
纠正n位错误	2n+1

流量控制与可靠传输机制

流量控制设计对链路上的帧的发送速率的控制，以使接收方有足够的缓冲空间来接收每个帧。
常见的方式有两种：停止-等待协议和滑动窗口协议。

• 滑动窗口：
  • 在任意时刻，发送方都维持一组连续的允许发送的帧的序号，称为发送窗口。

  • 同时接收方也维持一组连续的允许接收帧的序号，称为接收窗口。（只有收到的数据帧的序号在接收窗口内才收下，否则丢弃）

  • 特性：
    • 只有接收窗口向前滑动（同时接收方发送了确认帧）时，发送窗口才有可能（只有发送方收到确认帧后才一定）向前滑动。
    • 协议：
      • 停止-等待协议(Stop-and-Wait)：发送窗口大小=1，接收窗口大小=1
      • 后退N帧协议(Go-Back-N, GBN)：发送窗口大小>1，接收窗口大小=1
      • 选择重传协议(Selective Repeat, SR)：发送窗口大小>1,接收窗口大小>1
    • 接收窗口的大小为1时，可保证帧的有序接收。
    • 数据链路层的滑动窗口协议中，窗口的大小在传输过程中是固定的（注意与传输层的滑动窗口协议的区别）

• 可靠传输机制：

  数据链路层的可靠传输通常使用确认和超时重传两种机制来完成。确认是一种无数据的控制帧，这种控制帧使得接收方可以让发送方知道哪些内容被正确接收。

  • 自动重传请求(Auto Repeat reQuest, ARQ)通过接收方请求发送方重传出错的数据帧来恢复出错的帧，是通信中用于处理信道所带来的差错的方法之一。传统自动重传请求分为三种，即停止-等待(Stop-and-Wait)ARQ、后退N帧(Go-Back-N)ARQ、选择重传(Selective Repeat)ARQ。

    注意：在数据链路层中流量控制机制和可靠传输机制是交织在一起的。

停止-等待协议

信道利用率：即信道的效率，是指发送方在一个发送周期的时间内，有效地发送数据所需要的时间占整个发送周期的比率。（只算有效地发送数据，即 发送分组的那段时间 才是有效的）
\[信道吞吐率=信道利用率*发送方的发送速率\]

信道利用率U，\(T_D\)为分组发送时延，RTT为往返时延，\(T_A\)为确认发送时延。
\[U={{T_D} \over {T_D+RTT+T_A}}\]

• 还可用上述等式求出窗口大小。
  信道利用率100%，即 流水线式发送，不断发送分组，填满直到接收确认的时延。
  \[窗口最小大小={{T_D+RTT+T_A} \over {T_D}}\]

后退N帧协议(GBN)

将出错帧后的帧全部丢弃，从出错帧开始重新发送（即 表示需要再退回来重传已经发送过的N个分组）
累积确认，确认最后一个帧即可。（若收到了1、3、5号帧的确认 即代表5号帧及以前都收到了）
注意：数据链路层ACKn表示对第n号帧的确认，表示接收方已正确受到第n帧及以前的所有帧，下一次期望收到第n+1号帧。（此处注意与传输层TCP报文段中的确认号字段区别开，确认号字段ackn代表期望收到第n个，即 表明到n-1为止都收到了）

• 窗口大小：
  • 如果滑动窗口为n（即 帧的编号从0到n-1，n个），那么发送窗口最大为n-1（比序号少一个），接收窗口为1
  • 如果帧的编号范围是0~n-1，则发送窗口的尺寸为n-1
  • 即 采用n个比特编码，编号0~\(2^n-1\)，则发送窗口的尺寸为\(2^n-1\)（少一个给接收窗口）
    • 如n=3，即编号0,1,2,3,4,5,6,7，发送窗口大小为7，包含0,1,2,3,4,5,6。
    • 如果发送窗口的尺寸大于\(2^n-1\)，则会造成接收方无法分辨新帧和旧帧。如接收方接收完0~7后，发送确认，确认却丢失了，那么发送方又会传一次0~7，反而此时的接收方也能继续接收。
• 若信道的传输质量很差导致误码率较大时，后退N帧协议不一定优于停止-等待协议。

选择重传协议(SR)

无累积确认，每一个都要确认一遍

• 当接收方发现某帧出错后，其后继续送来的正确的帧虽然不能立即递交给接收方的高层，当接收方仍可以收下来，存放在一个缓存区中，同时要求发送方重新传送出错的那一帧。
• 一旦收到重新传来的帧后，就可以原已存于缓存区中的其余帧一并按正确的顺序递交高层。
• 采用NACK机制重传（即 否认帧NAK，没有收到，要求发送方重传）

• 无累积确认，牺牲存储空间（每一个都要确认一遍）

  累积确认：发送一个确认，代表我收到了之前所有的数据。如ACK100，代表我收到了之前的0~99。
  接收端不一定每收到一个正确的数据帧就必须立即发回一个确认帧，而可以在连续收到好几个正确的数据帧后，才对最后一个数据帧发确认信息，或者 可在自己有数据要发送时才将对以前正确收到的帧加以捎带确认。

• 窗口大小：
  • 如果滑动窗口为n，那么发送窗口最大为n/2，接收窗口为n/2
  • 如果帧的编号范围是0~n-1，则发送窗口的尺寸为n/2
  • 即 采用n个比特编码，编号0~\(2^n-1\)，则发送窗口的尺寸为\(2^{n-1}\)
• 总结：
  • 帧序号采用n bit编码，发送窗口+接收窗口<=\(2^n\)
  • 对于退后N帧，发送窗口的最大尺寸为\(2^n-1\)
  • 对于选择重传，发送窗口的最大尺寸至多是序号范围的一半\(2^{n-1}\)
  • 发送方管理超时控制的计数器数应等于缓冲器数，而不是序号空间的大小。

介质访问控制(MAC)

介质访问控制的主要任务：为使用介质的每个节点隔离来自同一信道上的其他节点所传送的信号，以协调活动节点的传输。

用来决定广播信道总信道分配的协议属于数据链路层的一个子层，称为介质访问控制(Medium Access Control, MAC)子层

---

• 静态划分信道：（将频带或时间片等固定分给各站点）
  • 信道划分介质访问控制：将使用介质的每个设备与来自同一通信信道上的其他设备的通信隔离开来，把时域和频域资源合理地分配给网络上的设备。（实际上就是把广播信道转变为点对点信道）
  • 分类：
    • 频分多路复用(Frequency Division Multiplexing, FDM)：分配不同的频带，在通信过程中自始至终都占用这个频带。
    • 时分多路复用(Time Division Multiplexing, TDM)：按时间分成若干时间片，轮流地分配给多个信号使用。
    • 波分多路复用(Wavelength Division Multiplexing, WDM)：光的频分多路复用，用不同波长（频率）的光信号
    • 码分多路复用(Code Division Multiplexing, CDM)：采用不同的编码来区分各路原始信号，既共享信道的频率，又共享时间。
  • 适用性：
    适用于站点少且固定，数据量大时
• 动态划分信道：（异步时分多路复用）
  • 分类：
    • 随机访问介质访问控制（负载较轻时）
    • 轮询访问介质访问控制（负载较重时）
  • 适用性：
    仅当有数据发时，才占信道发数据

码分多路复用(CDM)

码分多址(Code Division Multiple Access, CDMA)是码分复用的一种方式，其原理是每比特时间被划分为m个更短的时间槽，称为码片(Chip)，通常情况下每比特有64或128个码片。

码片序列实现了扩频，原本b个比特变为了mb个码片。

• 每个站被指派一个唯一的m bit码片序列。（如 0001 1011）（一般采用+1表示1，-1表示0）
  • 如发送比特1，则发送自己的m bit码片序列（0001 1011）（-1 -1 -1 1 1 -1 1 1）

  • 如发送比特0，则发送码片序列的二进制反码（1110 0100）（1 1 1 -1 -1 1 -1 -1）

    注意：当两个或多个站点同时发送时，各路数据在信道中线性相加。为从信道中分离出各路信号要求各个站点的码片序列相互正交。

• 特点：

  规格化内积是线性代数中的内容，实际上就是在的到两个向量的内积后，再除以向量的分量个数。（即 1/m * 内积）

  • 两个不同站的码片序列正交，就是向量S和T的规格化内积(inner product)都是0。（即 自己*别人=0）
  • 任何一个码片向量和该码片向量自己的规格化内积都是1。（即 自己*自己=1）

  • 任何一个码片向量和该码片反码向量的规格化内积都是-1。（即 自己*自己的反码=-1）

    分离时：这样就可以从线性叠加的数据中分离出自己的码片信号（即 一段混合的码片向量*规定的码片向量=数据(1或-1)）

• 适用性：

  码分多路复用计数具有频谱利用率高、抗干扰能力强、保密强、语音质量好等特点，还可以减少投资和降低运营成本。

  主要用于无线通信系统，特别是移动通信系统。

随机访问介质访问控制

ALOHA协议

有帧就发，随机重发

ALOHA协议(Additive Link On-line HAwaii system)

• 纯ALOHA协议：
  当网络中的任何一个站点需要发送数据时，可以不进行任何检测就发送数据。如果在一段时间内未收到确认，那么该站点就认为传输过程中发生了冲突，各发送站点需要等待一段随机的时间后再发送数据，直到发送成功。
  

• 时隙ALOHA协议：
  把所有各站在时间上同步起来，并将时间划分为一段段等长的时隙(Slot)，规定只能在每个时隙开始时才能发送一个帧。从而避免了用户发送数据的随意性，减少了数据产生冲突的可能性，提高了信道的利用率。（时隙的长度T0使得每个帧正好在一个时隙内发送完成）

  比纯ALOHA网络的吞吐量大了1倍。

  

CSMA协议

先听后发，随机重发（不要打断别人的发言！）

比ALOHA协议增加了一个载波监听装置。
载波监听多路访问(Carrier Sense Multiple Access, CSMA)协议：当一个站点要发送数据前，需要先监听总线信道，发现信道空闲后再发送。

信道状态	1-坚持CSMA	非坚持CSMA	p-坚持CSMA
空闲	立即发送数据	立即发送数据	以概率p发送数据，以概率1-p推迟到下一个时隙
忙	继续坚持侦听信道	放弃侦听，等待一个随机的时间后再侦听	持续侦听，等待下一个时隙再侦听

CSMA/CD协议

先听后发，边听边发，冲突停发（区别于CSMA协议），随机重发（不可靠，发了就不管了，无需确认）

强化碰撞：冲突后，除了立即停发之外，还要再继续发送若干比特的人为干扰信号(jamming signal)，以便让所有用户都知道现在已经发生了碰撞。

在具有广播特性的总线上实现了一对一的通信。

载波监听多点接入/碰撞检测(Carrier Sense Multiple Access with Collision Detection, CSMA/CD)协议：

• "CS"（“载波监听”）（“先听后说”）：就是发送前先监听，即每个站在数据发送之前要先检测一下总线上是否有其他站点正在发送数据，若有则暂时不发送数据，等待信道变为空闲再发送。

  注意：当某个站监听到总线是空闲时，也可能总线并非真正是空闲的。站只能检测到发送到站的数据信号电压，如果信号在路上还没有到达站，那么站是监听不到的，站会认为总线仍然是空闲的。

• "MA"（“多点接入”）：就是许多计算机以多点接入的方式连接在一根总线上。
• "CD"（“碰撞检测”）（“边说边听，一旦冲突，立即听说；等待时机，重新再说”）：就是便发送边侦听，即适配器边发送数据边检测信道上的信号电压的变化情况
  • 当几个站同时在总线上发送数据时，总线上的信号电压摆动值将会增大（相互叠加）
  • 当一个站检测到的信号电压摆动超过一定的门限值时，就认为总线上至少有两个站同时在发送数据，表明产生了碰撞。

• 适用性：
  适用于总线形网络或半双工网络环境。（有线连接的局域网）

  CSMA/CD中的站不可能同时进行发送和接受，因此采用CSMA/CD协议的以太网不可能进行全双工通信，而只能进行半双工通信。

• 争用期：（信号在最远两个端点之间往返传输的时间）
  
  如图所示，站A在发送帧后至多经过时间2τ就能知道所发送的帧是否发生碰撞(δ→0时)。即 刚无限接近B就冲突了，那么回来一趟A检测到冲突，若大于2τ，即已经到B一会了，已经争用到信道了，不会冲突了。
  因此把以太网端到端往返时间2τ称为争用期（又称冲突窗口或碰撞窗口）（2τ为能检测到发生碰撞的最长时间，过了这个时间就争用到了，不会发生碰撞了）。每个站在自己发送数据之后的一小段时间内，存在发生冲突的可能性，只有经过争用期这段时间还未检测到冲突时，才能确定这次发送不会发生冲突。
  • 2τ为能检测到发生碰撞的最长时间（即 在到达目的站B站处才发生碰撞），过了这个时间就争用到了，不会发生碰撞了。
  • 去一趟都回来了还没检测到冲突，则争用到了，不会冲突。

  • 争用期的长度：
    \[争用期的长度=2τ=RTT\]

  • 最小帧长：
    为了确保发送站在发送数据的同时能检测到可能存在的冲突，需要在发送完帧之前就能收到自己发送出去的数据（不然帧发送完了，就无法检测出信号电压的改变了，即无法检测出冲突）（得在发送完之前收到数据，才能检测到信号电压的改变，从而检测出冲突），即 帧的传输时延至少要2倍于信号在总线中的传播时延。所以规定了一个最小帧长。

    • 计算公式：
      \[最小帧长=2*总线传播时延*数据传输率\]
      \[最小帧长=W*RTT=2*(L/V)*C\]

      其中，W为传输率（最大为带宽），RTT为往返时延。
      其中，C为带宽，L为线缆长度，V为传播速率

    • 如果发送冲突，就一定是在发送的前64B之内。
    • 由于以检测到冲突就立即停止发送，这时已经发送出去的数据一定小于64B。

    • 任何站点收到帧长小于最小帧长的帧时，就把它当做无效帧立即丢弃。（即使有效）

      注意：以太网规定了最小帧长为64B(即 512bit)，凡长度小于64B的帧都是由于冲突而异常终止的无效帧。
      10Mb/s以太网取51.2微秒为争用期的长度，争用期内可发送64B（即 最小帧长）；
      100Mb/s以太网取5.12微秒为争用期长度，最小帧长也为64B不变。

  • 二进制指数类型退避算法：

    发生碰撞的站在停止发送数据后，要推迟（退避）一个随机时间才能再发送数据。（无法区别对待让其中一个站先发）

    1. 确定基本退避时间，一般是取争用期2τ；
    2. 定义重传次数k，k≤10，即\[k=min[重传次数, 10]\]（注意当重传次数大于10时，k就不再增大而一直等于10）
    3. 从整数集合[0, 1, …, (\(2^k-1\))]中随机地取出一个数，记为r。重传所需的时延就是r倍的基本退避时间，即
       \[重传所需的时延=2rτ\]。
    4. 当重传达16次仍不能成功时，说明网络太拥挤，即丢弃该帧，并向高层报告出错。
  • 步骤：
    • 准备发送。但在发送前先检测信道。
    • 检测信道。
      • 若信道忙，则不停地检测，一直等待信道转为空闲。
      • 若信道空闲，并在96比特时间内信道保持空闲（保证了帧间最小间隔）就发送这个帧
    • 检测碰撞。在发送过程中仍然不听地检测信道，即 网络适配器要边发送边监听。
      • 发送成功：在争用期内一直未检测到碰撞，这个帧肯定能够发送成功，发送完毕后什么也不做，回到1
      • 发送失败：在争用期内检测到碰撞，立即停止发送数据，并按规定发送人为干扰信号，适配器接着就执行指数退避算法，等待r倍512比特时间后，返回到2，继续检测信道。若16次仍不能成功，则停止重传向上报错。

CSMA/CA协议

发送数据时先广播告知其他结点，让其他结点在某段时间内不要发送数据，以免出现碰撞。预约信道可靠，需要确认

• 适用性：
  适用于无线局域网

  无线局域网不能简单地搬用CSMA/CD协议。

• 无线不能使用CD的原因：
  • “碰撞检测”要求一个站点在发送本站数据的同时，还必须不间断地检测信道，但接收到的信号强度往往会远远小于发送信号的强度，在无线局域网的设备中要实现这种功能就花费过大。
  • 即使能够实现碰撞检测功能，并且在发送数据时检测到信道是空闲的时候，在接收端依然有可能发生碰撞。
    • 隐蔽站问题：A站C站作用范围交于B站，当AC检测不到无线信号时，都以为B是空闲的，因而都向B发送数据，结果发生碰撞。（即 B隐藏在AC之中）
      
    • 暴露站问题：BC一直处在对方的作用范围之内，B想向A发送数据，C想向D发送数据，但BC都检测到媒体上有信号，于是不敢发送（其实B向A发送数据并不影响C向D发送数据）（即 B一直暴露在C范围之内）

• 改进：
  将碰撞检测改为了碰撞避免(Collision Avoidance, CA)。

  注意：碰撞避免并不是指协议可以完全避免碰撞，而是指协议的设计要尽量降低碰撞发生的概率。

• "CS"：“载波监听”这里的CS其实是虚拟载波监听，即 让源站将它要占用的信道的时间（包括目的站发回确认帧所需的时间）通知给所有其他站，以便使其他所有站在这一段时间都停止发送数据。

  注意：虚拟载波监听是表示其他站并没有监听信道，而是由于其他站收到了“源站的通知”才不发送数据。这种效果好像是其他站都监听了信道。
  所谓源站的通知就是源站在其MAC帧首部中的第二个字段“持续时间”中填入了在本帧结束后还要占用信道多少时间（以微秒为单位），包括目的站发送确认帧所需的时间。

• 采用三种机制来实现碰撞避免：
  • 预约信道。发送方在发送数据的同时向其他站点通知自己传输数据需要的时间长度，以便让其他站点在这段时间内不发送数据。
  • ACK帧。只有当客户端收到网络上返回的ACK信号后，才确认送出的数据已经正确到达目的。（即 确认该帧已经避免了碰撞）（CD则无连接，不需要确认，因为有线环境质量很好，不容易出错）（无线环境下容易出错重传，所以需要确认）

  • RTS/CTS帧（握手）。（RTS请求发送，CTS允许发送）发送站点在向接收站点发送数据包之前，即在DIFS之后不是立即发送数据，而是代之以发送一个请求发送RTS（Ready To Send）帧，以申请对介质的占用，当接收站点收到RTS信号后，立即在一个短帧隙SIFS之后广播回应一个准许发送CTS（Clear To send）帧，告知对方已准备好接收数据。双方在成功交换RTS/CTS信号对（即完成握手）后才开始真正的数据传递，保证了多个互不可见的发送站点同时向同一接收站点发送信号时，实际只能是收到接收站点回应CTS帧的那个站点能够进行发送，避免了冲突发生。解决无线网中“隐蔽站”的问题。

    前两者必须实现，RTS/CTS可选。

• 总结：

  1. 若站点最初有数据要发送（即 该数据帧为要发送的第一个数据帧）（而不是发送不成功再进行重传），且检测到信道空闲，在等待一个时间间隔后，就发送整个数据帧

     注意：考虑到有可能有其他的站有高优先级的帧要发送，所以要等待一个时间间隔。
     类比：就如同一伙人想进电梯，不等待的话，蜂拥而至，导致冲突；等待一会，让领导先进去，减少了冲突。

  2. 否则，信道忙，站点执行CSMA/CA协议的退避算法。
     • 一旦检测到信道忙，就冻结退避计时器
     • 只要信道空闲，退避计时器就进行倒计时
  3. 当退避计时器时间减少到0时（这时信道只可能是空闲的，因为只有空闲的时候才倒计时），站点就发送整个帧并等待确认
  4. 站点若收到确认，就知道已发送的帧已经被目的站正确收到了。这时如果要发送第二帧，就要从上面的步骤2开始，执行CSMA/CA协议的退避算法，随机选定一段退避时间

  5. 若站点在规定时间内没有收到确认帧ACK（由重传计时器控制这段时间），就必须重传帧（再次使用CSMA/CA协议争用接入信道），直到收到确认位置，或者经过若干次的重传失败后放弃发送。

802.11无线局域网使用CSMA/CA协议的同时，还增加使用停止等待协议，保证数据的可靠性，可靠传输。如果不停止等待，无线环境下很容易出错导致重传，那样造成的时间浪费更多。
802.3有线局域网的传输是不可靠的，发送方把数据发出去就不管了（当然若检测到碰撞是必须重传的），如果需要可靠传输则由高层负责。

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

• 基本思想：
  1. 当计算机都不需要发送数据时，令牌（由一组特殊的比特组合而成的帧）在环形网上游荡
  2. 直到有个站希望传送帧，等待令牌，收到令牌后，便可启动发送帧（帧中包含目的站的地址）
  3. 不管该帧是否是发给本站点的，所有站都进行转发
  4. 目的站除转发帧外，应针对该帧维持一个副本，并通过在帧的尾部设置“响应比特”来指示已收到此副本
  5. 直到该帧回到它的始发站，并由该始发站撤销该帧。
• 特点：
  • 即不共享时间，也不共享空间
  • 在随机介质访问控制的基础上，限定了有权力发送数据的节点只能有一个。
  • 使广播信道变为逻辑上点对点的信道
• 适用性：
  • 主要用在令牌环局域网中。
  • 适合负载很高（即 多个节点在同一时刻发送数据概率很大的信道）的广播信道

数据链路层研究的是“点到点”之间的通信。

局域网

局域网(Local Area Network, LAN)

• 考虑到局域网信道质量好，以太网采取了两项重要的措施来使信道更简单：
  • 采用无连接的工作方式；
  • 不对发送得数据帧进行编号，也不要求对方发回确认。
• 拓扑结构
  • 星形结构
  • 环形结构
  • 总线形结构
  • 星形和总线形结合的复合型结构

• 以太网逻辑上采用总线形拓扑结构，所有计算机共享一条总线，信息以广播方式发送。

• IEEE 802标准定义的局域网将数据链路层拆分为两个子层：逻辑链路控制(LLC)子层和媒体接入控制(MAC)子层。
  • LCC子层：
    • 与传输媒体无关，它向网络层提供无确认无连接、面向连接、带确认无连接、高速传输4种不同的连接服务类型。
    • IP包上加了8位目的/源地址服务接入点，为网络层提供统一的接口
  • MAC子层：
    • 存放与接入传输媒体有关的内容，向上层屏蔽对物理层访问的各种差异，提供对物理层的统一访问接口。
    • 主要功能包括：组帧和拆卸帧、比特传输差错检测、透明传输。
    • 用于定义如何分配信道使用权
• 以太网中各层次的主要功能：
  • 物理层的主要功能：信号的编码和译码、比特的接收和传输；
  • MAC子层的主要功能是：组帧和拆帧、比特差错检测、寻址、竞争处理；（与传输媒体有关）

  • LLC子层的主要功能是：建立和释放数据链路层的逻辑连接、提供与高层的接口、差错控制、给帧加序号。（与传输媒体无关）

    LLC子层接着就是网络层，所以在LLC加序号，再到网络里面去四散开来，最后集合起来。

IEEE 802.3(有线(基带总线形))

IEEE 802.3标准是一种基带总线形的局域网标准，它描述物理层和数据链路层的MAC子层的实现方法。

• 特点：（通常将802.3局域网（有线）简称为以太网）
  采用无连接的工作方式；不对发送的数据帧编号，也不要求发送方发送确认，即以太网尽最大努力交付数据，提供的是不可靠服务，对于差错的纠正由高层完成。

• 传输介质：

  常数	10BASE5	10BASE2	10BASE-T	10BASE-FL
  传输媒体	基带同轴电缆（粗缆）	基带同轴电缆（细缆）	非屏蔽双绞线	光纤对(850nm)
  编码	曼彻斯特编码	曼彻斯特编码	曼彻斯特编码	曼彻斯特编码
  拓扑结构	总线形	总线形	星形	点对点
  最大段长	500m	185m	100m	2000m
  最多结点数目	100	30	2	2

  注意：10BASE-T非屏蔽双绞线以太网拓扑结构为星形网，星形网中心为集线器，当使用集线器的以太网在逻辑上仍然是一个总线网，属于一个冲突域。

  • 第1部分：数字表示数据传输率，如10表示10Mb/s
  • 第2部分：Base表示介质上的信号为基带信号（即 基带传输，采用曼彻斯特编码）
  • 第3部分：
    • 如果是字母，T表示双绞线(Twisted Pair)、F表示光纤(Fibre-optical)
    • 如果是数字，表示所支持的最大传输距离，如2表示200m

• 网卡：

  计算机与外界局域网的连接是通过主机箱内插入的一块网络接口板（又称网络适配器(Adapter)或网络接口卡(Network Interface Card, NIC）实现的。

  • 网卡上装有处理器和存储器，是工作在数据链路层的网路组件。
  • 网卡是局域网中连接计算机和传输介质的接口。
  • 全世界的每块网卡在出厂时都有一个唯一的代码，称为介质访问控制(MAC)地址，这个地址用于控制主机在网络上的数据通信。
  • MAC地址，也称为物理地址，长为6B(mac电脑NB)，高24位为厂商代码，低24位为厂商自行分配的网卡***。
• 高速以太网：速率达到或超过100Mb/s的以太网
  • 100BASE-T以太网：
    • 全双工方式：无冲突发送，不使用CSMA/CD协议
    • 半双工方式
  • 吉比特以太网（千兆以太网）（G-bit）：
    • 全双工方式：无冲突发送，不使用CSMA/CD协议
    • 半双工方式：使用CSMA/CD协议
  • 10吉比特以太网：
    • 只使用光纤

    • 只用全双工方式：没有争用问题，也不使用CSMA/CD协议。

      以太网是可扩展的、灵活的，易于安装，稳健性好。

以太网MAC帧

DIX Ethernet V2标准的MAC帧格式：

• 前导码：8字节，使接收端与发送端时钟同步。
  • 前同步码：7字节，用来快速实现MAC帧的比特同步

  • 帧开始定界符：表示后面的信息就是MAC帧

    注意：MAC帧并不需要帧结束符，因为以太网在传送帧时，各帧之间必须有一定的间隙。但不要误以为以太网MAC帧不需要尾部，在数据链路层上，帧既要加首部，也要加尾部。

---

以太网MAC帧

• 目的地址：6字节（MAC地址）（目的地址在第一个，为了方便找到目的地，只用扫描第一个就能知道目的地了）
• 源地址：6字节
• 类型：2字节，指出数据域中携带的数据应交给哪个协议实体处理（802.3为长度域）
• 数据：46~1500字节，最短46字节=以太网帧的最短帧长-首尾18字节，最长1500字节是规定。
• 校验码(FCS)：4字节，校验范围从目的地址段到数据段的末尾。

IEEE 802.11(无线)

IEEE 802.11是无线局域网的一系列协议标准。

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

  802.11标准规定无线局域网的最小构件是基本服务集(Basic Service Set, BSS)。一个基本服务集包括一个基站和若干移动站。

  • 所有的站在本BSS内都可以直接通信，但在与本BSS外的站通信时，都要通过本BSS的基站（也称接入点，(Access Point, AP)，其实就相当于一个热点，其作用和网桥相似）
  • 基础设施模式是指预先建立起来的、能够覆盖一定地理范围的一批固定基站。
  • 移动主机通过基站接入有线网络

  • 切换：移动主机的移动可能会改变与之相关联的基站。

    关联：无线主机位于某个基站的无线通信覆盖范围内；该主机使用该基站中继它与更大网络之间的数据。
    切换：当一台移动主机移动范围超出一个基站的覆盖范围而到达另一个基站的覆盖范围后，它将改变其接入更大网络的接入点。

• 无固定基础设施无线局域网：自组织网络
  自组织网络没有上述基本服务集中的接入点(AP),而是由一些平等状态移动站相互通信组成的临时网络。各站点之间地位平等，中间站点都为转发站点，这些结点都具有路由器功能。
  • 无基站
  • 节点（移动主机）仅仅能够在其覆盖范围内向其他节点传送数据。
  • 节点之间相互通信组成的临时网络：在它们内部进行选路和地址分配。

802.11局域网的MAC帧

• MAC首部，共30字节。帧的复杂性都在帧的首部。
• 帧主体，也就是帧的数据部分，不超过2312字节，这个数值比以太网的最大长度长很多。不过802.11帧的长度通常都是小于1500 字节。
• 帧检验序列FCS是尾部，共4字节

• 802. 11数据帧的地址：

  802.11数据帧最特殊的地方就是有四个地址字段。地址4用于自组织网络。我们在这里只讨论前三种地址。

  去往AP	来自AP	地址1	地址2	地址3	地址4
  1	0	AP地址	源地址	目的地址	--
  0	1	目的地址	AP地址	源地址	--

  注意：A→B，AP进行中转。
  去往AP（A→AP）：先到AP（中转），从源过去的，到目的地。
  来自AP（AP→B）：先到目的地，从AP过去的，从源开始。

令牌环网

1. 网络空闲时，环路中只有令牌帧在循环传递。
2. 令牌传递到有数据要发送的站点时，该站点就修改令牌中的一个标志位，并在令牌中附加自己需要传输的数据，将令牌变成一个数据帧，然后将这个数据帧发送出去。
3. 数据帧沿着环路传输，接收到的站点一边转发数据，一边查看帧的目的地址。如果目的地址和自己的地址相同，那么接收站就复制该数据帧以便进一步处理。
4. 数据帧沿着环路传输，直到到达该帧的源站点，源站点接收到自己发出去的数据帧后边不再进行转发。同时，发送方可以通过检验返回的数据帧来查看数据传输过程中是否有错，有错则重传。

5. 源站点传送完数据后，重新产生一个令牌，并将令牌传递给下一个站点，以交出对媒体的访问权限。

   令牌环网在物理上采用星形拓扑结构，但在逻辑上仍是环形拓扑结构。

广域网

注意：广域网不等于互联网，互联网可以连接不同类型的网络（既可以连接局域网，又可以连接广域网），通常使用路由器来连接。
广域网由一些结点交换机（注意不是路由器，结点交换机和路由器都用来转发分组，它们的工作原理也类似。结点交换机在单个网络中转发分组，而路由器在多个网络构成的互联网中转发分组）及连接这些交换机的链路组成。
结点交换机的功能是将分组存储并转发。

• 与局域网的区别：
  • 局域网使用的协议主要在数据链路层（还有少量在物理层）

  • 广域网使用的协议主要在网络层

    注意：给数据“包装”的一层控制信息，用于实现检错纠错等功能。如果是数据链路层协议的控制信息，那么就使用了数据链路层协议，如果是网络层的控制信息，那么就使用了网络层协议。

PPP协议

• 基本概念：
  PPP(Point-to-Point Protocol)是使用串行线路通信的面向字节的协议，
• 应用：
  该协议应用在直接连接两个结点的链路上。

• 设计目的：
  主要是用来通过拨号或专线方式建立点对点连接发送数据，使其成为各种主机、网桥和路由器之间简单连接的一种共同的解决方案。

  使用拨号电话线接入互联网时，用户计算机和ISP进行通信时所使用的数据链路层协议就是PPP协议。

• 功能：
  • 差错检测
  • 点对点
  • 只支持全双工
  • 不可靠（不使用序号和确认机制）
  • 提供差错检测，但不提供纠错功能，只保证无差错接收
  • 两端可以运行不同的网络协议
  • 面向字节
• 不需要的功能：
  • 纠错
  • 流量控制

  • 序号

    不需要上面三种是因为PPP建立在一个质量好、可靠的网络上。

  • 多点线路
  • 半双工或单工链路
• 组成部分：
  • 一个将IP数据报封装到串行链路的方法
  • 链路控制协议(LCP, Link Control Protocol)：一种扩展链路控制协议，用于建立、配置、测试和管理数据链路

  • 网络控制协议(NCP, Network Control Protocol)：PPP协议允许同时采用多种网络层协议，每个不同的网络层协议要用一个相应的NCP来配置，为网络层协议建立和配置逻辑连接。

    工作过程：物理层→LCP→NCP→数据

• 透明传输问题：
  • 用在同步传输链路时，协议规定采用硬件来完成比特填充（和HDLC的做法一样）（因为传输的是一连串的数据，所以用比特填充比较快）

  • 用在异步传输时，就使用一种特殊的字符填充法（因为是将比特分成小组传送的，所以不好用比特进行填充（本来连续5个1，结果被分开了），只能用字符填充了）

    异步传输（Asynchronous Transmission）： 异步传输将比特分成小组进行传送，小组可以是8位的1个字符或更长。
    同步传输（Synchronous Transmission）：同步传输的比特分组要大得多。
    注意：PPP是点对点的，并不是总线形，所以无需采用CSMA/CD协议，自然就没有最短帧。

HDLC协议

高级数据链路控制协议(High-level Data Link Control, HDLC)协议是ISO制定的面向比特（记住PPP协议是面向字节的）的链路层协议。是一组用于在网络节点间（用比特）传送数据的协议,是在数据链路层中广泛使用的一种协议。

• 特点：
  • 透明传输：0比特填充
  • 全双工通信
• 采用主从站操作方式工作：
  • 主站：负责控制链路的操作，主站发出的帧称为命令帧
  • 从站：受控于主站，按主站的命令进行操作；发出的帧称为响应帧。
  • 正常响应方式：非平衡结构操作方式
    • 主站向从站传输数据，从站响应传输
    • 从站只有在收到主站的许可后，才能进行响应
  • 异步平衡方式：平衡结构操作方式
    • 每个复合站都可以进行对另一个站的数据传输
  • 异步响应方式：非平衡结构操作方式
    • 从站即使未收到主站的允许，也可以进行传输。
• HDLC帧：
  • 信息帧(I)：用来传输数据信息，或 使用捎带技术对数据进行确认。
  • 监督帧(S)：用于流量控制和差错控制，执行对信息帧的确认、请求重发和请求暂停发送等功能。

  • 无编号帧(U)：用于提供对链路的而建立、拆除等多种控制功能。

    "无奸细"：无监信

设备

第二层网络（数据链路层）设备可以解决冲突域问题，第三层（网络层）网络设备才能解决广播域问题

• 直通式：只检查目的MAC地址(6B)
• 存储转发式：还查正误（查整个帧）

网桥

连接不同链路层，连接网段、存储转发帧、隔离碰撞域（冲突域）、不隔离广播域，所连得网络设备享有全部的带宽
两个或多个以太网通过网桥连接后，就成为一个覆盖范围更大的以太网，而原来的每个以太网就称为一个网段。

• 功能：
  • 在数据链路层扩展局域网时使用网桥
  • 根据MAC帧的目的地址对收到的帧进行转发
• 建立转发表：
  查找转发表中与收到帧的源地址有无匹配的项目。
  • 如果有，则把原有的项目更新。
  • 如果没有，就在转发表中增加一个项目（源地址，进的接口和时间）
• 转发帧：
  查找转发表中与收到的帧的目的地址有无匹配的项目。

  • 如果没有，则通过所有其他接口（但进入网桥的接口除外）进行转发。

    注意：这个与

  • 如果有，则按转发表中给出的接口进行转发
  • 若转发表中给出的接口就是该帧进入网桥的接口，则丢弃这个帧（因为源站和目的站处在同一网段，这时不需要经过网桥进行转发）

• 转发表：

  注意建立表和查找转发表操作不一样。

  地址	接口
  源地址（建立时）	进的接口
  目的地址（转发时只是查找）	原本有接口

• 基本特征：
  • 网桥可以将一个局域网分段成隔离的碰撞域。
  • 网桥能够互连两个采用不同链路层协议、不同传输介质与不同传输速率的网络
  • 以接收、存储、地址过滤与转发的方式实现互连的网络之间的通信
  • 需要互连的网络在数据链路层以上采用相同的协议

  • 可以分隔两个网络之间的广播通信量，有利于改善互连网络的性能与安全性。

    注意：一般情况下，存储转发类设备都能进行协议转换，即 连接的两个网段可以使用不同的协议

• 优点：
  • 过滤通信量
  • 扩大了物理范围
  • 可以互连不同物理层、不同MAC子层和不同速率（如10Mb/s和100Mb/s以太网）的局域网
• 缺点：
  • 增大了时延
  • MAC子层没有流量控制功能（流量控制需要用到编号机制，而编号机制的实现在LLC子层）
  • 不同MAC子层的网段桥连接在一起时，需要进行帧格式的转换

• 适用性：
  只适用于用户数不多和通信量不大的局域网
  ---

  根据路由选择算法的不同，可见网桥分为透明网桥和源路由网桥

透明网桥

选择的不是最佳路由

• 透明网桥以混杂方式工作，它接收与之连接的所有LAN传送的每一帧。到达帧的路由选择过程取决于源LAN和目的LAN：
  • 如果源LAN和目的LAN相同，那么丢弃该帧（就在本局域网内）
  • 如果源LAN和目的LAN不同，那么转发该帧
  • 如果目的LAN未知，那么扩散该帧

• 为了避免转发的帧在网络中不断地“兜圈子”，透明网桥使用了生成树算法（无环），确保每个源到目的地只有唯一的一条路径。

  注意：生成树使得整个扩展局域网在逻辑上形成树形结构，所以工作时逻辑上没有环路，当生成树一般不是最佳路由。

源路由网桥

选择的是最佳路由

• 在源路由网桥中，路由选择由发送数据帧的源站负责，网桥只根据数据真正的路由信息对帧进行接收和转发。
• 为了找到最佳的路由，源站以广播的方式向目的站发送一个发现帧(Discovery Frame)作为探测之用。
• 源路由的生成过程是：
  1. 在未知路径前，源站要先发送一个发现帧；
  2. 途中的每个网桥都转发此帧
  3. 最终该发现帧坑你从多个路径到达目的站；
  4. 目的站一一发送应答帧
  5. 每个应答帧间通过原路径返回，途经的网桥把自己的标志记录在应答帧中
  6. 源站选择出一个最佳路由

  7. 以后，凡是从这个源站向该目的站发送的帧的首部，都必须携带这一路由信息。

     注意：透明网桥和源路由网桥中提到的最佳路径并不是经过路由器最少的路由，而是发送帧往返时间最短的路由。

交换机

连接多个以太网，多端口网桥，所连得网络设备享有全部的带宽，设置了VLAN也可以隔离广播域

网桥的主要限制是在任一时刻通常只能执行一个帧的转发操作，于是出现了局域网交换机，又称以太网交换机。从本质上来说，以太网交换机是一个多端口的网桥，他工作在数据链路层，能经济地将网络分为小的冲突域，为每个工作站提供更高的带宽。

• 特点：
  • 每个接口都与一个单台主机或另一个以太网交换机相连，一般都工作在全双工方式（主机独占）
  • 具有并行性。能同时连接多对接口，使多对主机能同时通信。
  • 相互通信的主机都是独占传输媒体，无碰撞地传输数据
  • 可以将一个局域网分段成隔离的碰撞域。
• 优点：
  • 对于普通10Mb/s的共享式以太网，若有N个用户，则每个用户占有的平均带宽只有1/N
  • 在使用以太网交换机时，虽然从每个端口到主机的带宽还是10Mb/s（半双工交换机）（全双工是20Mb/s），但由于一个用户在通信时是独占而不是和其他网络用户共享传输媒体的带宽，因此拥有N对端口的交换机的总容量为N*10Mb/s（看清楚了 这里是N对）（也就是说n个端口除以2，即 两个相连的交换机各占一半容量）
• 交换模式：
  • 直通式交换机：值检查帧的目的地址，这使得帧在接收后几乎能马上被转出去
    • 优点：速度快
    • 缺点：缺乏智能型和安全性，也无法支持具有不同速率的端口的交换
  • 存储转发式交换机：先将接收到的帧缓存到高速缓存器中，并检查数据是否正确，确认无误后通过查找表转换成输出端口将该帧发送出去。
    • 优点：可靠性高，能支持不同速率的端口间的转换
    • 缺点：延迟较大