Granted Patent B1

US 7,212,524 · App. 10/323,939 · Granted May 1, 2007

Abstract

Claims (90)

1. A multicast call scheduling method for a TST switch fabric having n input ports, n output ports, and a p-port space stage coupled between an m-timeslot input time stage and an m-timeslot output time stage, the input time stage having m 1 =m ingress timeslots and m 2 egress timeslots, the output time stage having m 2 ingress timeslots and m 1 =m egress timeslots, the fabric having a speedup factor s=i t ·i s where i t =m 2 /m and i s =p/n, the method comprising:

(a) forming a timeslot data structure having m 2 entries, each entry corresponding to a pair consisting of one input time stage egress timeslot and one output time stage ingress timeslot, each entry having 2n sub-entries, the first n sub-entries corresponding to the n input ports and the second n sub-entries corresponding to the n output ports, each sub-entry having is sub-sub-entries, each sub-sub-entry corresponding to one of the p space stage ports, wherein an N-cast call X:(y→z 1 , z 2 . . . z N ) from a y th one of the n input ports to z 1 , z 2 . . . z N ones of the n output ports is represented in the timeslot data structure by:

(i) associating a y th one of the first n sub-entries within a selected entry with z 1 , z 2 , . . . z N ones of the second n sub-entries within the selected entry;

(ii) associating a sub-sub-entry of the y th one of the first n sub-entries with a sub-sub-entry in every one of the z 1 , z 2 , . . . z N ones of the second n sub-entries within the selected entry;

(b) initially assigning an initialization value to each sub-sub-entry within each sub-entry within each entry, the initialization value representing scheduling of no calls on the space stage port corresponding to that sub-sub-entry in the timeslot corresponding to that entry;

(c) upon receipt of an N-cast call X:(y→z 1 , z 2 , . . . z N ) to be scheduled on the switch fabric, sequentially examining the timeslot data structure entries to determine if there is a first entry having a first property that the first entry has:

(i) a first sub-sub-entry containing the initialization value in the y th one of the first n sub-entries;

(ii) N sub-sub-entries containing the initialization value in the z 1 , z 2 , . . . z N ones of the second n sub-entries;

(d) if there is a first entry having the first property, scheduling the call X:(y→z 1 , z 2 . . . z N ) for transmission in the timeslot corresponding to the first entry having the first property and updating the timeslot data structure by assigning a non-initialization value to the first sub-sub-entry and to each of the N sub-sub-entries;

(e) if there is no first entry having the first property and if N=1, terminating the method by indicating that the call cannot be scheduled on the switch fabric; and,

(f) if there is no first entry having the first property and if N>1, dividing the call into two or more calls.

2. A multicast call scheduling method for a TST switch fabric having n input ports, n output ports, and a p-port space stage coupled between an m-timeslot input time stage and an m-timeslot output time stage, the input time stage having m 1 =m ingress timeslots and m 2 egress timeslots, the output time stage having m 2 ingress timeslots and m 1 =m egress timeslots, the fabric having a speedup factor s=i t ·i s where i 1 =m 2 /m and i s =p/n, the method comprising:

(a) forming a timeslot data structure having m 2 entries, each entry corresponding to a pair consisting of one input time stage egress timeslot and one output time stage ingress timeslot, each entry having 2n sub-entries, the first n sub-entries corresponding to the n input ports and the second n sub-entries corresponding to the n output ports, each sub-entry having an associated counter for storing an integer value between 0 and i s , each counter value corresponding to one of the p space stage ports, wherein an N-cast call X:(y→z 1 , z 2 . . . z N ) from a y th one of the n input ports to z 1 , z 2 . . . z N ones of the n output ports is represented in the timeslot data structure by:

(i) associating a y th one of the first n sub-entries within a selected entry with z 1 , z 2 . . . z N ones of the second n sub-entries within the selected entry;

(ii) storing a predefined integer value in the counter of the y th one of the first n sub-entries;

(iii) storing a predefined integer value in the counter of every one of the z 1 , z 2 , . . . z N ones of the second n sub-entries within the selected entry;

(b) initially storing a zero value in each counter within each sub-entry within each entry, to represent scheduling of no calls on the space stage port corresponding to that counter in the timeslot corresponding to that entry;

(c) upon receipt of an N-cast call X:(y→z 1 , z 2 . . . z N ) to be scheduled on the switch fabric, sequentially examining the timeslot data structure entries to determine if there is a first entry having a first property that the first entry has:

(i) a first counter containing a value <i s in the y th one of the first n sub-entries;

(ii) N counters each containing a value <i s in the z 1 , z 2 , . . . z N ones of the second n sub-entries;

(d) if there is a first entry having the first property, scheduling the call X:(y→z 1 , z 2 . . . z N ) for transmission in the timeslot corresponding to the first entry having the first property and updating the timeslot data structure by incrementing the first counter and each one of the N counters;

