基于帶寬匹配的軟件定義數據中心網絡流量節(jié)能調度方案

摘要： 針對數據中心網絡的流調度優(yōu)化問題，選用經典的Fat-Tree拓撲結構，利用軟件定義網絡集中控制的優(yōu)勢，提出一種基于帶寬匹配的節(jié)能路由算法（energy efficient routing algorithm， EERA）。EERA首先對需要傳輸的數據流按照其截止時間進行排序，然后對拓撲中的鏈路權值按照每個排序后的數據流需要傳輸的數據量進行更新，刪除可用帶寬不滿足傳輸數據量的鏈路，得到新的拓撲圖。在重新定義的拓撲圖中，EERA計算源節(jié)點和目標節(jié)點之間所有可用鏈路，從這些可用鏈路中選取與流傳輸數據量所需帶寬最匹配的鏈路進行路由。仿真實驗表明，在不增加額外存儲開銷的前提下，EERA為即將到來的數據流預留了足夠的帶寬，減少了網絡鏈路擁塞，在節(jié)省網絡能耗的同時實現了網絡負載均衡。

關鍵詞： 數據中心網絡; 軟件定義網絡; 流量調度; 負載均衡; 節(jié)能路由

中圖分類號： TN 92

文獻標志碼： A

DOI：10.12305/j.issn.1001-506X.2024.11.32

Traffic energy efficient scheduling scheme based on bandwidth matching in software defined data center networks

ZHANG Zhaohui^*， ZHOU Jiaqi

（School of Mathematics and Statistics， Xidian University， Xi’an 710126， China）

Abstract： To solve the traffic scheduling optimization problem in the data center networks， an energy efficient routing algorithm （EERA） is proposed based on bandwidth matching in the software defined data center networks， and takes the advantage of the software defined network centralized control using classic Fat-Tree topology. EERA sorts the traffic according to their deadlines and traffic sizes and updates the link weights in the topology for each sorted traffic according to the amount of data. Then EERA deletes the links whose available bandwidth does not meet the amount of transmitting data and gets a new topology. In the redefined topology， EERA calculates all the available links between the source node and the target node， then selectes the optimal links from these available links that match the bandwidth required by traffic transmitting. Simulation results show that EERA reserves enough bandwidth for incoming traffic with no additional storage overhead， and reduces the network congestion. At the same time， EERA saves the network energy consumption and achieves the network load balancing.

Keywords： data center network; software defined network; traffic scheduling; load balancing; energy efficient routing

0 引 言

數據中心（data centers， DCs）是當今云計算的重要組成部分，其拓撲構造主要由大量節(jié)點、服務器和交換機組成，通過設備之間的相互連接而進行數據通信，主要用于分布式計算、存儲或為用戶提供云服務。隨著5G技術的發(fā)展，用戶對分布式控制系統(tǒng)的需求逐步增加，過去十年，DC網絡（DC networks， DCNs）在規(guī)模和鏈路速率方面都在快速增長，與此同時，大量的計算、存儲和通信資源正在轉移到DCs，越來越多的分布式應用程序（如web搜索、社交網絡和在線購物）也部署在大型DCs，這些應用程序在DCNs中產生了海量的數據流量，其性能直接影響到用戶體驗和DCs提供商的收入。如今，DCNs承載著百度、抖音、推特、Ins、亞馬遜、微軟和谷歌等云服務供應商的大部分網絡流量，現代DCNs通常組織在多路由根樹拓撲中，比如Fat-Tree與兩層虛擬鏈接（virtual link-2， VL2），在不同服務器之間提供多條等成本路徑，故而多徑數據傳輸直接影響到DCNs應用程序的性能，針對DCNs的相關優(yōu)化技術研究至關重要。

據估計，到2025年，全球DCs能耗將占全球能源消耗的33%^［1］，對于DCs而言，不斷增長的能源消耗一直限制著云服務的快速發(fā)展，并引發(fā)了經濟和環(huán)境危機。DCs的能耗主要來自3個方面：DCNs、服務器和制冷系統(tǒng)，其中DCNs能耗約占DC總能耗的20%，這使得降低DCNs能源消耗已成為DCs需要解決的問題之一。

在現有的DCNs節(jié)能路由協議中，流量調度技術已被廣泛采用^［2］。在節(jié)能的前提下，合理的流量調度技術可以增加網絡吞吐量和降低延遲，從而改進網絡性能。獨占式路由可以充分利用鏈路，允許流獨占路徑，并且流可以在全帶寬鏈路下進行傳輸。然而，目前的流調度方法經常采取的方式是直接按照流大小優(yōu)先級或流到達時間順序進行調度，這樣雖然在一定的程度上實現了數據傳輸的高吞吐與低時延，但可能會導致一些具有高優(yōu)先級的大流占據較多的網絡資源和多路復用現象，延遲其他流的傳輸，導致網絡擁塞加劇，從而加重交換機和路由器等網絡設備的處理負擔，繼而造成額外的能耗開銷，不利于DCNs的運行。

軟件定義網絡（software defined network， SDN）^［3］是一種革命性的網絡架構，其引入了集中式控制器，提高了網絡的可編程性。該架構通常由SDN控制器和支持SDN的交換機所組成，SDN控制器是一種集中式網絡管理軟件，其作用是控制所有支持SDN的交換機轉發(fā)網絡流。除此之外，SDN控制器還提供面向北向應用的應用程序接口（application programming interface， API），API使網絡的架構管理更加靈活，讓企業(yè)和網絡運營商通過DCNs的可編程性實現了自動化網絡控制。

本文首先對流量約束下的DCNs能耗優(yōu)化問題進行了數學建模，進一步，為了近似地求解該模型，基于SDN對網絡流集中管理控制及調度的技術特點，提出了一種基于帶寬匹配的軟件定義DCN節(jié)能路由算法（energy efficient routing algorithm， EERA）。EERA首先對接入網絡的數據流按照截止時間優(yōu)先級進行排序，然后將數據流分配到與其所流大小最佳匹配的鏈路上，實現鏈路能耗的最大利用率，從而節(jié)省了網絡的能耗。

