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

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

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

3、―英特網(wǎng)</p><p><b>　　通用術(shù)語:</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)勢，常被大型企業(yè)和英特網(wǎng)服務(wù)提供商用以接入 Internet。一個客戶或 ISP 網(wǎng)絡(luò)（也可以叫做用戶）有著多個外部連接（或一個 ISP 或者多個服務(wù)提供商），即可被說成 multihomed[31]。一個用戶如果能有效地控制其通信量在多個外部連接上的分布，就可以說成實現(xiàn)了 sma

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

43、察是最小化Σkpk的值等同于qt(V, 1-Σk(1-pk))。舉個例子，有4個ISP，它們都是基于95%的量進(jìn)行收費，那么最小化Σkpk即等于總通信量的80%(1-4*(1-95%)=0.80)。這兩點觀察說明了要優(yōu)化成本，我們需有Σkpk＝qt(V, 1-Σk(1-pk))，其中的V與qk很容易算出。</p><p>　　現(xià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),其中第一個不等式是由于價值函數(shù)Ck是單調(diào)非減函數(shù)的，第二個不等式是根據(jù)Cmin的定義。</

45、p><p>　　第二點觀察，書面表述如定理2,確定了Σkpk可達(dá)的最低下限。</p><p><b>　　定理2: </b></p><p>　　要證明該定理，我們將用刀以下lemma，lemma的證明見附錄A</p><p>　　LEMMA 3（quantile inequality）給定K等長時間序列，其</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>　　以通過重新調(diào)整qk為來保證其整型值。清楚地看出，這樣的調(diào)整不會影響</p><p

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

66、的通信量來預(yù)測其下一時間間隔的通信（由于其沒有任何其他記錄）。第三，既然預(yù)測的總通信量與我們追蹤的流的預(yù)測量的總和可能不一致，我們在算法中加入用以正常化的一步。</p><p>　　除了通信，我們也需要預(yù)測V0以來決定下一時間間隔是否是高峰時間間隔。清楚地講，如果我們低估V0，那么我們可能最終會太早些時候詳盡研究高峰時間間隔的配額，所以增加單個ISPs的charging volumes會導(dǎo)致整體成本的整加。為避免

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

85、;/b></p><p>　　下面我們展示在線算法。在設(shè)計在線算法時，我們有兩個新的問題需要解決。第一點是我們需要同時預(yù)測通信量及性能。第二是我們需要一個有效的算法來為ISPs選擇合適的偽容量和分配通信量。</p><p>　　5.3.1預(yù)測通信量及性能</p><p>　　我們同樣用圖8中的方法來預(yù)測通信模式。為預(yù)測性能，我們再次利用指數(shù)級移動平均</

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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