面向大數(shù)據(jù)應(yīng)用的自適應(yīng)帶寬分配策略

姜 晶

(徐州開(kāi)放大學(xué) 信電學(xué)院, 江蘇 徐州 221116)

隨著移動(dòng)設(shè)備的高速發(fā)展，海量數(shù)據(jù)(大數(shù)據(jù))的應(yīng)用日益劇增[1-3]。通常大數(shù)據(jù)具有3Vs特性：容量(Volume)、速度(Velocity)和多變(Variety)[4]。隨著大數(shù)據(jù)的不斷涌現(xiàn)，隨之而來(lái)的問(wèn)題也難以避免，如大數(shù)據(jù)分析、大數(shù)據(jù)傳輸以及容量問(wèn)題。其中，大數(shù)據(jù)傳輸問(wèn)題尤為突出。為此，在滿足數(shù)據(jù)有效期的條件下，如何高效地傳輸大數(shù)據(jù)成為研究熱點(diǎn)。

節(jié)點(diǎn)產(chǎn)生的數(shù)據(jù)可能需要通過(guò)網(wǎng)絡(luò)傳輸至其他節(jié)點(diǎn)。在傳輸數(shù)據(jù)前，節(jié)點(diǎn)通常先傳輸數(shù)據(jù)請(qǐng)求。因此，如何可靠地傳輸請(qǐng)求并處理傳輸請(qǐng)求，對(duì)數(shù)據(jù)傳輸?shù)某晒ζ鸬疥P(guān)鍵作用。而有效地給傳輸請(qǐng)求(Request,Req)分配帶寬有利于快速地傳輸請(qǐng)求。然而由于海量數(shù)據(jù)和網(wǎng)絡(luò)的復(fù)雜性，有效地分配帶寬存在一些挑戰(zhàn)。

給請(qǐng)求分配寬的帶寬，可降低傳輸時(shí)延，但也消耗了寬帶資源。反之，若分配窄的帶寬，網(wǎng)絡(luò)可接收更多的請(qǐng)求，但增加傳輸時(shí)延，最終也可能加大了鏈路瓶頸的概率。因此，自適應(yīng)地分配帶寬顯得尤為重要。即在有限資源下，滿足時(shí)限要求，盡可能給傳輸請(qǐng)求分配帶寬，進(jìn)而高效地傳輸數(shù)據(jù)[5]。

為了克服現(xiàn)存帶寬分配的不足，提出自適應(yīng)帶寬分配策略(Flexible Bandwidth Allocation for Big Data Transfer,FBA-BDT)。首先，建立優(yōu)化規(guī)劃目標(biāo)函數(shù)，其目的是在滿足所有傳輸請(qǐng)求的時(shí)限條件下，最大化地完成請(qǐng)求的傳輸。目標(biāo)函數(shù)給每個(gè)已接收的請(qǐng)求分配了最優(yōu)帶寬，使得能在截止日期前完成數(shù)據(jù)傳輸，進(jìn)而提高帶寬利用率。

1 問(wèn)題描述

本節(jié)針對(duì)大數(shù)據(jù)傳輸請(qǐng)求(Big Data Transfer Requests,BDTRs)建立最優(yōu)規(guī)劃目標(biāo)函數(shù)。

令G(V,E)表示網(wǎng)絡(luò)，其中V為頂點(diǎn)集、E為邊集。Cl表示鏈路l∈E的剩余帶寬[6]。最初，當(dāng)網(wǎng)絡(luò)沒(méi)有準(zhǔn)許任何請(qǐng)求時(shí)，所有鏈路均具有最大容量的帶寬。在時(shí)隙t，令R表示已準(zhǔn)許的BDTRs集。對(duì)于每個(gè)請(qǐng)求r∈R，其可用一個(gè)元組〈sr,dr,Vr,tr〉表述，其中sr為源節(jié)點(diǎn)、dr為目的節(jié)點(diǎn)、Vr為需要傳輸?shù)臄?shù)據(jù)容量、tr為完成數(shù)據(jù)傳輸?shù)慕刂箷r(shí)間。

