METHOD, DEVICE AND SYSTEM FOR PROCESSING A NETWORK MAPPING IDENTIFIER, AND PEER SELECTION METHOD

• US 20120110089A1
• Filed: 01/11/2012
• Published: 05/03/2012
• Est. Priority Date: 07/24/2009
• Status: Active Grant

• Current Assignee: Huawei Technologies Co., Ltd. (Huawei Investment & Holding Co., Ltd.)
• Original Assignee: Huawei Technologies Co., Ltd. (Huawei Investment & Holding Co., Ltd.)
• Inventors: Wang, Yan, Chen, Guoyi
• Granted Patent: US 9,325,788 B2
• Time in Patent Office: Days
• US Class Current: 709/205
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/80 Ingress point selection by the source endpoint, e.g. selection of ISP or POP
• CPC Class Codes: H04L 61/5092 by self-assignment, e.g. picking addresses at random and testing if they are already in use
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks

Abstract

A method, a device and a system for processing a network mapping identifier, and a peer selection method are provided, in which the method includes: obtaining topology information of a network, in which the topology information includes a relation between nodes in the network; generating a network mapping identifier capable of indicating a relation between a peer and other peers in the network according to the topology information; and combining the generated network mapping identifier and an Internet Service Provider (ISP) identifier into a network mapping identifier, and allocating the network mapping identifier to the peer. Through the method, the device and the system, the network topology information of an ISP is protected from being exposed, a load on the ISP is reduced, and private information of a peer-to-peer (p2p) application system is capable of being protected.

Claims

1. A method for processing a network mapping identifier, the method comprising:

obtaining topology information of a network, wherein the topology information comprises a relation between nodes in the network;

generating a network mapping identifier capable of indicating a relation between a peer and other peers in the network according to the topology information; and

allocating the generated network mapping identifier to the peer.

2. The method according to claim 1, wherein the generating the network mapping identifier capable of indicating the relation between the peer and other peers in the network according to the topology information comprises:

generating a peer identifier capable of indicating a relation between the peer and other nodes in the network according to the topology information, and using the peer identifier as the network mapping identifier;

or

the generating the network mapping identifier capable of indicating the relation between the peer and other peers in the network according to the topology information comprises;

generating a peer identifier capable of indicating the relation between each peer and other peers in the network according to the topology information;

generating an Internet Service Provider (ISP) identifier for indicating a relation between each ISP and other ISPs in the network; and

combining the ISP identifier and the peer identifier into the network mapping identifier.

3. The method according to claim 2, wherein the relation between the nodes in the network is weight values between the nodes in the network;

and

the ISP identifier is a number, a string, or an identifier allocated according to an ISP policy.

4. The method according to claim 3, wherein the generating the peer identifier capable of indicating the relation between the peer and other peers in the network according to the topology information comprises:

generating a binary tree according to the relation between the nodes in the topology information, marking a left edge between any two sibling nodes in the binary tree as 1, marking a right edge between any two sibling nodes in the binary tree as 0, and using binary numbers, 0s and 1s, from a treetop to each leaf node of the binary tree form a binary code to generate a peer identifier of a node corresponding to each leaf node;

or

generating a binary tree according to the relation between the nodes in the topology information, marking a left edge between any two sibling nodes in the binary tree as 0, marking a right edge between any two sibling nodes in the binary tree as 1, and using binary numbers, 0s and 1s, from a treetop to each leaf node of the binary tree to form a binary code to generate a peer identifier of a node corresponding to each leaf node.

5. The method according to claim 4, wherein the nodes are Autonomous System (AS) nodes, and the allocating the generated network mapping identifier to the peer comprises:

allocating a network mapping identifier of an AS node corresponding to the each leaf node to each peer comprised in the AS node;

or

the nodes are Point of Presence (POP) nodes, and the allocating the generated network mapping identifier to the peer comprises;

allocating a network mapping identifier of a POP node corresponding to the each leaf node to each peer connected to the POP node;

or

the nodes are peers.

6. The method according to claim 5, wherein the generating the binary tree according to the relation between the nodes in the topology information comprises:

obtaining a first set formed by weight values between first nodes in the network according to the topology information;

selecting a smallest weight value from the first set, using two first nodes A1 and B1 corresponding to the smallest weight value as child nodes to establish a parent node C1 of 1l and B1, deleting the smallest weight value from the first set, and using a weight value between the parent node C1 and each of other first nodes i1 to replace a weight value between A1 and the first node i1 and a weight value between B1 and the first node i1 in the first set, wherein the weight value between the parent node C1 and the first node i1 is a greater one of the weight value between A1 and the first node i1 and the weight value between B1 and the first node i1, and other first nodes i1 are other first nodes in the network except the first nodes A1 and B1; and

continuously selecting a smallest weight value from the first set till only one weight value is left in the first set, using two first nodes An1 and Bn1 corresponding to the left weight value as child nodes to establish a parent node Cn1 of An1 and Bn1, wherein the parent node Cn1 is a root node of the generated binary tree.

7. The method according to claim 4, wherein the nodes comprise first nodes and second nodes;

