multihoming成本及性能的優(yōu)化

1、<p>　　Multihoming 成本及性能的優(yōu)化</p><p><b>　　摘要：</b></p><p>　　大型企業(yè)及英特網(wǎng)服務(wù)提供商常用 multihoming 技術(shù)來(lái)接入 Internet。在本文中，我們?cè)O(shè)計(jì)了一系列新穎的算法－－smart routing――為 multihoming 用戶在成本及性能上進(jìn)行優(yōu)化。通過(guò)分析和模擬現(xiàn)實(shí)收費(fèi)模式、通

2、信需求、性能數(shù)據(jù)及網(wǎng)絡(luò)拓樸，我們?cè)u(píng)估了該算法。評(píng)估結(jié)果顯示該算法能非常有效地在減少成本的同時(shí)提升性能。我們進(jìn)一步地檢測(cè)了 smart routing 對(duì)全局網(wǎng)絡(luò)均衡性的影響，發(fā)現(xiàn) smart routing 用戶能在不對(duì)其他用戶造成明顯影響的情況下提升自己的性能。</p><p><b>　　分類及主題：</b></p><p>　　C2.6[計(jì)算機(jī)通信網(wǎng)絡(luò)]：網(wǎng)絡(luò)―

3、―英特網(wǎng)</p><p><b>　　通用術(shù)語(yǔ):</b></p><p><b>　　算法，性能</b></p><p><b>　　關(guān)鍵字：</b></p><p>　　Multihoming, Smart Routing, 優(yōu)化，算法</p><p>

4、;<b>　　1.引述</b></p><p>　　Multihoming[31]由于其可靠性、成本及性能上的優(yōu)勢(shì)，常被大型企業(yè)和英特網(wǎng)服務(wù)提供商用以接入 Internet。一個(gè)客戶或 ISP 網(wǎng)絡(luò)（也可以叫做用戶）有著多個(gè)外部連接（或一個(gè) ISP 或者多個(gè)服務(wù)提供商），即可被說(shuō)成 multihomed[31]。一個(gè)用戶如果能有效地控制其通信量在多個(gè)外部連接上的分布，就可以說(shuō)成實(shí)現(xiàn)了 sma

5、rt routing。Smart routing 也可被指為路由優(yōu)化或者智能路由控制。</p><p>　　Smart routing 有如下幾個(gè)優(yōu)點(diǎn)。首先，smart routing 可以提升網(wǎng)絡(luò)性能及其可靠性。最近研究顯示[27, 32, 33]，與理想路由相比，網(wǎng)絡(luò)級(jí)路由由于路由體系和 BGP 路由規(guī)則會(huì)導(dǎo)致用戶性能的優(yōu)化被置于次要的地位。設(shè)備的癱瘓，短暫的不可靠和網(wǎng)絡(luò)擁塞同樣會(huì)影響到用戶性能。Smart

6、routing 提供了一種由最終用戶控制路由選擇的辦法。在[1]，Akella et al. 量化了 smart routing 的益處，顯示出選擇有效的提供商能帶來(lái)性能的提升。在[2]，Akella et al. 發(fā)現(xiàn)連接到三個(gè) ISP 帶來(lái)的延遲和吞吐量超過(guò)與 3 個(gè) multihoming 連接的路由覆蓋的 5~15%。其次，若考慮到特定收費(fèi)模式，smart routing 能有效降低用戶費(fèi)用。最近的一份經(jīng)濟(jì)分析表明 smart

7、routing 不僅能減少最終用戶費(fèi)用，也能降低服務(wù)提供商的成本。</p><p>　　由于 smart routing 潛在的益處及大量的 multihomed 用戶，許多公司正積極開(kāi)發(fā)著實(shí)現(xiàn)了</p><p>　　smart routing 的軟件，e.g., [12, 19, 21, 24]。然而，由于這些是商業(yè)產(chǎn)品，它們的技術(shù)細(xì)節(jié)是</p><p>　　保密

8、的，它們?cè)?Internet 上的性能和影響也不能被很好的評(píng)測(cè)。還有一些對(duì) smart routing 的探索研究，e.g., [1, 11]，這些研究的重點(diǎn)僅在提升網(wǎng)絡(luò)的性能；而用戶費(fèi)用作為使用 multihoming 的另一推動(dòng)因素卻被忽視了。此外，先前研究重點(diǎn)在潛在性能益處，而不在于算法的實(shí)現(xiàn)。潛在的益處如何得以實(shí)現(xiàn)仍然是一個(gè)公開(kāi)的問(wèn)題。</p><p>　　1 頁(yè) 共 28 頁(yè)</p>&l

9、t;p>　　在本文中，我們開(kāi)發(fā)了一系列優(yōu)化 multihomed 用戶成本及及性能的算法，從而實(shí)現(xiàn)了 smart routing 的部分益處。我們首先論證了單獨(dú)優(yōu)化網(wǎng)絡(luò)性能會(huì)大大增加用戶費(fèi)用，導(dǎo)致 smart routing 使用價(jià)值的下降。為了說(shuō)明這一點(diǎn)，我們提出新的離線和在線路由算法來(lái)減少用戶在通常收費(fèi)模式下的費(fèi)用。參考大學(xué)及企業(yè)的實(shí)際收費(fèi)價(jià)格和通信需求，我們得出在不考慮通信波動(dòng)的情況下，與專用連接或利用輪詢或同等時(shí)間片劃分算

10、法實(shí)現(xiàn)的間接連接相比，我們的在線算法能顯著地減少用戶費(fèi)用。我們同樣設(shè)計(jì)了在線與離線算法在成本有限的情況下為 smart routing 用戶優(yōu)化網(wǎng)絡(luò)性能。參考實(shí)際收費(fèi)價(jià)格，及對(duì)通信需求與延遲的追蹤，我們發(fā)現(xiàn)在線算法能達(dá)到經(jīng)過(guò)優(yōu)化的離線算法性能的 10~20%。</p><p>　　在本文中，我們假設(shè)用戶與一組 ISP 連接，是 multihomed。因此，我們重點(diǎn)在如何在這一組 ISP 之間動(dòng)態(tài)分配通信流量來(lái)優(yōu)化

11、成本及網(wǎng)絡(luò)性能。是否運(yùn)用 multihoming 及選擇哪一</p><p>　　ISP，這本身就非常復(fù)雜，可能會(huì)牽扯到很多技術(shù)性的和非技術(shù)性的因素，這些我們將不在本文中進(jìn)行闡述。我們同樣也假設(shè)用戶只對(duì)成本及網(wǎng)絡(luò)性能感興趣。然而對(duì)于許多實(shí)際的</p><p>　　Internet 服務(wù)（例如虛擬私有網(wǎng)絡(luò) VPNS），僅對(duì)成本及性能進(jìn)行優(yōu)化是不夠的。其他因素，例如易管理、易查錯(cuò)、安全性及服務(wù)

12、質(zhì)量（QoS）同樣在用戶的商業(yè)決定中起著關(guān)鍵職責(zé)。所以我們的技術(shù)在這些方面并不直接適用。然而，為了更好地理解在未來(lái)網(wǎng)絡(luò)中 smart routing 的潛在作用，我們相信應(yīng)從先前以性能為中心的的研究轉(zhuǎn)到將成本及性能放到同等地位加以優(yōu)化的優(yōu)化構(gòu)架中來(lái)。</p><p>　　除了開(kāi)發(fā)技術(shù)對(duì)成本及性能加以優(yōu)化外，我們也評(píng)估了這些優(yōu)化對(duì)網(wǎng)絡(luò)全局的影響。我</p><p>　　們發(fā)現(xiàn)由于每一個(gè)獨(dú)立的

13、 smart routing 用戶選擇適當(dāng)?shù)穆酚梢詢?yōu)化自身而不考慮對(duì)網(wǎng)絡(luò)的影響，smart routing 變成一個(gè)自私的路由方案。這些改變影響了網(wǎng)絡(luò)性能，可能會(huì)導(dǎo)致自干擾或與其他 smart routing 或正常通信產(chǎn)生干擾。Smart routing 能否在這些干擾中仍然保證其性能優(yōu)勢(shì)，這要等以后才能知曉。</p><p>　　我們通過(guò)大量的模擬研究了 smart routing 的全局影響。我們首先檢查了

