Minimum-cost routing with network coding

• US 7,414,978 B2
• Filed: 12/30/2004
• Issued: 08/19/2008
• Est. Priority Date: 12/30/2004
• Status: Active Grant

• Current Assignee: Board of Trustees of The University of Illinois, Massachusetts Institute of Technology
• Original Assignee: Massachusetts Institute of Technology
• Inventors: Lun, Desmond S., Medard, Muriel, Ho, Tracey, Koetter, Ralf, Ratnakar, Niranjan
• Primary Examiner(s): Ngo, Ricky
• Assistant Examiner(s): Samuel, DeWanda
• Application Number:
  US11/027,889
• Publication Number:
  US 20060146716A1
• Time in Patent Office: 1,328 Days
• Field of Search: 370/238, 370/390, 370/396, 709/232
• US Class Current: 370/238
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/124 using a combination of metrics

Abstract

A method and computer program product for performing minimum cost routing with network coding is presented. The method and system model a network as a directed graph. A cost per unit flow is associated with each link of the directed graph. A link capacity is associated with each link of the directed graph. A network code is then computed that sets up a routing connection that achieves an optimal cost using the cost per unit flow for each link of the directed graph and using the link capacity for each link of the directed graph.

Claims

1. A method of providing minimum cost routing with network coding comprising:

modeling a network as a directed graph represented by the formula G =(N,A) wherein N is the set of nodes of the network and A is the set of links of the network;

associating a cost per unit flow for each link of said directed graph;

associating a link capacity for each link of said directed graph; and

computing a network code that sets up a routing connection that achieves an optimal cost using said cost per unit flow for each link of said directed graph and using said link capacity for each link of said directed graph, wherein said computing a network code is done in accordance with the formula;

$\underset{\left(i,j\right)<br><br>\in <br><br>A}{\sum <br><br>}<br><br>a_{\mathrm{ij}}<br><br>z_{\mathrm{ij}}$

wherein (i,j) is a link and are elements of the directed graph G, a_ij is the cost per unit flow, c_ij is the capacity of the link, and z is a flow capacity vector, and wherein said computing a network code sets up a multicast connection in said direction graph G at a rate approximately equal to R from source s to terminals in the set T that puts a flow approximately equal to z_ij on each link (i,j).

2. The method of claim 1 wherein said network includes at least one single multicast connection.

3. The method of claim 1 wherein z_ij is subject to the condition:

