Protocol customizations primarily come in two forms: those driven by public extensions to open standard protocols; and dialecting and performance tuning driven by an enterprise network’s private security and performance needs. Current deployment of protocol customizations is mostly ad hoc, through manual configuration or script programs that are highly specialized to each customization. This method lacks the agility necessary to support the relatively high tempo of private customizations. Also, it is common for today’s protocol customization efforts to experience middlebox interference. We propose a systematic framework of network-wide orchestration and continuous management of protocol customization to enable agile operation for enterprise and data-center networks. By introducing a logically centralized orchestrator along with a Layer 4.5 fine-grained device customization solution, our framework will allow operators to configure, deploy, and monitor customized flows from a single vantage point, providing timely detection of rogue devices as well as real-time coordination of middlebox traversal. Results from prototyping and experimentation confirm utility of our framework while incurring modest processing overhead, at the levels of 3% and 0.5% for sample customized flows and non-customized flows, respectively. Furthermore, we present two major system refinements: (i) generalizing the design of receiving modules to support customization of encrypted flows, and (ii) adding logic system wide to support seamless rotation of customization modules for live flows. Finally, we discuss specific agile network operation use cases enabled by our solution and outline future work.

We demonstrate a system prototype of a new software framework [1] for orchestration and continuous management of protocol customization of selected devices in an enterprise or data-center network. The prototype mainly consists of a network-wide customization orchestrator (NCO) that deploys sample customization modules to a pair of client-server hosts for insertion between the application and transport layers, termed Layer 4.5, and a device customization agent (DCA) installed at each host. In this demo, we show how our system can be used to customize multiple protocols on a client to match different network and server requirements.

Protocol customizations primarily come in two forms: those driven by public extensions to open standard protocols; and dialecting and performance tuning driven by an enterprise network’s private security and performance needs. Current deployment of protocol customizations is mostly ad hoc, through manual configuration or script programs that are highly specialized to each customization. The method lacks the agility necessary to support the relatively high tempo of private customizations. Also, it is common for today’s protocol customization efforts to experience middlebox interference. In this paper, we propose a systematic framework of network-wide orchestration and continuous management of protocol customization for enterprise and data-center networks. By introducing a logically centralized orchestrator along with a layer 4.5 fine-grained device customization solution, our framework will allow operators to deploy and monitor customized flows from a single vantage point, providing timely detection of rogue devices as well as real-time coordination of middlebox traversal. Results from prototyping and experimentation confirm utility of our framework and show that the framework incurs modest processing overhead, at the levels of 3% and 1% for sample customized flows and non-customized flows, respectively.

Software-defined networking (SDN) has become a fundamental technology for data centers and 5G networks. Transport Layer Security (TLS) has been proposed as its single security layer for SDN networks; however, use of TLS is optional and TLS connections between the controller and switches are still vulnerable to downgrade attacks. In this paper, we propose a protocol dialecting approach to provide additional and customizable security assurance for network control messages. We consider and evaluate two dialecting approaches for OpenFlow protocol operation, adding per-message authentication to the SDN control channel that is independent of TLS and provides robustness against downgrade attacks targeting TLS. Furthermore, we measure the performance impact of using these dialecting primitives in a Mininet experiment. The results show a modest increase of communication latency of less than 22%.

The new generations of mobile devices have high processing power and storage, but they lag behind in terms of software systems for big data storage and processing. Hadoop is a scalable platform that provides distributed storage and computational capabilities on clusters of commodity hardware. Building Hadoop on a mobile network enables the devices to run data intensive computing applications without direct knowledge of underlying distributed systems complexities. However, these applications have severe energy and reliability constraints (e.g., caused by unexpected device failures or topology changes in a dynamic network). As mobile devices are more susceptible to unauthorized access, when compared to traditional servers, security is also a concern for sensitive data. Hence, it is paramount to consider reliability, energy efficiency and security for such applications. The MDFS (Mobile Distributed File System) [1] addresses these issues for big data processing in mobile clouds. We have developed the Hadoop MapReduce framework over MDFS and have studied its performance by varying input workloads in a real heterogeneous mobile cluster. Our evaluation shows that the implementation addresses all constraints in processing large amounts of data in mobile clouds. Thus, our system is a viable solution to meet the growing demands of data processing in a mobile environment.

