The concept of Software-Defined Networking (SDN) has been successfully applied to data centers and campus networks but it has had little impact in the fixed wireline and mobile telecom domain. Although telecom networks demand fine-granular flow definition, which is one of SDN's principal strengths, the scale of these networks and their legacy infrastructure constraints considerably limit the applicability of SDN principles. Instead, telecom networks resort to tunneling solutions using a plethora of specialized gateway nodes, which create high operation cost and single points of failure. We propose extending the concept of SDN so that it can tackle the challenges of the telecom domain. We see vertical forwarding, i.e. programmable en- and decapsulation operations on top of IF, as one of the fundamental features to be integrated into SDN. We discuss how vertical forwarding enables flow-based policy enforcement, mobility and security by replacing specialized gateways with virtualized controllers and commoditized forwarding elements, which reduces cost while adding robustness and flexibility.

Quantiles are very useful in characterizing the data distribution of an evolving dataset in the process of data mining or network monitoring. The method of Stochastic Approximation (SA) tracks quantiles online by incrementally deriving and updating local approximations of the underly distribution function at the quantiles of interest. In this paper, we propose a generalization of the SA method for quantile estimation that allows not only data insertions, but also dynamic data operations such as deletions and updates.

Line-rate data traffic monitoring in high-speed networks is essential for network management. To satisfy the line-rate requirement, one can leverage multi-core architectures to parallelize traffic monitoring so as to improve information processing capabilities over traditional uni-processor architectures. Nevertheless, realizing the full potential of multi-core architectures still needs substantial work, especially in the face of the ever-increasing volume and complexity of network traffic. This paper addresses the issue through the design of a lock-free, cache-efficient synchronization mechanism that serves as a basic building block for a general class of multithreaded, multi-core traffic monitoring applications. We embed the synchronization mechanism into MCRingBuffer, a multi-core shared ring buffer that provides fast data accesses among threads running in different cores. MCRingBuffer allows concurrent lock-free data accesses and improves the cache locality of accessing the control variables that are used for thread synchronization. Through extensive evaluation on an Intel Xeon multi-core machine, we show that MCRingBuffer achieves a throughput gain of up to 5× over existing lock-free ring buffers. Finally, we present a parallel traffic monitoring prototype that is built upon MCRingBuffer, and demonstrate via trace-driven simulation how MCRingBuffer facilitates packet processing at line rate.

We propose MCRingBuffer, a lock-free, cache-efficient shared ring buffer that provides fast data accesses among threads running in multi-core architectures. MCRingBuffer seeks to reduce the cost of inter-core communication by allowing concurrent lock-free data accesses and improving the cache locality of accessing control variables used for thread synchronization. Evaluation on an Intel Xeon multi-core machine shows that MCRingBuffer achieves a throughput gain of up to 4.9x over existing concurrent lock-free ring buffers. A motivating application of MCRingBuffer is parallel network traffic monitoring, in which MCRingBuffer facilitates multi-core architectures to process packets at line rate.

In this paper, we develop an online monitoring methodology for the time-varying cyclical streams of network data, that combines a baseline state-space model and statistical control schemes to monitor departures from the baseline model. Parameters of the state space models are initialized based on the training data, and updated for each incoming observation. The statistical control schemes for monitoring are designed based on forecasting errors from the baseline model, under the framework of statistical change detection. We demonstrate the effectiveness of our methodology using measurement data from an EVDO wireless network.

The Internet host cardinality, defined as the number of distinct peers that an Internet host communicates with, is an important metric for profiling Internet hosts. Some example applications include behavior based network intrusion detection, p2p hosts identification, and server identification. However, due to the tremendous number of hosts in the Internet and high speed links, tracking the exact cardinality of each host is not feasible due to the limited memory and computation resource. Existing approaches on host cardinality counting have primarily focused on hosts of extremely high cardinalities. These methods do not work well with hosts of moderately large cardinalities that are needed for certain host behavior profiling such as detection of p2p hosts or port scanners. In this paper, we propose an online sampling approach for identifying hosts whose cardinality exceeds some moderate prescribed threshold, e.g. 50, or within specific ranges. The main advantage of our approach is that it can filter out the majority of low cardinality hosts while preserving the hosts of interest, and hence minimize the memory resources wasted by tracking irrelevant hosts. Our approach consists of three components: 1) two-phase filtering for eliminating low cardinality hosts, 2) thresholded bitmap for counting cardinalities, and 3) bias correction. Through both theoretical analysis and experiments using real Internet traces, we demonstrate that our approach requires much less memory than existing approaches do whereas yields more accurate estimates.