(e) if there is no first entry having the first property and if N=1, terminating the method by indicating that the call cannot be scheduled on the switch fabric; and,

(f) if there is no first entry having the first property and if N>1, dividing the call into two or more calls.

3. A method as defined in claim 1 , said dividing the call into two or more calls further comprising:

(a) sequentially examining each timeslot data structure entry to determine whether the examined entry has a second property that:

(i) a sub-sub-entry in the y th one of the first n sub-entries contains the initialization value;

(ii) at least one sub-sub-entry in the z 1 , z 2 , . . . z N ones of the second n sub-entries contains the initialization value;

(b) forming a list of all candidate timeslot data structure entries having the second property, and including with each list entry an output-ports-satisfied indication of the number of sub-sub-entries in that list entry's second n sub-entries which contain the initialization value;

(c) ordering the list in descending sequence of each list entry's output-ports-satisfied indication;

(d) sequentially examining the ordered list entries to detect a combination of list entries having a third property that:

(i) each one of the combination of list entries contains the initialization value in a y th one of the first n sub-entries;

(ii) each one of the combination of list entries contains the initialization value in at least one of the z 1 , z 2 . . . z N ones of the second n sub-entries;

(iii) the combination of list entries contains the initialization value at least once in each z 1 , z 2 . . . z N one of the second n sub-entries;

(e) if a combination of entries having the third property is detected, scheduling the call X:(y→z 1 , z 2 . . . z N ) for transmission in the timeslots corresponding to the detected combination of list entries having the third property and updating the timeslot data structure by assigning the non-initialization value to:

(i) the y th one of the first n sub-entries in each one of the detected combination of list entries;

(ii) each one of the z 1 , z 2 . . . z N ones of the second n sub-entries in the detected combination of list entries corresponding to those ones of the n output ports on which the call is scheduled for transmission; and,

(f) if no combination of entries having the third property is detected, terminating the method by indicating that the call cannot be scheduled on the switch fabric.

4. A method as defined in claim 1 , said dividing the call into two or more calls further comprising:

(a) sequentially examining each timeslot data structure entry to determine whether the examined entry has a second property that:

(i) a counter in the y th one of the first n sub-entries contains a value <i s ;

(ii) at least one counter in the z 1 , z 2 , . . . z N ones of the second n sub-entries contains a value <i s ;

(b) forming a list of all candidate timeslot data structure entries having the second property, and including with each list entry an output-ports-satisfied indication of the number of counters in that list entry's second n sub-entries which contain a value <i s ;

(c) ordering the list in descending sequence of each list entry's output-ports-satisfied indication;

(d) sequentially examining the ordered list entries to detect a combination of list entries having a third property that:

(i) each one of the combination of list entries contains a counter containing a value <i s in a y th one of the first n sub-entries;

(ii) each one of the combination of list entries contains a counter containing a value <i s in at least one of the z 1 , z 2 . . . z N ones of the second n sub-entries;

(iii) the combination of list entries contains a counter containing a value <i s at least once in each z 1 , z 2 . . . z N one of the second n sub-entries;

(e) if a combination of entries having the third property is detected, scheduling the call X:(y→z 1 , z 2 . . . z N ) for transmission in the timeslots corresponding to the detected combination of list entries having the third property and updating the timeslot data structure by incrementing:

(i) the counter in the y th one of the first n sub-entries in each one of the detected combination of list entries;

(ii) the counter in each one of the z 1 , z 2 . . . z N ones of the second n sub-entries in the detected combination of list entries corresponding to those ones of the n output ports on which the call is scheduled for transmission; and,

(f) if no combination of entries having the third property is detected, terminating the method by indicating that the call cannot be scheduled on the switch fabric.

5. A method as defined in claim 3 , further comprising, at regular intervals, rearranging all calls scheduled on the switch fabric.

6. A method as defined in claim 4 , further comprising, at regular intervals, rearranging all calls scheduled on the switch fabric.

7. A method as defined in claim 3 , further comprising maintaining a sequentially ordered list of the timeslots, and wherein said sequentially examining the timeslot data structure entries to determine if there is a first entry having the first property further comprises examining every entry in the sequentially ordered list of the timeslots in a predefined order commencing at a predefined position in the sequentially ordered list of the timeslots.

8. A method as defined in claim 4 , further comprising maintaining a sequentially ordered list of the timeslots, and wherein said sequentially examining the timeslot data structure entries to determine if there is a first entry having the first property further comprises examining every entry in the sequentially ordered list of the timeslots in a predefined order commencing at a predefined position in the sequentially ordered list of the timeslots.

9. A method as defined in claim 3 , further comprising maintaining a sequentially ordered list of the timeslots, and wherein said sequentially examining the timeslot data structure entries to determine if there is a first entry having the first property further comprises examining every entry in the sequentially ordered list of the timeslots once before re-examining any entry in the sequentially ordered list of the timeslots.