As new network services and middleboxes proliferate, it is important to have reliable means to test these services and devices, and a common practice to generate realistic testing traffic is through replaying previously recorded packet traces. However, existing trace replay tools are highly specialized for particular protocols and scenarios. In this paper, we present a general trace replay tool called DSSR. We show that in a directional trace replay, where outbound and inbound packets are simulated by two (logically) distinct sets of hosts, the timestamps of packets handled by the host(s) simulating external destinations must be adjusted to accurately re-create the effect of network latency. Interestingly, the timestamp adjustment can boost the replay speed. Moreover, we identify the range of timestamp adjustment that will guarantee to preserve the semantic orderings of packets pertaining to client-server protocol interactions. Therefore, our solution provides an effective tuning knob for a user to balance the speed and semantics requirements in a trace replay. Equally important, it requires no clock synchronization between the replaying hosts, as the hosts leverage the arrivals of incoming packets as a clocking mechanism for generating outgoing packets.

Today's integration of mobile technologies and traditional cloud computing exploits the abundant computation and storage resources in the cloud, to enhance the capabilities of end-user mobile devices. The designs that rely on remote cloud services, however, sometimes overlook the abundant resources (e.g., storage, communication, and computation) on mobile devices. In particular, when the remote cloud services are unavailable (due to service downtime or network issues), these smart devices can no longer function. We propose a Heterogeneous Mobile Cloud (HMC) computing design that efficiently utilizes the communication and computation resources to support data storage and data processing services in a group of mobile devices. Each mobile device may have different energy, communication and computation capabilities, but our Mobile Storage & Processing System (MSPS) ensures that: i) the communication and computation tasks are executed in an energy-efficient manner, ii) task allocation considers device heterogeneity and achieves system-wide load balancing, and iii) the stored data are fault-tolerant. Through extensive simulations and real hardware implementations on Android devices, we demonstrate the performance and feasibility of deploying MSPS in a real heterogeneous mobile environment.

The support for safe network updates, i.e., live modification of device behavior without service disruption, is a critical primitive for current and future networks. Several techniques have been proposed by previous works to implement such a primitive. Unfortunately, existing techniques are not generally applicable to any network architecture, and typically require high overhead (e.g., additional memory) to guarantee strong consistency (i.e., traversal of either initial or final paths, but never a mix of them) during the update. In this paper, we deeply study the problem of computing operational sequences to safely and quickly update arbitrary networks. We characterize cases, for which this computation is easy, and revisit previous algorithmic contributions in the new light of our theoretical findings. We also propose and thoroughly evaluate a generic sequence-computation approach, based on two new algorithms that we combine to overcome limitations of prior proposals. Our approach always finds an operational sequence that provably guarantees strong consistency throughout the update, with very limited overhead. Moreover, it can be applied to update networks running any combination of centralized and distributed control-planes, including different families of IGPs, OpenFlow or other SDN protocols, and hybrid SDN networks. Our approach therefore supports a large set of use cases, ranging from traffic engineering in IGP-only or SDN-only networks to incremental SDN roll-out and advanced requirements (e.g., per-flow path selection or dynamic network function virtualization) in partial SDN deployments.

Overlay networking and ISP-assisted tunneling are effective solutions to overcome problematic BGP routes and bypass troublesome autonomous systems. Despite their demonstrated effectiveness, overlay support is not broadly available. In this paper, we propose Cloud-Routed Overlay Networks (CRONets), whereby users can readily build their own overlays using nodes from global and well-provisioned cloud providers like IBM Softlayer or Amazon EC2. While previous studies have demonstrated the benefits of overlay networks with the high-speed experimental Internet2 backbone, we are the first to evaluate the improvements in a realistic -- cloud -- setting. We conduct a large-scale experiment where we observe 6,600 Internet paths. The results show that CRONets improve the throughput for 78% of the default Internet paths with a median and average improvement factors of 1.67 and 3.27 times respectively, at a tenth of the cost of leasing private lines of comparable performance. We also performed a longitudinal measurement, and demonstrate that the performance gains are consistent over time with only a small number of overlay nodes needed to be deployed. However, given the size and dynamic nature of the Internet routing system (e.g., due to congestion and failures), selecting the proper path is still a challenging problem. To address it, we propose a novel solution based on the newly-introduced MPTCP extensions. Our experiments show that MPTCP can achieve the maximum observed throughput across the different overlay paths.