14、 smart routing 在自影響中的均衡性（即 smart routing 用戶的路由決定改變了網(wǎng)絡(luò)性能，網(wǎng)絡(luò)性能的改變反過(guò)來(lái)亦影響了路由決定）。結(jié)果表明即使在自影響中，我們的算法仍能取得好的性能均衡接著</p><p>　　我們?cè)u(píng)估了 smart routing 通信如何影響了其他 smart routing 通信或單用戶通信。評(píng)估是建立在內(nèi)部網(wǎng)絡(luò)拓?fù)浜同F(xiàn)實(shí)通信中用戶需求的基礎(chǔ)上的。結(jié)果顯示 smart

15、routing 能在不降低其他通信性能的基礎(chǔ)上增加自身性能。</p><p>　　我們關(guān)鍵性的貢獻(xiàn)可概述為以下幾點(diǎn)：</p><p>　　我們?cè)O(shè)計(jì)了離線與在線算法以在現(xiàn)實(shí)收費(fèi)模式的基礎(chǔ)上降低成本</p><p>　　我們?cè)O(shè)計(jì)了離線與在線算法以在成本有限的基礎(chǔ)上優(yōu)化網(wǎng)絡(luò)性能</p><p>　　我們?cè)趯?shí)際通信和性能數(shù)據(jù)的基礎(chǔ)上進(jìn)行分析與模擬，顯

16、示出我們的算法會(huì)產(chǎn)生高性能、低成本</p><p>　　我們?cè)u(píng)估了當(dāng)多個(gè)用戶“自私”地優(yōu)化他們自己的成本與性能時(shí)的 smart routing 性能，我們發(fā)現(xiàn)在該情況下，smart routing 通信能很好地與其他通信相互影響，保持</p><p><b>　　通信均衡。</b></p><p>　　本文剩余部分組織如下。在第二部分，我們回顧

17、了相關(guān)工作。在第三部分，我們討論了實(shí)際的網(wǎng)絡(luò)及收費(fèi)模式。在第四部分，我們引出成本優(yōu)化的重要性并展示了新穎的成本優(yōu)化算法。在第五部分，我們?cè)诂F(xiàn)有成本限制的基礎(chǔ)上優(yōu)化網(wǎng)絡(luò)延遲，在第六部分，我們展示了評(píng)估的方法與結(jié)果。第七部分，我們研究了 smart routing 的全局影響并評(píng)估了其他通信的影響。在第八部分，我們總結(jié)并討論了以后的工作。</p><p><b>　　2.相關(guān)工作</b><

18、/p><p>　　2 頁(yè) 共 28 頁(yè)</p><p>　　一些最近的研究（如[4,27,32,33]）顯示 Internet 路由常常導(dǎo)致用戶性能的優(yōu)化被置于次要地位。有很多因素會(huì)導(dǎo)致這一現(xiàn)象，比如路由體系、路由方針、對(duì)網(wǎng)絡(luò)擁塞或網(wǎng)絡(luò)錯(cuò)誤（如果發(fā)生的話）的較慢的反應(yīng)等。而 BGP 路由的不穩(wěn)定性會(huì)進(jìn)一步加深這一問(wèn)題。這些觀察結(jié)果使得人們?yōu)槭棺罱K用戶在路由選擇上有更多的控制投入相當(dāng)大的研究。例

19、如在[24,27]中，作者們建議利用超負(fù)荷路由來(lái)提升用戶性能。但要在實(shí)際中大規(guī)模部署這一方針還是具有挑戰(zhàn)性的，因?yàn)樵诙鄠€(gè)部門間協(xié)調(diào)可不那么容易。</p><p>　　Multihoming 為用戶控制路由提供了另一種辦法。許多大型企業(yè)、ISPs 甚至一些小的公司早已通過(guò) multihoming 方式來(lái)接入 Internet。</p><p>　　先前關(guān)于 multihoming 的研究更多

20、的是集中在如何設(shè)計(jì)協(xié)議來(lái)實(shí)現(xiàn) multihoming，如[5,7,11,30]。舉幾個(gè)例子：[5,7,12,24,30]的作者們利用點(diǎn)對(duì)點(diǎn) BGP 來(lái)作為實(shí)現(xiàn)手段。而在[9,21]中，作者們則利用 DNS 或 NAT 來(lái)實(shí)現(xiàn)。我們的工作和以上不同，我們工作重點(diǎn)不在于如何實(shí)現(xiàn)，而在于設(shè)計(jì)算法以使用戶決定在什么時(shí)候、分配多少通信量給不同的 ISP 以使優(yōu)化用戶自身的成本及性能。總體上講，我們的工作是對(duì)以上工作的補(bǔ)充。</p>

21、<p>　　有許多文獻(xiàn)評(píng)估了 smart routing 帶來(lái)的益處，如[8,28,29]。最近，在[1]中，Akella 等又根據(jù)實(shí)際網(wǎng)絡(luò)流量評(píng)測(cè)了使用 multihoming 的益處。他們的研究結(jié)果顯示出 smart routing 在</p><p>　　大多數(shù)情況下有能力為 2-multihomed 用戶帶來(lái)至少 25%的性能提升；當(dāng)有 4 個(gè)提供商時(shí)，帶來(lái)的益處是最大的。被這些研究結(jié)果所觸動(dòng)，

22、我們開(kāi)發(fā)路由體系以在實(shí)際上獲得這些益處。此外，我們還研究了多個(gè) smart routing 用戶相互影響下的未協(xié)調(diào)路由優(yōu)化的結(jié)果。</p><p>　　最后，有許多研究（如[1,15,17]）研究了 smart routing 的算法設(shè)計(jì)。如在[1]中，Orda</p><p>　　Rom 調(diào)查了在哪兒放置 multihoming 用戶，結(jié)果說(shuō)明該問(wèn)題是 NP 難度的。Cao 等在[6]中

23、建議使用哈希函數(shù)來(lái)取得多連接之間的均衡。在[11]中，作者在本地網(wǎng)絡(luò)中比較了多種路由選擇方案，結(jié)果顯示使用哈希函數(shù)取得的性能提升與使用負(fù)載敏感的路由選擇有的一拼。我們的工作與這些研究不同，我們的興趣在于既提升性能，又要降低成本。我們也研究了多 smart routing 用戶之間的影響及 smart routing 用戶與 single-homed 用戶之間的影響。</p><p><b>　　3.網(wǎng)絡(luò)

24、與收費(fèi)模式</b></p><p>　　在本段，我們描述了網(wǎng)絡(luò)模式、ISP 收費(fèi)模式及日常所使用的對(duì)性能的度量。</p><p><b>　　3.1 網(wǎng)絡(luò)模式</b></p><p>　　圖 1：一個(gè)用戶與 K 個(gè)服務(wù)提供商的例子</p><p>　　在圖 1 中，一個(gè) multihomed 用戶有多路連接到

25、 Internet 進(jìn)行收發(fā)通信。分布式通信連接中輸入與輸出通信的實(shí)現(xiàn)是不一樣的。對(duì)于輸出通信，用戶網(wǎng)絡(luò)中的邊界路由能有效控制通</p><p>　　3 頁(yè) 共 28 頁(yè)</p><p>　　信如何被分布。對(duì)于輸入通信，用戶能用 NAT 或 DNS 來(lái)控制路由。讀者可參考[1,5,7,11,30]，其中有關(guān)于實(shí)現(xiàn)的更細(xì)致的探討。</p><p>　　應(yīng)注意到我們討論

26、重點(diǎn)在于決定何時(shí)及在每條連接上應(yīng)分配多少通信量，所以 multihoming 的實(shí)現(xiàn)僅是對(duì)我們研究的補(bǔ)充。因此，我們的算法能被應(yīng)用在廣泛的 multihoming 的實(shí)現(xiàn)及輸入輸出通信上。由于正如下面所描述，我們的通信軌跡僅由輸出部分組成，所以在本文中我們也就僅評(píng)估通信的輸出部分。</p><p><b>　　3.2 收費(fèi)模式</b></p><p>　　用戶由于 I

27、SP 的相關(guān)服務(wù)而付以相應(yīng)費(fèi)用。費(fèi)用一般由用戶的通信量決定，例如：cost</p><p>　　c(x)，其中由用戶通信量來(lái)決定（我們用術(shù)語(yǔ) charging volume 表示），c 是一個(gè)非減函數(shù)，將 x 映射到相應(yīng)的成本上。不同收費(fèi)模式由于各自 charging volume 及費(fèi)用函數(shù) c 的選擇不同而不同。</p><p>　　通常，費(fèi)用函數(shù) c 是一個(gè)分段的線性非減函數(shù)，我們將

