Stability, Throughput, and Delay of Asynchronous Selective Reject ALOHA

An analytical performance evaluation model is presented for selective reject (SREJ) ALOHA, a recently proposed high-capacity protocol for unslotted channels with high propagation delay. SREJALOHA approaches the theoretical asynchronous multiaccess throughput limit of 0.368 for fixed or variable length message traffic, using subpacketization of messages in conjunction with a selective reject retransmission policy. A finite user flow equilibrium-based model for SREJ-ALOHA with variable length messages is derived and used to characterize stability, throughput, and delay. Particular attention is given to the development of a stability analysis methodology for unslotted ALOHA-type protocols with variable length transmissions. Numerical results based on a satellite channel example are presented to demonstrate the significant performance advantages offered by SREJ-ALOHA, even after accounting for realistic subpacket overheads.     

Ku-Band satellite data networks using very small aperture terminals—part I: Multi-access protocols

This two-part paper presents a comprehensive overview on the technology of very small aperture terminal (VSAT)-based satellite data networks, which have received increasing attention in recent years because of a combination of technical and economic factors. Ku-band networks with customer-premise earth-stations can overcome the inherent local access bottleneck in wide-area terrestrial data networks by suitably exploiting the unique multi-access and broadcast features of satellite communication. In this part of the paper, the issue of multiple access, which is an important critical path technology in the ongoing evolution of VSAT data networks, is considered in detail. Satellite multi-access protocols are classified in terms of channel synchronization (slotted and unslotted) and the qualitative nature of message access (fixed assigned, contention and reservation). In addition to well known techniques such as ALOHA, slotted ALOHA, tree CRA, packet CDMA and demand assigned (DAMA) TDMA, a number of new approaches to efficient unslotted access, including selective reject (SREJ) ALOHA, time-of-arrival CRA and locally synchronous reservation, are discussed. The general review is followed by a detailed performance comparison of a number of candidate first-generation VSAT protocols, namely ALOHA, slotted ALOHA, SREJ-ALOHA, DAMA with TDMA reservation access and DAMA with slotted ALOHA reservation access. The performance evaluation, based on detailed simulations with VSAT equipment and transaction traffic parameters, is summarized by curves of average delay and throughput vs. number of VSATs per channel for each of the protocols considered. Higher-order differences in delay performance are illustrated with appropriate delay distribution results and the sensitivity of performance with respect to key equipment and traffic parameters is investigated. For the transaction traffic model under consideration, the results suggest the use of SREJ-ALOHA among contention techniques or DAMA with slotted ALOHA reservation among controlled access alternatives. The trade-off between contention and reservation access is shown to be more complex, depending on the combination of average delay, peak delay, transmission cost and equipment complexity suited to the particular application. In Part II

1 To published in the next issue

of this paper on Ku-band VSAT networks, the issue of overall system design is considered.     

Calculation of message length transition probabilities in selectivereject ALOHA channels

A method is described for the exact calculation of message length transition probabilities in asynchronous selective reject (SREJ) ALOHA channels with Poisson message arrivals. The formulas derived are used for exact calculation of the throughput characteristics of example SREJ-ALOHA channels which were previously analyzed using bounds or approximate methods     

Selective reject ALOHA/FCFS: An advanced VSAT channel access protocol

This paper proposes and evaluates selective reject (SREJ) ALOHA/FCFS, a highly efficient, flexible and robust multiaccess protocol for very small aperture terminal (VSAT) applications. SREJ-ALOHA with locally synchronous FCFS retransmission scheduling is a ‘semi-compatible’ enhancement of asynchronous SREJ-ALOHA, which has earlier been shown to be an attractive satellite channel sharing protocol for low volume bursty terminals with variable length messages. The FCFS retransmission scheduling policy proposed here broadens the applicability of SREJ-ALOHA by providing higher maximum throughput, particularly in the important source traffic scenario with bimodal message length distributions. Improved channel-sharing efficiency and delay are achieved by exploiting time-of-arrival feedback naturally embedded in an unslotted SREJ-ALOHA channel to develop an implicit time-of-arrival based (FCFS) ordering for conflict-free, locally synchronous retransmission of most contending messages. An analytical procedure for evaluation of stability, throughput and delay for a general finite source, variable message length traffic model is described. The model is used to demonstrate that random access SREJ-ALOHA/FCFS typically achieves a maximum throughput in the region of 0·4–0·45 along with excellent stability and delay properties. In addition, a natural extension of the protocol which supports implicit reservation for long messages is described and shown to offer a high maximum throughput (>0·6), comparable to that achieved by highly co-ordinated slotted systems, for example mixed interactive/file-transfer traffic scenarios.     