Today, the network design process remains ad hoc and largely complexity agnostic, often resulting in suboptimal networks characterized by excessive amounts of dependence and commands in device configurations. The unnecessary high configuration complexity can lead to a huge increase in both the amount of manual intervention required for managing the network and the likelihood of configuration errors, and thus must be avoided. In this paper, we present an integrated top-down design approach and show how it can minimize the unnecessary configuration complexity in realizing reachability-based access control, a key network design objective that involves designing three distinct network elements: virtual local-area network (VLAN), IP address, and packet filter. Capitalizing on newly developed abstractions, our approach integrates the design of these three elements into a unified framework by systematically modeling how the design of one element may impact the complexity of other elements. Our approach goes substantially beyond the current divide-and-conquer approach that designs each element in complete isolation, and enables minimizing the combined complexity of all elements. Specifically, two new optimization problems are formulated, and novel algorithms and heuristics are developed to solve the formulated problems. Evaluation on a large campus network shows that our approach can effectively reduce the packet filter complexity and VLAN trunking complexity by more than 85% and 70%, respectively, when compared with the ad hoc approach currently used by the operators.

Network operators can and do deploy multiple routing control-planes, e.g., by running different protocols or instances of the same protocol. With the rise of SDN, multiple control-planes are likely to become even more popular, e.g., to enable hybrid SDN or multi-controller deployments. Unfortunately, previous works do not apply to arbitrary combinations of centralized and distributed control-planes. In this paper, we develop a general theory for coexisting control-planes. We provide a novel, exhaustive classification of existing and future control-planes (e.g., OSPF, EIGRP, and Open-Flow) based on fundamental control-plane properties that we identify. Our properties are general enough to study centralized and distributed control-planes under a common framework. We show that multiple uncoordinated control-planes can cause forwarding anomalies whose type solely depends on the identified properties. To show the wide applicability of our framework, we leverage our theoretical insight to (i) provide sufficient conditions to avoid anomalies, (ii) propose configuration guidelines, and (iii) define a provably-safe procedure for reconfigurations from any (combination of) control-planes to any other. Finally, we discuss prominent consequences of our findings on the deployment of new paradigms (notably, SDN) and previous research works.

Despite the advances in hardware for hand-held mobile devices, resource-intensive applications (e.g., video and image storage and processing or map-reduce type) still remain off bounds since they require large computation and storage capabilities. Recent research has attempted to address these issues by employing remote servers, such as clouds and peer mobile devices. For mobile devices deployed in dynamic networks (i.e., with frequent topology changes because of node failure/unavailability and mobility as in a mobile cloud), however, challenges of reliability and energy efficiency remain largely unaddressed. To the best of our knowledge, we are the first to address these challenges in an integrated manner for both data storage and processing in mobile cloud, an approach we call k-out-of-n computing. In our solution, mobile devices successfully retrieve or process data, in the most energy-efficient way, as long as k out of n remote servers are accessible. Through a real system implementation we prove the feasibility of our approach. Extensive simulations demonstrate the fault tolerance and energy efficiency performance of our framework in larger scale networks.

Simultaneously providing flexibility, evolvability and correctness of routing is one of the basic and still unsolved problems in networking. Route redistribution provides a tool, used in many enterprise networks, to either partition a network into multiple routing domains or merge previously independent networks. However, no general technique exists for changing a live network's route redistribution configuration without incurring packet losses and service disruptions. In this paper, we study the problem of how to safely transition between route redistribution configurations. We investigate what anomalies may occur in the reconfiguration process, showing that many long-lasting forwarding loops can and do occur if naive techniques are applied. We devise new sufficient conditions for anomaly-free reconfigurations, and we leverage them to build provably safe and practical reconfiguration procedures. Our procedures enable seamless network re-organizations to accomplish both short-term objectives, such as local repair or traffic engineering, and long-term requirement changes.

The network design process today remains ad-hoc and largely complexity agnostic, often resulting in suboptimal networks characterized by excessive amounts of dependencies and commands in device configurations. The unnecessarily high configuration complexity can lead to a huge increase in both the amount of manual intervention required for managing the network and the likelihood of configuration errors, and thus must be avoided. In this paper we present an integrated top-down design approach and show how it can minimize the unnecessary configuration complexity in realizing user reachability control, a key network design objective that involves designing three distinct network elements: VLAN, IP address, and packet filter. Capitalizing on newly-developed abstractions, our approach integrates the design of the three elements into a unified framework by systematically modeling how the design of one element may impact the complexity of other elements. Our approach goes substantially beyond the current "divide-and-conquer" approach that designs each element in complete isolation, and enables minimizing the combined complexity of all elements. Specifically, two new optimization problems are formulated, and novel algorithms and heuristics are developed to solve the formulated problems. Evaluation on a large campus network shows that our approach can effectively reduce the packet filter complexity and VLAN trunking complexity by more than 85% and 70%, respectively, when compared to the ad-hoc approach currently used by the operators.

