As modern hardware architectures evolve to support increasingly diverse, complex instruction sets for meeting the performance demands of modern workloads in image processing, deep learning, etc., it has become ever more crucial for compilers to provide robust support for evolution of their internal abstractions and retargetable code generation support to keep pace with emerging instruction sets. We propose Hydride, a novel approach to compiling for complex, emerging hardware architectures. Hydride uses vendor-defined pseudocode specifications of multiple hardware ISAs to automatically design retargetable instructions for AutoLLVM IR, an extensible compiler IR which consists of (formally defined) language-independent and target-independent LLVM IR instructions to compile to those ISAs, and automatically generated instruction selection passes to lower AutoLLVM IR to each of the specified hardware ISAs. Hydride also includes a code synthesizer that automatically generates code generation support for schedule-based languages, such as Halide, to optimally generate AutoLLVM IR. Our results show that Hydride is able to represent 3,557 instructions combined in x86, Hexagon, ARM architectures using only 397 AutoLLVM IR instructions, including (Intel) SSE2, SSE4, AVX, AVX2, AVX512, (Qualcomm) Hexagon HVX, and (ARM) NEON vector ISAs. We created a new Halide compiler with Hydride using only a formal semantics of Halide IR, leveraging the auto-generated AutoLLVM IR and back-ends for the three hardware architectures. Across kernels from deep learning and image processing, this compiler is able to perform just as well as the mature, production Halide compiler on Hexagon, and outperform on x86 by 8% and ARM by 3%. Hydride also outperforms the production Halide's LLVM back end by 12% on x86, 100% on HVX, and 26% on ARM across the same kernels.

In our study, we present bifurcated attention, a method developed for language model inference in single-context batch sampling contexts. This approach aims to reduce redundant memory IO costs, a significant factor in latency for high batch sizes and long context lengths. Bifurcated attention achieves this by dividing the attention mechanism during incremental decoding into two distinct GEMM operations, focusing on the KV cache from prefill and the decoding process. This method ensures precise computation and maintains the usual computational load (FLOPs) of standard attention mechanisms, but with reduced memory IO. Bifurcated attention is also compatible with multi-query attention mechanism known for reduced memory IO for KV cache, further enabling higher batch size and context length. The resulting efficiency leads to lower latency, improving suitability for real-time applications, e.g., enabling massively-parallel answer generation without substantially increasing latency, enhancing performance when integrated with post-processing techniques such as reranking.

LLMs can now act as autonomous agents that interact with digital environments and complete specific objectives (e.g., arranging an online meeting). However, accuracy is still far from satisfactory, partly due to a lack of large-scale, direct demonstrations for digital tasks. Obtaining supervised data from humans is costly, and automatic data collection through exploration or reinforcement learning relies on complex environmental and content setup, resulting in datasets that lack comprehensive coverage of various scenarios. On the other hand, there is abundant knowledge that may indirectly assist task completion, such as online tutorials that were created for human consumption. In this work, we present Synatra, an approach that effectively transforms this indirect knowledge into direct supervision at scale. We define different types of indirect knowledge, and carefully study the available sources to obtain it, methods to encode the structure of direct demonstrations, and finally methods to transform indirect knowledge into direct demonstrations. We use 100k such synthetically-created demonstrations to finetune a 7B CodeLlama, and demonstrate that the resulting agent surpasses all comparably sized models on three web-based task benchmarks Mind2Web, MiniWoB++ and WebArena, as well as surpassing GPT-3.5 on WebArena and Mind2Web. In addition, while synthetic demonstrations prove to be only 3% the cost of human demonstrations (at $0.031 each), we show that the synthetic demonstrations can be more effective than an identical number of human demonstrations collected from limited domains.

Retrieval-based language models (R-LM) model the probability of natural language text by combining a standard language model (LM) with examples retrieved from an external datastore at test time. While effective, a major bottleneck of using these models in practice is the computationally costly datastore search, which can be performed as frequently as every time step. In this paper, we present RetoMaton - retrieval automaton - which approximates the datastore search, based on (1) saving pointers between consecutive datastore entries, and (2) clustering of entries into "states". This effectively results in a weighted finite automaton built on top of the datastore, instead of representing the datastore as a flat list. The creation of the automaton is unsupervised, and a RetoMaton can be constructed from any text collection: either the original training corpus or from another domain. Traversing this automaton at inference time, in parallel to the LM inference, reduces its perplexity by up to 1.85, or alternatively saves up to 83% of the nearest neighbor searches over $k$NN-LM (Khandelwal et al., 2020) without hurting perplexity. Our code and trained models are available at https://github.com/neulab/retomaton .

Geotagged tweet streams contain invaluable information about the real-world local events like sports games, protests and traffic accidents. Timely detecting and extracting such events has various applications but yet unsolved challenges. In this paper, we present DeLLe, a methodology for automatically Detecting Latest Local Events from geotagged tweet streams. DeLLe first finds unusual locations which have aggregated unexpected number of tweets, and then ranks the unusual locations to select the top ones that are likely to be local event candidates. We evaluate DeLLe on the city of Seattle, WA as well as a larger city of New York. The results show that the proposed method generally outperforms competitive baseline approaches.

dbDedup is a similarity-based deduplication scheme for on-line database management systems (DBMSs). Beyond block-level compression of individual database pages or operation log (oplog) messages, as used in today's DBMSs, dbDedup uses byte-level delta encoding of individual records within the database to achieve greater savings. dbDedup's single-pass encoding method can be integrated into the storage and logging components of a DBMS to provide two benefits: (1) reduced size of data stored on disk beyond what traditional compression schemes provide, and (2) reduced amount of data transmitted over the network for replication services. To evaluate our work, we implemented dbDedup in a distributed NoSQL DBMS and analyzed its properties using four real datasets. Our results show that dbDedup achieves up to 37x reduction in the storage size and replication traffic of the database on its own and up to 61x reduction when paired with the DBMS's block-level compression. dbDedup provides both benefits with negligible effect on DBMS throughput or client latency (average and tail).

With the rise of large-scale, Web-based applications, users are increasingly adopting a new class of document-oriented database management systems (DBMSs) that allow for rapid prototyping while also achieving scalable performance. Like for other distributed storage systems, replication is important for document DBMSs in order to guarantee availability. The network bandwidth required to keep replicas synchronized is expensive and is often a performance bottleneck. As such, there is a strong need to reduce the replication bandwidth, especially for geo-replication scenarios where wide-area network (WAN) bandwidth is limited.

