Performance evaluation of preemptive polling schemes and ARQtechniques for indoor wireless networks

This paper examines a radio-based indoor communication network with a single radio channel shared by several data terminals. By enabling the terminals to communicate with each other and access the resources of a wired network, the system is a potential provider of in-building LAN-like services. In this indoor fading environment, a base-station approach is assumed. In the analysis, a two-state Markov chain model is used to model the nonstationary transmission channel. Two preemptive polling multiple-access schemes combine with ARQ error-control schemes to counteract the effects of a nonstationary transmission channel. The main idea devised is that of making the service interruption dependent on the propagation conditions of the transmission channel by monitoring the outcomes of the data packet transmission attempts. A performance comparison reveals the superiority of the preemptive polling systems with respect to a classical TDMA scheme     

A preemptive polling protocol for applications in wireless LANs

This paper deals with a radio‐based communication network with a single radio channel shared by several data terminals for transmissions to a single hub station. In particular, the communication system considered is a potential provider of wireless LAN‐like services. The focus is on the capacity of combining a preemptive polling‐based multiple access scheme with a Selective Repeat ARQ technique to counteract the effect of the nonstationary transmission channel. The nonstationary transmission channel has been modeled as a two‐state Markov chain with parameters related to actual propagation conditions. Typical outdoor/indoor environments have been considered. The main idea is that of making the service interruption of the preemptive polling scheme dependent on the propagation conditions of the transmission channel by monitoring the outcome of the data packet transmission attempts. A performance comparison clearly reveals the superiority of this preemptive polling scheme with respect to the classical cyclic polling scheme. This revised version was published online in June 2006 with corrections to the Cover Date.     

The effects of asymmetry on TCP performance

In this paper, we study the effects of network asymmetry on endtoend TCP performance and suggest techniques to improve it. The networks investigated in this study include a wireless cable modem network and a packet radio network, both of which can form an important part of a mobile ad hoc network. In recent literature (e.g., [18]), asymmetry has been considered in terms of a mismatch in bandwidths in the two directions of a data transfer. We generalize this notion of bandwidth asymmetry to other aspects of asymmetry, such as latency and mediaaccess, and packet error rate, which are common in widearea wireless networks. Using a combination of experiments on real networks and simulation, we analyze TCP performance in such networks where the throughput achieved is not solely a function of the link and traffic characteristics in the direction of data transfer (the forward direction), but depends significantly on the reverse direction as well. We focus on bandwidth and latency asymmetries, and propose and evaluate several techniques to improve endtoend performance. These include techniques to decrease the rate of acknowledgments on the constrained reverse channel (ack congestion control and ack filtering), techniques to reduce source burstiness when acknowledgments are infrequent (TCP sender adaptation), and algorithms at the reverse bottleneck router to schedule data and acks differently from FIFO (acksfirst scheduling).     

Tree multicast strategies in mobile,multihop wireless networks

Tree multicast is a well established concept in wired networks. Two versions, persource tree multicast (e.g., DVMRP) and shared tree multicast (e.g., Core Based Tree), account for the majority of the wireline implementations. In this paper, we extend the tree multicast concept to wireless, mobile, multihop networks for applications ranging from ad hoc networking to disaster recovery and battlefield. The main challenge in wireless, mobile networks is the rapidly changing environment. We address this issue in our design by: (a) using soft state (b) assigning different roles to nodes depending on their mobility (2level mobility model); (c) proposing an adaptive scheme which combines shared tree and persource tree benefits, and (d) dynamically relocating the shared tree Rendezvous Point (RP). A detailed wireless simulation model is used to evaluate various multicast schemes. The results show that persource trees perform better in heavy loads because of the more efficient traffic distribution; while shared trees are more robust to mobility and are more scalable to large network sizes. The adaptive tree multicast scheme, a hybrid between shared tree and persource tree, combines the advantages of both and performs consistently well across all load and mobility scenarios. The main contributions of this study are: the use of a 2level mobility model to improve the stability of the shared tree, the development of a hybrid, adaptive persource and shared tree scheme, and the dynamic relocation of the RP in the shared tree.     

Reliable Multicast in Multi-Access Wireless LANs

