縮小落差：大型無線網路中 DHCP 效能的實證研究

原題： Squeezing the Gap: An Empirical Study on DHCP Performance in a Large-scale Wireless Network
作者： Haibo Wang、Jessie Hui Wang、Jilong Wang、Weizhen Dang、Jing’an Xue、Fenghua Li、Jinzhe Shan
原文： 2020TON_DHCP.pdf

翻譯說明：本譯文依使用者提供的 17 頁 PDF，涵蓋摘要、正文 I–VIII、參考文獻、作者簡介及附錄 A–E。保留原文的引文編號、公式編號與圖表編號。圖表的中文圖說及標籤對照列於各節，原圖可依標示的 PDF 頁碼查閱；圖像本身不重繪。文中的研究結果、軟體預設行為與作者職稱均依原論文撰寫時的描述翻譯。

摘要

動態主機設定協定（Dynamic Host Configuration Protocol，DHCP）廣泛用於動態分配 IP 位址給使用者。然而，由於對 DHCP 的行為與效能了解不足，要在大型無線網路中適當設定租約時間，並將 IP 位址合理劃分至各個位址池，是一項挑戰。本文在 T 大學的無線網路（TWLAN）中，針對 DHCP 的行為與效能進行了已知規模最大的量測。

我們發現，DHCP 的效能遠不令人滿意：（1）未通過身分驗證的裝置在尖峰時段造成 25% 的位址浪費。（2）在目前的位址劃分策略下，各位址池的使用率差異很大。（3）平均而言，裝置在租約時間的 67% 期間內不會產生流量。同時，我們觀察到不同地點、不同作業系統的裝置呈現不同的上線模式。統一設定租約時間可能導致位址使用效率低落。

為了解決這些問題，我們提出一種納入身分驗證資訊與上線模式的新租約策略。結果顯示，該策略優於三種當時最先進的基準方法，在未顯著增加 DHCP 伺服器負載的情況下，將已分配位址數減少 24%，並將平均總租約時間減少 17%。此外，我們進一步提出自適應位址劃分策略，以平衡各位址池的位址使用率。這項策略可與新租約策略同時部署，並降低位址耗盡的風險。

索引詞： DHCP、量測、效能、最佳化。

I. 緒論

動態主機設定協定（DHCP）廣泛用於在裝置連上網路時，動態分配 IP 位址 [1]。近年來，IP 位址已接近耗盡，因此多數企業網路可使用的 IP 位址相當有限 [2–4]。相較於手動設定，DHCP 能夠更有效率且更有彈性地管理 IP 位址。

然而，日益複雜的無線網路環境也為 DHCP 帶來重大挑戰。一方面，裝置漫遊可能造成 IP 位址浪費。當裝置從一個子網路移動到另一個子網路時，會取得多個 IP 位址 [5–7]，而 DHCP 伺服器無法及時回收閒置位址。另一方面，多數無線網路部署了身分驗證機制，使用者必須通過驗證後才能存取 Internet。然而，許多裝置可能在未通過驗證的情況下，自動與無線網路建立關聯。它們請求並占用 IP 位址，卻不產生任何流量。

例如，T 大學無線網路（TWLAN）的存取點（Access Point，AP）使用相同的服務集識別碼（Service Set Identifier，SSID）。只要裝置曾經連過這些 AP，即使沒有通過身分驗證，也能與無線網路建立關聯並成功取得 IP 位址，導致大量 IP 位址浪費。在同時有大量使用者的地點，例如餐廳，即使訊號強度很高，某些裝置仍無法與無線網路建立關聯。其中一個可能原因，是大量未通過驗證的使用者使 IP 位址耗盡。

此外，當無線網路涵蓋範圍很大時，網路管理員通常會設定多個存取控制器（Access Controller，AC）來管理所有 AP，並依經驗將 IP 位址劃分成多個位址池，分別對應不同 AC。不適當的位址劃分策略會加劇位址耗盡的問題。

租約時間是 DHCP 最重要的參數之一，決定裝置可以持有某個 IP 位址多久。適當設定租約時間有助於提高 IP 位址使用效率。然而，目前沒有明確的指引，協助管理員合理設定租約時間 [8]。在 T 大學，網路管理員始終依經驗設定固定值。可惜的是，租約時間過長會造成 IP 位址浪費，因為已不再活躍的裝置仍可能占用位址；租約時間過短則可能大幅增加 DHCP 伺服器負載。

由於缺乏對 DHCP 行為與效能的全面了解，網路管理員難以設定適當的租約時間。更糟的是，在將位址劃分成多個位址池的大型無線網路中，不適當的位址劃分策略可能使某些位址池的位址耗盡，同時其他位址池卻仍有大量可用位址。

過去多數研究試圖透過尋找適當的租約策略改善 DHCP 效能 [8–11]。這些方法是為相對簡單、地點較少、裝置種類與使用者較少的網路環境設計的，可能無法適應複雜的無線網路環境。此外，所有這些研究都沒有考慮未通過身分驗證使用者的影響，也缺乏對 DHCP 行為與效能的全面理解。

為填補此缺口，本文在 TWLAN 中，系統性地對 DHCP 行為與效能進行大規模量測。TWLAN 擁有超過 59,000 名個別使用者、10,000 個 AP，以及 130,000 個不同的 IP 位址。我們根據分析結果，設計有效策略來適當設定 DHCP 租約時間。進一步地，我們提出自適應位址劃分策略，以平衡各位址池的位址使用率，降低位址耗盡風險。

主要貢獻如下：

• 據我們所知，本研究進行了規模最大的 DHCP 行為量測。我們發現，請求訊息與到期訊息的趨勢關係因地點而異。平均而言，行動裝置（例如手機）每天產生的請求訊息比筆記型電腦多，而物聯網（Internet of Things，IoT）裝置介於兩者之間。此外，我們揭露某些不遵循規範與罕見的使用者行為；這些行為可能對 DHCP 效能造成重大影響。
• 我們對 DHCP 效能提出系統性分析，以了解其運作與管理中的低效率。DHCP 伺服器分配的 IP 位址數，與已通過驗證使用者取得的 IP 位址數之間存在很大落差。尖峰時段約有 25% 的位址被浪費。在依經驗劃分位址的策略下，各位址池的使用率差異很大。我們也發現，平均而言，裝置在租約時間的 67% 期間內不會產生流量。DHCP 在複雜無線網路環境中的效能遠不令人滿意。同時，不同地點、不同作業系統的裝置有不同上線模式，統一設定租約時間可能導致 IP 位址使用效率低落。
• 透過區分已通過驗證與未通過驗證的使用者，並進一步納入已通過驗證使用者的不同上線模式，我們提出新的租約最佳化策略。此策略輕量，且能以離線計算的參數輕易設定。我們使用四項指標，將它與三種當時最先進的基準方法及 TWLAN 原有策略比較。重播結果顯示，新策略優於其他策略，在未顯著增加 DHCP 伺服器負載的情況下，將已分配位址數減少 24%。此外，平均總租約時間減少 17%，IP 位址使用率提高約 10%。
• 為進一步改善 DHCP 效能，我們提出自適應位址劃分策略。此策略在尖峰時段前，使用隨機森林迴歸模型預測各位址池所需容量，再據此重新分配各位址池間的 IP 位址。實驗顯示，此策略可與新的租約最佳化方法同時部署，進一步降低位址耗盡風險。方法能有效平衡各位址池的位址使用率，使每個位址池都保有容量來支援更多同時上線的使用者。

本文其餘內容安排如下：第 II 節介紹資料集與方法；第 III 節呈現 DHCP 行為的量測結果；第 IV 節分析 DHCP 的低效率；第 V、VI 節分別提出新的租約策略與自適應位址劃分策略，以改善 DHCP 效能；最後，第 VII 節整理相關研究，第 VIII 節總結本文。

資助與作者所屬機構（原文首頁註記）： 本研究獲中國國家重點研發計畫資助，計畫編號為 2016YFB0801301、2016YFB0801302 與 2017YFB0503703。通訊作者為 Jessie Hui Wang（電子郵件：jessiewang@tsinghua.edu.cn）。H. Wang 與 W. Dang 任職／就讀於清華大學電腦科學與技術系，並隸屬北京資訊科學與技術國家研究中心，中國北京 100084。J. H. Wang、J. Wang 與 F. Li 隸屬清華大學網路科學與網路空間研究院，以及北京資訊科學與技術國家研究中心，中國北京 100084。J. Xue 隸屬華為技術有限公司，中國北京 100085。J. Shan 隸屬墨爾本大學工程學院，澳洲 Parkville VIC 3052。

II. 資料集與研究方法

本研究的分析與效能評估，依據在大型校園無線網路 TWLAN 中蒐集的數個資料集。TWLAN 擁有超過 59,000 名個別使用者、10,000 個 AP，以及 130,000 個不同的 IP 位址。

如圖 1 所示，TWLAN 由多個 AC 管理。每個 AC 控制分布於多棟建築中的大量 AP，這些 AP 共用分配給該 AC 的 IP 位址池。裝置連上無線網路時，首先向 DHCP 伺服器發出 DHCP 請求，以取得一個 IP 位址。接著，在存取 Internet 前，裝置必須與身分驗證伺服器通訊，驗證使用者身分以進行計費。成功完成驗證後，裝置的所有封包即可透過校園網路邊界路由器轉送到 Internet。

本文主要使用 2017 年 5 月 20 日至 5 月 26 日這一週蒐集的資料，進行量測分析與租約策略評估¹。本節先介紹這一週蒐集的資料集，再說明如何定位裝置，以及辨識裝置類型與作業系統，供後續分析使用。

¹ 我們另使用 2017 年 5 月 13 日至 5 月 19 日的資料，在第 V-B 節找出上線模式，並在第 V-C 節找出最佳租約設定。此外，為建立第 IV-A 節的常用裝置資料庫，以及訓練第 VI 節的位址預測模型，我們額外蒐集了兩個月的 DHCP 日誌。

圖 1（PDF 第 2 頁）：TWLAN 的網路通訊架構。 圖中標籤：Authentication Server＝身分驗證伺服器；Campus Backbone Network＝校園骨幹網路；Internet＝網際網路；AC＝存取控制器；Campus Network Edge Router＝校園網路邊界路由器；DHCP Server＝DHCP 伺服器。