10. A method as defined in claim 4 , further comprising maintaining a sequentially ordered list of the timeslots, and wherein said sequentially examining the timeslot data structure entries to determine if there is a first entry having the first property further comprises examining every entry in the sequentially ordered list of the timeslots once before re-examining any entry in the sequentially ordered list of the timeslots.

11. A method as defined in claim 3 , further comprising maintaining a sequentially ordered list of the timeslots, and wherein said sequentially examining the timeslot data structure entries to determine if there is a first entry having the first property further comprises randomly searching the sequentially ordered list of the timeslots.

12. A method as defined in claim 4 , further comprising maintaining a sequentially ordered list of the timeslots, and wherein said sequentially examining the timeslot data structure entries to determine if there is a first entry having the first property further comprises randomly searching the sequentially ordered list of the timeslots.

13. A method as defined in claim 1 , wherein the initialization value is zero, and the non-initialization value is one.

14. A method as defined in claim 3 , further comprising terminating, in response to a call termination request, a call scheduled in one or more previously allocated timeslots, said terminating further comprising:

(a) decrementing the sub-sub-entry in the y th one of the first n sub-entries corresponding to each one of said previously allocated timeslots; and,

(b) decrementing the sub-sub-entries corresponding to the call's output ports in each of the z 1 , z 2 , . . . z N ones of the second n sub-entries corresponding to each one of said previously allocated timeslots.

15. A method as defined in claim 4 , further comprising terminating, in response to a call termination request, a call scheduled in one or more previously allocated timeslots, said terminating further comprising:

(a) decrementing the counter in the y th one of the first n sub-entries corresponding to each one of said previously allocated timeslots; and,

(b) decrementing the counters corresponding to the call's output ports in each of the z 1 , z 2 , . . . z N ones of the second n sub-entries corresponding to each one of said previously allocated timeslots.

16. A method as defined in claim 5 , wherein said rearranging further comprises removing all representations of a selected number of calls from the timeslot data structure, then repeating said updating of the timeslot data structure to re-represent each one of the selected number of calls in the timeslot data structure.

17. A method as defined in claim 6 , wherein said rearranging further comprises removing all representations of a selected number of calls from the timeslot data structure, then repeating said updating of the timeslot data structure to re-represent each one of the selected number of calls in the timeslot data structure.

18. A method as defined in claim 16 , wherein the selected number of calls further comprises calls previously divided into two or more calls.

19. A method as defined in claim 17 , wherein the selected number of calls further comprises calls previously divided into two or more calls.

20. A method as defined in claim 16 , wherein the selected number of calls further comprises calls scheduled in sequentially highest numbered timeslots.

21. A method as defined in claim 17 , wherein the selected number of calls further comprises calls scheduled in sequentially highest numbered timeslots.

22. A method as defined in claim 16 , wherein the selected number of calls are randomly chosen.

23. A method as defined in claim 17 , wherein the selected number of calls are randomly chosen.

24. A method as defined in claim 1 , further comprising, upon simultaneous receipt of a plurality of N-cast calls to be scheduled on the switch fabric:

(a) randomly selecting an unscheduled one of the plurality of calls;

(b) scheduling the randomly selected one of the plurality of calls in accordance with a sub-method comprising claim 1 (c) through claim 1 (f); and,

(c) repeating the method commencing with claim 24 (a) until all of the plurality of calls are scheduled.

25. A method as defined in claim 2 , further comprising, upon simultaneous receipt of a plurality of N-cast calls to be scheduled on the switch fabric:

(a) randomly selecting an unscheduled one of the plurality of calls;

(b) scheduling the randomly selected one of the plurality of calls in accordance with a sub-method comprising claim 1 (c) through claim 1 (f); and,

(c) repeating the method commencing with claim 25 (a) until all of the plurality of calls are scheduled.

26. A method as defined in claim 1 , further comprising, upon simultaneous receipt of a plurality of N-cast calls to be scheduled on the switch fabric:

(a) selecting an unscheduled one of the plurality of calls by round-robin selection from a list of the plurality of calls sorted in ascending sequence of input port number assigned to each one of the plurality of calls;

(b) scheduling the selected unscheduled one of the plurality of calls in accordance with a sub-method comprising claim 1 (c) through claim 1 (f); and,

(c) repeating the method commencing with claim 26 (a) until all of the plurality of calls are scheduled.

27. A method as defined in claim 2 , further comprising, upon simultaneous receipt of a plurality of N-cast calls to be scheduled on the switch fabric:

(a) selecting an unscheduled one of the plurality of calls by round-robin selection from a list of the plurality of calls sorted in ascending sequence of input port number assigned to each one of the plurality of calls;

(b) scheduling the selected unscheduled one of the plurality of calls in accordance with a sub-method comprising claim 1 (c) through claim 1 (f); and,

(c) repeating the method commencing with claim 27 (a) until all of the plurality of calls are scheduled.

Assignments (8)