山东大学计算机网络实验报告

901901J顼*，务SHANDONGUNIVERSITY计算机网络试验报告学院：计算机科学与技术学院班级：13计基地目录TOC\o"1-5"\h\z\o"CurrentDocument"一、实验简述3\o"CurrentDocument"二、实验内容3\o"CurrentDocument"实验一：双队列模型3\o"CurrentDocument"一、实验模型3\o"CurrentDocument"二、具体实现4\o"CurrentDocument"三、结果展示6\o"CurrentDocument"实验二：802.11无线竞争模型7\o"CurrentDocument"一、实验模型7\o"CurrentDocument"二、具体实现8\o"CurrentDocument"三、实验结果8\o"CurrentDocument"图表结果8\o"CurrentDocument"数据结果10\o"CurrentDocument"三、实验感想10\o"CurrentDocument"一、双队列单服务器10\o"CurrentDocument"二、802.11无限竞争模型11

_、实验简述Fl_、实验简述Fl实验一要求采用尽量公平的调度算法，实现一个服务器服务2个队列的功能。且满足以下条件：到达包数是泊松过程(Poissonprocess)；服务时间是指数分布(exponentiallydistributed)；只有一部服务器(server)；队列长度无限制；可加入队列的包数为无限。实验二基于802.11协议采用二进制指数回退算法，没有中央控制器的调度算法实现对五个站的调度机制。要求尽可能达到公平。二、实验内容实验一：双队列模型一、实验模型本次计算机网络实验主要是关于服务器处理包的过程模拟，其中一个重要的基础排队模型是M/M/1排队模型。M/M/1排队模型是一种单一服务器(single-server)的排队模型，有以下主要特点：1.到达人数是泊松过程(Poissonprocess)2.服务时间是指数分布(exponentiallydistributed)3.只有一台服务器(server)队列长度无限制可加入队列的人数为无限M/M/1排队模型在任何状态下，只有两种事情可能发生：有人加入队列。如果模型在状态k,它会以速率入进入状态k+1有人离开队列。如果模型在状态k(k不等于0),它会以速率巨进入状态k-1二、具体实现赤字轮询算法赤字轮询算法引入赤字的概念，即在较长时间统计平均意义上平衡各条流所获得的吞吐量。因为各流之间不同业务造成的数据包大小的差异以及各流内部数据包大小的不同都可能造成在一个轮询周期内各虚拟队列所发送的字节数具有较大偏差。DRR算法为每个虚拟队列维护一个赤字字节数，使得本次轮询未能发送的字节会在下一次甚至下几次轮询过程中得到补偿。具体过程如下：将有数据包等待发送的虚拟队列存放于一个链表中，轮询过程即访问链表表头上的队列，访问时先将队列的当前赤字值(deficitcounter)加上一个预先分配的值(表示每次轮询允许发送的字节数)，将它作为本次轮询所能发送的最大字节数Q,然后服务该队列。服务队列时先判断队头上的数据包长度(Byte)是否小于Q,如果是，则服务后令Q减去Byte并继续此循环过程直至Byte>Q,将最后得到的Q值赋予deficitcounter,并将该队列从数组中取出插入数组尾部，接着访问数组中的下一个队列。若从虚拟队列中取出数据包后队列为空，则将该虚拟队列从数组中删除。为了使结果更加精确，可以在电脑承受能力范围内适当增加发送包的个数。仿真与计算为了模拟队列长度分布，采用每个队列长度所占时间除以总时间来表示。队列长度发生变化的原因是有包到达队列或离开队列，因此我们可定义一个变量count并初始化为0，在每次包到达时count+1，每个包离开时count-1，在两个离开或到达事件之间队列中包的个数是不变的，这时就为包的个数为count的队列长度数组的时间加上这个时间间隔，依此继续得到所有的队列中包的个数为某个值的所占有的所有时间，再用该时间除以总时间得到队列长度为x时概率，最后可得到队列长度＞=x时的概率分布。为了模拟等待时间分布，可以根据每个包的到达队列时间和离开队列时间来获得等待时间，为了使画出的图更加精确，增大间距，每0.1s为一个单位。统计等待时间在0-0.1S之间、0.1-0.2s之间…的包的个数，用每0.1s包的个数除以总个数得到在某个0.1s时间间隔的概率，最后得到时间〉二某时间的概率。总之，采用数组来存储包的到达时间、离开队列时间、服务完成时间、每个包的大小等。到达时间通过包发送的时间间隔来产生，时间间隔通过泊松函数产生。根据调度算法来获得包的离开队列时间，服务完成时间可根据离开队列的时间加上服务器处理包所用的时间，而服务器处理包所用时间则由包的大小除以服务器的服务速率获得。当我们获得了每个包的状态后，便可计算出队列长度分布和等待时间分布了。三、结果展示1.表结果：1.表结果：分别将两个队列的队列长度分布和等待时间分布画在一幅图中进行比较，看是否是调度公平。测试包个数为108结果如下：（1）队列分布：下方红线为队列1等待队列分布，上方蓝线为队列2等待队列分布。图表40，50分别代表队列每秒发送包数。率概度长列队此于等于大率概度长列队此于等于大（2）时间分布下方红线为队列1等待时间分布，上方蓝线为队列1等待时间分布。

