File Download

There are no files associated with this item.

  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
Issue Date2003
PublisherThe Institution of Engineering and Technology. The Journal's web site is located at http://www.ietdl.org/IP-CDT
Citation
Iee Proceedings: Computers And Digital Techniques, 2003, v. 150 n. 1, p. 43-52 How to Cite?
AbstractA multi-gigabit internet protocol (IP) router may receive several million 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. An efficient hardware solution for the IP address lookup problem is presented. The problem is modelled as a searching problem on a binary-trie. The binary-trie is partitioned into fixed size non-overlapping subtrees. Each subtree is represented using a bit-vector and can be searched in parallel for the best matching prefix in a few nanoseconds. The address lookup is implemented using a hardware pipeline with a throughput of one lookup per memory access. A distinguishing feature of the 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. The approach can be extended to IPv6. By applying path compression, the amount of memory required is upper bounded by O(N) where N is the number of prefixes in the routing table.
Persistent Identifierhttp://hdl.handle.net/10722/158353
ISSN
2006 Impact Factor: 0.314
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorPao, Den_US
dc.contributor.authorLiu, Cen_US
dc.contributor.authorWu, Aen_US
dc.contributor.authorYeung, Len_US
dc.contributor.authorChan, KSen_US
dc.date.accessioned2012-08-08T08:59:12Z-
dc.date.available2012-08-08T08:59:12Z-
dc.date.issued2003en_US
dc.identifier.citationIee Proceedings: Computers And Digital Techniques, 2003, v. 150 n. 1, p. 43-52en_US
dc.identifier.issn1350-2387en_US
dc.identifier.urihttp://hdl.handle.net/10722/158353-
dc.description.abstractA multi-gigabit internet protocol (IP) router may receive several million 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. An efficient hardware solution for the IP address lookup problem is presented. The problem is modelled as a searching problem on a binary-trie. The binary-trie is partitioned into fixed size non-overlapping subtrees. Each subtree is represented using a bit-vector and can be searched in parallel for the best matching prefix in a few nanoseconds. The address lookup is implemented using a hardware pipeline with a throughput of one lookup per memory access. A distinguishing feature of the 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. The approach can be extended to IPv6. By applying path compression, the amount of memory required is upper bounded by O(N) where N is the number of prefixes in the routing table.en_US
dc.languageengen_US
dc.publisherThe Institution of Engineering and Technology. The Journal's web site is located at http://www.ietdl.org/IP-CDTen_US
dc.relation.ispartofIEE Proceedings: Computers and Digital Techniquesen_US
dc.titleEfficient hardware architecture for fast IP address lookupen_US
dc.typeConference_Paperen_US
dc.identifier.emailYeung, L:kyeung@eee.hku.hken_US
dc.identifier.authorityYeung, L=rp00204en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1049/ip-cdt:20030082en_US
dc.identifier.scopuseid_2-s2.0-0037285244en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-0037285244&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume150en_US
dc.identifier.issue1en_US
dc.identifier.spage43en_US
dc.identifier.epage52en_US
dc.identifier.isiWOS:000181339100008-
dc.publisher.placeUnited Kingdomen_US
dc.identifier.scopusauthoridPao, D=7003659464en_US
dc.identifier.scopusauthoridLiu, C=7409790291en_US
dc.identifier.scopusauthoridWu, A=7402998955en_US
dc.identifier.scopusauthoridYeung, L=7202424908en_US
dc.identifier.scopusauthoridChan, KS=37860993000en_US

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats