Context-based routing in multi-hop networks

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.

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.