We study how to achieve a desired connectivity in a wireless mesh network using beamforming antennas. We show that there is no unique solution to this problem. We propose a simple algorithm, directionality as needed (DAN), which strikes a good balance between the dual goals of minimum network design cost and minimum interference among different links.

Directional antennas are very attractive in wireless mesh networks (WMN). We study the problem of link scheduling and power control in a time-division multiple access (TDMA) WMN where the nodes use directional antennas. This is a cross- layer design problem spanning the physical and the link layers. Link scheduling in WMNs requires careful modeling of interference. Interference models used for omni-directional antennas cannot be used for directional antennas. We develop a generalized interference model applicable to directional antennas. Then, we use this model to formulate the link scheduling and power control problem as a Mixed Integer Linear Program. We also propose a heuristic algorithm to solve the problem efficiently.

Hybrid wireless-optical broadband access network (WOBAN) is a combination of wireless and optical networks to optimize the cost and performance of an access network. Wireless nodes collect traffic from end users and carry them to the optical part of a WOBAN using multiple hops, accumulating delay at each wireless node. Moreover, the radio capacity on each wireless link limits the capacity on each outgoing link from the node in a single-radio wireless mesh network (WMN) of a WOBAN. Thus, delay and capacity limitation in the WMN of a WOBAN is a major bottleneck. We design a capacity and delay aware routing scheme, CaDAR, to minimize the delay and increase network support in the WMN of a WOBAN. Our analysis shows that CaDAR is an efficient routing scheme for a single-radio WMN for a WOBAN that can support much higher load and has lower system delay than other approaches because of better load balanced routing.

In a WOBAN, the back end is a wired optical network, the front end is managed by wireless connectivity, and, in between, the tail ends of the optical part [known as optical network unit (ONU)] communicate directly with wireless access points (AP). We study a WOBAN deployment scenario and investigate an algorithm to optimize the placement of multiple ONUs. To obtain some representative data on locations of typical wireless users, we have conducted a survey on the distribution and types of wireless routers in the Wildhorse residential neighborhood of North Davis, CA. We also formulate the multiple-ONU deployment problem using a combinatorial optimizer, viz., simulated annealing. Having found the suitable locations for ONUs, we compare the expenditures of a WOBAN vs. a wired access solution, namely Passive Optical Network (PON). To capture the challenges behind a complete WOBAN setup, we propose and investigate a joint optimization algorithm, which considers design aspects of both the wireless front end, such as avoiding interference among neighboring APs, and the optical back end, such as minimizing expensive fiber layout.

Hybrid wireless-optical broadband access network (WOBAN) is a promising architecture for future network operations. Recently, the wireless part of WOBAN has been gaining increasing attention and early versions are being deployed as a municipal access solution to eliminate the wired backhaul to every wireless router. This architecture saves on network deployment costs because fiber (or wiring) does not need to extend to the end user, and it extends the reach of emerging optical access solutions, e.g., passive optical network (PON)-based access solutions. However, a major research opportunity exists in developing an efficient routing algorithm for the wireless front end of WOBAN. We propose and investigate the characteristics of "delay- aware routing algorithm (DARA)" that minimizes the average packet delay in the wireless front end of a WOBAN. We model wireless routers as queues and predict wireless link states periodically. Our simulation experiments show that DARA achieves better load balancing and less congestion compared to tradional approaches such as minimum-hop routing algorithm (MHRA) and shortest- path routing algorithm (SPRA). In addition to minimizing the delay, DARA also improves the average hop count compared to the predictive throughput routing algorithm (PTRA), a popular protocol used in several deployments for the wireless front end of a WOBAN.

The concept of a hybrid wireless-optical broadband access network (referred to as WOBAN here) is a very attractive one. This is because it may be costly in several situations to run fiber to every home from the telecom central office (CO); also, providing wireless access from the CO to every end user may not be possible because of limited spectrum. Thus, running fiber as far as possible from the CO towards the end user and then having wireless access technologies take over may be an excellent compromise. How far should fiber penetrate before wireless takes over is an interesting engineering design and optimization problem, which our study is focussing on. We propose and investigate the characteristics of a "mixed integer programming (MIP)" model for optimum placements of base stations (BS) and optical network units (ONU) in a WOBAN (primal problem). We develop several constraints to be satisfied: BS and ONU installation, user and channel assignment, and signal-quality and interference constraints. To solve this MIP with reasonable accuracy, we use "Lagrangean relaxation" to obtain the corresponding "Lagrangean dual" problem. Via simulation experiments, we verify how sensitive is the placement problem with respect to a set of chosen metrics.

