五.流量控制与可靠传输机制
较高的发送速度和较低的接收能力的不匹配，会造成传输出错，因此流量控制也是数据链路层的一项重要工作。
数据链路层的流量控制是点对点的，而传输层的流量控制是端到端的。
数据链路层的流量控制是点对点的，而传输层的流量控制是端到端的。
传输层流量控制手段：接收端给发送端一个窗口公告。
1.流量控制的方法
2.可靠传输、滑动窗口、流量控制
Summary:
2.1停止-等待协议
2.1.1.为什么要有停止-等待协议?
除了比特出差错，底层信道还会出现丢包问题。
为了实现流量控制。
丢包：物理线路故障、设备故障、病毒攻击、路由信息 错误等原因，会导致数据包的丢失。
2.1.2.研究停等协议的前提?
虽然现在常用全双工通信方式，但为了讨论问题方便，仅考虑一方发送数据（发送方），一方接收数据 （接收方）。
因为是在讨论可靠传输的原理，所以并不考虑数据是在哪一个层次上传送的。
“停止-等待”就是每发送完一个分组就停止发送，等待对方确认，在收到确认后再发送下一个分组。
2.1.3.停等协议有几种应用情况？
无差错情况&有差错情况
2.1.4停等协议性能分析
2.2.1信道利用率
Sunnmary:
六.后退N帧协议(GBN协议)
1.停止-等待协议的弊端
2.滑动窗口
3.GBN发送方必须响应的三件事
3.1上层的调用
上层要发送数据时，发送方先检查发送窗口是否已满，如果未满，则产生一个帧并将其发送；如果窗口已满，发送方只需将数据返回给上层，暗示上层窗口已满。上层等一会再发送。(实际实现中，发送方可以缓存这些数据，窗口不满时再发送帧)。
3.2收到了一个ACK
GBN协议中，对n号帧的确认采用累积确认的方式，标明接收方已经收到号帧和它之前的全部帧。
3.3超时事件
协议的名字为后退N帧/回退N帧，来源于出现丢失和时延过长帧时发送方的行为。就像在停等协议中一样，定时器将再次用于恢复数据帧或确认帧的丢失。如果出现超时，发送方重传所有已发送但未被确认的帧。
4.GBN接收方要做的事
如果正确收到n号帧，并且按序，那么接收方为n帧发送一个ACK，并将该帧中 的数据部分交付给上层
这句话的意思是:假如现在收到了0 1 2号帧 收到4 5号帧,4,5就丢弃掉,收到0,1,2号后,需要等待接受3号帧
其余情况都丢弃帧，并为最近按序接收的帧重新发送ACK。接收方无需缓存任 何失序帧，只需要维护一个信息：expectedseqnum（下一个按序接收的帧序 号）
5.运行中的GBN
6.滑动窗口长度
7.GBN协议性能分析
优点
因连续发送数据帧而提高了信道利用率
缺点
在重传时必须把原来已经正确传送的数据帧重传，是传送效率降低。
Summary:
1.累积确认（偶尔销带确认）
2.接收方只按顺序接收帧，不按序无情丢弃
3.确认序列号最大的、按序到达的帧
4.发送窗口最大为(2^n)-1，接收窗口大小为1
七.选择重传协议(SR)
1.滑动窗口
2.SR发送方必须响应的三件事
2.1上层的调用
从上层收到数据后，SR发送方检查下一个可用于该帧的序号，如果序号位于发送窗口内，则发送数据帧；否 则就像GBN一样，要么将数据缓存，要么返回给上层之后再传输。
2.2收到了一个ACK
如果收到ACK，加入该帧序号在窗口内，则SR发送方将那个被确认的帧标记为已接收。如果该帧序号是窗口 的下界（最左边第一个窗口对应的序号），则窗口向前移动到具有最小序号的未确认帧处。如果窗口移动了 并且有序号在窗口内的未发送帧，则发送这些帧。
2.3超时事件
每个帧都有自己的定时器，一个超时事件发生后只重传一个帧。
3.SR接收方要做的事
4.运行中的SR
5.滑动窗口长度
6.SR协议重点总结
习题
1.从滑动窗口的观，点看，当发送窗口为1、接收窗口也为1时，相当于ARQ的(C)方式.
A.回退N帧ARQ
B.选择重传ARQ
C.停止-等待
D.连续ARQ
2.在简单的停止等待协议中，当帧出现丢失时，发送端会永远等待下去，解决这种死锁现象的办法是(D)
A.差错校验
B.帧序号
C.NAK机制
D.超时机制
3.一个信道的数据传输速率为4kb/s,单向传播时延为30s,如果使停止等待协议的信道最大利用率达到80%，那么要求的数据帧长度至少为(D)。
A.160bit
B.320bit
C.560bit
D.960bit
4.数据链路层采用后退N帧协议方式，进行流量控制和差错控制，发送方已经发送了编号0~6的帧。计时器超时时，只收到了对1、3和5号顿的确认，发送方需要重传的帧的数目是(A).
A.1
B.2
C.5
D.6
5.【2009統考真题】数据链路层采用了后退N顿（GBN)协议，发送方已经发送了编号为0~7的帧。计时器超时时，若发送方只收到0、2、3号帧的确认，则发送方需要重发的帧数是(C)。
A.2
B.3
C.4
D.5
6.数据链路层采用了后退N帧的（GBN)协议，如果发送宙口的大小是32，那么至少需要(C)位的序列号才能保证协议不出错。
A.4
B.5
C.6
D.7
7.【2012统考真题】两台主机之间的数据链路层采用后退N帧协议(GBN)传输数据，数据传输速率为16kb/s,单向传播时延为270ms,数据帧长度范围是128~512字节，接收方总是以与数据帧等长的帧进行确认。为使信道利用率达到最高，帧序列的比特数至少为(B).
A.5
B.4
C.3
D.2
8.若采用后退N帧的ARQ协议进行流量控制，帧编号字段为7位，则发送窗口的最大长度为(C)。
A.7
B.8
C.127
D.128
9.【2011统考真题】数据链路层采用选择重传协议（SR)传输数据，发送方已发送0~3号数据帧，现已收到1号帧的确认，而0、2号帧依次超时，则此时需要重传的帧数是(B)。
A.1
B.2
C.3
D.4
10.一个使用选择重传协议的数据链路层协议，如果采用了5位的帧序列号，那么可以选用的最大接收窗口是(B)。
A.15
B.16
C.31
D.32
11.对于窗口大小为的滑动窗口，最多可以有（B)帧已发送但没有确认.
A.0
B.n-1
C.n
D.n/2
12.对无序接收的滑动窗口协议，若序号位数为，则发送窗口最大尺寸为（D)。
A.2^n-1
B.2n
C.2n-1
D.2^n
14.【2014统考真题】主机甲与主机乙之间使用后退N帧协议（GBN)传输数据，甲的发送窗口尺寸为1000，数据帧长为1000字节，信道带宽为100Mb/s,乙每收到一个数据帧立即利用一个短帧（忽略其传输延迟）进行确认，若甲、乙之间的单向传播时延是50ms,则甲可以达到的最大平均数据传输速率约为（C)。
A.10Mb/s
B.20Mb/s
C.80Mb/s
D.100Mb/s
15.【2018统考真题】主机甲采用停止-等待协议向主机乙发送数据，数据传输速率是3kb/s,单向传播时延是200ms,忽略确认顿的传输时延。当信道利用率等于40%时，数据帧的长度为()。
A.240比特
B.400比特
C:480比特
D.800比特
16.【2020统考真题】假设主机甲采用停等协议向主机乙发送数据帧，数据帧长与确认帧长均为1000B,数据传输速率是10kb/s,单项传播延时是200s。则甲的最大信道利用率为(D)。
A.80%
B.66.7%
C.44.4%
D.40%
停止等待协议的工作原理是：发送方每发送一帧，都要等待接收方的应答信号，之后才能发送下一帧；接收方每接收一帧，都要反馈一个应答信号，表示可接收下一帧，如果接收方不反馈应答信号，那么发送方必须一直等待。
在停止等待协议中，发送端设置了计时器，在一个帧发送之后，发送端等待确认，如果在计时器计满时仍未收到确认，那么再次发送相同的帧，以免陷入永久的等待。
设C为数据传输速率，L为帧长，R为单程传播时延，停止-等待协议的信道最大利用率为(LC/(L/C+2)=L/(L+2RC=L/(L+2×30ms×4kb/s)=80%,得出L=960bit。
GBN一般采用累计确认，因此收到了对5号帧的确认意味着接收方已收到1~5号帧，因此发送方仅需要重传6号帧。
在后退N帧协议中，当接收方检测到某个帧出错后，会简单地丢弃该帧及所有的后续帧，发送方超时后需重传该数据帧及所有的后续帧。这里应注意，连续ARQ协议中，接收方一般采用累计确认的方式，即接收方对按序到达的最后一个分组发送确认，因此本题中收到3的确认帧就表示编号为0,1,2,3的帧已接收，而此时发送方未收到1号帧的确认只能代表确认帧在返回的过程中丢失，而不代表1号帧未到达接收方。因此需要重传的帧为编号是4,5,6,7的帧。
在后退N帧的协议中，序列号个数不小于MAX_SEQ+1,题中发送窗口的大小是32，那么序列号个数最少应该是33个。所以最少需要6位的序列号才能达到要求。
数据帧长度是不确定的，范围是128一512B,但在计算至少窗口大小时，为了保证无论数据帧长度如何变化，信道利用率都能达到最高，应以最短的帧长计算。如果以512B计算，那么求得的最小帧序号数在128B的帧长下，达不到最高信道利用率。首先计算出发送一帧的时间128×8/16×10)=64ms:发送一帧到收到确认为止的总时间为64+270×2+64=668ms;这段时间总共可以发送668/64=10.4帧，发送这么多帧至少需要用4位比特进行编号。
接收窗口整体向前移动时，新窗口中的序列号和旧窗口的序列号产生重叠，致使接收方无法区别发送方发送的帧是重发帧还是新帧，因此在后退W帧的ARQ协议中，发送窗口W_T≤2^n-1。本题中n=7,因此发送窗口的最大长度是127。
选择重传协议中，接收方逐个确认正确接收的分组，不管接收到的分组是否有序，只要正确接收就发送选择ACK分组进行确认。因此选择重传协议中的ACK分组不再具有累积确认的作用。对于这一点，要特别注意与GBN协议的区别。此题中只收到1号帧的确认，0、2号帧超时，由于对1号帧的确认不具累计确认的作用，因此发送方认为接收方未收到0、2号帧，于是重传这两帧。
在选择重传协议中，若采用比特对帧进行编号，为避免接收端向前移动窗口后，新的窗口与旧的窗口产生重叠，接收窗口的最大尺寸应该不超过序号范围的一半，即W_R≤2^n-1。因此选B。
在连续ARQ协议中，发送窗口的大小≤窗口总数-1。例如，窗口总数为8，编号为0一7，假设这8个帧都已发出，下一轮又发出编号0~7的8个帧，接收方将无法判断第二轮发的8个帧到底是重传帧还是新帧，因为它们的序号完全相同。另一方面，对于回退N帧协议，发送窗口的大小可以等于窗口总数一1，因为它的接收窗口大小为1，所有的帧保证按序接收。因此对于窗口大小为n的滑动窗口，其发送窗口大小为1，即最多可以有1帧已发送但没有确认。
本题并未直接告知使用的是选择重传协议，而是通过间接方式给出的。题目说无序接收的滑动窗口协议，说明接收窗口大于1，所以得出数据链路层使用的是选择重传协议，而选择重传协议的发送窗口最大尺寸为2^n-1。
C D A
1)发送窗口大小为7意味着发送方在没有收到确认之前可以连续发送7个帧，由于发送方A已经发送编号为0~3的四个帧，下一个帧将是编号为4的帧。
2)当帧的序号长度为k比特时，对于选择重传协议，为避免接收端向前移动窗口后，新的窗口与旧的窗口产生重叠，接收窗口的最大尺寸应该不超过序列号范围的一半，即W≤2。
3)设发送窗口为[L,U],发送窗口大小的初始值为W,发送窗口的大小应该大于等于0，但小于等于W,所以有0≤U-L+1≤W。因此L≥(U-W+1)mod2^k。
考虑制约甲的数据传输速率的因素。首先，信道带宽能直接制约数据的传输速率，传输速率一定是小于等于信道带宽的：其次，主机甲、乙之间采用后退N帧协议，那么因为甲、乙主机之间采用后退N帧协议传输数据，要考虑发送一个数据到接收到它的确认之前，最多能发送多少数据，甲的最大传输速率受这两个条件约束，所以甲的最大传输速率是这两个值中小的那一个。甲的发送窗口的尺寸为1000，即收到第一个数据的确认之前，最多能发送1000个数据帧，也就是发送
1000×1000B=1B的内容，而从发送第一个帧到接收到它的确认的时间是一个帧的发送时延加上往返时延，即1000B/100Mb/s+50ms+50ms=0.10008s,此时的最大传输速率为1MB/0.10008s≈10B/s=80Mb/s。信道带宽为100Mb/s,所以答案为min{80Mb/s,100Mb/s}=80Mb/s,选C。
信道利用率=传输帧的有效时间传输帧的周期。假设帧的长度为x比特。对于有效时间，应该用帧的大小除以数据传输速率，即x/(3kb/s)。对于帧的传输周期，应包含4部分：帧在发送端的发送时延、帧从发送端到接收端的单程传播时延、确认帧在接收端的发送时延、确认帧从接收端到发送端的单程传播时延。这4个时延中，由于题目中说“忽略确认帧的传输时延”，因此不计算确认帧的发送时延（注意区分传输时延和传播时延的区别，传输时延也称发送时延，和传播时延只有一字之差)。所以帧的传输周期由三部分组成：首先是帧在发送端的发送时延x/(3kb/s),其次是帧从发送端到接收端的单程传播时延200ms,最后是确认帧从接收端到发送端的单程传播时延200ms,三者相加可得周期为x/(3kb/s)+400ms。代入信道利用率的公式，求出x=800bit。答案选D。
发送数据顿和确认帧的时间均为t=1000x8b/10kb/s=800ms。
发送周期为T=800ms+200ms+800ms+200ms=2000ms。
信道利用率为/T×100%=800/2000=40%
八.介质访问控制
1.传输数据使用的两种链路
点对点链路
广播式链路
2.介质访问控制
介质访问控制的内容就是，采取一定的措施，使得两对节点之间的通信不会发生互相干扰的情况。
3.(静态划分信道)信道划分介质访问控制
信道划分介质访问控制：将使用介质的每个设备与来自同一信道上的其他设备的通信隔离开，把时域和频域资源合理地分配给网络上的设备。
3.1频分多路复用(FDM)
3.2时分多路复用(TDM)
3.3.统计时分复用 (STDM)
每一个STDM帧中的时隙数小于连接在集中器上的用户数。各用户有了数据就随时发往集中器的输入缓存，然后集中器按顺序依次扫描输入缓存，把缓存中的输入数据放入STDM帧中，一个STDM帧满了就发出。STDM帧不是固定分配时隙，而是按需动态分配时隙。
3.4波分多路复用(WDM)
彼分多路复用就是光的频分多路复用，在一根光纤中传输多种不同波长（频率）的光信号，由于波长（频率）不同，所以各路光信号互不干扰，最后再用波长分解复用器将各路波长分解出来。
3.5.码分多路复用(CDM)
九.动态分配信道
1.随机访问介质访问控制
1.1ALOHA协议
1.1.1纯ALOHA协议
1.1.2时隙ALOHA协议
ALOHA的点
1.纯ALOHA比时隙ALOHA吞吐量更低，效率更低。
2.纯ALOHA想发就发，时隙ALOHA只有在时间片段开始时才能发。
1.2CSMA协议 [载波监听多路访问协议CSMA（carrier sense multiple access）]
CS：载波侦听/监听，每一个站在发送数据之前要检测一下总线上是否有其他计算机在发送数据。
当几个站同时在总线上发送数据时，总线上的信号电压摆动值将会增大（互相叠加）。当一个站检测到的信号 电压摆动值超过一定门限值时，就认为总线上至少有两个站同时在发送数据，表明产生了碰撞，即发生了冲突
MA：多点接入，表示许多计算机以多点接入的方式连接在一根总线上。
1.2.1 1-坚持CSMA
坚持指的是对于监听信道忙之后的坚持。
1-坚持CSMA思想：
如果一个主机要发送消息，那么它先监听信道。
空闲则直接传输，不必等待。
忙则一直监听，直到空闲马上传输。
如果有冲突（一段时间内未收到肯定回复），则等待一个随机长的时间再监听，重复上述过程。
优点：只要媒体空闲，站点就马上发送，避免了媒体利用率的损失。
缺点：假如有两个或两个以上的站点有数据要发送，冲突就不可避免
1.2.2非坚持CSMA
非坚持指的是对于监听信道忙之后就不继续监听。
非坚持CSMA思想：
如果一个主机要发送消息，那么它先监听信道。
空闲则直接传输，不必等待。
忙则等待一个随机的时间之后再进行监听。
优点：采用随机的重发延迟时间可以减少冲突发生的可能性。
缺点：可能存在大家都在延迟等待过程中，使得媒体仍可能处于空闲状态，媒体使用率降低。
1.2.3p-坚持CSMA
p-坚持指的是对于监听信道空闲的处理。
p-坚持CSMA思想：
如果一个主机要发送消息，那么它先监听信道。
空闲则以p概率直接传输，不必等特；概率1-p等待到下一个时间槽再 传输。
忙则持续监听直到信道空闲再以p概率发送。
若冲突则等到下一个时间槽开始再监听并重复上述过程。
优点：既能像非坚持算法那样减少冲突，又能像1-坚持算法那样减少媒体空闲时间的这种方案。
1.2.4三种CSMA对比总
1.2CSMA/CD协议 [载波监听多点接入/碰撞检测CSMA/CD（carrier sense multiple access with collision detection)]
CS：载波侦听/监听，每一个站在发送数据之前以及发送数据时都要检测一下总线上是否有其他计算机在发送数据。
MA：多点接入，表示许多计算机以多点接入的方式连接在一根总线上。
总线型网络
CD：碰撞检测（冲突检测），“边发送边监听”，适配器边发送数据边检测信道上信号电压的变化情况，以便判 断自己在发送数据时其他站是否也在发送数据。
半双工网络
1.2.1传播时延对载波监听的影响
1.2.2如何确定碰撞后的重传时机?
例：在以太网的二进制回退算法中，在11次碰撞之后，站点会在0(？)之间选择一个随机数。
k=min{11,10}=10
2^10-1=1023
r∈[0,1,2,3,4,5,6,....,1023]
1.2.3最小帧长问题
1.3CSMA/CA协议 [载波监听多点接入/碰撞避免CSMA/CA（carrier sense multiple access with collision avoidance）]
1.3.1工作原理
发送数据前，先检测信道是否空闲。
空闲则发出RTS(request to send),RTS包括发射端的地址、接收端的地址、下一份数据将持续发送的时间等信息：信道忙则等待。
接收端收到RTS后，将响应CTS(clear to send)。
发送端收到CTS后，开始发送数据帧（同时预约信道：发送方告知其他站点自己要传多久数据）。
接收端收到数据帧后，将用CRC来检验数据是否正确，正确则响应ACK帧。
发送方收到八CK就可以进行下一个数据帧的发送，若没有则一直重传至规定重发次数为止（采用二进制指数退避算法来确定随机的推迟时间)。
1.3.2CSMA/CD与CSMA/CA
相同点：
CSMA/CD与CSMA/CA机制都从属于CSMA的思路，其核心是先听再说。换言之，两个在接入信道之前都须要 进行监听。当发现信道空闲后，才能进行接入。
不同点：
1.传输介质不同：CSMA/CD用于总线式以太网【有线】，而CSMA/CA用于无线局域网【无线】
2.载波检测方式不同：因传输介质不同，CSMA/CD与CSMA/CA的检测方式也不同。CSMA/CD通过电缆中电压的变化来检测，当数据发生碰撞时，电缆中的电压就会随着发生变化；而CSMA/CA采用能量检测(ED)、载波检测(CS)和能量载波混合检测三种检测信道空闲的方式。
3.CSMA/CD检测冲突，CSMA/CA避免冲突，二者出现冲突后都会进行有上限的重传。
Summary:
2.轮询访问介质访问控制
2.1介质访问控制
信道划分介质访问控制（MAC Multiple Access Control ）协议：
基于多路复用技术划分资源。
网络负载重：共享信道效率高，且公平
网络负载轻：共享信道效率低
随机访问MAC协议： 冲突
用户根据意愿随机发送信息，发送信息时可独占信道带宽。
网络负载轻：共享信道效率高,单个节点可利用全部带宽
网络负载重：产生冲突开销
2.2轮询协议
问题： 1.轮询开销 2.等待延迟 3.单点故障
2.3令牌传递协议
令牌：一个特殊格式的MAC控制帧，不含任何信息。
控制信道的使用，确保同一时刻只有一个结点独占信道。
令牌环网无碰撞
每个结点都可以在一定的时间内（令牌持有时间）获得发送数据的权利，并不是无限制地持有令牌。
问题：
1.令牌开销 2.等待延迟 3.单点故障
应用于令牌环网（物理星型拓扑，逻辑环形拓扑）。
采用令牌传送方式的网络常用于负载较重、通信量较大的网络中。
习题:
选择
1.将物理信道的总频带宽分割成若干子信道，每个子信道传输一路信号，这种信道复用技术是（B)。
A.码分复用
B.频分复用
C.时分复用
D.空分复用
2.TDM所用传输介质的性质是(D)。
A.介质的带宽大于结合信号的位速率
B.介质的带宽小于单个信号的带宽
C.介质的位速率小于最小信号的带宽
D.介质的位速率大于单个信号的位速率
3.从表面上看，FDM比TDM能更好地利用信道的传输能力，但现在计算机网络更多地使用TDM而非FDM,其原因是().
A.FDM实际能力更差
B.TDM可用于数字传输而FDM不行
C.FDM技术不成热
D.TDM能更充分地利用带宽
4.在下列多路复用技术中，（B)具有动态分配时隙的功能。
A.同步时分多路复用
B.统计时分多路复用
C.频分多路复用
D.码分多路复用
5.在下列协议中，不会发生碰撞的是（A)。
A.TDM
B.ALOHA
C.CSMA
D.CSMA/CD
6.【2013统考真题】下列介质访问控制方法中，可能发生冲突的是(B)。
A.CDMA
B.CSMA
C.TDMA
D.FDMA
7.以下几种CSMA协议中，(C)协议在监听到介质空闲时仍可能不发送。
A.1-坚持CSMA B.非坚持CSMA C.p-坚持CSMA D.以上都不是
8.在CSMA的非坚持协议中，当媒体忙时，则(C)直到媒体空闲。
A.延迟一个固定的时间单位再侦听
B.继续侦听
C.延迟一个随机的时间单位再侦听
D.放弃侦听
9.在CSMA的非坚持协议中，当站点侦听到总线媒体空闲时，它(B).
A.以概率p传送
B.马上传送
C.以概率1-p传送
D.以概率p延迟一个时间单位后传送
10.在CSMA/CD协议的定义中，“争议期”指的是（A)。
A,信号在最远两个端，点之间往返传输的时间
B.信号从线路一端传输到另一端的时间
C.从发送开始到收到应答的时间
D.从发送完毕到收到应答的时间
11.以太网中，当数据传输速率提高时，帧的发送时间会相应地缩短，这样可能会影响到冲突的检测。为了能有效地检测冲突，可以使用的解决方策有（B)。
A.减少电缆介质的长度或减少最短帧长
B.减少电筑介质的长度或增加最短帧长
C.增加电缆介质的长度或减少最短帧长
D.增加电缆介质的长度或增加最短帧长
12.【2009统考真题】在一个采用CSMA/CD协议的网络中，传输介质是一根完整的电缆，传输速率为1Gb/s,电缆中的信号传播速率是200000k/s.若最小数据帧长度减少800比特，则最远的两个站点之间的距离至少需要（D)
A.增加160m
B.增加80m
C.减少160m
D.减少80m
13.长度为10km、数据传输速率为10Mb/s的CSMA/CD以太网，信号传播速率为200m/μs。那么该网络的最小帧长为(D)。
A.20bit
B.200bit
C.100bit
D.1000bit
15.以太网中若发生介质访问冲突，则按照二进制指数回退算法决定下一次重发的时间。使用二进制回退算法的理由是(C)。
A.这种算法简单
B.这种算法执行速度快
C.这种算法考虑了网络负载对冲突的影响
D.这种算法与网络的规模大小无关
16.以太网中采用二进制指数回退算法处理冲突问题。下列数据帧重传时再次发生冲突的概率最低的是（D).
A.首次重传的帧
B.发生两次冲突的帧
C.发生三次重传的帧
D.发生四次重传的帧
17.在以太网的二进制回退算法中，在11次碰撞之后，站点会在0~(C)之间选择一个随机数。
A.255
B.511
C.1023
D.2047
18.【2011统考真题】下列选项中，对正确接收到的数据帧进行确认的MAC协议是(D).
A.CSMA
B.CDMA
C.CSMA/CD
D.CSMA/CA
19.与CSMA/CD网络相比，令牌环网更适合的环境是（B).
A.负载轻
B.负载重
C.距离远
D.距离近
20.根据CSMA/CD协议的工作原理，需要提高最短帧长度的是(B).
A.网络传输速率不变，冲突域的最大距离变短
B.冲突域的最大距离不变，网络传输速率提高
C.上层协议使用TCP的概率增加
D.在冲突域不变的情况下减少线路中的中继器数量
21.多路复用器的主要功能是(D).
A.执行模/数转换
B.执行串行/并行转换
C.减少主机的通信处理负荷
D.结合来自两条或更多条线路的传输
22.下列关于令牌环网络的描述中，错误的是（A)。
A.令牌环网络存在冲突
B.同一时刻，环上只有一个数据在传输
C.网上所有结点共车网络带宽
D.数据从一个结点到另一结点的时间可以计算
23.一条广播信道上接有3个站点A、B、C,介质访问控制采用信道划分方法，信道的划分采用码分复用技术，A、B要向C发送数据，设A的码序列为+1，-1，-1，+1，+1，+1，+1，-1.站B可以选用的码片序列为（D).
A.-1,-1,-1,+1,-1,.+1,+1,+1
B.-1,+1,-1,-1-1,+1,+1,+1
C.-1+1,-1,+1,-1,+1,-1,+1
D.-1,+1,-1,+1,-1,+1,+1+1
24.【2014统考真题】站点A、B、C通过CDMA共享链路，A、B、C的码片序列分别是(1,1,1,1)、(1,-1,1,-1)和(1,1，-1，-1).若C从链路上收到的序列是(2,0,2,0,0，-2,0，-2,0，2,0,2),则C收到A发送的数据是（B).
A.000
B.101
C.110
D.111
25.【2015统考真题】下列关于CSMA/CD协议的叙述中，错误的是（B).
A,边发送数据顿，边检测是否发生冲突
B.适用于无线网络，以实现无线链路共享
C.需要根据网络跨距和数据传输速率限定最小帧长
D.当信号传播延迟趋近0时，信道利用率趋近100%
26.【2018统考真题】IEEE802.11无线局域网的MAC协议CSMA/CA进行信道预约的方法是（D)。
A,发送确认帧
B.采用二进制指数退避
C.使用多个MAC地址
D.交换RTS与CTS帧
27.【2019统考真题】假设一个采用CSMA/CD协议的100Mb/s局域网，最小帧长是128B,则在一个冲突域内两个站点之间的单向传播延时最多是(B)。
A.2.56μs
B.5.12μs
C.10.24μs
D.20.48μs
简答
1.以太网使用的CSMA/CD协议是以争用方式接入共享信道的。与传统的时分复用(TDM)相比，其优缺，点如何？
2.长度为1km、数据传输速率为10Mb/s的CSMA/CD以太网，信号在电缆中的传播速率为200000k/s,试求能够使该网络正常运行的最小帧长.
3.10000个航空订票站在竞争使用单个时隙ALOHA通道，各站平均每小时做18次请求，一个时隙是125s。总通信负载约为多少？
4.一组N个站，点共享一个56kb/s的纯AL0HA信道，每个站点平均每100s输出一个1000bit的顿，即使前一个帧未发送完也依旧进行。问N可取的最大值是多少？
5.考虑建立一个CSMA/CD网，电缆长1km,不使用重发器，运行速率为1Gb/s,电缆中的信号速率是200000am/s,最小帧长度是多少？
6.若构造一个CSMA/CD总线网，速率为100Mb/s,信号在电缆中的传播速率为2×10km/s,数据帧的最小长度为125字节。试求总线电缆的最大长度（假设总线电缆中无中继器）。
7.在一个采用CSMA/CD协议的网络中，传输介质是一根完整的电筑，传输速率为1Gb/s.电缆中信号的传播速率是200000k/s。若最小数据帧长度减少800bit,则最远的两个站点之间的距离应至少变化多少才能保证网络正常工作？
8.【2010统考真题】某局域网采用CSMA/CD协议实现介质访问控制，数据传输速率为10Mb/s,主机甲和主机乙之间的距离是2km,信号传播速率是200000m/s。请回答下列问题，要求说明理由或写出计算过程。
1)若主机甲和主机乙发送数据时发生冲突，则从开始发送数据的时刻起，到两台主机均检测到冲突为止，最短需要经过多长时间？最长需要经过多长时间（假设主机甲和主机乙在发送数据的过程中，其他主机不发送数据)？
2)若网络不存在任何冲突与差错，主机甲总是以标准的最长以太网数据帧（1518字节)向主机乙发送数据，主机乙每成功收到一个数据帧后立即向主机甲发送一个64字节的确认帧，主机甲收到确认帧后方可发送下一个数据帧。此时主机甲的有效数据传输速率是多少（不考虑以太网的前导码）？
在物理信道的可用带宽超过单个原始信号所需带宽的情况下，可将该物理信道的总带宽分割成若干与传输单个信号带宽相同（或略宽）的子信道，每个子信道传输一种信号，这就是频分多路复用。
时分复用TDM共享带宽，但分时利用信道。将时间划分成一段段等长的时分复用帧(TDM帧)，参与带宽共享的每个时分复用的用户在每个TDM帧中占用固定序号的时隙。显然，在这种情况下，介质的位速率大于单个信号的位速率。
TDM与FDM相比，抗干扰能力强，可以逐级再生整形，避免干扰的积累，而且数字信号比较容易实现自动转换，所以根据FDM和TDM的工作原理，FDM适合于传输模拟信号，TDM适合于传输数字信号。
时分多路复用(TDM)可分为同步时分多路复用和异步时分多路复用（又称统计时分复用）。同步时分多路复用是一种静态时分复用技术，它预先分配时间片（即时隙)，而异步时分多路复用则是一种动态时分复用技术，它动态地分配时间片（时隙）。
TDM属于静态划分信道的方式，各结点分时使用信道，不会发生碰撞，而ALOHA、CSMA和CSMA/CD都属于动态的随机访问协议，都采用检测碰撞的策略来应对碰撞，因此都可能会发生碰撞。
选项A、C·和D都是信道划分协议，信道划分协议是静态划分信道的方法，肯定不会发生冲突。CSMA的全称是载波侦听多路访问协议，其原理是站点在发送数据前先侦听信道，发现信道空闲后再发送，但在发送过程中有可能会发生冲突。
p-坚持CSMA协议是1-坚持CSMA协议和非坚持CSMA协议的折中。p-坚持CSMA在检测到信道空闲后，以概率p发送数据，以概率1-p推迟到下一个时隙，目的是降低1-坚持CSMA中多个结点检测到信道空闲后同时发送数据的冲突概率；采用坚持“侦听”的目的，是试图克服非坚持CSMA中由于随机等待造成延迟时间较长的缺点。
非坚持CSMA:站点在发送数据前先监听信道，若信道忙则放弃监听，则等待一个随机时间后再监听，若信道空闲则发送数据。
非坚持CSMA:站点在发送数据前先监听信道，若信道忙则放弃监听，等待一个随机时间后再监听，若信道空闲则发送数据。
CSMA/CD协议中定义的冲突检测时间（即争议期）是指，信号在最远两个端点之间往返传输的时间。
最短帧长等于争用期时间内发出的比特数。因此当传输速率提高时，可减少电缆介质的长度(使争用期时间减少，即以太网端到端的时延减小)，或增加最短帧长。
若最短帧长减少，而数据传输速率不变，则需要使冲突域的最大距离变短来实现碰撞窗口的减少。碰撞窗口是指网络中收发结点间的往返时延，因此假设需要减少的最小距离为S,则可得到如下公式（注意单位的转换)：减少的往返时延=减少的发送时延，即2×(s/(2×10^8))=800/(1×10^9)。即由于帧长减少而缩短的发送时延，应等于由于距离减少而缩短的传播时延的2倍。
可得s=80,即最远的两个站点之间的距离最少需要减少80m。
注意：CSMA/CD的碰撞窗口=2倍传播时延，报文发送时间>>碰撞窗口，
来回路程=10000×2m,往返时间RTT=10000×2/(200×10^6)=10^-4,最小帧长度=WRTT=1000bit。
B
因为要解决“理论上可以相距的最远距离”，那么最远肯定要保证能检测到碰撞，而以太网规定最短帧长为64B,其中Hub.为100Base-T集线器，可知线路的传输速率为100Mb/s,则单程传输时延为64B/(100Mb/s)/2=2.56μs,又Hub在产生比特流的过程中会导致时延1.535s,则单程的传播时延为2.56-1.535=1.025μs,从而H3与H4之间理论上可以相距的最远距离为200m/s×1.025μs=205m。
以太网采用CSMA/CD技术，网络上的流量越多、负载越大时，发生冲突的概率也会越大。当工作站发送的数据帧因冲突而传输失败时，会采用二进制回退算法后退一段时间再重新发送数
据帧。二进制回退算法可以动态地适应发送站点的数量，后退延时的取值范围与重发次数形成二进制指数关系。网络负载小时，后退延时的取值范围也小：负载大时，后退延时的取值范围也随着增大。二进制回退算法的优点是，把后退延时的平均取值与负载的大小联系了起来。所以二进制回退算法考虑了负载对冲突的影响。
根据IEEE8023标准的规定，以太网采用二进制指数后退算法处理冲突问题。在由于检测到冲突而停止发送后，一个站必须等待一个随机时间段，才能重新尝试发送。这一随机等待时间的
目的是为了减少再次发生冲突的可能性。等待的时间长度按下列步骤计算：
1)取均匀分布在0至2^min(k,10) -1之间的一个随机整数r,k是冲突发生的次数。
2)发送站等待r×2t长度的时间后才能尝试重新发送，其中1为以太网的端到端延迟。
从这个计算步骤可以看出，k值越大，帧重传时再次发生冲突的概率越低。
一般来说，在第i(i<10)次碰撞后，站点会在0到2^i -1中之间随机选择一个数M,然后等待M倍的争用期再发送数据。在达到10次冲突后，随机数的区间固定在最大值1023上，以后不再增加。如果连续超过16次冲突，那么丢弃。
CSMA/CA是无线局域网标准802.11中的协议，它在CSMA的基础上增加了冲突避免的功能。ACK帧是CSMA/CA避免冲突的机制之一，也就是说，只有当发送方收到接收方发回的ACK帧后，才确认发出的数据顿已正确到达目的地。
CSMA/CD网络各站随机发送数据，有冲突产生。负载很重时，冲突会加剧。而令牌环网各站轮流使用令牌发送数据，无论网络负载如何，都无冲突产生，这是它的突出优点。
对于选项A,网络传输速率不变，冲突域的最大距离变短，冲突信号可以更快地到达发送站点，此时可以减小最小帧的长度。对于选项B,冲突域的最大距离不变，网络传输速率提高，如果帧长度不增加，那么在帧发送完之前冲突信号可能回不到发送站点，因此必须提高最短帧长度。对于选项C,上层协议使用T℃P的概率增加与是否提高最短帧长度无关。对于选项D,在冲突域不变的情况下减少线路中的中继器数量，此时冲突信号可以更快地到达发送站点，因此可以减少最短帧长度。
多路复用器的主要功能是结合来自两条或多条线路的传输，以充分利用信道。
令牌环网络的拓扑结构为环状，有一个令牌不停地在环中流动。只有获得了令牌的主机才能发送数据，因此不存在冲突，选项A错误。其他选项都是令牌环网络的特点。
B站点选用的码片序列一定要与A站点的码片序列正交，且规格化内积为0。分别计算A,B,C,D,可知只有D选项符合要求。
把收到的序列分成每4个数字一组，即(2,0,2,0)，(0，-2,0，-2)，(0,2,0,2)，因为题目求的是A发送的数据，因此把这三组数据与A站的码片序列(1,1,1,1)做内积运算，结果分别是(2,0,2,0)·(1,1,1,1)/4=-1,(0,-2,0,-2)·(1,1,1,1)/4=1,(0,2,0,2)·(1,1,1,1)4=1,所以C接收到的A发送的数据是101，选B。
CSMA/CD适用于有线网络，CSMA/CA则广泛应用于无线周域网。其他选项关于CSMA/CD的描述都是正确的。
CSMA/CA协议进行信道预约时，主要使用的是销求发送顾(Request to Send,RIS)和清除发送帧(Clear to Send,CTS)。一台主机想要发送信息时，先向无线站点发送一个RTS帧，说明要传输的数据及相应的时间。无线站点收到RTS帧后，会广播一个CTS帧作为对此的响应，既给发送端发送许可，又指示其他主机不要在这个时间内发送数据，从而预约信道，避免碰撞。发送确认帧的目的主要是保证信息的可靠传输：二进制指数退避法是CSMA/CD中的一种冲突处理方法；C选项则和预约信道无关。
为了确保发送站在发送数据的同时能检测到可能存在的冲突，需要在发送完顺之前就能收到自己发送出去的数据，帧的传输时延至少要两倍于信号在总线中的传播时延，所以CSMA/CD总线网中的所有数据帧都必须大于一个最小帧长，这个最小帧长=总线传播时延×数据传输速率×2。已知最小帧长为128B,数据传输速率为100Mb/s=12.5MB/s,计算得单向传播延时为128B/(12.5MB/s×2)=5.12×10^-6s,即5.12μs
A
为了尽量避免碰撞，IEEE802.11规定，所有的站在完成发送后，必须再等待一段很短的时间（继续监听）才能发送下一帧。这段时间称为帧间间隔(InterFrame Space,IFS)。帧间间隔的长短取决于该站要发送的帧的类型。IEE80211使用3种FS:
DIFS（分布式协调IFS):最长的IFS,优先级最低，用于异步帧竞争访问的时延。
PIFS(点协调IFS):中等长度的FS,优先级居中，在PCF操作中使用。
SIFS(短IFS):最短的IFS,优先级最高，用于靥要立即响应的操作。
网络中的控制帧以及对所接收数据的确认帧都采用SIFS作为发送之前的等待时延。当结点要发送数据帧时，若载波监听到信道空闲，需等待DIFS后发送RTS预约信道，图中IFS1对应的是帧间间隔DIFS,时间最长，图中IFS2、IFS3、IFS4对应SIFS。
CSMA/CD是一种动态的介质随机接入共享信道方式，而TDM是一种静态的信道划分方式，所以从对信道的利用率来说， CSMA/CD用户共享信道，更灵活，信道利用率更高。
TDM不同，它为用户按时隙固定分配信道，用户没有数据传送时，信道在用户时隙就浪费了：因为CSMA/CD让用户共享信道，因此同时有多个用户需要使用信道时会发生碰撞，从而降低信道的利用率；而在TDM中，用户在分配的时隙中不会与其他用户发生冲突。对局域网来说，连入信道的是相距较近的用户，因此通常信道带宽较大。使用TDM方式时，用户在自己的时隙中没有发送的情况更多，不利于信道的充分利用。
对于计算机通信来讲，突发式的数据更不利于使用TDM方式。
对于1km长的电缆，单程传播时间为1/200000=5μs,来回路程传播时间为10μs=105s。
为了使该网络能按照CSMA/CD工作，最小的发送时间不能小于10μs。以10Mb/s速率工作时，10^-5s内可以发送的比特数为(10×10^6b/s)×10^-5s=100。因此最小帧长为100比特。
每个终端每3600/18=200s做一次请求，共有10000个终端，因此总负载是200s做10000次请求，平均每秒50次请求。每秒8000个时隙，平均每个时隙的发送次数是50/8000=1/160，即通信负载G=1/160=0.00625。
对于纯AL0HA协议，其信道利用率为0.184，因此可用带宽是0.184×56kb/s。每个站需要的带宽是1000/100=10b/s。因此，N可取的最大值是10304/10≈1030。
对于1km的电缆，单程传播时延是1200000=5×10^-6s,即5μs,往返传播时延是10μs。要能按照CSMA/CD工作，最小帧的发送时间不能小于10μs。以1Gb/s速率工作时，10μs内可以发送的比特数为(10×10^-6)/(1×10^-9)=10000，因此最小帧应是10000bit。
CSMA/CD方式要求帧的最短长度须满足条件：在发送帧的最后一位时，如果有冲突，那么发送方应能检测到冲突，即发送帧的时间至少是信号在最远两个端点之间往返传输的时间。现在的条件是帧的长度减少了800bit,即发送帧的时间减少了800b/(1Gb/s),所以信号在最远两个端点之间往返的时间必须减少800/(1Gb/s)。设减少的长度为x米，要计算往返传输的距
离，有
2x/(200000×10^3)≥800/10^9
十.局域网基本概念和体系结构
1.局域网
局域网(Local Area Network)：简称LAN,是指在某一区域内由多台计算机互联成的计算机组，使用广播信道。
1.特点
- 覆盖的地理范围较小，只在一个相对独立的局部范围内联，如一座或集中的建筑群内。
- 使用专门铺设的传输介质（双绞线、同轴电缆）进行联网，数据传输速率高(10Mb/s~10Gb/s)。
- 通信延迟时间短，误码率低，可靠性较高。
- 各站为平等关系，共享传输信道。
- 多采用分布式控制和广播式通信，能进行广播和组播。
决定局域网的主要要素为：网络拓扑，传输介质与介质访问控制方法。
2.网络拓扑
1.2.1星型拓扑
中心节点是控制中心，任意两个节点间的通信最多只需两步，传输速度快，并且网络构形简单、建网容易、便于控制和管理。但这种网络系统，网络可靠性低，网络共享能力差，有单点故障问题
1.2.2环形拓扑
系统中通信设备和线路比较节省。有单点故障问题由于环路是封闭的，所以不便于扩充，系统响应延时长，且信息传输效率相对较低。
1.2.3总线型拓扑
网络可靠性高、网络节点间响应速度快、共享资源能力强、设备投入量少、成本低、安装使用方便，当某个工作站节点出现故障时，对整个网络系统影响小。
1.2.4树型拓扑
易于拓展，易于隔离故障，也容易有单点故障。
3.局域网传输介质
4.局域网介质访问控制方法
1.CSMA/CD 常用于总线型局域网，也用于树型网络
2.令牌总线 常用于总线型局域网，也用于树型网络
它是把总线型或树型网络中的各个工作站按一定顺序如按接口地址大 小排列形成一个逻辑环。只有令牌持有者才能控制总线，才有发送信 息的权力。
3.令牌环 用于环形局域网，如令牌环网
5.局域网的分类
1.以太网 以太网是应用最为广泛的局域网，包括标准以太网(10Mbps)、快速以太网 (100Mbps)、千兆以太网(1000Mbps)和10G以太网，它们都符合IEEE802.3系列标准 规范。逻辑拓扑总线型，物理拓扑是星型或拓展星型。使用CSMA/CD
2.令环网 物理上采用了星形拓扑结构，逻辑上是环形拓扑结构。已是“明日黄花”。
3.FDDI (Flber Distributed Data Interface) 物理上采用了双环拓扑结构，逻辑上是环形拓 扑结构。
4.ATM(Asynchronous Transler Moe) 较新型的单元交换技术，使用53字节固定长度 的单元进行交换。
5.无线局网(Wireless Local Area Network;WLAN) 采用IEEE802.11标准。
6.IEEE 802标准
IEEE 802系列标准是IEEE 802LAN/MAN标准委员会制定的局域网、城域网技术标准(1980年2月成立)。其中最广泛使用的有以太网、令牌环、无线局域网等。这一系列标准中的每一个子标准都由委员会中的一个专门工作组负责。
7.MAC子层和LLC子层
IEEE 802标准所描述的局域网参考模型只对应OS参考模型的数据链路层与物理层，它将数据链路层划分为逻辑链路层LLC子层和介质访问控制MAC子层。
十一.以太网
1.概述
以太网(Ethernet)指的是由Xerox公司创建并由Xerox、Intel和DEC公司联合开发的基带总线局域网规范，是当今现有局域网采用的最通用的通信协议标准。以太网络使用CSMA/CD(载波监听多路访问及冲突检测)技术。
以太网在局域网各种技术中占统治性地位：
1.造价低廉（以太网网卡不到100块）；
2.是应用最广泛的局域网技术：
3.比令牌环网、ATM网便宜，简单；
4.满足网络速率要求：10Mb/s~10Gb/s.
以太网的两个标准
DIX Ethernet V2:第一个局域网产品（以太网)规约。
IEEE802.3:IEEE802委员会802.3工作组制定的第一个EEE的以太网标准。（帧格式有一 丢丢改动）
2.以太网提供无连接、不可靠的服务
无连接：发送方和接收方之间无“握手过程”。
不可靠：不对发送方的数据帧编号，接收方不向发送方进行确认，差错帧直接丢弃，差错纠正由高层负责。
以太网只实现无差错接收，不实现可靠传输。
3.以太网传输介质与拓扑结构的发展
4.10BASE-T以太网
10BASE-T是传送基带信号的双绞线以太网，T表示采用双绞线，现10BASE-T采用的是无屏蔽双绞线(UTP),传输速率是10Mb/s。
物理上采用星型拓扑，逻辑上总线型，每段双绞线最长为100m。
采用曼彻斯特编码。
采用CSMA/CD介质访问控制。
5.适配器与MAC地址
6.以太网MAC帧
7.高速以太网
速率≥100Mb/s的以太网称为高速以太网。