查看原圖所在頁

A. 資料集

本文主要使用四種資料：DHCP 日誌、身分驗證日誌、SNMP [12] 資料，以及 NetFlow [13] 流量紀錄。

（1）DHCP 日誌。 DHCP 日誌由 DHCP 伺服器產生，記錄伺服器回應 DHCP 用戶端請求時採取的動作。一週的日誌包含超過 22,600,000 筆紀錄。每筆紀錄包含訊息時間，以及用戶端的 IP 位址與 MAC 位址；此外，還包含下列重要屬性。

Description（描述）： 表示 DHCP 訊息的類型 [14]。TWLAN 中有八種主要類型：

• ASSIGN（分配）： DHCP 伺服器分配新的 IP 位址給 DHCP 用戶端。
• RENEW（續租）： DHCP 用戶端向 DHCP 伺服器更新租約時間。
• RELEASE（釋放）： DHCP 用戶端明確釋放 IP 位址。
• EXPIRE（到期）： 租約到期，DHCP 伺服器回收 IP 位址。
• DELETE（刪除）： DHCP 伺服器刪除不可用 IP 位址的紀錄。
• NACK（否定確認）： DHCP 伺服器拒絕租約請求。
• CONFLICT（衝突）： DHCP 伺服器偵測到尚未分配的 IP 位址已在 TWLAN 中被使用。
• EXHAUSTED（耗盡）： IP 位址池沒有可供分配的 IP 位址。

Host Name（主機名稱）： 表示 DHCP 用戶端的主機名稱 [15]。使用者可自訂有意義的字串作為裝置名稱，其中通常包含可用來辨識裝置類型的詞彙 [16]。

Vendor Class（廠商類別）： 提供識別值，其中包含裝置作業系統的線索 [15, 17]。例如，Windows 系列裝置預設會將此欄位設為「MSFT」[18]，而 Apple 裝置通常不設定此欄位。

（2）身分驗證日誌。 在 TWLAN 中，為進行身分驗證與計費，某個 IP 位址必須先由使用者通過驗證，也就是將該位址與使用者建立關聯，才能存取 Internet。使用者必須支付該位址所有傳入與傳出流量的費用。一般而言，離線時使用者應解除自己與該位址的關聯，但使用者可能忘記通知身分驗證伺服器。此時，DHCP 伺服器在回收位址時必須通知身分驗證伺服器；否則，當 DHCP 伺服器把該 IP 位址分配給其他使用者時，管理員可能取得錯誤的計費資料。

所有驗證資訊都記錄於身分驗證日誌中。一週的日誌超過 1,000,000 筆。每筆紀錄包含已通過驗證使用者的身分、IP 位址、使用者登入時間（建立關聯），以及登出時間（解除關聯）。這些紀錄用於判定任一時間點，某個 IP 位址是否已通過驗證。此外，與身分驗證伺服器的所有通訊皆以 HTTP 為基礎。本研究擷取所有使用者驗證請求，從 HTTP 請求標頭中取出 User-Agent 資訊，用於辨識裝置類型與作業系統。

（3）SNMP 資料。 SNMP 廣泛用於網路管理 [19, 20]。TWLAN 中所有 AC 都支援 SNMP，並提供一組資料物件，讓管理員監控其狀態與設定。本研究使用腳本每 5 分鐘輪詢 AC，取得下列鍵值對：（1）使用者裝置的 MAC 位址，以及與該裝置建立關聯之 AP 的 MAC 位址；（2）AP 的 MAC 位址與名稱；（3）使用者裝置的 MAC 位址，以及透過 DHCP 請求取得的 IP 位址。SNMP 資料用來判定每個活躍裝置的位置，詳細方法見第 II-B 節。

（4）NetFlow 流量紀錄。 我們部署 NFDUMP [21]，蒐集校園網路邊界路由器匯出的 NetFlow 流量紀錄。每筆流量紀錄擷取五個屬性：開始時間、持續時間、來源 IP 位址、目的 IP 位址，以及流量總位元組數。一週內共蒐集超過 3.5 TB 的流量紀錄。這個資料集用來判定任一時間點，裝置是否真的處於活躍狀態。

B. 定位裝置

在 TWLAN 中，每個 AC 控制不同建築中的大量 AP，這些 AP 共用與該 AC 對應的 IP 位址池。因此，同一位址池中的 IP 位址可能分配給不同建築裡的使用者裝置，僅靠 IP 位址難以準確判定裝置位置。

本文依靠 SNMP 資料來判定各裝置在某個時間點的位置。分析 SNMP 輪詢蒐集的三種鍵值對後，可取得裝置在該時間點連接的 AP 名稱。TWLAN 中的 AP 遵循特定命名規則；特別是，名稱中包含可判定 AP 所在建築的字串前綴。因此，我們可以判定 DHCP 用戶端發出請求時的位置。

C. 辨識裝置類型與作業系統

先前研究 [8] 僅透過 DHCP 訊息欄位辨識裝置類型與作業系統。然而，有些使用者會修改 Host Name 欄位以隱藏裝置資訊，對類型與作業系統辨識造成重大挑戰。研究 [22, 23] 利用 HTTP User-Agent 辨識裝置類型與作業系統，但無法處理 User-Agent 被修改或未提供的情況。研究 [24] 提出，DHCP 訊息與 HTTP User-Agent 可在裝置類型辨識上互補，但主要關注類型辨識，使用的資訊不足以辨識作業系統。

本文提出改進的方法，結合 DHCP 日誌中的更多欄位（例如 Host Name、Vendor Class、MAC 位址等），以及身分驗證日誌中的 User-Agent，以辨識裝置類型與作業系統。方法分成兩輪。

第一輪使用前述 DHCP 訊息欄位。Vendor Class 與 MAC 位址中的 OUI 比身分驗證日誌裡的 User-Agent 更可信，因為使用者不易修改它們，因此我們先用這些欄位辨識。如果 DHCP 日誌的欄位（Host Name、Vendor Class、MAC 位址）中有明確字串，例如「iPhone」、「MacBook」、「MSFT」，即可直接辨識裝置類型與作業系統。例如，某裝置的 Vendor Class 若為「MSFT」，即可判定作業系統屬於 Windows 系列。接著檢查 Host Name：若包含「desktop」或「laptop」，便將它辨識為 Windows 筆記型電腦，而非 Windows 行動裝置；同理，若包含「phone」，則辨識為 Windows 行動裝置。

顯然，如果 DHCP 訊息欄位中的證據不足，第一輪無法明確判定某些裝置的類型與作業系統。對這些裝置，我們啟動第二輪，在身分驗證日誌的 User-Agent 欄位中進行關鍵字搜尋。如果仍無法判定，便將裝置標記為「unknown」（未知）。

即使第二輪成功，也不會直接採用結果，因為我們認為 User-Agent 提供的資訊較不可信。我們會檢查第一輪是否提供有用資訊或線索，即使這些資訊不足以形成確定結論。如果有，就檢查第二輪結果是否與第一輪線索一致。兩者沒有衝突，才採用第二輪結果；否則，將有衝突的裝置標記為「unknown」。

我們將這三種能辨識裝置作業系統的方法，也就是基於 DHCP 訊息的方法、基於 HTTP User-Agent 的方法，以及本文的方法，套用到一週的資料集。結果顯示，本文方法可辨識約 98.3% 裝置的類型與作業系統，相較於過去的方法，大幅提高辨識率。

2017 年 5 月 20 日至 5 月 26 日這一週，共有 103,812 個不同裝置。我們觀察到，Windows 是筆記型電腦的主要作業系統，占約 68.9%（24,616／35,721）。Android 與 iOS 是行動裝置的兩種主要作業系統，分別占 50.6%（32,214／63,604）與 49.1%（31,235／63,604）。此外，我們辨識出 557 個 IoT 裝置。

III. DHCP 行為量測

本節深入分析 DHCP 訊息資料集，嘗試揭示裝置行為與 DHCP 行為之間的關係。分析一般類型訊息，也就是 ASSIGN、RENEW 與 EXPIRE 後可見，地點、裝置類型與裝置作業系統對 DHCP 行為有明顯影響。這促使我們在第 V 節，從不同地點與作業系統模式的角度最佳化 DHCP 效能。

此外，我們也調查 NACK、CONFLICT 與 RELEASE 等特殊訊息。這些訊息出現次數不多，但反映出異常或罕見的使用者行為。據我們所知，這是企業網路中規模最大的 DHCP 行為量測。

由於 ASSIGN 與 RENEW 都表示用戶端正在請求 IP 位址，本節不區分兩者，統稱為 REQUEST（請求）訊息。

A. 不同地點的 DHCP 訊息

TWLAN 中，REQUEST 與 EXPIRE 訊息合計占 DHCP 訊息總數的 80%。圖 2 繪出這一週不同地點中，這兩種訊息數量的變化趨勢。我們使用第 II-B 節的方法判定每則 DHCP 訊息的位置，再將這些地點，也就是建築，分為六類：行政大樓、餐廳、宿舍、體育館、研究大樓及教學大樓。建築分類方法受到先前研究 [19, 25] 啟發。

我們觀察到，在所有地點類別中，兩種訊息的趨勢都具有很強的每日規律。在行政、研究及教學大樓，週末的 REQUEST 與 EXPIRE 訊息數顯著少於平日。

此外，很有意思的是，餐廳與體育館中的 REQUEST 訊息趨勢，與 EXPIRE 訊息趨勢呈正相關，兩者大致同時達到峰值。這是因為使用者通常只在這些地點短暫停留，DHCP 伺服器會頻繁分配與回收 IP 位址。但在其他地點，使用者往往停留較久，因此看不到這種正相關。例如，上課時使用者可能產生大量 REQUEST 訊息，卻只產生極少量 EXPIRE 訊息。

圖 2（PDF 第 4 頁）：不同地點的請求訊息（藍色實線）與到期訊息（紅色虛線）趨勢，數值經正規化。 子圖：（a）行政大樓；（b）餐廳；（c）宿舍；（d）體育館；（e）研究大樓；（f）教學大樓。橫軸 Date＝日期；縱軸 Number of the messages＝訊息數；Request messages＝請求訊息；Expiration messages＝到期訊息。