Knowing the traffic matrix, i.e., packet/byte counts between pairs of nodes in a network, is important for network management. The main challenges for accurate traffic matrix estimation in a high speed network are the computation and memory limitations. In this paper, we propose a novel algorithm for traffic matrix estimation that can yield accurate estimates whereas uses small memory and per packet update overhead. Our algorithm constructs a compact probabilistic traffic digest at each network node, and derives a Quasi Maximum Likelihood Estimate (Quasi-MLE) of the traffic matrix by correlating the traffic digests received at a central location. Our new approach is highly efficient, requiring no prior knowledge of the exact packet size distributions. We derive accurate approximation of the relative error distribution of our estimate. For an origin- destination (OD) pair (o,d), we show that by using an array of size M for each traffic digest at o and d, the relative estimation standard error is O(M-1/2(sigmao+sigmad)1/2), where sigmao,sigmadare the noise-to-signal ratios, defined as the ratios of non-OD packet/byte counts to OD packet/byte counts at the origin and destination. This is superior to the state-of-the-art algorithms, especially for large sigmaoand sigmad, where the estimation is more challenging. We further demonstrate the effectiveness of our approach using both model and real Internet trace-driven simulations.

Identification of significant patterns in network traffic, such as IPs or flows that contribute large volume (heavy hitters) or introduce large changes (heavy changers), has many applications in accounting and network anomaly detection. As network speed and the number of flows grow rapidly, tracking per-IP or per-flow statistics becomes infeasible due to both the computational overhead and memory requirements. In this paper, we propose a novel sequential hashing scheme that requires only O(H log N) both in memory and computational overhead that are close to being optimal, where N is the the number of all possible keys (e.g., flows, IPs) and H is the maximum number of heavy keys. Moreover, the generalized sequential hashing scheme makes it possible to trade off among memory, update cost, and detection cost in a large range that can be utilized by different computer architectures for optimizing the overall performance. In addition, we also propose statistically efficient algorithms for estimating the values of heavy hitters and heavy changers. Using both theoretical analysis and experimental studies of Internet traces, we demonstrate that our approach can achieve the same accuracy as the existing methods do but using much less memory and computational overhead.

Network tomography has been regarded as one of the most promising methodologies for performance evaluation and diagnosis of the massive and decentralized Internet. It can be used to infer unobservable network behaviors from directly measurable metrics and it does not require cooperation between the network internal elements and the end users. For instance, the Internet users may estimate the link level characteristics such as loss and delay from end-to-end measurements, whereas the network operators can evaluate the Internet path-level traffic intensity based on link-level traffic measurements. In this paper, we present a novel estimation approach for the network tomography problem. Unlike previous likelihood based methods, our approach is based on characteristic functions, i.e. the Fourier transform, of the distributions of observed measurements. We focus on network delay tomography and develop a Fourier domain inference algorithm based on flexible mixture models of link delays. Through extensive model simulation and simulation using real Internet trace, we are able to demonstrate that the new algorithm is computationally more efficient and yields more accurate estimates than previous methods, especially for a network with heterogeneous link delays. In addition, we obtain some identifiability results that can be applied to general distribution models for link delays.

Third generation (3G) wireless networks based on the CDMA2000 and UMTS standards are now increasingly being deployed throughout the world. Because of their complex signaling and relatively limited bandwidth, these 3G networks are generally more vulnerable than their wireline counterparts, thus making them fertile ground for new attacks. In this paper, we identify and study a novel denial of service (DoS) attack, called signaling attack, that exploits the unique vulnerabilities of the signaling/control plane in 3G wireless networks. Using simulations driven by real traces, we are able to demonstrate the impact of a signaling attack. Specifically, we show how a well-timed low-volume signaling attack can potentially overload the control plane and detrimentally affect the key elements in a 3G wireless infrastructure. The low-volume nature of the signaling attack allows it to avoid detection by existing intrusion detection algorithms, which are often signature or volume-based. As a counter-measure, we present and evaluate an online early detection algorithm based on the statistical CUSUM method. Through the use of extensive trace-driven simulations, we demonstrate that the algorithm is robust and can identify an attack in its inception, before significant damage is done.