The Deuteronomy transactional key value store executes millions of serializable transactions/second by exploiting multi-version timestamp order concurrency control. However, it has not supported range operations, only individual record operations (e.g., create, read, update, delete). In this paper, we enhance our multi-version timestamp order technique to handle range concurrency and prevent phantoms. Importantly, we maintain high performance while respecting the clean separation of duties required by Deuteronomy, where a transaction component performs purely logical concurrency control (including range support), while a data component performs data storage and management duties. Like the rest of the Deuteronomy stack, our range technique manages concurrency information in a latch-free manner. With our range enhancement, Deuteronomy can reach scan speeds of nearly 250 million records/s (more than 27 GB/s) on modern hardware, while providing serializable isolation complete with phantom prevention.

Azure DocumentDB is Microsoft's multi-tenant distributed database service for managing JSON documents at Internet scale. DocumentDB is now generally available to Azure developers. In this paper, we describe the DocumentDB indexing subsystem. DocumentDB indexing enables automatic indexing of documents without requiring a schema or secondary indices. Uniquely, DocumentDB provides real-time consistent queries in the face of very high rates of document updates. As a multi-tenant service, DocumentDB is designed to operate within extremely frugal resource budgets while providing predictable performance and robust resource isolation to its tenants. This paper describes the DocumentDB capabilities, including document representation, query language, document indexing approach, core index support, and early production experiences.

Recent OLTP support exploits new techniques, running on modern hardware, to achieve unprecedented performance compared with prior approaches. In SQL Server, the Hekaton main-memory database engine embodies this new OLTP support. Hekaton uses the Bw-tree to achieve its great indexing performance. The Bw-Tree is a latch-free B-tree index that also exploits log-structured storage when used "beyond" Hekaton as a separate key value store. It is designed from the ground up to address two hardware trends: (1) Multi-core and main memory hierarchy: the Bw-tree is completely latch-free, using an atomic compare-and-swap instruction to install state changes on a "page address" mapping table; it performs updates as "deltas" to avoid update-in-place. These improve performance by eliminating thread blocking while improving cache hit ratios. (2) Flash storage: the Bw-tree organizes secondary storage in a log-structured manner, using large sequential writes to avoid entirely the adverse performance impact of random writes. We demonstrate the architectural versatility and performance of the Bw-tree in two scenarios: (a) running live within Hekaton and (2) running as a standalone key value store compared to both BerkeleyDB and a state-of-the-art in-memory range index (latch-free skiplists). Using workloads from real-world applications (Microsoft XBox Live Primetime and enterprise deduplication), we show the Bw-tree is 19x faster than BerkeleyDB and 3x faster than skiplists.

The emergence of new hardware and platforms has led to reconsideration of how data management systems are designed. However, certain basic functions such as key indexed access to records remain essential. While we exploit the common architectural layering of prior systems, we make radically new design decisions about each layer. Our new form of B-tree, called the Bw-tree achieves its very high performance via a latch-free approach that effectively exploits the processor caches of modern multi-core chips. Our storage manager uses a unique form of log structuring that blurs the distinction between a page and a record store and works well with flash storage. This paper describes the architecture and algorithms for the Bw-tree, focusing on the main memory aspects. The paper includes results of our experiments that demonstrate that this fresh approach produces outstanding performance.

LLAMA is a subsystem designed for new hardware environments that supports an API for page-oriented access methods, providing both cache and storage management. Caching (CL) and storage (SL) layers use a common mapping table that separates a page's logical and physical location. CL supports data updates and management updates (e.g., for index re-organization) via latch-free compare-and-swap atomic state changes on its mapping table. SL uses the same mapping table to cope with page location changes produced by log structuring on every page flush. To demonstrate LLAMA's suitability, we tailored our latch-free Bw-tree implementation to use LLAMA. The Bw-tree is a B-tree style index. Layered on LLAMA, it has higher performance and scalability using real workloads compared with BerkeleyDB's B-tree, which is known for good performance.

In this paper, we study the problem of utility maximization in peer-to-peer (P2P) systems, in which aggregate application-specific utilities are maximized by running distributed algorithms on P2P nodes, which are constrained by their uplink capacities. For certain P2P topologies, we show that routing along a linear number of trees per source can achieve the largest rate region that can be possibly obtained by intrasession and intersession network coding. This observation allows us to develop a simple multitree formulation for the problem. For the resulting nonstrictly concave optimization problem, we develop a Primal-dual distributed algorithm and prove its global convergence using our proposed sufficient conditions. These conditions are general and add understanding to the convergence of primal-dual algorithms under nonstrictly concave settings. We implement the proposed distributed algorithm in a peer-assisted multiparty conferencing system by utilizing only end-to-end delay measurements between P2P nodes. We demonstrate its superior performance through actual experiments on a LAN testbed and the Internet.

The bloom filter is a probabilistic data structure that provides a compact representation of a set of elements. To keep false positive probabilities low, the size of the bloom filter must be dimensioned a priori to be linear in the maximum number of keys inserted, with the linearity constant ranging typically from one to few bytes. A bloom filter is most commonly used as an in memory data structure, hence its size is limited by the availability of RAM space on the machine. As datasets have grown over time to Internet scale, so have the RAM space requirements of bloom filters. If sufficient RAM space is not available, we advocate that flash memory may serve as a suitable medium for storing bloom filters, since it is about one-tenth the cost of RAM per GB while still providing access times orders of magnitude faster than hard disk. We present BLOOMFLASH, a bloom filter designed for flash memory based storage, that provides a new dimension of trade off with bloom filter access times to reduce RAM space usage (and hence system cost). The simple design of a single flat bloom filter on flash suffers from many performance bottlenecks, including in-place bit updates that are inefficient on flash and multiple reads and random writes spread out across many flash pages for a single lookup or insert operation. To mitigate these performance bottlenecks, BLOOMFLASH leverages two key design innovations: (i) buffering bit updates in RAM and applying them in bulk to flash that helps to reduce random writes to flash, and (ii) a hierarchical bloom filter design consisting of component bloom filters, stored one per flash page, that helps to localize reads and writes on flash. We use two real-world data traces taken from representative bloom filter applications to drive and evaluate our design. BLOOMFLASH achieves bloom filter access times in the range of few tens of microseconds, thus allowing up to order of tens of thousands operations per sec.

Large scale data centers are enabling the new era of Internet cloud computing. The computing platform in such data centers consists of low-cost commodity servers that, in large numbers and with software support, match the performance and reliability of expensive enterprise-class servers of yesterday, at a fraction of the cost. The network interconnect within the data center, however, has not seen the same scale of commoditization or dropping price points. Today's data centers use expensive enterprise-class networking equipment and associated best-practices that were not designed for the requirements of Internet-scale data center services -- they severely limit server-to-server network capacity, create fragmented pools of servers that do not allow any service to run on any server, and have poor reliability and utilization. The commoditization and redesign of data center networks to meet cloud computing requirements is the next frontier of innovation in the data center.

