计算机网络课程的一些问题记录

一般来说,纠错码用于什么场合?检错码用于什么场合?请举例说明。

纠错码

计算机电信信息理论编码理论中,纠错码(ECCerror correction/correcting code)是信息传输中错误检测与纠正的工具。它通常用在不可靠或嘈杂的信道中(比如说无线链路)。数据发送方利用纠错码中的冗余信息,使得接收方能够检测消息传输中发生的错误,而且通常可以纠正这些错误而无需重新传输。

纠错码的分类

纠错码分为两大类:分组码(例如海明码,里德所罗门码和低密度奇偶校验码)和卷积码

分组码适用于一连串固定长度的数据包.

卷积码适用于任意长度的比特流/符号流.

纠错码的应用场合

相比错误检测,纠错码不仅能够检测到错误,而且可以将其更正。它的优点是在出现错误时不需要反向信道来请求重发数据,缺点是消息中增加了固定开销,因此需要更高的前向信道带宽。因此,纠错码可用于重传成本高昂或无法实现的情况,例如单向通信链路,时延较长的链接,以及以多播方式发送给多个接收者的链接。比如,绕天王星运行的卫星,由于传输错误而造成的重发会造成5个小时的延迟。纠错码信息通常添加到大容量存储设备中,以恢复损坏的数据,并广泛用于调制解调器,以及主存储器为 ECC 内存(在ECC技术出现之前,带有奇偶校验的内存的主要功能仅仅是“发现错误”,并不能纠正错误。在内存中ECC能够容许错误,并可以将错误自动更正,错误纠正存储器的控制器通常使用汉明码,使系统得以正常的操作,不致因错误而中断)的系统中。

接收机中的纠错码处理可以应用于数字比特流,也可以应用于数字调制载波的解调。对于后者,纠错码是接收器中模拟数字转换器的组成部分。维特比(Viterbi)解码器采用软判决算法,以从被噪声破坏的模拟信号中解调数字数据。许多纠错码编码器/解码器还可以生成比特误码率(BER)信号,该信号可用作反馈以微调模拟接收电子设备。(这段我也不懂)

检错码

检错码的分类

  • 重复编码

重复编码是在信道上重复比特信息以实现无差错通信的编码方案。首先将要发送的数据流划分为比特块,然后将每个传输预定的次数。例如,要发送比特“1011”,四比特块{{what}}则再重复三次而产生“1011 1011 1011”。但是,如果此例中收到12位信息为“1010 1011 1011”,其中第一个块不同于其他两个,则可以确定已经发生错误。

重复编码非常低效,并且如果错误在每个组的完全相同的地方发生,则很容易出现问题(例如上例中正巧错误为“1010 1010 1010”,将被检测为传输无误)。重复编码的优点是它非常简单,并实际上用于某些数字电台的传输。

  • 奇偶校验位

奇偶校验位(parity bit)是一种非常简单的方案,可以用于检测任何奇数个错误的发生。它不能进行错误校正。发生错误时必须扔掉全部的数据,然后从头开始传输数据。但如果发生的错误数量为偶数,则奇偶效验位看上去是正确的。

对奇偶效验位的扩展和改变有纵向冗余校验垂直冗余检查,以及双或对角奇偶(在RAID-DP中使用)。

  • 校验和

消息的校验和是固定字长(例如字节值)的字节码的模算数和。和可能在传输前用反码以检测全零消息出现的错误。

校验和方案包括奇偶校验位校验码纵向冗余校验。部分校验和方案如Damm算法Luhn算法Verhoeff算法在设计上是专门用于检测人类书写或记录数字时常出现的错误。

  • 循环冗余校验(CRC)

循环冗余校验(CRC)是一个非安全的散列函数,旨在检测计算机网络中数字数据的意外变化。因此,它不适合检测恶意引入的错误。

循环码有着非常适合检测突发错误的有利特性。CRC尤其容易在硬件中实现,并且因此常用在数字网络和诸如硬盘等存储设备中。

奇偶校验是循环冗余校验的特殊案例,其中单比特CRC由除数x + 1生成。

检错码的应用场合

光纤或高品质的铜线错误率较之无线链路低得多,因此对于偶尔出现的错误采用差错检测和重传的方式更有效.

错误检测和纠正码经常被用于提供数据存储介质的可靠性。

维基百科-纠错码:https://zh.wikipedia.org/wiki/%E7%BA%A0%E9%94%99%E7%A0%81

维基百科-错误检测与纠正:https://zh.wikipedia.org/wiki/%E9%94%99%E8%AF%AF%E6%A3%80%E6%B5%8B%E4%B8%8E%E7%BA%A0%E6%AD%A3

根据实例说明校验和是如何实现的?它真的有用吗?为什么?

校验和(英语:Checksum)是冗余校验的一种形式。 它是通过错误检测方法,对经过空间(如通信)或时间(如计算机存储)所传送数据的完整性进行检查的一种简单方法。

计算机领域常见的校验和的方法有循环冗余校验(CRC)、MD5SHA家族等。

