Cisco Research

The IT equipment comprising the Internet and the devices that connect to it use approximately 74TWh/yr (about $6 billion) of electricity every year in the USA. Much of this electricity is wasted on idle, but fully powered-up, desktop PCs and on nearly idle network links operating at high data rates. We quantify the energy use of networks and describe current regulatory directions that may encourage developers and users of networks - including operators of data centers - to seek greater efficiencies. The average utilization of Ethernet links is generally very low and thus there is a potential for energy savings by using an Adaptive Link Rate (ALR) protocol that matches link rate to utilization. Such a protocol - possibly to be named Rapid PHY Selection (RPS) - will be considered in November 2006 by the IEEE 802.3 for possible entry into a formal study group. Our simulation results show that ALR can save considerable energy at very small trade-off in increased packet delay. ALR presents interesting challenges in designing control polices for determining when to change the link data rate. For 10Gb/s Ethernet, ALR has significant potential to reduce overall data center energy consumption. We are also exploring how to reduce induced energy use. Power management proxying is being explored for P2P and other applications. One direction for proxying is a "Smart NIC" or "Smart Line Card" where proxying becomes a capability that a desktop NIC or switch line card can support. We will describe preliminary results and future directions for ongoing work in proxying.

Ken Christensen is an Associate Professor in the Department of Computer Science and Engineering at the University of South Florida. His research in energy efficiency of computer networks is currently funded by the National Science Foundation.

Bruce Nordman is a Principal Research Associate in the Energy Analysis Department, Environmental Energy Technologies Division, of Lawrence Berkeley National Laboratory Berkeley, California. His research is funded by the California Energy Commission and the EPA/Energy Star Program.

This proposal focuses on improving the throughput of software-based intrusion prevention systems running on general purpose processors. The two main approaches we plan to consider are the use of multi-core processors, and algorithmic improvements. We plan to use the open source IPS/IDS, Snort, to measure the performance impact of various improvements.

Cristian Estan started as an assistant professor of Computer Science at the University of Wisconsin-Madison in the fall of 2004. His research focuses on Internet traffic measurement and analysis. The primary aim of his traffic analysis efforts is to achieve a better understanding of how the network is used (and sometimes misused). The ultimate goal is to be able to build systems that analyze the traffic and make decisions about controlling it in real time (e.g. when the system detects a new worm epidemic, it instructs the routers and firewalls to filter the new worm out).

Before receiving his Ph.D. from UCSD under the supervision of George Varghese, he spent a year in the Ph.D. program of Cornell. He has a Master's and an Engineer (5 year undergraduate curriculum) degree in Computer Science from the Technical University of Cluj-Napoca (1996 and 1995 respectively). He has worked as software developer at two startups, Ensim, and Netsift in 2000 and 2004 respectively. He has worked as network administrator at the second largest node of the Romanian academic network from 1995 to 1998.

Who uses the network? What kind of applications do we see?
Can we detect attacks and viruses? Can we detect when a user is under attack? In this talk, we provide an overview of our work to answer the above questions. More specifically, we address the problems of traffic classification, and host profiling.

First, we present a fundamentally different approach to classifying traffic flows according to the applications that generate them. In contrast to previous methods, our novel graph-based approach is based on observing and identifying patterns of host behavior at the transport layer. We analyze these patterns at three levels of increasing detail (i) the social, (ii) the functional and (iii) the application level.

Second, we modify our approach for profiling the end-host behavior by looking at each interaction. We propose techniques to summarize, and evolve over time the profiles of hosts. We argue that our approach could aid in identifying attacks at the user and at the enterprise level.

Michalis Faloutsos is a faculty member at the Computer Science Dept in University of California, Riverside. He got his bachelor's degree at the National Technical University of Athens and his M.Sc and Ph.D. at the University of Toronto. His interests include, Internet protocols and measurements, peer-to-peer networks, network security, BGP routing, and ad-hoc networks. He is actively involved in the community as a reviewer and a TPC member in many conferences and journals.

