聯通IP組網的弊端

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

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

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

可行解決方法

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

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

自治系統介紹

1. 自治系統與其編號

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

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

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

2. 邊界網關協議

在介紹邊界網關協議之前，我們先簡單介紹一下內部網關協議（Interior Gateway Protocol, IGP）、外部網關協議（Exterior Gateway Protocol ,EGP）。

內部網關協議：運行在一個自治系統內部的一種路由協議，也就是網關（主機和路由器）間交換路由信息的協議。

外部網關協議：運行在不同自治系統之間的一種路由協議，是一種簡單的網絡可達性協議，使身在不同自治系統內的主機和路由器能夠交換信息。

由上頭的定義我們可以知道，內部網關協議適用于一個王國內的信息傳遞，而外部網關協議適用于兩個不同王國間的信息傳遞。

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

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

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

數據獲取工具與原理（吉民）

1. 內容定義

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

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

2. 數據爬取

爬取流程

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

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

3. 對當前asn，爬取下面每個的route號和子網號

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

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

爬取結果入庫

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

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

最長匹配原則

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

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

將爬取到的route和asn，從數據庫中以文件的形式導出到hdfs分布式文件系統中。

加載爬取結果文件到內存中，以Map數據結構存放，key為route/子網位數，value為asn號。

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

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

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

1. 將ip解析為route和asn的流程開發為hive的UDF形式，再hive中創建解析函數ip_to_asn_route

2. 驗證子網掩碼的最長匹配原則

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

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

2.從test_cdn_ip表統計ip的個數

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

4.統計p2p_report_route_asn表route_asn不等于空的個數

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

ASN組網條件與可行性評估

1. ASN內/間是否存在顯著差異

ASN概覽

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

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

ASN具體差異

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

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

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

2. 覆蓋度

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

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

3. ASN數量與IP分布情況

數量級

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

分布情況

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

熊貓用戶端IP分布

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

{zoom=50%}

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

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

結論與展望

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