适用於P2P档案共享系统

1適用於P2P檔案共享系統傳輸協定之設計政治大學資訊科學系行動計算與網路通訊實驗室Ⅱ指導教授：連耀南研究生：許弘奇2OutlineIntroductionRelatedWorkDesignofProtocolPacketLossRecoverySegmentSizeDeterminationAdaptiveUDPMechanismPerformanceEvaluationConclusion3IntroductionPeer-to-Peer(P2P)架構：P2P架構讓社群內的使用者收集分散在網路各處之資源。參與者可得到原本無法負擔之運算資源。P2P檔案共享系統：最廣為風行的P2P系統，如Napster、BitTorrent。P2P檔案共享系統，參與的角色分別為：資料提供者(DataSourceProvider)。資料下載者(Downloader)。4CentralizedModel&DecentralizedModelP2P檔案共享系統架構分為：集中式，如Napster-likeModel。分散式，如BitTorrent-likeModel。CentralizedModelDecentralizedModel5P2P檔案共享系統之分散式架構又可細分結構化：下載檔案之來源點和網路拓樸位置有關。非結構化：下載檔案之來源點未將網路拓樸納入考量。6BitTorrentBitTorrent之優點：目前最為風行。可擴張性極佳(scalability)。以BitTorrent-likeModel為代表，作為我們的研究對象。7BitTorrent運作時之參與角色檔案提供者(Seeder)檔案下載者(Downloader)Tracker扮演中央控管角色協助下載者尋找所需之檔案片段。網頁伺服器(Webserver)公佈並提供檔案之相關資訊。8BitTorrent特色P2P檔案共享協定。採分散式且非結構化之模式。檔案提供者將檔案切割成多個檔案片段。下載者會開放已完成之檔案片段，供其他下載者抓取。下載檔案時，可從不同之地點下載。同一檔案片段同時有許多地點可供下載。下載者可從不同地點下載同一檔案片段。參與者愈多時，其下載者之下載速度不會大幅降低。9BitTorrent運作機制檔案提供：提供者Seeder利用BitTorrent程式對檔案建立.torrent檔，過程中需指定「Tracker」的URL。檔案公佈：檔案提供者需將.torrent檔公佈至某網頁。.torrent除了TrackerURL位置之外，亦含被下載檔案之檔名、檔案大小、檔案Signature等訊息。10BitTorrent運作機制檔案下載：下載前，先至網頁抓取.torrent檔，用BitTorrent程式開啟此.torrent檔，才可下載檔案。檔案下載時，系統會經由「Tracker」尋找所需之檔案片段。11BitTorrent運作機制BitTorrent運作之檔案基本單位：Piece(Fragment)：檔案片段，大小為1/4Mbytes。Sub-piece(Sub-fragment)：為利用Pipeline方式提昇Piece傳輸速度之單位。大小為16Kbytes。傳輸協定：採用TCP傳輸協定。12TCP的特色傳輸層協定(Transportlayerprotocol)。端對端(end-to-end):一個傳送端，一個接收端。資料傳輸前需建立連線(connection-oriented)。PositiveACK：接收端收到正確資料須回傳ACK。ACK驅動傳送端送出新的封包(self-clocking)。保證資料完整及保持原序(dataintegrity,in-order)。流量控制(flowcontrolled):傳送端之資料速率不超過接收端之接收能力。傳輸速率由擁塞窗框(congestionwindow)所控制。13TCP擁塞控管機制利用WindowSize調節資料傳輸速率。以封包遺失或逾時當作網路擁塞的指標。資料傳輸中若有封包遺失或逾時，TCP就會啟動擁塞控制機制快速降低資料傳輸速率。14TCP擁塞控管機制SlowStart(CWNDThreshold)探測目前網路可承載的頻寬。當connection建立以後，CWND大小以指數的速度成長，直至超過Treshold或封包遺失產生為止。CongestionAvoidance(CWNDThreshold)AIMD(AdditiveIncreaseMultiplicativeDecrease)SlowStarttimeout3duplicateACKsCongestionAvoidance(RTT)threshold15P2P檔案共享系統的效能缺陷經驗中發現，上行頻寬窄、下行頻寬大的非對稱網路(如ADSL)之下，BitTorrent-likeModel之傳輸速度不佳。下載者之下行頻寬大，使用率卻很低。下載者無法完全使用下載頻寬。1001201401601802002468DownlinkBandwidth(Mbps)Time(sec)TCPRenoTCPVegasAdaptiveUDP16P2P檔案共享系統效能問題分析FractionalUpwardBandwidth(FUB)：一檔案片段被多個下載者同時下載。多個上傳訊務流要共用一個狹窄上行頻寬。BlockageofACK(BoA)：TCP協定下，接收端收到資料後，須回傳ACK。BitTorrent中之資料接收者，亦為資料上傳者。狹窄之上行頻寬擁塞，ACK無法順利回傳。ACK在佇列中逾時後，傳送端啟動擁塞控管機制，降低資料傳送速度。17P2P檔案共享系統效能問題分析檔案片段樹(FragmentTree)：以檔案片段Seed為樹根(Root)。上傳者與下載者形成階層架構。18由檔案片段樹觀察到下列結果LongPhysicalPaths：檔案片段樹之一鏈結(link)實際為路徑(path)。下載路徑可能很長，假如未考量路徑長短，便會浪費網路資源。下載路徑之間可能有重疊之處，會浪費網路資源。Lien(2005)提出，如果能盡量縮短路徑、減少重覆，必能降低頻寬之浪費。19LongPhysicalPaths20BushyTreeBushyTree：太多下載者抓取本身下載完成之檔案片段。導致FUB與BoA的問題。Lien(2005)提出可將之改成分支度較小的SlimTree，控制每個參與者分享資料流數目，可減少FUB與BoA的問題。BushyTreeSlimTree21研究目標以上分析有BoA、FUB等問題。因為BoA問題現今尚未有完整之解決方案，本研究之目的，即對BoA效能問題提出可行改進措施。22OutlineIntroductionRelatedWorkDesignofProtocolPacketLossRecoverySegmentSizeDeterminationAdaptiveUDPMechanismPerformanceEvaluationConclusion23RelatedWork非對稱網路下之資料傳輸問題非對稱網路下TCP問題之回顧非對稱網路下TCP問題之解法24非對稱網路下TCP問題之回顧H.BalakrishnanandV.N.Padmanabhan,“HowNetworkAsymmetryAffectTCP,”IEEECommunicationsMagazine,Apr.2001.回顧TCP協定，在非對稱網路下之效能影響並提出解法。對狹窄頻寬進行管理：TCPHeaderCompression、ACKFiltering、ACKCongestionControl、ACKsFirstScheduling等方式ACK頻率低，會破壞Self-clocking，補救措施：ACKReconstruction25非對稱網路下TCP問題之解法WanjiunLiaoandYi-DerLi,ImprovingTCPPerformanceforAsymmetricNetworks,IEEEICC,Helsinki,Finland,Jun.2001.TCPVegas不能分辨在非對稱網路之下，因傳輸方向不同所產生的負面影響，而導致整個效能大為降低。提出一個新的TCPFormosa協定。CumulativeACK的機制減少ACK的數量。避免非對稱網路之下因為ACK遺失所導致的影響。26評論上述之方法皆是直接修改TCP協定。改變TCP茲事體大，協定更改幅度太大，影響層面廣，不易被接受。現有之使用者不易為了解決非對稱網路產生之問題即採用一個新版的TCP協定。27OutlineIntroductionRelatedWorkDesignofProtocolPacketLossRecoverySegmentSizeDeterminationAdaptiveUDPMechanismPerformanceEvaluationConclusion28解決BoA問題的方法方案一：增加TCPACKTimeout時間。導致TCP對真正網路擁塞之反應時間拉長。不能即時處理網路擁塞。方案二：TCP之接受端重覆傳送ACK。增加ACK存活率，但會在非對稱網路狹窄的上行端增加ACK訊務量。此法對TCP更改幅度太大。方案三：以UDP為基礎的方式(UDP-BasedApproach)解決。29我們採用UDP的方法使用UDP傳送資料，不必對接收到的封包回送ACK，可避免BoA問題。UDP協定有兩個問題：無法確保資料的完整性。無法自動決定資料傳送速率。在應用層(ApplicationLayer)加上相關機制解決。30我們提出的協定之特色此協定以UDP協定為基礎，並加入下列機制：確保資料完整性之機制。自動決定資料傳送速率之機制。此協定之採用者：BitTorrent架構下之參與者。傳送端與接收端(sender&receiver)皆需採用。31我們提出的協定之特色本協定必須考慮下列的問題：避免因封包錯誤導致之重傳。提供自動重建遺失之封包。計算基本傳輸單位之大小。量測最適可用頻寬，決定傳送速率。3233效能目標儘量降低重傳次數。儘量利用可利用之網路頻寬，提高每個下載者的下載速度。34提昇效能之設計PacketLossRecovery(自動重建遺失之封包)：避免封包遺失而重傳。SegmentSizeDetermination(基本傳送單位之計算)：計算檔案片段中，最佳的基本傳輸單位大小要保護封包，亦要降低overhead。AdaptiveUDPMechanism(調節式UDP機制)：應用層加上自動調整傳輸速率機制。35FragmentStructure36PacketLossRecovery每n個封包為一群，加一個同位封包(ParityPacket)，稱為Segment。同位封包：Segment之資料封包經由同位計算後所產生。37PacketLossRecovery同位封包之功用：Segment任一封包遺失，可用同位封包救回。Segment中若有兩個以上封包遺失，同位封包將無法彌補，則資料必須重傳。重傳之單位：以Fragment為單位，重傳時須負擔較高的重傳成本。以Segment為單位，減輕重傳之成本。38PacketLossRecovery示意圖39PacketLossRecoveryIssueSegment長短影響協定之效能：Segment較短時，錯誤更正能力較強，但Overhead較大。Segment較長時，錯誤更正能力較弱，但Overhead較小。40SegmentSizeDetermination因Segment長短會影響協定效能。設計一計算最佳Segment大小之法。其中，每一