云計算下一種聚合流的有效帶寬接納控制方法

余 建 ，楊曉冬 ，劉孫發(fā) （1.三明學(xué)院 網(wǎng)絡(luò)中心， 福建 三明，65004；

2.物聯(lián)網(wǎng)應(yīng)用福建省高校工程研究中心,福建 三明，365004；3.三明學(xué)院 圖書館，福建 三明，365004）

隨著計算機(jī)網(wǎng)絡(luò)技術(shù)的發(fā)展，云計算[1]在快速為用戶提供資源的同時，還需具備可靠性、可用性、可擴(kuò)展等完備的服務(wù)質(zhì)量（QoS）保證機(jī)制，確保系統(tǒng)執(zhí)行的高效性[2-3]。近年來，云服務(wù)的數(shù)量與種類呈爆炸式增長，網(wǎng)絡(luò)流量也不斷增加，導(dǎo)致網(wǎng)絡(luò)負(fù)載較大。用戶對QoS的要求也越來越高，傳統(tǒng)的單流接納控制已經(jīng)不能滿足用戶需求。作為一種有效的預(yù)防性流量控制手段，接納控制[4-6]是避免網(wǎng)絡(luò)擁塞、保障云服務(wù)質(zhì)量的有效方法之一。

在云計算網(wǎng)絡(luò)中，接納控制作為網(wǎng)絡(luò)流量擁塞控制和服務(wù)質(zhì)量保障的有效手段，得到了越來越多專家學(xué)者的關(guān)注。文獻(xiàn)[7]中提出了一種基于負(fù)載傳遞的聯(lián)合接納控制算法，用戶申請接入時，引入動態(tài)負(fù)載流量傳輸，通過建立異構(gòu)網(wǎng)絡(luò)的QoS性能指標(biāo)，以此限制用戶流量。文獻(xiàn)[8]提出了一種呼叫接納控制（call admission control，CAC）算法，聯(lián)合帶寬系數(shù)權(quán)重以及帶寬降級策略，利用呼叫接納控制對已接入呼叫中權(quán)重系數(shù)最小的用戶進(jìn)行帶寬限制，再根據(jù)切換和新到達(dá)呼叫的優(yōu)先級，來分配相應(yīng)的帶寬資源。文獻(xiàn)[9]中通過在LTE系統(tǒng)中提出一種基于排隊機(jī)制的動態(tài)資源預(yù)留算法，通過設(shè)置一定的閥值資源，以新呼叫的形式定義請求接入，在無可用資源的情況下，對其他資源以排隊方法等待接入。目前在無線網(wǎng)絡(luò)中使用較多的是呼叫接納控制，其在保障接入用戶的通信質(zhì)量、降低系統(tǒng)阻塞率、控制傳輸速率等許多方面都扮演著關(guān)鍵角色。馬爾可夫決策過程是解決無線通信中決策問題的一種有效方法[10]，在接納控制策略的研究中起重要作用。云計算在提供服務(wù)能力和服務(wù)資源滿足用戶應(yīng)用需求的同時，還需要具備可靠性、可用性、可擴(kuò)展性等完備的QoS保證機(jī)制，確保其系統(tǒng)執(zhí)行的高效性。接納控制技術(shù)是保障其系統(tǒng)高速有效運行的重要部分，也是云計算的前提保障。

聚合流[11]可以理解成無數(shù)網(wǎng)絡(luò)依次到達(dá)，疊加組成的流量。聚合網(wǎng)絡(luò)流量由多個網(wǎng)絡(luò)用戶數(shù)據(jù)源組成，在每個網(wǎng)絡(luò)用戶數(shù)據(jù)源的內(nèi)部，數(shù)據(jù)的流動都有其行為模式，數(shù)據(jù)包間的到達(dá)間隔同樣也遵循一定的到達(dá)規(guī)律。將所有用戶數(shù)據(jù)源的數(shù)據(jù)包疊加后，便是聚合流。

1 聚合流的有效帶寬接納控制模型

