ES2262247T3 - Mecanismo para descartar tramas para conmutadores de paquetes. - Google Patents

Abstract

Método para descargar tramas para un conmutador de paquetes, incluyendo dicho método las siguientes etapas: - recibir paquetes pertenecientes al menos a una conexión de transmisión, formando tramas paquetes consecutivos de una conexión de transmisión individual, - conmutar paquetes procedentes de N puertos de entrada del conmutador a N puertos de salida del conmutador a través de, al menos, un puerto intermedio, - utilización de un mecanismo para descartar tramas que descarta tramas completas cuando el nivel de carga del conmutador supera un umbral predeterminado, caracterizado por utilizar el mecanismo para descartar tramas en un conmutador con salida con memoria temporal donde el número máximo de paquetes que pueden transmitirse simultáneamente a un puerto es inferior a N, de tal forma que cuando el número de paquetes que compiten simultáneamente por un puerto individual supera dicho número máximo, al menos un primer paquete de una trama es seleccionado de entre dichos paquetes para ser descartado, y una vez que se ha descartado el primer paquete de una trama, se descarta también el resto de paquetes de la misma trama, independientemente de la capacidad de almacenamiento temporal actual del conmutador.

Description

Mecanismo para descartar tramas para conmutadores de paquetes.

Ámbito de la invención

La presente invención se refiere en general a un mecanismo para descartar paquetes para conmutadores de paquetes. Más específicamente, la invención hace referencia a un mecanismo para descartar paquetes que descarta tramas completas en lugar de descartar de manera aleatoria paquetes individuales (o células).

Antecedentes de la invención

En una red conmutada por paquetes, la mayor parte de las unidades de datos de alto nivel que deben entregarse a través de los conmutadores de la red son demasiado grandes para ser transferidas en un paquete único y, por tanto, deben segmentarse para su entrega. En este contexto, estas unidades de datos de alto nivel, que se utilizan en diversos tipos de aplicaciones, se denominan tramas. La figura 1 muestra la relación entre paquetes y tramas en la forma utilizada en este contexto; una trama de transmisión consiste en M paquetes consecutivos, cada uno de ellos con una longitud fija. En una red TCP/IP sobre ATM, por ejemplo, una trama corresponde a un datagrama IP y los paquetes corresponden a células ATM. El tamaño de la trama (el número de paquetes incluidos en una trama) depende del tipo de aplicación que utiliza una conexión de transmisión.

Si se pierden en destino uno o más de los paquetes de una trama, la trama no puede volver a ensamblarse y debe ser descartada. Por lo tanto, si se evalúa el rendimiento de la red desde el punto de vista de las aplicaciones que envían y reciben estas unidades de datos de alto nivel, debería ser evidente que el retardo de extremo a extremo y la tasa de pérdidas de estas unidades de datos (es decir, tramas) constituyen unos indicadores de rendimiento más importantes que el retardo de extremo a extremo y la tasa de pérdidas de los paquetes de datos individuales.

Cuando se utilizan en la red políticas de descarte aleatorio de paquetes, es muy probable que los paquetes descartados pertenezcan a tramas diferentes en lugar de pertenecer a la misma trama. Por lo tanto, la tasa de pérdida de paquetes de dichos mecanismos de descarte no puede ser una indicación de la calidad de servicio (QoS) al nivel de la aplicación.

Para eliminar este inconveniente, se han propuesto mecanismos de pérdida más sofisticados. Uno de ellos es el denominado el método de descarte temprano de paquetes o "early packet discard" (EPD), que descarta tramas enteras en lugar de descartar paquetes de manera aleatoria. La forma más sencilla de implementar el EPD consiste en establecer un valor umbral en cada memoria temporal del conmutador. El primer paquete de cualquier trama entrante se descarta cuando la tasa de llenado de la memoria temporal supera el valor umbral. Una vez que se ha descartado el primer paquete de una trama, también se descartan los restantes paquetes de la trama aun cuando la tasa de llenado haya descendido por debajo del umbral. No obstante, no se descartará un paquete si se ha aceptado el primer paquete de la misma trama a menos que la memoria temporal esté completamente llena. El valor umbral debería seleccionarse de tal forma que, por
una parte, no se produzca el desbordamiento de la memoria temporal y por la otra no se transmitan tramas corruptas.

Para aquellas personas interesadas en la materia, puede encontrarse una descripción detallada del método EPD, por ejemplo, en un artículo de A. Romanow y S. Floyd, Dynamics of TCP Traffic over ATM Networks, Proc. ACM SIGCOMM 94, pp. 79-88, agosto 1994.

