George Varghese - US grants

94054444 Varghesee As networks become part of the nation's infrastructure, it is important that they become as reliable as other utilities such as the telephone and power services. This project is concerned with the design, evaluation, and implementation of reliable network protocols through the use of self-stabilization. A protocol is self-stabilizing if it begins to behave correctly no matter what state it starts in. The principal investigator believes that self-stabilizing network protocols are simpler (i.e., a small number of uniform mechanisms instead of multiple mechanisms to deal with a catalog of anticipated faults) and more robust (e.g., can recover from transient faults such as memory corruption as well as common faults such as link and node crashes). While there are self-stabilizing protocols in existing networks, such protocols typically rely on timers that are proportional to worst-case network delays and result in slow recovery times. Further, there are only a handful of such protocols. This project will investigate stabilizing protocols that have much faster recovery times and for a larger class of problems. This project will apply techniques from the theory of distributed algorithms (that the principal investigator and others have developed) to the systematic design of self-stabilizing protocols. The work in the distributed algorithm literature has introduced some useful paradigms and techniques but has not fully applied these ideas to real networks. It is this gap that this project will address. ***

Washington University at St. Louis George Varghese RIA: Trading Packets Headers for Packet Processing In high speed networks, packet processing is relatively expensive while bandwidth is cheap. The central thesis here is that if suitable header fields can be added to packets, then mechanisms to speed up packet processing can be devised. Several ideas are advanced to support the above thesis. First, data manipulation (e.g. data copying, checksumming) is a major bottleneck of end system packet processing. The approach taken here suggests adding a data manipulation header to an easily accessible portion of each packet. This header contains pointers to fields (in various layers) required for data manipulation. This information (e.g. a pointer to data to be encrypted) allows implementations to efficiently combine data manipulation steps (e.g. encryption and copying). Prior work has shown that combining data manipulation steps can yield order-of-magnitude performance improvement. The present approach can yield similar improvements in a more uniform and structured fashion. Second the work studys adding index fields to protocol identifiers at all layers (e.g. connection identifiers, network addresses) to reduce lookup costs and generic protocol processing. Several new ides to utilize these index fields (threaded indexing, index passing, and source hashing) are studied. It is known that the use of Virtual Circuit Identifiers (VCIs) on virtual circuit packets simplifies lookup and packet processing. In source hashing and threaded indexing, the added indices essentially serve as VCIs, but for flows in a datagram network. In source hashing, for example, the "VCI" is a consistent random label chosen by the source. OUr new methods provide the benefits of normal VCis without requiring a round trip delay for set up. The methods can lower uorst case datagram lookup times form O(log(n) to O(1), which may be important for gigabit routers. IN this project we design, analyze, and implement these new ideas and search for other techniques that arise from the basis thesis. The current climate of transition (in which transport, routing, and data link protocols are changing) provides an opportunity to apply these techniques to influence real protocols.

In the Internet today, packet losses are typically recovered using retransmission, as for example in TCP. The mechanism employed in TCP works well in the unicast environment. In multicast environment, however, such as the MBone, the TCP approach does not work well, especially when the multicast groups are very large. Difficulties arise because of two main problems: implosion and exposure. Implosion occurs when following a packet loss, many receivers multicast the same request; implosion also occurs when in response to a request, many receivers multicast the lost packet. Exposure occurs when requests and retransmissions reach members that have not experienced loss. Both implosion and exposure cause unecessary overhead. Existing solutions are not general because of the trade-offs they offer for reducing implosion and exposure. SRM for example, trades latency for reducing implosion, and uses a crude method for reducing exposure. RMTP, TMTP and LBRRM reduce both implosion and exposure by arranging members in a tree. The tree, however, is hard to construct and maintain in the face of dynamically changing groups without any access to topology information. We propose a new scheme to perform reliable multicast which overcomes the limitations of existing solutions. Our scheme is based on a dynamic tree hierarchy, but pushes the task of costructing and maintaining the tree to the network, where it can be done very efficiently. To achieve this, we enhance the IP Multicast service model by adding new forwarding services to the routers. The scheme combines three ideas to achieve near optimal performance: (a) electing a replier link at each router to eliminate implosion, (b) defining the concept of a "turning point" to discover the subtree where loss occurred, and (c) using "directed multicast" to limit replies to the loss subtree. These ideas minimize recovery latency and allow group members to be completely isolated from the details of group topology, thus allowing fast adaptation to dynamic membership changes.

Looking up the route to send a message is a major bottleneck in traditional
Internet Routers. Traditional routers only use the destination address in
a message to determine how to forward the message. However, in the last
few years, there have been proposals for more sophisticated routers that
are capable of what is called Layer 4 Switching. We believe that the
capabilities provided by Layer 4 Switching in terms of security, quality of
service, and guaranteed service will make Layer 4 Switching an integral
part of the Next Generation Internet.

In Layer Four switching, the route and resources allocated to a packet are
determined by the destination address as well as other header fields of the
packet (such as source address, TCP port numbers etc.). Layer Four
Switching unifies a number of recent trends (such as firewall processing,
resource reservation, providing virtual private networks) into a single
framework. The forwarding database of this new kind of router consists of
a potentially large number of filters on key header fields. A given packet
header can match multiple filters; thus each filter is given a cost, and
the packet is forwarded using the least cost filter that matches the packet
headers.

The flexibility and service differentiation provided by Layer 4 Switching
comes at a cost. Given that traditional Internet forwarding based only on
destination addresses is itself a challenge to implement at Gigabit speeds,
Layer 4 Switching at Gigabit speeds is a difficult problem for next
generation routers. In this proposal, we address the question of designing
and implementing fast algorithms for Layer 4 Switching that can be
implemented at Gigabit speeds even with hundreds of thousands of filters.
We introduce three promising candidate algorithms (cross-producting, Grid
of Tries, and Tuple Search). We propose to implement, evaluate, and
fine-tune these new ideas, consider combination schemes, and to search for
other fast algorithms for fast filter matching. As part of our proposal we
plan to design a chip capable of doing Layer 4 Switching at Gigabit speeds.

Network protocols lookup state using a number of data structures for functions such as IP lookups (e.g., tries), bridge lookups (e.g., hash tables), and packet filtering (e.g., Pathfinder). Network lookups are a key bottleneck for Internet routers today. As Internet link speeds move to 10 Gbps (OC-192) and 40 Gbps (OC-768), state lookups must complete in tens of nanoseconds. The researcher argues in this proposal that solutions to such next generation lookup problems must span a number of areas from algorithms to computer architecture. The proposal is devoted to investigating such crosscutting issues that arise in the context of next generation network lookups.
Current lookup technology that uses external DRAM (Dynamic RAM) cannot scale to this speeds; thus
Terabit lookups will require the use of on-chip or off-chip SRAM (Static RAM). Such memory is limited by either expense or manufacturing process | e.g., on-chip SRAM of 16 Mbits is considered optimistic. In this proposal, the researcher considers the issues involved in dealing with such state lookups at Terabit speeds using limited fast memory while providing provable guarantees.
An important issue considered in this proposal is SRAM memory utilization: if the lookup chip is to provide guarantees about the amount of state (e.g., number of IP prefixes) it can handle, the resarcher shows that the lookup chip must use a memory allocator which can guarantee a provable memory utilization ratio. However, all conventional memory allocation algorithms (e.g., First Fit, Best Fit, Buddy System) only guarantee poor worst case utilizations: for example, for requests of size 32 standard allocators can only guarantee a utilization ratio of 1/log2 32 = 20% because of possible fragmention. The proposal introduces new problem-specific memory allocation schemes that can be tuned to provide worst-case memory utilization ratios close to 100%. For example, a chip that does IP lookups using the researcher's new allocation schemes can guarantee to handle almost 5 times the number of prefixes that can be handled by a conventional allocator, and yet can allow insert/delete times of around 100 microseconds. The researcher's
schemes use new algorithms; optimal versions of the researcher's schemes also require new SRAM memory designs that allow shifted access in addition to normal word access.
The research also proposes to investigate other issues including the interaction of memory allocation with pipelining (i.e., dynamically allocating memory to stages), and the introduction of new lookup primitives that can support accounting and Quality of Service. For example, the researcher wishes to investigate a novel paradigm for pipelining a trie based on depth rather than height which appears to have a more bounded use of memory. As a second example,the researcher wishes to investigate the possibility of doing prefix lookups that contain a cost field; such a lookup can be used to update a accumulated cost field per input link. The proposal seeks to investigate these and other issues that arise when designing Terabit lookups, to search for new mechanisms, and implement, evaluate, and fine-tune the researcher's new ideas.

Accurate network traffic measurement is required for accounting, bandwidth provisioning, and detecting DOS attacks. However, keeping a counter to measure the traffic sent by each of a million concurrent flows is too expensive (using SRAM) or slow (using DRAM). The current state-of-the-art (e.g., Cisco NetFlow) methods which log periodically sampled packets are slow, inaccurate, and memory-intensive. This proposal introduces a paradigm shift by concentrating on the problem of measuring only "heavy" flows | i.e., flows whose traffic is above some threshold such as 1% of the link. After showing that a number of simple solutions based on cached
counters and classical sampling do not work, the resarchers describe two novel and scalable schemes for this purpose which take a constant number of memory references per packet and use a small amount of memory. Further, unlike NetFlow estimates, we have provable bounds on the accuracy of measured rates and the probability of false negatives. The researchers propose to implement, evaluate, and fine-tune these new ideas. Using these ideas as a basis, the researchers also propose to investigate the following questions. First, they will investigate a new form of accounting called threshold accounting in which only flows above threshold are charged by usage while the rest are charged a fixed fee. Threshold accounting generalizes the familiar notions of usage-based and duration based pricing. Second, they propose to investigate a more general question: the computation of flow statistics at very high speeds using very small amounts of high speed memory. Examples of other potentially useful flow statistics include the number of flows, the standard deviation of flow sizes, the average duration of a flow etc. Naive algorithms to measure such quantities all scale linearly with the number of flows. Finally, with colleagues at CAIDA, the researchers plan to deploy our algorithms in real-time on 5 traffic monitors placed at strategic Internet sites (AIX, the UCSD backbone, and possibly on Abilene). The potential impact of this proposal is the development of novel and practical tools for accounting, measurement, and security. These are three central problems as the Internet transitions from a research network to a commercial enterprise.

Collaborative Research: Cybertrust Center for Internet Epidemiology and Defenses

Stefan Savage, University of California - San Diego
Vern Paxson, International Computer Science Institute

Award 0433668

Abstract

The combination of widespread software homogeneity and the Internet's unrestricted communication model creates an ideal climate for infectious, self-propagating pathogens - "worms" and "viruses" - with each new generation of outbreaks demonstrating increasing speed, virulence, and sophistication. The Center for Internet Epidemiology and Defenses aims to address twin fundamental needs: to better understand the behavior and limitations of Internet epidemics, and to develop systems that can automatically defend against new outbreaks in real-time.

Understanding the scope and emergent behavior of Internet-scale worms seen in the wild constitutes a new science termed "Internet epidemiology". To gain visibility into pathogens propagating across the global Internet, the Center is pursuing the construction and operation of a distributed "network telescope" of unprecedented scale. The telescope in turn feeds a "honeyfarm" collection of vulnerable "honeypot" servers whose infection serves to indicate the presence of an Internet-scale worm.

To then fight worms once detected, the Center works on developing mechanisms for deriving "signatures" of a worm's activity and disseminating these to worm suppression devices deployed throughout the global network.

Finally, the Center strives to ground its research in the potentially thorny, but highly relevant, "real-world" issues of informing the development of legal frameworks in terms of the appropriate use of anti-worm technologies and their applications for providing forensic evidence; and enabling the development of actuarial models for quantifying exposure to aggregate risk and liability from Internet epidemics, critical for supporting the emerging cyber-insurance industry.

This project focuses on creating a programmable router processor designed to efficiently execute a variety of network algorithms with the goal to make it a feasible alternative to custom ASICs. To achieve the high throughput required by core routers, the research will focus on (1) fast data plane algorithms, (2) support for co-exploration of algorithms and architecture design, and (3) creating low power routers that do not sacrifice worst case throughput.

The project will spur the development of more revolutionary approaches to high speed network processors, allowing programmable processors to penetrate the core router market. This in turn can help reduce the cost of building and maintaining routers. The results will also help reduce the power costs to run these high speed network routers. In terms of academic impact, this research will bring collaboration between two hitherto separate academic communities (computer architecture and networking) to spark new ideas from this
interdisciplinary interaction.

Modern data centers host operations as varied as flight planning, drug discovery, and Internet search running on thousands of machines. These services are often limited by the speed of the underlying network to coordinate parallel data access. In current data centers, network I/O remains a primary bottleneck and a significant fraction of capital expenditure ($10B/year). Compounding the problem are operational issues caused by interference between services, down times due to failures, and violations of performance requirements.
This project will develop a hardware/software architecture with the following capabilities: i) non-blocking bandwidth to hundreds of thousands of hosts; ii) ``slicing'' across services with minimum bandwidth guarantees; iii) detecting fine-grained performance violations; iv) tolerating a range of failure scenarios; v) supporting end host virtualization and migration. Our goal is to enable modular deployment and management of networking infrastructure to keep pace with the burgeoning computation and storage explosion in data centers. This work will result in a prototype fully functional virtualizable data center network fabric to support higher-level services.
Broader impacts include: i) outreach to under-represented minorities through the UCSD COSMOS program; ii) a public release of the data center communication workloads, protocols, and algorithms we develop; iii) working with our industrial partners and advisory board to address key performance and reliability issues in a critical portion of the national computation infrastructure. A significant outcome will be students trained in data center networking and cloud computing.