$\begin{array}{cc}{z}_{\mathrm{ij}}\ge <br><br>x_{\mathrm{ij}}^{\left(t\right)},\_<br><br>\forall <br><br><br><br>\left(i,j\right)\in <br><br>A,t\in <br><br>T<br><br>& \forall <br><br>\left(i,j\right)\in <br><br>A,t\in <br><br>T,\\ \begin{array}{c}\underset{\left\{j|\left(i,j\right)<br><br>\in <br><br>A\right\}}{\sum <br><br>}<br><br>x_{\mathrm{ji}}^{\left(t\right)}-\\ \underset{\left\{j|\left(j,i\right)<br><br>\in <br><br>A\right\}}{\sum <br><br>}<br><br>x_{\mathrm{ji}}^{\left(t\right)}\end{array}=\{\begin{array}{cc}R& \mathrm{if}<br><br><br><br>i=s,\\ -R& \mathrm{if}<br><br><br><br>i=t,\forall <br><br>i\in <br><br>N,t\in <br><br>T,\\ 0& \mathrm{otherwise},\end{array}& \\ c_{\mathrm{ij}}\ge <br><br>x_{\mathrm{ij}}^{\left(t\right)}\ge <br><br>0,& <br><br>\forall <br><br>\left(i,j\right)\in <br><br>A,t\in <br><br>T.\end{array}$

wherein ∀

(ij) ε

A, t ε

T wherein t is a node in the set of destination nodes T.

4. The method of claim 1 wherein z_ij is a convex cost function, subject to the condition:

$\begin{array}{cc}{z}_{\mathrm{ij}}=\underset{i\in <br><br>T}{\max }<br><br><br><br>x_{\mathrm{ij}}^{\left(t\right)},<br><br>& \forall <br><br>\left(i,j\right)\in <br><br>A,\\ \underset{\left\{j|\left(i,j\right)<br><br>\in <br><br>A\right\}}{\sum <br><br>}<br><br>x_{\mathrm{ij}}^{\left(t\right)}-\underset{\left\{j|\left(j,i\right)<br><br>\in <br><br>A\right\}}{\sum <br><br>}<br><br>x_{\mathrm{ji}}^{\left(t\right)}={\mathrm{\sigma <br><br>}}_i^{\left(t\right)},<br><br>& \forall <br><br>i\in <br><br>N,t\in <br><br>T,\\ x_{\mathrm{ij}}^{\left(t\right)}\ge <br><br>0,& <br><br>\forall <br><br>\left(i,j\right)\in <br><br>A,t\in <br><br>T.\end{array}$

wherein ∀

(ij) ε

A, t ε

T, and wherein t is a node in the set of destination nodes T.

5. The method of claim 1 wherein said network comprises a wireless multicast network and wherein the cost function is modified to reflect a wireless multicast advantage.

6. The method of claim 5 wherein said network code is subject to

$\begin{array}{c}\sum _{}\end{array}$

{ k | ( i , k ) ⁢

∈

A , >

( i , j ) _ } ⁢

( ⁢

z ik - x ik ( t ) ≥

0 , ∀

( i , j ) ∈

A , t ∈

T , ∑

{ j | ( i , j ) ⁢

∈

A } ⁢

x ij ( t ) - ∑

{ j | ( j , i ) ⁢

∈

A } ⁢

x ji ( t ) = { R if ⁢

⁢

i = s , - R if ⁢

⁢

i = t , ∀

i ∈

N , t ∈

T , 0 otherwise , c ij ≥

x ij ( t ) ≥

0 , ∀

( i , j ) ∈

A , t ∈

T , .

7. The method of claim 1 wherein said network comprises a multiple multicast network having multiple source processes at multiple rates.

8. The method of claim 7 wherein said network code is subject to

$\begin{array}{c}{c}_{\mathrm{ij}}\ge \end{array}$

z ij = ∑

C ∈

C ⁢

⁢

( j ) ⁢

⁢

y ij ( C ) ∀

⁢

( i , j ) ⁢

∈

A , y ij ( C ) ≥

∑

m ∈

C ⁢

⁢

x ij ( t , m ) ∀

⁢

( i , j ) ⁢

∈

A , t ∈

T , C ∈

C ⁢

⁢

( j ) x ij ( t , m ) ≥

0 ∀

⁢

( i , j ) ⁢

∈

A , t ∈

T , m = 1 , …

⁢

, M , $\begin{array}{c}\underset{\left\{j|\left(i,j\right)<br><br>\in <br><br>A\right\}}{\sum <br><br>}<br><br>x_{\mathrm{ij}}^{\left(t,m\right)}-\\ \underset{\left\{j|\left(j,i\right)<br><br>\in <br><br>A\right\}}{\sum <br><br>}<br><br>x_{\mathrm{ji}}^{\left(t,m\right)}\end{array}=\{\begin{array}{cc}{R}_m& \mathrm{if}<br><br><br><br>v=s_m<br><br><br><br>\mathrm{and}<br><br><br><br>m\in <br><br>D<br><br><br><br>\left(t\right),\\ -R_m& \mathrm{if}<br><br><br><br>m\in <br><br>D<br><br><br><br>\left(i\right),\\ 0& \mathrm{otherwise},\end{array}<br><br><br><br>\forall <br><br>i\in <br><br>A,t\in <br><br>T,m=1,\mathrm{\dots <br><br>}<br><br>,M.$

9. The method of claim 8 wherein said network code sets up multicast connections for m=1, . . . , M at a rate approximately equal to R_m from source s_m to terminals in the set {t ε

T|m ε

D(t) that puts a flow approximately equal to z_ij on each link (i,j).

10. The method of claim 1 further comprising associating a utility function U_r(R) with each connection that has the same units as the cost function, said utility function subject to

$\sum _{}^{}$

{ j ⁢



( i , j ) ∈

A } ⁢

x ij ( t ) - ∑

{ j ⁢



( j , i ) ∈

A } ⁢

x ji ( t ) = σ

i ( t ) , ⁢

∀

i ⁢

∈

⁢

N ⁢

\ ⁢

{ t } , t ⁢

∈

⁢

T , R ≥

0 ⁢

( , ⁢

x ij ( t ) ≥

0 , ∀

( i , j ) ∈

⁢

A , t ∈

T .

11. The method of claim 10 wherein said utility function is determined in accordance with the formula:

$U<br><br>\left(x,R\right)<br><br>\text{;<br><br>}=U_r<br><br>\left(R\right)-\underset{\left(i,j\right)\in <br><br>A}{\overset{}{\sum <br><br>}}<br><br>f_{\mathrm{ij}}^{}<br><br>\left(z_{\mathrm{ij}}^{\mathrm{\prime <br><br>}}\right).$

12. A computer readable storage medium having encoded computer readable code thereon for providing minimum cost routing with network coding, the medium comprising:

instructions for modeling a network as a directed graph represented by the formula G=(N,A) wherein N is the set of nodes of the network and A is the set of links of the network;

instructions for associating a cost per unit flow for each link of said directed graph;

instructions for associating a link capacity for each link of said directed graph; and

instructions for computing a network code that sets up a routing connection that achieves an optimal cost using said cost per unit flow for each link of said directed graph and using said link capacity for each link of said directed graph, wherein said computing a network code is done in accordance with the formula;

$\underset{\left(i,j\right)\in <br><br>A}{\overset{}{\sum <br><br>}}<br><br>a_{\mathrm{ij}}<br><br>z_{\mathrm{ij}}$

wherein (i,j) is a link and are elements of the directed graph G, a_ij is the cost per unit flow, c_ij is the capacity of the link, and z is a flow capacity vector, and wherein said computing a network code sets up a multicast connection in said direction graph G at a rate approximately equal to R from source s to terminals in the set T that puts a flow approximately equal to z_ij on each link (i,j).

13. The computer readable storage medium of claim 12 wherein said instructions for modeling a network comprises instructions for modeling a network including at least one single multicast connection.

14. The computer readable storage medium of claim 12 wherein said instructions for putting flow on each link further comprises instructions for putting flow z_ij on each link is subject to the condition:

$z_{\mathrm{ij}}\ge <br><br>x_{\mathrm{ij}}^{\left(t\right)},\_<br><br>\forall <br><br>\left(i,j\right)\in <br><br>A,t\in <br><br>T<br><br><br><br>\forall <br><br>\left(i,j\right)\in <br><br>A,t\in <br><br>T,<br><br>\underset{\{j<br><br><br><br>\left(i,j\right)\in <br><br>A\}<br><br>}{\overset{}{\sum <br><br>}}<br><br>x_{\mathrm{ji}}^{\left(t\right)}-\underset{\{j<br><br><br><br>\left(j,i\right)\in <br><br>A\}<br><br>}{\overset{}{\sum <br><br>}}<br><br>x_{\mathrm{ji}}^{\left(t\right)}=\{\begin{array}{cc}R& \mathrm{if}<br><br><br><br>i=s,\\ -R& \mathrm{if}<br><br><br><br>i=t,\forall <br><br>i\in <br><br>N,t\in <br><br>T,\\ 0& \mathrm{otherwise},\end{array}<br><br><br><br>c_{\mathrm{ij}}\ge <br><br>x_{\mathrm{ij}}^{\left(t\right)}\ge <br><br>0,<br><br>\forall <br><br>\left(i,j\right)\in <br><br>A,t\in <br><br>T.$

wherein ∀

(ij) ε

A, t ε

T wherein t is a node in the set of destination nodes T.

15. The computer readable storage medium of claim 12 instructions for putting flow on each link further comprises instructions for putting flow z_ij on each link wherein the cost function is a convex, subject to the condition:

$z_{\mathrm{ij}}=\underset{i\in <br><br>T}{\max }<br><br>x_{\mathrm{ij}}^{\left(t\right)},<br><br>\forall <br><br>\left(i,j\right)\in <br><br>A,<br><br>\underset{\{j<br><br><br><br>\left(i,j\right)\in <br><br>A\}<br><br>}{\overset{}{\sum <br><br>}}<br><br>x_{\mathrm{ij}}^{\left(t\right)}-\underset{\{j<br><br><br><br>\left(j,i\right)\in <br><br>A\}<br><br>}{\overset{}{\sum <br><br>}}<br><br>x_{\mathrm{ji}}^{\left(t\right)}={\mathrm{\sigma <br><br>}}_i^{\left(t\right)},<br><br>\forall <br><br>i\in <br><br><br><br>N,t<br><br><br><br>\mathrm{\varepsilon <br><br>}<br><br><br><br>T<br><br>,<br><br>x_{\mathrm{ij}}^{\left(t\right)}\ge <br><br>0,<br><br>\forall <br><br>\left(i,j\right)<br><br>\in <br><br>A,t<br><br>\in <br><br><br><br>T.$

wherein ∀

(ij) ε

A, t ε

T, and wherein t is a node in the set of destination nodes T.

16. The computer readable storage medium of claim 12 wherein said network comprises a wireless multicast network and wherein the instructions for associating a cost per unit flow for each link includes instructions to reflect a wireless multicast advantage.

17. The computer readable storage medium of claim 16 wherein said instructions for computing a network code is subject to

$\sum _{}^{}$

{ k ⁢



( i , k ) ∈

A , ≻

( i , j ) } _ ⁢

( ⁢

z ik - x ik ( t ) ≥

0 , ⁢

∀

( i , j ) ∈

A , t ∈

T , ⁢

∑

{ j ⁢



( i , j ) ∈

A } ⁢

⁢

x ij ( t ) - ∑

{ j ⁢



( j , i ) ∈

A } ⁢

⁢

x ji ( t ) = { R ⁢

if ⁢

⁢

i = s , - R ⁢

if ⁢

⁢

i = t , ∀

i ∈

N , t ∈

T , 0 ⁢

otherwise , ⁢

⁢

c ij ≥

x ij ( t ) ≥

0 , ⁢

∀

( i , j ) ∈

A , t ∈

T , .

18. The computer readable storage medium of claim 12 wherein said network comprises a multiple multicast network having multiple source processes at multiple rates.

19. The computer readable storage medium of claim 14 wherein said instructions for computing a network code is subject to

$c_{\mathrm{ij}}\ge$

z ij = ∑

C ∈

C ⁡

( j ) ⁢

y ij ( C ) ⁢

⁢

∀

( i , j ) ∈

A , ⁢

y ij ( C ) ≥

∑

m ∈

C ⁢

x ij ( t , m ) ⁢

⁢

∀

( i , j ) ∈

A , t ∈

T , C ∈

C ⁡

( j ) $x_{\mathrm{ij}}^{\left(t,m\right)}\ge <br><br>0<br><br><br><br>\forall <br><br>\left(i,j\right)\in <br><br>A,t\in <br><br>T,m=1,\mathrm{\dots <br><br>}<br><br>,M,<br><br>\underset{\{j<br><br><br><br>\left(i,j\right)\in <br><br>A\}<br><br>}{\overset{}{\sum <br><br>}}<br><br>x_{\mathrm{ij}}^{\left(t,m\right)}-\underset{\{j<br><br><br><br>\left(j,i\right)\in <br><br>A\}<br><br>}{\overset{}{\sum <br><br>}}<br><br>x_{\mathrm{ji}}^{\left(t,m\right)}=\{\begin{array}{cc}{R}_m& <br><br>\mathrm{if}<br><br><br><br>v=s_m<br><br><br><br>\mathrm{and}<br><br><br><br>m\in <br><br>D<br><br>\left(t\right),\\ -R_m& <br><br>\mathrm{if}<br><br><br><br>m\in <br><br>D<br><br>\left(i\right),\\ 0& <br><br>\mathrm{otherwise},\end{array}<br><br><br><br>\forall <br><br>i\in <br><br>A,t\in <br><br>T,m=1,\mathrm{\dots <br><br>}<br><br>,M,.$

20. The computer readable storage medium of claim 16 wherein said instructions for computing a network code includes instructions for setting up multicast connections for m=1, . . . , M at a rate approximately equal to R_m from source s_m to terminals in the set {t ε

T| m ε

D(t) that puts a flow approximately equal to z_ij on each link (i,j).

21. The computer readable storage medium of claim 12 further comprising instructions for associating a utility function U_r(R) with each connection that has the same units as the cost function, said utility function subject to

$\sum _{}^{}$

{ j ⁢



( i , j ) ∈

A } ⁢

⁢

x ij ( t ) - ∑

{ j ⁢



( j , i ) ∈

A } ⁢

⁢

x ji ( t ) = σ

i ( t ) , ⁢

⁢

∀

i ⁢

∈

⁢

N ⁢

\ ⁢

{ t } , t ⁢

∈

⁢

T , R ≥

0 , ⁢

x ij ( t ) ≥

0 , ⁢

∀

( i , j ) ∈

A , t ∈

T . ⁢

22. The computer readable medium of claim 21 further comprising instructions for defining said utility function in accordance with the formula:

$U<br><br>\left(x,R\right)<br><br>\text{;<br><br>}=U_r<br><br>\left(R\right)-\underset{\left(i,j\right)\in <br><br>A}{\overset{}{\sum <br><br>}}<br><br>f_{\mathrm{ij}}^{}<br><br>\left(z_{\mathrm{ij}}^{\mathrm{\prime <br><br>}}\right).$

23. A method of providing minimum cost routing with network coding comprising:

modeling a network as a directed graph represented by the formula G=(N,A) wherein N is the set of nodes of the network and A is the set of links of the network;

associating a cost per unit flow for each link of said directed graph;

associating a link capacity for each link of said directed graph; and

computing a network code that sets up a routing connection that achieves an optimal cost using said cost per unit flow for each link of said directed graph and using said link capacity for each link of said directed graph, wherein said computing a network code is done in accordance with the formula;

$\mathrm{minimize}<br><br><br><br>\underset{\left(i,j\right)\in <br><br>A}{\sum <br><br>}<br><br>f_{\mathrm{ij}}<br><br>\left(z_{\mathrm{ij}}\right)$ $\mathrm{subject}<br><br><br><br>\mathrm{to}<br><br><br><br>z_{\mathrm{ij}}=\underset{t\in <br><br>T}{\max }<br><br>x_{\mathrm{ij}}^{\left(t\right)},<br><br>\forall <br><br>\left(i,j\right)\in <br><br>A,<br><br>\underset{\left\{j|\left(i,j\right)\in <br><br>A\right\}}{\sum <br><br>}<br><br>x_{\mathrm{ij}}^{\left(t\right)}-\underset{\left\{j|\left(j,i\right)\in <br><br>A\right\}}{\sum <br><br>}<br><br>x_{\mathrm{ji}}^{\left(i\right)}={\mathrm{\sigma <br><br>}}_i^{\left(t\right)},<br><br>\forall <br><br>i\in <br><br>N,<br><br>t\in <br><br>T,<br><br>x_{\mathrm{ij}}^{\left(t\right)}\ge <br><br>0,<br><br>\forall <br><br>\left(i,j\right)\in <br><br>A,<br><br>t\in <br><br>T.$

wherein ∀

(ij) ε

A, t ε

T, and wherein t is a node in the set of destination nodes T.

24. A computer readable storage medium having computer readable code thereon for providing minimum cost routing with network coding, the medium comprising:

instructions for modeling a network as a directed graph represented by the formula G=(N,A) wherein N is the set of nodes of the network and A is the set of links of the network;

instructions for associating a cost per unit flow for each link of said directed graph;

instructions for associating a link capacity for each link of said directed graph; and

instructions for computing a network code that sets up a routing connection that achieves an optimal cost using said cost per unit flow for each link of said directed graph and using said link capacity for each link of said directed graph, wherein said computing a network code is done in accordance with the formula;

$\mathrm{minimize}<br><br><br><br>\underset{\left(i,j\right)\in <br><br>A}{\sum <br><br>}<br><br>f_{\mathrm{ij}}<br><br>\left(z_{\mathrm{ij}}\right)$ $\mathrm{subject}<br><br><br><br>\mathrm{to}<br><br><br><br>z_{\mathrm{ij}}=\underset{t\in <br><br>T}{\max }<br><br>x_{\mathrm{ij}}^{\left(t\right)},<br><br>\forall <br><br>\left(i,j\right)\in <br><br>A,<br><br>\underset{\left\{j|\left(i,j\right)\in <br><br>A\right\}}{\sum <br><br>}<br><br>x_{\mathrm{ij}}^{\left(t\right)}-\underset{\left\{j|\left(j,i\right)\in <br><br>A\right\}}{\sum <br><br>}<br><br>x_{\mathrm{ji}}^{\left(i\right)}={\mathrm{\sigma <br><br>}}_i^{\left(t\right)},<br><br>\forall <br><br>i\in <br><br>N,<br><br>t\in <br><br>T,<br><br>x_{\mathrm{ij}}^{\left(t\right)}\ge <br><br>0,<br><br>\forall <br><br>\left(i,j\right)\in <br><br>A,<br><br>t\in <br><br>T.$

wherein ∀

(ij) ε

A, t ∀

T, and wherein t is a node in the set of destination nodes T.