熊貓直播通過ASN組網(wǎng)提升P2P分享率的實踐

聯(lián)通IP組網(wǎng)的弊端

回顧一下上一篇我們評估IP組網(wǎng)的可行性，存在幾個問題，最為重要的挑戰(zhàn)就是用戶網(wǎng)絡的復雜性。首先，大多數(shù)用戶的IP是動態(tài)分配的結果，導致這個用戶每次訪問熊貓直播所屬IP都不一樣，每個月節(jié)點IP遍及將近上千萬個；其次，用戶層面上來說，我們需要實時獲取基本的用戶網(wǎng)絡拓撲結構、實時掌握用戶的網(wǎng)絡狀況并對其進行分析，哪些用戶IP之間適合組網(wǎng)、哪些IP之間連通性更好、哪些IP之間距離更短，也就是說整個用戶網(wǎng)絡從IP層面來看是時時刻刻處于不斷變化的狀態(tài)。

結合上述兩點，如果每個月利用上千萬個節(jié)點IP，進行Floyd-Warshall經(jīng)典的動態(tài)規(guī)劃算法，計算任意兩個節(jié)點IP間的最短路徑計算，其時間復雜度為$O(n^3)$、空間復雜度為$O(n^2)$，數(shù)據(jù)體量大、計算速度慢，所以，雖然使用IP組網(wǎng)精確度較高，但是因為數(shù)據(jù)量大導致過程中的計算極其復雜，不適合熊貓直播的場景！

綜上可知，如果我們想組網(wǎng)，單從IP層面下手肯定不行，必須先把IP先進行分組，將相鄰的IP聚集成一個單位后在進行組網(wǎng)。

可行解決方法

既然IP組網(wǎng)存在較難跨越的障礙，我們提出幾個和適用于IP分組的想法，包括ASN組網(wǎng)、Route組網(wǎng)、地域組網(wǎng)、運營商組網(wǎng)等。經(jīng)過基本計算，我們發(fā)現(xiàn)千萬節(jié)點IP中，遍及六千多個route、將近一千個ASN、三百多個二級市、三十多個省份。

route組網(wǎng)的可行性，實際上我們將熊貓用戶遍及的千萬個節(jié)點IP歸結到route后，約遍及6000多個route，數(shù)量大大降低，計算復雜性同時也就降低不少。然而當我們享用空間換取時間時，利用查表方式，$6000^2$的數(shù)據(jù)還是遠高于利用ASN組網(wǎng)查表的數(shù)量（$1000^2$）。利用地域分組在主觀意識上會覺得同地理區(qū)塊應該距離比較近，但真實網(wǎng)絡的狀況和地理位置沒有絕對關系，可能同一個自治系統(tǒng)內(nèi)的IP遍及多個省份。而運營商組網(wǎng)就更不用提了，雖然計算復雜度相對很低，但分組粒度粗、精確度低，效果不理想。反觀ASN組網(wǎng)，一千個ASN，計算復雜性不管在空間還是時間上，都落在可接受的范圍，數(shù)據(jù)粒度也較為合適，最重要的是，其原理接近真實網(wǎng)絡狀態(tài)，各運營商都在使用，對于熊貓場景較為合適。

自治系統(tǒng)介紹

1. 自治系統(tǒng)與其編號

在互聯(lián)網(wǎng)中，自治系統(tǒng)（自治系統(tǒng)，AS）指的是一個能夠自主決定應該采用何種路由協(xié)議的小型單位。而一個自治系統(tǒng)將會分配一個全局的唯一的16位號碼，我們把這個號碼叫做自治系統(tǒng)號（ASN）。

還是不太清楚？還是覺得有點抽象？那我們換個說法，通俗的語言來形容，自治系統(tǒng)就是互聯(lián)網(wǎng)里的一個一個獨立王國，這一個個獨立王國互聯(lián)起來，就組成了互聯(lián)網(wǎng)（Internet），每個王國有自己獨立的國號，以利區(qū)別每個王國，而這個國號對應的就是自治系統(tǒng)號（自治系統(tǒng)編號，ASN）。

每個互聯(lián)網(wǎng)的用戶都置身于AS內(nèi)，可以想像成每個王國里面的居民，比如中國電信AS號為4809，那么中國電信的用戶就屬于4809的獨立王國，如果用戶訪問的服務器也是在這個AS內(nèi)，那雙向的流量就都在此王國中來回溜噠，如同居民們互相拜訪一樣沒有任何問題。那么問題來了，如果訪問的服務器屬于另一個不同的AS呢？也就是說兩個不同王國的居民們要如何跨王國訪問彼此？