We present SkimpyStash, a RAM space skimpy key-value store on flash-based storage, designed for high throughput, low latency server applications. The distinguishing feature of SkimpyStash is the design goal of extremely low RAM footprint at about 1 (± 0.5) byte per key-value pair, which is more aggressive than earlier designs. SkimpyStash uses a hash table directory in RAM to index key-value pairs stored in a log-structured manner on flash. To break the barrier of a flash pointer (say, 4 bytes) worth of RAM overhead per key, it "moves" most of the pointers that locate each key-value pair from RAM to flash itself. This is realized by (i) resolving hash table collisions using linear chaining, where multiple keys that resolve (collide) to the same hash table bucket are chained in a linked list, and (ii) storing the linked lists on flash itself with a pointer in each hash table bucket in RAM pointing to the beginning record of the chain on flash, hence incurring multiple flash reads per lookup. Two further techniques are used to improve performance: (iii) two-choice based load balancing to reduce wide variation in bucket sizes (hence, chain lengths and associated lookup times), and a bloom filter in each hash table directory slot in RAM to disambiguate the choice during lookup, and (iv) compaction procedure to pack bucket chain records contiguously onto flash pages so as to reduce flash reads during lookup. The average bucket size is the critical design parameter that serves as a powerful knob for making a continuum of tradeoffs between low RAM usage and low lookup latencies. Our evaluations on commodity server platforms with real-world data center applications show that SkimpyStash provides throughputs from few 10,000s to upwards of 100,000 get-set operations/sec.

Peer-to-peer (P2P) systems provide a scalable way to stream content to multiple receivers over the Internet. The maximum rate achievable by all receivers is the capacity of a P2P streaming session. We provide a taxonomy of sixteen problem formulations, depending on whether there is a single P2P session or there are multiple concurrent sessions, whether the given topology is a full mesh graph or an arbitrary graph, whether the number of peers a node can have is bounded or not, and whether there are nonreceiver relay nodes or not. In each formulation, computing P2P streaming capacity requires the computation of an optimal set of multicast trees, with an exponential complexity, except in three simplest formulations that have been recently solved with polynomial time algorithms. These solutions, however, do not extend to the other more general formulations. In this paper, we develop a family of constructive, polynomial-time algorithms that can compute P2P streaming capacity and the associated multicast trees, arbitrarily accurately for seven formulations, to a factor of 4-approximation for two formulations, and to a factor of log of the number of receivers for two formulations. The optimization problem is reformulated in each case so as to convert the combinatorial problem into a linear program with an exponential number of variables. The linear program is then solved using a primal-dual approach. The algorithms combine an outer loop of primal-dual update with an inner loop of smallest price tree construction, driven by the update of dual variables in the outer loop. We show that when the construction of smallest price tree can be carried out arbitrarily accurately in polynomial time, so can the computation of P2P streaming capacity. We also develop several efficient algorithms for smallest price tree construction. Using the developed algorithms, we investigate the impact of several factors on P2P streaming capacity using topologies derived from statistics of uplink capacities of Internet hosts.

We consider multi-rate peer-to-peer multiparty video conferencing applications, where different receivers in the same group can receive videos at different rates using, for example, scalable layered coding. The quality of video received by each receiver can be modeled as a concave utility function of the video bitrate. We study and address the unique challenges introduced by maximizing utility in the multi-rate setting as compared to the single-rate case. We first determine an optimal set of tree structures for routing multi-rate content using scalable layered coding. We then develop Primal and Primal-dual based distributed algorithms to maximize aggregate utility of all receivers in all groups by multi-tree routing and show their convergence. These algorithms can be easily implemented and deployed on today's Internet. We have built a prototype video conferencing system to show that this approach converges to optimal bitrates to improve user experience and offers automatic adaptation to network conditions and user preferences.

Two-phase routing, where traffic is first distributed to intermediate nodes before being routed to the final destination, has been recently proposed for handling widely fluctuating traffic without the need to adapt network routing to changing traffic. Preconfiguring the network in a traffic-independent manner using two-phase routing simplifies network operation considerably. In this paper, we extend this routing scheme by providing resiliency against link failures through end-to-end shared backup path restoration. We view this as important progress toward adding carrier-class reliability to the robustness of the scheme so as to facilitate its future deployment in Internet service provider (ISP) networks. In shared backup path restoration, each connection consists of a link-disjoint primary and backup path pair; two backup paths can share bandwidth on their common links if their primary paths are link-disjoint. We show that the optimization problem for maximum throughput two-phase routing with shared backup path restoration is NP-hard. Assuming an approximation oracle for a certain disjoint paths problem (called SBPR-DISJOINT-PATHS, which is also NP-hard) involving the dual variables of a path indexed linear programming formulation for the problem, we design a combinatorial algorithm with provable guarantees. We also provide heuristics for finding approximating solutions to the SBPR-DISJOINT-PATHS problem. We evaluate the throughput performance and number of intermediate nodes in two-phase routing for the above and other restoration mechanisms for two-phase routing on actual ISP topologies collected for the Rocketfuel project and three research network topologies.

Routing traffic subject to hose model constraints has been of much recent research interest. Two-phase routing has been proposed as a mechanism for routing traffic in the hose model. It has desirable properties in being able to statically preconfigure the transport network and in being able to handle constraints imposed by specialized service overlays. In this paper, we investigate whether the desirable properties of two-phase routing come with any resource overhead compared to: 1) direct source-destination path routing; and 2) optimal scheme among the class of all schemes that are allowed to even make the routing dynamically dependent on the traffic matrix. In the pursuit of this endeavor, we achieve several milestones. First, we develop a polynomial-size linear programming (LP) formulation for maximum throughput routing of hose traffic along direct source-destination paths. Second, we develop a polynomial-size LP formulation for maximum throughput two-phase routing of hose traffic for a generalized version of the scheme proposed in our previous work. Third, we develop a polynomial-size LP formulation for minimum-cost two-phase routing of hose traffic for the generalized version of the scheme. We also give a second (simpler) LP formulation and fast combinatorial algorithm for this problem using an upper bound on the end-to-end traffic demand. Fourth, we prove that the throughput (and cost) of two-phase routing is within a factor of 2 of that of the optimal scheme. Using the polynomial-size LP formulations developed, we compare the throughput of two-phase routing to that of direct source-destination path routing and optimal scheme on actual Internet service provider topologies collected for the Rocketfuel project and three research network topologies. The throughput of two-phase routing matches that of direct source-destination path routing and is close to that of the optimal scheme on all evaluated topologies. We conclude that two-phase routing achieves its robustness to traffic variation without imposing any appreciable additional resource requirements over previous approaches.

