Abstract A quest for geographic routing schemes of wireless sensor networks when sensor nodes are deployed in areas with obstacles has resulted in numerous ingenious proposals and techniques. However, there is a lack of solutions for complicated cases wherein the source or the sink nodes are located close to a specific hole, especially in cavern-like regions of large complex-shaped holes. In this paper, we propose a geographic routing scheme to deal with the existence of complicated-shape holes in an effective manner. Our proposed routing scheme achieves routes around holes with the (1+ $$\epsilon$$ ϵ )-stretch. Experimental results show that our routing scheme yields the highest load balancing and the most extended network lifetime compared to other well-known routing algorithms as well.

The great French writer, historian and philosopher Voltaire once asked, "Is there anyone so wise as to learn by the experience of others?" In celebration of the 20th MobiCom conference, join us for a thought provoking discussion between pioneers of our field on the lessons they have learned over their illustrious career paths that accelerated the pace of technology adoption and enabled world-wide societal impact. Learn from our heroes as they share with us gems of wisdom on how to choose a great problem, what to avoid and how to be successful as you build your own remarkable careers.

The signalling subsystem is the most expensive and complex element in cellular networks. Today's networks use signalling mechanisms whose design builds on more than 20 years of the operational expertise. Despite this, the signalling subsystem of all mobile network standards remains vulnerable to failures of equipment and to sharp increases in offered load caused by unanticipated traffic patterns. In this work we analyse the technical vulnerability of paging - a key signalling mechanism that is responsible for notifying mobile terminals of downlink service requests. Our assessment considers the operation of Long-Term Evolution (LTE) networks and in particular the performance of the paging mechanism on the radio interface. We implemented the paging procedure in a simulator, and we propose and verify a mathematical model of the system behaviour. The proposed mathematical model effectively captures the non-zero threshold of paging failure probability; it is scrupulously precise for the paging loads below the nonzero threshold and delivers a close approximation with the increasing paging load. The mathematical model can be applied to optimise the performance of the paging mechanism and to devise techniques able to overcome its technical vulnerability.

In this paper, we present the Airtime Deficit Round Robin (ADRR), a novel scheduling algorithm for IEEE 802.11-based wireless networks. The ADRR mechanism enhances the Deficit Round Robin scheduling discipline by taking into account the channel quality experienced by the transmitting node. The devised algorithm addresses the IEEE 802.11 performance anomaly, preventing a node which experiences poor channel conditions from monopolizing the wireless medium, lowering the performance of the whole system. The proposed approach combines link scheduling with measurable routing metrics. Simulation analyses have shown that the proposed scheme can achieve performance isolation among links characterized by heterogeneous channel conditions. A real prototype has been implemented and evaluated over a small scale testbed confirming the simulation results.

We show how the TUNEGreen real-time energy consumption monitoring capabilities can be used to understand how and where power is consumed in a simple star-shaped network based on IEEE 802.11. Different traffic patterns will be generated in order to demonstrate the correlation between traffic and energy consumption.

As the number and capabilities of mobile devices is rapidly increasing, new challenges arise in the way services are currently designed. Users are seeking for more complex and advanced functionalities able to satisfy their increasing requirements. As a consequence, in ubiquitous environments, a different way to design services has to be introduced in order to guarantee services always up to date in a transparent and efficient way. In this paper, we present and analyze a framework for distributed cooperative service evolution in a wireless nomadic environment. In particular, we assume a disconnected network architecture, where users' mobility is exploited to achieve a scalable behavior, and communication is based on localized peer-to-peer interactions among neighboring nodes. Service management is achieved by introducing autonomic services, whose operations are based on a distributed evolution process, which draws tools and concepts from evolutionary computation (and genetic algorithms in particular). The latter relies on the concept of recombination , i.e., the exchange of information among service users, which collaborate to enhance their fitness , defined as the ability of the actual service to fulfill user's requirements. We introduce a general framework for analyzing service recombination policies and exploit results from martingales theory to study their convergence properties.

In this paper we study the performance of periodic spectrum sensing in cognitive radios (CR) based on experimentally obtained temporal spectral occupancy statistics of the legacy user (LU). The detection performance of the periodic sensing technique depends on the occupancy statistics of the LU such as the traffic arrival rate and the occupancy duration. The sensing period and the sensing duration requirements also depend on the temporal statistics of the LU in order to achieve a predefined detection probability. The LU services that we consider here are the UMTS voice and the HSDPA data services that operate in the 2100MHz frequency range. The UMTS and HSDPA spectral occupancy behaviors are experimentally analyzed using real world measurements performed by Telefónica I+D in order to find the white spaces or spectrum holes associated with it, which are then used to study the detection performance of the periodic sensing technique. The temporal characteristics such as the occupancy distribution and the approximated occupancy-time plot are presented for the UMTS/HSDPA services based on the experimentally obtained data. The probability of detection is then presented with respect to the sensing period and the duration, based on a temporal spectral occupancy model that we derive from the experimentally obtained occupancy statistics.

The technology world is experiencing the emergence of a generation of massive-scale networked digital systems, performing complex operations that are partially out of the control of the systems' designers. This is the case, e.g., of pervasive computing environments, characterized by the proliferation of embedded electronic devices with communication and computing capabilities, able to network themselves forming a “digital halo” surrounding the user in its daily activities. In this paper, we advocate the use of bottom-up design patterns, able to build on results in complex systems science and systems biology, for devising new solutions for designing and managing such environments. We also present a possible application to a novel cyberphysical ecosystem, that we call the Energy Web, arising from the combination of innovative information and communication technologies with distributed renewable energy sources.

Operating on a frequency band occupying several nonoverlapping channels, IEEE 802.11 is now widely used in Wireless Mesh Networks (WMNs). Many multichannel MAC protocols are proposed to improve the spatial reuse in the network under the assumption that the transmissions on nonoverlapping channels do not interfere with each other. Some joint routing and channel assignment algorithms are also designed to increase the network throughput based on the premise that we can switch between different channels freely. Although simulations show that great improvements on network throughput can be observed in both cases, two fundamental questions remain: 1) Can we really use multiple nonoverlapping channels freely in WMNs? 2) If we can, what will be the cost when we switch channels dynamically and frequently? In this paper, by conducting extensive experiments on our testbed, we attempt to answer these questions. We find that in spite of interference between both overlapping and nonoverlapping channels, we can still use multiple channels in mesh networks under certain conditions but with care. We also show that the channel switching cost is actually very significant in WMNs. We recommend not to switch the channels too frequently when designing the channel assignment algorithms, and those channel assignment algorithms selecting one channel for each packet are not really beneficial.

With the availability of multiple rates in IEEE 802.11 a/b/g wireless LANs, it is desirable to improve the network capacity and temporal fairness by sending multiple consecutive frames over high rate links, as proposed in opportunistic auto rate (OAR [1]). However, the basic OAR does not provide quality of service (QoS) guarantee and thus is not sufficient in supporting real time voice/video traffic. In this paper, we further enhance the OAR protocol with a set of QoS mechanisms. The proposed QOAR protocol consists of two protocols: (i) a traffic- differentiating flow weight adaptation protocol (FWA) that dynamically tunes both contention window and concatenation number per channel access; (ii) an admission control protocol (AC) that guarantees the bandwidth/delay requirements of multimedia services. Extensive simulation studies show that QOAR enables QoS for real-time traffic yet maximizes performance of best effort traffic.

Providing quality of service (QoS) to users in a wireless ad-hoc network is a key concern for service providers. With the availability of multiple rates in IEEE 802.11a/b/g wireless LANs, it is desirable to improve the network capacity and temporal fairness by sending multiple consecutive frames (also referred as frame concatenation mechanism) over high rate links, as proposed in opportunistic auto rate (OAR). However, OAR does not consider the effect of frame sizes and may yield unsatisfactory performance for high priority multimedia flows transmitting over low rate links. Therefore, a more appropriate frame concatenation strategy and a corresponding service differentiation scheme should be devised to provide better performance for high priority voice/video flows than low priority data flows, under various channel rate scenarios. We first analyze the effect of frame size on the performance of OAR. Then, we propose a general concatenation mechanism (GCM), a more accurate frame concatenation mechanism for multi-rate MAC with better fairness. Finally, we propose two mechanisms: adaptive weighted fair frame concatenation mechanism (AWFCM) and adaptive QoS aware frame concatenation mechanism (AQCM), for supporting service differentiation and QoS in multi-rate wireless ad hoc networks. The primary idea is to adjust the number of concatenated frames based on flow weights/priorities, frame sizes, link rates, and network traffic. Simulation results show that the proposed mechanisms achieve desirable performance on supporting multimedia applications in multi-rate wireless ad-hoc networks.

In this paper we present airtime deficit round robin (ADRR) a novel scheduling algorithm for IEEE 802.11-based wireless mesh networks. ADRR enhances the deficit round robin scheduling discipline by taking into account the channel quality experienced by the transmitting node. The devised algorithm addresses the IEEE 802.11 performance anomaly, preventing a node which experiences poor channel conditions from monopolizing the wireless medium lowering the performance of the whole system. The proposed approach combines link scheduling with measurable routing metrics typically available in WMNs. Results show the ability of the ADRR scheduler to achieve performance isolation among links characterized by heterogeneous channel conditions. The proposed solution has been implemented and tested over an IEEE 802.11-based wireless mesh network. Source code has been released under a BSD License making it fully available to the research community.

IEEE 802.16 mesh networking has attracted significant commercial interests recently. In this paper, we propose a unified Collision-Free Coordinated Distributed Scheduling (CFCDS) algorithm for both control and data transmissions in IEEE 802.16 Mesh mode. Compared to corresponding algorithms defined by the standard [1][3], CF-CDS has two major advantages: (i) CF-CDS truly achieves collision-free control scheduling while the standards CDS algorithm does not, although it claims to; (ii) in addition to periodic scheduling for the control subframe, CF-CDS can be applied to on-demand data scheduling in the data sub-frame, where it outperforms the CDS-based 3- way handshakes approach adopted by the standard. We provide performance comparison between standard algorithms and CFCDS through extensive simulation.

Ultra Wideband (UWB) technology has been considered as one of the suitable transmission techniques for implementing a cognitive radio system, where spectrum-agile UWB waveforms achieve a number of spectral adaptation features. One approach for designing such waveforms relies on orthogonally combining PSWF (Prolate Spheroidal Wave Functions) based pulse wavelets. In a cognitive UWB radio environment when the transmit signal is M-ary pulse shape modulated, we can obtain M different eigenvalues corresponding to the M PSWF-based pulses while transmitting them through the multipath fading channel. Each eigenvalue represents the multipath channel gain for its corresponding pulse. We propose an optimal power allocation scheme depending on the eigenvalues to improve bit error rate (BER) performance in such a cognitive UWB radio environment. Numerical results show that the scheme outperforms the general equal power allocation scheme.

In this paper we propose a novel architecture integrating a fiber optic infrastructure with 60 GHz wireless transmission, capable of delivering a data rate up to 1 Gbps per cell in indoor environment. The system uses a hybrid WDM/TDM PON as the fixed infrastructure and the 60 GHz radio to provide the end user access and mobility. A centralized medium access control mechanism derived from IEEE 802.3ah is adopted for efficient channel access and bandwidth allocation. The use of standard components and the dynamic bandwidth allocation across wireless cells makes the system a strong candidate for future gigabit wireless LANs.

There are many different channels denned in the IEEE 802.11 standard. However, the performance of WiFi networks still greatly suffers from the interference between users, even if they are using different channels. In this paper, we conduct some theoretical analysis of the interference between two channels, which is further verified by experiments. We show that there is indeed serious interference between two non- overlapping channels if they are close to each other.

As the radio spectrum usage paradigm shifting from the traditional command and control allocation scheme to the open spectrum allocation scheme, wireless mesh networks meet new opportunities and challenges. The open spectrum allocation scheme has potential to provide those networks more capacity, and make them more flexible and reliable. However, the freedom brought by the new spectrum usage paradigm introduces spectrum management and network coordination challenges. In this paper, we study the network formation problem in cognitive radio based mesh networks. A cluster-based approach is proposed to form a mesh network in the context of cognitive radio scenario. Moreover, a topology management algorithm is developed to optimize the cluster configuration with regard to the network topology. The prominent feature of the proposed approach lies in the capability to adapt the cluster configuration to network and radio environment changes.

