This work addresses the problem of delay-sensitive job scheduling in cloud computing systems that offer two compute options: (i) low-cost, high-demand spot servers and (ii) high-cost on-demand servers. While prior research has focused on scheduling a single job, we consider a more practical scenario where a continuous stream of jobs, categorized into n different classes, must be managed. Each class i is characterized by an on-demand cost ki, an arrival rate λi, and an average delay constraint δi. With Poisson job arrivals and spot server availability modeled as an exponential service process, we optimize two key aspects: (i) the wait-time distribution for each job class and (ii) the precedence order for processing classes in case of scheduling conflicts. By modeling the system as a Markov chain, we formulate constrained optimization problems for two cases: (i) equal treatment of all job classes and (ii) priority-based scheduling, the latter introducing a combinatorial challenge. We propose algorithms to determine optimal wait-time distributions in both cases and demonstrate through numerical experiments that precedence-order optimization significantly improves performance, especially when delay constraints are not overly strict.

Traditional data center architectures, such as Clos-based topologies, can sometimes encounter challenges with scalability and latency. The Direct Interconnect Data Center (DIDC) architecture offers a solution to these issues by enabling direct, low-latency MEMS-based optical connections between servers. This architecture is gaining popularity among web scalers, particularly in data centers that handle low-latency workloads. We introduce a novel machine learning-based algorithm, JIRO, for optimal traffic management in DIDC, considering the unique constraints of this architecture. During the development of this algorithm, we created new techniques for handling integer constraints within the Pytorch gradient descent framework, which can also be applied to other combinatorial optimization problems. Through extensive experiments and comparisons to lower bounds, we demonstrate that JIRO offers performance guarantees for multiple traffic patterns without significant over-provisioning.

The convergence of Software-Defined Networking (SDN) and Network Function Virtualization (NFV) has transformed wide area network operations. A critical challenge in these networks is the strategic deployment of Virtual Network Functions (VNFs) to optimize performance, resource utilization, and cost, amidst varying and unpredictable traffic patterns. Traditional methods often assume a single, static traffic pattern, but this approach is impractical due to the dynamic nature of network traffic. This paper presents a robust machine learningbased approach (PLANAR) for VNF placement and routing that accommodates multiple traffic patterns, providing worst-case performance guarantees. Our gradient descent-based stochastic optimization algorithm efficiently scales to handle hundreds of traffic patterns, significantly enhancing network resilience and resource management. The technique is effective and scalable and works well on a wide variety of network topologies.

This paper presents a novel approach to telemetry-based routing, aiming to minimize network congestion using multiple link load measurements collected at different points in time at a centralized management system. The objective is to determine a fixed routing policy that optimizes network performance by minimizing the maximum link utilization for any traffic matrix that could have generated any link load measurement. The key idea is to develop a routing mechanism that has the flexibility to handle a wide variety of traffic conditions without reconfiguration. We use a routing mechanism called deflection routing and develop a machine learning based gradient algorithm (LASER) to compute the deflection routing parameters. We use a combination of variable transformation and Lagrangian based techniques to transform the parameter optimization problem into an unconstrained loss minimization problem which is solved using a structured neural network in the PyTorch framework.

Oblivious routing of network traffic uses predetermined paths that do not change with changing traffic patterns. It has the benefit of using a fixed network configuration while robustly handling a range of varying and unpredictable traffic. Theoretical advances have shown that the benefits of oblivious routing are achievable without compromising much capacity efficiency. For oblivious routing, we only assume knowledge of the ingress/egress capacities of the edge nodes through which traffic enters or leaves the network. All traffic patterns possible subject to the ingress/egress capacity constraints (also known as the hose constraints) are permissible and are to be handled using oblivious routing. We use the widely deployed segment routing method for route control. Furthermore, for ease of deployment and to not deviate too much from conventional shortest path routing, we restrict paths to be 2-segment paths (the composition of two shortest path routed segments). We solve the 2-segment oblivious routing problem for all permissible traffic matrices (which can be infinitely-many). We develop a new adversarial and machine-learning driven approach that uses an iterative gradient descent method to solve the routing problem with worst-case performance guarantees. Additionally, the parallelism involved in descent methods allows this method to scale well with the network size making it amenable for use in practice.

In the new industrial Internet, a wide variety of industrial applications are expected to rely on high-performance data communication between a multitude of sensors and actuators that are deployed on a large scale. Publish-subscribe-based communication model is well-suited to handle such large-scale data gathering and dissemination among data sources and sinks. To support publish-subscribe-based data delivery, the newly standardized Segmented Routing over IPv6 (SRv6) can provide non-disruptive network programming primitives for building and maintaining network-efficient, shareable data distribution trees within the network. We study optimal algorithms for setting up different types of multicasting in the SRv6-capable network. In particular, we show, both theoretically and experimentally, that splitting multicast streams into multiple sub-streams, as well as using end-to-end application-layer coding without any network participation can provide significant benefits in terms of multicast throughput compared to traditional single stream multicasting.

Modern data centers are witnessing fast-growing east-west traffic on their network infrastructure due to the highly distributed data center applications. Motivated by the heterogeneity of such application workloads, we propose in this article an extensible network management architecture calledMAGNetwhich enables application-aware intra-data center networking. The crux ofMAGNetis the smart endpoint residing within end-hosts, which is empowered by machine learning combined with lightweight workload tracing to detect workload identities and enable workload-dependent packet tagging. The centralized management plane interface ofMAGNetallows network functions to interpret packet tags and perform application-aware packet processing. We demonstrate the feasibility of the architecture via prototype implementation and extensive use case evaluation. Our experiments show that the smart endpoint can fingerprint many real-world applications with 99 percent accuracy only at 1–2 percent additional CPU, and that application-aware data plane can potentially bring substantial benefits in terms of security (e.g., via identity-based microsegmentation), CPU usage (e.g., for intrusion detection) and network latency (e.g., via TCP stack customization).

Multiplexing resources is the core savings principle upon which the economic model of the Cloud is built. Cloud customers can flexibly purchase additional resources when needed, and trim these down when the need has past, while Cloud providers can direct resources when and where customers might require. One aspect which poses a challenge to this capability is the allocation process itself, which can be costly in terms of time and energy. Indeed, both provider and customer would prefer if resource allocation would be continuous, fast and with low energy overhead. Since this is not the case, there is an inherent tension between limiting the number of allocation events and efficient resource utilization.This paper considers this tension using several different models, and proposes a history-based dynamic allocation scheme that minimizes the number of resource allocation transition points for both average and adversarial use cases. We prove performance bounds and use extensive simulation to study the performance of our scheme.

Internet routing protocols like OSPF and ISIS use shortest path routing to route traffic from ingress nodes to egress nodes in a network. These shortest paths are computed with respect to the weights assigned to links in the underlying network. Since the routed paths depend on the assigned link weights, a fundamental problem in optimizing network routing is the determination of the set of weights that minimizes congestion in the network. This is an NP-hard combinatorial optimization problem. Consequently, several heuristics have been developed to determine the set of link weights to minimize congestion. In this paper, we develop a machine-learning based approach by formulating a smoothed version of the weight setting problem and using gradient descent in the PyTorch framework to derive approximate solutions to this problem. We demonstrate the improvement in performance compared to traditional approaches using several benchmark network topologies.

With the increasing success of machine learning based approaches for prediction problems, there has been recent effort in improving the performance of online algorithms by augmenting them with machine learning predictions. Since machine learning predictions typically do not offer any performance guarantees, the new approach has to take into consideration the possibility that the machine learning prediction can be inaccurate. The idea is to develop approaches that give good results when the prediction is accurate (consistency) while ensuring that the performance is still acceptable in the worst case, when the prediction is not accurate (robustness). Segment routing is now being widely deployed and used for traffic engineering in IP networks. The key idea in segment routing is to break up the routing path into segments to better control routing paths and improve network utilization. We consider the problem of designing the segments in a network to minimize congestion. This is typically done for a predicted traffic matrix. We use the ideas of consistency and robustness to design a parametrized algorithm that gives good performance when the actual traffic matrix is exactly the predicted traffic matrix (consistency) while giving good performance in the worst case if the actual traffic matrix deviates significantly from the predicted traffic matrix (robustness).

Dynamic resource allocation to satisfy varying, concurrent and unpredictable demands from multiple applications is a key need in cloud systems. A fundamental challenge is the need to find the right balance between over-allocation, which satisfies each application’s varying needs without requiring frequent allocation changes, and system efficiency which requires that the allocation exactly matches the application needs. However, allocating resources close to current needs will result in frequent allocation changes. This can be detrimental to applications since there may be fixed costs (state replication, policy reconfiguration, etc.) that need to be incurred by applications for each allocation change. In this paper, we develop an MDP-based dynamic allocation scheme that uses reinforcement learning to satisfy unpredictable application demands. It minimizes the overall resource allocation needed to satisfy varying application demands while meeting application constraints on the rate of allocation changes. We prove convergence bounds and use real-world traces to study the performance.