28、在設(shè)計(jì)與評(píng)估中用到。Charging volume x 可由多種方式來(lái)決定。通常用到百分比收費(fèi)方式與總量收費(fèi)方式。</p><p>　　z 百分比收費(fèi)方式：這是一種現(xiàn)在被 ISP 所使用的典型的 usage－based 收費(fèi)方式。在該方式中，ISP 每五分鐘記錄一次用戶的通信量。在最后收費(fèi)期間，所有每五分鐘通信量的第 q％被用來(lái)當(dāng)著 charging volume x 的 q％收費(fèi)。更具體的講，ISP 將收費(fèi)期

29、間的每五分鐘的通信量以生序進(jìn)行排列，然后以第 q％×I 的量作為 charging volume x，其中 I 是收費(fèi)期間每五分鐘的間隔總數(shù)。舉個(gè)例子，假如 q％為 95%，收費(fèi)期間為 30 天，那么就以排序后第 8208 個(gè)間隔斷的通信量來(lái)收費(fèi)（95%×30</p><p>　　×24×60/5=8208）。</p><p>　　z 總通信量收費(fèi)

30、方式：這是一個(gè)較直觀的收費(fèi)模式，其中 x 是用戶在總收費(fèi)期間的總</p><p><b>　　通信量。</b></p><p>　　在本文中，我們主要關(guān)注百分比收費(fèi)方式。在附錄 C 中，我們描述如何處理基于總通信量的收費(fèi)方式。在評(píng)測(cè)中，我們將使用到兩組價(jià)格函數(shù)。一組是較簡(jiǎn)單的：如果通信量為0,則價(jià)格也為 0;否則，價(jià)格是一個(gè)常數(shù)。我們從表 1 中取得價(jià)格值，表 1 發(fā)

31、表在[25]中。</p><p>　　在該表中，間或連接（Burstable）的價(jià)格基于百分比收費(fèi)方式，而滿連接（Full-rate）也可以說(shuō)的專用連接有著與通信用量無(wú)關(guān)的固定價(jià)格。為評(píng)估我們的算法對(duì)價(jià)格函數(shù)的敏感度，我們也使用了另一組價(jià)格函數(shù)（見(jiàn)圖 2）。這些函數(shù)是較復(fù)雜一點(diǎn)的分布函數(shù)。DS3 的 24Mbps 的價(jià)格及 OC3 的 100Mbps 的價(jià)格與表 1 相符合。價(jià)格曲線的整體趨勢(shì)反映了隨著帶寬的增加

32、價(jià)格的增量逐漸減少，這也與我們?cè)赱3,18]中所知道的價(jià)格曲線相一致</p><p>　　4 頁(yè) 共 28 頁(yè)</p><p>　　3.3 網(wǎng)絡(luò)性能度量</p><p>　　可有多種方式來(lái)度量網(wǎng)絡(luò)性能。在評(píng)估中，我們使用端到端的延遲作為度量手段。正如在[24]中所述，延遲能反映出網(wǎng)絡(luò)的響應(yīng)時(shí)間，而且由于用戶經(jīng)常以較大延遲或快速增加的延遲作為潛在的可靠性標(biāo)示，延遲也被

33、用來(lái)評(píng)測(cè)網(wǎng)絡(luò)可靠性。我們的算法能很容易地?cái)U(kuò)展以</p><p><b>　　4.最小化總成本</b></p><p>　　由于先前的研究?jī)H基于提升網(wǎng)絡(luò)性能，而沒(méi)有考慮到成本問(wèn)題，我們首先將提出優(yōu)化成本的必要性。我們發(fā)現(xiàn)，通過(guò)僅僅優(yōu)化性能可能導(dǎo)致用戶成本的增加。既然基于百分比的收費(fèi)方式被普遍采用，我們將在下面通過(guò)該模式下的一個(gè)簡(jiǎn)單例子來(lái)闡述我們的觀點(diǎn)。在第六部分，使用實(shí)

34、際數(shù)據(jù)所得出的性能結(jié)果將更進(jìn)一步證實(shí)這一觀點(diǎn)。</p><p>　　假設(shè)一個(gè)用戶有到 K 個(gè) ISP 的 K 個(gè)相同的連接。再假設(shè)用戶在每個(gè)間隔期間有一個(gè)單位的通信量傳輸，每個(gè)間隔每個(gè)連接的延遲均在一個(gè)共同范圍內(nèi)。為了減少延遲，在每個(gè)間隔期間用戶在延遲最短的那個(gè)連接上傳輸其所有通信，而其他連接無(wú)任何通信。由于不同連接上的延遲是同等分布的，每個(gè)連接接受通信大約是間隔的 1/K。所以當(dāng) K 小于 20 時(shí)，如K＝4,

35、那么每個(gè)連接的 95%就是 1.也就是說(shuō)通過(guò)優(yōu)化性能，用戶所付費(fèi)用是單連接用戶費(fèi)用</p><p>　　5 頁(yè) 共 28 頁(yè)</p><p>　　K 倍。費(fèi)用增加 K 倍對(duì)大多用戶而言顯然是不能接受的。</p><p>　　給出了費(fèi)用可能大幅增加的可能性，在本段中我們將研究如何設(shè)計(jì)有效的 smart routing</p><p>　　算法來(lái)

36、優(yōu)化費(fèi)用。如在第三段所講，我們重點(diǎn)在基于百分比的收費(fèi)模式。在附錄 C 中，我們給出了基于總通信量的收費(fèi)模式的算法。</p><p><b>　　4.1 問(wèn)題說(shuō)明</b></p><p>　　我們首先介紹以下符號(hào)：</p><p>　　現(xiàn)在我們正式提出流分配問(wèn)題：給定價(jià)格函數(shù)Ck，流分配問(wèn)題就是要求找除合適的tk[i]使</p>&

37、lt;p><b>　　總費(fèi)用最小。</b></p><p>　　我們考慮兩種情況：fractional流分配及integral流分配。在fractional流分配中，流是無(wú)限可分的。相反，integral流分配假設(shè)在每個(gè)時(shí)間間隔中每股流僅分配給一個(gè)ISP。后者中，當(dāng)用BGP來(lái)實(shí)現(xiàn)smart routing時(shí)，流可以很自然地用目的地址前綴來(lái)確定。</p><p>

38、　　流分配問(wèn)題，不管是fractional或者是integral，可以更進(jìn)一步地分為兩類：離線與在線。離線型假設(shè)vf[i]事先給定，然而在線型需要預(yù)測(cè)vf[i]并處理預(yù)測(cè)錯(cuò)誤。在線integral算法更實(shí)際且面對(duì)較低控制。離線fractional算法同樣重要，因?yàn)樗鼈兲峁┝溯^低的成本，且可進(jìn)一步作為設(shè)計(jì)我們?cè)诰€算法的基礎(chǔ)。</p><p>　　4.2離線fractional流分配</p><p

39、>　　我們從解決離線fractional流分配問(wèn)題開(kāi)始。首先我們展示一個(gè)在ISP沒(méi)有容量限制情況下來(lái)優(yōu)化流分配的有效算法。接著我們補(bǔ)充該算法來(lái)處理有容量限制的情況。</p><p>　　4.2.1沒(méi)有容量限制下基于百分比收費(fèi)模式的優(yōu)化算法</p><p>　　優(yōu)化成本的一個(gè)關(guān)鍵處在于決定charging volume。比如：若ISP用95%的收費(fèi)模式，我們</p>&l

40、t;p>　　6 頁(yè) 共 28 頁(yè)</p><p>　　則需要為每個(gè)ISP計(jì)算95%下的通信量。一旦知道了每個(gè)ISP的charging volume，我們就可以分配流量以保證ISP k的服務(wù)比其通信收費(fèi)量多的時(shí)間間隔數(shù)不超過(guò)（1-qk）×I（如95%的收費(fèi)模式為5%×I）。</p><p>　　基于以上觀察，我們開(kāi)發(fā)出一個(gè)有效的算法來(lái)分兩步計(jì)算一個(gè)優(yōu)化的流分配：（i

41、）計(jì)算每個(gè)ISP的charging volume （ii）根據(jù)charging volume分配流量</p><p>　　4.2.2計(jì)算charging volume</p><p>　　在本段中，描述了如何計(jì)算優(yōu)化charging volumes以使總成本最低。我們展示了charging volumes可被分為兩步：（i）計(jì)算charging volume總值，即Σkpk (ii)根據(jù)總