This paper deals with a system level design solution to support information gathering in the presence of a mobile querying node that experiences frequent disconnections from a Wireless Sensor Network (WSN), an application scenario that embraces the area of Intelligent Transportation Systems (ITS). The proposed scheme basically relies on the network capability of autonomously adapting to sink mobility in order to properly deliver the requested data. The system is defined as far as its functional elements and related communications protocols, together with validating its effectiveness by means of a simulative study. In particular, the performance in terms of delivering latency and packet delivery ratio has been investigated for several network topologies, architecture and mobility pattern, always highlighting a remarkable quality of provided services together with robustness with regard to operative conditions.

Recently, research on disconnected networks has been fostered by several studies on delay-tolerant networks, which are designed in order to sustain disconnected operations. We focus on the emerging notion of connectivity which exists in such networks, where the message exchange between nodes is enforced by leveraging storage capabilities at intermediate relays, with the aim of achieving connectivity over time. The problem, under the constraint of intermittent connectivity, is hence to devise efficient mechanisms for message delivery, and evaluate the performance thereof. In this paper, we introduce a graph-based model able to capture the evolution of the connectivity properties of such systems over time. We show that, for most networks of interest, such connectivity graphs can be modeled as Erdos-Renyi random graphs. Furthermore, we show that, under a uniformity assumption, the time taken for the connectivity graph to become connected scales as Theta((n log n)/lambda) with the number of nodes in the network. Hence we found that, using epidemic routing techniques, message delay is O((n log2n)/(lambda log log n)). The model is validated by numerical simulations and by a comparison with the connectivity patterns emerging from real experiments.

In this work, we present a multi-resolution data management scheme for efficiently storing and diffusing information, which is originating from sensors and augmenting mobile applications. The proposed mechanism exploits the discrete wavelet transform properties for providing a location-dependent data management scheme, which alleviates the constraints on the storage resources needed for running context-aware mobile applications. The data management scheme has been implemented and evaluated by means of numerical simulations.

The emergence of future pervasive ICT environments, characterized by the massive proliferation of embedded electronic devices with communication and computing capabilities, are posing enormous challenges to existing approaches to networking, service provisioning and system management. In this paper, we make a case to go for biology as possible source of novel, revolutionary design patterns suitable to large-scale highly dynamic ICT systems. We also present a case study, the EU- funded BIONETS project, which tackles the increased complexity of large-scale ubiquitous systems by applying an evolutionary framework to the provisioning of pervasive services.

Infrared communication has been recently reconsidered as an alternative to microwave radio used by WLAN devices, suitable for specific applications such as hospitals or industrial communication in the presence of strong electromagnetic fields. The design of a system able to communicate efficiently even without line of sight (LOS) and in the presence of fading represents a challenging issue for a wider utilization of IR. The growing interest in the field of radio communication towards MIMO systems has encouraged few researchers to use similar techniques to fight fading effects of the diffuse infrared channel. As a first step in the design of an infrared node for diffuse communication the authors developed a complete simulation framework to evaluate the performance of diversity techniques for IR. The authors also introduce a blind channel estimator for IR MIMO receivers. Results show that diversity leads to consistent performance improvements for the IR channel in the presence of fading.

Distributed lightpath provisioning is expected to play a key role in next-generation WDM optical networks. A major challenge in distributed lightpath provisioning is the potentially significant degradation of network blocking performance caused by outdated link-state information, occurring especially under traffic with short average durations of connections. To address this problem, various parallel reservation schemes have been proposed, with the common feature of applying multiple capacity-search and/or reservation operations executed simultaneously. In this paper, we evaluate the performance of these distributed parallel reservation schemes in wavelength-routed networks. Specifically, we develop general yet accurate analytical models to provide insights into the behavior of the different schemes. We also conduct extensive simulation study. Numerical results show that by using simple parallel reservation schemes, in particular through multiple reservations on several different routes, blocking probabilities caused by outdated link-state information can be drastically lowered and network performance can be significantly improved. The tradeoff between control traffic loads and network blocking performance is also evaluated.

With the increase of the number of wavelengths per fiber, waveband switching has been proposed to decrease the number of switching ports in optical nodes. Another concept, that of Light trails, allows the intermediate nodes along a lightpath to access the wavelength channel, aiming at the reduction of the number of wavelengths. Both techniques apply traffic grooming on different levels of the WDM network. In this paper, we combine them and compare the two switching techniques: waveband switching lightpath (WBS-LP) and waveband switching lighttrail (WBS-LT). Auxiliary graph models (LP_AG/LT_AG) are proposed for WBS-LP/WBS-LT respectively. These two auxiliary graph models can exploit not only the wavelength resource in the fiber links but also the limited waveband ports resource inside the multi-granular optical cross connects (MG-OXC) nodes. The influence of network parameters, e.g. number of wavebands, ports and transceivers, is studied. The proposed algorithms are compared with shortest path (SP), least-weighted path (LW), and K-least-weighted path (KP) algorithms; numerical simulations show their better performance. For different algorithms, WBS-LT can have better blocking performance than WBS-LP especially when add/drop waveband ports are the critical resources.

In this paper, we analyze the performance of a family of opportunistic forwarding schemes (the K-copy relaying strategies) over disconnected wireless networks. We introduce a classification of mobility models based on their dynamic properties, and characterize the M2(marks-memory less) class. Statistical tools are combined with numerical simulations to show that some of the most used mobility models in the literature fall within the M2class. A mathematical framework is provided for evaluating the performance of opportunistic forwarding schemes in the presence of M2mobility, and it is shown that the finiteness of the mean time necessary to deliver a message depends only on the mobility characteristics and not on the relaying protocol specification

Cognitive ultra-wideband (UWB) radio is proposed to exploit the advantages and the unique features of enhancing UWB wireless technologies by utilizing cognitive radio functionality. In order to achieve the cognitive UWB radio, multiple pulse waveforms adaptation has been investigated for producing the expected spectral notches while matching with the Federal Communications Commission (FCC) spectral mask. Then the specifically designed pulse waveform with adaptive spectral notches is tested by high-speed digital processing unit for implementation estimation. To verify the pulse distortion effects of UWB antenna in the cognitive UWB radio, the generalized pulse waveform is further transferred through an actual UWB antenna. Furthermore, a pulse waveform predistortion scheme is considered before antenna transmission, so as to compensate the pulse distortion effects.

The increasing demand for high bandwidth and mobility has challenged research to design innovative broadband wireless access networks. The 60 GHz band has recently been attracting interest because of the huge bandwidth it can provide from its 3-7 GHz unlicensed spectrum available worldwide. However, until now a mature system design in the 60 GHz band is still lacking. In this paper, we propose a novel architecture integrating a fiber optic infrastructure with 60 GHz wireless transmission capable of delivering a high data rate of 1 Gbps per cell in indoor environments. We use a WDM upgraded EPON as the fixed infrastructure and the 60 GHz band to provide the end user access and mobility. A centralized media access control mechanism derived from IEEE 802.3ah is adopted for efficient channel sharing. The use of standard components and the dynamic bandwidth allocation across wireless cells make the system a strong candidate for future gigabit wireless LANs.

This paper presents a novel solution of bidirectional high speed communications for IP traffic transport over WDM networks. Based on the observation of the bidirectional nature of traffic in the Internet bidirectional light-trails are proposed as an extension of the natively unidirectional light-trail concept. Specification of a synchronous protocol enables fairness in medium access and data delivery improving reliability of communications and enabling QoS support in WDM networks

In today's WDM networks the dominating cost factor is the number of transceivers. Light trails have been shown to reduce the total number of wavelengths, however not necessarily the number of transceivers used in the network. Within this paper we explain two mechanisms that deal with reducing the total number of transceivers in light trail networks. While the first method - 'tune in' light trails (TILT) - ensures that this number is at most the one of a corresponding lightpath network, traffic grooming can be applied in light trail networks as well to reduce the number of transceivers even further. Simulation results show that the TILT network has much better performance than the traditional counterpart, especially when the number of transceivers in the network is limited. Also the light trail network with grooming has better performance than that without grooming

Cooperative transmission scheme utilizing Space-Frequency coding (SFC) is investigated for cognitive Ultra Wideband (UWB) communications and networks, in the cases where multiple relaying is necessary among distributed nodes. The new scheme avoids the issue of the lack of required perfect synchronization on propagation delay and timing among the distributed nodes while using virtual multi-input multi-output (MIMO) algorithms. By computer simulations, it is shown that in the modified IEEE 802.15.3a S-V channel, the proposed SFC scheme combined with selective Rake receiver achieves almost the same BER performance compared with Alamouti's Space-Time block coding (STBC) performance. The most promising perspective of this new scheme relies on its application to Cognitive UWB Radio and its networking in potentially providing full spatial and frequency diversity. Moreover, the proposed cooperative relaying scheme is capable of matching with the FCC emission mask while still achieving interference avoidance as well as efficient wireless transmission.

In this paper, we analyze the blocking probability of distributed lightpath establishment in wavelength-routed WDM networks by studying the two basic methods: destination-initiated reservation (DIR) and source-initiated reservation (SIR). We discuss three basic types of connection blocking: 1) blocking due to insufficient network capacity; 2) blocking due to outdated information; and 3) blocking due to over-reservation. It is shown that the proposed models are highly accurate for both the DIR and the SIR methods, in both the regular and irregular network topologies, under the whole range of traffic loads.

In this paper, we provide a new analytical model for evaluating the blocking performance of dynamic lightpath establishment in multifiber wavelength-routed networks. By adopting the simple link-independent model together with the wavelength correlation assumptions, we manage to achieve a good balance between analytical accuracy and computational complexity. Extensive numerical results show that the proposed model can quickly produce accurate analytical results under different traffic loads and in different networks.

The intensive handoff calls from surrounding cells, triggered by non-uniform traffic distribution, cause more serious quality of service (QoS) deterioration problems than uniform traffic distribution because they usually cannot be regulated by admission control. This paper proposes an on-line hot-spot detection scheme, which predicts the presence of hot-spots and assists the admission control to reduce the handoff deterioration probability. Our proposed scheme consists of two procedures: 1) a utilization trend detection procedure, which predicts the traffic load of the desired sector from its past utilization information; and 2) an aggregated utilization procedure, which estimates how close is the desired sector to the hot-spot regime. Simulations show that under an acceptable new call blocking probability, the proposed scheme decreases the handoff deteriorating probability of the hot-spot cells and their surrounding cells.

We propose an architecture and an algorithm for the realization of a pragmatic framework for optical packet transport. The architecture enables the transport of IP packets over optical frames in a network. While doing so, it relaxes the need for address recognition as well as for high speed switching, the two key hindering factors that have prevented contemporary optical packet transport solutions from being deployed. We propose the light-frames architecture for sub-lambda level provisioning of optical paths. The idea is to create a logical topology that allows N/sup 2/ connectivity using optical paths that are by themselves sublambda provisionable yielding in packet transport. We show that by using substantially fewer resources, we can provide N/sup 2/ connectivity in arbitrary graphs to support optical packet transport.

The rapid growth of IP centric communication in worldwide networks and the parallel mass deployment of fiber based WDM networks have propelled IP over WDM being considered as an eventual solution for bandwidth on demand to customers. Contemporary optical networks are, however, based on lightpath communication and a lightpath represents end-to-end optical circuits from source to destination. Light-trails are a generalization of lightpaths, such that multiple nodes along a trail can participate in time differentiated communication over the same established trail. Managing and setting up of light-trails in order to cater to IP centric traffic is a key to the success of IP centric communication at the optical layer. A light-trail represents an open optical path that allows multiple users to communicate without the need for switch reconfiguration at any user node, the light-trail itself being static. IP communication on the other hand represents a bursty traffic flow often characterized by spurts or bursts of data. The goal of this paper is to show how to create efficient light-trails based virtual topology for a given network traffic flow. We first describe a tree-shaped variant of light-trail, called the clustered light-trail (CLT) and then present optimization techniques for satisfying the given IP centric communication requirements, using the light-trails framework that is very flexible, despite being basically a static mechanism.