In this paper, we propose a general framework for combining deep neural networks (DNNs) with dynamic programming to solve combinatorial optimization problems. For problems that can be broken into smaller subproblems and solved by dynamic programming, we train a set of neural networks to replace value or policy functions at each decision step. Two variants of the neural network approximated dynamic programming (NDP) methods are proposed; in the value-based NDP method, the networks learn to estimate the value of each choice at the corresponding step, while in the policy-based NDP method the DNNs only estimate the best decision at each step. The training procedure of the NDP starts from the smallest problem size and a new DNN for the next size is trained to cooperate with previous DNNs. After all the DNNs are trained, the networks are fine-tuned together to further improve overall performance. We test NDP on the linear sum assignment problem, the traveling salesman problem and the talent scheduling problem. Experimental results show that NDP can achieve considerable computation time reduction on hard problems with reasonable performance loss. In general, NDP can be applied to reducible combinatorial optimization problems for the purpose of computation time reduction.

Mobile Augmented Reality (MAR) is going to play an important role in industrial automation. In order to tag a physical object in the MAR world, a smart phone running MAR-based applications must know the precise location of an object in the real world. Tracking and localizing a large number of objects in an industrial environment can become a huge burden for the smart phone due to compute and battery requirements. In this paper we propose GLAMAR, a novel framework that leverages externally provided geo-location of the objects and IMU sensor information (both of which can be noisy) from the objects to 10-cate them precisely in the MAR world. GLAMAR offloads heavy-duty computation to the edge and supports building MAR-based applications using commercial development packages. We develop a regenerative particle filter and a continuously improving transformation matrix computation methodology to dramatically improve the positional accuracy of objects in the real and the AR world. Our prototype implementation on Android platform using ARCore shows the practicality of GLAMAR in developing MAR-based applications with high precision, efficiency, and more realistic experience. GLAMAR is able to achieve less then 10cm error compared to the ground truth for both stationary and moving objects and reduces the CPU overhead by 83% and battery consumption by 80% for mobile devices.

In order to create services using IoT devices, the underlying network infrastructure must support large number of such devices with different underlying protocols, and diverse requirements from the service applications (privacy, reliability and QoS guarantee, etc.). Many of these requirements can be realized by implementing an in-network packet forwarding policy in the infrastructure supporting direct device-to-device communications. However, with large number of devices deployed in the IoT network, the number of rules required for policy enforcement grows very rapidly, and it becomes an infrastructural challenge to installing and managing the rules in switches/routers. We argue that attaching service and role-based labels to address IoT devices can significantly reduce the number of rules by using wild-cards. We formulate a scheme that can produce the optimum length labels for representing the service attributes of the communicating IoT devices. Due to non-convex nature of the optimization, we develop two heuristic solutions for the label generating scheme. Through evaluation using a simulated but practical IoT network environment with large number of devices, we demonstrate the benefits of the scheme that can reduce the number of rules by several orders of multitude.

Application aware data centers promise various benefits for data center management, in terms of resource provisioning, power estimation, network management, security protection, etc. However, the emerging microservices make it challenging for data center operators to accurately identify what applications are deployed by tenants, due to their highly dynamic and heterogeneous nature. In this paper, we address the problem of fingerprinting microservices in a unified, efficient, accurate and non-intrusive fashion. To this end, we characterize the runtime behaviors of microservices using eBPF-based lightweight system call tracing. To accurately fingerprint a diverse set of microservices based on their system call activities, we utilize the machine learning approach which combines Bayesian learning and LSTM autoencoders. We demonstrate that our approach can fingerprint many real-world microservices with 99% accuracy, using 1-2% additional CPU resource, and can detect the presence of previously unseen microservices with near perfect accuracy.

The Bitcoin blockchain is a secure, distributed ledger that enables trusted transactions across untrusted entities. However, many applications need much faster transaction confirmation than that of the current Bitcoin blockchain. In this paper, we present a high-throughput, low-latency, deterministic confirmation mechanism called ACCEL for accelerating Bitcoin's block confirmation mechanism. Our key idea for achieving faster confirmation is the quick identification of singular blocks that provably belong to the blockchain. While it is impossible to determine with certainty if a block belongs to a blockchain when network delays are unbounded, singular block detection exploits the fact that the end-to-end latency between Bitcoin miners is substantially lower than the inter-block spacing and can be assumed to be upper bounded. ACCEL is especially suitable for low-latency, permissioned blockchains, where the block spacing can be optimized to the blockchain's small latencies to greatly improve throughput. We evaluate ACCEL's performance with extensive simulations and with a real implementation built with minimal changes to and fully compatible with the Bitcoin blockchain. We show that with appropriate bounds on the end-to-end latency, it is possible to reduce transaction confirmation latencies to milliseconds with ACCEL, and so meet the performance needs of a wide range of applications.

It is well established that physical layer impairments significantly affect the performance of optical networks. The management of these impairments is critical for successful transmission, and may significantly affect network layer routing decisions. Hence, the traditional divide-and-conquer layered approach is sub-optimal, which has led to work on cross-layer techniques for routing in optical networks. Apart from fiber loss, one critical physical layer impairment that limits the capacity of optical networks is fiber nonlinearity. Handling nonlinearity introduces significant complexity to the traditional cross-layer approaches. We formulate and solve a joint routing and power control problem to optimize the system throughput that takes into consideration both fiber loss and nonlinearity. The joint power control and routing problem considered is a nonlinear integer programming problem. By characterizing the feasible solution space of the power control problem, we find a set of universal power settings that transform the complex power control and routing problem into a constrained path routing problem. We then propose an efficient fully polynomial time approximation scheme to solve the constrained path routing problem. Simulation results show that our proposed algorithm significantly improves network throughput and greatly outperforms greedy heuristics by providing a guaranteed performance bound.

In the past decade, mobile devices and applications have experienced an explosive growth, and users are expecting higher data rates and better quality services every year. In this paper, we propose several ideas to increase the functionality and capacity of wireless networks using software-defined networking (SDN) and cloud computing technologies. Connections between users and services in mobile networks typically have to pass through a required set of middleboxes. The complex routing is one of the major impetus for the SDN paradigm, which enables flexible policy-aware routing in the next generation mobile networks. In addition, the high costs of middleboxes and limited capabilities of mobile devices call for revolutionary virtualization technologies enabled by cloud computing. Based on these, we consider an online routing problem for mobile networks with SDN and cloud computing. In this problem, connection requests are given one at a time (as in a real mobile system), and the objective is to steer traffic flows to maximize the total amount of traffic accepted over time, subject to capacity, budget, policy, and quality of service constraints. A fast log-competitive approximation algorithm is developed based on time-dependent duals.

One of the primary functions of a cloud service provider is to allocate cloud resources to users upon request. Requests arrive in real-time and resource placement decisions must be made as and when a request arrives, without any prior knowledge of future arrivals. In addition, when a cloud service provider operates a geographically diversified cloud that consists of a large number of small data centers, the resource allocation problem becomes even more complex. This is due to the fact that resource request can have additional constraints on data center location, service delay guarantee, and so on, which is especially true for the emerging network function virtualization application. In this paper, we propose a generalized resource placement methodology that can work across different cloud architectures, resource request constraints, with real-time request arrivals and departures. The proposed algorithms are online in the sense that allocations are made without any knowledge of resource requests that arrive in the future, and the current resource allocations are made in such a manner as to permit the acceptance of as many future arrivals as possible. We derive worst case competitive ratio for the algorithms. We show through experiments and case studies the superior performance of the algorithms in practice.

Segment routing is a new proposed routing mechanism for simplified and flexible path control in IP/MPLS networks. It builds on existing network routing and connection management protocols and one of its important features is the automatic rerouting of connections upon failure. Re-routing can be done with available restoration mechanisms including IGP-based rerouting and fast reroute with loop-free alternates. This is particularly attractive for use in Software Defined Networks (SDN) because the central controller need only be involved at connection set-up time and failures are handled automatically in a distributed manner. A significant challenge in restoration optimization in segment routed networks is the centralized determination of connections primary paths so as to enable the best sharing of restoration bandwidth over non-simultaneous network failures. We formulate this problem as a linear programming problem and develop an efficient primal-dual algorithm for the solution. We also develop a simple randomized rounding scheme for cases when there are additional constraints on segment routing. We demonstrate the significant capacity benefits achievable from this optimized restoration with segment routing.

The advent and continued growth of large data centers has led to much interest in switch architectures that can economically meet the high capacities needed for interconnecting the thousands of servers in these data centers. Various multilayer architectures employing thousands of switches have been proposed in the literature. We make use of the observation that the traffic in a data center is a mixture of relatively static and rapidly fluctuating components, and develop a combined scheduler for both these components using a generalization of the load-balanced scheduler. The presence of the known static component introduces asymmetries in the ingress-egress capacities, which preclude the use of a load-balanced scheduler as is. We generalize the load-balanced scheduler and also incorporate an opportunistic scheduler that sends traffic on a direct path when feasible to enhance the overall switch throughput. Our evaluations show that this scheduler works very well despite avoiding the use of a central scheduler for making packet-by-packet scheduling decisions.

