文 / 熊猫直播基础研发部

IP组网

一. 组网背景-IP组网是什么，有什么意义?

商业背景

本项目为熊猫直播平台服务，众所周知，网络直播近年非常火热，同一个直播间可能有上万人在观看，产生的流量是相当可观的，并且会占用相当高的网络带宽，由此产生的直播流数据费用将是很大一笔数目。而CDN级的p2p网络尚不能完全满足节省流量的需求，为此我们从节省带宽的目的出发提出了熊猫直播自建P2P网络的想法，并计划了长期的执行方案。

P2P网络介绍

P2P即peer-to-peer,peer指“伙伴”,P2P即“伙伴对伙伴”。而P2P网络即可以理解为对等网络.在这样的网络中，每个网络节点同时作为客户端和服务器端。没有中心服务器，没有中心路由器。它的一个重要目标是让所有的客户端都能提供资源，包括带宽，存储和计算能力。具体的网络拓扑结构可以分为集中式，分布式，混合式以及结构化P2P网络，因此P2P网络常被用于分布式科学计算，如著名的SETI@home项目，文件共享如BitTorrent,以及流媒体直播等等。

集中式P2P网络

分布式P2P网络

混合式P2P网络

IP组网介绍

在整个基于数据分享为目的的P2P网络中，每个节点会与多个相邻节点建立连接并进行数据交换，对于网络直播而言，即分享共同观看的直播数据片段。这里的核心问题在于如何组网才能使得该p2p网络的分享率可以达到最大，我们的做法是从IP层面组建P2P网络，而这实际上是一个规划问题。

图论基础

图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。图分为有向图和无向图。

图的数学表示：G（V，E），其中V是顶点集：V={Vi,i=1...n} ; E是边集：E={Ei,i=1...n}

顶点的度：一个顶点的度在无向图中是指与该顶点相连的边的个数。有向图的顶点的度还可以细分为入度和出度，入度是以该顶点为头（head）的边的条数，出度是以该顶点为尾（tail）的边的条数。如下图无向图中2号节点的度为4，有向图中2号节点的出度为1，入度为3。无向图

应用

我们从整个用户网络角度出发，假设用户网络图为G(V,E)，V是顶点集合，E是边的集合，每条边上有权重weight，这里的weight可以用网络延迟来概括，即每个IP到其他IP的rtt值的大小，采用rtt来表征连通性是因为网络延迟可以比较直观且准确的反映两个IP之间的网络状况。在这张全局的用户网络图的基础上，我们可以为每一路直播流下的用户P2P组网提供数据支持。

所以核心问题可以抽象的表示为：在以每一路流为目标组建P2P网络时，可以将该P2P网络图抽象为g(V,E),网络g(V,E)中新加入一个共享节点node后，如何选择节点与node建立连接使新的P2P网络g'(V,E)保证最大的共享率。为了保证网络的稳定性，我们规定每个节点的度数即共享IP数不应该超过20(当然这里的20是粗略估计，具体数目得根据网络状况动态设定。)在这样的前提下参考用户网络G(V,E),找出至多20个与node连通性好(rtt小)的目标节点(这里需要保证目标节点也在该路流下且度数加一后不会超过20),与node进行p2p组网。这样我们便实现了在保证整个P2P网络稳定性的前提下使得每个节点的共享率最大，也就实现了全局的共享率最大化。

二. 基本观点-当前业界在P2P共享网络上的做法以及我们的尝试?

典型应用案例及观点

在以数据共享为目的的P2P网络中，典型的做法有P2P文件分发，如BitTorrent,每个节点向其他相邻节点获取不同的数据片段，最后组合成一个完整文件，实现静态文件共享的目的。这种做法对于固定且规模较大的文件共享有比较好的效果，但对于网络直播的流数据来说则不太适用。

在流媒体领域，典型的案例有P2P+CDN（简称PCDN）的解决方案，CDN主要用于可靠的Web和流媒体内容分发,而P2P则主要用于内容交换。二者结合的核心思想是在CDN网络的边缘节点上引入P2P自治域，在域内利用P2P技术实现资源共享，自治域之间不发生流量交换。这样可以大大降低边缘服务器的压力，提高了网络的稳定性和文件传输的效率。PCDN的做法虽然在CDN层面改善了网络，但在用户层面，每个客户端还是分别向同一个CDN拉取相同的数据，在流媒体应用上也就是同一路视频流。这也就是PCDN做法的瓶颈所在。

