王道计算机网络--3.1数据链路层的功能...3.4

    xiaoxiao2021-03-25  21

    1.数据链路层的功能:加强物理层传输原始比特流的功能,将物理层提供的可能出错的物理连接改造成逻辑上无差错的链路,

    ⑴为网络层提供服务:数据链路层基本任务是将源机器中来自网络层的数据传输到目标机器网络层。其为网络层提供服务有

    ①无确认的无连接服务(不需先建立链路连接,接收到帧后不需发回确认,对于丢失的帧,交给上层处理,适合实时通信或误码率低的通信信道,比如以太网)

    ②有确认的无连接服务(...,但收到帧后必须回确认,源机器在规定时间内没收到确认,重发,以提高可靠性。适合误码率较高的信道,如无线通信)

    ③有确认的面向连接服务(建立数据链路、传输帧、释放数据链路。对每一帧都进行确认,源机器收到确认后才能发送下一帧,适合通信要求高的场所)

    ⑵链路管理:数据链路层连接的建立、维持和释放过程。主要用于面向连接的服务

    进行通信前,必须首先确认对方已处于就绪状态,并交换一些必要的信息以对帧序号初始化,然后才能建立连接,传输时维持连接,结束后释放连接

    多个站点共享统一物理信道(如局域网),如何再要求通信的站点间分配和管理信道,也是此范畴内

    ⑶帧定界、帧同步、透明传输

    帧定界:讲一段数据的前后分别添加首部和尾部,就构成了帧,首尾部包含很多控制信息,其中一个重要作用是确定帧的界限,即帧定界

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

    透明传输:不管出现什么样的比特组合,都应当能再链路上传送。(解决数据中恰好出现与帧定界符相同的比特组合的问题)

    ⑷流量控制:限制发送方的数据流量,使其发送速率不致超过接收方的接收能力(通过反馈机制来实现)(并不是数据链路层特有的功能,很多高层协议也提供此功能)

    ⑸差错控制:用以使发送方确定接收方是否正确收到了由它发送的数据的方法

    位错:帧中某些位出现了差错,通常采用循环亢余检验(CRC)方式检错,通过自动重传请求(ARQ)重传出错的帧

    帧错:帧的丢失、重复、失序等错误,再数据链路层引入定时器和编号机制,可保证每一帧最终都有且仅有依次正确交付给目的站点

    2.组帧:为了在出错时只重发出错的帧,而不必全部重发,组帧主要解决帧定界、帧同步、透明传输等问题,有四种方法实现组帧

    ⑴字符计数法:在帧头部使用一个计数字段来标明帧内字符数。当目的节点的数据链路层接收到字节计数值时就值得后面跟随的字节数,从而定界(计数包括自身所占的一个字节),最大的问题是如果计数字段出错,就失去了帧边界划分依据,造成灾难性后果

    ⑵字符填充的首尾定界符法:使用一些特定的字符来定界一帧的开始(DLE STX)与结束(DLE ETX);

    为使信息位中出现的特殊字符不被误认为帧的首尾界定符,可以再特殊字符的前面填充一个转义字符(DLE),以实现透明运输

    ⑶比特填充的首尾标志法:允许数据帧包含任意个数的比特,也允许每个字符的编码包含任意个数的比特,

    通过01111110来标志界限,信息位中每遇到5个连续的1时,后插入一个0,而接受方没收到5个1,则自动删除后面紧跟的0

    容易由硬件实现,优于字符填充方法

    ⑷违规编码法:不需要任何填充技术,便能实现数据传输的透明性,但他只适用于采集亢余编码的特殊编码环境。IEEE 802

    物理层比特编码通常采用违规编码法,比如曼彻斯特编码中,1代表高-低电平对,0代表低-高电平对,而高-高电平对和低-低电平对是违规的(没有采用)。可以借用这些违规编码来定界帧的起始和终止。

    3.差错控制:差错一般都是由于噪音引起的,噪音有两大类:①信道所固有的持续存在的随机热噪音(通过信噪比减少干扰)②由于外界特定的短暂原因所造成的的冲击噪音

    利用编码技术进行差错控制,主要有两类:自动重传请求(ARQ)、前向纠错(FEC)(接收端发现差错并能确定二进制数码的错误位置,从而加以纠正)

    编码又分为检错编码和纠错编码

    ⑴检错编码:都是采用亢余编码技术,核心思想是再有效数据被发送前,先按某种关系附加上一定的康雨薇,构成一个符合某一规则的码字后再发送。

    ①奇偶校验码:奇校验码和偶校验码的统称,由n-1位信息元有1位校验元组成,若是奇校验元,附加此校验元后保证信息元1的个数为奇数个,偶校验元偶数个。

    ②循环亢余码(CRC):又称为多项式码(模2运算)

    m bit的帧或报文,发送器生成一个r bit的序列,称为帧检验序列(FCS),放于报文末端,m+r bit的信息正好被商定的多项式G(x)整除

    求FCS:①末尾加r个0(G(x)的阶为r)②模2除。得到的余数即为亢余码(共r位,0不可省略)FCS

    ⑵纠错编码:在每发送的数据块上附加足够的亢余信息,使接收方能推导出发送方实际送出的比特串。(海明码能发现双比特错,但只能纠正单比特错)

    海明码:m个信息位和r个校验位(0<m<=2^r-1-r)校验位的位置1 2 4 8...(位置从1开始排)其余位置由信息位填充

    原理:例子:P1 P2 D1 P3 D2 D3 D4 数据是1101(D1位置=1+2     D2位置=1+4         D3位置=2+4      D4位置=1+2+4)

    校验位P1 ⊕D1⊕D2⊕D4=0--->P1=1同理P2=0,P3=0传递后再求P1、P2、P3

    P1P2P3组成的数比如110就代表第6位错了,取反即可

    4.流量控制与可靠传输机制

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

    流量控制涉及对链路上帧的发送速率的控制,以使接收方有足够的缓冲空间来接受每一帧。常见的方式有两种:停止-等待协议、滑动窗口协议

    1.停止-等待控制流量基本原理:发送方每发送一帧,都要等待接收方的应答信号,之后才能发送下一帧;发送方没接收一帧,都要反馈一个应答信号,表示可接收下一帧。每次只允许发送一帧,然后就陷入等待接收确认信号的过程,因而传输效率很低。

    2.滑动窗口流量控制基本原理

    任意时刻,发送方都维持一组连续的允许发送的帧的序号,称为发送窗口;同时接收方也维持一组连续的允许接受帧的序号,称为接收窗口。发送窗口WT代表还没有收到对方确认信息的情况下发送方最多还可以发送多少个数据帧。接受窗口是为了控制可以接受那些数据帧。

    滑动窗口的重要特性:

    ①只有接收窗口向前滑动时(同时接收方发送了确认帧),发送窗口才可能(发送放收到确认帧是一定)向前滑动

    ②从滑动窗口概念看,停止-等待协议、后退N帧协议和选择重传协议只在发送窗口大小与接收窗口大小上有所差别。

    停止-等待协议:发送窗口大小=1        接收窗口大小=1

    后退N帧协议:发送窗口大小>1        接收窗口大小=1

    选择重传协议:发送窗口大小>1        接收窗口大小>1

    ③当接收窗口的大小为1时,可保证帧的有序接收

    ④数据链路层的滑动窗口协议中,窗口的大小在传输过程中是固定的

    3.可靠传输机制:通常使用确认和超时重传两种机制来完成

    确认:一种无数据的控制帧,使接收方知道那些内容被正确接收。为提高传输效率,有时将确认捎带再一个恢复帧中,称为捎带确认。

    超时重传:发送放在发送某个数据帧后就开启一个计时器,再一定时间内未收到确认帧,那么就重新发送,直至发送成功为止。

    5.自动重传请求(ARQ):通过接收方请求发送放重传出错的数据帧来恢复出错的帧,是处理信道所带来的差错的方法之一。

    传统自动重传请求分为三种,停等待ARQ、后退N帧ARQ以及选择性重传ARQ。后两种协议是活动窗口技术与请求重发技术的结合,由于窗口尺寸开到足够大时,帧在线路上可连续流动,因此又称为连续ARQ协议。数据链路层中,流量控制与可靠性传输机制是交织在一起的。

    ⑴单帧滑动窗口与停止-等待协议

    在此协议中,除了数据帧丢失,还能可能出现以下两种差错:假设发送的帧用交替的0、1表示,肯定确认用ACK0和ACK1来表示

    ①到达目的的帧被破坏,接受端简单的将帧丢弃,为解决此问题,源站装备了计时器……

    ②数据帧正确而确认帧被破坏,发送方会重发缓存中的帧,接收方收到同样的帧,丢弃,重传相应的确认帧。

    步骤:

    发送节点:①从主机取一数据帧,送交至发送缓存        ②V(S)=0//初始化        ③N(S)=V(S)//发送序号N(S)        

    ④缓存的帧发送(这个数据帧的副本扔在缓存)        ⑤设置超时计时器。        ⑥等待//⑦⑧最先出现一个

    ⑦若收到确认帧ACKn,若n=1-V(S),则从主机取一个新的帧放入发送缓存,V(S)=1-V(S),goto ③//下一个序号        否则丢弃确认帧,goto⑥

    ⑧若超时计时器时间,goto④

    接受节点:①V(R)=0//初始化        ②等待        ③收到一个数据帧,检查是否产生传输差错(比如CRC),若出错,丢弃,goto②;否则继续

    ④若N(S)==V(R),继续//收到正确帧        否则丢弃,goto⑦//收到重复帧        ⑤将收到的数据帧的数据部分送交主机       ⑥V(R)=1-V(R)//更新

    ⑦发送确认帧ACKn(n=1-V(R)),goto②(表面期望接受V(R))

    停止-等待协议通信信道的利用率很低,为客服这一缺点,就产生了另外两种协议,即后退N帧协议和选择重传协议

    ⑵多帧滑动窗口与后退N帧协议(GBN)接收窗口尺寸为1,发送窗口尺寸大于1,为减少开销,GBN协议还规定接收端不一定没收到一个正确的帧就立即回发一个确认帧,而是可以连续收到好几个确认帧后才对最后一个帧发确认信息,在接收到错误的帧的情况下,又收到错误帧后面的几个正确帧,则应丢弃,并重复发送已发送过的最后以确认帧,以防已发送的确认帧被丢弃。

    后退N帧协议因连续发送帧而提高信道利用率,但重传时又必须把原来已传送正确的数据帧进行重传,这又降低了效率。

    ⑶多帧滑动窗口与选择重传协议(SR)加大接收窗口,收下发送序号不连续但仍处于接收窗口中的数据帧,等所缺序号数据帧再一并送交主机

    计时器……,接收方怀疑帧出错时,发送一个否认帧NAK给发送方,要求发送方对NAK中指定的帧进行重发,返回正确接收的最后一个确认帧

    接收窗口WR和发送窗口尺寸WT都大于1,WT+WR<=2^n(若采用n比特对帧编号),目的是为了保证接收方向前移动窗口后,新窗口与就窗口序号没有重叠部分。

    信道利用率=(L/C)/T(L:这个周期共发送L比特数据    C:发送方的数据率    T:发送到收到第一个确认帧的时间)(数据率的利用率)

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

    习题:

    1.为了纠正2比特的错误,编码的海明距应该为()              5

    海明码纠错d位,需要码距为2d+1的编码方案,而检错d位,只需要码距为d+1,纠正t个错误的同时检测e(e>=t)个错误,只需要码距t+e+1

    2.在选择重传ARQ协议中,设编号用3bit,再设WT=6,WR=3,试找出一种情况,使得在此情况下,协议不嫩公证处工作。

    发送方:0123456701234567       假设发送方发送0~5后,接收方收到0~5,并发送确认帧,希望接收6、7、0但是确认帧丢失,此时发送方发送的0

    接收方:0123456701234567       无法判断是新的还是旧的帧。

    转载请注明原文地址: https://ju.6miu.com/read-50329.html

    最新回复(0)