本文其余部分安排如下：在第1節(jié)，對DCNs流量控制的國內外研究現狀與相關工作進行了介紹。在第2節(jié)中，給出了網絡系統(tǒng)模型。在第3節(jié)，介紹了建立的節(jié)能單目標優(yōu)化模型以及對應的近似優(yōu)化算法EERA具體實現步驟。在第4節(jié)，通過仿真實驗驗證了所提算法在能耗、吞吐量和流的接受率3項指標的性能。最后，對本文的工作進行了總結與展望。

1 DCNs國內外研究現狀與相關工作

針對DCNs的流量控制問題，國內外科研工作者探索研究較多的包含兩個方面：流量工程和擁塞控制^［4］。DCNs流量工程是針對不同業(yè)務的數據流量特征設計相應的傳輸策略，旨在實現負載平衡與流量優(yōu)先級的優(yōu)化目標。DCNs擁塞控制的優(yōu)化目標是降低通信鏈路擁塞發(fā)生的可能性，或者在部分鏈路發(fā)生擁塞時采取相應措施，比如降低數據傳輸速率或提前分配帶寬，以此來減輕擁塞程度，以確保數據傳輸的低時延要求得到滿足，緩解傳輸控制協議（transmission control protocol， TCP）多對一傳輸現象?；诖?，本節(jié)主要從DCNs流量工程和擁塞控制兩個方面綜述當前DCNs流量控制的國內外研究現狀。

1.1 DCNs流量工程

Alasmor等^［5］提出了一種用于DCNs通用的傳輸協議，即系統(tǒng)級率少編碼數據傳輸協議（systematic rateless coding-based data transport protocol， SCDP），這是第一個利用DCNs中網絡層組播傳輸并均衡多對一通信中數據發(fā)送方負載的協議，從應用層長單播流和短單播流的吞吐量和流完成時間來看，SCDP都表現出了非常優(yōu)越的性能。Luo等^［6］針對DCNs組播設計了一種基于優(yōu)先級的自適應組播（priority-based adaptive multicast， PAM）協議，PAM協議通過使用一種分布式的機制完成了一系列流量調度規(guī)則，減少了DCNs內文件分發(fā)的平均組播完成時間和錯過傳輸截止時間的次數。Wang等^［7］提出一種新的DCNs流傳輸路由框架，并基于該框架提出了一種兩階段的EERA，該算法可以根據交換機功耗和路由之間的關系，減少活動交換機的數量并平衡網絡流量，從而減少能耗。Li等^［8］設計了一種用于節(jié)省DCNs受限流的網絡能耗流調度算法，該算法同時考慮交換機使用數量與交換機有效運行持續(xù)時間，以達到網絡減少能耗的目的。

針對DCNs中具有流傳輸截止時間限制的網絡流優(yōu)化問題，文獻［2］提出一種基于SDN的帶寬感知EERA（bandwidth-aware EERA with SDN， BEERS），該算法通過將流調度到每個鏈路的隊列中，從而最小化DCNs流量造成的能耗。進一步，文獻［9］提出了一種流截止時間感知的流動態(tài)調度節(jié)能策略（deadline-aware and energy-efficient dynamic flow scheduling， DEDFS），該策略按照不同的傳輸以及網絡節(jié)能目的對數據流進行分類，有效實現了DCNs節(jié)能與傳輸效率間的平衡，但是犧牲了部分服務質量（quality of service， QoS）。為了解決這一問題，Cui等^［10］充分考慮用戶的需求差異設計了一種新型的拓撲自適應DCNs范式用以解決虛擬機（virtual machine， VM）遷移問題，并提出了漸進分解舍入（progressive-decom position-rounding， PDR）和在線決策者（online decision-maker， ODM）兩種算法，PDR與ODM算法分別用以定期流調度和實時流調度，在保證節(jié)能的同時滿足了不同用戶的傳輸要求。

負載均衡是DCNs的重要挑戰(zhàn)。Chkirbene等^［11］利用網絡流的數據相關性解決了DCNs負載與能耗不成比例的問題。針對現有流調度方案功效低下和QoS波動的問題，Guo等^［12］設計了一種動態(tài)流調度方案Aggreflow，Aggreflow以較低的開銷提高了DCN的功率效率，實現了負載均衡，但同時也造成了更高的延遲，針對這一問題，文獻［13］提出了一種排隊延遲感知的流負載平衡機制 （queueing delay aware packet spraying， QDAPS），QDAPS在保障網絡QoS的前提下顯著地降低流完成時間。而Cheng等^［14］通過考慮異構網絡帶寬，給出了一種有效的網絡感知多路徑（network-aware multi-pathing， NAMP）方案，NAMP在不影響正在傳輸中的流的情況下，通過在線事件觸發(fā)的方式對DCNs新加入的流組進行集中調度。為了有效地平衡多路徑間的流量，文獻［15］提出了一種分布式動態(tài)多路由（dynamic distributed multi-path， DDMP）負載均衡算法，該算法利用動態(tài)哈希計算DCNs中的流量分布，并根據緩沖區(qū)占用率的反比動態(tài)調整流量分布，從而有效地防止了鏈路的擁塞。Wu等^［16］使用了一種稱為Blender的流量感知容器放置策略，實現了 DCNs流量成本的縮減和負載平衡。文獻［17］通過使用加入第一空閑隊列（join-the-first-idle-queue， JFIQ）和一種分散的自動縮放策略，構建了一個統(tǒng)一的負載平衡和自動縮放框架，該框架在減少DCNs操作開銷的同時降低了流傳輸響應時間。崔子熙等^［18］設計了一種基于流分類的DCNs負載均衡（utilization-aware load balancing based on flow classification， ULFC）機制，ULFC機制在實現擁塞感知的基礎上對流量特征進行分析，使用不同的流調度策略為大、小流分配路徑，實現網絡流量特征與路徑分配之間的最佳匹配。

