余 建，刘孙发

（三明学院 现代教育技术中心，三明 福建 365004）

许多高校校园网经过多年的建设、升级与改造后，基本上都完成校园网的基础建设。由于早期电脑较少，一般高校都采用静态IP来分配校园网的IP。伴随着近年来校园网组网规模的逐步扩大和电脑数量的激增，使用手工方法为师生分配IP地址的做法已经越来越不可取。网络管理员大多会通过带有DHCP功能的服务器为工作站自动分配IP地址，从而提高网络管理效率；当用户通过身份认证系统在登录校园网系统时，系统总有一段逗留的时间去获取动态IP，特别是在高峰时间段用户可能会等待很长一段时间或出现获取不到IP或IP冲突的情况发生。如何更好的解决这个问题，同时对DHCP分配IP时能更深一层的研究，本文在结合DHCP服务器的原理下提出了一种带有闭合并联排队信息算法的DHCP IP分配方法。

1 DHCP服务器原理

在整个DHCP服务器为DHCP客户端初次提供IP地址自动分配过程中，一共经过了以下四个阶段：发现阶段 （DHCP客户端在网络中广播发送DHCP DISCOVER请求报文，发现DHCP服务器，请求IP地址租约）、提供阶段（DHCP服务器通过DHCP OFFER报文向DHCP客户端提供IP地址预分配）、选择阶段（DHCP客户端通过DHCP REQUEST报文确认选择第一个DHCP服务器为它提供IP地址自动分配服务）和确认阶段（被选择的DHCP服务器通过DHCP ACK报文把在DHCP OFFER报文中准备的IP地址租约给对应DHCP客户端）。在DHCP客户端在获得了一个IP地址以后，就可以发送一个免费ARP请求探测网络中是否还有其它主机使用IP地址，来避免由于DHCP服务器地址池重叠而引发的IP冲突[1]。

实际上当DHCP服务器在面对每天那些难以计数的IP服务请求的时候，网络上的IP分配服务器就像一个排队系统，IP分配服务请求就像是一个个的IP，处理请求的DHCP服务器就是服务台。当在某一时间点或一个时间区域内，服务请求的数量达到了高峰点，在这个高峰时期，服务器就处于高负载工作状态[2]，如图1所示。在高负载的状态下，大家都希望服务器的工作性能有较高效率的表现，并保持较高的数据吞吐量。因此，为了解决这个问题，首先就要用排队论的方法，对DHCP服务器在分配IP过程中的系统性能进行建模和分析。

图1 校园网中DHCPIP登录情况表Figure 1 DHCPIPlogin in campus network

2 传统排队理论模型类别

DHCP中的IP分配一般属于IP分配系统中的无形排队，当某网段的IP被占用时，用户要获取的IP就得选择在系统中排队等待分配，而这种等待是不需要IP地址池中等待的[3]。我们用M/Y/Z/A/B/C来表示IP地址池中的排队队型，其中，M表示相邻IP到达的时间间隔所服从的分布，Y表示系统服务时间所服从的分布，Z为服务器建立IP网段数量，A为IP池容量，B表示IP池的数量，C为服务规则。通常用P表示泊松分布，E表示爱尔朗分布。

传统的M/M/1排队系统模型，是指用户IP到达和服务时服从泊松分布，DHCP服务器中IP的VLAN数为1的排队模型，即IP尾数从1排到254，这是IP排队模型的基础。我们把IP排队的过程看成是一种符合生物生灭的过程，它也是一种简当并广泛的随机过程。在IP地址池中，这些即将获取IP的到达看作“生”，用户退出网络，并重新释放出IP地址后看作是“灭”，校园网中的用户采用DHCP的方式来获取自身的IP，就是通过生灭过程来实现的[4]。我们假设IP到达的分布参数为，服务时间分布参数为，则根据生灭法则，同一时间内只能有一个IP到达和离开，IP初始的排队效率值算法如下：

由此可得出系统中IP的平稳分配状态，排队系统在稳定状态下系统中有IP数为n的概率p0=1-p，pn=pn（1-pn），n≥ 1，p＜1。p0=λ/μ,我们一般称之为服务强度系数。同时可以得出：

IP在系统中的排队时间Wq为：

3 闭合IP排队理论模型参数

现实意义中，由于校园IP分为了许多个不同的VALN和IP段，相当于每个VLAN都是一个服务站。如直接按照标准的M/M/1排队系统模型来分析校园网中的IP分配,可能得到的结果会存在很大的误差。在本文中，我们假设一个闭合排队网络由N个服务站组成，每个IP地址池都有自己的队列，都是此排队网络中的一个结点，其中第i个服务站也称为第i个结点(1≤i≤N)包含的相互独立、相同的(即服务时间概率分布相同，平均服务率相同)服务台数量是mi个，是一个M/M/mi型排队结点.此闭合排队网络共有K个IP在其中循环接受服务.闭合排队算法的计算原理是基于稳态时2个简单关系，即排队网络中每一个结点的IP的平均队长是此结点流量的函数[5]；闭合排队系统中各节点处的IP队长之和等于网络内IP总数.如图2所示。