Segment Routing is a proposed IETF protocol to improve traffic engineering and online route selection in IP networks. The key idea in segment routing is to break up the routing path into segments in order to enable better network utilization. Segment routing also enables finer control of the routing paths and can be used to route traffic through middle boxes. This paper considers the problem of determining the optimal parameters for segment routing in the offline and online cases. We develop a traffic matrix oblivious algorithm for robust segment routing in the offline case and a competitive algorithm for online segment routing. We also show that both these algorithms work well in practice.

It is well established that physical layer impairments significantly affect the performance of optical networks. The management of these impairments is critical for successful transmission, and may significantly affect network layer routing decisions. Hence the traditional divide-and-conquer layered approach is sub-optimal, which has led to work on cross-layer techniques for routing in optical networks. Apart from fiber loss, one critical physical layer impairment that limits the capacity of optical networks is fiber nonlinearity. Handling nonlinearity introduces significant complexity to the traditional cross-layer approaches. We formulate and solve a joint routing and power control problem to optimize the system throughput that takes into consideration both fiber loss and nonlinearity. The joint power control and routing problem considered is a nonlinear integer programming problem. By characterizing the feasible solution space of the power control problem we find a set of universal power settings that transforms the complex power control and routing problem into a constrained path routing problem. We then propose an efficient Fully Polynomial Time Approximation Scheme (FPTAS) to solve the constrained path routing problem. Simulation results show that our proposed algorithm significantly improves network throughput and greatly outperforms greedy heuristics by providing a guaranteed performance bound.

Cloud service providers enable tenants to elastically scale resources to meet their demands. While running cloud applications, a tenant aiming to minimize cost is often challenged with crucial tradeoffs. For instance, upon each arrival of a query, a Web application can either choose to pay for CPU to compute the response fresh, or pay for cache storage to store the response to reduce future compute costs. The Ski-Rental problem abstracts such scenarios where a tenant is faced with a to-rent-or-to-buy tradeoff; in its basic form, a skier should choose between renting or buying a set of skis without knowing the number of days she will be skiing. In the multislope version of the Ski-Rental problem, the skier can choose among multiple services that differ in their buying and renting prices. In this paper, we introduce a variant of the classical Ski-Rental problem in which we assume that the skier knows the first (or second) moment of the distribution of the number of ski days in a season. We also extend the classical multislope Ski-Rental problem, where the skier can choose among multiple services, to this setting. We demonstrate that utilizing this information leads to achieving the best worst-case expected competitive ratio performance. Our method yields a new class of randomized algorithms that provide arrivals-distribution-free performance guarantees. Simulations illustrate that our scheme exhibits robust average-cost performance that combines the best of the well-known deterministic and randomized schemes previously proposed to tackle the Ski-Rental problem.

Scalable, low-latency and accurate RFID counting algorithms have recently been proposed as a fundamental building block to support more complex query operations in a large-scale RFID system. One distinct feature of these algorithms is that they do not require explicit identification of individual tags and therefore can eliminate the latency bottleneck caused by serialization during multiple access control. However, these algorithms all assume reliable communications between the reader and the tags. While this assumption is also adopted by many tag-identification protocols in the current RFID standards, it is practically unachievable given the current technology and low-cost requirement of RFID tags. In fact, recent empirical studies have found that the communication between an RFID reader and a set of seemingly “in-range” tags are still unreliable and highly non-deterministic due to the varying channel conditions. In this paper, we discuss the design and performance analysis of a set of channel-oblivious RFID counting algorithms which can estimate the size of a tag-set of interest over unreliable wireless channels. The proposed schemes can provide accurate cardinality estimates without any prior knowledge of the channel parameters. We first propose a series of algorithms and analyze their performance under a simplified memoryless lossy channel model. We then extend them to handle the impact due to backscattering effects and correlated losses found in practical RFID systems. Our proposed designs only require simple modifications to standard RFID tags and readers and can be implemented using current technologies with minimal increase in tag/ reader cost. Our designs can also be extended to other RFID counting algorithms which assumed reliable communication channels.

The advent and continued growth of large data centers has led to much interest in switch architectures that can economically meet the high capacities needed for interconnecting the thousands of servers in these data centers. Various multilayer architectures employing thousands of switches have been proposed in the literature. We make use of the observation that the traffic in a data center is a mixture of relatively static and rapidly fluctuating components, and develop a combined scheduler for both these components using a generalization of the load-balanced scheduler. The presence of the known static component introduces asymmetries in the ingress-egress capacities, which preclude the use of a load-balanced scheduler as is. We generalize the load-balanced scheduler and also incorporate an opportunistic scheduler which sends traffic on a direct path when feasible to enhance the overall switch throughput. Our evaluations show that this scheduler works very well despite avoiding the use of a central scheduler for making packet-by-packet scheduling decisions.

One of the primary functions of a cloud service provider is to allocate cloud resources to users upon request. Requests arrive in real-time and resource placement decisions must be made as and when a request arrives, without any prior knowledge of future arrivals. In addition, when a cloud service provider operates a geographically diversified cloud that consists of large number of small data centers, the resource allocation problem becomes even more complex. This is due to the fact that resource request can have additional constraints on data center location, service delay guarantee, etc. In this paper, we propose a generalized resource placement methodology that can work across different cloud architectures, resource request constraints, with real-time request arrivals and departures. The proposed algorithms are online in the sense that allocations are made without any knowledge of resource requests that arrive in the future, and the current resource allocations are made in such a manner as to permit the acceptance of as many future arrivals as possible. We derive worst case competitive ratio for the algorithms. We show through experiments and case studies the superior performance of the algorithms in practice.

Software Defined Networking is a new networking paradigm that separates the network control plane from the packet forwarding plane and provides applications with an abstracted centralized view of the distributed network state. A logically centralized controller that has a global network view is responsible for all the control decisions and it communicates with the network-wide distributed forwarding elements via standardized interfaces. Google recently announced [5] that it is using a Software Defined Network (SDN) to interconnect its data centers due to the ease, efficiency and flexibility in performing traffic engineering functions. It expects the SDN architecture to result in better network capacity utilization and improved delay and loss performance. The contribution of this paper is on the effective use of SDNs for traffic engineering especially when SDNs are incrementally introduced into an existing network. In particular, we show how to leverage the centralized controller to get significant improvements in network utilization as well as to reduce packet losses and delays. We show that these improvements are possible even in cases where there is only a partial deployment of SDN capability in a network. We formulate the SDN controller's optimization problem for traffic engineering with partial deployment and develop fast Fully Polynomial Time Approximation Schemes (FPTAS) for solving these problems. We show, by both analysis and ns-2 simulations, the performance gains that are achievable using these algorithms even with an incrementally deployed SDN.

Preventing flow of confidential data out of a network is a fundamental problem faced by network operators. This problem gets even more complex in the context of Cloud Computing, where multiple distrusting customers share the same underlying infrastructure, and data is often replicated and moved across regions. Despite the significance of this problem, existing solutions are based on generic search for keywords in outgoing data, and hence severely lack the ability to control data flow at a fine granularity with low false positives. In this paper, we advocate a fine-grained approach to prevent confidential data from leaking out of the cloud. We propose a solution using document-level fingerprint checks. We show via analysis and experiments that our algorithm for checking the fingerprints on-the-fly scale to a large amount of documents at very low cost. For example, for one TB of documents, our solution only requires 340 MB memory to achieve worst case expected detection lag (i.e. leakage length) of 1000 bytes.

Cloud service providers (CSPs) enable tenants to elastically scale their resources to meet their demands. In fact, there are various types of resources offered at various price points. While running applications on the cloud, a tenant aiming to minimize cost is often faced with crucial trade-off considerations. For instance, upon each arrival of a query, a web application can either choose to pay for CPU to compute the response fresh, or pay for cache storage to store the response so as to reduce the compute costs of future requests. The SkiRental problem abstracts such scenarios where a tenant is faced with a to-rent-or-to-buy trade-off; in its basic form, a skier should choose between renting or buying a set of skis without knowing the number of days she will be skiing. In this paper, we introduce a variant of the classical SkiRental problem in which we assume that the skier knows the first (or second) moment of the distribution of the number of ski days in a season. We demonstrate that utilizing this information leads to achieving the best worst-case expected competitive ratio (CR) performance. Our method yields a new class of randomized algorithms that provide arrivals-distribution-free performance guarantees. Further, we apply our solution to a cloud file system and demonstrate the cost savings obtained in comparison to other competing schemes. Simulations illustrate that our scheme exhibits robust average-cost performance that combines the best of the well-known deterministic and randomized schemes previously proposed to tackle the Ski-Rental problem.

Enterprises are moving their IT infrastructure to cloud service providers with the goal of saving costs and simplifying management overhead. One of the critical services for any enterprise is its file system, where users require real-time access to files. Cloud service providers provide several building blocks such as Amazon EBS, or Azure Cache, each with very different pricing structures that differ on the basis of storage, access and bandwidth costs. Moving an entire file system to the cloud using such services is not cost-optimal if we rely on only one of these services. In this paper, we propose FCFS, a storage solution that drastically reduces the cost of operating a file system in the cloud. Our solution integrates multiple storage services and dynamically adapts the storage volume sizes of each service to provide a cost-efficient solution with provable performance bounds. Using real-world large scale data sets spanning a variety of work loads from an enterprise data center, we show that FCFS can reduce file storage and access costs in current cloud services by a factor of two or more, while allowing users to utilize the benefits of the various cloud storage services.

