聯(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),能夠用相對小的成本,達到最高效益。
-
運營商
+關注
關注
4文章
2385瀏覽量
44293 -
P2P
+關注
關注
0文章
151瀏覽量
26635 -
組網(wǎng)
+關注
關注
1文章
341瀏覽量
22279
原文標題:熊貓直播P2P分享率優(yōu)化(下):ASN組網(wǎng)
文章出處:【微信號:livevideostack,微信公眾號:LiveVideoStack】歡迎添加關注!文章轉(zhuǎn)載請注明出處。
發(fā)布評論請先 登錄
相關推薦
評論