The rapid growth of data applications is forcing service providers to seek efficient means of carrying packet data over their legacy SONET/SDH networks, designed for circuit-switched voice traffic. This problem is exacerbated by the increased deployment of new Ethernet-based VPN services over their metro networks. To support Ethernet traffic, two packet-aware SONET/SDH transport architectures have been proposed-Ethernet-over-SONET/SDH (EoS) and packet-rings (PR). In this paper, we argue that both architectures make inherent tradeoffs that limit the volume of data traffic that may be supported. Instead, we propose a hybrid architecture called CyBorg that makes selective use of EoS pipes in conjunction with a PR capability. We formulate and propose a solution to the setup failure re-arrangement problem that dynamically creates EoS pipes to supplement the existing PR if the system fails to satisfy incoming demands. We show through extensive simulations that by doing so, this novel architecture not only enables higher data traffic loads but achieves it with lower data switching capacity. We believe that this hybrid architecture and the efficiency it provides, makes for a cost-effective solution for the dilemma facing service providers.

Service providers are starting to offer next-generation E-Line (point-to-point) and E-LAN (multipoint-to-multipoint) Ethernet services over their existing SONET/SDH networks. While Ethernet typically is "best-effort", these emerging services are expected to be "carrier-class" with strict bandwidth guarantees. Consequently, spanning tree creation, critical to any Ethernet network is fundamentally changed; each tree hop now needs to have sufficient capacity to meet the requisite bandwidth demands. In this paper, we introduce the bandwidth-endowed spanning tree (BEST) problem. Unlike the polynomial complexity of standard spanning tree algorithms, BEST is NP-complete, raising questions about the scalability of these services. We propose offline and online algorithms and study their performance using extensive simulations. We show that leveraging the Virtual Concatenation protocol (ITU-T G.707) is key to practical algorithms that are both effective and efficient. Inspite of the theoretical hardness, the online algorithms we propose are a good match to "optimal", offline integer programming benchmarks, demonstrating the viability of next-generation Ethernet services.

The virtual concatenation protocol in SONET/SDH has ushered in a novel routing paradigm that enables a circuit to be "split" and routed over multiple paths. However, this diverse routing causes differential delay among the paths which can impact service if not accounted for in the routing. In this paper, we introduce the differential delay aware routing problem and show that it is not only NP-complete but is also provably hard to approximate within a constant factor. However, by transforming it into a flow routing formulation, we can derive effective, practical solutions. We present various algorithms and use extensive simulations to show that they are a good match to an "ideal" integer linear programming formulation. We also highlight how the differential delay data allows individual link delays to be reverse-engineered. We propose three algorithms to derive link delays including one that leverages the flexibility in the virtual concatenation protocol bits. Given the rise of next-generation applications such as online games where latency information is key, this knowledge of link delays, heretofore only loosely approximated, enables the telecom infrastructure to be more effective in supporting these applications.

We investigate the problem of precomputing bandwidth guaranteed paths as a cheaper replacement for on-demand routing. The focus in the prior precomputation literature has been on minimizing storage and computational overhead of the precomputation process. This paper instead explores the "quality" of precomputed paths and attempts to answer the following question: given a traffic ingress-egress node pair and storage for k routes, what paths should be materialized for good routing performance? We argue that the min-hop formulation typically assumed in prior precomputation work is a poor offline strategy. We instead propose an efficient maxflow based algorithm called MobiFlow. We show via simulations that it outperforms min-hop algorithms such as K-shortest path on several metrics including number of requests rejected and the fraction of the bandwidth routed. Furthermore, the algorithm has a low computational complexity and degrades gracefully on network failures, making it very attractive to implement in practice.

We study the problem of bandwidth fragmentation in links that comprise rings and meshes in SONET networks. Fragmentation is a serious challenge for network operators since it creates "holes" in the transport pipe causing new demands to be rejected, in spite of sufficient bandwidth being available. Unlike the well-studied, general fragmentation problem, link defragmentation is "hard" and novel due to some unique constraints imposed by the SONET standard. Since a defragmentation operation typically occurs on a network carrying live traffic, in addition to the "quality" of the output, any link defragmentation algorithm has to avoid traffic hit and also optimize the "cost" of reorganizing circuits. We propose an algorithm called mobipack that is optimal in its defragmentation quality. Moreover, we demonstrate via extensive simulations, that it also achieves its goal in a hitless manner with only marginal additional cost over the optimal, making it extremely attractive to use in practice