MapReduce has emerged as an important paradigm for processing data in large data centers. MapReduce is a three phase algorithm comprising of Map, Shuffle and Reduce phases. Due to its widespread deployment, there have been several recent papers outlining practical schemes to improve the performance of MapReduce systems. All these efforts focus on one of the three phases to obtain performance improvement. In this paper, we consider the problem of jointly scheduling all three phases of the MapReduce process with a view of understanding the theoretical complexity of the joint scheduling and working towards practical heuristics for scheduling the tasks. We give guaranteed approximation algorithms and outline several heuristics to solve the joint scheduling problem.

In an ad targeting system, an advertiser specifies the profiles of the users to whom it is interested in showing an ad. The underlying ad distribution system would like to use profiles of users, if available, to match advertisers to users in an optimal manner. Availability of the needed profile information very much depends on whether users opt-in to have their profile information revealed. When some set of users opt-out of having their profile information revealed, possibly for privacy reasons, an ad distribution system needs methods to match advertisers to the right users despite the system itself not having full knowledge of the users' profiles. In this paper, we propose solutions to this problem thereby expanding the universe of users to whom ad targeting becomes feasible. Ads can be targeted to opt-in users, whose profiles are therefore known to the ad targeting system, using now known approaches. Our solution enables targeting of ads to users who have chosen to not opt-in to reveal their profiles. Such users keep their true interest profiles to themselves (locally on their equipment). Ads to be displayed are selected locally and ad scheduling is done using a guaranteed approximation online algorithm that uses only statistically falsified profile information and not the true profiles. Despite the use of statistically falsified information, accurate targeting can be done. We show both analytically and experimentally that the performance of the ad scheduler is quite close to optimal.

In this paper, we consider the problem of designing a data structure that can perform fast multiple-set membership testing in deterministic time. Our primary goal is to develop a hardware implementation of the data structure that uses only embedded memory blocks. Prior efforts to solve this problem involve hashing into multiple Bloom filters. Such approach needs a priori knowledge of the number of elements in each set in order to size the Bloom filter. We use a single-Bloom-filter-based approach and use multiple sets of hash functions to code for the set (group) id. Since a single Bloom filter is used, it does not need a priori knowledge of the distribution of the elements across the different sets. We show how to improve the performance of the data structure by using constant-weight error-correcting codes for coding the group id. Using error-correcting codes improves the performance of these data structures especially when there are a large number of sets. We also outline an efficient hardware-based approach to generate the large number of hash functions that we need for this data structure. The resulting data structure, COMB, is amenable to a variety of time-critical network applications.

Many popular algorithms for fast packet forwarding and filtering rely on the tree data structure. Examples are the trie-based IP lookup and packet classification algorithms. With the recent interest in network virtualization, the ability to run multiple virtual router instances on a common physical router platform is essential. An important scaling issue is the number of virtual router instances that can run on the platform. One limiting factor is the amount of high-speed memory and caches available for storing the packet forwarding and filtering data structures. An ideal goal is to achieve good scaling while maintaining total isolation among the virtual routers. However, total isolation requires maintaining separate data structures in high-speed memory for each virtual router. In this paper, we study the case where some sharing of the forwarding and filtering data structures is permissible and develop algorithms for combining tries used for IP lookup and packet classification. Specifically, we develop a mechanism called trie braiding that allows us to combine tries from the data structures of different virtual routers into just one compact trie. Two optimal braiding algorithms and a faster heuristic algorithm are presented, and the effectiveness is demonstrated using the real-world data sets.

Large-scale data processing needs of enterprises today are primarily met with distributed and parallel computing in data centers. MapReduce has emerged as an important programming model for these environments. Since today's data centers run many MapReduce jobs in parallel, it is important to find a good scheduling algorithm that can optimize the completion times of these jobs. While several recent papers focused on optimizing the scheduler, there exists very little theoretical understanding of the scheduling problem in the context of MapReduce. In this paper, we seek to address this problem by first presenting a simplified abstraction of the MapReduce scheduling problem, and then formulate the scheduling problem as an optimization problem.We devise various online and offline algorithms to arrive at a good ordering of jobs to minimize the overall job completion times. Since optimal solutions are hard to compute (NP-hard), we propose approximation algorithms that work within a factor of 3 of the optimal. Using simulations, we also compare our online algorithm with standard scheduling strategies such as FIFO, Shortest Job First and show that our algorithm consistently outperforms these across different job distributions.

A low-latency, accurate RFID counting scheme can be used as a fundamental building block to support more elaborated RFID query operations. RFID counting algorithms of such nature have been proposed recently by Kodialam et. al.. One distinct feature of these schemes is that they do not require the reader to explicitly identify individual tags and thus can help to preserve privacy of the RFID users. However, these schemes all assume a perfect communication channel between the reader and the tags which is not achievable in practice. Recent empirical measurement studies have found that the radio communication between an RFID reader and a set of seemingly “in-range” tags are still unreliable and non-deterministic due to ever-changing channel conditions. Worse still, given the stringent cost constraint, it is unlikely that standard channel estimation procedures can be applied for individual tags. In this paper, we propose two new algorithms which can provide good estimates of the size of an RFID tag-set over unreliable, lossy wireless channels while assuming minimal or no prior knowledge of channel parameters. These algorithms are scalable over a wide range of tag-set size using a small, fixed protocol frame-size, which is critical for low-cost RFID tags with typically sub-par synchronization or timing control. They are also adaptive in the sense that, they self-tune the algorithm parameters according to the tag-set size and channel characteristics. This set of features makes them applicable in a wide variety of situations where the reader is unaware of or has very limited knowledge of the channel conditions. We also demonstrate the efficacy of the proposed schemes via extensive simulation studies.

Behavioral targeting of content to users is a huge and lucrative business, valued as a $20 billion industry that is growing rapidly. So far, the dominant players in this field like Google and Yahoo! examine the user requests coming to their servers and place appropriate ads based on the user's search keywords. Triple-play service providers have access to all the traffic generated by the users and can generate more comprehensive profiles of users based on their TV, broadband, and mobile usage. Using such multisource profile information, they can generate new revenue streams by smart targeting of ads to their users over multiple screens (computer, TV, and mobile handset). This paper proposes methods to place targeted ads to a TV based on user's interests. It proposes an ad auction model that can leverage multisource profile and can handle dynamic profile-based targeting like Google's AdWords vis-à-vis static demography-based targeting of legacy TV. We then present a 0.502-competitive revenue maximizing scheduling algorithm that chooses a set of ads in each time slot and assigns users to one of these selected ads.

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.

Behavioral targeting of content to users is a huge and lucrative business, valued as a $20 billion industry that is growing rapidly. So far dominant players in this field like Google and Yahoo examine the user requests coming to their servers and place appropriate ads based on the user's search keywords. Triple play service providers have access to all the traffic generated by the users and can generate more comprehensive profiles of users based on their TV, broadband and mobile usage. Using such multi-source profile information they can generate new revenue streams by smart targeting of ads to their users over multiple screens (computer, TV and mobile handset). This paper proposes methods to place targeted ads to a TV based on user's interests. It proposes an ad auction model that can leverage multi-source profile and can handle dynamic profile-based targeting like Google's AdWords vis-a-vis static demography-based targeting of legacy TV. We then propose a 0.502-competitive revenue maximizing scheduling algorithm that chooses a set of ads in each time slot and assigns users to one of these selected ads.

Many popular algorithms for fast packet forwarding and filtering rely on the tree data structure. Examples are the trie-based IP lookup and packet classification algorithms. With the recent interest in network virtualization, the ability to run multiple virtual router instances on a common physical router platform is essential. An important scaling issue is the number of virtual router instances that can run on the platform. One limiting factor is the amount of high-speed memory and caches available for storing the packet forwarding and filtering data structures. An ideal goal is to achieve good scaling while maintaining total isolation amongst the virtual routers. However, total isolation requires maintaining separate data structures in high-speed memory for each virtual router. In this paper, we study the case where some sharing of the forwarding and filtering data structures is permissible and develop algorithms for combining tries used for IP lookup and packet classification. Specifically, we develop a mechanism called trie-braiding that allows us to combine tries from the data structures of different virtual routers into just one compact trie. Two optimal braiding algorithms are presented and the effectiveness is demonstrated using the real world data sets.

With the increasing volume of VoIP, IPTV, and other real-time traffic on the Internet in recent years, service providers and operators demand tools to effectively detect and manage such traffic in their networks. However, many such applications are not easy to detect by using conventional approaches based on packet header and payload inspections since they may use random ports and data encryption. In this paper, we propose a simple yet effective approach that can detect constant or near constant rate traffic based on statistical inference on packet timing behaviors. Through experiments with traffic collected from both lab controlled environment and actual field networks, we show that this approach is easier to implement and has much better performance compared to existing approaches.

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.