Current cellular networks are not self-organizing in nature; e.g., they are vulnerable to base station (BS) failures or malfunctions due to congestion (a large amount of traffic) or due to emergencies. To address this problem, use of fixed relay nodes (FRNs) in a geographical area (which may or may not be covered by base stations or access points) was recently proposed to introduce self-organizing features to cellular wireless networks, such as enabling traffic forwarding in case of congestion and handling base station failures. In this paper, we provide an algorithm for choosing system parameters in a joint cellular and fixed relay network such that quality of service (QoS) requirements in terms of delay are satisfied. In particular, we show how to determine the optimum number of neighbors to achieve small average path lengths, high coverage, and low vulnerability to failures.

Summary form only given. The size of the Internet increases with the mainstream adoption of the broadband mobility connecting a myriad of devices and sensors at homes and businesses and the use of IPv6. All this adds to the spatio-temporal complexity of the network topology and dynamics. We present a brief overview of the role that self-organization can play in this new era of complexity. Issues of QoS, scalability, robustness, and reachability, among others (e.g., heterogeneity) continues to dominate the research in the future. First, we present the definition, scope, and applicability of self-organization. Then we briefly articulate the need for self-organization, and some recent breakthrough advances in this emerging area of research. This is followed by some near- and long-term scenarios where self-organization can be applied, and some results that we have obtained. We conclude the talk with a discussion on the key challenges that lie ahead.

Accelerating multimedia content delivery to mobile devices is challenging because we must not only address long and unpredictable latency created by the error-prone air interface, but also meet mobility-specific requirements such as efficient terminal power consumption. In this paper, we present a novel architecture for content delivery in the mobile environment (ACME) that significantly accelerates interactive mobile services such as Web browsing. ACME exploits the key concept of user interest correlation (the interest in the same content among different users) to push content to mobile users efficiently. Trace-driven simulations show that ACME achieves 50% effectiveness of content broadcasting by, on average, pushing content to only 0.7% to 6% of all users, thus substantially reducing mobile terminal power consumption. Furthermore, ACME has superior scalability as the push group size increases by only 62% when the total number of users increases by 16 times

In this paper, we propose and investigate the characteristics of a fair queueing with service envelopes (FQSE) algorithm-a hierarchical fair-share scheduling algorithm for access networks based on a remote scheduling system such as Ethernet passive optical networks (EPON) or cable TV network. FQSE is designed to overcome the limiting factors of a typical remote scheduling system such as large control-plane delay, limited control-plane bandwidth, and significant queue switch-over overhead. The algorithm is based on a concept of service envelope-a function representing the fair allocation of resources based on a global network condition called satisfiability parameter (SP). We define properties of cousin-fairness and sibling-fairness and show the FQSE to be cousin-fair. FQSE is unique in that it is the only hierarchical algorithm that is simultaneously cousin-fair. Furthermore, we show the necessary techniques to adapt FQSE to variable-sized packet-based networks. We analyze FQSE performance in EPON serving 1024 independent queues and demonstrate FQSE's ability to provide guaranteed bandwidth to each queue and to share the excess bandwidth fairly.

Traffic grooming is an important task in interworking between the wavelength-division multiplexing (WDM) optical network that supplies "pipes" at the wavelength granularity, and the attached client networks that usually require connections of subwavelength granularity. The focus of this paper is to conduct performance analysis of grooming dynamic client traffic in WDM optical networks with a mesh topology. This paper first briefly introduces the traffic grooming problem in WDM optical networks and the issues related to performance analysis. It then develops two link blocking models, an exact model based on the stochastic knapsack problem and an approximation model based on an approximate continuous time Markov chain (CTMC). The end-to-end performance analysis is conducted using the reduced load approximation. The result obtained from analysis is shown to be accurate compared with the numerical result obtained from simulation.

Ethernet-based passive optical network (EPON) technology is being considered as a promising solution for next generation broadband access networks due to the convergence of low-cost Ethernet equipment and low-cost fiber infrastructure along with its ability to support successfully IP-based multimedia applications with quality of service requirements. We propose to use the multi-point control protocol (MPCP) defined in the IEEE 802.3ah task force to arbitrate the transmission of different users; dynamic bandwidth allocation (DBA) algorithms are then presented to allocate bandwidths between these users effectively and fairly. These DBA algorithms are then augmented to support differentiated services in a network with heterogeneous traffic. We conduct detailed simulation experiments to study the performance and validate the effectiveness of the proposed protocols.