There has been a dramatic increase in interactive cloud based software applications. Compared to classical real-time media applications (voice over IP (VoIP)/conferencing) and non real-time file delivery, these interactive software applications have unique characteristics: 1) they are delay sensitive yet demand in order and reliable data delivery, and 2) the traffic is usually bursty. Traditional window based congestion control does not work well for interactive applications because the bursty arrival of data leads to bursty network traffic, which causes additional queuing delay and packet loss in the network which reduces its delay performance. In this paper, we propose a new hybrid window plus rate based congestion control technique. This algorithm improves the delay performance of interactive applications by preventing congestion induced loss and minimizing queuing delay while still fully utilizing network capacity and maintaining fairness across multiple flows.

Two of the fundamental problems in peer-to-peer (P2P) streaming are as follows: what is the maximum streaming rate that can be sustained for all receivers, and what peering algorithms can achieve close to this maximum? These problems of computing and approaching the P2P streaming capacity are often challenging because of the constraints imposed on overlay topology. In this paper, we focus on the limit of P2P streaming rate under node degree bound, i.e., the number of connections a node can maintain is upper bounded. We first show that the streaming capacity problem under node degree bound is NP Complete in general. Then, for the case of node out-degree bound, through the construction of a “Bubble algorithm”, we show that the streaming capacity is at least half of that of a much less restrictive and previously studied case, where we bound the node degree in each streaming tree but not the degree across all trees. Then, for the case of node total-degree bound, we develop a “Cluster-Tree algorithm” that provides probabilistic guarantee of achieving a rate close to the maximum rate achieved under no degree bound constraint, when the node degree bound is logarithmic in network size. The effectiveness of these algorithms in approaching the capacity limit is demonstrated in simulations using uplink bandwidth statistics of Internet hosts. Both analysis and numerical experiments show that peering in a locally dense and globally sparse manner achieves near-optimal streaming rate if the degree bound is at least logarithmic in network size.

Cloud data centers host diverse applications, mixing workloads that require small predictable latency with others requiring large sustained throughput. In this environment, today's state-of-the-art TCP protocol falls short. We present measurements of a 6000 server production cluster and reveal impairments that lead to high application latencies, rooted in TCP's demands on the limited buffer space available in data center switches. For example, bandwidth hungry "background" flows build up queues at the switches, and thus impact the performance of latency sensitive "foreground" traffic.

We present FlashStore, a high throughput persistent key-value store, that uses flash memory as a non-volatile cache between RAM and hard disk. FlashStore is designed to store the working set of key-value pairs on flash and use one flash read per key lookup. As the working set changes over time, space is made for the current working set by destaging recently unused key-value pairs to hard disk and recycling pages in the flash store. FlashStore organizes key-value pairs in a log-structure on flash to exploit faster sequential write performance. It uses an in-memory hash table to index them, with hash collisions resolved by a variant of cuckoo hashing. The in-memory hash table stores compact key signatures instead of full keys so as to strike tradeoffs between RAM usage and false flash read operations. FlashStore can be used as a high throughput persistent key-value storage layer for a broad range of server class applications. We compare FlashStore with BerkeleyDB, an embedded key-value store application, running on hard disk and flash separately, so as to bring out the performance gain of FlashStore in not only using flash as a cache above hard disk but also in its use of flash aware algorithms. We use real-world data traces from two data center applications, namely, Xbox LIVE Primetime online multi-player game and inline storage deduplication, to drive and evaluate the design of FlashStore on traditional and low power server platforms. FlashStore outperforms BerkeleyDB by up to 60x on throughput (ops/sec), up to 50x on energy efficiency (ops/Joule), and up to 85x on cost efficiency (ops/sec/dollar) on the evaluated datasets.

A recent approach-COPE, presented by Katti (Proc. ACM SIGCOMM 2006, pp. 243-254)-for improving the throughput of unicast traffic in wireless multihop networks exploits the broadcast nature of the wireless medium through opportunistic network coding. In this paper, we analyze throughput improvements obtained by COPE-type network coding in wireless networks from a theoretical perspective. We make two key contributions. First, we obtain a theoretical formulation for computing the throughput of network coding on any wireless network topology and any pattern of concurrent unicast traffic sessions. Second, we advocate that routing be made aware of network coding opportunities rather than, as in COPE, being oblivious to it. More importantly, our model considers the tradeoff between routing flows close to each other for utilizing coding opportunities and away from each other for avoiding wireless interference. Our theoretical formulation provides a method for computing source-destination routes and utilizing the best coding opportunities from available ones so as to maximize the throughput. We handle scheduling of broadcast transmissions subject to wireless transmit/receive diversity and link interference in our optimization framework. Using our formulations, we compare the performance of traditional unicast routing and network coding with coding-oblivious and coding-aware routing on a variety of mesh network topologies, including some derived from contemporary mesh network testbeds. Our evaluations show that a route selection strategy that is aware of network coding opportunities leads to higher end-to-end throughput when compared to coding-oblivious routing strategies.

We consider multi-rate peer-to-peer multi-party conferencing applications, where different receivers in the same group can receive videos at different rates using, for example, scalable layered coding. The quality of video received by each receiver can be modeled as a concave utility function of the video rate. We study and address the unique challenges introduced by multi-rate setting as compared to the single-rate case. We first determine an optimal set of tree structures for routing multi-rate content using scalable layered coding. We then develop primal and primal-dual based distributed algorithms to maximize aggregate utility of all receivers in all groups by multi-tree routing and show their convergence. These algorithms can be easily implemented and deployed on today's Internet. We have built a prototype video conferencing system to show that this approach offers low end-to-end delay, low complexity and high throughput, along with automatic adaptation to network conditions and user preferences.

Two-phase routing, where traffic is first distributed to intermediate nodes before being routed to the final destination, has been proposed for handling widely fluctuating traffic without the need to adapt network routing to changing traffic. Pre-configuring the network in a traffic independent manner using two-phase routing simplifies network operation considerably. In this paper, we extend this routing scheme by providing resiliency against link failures through shared backup path restoration. We view this as important progress towards adding carrier-class reliability to the robustness of the scheme so as to facilitate its future deployment in Internet service provider (ISP) networks. In shared backup path restoration, each connection consists of a link-disjoint primary and backup path pair - two backup paths can share bandwidth on their common links if their primary paths are link disjoint. We show that the optimization problem for maximum throughput two-phase routing with shared backup path restoration is NP-hard. Assuming an approximation oracle for a certain disjoint paths problem (called SBPR-DISJOINT-PATHS, which is also NP-hard) involving the dual variables of a path indexed linear programming formulation for the problem, we design a combinatorial algorithm with provable guarantees. We also provide heuristics for finding approximating solutions to the SBPR-DISJOINT-PATHS problem. We evaluate the throughput performance and number of intermediate nodes in two-phase routing for the above and other restoration mechanisms for two-phase routing on actual ISP topologies collected for the Rocketfuel project.