一些貪婪啟發(fā)式算法也在DCNs流量工程中被廣泛應用。為了兼顧優(yōu)化物理機資源浪費和網絡總流量兩個方面，趙君等^［19］將虛擬機放置問題建模為多目標優(yōu)化問題，使用基于多目標蟻群優(yōu)化的虛擬機放置算法快速地完成了虛擬機的放置。為了減少DC的能量消耗，Feng等^［20］設計了一種基于模擬退火算法（simulated annealing based algorithm， SABA）的VMs遷移優(yōu)化策略，SABA相較于模擬退火（simulated annealing， SA）算法，使用了更少的迭代次數獲得最優(yōu)解的近似解，通過減少VMs遷移布置任務所需激活服務器的數量從而降低了DCNs能耗。Ayoub等^［21］在DCNs中引入了VMs遷移問題，可以在不中斷服務的情況下跨DC遷移VMs，針對在線最小資源使用和在線最小帶寬建立了一個多目標整數線性規(guī)劃（integer linear programming， ILP）模型，為了求解該ILP模型，Omaran提出了兩種啟發(fā)式算法以及一種離線VMs遷移方法，并同時開發(fā)了一個“警報感知VMs疏散”策略，該策略可以根據流到達VMs的截止時間、數量、特征以及鏈路容量選擇最優(yōu)的在線VMs遷移方式。針對DCNs虛擬網絡功能（virtual network functions， VNFs）遷移和服務功能鏈（service function chains， SFCs）重構問題，Li等^［22］使用了一種改進的遺傳進化（improved hybrid genetic evolution， IHGE）算法解決了該問題。此外，為了減少IHGE路由器的計算開銷，Li進一步設計了一種多級啟發(fā)式算法（multi-stage heuristic algorithm based on optimal order， MSH-OR）。仿真結果表明，IHGE算法和MSH-OR算法能夠在減少服務延遲的同時保證網絡負載均衡。Zu等^［23］從DCNs管理的角度出發(fā)，研究了支持網絡功能虛擬化（network function virtualization， NFV）環(huán)境下SFCs調度的虛擬帶寬分配和速率控制問題，提出了一種SFCs鏈式啟發(fā)式算法來向服務器節(jié)點分配VNFs的請求，最后使用了一種基于粒子群的貪婪啟發(fā)式算法優(yōu)化了速率和帶寬的分配。

1.2 DCNs擁塞控制

首次為DCNs設計的專用擁塞控制協議是Alizadeh等在2010年所提出的DC傳輸控制協議（DC transmission control protocol， DCTCP）^［24］，DCTCP的關鍵在于發(fā)送端能夠根據實際網絡的狀態(tài)發(fā)出接收端接收的正確數據包，由于交換機不需要大量緩存冗余數據，也就是說即使發(fā)生流錯誤傳輸時也不會導致超時重傳的現象，這就降低了傳輸時延。文獻［25］對DCTCP進行了改進，提出一種高帶寬超低時延協議（high-bandwidth ultra-low latency， HULL），該協議構建了一種可以預知擁塞鏈路并給小流預留帶寬的數據傳輸機制，在提高了帶寬使用效率的同時降低了時延。

在超大規(guī)模DCNs中出現突發(fā)流量的情況下，傳統(tǒng)終端交換機在使用DCTCP擁塞控制機制時，數據隊列容易發(fā)生丟包的現象。為了解決該問題，Cheng等^［26］提出拋棄負載（cut payload， CP）的方法，這是一種在交換機上輔助擁塞控制的機制，具體方法是，當檢測到即將發(fā)生擁塞時，CP立刻截取數據包的包頭，并沿用原有的TCP時鐘，使TCP狀態(tài)得以維持，并對鏈路進行相應的調整以緩解擁塞程度。Perry等^［27］通過將理論最優(yōu)的算法用于實際DCNs系統(tǒng)，提出了一種集中式的鏈路擁塞控制機制Fastpass，該機制摒棄了傳統(tǒng)的分布式解決時延問題的方式，采用集中控制的方法，通過在DCNs中設置一個仲裁器，根據發(fā)送端在傳輸數據時與仲裁器交互的信息來確定傳送速率和分配的路徑。這種做法不僅降低了隊列排隊延遲，還提高了帶寬鏈路的利用率和網絡中流之間的資源共享率。

Cho等^［28］設計一種端到端的基于Credit的擁塞控制協議ExpressPass。用戶在發(fā)送數據包之前，ExpressPass通過發(fā)送Credit包對擁塞進行探測，確保數據傳輸的低延遲，有效應對部分鏈路的突發(fā)流量。與傳統(tǒng)TCP不同，ExpressPass在需要發(fā)送數據時，會首先向接收端請求Credit，發(fā)送端只有在收到接收端返回的一個Credit時，才會發(fā)送一個數據包。然而，如何更精確地控制Credit和流鏈路帶寬分配仍需進一步研究和探索。為了解決DCNs數據流傳輸中服務器數據處理的延遲問題，Li等^［29］提出一種遠程直接數據存取的協議HPCC，利用網絡遙測技術（in network telemetry， INT）來獲取精確的鏈路負載信息，從而實現了準確地控制鏈路流量。HPCC通過解決在鏈路擁塞期間處理延遲的INT信息等問題，提高了帶寬利用率的同時使得算法快速收斂，緩解鏈路擁塞的同時保證了數據傳輸的低延遲。

針對鏈路容量的急劇增長產生的擁塞問題，Zhang等^［30］設計一種適合DCNs高速數據流的傳輸協議（fast and friendly converging， FFC），FFC通過從內網數據接收交換機端口檢索二維擁塞指示，實現細粒度擁塞測量，從而使流快速收斂到合適的發(fā)送速率性，同時只在終端主機上引入很少的部署開銷。針對擁塞導致的流傳輸排隊以及丟包導致的超時重傳問題，Abdelmoniem等^［31］提出一種DCNs流實時重傳的數據包丟失恢復機制（timely-retransmitted ACKs， T-RACKs），該機制對丟失的數據包可以及時地有效重傳，即使在數據包嚴重丟失的情況下，也可以克服長期重傳超時（retransmission timeout， RTO）的缺點。

