姜 彬 喬紅宇

基于主動(dòng)隊(duì)列管理算法的綠色云模型

姜 彬1喬紅宇2

（1.江蘇航運(yùn)職業(yè)技術(shù)學(xué)院 智能制造與信息學(xué)院，江蘇 南通 226000；2.江蘇航運(yùn)職業(yè)技術(shù)學(xué)院 輪機(jī)工程學(xué)院，江蘇 南通 226000）

針對(duì)5G網(wǎng)絡(luò)低能耗和低延遲的要求，提出一種基于主動(dòng)隊(duì)列管理（Active Queue Management，AQM）算法的綠色云模型，該模型利用增強(qiáng)的隨機(jī)早期檢測(cè)算法并結(jié)合鏈接虛擬列表來實(shí)現(xiàn)數(shù)據(jù)包的智能優(yōu)先排序，通過降低重傳次數(shù)和減少排隊(duì)延遲來減輕聚合層隊(duì)列中的擁塞，在無需修改現(xiàn)有基礎(chǔ)設(shè)施的基礎(chǔ)上實(shí)現(xiàn)系統(tǒng)的低延遲和低能耗，達(dá)到節(jié)能環(huán)保的目的。研究結(jié)果表明：提出的模型與傳統(tǒng)的Cloud模型、Femtolet模型相比，在吞吐量、延遲以及能耗等三個(gè)方面效果更好，本文的方法是有效的。

綠色云計(jì)算；主動(dòng)隊(duì)列管理；擁塞；能耗

隨著云計(jì)算在物聯(lián)網(wǎng)系統(tǒng)、智能城市、電子醫(yī)療以及多媒體等眾多領(lǐng)域的快速擴(kuò)展，其高能耗與環(huán)境的影響問題越來越引起重視。綠色計(jì)算是本著對(duì)環(huán)境負(fù)責(zé)的原則使用計(jì)算機(jī)及相關(guān)資源的行為，綠色計(jì)算可以更加合理協(xié)調(diào)地利用計(jì)算資源，以低耗方式滿足日益多樣的計(jì)算需求[1]。綠色云計(jì)算是指在云計(jì)算環(huán)境中，通過有效地管理云計(jì)算，在滿足服務(wù)質(zhì)量(Quality of Service，QoS)的同時(shí)，解決云計(jì)算帶來的環(huán)境、能耗及運(yùn)營(yíng)成本問題。因此，綠色云計(jì)算的重點(diǎn)不在于重新研制低能耗的基礎(chǔ)設(shè)備，而是高效地整合利用現(xiàn)有資源，達(dá)到降低能耗、節(jié)能環(huán)保的目的[2-3]。

近年來，綠色云計(jì)算領(lǐng)域已經(jīng)引起全球研究人員的廣泛關(guān)注。針對(duì)云計(jì)算的能耗和資源利用問題，國內(nèi)外學(xué)者在綠色云計(jì)算技術(shù)方面取得了一系列重要的研究和應(yīng)用成果。金順福等[4]對(duì)比了綠色云調(diào)度算法與其他任務(wù)調(diào)度算法的能耗大小，綠色云調(diào)度算法通過采用多租戶方式和虛擬機(jī)實(shí)時(shí)遷移技術(shù)，使得程序調(diào)度的功耗更低。Rao等[5]針對(duì)綠色云計(jì)算中的能耗問題，提出了一種基于任務(wù)調(diào)度的資源感知負(fù)載均衡克隆算法。該算法在負(fù)載均衡策略中引入克隆選擇原理，解決了節(jié)能資源感知調(diào)度問題。Lu等[6]提出了一種用于異構(gòu)云環(huán)境的自適應(yīng)任務(wù)分配算法，該算法通過最小化云系統(tǒng)的完工時(shí)間來降低能耗，促進(jìn)綠色云計(jì)算。Mukherjee等[7]指出移動(dòng)邊緣計(jì)算可以將移動(dòng)計(jì)算、網(wǎng)絡(luò)控制和存儲(chǔ)推送到網(wǎng)絡(luò)邊緣，以便在資源有限的移動(dòng)設(shè)備上實(shí)現(xiàn)計(jì)算密集型和延遲要求高的應(yīng)用，移動(dòng)邊緣計(jì)算能夠大幅降低延遲和移動(dòng)能耗。Sun等[8]提出了一種綠色云網(wǎng)絡(luò)體系結(jié)構(gòu)，旨在用戶設(shè)備與其云中的軟件克隆之間提供無縫且端到端的低延遲。