Multicast is an efficient paradigm for transmitting data from a sender to a group of receivers. In this paper, we focus on multicast in single channel multi-access wireless local area networks (LANs) comprising several small cells. In such a system, a receiver cannot correctly receive a packet if two or more packets are sent to it at the same time, because the packets collide. Therefore, one has to ensure that only one node sends at a time. We look at two important issues. First, we consider the problem of the sender acquiring the multi-access channel for multicast transmission. Second, for reliable multicast in each cell of the wireless LAN, we examine ARQ-based approaches. The second issue is important because the wireless link error rates can be very high.We present a new approach to overcome the problem of feedback collision in single channel multi-access wireless LANs, both for the purpose of acquiring the channel and for reliability. Our approach involves the election of one of the multicast group members (receivers) as a leader or representative for the purpose of sending feedback to the sender. For reliable multicast, on erroneous reception of a packet, the leader does not send an acknowledgment, prompting a retransmission. On erroneous reception of the packet at receivers other than the leader, our protocol allows negative acknowledgments from these receivers to collide with the acknowledgment from the leader, thus destroying the acknowledgment and prompting the sender to retransmit the packet.Using analytical models, we demonstrate that the leader-based protocol exhibits higher throughput in comparison to two other protocols which use traditional delayed feedback-based probabilistic methods. Last, we present a simple scheme for leader election.     

A Distributed Packet Scheduling Scheme with Interference Avoidance for Non Real-Time Applications in CDMA Networks

In this paper, a packet scheduling scheme based on real-time channel conditions and dominant intercell interferer avoidance is proposed, studied and evaluated for reverse links in a time-slotted code division multiple access (CDMA) system. This scheme is implemented by distribution of tags by receivers among transmitters. Each base station issues M(1) tags to M mobile users based on the ranked reverse link gains in every slot. M=1 corresponds to spread-spectrum time division multiplexing mode operation and M1 corresponds to scheduling multiple simultaneous transmissions as in the traditional CDMA systems. The number of issued tags is a system parameter which depends on the expected traffic, the number of cells and the propagation conditions in the network. In the proposed scheme, users who not only have stronger channel gains to their respective home base stations but also cause relatively lower intercell interference are scheduled for transmissions. Different classes of tags can be issued and various scheduling decision rules can be implemented giving flexibility in interference management. Simulation results in shadow and multipath fading environment are presented to show the performance advantage of the proposed scheme.     

Predictive Caching Strategy for On-Demand Routing Protocols in Wireless Ad Hoc Networks

Route caching strategy is important in on-demand routing protocols in wireless ad hoc networks. While high routing overhead usually has a significant performance impact in low bandwidth wireless networks, a good route caching strategy can reduce routing overheads by making use of the available route information more efficiently. In this paper, we first study the effects of two cache schemes, link cache and path cache, on the performance of on-demand routing protocols through simulations based on the Dynamic Source Routing (DSR) protocol. Since the path cache DSR has been extensively studied, we focus in this paper on the link cache DSR in combination with timer-based stale link expiry mechanisms. The effects of different link lifetime values on the performance of routing protocol in terms of routing overhead, packet delivery ratio and packet latency are investigated. A caching strategy incorporating adaptive link timeout is then proposed, which aims at tracking the optimal link lifetime under various node mobility levels by adaptively adjusting the link lifetime based on the real link lifetime statistics. The performance of the proposed strategy is then compared with the conventional path cache DSR. The results show that without a timeout mechanism, a link cache scheme may suffer severe performance degradation due to the use of broken routes, while the proposed adaptive link cache strategy achieves significantly improved performance by reducing the routing overhead when the network traffic load is high.     

Performance of Double-Tier Access-Control Schemes Using a Polling Backbone for Metropolitan and Interconnected Communication Networks

We consider a double-tier communication network architecture for metropolitan area and packet radio networks for controlling the access of network terminals into a single shared broadcast channel. Terminals are organized into local groups in accordance with their geographical proximity or other criteria. Each local group can be associated with a primary station. The latter can serve as an unbuffered repeater for terminal transmissions unto the multiple-access channel. A polling policy is used by the primary stations to gain access into the shared communications backbone. Once a primary station is provided access into the channel, it initiates a local access control procedure. Message delay performance results and bounds are obtained for general reservation local-access procedures. In particular, we analyze and present performance results for a polling/tree-random-access procedure which can be effectively used for many packet radio and cellular digital radio networks, as well as for a polling/positionalpriority scheme for CATV and fiber-optic based networks.     