為了緩解DCNs TCP Incast現象，文獻［32］提出一種自適應調步的通用方案AP（adaptive pacing， AP）可根據并發(fā)流的數量動態(tài)調整不同流傳輸的時間間隔，有效地防止了微突發(fā)情形下中的丟包。陸一飛等^［33］提出一種基于SDNs的TCP擁塞控制機制（TCP congestion control based on SDN， TCCS）， 具體做法是當鏈路出現擁塞時，通過臨時降低大象流的發(fā)送速率來預留帶寬，以滿足老鼠流的數據傳輸效率，有效緩解了TCP Incast現象。為了進一步解決DC鏈路擁塞問題，文獻［34］依據流量分布與不同流的特征，設計了一種基于光互聯架構的流量識別和調度方案（host-controller flow detection， HCFD），HCFD通過在主機端標記大象流特征，然后利用SDN控制器識別出鏈路中標記的大象流之后對其進行分類，最后根據DCNs全局鏈路流量分布情況下發(fā)流轉發(fā)策略。此外，機器學習算法在解決上述兩方面的問題時也表現出了非常良好的性能，近年來已經成為研究DCs先進的技術手段，國內外眾多科研工作者使用機器學習模擬探索了大規(guī)模DCNs流量工作與擁塞控制問題并取得了較多的研究成果^［35-40］。

2 DCNs系統(tǒng)模型

2.1 網絡模型

目前DCNs大多采用具有多路徑特性的拓撲結構，如Fat-Tree、VL2等拓撲結構。在各種分層網絡架構中，近年來Fat-Tree拓撲因為其簡單且易操作的特性在很多DCNs中得到了廣泛應用?；贔at-Tree拓撲的優(yōu)異性能，本文采用Fat-Tree拓撲作為DCNs流量工程研究的網絡模型。Fat-Tree拓撲包含3層：核心層、匯聚層、邊緣層。其中，匯聚層的聚合交換機與邊緣層的邊緣交換組成多個Pod，每個Pod中的聚合交換機分別與同Pod中的所有邊緣交換機相連。每個Pod有k/2個聚合交換機與k/2個邊緣交換機，同時，每個邊緣交換機與k/2個主機相連。本文拓撲中用k表示Pod的數量，則Fat-Tree拓撲中有k²/4個核心交換機，k²/2個聚合交換機，k²/2個邊緣交換機與k³/4個主機。

本文選取k=4時的Fat-Tree作為DCNs的基本拓撲，如圖1所示。

2.2 能耗模型

在本文的DCNs能耗模型中，網絡能耗只考慮網絡中流傳輸時所有交換機的能耗^［41］。假設每個交換機有開啟或休眠兩種狀態(tài)，當與交換機相連的所有鏈路均未被占用時，交換機處于休眠狀態(tài)，其固定能耗為E_sleep，否則交換機處于開啟狀態(tài)，能耗為E_active，且E_sleeplt;E_active。交換機開啟時其能耗與其開啟的端口數和端口利用率呈線性相關^［42］，其中與服務器相連的端口能耗記為EPort_host，交換機之間相連的端口能耗記為EPort_switch。交換機與服務器相連的端口需要時刻監(jiān)測網絡信息，因此此類端口保持開啟狀態(tài)，不會休眠。

交換機之間的端口會根據網絡狀態(tài)的變化而開啟或休眠，休眠狀態(tài)的交換機能耗E_sleep和開啟狀態(tài)下交換機能耗E_active分別如下所示：

E_sleep=e₁（1）

式中：e₁表示休眠交換機的固定能耗，e₁gt;0;e₂表示開啟狀態(tài)下交換機的固定能耗，e₂gt;0;n₁為交換機與服務器相連的端口數量；n₂為交換機之間相連的端口數量。

EPort_host和EPort_switch分別如下所示：

EPort_host=e₃（3）

EPort_switch=e₄+r·（e₃－e₄）（4）

式中：e₄為端口在休眠狀態(tài)下所產生的固定能耗，e₄gt;0;e₃為端口在開啟狀態(tài)下的最大能耗，0lt;e₄lt;e₃;r為端口利用率，0lt;rlt;1。第i個端口的端口利用率r_i計算公式為該端口所連鏈路的已用帶寬b_i與鏈路容量C上限的比值：

r_i=b_i/C（5）

綜上，由式（1）～式（5）得本文的網絡能耗為

E_Network=E_sleep+E_active（6）

3 DCNs能耗優(yōu)化模型及其近似求解策略EERA

3.1 DCNs能耗優(yōu)化模型

為了實現控制器對DCNs中數據流的高效管理以及調度，需要在控制器中保存數據流的一些詳細信息，用五元組f_i=（p_i，q_i，b_i，s_i，τ_i）來代表一個數據流。其中，p_i，q_i，b_i，s_i，τ_i分別表示第i個數據流的源節(jié)點、目的節(jié)點、數據量、到達時間、截止時間。

本文的主要優(yōu)化目標是優(yōu)化DCNs的能耗，故而建立如下的單目標非線性優(yōu)化模型：

C₁為流量約束，δ⁺（v）表示以節(jié)點v為起點的所有有向邊的集合，δ^－（v）表示以節(jié)點v為終點的所有有向邊的集合，x_i，e（t）表示第i個數據流請求在連接e上的第t個時刻的傳輸數據量，N⁺表示正整數集合。該約束的含義是，在傳輸時間段內的任意一個數據流在所有它的源目的節(jié)點之外的節(jié)點上的所有時刻上必須滿足流量守恒，即從該節(jié)點流出的屬于該數據流的流量之和必須等于流入該節(jié)點的屬于該數據流的流量之和。

C₂為另一個流量約束，δ⁺（p_i）表示以節(jié)點p_i為起點的所有有向邊的集合，δ^－（p_i）表示以節(jié)點p_i為終點的所有有向邊的集合。其中約束保證了任意一個數據流的源節(jié)點流出的屬于該數據流的流量之和減去流入源節(jié)點的屬于該數據流的流量之和在所有時刻上求和等于該數據流的總數據傳輸量，進而保證所有數據流可以在規(guī)定時間內傳輸完成。

C₃為容量約束，表示任意一條鏈路在任意傳輸時刻傳輸的流量之和不應超過鏈路的容量上限。

