DEV Community: Jorge Massih

Hexagonal Architecture (Ports & Adapters)

Jorge Massih — Thu, 26 Feb 2026 15:41:10 +0000

When I started in software engineering, I thought it was all about languages, frameworks and folders names, actually I remember when my biggest concern was about naming variables in a clear and understandable way — and don't get me wrong, those kind of stuff are really big important things to think, reflect and learn about, but if there's something that we must really care about when working on a project is picking a good Architecture, because that’s where the flexibility to make new changes easily lies. So in this article I'll try to teach you about how to stop your business logic from dating your database.

What Do We Mean by Architecture?

In the world of Software Engineering, architecture is a set of high‑level decisions and constraints that shape how a system is built and how it evolves over time, and this involves thinking about how responsibilities are divided, or how components depend on each other, or even how easy it's to change something — and how much expensive it might be.

A good architecture protects the parts of the system that change the least — like business rules — from the parts that change the most — like infrastructure and delivery mechanisms.

Dirty Architecture?

There's not such official term like a "dirty architecture" or "non-clean architecture", however there are signals for a bad architecture:

Business logic depends on frameworks. It's not a common thing but just for a second think about what happens if you decide to decouple your framework from your project.
Business logic depends on the database. Have you ever thought about using a different database for your project? How much does it cost? And I'm not taking about switching the database driver for the ORM, I'm talking about replacing the whole storage layer. Don't get mad, but if switching from your SQL database to a file in the filesystem makes you to re-write the entire app, your architecture s*cks.
Changing the transport is expensive. You have a REST API and your team decides to switch to gRPC or GraphQL. Would that be an easy task, or would you need to start the project from scratch.

Clean Architecture

What does exist is the term "Clean Architecture", introduced by Robert C. Martin (uncle Bob). You may know him for his books, or maybe for his rants on X. He first wrote about Clean Architecture in a 2012 blog post, and later in 2017 we got a book about the same.

The signals of a Clean Architecture are clear:

Business rules are independent of frameworks.
Business rules are independent of databases.
The system can evolve without rewriting core logic.

As for the rules, the Clean Architecture only has one rule: source code dependencies must point inward, toward the business rules.

Original diagram by Robert C. Martin in his blog, used for educational purposes.

You might be wondering, "If it works, why do I need Clean Architecture?" I asked myself the same question before rewriting an entire service using a "clean" approach. The answer is simple: software rarely stays "done". A system can work perfectly today and still fail the business tomorrow—not because it crashes, but because it becomes too expensive to change.

The key insight that I learned from Clean Architecture book is to compare the extremes: a program that works but is effectively unchangeable becomes useless the moment requirements evolve, while a program that is easy to change can be made to work and kept working as the business learns.

In practice, systems don’t become literally unchangeable, they become economically unchangeable when the cost of change exceeds the value. Clean Architecture is a practical way to stay on the “easy to change” side of that trade‑off by keeping dependencies pointed inward (toward business rules) and treating frameworks, databases, and delivery mechanisms as replaceable details.

Hexagonal Architecture

I could say this is one of the most famous Clean Architectures nowadays, the Hexagonal Architecture or better known as Ports and Adapters, introduced by Alistair Cockburn on his blog in 2005.

It's known as Ports and Adapter because "Ports" are the abstract interfaces that define the protocols and interactions your application exposes or requires according to the business rules, and "Adapters" are the concrete implementations of those ports for specific technologies like HTTP handlers, databases, queues. And the reason because it's also called "Hexagonal Architecture" is not because it's required to have six things; it’s because the hexagon shape shows how multiple interfaces connect with the outside world.

This makes input mechanisms (HTTP, CLI, gRPC) and output mechanisms (Postgres, Redis, APIs) interchangeable without changing the core logic. Think about your project as a Lego system.

The goal of the image above is to highlight that the boundary of the application is what matters: inside are the business rules and use cases, and outside are all the ways the application connects with the world.

You may have also noticed in the image above the distinction between a "Driving side" and a "Driven side". This concept comes from Cockburn's original Ports & Adapters (Hexagonal) model. The driving (primary) side consists of actors and adapters that initiate actions into the application core — such as user interfaces, HTTP/gRPC requests, CLI commands, or test scripts. The driven (secondary) side consists of actors and adapters that the application itself drives in order to fulfill its work — such as databases, external services, or other systems. The distinction is based on who triggers the interaction: driving adapters call into the core through its ports, while driven adapters implement the ports that the core calls to interact with external technology. This separation helps ensure that the business logic remains isolated from and independent of specific technologies or protocols.

In conclusion, if your architecture allows you to refactor code and change transport mechanisms, databases, or queues as easily as swapping your car’s wheels, then you’ve reached the Valhalla of software engineering — a place where change is expected, not feared.

Estructuras de Datos para Network Engineers 101: Hash Tables (Parte II)

Jorge Massih — Fri, 21 May 2021 13:20:12 +0000

Introducción

Según lo que vimos en la primera parte, deberíamos de ser hábiles para entender una Tabla de Hash, en la cual se basará la aplicación que desarrollaremos en este post.

Recuerda que queremos crear una aplicación que nos automatice la asociación de alguna interfaz de nuestro switch con una vlan especifica. A su vez, la vlan estará relacionada con una MAC-Address.

Normalmente en una oficina se tiene el siguiente escenario:

Los dispositivos que utilizamos en el día a día se conectan a un Switch de Acceso, en dicho equipos asociamos Vlans especificas con interfaces a las que están conectadas los dispositivos.

La idea de esta aplicación, es que el proceso de asignación a una Vlan cada vez que conectamos un dispositivo a una interfaz, se haga de manera automática. De igual forma cuando dicho dispositivo sea desconectado de la interfaz correspondiente.

Alcance

Hay que tomar en cuenta que esta aplicación será desarrollada de la manera más básica posible, ya que sólo es una demostración de aplicación de una Estructura de Dato, por lo que hay ciertos features que no podrán ser cubiertos. Dicho esto, nuestro alcance será el siguiente:

Cada interfaz sólo podrá tener una sola MAC-Address.
La aplicación asumirá que la IP del dispositivo ya fue dada, por lo que no contempla el uso de DHCP, NTP, ni otro tipo de servicio.
Sólo se abarcarán equipos Cisco y con el cisco ios como sistema operativo.

Módulos a utilizar

Esta aplicación se soportará de dos módulos esenciales:

Netmiko: Simplifica las conexiones a equipos de Red. Estaremos utilizando este módulo para conectarnos por SSH a los equipos para automatizar tareas y extraer información de sus configuraciones.
Text Template Parser (TTP): Este es un módulo que permite parsear de manera rápida data semi-estructurada mediante plantillas o templates. Estaremos utilizando este módulo para sacar la información útil de la data extraída de los equipos. Por ejemplo, si corremos el comando show ip interface brief, este nos devolverá una tabla, para poder extraer los valores útiles de esa tabla (IPs asignadas, estado de la interfaz, entre otras cosas) podemos auxiliarnos de Regular Expressions o RegEx; Este módulo facilita la extracción de valores ya que crea el RegEx a partir de una plantilla en donde se le muestra como pueden venir los datos.

Nota: Este no es un tutorial acerca de estos módulos, por lo que si querrás saber más sobre como usar Netmiko, te refiero a su documentación para empezar a usaro, de igual manera con TTP, debes ir a la documentación para aprender a usarlo a fondo.

Funcionamiento

