Scheduling with delayed graphs for communication networks
View Patent ↗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.
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 in accordance with a Birkhoff-Von Neumann decomposition, 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, wherein step (c) decomposes the traffic matrix R in accordance with the Birkhoff-Von Neumann decomposition defined as:
R
≤
∑
k
=
1
K
ϕ
k
σ
k
,
with
∑
k
=
1
K
ϕ
k
=
1
and
wherein the set (φ k ) 0≦k≦K is a set of positive rational numbers of denominator F and (σ k ) 0≦k≦K is a set of permutation matrices.
2. The method of claim 1 , further comprising the step of (d) scheduling each of the set of transmission matrices over the frame period.
3. The method 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 method 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 method of claim 2 , wherein, for step (b) the set of constraints of a set S of transmission matrices are:
∑
k
=
1
N
S
ik
(
t
)
≤
1
∀
i
,
t
1
F
∑
t
=
0
F
-
1
S
ij
(
t
)
≥
R
ij
∀
i
,
j
S
ij
(
t
)
∈
{
0
,
1
}
∀
i
,
j
,
t
∑
k
=
1
N
S
kj
(
(
t
-
τ
kj
)
mod
F
)
≤
1
∀
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, and R ij is an entry corresponding to nodes i,j in a traffic matrix R.
6. The method 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 )modF ∀j,t.
7. The method 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 j modF ∀i,j.
8. The method 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 (τ)} i,j :
{
(
i
)
τ
^
ij
=
τ
ij
+
δ
ij
∀
i
,
j
(
ii
)
τ
^
ij
=
u
i
+
v
j
∀
i
,
j
(
iii
)
δ
ij
≥
0
∀
i
,
j
.
9. The method of claim 8 , further comprising the step of evaluating an objective function:
min
δ
(
∑
i
,
j
δ
ij
)
.
10. The method of claim 1 , wherein, for step (b), one of the network constraints sets the frame period to a total delay through the network.
11. The method of claim 10 , 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.
12. The method 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.
13. The method hwenhen of claim 12 , 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.
14. The method of claim 13 , 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.
15. The method of claim 1 , wherein the method is implemented in a processor of a network controller coupled to the two or more nodes.
16. The method of claim 1 , wherein, for step (a), the network is a ring network of nodes interconnected by links in a ring configuration.
17. The method of claim 16 , 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.
18. 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 a schedule accounting for each delay; and
third means for decomposing in accordance with a Birkhoff-Von Neumann decomposition, into a set of transmission matrices, a traffic matrix R for the network graph based on the set of network constraints, the set of transmission matrices representing the schedule over a frame period,
wherein the traffic matrix R in accordance with the Birkhoff-Von Neumann decomposition is defined as:
R
≤
∑
k
=
1
K
ϕ
k
σ
k
,
with
∑
k
=
1
K
ϕ
k
=
1
and
wherein the set (φ k ) 0≦k≦K is a set of positive rational numbers of denominator F and (σ k ) 0≦k≦K is a set of permutation matrices.
19. 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 in accordance with a Birkhoff-Von Neumann decomposition, 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, wherein step (c) decomposes the traffic matrix R in accordance with the Birkhoff-Von Neumann decomposition defined as:
R
≤
∑
k
=
1
K
ϕ
k
σ
k
,
with
∑
k
=
1
K
ϕ
k
=
1
and
wherein the set (φ k ) 0≦k≦K is a set of positive rational numbers of denominator F and (σ k ) 0≦k≦K is a set of permutation matrices.
20. 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, wherein the set of constraints of a set S of transmission matrices are:
∑
k
=
1
N
S
ik
(
t
)
≤
1
∀
i
,
t
1
F
∑
t
=
0
F
-
1
S
ij
(
t
)
≥
R
ij
∀
i
,
j
S
ij
(
t
)
∈
{
0
,
1
}
∀
i
,
j
,
t
∑
k
=
1
N
S
kj
(
(
t
-
τ
kj
)
mod
F
)
≤
1
∀
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, and R ij is an entry corresponding to nodes i,j in a traffic matrix R;
(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; and
(d) scheduling each of the set of transmission matrices over the frame period.
21. The method of claim 20 , 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.
22. The method of claim 20 , 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.
23. The method of claim 20 , 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.
24. The method of claim 20 wherein, for step (a), each delay τ ij is separable into sub-delay sets u and v such that τ ij =u i +v j mod F ∀i,j.
25. The method of claim 20 , 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 :
{
(
i
)
τ
^
ij
=
τ
ij
+
δ
ij
∀
i
,
j
(
ii
)
τ
^
ij
=
u
i
+
v
j
∀
i
,
j
(
iii
)
δ
ij
≥
0
∀
i
,
j
.
26. The method of claim 25 , further comprising the step of evaluating an objective function:
min
δ
(
∑
i
,
j
δ
ij
)
.
27. The method of claim 20 , wherein step (c) decomposes the traffic matrix in accordance with a Birkhoff-Von Neumann decomposition.
28. The method of claim 27 , wherein step (c) decomposes the traffic matrix R in accordance with the Birkhoff-Von Neumann decomposition defined as:
R
≤
∑
k
=
1
K
ϕ
k
σ
k
,
with
∑
k
=
1
K
ϕ
k
=
1
and
wherein the set (φ k ) 0≦k≦K is a set of positive rational numbers of denominator F and (τ k ) 0≦k≦K is a set of permutation matrices.
29. The method of claim 20 , wherein, for step (b), one of the network constraints sets the frame period to a total delay through the network.
30. The method of claim 29 , 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.
31. The method of claim 20 , 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.
32. The method of claim 31 , 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.
33. The method of claim 32 , 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.
34. The method of claim 20 , wherein the method is implemented in a processor of a network controller coupled to the two or more nodes.
35. The method of claim 20 , wherein, for step (a), the network is a ring network of nodes interconnected by links in a ring configuration.
36. The method of claim 35 , 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.
37. 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 a schedule accounting for each delay, wherein the set of constraints of a set S of transmission matrices are:
∑
k
=
1
N
S
ik
(
t
)
≤
1
∀
i
,
t
1
F
∑
t
=
0
F
-
1
S
ij
(
t
)
≥
R
ij
∀
i
,
j
S
ij
(
t
)
∈
{
0
,
1
}
∀
i
,
j
,
t
∑
k
=
1
N
S
kj
(
(
t
-
τ
kj
)
mod
F
)
≤
1
∀
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, and R ij is an entry corresponding to nodes i,j in a traffic matrix R; 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.
38. 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, wherein the set of constraints of a set S of transmission matrices are:
∑
k
=
1
N
S
ik
(
t
)
≤
1
∀
i
,
t
1
F
∑
t
=
0
F
-
1
S
ij
(
t
)
≥
R
ij
∀
i
,
j
S
ij
(
t
)
∈
{
0
,
1
}
∀
i
,
j
,
t
∑
k
=
1
N
S
kj
(
(
t
-
τ
kj
)
mod
F
)
≤
1
∀
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, and R ij is an entry corresponding to nodes i,j in a traffic matrix R; 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.