3.2 EERA以及實施步驟

在理想的節(jié)能路由方案中，構建流路由拓撲應以最少使用交換機和鏈路的方式為目標。例如，Bagaa等^［43］基于傳統(tǒng)網絡架構，考慮用戶的移動環(huán)境以及 QoS需求提出一種啟發(fā)式路徑重計算（heuristic paths re-computation， HPR）算法。HPR算法在滿足算法執(zhí)行合理計算時間的前提下，有效地降低了網絡運營支出成本（operating expenditure， OPEX），減少了交換機的使用數量，使得SDN支持的網絡運營商在考慮設備移動性的情況下依然可以合理分配網絡資源，從而減少甚至消除過度的資源供應。Muhammad等^［44］提出一種能耗感知容錯（energy-aware fault-tolerant， EAFT）算法，該算法在調度資源時實現了DCNs能耗和容錯之間的權衡。然而，類似的流量調度方案并沒有考慮到網絡整體流量負載均衡，影響到網絡的性能，無法直接用于DCNs。

本文考慮DCNs網絡整體流量負載均衡，在第3.1節(jié)中建立了DCNs流量約束的能耗優(yōu)化模型，為了求解該單目標優(yōu)化模型，本文介紹了一種DCNs基于帶寬匹配的啟發(fā)式算法EERA進行近似求解。EERA主要思想是：首先對數據流按照截止時間優(yōu)先級進行排序，然后將每個數據流分配到與其所傳輸數據量最佳匹配的路徑上，實現鏈路的最大利用率，從而節(jié)省了網絡的能耗。EERA的數據流路由尋找流程如下所述：

步驟 1 將DCNs拓撲結構抽象為無向圖G=（V，E，W），其中節(jié)點V代表DCNs中的交換機和服務器集合，E是無向圖的邊集，表示所有鏈路的集合，W表示無向圖G中鏈路的帶寬集合，其中對于邊（u，v）和邊（v，u），w_u，v=w_v，u。DCNs開始運行SDN控制器，獲得傳輸時隙內數據流集合F中每個數據流f_i的源節(jié)點、目的節(jié)點、數據量、到達時間以及截止時間。

步驟 2 對F中的每個數據流按照截止時間τ_i的先后進行排序，排序過后的數據流集合記為F′。

步驟 3 對于F′中的每個數據流，當接入服務器申請帶寬時，按照其數據量所需帶寬對拓撲圖進行更新，刪除不滿足數據量傳輸需求的鏈路，得到新的拓撲G′=（V′，E′，W′）。

步驟 4 在拓撲G′中，尋找當前數據流源節(jié)點到目的節(jié)點之間的可行數據傳輸鏈路，如果沒有滿足條件的可行鏈路則放棄該流的鏈路以及帶寬分配，返回上一步直接對F′中下一個數據流進行路由;否則，從所有可行鏈路中，選擇與數據量所需帶寬數值最接近的一條鏈路作為該流的路由方案并對其進行帶寬分配。

步驟 5 如果F′中還有數據流，返回步驟3;否則，算法終止，根據算法結果生成流量調度方案，對DCNs中每條流進行鏈路、帶寬分配并且進行流量調度。

算法1如下所示。

4 仿真分析

4.1 實驗設置

本文的仿真實驗硬件環(huán)境為Win10 64位系統(tǒng)、CPU處理器 Intel Core i5-4300U 2.50 GHz，內存4.00 GB，仿真軟件為Visual studio 2022。

4.1.1 仿真參數設置

DCNs拓撲圖如圖1所示，仿真拓撲中包括20個4端口的交換機、16個服務器和48條鏈路，數據流的開始時間和截止時間在［0，16］s內服從隨機分布，流的大小在［5，50］MB區(qū)間服從隨機分布，表1給出了實驗的主要參數。

表1 主要參數

Table 1 Main parameters參數含義數值e₁交換機休眠狀態(tài)固定能耗/J240 e₂交換機開啟狀態(tài)固定能耗/J310 e₃交換機端口滿載狀態(tài)能耗/J4 e₄交換機端口空載狀態(tài)能耗/J2 CDCNs鏈路容量/Mbps1004.1.2 實驗對比算法

為了驗證本文所提EERA算法的有效性，本文除了與近幾年性能優(yōu)異的HPR^［43］、EAFT^［44］算法進行對比外，還選擇了以下兩種經典的流調度方法進行性能比較：

最短路徑優(yōu)先（shortest path first， SPF）^［45］：SPF算法是開放式最短路徑優(yōu)先（open shortest path first， OSPF）路由協議的基礎，該算法將每一個路由器作為根來計算其到每一個目的路由器的距離，每一個路由器根據一個統(tǒng)一的數據集計算出路由域的拓撲結構圖，是一種經典且有效的路由協議。

等價多路徑路由（equal-cost multi-path routing， ECMP）算法^［46］：ECMP算法的主要策略是從所有等長的最短路徑中隨機分配一條路徑作為路由路徑，該算法復雜度低、易操作，是目前DCs解決負載均衡所采用的主要方法。

4.2 仿真性能指標

DCNs性能指標主要包括網絡的總能耗、吞吐量以及流的接受率。其中，網絡能耗的計算方式在第2.2節(jié)已經給出;吞吐量的計算公式為b_i×h，b_i表示接入用戶申請的寬帶，h表示該數據流傳輸路徑的跳數。數據流接受率的計算公式為f_N1/f_n，f_N1表示一個傳送周期內流傳送成功的數據流數量，f_n表示該周期內的數據流總數。在實驗中，本文通過假設接入數據流的數量分別為100條、200條、300條、400條、500條，來模擬不同負載的流量。

4.2.1 網絡能耗

