实验-停止等待协议分析与协议模拟实现.doc

《实验-停止等待协议分析与协议模拟实现.doc》由会员分享，可在线阅读，更多相关《实验-停止等待协议分析与协议模拟实现.doc（9页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、精品文档，仅供学习与交流，如有侵权请联系网站删除实验 停止等待协议分析与协议模拟实现一、实验目的1）了解停止等待协议的原理2）掌握协议分析的方法和过程3）通过程序模拟停止等待协议的工作过程二、实验要求1）根据示例，编写停止等待协议的模拟程序，演示停止等待协议的工作过程。2）撰写实验报告。三、协议概述如果链路是理想的传输信道，1）所传送的任何数据既不会出差错也不会丢失；2）如果不管发送方以多快的速率发送数据，接收方总是来得及收下，并及时上交主机。如果存在这样的传输信道，数据链路层协议也是不需要的。信道不会出错，而且接收方缓存的容量为无限大而永远不会溢出；或接收速率与发送速率绝对精确相等。在上述两

2、个假定的情况下，数据链路层当然就不需要任何协议就可以保证数据传输的正确。这就是说，传输数据的信道是不可靠的（即不能保证所传的数据不产生差错），并且还需要对数据的发送端进行流量控制。在大多数协议中，流量控制是一组过程，这组过程是用来告诉发送方在等待接收方的应答信号之前最多可以传送多少数据。流量控制有两个要点：（1）数据流不能使接收方过载。任何接收设备都有一个处理输入数据的速率限制，并且存储输入数据的存储器容量也是有限的。接收设备必须在达到这些限制之前通知发送设备并且请求发送设备发送较少的数据帧或是暂停一会儿。在使用输入数据之前，需要对数据进行校验和处理，因此，每个接收设备都有一块存储器，叫做缓冲

3、区，用于存放未来得及处理的数据帧。如果缓冲区将满，接收方也必须能够通知发送方暂停传输，直到接收方又能接收数据。（2）应答。随着数据帧的到来，接收方对他们进行应答，可以每收到一帧给一个应答，也可以一次对若干帧进行应答。如果一个帧到达时已经被破坏，接收方发送一个否定应答帧（NAK）。在数据链路层，差错控制主要指错误检测和重传方法。在一个帧中出现任何一个错误，接收方就返回一个否定应答帧，出错的帧就被发送方重新传送。这个过程被称作自动重复请求(ARQ)。数据被重传的情况有三种：帧破坏、帧丢失和应答帧丢失。流量控制和差错控制是结合在一起实现的，共有两种实现流量控制和差错控制的技术：停止等待协议和滑动窗口

4、协议。【图解】【总结】使用的链路层传输控制协议发方：发送一个数据帧后，必须等待收方的确认帧才可以发送下一个数据帧；为防止发送的数据或该数据的确认帧丢失，发方内部设置一个定时器，当超过定时时间发方仍未收到确认帧时，发方重发该帧；为防止确认帧丢失而造成收方收到重复帧的情况，发方给每一个数据帧带上一个序列号。（1个比特位）收方：在收方接收错误时，收方发一否认帧，要求发方重发该帧；收方收到相同的两帧时，丢掉该数据帧并重发确认帧。【流程示意图】发送数据包1接收正确认ACK发送数据包2重发数据包2发送数据包3接收负确认NAK接收正确认ACK接收正确认ACK接收数据包1正确发送正确认ACK接收数据包2错误发

5、送负确认NAK接收数据包2正确发送正确认ACK接收数据包3正确发送正确认ACK发送方接收方发送数据包0接收正确认ACK1发送数据包1超时重传数据包1超时重传数据包1接收正确认ACK0接收数据包0正确发送正确认ACK1接收数据包1正确发送正确认ACK0接收数据包1正确(抛弃)发送正确认ACK0发送方接收方发送数据包0超时超时图a 停止等待协议的基本工作过程 图b 数据包的丢失和确认信息的丢失示意图四、协议分析可以用多种方法来表示一个有限状态机，对协议进行描述。以下是在某种假定条件下的协议分析。1）状态迁移图设甲、乙双方进行半双工通信，甲发信息帧，乙回送确认帧。双方约定采用停止等待协议，因此甲方仅

