Network slicing was adopted as a solution for future networks to support various applications with diverse requirements. While active research has focused on this functionality, most of the work targets RAN or packet core slicing and leaves the transport network nearly untouched. With packet core functions moving to data centers and parts of RAN functions moving to edge clouds, the transport network will gain significantly more importance. To ensure stringent service level agreements (SLAs) and facilitate slice management, it is imperative for the transport network to support live slice mobility with no disruption of current services. In this paper, we present FestNet, a Flexible and Efficient Sliced Transport Network, achieved by our virtualized Programmable Data Plane (vPDP) and two-layer design. Not only conventional protocols but also stateless and stateful network functions (NFs) can be integrated as slices in FestNet. We implemented a FestNet prototype. Our evaluation shows that FestNet supports live slice migration with no packet loss and no state loss for stateful slices and that FestNet provides many times faster slice operations than implementations in related work.

5G technologies promise to revolutionize mobile networks and push them to the limits of resource utilization. Besides better capacity, we also need better resource management via virtualization. End-to-end network slicing not only involves the core but also the Radio Access Network (RAN) which makes this a challenging problem. This is because multiple alternative radio access technologies exist (e. g. ,LTE, WLAN, and WiMAX), and there is no unifying abstraction to compare and compose from diverse technologies. In addition, existing work assumes that all RAN infrastructure exists under a single administrative domain. Software-Defined Radio Access Network (SD-RAN) offers programmability that facilitates a unified abstraction for resource sharing and composition across multiple providers harnessing different technology stacks. In this paper we propose a new architecture for heterogeneous RAN slicing across multiple providers. A central component in our architecture is a service orchestrator that interacts with multiple network providers and service providers to negotiate resource allocations that are jointly optimal. We propose a double auction mechanism that captures the interaction among selfish parties and guarantees convergence to optimal social welfare in finite time. We then demonstrate the feasibility of our proposed system by using open source SD-RAN systems such as EmPOWER (WiFi) and FlexRAN (LTE).

Softwarization enables tremendous flexibility for networks as the use of software-defined networking (SDN) and programmable data planes (e.g. P4) together support dynamic reconfiguration of networks in real-time, in response to network conditions and new service requests. In such networks, it is imperative to ensure that end-to-end network services continue to satisfy SLAs, especially performance requirements. However, in the presence of unpredictable dynamics due to network reconfigurations, it is not possible to guarantee prior to deployment that a service will meet such SLAs. Run-time verification - in combination with programmable control and data plane monitoring - can provide a basis for detecting potential performance SLA violations, together with identifying and executing appropriate network mitigations. In this paper, we propose a verification transverse based on formal specifications, that spans performance SLAs across the distributed SDN control and programmable data planes, and can coordinate with both planes to execute dynamic reconfiguration that mitigate the detected issues. We demonstrate a proof-of-concept prototype based on an extension of the Aerial run-time verification tool, together with the Inband Network Telemetry (INT) capability, on a network running distributed ONOS controllers together with a P4 data plane.

One of the biggest emerging challenges for telco operators is to dynamically create new services while maintaining the network at its optimal performance/revenue break point. To this end, operators are moving to a much leaner cloud-based Software Defined Network (SDN) infrastructure to achieve a truly programmable network fabric. While cloud services can be provisioned in seconds and tested in-production, service provisioning in SDNs still lasts many weeks and requires substantial manual effort. A large part of this service creation time can be attributed to testing and tuning the control plane. In this paper we present SCP-CLUB (SDN Control Plane CLoUd-based Benchmarking), a platform for in-production performance testing of telco operator SDNs, offering a level of automation as available in deploying cloud services. Telco cloud SDN performance testing with SCP-CLUB focuses on the analysis of how design choices in the cloud and SDN control planes influence SLA metrics like throughput and latency. We describe the SCP-CLUB architecture and its performance testing support capabilities. Experiments are performed on an SDN telco cloud built to demonstrate SCP-CLUB under production load conditions.