圖2給出了幾種算法的網絡能耗比較圖，圖中直方圖按照交換機能耗的類型進行了分塊，自下向上依次是：激活交換機能耗、休眠交換機能耗和端口能耗。圖2（a）～圖2（e）分別給出了傳輸的數據流數目為100、200、300、400以及500條時的網絡能耗，從圖中可以看出EERA的能耗均少于其余4種算法。這是因為EERA首先按照流截止時間對數據流進行了排序，這樣做可以讓先截止的流盡可能早地調度完成騰出富余鏈路。對于在HPR、SPF、ECMP算法中，到達時間早、持續(xù)時間長且攜帶數據量大的數據流，會占用太多的網絡資源，導致交換機過早地處于激活狀態(tài)從而導致DCNs能耗的增加，而EAFT算法雖然當鏈路發(fā)生故障時會重新路由，但其路由方法仍是基于ECMP的，因此當數據流數目增加時，能耗優(yōu)化效果有所衰減。

圖3分別給出了DCNs在不同數據流數量下激活交換機、休眠交換機以及交換機端口能耗比較圖。

由圖3可以看出，EERA在激活交換機能耗和端口能耗上明顯少于其余4種算法，而在休眠交換機能耗上明顯多于其余3種算法。其中，從圖3（a）和圖3（b）中可以看出，在數據流規(guī)模較小時（f_N1=100），EERA的交換機能耗與其他算法的差距非常明顯，這是因為EERA通過對數據流截止時間排序進而對數據流集中調度，并且通過帶寬匹配策略充分利用了已激活節(jié)點和已激活鏈路，而不會過早激活剩余休眠節(jié)點。雖然HPR算法以復用已激活交換機節(jié)點為核心優(yōu)化思想，但是無法以合理的方式對持續(xù)時間長并攜帶著大量數據的流進行調度，導致這類數據流占用過多網絡資源，造成能耗增加。

表2給出了5種算法網絡能耗的具體類型比例分布。從表2可以看出隨著數據流數量的增加，除了HPR算法在數據流為400條相較于數據流為300條時增加，其他算法的端口能耗占比都在緩慢增加，這是因為當數據流規(guī)模變大時，DCNs中的鏈路容量瞬間達到上限，交換機也被全部激活。HPR、SPF、ECMP 3種算法端口能耗均僅增加不到1%，這是因為隨著網絡流的增加，過重的負載導致網絡波動的加劇，從而網絡負載會變得不均衡，造成了鏈路擁塞，尤其當數據流數目大于300時，端口能耗增加量有限。當數據流數目從400增加到500時，HPR算法相對SPF算法的端口能耗占比增值更明顯一些，這是因為HPR算法根據網絡中的節(jié)點狀態(tài)對鏈路權值進行重新定義，從而更新路由。EERA和EAFT算法端口占比能耗增加了超過一倍，這是因為數據流規(guī)模較小時，EERA的網絡能耗大部分是休眠節(jié)點的固定能耗，但隨著數據流增多，其優(yōu)越的負載均衡性能令網絡的擁塞情況得到改善，EAFT算法則是得益于其重路由策略。

4.2.2 網絡吞吐量

網絡吞吐量在很大程度上取決于DCNs流量管理策略。為了評估EERA負載平衡路由的效率，本文測試了不同數據流數量下的網絡吞吐量，仿真結果如圖4所示。由圖4可以看出，在不同數量的數據流下，EERA相較其他4種算法實現了更高的吞吐量。這是因為隨著數據流數目的增加，ECMP根據哈希值將流隨機分配到一條路由，而不考慮鏈路的利用率，這種高度不均勻的流量分布在某些鏈路上造成擁塞，而使其他鏈路空閑，因此，隨著流量的增加，容易造成鏈路的擁塞從而導致數據包的丟失，吞吐量受到限制。

在HPR算法中，傳輸節(jié)點的選擇傾向于那些已經處于激活狀態(tài)的交換機，數據傳輸路徑會一直被占用到鏈路帶寬不滿足數據流的帶寬要求時才停止，這造成了休眠狀態(tài)節(jié)點資源的浪費，降低了資源分配效率，這種貪婪的方法可能會導致即將到來的數據流沒有滿足其帶寬需求的路徑。SPF算法也是由于其貪婪地選擇最短的跳數作為傳輸路徑而忽略了整體的負載均衡，造成了網絡擁塞。在數據流數量為500時，EERA優(yōu)化效果更加明顯，這是由于此時網絡負載達到了上限，基于ECMP重路由的EAFT算法此時也會遇到擁塞問題，而EERA通過選擇一個與數據流所需帶寬最匹配的路徑，從而在調度過程中給后續(xù)流預留了更多的可用帶寬，而如果選擇一個與流所需帶寬相差較大的路徑，那么在后續(xù)流的調度過程中，就可能會出現可用帶寬不足的情況，導致數據流傳輸延遲或丟包。

4.2.3 數據流接受率

圖5給出了DCNs數據流的接受率，本文對5組數據流（100條、200條、300條、400條、500條）分別進行了數據流接受率的仿真。從圖5中可以看出，EERA的數據流接受率在不同數據流規(guī)模下都是最高的。這是因為ECMP算法是在所有等價路徑中隨機路由，容易造成鏈路擁塞，導致大量數據流傳輸失敗。而HPR與SPF算法貪婪地選擇節(jié)點最少的路徑從而給鏈路負載帶來了極大負擔，隨著數據流數量的增加，因為部分鏈路負載的增加令鏈路容量很快接近其最大值甚至超過容量，容易造成部分數據的丟失，從而降低數據流的接受率。

EERA算法通過預留帶寬的方式有效地降低了擁塞發(fā)生的概率，EAFT算法雖然也表現出很良好的效果，但是當數據流規(guī)模增加到500條時明顯劣于EERA算法，這是因為當數據流數目達到網絡負載上限時，EAFT算法基于ECMP的重路由策略會使鏈路擁塞，其他3種算法在數據流規(guī)模為500條時的接受率降到不足30%，而EERA算法依然維持在接近60%左右的接受水平，這就表明了本文所提算法EERA在數據流接受率方面的優(yōu)異性能。

5 結束語

