Patent Document ID: 7660315
Application ID: 11194748
Patent Flag: 1

Claim One:
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 receives transmissions from a specified plurality Ω(v) of other nodes, and at least one of the scheduling conditions depends on Ω(v); the linear optimization problem is solved as a concurrent flow problem; the linear optimization problem is solved using a primal-dual algorithm that alternates between (i) sending the data along shortest path pairs and (ii) adjusting the length of links along which the data has been sent until an optimum solution is reached; N in (v) represents a set of all incoming links at node v in the network; N out (v) represents a set of all outgoing links at node v in the network; k represents a set of all paths P for a source-destination pair k from s(k) to d(k); x(P) represents an amount of flow sent on path P; a rate vector r having K components represents traffic demand for a plurality of different source-destination node pairs (s(k),d(k)) for a commodity k=1, 2,. .. K, with a desired flow rate r(k) between s(k) and d(k); c(e) represents capacity of a link e in the network; t(e) represents a transmitting node at one end of link e; r(e) represents a receiving node at the other end of link e; η(v) represents a weight of node v; z(k) is an intermediate variable assigned to each commodity k=1, 2,. .. K; λ is a scaling factor of the network; V″ represents a set of nodes consisting of all full-duplex nodes in the network; V′ represents a set of nodes consisting of all half-duplex nodes in the network; Q out ⁡ ( v , x ) ⁢ ⁢ is ⁢ ⁢ defined ⁢ ⁢ as ⁢ ∑ e ∈ N out ⁡ ( v ) ⁢ ∑ k ⁢ ∑ P ∈ 𝒫 k ⁢ : ⁢ e ∈ P ⁢ x ⁡ ( P ) c ⁡ ( e ) ; Q in ⁡ ( v , x ) ⁢ ⁢ is ⁢ ⁢ defined ⁢ ⁢ as ⁢ ∑ e ∈ N in ⁡ ( v ) ⁢ ∑ k ⁢ ∑ p ∈ 𝒫 k ⁢ : ⁢ e ∈ P ⁢ x ⁡ ( P ) Ω ⁡ ( v ) ⁢ c ⁡ ( e ) ; and a primal formulation is: maximize λ, subject to Q out ⁡ ( v , x ) + Q in ⁡ ( v , x ) ≤ 1 , ∀ v ∈ V ′ , ⁢ Q out ⁡ ( v , x ) ≤ 1 , ∀ v ∈ V ″ Q in ⁡ ( v , x ) ≤ 1 , ∀ v ∈ V ″ ∑ P ∈ 𝒫 k ⁢ x ⁡ ( P ) = λ ⁢ ⁢ r ⁡ ( k ) , ∀ k = 1 , 2 , … ⁢ , K , ⁢ x ⁡ ( P ) ≥ 0 , ∀ P ∈ 𝒫 k , ∀ k .