Abstract — Fast spreading worms are a reality, as amply demonstrated by worms such as Slammer, which reached its peak propagation in a matter of minutes. With these kinds of fast spreading worms, the traditional approach of signature-based detection is no longer sufficient. Specifically, these worms can infect all vulnerable hosts well before a signature is available. To counter them, we must devise fast detection algorithms that can detect new worms without signatures as they first begin to appear. We present the design and evaluation of such an algorithm in this paper. The key to the algorithm is the identification of certain invariant characteristics of worm propagation. Specifically, we are able to demonstrate using real network traces how worm propagation can perturb the arrival process distribution of unsolicited packets. Our algorithm employs a novel two-step procedure that combines a first stage change point detection with a second stage growth rate inference to confirm the existence of aworm. To evaluate the algorithm, we have applied it to multi-year network traces that cover many of the major worm outbreaks in recent years, including Slammer, Witty, Nimda and Blaster. In all cases, the new algorithm is able to detect the worm within a very short time, well before significant infection has taken place. I.

In 3G data networks, network operators would like to balance system throughput while serving users in a fair manner. This is achieved using the notion of proportional fairness. However, so far, proportional fairness has been applied at each base station independently. Such an approach can result in non-Pareto optimal bandwidth allocation when considering the network as a whole. Therefore, it is important to consider proportional fairness in a network-wide context with user associations to base stations governed by optimizing a generalized proportional fairness objective. In this paper, we take the first step in formulating and studying this problem rigorously. We show that the general problem is NP-hard and it is also hard to obtain a close-to-optimal solution. We then consider a special case where multi-user diversity only depends on the number of users scheduled together. We propose efficient offline optimal algorithms and heuristic-based greedy online algorithms to solve this problem. Using detailed simulations based on the base station layout of a large service provider in the U.S., we show that our simple online algorithm, which assigns a newly arrived user to a base station that improves the generalized proportional fairness objective the most without changing existing users ’ association, is very close to the offline optimal solution. The greedy algorithm can achieve significantly better throughput and fairness in heterogeneous user distributions, when compared to the approach that assigns a user to the base station with the best signal strength.

IP-based radio access networks (RAN) are expected to be the next generation access networks in UMTS and CDMA networks. The question of connectivity, i.e., how best to connect base stations to the radio network controllers (RNC) in an IP-based RAN, has not been addressed by researchers. Furthermore, given a connection configuration, an RNC selection algorithm that assigns an incoming call to an RNC is also necessary. This paper examines RAN connectivity and its impact on the performance and resiliency of the wireless network using different RNC selection algorithms. For homogeneous networks, we show that the proposed min-load-1 algorithm, which allows at most one hard handoff in order to accommodate each incoming call request, delivers performance close to the optimal algorithm. We also show that allowing a few base stations to connect to two RNCs (a 10 percent increase in the number of links in our network) results in resiliency to RNC failures that is comparable to the resiliency of RANs with full-mesh connectivity. Finally, for heterogeneous networks, we show that the min-load-k algorithm (with at most k hard handoffs per call) is effective in handling load imbalances. These results provide strong motivation for deploying IP-based RAN, as they suggest that enhancing current point-to-point RAN with few additional links and allowing a few hard handoffs to accommodate incoming calls can result in significant gains in performance and resiliency.

In third generation (3G) cellular networks, base stations are connected to base station controllers by point-to-point (usually T1/E1) links. However, today's T1/E1 based buck haul network is not a good match for next generation wireless networks because symmetric T1s is not an efficient way to carry bursty and asymmetric data traffic. In this paper, we propose designing an IEEE 802.16-based wireless radio access network to carry the traffic from the base station to the radio network controller. 802.16 has several characteristics that make it a better match for 3G radio access networks including its support for time division duplex mode that supports asymmetry efficiently. In this paper, we tackle the following question; given a layout of base stations and base station controllers, how do we design the topology of the 802.16 radio access network connecting the base stations to the base station controller that minimizes the number of 802.16 links used while meeting the expected demands of traffic from/to the base stations? We make three contributions: we first show that finding the optimal solution to the problem is NP-hard. We then provide heuristics that perform close to the optimal solution. Finally, we address the reliability issue of failure of 802.16 links or nodes by designing algorithms to create topologies that can handle single failures effectively.

An attack-resistant network is a purpose-built network to survive attacks; by construction, it should be both resilient and secure. Resiliency is the ability to provide alternative communication paths should one path become disrupted due to failures or attacks; while security is the ability to contain and limit the impact of compromises. Interestingly, these two can present conflicting demands. We provide a first formulation of a new class of problems focusing on the engineering of attack-resistant networks. Our model considers both resiliency and security, and uses a notion of blocking probability as a rigorous measure for evaluating different network constructions. We propose several efficient approximation algorithms for computing blocking probability and provide bounds for their errors. Based on these algorithms, we introduce a family of heuristics to guide the construction of optimal attack-resistant networks with minimum blocking probabilities. We also present extensive results to evaluate and demonstrate the near-optimal performance of our heuristics and approximation algorithms.