For interconnection between geographically-separated data centers, network carriers typically implement multiple optical paths in a wide-area network. For example, when transmission wavelengths have 100 Gb/s granularity, three 100 Gb/s wavelength paths are provisioned to satisfy a customer demand of 300 Gb/s. Over the multiple provisioned paths, interconnection traffic is typically distributed using per-flow hashing, which results in an uneven distribution of traffic caused by hash collisions. For a relatively-few number of high-bandwidth traffic flows (> 1 Gb/s) between data center locations, per-flow hashing can perform poorly in terms of bandwidth utilization and availability. We propose new software-defined traffic load balancer, SD-TLB, that performs measurement-based flow distribution over multiple optical paths, with an implicit impairment detection method using per-port statistics on available paths and a flow redistributor that is immediately adjusted to the current network state. While our approach does not provide the same level of protection as 1+1 optical protection, it can provide the necessary redundancy for data center inter-connection at a lower cost. We experimentally implement the SD-TLB using ASIC-based switches and open virtual switches interconnected by wavelength-division multiplexed transport network test-bed. The experimental results show that SD-TLB outperforms today's hashing-based alternatives in balancing, throughput, and restoration in the presence of outages and impairments and as a result achieves improved cost-efficiency.

In future mobile networks, e.g., 5G, emerging IoT services are expected to support billions of IoT devices with unique characteristics and traffic patterns. In this paper we propose an SDN-based IoT Mobile Edge Cloud Architecture (SIMECA1) which can deploy diverse IoT services at the mobile edge by leveraging distributed, lightweight control and data planes optimized for IoT communications. We prototyped our architecture using a pre-commercial mobile networking software stack to demonstrate the feasibility and utility of our approach.

Continued scaling of switching capacity in the Internet core is threatened by power considerations. Internet service providers face increased carbon footprint and operational costs, while router manufacturers encounter upper limits on switching capacity per rack. This paper studies the role of packet buffer memory on the power consumption of backbone routers. Our first contribution is to estimate from published datasheets the energy costs of static RAM/dynamic RAM packet-buffer memory, showing that it accounts for over 10% of power consumption in a typical router line-card; we then show, using empirical data from core and enterprise networks, that much of this memory is used for only a small fraction of time. Our second contribution is to develop a simple yet practical algorithm for putting much of the memory components to sleep and waking them as needed, while being able to control resulting traffic performance degradation in the form of packet loss during transient congestion. Finally, we conduct a comprehensive evaluation of our scheme, via analytical models pertaining to long-range-dependent traffic, using simulations of offline traffic traces taken from carrier/enterprise networks as well as online Transmission Control Protocol flows in ns2, and by implementing our scheme on a programmable-router test bed. This paper is the first to show the feasibility of, and energy savings from, dynamic management of packet buffer memory in core routers in the market today.

We conduct a comprehensive measurement study of switch control plane latencies using four types of production SDN switches. Our measurements show that control actions, such as rule installation, have surprisingly high latency, due to both software implementation inefficiencies and fundamental traits of switch hardware. We also propose three measurement-driven latency mitigation techniques---optimizing route selection, spreading rules across switches, and reordering rule installations---to effectively tame the flow setup latencies in SDN.

We study a class of robust network design problems motivated by the need to scale core networks to meet increasingly dynamic capacity demands. Past work has focused on one of two models. First, design the network for the known point-to-point peak demands. Second, design the network to support all hose matrices (all matrices not exceeding marginal bounds at the nodes). Both models may be too conservative if additional information on traffic patterns is available. We introduce a capped hose model to explore a range of traffic scenarios, which includes the above two as special cases. It is known that optimal network designs for the hose model are always determined by single-hub routing, and for the fixed-demand model are based on shortest-path routing. We demonstrate that a wider variety of routing templates is required to address the broader spectrum of capped hose matrices. We propose the use of hierarchical multihub routing templates, a generalization of hub and tree routing. Our empirical analysis is based on a heuristic for the resulting robust network design problem. These lead to two important findings: 1) designs based on multihub routing are often preferable to both hub and shortest path; 2) it may be possible for a carrier to sample their traffic in order to determine which type of routing is most cost-effective for their network.