We explore the nature of traffic in data centers, designed to support the mining of massive data sets. We instrument the servers to collect socket-level logs, with negligible performance impact. In a 1500 server operational cluster, we thus amass roughly a petabyte of measurements over two months, from which we obtain and report detailed views of traffic and congestion conditions and patterns. We further consider whether traffic matrices in the cluster might be obtained instead via tomographic inference from coarser-grained counter data.

The capacity of wireless channels has been studied extensively by the information theory community over the years. There have been several efforts to extend this theory to multi-hop wireless networks. One approach to estimating the capacity of multihop wireless networks is to determine asymptotically how the capacity scales as the number of nodes in the network increases. In these models, the traffic is typically assumed to be uniform. Another approach assumes that node locations and channel conditions are known and the question is to determine whether a given traffic matrix can be routed on the wireless network. This usually involves solving jointly, routing, scheduling and power control problems to achieve the given traffic matrix. In practice, it is quite difficult to estimate the traffic matrix and further, the traffic matrix typically changes over time. In this paper, we are given the location of the nodes and the inter-node channel parameters. Instead of being provided a traffic matrix, we are provided with only the total amount of traffic that can originate and terminate at each node in the network. The objective is to determine if there exists a joint routing and scheduling policy that can handle any traffic matrix that satisfies these ingress/egress constraints. We derive necessary and sufficiency conditions for the problem for both the directional and omni-directional antenna cases. We solve the joint routing and scheduling problem for all traffic matrices that satisfy the ingress-egress constraints.

To be agile and cost effective, data centers should allow dynamic resource allocation across large server pools. In particular, the data center network should enable any server to be assigned to any service. To meet these goals, we present VL2, a practical network architecture that scales to support huge data centers with uniform high capacity between servers, performance isolation between services, and Ethernet layer-2 semantics. VL2 uses (1) flat addressing to allow service instances to be placed anywhere in the network, (2) Valiant Load Balancing to spread traffic uniformly across network paths, and (3) end-system based address resolution to scale to large server pools, without introducing complexity to the network control plane. VL2's design is driven by detailed measurements of traffic and fault data from a large operational cloud service provider. VL2's implementation leverages proven network technologies, already available at low cost in high-speed hardware implementations, to build a scalable and reliable network architecture. As a result, VL2 networks can be deployed today, and we have built a working prototype. We evaluate the merits of the VL2 design using measurement, analysis, and experiments. Our VL2 prototype shuffles 2.7 TB of data among 75 servers in 395 seconds - sustaining a rate that is 94% of the maximum possible.

Traditionally, the channelization structure in IEEE 802.11-based wireless LANs has been fixed: Each access point (AP) is assigned one channel and all channels are equally wide. In contrast, it has recently been shown that even on commodity hardware, the channel-width can be adapted dynamically purely in software. Leveraging this capability, we study the use of dynamic-width channels, where every AP adaptively adjusts not only its center-frequency, but also its channel-width to match its traffic load. This gives raise to a novel optimization problem that differs from previously studied channel assignment problems. We propose efficient spectrum-distribution algorithms and evaluate their effectiveness through analysis and simulations using real-world traces. Our results indicate that by allocating more spectrum to highly-loaded APs, the overall spectrum-utilization can be substantially improved and the notorious load-balancing problem in WLANs can be solved naturally.

The continued explosion of new virus/worm and other security attacks in the Internet and the tremendous propagation speed of self-propagating attacks has led to network security being considered as a design criterion rather than an afterthought. Attack prevention, detection, and mitigation mechanisms can be broadly classified as network based or host based. Network based security mechanisms have been shown to be much more effective than host based mechanisms, primarily because of the former's ability in identifying attack traffic that is further upstream from the victim and closer to the attack source. In the context of network based mechanisms, we consider a flexible overlay network of security systems running on top of programmable (active) routers. In such an architecture, security services can be dynamically distributed across the network, which provides flexibility for load-balancing of services across nodes and addition of new services over time. Such network based mechanisms inevitably decrease network performance as all packets are analyzed for malicious content before being forwarded. In this paper, we consider traffic routing, placement of active router nodes, and distribution of security services across such nodes so as to optimize certain objectives, including (i) minimize the total number of active router deployed nodes, and (ii) minimize the maximum utilization of any router node in the network. Based on an emulation in the Deter testbed we show the benefit of the presented approach.

We consider multi-source multicast communication scenarios in which each node has an aggregate outbound traffic capacity and can directly communicate with any other node. This is motivated by peer-to-peer (P2P) information dissemination applications on the Internet in which the uplink capacity of nodes is usually the bottleneck, being several times smaller than the downlink capacity. We also allow the communication in a group to be helped by non-receiver nodes (with respect to that group) as relays. Extending an earlier result for the single source case, we show that when coding is not allowed across sources, routing is optimal. Also, as a rather surprising discovery, we show that when all groups have pairwise identical or disjoint receivers, routing is optimal even when coding across sources is allowed. Moreover, routing along a linear number of trees per source is sufficient to achieve this. The latter scenario is common in multiparty conferencing systems, hence our results have interesting practical applications in the design of infrastructure-less P2P multiparty conferencing systems.

In this paper, we study the problem of utility maximization in P2P systems, in which aggregate application-specific utilities are maximized by running distributed algorithms on P2P nodes, which are constrained by their uplink capacities. This may be understood as extending Kelly's seminal framework from single-path unicast over general topology to multi-path multicast over P2P topology, with network coding allowed. For certain classes of popular P2P topologies, we show that routing along a linear number of trees per source can achieve the largest rate region that can be possibly obtained by (multi-source) network coding. This simplification result allows us to develop a new multi-tree routing formulation for the problem. Despite of the negative results in literature on applying Primal-dual algorithms to maximize utility under multi-path settings, we have been able to develop a Primal-dual distributed algorithm to maximize the aggregate utility under the multi-path routing environments. Utilizing our proposed sufficient condition, we show global exponential convergence of the Primal-dual algorithm to the optimal solution under different P2P communication scenarios we study. The algorithm can be implemented by utilizing only end-to-end delay measurements between P2P nodes; hence, it can be readily deployed on today's Internet. To support this claim, we have implemented the Primal-dual algorithm for use in a peer-assisted multi-party conferencing system and evaluated its performance through actual experiments on a LAN testbed and the Internet.