IP-based radio access networks (RAN) are expected to be the next generation access networks in UMTS and CDMA networks. There are several benefits of IP-based RAN including lower costs, flexibility of merging wired and wireless networks, and network scalability and reliability. While quality of service issues in IP-based RAN have been addressed by a number of researchers, the question of connectivity, i.e., how best to connect base stations to the radio network controllers (RNC) in an IP-based RAN, has not been addressed by any research literature. Furthermore, given a connection configuration, an RNC selection algorithm that assigns an incoming call to an RNC is also necessary. This paper examines radio access network (RAN) connectivity and its impact on the performance and resiliency of the wireless network using different RNC selection algorithms. The proposed min-load-1 algorithm, which allows at most one hard hand off in order to accommodate each incoming request, delivers performance close to the standard Min-Load algorithm using a RAN of much higher connectivity and is close to the optimal algorithm using the same RAN. We also find that using min-load-1 algorithm and allowing the base stations to connect to two RNCs result in resiliency to RNC failures that is similar to having full-mesh connectivity between base stations and RNCs

BGP routing table sizes have increased by an order of magnitude over the last six years. This dramatic growth can decrease packet forwarding speed and demand more router memory space. We explore the extent that various factors contribute to the routing table size and characterize the growth of each contribution. We begin with a measurement study using the routing tables of an Oregon route views server to determine the contributions of multi-homing, load balancing, address fragmentation, and failure-to-aggregate to routing table size. Address fragmentation makes the greatest contribution and it is three times those of multihoming or load balancing. The contribution of failure-to-aggregate is the least. Although multihoming and load balancing contribute less to routing table size than address fragmentation, we observe that their contributions grow faster than the routing table does and that load balancing has surpassed multihoming, becoming the fastest growing contributor. Moreover, we find that both load balancing and multihoming contribute to routing table growth by introducing more prefixes of length between 17 and 25, which are the fastest growing prefixes. Next, we examine the growth routable IP addresses, and conclude that their growth is much slower than that of routing table size. Lastly, we demonstrate that our findings based on views derived from the Oregon server are accurate through an evaluation using 15 additional routing tables collected from different locations in the Internet.

Recent work has shown that the node degree in the WWW induced graph and the autonomous system (AS) level Internet topology exhibit power laws. Since then, several algorithms have been proposed to generate such power law graphs. We evaluate the effectiveness of these generators to generate representative AS-level topologies. Our conclusions are mixed. Although they (mostly) do a reasonable job at capturing the power law exponent, they do less well in capturing the clustering phenomena exhibited by the Internet topology. Based on these results, we propose a variation of the recent incremental topology generator of R. Albert and A. Barabasi (see Phys. Rev. Letters, vol.85, p.5234-7, 2000) that is more successful at matching the power law exponent and the clustering behavior of the Internet. Last, we comment on the small world behavior of the Internet topology.

In this paper we consider the problem of inferring link-level loss rates from end-to-end multicast measurements taken from a collection of trees. We give conditions under which loss rates are identifiable on a specified set of links. Two algorithms are presented to perform the link-level inferences for those links on which losses can be identified. One, the minimum variance weighted average (MVWA) algorithm treats the trees separately and then averages the results. The second, based on expectation-maximization (EM) merges all of the measurements into one computation. Simulations show that EM is slightly more accurate than MVWA, most likely due to its more efficient use of the measurements. We also describe extensions to the inference of link-level delay, inference from end-to-end unicast measurements, and inference when some measurements are missing.

We explore the use of end-to-end multicast traffic as measurement probes to infer network internal characteristics. We have developed in an earlier paper a maximum likelihood estimator for packet loss rates on individual links based on losses observed by multicast receivers. This technique exploits the inherent correlation between such observations to infer the performance of paths between branch points in the multicast tree spanning the probe source and its receivers. We evaluate through analysis and simulation the accuracy of our estimator under a variety of network conditions. In particular, we report on the error between inferred loss rates and actual loss rates as we vary the network topology, propagation delay, packet drop policy, background traffic mix, and probe traffic type. In all but one case, estimated losses and probe losses agree to within 2 percent on average. We feel this accuracy is enough to reliably identify congested links in a wide-area internetwork.