We study a class of robust network design problems motivated by the need to scale core networks to meet increasingly dynamic capacity demands. Past work has focused on designing the network to support all hose matrices (all matrices not exceeding marginal bounds at the nodes). This model may be too conservative if additional information on traffic patterns is available. Another extreme is the fixed demand model, where one designs the network to support peak point-to-point demands. We introduce a capped hose model to explore a broader range of traffic matrices which includes the above two as special cases. It is known that optimal designs for the hose model are always determined by single-hub routing, and for the fixed-demand model are based on shortest-path routing. We shed light on the wider space of capped hose matrices in order to see which traffic models are more shortest path-like as opposed to hub-like. To address the space in between, we use hierarchical multi-hub routing templates, a generalization of hub and tree routing. In particular, we show that by adding peak capacities into the hose model, the single-hub tree-routing template is no longer cost-effective. This initiates the study of a class of robust network design (RND) problems restricted to these templates. Our empirical analysis is based on a heuristic for this new hierarchical RND problem. We also propose that it is possible to define a routing indicator that accounts for the strengths of the marginals and peak demands and use this information to choose the appropriate routing template. We benchmark our approach against other well-known routing templates, using representative carrier networks and a variety of different capped hose traffic demands, parameterized by the relative importance of their marginals as opposed to their point-to-point peak demands. This study also reveals conditions under which multi-hub routing gives improvements over single-hub and shortest-path routings.

To cope with the phenomenal growth of the Internet over the next decade, core networks are expected to scale to capacities of terabits-per-second and beyond. Increasing the role of optics for switching and transmission inside the core network seems to be the most promising way forward to accomplish this capacity scaling. Unfortunately, unlike electronic memory, it remains a formidable challenge to build even a few packets of integrated all-optical buffers. In this context, we envision a bufferless (or near-zero buffer) core optical network and make three contributions: First, we propose a novel edge-to-edge based packet-level forward error correction (FEC) scheme that combats packet loss in the bufferless core, and characterise the impact of FEC strength on loss at a single link. Second, we develop a global optimisation framework for multi-hop networks, and propose a heuristic algorithm that adjusts FEC strength to achieve fairness amongst the different single- and multi-hop flows. Finally, we evaluate the performance of our FEC scheme for realistic mixes of short- and long-lived TCP flows, and show that edge-to-edge packet-level FEC can be tuned to effectively mitigate contention losses in the core, thus opening the doors to bufferless optical networks in the near future.

Smart Grid applications are imposing challenging requirements of security and reliability on the N-way communication infrastructure being designed to support multiple grid applications. These challenges stem from the increasing incorporation of distributed renewable energy sources on to the grid, the rising deployment of electric vehicles, and active consumer participation into power grid operations, all of which communicate with the utility control center with varying degrees of priority and security. To address these challenging requirements, we propose SeDAX, a SEcure Data-centric Application eXtensible platform for Smart Grid applications. SeDAX implements scalable, resilient and secure data delivery and data sharing in a wide area network. The platform can scalably handle high volumes of data generated by both applications and sensors. The SeDAX architecture has as its basis a Delaunay Triangulation (DT) network. The properties of the DT graph are leveraged to scalably support secure data-centric (or information-centric) group communication. The primary goals of this platform are to support communication resilience and data availability. The key functional blocks of the SeDAX platform are: (1) a geographic hash forwarding algorithm that operates over the DT graph (DT-GHF), and (2) a DT-based data replication scheme. The forwarding and replication schemes are scalable and cost effective in terms of communication overhead and memory. We describe the design details of the SeDAX platform and present empirical results on the performance of SeDAX as compared with other geometric-based alternatives such as Geographic Hash Table (GHT) forwarding and Content Addressable Networking (CAN). The operation of SeDAX is illustrated in the context of implementing demand response, a known Smart Grid application.

