Context-based routing in multi-hop networks

• US 7,693,939 B2
• Filed: 05/07/2007
• Issued: 04/06/2010
• Est. Priority Date: 05/07/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Das, Saumitra M., Wu, Yunnan, Chandra, Ranveer, Florencio, Dinei
• Primary Examiner(s): NGUYEN, THANH T
• Application Number:
  US11/745,340
• Publication Number:
  US 20080279101A1
• Time in Patent Office: 1,065 Days
• Field of Search: 709/203, 709/239, 709/241, 709/242, 370/238, 370/400, 370/351
• US Class Current: 709/203
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04L 45/124 using a combination of metrics
• CPC Class Codes: H04L 45/125 based on throughput or bandwidth
• CPC Class Codes: H04W 40/16 based on interference
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

Context-based routing in multi-hop networks involves using a context-based routing metric. In a described implementation, respective path values are calculated for respective ones of multiple paths using the context-based routing metric. A path is selected from the multiple paths responsive to the calculated path values. Data is transmitted over at least one link of the selected path. In an example embodiment, the context-based routing metric is ascertained responsive to an estimated service interval (ESI) of a bottleneck link of each path of the multiple paths. In another example embodiment, the context-based routing metric is ascertained responsive to an expected resource consumption (ERC) metric. In an example embodiment of path selection, the path is selected using a context-based path pruning (CPP) technique that involves maintaining multiple local contexts at each intermediate node, with each local context representing at least one partial path.

Claims

1. A method for a network node, the method comprising:

ascertaining a routing metric responsive to an estimated service interval (ESI) of a bottleneck link of each path of multiple paths, wherein the ESI for a particular link of a given path is determined responsive to (i) an expected transmission time (ETT) of the particular link and (ii) a weighted sum of one or more ETTs of selected previous links along the given path in which a previous link is selected if the previous link interferes with the particular link;

calculating respective path values for respective paths of the multiple paths using the ascertained routing metric;

selecting a path from the multiple paths responsive to the calculated path values; and

transmitting data over at least one link of the selected path.

2. The method as recited in claim 1, wherein the routing metric comprises a self-interference aware routing metric (SIM).

3. The method as recited in claim 1, wherein the selecting comprises:

selecting the path from the multiple paths responsive to the calculated path values using a context-based path pruning (CPP) technique that involves maintaining a set of partial paths that reach one or more intermediate nodes as the partial paths are extended link-by-link toward a destination node.

4. The method as recited in claim 1, wherein the selecting comprises:

selecting the path from the multiple paths responsive to the calculated path values using a context-based path pruning (CPP) technique that involves a context-expanded graph with local contexts defined by a predetermined number of previous hops.

5. A method for a network node, the method comprising:

ascertaining a context-based routing metric that cannot be decomposed into a sum of terms, with each term determined by a local context at a node and a link adjacent to the node, wherein the ascertaining further comprises;

ascertaining the context-based routing metric responsive to an estimated service interval (ESI) of a bottleneck link of each path of multiple paths, wherein the ESI for a particular link of a given path is determined responsive to (i) an expected transmission time (ETT) of the particular link and (ii) a weighted sum of one or more ETTs of selected previous links along the given path in which a previous link is selected if the previous link interferes with the particular link;

calculating respective path values for respective paths of the multiple paths using the ascertained context-based routing metric;

selecting a path from the multiple paths responsive to the calculated path values using a context-based path pruning (CPP) technique that involves maintaining multiple local contexts at each of one or more intermediate nodes and examining partial paths starting from a source node or ending at a destination node using the multiple local contexts; and

transmitting data over at least one link of the selected path.

6. The method as recited in claim 5, wherein the multiple local contexts at a given intermediate node are defined using a predetermined number of previous links or nodes along multiple partial paths reaching the given intermediate node.

7. The method as recited in claim 5, wherein the calculating and selecting comprise:

reconstructing at least one path from at least one source node to an intermediate node; and

updating the context-based routing metric for a particular local context responsive to a path value calculated on a path extending from the at least one source node to a neighbor node of the intermediate node along the reconstructed path.

8. The method as recited in claim 5, wherein the calculating and selecting comprise:

creating a context-expanded graph with local contexts, wherein for each of one or more physical nodes the creating comprises;

introducing one vertex for each local context that is applicable to the physical node; and

interconnecting vertices according to an original network connectivity.

9. The method as recited in claim 8, wherein the context-expanded graph comprises a reverse context-expanded graph.

10. The method as recited in claim 5, wherein the calculating and selecting comprise:

extending at least one path of the multiple paths by a link to create a valid extended path;

ascertaining a local context of the valid extended path;

determining if an identified path that has already been checked is associated with a local context that is equivalent to the ascertained local context;

if the identified path is associated with the local context that is equivalent to the ascertained local context, determining if a cost of the valid extended path is less than the identified path; and

if the cost of the valid extended path is less than the identified path, replacing the identified path with the valid extended path.

11. The method as recited in claim 5, wherein the calculating and selecting are performed via a distributed algorithm in which nodes exchange lists of estimated minimum cost paths to reach each destination for each applicable outgoing context.

12. The method as recited in claim 5, wherein the calculating and selecting are performed via a distributed algorithm in which (i) source nodes broadcast route requests and intermediate nodes forward route requests after appending their address and link costs and (ii) when a node receives a request it has already forwarded, it forwards the request again if a path cost to a neighbor is better than a best cost it has previously forwarded with the same local context.

13. A method for a network node, the method comprising:

determining an estimated service interval (ESI) for a particular link of a given path responsive to (i) an expected transmission time (ETT) of the particular link and (ii) a weighted sum of one or more ETTs of selected previous links along the given path in which a previous link is selected if the previous link interferes with the particular link;

determining at least one conditional link cost in dependence on a local mixing opportunity;

calculating multiple respective path costs for respective ones of multiple paths responsive to one or more conditional link costs determined in dependence on at least one local mixing opportunity;

selecting a path from the multiple paths responsive to the calculated path costs; and

transmitting data from the network node over at least one link of the selected path.

14. The method as recited in claim 13, wherein the calculating comprises:

creating a dot graph representation of a network in which wires interconnect dots to reflect conditional link costs that are reduced based on a potential local mixing opportunity; and

applying a shortest path algorithm over the dot graph representation.

15. The method as recited in claim 13, wherein determining at least one conditional link cost comprises:

ascertaining an expected resource consumption (ERC) metric responsive to (i) a resource total consumed by a particular number of packets sent within a given time period and (ii) the particular number of packets sent within the given time period.

16. The method as recited in claim 13, wherein determining at least one conditional link cost comprises:

ascertaining a marginal expected resource consumption (ERC) metric as an estimate of an ERC value if an additional amount of new traffic is added to a particular wire e_ij→

e_jk of a dot graph representation.

17. The method as recited in claim 13, wherein determining at least one conditional link cost comprises:

assessing individual resource consumption of an individual packet, which is transmitted as part of a mixture packet, as a fraction of a total resource consumption of the mixture packet.