Recently, there has been much renewed interest in developing compact data structures for packet processing functions such as longest prefix-match for IP lookups. This has been motivated by several factors: (1) The advent of 100 Gbps interfaces necessitating correspondingly fast packet processing algorithms with a compact memory footprint; (2) network virtualization leading to virtualization of physical router platforms making it critical to reduce high-speed memory needs per virtual router; (3) software routers built on multi-core processors requiring the use of compact data-structures that fit in on-chip caches for good performance. In this paper, we revisit this issue of developing compact data structures for key packet-processing functions. We develop a new data structure, called the shape graph, that significantly compacts the trie data-structure used for IP lookups. We accomplish this by identifying considerable structural similarities in IP lookup tries that have not previously been used in the literature for scalable IP lookups. We use these similarities to store lookup tries in a new graph data structure that has a significantly lower memory-footprint. Using real IP forwarding tables, we compare the memory usage of this new data structure to that of multi-bit tries and of Bloom filters used for IP lookups. The shape graph requires significantly less memory and allows the far more effective use of on-chip memory. This effective use of on-chip memory combined with multi-threading on a multi-core processor makes shape-graph-based IP lookups well suited for 100 Gbps lookups. The small footprint also makes it well suited for use in router platforms that host a large number of virtual routers.

In this paper we consider the problem of designing a data structure that can perform fast multiset membership testing in deterministic time. Our primary goal is to develop a hardware implementation of the data structure which uses only embedded memory blocks. Prior efforts to solve this problem involve hashing into multiple bloom filters. Such approach needs a priori knowledge of the number of elements in each set in order to size the bloom filter. We use a single bloom filter based approach and use multiple sets of hash functions to code for the set (group) id. Since a single bloom filter is used, it does not need a priori knowledge of the distribution of the elements across the different sets. We show how to improve the performance of the data structure by using constant weight error correcting codes for coding the group id. Using error correcting codes improves the performance of these data structures especially when there are large number of sets. We also outline an efficient hardware based approach to generate the the large number of hash functions that we need for this data structure. The resulting data structure, COMB, is amenable to a variety of time-critical network applications.

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.

Internet line speeds are expected to reach 100 Gbps in a few years. To match these line rates, a single router line card needs to forward more than 150 million packets per second. This requires a corresponding amount of longest prefix match operations. Furthermore, the increased use of IPv6 requires core routers to perform the longest prefix match on several hundred thousand prefixes varying in length up to 64 bits. It is a challenge to scale existing algorithms simultaneously in the three dimensions of increased throughput, table size and prefix length. Recently, Bloom filter-based IP lookup algorithms have been proposed. While these algorithms can take advantage of hardware parallelism and fast on-chip memory to achieve high performance, they have significant drawbacks (discussed in the paper) that impede their use in practice. In this paper, we present the distributed and load balanced bloom filters to address these drawbacks. We develop the practical IP lookup algorithm for use in 100 Gbps line cards. The regular and modular hardware architecture of our scheme directly maps to the state-of-art ASICs and FPGAs with reasonable resource consumption. Also, our scheme outperforms TCAMs on most metrics including cost, power dissipation, and board footprint.

Given a large set of RFID tags, we are interested in determining the categories of tags that are present in the shortest time possible. Since there can be more than one tag present in a particular category, pure randomized strategies that rely on resolving individual tags are very inefficient. Instead, we rely on a pseudo-random strategy that utilizes a uniform hash function to accurately identify all t categories present among a given set of ψ tags with high probability. We propose two algorithms: (a) a single frame algorithm that determines the optimal frame size, and (b) a probabilistic version where the frame size is fixed, and we select the probability to minimize the number of frames needed for identification. Both of these algorithms run in time linear to the number of categories present, t. We show that our approach significantly outperforms existing algorithms for category identification. The performance of our algorithms is within a constant factor of the lower bound.

High-speed organizational networks running over leased fiber-optic lines or VPNs suffer from the well-known limitations of TCP over long-fat pipes. High-performance protocols like XCP require changes in the network. Other protocols like FastTCP assume nothing about the network but may not perform as well as network-aware protocols. In this paper, we present a new transport protocol that exploits the fact that these networks can offer priority queuing, thus finding the sweet spot between assuming too much and too little about the network. Our protocol splits a given transport flow into two prioritized flows. The higher priority flow operates with the legacy congestion control while the lower priority flow aggressively exploits spare capacity in the network while not interfering with the other participating flows. This isolation of the aggressive flow into strictly lower priority queues gives us more latitude in how to operate the aggressive component. We show through Emulab experiments of our implementation as well as simulations that this protocol can produce near-perfect goodputs in lossy networks, can considerably improve the completion time of short flows, and can sustain a high bottleneck utilization even in changing network conditions.

A bloom filter is a randomized data structure for performing approximate membership queries. It is being increasingly used in networking applications ranging from security to routing in peer to peer networks. In order to meet a given false positive rate, the amount of memory required by a bloom filter is a function of the number of elements in the set. We consider the problem of minimizing the memory requirements in cases where the number of elements in the set is not known in advance but the distribution or moment information of the number of elements is known. We show how to exploit such information to minimize the expected amount of memory required for the filter. We also show how this approach can significantly reduce memory requirement when bloom filters are constructed for multiple sets in parallel. We show analytically as well as experiments on synthetic and trace data that our approach leads to one to three orders of magnitude reduction in memory compared to a standard bloom filter.

In this paper, we propose DATALITE, a Distributed Architecture for Traffic Analysis via LIght-weight Traffic digEst, which introduces a set of new distributed algorithms and protocols to support general Traffic Measurement and Analysis (TMA) functions for large-scale, 10Gbps+ packet-switched networks. We formulate the network-wide traffic measurement/ analysis problem as a series of set-cardinality-determination (SCD) problems. By leveraging recent advances in probabilistic distinct sample counting techniques, the set-cardinalities, and thus, the network-wide traffic measurements of interest can be computed in a distributed manner via the exchange of extremely light-weight traffic digests (TD’s) amongst the network nodes. A TD for N packets only requires O(loglog N) bits of memory storage.

In this paper, we investigate joint resource allocation and routing for a wireless mesh network consisting of fixed access points inter-connected through multi-channel wireless links. Some of the mesh routers are assumed to function as gateways with high bandwidth connections to a wired network and the mesh network is assumed to provide multi-hop capability where the traffic entering the mesh via gateways may be carried over multiple wireless hops towards the destination mesh routers. The main objective of this work is to optimize resource allocation and routing in such networks; in this regard, we study a cross- layer optimization problem that includes power control, channel allocation, link scheduling and routing. We provide results highlighting the capacity benefits of our proposed approach; these results indicate that significant throughput improvements can be achieved with cross-layer system design.

We consider a wireless system comprising of multiple users that communicate with a base station. When there are a large number of users with time varying channels, it has been shown that multiuser diversity can be exploited to achieve high throughput in these systems. In a system employing multiuser diversity, the base station estimates the channel quality for each user during each time slot, and schedules the user with the best channel condition for that time slot. There has been a considerable amount of work towards developing scheduling mechanisms to provide quality of service guarantees to the individual users in addition to maximizing total throughput. In this paper, we consider the achievable rate region of a multiuser TDM system when the average transmit power is bounded. Our objective is to develop efficient algorithms to determine if a given rate vector is achievable within the average power bound. We characterize the achievable rate region when the channel behavior can be approximated by the on-off Gilbert-Elliot channel model. We first show that the problem of determining if a rate vector is achievable can be formulated as a convex optimization problem over a suitably denned polymatroid. We derive optimal waterfilling algorithms for solving the achievable rate region problem.

The increasing use of RFID tags in many applications have brought forth valid concerns of privacy and anonymity among users. One of the primary concerns with RFID tags is their ability to track an individually tagged entity. While this capability is currently thought to be necessary for supporting some features of RFID systems, such practice can lead to potential privacy violations. In this paper, we propose a privacy-preserving scheme that enables anonymous estimation of the cardinality of a dynamic set of RFID tags, while allowing the set membership to vary in both the spatial and temporal domains. In addition, the proposed scheme can identify the dynamics of the changes in the tag set population. The main idea of the scheme is to avoid explicit identification of tags. We demonstrate that the proposed scheme is highly adaptive and can accurately estimate tag populations across many orders of magnitude, ranging from a few tens to millions of tags. The associated probing latency is also substantially lower (les 10%) than that of the schemes which require explicit tag identification. We also show that our proposed scheme performs well even in highly dynamic environments, where the tag set keeps changing rapidly.

The growing importance of operations such as packet-content inspection, packet classification based on non-IP headers, maintaining flow-state, etc. has led to increased interest in the networking applications of Bloom filters. This is because Bloom filters provide a relatively easy method for hardware implementation of set-membership queries. However, the tradeoff is that Bloom filters only provide a probabilistic test and membership queries can result in false positives. Ideally, we would like this false positive probability to be very low. The main contribution of this paper is a method for significantly reducing this false positive probability in comparison to existing schemes. This is done by developing a partitioned hashing method which results in a choice of hash functions that set far fewer bits in the Bloom filter bit vector than would be the case otherwise. This lower fill factor of the bit vector translates to a much lower false positive probability. We show experimentally that this improved choice can result in as much as a ten-fold increase in accuracy over standard Bloom filters. We also show that the scheme performs much better than other proposed schemes for improving Bloom filters.

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.