To ensure probabilistic guarantees on quality of service in content delivery networks (CDN), an access control support is needed that takes into account a proper differentiation of requests and performs session based decisions, managing different types of services and different service phases. In this paper we introduce a CDN architecture with access control capabilities at session aware access routers. We formulate a Markov modulated Poisson decision process for access control that captures the heterogeneity of multimedia services and the variable availability of resources due to the network congestions that characterize a non-dedicated network environment. The structural properties of the optimal solutions are studied and considered as the basis for the formulation of heuristics that perform close to the optimal policy.

With information access becoming more and more ubiquitous, there is a need for providing QoS support for communication that spans wired and wireless networks. For the wired side, RSVP/SBM has been widely accepted as a flow reservation scheme in IEEE 802 style LANs. In this paper, we investigate the integration of RSVP and a RSVP-like flow reservation scheme in wireless LANs, as an end-to-end solution for QoS guarantee in wired-cum-wireless networks. We propose WRESV, an RSVP-like flow reservation and admission control scheme for IEEE 802.11 wireless LAN. Using WRESV, wired/wireless integration can be easily implemented by cross-layer interaction at the access point. Main components of the integration are RSVP-WRESV parameter mapping, and the initiation of new reservation messages, depending on where senders/receivers are located. In addition, we also propose various optimizations for supporting multicast session, mobility management, and admission control.

This paper proposes overflow control schemes to support high-speed downlink packet access (HSDPA) mechanism in the universal mobile telecommunication system (UMTS). To access the UMTS services, a user equipment (UE) communicates with all cells (base stations) in an active set. However, multiple links between the UE and the cells in the active set may reduce the transmission speed due to interference. Third-Generation Partnership Project specification TR 25.950 proposes HSDPA. In this mechanism, the UE only selects one cell (referred to as the serving cell) in the active set for high-speed downlink transmission. In HSDPA, the radio network controller sends the packet frames to the cells in the active set. For the serving cell, the packet frames are forwarded to the UE. On the other hand, every nonserving cell in the active set queues the packet frames in a buffer. If the link quality between the serving cell and the UE degrades below some threshold, the UE selects the best cell in the active set as the new serving cell. Since the nonserving cells do not send packet frames to the UE, their buffers may overflow. In this paper, we propose schemes to address the buffer overflow issue. Our schemes guarantee that when the buffer of a nonserving cell is full, the previously received packet frames in the buffer can be safely dropped, and after the UE has switched wireless link to the new serving cell, no packet frames are lost.

For video broadcasting applications in a wireless environment, layered transmission is an effective approach to support heterogeneous receivers with varying bandwidth requirements. There are several important issues that need to be addressed for such layered video broadcasting systems. At the session level, it is not clear how to allocate bandwidth resources among competing video sessions. For a session with a given bandwidth, questions such as how to set up the video layering structure (i.e., number of layers) and how much bandwidth should be allocated to each layer remain to be answered. The solutions to these questions are further complicated by practical issues such as uneven popularity among video sessions and video layering overhead. This paper presents a systematic study to address these issues for a layered video broadcasting system in a wireless environment. The approach is to employ a generic utility function for each receiver under each video session. They cast the joint problem of layering and bandwidth allocation (among sessions and layers) into an optimization problem of total system utility among all the receivers. By using a simple two-step decomposition of intersession and intrasession optimization, they derive efficient algorithms to solve the optimal layering and bandwidth allocation problem. Practical issues for deploying the optimal algorithm in typical wireless networks are also discussed. Simulation results show that the optimal layering and bandwidth allocation improves the total system utility under various settings.

The recent industry standard Bluetooth promises low cost replacement of communication cabling with moderate symbol-rate, short-range wireless links. The same specification also addresses the establishment of point-to-multipoint piconets and the interconnection of several of these piconets into scatternets, enabling Bluetooth to be used as a technology for realizing personal area networks. Establishing Bluetooth piconets requires nodes to discover each other by completing an inquiry phase. This paper investigates the inquiry phase; shows the shortcomings of the current inquiry procedure in multi node-PAN scenarios, and outlines and analyses a backwards Bluetooth compliant modification to accelerate Bluetooth inquiry. Extensive simulations comparing the original and the proposed Bluetooth inquiry schemes show improvements of more than an order of magnitude in device discovery times.

In this paper we propose a solution to implement Ethernet over PON using two unidirectional channels for access networks. The protocol called TUR is efficient and scalable and easy to implement using conventional mature technologies. We discuss strategies to deploy both upstream as well as downstream communication. Possible end-user designs are also discussed in connection to the protocol. A simulation study verifies the protocol and compares to contemporary solutions.

In this work, we propose a new distributed signaling scheme, within the GMPLS framework for establishing lightpaths in wavelength-routed networks with sparse wavelength conversion. Analytical models are developed to evaluate the performance of the proposed scheme. Theoretical and simulation results show that compared to the classic schemed designed primarily for networks with no wavelength conversion, the proposed signaling scheme can achieve much lower blocking probability.

In this paper we study the inter- and intra- steam synchronization control schemes in networks with large end-to-end delays. We analyze pros and cons of different types of control schemes, focusing on the performance criterion of minimizing the jitter variance with the media stream for intra-stream synchronization, considered the most important objective. The minimum variance controller model is introduced to analyze the feasibility of feedback control schemes to achieve this objective. Due to the constraints of the distributed multimedia system model, especially when the average end-to-end network delay d/sub avg/ is large (compared to the duration of the playback of the full buffer, 2/spl Delta/), we show that within a single stream (at least the master stream), the playback performance of any kind of feedback control scheme cannot be better than the uncontrolled system. Therefore, we can remove the feedback loop to reduce communication overheads and computation complexity. Given the increasing size of global networks and the integration of wireless services the delays are gradually increasing, making this result of increased importance in the emerging networking paradigms.

Light-trails communication (Chlamtac and Gumaste, 2003) proposes a solution for implementing a conceptual framework for IP centric communication in the optical domain which is a combination of node architecture and protocol for realizing efficient optical communications from IP bursts to dynamic lightpaths. In this paper we introduce a Light-trails solution that is applicable to mesh networks. Contrary to existing proposals for IP type communication in the optical domain light-trail node architecture also presents the first practically implementable solution to enable optical transport with mature technology, nonstringent optical switching requirements, and potentially presents a cost effective alternative to electronics in supporting IP networks.

Having been originally developed as an extension of the wired LANs, IEEE 802.11 lacks support for QoS and differential services. Since its introduction various extensions and modifications have been studied to address this current need and the IEEE 802.11 Task Group E is responsible for developing a QoS-aware MAC protocol that considers several service differentiation mechanisms. In this paper, we first consider the enhanced DCF access method of IEEE 802.11e. We then introduce an analytical model, which can be used to calculate the traffic priority and throughput corresponding to the configuration of multiple DCF contention parameters under saturation condition. A detailed simulation is provided to validate the proposed model.

For video broadcasting applications in a wireless environment, layered transmission is an effective approach to support heterogeneous receivers with varying bandwidth requirements. There are several important issues that need to be addressed for such layered video broadcasting systems. At the session level, it is not clear how to allocate bandwidth resources among competing video sessions. For a session with a given bandwidth, questions such as how to set up the video layering structure (i.e., number of layers) and how much bandwidth should be allocated to each layer remain to be answered. The solutions to these questions are further complicated by practical issues such as uneven popularity among video sessions and video layering overhead. This paper presents a systematic study to address these issues for a layered video broadcasting system in a wireless environment. Our approach is to employ a generic utility function for each receiver under each video session. We cast the joint problem of layering and bandwidth allocation (among sessions and layers) into an optimization problem of total system utility among all the receivers. By using a simple 2-step decomposition of inter-session and intra-session optimization, we derive efficient algorithms to solve the optimal layering and bandwidth allocation problem. Practical issues for deploying the optimal algorithm in wireless networks are also discussed. Simulation results show that the optimal layering and bandwidth allocation improves the total system utility.

Distributed wavelength provisioning is becoming one of the most important technologies for supporting the next-generation wavelength-routed networks. In this paper we analyze the behavior of wavelength-routed networks with partial wavelength conversion capabilities (i.e., where wavelength conversion is available at only a subset of network nodes) when using distributed wavelength provisioning. Simulation results show that the proposed models are highly accurate for different network topologies under various traffic loads.

A problem of many distributed lightpath provisioning schemes is wavelength contention, which occurs when a connection request attempts to reserve a wavelength channel that is no longer available. This situation results from the lack of updated global link-state information at every node. In networks with highly dynamic traffic loads, wavelength contention may seriously degrade the network performance. To overcome this problem, we propose a new framework for distributed signaling and introduce a class of schemes referred to as intermediate-node initiated reservation. In the new scheme, reservations may be initiated at any set of nodes along the route; in contrast, reservations can only be initiated by the destination node in the classic destination initiated reservation (DIR) scheme. As a result, the possibility of having outdated information due to propagation delay is significantly lowered. Specifically, we consider two schemes within this framework, for networks with no wavelength conversion and for networks with sparse wavelength conversion, respectively. Theoretical and simulation results show that, compared with the classic DIR scheme, the new schemes can significantly improve the network blocking performance. The accuracy of the analytical models is also confirmed by extensive numerical simulations.

Describes a protocol for the establishment of multihop ad hoc networks based on Bluetooth devices. The protocol proceeds in three phases: device discovery, partitioning of the network into Bluetooth piconets, and interconnection of the piconets into a connected scatternet. The protocol has the following desirable properties: it is executed at each node with no prior knowledge of the network topology, thus being fully distributed. The selection of the Bluetooth masters is driven by the suitability of a node to be the "best fit" for serving as a master. The generated scatternet is a connected mesh with multiple paths between any pair of nodes, thus achieving robustness. Differently from existing solutions, no extra hardware is required to run the protocol at each node and there is no need for a designated node to start the scatternet formation process. Simulation results are provided which evaluate the impact of the Bluetooth device discovery phase on the performance of the protocol.

Sparse wavelength conversion and appropriate routing and wavelength assignment (RWA) algorithms are the two key factors in improving the blocking performance in wavelength-routed all-optical networks. It has been shown that the optimal placement of a limited number of wavelength converters in an arbitrary mesh network is an NP-complete problem. There have been various heuristic algorithms proposed in the literature, in which most of them assume that a static routing and random-wavelength assignment RWA algorithm is employed. However, the existing work shows that fixed-alternate routing and dynamic routing RWA algorithms can achieve much better blocking performance. Our study further demonstrates that the wavelength converter placement and RWA algorithms are closely related in the sense that a well-designed wavelength converter placement mechanism for a particular RWA algorithm might not work well with a different RWA algorithm. Therefore, the wavelength converter placement and the RWA have to be considered jointly. The objective of this paper is to investigate the wavelength converter placement problem under the fixed-alternate routing (FAR) algorithm and least-loaded routing (LLR) algorithm. Under the FAR algorithm, we propose a heuristic algorithm called minimum blocking probability first for wavelength converter placement. Under the LLR algorithm, we propose another heuristic algorithm called weighted maximum segment length. The objective of the converter placement algorithms is to minimize the overall blocking probability. Extensive simulation studies have been carried out over three typical mesh networks, including the 14-node NSFNET, 19-node EON, and 38-node CTNET. We observe that the proposed algorithms not only outperform existing wavelength converter placement algorithms by a large margin, but they also can achieve almost the same performance compared with full wavelength conversion under the same RWA algorithm.