查看原圖所在頁

B. 不同作業系統的 DHCP 訊息

本小節探討不同種類裝置的 DHCP 行為。圖 3(a) 顯示不同類型與作業系統的裝置，一天內產生 REQUEST 訊息數的累積分布函數（CDF）。

我們發現，平均而言，行動裝置（iOS、Windows Phone、Android 等）比筆記型電腦（Windows、MAC OS、Linux）產生更多 REQUEST 訊息，而 IoT 裝置介於兩者之間。圖 3(b) 可解釋此現象：它呈現裝置一天內連接 AP 數量的 CDF。約 30% 的行動裝置一天與超過 5 個 AP 建立關聯，而超過 75% 的筆記型電腦一天與少於 3 個 AP 建立關聯。這表示行動裝置比筆記型電腦更常移動，因此通常產生更多 REQUEST 訊息。

圖 3(b) 進一步根據裝置名稱中的關鍵字，區分行動 IoT 裝置（例如智慧手錶）與固定 IoT 裝置（例如加濕器），並分別呈現量測結果。我們觀察到，超過 60% 的固定 IoT 裝置一天只與 1 個 AP 建立關聯，表示這些裝置不會移動，往往比筆記型電腦產生更少的 REQUEST 訊息。約 42% 的行動 IoT 裝置一天會與超過 4 個 AP 建立關聯，與行動裝置相似。頻繁移動可能使它們產生與行動裝置相近數量的 REQUEST 訊息。

圖 3(a) 的另一個發現是，在相同裝置類型中，Apple 裝置每天產生的 REQUEST 訊息比其他裝置多。例如，iOS 裝置平均產生的 REQUEST 訊息比 Android 裝置多 40%。這可以由不同裝置的預設電源管理政策解釋。iOS 裝置的螢幕關閉時，Wi-Fi 介面會進入休眠；Android 裝置的政策則可設定，其預設值為「永不休眠」。因此，iOS 裝置在 Wi-Fi 介面重新啟用時，會產生更多 REQUEST 訊息。

圖 3（PDF 第 5 頁）：（a）不同類型與作業系統的裝置每天產生請求訊息數的 CDF。（b）裝置每天連接 AP 數量的 CDF。標籤：Number of request messages＝請求訊息數；Number of APs＝AP 數量；Laptop＝筆記型電腦；Mobile Device＝行動裝置；Mobile IoT Device＝行動 IoT 裝置；Static IoT Device＝固定 IoT 裝置；CDF＝累積分布函數。作業系統名稱保留原文。

查看原圖所在頁

C. 特殊訊息類型與對應的使用者行為

第 II-A 節描述的某些訊息類型並不常出現，卻反映不遵循規範與罕見的使用者行為，可能對 DHCP 效能造成重大影響。

當裝置提出 DHCP 伺服器無法滿足的租約請求時，伺服器會拒絕請求並送出 NACK 訊息。從一週的 DHCP 日誌中，我們找出造成 NACK 的三個主要原因：

1. 約 65% 與使用者移動有關。使用者移至具有不同位址池的新網路時，仍繼續請求在先前網路的前一份租約中取得的位址。由於目前的位址池不包含該位址，DHCP 伺服器會拒絕租約請求。
2. 約 18% 是裝置嘗試續租已到期的租約。例如，裝置 A 的租約已到期，經過一段時間後，A 嘗試續租舊租約，但該 IP 位址已分配給裝置 B，因此無法滿足 A 的續租請求。
3. 其餘 NACK 訊息可能由網路設定錯誤造成，研究 [9] 曾報告此問題。

CONFLICT 訊息表示，DHCP 伺服器偵測到尚未分配的 IP 位址已在網路中被使用。可能原因是不遵循規範的使用者刻意為裝置設定靜態位址，而不是透過 DHCP 取得位址。這些使用者能推斷子網路的位址池、子網路遮罩及預設閘道，再據此設定靜態 IP 位址。

TWLAN 的 DHCP 伺服器設定為：在分配 IP 位址前，主動偵測該位址是否已被使用，也就是對該 IP 位址執行 ping，檢查有無回應。若偵測到位址已被占用，就不分配該位址，而是將其標記為「不可用」，並在日誌中產生 CONFLICT 紀錄。伺服器會定期檢查該位址是否仍被占用，直到不再被占用。換言之，如果不遵循規範的使用者一直占用位址，DHCP 伺服器就「失去」了該位址。我們將此現象稱為位址竊用（address theft）。

量測顯示，不遵循規範的使用者每天從位址池竊用約 155 個 IP 位址。此外，約 40% 的衝突位址被這些使用者占用超過 3 小時。

我們也調查 RELEASE 訊息，分析這一週明確釋放 IP 位址的租約比例。每天的比例變化不大，且都低於 2%。這表示使用者很少明確釋放自己的位址。換言之，多數閒置裝置會繼續占用 IP 位址，直到租約到期。

IV. DHCP 運作中的低效率

本節透過量測研究，從不同角度了解 DHCP 運作與管理效率低落的原因。第一部分研究未通過驗證使用者及位址劃分策略對 DHCP 效能的影響。第二部分呈現裝置的活躍上線時間與總租約時間之間的落差，並進一步探索不同地點與作業系統的上線模式。

未通過驗證使用者與裝置上線模式的分析，促使我們提出第 V 節的租約時間最佳化策略；位址池使用率的分析，則促使我們提出第 VI 節的自適應位址劃分策略。

A. 未通過驗證的使用者與位址池劃分

TWLAN 中只有通過驗證的裝置能存取 Internet。然而，未通過驗證的裝置只要曾連過 TWLAN，就能自動連接 AP。連上 AP 後，便能向 DHCP 伺服器請求位址。DHCP 伺服器收到請求後，會公平地分配 IP 位址給它們。雖然未通過驗證使用者的裝置無法存取 Internet，仍會占用 IP 位址。這顯然浪費了原本可分配給其他裝置的位址。

圖 4 呈現這一週不同地點中，DHCP 伺服器分配的 IP 位址數，與已通過驗證使用者取得的 IP 位址數之間的差異。兩條曲線的趨勢一致，尖峰時間則與地點類別有關。例如，研究大樓的已分配位址數在兩段時間達到峰值（10:00–11:00、14:00–16:00），如圖 4(e) 所示，這是因為多數學生習慣在這些時段進行研究。學生與教職員通常在 12:00、18:00 用餐，因此餐廳的已分配位址數在這些時間達到峰值，如圖 4(b) 所示。

此外，兩條曲線間存在很大落差，表示大量 IP 位址分配給未通過驗證的使用者。但落差程度因地點而異。在教學大樓（圖 4(f)），多數使用者會通過驗證以搜尋線上教材，因此落差相對較小。行政大樓（圖 4(a)）與體育館（圖 4(d)）中的使用者更常做其他事，而不是上網，所以較多使用者不會驗證身分，造成很大落差。

有意思的是，宿舍的落差比教學與研究大樓更明顯，原因如下：一名學生通常擁有多個裝置，大多數裝置更可能出現在宿舍，包括各種行動裝置與某些 IoT 裝置，例如 PlayStation、加濕器等。學生不太可能同時使用多個裝置，但這些裝置仍可能與無線網路建立關聯並取得 IP 位址，使宿舍的落差較大。相較之下，學生通常在教學或研究大樓讀書、研究，只會帶必要的裝置，而且大多數裝置會通過驗證。

圖 4（PDF 第 6 頁）：不同地點中，DHCP 伺服器分配的 IP 位址數（紅色實線），與已通過驗證使用者取得的 IP 位址數（藍色虛線）之間的落差。 子圖地點順序與圖 2 相同。Number of IP addresses＝IP 位址數；Authentication IP＝已通過驗證的 IP 位址；DHCP IP＝DHCP 已分配的 IP 位址；Date＝日期。

查看原圖所在頁

裝置第一次發出 DHCP 請求時，伺服器不知道之後是否會通過驗證，因此無法區分已通過與未通過驗證的使用者，也無法分別設定租約時間。為解決此問題，我們根據 TWLAN 過去兩個月的 DHCP 日誌與身分驗證日誌，建立常用裝置資料庫（common device database）。如果某裝置的 MAC 位址在每個平日都出現在 DHCP 日誌中，且每週至少通過驗證一次，就將它視為常用裝置。

可見，常用裝置是 T 大學學生或教職員經常使用的裝置，而非訪客的裝置，較可能通過驗證以存取 Internet。為維持有效性，資料庫每週更新一次，並將用於第 V 節的租約時間最佳化。

如公式（1），我們定義新指標 IP 位址使用率 $U_{ip}$，表示常用裝置使用的 IP 位址數 $IP_{common}$，占 DHCP 伺服器分配的所有 IP 位址數 $IP_{total}$ 的比例。$U_{ip}$ 越高，低效率使用的 IP 位址就越少。

圖 5(a) 繪出 $U_{ip}$。週末的平均 $U_{ip}$ 比平日低，因為週末訪客很多。此外，夜間的 $U_{ip}$ 比白天高，因為使用者夜間幾乎都在宿舍，更可能是學生或教職員，並使用自己的常用裝置。尖峰時段的 $U_{ip}$ 約為 75%，表示平均約 25% 的 IP 位址未被有效率地使用。

現在考慮位址劃分策略的影響。為方便管理，TWLAN 將所有 IP 位址劃分為多個位址池，每個位址池對應一個 AC。網路管理員憑經驗直覺設定各位址池容量，而且容量不隨時間改變。顯然，我們希望位址池容量能隨 AC 的位址需求調整，避免一個位址池耗盡，而其他位址池卻仍有大量可用位址。單憑經驗的直覺設定可能不理想。

為評估目前的位址劃分策略，我們定義 IP 位址池使用率 $U_{pool}$：

其中，$IP_{demand}$ 是對應 AC 的最大 IP 位址需求量，$IP_{pool}$ 是位址池容量。請注意，即使位址池耗盡，裝置無法取得可用 IP 位址，其 DHCP 請求仍會以 EXHAUSTED 訊息記錄於日誌。因此，我們能準確取得某段時間內的最大 IP 位址需求量。

