CN111314156B - Overlay network snapshot acquisition method and evaluation method for peer-to-peer network streaming media - Google Patents

Abstract

The invention discloses an overlay network snapshot acquisition method and evaluation method oriented to peer-to-peer network streaming media. The snapshot acquisition method includes constructing a distributed crawler system oriented to peer-to-peer network streaming media system. The preset crawling algorithm of the feedback mechanism collects the node snapshots of the target channel coverage network, and evaluates the integrity of the network snapshots by using the node snapshot topology microscopic deformation index, the node snapshot topology macroscopic stability index and the coverage controllable node discovery rate. The invention can avoid the problem of low crawling efficiency caused by the existing crawler system using a single crawler terminal to collect snapshot information of the overlay network, effectively improve the crawling efficiency of the crawler system, and ensure the integrity and accuracy of the crawling results.

Description

Overlay network snapshot acquisition method and evaluation method for peer-to-peer network streaming media

technical field

The invention belongs to the technical field of network communication in computer science and technology, and in particular relates to a method for obtaining and evaluating a snapshot of an overlay network for peer-to-peer network streaming media.

Background technique

In recent years, the measurement research on peer-to-peer network streaming media system has received extensive attention from the global academic community, and the research content has covered user behavior research, topology structure research, traffic characteristics research, security mechanism research and so on. These research works provide important research ideas for in-depth understanding of the working principle, system architecture, topology properties, traffic characteristics, and security issues of large-scale peer-to-peer network streaming media systems. Among them, the active measurement method based on crawler technology studies the communication protocol of a specific peer-to-peer network streaming media system through protocol analysis technology or reverse engineering technology. Collect relevant information. Since the active measurement method based on crawler technology can accurately and directly obtain the user information of the peer-to-peer network streaming media system, this method is widely used to study the topology, user behavior, geographical distribution, user scale, security, and security of the peer-to-peer network overlay network. It is the most effective and mainstream measurement method for peer-to-peer network streaming media system research. In the active measurement method, the overlay network snapshot information is the most important kind of information. It includes the basic information such as the IP address and port number of a single node in the overlay network of the target program at a certain moment, the scale of online nodes and the connections between nodes. relationship, etc. Collecting accurate snapshots of overlay network nodes is the basis and premise to study the dynamic behavior characteristics of users and the evolution characteristics of topology structure in peer-to-peer network streaming media systems.

Due to the large-scale, self-organized, and highly dynamic characteristics of the peer-to-peer network streaming media system itself, the active measurement work for it faces huge challenges: (1) The peer-to-peer network streaming media overlay network has strong dynamic characteristics, which The crawler program that collects node information is required to quickly access the nodes in the peer-to-peer streaming media overlay network, but the access speed of the crawler program is not only limited by its own network access capability, but also related to the network access speed of the interactive nodes during its crawling process. In the process of collecting information by the crawler, the information of the overlay network nodes will always change to a certain extent; (2) There are some unreachable nodes in the peer-to-peer network streaming media system, and the nodes may be in the firewall or in the NAT (Network Address Translator, Network Address Translator). ), these nodes belong to the peer-to-peer network streaming media system, but they do not respond to the node list request sent by the crawler and return their neighbor node information, which may result in incomplete data acquisition of overlay network node information.

At present, in the active measurement research for peer-to-peer network streaming media systems, most crawlers use a single crawler terminal to collect overlay network snapshot information, and there is a lack of systematic evaluation of the accuracy and integrity of overlay network node snapshot collection results. indicator system.

SUMMARY OF THE INVENTION

Aiming at the above problems existing in the prior art, the present invention provides a method for obtaining and evaluating an overlay network snapshot for a peer-to-peer network streaming media, which improves the crawling efficiency of the crawler system and the integrity and accuracy of the crawling result.

In order to achieve the above-mentioned purpose of the invention, the technical scheme adopted in the present invention is:

A method for obtaining a snapshot of an overlay network for peer-to-peer network streaming media, comprising the following steps:

Build a distributed crawler system for peer-to-peer streaming media systems;

The distributed crawler system uses a preset crawling algorithm to collect node snapshots of the target channel coverage network.