This paper addresses the issue of reliable transport of emerging data services in Ethernet over SONET (EoS) networks that require protection guarantees beyond standard best effort delivery. We argue that the current consensus of using Ethernet spanning tree and a SONET 1+1 protection, while providing reliability, is an inefficient use of resources. Instead, we claim that EoS opens novel opportunities for protection heretofore unavailable in other environments. In particular, the deployment of virtual concatenation and LCAS protocols enables "route splitting", creating a fundamentally new routing paradigm for circuit-switched environments. We propose a scheme called PESO, appropriate for EoS, with innovative routing, failure notification and switching components. More importantly, it is competitive with SONET protection without its 100% bandwidth overhead. We also suggest a enhancement in LCAS that can further improve PESO'S switching time. PESO leverages the underlying protocols, making it extremely attractive to implement and use in practice.

Shrinking capital expenditure budgets are forcing telecom service providers to explore engineering tools that extract greater utilization from their existing transport infrastructure. In this paper, we explore the challenges in engineering SONET rings to support higher traffic volumes. Unlike network design tools, engineering operations have to reconfigure live traffic and do so in a hitless manner. We present an efficient algorithm called MobiRing that accounts for the unique constraints imposed by the SONET standard. In spite of the hardness of the optimization problems, we show using extensive simulations that the greedy approach of MobiRing performs extremely well. More importantly, MobiRing is able to achieve hitless reconfigurations and therefore, very attractive to use in practice. This ability to do effective, hitless engineering opens the possibility that network engineering, traditionally a very infrequent operation, can now be done proactively to maintain high levels of network utilization.

MPLS traffic engineering has primarily focused on efficient route setups. However, as data traffic explodes, there is an increased demand for tools that enable network-wide tuning in order to maintain high levels of end-to-end network efficiency. Network tuning aims to pro-actively reconfigure traffic without causing any service disruption. In this paper, we explore the requirements on management systems to support tuning. Network design tools have similar goal; however, the additional requirement for online, hitless optimization fundamentally differentiates tuning from traditional network design. We present an efficient algorithm for network tuning called MobiTree. Using extensive simulation results, we show that the greedy approach in MobiTree outperforms prior traffic design schemes. More importantly, it achieves the gains while ensuring a hitless reconfiguration. Given its low overhead, we propose MobiTree as an effective solution to implement in practice.

The problem of routing bandwidth guaranteed paths in wavelength-routed, WDM optical mesh networks is explored. A WDM mesh network offers great flexibility in dynamically reconfiguring the optical core to match the IP layer demands. In this paper, we argue that IP subnets can limit the reconfigurability potential of the WDM mesh network. We show that finding the shortest IP-hop path, normally admitting a straightforward polynomial solution on the WDM mesh, is NP-hard in the presence of subnets. We propose a new algorithm called MobiTwist that finds the optimal shortest path when accounting for subnets. We also observe that subnets impose a routing penalty by forcing longer paths for bandwidth demands. Consequently, they create a trade-off between lower network efficiency if subnets are honored (due to longer paths) or, an upfront overhead of dynamically changing subnets to derive shorter paths. We propose the MobiFlex algorithm that attempts to achieve a balance by finding the shortest path given an upper limit on the number of subnet violations acceptable. The inherent hardness of the routing problem due to subnets precludes a solution with low worst-case complexity. However, we present performance results that show that both the algorithms proposed are extremely efficient in routing demands, and in practice, do so in polynomial time.

In large data warehousing environments, it is often advantageous to provide fast, approximate answers to complex decision support queries using precomputed summary statistics, such as samples. Decision support queries routinely segment the data into groups and then aggregate the information in each group (group-by queries). Depending on the data, there can be a wide disparity between the number of data items in each group. As a result, approximate answers based on uniform random samples of the data can result in poor accuracy for groups with very few data items, since such groups will be represented in the sample by very few (often zero) tuples.

