Tutorials

Using the Open Network Laboratory
Jonathan Turner, Washington University in St. Louis

The Open Network Laboratory is a resource designed to enable experimental evaluation of advanced networking concepts in a realistic operating environment. The laboratory is built around a set of opensource, extensible, high performance routers, which can be accessed by remote users through a Remote Laboratory Interface (RLI). The RLI allows users to configure the testbed network, run applications and monitor those running applications using built-in data gathering mechanisms. Support for data visualization and real-time remote display is provided. The RLI also allows users to extend, modify or replace the software running in the routers' embedded processors and to similarly extend, modify or replace the routers' packet processing hardware, which is implemented largely using Field Programmable Gate Arrays. The routers included in the testbed are architecturally similar to high performance commercial routers, enabling researchers to evaluate their ideas in a more realistic context than can be provided by PC-based routers. The Open Network Laboratory is designed to provide a setting in which systems researchers can evaluate and refine their ideas and then demonstrate them to those interested in moving their technology into new products andservices.

This tutorial will teach users how to use the ONL. It will include detailed presentations on the system
architecture and principles of operation, as well as live demonstrations. We also plan to give participants an opportunity for hands-on experience with setting up and running experiments themselves.

Line Rate Packet Classification and Scheduling (slides)
Michael Kounavis, Intel
Alok Kumar, Intel
Raj Yavatkar, Intel
Harrick Vin, Univ. of Texas at Austin

In this tutorial we will present a collection of algorithms and techniques for building high performance packet classification and scheduling systems. Packet classification is the process of identifying flows from among streams of packets that arrive at routers. Packet scheduling is the process of selecting which packet to forward next from among competing flows. Packet classification and scheduling are still important and open networking problems because these steps need to take place as quickly as possible in modern router systems. To ensure that routers can process packets at link speeds ranging from 1 Gbps (e.g., Gigabit Ethernet link speeds at the network edge) to 10-40 Gbps (e.g., OC-192 or OC-768 link speeds in the network core), the number of memory accesses performed by classifiers and schedulers must be minimized. Further, the data structures maintained by these algorithms must fit within the small amount of fast memory available in routers.

The first part of the tutorial will cover state of the art packet classification algorithms and systems. Emphasis will be placed on two new concepts to the design of packet classifiers. First, we will present Most Specific Filter Matching (MSFM), a refined version of the well known Cross Producting algorithm that solves the memory explosion problem associated with the earlier scheme. Second, we will discuss observations that have been made on real world databases, where many different sets of source-destination IP prefix pairs are associated with identical sets of transport level fields. We will discuss how transport level sharing can be exploited for reducing a classifier’s memory requirement and for hardware acceleration.

The second part of the tutorial will cover the efficient implementation of packet scheduling algorithms. This tutorial will cover a range of state-of-the-art techniques for tagging and sorting packets in schedulers. Emphasis will be given to a novel data structure and algorithm for sorting packets that reduces the latency of making the scheduling decisions to a single memory access and a small constant number of computation steps, independent of the number of flows in a scheduler. This algorithm is based on the observation that packet tags are typically within a range called the scheduling horizon. We will discuss how the scheduling horizon can be represented as a trie data structure and how state can be put into the nodes of the trie so as to allow the leaf nodes to be connected into a doubly connected linked list. As a result of this, the next packet for transmission into the network can be obtained in a single memory access time. Finally, we will discuss how a hierarchical packet scheduler can be efficiently implemented from single-level schedulers.