【文章內(nèi)容簡介】 一個潛在提供者的分組開始確定某一分組的提供者. 之后是對應有兩個潛在提供者的分組, 以此類推. 如果一個分組對應著多個潛在提供者, 那么具有最高帶寬并且具有更長可用時間的提供者會被選中. Fig3 列出了這個算法的偽碼. 對于每個結(jié)點, 都將會執(zhí)行該算法. 它的時間復雜度為 O( W * B * M ). 在具體的實現(xiàn)中, 每次執(zhí)行僅需15ms. 計算的額外開銷并不高. 因此, 它可以比較頻繁地運行, 從而更新調(diào)度策略. Fig3 每個DONet結(jié)點調(diào)度算法的偽碼( 譯者注: 個人認為, 該偽碼包含部分打印錯誤:自Scheduling: 一行起, 向下四行, 有: T[j,i]. 個人認為應該改為: t[j,i]第一個if語句中的for循環(huán), 包含一個循環(huán)控制條件, 原文為: jk. 個人認為應該改為 ji再向下五行, 原文為 supplier[n]. 個人認為應該改為 supplier[i]最后一個for循環(huán), 包含一個循環(huán)控制條件, 原文為: jk. 個人認為應該改為 ji以上純屬個人臆斷, 一切仍以原文為準 )結(jié)點通過調(diào)度算法的計算獲得調(diào)度策略, 把需要從同一個伙伴處獲得哪些分段的信息存儲在一個類似 BM 的位序列中. 之后, 將這個位序列發(fā)送給相應的伙伴. 該伙伴會把位序列中所對應的分段通過一個實時的傳輸協(xié)議發(fā)送給結(jié)點. DONet 并不依賴于某個特定的協(xié)議. 和其他系統(tǒng)一樣, 目前所采用的是 TFRC ( TCPFriendly Rate Control ) 協(xié)議 [31]. BM 信息和調(diào)度策略信息可以隨數(shù)據(jù)一并傳輸. 這樣可以快速更新并且減少額外開銷.源結(jié)點在此始終作為資源提供者. 并且所有的分段都存儲在它的緩存中. 為了防止源結(jié)點過載, 這里給出了一個適應度較高的調(diào)度算法. 如果需要, 它還可以通過對外公布保留的緩存映射來控制負載. 例如, 一個源結(jié)點擁有 M 個伙伴, 那么它可以把傳遞給第 k 個伙伴的 BM 設置為:這就是說, 只有第 ( i mod M ) 個伙伴才會從源結(jié)點處獲得第 i 個分段. 其他的分段則來自別的伙伴. D. 錯誤的恢復和伙伴的篩選在 DONet 網(wǎng)絡中, 一個結(jié)點可以在事先聲明后退出, 或由于崩潰而意外退出. 這兩種情況都可以在TFRC空轉(zhuǎn)一段時間或者BM信息傳遞過程中被檢測出來. 結(jié)點同時離開的概率很小, 受到離開結(jié)點影響的結(jié)點會立即做出反應 根據(jù)剩下伙伴的 BM 信息重構(gòu)調(diào)度策略. 除了這個恢復機制以外, 下面提出的操作也同樣用于增強系統(tǒng)的恢復能力. 聲明后退出: 即將退出的結(jié)點會提交一個退出消息. 這個信息的格式與成員信息一樣, 只是num_partner這一項被設為1.意外退出: 一個結(jié)點的意外退出會被它的伙伴檢測到. 這個伙伴會代替退出的結(jié)點來發(fā)布退出消息. 退出消息的傳遞方式與成員信息的傳遞方式一樣. 如果結(jié)點是意外退出的, 冗余的退出消息也許會被退出結(jié)點的多個伙伴發(fā)布. 但是只有第一個收到的退出消息會被允許繼續(xù)在網(wǎng)絡上傳播, 其他的相同信息傳播則會被抑制. 每個收到消息的結(jié)點會刪除各自 mCache 中對應于退出結(jié)點的記錄.最后, 每個結(jié)點會定期地從它的 mCache 中隨機選擇出結(jié)點并與之建立伙伴關系. 這一操作的目的有兩個: 第一, 它使得每個結(jié)點可以在一些伙伴退出的情況下, 維護一定數(shù)量的伙伴。 第二, 它使得結(jié)點可以尋找到更高質(zhì)量的伙伴. 在實現(xiàn)中, 一個結(jié)點 i 評估它的伙伴結(jié)點 j, 使用函數(shù) max{ si,j, sj,i}. 其中, si,j 表示單位時間內(nèi), 結(jié)點 i 收到來自結(jié)點 j 的分段的平均數(shù)量. 直覺上看, 一個具有更大上傳帶寬和更多可用分段的伙伴會獲得更高的評估分數(shù). 由于一個結(jié)點既可以是資源提供者, 也可以是接收者, 因此需要計算兩個方向上的最大值. 在尋找到新的伙伴后, 為了保持伙伴數(shù)量的穩(wěn)定, 伙伴列表中具有最低分數(shù)的伙伴將會被拋棄. 伙伴的數(shù)量, M , 是一個很重要的設計參數(shù). 它的影響將會在之后的理論分析和實驗中做具體介紹. IV. 網(wǎng)絡半徑的分析 ( 本節(jié)翻譯: 默難 )本節(jié)將會對 DONet 網(wǎng)絡的半徑進行分析. 所謂網(wǎng)絡半徑, 指的是一個分段在傳遞過程中, 從源結(jié)點到所有的目的結(jié)點的平均距離. 和大多數(shù)文獻 [11] , [12], [27] 相同, 距離的單位是經(jīng)過網(wǎng)絡中結(jié)點的跳數(shù). 這在一定程度上反應了端到端的傳輸延遲. 這里用到的分析模型是經(jīng)過簡化的, 結(jié)果顯示網(wǎng)絡半徑與網(wǎng)絡大小之間成對數(shù)關系. 這說明 , DONet 網(wǎng)絡中的端到端延遲是較小的, 足以用來傳輸實時的流媒體.在 DONet 網(wǎng)絡中, 分段可用性信息的傳遞路徑, 可以用一棵廣度優(yōu)先搜索 ( BFS, BreadthFirst Search) 的樹結(jié)構(gòu)來表示. 源結(jié)點是樹的根結(jié)點, 處于第 0 層. 第 k 層的結(jié)點與源結(jié)點之間相隔 k 跳. DONet 的結(jié)點不會維護一個明確的結(jié)構(gòu), 因此, 每個結(jié)點可以在這個 BFS 樹中出現(xiàn)多次.為了描述方便, 把 BFS 樹中的結(jié)點稱為 s結(jié)點 ( snode ). 根據(jù)廣度優(yōu)先搜索的規(guī)則, s結(jié)點按照在搜索時被訪問的順序進行編號. 這樣, 根結(jié)點的編號為 1. 對于編號為 t 的 s結(jié)點, 它所對應的 DONet 結(jié)點被表示為 pt ( 譯者注: 根據(jù)下面(t) 函數(shù)的定義, 此處應為 ). 假設伙伴之間的帶寬大約相等, 并且一個分段到達一個結(jié)點的過程, 是自根結(jié)點出發(fā), 按照廣度優(yōu)先的算法搜索樹結(jié)構(gòu), 直到該結(jié)點第一次出現(xiàn). Fig4 顯示了 Fig2 的 DONet 網(wǎng)絡的 BFS 樹結(jié)構(gòu) ( 只列舉了三個層次).Fig4 一棵廣度優(yōu)先搜索的數(shù). 黑色的結(jié)點表示(t)等于1的結(jié)點. 即第一次出現(xiàn)的結(jié)點. 白色結(jié)點表示(t)等于零的結(jié)點.定義一個輔助函數(shù) (t): 也就是說, 只有在 s結(jié)點 t 第一次在樹結(jié)構(gòu)中出現(xiàn)時, 函數(shù)值才為 1. 由于成員關系和伙伴關系協(xié)議是采用隨機的伙伴選擇方式, 用 N 表示網(wǎng)絡中的結(jié)點數(shù)量, 因此則有:這里, f(t) 表示編號為 1 至 t 的 s結(jié)點中, 包含的 DONet 結(jié)點的數(shù)量. 由此則有: f(t) f(t1) = (t). 對 (1) 式兩遍同時求期望, 則有:由此推導出:因為 f(1) = 1, 根據(jù)等式 (3) 可以推導出:這一關系給出了 DONet 結(jié)點數(shù)目關于 s結(jié)點編號的函數(shù). 令tk表示第 k 層中最后一個 s結(jié)點的編號, 那么 DONet 網(wǎng)絡中其他結(jié)點與源結(jié)點之間的平均距離, 即網(wǎng)絡半徑, 則為:注意到, 當 k 趨近于無窮時, 有: . 對于一個連通的網(wǎng)絡來說, 可得:考慮一種穩(wěn)定的狀態(tài): 每個 DONet 結(jié)點均擁有 M 個伙伴. 那么對應的 BFS 樹中, 除了根結(jié)點擁有 M 棵子樹外, 每個非葉子結(jié)點都擁有 M1 棵子樹. 那么可以導出:將 (6) 式中的連加分解為兩部分: 一部分是從 k = 0 到 k = logM1N。 另一部分是從 k = 1 + log M1N 到正無窮. 那么有:當 M 大于等于 3 時, 有 (M1)k = (M1)k. 則 eM1^k = e(M1)k. 由此導出: 由此, 源結(jié)點到網(wǎng)絡中任意結(jié)點的平均距離則為 O(logN). 從式 (4) 和式 (8) 可以看出, 從源結(jié)點出發(fā), 在 k 跳之內(nèi)可以到達的結(jié)點的比例為. 也就是說, 對于包含 500 個結(jié)點的 DONet 網(wǎng)絡, 設 M = 4, 那么, 大約 95% 的結(jié)點可以在 6 跳之內(nèi)到達.V. 基于全球范圍的性能評估 ( 本節(jié)翻譯: AC由DriftingLeaves翻譯。 D和E由默難翻譯 )關于DONet 的原型, 已經(jīng)進行過多方面實驗. 這一部分中, 將會首先說明在 PlanetLab [30] 環(huán)境下, 實驗系統(tǒng)是如何設計. 其次會列出一些典型的結(jié)果. 最后, 本文會指出在實驗中所遇到的一些典型問題, 并討論它們對實驗結(jié)果的影響. Fig5 結(jié)點地理分布的快照A. 實驗系統(tǒng)的設計這些實驗幾乎動用了 PlanetLab 的所有可用結(jié)點, 而結(jié)點的總量在實驗期間 (2004年5月到2004年6月), 達到了200個到300個. 每一個結(jié)點都運行一個程序原型, 扮演 DONet 結(jié)點的角色. 源結(jié)點被設置在美國 ( , IP : ), 而借助遠程登錄, 通過在香港 ( , IP : ) 的結(jié)點控制整個系統(tǒng), 它也就是所謂的監(jiān)控結(jié)點 ( Monitoring Node ) . 實際上這也是亞洲第一個接入 PlanetLab 的結(jié)點 ( 從2003年1月開始 ). Fig5展示了一個在5月進行的實驗所動用結(jié)點的地理分布快照. 對于這樣一個大范圍分布的實驗臺, 如何有效地控制結(jié)點和收集報告, 將會是一個挑戰(zhàn), 因為無論是啟動或升級程序, 還是收集實驗結(jié)果, 所有的結(jié)點都將會集中地完成登錄, 上傳或下載操作. 所以設計一個自動控制系統(tǒng)是很必要的. 而同時實驗系統(tǒng)應該具有高度的可擴展性, 以便加入新的結(jié)點和性質(zhì). 有趣的是, 借助 PlanetLab 所提供的工具, 以上目的也可以通過使用重疊網(wǎng)絡來達到. 下面將簡要描述實驗系統(tǒng)的模塊, Fig6描述了這一模塊的構(gòu)成. Fig6 實驗系統(tǒng)的模塊結(jié)構(gòu)圖DONet 模塊: DONet 是使用 Python 也就是 Planet 的編程語言, 來實現(xiàn)的. 在這一模塊中, 對于并行事件的處理是采用具有非阻塞模式套接字的事件隊列來完成的, 而不是多線程. 正因為程序是單線程的, 可以避免許多在多線程編程下的復雜問題, 因此程序的調(diào)試和實現(xiàn)會更加簡單, 這也會使得原型的設