Resource Allocation has been widely used for improving various performance metrics in wireless networks. Applying resource allocation to a Mobile Ad Hoc Network (MANET), however, is a challenging problem because of dynamic network topology. In this paper, we develop a novel resource allocation scheme designed for MANETs that minimizes the communication cost for accessing distributed resources while improving the reliability by adopting the k-out-of-n system, a widely used technique for reliability control. Specifically, we propose a scheme that allocates resources to n nodes, called service centers, such that the expected energy consumption for nodes to access k service centers out of the n service centers (k⩽n) is minimized. Our scheme accounts for dynamic network topology by estimating the failure probabilities of nodes and monitoring the network for significant topology changes. In addition, an Importance Sampling technique is used to reduce the computation-overhead. To evaluate the performance, we build a mobile distributed file system based on our resource allocation scheme. Through both extensive simulations and real hardware implementation on Smartphones, we show that our resource allocation scheme effectively reduces energy consumption by up to 45% and increases the successful data retrieval rate by up to 50% in comparison with a greedy algorithm.

With the advance of mobile devices, cloud computing has enabled people to access data and computing resources without spatiotemporal constraints. A common assumption is that mobile devices are well connected to remote data centers and the data centers securely store and process data. However, for systems like mobile cloud deployed in infrastructureless dynamic networks (i.e., with frequent topology changes because of node failure/unavailability and mobility), reliability and energy efficiency remain largely unaddressed challenges. To address these issues, we develop the first 'k-out-of-n computing' framework that ensures nodes retrieve or process data stored in mobile cloud with minimum energy consumption as long as k out of n storage/processing nodes are accessible. We demonstrate the feasibility and performance of our framework through both hardware implementation and extensive simulations.

Enterprise networks often have complex routing designs given the need to meet a wide set of resiliency, security and routing policies. In this paper, we take the position that minimizing design complexity must be an explicit objective of routing design. We take a first step to this end by presenting a systematic approach for modeling and reasoning about complexity in enterprise routing design. We make three contributions. First, we present a framework for precisely defining objectives of routing design, and for reasoning about how a combination of routing design primitives (e.g. routing instances, static routes, and route filters etc.) will meet the objectives. Second, we show that it is feasible to quantitatively measure the complexity of a routing design by modeling individual routing design primitives, and leveraging configuration complexity metrics [5]. Our approach helps understand how individual design choices made by operators impact configuration complexity, and can enable quantifying design complexity in the absence of configuration files. Third, we validate our model and demonstrate its utility through a longitudinal analysis of the evolution of the routing design of a large campus network over the last three years. We show how our models can enable comparison of the complexity of multiple routing designs that meet the same objective, guide operators in making design choices that can lower complexity, and enable what-if analysis to assess the potential impact of a configuration change on routing design complexity.

A variety of network deployments in disaster recovery, fire fighting and military scenarios create networks that do not form a connected network all the time. In such scenarios, paths between a source and destination may be created over time when nodes encounter each other due to node mobility. Many routing algorithms that can route messages in such delay-tolerant networking (DTN) settings have been proposed. Each of these proposals presents simulation and/or analytical results to demonstrate improved performance in comparison with other known protocols. This paper proposes a common framework that defines multiple important components through which performance of these protocols can be compared using simulation experiments. This framework includes performance metrics that can be used for comparison, simulation environment, new mobility models and results in organizing the various known protocols based on their ability to predict a path. In a case study using the framework, we demonstrate how the predictive ability of PROPHET may or may not result in significant performance gains, depending on the mobility model.