Multiparty interactive network applications such as teleconferencing, network gaming, and online trading are gaining popularity. In addition to end-to-end latency bounds, these applications require that the delay difference among multiple clients of the service is minimized for a good interactive experience. We propose a Latency EQualization (LEQ) service, which equalizes the perceived latency for all clients participating in an interactive network application. To effectively implement the proposed LEQ service, network support is essential. The LEQ architecture uses a few routers in the network as hubs to redirect packets of interactive applications along paths with similar end-to-end delay. We first formulate the hub selection problem, prove its NP-hardness, and provide a greedy algorithm to solve it. Through extensive simulations, we show that our LEQ architecture significantly reduces delay difference under different optimization criteria that allow or do not allow compromising the per-user end-to-end delay. Our LEQ service is incrementally deployable in today's networks, requiring just software modifications to edge routers.

Reducing the power consumption of core Internet routers is important for both Internet Service Providers (ISPs) and router vendors. ISPs can reduce their Carbon footprint and operational costs, while router manufacturers can achieve higher switching capacity per rack space. In this work, we examine the impact of packet buffers on the power consumption of backbone router line-cards. We argue that Gigabytes of always-on SRAM and DRAM buffers account for around 10% of the power, but are actively used only during transient periods of congestion. We propose a simple and practical algorithm for activating buffers incrementally as needed and putting them to sleep when not in use. We evaluate our algorithm on traffic traces from carrier and enterprise networks, via simulations in ns2, and by implementing it on a programmable-router test-bed. Our study shows that much of the energy associated with off-chip packet buffers can be eliminated with negligible impact on traffic performance. Dynamic adjustment of active router buffer size provides a low-complexity low-risk mechanism of saving energy that is amenable for incremental deployment in networks today.

The rapid increase in Internet traffic is forcing packet routers to grow in capacity to meet the demand. Optical packet routers with less buffering and a greater degree of optical transparency are actively being researched as a way to improve energy efficiency and capacity scaling over traditional electronic routers. Since it is difficult to buffer packets in the optical domain, in this paper we analyze the performance of a hybrid optoelectronic packet router. The router architecture has multiple optical switch planes and a shared electronic buffer to resolve output-port contention. By using multiple ports on the switch planes for each input and output fiber, and by using some switch-plane ports to inter-connect the planes, we can achieve a relatively low packet loss ratio in a router with no buffer. In this case, most traffic can be switched using only the through optical paths of the router without entering the shared buffer. The shared electronic buffer is primarily used to reduce the packet drop ratio under periods of heavy loads and occasionally for optical regeneration of a packet.We run extensive simulations to evaluate the performance of the router with varying number of switch plane ports, number of connections to the electronic buffer, and number of interconnections between the switch planes. We show that the router can provide good throughput, with realistic on-off bursty traffic and asynchronous packet arrivals.

Internet traffic is expected to grow phenomenally over the next five to ten years, and to cope with such large traffic volumes, core networks are expected to scale to capacities of terabits-per-second and beyond. Increasing the role of optics for switching and transmission inside the core network seems to be the most promising way forward to accomplish this capacity scaling. Unfortunately, unlike electronic memory, it remains a formidable challenge to build even a few packets of integrated all-optical buffers. In the context of envisioning a bufferless (or near-zero buffer) core network, our contributions are threefold: First, we propose a novel edge-to-edge based packet-level forward error correction (FEC) framework as a means of combating high core losses, and investigate via analysis and simulation the appropriate FEC strength for a single core link. Second, we consider a realistic multi-hop network and develop an optimisation framework that adjusts the FEC strength on a per-flow basis to ensure fairness between single-and multi-hop flows. Third, we study the efficacy of FEC for various system parameters such as relative mixes of short-lived and long-lived TCP flows, and average offered link loads. Our study is the first to show that packet-level FEC, when tuned properly, can be very effective in mitigating high core losses, thus opening the doors to a bufferless core network in the future.