隨著DCs數量和規(guī)模的不斷增加，數據流的數量以及大小也在呈指數級增加，DCs運營面臨著更加嚴峻的節(jié)能和負載均衡問題。本文對基于SDN的DCNs流量調度問題進行了研究，主要利用SDN對DCNs集中控制的特點和優(yōu)勢，提出一種基于帶寬匹配的軟件定義DCNs EERA。該算法通過SDN控制器對DCNs中具有截止時間限制的流依照其傳輸數據量進行集中調度從而優(yōu)化其能耗效率與負載均衡效率，最后仿真結果驗證了EERA的系統(tǒng)性能，實現了在不增加額外存儲OPEX的前提下，節(jié)省網絡能耗的同時實現了網絡負載均衡。在將來的工作中將考慮引入一些VNF技術，結合VMs節(jié)能方法可以最大限度減少物理服務器數量和遷移時間，借助SDN實現DCNs管控自動化并保證QoS，通過DCNs節(jié)能技術有效地協同降低DCs系統(tǒng)和網絡設備的能耗。

參考文獻

［1］JIANG C W， TSENG C L， WANG Y Z， et al. Optimal pricing strategy for data center considering demand response and renewable energy source accommodation［J］. Journal of Modern Power Systems and Clean Energy， 2023， 11（1）： 345-354.

［2］XU G， DAI B， HUANG B X， et al. Bandwidth-aware energy efficient flow scheduling with SDN in data center networks［J］. Future Generation Computer Systems， 2017， 68： 163-174.

［3］左青云， 陳鳴， 王秀磊， 等. 一種基于SDN的在線流量異常檢測方法［J］. 西安電子科技大學學報， 2015， 42（1）： 155-160.

ZUO Q Y， CHEN M， WANG X L， et al. Online traffic anomaly detection method for SDN［J］. Journal of Xidian University， 2015， 42（1）： 155-160.

［4］杜鑫樂， 徐恪， 李彤， 等. 數據中心網絡的流量控制： 研究現狀與趨勢［J］. 計算機學報， 2021， 44（7）： 1287-1309.

DU X L， XU K， LI T， et al. Traffic control for data center network： state of the art and future research［J］. Chinese Journal of Computers， 2021， 44（7）： 1287-1309.

［5］ALASMAR M， PARISIS G， CROWCROFT J. SCDP： systematic rateless coding for efficient data transport in data centers［J］. IEEE/ACM Trans.on Networking， 2021， 29（6）： 2723-2736.

［6］LUO S X， YU H F， LI K， et al. Efficient file dissemination in data center networks with priority-based adaptive multicast［J］. IEEE Journal on Selected Areas in Communications， 2020， 38（6）： 1161-1175.

［7］WANG L， ZHANG F， AROCA J A， et al. GreenDCN： a general framework for achieving energy efficiency in data center networks［J］. IEEE Journal on Selected Areas in Communications， 2013， 32（1）： 4-15.

［8］LI D， YU Y R， HE W， et al. Willow： saving data center network energy for network-limited flows［J］. IEEE Trans.on Pa-rallel and Distributed Systems， 2014， 26（9）： 2610-2620.

［9］YAO Z， WANG Y， BA J H， et al. Deadline-aware and energy-efficient dynamic flow scheduling in data center network［C］∥Proc.of the 13th International Conference on Network and Ser-vice Management， 2017.

［10］CUI Y， XIAO S H， WANG X， et al. Performance-aware energy optimization on mobile devices in cellular network［J］. IEEE Trans.on Mobile Computing， 2016， 16（4）： 1073-1089.

［11］CHKIRBENE Z， GOUISSEM A， HADJIDJ R， et al. Efficient techniques for energy saving in data center networks［J］. Computer Communications， 2018， 129： 111-124.

［12］GUO Z H， XU Y， LIU Y F， et al. AggreFlow： achieving power efficiency， load balancing， and quality of service in data center networks［J］. IEEE/ACM Trans.on Networking， 2020， 29（1）： 17-33.

［13］HUANG J W， LYU W J， LI W H， et al. Mitigating packet reordering for random packet spraying in data center networks［J］. IEEE/ACM Trans.on Networking， 2021， 29（3）： 1183-1196.

［14］CHENG Y Y， JIA X H. NAMP： network-aware multipathing in software-defined data center networks［J］. IEEE/ACM Trans.on Networking， 2020， 28（2）： 846-859.

［15］WANG F， YAO H P， ZHANG Q， et al. Dynamic distributed multi-path aided load balancing for optical data center networks［J］. IEEE Trans.on Network and Service Management， 2021， 19（2）： 991-1005.

［16］WU Z R， DENG Y H， FENG H， et al. Blender： a container placement strategy by leveraging Zipf-like distribution within containerized data centers［J］. IEEE Trans.on Network and Service Management， 2021， 19（2）： 1382-1398.

［17］DESMOUCEAUX Y， ENGUEHARD M， CLAUSEN T H. Joint monitorless load-balancing and autoscaling for zero-wait-time in data centers［J］. IEEE Trans.on Network and Service Management， 2020， 18（1）： 672-686.

［18］崔子熙， 胡宇翔， 蘭巨龍， 等. 基于流分類的數據中心網絡負載均衡機制［J］. 電子學報， 2021， 49（3）： 559.

CUI Z X， HU Y X， LAN J L， et al. Load balancing based on flow classification for datacenter network［J］. Acta Electonica Sinica， 2021， 49（3）： 559.

［19］趙君， 馬中， 劉馳， 等. 一種多目標蟻群優(yōu)化的虛擬機放置算法［J］. 西安電子科技大學學報， 2015， 42（3）： 173-178.

ZHAO J， MA Z， LIU C， et al. Multi-objective ant colony optimization algorithm for virtual machine placement［J］. Journal of Xidian University， 2015， 42（3）： 173-178.

［20］FENG H， DENG Y H， ZHOU Y， et al. Towards heat-recirculation-aware virtual machine placement in data centers［J］. IEEE Trans.on Network and Service Management， 2021， 19（1）： 256-270.

［21］AYOUB O， DE SOUSA A， MENDIETA S， et al. Online virtual machine evacuation for disaster resilience in inter-data center networks［J］. IEEE Trans.on Network and Service Ma-nagement， 2021， 18（2）： 1990-2001.

［22］LI B Y， CHENG B， LIU X， et al. Joint resource optimization and delay-aware virtual network function migration in data center networks［J］. IEEE Trans.on Network and Service Management， 2021， 18（3）： 2960-2974.