图2 DHCP服务的并联闭合排队模型Figure 2 The parallel closed queuing model for DHCPservices

根据上面提到的DHCP排队论的知识,由图2所示的排队通信过程可抽象为图3所示的模型。

图3 带排队信息的DHCP服务系统流程图Figure 3 DHCPservice system flow chart with queuing information

并联闭合排队网络的第1个关系可表述为

系统中最多只能容下K个IP（等待位置只有K-1个），λn为排队网络中第i结点处IP的平均队长；λi为通过第i个结点的IP流量；i为排队网络中的结点IP编号，i=l，2，3，…，K。

图4 随机变量λn生灭图Figure 4 Random variableλn birth and death graph

4 基于改进的闭合排队论IP分配算法

假设系统能达到闭合状态，对一个新分配的IP来说。设到达过程是一个参数为λ的Poisson过程[6]，如图3所示。长度t为的时间内到达k个呼叫的概率服从Poisson分布，

定义1 系统空闲的概率

定义2 系统有n个IP的概率（IP的损失率）

定义3 IP有效到达率

IP损失率pk，IP可进入系统的概率1-pk

定义4系统平均队长（平均IP数）

定义5 系统中IP平均排队队长（平均等待服务的IP数）

定义6 平均逗留时间

定义7平均等待时间

定义8 IP在系统中的逗留时间，当K=1时，为单服务地址址池损失系统

5 校园网中的IP数据实验仿真结果与分析

实验采用MATLAB7仿真软件平台，硬件平台为Inter I7处理器，8G DDR3的PC机。在实验中，设到达过程是一个参数为λ的Poisson过程，则长度为t的时间内到达k个呼叫的概率服从Poisson分布，即,其中 λ＞0 为一常数，表示了平均到达率或Poisson呼叫流的强度。

1、服务模式

设每个呼叫的持续时间为τi，服从参数为μ的负指数分布，即其分布函数为 P｛X ＜t｝=1-e-μt，t≥ 0

2、服务规则

先进先服务的规则（FIFO）

3、理论分析结果

在该M/M/mi系统中，设则稳态时的平均等待队长为的平均等待时间为我们根据校园网IP登录的值，输入仿真的IP数，计算第1个IP的离开时间,同时判断闭合排队系统是否接纳第i个IP，计算第i个IP的等待时间、离开时间、标示位。并输出仿真的结果。

实验结果截图如下（K分别为1 000、100 000）：

图5 SimTotal分别为1 000的排队变化关系图Figure 5 A queuing change relationship diagram of 1 000 SimTotal,respectively

图6 SimTotal分别为1 000 000的排队变化关系图Figure 6 A queuing change relationship diagram of 1 000 000 SimTotal,respectively

表1 二组仿真数据结果比较Table 1 Comparison of the results of the two groups of simulation data

由图表1所示，当仿真的IP数为1000时，平均等待时间、平均排队时间、平均IP数、平均等待队长的平均值分别为：2.003 00、0.891 98、0.801 16、0.356 78。而当仿真IP总数=1 000 000时，平均等待时间、平均排队时间、平均IP数、平均等待队长的平均值分别为：2.001 62、0.890 6、0.800 84、0.356 33。综上，可以看出越着IP数的不断增长，排队时间变化并不太，说明并发闭合排队信息算法对系统有着很强的稳定性。

3 结束语

运用经典成熟的排队论来分析校园网中的DHCP IP排队方案，同时采用更多更准确的仿真数据分析，得出更符合实际的排队模型，为我们设计具有高质量和高效率的IP地址服务器分配方案，并由此来分析服务器的负载率提供有价值的依据。从科学的角度看，M/M/mi排队理论模型还有待进一步研究，以使该模型能更好地反映出DHCP服务器在分配IP时的各种性能特征，从而实现服务器在忙时的服务质量与效率的平衡。

[1]徐坚.利用DHCP中继代理实现跨子网服务 [J].电脑知识与技术，2011（3）：526.

[2]汤红军.DHCP中继代理在校园网中的应用分析研究 [J].计算机系统应用，2008(4)：100.

[3]李颖利，赵相珺，吴杰仁.排队论数学模型在电子分诊系统中的应用体会[J].医疗卫生装备，2009,30(10)：36-39.

[4]刘猛，孙冬石，于绍政.基于新型排队论的网络订餐服务优化研究[J].物流工程与管理.2017(5)：115-117.

[5]于森,宫俊杰,唐加福,等.带排队信息提示的呼叫中心人力资源分配方法[J].东北大学学报（自然科学版），2014(1)：2.

[6]张继文,王青.闭合排队网络的扩展求和算法及其应用[J].煤炭学报，2008(11)：1311.