Uno de los inconvenientes del método EPD es que no trata por igual a los diferentes usuarios. Esto se debe al hecho de que el método EPD descarta tramas completas de todas las conexiones sin tener en cuenta sus actuales tasas o su nivel de utilización de la memoria temporal, es decir sin tener en cuenta su contribución relativa a una situación de sobre-
carga. Para solventar este inconveniente se han propuesto diversas variaciones sobre las políticas de descarte selectivas.

No obstante, el método EPD y sus variaciones siguen teniendo como desventaja que su utilización se limita a la asociación con las memorias temporales del conmutador, activándose únicamente el método cuando la tasa de llenado de una memoria temporal supera el umbral.

El método EPD y sus variaciones se han estudiado suponiendo que el conmutador es un conmutador de tasa completa con memoria temporal de salida, es decir que la capacidad del conmutador es igual a la dimensión (número de puertos de entrada/salida) del conmutador. Otro inconveniente relativo a este tipo de conmutador es que la velocidad interna de conmutación del conmutador se eleva cuando el conmutador es de grandes dimensiones. A su vez, esto significa que deben utilizarse unos chips potentes (y caros).

Resumen de la invención

La finalidad de la invención consiste en eliminar los inconvenientes que anteceden y crear un nuevo método que haga posible obtener un rendimiento a nivel de tramas equivalente al de los métodos de la técnica anterior indicados anteriormente, mediante una estructura de conmutador menos compleja y menos cara, y sin necesidad de controlar las tasas de llenado de las memorias temporales individuales.

Este objetivo se logra utilizando la solución definida en las reivindicaciones independientes de la patente.

De acuerdo con la invención, se introduce un mecanismo para descartar tramas en un conmutador con una menor capacidad y, preferiblemente, esencialmente menor que el número de entradas y salidas del conmutador. Esto se lleva a cabo de forma que el primer paquete de una o más tramas es descartado cuando el número de paquetes destinados simultáneamente al mismo puerto del conmutador supera un valor predeterminado (la capacidad del conmutador). Una vez descartado el primer paquete de una trama, se descarta el resto de paquetes de la misma trama al acceder al conmutador, independientemente de la actual capacidad de almacenamiento temporal del conmutador, es decir que se impide que el resto de los paquetes de tramas corrompidas se introduzcan en la estructura del conmutador.

Dicho de otro modo, la idea de la invención consiste en introducir un mecanismo de descarte en la estructura del conmutador de forma que la variable que controla la activación y desactivación del mecanismo de descarte indique el número de paquetes que se están disputando simultáneamente el mismo puerto. Este puerto puede ser un puerto de salida del conmutador o cualquier puerto de salida de la estructura del conmutador. Dado que la característica de varios paquetes disputándose simultáneamente el mismo puerto hace referencia únicamente a conmutadores con memoria temporal de salida, el conmutador de acuerdo con la invención debe ser un conmutador con memoria temporal de salida.

Mediante la solución de acuerdo con la presente invención, la simplicidad de realización que suele ser característica de los conmutadores con cola de entrada, el excelente rendimiento que suele ser característico de los conmutadores con cola de salida, y un tasa muy baja de pérdida de tramas pueden combinarse en un solo conmutador con mayor eficacia que antes.

La simplicidad de la realización puede mejorarse, ya que la velocidad interna de conmutación del conmutador de acuerdo con la invención no es proporcional a las dimensiones del conmutador sino a la capacidad del conmutador, que es inferior y preferiblemente muy inferior a la dimensión.

El conmutador de acuerdo con la invención se basa preferiblemente en una estructura de tipo knockout o eliminación, dado que este tipo de estructura puede modificarse con facilidad para cumplir los requisitos de funcionalidad de la invención.

Breve descripción de las figuras

En los párrafos que siguen se describirá en mayor detalle la invención y sus realizaciones preferidas haciendo referencia a los ejemplos mostrados en las ilustraciones adjuntas, en las cuales:

La figura 1 muestra la relación entre los paquetes y las tramas tal y como se utilizan en esta invención.

La figura 2 muestra la estructura general de un conmutador Knockout.

La figura 3 es un diagrama de bloques de un módulo con una sola salida de un conmutador Knockout.

La figura 4 es un organigrama que muestra las etapas del método de acuerdo con la invención.

La figura 5 muestra una realización preferida del conmutador de acuerdo con la presente invención.

Las figuras 6a a 6d muestran los estados de un elemento de conmutador individual de un concentrador Knockout con prioridad.