This paper proposes overflow control scheme to support high-speed downlink packet access (HSDPA) mechanism in the Universal Mobile Telecommunication System (UMTS). To access the UMTS services, a user equipment (UE) communicates with all cells (base stations) in an active set. However, multiple links between the UE and the cells in the active set may reduce the transmission speed due to interference. 3GPP specification TR 25.950 proposes HSDPA. In HSDPA, the UE only selects one cell (referred to as the serving cell) in the active set for high-speed downlink transmission. In this mechanism, the radio network controller sends the packet frames to the cells in the active set. For the serving cell, the packet frames are forwarded to the UE. On the other hand, every non-serving cell in the active set queues the packet frames in a buffer. If the link quality between the serving cell and the UE degrades below some threshold, the UE selects the best cell in the active set as the new serving cell. Since the non-serving cells do not send packet frames to the UE, their buffers may overflow. In this paper, we propose the scheme to address the buffer overflow issue. Our scheme guarantees that when the buffer of a non-serving cell is full, the previously received packet frames in the buffer can be safely dropped, and after the UE has switched wireless link to the new serving cell, no packet frames are lost.

In this paper, we analyze the blocking probability of dynamic lightpath establishment in wavelength-routed networks. By using the destination-initiated reservation (DIR) method as a case study, we analyze traffic blocking occurring due to insufficient network capacity as well as traffic blocking caused by outdated information. Simulation results show the proposed models to be highly accurate.

This paper addresses the call admission control problem for the multimedia services that characterize the third generation of wireless networks. In the proposed model each cell has to serve a variety of classes of requests that differ in their traffic parameters, bandwidth requirements and in the priorities while ensuring proper quality of service levels to all of them. A semi Markov process is used to model multi-class multimedia systems with heterogeneous traffic behavior, allowing for call transitions among classes. It is shown that the derived optimal policy establishes state-related threshold values for the admission policy of handoff and new calls in the different classes, while minimizing the blocking probabilities of all the classes and prioritizing the handoff requests. It is proven that in restrictive cases the optimal policy has the shape of a multi-threshold priority policy, while in general situations the optimal policy has a more complex shape.

The paper presents a formal study on optimal bandwidth partitioning for multi-rate video broadcasting in a broadband wireless network. The formulation is generic in that it considers both inter-session and intra-session bandwidth partitions for layering as well as stream replication based broadcasting. It also takes into account the most fundamental issues associated with video transmission, including encoding overhead, non-linear relationship between the receiver perceived video quality and the delivered bandwidth, as well as intra-session and inter-session fairness. Specifically, we consider the bandwidth-constrained case with channelized allocation. We show that there exist polynomial time algorithms for both inter-session and intra-session partitioning problems.

One of the key performance measures in wireless cellular systems is the handoff dropping probability. The paper studies the handoff performance for an integrated voice/data wireless cellular system. Specifically, we propose a new handoff control policy, called dual trunk reservation with queuing (DTR-Q). It uses two thresholds, one to reserve bandwidth for voice handoff, and the other for managing the data traffic. By taking advantage of the adaptiveness of data traffic, it uses a single queue to buffer the data request further in case the requested bandwidth is not available. The unique features of the proposed DTR-Q scheme are: 1) it can provide the necessary service guarantee and service differentiation for voice and data traffic; 2) it adopts a complete sharing approach that can maximize the channel utilization. We propose an analytical model to calculate the key performance measures, and thoroughly investigate system performances under a variety of system parameters.

We present analytical results for handoff probability for wireless networks under assumption that the call holding time and the cell residence time are all generally distributed. Easily computable formulas can be obtained for cases when the call holding time and cell residence time have rational Laplace transforms.

This paper presents a new adaptive bandwidth allocation scheme to prevent handoff failure in wireless cellular networks, known as the measurement-based preassignment (MPr) technique. This technique is particularly useful in micro/pico cellular networks which offers quality-of-service (QoS) guarantee against call dropping. The proposed MPr scheme distinguishes itself from the well-known guarded channel (GC) based schemes in that it allows the handoff calls to utilize a prereserved channel pool before competing for the shared channels with new call arrivals. The key advantage of the proposed MPr scheme is that it enables easy derivation of the number of channels that needs to be reserved for handoff based on a predetermined handoff dropping probability, without the need for solving the often complex Markov chain required in GC schemes, thus, making the proposed MPr scheme simple and efficient for implementation. This is essential in handling multiple traffic types with potentially different QoS requirements. In addition, the MPr scheme is adaptive in that it can dynamically adjust the number of reserved channels for the handoff according to the periodical measurement of the traffic status within a local cell, thus completely eliminating the signaling overhead for status information exchange among cells mandated in most existing channel allocation schemes. Numerical results and comparisons are given to illustrate the tradeoff.

Bluetooth is an open specification for short-range wireless communication and networking, mainly intended to be a cable replacement between portable and/or fixed electronic devices. The specification also defines techniques for interconnecting large number of nodes in scatternets, thus enabling the establishment of a mobile ad hoc network (MANET). While several solutions and commercial products have been introduced for one-hop Bluetooth communication, the problem of scatternet formation has not yet been dealt with. This problem concerns the assignment of the roles of master and slave to each node so that the resulting MANET is connected. We introduce two novel protocols for forming connected scatternets. In both cases, the resulting topology is termed a bluetree. In our bluetrees the number of roles each node can assume are limited to two or three (depending on the protocol), thus imposing low slave management overhead. The effectiveness of both protocols in forming MANETs is demonstrated through extensive simulations.

Abstract This paper introduces a general decision model, in the shape of a Markov Decision Process, as an instrument to analytically compare the behavior of call admission control policies. This approach allows the study of a wide class of policies, including well‐known pure stationary as well as randomized policies, in a way that explicitly incorporates the dependency between the hand‐off rate and the system state, assuming that the hand‐off rate arriving to a cell is proportional to the occupancy level of the adjacent cells. In particular, some well‐known non‐preemptive prioritization schemes are analyzed, including the Cutoff Priority Policy (CPP), which consists of reserving a number of channels for the high priority requests stream. Using our analytical approach, we prove the optimality of CPP within the analyzed class. Copyright © 2001 John Wiley & Sons, Ltd.

Abstract This paper describes mobility management for the third‐generation mobile networks. We focus on the evolution from General Packet Radio Service (GPRS) to Universal Mobile Telecommunication System (UMTS). In this evolution, the radio access network UTRAN has been introduced, and radio‐related management is moved from the core network to UTRAN. We elaborate on how this architecture change affects the mobility management functionality, including the attach and detach procedures, location update, serving radio network controller relocation and intersystem change between GPRS and UMTS. Copyright © 2001 John Wiley & Sons, Ltd.

This article provides an overview of General Packet Radio Service (GPRS). GPRS reuses the existing GSM infrastructure to provide end-to-end packet-switched services. Benefits of GPRS include efficient radio usage, fast set-up/access time and high bandwidth with multiple timeslots. GPRS also provides a smooth path for GSM evolution to the third generation mobile network. Specifically, a third generation network can continue to utilize the GPRS IP backbone network. We describe the GPRS network nodes and the interfaces among these nodes. Deployment issues for GPRS are also elaborated. Copyright © 2001 John Wiley & Sons, Ltd.

This paper presents ABROAD, an adaptive medium access control (MAC) protocol for reliable broadcast packet transmission in wireless networks. ABROAD incorporates a collision-avoidance handshake within each slot of a synchronous transmission schedule, allowing nodes to reclaim and/or reuse idle slots while maintaining bounded access delay. Thus, ABROAD provides worst-case performance guarantees while remaining adaptive to local changes in traffic load and node connectivity. We analyze the optimal worst-case performance of ABROAD, and show that there is a strict increase in the number of broadcast packets per second over a pure time division multiple access (TDMA) protocol. Extensive simulation confirms our analysis, and also demonstrates that ABROAD outperforms broadcast protocols based on reliable unicast packet delivery schemes, such as the IEEE 802.11 MAC standard.

In wireless mobile networks, particularly in PCS networks, new calls to a portable may be lost due to the incorrect location information in the mobility database, which leads to a database failure. Such database failure can be recovered either through the portable's registration initiation, the deregistration when it crosses the location area boundary or the active location update. In this paper, we analyze the active location update scheme under several different mobile traffic distributions for failure restoration. We present analytical results for cost analysis. We find that under certain conditions there exists an optimal choice of location update period to minimize the total cost which represents the tradeoff between the location update and call loss. Our results provide a general framework for evaluating active database failure recovery schemes in wireless networks.

This paper describes an integrated framework for selecting optimal call mixes (in a multimedia traffic scenario) by bandwidth degradation in a wireless cellular network, to maximize the revenue earned by the service provider. Each admitted call in our framework generates a revenue for the service provider based on the parameters of the call. The sum of the revenues generated by all admitted calls at a time is considered as the total revenue earned in a cell. By degradation, we mean that: (1) some channels can be taken away from ongoing calls that are assigned multiple channels and/or (2) newly admitted calls that require multiple channels get fewer than what they requested. To avoid removing more channels from calls than they could tolerate, we incorporate a new call attribute: the degradation tolerance, i.e, the number of channels a call can be degraded without sacrificing the acceptable level of quality. We also consider priorities over calls to influence the admission-degradation decision. Our analytical framework includes both static and dynamic scenarios. The dynamic case is enhanced with the ability to select the optimal call mix using incoming and departing handoffs, new calls, and call terminations in a recursive way. We also discuss how to accommodate non-real-time calls into our system. To evaluate the performance of the proposed scheme a discrete event simulation tool, that accommodates our dynamic framework built on a customized simulated annealing optimization function, has been developed. Simulation results demonstrate that not only does the proposed integrated admission-degradation framework maximize the total revenue earned in cells, but also handoff and new call blocking probabilities are reduced.

This paper studies call admission policies for access control in cellular networks by means of a Markov decision process (MDP). This approach allows us to study a wide class of policies, including well known pure stationary as well as randomized policies, in a way that explicitly incorporates the dependency between the hand-off rate and the system state, assuming that the hand-off rate arriving to a cell is proportional to the occupancy level of the adjacent cells. In particular, we propose and analyze a nonpreemptive prioritization scheme, we term the cutoff priority policy. This policy consists of reserving a number of channels for the high priority requests stream. Using our analytical approach, we prove the proposed scheme to be optimal within the analyzed class.

This paper introduces OLAM, a novel on-demand location aware multicast protocol for ad hoc networks. The protocol assumes that, through the use of positioning system devices, such as Global Positioning System (GPS) devices, each node knows its own position and the current (global) time, and it is able to efficiently distribute these measures, including its current transmission radius, to all other nodes. As the measures are received, each node updates its local snapshot of the complete network topology. When a packet is to be multicast to a group, a heuristic is then used to locally compute the Steiner (i.e., multicast) tree for the addressed multicast group based on the snapshot rather than maintaining the tree in a distributed manner. The resulting Steiner tree is then optimally encoded by using its unique Prufer sequence and included along with the packet, extending the length of the header by no more than the header of packets in source routing (unicast) techniques. All local computations are executed using efficient (i.e., polynomial time) algorithms. The protocol has been simulated in ad hoc networks with 30 and 60 nodes and with different multicast group sizes. We show that OLAM delivers packets to all the nodes in a destination group in more than 85% of the cases. Furthermore, compared to flooding, OLAM achieves improvements of up to 50% on multicast completion delay.

One of the approaches currently pursued to provide an optical network architecture for supporting the next generation Internet consists of transmitting the Internet protocol (IP) packets directly over the wavelength division multiplexing (WDM) layer. The challenge of this approach is to make the optical bandwidth directly accessible to IP with the statistical multiplexing necessary to support the bursty nature of IP traffic in a cost effective way. This paper proposes a WDM ring architecture with a multitoken interarrival time (MTIT) access protocol designed to achieve a bandwidth efficient multiplexing technique in local and metropolitan network applications. The MTIT protocol achieves efficient multiplexing of all-optically transmitted packets by means of multiple control tokens whose rotation speed along the ring is regulated via the "token interarrival time," as opposed to the "token rotation time" adopted in existing standards. The proposed WDM architecture and protocol provide a unique medium access control that allows one to maintain the channel access delay at a node within a limited range of values, possibly reaching average values that are below the roundtrip propagation time of the ring. In the paper it is shown that the MTIT protocol efficiency grows with the number of wavelengths-in agreement with today's WDM technology trends-and it is not a function of the packet size-a mandatory feature to support IP traffic.

