CN1968164A - Global Internet topology knowledge-based P2P application construction method - Google Patents

Abstract

The invention relates to a P2P application construction method, a P2P application construction method based on global Internet network topology information. The method sequentially considers the following topological information in the process of node joining, network dynamic maintenance and download point decision-making: the longest IP address prefix match, the corresponding relationship between IP address and AS number, and the topological connection graph of global AS. The method includes: step S1, when a new node joins the network, the bootstrap server selects neighbors for the new node according to the longest match of the IP address, the AS number corresponding to the IP address, and the AS topology map in turn; step S2, after the node joins the network, when When a neighbor exits the network, the node uses the above information to dynamically select a replacement neighbor. In step S3, the above topology information is used to help select the adjacent download point of the requested file in all query response messages, thereby reducing the download traffic across management domains.

Description

P2P Application Construction Method Based on Global Internet Topology Knowledge

technical field

The invention relates to the technical field of border gateway protocol (BGP) table and Internet autonomous system level topology, in particular to a P2P application construction method based on global Internet topology knowledge.

Background technique

Peer-to-Peer (P2P peer-to-peer) technology has been widely used in various network applications, such as grid computing, file sharing and real-time media stream distribution. The enhancement of terminal capabilities and the increase of network bandwidth enable P2P technology to make full use of the computing, storage and transmission capabilities of network terminals.

The P2P network is an overlay network built on the application layer, and each node in the pure P2P network is a peer-to-peer relationship. Traditional P2P applications do not consider the topology of the underlying physical network, which may cause a mismatch between the overlay network and the underlying physical network. For example, two hosts belonging to the same LAN may not be directly adjacent to each other in the overlay network. , but are connected through several remote relay points, which results in the inefficiency of the upper layer overlay network in information transmission. At the same time, network operators and network managers hope to reduce P2P traffic between networks or between ISPs as much as possible, so that P2P traffic does not excessively consume precious inter-domain bandwidth.

The existing P2P network construction method that considers the underlying physical topology only considers the local topology knowledge of nodes, and uses TTL detection to determine the similarity between two nodes based on the number of router hops. However, this method does not consider the management characteristics of the network. That is, the P2P traffic should be limited to the smallest management domain as possible, and the P2P traffic between management domains should be minimized.

We roughly divide P2P applications into two categories: one is represented by the file sharing system, which is characterized by the fact that the P2P network is only used to transmit control information, while the actual data transmission is directly carried out point-to-point, which has nothing to do with the P2P network structure; The other type is represented by real-time media stream multicast, which is characterized in that the application layer multicast tree is both a transmission path for control information and data. For both types of P2P applications, applying global topology knowledge to build an overlay network can improve transmission efficiency and reduce inter-domain traffic. Figure 1 shows a P2P-based file sharing system, where the two planes respectively represent the topology of the underlying physical network and the topology of the overlay network. Among them, A-J represents the terminal node, the solid line represents the actual connection, and the resource r exists in B, E, and H. Assuming that the Flood resource search strategy is adopted and the TTL hop count is limited to 3, the search request for resource r sent from F will return B and H. Regardless of whether F chooses to obtain resource r from B or H, it is cross-domain traffic. However, if a P2P network is built based on the global physical topology knowledge, for example, E is directly regarded as a neighbor of F, then F can choose to obtain resource r from E, which generates intra-domain traffic, and in most cases, the rate is relatively fast. Figure 2 shows the construction scheme of the application layer multicast tree of the same node set, (a) does not consider the topology of the underlying network, (b) considers the topology of the underlying network, it can be seen that the multicast in (a) Four of the six edges of the tree are cross-domain edges, while (b) has only two cross-domain edges.

Contents of the invention

In order to solve the inconsistency between the overlay network and the physical network topology and reduce the P2P traffic between the management domains, the present invention proposes a P2P network construction, network dynamic maintenance and download point decision-making method based on the global Internet network topology knowledge, which makes the overlay The topology of the network and the underlying physical network is basically the same, and more importantly, it greatly reduces the P2P traffic between management domains.

P2P application construction method, the joining of new nodes, network dynamic maintenance and download point decision-making process in P2P applications are based on global network topology information rather than local topology information, and the constructed P2P overlay network has both physical proximity and management domain proximity .

The method is first based on the following assumptions:

(1) Hosts with the same IP address prefix are more similar than hosts with different IP address prefixes, and their transmission speed is generally faster.

(2) Hosts belonging to the same AS are closer and generally faster in transmission speed than hosts belonging to different ASs.