La figura 7 muestra la clasificación de los paquetes en el conmutador de la figura 5.

La figura 8 muestra una posible realización del distribuidor de acuse de recibo de la figura 5.

Las figuras 9a a 9d muestran el proceso para descarte de tramas en el conmutador de acuerdo con la invención.

La figura 10 muestra una segunda realización preferida del conmutador de acuerdo con la invención.

La figura 11 es un diagrama de bloques de un filtro individual de paquetes de la figura 10.

La figura 12 es un organigrama que muestra las funciones de un filtro individual de paquetes de la figura 10, y

La figura 13 muestra la ruta de los acuses de recibo en el modelo de salida de la figura 10.

Descripción detallada de la invención

Como se ha indicado anteriormente, el método de acuerdo con la presente invención se utiliza en un conmutador con salida con memoria temporal que conmuta paquetes de longitud fija de N entradas a N salidas. Dicho de otro modo, el conmutador puede ser cualquier conmutador de paquetes adecuado para la conmutación de paquetes de longitud fija, tal como un conmutador ATM. Además, la capacidad del conmutador L, que se define como el número máximo de paquetes que pueden transmitirse simultáneamente a un puerto de salida en un solo intervalo temporal, es inferior a N, es decir L<N. La arquitectura Knockout es una arquitectura de conmutador muy conocida que satisface estos requisitos. Por lo tanto, la invención se describirá seguidamente utilizando el conmutador Knockout como ejemplo de estructura de conmutador a la cual se aplica la invención.

Como es bien conocido, el diseño del conmutador Knockout se basa en el principio de eliminación o knockout: si las llegadas de paquetes de N diferentes líneas de entrada son independientes desde el punto de vista estadístico, existe una muy baja probabilidad de que un número mayor que unos pocos paquetes simultáneos, es decir L paquetes (L<N) estén destinados a cualquier puerto de salida específico, aún en el caso de unas dimensiones arbitrariamente grandes (NxN) del conmutador.

La estructura básica del conmutador Knockout se muestra en la figura 2. Un paquete que llega a una de las N salidas se sitúa en un bus de transmisión desde el cual se transfiere a cada uno de los N módulos de salida OM_{i} (i = 1,2...N). Los módulos de salida leen el encabezado de los paquetes, aceptando los paquetes destinados a dicha salida y enviando a la memoria temporal aquellos paquetes que no puedan ser inmediatamente situados en el enlace de salida, es decir cuando dos o más paquetes se están disputando simultáneamente la misma salida.

En la figura 3 se muestra un diagrama de bloques de un módulo de salida OM_{i}. Cada uno de los buses de entrada está conectado a un filtro de paquetes PF_{i} (i = 1, 2, ...N), es decir hay N filtros de paquetes a la entrada de cada módulo de salida. Cada filtro de paquete lee el encabezado del paquete entrante y lo envía a un concentrador CC cuando el encabezado indica que el paquete está destinado a esa salida. De lo contrario, se ignora el paquete. Por consiguiente, los paquetes que aparecen en las salidas de los filtros de paquetes de un determinado módulo de salida pertenecen a la salida del conmutador a la que presta servicio ese módulo de salida específico.

El concentrador incluye N entradas, pero tan sólo L (L<N) salidas. En cualquier intervalo temporal, el concentrador busca todos los paquetes activos que aparecen en sus entradas. Si encuentran L o menos paquetes, estos paquetes se sitúan en las salidas del concentrador, llenándose primero las salidas situadas más a la izquierda. Por otra parte, si llegan simultáneamente al concentrador más de L paquetes (en el mismo intervalo de tiempo), se perderán esos paquetes excepto L. Seleccionando adecuadamente el valor de L, la tasa de pérdida resultante de este mecanismo de pérdida de paquetes "incorporado" podrá mantenerse a un nivel aceptable. De este modo, L representa el número máximo de paquetes que pueden transferirse simultáneamente a un puerto de salida específico, es decir L representa la capacidad del conmutador.

Las salidas del concentrador están conectadas a un dispositivo de desplazamiento (shifter) SH con L entradas y L salidas. Cuando el concentrador llena en primer lugar sus salidas situadas más a la izquierda, las memorias temporales situadas más a la izquierda tenderían a llenarse si los paquetes fueran directamente conectados del concentrador a las L memorias temporales de salida. La finalidad del dispositivo de desplazamiento consiste en asegurarse de que las L memorias temporales de salida OB_{i} (i = 1,2...L) se llenen de la forma más uniforme posible.