Further, the distributed crawler system oriented to the peer-to-peer network streaming media system specifically includes multiple node list server crawler modules and multiple common node information crawler modules that communicate with the peer-to-peer network streaming media system overlay network respectively, and respectively. The crawler controller module for network communication with the node list server crawler module and the common node information crawler module.

Further, the crawler controller module specifically adopts an adaptive scheduling algorithm to dynamically distribute the crawling tasks to each crawler module, dynamically adjust the balanced operation of the crawler tasks in each crawler module, receive and process the crawling results fed back by each crawler module and send them back to the crawler module. save to the database;

The node list server crawler module first parses the channel play link to obtain the node list server address and service port number of the channel, and then uses the knowledge of the communication protocol of the peer-to-peer network streaming media system obtained by the reverse engineering method to construct the same node list as the ordinary client. Request message, continuously send node list request message to the node list server, and collect target channel overlay network node information;

The common node information crawler module sends a node list request to all nodes to obtain node list information maintained by the target node after the node list server crawler module completes the collection of the target channel, and finally deduplicates all the collected node information to obtain The final node information of the target channel and form a node snapshot and store it in the database.

Further, the distributed crawler system adopts the preset crawling algorithm to collect the node snapshots of the target channel coverage network, which specifically includes the following sub-steps:

(1) Utilize the node list server crawler module to first send a node list request to the node list server provided by the channel play link analysis module to obtain the seed nodes required for crawling;

(2) Use the common node information crawler module to store the collected seed nodes in the discovered node queue, mark them as unvisited nodes, and then send node list requests to the unvisited nodes in turn, and finally request the nodes that have been requested. The nodes in the list are marked as visited nodes and stored in the visited node queue;

(3) After the target node returns the list of nodes it owns, use the common node information crawler module to add the new nodes that are not repeated in the received node list to the tail of the found node queue;

(4) Use the common node information crawler module to continuously send node list requests to the nodes that have not been visited in the discovered node queue to obtain the partner node information it has, until the currently requested node is the last node of the discovered node queue. The entire crawling Process ends.

Further, in the crawling process, after sending a node list request to the target node, if the node exceeds the set time threshold or does not return its response message at the end of the crawling, the node is determined to be an unreachable node, and the node is set as an unreachable node. Save to unreachable node queue.

Further, during the node snapshot collection process, before the node snapshot information crawled in the previous round is fed back to the next round, the unreachable nodes and server nodes are first removed, and then the nodes in the node snapshot are analyzed according to the size of the node degree. Sorting is performed, and finally, the set proportion node with larger node degree after sorting and the node fed back from the node list server are jointly used as the seed node and become the input of the next round of crawling.

The present invention also proposes a method for evaluating results of snapshot collection of overlay network oriented to peer-to-peer network streaming media, comprising the following steps:

Applying the above-mentioned overlay network snapshot acquisition method to obtain an overlay network snapshot acquisition result;

Based on the node snapshot topology deformation index, the node snapshot topology stability index and the overlay network controllable node discovery rate, the collection efficiency of the overlay network snapshot and the integrity of the collection results are evaluated.

Further, the crawling efficiency of the distributed crawler system is expressed as:

为爬虫终端的爬行效率，ρ为爬虫终端采集的目标频道覆盖网络节点快照完整度，T_c为爬虫终端爬行频道c覆盖网络的总耗时，S_c为频道c覆盖网络中的真实节点快照，

为爬虫终端在第t秒钟采集的频道c覆盖网络节点快照。in,

is the crawling efficiency of the crawler terminal, ρ is the completeness of the target channel coverage network node snapshot collected by the crawler terminal, T _c is the total time spent by the crawler terminal crawling the network covered by channel c, S _c is the real node snapshot in the coverage network of channel c,

Snapshot of the channel c overlay network node collected by the crawler terminal in the t second.

和

其中

为目标频道覆盖网络中的节点集合，

为目标频道覆盖网络中节点之间的关系边集合，则节点快照

和

中节点元素的差异性表示为

边关系的差异性表示为

节点快照

和

拓扑形变指数γⁱ表示为：Further, set the distributed crawler systems at positions A and B to collect two node snapshots in the i-th round.

and

in

is the set of nodes in the overlay network for the target channel,

cover the set of relational edges between nodes in the network for the target channel, then the node snapshot

and

The difference of the node element in the middle is expressed as

The difference of the edge relationship is expressed as

Node snapshot

and