All sectors of society depend on properly functioning computer networks. For example, every day, millions of citizens order prescription drug refills, pay their electricity bills, book hotels, shop for groceries, and participate in thousands more activities online, through the cloud. But none of these services will work if the networks that deliver information are down. Moreover, modern business, healthcare, the military and the government are just as dependent on reliable networks as everyday citizens. Many network outages are caused by operators manually (and incorrectly) programming the 'configuration files' that manage the ways that network devices forward information. While the flexibility allowed by configuration files is essential, network outages are often caused by operators using hundreds of low-level directives at each network device to create network-wide policy. Because the global consequences of making even small configuration changes is so drastic, many organizations take several weeks to audit even small changes, limiting their ability to respond effectively to traffic fluctuations, business opportunities, security threats and hardware failures.

A natural solution to these problems -- analogous to the trend in programming languages for software development over the last several decades as programmers have moved from machine code to Java -- is to define more robust, higher-level programming languages for implementing network policies. However, there are technical and pragmatic hurdles to surmount before it will be possible to deploy new languages in industrial settings on a large scale. In particular, existing network-wide policy languages are not expressive enough for many desired network policies and often require wholesale migration to new networking platforms. Hence, the overarching goal of this project is to surmount the technical challenges that impede practical deployment of high-level network programming languages. The project is developing the core technology necessary to efficiently support and incrementally deploy high-level network policies. The project leverages connections to two major cloud providers as a means to test the resulting languages and systems on real industrial networks, identify pragmatic barriers to adoption, and ultimately deploy the technology where possible.

The project builds on the PIs' recent work on Propane, a new network programming language that allows users to describe end-to-end paths for intra- and inter-domain routing, along with a compiler that produces configurations for the industry-standard BGP protocol. The results of this project will extend Propane in several ways to support practical deployment: First, users will be able to declare device roles (e.g., top-of-rack switch) and the connectivity invariants related to them to enable concise specifications. A new compiler will verify safety properties of policies in the presence of such declarations and generate parameterized templates that make compiler outputs more intelligible for operators. Second, users will specify financial contracts that govern transit costs using a new declarative language and the compiler will optimize routes automatically by generating refined policies that meet objectives. Third, the Butane compiler will target and exploit the benefits of heterogeneous back-end protocols and platforms. Fourth, tools will help network operators infer new high-level configurations from existing low-level configurations and to verify that new configurations are equivalent to old ones. Finally, Butane will support mixed mode (legacy- and high-level network operations) so engineers can migrate their networks slowly over time and test partial deployment on small fractions of their live traffic.