This paper investigates the fundamental performance limits of medium access control (MAC) protocols for particular multihop, RF-based wireless sensor networks and underwater sensor networks. A key aspect of this study is the modeling of a fair-access criterion that requires sensors to have an equal rate of underwater frame delivery to the base station. Tight upper bounds on network utilization and tight lower bounds on the minimum time between samples are derived for fixed linear and grid topologies. The significance of these bounds is two-fold: First, they hold for any MAC protocol under both single-channel and half-duplex radios; second, they are provably tight. For underwater sensor networks, under certain conditions, we derive a tight upper bound on network utilization and demonstrate a significant fact that the utilization in networks with propagation delay is larger than that in networks with no propagation delay. The challenge of this work about underwater sensor networks lies in the fact that the propagation delay impact on underwater sensor networks is difficult to model. Finally, we explore bounds in networks with more complex topologies.

Route Aggregation (RA), the method to supersede a set of routes by a single, more general route, is a fundamental mechanism to the Internet scalability. Yet, despite its importance, it is poorly understood. We present the first systematic analysis of RA via both bottom-up experimental and top-down analytical approaches. We first conduct a set of experiments on RA behaviors of all major routing protocols as implemented by the two leading router vendors. Our experiments show that the RA behaviors vary significantly across routing protocols and vendors. We propose two router level primitives and incorporate them into a canonical router model. The new model captures the diversity of the observed behaviors. With aid of the model, we have advanced the fundamental understanding of RA on three fronts. First, we expose four new types of routing anomaly that can derive from RA. Configuring RA on one router interface can influence how routes are advertised on other interfaces of the same router, impacting network reachability in surprising ways. Second, we demonstrate that determining whether a RA configuration can result in persistent forwarding loops is NP-complete. Finally, we present sufficient conditions for RA primitives to guarantee routing safety, and explore clean-slate designs for RA.

Enterprise networks are important, with size and complexity even surpassing carrier networks. Yet, the design of enterprise networks remains ad hoc and poorly understood. In this paper, we show how a systematic design approach can handle two key areas of enterprise design: virtual local area networks (VLANs) and reachability control. We focus on these tasks given their complexity, prevalence, and time-consuming nature. Our contributions are threefold. First, we show how these design tasks may be formulated in terms of network-wide performance, security, and resilience requirements. Our formulations capture the correctness and feasibility constraints on the design, and they model each task as one of optimizing desired criteria subject to the constraints. The optimization criteria may further be customized to meet operator-preferred design strategies. Second, we develop a set of algorithms to solve the problems that we formulate. Third, we demonstrate the feasibility and value of our systematic design approach through validation on a large-scale campus network with hundreds of routers and VLANs.

Current large-scale topology mapping systems require multiple days to characterize the Internet due to the large amount of probing traffic they incur. The accuracy of maps from existing systems is unknown, yet empirical evidence suggests that additional fine-grained probing exposes hidden links and temporal dynamics. Through longitudinal analysis of data from the Archipelago and iPlane systems, in conjunction with our own active probing, we examine how to shorten Internet topology mapping cycle time. In particular, this work develops discriminatory primitives that maximize topological fidelity while being efficient.

Recent studies have shown that the current primitives for connecting multiple routing protocol instances (OSPF 1, OSPF 2, EIGRP 10, etc.) are pervasively deployed in enterprise networks and the Internet. Furthermore, these primitives are extremely vulnerable to routing anomalies (route oscillations, forwarding loops, etc.) and at the same time too rigid to support some of today's operational objectives. In this paper, we propose a new theory to reason about routing properties across multiple routing instances. The theory directly applies to both link-state and vector routing protocols. Each routing protocol still makes independent routing decisions and may consider a combination of routing metrics, including bandwidth, delay, cost, and reliability. While the theory permits a range of solutions, we focus on a design that requires no changes to existing routing protocols. Guided by the theory, we derive a new set of connecting primitives, which are not only provably safe but also more expressive than the current version. We have implemented and validated the new primitives using XORP. The results confirm that our design can support a large range of desirable operational goals, including those not achievable today, safely and with little manual configuration.

This paper investigates fundamental performance limits of medium access control (MAC) protocols for particular underwater multi-hop sensor networks under a fair-access criterion requiring that sensors have an equal rate of underwater frame delivery to a base station. Tight upper bounds on network utilization and tight lower bounds on minimum time between samples are derived for fixed linear topology. The paper also examines the implication of the end-to-end performance bounds regarding the traffic rate and sensing time interval of individual sensors.

The nine papers in this special issue focus on network infrastructure configuration and some of the problems encountered in the areas of specification, diagnosis, repair, synthesis, and anonymization.