The topological deformation index γ ⁱ is expressed as:

和

中节点元素基于节点度大小进行排序，分别获得节点度从大到小排列的节点分布序列P_a和P_b，取集合P_a和P_b中排名的前k个节点对应的节点度大小构成样本

则节点快照

和

的拓扑结构稳定性指数χⁱ表示为：Take a snapshot of the node

and

The middle node elements are sorted based on the node degree size, and the node distribution sequences P _a and P _b are obtained from large to small node degrees, respectively, and the node degree corresponding to the top k nodes in the set P _a and P _b is taken to form a sample.

then the node snapshot

and

The topological stability index χ ⁱ of is expressed as:

表示集合P_a中排第j个节点的度大小，

表示集合P_b中排第j个节点的度大小，

表示集合P_a中排名前k个节点对应的节点度平均值，

表示集合P_b中排名前k个节点对应的节点度平均值；in,

represents the degree size of the jth node in the set _Pa ,

represents the degree size of the jth node in the set P _b ,

represents the average node degree corresponding to the top _k nodes in the set Pa,

represents the average node degree corresponding to the top k nodes in the set P _b ;

Deploy _n controllable nodes at the location of the _{crawler module respectively} , and the controllable _nodes are provided with different independent IP _addresses and port numbers. Represents a set of controllable nodes deployed in three different geographical locations, then the controllable node discovery rate ψ that the distributed crawler system collects snapshots of N nodes is expressed as:

The present invention has the following beneficial effects:

(1) The present invention constructs a high-performance crawler system oriented to a peer-to-peer network streaming media system by adopting a distributed architecture, node degree sorting and node snapshot feedback mechanism, and adopts a preset crawling algorithm to collect node snapshots of the target channel coverage network, which can Avoid the problem of low crawling efficiency caused by the existing crawler system using a single crawler terminal to collect snapshot information of the overlay network, and effectively improve the crawling efficiency of the crawler system;

(2) On the basis of the system architecture, crawling algorithm, crawling speed, and integrity of crawling results of the distributed crawler system, the present invention forms certain evaluation indicators and methods for measuring the reliability, integrity and accuracy of data, thereby ensuring that Completeness and accuracy of crawl results.

Description of drawings

1 is a schematic flowchart of a method for obtaining a snapshot of an overlay network for peer-to-peer network streaming media according to the present invention;

2 is a schematic diagram of a framework for obtaining a snapshot of an overlay network and an evaluation method for peer-to-peer network streaming media according to an embodiment of the present invention;

3 is a schematic diagram of a distributed crawler system framework for a peer-to-peer network streaming media system in an embodiment of the present invention;

4 is a schematic diagram of a node information storage queue in an embodiment of the present invention;

FIG. 5 is a schematic diagram of a flowchart of node snapshot collection in an embodiment of the present invention.

Detailed ways

In order to make the objectives, technical solutions and advantages of the present invention clearer, the present invention will be further described in detail below with reference to the accompanying drawings and embodiments. It should be understood that the specific embodiments described herein are only used to explain the present invention, but not to limit the present invention.

Example 1

As shown in FIG. 1 and FIG. 2 , an embodiment of the present invention provides a method for obtaining a snapshot of an overlay network oriented to peer-to-peer network streaming media, including the following steps:

A1. Build a distributed crawler system for peer-to-peer streaming media systems;

In an optional embodiment of the present invention, the large-scale and highly dynamic nature of peer-to-peer streaming media systems makes active measurement work against them a great challenge. Existing research shows that the overlay network of the peer-to-peer network system has strong dynamic characteristics, which requires the crawler program that collects node information to crawl quickly to obtain accurate node snapshots. Otherwise, due to the frequent joining and leaving of nodes in the overlay network of the peer-to-peer streaming media system, the node snapshot may be deformed during the crawling process of the crawler, resulting in inaccurate node snapshots being collected. More importantly, existing studies have shown that using inaccurate node snapshots to study the topological properties of the overlay network of peer-to-peer systems is likely to draw completely wrong conclusions. Therefore, the high-performance distributed crawler system proposed by the present invention is of great significance for implementing active measurement research for the peer-to-peer network streaming media system.

