TIME CONSTRAINED AND MULTIACCESS COMMUNICATIONS (PACKET-SWITCHED NETWORKS, SCHEDULING, QUEUES IMPATIENCE, CONTENTION, RESOLUTION, ALGORITHMS)

Time constrained communications, such as packetized voice, differs from data communications in two important respects. Firstly, messages not received within a certain deadline after their generation at the transmitting station are considered lost and, secondly, a certain amount of message loss is tolerable. The problem of a large number of occasionally active users attempting to share a common channel, on the other hand, is referred to as the multiaccess problem. This dissertation is primarily concerned with time constrained and multiaccess communications. We first consider a ternary feedback random access channel with Poisson arrivals without time constraints. It is shown that 0.5 is an upper bound to the throughputs of all degenerate intersection and first-come first-served (FCFS) collision resolution algorithms. We then consider a ternary feedback channel for which each packet has the same deadline of K time units. A window protocol is devised with the aim of minimizing the percentage of packets lost (as a result of exceeding their respective deadlines) for a Poisson arrival process with parameter (lamda). A genie argument is used to obtain a lower bound on the losses for any algorithm for a range of K. Finally, we consider the problem of scheduling packets when each of them has a different deadline given by a general independent distribution. Here, we model the time constrained multi-access network as a single server queue with impatient customers. We define a scheduling policy to be optimal if the expected packet losses under this policy is lower than or equal to any other scheduling policy. We also define an STE (shortest time to extinction) scheduling policy as one which schedules for service the packet with the earliest deadline first. We show that the STE policy is optimal for a class of single server queues. Also shown is that, for a wider class of queues, the optimal scheduling policy comes from the class of STE policies with inserted idle times, referred to as STE(I) policies. The performance of the STE and FCFS policies is compared for one of the queues