The Control of Multimedia Communication Processors: for Messages with Time Constraints
December 31, 1988
This thesis deals with the message switching problem in a multiple networks environment with time constraints for each message class. The sojourn time distribution for an overtake free path are first derived for two classes of routing algorithms, namely, the shortest path algorithms and the optimal routing algorithms, based on Kleinrock’s assumptions for standard queueing systems. The estimates of 99% or other percentile of the delay distributions are derived. They are converted into sequences which represent the "reward" one gets by operating one of the subnetwork (media) with routing strategies specified. Based on this reward sequence we formulate the problem of message allocation into the famous "Multi-armed bandit problems" in which the optimal policy has been known to be operating the arm of the bandit with the "Gittens index". A simpler index is found by the non-increasing properties of our reward sequences. Our algorithms switch messages based on this index rule to the maximal-current-reward (MCR rule) network. Our algorithms are suitable for distributed implementation on a multimedia metwork environment. We show that the indicies can be computed in time O (n log n) by employing the fast Fourier transform algorithms to compute sample points for delay distribution. The algorithms have been simulated by QNAP2 and the simulation results show that our algorithms give better delay performance than most conventional routing algorithms do. It also reduces the portion of messages that are not able to meet the time constraints.