2. 邊界網(wǎng)關協(xié)議

在介紹邊界網(wǎng)關協(xié)議之前，我們先簡單介紹一下內(nèi)部網(wǎng)關協(xié)議（Interior Gateway Protocol, IGP）、外部網(wǎng)關協(xié)議（Exterior Gateway Protocol ,EGP）。

內(nèi)部網(wǎng)關協(xié)議：運行在一個自治系統(tǒng)內(nèi)部的一種路由協(xié)議，也就是網(wǎng)關（主機和路由器）間交換路由信息的協(xié)議。

外部網(wǎng)關協(xié)議：運行在不同自治系統(tǒng)之間的一種路由協(xié)議，是一種簡單的網(wǎng)絡可達性協(xié)議，使身在不同自治系統(tǒng)內(nèi)的主機和路由器能夠交換信息。

由上頭的定義我們可以知道，內(nèi)部網(wǎng)關協(xié)議適用于一個王國內(nèi)的信息傳遞，而外部網(wǎng)關協(xié)議適用于兩個不同王國間的信息傳遞。

而BGP的概念和EGP較為相似，用來取代EGP。

BGP協(xié)議是網(wǎng)路路由協(xié)議（Routing Protocol）的一種，主要是一個用來在自治系統(tǒng)之間傳遞路由的協(xié)議，、AS之間會使用邊界網(wǎng)關協(xié)議（Border Gateway Protocol，BGP）收集相鄰節(jié)點的可達性信息，并交換各自的IP路由表，而ASN就是BGP協(xié)議用來辨識鄰國的一個身分證，同時在交換的路由表信息里，會附上各自的ASN。既然A王國可以通過BGP學接學習到B王國的路由信息，A王國（AS A）就可以把其居民（用戶）的訪問請求轉(zhuǎn)發(fā)給B王國（AS B）的邊界路由器，A王國的IP包順利進入B王國后，接下來就任由B王國的設備進行處理，順利到達目標服務器后，回程檢查用戶IP，發(fā)現(xiàn)是來自A王國的IP，就會以相同方式透過BGP將其轉(zhuǎn)發(fā)回A王國的邊界路由器，最終傳到達原始發(fā)請求的居民。

就目前國內(nèi)市場來說，中國網(wǎng)通 、中國電信、中國鐵通和一些大的運營商都具有專屬AS號，運營商多數(shù)都是通過BGP協(xié)議與自身的AS號來實現(xiàn)多線互聯(lián)，與真實網(wǎng)絡狀圖較為相似，所以我們大膽假設利用ASN組網(wǎng)是可行且合適的！

數(shù)據(jù)獲取工具與原理（吉民）

1. 內(nèi)容定義

使用pyspider框架對亞太地區(qū)的asn數(shù)據(jù)周期爬取，將爬取到的asn數(shù)據(jù)入到關系型數(shù)據(jù)庫，最后導到hive中分析 與使用。

pyspider框架是通過python腳本進行結構化信息的提取，follow鏈接調(diào)度抓取控制，實現(xiàn)最大的靈活性；通過web化的腳本編寫、調(diào)試環(huán)境。web展現(xiàn)調(diào)度狀態(tài)抓取環(huán)模型成熟穩(wěn)定，模塊間相互獨立，通過消息隊列連接，從單進程到多機分布式靈活拓展。

2. 數(shù)據(jù)爬取

爬取流程

1. 從ftp地址作為爬取入口ftp://ftp.apnic.net/public/apnic/stats/apnic/delegated-apnic-latest

2. 獲取每一個asn號碼，拼接成目標鏈接后進行訪問，獲得當前asn的地理位置

3. 對當前asn，爬取下面每個的route號和子網(wǎng)號

紅色的route比綠色的route號在表示范圍上更精準。在從客戶端ip轉(zhuǎn)換route/asn時，如果匹配上紅色的，則返回當前route和asn；都沒有匹配上紅色的route，則會匹配最長子網(wǎng)掩碼的綠色的route，返回其route/asn；如果綠色的route也沒匹配上，則返回空值。

4. 周期定時爬取，至于周期是多久，得需要根據(jù)組網(wǎng)的要求情況。譬如ip當前屬于這個asn，到了下一個小時可能屬于另一個asn了，通過數(shù)據(jù)挖掘分析得出asn變動的大概周期A，那么爬取周期B保證小于周期A。

爬取結果入庫

將爬取到的route號和asn號入庫，在入庫操作時，是根據(jù)route來做更新的（有則更新無則插入），這樣在route號所在的asn有變動時都能保證是最新的。