目前，大多數(shù)方法都側(cè)重于云架構(gòu)和開發(fā)新的邊緣解決方案來實(shí)現(xiàn)降低能耗的目標(biāo)，這些研究均是在移動(dòng)設(shè)備（Mobile Device，MD）附近建立云體系。但是，這種方式為運(yùn)營(yíng)商帶來額外的成本，以及由于部署新的邊緣解決方案產(chǎn)生更多的能耗。針對(duì)上述問題，本文提出一種基于主動(dòng)隊(duì)列管理算法降低能耗的綠色云模型，通過對(duì)數(shù)據(jù)包進(jìn)行智能優(yōu)先排序，降低重傳次數(shù)來減輕聚合層隊(duì)列中的擁塞，在無需修改現(xiàn)有基礎(chǔ)設(shè)施的基礎(chǔ)上實(shí)現(xiàn)系統(tǒng)的低延遲和高能效。

1 主動(dòng)隊(duì)列管理

主動(dòng)隊(duì)列管理（Active Queue Management，AQM）是實(shí)現(xiàn)擁塞控制的重要手段，一直受到廣大研究人員的關(guān)注。目前，存在幾種基于不同理論的AQM算法，這些算法在一定程度上能夠?qū)崿F(xiàn)網(wǎng)絡(luò)擁塞控制的任務(wù)，但是在公平性和復(fù)雜度上有不同程度的缺陷。

1.1 隨機(jī)早期檢測(cè)算法

隨機(jī)早期檢測(cè)（Random Early Detection，RED）算法作為一個(gè)重要的AQM算法，通過檢測(cè)路由器緩沖區(qū)隊(duì)列的平均長(zhǎng)度來判斷擁塞。當(dāng)擁塞出現(xiàn)時(shí)，該算法采取隨機(jī)選擇連接來通知擁塞，在隊(duì)列溢出導(dǎo)致丟包之前減小擁塞窗口，降低發(fā)送數(shù)據(jù)速度，從而緩解網(wǎng)絡(luò)擁塞。

RED算法大致可以分為計(jì)算平均隊(duì)列長(zhǎng)度avg和丟包概率b兩部分。平均隊(duì)列長(zhǎng)度采用指數(shù)加權(quán)移動(dòng)平均值進(jìn)行估計(jì)，該估計(jì)類似帶權(quán)值的低通濾波器計(jì)算公式為

丟包概率的計(jì)算是根據(jù)隊(duì)列平均長(zhǎng)度計(jì)算的，算法將平均隊(duì)列保持在一定長(zhǎng)度，當(dāng)平均隊(duì)列長(zhǎng)度增加時(shí)，丟包概率也隨之增加。丟包概率b的分段函數(shù)可表示為

其中：min和max分別表示隊(duì)列長(zhǎng)度的最小閾值和最大閾值，max表示最大丟包概率。

丟包概率還與隊(duì)列中數(shù)據(jù)包的數(shù)量有關(guān)，為了避免連續(xù)丟包，丟包概率b修正為

其中：b表示上一次丟包到進(jìn)入當(dāng)前隊(duì)列的數(shù)據(jù)包的數(shù)量，a為丟包概率的修正值。其值的增加，會(huì)導(dǎo)致后序數(shù)據(jù)包丟失的可能性逐漸升高。丟包概率修正的目的是為了避免連續(xù)丟包，防止突發(fā)流偏見及全局同步現(xiàn)象的產(chǎn)生。

RED算法利用平均隊(duì)列長(zhǎng)度來判斷數(shù)據(jù)包的丟棄概率，這種方式無法對(duì)突然暴增的流量做出立即響應(yīng)。

1.2 增強(qiáng)RED