A framework for delivering multicast messages in networks with mobile hosts

To accommodatemobile hosts (MHs) within existing data networks, the static network is augmented with mobile support stations (MSSs) that communicate directly with MHs, usually via wireless links. Connectivity of the overall network changes dynamically as MHs connect to the static network from different locations (MSSs) at different times. Compared to their desktop counterparts, mobile hosts face a new set of constraints namely, low bandwith of the wireless links, tight constraints on power consumption and a significantly lower computing capability. Thus, even without considering failures, integration of mobile computer within existing networks pose a new set of problems. In this paper, we look at the problems associated with delivering multicast meassages to mobile hosts. First, we identify how a mobile host's ability to connect to different MSSs at different times, affects delivery of multicast messages and present schemes to deliver multicast messages to MHs fromatleast-one location, fromatmost-one location, and fromexactly-one location. Next, we introduce multicast groups of mobile hosts wherein each multicast group is associated with a host view, a set of MSSs representing theaggregate location information of the group. A host-view membership algorithm is then presented and combined with the multicast scheme for exactly-once delivery. As a result, to deliver a multicast message to a specified group, copies of the message need be propagated only to the MSSs in the group's host-view.This work was done while the author was a graduate student at Rutgers University.This research work was supported in part by ARPA under contract number DAAH04-95-1-0596, NSF grant numbers CCR 95-09620, IRIS 95-09816 and sponsors of WINLAB.     

An adaptive algorithm for optimizing the packet size used in wireless ARQ protocols

We develop an algorithm that allows an ARQ protocol to dynamically optimize the packet size based on estimates of the channel biterrorrate. Our algorithm is particularly useful for wireless and satellite channels where the biterrorrates tend to be relatively high and time variable. Our algorithm uses the acknowledgment history to make estimates of the channel biterrorrate, based on which the optimal packet size can be chosen. We develop a Markov chain model for the analysis of the system, under static channel conditions, and show that the algorithm can achieve close to optimal performance using a history of just 10,000 bits. We also use the Gilbert–Elliott twostate Markov channel to model dynamic channel conditions. We show, through simulation, that the algorithm performs well even under rapidly changing channel conditions. Finally, we discuss a maximum likelihood approach for choosing the packet size, which performs almost optimally but is much easier to implement.     

Scalable parallel simulations of wireless networks with WiPPET: Modeling of radio propagation,mobility and protocols

We review the design, selected applications and performance of WiPPET (Wireless Propagation and Protocol Evaluation Testbed), a general parallel simulation testbed for various types of wireless networks. WiPPET has been written in TeD/C++, an objectoriented modeling framework that isolates network modeling from the underlying parallel discrete event simulator. We describe the techniques for modeling radio propagation (long and shortscale fading and interference) and protocols that promote scalability of parallel simulations at session and packet timescales. We outline two selected applications of WiPPET: integrated radio resource management in a mobile wireless network; and packet losses due to mobility and shortscale fading over a radio link. We illustrate the efficiency of the simulator under two partitioning schemes with parallel performance data obtained using the Georgia Time Warp optimistic simulator.     

Virtual Cellular Network: A New Wireless Communications Architecture with Multiple Access Ports

A virtual cellular network (VCN) is proposed to provide wireless random access for bursty multimedia traffic to a fixed backbone infrastructure. A VCN does not use a conventional cellular frequency reuse concept. In a VCN, each terminal sends packets using the entire system bandwidth while any nearby port can pick up the signal. Then, the ports relay the packets to the port server (PS) over a fixed (wired) network. Ports can be simple radio receivers as they do not have to support the same functionality as conventional cellular base stations. The performance is investigated in terms of probability of capture, throughput and delay. Both our analysis and simulation show that despite its simplicity this network has a larger user capacity than conventional cellular reuse patterns.     

A low power,low bandwidth protocol for remote wireless terminals

