山东大学计算机网络实验报告
计算机网络试验报告
学院：计算机科学与技术学院
班级：13计基地
目录
一、实验简述 (3)
二、实验内容 (3)
实验一：双队列模型 (3)
一、实验模型 (3)
二、具体实现 (3)
三、结果展示 (4)
实验二：802.11 无线竞争模型 (6)
一、实验模型 (6)
二、具体实现 (6)
三、实验结果 (6)
1.图表结果 (6)
2.数据结果 (8)
三、实验感想 (8)
一、双队列单服务器 (8)
二、802.11无限竞争模型 (8)
一、实验简述
实验一要求采用尽量公平的调度算法，实现一个服务器服务2个队列的功能。且满足以下条件：到达包数是泊松过程（Poisson process）；服务时间是指数分布（exponentially distributed）；只有一部服务器（server）；队列长度无限制；可加入队列的包数为无限。
实验二基于802.11协议采用二进制指数回退算法，没有中央控制器的调度算法实现对五个站的调度机制。要求尽可能达到公平。
二、实验内容
实验一：双队列模型
一、实验模型
本次计算机网络实验主要是关于服务器处理包的过程模拟，其中一个重要的基础排队模型是M/M/1 排队模型。M/M/1排队模型是一种单一服务器（single-server）的排队模型，有以下主要特点：
1.到达人数是泊松过程(Poisson process)
2.服务时间是指数分布(exponentially distributed)
3.只有一台服务器(server)
4.队列长度无限制
5.可加入队列的人数为无限
M/M/1排队模型在任何状态下，只有两种事情可能发生：
1.有人加入队列。如果模型在状态k，它会以速率λ进入状态k + 1
2.有人离开队列。如果模型在状态k（k不等于0），它会以速率μ进入状
态k -1
二、具体实现
1.赤字轮询算法
赤字轮询算法引入赤字的概念, 即在较长时间统计平均意义上平衡各条流所获得的吞吐量。因为各流之间不同业务造成的数据包大小的差异以及各流内部数据包大小的不同都可能造成在一个轮询周期内各虚拟队列所发送的字节数具有较大偏差。 DRR算法为每个虚拟队列维护一个赤字字节数, 使得本次轮询未能发送的字节会在下一次甚至下几次轮询过程中得到补偿。具体过程如下：将有
数据包等待发送的虚拟队列存放于一个链表中, 轮询过程即访问链表表头上的队列, 访问时先将队列的当前赤字值（deficitcounter）加上一个预先分配的值（表示每次轮询允许发送的字节数）,将它作为本次轮询所能发送的最大字节数Q, 然后服务该队列。服务队列时先判断队头上的数据包长度(Byte)是否小于Q, 如果是, 则服务后令 Q减去 Byte并继续此循环过程直至Byte>Q, 将最后得到的 Q值赋予 deficitcounter, 并将该队列从数组中取出插入数组尾部, 接
着访问数组中的下一个队列。若从虚拟队列中取出数据包后队列为空, 则将该虚拟队列从数组中删除。为了使结果更加精确，可以在电脑承受能力范围内适当增加发送包的个数。
2.仿真与计算
为了模拟队列长度分布，采用每个队列长度所占时间除以总时间来表示。队列长度发生变化的原因是有包到达队列或离开队列，因此我们可定义一个变量count并初始化为0，在每次包到达时count+1，每个包离开时count-1，在两个离开或到达事件之间队列中包的个数是不变的，这时就为包的个数为count的队列长度数组的时间加上这个时间间隔，依此继续得到所有的队列中包的个数为某个值的所占有的所有时间，再用该时间除以总时间得到队列长度为x时概率，最后可得到队列长度>=x时的概率分布。
为了模拟等待时间分布，可以根据每个包的到达队列时间和离开队列时间来获得等待时间，为了使画出的图更加精确，增大间距，每0.1s为一个单位。统计等待时间在0-0.1s之间、0.1-0.2s之间…的包的个数，用每0.1s包的个数除以总个数得到在某个0.1s时间间隔的概率，最后得到时间>=某时间的概率。
总之，采用数组来存储包的到达时间、离开队列时间、服务完成时间、每个包的大小等。到达时间通过包发送的时间间隔来产生，时间间隔通过泊松函数产生。根据调度算法来获得包的离开队列时间，服务完成时间可根据离开队列的时间加上服务器处理包所用的时间，而服务器处理包所用时间则由包的大小除以服务器的服务速率获得。当我们获得了每个包的状态后，便可计算出队列长度分布和等待时间分布了。
三、结果展示
1.图表结果：
分别将两个队列的队列长度分布和等待时间分布画在一幅图中进行比较，看是否是调度公平。测试包个数为108，结果如下:
（1）队列分布：
下方红线为队列1等待队列分布，上方蓝线为队列2等待队列分布。图表40，50分别代表队列每秒发送包数。
（2）时间分布
下方红线为队列1等待时间分布，上方蓝线为队列1等待时间分布。
实验二：802.11 无线竞争模型
一、实验模型
用五个站来模拟802.11MAC子层协议。首先，看一下什么是802.11。
802.11协议组是国际电工电子工程学会(IEEE)为无线局域网络制定的标准。为了避免冲突碰撞，采用的协议为CSMA/CA协议，即采用二进制指数后退的方法来解决冲突问题。该方法是在第i次冲突后，从〖0~2〗^i-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.图表结果
（1）等待队列概率分布，如下图所示。
（2）等待时间长度分布，如下图所示
2.数据结果
三、实验感想
一、双队列单服务器
首先选择数组作为模拟结构，将队列中每个包的到达队列时间、离开队列时间、服务完成时间放入相应的数组中。然后就是选择调度机制来调度包的发送。算法对结果的影响是至关重要的，决定了队列调度的公平程度。这里采用了带赤字的轮转制度来进行模拟，在编码过程中，为了优化方法，如果一个队列中还有赤字但是队列中没有包，这时将赤字清零并转去执行另外一个队列。通过更改后，程序得到了优化。
二、802.11无限竞争模型
同样，首先选择数组作为模拟结构存储各类数据。然后就是调度机制，这里的调度机制采用了二进制指数回退方法，在编写该方法过程中，要很多细节问题需要注意，比如当一个包连续碰撞10次后，产生的时间槽的随机数就为0-1023不再改变，当碰撞16次后，放弃该包，以此来提高模拟精确度。