增強(qiáng)隨機(jī)早期檢測(cè)(Enhanced Random Early Detection，ENRED)算法是一種AQM算法，旨在保留RED優(yōu)點(diǎn)的同時(shí)，提供更好的網(wǎng)絡(luò)擁塞控制。該算法依靠對(duì)平均隊(duì)列大小的增強(qiáng)來限制隊(duì)列大小，在保證隊(duì)列更穩(wěn)定的同時(shí)，將延遲和數(shù)據(jù)包丟失率降到最低。當(dāng)前平均隊(duì)列大小為

丟包概率表示為

其中：C表示緩沖區(qū)溢出前的臨界隊(duì)列長(zhǎng)度。由于ENRED算法具有更多的擁塞窗口，因此可以實(shí)現(xiàn)穩(wěn)定的隊(duì)列長(zhǎng)度，有效降低延遲和丟包率。

2 基于主動(dòng)隊(duì)列管理的綠色云模型

本文提出一種基于主動(dòng)隊(duì)列管理的綠色云模型設(shè)計(jì)方法，該方法采用增強(qiáng)隨機(jī)早期檢測(cè)算法來控制網(wǎng)絡(luò)擁塞和減少排隊(duì)延遲，在保證系統(tǒng)穩(wěn)定可靠的基礎(chǔ)上，通過減少重傳次數(shù)的方式實(shí)現(xiàn)云端和移動(dòng)設(shè)備的低能耗、低延遲和高吞吐量。

2.1 模型設(shè)計(jì)和部署

重傳過程對(duì)于發(fā)射機(jī)和整個(gè)系統(tǒng)來說是消耗能量的，尤其是在異構(gòu)網(wǎng)絡(luò)中。此外，重傳會(huì)造成額外的信令開銷。因此，本文提出一種控制擁塞的新模型，作為減少重傳的方法，以最大限度地減少浪費(fèi)的能量，減少延遲并提高系統(tǒng)吞吐量。該模型通過實(shí)施ENRED算法來處理擁塞問題，以便管理由數(shù)據(jù)通信網(wǎng)絡(luò)（Data Communication Network，DCN）匯聚層內(nèi)的移動(dòng)節(jié)點(diǎn)傳入的數(shù)據(jù)包。通過減少擁塞導(dǎo)致的延遲和分組丟失來降低服務(wù)時(shí)間和重傳率，達(dá)到能量消耗最小化的目的。提出的方法在移動(dòng)分組調(diào)度中采用標(biāo)記概率來增加分組成功率，保證在連接期間延遲最小。同時(shí)，為核心層內(nèi)的每個(gè)POD（容器組）開發(fā)了可鏈接的虛擬列表（Virtual List，VL），該列表作為所有節(jié)點(diǎn)傳入數(shù)據(jù)包的緩存，可以保留所有數(shù)據(jù)包的類型、源IP、目標(biāo)IP和數(shù)據(jù)包長(zhǎng)度。VL可以根據(jù)數(shù)據(jù)包的類型和到達(dá)時(shí)間對(duì)其進(jìn)行優(yōu)先級(jí)排序。

本文模型設(shè)計(jì)示意圖如圖1所示，本文提出的方法通過擁塞控制算法和鏈接虛擬列表來減少服務(wù)時(shí)間，以及更好地控制隊(duì)列大小和丟棄率。降低擁塞可以在相同的時(shí)間內(nèi)增加服務(wù)分組的速率，增加系統(tǒng)吞吐量，同時(shí)云中的服務(wù)時(shí)間減少，導(dǎo)致負(fù)載功率降低，移動(dòng)設(shè)備能夠體現(xiàn)更多的節(jié)能。

圖1 本文模型設(shè)計(jì)示意圖