Cuando se conecta un dispositivo a nuestro switch, este guarda su MAC-Address en una tabla; nuestra aplicación se mantendrá atenta a la tabla de MACs, y cuando aparezca una nueva, se busca en la Base de Datos, si está ahí, automáticamente se configura dicha interfaz con la Vlan que aparece en la Base de Datos para dicha MAC, también, se utiliza la funcionalidad de Port Security para asegurarse que que no se conecten más dispositivos que los autorizados a dicho puerto.

Cuando un dispositivo se desconecte del switch, la interfaz se apagará, la aplicación estará atenta a dichas interfaces para restaurarlas a su estado por defecto y esta pueda ser utilizada por otro dispositivo que se conecte.

Nota: Por defecto las interfaces contienen la vlan 1, asumiremos que esta será nuestra vlan de Black-hole para dispositivos no identificados.

Ya sabes como es esto, tu no me entiendes, y yo te dejo una imagen que te explica mejor 😜😆

Base de Datos

En este caso, para simplicidad, utilizaremos un archivo de configuración como Base de Datos, en dicho archivo pondremos los datos de las MAC Address y en que Vlans las queremos.

A continuación un ejemplo de la estructura que diseñé para que la aplicación pueda leer dicho archivo sin problemas.

Nota: los Keys o Values que estén entre caracteres <> están hábiles para ser cambiados.

{
  "hosts": {
    "<hostname>": {
      "deviceType": "cisco_ios",
      "username": "<device-username>",
      "password": "<device-password>",
      "secret": "<enable-secret>",
      "macs": {
        "<mac1>": {
          "vlan": "<vlan-id>"
        },
        "<mac2>": {
          "vlan": "<vlan-id>"
        },
        "<mac3>": {
          "vlan": "<vlan-id>"
        },
        "<mac4>": {
          "vlan": "<vlan-id>"
        }
      }
    }
  }
}

Más adelante veremos como quedó el que utilizaré para la demostración.

Archivos de comandos de configuración

Los comandos de configuraciones de los equipos pudieran estar en el código, sin embargo, ponerlos en archivos aparte y extraer los comandos de ahí a la hora de utilizarlos es una solución más elegante. A continuación los 2 archivos de configuración que utilizaré.

create_vlan.conf: Estos son los comandos para asociar una interfaz a una Vlan cuando encontremos una MAC nueva en la tabla y que esté en la Base de Datos.

vlan {vlan}
interface {interface}
switchport mode access
switchport access vlan {vlan}
switchport port-security
switchport port-security maximum 1
switchport port-security violation protect
switchport port-security mac-address {mac}
end

restore_interface.conf: Estos son los comandos para volver una interfaz a su estado por defecto cuando se desconecte un dispositivo y la aplicación lo detecte.

interface {interface}
no switchport port-security
no switchport port-security violation protect
no switchport port-security mac-address
switchport access vlan 1
no switchport nonegotiate
no switchport mode access
end

Templates

Acordamos en que utilizaríamos un modulo para extraer la información de los switches, este módulo requiere del uso de plantillas que modelen como vendrá la información. Este no es un tutorial del uso de Text Template Parser (puedo hacer uno en el futuro si lo piden), para eso te dejé la documentación más arriba. Si no quieres leer, puedes quedar con la idea abstracta de lo que hace el módulo, después de todo, lo importante es entender como incorporamos la estructura a nuestro código.

A continuación los templates que utilicé:

interfaces.xml: Plantilla de la estructura de la tabla dada por el comando show ip interface brief, el cual utilizaremos para saber si las interfaces están prendidas o apagadas.

<group name='{{ interface }}' method='table'>
{{ interface }}     {{ ignore }}      {{ ignore }} {{ ignore }}  {{ status }}                  {{ ignore }}
</group>

mactable.xml: Plantilla de la estructura de la tabla dada por el comando show mac address-table, el cual utilizaremos para saber si hay una MAC Address en la tabla sin inspeccionar.

<group name="{{ mac }}" method="table">
   {{ vlan | DIGIT }}    {{ mac }}    {{ type }}     {{ port }}
   {{ vlan | DIGIT }}    {{ mac }}    {{ type }}      {{ port }}
  {{ vlan | DIGIT }}    {{ mac }}    {{ type }}      {{ port }}
  {{ vlan | DIGIT }}    {{ mac }}    {{ type }}     {{ port }}
</group>

Let's go to code

Ahora vamos a cocinar 😎.

Creamos una clase llama MBVlan (adivina el nombre) que será la que representará todas las funcionalidades de nuestra aplicación. En el método __init__ instanciamos nuestra clase. En ese momento creamos un atributo que guarda el estado inicial del estado de las interfaces, es decir: si están up o down. La idea es que cada vez que se detecte un cambio en el estado de las interfaces, este atributo se actualice. En cuanto al método que se usa get_interfaces, hablaremos de eso más adelante.

from netmiko import ConnectHandler
from ttp import ttp
import json
import time


class MBVlan:
    def __init__(self):
        self.devices = dict([(device, {'interfaces': self.get_interfaces(device)}) for device in
                             self._config['hosts'].keys()])

La propiedad _config nos devuelve el archivo de configuración en forma de un diccionario de Python.

    @property
    def _config(self):
        with open('config.json') as f:
            data = json.load(f)
        return data

Hay dos métodos importantes para la interacción con los equipos, el primero es _get_device_config, este nos devuelve la configuración del archivo de configuracion para ese dispositivo o switch. El otro método es _get_device_conn, el cual gestiona una conexión mediante Netmiko con los dispositivos de red, en este caso son los switches. Fijémonos que se auxilia con el método mencionado anteriormente para obtener los parámetros de conexión estipulados en el archivo de configuración.

    def _get_device_config(self, device_id: str):
        config = self._config['hosts']
        config = config[device_id]
        return config

    def _get_device_conn(self, device_name):
        device_conf = self._get_device_config(device_name)
        conn = ConnectHandler(device_type=device_conf['deviceType'], host=device_name,
                              username=device_conf['username'],
                              password=device_conf['password'],
                              secret=device_conf['secret'])
        return conn

Tenemos dos métodos estáticos (que he colocado dentro de la clase para no crear otro archivo) que nos servirán para cargar contenido en archivos. El primero, open_conf nos abre los archivos de comandos configuración más arriba. El segundo, _load_template nos abre los archivos xml que contienen las plantillas a parsear para extraer la información útil entre toda la que nos muestran los equipos.

    @staticmethod
    def open_conf(filename: str):
        with open(f'commands/{filename}.conf', mode='r') as file:
            conf_template = file.read()

            return conf_template

    @staticmethod
    def load_template(name):
        with open(f'./templates/{name}.xml') as f:
            template = f.read()

        return template

El método que se encarga de cargar las plantilla es de suma importancia porque nos ahorra espacio en nuestro archivo de código, este es usado en los métodos que te voy a mostrar a continuación, get_interfaces y get_tables, los cuales utilizan los módulos que mencionamos al principio para extraer información de los equipos (en este caso los switches) y luego extraer la información que es útil, ya que es mucho texto que necesitamos procesar para entender el estado de la red. Hay algo importante que mencionar sobre TTP, y es que devuelve la data en un diccionario, recuerda que esta es la propia Tabla de Hash de Python, esto nos facilitará acceder a cualquier dato de una manera bastante rápida, tal como lo describimos en la primera parte. Notarás que se hace uso del statement with en esta porción de código, si no sabes para que se usa te recomiendo leer esto.

    def get_interfaces(self, device_id):
        # Crea una nueva connección con netmiko
        with self._get_device_conn(device_id) as conn:
            template = self.load_template('interfaces')

            interfaces = conn.send_command('show ip interface brief')

            # Usa la plantilla que describe el comando 'show ip interface brief'
            # para parsear la data que devuelve a la salida.
            parser = ttp(interfaces, template)
            parser.parse()

            # Aísla la salida dada por el switch y elimina del diccionario
            # el key "Interface", el cual es innecesario porque es el head
            # de la tabla obtenida.
            interfaces = parser.result()[0][0]
            interfaces.pop('Interface')
            return interfaces

    def get_table(self, device_id: str, table_name: str):
        # Crea una nueva connección con netmiko
        with self._get_device_conn(device_id) as conn:
            template = self.load_template(table_name)

            # Usa la plantilla que describe la salida del comando para
            # la tabla de mac address y devuelve la data usable
            mac_table = conn.send_command('show mac address-table')
            parser = ttp(mac_table, template)
            parser.parse()
            # Aisla la salida
            mac_table = parser.result()[0][0]

            return mac_table