产生检验和的实际过程一般是向核对函数或检验和算法输入给定的数据,一个良好的检验和算法通常会对进行很小的修改的输入数据都会输出一个显著不同的值。

以上来自维基百科-校验和:https://zh.wikipedia.org/wiki/%E6%A0%A1%E9%AA%8C%E5%92%8C.

在教材计算机网络第五版中,写的是:

校验和通常放置在消息的末尾,作为求和功能的补充。这样一来,通过对整个接收到的码字(包含了数据位和校验和)进行求和计算就能检测出错误。如果计算结果是零,则没有检测出错误。

这里其实有点疑问,具体说一下我的理解,上完课后再做一个修改补充.

MD5校验原理举例:
如客户往我们数据中心同步一个文件,该文件使用MD5校验,那么客户在发送文件的同时会再发一个存有校验码的文件,我们拿到该文件后做MD5运算,得到的计算结果与客户发送的校验码相比较,如果一致则认为客户发送的文件没有出错,否则认为文件出错需要重新发送。

就比如我的A1P自助注册的网站,我的密码已经被我md5加密放在了后台,我在登陆的时候,输入密码,密码做md5运算后与我存在后台的校验码比较,如果一直则说明输入的密码正确.

举一反三,如果要发送一串数据,或者一个文件,发送的时候再发送一个存有校验码的文件,我们对接受的文件做md5运算,结果与校验码作比较,一致的话则没有出错.

举例说明CRC的检错原理。

循环冗余校验(英语:Cyclic redundancy check,通称“CRC”)是一种根据网络数据包或电脑文件等数据产生简短固定位数校验码的一种散列函数,主要用来检测或校验数据传输或者保存后可能出现的错误。生成的数字在传输或者存储之前计算出来并且附加到数据后面,然后接收方进行检验确定数据是否发生变化。由于本函数易于用二进制的电脑硬件使用、容易进行数学分析并且尤其善于检测传输通道干扰引起的错误,因此获得广泛应用。此方法是由W. Wesley Peterson于1961年发表

相比于奇偶校验码(PCC)只能校验一位错误,循环冗余校验码(CRC)的检错能力更强,可以检测出多处错误。

根本思想就是先在要发送的帧后面附加一个数(这个就是用来校验的校验码,但要注意,这里的数也是二进制序列的,下同),生成一个新帧发送给接收端。当然,这个附加的数不是随意的,它要使所生成的新帧能与发送端和接收端共同选定的某个特定数整除(注意,这里不是直接采用二进制除法,而是采用一种称之为“模2除法”)。到达接收端后,再把接收到的新帧除以(同样采用“模2除法”)这个选定的除数。因为在发送端发送数据帧之前就已通过附加一个数,做了“去余”处理(也就已经能整除了),所以结果应该是没有余数。如果有余数,则表明该帧在传输过程中出现了差错。

维基百科-循环冗余校验:https://zh.wikipedia.org/wiki/%E5%BE%AA%E7%92%B0%E5%86%97%E9%A4%98%E6%A0%A1%E9%A9%97

数据链路层协议一般都是采用ARQ的方式,3.3通过递进的方式,一步步将ARQ的所有要素引入,请总结ARQ的所有要素即实现过程。

自动重传请求(Automatic Repeat-reQuest,ARQ)是OSI模型数据链路层传输层的错误纠正协议之一。它通过使用确认和超时这两个机制,在不可靠服务的基础上实现可靠的信息传输。如果发送方在发送后一段时间之内没有收到确认帧,它通常会重新发送。ARQ可能包括停止等待ARQ协议和连续ARQ协议,错误检测(Error Detection)、正面确认(Positive Acknowledgment)、超时重传(Retransmission after Timeout)和 负面确认及重传(Negative Acknowledgment and Retransmission)等机制。

停止并等待ARQ协议(stop-and-wait)

停止并等待协议的工作原理如下:

  1. 发送点对接收点发送数据包,然后等待接收点回复ACK并且开始计时。
  2. 在等待过程中,发送点停止发送新的数据包。
  3. 当数据包没有成功被接收点接收时候,接收点不会发送ACK.这样发送点在等待一定时间后,重新发送数据包。
  4. 反复以上步骤直到收到从接收点发送的ACK.

连续ARQ协议(Continuous ARQ)

为了克服停止并等待ARQ协议长时间等待ACK的缺点。这个协议会连续发送一组数据包,然后再等待这些数据包的ACK.

回退N重传(Go-Back-N)

接收点丢弃从第一个没有收到的数据包开始的所有数据包。
发送点收到NACK后,从NACK中指明的数据包开始重新发送。


选择重传(Selective Repeat)

发送点连续发送数据包但对每个数据包都设有个一个计时器。
当在一定时间内没有收到某个数据包的ACK时,发送点只重新发送那个没有ACK的数据包。


ARQ协议对错误纠正的方法是:

丢弃已经接收的含有错误的数据包。
向发送点请求重新发送数据包。

维基百科-自动重传请求:https://zh.wikipedia.org/wiki/%E8%87%AA%E5%8A%A8%E9%87%8D%E4%BC%A0%E8%AF%B7%E6%B1%82