本文模型由于設(shè)計(jì)為在云網(wǎng)絡(luò)核心層和匯聚層內(nèi)實(shí)現(xiàn)，因此可以部署在動(dòng)態(tài)網(wǎng)絡(luò)環(huán)境中。該方法可以單獨(dú)使用，也可以與任何移動(dòng)邊緣計(jì)算場(chǎng)景（如Cloudlet、Femtocloud、Femtolet）配合使用，以進(jìn)一步提高能源效率，減少延遲，同時(shí)保持較高的系統(tǒng)吞吐量。在單獨(dú)使用場(chǎng)景中，MD通過移動(dòng)基站（base station，BS）將其請(qǐng)求發(fā)送到云，當(dāng)遇到BS沒有任何云計(jì)算或存儲(chǔ)功能時(shí)，模型接收請(qǐng)求，利用提出的算法減少匯聚層中的擁塞和服務(wù)器之間多層交換的流路徑，并在處理后將其響應(yīng)發(fā)送給MD。在移動(dòng)邊緣計(jì)算場(chǎng)景中，如果邊緣層具有執(zhí)行請(qǐng)求的能力，則MD通過BS將其請(qǐng)求首先發(fā)送到邊緣設(shè)備或中間層（Cloudlet，F(xiàn)emtocloud或Femtolet），處理請(qǐng)求并將響應(yīng)發(fā)送回MD，而無需本文模型的干預(yù)。但是，如果中間層不具有處理請(qǐng)求的能力，則邊緣設(shè)備將請(qǐng)求轉(zhuǎn)發(fā)到提出的模型上，經(jīng)過處理后發(fā)送回MD。

整個(gè)移動(dòng)系統(tǒng)的核心是數(shù)據(jù)中心基礎(chǔ)設(shè)施，所有流量都通過該基礎(chǔ)設(shè)施，因此基礎(chǔ)設(shè)施設(shè)計(jì)需要綜合考慮其彈性、性能和可擴(kuò)展性。本文提出的云模型涉及三層DCN架構(gòu)（接入層、匯聚層和核心層）如圖2所示。具體情況如下：接入層是允許服務(wù)器連接到網(wǎng)絡(luò)，因此接入層交換機(jī)具有低成本和高端口密度特性；匯聚層是多臺(tái)接入層交換機(jī)的匯聚點(diǎn)，處理來自接入層設(shè)備的所有通信量，并將流量轉(zhuǎn)發(fā)到核心層，故匯聚層交換機(jī)需要更高的性能、更少的接口和更高的交換速率；核心層將多個(gè)匯聚模塊連接到互聯(lián)網(wǎng)，并為通過數(shù)據(jù)中心的所有流量提供高速分組交換網(wǎng)關(guān)，所以核心層交換機(jī)應(yīng)該擁有更高的可靠性、性能和吞吐量。本文提出的模型是在匯聚層和核心層內(nèi)實(shí)現(xiàn)。

圖2 本文模型在DCN架構(gòu)中部署示意圖

2.2 模型算法

本文提出的模型算法包括擁塞檢測(cè)算法、增強(qiáng)隨機(jī)早期檢測(cè)算法和鏈接虛擬列表算法三部分組成。表1～3分別給出了三種算法的偽碼。

表1 擁塞檢測(cè)算法

整個(gè)算法操作如下：在初始階段，表1所列的“算法1”在每個(gè)移動(dòng)數(shù)據(jù)包到達(dá)之后檢查隊(duì)列擁塞，如果檢測(cè)到擁塞，則開始執(zhí)行表2所列的“算法2”。其中ENRED算法的ar值是根據(jù)最大和最小閾值獲得，數(shù)據(jù)包丟失率由式(6)和(7)計(jì)算得到。表3所列的“算法3”創(chuàng)建虛擬列表用來存儲(chǔ)接收的數(shù)據(jù)包信息，以便當(dāng)核心層訪問數(shù)據(jù)包時(shí)可以根據(jù)這些信息對(duì)其進(jìn)行優(yōu)先級(jí)排序。當(dāng)未檢測(cè)到擁塞時(shí)，執(zhí)行表3所列的“算法3”。

表2 增強(qiáng)隨機(jī)早期檢測(cè)算法

表2（續(xù)）

表3 鏈接虛擬列表算法

3 實(shí)驗(yàn)結(jié)果及分析

為了驗(yàn)證本文模型的性能，采用NS2網(wǎng)絡(luò)模擬軟件進(jìn)行仿真，仿真參數(shù)由表4給出。在仿真過程中，MD向移動(dòng)基站發(fā)送不同數(shù)量的請(qǐng)求，然后BS通過移動(dòng)網(wǎng)絡(luò)核心將請(qǐng)求轉(zhuǎn)發(fā)到因特網(wǎng)網(wǎng)關(guān)和處理請(qǐng)求的云，最后將其發(fā)送回MD。采用吞吐量、延遲、能耗三個(gè)指標(biāo)來評(píng)估模型的性能，并將結(jié)果與傳統(tǒng)Cloud模型、Femtolet模型[7]作對(duì)比。