Debes recordar, que acorde con el diagrama de flujo que viste al principio, habían dos operaciones sumamente importantes, una de ellas asignaba la vlan correspondiente a la interfaz del nuevo dispositivo conectado al switch, esto lo hacemos mediante el método _update_interfaces, el cual recibe en un diccionario la información de los hosts registrados en el archivo de Base de Datos y que están actualmente conectados algún equipo de la red, se itera sobre el diccionario y se este diccionario también contiene informaciones como que tenemos que actualizar mediante la asignación de una Vlan y la activación del feature Port Security. La función de dicho método es sencilla, este busca todas las interfaces en el diccionario y luego carga el archivo de comandos en el dispositivo al que corresponde dicha interfaz mediante el uso de Netmiko.

La otra operación importante revisaba las interfaces que recién se habían apagado por desconexión del host, de ser el caso, dicha interfaz volvía a su estado por defecto, es decir, vlan por defecto y funcionalidades de Port Security deshabilitadas. Todo esto lo hacemos mediante el método _restore_interfaces.

Nota: Para lograr saber que interfaz se apagó recientemente, la aplicación monitorea la tabla de interfaces cada cierto tiempo y guarda el estado de esta, cuando se detecta un cambio, es porque una interfaz pasó de tener un estado "up" a "down".

    def _update_interface(self, device_id: str, hosts: dict):
        # Crea una nueva connección con netmiko
        with self._get_device_conn(device_id) as conn:
            conf_template = self.open_conf('create_vlan')

            # Itera sobre el diccionario de los hosts en el archivo 
            # de Base de Datos
            for legal_host in hosts:
                # Agrega las variables de cada host a la platilla de comandos 
                commands = conf_template.format(vlan=hosts[legal_host]['vlan'], interface=hosts[legal_host]['port'], 
                                                mac=legal_host).split('\n')[
                           :-1]
                conn.send_config_set(commands)

    def _restore_interfaces(self, device, interfaces: set):
        # Crea una nueva connección con netmiko
        with self._get_device_conn(device) as conn:
            conf_template = self.open_conf('restore_interface')

            # Itera sobre las interfaces a restaurar valores por defecto
            for interface in interfaces:
                # Agrega las variables de cada host a la platilla de comandos  
                commands = conf_template.format(interface=interface).split('\n')[:-1]
                conn.send_config_set(commands)

Ya casi para terminar la explicación de todo el código, existe un método que es como la cereza del pastel, se llama diff, este se encarga de notar los cambios de estados en los dispositivos, es decir, cambios en la tabla de MAC-Address y en el estado de las Interfaces. Este método es el que llama a los métodos _update_interface y _restore_interfaces cuando detecta cambios.

En pocas palabras podemos decir que este método es el Core de todo el proyecto, de hecho, el diagrama de flujo del principio del post es una descripción a nivel general de este método.

Debido a que la información se representa en una Tabla de Hash, no es tan costoso a nivel de procesamiento hacer operaciones con esta, ya que sólo se necesita acceder al Key correspondiente para tener el Value deseado en un tiempo constante ( $O (1)$ ). Te pongo un ejemplo para la detección del cambio en la tabla de MACs de un switch, esta vez utilizaré una imagen:

Con respecto a la detección de cambio de estado de las interfaces, debemos recordar que cuando la clase MBVlan es instanciada, se crea el atributo devices con el estado de todas las interfaces de todos los equipos (espero que te acuerdes de eso), y cada vez que se llama al método diff, dicho atributo es actualizado. La siguiente imagen muestra la actuación del método diff en los cambios de estado de las interfaces.

Para hacer la diferenciación entre las interfaces que siguen encendidas y las que se apagaron, se utiliza la Estructura de Datos basada en Teoría de Conjuntos llamada Set, recuerda que dijimos en el post de introducción que íbamos a hablar de esta estructura, pues llegó el momento. Sucede que, es lo mimo que una Tabla de Hash, pero el Value siempre será None, y, ya que en una Tabla de Hash el Key nunca está en 2 posiciones al mismo tiempo, es imposible que se repita, por lo que podemos tener una estructura donde se almacenen elementos (que en este caso son los Keys de la Tabla de Hash) y que no se repitan. Ingenioso, ¿no?

Esta estructura permite hacer operaciones parecidas a las que describe la Teoría de Conjuntos; para nuestra implementación utilizamos la operación de Diferencia de Conjuntos para ver los cambios entre los estados de interfaces en caché mediante el atributo devices y los estados actuales obtenidos mediante el método get_interfaces. Por el momento, los cambios de estado de las interfaces de down a up no nos interesan (aunque pudieran eficientizar la aplicación, pero añadirían más complejidad), por lo que los filtraremos para ignorarlos en el resultado final. ¿Confundido? Es que he explicado mucho, pero aquí un una imagen que te aclarará el proceso:

Nota: La complejidad de la operación Difference de B y A es de $O (l e n (B))$ . Se está utilizando la estructura Built-in de Python, puedes ver los tiempos de complejidad que emplea aquí.

A continuación te dejo con la porción de código que describe la intención del método diff:

    def diff(self, device):
        new_macs = dict()

        switch_table = self.get_table(device, 'mactable')
        file_table = self._get_device_config(device)['macs']

        cached_int_status = self.devices[device]['interfaces']
        current_int_status = self.get_interfaces(device)

        # Obtiene la diferencia entre el estado actual de las int
        # y el que se tiene almacenado
        int_off = set(item[0] for item in current_int_status.items() if item[1]['status'] == 'down') - set(
            item[0] for item in cached_int_status.items() if item[1]['status'] == 'down')

        # Si existe interfaces apagadas recientemente, las restaura a su estado inicial
        if int_off:
            self._restore_interfaces(device, int_off)

        # Actualiza el estado de las interfaces
        self.devices[device]['interfaces'] = current_int_status

        # Busca nuevos hosts conectados al switch que esten en el archivo de BD
        for mac in switch_table:
            if file_table.get(mac) and switch_table[mac]['vlan'] != file_table[mac]['vlan']:
                new_macs.update({mac: {**file_table[mac], 'port': switch_table[mac]['port']}})

        # Si hay nuevos hosts, entonces actualiza sus interfaces
        if new_macs:
            self._update_interfaces(device, new_macs)

Nota: La actualización del atributo devices pudiera optimizarse y hacerse sólo cuando se detecte un cambio, sin embargo, al igual que otras cosas en la implementación, se ha dejado como está para poder simplificarla y que sea más entendible.

