En la Figura 2 se ofrece una vista más detallada de la funcionalidad de los puertos de entrada. Como se acaba de decir, éste comprende la función de terminación de la línea de los puertos de entrada y el procesamiento de enlace de datos implementan las capas físicas y de enlace de datos asociadas a un enlace individual del router; la función de búsqueda (y encaminamiento) del puerto de entrada es central para la función de conmutación del router. En muchos routers, es aquí donde el router determina el puerto de salida hacia el que un paquete entrante será encaminado a través del entramado de conmutación. La elección del puerto de salida se hace usando la información contenida en la tabla de encaminamiento.
Aunque la tabla de encaminamiento se calcula en el procesador de ruteo, suele almacenarse una copia shadow en la tabla de encaminamiento en cada puerto de entrada, la cual es actualizada por el procesador de ruteo cuando resulta necesario. Con copias locales de la tabla de encaminamiento, la decisión de conmutación puede realizarse en cada puerto de entrada sin invocar al procesador central de ruteo. Dicha conmutación descentralizada evita la aparición de un cuello de botella en un solo punto del router.
Figura 2. Procesamiento en el puerto de entrada.
En routers con limitada capacidad de procesamiento en el puerto de entrada, éste puede simplemente encaminar el paquete hacia el procesador central de ruteo, que deberá entonces realizar la búsqueda en la tabla de encaminamiento y encaminar el paquete al puerto de salida apropiado. Ésta es la única aproximación usual cuando una estación de trabajo o un servidor funcionan como router; aquí, el procesador de ruteo no es más que la CPU de la estación de trabajo, y el puerto de entrada es tan sólo una tarjeta de la interface de red (por ejemplo, una tarjeta Ethernet).
Partiendo de la existencia de una tarjeta de encaminamiento, la búsqueda en la tabla es conceptualmente simple: sólo hay que buscar a lo largo de la tabla de encaminamiento la entrada que mejor se ajuste a la dirección de red destino del paquete, o una ruta por defecto si no se encuentra la dirección destino. (Cabe recordar que la mejor concordancia es la entrada en la tabla de encaminamiento con el prefijo de red más largo que coincida con la dirección de destino del paquete). En la práctica, sin embargo, las cosas no son tan simples.
Quizá el factor que introduce mayor complejidad es que los routers troncales deban operar a elevadas velocidades y ser capaces de efectuar millones de búsquedas por segundo. Lo que resulta deseable es que el procesamiento del puerto de entrada se pudiera efectuar a la velocidad de la línea, es decir, que se pudiera realizar una búsqueda en menos tiempo del necesario para recibir un paquete por el puerto de entrada. En este caso, el procesamiento de entrada de un paquete entrante podría completarse antes de que se completara la siguiente operación de recepción. Para hacernos una idea de los requisitos de prestaciones de una búsqueda, consideremos el enlace llamado OC-485, que funciona a 2.5Gbps. Con paquetes de 256 bits de longitud, implica una velocidad de búsqueda de aproximadamente un millón de búsquedas por segundo.
Dada la necesidad de operar a las velocidades de enlace de hoy en día, una búsqueda final a lo largo de una tabla de encaminamiento grande es imposible. Una técnica más razonable es almacenar las entradas de la tabla de encaminamiento en una estructura arborescente. Cada nivel del árbol puede verse como correspondiente a un bit en la dirección de destino. Para buscar una dirección, se comienza en el nodo raíz del árbol; si el primer bit de la dirección es un cero, entonces la entrada de la tabla de encaminamiento de la dirección destino se encuentra en el subárbol izquierdo; en caso contrario, se elegiría el subárbol derecho. Se recorre así el subárbol correspondiente utilizando los restantes bits de dirección; si el siguiente bit de dirección es cero, se elige el subárbol izquierdo del árbol original; de no ser así, se elige el subárbol derecho. De esta forma, es posible recorrer la tabla de encaminamiento en N pasos, donde N es el número de bits de la dirección. (El lector observará que ésta es esencialmente una búsqueda binaria sobre un espacio de direcciones de tamaño 2N). En Srinivasan6 se describe una mejora de las técnicas de búsqueda binaria, y en Gupta7 se ofrece una revisión general de algoritmos de clasificación de paquetes. Pero incluso con N = 32 pasos (por ejemplo, con una dirección de 32 bits), la velocidad obtenida mediante búsqueda binaria no es suficientemente buena para los requisitos de ruteo troncal de hoy en día. Por ejemplo, suponiendo un acceso a memoria en cada paso, con una memoria de 40ns de tiempo de acceso, se calculan menos de un millón de búsquedas de direcciones por segundo. Para incrementar estas velocidades de búsqueda se han explotado otras técnicas. Las content addressable memory -CAM-, admiten direcciones IP de 32 bits, y devuelven el contenido de la entrada de la tabla de encaminamiento para esa dirección en un tiempo esencialmente constante. Otra técnica para acelerar las búsquedas es mantener en una caché el encaminamiento de las direcciones más recientemente buscadas, como los propone Feldmeier8. Aquí la cuestión principal es el tamaño de la caché; las medidas realizadas por Thomson9 sugieren que incluso para un enlace de velocidad OC-310, pueden alcanzarse aproximadamente las 256.000 consultas fuente-destino por minuto en un router troncal. Más recientemente se han propuesto estructuras de datos incluso más rápidas, que permiten localizar entradas en la tabla de encaminamiento en log(N) pasos (Waldvogel11), o que comprimen tablas de encaminamiento de nuevas formas (Brodnik12). En Gupta13 se discute una aproximación basada en hardware de la búsqueda, especialmente optimizada para el caso más común en que se buscan direcciones de 24 bits o menos.
Una vez determinado, mediante la búsqueda, el puerto de salida para el paquete, éste podrá ser dirigido hacia el entramado de conmutación. Sin embargo, como veremos más adelante, podría darse el caso de que fuera bloqueado temporalmente antes de entrar en el entramado de conmutación (debido a que hubiera otros paquetes de otros puertos de entrada utilizando en ese momento el entramado). Por ello, deberán ponerse en cola los paquetes bloqueados en los puertos de entrada, y después planificarse para cruzar el entramado de conmutación en un instante posterior. Inspeccionaremos con más detalle el bloqueo, el encolamiento y la planificación de paquetes (tanto en los puertos de entrada como en los de salida).
5 OC-48 es un enlace de red con velocidades de transmisión
de hasta 2488.32 Mbit/s (payload: 2405.376 Mbit/s; overhead: 82.944 Mbit/s).
Las conexiones OC-48 son una de las conexiones de datos más veloces en uso
actualmente. Más rápidas que las conexiones OC-3, OC-12, e incluso sobrepasando
a Gigabit Ethernet, las conexiones OC-48 se utilizan como troncales de muchos
ISPs regionales.
6 V. Srinivasan and G. Varghese, "Fast
Address Lookup Using Controlled Prefix Expansion," ACM Transactions
Computer Sys., Vol. 17, No. 1 (Febrary 1999), pp. 1-40. Ver http://www.cse.ucsd.edu/users/varghese/PAPERS/cpeTOCS.ps.Z
7 P. Gupta, N. McKeown, "Algorithms
for Packet Classification," IEEE Network Magazine, Vol. 15, No.2
(Mar./Apr. 2001), pp. 24-32. Ver
http://klamath.stanford.edu/~pankaj/paps/ieeenetwork_tut_01.pdf
8 D. Feldmeier, "Improving Gateway
Performance with a Routing Table Cache," Proc. 1988 IEEE Infocom
Conference (New Orleans LA, Mar. 1988).
9 K. Thomson, G. Miller, R. Wilder,
"Wide Area Traffic Patterns and Characteristics," IEEE Network
Magazine, Vol. 11, No. 6 (Nov./Dec. 1997), pp.10-23. Ver
http://www.vbns.net/presentations/papers/MCItraffic.pdf
10 OC-3 es un enlace de red con velocidad de transmisión de
hasta 155.52 Mbit/s (payload: 150.336 Mbit/s; overhead: 5.184 Mbit/s) que
emplea fibra óptica. Dependiendo del sistema, se lo conoce como STS-3
(electrical level) and STM-1 (SDH).
11 M. Waldvogel et
al., "Scalable High Speed IP Routing Lookup," Proceedings of ACM
SIGCOMM '97 (Cannes, France, Sept. 1997). Ver
http://www.acm.org/sigs/sigcomm/sigcomm97/papers/p182.html
12 A. Brodnik, S. Carlsson, M. Degemark, S. Pink, "Small Forwarding Tables for Fast Routing
Lookups," Proceedings of ACM SIGCOMM '97 (Cannes, France, Oct. 1997),pp.
3-15. Ver http://www.acm.org/sigs/sigcomm/sigcomm97/papers/p192.html
13 P. Gupta, S. Lin, N. McKeown.
"Routing lookups in hardware at memory access speeds," Proc. IEEE
Infocom 1998 (San Francisco, CA, April 1998), pp. 1241-1248. Ver
http://tiny-tera.stanford.edu/~nickm/papers/Infocom98_lookup.pdf