Scheduling with delayed graphs for communication networks

• US 20050226214A1
• Filed: 04/08/2004
• Published: 10/13/2005
• Est. Priority Date: 04/08/2004
• Status: Active Grant

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Alcatel-Lucent USA, Inc. (Nokia Corporation)
• Inventors: Lakshman, Tirunell V., Kodialam, Muralidharan S., Stiliadis, Dimitrios, Keslassy, Isaac
• Granted Patent: US 7,489,638 B2
• Time in Patent Office: Days
• US Class Current: 370/351
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/52 by attributing bandwidth to queues

Abstract

A network of nodes interconnected by links, such as a wavelength division multiplexing (WDM) ring network, is modeled by a delayed graph in which propagation delay between nodes is accounted for. Given the delayed graph, a traffic matrix for an admissible traffic pattern is scheduled over a frame period. Scheduling of the traffic matrix formulates a set of scheduling constraints based on the delays and decomposes the traffic matrix into a set of transmission matrices. Each of the set of transmission matrices is scheduled over the frame period.

Claims

1. A method of generating a schedule for two or more nodes of a network, the method comprising the steps of:

(a) generating a network graph accounting for delay between each node of the network;

(b) generating a set of network constraints for the network graph, one or more of the network constraints based on the schedule accounting for each delay; and

(c) decomposing, into a set of transmission matrices, a traffic matrix for the network graph based on the set of network constraints, the set of transmission matrices representing the schedule over a frame period.

2. The invention of claim 1, further comprising the step of (d) scheduling each of the set of transmission matrices over the frame period.

3. The invention of claim 2, wherein, for step (c), traffic of the traffic matrix is delay insensitive, step (c) decomposes the traffic matrix for the set of constraints not accounting for delay, and the frame period includes an inter-schedule time of T, where the inter-schedule time is the time between scheduling each of the set of transmission matrices and T is the total propagation time through the network.

4. The invention of claim 2, wherein step (c) decomposes the traffic matrix for the set of constraints not accounting for delay, and step (c) further comprises the step of adjusting a time-slot of the framing period, the framing period being equivalent to a multiple of the time-slot, such that each delay is a multiple of the frame period.

5. The invention of claim 2, wherein, for step (b) the set of constraints of a set S of transmission matrices are:

$\underset{k=1}{\overset{N}{\sum <br><br>}}<br><br>S_{\mathrm{ik}}<br><br>\left(t\right)\le <br><br>1<br><br>\text{\hspace{1em}<br><br>}<br><br>\forall <br><br>i,t$ $\frac{1}{F}<br><br>\underset{t=0}{\overset{F-1}{\sum <br><br>}}<br><br>S_{\mathrm{ij}}<br><br>\left(t\right)\ge <br><br>R_{\mathrm{ij}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\forall <br><br>i,j$ $S_{\mathrm{ij}}<br><br>\left(t\right)\in <br><br>\left\{0,1\right\}<br><br>\text{\hspace{1em}<br><br>}<br><br>\forall <br><br>i,j,t$ $\underset{k=1}{\overset{N}{\sum <br><br>}}<br><br>S_{\mathrm{kj}}<br><br>\left(\left(t-{\mathrm{\tau <br><br>}}_{\mathrm{kj}}\right)<br><br>\mathrm{mod}<br><br>\text{\hspace{1em}<br><br>}<br><br>F\right)\le <br><br>1<br><br>\text{\hspace{1em}<br><br>}<br><br>\forall <br><br>j,t.$

where i,j are the ith and jth nodes of the network, F is the frame period, t is a time unit, τ

_kj is a delay between node k and node j, and N is a number of nodes in the network.

6. The invention of claim 5, wherein, for step (c), the frame period F is set to the total propagation time of the network, the schedule of each node is synchronized to a global clock, step (c) decomposes the rate matrix in accordance with the set of constraints not accounting for each delay τ

_kj between nodes k and j for time t=t′

, and t′

is time shifted by (t−

τ

_kj)mod F) ∀

j,t.

7. The invention of claim 5, wherein, for step (a), each delay τ

_ij is separable into sub-delay sets u and v such that τ

_ij=u_i+v_jmod F ∀

i,j.

8. The invention of claim 5, wherein, for step (a), one or more of the delays τ

_ij are non-separable, step (a) further comprises the step of adding, to one or more of the non-separable delays, an additional delay δ