3. ip解析為route及asn的流程

最長匹配原則

最長匹配原則是CISCO IOS路由器默認的路由查找方式。當路由器收到一個IP數(shù)據(jù)包時，會將數(shù)據(jù)包的目的IP地址與自己本地路由表中的表項進行bit by bit的逐位查找，直到找到匹配度最長的條目，這叫最長匹配原則。

保證ip匹配到更精準的route和asn

將爬取到的route和asn，從數(shù)據(jù)庫中以文件的形式導出到hdfs分布式文件系統(tǒng)中。

加載爬取結果文件到內(nèi)存中，以Map數(shù)據(jù)結構存放，key為route/子網(wǎng)位數(shù)，value為asn號。

ip解析為網(wǎng)絡號的程序，將ip與子網(wǎng)號的位數(shù)做與運算，子網(wǎng)號位數(shù)是由31位到1位的順序處理，最終將該ip計算出的的每個網(wǎng)絡號存放在內(nèi)存List數(shù)據(jù)結構中，這樣的順序能夠保證最長匹配的位數(shù)在前面，最短匹配的位數(shù)在后面。

將解析出的保存在List中的網(wǎng)絡號列表分別作為key從加載到內(nèi)存中的Map獲取value，獲取到第一個value值且該值不為空時則終止List的遍歷，這樣就能保證匹配到最長的子網(wǎng)掩碼對應的route，最終返回route和asn結果。

4. IP解析route/asn的應用示例

1. 將ip解析為route和asn的流程開發(fā)為hive的UDF形式，再hive中創(chuàng)建解析函數(shù)ip_to_asn_route

2. 驗證子網(wǎng)掩碼的最長匹配原則

5. 從CDN日志的ip，對asn覆蓋度進行分析

1.從cdn日志中抽取了半個月的ip，且對其去重，存放到test_cdn_ip表中

2.從test_cdn_ip表統(tǒng)計ip的個數(shù)

3.對test_cdn_ip的host_ip使用寫好的UDF函數(shù)，將執(zhí)行結果保存在p2p_report_route_asn表

4.統(tǒng)計p2p_report_route_asn表route_asn不等于空的個數(shù)

5.統(tǒng)計cdn近半個月ip所對應的asn覆蓋率：接近98%，還算理想

ASN組網(wǎng)條件與可行性評估

1. ASN內(nèi)/間是否存在顯著差異

ASN概覽

透過ASN分布分析可以得知，權重TOP20的ASN包涵將近九成九的節(jié)點IP，ASN間與ASN內(nèi)部的一些明顯特征畫成一張圖，如下所示。

首先，由外而內(nèi)第二圈代表不同ASN，占比例越大代表權重（包含rtt, 跳數(shù), 所含IP等）越高，也意外著ASN的體量及重要性。最外圈表示ASN內(nèi)部跳數(shù)分布，分為一跳、二跳、三跳、四跳、四跳以上，我們可以發(fā)現(xiàn)大多集中在一跳，四跳以上幾乎為0，除了少數(shù)幾個ASN比較特殊，代表ASN內(nèi)IP的傳輸距離較近。第三圈表現(xiàn)的ASN內(nèi)部rtt的分布，分為30毫秒以內(nèi)、30-100毫秒、100-500毫秒、500-1000毫秒，1000毫秒以上基本已經(jīng)當做離群值處理掉了，整體數(shù)據(jù)看多數(shù)落在前兩區(qū)間，也就是基本落在100毫秒內(nèi)，同樣代表ASN內(nèi)IP的傳輸距離較近。最內(nèi)圈表示的則是不同ASN之間的連接狀況，線越粗代表連線數(shù)量越多，線的顏色代表起始ASN的顏色，能清楚看到TOP20 ASN間兩兩相連關系。

ASN具體差異

前面提出ASN組網(wǎng)合適用于熊貓直播的場景，現(xiàn)在要證明在實際數(shù)據(jù)分析下，ASN間（inter)與ASN內(nèi)部（inner）確實具有顯著差異。

首先，我們將同一ASN內(nèi)的訪問與兩兩ASN間的訪問區(qū)分開來，每一個ASN內(nèi)的rtt取中位數(shù)后我們得到一系列不同ASN內(nèi)的rtt中位數(shù)；同理，我們將相同兩個ASN間訪問rtt取中位數(shù)后，也會得到一系列兩兩ASN間的rtt中位數(shù)，將這兩筆數(shù)據(jù)化成機率密度分布圖可以看見，ASN內(nèi)（inner，紅色）的rtt中位數(shù)偏小，多數(shù)落在10毫秒以下，而ASN間（inter，綠色）的rtt中位數(shù)偏高，多數(shù)落在50-100毫秒，超過1000毫秒的也有不少。這與我們假設相符，想同ASN之內(nèi)的IP較易相連、延時較短，而不同ASN間的IP相連延時較長。