We present a low bandwidth protocol for wireless multimedia terminals targeted towards low power consumption on the terminal side. With the widespread use of portable computing devices, low power has become a major design criterion. One way of minimizing power consumption is to perform all tasks, other than managing hardware for the display and input, on a stationary workstation and exchange information between that workstation and the portable terminal via a wireless link. A protocol for such a system that emphasizes low bandwidth and low power requirements is presented herein. Such a protocol should address the issue of noisy wireless channels. We describe error correction and retransmission methods capable of dealing with burst error noise up to BERs of 10^-3. The final average bandwidth required is 140 Kbits/sec for 8bit color applications.     

Performance of a joint CDMA/PRMA protocol with heavy‐tailed ON/OFF source

The performance of a joint CDMA/PRMA protocol with heavy-tailed ON/OFF source has been studied. Compared with the random access scheme, the PRMA protocol improves the system performance (such as packet loss, throughput) whether the traffic is SRD or LRD. The less bursty traffic is, the greater the improvement. The buffer design should take into account knowledge about the network traffic such as the presence or absence of the Noah effect in a typical source, especially of _on, the intensity of the Noah effect of ONperiod. The smaller _on is, the smaller the buffering gain, and the more packets will be lost. LRD has impacts on the overall system performance. The Noah effect, especially _off, the intensity of the Noah effect of OFFperiod, has significant impact on the overall system performance such as capacity, time delay, etc. As _off gets closer to 1, the traffic becomes more bursty, the system capacity is decreased and time delay is increased.     

Tree Recovery in PIM Sparse Mode

A PIM–SM-built multicast tree must be restructured when the underlying unicast routing tables change. We describe the PIM–SM recovery mechanisms and evaluate the recovery performance, showing its dependence on a range of network and session parameters. Our results show that a substantial packet loss can be caused by nonreductive, benign events in the network, such as an addition of a new link. We propose and evaluate an improvement to the standard PIM–SM recovery procedure aimed to reduce the packet loss caused by the benign events. Our evaluation shows that the data loss caused by these events can be significantly decreased regardless of the topology and session parameters.     

VoIP Protection and Performance Improvement

A lot of ongoing work is geared towards improving the reliability, performance and QoS characteristics of service provider IP networks. In contrast, we propose novel enterprise-based techniques that exploit the fact that many enterprises are multi/dual-homed. In a form of service-aware routing, certain (e.g., VoIP) packets are duplicated (e.g., at one edge router) and sent over multiple service providers. After traversing the service provider networks, only the first-to-arrive packets are kept and the later-arriving copies are discarded. In so doing, the result is not only better protection against node and link failures, and packet losses and errors, but also better QoS performance under normal (fault-free) operation. The packet-duplication process can be policy-based and take into account costs, bandwidth, and priority issues, permitting the system to behave like a simple smart router that automatically and continually makes use of the best (lowest-delay) service provider. In this paper, we present the main ideas behind the proposal, along with some initial analytical and experimental/simulation results and insights from a Linux-based implementation.     

TCP Westwood: End-to-End Congestion Control for Wired/Wireless Networks

TCP Westwood (TCPW) is a sender-side modification of the TCP congestion window algorithm that improves upon the performance of TCP Reno in wired as well as wireless networks. The improvement is most significant in wireless networks with lossy links. In fact, TCPW performance is not very sensitive to random errors, while TCP Reno is equally sensitive to random loss and congestion loss and cannot discriminate between them. Hence, the tendency of TCP Reno to overreact to errors. An important distinguishing feature of TCP Westwood with respect to previous wireless TCP extensions is that it does not require inspection and/or interception of TCP packets at intermediate (proxy) nodes. Rather, TCPW fully complies with the end-to-end TCP design principle. The key innovative idea is to continuously measure at the TCP sender side the bandwidth used by the connection via monitoring the rate of returning ACKs. The estimate is then used to compute congestion window and slow start threshold after a congestion episode, that is, after three duplicate acknowledgments or after a timeout. The rationale of this strategy is simple: in contrast with TCP Reno which blindly halves the congestion window after three duplicate ACKs, TCP Westwood attempts to select a slow start threshold and a congestion window which are consistent with the effective bandwidth used at the time congestion is experienced. We call this mechanism faster recovery. The proposed mechanism is particularly effective over wireless links where sporadic losses due to radio channel problems are often misinterpreted as a symptom of congestion by current TCP schemes and thus lead to an unnecessary window reduction. Experimental studies reveal improvements in throughput performance, as well as in fairness. In addition, friendliness with TCP Reno was observed in a set of experiments showing that TCP Reno connections are not starved by TCPW connections. Most importantly, TCPW is extremely effective in mixed wired and wireless networks where throughput improvements of up to 550% are observed. Finally, TCPW performs almost as well as localized link layer approaches such as the popular Snoop scheme, without incurring the overhead of a specialized link layer protocol.     

