NDLI: Data Structures and Algorithms for Packet Forwarding and Classification

Content Provider	IEEE Xplore Digital Library
Author	Sahni, S.
Copyright Year	2009
Abstract	Efficient packet forwarding is central to moving traffic smoothly through the Internet. For example, at a line rate of 10Gbps and a minimum packet size of 40 bytes, an Internet router must process more than 30 million packets per second. At 80Gbps, more than240 million packets must be processed per second. At its simplest, packet processing involves extracting the packet’s destination address, doing a look up in a router table of size up to about 1 million, and sending the packet to its next hop as determined by the table lookup. Besides providing a very high look up rate, an Internet router must be able to update its lookup table at rates that are of the order of 50,000 updates per second (peak). The extreme performance demand on an Internet router may be somewhat reduced by maintaining an additional flow table, filtering out packets that correspond to a packet in the flow table, and doing a router table lookup only for those packets that do not correspond to an existing flow [3]. Power consumption is another very important consideration in the design of an Internet router. For example, Sekiguchi [6]projects that with a 40% annual growth in Internet traffic, the energy consumed by routers in Japan in 2022 will exceed the 2005gross power generation of Japan. Extensive research has been conducted to develop good data structures to meet the lookup and update requirements of a router as well as to reduce power consumption. This talk reviews some of this research as well as current trends in router design. Sample data structures include multibit one- and two-dimensional tries and hybrid shape shifting tries. Hardware assisted solutions such as Ternary Content Addressable Memories also are reviewed. For more details, see the listed references.
Starting Page	3
Ending Page	3
File Size	189143
Page Count	1
File Format	PDF
ISBN	9781424454037
e-ISBN	9781424454044
DOI	10.1109/I-SPAN.2009.122
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2009-12-14
Publisher Place	Taiwan
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Data structures Internet Table lookup Energy consumption Information filtering Information filters Power generation Shape Hardware Associative memory
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Efficient TCAM Encoding Schemes for Packet Classification Using Gray Code

Technique to eliminate sorting in IP packet forwarding devices

High-performance TCAM-based IP lookup engines

A parallel IP-address forwarding approach based on partitioned lookup table techniques

Segregating the encompassing prefixes to enhance the performance of packet forwarding engines

Exact Forwarding Table Partitioning for Efficient TCAM Power Savings

TCAM-Based Forwarding Engine with Minimum Independent Prefix Set (MIPS) for Fast Updating

Complete Redundancy Removal for Packet Classifiers in TCAMs

Packet classification using coarse-grained tuple spaces

Data Structures and Algorithms for Packet Forwarding and Classification

Similar Documents

Efficient TCAM Encoding Schemes for Packet Classification Using Gray Code

Technique to eliminate sorting in IP packet forwarding devices

High-performance TCAM-based IP lookup engines

A parallel IP-address forwarding approach based on partitioned lookup table techniques

Segregating the encompassing prefixes to enhance the performance of packet forwarding engines

Exact Forwarding Table Partitioning for Efficient TCAM Power Savings

TCAM-Based Forwarding Engine with Minimum Independent Prefix Set (MIPS) for Fast Updating

Complete Redundancy Removal for Packet Classifiers in TCAMs

Packet classification using coarse-grained tuple spaces

Data Structures and Algorithms for Packet Forwarding and Classification