Many emerging environments are increasingly facing the problem where the requirements of applications easily outstrip the system resources. This is particularly acute in the World Wide Web (WWW) and many data-intensive applications like OLAP and multimedia databases. We address this problem in the Web context via systematic multiresolution, i.e., a framework for providing responses at different qualities (resolutions) and costs. We validate our conceptual contributions by implementing NetBlitz a multiresolution-based proxy server on the WWW. NetBlitz addresses two key problems facing the Web: high latencies and heterogeneity of client resources and requirements. It solves these problems by dynamically generating the "required version" of a Web object based on client preferences and capabilities. We also propose novel multiresolution-aware caching techniques that further improve performance. Finally we experimentally demonstrate the utility of multiresolution and the caching enhancements proposed.

In large data warehousing environments, it is often advantageous to provide fast, approximate answers to complex aggregate queries based on statistical summaries of the full data. In this paper, we demonstrate the difficulty of providing good approximate answers for join-queries using only statistics (in particular, samples) from the base relations. We propose join synopses as an effective solution for this problem and show how precomputing just one join synopsis for each relation suffices to significantly improve the quality of approximate answers for arbitrary queries with foreign key joins. We present optimal strategies for allocating the available space among the various join synopses when the query work load is known and identify heuristics for the common case when the work load is not known. We also present efficient algorithms for incrementally maintaining join synopses in the presence of updates to the base relations. Our extensive set of experiments on the TPC-D benchmark database show the effectiveness of join synopses and various other techniques proposed in this paper.

Selectivity estimation of queries is an important and well-studied problem in relational database systems. In this paper, we examine selectivity estimation in the context of Geographic Information Systems, which manage spatial data such as points, lines, poly-lines and polygons. In particular, we focus on point and range queries over two-dimensional rectangular data. We propose several techniques based on using spatial indices, histograms, binary space partitionings (BSPs), and the novel notion of spatial skew. Our techniques carefully partition the input rectangles into subsets and approximate each partition accurately. We present a detailed experimental study comparing the proposed techniques and the best known sampling and parametric techniques. We evaluate them using synthetic as well as real-life TIGER datasets. Based on our experiments, we identify a BSP based partitioning that we call Min-Skew which consistently provides the most accurate selectivity estimates for spatial queries. The Min-Skew partitioning can be constructed efficiently, occupies very little space, and provides accurate selectivity estimates over a broad range of spatial queries.

Assatellite,wirelessand CableW-based networksspreadtheir reach, there is an increased infrastructure of high-bandwidth links into the home and on the road.Much of this enhanced infrastructure inherently reties on bmdcast tuhnology to deliver data to large user populations.This increase in broadcast capacity has been complemented by the growth of large-scale infomtion-centn.capptimtions.Many of these applications such as wireless interneta and traffic information systems are .pull-hosed, that is, they respond to on-denrarrd user requests.In this paper, we study the scheduling problems arising in such on-demand broadwt environments for applications with data requests of varying sizes, and the novel issues that arise therein.We study the problem in its generality while much of the previous work has fwusd on one speciat case or the other, such as, assuming identid-sized data requests, or static ctient a-s profiles known by the server u pm"on.,etc.Traditionally, the response time of the requ~ts has been used as a performance measure.In this paper, we additionally motivate an alternative metric -the sfretch of a request, which seems better suited to variable-sized requests.Our main contribution is an algorithm Aled ~based on the criteria of optimizing the worst ease stretch of individud requests.w is simple and effitien~firthersnore, as our experiments show, it performs well mmpared to more expensive strategies that serve as yardsticks for optimizing worstiaverage case response timdstretch m-ures.Finding a right brdancebetween the worst case ~ndividud) and the average ease Qlobd) performanceis a key challenge.Surprisingly,w seems to find such a batanu.Additionrdly, even"though it is dmignd to minimize the stretch, it performs reasonably well on the tradition response time measure too.

