Technique for dynamic scheduling of integrated circuit- and packet-switching in a multi-beam SS/TDMA system
First Claim
1. A method of assigning both circuit and packet traffic requests between grouped pairs of a plurality of N ground zones of a satellite communication system to each of a plurality of concurrent and synchronized satellite-switched time division multiple access (SS/TDMA) frame sequences, each frame sequence comprising M sequential time slots, the method comprising the steps of:
- a. representing the circuit traffic requests by an N×
N circuit traffic matrix ([ci,j ]) where an individual element (ci,j) represents a total number of requests for circuit traffic from a first ground zone i to a second ground zone j;
b. representing the packet traffic requests by an N×
N packet traffic matrix ([pi,j ]) where an individual element (pi,j) represents a total number of requests for packet traffic from a first ground zone i to a second ground zone j;
c. representing a plurality of ongoing circuits continuing from a previous time frame into a present time frame by M N×
N matrices ([oi,j ]) where an individual element (oi,j) in a Kth matrix represents the presence or absence of an ongoing circuit from zone i to zone j in time slot K;
d. representing circuit assignments by M N×
N circuit assignment matrices and packet assignments by M N×
N packet assignment matrixes ([ti,j ]) where an individual element (ti,j) in the Kth assignment matrix represents the presence or absence of a scheduled interconnection between a first ground zone i and a second ground zone j in slot K;
e. forming for the current slot being assigned an N×
N binary matrix ([c'"'"'i,j ]) by setting each element (c'"'"'i,j) to the value one if both the element (ci,j) in the circuit traffic matrix formed in step (a) is nonzero and there is no element of value one in row i or column j of the ongoing circuits matrix for the current slot as formed in step (c), and by setting all other elements of the binary matrix to zero;
f. forming for the current slot being assigned, a row sum (Ri) for each row in the binary matrix formed in step (e) and a column sum (Cj) for each column in said binary matrix, wherein the row sum is the sum of the element values in the row and is also the number of nonzero elements in said row, and the column sum is the sum of the element values in the column and is also the number of nonzero elements in said column;
g. forming for each new slot to be assigned, an N×
N cost matrix ([c"i,j ]) wherein each element (c"i,j) is an ordered pair comprising a first member less than or equal to a second member such that if an element (c'"'"'i,j) of said binary matrix formed in step (f) is zero, said first and second members of said ordered pair related thereto are both equal to zero, and if an element (c'"'"'i,j) of said binary matrix formed in step (f) is nonzero, said first member of said ordered pair is equal to the lesser of said row sum and said column sum formed in step (f) related thereto and said second member of said ordered pair is equal to the greater of said row and column sums;
h. determining a row i and a column j of a least-cost element in the cost matrix formed in step (g), wherein the least-cost element is an ordered pair such that a first member thereof is less than or equal to the first member of all nonzero ordered-pair elements in said cost matrix, and such that the second member thereof is less than or equal to the second member of all nonzero ordered pairs with a least first member;
i. assigning a least-cost switchpoint (i,j) in the current slot to a circuit, by setting to one the element at row i and column j of that circuit assignment matrix for the current slot, wherein said row i and said column j are those determined in step (h);
j. updating the row sums and the column sums formed in step (f), wherein a row sum is reduced by one if the row of said binary matrix related thereto contained a value of one in the column of the switchpoint determined in step (i); and
a column sum is reduced by one if the column of said binary matrix related thereto contained a value of one, in the row of the switchpoint determined in step (i);
k. updating said binary matrix formed in step (e) by setting to zero each element in the row i and the column j of said binary matrix chosen in step (h);
l. obtaining any remaining assignments for the current slot by reiterating steps (g)-(k) until said binary circuit matrix comprises only zero valued elements, or the number of circuit assignments made in the current slot equals a predetermined limit, or the total number of circuit assignments made in all slots in the current frame equals a predetermined limit;
m. updating the ongoing circuits matrix for the current slot by entering a one at each position (i,j) of the matrix for each new circuit assigned in the current slot determined in step (h);
n. assigning packets for the current slot by reiterating steps (e)-(l) wherein in step (e) the packet traffic matrix is accessed instead of the circuit traffic matrix, and wherein in step (i) the packet assignment matrix is accessed instead of the circuit assignment matrix, and wherein in step (l) references are to packet assignments instead of circuit assignments;
o. updating the circuit traffic matrix by subtracting one from each position of the circuit traffic matrix for which there is a one in the corresponding position of the circuit assignment matrix for the current slot;
p. updating the packet traffic matrix by subtracting one from each position of the packet traffic matrix for which there is a one in the corresponding position of the packet assignment matrix for the current slot;
q. obtaining assignments for any remaining slots in the current frame by reiterating steps (e)-(p) until all M slots are scheduled, or both the circuit traffic matrix and the packet traffic matrix have only zero valued elements as determined in step (1), or the predetermined limits on both the total number of circuit assignments and the total number of packet assignments in a frame have been reached, as determined in step (l); and
r. accessing by a controller of the circuit assignment matrices for the M slots of a frame and of the packet assignment matrices for the M slots of the frame, as assigned in step (i), for broadcasting the assignment schedule to the ground and configuring an interconnection in accordance with the assignment schedule, resetting both the circuit and packet assignments matrices thereafter, and setting to zero positions within the matrices corresponding to circuits which had been assigned and were ongoing, but have now terminated, and deducting blocked circuit requests from the circuit traffic matrix and adding newly arrived demand to the circuit and packet traffic matrices.
1 Assignment
0 Petitions
Accused Products
Abstract
The present invention relates to a technique for dynamic scheduling of integrated circuit- and packet-switching in accordance with rapidly changing demand in a multibeam satellite switched, time division multiple accessed (SS/TDMA) environment. It is equally applicable to terrestrial communication systems, or more broadly to any type of centralized scheduling system involving arbitration of contention for resources among a plurality of users or equipments. All of the scheduling is performed onboard the satellite by a scheduler (6, 8) under the direction of a controller (4). The controller contains all the information related to both circuit requests ([cij ]) and packet requests ([pij ]) in matrix form, where it constructs these matrices from requests for service from each zone to each zone on a frame-by-frame or possibly less frequent basis, which it receives from the ground via an order-wire facility. The scheduler performs, for each of the slots of a frame, a least-choice assignment of the circuit requests contained in the controller. The scheduler then applies the same least-choice procedure to assign packets to switch positions not already assigned to the circuit traffic. The least-choice assignment yields efficient bandwidth and transponder utilization. Provision is also made for prioritizing or preempting both the circuit and packet traffic employing a movable-boundary or other protocols. At the completion of both the circuit and packet assignments for a particular slot, the controller broadcasts the slot schedule to the earth stations.
176 Citations
7 Claims
-
1. A method of assigning both circuit and packet traffic requests between grouped pairs of a plurality of N ground zones of a satellite communication system to each of a plurality of concurrent and synchronized satellite-switched time division multiple access (SS/TDMA) frame sequences, each frame sequence comprising M sequential time slots, the method comprising the steps of:
-
a. representing the circuit traffic requests by an N×
N circuit traffic matrix ([ci,j ]) where an individual element (ci,j) represents a total number of requests for circuit traffic from a first ground zone i to a second ground zone j;b. representing the packet traffic requests by an N×
N packet traffic matrix ([pi,j ]) where an individual element (pi,j) represents a total number of requests for packet traffic from a first ground zone i to a second ground zone j;c. representing a plurality of ongoing circuits continuing from a previous time frame into a present time frame by M N×
N matrices ([oi,j ]) where an individual element (oi,j) in a Kth matrix represents the presence or absence of an ongoing circuit from zone i to zone j in time slot K;d. representing circuit assignments by M N×
N circuit assignment matrices and packet assignments by M N×
N packet assignment matrixes ([ti,j ]) where an individual element (ti,j) in the Kth assignment matrix represents the presence or absence of a scheduled interconnection between a first ground zone i and a second ground zone j in slot K;e. forming for the current slot being assigned an N×
N binary matrix ([c'"'"'i,j ]) by setting each element (c'"'"'i,j) to the value one if both the element (ci,j) in the circuit traffic matrix formed in step (a) is nonzero and there is no element of value one in row i or column j of the ongoing circuits matrix for the current slot as formed in step (c), and by setting all other elements of the binary matrix to zero;f. forming for the current slot being assigned, a row sum (Ri) for each row in the binary matrix formed in step (e) and a column sum (Cj) for each column in said binary matrix, wherein the row sum is the sum of the element values in the row and is also the number of nonzero elements in said row, and the column sum is the sum of the element values in the column and is also the number of nonzero elements in said column; g. forming for each new slot to be assigned, an N×
N cost matrix ([c"i,j ]) wherein each element (c"i,j) is an ordered pair comprising a first member less than or equal to a second member such that if an element (c'"'"'i,j) of said binary matrix formed in step (f) is zero, said first and second members of said ordered pair related thereto are both equal to zero, and if an element (c'"'"'i,j) of said binary matrix formed in step (f) is nonzero, said first member of said ordered pair is equal to the lesser of said row sum and said column sum formed in step (f) related thereto and said second member of said ordered pair is equal to the greater of said row and column sums;h. determining a row i and a column j of a least-cost element in the cost matrix formed in step (g), wherein the least-cost element is an ordered pair such that a first member thereof is less than or equal to the first member of all nonzero ordered-pair elements in said cost matrix, and such that the second member thereof is less than or equal to the second member of all nonzero ordered pairs with a least first member; i. assigning a least-cost switchpoint (i,j) in the current slot to a circuit, by setting to one the element at row i and column j of that circuit assignment matrix for the current slot, wherein said row i and said column j are those determined in step (h); j. updating the row sums and the column sums formed in step (f), wherein a row sum is reduced by one if the row of said binary matrix related thereto contained a value of one in the column of the switchpoint determined in step (i); and
a column sum is reduced by one if the column of said binary matrix related thereto contained a value of one, in the row of the switchpoint determined in step (i);k. updating said binary matrix formed in step (e) by setting to zero each element in the row i and the column j of said binary matrix chosen in step (h); l. obtaining any remaining assignments for the current slot by reiterating steps (g)-(k) until said binary circuit matrix comprises only zero valued elements, or the number of circuit assignments made in the current slot equals a predetermined limit, or the total number of circuit assignments made in all slots in the current frame equals a predetermined limit; m. updating the ongoing circuits matrix for the current slot by entering a one at each position (i,j) of the matrix for each new circuit assigned in the current slot determined in step (h); n. assigning packets for the current slot by reiterating steps (e)-(l) wherein in step (e) the packet traffic matrix is accessed instead of the circuit traffic matrix, and wherein in step (i) the packet assignment matrix is accessed instead of the circuit assignment matrix, and wherein in step (l) references are to packet assignments instead of circuit assignments; o. updating the circuit traffic matrix by subtracting one from each position of the circuit traffic matrix for which there is a one in the corresponding position of the circuit assignment matrix for the current slot; p. updating the packet traffic matrix by subtracting one from each position of the packet traffic matrix for which there is a one in the corresponding position of the packet assignment matrix for the current slot; q. obtaining assignments for any remaining slots in the current frame by reiterating steps (e)-(p) until all M slots are scheduled, or both the circuit traffic matrix and the packet traffic matrix have only zero valued elements as determined in step (1), or the predetermined limits on both the total number of circuit assignments and the total number of packet assignments in a frame have been reached, as determined in step (l); and r. accessing by a controller of the circuit assignment matrices for the M slots of a frame and of the packet assignment matrices for the M slots of the frame, as assigned in step (i), for broadcasting the assignment schedule to the ground and configuring an interconnection in accordance with the assignment schedule, resetting both the circuit and packet assignments matrices thereafter, and setting to zero positions within the matrices corresponding to circuits which had been assigned and were ongoing, but have now terminated, and deducting blocked circuit requests from the circuit traffic matrix and adding newly arrived demand to the circuit and packet traffic matrices. - View Dependent Claims (2)
-
- 3. comparing the result of step (s) (2) to a subsequent ordered pair from the least-cost traffic matrix;
-
4. reiterating steps (s) (2) and (s) (3) N2 -1 times. 3. An onboard satellite switching system responsive to both circuit transmission requests and packet transmission requests from a plurality of N separate ground zones for assigning both said circuit and packet requests in each succeeding time slot of a plurality of time slots forming a single time frame, thereby likewise continuously assigning circuit and packet requests in each subsequent time frame, said satellite switching system comprising
a controller (4) responsive to said circuit and packet requests on a frame-by-frame basis for first initializing and subsequently terminating the assignment of circuit transmission requests and second initializing and subsequently terminating the assignment of packet transmission requests in each time slot of said single time frame, said controller repeating said initializing and terminating for subsequent time slots forming subsequent time frames; -
a traffic matrix circuit (6) responsive first to said circuit transmission requests and a plurality of ongoing circuit matrices from said controller for formimg a cost matrix related thereto and responsive second to said packet transmission requests from said controller for forming a cost matrix related thereto; and a least-cost selection circuit (8) responsive first to the cost matrix formed in relation to said circuit transmission requests for selecting a least-cost circuit assignment and using said least-cost circuit assignment to update the cost matrix and relaying said least-cost circuit assignment back to said traffic matrix circuit to be used in updating the circuit traffic matrix and one of a plurality of ongoing circuit matrices, and responsive second to the cost matrix formed in relation to said packet transmission requests for selecting a least-cost packet assignment and using said least-cost packet assignment to update the cost matrix and relaying said least-cost packet assignment back to said traffic matrix circuit to be used in updating the packet traffic matrix. - View Dependent Claims (6)
-
Specification