The paper develops a theoretical performance analysis model for the online single-hop traffic grooming algorithm in the mesh topology wavelength division multiplexing (WDM) optical network. This is done by developing a link blocking model for traffic grooming based on the continuous time Markov chain and queueing theory, and by extending the Erlang fixed-point approximation for traffic grooming analysis. The results obtained from the analytic model are shown to match well with the numerical results obtained from simulations.

Optical circuit switching (OCS) is a sophisticated technology widely deployed in current optical networks, and has many advantages in the transport of stable and long-duration traffic flows. However, it is not suitable for bursty data traffic. On the other hand, an alternative technology, optical burst switching (OBS), well addresses bursty IP traffic transport, but is not suitable for stable and large flows. To transport both types of traffic effectively, a hybrid optical switching approach is proposed which combines OCS and OBS to exploit the merits of both technologies. The performance has been evaluated in terms of throughput and blocking probability.

Efficient path selection combined with fast restoration algorithms is a key requirement for designing shared restorable mesh networks. In this paper we first discuss a distributed path selection algorithm for efficient routing of restorable connections in optical networks. This approach relies on the knowledge of global information, maintained at each node, to determine link sharability and compute optimal shared paths; we compare its performance to another protocol [C. Assi et al., 2002] that only requires the knowledge of local resource usage. Second, we study the network's ability to recover from single element failures in a shared mesh network and we propose a new restoration algorithm for rapid recovery upon a failure. The significant contribution of this algorithm is that the network restoration time is independent of the protection path length (i.e., the effect of propagation delay is eliminated) as well as the accumulation of the switch configuration times. We evaluate the performance of these protocols through simulation experiments.

Ethernet-based passive optical network (EPON) technology is being considered as a promising solution for next-generation broadband access networks due to the convergence of low-cost Ethernet equipment and low-cost fiber infrastructures. A major feature for this new architecture is the use of a shared transmission media between all users; hence, medium access control arbitration mechanisms are essential for the successful implementation of EPON: i.e., to ensure a contention-free transmission and provide end users with equal access to the shared media. We propose to use the multipoint control protocol defined by the IEEE 802.3ah task force to arbitrate the transmission of different users, and we present different dynamic bandwidth allocation (DBA) algorithms to allocate bandwidths effectively and fairly between end users. These DBA algorithms are also augmented to support differentiated services, a crucial requirement for a converged broadband access network with heterogeneous traffic. We show that queueing delays under strict bandwidth allocation algorithms result in an unexpected behavior for certain traffic classes, and we suggest the use of DBA with appropriate local queue management to alleviate this inappropriate behavior. We conduct detailed simulation experiments to study the performance and validate the effectiveness of the proposed protocols.

This paper presents a novel hybrid distributed fault-management protocol for combating single-fiber failures in mesh-based DWDM optical networks. The proposed hybrid approach combines Link State Protocol to disseminate and update information only about the physical connectivity of the network and a distributed local information-based signaling algorithm for connection management. The purpose of using a hybrid approach is two advantages: (1) reducing the signaling overhead associated with the global information-based link state protocol by using a distributed approach where only local information is maintained at each node; and (2) eases the implementation of the routing protocol where physical constraints, such as link/node diversity, are imposed. The performance of the proposed hybrid approach is evaluated via comparing the dedicated-path protection and the shared-path protection schemes in terms of blocking probability, restoration time under failure assumption, and data loss incurred during the recovery phase.

We propose an agent-based traffic grooming and management mechanism for IP over wavelength division multiplexing (WDM) optical networks. The agent-based mechanism effectively manages the traffic aggregation across the optical core between the IP client networks. It offers the benefit of efficient resource usage and reduced connectivity complexity for IP over WDM optical networks. We have studied this mechanism and evaluated its performance over various traffic patterns.

Web caching is becoming increasingly important as rich content such as streaming media gains popularity on the Web. However, conventional Web caching lacks two essential functionalities for many services. First, Web caching is largely a "best effort" service, lacking the capability of guaranteeing application-level QoS such as content storage that many services (including streaming media) desire. Second, standard Web caching does not ensure strong content consistency. In this paper, we develop a cache on demand (CoD) system that addresses both problems. The key components of the CoD system are an admission control mechanism that guarantees the content storage, and the CoD protocol that ensures content consistency between the origin server and the cache. CoD also allows QoS to be switched between "guaranteed" and "best effort" as needed. CoD is a flexible and effective solution for providing application layer QoS and strong consistency, and provides a new model for revenue-generating services.

