Scheduling connections in a multi-stage switch to retain non-blocking properties of constituent switching elements
AssigneeVelio Communications, Inc.
InventorBrian Patrick Towles
Life of this patent
Estimating the term…
Abstract
A scheduling algorithm is provided that may be implemented in a multi-stage switch requiring less switching elements than known switching architectures in order to increase bandwidth and to retain the non-blocking properties of the constituent switching elements for incoming traffic, including multicast traffic. A scheduling algorithm is also provided for incremental scheduling of connections being added or removed from the switch.
Claims27
A method of scheduling connections in a multi-stage switch, the multi-stage switch comprising two input stage switching elements, two output stage switching elements, and two center stage switching elements coupling the two input stage switching element to the two output stage switching elements, each of the respective switching elements having non-blocking properties for incoming traffic, including multicast traffic, the method comprising:
- scheduling a configured set of input/output connections including multicast connections between the two center stage switching elements according to a scheduling pattern in order to minimize a first difference in the numbers of connections from a common input stage switching element scheduled for the respective center stage switching elements and to minimize a second difference in the numbers of connections to a common output stage switching element scheduled for the respective center stage switching elements, resulting in the non-blocking properties of the respective switching elements being retained.
A method of incremental scheduling connections in a multi-stage switch, the multi-stage switch comprising two input stage switching elements, two output stage switching elements, and two center stage switching elements coupling the two input stage switching element to the two output stage switching elements, each of the respective switching elements having non-blocking properties for incoming traffic, including multicast traffic, the method comprising:
- adding a connection to a first configured set of input/output connections including multicast connections, resulting in a second configured set of input/output connections;
- generating temporary schedules for the two center stage switching elements from the second configured set of connections according to a scheduling pattern in order to minimize a first difference in the numbers of connections from a common input stage switching element scheduled for the respective center stage switching elements and to minimize a second difference in the numbers of connections to a common output stage switching element scheduled for the respective center stage switching elements, resulting in the non-blocking properties of the respective switching elements being retained;
- and
- rearranging scheduled connections for the two center stage switching elements using a limited number of rearrangements to match the temporary schedules.
A method of incremental scheduling connections in a multi-stage switch, the multi-stage switch comprising two input stage switching elements, two output stage switching elements, and two center stage switching elements coupling the two input stage switching element to the two output stage switching elements, each of the respective switching elements having non-blocking properties for incoming traffic, including multicast traffic, the method comprising:
- removing a connection from a first configured set of connections, resulting in a second configured set of connections;
- obtaining existing schedules for the two center stage switching elements, the existing schedules being previously generated according to a scheduling pattern in order to minimize a first difference in the numbers of connections from a common input stage switching element scheduled for the respective center stage switching elements and to minimize a second difference in the numbers of connections to a common output stage switching element scheduled for the respective center stage switching elements, resulting in the non-blocking properties of the respective switching elements being retained;
- removing a scheduled connection from one of the existing schedules of the two center stage switching elements that corresponds to the removed connection;
- and
- rearranging the existing schedules of the two center stage switching element the schedules using a limited number of rearrangements to minimize a difference between the schedules.
A multi-stage switch, comprising:
- two input stage switching elements;
- two output stage switching elements;
- two center stage switching elements coupling the two input stage switching elements to the two output stage switching elements, each of the respective switching elements having non-blocking properties for incoming traffic, including multicast traffic;
- a processor scheduling a configured set of input/output connections including multicast connections between the two center stage switching elements according to a scheduling pattern in order to minimize a first difference in the numbers of connections from a common input stage switching element scheduled for the respective center stage switching elements and to minimize a second difference in the numbers of connections to a common output stage switching element scheduled for the respective center stage switching elements, resulting in the non-blocking properties of the respective switching elements being retained.
A multi-stage switch, comprising:
- two input stage switching elements;
- two output stage switching elements;
- two center stage switching elements coupling the two input stage switching elements to the two output stage switching elements, each of the respective switching elements having non-blocking properties for incoming traffic, including multicast traffic;
- a processor adding a connection to a first configured set of input/output connections including multicast connections, resulting in a second configured set of input/output connections;
- the processor generating temporary schedules for the two center stage switching elements from the second configured set of connections according to a scheduling pattern in order to minimize a first difference in the numbers of connections from a common input stage switching element scheduled for the respective center stage switching elements and to minimize a second difference in the numbers of connections to a common output stage switching element scheduled for the respective center stage switching elements, resulting in the non-blocking properties of the respective switching elements being retained;
- and
- the processor rearranging scheduled connections for the two center stage switching elements using a limited number of rearrangements to match the temporary schedules.
A multi-stage switch, comprising:
- two input stage switching elements;
- two output stage switching elements;
- two center stage switching elements coupling the plural input stage switching elements to the two output stage switching elements, each of the respective switching elements having non-blocking properties for incoming traffic, including multicast traffic;
- a processor removing a connection from a first configured set of connections including multicast traffic, resulting in a second configured set of connections;
- the processor obtaining existing schedules for the two center stage switching elements, the existing schedules being previously generated by the processor according to a scheduling pattern in order to minimize a first difference in the numbers of connections from a common input stage switching element scheduled for the respective center stage switching elements and to minimize a second difference in the numbers of connections to a common output stage switching element scheduled for the respective center stage switching elements, resulting in the non-blocking properties of the respective switching elements being retained;
- the processor removing a scheduled connection from one of the existing schedules of the two center stage switching elements that corresponds to the removed connection;
- and
- the processor rearranging the existing schedules of the two center stage switching element the schedules using a limited number of rearrangements to minimize a difference between the schedules.
A multi-stage switch, comprising:
- two input stage switching elements;
- two output stage switching elements;
- two center stage switching elements coupling the two input stage switching elements to the two output stage switching elements, each of the respective switching elements having non-blocking properties for incoming traffic, including multicast traffic;
- a scheduling means coupled to at least the two center stage switching elements, the scheduling means scheduling a configured set of input/output connections including multicast connections between the two center stage switching elements according to a scheduling pattern in order to minimize a first difference in the numbers of connections from a common input stage switching element scheduled for the respective center stage switching elements and to minimize a second difference in the numbers of connections to a common output stage switching element scheduled for the respective center stage switching elements, resulting in the non-blocking properties of the respective switching elements being retained.
Dependencies are inferred from the claim text.