Load balancing multicast connection scheduling in 3-stage TDM fabrics
View Patent ↗A multicast connection scheduling method for a 3-stage switch fabric with n 1 first stage, n 2 second stage and n 3 third stage interconnected switching devices. The first and third stage devices are non-blocking for unicast connections. The center stage devices are non-blocking for multicast connections. Load tables are provided for each center stage device, with one row per first and/or third stage device. Each row represents the number of connections being serviced between the first and/or third stage devices, through the center stage device corresponding to the table. By monitoring and updating the tables, the invention derives an approximately optimal connection schedule for an input list of connection requests, such that no input connection load exceeds any center stage device's maximum input connection load capacity and no output connection load exceeds any center stage device's maximum output connection load capacity.
1. A multicast connection scheduling method for a 3-stage switch fabric having n 1 first stage switching devices, n 2 center stage switching devices and n 3 third stage switching devices, wherein:
(a) each first stage switching device has an output connected to an input of each center stage switching device;
(b) each third stage switching device has an input connected to an output of each center stage switching device;
the method comprising:
(c) for each one of the n 2 center stage switching devices:
(i) providing an input connection load table having one row for each one of the n 1 first stage switching devices, each row containing a representation of a number of connections currently being serviced by connections established between the first stage switching device corresponding to that row and the center stage switching device to which the input connection load table corresponds;
(ii) providing an output connection load table having one row for each one of the n 3 third stage switching devices, each row containing a representation of a number of connections currently being serviced by connections established between the third stage switching device corresponding to that row and the center stage switching device to which the output connection load table corresponds;
(iii) storing in each row of the input connection load table a representation that no connections are currently being serviced by connections established between the first stage switching device corresponding to that row and the center stage switching device to which the input connection load table corresponds;
(iv) storing in each row of the output connection load table a representation that no connections are currently being serviced by connections established between the third stage switching device corresponding to that row and the center stage switching device to which the output connection load table corresponds;
(d) for each connection request received by the 3-stage switch fabric:
(i) for each center stage switching device having sufficient connection capacity to service the connection request, determining a sum of input and output connection loads currently being serviced by the center stage switching device on input and output ports of the center stage switching device corresponding to input and output port requirements of the connection request;
(ii) if at least one center stage switching device has sufficient connection capacity to service the connection request and if the sum has a lowest value for exactly one center stage switching device:
(1) scheduling the connection request on the exactly one center stage switching device;
(2) in the input connection load table corresponding to the exactly one center stage switching device, incrementing by one the representation contained in the row corresponding to the first stage switching device corresponding to the input port requirement of the connection request;
(3) in the output connection load table corresponding to the exactly one center stage switching device, incrementing by one the representation contained in each row corresponding to each third stage switching device corresponding to the output port requirement of the connection request;
(iii) if at least two center stage switching devices have sufficient connection capacity to service the connection request and if the sum has a lowest value for two or more center stage switching devices:
(1) scheduling the connection request on a selected one of the two or more center stage switching devices;
(2) in the input connection load table corresponding to the selected one of the two or more center stage switching devices, incrementing by one the representation contained in the row corresponding to the first stage switching device corresponding to the input port requirement of the connection request;
(3) in the output connection load table corresponding to the selected one of the two or more center stage switching devices, incrementing by one the representation contained in each row corresponding to each third stage switching device corresponding to the output port requirement of the connection request; and,
(iv) if no center stage switching device has sufficient connection capacity to service the connection request, failing to schedule the connection request.
2. A method as defined in claim 1 , wherein the selected one of the two or more center stage switching devices is a lowest numbered one of the two or more center stage switching devices.
3. A method as defined in claim 2 , wherein:
(a) each first stage switching device is non-blocking for unicast connections;
(b) each center stage switching device is non-blocking for a predefined level of multicast connections; and,
(c) each third stage switching device is non-blocking for unicast connections.
4. A method as defined in claim 1 , wherein the selected one of the two or more center stage switching devices is a randomly selected one of the two or more center stage switching devices.
5. A method as defined in claim 4 , wherein:
(a) each first stage switching device is non-blocking for unicast connections;
(b) each center stage switching device is non-blocking for a predefined level of multicast connections; and,
(c) each third stage switching device is non-blocking for unicast connections.
6. A method as defined in claim 1 , further comprising determining the lowest value of the sum by:
(a) initializing a previously determined lowest value of the sum to a predefined initialization value;
(b) for each one of the n 2 center stage switching devices, if the previously determined lowest value of the sum is one of:
(i) an initialization value;
(ii) greater than the sum of the input and output connection loads currently being serviced by the center stage switching device on the input and output ports of the center stage switching device corresponding to the input and output port requirements of the connection request;
replacing the previously determined lowest value of the sum with the sum of the input and output connection loads currently being serviced by the center stage switching device on the input and output ports of the center stage switching device corresponding to the input and output port requirements of the connection request; and,
(c) then utilizing the previously determined lowest value of the sum as the lowest value of the sum.
7. A method as defined in claim 6 , wherein:
(a) each first stage switching device is non-blocking for unicast connections;
(b) each center stage switching device is non-blocking for a predefined level of multicast connections; and,
(c) each third stage switching device is non-blocking for unicast connections.
8. A method as defined in claim 1 , further comprising, for each connection deletion request received by the 3-stage switch fabric:
(a) determining the center stage switching device on which a connection corresponding to the connection deletion request is currently scheduled;
(b) in the input connection load table corresponding to the determined center stage switching device, decrementing by one the representation contained in the row corresponding to the first stage switching device corresponding to an input port requirement of the connection deletion request; and,
(c) in the output connection load table corresponding to the determined center stage switching device, decrementing by one the representation contained in each row corresponding to each third stage switching device corresponding to an output port requirement of the connection deletion request.
9. A method as defined in claim 8 , wherein:
(a) each first stage switching device is non-blocking for unicast connections;
(b) each center stage switching device is non-blocking for a predefined level of multicast connections; and,
(c) each third stage switching device is non-blocking for unicast connections.
10. A method as defined in claim 1 , wherein:
(a) each first stage switching device is non-blocking for unicast connections;
(b) each center stage switching device is non-blocking for a predefined level of multicast connections; and,
(c) each third stage switching device is non-blocking for unicast connections.
11. A multicast connection scheduling method for a 3-stage switch fabric having n 1 first stage switching devices, n 2 center stage switching devices and n 3 third stage switching devices, wherein:
(a) each first stage switching device has an output connected to an input of each center stage switching device;
(b) each third stage switching device has an input connected to an output of each center stage switching device;
the method comprising:
(c) for each one of the n 2 center stage switching devices:
(i) providing an input connection load table having one row for each one of the n 1 first stage switching devices, each row containing a representation of a number of connections currently being serviced by connections established between the first stage switching device corresponding to that row and the center stage switching device to which the input connection load table corresponds;
(ii) providing an output connection load table having one row for each one of the n 3 third stage switching devices, each row containing a representation of a number of connections currently being serviced by connections established between the third stage switching device corresponding to that row and the center stage switching device to which the output connection load table corresponds;
(iii) storing in each row of the input connection load table a representation that no connections are currently being serviced by connections established between the first stage switching device corresponding to that row and the center stage switching device to which the input connection load table corresponds;
(iv) storing in each row of the output connection load table a representation that no connections are currently being serviced by connections established between the third stage switching device corresponding to that row and the center stage switching device to which the output connection load table corresponds;
(d) for each connection request received by the 3-stage switch fabric:
(i) for each center stage switching device having sufficient connection capacity to service the connection request, determining an average of input and output connection loads currently being serviced by the center stage switching device on input and output ports of the center stage switching device corresponding to input and output port requirements of the connection request;
(ii) if at least one center stage switching device has sufficient connection capacity to service the connection request and if the average has a lowest value for exactly one center stage switching device:
(1) scheduling the connection request on the exactly one center stage switching device;
(2) in the input connection load table corresponding to the exactly one center stage switching device, incrementing by one the representation contained in the row corresponding to the first stage switching device corresponding to the input port requirement of the connection request;
(3) in the output connection load table corresponding to the exactly one center stage switching device, incrementing by one the representation contained in each row corresponding to each third stage switching device corresponding to the output port requirement of the connection request;
(iii) if at least two center stage switching devices have sufficient connection capacity to service the connection request and if the average has a lowest value for two or more center stage switching devices:
(1) scheduling the connection request on a selected one of the two or more center stage switching devices;
(2) in the input connection load table corresponding to the selected one of the two or more center stage switching devices, incrementing by one the representation contained in the row corresponding to the first stage switching device corresponding to the input port requirement of the connection request;
(3) in the output connection load table corresponding to the selected one of the two or more center stage switching devices, incrementing by one the representation contained in each row corresponding to each third stage switching device corresponding to the output port requirement of the connection request; and,
(iv) if no center stage switching device has sufficient connection capacity to service the connection request, failing to schedule the connection request.
12. A method as defined in claim 11 , wherein the selected one of the two or more center stage switching devices is the lowest numbered one of the two or more center stage switching devices.
13. A method as defined in claim 12 , wherein:
(a) each first stage switching device is non-blocking for unicast connections;
(b) each center stage switching device is non-blocking for a predefined level of multicast connections; and,
(c) each third stage switching device is non-blocking for unicast connections.
14. A method as defined in claim 11 , wherein the selected one of the two or more center stage switching devices is a randomly selected one of the two or more center stage switching devices.
15. A method as defined in claim 14 , wherein:
(a) each first stage switching device is non-blocking for unicast connections;
(b) each center stage switching device is non-blocking for a predefined level of multicast connections; and,
(c) each third stage switching device is non-blocking for unicast connections.
16. A method as defined in claim 11 , further comprising determining the lowest value of the average by:
(a) initializing a previously determined lowest value of the average to a predefined initialization value;
(b) for each one of the n 2 center stage switching devices, if the previously determined lowest value of the average is one of:
(i) an initialization value;
(ii) greater than the average of the input and output connection loads currently being serviced by the center stage switching device on the input and output ports of the center stage switching device corresponding to the input and output port requirements of the connection request;
replacing the previously determined lowest value of the average with the average of the input and output connection loads currently being serviced by the center stage switching device on the input and output ports of the center stage switching device corresponding to the input and output port requirements of the connection request; and,
(c) then utilizing the previously determined lowest value of the average as the lowest value of the average.
17. A method as defined in claim 16 , wherein:
(a) each first stage switching device is non-blocking for unicast connections;
(b) each center stage switching device is non-blocking for a predefined level of multicast connections; and,
(c) each third stage switching device is non-blocking for unicast connections.
18. A method as defined in claim 11 , further comprising, for each connection deletion request received by the 3-stage switch fabric:
(a) determining the center stage switching device on which a connection corresponding to the connection deletion request is currently scheduled;
(b) in the input connection load table corresponding to the determined center stage switching device, decrementing by one the representation contained in the row corresponding to the first stage switching device corresponding to an input port requirement of the connection deletion request; and,
(c) in the output connection load table corresponding to the determined center stage switching device, decrementing by one the representation contained in each row corresponding to each third stage switching device corresponding to an output port requirement of the connection deletion request.
19. A method as defined in claim 18 , wherein:
(a) each first stage switching device is non-blocking for unicast connections;
(b) each center stage switching device is non-blocking for a predefined level of multicast connections; and,
(c) each third stage switching device is non-blocking for unicast connections.
20. A method as defined in claim 11 , wherein:
(a) each first stage switching device is non-blocking for unicast connections;
(b) each center stage switching device is non-blocking for a predefined level of multicast connections; and,
(c) each third stage switching device is non-blocking for unicast connections.