The above-mentioned distributed crawler system for the peer-to-peer network streaming media system specifically includes a plurality of node list server crawler modules and a plurality of common node information crawler modules that communicate with the peer-to-peer network streaming media system overlay network respectively, and respectively communicate with the node list. The crawler controller module for network communication between the server crawler module and the common node information crawler module is shown in Figure 3.

The crawler controller module is the core of the distributed crawler system, which is specifically used to dynamically distribute crawling tasks to each crawler module as needed, dynamically adjust the balanced operation of crawling tasks in each crawler module, and receive and process the crawling feedback from each crawler module. result and save it to the database. In order to make full use of the node information collection capability of each crawler module, the crawler controller module interacts with each crawler terminal in real-time task progress to master their task execution status, and uses an adaptive scheduling algorithm to dynamically allocate crawling tasks.

The node list server crawler module first parses the channel play link to obtain the node list server address and service port number of the channel, and then uses the peer-to-peer network streaming media system communication protocol knowledge obtained by reverse engineering to construct the same node list request report as the ordinary client. It continuously sends node list request messages to the node list server, and collects the target channel overlay network node information. Since the node list server cannot distinguish between the normal peer-to-peer network streaming media client and the node list server crawler system, the crawler program can continuously collect the target channel seed node information in this way.

When the node list server crawler module completes the collection of the target channel, it deduplicates the collected node information from different node list servers, and sends the deduplicated node information to the common node information crawler module and starts the common node information crawler module. The common node information crawler module sends a node list request to all nodes to obtain the node list information maintained by the target node, and finally deduplicates all the collected node information, obtains the final node information of the target channel, and forms a node snapshot and stores it in the database.

A2. Use a distributed crawler system to collect node snapshots of the target channel coverage network by using a preset crawling algorithm.

In an optional embodiment of the present invention, the above-mentioned distributed crawler system adopts a preset crawling algorithm to collect node snapshots of the target channel coverage network, which specifically includes the following sub-steps:

(1) Using the node list server crawler module to first send a node list request to the node list server provided by the channel play link analysis module to obtain the seed nodes required for crawling; the number of requests sent here can be set to 10 times;

(2) Use the common node information crawler module to store the collected seed nodes in the queue of discovered nodes (Queen of Discovered Peers, Queen-D), and mark them as unvisited peers (Unvisited Peers); The number of requests sent here can be set to 3 times; finally, the nodes that have requested the node list are marked as visited nodes (Visited Peers) and stored in the visited node queue (Queen of Visited Peers, Queen of Visited Peers, Queen of Visited Peers) -V);

(3) After the target node returns the list of nodes it owns, use the common node information crawler module to add the new nodes that are not repeated in the received node list to the tail of the found node queue Queen-D;

(4) The common node information crawler module is used to continuously send node list requests to the nodes that have not been visited in the found node queue Queen-D to obtain the partner node information it has, until the currently requested node (Current Peer) is the found node queue. The whole crawling process ends when Queen-D is the last node (Last peer).

The distributed crawler system of the present invention adopts a crawling strategy similar to breadth-first traversal, but is different from the existing research work, which adopts a fixed crawling period and evaluates the number of newly added nodes for determining the termination condition of the crawling process. The crawling termination condition of the distributed crawler system of the present invention depends on the setting of the node list request message sending time interval Δt.

During the crawling process, after sending a node list request to the target node, if the node exceeds the set time threshold T _u or does not return its response message at the end of the crawling, the node is considered as unreachable peers (Unreachable peers), and Save the node to the unreachable node queue Queen-U. The structure of the node information storage queue is shown in Figure 4.

In order to further improve the crawling performance of the distributed crawler system, the present invention adds a node degree sorting mechanism and a node snapshot information feedback mechanism, that is, the crawling results of each round are processed by the importance sorting algorithm and fed back to the next round of crawling as an input , in order to reduce the time consumption of the crawler system to obtain seed nodes in the initial stage of crawling, as shown in Figure 5. Specifically, before the node snapshot information crawled in the previous round is fed back to the next round, it is necessary to remove those unreachable nodes and server nodes (including node list server and streaming media distribution server nodes); The nodes in the node snapshot are sorted by the size of the node snapshot; finally, the top 30% nodes with the largest node degree after sorting and the nodes fed back from the node list server are used as the seed nodes as the input of the next round of crawling.

