The behavior of exponential backoff (EB) has challenged researchers ever since its introduction, but only approximate and partial results have been produced up to this date. This paper presents accurate results about the effect of protocol parameters on throughput and delay, assuming queues in saturation. Among the manifold results, we first introduce a simple model that provides close-form results for the approximated model known as “decoupling assumption.” Since the latter fails to provide well approximated results in many cases, we also introduce a Markovian model able to trade the precision of the results with complexity even with an infinite number of users, enabling us to get definite throughput results, such as 0.3706 with binary EB, and 0.4303 with an optimized base. Analytical considerations allow to derive the tail of the access-delay distribution, found to be slowly decreasing and with no variance as the number of users goes to infinity. Taking into account the overall performance, preliminary results seem to indicate that the exponential base b=1.35 is more appealing than the standard value b=2.

The Slotted-Aloha protocol has been widely studied in the past forty-five years. Nonetheless, when the Exponential Backoff (EB) is used to stabilize its behavior, the characterization of stability conditions have eluded all efforts. Here we prove that the EB with geometric law i ↦ b−i−i0, with queues in saturation, is ergodic if and only if b > 1 and the initial offset is i0> 1, for any number of users. If i0= 0 the system is transient, and null recurrent for 00≤ 1, where some intermediate behavior is possible, since not all backoff indexes are unstable.

The stability and throughput of the Slotted Aloha protocol have been studied at length, yielding results that depend on the environment and channel assumptions, in many cases indicating e-1 as the S-Aloha capacity. When users can detect only their own collisions, and the number of users N goes to infinity, no definite capacity result exists. Approximated models have been introduced to study the exponential back-off mechanism, which seem to indicate an asymptotic capacity of ln(2)/2 when binary back-off is used, and again e-1 when the exponential base is optimized. Here we introduce a more accurate and flexible model that shows that past results miss their mark. In fact, we prove that with binary back-off the capacity is practically 0.370, slightly greater than e-1; furthermore, and more important, we prove that using 1.35 as exponential back-off base, the capacity reaches 0.4303 with an infinite number of users, and up to 0.496 with N = 2 users.

In dynamic-frame Aloha, subsequent frame lengths must be optimally chosen to maximize throughput. When the initial population size N is known, numerical evaluations show that the maximum efficiency is achieved by setting the frame length equal to the backlog size at each subsequent frame; however, to the best of our knowledge, a formal proof of this result is still missing, and is provided here. As byproduct, we also prove that the asymptotic efficiency in the optimal case is e-1, provide tight upper and lower bounds for the length of the entire transmission period, and show that its asymptotic behavior is ~ne-ζ ln(n) with ζ =-0.5/\ln (1-e-1).

This paper refers to a network scenario featuring a single RFID reader (interrogator) which aims at identifying a large number of objects geared with RFID tags, through multiple and sequential interrogations. Since several tags can answer to each interrogation, a problem of collisions arbitration at the reader arises. Classical previously proposed collisions arbitration protocols based on tree-search algorithms make use of channel feedback information on the outcome of the preceding transmissions either of binary type (collided/non collided), or ternary type (idle/successful/collided) achieving an average resolution time per object ranging between 2.1 and 2.8 interrogation cycles. In this paper, we show that the RFID transmission environment allows to obtain an enriched channel feedback information that can be leveraged to greatly improve the efficiency of the identification procedure. We further propose and analyze the arbitration protocol with advanced feedback (ARPA), able to asymptotically provide 100% efficiency. Finally, we show that the overhead needed to implement our protocol in practical RFID systems easily allows to achieve an average resolution time of about 1.4 interrogation cycles per object.

The efficiency of point-to-point (PTP) connections in ad hoc networks highly depends on the capability of the medium access control (MAC) layer to reuse the shared wireless resource. One of the most critical impairments to the reuse capability is the exposed terminal problem which may prevent feasible PTP communications to run in parallel. In this paper we evaluate the impact of the exposed terminal on the reuse efficiency of PTP communications in ad hoc random networks. To this end, we propose a scheduling algorithm for PTP connections within the framework of ADHOC MAC, a recently proposed MAC scheme. The simulative results we gather show that the solution of the exposed terminal problem provides a reuse efficiency gain around the 40% in the network scenario we considered.