The importance of border gateway protocol (BGP) as the primary interautonomous system (AS) routing protocol that maintains the connectivity of the Internet imposes stringent stability requirements on its route selection process. Accidental and malicious activities such as misconfigurations, failures, and worm attacks can induce severe BGP instabilities leading to data loss, extensive delays, and loss of connectivity. In this work, we propose an online instability detection architecture that can be implemented by individual routers. We use statistical pattern recognition techniques for detecting the instabilities, and the algorithm is evaluated using real Internet data for a diverse set of events including misconfiguration, node failures, and several worm attacks. The proposed scheme is based on adaptive segmentation of feature traces extracted from BGP update messages and exploiting the temporal and spatial correlations in the traces for robust detection of the instability events. Furthermore, we use route change information to pinpoint the culprit ASes where the instabilities have originated.

Unbounded growth in the number of active flows can lead to severe service quality degradation to existing flows in a network . To guarantee minimum service quality for individual flows, specially for multimedia traffic, it is necessary to estimate and bound the number of active flows in the network. Prior work on estimating the number of active flows has been difficult without maintaining per-flow state. In this paper, we propose a light weight (not requiring per flow state) mechanism to estimate the number of active flows. This estimate is then used to determine the probability of admitting a new flow into the network with the goal of preventing extreme degradation of throughput to existing flows. The key idea here is that the number of active flows can be inferred from the frequency at which a newly arriving packet is part of the same flow as a randomly selected packet in the buffer. Since this scheme relies on information already available in the buffer, no per-flow state is maintained in the network. This mechanism requires very little per-packet processing, even less than a forwarding table lookup. Simulation results show that the proposed scheme can stabilize an overloaded network by bounding the number of active flows without significantly impairing link utilization. This scheme also gives good performance when buffer sizes are small and when the network has a mix of TCP and UDP traffic.

Being the primary interdomain routing protocol, border gateway protocol (BGP) is the singular means of path establishment across the Internet. Therefore, misconfiguration errors in BGP routers result in failure to establish paths which in turn can cause several networks to become unreachable. In this paper, we first analyze data from recent BGP tables to show that misconfiguration errors occur very frequently in the Internet today. We then show theoretically and using real-world events the impact of these errors on routing stability. A scheme for real-time isolation of large-scale BGP misconfiguration events is then proposed in this paper. Our methodology is based on statistical techniques and is evaluated using data from past wellknown misconfiguration events. We show the effectiveness of our method as compared to the current state-of-the-art.

The issue of router buffer sizing is still open and significant. Previous work either considers open-loop traffic or only analyzes persistent TCP flows. This paper differs in two ways. First, it considers the more realistic case of non-persistent TCP flows with heavy-tailed size distribution. Second, instead of only looking at link metrics, we focus on the impact of buffer sizing on TCP performance. Specifically, our goal is to find the buffer size that maximizes the average per-flow TCP throughput. Through a combination of testbed experiments, simulation, and analysis, we reach the following conclusions. The output/input capacity ratio at a network link largely determines the required buffer size. If that ratio is larger than one, the loss rate drops exponentially with the buffer size and the optimal buffer size is close to zero. Otherwise, if the output/input capacity ratio is lower than one, the loss rate follows a power-law reduction with the buffer size and significant buffering is needed, especially with flows that are mostly in congestion-avoidance. Smaller transfers, which are mostly in slow-start, require significantly smaller buffers. We conclude by revisiting the ongoing debate on "small versus large" buffers from a new perspective.

Valiant's concept of randomized load balancing (RLB), also promoted under the name 'two-phase routing', has previously been shown to provide a cost-effective way of implementing overlay networks that are robust to dynamically changing demand patterns. RLB is accomplished in two steps; in the first step, traffic is randomly distributed across the network, and in the second step traffic is routed to the final destination. One of the benefits of RLB is that packets experience only a single stage of routing, thus reducing queueing delays associated with multi-hop architectures. In this paper, we study the queuing performance of RLB, both through analytical methods and packet-level simulations using ns2 on three representative carrier networks. We show that purely random traffic splitting in the randomization step of RLB leads to higher queuing delays than pseudo-random splitting using, e.g., a round-robin schedule. Furthermore, we show that, for pseudo-random scheduling, queuing delays depend significantly on the degree of uniformity of the offered demand patterns, with uniform demand matrices representing a provably worst-case scenario. These results are independent of whether RLB employs priority mechanisms between traffic from step one over step two. A comparison with multi-hop shortest-path routing reveals that RLB eliminates the occurrence of demand-specific hot spots in the network.