42、值來(lái)計(jì)算單個(gè)pk值。</p><p>　　4.2.2.1計(jì)算charging volume總值</p><p>　　首先來(lái)展示如何計(jì)算總charging volumes以使總成本最低。這是基于以下兩個(gè)重要觀察，這兩個(gè)觀察我們將在下面進(jìn)行證明。第一個(gè)觀察是關(guān)于charging volume總量，總費(fèi)用有一個(gè)單一特性。這個(gè)單一特性即是指套優(yōu)化總成本Σkpk，我們需要最小化Σkpk的值。第二個(gè)觀

43、察是最小化Σkpk的值等同于qt(V, 1-Σk(1-pk))。舉個(gè)例子，有4個(gè)ISP，它們都是基于95%的量進(jìn)行收費(fèi)，那么最小化Σkpk即等于總通信量的80%(1-4*(1-95%)=0.80)。這兩點(diǎn)觀察說(shuō)明了要優(yōu)化成本，我們需有Σkpk＝qt(V, 1-Σk(1-pk))，其中的V與qk很容易算出。</p><p>　　現(xiàn)在我們正式證明這兩點(diǎn)觀察。定義Cmin(s)=min{ΣkCk(pk)| Σkpk=s

44、}。則有定理1:如果S0≥S1≥0,那么Cmin(S0)≥Cmin(S1)</p><p>　　證明：根據(jù)Σkpk=S0，pk集最小化ΣkCk(pk)，則有Cmin(S0)=ΣkCk(pk)≥ΣkCk(pk*S1/S0)≥</p><p>　　Cmin(Σkpk*S1/S0)=Cmin(S1),其中第一個(gè)不等式是由于價(jià)值函數(shù)Ck是單調(diào)非減函數(shù)的，第二個(gè)不等式是根據(jù)Cmin的定義。</

45、p><p>　　第二點(diǎn)觀察，書面表述如定理2,確定了Σkpk可達(dá)的最低下限。</p><p><b>　　定理2: </b></p><p>　　要證明該定理，我們將用刀以下lemma，lemma的證明見(jiàn)附錄A</p><p>　　LEMMA 3（quantile inequality）給定K等長(zhǎng)時(shí)間序列，其</p&g

46、t;<p>　　中n=|Tk|且0≤ak≤1，則有</p><p>　　綜述上述lemma，我們可證明定理如下：</p><p>　　在上述證明中，我們隱式地假設(shè)qk*I都為整數(shù)，其中I＝|V|。當(dāng)qk×I不為整數(shù)，我們可</p><p>　　以通過(guò)重新調(diào)整qk為來(lái)保證其整型值。清楚地看出，這樣的調(diào)整不會(huì)影響</p><p

47、>　　的結(jié)果，（即），其中I=|V|）。在以下，本文中，我們</p><p>　　假設(shè)已事先對(duì)每一個(gè)qk作了這樣的調(diào)整。例如，當(dāng)討論一周收費(fèi)期間以95%收費(fèi)（即</p><p>　　I=7*24*60/5=2016），我們實(shí)際上用qk=（與</p><p>　　qk=0.95=1915.2/2016相反）</p><p>　　7 頁(yè)

48、共 28 頁(yè)</p><p>　　4.2.2.2 計(jì)算單個(gè)charging volumes</p><p>　　一旦V0確定了，接下來(lái)一步就是計(jì)算最小化趨向的優(yōu)化的</p><p>　　charging volumes pk。</p><p>　　從定理4可以很容易看出當(dāng)所有的Ck均concave，優(yōu)化的charging volume Pk可

49、很容易被求出（證明忽略了較短時(shí)間部分）。</p><p>　　定理4:如果所有的價(jià)值函數(shù)Ck是concave，那么優(yōu)化結(jié)果為除了一個(gè)ISP外，其余所有 charging volumes為0。更具體地講，讓k0=argmink[ck(V0)-ck(0)]，定義當(dāng)k=k0時(shí)pk*=V0，否則為0.對(duì)于每個(gè)滿足Σkpk=V0的pk有ΣkCk(Pk*)≤ΣkCk(pk)。</p><p>　　對(duì)于

50、一般的價(jià)值函數(shù)（如非增分段函數(shù)），更難決定優(yōu)化的charging volumes pk（其最小化ΣkCn(pk)趨于Σkpk=V0）。下面我們來(lái)介紹一個(gè)動(dòng)態(tài)編程算法來(lái)解決該問(wèn)題，設(shè)定opt(v,k)是期限的k個(gè)ISP服務(wù)器通信量的優(yōu)化后的費(fèi)用。有</p><p><b>　　根據(jù)上面的</b></p><p>　　遞歸關(guān)系，我們可以從opt(v,1)起來(lái)計(jì)算opt(v

51、,k)，同能追蹤出相應(yīng)分配量opt(v0,k)的值</p><p>　　可得出優(yōu)化費(fèi)用，而其相應(yīng)分配量則決定了pk。算法的時(shí)間復(fù)雜度為O(K*V02),空間復(fù)雜度為</p><p>　　O(K*V0)。以上算法假設(shè)期望精度為1。由于價(jià)格曲線的點(diǎn)也是很粗糙地取得的。所以在實(shí)際</p><p>　　中不必如此精確。當(dāng)然謹(jǐn)慎點(diǎn)可以取得任意的期望精度。例如：如果要V0和Pk

52、精確到100，我</p><p>　　們僅需要計(jì)算opt(v,k)，其中V是100的倍數(shù)。這同時(shí)降低了時(shí)間復(fù)雜度和空間復(fù)雜度。更準(zhǔn)</p><p>　　確地說(shuō)，對(duì)于精度P，時(shí)間與空間復(fù)雜度分別為和。實(shí)際上，我們一般僅需要處理K≤10和v0/p≤1000的情況，所以算法復(fù)雜度是相當(dāng)?shù)偷摹?lt;/p><p>　　4.2.3給定charging volumes來(lái)分配通信量&

53、lt;/p><p>　　給定charging volumes，對(duì)于ISP k取名為pk，下面我們來(lái)描述如何在各個(gè)時(shí)間段來(lái)分配通信量。通信量分配的目的在于確保pk是ISP k的通信量；也就是說(shuō)，在qk*I個(gè)間隔內(nèi)，分配給ISP k的通信量將小于或等于pk，并且ISP k僅被允許在剩下的(1-qk)*I個(gè)時(shí)間間隔內(nèi)提供比pk多的服務(wù)。這點(diǎn)可以通過(guò)將時(shí)間間隔劃分為非高峰時(shí)間間隔和高峰時(shí)間間隔來(lái)達(dá)到。</p>

54、<p>　　根據(jù)V0的定義，在總通信量不大于V0的時(shí)間間隔內(nèi)，所有的通信可在任何一個(gè)ISP接受的通信量不多于其charging volume的情況下來(lái)能成。因此，我們稱這些時(shí)間間隔為非高峰時(shí)間間隔。對(duì)剩下的間隔，至少有一個(gè)ISP要實(shí)際承擔(dān)比其charging volume要多的通信量。正因?yàn)槿绱?，我們稱剩下的間隔為高峰時(shí)間間隔。我們將用下本文下面部分這兩個(gè)術(shù)語(yǔ)。</p><p>　　根據(jù)上面對(duì)高峰和非高

55、峰時(shí)間間隔的定義，我們根據(jù)以下方法來(lái)分配通信量。如果時(shí)間間隔是非高峰的，我們分配給ISP k的通信量將小于等于pk。有多種分配方法可實(shí)現(xiàn)以上限制的分配，并且這些分配方法的成本是一樣的。所有我們?nèi)稳∫粋€(gè)。在di五段，我們將利用這點(diǎn)靈活性來(lái)提高性能。對(duì)于高峰時(shí)間間隔，將隨機(jī)挑選一個(gè)ISP k來(lái)超標(biāo)（即，分配給他的通信量將超過(guò)pk）。這通過(guò)分配給剩下的ISPs各自的pk，然后將剩余的通信量統(tǒng)統(tǒng)分配給超標(biāo)的那個(gè)ISP。在我們所假設(shè)的ISPs沒(méi)有

56、容量限制的情況下，這樣分配是合理的。（我們將研究ISPs有容量限制的情況下的流量分配情況）</p><p>　　總結(jié)以上研究，我們即得出圖3中對(duì)可分流成本降低的算法。很容易看出，pk肯定是ISP k</p><p>　　的charging volume，因?yàn)镮SP k在(1-qk)×I時(shí)間間隔內(nèi)接受的通信量多于pk。由于根據(jù)定理</p><p>　　2,p