Por último, si lo anterior fue la cereza en el helado, esto es la mermelada; se ha creado un método para correr la aplicación, de modo que a la hora de instanciar la clase, el siguiente paso es llamar a este método, se trata de run, el cual no hace más que iterar sobre todos dispositivos disponibles en nuestro archivo de base de datos config.json y llamar el método diff con cada dispositivo. Esto se hace a una frecuencia de muestreo deseada, yo puse 5 segundos en el ejemplo para fines demostrativos, pero, mientras más alta es la frecuencia de muestreo (tiempo bajo), será más fácil para nuestra aplicación detectar los cambio en nuestros equipos de red o switches.

    def run(self):
        print('running...')
        devices = self.devices.keys()
        while True:
            time.sleep(5)
            for device in devices:
                self.diff(device)

Por lo que tendríamos:

if __name__ == '__main__':
    app = MBVlan()
    app.run()

Demostración y Conclusión

Escenario

La topología siguiente describe el escenario que utilizaremos para la prueba, donde tendremos dos switches de acceso, los cuales se conectan por una red de administración con el servidor que está corriendo el script. La configuración de estos switches solo contempla la de las interfaces de administración y el protocolo de SSH para que el módulo de Netmiko tenga acceso a ellos.

Cualquiera de los hosts que están en el diagrama deben de poder conectarse a cualquiera de los dos switches y ser asignados automáticamente a la Vlan correspondiente.

Archivo de configuración

Este es el archivo que utilicé como Base de Datos:
config.json

{
  "hosts": {
    "192.168.56.154": {
      "deviceType": "cisco_ios",
      "username": "admin",
      "password": "admin",
      "secret": "admin",
      "macs": {
        "0050.7966.6800": {
          "vlan": "10"
        },
        "0050.7966.6801": {
          "vlan": "20"
        },
        "0050.7966.6802": {
          "vlan": "10"
        },
        "0050.7966.6803": {
          "vlan": "30"
        },
        "0050.7966.6804": {
          "vlan": "40"
        },
        "0050.7966.6805": {
          "vlan": "40"
        },
        "0050.7966.6806": {
          "vlan": "30"
        }
      }
    },
    "192.168.56.155": {
      "deviceType": "cisco_ios",
      "username": "admin",
      "password": "admin",
      "secret": "admin",
      "macs": {
        "0050.7966.6800": {
          "vlan": "10"
        },
        "0050.7966.6801": {
          "vlan": "20"
        },
        "0050.7966.6802": {
          "vlan": "10"
        },
        "0050.7966.6803": {
          "vlan": "30"
        },
        "0050.7966.6804": {
          "vlan": "40"
        },
        "0050.7966.6805": {
          "vlan": "40"
        },
        "0050.7966.6806": {
          "vlan": "30"
        }
      }
    }
  }
}

Look at the demo

Aquí un pequeño video del resultado, quiero hacer dos aclaraciones al respecto; la primera es que hice algunos cortes al video para acortar su duración, la segunda aclaración es que, una vez los hosts tienen una IP asignada de forma manual (debido a que en el escenario presentado no hay servidor DHCP), estos necesitan enviar tráfico hacia el switch para que este pueda aprender sus direcciones MACs, por lo que en el video se ve cuando se da ping hacia una IP que no existe en la red para forzar el aprendizaje de la MAC Address por parte del Switch, en un ambiente de producción de la vida real esto no es necesario.

Conclusión

La Tabla de Hash fue clave para el desarrollo de esta aplicación, vemos como en algunas partes de la misma utilizamos algoritmos que corren en una complejidad lineal de $O (n)$ , por lo que utilizar una Lista o un Array pudo haber elevado la complejidad hasta $O(n^3)$ , sin embargo, las operaciones de esta estructura entregan mejor complejidad, lo que da la oportunidad a nuestra aplicación de tener mejor rendimiento.

Por otra parte, tocamos la automatización, la cual es una herramienta muy poderosa, y más cuando se combina con las estructuras de datos adecuadas, y por eso es muy importante conocerlas todas ellas. Ahora te toca a ti ¿Qué piensas automatizar en tu red?¿Qué estructura utilizarías?

Aquí te dejo el proyecto completo:

Estructuras de Datos para Network Engineers 101: Hash Tables (Parte I)

Jorge Massih — Mon, 03 May 2021 13:20:47 +0000

Introducción

"Aqui es donde se separan los niños de los hombres."
— Yo en mi mente cuando empecé a aprender Tablas de Hash.

A muchas personas se les dificulta aprender Tablas de Hash, recuerdo que fue la Estructura de Datos que menos me gustó cuando la vi en la universidad, realmente es una estructura relativamente fácil de aprender, y aquí trataré de explicártela lo mejor posible.

Esta estructura tambien tiene la particularidad de que es MÁGICA, sí, mágica, es una de las Estructuras de Datos más eficientes y rápidas, esto es porque su tiempo de ejecución es constante en el caso promedio. En el primer post mencionamos algo relacionado con complejidad de un algoritmo y su tiempo de ejecución, las Tablas de Hash tienen una complejidad tremendamente buena, abajo te lo detallo.

Algoritmo	Caso Promedio	Peor Caso
Inserción	$O (1)$	$O (n)$
Busqueda	$O (1)$	$O (n)$
Eliminación	$O (1)$	$O (n)$

La motivación de este post será un poco más práctica, se trata de una aplicación que estoy desarrollando sobre Mac Based Vlan para equipos Cisco que no poseen diche feature. Se estará implementando una Tabla de Hash y se usará el módulo de Netmiko, el cual se utiliza para Network Automation. Pero, debido a lo extenso que podría salir este post, lo dividiré en dos partes, en esta te explico todo el fundamento y luego en el otro te explico como desarrollé la aplicación.

¿Qué es una Hash Table?

La Tabla de Hash es una Estructura de Datos de manera "asociativa", esto quiere decir, que tiene que asociar "algo" con "algo" para llevar a cabo sus operaciones.

Antes de explicar como funciona, volvamos al pasado, al primer post: Habíamos dicho que un array o lista, almacena los elementos en bloques de memoria contiguos (uno al lado del otro), eso facilita muchas cosas, como el acceso a algún índice de esa estructura de manera instantánea. Esto nos dice que, si tuviéramos el índice de un elemento en un array o lista, pudiéramos acceder de inmediato a dicho elemento, en un tiempo constante, es decir, no hay que recorrer toda la estructura para llegar a ese elemento.

En la estructura de la Tabla de Hash tenemos 3 componentes importantes:

Los elementos a insertar
Una función de Hash
La Tabla de Hash

El primer componente, es decir, los elementos a insertar, se identifican con un Key único, esto quiere decir que, la manera de nosotros insertar o extraer un valor de la estructura es mediante dicho Key, dicho Key es elegido por nosotros. Podemos ver el Key como un apodo que le ponemos a nuestro valor para poder identificarlo dentro de la estructura, por ejemplo: en mi familia habemos muchos con nombre de Jorge, mi papá se llama Jorge, mi hermano mayor se llama Jorge, uno de mis hermanos más pequeños se llama Jorge, uno de mis primos se llama Jorge, y yo tal vez le ponga Jorge a un hijo mío para no perder la cultura 😂😂, cuando hacemos reuniones familiares y estamos todos los Jorges, usan nuestros segundos nombres (el cual sirve de Key) para referirse a nosotros.

Luego que entendemos el concepto, debemos buscar la manera de asociar el Key a la estructura, esto nos lleva al segundo componente importante, la función de Hash, esta recibe el Key como entrada y retorna un número. Es como una cafetera, le hechas el café y el agua y luego esta te devuelve el resultado. Es importante destacar que dicho número debe ser generado por funciones que corran en tiempo constante, las funciones de Hash eficientes utilizan operaciones matemáticas para lograrlo.

