A method of flow control that requires very few buffers to be allocated at each node to virtual circuits (or sessions) that have to transverse many links is described. Transmissions are scheduled using the golden ratio policy of A. Itai and Z. Rosberg (1984). It is shown that the buffer requirements of a session grow at most logarithmically with the number of slots allotted to it. As an immediate consequence, intra-network delays are bounded.>

The diameter of a class of random directed graphs in which the outdegree of each vertex is constrained to be exactly k is examined. Vertices connect themselves to k other distinct vertices with outwardly directed edges, all possible sets of k vertices being chosen with equal probability. It is shown that the diameter of such a random graph almost surely takes on only one of two values.>

In this paper we derive an approximation for the mean response time of a multiple queue system in which shortest queue routing is used. We assume there are Κ identical queues with infinite capacity and service times that are exponentially distributed. Arrivals of jobs to this system are Poisson and are routed to a queue of minimal length. We develop an approximation which is based on both theoretical and experimental considerations and, for Κ ≤ 8, has an relative error of less than one half of one percent when compared to simulation. For Κ = 16, the relative error is still acceptable, being less than 2 percent. An application to a model of parallel processing and a comparison of static and dynamic load balancing schemes are presented.

A model of a packet radio network in which transmitters with range R are distributed according to a two-dimensional Poisson point process with density D is examined. To ensure network connectivity, it is shown that pi R/sup 2/D, the expected number of nearest neighbors of a transmitter, must grow logarithmically with the area of the network. For an infinite area there exists an infinite connected component with nonzero probability if pi R/sup 2/D>N/sub 0/, for some critical value N/sub 0/. It is shown that 2.195>

A sequence of upper and lower bounds for theQfunction defined asQ(x)= 1/ \sqrt{2 \pi} \int_{x}^{\infty} \exp[(-y^{2})/2]dyis developed. These bounds are shown to be tighter than those most commonly used.