The value of the time interval (Crawling interval) for channel coverage network node snapshot collection can be adjusted according to the crawling speed of the crawler system and the need to observe the change frequency of topology snapshots.

Example 2

Based on the above-mentioned method for obtaining an overlay network snapshot for peer-to-peer network streaming media, the present invention also proposes a method for evaluating a result of overlay network snapshot collection for peer-to-peer network streaming media, as shown in FIG. 2 , including the following steps:

B1. Apply the above-mentioned overlay network snapshot acquisition method to obtain an overlay network snapshot acquisition result;

B2. Based on the node snapshot topology deformation index, the node snapshot topology stability index and the overlay network controllable node discovery rate, the collection efficiency of the overlay network snapshot and the integrity of the collection result are evaluated.

The distributed crawler system of the present invention uses the UDP protocol to send forged communication protocol messages, and interacts with the node list server and common nodes. Therefore, without considering the influence of network instability factors on the crawling process, the termination condition of the crawling process will depend on the speed at which the crawler sends the node list request (that is, the number of nodes that have not been visited in the Queen-D of Figure 3 consumed per unit time). ) and the speed at which the target node returns information about its partner nodes. Among them, the latter directly affects the number of new nodes in the queue Queen-D in Figure 3 per unit time. The feedback speed of partner node information is mainly affected by the network bandwidth of the crawler and the target node, the number of neighbor nodes fed back by the target node, and the speed at which the crawler sends the node list. If the crawler sends the node list request too fast, the feedback node list information may not reach the crawler terminal, and the crawling process has ended, which will cause the crawler system to fail to collect accurate node snapshots. On the contrary, if the sending speed of the node list request is too slow, although relatively complete node information can be obtained, it will increase the time-consuming of the whole crawling process. At the same time, too long crawling time is likely to cause the node snapshots collected to be deformed during the crawling, thus affecting the accuracy of the network topology measurement results. Therefore, it is very important to set the appropriate node list request speed of the crawler terminal module.

其中t∈{1,...,T_c}，那么分布式爬虫系统最终采集到的节点快照S_c′可表示为：In order to analyze the crawling performance of the crawler terminal and evaluate its crawling efficiency, the present invention assumes that the distributed crawler system is in one round of crawling, and the snapshot of the target channel coverage network node collected in the t second is as follows:

where t∈{1,...,T _c }, then the node snapshot S _c ' finally collected by the distributed crawler system can be expressed as:

Assuming that S _c is the real node snapshot in the coverage network of the target channel c at this time, then the integrity ρ of the node snapshot of the coverage network node of the channel c collected by the crawler terminal is expressed as:

The integrity ρ can be used to measure the accuracy of node snapshots collected by crawler terminals, but due to the distributed and highly dynamic characteristics of peer-to-peer streaming media systems, it is difficult for researchers to obtain accurate node snapshots S _c . Therefore, computing the integrity ρ of the node snapshots collected by the crawler terminal system faces a huge challenge.

In a highly dynamic peer-to-peer streaming media system, nodes join and leave the system frequently at all times, and the crawler system always accompanies the joining or leaving of nodes during the crawling process. These behaviors of nodes will cause the crawler system to fail to obtain an accurate node snapshot S _c , and the crawler collection may acquire more nodes than real nodes. In addition, studies have shown that even the system's own management platform cannot provide completely accurate real-time online node information, and there is a certain lag in updating the status of nodes that have left the system. When the node has left the overlay network of the target channel, but the node list server does not delete it immediately, this will cause the crawler terminal to still collect the node from the node list server. Therefore, this paper uses the intersection of S _c and S _c ′ to represent the real node set collected by the crawler when defining the completeness of the node snapshots collected by the crawler system. At the same time, it is assumed that the crawler completes the crawling process within the time threshold T _s Snapshot S _c ' is not deformed.

After it is known that the crawler terminal collects the node snapshot integrity ρ of the target channel coverage network and the total time-consuming T _c of the crawling process, this paper defines the crawling efficiency of the crawler system as:

为爬虫终端的爬行效率，ρ为爬虫终端采集的目标频道覆盖网络节点快照完整度，T_c为爬虫终端爬行频道c覆盖网络的总耗时，S_c为频道c覆盖网络中的真实节点快照，

为爬虫终端在第t秒钟采集的频道c覆盖网络节点快照。in,