Space-time characteristics of ALOHA protocols in high-speedbidirectional bus networks

Studies the space-time characteristics of ALOHA multiple-access protocols in bidirectional bus networks where transmissions are in the form of packets of constant length. For point-to-point communications, the maximum throughput of unslotted ALOHA is known to be 1/(2e), independent of station configuration. The authors show that, with a uniform probabilistic station configuration, the maximum throughput of slotted ALOHA tends to a nonzero constant that is less than 1/(2e), when a, the end-to-end propagation delay normalized with respect to the packet transmission time, tends to infinity. However, when N stations are evenly spaced on the bus, the maximum throughput of slotted ALOHA vanishes as a tends to infinity. For broadcast communications, the maximum throughput of slotted ALOHA is well known to be 1/{e(1+a)}. For unslotted ALOHA, the authors show that, if the offered load intensity is constant along the bus, the maximum broadcast throughput achievable by a station varies along the bus and is maximized at its center. The authors also derive the optimal profile of the offered load intensity for achieving a constant throughput intensity. In both cases, the maximum broadcast throughput is greater than that derived by conventional analysis     

Performance analysis of DS/SSMA unslotted ALOHA system withvariable length data traffic

We analyze the throughput of a direct-sequence spread spectrum multiple access (DS/SSMA) unslotted ALOHA system with variable length data traffic. The system is analyzed for two cases: (1) systems without a channel load sensing protocol (CLSP) and (2) systems with a CLSP. The bit-error probability and the throughput are obtained as a function of the signal-to-noise ratio (SNR) during message transmission, considering the number of overlapped messages and the amount of time overlap. We assume that the generation of data messages is Poisson distributed and that the messages are divided into packets before transmission. The system is modeled as a Markov chain under the assumption that the number of packets in a message is geometrically distributed with a constant packet length. The throughput variance of the DS/SSMA unslotted ALOHA system with variable length data traffic is obtained as the Reed-Solomon code rate varies. Results show that a significant throughput improvement can be obtained by using an error-correcting code     

Throughput of unslotted direct-sequence spread-spectrummultiple-access channels with block FEC coding

An analysis of unslotted random-access direct-sequence spread-spectrum multiple-access (DS/SSMA) channels with block forward error correction (FEC) coding is presented. Extending a methodology that was introduced in an earlier paper on unslotted packet code-division multiple access (CDMA) without coding, a procedure for calculating the error probability of an L-bit packet in the variable message length, FEC-coded, DS/SSMA environment is described. This procedure is then used in conjunction with appropriate flow equilibrium traffic models to compute channel throughput. Using BCH block coding as an example, the analytical model is exercised to obtain throughput versus channel traffic curves over a range of code rates, leading to an assessment of maximum achievable throughput and the associated optimum FEC code rate. The results show that the use of block FEC coding provides a significant improvement in the bandwidth-normalized channel throughput (utilization), approaching values competitive with those for comparable narrowband ALOHA channels     

Random access with large propagation delay

Random access to a packet broadcast channel with large propagation delay is investigated. A protocol is presented that combines slotted ALOHA random access with the use of forward-error-correction (FEC) across transmitted packets. Expressions for the throughput, delay, and drift of this protocol are derived. Numerical studies and asymptotic analyses of the drift indicate that the protocol has a maximum throughput of e^-1 and exhibits bistability and saturation behavior similar to that of slotted ALOHA with immediate feedback. However, unlike ALOHA, bistability and saturation in the code protocol can be eliminated with the proper choice of protocol parameters without increasing the packet delay. It is further shown that, when compared to slotted ALOHA, the code protocol typically achieves a higher throughput and lower delay at system equilibrium with no loss in maximum throughput     

Output Processes in Contention Packet Broadcasting Systems

The processes consisting of the packet interdeparture times in contention-type packet broadcasting systems are studied under the heavy-traffic assumption. The channel access protocols considered include slotted and unslotted ALOHA and carrier-sense-multiple-access (CSMA) with and without collision detection. Through analysis of the Channel activity cycle, the distribution, mean, and coefficient of variation of the packet interdeparture times are explicitly derived. Taking the reciprocal of the mean interdeparture time, we obtain the channel throughput. Cases with dissimilar users are mainly considered, and systems of statistically identical users are treated as special cases.     

