We introduce a class of Markov models, termed best-effort networks, designed to capture performance indices such as mean transfer times in data networks with best-effort service. We introduce the so-called min bandwidth sharing policy as a conservative approximation to the classical max-min policy. We establish necessary and sufficient ergodicity conditions for best-effort networks under the min policy. We then resort to the mean field technique of statistical physics to analyze network performance deriving fixed point equations for the stationary distribution of large symmetrical best-effort networks. A specific instance of such networks is the star-shaped network which constitutes a plausible model of a network with an overprovisioned backbone. Numerical and analytical study of the equations allows us to state a number of qualitative conclusions on the impact of traffic parameters (link loads) and topology parameters (route lengths) on mean document transfer time.

The impact of adding certain families of generalized quantifiers to first-order logic (FO) on the asymptotic behavior of sentences is studied. All the results are stated and proved for languages disallowing free variables in the scope of generalized quantifiers. For a class K of finite structures closed under isomorphism, the quantifier Q/sub K/ is said to be strongly monotonic, sm, if membership in the class is preserved under a loose form of extensions. The first theorem (O/1 law for FO with any set of sm quantifiers) subsumes a previous criterion for proving that almost no graphs satisfy a given property. A O/1 law for FO with Hartig quantifiers (equicardinality quantifiers) and a limit law for a fragment of FO with Rescher quantifiers (expressing inequalities of cardinalities) are also established. It is also proved that the O/1 law fails for the extension of FO with Hartig quantifiers if the above syntactic restriction is relaxed, giving the best upper bound for the existence of a O/1 law for FO with Hartig quantifiers.>

An exact analysis is given of the main parameters that characterize the properties of the Capetanakis-Tsybakov-Mikhailov collision resolution algorithm with the free-access (continuous input) protocol. In particular, the distributions of the collision resolution interval, the delay experienced by a packet, and the state of the top level of the stack that is maintained by the algorithm are determined.

A tandem queueing system with constant slotted service times and threshold control is modeled and analyzed in this paper. The input to the first queue is controlled by the buffer occupancy of the second queue. When the second queue has more than No customers, the input to the first queue will be rejected. The input to the second queue consists of the output from the first queue and an external input which is assumed to be Poisson distributed. The behavior of such a queueing system is analyzed and portrayed in graphs. The threshold control rejects input traffic to the first queue and avoids congestion at the second queue. As a result, the delay for an arrival to be serviced by both of the queues is much lower than the case without threshold control. As No increases, the system behavior approaches the case of the system without threshold control. Such a queueing model is motivated by congestion control in a computer network. An example is given to illustrate the applications of gateway flow control in internet- working.

A single-server processor-sharing system with M job classes is analyzed in the steady state.The scheduling strategy considered divides the total processor capacity in unequal fractions among the different job classes.More precisely, if there are N~jobs of classj in the system, j = 1, 2 ..... M, each class k job receives a fraction gh/(~M.~giN~) of the processor capacity.Earlier analyses of this system are shown to be incorrect and new expressions for the conditional expected response times Wk(t) of class k jobs with required service time t are obtained (for general required service time distributions).These yield the asymptotic behavior of W~(t) as t ~ oo and rather simple formulas in the exponential case.The unconditional average response times are also obtained.

In this study, we are concerned with a simple error control protocol, the "send and wait" protocol, which uses the classical technique of positive acknowledgment and time-out periods. We first analyze the influence of the time-out on the packet transmission rate. Then we use a queuing analysis to obtain the ergodicity condition and to compute the buffer queue length probability distribution. Finally we compute buffer overflow when a finite number of packets are allowed to enter the node. This analysis allows us to obtain optimum values of the time-out in order to maximize throughput, or to minimize average transit delay through the node or buffer overflow probabilities.

The purpose of this paper is to analyze and optimize the behavior of the broadcast channel for a packet transmission operating in the slotted mode Mathematical methods of Markov chain theory are used to prove the inherent lnstablhty of the system If no control is apphed, the effective throughput of the system will tend to zero tf the population of user terminals ~s sufficiently large Two classes of control pohcles are examined, the first acts on admissions to the channel from active terminals, and the second modifies the retransmlss~on rate of packets In each case sufflc~ent conditions for channel stability are given.In the case of retransm~sslon controls it is shown that only pohcles which assure a rate of retransmlsslon from each blocked terminal of the form off = 1/n, where n is the total number of blocked terminals, will yield a stable channel It ts also proved that the optimal pohcy which maximizes the maximum achievable throughput wtth a stable channel IS of the formf = (1 -k)/n Simulations illustrating channel lnstabdlty and the effect of the opnmal control are prowded KEY WORDS AND PHRASES computer networks, packet swnchlng, broadcast channel, optimal control CR CATEGORIES 4 3, 4 6, 5 5, 6 2, 6 35 ~t has to repeat the transmission untd it succeeds Either a termmal which is not blocked