A number of events such as hurricanes, earthquakes, power outages can cause large-scale failures in the Internet. These in turn cause anomalies in the interdomain routing process. The policy-based nature of border gateway protocol (BGP) further aggravates the effect of these anomalies causing severe, long lasting route fluctuations. In this work we propose an architecture for anomaly detection that can be implemented on individual routers. We use statistical pattern recognition techniques for extracting meaningful features from the BGP update message data. A time-series segmentation algorithm is then carried out on the feature traces to detect the onset of an instability event The performance of the proposed algorithm is evaluated using real Internet trace data. We show that instabilities triggered by events like router mis-configurations, infrastructure failures and worm attacks can be detected with a false alarm rate as low as 0.0083 alarms per hour. We also show that our learning based mechanism is highly robust as compared to methods like exponentially weighted moving average (EWMA) based detection.

Abstract — With the increasing commercial interest in supporting voice and multimedia services over the IP network there is a need for bandwidth guaranteed services. For example, guaranteeing the peak demand of VoIP traffic entails high costs in terms of bandwidth reservation requirements. To effectively make use of the reserved peak bandwidth, it is imperative that this bandwidth is shared with best effort data traffic during non peak periods. In this paper, we formulate this bandwidth sharing network design problem. Our goal is to minimize the total cost of bandwidth reservation while satisfying (1) the peak demand for real time traffic, and (2) the average demand of both real time and best effort data traffic. We show that, the problem is polynomially solvable if we do not restrict the number of paths used. It is strongly NP-hard if we use only one path between any pair of nodes. We present a simple 2-approximation algorithm and through simulation studies show that this algorithm can be further improved using a local search heuristic. Our simulation results also show that sharing significantly reduces the total bandwidth reservation costs and our local search heuristic can find a solution which is very close to or equal to the optimal in most cases.

Abstract — The need to monitor real time network services has prompted service providers to use new measurement technologies, such as service-specific probes. Service-specific probes are active probes that closely mimic the service traffic so that it receives the same treatment from the network as the actual service traffic. These probes are end-to-end and their deployment depends on solutions that address questions such as minimizing probe traffic, while still obtaining maximum coverage of all the links in the network. In this paper, we provide a polynomial-time probe-path computation algorithm, as well as a-approximate solution for merging probe paths when the number of probes exceed a required bound�. Our algorithms are evaluated using ISP topologies generated via Rocketfuel. We find that for most topologies, it is possible to cover more than��of the edges using just�of the nodes as terminals. Our work also suggests that the deployment strategy for active probes is dependent on cost issues, such as probe installation, probe set-up, and maintenance costs. I.

In third-generation (3G) wireless data networks, repeated requests for popular data items can exacerbate the already scarce wireless spectrum. In this paper, we propose an architectural and protocol framework that allows 3G service providers to host efficient content distribution services. We offload the spectrum intensive task of content distribution to an ad hoc network. Less mobile users (resident subscribers) are provided incentives to cache popular data items, while mobile users (transit subscribers) access this data from resident subscribers through the ad hoc network. Since the participants of this data distribution network act as selfish agents, they may collude to maximize their individual payoff. Our proposed protocol discourages potential collusion scenarios. In this architecture, the goal (social function) of the 3G service provider is to have the selfishly motivated resident subscribers service as many data requests as possible. However, the choice of which set of items to cache is left to the individual user. The caching activity among the different users can be modeled as a market sharing game. In this work, we study the Nash equilibria of market sharing games and the performance of such equilibria in terms of a social function. These games are a special case of congestion games that have been studied in the economics literature. In particular, pure strategy Nash equilibria for this set of games exist. We give a polynomial-time algorithm to find a pure strategy Nash equilibrium for a special case, while it is NP-hard to do so in the general case. As for the performance of Nash equilibria, we show that the price of anarchy-the worst case ratio between the social function at any Nash equilibrium and at the social optimum-can be upper bounded by a factor of 2. When the popularity follows a Zipf distribution, the price of anarchy is bounded by 1.45 in the special case where caching any item has a positive reward for all players. We prove that the selfish behavior of computationally bounded agents converges to an approximate Nash equilibrium in a finite number of improvements. Furthermore, we prove that, after each agent computes its response function once using a constant factor approximation algorithm, the outcome of the game is within a factor of O(logn) of the optimal social value, where n is the number of agents. Our simulation scenarios show that the price of anarchy is 30% better than that of the worst case analysis and that the system quickly (1 or 2 steps) converges to a Nash equilibrium.