(3) Network operators and network managers hope that the less cross-domain P2P traffic, the better. The above assumption is not always true in some cases, but in most cases, it still satisfies physical proximity. More importantly, this invention considers the proximity of management domains when constructing an overlay network for the first time. In addition, the invention requires global network topology knowledge as a basis. When new nodes join, network dynamic maintenance and content downloading, the following three aspects of global network topology information are used:

(1) Given an IP address, the longest matching IP address prefix can be obtained. This can be obtained by comparing all route prefixes with the BGP table (RouteViews publishes BGP table information). For example, for the IP address 202.119.35.4, if both 202.119.0.0/16 and 202.119.32.0/20 match 202.119.35.4 in the routing prefix of the BGP table, the latter is taken as the longest match of the IP address.

(2) Given an IP address, you can get its corresponding AS number. This can be obtained by searching the source AS of the longest IP address prefix corresponding to the IP address.

(3) The topological connection diagram of the global AS level can be obtained from CAIDA (www.caida.org), or can be measured by oneself or speculated from the BGP table.

Based on the above, the process of joining a new node with an IP address of X during the evolution of the P2P network is as follows:

(1) The new node sends a join request to bootstrap;

(2) bootstrap calculates the corresponding longest IP prefix match and AS number according to the IP address of the node, and sends it to the node;

(3) Bootstrap selects a set of neighbors for the new node according to the following rules, and sends the set of neighbors to the new node.

The joining of a new node consists of the following steps:

S.1 If there is Y in the system so that X and Y have the same longest IP address prefix match, then select such Y as the neighbor of X;

S.2 If Y mentioned in step S.1 does not exist in the system, but Z exists in the system, so that Z and X have the same AS number, then select such Z as the neighbor of X;

S.3 If there is no node of the type mentioned in steps S.1 and S.2 in the system, use the topological connection graph of AS to select the node W with the minimum AS hop count with X as the neighbor of X.

(4) The new node establishes a logical connection to these neighbors and completes the addition of the node. At the same time, during operation, a node needs to:

(1) According to the global topology information, dynamically select the senders of some query request packets, and record them in the temporary list;

(2) Periodically detect the state of the current neighbor list;

(3) If some neighbors in the current neighbor list have left the network or do not respond, select some nodes from the temporary list as the new neighbors of the current node.

When the response message of the request arrives, the node will preferentially recommend those nodes with the same IP address prefix as the node as the download point, if there is no such response point, then recommend those download points in the same AS as the node, if still If there is no such response point, the nodes with the shortest AS hops to this node are recommended as download points.

During the dynamic operation of the network, each node utilizes the following three aspects of global network topology information when joining new nodes, dynamically maintaining the network, and downloading content:

(1) The longest address prefix match of the IP address;

(2) The AS number corresponding to the IP address;

(3) Topological connection diagram of AS level.

The topology information dynamically selects the IP addresses of some other nodes to record, and when a neighbor leaves, selects several from the recorded IP address list as its new neighbors.

After the request response message arrives, instead of the user choosing a download point arbitrarily, the node intelligently recommends the adjacent download point to the user according to the global topology information.

The method of the invention solves the inconsistency between the application layer overlay network and the underlying network topology, and simultaneously considers the management characteristics of the underlying network, thereby reducing the P2P traffic between different network management domains to the greatest extent, including query traffic and download traffic.

Description of drawings

Figure 1 is an example of the inefficiency of information transmission in the overlay network caused by the inconsistency between the topology of a P2P overlay network and the underlying physical topology.

Fig. 2 is a diagram of different application layer multicast tree construction methods for the same vertex set.

Fig. 3 is the flow of the P2P application construction method based on global Internet topology knowledge of the present invention

Detailed ways

Figure 1 is an example where the topology of the P2P overlay network does not match the topology of the underlying physical network. The underlying plane is the topology of the physical layer, and the upper plane is the topology of the overlay network. The three ellipses represent three different management domains, and A-J represent terminal machines , the solid line represents the actual connection, resource r exists in nodes B, E, H. The system adopts the Flood search strategy and limits its TTL to 3. The arrow indicates the query message path of searching resource r starting from F. As a result, B and H will respond to the query request, while E in the same domain cannot receive the query request because the construction method of the P2P overlay network does not conform to the underlying topology.

Figure 2 shows different application layer multicast tree construction methods for the same vertex set, where A-F are terminal machines, and three ellipses represent three different management domains. (a) is a multicast tree construction scheme that does not consider the underlying topology, and (b) is a multicast tree construction scheme that considers global topology information. It can be seen that the application layer multicast tree constructed based on the global topology information has fewer cross-domain connections, thereby reducing inter-domain traffic as much as possible.

