Fang
Yu, Randy H. Katz
{fyu,randy}@eecs.berkeley.edu
T.
V. Lakshman
lakshman@research.bell-labs.com
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
Ling
Huang
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.
Karthik Lakshminarayanan
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.
Ayumu
Kubota
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.
Mukund Seshadri
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.
Sharad
Agarwal
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.
Sridhar
Machiraju
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.
Mel
Tsai
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.
George
Porter
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.
Yin
Li
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.