A Model of Periodic Acknowledgment

Wednesday, November 20, 2002 - 17:30
TH 331
Alexandre Brandwajn UC Santa Cruz

We study a problem abstracted from modeling a multicast protocol. In our model, messages generated by a single source are simultaneously forwarded to a set of receivers where they are independently processed. We assume a state-dependent message arrival rate and memoryless service time distributions. The receivers may process messages at different average rates. Messages processed by all receivers are periodically acknowledged and cleared from the system. Due to finite buffer space, the total number of non-acknowledged messages in the system is limited. Our focus in this study is on the number of messages cleared at acknowledgement time. The problem under consideration bears resemblance to a fork/join process with heterogeneous servers, used in the study of multiprocessing computer systems. Our model includes the additional features of finite buffer space and delayed periodic departure of completed jobs. Even without these features, the resulting type of queueing model has no known closed form solution in the general case of more than two servers. Because the arrival processes to the servers are correlated, the model is difficult to decompose. We propose a relatively simple decomposition technique and a fixed-point iteration scheme. In our approach, we consider each receiver (server) in isolation, and we account for the influence of other receivers through the probability that a given number of messages can be cleared at acknowledgement time. We derive elementary differential equations for the number of messages processed by a receiver. These equations involve the conditional probability of the number of messages not yet processed given the number of messages waiting to be cleared. We compute an approximate solution using the conditional probability obtained from a model with exponentially distributed acknowledgement periods. Our numerical results for the average number of messages cleared at acknowledgment time are typically within a few percent of simulation midpoints.


Alexandre Brandwajn holds an Ingenieur Civil des Telecommunications degree from the Ecole Nationale Suprieure des Telecommunications in Paris, and a Docteur d'Etat degree in Computer Science from the University of Paris VI. He worked as researcher at the Institut de Recherche en Informatique et Automatique (IRIA), France, then he was on the Faculty of the Ecole Nationale Superieure des Telecommunications in Paris, where he directed a project in adaptive computer architecture. In 1979, he joined Amdahl Corporation in Sunnyvale, California, where he was a Senior Computer Architect, and later Manager of Systems Analysis group. Since 1985, he is a Professor of Computer Engineering at the University of California at Santa Cruz. His current research interest include efficient solution of systems with large state space, multimedia/networking problems, and applications of priority systems with finite capacity.