System and method for rerouting circuits on SONET and SDH rings without disrupting service
View Patent ↗A system and method for rerouting circuits on a SONET, SDH or similar ring without disrupting service. In one embodiment, the system includes: (1) a route design subsystem adapted to identify, for the circuits, alternative routes that are subject to an alignment constraint and increase an objective value associated with the ring and (2) a path migration subsystem, associated with the route design subsystem, adapted to determine a hitless migration sequence that allows the alternative routes to be employed.
1. A system for rerouting circuits on a ring, comprising:
a route design subsystem for defining a sequence of time slots, each time slot corresponding to a circuit capacity unit, an alternative route for a circuit on said ring being identified subject to an alignment constraint and being assigned a number of contiguous time slots in said sequence, wherein said number of contiguous time slots corresponds to multiple circuit capacity units required by said circuit, and said assigned time slots start at one of given pre-selected specific time slots in said sequence pursuant to said alignment constraint; and
a path migration subsystem, associated with said route design subsystem, that determines a hitless migration sequence that allows said alternative route to be employed;
wherein said route design and path migration subsystems are configured to reroute multiple circuits at any given time.
2. The system as recited in claim 1 wherein route design subsystem employs a greedy algorithm to identify said alternative route.
3. The system as recited in claim 1 wherein said route design subsystem employs at least one packing set to measure an objective value associated with said ring.
4. The system as recited in claim 1 wherein an objective function orthogonal to an algorithm employed by said route design subsystem determines an objective value associated with said ring.
5. The system as recited in claim 1 wherein an objective value associated with said ring is determined by
Z
=
∑
i
∈
{
1
,
3
,
12
,
…
}
∑
c
k
∈
P
i
f
(
g
(
c
k
)
,
l
(
c
k
)
)
,
where P i is a packing set for granularity i and g(c k ) and l(c k ) are granularity and length, respectively of circuit c k in P i , and f is a heuristic function.
6. The system as recited in claim 1 wherein said hitless migration sequence calls for ones of said circuits to be rerouted according to a selected one of:
rerouting said ones to a different time slot,
reversing a direction of said ones, and
rerouting by both rerouting said ones to said different time slot and reversing said direction.
7. The system as recited in claim 1 wherein said route design subsystem identifies alternative routes that at least locally maximize an objective value associated with said ring.
8. The system as recited in claim 1 wherein said ring is selected from the group consisting of:
a Unidirectional Path-Switched Ring (UPSR) in which said circuits are unprotected, and
a Bidirectional Line-Switched Ring (BLSR).
9. The system as recited in claim 1 wherein said given pre-selected specific time slots are selected from the group consisting of:
1,
3,
12,
48, and
192.
10. The system as recited in claim 1 wherein said ring conforms to a standard selected from the group consisting of:
Synchronous Optical NETwork (SONET), and
Synchronous Digital Hierarchy (SDH).
11. A method of rerouting circuits on a ring, comprising:
defining a sequence of time slots, each time slot corresponding to a circuit capacity unit;
identifying, for a circuit on said ring, an alternative route subject to an alignment constraint and assigned a number of contiguous time slots in said sequence, wherein said number of contiguous time slots corresponds to multiple circuit capacity units required by said circuit, and said assigned time slots start at one of given pre-selected specific time slots in said sequence pursuant to said alignment constraint; and
determining a hitless migration sequence that allows said alternative route to be employed;
wherein said method reroutes multiple circuits at any given time.
12. The method as recited in claim 11 wherein said identifying comprises employing a greedy algorithm to identify said alternative route.
13. The method as recited in claim 11 wherein said identifying comprises employing at least one packing set to measure an objective value associated with said ring.
14. The method as recited in claim 11 wherein said identifying comprises employing an objective function orthogonal to an algorithm to determine an objective value associated with said ring.
15. The method as recited in claim 11 wherein said identifying comprises employing
Z
=
∑
i
∈
{
1
,
3
,
12
,
…
}
∑
c
k
∈
P
i
f
(
g
(
c
k
)
,
l
(
c
k
)
)
to determine an objective value associated with said ring, where P i is a packing set for granularity i and g(c k ) and l(c k ) are granularity and length, respectively of circuit c k in P i , and f is a heuristic function.
16. The method as recited in claim 11 wherein said hitless migration sequence calls for ones of said circuits to be rerouted according to a selected one of:
rerouting said ones to a different time slot,
reversing a direction of said ones, and
rerouting by both rerouting said ones to said different time slot and reversing said direction.
17. The method as recited in claim 11 wherein said identifying comprises identifying alternative routes that at least locally maximize an objective value associated with said ring.
18. The method as recited in claim 11 wherein said ring is selected from the group consisting of:
a Unidirectional Path-Switched Ring (UPSR) in which said circuits are unprotected, and
a Bidirectional Line-Switched Ring (BLSR).
19. The method as recited in claim 11 wherein said given pre-selected specific time slots are selected from the group consisting of:
1,
3,
12,
48, and
192.
20. The method as recited in claim 11 wherein said ring conforms to a standard selected from the group consisting of:
Synchronous Optical NETwork (SONET), and
Synchronous Digital Hierarchy (SDH).
21. A system for rerouting circuits on a ring, comprising:
means for defining a sequence of time slots, each time slot corresponding to a circuit capacity unit;
means for identifying, for a circuit on said ring, an alternative route subject to an alignment constraint and assigned a number of contiguous time slots in said sequence, wherein said number of contiguous time slots corresponds to multiple circuit capacity units required by said circuit, and said assigned time slots start at one of given pre-selected specific time slots in said sequence pursuant to said alignment constraint; and
means for determining a hitless migration sequence that allows said alternative route to be employed;
wherein said system is configured to reroute multiple circuits at any given time.
22. The system as recited in claim 21 wherein said means for identifying comprises means for employing a greedy algorithm to identify said alternative route.
23. The system as recited in claim 21 wherein said means for identifying comprises means for employing at least one packing set to measure an objective value associated with said ring.
24. The system as recited in claim 21 wherein said means for identifying comprises means for employing an objective function orthogonal to an algorithm employed to determine an objective value associated with said ring.