Estructuras de Datos para Network Engineers 101: Queues & Stacks
Tags: networking, queuestack, python, datastructure
Published: 2021-04-26 13:59:27

Antes de empezar a leer, es recomendable tener manejo del lenguaje de programación [Python 3](https://es.wikipedia.org/wiki/Python), también conocimientos en [Programación Orientada a Objetos (POO)](https://j2logo.com/python/tutorial/programacion-orientada-a-objetos/). No es estrictamente necesario, pero importante, tener por lo menos nociones del concepto [Magic Methods (ó Dundder Methods)](https://recursospython.com/guias-y-manuales/clases-metodos-magicos-y-propiedades/) de Python.

También, te recomiendo que visites el post anterior (si no lo has hecho) acerca de las [Linked List](https://dev.to/jorgmassih/estructuras-de-datos-para-network-engineers-101-las-linked-list-50n9), 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](https://www.sdxcentral.com/data-center/bare-metal/white-box/definitions/what-is-white-box-networking/) 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_](https://en.wikipedia.org/wiki/Packet_loss), a esta situación en las interfaces de red algunos fabricantes le dicen [Overruns](https://www.cisco.com/c/en/us/support/docs/dial-access/asynchronous-connections/15286-serial-overruns.html). 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](https://es.wikipedia.org/wiki/B%C3%BAfer_de_datos) 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 :sweat:. 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 :stuck_out_tongue_winking_eye:) 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)](https://es.wikipedia.org/wiki/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.

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/pxbs074evl9nwutd8pry.png)

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](https://ellibrodepython.com/herencia-en-python) del campo de POO, por lo que nuestra clase _Queue_ heredará de la clase _Linked List_.

```python
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](https://pythones.net/propiedades-en-python-oop#Propiedades_de_atributos_de_clase_en_Python_Getter_Setter_y_Deleter) para hacer un pseudo cambio de nombre.

```python
	@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:dizzy_face:? Te dejo una imagen que te sacará de apuros:

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/roveqrzzjlfkrjw5zdai.png)

```python
	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)](https://es.wikipedia.org/wiki/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.

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/h8gjjmlfvvifir3lhw93.png)

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](https://es.wikipedia.org/wiki/Uno_(juego)):joy:). 

### 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_:

```python
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 :satisfied:), 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 :wink:). ¿Confundido de nuevo:dizzy_face:? _don't worry my friend_, aquí tienes:

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/vsmp7b125cy7vinw3bkb.png)

```python
	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](https://www.genbeta.com/desarrollo/multiprocesamiento-en-python-threads-a-fondo-introduccion).

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](https://pypi.org/project/prettytable/), el cual puede instalarse fácilmente vía [pip](https://pypi.org/project/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_](https://javadesdecero.es/poo/overriding-o-anulacion-metodos/#:~:text=En%20cualquier%20lenguaje%20de%20programaci%C3%B3n,sus%20superclases%20o%20clases%20principales.) al magic method de `__repr__`, esto es para que a la hora de imprimir la Queue, imprimamos la tabla como una representación.

```python
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.

{% replit @Jorgmassih/Queues-y-Stacks-Tutorial %}

<a href="https://www.buymeacoffee.com/jorgmassih"><img src="https://img.buymeacoffee.com/button-api/?text=Buy me a coffee here&emoji=⌨️&slug=jorgmassih&button_colour=5F7FFF&font_colour=ffffff&font_family=Lato&outline_colour=000000&coffee_colour=FFDD00"></a>