is the crawling efficiency of the crawler terminal, ρ is the completeness of the target channel coverage network node snapshot collected by the crawler terminal, T _c is the total time spent by the crawler terminal crawling the network covered by channel c, S _c is the real node snapshot in the coverage network of channel c,

Snapshot of the channel c overlay network node collected by the crawler terminal in the t second.

将随爬虫终端发送节点列表请求的时间间隔Δt增加而降低。According to the definition of crawling efficiency, the shorter the time-consuming T _c of the crawler terminal in the crawling process, the higher the crawling efficiency, and the more complete the node snapshots collected by the crawler terminal, the higher the crawling efficiency. The crawling efficiency represents the accuracy and crawling speed of the crawler system in collecting node snapshots. According to the above analysis, the termination condition of the crawler terminal crawling process mainly depends on the speed at which the crawler sends the node list request. In the measurement process, this paper finds that there is a certain linear relationship between Δt and the crawling time T _c by curve fitting the measured data of the relationship between the time interval Δt of the crawler terminal sending the node list request and the crawling time T _c in the experiment. The crawling time T _c is a monotonically increasing function of Δt. Therefore, when the node snapshot S _c ' does not deform during the crawling process (0<T _c ≤T _s ), then the crawling efficiency of the crawler system

It will decrease as the time interval Δt for the crawler terminal to send the node list request increases.

According to the definition and analysis of the completeness ρ of node snapshots collected by the crawler terminal, the node snapshot S _c of the target channel only exists in theory. Due to the highly dynamic nature of the peer-to-peer streaming media system, it is difficult for the crawler system and the operating platform of the peer-to-peer streaming media system to obtain an accurate node snapshot S _c , so the node snapshot integrity ρ cannot be accurately quantified. A reliable method to verify whether the node snapshot collected by the crawler system is complete is to send a session connection request to all nodes in the node snapshot S _c ′, and judge the online status of the current node by evaluating the response of the target node to the session connection request. However, it has been shown that a large number of nodes do not respond to session establishment requests issued by the crawler due to the large number of nodes located behind firewalls or NAT devices. Therefore, the present invention adopts the controllable node to join the target channel coverage network, and then verifies the accuracy of the crawler's snapshot collection by evaluating whether the crawler system can capture the join and leave behavior of the controllable node. The present invention evaluates the integrity of the collection results of the distributed crawler system of the present invention in detail based on the three measurement indexes of the node snapshot topology deformation index, the node snapshot topology stability index and the coverage network controllable node discovery rate.

其中

表示第i轮采集的在线节点快照集合，N为采集的总轮数，

其中，

为非空有限集合，其元素为目标频道覆盖网络中的节点，表示为

p_k表示节点集合

中的第k个节点；

为有限集合(可空)，它的元素为目标频道覆盖网络中节点之间的关系边。同理可定义地理位置B、C的节点快照，它们位于不同的网络运营商环境中。为了对比各个爬虫采集快照的差异性，部署在不同地方的爬虫系统同一时刻被启动，另外节点快照采集的时间间隔也设置为相同。The set of time-continuous online node snapshots collected by the distributed crawler system located in geographic location A is defined as

in

Indicates the collection of online node snapshots collected in the i-th round, N is the total number of rounds of collection,

in,

is a non-empty finite set whose elements are nodes in the target channel overlay network, denoted as

p _k represents the set of nodes

The kth node in ;

is a finite set (nullable) whose elements are the relationship edges between nodes in the target channel overlay network. Similarly, node snapshots of geographic locations B and C can be defined, which are located in different network operator environments. In order to compare the differences between the snapshots collected by each crawler, the crawler systems deployed in different places are started at the same time, and the time interval for node snapshot collection is also set to the same.

和

其快照中节点元素的差异性可以用

表示，边关系的差异性可以用

来表示，那么节点快照

和

拓扑形变指数γⁱ表示为：For the crawler systems located at positions A and B, two node snapshots are collected in the i-th round respectively

and

The difference of node elements in its snapshot can be used

Representation, the difference of edge relation can be expressed by

to represent, then the node snapshot

and

The topological deformation index γ ⁱ is expressed as:

和

的拓扑结构完全不同时，γⁱ将取得最大值1；而当节点快照

和

的拓扑结构完全相同时，那么