圖 5(b) 顯示 TWLAN 五個典型位址池在尖峰時段的 $U_{pool}$。其他位址池與這五種情況相似，為求簡潔省略。位址池 1、2 的 $U_{pool}$ 都超過 1，表示兩者位址耗盡，許多使用者無法取得位址。位址池 4、5 的 $U_{pool}$ 很低，位址未充分利用，顯示資源浪費。位址池 3 的 $U_{pool}$ 接近 1，面臨很高的耗盡風險。分析顯示各位址池的 $U_{pool}$ 差異極大，依經驗劃分的方法並不令人滿意。

圖 5（PDF 第 6 頁）：（a）這一週 IP 位址使用率的變化。（b）TWLAN 五個典型位址池的 IP 位址池使用率。IP Address Utilization＝IP 位址使用率；IP Address Pool Utilization＝IP 位址池使用率；Pool＝位址池；Date＝日期。

查看原圖所在頁

B. DHCP 總租約時間與活躍上線時間

第 III-C 節提到，多數使用者裝置不會明確釋放位址。因此，即使裝置已不需要 IP 位址，仍必須等租約到期才能回收。如果能預測裝置上線時間的長度，就能據此設定租約時間，避免閒置裝置造成資源浪費。顯然，固定租約時間無法達成這個目標。本小節使用這一週蒐集的超過 3.5 TB NetFlow 資料，研究閒置裝置造成的浪費。

我們將一份租約中的**活躍上線時間（active online time）**定義為：從裝置發出 DHCP 請求（ASSIGN 訊息）開始，到裝置產生最後一個位元組為止的時間。分析 DHCP 日誌與 NetFlow 流量紀錄後，即可找出所有租約的活躍上線時間。**DHCP 總租約時間（total lease time）**則定義為：一份租約中，裝置實際占用 IP 位址的整段時間。

圖 6 描述兩者的關係。圖 7(a) 呈現所有租約的 DHCP 總租約時間與活躍上線時間 CDF。兩條曲線之間存在很大落差，平均而言，活躍上線時間遠小於總租約時間。活躍上線時間的中位數約為 28 分鐘，總租約時間的中位數約為 85 分鐘，表示 IP 位址約 67% 的時間被浪費，進一步加劇有限 IP 位址耗盡的問題。

我們進一步探討 TWLAN 不同地點的上線時間長度，結果如圖 7(b)。裝置上線時間的分布因地點而異。在行政大樓、餐廳與體育館，超過 50% 裝置的上線時間少於 10 分鐘。在教學大樓，平均上線時間約為 75 分鐘，超過 80% 裝置的上線時間少於 150 分鐘。這是因為一般課程長度為 95 分鐘，某些重要課程則為 155 分鐘。

研究大樓與宿舍的上線時間分布相似，都是長尾分布，可以由某些學生習慣長時間待在研究大樓或宿舍解釋。圖 7(c) 呈現不同作業系統裝置的活躍上線時間 CDF。雖然都呈長尾分布，不同作業系統的曲線仍不相同。特別是，筆記型電腦往往比行動裝置有更長的上線時間。90% IoT 裝置的上線時間接近 0，可能表示：即使其 Wi-Fi 模組已開啟，也很少使用 Wi-Fi 通訊。

總結而言，裝置的地點與作業系統明顯影響活躍上線時間長度。我們需要能自適應設定 DHCP 租約時間的方法，而且應將地點與裝置作業系統納入考量。

圖 6（PDF 第 7 頁）：某份租約的活躍上線時間與總租約時間之間的關係。 Assign＝分配；Active Online Time＝活躍上線時間；Last Byte＝最後一個位元組；Expire／Release＝到期／釋放；Total Lease Time＝總租約時間。

查看原圖所在頁

圖 7（PDF 第 8 頁）：（a）所有裝置的 DHCP 總租約時間與活躍上線時間 CDF。（b）不同地點類型之裝置上線時間的 CDF。（c）不同作業系統之裝置上線時間的 CDF。為提高可讀性，截去長尾部分。Time (minute)＝時間（分鐘）；DHCP Lease time＝DHCP 租約時間；Active Online time＝活躍上線時間；Classroom＝教學大樓；Research Department＝研究大樓；Administrative Building＝行政大樓；Dormitory＝宿舍；Gymnasium＝體育館；Cafeteria＝餐廳；IoT Device＝IoT 裝置。

查看原圖所在頁

V. 租約時間最佳化

量測研究顯示，如果能針對不同使用者與裝置設定不同租約時間，也就是納入身分驗證資訊、地點與作業系統，就能減少 IP 位址浪費。本節介紹租約時間最佳化策略的構想與實作。我們將它與三種當時最先進的策略，以及 TWLAN 現行策略比較，透過實驗證明有效性。

特別是，我們開發重播演算法，還原使用者請求位址、離線等行為，並盡可能貼近真實情境地模擬 DHCP 訊息互動，進行效能評估。

A. 目標與啟發式原則

主要目標是透過合理設定租約時間，將 IP 位址浪費降至最低。較短租約時間總是有利於此目標，卻不可避免地增加 DHCP 伺服器負載。因此，最佳化目標是找出效率與成本之間的良好取捨。換言之，我們希望：（1）盡可能減少已分配 IP 位址數；（2）將 DHCP 伺服器負載的增幅限制在某個門檻內。

本文以 DHCP 伺服器收到的 DHCP 請求訊息與回應訊息數量，衡量伺服器負載。TWLAN 網路管理員建議，負載增幅不應超過 30%；此限制依具體網路環境決定。

我們無法精確預測每個裝置在一份租約中的上線時間，因此必須依靠啟發式原則，決定每次 DHCP 請求的適當租約時間。根據量測與資料分析，我們提出兩項原則：

1. 對不在第 IV-A 節所建常用裝置資料庫中的裝置，DHCP 伺服器應分配較短租約。
2. 對資料庫中的裝置，其預期活躍上線時間（依地點與作業系統判定）越長，分配的租約時間也應越長。

第一項確保伺服器能及時回收從不通過驗證之裝置的 IP 位址。第二項確保租約時間設定考慮地點與作業系統資訊，並避免產生大量 DHCP 訊息。

B. 已通過驗證使用者的預期上線時間

我們發現，不同地點、不同作業系統的裝置，其活躍上線時間分布不同。TWLAN 有 6 種地點類型與 8 種作業系統類型，共形成 48 種組合，其中 8 種占比極小，可省略。我們蒐集 2017 年 5 月 13 日至 5 月 19 日的資料，分別繪製其餘 40 種組合的裝置上線時間 CDF；為求簡潔，省略這些 CDF 圖。某些組合具有相似分布，表示上線模式相似，可以同等處理。

我們以各組合上線時間分布的中位數代表其上線模式，並將中位數時間長度繪於圖 8。橫軸表示依上線時間中位數排序的所有組合。依其中位數時間長度，可將（作業系統，地點）組合分成五類，並以不同顏色與符號標示。同一類中，已通過驗證使用者的活躍上線時間中位數大致相同，可由單一數值代表。我們將此數值定義為該類的預期上線時間（expected online time）。

詳細分類見表 I。第二欄的萬用字元表示可匹配所有地點或所有作業系統，並採最長匹配原則。預期上線時間將用於租約時間最佳化。

圖 8（PDF 第 8 頁）：不同組合的上線時間中位數。 Median of Online Time＝上線時間中位數（分鐘）；Combinations of Location Type and OS＝地點類型與作業系統的組合。

查看原圖所在頁

表 I：已通過驗證使用者的五種分類。

C. 租約時間設定策略

我們針對每次 DHCP 請求提出如下設定策略。收到請求後，DHCP 伺服器先檢查發出請求的裝置是否位於常用裝置資料庫中。如果不在，租約時間設為 5 分鐘。如果是常用裝置，方法先取得其地點與作業系統，再將（作業系統，地點）與表 I 條目比對，找出分類編號。

依第 V-A 節第二項啟發式原則，我們提出：常用裝置的租約時間可與表 I 的預期上線時間成線性比例。令 $x$ 表示比例係數的倒數，也就是預期上線時間與租約時間的比值。可調整 $x$，在 DHCP 伺服器負載與 IP 位址最大需求量之間取得所需取捨。

較大的 $x$ 使租約時間較短，產生更多 RENEW 訊息，因此 DHCP 伺服器負載較重。較小的 $x$ 使租約時間較長，更多位址被不活躍的裝置占用，因此 IP 位址需求較大。

我們需要找出在 TWLAN 中達成良好取捨的最佳 $x$。逐步調整 $x$，並對每個參數值，使用 2017 年 5 月 13 日至 5 月 19 日的 DHCP 日誌進行重播，推導對應的位址需求與伺服器負載。重播演算法將在第 V-D 節詳述。

圖 9 顯示，參數 $x$ 改變時，已分配 IP 位址數及 DHCP 伺服器負載的變化趨勢。橫軸為 $x$；左縱軸是新租約設定下的已分配 IP 位址數，與原設定下的數量之比；右縱軸是新設定與原設定之 DHCP 伺服器負載的比值。

我們觀察到，隨 $x$ 增加，也就是租約時間縮短，減少 IP 位址數所帶來的額外收益逐漸變小，而伺服器負載增幅呈線性成長。由於必須將負載增幅限制在 30%，我們將 $x=2$ 視為最佳取捨點。$x=2$ 表示租約時間應設為預期上線時間的一半。此時，可在未顯著增加伺服器負載的情況下，減少 24% 的已分配位址數。

圖 9（PDF 第 8 頁）：參數 $x$ 改變時，已分配位址數與 DHCP 伺服器負載的趨勢。 Parameter of Lease Time Setting＝租約時間設定參數；IP Address Decrement＝IP 位址減少情形（新／原數量比）；Server Load Increment＝伺服器負載增加情形（新／原負載比）；server load baseline (30%)＝伺服器負載增幅基準（30%）；reduced by 24%＝減少 24%。

查看原圖所在頁

D. 重播演算法