The increasing ability to interconnect computers through internet-working, wireless networks, high-bandwidth satellite, and cable networks has spawned a new class of information-centered applications based on data dissemination. These applications employ broadcast to deliver data to very large client populations. We have proposed the Broadcast Disks paradigm [Zdon94, Acha95b] for organizing the contents of a data broadcast program and for managing client resources in response to such a program. Our previous work on Broadcast Disks focused exclusively on the “push-based” approach, where data is sent out on the broadcast channel according to a periodic schedule, in anticipation of client requests. In this paper, we study how to augment the push-only model with a “pull-based” approach of using a backchannel to allow clients to send explicit requests for data to the server. We analyze the scalability and performance of a broadcast-based system that integrates push and pull and study the impact of this integration on both the steady state and warm-up performance of clients. Our results show that a client backchannel can provide significant performance improvement in the broadcast environment, but that unconstrained use of the backchannel can result in scalability problems due to server saturation. We propose and investigate a set of three techniques that can delay the onset of saturation and thus, enhance the performance and scalability of the system.

Broadcast disks have been proposed as a means to efficiently deliver data to clients in "asymmetric" environments where the available bandwidth from the server to the clients greatly exceeds the bandwidth in the opposite direction. A previous study investigated the use of cost based caching to improve performance when clients access the broadcast in a demand driven manner (S. Acharya et al., 1995). Such demand driven access however, does not fully exploit the dissemination based nature of the broadcast, which is particularly conducive to client prefetching. With a broadcast disk, pages continually flow past the clients so that in contrast to traditional environments, prefetching can be performed without placing additional load on shared resources. We argue for the use of a simple prefetch heuristic called PT and show that PT balances the cache residency time of a data item with its bandwidth allocation. Because of this tradeoff, PT is very tolerant of variations in the broadcast program. We describe an implementable approximation for PT and examine its sensitivity to access probability estimation errors. The results show that the technique is effective even when the probability estimation is substantially different from the actual values.

For the last few years mobile (or nomadic) computing has generated tremendous interest in both the research and the industrial community. Mobility is seen as an area of great potential benefits, both in terms of products and research contributions, However, at this time, mobile systems are so novel that there is little practical experience regarding their use. This has led to much speculation regarding a number of system issues such as determining what the killer apps will be, the hardware architecture of the nomadic machines, deciding whether communication or computation will be their primary feature and so on. One of the issues yet to be resolved is that of the architecture of these machines. Will mobile machines be essentially a new type of portable computer (although perhaps smaller, less powerful, friendlier, and pencentric) or will we carry around with us the equivalent of an X-window terminal (i.e., simply a display device, with all computation being carried out at a non-mobile server)? Examples of the first approach are the Apple Newton and the EO computers formerly marketed by AT&T, while the second approach is being explored by a number of other researchers (e.g., the InfoPad project at U.C. Berkeley, or the Xerox PARC tabs). This paper briefly describes the research issues involved and outlines the pros and cons of either approach. We also explore in detail one particular aspect, namely, the performance implications of the choice of architecture in a distributed information system. The results are presented as a set of simulation-based studies.

Mobile computing adds a new wrinkle to the ageold problem of caching. Today's wireless links are both slow and expensive, and are not always available to a user. Therefore, when a mobile user is disconnected, a cache miss means (at best) a substantial cost in time and money, or (at worst) a complete halt to work if critical information has not been cached. Existing solutions to this problem rely on some combination of explicit hoard profiles and spying on a user's file accesses.

This paper proposes the use of repetitive broadcast as a way of augmenting the memory hierarchy of clients in an asymmetric communication environment. We describe a new technique called "Broadcast Disks" for structuring the broadcast in a way that provides improved performance for non-uniformly accessed data. The Broadcast Disk superimposes multiple disks spinning at different speeds on a single broadcast channel--in effect creating an arbitrarily fine-grained memory hierarchy. In addition to proposing and defining the mechanism, a main result of this work is that exploiting the potential of the broadcast structure requires a re-evaluation of basic cache management policies. We examine several "pure" cache management policies and develop and measure implementable approximations to these policies. These results and others are presented in a set of simulation studies that substantiates the basic idea and develops some of the intuitions required to design a particular broadcast program.