Dynamic control and accuracy of thepi-persistent protocol using channel feedback

The p_i-persistent protocol is based on a probabilistic scheduling mechanism (see Mukherjee and Meditch, 1988). The authors further develop the protocol to make it easily implementable, by allowing it to be sensitive to changing load conditions. They study various properties of a simple algorithm which stations execute independently by using channel feedback information. This results in a fully distributed control mechanism that continuously adjusts the station probabilities p_i at their proper levels as governed by the offered traffic. An extensive simulation model has been developed to study properties of this control mechanism such as p_i settling time and accuracy, behavior under step changes in traffic load, effect of injection of additional packets, and effect of various parameters associated with the underlying algorithm. These experiments indicate that this algorithm is suitable for implementing the protocol     

A dynamic bandwidth-allocation-based priority mechanism for thepi-persistent protocol for MAN's

While a variety of medium access protocols have been proposed for metropolitan area networks (MANs), the problem of handling multipriority traffic effectively in these networks remains open. The authors present a simple and effective priority mechanism for an existing MAN protocol known as the p_i-persistent protocol, a probabilistic scheduling scheme that has been shown to be suitable for applications requiring large bandwidth over long, repeater-free distances. The mechanism works by clipping the low-priority stations in a controlled manner, thereby increasing the bandwidth available to the high-priority stations. This mechanism operates entirely within the framework of the basic p_i-persistent protocol and may be easily tailored to achieve specific performance goals by selection of a single operating parameter. A multipriority version of a distributed algorithm by which the stations can update their operating parameters and adapt to changing network conditions dynamically is also presented     

Delay analysis of a packet voice multiplexer by the ΣDi/D/1 queue

The performance of a statistical multiplexer whose inputs consist of a superposition of voice packet streams is studied. The delay for such a system is analyzed by solving the ΣD_i/ D/1 queue. The analytic method can be used to find the approximate mean delay for an arbitrarily large number of trunks and the approximate delay distribution when the number of trunks is less than 100. An efficient hybrid simulation of the packet voice multiplexer which can be used to find the delay distribution for a large number of trunks is presented. In addition, easily computable error bounds for the present approximation are provided, and the accuracy of the M/ D/1 approximation is investigated     

Optimal probability-of-error thresholds and performance for twoversions of the sign detector

Expressions are obtained for specifying the optimal error probability (minimum P_e) thresholds λ₀₁ and λ₀₂ for the traditional and modified sign detectors, respectively. These thresholds are shown to depend on the parameters p, P₁, and M where: M is the number of observations z_i used in the test statistic; P₁=P(H₁ ) is the prior probability for hypothesis H₁ that signal s₁ is present and 1-P₁ =P(H₀) corresponds to the hypothesis H₀ that signal s₀ is present; and p=Pr{z_i⩾0|H₁} with s₀=0 for the traditional sign detector and p=Pr{z_i⩾λ|H₁ }=Pr{z_i<λ|H₀} with λ =(s₀+s₁)/2 for the modified sign detector. The expressions for λ₀₁ and λ₀₂, are given explicitly, and shown to be independent of P₁ for sufficiently large M. Optimal P_e versus M performance curves, corresponding to both versions of the sign detector, are obtained for a representative range of values for p and P₁     

An approximate performance fairness analysis of thepi-persistent protocol with destination release

Sufficient conditions are derived for achieving the two most important fairness criteria in the design of access protocols for high-speed metropolitan area networks (MAN), the delay and throughput fairness criteria, a probabilistic scheduling scheme, known as the p_i-persistent protocol is considered, which has been shown to be suitable for applications requiring large bandwidth over long repeater-free distances and also amenable to an approximate analytical performance evaluation. It is found that the throughput fairness criterion is easier to achieve than its delay counterpart. The delay fairness, when achieved, induces approximate throughput fairness. The current practice in the field of protocol design for unidirectional bus MANs appears to focus almost exclusively on the throughput fairness. For example, in the DQDB protocol, although a bandwidth balancing function exists, balancing delay performance has never been dealt with     

Capture probability in a mobile packet radio system

The probability of q_i of successful packet reception when i users transmit simultaneously in a mobile packet radio system is shown to decrease monotonically with i for a number of commonly used capture and spatial distribution models, with no fading. Examples of both noiseless and noisy systems in which q_i is not monotonically decreasing with i are also given     