La línea de salida OL_{i} conectada a la salida de las memorias temporales de salida recoge los paquetes cíclicamente de las memorias temporales de salida; en el intervalo de tiempo 1 la línea de salida recoge un paquete de la memoria temporal OB_{1}, en el intervalo de tiempo 2 un paquete de la memoria temporal OB_{2}, etc. Después de que la línea de salida haya recogido un paquete de la última (L^{-ésimo}) memoria temporal, el siguiente paquete se recogerá nuevamente en la primera memoria temporal (OB_{1}).

Dado que el conmutador Knockout es ampliamente conocido, un lector interesado podrá encontrar descripciones detalladas en los muchos artículos y libros que describen su arquitectura y funcionalidad. El conmutador Knockout también se describe en la patente US 4.760.570. Por lo tanto, en este documento no se describirán en mayor detalle las características del conmutador Knockout. Por el contrario, la siguiente descripción detalla las modificaciones introducidas por la presente invención en la arquitectura Knockout.

De acuerdo con la presente invención, se descartan tramas completas en el conmutador en lugar de eliminar paquetes de manera aleatoria, como es el caso del conmutador Knockout. Las tramas se descartan de tal forma
que el conmutador comienza a eliminar de manera aleatoria el primer paquete de una o más tramas cuando
el número de paquetes destinado simultáneamente a un puerto de salida excede de la capacidad del conmutador L. El conmutador identifica las tramas a las que pertenecen los paquetes descartados y continúa descartando los restantes paquetes de dichas tramas. Esta funcionalidad se describe más detalladamente en los siguientes párra-
fos.

Cuando el número de paquetes entrantes destinados simultáneamente al mismo puerto de salida excede de la capacidad del conmutador L, el conmutador comienza a descartar (eliminar) los primeros paquetes de algunas de las tramas entrantes. Una vez descartado (eliminado) un primer paquete de una determinada trama, también se descarta el resto de los paquetes de la misma trama a medida que acceden al conmutador aun cuando el conmutador tenga suficiente capacidad de almacenamiento temporal para aceptar dichos paquetes. No obstante, nunca se descarta un paquete si ya ha sido aceptado el primer paquete de la misma trama por el puerto de salida del conmutador, a menos que la memoria temporal en cuestión esté totalmente llena.

Para impedir que los paquetes pertenecientes a tramas corruptas accedan a la estructura de conmutación, cada puerto de entrada del conmutador, comprueba si el paquete que sale hacia el conmutador pertenece a una trama corrupta, es decir si el primer paquete de la trama a la que pertenece el paquete había sido descartado anteriormente en la estructura del conmutador. Por lo tanto, no existen paquetes que accedan a la estructura de conmutación que pertenezcan a una trama corrupta.

La figura 4 es un organigrama que muestra el principio básico de la invención. El conmutador descarta continuamente los paquetes entrantes que pertenecen a tramas corruptas (etapas 41 y 42). En caso que el número K de paquetes destinados simultáneamente a un puerto de salida exceda de la capacidad del conmutador L, el conmutador descarta un cierto número de primeros paquetes de tramas (es decir (K-L) paquetes) seleccionando los primeros paquetes que van a descartarse de manera aleatoria (etapas 43 y 44). Dicho de otro modo, las (K-L) tramas que van a descartarse se seleccionan de manera aleatoria. Como se explica más adelante, siempre hay al menos (K-L) primeros paquetes compitiendo por un puerto cuando K es mayor que L. En la figura 4, el proceso de eliminación se divide en dos etapas consecutivas, ya que estas etapas se realizan en distintos componentes del conmutador.

Para poder comprobar si un paquete entrante pertenece a una trama corrupta, el puerto de entrada del conmutador debe saber si la estructura de conmutación ha aceptado o descartado un paquete anterior de la misma trama. Dicho de otro modo, la estructura de conmutación debe enviar acuses de recibo a los puertos de entrada.

El principio que antecede puede llevarse a cabo de varias formas. En los siguientes párrafos se mostrarán en mayor detalle dos realizaciones preferidas basadas en el conmutador Knockout.

La figura 5 muestra la primera realización, que incluye un conmutador Knockout KS, N módulos de entrada IM_{i} (i = 1, 2...N), uno para cada bus de entrada del conmutador Knockout, y un distribuidor de acuses de recibo AD. En esta realización, los módulos de entrada ejecutan la etapa 1 de la figura 4, mientras que los concentradores ejecutan la etapa 2.