Frequency-hop transmission for satellite packet switching and terrestrial packet radio networks

The performance of frequency-hop transmission in a packet communication network is analyzed. Satellite multiple-access broadcast channels for packet switching and terrestrial packet radio networks are the primary examples of the type of network considered. An analysis of the effects of multiple-access interference in frequency-hop radio networks is presented. New measures of "local" performance are defined and evaluated for networks of this type, and new concepts that are important in the design of these networks are introduced. In particular, error probabilities and local throughput are evaluated for a frequency-hop radio network which incorporates the standard slotted and unslotted ALOHA channel-access protocols, asynchronous frequency hopping, and Reed-Solomon error-control coding. The performance of frequency-hop multiple access with error-control coding is compared with the performance of conventional ALOHA random access using narrow-band radios.     

非时隙CDMA分组网络吞吐量性能分析:统一的方法

CDMA分组网络性能主要受限于信道中同时传输的其它分组的干扰.与时隙CDMA分组网络相比,非时隙CDMA分组网络所受到的干扰情况更加复杂.本文提出了一种非时隙CDMA分组网络的干扰分析模型,并采用递归方式建立了网络吞吐量性能分析的统一方法.在此基础上,分析了网络节点突发固定长度分组和突发可变长度分组两种情况下的网络吞吐量性能,并讨论了扩频增益和分组传输方式对网络性能的影响,给出了相应的数值结果.文章最后进一步讨论了吞吐量的上下界问题.与前人提出的马尔可夫模型相比,采用本文提出的方法可以得到更为准确的吞吐量性能.     

Multiple-access protocols for satellite packet communication networks: A performance comparison

This paper considers satellite packet communication networks with a large population of bursty users and presents an analytic comparison of the throughput versus average message delay trade-off characteristics of multiple-access protocols. The following six multiple-access protocols are examined: 1) slotted ALOHA, 2) reservation-ALOHA, 3) a reservation protocol with a slotted ALOHA reservation channel, 4) a reservation protocol with a TDMA reservation channel, 5) SRUC (Split Reservation Upon Collision), and 6) fixed assigned TDMA. All the protocols are required to ensure that all packets of a message are correctly received in the proper order at the destination. Then, a unified presentation of the delay-throughput performance of the protocols is given by means of an analytical technique called equilibrium point analysis. The throughput versus average message delay tradeoff characteristics are compared taking into account the system stability.     

The effect of multipath interference on the performance of packetradios

The effect of multipath interference on the performance of packet radios is investigated. The protocols considered include pure ALOHA and slotted ALOHA. Signal reception with and without capture effect is considered in the analysis. Mathematical expressions of system throughput and packet delay have been successfully obtained for each protocol. Numerical calculations are used to demonstrate when the multipath interference can be ignored and when it can be disastrous     

A novel spread slotted Aloha system with channel load sensingprotocol

This paper presents a novel spread slotted Aloha system with channel load sensing protocol (CLSP). CLSP is an effective scheme to improve the throughput performance in spread unslotted Aloha systems. In spread slotted Aloha systems, however, it does not make sense to utilize CLSP because the slot size is usually the same as the packet size. The slot size of the proposed system is set less than the packet size, thereby enabling the authors to apply CLSP and improving the throughput performance. Another feature of the proposed system is that the system is not likely affected by the time difference between channel load sensing and timing of packet access, which they call the access timing delay. Throughput performance of the proposed system is evaluated in the presence of the access timing delay and a significant increase of the throughput is shown compared with that of spread unslotted Aloha with CLSP     

Stability and throughput analysis of unslotted CDMA‐ALOHA with finite number of users and code sharing

We consider a system comprising a finite number of nodes, with infinite packet buffers, that use unslotted ALOHA with Code Division Multiple Access (CDMA) to share a channel for transmitting packetised data. We propose a simple model for packet transmission and retransmission at each node, and show that saturation throughput in this model yields a sufficient condition for the stability of the packet buffers; we interpret this as the capacity of the access method. We calculate and compare the capacities of CDMA‐ALOHA (with and without code sharing) and TDMA‐ALOHA; we also consider carrier sensing and collision detection versions of these protocols. In each case, saturation throughput can be obtained via analysis of a continuous time Markov chain. Our results show how saturation throughput degrades with code‐sharing. Finally, we also present some simulation results for mean packet delay. Our work is motivated by optical CDMA in which “chips” can be optically generated, and hence the achievable chip rate can exceed the achievable TDMA bit rate which is limited by electronics. Code sharing may be useful in the optical CDMA context as it reduces the number of optical correlators at the receivers. Our throughput results help to quantify by how much the CDMA chip rate should exceed the TDMA bit rate so that CDMA‐ALOHA yields better capacity than TDMA‐ALOHA. This revised version was published online in June 2006 with corrections to the Cover Date.     