In this paper, we propose a cross layer optimization framework for multi-hop routing and resource allocation design in an orthogonal frequency division multiple access (OFDMA) based wireless mesh network. The network under consideration is assumed to consist of fixed mesh routers (or base station routers) inter-connected using OFDMA wireless links with some of the mesh routers functioning as gateways to a wired network. The objective of our cross-layer formulation is to allow joint determination of power control, frequency-selective OFDMA scheduling and multi-hop routing in order to maximize the minimum throughput that can be supported to all mesh routers. Results of our investigations under typical cellular deployment, propagation and channel model assumptions show that this approach achieves significant mesh throughput improvements primarily due to the following: (a) frequency selective scheduling with OFDMA which provides improved tone diversity thus allowing more efficient bandwidth utilization relative to single carrier methods; and (b) multi-hop routing which provides improved path diversity relative to single hop transmissions.

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.

Fast IP flow rate estimation has many potential applications in network management, monitoring, security, and traffic engineering. Recently, low cost and memory efficient techniques to accurately estimate flow-rates in real-time have been developed. These techniques rely on flow definitions being constrained to being subsets of the fields in the packet header making flow-membership tests relatively inexpensive. In this paper, we consider a more general flow-rate estimation problem where flow membership testing is non-trivial and may involve more complex processing such as packet-payload based tests. An example is to estimate the amount of traffic that contains a given set of patterns (e.g., virus or worm signatures). We design new flow estimation techniques to reduce the number of membership tests. These techniques track pairs of arrivals that have the given property of interest and use lazy membership testing to avoid complex property testing unless absolutely necessary. The efficiency of the new schemes is evaluated by both analysis and simulation. I.

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.

RFID tags are being used in many diverse applications in increasingly large numbers. These capabilities of these tags span from very dumb passive tags to smart active tags, with the cost of these tags correspondingly ranging from a few pennies to many dollars. One of the common problems that arise in any RFID deployment is the problem of quick estimation of the number of tags in the field up to a desired level of accuracy. Prior work in this area has focused on the identification of tags, which needs more time, and is unsuitable for many situations, especially where the tag set is dense. We take a different, more practical approach, and provide very fast and reliable estimation mechanisms. In particular, we analyze our estimation schemes and show that the time needed to estimate the number of tags in the system for a given accuracy is much better than schemes presented in related work. We show that one can estimate the cardinality of tag-sets of any size in near-constant time, for a given accuracy of estimation.

Real-time IP flow estimation has many potential applications in network management, monitoring, security, and traffic engineering. Existing techniques typically rely on flow definitions being constrained as subsets of the fields in packet headers. This makes flow-membership tests relatively inexpensive. In this paper, we consider a more general flow estimation problem that needs complex packet-payload based tests for flow-membership. An example is to estimate traffic with common strings in the payload and detect potential virus signatures for early alarm generation. We develop a fast, memory efficient algorithm for solving this problem as a variant of the longest common subsequence problem. This is done via an application of Rabin fingerprinting in combination with bloom filters. Both analysis and simulation show the effectiveness of the developed method.

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.

We consider the problem of fast, estimation of flow rates in backbone network links with possibly millions of flows. Accurate flow rate estimation is necessary for network traffic management, network planning, measuring compliance to service level agreements, and network security. Ideally, a rate estimation scheme should have short estimation times with provable bounds on estimation error, be low in memory usage, and be easily implementable in hardware for operation at high speeds. We develop such a scheme, and achieve up to two orders of magnitude speed-up in estimation time over the previously proposed two-runs-based RATE scheme [Kodialam, M et al., 2004]. The speedups are achieved without a significant increase in memory usage, by using coincidences instead of runs. Counting coincidences has a higher processing overhead than detecting two-runs, but this higher overhead is not significant for a hardware implementation. We show that the proposed scheme is faster and more accurate than other recently proposed schemes such as ACCEL-RATE [Hao, F et al., 2004] and smart sampling [Duffield, N et al., 2004]. The faster estimation time of the new scheme has many benefits including quicker detection of incipient denial of service attacks. We prove bounds on the scheme's accuracy, memory needs, and also show that it performs well by simulations that use both synthetic and real traffic traces.

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.

Next generation fixed wireless broadband networks are being increasingly deployed as mesh networks in order to provide and extend access to the internet. These networks are characterized by the use of multiple orthogonal channels and nodes with the ability to simultaneously communicate with many neighbors using multiple radios (interfaces) over orthogonal channels. Networks based on the IEEE 802.11a/b/g and 802.16 standards are examples of these systems. However, due to the limited number of available orthogonal channels, interference is still a factor in such networks. In this paper, we propose a network model that captures the key practical aspects of such systems and characterize the constraints binding their behavior. We provide necessary conditions to verify the feasibility of rate vectors in these networks, and use them to derive upper bounds on the capacity in terms of achievable throughput, using a fast primal-dual algorithm. We then develop two link channel assignment schemes, one static and the other dynamic, in order to derive lower bounds on the achievable throughput. We demonstrate through simulations that the dynamic link channel assignment scheme performs close to optimal on the average, while the static link channel assignment algorithm also performs very well. The methods proposed in this paper can be a valuable tool for network designers in planning network deployment and for optimizing different performance objectives.

Input-queued switches are used extensively in the design of high-speed routers. As switch speeds and sizes increase, the design of the switch scheduler becomes a primary challenge, because the time interval for the matching computations needed for determining switch configurations becomes very small. Possible alternatives in scheduler design include increasing the scheduling interval by using envelopes , and using a frame-based scheduler that guarantees fixed rates between input-output pairs. However, both these alternatives have significant jitter drawbacks: the jitter increases with the envelope size in the first alternative, and previously-known methods do not guarantee tight jitter bounds in the second. In this paper, we propose a hybrid approach to switch scheduling. Traffic with tight jitter constraints is first scheduled using a frame-based scheduler that achieves low jitter bounds. Jitter-insensitive traffic is later scheduled using an envelope-based scheduler. The main contribution of this paper is a scheduler design for generating low-jitter schedules. The scheduler uses a rate matrix decomposition designed for low jitter and different from the minimum-bandwidth Birkhoff-Von Neumann (BV) decomposition. In addition to generating low-jitter schedules, this decomposition in the worst case yields fewer switch configuration matrices (O(n)) than the BV decomposition (O(n/sup 2/)), and so requires far less high-speed switch memory. We develop an efficient algorithm for decomposing the rate matrix and for scheduling the permutation matrices. We prove that our low-jitter algorithm has an O(logn) factor bound on its bandwidth consumption in comparison to the minimum-bandwidth BV decomposition. Experimentally, we find that the bandwidth increase in practice is much lower than the theoretical bound. We also prove several related performance bounds for our scheduler. Finally, we propose a practical algorithm for bandwidth-guaranteed algorithm, and show how our findings could even be extended to systems with large tuning time.

This paper considers the problem of determining the achievable rates in multi-hop wireless mesh networks with orthogonal channels. We classify wireless networks with orthogonal channels into two types, half duplex and full duplex, and consider the problem of jointly routing the flows and scheduling transmissions to achieve a given rate vector. We develop tight necessary and sufficient conditions for the achievability of the rate vector. We develop efficient and easy to implement Fully Polynomial Time Approximation Schemes for solving the routing problem. The scheduling problem is a solved as a graph edge-coloring problem. We show that this approach guarantees that the solution obtained is within 50% of the optimal solution in the worst case (within 67% of the optimal solution in a common special case) and, in practice, is close to 90% of the optimal solution on the average. The approach that we use is quite flexible and can be extended to handle more sophisticated interference conditions, and routing with diversity requirements.

We address the problem of fast automatic identification of traffic patterns in core networks with high speed links carrying large numbers of flows. This problem has applications in detecting DoS attacks, traffic management, and network security. The typical measurement and identification objective is to determine flows that use up a disproportionate fraction of network resources. Several schemes have been devised to measure large flows efficiently assuming that the notion of what constitutes a flow is well defined a priori. However, there are many scenarios where traffic patterns are hidden in the sense that there is no clear knowledge of what exactly to look for and there is no natural a priori definition of flow. In This work, we develop an effective scheme to identify and measure hidden traffic patterns. The approach is flexible enough to automatically identify interesting traffic patterns for further evaluation. The basic idea is to extend the runs based approach proposed in (Kodialam, M. et al., 2004) to the case where flow definitions are not known a priori. A straightforward extension is both memory and processing intensive. We develop an efficient scheme that has good theoretical properties and does extremely well in practice.

