File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Efficient hardware architecture for fast IP address lookup

TitleEfficient hardware architecture for fast IP address lookup
Authors
KeywordsCommunications
Computer applications
Issue Date2002
PublisherIEEE 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?
AbstractA 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 Identifierhttp://hdl.handle.net/10722/48458
ISSN
References

 

DC FieldValueLanguage
dc.contributor.authorPao, Den_HK
dc.contributor.authorLiu, Cen_HK
dc.contributor.authorWu, Aen_HK
dc.contributor.authorYeung, Len_HK
dc.contributor.authorChan, KSen_HK
dc.date.accessioned2008-05-22T04:13:39Z-
dc.date.available2008-05-22T04:13:39Z-
dc.date.issued2002en_HK
dc.identifier.citationProceedings - IEEE INFOCOM, 2002, v. 2, p. 555-561en_HK
dc.identifier.issn0743-166Xen_HK
dc.identifier.urihttp://hdl.handle.net/10722/48458-
dc.description.abstractA 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.extent217100 bytes-
dc.format.extent8014 bytes-
dc.format.mimetypeapplication/pdf-
dc.format.mimetypetext/plain-
dc.languageengen_HK
dc.publisherIEEE Computer Society. The Journal's web site is located at http://www.ieee-infocom.org/en_HK
dc.relation.ispartofProceedings - IEEE INFOCOMen_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.en_HK
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.subjectCommunicationsen_HK
dc.subjectComputer applicationsen_HK
dc.titleEfficient hardware architecture for fast IP address lookupen_HK
dc.typeConference_Paperen_HK
dc.identifier.openurlhttp://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+lookupen_HK
dc.identifier.emailYeung, L:kyeung@eee.hku.hken_HK
dc.identifier.authorityYeung, L=rp00204en_HK
dc.description.naturepublished_or_final_versionen_HK
dc.identifier.doi10.1109/INFCOM.2002.1019300en_HK
dc.identifier.scopuseid_2-s2.0-0036346352en_HK
dc.identifier.hkuros72431-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-0036346352&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume2en_HK
dc.identifier.spage555en_HK
dc.identifier.epage561en_HK
dc.publisher.placeUnited Statesen_HK
dc.identifier.scopusauthoridPao, D=7003659464en_HK
dc.identifier.scopusauthoridLiu, C=7409790291en_HK
dc.identifier.scopusauthoridWu, A=7402998955en_HK
dc.identifier.scopusauthoridYeung, L=7202424908en_HK
dc.identifier.scopusauthoridChan, KS=8338485100en_HK
dc.customcontrol.immutablesml 151016-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats