skip to main content
Idioma:
Primo Search
Clear Search Box
Search in: Busca Geral
Busca Avançada
Busca por Índices

Enhanced interval trees for dynamic IP router-tables

Haibin Lu ; Sahni, S.

IEEE transactions on computers, 2004-12, Vol.53 (12), p.1615-1628 [Periódico revisado por pares]

New York: IEEE

Texto completo disponível

Citações Citado por
  • Título:
    Enhanced interval trees for dynamic IP router-tables
  • Autor: Haibin Lu ; Sahni, S.
  • Assuntos: Algorithms ; Cache memories ; Communication system routing ; Complexity theory ; Data structures ; dynamic rule-tables ; highest-priority matching ; Index Terms- Interval trees ; longest-prefix matching ; packet classification ; packet routing ; Packet switching ; router tables ; rule insertion and deletion ; Studies
  • É parte de: IEEE transactions on computers, 2004-12, Vol.53 (12), p.1615-1628
  • Notas: ObjectType-Article-2
    SourceType-Scholarly Journals-1
    ObjectType-Feature-1
    content type line 23
  • Descrição: We develop an enhanced interval tree data structure that is suitable for the representation of dynamic IP router tables. Several refinements of this enhanced structure are proposed for a variety of IP router tables. For example, the data structure called BOB (binary tree on binary tree) is developed for dynamic router tables in which the rule filters are nonintersecting ranges and in which ties are broken by selecting the highest-priority rule that matches a destination address. Prefix filters are a special case of nonintersecting ranges and the commonly used longest-prefix tie breaker is a special case of the highest-priority tie breaker. When an n-rule router table is represented using BOB, the highest-priority rule that matches a destination address may be found in O(log/sup 2/n) time; a new rule may be inserted and an old one deleted in O(logn) time. For general ranges, the data structure CBOB (compact BOB) is proposed. For the case when all rule filters are prefixes, the data structure PBOB (prefix BOB) permits highest-priority matching as well as rule insertion and deletion in O(W) time, where W is the length of the longest prefix, each. When all rule filters are prefixes and longest-prefix matching is to be done, the data structure LMPBOB (longest matching-prefix BOB) permits longest-prefix matching in O(W) time; rule insertion and deletion each take O(logn) time. On practical rule tables, BOB and PBOB perform each of the three dynamic-table operations in O(logn) time and with O(logn) cache misses. The number of cache misses incurred by LMPBOB is also O(logn). Experimental results also are presented.
  • Editor: New York: IEEE
  • Idioma: Inglês
Voltar para lista de resultados
Ir para página anteriorAnterior Resultado  13 AvançarIr para próxima página

  • Realização: ABCD-USP USP   Logos de Redes Sociais: Freepik

Buscando em bases de dados remotas. Favor aguardar.