為決定參數 $x$（第 V-C 節），以及評估不同策略的效能（第 V-E 節），我們需要知道任一租約時間策略下的 IP 位址使用情況與 DHCP 伺服器負載。因此，我們設計重播演算法，從真實 DHCP 日誌推斷使用者行為，例如何時傳送 DHCP 請求以重新啟用裝置、何時離線，再重播這些行為，依待評估策略產生 DHCP 訊息。

使用此演算法，可取得部署某策略時預期出現的 DHCP 訊息序列，再推導該策略的相關統計量。

演算法主要關注五種訊息：ASSIGN、RENEW、RELEASE、EXPIRE 與 EXHAUSTED，因為它們代表完整的租約過程。ASSIGN 與 RELEASE 直接由使用者動作觸發，不受租約策略影響，因此可直接複製實際網路所蒐集原始日誌中的這些訊息。部署新策略後，其他訊息將於不同時間點產生。換言之，必須根據採用的策略，以及從原始日誌還原的使用者行為來產生。以下主要說明 RENEW 與 EXPIRE 的產生方式。

（1）產生 RENEW 訊息。 DHCP 日誌中的 RENEW 可能由兩種原因造成。第一種是租約延長機制：租約時間過了一半時，如果用戶端仍與網路建立關聯，就會自動請求延長租約，產生 RENEW 訊息。我們稱之為租約延長 RENEW 訊息（lease extension RENEW messages）。此類訊息的產生時間由具體租約策略決定。因此，因為分配的租約時間已改變，重播時必須忽略原始日誌中的這類訊息，並依新策略週期性產生新的租約延長 RENEW 訊息。

第二種原因是使用者行為，例如重新啟動系統、喚醒螢幕或重新啟用 Wi-Fi 介面。在這些情況下，裝置產生 RENEW 訊息，以確認之前取得的位址是否正確。我們稱之為 init-reboot RENEW 訊息。重播時真實使用者行為應保持相同，因此必須將這些訊息複製到新 DHCP 日誌中；也就是說，新策略下 init-reboot RENEW 的產生時間，應與原策略相同。

如圖 10(a)，init-reboot 請求的抵達時間具隨機性，而租約延長請求總是在租約時間過了一半時產生。我們可依兩個連續續租請求間的時間間隔，區分這兩種請求。

（2）產生 EXPIRE 訊息。 圖 10(b) 的例子中，原策略下租約在 $t_6$ 到期，最後一次續租請求在 $t_3$。可以推得兩點：原策略的租約時間為 $t=t_6-t_3$；在 $t_5=(t_3+t_6)/2$，也就是原租約期間的中點時，裝置已與 AP 斷線，否則會在 $t_5$ 自動產生 RENEW 訊息以延長租約。

雖然知道斷線必定發生於 $t_3$ 與 $t_5$ 之間，仍無法取得精確時間。因此，我們選擇兩者的中點 $t_4$，作為斷線時間的近似值。據此，可進一步決定新策略下 EXPIRE 訊息的產生時間：新策略下最後一則 RENEW 訊息的時間，加上新的租約時間。

實際上，此重播演算法提供一種方式，可評估任何透過設計租約策略來改善 DHCP 效能的方法。正式虛擬碼見附錄 A。

圖 10（PDF 第 10 頁）：（a）租約延長 RENEW 訊息與 init-reboot RENEW 訊息之間的差異。（b）在完整租約期間中，找出裝置與無線網路斷線的時間點。標籤：Complete Lease Process＝完整租約過程；Assign＝分配；Renew＝續租；Expired＝到期；Lease Extension Renewal Request＝租約延長續租請求；Init-reboot Renewal Request＝init-reboot 續租請求；Active Point＝活躍時間點。（a）中的 $t$ 表示租約時間的一半，$t_1$、$t_2$ 表示 init-reboot 請求的間隔；（b）中的 $t$ 表示原租約時間。

查看原圖所在頁

E. 本文策略的效能評估

前面各節使用 2017 年 5 月 13 日至 5 月 19 日的資料，決定租約策略參數。現在將此策略套用於後續週次，並以重播演算法評估有效性。為求簡潔，本文僅呈現 2017 年 5 月 20 日至 5 月 26 日的模擬結果；其他週次的資訊見附錄 C。我們選用三種當時最先進的方法作為比較基準，介紹如下。

Single Adaptation（單次調整）[10]： 對初次租約請求設定較長租約時間，對後續續租請求則縮短租約時間。其假設是，裝置上線時間越長，越可能與無線網路斷線。實驗使用研究 [10] 作者提出的設定與參數：初次請求的租約時間為 90 分鐘，後續續租請求為 30 分鐘。

Exponential Adaptation（指數調整）[10]： 裝置初次抵達時分配較短租約，每次發出續租請求就將租約時間加倍，直到上限。此方法假設：如果用戶端已活躍夠久，就更可能繼續連接網路。研究 [10] 以降低伺服器負載為目標，設定很大的上限，會造成嚴重資源浪費。為公平評估，我們透過枚舉找出最佳參數。上限設為 60 分鐘，初始值設為 15 分鐘，此設定最能平衡位址使用與伺服器負載。

OS-based Differential Lease（依作業系統差異化租約）[8]： 為不同作業系統分配不同租約時間，以盡量減少尖峰時段的 IP 位址數與 DHCP 伺服器負載。兩個目標無法同時達到，原作者也未清楚說明如何取捨。實驗採用與本文相同的最佳化目標：DHCP 伺服器負載增幅不超過 30%。在此條件下，選擇能將已分配位址數降至最低的各作業系統設定。

我們繪圖呈現不同作業系統租約時間改變時，伺服器負載及已分配位址峰值的趨勢，見附錄 B，據此取得最適當的租約設定：Android 24 分鐘、iOS 22 分鐘、Windows 28 分鐘、MAC OS 26 分鐘；其他作業系統皆為 30 分鐘。

我們使用四項指標，評估不同租約策略下的 DHCP 效能：

• IP 位址使用量： 某個時間點，尤其尖峰時段的已分配 IP 位址數，是最重要的最佳化目標之一。
• DHCP 伺服器負載： 以 DHCP 伺服器收到的請求訊息與回應訊息數量衡量。
• 總租約時間： 一份租約中，裝置占用 DHCP 伺服器分配的 IP 位址之期間長度。
• IP 位址使用率： 依公式（1）定義，反映某個時間點，常用裝置使用的 IP 位址比例。一般而言，使用率高表示多數位址被有效率地使用。

接著，將本文方法與三種基準方法，以及 TWLAN 原有的固定租約時間策略比較。

圖 11(a) 顯示這一週的已分配 IP 位址數，內嵌小圖表示每天尖峰時段的位址峰值；圖 11(b) 顯示這一週正規化後的 DHCP 伺服器負載。套用本文方法後，已分配 IP 位址數可顯著減少。尖峰時段節省超過 6,000 個 IP 位址，約減少 24%，與第 V-C 節結果一致。同時，DHCP 伺服器負載平均增加約 25%，符合增幅不超過 30% 的要求。

對依作業系統差異化租約策略而言，雖然整體位址使用量優於原策略，趨勢卻大幅波動。已分配位址峰值只減少約 10%，效果遠不及本文方法；伺服器負載也增加約 20%，與本文方法相近。這表示在大型無線網路環境中，只考慮作業系統無法準確反映裝置上線模式。

單次調整與指數調整雖未明顯增加伺服器負載，已分配位址峰值卻接近原策略，某些情況甚至更高。這反映不同使用者的行為特徵有差異，兩種策略的基本假設不一定適用所有裝置。良好的租約策略應區分不同使用者行為。總體而言，位址使用量與伺服器負載的實驗結果證明本文租約策略有效。

圖 12(a) 顯示不同租約策略下，所有裝置總租約時間的 CDF。本文方法將平均總租約時間減少 17%，更接近使用者的活躍上線時間，表示已分配位址能及時回收。其他基準策略的平均總租約時間，甚至比原策略更長。

圖 12(b) 呈現 IP 位址使用率。相較其他基準方法，本文方法有顯著改善，比原策略高約 10%。我們認為，這得益於仔細區分已通過驗證與未通過驗證的使用者。綜合實驗結果，本文方法大幅改善已分配 IP 位址的使用效率。

圖 11（PDF 第 11 頁）：（a）不同租約策略下，這一週已分配 IP 位址數的趨勢；內嵌小圖表示每天的位址峰值。（b）不同租約策略下，這一週正規化後的 DHCP 伺服器負載。Normalized DHCP Server Load＝正規化 DHCP 伺服器負載；Date＝日期；Original Leasing Strategy＝原租約策略；Single Adaptation＝單次調整；Exponential Adaptation＝指數調整；OS-based Differential Lease＝依作業系統差異化租約；Our Proposed Strategy＝本文提出的策略。

查看原圖所在頁

圖 12（PDF 第 11 頁）：（a）不同租約策略下，所有裝置 DHCP 總租約時間的 CDF。（b）不同租約策略在尖峰時段的 IP 位址使用率。Time (minute)＝時間（分鐘）；Active Online Time＝活躍上線時間；Average IP Address Utilization＝平均 IP 位址使用率。圖例中的策略 1–5 依序為：原策略、單次調整、指數調整、依作業系統差異化租約、本文策略。

查看原圖所在頁

VI. 自適應位址劃分

第 V 節的租約策略雖能大幅減少 IP 位址浪費，但若同時上線的使用者數超過對應位址池的 IP 位址總數，仍可能有裝置無法取得位址。第 IV-A 節分析指出，TWLAN 現行的依經驗劃分策略並不理想。對同一位址池而言，每日所需 IP 位址數有顯著差異，顯示固定容量可能不合理。因此，我們提出自適應位址劃分策略，改善 IP 位址池使用率 $U_{pool}$。

A. 自適應位址劃分策略的設計

將一個位址池中使用者所需的 IP 位址數，稱為所需位址池容量（demanded pool size）。基本構想是依各位址池所需容量劃分位址空間。問題是，如何事先預測某位址池一天所需的容量？若能預測，就能在每天開始時，依需求比例分配各位址池的位址。

雖然各位址池的已分配位址數趨勢具有強烈每日規律，每天的峰值仍變化很大，難以僅靠歷史資料預測，因為使用者行為彼此獨立，某些日子也可能因重要活動而突然增加。