Ad-hoc networks, though an attractive solution for many applications, still presents many unsolved issues, such as the hidden-terminal problem, flexible and prompt access, QoS provisioning, and efficient broadcast service. In this paper, we present a MAC architecture able to solve the above issues in environments with no power consumption limitation, such as networks for inter-vehicle communications. This new architecture is based on a completely distributed access technique, RR-ALOHA, capable to dynamically establish on a slotted/framed structure a reliable single-hop broadcast channel for each active terminal on the network. Though the proposed MAC uses a slotted channel, it can be adapted to operate on the physical layer of different standards, including the UMTS terrestrial radio access TDD, and the IEEE 802.11. The paper presents the mechanisms that compose the new MAC: the basic RR-ALOHA protocol, an efficient broadcast service and the reservation of point-to-point channels that exploit parallel transmissions. Some basic performance figures are discussed to prove the effectiveness of this protocol.

The UMTS W-CDMA radio interface is characterized by great flexibility and a variety of different physical and logical channel types, rates and protections are possible, by choosing suitable parameters, such as spreading factors, code rates and ARQ schemes. In this paper we present the results, obtained by a detailed simulation, about the effect of several parameters and system alternatives on the capacity of the downlink shared channel.

The increasing demand for a variety of new Internet services with different and possibly stringent QoS requirements (i.e. Internet telephony, videoconferencing etc.) requires the design of mechanisms to support QoS guarantees. The current solutions proposed in IETF, RSVP (Resource reSerVation Protocol) and differentiated services, though suitable for many applications, may result inefficient to support real-time services on a call basis. The RSVP is not really scalable and requires substantial changes in the Internet architecture, while differentiated services provide guarantees mostly on a static and permanent basis. In this paper we assume an Internet architecture supporting multiple priorities as needed in differentiated services, and introduce the PCP (phantom circuit protocol), a mechanism that provides a guaranteed bandwidth transport service for circuit oriented connections. The PCP includes a fully scalable call admission control (CAC) and operates on a per call basis. Simulation of the protocol performance for CBR (constant bit rate) traffic under various network conditions show the adherence of the mechanism to theoretical expectations.

In wireless ATM systems, the introduction of an error control scheme at the air interface is mandatory in order to meet the constraints on the cell loss rate. Error control must be able to cope with the characteristics of the radio channel which is usually a channel with memory characterized by burst of errors, commonly modeled as a Gilbert-Elliott channel. Common approaches to the problem include standard forward error correction (FEC) techniques with bit interleaving implemented at the physical layer, and ARQ (automatic repeat request) techniques implemented at the MAC/DLC layer for non real-time applications only. However, the peculiar characteristics of the Gilbert-Elliott channel, for an extended range of channel parameters, are better exploited by other approaches. In this paper, we consider a wireless ATM access interface based on a TDMA scheme and real-time services with stringent delay constraints. The efficiencies of three error control schemes are compared: the classical FEC plus bit interleaving, a scheme based on block erasure codes, and a real-time ARQ scheme proposed in a previous paper. It turns out that the delay constraints can severely limit the performance of the FEC with respect to the other approaches.

The capacity of mobile cellular systems is mainly limited by cochannel interference. Commonly in multiple carrier-time division multiple access (MC-TDMA) systems, like the global system for mobile (GSM) communications, the interference noise is first reduced by means of channel clustering and slow frequency hopping. The residual interference, characterized by a level varying slot by slot, causes errors in burst which are spread with bit interleaving and fought with correcting codes for random errors. With real-time services like voice, no other error control technique, such as automatic repeat request (ARQ), is usually adopted. An alternative approach is given by capture division packet access (CDPA) where transmissions are spread in time adopting a dynamic slot assignment (DSA), and errors are dealt with a retransmission mechanism. In this paper, we present a comparison of this two approaches, and using a simple theoretic capacity analysis, we justify the better performance of CDPA. Moreover, by the delay performance analysis, we prove that in spite of its retransmission mechanism, CDPA is effective also with delay constrained services.

Different dynamic channel allocation (DCA) strategies based on local signal strength measures are evaluated in terms of the degree of frequency reuse they can afford. Fixed and dynamic channel allocation schemes are compared by using a simulation model, which overcomes the limitations of models traditionally used in literature. Valuable results show the superiority of DCA schemes in various scenarios characterized by different patterns of traffic and propagation conditions.