引用二值變量xr表示請(qǐng)求r是否被網(wǎng)絡(luò)準(zhǔn)許，若xr=1，表示準(zhǔn)許；若xr=0，表示拒絕。而引用二值變量yr表示選用了哪條路徑：Pr,1或Pr,2。而用zr表示給請(qǐng)求r分配的帶寬數(shù)。因此，自適應(yīng)帶寬分配的優(yōu)化規(guī)劃目標(biāo)函數(shù)如下：

(1)

(2)

(3)

xrVr/tr≤zr, ?r∈R

(4)

(5)

xr,yr∈{0,1}, ?r∈R

(6)

由式(1)可知，目標(biāo)函數(shù)的目的就是最大化已準(zhǔn)許的BDTRs數(shù)，準(zhǔn)許的BDTRs數(shù)越多，通過(guò)的數(shù)據(jù)量越大。而限制條件式(2)和式(3)確保了給已選的每個(gè)BDTR的路徑分配足夠的帶寬。如果一條鏈路用于多個(gè)請(qǐng)求，必須有剩余帶寬分配給這些請(qǐng)求。

限制條件式(2)應(yīng)用于使用第一條路徑(Pr,1,?r∈R∪Rac)的BDTRs，而限制條件式(3)應(yīng)用于使用第二路徑(Pr,2)的其他請(qǐng)求。注意當(dāng)yr=1，表示請(qǐng)求r利用路徑Pr,1傳輸數(shù)據(jù)；而yr=0，表示請(qǐng)求r利用路徑Pr,2傳輸數(shù)據(jù)。而限制條件式(4)和式(5)給已準(zhǔn)許的請(qǐng)求和正在進(jìn)行的請(qǐng)求提供了最小的帶寬，并滿足它們的時(shí)限要求。

然而，由于目標(biāo)函數(shù)的非線性特性[7]，計(jì)算目標(biāo)函數(shù)的運(yùn)算量較大。即使對(duì)于少量的BDTRs和小型網(wǎng)絡(luò)，涉及的變量數(shù)仍過(guò)大，并且變量數(shù)隨請(qǐng)求數(shù)和網(wǎng)絡(luò)尺寸呈指數(shù)增長(zhǎng)。因此，很難在短時(shí)間內(nèi)，獲取最優(yōu)解。為此，接下來(lái)，利用啟動(dòng)算法求解目標(biāo)函數(shù)，進(jìn)而獲取可接收的次優(yōu)解。

2 求解算法

利用FBA-BDT算法求解目標(biāo)函數(shù)。求解過(guò)程由兩步構(gòu)成，偽代碼分別如算法1和算法2所示。它們需解決的問(wèn)題如圖1所示。從圖1可知，算法1的目的在于滿足請(qǐng)求的最基本要求(分配所需的最小帶寬)，而算法2是將剩余帶寬重新分配給已準(zhǔn)許的請(qǐng)求。

注意到，算法1和算法2均是周期地執(zhí)行，即在每個(gè)時(shí)隙開(kāi)始執(zhí)行，且每個(gè)時(shí)隙的時(shí)長(zhǎng)為ts。具體而言，在時(shí)隙t-1到達(dá)的所有BDTRs需在時(shí)隙t的開(kāi)始時(shí)完成。

圖1 FBA-BDT算法的兩個(gè)子算法框圖

2.1 算法1

具體而言，在給定正在進(jìn)行的傳輸請(qǐng)求數(shù)和網(wǎng)絡(luò)狀態(tài)時(shí)，算法1目的就是給每條準(zhǔn)許的請(qǐng)求選擇一條合適的路徑，并分配最小的帶寬，進(jìn)而完成數(shù)據(jù)的傳輸。

(7)

(8)

式(8)中，er表示請(qǐng)求r擁有的剩余時(shí)隙數(shù)；ts是時(shí)隙的時(shí)長(zhǎng)。