A repository of router configuration files from production networks would provide the research community with a treasure trove of data about network topologies, routing designs, and security policies. However, configuration files have been largely unobtainable precisely because they provide detailed information that could be exploited by competitors and attackers. This paper describes a method for anonymizing router configuration files by removing all information that connects the data to the identity of the underlying network, while still preserving the structure of information that makes the data valuable to networking researchers. Anonymizing configuration files has unusual requirements, including preserving relationships between elements of data, anonymizing regular expressions, and robustly coping with more than 200 versions of the configuration language. Conventional tools and techniques are poorly suited to the problem. Our anonymization method has been validated with a major carrier, earning unprivileged researchers access to the configuration files of thousands of routers in hundreds of networks. Through example analysis, we demonstrate that the anonymized data retains the key properties of the network design. The paper sets out techniques that could be used in an attempt to break the anonymization, and it concludes our anonymization techniques are most applicable to enterprise networks, because the large number of enterprises and the difficulty of probing them from the outside make it hard to recognize an anonymized network based solely on publicly-available information about its topology or configuration. When applied to backbone networks, which are few in number and many of whose properties can be publicly measured, the anonymization might be broken by fingerprinting techniques described in this paper.

Today, a large body of research exists regarding the correctness of routing protocols. However, many reported global disruptions of Internet connectivity, e.g., inter-AS persistent loops, cannot be explained by looking at a single routing protocol at a time. In fact, these anomalies have long been suspected in the operator community to be caused by the interactions between routing protocols. The interactions between protocol instances are governed by two procedures at the border routers: route selection (RS) ranks routes from different protocol instances; and route redistribution (RR) exchanges routes between protocol instances. Prior studies hypothesized that RR may be responsible for a portion of the observed anomalies. In this paper, we provide analytical and experimental results to link RS, RR, and their interplay to anomalies discovered in operational networks. We show that RS by itself can cause route oscillations and loops, and that in all Cisco, Quagga, and XORP implementations, non-deterministic behaviors may occur because of their incorrect modeling of the dependencies between RS and RR. We identify the root cause for each of the instabilities and derive a configuration guideline as well as a functional model to eliminate them.

Enterprise networks are important, with size and complexity even surpassing carrier networks. Yet, the design of enterprise networks is ad-hoc and poorly understood. In this paper, we show how a systematic design approach can handle two key areas of enterprise design: virtual local area networks (VLANs) and reachability control. We focus on these tasks given their complexity, prevalence, and time-consuming nature. Our contributions are three-fold. First, we show how these design tasks may be formulated in terms of network-wide performance, security, and resilience requirements. Our formulations capture the correctness and feasibility constraints on the design, and they model each task as one of optimizing desired criteria subject to the constraints. The optimization criteria may further be customized to meet operator-preferred design strategies. Second, we develop a set of algorithms to solve the problems that we formulate. Third, we demonstrate the feasibility and value of our systematic design approach through validation on a large-scale campus network with hundreds of routers and VLANs.

Recent studies reveal that the routing structures of operational networks are much more complex than a simple BGP/IGP hierarchy, highlighted by the presence of many distinct instances of routing protocols. However, the glue (how routing protocol instances interact and exchange routes among themselves) is still little understood or studied. For example, although Route Redistribution (RR), the implementation of the glue in router software, has been used in the Internet for more than a decade, it was only recently shown that RR is extremely vulnerable to anomalies similar to the permanent route oscillations in BGP. This paper takes an important step toward understanding how RR is used and how fundamental the role RR plays in practice. We developed a complete model and associated tools for characterizing interconnections between routing instances based on analysis of router configuration data. We analyzed and characterized the RR usage in more than 1600 operational networks. The findings are: (i) RR is indeed widely used; (ii) operators use RR to achieve important design objectives not realizable with existing routing protocols alone; (iii) RR configurations can be very diverse and complex. These empirical discoveries not only confirm that the RR glue constitutes a critical component of the current Internet routing architecture, but also emphasize the urgent need for more research to improve its safety and flexibility to support important design objectives.

This paper investigates fundamental performance limits of medium access control (MAC) protocols for multi-hop sensor networks. A unique aspect of this study is the modeling of a fair-access criterion requiring that sensors have an equal rate of frame delivery to the base station. Tight upper bounds on network utilization and tight lower bounds on minimum time between samples are derived for fixed linear and grid topologies. The significance of these bounds is two-fold: First, they are universal, i.e., they hold for any MAC protocol. Second, they are provably tight, i.e., they can be achieved by a version of time division multiple access (TDMA) protocol that is self-clocking, and therefore does not require system-wide clock synchronization. The paper also examines the implication of the end-to-end performance bounds regarding the traffic rate and sensing time interval of individual sensors.