This paper investigates the ability of the DECT system to provide a cellular transmission service for data traffic composed of short messages. At first, the DECT performance is investigated in a single cell environment. Its access mechanism is analyzed in detail, discussing the overhead of the different procedures and measuring their quantitative effects. Then, the performance in the cellular environment specified by the ETSI is considered. The simulation results show a relatively small degradation in throughput, with respect to the single cell case, due to co-channel interference.

The paper compares the performance of two channel-access schemes suitable for the cellular environment which, in particular allow the packet capture and can deal with inter-cell interference. The first scheme is the well known S-ALOHA while the second one is the capture division packetized access (CDPA). The comparison is analytically performed over a common system with a common analytical model. Despite the many analyses that have appeared on S-ALOHA, the one we develop is new because a throughput density uniformly distributed on the plane is considered in a multiple cell environment. The analysis clearly shows the effect of intra-cell and inter-cell interference on the ALOHA system and proves that a superior throughput is achieved by CDPA, which completely avoids intra-cell interference. Our analysis also provides an insight into the effectiveness of power control on both systems.

In this paper we present the performance of the capture division packet access (CDPA) cellular architecture obtained by using a more accurate packet capture model than the one used in previously appeared analyses. In the new model, the effect of cocell interference is evaluated on each bit of the packet. The results obtained with this new model are directly related to the propagation parameters that are normally used in the literature on cellular systems, such as the exponent of the near-far power attenuation law. In practice, we find that CDPA can achieve better performance than that predicted by the "threshold" model used previously. With this new model we also evaluate the effect of forward error correcting techniques, which are found to provide only a small improvement in the maximum throughput.

This paper presents a new architecture for the third-generation mobile systems, capture-division packetized access (CDPA), that overcomes most of the limitations of present cellular systems. It addresses the three main issues of radio access, namely the channel reuse, the multiple access, and the handover problems, in complete adherence to packet-switching principles. The CDPA channel reuse mechanism is a completely new alternative with respect to time-division, frequency-division, or code-division multiple-access (TDMA, FDMA, and CDMA, respectively), which achieve communication parallelism by subdividing the bandwidth a priori among cells. In CDPA, a single frequency channel is used and parallel transmissions are achieved through the "capture" capability of receivers. The hybrid reservation-polling multiple access mechanism used in CDPA is able to integrate any kind of traffic and guarantees almost immediate retransmission of packets that are not captured, thus assuring their correct reception. Finally, the packet-switching approach allows connectionless communications with any base station (BS), and eliminates the need for extra radio traffic in managing handovers. This turns out to be very effective in local area systems where the required high bandwidth is obtained by using a pico-cell structure. We present the CDPA architecture, discuss some implementation issues, and evaluate its performance under a variety of system parameters and operating conditions, using analytical and simulation methods.

Deflection routing can be used in networks whose stations have the same number of input and output links. Fixed length packets arrive synchronously on the station's input links at the beginning of time slots, and each packet is routed via the output link that offers the shortest path to its destination. Since the number of packet buffers at each output link is finite, the simultaneous contention of two packets for the last buffer of a common output link must be resolved by "deflecting" one of the packets to another output link. Thus, the deflection of a packet could result in the packet following a route that is not a shortest path. The potentially unbounded number of routes that a given packet can take makes analyzing the performance of such networks difficult. In particular, there are no analytical models that can analyze multibuffer deflection-routing networks with nonuniform traffic. Using independence assumptions, the authors develop a performance model of deflection routing that allows to estimate accurately and efficiently the mean transport time and throughput in a network that has any given two-connected topology, multiple buffers at each output port, and an arbitrary traffic matrix.>

Deflection routing plays a prominent role in many optical network architectures, because it can be implemented with modest packet-buffering requirements. From the practical perspective, however, the implementation of deflection routing, which is normally based on global time slotting, might pose challenges. The authors develop approaches to the implementation of both slotted and unslotted deflection-routing optical networks. They analyse important tradeoffs that are inherent to the design of optical deflection-routing networks and compare the performance of slotted and unslotted networks. Under a reasonable set of assumptions about optical technology, the results suggest that the unslotted link protocol should be the preferred approach to building the optical deflection-routing network.>

