File Download
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1109/INFCOM.2002.1019300
- Scopus: eid_2-s2.0-0036346352
- Find via
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: Efficient hardware architecture for fast IP address lookup
Title | Efficient hardware architecture for fast IP address lookup |
---|---|
Authors | |
Keywords | Communications Computer applications |
Issue Date | 2002 |
Publisher | IEEE Computer Society. The Journal's web site is located at http://www.ieee-infocom.org/ |
Citation | Proceedings - IEEE INFOCOM, 2002, v. 2, p. 555-561 How to Cite? |
Abstract | A multigigabit IP router may receive several millions packets per second from each input link. For each packet, the router needs to find the longest matching prefix in the forwarding table in order to determine the packet's next-hop. In this paper, we present an efficient hardware solution for the IP address lookup problem. We model the address lookup problem as a searching problem on a binary-trie. The binary-trie is partitioned into four levels of fixed size 255-node subtrees. We employ a hierarchical indexing structure to facilitate direct access to subtrees in a given level. It is estimated that a forwarding table with 40K prefixes will consume 2.5Mbytes of memory. The searching is implemented using a hardware pipeline with a minimum cycle of 12.5ns if the memory modules are implemented using SRAM. A distinguishing feature of our design is that forwarding table entries are not replicated in the data structure. Hence, table updates can be done in constant time with only a few memory accesses. |
Persistent Identifier | http://hdl.handle.net/10722/48458 |
ISSN | 2023 SCImago Journal Rankings: 2.865 |
References |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Pao, D | en_HK |
dc.contributor.author | Liu, C | en_HK |
dc.contributor.author | Wu, A | en_HK |
dc.contributor.author | Yeung, L | en_HK |
dc.contributor.author | Chan, KS | en_HK |
dc.date.accessioned | 2008-05-22T04:13:39Z | - |
dc.date.available | 2008-05-22T04:13:39Z | - |
dc.date.issued | 2002 | en_HK |
dc.identifier.citation | Proceedings - IEEE INFOCOM, 2002, v. 2, p. 555-561 | en_HK |
dc.identifier.issn | 0743-166X | en_HK |
dc.identifier.uri | http://hdl.handle.net/10722/48458 | - |
dc.description.abstract | A multigigabit IP router may receive several millions packets per second from each input link. For each packet, the router needs to find the longest matching prefix in the forwarding table in order to determine the packet's next-hop. In this paper, we present an efficient hardware solution for the IP address lookup problem. We model the address lookup problem as a searching problem on a binary-trie. The binary-trie is partitioned into four levels of fixed size 255-node subtrees. We employ a hierarchical indexing structure to facilitate direct access to subtrees in a given level. It is estimated that a forwarding table with 40K prefixes will consume 2.5Mbytes of memory. The searching is implemented using a hardware pipeline with a minimum cycle of 12.5ns if the memory modules are implemented using SRAM. A distinguishing feature of our design is that forwarding table entries are not replicated in the data structure. Hence, table updates can be done in constant time with only a few memory accesses. | en_HK |
dc.format.extent | 217100 bytes | - |
dc.format.extent | 8014 bytes | - |
dc.format.mimetype | application/pdf | - |
dc.format.mimetype | text/plain | - |
dc.language | eng | en_HK |
dc.publisher | IEEE Computer Society. The Journal's web site is located at http://www.ieee-infocom.org/ | en_HK |
dc.relation.ispartof | Proceedings - IEEE INFOCOM | en_HK |
dc.rights | ©2002 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE. | - |
dc.subject | Communications | en_HK |
dc.subject | Computer applications | en_HK |
dc.title | Efficient hardware architecture for fast IP address lookup | en_HK |
dc.type | Conference_Paper | en_HK |
dc.identifier.openurl | http://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0743-166X&volume=2&spage=555&epage=561&date=2002&atitle=Efficient+hardware+architecture+for+fast+IP+address+lookup | en_HK |
dc.identifier.email | Yeung, L:kyeung@eee.hku.hk | en_HK |
dc.identifier.authority | Yeung, L=rp00204 | en_HK |
dc.description.nature | published_or_final_version | en_HK |
dc.identifier.doi | 10.1109/INFCOM.2002.1019300 | en_HK |
dc.identifier.scopus | eid_2-s2.0-0036346352 | en_HK |
dc.identifier.hkuros | 72431 | - |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-0036346352&selection=ref&src=s&origin=recordpage | en_HK |
dc.identifier.volume | 2 | en_HK |
dc.identifier.spage | 555 | en_HK |
dc.identifier.epage | 561 | en_HK |
dc.publisher.place | United States | en_HK |
dc.identifier.scopusauthorid | Pao, D=7003659464 | en_HK |
dc.identifier.scopusauthorid | Liu, C=7409790291 | en_HK |
dc.identifier.scopusauthorid | Wu, A=7402998955 | en_HK |
dc.identifier.scopusauthorid | Yeung, L=7202424908 | en_HK |
dc.identifier.scopusauthorid | Chan, KS=8338485100 | en_HK |
dc.customcontrol.immutable | sml 151016 | - |
dc.identifier.issnl | 0743-166X | - |