Antes de empezar a leer, es recomendable tener manejo del lenguaje de programación Python 3, también conocimientos en Programación Orientada a Objetos (POO). No es estrictamente necesario, pero importante, tener por lo menos nociones del concepto Magic Methods (ó Dundder Methods) de Python.
También, te recomiendo que visites el post anterior (si no lo has hecho) acerca de las Linked List, ya que reutilizaremos algunos conceptos de estos.
Introducción
Tecnologías como White Box Switches (WBS) se están levantando hoy en día con el auge del Software Defined Networking (SDN), en pocas palabras: Los WBS, se refieren a equipos de red que son "anti-vendors" y como tal, sólo vienen con el hardware necesario para lidiar con tráfico de red y opcionalmente un Sistema Operativo (comúnmente una distribución de Linux), después de ahí las demás funcionalidades de esos equipos quedan a tu responsabilidad. Aquí puedes saber algo más si tanto te gustó el tema.
Para animarte a seguir leyendo, te voy a plantear una situación, y es la que estaremos tratando de solucionar a lo largo de este post.
Supón que llegó a tus manos un WBS, y tu trabajo es instalar en el sistema operativo aplicaciones que brinden las funcionalidades de red que tu compañía necesita, sin embargo, hay un problema: el equipo nuevo puede quedarse ahogado al intentar acomodar el tráfico recién llegado, esto ocurre si la velocidad de llegada del tráfico es mayor que la velocidad a la que este le da salida. En tal situación, el tráfico que va llegando se ignora, es decir, ocurre el famoso Packet Loss, a esta situación en las interfaces de red algunos fabricantes le dicen Overruns. Como parte de los mecanismos de asignación de recursos, los equipos de red deben implementar algún tipo de técnica para gobernar la forma en que el tráfico se almacena en el buffer del equipo.
¿Qué es una Queue?
Imagina que estas bebiendo mucha agua, e inclinas la cabeza hacia atrás junto con el vaso, si tragas muy lento con relación a la velocidad a la que baja el agua del vaso, llegará un momento donde esta se botará de tu boca y harás un tremendo reguero 😓. Como ya se mencionó antes, algo similar pasa con los equipos de redes. Las Queues vienen a resolver este problema.
Una Queue o Cola (ya sabes del post anterior que aquí usamos anglicismos 😜) es una Estructura de Datos lineal que almacena los datos de forma ordenada, en donde los primeros en entrar, son los primeros en salir, este mecanismo es llamado FIFO (First In, First Out). Son algo similar a la fila que haces en el banco, o cuando esperas en una llamada a un Call Center porque todos los operadores están ocupados. Te dejo una imagen para que veas a lo que me refiero.
Como te habrás podido imaginar, en la imagen anterior, el objeto que sigue para extraer es obj1, luego obj2, y si quisieras obj4 tendrías que sacar obj3 primero.
Para insertar un elemento hacemos una operación llamada Enqueue, que no es nada más que insertar el elemento al final de la Queue (Rear). Existe una otra operación importante llamada Dequeue, la cual se refiere a extraer el elemento en turno, es decir, el primero (Front). Cabe destacar que cuando se hace un Dequeue, se debe desvincular de la estructura dicho elemento y se debe de poner como primero (Front) al que le sigue.
Implementando nuestra propia Queue
Debido a que ya habíamos implementado una Linked List en el post anterior, vamos a reutilizarla y hacer la implementación sobre dicha Linked List. Sí, esto es válido, podemos ver nuestra Queue como una Linked List que sólo puede retirar el nodo head y se puede insertar despues del último elemento. Entonces, tenemos que el Front será nuestro head y el Rear será el último elemento de la Linked List.
Para la implementación utilizaremos el concepto de herencia del campo de POO, por lo que nuestra clase Queue heredará de la clase Linked List.
class Queue(LinkedList):
def __init__(self, head=None, l=None):
super().__init__(head=None, l=None)
# Si se pasó una lista, crea la Linked List a partir de esta
if l is not None:
self.list_to_linked(l)
Podemos utilizar el atributo head como nuestro Front, y ya que no podemos renombrar en la clase hija los atributos de la clase padre, podemos utilizar los métodos Setter y Getter nativos de Python para hacer un pseudo cambio de nombre.
@property
def front(self):
return self.head
@front.setter
def front(self, new: Node):
self.head = new
Nota: cambiar el nombre sería lo correcto porque agrega legibilidad y contexto al código, es decir, hace que se vea más "limpio".
El siguiente paso es crear los métodos para Enqueing y Dequeing. Para Enqueing la estrategia será hacer uso del método append() que se hereda de nuestra clase Linked List, dicho método sólo recorre la Linked List y e inserta el elemento al final (Rear). Para Dequeing la idea es vincular el Front con el nodo siguiente al primero. ¿Confundido😵? Te dejo una imagen que te sacará de apuros:
def enqueue(self, equeueing: Node):
# Llama el método heredado 'append', el cual itera sobre
# la lista y agrega el nuevo Nodo después del Nodo último
self.append(equeueing)
def dequeue(self):
# Desvincula el Front de su Nodo y lo apunta al siguiente
dequeued = self.front
self.front = self.front.next
dequeued.next = None
return dequeued
¿Qué es un Stack?
Imagina que estás montando cajas en un camión, y las pones una al lado de la otra, llegará un momento donde no habrá más espacio para las cajas, por lo que recurrirás a organizarlas de una manera más eficiente. Ponerlas una arriba de otra es la opción más común, y la que todos preferiríamos, básicamente de eso se trata el Stack o Pila. Otro ejemplo es la pila de platos que se arma antes y/o después de lavarlos, cuando vas a tomar un plato, sacas el que está en la cima para no tumbar los otros, de igual manera, cuando vas a insertar un plato, lo colocas arriba. En esta estructura se colocan los datos de manera que el último en llegar es el primero en salir, dicho mecanismo se conoce como LIFO (Last In, First Out). Principalmente los equipos de red utilizan esta estructura para consultar registros del tráfico, por lo regular, los que se desean ver son los últimos, por eso es más convenientes tenerlos de primero.
Como se puede observar, al último elemento (el cual es el primero en salir) se le llama Top. Las operaciones básicas con esta estructura son Push y Pop, la primera inserta un elemento de último y la segunda retira ese elemento que está de último (como cuando te toca coger 4 cartas jugando UNO😂).
Implementando nuestro propio Stack
De igual forma, utilizaremos nuestra clase Linked List para implementar nuestro Stack. Podemos ver nuestro Stack como una Linked List que sólo puede retirar el nodo Top (que realmente es nuestro head) y se puede insertar al principio (el Top).
Nota: de igual forma que con la Clase Queue, utilizaremos los métodos Setter y Getter nativos de Python para renombrar el head como Top:
class Stack(LinkedList):
def __init__(self, head=None, l=None):
super().__init__(head=None, l=None)
# Si se pasó una lista, crea la Linked List a partir de esta
if l is not None:
# La lista está invertida para mantener el concepto de Stack
self.list_to_linked(lst=l[::-1])
@property
def top(self):
return self.head
@top.setter
def top(self, new: Node):
self.head = new
Los métodos Pop y Push serán similares, de hecho, son inversos. Para el método Pop, utilizaremos la misma técnica que para el proceso de Dequeing (sí, es lo mismo realmente 😆), por lo que puedes volver a consultar la imagen que lo explica si tienes dudas. En el caso del método Push, lo que haremos será utilizar un método ya incorporado en la clase Linked List que se llama insert_first(), este método desvincula el Top (que realmente es el head) del primer nodo y luego lo apunta al nuevo nodo a insertar (recuerda que te dije que era el proceso inverso a Pop 😉). ¿Confundido de nuevo😵? don't worry my friend, aquí tienes:
def push(self, item: Node):
# Llama al método heredado 'insert_first', el cual agrega
# un nodo en la primera posición de la Linked List
self.insert_first(item)
def pop(self):
# Desvincula el Top del nodo a extraer y lo vincula al siguiente
popped = self.top
self.top = self.top.next
# Apunta el nodo extraido a None
popped.next = None
return popped
Resolviendo los problemas con lo aprendido
Para resolver el problema planteado en la introducción, vamos a implementar una Queue como Estructura de Datos para mantener los datos en memoria estructurados en dicho estilo, de modo que se vayan acumulando y salgan en el orden de llegada, es decir, el trafico más viejo primero (FIFO).
Para hacer la aplicación un poco más didáctica y que podamos ver el funcionamiento de la Queue, la centraremos en una simulación de la llegada y salida del tráfico en un tiempo especifico generados aleatoriamente, esto provocará que los paquetes se vayan acumulando en la Queue. Para esto crearemos dos funciones que corran como dos procesos "más o menos paralelos", una para simular la recepción del tráfico y otra para la simulación de la transmisión. Para esto haremos uso de Threads.
También, para hacer el ejercicio más visual, representaremos la Queue en una tabla, donde se especificará el orden de salida. El Id del tráfico (un número generado aleatoriamente para fines de demostración), el tiempo de llegada y las interfaces de entrada y salida.
Para la representación de la tabla utilizaremos un módulo externo llamado Prettytable, el cual puede instalarse fácilmente vía pip como: pip install -U prettytable.
Crearemos una clase llamada TrafficQueue que heredará de la clase creada anteriormente Queue. Esta clase será muy sencilla y su diseño es muy fácil, ya que sólo agrega 2 componentes. El primer componente es un atributo llamado frame_table, que servirá para instanciar el objeto del módulo que nos ayudará a crear la tabla. El segundo componente es un Overriding al magic method de __repr__, esto es para que a la hora de imprimir la Queue, imprimamos la tabla como una representación.
from prettytable import PrettyTable
import time
import threading
import random
from Utils.DataStructures.ds import Node, Queue
import os
class TrafficQueue(Queue):
def __init__(self, head=None, l=None):
super().__init__(head=None, l=None)
# Atributo utilizado para imprimir la tabla
self.frame_table = PrettyTable()
self.frame_table.field_names = ['Index', 'Id', 'Time', 'In Interface','Out Interface']
if l is not None:
self.list_to_linked(l)
def __repr__(self):
# Agrega todos los nodos de la Queue a la tabla
self.frame_table.clear_rows()
if self.front:
count = 0
for node in self:
count += 1
frame_id, frame_time, input_int, output_int = node.value
self.frame_table.add_row([count, frame_id, frame_time, input_int, output_int])
return self.frame_table.get_string()
queue = TrafficQueue()
def rx(interfaces: list, input_time):
# Espera el tiempo indicado para simular la llegada del tráfico
# en interfaces de entrada y salida aleatorias
while True:
time.sleep(input_time)
frame_id = hex(abs(random.randint(100, 5000)))
frame_time = time.ctime(time.time())
input_int, output_int = random.sample(interfaces, 2)
# Agrega la información del trafico generado a la Queue
queue.enqueue(Node(value=(frame_id, frame_time, input_int, output_int)))
def tx(output_time):
# Espera el tiempo indicado para simular la salida del tráfico
while True:
time.sleep(output_time)
queue.dequeue()
def app():
# Lista de los números de interfaces a simular
interfaces = range(1,21)
# Tiempo de entrada/salida del tráfico
# El tiempo de entrada debe ser menor
input_time, output_time = (0.7, 0.8)
# Crea los threads
rx_thread = threading.Thread(target=rx, args=(interfaces, input_time))
tx_thread = threading.Thread(target=tx, args=(output_time,))
rx_thread.start()
tx_thread.start()
refresh_time = 0.5
# Hará una actualización de la taba en el tiempo estipulado
while True:
time.sleep(refresh_time)
os.system('clear') if os.name == 'posix' else os.system('cls')
print('Network Equipment Interfaces Queue')
print(queue, end= '\r')
Conclusión
Realizamos una aplicación que concentra el uso de Queues y explica la importancia de estas en el mundo de las redes computacionales. Cabe destacar que lo importante de la parte de Queues fue la explicación de la estructura mediante la implementación de una aplicación que maneja el reenvío del tráfico en nuestros equipos de red. Normalmente estos equipos ya traen implementado un sistema de Queues para resolver la problemática planteada, sin embargo, existe la posibilidad de que se necesite crear una variante propia de la implementación, para hacer modelos de QoS y demás, de ser así, si prestaste atención, entonces lo tienes cubierto.
Te dejo el repositorio de replit con todo el código desarrollado y la aplicación final. Te recomiendo que la abras en la web de replit directamente y pongas el apartado de la consola más grande para que se puede apreciar bien la tabla.
Top comments (1)
Buen post!