云計算雖說是以傳統(tǒng)網(wǎng)絡(luò)為基礎(chǔ)，但其接納控制模型卻不同于傳統(tǒng)網(wǎng)絡(luò)[12]。云計算中的接納控制必須滿足在保證QoS的前提下，不影響其他服務(wù)運行，考慮到云計算服務(wù)請求的高并發(fā)性，在多個請求在整形器的作用下進(jìn)入到等待區(qū)后形成聚合流，然后通過接納控制模塊從入口節(jié)點進(jìn)入到云服務(wù)中。由于傳統(tǒng)的單流接納控制方法只能同時處理一個請求，當(dāng)多個單流同時進(jìn)入到入口節(jié)點后，等待處理的時延加大，用戶體驗效果不佳。為了提升網(wǎng)絡(luò)并發(fā)處理能力，提升云服務(wù)的QoS，本文提出了一種基于聚合流的接納控制算法，該算法通過估計聚合流所需的帶寬來執(zhí)行接納控制，能同時處理多個服務(wù)請求，云計算環(huán)境下的接納控制模型如圖1所示。

圖1 聚合流的有效帶寬接納控制模型

在圖1中，用戶請求云計算服務(wù)的異構(gòu)流經(jīng)過整形器整形后，再通過FIFO復(fù)用模塊調(diào)用，接納控制模塊將對復(fù)用模塊輸出的聚合流執(zhí)行接納控制，異構(gòu)流合并復(fù)用時會進(jìn)入到等待區(qū)，在網(wǎng)絡(luò)入口節(jié)點流量一定時，能同時處理多個業(yè)務(wù)請求。

2 聚合流的有效帶寬模式

2.1 網(wǎng)絡(luò)聚合流

給定一個有向圖B=(V,E)，在V中指定兩點，其中一點稱為發(fā)點（記為v1），另一點稱為收點（記為vn，n是B的頂點個數(shù)），其余的點v2,v3,…，vn-1稱為中間點。對于每一個(vi,vj)∈E對應(yīng)有一個cij(cij≥0)，稱為弧的容量。把這樣的B叫作一個網(wǎng)絡(luò)，記為B=(V,E,C)?；〖螮上的一個函數(shù)f={f(vi,vj)}，稱為網(wǎng)絡(luò)上的流，并稱f(vi,vj)為弧(vi,vj)上的流量，簡記為aij。由文獻(xiàn)[13-14]可知，滿足下面條件的流f稱為可行流。

（1）容量限制條件。 對每一弧(vi,vj)∈E，滿足 0≤aij≤cij。

（2）對于中間點。流出量與流入量相等，即對于個i（1＜i＜n），有Σaik-Σaji=0；對于發(fā)點Σa1k-對于收點Σank-Σajn=-v（f）。

最大流問題就是求解流{aij}，使其流量v（f）達(dá)到最大，且滿足

2.2 聚合流的等效容量

代數(shù)法求解[15]EBAF就是利用有效帶寬的定義式直接求解。利用代數(shù)法得到EBAF模型，需要引入數(shù)學(xué)中關(guān)于上確界的知識，如下

定義1設(shè)S是R中的一個數(shù)集，對于η有以下兩條

①對一切x∈S，有x≤n，即η是數(shù)集S的上界；

②對任意ε＞0，存在x0∈S使得x0＞η-ε（η是數(shù)集S的最小上界），則稱η為數(shù)集S的上確界。記為 η=supS。

定理1對于一個在定義域[x1，xn]內(nèi)連續(xù)的函數(shù)f（x），若它存在上確界，那么它的上確界等于函數(shù) f（x）各個分區(qū)間[x1，x2]，[x2，x3]，…，[xn-1，xn]上的上確界的最大值，即

根據(jù)定理1的內(nèi)容，可以得到如下推論。

推論1對于一個在定義域[x1，xn]內(nèi)連續(xù)的分段函數(shù)f（x），若它存在上確界，并且f（x）各個分區(qū)間[x1，x2]，[x2，x3]，…，[xn-1，xn]上對應(yīng)的函數(shù)解析式為 fi（x）=（i=1,2，…，n-1）。 如果 f（x）在區(qū)間[xi，xi+1]上單調(diào)，那么函數(shù)f（x）在定義域內(nèi)的上確界為

其中α*是聚合流的到達(dá)曲線，s為通過的節(jié)點，D為所有流的時延約束，聚合流的有效帶寬為eD。其流量模型滿足流量規(guī)范T-SPEC(pi,Mi,pi,ri)，在計算過程中，且（4）就是通過代數(shù)法得到的EBAF的值。

2.3 效流量與等效容量的關(guān)系

