Efficient Partitioning of the Binary Trie to Keep IPv6 Forwarding Tables in cache Memories
Fecha: 19 de junio de 2014 a las 11:40 hrs.
Presenta: Fidel Ulises Sanchez Jimenez
Afiliación: Alumno de doctorado PCyTI
Asesores: Dr. Miguel Ángel Ruiz Sánchez y Dr.César Jalpa Villanueva
Resumen: Different bit-vector encoding schemes of the forwarding table guarantee low and constant lookup latency in Longest Prefix Matching (LPM) lookups; however those schemes have an exponential memory complexity and no proposal justifies fully the parameter values used in the encoding. Usually the encoding parameters can be seen as cuts in a binary Trie and cuts belong to combination problem; also the updates of forwarding tables is once or twice times in a second then, the combination problem has to solved in a short time. We use heuristic search to find the best combination that gives an efficient partitioning of the Trie in terms of memory and LPM instructions.