Based on network circulation formulation, the existence of feasible beam-to-beam switching modes for a satellite-switched time-division multiple access system is completely and transparently proved, where simultaneous transmissions on several carriers in each spot-beam are configured. Showing the linear independence of all but one augmented switching modes, a new bound of mn+2 is obtained on the number of switching modes, where m and n are the number of up-link and down-link beams, respectively. The time complexity for finding the whole sequence of switching modes and for finding the initial switching mode are improved to O(m/sup 2/n/sup 2/) and O(min(/spl radic/K,(m+n)/sup 2/3/)mn), respectively. Practical implementation considerations are discussed.

A unified algorithmic framework for time-optimal transmission scheduling is obtained for satellite-switched time-division multiple access systems with M uplink and N downlink beams. System capability may vary from the basic configuration of one carrier per beam to complex configurations of variable number of carriers for each beam and variable transmission rate for each beam. The computational complexity for time-optimal transmission scheduling remains strongly polynomial at O(M/sup 2/N/sup 2/) and the number of switching configurations is at most MN+1 for all system configurations considered.

The asymmetrical multiconnection three-stage rearrangeable Clos network is considered, where, in general, many-to-many connections are allowed between input and output terminals. The problem of routing the connections over the switches is efficiently solved. The computational complexity is improved from O(mf 3) to O(f 4) using a network flow model for the routing problem, where f is the number of first-stage switches and m is the number of second-stage switches; the number of third-stage switches is assumed to be of the same order as f. Note that the O(f 4) complexity is independent of the number of second-stage switches. Using an appropriate data structure, the computational complexity of an edge-coloring approach to the routing problem is lowered from O(mK 2) to O(m(f 2 + K log K)), where K is the aggregate capacity of the interconnecting links between all first-stage switches and a second-stage switch; the aggregate capacity of the interconnecting links between a second-stage switch and all third-stage switches is assumed to be of the same order as K. This makes the edge-coloring approach competitive for small values of m and K. © 1998 John Wiley & Sons, Inc. Networks 32: 77–83, 1998

Bipartite graph and network circulation formulations of the TDM switching assignment problem are compared; a correct proof is given of the existence of a feasible circulation in the network model corresponding to a valid switching assignment. Dividing users into groups, an O(K/sup 4/) algorithm for solving the assignment problem is described where K is the number of TDM lines, and a bound is derived on the number of switching configurations.>