我们的尝试即是从用户层面出发，自建P2P网络，这也就意味着即使是边缘CDN，也不用频繁分发同一路直播流，使得整个网络近似于完全的P2P网络，而这，将大大改善网络传输环境，提高整个网络的数据共享率。

为了达到这个目标，我们引入了用户层面的IP组网。对此，需要解决的难题有很多，这些困难可以集中表达为用户网络的复杂性以及网络数据规模，在CDN层面，实际上有一个清晰的P2P组网架构，在用户层面，我们要做的也是掌握用户的网络状况。

正如上面所介绍的，IP组网前提是拥有一张全局的用户网络图G(V,E)，每条边以rtt作为权重，这里的网络图实际上接近于一张全连通图，就是说每个节点与其他节点都应该存在一条边，而我们的收集上来的记录实际上并不足以构成这样一张全联通图，并且边的权重也不是最佳权重，所以得在已有的图的基础上通过图的最短路径算法来计算出每个节点到其他节点的rtt值，以此为p2p组网做铺垫。

在已有的基于图算法的用户网络图基础上，我们为每一个节点提供组网时的可用节点，通过查询包含该节点的最短连接，找出与它最“近”的某几个节点作为候选节点来建立p2p连接，从而达到最优化组网的目的。

三. 实践过程

数据获取过程:如何获取网络拓扑结构 ?

网络原理 - Traceroute介绍

traceroute(Windows系统下是tracert)命令可以遍历数据包传输路径上的所有路由器，从源主机使用traceroute 目标主机的命令，即可依次打印出所有经过的路由器以及相应的rtt值。在网络原理上主要利用IP数据包的TTL字段值和ICMP协议来实现，在此不作展开，我们的工具即是基于该命令收集用户网络的路径信息，并作相应的格式处理。

具体实现 - SDK的使用

目前数据采集主要在安卓客户端进行，实际采集中使用到了网易的一个开源SDK，这里贴出该工具的Github 网址：https://github.com/Lede-Inc/LDNetDiagnoService_Android

该工具使用到了上述的traceroute的网络原理，对指定域名进行网络诊断，并收集诊断日志，其中用到了开源网络检测库iputils进行ICMP报文模拟。

数据分析过程:如何还原运营商网络联通图 ?

数据特点

在具体实践过程中我们是通过用户客户端SIP来tracert我们的服务器目标DIP进而探测整个网络的分布状况，根据收集上来的数据来看，我们的数据分布范围非常广泛，涵盖了国内的绝大部分地区，以及国外的部分网络。下面列出了客户端IP的分布状况，目标服务器IP的分布状况，以及总体的全国网络IP分布状况。

客户端IP分布状况

服务器目标IP分布状况

用户网络IP分布状况

从以上的分布图可以看出我们的目标服务器IP则更为分散，这样有利于采集到更广大范围的数据，而最终我们的客户端IP和整个网络的IP覆盖到了绝大部分省市，主要分布在东部，并集中在一些规模较大的城市，这也符合我们国家的网络状况，在数据上有足够的可信度，为之后的分析提供了保障。

共享IP订立规则

速度：作为共享的IP组来说，首先得保证IP之间的数据传输速度要够快，这一点可以由rtt(延迟)，hop_cnt(跳数)来衡量，即我们希望的是延迟低，跳数少的IP之间互传数据，建立组网。

频度：频度是指一对IP连接在记录上表现的数量，即是说从我们收集上来的数据来看，如果一对IP之间频繁出现通信或者数据传输，那么这一对IP将是整个网络的重要连接(桥梁)，在进行IP组网的时候就需要优先将这一对IP作为相邻节点互传数据

稳定性：基于以上两个因素，在IP组网的过程中还需要保证网络连接的稳定性，即保证网络延迟的波动不会过大，这一层面可以由rtt来表征，rtt波动大则说明网络稳定性比较差，rtt波动小则说明网络稳定性高，适合作为相邻节点进行组网。