There is a rapidly growing demand for low-cost packet data services in GSM networks. Therefore, the ETSI is considering the possible introduction of a general packet radio service (GPRS) in GSM. We propose an enhancement of a GPRS proposal which improves the utilization of the radio resource. In particular, we consider a random access technique, that is very close to the PRMA, and allows mobile stations to share all data traffic channels available in the cell. In this context, the performance of typical data applications, which require short messages, are evaluated by simulations. The results obtained confirm the validity of this proposal even if more accurate investigations are needed for its complete definition.

The paper presents a new cellular architecture for radio access, CDPA, that can be applied to present and future cellular systems, independently of the cell size. It poses as an appealing alternative to systems based on classical bandwidth-subdivision methods, namely TDMA, FDMA or CDMA. In these systems, parallelism of communications is achieved by subdividing the bandwidth "a priori" among cells. In CDPA no bandwidth subdivision is operated. All cells and terminals use a single frequency channel and transmit packets on a slotted channel. Parallel transmission in different cells is achieved through the "capture" capability. A dynamic polling mechanism, C-PRMA, managed by the base station, guarantees almost immediate re-transmission of packets that are not captured, thus assuring that packets are eventually correctly received. Analytical evaluations show that CDPA has the potential to provide larger capacity than the other cited systems in the case of continuous traffic sources. Furthermore, as C-PRMA is inherently apt to sustain bursty traffic, the system capacity is easily doubled in the case of packetized voice transmission using silence suppression.

The fair queue dual bus (FQDB) medium-access control (MAC) protocol for dual bus networks, which is intrinsically fair in bandwidth sharing and retains all the positive features of distributed-queue dual-bus (DQDB) systems including simplicity, robustness, flexibility, 100% bandwidth utilization, and zero access delay at very low load, is presented. Features which make this protocol appealing with respect to others DQDB alternatives are represented by the fact that FQDB is compatible with the DQDB standard with respect to the physical arrangement and attachment to the bus, the XOR write tap, the access control field (ACF) length, and the three priority levels. Nevertheless, its properties are attractive also for protocols operating at 1 Gb/s and up. Fairness is formally proved, and it is shown that a bandwidth sharing pattern different from the uniform one can easily be enforced, as may be the case if bridges or other large users are presented. Queueing disciplines, priorities, and implementation issues are discussed, and comparisons obtained by simulation are given.>

The use of independence assumptions has made it possible to derive an approximate model of deflection-routing networks that have multibuffer stations and two-connected topologies. A procedure is presented for estimating the mean transport time (and throughput) of these networks, even when the offered traffic is nonuniform. The proposed procedure is efficient and yields very accurate results, as comparisons with simulations have confirmed. The model is quite general and can be applied to deflection-routing networks that deflect packets according to destination-based priorities. The authors have modeled only a few of the several options for designing a deflection-routing network. In particular, they have modeled a network with no user input buffers, a specific admission-routed policy, and destination-based priorities.>

The authors present the delay-throughput performance of a new MAC protocol, the fair queue dual bus (FQDB), which relieves dual bus networks from the unfairness problems exhibited by the basic version of the distributed queue dual bus (DQDB) standard. The protocol considered is absolutely fair in bandwidth sharing and does not imply any change in the DQDB transmission system. It retains all the positive features of DQDB including simplicity, robustness, flexibility, 100% bandwidth utilization, and little slot access delay at light load. Comparisons to DQDB with the bandwidth balancing mechanism show that the FQDB delay-throughput performance was always superior while its implementation complexity was comparable.>

The capability of the deflection network to provide circuit service, i.e., virtual circuit service with guaranteed bandwidth, is investigated. Such a capability is achieved by modifying the datagram access algorithm and by introducing additional information in the packet header which allows prioritized access via token requests. This mechanism guarantees the needed resources to the already established connections. A second mechanism, which is superimposed on the previous one, is used to measure the resources available and to assign them upon request. The whole mechanism is completely distributed and very robust, since it is based on measures that reflect the real status of the network. A performance analysis is carried out by simulation. In particular, the capability is shown to guarantee the bandwidth to each connection, and the degradation in the network's maximum throughput due to the token mechanism is investigated. Some modifications to improve the circuit capacity are introduced and their effectiveness is evaluated.>

A class of shortest-path distributed-routing techniques is presented, and the authors show a locally optimal solution under uniform traffic assumptions. It is argued that, as the number of nodes grows to infinity, the throughput tends to the limit represented by the maximum throughput attainable with the store-and-forward technique and infinite queueing storage. The results obtained show the suitability, as far as the throughput is concerned, of meshed networks using packet switching without storing packets at nodes. The routing techniques investigated perform similarly. At least one of these is simple enough to be implemented with very-fast circuitry, able to cope with the speed foreseen in future metropolitan-area networks (MANs).>