6、需用 1 比特来编号。下面将 0 号帧和 1 号帧分别记为 0 和 1 。当收到有差错的帧时，则丢弃此帧，同时不发任何应答帧。当收到无差错的帧但序号不正确时，要发确认帧，同时要丢弃此帧，不送主机。我们还假定收方在准备发送确认帧 ACK 时，暂不接收外面发来的帧。这样，我们就得出甲乙双方各自的有限状态机，如下图所示。图中椭圆形符号为状态符号，其右方数字为状态标号，椭圆形内的字表示状态的意义。带箭头的直线或弧线表示状态的变迁，而直线或弧线旁边的字代表自动机的输入事件。例如，甲方自动机中的 “发 0 ” 就是一个输入事件。图中在某些方面进行了一些简化。例如，当乙方处于 “期望收 0 ” 的状态时，若

7、收到无差错的 1 帧，仍然应当先进入 “准备发 ACK ” 状态，然后才发出 ACK 。但这里就将 “收 1 ” 与 “发 ACK ” 合并成为一个事件。其余部分不再详述。2）状态迁移表方法除状态转移图之外，还可用状态迁移表（又称为判决表）来表示自动机的工作。例如对甲方的自动机，可得出如下表所示的状态变迁表。表中的项目代表 “新的状态输出” 。例如在状态为 x1 时，若输入为 “发 0 ” ，则状态从 x1 转为 x2，同时输出为 “ 0 帧 ” 。当输出为 “” 时表示无输出。3）混合描述方法比较实用的办法是合并一些状态，即考虑一些次要的细节。例如，甲方的状态 1 和状态 2，状态 3和状态

8、 4 都可以合并，乙的状态 1 和状态 4，状态 2 和状态 3 也可进行合并。这样可以用 3 个字符 XYZ 表示整个系统的状态，其中 X0 或 1，对应于甲方准备发 0 或 1（包括发完后等待 ACK 的状态）；Y0 或 1，对应于乙方期望收到 0 或 1；Z0、l、A或，对应于信道上传送的是 0、1、ACK 或出现了差错（包括丢失）。这样，就可得出 图3-24 的有限状态机。在弧线（或直线）旁边注明的数字为状态变迁的标号，其意义也注明在 图3-24 的右方。假设系统一开始处在（000）状态。这表示甲发完 0，乙期望收到 0，而信道上传送的也是 0。在无差错的情况下，系统的状态仅在 4 个

9、状态中循环：（000）（01A）（111）（10A）（000） 。从理论上讲，应当共有 2 2 4 = 16 种不同的状态。去掉没有意义的组合后，还剩下 10 种状态，而导致状态变迁的输人事件共有 9 种（ 标号 0 8 ）。这种有限状态机可帮助我们检查协议是否正确。例如，检查一下乙方会不会连续将两个 0 号帧送交主机。这相当于检查一下会不会出现这种情况，即在两次出现状态变迁 1 之间不出现状态变迁 3 。仔细检查 图3-24 就可发现这种情况是不会发生的。同样方法也可用来排除连续将两个 1 号帧送交主机的可能。再检查一下会不会发生甲方连续改变状态 2 次（ 如从 0 到 1，再回到 0 ）而

10、乙方的状态未改变。这种情况相当于出现了未被发现的报文丢失。可以看出，这种情况也是不存在的。协议必须不出现死锁。死锁的出现是因为存在着这样的一种状态子集，其特点是：从这一子集内变迁到子集外是不可能的，而在这一子集内状态的变迁总是局限于子集内的几个状态。可以看出，图3-24 所示的自动机没有死锁现象。有限状态机模型的缺点就是当描述比较复杂的协议时，状态的数目将急剧增加，以致很难用它来清晰地描述协议。五、协议验证协议的 “验证” 一词包括了“validation”与“verification”，包括了协议语法和语义的验证。一般说来，协议的验证包括以下几个方面的内容： （l）可达性（reachabil

