计算机网络习题——第3章 数据链路层
时间：2023-06-15 13:07:00
3-01数据链路(即逻辑链路)和链路(即物理链路)有什么区别？电路连接和数据链接连接有什么区别？
数据链路和链路的区别在于，除了链路，数据链路还必须有一些必要的程序来控制数据传输。因此，实现通信程序所需的硬件和软件比链路多。
电路连接意味着链路两端的结点交换机已经启动，物理连接可以传输比特流。但数据传输并不可靠。在物理连接的基础上，建立数据链接是数据链接连接。此后，由于数据链接具有检测、确认和重传功能，不可靠的物理链路变成可靠的数据链路进行可靠的数据传输。当数据链路断开连接时，物理电路连接不一定断开连接。
3-06PPP协议的主要特点是什么？为什么？PPP不使用帧的编号？PPP适用于什么情况？为什么？PPP协议不能使数据链路层可靠传输？
主要特点有:(1) 点对点协议支持异步链路和同步链路；(2) PPP面向字节。
PPP由于以下考虑，不使用序号和确认机制：
第一， 可靠传输的数据链路层协议(如HDLC），费用会增加。当数据链路层出现错误的概率较小时，使用相对简单PPP协议比较合理。
第二， 在因特网环境下，PPP放入信息字段的数据是IP数据报告。假设我们采用了可靠传输但非常复杂的数据链路层协议，但当数据帧从路由器中的数据链路层上升到网络层时，由于网络拥塞，它仍然可能被丢弃。因此，数据链路层的可靠传输并不能保证网络层的可靠传输。
第三， PPP帧格式中有帧检查序列FCS安段。每个收到的帧，PPP使用硬件CRC检验。若发现有差错，则丢弃该帧（一定不能把有差错的帧交付给上一层）。端到端的差错检测最后由高层协议负责。因此，PPP协议可以保证无误接受。
PPP本协议适用于用户使用拨号电话线接入因特网线路，质量不太差。
3-07发送的数据为1101011011。CRC多项式的生成是P(X)=X4 X 1.试图在数据后面添加余数。
在传输过程中，数据的最后一个1变为0，问接收器是否能找到它？
如果数据在传输过程中最后两个1变为0，请问接收器是否能找到它？
采用CRC检查后，数据链路层的传输是否可靠？
多项式是根据数据生成的M(X)=X9 X8 X6 X4 X3 X1 X0=1101011011，因为G(X)=X4 X 1=10011，所以K=4，把M(X)左移K位，得到M’(X)，M’(X)=M(X)*XK=M(X)*X4=X13 X12 X10 X8 X7 X5 X4=11010110110000 ，用M’(X)模二除G(X)，余数为CRC位，M’(X)/G(X)= 11010110110000/10011，R(X)=1110。
在传输过程中，数据的最后一个1变为0，110110101110除10011外，余数为011，不为0，接收端可发现错误。
在数据传输过程中，最后两个1成了0，1101011万1110除10011外，余数为101，不为0，接收端可发现错误。
采用crc检查后，收方将丢失数据，因此只使用crc检验而没有ppp重传机制，数据链路层的传输不可靠。
3-08发送的数据为101110。CRC多项式的生成是P(X)=X3 1.试图在数据后面添加余数。
已知除数为1001，被除数为1011000，余数为011。
3-09一个PPP帧的数据部分(16进制)为7D 5E FE 27 7D 5D 7D 5D 65 7D 5E。真实数据是什么(用十六进制写)？
由于PPP字节填充法规定：0x7E转换为（0x7D，0x5E），0x7D转换为（0x7D，0x5D），即7E→7D 5E，7D→7D 5D，分为数据部分7D 5E FE 27 7D 5D 7D 5D 65 7D 5E，所以真正的16进制数据是7E FE 27 7D 7D 65 7E。
3-10PPP协议采用同步传输技术传输比特串01111100。零比特填充后变成什么样的比特串？如果接收器收到PPP帧的数据部分是000110111111101110110，删除发送端添加的零比特后会变成什么样的比特串？
零比特填充:只要发现5个连续1，立即填充0
原比特串：011011111 11111零比特填充后：0110111110 11111000
0001110111110 111110 110=>000111011111 11111110
3-14常用的局域网网络拓扑有哪些类型？现在最流行的结构是什么？为什么以太网早期选择总线拓扑结构而不是星形拓扑结构，但现在改为星形拓扑结构？
常用的局域网网络拓扑有星形网、总线网、环形网、树形网四种。
当时，非常可靠的星形拓扑结构更昂贵，人们认为无源总线结构更可靠，但实践证明，连接大量网站的总线以太网容易出现故障，现在是特殊的ASIC芯片的使用可以使星形结构的集线器或交换机非常可靠，因此星形结构的拓扑通常用于以太网。
3-19使用以太网 CSMA/CD协议是以争用方式接入到共享信道的。这与传统的时分复用TDM相比优缺点呢？
传统时间复用TDM是静态固定间隙分配，信道利用率高，负荷低或负荷不均匀，CSMA/CD新的空闲资源可以动态使用，低负荷时信道利用率高，但控制复杂，高负荷时信道冲突大。
对于局域网，相距较近的用户连接到信道，因此通常信道带宽较宽，如果使用TDM如果用户在自己的间隙中没有发送更多的数据，这将不利于信道的充分利用。对于计算机通信，突发数据不利于使用TDM方式。
3-20假定1km长的 CSMA/CD网络数据率为1 Gbit/s。在网络上设置信号的传输速率为2万km/s。使用本协议的最短帧长。
电磁波在1km电缆的传播时间约为5微秒，来回路程的传播时间为10微秒。为了能够遵循它CSMA/CD工作，最小帧的发射时间不能小于10微秒；以1Gb/s10微秒可以发送的比特数为:10×10-6×109=因此，最短帧为10000或1250字节长。
3-22假定在使用 CSMA/CD协议的10Mbit/s以太网中的一个站在发送数据时检测到碰撞，在执行退出算法时选择随机数r=100。这个站要等多久才能再次发送数据？如果是100 Mbit/s以太网呢？
对于10Mbit/s以太网将争用期定为51.2μs，等待时间为51.2μs×100=5.12ms。对于100Mbit/s以太网，以太网将争用期定为5.12μs，争用期为100个，等待时间为5个.12μs×100=512μs。
3-24假设站点A和B在同一个10Mbit/s以太网段。这两个站点之间的传播时延为225比特时间。假设A开始发送一帧，B也在A发送结束前发送一帧。如果A发送以太网允许的最短帧，A能在检测到与B碰撞之前发送自己的数据吗？换句话说，如果A在发送前没有检测到碰撞，A发送的帧能否与B发送的帧不碰撞？(提示:计算时应考虑每个以太网帧发送到信道时，MAC在帧前添加几个字节的前同步码和帧定界符。）
设在t=0点A开始发送，在t=(64 8)*8=576比特时间，A应发送完毕。t=225比特时间，B检测A的信号。只要B在t=在224比特时间前发送数据，A发送前必须检测到碰撞，以确保以后不会发送碰撞。如果A在发送前没有检测到碰撞，那么A发送的帧肯定不会与B发送的帧碰撞（当然不会与其他站点碰撞）。
3-25站点A和B在t=数据帧同时发送。t=225比特时间，A与B同时发现碰撞，并在t=225 48=干扰信号的传输在273比特时间完成。A和B在 CSMA/CD在算法中选择不同的r值退出。假设A和B选择的随机数分别是 r A r_A rA=0和 r B r_B rB=1。试问A和B各在什么时间开始重传其数据帧？A重传的数据帧在什么时间到达B？A重传的数据会不会和B重传的数据再次发送碰撞？B会不会在预定的重传时间停止发送数据？
因为 r A r_A rA=0，则A在干扰信号传输完之后立即开始侦听t=273+225（传播时延）=498比特时间，A检测到信道开始空闲t=498+96（帧间最小间隔）=594比特时间，A开始重传数据。
t=594+225（传播时延）=819比特时间，A重传完毕，A重传的数据帧到达B的时间。
因为 r B r_B rB=1，则B在干扰信号传输完之后1倍的争用期，即512比特时间才开始侦听t=273+512=785比特时间，B开始侦听。若侦听空闲，则t=785+96（帧间最小间隔）=881比特时间，B开始重传数据，若侦听非空闲，则继续退避算法，又因为t=819比特时间的时候，A才重传数据完毕，所以B在785比特时间侦听的时候，肯定会侦听信道非空闲，即B在预定的881比特时间之前侦听到信道忙，所以B在预定的881比特时间是停止发送数据的。即A重传的数据不会和B重传的数据再次发生碰撞。
3-26以太网上只有两个站，它们同时发送数据，产生了碰撞。于是按截断二进制指数退避算法进行重传。重传次数记为i，i=1，2，3，…试计算第1次重传失败的概率、第2次重传失败的概率、第3次重传失败的概率，以及一个站成功发送数据之前的平均重传次数I。
第i次重传分布在[0，1，…，2i-1]共2个时间槽内，因此，i次重传碰撞的概率为 p i = 2 − i ， i = m i n [ i ， 10 ] p_i=2^{-i}，i=min[i，10] pi=2−i，i=min[i，10]。
第一次重传碰撞的概率为 P 1 = 2 − 1 = 0.5 P_1=2^{-1}=0.5 P1=2−1=0.5，第2次重传失败的概率为 P 2 = 2 − 2 = 0.25 P_2=2^{-2}=0.25 P2=2−2=0.25，第3次重传失败的概率为 P 3 = 2 − 3 = 0.125 P_3=2^{-3}=0.125 P3=2−3=0.125。
开始k-1次失败，紧接着第k次重传成功的概率为 P k = ( 1 − 2 − k ) ∏ i = 1 k − 1 2 − i P_k=(1-2^{-k} ) ∏_{i=1}^{k-1}2^{-i} Pk=(1−2−k)∏i=1k−12−i ，进一步化简可得： P k = ( 1 − 2 − k ) [ 2 − 1 ∗ 2 − 2 ∗ ⋯ 2 − ( k − 1 ) ] = ( 1 − 2 − k ) 2 − k ( k − 1 ) / 2 P_k=(1-2^{-k} )[2^{-1}*2^{-2}*⋯2^{-(k-1) } ]=(1-2^{-k})2^{-k(k-1)/2} Pk=(1−2−k)[2−1∗2−2∗⋯2−(k−1)]=(1−2−k)2−k(k−1)/2（平均重传k次的概率）
平均重传次数 l = ∑ k = 1 ∞ k p k = ∑ k = 1 ∞ k ( 1 − 2 − k ) 2 − k ( k − 1 ) / 2 = 1 / 2 + 3 / 4 + 21 / 64 + 15 / 256 + ⋯ ≈ 1.64 l=∑_{k=1}^∞kp_k =∑_{k=1}^∞k(1-2^{-k})2^{-k(k-1)/2} =1/2+3/4+21/64+15/256+⋯≈1.64 l=∑k=1∞kpk=∑k=1∞k(1−2−k)2−k(k−1)/2=1/2+3/4+21/64+15/256+⋯≈1.64
3-34有两台主机A和B接在800m长的电缆线的两端，并在t=0时各自向对方发送一个帧，长度为1500bit（包括首部和前同步码）。假定在A和B之间有4个转发器，在转发帧时会产生20比特的时延。设传输速率为100 Mbit/s，而 CSMA/CD的退避时间是随机数r倍的争用期，争用期为512bit，在发生第一次碰撞后，在退避时A选择r=0而B选择r=1。忽略发生碰撞后的人为干扰信号和帧间最小间隔。
（1）设信号的传播速率是2×108m/s。试计算从A到B（包括4个转发器）的传播时延。
（2）在什么时间（以秒为单位）B完全收到了A发送的帧？
（3）现在假定只有A发送帧，帧长仍为1500bit，但4个转发器都用交换机来代替。交换机在进行存储转发时还要产生额外的20bit的处理时延。在什么时间（以秒为单位）B完全收到了A发送的帧？
（1） 整个传输链路被4个交换机分成5个网段。在主机和交换机之间或两个交换机之间的传播时延是：每一段电缆长度160m除以电磁波的传播速率2×108m/s，即(160m/2×108m/s)=0.8µs，总的传播时延是5×0.8=4µs。4个交换机的处理时延是4×0.2=0.8µs。所以从A到B（包括4个转发器）的传播时延4µs+0.8µs=4.8µs
（2）发送1帧需要的时间是1500/(100×106bit/s)=15µs，比从A到B传播一个比特所需的时间还要多。
在t=0时，A和B同时发送帧。
在t=4.8µs时，A和B都检测出碰撞。
在t=9.6µs时，B终止发送的帧的最后一个比特到达A，A立即重传。
在t=14.4µs时，A重传帧的第一个比特到达Ｂ。
Ａ发送1500bit所需要的时间是1500/108=15µs。
在t=29.4µs=29.4×10-6s时，A重传帧的最后一个比特到达B。
（3） 主机A和4个交换机的发送时延一共是5×15=75µs。由（1）可知，从A到B的传播时延为4.8µs，因此，B收完A所发送的帧总共经历的时延=4.8+75=79.8µs=79.8×10-6s。