幸運的是，我們發現一天的峰值，可能與當天較早時段的已分配 IP 位址數高度相關。考慮到峰值通常出現在 10:00 之後，我們希望依 10:00 前的趨勢預測，再重新劃分位址，以滿足各池的真實需求。0:00–6:00 的已分配位址很少，趨勢也沒有明顯變化，難以擷取有價值的特徵。因此，我們以 6:00–9:00 的特徵預測位址需求峰值，使位址能在 10:00 前重新劃分。

策略設計以監督式機器學習迴歸模型為基礎。訓練階段連續蒐集兩個月 DHCP 日誌；接著，對每個位址池，擷取每天所選特徵的數值以組成特徵向量，並找出當天對應的所需容量，用這些資料訓練迴歸模型。預測階段，將新取得的特徵向量輸入模型，即可預測所需容量。

本文選用隨機森林迴歸（Random Forest Regression）作為預測模型。它已在許多應用情境中證實有效，例如 Wi-Fi 效能與 Internet 路徑延遲預測 [26–28]。附錄 D 的實驗也顯示，隨機森林模型優於其他常見迴歸模型。

受先前研究 [26, 28] 啟發，我們依經驗，採用 6:00–9:00 已分配 IP 位址數曲線的 18 個統計量作為候選特徵，稱為曲線特徵。此外，週末趨勢與平日顯著不同，因此加入一個時間特徵，區分週末與平日，以提高準確度。

我們再使用相對資訊增益（Relative Information Gain，RIG）[27]，從 19 個候選特徵中選出最有效者。RIG 反映知道某特徵值後，預測目標的不確定性減少的百分比。各候選特徵的詳細描述及 RIG 見附錄 E。

所有候選特徵中，有六個曲線特徵的 RIG 小於 0.01，因此排除。其餘 12 個曲線特徵被選用，分別是：6:00、7:00、8:00、9:00 的已分配 IP 位址數；6:00–8:00 的平均數；7:00–9:00 的平均數；6:00–9:00 已分配 IP 位址數的第 25、50、75 百分位數；以及該時段曲線斜率的第 50、75 百分位數與最大值。時間特徵的 RIG 也相對較高，表示對預測模型有價值，因此保留。

B. 自適應位址劃分策略的評估

本小節評估所提出策略的效能。先關注隨機森林迴歸預測模型的準確度，以決定係數 $R^2$ 及相對誤差為指標，分別定義如下：

其中，$n$ 為測試樣本數，$y$ 為測試樣本的真實峰值，$\bar y$ 為 $y$ 的平均值，$\hat y$ 為預測值。$R^2$ 衡量迴歸預測值接近真實資料點的程度，越接近 1，擬合越好。相對誤差衡量預測誤差的程度；越小表示誤差越不顯著，預測越好。

圖 13 顯示隨機森林迴歸在測試資料上的結果。橫軸、縱軸分別為真實位址需求與預測位址需求。以 $y=x$ 作為基準線，代表預測值與真實值完全相同。幾乎所有點都接近基準線，呈正線性關係。$R^2$ 約為 0.96，相對誤差約為 2.8%，顯示模型有效。

令 $\delta$ 表示預測值與真實值之差的絕對值。圖 14(a) 呈現其分布。測試資料中幾乎所有 $\delta$ 都小於 256，相當於一個 /24 位址區塊的容量。只有極少數大值（少於 0.5%），由不尋常的需求突增造成，例如某地點舉行大型全校活動；這些不具代表性，可予省略。

因此，實務上為降低位址不足風險，我們將「預測值加上 256」作為某位址池的所需容量。此外，依慣例，以 /24 為各位址池間分配位址的粒度。

最後，我們同時部署自適應位址劃分策略及前一節的租約最佳化策略，使用 2017 年 5 月 20 日至 5 月 26 日資料，評估第 IV-A 節五個典型位址池的使用率。如圖 14(b)，相較原有依經驗的策略，本文策略能平衡所有位址池的 $U_{pool}$，五個位址池的使用率都在 70% 左右。

同時，租約最佳化有效降低每個位址池的所需容量。例如，位址池 1、2、3 成功避免耗盡（$U_{pool}<1$），使用率顯著下降；位址池 4、5 的 $U_{pool}$ 則提高，表示位址能更充分利用。綜合而言，自適應位址劃分搭配租約最佳化取得良好成果，所有位址池都保有可用容量，能滿足更多同時上線的使用者。

圖 13（PDF 第 12 頁）：隨機森林迴歸在測試資料上的預測結果。 True Value＝真實值；Predicted Value＝預測值；Relative Error＝相對誤差；$R^2$＝決定係數。

查看原圖所在頁

圖 14（PDF 第 12 頁）：（a）預測值與真實值差之絕對值的分布。（b）同時使用自適應位址劃分與租約最佳化策略後，五個典型位址池的使用率。Before Using Our Proposed Strategy＝使用本文策略前；After Using Our Proposed Strategy＝使用本文策略後；IP Address Pool Utilization＝IP 位址池使用率；Pool＝位址池；$\delta=256$ 為誤差參考界線。

查看原圖所在頁

VII. 相關研究

與本文相關的研究包括 [8–11, 24, 29–31]。Brik 等人描述 DHCP 的潛在問題 [9]。Das 等人提出，為手持裝置設定較短租約能提高位址使用率 [24, 29]。Khadilkar 等人探討兩種租約策略，以最佳化 IP 位址使用與伺服器負載 [10]。Papapanagiotou 等人仔細研究不同裝置類型與作業系統的 DHCP 行為，並提出考慮裝置差異的租約策略 [8]。Li 等人設計負載感知演算法來設定租約時間，以減少 DHCP 額外負擔 [11]。研究 [30] 從理論分析租約時間設定對位址使用與伺服器負載的影響。

上述研究雖試圖透過租約時間改善 DHCP 效能，但某些研究的最佳化目標與本文不同。此外，它們皆為簡單網路環境設計，未考慮許多有用資訊，例如地點與身分驗證資訊，因此無法適應 TWLAN 這類複雜環境。它們也未系統性分析租約時間設定的問題，例如未通過驗證使用者對 IP 位址使用率的影響；多數也未考慮大型無線網路中位址劃分策略的作用。本文填補這些缺口。

本文從以下方面擴充我們先前的研究 [32]：分析依經驗劃分位址的問題，提出自適應劃分策略，以進一步降低位址耗盡風險；詳細描述 DHCP 重播演算法設計；並進行更多實驗，將本文租約策略與三種基準比較，證明其有效性。

許多先前研究提出不同裝置類型與作業系統辨識方法 [8, 22–24]。Papapanagiotou 等人 [8] 指出，可用 DHCP 訊息中的某些欄位辨識作業系統，但使用者可能修改某些欄位，例如 Host Name，以隱藏裝置資訊，對辨識造成重大挑戰。某些研究 [22, 23] 使用 HTTP User-Agent 辨識作業系統，但無法處理 User-Agent 被修改或未提供的情況。

Das 等人 [24] 注意到，DHCP 欄位與 HTTP User-Agent 可在裝置類型辨識上互補，但主要關注類型。本研究提出改進方法，結合更多 DHCP 日誌欄位及 HTTP User-Agent，同時辨識裝置類型與作業系統。結果顯示，新方法取得令人滿意的辨識率。

VIII. 結論

據我們所知，本研究進行了規模最大的 DHCP 行為與效能量測。DHCP 雖廣泛使用，效能卻遠不令人滿意。約 25% 的 IP 位址因非常用裝置而未被有效利用，各位址池的使用率也差異很大。此外，已分配位址的總租約時間平均有 67% 被浪費。

非常用裝置普遍存在於各種無線網路，它們占用 IP 位址，卻未真正使用網路。大型無線網路通常為方便管理而劃分為多個子網路，但子網路間如何劃分位址空間，往往憑經驗決定。因此，第 IV 節報告的 DHCP 低效率，是大型無線網路中的普遍問題，尤其是具有身分驗證機制的網路。

受這些發現啟發，我們提出租約策略與自適應位址劃分策略，以改善 DHCP 效能。實驗顯示，租約策略可將已分配 IP 位址總數減少 24%；自適應位址劃分則可進一步降低各位址池耗盡的風險。

解決方案的第一項建議，是區分常用與非常用裝置，對非常用裝置給予較短租約。這應在所有無線網路中都有用且有效。第二項建議，是依裝置屬性，例如地點、類型與作業系統，給予不同租約時間。基本構想應適用所有無線網路，但上線模式與具影響力的屬性未必相同。如果找不到明確模式，仍可對所有裝置設定相同租約時間，並以資料驅動方法決定數值，應比目前依經驗設定更好。第三項建議，是依位址池的預測需求劃分位址空間。基本構想可有效用於各種無線網路，但本文的需求預測模型，須依個別案例或網路類型檢驗。

我們相信，本文是在更了解 DHCP 行為，以及改善複雜無線網路中 DHCP 效能方面，有意義的一步。我們正推動在 TWLAN 部署所提出的租約策略與自適應位址劃分策略，希望實際正式運作網路中的部署，能帶來更多改善 DHCP 效能的寶貴見解。

參考文獻

作者姓名、出版品名稱、年份、卷期與頁碼保留書目資訊；文獻標題附中文翻譯，以便閱讀與查找。

[1] R. Droms，〈動態主機設定協定〉（Dynamic host configuration protocol），1997。

[2] 〈IPv4 位址報告〉（IPv4 address report），線上電子文獻，2017，原網址。

[3] S. Zander、L. L. Andrew、G. Armitage、G. Huston，〈以捕捉－再捕捉方法估計 IPv4 位址空間使用情況〉（Estimating IPv4 address space usage with capture-recapture），2013 IEEE 38th Conference on Local Computer Networks Workshops (LCN Workshops)，IEEE，2013，頁 1010–1017。

[4] A. Dainotti、K. Benson、A. King、M. Kallitsis、E. Glatz、X. Dimitropoulos 等，〈透過被動量測估計 Internet 位址空間使用情況〉（Estimating internet address space usage through passive measurements），ACM SIGCOMM Computer Communication Review，第 44 卷，第 1 期，頁 42–49，2013。