57、k的總和等于V0，則該算法實(shí)現(xiàn)了最低成本。</p><p>　　8 頁(yè) 共 28 頁(yè)</p><p>　　圖3:在基于百分比的收費(fèi)模式、沒(méi)有容量限制的情況下，對(duì)可分流分配的一個(gè)離線優(yōu)化算法。</p><p>　　4.2.4處理容量限制</p><p>　　前面算法假設(shè)ISPs沒(méi)有容量限制（即，他們可在時(shí)間間隔內(nèi)傳送所有的通信量）。這個(gè)假設(shè)是合

58、理的，因?yàn)閙ultihoming常被用來(lái)提供高可靠性的服務(wù)，即使其他所有的ISP s都斷了，用來(lái)還能使用剩下的哪個(gè)ISP s。然而單個(gè)的ISP也可能沒(méi)有足夠的容量來(lái)處理所有的通信。</p><p>　　圖4:整體分流離線分配算法（GFA-offline）：一個(gè)基于百分比收費(fèi)模式，并在容量限制情況下的算法。成本函數(shù)ck(x)假設(shè)當(dāng)x超過(guò)ISP k的容量時(shí)將達(dá)到無(wú)窮大。常量在我們搜索f時(shí)控制步進(jìn)大小，為高峰時(shí)間間隔的

59、最大部分（在我們的評(píng)估中＝0.01）。</p><p>　　我們利用圖4中的算法來(lái)處理容量限制的情況。其基本思想是選擇高峰時(shí)間間隔，記為f，因此在每個(gè)高峰時(shí)間間隔期間有多個(gè)ISPs一起提供足夠的容量來(lái)傳送所有的通信。更一般地 ， 給 定 d 和 相 應(yīng) 的 V0 及 pk （ 在 圖 4 的 while － loop 中 計(jì) 算 ）， 我 們 需 要 知 道</p><p>　　，即，分配

60、給不同的ISPs f×I高峰時(shí)間間隔是否滿足（i）沒(méi)有ISP k服務(wù)了超過(guò)（1-qk）×I個(gè)時(shí)間間隔，（ii）在每個(gè)高峰間隔期間有足夠的總?cè)萘俊?lt;/p><p>　　將能在任意高峰時(shí)間間隔內(nèi)能處理通信的 ISPs 集合記為 g 。一個(gè) g 的足夠情況是</p><p>　　其中Ck連接k的容量，maxload是收費(fèi)期間的最大負(fù)擔(dān)。</p><p>

61、;　　tg記為組g中ISPs承擔(dān)負(fù)載的時(shí)間間隔數(shù)。G記為所有（2k）可能ISP組。當(dāng)滿足下面情況，將</p><p>　　存在一個(gè)高峰時(shí)間間隔，且將返回真。</p><p>　　下面是些說(shuō)明。首先，K一般很?。ㄈ?，小于10），因此變量的個(gè)數(shù)是可管理的。第二，上面條件是充分不必要的，因?yàn)榧词垢叻鍟r(shí)期承擔(dān)的通信量總是最大通信量，我們?nèi)阅芊峙洹Ｈ欢热桓叻鍟r(shí)間間隔間分配的通信量總是低于最大分配

62、量（如：95%的分配小于最大分配量），那么即使上面情形不滿足，仍然能進(jìn)行高峰分配。當(dāng)最大分配量與最小分配量差不</p><p>　　9 頁(yè) 共 28 頁(yè)</p><p>　　多時(shí)，狀況就很緊了。第三，所有這些限制是線性的，因此我們可以通過(guò)解決一個(gè)整型編程問(wèn)題來(lái)決定存在的最大負(fù)載的分配。既然間隔的數(shù)目巨大，在實(shí)踐中我們首先解決沒(méi)有整型限制的情形，然后通過(guò)變園來(lái)得出結(jié)果。</p>

63、<p>　　我們稱這個(gè)分配算法為全局部分離線分配（GFA-offline）。</p><p>　　4.3在線整式分配算法</p><p>　　上一段離線部分分配算法假設(shè)通信模式事先已知，并且通信流是可以劃分的。在實(shí)際中，通信模式不會(huì)事先給定。更進(jìn)一步，也許人們傾向于不可分的流（為了減少控制，如實(shí)際中使用的BGP）。在本段中，我們展示在線整式分配算法來(lái)處理兩種這情況。我們的解決辦

64、法由下面兩步組成：</p><p>　　預(yù)測(cè)在下一個(gè)時(shí)間間隔中的通信和V0。</p><p>　　根據(jù)預(yù)測(cè)的通信來(lái)計(jì)算整式分配。我們將詳細(xì)描述每一個(gè)步驟。</p><p>　　4.3.1 預(yù)測(cè)通信及V0</p><p>　　首先，如圖5所示，我們通過(guò)一個(gè)指數(shù)加權(quán)移動(dòng)平均數(shù)（EWMA）預(yù)測(cè)整體和每一個(gè)流通信。</p><p&

65、gt;　　那就是。注意到對(duì)應(yīng)于僅通過(guò)上</p><p>　　一時(shí)間間隔預(yù)測(cè)的通信。我們的估測(cè)顯示與得出相似的結(jié)果。</p><p>　　圖5:PredictTraffic()子程序：預(yù)測(cè)總流量即每股流量</p><p>　　在通信預(yù)測(cè)中有幾點(diǎn)技術(shù)細(xì)節(jié)需要提及。首先，避免為太多流保留記錄，我們周期性地移除預(yù)測(cè)的最小通信。第二，當(dāng)流第一次出現(xiàn)，我們將直接利用當(dāng)前時(shí)間間隔

66、的通信量來(lái)預(yù)測(cè)其下一時(shí)間間隔的通信（由于其沒(méi)有任何其他記錄）。第三，既然預(yù)測(cè)的總通信量與我們追蹤的流的預(yù)測(cè)量的總和可能不一致，我們?cè)谒惴ㄖ屑尤胗靡哉；囊徊健?lt;/p><p>　　除了通信，我們也需要預(yù)測(cè)V0以來(lái)決定下一時(shí)間間隔是否是高峰時(shí)間間隔。清楚地講，如果我們低估V0，那么我們可能最終會(huì)太早些時(shí)候詳盡研究高峰時(shí)間間隔的配額，所以增加單個(gè)ISPs的charging volumes會(huì)導(dǎo)致整體成本的整加。為避免

67、這一后果，我們根據(jù)以下辦法來(lái)較保守地更新V0。我們使用上一收費(fèi)期間的V0值作為初始V0值。我們還維護(hù)了一個(gè)滑動(dòng)窗口（其長(zhǎng)度等于收費(fèi)時(shí)期），在每一間隔期后我們計(jì)算最近滑動(dòng)窗口的V0值，記為。每當(dāng) 超過(guò)V0，我們?cè)黾覸0到，并根據(jù)新的V0值重新計(jì)算左右的charging volumes。在我</p><p>　　們的追蹤中，使，我們能迅速跟蹤V0的增加而不射擊過(guò)高而超過(guò)太多。</p><p>

68、　　當(dāng)重新計(jì)算charging volumes，我們需要確保對(duì)每一個(gè)k，新的charging volume 不</p><p>　　會(huì)比老的charging volume pk小。否則，即如果，那么可能有很多以前的時(shí)間間隔（大概多于（1-qk）I），其中我們分配給ISP k的通信量將多于（但小于pk），因此要確</p><p>　　保會(huì)很難。我們可以應(yīng)用在4.2.2.2段中的動(dòng)態(tài)算法來(lái)計(jì)算

69、，｛pk｝的下</p><p>　　10 頁(yè) 共 28 頁(yè)</p><p>　　限可以很容易地通過(guò)設(shè)定對(duì)所有的x<pk有來(lái)確保。</p><p>　　4.3.2進(jìn)行離線整式分配</p><p>　　我們首先指出甚至在一離線設(shè)置中隨著通信的完美知識(shí),整式分配問(wèn)題已經(jīng)是艱難.更特別,我們有下列的負(fù)結(jié)果(請(qǐng)見(jiàn)附錄B的證明):</p>