然后給已準(zhǔn)許的請(qǐng)求R中的每條請(qǐng)求決策傳輸數(shù)據(jù)的路徑，進(jìn)而滿足截止時(shí)期tr,如算法1的Step5至Step14，為每個(gè)請(qǐng)求r的可選路徑計(jì)算最小剩余帶寬。假定可選路徑Pr,1、Pr,2的最小剩余帶寬分別表示為CPr,1、CPr,2。

圖2 算法1的偽代碼

(9)

如果請(qǐng)求r能夠獲取更高帶寬的路徑，即滿足式(10)，則準(zhǔn)許請(qǐng)求r入網(wǎng)，并選擇更高帶寬的路徑Pr傳輸數(shù)據(jù)。否則拒絕r入網(wǎng)。

(10)

完成算法1后，就構(gòu)成已準(zhǔn)許的請(qǐng)求集Rad。綜上所述，算法1的執(zhí)行流程如圖3所示。

圖3 算法1的執(zhí)行流程框圖

2.2 算法2

完成了第一階段后，基于可用的剩余帶寬[8-9]，第二階段試著將額外的帶寬分配給已準(zhǔn)許的Req和正在進(jìn)行的Req，進(jìn)而完成數(shù)據(jù)的傳輸，提高資源效率。

算法2的偽代碼如圖4所示。在給定Rad和Rac條件下，算法2就將額外帶寬分配給這些請(qǐng)求，使它們能夠在截止日期前完成數(shù)據(jù)傳輸。對(duì)于請(qǐng)求r，首先迭代計(jì)算路徑Pr上所有鏈路，進(jìn)而完成在每條鏈路上能夠獲取的額外帶寬。對(duì)于鏈路l∈Pr，所分配的額外帶寬zr，其正比于每條請(qǐng)求所需要傳輸?shù)臄?shù)據(jù)量，表示為：

(11)

迭代完畢后就可計(jì)算分配請(qǐng)求r的帶寬，即：

(12)

(13)

圖4 算法2的偽代碼

3 性能分析

3.1 仿真環(huán)境

仿真過(guò)程中引用ESnet拓?fù)鋄5]。網(wǎng)絡(luò)由58個(gè)節(jié)點(diǎn)組成，其中23個(gè)節(jié)點(diǎn)是流量Hubs，而余下的35個(gè)節(jié)點(diǎn)為流量產(chǎn)生節(jié)點(diǎn)。每個(gè)流量產(chǎn)生節(jié)點(diǎn)能夠以10 Gbit/s數(shù)據(jù)率產(chǎn)生數(shù)據(jù)。假定連接58個(gè)節(jié)點(diǎn)的所有鏈路具有10 Gbit/s的容量。每條請(qǐng)求所傳輸?shù)臄?shù)據(jù)量在[1,20]GB內(nèi)隨機(jī)選取。每條請(qǐng)求的傳輸截止時(shí)限在[40,300]s。每個(gè)時(shí)隙的時(shí)長(zhǎng)為40 s。此外，由于數(shù)據(jù)傳輸時(shí)延是秒量級(jí)，忽略傳播時(shí)延[10-11]。

為了更好地分析FBA-BDT算法的性能，選擇拒絕請(qǐng)求率、每個(gè)時(shí)隙傳輸?shù)钠骄鶖?shù)據(jù)量和每個(gè)時(shí)隙每條請(qǐng)求所分配的平均帶寬[12-13]。其中拒絕請(qǐng)求率等于拒絕的BDTRs數(shù)與已準(zhǔn)許的BDTRs數(shù)之比[14]；每個(gè)時(shí)隙傳輸?shù)钠骄鶖?shù)據(jù)量等于在總仿真時(shí)間內(nèi)的總時(shí)隙內(nèi)傳輸?shù)钠骄鶖?shù)據(jù)量；每個(gè)時(shí)隙每條Req所分配的平均帶寬等于在總的時(shí)隙數(shù)、總的已準(zhǔn)許的BDTRs內(nèi)，給已準(zhǔn)許的BDTRs所分配的帶寬。