_ij such that the resulting network graph includes separable delays {circumflex over (τ

)}_ij;

$\{\begin{array}{ccc}\left(i\right)& {\widehat{\mathrm{\tau <br><br>}}}_{\mathrm{ij}}={\mathrm{\tau <br><br>}}_{\mathrm{ij}}+{\mathrm{\delta <br><br>}}_{\mathrm{ij}}& \forall <br><br>i,j\\ \left(\mathrm{ii}\right)& {\widehat{\mathrm{\tau <br><br>}}}_{\mathrm{ij}}=u_i+v_j& \forall <br><br>i,j\\ \left(\mathrm{iii}\right)<br><br>\text{\hspace{1em}<br><br>}& {\mathrm{\delta <br><br>}}_{\mathrm{ij}}\ge <br><br>0& \forall <br><br>i,j\end{array}.$

9. The invention of claim 8, further comprising the step of evaluating an objective function:

$\underset{\mathrm{\delta <br><br>}}{\min }<br><br>\left(\underset{i,j}{\sum <br><br>}<br><br>{\mathrm{\delta <br><br>}}_{\mathrm{ij}}\right).$

10. The invention of claim 1, wherein step (c) decomposes the traffic matrix in accordance with a Birkhoff-Von Neumann decomposition.

11. The invention of claim 10, wherein step (c) decomposes the traffic matrix R in accordance with the Birkhoff-Von Neumann decomposition defined as:

$R\le <br><br>\underset{k=1}{\overset{K}{\sum <br><br>}}<br><br>{\mathrm{\varphi <br><br>}}_k<br><br>{\mathrm{\sigma <br><br>}}_k,\mathrm{with}$ $\underset{k=1}{\overset{K}{\sum <br><br>}}<br><br>{\mathrm{\varphi <br><br>}}_k=1<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{and}$

wherein the set (φ

_k)<sub>1≦

k≦

K</sub> is a set of positive rational numbers of denominator F and (σ

_k)<sub>1≦

k≦

K</sub> is a set of permutation matrices.

12. The invention of claim 1, wherein, for step (b), one of the network constraints sets the frame period to a total delay through the network.

13. The invention of claim 12, further comprising the steps of providing, by one of the two or more nodes of the network, a global clock and synchronizing the schedule of each node to the global clock.

14. The invention of claim 13, wherein step (c) decomposes the traffic matrix.

15. The invention of claim 1, wherein, for step (a), the network is a ring network of nodes interconnected by links in a ring configuration, the ring configuration having first and second logical rings coupled to corresponding first and second transmitter/receiver pairs.

16. The invention of claim 15, further comprising the steps of forming the traffic matrix for traffic of the second logical ring, the traffic of the second logical ring formed by load balancing the traffic of the traffic matrix between the first and second logical rings.

17. The invention of claim 16, wherein load balancing of the traffic includes the steps of uniformly distributing packets received at a node in the first logical ring to one or more buffers of the node, and transferring packets of the buffers to the second logical ring.

18. The invention of claim 1, wherein the method is implemented in a processor of a network controller coupled to the two or more nodes.

19. The invention of claim 1, wherein, for step (a), the network is a ring network of nodes interconnected by links in a ring configuration.

20. The invention of claim 19, wherein, for step (a) the ring is either a wavelength division multiplex ring, and each delay represents a propagation delay of a wavelength of each link.

21. A network of nodes interconnected by links including a processor comprising:

first means for generating a network graph accounting for delay between each node of the network;

second means for generating a set of network constraints for the network graph, one or more of the network constraints based on the schedule accounting for each delay; and

third means for decomposing, into a set of transmission matrices, a traffic matrix for the network graph based on the set of network constraints, the set of transmission matrices representing the schedule over a frame period.

22. A computer-readable medium having stored thereon a plurality of instructions, the plurality of instructions including instructions which, when executed by a processor, cause the processor to implement a method for generating a schedule for two or more nodes of a network, the method comprising the steps of:

(a) generating a network graph accounting for delay between each node of the network;

(b) generating a set of network constraints for the network graph, one or more of the network constraints based on the schedule accounting for each delay; and

(c) decomposing, into a set of transmission matrices, a traffic matrix for the network graph based on the set of network constraints, the set of transmission matrices representing the schedule over a frame period.