Networks undergo continuous changes to introduce new services and improve existing ones. Network change deployment involves carefully deciding when each change activity will be executed and who will be executing the change. This is a complex process because each service group has to plan its activities following a set of operational and technological constraints. Besides, multiple groups may be working on the same or dependent nodes at the same time, and they must coordinate their deployment plans. If they do not co-ordinate, conflicting change execution could result in unexpected impacts. Traditionally, change deployment has been a tedious and time-consuming task. To address this, we propose an innovative solution Zapper that aims for minimal human effort to coordinate the changes, minimal risk to service quality, and efficient plans to rapidly deploy the changes. Zapper maps change scheduling constraints into mathematical equations and then uses optimization algorithms to generate conflict-free change plans that satisfy all constraints across service groups. We have deployed Zapper at a large service provider and it is being used regularly by the network operations teams for more than two years to schedule over 4.5 million change activities.

Change management has been a long-standing challenge for network operations. The large scale and diversity of networks, their complex dependencies, and continuous evolution through technology and software updates combined with the risk of service impact create tremendous challenges to effectively manage changes. In this paper, we use data from a large service provider and experiences of their operations teams to highlight the need for quick and easy adaptation of change management capabilities and keep up with the continuous network changes. We propose a new framework CORNET (COmposition fRamework for chaNge managEmenT) with key ideas of modularization of changes into building blocks, flexible composition into change workflows, change plan optimization, change impact verification, and automated translation of high-level change management intent into low-level implementations and mathematical models. We demonstrate the effectiveness of CORNET using real-world data collected from 4G and 5G cellular networks and virtualized services such as VPN and SDWAN running in the cloud as well as experiments conducted on a testbed of virtualized network functions. We also share our operational experiences and lessons learned from successfully using CORNET within a large service provider network over the last three years.

Today's HTTP adaptive streaming applications are designed to provide high levels of Quality of Experience (QoE) across a wide range of network conditions. The adaptation logic in these applications typically needs an estimate of the future network bandwidth for quality decisions. This estimation, however, is challenging in cellular networks because of the inherent variability of bandwidth and latency due to factors like signal fading, variable load, and user mobility. In this paper, we exploit machine learning (ML) techniques on a range of radio channel metrics and throughput measurements from a commercial cellular network to improve the estimation accuracy and hence, streaming quality. We propose a novel summarization approach for input raw data samples. This approach reduces the 90th percentile of absolute prediction error from 54% to 13%. We evaluate our prediction engine in a trace-driven controlled lab environment using a popular Android video player (ExoPlayer) running on a stock mobile device and also validate it in the commercial cellular network. Our results show that the three tested adaptation algorithms register improvement across all QoE metrics when using prediction, with stall reduction up to 85% and bitrate switching reduction up to 40%, while maintaining or improving video quality. Finally, prediction improves the video QoE score by up to 33%.

Streaming over the wireless channel is challenging due to rapid fluctuations in available throughput. Encouraged by recent advances in cellular throughput prediction based on radio link metrics, we examine the impact on Quality of Experience (QoE) when using prediction within existing algorithms based on the DASH standard. By design, DASH algorithms estimate available throughput at the application level from chunk rates and then apply some averaging function. We investigate alternatives for modifying these algorithms, by providing the algorithms direct predictions in place of estimates or feeding predictions in place of measurement samples. In addition, we explore different prediction horizons going from one to three chunk durations. Furthermore, we induce different levels of error to ideal prediction values to analyse deterioration in user QoE as a function of average error.

Robustness and reliability are critical issues in network management. To provide resiliency, a popular protection scheme against network failures is simultaneous routing along multiple paths. The use of Software-Defined Networking (SDN), with fine-grained forwarding rules and the limited forwarding table size of commodity switches, brings a new set of constraints and challenges. In this work, we consider the problem of routing demands with dependability in a software-defined ISP backbone. We propose splitting large demands over multiple paths to reduce fragmentation and achieve service reliability under failures. We also minimize the delay differential among these paths to reduce the number of out-of-order packets. Finally, our routing algorithm works with forwarding tables of bounded size, commonly required by low-cost SDN switches. We report emulation and simulation results confirming the practicality of our solutions.