Performance comparison of a slotted ALOHA DS/SSMA network and amultichannel narrow-band slotted ALOHA network

Throughput, delay, and stability for two slotted ALOHA packet radio systems are compared. One system is a slotted direct-sequence spread-spectrum multiple-access (DS/SSMA) network where each user employs a newly chosen random signature sequence for each bit in a transmitted packet. The other system is a multiple-channel slotted narrow-band ALOHA network where each packet is transmitted over a randomly selected channel. Accurate packet success probabilities for the code-division multiple-access (CDMA) system are computed using an improved Gaussian approximation technique which accounts for bit-to-bit error dependencies. Average throughput and delay results are obtained for the multiple-channel slotted ALOHA system and CDMA systems with block error correction. The first exit time (FET) is computed for both systems and used as a measure of the network stability. The CDMA system is shown to have better performance than the multiple-channel ALOHA system in all three areas     

Accurate DS-CDMA Packet-Error Rate Analysis in Rayleigh Fading

We present new packet-error rate (PER) analysis for both slotted and unslotted direct-sequence spread-spectrum packet communication systems in a slow Rayleigh fading environment. Based on the accurate improved Gaussian approximation, we derive closed-form expressions for the cumulative probability distribution function of the signal-to-interference-plus-noise ratio in binary phase-shift keying (PSK), quadratic PSK, and differential PSK-based code-division multiple-access (CDMA) systems having different types of chip waveforms including bandwidth-efficient waveforms. This leads to new accurate unified expressions for the PERs that account for bit-to-bit error dependence, which are valid for packets with unequal power levels. These new results facilitate accurate computation of the throughput performance of CDMA-based ALOHA local radio networks     

Throughput Analysis for Persistent CSMA Systems

The channel throughput for a finite number of packet broadcasting users is analyzed for random access protocols, including slotted persistent carrier sense multiple access (CSMA) with and without collision detection and unslotted persistent CSMA with and without collision detection. We consider bothp- and 1-persistent CSMA. Our results can be extended to infinite population cases (by taking the proper limit), where they agree with the known throughput expressions when available.     

Contention-based MAC protocols with erasure coding for wireless data networks

Contention-based medium access control (MAC) protocol is a key component for the success of wireless data networks. Conventional random access protocols like ALOHA and Carrier Sense Multiple Access (CSMA) suffer from packet collision which leads to low throughput. Aimed at improving the throughput performance, we propose to integrate erasure coding with contention-based MAC protocols for recovering collided packets. To demonstrate the effectiveness of this approach, we focus on combining erasure coding with slotted ALOHA and slotted non-persistent CSMA in this paper. The performances of the resulting protocols are evaluated by both analytical model and simulation. Simulation results match very well with analytical results and show that the system throughput is increased for low to medium traffic loading. Packet loss ratio is also improved considerably with our scheme when the maximum number of packet retransmission times is limited. However, the delay for our scheme is higher due to the longer waiting time in our scheme for recovering collided packets. It is also shown that delay can be significantly reduced if we choose appropriate coding parameters though throughput will be sacrificed.     

Random Signal Levels for Channel Access in Packet Broadcast Networks

In this paper, it is proposed to employ random multiple signal levels for channel access in packet broadcast networks. We present priority-free random access protocols that possess the advantage of capture effect. The presented schemes are applied to the slotted ALOHA, and the performance is analyzed based on a conservative capture model. Closed-form expressions for the system throughput are derived for a general two-signal level system and a generalm-signallevel system. It is shown that the maximum throughput for the twolevel system increases from 0.47 to 0.52 as the separation between the two levels increases. For them-level system, the maximum throughput increases from 0.52 to 0.66 asmincreases from three to infinity. Then a rotary-priority sure-capture random access scheme is presented, which can achieve perfect channel utilization. The time-delay characteristic and the throughput-delay tradeoff are analyzed for the simplest two-level system for which the higher level is double the lower level. The results compare favorably to those of the conventional slotted ALOHA system which employs a single signal level for packet transmission. A number of open problems are addressed.