Fang Yu, Randy H. Katz
T. V. Lakshman
Network Intrusion Detection Systems (NIDS) are recently developed to increase network security. The key component of such systems is searching for thousands of patterns from both packet header and payload. Pure software implementation using known pattern matching algorithms cannot support it at gigabit rate. In this poster, we present a multiple pattern-matching algorithm using Ternary Content Addressable Memory (TCAM). The proposed algorithm has following features. It supports tens of thousands of patterns. It easily handles patterns longer than TCAM width. It also finds correlated patterns and patterns with negation. The proposed scheme can operate at gigabit rate and it can be extended to support multi-gigabit rate.
Yasuhiko Matsunaga - y-matsunaga AT bl.jp.nec.com
Ana Sanz Merino - asanz AT eecs.berkeley.edu
Manish Shah - manish AT eecs.berkeley.edu
Takashi Suzuki - suzuki AT spg.yrp.nttdocomo.co.jp
Randy Katz - randy AT cs.berkeley.edu
A serious challenge for seamless roaming between independent wireless LANs (WLANs) is how best to confederate the various WLAN service providers, each having different trust relationships with individuals and each supporting their own authentication schemes,which may vary from one provider to the next. We have designed and implemented a comprehensive single sign-on (SSO) authentication architecture that confederates WLAN service providers through trusted identity providers. Users select the appropriate SSO authentication scheme from the authentication capabilities announced by the WLAN service provider. For this, we have developed the Authentication Negotiation Protocol. Our system also allows users to block the exposure of their privacy information while roaming. In addition, we have developed a compound Layer 2 and Web authentication scheme that ensures cryptographically protected access while preserving pre-existing public WLAN payment models. Our experimental results, obtained from our prototype system, show that the total authentication delay is about 2 seconds in the worst case. This time is dominated primarily by our use of industry-standard XML-based protocols, yet is still small enough for practical use.
Wei Dong Cui
Today’s Internet is fragile due to network faults and malicious attacks. To achieve better resilience, we need rapid detection of network anomaly. Network anomaly has two folds: performance degradation and abnormal user behavior. In this project, we propose a new collaborative online passive monitoring infrastructure for rapid anomaly detection. In the monitoring infrastructure, each edge network has a monitoring box at its gateway. The monitoring box passively monitors all traffic into and from the edge network and online computes traffic statistics. To detect performance degradation, the monitoring box calculates aggregated performance measures from the edge network to other edge networks and uses Change-Point detection algorithms. To detect abnormal user behavior, the monitoring box updates user profiles for end hosts inside the edge network. Each user profile has a set of histograms that can be used to calculate the distribution of user behavior. Each monitoring box can exchange information of traffic statistics securely. This project is on progress. On-going work includes implementation and evaluation of the design
Probabilistic Data Aggregation
This poster presents our first step toward to a scalable and robust solution for accurate data aggregation in large groups communicating over unreliable networks. Calculating global aggregate functions is an important function in many network infrastructure and applications, including sensor networks, P2P networks, and network monitoring and intrusion detection systems.
In networks with high link loss and node failures, date aggregation becomes a difficult task and exact results are not achievable. Sensors have low computational power, communicate on low bandwidth, high loss links, and often fail without warning. On the other hand, while it may seem that P2P networks have relatively high bandwidth and computation power, much of those resources are consumed by applications and control traffic, leaving low resources for aggregation tasks. P2P membership is also highly dynamic, making stable aggregation results difficult to achieve. Finally, network monitoring and intrusion detection systems provide the highest value under conditions of network stress, such as attacks or high congestion. Performing aggregation under these low resource conditions is crucial to their value. In each of these cases, providing a low overhead, highly accurate data aggregation scheme is highly desirable.
In this work, we define the approximate version of the data aggregation problem. We aim to introduce statistical learning algorithms to design scalable and robust protocol which achieves good approximation. We try to evaluate the effectiveness of different algorithms and explore the trade off between the accuracy and the number of participants in the aggregate calculation. When loss and failures happen, partial of all members of the group can participate in the aggregation. We want to achieve accurate result even when only small portion of members participate in the calculation and communication by employing statistical sampling and prediction algorithms.
To evaluate the approach, we aim to develop a data aggregation framework based on statistical learning algorithm. In this framework, loss (on the link) and faults (data corruption on the node) are introduced into the aggregation process; protocols and algorithms are designed to handle failures as part of normal operations. The main building blocks in the framework include Aggregation tree constructor, statistical sampler, distribution estimator and data predictor.
Emerging applications in the Internet demand a varied set of route selection mechanisms that are different from what the underlying routing provides. However, the tight integration of routing in the Internet infrastructure coupled with the difficulty in modifying the infrastructure has led applications to build their own routing at a layer above the IP (termed as the overlay layer). Routing at the overlay layer, on the one hand is much less efficient than network layer routing, and on the other is indispensable if the network infrastructure cannot be changed. To resolve this tussle, we propose a way of designing networks where control over routing is pushed out of the basic network infrastructure. The infrastructure provides a basic forwarding functionality which is used to construct routes along the infrastructure by entities that are outside this underlying infrastructure. By this, we decouple the control and data plane of the network by providing clean abstractions. We demonstrate the technical feasibility of such an approach by providing simple mechanisms that address the issues of security, trust, scalability and stability of the network. We believe that this design would lead to evolvable networks where application needs drive the routing mechanisms of the network.
Internet Indirection Infrastructure (i3) is a flexible network infrastructure that provides support for basic communication primitives such as multicast, anycast, mobility, and service composition. To enable legacy applications to take advantage of i3's flexibility we have designed and implemented several proxy solutions that tunnel legacy IP traffic over i3. By doing this, we are able to provide users enhanced security, mobility support, transparent access to machines behind NATs and Firewalls, and support for interposing new functionalities in the data path. During the poster session we will explain the implementation of the proxy, which currently runs on both Windows and Linux, and demonstrate how legacy application can benefit from using it.
Infrastructured-based Resilient Routing
Ben Y. Zhao
With the continued growth of the Internet, developers are deploying new and larger scale network applications, such as file sharing, instant messaging, streaming multimedia and voice-over-IP (VoIP). These applications are placing increasingly heavy demands on the Internet infrastructure, requiring highly reliable delivery and quick adaptation in the face of failure.
Unfortunately, it is becoming increasingly difficult to meet these criteria. The growing size and complexity of the network lead to frequent periods of wide-area disconnection or high packet loss. A variety of factors contribute to this, including router reboots, maintenance schedules, BGP misconfigurations, cut fibers and other hardware faults. The resulting loss and jitter on application traffic creates significant roadblocks to the widespread deployment of ``realtime'' applications such as VoIP.
The magnitude of this loss and jitter is a function of the routing protocol's response time to faults, including time to detect a fault, construct a new path, and reroute traffic. Recent work has analyzed the fault-recovery time of intra-AS protocols such as IS-IS for large IP backbone networks, and found that overall recovery is on the order of five or six seconds. Wide-area route convergence on BGP is significantly slower. Recent work has identified interactions between protocol timers as the fundamental cause of delayed convergence. Because BGP disseminates reachability updates hop by hop between neighbors, full propagation across a network can take 30n seconds, where n is the longest alternative path between a source and any destination AS, and 30 is the length of a typical BGP rate limiting timer. Unfortunately, studies have shown a significant growth in BGP routing tables fueled by stub ASes, meaning the delayed convergence problem will only grow in severity with time.
In this work, we propose the use of structured peer-to-peer (P2P) overlay networks as the basis for a resilient overlay routing infrastructure. The key insight is to leverage the limited connectivity of each node in two ways. First, the small number of next hop neighbors allows each node to proactively probe outgoing routes for link quality at a relatively high rate while consuming relatively low bandwidth. The result is a minimal time to detect IP level routing failures. Second, the low connectivity and flexible routing scheme means that each node can actively maintain backup routes for each outgoing route. We decouple discovery of backup paths from adaptation to failure. Instead of computing a backup path when a failure is detected, nodes immediately redirect traffic to a backup route. The end result is that nodes respond very quickly to failures, reducing disruption to application traffic. Finally, unlike unstructured overlay approaches, the logarithmic state kept per node of structured P2P overlays allows the infrastructure to scale without putting undue stress on the underlying network.
We demonstrate the benefits of overlay routing through structured P2P overlays using a combination of analysis, simulation, and experimental measurements. We deployed a prototype of the Tapestry system, a fault-resilient overlay that implements these adaptive mechanisms. We show that Tapestry can recover from network failures in under 700 milliseconds while using less than 7 Kilobytes/second of per-node beaconing traffic---agile enough to support most streaming multimedia applications. Our design should be scalable and easy for Internet Service Providers (ISPs) to deploy, providing fault-resilient routing services to legacy applications.
Overlay networks allow routing to be controlled at the application layer. Consider several independent overlay network flows, each with a set of available overlay routes to send their data on. If they each select the best route (i.e., they are ``greedy''), a significant degree of instability could result, leading to degraded performance. We investigate this possibility, and a wide variety of factors that affect routing performance, by simulations. We find that some measure of ``restraint'' is crucial for obtaining acceptable performance of route selection in such scenarios. Specifically, we investigate three forms of restraint - randomization of route selection, utilizing an appropriate hysteresis threshold when switching routes, and increasing the time intervals between route-change considerations.
Our results indicate that randomization can significantly reduce loss-rates (typically by half) - more importantly, it is sufficient to utilize load information from a small subset of overlay paths to obtain such results. This approach would significantly reduce the measurement overhead imposed by applications. Secondly, we find that appropriate values of the hysteresis threshold (H) can be heavily dependent on the parameters of the topology; therefore we propose that flows discover H dynamically, and evaluate a candidate algorithm to do the same. Finally, we investigate the scenario when a subset of unrestrained overlay flows (the ``cheaters'') select the best of all available routes, while the remainder use the randomized protocols or dynamic discovery of H.
Matt Caesar, L. Subramanian, Randy H. Katz
The lack of a good understanding of the dynamics of interdomain routing has made efforts to address BGP's shortcomings a black art. To gain more insight into these dynamics, we need to answer two questions: What is the cause of a routing change? Where does a routing change originate? We are working towards development of a BGP health inferencing system that answers these questions by observing routing updates from multiple vantage points and inferring the type and location of an event that triggers a routing change. To build such a system, we solve two basic problems: (a) classify route updates into groups of correlated routing changes where all route updates in a group are triggered by the same event, (b) given the set of routing changes for an event, determine the location and the cause of the event.
By analyzing route updates from Routeviews and RIPE for over 18 months, we found that our approach can pinpoint the location where an update is triggered to a single inter-AS link in over 70% of observed updates. We found that the majority of updates are caused by a relatively small number of unstable links. In addition, 25% of prefixes are persistently unstable, causing 20% of all updates observed. Routes through the Internet core usually reconverge quickly after events, while an event taking place at the network edge is 9 times more likely to cause a long-term route change. We validated our approach by showing it can detect a variety of well-known events, namely: (a) session resets recorded in the NANOG mailing list; (b) routing problems within ISPs; (c) location of BGP Beacons. In addition, our inference methodology is able to detect several routing problems not publicly known. In summary, we believe that our health inferencing system is a first step towards forming a better understanding of inter-domain routing dynamics.
The Internet is a collection of separately administered networks called Autonomous Systems (ASes). This separation is meant to achieve scalability by isolating inter-domain routing from intra-domain changes. If this isolation is not maintained, complex interactions in different parts of the Internet can destabilize it.
I have collected and analyzed routing and traffic data in the Sprint network. I have found that during typical network conditions, there is tremendous inter-domain routing variability. This can significantly degrade intra-domain network performance. However, my analysis has shown certain properties of routing and traffic that shield the majority of traffic from this harm.
While typical network conditions may be safe from this harmful interaction, periods of network tuning may not be safe. During traffic engineering, significant intra-domain routing changes can be expected. My ongoing research shows that during this time, the egress for a significant portion of traffic can change. As a result, changes inside one network can significantly impact the traffic in many other networks. This is an important finding, because this unexpected interaction can further destabilize Internet routing and traffic.
The desire, of network operators, to keep their network operational conditions, policies, etc. confidential has made managing, optimizing and debugging inter-domain routing extremely challenging. In this presentation, we develop techniques for inter-domain routing that provide new insights into how ASes can reconcile the need for cooperation with their confidentiality requirements. Our techniques leverage the field of secure multiparty computations. Specifically, we demonstrate how ASes can cooperate without revealing their confidential information to:
(1) Perform intra-domain traffic engineering that causes acceptable changes in traffic to neighboring domains.
(2) Allow customer-defined policy for better choice of routes at stub ASes.
(3) Perform static analysis of BGP policies to detect and eliminate conflicting policies that could lead to divergent routing.
We are currently investigating the overhead, amount of information leakage in each of our techniques and methods by which misbehavior can be detected. Our future work is also focused on developing more techniques that would enable other traffic engineering objectives such as the selection of optimal exit points and inter-domain QoS.
Tomorrow's programmable hardware will support stateful, wire-speed classification and computation on millions of flows. Even today we are seeing a strong push towards application-level processing being placed in the network, e.g. load balancers, intrusion detection, intelligent storage, link compression devices, and others. Inevitably, as the hardware improves and reduced TCO become the primary goal, these and other such devices will converge into an inexpensive, easy-to-manage programmable device.
RouterVM is a flexible, architecture-independent, and high-level environment for writing multiple, coexisting network applications for deployment on a single programmable router. RouterVM is a virtual machine runtime that sits on top of any programmable hardware. It allows powerful new applications to be written by network administrators and engineers alike, and in most cases without writing new code. Applications and standard routing functions are managed through an intuitive and flexible CLI. The environment can be extended to support new functionality through the addition of new Generalized Packet Filters (GPFs), a concept that is the key innovation of RouterVM. Although RouterVM can target any hardware, a proof-of-concept implementation has been written for PC hardware running Linux.
Programmable Network Elements (PNEs) are a general platform for doing packet processing in the edges of the network. To serve as a measurement, monitoring, and modification point for arbitrary application-layer protocols, we must extend the PNE’s design to include stream processing. While packet processing deals with each packet individually, stream processing acts on application-layer data units that might span multiple underlying IP packets. This means that the in-network PNE must be able to track the boundaries of these data units despite loss, reorder, and delay in a way that generalizes to a variety of application-layer protocols and fits within the design of the PNE and its specification environment.
I propose an extension to the PNE specification language and a new mechanism that enable stream processing in an efficient and general manner within the PNE. This mechanism provides a clear separation between the transport of packets and the structure of the application-layer protocol. The proposed mechanism is efficient because it only looks in depth at a small subset of the packets that comprise the stream. In a collection of sample workloads, about 1-5% of the packets were examined. In terms of in-router delay, unexamined packets undergo a very small additional delay, while examined packets undergo 30-50% additional processing time.
This extension to the PNE design will allow users to specify networked storage flows, HTTP flows, P2P and Kazaa flows, and many other data streams that reside above TCP. Furthermore, new protocols can be added to a PNE at the command-line without modifying the underlying PNE.
Yin Li, George Porter, Mel Tsai
The OASIS project is focused on building network services from the network layer up. Informed by the introduction of a vast array of special-purpose processing points within the network (such as SAN storage directors, HTTP load balancers, firewalls, traffic shapers, etc), we are designing Programmable Network Elements based on a Classify, Infer, and Act architecture. These elements rely on a router mechanism we are designing called a "generalized packet filter". These filters are simple, composable, and customizable, allowing for arbitrary combinations of high speed packet processing paths in the router, which we will be able to use to invoke per-stream and per-packet processing at various points in the network.
To develop, test, and measure our software artifact, RouterVM, we are deploying it as part of a multimedia delivery service called VideoCollective. This service will reside in our experimental testbed consisting of a cluster of single-board Linux servers and routers. Users will access playlists and request specific programs through a web interface. Our PNEs will load-balance requests and streams among the video servers. Those video servers will draw their content from a storage area network (SAN) using our PNEs as the interconnect fabric. This will allow us to experiment with in-network storage (iSCSI) enhancements, including load-balancing, caching, virtualization, and recovery mechanisms using real workloads. Later stages of the deployment will include creating “shared playlists” using virtual SAN (vSAN) enhancements to the PNE design. This platform will provide a versatile real-world environment to test our design and measure its performance.
The integration of Local Area Network (LAN) and Storage Area Network (SAN) is an emerging direction of SAN deployment due to its cost-effectiveness and easy of management. iSCSI is the most commonly deployed protocol in this environment. However, it has been observed that iSCSI's performance will drop dramatically in the presence of cross traffic. The goal of this project is to propose solutions to achieve sustained high performance on the merged infrastructure. We present our research plan in the poster. We discuss how to build a testbed to emulate performance degradation caused by cross traffic. Our targeted environment includes scientific computing and multi-tiered transaction data center. We present our hypotheses on reasons that cause performance drop and discuss possible directions of solutions.