Local network coding is growing in prominence as a technique to facilitate greater capacity utilization in multi-hop wireless networks. A specific objective of such local network coding techniques has been to explicitly minimize the total number of transmissions needed to carry packets across each wireless hop. While such a strategy is certainly useful, we argue that in lossy wireless environments, a better use of local network coding is to provide higher levels of redundancy even at the cost of increasing the number of transmissions required to communicate the same information. In this paper we show that the design space for effective redundancy in local network coding is quite large, which makes optimal formulations of the problem hard to realize in practice. We present a detailed exploration of this design space and propose a suite of algorithms, called CLONE, that can lead to further throughput gains in multi-hop wireless scenarios. Through careful analysis, simulations, and detailed implementation on a real testbed, we show that some of our simplest CLONE algorithms can be efficiently implemented in today's wireless hardware to provide a factor of two improvement in throughput for example scenarios, while other, more effective, CLONE algorithms require additional advances in hardware processing speeds to be deployable in practice.

A recent approach, COPE, for improving the throughput of unicast traffic in wireless multi-hop networks exploits the broadcast nature of the wireless medium through opportunistic network coding. In this paper, we analyze throughput improvements obtained by COPE-type network coding in wireless networks from a theoretical perspective. We make two key contributions. First, we obtain a theoretical formulation for computing the throughput of network coding on any wireless network topology and any pattern of concurrent unicast traffic sessions. Second, we advocate that routing be made aware of network coding opportunities rather than, as in COPE, being oblivious to it. More importantly, our work studies the tradeoff between routing flows "close to each other" for utilizing coding opportunities and "away from each other" for avoiding wireless interference. Our theoretical formulation provides a method for computing source-destination routes and utilizing the best coding opportunities from available ones so as to maximize the throughput. We handle scheduling of broadcast transmissions subject to wireless transmit/receive diversity and link interference in our optimization framework. Using our formulations, we compare the performance of traditional unicast routing and network coding with coding-oblivious and coding-aware routing on a variety of mesh network topologies, including some derived from contemporary mesh network testbeds. Our evaluations show that a route selection strategy that is aware of network coding opportunities leads to higher end-to-end throughput when compared to coding-oblivious routing strategies.

We consider the problem of joint routing, scheduling and transmission power assignment in multi-hop wireless mesh networks with unknown traffic. We assume the traffic is unknown, but the traffic matrix, which specifies the traffic load between every source-destination pair in the network, always lies inside a polytope defined by hose model constraints. The objective is to minimize the maximum of the total transmission power in the network over all traffic matrices in a given polytope. We propose efficient algorithms that compute a two-phase routing, schedule and power assignment, and prove the solution to be 3-approximation with respect to an optimal two-phase routing, scheduling and power assignment. We show via extensive simulations that the proposed algorithm has good performance at its worst operating traffic compared to an algorithm optimized for that traffic.

Abstract — We consider the realization of traffic-oblivious routing in IP-over-Optical networks where routers are interconnected over a switched optical backbone, also called IP-over-OTN (Optical Transport Network). The traffic-oblivious routing we consider is a scheme where incoming traffic is first distributed in a preset manner to a set of intermediate nodes. The traffic is then routed from the intermediate nodes to the final destination. This splitting of the routing into two-phases simplifies network configuration significantly [8], [17]. In implementing this scheme, the first and second phase paths are realized at the optical layer with router packet grooming at a single intermediate node only. Studies like [10] indicate that IP routers are 200 times more unreliable than traditional carrier-grade switches and average 1219 minutes of down time per year. Given this unreliability of routers, we consider how two-phase routing in IP-over-OTN can be made resilient against router node failures. We propose two different schemes for provisioning the optical layer to handle router node failures – one that is failure node independent and static, and the other that is failure node dependent and dynamic. We develop linear programming formulations for both schemes and a fast combinatorial algorithm for the second scheme so as to maximize network throughput. In each case, we determine (i) the optimal distribution of traffic to various intermediate routers for both normal (no-failure) and failure conditions, and (ii) provisioning of optical layer circuits to provide the needed inter-router links. We evaluate the performance of the two router failure protection schemes (in terms of throughput) and compare it with that of unprotected routing. For our experiments, we use actual ISP network topologies collected for the Rocketfuel project. I.

Two-phase routing, where traffic is first distributed to intermediate nodes before being routed to the final destination, has been recently proposed for handling widely fluctuating traffic without the need to adapt network routing to changing traffic. Pre-configuring the network in a traffic independent manner using two-phase routing simplifies network operation considerably. In this paper, we extend this routing scheme by providing resiliency against link failures through two different fast restoration mechanisms - local (link/span) based and end-to-end (path) based. We view this as important progress towards adding carrier-class reliability to the robustness of the scheme so as to facilitate its future deployment in Internet service provider (ISP) networks. The main contribution of the paper is the development of fast combinatorial algorithms for routing under the scheme with link and path restoration mechanisms so as to minimize the maximum utilization of any link in the network, or equivalently, maximize the throughput. The algorithms developed are fully polynomial time approximation schemes (FPTAS) - for any given epsi > 0, an FPTAS guarantees a solution that is within a (1 + epsi) -factor of the optimum and runs in time polynomial in the input size and 1/epsi. To the best of our knowledge, this is the first work in the literature that considers making the scheme resilient to link failures through pre-provisioned fast restoration mechanisms. We evaluate the performance of link and path restoration (in terms of throughput) and compare it with that of unprotected routing. For our experiments, we use actual ISP network topologies collected for the Rocketfuel project.