With recent standardization and deployment of LTE eMBMS, cellular multicast is gaining traction as a method of efficiently using wireless spectrum to deliver large amounts of multimedia data to multiple cell sites. Cellular operators still seek methods of performing optimal resource allocation in eMBMS based on a complete understanding of the complex interactions among a number of mechanisms: the multicast coding scheme, the resources allocated to unicast users and their scheduling at the base stations, the resources allocated to a multicast group to satisfy the user experience of its members, and the number of groups and their membership, all of which we consider in this work. We determine the optimal allocation of wireless resources for users to maximize proportional fair utility. To handle the heterogeneity of user channel conditions, we efficiently and optimally partition multicast users into groups so that users with good signal strength do not suffer by being grouped together with users of poor signal strength. Numerical simulations are performed to compare our scheme to practical heuristics and state-of-the-art schemes. We demonstrate the tradeoff between improving unicast user rates and improving spectrum efficiency through multicast. Finally, we analyze the interaction between the globally fair solution and individual user's desire to maximize its rate. We show that even if the user deviates from the global solution in a number of scenarios, we can bound the number of selfish users that will choose to deviate.

Cellular providers are rapidly deploying multiple technologies like cell biasing, carrier aggregation, co-ordinated interference control/scheduling to improve capacity and coverage. In this paper, we explore a complementary transport layer approach based on multipath TCP that can concurrently use multiple interfaces to boost throughput of users with poor coverage and improve fairness. Multipath TCP has been recently standardized by IETF and requires no modifications to applications. It has been shown to improve fairness and throughput in wire line environments and individual user throughputs in wireless networks. However, in a wireless multi-user environment, it is not clear that it is always beneficial, as we show in this paper. Therefore, we examine if it is indeed beneficial for a service provider to judiciously decide whether to enable multiple cellular interfaces on a smart phone based on a global centralized view of its network. Alternatively, should a device decide independently based only on a local view? To quantify the network wide impact in a system where users have multiple cellular interfaces, we have developed centralized and distributed heuristic algorithms to evaluate this, particularly in the context of fairness across all the users. Our simulations and numerical models show that there are potential gains in fairness (15-30%) to be realized by judiciously enabling multipath connections at the cell edge. These gains diminish as the number of users in a cell increases or users behave greedily. We also quantify the delicate balance between throughput and fairness. Our analysis provides an intuition on which user(s) in a cellular network stand to benefit the most by enabling multiple interfaces. We also discuss LTE protocol mechanisms to enforce associations of specific interfaces to specific cells.

To address reliability challenges due to failures and planned outages, Internet Service Providers (ISPs) typically use two backbone routers (BRs) at each central office. Access routers (ARs) are connected to these BRs in a dual-homed configuration. To provide reliability through node and path diversity, redundant backbone routers and redundant transport equipment to interconnect them are deployed. However, deploying such redundant resources increases the overall cost of the network. Hence, to avoid such redundant resources, a fundamental redesign of the backbone network leveraging the capabilities of an agile optical transport network is highly desired. In this paper, we propose a fundamental redesign of IP backbones. Our alternative design uses only a single router at each office. To survive failures or outages of a single local BR, we leverage the agile optical transport layer to carry traffic to remote BRs. Optimal mapping of local ARs to remote BRs is determined by solving an Integer Linear Program (ILP). We describe how our proposed design can be realized using current optical transport technology. We evaluate network designs for cost and performability, the latter being a metric combining performance and availability. We show significant reduction in cost for approximately the same level of reliability as current designs.