An IP transport scheme for third generation radio access networks (3G RAN) based on multiprotocol label switching (MPLS) technology is proposed. The basic idea is to establish and manage label switched paths for interconnecting base stations and radio network controllers. This scheme incorporates constraint-based routing and Diffserv to provide transport bears that can support bandwidth provisioning and a variety of QoS requirements in the RAN.

The purpose of this work is to show the benefits gained by dynamically provisioning low-rate traffic streams at the IP/MPLS layer in future IP-centric WDM-based optical networks. First, several low-rate data flows are statistically multiplexed (groomed) onto one wavelength at the IP/MPLS router. Then, conventional dynamic lightpath provisioning schemes at the physical WDM layer, where the bandwidth of a connection request is assumed to be a full wavelength capacity, are extended to allow the provisioning of "sub-lambda" connection flow requests at the IP/MPLS layer. In this work, provisioning a connection request implies that a flow of data is successfully routed if both an active path and another alternate link and node-disjoint backup path are setup at the same time.

This paper proposes two new distributed signaling protocols for fast automatic setup and tear-down of paths across the emerging interconnection models for IP-over-optical-networks. The first scheme is probe flooding-based routing (PFBR) algorithm with backward reservation while the second scheme is based on an adaptive routing algorithm called multi-path routing (MPR) where k paths are probed simultaneously. Our objective in developing these protocols is twofold: first, to simplify the specific signaling protocols or algorithms in the components of MPLS control plane; and second, to adapt the performance optimization algorithm to the requirements of different user applications by having the flexibility to vary the relative weight assigned to each of three performance metrics [call acceptance rate (CAR), call set-up time (CST), and routing distance (RD)].

In survivable WDM optical networks, one of the critical issues is route computation. Although there is a possibility to optimize the route computation (together with the wavelength assignment) for static traffic pattern, it is impossible to perform such optimization for incremental and dynamic traffic. The conventional approach first computes the working path and then computes an edge-disjoint protection path using the shared risk link groups (SRLGs) information of the working path. We propose a joint working and protection path selection approach. Our approach tries to find multiple pairs of candidate working and protection paths. Then the pair with the minimum cost sum is selected. We have evaluated the performance benefit gained from the joint path selection approach with a single service class dynamic traffic supporting 1:1 protection scheme.

We address the issue of how to provide quality of service (QoS) with limited fiber delay lines (FDLs) at the WDM layer. We propose an offset-time-based scheme, which is less complex and more scalable than existing buffer-based schemes. The proposed scheme does not mandate any buffer at the intermediate nodes, but can take advantage of FDL-based buffers, and thus is suitable for optical networks. We discuss a couple of structures of the FDL "buffers" (which differ from the conventional queues), and evaluate their effectiveness. Specifically, the offset time required for class isolation when reserving resources such as wavelengths and FDLs is quantified. The effect of having limited FDLs on the offset time-based scheme is measured in terms of the burst loss probability and queuing delay as a function of the offset time, the maximum delay time of FDLs, the number of FDLs, and the number of wavelengths.

We address the issue of how to provide basic quality of service (QoS) in optical burst-switched WDM networks with limited fiber delay lines (FDLs). Unlike existing buffer-based QoS schemes, the novel offset-time-based QoS scheme we study in this paper does not mandate any buffer for traffic isolation, but nevertheless can take advantage of FDLs to improve the QoS. This makes the proposed QoS scheme suitable for the next generation optical Internet. The offset times required for class isolation when making wavelength and FDL reservations are quantified, and the upper and lower bounds on the burst loss probability are analyzed. Simulations are also conducted to evaluate the QoS performance in terms of burst loss probability and queuing delay. We show that with limited FDLs, the offset-time-based QoS scheme can be very efficient in supporting basic QoS.

In a wireless environment, due to topology changes and characteristics of media (interference in radio signals) the bandwidth of a link is unpredictable and possibly very low, the error rates are variable and extremely high. Provisioning and guaranteeing quality of service (QoS) in such an environment is a very challenging problem. In this paper we propose an adaptive and QoS framework to support multimedia applications in a wireless networking environment. The proposed framework is hierarchical in nature with cluster of mobile end hosts connected to a base station, base stations are connected to a supervisory node, which in turn is connected to the wired infrastructure. The changing conditions in wireless due to interference and possibly mobility, entitle that the real-time applications needing stringent QoS should be adaptable. The framework uses a generic feedback mechanism to support adaptability at all layers of the wireless network. An overview of existing wireless architectures which support QoS is given. The architectures discussed are WAMIS (wireless adaptive multimedia information system), SWAN (seamless wireless ATM network), MMWN (multimedia support for mobile wireless networks), and QGMC (QoS guarantees in mobile computing). The proposed approach is compared with these existing methods.

