Conmutación de paquetes sin puntos muertos

En las redes informáticas, el interbloqueo es la falla más grave del sistema. Los interbloqueos son situaciones en las que los paquetes se atascan en un bucle y nunca pueden llegar a su destino sin importar la secuencia de movimientos que se realicen. Se debe observar el interbloqueo y manejarlo con cuidado para evitar fallas en el sistema. 

La mayoría de las redes que tenemos hoy en día son redes de conmutación de paquetes donde el mensaje se divide en paquetes y los paquetes se enrutan desde el origen hasta el destino.

Puntos muertos de almacenamiento y reenvío:

Este es el interbloqueo ampliamente discutido en el que el Node intermedio puede recibir paquetes de diferentes destinos y tiene que almacenar esos paquetes en su búfer local y reenviarlos al siguiente Node de acuerdo con su tabla de enrutamiento, ya que el búfer local es de tamaño finito. se produce un interbloqueo .

Ejemplo: a,b,cd son los cuatro Nodes, todos los Nodes tienen un tamaño de búfer de 4. Supongamos que el Node ‘a’ envía paquetes a ‘d’ a través de ‘b’ y el Node ‘d’ también envía paquetes a ‘a’ a través de ‘c’

Solución:  ahora, para llegar al Node ‘d’, todos los paquetes de ‘b’ deben transferirse a ‘c’, y de manera similar, para llegar a ‘a’, todos los Nodes de ‘c’ deben llegar a ‘b’ pero ninguno de los Nodes tiene un búfer vacío.

Supuestos para resolver interbloqueos de almacenamiento y reenvío:

Algunas suposiciones para resolver el problema son las siguientes:

Modelo:La red es un grafo G =(V, E), V es el conjunto de procesadores y E es el conjunto de enlaces de comunicación. Cada Node tiene B buffers, y k, la longitud de la ruta más larga tomada por un paquete en G

Movimientos: Vemos el cálculo distribuido como un conjunto de movimientos, es decir; algo sucede en el entorno y el Node reacciona a eso.

1. Generación : un Node que crea o recibe un nuevo paquete ‘p’. Se sabe que este Node es una fuente del paquete.
2. Reenvío: el paquete se reenvía al nuevo Node que tiene un búfer vacío en su ruta.
3. Consumo: cuando el paquete llega al destino , se elimina del búfer.

Requisito para la conmutación de paquetes:

1. Un algoritmo de controlador que permite varios movimientos en una red.
2. Siempre se permite el consumo de un paquete (en su destino).
3. Siempre se permite la generación de un paquete en un Node donde todos los buffers están vacíos.
4. El controlador utiliza solo información local.
5. Se dice que un controlador está libre de puntos muertos si protege la red de puntos muertos.

Solución para almacenar y reenviar interbloqueo:

Para resolver este punto muerto tenemos dos soluciones:

1. Grupos de almacenamiento intermedio estructurados
2. Grupos de almacenamiento intermedio no estructurados

Grupos de almacenamiento intermedio estructurados: 

Los métodos que utilizan grupos de búfer estructurados identificarán para un Node y un paquete un búfer específico que debe tomarse si se genera o recibe un paquete. Si este búfer está ocupado, el paquete no puede aceptarse.

1. Gráfico de búfer (BG): es una solución estructurada para resolver el interbloqueo. Es un gráfico dirigido virtual definido sobre el búfer en la red de manera que,

1. Buffer Graph (BG) no tiene un ciclo dirigido, es decir; es acíclico.
2. Para cada ruta de enrutamiento, debe haber una ruta en el gráfico de búfer

[ NOTA: La ruta a través de la cual se mueve el paquete está determinada por el algoritmo de enrutamiento, y la estrategia de administración del búfer es establecer en qué búfer se almacenará el paquete en el siguiente Node. ]

2. Controlador de gráfico de búfer:

• Solo se permite la generación del paquete si hay un búfer vacío en el Node.
• El reenvío de un paquete solo está permitido si hay un búfer vacío en el siguiente Node.

Mediante este conjunto de reglas, se evita el interbloqueo y se protege la pérdida de paquetes.

Desventaja: uso limitado del búfer de almacenamiento.

Grupos de almacenamiento intermedio no estructurados: 

En los métodos que utilizan grupos de búfer no estructurados, todos los búfer son iguales; el método solo prescribe si un paquete puede aceptarse o no, pero no determina en qué búfer debe colocarse.

1. Controlador de conteo directo (FC): es una solución no estructurada, para un paquete p, sea p _el número de saltos para llegar al destino y f _u sea el número de búferes en el Node luego el controlador acepta el paquete p si s _p <f _u .
Si B denota el número máximo de búfer libre en el Node y k denota el número máximo de saltos para llegar al destino, entonces B>K siempre garantiza un estado sin puntos muertos. 
De lo anterior, podemos decir que el controlador de conteo hacia adelante es un controlador sin puntos muertos.

2. Controlador de estado directo (FS): toma más información sobre el paquete en el extremo receptor. Como en el caso, si el número de búfer vacío b es menor que la ruta del paquete para llegar al destino, entonces reenviamos el controlador de estado como un controlador sin puntos muertos.

3. Controlador de conteo hacia atrás (BC): es una variante del controlador de conteo de reenvío, un paquete que ha realizado algunos movimientos desde su origen a un Node de destino, debe ser aceptado por Destino solo si tiene como máximo algunos búferes no vacíos, es decir; para un paquete p, sea t _p el número de saltos que ha hecho desde su origen, luego el controlador acepta el paquete p en un Node si t _p > kf _u. 
Al aplicar esto en una red, se puede evitar el interbloqueo, por lo que se dice que el controlador de conteo regresivo es el controlador sin interbloqueo.

4. Controlador de estado hacia atrás (BS): similar a los controladores de estado hacia adelante, en los controladores de estado hacia atrás podemos usar más información sobre los paquetes en el Node receptor. 

Relaciones entre FC, BC, FS, BS:

1. FC ⊂ FS, es decir
2. BC ⊂ BS
3. BC ⊂ FC
4. BS ⊂ FS

Algunos otros puntos muertos son:

1. El interbloqueo de la progenie puede surgir cuando un paquete p en la red puede crear otro paquete q, lo que viola la suposición de que la red siempre permite el reenvío y el consumo de un paquete. El interbloqueo de progenie se puede evitar al tener múltiples niveles del gráfico de búfer

2. Puede surgir un punto muerto de liberación de copia cuando el origen retiene una copia del paquete hasta que se recibe un acuse de recibo (extremo a extremo) del paquete desde el destino. Se dan dos extensiones del principio del gráfico de memoria intermedia mediante las cuales se puede evitar el punto muerto de liberación de copia.

3. Puede surgir un interbloqueo de ritmo cuando la red contiene Nodes, con almacenamiento interno limitado, que pueden negarse a consumir mensajes hasta que se hayan generado otros mensajes. El punto muerto de marcapasos se puede evitar haciendo una distinción entre paquetes pacíficos y respuestas de marcapasos.

4. Puede surgir un punto muerto de reensamblaje en redes donde los mensajes grandes se dividen en paquetes más pequeños para la transmisión y ningún paquete puede eliminarse de la red hasta que todos los paquetes del mensaje hayan llegado al destino. Los interbloqueos de reensamblado se pueden evitar utilizando grupos separados de búferes para el reenvío y reensamblado de paquetes.