同樣原理，我們計算跳數(shù)，得到下圖。ASN內(nèi)（inner，紅色）的跳數(shù)多落在一跳，也就是說IP在ASN內(nèi)連接距離較近，反觀ASN間（inter，綠色）超過五跳也不在少數(shù)，兩個在不同ASN內(nèi)的IP距離相對較遠。

2. 覆蓋度

利用CDN打點日志數(shù)據(jù)作為評估覆蓋度的參考，發(fā)現(xiàn)TOP15的ASN可覆蓋99%以上的節(jié)點IP且遍及99%以上的訪問次數(shù)，也就是涉及的IP、用戶多數(shù)集中于某幾個大的ASN中。

綜上，我們基本可以確認，在熊貓直播的場景下，ASN組網(wǎng)的基本條件已經(jīng)滿足！

3. ASN數(shù)量與IP分布情況

數(shù)量級

根據(jù)上述步驟從網(wǎng)上爬取下來亞太地區(qū)的ASN，總數(shù)約有八千個，而熊貓用戶遍及的ASN大約一千個左右，遠小于熊貓用戶端IP數(shù)量，即便我們做一個1000*1000的查詢表，也不是一件困難的事情，所以就量級上來說，確實相比于IP更加合適！

分布情況

接著我們看看熊貓用戶端IP的分布，由下面這張圖我們可以清楚看到，熊貓用戶雖然分布于全國各，但主要集中在某些省份，例如：廣東、江蘇、四川等，相對來說主要用戶還是比較聚集的，若進行p2p組網(wǎng)，效果也會比較顯著。

熊貓用戶端IP分布

如果我們將不同運營商的用戶區(qū)分開來，會發(fā)現(xiàn)每個運營商用戶的分布狀況不一樣，移動用戶多數(shù)集中在四川、江蘇、河南、廣東，聯(lián)通用戶多數(shù)集中在山東、河南、河北、北京，電信的用戶則多數(shù)集中在四川、江蘇、廣東、湖南，可以見得，以運營商區(qū)分用戶，在地域上也相對較復雜、數(shù)據(jù)粒度太粗，不適合直接利用運營商組網(wǎng)。另一方面，每個運營商間用戶分布不同，卻各自集中，也就是我們可以結合地域和運營商兩個維度來對用戶IP進行分組，而上述ASN組網(wǎng)的方式就同時具有此兩種特性。

{zoom=50%}

最后我們看看TOP100 ASN間在地域上的分布狀況與連接情況，每個點上有一圈一圈，代表著其他ASN訪問數(shù)量，越多圈圈代表越多訪問經(jīng)過此ASN，每一個圈圈的顏色和邊的顏色相同，代表著權重，升序依序是藍色、綠色、黃色、橘色、紅色。

首先我們能清楚看到，每個省份會有不只一個ASN，但數(shù)量也都是十個以下，和上面呼應，如果使用地域性質(zhì)組網(wǎng)，粒度會太粗（省份分組）或太細（二級市分組）；其次，我們可以發(fā)現(xiàn)主要大量訪問還是集中在某幾個ASN，和我們原先假設一樣，如果進行ASN組網(wǎng)，能夠以最小成本到最大效益。

結論與展望

本文提到的各種組網(wǎng)技術，其目的都是想讓所有的客戶端都能同時相互提供資源，包括分享帶寬、計算力等，有別于以往的方法，我們從用戶層面出發(fā)，提出利用ASN自建P2P網(wǎng)絡，使得整個網(wǎng)絡近似于完全的P2P網(wǎng)絡，邊緣CDN不再需要頻繁分發(fā)同一路直播流，這將大大改善網(wǎng)絡傳輸環(huán)境，提高整個網(wǎng)絡的數(shù)據(jù)共享率。比起IP組網(wǎng)，ASN組網(wǎng)除了可以改善了IP組網(wǎng)計算復雜度過高的問題，節(jié)省了儲存空間、提升了計算效率，同時整個P2P網(wǎng)絡的共享率以及網(wǎng)絡穩(wěn)定性也是在相對可接受的范圍內(nèi)，能夠用相對小的成本，達到最高效益。