11、ity） 验证协议的各种可能状态之间的可达关系。如果从状态 A 到状态 B 的变迁不可能发生（直接或间接），则从状态 A 到状态 B 是不可达的。如果协议从初始状态到某个状态不可达，则表明协议有错误。 （2）死锁 最典型的死锁是协议中各实体都处于这样的一种等待状态，即只有在“某一事件”发生后才能做进一步的动作，但在该状态下，这个“某一事件”却不可能发生。死锁发生时，协议所处的状态称为死锁状态。 死锁的另一种形式是协议处于无限的死循环中，而没有别的事件可使协议从这一循环中解脱出来。例如，协议无限制地执行超时重发操作，但总是收不到对方的确认信息。这种形式的死锁称为活锁（livelock），表示整个

12、协议的状态还是在变化的，不过不能脱离这种死循环状态而已。（3）有界性检验协议的某些成分或参数（例如通道容量、窗口大小）是否有界。（4）完整性检验协议是否缺少应有的处理，以及有无非期待的接收（即错收）。（5）可恢复性或自同步性这是当出现差错后，协议能否在有限的步骤内返回到正常状态（包括初始态）下执行。（6）状态二义性一个进程在某一时刻只允许具有一个稳定状态。所谓稳定状态是指当通信双方的通道为空时的进程状态。若在某一时刻进程可以有不只一个的稳定状态，则称该进程的状态为二义状态。（7）动作序列将协议的动作按执行顺序组合起来，即构成协议的动作序列。协议的动作序列集合又称为协议的语言。检查协议的动作序列

13、，可以验证协议有无错误动作或无用动作。（8）通道溢出检查当通道中的数据已达到通道的最大容量后，是否有某个进程仍然试图向通道中放入数据。六、参考代码如下为Java参考代码1）Sender.javaimport java.io.*;import .*;public class Sender extends Threadprivate String address = 127.0.0.1; private int port = 9878; public Sender() Socket client = null ; for(int i=0;i10; i+) client = new Socket()