Performance evaluation of polling systems for wireless localcommunication networks

This paper evaluates the performance of different polling systems used in wireless local networks where the transmission channel exhibits a nonstationary behavior. Many spatially dispersed data user terminals have been assumed to share a common short-range radio uplink channel to access a hub station. We have specifically considered cyclic polling systems with M queues (terminals), having the same general packet arrival process and general switchover period. The gated and exhaustive disciplines have been considered in ordering the transmission of the packets buffered at each terminal. By appropriately modeling the uplink channel, we propose analytical approaches to derive the average packet waiting time and the average cycle length for gated polling systems, combined with stop-and-wait (SW) and go-back-N (GBN) automatic repeat request (ARQ) techniques to control errors. A gated cyclic polling scheme combined with the selective-repeated (SR) stutter ARQ technique as well as an exhaustive cyclic polling scheme combined with SW, GBN, or SR stutter ARQ techniques, respectively, have also been considered In order to give an in-depth knowledge of the behavior of suitable polling alternatives for applications in wireless local communication networks     

Adaptive multicast routing in multirate loss networks

In this paper, we study two versions of the multicast routing problem in multirate loss networks: complete and partial. In the complete version of the multicast routing problem, the identities of all destination nodes are available to the multicast routing algorithm at once. Conversely, in the partial version of the multicast problem, the identities of the destination nodes are revealed to the routing algorithm one by one. Although the complete version of the multicast routing problem, also known as the Steiner tree problem, has been well studied in the literature, less attention has been paid for the definition of link costs and evaluating the performance of multicast routing algorithm from the network revenue point of view. Therefore, in this paper, we first propose two approaches, namely, the Markov Decision Processbased (MDPbased) and Least Loaded Routingbased (LLRbased) approaches, for defining link costs. Several heuristic multicast routing algorithms are then proposed for both fully connected networks and sparsely connected networks. We have also proposed a new performance metric, referred to as fractional reward loss, for evaluating the performance of multicast routing algorithms. Our simulation results indicate that algorithms based on partial destination information yield worse performance than those based on complete information. We also found that, for fully connected networks, algorithms that use LLRbased link costs yield very competitive performance as compared to those that use MDP approach. However, for sparsely connected networks, LLRbased algorithms yield significantly worse performance as compared to the MDPbased algorithms.     

Connection Admission Control and Comparison of Two Differentiated Resources Allocation Schemes in a Low Earth Orbit LEO Satellite Constellation

The Up/Down Link UDL of a Low Earth Orbit LEO satellite constellation is a scarce radio resource that needs to be shared efficiently between many users with different needs. A suitable Connection Admission Control (CAC) policy is required. In our study we assume that the network handles three types of calls: real time (voice) calls with strict constraints over the delay and over the bandwidth, non-real time (data) calls delay tolerant but with bandwidth guarantees requirements and Best Effort calls with no guarantees requirements. In order to ensure priorities are respected, two mechanisms are considered: an enhanced extended trunk reservation policy, as well as a combination of trunk reservation with priority scheduling in order to derive the Resources Allocation RA. A differentiated RA scheme is proposed, associated with queuing for the lower priority calls. Different unit bandwidths are associated with calls depending on their requirements. The analytical Markovian models for both the differentiated and the non-differentiated trunk reservation systems are first derived, under simplified hypothesis, in order to point out the advantages of the differentiated RA choice. Then, the model for another RA scheme, the combined differentiated trunk reservation/priority scheduling, is also analytically solved under Markovian hypothesis for the different traffic classes. The performance of the two more general versions of the RA techniques thus solved are compared using simulation. Impact of non-Markovian laws is also studied using simulation.