Luego, lo que procede es almacenar los valores en la tabla, ¿Cómo se crea la tabla? Es una lista o arreglo. ¿En que índice de la lista o arreglo almaceno los elementos? En el índice del número obtenido por la Función de Hash. ¿Aún sigues sin entender 😅? Tranquilo, a continuación te presento la hiper-mega-apoteósica imagen explicativa:

Una forma "fácil" en la que aprendí a ver las Tablas de Hash fue la siguiente: imagina que vas a un hospital a consultarte con tu médico, cuando llegas, alguien en la recepción te atiende, tu le dices a que médico quieres ir, y dependiendo del médico que sea te dicen el número del consultorio al que debes ir. Lo mismo pasa con las Tablas de Hash, de acuerdo al Key de algún Value, la Función de Hash retornará un número correspondiente a dicha posición en la tabla (recuera que es una lista o arreglo) donde debe ir el Value.

A continuación te dejo un ejemplo: supongamos que queremos guardar las edades (nuestro Value) de personas, y las asociaremos a sus nombres (nuestro Key).

Para que esta explicación sea lo más simple posible, utilizaremos una Función de Hash sencilla; tomaremos cada letra del nombre de la persona (el Key), las convertiremos en su valor ASCII y las sumaremos.

Los algoritmos de Hash suelen retornar números grandes, esto puede provocar que necesitemos índices grandes dentro de la tabla, lo que se traduce a mucha ocupación en memoria. Algo que se suele hacer es ajustar dicho índice al tamaño de nuestra tabla, es decir, si nuestra tabla será de tamaño de 100 índices, entonces dividimos el número entre 100 y tomamos el residuo (o resto) porque este nunca será mayor al divisor, esto nos garantiza que el valor del hash nunca quedará fuera de la tabla cuando utilicemos un número fijo de valores. En nuestro ejemplo utilizaremos una tabla de tamaño 5, por lo que tendremos que obtener el $5\mod 5$ de las sumas resultantes de los valores de los caracteres, entonces, ese resultado será nuestro índice dentro de la tabla. A continuación, una imagen que vale más que mil palabras que te pueda escribir 😉.

Colisiones

Ya estamos claros en que el índice en donde se alojarán los datos es dados por una función de Hash, pero, ¿Qué pasa si dos Keys producen el mismo número de índice cuando pasan por la Función de Hash? Bueno, en ese caso explota la Tabla de Hash, tienes que activar de inmediato la alarma anti incendios y a parte de eso, correr lo más lejos posible en el menor tiempo posible.

Nah!😂😂, cuando eso pasa ocurre lo que se llama una "Colisión", por lo regular, las colisiones ocurren en los malos algoritmos de Funciones de Hash, de hecho, en teoría estas están siempre supuestas a pasar, no obstante un buen diseño de dicha función reduce las probabilidades de que estas ocurran. Si te interesa el diseño de Funciones de Hash te dejo este Paper.

Tal como se muestra en la imagen anterior, existe una colisión en el ejemplo anterior cuando intentamos insertar a 'Felisa' en la Tabla de Hash, esto porque su índice correspondiente coincide con el índice para 'Isaac'.

Lidiando con Colisiones

Existen varias maneras, porque después de todo, hay que almacenar más de un dato en la misma posición de la tabla, una muy popular es The Chainning Technique, esta consiste en tener una Estructura de Datos como una Linked List en cada índice de la Tabla de Hash. Debido a las colisiones es que se dijo al principio que en el peor caso las operaciones en la Tabla de Hash tomarían una complejidad de tiempo de $O (n)$ , el peor de los casos se da cuando todas entradas a la Tabla de Hash producen colisiones entre ellas y por consiguiente, se almacenarían en el mismo lugar y tendriamos que recorrer toda la Linked List de tamaño $n$ para llegar al elemento que queremos. Te lo explico mejor con una ilustración.

Creando nuestra propia Tabla de Hash

Antes de empezar, quisiera decir que el lenguaje que hemos estado utilizando a lo largo de esta serie contiene esta Estructura de Datos de manera Built-in, no obstante, estaremos realizando nuestra propia estructura para demostrar los conceptos que hemos explicado anteriormente. Es importante mencionar que se utilizará Chainning Technique para manejar las colisiones, para emplear dicho mecanismo haremos uso de nuestra clase Linked List creada en el primer post.

Primero debemos definir los nodos a utilizar en nuestra Tabla de Hash, ya que estos serán utilizados por nuestras Linked Lists, podríamos utilizar la clase Nodo del principio, pero ahora tenemos un atributo adicional que representa al Key, entonces, haciendo uso del segundo y tercer pilar de la POO, la encapsulación y la herencia; crearemos una clase que herede de la clase Nodo para añadir el atributo de key. Si quieres saber más acerca de los 4 pilares de la POO, te recomiendo esto, de todos modos pienso hacer una serie sobre POO.

class HashNode(Node):
    def __init__(self, key, value):
        self._key = key

        super().__init__(value)

    @property
    def key(self):
        return self._key

Nota importante: Recordemos que una Key es un atributo inmutable, y cambiarlo podría implicar moverlo en la Tabla de Hash. Dicha operación no es permitida en esta estructura, entonces, haremos uso de la propiedad key y no le crearemos un setter para que no se pueda modificar.

Ahora vamos a crear nuestra clase HashTable, recordemos que dicha tabla tiene que tener un tamaño específico, también debe tener una Función de Hash asociada para colocar los elementos de acuerdo a su key, por lo cual, como parámetro para instanciar la clase vamos a requerir un número size y una Función de Hash hash_func. Adicional, tenemos el atributo hash_function que nos define la Función de Hash requerida, y tambien el atributo de la tabla table, el cual no es más que una lista de Linked Lists vacías del tamaño del atributo size.

class HashTable:
    def __init__(self, size: int=1024, hash_func:type(lambda x: None) = hash):
        self.size = size
        self.hash_function = hash_func
        self.table = [LinkedList() for _ in range(self.size)]

    def _test_hash_value(self, value):
        if value > self.size:
            raise Exception('Hash function must return a lower number than Hash Table size: {}'.format(self.size))

Nota: La Función de Hash estará como parametro en la clase debido a que la queremos de manera implicita, esto es para poder modificarla de acuerdo a la aplicación del Hash.

Como se pudo observar, se introdujo una función llamada _test_hash_value, la cual velará porque la Funcion de Hash no retorne un valor que pueda estár fuera del índice de la tabla, de ocurrir, se activará una excepcion.

Luego, procedemos con los métodos más importantes: los de insertar y buscar elementos en la Tabla de Hash, para ambos vamos a utilizar los Magic Methods __setitem__ y __getitem__.

Para insertar en la tabla, se obtiene el valor calculado por la Función de Hash y luego se ubica la Linked List de esa posición en la tabla, si la tabla está vacía es porque no hay ningún otro elemento y no ha ocurrido una colisión, sólo tendríamos que asignar el nodo al head de esa Linked List. Cuando ocurre una colisión, se debe insertar el nodo al final de la Linked List. En el caso de la actualización de algún value, se buscará en la Linked List por por dicho Key y Value.