ExpressMAN is a metropolitan area network architecture which connects users grouped in different clusters. It retains all the positive features of LAN's, but in addition, allows for parallel transmission of local traffic. The overall network structure is halfway between a linear bus and a two-level hierarchical structure in which several subnetworks are connected by a backbone network. However, it does not need complex routing facilities like bridges. Based on the Expressnet access mechanism, it can be dynamically configured either as a unique bus or as several different local buses which allow the circulation of long distance and local trains, respectively. Routing is performed by the transmitting stations choosing the correct train. Local communications can take the bandwidth not used by long distance trains, and thus increase bandwidth efficiency by means of parallel transmissions. In this paper, the performance of ExpressMAN is evaluated and compared to that achieved by the aforementioned two-level structure based on Express networks. Although the Expressnet mechanism has been chosen as the simplest and most efficient mechanism available for LAN's the principle underlying ExpressMAN could be applied to other token schemes such as the token ring.

L-Express is a protocol for Local Area Networks based on a single bus topology. It utilizes a simple and efficient virtual token access scheme which provides ordered and collision-free transmission. This paper presents results of measurements performed to investigate in details the behavior of the L-Express protocol under different network speeds, configurations and traffic environments. The measurements are obtained using a mix of simulation and field tests on a network prototype. Voice and integration of voice and data are also taken into account. The results indicate a good behavior (compared with Ethernet) for small size networks (500 m) and Low data rates (10 Mb/s) as well as for Large size networks (5000 m) and high data rates (100 Mb/s)

L-Expressnet is the communication suxbnetwork for the CNET local area network project of the CNR, Italy. Based on a single bus topology, it utilizes a simple and efficient virtual-token access protocol which provides ordered and collision-free transmission. The paper discusses the needs which led to L-Expressnet, describes the protocol, proves its correct operation, and compares its throughput-delay performance with those of other typical bus Protocols. A major advantage of L-Expressnet is that its implementation may be based on Ethernet standard transceivers and network interfaces.

The behavior of the throughput of an ALOHA channel is investigated, taking into account the effect of acknowledgment traffic when the acknowledgment mechanism is provided by high-level protocols. It is shown that the use of redundant ACK packets slightly increases the channel throughput.

Expressnet is a local area communication network comprising an inbound channel and an outbound channel to which the stations are connected. Stations transmit on the outbound channel and receive on the inbound channel. The inbound channel is connected to the outbound channel so that all signals transmitted on the outbound channel are duplicated on the inbound channel, thus achieving broadcast communication among the stations. In order to transmit on the bus, the stations utilize a distributed access protocol which achieves a conflict-free round-robin scheduling. This protocol is more efficient than existing round-robin Schemes as the time required to switch control from one active user to the next in a round is minimized (on the order of a carrier detection time), and is independent of the end-to-end network propagation delay. This improvement is particularly significant when the channel data rate is so high, or the end-to-end propagation delay is so large, Or the packet size is so small as to render the end-to-end propagation delay a significant fraction of, or larger than, the transmission time of a packet. Moreover, some features of Expressnet make it particularly suitable for voice applications. In view of integrating voice and data, a simple access protocol is described which meets the bandwidth requirement and maximum packet delay constraint for voice communication at all times, while guaranteeing a minimum bandwidth requirement for data traffic. Finally, it is noted that the voice/data access protocol constitutes a highly adaptive allocation scheme of channel bandwidth, which allows data users to recover the bandwidth unused by the voice application. It can be easily extended to accommodate any number of applications, each with its specific requirements.

In this paper we give a new simple expression for the probability of successful transmission on an infinite population ALOHA channel with variable length packets. Expressions for the throughput and the probability density of the packet length on the channel are derived in a straightforward way along with the best and the worst length densities.

The goal of this paper is to present a multi-access technique for Satellite Broadcast Channel Communication which extends the features of the Slotted-ALOHA system to higher Channel Utilization and presents a stable behaviour. The Reservation Upon Collision (RUC) Technique consists on a S-ALOHA scheme with a super-imposed reservation technique which automatically operates when collisions occur.