Patent ID: 7212524

Claim:
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.