Browse Prior Art Database

Optimal Time Slot Assignment Algorithm for Satellite Switching Systems

IP.com Disclosure Number: IPCOM000053035D
Original Publication Date: 1981-Aug-01
Included in the Prior Art Database: 2005-Feb-12
Document File: 3 page(s) / 19K

Publishing Venue

IBM

Related People

Bongiovanni, G: AUTHOR [+3]

Abstract

A scheduling algorithm is described which achieves the minimum transmission time for any traffic matrix.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 3

Optimal Time Slot Assignment Algorithm for Satellite Switching Systems

A scheduling algorithm is described which achieves the minimum transmission time for any traffic matrix.

In a satellite-switched time-division multiple access (SS/TDMA) system, a satellite has several spot-beam antennas and a solid-state RF switch which provides connections between uplink and downlink beams to accommodate the traffic demand. A TDMA frame is divided into a number of switching modes, and to each switching mode a fixed on-board switch configuration is assigned. The traffic demand is characterized by a traffic matrix D, where an entry d(ij) in D represents the traffic demand from uplink beam i to downlink beam j, measured in units of slot time. A scheduling scheme then depicts a way to decompose the given traffic matrix D into distinct component "switching matrices", i.e., D = D(1) + D(2) +...+D(L), in such a way that each D(i) is a matrix with, at most positive entry in each row and each column.

The largest entry in a switching matrix D(i) dictates the "duration" of the switching mode corresponding to D(i), and is called the switching duration of D(i), denoted by absolute value of D. To maximize transponder through one must minimize the total duration L Sigma i=I absolute value of D(i) needed the the complete traffic matrix D.

In general, let M, N, K denote respectively the number of uplink beams, downlink beams and transponders, where 1 < = K < or = to min (M,N). We also consider the symmetric case when M = N and 1 < or = K< or = N. An optimal schedule algorithm (in the sense of minimizing the total duration) is described. All results can be generalized to the asymmetric case when M, N need not be the same and 1< or = K < or = min(M,N). Details can be found in [*].

Given a traffic matrix D, let T be the sum of all entries. In D, we call a row or a column a line. The sum of entries in a line is called the line sum. Let C be the maximum line sum in the matrix D. Let S = max ( T over K, C).

Theorem 1. For any NxN traffic matrix D, with total traffic T and maximum line sum C, and for any K, 1< or = K < or = N, the total duration Sigma i absolute value scheduling algorithm satisfies the following inequality: Sigma (i) absolute value of D(i) > or = S.

In particular, if a scheduling algorithm always generates total duration equal to S, then it is optimal.

Definition. A line in D is said to be a critical line if its sum equals S.

Definition. A set of K positive entries (x(i), x(2), ..., x(K)) in D is called a system of K representatives (SKR for short) if they are distinct and if there is, at most, one such entry in each row and each column.

Definition. A...