14、 ; Msg data = new Msg(i%2); InetSocketAddress isa = new InetSocketAddress(this.address,this.port); try client.connect(isa,10000); ObjectOutputStream out = new ObjectOutputStream(client.getOutputStream(); out.writeObject(data); System.out.println(发送分组 +data.getN_msg(); BufferedReader br = new Buffere

15、dReader(new InputStreamReader(client.getInputStream(); String str = br.readLine(); if(str.equals(resend1) System.out.println(分组丢失，重发); i-; out.flush(); out.close(); out = null ; data = null ; client.close();client = null ; continue; else if(str.equals(resend2) System.out.println(ACK丢失，重发); i-; out.f

16、lush(); out.close(); out = null ; data = null ; client.close();client = null ; continue; else System.out.println(n+接收ACK+data.getN_msg()+ 发送分组+(data.getN_msg()+1)%2); out.flush(); out.close(); out = null ; data = null ; client.close();client = null ; catch(java.io.IOException e) System.out.println(S

17、ocket error! ); System.out.println(IOException : + e.toString(); try this.sleep(8000); catch (InterruptedException e) e.printStackTrace();public static void main(String args) new Sender();2）Recver.javaimport java.io.*;import .*;public class Recver extends Thread private boolean OutServer = false; pr

18、ivate static ServerSocket server ; private static int ServerPort = 9878; public static void main(String args) (new Recver().start();public Recver() try server = new ServerSocket(ServerPort); catch(java.io.IOException e) System.out.println(Socket啟動有問題 ! ); System.out.println(IOException : + e.toStrin

19、g(); public void run() Socket socket; ObjectInputStream in ; System.out.println(伺服器已啟動 ! ); while(!OutServer) socket = null; try synchronized(server) socket = server.accept(); socket.setSoTimeout(15000); in = new ObjectInputStream(socket.getInputStream(); Msg data = (Msg)in.readObject(); System.out.

20、println(发送端正在发送的内容+data.getN_msg()+ 状态：+data.getInfo(); if(data.getInfo().equals(losePackage) System.out.println(分组丢失); DataOutputStream dos = new DataOutputStream(socket.getOutputStream(); dos.writeBytes(resend1+n); dos.close(); else if(data.getInfo().equals(loseAck) System.out.println(ACK丢失); Data

21、OutputStream dos = new DataOutputStream(socket.getOutputStream(); dos.writeBytes(resend2+n); dos.close(); else System.out.println(接收分组 +data.getN_msg()+ 发送ACK +data.getN_msg(); DataOutputStream dos = new DataOutputStream(socket.getOutputStream(); dos.writeBytes(ok+n); dos.close(); System.out.println

22、(); in.close(); in = null ; socket.close(); catch(java.io.IOException e) System.out.println(Socket error ! ); System.out.println(IOException : + e.toString(); catch(java.lang.ClassNotFoundException e) System.out.println(ClassNotFoundException : + e.toString(); 3）Msg.javaimport java.io.Serializable;i

23、mport java.util.*;public class Msg implements Serializableprivate int n_msg;private String info;private Random random; private int rdNum;public Msg(int n_msg) this.n_msg = n_msg;MsgState();public void MsgState()/用于模拟分组丢失，ACK丢失等情况random = new Random();rdNum = Math.abs(random.nextInt()%100;if (rdNum80

24、) info =loseAck;else info =noError;public int getN_msg() return n_msg;public void setN_msg(int n_msg) this.n_msg = n_msg;public String getInfo() return info;public void setInfo(String info) this.info = info;下午13：0017：00B实行不定时工作制的员工，在保证完成甲方工作任务情况下，经公司同意,可自行安排工作和休息时间。312打卡制度3.1.2.1公司实行上、下班指纹录入打卡制度。全体员

25、工都必须自觉遵守工作时间，实行不定时工作制的员工不必打卡。3.1.2.2打卡次数：一日两次，即早上上班打卡一次，下午下班打卡一次。3.1.2.3打卡时间：打卡时间为上班到岗时间和下班离岗时间； 3.1.2.4因公外出不能打卡：因公外出不能打卡应填写外勤登记表,注明外出日期、事由、外勤起止时间。因公外出需事先申请，如因特殊情况不能事先申请，应在事毕到岗当日完成申请、审批手续，否则按旷工处理。因停电、卡钟（工卡）故障未打卡的员工，上班前、下班后要及时到部门考勤员处填写未打卡补签申请表，由直接主管签字证明当日的出勤状况，报部门经理、人力资源部批准后，月底由部门考勤员据此上报考勤。上述情况考勤由各部门

26、或分公司和项目文员协助人力资源部进行管理。3.1.2.5手工考勤制度3.1.2.6手工考勤制申请：由于工作性质，员工无法正常打卡（如外围人员、出差），可由各部门提出人员名单，经主管副总批准后，报人力资源部审批备案。3.1.2.7参与手工考勤的员工，需由其主管部门的部门考勤员(文员)或部门指定人员进行考勤管理，并于每月26日前向人力资源部递交考勤报表。3.1.2.8参与手工考勤的员工如有请假情况发生，应遵守相关请、休假制度，如实填报相关表单。3.1.2.9 外派员工在外派工作期间的考勤,需在外派公司打卡记录;如遇中途出差,持出差证明,出差期间的考勤在出差地所在公司打卡记录;3.2加班管理3.2.

27、1定义加班是指员工在节假日或公司规定的休息日仍照常工作的情况。A现场管理人员和劳务人员的加班应严格控制，各部门应按月工时标准，合理安排工作班次。部门经理要严格审批员工排班表，保证员工有效工时达到要求。凡是达到月工时标准的，应扣减员工本人的存休或工资；对超出月工时标准的，应说明理由，报主管副总和人力资源部审批。 B因员工月薪工资中的补贴已包括延时工作补贴，所以延时工作在4小时（不含）以下的，不再另计加班工资。因工作需要，一般员工延时工作4小时至8小时可申报加班半天，超过8小时可申报加班1天。对主管(含)以上管理人员，一般情况下延时工作不计加班，因特殊情况经总经理以上领导批准的延时工作，可按以上标

28、准计加班。3.2.2.2员工加班应提前申请，事先填写加班申请表，因无法确定加班工时的，应在本次加班完成后3个工作日内补填加班申请表。加班申请表经部门经理同意，主管副总经理审核报总经理批准后有效。加班申请表必须事前当月内上报有效，如遇特殊情况，也必须在一周内上报至总经理批准。如未履行上述程序，视为乙方自愿加班。3.2.2.3员工加班，也应按规定打卡，没有打卡记录的加班，公司不予承认；有打卡记录但无公司总经理批准的加班，公司不予承认加班。3.2.2.4原则上，参加公司组织的各种培训、集体活动不计加班。3.2.2.5加班工资的补偿：员工在排班休息日的加班，可以以倒休形式安排补休。原则上，员工加班以倒

29、休形式补休的，公司将根据工作需要统一安排在春节前后补休。加班可按1：1的比例冲抵病、事假。3.2.3加班的申请、审批、确认流程3.2.3.1加班申请表在各部门文员处领取，加班统计周期为上月26日至本月25日。3.2.3.2员工加班也要按规定打卡，没有打卡记录的加班，公司不予承认。各部门的考勤员(文员)负责加班申请表的保管及加班申报。员工加班应提前申请，事先填写加班申请表加班前到部门考勤员(文员)处领取加班申请表，加班申请表经项目管理中心或部门经理同意，主管副总审核，总经理签字批准后有效。填写并履行完审批手续后交由部门考勤员(文员)保管。3.2.3.3部门考勤员（文员）负责检查、复核确认考勤记录

30、的真实有效性并在每月27日汇总交人力资源部，逾期未交的加班记录公司不予承认。“耶”随着一阵欢呼声及掌声，我们的指挥走上舞台，领下“红歌比赛一等奖”的奖状。 你可别以为这只是一个偶然的画面，要知道，这次的成功可是用我们的汗水所换来的。 早在两个月以前，我们就接到了要举办“红歌比赛”的通知。本来时间还早，其他班对此还不大重视，可我们班的班主任似乎一刻也不能等，不仅给我们排好了班歌，还让我们在每天早晨、下午练歌，让我们做着充足的准备迎接挑战。有一次，我们班主任还特的请来了一位音乐老师来指导我们，特别准备了两节课来练歌。当然，我们也不负众望，练得十分认真：有的脸涨红了;有的嗓子练哑了;有的甚至还在这严

31、寒之际，唱出了汗水，渗透了衣裳。离红歌比赛还有一两周了。我们班主任又给我们编了队形，还给我们制出了道具：整个道具呈圆形，飞盘状，一面是咱们班“北山雄鹰”的班徽，一面是代表咱们六班每一棵“小树苗”的绿叶。你可别小看它，它不仅是我们比赛的制胜“法宝”，而且，为了给我们班69名同学每人一个，我们班的几位同学硬是忍冻挨饿，直至晚上十点半左右，才完成了那69个道具。还有几天就要比赛了，同学们抓的更紧了。在一次训练时，一个调皮的同学问道：“老师，你说我们会拿一等奖吗?”这句话打破了紧张的练习，大家都把目光投向班主任那儿。班主任笑着说：“当然啦!我们付出了这么多，如果连我们也拿不到第一，那恐怕就没有人敢去夺第一了。”班主任的一番话有使我们信心大增，再次点燃了我们心中的斗志，想着比赛做着最后的冲刺。比赛当天，我们班除了领唱和指挥，其余人员全部穿着统一色的校服，配上鲜艳的红领巾，再加上耀眼的班徽，给人一种“不拿第一，誓不罢休”的感觉。比赛时，我们忘却了练习时的辛苦，忘掉了站在舞台上的紧张，只是注视着指挥的每一个手势、每一个动作，满怀激情地唱出那嘹亮的歌声，完全沉浸在这优美的旋律里。知道主持人说出：“红歌比赛一等奖的获得者是初20级6班!”便出现了开头的那一幕。成功的花，人们只惊慕她现时的明艳!然而当初她的芽儿，渗透了奋斗的泪泉，洒遍了牺牲的血雨。【精品文档】第 9 页