率概度长间时此于等于大等待时间长度概率分布10010-110一210一310-410-510一率概度长间时此于等于大等待时间长度概率分布10010-110一210一310-410-510一610一7020406080100120140160180等待时间长度用五个站来模拟802.11MAC子层协议。首先，看一下什么是802.11。802.11协议组是国际电工电子工程学会(IEEE)为无线局域网络制定的标准。为了避免冲突碰撞，采用的协议为CSMA/CA协议，即采用二进制指数后退的方法来解决冲突问题。该方法是在第i次冲突后，从〖0〜2〗E-1之间随机选择一个数，然后等待这么多个时间槽。然而，达到10次冲突之后，随机数的选择区间被固定在最大值1023，以后不再增加，在16次冲突之后，控制器放弃努力，并给计算机返回一个失败报告。比如：第一次冲突后，从0〜1之间随机选择一个数然后作为该站等待的时间槽数。虽然，CSMA/CA和回归都能解决碰撞的问题，不过，在功能上，它们是有差别的。CSMA/CA是一种“竞争"(contention)通信协议，它倾听WLAN网络，避免碰撞发生。它和传统的CSMA/CD(被以太网络使用)不同，CSMA/CD是在碰撞发生之后,才起来处理后续的传送作业°CSMA/CA则是防患未然，所以比较有助于网络通信。因为它在任何真正的数据被传送之前，会先在网络上广(broadcast)一个信号，侦听是否有碰撞发生，同时告诉其它装置不要广播。二具体实现首先创建了新的结构--站，然后创建5个站。然后令总包数为10000000(107),设置固定的参数timeslot为一个时间单位。当一个站需要发包时，采用p坚持的方法，在0〜N-1之间随机选择个数作为该包开始发包时timeslot值,等到对应的timeslot值时试图发送包，若同时有其他包在同一时间发送，产生碰撞，该包返回到站中同时该包要进行二进制回退选择自己再次发包的时间；如不产生碰撞，则成功发送，根据包的大小决定包发送完成的时间并返回ack给站,在包处理的过程中其他包不能发送。最后，若产生16次冲突时，抛弃此包。三、实验结果1.图表结果⑴等待队列概率分布，如下图所示。率概量数包务服此于等于大等待时间长度分布，如下图所示率概间时待等此于等于大2.数据结果（1）服务器服务数据初始数据运行结果竞争信道站数（个）5总包数（个）108平均间隔时间（秒）15.5总时间（秒）30993668.7200平均服务器响应时间（秒）1.8吞吐率（个/单位时间）3.226465时间槽0.07碰撞浪费时间概率0.00888（2）五个站服务数据发送总包数（个）平均等待时间（秒）平均等待包个数（个）信道利用率站1200043730.80476319.9004300.580357站2200007330.62091819.7787390.580357站3200050730.87260519.9449050.580357站4200098730.88730619.9593600.580357站5199799630.78283919.8622560.580357三、实验感想一、双队列单服务器首先选择数组作为模拟结构，将队列中每个包的到达队列时间、离开队列时间、服务完成时间放入相应的数组中。然后就是选择调度机制来调度包的发送。算法对结果的影响是至关重要的，决定了队列调度的公平程度。这里采用了带赤字的轮转制度来进行模拟，在