This paper proposes an efficient contention resolution switching architecture which can serve as the basis for all-optical switching nodes. The presented solution builds on fiber delay lines used as temporary optical storage and 2/spl times/2 space photonic switches, a solution principle also known as Quadro or switched delay lines (SDLs). The efficiency of SDLs is fundamentally linked to its storage capacity, i.e., the length of the fiber delay lines, while its cost depends on the number of 2/spl times/2 photonic switches, i.e., the number of stages in the switch. This work presents a solution that makes use of multibuffer fiber delay lines which allow multiple packets to be concurrently stored (propagated) on each line. With a novel switch control, it is shown that this solution increases the total storage capacity and significantly improves switch and network performance, without increasing the number of the 2/spl times/2 switches in the system, i.e., its cost.

When the location information for a mobile user in the Home Location Register (HLR) is corrupted or obsolete, the new arriving calls to the user may be lost. In order to minimize the effect of such HLR mobility database failure, a location update scheme called period location updating is proposed, and the cost analysis is performed. Analytical results for the failure recovery time distribution and the average number of call losses, which are crucial for cost analysis, are presented. The optimal location update period is given analytically as a function of other traffic parameters. This optimal choice of location update period lays the foundation for the adaptive adjustment of the location update period in failure restoration for PCS networks.

One of the concepts currently pursued to provide the ideal network architecture for supporting the next generation Internet consists of transmitting the Internet protocol (IP) packets directly over the wavelength division multiplexing (WDM) layer of extant optical networks. The challenge of this concept is to make the optical bandwidth directly accessible to IP with the statistical multiplexing necessary to support the bursty nature of IP traffic in a cost effective way. This paper proposes the multi-token inter-arrival time (MTIT) access protocol designed to achieve a bandwidth efficient multiplexing technique in WDM ring networks. The network throughput is maximized without violating the desired access delay requirement by controlling the "token inter-arrival time" as opposed to controlling the "token rotation time" as proposed in existing standards, e.g., FDDI. It is shown that the MTIT protocol efficiency grows with the number of wavelengths-in full agreement with the WDM technology trend-and does not depend on the packet length-a feature ideal for IP implementation. In addition, the protocol provides a unique token control technique that allows to maintain the channel access delay at a node bounded even within the round trip propagation time of a ring.

A method is presented to find routes for UBR (unspecified bit rate) circuits in ATM networks to make UBR traffic well-balanced. It selects an optimal path for each UBR circuit, while avoiding the potential problem of selecting the same optimal path or subpath repeatedly for different circuits. This is achieved by choosing an optimal path uniformly at random from the set of all optimal paths, according to any user-selected metric. Since the set of potential paths is exponentially large and has a complex structure, a new tool is needed to select a path uniformly at random from the set of all optimal paths efficiently. We propose a solution whose complexity is only that of shortest path selection, and we prove that it selects any optimal path with equal probability, thus providing good load balancing among candidate routes. Given the efficiency of the proposed solution and the above properties of the resulting paths selection, we believe the solution can be a practical approach to load balancing of UBR circuits in ATM networks.

In order to capture the essence of PCS network behaviour, a good mobility model is necessary. This model must be good enough to fit field data and make the resulting queueing model still tractable. We propose a new mobility model, called the hyper-Erlang distribution model, which satisfies the above two requirements. We use this model to characterize the cell residence time and obtain analytical results for the channel holding time, the distribution of which is of primary importance in teletraffic analysis of PCS networks. These results can be used to facilitate the computation together with the use of the partial fractional expansion technique. It is expected that the mobility model and the analytical results for channel holding time presented in this paper will play an significant role for field data processing in PCS network design and performance evaluation.

An algorithm is presented for designing the logical topology of the virtual path (VP) network, an important task in ATM network design. We prove that the algorithm provides a VP network topology that is asymptotically optimal with respect to both connectivity and the diameter of the network. These optimality properties are combined with algorithmic simplicity and polynomial running time, thus overcoming the notorious "optimality vs. scalability" dilemma. This result is made possible by applying the theory of random graphs to this type of networks. This theory has the methodological advantage of increased accuracy with growing network size, thus turning the "curse of dimensionality" into a blessing. Therefore, the paper exemplifies that the theory of random graphs, beyond supporting analysis purposes, may serve as a useful tool in the design of algorithms that overcome the "scalability bottleneck", a problem that prevents current approaches from finding near-optimal solutions as today's networks grow in size and complexity.

This paper proposes a new routing protocol for ad hoc networks built around the source routing technique combined with the location (e.g., GPS coordinates) of nodes obtained by an energy and distance smart dissemination mechanism. The key new observation used is that the location information provides each node with a snapshot of the topology of the complete network from which a source route may be computed locally rather than through route discovery. The resulting protocol has reduced delay, and is more bandwidth and energy efficient, than both traditional (proactive and reactive) ad hoc routing protocols, as well as location based routing protocols.

Recent PCS teletraffic research and field data have shown that the channel holding time (CHT) distribution is not exponential and that the cell traffic (i.e., the merged traffic from new calls and hand-off calls) is not Poissonian. It was also observed that in operational PCS systems the call blocking probability tends to be different than that given by the Erlang-B formula. In this paper, we study the effect of variance of the cell residence time (CRT) on the call blocking performance and investigate the sensitivity of the call blocking probability to the distribution of the CRT. We show that the blocking probability of new call and handoff call are different, they are affected by the CRT distribution in different way. Besides the variance of CRT, the user mobility also has a contribution to influence the call blocking performance.

Wireless mobile networks require efficient bandwidth utilization and reliable link connectivity regardless of terminal mobility. Solutions proposed for bandwidth and location management tend to impose two conflicting requirements on network design, namely (1) maintain maximum resource (bandwidth) utilization and (2) reserve enough bandwidth so that the maximum rate of forced call termination rate due to bandwidth unavailability is kept below an acceptable level. To resolve this conflict, we proposed a predictive guard bandwidth scheme that adapts the resources' access priority via guard bandwidth adjustments, in response to changes in instantaneous traffic load, predicted from terminal mobility tracking. A mathematical formulation has been derived to predict a mobile user's movement behavior in terms of boundary crossing probability and cell residence probability, based on which active mobile probability is obtained to estimate instantaneous traffic load in terms of handoff call arrival rate and call departure rate. For given traffic situation, a dynamic programming approach has been further developed to determine the necessary amount of guard bandwidth to achieve the objective of congestion-related performance. The effectiveness of the proposed predictive guard bandwidth scheme is demonstrated through simulation studies in comparison with fixed guard bandwidth scheme. Simulation results indicate that the proposed scheme is insensitive to traffic load fluctuations caused by changes of user movement behavior, and that it maintains reliable connectivity without sacrificing bandwidth utilization efficiency.

Many aspects of handoff traffic analysis for third generation wireless communications networks are still not fully understood. In this paper, we study the handoff traffic distribution aspect in blocking and nonblocking environments under a general cell residence time (CRT). We use a gamma distribution for CRT to show that CRT affects the handoff traffic in both blocking and nonblocking environments. When the variance of CRT is large, the handoff traffic cannot be modeled by a Poisson process. In a blocking environment, the handoff arrival rate is affected by the CRT distribution, the lower the variance, the higher the handoff arrival rate. However, in a nonblocking environment, the handoff arrival rate is only affected by the mean value of CRT. We show that besides the variance of CRT, the new call traffic load, and users' mobility, all affect the handoff traffic.

Channel holding time is of primary importance in teletraffic analysis of PCS networks. This quantity depends on user's mobility which can be characterized by the cell residence time. We show that when the cell residence time is not exponentially distributed, the channel holding time is not exponentially distributed either, a fact also confirmed by available field data. In order to capture the essence of PCS network behaviour, including the characterization of channel holding time, a correct mobility model is therefore necessary. The new model must be good enough to fit field data, while at the same time resulting in a tractable queueing system. We propose a new mobility model, called the hyper-Erlang distribution model, which is consistent with these requirements. Under the new realistic operational assumption of this model, in which the cell residence time is generally distributed, we derive analytical results for the channel holding time distribution, which are readily applicable to the hyper-Erlang distribution models. Using the derived analytical results we demonstrate how the distribution of the cell residence time affects the channel holding time distribution. The results presented in this paper can provide guidelines for field data processing in PCS network design and performance evaluation.

Broadcast (distributing a message from a source node to all other nodes) is a fundamental problem in distributed computing. Several solutions for solving this problem in mobile wireless networks are available, in which mobility is dealt with either by the use of randomized retransmissions or, in the case of deterministic delivery protocols, by using conflict-free transmission schedules. Randomized solutions can be used only when unbounded delays can be tolerated. Deterministic conflict-free solutions require schedule recomputation when topology changes, thus becoming unstable when the topology rate of change exceeds the schedule recomputation rate. The deterministic broadcast protocols we introduce in this paper overcome the above limitations by using a novel mobility-transparent schedule, thus providing a delivery (time) guarantee without the need to recompute the schedules when topology changes. We show that the proposed protocol is simple and easy to implement, and that it is optimal in networks in which assumptions on the maximum number of the neighbors of a node can be made.

This paper introduces an approach to solving the fundamental scalability problem of all-optical packet switching wavelength-division multiplexing (WDM) access networks. Current optical networks cannot be scaled by simply adding nodes to existing systems due to the accumulation of insertion losses and/or the limited number of wavelengths. Scalability through bridging requires, on the other hand, the capability to switch packets among adjacent subnetworks on a wavelength basis. Such a solution is, however, not possible due to the unavailability of fast-switching wavelength sensitive devices. In this paper, we propose a scalable WDM access network architecture based on a recently proposed optical switching approach, termed photonic slot routing. According to this approach, entire slots, each carrying multiple packets (one on each wavelength) are "transparently" routed through the network as single units so that wavelength sensitive data flows can be handled using fast-switching wavelength nonsensitive devices based on proven technologies. The paper shows that the photonic slot routing technique can be successfully used to achieve statistical multiplexing of the optical bandwidth in the access network, thus providing a cost-effective solution to today's increasing bandwidth demand for data transmissions.

A myriad of applications are emerging, in which energy conservation is a critical system parameter for communications. Radio frequency identification device (RFID) networks, smart cards, and even mobile computing devices, in general, need to conserve energy. In RFID systems, nodes are small battery-operated inexpensive devices with radio receiving/transmitting and processing capabilities, integrated into the size of an ID card or smaller. These identification devices are designed for extremely low-cost large-scale applications, such that the replacement of batteries is not feasible. This imposes a critical energy constraint on the communications (access) protocols used in these systems, so that the total time a node needs to be active for transmitting or receiving information should be minimized. Among existing protocols, classical random access protocols are not energy conserving, while deterministic protocols lead to unacceptable delays. This paper deals with designing communications protocols with energy constraint, in which the number of time slots in which tags need to be in the active state is minimized, while the access delay meets the applications constraints. We propose three classes of protocols which combine the fairness of random access protocols with low energy requirements.

Article Free Access Share on A distance routing effect algorithm for mobility (DREAM) Authors: Stefano Basagni Erik Jonsson School of Engineering and Computer Science, The University of Texas at Dallas Erik Jonsson School of Engineering and Computer Science, The University of Texas at DallasView Profile , Imrich Chlamtac Erik Jonsson School of Engineering and Computer Science, The University of Texas at Dallas Erik Jonsson School of Engineering and Computer Science, The University of Texas at DallasView Profile , Violet R. Syrotiuk Erik Jonsson School of Engineering and Computer Science, The University of Texas at Dallas Erik Jonsson School of Engineering and Computer Science, The University of Texas at DallasView Profile , Barry A. Woodward Erik Jonsson School of Engineering and Computer Science, The University of Texas at Dallas Erik Jonsson School of Engineering and Computer Science, The University of Texas at DallasView Profile Authors Info & Claims MobiCom '98: Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networkingOctober 1998 Pages 76–84https://doi.org/10.1145/288235.288254Published:25 October 1998Publication History 704citation5,003DownloadsMetricsTotal Citations704Total Downloads5,003Last 12 Months353Last 6 weeks41 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Mobile communications implies reliance on a self-contained, portable power source, error-prone fading radio channels and subsequent need for acknowledgments. We propose two energy-conserving variants of the selective repeat ARQ protocol, which reduce the number of acknowledgments sent by the mobile node. The protocols are compared to previously described energy-conserving go-back-N ARQ protocols as well as classical approaches and shown to maintain favorable delay and throughput performances.