The emergence of new applications on the Internet like voice-over-IP, peer-to-peer, and video-on-demand has created highly dynamic and changing traffic patterns. In order to route such traffic with Quality-of-Service (QoS) guarantees without requiring detection of traffic changes in real-time or reconfiguring the network in response to it, we consider a routing and bandwidth allocation scheme that allows preconfiguration of the network such that all traffic patterns permissible within the network’s natural ingress-egress capacity constraints can be handled in a capacity efficient manner. The scheme routes traffic in two phases. In the first phase, incoming traffic is sent from the source to a set of intermediate nodes and then, in the second phase, from the intermediate nodes to the final destination. The traffic in the first phase is distributed to the intermediate nodes in predetermined proportions that depend on the intermediate nodes. In this paper, we develop linear programming formulations and a fast combinatorial algorithm for routing under the scheme so as to maximize throughput (or, minimize maximum link utilization). We compare the throughput performance of the scheme with that of the optimal scheme among the class of all schemes that are allowed to even make the routing dependent on the traffic matrix. For our evaluations, we use actual Internet Service Provider topologies collected for the Rocketfuel project. We also bring out the versatility of the scheme in not only handling widely fluctuating traffic but also accommodating applicability to several widely differing networking scenarios, including (i) economical Virtual Private Networks (VPNs), (ii) supporting indirection in specialized service overlay models like Internet Indirection Infrastructure (i3), (iii) adding QoS guarantees to services that require routing through a network-based middlebox, and (iv) reducing IP layer transit traffic and handling extreme traffic variability in IP-over-Optical networks without dynamic reconfiguration of the optical layer. The two desirable properties of supporting indirection in specialized service overlay models and static optical layer provisioning in IP-over-Optical networks are not present in other approaches for routing variable traffic, such as direct source-destination routing along fixed paths.

We consider the realization of traffic-oblivious rout- ing in IP-over-Optical networks where routers are interconnected over a switched optical backbone. The traffic-oblivious routing we consider is a scheme where incoming traffic is first distributed in a preset manner to a set of intermediate nodes. The traffic is then routed from the intermediate nodes to the final destination. This splitting of the routing into two phases simplifies network configuration significantly. In implementing this scheme, the first and second phase paths are realized at the optical layer with router packet grooming at a single intermediate node only. Stud- ies like (13) indicate that IP routers are 200 times more unreliable than traditional carrier-grade switches and average 1219 minutes of down time per year. Given this unreliability of routers, we consider how two-phase routing in IP-over-Optical networks can be made resilient against router node failures. We propose two different schemes for provisioning the optical layer to handle router node failures - one that is failure node independent and static, and the other that is failure node dependent and dynamic. We develop linear programming formulations for both schemes and a fast combinatorial algorithm for the second scheme so as to maximize network throughput. In each case, we determine (i) the optimal distribution of traffic to various intermediate routers for both normal (no-failure) and failure conditions, and (ii) provisioning of optical layer circuits to provide the needed inter-router links. We evaluate the performance of the two router failure protection schemes (in terms of throughput) and compare it with that of unprotected routing.

A computer-implemented method of computing throughput of a data-routing scheme for a network of nodes interconnected by links and having at least one ingress point and at least one egress point. The method includes: deriving a polynomial-size linear program from a combination of a first linear program and a second linear program and solving the polynomial-size linear program. The first linear program has infinite constraints and minimizes maximum-link utilization of a link in a path between the ingress point and the egress point. The second linear program determines whether any constraint of the first linear program is violated.

An important feature of MPLS networks is local restoration where detour paths are set-up a priori. The detour is such that failed links or nodes can be bypassed locally from the first node that is upstream from the failures. This local bypass activation from the first detection point for failures permits much faster recovery than end-to-end path based mechanisms that require failure information to propagate to the network edges. However, local restoration of bandwidth guaranteed connections can be expensive in the additional network capacity needed. Hence, it is important to minimize and share restoration capacity. The problem of routing with local restoration requirements has been studied previously in a dynamic on-line setting. However, there are no satisfactory algorithms for the problem of pre-provisioning fast restorable connections when the aggregate traffic demands are known (as would be the case when a set of routers are to be interconnected over an optical network or for pre-provisioned ATM over MPLS overlays). The contribution of this paper is a fast combinatorial approximation algorithm for maximizing throughput when the routed traffic is required to be locally restorable. To the best of our knowledge, this is the first combinatorial algorithm for the problem with a performance guarantee. Our algorithm is a fully polynomial time approximation scheme (FPTAS), i.e., for any given /spl epsi/>0, it guarantees (1+/spl epsi/)-factor closeness to the optimal solution, and runs in time polynomial in the network size and 1//spl epsi/. We compare the throughput of locally restorable routing with that of unprotected routing and 1+1-dedicated path protection on representative ISP topologies.

With the rapid increase in the frequency of worm attacks, there has been significant interest in developing network based mechanisms that slow or contain worm propagation. One suggested network-based approach is the use of special content filtering nodes that examine the complete content of each packet and block traffic that contain strings matching a pre-specified set of worm signatures. To be effective, containment systems need to have fast reaction times (content filtering with the appropriate signatures must be activated very soon after the start of an attack) and need to be comprehensive in the sense that every packet routed through the network must be examined at least once. Since network-based content filtering is expensive, it is desirable to make the best use of deployable content filtering capability. This requires intelligent placement of the content filtering nodes in the network and use of appropriate network routing to maximize the carried traffic. In this paper, we study the impact of the content filtering requirement on network capacity. First, we develop an intelligent heuristic for deployment of content filtering nodes in the network. Next, given a set of deployed content filtering nodes, we develop a fully polynomial time approximation scheme (FP-TAS) that maximizes the traffic carried by the network subject to the constraint that all traffic passes through a content filtering node at least once. Simulation studies using the developed schemes show that for large networks, most of the traffic can be examined even when only 10% of the network nodes are content filtering capable.

While deploying the next generation of optical networks with a mesh topology, telecommunications carriers are being confronted with a choice between wavelength switches that can switch traffic at SONET STS-48 (2.5 Gbps) granularity and subwavelength grooming capable switches that can switch at STS-1 (51 Mbps) granularity. The former consumes high fragmented/unused capacity to support low capacity end-to-end circuits using high capacity STS-48 channels (given current subwavelength traffic levels) while the latter may require relatively complicated hardware design that decreases switch scalability. Two-tier network architectures combine the benefits of STS-1 and STS-48 switches by using an upper tier of STS-48 switches for routing and restoration and a lower tier of STS-1 switches for grooming efficiency. A partial two-tier architecture, where STS-1 switches are restricted to a subset of the network nodes, has been shown in to closely match the grooming benefits of a full lower STS-1 tier. We furnish a detailed upper hound analysis of how the fragmented/unused capacity in STS-48 channels (fragmentation loss) varies with the grooming capability of a network for arbitrary traffic scenarios. We show that the upper bounds derived in this paper are in agreement with results obtained using efficient routing and grooming algorithms discussed. Because the bounds obtained do not make any assumptions about traffic and are easy to compute, they are suited for incorporation into a network engineering tool for deciding strategic placement of STS-1 switches in partial two-tier networks. Our work is not biased towards any particular network architecture but aims to analyze the grooming efficiency of two-tier networks.

