Natasha Gude, Ben Pfaff, Teemu Koponen, Martín Casado, Scott Shenker, Justin Pettit, ...
This article is an editorial note submitted to CCR. It has NOT been peer reviewed. Authors take full responsibility for this article’s technical content. Comments can be posted through CCR Online....
1 Practical Algorithms for Performance Guarantees in Buffered Crossbars (2009)
Shang-tse Chuang, Sundar Iyer, Nick Mckeown
Abstract — This paper is about high capacity switches and routers that give guaranteed throughput, rate and delay guarantees. Many routers are built using input queueing or combined input and...
Obtaining High Throughput in Networks with Tiny Buffers (2009)
Neda Beheshti, Yashar Ganjali, Ashish Goel, Nick Mckeown
Abstract — In this paper we explore whether a general topology network built up of routers with very small buffers, can maintain high throughput under TCP’s congestion control mechanism. Recent...
OpenFlow: Enabling Innovation in Campus Networks (2009)
Nick Mckeown, Scott Shenker, Tom Anderson, Larry Peterson, Jonathan Turner, Hari Balakrishnan, ...
This article is an editorial note submitted to CCR. It has NOT been peer reviewed. Authors take full responsibility for this article’s technical content. Comments can be posted through CCR Online....
Glen Gibb, John W. Lockwood, Jad Naous, Paul Hartke, Nick Mckeown
Abstract—The NetFPGA platform enables students and researchers to build high-performance networking systems using Field Programmable Gate Array (FPGA) hardware. A new version of the NetFPGA...
Neda Beheshti, Nick Mckeown, Yashar Ganjali, Jad Naous, Monia Ghobadi, Geoff Salmon
It is commonly believed that the Internet has deficiencies that need to be fixed. However, making changes to the current Internet infrastructure is not easy, if possible at all. Any new protocol or...
Designing a Fault-Tolerant Network Using Valiant Load-Balancing (2009)
Abstract—Commercial backbone networks must continue to operate even when links and routers fail. Routing schemes such as OSPF, IS-IS, and MPLS reroute traffic, but they cannot guarantee that the...
Buffer Sizing results for RCP Congestion Control under Connection Arrivals and Departures (2009)
Ashvin Lakshmikantha, Nick Mckeown, R. Srikant, Nandita Dukkipati, Carolyn Beck
Buffer sizing has received a lot of attention recently since it is becoming increasingly difficult to use large buffers in highspeed routers. Much of the prior work has concentrated on analyzing the...
Implementing an OpenFlow Switch on the NetFPGA platform (2009)
G. Adam Covington, Jad Naous, David Erickson, Nick Mckeown
We describe the implementation of an OpenFlow Switch on the NetFPGA platform. OpenFlow is a way to deploy experimental or new protocols in networks that carry production traffic. An OpenFlow network...
Experimenting with Buffer Sizes in Routers (2009)
Neda Beheshti, Jad Naous, Nick Mckeown, Yashar Ganjali
Recent theoretical results in buffer sizing research suggest that core Internet routers can achieve high link utilization, if they are capable of storing only a handful of packets. The underlying...
Guaranteeing Quality of Service to Peering Traffic (2009)
Abstract—Network operators connect their backbone networks together at peering points. It is well known that the peering points are the most congested parts of the backbone network. Network...
Obtaining High Throughput in Networks with Tiny Buffers (2009)
Neda Beheshti, Yashar Ganjali, Ashish Goel, Nick Mckeown
Abstract — In this paper we explore whether a general topology network built up of routers with very small buffers, can maintain high throughput under TCP’s congestion control mechanism. Recent...
Abstract SANE: A Protection Architecture for Enterprise Networks (2009)
Martin Casado, Tal Garfinkel, Aditya Akella, Michael J. Freedman, Dan Boneh, Nick Mckeown, ...
Connectivity in today’s enterprise networks is regulated by a combination of complex routing and bridging policies, along with various interdiction mechanisms such as ACLs, packet filters, and...
Collaborative Research: ITR/ANIR: 100 Mb/sec For 100 Million Households (2008)
Hui Zhang, David A. Maltz, Edward W. Knightly, Contributors John, C-i. Chuang, Er Fraser, ...
Prototyping Fast, Simple, Secure Switches for Ethane (2008)
Jianying Luo, Justin Pettit, Martin Casado, John Lockwood, Nick Mckeown
We recently published our proposal for Ethane: A cleanslate approach to managing and securing enterprise networks. The goal of Ethane is to make enterprise networks (e.g. networks in companies,...
The Tiny Tera: 1 A Packet Switch Core (2008)
Nick Mckeown, Martin Izzard, Adisak Mekkittikul, William Ellersick, Mark Horowitz
Abstract — In this paper, we present the Tiny Tera: a small packet switch with an aggregate bandwidth of 320Gb/s. The Tiny Tera is a CMOS-based input-queued, fixed-size packet switch suitable for a...
The Tiny Tera: 1 A Packet Switch Core (2008)
Nick Mckeown, Martin Izzard, Adisak Mekkittikul, William Ellersick, Mark Horowitz
Abstract — In this paper, we present the Tiny Tera: a small packet switch with an aggregate bandwidth of 320Gb/s. The Tiny Tera is a CMOS-based input-queued, fixed-size packet switch suitable for a...
Building a RCP (Rate Control Protocol) Test Network ∗ (2008)
Ita Dukkipati, Glen Gibb, Nick Mckeown, Jiang Zhu
We recently proposed the Rate Control Protocol (RCP) as way to minimize download times (or flow-completion times). Simulations suggest that if RCP were widely deployed, downloads would frequently...
ABSTRACT Part III: Routers with very small buffers ∗ (2008)
Mihaela Enachescu, Ashish Goel, Tim Roughgarden, Yashar Ganjali, Nick Mckeown
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...
ABSTRACT Part III: Routers with Very Small Buffers ∗ (2008)
Mihaela Enachescu, Ashish Goel, Tim Roughgarden, Yashar Ganjali, Nick Mckeown
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...
Prototyping Fast, Simple, Secure Switches for Ethane (2008)
Jianying Luo, Justin Pettit, Martin Casado, John Lockwood, Nick Mckeown
We recently published our proposal for Ethane: A cleanslate approach to managing and securing enterprise networks. The goal of Ethane is to make enterprise networks (e.g. networks in companies,...
A 50 Gb/s 32 × 32 CMOS Crossbar Chip using Asymmetric Serial Links* (2008)
Shang-tse Chuang, Nick Mckeown, Mark Horowitz
A synchronous crossbar chip was designed in a 0.27μm CMOS technology for use in a high-speed network switch [1]. The crossbar chip uses 32 Asymmetric Serial Links [2] [3] to achieve high speed at...
Abstract SANE: A Protection Architecture for Enterprise Networks (2008)
Martin Casado, Tal Garfinkel, Aditya Akella, Michael J. Freedman, Dan Boneh, Nick Mckeown, ...
Connectivity in today’s enterprise networks is regulated by a combination of complex routing and bridging policies, along with various interdiction mechanisms such as ACLs, packet filters, and...
ABSTRACT Update on Buffer Sizing in Internet Routers ∗ (2008)
In the past two years, several papers have proposed rules that suggest two to five orders of magnitude reduction in Internet core router buffers. Others present scenarios where buffer sizes need to...
Abstract Prototyping Fast, Simple, Secure Switches for Ethane (2008)
Jianying Luo, Justin Pettit, Martin Casado, John Lockwood, Nick Mckeown
We recently proposed Ethane: A clean-slate approach to managing and securing enterprise networks. The goal of Ethane is to make enterprise networks (e.g. networks in companies, universities, and home...
The Throughput of a Buffered Crossbar Switch (2008)
Mingjie Lin Student, Mingjie Lin, Student Member, Nick Mckeown, Senior Member
The throughput of an input-queued crossbar switch -- with a single FIFO queue at each input -- is limited to ## # # # ##### for uniformly distributed, Bernoulli i.i.d. arrivals of fixed length...
Recent Results on Sizing Router Buffers (2008)
Guido Appenzeller, Nick Mckeown, Joel Sommers, Paul Barford
Today all Internet routers are built with buffers that hold packets in times of congestion. These buffers can typically store...
Designing a Predictable Internet Backbone Network (2008)
Designing a backbone network is hard. On one hand, users expect the network to have very high availability, little or no congestion, and hence little or no queueing delay. On the other hand, tra#c...
Routing in a Highly Dynamic Topology (2008)
Routing in mobile ad-hoc networks is hard because the topology can change very rapidly. By the time new paths are discovered, the network can change again -- and in extreme cases, packets circulate...
Achieving 100% Throughput in an Input-Queued Switch (2007)
Nick Mckeown, Adisak Mekkittikul, Venkat Anantharam, Jean Walrand
It is well known that head-of-line (HOL) blocking limits the throughput of an input-queued switch with FIFO queues. Under certain conditions, the throughput can be shown to be limited to...
Devavrat Shah, Sundar Iyer, Balaji Prabhakar, Nick Mckeown
Packet switches (that is, IP routers and ATM and Ethernet switches) maintain statistics for performance monitoring, network management, security, network tracing, and traffic engineering. Counters...
nickre @ ee.stanford.edu (2007)
Nick Mckeown, Venkat Anantharam, Jean Walrand
{ ananth,wlr} @ eecs.berkeley. edu It is well known that head-of-line (HOL) blocking limits the throughput of an input-queued switch with FIFO queues. Under certain conditions, the throughput can be...
Is IP going to take over the world (of communications)? (2007)
While it is technically pleasing to believe that IP will dominate all forms of communication, our delight in its elegance is making us overlook its shortcomings. IP is an excellent means to exchange...
Is IP going to take over the world (of communications)? (2007)
While it is technically pleasing to believe that IP will dominate all forms of communication, our delight in its elegance is making us overlook its shortcomings. IP is an excellent means to exchange...
1 The Tiny Tera: 1 A Packet Switch Core (2007)
Nick Mckeown, Martin Izzard, Adisak Mekkittikul, William Ellersick, Mark Horowitz
Abstract--- In this paper, we present the Tiny Tera: a small packet switch with an aggregate bandwidth of 320Gb/s. The Tiny Tera is a CMOS-based input-queued, fixed-size packet switch suitable for a...
Baybridge Ahigh Speed, Nick Mckeown, Ri Edell Mytle
The BayBridge is a highperformance bridge/routerdesignedforhigh throughputbridgingandroutinginhardwarebetweentwonetworkports. Thefirstprototypemayoperateasanencapsulatingtwo-portremote...
1 Algorithms for Packet Classification (2007)
The process of categorizing packets into "flows " in an Internet router is called packet classification. All packets belonging to the same flow obey a pre-defined rule and are...
The Tiny Tera: 1 A Packet Switch Core (2007)
Nick Mckeown, Martin Izzard, Adisak Mekkittikul, William Ellersick, Mark Horowitz
Abstract — In this paper, we present the Tiny Tera: a small packet switch with an aggregate bandwidth of 320Gb/s. The Tiny Tera is a CMOS-based input-queued, fixed-size packet switch suitable for a...
Compressed Domain Processing (2007)
And The Committee, Nick Mckeown, Scott Nathan Levine
this dissertation and that in my opinion it is fully adequate, in scope and in quality, as a dissertation for the degree of Doctor of Philosophy
A Load-Balanced Switch with an Arbitrary (2007)
Number Of Linecards, Isaac Keslassy, Shang-tse Chuang, Nick Mckeown
The load-balanced switch architecture is a promising way to scale router capacity. It requires no centralized scheduler, requires no memory operating faster than the line-rate, and can be built using...
Circuit switches have simpler data paths and are potentially much faster than packet switches. Taking advantage of this difference makes very high capacity all-optical circuit switches feasible,...
ETHANE: Taking Control of the Enterprise (2007)
Martín Casado, Michael J. Freedman, Justin Pettit, Jianying Luo, Nick Mckeown, Scott Shenker
This paper presents Ethane, a new network architecture for the enterprise. Ethane allows managers to define a single networkwide fine-grain policy, and then enforces it directly. Ethane couples...
ETHANE: Taking Control of the Enterprise (2007)
Martìn Casado, Michael J. Freedman, Justin Pettit, Jianying Luo, Nick Mckeown
This paper presents Ethane, a new network architecture for the enterprise. Ethane allows managers to define a single networkwide fine-grain policy, and then enforces it directly. Ethane couples...
Netfpga - an open platform for gigabit-rate network switching and routing (2007)
John W. Lockwood, Nick Mckeown, Greg Watson, Glen Gibb, Paul Hartke, Jad Naous, ...
The NetFPGA platform enables students and researchers to build high-performance networking systems in hardware. A new version of the NetFPGA platform has been developed and is available for use by...
ETHANE: Taking Control of the Enterprise (2007)
Martìn Casado, Michael J. Freedman, Justin Pettit, Jianying Luo, Nick Mckeown
This paper presents Ethane, a new network architecture for the enterprise. Ethane allows managers to define a single networkwide fine-grain policy, and then enforces it directly. Ethane couples...
Routers with Very Small Buffers (2006)
Mihaela Enachescu, Ashish Goel, Tim Roughgarden, Yashar Ganjali, Nick Mckeown
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...
Routers with Very Small Buffers (2006)
Mihaela Enachescu Yashar, Mihaela Enachescu, Yashar Ganjali, Ashish Goel, Nick Mckeown, Tim Roughgarden
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...
Routers with Very Small Buffers (2006)
Mihaela Enachescu, Yashar Ganjali, Ashish Goel, Nick Mckeown, Tim Roughgarden
Abstract — 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...
RCP-AC: Congestion Control to make flows complete quickly in any environment (2006)
Abstract — We believe that a congestion control algorithm should make flows finish quickly- as quickly as possible, while staying stable and fair among flows. Recently, we proposed RCP (Rate...
Buffer sizing in all-optical packet switches (2006)
Neda Beheshti, Yashar Ganjali, Ramesh Rajaduray, Daniel Blumenthal, Nick Mckeown
Abstract: Packet-switched routers need buffers during times of congestion. We show that a combined input-output queued router needs no more buffering than an output queued router. Using simulations,...
Routers with Very Small Buffers (2006)
Mihaela Enachescu, Yashar Ganjali, Ashish Goel, Nick Mckeown, Tim Roughgarden
Abstract — 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...
Designing a Predictable Internet Backbone with Valiant Load-Balancing (2005)
Abstract. Network operators would like their network to support current and future traffic matrices, even when links and routers fail. Not surprisingly, no backbone network can do this today: It is...
Practical Algorithms for Performance Guarantees in Buffered Crossbars (2005)
Shang-Tse Chuang, Sundar Iyer, Nick Mckeown
This paper is about high capacity switches and routers that give guaranteed throughput, rate and delay guarantees. Many routers are built using input queueing or combined input and output queueing...
Isaac Keslassy, Cheng-shang Chang, Nick Mckeown, Duan-Shin Lee
This paper is about load-balancing packets across multiple paths inside a switch, or across a network. It is motivated by the recent interest in load-balanced switches. Load-balanced switches provide...
Isaac Keslassy, Cheng-shang Chang, Nick Mckeown, Duan-shin Lee
Abstract — This paper is about load-balancing packets across multiple paths inside a switch, or across a network. It is motivated by the recent interest in load-balanced switches. Load-balanced...
Stability analysis of explicit congestion control protocols (2005)
Hamsa Balakrishnan, Ita Dukkipati, Nick Mckeown, Claire J. Tomlin
Abstract—In the context of explicit congestion control protocols like XCP and RCP where the equilibrium queue lengths are zero, we show that the stability region derived from traditional Nyquist...
Stability analysis of explicit congestion control protocols (2005)
Hamsa Balakrishnan, Ita Dukkipati, Nick Mckeown, Claire J. Tomlin
Much recent attention has been devoted to analyzing the stability of congestion control algorithms, in the context of TCP modifications (e.g., TCP/RED [10], [15], FAST [17]) and new protocols (e.g.,...
Processor sharing flows in the internet (2005)
Ita Dukkipati, Masayoshi Kobayashi, Rui Zhang-shen, Nick Mckeown
Abstract. Most congestion control algorithms try to emulate processor sharing (PS) by giving each competing flow an equal share of a bottleneck link. This approach leads to fairness, and prevents...
Using Hardware to Configure a Load-Balanced Switch (2005)
Srikanth Arekapudi, Shang-tse Chuang, Isaac Keslassy, Nick Mckeown
Efficient router architectures should have predictable throughput and scalable capacity, as well as internal optical technology (such as optical switches and wavelength division multiplexing) that...
Isaac Keslassy, Cheng-shang Chang, Nick Mckeown, Duan-shin Lee
Abstract — This paper is about load-balancing packets across multiple paths inside a switch, or across a network. It is motivated by the recent interest in load-balanced switches. Load-balanced...
All Internet routers contain bu#ers to hold packets during times of congestion. Today, the size of the bu#ers is determined by the dynamics of TCP's congestion control algorithm. In particular,...
Guido Appenzeller, Isaac Keslassy, Nick Mckeown
All Internet routers contain bu#ers to hold packets during times of congestion. Today, the size of the bu#ers is determined by the dynamics of TCP's congestion control algorithm. In particular,...
Configuring a load-balanced switch in hardware (2004)
Srikanth Arekapudi, Shang-tse Chuang, Isaac Keslassy, Nick McKeown
Abstract — The load-balanced switch architecture is a promising way to scale router capacity. We explained in [1] how it can be used to build a 100Tb/s router with no centralized scheduler, no...
A Load-Balanced Switch with an Arbitrary Number of Linecards (2004)
Isaac Keslassy, Shang-Tse Chuang, Nick McKeown, Number Of Linecards
The load-balanced switch architecture is a promising way to scale router capacity. It requires no centralized scheduler, requires no memory operating faster than the line-rate, and can be built using...
Guido Appenzeller, Isaac Keslassy, Nick McKeown
All Internet routers contain bu#ers to hold packets during times of congestion. Today, the size of the bu#ers is determined by the dynamics of TCP's congestion control algorithm. In particular,...
Configuring a loadbalanced switch in hardware,” under review (2004)
Srikanth Arekapudi, Shang-tse Chuang, Isaac Keslassy, Nick Mckeown
Abstract — The load-balanced switch architecture is a promising way to scale router capacity. We explained in [1] how it can be used to build a 100Tb/s router with no centralized scheduler, no...
Scaling Internet routers using optics (2003)
Isaac Keslassy, Shang-tse Chuang, Kyoungsik Yu, David Miller, Mark Horowitz, Olav Solgaard, ...
Routers built around a single-stage crossbar and a centralized scheduler do not scale, and (in practice) do not provide the throughput guarantees that network operators need to make efficient use of...
Analysis of the parallel packet switch architecture (2003)
Abstract-- Our work is motivated by the desire to design packet switches with large aggregate capacity and fast line-rates. In this paper, we consider building a packet-switch from multiple, lower...
Maximum Size Matching is Unstable for Any Packet Switch (2003)
Isaac Keslassy, Rui Zhang-shen, Nick Mckeown, Senior Member
Input-queued packet switches use a matching algorithm to configure a nonblocking switch fabric (e.g., a crossbar). Ideally, the matching algorithm will guarantee 100% throughput for a broad class of...
Scaling Internet Routers Using Optics (2003)
Isaac Keslassy, Shang-Tse Chuang, Kyoungsik Yu, David Miller, Mark Horowitz, Olav Solgaard, ...
Routers built around a single-stage crossbar and a centralized scheduler do not scale, and (in practice) do not provide the throughput guarantees that network operators need to make e#cient use of...
Cioq Switches Sundar, Sundar Iyer, Associate Member, Nick Mckeown, Senior Member
We recently proposed Constraint Sets as a simple technique to analyze routers with a single stage of buffering. In this letter, we extend the technique to analyze combined input and output (CIOQ)...
Maximum Size Matching Is Unstable for Any Packet Switch (2003)
Isaac Keslassy, Rui Zhang-Shen, Nick McKeown
Input-queued packet switches use a matching algorithm to configure a non-blocking switch fabric (e.g. a crossbar). Ideally, the matching algorithm will guarantee 100% throughput for a broad class of...
Scaling Internet routers using optics (extended version) (2003)
Isaac Keslassy, Shang-Tse Chuang, Kyoungsik Yu, David Miller, Mark Horowitz, Olav Solgaard, ...
Routers built around a single-stage crossbar and a centralized scheduler do not scale, and (in practice) do not provide the throughput guarantees that network operators need to make efficient use of...
Circuit Switching In The Internet (2003)
Pablo Molinero Fernandez, Nick Mckeown, Nicholas Bambos
The motivation for this thesis is our desire to build faster routers and switches to accommodate for the traffic growth in the Internet. For the past few years, Internet traffic has been doubling...
this paper we describe some recent developments in how optics can be used inside Internet routers to scale capacity and reduce power. At Stanford University we are currently designing a 100Tb/s...
Scaling Internet routers using optics (2003)
Isaac Keslassy, Shang-tse Chuang, Kyoungsik Yu, David Miller, Mark Horowitz, Olav Solgaard, ...
Routers built around a single-stage crossbar and a centralized scheduler do not scale, and (in practice) do not provide the throughput guarantees that network operators need to make efficient use of...
Scaling Internet routers using optics (2003)
Isaac Keslassy, Shang-tse Chuang, Kyoungsik Yu, David Miller, Mark Horowitz, Olav Solgaard, ...
Routers built around a single-stage crossbar and a centralized scheduler do not scale, and (in practice) do not provide the throughput guarantees that network operators need to make efficient use of...
Scaling Internet Routers Using Optics (extended version)”, Stanford HPNG (2003)
Isaac Keslassy, Shang-tse Chuang, Kyoungsik Yu, David Miller, Mark Horowitz, Olav Solgaard, ...
This paper is an extended version of [1]. In conjunction with “A load-balanced switch with an arbitrary number of linecards ” [2], it replaces Abstract — Routers built around a single-stage...
The Performance of circuit switching in the Internet (2003)
Pablo Molinero-fernández, Nick Mckeown
Abstract-- This paper studies the performance of an Internet that uses circuit switching instead of, or in addition to, packet switching. On the face of it, this would seem a pointless exercise; the...
Analysis of a statistics counter architecture (2002)
Devavrat Shah, Sundar Iyer, Balaji Prabhakar, Nick Mckeown
Abstract-- Packet switches (e.g., IP routers, ATM switches and Ethernet switches) maintain statistics for a variety of reasons: performance monitoring, network management, security, network tracing,...
Designing packet buffers for router linecards (2002)
Sundar Iyer, Ramana Rao Kompella, Nick Mckeown
Abstract-- All routers contain buffers to hold packets during times of congestion. When designing a high-capacity router (or linecard) it is challenging to design buffers because of the buffer’s...
Maximum size matchings and input queued switches (2002)
Abstract — Simulation results suggest that a maximum size matching (MSM) algorithm will lead to 100 % throughput for uniform Bernoulli i.i.d traffic. Previous analysis on the throughput of MSM...
Designing Packet Buffers for Router Linecards (2002)
Sundar Iyer, Ramana Rao Kompella, Nick Mckeown
All routers contain buffers to hold packets during times of congestion. When designing a high-capacity router (or linecard) it is challenging to design buffers because of the buffer's speed and...
Analysis of a statistics counter architecture (2002)
Devavrat Shah, Sundar Iyer, Balaji Prabhakar, Nick Mckeown
Abstract-- Packet switches (e.g., IP routers, ATM switches and Ethernet switches) maintain statistics for a variety of reasons: performance monitoring, network management, security, network tracing,...
Designing packet buffers for router linecards (2002)
Sundar Iyer, Ramana Rao Kompella, Nick Mckeown
Abstract-- Internet routers and Ethernet switches contain packet buffers to hold packets during times of congestion. Packet buffers are at the heart of every packet switch and router, which have a...
Making Parallel Packet Switches Practical (2001)
Abstract-- A parallel packet switch (PPS) is a switch in which the memories run slower than the line rate. Arriving packets are spread (or load-balanced) packet-by-packet over multiple slower-speed...
Analysis of a Memory Architecture for Fast Packet Buffers (2001)
Sundar Iyer, Ramana Rao Kompella, Nick Mckeown
Abstract-- All packet switches contain packet buffers to hold packets during times of congestion. The capacity of a high performance router is often dictated by the speed of its packet buffers. This...
Monitoring very high speed links (2001)
Gianluca Iannaccone, Christophe Diot, Ian Graham, Nick Mckeown
Abstract--- Our goal is to build passive monitoring equipment for use at 10Gb/s (e.g. 10GE and OC-192) and above. We already have in place an OC-48 passive monitoring system for capturing and storing...
Monitoring very high speed links (2001)
Gianluca Iannaccone, Christophe Diot, Ian Graham, Nick Mckeown
Abstract—Our goal is to build passive monitoring equipment for use at 10Gb/s (e.g. 10GE and OC-192) and above. We already have in place an OC-48 passive monitoring system for capturing and storing...
Algorithms for packet classification (2001)
The process of categorizing packets into “flows ” in an Internet router is called packet classification. All packets belonging to the same flow obey a pre-defined rule and are processed in a...
On the speedup required for a multicast parallel packet switch (2001)
Abstract-- A parallel packet switch (PPS) is a switch in which the memories run slower than the line rate. Arriving packets are load-balanced packet-by-packet over multiple lower speed center stage...
Congestion control and periodic behavior (2001)
Anna C. Gilbert, Youngmi Joo, Nick Mckeown
Abstract-- Feedback based congestion control — used by TCP and other transport protocols — causes the transmission rate of a long-lived flow to oscillate. This paper is about the tendency of...
Analysis of a Packet Switch with Memories Running Slower than the Line Rate (2000)
Sundar Iyer, Nick Mckeown, Balaji Prabhakar
I certify that I have read this dissertation and that in my
Analysis of a Packet Switch with Memories Running Slower than the Line Rate (2000)
Sundar Iyer, Amr Awadallah, Nick Mckeown
the line-rate
Dynamic Algorithms with Worst-case Performance for Packet Classification (2000)
Packet classification involves - given a set of rules - finding the highest priority rule matching an incoming packet. When designing packet classification algorithms, three metrics need to be...
Analysis of a Packet Switch With Memories Running Slower Than the Line-Rate (2000)
Sundar Iyer, Amr Awadallah, Nick Mckeown
Our work is motivated by the desire to build a very high speed packet-switch with extremely high line-rates. In this paper, we consider building a packet-switch from multiple, lower speed...
Matching Output Queueing with a Combined Input Output Queued Switch (1999)
Shang-tse Chuang, Ashish Goel, Nick Mckeown, Balaji Prabhakar
Abstract — The Internet is facing two problems simultaneously: there is a need for a faster switching/routing infrastructure, and a need to introduce guaranteed qualities of service (QoS). Each...
Packet Classification on Multiple Fields (1999)
Routers classify packets to determine which flow they belong to, and to decide what service they should receive. Classification may, in general, be based on an arbitrary number of fields in the...
Packet Classification using Hierarchical Intelligent Cuttings (1999)
Pankaj Gupta And, Pankaj Gupta, Nick Mckeown
Internet routers that operate as firewalls, or provide a variety of service classes, perform different operations on different flows. A flow is defined to be all the packets sharing common header...
Matching output queueing with a combined input output queued switch (1999)
Nick Mckeown, Balaji Prabhakar, Mingyan Zhu
At very high aggregate bandwidths, output queueing is impractical because of insufficient memory bandwidth. This problem is getting worse: memory bandwidth is improving slowly, whereas the demand for...
The Tiny Tera: A Packet Switch Core (1998)
McKeown, Nick, Izzard, Martin, Mekkittikul, Adisak, Ellersick, Bill, Horowitz, Mark
The objective is to design and build a small, high-bandwidth switch.
A quantitative comparison of iterative scheduling algorithms for input-queued switches (1998)
Nick Mckeown, Thomas E. Anderson
In this paper we quantitatively evaluate three iterative algorithms for scheduling cells in a high-bandwidth input-queued ATM switch. In particular, we compare the performance of an algorithm...
Matching Output Queueing with a Combined Input Output Queued Switch (1998)
Shang-Tse Chuang, Ashish Goel, Nick Mckeown, Balaji Prabhakar, Many Commercial Switches
The Internet is facing two problems simultaneously: there is a need for a faster switching/routing infrastructure, and a need to introduce guaranteed qualities of service (QoS). Each problem can be...
Routing Lookups in Hardware at Memory Access Speeds (1998)
Pankaj Gupta, Steven Lin, Nick Mckeown
Increased bandwidth in the Internet puts great demands on network routers; for example, to route minimum sized Gigabit Ethernet packets, an IP router must process about packets per second per port....
Design and Implementation of a Fast Crossbar Scheduler (1998)
Crossbar switches are frequently used as the internal switching fabric of high-performance network switches and routers. However, an intelligent centralized scheduler is needed to configure the...
A Quantitative Comparison of Iterative Scheduling Algorithms for Input-Queued Switches (1998)
Nick Mckeown, Thomas E. Anderson
In this paper we quantitatively evaluate three iterative algorithms for scheduling cells in a high-bandwidth input-queued ATM switch. In particular, we compare the performance of an algorithm...
Matching Output Queueing with a Combined Input Output Queued Switch (1998)
Shang-Tse Chuang, Ashish Goel, Nick Mckeown, Balaji Prabhakar
The Internet is facing two problems simultaneously: there is a need for a faster switching/routing infrastructure, and a need to introduce guaranteed qualities of service (QoS). Each problem can be...
Design and Implementation of a Fast Crossbar Scheduler (1998)
Pankaj Gupta And, Pankaj Gupta, Nick Mckeown
Crossbar switches are frequently used as the internal switching fabric of high-performance network switches and routers. However, an intelligent centralized scheduler is needed to configure the...
AUDIO REPRESENTATIONS FOR DATA COMPRESSION AND COMPRESSED DOMAIN PROCESSING (1998)
Julius Orion Smith, Nick Mckeown, Scott Nathan Levine
that I have read this dissertation and that in my opinion
A Quantitative Comparison of Scheduling Algorithms for Input-Queued Switches (1998)
Nick Mckeown, Thomas E. Anderson
This paper quantitatively evaluates several alternative approaches to the scheduling of cells in a highbandwidth input-queued ATM switch. In particular, we compare the performance of three algorithms...
Scheduling VOQ switches under non-uniform traffic”, CSL (1997)
Adisak Mekkittikul, Nick Mckeown
Abstract — Input queueing is becoming increasingly important for high-bandwidth switches and routers. In previous work, we proved that it is possible to achieve 100 % throughput for input-queued...
Multicast scheduling for input-queued switches (1997)
Balaji Prabhakar, Nick Mckeown, Ritesh Ahuja
This paper presents the design of the scheduler for an M N input-queued multicast switch. It is assumed that: (i) Each input maintains a single queue for arriving multicast cells, and (ii) Only the...
On the Speedup Required for Combined Input and Output Queued Switching (1997)
Balaji Prabhakar, Nick Mckeown
Architectures based on a non-blocking fabric, such as a crosspoint switch, are attractive for use in high-speed LAN switches, IP routers, and ATM switches. When operating at the highest speed, memory...
On the Speedup Required for Combined Input and Output Queued Switching (1997)
Balaji Prabhakar, Nick Mckeown
Architectures based on a non-blocking fabric, such as a crosspoint switch, are attractive for use in high-speed LAN switches, IP routers, and ATM switches. These fabrics, coupled with memory...
The Tiny Tera: A Packet Switch Core (1997)
Nick Mckeown, Martin Izzard, Adisak Mekkittikul, William Ellersick, Mark Horowitz
In this paper, we present the Tiny Tera: a small packet switch with an aggregate bandwidth of 320Gb/s. The Tiny Tera is a CMOS-based input-queued, fixed-size packet switch suitable for a wide range...
A Quantitative Comparison of Scheduling Algorithms for Input-Queued Switches (1997)
Nick Mckeown, Thomas E. Anderson
This paper quantitatively evaluates several alternative approaches to the scheduling of cells in a highbandwidth input-queued ATM switch. In particular, we compare the performance of three algorithms...
Xdistribute: A process distribution system (1996)
Abstract- Powerful, single-user workstations- now common in the workplace- spend most of their time sitting idle. In an attempt to find low-cost computational power researchers have attempted to take...
Achieving 100% Throughput in an Input-Queued Switch (1996)
Nick Mckeown, Adisak Mekkittikul, Venkat Anantharam, Jean Walrand
Abstract — It is well known that head-of-line (HOL) blocking limits the throughput of an input-queued switch with FIFO queues. Under certain conditions, the throughput can be shown to be limited to...
Achieving 100% Throughput in an Input-Queued Switch (1996)
Nick Mckeown, Senior Member, Adisak Mekkittikul, Venkat Anantharam, Jean Walr
Abstract — It is well known that head-of-line blocking limits the throughput of an input-queued switch with first-in–first-out (FIFO) queues. Under certain conditions, the throughput can be shown...
Scheduling Multicast Cells in an Input-Queued Switch (1996)
In this paper we consider policies for scheduling cells in an input-queued multicast switch. It is assumed that each input maintains a single queue for arriving multicast cells and that only the cell...
Tetris Models for Multicast Switches (1996)
Balaji Prabhakar, Nick Mckeown, Jean Mairesse
This paper presents a unified approach to the analysis of schedulers for input-queued multicast ATM switches. It is shown that the general multicast scheduling problem can be mapped onto a variation...
Billing users and pricing for TCP (1995)
Richard J. Edell, Richard J. Edell, Nick Mckeown, Nick Mckeown, Pravin P. Varaiya, Pravin P. Varaiya
© 1995 IEEE. All rights reserved. Do not redistribute this document electronically. This document may be found on the web at:
Designing a Multicast Switch Scheduler (1995)
Balaji Prabhakar, Nick Mckeown
This paper presents the design of the scheduler for an M N input-queued multicast switch. It is assumed that each input maintains a single queue for arriving multicast cells and that only the cell at...
Billing users and pricing for TCP (1995)
Richard J. Edell, Nick Mckeown, Pravin P. Varaiya
Abstract | This paper presents a system for billing users for their TCP tra c. This is achieved by postponing the establishment of connections while the user is contacted, verifying in a secure way...
Billing Users and Pricing for TCP (1995)
Richard J. Edell, Nick Mckeown, Pravin P. Varaiya
This paper presents a system for billing users for their TCP traffic. This is achieved by postponing the establishment of connections while the user is contacted, verifying in a secure way that they...
Designing A Multicast Switch Scheduler (1995)
Balaji Prabhakar, Nick Mckeown
This paper presents the design of the scheduler for an M × N input-queued multicast switch. It is assumed that each input maintains a single queue for arriving multicast cells and that only...
High Performance Switching (1995)
Contents Introduction .................................................................................. 3 Objectives...
Scheduling Cells in an Input-Queued Switch (1993)
Nick Mckeown, Pravin Varaiya, Jean Walrand
We present two algorithms, IRRM and SLIP-IRRM, for scheduling cells in an input-queued cell switch. Both algorithms exhibit asymptotically 100% utilisation under high load; SLIP-IRRM within a single...
Analysis of a Packet Switch With Memories Running Slower Than the Line-Rate
Sundar Iyer Amr, Amr Awadallah, Nick Mckeown
Our work is motivated by the desire to build a very high speed packet-switch with extremely high line-rates. In this paper, we consider building a packet-switch from multiple, lower speed...
Multicast Scheduling for Input-Queued Switches
Balaji Prabhakar, Nick Mckeown, Ritesh Ahuja
The demand for network bandwidth is growing much faster than the increase in commercially available memory bandwidth, causing a growing interest in input-queued switches. Furthermore, an increase in...
Scheduling Multicast Cells In An Input-Queued Switch
Nick Mckeown, Balaji Prabhakar
In this paper we consider policies for scheduling cells in an input-queued multicast switch. It is assumed that each input maintains a single queue for arriving multicast cells and that only the cell...