70、;<p>　　定理5: 事實(shí)上沒(méi)有多項(xiàng)式的時(shí)間算法能夠取得使整式分配與一般成本函數(shù)的比率為一個(gè)近似常數(shù)，除非P=NP。</p><p>　　上面的負(fù)結(jié)果使得很容易去考慮類似的算法。我們建議下面的（離線）貪婪算法來(lái)進(jìn)行整式分配。如圖6所示，</p><p>　　圖6:OfflineIntegral()子程序：一個(gè)離線貪婪整式流分配算法</p><p>　

71、　我們首先運(yùn)行離線部分流分配算法來(lái)找除charging volumes pk。根據(jù)ISP k的pk，我們計(jì)算出要分配給他的目標(biāo)通信量；我我們稱該值為時(shí)間間隔中的偽容量（簡(jiǎn)稱為Pseudo Cap）。對(duì)于ISP k不是burst ISP的非高峰時(shí)間間隔或者高峰時(shí)間間隔，ISP k的偽容量是其通過(guò)部分流分配算法計(jì)算的charging volume；對(duì)高峰時(shí)間間隔，其中ISP k是一個(gè)burst ISP，其偽容量是其連接容量CK。我們的目標(biāo)是

72、確保分配給任意ISP的容量不超過(guò)其偽容量。</p><p>　　概念上講，這個(gè)問(wèn)題類似于打包問(wèn)題，因此可以通過(guò)貪婪算法來(lái)解決。特別的，我們可以初始化每個(gè)ISP為其偽容量，再根據(jù)他們產(chǎn)生的通信量來(lái)進(jìn)行流的降序排列，然后重復(fù)的將剩余的最大偽容量分配給ISPs。圖6中的實(shí)際算法將概念上的貪婪分配分為兩個(gè)步驟。其首先將pk作為包的大小進(jìn)行通信分配，然后重新填充包大小為（PseudoCapk－pk），接著分配剩余的通信量。

73、我們發(fā)現(xiàn)通過(guò)這兩步使得其更可能有ISP具有大的剩余的包大小。那是這個(gè)ISP即可以用來(lái)在一個(gè)在線算法中設(shè)定容納通信以處理以前沒(méi)有遇到過(guò)的前綴。</p><p>　　4.3.3包容預(yù)測(cè)中的錯(cuò)誤</p><p>　　圖6中顯示的整式分配算法在離線通信要求中可以很好的工作。然而，在在線設(shè)置中，預(yù)測(cè)的通信由于預(yù)測(cè)錯(cuò)誤也許與實(shí)際的通信流量不相符合。如果我們?cè)谔畛溥B接的偽容量時(shí)太貪婪了，那么預(yù)測(cè)錯(cuò)誤可能

74、導(dǎo)致實(shí)際使用的超過(guò)目標(biāo)偽容量，因此，顯著增加了實(shí)際成本。我們解決的辦法是當(dāng)計(jì)算charging volumes時(shí)增加一些邊界，然后向后縮小其；我們調(diào)整后</p><p>　　11 頁(yè) 共 28 頁(yè)</p><p>　　的算法如圖7?？梢钥闯鲈O(shè)定margin＝0.05*V0在我們的追蹤中可能很好的工作。</p><p>　　圖7:通過(guò)調(diào)整pk來(lái)處理預(yù)測(cè)錯(cuò)誤</p

75、><p><b>　　4.3.4最終算法</b></p><p>　　將所有東西放在一起，我們得出圖8中的最終在線算法。這個(gè)算法是全局整體在線分配算法（GIA-online）。</p><p>　　圖8:全局整體在線流分配算法（GIA-online）</p><p>　　5.在成本限制的條件下優(yōu)化性能</p>

76、<p>　　在前面章節(jié)中，我們研究了如何為用戶來(lái)降低成本。在實(shí)際中，一個(gè)明智的路由算法需要同時(shí)考慮成本及性能。</p><p>　　5.1 問(wèn)題公式化及概述</p><p>　　有多種方法可將優(yōu)化性能和成本的問(wèn)題公式化。比如，一個(gè)可能就是設(shè)計(jì)一個(gè)對(duì)成本及性能綜合度量的度量標(biāo)準(zhǔn)。然而，對(duì)用戶而言卻可能對(duì)成本及性能相關(guān)比重問(wèn)題不大清楚。一個(gè)更直接點(diǎn)的辦法，如本文中所建議的是，以來(lái)在給

77、定成本限制情況下優(yōu)化性能。</p><p>　　在前面，我們一并設(shè)計(jì)了離線與在線算法。兩個(gè)算法都由兩個(gè)關(guān)鍵部分組成。第一個(gè)組件是第二個(gè)組件的基礎(chǔ)。</p><p>　　給定每個(gè)時(shí)間間隔下每個(gè)ISP的偽容量，稱為可以分配給一個(gè)ISP的通信量的上界，我們分配通信流量以使總延遲最小。我們稱這個(gè)組件為給定偽容量流分配。</p><p>　　既然一個(gè)給定成本限制允許多偽容量分

78、配，不同的分配方案有著其不同的延遲，我們將需要選擇適當(dāng)?shù)牧鞣峙浞桨敢杂泻玫男阅堋Ｎ覀兎Q此組件為偽容量選擇。</p><p>　　5.2離線通信流分配</p><p>　　我們首先展示了一個(gè)離線算法。</p><p>　　12 頁(yè) 共 28 頁(yè)</p><p>　　5.2.1給定偽容量的流分配</p><p>　　給定偽

79、容量下整體流分配是為了最小化總延遲，這樣分配給每個(gè)ISP的流量將不超過(guò)其偽容量。</p><p>　　我們通過(guò)構(gòu)造如圖9稱為最小化多重流分配（MCMCF）來(lái)解決流的分配問(wèn)題。在圖中，最上行的每一個(gè)節(jié)點(diǎn)代表了通信流的源，而最下行的節(jié)點(diǎn)代表了通信流的目的地。中間兩行的節(jié)點(diǎn)代表了ISPs。從源節(jié)點(diǎn)f到目的ISP節(jié)點(diǎn)k連接的成本perf(k,f)，下一行是流f到ISP的延遲；其他連接的成本是0。第二行的每個(gè)ISP節(jié)點(diǎn)對(duì)應(yīng)

80、到第三行的連接容量是ISP的偽容量；其他連接的容量是無(wú)限的。</p><p>　　圖9:流分配問(wèn)題的MCMCF公式化</p><p>　　5.2.2偽的容量選擇</p><p>　　給定偽容量，上述算法計(jì)算流分配以優(yōu)化延遲。下面我們研究怎樣決定每個(gè)時(shí)間間隔期間連接的偽容量。</p><p>　　偽容量由成本限制來(lái)決定。在沒(méi)有成本限制的情況下，

81、每個(gè)ISP能分配通信高達(dá)其連接容量，即，一個(gè)連接的偽容量是其源生容量。然而，既然我們的目標(biāo)是在成本限制的情況下優(yōu)化性能，我們應(yīng)用在第四段中描述的算法，其利用一個(gè)連接能承擔(dān)多少通信量為限制。更特別的說(shuō)，我們基于成本優(yōu)化來(lái)取得ISP k的charging volume pk。那么，在非高峰時(shí)間間隔期間，每個(gè)ISP的通信不應(yīng)超過(guò)pk（即，ISP k的偽容量為pk）。</p><p>　　高峰時(shí)間間隔期間的偽容量也并不完

82、全由成本優(yōu)化來(lái)限制。由成本優(yōu)化而產(chǎn)生的限制是每個(gè)ISP可以超過(guò)pk僅（1-qk）* I個(gè)時(shí)間間隔，因此我們?cè)诿總€(gè)單獨(dú)的高峰時(shí)間間隔內(nèi)仍有很大的靈活性來(lái)選擇合適的ISPs。下面，我們將描述高峰時(shí)間間隔期間在成本限制的情況下來(lái)決定合適偽容量的算法。</p><p>　　決定高峰時(shí)間間隔期間偽容量的關(guān)鍵一步就是選擇哪個(gè)或哪組ISPs來(lái)分流。在一個(gè)給定的高峰時(shí)間間隔內(nèi)選擇合適的ISPs可被分為兩步來(lái)作。首先，我們得出在一

83、個(gè)給定高峰時(shí)間間隔內(nèi)選擇任一組ISPs得到的最佳性能。這一步可以這樣來(lái)做，首先設(shè)定被選擇的ISPs的偽容量為其連接容量，剩余連接的偽容量為他們的charging volumes，然后調(diào)用在5.2.1段中的算法。</p><p>　　下一步，我們?cè)诒ＷC成本限制的情況下優(yōu)化在整個(gè)收費(fèi)期間的性能（即，每個(gè)ISP可以在qk*I個(gè)時(shí)間間隔內(nèi)被選擇）。用BestPerf(g, i)來(lái)標(biāo)示用5.2.1段中算法所計(jì)算得出的最佳性