Route redistribution (RR) has become an integral part of IP network design as the result of a growing need for disseminating certain routes across routing protocol boundaries. While RR is widely used and resembles BGP in several nontrivial aspects, surprisingly, the safety of RR has not been systematically studied by the networking community. This paper presents the first analytical model for understanding the effect of RR on network wide routing dynamics and evaluating the safety of a specific RR configuration. We first illustrate how easily inaccurate configurations of RR may cause severe routing instabilities, including route oscillations and persistent routing loops. At the same time, general observations regarding the root causes of these instabilities are provided. We then introduce a formal model based on the general observations to represent and study the safety of route redistribution. Using the model, we prove that given a RR configuration, determining whether the redistributions result in a cycle is NP-hard. Given this complexity, we present a sufficient condition, which can be checked in polynomial time with the proposed analytical model, for ensuring the safety of a RR configuration. Finally, the paper proposes potential changes to the current RR protocol to guarantee safety.

The primary purpose of a network is to provide reachability between applications running on end hosts. In this paper, we describe how to compute the reachability a network provides from a snapshot of the configuration state from each of the routers. Our primary contribution is the precise definition of the potential reachability of a network and a substantial simplification of the problem through a unified modeling of packet filters and routing protocols. In the end, we reduce a complex, important practical problem to computing the transitive closure to set union and intersection operations on reachability set representations. We then extend our algorithm to model the influence of packet transformations (e.g., by NATs or ToS remapping) along the path. Our technique for static analysis of network reachability is valuable for verifying the intent of the network designer, troubleshooting reachability problems, and performing "what-if" analysis of failure scenarios.

A repository of router configuration files from production networks would provide the research community with a treasure trove of data about network topologies, routing designs, and security policies. However, configuration files have been largely unobtainable precisely because they provide detailed information that could be exploited by competitors and attackers. This paper describes a method for anonymizing router configuration files by removing all information that connects the data to the identity of the originating network, while still preserving the structure of information that makes the data valuable to networking researchers. Anonymizing configuration files has unusual requirements, including preserving relationships between elements of data, anonymizing regular expressions, and robustly coping with more than 200 versions of the configuration language, that mean conventional tools and techniques are poorly suited to the problem. Our anonymization method has been validated with a major carrier, earning unprivileged researchers access to the configuration files of more than 7600 routers in 31 networks. Through example analysis, we demonstrate that the anonymized data retains the key properties of the network design. We believe that applying our single-blind methodology to a large number of production networks from different sources would be of tremendous value to both the research and operations communities.

In any IP network, routing protocols provide the intelligence that takes a collection of physical links and transforms them into a network that enables packets to travel from one host to another. Though routing design is arguably the single most important design task for large IP networks, there has been very little systematic investigation into how routing protocols are actually used in production networks to implement the goals of network architects. We have developed a methodology for reverse engineering a coherent global view of a network's routing design from the static analysis of dumps of the local configuration state of each router. Starting with a set of 8,035 configuration files, we have applied this method to 31 production networks. In this paper we present a detailed examination of how routing protocols are used in operational networks. In particular, the results show the conventional model of interior and exterior gateway protocols is insufficient to describe the diverse set of mechanisms used by architects, and we provide examples of the more unusual designs and examine their trade-offs. We discuss the strengths and weaknesses of our methodology, and argue that it opens paths towards new understandings of network behavior and design.

Most application data units are too large to be carried in a single packet (or cell) and must be segmented for network delivery. To an application, the end-to-end delays and loss rate of its data units are much more relevant performance measures than ones specified for individual packets (or cells). The concept of a burst (or block) was introduced to represent a sequence of packets (or cells) that carry an application data unit. We describe how a real-time variable bit-rate (VBR) service, with quality of service (QoS) parameters for block transfer delay and block loss rate, can be provided by integrating concepts and delay guarantee results from our previous work on burst scheduling, together with ideas from asynchronous transfer mode (ATM) block transfer. Two new contributions are presented herein. First, we design an admission control algorithm to provide the following two classes of service: bounded-delay block transfer with no loss, and bounded-delay block transfer at a specified block loss rate. Secondly, we show how to extend existing end-to-end delay bounds to networks with hierarchical link sharing.

