Scalable IPv6 lookup/update design for high-throughput routers

Chung-Ho Chen, Chao Hsien Hsu, Chen Chieh Wang

Research output: Contribution to journalArticle

Abstract

Achieving scalable performance in the IPv6 address lookup and update poses a challenge to the design of existing routers. To concurrently match address prefixes with different route entries, we propose a parallel memory lookup scheme which uses three-level tables to cover various lengths of prefix distributions for the long IP address. The scheme employs a parallel CRC address compression hardware to reduce the lookup table sizes. The multi-cycle implementation of the design has achieved an average of 1.6 memory accesses per lookup request. The pipeline version features a five-stage pipeline design with a mechanism to reduce pipeline stalls due to updates. Performance simulation reveals that the number of address queue entries significantly influences the lookup throughput when frequent table updates occur. The proposed single pipeline module with an eight-entry queue stage has achieved a maximum rate of 100 × 106 lookups per second. With the four-pipeline configuration, the throughput is increased by a factor of 2.5 for sparse updates and up to 2.3 when the update rate increases to 20 percents of the lookup's. This paper has demonstrated a viable IPv6 lookup design that is scalable for high-throughput routers.

Original languageEnglish
Pages (from-to)261-269
Number of pages9
JournalJournal of Internet Technology
Volume8
Issue number3
Publication statusPublished - 2007 Jul

Fingerprint

Routers
Pipelines
Throughput
Data storage equipment
Table lookup
Hardware

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Networks and Communications

Cite this

Chen, Chung-Ho ; Hsu, Chao Hsien ; Wang, Chen Chieh. / Scalable IPv6 lookup/update design for high-throughput routers. In: Journal of Internet Technology. 2007 ; Vol. 8, No. 3. pp. 261-269.
@article{1639aaf763a04731ad661f165a78a684,
title = "Scalable IPv6 lookup/update design for high-throughput routers",
abstract = "Achieving scalable performance in the IPv6 address lookup and update poses a challenge to the design of existing routers. To concurrently match address prefixes with different route entries, we propose a parallel memory lookup scheme which uses three-level tables to cover various lengths of prefix distributions for the long IP address. The scheme employs a parallel CRC address compression hardware to reduce the lookup table sizes. The multi-cycle implementation of the design has achieved an average of 1.6 memory accesses per lookup request. The pipeline version features a five-stage pipeline design with a mechanism to reduce pipeline stalls due to updates. Performance simulation reveals that the number of address queue entries significantly influences the lookup throughput when frequent table updates occur. The proposed single pipeline module with an eight-entry queue stage has achieved a maximum rate of 100 × 106 lookups per second. With the four-pipeline configuration, the throughput is increased by a factor of 2.5 for sparse updates and up to 2.3 when the update rate increases to 20 percents of the lookup's. This paper has demonstrated a viable IPv6 lookup design that is scalable for high-throughput routers.",
author = "Chung-Ho Chen and Hsu, {Chao Hsien} and Wang, {Chen Chieh}",
year = "2007",
month = "7",
language = "English",
volume = "8",
pages = "261--269",
journal = "Journal of Internet Technology",
issn = "1607-9264",
publisher = "Taiwan Academic Network Management Committee",
number = "3",

}

Scalable IPv6 lookup/update design for high-throughput routers. / Chen, Chung-Ho; Hsu, Chao Hsien; Wang, Chen Chieh.

In: Journal of Internet Technology, Vol. 8, No. 3, 07.2007, p. 261-269.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Scalable IPv6 lookup/update design for high-throughput routers

AU - Chen, Chung-Ho

AU - Hsu, Chao Hsien

AU - Wang, Chen Chieh

PY - 2007/7

Y1 - 2007/7

N2 - Achieving scalable performance in the IPv6 address lookup and update poses a challenge to the design of existing routers. To concurrently match address prefixes with different route entries, we propose a parallel memory lookup scheme which uses three-level tables to cover various lengths of prefix distributions for the long IP address. The scheme employs a parallel CRC address compression hardware to reduce the lookup table sizes. The multi-cycle implementation of the design has achieved an average of 1.6 memory accesses per lookup request. The pipeline version features a five-stage pipeline design with a mechanism to reduce pipeline stalls due to updates. Performance simulation reveals that the number of address queue entries significantly influences the lookup throughput when frequent table updates occur. The proposed single pipeline module with an eight-entry queue stage has achieved a maximum rate of 100 × 106 lookups per second. With the four-pipeline configuration, the throughput is increased by a factor of 2.5 for sparse updates and up to 2.3 when the update rate increases to 20 percents of the lookup's. This paper has demonstrated a viable IPv6 lookup design that is scalable for high-throughput routers.

AB - Achieving scalable performance in the IPv6 address lookup and update poses a challenge to the design of existing routers. To concurrently match address prefixes with different route entries, we propose a parallel memory lookup scheme which uses three-level tables to cover various lengths of prefix distributions for the long IP address. The scheme employs a parallel CRC address compression hardware to reduce the lookup table sizes. The multi-cycle implementation of the design has achieved an average of 1.6 memory accesses per lookup request. The pipeline version features a five-stage pipeline design with a mechanism to reduce pipeline stalls due to updates. Performance simulation reveals that the number of address queue entries significantly influences the lookup throughput when frequent table updates occur. The proposed single pipeline module with an eight-entry queue stage has achieved a maximum rate of 100 × 106 lookups per second. With the four-pipeline configuration, the throughput is increased by a factor of 2.5 for sparse updates and up to 2.3 when the update rate increases to 20 percents of the lookup's. This paper has demonstrated a viable IPv6 lookup design that is scalable for high-throughput routers.

UR - http://www.scopus.com/inward/record.url?scp=34547844297&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=34547844297&partnerID=8YFLogxK

M3 - Article

VL - 8

SP - 261

EP - 269

JO - Journal of Internet Technology

JF - Journal of Internet Technology

SN - 1607-9264

IS - 3

ER -