适用於P2P档案共享系统.ppt

1 適用於P2P檔案共享系統傳輸協定之設計 政治大學資訊科學系行動計算與網路通訊實驗室 指導教授 連耀南研究生 許弘奇 2 Outline IntroductionRelatedWorkDesignofProtocolPacketLossRecoverySegmentSizeDeterminationAdaptiveUDPMechanismPerformanceEvaluationConclusion 3 Introduction Peer to Peer P2P 架構 P2P架構讓社群內的使用者收集分散在網路各處之資源 參與者可得到原本無法負擔之運算資源 P2P檔案共享系統 最廣為風行的P2P系統 如Napster BitTorrent P2P檔案共享系統 參與的角色分別為 資料提供者 DataSourceProvider 資料下載者 Downloader 4 CentralizedModel DecentralizedModel P2P檔案共享系統架構分為 集中式 如Napster likeModel 分散式 如BitTorrent likeModel CentralizedModel DecentralizedModel 5 P2P檔案共享系統之分散式架構又可細分 結構化 下載檔案之來源點和網路拓樸位置有關 非結構化 下載檔案之來源點未將網路拓樸納入考量 6 BitTorrent BitTorrent之優點 目前最為風行 可擴張性極佳 scalability 以BitTorrent likeModel為代表 作為我們的研究對象 7 BitTorrent運作時之參與角色 檔案提供者 Seeder 檔案下載者 Downloader Tracker扮演中央控管角色協助下載者尋找所需之檔案片段 網頁伺服器 Webserver 公佈並提供檔案之相關資訊 8 BitTorrent特色 P2P檔案共享協定 採分散式且非結構化之模式 檔案提供者將檔案切割成多個檔案片段 下載者會開放已完成之檔案片段 供其他下載者抓取 下載檔案時 可從不同之地點下載 同一檔案片段同時有許多地點可供下載 下載者可從不同地點下載同一檔案片段 參與者愈多時 其下載者之下載速度不會大幅降低 9 BitTorrent運作機制 檔案提供 提供者Seeder利用BitTorrent程式對檔案建立 torrent檔 過程中需指定 Tracker 的URL 檔案公佈 檔案提供者需將 torrent檔公佈至某網頁 torrent除了TrackerURL位置之外 亦含被下載檔案之檔名 檔案大小 檔案Signature等訊息 10 BitTorrent運作機制 檔案下載 下載前 先至網頁抓取 torrent檔 用BitTorrent程式開啟此 torrent檔 才可下載檔案 檔案下載時 系統會經由 Tracker 尋找所需之檔案片段 11 BitTorrent運作機制 BitTorrent運作之檔案基本單位 Piece Fragment 檔案片段 大小為1 4Mbytes Sub piece Sub fragment 為利用Pipeline方式提昇Piece傳輸速度之單位 大小為16Kbytes 傳輸協定 採用TCP傳輸協定 12 TCP的特色 傳輸層協定 Transportlayerprotocol 端對端 end to end 一個傳送端 一個接收端 資料傳輸前需建立連線 connection oriented PositiveACK 接收端收到正確資料須回傳ACK ACK驅動傳送端送出新的封包 self clocking 保證資料完整及保持原序 dataintegrity in order 流量控制 flowcontrolled 傳送端之資料速率不超過接收端之接收能力 傳輸速率由擁塞窗框 congestionwindow 所控制 13 TCP擁塞控管機制 利用WindowSize調節資料傳輸速率 以封包遺失或逾時當作網路擁塞的指標 資料傳輸中若有封包遺失或逾時 TCP就會啟動擁塞控制機制快速降低資料傳輸速率 14 TCP擁塞控管機制 SlowStart CWNDThreshold AIMD AdditiveIncreaseMultiplicativeDecrease 15 P2P檔案共享系統的效能缺陷 經驗中發現 上行頻寬窄 下行頻寬大的非對稱網路 如ADSL 之下 BitTorrent likeModel之傳輸速度不佳 下載者之下行頻寬大 使用率卻很低 下載者無法完全使用下載頻寬 16 P2P檔案共享系統效能問題分析 FractionalUpwardBandwidth FUB 一檔案片段被多個下載者同時下載 多個上傳訊務流要共用一個狹窄上行頻寬 BlockageofACK BoA TCP協定下 接收端收到資料後 須回傳ACK BitTorrent中之資料接收者 亦為資料上傳者 狹窄之上行頻寬擁塞 ACK無法順利回傳 ACK在佇列中逾時後 傳送端啟動擁塞控管機制 降低資料傳送速度 17 P2P檔案共享系統效能問題分析 檔案片段樹 FragmentTree 以檔案片段Seed為樹根 Root 上傳者與下載者形成階層架構 18 由檔案片段樹觀察到下列結果 LongPhysicalPaths 檔案片段樹之一鏈結 link 實際為路徑 path 下載路徑可能很長 假如未考量路徑長短 便會浪費網路資源 下載路徑之間可能有重疊之處 會浪費網路資源 Lien 2005 提出 如果能盡量縮短路徑 減少重覆 必能降低頻寬之浪費 19 LongPhysicalPaths 20 BushyTree BushyTree 太多下載者抓取本身下載完成之檔案片段 導致FUB與BoA的問題 Lien 2005 提出可將之改成分支度較小的SlimTree 控制每個參與者分享資料流數目 可減少FUB與BoA的問題 BushyTree SlimTree 21 研究目標 以上分析有BoA FUB等問題 因為BoA問題現今尚未有完整之解決方案 本研究之目的 即對BoA效能問題提出可行改進措施 22 Outline IntroductionRelatedWorkDesignofProtocolPacketLossRecoverySegmentSizeDeterminationAdaptiveUDPMechanismPerformanceEvaluationConclusion 23 RelatedWork 非對稱網路下之資料傳輸問題非對稱網路下TCP問題之回顧非對稱網路下TCP問題之解法 24 非對稱網路下TCP問題之回顧 H BalakrishnanandV N Padmanabhan HowNetworkAsymmetryAffectTCP IEEECommunicationsMagazine Apr 2001 回顧TCP協定 在非對稱網路下之效能影響並提出解法 對狹窄頻寬進行管理 TCPHeaderCompression ACKFiltering ACKCongestionControl ACKsFirstScheduling等方式ACK頻率低 會破壞Self clocking 補救措施 ACKReconstruction 25 非對稱網路下TCP問題之解法 WanjiunLiaoandYi DerLi ImprovingTCPPerformanceforAsymmetricNetworks IEEEICC Helsinki Finland Jun 2001 TCPVegas不能分辨在非對稱網路之下 因傳輸方向不同所產生的負面影響 而導致整個效能大為降低 提出一個新的TCPFormosa協定 CumulativeACK的機制減少ACK的數量 避免非對稱網路之下因為ACK遺失所導致的影響 26 評論 上述之方法皆是直接修改TCP協定 改變TCP茲事體大 協定更改幅度太大 影響層面廣 不易被接受 現有之使用者不易為了解決非對稱網路產生之問題即採用一個新版的TCP協定 27 Outline IntroductionRelatedWorkDesignofProtocolPacketLossRecoverySegmentSizeDeterminationAdaptiveUDPMechanismPerformanceEvaluationConclusion 28 解決BoA問題的方法 方案一 增加TCPACKTimeout時間 導致TCP對真正網路擁塞之反應時間拉長 不能即時處理網路擁塞 方案二 TCP之接受端重覆傳送ACK 增加ACK存活率 但會在非對稱網路狹窄的上行端增加ACK訊務量 此法對TCP更改幅度太大 方案三 以UDP為基礎的方式 UDP BasedApproach 解決 29 我們採用UDP的方法 使用UDP傳送資料 不必對接收到的封包回送ACK 可避免BoA問題 UDP協定有兩個問題 無法確保資料的完整性 無法自動決定資料傳送速率 在應用層 ApplicationLayer 加上相關機制解決 30 我們提出的協定之特色 此協定以UDP協定為基礎 並加入下列機制 確保資料完整性之機制 自動決定資料傳送速率之機制 此協定之採用者 BitTorrent架構下之參與者 傳送端與接收端 sender receiver 皆需採用 31 我們提出的協定之特色 本協定必須考慮下列的問題 避免因封包錯誤導致之重傳 提供自動重建遺失之封包 計算基本傳輸單位之大小 量測最適可用頻寬 決定傳送速率 32 33 效能目標 儘量降低重傳次數 儘量利用可利用之網路頻寬 提高每個下載者的下載速度 34 提昇效能之設計 PacketLossRecovery 自動重建遺失之封包 避免封包遺失而重傳 SegmentSizeDetermination 基本傳送單位之計算 計算檔案片段中 最佳的基本傳輸單位大小要保護封包 亦要降低overhead AdaptiveUDPMechanism 調節式UDP機制 應用層加上自動調整傳輸速率機制 35 FragmentStructure 36 PacketLossRecovery 每n個封包為一群 加一個同位封包 ParityPacket 稱為Segment 同位封包 Segment之資料封包經由同位計算後所產生 37 PacketLossRecovery 同位封包之功用 Segment任一封包遺失 可用同位封包救回 Segment中若有兩個以上封包遺失 同位封包將無法彌補 則資料必須重傳 重傳之單位 以Fragment為單位 重傳時須負擔較高的重傳成本 以Segment為單位 減輕重傳之成本 38 PacketLossRecovery示意圖 39 PacketLossRecoveryIssue Segment長短影響協定之效能 Segment較短時 錯誤更正能力較強 但Overhead較大 Segment較長時 錯誤更正能力較弱 但Overhead較小 40 SegmentSizeDetermination 因Segment長短會影響協定效能 設計一計算最佳Segment大小之法 其中 每一封包之封包遺失率皆同為 41 SegmentSizeDetermination 一個Fragment可分為Segment 一個Segment中 x個封包遺失的機率 一個Segment傳送成功的機率 反之 一個Segment傳送失敗之機率為 42 SegmentSizeDetermination 額外成本一個Segment中需增加一個同位封包 成本為當一個Segment傳送失敗時 仍要再重傳一次 其重傳成本為懲罰函數 PenaltyFunction 簡化 43 SegmentSizeDetermination 當懲罰函數最小時 可得最佳Segment封包數 給定一 值即解得一個n值 44 AdaptiveUDPMechanism UDP協定沒有調整傳送速率之機制 必須在應用層加入自動調整速率之機制 影響資料傳送速率之決定因素 瓶頸鏈結之頻寬 傳送端如何獲得瓶頸鏈結之可用頻寬 如在傳送者上行端假設使用者已知上行端之實際可用頻寬 如在核心網路內部需利用探測封包 ProbingPacket 的方式 幫助瞭解網路內部瓶頸頻寬 bottleneckbandwidth 的狀況 45 UDPwithProbingPackets 傳送端定期發送探測封包量測網路狀態 根據其變化來調整合理傳送速率 接收端在ACK裡加入此項資訊 傳送端使用此資訊來調整合理傳送速率 目標 降低頻寬浪費或網路擁塞之機率 46 PacketDispersion C Dovroliset al Packet DispersionTechniquesandaCapacity EstimationMethodology IEEE ACMTransactionsOnNetworking VOL 12 No 6 Dec2004 緊鄰兩個封包通過瓶頸鏈結時 其封包距離有散開 Dispersion 之現象 此散開可當做瓶頸可用頻寬之估計依據 此法稱為PacketDispersion法 利用此PacketDispersion估計目前網路內部瓶頸的頻寬 47 AdjustingCoefficient 為避免估計偏差 bias 對協定造成負面影響 以一校正係數 AdjustingCoefficient 修正估計結果 我們所測得之可用頻寬為調整資料傳送速度之一參考指標 其調整方式 可參考Yung PingChungandYao NanLien DesignofTCPCongestionControlTechniquesbyRouter assistedApproach Sep 2005 48 Outline IntroductionRelatedWorkDesignofProtocolPacketLossRecoverySegmentSizeDeterminationAdaptiveUDPMechanismPerformanceEvaluationConclusion 49 參數估算與效能評估 模擬工具 模擬環境為Cygwin下之ns2 28版 參數估算 計算最佳Segment數 用實驗估算調節式UDP機制之校正參數 值 效能評估 UDP BasedApproach與其他傳輸協定之效能比較 50 SegmentSize計算 實驗目標 給定特定的網路環境 將懲罰函數 PenaltyFunction 最小化以找出最佳SegmentSize 51 SegmentSize計算結果 0 005 0 01 0 015 0 02 52 SegmentSize計算之敏感度分析 不同網路封包遺失率下 求得SegmentSize變化情形 封包遺失率很低時 不太會發生封包遺失 求得的SegmentSize比較大 封包遺失率提高時 封包遺失就容易發生 求得的SegmentSize就較小 53 AdaptiveUDPMechanism 值參數估算 實驗目標 利用Packet Dispersion估計可用頻寬 利用實驗找出適當之校正參數 值供他人參考 54 AdaptiveUDPMechanism 值參數估算實驗設計 魚骨狀之網路架構 中介鏈結上有中介訊務流經其中 調整此魚骨拓樸之長度 並且控制實際可用頻寬之下 求取參考用之 值 55 AdaptiveUDPMechanism 值參數估算實驗參數 56 值參數估算之實驗結果 中介鏈結數 1 此例計算得到之 0 897 57 值參數估算之實驗結果 中介鏈結數 3 此例計算得到之 0 962 58 值參數估算之實驗結果 中介鏈結數 5 此例計算得到之 0 944 59 值參數估算之實驗結果 中介鏈結數 7 此例計算得到之 0 958 60 值參數估算之實驗結果 中介鏈結數 9 此例計算得到之 0 885 61 中介鏈結數之變化與校正參數 之間的關係 中介鏈結數變化與校正參數 之間的關係 發現 值之變化相當平穩 中介鏈結數之大小對 值的影響不大 得到最後估計之 值為0 93 62 UDP BasedApproach與其他傳輸協定之效能比較 實驗目標 設計一個網路上發生FUB與BoA之網路場景 各種不同的傳輸協定進行效能分析與比較 實驗設計 UDP BasedApproach為實驗組 TCP Reno TCP Vegas為對照組 核心網路 CoreNetwork 中有充沛頻寬 雙向有1Gbps頻寬 接取網路為非對稱網路 63 UDP BasedApproach與其他傳輸協定效能比較之網路拓樸 核心網路上有R1 R2兩個路由器 Router 非對稱鏈結所接取的的機器有X1 X5及Y1共六台 X1 X5同時會至Y1下載資料 Y1亦有5個Session同時至X1 X5下載資料 在Y1至R2的上行鏈結會發生FUB與BoA的問題 64 UDP BasedApproach與其他傳輸協定效能比較之實驗參數 65 傳輸協定效能比較之實驗結果 上行64Kbps 下行2Mbps 0 TCPReno每個Session平均 164 8秒 LostACK 41 TCPVegas每個Session平均 188秒 LostACK 0 AdaptiveUDP每個Session平均 110 7秒 重傳次數 0 66 傳輸協定效能比較之實驗結果 上行64Kbps 下行2Mbps 0 001 TCPReno每個Session平均 201 5秒 LostACK 66 TCPVegas每個Session平均 187 8秒 LostACK 0 AdaptiveUDP每個Session平均 112秒 重傳次數 0 67 傳輸協定效能比較之實驗結果 上行64Kbps 下行2Mbps 0 005 TCPReno每個Session平均 150 1秒 LostACK 39 TCPVegas每個Session平均 159 2秒 LostACK 0 AdaptiveUDP每個Session平均 115秒 重傳次數 4 68 傳輸協定效能比較之實驗結果 上行64Kbps 下行2Mbps 0 01 TCPReno每個Session平均 150 2秒 LostACK 34 TCPVegas每個Session平均 164秒 LostACK 0 AdaptiveUDP每個Session平均 119 6秒 重傳次數 15 69 傳輸協定效能比較之實驗結果 上行64Kbps 下行2Mbps 0 05 TCPReno每個Session平均 208 7秒 LostACK 1 TCPVegas每個Session平均 196秒 LostACK 0 AdaptiveUDP每個Session平均 131 3秒 重傳次數 311 70 傳輸協定效能比較之實驗結果 上行64Kbps 下行2Mbps 0 1 TCPReno每個Session平均 231 7秒 LostACK 0 TCPVegas每個Session平均 213 1秒 LostACK 0 AdaptiveUDP每個Session平均 150 2秒 重傳次數 480 71 傳輸協定效能比較之實驗結果 上行64Kbps 下行4Mbps 0 TCPReno每個Session平均 174 4秒 LostACK 40 TCPVegas每個Session平均 188秒 LostACK 0 AdaptiveUDP每個Session平均 110 7秒 重傳次數 0 72 傳輸協定效能比較之實驗結果 上行64Kbps 下行4Mbps 0 001 TCPReno每個Session平均 151 1秒 LostACK 39 TCPVegas每個Session平均 187 8秒 LostACK 0 AdaptiveUDP每個Session平均 112秒 重傳次數 0 73 傳輸協定效能比較之實驗結果 上行64Kbps 下行4Mbps 0 005 TCPReno每個Session平均 143 3秒 LostACK 45 TCPVegas每個Session平均 148秒 LostACK 0 AdaptiveUDP每個Session平均 115秒 重傳次數 4 74 傳輸協定效能比較之實驗結果 上行64Kbps 下行4Mbps 0 01 TCPReno每個Session平均 142 9秒 LostACK 24 TCPVegas每個Session平均 164秒 LostACK 0 AdaptiveUDP每個Session平均 119 6秒 重傳次數 15 75 傳輸協定效能比較之實驗結果 上行64Kbps 下行4Mbps 0 05 TCPReno每個Session平均 201 5秒 LostACK 1 TCPVegas每個Session平均 196秒 LostACK 0 AdaptiveUDP每個Session平均 131 3秒 重傳次數 311 76 傳輸協定效能比較之實驗結果 上行64Kbps 下行4Mbps 0 1 TCPReno每個Session平均 222 2秒 LostACK 0 TCPVegas每個Session平均 222 1秒 LostACK 0 AdaptiveUDP每個Session平均 150 2秒 重傳次數 480 77 傳輸協定效能比較之實驗結果 上行64Kbps 下行6Mbps 0 TCPReno每個Session平均 177 9秒 LostACK 40 TCPVegas每個Session平均 188秒 LostACK 0 AdaptiveUDP每個Session平均 110 7秒 重傳次數 0 78 傳輸協定效能比較之實驗結果 上行64Kbps 下行6Mbps 0 001 TCPReno每個Session平均 166 9秒 LostACK 39 TCPVegas每個Session平均 187 8秒 LostACK 0 AdaptiveUDP每個Session平均 112秒 重傳次數 0 79 傳輸協定效能比較之實驗結果 上行64Kbps 下行6Mbps 0 005 TCPReno每個Session平均 148 5秒 LostACK 43 TCPVegas每個Session平均 148秒 LostACK 0 AdaptiveUDP每個Session平均 115秒 重傳次數 4 80 傳輸協定效能比較之實驗結果 上行64Kbps 下行6Mbps 0 01 TCPReno每個Session平均 141 2秒 LostACK 24 TCPVegas每個Session平均 164秒 LostACK 0 AdaptiveUDP每個Session平均 119 6秒 重傳次數 15 81 傳輸協定效能比較之實驗結果 上行64Kbps 下行6Mbps 0 05 TCPReno每個Session平均 201 5秒 LostACK 1 TCPVegas每個Session平均 192 3秒 LostACK 0 AdaptiveUDP每個Session平均 131 3秒 重傳次數 311 82 傳輸協定效能比較之實驗結果 上行64Kbps 下行6Mbps 0 1 TCPReno每個Session平均 211 5秒 LostACK 0 TCPVegas每個Session平均 197 4秒 LostACK 0 AdaptiveUDP每個Session平均 150 2秒 重傳次數 480 83 傳輸協定效能比較之實驗結果 上行64Kbps 下行8Mbps 0 TCPReno每個Session平均 158 5秒 LostACK 41 TCPVegas每個Session平均 188秒 LostACK 0 AdaptiveUDP每個Session平均 110 7秒 重傳次數 0 84 傳輸協定效能比較之實驗結果 上行64Kbps 下行8Mbps 0 001 TCPReno每個Session平均 171 3秒 LostACK 56 TCPVegas每個Session平均 187 8秒 LostACK 0 AdaptiveUDP每個Session平均 112秒 重傳次數 0 85 傳輸協定效能比較之實驗結果 上行64Kbps 下行8Mbps 0 005 TCPReno每個Session平均 149 3秒 LostACK 46 TCPVegas每個Session平均 148秒 LostACK 0 AdaptiveUDP每個Session平均 115秒 重傳次數 4 86 傳輸協定效能比較之實驗結果 上行64Kbps 下行8Mbps 0 01 TCPReno每個Session平均 138 1秒 LostACK 23 TCPVegas每個Sessio