METHOD AND SYSTEM FOR CREATING PEER-TO-PEER GEOGRAPHICAL ROUTING AND MULTI-ATTRIBUTE SIMILARITY ROUTING

• US 20130036236A1
• Filed: 08/01/2011
• Published: 02/07/2013
• Est. Priority Date: 08/01/2011
• Status: Abandoned Application

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Sun, Yu-An, Morales, Ramses
• Application Number:
  US13/195,358
• Publication Number:
  US 20130036236A1
• Time in Patent Office: Days
• US Class Current: 709/238
• CPC Class Codes: G06Q 30/0205 Location or geographical consideration
• CPC Class Codes: G06Q 30/0261 based on user location
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04W 4/02 Services making use of location information

Abstract

A system and method for creating a peer-to-peer geographical routing overlay network and a multi-attribute similarity routing overlay network. The geographical overlay network can be generated utilizing a geographical routing protocol to organize connections between one or more distributed micro-markets depending on a geographical location of each market and to detect a geographically close neighbor in a decentralized manner. The multi-attribute similarity overlay network can be computed by applying a filtering function based on a multi-attribute routing protocol defined over at least one attribute in order to enable decentralized clustering of the distributed micro-markets. The multi-attribute similarity protocol can be combined with the geographic overlay protocol to route messages to a target set of similarity-based attributes and a target geographic location thereby dynamically evolve a structure of distributed micro-markets over time and optimize a market interaction in the overlay network.

Claims

1. A method, comprising:

generating a geographical overlay network utilizing a geographical routing protocol to organize connections between a plurality of distributed micro-markets depending on a geographical location of each market and to detect a geographically close neighbor in a decentralized manner;

computing a multi-attribute similarity overlay network with respect to said plurality of distributed micro-markets by applying a filtering function based on a multi-attribute routing protocol defined over at least one attribute in order to enable decentralized clustering of said plurality of distributed micro-markets; and

combining said multi-attribute similarity protocol with said geographic overlay protocol to route a message to a target set of similarity-based attributes and a target geographic location thereby dynamically evolve a structure of said plurality of distributed micro-markets over time and optimize a market interaction in said overlay network.

2. The method of claim 1 wherein generating said geographical overlay network further comprises:

grouping a plurality of nodes that are geographically close utilizing a low-overhead protocol and simultaneously permitting each node to learn regarding a small number of nodes that are geographically close.

3. The method of claim 1 wherein said node possess at least one geographic location attribute and said message geographic location is set at creation time.

4. The method of claim 1 wherein said at least one geographic location attribute includes at least on of the following types of attributes:

a latitude and longitude of said node; and

x and y co-ordinate in a two-dimensional plane.

5. The method of claim 1 wherein generating said geographical overlay network further comprises:

computing a distance function in order to determine distance between at least two nodes and/or a node and a message;

routing said message tagged with said geographical location in such a way that said message can arrive to said market that is geographically close to said geographical location of said message; and

comparing said geographic location of said message to said geographic location of said node associated with said message and said geographic location of a neighbor of said node at each hop utilizing said distance function.

6. The method of claim 5 further comprising applying Harversine formula to determine said distance function if said geographic location is represented with said latitude and longitude attribute.

7. The method of claim 5 further comprising determining said distance function utilizing Euclidean distance between two points if said geographic location is represented with x and y coordinates in said plane.

8. The method of claim 1 further comprising stopping routing of said message if a current node is a closest node to said message and forwarding said message to said node if a neighbor of said node is close to said message.

9. The method of claim 1 wherein generating said geographical overlay network further comprises:

periodically gossiping said node location with respect to a plurality of close neighbors in association with a maximum and minimum distance from a close neighbor list wherein said receiving node determine if said node is a better neighbor for an originating node utilizing said node location and said maximum and minimum distance;

adding said originating node to said close neighbor list by said receiving node and potentially dropping another node from said list; and

periodically updating a not-close list by initiating a random walk utilizing at least one node from said list.

10. The method of claim 9 further comprising:

performing said random walk by said message that includes location of said originator node and distance to a furthest node in said close neighbor list; and

forwarding said message at each hop to a random neighbor chosen from among said plurality of neighbors that are at a further distance than the one contained in said message.

11. The method of claim 1 wherein generating said multi-attribute similarity overlay network further comprises:

maintaining said plurality of neighbor lists one for each market attribute in order to cluster similar market together; and

consulting an attribute neighbor list maintained by said similarity overlay network by said market if said market desires to transmit message to another market similar to itself with regards to an attribute.

12. The method of claim 1 further comprising combining said geographic overlay network with said similarity overlay network to permit said market transmit said message to any other market that is both similar to an originating market and close to a desired location.

13. The method of claim 1 wherein said filtering function comprises a Bloom filter.

14. The method of claim 1 further comprising connecting said plurality of distributed micro-markets is a peer-to-peer connection computing arrangement.

15. A system, comprising:

a processor;

a data bus coupled to said processor; and

a computer-usable medium embodying computer code, said computer-usable medium being coupled to said data bus, said computer program code comprising instructions executable by said processor and configured for;

generating a geographical overlay network utilizing a geographical routing protocol to organize connections between a plurality of distributed micro-markets depending on a geographical location of each market and to detect a geographically close neighbor in a decentralized manner;

computing a multi-attribute similarity overlay network with respect to said plurality of distributed micro-markets by applying a filtering function based on a multi-attribute routing protocol defined over at least one attribute in order to enable decentralized clustering of said plurality of distributed micro-markets; and

combining said multi-attribute similarity protocol with said geographic overlay protocol to route a message to a target set of similarity-based attributes and a target geographic location thereby dynamically evolve a structure of said plurality of distributed micro-markets over time and optimize a market interaction in said overlay network.

16. The system of claim 15 wherein said instructions are further configured for grouping a plurality of nodes that are geographically close utilizing a low-overhead protocol and simultaneously permitting each node to learn regarding a small number of nodes that are geographically close.

17. The system of claim 15 wherein said node possess at least one geographic location attribute and said message geographic location is set at creation time.

18. The system of claim 15 wherein said at least one geographic location attribute includes at least on of the following types of attributes:

a latitude and longitude of said node; and

x and y co-ordinate in a two-dimensional plane.

19. The system of claim 15 wherein said instructions are further configured for:

computing a distance function in order to determine distance between at least two nodes and/or a node and a message;

routing said message tagged with said geographical location in such a way that said message can arrive to said market that is geographically close to said geographical location of said message; and

comparing said geographic location of said message to said geographic location of said node associated with said message and said geographic location of a neighbor of said node at each hop utilizing said distance function.

20. A processor-readable medium storing code representing instructions to cause a processor to perform a process, said code comprising code to:

generate a geographical overlay network utilizing a geographical routing protocol to organize connections between a plurality of distributed micro-markets depending on a geographical location of each market and to detect a geographically close neighbor in a decentralized manner;

compute a multi-attribute similarity overlay network with respect to said plurality of distributed micro-markets by applying a filtering function based on a multi-attribute routing protocol defined over at least one attribute in order to enable decentralized clustering of said plurality of distributed micro-markets; and

combine said multi-attribute similarity protocol with said geographic overlay protocol to route a message to a target set of similarity-based attributes and a target geographic location thereby dynamically evolve a structure of said plurality of distributed micro-markets over time and optimize a market interaction in said overlay network.