表4 仿真參數(shù)

表4（續(xù)）

3.1 吞吐量

對(duì)網(wǎng)絡(luò)、設(shè)備、端口、虛電路或其他設(shè)施，單位時(shí)間內(nèi)成功地傳送數(shù)據(jù)的數(shù)量稱為吞吐量。當(dāng)考慮若干協(xié)議開銷時(shí)，有效速率則明顯低于最大吞吐量。為了定義網(wǎng)絡(luò)或連接的實(shí)際數(shù)據(jù)傳輸速率，可以采用實(shí)際吞吐量作為度量。其中，實(shí)際吞吐量的計(jì)算不包括數(shù)據(jù)包丟失、數(shù)據(jù)包重傳以及協(xié)議開銷。此外，吞吐量還受到數(shù)據(jù)包丟失率和調(diào)度算法的影響。利用NS2網(wǎng)絡(luò)模擬軟件在無線網(wǎng)絡(luò)中進(jìn)行仿真的吞吐量測(cè)試結(jié)果如圖3所示。與傳統(tǒng)Cloud模型相比，本文模型在吞吐量方面具有明顯的改進(jìn)效果；與作為多接入邊緣計(jì)算（Multi-access Edge Computing，MEC）解決方案之一的Femtolet模型相比，本文模型通過增強(qiáng)中間MEC層，以較少的邊緣計(jì)算實(shí)現(xiàn)了更高的吞吐量。

圖3 不同模型的吞吐量測(cè)試結(jié)果示意圖

3.2 延遲

在分組交換網(wǎng)絡(luò)中，延遲的測(cè)量方式有兩種：一是指從發(fā)送器發(fā)送數(shù)據(jù)包到接收數(shù)據(jù)包的接收器的時(shí)間；二是指包括從發(fā)送器到接收器的延遲以及從接收器返回發(fā)送器的延遲的往返延遲時(shí)間。一般而言，往返延遲更常用，因?yàn)樵撗舆t可以從單個(gè)點(diǎn)位置進(jìn)行測(cè)量。

當(dāng)網(wǎng)關(guān)接收到多個(gè)來自不同源卻具有相同目的地的數(shù)據(jù)包時(shí)，就會(huì)發(fā)生排隊(duì)延遲。由于一次只能對(duì)一個(gè)數(shù)據(jù)包進(jìn)行重新路由，因此許多數(shù)據(jù)包必須排隊(duì)等待傳送，從而產(chǎn)生額外的延遲?？紤]到延遲限制了雙向通信系統(tǒng)中的總吞吐量并且被視為擁塞最準(zhǔn)確的度量，因此將其作為評(píng)估所提出的主動(dòng)隊(duì)列管理機(jī)制和鏈接的虛擬列表的性能指標(biāo)。本文模型的延遲測(cè)量結(jié)果如圖4中所示，從圖4可見：同傳統(tǒng)的Cloud模型和Femtolet模型相比，本文的模型在不同數(shù)量的數(shù)據(jù)包傳輸中的延遲最低，表明隊(duì)列中移動(dòng)分組調(diào)度的成功率明顯增強(qiáng)。

圖4 不同模型的延遲量測(cè)試結(jié)果圖

3.3 能耗

由于云服務(wù)中的數(shù)據(jù)在數(shù)據(jù)中心進(jìn)行處理和存儲(chǔ)，因此分布式控制系統(tǒng)是降低云計(jì)算應(yīng)用程序和服務(wù)能耗的焦點(diǎn)。為了提高分布式控制系統(tǒng)的能源效率，人們采用了幾種策略，包括能量比例計(jì)算、動(dòng)態(tài)供應(yīng)、冷卻方法以及虛擬化。在絕大多數(shù)云服務(wù)能耗研究中，能耗被認(rèn)為是云應(yīng)用和服務(wù)的總能耗。然而，傳輸網(wǎng)絡(luò)和最終用戶設(shè)備是云的基本組件。因此，云的能量消耗應(yīng)從三個(gè)方面進(jìn)行考慮，即訪問云的移動(dòng)設(shè)備能耗、連接移動(dòng)設(shè)備到云的傳輸網(wǎng)絡(luò)能耗以及數(shù)據(jù)中心的能耗。