The ever increasing complexity of networks dramatically increases the challenges faced by service providers to analyze network behavior and (re)provision resources to support multiple complex distributed applications. Accurate and scalable simulation tools are pivotal to this cause. The recently proposed hybrid systems model for data communication networks shows promise in achieving performance characteristics comparable to fluid models while retaining the accuracy of discrete models. Using the hybrid systems paradigm, this paper provides contributions to the modeling of TCP behavior and the analysis/simulation of data communication networks based on these models. An important distinguishing feature of our simulation framework is a faithful accounting of link propagation delays which has been ignored in previous work for the sake of simplicity. Other salient aspects of the work include a new finite state machine model for a drop-tail queue, a new model for fast recovery/fast retransmit mode, a revised sending rate model, and an embedded time-out mode transition mechanism all of which employ a time-stepped solution method to solve the hybrid system network models. Our simulation results are consistent with well-known packet based simulators such as ns-2, thus demonstrating the accuracy of our hybrid model. Our future efforts will be directed towards studying and improving the computational performance of hybrid model based simulations.

The increasing incidence of worm attacks in the Internet and the resulting instabilities in the global routing properties of the border gateway protocol (BGP) routers pose a serious threat to the connectivity and the ability of the Internet to deliver data correctly. In this paper we propose a mechanism to detect/predict the onset of such instabilities which can then enable the timely execution of preventive strategies in order to minimize the damage caused by the worm. Our technique is based on online statistical methods relying on sequential change-point and persistence filter based detection algorithms. Our technique is validated using a year's worth of real traces collected from BGP routers in the Internet that we use to detect/predict the global routing instabilities corresponding to the Code Red II, Nimda and SQL Slammer worms.

Evolving monitoring infrastructure in response to network growth is a critical aspect of network management. Previous work in network management primarily focused on optimizing monitoring systems for static networks. In this paper, we address the problem of optimally upgrading the existing monitoring infrastructure as the network evolves. The problem formulation presented here captures the trade off between adding new monitoring resources vs. disrupting the existing infrastructure. We show that this problem is NP hard and not approximable within a factor better than n/sup /spl epsi// in the general case and no better than log(n) when only shortest paths are considered. We develop a heuristic algorithm and evaluate its performance using simulated network evolution scenarios. We show that in spite of not allowing poller relocation, our adaptive online algorithm has comparable performance to that of the offline algorithm where such constraint does not exist.

The recent reduction in telecommunications spending has increased the importance of network planning to improve the return on investment on the existing network infrastructures. Therefore, tools that help in maximizing the bandwidth efficiency of the network at a minimum cost are essential. Previous work in this area focused on increasing bandwidth efficiency and reliability. In this work, in addition to increasing the bandwidth efficiency, we address the complexity of network management and operations. This issue is explicitly addressed by our novel framework, a simple polynomial time algorithm (SimPol) that achieves optimum network performance (in terms of congestion or bandwidth consumption) using only a small number of paths. The problem formulation is based on splittable multicommodity flows. Using SimPol we show that the total number of paths is at most k+m, where k and m are the numbers of demands and edges in the network, respectively. We extend the basic framework into an integer programming formulation to address the tradeoff between network congestion and the total number of paths. We also use SimPol to address the problem of implementing path/link policies such as bandwidth-limited paths. The performance of SimPol is evaluated through extensive simulations. Using the integer programming approach, we can get exactly one path while losing about 10% to 50% in congestion depending on the number of demands. This congestion is, however, far better than the traditional shortest path routing. The framework is general and can be used in capacity planning for transport networks such as MPLS and ATM.