the allocating the generated network mapping identifier to the peer comprises;

allocating the generated network mapping identifier of the second node corresponding to the each leaf node to each peer belonging to the second node; and

the second node belongs to the first node.

8. The method according to claim 7, wherein the generating the binary tree according to the relation between the nodes in the topology information comprises:

generating a preliminary binary tree according to a relation between the first nodes in the topology information;

using each leaf node of the preliminary binary tree as a parent node according to a relation between the second nodes and a relation between each second node and each first node in the topology information to establish a subtree under the each leaf node of the preliminary binary tree to generate the binary tree.

9. The method according to claim 3, wherein the generating the peer identifier capable of indicating the relation between the peer and other peers in the network according to the topology information comprises:

obtaining weight values between the nodes in the network according to the topology information to construct an n×

n matrix Q, wherein n is the number of the nodes, W_ij is an element in an i^th row and a j^th column in Q and is a weight value from an i^th node to a j^th node, and when i=j, W_ij is a value greater than or smaller than all weight values between the nodes, i,jε

[1,n];

decomposing Q into Q1 and Q2, wherein a product of Q1 and Q2 is Q; and

extracting elements in an i^th row in Q1, and using the elements in the i^th row in Q1 to form a source part of a multidimensional vector of the i^th node;

extracting elements in an i^th row in Q2, and using the elements in the i^th row in Q2 to form a destination part of the multidimensional vector of the i^th node;

combining the source part and the destination part into the multidimensional vector of the i^th node, and using the multidimensional vector as a peer identifier of the node.

10. The method according to claim 9, wherein the nodes are AS nodes, and the allocating the generated network mapping identifier to the peer comprises:

allocating a generated network mapping identifiers of an AS node to peers comprised in the AS node;

or

the nodes are POP nodes, and the allocating the generated network mapping identifier to the peer comprises;

allocating a generated network mapping identifier of a POP node to the peers connected to the POP node;

or

the nodes are peers.

11. The method according to claim 3, wherein the nodes comprise first nodes and second nodes;

and the second node belongs to the first node;

the generating the peer identifier capable of indicating the relation between the peer and other peers in the network according to the topology information comprises;

obtaining a multidimensional vector of the first node, wherein the multidimensional vector of the first node comprises a source part and a destination part;

obtaining a multidimensional vector of the second node, wherein the multidimensional vector of the second node comprises a source part and a destination part; and

combining the source part of the multidimensional vector of the first node and the source part of the multidimensional vector of the second node into a first source part, combining the destination part of the multidimensional vector of the first node and the destination part of the multidimensional vector of the second node into a first destination part, and combining the first source part and the first destination part into a peer identifier of a peer in the second node.

12. The method according to claim 11, wherein the obtaining the multidimensional vector of the first node comprises:

obtaining weight values between the first nodes in the network according to the topology information to construct an n×

n matrix Q, wherein n is the number of the first nodes, W_ij is an element in an i^th row and a j^th column in Q and is a weight value from an i^th first node to a j^th first node, and when W_ij is a value greater than or smaller than all weight values between the first nodes, i, jε

[1,n];

decomposing Q into Q1 and Q2, wherein a product of Q1 and Q2 is Q; and

extracting elements in an i^th row in Q1, and using the elements in the i^th row in Q1 to form a source part of a multidimensional vector of the i^th first node;

extracting elements in an i^th row in Q2, and using the elements in the i^th row in Q2 to form a destination part of the multidimensional vector of the i^th first node;

combining the source part of the multidimensional vector of the i^th first node and the destination part of the multidimensional vector of the i^th first node into the multidimensional vector of the i^th first node;

the obtaining the multidimensional vector of the second node comprises;

obtaining weight values between the second nodes in the network according to the topology information to construct an m×

m matrix P, wherein m is the number of the second nodes, P_xy is an element in an x^th row and a y^th column in P and is a weight value between the x^th second node and the y^th second node, and when x=y, P_xy is a greatest value or a smallest value of all weight values between the second nodes, x, yε

[1,m]

decomposing P into P1 and P2, wherein a product of P1 and P2 is P; and

extracting elements in an x^th row in P1, and using the elements in the x^th row in P1 to form a source part of a multidimensional vector of the x^th second node;

extracting elements in a y^th row in P2, and using the elements in the x^th row in Q2 to form a destination part of the multidimensional vector of the x^th second node; and

combining the source part of the multidimensional vector of the x^th second node and the destination part of the multidimensional vector of the x^th second node into the multidimensional vector of the x^th second node.

13. The method according to claim 3, wherein the generating the peer identifier capable of indicating the relation between the peer and other peers in the network according to the topology information comprises:

generating multidimensional space coordinates of each peer according to the topology information, and using the multidimensional space coordinates as a peer identifier of the peer.

14. A peer selection method using a network mapping identifier, the method comprising:

obtaining a network mapping identifier of a peer, wherein the network mapping identifier is capable of indicating a relation between the peer and other peers in a network; and

selecting a target peer for performing data transmission with the peer according to the network mapping identifier.