[5] G. C. Moura、C. Ganán、Q. Lone、P. Poursaied、H. Asghari、M. van Eeten，〈ISP 位址空間有多動態？邁向全 Internet 的 DHCP 位址更替估計〉（How dynamic is the ISPs address space? Towards Internet-wide DHCP churn estimation），IFIP Networking Conference (IFIP Networking)，IEEE，2015，頁 1–9。

[6] Y. Xie、F. Yu、K. Achan、E. Gillum、M. Goldszmidt、T. Wobber，〈IP 位址有多動態？〉（How dynamic are IP addresses?），ACM SIGCOMM Computer Communication Review，第 37 卷，第 4 期，ACM，2007，頁 301–312。

[7] L. Vu、D. Turaga、S. Parthasarathy，〈DHCP 位址更替對網路特性分析的影響〉（Impact of DHCP churn on network characterization），ACM SIGMETRICS Performance Evaluation Review，第 42 卷，第 1 期，ACM，2014，頁 587–588。

[8] I. Papapanagiotou、E. M. Nahum、V. Pappas，〈智慧型手機時代的 DHCP 租約設定〉（Configuring DHCP leases in the smartphone era），Proceedings of the 2012 ACM Conference on Internet Measurement Conference，ACM，2012，頁 365–370。

[9] V. Brik、J. Stroik、S. Banerjee，〈DHCP 效能問題的除錯〉（Debugging DHCP performance），Proceedings of the 4th ACM SIGCOMM Conference on Internet Measurement，ACM，2004，頁 257–262。

[10] M. Khadilkar、N. Feamster、M. Sanders、R. Clark，〈基於使用情況的 DHCP 租約時間最佳化〉（Usage-based DHCP lease time optimization），Proceedings of the 7th ACM SIGCOMM Conference on Internet Measurement，ACM，2007，頁 71–76。

[11] F. Li、X. Wang、J. Cao、R. Wang、Y. Bi，〈DHCP 租約如何因應智慧終端：模擬與建模〉（How DHCP Leases Meet Smart Terminals: Emulation and Modeling），IEEE Internet of Things Journal，第 5 卷，第 1 期，頁 56–68，2018。

[12] W. Stallings，《SNMP、SNMPv2、SNMPv3，以及 RMON 1 與 2》（SNMP, SNMPv2, SNMPv3, and RMON 1 and 2），Addison-Wesley Longman Publishing Co., Inc.，1998。

[13] B. Claise，〈Cisco Systems NetFlow 服務匯出第 9 版〉（Cisco Systems NetFlow Services Export Version 9），2004。

[14] 〈分析 DHCP 伺服器日誌檔案〉（Analyze DHCP Server Log Files），線上電子文獻，2017，原網址。

[15] 〈DHCP 工具與選項〉（DHCP Tools and Options），線上電子文獻，2017，原網址。

[16] X. Chen、L. Lipsky、K. Suh、B. Wang、W. Wei，〈大學校園 Wi-Fi 網路中智慧型手機的連線階段長度與 IP 位址使用：特性分析及解析模型〉（Session lengths and IP address usage of smartphones in a university campus WiFi network: Characterization and analytical models），2013 IEEE 32nd International Performance Computing and Communications Conference (IPCCC)，IEEE，2013，頁 1–9。

[17] S. Alexander、R. Droms，〈DHCP 選項與 BOOTP 廠商擴充〉（DHCP Options and BOOTP Vendor Extensions），1997。

[18] 〈解釋並釐清 Microsoft 廠商專屬 DHCP 選項〉（(Microsoft) Vendor specific DHCP options explained and demystified），線上電子文獻，2017，原網址。

[19] K. Sui、Y. Zhao、D. Pei、L. Zimu，〈未授權裝置對企業 802.11 網路效能的影響有多嚴重？〉（How bad are the rogues’ impact on enterprise 802.11 network performance?），2015 IEEE Conference on Computer Communications (INFOCOM)，IEEE，2015，頁 361–369。

[20] D. Perkins、E. McGinnis，《理解 SNMP MIB》（Understanding SNMP MIBs），Prentice-Hall, Inc.，1997。

[21] P. Haag，〈Nfdump〉，2010，可從原網站取得。

[22] J. Erman、A. Gerber、K. Ramadrishnan、S. Sen、O. Spatscheck，〈OTT 影音：行動網路中的龐然大物〉（Over the top video: The gorilla in cellular networks），Proceedings of the 2011 ACM SIGCOMM Conference on Internet Measurement Conference，ACM，2011，頁 127–136。

[23] A. Gember、A. Anand、A. Akella，〈校園 Wi-Fi 網路中手持與非手持裝置流量的比較研究〉（A comparative study of handheld and non-handheld traffic in campus Wi-Fi networks），Passive and Active Measurement，Springer，2011，頁 173–183。

[24] A. K. Das、P. H. Pathak、C.-N. Chuah、P. Mohapatra，〈無線多裝置使用者的特性分析〉（Characterization of wireless multi-device users），2015 12th Annual IEEE International Conference on Sensing, Communication, and Networking (SECON)。

[25] D. Kotz、K. Essien，〈全校園無線網路分析〉（Analysis of a campus-wide wireless network），Wireless Networks，第 11 卷，第 1–2 期，頁 115–133，2005。

[26] S. Wassermann、P. Casas、T. Cuvelier、B. Donnet，〈Netperftrace：以機器學習預測 Internet 路徑動態與效能〉（Netperftrace: Predicting internet path dynamics and performance with machine learning），Proceedings of the Workshop on Big Data Analytics and Machine Learning for Data Communication Networks，ACM，2017，頁 31–36。

[27] C. Pei、Y. Zhao、G. Chen、R. Tang、Y. Meng、M. Ma、K. Ling、D. Pei，〈實際環境中，Wi-Fi 可能是網路往返延遲最薄弱的一環〉（WiFi can be the weakest link of round trip network latency in the wild），INFOCOM 2016—The 35th Annual IEEE International Conference on Computer Communications，IEEE，2016，頁 1–9。

[28] M. Konte、R. Perdisci、N. Feamster，〈Aswatch：揭露提供防彈主機代管之自治系統的 AS 信譽系統〉（Aswatch: An AS reputation system to expose bulletproof hosting ASes），ACM SIGCOMM Computer Communication Review，第 45 卷，第 4 期，ACM，2015，頁 625–638。

[29] A. K. Das、P. H. Pathak、C.-N. Chuah、P. Mohapatra，〈無線多裝置使用者的特性分析〉（Characterization of wireless multidevice users），ACM Transactions on Internet Technology (TOIT)，第 16 卷，第 4 期，文章 29，2016。

[30] T. Van Do，〈用於 DHCP 效能與可靠性評估之重試佇列的有效解法〉（An efficient solution to a retrial queue for the performability evaluation of DHCP），Computers & Operations Research，第 37 卷，第 7 期，頁 1191–1198，2010。

[31] X. Wei、N. C. Valler、H. V. Madhyastha、I. Neamtiu、M. Faloutsos，〈手持裝置行為的特性分析及其影響〉（Characterizing the behavior of handheld devices and its implications），Computer Networks，第 114 卷，頁 1–12，2017。

[32] H. Wang、J. Wang、W. Dang、J. Xue、F. Li，〈縮小落差：大型無線網路中 DHCP 效能的實證研究〉（Squeezing the Gap: An Empirical Study on DHCP Performance in a Large-scale Wireless Network），IEEE INFOCOM 2018—IEEE Conference on Computer Communications，IEEE，2018，頁 1628–1636。

作者簡介

Haibo Wang： 2015 年取得北京交通大學電腦科學與技術學士學位。目前為清華大學電腦科學與技術系博士候選人。研究興趣包括網路量測、網路管理及 AIOps。

Jessie Hui Wang： 取得清華大學電腦科學學士與碩士學位，並於 2007 年取得香港中文大學資訊工程博士學位。目前為清華大學副教授。研究興趣包括 Internet 路由、雲端運算、資料分析、網路量測及 Internet 經濟學。

Jilong Wang： 2000 年取得清華大學電腦科學與技術系博士學位。目前為清華大學教授。研究重點包括網路量測、以位置為導向的網路，以及軟體定義網路（SDN）。

Weizhen Dang： 2016 年取得清華大學電腦科學與技術系學士學位，目前於該系攻讀碩士。研究興趣包括網路量測、無線網路及網路管理。

Jing’an Xue： 分別取得清華大學與西安交通大學的電腦科學與技術博士及工程學士學位。研究興趣包括網路量測與管理，尤其是內容傳遞網路量測與智慧異常偵測（AIOps）。

Fenghua Li： 2004 年取得清華大學電腦科學與技術系博士學位。目前為清華大學副教授。研究重點包括網路管理、無線網路及網路架構。

Jinzhe Shan： 2015 年取得北京郵電大學物聯網工程學士學位。目前於墨爾本大學攻讀碩士。研究重點包括網路管理、機器學習與自然語言處理。

附錄

A. 重播演算法的設計

重播演算法對資料驅動分析與效能評估至關重要，因此我們在演算法 1 中詳細呈現設計。它提供一種評估方式，適用於任何透過設計租約策略來改善 DHCP 效能的方法。

重播 DHCP 日誌時，主要關注 RENEW 與 EXPIRE 訊息，因為它們同時受使用者行為及採用的租約策略影響。策略改變後，RENEW 與 EXPIRE 會在不同時間點產生。

（1）在演算法 1 中產生 RENEW 訊息。 第 11–13 行說明如何處理租約延長 RENEW。出現這類訊息，表示裝置自動請求延長租約。顯然，其產生時間與採用的策略密切相關。租約時間改變，這類訊息就應在不同時間點產生。因此，重播時應忽略原日誌中的這類訊息，並依新策略產生新的 RENEW。

第 14–15 行及第 20 行說明如何處理 init-reboot RENEW。它們由使用者行為引發，例如重啟系統、喚醒螢幕、重新啟用 Wi-Fi 介面。必須將這類訊息複製到新日誌，因為重播時真實使用者行為應保持不變，代表新策略與原策略下 init-reboot RENEW 的產生時間應相同。