In third generation (3G) wireless data networks, repeated requests for popular data items can exacerbate the already scarce wireless spectrum. In this paper we propose an architectural and protocol framework that allows 3G service providers to host efficient content distribution services. We offload the spectrum intensive task of content distribution to an ad-hoc network. Less mobile users (resident subscribers) are provided incentives to cache popular data items while mobile users (transit subscribers) access this data from resident subscribers through the ad-hoc network. Since the participants of this data distribution network act as selfish agents, they may collude to maximize their individual payoff. Our proposed protocol discourages potential collusion scenarios. In this architecture the goal (social function) of the 3G service provider is to have the selfishly motivated resident subscribers service as many data requests as possible. However, the choice of which set of items to cache is left to the individual user. The caching activity among the different users can be modeled as a market sharing game. In this work, we study the Nash equilibria of market sharing games and the performance of such equilibria in terms of a social function. These games are a special case of congestion games that have been studied in the economics literature. In particular, pure strategy Nash equilibria for this set of games exist. We give a polynomial-time algorithm to find a pure strategy Nash equilibrium for a special case while it is is NP-Hard to do so in the general case. As for the performance of Nash equilibria, we show that the price of anarchy -- the worst-case ratio between the social function at any Nash equilibrium and at the social optimum -- can be upper bounded by a factor of 2. When the popularity follows a Zipf distribution, the price of anarchy is bounded by 1.45 in the special case where caching any item has a positive reward for all players. We prove that the selfish behavior of computationally bounded agents converges to an approximate Nash equilibrium in a finite number of improvements. Furthermore, we show that even with one improvement by each player, an O(log n) approximate solution can be obtained. Our simulation scenarios show that the price of anarchy is 30% better than that of the worst-case analysis and that the system quickly (1 or 2 steps) converges to a Nash equilibrium.

Designing optimal measurement infrastructure is a key step for network management. In this work we address the problem of optimizing a scalable distributed polling system. The goal of the optimization is to reduce the cost of deployment of the measurement infrastructure by identifying a minimum poller set subject to bandwidth constraints on the individual links. We show that this problem is NP-hard and propose three different heuristics to obtain a solution. We evaluate our heuristics on both hierarchical and flat topologies with different network sizes under different polling bandwidth constraints. We find that the heuristic of choosing the poller that can poll the maximum number of unpolled nodes is the best approach. Our simulation studies show that the results obtained by our best heuristic is close to the lower bound obtained using LP relaxation.

Faults can be classified using information contained in the MIB variables. It is observed that distinct changes in the MIB data characteristics precede different fault types. Previous work has shown that network faults can be predicted using MIB data. Now with the possibility of classifying faults, network alarms can be associated with specific fault types. Associating a network alarm with a specific network fault is an essential pre-requisite for automated recovery. In our current work we describe the classification of four different faults: network access problems, protocol implementation error, runaway process and file server failures. We also show that a simple discriminant function scheme that accounts for spatial correlations in the MIB data performs better than common majority-voting schemes.

Network fault management is a difficult task due to the lack of accurate definitions for the different types of faults. In this work we attempt to characterize network faults by studying their effects on the statistics of network traffic. The evolution of networks in terms of size and variety of network components and services makes it difficult to understand the dynamics of the traffic. Instead, by describing network fault behavior in terms of the changes they effect on the statistics of network traffic, we can develop algorithms to detect or predict network faults. The advantage is the independence of fault descriptions from symptom-specific feature vectors and the availability of historical data.

Prediction of network failures at the router level has been achieved using an intelligent agent. The intelligent agent gathers relevant MIB data from the router and provides temporally and spatially correlated predictive alarms. The time correlated abnormal changes in the individual MIB variables are spatially correlated using a novel combining scheme. The agent was implemented on a real network and seven out of nine faults were predicted. Two typical case studies are presented. The prediction time was of the order of minutes.