［23］ZU J C， HU G Y， PENG D Y， et al. Fair scheduling and rate control for service function chain in NFV enabled data center［J］. IEEE Trans.on Network and Service Management， 2021， 18（3）： 2975-2986.

［24］ALIZADEH M， GREENBERG A， MALT D A， et al. Data center TCP （DCTCP）［C］∥Proc.of the ACM SIGCOMM 2010 Conference， 2010： 63-74.

［25］ALIZADEH M， KABBANI A， EDSALL T， et al. Less is more： trading a little bandwidth for ultra-low latency in the data center［C］∥Proc.of the 9th USENIX Symposium on Networked Systems Design and Implementation， 2012： 253-266.

［26］CHENG P， REN F， SHU R， et al. Catch the whole lot in an action： rapid precise packet loss notification in data center［C］∥Proc.of the 11th USENIX Symposium on Networked Systems Design and Implementation， 2014： 17-28.

［27］PERRY J， OUSTERHOUT A， BALAKRISHNAN H， et al. Fastpass： a centralized \"zero-queue\" datacenter network［C］∥Proc.of the ACM Conference on SIGCOMM， 2014： 307-318.

［28］CHO I， JANG K， HAN D. Credit-scheduled delay-dounded congestion control for datacenters［C］∥Proc.of the Conference of the ACM Special Interest Group on Data Communication， 2017： 239-252.

［29］LI Y， MIAO R， LIU H H， et al. HPCC： high precision congestion control［C］∥Proc.of the ACM Special Interest Group on Data Communication， 2019： 44-58.

［30］ZHANG T， HUANG J W， CHEN K， et al. Rethinking fast and friendly transport in data center networks［J］. IEEE/ACM Trans.on Networking， 2020， 28（5）： 2364-2377.

［31］ABDELMONIEM A M， BENSAOU B. T-RACKs： a faster recovery mechanism for TCP in data center networks［J］. IEEE/ACM Trans.on Networking， 2021， 29（3）： 1074-1087.

［32］ZOU S J， HUANG J W， WANG J X， et al. Flow-aware adaptive pacing to mitigate TCP incast in data center networks［J］. IEEE/ACM Trans.on Networking， 2020， 29（1）： 134-147.

［33］陸一飛， 朱書宏. 數據中心網絡下基于SDN的TCP擁塞控制機制研究與實現［J］. 計算機學報， 2017， 40（9）： 2167-2180.

LU Y F， ZHU S H. Research and implementation of TCP congestion control mechanism based on SDN in data center network［J］. Chinese Journal of Computers， 2017， 40（9）： 2167-2180.

［34］郭秉禮， 趙寧， 朱志文， 等. 數據中心中面向光互聯的流量識別與調度研究［J］. 通信學報， 2018， 39（9）： 122-128.

GUO B L， ZHAO N， ZHU Z W， et al. Research on traffic identification and scheduling based on optical interconnection architecture in data center［J］. Journal on Communications， 2018， 39（9）： 122-128.

［35］LIU G Y， GUO S T， XIAO B， et al. SDN-based traffic matrix estimation in data center networks through large size flow identification［J］. IEEE Trans.on Cloud Computing， 2019， 10（1）： 675-690.

［36］YU A， YANG H， NGUYEN K K， et al. Burst traffic scheduling for hybrid E/O switching DCN： an error feedback spiking neural network approach［J］. IEEE Trans.on Network and Service Management， 2020， 18（1）： 882-893.

［37］LIU W X， LU J J， CAI J， et al. DRL-PLink： deep reinforcement learning with private link approach for mix-flow scheduling in software-defined data-center networks［J］. IEEE Trans.on Network and Service Management， 2021， 19（2）： 1049-1064.

［38］ZHOU X， WANG R H， WEN Y G， et al. Joint IT-facility optimization for green data centers via deep reinforcement learning［J］. IEEE Network， 2021， 35（6）： 255-262.

［39］JIANG Y A， KODIALAM M， LAKSHMAN T V， et al. Resource allocation in data centers using fast reinforcement learning algorithms［J］. IEEE Trans.on Network and Service Ma-nagement， 2021， 18（4）： 4576-4588.

［40］WANG Y， LI Y T， WANG T， et al. Towards an energy-efficient data center network based on deep reinforcement learning［J］. Computer Networks， 2022， 210： 108939.

［41］魯垚光， 王興偉， 李福亮， 等. 軟件定義網絡中的動態(tài)負載均衡與節(jié)能機制［J］. 計算機學報， 2020， 43（10）： 1969-1982.

LU Y G， WANG X W， LI F L， et al. Dynamic load balancing and energy saving mechanism in software defined network［J］. Chinese Journal of Computers， 2020， 43（10）： 1969-1982.

［42］BIANZINO A P， CHAUDET C， ROSSI D， et al. A survey of green networking research［J］. IEEE Communications Surveys amp; Tutorials， 2010， 14（1）： 3-20.

［43］BAGAA M， DUTRA D L C， TALEB T， et al. On SDN-driven network optimization and QoS aware routing using multiple paths［J］. IEEE Trans.on Wireless Communications， 2020， 19（7）： 4700-4714.

［44］SHAUKAT M， ALASMARY W， ALANAZI E， et al. Balanced energy-aware and fault-tolerant data center scheduling［J］. Sensors， 2022， 22（4）： 1482.

［45］HE Q， WANG Y， WANG X W， et al. Routing optimization with deep reinforcement learning in knowledge defined networking［J］. IEEE Trans.on Mobile Computing， 2023， 23（2）： 1444-1455.

［46］LI Y， JIAN S J， HSIEH S Y， et al. A weighted optimal sche-duling scheme for congestion control in cloud data center networks［J］. IEEE Trans.on Services Computing， 2023， 16（4）： 2402-2410.

作者簡介

張朝輝（1987—），男，講師，博士，主要研究方向為網絡拓撲優(yōu)化、資源分配優(yōu)化。

周嘉琦（2000—），男，碩士研究生，主要研究方向為多智能體協作優(yōu)化。