有效帶寬是從云服務(wù)的角度定義的，而等效容量是從網(wǎng)絡(luò)的角度定義的。為了在保證云服務(wù)時延的同時，優(yōu)化網(wǎng)絡(luò)對資源(如等待區(qū)大小)的分配，需要分析有效帶寬與等效容量之間的關(guān)系。根據(jù)定理1與推理1，可以得到下面的定義及定理。

定義2時延影響因子(delay impact factor，DIF)。對于到達(dá)曲線為α的流，通過一個節(jié)點S，給定流的時延約束為D，當(dāng)節(jié)點的等待區(qū)大小B滿足B=h（D）時，流的有效帶寬等于其等效容量，把h（D）稱為流的時延影響因子。 其中 h（D）=supS≥0{a（S）-eDa（S）},eD（a）流的有效帶寬。

定義 3等待區(qū)影響因子(buffer impact factor，BIF)。對于到達(dá)曲線為α的流，通過一個節(jié)點S。節(jié)點的等待區(qū)大小約束為B，如果流的時延D滿足D=g（B）時，流的等效容量等于其有效帶寬，把g（B）稱為節(jié)點等待區(qū)影響因子。 其中 g（B）=supS≥0{inf{T≥0：a（S）≤fB（a）（S+T）}},fB（a）為流的等效容量。

定理2對于到達(dá)曲線為α的流，通過一個節(jié)點S。

①如果給定時延約束D，當(dāng)節(jié)點等待區(qū)的大小B滿足B=h（D），此時流的有效帶寬與其等效容量相等。

②如果給定等待區(qū)大小約束為B，那么只要這個流的時延約束滿足D=g（B），此時，流的等效容量等于其有效帶寬。

如果給定時延約束 D，本定理所表示的內(nèi)容用數(shù)字表達(dá)式表示為 eD（a）B=h（D）=fB（a）， 節(jié)點為流提供的服務(wù)速率為 eD（a），在 B=h（D）時，流的等效容量為

又由于

根據(jù)不等式(6)

可以看出，在上述過程中，函數(shù)值都是在定義域內(nèi)進(jìn)行放大或縮小，所以函數(shù)在定義域[0，+∞）內(nèi)的最大值就是 eD（a），且 eD（a）也是該函數(shù)的上確界。因此，根據(jù)不等式(7)，可以得到 fB（a）=eD（a）。

如果給定等待區(qū)大小約束B，節(jié)點需要為流提供的服務(wù)速率為fB（a）。定理2所表示的內(nèi)容用數(shù)學(xué)表達(dá)式表示為 feD（a）B=h（D）=eD（a）。 在 D=g（B）時，流的有效帶寬為

因此，根據(jù)式（10），可以得到 eD（a）=fB（a）。

有效帶寬是表示在滿足時延約束D時節(jié)點需要為流提供的服務(wù)速率，因此，現(xiàn)在考慮云服務(wù)的時延約束為D，則就是節(jié)點eD（a）分配給流的最小帶寬，那么，在滿足此時延約束D時，節(jié)點需要提供給云服務(wù)的最小等待區(qū)Bmin必須滿足如下條件

①保證QoS不變。也就是在節(jié)點等待區(qū)大小為Bmin時，云服務(wù)通過此節(jié)點產(chǎn)生的時延在要求的時延約束范圍內(nèi)，即不能超過D;

②不能改變節(jié)點的接納能力。也就是在等待區(qū)大小為Bmin時，在滿足時延約束D的條件下，等待區(qū)不能有溢出。否則節(jié)點所能接納的云服務(wù)數(shù)量將少于在單獨滿足時延約束節(jié)點所能接納的數(shù)量。

由于時延約束D與等待區(qū)大小約束B都能影響節(jié)點接納云服務(wù)的數(shù)量，而接納云服務(wù)數(shù)量的多少由有效帶寬和等效容量決定。若只考慮給定時延約束D時，節(jié)點接納的云服務(wù)數(shù)量為nD，只考慮等待區(qū)大小約束B時，節(jié)點接納的云服務(wù)數(shù)量為nB，而同時考慮兩者的情況下，節(jié)點接納的云服務(wù)數(shù)量為 n=min(nD,nB)。 因此，如果要滿足第②點的條件，就必須使 fB（a）≤eD（a），而 fB（a）的值隨著 B的減小而增大，那么滿足條件的最小值 Bmin即是 fB（a）=eD（a）時求解得到的值。 而當(dāng) fB（a）=eD（a）時，第①點的條件顯然滿足。那么當(dāng)給定云服務(wù)的時延約束為D，節(jié)點提供給云服務(wù)的服務(wù)曲線為β（t）=eD（a）t時，根據(jù)定理2可以得到滿足條件的最小等待區(qū)大小Bmin就是DIF，且為

綜合以上，對于假設(shè)云計算環(huán)境中有I種類型的云服務(wù)的場景，每個云服務(wù)的業(yè)務(wù)流的時延約束為D，結(jié)合推論1，可以推導(dǎo)出節(jié)點需要為I種類型流的聚合流提供的最小等待區(qū)大小Bmin為

3 基于聚合流的有效帶寬接納控制算法

當(dāng)用戶請求服務(wù)時，接納控制算法根據(jù)服務(wù)參數(shù)和用戶的QoS要求估計聚合流所需要的帶寬，最后根據(jù)對聚合流的帶寬估計和節(jié)點的帶寬情況來執(zhí)行接納決策。表1給出了EBAF算法中的常用標(biāo)記及含義。表2詳細(xì)介紹了基于聚合流的有效帶寬的接納控制算法的執(zhí)行過程，該過程主要包括以下步驟（1）第 1～10行，求出，并將從小到大排序，在此過程須保持與，的對應(yīng)關(guān)系不變。（2）第11～20行，利用輸入的服務(wù)參數(shù)和用戶的QoS參數(shù)估計聚合流所需的帶寬。（3）第21～25行，接納決策過程。利用上一步計算得到的聚合流的帶寬估計與節(jié)點帶寬，判斷該流的請求接納與否。

表1 EBAF算法常用標(biāo)記及含義

表2 EBAF算法

4 實驗分析

本文通過計算機(jī)仿真，在CloudSim仿真器中搭建實驗環(huán)境，云服務(wù)中含有2個計算節(jié)點，節(jié)點配置為：100個CPU，256 GB內(nèi)存，100 TB硬盤存儲，2 GB的網(wǎng)絡(luò)帶寬流量。假設(shè)每個單流到達(dá)等待區(qū)都符合馬爾可夫鏈[16]。仿真參數(shù)我們參照文獻(xiàn)[17]，具體如表3所示。

表3 三種云服務(wù)的仿真參數(shù)

表3中參數(shù)i=4的服務(wù)流的有效帶寬與等效容量如圖2～3所示。從圖中可以看出，隨著時延約束或等待區(qū)大小約束的增大，有效帶寬或等效容量會隨之減小，也就是網(wǎng)絡(luò)入口節(jié)點需要為服務(wù)流提供的服務(wù)速率變小，但最小的速率不能低于流的平均速率r，這個速率也是在滿足當(dāng)前約束等待區(qū)沒有溢出時節(jié)點需要提供的最小速率。

圖2 有效帶寬圖

圖3 等效容量

針對EBAF算法，接納服務(wù)流的數(shù)量都是隨著時延約束D的增大而增大，這是因為隨著時延約束D的增大，流所需帶寬資源變少，即有效帶寬變小，接納容量增大，即時延約束越大，節(jié)點的接納能力增加。但當(dāng)時延約束增大一定程度后，不管D如何變化，接納的數(shù)量都將保持不變。這是因為時延約束增大到一定程度后，流的有效帶寬等于流的平均速率r，之后D再增大，有效帶寬的值將不再發(fā)生變化，接納服務(wù)的數(shù)量也不再變化。圖5～6分別為i=1,2和i=2,3時的性能比較。通過對比我們可以得知，隨著時延約束D的增大，聚合流的有效帶寬比單流的有效帶寬先達(dá)到最小值。

圖4 i=1,2的有效帶寬性能比較

圖5 i=2,3的有效帶寬性能比較

5 結(jié)語

為了提高云計算下網(wǎng)絡(luò)流量的執(zhí)行效率，本文提出了一種基于聚合流的有效帶寬（EBAF）接納控制算法，通過估計聚合流所需的帶寬來執(zhí)行接納控制，能同時處理多個服務(wù)請求。在不同云服務(wù)參數(shù)下進(jìn)行模擬仿真。仿真結(jié)果表明，本文提出的有效帶寬接納控制方法，能有效的解決云計算環(huán)境下的帶寬流量控制，實現(xiàn)網(wǎng)絡(luò)的負(fù)載均衡，從而提升網(wǎng)絡(luò)并發(fā)處理的能力，以進(jìn)一步提高云計算的QoS。