Fast restoration is an important feature of both MPLS and optical networks. The main mechanism for achieving fast restoration is by locally routing around failures using pre-setup detour paths. Signaling and routing protocol extensions to implement this local bypass ability are currently being standardized. To make use of this ability, dynamic schemes that jointly route primary paths and all link detours for links used by the primary paths have been previously proposed. These schemes also permit sharing of reserved restoration capacity for achieving efficiency. However, this joint computation places a significantly larger computational load on the network elements than that imposed by the shortest path computation variants typically used for unprotected network connection routing. We propose a new scheme that is operationally much simpler, shares capacity used for restoration, and permits the network to route the primary paths in a manner that is oblivious to restoration needs. Restoration of all carried traffic is guaranteed by a new link capacity partitioning scheme that maximizes the working capacity of the network without requiring any knowledge of the traffic that will be imposed on the network. Being traffic independent for a priori link capacity partitioning and being oblivious to restoration needs for on-line network routing makes this scheme operationally simple and desirable in the sense of placing no additional routing load on the constrained computing resources at the network nodes. To compute the link capacity partitions, we develop a fast combinatorial algorithm that uses only iterative shortest path computations, and is a fully polynomial time approximation scheme (FPTAS), i.e., it achieves a (1 + /spl epsi/)-factor approximation for any /spl epsi/> 0 and runs in time polynomial in the input size and 1//spl epsi/.The approximation scheme also allows link detour paths to be hop constrained if needed so as to bound restoration latency in optical networks.

We present a new algorithm for online routing of bandwidth-guaranteed multicasts where routing requests arrive one by one without any prior knowledge of future requests. A multicast routing request consists of a source, a set of receivers, and a bandwidth requirement. Two multicast applications of interest are routing of point-to-multipoint label-switched paths in multiprotocol label switched (MPLS) networks, and the provision of bandwidth-guaranteed virtual private network (VPN) services under the "hose" service model. Without prior knowledge of multicast requests, offline multicast routing algorithms cannot be used. Online algorithms are needed to handle requests arriving one by one and to satisfy as many potential future demands as possible. Our new online algorithm is based on the idea that a newly routed multicast must follow a route that does not interfere too much with network paths that may be critical to satisfy future demands. We develop a multicast tree selection heuristic based on the idea of deferred loading of certain critical links. The algorithm identifies them as links that, if heavily loaded, would make it impossible to satisfy future demands between certain ingress-egress pairs. The algorithm uses link-state information and some auxiliary capacity information for multicast tree selection and is amenable to distributed implementation. Unlike previous algorithms, our algorithm exploits any available knowledge of the network ingress-egress points of potential future demands, even though the demands themselves are unknown. It performs very well.

We discuss enhancements to the OSPF (open shortest path first) protocol for routing and topology discovery in optical mesh networks. OSPF's opaque LSA (link state advertisement) mechanism is used to extend OSPF to disseminate optical resource related information through optical LSAs. Standard link-state database flooding mechanisms are used for distribution of optical LSAs. Each optical LSA carries optical resource information pertaining to a single optical link bundle between two adjacent OXCs (optical cross connects), allowing for fine granularity changes in topology to be incorporated in path computation algorithms. OSPF packets are carried over a single IP control channel between adjacent OXCs. We analyze the performance of OSPF with optical extensions. Specifically, we compute control channel bandwidth used due to LSA updates. We also estimate the amount of memory required to store the LSA database. Finally, we study CPU usage for computing primary and backup lightpaths. Our analysis shows that the control channel bandwidth usage, memory requirement, and CPU usage are small enough to not be limiting factors for designing optical networks with single OSPF areas consisting of a large number (more than 500) of OXCs.

In an optical mesh network, backup channels are shared between multiple lightpaths to reduce restoration capacity overhead. The sharability of channels is usually constrained by the mandate to provide 100% recovery of all lightpaths affected by any single event failure in the network. This paper proposes a pool based channel reservation scheme that is optimal when the set of primary and backup paths (specified at link level without channel allocation) is given. In the online case, our simulations on representative network topologies show that this method improves over the existing (more restrictive) method of allocating shared backup channels using primary path diversity.

A mesh-restored lightpath in an optical network has a primary route and a diversely routed backup route. The wavelength channels on the primary route of a mesh-restored lightpath are dedicated for that lightpath whereas the wavelength channels on the backup route are shared among different mesh-restored lightpaths. Wavelength channels are shared in a way that ensures restoration of all lightpaths affected by any single link failure. In the centralized scenario, complete knowledge of the network state allows determination of the sharability of a backup channel during path computation. This information is not available in the distributed scenario. Use of 1+1 routing algorithms for mesh-restored lightpaths leads to inefficient capacity sharing. We propose distributed routing techniques to decrease the capacity efficiency gap between centralized routing and 1+1 routing of mesh-restored lightpaths. The algorithm uses information about the number of available and (shared) backup channels in a link, which can be disseminated through traffic engineering extensions to OSPF. A sharing database at each OXC maintains information about the lightpaths whose primary or backup paths traverse that OXC. The approach involves distributed determination of the sharability of a link on the backup path during path signaling using the sharing database at each OXC on the backup path. This, combined with a retry scheme facilitated by crankback routing extensions to CR-LDP/RSVP-TE to reduce lightpath blocking, leads to capacity efficient distributed routing of mesh-restored lightpaths.

This paper presents a new algorithm for on-line routing of bandwidth-guaranteed multicasts where routing requests arrive one-by-one without there being any a priori knowledge of future requests. A multicast routing request consists of a source s, a set of receivers R, and a bandwidth requirement b. This multicast routing problem arises in many contexts. Two applications of interest are routing of point-to-multipoint label-switched paths in Multi-Protocol Label Switched (MPLS) networks, and the provision of bandwidth guaranteed Virtual Private Network (VPN) services under the “hose” service model [17]. Offline multicast routing algorithms cannot be used since they require a priori knowledge of all multicast requests that are to be routed. Instead, on-line algorithms that handle requests arriving one-by-one and that satisfy as many potential future demands as possible are needed. The newly developed algorithm is an on-line algorithm and is based on the idea that a newly routed multicast must follow a route that does not “interfere too much” with network paths that may be critical to satisfy future demands. We develop a multicast tree selection heuristic that is based on the idea of deferred loading of certain “critical” links. These critical links are identified by the algorithm as links that, if heavily loaded, would make it impossible to satisfy future demands between certain ingress-egress pairs. The presented algorithm uses link-state information and some auxilliary capacity information for multicast tree selection and is amenable to distributed implementation. Unlike previous algorithms, the proposed algorithm exploits any available knowledge of the network ingress-egress points of potential future demands even though the demands themselves are unknown and performs very well.