This paper presents a formula for the computation of handoff rate in PCS networks under generally distributed call holding times and generally distributed cell residence times. This formula can be used to study the handoff traffic rate. It shows that applying the exponential distribution underestimate the handoff traffic rate, hence the computed handoff call blocking probability will be lower than the actual handoff call blocking probability. This suggests the necessity of the sensitivity study with respect to the variance of channel occupancy time in the PCS network analysis and design.

Wireless ATM networks require efficient mobility management to cope with frequent mobile handoff and rerouting of connections. Although much attention has been given in the literature to network architecture design to support wide-area mobility in public ATM networks, little has been done to the important issue of user mobility estimation and prediction to improve the connection reliability and bandwidth efficiency of the underlying system architecture. This paper treats the problem by developing a hierarchical user mobility model that closely represents the movement behavior of a mobile user, and that, when used with appropriate pattern matching and Kalman filtering techniques, yields an accurate location prediction algorithm, HLP, or hierarchical location prediction, which provides necessary information for advance resource reservation and advance optimal route establishment in wireless ATM networks.

This paper presents a study of channel occupancy times and handoff rate for mobile computing in MC (Mobile Computing) and PCS (Personal Communications Services) networks, using general operational assumptions. It is shown that, for exponentially distributed call holding times, a distribution more appropriate for conventional voice telephony, the channel occupancy times are exponentially distributed if and only if the cell residence times are exponentially distributed. It is further shown that the merged traffic from new calls and handoff calls is Poisson if and only if the cell residence times are exponentially distributed, too. When cell residence times follow a general distribution, a more appropriate way to model mobile computing sessions, new formulae for channel occupancy time distributions are obtained. Moreover, when the call holding times and the cell residence times have general (nonlattice) distributions, general formulae for computing the handoff rate during a call connection and handoff call arrival rate to a cell are given. Our analysis illustrates why the exponential assumption for call holding time results in the underestimation of handoff rate, which then leads to the actual blocking probabilities being higher than the blocking probabilities for MC/PCS networks designed using the exponential distribution approximation for call holding time. The analytical results presented in this paper can be expected to play a significant role in teletraffic analysis and system design for MC/PCS networks.

We analyze the worst-case behavior of general connection-oriented networks, with first-in-first-out (FIFO) queueing policy, forwarding packets along an arbitrary system of routes. A worst-case bound is proven for the end-to-end queueing delay and buffer size needed to guarantee loss-free packet delivery, given that sources satisfy a given source rate condition. The results are based on a novel deterministic approach and help in reconciling the discrepancy between the unstable worst-case behavior of FIFO-based networks and their good practical performance.

The task of supporting integrated multi-rate multimedia traffic in a bandwidth poor wireless environment poses a unique and challenging problem for network managers. In this paper we propose a novel bandwidth allocation strategy which partitions the available bandwidth amongst the different traffic classes in a manner that ensures quality of service (QoS) guarantees for digital video while minimizing the maximum blocking probability for voice and data connections. At the connection level, optimum utilization of the reserved bandwidth is achieved through intra-frame statistical multiplexing, while at the system-level, the delicate task of partitioning the bandwidth is accomplished by developing an efficient algorithm which uses traffic parameters consisting only of aggregate traffic load and the total available bandwidth. The algorithm built on non-trivial mathematical results, is simple, robust, and well suited for practical implementations.

This paper deals with the design of a communications protocol which operates under an energy constraint, in which the fraction of timeslots in which tags need to be in the active (awake) state is minimized, and the access delay meets the applications constraints. We present a new approach to this problem, a pseudo-random protocol, which combines the fairness from random access protocols with the low energy requirements of classical TDMA. Considering an analytical model as well as simulations of the system behavior for the cases of uniformly and non-uniformly distributed traffic destinations, we show that in addition to fairness, and low energy requirements the proposed protocol provides low access delays.

Photonic slot routing (PSR) is a promising approach to solving the fundamental scalability problem of all-optical packet switched WDM networks. In this approach adjacent subnetworks can exchange wavelength sensitive traffic through bridges using wavelength non-selective devices which can be constructed using proven technologies. With photonic slot routing, packets sharing a common subnetwork destination are aggregated to form a photonic slot which is individually routed in order to reach the destination subnetwork. Photonic slots from different subnetworks can originate contentions at the bridge, leading to potential penalties of slot loss and retransmission. This paper shows how slot contention penalties can be reduced through the use of switched delay lines (SDL) at the bridges. The combination of these two innovative techniques, the photonic slot routing and the switched delay lines, leads to a unique solution that is shown to nearly achieve throughput and delay performance obtainable in absence of slot contentions.

Previous performance studies of PCS channel allocation assumed that call holding times have an exponential distribution. The exponential call holding time assumption is justified for existing cellular systems, where wireless calls are charged based on the length of the call holding time. Future PCS systems may exercise flat rate billing, and consequently a more general distribution is desirable to model the call holding times. This paper models the call holding times by the Erlang distribution (a generalization of the exponential distribution) to investigate the effect of the variance of the call holding times on the call completion probability. Our analysis indicates that the call completion probability decreases as the variance of the call holding times decreases. This effect becomes more pronounced as the variance of the cell residence times decreases.

It is well known that, due to the mobility of a portable and limited channel availability, calls of portables may not be completed due to being blocked or terminated during the call initiation or the handover process. The characteristics of the call-completion and call-holding times for both a complete call and an incomplete call are of critical importance for establishing the actual billing process in the PCS network. We derive the call-completion probability (hence, call-dropping probability) and the effective call-holding time distributions for complete/incomplete calls with a general cell-residence time and a general call-holding time are analyzed, and general computable formulas are obtained. We show that when call-holding times are Erlang distributed, easy-to-compute formulas for the probability of a call completion and the expected effective call-holding times for both a complete call and an incomplete call can be derived.

—————————— ✦ —————————— One of the most challenging and interesting recent trends in the computer and telecommunications industries is the integration of mobile communications and computing. The resulting distributed network, referred to as a mobile computing system, is in more that one way fundamentally different from conventional wired computer networks. Wireless connectivity enhances the functionality of computing equipment by freeing communication from the location constraints of the wireline infrastructure. By changing this basic characteristic, mobile computing systems operate on a set of assumptions made by traditional computing systems, requiring researchers and users to redefine their model of networked computing. The successful use of mobile computing faces several challenges, among them:

This paper introduces a novel technique called protocol threading, yielding a deterministic protocol that gives a guaranteed upper bound on the transmission delay of each packet at every node in a multihop mobile network. By eliminating the maximum degree constraint, the new method improves upon existing time-spread multiple-access (TSMA)-type protocols while preserving the advantages of the deterministic operation and topology transparency. We introduce the protocol threading solution, derive the maximum delay bound in a mobile topology, and analyze the performance of the protocol.

In a personal communication service (PCS) network, the call completion probability and the effective call holding times for both complete and incomplete calls are central parameters in the network cost/performance evaluation. These quantities will depend on the distributions of call holding times and cell residence times. The classical assumptions made in the past that call holding times and cell residence times are exponentially distributed are not appropriate for the emerging PCS networks. This paper presents some systematic results on the probability of call completion and the effective call holding time distributions for complete and incomplete calls with general cell residence times and call holding times distributed with various distributions such as gamma, erlang, hyperexponential, hyper-erlang, and other staged distributions. These results provide a set of alternatives for PCS network modeling, which can be chosen to accommodate the measured data from PCS field trials. The application of these results in billing rate planning is also discussed.

Resource contention in packet switched all-optical networks is being addressed in this paper through the combined use of fiber delay lines and 2/spl times/2 space photonic switches. With this basic approach, also known as Quadro or switched fiber delay lines (SDL), the solution efficiency is linked to its storage capacity, determined by the combined length of the fiber delay lines. In the past, this capacity was given by the number of 2/spl times/2 photonic switches used, i.e., the number of stages in the receiver, which limited the solution by cost, mainly determined by the switch component, and by the signal power loss and crosstalk introduced by each switch. This work presents and analyzes the use of "multibuffer" fiber delay lines, in Quadro, so termed since in it multiple packets are allowed to be concurrently stored (propagated) on each delay line. In this way the total storage capacity is increased, while the proposed design utilizing novel switch control is shown to significantly improve receiver and network performance, without increasing the number of the 6/spl times/2 space photonic switches in the system, i.e., its cost.

This paper addresses two important PCS cost and performance issues: (1) are blocking probabilities (for new call blocking, forced termination or call completion) appropriate for PCS network performance measurement? (2) Should PCS service providers offer discounts to phone calls that are force terminated? In order to do that we derive the effective call holding time distributions for complete/incomplete calls by using an analytic model. We assume that the cell residence times have a general distribution so that the measured data from the field trials, after a second order approximation, can be used to drive our model. Our study on the effective call holding time distributions indicates that (1) blocking probabilities do not provide sufficient information to evaluate the performance of a PCS network, and that output measures, such as expected effective call holding times for complete/incomplete calls, are desirable; (2) for a PCS network with moderate user mobility, the service provider can offer substantial discounts to incomplete calls (to increase the user satisfaction) without significantly reducing the profit margin. A quantitative analysis is also provided that can be used to determine the discount factor.

We address the problem of efficient circuit switching in wide area optical networks. The solution provided is based on finding optimal routes for lightpaths and the new concept of semilightpaths. A lightpath is a fully optical transmission path, while a semilightpath is a transmission path constructed by chaining together several lightpaths, using wavelength conversion at their junctions. A fast and practical algorithm is presented to optimally route lightpaths and semilightpaths taking into account both the cost of using the wavelengths on links and the cost of wavelength conversion. We prove that the running time of the algorithm is the best possible in the wide class of algorithms allowing linear algebraic operations on weights. This class encompasses all known related practical methods. Additionally, our method works for any physical realization of wavelength conversion, independently whether it is done via optoelectronic conversion or in a fully optical way.

The implementation of optical packet-switched networks requires that the problems of resource contention, signalling and local and global synchronization be resolved. A possible optical solution to resource contention is based on the use of switching matrices suitably connected with optical delay lines. Signalling could be dealt with using subcarrier multiplexing of packet headers. Synchronization could take advantage of clock tone multiplexing techniques, digital processing for ultra-fast clock recovery, and new distributed techniques for global packet-slot alignment. To explore the practical feasibility and effectiveness of these key techniques, a consortium was formed among the University of Massachusetts, Stanford University, and GTE Laboratories. The consortium, funded by ARPA, has three main goals: investigating networking issues involved in optical contention resolution (University of Massachusetts), constructing an experimental contention-resolution optical (CRO) device (GTE Laboratories), and building a packet-switched optical network prototype employing a CRO and novel signaling/synchronization techniques (Stanford University). This paper describes the details of the project and provides an overview of the main results obtained so far.

The requirement to connect high-performance components of supercomputer systems has caused an increasing demand for connection-oriented, high-speed communication in a peer-to-peer environment. The importance of this type of communication is underscored by the advent of the high-performance parallel interface (HIPPI) standard, designed to support the commercial development of interconnection systems for this environment. For such interconnection systems, we present a connection management algorithm that supports priorities to provide preferential access for important classes of traffic, and that assures equitable access for all connections within the same priority class. At the same time, the algorithm utilizes the connection resources efficiently and assures low overhead at the nodes. We demonstrate the algorithm's applicability by outlining a centralized as well as a distributed implementation in an HIPPI-based interconnection system. Furthermore, we introduce an analytic priority model that can be used to evaluate an interconnection system's performance under the algorithm. Using this model, we analyze the efficacy of the nonpreemptive priority discipline and show the load/throughput behavior of a typical system.

A topology transparent protocol for link activation in mobile CDMA networks is presented. The protocol resolves primary and secondary conflicts, and can easily be adapted to TDMA link activation, as well. The proposed protocol guarantees that each link will be successfully activated at least once in a frame without the need to adjust transmission schedules in mobile environments. Compared to other protocols with guaranteed delivery, the overhead due to the recomputation of transmission schedules is eliminated and, accordingly, transmissions need not be suspended for schedule reorganization. Furthermore, contrary to previously known protocols that adapt to mobility by schedule recomputation, the proposed solution is not subject to a potential catastrophic failure when the rate of topology changes exceeds the rate at which schedules can be readjusted. We prove the correctness and evaluate the efficiency of the new protocol by analytical methods.>

