《《计算机网络技术及应用(第二版)》-刘永华-电子教案 第4章 数据链路层》由会员分享,可在线阅读,更多相关《《计算机网络技术及应用(第二版)》-刘永华-电子教案 第4章 数据链路层(73页珍藏版)》请在金锄头文库上搜索。
1、第4章 数据链路层,计算机网络技术及应用(第2版),4.1数据链路层的设计问题,4.1.1几个主要概念 在计算机上网络中,我们经常提到“链路”和“数据链路”这两个术语,事实上“链路”和“数据链路”并非一回事。所谓链路(link)是一条无源的点到点的物理线路段,中间没有任何其他的交换结点。在进行数据通信时,两个计算机之间的通路往往是由许多的链路串接而成的。可见,一条链路只是一条通路的组成部分。 数据链路(data link)则是另一个概念,这是因为当需要在一条线路上传送数据时,除了必须有一条物理线路外,还必须有通信协议来控制这些数据的传输。若把实现这些协议的硬件和软件加到链路上,就构成了数据链路
2、。现在最常用的方法就是使用适配器(网卡)来实现这些协议的硬件和软件。一般的适配器都包括了数据链路层和物理层这两层的功能。,常常在两个对等的数据链路层之间画出一个数字管道,而在这条数字管道上传输的数据单位是帧。见图4-1。,有时候我们将链路划分为物理链路和逻辑链路。所谓物理链路就是上面我们所说的链路,而逻辑链路就是上面的数据链路,是物理链路加上必要的通信协议。这两种划分实质上是一样的。 早期的数据通信协议曾叫作通信规程(procedure)。因此在数据链路层,规程和协议是同义语。,数据链路层的主要用途是为在相邻网络实体之间建立、维持和释放数据链路连接,并传输数据链路服务数据单元。亦即数据链路层的
3、主要职责是控制相邻系统之间的物理链路,它在物理层传送“位“信息的基础上,在相邻节点间传送被称为帧的数据信息,数据链路层也需进行检错、纠错,从而向网络层提供无错的透明传送。数据链路层软件是计算机中网络最基本的软件,该层是任何网络都必须有的层次,相对于高层来说,所用的服务和协议比较成熟。,4.1.2数据链路层的目的,数据链路层在网络实体间提供建立、维持和释放数据链路连接以及传输数据链路服务数据单元所需的功能和过程的手段,在物理连接上建立数据链路连接。 数据链路层检测和校正在物理层出现的错误,并能使网络层控制物理层中的数据电路的互联。,4.1.3数据链路层的主要功能,(1) 链路管理 当网络中的两个
4、节点要进行通信时,数据的发方必须确知收方是否已经已经处于准备。为此,通信的双方必须先要交换一些必要的信息。或者说是必须先建立一条数据链路。同样地,在传输数据时要维持数据链路,而在通信完毕时要释放熟路链路。数据链路的建立、维持和释放就叫做链路管理。 根据数据链路层向网络层提供的服务质量、应用环境以及是否有连接这三个因素,服务可分为无应答无连接服务、有应答无连接服务和面向连接的服务三种。,(2) 帧定界 在数据链路层,数据的传输单位是帧。数据一帧一帧地传送,就可以在出现差错时将有差错的帧再重传一次,而避免了将全部数据都进行重传。帧定界是指收方应当能从收到的比特流中准确地区分出一帧的开始和结束在什么
5、地方。帧定界也可称为帧同步。 (3) 流量控制 发方发送数据的速率必须使得收方来得及接收。当收方来不及接收时,就必须及时控制发方发送数据的速率。这种功能称为流量控制(flow conctrol)。采用接收方的接收能力来控制发送方的发送能力这是计算机网络流量控制中采用的一般方法。,(4) 差错控制 在计算机通信中,一般都要求有极低的比特差错率。为此,广泛采用了编码技术,编码技术有两大类。一类是前向纠错,也就是收方收到有差错的数据帧时,能够自动将差错改正过来。这种方法的开销较大,不大适合于计算机通信。另一类是差错检测,也就是收方可以检测出收到的数据帧有差错(但并不知道出错的确切位置)。当检测出有差
6、错的数据帧就立即将它丢弃,但接下去有两种选择:一种方法是不进行任何处理(要处理也是有高层进行),另一种方法则是由数据链路层负责重传丢弃的帧。 (5) 将数据和控制信息区分开 在许多情况下,数据和控制信息处在同一帧中。为此一定要有相应的措施使得收方能够将他们区分开来。,(6) 透明传输 所谓透明传输就是不管所传数据是什么样的比特组合,都应当能够在链路上传送,当所传数据中的比特组合恰好出现了与某一控制信息完全一样时,必须有可靠的措施,使得接收方不会将这种比特组合的数据误认为是某种控制信息。只要能够做到这一点。数据链路层的传输就被称为是透明传输。在面向比特的同步规程和面向字符的同步规程中都会遇到这个
7、问题。 (7) 寻址 必须保证每一帧都能送到正确的目的站,接收方也应知道发送方是哪个站。,4.2差错控制技术,在数据通信过程中,由于衰耗、失真和噪声会使通信线路上的信号发生错误。为了减少错误,提高通信质量,一是改善传输信道的电气特性,更重要的是采取检错、纠错技术,即差错控制。差错控制的核心是抗干扰编码,一类是检错码、另一类是纠错码。,4.2.1差错控制原理,1差错控制的基本原理是在发送端对信源送出的二进制序列附加多余数字,使得这些数字与信息数字建立某种相关性。在接收端检查这种相关性来确定信息在传输过程中是否发生错误以检测传输差错。 例如:信息序列有100个比特,分成10组。每一组增加1比特,这
8、一比特是每一组奇偶校验得到的。在接收端检查这一比特是否正确,来判断信息在传输过程中是否发生错误。,新加入的码元愈多,冗余度愈大,纠错能力欲强,但效率越低。 分组码:将信息码分组,并为每个组附加若干监督的编码,称为“分组码”。在分组码中,监督码元仅监督本码组中的信息码元。 分组码一般可用符号(n,k)表示,n是码组中的总位数,k是每组码二进制信息码元的数目。 n-k = r是监督码元的数目。,2差错控制编码的特性和能力,(1)海明(Hamming)距离 海明(Hamming)距离是两个不同的码组,其对应的码位的不同码元的个数。 例如,码组(01)和(00)海明距离是1,码组(110)和)(101
9、)的海明距离是2。,(2)一个码组中,任何两个码组中海明(Hamming)距离的最小值称为该码组的最小值。 例如:在(000),(011),(101),(110)4个码组中,最小距离d=2。而码组集合(000),(111)最小距离d=3。,(3)最小码距d0与编码的检错和纠错能力的关系。 定理4.1 若一种码的最小距离为d,则它能检查传输差错个数(称为检错能力)e应满足de+1。 该定理说明要想使传输的码组具有检错能力,该码组集合的最小距离必须d2。 定理4.2 若一种码的最小距离为d,则它能纠正传输差错个数(称为检错能力)t应满足d2t+1。 定理4.3 若一种码的最小距离为d0,则它能检查
10、e个错误,同时又能纠正t个以下错误的条件dt+e+1。,例4.1 求码集合(000),(011),(101),(110)和(000),(111)的e值并作必要的分析。 由于码组(000),(011),(101),(110)的最小的距离为2,则e = d1=2-1=1,则可检测出一个错。 (000),(111)的最小的距离为3,则e= d1=3-1=2,则可检测出两个错。当用于纠错时,由定理4.2 t=1,能纠正一个错。由定理4.3 t=1,e=1,能纠正、检错各一个。,4.2.2差错控制编码,1循环冗余校验码(CRC) 在计算机通信中广泛应用的是循环冗余校验码(CRC)。CRC 校验码的基本思
11、想是利用线性编码理论。利用代数的方法可以把它设计成各种有用的且有很大纠错能力的编码。,背景知识:任何一个由二进制数位串组成的代码都可以和一个只含有“0”和“1”两个系数的多项式建立一一对应的关系。这个多项式成为码多项式。 一个n位的二进制序列,它的码多项式为:Xn-1 到 X n次多项式的系数系列。 例如:110110的码多项式,循环码的定义:如果分组码中各码字中的码元循环左移位(或右移位)所形成的码字仍然是码组中的一个码字(除全零码外),则这种码称为循环码。例如n长循环码中的一个码为C=Cn-1Cn-2C1C0 , 依次循环移位后得: Cn-2Cn-3C0C1 C0Cn-1C2C1,码多项式
12、的运算: 二进制码多项式的加减运算: 二进制码多项式的加减运算实际上是逻辑上的异或运算。 循环码的性质:在循环码中,n-k次码多项式有一个而且仅有一个,称这个多项式为生成多项式G(X)。在循环码中,所有的码多项式能被生成多项式G(X)整除。,(1)编码方法,由信息码元和监督码元一起构成循环码,首先把信息序列分为等长的k位序列段,每一个信息段附加r位监督码元,构成长度为n=k+r的循环码。循环码用(n,k)表示。它可以用一个n-1次多项式来表示。n位循环码的格式如图4-2所示:,一个n位的循环码是由K位信息位加上r位校验位组成的。其中r=n-k。这样新组成的二进制序列叫作循环码(CRC)。标征C
13、RC循环码的多项式叫生成多项式G(x)。K位二进制加上r位CRC校验位后,既信息位要向左移(r=n-k),这相当于A(X)乘上X。X A(X)被生成多项式G(X)除,得整数多项式Q(X)加上余数多项式R(X),即:,移项得,说明信息多项式A(X)和余数多项式R(X)可以合并成一个新的多项式C(X)称为循环码多项式,则该多项式是生成多项式G(X)的整数倍,既能被G(X)整除。根据这一原理在发送端用信息码多项式乘上X除以生成多项式G(X)所得余数多项式R(X)就是所要加的监督位。在接收端将循环码多项式C(X)除以生成多项式G(X),若能整除,则说明传送正确,否则说明传送出现差错。,(2)举例分析,
14、例4.2 如信息码元为1101,生成多项式G(X)= X+ X+1,编一个(7,4)循环码。 A(X)=1101 向左移3位的1101000 除1011的余数为1,则余数多项式R(X)=001。 在做除法过程中,被除数减除数是做逻辑运算。,例4.3 某一个数据通信系统采用CRC校验方式,其中:生成多项式G(X)= X4+X+1, 发送端要发送的信息序列为10110,求:(1)校验码及校验码多项式;(2)发送端经过循环冗余编码后要发送的比特序列; 解:生成多项式为G(X)= X4+X+1,生成多项式的比特序列是:10011,为4阶,所以将发送端要发送的信息序列10110左移四位,得到XRD(X)
15、为:101100000,(1)用XRD(X)/G(X),所以校验码为:1111 ,校验码多项式为: X3+X2+X+1 。 发送端经过循环冗余编码后要发送的比特序列为:101101111。,(3)在串行通信中通常使用的三种生成多项式G(X)来产生校验码。,(4)编码特点,由于码的循环性,它的编解码的设备比较简单。 纠错能力强,特别适合检测突发性的错误,除了正好数据块的比特值是按除数变化外,循环冗余校验(CRC)将检测出所有的错误。 所以在计算机通信中得到广泛的应用。,4.2.3差错控制方式,差错控制编码一类是检错码(如奇偶校验)、另一类是纠错码。根据检错码和纠错码的结构的不同形成了不同的差错控
16、制方式 (1)利用检错码 (2)利用纠错码 在数据通信过程中,利用差错控制编码进行系统传输的差错控制的基本工作方式分成四类:自动请求重发(ARQ ,Automatic Repeat Request),前向纠错(FEC,Forword ErrorCorrection),混合纠错(HEC,Hybrid Error correction),信息反馈(IRQ,Information Repeat Request),4.2.4 几种纠错方式,1前向纠错(FEC,Forword Error Correction) (1)工作过程: 利用纠错编码,使得在系统的接收端译码器能发现错误并能准确地判断差错的位置,从而自动纠正它们。所以使用前向纠错。,(2)FEC方式的特点:,接收端自动纠错,实时性好。 无需反馈通道。特别适用于单点向多点同时传送的方式。 纠错码需要较大的冗余度,传输效率下降。 控制规程简单,译码设备复杂。 纠错码应与信道特性相配合,对信道的适应性差。,2混合纠错(HEC,