To accommodate the increasing demands for bandwidth, Internet Service Providers (ISPs) have deployed higher-speed links and reconfigurable optical add drop multiplexers (ROADMs) in their backbone networks. To address the reliability challenges due to failures and planned outages, ISPs typically use two backbone routers at each central office in a dual-home configuration. Thus at the IP layer, redundant backbone routers as well as redundant transport equipment to interconnect them are deployed to provide reliability through node and path diversity. However, adding such redundant resources increases the overall cost of the network. Hence, a fundamental redesign of the backbone network which avoids such redundant resources by leveraging the capabilities of an intelligent optical transport network is a highly desirable objective. It is clear that such a redesign must lower costs without compromising on the reliability achieved by today's backbone networks. Modeling the costs and reliability of the network at all layers is an important step in achieving this objective. In this paper, we undertake an in-depth investigation of the cost and reliability considerations involved in designing the next-generation backbone network. Our work includes a detailed analysis of the operation, cost and reliability of the network at the IP layer and the multiple layers below it. We discuss alternative backbone network designs which use only a single router at each central office but use the optical transport layer to carry traffic to routers at other offices in order to survive failures or outages of the single local router. We discuss trade-offs involved in using these designs.

We describe a prototype tool that analyzes combined aspects of reliability and performance for a variety of networks. Our network-wide analysis systematically generates failure scenarios (called network states), maps their effects from the physical to the network to the traffic layer, calculates the probability of each state, and evaluates a metric on it, until the expected value of the metric or a point on its distribution is estimated to sufficient accuracy. We describe an application of this multi-layer probabilistic methodology to dealing with partial link failures in an ISP backbone network.

This work has been motivated by the need to test interoperability of systems carrying voice calls over the IP network. The voice over IP (VoIP) systems must be integrated and interoperate with the existing public switched telephone network (PSTN) before they are widely adopted. Standards have been developed to address this problem, but unfortunately different standards bodies and commercial consortiums have defined different standards. Furthermore, the prevailing VoIP standard such as H.323 is incomplete, complex, and presents the implementers with "vendors latitudes". As a result, there is no guarantee that the integrated VoIP systems would interoperate properly even if the implementations are all H.323-compliant. Thus interoperability testing has become indispensable. We want to test all the system interoperations by exercising all the required patterns of "interoperating behaviors". On the other hand, test execution in real environment is expensive, and we want to minimize the number of tests while maintaining the coverage. We present a general method for automatic generation of test cases, which cover all the required system interoperations and contain a minimal number of tests. We study data structures and efficient test generation algorithms, which take time proportional to the total test case size. Finally, we report experimental results on VoIP systems.

Multi-disk systems, coupled with declustering schemes, have been widely used in various applications to improve I/O performance by enabling parallel disk accesses. A declustering scheme determines how data blocks should be placed among multiple disks to maximize the parallelism. We focus on the problem of declustering grid-structured multidimensional data with the objective of reducing the response time for range queries. Because of the combinatorial nature of the problem, it is not computationally feasible to perform an exhaustive search for the best scheme for large values of $M$ (the number of disks). In this paper, we present an efficient technique for building good-performance declustering schemes for large values of $M$, based on known good declustering schemes for small values of $M$. We analyze the performance of the declustering schemes generated by this hierarchical technique, giving tight bounds on their query response times. For example we show, in two dimensions, that using optimal declustering schemes for $M_1$ and $M_2$ disks we can construct a scheme for $M_1\times M_2$ disks whose response time, expressed in terms of the maximum number of data blocks to be retrieved from any of the disks, is at most five more than the optimal response time. Our technique generalizes to any value of $M$ in two dimensions and selected values of $M$ in higher dimensions. We also present simulation results to show the effectiveness of these schemes in practice.

We propose a new declustering scheme for allocating uniform multidimensional data among parallel disks. The scheme, aimed at reducing disk access time for range queries, is based on Golden Ratio Sequences for two dimensions and Kronecker Sequences for higher dimensions. Using exhaustive simulation, we show that, in two dimensions, the worst-case (additive) deviation of the scheme from the optimal response time for any range query is one when the number of disks (M) is at most 22; its worst-case deviation is two when M /spl les/ 94; and its worst-case deviation is four when M /spl les/ 550. In two dimensions, we prove that whenever M is a Fibonacci number, the average performance of the scheme is within 14 percent of the (generally, unachievable) strictly optimal scheme and its worst-case response time is within a multiplicative factor three of the optimal response time for any query, and within a factor 1.5 of the optimal for large queries. We also present comprehensive simulation results, on two-dimensional as well as on higher-dimensional data, that compare and demonstrate the advantages of our scheme over some recently proposed schemes in the literature.