A multiple access packet communication model is analyzed in which the users can receive packets on more than one common channel. For this type of system, a new channel access protocol is presented. The authors prove that under heavy homogeneous load the protocol guarantees the maximum achievable throughput among all possible protocols. The general model can be applied to different systems, according to various realizations of the logical channels. For example, in packet radio networks the channels can be realized by different carrier frequencies (FDMA) or by different codes (CDMA). The simplicity and optimality of the protocol make it attractive for practical applications.>

This paper proposes an original approach to controlling WDM Passive optical stars, termed queuing arrivals for delayed reception operation (Quadro). In WDM stars the fundamental problem of receiver conflicts leads to severe performance degradation. In current solutions conflicts are prevented by scheduling transmissions or resolved by retransmissions. Both approaches waste bandwidth and involve electronic processing and buffering. The proposed approach is conceptually different in introducing a local conflict resolution mechanism at each receiver incorporating delay lines. This solution brings optical star networks a step closer to an all-optical realization. In addition, it allows an almost total utilization of the channels, as obtainable until now only by TDM control. Contrary to TDM, however, the proposed solution does not suffer performance degradation under heterogeneous traffic conditions and increasing number of nodes. It is thus unique in offering the potential of an all-optical solution providing at the same time high throughput, low delay, small buffer requirements, and robustness under all traffic conditions.>

Transmissions scheduling is a key design problem in packet radio networks, relevant to TDMA and CDMA systems. A large number of topology-dependent scheduling algorithms are available, in which changes of topology inevitably require recomputation of transmission schedules. The need for constant adaptation of schedules to mobile topologies entails significant, sometime insurmountable, problems. These are the protocol overhead due to schedule recomputation, performance penalty due to suspension of transmissions during schedule reorganization, exchange of control message and new schedule broadcast. Furthermore, if topology changes faster than the rate at which new schedules can be recomputed and distributed, the network can suffer a catastrophic failure. The authors propose a robust scheduling protocol which is unique in providing a topology transparent solution to scheduled access in multi-hop mobile radio networks. The proposed solution adds the main advantages of random access protocols to scheduled access. Similarly to random access it is robust in the presence of mobile nodes. Unlike random access, however, it does not suffer from inherent instability, and performance deterioration due to packet collisions. Unlike current scheduled access protocols, the transmission schedules of the proposed solution are independent of topology changes, and channel access is inherently fair and traffic adaptive.>

The virtual path (VP) concept is known to be a powerful transport mechanism for ATM networks. This paper deals with the optimization of the virtual paths system from a bandwidth utilization perspective. While previous research on VP management has basically assumed that bandwidth in ATM networks is unlimited, emerging technologies and applications are changing this premise. In many networks, such as wireless, bandwidth is always at a premium. In wired networks, with increasing user access speeds, less than a dozen of broadband connections can saturate even a Gigabit link. We present an efficient algorithm that finds a system of VP routes for a given set of VP terminators and VP capacity demands. This solution is motivated by the need to minimize the load, or reduce congestion, generated by the VP's on individual links. A nontrivial performance guarantee is proven for the quality of the proposed solution and numerical results show that the proposed solution carries the potential for a near optimal allocation of VPs.>

An electronically controlled optical packet deflection switch that is based on space and time switching at intermediate nodes is described. The switch uses optical delay lines to store and switch packets in the optical domain so that optical bandwidth can be achieved across the network. The optical switch is controlled by an associated electronic mechanism that provides the necessary versatility and processing power. This approach combines the advantages of the optics and the electronics. The use and performance of the switch are demonstrated in the context of the Manhattan deflection network.>

The proposed HIPPI standard, a connection-oriented communication standard for very-high-speed interconnection systems connecting high-end computing systems, is discussed. The problems of managing connections and of configuring the interconnection system as either a single crossbar switch or as a clique of crossbar switches are considered. Three connection management policies are introduced: a centralized policy, a broadcast policy, and a distributed policy. To compare these policies for different system configurations, a set of models is introduced and used to evaluate a range of interconnection system configurations. The results of these models and the use of a cost measure make it possible to compare the cost and performance of different configurations and alternative connection management policies.>

The authors introduce a common modeling framework making it possible to develop tractable analytic models of optical star networks with reservation-based control. Reservation-based wavelength division multiplexing (WDM) optical star systems, and in particular the Quadro-based receiver design, have the performance advantages of high capacity, low response time, and adaptability to changing traffic flows. Using the modeling framework introduced, tractable approximate models of reservation-controlled WDM stars were derived. It was shown that the framework allows the representation of different control strategies, while resulting in only a very small error.>

An architectural approach that meets high bandwidth requirements by introducing a communication architecture based on lightpaths, optical transmission paths in the network, is introduced. Since lightpaths form the building block of the proposed architecture, its performance hinges on their efficient establishment and management. It is shown that although the problem of optimally establishing lightpaths is NP-complete, simple heuristics provide near optimal substitutes for several of the basic problems motivated by a lightpath-based architecture.>

The authors introduce analytic models for evaluating demand assignment protocols in realistic finite-buffer/finite-station network configurations. A solution for protocols with gated and nongated service disciplines that enables one to model demand assignment protocols as found, for example, in local and metropolitan area networks and in satellite communication systems is presented. A tractable approximate solution based on linear equations whose number is also linear is given. It is demonstrated that in addition to its computational efficiency, the presented approach does not incur a significant penalty in terms of accuracy.>

The problem addressed arose from the evolution of broadband applications and the design of networks that service them. An emerging approach optimizing the transport mechanism in these networks is based on the establishment of virtual topologies. The problem of determining the set of physical links for each virtual link routing is studied. These sets are chosen so as to minimize delay and maximum physical link congestion. A lower bound on the problem and a heuristic solution that achieves near-optimal results when compared with the bound are developed.>

An algorithm for efficient communication between neighbours in multihop radio networks is proposed. The algorithm guarantees a bound on the transmission efficiency in a radio channel for arbitrary topology. The algorithm can be embedded in protocols for solving basic network problems such as broadcast, multicast, leader election, or finding shortest paths. The problem of bounded-time broadcasting utilizing the proposed algorithm is addressed. A polynomial solution in which the process of spreading information over the network is viewed as the expansion of a wave caused by a point of disturbance is presented. The broadcast originates at a source node and is accomplished in repeated transmission periods, emulating a wave progressing away from the source. The algorithm is used to select a subset of potential transmitters in each period, so that a tightly bound proportion of potential receivers receive the transmission without collisions, guaranteeing a high level of spatial reuse in the broadcast process.>

The authors introduce two techniques for allocating and managing buffers in support of distributed system operation and evaluate the resulting system behavior. For this evaluation a methodology that permits the development of an analytic model is introduced. With the help of this model, it becomes possible to fine-tune the buffer allocation policies in realistic system configurations.>

An inherent problem of conventional point-to-point wide area network (WAN) architectures is that they cannot translate optical transmission bandwidth into comparable user-available throughput due to the limiting electronic processing speed of the switching nodes. A solution to wavelength division multiplexing (WDM)-based WAN networks that addresses this limitation is presented. The proposed lightpath architecture trades the ample bandwidth obtained by using multiple wavelengths for a reduction in the number of processing stages and a simplification of each switching stage, leading to substantially increased throughput. The principle of the lightpath architecture is the construction and use of a virtual topology network in the wavelength domain, embedded in the original network. A study is made of the embedding of virtual networks whose topologies are regular, using algorithms which provide bounds on the number of wavelengths, switch sizes, and average number of switching stages per packet transmission.>

An examination is made of the rationale behind the need for ever higher networking speeds, the technological developments that are making them possible on a commercial basis, the directions being taken in their development, and the issues surrounding their construction and use. Roadblocks to providing high-speed networks are discussed. The impact of standardization efforts on development efforts is considered, focusing on the HSC channels, the fiber distributed data interface (FDDI), and metropolitan- and wide-area networks (MANs and WANs). Possibilities for future technologies and architectures are described.>

An approach to communication architectures for high-speed networks which provides efficient, adaptive communication for any traffic distribution is presented. It is based on a concept of dynamic sharing of communication resources which is obtained from the following three-tier SWIFT architecture. At the physical layer the high-speed communication system is based on the use of several lower speed channels or frequencies. At the data link layer, driven by hardware simplicity considerations, the SWIFT architecture uses a fixed time-slotted allocation of subchannels, in which each node is required to transmit or receive over only a single, predetermined, subchannel at a time. To provide adaptive channel access control, while preserving the data link hardware simplicity, a network layer is added. This layer introduces multihop adaptive channel (frequency) routing on the inherently broadcast communication medium. The routing concept provides dynamic sharing of communication channels and buffers, leading to a fully distributed adaptive bandwidth control. An analytic model for analyzing the performance of the multilayered architecture is developed. It shows that for homogeneous or heterogeneous traffic requirements the approach provides throughput/delay performance superior to that found in existing communication systems.>

An approximate solution to slotted communication systems with finite population and finite buffer capacity is presented. The authors assume symmetric systems and present for the first time a linear solution involving linear equations whose number is a linear function of the total buffer capacity. They show that the model can be applied to existing multiaccess channel protocols in which a single successful transmission can be affected per slot. They further show that, unlike solutions based on existing nonlinear models, the proposed solution can be extended to communication systems in which several successful transmissions can take place in parallel, such as multibus communication networks and multichannel satellite systems.>

Emerging applications require a substantially higher bandwidth than the one offered by current networks. The authors propose a novel architectural approach that meets the high bandwidth requirements by introducing a communication architecture based on lightpaths, which are purely optical transmission paths in the network. Since lightpaths form the building block of the proposed architecture, its performance hinges on their efficient establishment and management. The authors shown that although the problem of optimally establishing lightpaths is NP-complete, distributed heuristics provide near-optimal solutions for several of the basic problems presented by the lightpath architecture.>

A path-oriented channel allocation management approach is introduced for the emerging high-bandwidth fiber optic star networks. In the proposed approach, the transmission channel of the source node and the reception channel of the destination node are synchronized at the central switching node, creating a virtual path for packet communication between any two nodes. The number of virtual paths that can be established simultaneously, i.e. the number of concurrent packet transmissions, equals the number of channels in the network. The proposed path allocation thus provides maximum spatial reuse not found in existing fiber optic star systems. The provision of a virtual path for every packet eliminates the need for buffering at the central node and provides bounded delays.>

The authors consider a path-oriented channel allocation management. As opposed to multiaccess protocols of existing fiber-optic systems, in the proposed approach the outgoing channel of the source node and the incoming channel of the destination node are allocated time-sequentially, creating a time-dependent virtual path for all pairs of users. Using the time-oriented path allocation, the need for packet buffering at the central node is eliminated multiple channels can be utilized simultaneously for different transmissions, and packet delays are bounded. The authors demonstrate that the same approach is feasible for efficient control of multibeam satellite systems. They introduce a tractable analytic model for the evaluation of communication systems based on this approach. The model is used to evaluate the proposed system performance under different switching functionalities of the central node. In addition to providing the throughput/delay characteristics of the system, the model shows a relation between the degree of star symmetry and the system performance, with the equidistant node arrangement yielding the optimal performance.>

Emerging high speed networks are using optical fibers employing time division synchronous communication. In these systems the use of optical switching is strongly advocated due to the bottleneck created by store and forward in electronic components. Switching solutions geared toward optical systems have been proposed so far only for packet switching networks.

This paper introduces analytic models for evaluating demand assignment protocols in realistic finite buffer/finite station network configurations. We present a solution for implicit and explicit token passing systems enabling us to model local area networks, such as Token Bus. We provide, for the first time, a tractable approximate solution by using an approach based on restricted occupancy urn models. The presented approximation involves the solving of linear equations whose number is linear and equal only to the number of buffers in the system. It is demonstrated that in addition to its simplicity, the presented approximation is also highly accurate.

