文 / 熊貓直播基礎研發部
IP組網
一. 組網背景-IP組網是什麼，有什麼意義?
商業背景
本項目為熊貓直播平台服務，衆所周知，網絡直播近年非常火熱，同一個直播間可能有上萬人在觀看，産生的流量是相當可觀的，并且會占用相當高的網絡帶寬，由此産生的直播流資料費用将是很大一筆數目。而CDN級的p2p網絡尚不能完全滿足節省流量的需求，為此我們從節省帶寬的目的出發提出了熊貓直播自建P2P網絡的想法，并計劃了長期的執行方案。
P2P網絡介紹
P2P即peer-to-peer,peer指“夥伴”,P2P即“夥伴對夥伴”。而P2P網絡即可以了解為對等網絡.在這樣的網絡中，每個網絡節點同時作為用戶端和伺服器端。沒有中心伺服器，沒有中心路由器。它的一個重要目标是讓所有的用戶端都能提供資源，包括帶寬，存儲和計算能力。具體的網絡拓撲結構可以分為集中式，分布式，混合式以及結構化P2P網絡，是以P2P網絡常被用于分布式科學計算，如著名的SETI@home項目，檔案共享如BitTorrent,以及流媒體直播等等。
集中式P2P網絡
分布式P2P網絡
混合式P2P網絡
IP組網介紹
在整個基于資料分享為目的的P2P網絡中，每個節點會與多個相鄰節點建立連接配接并進行資料交換，對于網絡直播而言，即分享共同觀看的直播資料片段。這裡的核心問題在于如何組網才能使得該p2p網絡的分享率可以達到最大，我們的做法是從IP層面組建P2P網絡，而這實際上是一個規劃問題。
- 圖論基礎
圖論中的圖是由若幹給定的點及連接配接兩點的線所構成的圖形，這種圖形通常用來描述某些事物之間的某種特定關系，用點代表事物，用連接配接兩點的線表示相應兩個事物間具有這種關系。圖分為有向圖和無向圖。
圖的數學表示：G（V，E），其中V是頂點集：V={Vi,i=1...n} ; E是邊集：E={Ei,i=1...n}
頂點的度： 一個頂點的度在無向圖中是指與該頂點相連的邊的個數。有向圖的頂點的度還可以細分為入度和出度，入度是以該頂點為 頭（head） 的邊的條數，出度是以該頂點為尾（tail） 的邊的條數。如下圖無向圖中2号節點的度為4，有向圖中2号節點的出度為1，入度為3。 無向圖
- 應用
我們從整個使用者網絡角度出發，假設使用者網絡圖為G(V,E)，V是頂點集合，E是邊的集合，每條邊上有權重weight，這裡的weight可以用網絡延遲來概括，即每個IP到其他IP的rtt值的大小，采用rtt來表征連通性是因為網絡延遲可以比較直覺且準确的反映兩個IP之間的網絡狀況。在這張全局的使用者網絡圖的基礎上，我們可以為每一路直播流下的使用者P2P組網提供資料支援。
是以核心問題可以抽象的表示為：在以每一路流為目标組建P2P網絡時，可以将該P2P網絡圖抽象為g(V,E),網絡g(V,E)中新加入一個共享節點node後，如何選擇節點與node建立連接配接使新的P2P網絡g'(V,E)保證最大的共享率。 為了保證網絡的穩定性，我們規定每個節點的度數即共享IP數不應該超過20(當然這裡的20是粗略估計，具體數目得根據網絡狀況動态設定。)在這樣的前提下參考使用者網絡G(V,E),找出至多20個與node連通性好(rtt小)的目标節點(這裡需要保證目标節點也在該路流下且度數加一後不會超過20),與node進行p2p組網。這樣我們便實作了在保證整個P2P網絡穩定性的前提下使得每個節點的共享率最大，也就實作了全局的共享率最大化。
二. 基本觀點-目前業界在P2P共享網絡上的做法以及我們的嘗試?
典型應用案例及觀點
- 在以資料共享為目的的P2P網絡中，典型的做法有P2P檔案分發，如BitTorrent,每個節點向其他相鄰節點擷取不同的資料片段，最後組合成一個完整檔案，實作靜态檔案共享的目的。這種做法對于固定且規模較大的檔案共享有比較好的效果，但對于網絡直播的流資料來說則不太适用。
- 在流媒體領域，典型的案例有P2P+CDN（簡稱PCDN）的解決方案，CDN主要用于可靠的Web和流媒體内容分發,而P2P則主要用于内容交換。二者結合的核心思想是在CDN網絡的邊緣節點上引入P2P自治域，在域内利用P2P技術實作資源共享，自治域之間不發生流量交換。這樣可以大大降低邊緣伺服器的壓力，提高了網絡的穩定性和檔案傳輸的效率。PCDN的做法雖然在CDN層面改善了網絡，但在使用者層面，每個用戶端還是分别向同一個CDN拉取相同的資料，在流媒體應用上也就是同一路視訊流。這也就是PCDN做法的瓶頸所在。
- 我們的嘗試即是從使用者層面出發，自建P2P網絡，這也就意味着即使是邊緣CDN，也不用頻繁分發同一路直播流，使得整個網絡近似于完全的P2P網絡，而這，将大大改善網絡傳輸環境，提高整個網絡的資料共享率。
- 為了達到這個目标，我們引入了使用者層面的IP組網。對此，需要解決的難題有很多，這些困難可以集中表達為使用者網絡的複雜性以及網絡資料規模，在CDN層面，實際上有一個清晰的P2P組網架構，在使用者層面，我們要做的也是掌握使用者的網絡狀況。
正如上面所介紹的，IP組網前提是擁有一張全局的使用者網絡圖G(V,E)，每條邊以rtt作為權重，這裡的網絡圖實際上接近于一張全連通圖，就是說每個節點與其他節點都應該存在一條邊，而我們的收集上來的記錄實際上并不足以構成這樣一張全聯通圖，并且邊的權重也不是最佳權重，是以得在已有的圖的基礎上通過圖的最短路徑算法來計算出每個節點到其他節點的rtt值，以此為p2p組網做鋪墊。
在已有的基于圖算法的使用者網絡圖基礎上，我們為每一個節點提供組網時的可用節點，通過查詢包含該節點的最短連接配接，找出與它最“近”的某幾個節點作為候選節點來建立p2p連接配接，進而達到最優化組網的目的。
三. 實踐過程
資料擷取過程:如何擷取網絡拓撲結構 ?
- 網絡原理 - Traceroute介紹
traceroute(Windows系統下是tracert)指令可以周遊資料包傳輸路徑上的所有路由器，從源主機使用traceroute 目标主機的指令，即可依次列印出所有經過的路由器以及相應的rtt值。在網絡原理上主要利用IP資料包的TTL字段值和ICMP協定來實作，在此不作展開，我們的工具即是基于該指令收集使用者網絡的路徑資訊，并作相應的格式處理。
- 具體實作 - SDK的使用
目前資料采集主要在安卓用戶端進行，實際采集中使用到了網易的一個開源SDK，這裡貼出該工具的Github 網址：
https://github.com/Lede-Inc/LDNetDiagnoService_Android該工具使用到了上述的traceroute的網絡原理，對指定域名進行網絡診斷，并收集診斷日志，其中用到了開源網絡檢測庫iputils進行ICMP封包模拟。
資料分析過程:如何還原營運商網絡聯通圖 ?
- 資料特點
在具體實踐過程中我們是通過使用者用戶端SIP來tracert我們的伺服器目标DIP進而探測整個網絡的分布狀況，根據收集上來的資料來看，我們的資料分布範圍非常廣泛，涵蓋了國内的絕大部分地區，以及國外的部分網絡。下面列出了用戶端IP的分布狀況，目标伺服器IP的分布狀況，以及總體的全國網絡IP分布狀況。
用戶端IP分布狀況
伺服器目标IP分布狀況
使用者網絡IP分布狀況
從以上的分布圖可以看出我們的目标伺服器IP則更為分散，這樣有利于采集到更廣大範圍的資料，而最終我們的用戶端IP和整個網絡的IP覆寫到了絕大部分省市，主要分布在東部，并集中在一些規模較大的城市，這也符合我們國家的網絡狀況，在資料上有足夠的可信度，為之後的分析提供了保障。
- 共享IP訂立規則
速度：作為共享的IP組來說，首先得保證IP之間的資料傳輸速度要夠快，這一點可以由rtt(延遲)，hop_cnt(跳數)來衡量，即我們希望的是延遲低，跳數少的IP之間互傳資料，建立組網。
頻度：頻度是指一對IP連接配接在記錄上表現的數量，即是說從我們收集上來的資料來看，如果一對IP之間頻繁出現通信或者資料傳輸，那麼這一對IP将是整個網絡的重要連接配接(橋梁)，在進行IP組網的時候就需要優先将這一對IP作為相鄰節點互傳資料
穩定性：基于以上兩個因素，在IP組網的過程中還需要保證網絡連接配接的穩定性，即保證網絡延遲的波動不會過大，這一層面可以由rtt來表征，rtt波動大則說明網絡穩定性比較差，rtt波動小則說明網絡穩定性高，适合作為相鄰節點進行組網。
其他因素：除了以上幾點之外，其他的因素也可以作為參考條件考慮，比如說組網的一對IP是否屬于同一網段，是否屬于同一自治域，是否屬于同一營運商，在此基礎之上，需要讨論同一網段，自治域，營運商内的IP之間的連通性是否比不同網段，自治域，營運商之間更好。
在實踐過程中，以上因素不一定均會考慮到，上面也說了，目前我們用速度即rtt這一因素就可以表示出各個IP對之間的連通性好壞，也就是說整張使用者網絡圖G(V,E)是建立在網絡延遲這一重要屬性上的。
資料格式與規模
在資料處理過程中，我們将一個tracert指令傳回的路徑資訊進行拆分，可以得到格式化的每一段記錄的資訊:路徑源IP—路徑終IP—該跳起始IP—該跳終點IP—該跳起始ASN—該跳終點ASN—跳數，通過這些處理過的格式化資訊，可以為接下來的分析做鋪墊。截至到目前，這樣的格式化資料一共收集了20億條，平均每天可以收集上來大約4千萬條資料。
資料分析過程
傳輸速度：通過對各個單獨的IP對計算rtt和hop_cnt的綜合值(這裡取中位數)，可以得到每個IP與其他有連接配接的IP之間傳輸的延遲和跳數的綜合值，作為傳輸速度的表征。例如：
傳輸頻度：通過對各個單獨的IP對計算存在的記錄數，包括總記錄數，以及每天的單獨記錄數，就可以大緻模拟出二者之間互傳資料的頻度，也就可以表征出二者之間的連接配接作為網絡拓撲中的橋梁作用。例如：
穩定性：對于每一組IP對，我們以rtt為對象，研究網絡延遲的穩定性，并以标準差作為衡量标準，因為整個網絡環境處于不穩定狀态，傳輸的延遲也會随之發生必然的波動，是以我們在組網的過程中也就需要規避不穩定的網絡狀況，盡量選擇穩定的連接配接作為資料共享的peers，以此提高整個P2P網絡的共享穩定性。例如：
以上資料是建立在已有記錄的基礎上的，即沒有考慮到節點間最短路徑的計算結果，在計算節點最短路徑的過程中，我們采用了floyd全圖最短路徑算法，但是會面臨兩個問題，即時間複雜度和空間複雜度，該算法的時間複雜度為O(n^3),空間複雜度為O(n^2),是相當高的，随着資料規模的擴大，計算所用的時間會不斷增加，目前來看4000左右的節點規模所用時間為7到8小時，而IP節點的數目要遠高于該規模，是以計算時間上是無法容忍的。在空間複雜度上，由于該算法是全圖最短路徑算法，是以會不斷更新得到的最短路徑圖，并得到最終的全連通圖G(V,E)，所需要的計算資源，存儲資源是相當高的，對于性能的調優是個不小的挑戰。
即是說，我們的瓶頸即在于該算法的瓶頸，而對算法進行改進或者尋找更好的大資料圖算法是需要一定時間的，這就需要考慮到時間成本問題。
四. 總結
通過以上的研究以及實踐過程，我們可以得出以下的結論以及觀點。
- IP組網對于建立一個可以在使用者級别共享資料的P2P網絡是理論上可行的，并且有确切的資料支撐，可以做到相當精确的程度，也就是說使用IP組網來實作P2P網絡可以最大化該P2P網絡的共享率以及網絡穩定性，從這個角度來說，IP組網應當是最佳的選擇。
- 相對的，使用IP級别的組網，必然會帶來很多問題，從資料分析角度來看，由于資料規模過大，我們在分析的過程中會面臨相當大的複雜度，具體展現在圖算法的瓶頸，帶來時間和空間上的巨大開銷，而改進現有算法或選用更好的算法則需要更多的時間成本來嘗試和比較。
- 另外，從網絡的動态變化來看，其實越往細處，網絡的不确定性越高，即是說，在IP層面，我們很難把握到精确的狀态，比如說移動資料網絡的IP位址實際上是動态配置設定的，區域網路傳回的IP可能還包含諸如192.168.0.1這種保留IP。而這種資料對于圖算法的計算會帶來很大的誤差，很多時候并不能反映真實的網絡狀況。為此我們需要更高次元的網絡研究，比如網段級别，網絡自治域級别，能夠從更加宏觀的角度反映真實的網絡狀況，而且在需要計算的資料規模上也是可以把控的。
————————————————
版權聲明：本文為CSDN部落客「LiveVideoStack_」的原創文章，遵循CC 4.0 BY-SA版權協定，轉載請附上原文出處連結及本聲明。
原文連結：
https://blog.csdn.net/vn9PLgZvnPs1522s82g/article/details/88325263「視訊雲技術」你最值得關注的音視訊技術公衆号，每周推送來自阿裡雲一線的實踐技術文章，在這裡與音視訊領域一流工程師交流切磋。