Panel Description:

The panel session will explore the topics discussed at the Next Generation Networks workshop, specifically focusing on research directions for future network architectures such as GENI. The panel will discuss trends in these research areas from 3 major perspectives: fundamental significance of the research, practical/industrial impact and current and future funding opportunities. The panel will consist of researchers from academia, industry and government organizations.

Panelists:

Constantine Dovrolis - Georgia Tech
Chuck Kalmanek - AT&T Labs
Narayan Mandayam - Rutgers WINLAB
Allison Mankin - NSF
Gee Rittenhouse - Bell Labs
Jennifer Rexford - Princeton University

Title: Network algorithms: routing and design

Optical dense wavelength division multiplexing (DWDM) technology enables very high capacity backbone networks but at the cost of extremely expensive equipment. These high costs and reliability requirements make it critical to optimize the network design process. However, the associated design problems involve many difficult algorithmic challenges. In this tutorial we provide a high level overview of the design desiderata and then focus on two clean optimization problems: buy-at-bulk network design (with protection) and wavelength provisioning with continuity. The former concerns choosing disjoint routes for each demand so as to take advantage of the economies of scale in deploying optical components. The latter concerns assigning wavelengths so that traffic demands sharing a common fiber are carried on distinct wavelengths. We discuss the complexity of both problems, present approximation algorithms and also discuss practical issues arising from design tools that are being developed and used at Bell Labs.

Title: Overlay Networks: Indirection and Virtualization

Overlay networks have emerged as a promising platform to provide customizable and reliable services at the application layer to support new services, such as multicast, content delivery, and resilient connectivity.

The first part of the talk will focus on infrastructure-based overlay networks, where pre-selected nodes (located in one or multiple network domains) are connected to one another through application-layer routing. A basic service provided is 'indirection', which allows individual flows to optimize route selection based on specific requirements, e.g., end-to-end delay, loss rate, or throughput. When different overlays are simultaneously and independently conducting routing control, they may unintentionally interfere with each other, leading to traffic oscillations. Similarly, problematic interactions can occur between IP- and overlay-networks. For example, traffic matrices become more dynamic and ambiguous, making them harder to estimate, and load-balancing policies at IP-layer can be undermined. We will discuss existing works that apply game theory to study such interactions both in equilibrium and during the transient period.

The second part of the talk will provide an overview of challenges, open problems, and applications related to overlay networks, including both infrastructure-based overlays and peer-to-peer systems. Topics include: resource virtualization techniques, content distribution, peer-assisted streaming, collaborative overlays, and reputation systems.

Title: Optical physical layer issues in wavelength-division multiplexed networks

Fiber optic networks have evolved from a simple point-to-point architecture to rings with add-drop. The evolution will likely continue to a full mesh architecture. Many interesting problems emerge in the physical layer design of optical mesh nodes. We will first give a background of the physical devices used to perform optical wavelength switching. We will then discuss the architecture that is being adopted today for mesh nodes. Finally, we will show new concepts for creating mesh nodes that have significant advantages over today's mesh nodes.

Title: Data plane algorithms in routers: from prefix lookup to deep packet inspection

One of the main challenges for the builders of modern IP routers and switches is to perform data plane functions at high speeds. The need for more and more control over the traffic means that besides traditional operations such as routing table lookup, these devices must perform more and more complex operations such as packet classification and matching signatures against the traffic. While the performance of the underlying hardware technologies is crucial for achieving high speeds, the algorithms used to perform these functions also have a tremendous effect on performance and cost.

In this talk I will present an overview of the best current algorithmic solutions for three important data plane operations: finding the longest matching prefix (used for routing table lookup), packet classification on multiple fields (used for security and QoS), and regular expression matching (used in intrusion prevention). While the talk will focus on algorithmic aspects, I will also present some solutions that use custom hardware (no background in hardware design is required).

Title: Internet Routing Availability

Internet applications are increasingly demanding high availability; unfortunately, today's network infrastructure is subject to many aberrations that can compromise availability, from misconfigurations to slowly converging routing protocols. The first part of the talk describes how various aspects of today's Internet routing infrastructure---from misconfigurations to slowly converging routing protocols to poor support for multihoming---degrade availability. The second half of the talk will discuss various techniques, mechanisms, and new routing protocols that aim to improve network availability. We will focus specifically on recent multipath routing proposals from both the IETF (e.g., IPv6 multihoming extensions, multi-router configurations) as well as proposals from the broader research community (e.g., path deflections, path splicing).