本文提出的算法通過減輕數(shù)據(jù)中心的擁塞和數(shù)據(jù)包過載，減少數(shù)據(jù)包丟失率和重傳率，從而減少服務(wù)時(shí)間，最終降低能耗。因此，本文模型在云端和移動(dòng)設(shè)備端實(shí)現(xiàn)了較低的能耗?？紤]到云中服務(wù)時(shí)間的縮短會(huì)導(dǎo)致負(fù)載功率的降低，移動(dòng)設(shè)備的節(jié)能效果更佳。能量消耗反映了吞吐量和延遲之間的相關(guān)性。使用不同數(shù)量數(shù)據(jù)包時(shí)三個(gè)模型的能耗值如圖5所示。

圖5 不同模型的總能耗測(cè)試結(jié)果圖

從圖5可見：本文提出的模型在總能耗方面優(yōu)于其他兩類模型。

4 結(jié) 語

本文針對(duì)5G網(wǎng)絡(luò)低能耗和低延遲的要求，提出了一種基于主動(dòng)隊(duì)列管理算法的綠色云模型，該模型通過利用主動(dòng)隊(duì)列管理（AQM）機(jī)制來減少云聚合層的擁塞，在核心層實(shí)現(xiàn)鏈接虛擬列表，進(jìn)一步增強(qiáng)響應(yīng)時(shí)間，降低丟包率和減少延遲，從而節(jié)省重傳浪費(fèi)的能量，最終降低云和移動(dòng)設(shè)備的能耗。研究結(jié)果表明：提出的模型在吞吐量、延遲以及能耗等三個(gè)方面的性能突出，優(yōu)于其他兩類模型。

[1]過敏意.綠色計(jì)算:內(nèi)涵及趨勢(shì)[J].計(jì)算機(jī)工程,2010,36(10): 1-7.

[2]ZHOU R T, LI Z P, WU C. A truthful online mechanism for location-aware tasks in mobile crowd sensing[J]. IEEE Transactions on Mobile Computing, 2018, 17(8): 1737-1749.

[3]MORE N S, INGLE R B. Challenges in Green Computing for Energy Saving Techniques[C] //2017 International Conference on Emerging Trends & Innovation in ICT (ICEI). February 3-5, 2017, Pune, India. IEEE, 2017: 73-76.

[4]金順福,王寶帥,郝閃閃,等.基于備用虛擬機(jī)同步休眠的云數(shù)據(jù)中心節(jié)能策略及性能[J].吉林大學(xué)學(xué)報(bào)(工學(xué)版), 2018,48(6):1859-1866.

[5]RAO G J, BABU G S. Energy analysis of task scheduling algorithms in green cloud[C]//2017 International Conference on Innovative Mechanisms for Industry Applications (ICIMIA). February 21-23, 2017, Bengaluru, India. IEEE, 2017:302-305.

[6]LU Y, SUN N. An effective task scheduling algorithm based on dynamic energy management and efficient resource utilization in green cloud computing environment[J]. Cluster Computing, 2019, 22(1): 513-520.

[7]MUKHERJEE A, DE D. Femtolet: A novel fifth generation network device for green mobile cloud computing[J]. Simulation Modelling Practice and Theory,2016, 62:68-87.

[8]SUN X, ANSARI N. Green Cloudlet Network: A Distrib- uted Green Mobile Cloud Network[J]. IEEE Network, 2017, 31(1): 64-70.

TP393

A

1673-2219（2021）03-0053-05

2020-05-03

江蘇省教育廳蘇教科﹝2017﹞5號(hào)，省高校自然科學(xué)研究面上項(xiàng)目“基于滑模模糊控制器的不確定隨機(jī)非線性系統(tǒng)魯棒性研究”（項(xiàng)目編號(hào)17KJD413001）。

姜彬（1980－），男，江蘇如皋人，副教授，研究方向?yàn)槿斯ぶ悄芘c智能系統(tǒng)。喬紅宇（1982－），男，江蘇淮安人，副教授，研究方向?yàn)檩啓C(jī)自動(dòng)化。

（責(zé)任編校：宮彥軍）