OPTIMIZATION SCHEME FOR ROUTING BASED ON DATA LATENCY

• US 20070263590A1
• Filed: 04/25/2006
• Published: 11/15/2007
• Est. Priority Date: 04/25/2006
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Abileah, Shahaf, Couckuyt, Jeffrey
• Application Number:
  US11/380,167
• Publication Number:
  US 20070263590A1
• Time in Patent Office: Days
• US Class Current: 370/351
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/12 Shortest path evaluation

Abstract

The subject disclosure pertains to systems and methods for optimizing generation of routes within a topology by providing for latency during data retrieval. Frequently, topologies are maintained in multiple data stores, such as cache, local data stores and remote data stores. Delays due to latency in retrieving data from the various data stores can be mitigated by immediately processing available edge data rather than waiting for requested edge data to become available. A list can be provided for tracking edges that have been partially processed. As topology data from data stores with slower data retrieval rates is received, additional edges become available for processing and the list of partially processed edges can be updated.

Claims

1. A system for facilitating the generation of a route of edges that connects a first node and a second node within a topology while mitigating latency in data retrieval, comprising:

a processing order component that receives at least one block of topology data and determines an edge processing order based at least in part upon latency in receiving topology data;

an edge processor component that processes at least one edge included in the block of topology data; and

a route generator component that generates a route of edges based at least in part upon the processed edge.

2. The system of claim 1, the processing order component maintains a set of partially processed edges and a set of edges to be processed.

3. The system of claim 1, further comprising:

a termination component that determines when a termination condition is met and concludes route generation based at least in part upon whether the termination condition is met.

4. The system of claim 3, the termination condition includes a time limit.

5. The system of claim 3, the termination condition includes a route quality threshold.

6. The system of claim 1, further comprising:

an input component that receives input specifying the first node and the second node; and

an output component that provides the route of edges to an interface component.

7. The system of claim 1, the topology is organized using at least one of a quad tree scheme and a R-tree scheme.

8. The system of claim 1, the at least one block of topology data is obtained from at least one of a remote data store and a local data store.

9. The system of claim 1, further comprising:

an interface component that provides a user interface to the route generator component, the interface component is accessible using a mobile device.

10. A method for facilitating generation of a path of edges connecting a first node and a second node within a graph while providing for delays in data retrieval, comprising:

requesting at least one block of graph data;

receiving at least one block, the at least one block includes at least one edge;

processing the at least one edge, order of edge processing is based at least in part on a retrieval rate associated with the at least one block; and

determining the path of edges based at least in part upon the processed edge.

11. The method of claim 10, further comprising:

maintaining a first set of edges for which data has been requested, but not received;

maintaining a second set of edges available for processing; and

removing the at least one edge from the first set when the requested data is received.

12. The method of claim 10, further comprising:

pre-fetching the at least one edge based upon an inference regarding the likelihood that the edge will be processed in the near future.

13. The method of claim 10, further comprising:

halting edge processing based at least in part upon a predetermined time limit.

14. The method of claim 10, further comprising:

halting edge processing based at least in part upon a predetermined time limit after generation of a possible path.

15. The method of claim 10, edge processing, further comprises:

determining a cost for the at least one edge, the cost is based at least in part upon a user preference, the path is determined based at least in part upon the cost of the at least one edge.

16. The method of claim of claim 10, the graph represents geographic data and the first node and second node represent geographic locations.

17. A system for facilitating generation of a route connecting a first node and a second node within a graph, comprising:

means for retrieving a block of graph data that includes at least one edge;

means for processing edges, edge processing order is based at least in part upon data latency in retrieval of the block of graph data; and

means for generating the route based upon the processed edges.

18. The system of claim 17, further comprising:

means for maintaining a first set indicating edges that are partially processed; and

means for maintaining a second set indicating edges that are to be processed.

19. The system of claim 17, further comprising:

means for pre-fetching a block of graph data.

20. The system of claim 17, further comprising:

means for terminating route generation conditioned at least in part on a predetermined time limit.