Title: Network coding: An algorithmic approach

The tutorial will provide basic and in-depth knowledge of the rapidly evolving area of network coding. Network coding generalizes network operation beyond the traditional forwarding or replication of information, allowing network nodes to perform coding operations on information from different streams. We will cover the resent results and potential benefits of network coding that have been demonstrated in various aspects of networking. We will focus on the algorithmic aspects of finding efficient network codes, covering both deterministic and randomized techniques. We will also discuss open problems and directions for future research.

Title: Packet level algorithms: accounting and tracking

Many flow monitoring and measuring tasks are now being done using hash-based data structures, including Bloom filters and their many variations. In this talk, we discuss a three-pronged agenda for this line of research:

   1) Low: Mapping algorithms data structures to efficient hardware implementations.
   2) Medium: Developing new algorithms and data structures for 
              monitoring and measuring tasks.
   3) High: Designing an distributed infrastructure for hash-based monitoring and measuring schemes.

We provide in-depth examples from our recent work of progress in this research agenda, including our work on approximate concurrent state machines, novel constructions of Bloom filters and counting Bloom filters, and the benefits of allowing moves (as with cuckoo hashing) in multiple-choice hash tables. We also speculate wildly about future directions to pursue.

Title: Next Generation Cellular Networks: Novel Features and Algorithms

Motivated by the dramatically growing demand for high data rate wireless services, the 3GPP2 standards forum has standardized an orthogonal frequency division multiple access (OFDMA) based air-interface for next generation cellular networks called ultra mobile broadband (UMB). Several novel features built upon OFDMA such as dynamic fractional frequency reuse (FFR), pre-coded code division multiple access, Supercast for broadcast services, and advanced multiple antenna (MIMO) techniques have been included in the standards. In this talk, we will first provide an overview of some of the novel features of the UMB system and related algorithms. We will then describe the dynamic fractional frequency reuse feature in more detail. We demonstrate, both analytically on a simple one-dimensional system and through extensive simulations, that an algorithm based on continuous ``selfish'' optimization of resource allocation by each sector can lead the system to ``self-organize'' into efficient frequency reuse patterns.

Title: The Border Gateway Protocol (BGP): Convergence Issues and a New Fractional Model

The Border Gateway Protocol (BGP) is the interdomain routing protocol used by routers to exchange routing information in the Internet. While intradomain protocols such as RIP can be viewed as distributed algorithms for computing shortest paths, the question arises as to whether there is such a graph theoretic problem that BGP is trying to solve. We will describe the stable paths problem (SPP) and show that this is the problem that BGP is attempting to solve. Most of the rest of the talk will be in terms of SPP to allow us to mask all the complex details of how BGP operates.

We will discuss a number of decision questions concerning BGP convergence and show that they are NP-hard. Then we'll consider modifications to the protocol that guarantee convergence. Rather than changing the protocol, another approach is to find configuration constraints such that a network satisfying these constraints will guarantee BGP convergence.

Finally, we define a fractional version of SPP and show that this problem always has a stable solution. This leads to open problems such as how to design a protocol (i.e., a distributed algorithm) to achieve such a fractional stable solution.

Title: Randomized Load Balancing and Network Architectures for Dynamic Data Trffic

We consider the problem of building cost-effective networks which are robust to dynamic changes in demand patterns. We compare several architectures based on demand-oblivious routing strategies. Traditional approaches include single-hop architectures based on a (static or dynamic) circuit-switched core infrastructure, and multi-hop (packet-switched) architectures based on point-to-point circuits in the core. We first discuss the benefits and drawbacks of conventional shortest-path and VPN tree routing strategies. We then focus on several aspects and extensions of Valiant's randomized load balancing (RLB), which represents a highly attractive networking approach if network traffic is highly dynamic (e.g., hose-constrained). We give empirical analyses for the cost in terms of transport and switching equipment as well as for the expected queuing delays for the discussed architectures, based on three representative carrier networks.