Effect of hot-electron injection of high-frequency characteristicsof abrupt In0.52(Ga1-xAlx)0.48As/InGaAs HBT's

The effect of hot-electron injection energy (E_i) into the base on the high-frequency characteristics of In_0/52(Ga_1-xAl_x)_0.48 As/InGaAs abrupt heterojunction bipolar transistors (HBTs) is investigated by changing the composition of the emitter. There exists an optimum E_i at which a maximum current gain cutoff frequency (ft) is obtained. Analysis of hot-electron transport in the base and collector by Monte Carlo simulation is carried out to understand the above phenomenon. The collector transit time (τ_c ) increases with E_i, because electrons with higher energy transfer from the Γ valley into the upper L and X valleys. At first, the base transit time (τ_b ) decreases with E_i at the low E_i region. However, τ_b does not decrease monotically with E_i, because of the nonparabolicity in the energy-band structure of InGaAs. Consequently, there exists a minimum in the sum of τ_b and τ_c , in other words a maximum f_t, at an intermediate value of E_i     

Distribution of the lifetime of consecutive k-within-m-out-of-n:F systems

The distribution of the lifetime (MTTF) of any consecutive k -within-m-out-of-n:F system, with independent exponentially distributed component lifetimes, is shown to be a convex combination of the distributions (MTTFs) of several convolutions of independent random variables, where each convolution represents a distinct path in the evolution of the system's history, and where in each convolution all but the last random variable is exponential. The last random variable in each convolution is either a zero lifetime or the lifetime of several disjoint consecutive k_i within m_i-out-of-n:F systems in series with each k_i<k, each m_i<m, and each n_i<n. This enables the calculations to proceed recursively. Calculations are facilitated by the symmetric nature of the convex combination     

An improved transmission protocol for two interfering queues inpacket radio networks

The protocol allows a 1.0 transmission probability for newly transmitted packets, while p for retransmitted packets. Compared to the protocol in which each packet is always transmitted with the same probability p, it shows better performance, especially when the channel traffic is light, as demonstrated by numerical results     

Capture models for mobile packet radio networks

The probability q_i of successful reception in a nonfading mobile radio channel with i contending mobiles transmitting to a central base station is studied for a number of different capture and spatial distribution models. It is shown that a generalized capture model can be used to estimate q_i's for a simplified example system which uses noncoherent frequency shift keying modulation. This model can be applied to other systems as well. An example of the use of the q_i 's in the throughput evaluation of a finite population slotted ALOHA system is given. In most practical systems, the mobiles cannot get arbitrarily close to the base station. The effect of this constraint on q_i is examined. Finally, the dependence of the capture probability for a test mobile on its distance from the base station is obtained     

Limiting efficiencies of burst-correcting array codes

The author evaluates the limiting efficiencies e(-S ) of burst-correcting array codes A(n₁,n₂, -s) for all negative readouts -s as n₂ tends to infinity and n₁ is properly chosen to maximize the efficiency. Specializing the result to the products of the first i primes donated by s_i (1⩽i<∞), which are optimal choices for readouts, gives the expression e(-s_i)=(2p_i+1 -2)/(2p_i+1-1) where p_i+1 is the next prime. Previously, it was known only that e(-2)⩾4/5 and e(-1)⩾2/3. This result reveals the existence of burst-correcting array codes with efficiencies arbitrarily close to 1 and with rates also arbitrarily close to 1     

Performance analysis of nonblocking packet switch with input andoutput buffers

The performance of nonblocking packet switches such as the knockout switch and Batcher banyan switch for high-speed communication networks can be improved as the switching capacity L per output increases; the switching capacity per output refers to the maximum number of packets transferred to an output during a slot. The N×N switch with L=N was shown to attain the best possible performance by M.J. Karol et al. (1987). Here a N×N nonblocking packet switch with input and output buffers is analyzed for an arbitrary number of L such that 1⩽L⩽N. The maximum throughput and packet loss probability at input are obtained when N=∞     

Design and analysis of a contention-based lookahead reservationprotocol on a multichannel local area network