此外，如第 16–19 行，兩個連續 init-reboot RENEW 之間，需根據新策略週期性產生租約延長 RENEW。

（2）在演算法 1 中產生 EXPIRE 訊息。 如第 21 行，若原始 DHCP 日誌的一筆紀錄是 EXPIRE，表示對應原租約結束。圖 15 顯示完整原租約的例子：若租約於 $t_6$ 到期，最後續租請求於 $t_3$ 發出，則可推得在 $t_5$（$t_3$ 加上原租約時間的一半）裝置已與 AP 斷線，否則會自動產生 RENEW 來延長租約。

因此，選取 $t_3$ 與 $t_5$ 的中點 $t_4$，近似兩者間真正的斷線時間。$t_4$ 與 $t_3$ 的間隔是原租約時間的四分之一。重播時，第 23 行先將最後 RENEW 的發出時間加上原租約時間的四分之一，取得近似斷線時間。接著，如第 24–26 行，在斷線前，依新策略以新租約時間的一半為週期，產生租約延長 RENEW。最後，新租約到期時，相應產生 EXPIRE（第 27 行）。

演算法 1：DHCP 日誌中租約的重播演算法。

輸入：原租約 $L$、參數 $x$。輸出：新租約 newLease。

 1: newTime = L.leaseTime / x;
 2: 若 L.device 不在常用裝置資料庫中，則
 3:     newTime = 5;
 4: 否則
 5:     newTime = getLeaseTime(L.location, L.OS) / x;
 6: 初始化新租約 newLease;
 7: 對 i = 1 到 L.length 逐一執行
 8:     若 L[i].description == ASSIGN 或 RELEASE，則
 9:         將 L[i] 加入 newLease;
10:     若 L[i].description == RENEW，則
11:         若 L[i] 不是 init-reboot 請求，則
12:             // 租約延長請求的情況
13:             continue;
14:         否則
15:             // init-reboot 請求的情況
16:             t = newLease 中最後一筆紀錄的時間;
17:             當 t + newTime / 2 < L[i].time 時
18:                 t = t + newTime / 2;
19:                 在 newLease 中加入時間為 t 的 RENEW;
20:             將 L[i] 加入 newLease;
21:     若 L[i].description == EXPIRE，則
22:         t = newLease 中最後一筆紀錄的時間;
23:         tmp = L[i−1].time + L.leaseTime / 4;
24:         當 t + newTime / 2 < tmp 時
25:             t = t + newTime / 2;
26:             在 newLease 中加入時間為 t 的 RENEW;
27:         在 newLease 中加入時間為 t + newTime 的 EXPIRE;
28:     若 L[i].description == EXHAUSTED，則
29:         若位址池中存在可用 IP 位址，則
30:             在 newLease 中加入一份完整租約;
31:             break;
32:         否則
33:             將 L[i] 加入 newLease;
34:     若 L[i].description == 其他類型，則
35:         將 L[i] 加入 newLease;
36: 回傳 newLease;

譯註：虛擬碼保留原文的變數、行號與控制流程，不將原文未展開的「加入一份完整租約」補寫成額外實作。第 5 行的函式名稱與正文「預期上線時間除以 $x$」的描述皆依原文保留。

圖 15（PDF 第 15 頁）：在一份完整租約中，找出裝置與無線網路斷線的時間點。 Assign＝分配；Renew＝續租；Expired＝到期；Active Point＝活躍時間點；$t$＝原租約時間。圖示與圖 10(b) 相同。

查看原圖所在頁

B. 基準策略的租約時間設定

依作業系統差異化租約策略，對不同作業系統分配不同租約時間，以盡量減少尖峰時段的 IP 位址數及伺服器負載。為決定最佳設定，圖 16 呈現不同作業系統的租約時間改變時，DHCP 伺服器負載及已分配位址峰值的趨勢。

可見，Android、iOS、Windows、MAC OS 的租約時間應分別設為 24、22、28、26 分鐘。其他作業系統設為 30 分鐘。由於它們占比小且趨勢相似，省略其圖。

圖 16（PDF 第 16 頁）：找出不同作業系統最適當的租約設定。（a）Android：24 分鐘；（b）iOS：22 分鐘；（c）Windows：28 分鐘；（d）MAC OS：26 分鐘。其他作業系統因占比小且趨勢相似而省略，皆設為 30 分鐘。Lease Time＝租約時間；min＝分鐘；其位址數與伺服器負載比值的意義同圖 9。

查看原圖所在頁

C. 另一週資料的實驗

為求簡潔，正文僅呈現以一週資料為基礎的 DHCP 低效率量測，以及本文解決方案的效能評估。此處提供更多結果，以驗證正文中的觀察。我們將顯示，不同地點與作業系統的裝置，其上線模式在不同週次相似；也使用另一週資料，證明相似的 DHCP 低效率行為，並驗證租約策略有效性。

（1）不同週次具有相似的上線模式。 我們製作盒鬚圖，比較 2017 年 5 月 20 日至 5 月 26 日，以及 5 月 27 日至 6 月 2 日兩週中，不同地點與作業系統裝置的活躍上線時間分布。如圖 17(a)、17(b)，兩週間沒有明顯變化。這表示使用者裝置行為呈每週規律，一週資料應足以描述此校園網路的使用者行為。

圖 17（PDF 第 16 頁）：（a）比較兩週不同地點裝置的上線模式。（b）比較兩週不同作業系統裝置的上線模式。First Week Data＝第一週資料；Second Week Data＝第二週資料；Time (minute)＝時間（分鐘）。地點依序為餐廳、宿舍、體育館、教學大樓、行政大樓、研究大樓；裝置／作業系統依序為 IoT 裝置、Windows、MAC OS、Linux、iOS、Android、Windows Phone。

查看原圖所在頁

（2）相似的 DHCP 低效率與新租約策略有效性評估。 本研究以 2017 年 5 月 20 日至 5 月 26 日資料，報告 TWLAN 原策略的低效率與本文策略的有效性。此處再以 5 月 27 日至 6 月 2 日另一週資料呈現量測與評估結果。請注意，重播新一週日誌時，本文策略設定維持與正文評估相同，仍使用第 V-C 節依 5 月 13 日至 5 月 19 日資料決定的設定。

結果證實，本文主要結論在新一週資料的實驗中仍成立。以下提供圖表，整理新結果：

• 新一週中，本文租約策略仍能在 DHCP 伺服器負載與已分配位址峰值之間取得所需取捨。 圖 18(a) 顯示新一週的已分配 IP 位址數，圖 18(b) 顯示正規化負載。結果與第 V-E 節前一週結果一致。本文策略下的已分配位址峰值顯著下降，伺服器負載增幅從未超過 30%。
• 新一週中，裝置的平均活躍上線時間仍遠小於總租約時間，本文策略能有效縮小落差。 圖 19(a) 為新一週所有裝置總租約時間的 CDF。原策略下，總租約時間與活躍時間仍存在很大落差，表示新一週大量 IP 位址仍未被有效使用，與第 IV-B 節結論一致。此外，本文策略仍能有效降低平均總租約時間，並優於其他策略。
• 新一週中，非常用裝置仍造成大量 IP 位址浪費，本文策略能有效提高位址使用率。 圖 19(b) 顯示 IP 位址使用率。原策略下約 26% 的 IP 位址分配給非常用裝置，表示身分驗證機制對 DHCP 效能的負面影響仍嚴重；此比例與第 IV-A 節非常接近。此外，新策略能改善約 12%。

上述觀察顯示，本研究結論在不同週次均成立。此外，本文方法以資料驅動。為確保策略有效，其參數，也就是常用裝置資料庫、已通過驗證使用者的上線模式及參數 $x$，可定期更新。

圖 18（PDF 第 16 頁）：（a）新一週已分配 IP 位址數的趨勢。（b）新一週正規化後的 DHCP 伺服器負載。橫軸日期為 5 月 27 日至 6 月 2 日；策略圖例與圖 11 相同。

查看原圖所在頁

圖 19（PDF 第 16 頁）：（a）新一週所有裝置 DHCP 總租約時間的 CDF。（b）新一週的 IP 位址使用率。策略編號與圖 12 相同；Average IP Address Utilization＝平均 IP 位址使用率。

查看原圖所在頁

D. 不同迴歸模型的效能比較

第 VI-A 節選用隨機森林迴歸，預測各位址池的位址需求峰值。為進一步展示其優勢，我們將它與六種常見迴歸預測方法比較：線性迴歸（Linear Regression）、邏輯斯迴歸（Logistic Regression）、貝氏迴歸（Bayesian Regression）、決策樹迴歸（Decision Tree Regression）、支援向量機迴歸（SVM Regression）、梯度提升迴歸（Gradient Boosting Regression）。

圖 20 呈現 10 折交叉驗證結果。隨機森林迴歸的 $R^2$ 優於其他迴歸演算法，表示以隨機森林為基礎的模型，在此問題中更有效。

圖 20（PDF 第 17 頁）：隨機森林迴歸與另外六種常見迴歸演算法的比較。 Random Forest Regression＝隨機森林迴歸；其他模型名稱的中文對照如上；比較指標為 $R^2$。

查看原圖所在頁

E. 預測模型的特徵選擇

為以隨機森林迴歸預測各位址池的位址需求峰值，我們依經驗，從 6:00–9:00 擷取 18 個曲線特徵，表示已分配 IP 位址數及其成長率的變化，並加入一個時間特徵，區分週末與平日。這 19 個候選特徵的詳細描述見表 II。

接著使用相對資訊增益（RIG）選擇最重要特徵。RIG 反映知道某特徵值後，預測目標的不確定性降低的百分比，也就是對預測任務的貢獻。各候選特徵的 RIG 列於表 II 第四欄。

第 13–18 列候選特徵因 RIG 低於 0.01 而忽略，選用前 12 個曲線特徵。我們也發現，7:00–9:00 已分配 IP 位址數平均值與曲線斜率最大值，對預測任務貢獻最大；時間特徵也非常有價值。

表 II：所有特徵的相對資訊增益。 # 表示數量；「斜率」對應原文 curve gradient。

原表以合併儲存格標示第 13–18 項的 RIG 均低於 0.01；此處為便於 Markdown 閱讀，逐列重複標示。