γⁱ则将取得最小值0。它反映了两个拓扑快照微观的形变情况，其值越小，则对应的两个节点快照拓扑变化程度越小，反之则越大。Similarly, the topological deformation index of any two node snapshots can be calculated. When two nodes snapshot

and

When the topology is completely different, γ ⁱ will achieve the maximum value of 1;

and

When the topology is exactly the same, then

γ ⁱ will take the minimum value of 0. It reflects the microscopic deformation of the two topology snapshots. The smaller the value is, the smaller the degree of topology change of the corresponding two node snapshots, and vice versa.

和

对它们的节点元素进行基于节点度大小的排序，分别获得节点度从大到小排列的节点分布序列，

和

令

表示集合P_a中排第j个节点的度大小，

表示集合P_b中排第j个节点的度大小，

表示集合P_a中排名前k个节点对应的节点度平均值，

表示集合P_b中排名前k个节点对应的节点度平均值，取集合P_a和P_b中排名的前k个节点对应的节点度大小构成样本

那么两个节点快照

和

的拓扑结构稳定性指数χⁱ表示为：For node snapshots

and

Sort their node elements based on the size of the node degree, and obtain the node distribution sequence arranged from large to small, respectively,

and

make

represents the degree size of the jth node in the set _Pa ,

represents the degree size of the jth node in the set P _b ,

represents the average node degree corresponding to the top _k nodes in the set Pa,

Represents the average value of the node degrees corresponding to the top k nodes in the set P _b , and takes the node degrees corresponding to the top k nodes in the sets P _a and P _b to form a sample

then two node snapshots

and

The topological stability index χ ⁱ of is expressed as:

Similarly, the topological stability index of snapshots of any two nodes can be calculated. It reflects the macroscopic similarity of two topological snapshots. The larger the value, the higher the topological similarity of the corresponding two node snapshots, and vice versa. The value range of the stability index χ is also in [0,1] .

表示位于位置A的第i个可控节点(Controller host)，每一个节点由IP地址和服务器端口号来唯一确定，

令C＝C_a∪C_b∪C_c，则分布式爬虫系统采集N个节点快照的可控节点发现率ψ表示为：In order to characterize the ability of the distributed crawler system of the present invention to discover controllable nodes in the channel coverage network, n controllable nodes are respectively deployed in the crawler locations. These controllable nodes have different independent IP addresses and port numbers, and are distributed in the distribution network. Join the target channel coverage network before the crawler system starts. Sets of controllable nodes deployed in three different geographical locations are denoted by C _a , C _b and C _c respectively, where

Indicates the i-th controllable node (Controller host) located in position A, each node is uniquely determined by IP address and server port number,

Let C=C _a ∪C _b ∪C _c , then the controllable node discovery rate ψ that the distributed crawler system collects N node snapshots is expressed as:

Those of ordinary skill in the art will appreciate that the embodiments described herein are intended to assist readers in understanding the principles of the present invention, and it should be understood that the scope of protection of the present invention is not limited to such specific statements and embodiments. Those skilled in the art can make various other specific modifications and combinations without departing from the essence of the present invention according to the technical teaching disclosed in the present invention, and these modifications and combinations still fall within the protection scope of the present invention.

Claims (5)

1. A peer-to-peer network streaming media oriented overlay network snapshot obtaining method and an evaluation method are characterized by comprising the following steps:

constructing a distributed crawler system facing a peer-to-peer network streaming media system;

the method for acquiring the node snapshot of the target channel coverage network by using the distributed crawler system through the preset crawling algorithm specifically comprises the following steps:

(1) firstly, a node list server crawler module is utilized to send a node list request to a node list server provided by a channel playing link analysis module, and seed nodes required by crawling are obtained;

(2) storing the collected seed nodes into a found node queue by using a common node information crawler module, marking the seed nodes as nodes which are not accessed, then sequentially sending a node list request to the nodes which are not accessed, and finally marking the nodes which have requested the node list as accessed nodes and storing the accessed nodes into an accessed node queue;

(3) after the target node returns to the node list owned by the target node, adding a new node which is not repeated in the received node list to the tail of the found node queue by using a common node information crawler module;

(4) continuously sending a node list request to a node which is not accessed in the found node queue by using a common node information crawler module to acquire information of a partner node owned by the node until the whole crawling process is finished when the node which is currently requested is the last node of the found node queue;

