文 / 熊貓直播基礎研發部
聯通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網絡的共享率以及網絡穩定性也是在相對可接受的範圍内，能夠用相對小的成本，達到最高效益。
————————————————
版權聲明：本文為CSDN部落客「LiveVideoStack_」的原創文章，遵循CC 4.0 BY-SA版權協定，轉載請附上原文出處連結及本聲明。
原文連結：
https://blog.csdn.net/vn9PLgZvnPs1522s82g/article/details/88568782「視訊雲技術」你最值得關注的音視訊技術公衆号，每周推送來自阿裡雲一線的實踐技術文章，在這裡與音視訊領域一流工程師交流切磋。