The problem of fast address lookup is crucial to routing and thus has received considerable attention. Most of the work in this field has focused on improving the speed of individual accesses-independent from the underlying access pattern. Gupta et al. (2000) proposed an efficient data structure to exploit the bias in access pattern. This technique achieves faster lookups for more frequently accessed keys while bounding the worst case lookup time; in fact it is (near) optimal under constraints on worst case performance. However,it needs to be rebuilt periodically to reflect the changes in access patterns, which can be inefficient for bursty environments. In this paper we introduce a new dynamic data structure to exploit biases in the access pattern, which tend to change dynamically. Previous work shows that there are many circumstances under which access patterns change quickly. Our data structure, which we call the biased skip list (BSL), has a self-update mechanism which reflects the changes in the access patterns efficiently and immediately, without any need for rebuilding. It improves throughput while keeping the worst case access time bounded by that of the fastest (unbiased) schemes. We demonstrate the practicality of BSL by experiments on data with varying degrees of burstiness.

Declustering schemes enable parallel data retrieval by placing data blocks across multiple disk devices. Various declustering schemes have been proposed for multidimensional data to reduce the response time of range queries. However, efficient schemes, which must be easy to compute and provide good performance, are only known for a restricted number of disks and dimensions. In this paper, we propose a novel technique to construct efficient multidimensional declustering schemes, for any number of disks and dimensions. Simulation results show that the new schemes outperform the best previously-known non-exhaustive search-based multidimensional declustering schemes.

A dictionary data structure supports efficient search, insert, and delete operations on n keys from a totally ordered universe. Red-black trees, 2-3 trees, AVL trees, skip lists and other classic data structures facilitate O(logn) time search, insert and deletes, matching the information theoretic lower bound when access probabilities are uniform i.i.d. If access probabilities are non-uniform but still i.i.d., there are other weighted data structures such as D-trees, biased search trees, splay trees and treaps which can achieve optimality.

Voice over IP (VoIP) systems have to be integrated and interoperate with the existing telephone network before they become widely adopted. However, different standards have been proposed and the prevailing standard (H.323) is incomplete, complex, and provides the implementers with "vendors latitudes". As a result, there is no guarantee that even H.323-compliant systems would interoperate properly. Interoperability testing has become indispensable. We present techniques for automatic generation of a minimal set of test cases, covering all the required system interoperations. Our algorithms have been implemented and incorporated in a software tool-ITIS. We report experimental results on VoIP systems interoperability testing, using ITIS.

SOCRATES is a software system for testing correctness of implementations of IP routing protocols such as RIP, OSPF and BGP. It uses a probabilistic algorithm to automatically construct random network topologies. For each generated network topology, it checks the correctness of routing table calculation and the IP packet forwarding behavior. For OSPF, it also checks the consistency between network topologies and the link-state databases of router under test. For BGP, it further checks the BGP update redistribution. Being different than commercial testing tools, which select their test cases in an ad-hoc manner, SOCRATES chooses test cases with a guaranteed fault coverage.

We propose a new data declustering scheme for range queries. Our scheme is based on Golden Ratio Sequences (GRS), which have found applications in broadcast disks, hashing, packet routing, etc. We show by analysis and simulation that GRS is nearly the best possible scheme for 2-dimensional range queries. Specifically, it is the best possible scheme when the number of disks (M) is at most 22; has response time at most one more than that of the best possible scheme for M/spl les/94; and has response time at most three more than that of the best possible scheme for M/spl les/550. We also show that it outperforms the cyclic declustering scheme-a recently proposed scheme that was shown to have better performance than previously known schemes for this problem. We give some analytical results to suggest that the average performance of our scheme is within 14 percent of the optimal scheme. Our analytical results also suggest a worst case response time within a factor 3 of the optimal for any query, and within a factor 1.5 of the optimal for large queries. We also give a multidimensional extension of our scheme, which has better performance than the multidimensional generalization of the cyclic declustering scheme.