Para buscar en la tabla, hacemos un procedimiento similar, primero sometemos el key a la Función de Hash, luego, accedemos a la Linked List en esa posición y verificamos si el Key se encuentra en la misma.

    def __setitem__(self, key, value):
        node = HashNode(key, value)

        # obtiene el indice calculado por la función de hash
        hash_value = self.hash_function(node.key, self.size)

        # verifica si el valor del índice está en la tabla
        self._test_hash_value(hash_value)

        # obtiene la linked list del índice obtenido
        table_value = self.table[hash_value]

        # asigna el nodo a la posición si no hay algun otro
        if table_value.head is None:
            table_value.head = node

        # lidia con las colisiones y la actualización de values
        else:
            for hash_node in table_value:
                # si el key ya está en la tabla, lo actualiza
                if hash_node.key == key:
                    hash_node.value = value
                    break
                # si ocurre una colisión, añade el nodo al final
                if hash_node.next is None:
                    hash_node.next = node
                    break

    def __getitem__(self, key):
        # obtiene el indice calculado por la función de hash
        hash_value = self.hash_function(key, self.size)

        # verifica si el valor del índice está en la tabla
        self._test_hash_value(hash_value)

        node = self.table[hash_value].head

        # si no hay nodo en la cabeza de la LL, entonces está vacia
        if node is None:
            return None

        # busca un nodo en la Linked List
        while node.key != key:
            if node.next is None:
                return None
            node = node.next

        value = node.value
        return value

Por último, tenemos la función para remover elementos, la cual es básicamente la misma que la función que la de inserción, sólo que una vez encontrado el nodo, lo desvincula de la Linked List. Esto se hace a través de una método llamado unlink añadido a nuestra clase Linked List, esta clase elimina un nodo especifico de una Linked List.

    def remove(self, key):
        # obtiene el indice calculado por la función de hash
        hash_value = self.hash_function(key, self.size)

        # verifica si el valor del índice está en la tabla
        self._test_hash_value(hash_value)

        # verifica si el nodo existe para desvincularlo
        # de una linked list en específico
        item_value = self[key]

        if item_value is None:
            return None

        table_value = self.table[hash_value]
        table_value.unlink(HashNode(key, item_value))

Conclusión

Aunque estamos en la parte conclusiva, esto no quiere decir que cerraremos este tema aquí, ya sabes los fundamentos, el siguiente post será totalmente práctico. Verás una aplicación utilizando el módulo de Netmiko y otros más que facilitan tareas de automatización.

Por otra parte, creamos una clase que maneja las Tablas de Hash de manera correcta, tal vez no sea la más óptima pero sirve para practicar los conceptos. Mi profesor de Estructura de Datos decía que la mejor forma para comprobar los conocimientos es hacer una implementación de estos, aunque también decía que en teoría, la teoría y la práctica son lo mismo; sin embargo, en la práctica no ocurre así... ¿Paradójico verdad?

A continuación, haremos una comparación de desempeño entre la clase que hemos hecho con la que Python ya trae de manera Built-in, a partir de los resultados decidiremos cual vamos a utilizar para desarrollar la aplicación del siguiente post. Abajo te dejo el Replit del código utilizado junto con la demostración.

Estructuras de Datos para Network Engineers 101: Queues & Stacks

Jorge Massih — Mon, 26 Apr 2021 13:59:27 +0000

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.

Estructuras de Datos para Network Engineers 101: Las Linked Lists

Jorge Massih — Mon, 19 Apr 2021 13:20:19 +0000

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 si importante, tener por lo menos nociones del concepto Magic Methods (ó Dundder Methods) de Python.

Introducción

Es muy probable que cundo se hable de organizar datos de manera secuencial tu primera opción sea intentar utilizar un Array (conocido por algunos como Arreglo) o Lista, y bueno, no te culpo, también era el mío antes de conocer por completo el maravilloso mundo de las Estructuras de Datos. No está mal usar dichas estructuras, pero existen otras alternativas para situaciones específicas que harán que tus implementaciones sean más fáciles, seguras y eficientes.

¿Qué es una Linked List?

Linked List o Lista Enlazada (aquí utilizaremos anglicismos 😜) es una estructura de datos lineal, compuesta por objetos llamados Nodos, los cuales están referenciados unos con otros y no necesariamente porque estén ubicados continuamente en bloques de memoria, como pasa tradicionalmente con los Arrays.

Ahora con cucharita 😅: toda la información volátil (que no está almacenada para siempre, sólo mientras corra nuestro código) de nuestra aplicación, así como las variables y objetos, se colocan en un espacio de nuestra memoria volátil (como la RAM), en el caso de los arreglos, se colocan todos los integrantes uno al lado del otro en bloques de memoria continuos. Por ejemplo, supongamos que se tiene lo siguiente:

frutas = ['pizza', 'banana', 'naranja', 'pera', 'piña', 'melón']

La 🍕 no es una fruta pero a veces le echan tanta piña que parece una 😪.

La manera como se aloja en bloques de memoria continuos es la siguiente:

Nota: en la imagen se asume que los caracteres están codificados en UCS-4, lo que implica que se ocupan 4 bytes por caracter.

En el caso de las Linked List, no es necesario, sino, que los integrantes (o Nodos) de dicha lista pueden estar en bloques de memoria bastante alejados o bastante cerca:

Si, ya sé... Te estás preguntando que quiere decir eso, déjame ilustrarte:

Hasta este punto tenemos una explicación más clara que concluye en que las Linked List son un grupo de Nodos que se referencian entre sí. Sin embargo, falta un detalle importante, bueno, dos detalles importantes 😅. Lo primero es que nuestro objeto de Linked List no almacena por si solo los Nodos, sino que esta guarda una referencia sólo al primer Nodo, el cual se llama Head (o cabeza). El Head, a su vez guarda referencia al Nodo siguiente, y así mismo el Nodo siguiente al que le sigue, hasta llegar al último, el cual tiene que apuntar a una dirección de memoria vacía o de valor nulo, esto es porque en una Linked List todos los Nodos deben de estar apuntando a "algo".

Ya que sabemos más o menos los fundamentos, te estarás preguntando sobre las ventajas de sobre las Listas o Arrays, bueno, realmente existen ciertas ventajas que murieron con la utilización de los lenguajes de alto nivel, ya que estos en su mayoría son capaces de ajustar dinámicamente los tamaños de los bloques de memoria, ya que tradicionalmente eran fijos, también permiten tener objetos de diferentes tipos en una misma estructura. No obstante, la verdadera ventaja de esta estructura es el acceso secuencial de la data, lo cual facilita la implementación de otras estructuras muy importantes que veremos más adelante. Ya verás :twink:.

Podemos hacer muchas operaciones como las Linked List, así como insertar elementos, buscar elementos, entre otras más. Sin embargo, la más importante es la de recorrer la Linked List, ya que todas las demás se apoyan en esta, es decir, siempre hay que recorrer la Linked List. Si quieres saber sobre más operaciones que se pueden hacer con las Linked List, te invito a ver esto. También existen otras variantes de Linked List, son fáciles de entender si se aplican los conceptos explicados anteriormente, sin embargo, no las estaremos utilizando a lo largo de esta serie y por eso no me detendré a explicarlas. Si tu aplicación demanda dichas implantaciones, entonces adelante.

Haciendo nuestra propia LinkedList

Cabe destacar que la Estructura de Datos List de Python, puede utilizarse como una Linked List, de hecho tiene métodos para tales fines, también tenemos un módulo llamado Collections que contiene una Estructura llamada Deque, la cual funciona parecido. En nuestro caso, haremos la nuestra para fines de explicación de la implementación. En la vida real, estas estructuras ya construidas por el lenguaje que utilicemos nos ahorran tiempo y son más eficientes.

Primero, empezamos creando los Nodos, estos serán los objetos que almacenaremos en nuestra Linked List, ej.: Pizza, banana, pera, etc.. La estrategia es que el Nodo pueda hacer referencia al objeto que tendrá como valor y al Nodo siguiente.

class Node:

  def __init__(self, value=None, next=None):
    self.value = value
    self.next = next