A multibus train (ordered demand assignment) communication architecture, using the AMTRAC protocol (for efficient utilization of fiber-optic-based very-high-speed networks) is presented. Taking advantage of the emerging WDM (wavelength-division multiplexing) and FDM (frequency-division multiplexing) technologies, the proposed solution introduces a coordinated multichannel control combining the performance advantages of two known approaches for high-speed communication: multichannel and train protocols. As a result an AMTRAC-based high-speed network achieves channel utilization significantly higher than previous approaches. For a network consisting of N stations, with propagation delay to packet transmission time ratio given by a, the AMTRAC architecture reaches a capacity of 1/(1+a/N/sup 2/).>

Communication architectures for very-high-speed networks are dealt with. The use of high communication speed increases the ratio between the end-to-end propagation delay and the packet transmission time. This increase restricts the utilization of the high system bandwidth in broadcast channel-based systems, causing a rapid performance deterioration. A communication system architecture characterized by the use of several parallel channels and design of the nodes' channel interface is presented. The channel-division approach is introduced, showing that for a given system bandwidth the total system capacity will be increased by bandwidth division and parallel communication. An analytic model of this system is developed, from which the proposed system's performance is obtained and performance bounds determined for multichannel slotted finite systems. The results show that the architecture has a potential to improve significantly the system performance compared to conventional single-channel-based systems. Furthermore, for a given network configuration an optimal architecture can be found which simultaneously maximizes the system throughput and minimizes the average packet delay.>

In conventional high-speed systems, the high ratio between the end-to-end propagation delay and the message transmission time severely restricts the system performance. Thus, the increase in channel bandwidth may be accompanied by only a marginal increase in actual system capacity. A combined frequency-time division-based control of the high-speed channel that significantly reduces this problem is proposed. The design of protocols subject to the unique channel control penalties of the resulting multichannel system is considered. The allocation of channels on a demand assignment basis is hindered in the multichannel configuration by the time penalty involved in locating an idle channel and by practical limitations on the transmit/receive multichannels mode interface. A new class of fixed allocation protocols is introduced in which the channel access is obtained without the aforementioned penalties. The protocols build on the allocation of source and destination oriented transmission rights, taking into account the implementation aspects of multichannel networks. It is shown that this class of protocols covers the whole range of random-access to fixed-channel-access control policies. An analytic approach for a uniform analytic treatment is introduced, showing the potential for a significant improvement in the system capacity and the average message delay.>

A class of message-based or station-based priority protocols for demand-assignment-based local area networks (LANs), such as Token Bus, HYPERbus, LCN, etc., is defined. It is shown how existing priority protocols can be represented within this class and how they can be extended for a more efficient realization with regard to both delay and capacity of prioritized channel access in LANs. An analytic approach for analyzing multiple-access systems operating under prioritized demand assignment protocols is introduced. The approach permits the modeling of station-dependent and priority-dependent arrival rates and generally distributed transmission times. The introduced finite-population model is especially appropriate for prioritized systems where the number of users per priority class is typically small and users place different service demands on the system. For modeling systems with large populations of users, an approximate model, which is shown to be significantly more computationally efficient than the exact model without imposing additional modeling restrictions, is introduced.>

In high-speed communication networks, the ratio between the end-to-end propagation delay to packet transmission time is large, causing increased scheduling overhead in demand assignment protocols and increased collision probabilities in random access schemes. These lead to rapid degradation of the channel utilization in both channel access control approaches. In this paper, we present a "random token" oriented protocol where channel access is scheduled by random, implicit token passing leading to lower channel access control penalty. By optimally balancing the collision and scheduling penalties, the protocol allows the network to reach better performance than that obtained from random access schemes in networks with and without collision detection, without imposing additional system operational assumptions. Specifically, the random token protocol does not require knowledge of the number of stations, their identities, or synchronization in periods of silence. Therefore, the protocol is also suitable for high-speed networks with frequent reconfiguration and for mobile radio networks.

The HYPERchannel communication network based on one to four trunks, or channels is considered. We develop closed queueing models with dependent servers which characterize the network performance as a function of the number of channels, the channel load, the number of stations and the packet length distribution. For analyzing the network behavior with constant packet length we introduce techniques for representing the actual asynchronous network operation by a tractable "sequential synchronous" model. Throughput and delay measures are in this way obtained for asynchronous systems operating with constant or exponential service times. The developed approach can also be used for obtaining tractable analyses of other asynchronous systems, such as multiprocessors employing multiple-bus interconnection. In the case of HYPERchannel networks, we apply the introduced models for analyzing multi- trunk network behavior and for predicting the number of channels needed to obtain a required packet-delay/trunk-utilization performance. In HYPERchannel networks the observed results are of special significance since they are most pronounced when the number of stations is small, the situation found in the majority of operational networks.

This paper considers the issue of broadcasting protocols in multihop radio networks. The objective of a broadcasting protocol is to deliver the broadcasted message to all network nodes. To efficiently achieve this objective the broad- casting protocol in this paper utilizes two basic properties of the multihop radio network. One is the broadcast nature of the radio which allows every single trasmission to reach all nodes that are in line of sight and within range of the transmitting node. The other, spatial reuse of the radio channel, which due to the multihop nature of the network allows multiple simultaneous transmissions to be received correctly. The proposed protocol incorporates these properties to obtain a collision free forwarding of the broadcasted message on a tree. Centralized and distributed algorithms for the tree construction are presented. The obtained trees are unique in incorporating radio oriented time ordering as part of their definition. In this way multiple copies of one or more broadcasted messages can be transmitted simultaneously without collision, requiring only a small number of message transmissions. Consequently, the protocol not only guarantees that the broadcasted message reaches all network nodes in bounded time, but also ensures that the broadcasting activity will use only limited channel bandwidth and node memory. The proposed broadcast protocol thus possesses the advantages of TDM solutions while allowing the channel bandwidth to be shared, concurrently with the broadcast, with other transmission activities as dictated, for instance, by data link protocols. Some NP-completeness proofs are also given.

This paper proposes a solution to providing a collision free channel allocation in a multihop mobile radio network. An efficient solution to this problem provides spatial reuse of the bandwidth whenever possible. A robust solution maintains the collision free property of the allocation under any combination of topological changes. The node organization algorithm presented in this paper provides a completely distributed, maximally localized execution of collision free channel allocation. It allows for parallel channel allocation in stationary and mobile networks with provable spatial reuse properties. A simpler version of the algorithm provides also a highly localized distributed coloring algorithm of dynamic graphs.

We present a distributed algorithm for obtaining a fair time slot allocation for link activation in a multihop radio network. We introduce the concept of maximal fairness in which the termination of a fair allocation algorithm is related to maximal reuse of the channel under a given fairness metric. The fairness metric can be freely interpreted as the expected link traffic load demands, link priorities, etc. Since respective demands for time slot allocation will not necessarily be equal, we define fairness in terms of the closeness of allocation to respective link demands while preserving the collision free property. The algorithm can be used in conjunction with existing link activation algorithms to provide a fairer and fuller utilization of the channel.

The development of “very high speed” networks is being motivated by emerging applications and is therefore attracting increasing attention. As demonstrated in the past, in conventional high speed systems the high ratio between the end-to-end propagation delay and the message transmission time severely restricts the system performance. Thus the increase in channel bandwidth may be accompanied by only a marginal increase in actual system capacity. In this paper we propose a network architecture which eliminates this problem by introducing a combined Frequency - Time Division based control of the high speed channel. We consider the implementation characteristics of the resulting multichannel system and show that the design of protocols in these systems is subject to unique channel control penalties. Specifically, we show that in addition to the relatively high cost of channel sensing, the allocation of channel on a demand assignment basis is hindered in the multichannel configuration by the time penalty involved in locating an idle channel and by practical limitations of multichannel node interface design. We therefore introduce a new class of “allocation” protocols in which the channel access is obtained without the aforementioned penalties. The allocation protocols build on message source and destination oriented transmission rights allocation, taking into account the implementation aspects of multichannel networks. We show that the class of “multichannel allocation” protocols covers the whole range of random access to fixed channel access control policies and introduce an analytic approach for a uniform analytic treatment. The analysis demonstrates the potential for a significant improvement in the system capacity and the average message delay, when compared to a conventional single (undivided) channel system.

Demand assignment protocols have been implemented in a large number of operational LANs. However, the analytic models for protocol evaluation currently capture only a limited range of LAN operational circumstances. In this paper we present an analytic tool for evaluating fair and prioritized demand assignment protocols with a relatively general workload model. We consider arbitrary and station dependent message size distributions and arrival rates. This allows the modeling of LANs with heterogeneous workloads, thus permitting a larger correspondence between the modeled system and the real life network.

The concept of a multibeam satellite system With on-board processing and memory is studied. In this system multiple slotted ALOHA uplinks carry the traffic to the satellite. Packets are accepted at the satellite, when memory is available, and are routed to their destination zones using a TDM protocol. We present a model which can be used to evaluate a satellite system with conflict-free scheduling, i.e., a system in which several packets can be simultaneously chosen for downlink transmissions, given each earth zone is served by at most one satellite transponder in each slot. We compute the system throughput, packet delays, and buffer overflow probabilities for a general configuration. It is shown that for some configurations the one beam per zone restriction can have a significant effect on the system performance. The presented model can be also used to evaluate satellite systems when this restriction is removed and to evaluate a variety of other satellite systems.

We consider a voice/data integrated local area communication system. Due to the high suitability of CSMA/CD protocols for data communication and the existence of real time voice delay constraints we consider a hybrid TDM/CSMA/CD protocol. This model fundamentally differs from the very well documented voice/data integrated systems in point to point networks in which both voice and data users are assigned fixed duration time slots for transmission. The TDM/CSMA/CD integrated system performance is analysed and basic performance tradeoffs in the system design are manifested.

The HYPERchannel communication network configured around one to four channels is considered. We develop a queueing model which characterizes the network performance as a function of the number of channels, the channel load and the number of stations in the network. The model is used to analyze the multichannel system performance and to evaluate the effect of the channel selection mechanism, as implemented by the HYPERchannel station interface units, on the performance.

We describe an adaptive multiaccess channel protocol for use in radio networks with an arbitrary distribution of stationary hidden nodes, which provides the nodes with controlled, collision-free access to the channel. The protocol can be considered to belong to the BRAM [5] protocol family, but differs in significant ways from BRAM. In this paper we describe the tenets of the protocol, then develop the protocol, and finally develop analytic expressions for its expected throughput and delay performance. Given these delay-throughput expressions, we show how protocol "delay" optimization can be achieved by dynamic adjustment of a protocol parameter as the network traffic load changes.

In this paper we develop a graph-oriented model for dealing with broadcasting in radio networks. Using this model, optimality in broadcasting protocols is defined, and it is shown that the problem of finding an optimal protocol is NP-hard. A polynomial time algorithm is proposed under which a channel is assigned to nodes from global, multiple-source broadcasting considerations. In particular, nodes participating in the broadcast do not interfere with each other's transmissions, but otherwise simultaneous channel reuse is permitted. Protocol implementations of this approach by frequency division and by time division are given. It is shown that, using these protocols, bounded delay for broadcasted messages can be guaranteed.

In this paper, we first present the broadcast recognizing access method (BRAM), an access protocol suitable for regulating internode communication in either a radio or (coaxial or fiber) cable based communication system. The method avoids collisions, imposes negligible computational requirements on the nodes attempting to transmit, and is fair in the sense that no node will be indefinitely prevented from transmitting. Next we introduce parametric BRAM which attempts to balance the length of inserted channel idle periods, resulting from scheduling effects, against the probability of allowed message collisions. We show that parametric BRAM can be used to realize a method which balances inserted channel idle time against the probability of message collision to yield enhanced performance. For high message loads, parametric BRAM converges to BRAM, while for low and medium loadings it yields throughputs in excess of BRAM, and other methods. Both BRAM and parametric BRAM are discussed under the assumption of homogeneous message arrival rates at the nodes. We conclude by showing how the parametric BRAM can be applied when the nodes operate with heterogeneous or mixed message arrival rates.