Router Design for Named Data Networking

Abstract

The Internet is one of the greatest inventions of the past century. The success of the Internet comes mainly from its networking architectures like TCP/IP. The contemporary internet architecture is designed to support point-to-point conversation between two entities. Over the past few decades, the IP has successfully facilitated ubiquitous connectivity. However, with the development of the Internet, services like e-commerce, social networking, and digital media have dominated the network usage. Today, people value what contents that can be provided by the Internet. The global demand for data is nearing 30 exabytes (30 billion gigabytes) per month in 2011. Also, it was estimated that about 500 exabytes of new on-line contents had been created in 2008 alone. The host-based network architecture of today’s Internet is overwhelmingly used for content distribution.

Named Data Networking (NDN) is a newly proposed network architecture to address the mismatch between the content-centric communication needs and the host-based network architecture. Under the NDN architecture, an end user can focus on the contents he or she needs, rather than find out where the contents are located. NDN also comes with other potential benefits such as in-network caching to reduce congestion and improve data retrieval speed, stateful forwarding that enables loop detection, and native support for multicast.

Data retrieval in NDN is initiated by the receivers, through the exchange of two types of packets: interest packet and data packet. Both types of packet carry a name in the packet headers, which identifies a piece of data chunk. The NDN routers carry out the packet processing based on the names. The packet processing involves three major components: forwarding information base (FIB), pending interest table (PIT) and cache store (CS). The design of the three components, as well as the router system, is an important research topic for the NDN deployment.

The packet processing in contemporary network architecture has been extensively studied. However, the packet processing in NDN is expected to be more complicated. The major issues in NDN packet processing include the more complex name-based matching, much larger table sizes, and per-packet update to the lookup table. There are substantive research studies on the NDN packet processing and the prototype design of the NDN router. However, most of them are software-based with relatively low throughput. In this thesis, we present the designs of hardware accelerators to speed up packet processing in NDN routers. Two design approaches are used for mid-range and high-end NDN routers, respectively.

The design of the mid-range NDN router is based on centralized packet processing. We present a hardware design of PIT/CS for the mid-range NDN router. The data structure of the PIT is optimized for high-speed lookup and per-packet update. A 2-level memory architecture of CS is also proposed. The PIT and CS lookups are integrated into one table lookup in order to reduce the hardware implementation cost and streamline the packet processing procedure. A novel data structure called name ID table (nidT) is also incorporated to reduce the FIB workload so that the existing software-based FIB design can meet the throughput requirement. The overall packet processing rate of the router can be up to 60 MPPS (480 Gbps).

We adopt parallel and distributed processing techniques in the design of the high-end NDN router. We also present a dedicated hardware design of FIB lookup engine for the router. The lookup speed of one FIB lookup engine can be up to 98.6 million searches per second (MSPS). With multiple FIB lookup engines equipped, the router can achieve multi-Tbps throughput.

Date of Award	28 Feb 2019
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Chi Wai Derek PAO (Supervisor)