数据链路层协议的设计分析

数据链路层协议的设计分析

petri网通信协议的分析在计算机网络的体系结构中，数据链路层位于第二层。数据链路层屏蔽了物理层的差异，并为网络层提供了一个完整的接口，以便于当前流行的tcp协议和ip地址。它不会受到底层的影响，也不会成功运行。因此，对数据链路层的研究分析是非常重要的。Petri网是一种适合于并发、异步、分布式系统描述与分析的图形数学工具，在通信协议的分析方面已经成为最成功的应用之一。为此，我们对一个基本数据链路层协议原有Petri网模型进行了改进及动态行为分析，使其更加具有合理性。1网络层和数据链路层、物理层在分析协议前，有必要假设两个通用的理想状态：网络层、数据链路层、物理层是独立的进程；协议只考虑通信错误，不考虑机器发生故障及重起引起的问题。1.1基于库所等的petri网模型现实中，通信信道本身是不可靠的，在信道中传输的数据会发生丢失或者错误。我们分析的是一个比较常规的噪声信道的单工停等协议。由于所传输的帧可能发生错误，采用重发机制来弥补，引入定时器。假设发送方为A，接收方为B。A发送一帧的同时，保存该帧副本，并启动定时器，若在定时器溢出之前收到确认帧，则明确知道已发送的帧被正确接收，于是删除已发送帧的副本，并发送下一帧。如果此帧在传输过程中丢失，或者发生错误被B拒绝，则无确认帧发送，因而定时器溢出，A将重发该帧。若确认帧ack丢失或损坏，则A无法意识到B已经正确接收数据帧，A也会重发。这就会引起B收到重复的帧。为了解决这个问题，给每一帧加上序号。由于在该协议中采用停—等方式，我们只需将帧的序号最大定义为1。因此，A的发送次序为0帧、1帧、0帧、1帧……首先发送0帧，同时B被定义同样的序号，即首先希望接收0帧，当该帧正确接收后，希望接收的就是下一帧1帧。若返回的ack丢失或损坏，A重发0帧，当重发的0帧到达B时，由于序号与此时B希望接收的帧的序号1不相符，则B意识到这是重复帧，从而拒绝该帧。文献中已对该协议做出模型，具体模型参看文献，233页，Figure3-23ㄢ该模型是基于发送方、信道、接受方的严格逻辑状态来定义库所含义而建立模型的。我们也可以将逻辑状态与实际情形相结合建立另外一个Petri网模型，此模型更加符合现实情况，容易理解。具体分析及建模如下：分别确定三方的库所。对于发送方，所要发送的帧被附上序号以0帧、1帧交替发送，因此发送方需要两个库所，分别代表0帧、1帧的缓存器。在信道中传输状态有三种：传输0帧、1帧、和确认帧ack。对于接收方，相应也需要0帧、1帧的缓存器，但是仅仅有两个缓存器不能完整表现协议功能。因为没有体现出接收方只有正确接收到所期望的帧，才能进入准备接收下一帧的状态。因此，我们认为还应加上两个逻辑状态，分别代表准备接收0帧和1帧的状态。变迁的设定需要尊重一个原则，即变迁能否发生及发生的影响完全取决于自然规律，不带主观性。为此，我们构造如下Petri网模型：具体库所、变迁代表的含义如下：S1、S6：分别代表发送方0帧、1帧缓存器S2、S7、S5：分别代表信道中正传输0帧、1帧、确认帧ackS3、S8：分别代表接收方0帧、1帧缓存器S4：表示正确接收1帧后准备接收0帧的状态S9：表示正确接收0帧后准备接收1帧的状态t1、t8：定时器溢出t2、t6、t9：分别代表0帧、确认帧、1帧丢失t3、t10：分别代表0帧、1帧接收t4、t11：分别代表经过校验发现0帧、1帧错误而丢弃t5：接收0帧并发送0帧的确认帧ack，同时进入准备接收下一帧1帧的状态t12：接收1帧并发送1帧的确认帧ack，同时进入准备接收下一帧0帧的状态t7：正确收到0帧的确认帧，则删除S1中缓存的0帧幅本，并将下一帧1帧发送到信道上同时在缓存器S6中保存此1帧的副本，启动定时器t13：正确收到1帧的确认帧，则删除S6中缓存的1帧幅本，并将下一帧0帧发送到信道上同时在缓存器S1中保存该帧副本，启动定时器t14：拒绝重复帧0帧，并再次返回确认帧（如果0帧已经被正确接收，则计数器S9变为激活状态，即接收方已经处于准备接受1帧的状态，而返回的确认帧丢失，则发送方认为此0帧发生错误或者丢失，则重发，在接受方收到重复的0帧，拒绝并且再次返回确认帧）t15：拒绝重复帧1帧，并再次返回确认帧1.2噪声信道的单工停等协议的性能分析协议的正确性验证主要包括以下几个方面：协议的活性（无死锁）；协议的循环可达性（能否按规定正常循环运转）；协议的一致性（协议的服务行为与协议内部行为一致性）；协议的完备性（协议性质符合协议环境的各要求）；协议的自恢复性（任何出错状态都可自动恢复到常态）；有界性（不会发生缓冲区溢出之类的问题）等。我们用可达树对模型进行分析，可达树可以方便的分析系统的可达性、有界性、活性等各种动态特性。用关联矩阵来计算后继标识。写出图1的关联矩阵：由初始标识M0开始依次计算后继标识。M0=(110100000)T,t2发生时U(t2)=(010000000000000)T,所以M′=M0+CU=(110100000)T+(0-10000000)T=(100100000)T同理,可计算得各个变迁发生后的后继标识。画出协议可达图：分析可达图，可以看出，该模型不存在死锁现象，因为所有变迁都是活的，即此模型动态运行可达到的任何标识状态下都有变迁可启动并生成后继标识。而且协议循环可达。另外可以看到，变迁t2,t4,t6,t9,t11,t14,t15是我们不希望出现却现实存在的发生错误的变迁，在可达树中都可以自动循环恢复至常态。以上讨论的是单工协议。在大多数实际环境中，数据传输是双向的。实现全双工数据传输的方法是“捎带确认”，将确认帧附在发送的数据帧上，从而使得通信双方都可发送数据。我们将双向协议称为滑动窗口协议。由于实际的滑动窗口协议较为复杂，因此建立Petri网模型的状态空间比较大，更适合用高级Petri网进行建模及分析。2协议的验证以上通过pertri网对基本数据链路层协议进行了建模及改