El conmutador Knockout KS de la figura 5 es similar en otra forma al conmutador Knockout conocido normalmente, a excepción de que los concentradores PC_{i} (i = 1, 2, ... N) eliminan los primeros paquetes de las tramas en lugar de eliminar los paquetes de manera aleatoria. Para conseguirlo, deben utilizarse los conocidos como concentradores priorizados, y los paquetes entrantes deben dividirse en dos clases en función de su probabilidad de pérdida, es decir una clase de alta prioridad y una clase de baja prioridad. La división se efectúa de tal forma que el primer paquete entrante de cada trama se marca como un paquete de baja prioridad y el resto de los paquetes (es decir aquellos que no son el primer paquete de una trama) se marcan como paquetes de alta prioridad (si no se hubiesen descartado anteriormente).

La estructura interna de un concentrador priorizado es similar a la de un concentrador knockout ordinario, excepto que los elementos de conmutación internos 2x2 funcionan de forma que un paquete de alta prioridad siempre ganará la competición frente a un paquete de baja prioridad. Por lo tanto, se transfiere un paquete de baja prioridad al siguiente nivel de competición tan sólo cuando no se encuentra presente ningún paquete de alta prioridad en las entradas de un elemento de conmutación 2x2. Si se encontrasen presentes dos paquetes de alta prioridad en las entradas de un elemento de conmutación 2x2, el paquete situado en la entrada derecha será el que pierda la competición.

Las figuras 6a a 6d muestran los estados de un elemento de conmutación individual SE de un concentrador priorizado PC_{i}, suponiendo que se encuentre presente un paquete en ambas entradas.

La clasificación de los paquetes se muestra en la figura 7, donde Kh representa el número de paquetes de alta prioridad y Kl el número de paquetes de baja prioridad destinados a una salida específica en un solo intervalo de tiempo. En los concentradores priorizados PC_{i} se eliminan (K-L) paquetes de baja prioridad si K>L.

Cabe señalar que nunca se eliminarán en los concentradores paquetes de alta prioridad debido a que el número de paquetes de alta prioridad que compiten no será nunca superior a L. Esto se debe a que los restantes paquetes (que se marcarían como paquetes de alta prioridad) de las tramas corruptas no están autorizados a entrar en la estructura de conmutación. Este es también el motivo por el que siempre hay, al menos, (K-L) primeros paquetes compitiendo por una salida en el caso de que K sea mayor que L. Esto puede demostrarse de la forma siguiente:

Si K>L, existen dos alternativas en función del valor de Kh,

(1) supongamos que Kh>L. Esto significaría que el número de paquetes aceptados por la estructura de conmutación en el intervalo de tiempo anterior es mayor que la capacidad del conmutador (ya que un puerto de salida del conmutador sólo puede aceptar hasta L paquetes simultáneos). Por lo tanto, esta hipótesis es falsa.

(2) supongamos que Kh\leqL. Entonces Kl = K-Kh\geqK-L, es decir existen al menos (K-L) paquetes de baja prioridad (primeros paquetes) compitiendo por la salida.

El distribuidor de acuses de recibo AD, que es común a todos los módulos de salida, tiene NxL entradas y N salidas. Las primeras L entradas están conectadas a las salidas del concentrador del primer módulo de salida, las siguientes L entradas a las salidas del concentrador del segundo módulo de salida, etc. Si un paquete pasa a través de un concentrador PC_{i}, se genera un acuse de recibo y se envía a través del distribuidor al módulo de entrada correcto.

El distribuidor de acuses de recibo AD puede ser, por ejemplo, una matriz simple de barras cruzadas como se muestra en la figura 8. Sólo existe una conexión en cada fila y columna de la matriz de barras cruzadas en cada intervalo de tiempo. La figura 8 muestra cómo se transfiere un acuse de recibo si el módulo de salida OM_{1} acepta un paquete procedente del módulo de entrada IM_{2}. Se supone que el paquete surgirá de la salida L del concentrador de dicho módulo de salida. A continuación se generará en dicha salida un mensaje de acuse de recibo, incluyendo dicho mensaje, además de otros datos, la dirección del puerto de entrada desde el cual ha llegado el paquete (es decir, la dirección de origen). En base a esta dirección de origen, el elemento de conmutación (marcado con un círculo en la figura 8) correspondiente a la dirección de origen conecta el mensaje al módulo de entrada correcto. De este modo, cabe señalar que la etiqueta de encaminado automático que se adjunta a los paquetes (en los módulos de entrada) incluye las direcciones del puerto de entrada y del puerto de salida.