Frame relay (FR) service via an FR interface over a common asynchronous transfer mode (ATM) backbone network requires an FR-to-ATM interworking unit (IWU), the functionality of which directly impacts the engineering of the overall network in terms of the capacity required, quality of service (QoS) expected, and the interference among different types of services being offered on the same platform. In the absence of a traffic shaping function in the equipment at the customer's location, the issue of policing and bandwidth allocation becomes much more critical. This paper focuses on the issue of FR traffic descriptor mapping, the issue of traffic policing in the frame mode and the cell mode, and the implication on the QoS when the same bandwidth resources are shared by the ATM [cell relay (CR)] and FR virtual connections. Some major conclusions that we draw from the computer simulations are: (1) the performance is somewhat independent of the mode in which traffic policing is implemented; (2) from a cost standpoint it is more advantageous to use the cell mode for traffic policing; (3) the allocation of bandwidth in the multiplexer and the switching fabric is greatly dependent on the type of service interface used since the FR traffic becomes much burstier after frame-to-cell conversion process; and (4) it becomes necessary to provide a traffic shaping function after the conversion process in order to achieve high bandwidth utilization, fair allocation of bandwidth resources, and guaranteed QoS.

The authors introduce a model based on arrival rate histograms for characterizing the behavior of an ATM buffer when it is carrying variable bit rate video traffic. Traffic smoothing on a frame-by-frame basis allows a quasistatic approximation that accurately predicts results such as buffer occupancy distributions and cell loss rates to be made. Convolving individual source histograms allow prediction of the queueing performance of a multiplexed stream. The approximation is investigated in more detail by modeling video as a Markov modulated Poisson process. It is shown that the multiplexer system is nearly completely decomposable (NCD). NCD systems have a well-known approximate solution, which is identical to the histogram approximation. Error bounds for the NCD approximation are also known and are reasonably tight. Results indicate that while the presence of strong correlations is an important characteristic of video traffic, the actual form of that correlation is not.>

The authors develop a model for characterizing the behavior of an asynchronous transfer mode (ATM) buffer when it is carrying variable-bit-rate video traffic. Traffic smoothing on a frame-by-frame basis allows the modeling of video sources as randomly modulated Poisson processes which are characterized by their bit rate histograms. An M/D/1/N approximation is used to accurately predict results such as buffer occupancy distributions and cell loss rates. Given the bit rate histograms of several individual video sources, a histogram for the aggregate arrival process can be found and the system behavior can be predicted. A new call admission control scheme and policing algorithm are developed based on the model. They can be used to prevent congestion in the network and to protect calls that adhere to parameters given at call setup.>

A combined inter/intra-frame discrete cosine transform (DCT) with layered transmission of (significant) coefficient sets is proposed. In the scheme, a whole frame is either intraframe or interframe coded based on the amount of motion. In the interframe mode, a vertical strip, which cycles periodically to refresh a section of the frame, is intraframe coded. This refresh feature preserves the synchronization in the event of cell loss. The layered transmission of the coefficients allows delivery of the desired quality video, after low-energy (layered) coefficients are selectively discarded, and immunity to cell loss is achieved by utilizing the correctly received layers to compensate for the effects of lost cells in reconstructing the frame blocks.>

The authors describe a novel adaptive vector quantization (VQ) scheme suitable for packet video. The technique is shown to provide flexibility in selecting the desired image quality, without the need to send the code vectors themselves. A large codebook is divided into two parts, called higher and lower priority sections, representing common and specific characteristics of images. Entries in the two sections are reorganized and/or exchanged as a function of the usage of the code vectors therein. The rate and extent of adaptation are dictated by the update interval and the desired level of quality, respectively, without requiring any transmission of the vectors themselves. Experimental results are presented.>

Most original document images tend to be bi-level. When electronically captured, raw pixels are represented typically as a 6 or 8 bit number on a rectangular array. Traditionally, these pixels are thresholded to generate a binary image for further processing. In the first part of the paper we describe why is it advantageous to threshold an image to a 2- or 3-bit pixel image rather than a 1-bit per pixel image. This helps mitigate the staircasing effect (seen in a binarized image), especially when the spatial resolution of the sampled image is poor. The second part of the paper describes several encoding algorithms to compress multi-level thresholded images. Through examples, it is shown that compression of error images (generated by DPCM), utilizing a modified runlength coding than the CCITT Group 3 coding and when pixels are concatenated, yields substantially better compression factors than the other approaches.