84、能，當(dāng)ISP設(shè)定g在時(shí)間間隔i內(nèi)被選擇。然后下一步?jīng)Q定那些ISPs在每個(gè)高峰時(shí)間間隔內(nèi)被選擇能被映射到圖10所示的混合整式編程（MIP）問(wèn)題。這個(gè)MIP可以用LP軟件來(lái)解決，如lp_solve〔14〕。</p><p>　　13 頁(yè) 共 28 頁(yè)</p><p>　　圖10:決定選擇合適ISPs的MIP公式</p><p><b>　　5.3在線算法<

85、;/b></p><p>　　下面我們展示在線算法。在設(shè)計(jì)在線算法時(shí)，我們有兩個(gè)新的問(wèn)題需要解決。第一點(diǎn)是我們需要同時(shí)預(yù)測(cè)通信量及性能。第二是我們需要一個(gè)有效的算法來(lái)為ISPs選擇合適的偽容量和分配通信量。</p><p>　　5.3.1預(yù)測(cè)通信量及性能</p><p>　　我們同樣用圖8中的方法來(lái)預(yù)測(cè)通信模式。為預(yù)測(cè)性能，我們?cè)俅卫弥笖?shù)級(jí)移動(dòng)平均</

86、p><p><b>　　數(shù)。</b></p><p>　　5.3.2進(jìn)行通信分配</p><p>　　我們用下面的貪婪啟發(fā)來(lái)在線分配通信量。在時(shí)間間隔i內(nèi)，一股通信流是分配給所有有足夠偽容量的ISPs中具有最佳預(yù)測(cè)性能的ISP的。我們注意到流分配的次序?qū)⒂绊懙叫阅堋?lt;/p><p>　　特別是，我們發(fā)現(xiàn)以降序 次序來(lái)分配流會(huì)

87、得到較好的性能，其中</p><p>　　是預(yù)測(cè)的具備最佳性能的ISP與最糟性能的ISP的性能差，而是在時(shí)間間隔</p><p>　　i內(nèi)f流的量。類似于圖6,我們將貪婪分配過(guò)程分為兩個(gè)獨(dú)立的過(guò)程，所以我們可以更好地來(lái)容納以前沒(méi)有出現(xiàn)過(guò)的通信量。</p><p><b>　　6.評(píng)測(cè)</b></p><p>　　在本段中

88、，我們?cè)u(píng)測(cè)在前面章節(jié)中設(shè)計(jì)的算法的性能。我們?nèi)〉脙山M通信流量的追蹤數(shù)據(jù)：Abilene追蹤數(shù)據(jù)及一個(gè)大型web服務(wù)器的流量數(shù)據(jù)。Abilene數(shù)據(jù)包含從2003年10月8日到2004年6月6日的一些大學(xué)及企業(yè)在Internet-2上的網(wǎng)絡(luò)流量數(shù)據(jù)。在我們的評(píng)測(cè)中，將選擇表2中的組織的流量追蹤。為加速我們的評(píng)測(cè)，在每五分鐘的時(shí)間間隔，我們僅使用最大容量前綴的2000個(gè)目的地。我們稱這些前綴為最高前綴。注意到在不同的時(shí)間間隔內(nèi)，最高前綴的集

89、合是不一樣的，但他們總是超過(guò)一個(gè)時(shí)間間隔內(nèi)總通信量的90%。</p><p>　　14 頁(yè) 共 28 頁(yè)</p><p>　　表2:我們?cè)u(píng)測(cè)中使用的通信流量追蹤，其中最后一列顯示了組織在91天中的平均通信量，過(guò)濾后的通信量顯示在括號(hào)內(nèi)。</p><p>　　為多樣化，我們也使用了從以大型商業(yè)web服務(wù)器追蹤得到的從2003年10月1日到2003年12月31日期間的通

90、信流量。追蹤數(shù)據(jù)中包含web請(qǐng)求的主機(jī)的IP地址，還有其時(shí)間郵戳及請(qǐng)求文件大小?？紤]到效率問(wèn)題，web服務(wù)器前端部署了一組代理緩存。大概有一半對(duì)web服務(wù)器的請(qǐng)求被將IP地址換為代理的IP地址從而被重定向到代理。由于我們僅對(duì)廣域網(wǎng)的通信流量感興趣，我們過(guò)濾了重定向請(qǐng)求。此外，與Abilene追蹤一樣，我們僅考慮每五分鐘間隔期間前最高2000前綴產(chǎn)生的通信量。表2中最后一列顯示了過(guò)濾前與過(guò)濾后的通信流量。可注意到web服務(wù)器過(guò)濾前后的差距

91、比Abilene追蹤大，其是因?yàn)檫^(guò)濾了重定向的請(qǐng)求。</p><p><b>　　6.1評(píng)測(cè)成本優(yōu)化</b></p><p>　　我們將在下面改變中比較在段4中成本優(yōu)化算法的性能（即，圖4中GFA在線和圖8中GIA在線）：</p><p>　　輪詢：在每個(gè)時(shí)間間隔中，通信量被分配個(gè)一個(gè)單獨(dú)的ISP，我們循環(huán)選擇負(fù)責(zé)通信的ISP。如果被選擇的IS

92、P沒(méi)有足夠的容量來(lái)傳輸所有的通信量，剩余的通信量也將按照循環(huán)的方式分配給其他ISP。</p><p>　　均分：在每個(gè)時(shí)間間隔期間，通信量被在所有ISPs中平均分配。當(dāng)有容量限制時(shí)，我們首先將連接按容量降序排列。這樣，我們分配給ISP k的就是Ck中最小的通信量 rem_traf/rem_nisps，其中 rem_trap 是剩余的被分配的通信量，rem_nisps是還沒(méi)有被分配以通信量的ISPs的數(shù)量。<

93、/p><p>　　本地部分離線（LEA離線）：在每個(gè)時(shí)間間隔i內(nèi)我們決定合適的分配以使</p><p>　　最小。在成本是在當(dāng)前時(shí)間間隔內(nèi)的通信量（而不是qk百分比的通</p><p>　　信量）的函數(shù)的前提下，這根本上最小化了總成本。為決定優(yōu)化分配，我們應(yīng)用在4.2段中介紹的動(dòng)態(tài)編程算法，其將當(dāng)前時(shí)間間隔中總通信量作為輸入來(lái)產(chǎn)生最小的成本消耗。</p>

94、<p>　　專用連接：現(xiàn)在的市場(chǎng)中，除了共享連接還可以購(gòu)買專用連接。專用連接有固</p><p>　　定的利率，其與使用量沒(méi)有關(guān)系，即使其通信量為0。</p><p>　　我們?cè)谠u(píng)測(cè)中使用基于95%百分比的收費(fèi)模式來(lái)產(chǎn)生一個(gè)可突發(fā)連接的成本。給定一個(gè)追蹤，我們決定專有連接中最小成本的一組連接，這些連接的總?cè)萘磕苋菁{當(dāng)前收費(fèi)期間最</p><p>　　15

95、頁(yè) 共 28 頁(yè)</p><p><b>　　大通信量。</b></p><p>　　圖11：不同追蹤的總成本的對(duì)比，其中每個(gè)用戶具備4個(gè)到Internet的連接，且每個(gè)連接的成本由一個(gè)簡(jiǎn)單的價(jià)格函數(shù)來(lái)決定</p><p>　　我們以考慮一個(gè)簡(jiǎn)單的價(jià)格函數(shù)來(lái)開(kāi)始我們的評(píng)測(cè)：如果charging volume大于0,那么一個(gè)ISP連接的價(jià)格將是一

96、個(gè)常數(shù)，這個(gè)值是表1中的一個(gè)條目。在我們的第一個(gè)試驗(yàn)中，我們考慮一個(gè)具備4個(gè)到Internet連接的用戶。我們隨機(jī)選擇表1中10個(gè)連接中的4個(gè)及相應(yīng)的容量限制。由于有可能同樣類型卻有多重連接，我們?cè)试S重復(fù)。圖11顯示了運(yùn)用不同通信分配算法的5組追蹤所消耗的正?；某杀?。這兒正常化的成本由基于特定分配算法的可選連接的成本與專有連接的成本的比率來(lái)決定。注意到除了GIA在線，所有的算法是離線算法；所有他們能預(yù)先知道通信模式。</p>

