Cisco engineers collaborate with academic researchers and educators on a wide variety of projects. See examples of recent awards and opportunities.
Alex C. Snoeren Department of Computer Science and Engineering, University of California, San Diego Designing Router Primitives to Monitor Network Health Sponsor: Doug Comer
We propose designing new router primitives that can accurately and efficiently monitor the health of a network in a scalable fashion. If a problem is detected (whether a connectivity problem or a performance problem such as high rates of loss or jitter), the primitives can help localize the problem to facilitate rapid repair. Current ad hoc monitoring techniques such as end-to-end network probes do not scale to timely full, all-pairs coverage, and leveraging them for localization requires indirect inference using heuristics or effort by expert human operators. In contrast, our router-based primitives lend themselves to automated diagnosis and localization of enterprise networks and ISPs, which can considerably reduce operational expenditures and improve customer satisfaction.
Amin Vahdat Department of Computer Science and Engineering, University of California, San Diego Algorithms and Infrastructure for Shared Mesh-based Video Distribution Sponsor: Doug Comer
The goal of this proposal is to investigate algorithms and architectures to enable scalable, high-performance video distribution to large numbers of nodes distributed across the Internet.
The idea is to develop a set of technologies that can be combined to create federated video distribution utilities that support the simultaneous delivery of a wide variety of content to overlapping sets of clients with statistical quality of service assurances.
By enabling a single service to dynamically reconfigure itself based upon the content it is serving at any particular moment, this work will allow autonomous service providers to pool their resources to construct distribution networks of scales never before thought possible.
Alan E. Willner Communication Science Institute, Department of Electrical Engineering, University of Southern California Flexible High-Speed Parsing for Network Devices Architecture Sponsor: Loukas Paraschis
An explosion of excitement has erupted in the optical communications community at the prospect of using data modulation formats that are more advanced than simple ON/OFF keying. Specifically, the simple and higher-order formats related to differential-phase-shift-keying (DPSK) hold the promise of increased tolerance to chromatic dispersion and nonlinearity, higher receiver sensitivity and spectral efficiency, and reduced electronic speed requirements for the same data rate. Unfortunately, advanced modulation formats tend to require more complex receivers, such that DPSK demodulation typically requires phase-sensitive delay-line interferometers. Moreover, future networks might wish receivers to recover different bit rates and modulation formats in order to accommodate heterogeneous traffic, and yet advanced receivers tend to be fixed in bit rate and format.
At data rates ranging from SONET-relevant 40 Gb/s to Ethernet-relevant 100 Gb/s, we will pursue novel DQPSK receiver designs that enable more stable, reconfigurable, and cost-effective operation for future high-performance optical networks. We will build on past successful collaborations with Dr. Loukas Paraschis, our Cisco Champion, to explore systems limitations and potential applications of our stable and reconfigurable receiver techniques. Specific projects will include: (a) demonstrating a reconfigurable receiver that can be readily tuned to recover different bit rates and modulation formats, (b) demonstrating a non-coherent receiver that reduces by half the number of required interferometers, (c) demonstrating a stable and low-cost fiber-Bragg-grating (FBG) that replaces the interferometer, and (d) determining the network limitations placed on polarization-multiplexed DQPSK 100 Gb/s systems by fiber-based chromatic, polarization, and nonlinear effects. If successful, our research will enable increased flexibility and simplicity in next-generation high-performance optical systems, and at lower cost.
George Varghese Department of Computer Science, University of California, San Diego Flexible High-Speed Parsing for Network Devices Architecture Sponsor: Flavio Bonomi
As speeds increase, the complexity of parsing for protocols can become a bottleneck. At the same time, as routers integrate more services, it becomes important (at least in the enterprise space) for routers to parse complex new applications protocols, some of which hide behind standard TCP ports. Besides speed, flexibility is also an important goal: it is important to design a flexible parsing block to which the specifications of a new (say P2P) protocol can be added after the device is operational.
Standard techniques for flexible parsing (e.g., Pathfinder in software, Cisco FlexParser in hardware) represent the parsing process as a tree-shaped state machine where parsing a field corresponds to a node in the tree, which can then lead to a number of child nodes where further fields are examined. Unfortunately, each level in the tree adds an interpretation cost and so the cost of flexible parsing in this way is high. On the other hand, in some situations it is possible to extract all the relevant fields and directly jump to the leaves of the parse tree using a large CAM, which is expensive in storage. We propose research into a new style of parsing that tries to use an intermediate stance where a limited amount of parallelism at each tree node can be used to generate parse trees that are both fast and memory efficient.
Injong Rhee Department of Computer Science, NC State University Stability of Congestion Control: Metrics and Protocols Sponsor: Larry Dunn
Can we design a congestion control protocol that can be stable independent (or less dependent) of packet buffers smaller than the full bandwidth and delay product? This proposed study takes two approaches to answer this question. We first define a set of reviewed metrics for stability and study their implications on the general well-being of the Internet, and then experimentally validate the reviewed metrics and apply the lessons learned to the design and implementation of new congestion control protocols.
Nancy Griffeth Department of Mathematics and Computer Science, Lehman College of the City University of New York Nancy Lynch Electrical Engineering and Computer Science, MIT A New MAC-Layer Paradigm for Mobile Ad-Hoc Networks Sponsor: Ralph Droms
The wireless MAC layer affects higher-layer network protocols in many ways, requiring that the usual Internet strategies for routing, security, and reliable message delivery be rethought. Node mobility requires further rethinking of the higher layers. We propose a lower-layer paradigm for communication and mobility-hiding to solve two difficult problems for Mobile Ad Hoc Networks (MANETs):
1) Successful message delivery in the presence of malicious adversaries.
2) Message routing over large, mobile networks.
The proposed lower-layer communication paradigm uses multiple channels, either frequency-based or time-based, to avoid collisions and to foil adversaries. The proposed mobility-hiding mechanism is virtual nodes. A virtual node is associated with a geographical region and is implemented by physical nodes that are in the region. Virtual nodes are stationary and so support use of traditional wire line protocols. However, a virtual node may be more likely to fail than a normal node, changing the behavior of the traditional protocols.
We will use a combination of simulation and analysis to evaluate the performance of communication and routing algorithms based on this paradigm. We will base these evaluations on abstract complexity measures such as percent of messages delivered, total number of messages sent and received, and latency of message delivery. Because of complex interactions between various design decisions at the MAC and internet layer, we will not attempt detailed performance studies. Instead, we will use the results obtained by simulation to suggest analytical results, subject to proof, to be used as guidelines for network design.
This project is intended to be an exploratory project, to determine the feasibility and value of the new lower-layer communication paradigm. If the results justify further work, we will extend the project using additional funding sources.
Nick McKeown Electrical Engineering and Computer Science, Stanford University Accurate Network Timing and Synchronization Sponsor: Tom Edsall
The IEEE 1588 “Precision Time Protocol” (PTP) provides hardware support to synchronize multiple clocks in a Gigabit Ethernet network to within 50ns or less. We are interested in two questions: (1) What are the theoretical and practical limits to clock synchronization in a network of switches and routers?, and (2) If there is precise network-wide clock synchronization, what are the implications on network protocols and applications? We suspect it will lead to big simplifications in how networks operate, and could simplify important applications where the timing and ordering of events is important.
Sanjay Rao
School of Electrical and Computer Engineering, Purdue University Monitoring Peer-to-Peer Networks for Anomalous Traffic Sponsor: Navindra Yadav
We seek to design algorithms to monitor traffic of peer-to-peer systems, and detect deviant traffic behavior. The motivation is two fold:
(i) Normal behavior in peer-to-peer applications exhibit characteristics similar to an Internet worm due to their many-to-many download profile This is a common cause for false positives; (ii) Software bugs, design limitations, and DDoS reflector attacks exploiting peer-to-peer systems, may lead to undesirable traffic patterns. To address these issues, we will: (i) Characterize traffic of peer-to-peer systems with regard to metrics used in anomaly detection based on data collected from operational peer-to-peer systems, and analyzing system behavior under scale and churn; (ii) Study the implication for traffic characteristics for detection algorithms; and (iii) Study the interplay between system design, and ease of monitoring the system.
Janardhan Iyengar Computer Science Department, Connecticut College Shared Bottleneck Detection and Response Mechanisms For Concurrent Multipath Transfer (CMT) Sponsor: Randall Stewart
Concurrent Multipath Transfer (CMT) extends the Stream Control Transmission Protocol’s (SCTP’s) multihoming capabilities for concurrent transfer of new data between source and destination hosts via two or more end-to-end paths. In prior research, we inquired into design considerations, established feasibility, and investigated performance benefits and tradeoffs of CMT. CMT is now part of the FreeBSD SCTP stack. We now seek to resolve a vital open question, whose answer will mature CMT technology significantly. Our research thus far assumed that paths used in CMT do not share any bottleneck links (i.e., points of congestion). Indeed, this restrictive assumption is the major reason for the IETF’s hesitancy in accepting CMT. We propose to relax our assumption and investigate shared bottleneck detection and response mechanisms for CMT. In particular, we propose to investigate mechanisms for a CMT sender to (i) detect the presence of a shared bottleneck, (ii) share congestion state when a shared bottleneck is detected, and (iii) seamlessly migrate between using shared and separate congestion state during an association, as per need. We will incorporate our results into the FreeBSD implementation of CMT.
Srinivasan Ramasubramanian Department of Electrical and Computer Engineering, University of Arizona Sustainable Multipath Routing in Packet-Switched Networks With Minimum Overhead Sponsor: Russ White
Colored trees is an effective mechanism for achieving disjoint multipath routing with no packet overhead. The colored tree approach constructs two trees, namely red and blue, rooted at given destination such that the path from any node to the destination on the two trees are (node or link) disjoint.
In this research, we propose to study (1) the maintenance of colored trees under node additions and deletions; (2) the alternatives for all-to-all multipath routing for packet-switched networks; (3) the effectiveness of the colored tree construction/maintenance algorithms in guaranteeing performance during reconfiguration; (4) the ability of TCP connections to exploit the increased bandwidth available from multiple paths. We will evaluate the performance both theoretically and simulation experiments.
Jim Martin and James M. Westall School of Computing, Clemson University DOCSIS 3.0 Channel Bonding Scheduling Algorithms and Issues Sponsor: Randall Stewart
We propose a simulation-based study of scheduling algorithms for DOCSIS 3.0 systems. Building off our past work in developing and validating a DOCSIS 1.1 model with the ‘ns-2’ open-source simulation package, we will add channel bonding capabilities to the model. The objectives of the project are to: 1) develop and validate a simulation model of an HFC network that supports upstream and downstream channel bonding; 2) develop and validate a baseline scheduler for both upstream and downstream; 3) develop a more advanced scheduler that incorporates the ideas underlying Cisco’s Low Level Queuing (LLQ) scheduling policy.
Shigang Chen Department of Computer & Information of Science & Engineering, University of Florida Optimizing Access Control Lists Sponsor: Bo Zou
The configuration of a firewall may contain numerous ACLs that are associated with physical network interfaces, logical network interfaces, and tunnels. Optimizing the ACLs has huge impact on the firewall performance; verifying the correctness of the ACLs with respect to the end-to-end policies is also critical. Research has shown that hand-configured firewall configurations are not only inefficient but also error-prone. According to the PI’s experience with CSPM, the security management tools can also produce highly inefficient configurations. This project will provide a comprehensive study on the important subjects of ACL optimization and verification. Efficient algorithms that address these problems will significantly improve the firewall performance, reduce the configuration errors, and, by relieving the administrators from such heavy-duty tasks, cut down the time for constructing the firewall configurations. Finally, the algorithms may directly contribute to the future success of Cisco’s security management software.
Ahmed Kamal Department of Electrical and Computer Engineering, Iowa State University Survivable Network Operation Using Network Coding Sponsor: Iftekhar Hussain
Survivable network operation requires networks to be able to detect failures as soon as they occur, and to then reroute traffic over alternate paths. Two objectives, which are usually contradictory, are the requirements to recover from failures expeditiously, and to minimize the resources reserved by the network to recover from those failures. In this project we propose to use network coding to achieve both objectives. With the use of network coding, different sessions combine their signals on shared protection circuits, hence reducing the amount of required resources, while always providing receivers with backup copies of transmitted signals, therefore allowing instantaneous data recovery. The project will develop network coding-based protection strategies for single link failures, and will then extend the strategies to protect against multiple link failures. Implementation strategies in different protocols, such as IP and MPLS, will also be developed, and additional router and switch functionalities to implement the proposed protection techniques will be introduced. Hybrid strategies, combining different types of protection techniques, including network coding, 1:N and M:N protection, will also be investigated as a means of further reducing the amounts of required resources, while guaranteeing an upper bound on the data recovery time.
Harry G. Perros Department of Computer Science, NC State University Multi-Domain and Single Domain Route Selection under QoS constraints Sponsor: Tsegereda Beyene
We believe that now is an appropriate time to work towards a wider deployment of QoS. Cisco, as one of the stakeholders, has an interest in seeing broader adoption of QoS in multi-provider networks, both public and private. The stakeholders include network service providers, network equipment vendors, large enterprise users of networking services, application designers and other service innovators. We believe that a multi-vendor, multi-provider effort is critical to success, as open standards will ultimately be needed to foster widespread deployment of QoS that reaches beyond the boundaries of a single provider's network.
The proposed research aims at resolving some of the issues associated with the wider deployment of QoS. It was discussed with Ms. Tsegereda Beyenne (tbeyene@cisco.com) and it builds on a proposal by her and co- authors for the optimal route calculation across several domains using the concept of the path computation element (PCE). Ms. Beyenne will advise us during this project.
Thomas LaPorta Computer Science and Engineering, Penn State Security for Internet/IMS Convergence Sponsor: Cetin Seren
The deployment of the IP Multimedia Subsystem (IMS) will mark the beginning of a large-scale convergence of telecommunications networks and the Internet. The unification of these systems through an all-IP core will permit cellular providers to seamlessly support both traditional voice and expanded data services. However, such interconnection will also allow many of the security problems common in the Internet (e.g., Denial of Service, core network element compromise, malware-generated traffic) to directly impact the telecommunications infrastructure. In response, this work proposes to characterize the impact of such attacks and mitigation. This will have a direct impact on Cisco IMS product offerings, such as the family of products that comprise the Cisco Service Exchange Framework Products and Solutions. Specifically, we aim to characterize attacks and determine the feasibility of a class of solutions targeted at preventing overloads in the network.
Jeffrey Andrews Department of Electrical & Computer Engineering, University of Texas at Austin Network Coding’s Impact on Ad Hoc Network Capacity Sponsors: Xuechen Yang, Jan Kruys
The goal of this research is to understand the actual viability and impact of these network coding schemes in a practical network setup. Network coding – in a wireless network – relies on nodes being in certain positions to help with routing. While nearly any set of positions allows for some savings with network coding, some configurations are much better than others. We will use stochastic geometric tools to model typical locations in the network and make predictions on the capacity impact that network coding is likely to have. This research will be challenging because it requires a notion of routing and end-to-end communication to be considered, but these aspects are difficult to incorporate when talking about network capacity. Indeed, even a well-accepted definition of capacity is lacking in such a scenario.
Yanlei Diao Department of Computer Science, University of Massachusetts, Amherst In-Network Complex Event Processing over Distributed Streams Sponsor: Krishna Sankar
In this proposal, we identify core functions of complex event processing (CEP), including filtering, aggregation, correlation, transformation, and predication, and argue for in-network implementation to make computer networks proactive and adaptive. The combination of CEP, a new stream processing paradigm, and its efficient in-network implementation, presents significant challenges that have not been sufficiently addressed before. In this project, we devise novel automata-based mechanisms and appropriate communication protocols for efficient pattern detection across distributed streams. We also propose initial extensions of these mechanisms to address a rich set of issues related to pattern predication, out-of-order and out-of-sync events, and multi-pattern detection. We plan to collect use cases, including trace data and typical patterns, from financial, healthcare, and network monitoring applications to evaluate our proposed algorithms and protocols.
Michael Mitzenmacher School of Engineering and Applied Sciences, Harvard University Hashing and Sampling Algorithms and Data Structures for Network Measurement, Monitoring, and Applications Sponsor: Flavio Bonomi
Hashing-based and sampling-based algorithms and data structures are playing a growing role in networking hardware, enabling richer applications and natural methods for providing approximate measurement and monitoring primitives. In this proposal, we focus on a wide spectrum of questions relating to how to best take advantage of hashing and sampling within the network. At the high level, we consider possible designs for a near-ubiquitous, flexible hashing infrastructure that would allow approximation schemes for a variety of network measurement and monitoring tasks. This focus is motivated by the great value we see from hash-based structures, including their relative simplicity, flexibility, and cost-effectiveness. The goal of a general hashing infrastructure would not only be to handle issues that have already arisen in today's network, but also to provide a general framework for handling additional, currently unknown problems that may arise in the future. In particular, we plan to focus on examining how local hash-based structures can be combined to yield larger-scale synopses of network characteristics and performance. At the low level, we focus on the architectural design of hash-based on sample-based algorithms and data structures. Specifically, we consider how current ideas from theory can be best implemented and utilized in actual network hardware, emphasizing the analysis of actual performance and costs of the variety of alternative approaches.
Bhuvan Urgaonkar Department of Computer Science and Engineering, The Pennsylvania State University Resource Management in Virtualization-Based Consolidated Hosting Platforms Sponsor: Vithal Shirodkar
This project will develop a resource management infrastructure called River for emerging data centers employing server virtualization for consolidating heterogeneous OS/applications. Such consolidation is desirable due to the associated cost reductions. Virtualization introduces several new features - overheads of virtualization, new stability and optimality concerns raised by the fast migration capabilities, new resource usage monitoring and accounting issues, the emergence of a hierarchical scheduling structure - that necessitate a fresh look at resource management. Our solution will span multiple spatial and temporal granularities, from fine time-scale scheduling at the VMM-level to coarser time-scale provisioning at the data center level. An enhanced VMM kernel, called eVMM, will implement a variety of improved resource management algorithms to enable robust performance under high consolidation: (i) an IO aware CPU scheduling algorithm that would help reduce the performance degradation of I/O-intensive applications, (ii) a scheduler-aware memory manager that would assist the CPU scheduler in continuing to provide fair CPU allocations even under high memory pressure, and (iii) mechanisms to allow VMM schedulers to dynamically tune their operation to the overlying operating systems schedulers. Our dynamic resource provisioning mechanisms will be implemented within a system-wide resource manager called the Control Plane. First, we will devise mechanisms to refine the predicted resource needs of applications using simple statistical techniques such as Linear Regression. Second, we will develop a scalable optimization framework in the form of an Allocator to dynamically re-provision resources to hosted applications. Finally, we will employ feedback control-based approaches to: (i) ensure the stability of provisioning decisions and (ii) bound deviations from optimal operating regimes due to modeling/prediction errors and workload fluctuations.
Timothy Griffin Computer Laboratory, University of Cambridge Applied Metarouting Sponsor: David Ward
Network connectivity is implemented using dynamic routing protocols. Today these protocols are few in number and are not well suited for many networks. Existing protocols are pressed into service in highly complex and contorted ways. This leads to high cost of operations, lack of flexibility in the face of new demands, and low levels of network robustness. The Metarouting project proposes a radically new approach to network routing. The basic idea is to implement a metalanguage for defining routing
protocols that could be used by network operators to define new protocols that meet the needs of their networks. The routing metalanguage is based on a firm theoretical framework that allows protocol specifications to be automatically checked for correctness.
Paul Amer Computer and Information Sciences Dept, University of Delaware Improving SCTP with Non-Renegable Selective Acks (NR-SACKs) Sponsor: Randall Stewart
Since cumulative acknowledgments (acks) were defined for TCP in RFC793, two significant mechanisms have extended the concept of data acks in providing end-to-end reliable transport layer data transfer: SACKs and Duplicate-SACKs. We propose to design and investigate a further extension: the Non-Renegable SACK (NR-SACK). NR-SACKs would supplement SACKs by identifying out-of-order data that has progressed to become the sole responsibility of the receiver, such as but not limited to data that has been delivered to the receiving application. NR-SACKs are primarily proposed to improve throughput for the Stream Control Transmission Protocol (SCTP). SCTP’s multistreaming service divides an end-to-end transport association into independent logical data streams. Data that arrives in-order within a stream can be delivered to a receiving application even if that data is out-of-order relative to other streams. A transport sender has no reason to maintain a copy of delivered data in its retransmission queue.
The term non-renegable refers to the fact that, according to current TCP and SCTP specifications, data that has been acked by a SACK, but not yet by a cumulative ack can be reneged. That is, the transport receiver can discard the SACKed data, thus requiring the transport sender to retransmit it. However, situations exist when a transport receiver knows that reneging will never take place. NR-SACKs are a mechanism to share this information with the transport sender. This research will (1) formally define the semantics of NR-SACKs in an Internet Draft, (2) estimate the potential throughput benefits of using NR-SACKs in SCTP via ns-2 simulation, and (3) demonstrate technical feasibility and actual benefits by deploying NR-SACKs into the latest FreeBSD version of SCTP.
Leonard Cimini Department of Electrical and Computer Engineering, University of Delaware Beamforming in IEEE 802.11n for Wide-Area Applications Sponsors: Brett Douglas, Jan Kruys
MIMO systems have been extensively studied and are now fairly well-understood. The antennas in a MIMO system can be employed in a number of ways. A spatial multiplexing gain can be achieved by transmitting independent data streams over individual antennas. The maximum gains are achieved when the channel is known at the transmitter and receiver and transmit precoding and receiver weighting are performed. Alternatively, the same stream can be sent over each antenna to obtain a diversity gain. When the channel is known a the transmitter, the data stream can be optimally weighted to maximize performance. If the channel is not known, diversity gain can be obtained using a space-time code. The IEEE 802.11 standard has been very successful, and the extension in 802.11n promises (i) increased data throughput through spatial multiplexing; and (ii) increased range through exploiting spatial diversity. In particular, for the high-throughput case, the transmitter is designed to operate with one to four independent data streams using one to four antennas, and several modes are described including spatial multiplexing, space-time block coding, or some combination. In addition, there are options for beamforming in which the transmitter utilizes the knowledge of the MIMO channel to improve reception at the receiver. The Spatial Multiplexing (SM) and Space-Time Block Coding (STBC) modes are fairly well understood. The advantage of transmit beamforming, given the overhead required, is less so; this is the focus of the currently funded project. Moreover, the application of 802.11n in outdoor environments and the effects (and mitigation of) interference have received very little attention; this is the focus of our new proposal.
Jason But Centre for Advanced Internet Architectures, Swinburne University of Technology FreeBSD Implementation of an SCTP friendly NAT Sponsor: Randall Stewart
Network Address Translation (NAT) is typically used to share a single Internet address amongst a number of users. Extending the common approach used in NAT implementations for TCP and UDP to the SCTP protocol is not viable - the SCTP protocol specification would require checksums for the whole packet (not just the header) to be re-calculated for each packet - particularly for small home router implementations. Further, SCTP also offers multi-homing which offers new challenges for the NAT code to track in a single SCTP connection. We propose to develop a NAT implementation to support SCTP to be released for the FreeBSD 6.2 (or its replacement as of August 2007) platform. Our release code will utilise an existing NAT framework such as ipfw or ipf such that it can be practically deployed on real systems. The NAT will track SCTP connections via the Verification Tag (VTag) field and retain connection details should one end of a multi-homed session change end-points. We also propose to test this implementation under a number of different usage and failure-mode scenarios, the results of these tests will be published and can be used to promote the use of SCTP "in-the-wild".
George Kesidis Department of Computer Science and Engineering; Department of Electrical Engineering, The Pennsylvania State University Per-flow state management in Internet routers: mass purging and heavy-hitter detection Sponsor: Cetin Seren
In the context of a surveillance system in an Internet router for all active TCP sessions, we will consider two problems. The first is the problem of simultaneously purging a potentially enormous number of deemed-stale TCP sessions and the second is identifying “heavy hitter” TCP sessions. Our approaches will be sensitive to the limited hardware and software resources allocated for this purpose in a linecard in addition to the very high data rates that modern linecards handle, specifically we are interested in avoiding excessive I/O to free-list memories. We propose to investigate three alternatives for memory purging: an opportunistic system that does employ a free-list, a framework involving logical swapping of a 1-bit flow enable and touch vectors that does not employ a free list, and finally a randomized system that also identifies the heavy hitter sessions with no additional state.
Aleksandar Kuzmanovic Department of Electrical Engineering and Computer Science, Northwestern University Diagnosing Spatio-Temporal Internet Congestion Properties Sponsor: Bruce Davie
The ability to accurately detect congestion events in the Internet and reveal their spatial (i.e., where they happen) and temporal (i.e., how frequently they occur and how long they last) properties would significantly improve our understanding of how the Internet operates. Moreover, the ability to accurately pinpoint congested locations in real time is useful for fault diagnosis, design of advanced delay-based congestion control protocols, and for efficient overlay-network construction. We propose to design and implement a novel measurement methodology and tool, which we call Pong, capable of accurately revealing spatio-temporal Internet properties. Pong (i) uses queuing delay as indicative of congestion, and (ii) strategically combines end-to-end probes with probes targeted to intermediate nodes. It (iii) achieves high sampling frequency and dramatically improves spatial detection granularity (i.e., from path segments to individual links), (iv) considerably enhances the measurement quality by adjusting the probing methodology based on the observed path topology, and (v) deterministically detects moments of its own inaccuracy. We propose to deploy a triggered-based monitoring system and utilize Pong measurements in the wide area Internet with the following goals: (i) Reveal joint spatio-temporal congestion characteristics of today’s Internet, (ii) study congestion patterns and understand correlation across multiple geographic areas and time-scales, (iii) expose the role of intra- and inter-AS routing and peering policies on inducing congestion events, and (iv) identify how network disruptions (and consequent re-routing events) affect spatio-temporal congestion properties in a given Internet area.
Constantine Dovrolis College of Computing, Georgia Institute of Technology Ingress Traffic Engineering and Performance Routing Sponsors: Dana Blair, Monique Morrow
In earlier research, we investigated the performance and stability of outbound traffic engineering in Optimized Edge Routing (OER). In this project, we will expand that research in two new directions. First, we will focus on ingress traffic engineering, again in the context of OER, but without using BGP. The motivation is that several multihomed stub networks do not run BGP, and further, using BGP for ingress traffic engineering raises concerns about the size of the DFZ routing table and the volume of BGP updates. Instead of BGP, we will investigate methods that conduct ingress traffic engineering using measurement-based DNS name resolution. Our research will model, simulate and experiment with the effectiveness of this DNS-based method, the impact of DNS caching, and the reliability of the associated active probing. In the second thread of this project, we will generalize the previous methods for outbound/inbound optimized edge routing in the direction of intradomain Performance Routing (PfR). PfR allows a router to dynamically sense congestion, or other network impairments, and dynamically reroute traffic through a better path. Our research in this area will focus on the fundamental concern: how to make sure that such dynamic routing will be stable and that it will actually improve application performance. Our preliminary results show that the appropriate measurement techniques combined with a necessary router coordination protocol can provide stable and effective adaptive routing.
King-Shan Lui Department of Electrical and Electronic Engineering, University of Hong Kong Network Parameter Representation and Quality of Service Routing in the Internet Sponsors: Kirk Lougheed, Fred Baker
Computer applications nowadays are very diversified in terms of network requirements. Conventional approach of representing metrics using numbers is not sufficient. For instance, we may want to describe survivability in terms of how likely a path can survive in different situations. In this case, a single number may not be appropriate. Even though some metrics can be represented by single values, when a parameter consists of more than one metric, such as delay and bandwidth, conventional representation is still problematic because comparisons are not trivial. To enhance the effectiveness of routing protocols and the reliability of networks, different kinds of network parameters representation have to be introduced. In this project, we aim at investigating how to represent and manipulate network parameters to facilitate more effective and accurate distribution of route advertisement so as to find more feasible paths for user services and failure recoveries in the Internet.
Rodney Tucker Department of Electrical and Electronic Engineering, University of Melbourne A Green Internet Sponsors: Jeff Allison, Garry Epps
The aim of this project is to develop a model of energy consumption in the Internet and to use this model to analyze the growth of energy consumption as the size and capacity of the network increases. We will focus on developing an understanding of technological barriers to growth of the network. The analysis will use models of the scaling properties of IP networks, based on fundamental considerations of network capacity, physical limitations of key technologies and an analysis of the inter-relationship between energy consumption and information flow.
Kevin Almeroth Department of Computer Science, University of California, Santa Barbara The Last Mile: Building the Final Piece in One-to-Many Content Distribution
There is a need to support multicast capability in the Internet's expansion at the edges (such as in consumer broadband networks). One particularly promising technology being standardized by the IETF is Automatic IP Multicast Without Explicit Tunnels, commonly known as AMT. The development of AMT has reached a point where relay and gateway functions need to be implemented and deployed. This proposal describes our planned efforts to develop software that offers the final piece of the multicast puzzle.
Magdalena Balazinska Computer Science and Engineering Department, University of Washington History-Enhanced Monitoring
A new class of general-purpose data management systems, called stream processing engines (SPEs), supports the needs of monitoring applications. The goal of existing SPEs is to provide low-latency processing of data that streams in from geographically distributed sources. Although monitoring applications focus on the current state of the system, when events of interest occur, we posit that historical information is necessary to explain these events and determine appropriate responses. The goal of this project is to explore techniques for enhancing the near-real-time information produced by an SPE with relevant historical data.
Olivier Bonaventure, Pierre Francois Computer Science and Engineering Department, Université Catholique de Louvain ICIM : Improving the Convergence of IP Multicast Routing Protocols
This project addresses the problem of fast recovery for multicast traffic after network topology changes. Two types of topology changes exist: urgent (such as sudden link failures) and non-urgent changes (such as changes in IGP metrics, manual link shutdowns, or linkup events). In this project we will rely on traces to characterize these events and evaluate their impact on multicast trees. Second, we use simulations to evaluate the convergence time of current PIM-SSM implementations in ISP networks. Then we rely on the ordered FIB updates extensions proposed for IS-IS to develop extensions to allow PIM-SSM routers to converge without packet losses after a non-urgent topology change. Finally, we propose fast-reroute techniques able to protect IP multicast traffic.
John Canny Computer Science Division, University of California, Berkeley MultiView Videoconferencing
Preservation of gaze (eye contact or gaze perception) is important for trust-building and persuasion among videoconference participants. The only way to preserve gaze in a group conference is using a MultiView display, which allows each participant to see a distinct, personal view of the other side. For this project we are developing and evaluating new MultiView systems and how they impact group-to-group communication. The goal is to build systems that, for the first time, reproduce all the advantages of a face-to-face meeting.
Cristian Estan Computer Science and Engineering Department, University of Wisconsin-Madison High Performance Intrusion Prevention in Software
This proposal focuses on finding algorithmic solutions that improve performance measures of software-based intrusion prevention systems. We wish first to improve throughput by extending the operation of traditional deterministic finite automata with counters in a way that reduces the number of states required for an automaton to match a set of signatures. This reduces the number of automata required to implement the full set of signatures. Second, we wish to improve performance by tuning algorithms and data structures to multicore processors, exploiting the parallelism of multiple threads without introducing extensive locking and synchronization overhead, and improving cache locality by careful scheduling.
Michalis Faloutsos Computer Science Department, University of California, Riverside Automated Traffic Classification: Benchmarks and Novel Tools
In the area of traffic classification and (its special case of) intrusion detection, there are two main challenges. First, there is no benchmark to assess and compare different approaches. Second, most approaches are either nonintuitive (based on obscure machine learning and statistical techniques), or intuitive approaches relying on human intervention or heuristics. Our first goal is to develop the first publicly available benchmark, based on carefully anonymized data collected from our campus with many traces at multiple levels (campus, department, lab). Second, we shall introduce statistical techniques into BLINC, a traffic classification technique we have developed, in a way that does not take away from its highly intuitive operation.
Paul Francis Computer Networking Department, Cornell University End-Middle-End Internet Connection Establishment
This proposal is an extension of a previous award, “Next Generation NAT and Firewall Traversal,” in which we focused on the problem of establishing data connections between hosts behind NATs and firewalls in a way that allows all stakeholders in the connection (endhost, enterprises, ISPs) to invoke their security policies. The technology, called NUTSS, is a name-based signaling architecture that couples off-path and optional on-path signaling components. In the next year we shall work on the goals of the EMERG (End-Middle-End Research Group) and in addition produce a publicly releasable NUTSS library, which we shall evolve to reflect EMERG output.
Edgar Gabriel Department of Computer Science, University of Houston Optimizing Collective File Operations over InfinBand, Gigabit Ethernet and Mixed Network Interconnects
For many applications in industry as well as in academic environments, a key challenge in the handling of large data sets is being able to access large files simultaneously with multiple processors and applications in the most efficient manner without generating inconsistencies in the file or the file system. In this project we will develop optimizations for collective I/O operations over InfiniBand, Gigabit Ethernet, and mixed network interconnects by analyzing the occurring communication patterns, then optimizing the resulting group communication using message segmentation, explicit handling of communication hierarchies, and using hardware support such as multicast if applicable.
Nancy Griffeth Department of Math and Computer Sciencev Lehman College Address Assignment in Traditional and Ad Hoc Networks
We shall carry out a theoretical and experimental study of algorithms for reliable assignment of IP addresses in spite of server failures, network failures, and node mobility. For traditional IP networks, both wired and wireless, we examine the proposed failover protocol for DHCP. For MANETs, we will examine and propose new algorithms for assigning IP-compatible addresses reliably and correctly. The central goals are to develop new insights into the best design for address-assignment mechanism for traditional networks and MANETs, to develop innovative algorithms for address assignment, and to explore improved methods for expressing requirements for Internet protocol standards.
Edward Knightly ECE and CS Departments, Rice University Achieving High Performance and Fairness in Multihop Wireless Access Networks
The first year of this project yielded four key outcomes: (1) expanded deployment of the TFA-Rice Wireless Mesh to nearly 1000 users, (2) completion of a measurement-driven study of mesh network deployment factors, (3) development of an analytical model to predict each flow's throughput in an arbitrary multihop topology of 802.11 nodes, and (4) development and study of new protocols to counter severe unfairness and starvation. In the next phase of this project we shall design, implement, and deploy a zero-overhead congestion control algorithm that operates purely at the wireline gateway; we shall also pursue measurement-driven protocol design, in which our discoveries from field measurements drive the design of optimized protocols.
Andrew Lumsdaine Computer Science Department, Indiana University Exploiting Multi-Path Routing for Collective Communication in MPI
Although Message Passing Interface (MPI) implementations have made considerable efforts in tuning the local communication stack to optimize point-to-point communication operations, optimization of collective routines in MPI requires information about the global network and is less well-studied. Accordingly, we shall develop collective routines for MPI that can fully exploit large-scale high-performance InfiniBand-based networks. In particular, we will study the use of the multiple equivalent paths between leaf and core switches in large-scale InfiniBand clusters to reduce switch-to-switch congestion during collective operations and therefore increase collective performance at scale.
Nick McKeown Electrical Engineering and Computer Science, Stanford University NetFPGA: An Open-source Teaching and Research Tool for Programmable Network Hardware
NetFPGA is a low-cost prototyping system for teachers and researchers for the design, implementation, and deployment of real networking hardware. NetFPGA is a low-cost PCI card with four Gigabit Ethernet ports, a large FPGA, and some buffer memory. Users implement designs using an industry-standard design flow (Verilog). NetFPGA will be made available at cost to educational institutions and nonprofits; Xilinx will donate the FPGA components, IP, and tools. In the proposed work, we will develop a self-supporting user community to allow NetFPGA to scale for networking hardware developers, in the way the open-source community has done for software.
Karen Sollins Mathematics and Computer Science Department, Massachusetts Institute of Technology Prediction Intelligence in the Network
The objective of this project is to address a set of questions about the utility, design, and placement of intelligence in the network. The work proposed here will concentrate on learning and prediction to improve routing. Because routing decisions are made inside the network, this will imply placement of certain amounts of learning and reasoning in the network, although the balance and tradeoffs with respect to communications costs, memory usage, complexity, and deployability remain key factors in our research. We also intend to be able to extend our work on routing to a DTN-like environment. This work comprises the core of the doctoral dissertation of Rob Beverly, under the supervision of Dr. Karen Sollins.
Alan Wagner Computer Science Department, University of British Columbia Compute- and Data-Intensive Processing using MPI over SCTP
Our goal is to provide a robust and secure system for the execution of data- and compute-intensive applications in cluster and grid environments. We propose to design, implement, evaluate, and release SCTP-based middleware for support of message-passing programs using MPI (Message Passing Interface). We intend to extend the design to MPI-2 to support dynamic processes and RDMA, and investigate the potential advantages of using SCTP in a cluster environment. We will integrate our SCTP-based middleware into MPICH2 and Open MPI, two public domain versions of MPI, to allow others to use and experiment with SCTP and MPI in cluster and grid environments.
Nelson da Fonseca Computer Engineering Department, State University of Campinas Dynamic Traffic Grooming with Support to QoS in IP over WDM Networks
Wavelength-division multiplexing (WDM) is the switching technology for the new generation of optical Internet, as it provides bandwidth at very large scale. The disparity between the bandwidth available in lightpaths and the demand of label switch paths (LSPs) has motivated the multiplexing of LSPs to a single lightpath. Our aim is to develop effective and efficient techniques for dynamic grooming of subwavelength LSPs into a lightpath without ignoring QoS requirements.
Kamil Sarac
Computer Science Department, University of Texas at Dallas The Last Mile: Building the Final Piece in One-to-Many Content Distribution
There is a need to support multicast capability in the Internet's expansion at the edges (e.g. , consumer broadband networks like DSL and cable. One particularly promising technology being standardized by the IETF is Automatic IP Multicast Without Explicit Tunnels, commonly known as AMT. The development of AMT has reached a point where relay and gateway functionality need to be implemented and deployed. In this proposal, we describe our planned efforts to develop the software to offer the final piece of the multicast puzzle.