在3.3.3的协议中,引入了“帧序号”是为了解决什么问题?这些“序号”是如何设置的?

对于接收方来说,它需要有一种办法能够区分到达的帧是第一次发来的新帧,还是被重传的老帧。为了做到这一点,很显然的做法是让发送方在它所发送的每个帧的头部放上一个序号。然后,接收方可以检查它所接收到的每个帧的序号,由此判断这是个新帧还是应该被丢弃的重复帧。

因为协议必须正确,并且出于链路效率的考虑,包含在帧头中的序号字段应当很小。

不过序号需要的位数取决于具体的链路层协议,尤其是,帧携带的序号必须足够大到保证协议能正确工作。

在这个协议中,唯一不明确的地方在于一帧和它的前一帧或者和它的后一帧之间。

因此,一位序号(0或者1)就足以解决问题。在任何一个时刻,接收方期望下一个特定的序号。当正确帧到来时,帧被传递到网络层,然后接收方期待的下一个序号模2增加1(即从0到1,从1到0)。

任何一个到达的帧,如果包含了错误序号都将作为重复帧被拒绝接收,不过最后一个有效的确认需要重复,以便发送方确认已经被接收的帧。

3.3介绍的三个协议都是单向传输数据的,即是单工通信方式,请问什么是单工通信?什么是半双工通信?什么是双工通信?它们都有哪些模式?工作场合是什么?

单工通信只支持信号在一个方向上传输(正向或反向),任何时候不能改变信号的传输方向。为保证正确传送数据信号,接收端要对接收的数据进行校验,若校验出错,则通过监控信道发送请求重发的信号。

双工通信主要分为半双工通信与全双工通信。

半双工通信允许信号在两个方向上传输,但某一时刻只允许信号在一个信道上单向传输。

全双工通信允许数据同时在两个方向上传输,即有两个信道,因此允许同时进行双向传输。

单工通信就是只能从A到B,如[广播][计算机和打印机]
半双工通信是A到B,B到A都行,但不能同时进行.如[对讲机]
全双工通信是A到B,B到A都行,可以同时进行.如[电话]

什么是捎带确认(piggybacking) ?为什么采用这种方式?采用piggybacking时需要注意什么情况?

当到达-一个数据帧时,接收方并不是立即发送一个单独的控制帧,而是抑制自己并开始等待,直到网络层传递给它下一一个要发送的数据包。然后,确认信息被附加在往外发送的数据帧上(使用帧头的ack字段)。实际上,确认信息搭了下-一个出境数据帧的便车。这种暂时延缓确认以便将确认信息搭载在下一个出境数据帧上的技术就称为捎带确认(piggybacking)。

为了捎带一个确认,数据链路层应该等待网络层传递给它的下一个数据包。数据链路层采用某种自组织方法,比如等待一个固定的毫秒数。如果一个新的数据包很快就到来,那么确认就可以立即被捎带回去。如果在这段间隔超时之前没有新的数据包到来,数据链路层必须发送一个单独的确认帧。

为什么要采用滑动窗口协议?

●所有滑动窗口协议的本质是在任何时刻发送方总是维持着一组序号,分别对应于允许它发送的帧。我们称这些帧落在发送窗口(sending window)内。类似地,接收方也维持着一个接收窗口(receiving window),对应于一组允许它接受的帧。发送方窗口内的序号代表了那些可以被发送的帧,或者那些已经被发送但还没有被确认的帧。任何时候当有新的数据包从网络层到来时,它被赋予窗口中的下一个最高序号,并且窗口的上边界前移一格。当收到一个确认时,窗口的下边界也前移一格。按照这种方法发送窗口持续地维持了一系列未被确认的帧。

●滑动窗口协议可用于网络数据传输时的流量控制,以避免拥塞的发生。该协议允许发送方在停止并等待确认前发送多个数据分组。由于发送方不必每发一个分组就停下来等待确认,因此该协议可以加速数据的传输,提高网络吞吐量。如果过多的源同时以很快的速度发送大量的数据包,而此时接收方并没有如此高的接收数据的能力,因此极易导致网络的拥塞。所以,为了控制发送方的发送速度,防止发送方并考虑到受发送缓冲区大小的制约等,要求对发送方已发出但尚未经确认的帧的数目加以限制,同时使网络的传输效率得到提高,滑动窗口协议应运而生,它使得发送方可以在未收到确认的情况下,同时发送多个数据分组,由此大大提升了网络吞吐量。

请解释Go-BackN协议是如何进行的。

  • 接收点丢弃从第一个没有收到的数据包开始的所有数据包。
  • 发送点收到NACK后,从NACK中指明的数据包开始重新发送。

请解释Selective Repeat协议是如何进行的。

  • 发送点连续发送数据包但对每个数据包都设有个一个计时器。
  • 当在一定时间内没有收到某个数据包的ACK时,发送点只重新发送那个没有ACK的数据包
© 版权声明
THE END
喜欢就支持以下吧
点赞1赞赏 分享
评论 抢沙发

请登录后发表评论

    暂无评论内容