With increasing interest in energy constrained multi-hop wireless networks (Bambos, N. et al., 1991), a fundamental problem is one of determining energy efficient communication strategies over these multi-hop networks. The simplest problem is one where a given source node wants to communicate with a given destination, with a given rate over a multi-hop wireless network, using minimum power. Here the power refers to the total amount of power consumed over the entire network in order to achieve this rate between the source and the destination. There are three decisions that have to be made (jointly) in order to minimize the power requirement. (1) The path(s) that the data has to take between the source and the destination. (Routing). (2) The power with each link transmission is done. (Power Control). (3) Depending on the interference or the MAC characteristics, the time slots in which specific link transmissions have to take place. (Scheduling). (4) To the best of our knowledge, ours is the first attempt to derive a performance guaranteed polynomial time approximation algorithm for jointly solving these three problems. We formulate the overall problem as an optimization problem with non-linear objective function and non-linear constraints. We then derive a polynomial time 3-approximation algorithm to solve this problem. We also present a simple version of the algorithm, with the same performance bound, which involves solving only shortest path problems and which is quite efficient in practice. Our approach readily extends to the case where there are multiple source-destination pairs that have to communicate simultaneously over the multi-hop network.

Per-flow network traffic measurements are needed for effective network traffic management, network performance assessment, and detection of anomalous network events such as incipient DoS attacks. Explicit measurement of per-flow traffic statistics is difficult in backbone networks because tracking the possibly hundreds of thousands of flows needs correspondingly large high-speed memories. To reduce the measurement overhead, many previous papers have proposed the use of random sampling and this is also used in commercial routers (Cisco's Net Flow). Our goal is to develop a new scheme that has very low memory requirements and has quick convergence to within a prespecified accuracy. We achieve this by use of a novel approach based on sampling two-runs to estimate per-flow traffic. (A flow has a two-run when two consecutive samples belong to the same flow). Sampling two-runs automatically biases the samples towards the larger flows thereby making the estimation of these sources more accurate. This biased sampling leads to significantly smaller memory requirement compared to random sampling schemes. The scheme is very simple to implement and performs extremely well

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.

The effect of interference on the achievable rate region in multihop wireless networks under three increasingly constraining interference models network throughput characterization namely primary conflict avoidance, receiver conflict avoidance and transmitter-receiver conflict avoidance is studied in this paper. The necessary conditions for achievability in the three models as linear constraints, and the structure of these constraints to develop efficient fully polynomial time approximation algorithms that route end-to-end flows between multiple source destination pairs are exploited. The techniques developed in this paper are applicable to a wide range of problems, including capacity problems, arising in multihop networks with interference constraints.

Per-flow network traffic measurement is an important component of network traffic management, network performance assessment, and detection of anomalous network events such as incipient DoS attacks. In [1], the authors developed a mechanism called RATE where the focus was on developing a memory efficient scheme for estimating per-flow traffic rates to a specified level of accuracy. The time taken by RATE to estimate the per-flow rates is a function of the specified estimation accuracy and this time is acceptable for several applications. However some applications, such as quickly detecting worm related activity or the tracking of transient traffic, demand faster estimation times. The main contribution of this paper is a new scheme called ACCEL-RATE that, for a specified level of accuracy, can achieve orders of magnitude decrease in per-flow rate estimation times. It achieves this by using a hashing scheme to split the incoming traffic into several sub-streams, estimating the per-flow traffic rates in each of the substreams and then relating it back to the original per-flow traffic rates. We show both theoretically and experimentally that the estimation time of ACCEL-RATE is at least one to two orders of magnitude lower than RATE without any significant increase in the memory size.

A new algorithm for routing of messages in ad-hoc networks where the nodes are energy-constrained is presented. The routing objective is to maximize the total number of messages that can be successfully sent over the network without knowing any information regarding future message arrivals or message generation rates. From a theoretical perspective, we show that if admission control of messages is permitted, then the worst-case performance of our algorithm is within a factor of O(log(network size)) of the best achievable solution. In other words, our algorithm achieves a logarithmic competitive ratio. Our approach provides sound theoretical backing for several observations that have been made by previous researchers. From a practical perspective, we show by extensive simulations that the performance of the algorithm is very good even in the absence of admission control (the admission control being necessary only to prove the competitive ratio result), and that it also performs better than previously proposed algorithms for other suggested metrics such as network lifetime maximization. Our algorithm uses a single shortest path computation, and is amenable to efficient implementation. We also evaluate by simulations the performance impact of inexact knowledge of residual battery energy, and the impact of energy drain due to dissemination of residual energy information.

Input-queued switches are used extensively in the design of high-speed routers. As switch speeds and sizes increase, the design of the switch scheduler becomes a primary challenge, because the time interval for the matching computations needed for determining switch configurations becomes very small. Possible alternatives in scheduler design include increasing the scheduling interval by using envelopes, and using a frame-based scheduler that guarantees fixed rates between input-output pairs. However, both these alternatives have significant jitter drawbacks: the jitter increases with the envelope size in the first alternative, and previously-known methods do not guarantee tight jitter bounds in the second. In this paper, we propose a hybrid approach to switch scheduling. Traffic with tight jitter constraints is first scheduled using a frame-based scheduler that achieves low jitter bounds. Jitter-insensitive traffic is later scheduled using an envelope-based scheduler. The main contribution of this paper is a scheduler design for generating low-jitter schedules. The scheduler uses a rate matrix decomposition designed for low jitter and different from the minimum-bandwidth Birkhoff-Von Neumann (BV) decomposition. In addition to generating low-jitter schedules, this decomposition yields fewer switch configuration matrices (O(n)) than the BV decomposition (O(n/sup 2/)), and so uses far less high-speed switch memory. We develop an efficient algorithm for decomposing the rate matrix and for scheduling the permutation matrices. We prove that our low-jitter algorithm has an O(log n) factor bound on its bandwidth consumption in comparison to the minimum-bandwidth BV decomposition. Experimentally, we find that the bandwidth increase in practice is much lower than the theoretical bound. We also prove several related performance bounds for our scheduler. Finally, we propose a practical bandwidth-guaranteed algorithm, and show how our findings could even be extended to systems with large tuning time.

In this paper, we consider the problem of detecting an intruding packet in a communication network. Detection is accomplished by sampling a portion of the packets transiting selected network links (or router interfaces). Since sampling entails incurring network costs for real-time packet sampling and packet examination hardware, we would like to develop a network packet sampling strategy to effectively detect network intrusions while not exceeding a given total sampling budget. We consider this problem in a game theoretic framework, where the intruder picks paths (or the network ingress point if only shortest path routing is possible) to minimize chances of detection and where the network operator chooses a sampling strategy to maximize the chances of detection. We formulate the game theoretic problem, and develop sampling schemes that are optimal in this game theoretic setting.

This paper considers the problem of determining the achievable rates in multi-hop wireless networks. We consider the problem of jointly routing the flows and scheduling transmissions to achieve a given rate vector. We develop tight necessary and sufficient conditions for the achievability of the rate vector. We develop efficient and easy to implement Fully Polynomial Time Approximation Schemes for solving the routing problem. The scheduling problem is a solved as a graph edge-coloring problem. We show that this approach guarantees that the solution obtained is within 67% of the optimal solution in the worst case and, in practice, is typically within about 80% of the optimal solution. The approach that we use is quite flexible and is a promising method to handle more sophisticated interference conditions, multiple channels, multiple antennas, and routing with diversity requirements.

Routing with service restorability is of much importance in Multi-Protocol Label Switched (MPLS) networks, and is a necessity in optical networks. For restoration, each connection has an active path and a link-disjoint backup path. The backup path enables service restoration upon active path failure. For bandwidth efficiency, backups may be shared. This requires that at least the aggregate backup bandwidth used on each link be distributed to nodes performing route computations. If this information is not available, sharing is not possible. Also, one scheme in use for restorability in optical networks is for the sender to transmit simultaneously on the two disjoint paths and for the receiver to choose data from the path with stronger signal. This has the advantage of fast receiver-initiated recovery upon failure but it does not allow backup sharing. In this paper, we consider the problem of efficient dynamic routing of restorable connections when backup sharing is not allowed. Our objective is to be able to route as many connections as possible for one-at-a-time arrivals and no knowledge of future arrivals. Since sharing cannot be used for achieving efficiency, the goal is to achieve efficiency by improved path selection. We show that by using the minimum-interference ideas used for nonrestorable routing, we can develop efficient algorithms that outperform previously proposed algorithms for restorable routing such as routing with the min-hop like objective of finding two disjoint paths with minimum total hop-count. We present two new and efficient algorithms for restorable routing without sharing, and one of them requires only shortest path computations. We demonstrate that both algorithms perform very well in comparison to previously proposed algorithms.

The paper presents new algorithms for dynamic routing of restorable bandwidth-guaranteed paths. We assume that connections are requested one-by-one and there is no prior knowledge of future arrivals. In order to guarantee restorability an alternate link (node) disjoint backup (restoration) path has to be determined, as well as an active path, when the connection is initiated. This joint on-line routing problem is particularly important in optical networks and in MPLS networks for dynamic provisioning of bandwidth-guaranteed or wavelength paths. A simple solution is to find two disjoint paths, but this results in excessive resource usage. Backup path bandwidth usage can be reduced by judicious sharing of backup paths amongst certain active paths while still maintaining restorability. The best sharing performance is achieved if the routing of every path in progress in the network is known to the routing algorithm at the time of a new path setup. We give a new integer programming formulation for this problem. Complete path routing knowledge is a reasonable assumption for a centralized routing algorithm, but is not often desirable, particularly when distributed routing is preferred. We show that a suitably developed algorithm which uses only aggregated information, and not per-path information, is able to perform almost as well as one using complete information. Disseminating this aggregate information is feasible using proposed traffic engineering extensions to routing protocols. We formulate the dynamic restorable bandwidth routing problem in this aggregate information scenario and develop efficient routing algorithms. The performance of our algorithm is close to the complete information bound.

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.

This paper presents a new algorithm for dynamic routing of bandwidth guaranteed multicast tunnels with failure backup. The multicast routing problem arises in many contexts such as the routing of point-to-multipoint label switched paths in Multi-Protocol Label Switched (MPLS) networks, and the provision of bandwidth guaranteed services under the "hose" model. Failure backup implies that when a multicast tree is set-up alternate backup paths be also set-up so that the multicast is unaffected by single link or node failures. For dynamic routing, the multicast routing requests arrive one-by-one and there is no a priori knowledge regarding future requests. We believe that this is the first paper that addresses the issue of multicast routing with failure backup. Each multicast request consists of a source s, a set of receivers R, and a bandwidth requirement b. Offline multicast routing algorithms cannot be used since they require a priori knowledge of all multicast tunnel requests that are to be routed. The newly developed algorithm is an on-line algorithm that generates a reserved-bandwidth multicast tree with additional backup links that make the multicast tree resilient to single element failures in the network. It shares backup bandwidth when possible and only uses link usage information obtainable in a distributed manner.

Routing with service restorability is very important in multiprotocol label switched (MPLS) networks, and is a necessity in optical networks. For restoration, each connection has an active path and a disjoint backup path. The backup path enables service restoration upon active path failure. For bandwidth efficiency, backups may be shared. This requires that at least the aggregate backup bandwidth used on each link be distributed to nodes performing route computations. If this information is not available, sharing is not possible. Also, one scheme in use for restorability in optical networks is for the sender to transmit simultaneously on the two disjoint paths and for the receiver to choose data from the path with stronger signal. This has the advantage of fast receiver-initiated recovery upon failure but it does not allow backup sharing. We consider the problem of efficient dynamic routing of restorable connections when backup sharing is not allowed. Our objective is to be able to route as many connections as possible for one-at-a-time arrivals and no knowledge of future arrivals. Since sharing cannot be used for achieving efficiency, the goal is to achieve efficiency by improved path selection. We show that by using the minimum-interference ideas used for non-restorable routing, we can develop efficient algorithms that outperform previously proposed algorithms for restorable routing such as routing with the min-hop like objective of finding two disjoint paths with minimum total hop-count. We present two new and efficient algorithms for restorable routing without sharing, and one of them requires only shortest path computations. We demonstrate that both algorithms perform very well in comparison to previously proposed algorithms.

This paper develops an algorithm for integrated dynamic routing of bandwidth guaranteed paths in IP over WDM networks. By integrated routing, we mean routing taking into account the combined topology and resource usage information at the IP and optical layers. Typically, routing in IP over WDM networks has been separated into routing at the IP layer taking only IP layer information into account, and wavelength routing at the optical layer taking only optical network information into account. The motivation for integrated routing is the potential for better network usage, and this is a topic which has not been been studied extensively. We develop an integrated routing algorithm that determines (1) whether to route an arriving request over the existing topology or whether it is better to open new wavelength paths. Sometimes it is better to open new wavelength paths even if it feasible to route the current demand over the existing IP topology due to previously set-up wavelength paths. 2) For routing over the existing IP-level topology, compute "good" routes. (3) If new wavelength paths are to be set-up, determine the routers amongst which new wavelength paths are to be set-up and compute "good" routes for these new wavelength paths. The performance objective is the accomodation of as many requests as possible without requiring any a priori knowledge regarding future arrivals. The route computations account for the presence or absence of wavelength conversion capabilities at optical crossconnects. We show that the developed scheme performs very well in terms of performance metrics such as the number of rejected demands.

