熊猫直播 P2P 分享率优化(下):ASN 组网
文章版权:熊猫直播基础研发部,直播技术架构
文章首发链接:https://mp.weixin.qq.com/s/eOl-KyPvVbrll_o37FMKyg
本文来自熊猫直播基础研发部的投稿,是熊猫直播P2P分享率优化系列文章的第二篇,第一篇请访问这里。重点展示了熊猫直播通过ASN组网提升P2P分享率的实践。
联通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,计算复杂性不管在空间还是时间上,都落在可接受的范围,数据粒度也较为合适,最重要的是,其原理接近真实网络状态,各运营商都在使用,对于熊猫场景较为合适。
自治系统介绍
自治系统与其编号
在互联网中,自治系统(自治系统,AS)指的是一个能够自主决定应该采用何种路由协议的小型单位。而一个自治系统将会分配一个全局的唯一的16位号码,我们把这个号码叫做自治系统号(ASN)。
还是不太清楚?还是觉得有点抽象?那我们换个说法,通俗的语言来形容,自治系统就是互联网里的一个一个独立王国,这一个个独立王国互联起来,就组成了互联网(Internet),每个王国有自己独立的国号,以利区别每个王国,而这个国号对应的就是自治系统号(自治系统编号,ASN)。
每个互联网的用户都置身于AS内,可以想像成每个王国里面的居民,比如中国电信AS号为4809,那么中国电信的用户就属于4809的独立王国,如果用户访问的服务器也是在这个AS内,那双向的流量就都在此王国中来回溜哒,如同居民们互相拜访一样没有任何问题。那么问题来了,如果访问的服务器属于另一个不同的AS呢?也就是说两个不同王国的居民们要如何跨王国访问彼此?
边界网关协议
在介绍边界网关协议之前,我们先简单介绍一下内部网关协议(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组网是可行且合适的!
数据获取工具与原理(吉民)
内容定义
使用pyspider框架对亚太地区的asn数据周期爬取,将爬取到的asn数据入到关系型数据库,最后导到hive中分析 与使用。
pyspider框架是通过python脚本进行结构化信息的提取,follow链接调度抓取控制,实现最大的灵活性;通过web化的脚本编写、调试环境。web展现调度状态抓取环模型成熟稳定,模块间相互独立,通过消息队列连接,从单进程到多机分布式灵活拓展。
数据爬取
爬取流程
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有变动时都能保证是最新的。
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结果。
IP解析route/asn的应用示例
1. 将ip解析为route和asn的流程开发为hive的UDF形式,再hive中创建解析函数ip_to_asn_route
2. 验证子网掩码的最长匹配原则
从CDN日志的ip,对asn覆盖度进行分析
从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组网条件与可行性评估
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距离相对较远。
覆盖度
利用CDN打点日志数据作为评估覆盖度的参考,发现TOP15的ASN可覆盖99%以上的节点IP且遍及99%以上的访问次数,也就是涉及的IP、用户多数集中于某几个大的ASN中。
综上,我们基本可以确认,在熊猫直播的场景下,ASN组网的基本条件已经满足!
ASN数量与IP分布情况
数量级
根据上述步骤从网上爬取下来亚太地区的ASN,总数约有八千个,而熊猫用户遍及的ASN大约一千个左右,远小于熊猫用户端IP数量,即便我们做一个1000*1000的查询表,也不是一件困难的事情,所以就量级上来说,确实相比于IP更加合适!
分布情况
接着我们看看熊猫用户端IP的分布,由下面这张图我们可以清楚看到,熊猫用户虽然分布于全国各,但主要集中在某些省份,例如:广东、江苏、四川等,相对来说主要用户还是比较聚集的,若进行p2p组网,效果也会比较显著。
熊猫用户端IP分布
如果我们将不同运营商的用户区分开来,会发现每个运营商用户的分布状况不一样,移动用户多数集中在四川、江苏、河南、广东,联通用户多数集中在山东、河南、河北、北京,电信的用户则多数集中在四川、江苏、广东、湖南,可以见得,以运营商区分用户,在地域上也相对较复杂、数据粒度太粗,不适合直接利用运营商组网。另一方面,每个运营商间用户分布不同,却各自集中,也就是我们可以结合地域和运营商两个维度来对用户IP进行分组,而上述ASN组网的方式就同时具有此两种特性。
最后我们看看TOP100 ASN间在地域上的分布状况与连接情况,每个点上有一圈一圈,代表着其他ASN访问数量,越多圈圈代表越多访问经过此ASN,每一个圈圈的颜色和边的颜色相同,代表着权重,升序依序是蓝色、绿色、黄色、橘色、红色。
首先我们能清楚看到,每个省份会有不只一个ASN,但数量也都是十个以下,和上面呼应,如果使用地域性质组网,粒度会太粗(省份分组)或太细(二级市分组);其次,我们可以发现主要大量访问还是集中在某几个ASN,和我们原先假设一样,如果进行ASN组网,能够以最小成本到最大效益。
结论与展望
本文提到的各种组网技术,其目的都是想让所有的客户端都能同时相互提供资源,包括分享带宽、计算力等,有别于以往的方法,我们从用户层面出发,提出利用ASN自建P2P网络,使得整个网络近似于完全的P2P网络,边缘CDN不再需要频繁分发同一路直播流,这将大大改善网络传输环境,提高整个网络的数据共享率。比起IP组网,ASN组网除了可以改善了IP组网计算复杂度过高的问题,节省了储存空间、提升了计算效率,同时整个P2P网络的共享率以及网络稳定性也是在相对可接受的范围内,能够用相对小的成本,达到最高效益。
直播技术架构
One Reply to “熊猫直播 P2P 分享率优化(下):ASN 组网”
赶紧删除B站代码吧,不然可能被起诉