Characterizing achievable flow rates in multi-hop mesh networks with orthogonal channels
First Claim
1. A method of routing data from a source node to a destination node in a multi-hop network of nodes interconnected by links, comprising:
- (a) determining that a link-flow vector satisfies one or more necessary scheduling conditions for achievability, wherein the link-flow vector represents a set of flows to be routed on one or more links from the source node to the destination node;
(b) generating a scheduling multi-graph for the network, wherein the scheduling multi-graph comprises a graph having at least one pair of nodes with multiple edges therebetween;
(c) deriving one or more sufficient scheduling conditions for achievability of the link-flow vector;
(d) solving a linear optimization problem over the one or more necessary scheduling conditions to obtain an upper bound on the achievability of the link-flow vector;
(e) generating, based on the scheduling multi-graph, a solution comprising a set of routes and an associated schedule for achieving the link-flow vector, the solution being a lower bound on the achievability of the link-flow vector; and
(f) implementing a routing method using the set of routes and the associated schedule to route the link-flow vector from the source node to the destination node;
wherein at least one node v of the network is adapted to receive transmissions from a specified plurality Ω
(v) of other nodes, and at least one of the scheduling conditions depends on Ω
(v).
10 Assignments
0 Petitions
Accused Products
Abstract
A method of routing data from a source node to a destination node in a multi-hop network of nodes interconnected by links comprises: (a) determining that a link-flow vector satisfies one or more necessary scheduling conditions for achievability, wherein the link-flow vector represents a set of flows to be routed on one or more links from the source node to the destination node; (b) generating a scheduling multi-graph for the network, wherein the scheduling multi-graph comprises a graph having at least one pair of nodes with multiple edges therebetween; (c) deriving one or more sufficient scheduling conditions for achievability of the link-flow vector by edge-coloring the scheduling multi-graph; (d) solving a linear optimization problem over the one or more necessary scheduling conditions to obtain an upper bound on the achievability of the link-flow vector; (e) generating, based on the scheduling multi-graph, a solution comprising a set of routes and an associated schedule for achieving the link-flow vector, the solution being a lower bound on the achievability of the link-flow vector; and (f) implementing a routing method using the set of routes and the associated schedule to route the link-flow vector from the source node to the destination node. At least one node v of the network is adapted to receive transmissions from a specified plurality Ω(v) of other nodes, and at least one of the scheduling conditions depends on Ω(v).
-
Citations
44 Claims
-
1. A method of routing data from a source node to a destination node in a multi-hop network of nodes interconnected by links, comprising:
-
(a) determining that a link-flow vector satisfies one or more necessary scheduling conditions for achievability, wherein the link-flow vector represents a set of flows to be routed on one or more links from the source node to the destination node;
(b) generating a scheduling multi-graph for the network, wherein the scheduling multi-graph comprises a graph having at least one pair of nodes with multiple edges therebetween;
(c) deriving one or more sufficient scheduling conditions for achievability of the link-flow vector;
(d) solving a linear optimization problem over the one or more necessary scheduling conditions to obtain an upper bound on the achievability of the link-flow vector;
(e) generating, based on the scheduling multi-graph, a solution comprising a set of routes and an associated schedule for achieving the link-flow vector, the solution being a lower bound on the achievability of the link-flow vector; and
(f) implementing a routing method using the set of routes and the associated schedule to route the link-flow vector from the source node to the destination node;
wherein at least one node v of the network is adapted to receive transmissions from a specified plurality Ω
(v) of other nodes, and at least one of the scheduling conditions depends on Ω
(v). - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)
-
-
16. A multi-hop network of nodes interconnected by links, wherein the network comprises an apparatus for routing data from a source node to a destination node, the apparatus adapted to:
-
(a) determine that a link-flow vector satisfies one or more necessary scheduling conditions for achievability, wherein the link-flow vector represents a set of flows to be routed on one or more links from the source node to the destination node;
(b) generate a scheduling multi-graph for the network, wherein the scheduling multi-graph comprises a graph having at least one pair of nodes with multiple edges therebetween;
(c) derive one or more sufficient scheduling conditions for achievability of the link-flow vector;
(d) solve a linear optimization problem over the one or more necessary scheduling conditions to obtain an upper bound on the achievability of the link-flow vector;
(e) generate, based on the scheduling multi-graph, a solution comprising a set of routes and an associated schedule for achieving the link-flow vector, the solution being a lower bound on the achievability of the link-flow vector; and
(f) implement a routing method using the set of routes and the associated schedule to route the link-flow vector from the source node to the destination node;
wherein at least one node v of the network is adapted to receive transmissions from a specified plurality Ω
(v) of other nodes, and at least one of the scheduling conditions depends on Ω
(v). - View Dependent Claims (17, 18, 19, 20, 21)
-
-
22. Apparatus for routing data from a source node to a destination node in a multi-hop network of nodes interconnected by links, the apparatus adapted to:
-
(a) determine that a link-flow vector satisfies one or more necessary scheduling conditions for achievability, wherein the link-flow vector represents a set of flows to be routed on one or more links from the source node to the destination node;
(b) generate a scheduling multi-graph for the network, wherein the scheduling multi-graph comprises a graph having at least one pair of nodes with multiple edges therebetween;
(c) derive one or more sufficient scheduling conditions for achievability of the link-flow vector;
(d) solve a linear optimization problem over the one or more necessary scheduling conditions to obtain an upper bound on the achievability of the link-flow vector;
(e) generate, based on the scheduling multi-graph, a solution comprising a set of routes and an associated schedule for achieving the link-flow vector, the solution being a lower bound on the achievability of the link-flow vector; and
(f) implement a routing method using the set of routes and the associated schedule to route the link-flow vector from the source node to the destination node;
wherein at least one node v of the network is adapted to receive transmissions from a specified plurality Ω
(v) of other nodes, and at least one of the scheduling conditions depends on Ω
(v).
-
-
23. A method of routing data from a source node to a destination node in a multi-hop network of nodes interconnected by links, comprising:
-
(a) determining that a link-flow vector satisfies one or more necessary scheduling conditions for achievability, wherein the link-flow vector represents a set of flows to be routed on one or more links from the source node to the destination node;
(b) generating a scheduling multi-graph for the network, wherein the scheduling multi-graph comprises a graph having at least one pair of nodes with multiple edges therebetween;
(c) deriving one or more sufficient scheduling conditions for achievability of the link-flow vector;
(d) solving a linear optimization problem over the one or more necessary scheduling conditions to obtain an upper bound on the achievability of the link-flow vector;
(e) generating, based on the scheduling multi-graph, a solution comprising a set of routes and an associated schedule for achieving the link-flow vector, the solution being a lower bound on the achievability of the link-flow vector; and
(f) implementing a routing method using the set of routes and the associated schedule to route the link-flow vector from the source node to the destination node;
wherein at least one node v of the network is adapted to transmit and receive in the same time slot, and at least one of the scheduling conditions depends on (i) a set of links Nin(v) terminating at node v and (ii) a set of links Nout(v) emanating from node v. - View Dependent Claims (24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37)
-
-
38. A multi-hop network of nodes interconnected by links, wherein the network comprises an apparatus for routing data from a source node to a destination node, the apparatus adapted to:
-
(a) determine that a link-flow vector satisfies one or more necessary scheduling conditions for achievability, wherein the link-flow vector represents a set of flows to be routed on one or more links from the source node to the destination node;
(b) generate a scheduling multi-graph for the network, wherein the scheduling multi-graph comprises a graph having at least one pair of nodes with multiple edges therebetween;
(c) derive one or more sufficient scheduling conditions for achievability of the link-flow vector;
(d) solve a linear optimization problem over the one or more necessary scheduling conditions to obtain an upper bound on the achievability of the link-flow vector;
(e) generate, based on the scheduling multi-graph, a solution comprising a set of routes and an associated schedule for achieving the link-flow vector, the solution being a lower bound on the achievability of the link-flow vector; and
(f) implement a routing method using the set of routes and the associated schedule to route the link-flow vector from the source node to the destination node;
wherein at least one node v of the network is adapted to transmit and receive in the same time slot, and at least one of the scheduling conditions depends on (i) a set of links Nin(v) terminating at node v and (ii) a set of links Nout(v) emanating from node v. - View Dependent Claims (39, 40, 41, 42, 43)
-
-
44. Apparatus for routing data from a source node to a destination node in a multi-hop network of nodes interconnected by links, the apparatus adapted to:
-
(a) determine that a link-flow vector satisfies one or more necessary scheduling conditions for achievability, wherein the link-flow vector represents a set of flows to be routed on one or more links from the source node to the destination node;
(b) generate a scheduling multi-graph for the network, wherein the scheduling multi-graph comprises a graph having at least one pair of nodes with multiple edges therebetween;
(c) derive one or more sufficient scheduling conditions for achievability of the link-flow vector;
(d) solve a linear optimization problem over the one or more necessary scheduling conditions to obtain an upper bound on the achievability of the link-flow vector;
(e) generate, based on the scheduling multi-graph, a solution comprising a set of routes and an associated schedule for achieving the link-flow vector, the solution being a lower bound on the achievability of the link-flow vector; and
(f) implement a routing method using the set of routes and the associated schedule to route the link-flow vector from the source node to the destination node;
wherein at least one node v of the network is adapted to transmit and receive in the same time slot, and at least one of the scheduling conditions depends on (i) a set of links Nin(v) terminating at node v and (ii) a set of links Nout(v) emanating from node v.
-
Specification