ONBOARD DEMAND SCHEDULING OF A MULTIBEAM SS/TDMA SATELLITE WITH INTEGRATED CIRCUIT AND PACKET SWITCHING (QUEUEING THEORY, SIMULATION, COMBINATORIAL OPTIMIZATION)

This research investigates a spacecraft-switched time division multiple access communications satellite system that achieves efficient bandwidth and system utilization by frequency reuse with multibeams, by integrated circuit and packet switching, and by onboard demand scheduling of beam interconnections on a frame-by-frame basis. A major aim is to formulate a scheduling strategy that yields high utilization, subject to achieving acceptable levels of circuit blocking and packet queueing delay, and that is suitable for onboard use by meeting given time and complexity constraints.; Considered is the following scheduling problem. Given an onboard N x N switch, K transponders, and an N x N traffic demand matrix, determine a switchpoint assignment for each slot of a frame that maximizes the number of requested switchpoints assigned. We formulate this problem as an integer program, and prove that it can not be converted to a single-commodity network flow problem. We show how to convert the problem to a multi-index transportation problem, and also how to solve it using Lagrangean relaxation and subgradient optmization. Weaker forms of optimality are also considered. We introduce a suboptimum Least-choice method suitable for onboard use, and that achieves utilization greater than 99 percent of optimum in extensive simulation.; A generalized software simulator of the onboard scheduling and switching operations was implemented. For this effort, we derive blocking probability formulae for an M/M/S/S queueing system with framing. Over 100 large-scale simulations were made of a system with a 5 x 5 switch, 100 slots per frame, and two-way circuit capability. Each run simulated 61.1 hours of circuit traffic only, or 83.3 minutes of integrated traffic. Simulation results include the following. To maximize average circuit load, while minimizing packet queueing delay, limit circuit capacity to about 82 percent of total capacity. With equal intrazone and interzone two-way circuit switchpoint capacity, large packet queueing delays result for intrazone traffic. Of several means investigated, the Static and Dynamic Row/Column circuit blocking policies reduce queueing delay markedly. A system with 0.01 circuit blocking probability, 0.01 seconds average, and 7 seconds maximum, packet queueing delay, and 99.9 percent of the time with delay under 1 second, has utilization over 0.70; with blocking probability 0.02 this becomes 0.79. An integrated system has utilization about 8-12 percent above that of a pure circuit system with comparable blocking.