其他因素：除了以上几点之外，其他的因素也可以作为参考条件考虑，比如说组网的一对IP是否属于同一网段，是否属于同一自治域，是否属于同一运营商，在此基础之上，需要讨论同一网段，自治域，运营商内的IP之间的连通性是否比不同网段，自治域，运营商之间更好。

在实践过程中，以上因素不一定均会考虑到，上面也说了，目前我们用速度即rtt这一因素就可以表示出各个IP对之间的连通性好坏，也就是说整张用户网络图G(V,E)是建立在网络延迟这一重要属性上的。

数据格式与规模

在数据处理过程中，我们将一个tracert命令返回的路径信息进行拆分，可以得到格式化的每一段记录的信息:路径源IP—路径终IP—该跳起始IP—该跳终点IP—该跳起始ASN—该跳终点ASN—跳数，通过这些处理过的格式化信息，可以为接下来的分析做铺垫。截至到目前，这样的格式化数据一共收集了20亿条，平均每天可以收集上来大约4千万条数据。

数据分析过程

传输速度：通过对各个单独的IP对计算rtt和hop_cnt的综合值(这里取中位数)，可以得到每个IP与其他有连接的IP之间传输的延迟和跳数的综合值，作为传输速度的表征。例如：

传输频度：通过对各个单独的IP对计算存在的记录数，包括总记录数，以及每天的单独记录数，就可以大致模拟出二者之间互传数据的频度，也就可以表征出二者之间的连接作为网络拓扑中的桥梁作用。例如：

稳定性：对于每一组IP对，我们以rtt为对象，研究网络延迟的稳定性，并以标准差作为衡量标准，因为整个网络环境处于不稳定状态，传输的延迟也会随之发生必然的波动，所以我们在组网的过程中也就需要规避不稳定的网络状况，尽量选择稳定的连接作为数据共享的peers，以此提高整个P2P网络的共享稳定性。例如：

以上数据是建立在已有记录的基础上的，即没有考虑到节点间最短路径的计算结果，在计算节点最短路径的过程中，我们采用了floyd全图最短路径算法，但是会面临两个问题，即时间复杂度和空间复杂度，该算法的时间复杂度为O(n^3),空间复杂度为O(n^2),是相当高的，随着数据规模的扩大，计算所用的时间会不断增加，目前来看4000左右的节点规模所用时间为7到8小时，而IP节点的数目要远高于该规模，所以计算时间上是无法容忍的。在空间复杂度上，由于该算法是全图最短路径算法，所以会不断更新得到的最短路径图，并得到最终的全连通图G(V,E)，所需要的计算资源，存储资源是相当高的，对于性能的调优是个不小的挑战。

即是说，我们的瓶颈即在于该算法的瓶颈，而对算法进行改进或者寻找更好的大数据图算法是需要一定时间的，这就需要考虑到时间成本问题。

四. 总结

通过以上的研究以及实践过程，我们可以得出以下的结论以及观点。

IP组网对于建立一个可以在用户级别共享数据的P2P网络是理论上可行的，并且有确切的数据支撑，可以做到相当精确的程度，也就是说使用IP组网来实现P2P网络可以最大化该P2P网络的共享率以及网络稳定性，从这个角度来说，IP组网应当是最佳的选择。

相对的，使用IP级别的组网，必然会带来很多问题，从数据分析角度来看，由于数据规模过大，我们在分析的过程中会面临相当大的复杂度，具体体现在图算法的瓶颈，带来时间和空间上的巨大开销，而改进现有算法或选用更好的算法则需要更多的时间成本来尝试和比较。

另外，从网络的动态变化来看，其实越往细处，网络的不确定性越高，即是说，在IP层面，我们很难把握到精确的状态，比如说移动数据网络的IP地址实际上是动态分配的，局域网返回的IP可能还包含诸如192.168.0.1这种保留IP。而这种数据对于图算法的计算会带来很大的误差，很多时候并不能反映真实的网络状况。为此我们需要更高维度的网络研究，比如网段级别，网络自治域级别，能够从更加宏观的角度反映真实的网络状况，而且在需要计算的数据规模上也是可以把控的。

————————————————

原文链接：https://blog.csdn.net/vn9PLgZvnPs1522s82g/article/details/88325263