校園網中基于一種并發閉合排隊信息算法的DHCP IP分配方法

余 建，劉孫發

（三明學院 現代教育技術中心，三明 福建 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.