Time-Constrained Communication in Multiple Access Networks

Kurose, James F.

The characteristics of time-constrained communication applications,' such as packetized voice, differ significantly from those of standard data communication applications. First, messages not received within a fixed amount of time after their generation at a sending station are considered lost. Secondly, a certain amount of message loss is tolerable. In this thesis we address the problem of supporting time constrained communication applications in a multiple access network. The principal contributions of this thesis fall into two categories. The first contribution is the development and analysis of a new class of protocols for supporting multi-access time-constrained communication. These protocols are based on a generalization of the time window mechanism and provide a family of network-wide message transmission scheduling disciplines based on message generation times. The problem of determining the optimal elements of the protocol's window selection policy is addressed. A semi-markov decision model is formulated for protocol operation and the optimal elements of the windowing policy are found to be both simple and intuitive. The extension of the protocol for transmitting both time-constrained and non-time-constrained messages is considered. In our scheme, time-constrained traffic, when transmitted, receives preemptive priority over other classes of traffic. Several novel analytic performance models are developed and validated through simulation. The protocol's time-constrained performance is found to critically depend on its imposed scheduling function and is significantly better under the optimal windowing policy elements than under other policy elements. For multiple classes of traffic, our results indicate that trading time-constrained message loss against the average delay of non-time-constrained traffic is not usually a viable option. The second major contribution of this thesis is the development of a systematic, formal approach towards distributed optimization via a fictitious resource sharing paradigm and a decentralized "microeconomics" solution to the resource sharing problem. This approach, which draws on previous work In mathematical economics, is successfully used to compute the optimum transmission probabilities for both the time window and Slotted Aloha protocols. Interestingly, several network mechanisms, such as flow control and priorities, are found to emerge naturally from this approach.



More About This Work

Academic Units
Computer Science
Department of Computer Science, Columbia University
Columbia University Computer Science Technical Reports, CUCS-120-84
Published Here
February 17, 2012