En cada intervalo de tiempo, cada módulo de entrada IM_{i} (i = 1, 2,...N) comprueba si el paquete que sale hacia el conmutador es el primer paquete de una trama. En ese caso, el módulo de entrada marca el paquete como un paquete de baja prioridad y lo transfiere a la estructura de conmutación. Si el paquete no es un primer paquete de una trama, el módulo de entrada comprueba, utilizando los acuses de recibo recibidos, si se ha descartado en el conmutador el paquete anterior perteneciente a la misma conexión. Si se hubiese descartado el paquete anterior, el módulo de entrada descartará el paquete, pero si se hubiese aceptado el paquete anterior, el módulo de entrada marcará el paquete como un paquete de alta prioridad y lo transferirá a la estructura de conmutación.

Como se muestra en relación con el módulo de entrada IM_{N} en la figura 5, la función que acaba de describirse puede llevarse a cabo, por ejemplo, mediante una unidad de control independiente CU que recibe los acuses de recibo, lee el encabezado del paquete que se encuentra al principio de la memoria temporal de entrada IB y marca o descarta dicho paquete.

Las figuras 9a a 9d muestran un ejemplo del proceso de eliminación de tramas en el conmutador de acuerdo con la invención. En este ejemplo, el conmutador tiene cuatro entradas y cuatro salidas, y la capacidad del conmutador L es igual a 2. Los paquetes de baja prioridad se muestran sombreados, y los números que se encuentran en el interior de los paquetes indican el puerto de salida que constituye el destino del paquete.

En el intervalo de tiempo 1 (figura 9a), los dos paquetes destinados a la salida 1 son aceptados debido a que L = 2. En el intervalo de tiempo 2 (figura 9b), tres paquetes se dirigen a la salida 1, por lo que debe descartarse uno de ellos. En este caso, se descarta en el concentrador el paquete procedente de la entrada 2 debido a que es el único paquete de baja prioridad (el primer paquete de una trama). Los otros dos paquetes son aceptados debido a que no son el primer paquete de una trama y a que se han aceptado los anteriores paquetes de las mismas tramas. En el intervalo de tiempo 3 (figura 9c), se elimina el paquete procedente de la entrada 2 en el puerto de entrada 2 debido a que se ha eliminado el anterior paquete de la trama. En el intervalo de tiempo 4 (figura 9d), el paquete procedente de la entrada 2 se elimina nuevamente por el mismo motivo. No obstante, sigue habiendo tres paquetes destinados a la salida 1. El paquete procedente de la entrada 1 se acepta debido a que se trata de un paquete de alta prioridad, mientras que uno de los dos primeros paquetes que compiten por la salida 1 se elimina de manera aleatoria.

En la realización de la figura 5, el conmutador utiliza un gran distribuidor de acuses de recibo centralizado. Alternativamente, el mecanismo de eliminación puede ejecutarse tan sólo en los módulos de salida. Esta realización se indica en la figura 10, que muestra un módulo de salida de este tipo de conmutador. La estructura general del conmutador es la mostrada en la figura 2. Como se muestra en la figura 10, cada módulo de salida incluye N filtros de paquete PF'_{i} (i = 1, 2, ...N), un concentrador priorizado PC_{i} con N entradas y L salidas, un dispositivo de desplazamiento, L memorias temporales de salida, y un distribuidor de acuses de recibo AD_{i} con L entradas y N salidas. En este caso, los filtros del paquete ejecutan la etapa 1 de la figura 4, mientras que el concentrador priorizado ejecuta la etapa 2.

Al igual que en el conmutador Knockout, los filtros de paquete PF'_{i} aceptan paquetes destinados a dicha salida e ignoran el resto. No obstante, en comparación con el filtro de paquetes conocido del conmutador Knockout, cada filtro de paquetes PF'_{i} tiene algunas características adicionales. En primer lugar, un filtro de paquetes impide que en el concentrador entre un paquete procedente de una trama corrupta. En segundo lugar, un filtro de paquetes marca el primer paquete de las tramas como paquete de baja prioridad, y el resto de paquetes como paquetes de alta prioridad. La figura 11 es un diagrama de bloques de un filtro de paquetes individual PF'_{i}, y la figura 12 es un organigrama que muestra las funciones de un filtro de paquetes individual. Un filtro de dirección 101 lee la dirección de destino del paquete entrante y comprueba si el paquete está destinado a la salida en cuestión (etapa 110). Si es así, el paquete se envía a una unidad de identificación 102, que identifica los paquetes que son el primer paquete de las tramas (etapa 111) leyendo los encabezados de los paquetes entrantes. Por ejemplo, si los paquetes son células ATM, el tercer bit del campo PTI del encabezado de la célula indica cuando la célula es la última célula segmentada procedente de una unidad de datos mayor.