evaluating the acquisition efficiency and the integrity of acquisition results of the overlay network snapshot based on the node snapshot topology deformation index, the node snapshot topology stability index and the overlay network controllable node discovery rate;

the crawling efficiency of the distributed crawler system is expressed as:

wherein,

for the crawling efficiency of the crawler terminal, rho is the snapshot integrity of the coverage network node of the target channel acquired by the crawler terminal, T_cTotal time consumption of coverage network for crawling channel c for crawler terminal S_cCovering a snapshot of the real nodes in the network for channel c,

covering a network node snapshot for a channel c acquired by the crawler terminal in the tth second;

setting distributed crawler systems located at positions A and B to respectively acquire two node snapshots at the ith round

And

wherein

The set of nodes in the network is overlaid for the target channel,

for a target channel to cover a set of relationship edges between nodes in a network, the nodes are snapshot

And

the difference of the middle node elements is expressed as

The difference of the edge relation is expressed as

Node snapshot

And

topological deformation index gammaⁱExpressed as:

node snapshot

And

the middle node elements are sorted based on the node degrees, and node distribution sequences P with the node degrees arranged from large to small are respectively obtained_aAnd P_bTake the set P_aAnd P_bNode degree size corresponding to the top k nodes of the medium rank constitutes a sample

Node snapshot

And

topological structure stability index ofχⁱExpressed as:

wherein,

representation set P_aThe degree of the jth node in the middle row,

representation set P_bThe degree of the jth node in the middle row,

representation set P_aThe node degree average value corresponding to k nodes before the middle rank,

representation set P_bAverage node degree values corresponding to k nodes before the medium rank;

respectively deploying n controllable nodes at the location of the crawler module, wherein the controllable nodes are provided with different independent IP addresses and port numbers, and making C equal to C_a∪C_b∪C_c，C_a、C_bAnd C_cRespectively representing controllable node sets deployed at three different geographic positions, and then the controllable node discovery rate psi for the distributed crawler system to acquire N node snapshots is represented as:

2. the overlay network snapshot obtaining method and the evaluating method for the peer-to-peer network streaming media according to claim 1, wherein the distributed crawler system of the peer-to-peer network streaming media system specifically includes a plurality of node list server crawler modules and a plurality of common node information crawler modules, which respectively communicate with the overlay network of the peer-to-peer network streaming media system, and a crawler controller module, which respectively performs network communication with the node list server crawler modules and the common node information crawler modules.

3. The method for acquiring and evaluating an overlay network snapshot facing peer-to-peer network streaming media according to claim 2, wherein the crawler controller module dynamically distributes the crawling task to each crawler module by specifically adopting an adaptive scheduling algorithm, dynamically adjusts the balanced operation of the crawling task in each crawler module, receives and processes the crawling result fed back by each crawler module, and stores the crawling result in the database;

the node list server crawler module firstly analyzes a channel playing link to obtain the address and the service port number of a node list server of the channel, then constructs a node list request message which is the same as that of a common client by utilizing the peer-to-peer network streaming media system communication protocol knowledge obtained by a reverse engineering method, continuously sends the node list request message to the node list server and collects the node information of a target channel coverage network;

and the common node information crawler module sends a node list request to all nodes to obtain node list information maintained by the target node after the node list server crawler module finishes collecting the target channel, and finally, all the collected node information is subjected to duplicate removal to obtain final node information of the target channel and form a node snapshot to be stored in a database.

4. The method for acquiring and evaluating the overlay network snapshot facing the peer-to-peer network streaming media of claim 1, wherein in the crawling process, after sending a node list request to a target node, if the node exceeds a set time threshold or does not return its response message after the crawling is finished, the node is determined as an unreachable node, and the node is saved in an unreachable node queue.

5. The overlay network snapshot obtaining method and the evaluation method for the peer-to-peer network streaming media as claimed in claim 1 or 4, wherein in a node snapshot collecting process, before node snapshot information crawled in a previous round is fed back to a next round, inaccessible nodes and server nodes are removed first, then nodes in the node snapshots are sorted according to the node degrees, and finally, a node with a set proportion and a node fed back from a node list server, which have a larger node degree after being sorted, are used together as seed nodes to be input for the next round of crawling.

Images