We present an admission control framework and loss management techniques in support of a guaranteed statistical service. The service is characterized by (i) the loss rate of application data units (ADUs) bounded below a specified value, and (ii) ADU losses distributed evenly among flows subscribing to the service and uniformly over the duration of each flow. Specifically, a flow is modeled as a sequence of bursts, each of which is a sequence of packets that carry the bits of an ADU. The first packet of each burst carries information on the ADU (e.g., its bandwidth requirement). This traffic model enables admission control at the burst level as well as at the flow level. Such a two level admission control approach is very effective in bounding end-to-end ADU loss rates of flows while maintaining high channel utilization in the network. The traffic model also enables simple techniques that can be used at a network channel to distribute ADU losses evenly among flows subscribing to the same statistical service, and to protect high priority ADUs (e.g., 1 frames of MPEG applications).

Most application-level data units are too large to be carried in a single packet (or cell) and must be segmented for network delivery. To an application, the end-to-end delays and loss rate of its data units are much more relevant performance measures than ones specified for individual packets (or cells). The concept of a burst (or block) was introduced to represent a sequence of packets (or cells) that carry an application data unit. In this paper, we describe how a real-time VBR service, with quality of service parameters for block transfer delay and block loss rate, can be provided by integrating concepts and delay guarantee results from our previous work on burst scheduling, together with ideas from ATM block transfer. Two new contributions are presented. First, we design an admission control algorithm to provide the following classes of service: bounded-delay block transfer with no loss, and bounded-delay block transfer at a specified block loss rate. Second, we show how to extend existing end-to-end delay bounds to networks with hierarchical link sharing.

We present an end-to-end delay guarantee theorem for a class of guaranteed deadline (GD) servers. The theorem can be instantiated to obtain end-to-end delay bounds for a variety of source control mechanisms and GD servers. We then propose the idea of group priority, and specialize the theorem to a subclass of GD servers that use group priority in packet scheduling. With the use of group priority, the work of packet schedulers can be substantially reduced. We work out a detailed example, for the class of burst scheduling networks, to illustrate how group sizes can be designed such that the worst case end-to-end delay of application data units in a real-time flow is unaffected by the use of group priority. Group priority also can be used in packet schedulers that provide integrated services (best effort as well as real-time services) to achieve statistical performance gains, which we illustrate with empirical results from simulation experiments.

For many service disciplines that provide delay guarantees, the scheduler of a channel repeatedly searches for the smallest element in a set of priority values (or deadlines). It is required that each search finishes within a time bound. Furthermore, the search algorithm should be highly efficient. To meet these requirements, we have developed a search algorithm based upon a new data structure, called adaptive heap; it behaves like a heap most of the time, but adaptively changes its strategy when necessary to satisfy the time bound. We show that the algorithm has an optimal worst-case time complexity and a good average performance. To further improve the efficiency, the basic algorithm is extended to include the use of group scheduling. We present empirical results on the performance of adaptive heap search with and without group scheduling. We conclude that adoptive heap search performs as intended, and that group scheduling provides a substantial reduction in the scheduler's work when channel utilization is high.

For many applications, the end-to-end delay of an application-specific data unit is a more important performance measure than the end-to-end delays of individual packets within a network. From this observation, we propose the idea of group scheduling. Specifically, consecutive packet arrivals in a flow are partitioned into groups, and the same deadline (called group priority) is assigned to every packet in a group. We first present an end-to-end delay guarantee theorem for a network of guaranteed-deadline (GD) servers. The theorem can be instantiated to obtain end-to-end delay bounds for a variety of source control mechanisms and GD servers. We then specialize the delay guarantee theorem to group scheduling for a subclass of GD servers. We work out a detailed example to demonstrate how to use group scheduling in a particular class of networks. The advantages of group scheduling are discussed and illustrated with empirical results from simulation experiments.

In a packet switching network, each communication channel is statistically shared among many traffic flows that belong to different end-to-end sessions. We present and prove a delay guarantee for the virtual clock service discipline (inspired by time division multiplexing). The guarantee has several desirable properties, including the following firewall property: the guarantee to a flow is unaffected by the behavior of other flows sharing the same server. There is no assumption that sources are flow controlled or well behaved. We first introduce and define the concept of an active flow. The delay guarantee is then formally stated as a theorem. We show how to obtain delay bounds from the delay guarantee of a single server for different specifications.