Idioma:

Efficient Construction of Pipelined Multibit-Trie Router-Tables

Kun Suk Kim ; Sahni, S.

IEEE transactions on computers, 2007-01, Vol.56 (1), p.32-43 [Periódico revisado por pares]

Texto completo disponível

Citações Citado por

Título:
Efficient Construction of Pipelined Multibit-Trie Router-Tables
Autor: Kun Suk Kim ; Sahni, S.
Assuntos: Algorithms ; Construction ; controlled prefix expansion ; dynamic programming ; Heuristic ; longest matching-prefix ; multibit trie ; Packet routing ; Partitioning ; pipelined router-table ; Trees
É parte de: IEEE transactions on computers, 2007-01, Vol.56 (1), p.32-43
Notas: ObjectType-Article-2
SourceType-Scholarly Journals-1
ObjectType-Feature-1
content type line 23
Descrição: Efficient algorithms to construct multibit tries suitable for pipelined router-table applications are developed. We first enhance the 1-phase algorithm of Basu and Narlikar, obtaining a 1-phase algorithm that is 2.5 to 3 times as fast. Next, we develop 2-phase algorithms that not only guarantee to minimize the maximum per-stage memory but also guarantee to use the least total memory subject to the former constraint. Our 2-phase algorithms not only generate better pipelined trees than those generated by the 1-phase algorithm, but they also take much less time. A node pull-up scheme that guarantees no increase in maximum per-stage memory as well as a partitioning heuristic that generates pipelined multibit tries requiring less maximum per-stage memory than required by the tries obtained using the 1-phase and 2-phase algorithms are also proposed
Editor: New York: IEEE
Idioma: Inglês

Voltar para lista de resultados

Anterior Resultado 7 Avançar Ir para próxima página