此外，比較最小帶寬分配(Minimum Bandwidth Allocation,MinBA)、最大帶寬分配(Maximum Bandwidth Allocation,MaxBA)策略。MinBA策略在滿足時(shí)限要求下，給每條準(zhǔn)許BDTRReq分配所需的最小帶寬，并維持此帶寬，直到數(shù)據(jù)傳輸完畢。而MaxBA策略是分配可用的最大帶寬。

3.2 數(shù)據(jù)分析

3.2.1 拒絕請(qǐng)求率

圖5顯示了拒絕請(qǐng)求率隨請(qǐng)求到達(dá)率的變化曲線。相比于MaxBA和MinBA算法，F(xiàn)BA-BDT算法的拒絕率得到了有效控制。即使在糟糕的情況，F(xiàn)BA-BDT算法的拒絕率比MaxBA和MinBA算法也分別提高82%、40%。換而言之，MinBA算法拒絕40%的Req被FBA-BDT算法接收。

FBA-BDT算法的最佳拒絕率比MaxBA和MinBA算法分別降低了88%和98%。這些數(shù)據(jù)表明給請(qǐng)求自適應(yīng)分配帶寬比采用固定策略分配帶寬，能夠有效地降低拒絕請(qǐng)求率。

圖5 拒絕請(qǐng)求率

3.2.2 每個(gè)時(shí)隙傳輸?shù)钠骄鶖?shù)據(jù)量

圖6顯示每個(gè)時(shí)隙傳輸?shù)钠骄鶖?shù)據(jù)量隨請(qǐng)求到達(dá)率的變化曲線。從圖6可知，在每個(gè)時(shí)隙的請(qǐng)求到達(dá)率為16個(gè)BDTRs時(shí)，F(xiàn)BA-BDT算法能夠每時(shí)隙傳輸高達(dá)142 GB，而MaxBA和MinBA算法只能夠傳輸50 GB和125 GB。換而言之，利用FBA-BDT算法，網(wǎng)絡(luò)每天能夠傳輸和處理約300 TB的大數(shù)據(jù)，這幾乎是Large Hadron Collider的4倍。

圖6 每個(gè)時(shí)隙傳輸?shù)钠骄鶖?shù)據(jù)量

3.2.3 每個(gè)時(shí)隙每條請(qǐng)求所分配的平均帶寬

圖7顯示了每個(gè)時(shí)隙每條請(qǐng)求所分配的平均帶寬隨Req到達(dá)率的變化曲線。從圖7可知，MaxBA和MinBA算法在到達(dá)率變化期間給所有請(qǐng)求分配相同的帶寬。而FBA-BDT算法給請(qǐng)求分配的帶寬隨到達(dá)率的增加而逐漸減少。原因在于：當(dāng)?shù)竭_(dá)率低時(shí)，有額外可用帶寬分配給這些請(qǐng)求。而當(dāng)?shù)竭_(dá)率增加時(shí)，額外可用帶寬隨之下降。

此外，F(xiàn)BA-BDT算法可提高資源效率。在低到達(dá)率時(shí)分配更多帶寬給請(qǐng)求，可提高帶寬利用率，也使得請(qǐng)求在截止日期前完成數(shù)據(jù)的傳輸。

圖7 每個(gè)時(shí)隙每條請(qǐng)求所分配的平均帶寬曲線

4 結(jié)論

本文基于傳輸請(qǐng)求時(shí)限條件下，分析了利用自適應(yīng)分配帶寬的大數(shù)據(jù)傳輸問(wèn)題，進(jìn)而最大化請(qǐng)求接收率。提出的FBA-BDT算法先建立目標(biāo)函數(shù)，再利用啟發(fā)式算法求解目標(biāo)函數(shù)。實(shí)驗(yàn)數(shù)據(jù)表明，提出的FBA-BDT算法有效地降低了請(qǐng)求拒絕率，并提高了數(shù)據(jù)量。