97、;<p>　　我們可有如下觀察。首先，如期望的，GFA離線算法產(chǎn)生最佳性能。GIA在線算法由于預(yù)測(cè)錯(cuò)誤比其離線版本有適當(dāng)高點(diǎn)的成本。然而，其仍然比LE離線算法有較低（稍低）的成本損耗，比輪詢及均分有著低的多的成本損耗。其次，我們發(fā)現(xiàn)對(duì)可選連接應(yīng)用GFA離線算法、GIA在線算法或者LFA離線算法都相對(duì)于專有連接有著低的成本損耗。另一方面，對(duì)可選連接應(yīng)用輪詢或者均分，會(huì)比專有連接有著高的多的成本損耗。最后，我們可以發(fā)現(xiàn)，這些算

98、法的相關(guān)比率仍然與收費(fèi)期間從一周到一月相同。</p><p>　　我們下一步將用較復(fù)雜的價(jià)格函數(shù)來(lái)估測(cè)我們算法在不同價(jià)格函數(shù)間的健壯性，其在第三段中介紹過(guò)。圖12總結(jié)了結(jié)果。我們發(fā)現(xiàn)GFA離線算法仍然有最好的性能。其在線版本由于預(yù)測(cè)錯(cuò)誤還是相對(duì)稍稍遜色，但比其他算法要好。</p><p>　　16 頁(yè) 共 28 頁(yè)</p><p>　　圖12：在不同追蹤數(shù)據(jù)間比較總

99、成本，其中每個(gè)用戶有4個(gè)鏈路來(lái)連接到Internet，且每個(gè)連接的成本是通信量的分段線性函數(shù)，如圖2中所示。</p><p>　　下面，我們來(lái)研究不同數(shù)目連接的影響。圖13顯示了連接數(shù)從2到15變化時(shí)其相應(yīng)成本的變化。與前面一樣，GFA離線算法具有最好的性能，其次是GIA在線算法。我們發(fā)現(xiàn)正?；腉FA離線算法和GIA在線算法隨著可用連接數(shù)的增加而減小。這是因?yàn)樗麄兛梢栽诟叻鍟r(shí)刻選擇ISP使其在滿負(fù)載下工作而不增

100、加額外的成本。相反，我們發(fā)現(xiàn)正?；妮喸儭⒕旨癓IA離線算法隨著連接數(shù)的增加而增加。</p><p>　　最后，我們成本隨著時(shí)間變化的動(dòng)態(tài)性。圖14劃分了在收費(fèi)期間為一周時(shí)成本在13周內(nèi)的變化。如圖中所示，GFA離線與GIA在線算法明顯比其他三個(gè)算法效率高。由于GFA離線和GIA在線算法正?；某杀疽话惚?低，可選連接應(yīng)用這些算法的成本明顯比專用連接低。我們還可發(fā)現(xiàn)GFA在線算法有時(shí)與GFA離線算法性能相同，如

101、圖16中b圖的第四周。這是因?yàn)镚FA離線算法沒(méi)有確保在容量限制情況下的優(yōu)化。</p><p>　　17 頁(yè) 共 28 頁(yè)</p><p>　　圖13：運(yùn)用圖2中的分段線性價(jià)格函數(shù)來(lái)對(duì)比不同路由體系下的成本對(duì)比</p><p>　　圖14：不同追蹤間的時(shí)間劃分，其中每個(gè)用戶有4個(gè)鏈路來(lái)連接到Internet，每個(gè)鏈路的成本是其charging volume的分段線性函

102、數(shù)，如圖2中所示。</p><p>　　總結(jié)：我們的評(píng)測(cè)表明GFA離線算法如我們所期望有著最低的成本。更進(jìn)一步講，其在線版本在通信量沒(méi)有波動(dòng)性的情況下也有很強(qiáng)的競(jìng)爭(zhēng)性――其常常能比其他的選擇有一定數(shù)量的性能提升。</p><p>　　6.2 評(píng)測(cè)在成本限制的情況下的性能優(yōu)化</p><p>　　下面我們?cè)u(píng)測(cè)在成本限制情況下的延遲優(yōu)化。在本段中，我們主要關(guān)注現(xiàn)實(shí)中In

103、ternet</p><p>　　18 頁(yè) 共 28 頁(yè)</p><p>　　上中RTT變分的在線算法的評(píng)測(cè)。在下一段，我們將進(jìn)一步檢測(cè)當(dāng)多用戶間相互影響時(shí)的 smart routing的性能。</p><p>　　為評(píng)測(cè)給定通信要求追蹤下的smart routing的益處，我們將在通信量收集期間在源和目的節(jié)點(diǎn)間理想化的使用輪詢時(shí)間（RTT）辦法。由于缺少這些測(cè)量數(shù)

104、據(jù)，我們?cè)谠u(píng)測(cè)中使用NLANR〔16〕中法部的數(shù)據(jù)。NLANR追蹤由從2003奶奶10月到2004年1月間140所大學(xué)的RTT測(cè)量。為了取得一股通信流的言辭，我們首先用如下方法組建虛擬ISPs。我們將Rocket dataset〔22〕中的ISPs映射到NLANR追蹤中最近的大學(xué)。運(yùn)用CAIDA中NetGeo項(xiàng)目中的數(shù)</p><p>　　據(jù)庫(kù)，我們?nèi)〉迷贏bilene追蹤中每個(gè)目標(biāo)前綴的物理對(duì)應(yīng)。我們將每個(gè)前綴

105、映射到最近的每個(gè)ISP幾點(diǎn)。一個(gè)給定ISP從原先到前綴的的延遲被分配為原先在NLANR追蹤中的大學(xué)與被分配給前綴的ISP節(jié)點(diǎn)的RTT。我們也加入了基于光速和一個(gè)前綴和其ISP節(jié)點(diǎn)間距離的最新跳躍延遲。這樣，我們?nèi)〉梅从超F(xiàn)實(shí)Internet RTT變化和ISP間地理性能相關(guān)的延遲追蹤。</p><p>　　注意到NLANR中延遲追蹤大多在US內(nèi)主機(jī)間，因此我們過(guò)濾了US外的目的前綴的通信量。這樣的過(guò)濾減少了通信量大

106、概20%～60%，增加了通信的可變性（由于更小的集合）。這增加的可變性將進(jìn)一步對(duì)我們的在線算法進(jìn)行“壓力測(cè)試”。</p><p>　　圖15比較了不同路由體系間的成本及性能，其中圖15(a)由離線成本優(yōu)化算法來(lái)正?；?。</p><p><b>　　我們可有如下觀察。</b></p><p>　　首先，比較三個(gè)離線算法，我們發(fā)現(xiàn)單獨(dú)優(yōu)化性能會(huì)將成

107、本增加到與成本一同優(yōu)化情況下的2.75倍，但是單獨(dú)優(yōu)化成本會(huì)導(dǎo)致延遲增加了一同優(yōu)化性能情況下的33%。相反，離線成本性能算法取得了兩方面的提升：低成本和低延遲。</p><p>　　第二，比較離線算法與他們的相應(yīng)的在線版本，我們發(fā)現(xiàn)在線版本會(huì)由于預(yù)測(cè)錯(cuò)誤而產(chǎn)生較高的成本。可注意到離線與在線版本成本的差別比前面段中大，這是因?yàn)檫@兒我們過(guò)濾了相當(dāng)大數(shù)量的非US通信，這增加了通信的變化性。然而，在線成本性能一起優(yōu)化比單

108、獨(dú)優(yōu)化性能成本低，且產(chǎn)生的延遲缺差不多（在10~20%內(nèi)）。</p><p>　　圖16進(jìn)一步比較了運(yùn)用時(shí)間劃分下不同算法的延遲。如其所示，在大多情況下用在線成本性能一并優(yōu)化產(chǎn)生的延遲在離線性能優(yōu)化的后面。這就是說(shuō)在線成本性能優(yōu)化算法能有效的追蹤延遲和通信量的變化。有事其延遲顯著地比純性能優(yōu)化高。這是由成本限制導(dǎo)致，說(shuō)明了成本優(yōu)化與性能優(yōu)化之間有一定的關(guān)系。但是兩者間性能差別通常很小（小于10%）。當(dāng)與單獨(dú)優(yōu)化成