We study a network model in which each network link is associated with a set of delays and costs. These costs are a function of the delays and reflect the prices paid in return for delay guarantees. Such a cost structure can model a setting in which the service provider provides multiple service classes with a different price and delay guarantee for each class. We are given a source node s, a sink node t, and an end-to-end delay constraint D. Our aim is to choose an s-t path and determine a set of per link delay guarantees along this path so as to satisfy the constraint D while minimizing the total cost incurred. In the case where the s-t path is known, we aim to optimally partition the end-to-end delay constraint into link constraints along the path. We present approximation algorithms for both problems, since they are known to be NP-hard. Our algorithms guarantee to produce solutions that are within a factor 1+/spl epsiv/ of the optimal, where /spl epsiv/ is a parameter of our choice. The run times are polynomial in the input size and 1//spl epsiv/. We also provide a number of heuristics for the second problem and present simulation results. Previous work on related problems either focused on optimal solutions for special cost functions or on heuristics that have no performance guarantees. In contrast, we present provably good approximation algorithms and heuristics which apply to general cost functions.

Declustering schemes enable parallel retrievals of raster-spatial data by allocating data among multiple disks. Previous work in the literature has focused on static range queries. In this paper, we focus on interactive navigation queries, which exhibit a new class of data access patterns. We analyze and compare the performance of previously known declustering schemes from the perspective of navigation queries. These schemes include a class of latin-square-based schemes, Disk Modulo, Fieldwise Exclusive-OR, Hilbert Curve Allocation Method, and a random assignment scheme. We show that, unlike the case of range queries, disk module outperforms other schemes and gives nearly optimal performance for navigation queries. In addition, we propose a new scheme under the constraint of bounded window size-a common constraint in practice due to resource limitation such as monitor resolution or memory size. Through extensive analysis, we establish guidelines on how these schemes can be tuned to provide guaranteed performance under the constraint of bounded window size.

Various declustering techniques have been proposed in the literature for raster-geospatial data. Their primary focus is on reducing response time for static range queries. We focus on interactive navigation queries, which exhibit a new class of data access patterns. We analyze and compare the performance of three well-known declustering schemes: Disk Modulo, Exclusive-OR, and Hilbert Curve Access Method. The results show that Disk Modulo is close to optimal and, contrary to the case of range queries, is significantly better than Hilbert Curve Access Method. In addition, we propose a new scheme that further improves Disk Module for a realistic situation when the navigation window is bounded by a maximum size-a common constraint due to either monitor resolution or limited memory size. Performance properties of the scheme are also analyzed.

The time complexity of several fundamental problems on the sub-bus mesh parallel computer with p processors is investigated. The problems include computing the PARITY and MAJORITY of p bits, the SUM of p numbers of length $O(\log p)$, and the MINIMUM of p numbers. It is shown that in one dimension the time to compute any of these problems is $\Theta (\log p)$. In two dimensions the time to compute any of PARITY, MAJORITY, and SUM is $\Theta (\tfrac{{\log p}} {{\log \log p}})$. It was previously shown that the time to compute MINIMUM in two dimensions is $\Theta (\log \log p)$ [R. Miller et al., IEEE Trans. Comput., 42 (1993), pp. 678–692; L. Valiant, SIAM J. Comput., 4 (1975), pp. 348–355]

In his survey paper on branching programs, A.A. Razborov (1991) asked the following question: Does every rectifier-switching network computing the majority of n bits have size n/sup 1+/spl Omega/(1/)? We answer this question in the negative by constructing a simple oblivious branching program of size O(n log/sup 3/ n/log log n log log log n) for computing any threshold function. This improves the previously best known upper bound of O(n/sup 3/2/) due to O.B. Lupanov (1965).>

Recently, there has been considerable interest in the study of replica-control protocols which are based on organizing several copies of an object into logical structures, such as rectangular grids. In addition to high availability, another objective in exploiting such structures is to improve the degree of load sharing in a system. The authors extend the scope of grid structures to general grids, which allow holes in various positions of a rectangular structure and are useful to consider because they often produce availabilities that are higher than solid grids, where every position must be occupied by a node. In addition to proposing an improvement to the existing grid protocol, new insights are offered into the performance of the grids, from both availability and load sharing points of view. Algorithms for designing grids to maximize availability independently and also in conjunction with a load sharing constraint are given.>