15. The method according to claim 14, wherein the network mapping identifier comprises an Internet Service Provider (ISP) identifier and a peer identifier.

16. The method according to claim 15, wherein the selecting the target peer for performing data transmission with the peer according to the network mapping identifier comprises:

obtaining a candidate peer list; and

performing exclusive-or operation on a network mapping identifier of each candidate peer having the same ISP identifier as the peer and the network mapping identifier of the peer, and selecting a candidate peer of a smallest exclusive-or operation result as the target peer.

17. The method according to claim 15, wherein the selecting the target peer for performing data transmission with the peer according to the network mapping identifier comprises:

obtaining a candidate peer list; and

calculating an inner product of a network mapping identifier of each candidate peer having the same ISP identifier as the peer and the network mapping identifier of the peer, and selecting a candidate peer of a smallest or greatest inner product as the target peer.

18. The method according to claim 15, wherein the selecting the target peer for performing data transmission with the peer according to the network mapping identifier comprises:

obtaining a candidate peer list; and

calculating a Euclidean distance between a network mapping identifier of each candidate peer having the same ISP identifier as the peer and the network mapping identifier of the peer, and selecting a candidate peer of a shortest Euclidean distance as the target peer.

19. A device for processing a network mapping identifier, the device comprising:

a first obtaining module, configured to obtain topology information of a network, wherein the topology information comprises a relation between nodes in the network;

an identifier generation module, configured to generate a network mapping identifier capable of indicating a relation between a peer and other peers in the network according to the topology information obtained by the first obtaining module; and

an allocation module, configured to allocate the generated network mapping identifier to the peer.

20. The device according to claim 19, wherein the identifier generation module is configured to generate a peer identifier capable of indicating a relation between each peer and other nodes in the network according to the topology information obtained by the first obtaining module, and use the peer identifier as the network mapping identifier;

or generate a peer identifier capable of indicating a relation between each peer and other peers in the network according to the topology information obtained by the first obtaining module, generate an Internet Service Provider (ISP) identifier, and combine the ISP identifier and the peer identifier into the network mapping identifier.

21. The device according to claim 20, wherein the identifier generation module is configured to generate a binary tree according to a relation between nodes in the topology information, mark a left edge between any two sibling nodes in the binary tree as 1, mark a right edge between any two sibling nodes in the binary tree as 0, and use binary numbers, 0s and 1s, from a treetop to each leaf node of the binary tree to form a binary code to generate a peer identifier of a node corresponding to the each leaf node;

or

generate a binary tree according to the relation between the nodes in the topology information, mark a left edge between any two sibling nodes in the binary tree as 0, mark a right edge between any two sibling nodes in the binary tree as 1, and use binary numbers, 0s and 1s, from a treetop to each leaf node of the binary tree to form a binary code to generate a peer identifier of a node corresponding to the each leaf node.

22. The device according to claim 20, wherein the identifier generation module is configured to obtain weight values between the nodes in the network according to the topology information to construct an n×

n matrix Q, wherein n is the number of the nodes, W_ij is an element in an i^th row and a j^th column in Q and is a weight value from an i^th node to a j^th node, and when i=j, W_ij is a value greater than or smaller than all weight values between the nodes, i,jε

[1,n];

decompose Q into Q1 and Q2, wherein a product of Q1 and Q2 is Q; and

extract elements in an i^th row in Q1, and using the elements in the i^th row in Q1 to form a source part of a multidimensional vector of the i^th node;

extract elements in an i^th row in Q2, and using the elements in the i^th row in Q2 to form a destination part of the multidimensional vector of the i^th node; and

combine the source part and the destination part into the multidimensional vector of the i^th node, and use the multidimensional vector as a peer identifier of the node.

23. The device according to claim 20, wherein the identifier generation module is configured to generate multidimensional coordinates of each peer according to the topology information, and use the multidimensional coordinates as a peer identifier of the peer.

24. A device for processing a network mapping identifier, the device comprising:

an obtaining module, configured to obtain a network mapping identifier of a peer, wherein the network mapping identifier is capable of indicating a relation between the peer and other peers in a network; and

a processing module, configured to select a target peer for performing data transmission with the peer according to the network mapping identifier.

25. The device according to claim 24, wherein the processing module is configured to obtain a candidate peer list;

and

perform exclusive-or operation on a network mapping identifier of each candidate peer having the same Internet Service Provider (ISP) identifier as the peer and the network mapping identifier of the peer, and select a candidate peer of a smallest exclusive-or operation result as the target peer.

26. The device according to claim 24, wherein the processing module is configured to obtain a candidate peer list;

and

calculate an inner product of a network mapping identifier of each candidate peer having the same ISP identifier as the peer and the network mapping identifier of the peer, and select a candidate peer of a smallest or greatest inner product as the target peer.

27. The device according to claim 24, wherein the processing module is configured to obtain a candidate peer list;

and

calculate a Euclidean distance between a network mapping identifier of each candidate peer having the same ISP identifier as the peer and the network mapping identifier of the peer, and select a candidate peer of a shortest Euclidean distance as the target peer.