We consider a new QoS routing problem which requires the on-line routing of a bandwidth guaranteed path along with the setting up of bypass paths for every link or node traversed by the primary active path. The bypass paths are used for fast local restoration where upon a link or node failure, the first upstream node re-establishes path continuity (with bandwidth guarantees) by switching to the bypass path for the failed node or link, The routing objective is to minimize the bandwidth usage for each connection so as optimize use of network resources while protecting against single node or link failure. Bandwidth efficiency is achieved by exploiting the potential for inter-demand and intra-demand backup bandwidth sharing. We develop a new algorithm for this routing problem which only uses aggregated link usage information (total bandwidth consumed on each link by active paths, total bandwidth consumed on each link by backup paths, and the residual bandwidths) that is easily obtainable by proposed routing protocol extensions. We show that the algorithm performs well in terms of the number of rejected requests and the total bandwidth used, The main use of this algorithm is for MPLS network routing and for wavelength routing in optical networks with wavelength conversion.

A new generation of ATM switches with more sophisticated cell queueing and scheduling capabilities are becoming available. We discuss an effective approach to connection admission control (CAC) for the real-time variable-bit-rate (rtVBR) service category in an ATM switch with per-VC queueing and scheduling. The quality of service (QoS) requirements for rtVBR are given in terms of the cell loss ratio (CLR) and the cell delay variation (CDV). Given the rtVBR traffic descriptor and QoS parameters, we compute the capacity C/sub rtVBR/ required to support all the ATM virtual circuits (VCs) in the rtVBR category while meeting their QoS requirement. As part of the process of computing C/sub rtVBR/, we also compute a per-VC effective bandwidth used to program the scheduler. We also characterize the admissible region in the 2-class case and show that it is made up of delay-dominant and loss-dominant regions.

This paper presents a new algorithm for dynamic routing of bandwidth-guaranteed tunnels when tunnel routing requests arrive one-by-one and there is no a priori knowledge regarding future requests. This problem is motivated by service provider needs for fast deployment of bandwidth-guaranteed services and the consequent need in backbone networks for fast provisioning of bandwidth-guaranteed paths. Offline routing algorithms cannot be used since they require a priori knowledge of all tunnel 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 tunnel must follow a route that does not "interfere too much" with a route that may be critical to satisfy a future demand. We show that this problem is NP-hard. We then develop a path 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. Like min-hop routing, the presented algorithm uses link-state information and some auxiliary capacity information for path selection. 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.

This paper presents new algorithms for dynamic routing of restorable bandwidth-guaranteed paths. A straightforward solution for the restoration problem is to find two disjoint paths. However, this results in excessive resource usage for backup paths and does not satisfy the implicit service provider requirement of optimizing network resource utilization so as to increase the number of potential future demands that can be routed. We give an integer programming formulation for this problem which is new. Complete path routing knowledge is a reasonable assumption for a centralized routing algorithm. However, it requires maintenance of non-aggregated or per-path information which is not often desirable particularly when distributed routing is preferred. We show that a partial information scenario which uses only aggregated and not per-path information provides sufficient information for a suitably developed algorithm to be able to perform almost as well as the complete information scenario. In this partial information scenario the routing algorithm only knows what fraction of each link's bandwidth, is currently used by active paths, and is currently used by backup paths. Obtaining this information is feasible using proposed traffic engineering extensions to routing protocols. We formulate the dynamic restorable bandwidth routing problem in this partial information scenario and develop efficient routing algorithms. We compare there routing performance of this algorithm to a bound obtained using complete information. Our partial information-based algorithm performs very well and its performance in terms of the number of rejected requests is very close to the full information bound.

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.

This paper presents new algorithms for dynamic routing of bandwidth guaranteed tunnels, where tunnel routing requests arrive one by one and there is no a priori knowledge regarding future requests. This problem is motivated by the service provider needs for fast deployment of bandwidth guaranteed services. Offline routing algorithms cannot be used since they require a priori knowledge of all tunnel requests that are to be rooted. 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 algorithms are on-line algorithms and are based on the idea that a newly routed tunnel must follow a route that does not "interfere too much" with a route that may he critical to satisfy a future demand. We show that this problem is NP-hard. We then develop path selection heuristics which are 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. Like min-hop routing, the presented algorithm uses link-state information and some auxiliary capacity information for path selection. 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. If all nodes are ingress-egress nodes, the algorithm can still be used, particularly to reduce the rejection rate of requests between a specified subset of important ingress-egress pairs. The algorithm performs well in comparison to previously proposed algorithms on several metrics like the number of rejected demands and successful rerouting of demands upon link failure.

We consider how to allocate bandwidth in a multicast tree so as to optimize some global measure of performance. In our model each receiver has a budget to be used for bandwidth reservation on links along its path from the source, and each link has a cost function depending on the amount of total bandwidth reserved at the link by all receivers using that link. We formulate and solve a problem of allocating bandwidth in the multicast tree such that the sum of link costs is minimized.