Los paquetes que no son primeros paquetes se transfieren a una unidad de marcado 103 (etapa 112) para una comprobación adicional. En esta comprobación adicional, se comprueba la información de acuse de recibo relativa al paquete anterior de la misma conexión. Si se ha aceptado el paquete anterior, se marcará el paquete con una marca de alta prioridad (etapa 114) y se suministrará a la salida del filtro de paquetes. De lo contrario, no se activará la salida del filtro, es decir se impedirá que el paquete acceda al concentrador (se descartará el paquete). Los paquetes identificados como primeros paquetes se saltan la comprobación de acuse de recibo y se marcan directamente con una marca de baja prioridad antes de ser suministrados a la salida del filtro de paquetes.

La siguiente tabla describe el funcionamiento del filtro de paquetes en diversas situaciones.

Entrada	Acuse de recibo	Estado de	Salida
		prioridad/descarte
Primer paquete	1	Baja prioridad	Primer paquete
Primer paquete	0	Baja prioridad	Primer paquete
Otro paquete	1	Alta prioridad	Otro paquete
Otro paquete	0	Descartado	Sin paquete
\begin{minipage}[t]{37mm} El paquete no pertenece a la salida o no hay ningún paquete en la entrada \end{minipage}	1	Descartado	Sin paquete
\begin{minipage}[t]{37mm} El paquete no pertenece a la salida o no hay ningún paquete en la entrada \end{minipage}	0	Descartado	Sin paquete
	\begin{minipage}[t]{37mm} 1: el paquete anterior ha sido aceptado 0: el paquete anterior ha sido descartado o no se ha aceptado ningún paquete \end{minipage}

En la segunda realización del conmutador (figura 10), el concentrador priorizado funciona de la misma forma que en la primera realización (figura 5), es decir lleva a cabo la etapa 2 de la figura 4.

En la segunda realización, los distribuidores de acuse de recibo se distribuyen a cada módulo de salida. Cada distribuidor AD_{i} puede ser una simple red de barras cruzadas LxN con las entradas conectadas a las salidas del concentrador y las salidas conectadas a los filtros de paquetes. Si un paquete atraviesa el concentrador PC_{i}, se genera un acuse de recibo y se devuelve a través del distribuidor al filtro de paquetes del cual procede el paquete. La figura 13 muestra un ejemplo de la trayectoria de realimentación del acuse de recibo. La ruta del paquete se muestra mediante una línea de trazos gruesos y la ruta del acuse de recibo mediante una línea de trazos finos.

Aunque se ha descrito la invención en relación con los ejemplos mostrados en las figuras adjuntas, es evidente que la invención no se limita a dichos ejemplos ya que puede variar de diferentes formas dentro de los límites establecidos por las reivindicaciones de la patente adjuntas. Por ejemplo, el principio descrito anteriormente puede aplicarse también a los elementos de conmutación individuales de una estructura de conmutación de etapas múltiples. En función de la estructura básica del conmutador al cual se aplica la invención, el conmutador puede precisar un medio independiente para contar el número de paquetes que compiten simultáneamente, es decir el nivel de carga, de forma que pueda activarse el mecanismo de eliminación cuando se supera el umbral. No obstante, es preferible una estructura de conmutador basada en el conmutador de tipo Knockout, debido a que no son necesarios medios independientes para medir el nivel de carga. El conmutador puede tener también un mecanismo de eliminación adicional que controla las tasas de llenado de las memorias temporales de salida y elimina paquetes de dichas memorias temporales, es decir que el conmutador puede tener dos mecanismos de eliminación superpuestos.

Claims (12)

1. Método para descargar tramas para un conmutador de paquetes, incluyendo dicho método las siguientes etapas:

- recibir paquetes pertenecientes al menos a una conexión de transmisión, formando tramas paquetes consecutivos de una conexión de transmisión individual,

- conmutar paquetes procedentes de N puertos de entrada del conmutador a N puertos de salida del conmutador a través de, al menos, un puerto intermedio,

- utilización de un mecanismo para descartar tramas que descarta tramas completas cuando el nivel de carga del conmutador supera un umbral predeterminado,

caracterizado por

utilizar el mecanismo para descartar tramas en un conmutador con salida con memoria temporal donde el número máximo de paquetes que pueden transmitirse simultáneamente a un puerto es inferior a N, de tal forma que

cuando el número de paquetes que compiten simultáneamente por un puerto individual supera dicho número máximo, al menos un primer paquete de una trama es seleccionado de entre dichos paquetes para ser descartado, y