The contention-based lookahead reservation (CLAR) protocol can provide fast circuit-switching services that are particularly advantageous for networks supporting integrated services. The delay and throughput performance for message transmission are obtained, and they agree closely with that obtained by simulation. The delay performance of CLAR is similar to that of the M-CSMA protocol for an M-channel network, but only CLAR can give a stable maximum throughput of (M-1)/M independent of the cable length. Moreover, CLAR requires only two sets of transceivers, while M-CSMA requires M. The lookahead reservation technique can provide 9% throughput increase for fixed-size messages and 19% for geometrically distributed messages     

A note on D-ary Huffman codes

An upper bound on the redundancy of D-ary Huffman codes in terms of the probability p₁ of the most likely source letter is provided. For large values of p₁, the bound improves the one given by R.G. Gallager (1978). Additionally, some results known for the binary case (D=2) are extended to arbitrary D-ary Huffman codes. As a consequence, a tight lower bound that corrects a bound recently proposed by J.D. Golic and M.M. Obradovic (1987) is derived     

A selective ARQ protocol with a finite-length buffer

Of the automatic-repeat-request (ARQ) techniques commonly used in communication systems, selective protocols, while the most efficient, have the notable drawback of requiring large buffers at the receiver side. A selective ARQ protocol with a finite-length buffer is described. If N is the number of codewords transmittable in the round-trip delay, the protocol requires a buffer length N+N_a , N_a⩾2 being an integer. A lower bound on the throughput of the protocol is derived. It achieves higher throughputs than similar schemes giving results comparable to those for selective protocols with infinite-length buffer for high error rates in the communication channel     

On the average delay for routing subject to independent deflections

Consider a packet walking along a directed graph with each node having two edges directed out. The packet is headed towards one of N destinations, chosen according to a probability distribution p . At each step, the packet is forced to use a nonpreferred edge with some probability q, independently of past events. Using information theory and sequential analysis, it is shown that the mean number of steps required by the packet to reach the destination is roughly, at least H(p)/(1-h(q), where h is the binary entropy function and H(p) is the entropy (base two) of p. This lower bound is shown to be asymptotically achievable in the case where the packet always begins at a fixed node. Also considered is the maximum, over all pairs of nodes in a graph, of the mean transit time from one node to the other. The work is motivated by the search for graphs that work well in conjunction with deflection routing in communication networks     

Quantile estimation based on nomination sampling

Nomination sampling is a sampling process in which every observation is the maximum of a random sample from some distribution. If all samples are taken from a single underlying CDF, F, data can be viewed as consisting of pairs (X_i,K_i) where K_i is the size of sample i and, given K_i=k_i, X_i is distributed according to CDF F^ki. R.A. Boyles and F.J. Samaniego (1986) developed a nonparametric maximum-likelihood estimator of F. In the present work, their approach is extended to obtain estimates of the quantiles of F and to study the limit theory and consistency properties of these estimates. These results generalize the results of T.R. Willemain (1980), who discussed the estimation of the median of F based on nomination samples     

Nonparametric Bayes estimation of a distribution under nominationsampling

Nomination sampling is a sampling process in which every observation is the maximum of a random sample from some distribution. If the data are {(Y_i, K_i), i =1, . . ., n} where K_i is the size of sample i, and Y_i is the maximum of a random sample of size K_i from an unknown Cdf, F; the Bayes estimator of F is derived by discretizing F over a fixed finite partition of the support of F and taking a Dirichlet distribution as the prior for the probabilities of the partitioning intervals. For the flood data of the Nidd River considered by R.A. Boyles and F.J. Samaniego (J. Am. Stat. Assoc., vol.81, p.1039-45, 1986), the plots of the Bayes estimator of F are obtained for several sets of values of the parameters of the Dirichlet distribution     

A comparison of three switching schemes in isotropic networks withnoisy channels

Previous work on analyzing three switching schemes for isotropic networks, namely single hop and two cut-through communication schemes (with and without error checking by intermediate nodes), is extended. Each scheme is modeled by a discrete Markov chain. It is shown how the performance of the communication schemes depends on path length (n ), load on the network (λ), and the error rate (p). As expected, the cut-through schemes perform much better than the single hop when the communication load is light, but as the load increases, the cut-through schemes deteriorate more rapidly, until they are comparable. In fact, when the load approaches saturation (λ is close to 1-p), the cut-through schemes are actually worse than the single-hop schemes. The schemes with checking always outperform those without, but each node must perform more work in checking the correctness of the packets passing through. The time delay becomes infinite when the throughput approaches 1-p. The solutions are expressed as simple formulas and/or algorithms for each scheme