目 录
一、课程设计目的与意义 2
二、课程设计要求 2
三、帧结构分析 2
1.帧的介绍 2
2.CRC校验分析 4
四、帧封装的过程 7
1、填充帧头部字段 7
2、填充数据字段 8
3、CRC校验 9
五、帧封装流程图 11
六、帧封装方法的相关扩展 12
1、比特型算法 12
2、字节型算法 12
七、程序调试分析与结果 13
八、课程设计心得与体会 14
附录一:参考文献 15
附录二:帧封装源程序 16
一、课程设计目的与意义
帧是在数据链路层数据进行传输与交换的基本单位。构造帧对于理解网络协议的概念、协议执行过程以及网络问题处理的一般方法具有重要的意义。本次课程设计的目的是应用数据链路层与介质访问控制层的知识,根据数据链路层的基本原理,通过构造一个具体的Ethernet帧,从而深入理解网络协议的基本概念与网络问题处理的一般方法。
二、课程设计要求
编写程序,根据给出的原始数据,组装一个IEEE802.3格式的帧,(默认的输入文件为二进制原始数据(文件名分别为li和lzy))。
1) 要求程序为命令行程序。比如,可执行文件各为framer.exe,则命令行形式如下:
framer inputfile outpurfile
其中,inputfile为原始数据文件,outpurfile为输出结果。
2) 输出:对应input1和input2的结果分别为output1和output2。
3) 开发环境:
硬件环境:PC微机
软件环境:Windows 2000 Microsoft Visual C++ 6.0
三、帧结构分析
1.帧的介绍
术语“帧”来源于串行线路上的通信。其中,发送者在发送数据的前后各添加特殊的字符,使它们成为一个帧。Ethernet从某种程序上可以被看作是机器这间的数据链路层连接。
首先我们来认识一下Ethernet帧结构,Ethernet V2.0规范和IEEE802.3标准中的Ethernet帧结构有一些差别,这里我们按802.3标准的帧结构进行讨论,图一给出了Ethernet帧结构图。
图一 Ethernet帧结构
如图一所示,802.3标准的Ethernet帧结构由6部分组成。
(1)前导码与帧前定界符字段
前导码由56位(7B)的1010101…101010位序列组成。帧前定界符可以
视为前导码的延续。1B的帧前定界符结构为10101011。
如果将前导码与帧定界符一起看,那么在62位101010…1010位序列之后出
现11。在11之后是Ethernet帧的目的地址字段。前导码与帧前定界符主要是保证接收同步,这8B接收后不需要保留,也不记入帧头长度中。
(2)目的地址和源地址
目的地址(DA)与法制地址(SA)分别表示帧的接收结点地址与发送结点的硬件地址。
● 在Ethernet帧中,目的地址和法制地址字段长度可以是2B或6B。目前
的Ethernet都使用6B(即48位)长度的地址。
● Ethernet帧的目的地址可以是单播地址(unicast address)、多播地址
(multicast address)与广播地址(broadcast address),目的地址的第一位为0表示单播地址,为1表示多播地址,目的地址为全1表示广播地址。
(3)长度字段
802.3标准中的帧用2B定义数据字段包含的字节数。协议规定,帧数据的
最小长度为46B,最大长度为1500B。设置最小帧长度的目的是使每个接收结点能够有足够的时间检测到冲突。
(4)数据字段
帧数据字段的最小长度为46B。如果帧的LLC数据少于46B,则应将数据字
段填充至46B。填充字符是任意的,不计入长度字段值中。
(5)检验字段
帧校验字段(FCS)采用32位的CRC校验。校验的范围包括目的地址字段、
源地址字段、长度字段、LLC数据字段。
此处,为了简便起见,采用8位的CRC校验。CRC校验的生成多项式为:
G(x)= x8+ x2+x+1
某些帧结构中还会包括帧类型字段,用来识别些帖所承载的数据的类型。当一个帧到达指定的计算机时,操作系统根据帧类型决定用哪个协议软件模块对它进行处理。自识别帧的主要优点是,可以在同一物理网络中使用多个协议而互不干扰。
2.CRC校验分析
我们已经知道了差错控制在通信中的重要意义,以及简单的差错校验码计算过程。在这里我们进一步来了解循环冗余编码(CRC)的编码方式。它是一种重要的线性分组码、编码和解码方法,具有简单、检错和纠错能力强等特点,在通信领域广泛的用于实现差错控制。实际上,除数据通信外,CRC在很多领域也是大有用武之地的。
利用CRC进行检错的过程可简单描述如下:在发送端根据要传送的k位二进制码序列,以一定的规则产生一个校验用的r位监督码(CRC码),附在原始信息的后边,构成一个新的二进制码序列(共k+r位),然后发送出去。在接收端,根据信息码和CRC码之间所遵循的规则进行检验,以确定传送中是否出错。这个规则在差错控制理论中称为“生成多项式” 。
(1)CRC编码的代数学原理
在代数编码理论中,将一个码组表示为一个多项式,码组中的各码元作为多项式的系数。
例如,1100101表示为1·x6+1·x5+0·x4+0·x3+1·x2+0·x+1,
即 x6+x5+x2+1。
设编码前的原始信息多项式为P(x), P(x)的最高幂次加1等于k;生成多项式为G(x),G(x)的最高幂次等于r;CRC多项式为R(x);编码后的带CRC的信息多项式为T(x)。
发送编码的方法是:将P(x)乘以x^r(即对应的二进制码序列左移r位),再除以G(x),得余式即为R(x)。
用公式可以表示为T(x)=xrP(x)+R(x)
接收方解码的方法是:将T(x)除以G(x),如果余数为0,则说明传输中无错误发生,否则说明传输有误。
举例来说,设信息码为1100,生成多项式为1011,即P(x)=x³+x²,G(x)=x³+x+1,则可以用以下方法计算CRC 。
xrP(x) x3(x3+x2) x6+x5 x
-------- = ---------- = -------- = (x3+x2+x) + --------
G(x) x3+x+1 x3+x+1 x3+x+1
即R(x)=x。注意到G(x)最高幂次r=3,得出CRC为010。如果用竖式除法,计算过程为:
1110
1011/1100000 (1100左移3位)
1011
1110
1011
1010
1011
0010
0000
010
因此,T(x)=(x6+x5)+(x)=x6+x5+x,即1100000+010=1100010。
如果传输无误,则
T(x) x6+x5+x
G(x) x³+x+1
无余式。看一下上面的竖式除法,如果被除数是1100010,显然在商第3个1时,就能除尽。
上述推算过程有助于我们理解CRC的概念。但如果直接编程来实现上面的算法,不仅繁琐,而且效率也不高。实际上在工程中不会直接这样去计算和验证CRC。 表一 标准的CRC
该表中列出了一些标准CRC资料。
① 生成多项式的最高幂次项系数是固定的1,故在简记式中,将最高的1统一去掉了,如04C11DB7实际上是104C11DB7 。
② 前称CRC-CCITT。ITU的前身是CCITT。
(2)CRC的硬件电路实现
图2给出了CRC运算通用电路的方框图。
g1 g2 gn-2 gn
LSB MSB
b0 b1 b2 bn-2 bn-1
图二 CRC运算通用电路方框图
CRC计算生成多项式G(x)通常用n次多项式定义:G(x)=Xn+gn-1Xn-1+…giXi+…+g2X2+g1X+1,其中gi为0或1,i=1,2,…,n-1。通常CRC计算可以用有n个存储器级的移位寄存器实现,如图二所示。如果多项式的相应项的系数为1,那么相应的存储器级输入端的模2加法器是有分支的。根据应用的不同,在系统开始工作前将所有的移位寄存器全部置“0”或“1” 。
在图二中输入端送入的是原始数据序列,移位寄存器各级的输出b0、b1、…、bn-2、bn-1便是CRC码字。其中b0和bn-1分别代表最低有效位(LSB)和最高有效位(MSB)。
(3)CRC的基本实现
以CRC-8(X8+X2+X1+1)为例(如图三所示),它由多个移位寄存器和加法器组成。编码、解码前将个寄存器初始化为0,输入位作为最右边异或操作的输入之一。三个寄存器上的移位操作同时进行,均为左移一位,左边寄存器的最左一位作为三个异或操作的输入之一。每次移位时,最右边的寄存器内容作为中间异或操作的输入之一,中间的寄存器的内容作为最左边异或操作的输入之一,各个异或操作的结果作为与它左边那个寄存器的移入位。重复以上步骤,每输入一个位就做一次移位操作,直到输入了所有要计算的数据为止。这时,这个寄存器组中的数据就是CRC-8的结果。图三给出了CRC基本实现方法。
输入
图三 CRC基本实现
CRC的工作原理是,CRC在发送端编码和接受端校验时,都可以利用事先约定的生成多项式G(x)来得到,K位要发送的信息位可对应于一个(K-1)次多项式K(x),r为冗余位则对应于一个(r-1)次多项式R(x),有r位冗余位组成的n=k+r位码字则对应与一个(n-1)次多项式T(x)= Xr*K(x)+R(x)。
(4)循环冗余校验码的特点
CRC校验码的检测能力很强,不仅能检查出离散错误,还能检查出突发错误。CRC校验码具有以下检错能力:
● CRC检验码可检测出所有单个错误。
● CRC检验码可检测出所有奇数位错误。
● CRC检验码可检测出所有双位的错误。
● CRC检验码可检测出所有小于、等于校验位长度的突发错误。
● CRC检验码可以[1- (1/2)k-1]的概率检测出长度为(K+1)位的突发错误。
四、帧封装的过程
1、填充帧头部字段
要完成一次帧封装的过程,首先要完成的就是帧头部的装入,这一过程非常简单,只要将前导码、定界符、目的地址、源地址、长度字段的响应数值按顺序写入就可以了。其中,长度字段的值即为要发送的数据的实际长度。我们可以通过以下两种方式来获得长度字段的值。
方法一
While(!in.eof()) //读数据至缓冲区buf
{
in.get(a);
buf[j]=a; //通过j来记录输入数据的长度
j++;
}
方法二
infile.open(argv[1],ios::binary); //打开指定输入文件
infile.seekg(0,ios::end); //将文件读指针移到末尾
short length=(short)infile.tellg(); //获得位置偏移量,即为输入文件长度
file.put(char(length/256)); //将该长度写入数据长度字段(2B)
file.put(char(length%256));
注意,上面程序的最后两行是把读到的数据长度值按逆序填入长度字段。这就涉及网络字节序的问题。
计算机数据存储有两种字节优先顺序,即高位字节优先和低位字节优先。
● 低位字节优先:低序字节存储在起始地址。
● 高位字节优先:高序字节存储在起始地址。
Internet上的数据以高位字节优先顺序在网络上传输,所以对于在机器内部以低位字节优先方式存储的数据来说,在Internet上传输数据时就需要进行转换,否则就会出现数据不一致。
下面是几个字节顺序转换函数:
● Htonl():把32位值从主机字节序转换成网络字节序。
● Htons():把16位值从主机字节序转换成网络字节序。
● Ntonl():把32位值从网络字节序转换成主机字节序。
● Ntons():把16位值从网络字节序转换成主机字节序。
2、填充数据字段
在填充数据字段的过程中要注意的主要问题是数据字段的长度。802.3标准中规定了帧数据字段的最小长度为46B,最大长度为1500B。如果数据不足46B,则需要通过填充0来补足;如数据长度超过1500B,则将超过部分封装入下一个帧进行发送。
由于帧头部分应该包括6B目的地址、6B源地址字段、2B长度字段以及4B帧校验字段,因此帧头部分长度为18B。前导码与帧前定界符不计入帧头部长度中。那么,Ethernet帧的最小长度为64B,最大长度为1518B。
填充数据字段的代码如下:
if(len==1500) //读满1500B后,封装成一个帧并输出
{
… … //封装成一个帧并输出
len=0; //长度计数重置0
)
//如果数据的长度小于46则补0
If(len<64)
{
for(i=len;i<46;i++)
{
fr.data[i]=0x00; //在数据字段中填充0
}
}
data_len=len; //获得数据的实际长度放入data_len
3、CRC校验
帧封装的最后一步就是对数据进行校验,并将校验结果记入帧校验字段。下面举例说明在本程序中是如何实现CRC-8校验算法的。设数据为10010010,CRC-8的生成多项式为X8+X2+X1+1即10000111。先看一下在代数学中计算CRC校验的一般算法。如果用竖式除法,计算过程如下:
10010001
100000111√1001001000000000 (后面补8个0)
1000000111
100011000
100000111
111110000
100000111
11110111
从上式可以看出,CRC编码实际上是一个循环移位的模2运算。对于CRC-8,假设有一个9位的寄存器,通过反复移位和进行CRC除法,最终该寄存器中的值去掉最高一位就应该是我们所需要的余数。
上述步骤可以用下面的流程描述:
//crc是一个9位的寄存器
把crc中的值置为0
在原始数据input后添加8个0
While(数据未处理完)
begin
if(crc首位是1)
crc=crc XOR 100000111
把crc中的值左移一位,从input中读一位新的数据并置于crc的0位
end
crc中后8位就是经过CRC-8校验的余数。这样,我们只需要看后8位即可,因此上面流程可以简化。构造一个8位的寄存器crc,初始值为0,数据依次移入crc的0位,同时crc的7位移出。当移出的数据为1时,crc才和0000111进行XOR运算;移出的数据为0时,不做运算。每次crc中数据左移后就需要从输入数据中读入一位新的数据。由于左移时crc 0位补0,因此当读入的数据最高位为1时还需要对crc 0位进行处理(将crc与00000001异或使0位置1)。
下面给出伪代码:
//crc是一个8位的寄存器
把crc中的值置为0
在原始数据input后添加8个0
while(数据未处理完)
begin
if(crc首位是1)
crc左移1位
crc=crc XOR 00000111
else
crc左移1位
if(从input中读入的新的数据)
end
五、帧封装流程图
Y
图四 帧封装流程图
六、帧封装方法的相关扩展
除了上面介绍的方法之外,还有其它一些算法可以完成CRC校验。例如,多项式除法,可用除法电路来实现。除法电路的主体由一组移位寄存器和模2加法器(异或单元)组成。以CRC-ITU为例,它由16级移位寄存器和3个加法器组成,见下图(编码/解码共用)。编码、解码前将各寄存器初始化为"1",信息位随着时钟移入。当信息位全部输入后,从寄存器组输出CRC结果。
图五 除法电路实现CRC
1、比特型算法
上面的CRC-ITU除法电路,完全可以用软件来模拟。定义一个寄存器组,初始化为全"1"。依照电路图,每输入一个信息位,相当于一个时钟脉冲到来,从高到低依次移位。移位前信息位与bit0相加产生临时位,其中bit15移入临时位,bit10、bit3还要加上临时位。当全部信息位输入完成后,从寄存器组取出它们的值,这就是CRC码。
2、字节型算法
比特型算法逐位进行运算,效率比较低,不适用于高速通信的场合。数字通信系统(各种通信标准)一般是对一帧数据进行CRC校验,而字节是帧的基本单位。最常用的是一种按字节查表的快速算法。该算法基于这样一个事实:计算本字节后的CRC码,等于上一字节余式CRC码的低8位左移8位,加上上一字节CRC右移8位和本字节之和后所求得的CRC码。如果我们把8位二进制序列数的CRC(共256个)全部计算出来,放在一个表里 ,编码时只要从表中查找对应的值进行处理即可。
CRC-ITU的计算算法如下:
1) 寄存器组初始化为全"1"(0xFFFF)。
2) 寄存器组向右移动一个字节。
3) 刚移出的那个字节与数据字节进行异或运算,得出一个指向值表的索引。
4) 索引所指的表值与寄存器组做异或运算。
5) 数据指针加1,如果数据没有全部处理完,则重复步骤b。
6) 寄存器组取反,得到CRC,附加在数据之后。
CRC-ITU的验证算法如下:
1) 寄存器组初始化为全"1"(0xFFFF)。
2) 寄存器组向右移动一个字节。
3) 刚移出的那个字节与数据字节进行异或运算,得出一个指向值表的索引。
4) 索引所指的表值与寄存器组做异或运算。
5) 数据指针加1,如果数据没有全部处理完,则重复步骤b (数据包括CRC的两个字节)。
6) 寄存器组的值是否等于“Magic Value”(0xF0B8),若相等则通过,否则失败。
七、程序调试分析与结果
先进入Microsoft Visual C++ 6.0中,编译运行源程序,生成可执行文件。其可执行文件名为lizeyin.exe。
然后进入DOS中,进行帧的封装,其过程如下图五所示。
图六 帧封装过程图
其中,输入命令行中的“lizeyin”指的是生成的可执行文件,这里生成的是lizeyin.exe;“原始数据文件” 指的是在可执行文件存放路径下的一个数据文件,我在这里新建了一个文本文档li.txt,其中的内容为:
My name is lizeyin!!! 计科05104班。
其二进制形式如下图七所示:
图七 原始数据的二进制形式图
“输出结果”是将原始数据文件进行封装后所得到的一个文件,它也将存放在可执行文件存放的路径下,这里封装后的文件名是:lzy.txt,其中的内容是:
鋯: €_鎒 !My name is lizeyin!!! 计科05104班
其二进制形式如下图八所示:
图八 输出结果的二进制形式图
八、课程设计心得与体会
课程设计是培养学生综合运用所学知识,发现、提出、分析和解决实际问题,锻炼实践能力的重要环节,是对学生实际工作能力的具体训练和考察过程。随着科学技术发展的日新日异,当今计算机应用在生活中可以说得是无处不在,因此作为二十一世纪的大学来说掌握计算机开发技术是十分重要的。
回顾起此次课程设计,我感慨颇多。它不仅巩固了我所学过的知识,而且让我学到了很多在书本上所没有学到过的知识。通过这次课程设计使我懂得了理论与实际相结合是很重要的,只有理论知识是远远不够的,只有把所学的理论知识与实践相结合起来,从理论中得出结论,才能真正为社会服务,提高自己的实际动手能力和独立思考的能力。在该设计过程中我遇到了许多的问题,让我发现了自己的不足之处,对以前所学过的知识理解得不够深刻,掌握得不够牢固,看到了自己的实践经验还是比较缺乏,理论联系实际的能力还急需提高。
附录一:参考文献
[1] 吴功宜、胡晓英等,计算机网络课程设计,北京:机械工业出版社,2007.12
[2] 杨丰瑞、杨丰任,实用教程最新计算机网络,北京:中国铁道出版社,2007.7
[3] 胡晓英等,计算机网络课程设计,北京:机械工业出版社,2005.9
[4] 郭国强等著,计算机网络与Internet教程,北京:清华出版社,2006.11
附录二:帧封装源程序
#include
#include
void main (int argc,char* argv[])
{
if(argc!=3)//判断输入的命令行格式是否正确
{
cout <<"请按以下格式输入命令行:framer inputfile outputfile" <
return;
}
fstream file;//创建文件流
file.open(argv[2],ios::in |ios::out |ios::binary |ios::trunc);
//打开指定输出文件,读写方式为以二进制方式可读可写,如文件存在则清除其
for(int i=0;i <7;i++) file.put(char(0xaa));//写入7B前导码
file.put(char(0xab));//写入1B帧前界定符
long pCrcs=file.tellp();//获得当前文件指定指针位置,计算CRC时从这里开始
char
dst_addr[6]={char(0x00),char(0x00),char(0xe4),char(0x86),char(0x3a),
char(0xdc)};
file.write(dst_addr,sizeof(dst_addr));
//写入6B目的地址
char
src_addr[6]={char(0x00),char(0x00),char(0x80),char(0x1a),char(0xe6),
char(0x65)};
file.write(src_addr,sizeof(src_addr));
//写入6B源地址
ifstream infile;//创建输入文件流
infile.open(argv[1],ios::binary);//打开指定输入文件
infile.seekg(0,ios::end);//将文件读指针移到末尾
short length=(short)infile.tellg();//获得位置偏移量,即为输入文件长度
file.put(char(length/256));//将该长度写入数据长度字段(2B)
file.put(char(length%256));
char* data=new char[length];
infile.seekg(0,ios::beg);
infile.read(data,length);//从输入文件中读出所有数据至data中
file.write(data,length);//将data中数据写入输出文件
infile.close();//关闭输入文件
delete data;//回收data
if(length <46) for(int i=0;i <46-length;i++) file.put(char(0x00));
//数据字段不足46B的部分用0填充
long pCrc=file.tellp();
//获得当前位置,计算后的CRC码将写到这个位置
file.put(char(0x00));
//数据后补1B的0,用于crc计算
short total=short(file.tellp())-(short)pCrcs;
//需要进行计算的数据长度
file.seekg(pCrcs,ios::beg);
//将读指针指向目的地址字段,从这里开始crc计算
unsigned char crc=0; //初始余数为0
while(total--)
{
unsigned char temp;
file.get(temp); //读1B的数据
//以下模拟数据除以100000111的二进制除法过程
for(unsigned char i=(unsigned char)0x80;i>0;i>>=1)
{
if(crc&0x80)
{
crc<<=1;
if(temp&i) crc^=0x01;
//将输入数据相应位的值递补到余数末位
crc^=0x07;
//进行除法运算(即减去除数的低8位:00000111)
}
else
{
crc<<=1;
if(temp&i) crc^=0x01;
//将输入数据相应位的值递补到余数末位
}
}
}
file.seekp(pCrc,ios::beg);
file.put(crc);
cout<<"帧文件"<
file.close(); //关闭文件
}
¥29.8
¥9.9
¥59.8