una vez que se ha descartado el primer paquete de una trama, se descarta también el resto de paquetes de la misma trama, independientemente de la capacidad de almacenamiento temporal actual del conmutador.

2. Método de acuerdo con la reivindicación 1, caracterizado porque al menos un primer paquete de una trama se selecciona de manera aleatoria de entre los paquetes que sean el primer paquete de una trama.

3. Método de acuerdo con la reivindicación 1, caracterizado porque los restantes paquetes pertenecientes a una trama cuyo primer paquete se ha conmutado a través del conmutador se descartan solamente cuando el conmutador carece de capacidad de almacenamiento temporal de dichos paquetes.

4. Método de acuerdo con la reivindicación 1, caracterizado porque los paquetes recibidos se clasifican como paquetes de alta y baja prioridad y se suministran a un conmutador Knockout que incluye concentradores Knockout en los que los paquetes compiten de dos en dos de tal forma que el paquete de alta prioridad prevalece sobre el paquete de baja prioridad cuando paquetes de alta y baja prioridad compiten entre sí.

5. Método de acuerdo con la reivindicación 1, caracterizado porque dichos paquetes restantes son descartados a la entrada del conmutador para impedir que accedan a dicho conmutador.

6. Conmutador de paquetes con salida con memoria temporal para conmutar paquetes, incluyendo dicho conmutador N puertos de entrada, N puertos de salida y al menos un puerto intermedio dispuesto entre los puertos de entrada y los puertos de salida, con lo que el número máximo de paquetes que pueden transmitirse simultáneamente a un puerto del conmutador es inferior a N,

caracterizado porque

el conmutador incluye adicionalmente

primeros medios (IM_{i}, PC_{1} ... PC_{N}; PF'_{1}.... PF'_{N}, PC_{i}) para descartar, al menos, un primer paquete de una trama cuando el número de paquetes destinados simultáneamente a un puerto individual supera dicho número máximo, y

segundos medios (AD, IM_{i;} AD_{i}, PF'_{1}.... PF'_{N}) para descartar los restantes paquetes de una trama cuando el primer paquete de dicha trama ha sido descartado.

7. Conmutador de paquetes de acuerdo con la reivindicación 6 caracterizado porque dichos primeros medios incluyen

medios de clasificación para dividir los paquetes recibidos en paquetes de alta y baja prioridad, y

Concentradores Knockout (PC_{1} ... PC_{N}; PC_{i}) que incluyen elementos (SE) en los que los paquetes compiten de dos en dos de tal forma que un paquete de alta prioridad siempre prevalece sobre un paquete de baja prioridad cuando dichos paquetes compiten entre sí.

8. Conmutador de paquetes de acuerdo con la reivindicación 7 caracterizado porque incluye

N buses paralelos y N módulos de salida, estando conectado cada módulo de salida a cada uno de los buses e incluyendo un concentrador Knockout y,

N módulos de entrada, estando conectado cada uno de ellos a uno de los buses de entrada e incluyendo cada uno dichos medios de clasificación.

9. Conmutador de paquetes de acuerdo con la reivindicación 8, caracterizado porque los segundos medios incluyen un distribuidor centralizado conectado a las salidas del concentrador Knockout de cada módulo de salida para encaminar los acuses de recibo procedentes de cada concentrador hacia los módulos de entrada, incluyendo dichos acuses de recibo información sobre los paquetes que han pasado los concentradores.

10. Conmutador de paquetes de acuerdo con la reivindicación 9, caracterizado porque el distribuidor centralizado es una matriz de barras cruzadas.

11. Conmutador de paquetes de acuerdo con la reivindicación 7, caracterizado porque el conmutador es un conmutador tipo Knockout que incluye

N buses paralelos y

N módulos de salida, incluyendo cada uno de ellos,

N filtros de paquetes, teniendo cada uno de ellos una entrada y una salida, estando conectada la entrada de cada filtro a uno de los buses e incluyendo cada filtro dichos medios de clasificación (103),

un concentrador Knockout con N entradas y L salidas, estando conectada cada una de las entradas a la salida de uno de los filtros de paquetes, y

un distribuidor (AD_{i}) conectado a las salidas del concentrador para encaminar los acuses de recibo procedentes del concentrador a los filtros de paquetes, conteniendo dichos acuses de recibo información sobre los paquetes que han pasado el concentrador.

12. Conmutador de paquetes de acuerdo con la reivindicación 11, caracterizado porque el distribuidor es una matriz de barras cruzadas.