FIG. 3 is a flow chart of the P2P application construction method based on global Internet topology knowledge of the present invention.

Its main steps are as follows:

Step S1, new nodes join:

Step S1.1, node A to be joined sends a join request to the bootstrap server;

Step S1.2, bootstrap calculates the longest IP address prefix and AS number of the node according to the IP address of the node to be joined, and sends it to the node to be joined;

Step S1.3, bootstrap selects an initial neighbor set for the node to be joined according to the global topology knowledge, and sends it to the node to be joined;

Step S1.4, the node to be added establishes a logical connection with each of the initial neighbor set, and completes the node joining process;

Step S2, dynamic maintenance of the network:

Step S2.1 The node detects the IP address, IP address prefix and AS number carried in the request while processing the request, selects some nodes that are not the current neighbors but are similar, and record them in the temporary list. Step S2.2 The node periodically detects the current the state of the neighbor list;

Step S2.3 If some neighbors in the current neighbor list leave the network or do not respond, select several neighbors from the temporary list as the node's new neighbors;

Step S3 When the response message of the request arrives, determine which nodes are relatively nearby download points according to the IP address, IP address prefix and AS number carried in the response message, and recommend them to the user in an appropriate manner.

Bootstrap needs to store a binary search tree of IP address prefixes, a mapping table of IP address prefixes and AS numbers, and a global AS topology map. Each Peer needs to maintain a topology map of the global AS. All query messages and response messages must contain the IP longest prefix match and AS number of the message sender.

The execution flow of a node starting from requesting to join the network is shown in Figure 3.

Claims (6)

1. The P2P application construction method based on the topological information of the global underlying Internet network is characterized in that the process of adding new nodes, network dynamic maintenance and download point decision-making process in the P2P application is based on the global network topological information rather than local topological information. The P2P overlay network has both physical proximity and administrative domain proximity. 2. the P2P application construction method based on global bottom layer Internet network topology information as claimed in claim 1, is characterized in that, when new node joins, network dynamic maintenance and content download, utilized the global network topology information of following three aspects: (1) The longest address prefix match of the IP address; (2) The AS number corresponding to the IP address; (3) Topological connection diagram of AS level. 3. the P2P application construction method based on global bottom layer Internet network topology information as claimed in claim 1, is characterized in that, the joining of new node is made up of the following steps: S.1 If there is Y in the system so that X and Y have the same longest IP address prefix match, then select such Y as the neighbor of X; S.2 If Y mentioned in step S.1 does not exist in the system, but Z exists in the system, so that Z and X have the same AS number, then select such Z as the neighbor of X; S.3 If there is no node of the type mentioned in steps S.1 and S.2 in the system, use the topological connection graph of AS to select the node W with the minimum AS hop count with X as the neighbor of X. 4. The P2P application construction method based on the topological information of the global underlying Internet network as claimed in claim 1, wherein, in the dynamic running process of the network, each node dynamically selects some of the topological information according to claim 2. Record the IP addresses of other nodes, and when a neighbor leaves, select several from the recorded IP address list as your new neighbors. 5. The P2P application construction method based on the topological information of the global underlying Internet network as claimed in claim 1, characterized in that, after the request response message arrives, the download point is not arbitrarily selected by the user, but the node intelligently according to the global The topology information recommends to the user nearby download points. 6. A P2P application construction method based on global Internet network topology information, its steps are as follows: Step S1, new nodes join: S1.1 The new node sends a join request to bootstrap; S1.2bootstrap calculates the longest IP prefix match and AS number corresponding to the node's IP address, and sends it to the node; S1.3bootstrap selects a group of neighbors for the new node according to the method according to claim 3, and sends the set of neighbors to the new node; S1.4 The new node establishes a logical connection to these neighbors, and completes the joining of the node; Step S2, dynamic maintenance of the network: S2.1 Each node detects the IP address, IP address prefix and AS number carried by the request while processing the request, and records a temporary list according to the rule described in claim 4; S2.2 Each node regularly detects the state of the current neighbor list; S2.3 If some neighbors leave the network or do not respond in the current neighbor list, select several neighbors from the temporary list as the node's new neighbors; Step S3, when the requested response message arrives, according to the method of claim 5, the node determines which nodes are relatively adjacent download points according to the IP address, IP address prefix and AS number carried in the response message, and uses an appropriate recommended to users.