STOCHASTIC FLOW OF MESSAGES AND ITS EFFICIENT TRANSMISSION THROUGH COMMUNICATION NETS
Kenji Onaga · Illinois Digital Environment for Access to Learning and Scholarship (University of Illinois at Urbana-Champaign) · 1965
Efficient transmission of stochastic flow of messages through storeand-forward type communication nets is discussed in this paper.In order to express quality or performance of flow quantitatively, we define the penalty index P(t) as the sum of total time delay D(ty), total transmission cost K(ty), and total transmission redundancy R(\|f) with certain proportions of penalty.A necessary and sufficient condition of minimum penalty flow for the fixed flow value is obtained in Theorem 4 and is demonstrated by a simple example.I .INTRODUCTION As demonstrated in arrivals and services for telephone calls, tele graph messages, and customers at a supermarket, generation of information or service demands and time required for services are in general of stochastic nature.Stochastic flow is flow of such messages or service demands through nets.So far study of communication nets has been mainly focused on steady (or non-stochastic) flow.In the study of stochastic systems, average prop erties are the first thing to be concerned.Although by considering average flow, we can reduce properties of stochastic (or unsteady) flow to these of steady flow, there are many differences at a closer look.As a concrete example we take the following digital transmission of information through store-and-forward type communication nets.II.THE MODEL: ASSUMPTIONS AND NOTATIONS In this section we set up a mathematical model of the communication net by furnishing assumptions quantitatively and notations explicitly so that we can work on the model henceforth.1.The message originates from the information source in a coded form and is fed to the net for transmission to the destination or sink.From the source a message occurs with constant probability in a unit time interval.For any time t the probability that a message occurs in the small interval (t, t + At) is A • At + 0(At) , where X is a constant and 0(At) is a quantity of smaller order of magnitude than At, and the probability that more than one message occurs is also smaller order of magnitude than At.Then it can be shown that the distribution function A(t) of inter arrival time t of messages is given by A(t) = 1 -e ^,t.The average number of messages per second originating from the source is A. This input is called a Poisson distributed or a Poisson input because the number of messages in any time interval T has a poisson distribution with mean XT. 2. The length n of the message is governed by an exponential dis tribution function B(n) = 1 -e where l/|l is the average length of the messages in bits.Throughout this paper we assume that the message length and the inter arrival time have no influence upon each other, in other words two distribution functions A(t) and B(n) are statistically independent.3.At each station each outgoing channel has its own unlimited storage for incoming messages and the messages form a waiting line, called a queue.Messages in a queue are processed for transmission according to the firstcome first-served principle.