Hasta aqui no creo que la cosa se complique 😬. Tenemos un objeto Nodo que posee un valor y una referencia de quien le sigue. Por lo tanto, si yo creo un Nodo, le doy su valor y el del Nodo que le sigue, si no tienen ningún otro, entonces apunta a None, así voy creando mi Linked List.

Ok, obvio que no es todo... ¿Cómo puedo saber cual es el Head de mi lista?... No puedo poner dicho objeto Hardcoded en mi código porque si cambia en alguna parte de este, tendré un tremendo lío con la referencia. Por lo tanto, tenemos que crear un objeto Linked List que siempre guarde una referencia en el atributo Head (tal como lo habíamos dicho antes) y también efectué todas las operaciones necesarias sobre la lista, tales como recorrerla, voltearla, añadir otros Nodos, extraerlos, etc.

class LinkedList:
  def __init__(self, head=None, l=None):

    # Referencia al nodo head
    self.head = head

    # Si se pasó una lista como argumento, se crea una Linked List
    if l is not None:
      # Selecciona el primer elemento de la lista como la cabeza
      self.head = Node(l[0])
      current_node = self.head

      list_len = len(l)
      # Itera sobre la lista, si el elemento en curso es el ultimo
      # apunta su siguiente nodo a None
      for i in range(1, list_len):
        current_node.next = Node(l[i])

        if i == list_len:
          current_node.next = None

        else:
          current_node = current_node.next

  # Magic method para recorrer la Linked List
  # Este metodo se llama cuando se está recorriendo la Linked List
  def __iter__(self):
    node = self.head
    # Retorna cada nodo en la iteración correspondiente
    while node is not None:
      yield node
      node = node.next

  # Magic method que retorna la longitud de la lista
  def __len__(self):
    count = 0

    # Itera la Linked List mientras cuenta cada elemento
    for node in self:
      count += 1

    return count

  # Magic method que retorna el nodo, dado un indice a la entrada 
  def __getitem__(self, item):
    current = self.head
    count = 0

    # Retorna el valor del nodo si el item es un entero
    while count != idx:
      current = current.next
      count += 1
    return current

  # Inserta un nodo al final de la Linked List
  def append(self, item: Node):
    #Si no hay nodo, entonces lo inserta como Head
    if self.head is None:
      self.head = item
      self.head.next = None
      return None

    # Busca el último nodo y lo apunta al nodo a insertar
    for node in self:
      if node.next is None:
        node.next = item
        item.next = None

Podemos añadir más métodos para hacer más operaciones con nuestra Linked List, pero lo vamos a dejar hasta ahí por el momento para no crearte un Stackoverflow 😫 😵 en el 🧠. La idea es que entiendas el concepto de esta estructura, las demás operaciones las estaremos viendo conforme salgan los otros posts.

Aplicando lo aprendido

Para poner en práctica lo explicado anteriormente, vamos a utilizar nuestro código y haremos un reproductor de tracklists como el de Spotify (más sencillo). En dado caso que no quieras utilizar lo que se creó más arriba, puedes utilizar las estructuras nativas de Python que te mencioné y tomarlo como ejercicio, esto si no sabes sobre POO, más adelante haré una serie al respecto.

Para esto, consumiremos un API de Discogs que nos proporcione los tracklist de acuerdo a releases de los artistas, elegiremos cual queremos reproducir y podremos cambiar de canción o track (avanzar a la siguiente y/o volver a la anterior).

Nota: esto no es un tutorial para consumir APIs, esta parte la puedes obviar, te puedes hacer de cuenta que es una función que llamas y te da una lista de tracks. De todos modos, pondré el código por si alguien se anima a querer entenderlo, no tiene mucha complejidad.

import time
import requests
from random import sample

def get_tracklists(artist_id:int=57620, releases_n:int = 5) -> list:
  # Url para obtener los releases 
  url = "https://api.discogs.com/artists/{}/releases".format(artist_id)
  response = requests.request("GET", url,).json()['releases']
  releases = [(release['id'], release['title']) for release in response if release['type'] == 'master']

  # Filtrando la data y obteniendo el campo de releases
  random_rels = sample(releases, k=releases_n) 

  # Url para obtener información acerca de los releases
  url = "https://api.discogs.com/masters/{}"
  tracklists_names = []

  # Separando los tracklist de cada reseale
  for rel in random_rels:
    tracklists = requests.request('GET', url.format(rel[0])).json()['tracklist']
    # Tiempo de delay para que api.discogs.com no niegue los responses
    # debido a la velocidad en un corto lapso de tiempo
    time.sleep(0.5)

    tracklists_names.append({rel[1]: [track['title'] for track in tracklists if track['type_'] == 'track']})

  return tracklists_names

En resumen, la funcion retorna una lista con varios diccionarios, en los cuales cada key es el nombre de un release en específico de un artista en específico (para el ejemplo he cogido a Buddy Rich), el value de cada uno sería una lista de las canciones o tracks pertenecientes a dicho release.

Para crear nuestra app de nuestro reproductor, tendríamos lo siguiente:

from apis import get_tracklists
from linked_list import LinkedList, Node

def app():
  # Obtiene la lista de los releases con sus repectivos tracklists
  releases = get_tracklists()
  current_rel, current_track = 'No release selected', Node('No track selected')

  #Linked List para manejar los tracks
  tracklist = LinkedList()

  # String de las opciones del menu
  main_menu = """

Main menu 
===================

1. Select Release
2. Next track
3. Previous track
4. Exit
Current Release: {}
Current Track: {}

Select an option: """

  while True:
    # Guarda la opcion seleccionada en el menu
    selection = input(main_menu.format(current_rel, current_track.value))

    if selection == '1':
      # Construye el menu de releases
      # Para fines de este tutorial, no se abundará esta parte
      rel_menu = lambda rel_list: ''.join(['{}- {} \n'.format(index, list(rel.keys())[0]) for index, rel in zip(range(1, len(rel_list)+1), rel_list)])
      releases_menu = """

Releases Menu
=====================

{}

Select an option: """

      # Captura la selección del release
      release_selection = input(releases_menu.format(rel_menu(releases)))

      # Guarda el release seleccionado en el menu
      # El release contiene una lista con los tracklist
      rel_dic = releases[int(release_selection)-1]
      rel_name = list(rel_dic.keys())[0]
      rel_tracks = list(rel_dic.values())[0]

      # Actualiza la Linked List a una con el tracklist seleccionado 
      tracklist = LinkedList(l=rel_tracks)
      # Asigna los valores para el release seleccionado,
      # y el track en reproduccion como el head de la Linked List
      current_rel, current_track = rel_name, tracklist.head

    # Para cambiar al siguiente solo se asigna el nodo siguiente al track actual
    elif selection == '2':
      if current_track.next:
        current_track = current_track.next

    # Para volver atrás se recorre la lista hasta que el nodo siguiente
    # del iterado sea el del track actual 
    elif selection == '3':
      for track in tracklist:
        if track.next == current_track:
          current_track = track

    # Sale de la aplicación
    elif selection == '4':
      break

Conclusión

La Linked List es una estructura muy poderosa y una alternativa a otras que ya conocemos, sobre todo son útiles en aplicaciones que utilizamos en el día a día, incluyendo los protocolos que se utilizan en nuestros equipos de redes, pero eso no es tema de este post, iremos adentrándonos más adelante.

Te dejo el código en Repl.it del resultado final para que puedas correrlo tu mismo.

Estructuras de Datos para Network Engineers 101: Introducción

Jorge Massih — Mon, 12 Apr 2021 04:11:29 +0000