With his two brothers, he co-authored the paper on power laws of the Internet topology (SIGCOMM'99). His most recent work on peer-to-peer measurements have been widely cited in popular printed and electronic press such as Slashdot, ACM Electronic News, USA Today, and Wired.

Most recently he has focused on the classification of traffic and identification of abnormal network behavior. In a nutshell, his research interests are:

• measurements: Internet backbone traffic, end user profiling
• modeling and mining graphs (computer, biological, social networks)
• routing protocols: BGP, ad hoc networks, and multicast
• security: detecting abnormalities, improving the robustness of BGP routing, safeguarding ad hoc networks

Internet routers require buffers to hold packets during times of congestion. The buffers need to be fast, and so ideally they should be small enough to use fast memory technologies such as SRAM or all-optical buffering. Unfortunately, a widely used rule-of-thumb says we need a bandwidth-delay product of buffering at each router so as not to lose link utilization. This can be prohibitively large. In a recent paper, Appenzeller et al. challenged this rule-of-thumb and showed that for a backbone network, the buffer size can be divided by v(N) without sacrificing throughput, where N is the number of flows sharing the bottleneck. In this work, we explore how buffers in the backbone can be significantly reduced even more, to as little as a few dozen packets, if we are willing to sacrifice a small amount of link capacity. We argue that if TCP sources are not overly bursty, then fewer than twenty packet buffers are sufficient for high throughput. Specifically, we argue that O(log W) buffers are sufficient, where W is the maximum window size of each flow. We support our claim with analysis and a variety of simulations. The change we need to make to TCP is minimal---each sender just needs to pace packet injections from its window. Moreover, there is some evidence that such small buffers are sufficient even if we don't modify the TCP sources so long as the access network is much slower than the backbone, which is true today and likely to remain true in the future.We conclude that buffers can be made small enough for all-optical routers with small integrated optical buffers.

Yashar Ganjali is with High Performance Networking Group at Stanford University, where he is working toward his PhD degree. He has got a BSc in Computer Engineering from Sharif University of Technology, Tehran, Iran in 1999, and a MSc in Computer Science from University of Waterloo, Waterloo, Canada in 2001. He is currently involved with the buffer sizing project; the goal is finding out the impact of reducing the buffer size in core routers from millions of packets to just tens of packets, and thus exploring the possibility of building all-optical networks. His other research interests include analysis and design of high performance switches, scheduling algorithms, congestion control, routing protocols, and network optimization.

The traditional view of routing algorithms and protocols has focused on the type of information exchanged among nodes (routers) to compute paths to destinations. For instance, most books and chapters refer to routing protocols in the Internet as being based on the link-state approach or the distance-vector approach, with some further mentioning "path vectors". In this talk, I will try to make the case that what matters in the study of distributed routing algorithms is not the type of information exchanged among routers, but rather the mechanisms used by the routers to ensure that the distributed computations they perform converge within a finite time to correct results. Furthermore, I will argue that the inherent operation needed in any type of routing algorithm is the ordering of nodes in a graph, which can be total ordering or partial ordering. I will use examples related to wireless ad hoc networks, simply because there has been much more research done for ad hoc networks than for wired networks in recent years.

J.J. Garcia-Luna-Aceves holds the Jack Baskin Chair of Computer Engineering at the University of California, Santa Cruz (UCSC), and is a Principal Scientist at the Palo Alto Research Center (PARC). Prior to joining UCSC in 1993, he was a Center Director at SRI International (SRI) in Menlo Park, California. He has been a Visiting Professor at Sun Laboratories and a Principal of Protocol Design at Nokia.

Dr. Garcia-Luna-Aceves has published a book, more than 320 papers, and 23 U.S. patents. He has directed 26 Ph.D. theses and 20 M.S. theses since he joined UCSC in 1993. He has been the General Chair of the IEEE SECON 2005 Conference; Program Co-Chair of ACM MobiHoc 2002 and ACM Mobicom 2000; Chair of the ACM SIG Multimedia; General Chair of ACM Multimedia '93 and ACM SIGCOMM '88; and Program Chair of IEEE MULTIMEDIA '92, ACM SIGCOMM '87, and ACM SIGCOMM '86. He has served in the IEEE Internet Technology Award Committee, the IEEE Richard W. Hamming Medal Committee, and the National Research Council Panel on Digitization and Communications Science of the Army Research Laboratory Technical Assessment Board. He has been on the editorial boards of the IEEE/ACM

Transactions on Networking, the Multimedia Systems Journal, and the Journal of High Speed Networks. He is the co-recipient of the IEEE MASS 2005 Best Paper Award and the Best Student Paper Award of the 1998 IEEE International Conference on Systems, Man, and Cybernetics. He received the SRI International Exceptional-Achievement Award in 1985 for his work on multimedia communication and in 1989 for his work on routing algorithms. He was elected Fellow of the IEEE for contributions to the theory and design of network protocols for network routing and channel access.

Faced with mounting evidence of our own irrelevance, and feeling an increasing sense of intellectual stagnation, many in the academic Internet research community are ready for a change. There are two major NSF-sponsored efforts underway to effect this change, GENI and FIND. GENI is a large-scale experimental infrastructure, modeled on Planetlab but designed to be far more general, flexible and network- oriented. FIND is an NSF program to explore what a clean-sheet redesign of the Internet architecture might look like. FIND's goal is not to replace the current Internet, but to entertain a wider set of design possibilities that might inform and guide the Internet's future evolution. While they have generated much excitement within the community, it remains to be seen whether these exercises are fruitful or folly.

In this talk he begins with a very quick review of GENI and FIND, and then share some initial architectural thoughts. In doing so he will touch on an idiosyncratic set of topics, ranging from self-certifying names to incorporating middleboxes to distributed debugging.

Scott Shenker is a Professor of Computer Science at UC Berkeley. He is also the head of the Networking Group and the Vice President of the International Computer Science Institute in Berkeley, California. He received his Sc.B. in Physics from Brown University in 1978, and his PhD in Physics from University of Chicago in 1983. He is a Fellow of the ACM and IEEE.

In 2002, Scott Shenker received the SIGCOMM Award is in recognition of his "contributions to Internet design and architecture, to fostering research collaboration, and as a role model for commitment and intellectual rigor in networking research".

In 2006, he received the IEEE Internet Award "For contributions towards an understanding of resource sharing on the Internet."

You've probably seen tons of paper about "throughput" - how to maximize it, how to achieve 100% throughput, and clever algorithms that come close. You see it in marketing literature too: "our switch has higher throughput than theirs". In the talk I'll give a (speedy) potted history about throughput in switches. What exactly is throughput, why does it matter, why did we think it was hard to achieve high throughput. And why, with the benefit of hindsight, it was much probably much easier than we thought. (The answer usually involves including a speedup of two somewhere and/or load-balancing).

In a follow up talk in the New Year, I'll describe how 100% throughput using load-balancing led to the design of the first Juniper routers, how it might lead to simple passive optical switched backplanes, how a switch with 100% throughput doesn't mean a network with 100% throughput; and how you can design whole networks with guaranteed throughput. This is how I wasted away the 1990s.

Nick McKeown is an Assistant Professor of Electrical Engineering and Computer Science at Stanford University. He received his PhD from the University of California at Berkeley in 1995. From 1986-1989 he worked for Hewlett-Packard Labs, in their network and communications research group in Bristol, England. Nick's research interests include the architecture, analysis and design of high performance switches and Internet routers, IP lookup and classification algorithms, scheduling algorithms, Internet traffic analysis, traffic modeling and network processors.

We discuss the role of optical technology in switching architectures. The design of these architectures for future telecommunication networks needs to consider the limits imposed by electronic technology.
The question is: can optics help?

Currently, optical technology is exploited mainly for transmissions over optical links requiring great bandwidth-distance products; however, many researchers and switch architects believe that its introduction in switching functions can overcome most of the current design limits.

Since many years, the research community has been studying not only solutions that make use of optics inside electronic switches, but also switching architectures that implement optical switching without any need of optoelectronic conversion. We propose a solution that tries to exploit electronics and optics peculiarities for the design of high-speed switches.

The talk is focused on the OSATE (Optics in Switching Architecture: Theory and Experimentation) project, which contemplates the development of a switch prototype equipped with FPGA-based Gigabit Ethernet cards, connected to a dual WDM (Wavelength Division Multiplexing) optical ring that acts as the prototype switching fabric.

The FPGA includes not only Ethernet protocol functions but also the control logic required to drive optical interfaces and to regulate access to the optical bus.

Access protocol and fairness issues arising when accessing the WDM optical bus are discussed, with particular attention to solutions providing not only fairness and high throughput but also controlled access delays.

Andrea Bianco is Associate Professor at the Dipartimento di Elettronica of Politecnico di Torino, Italy. He holds a Dr. Ing. degree in Electronics Engineering (since 1986) and a Ph.D. in Telecommunications Engineering (since 1994) both from Politecnico di Torino.

Currently, he is leading the National project on scalable software router BORA-BORA; he is deeply involved in the OSATE Italian project on the construction of an optical demonstrator of an optical switch, and in the European Network of Excellence on Optical Networks e-PHOTON/ONe.

He has co-authored over 100 papers published in international journals and presented in leading international conferences in the area of telecommunication networks. He was Technical Program Co-Chair for HPSR (High Performance Switching and Routing) 2003 and for DRCN (Design of Reliable Communication Networks) 2005.

He was a member of the TPC of several conferences, including IEEE INFOCOM, IFIP ONDM (Optical Networks Design and Modeling), HPSR (High Performance Switching and Routing), IEEE GLOBECOM, IEEE ICC, Hot Interconnects (HotI), and Networking. His main research interest include high speed switching architectures, scheduling in Input Queuing switches, software router architectures, access protocols for all-optical networks and all-optical switch architectures

We present some new results for Bloom filters, a randomized data structure for set membership queries based on hashing. Bloom filters require very small amounts of space, but allow false positives; they may return that a query item is in the set even if it is not.

We first show that Bloom filters, which normally require k hash functions, can be modified so that only 2 hash functions are required, with no effect on the asymptotic false positive probability. This may simplify the use of Bloom filters in many practical situations.

We then show how Bloom filters can be used in conjunction with the power of two choices to design very effective hash tables, suitable for use in routers and other situations that require highly efficient and effective hash tables under strict memory limitations.

Time permitting, we will also present further results of our ongoing work on the Bloom filter data structure.

Michael Mitzenmacher is a Professor of Computer Science in the Division of Engineering and Applied Sciences at Harvard University. Michael has authored or co-authored over 100 conference and journal publications on a variety of topics, including Internet algorithms, hashing, load-balancing, erasure codes, error-correcting codes, compression, bin-packing, and power laws. His work on low-density parity-check codes shared the 2002 IEEE Information Theory Society Best Paper Award. His first textbook on probabilistic techniques in computer science, co-written with Eli Upfal, was published in 2005 by Cambridge University Press.

Michael Mitzenmacher graduated summa cum laude with a degree in mathematics and computer science from Harvard in 1991. After studying math for a year in Cambridge, England, on the Churchill Scholarship, he obtained his Ph. D. in computer science at U.C. Berkeley in 1996.He then worked at Digital Systems Research Center until joining the Harvard faculty in 1999.