Esquema de búsqueda IPv4/6 eficiente en memoria usando codificación de vector de bits y particionamiento de prefijos Público Deposited
El desempeño de los esquemas de búsqueda del prefijo de mayor coincidencia en dispo- sitivos de encaminamiento globales tiene un impacto significativo en la calidad de servicio de las comunicaciones que se producen en Internet. El crecimiento acelerado del tráfico de Internet aunado al desarrollo de enlaces de comunicaciones que pueden operar con un ancho de banda de varios gigabit por segundo, implica un desafío para los esquemas de búsqueda del prefijo de mayor coincidencia. Existen diferentes esquemas de búsqueda del prefijo de mayor coincidencia que basan su idea principal en conteos precomputados de bits puestos en uno de un vector de bits que codifica la información de encaminamien- to; dichos esquemas se caracterizan por tener una complejidad en memoria constante y garantizar un alto desempeño al realizar las búsquedas. Sin embargo la desventaja de es- quemas clasificados en conteos precomputados es que tienen una complejidad en memoria exponencial por lo que son utilizados como algoritmos base dentro de esquemas que reali- zan la búsqueda en etapas; de esta manera se puede reducir drásticamente su consumo en memoria. En este trabajo se presentan dos aportaciones principales. El primer aporte con- siste en una generalización de un esquema basado en el conteo precomputado de valores puestos en uno de un vector de bits, esta generalización es independiente a la distribución y número de prefijos en las tablas de encaminamiento; la razón de la generalización es para garantizar el mínimo consumo en memoria eligiendo y justificando los parámetros de operación más adecuados. La segunda aportación que se presenta en este documento consiste en un esquema general de particionaminento en etapas basado en la exploración heurística debido que se debe considerar el número y distribución de prefijos en la tabla. Cabe mencionar que en cada etapa se realiza una búsqueda utilizando cualquier esquema que utiliza conteos precomputados.
Longest Prefix Matching (LPM) address lookup speed in core routers has a significant impact on service quality in communication. The rapid growth of traffic on the Internet and the development of communications links working at speeds of several gigabits per second imply that LPM lookup is a challenge for routers on Internet. There are different LPM lookup schemes based on counts of bit values set to one of a bit-vector that encode routing information in structures of constant size that guarantee fast LPM lookups. Ho- wever, these schemes have exponential memory complexity and then prefix partitioning schemes are used to save memory consumption, this by using LPM lookup in stages. This work contains two main contributions. The first one is a generalizad LPM lookup scheme based on precalculated counts of set bits in a bit-vector for which we obtain a memory cost function that is used to justify fully the choosed optimal parameter values used in the scheme. Our proposal guarantees a constant number of memory access in LPM loo- kup, maximum possible savings in memory, and memory independent costs of the prefix distribution in forwarding tables. The second is that, we propose a LPM lookup sche- me based on a precalculated count of bit values set to one of a bit-vector where a LPM lookup has an instruction cost of two memory accesses and a prefix-partitioning scheme that optimize the available memory usage in LPM lookups in accordance with the prefix distribution in forwarding tables. The proposed prefix-partitioning is based on heuristic search using genetic algorithms that allows a memory optimization in a short period of time. Our proposal can be implemented in general purpose hardware for IPv4/6 schemes.
Relaciones
| En Conjunto Administrativo: |
|---|
Descripciones
| Nombre del atributo | Valores |
|---|---|
| Creador | |
| Colaboradores | |
| Tema | |
| Editor | |
| Idioma | |
| Identificador | |
| Palabra Clave | |
| Año de publicación |
|
| Tipo de Recurso | |
| Derechos | |
| División académica | |
| Línea académica | |
| Licencia |