Hoy en día, tres conceptos están tomando auge en el mundo del Networking y IT: Software Defined Network (ó Redes Definidas Por Software), Network Automation (ó Automatización de Redes) y Network Orquestation (u Orquestación de Redes). Estos se pueden involucrar entre sí, sin embargo, sería un pecado capital confundirlos.

Debido a los nuevos paradigmas emergentes, muchos ingenieros se han tenido que tomar la tarea de aprender a programar. No todo es tan fácil a la hora de hacer este trabajo, existen conocimientos que debemos tener para que el proceso no resulte tan frustrante a la hora de diseñar una aplicación y verla funcionando, me refiero a conocimientos acerca de Algoritmos y Estructura de Datos, esta última, según GeeksForGeeks, no es más que una forma particular de organizar los datos en una computadora, de manera que estos puedan ser accedidos y utilizados de una manera eficiente.

A veces solemos queremos automatizar tareas en nuestra red, o también brindar un servicio que utilice la automatización como medio operativo, o tal vez quisiéramos implementar nuestra propia versión del protocolo OSPF o del STP, hasta nuestra propia aplicación de QoS. Para hacer todas estas cosas es necesario conocer Estructuras de Datos como Linked List, Queues, Stacks, Hash Tables, Graphs, Binary Trees, entre otras más. Afortunadamente, este es el primer post de otros más que vendrán en esta serie llamada Estructuras de Datos para Network Engineers 101, y estas estructuras ya mencionadas las estaremos viendo a lo largo del camino. Es bueno aclarar que no profundizaré a tal nivel que termines siendo un experto en el manejo de esas estructuras que te mencioné, pero si tendrás fundamentos sólidos para llegar a serlo con tu propia práctica.

Te pongo un ejemplo que quizás te motive a seguir leyendo: supón que estás automatizando una tarea en tu red, y en un fragmento de tu código necesitas filtrar una lista de IPs que pueda contener las mismas IPs más de una vez, de modo que las IPs no se repitan. Si tu primer approach sería hacer algo más o menos como lo que vamos a hacer a continuación, entonces esta serie es ideal para ti. Si pensaste en una manera más óptima de resolver el problema, también, te invito que te quedes, quizás aprendas algo nuevo más adelante, nadie sabe 😉.

# No tan cool :p
def remove_duplicated(l: list)->list:
    filtered_list = []
    for ip in l:
        if ip not in filtered_list:
            filtered_list.append(ip)
    return filtered_list

En pocas palabras lo que se intenta hacer es recorrer la lista e ir almacenando cada Ip en otra lista nueva, si esta Ip ya está almacenada, entonces no se añade. Realmente el algoritmo es correcto, y va a funcionar, el problema es que en el mundo del software no es suficiente con que el las aplicaciones solamente funcionen, sino que también sean eficientes a nivel de rendimiento. La idea es que tu código corra lo más óptimo posible cuando tenga entradas de miles de datos y necesite entrar a decenas de equipos en tu red de una manera muy rápida.

A continuación, te mostraré la razón de la ineficiencia del algoritmo concebido, pero no te asustes si no entiendes, no utilizaremos este método a lo largo de la serie ya que trataré de explicarte todo con cucharita y de la forma más clara y resumida posible. Cabe destacar que sí es importante que te tomes un tiempo para aprender a analizar algoritmos, lo agradecerás en un futuro.

Usando el Modelo de la RAM para analizar el tiempo de ejecución, tenemos que.

Instrucción	Veces que se repite
`filtered_list = []`	$1$
`for ip in l`	$n$
`if ip not in filtered_list`	$n(n+1)2\frac{n(n+1)}{2}$
`filtered_list.append(ip)`	$n(n+1)2\frac{n(n+1)}{2}$
`return filtered_list`	$1$

\frac{n(n+1)}{2} + \frac{n(n+1)}{2} + n + 1 + 1

T (n) = n (n + 1) + n + 2

T(n) = n^2 + 2n + 2

Nota: Cada instrucción está asociada a un costo ( $c_i$ ), el cual no es más que una cantidad de pasos que toma para ejecutarse, pero para fines de explicación lo vamos a obviar asumiendo que es 1 para todas las instrucciones, esto para no complicar el asunto.

Si analizamos el Time Complexity (ó Complejidad Temporal) de nuestro algoritmo obtendremos que es una Complejidad Exponencial de tipo $O(n) = n^2$ .

Existe una mejor manera, incluso, el algoritmo es más simple y corre en una Complejidad Lineal de tipo $O (n) = n$ .

# muy cool :p
filtered_list = list(set(l))

# Dependiendo de las operaciones que necesitemos hacer sobre
# el iterable, podemos olvidarnos de convertir el set a lista.

Esta mejora en nuestro algoritmo se debe a que se supo utilizar una estructura de datos adecuada para los fines, la cual está basada en conjuntos numéricos, esta es denominada Set. No vamos a hablar mucho ahora de esta Estructura de Datos, por lo que sólo nos quedaremos sabiendo que no permite elementos repetidos en ella.

Si no has entendido nada de lo que se explicó arriba sobre Big O Notation, Time Complexity y/o Time Execution, entonces tienes mucho que leer. Te recomiendo este libro para iniciar.

Mientras tanto, en lo que el hacha va y viene, te lo voy a explicar de una manera sencilla: El primer algoritmo concebido es ineficiente delante del segundo. ¡Listo!. Esto es culpa de la Estructura de Datos seleccionada, ya que el algoritmo que concibamos dependerá mucho de esto. Y no es que sea una mala Estructura de Datos, lo que pasa es que no es la más adecuada para los fines.

>>> from timeit import timeit
>>> my_ips = ['192.168.1.1', '192.168.1.2', '192.168.2.1', '192.168.2.2', '192.168.3.1', '192.168.3.2', '192.168.4.1', '192.168.4.2', '192.168.5.1', '192.168.5.1']
>>> timeit(lambda: remove_duplicated(my_ips), number=1000) # Tiempo en segundos
0.0016276000000061686
>>> timeit(lambda: list(set(my_ips)), number=1000) # Tiempo en segundos
0.0004897999999684544

Nota: En este ejemplo se utilizaron las condiciones para recrear el peor caso de ejecución para el algoritmo, es decir, donde no se repite ninguna IP y este tenga que correr todas las instrucciones.

Pudimos ver como tomamos de ejemplo 10 IPs y se nota la diferencia en el tiempo de ejecución, de hecho, no es más grande porque la cantidad IPs de entrada es relativamente pequeña comparada con miles que nuestro código pudiera recibir.

Por esto es importante saber sobre Estructuras de Datos, pueden hacer más ligeras las cosas, también, nos ayudan a concebir buenos algoritmos para tratar los problemas de una manera más fácil.

Voy a tratar de enseñarte a través de ejemplos prácticos, la mayoría de estos aplicados al mundo del Networking, publicaré el código de lo que vamos a hacer en cada post y te explicaré cómo funciona, fragmento por fragmento, de una manera resumida claro está. La idea es que no dures demasiado leyendo un post que te vaya a agobiar, sería mejor que pases más tiempo profundizando por tu parte lo que voy a explicar, esto lo harás con los fundamentos que te enseñaré en cada post. Trataré de utilizar un lenguaje muy llano y divertido, para que no te canses si no entiendes algo, además, cualquier duda que tengas puede ser depositada en los comentarios y yo me tomaré de vez en cuando el tiempo para responderlas.

Entonces, si tengo tu atención, te recomiendo el siguiente post, el cual dará inicio formal a la serie y te introducirá a la primera Estructura de Datos a tratar.