D E S C R I P C I Ó N

CAMPO DE LA INVENCIÓN

La presente invención se engloba en el campo de las Telecomunicaciones. Dentro de este ámbito, en el de la virtualización de redes de comunicaciones.

ANTECEDENTES DE LA INVENCIÓN

La virtualización de redes de telecomunicaciones es una técnica clave en el desarrollo del futuro de Internet que consiste en compartir recursos (de red) de uno o diferentes sustratos físicos por diferentes operadores de red de manera transparente y segura [L. Peterson, S. Shenker, J. Turner. "Overcoming the Internet impasse through Virtualization". ACM HotNets III, 2004\, [N. Feamster, L. Gao, J. Rexford. "How to léase the Internet in your spare time". Georgia Tech Technical Report GT-CSS-06- 10, August 2006\. Existen varias ramas de investigación abiertas respecto a dicha técnica. Una de ellas es el método de asociación, que consiste en el proceso de mapear las solicitudes de redes virtuales VNets (del inglés Virtual Networks) compuestas por nodos virtuales y sus respectivos enlaces virtuales de manera óptima en la infraestructura física tratando de maximizar el uso de los recursos disponibles.

Varios son los puntos que hacen del algoritmo de asociación de VNets un problema difícil de solventar de cara a un mapeo óptimo y una mejor explotación de los recursos físicos disponibles:

- Los nodos virtuales solicitan una capacidad concreta de procesamiento CPU (del inglés Central Processor Unit) y ancho de banda BW (del inglés Band Width) para sus enlaces que han de ser satisfechos mediante los recursos físicos disponibles. En ocasiones no será posible dar servicio a dichas VNets por lo que deberán ser pospuestas o rechazadas.

- El desconocimiento previo de la llegada de nuevas peticiones hace de la asociación de recursos una tarea difícil de afrontar ya que se debe tratar de alojar la petición en función de los recursos físicos actuales tratando de maximizar la posibilidad de alojar futuras VNets si bien desconocemos los requerimientos que solicitarán.

- No existe ninguna restricción respecto al tipo de topología a solicitar por el operador de red por lo que el sistema debe adaptarse en todo momento a las necesidades específicas de cada esquema de red.

El problema del mapeo se puede abordar desde diferentes puntos de vista, dependiendo de las métricas o criterios de optimización que interese aplicar en cada caso. Son numerosas a día de hoy las soluciones que tratan de solventar el problema del alojamiento (del inglés "allocation"). [M. Yu, Y. Yi, J. Rexford and M. Chiang. "Rethinking Virtual Network Embedding: Substrate Support for Path Splitting and Migration". ACM SIGCOMM, April 2008\ y [ V. Zhu and M. Ammar. "Algoríthms for assigning substrate network resources to virtual network components" In Proceedings for IEEE GLOBECOM, 2003, pp. 3004-3008] muestran el proceso de asignación de recursos como un problema de complejidad computacional NP-complejo ó NP-hard (del inglés Non-Deterministic Polynomial- time hard) si bien lo afrontan desde una perspectiva diferente. Así M. Yu et al asumen la posibilidad de dividir el ancho de banda solicitado en diferentes rutas físicas mediante la técnica denominada División de Caminos (del inglés Path Splitting) y aplican otras técnicas de tiempo polinomial para resolver el mapeo de nodos y enlaces. Para ello, optan por la división del tiempo de ejecución en ventanas de tiempo de manera que durante el transcurso de una ventana varias son las solicitudes de alojamiento de VNets que llegan al sistema. Asimismo proponen la aplicación del concepto de migración para el balance dinámico de los recursos físicos cada ventana de tiempo. Sin embargo, Y. Zhu & M. Ammar aplican una serie de métodos heurísticos para la asignación de recursos. También dividen el proceso de asignación de nodos virtuales y enlaces virtuales como procesos diferentes. A partir de la información de utilización de cada elemento físico de la red, el sistema en primer lugar asigna el nodo central de la VNet y continua el proceso de asignación dividiendo la topología de red solicitada en pequeñas topologías en estrella que serán finalmente unidas. Zhu & Ammar proponen un método de migración en el cual las VNets en situación crítica, es decir, aquellas en las que sus recursos físicos se encuentran más saturados, son las primeras en tratar de reconfigurar. [N.M. Chowdhury, M. Rahman and R. Boutaba. "Virtual Network Embedding with Coordinated Node and Link mapping". Accepted for IEEE INFOCOM, 2009] por su parte trata de optimizar la solución considerando el alojamiento de nodos y enlaces virtuales de manera conjunta en vez del tradicional sistema separado. Para ello, se introduce el concepto de clusters, nodos situados dentro de una célula de localización, y meta-nodes, nodos encargados de gestionar dichos nodos del clúster. [/. Houidi, W. Louati and D. Zeghlache. "A Distributed Virtual Network Mapping Algorithm". IEEE International Conference on Communications (ICC 2008), 2008] propone un enfoque diferente a los análisis anteriores mediante un sistema de almacenamiento distribuido entre los nodos de la red. Con el objetivo de reducir el tiempo de asignación, divide la infraestructura en clusters compuestos por nodos de similares características.

A día de hoy, el problema de la asignación de recursos en la virtualización de redes se ha restringido a redes de telecomunicaciones estáticas y cableadas, si bien la Internet of Things [Internet Reports 2005: "The Internet of Things 2005, 7th edition":http://www.itu.int/publ/S-POLIR.IT-2005/e] prevé un nuevo paradigma de red compuesto, principalmente, por nodos móviles.

RESUMEN DE LA INVENCIÓN

La presente invención se refiere a un sistema y método de asignación de recursos para el alojamiento de redes virtuales sobre un sustrato formado por nodos inalámbricos móviles.

El método y sistema se centran en la maximización del número de VNets que conviven en el sistema simultáneamente.

En concreto, en una realización de la presente invención, se proporciona un método para la asignación de una red virtual en una red de comunicaciones, donde dicha red de comunicaciones comprende una pluralidad de nodos físicos móviles situados en una zona dividida en celdas de localización. Cada uno de los nodos físicos móviles tiene una capacidad de procesamiento, una localización, un factor de movilidad y una velocidad de movimiento y se comunican mediante unas rutas físicas donde cada una de dichas rutas físicas comprende, al menos, un enlace físico con un ancho de banda, entre dos nodos físicos móviles, disponible en un determinado momento. El método comprende los siguientes pasos:

• recibir en un nodo físico móvil, perteneciente a dicha red de comunicaciones, una solicitud de asignación, por un tiempo determinado, de una red virtual que comprende una pluralidad de nodos virtuales que tienen una capacidad de procesamiento y una localización y se comunican mediante una pluralidad de enlaces virtuales con un ancho de banda determinado;

• retransmitir desde dicho nodo físico móvil la solicitud de asignación hasta el nodo físico móvil con la mayor cantidad de recursos, donde dichos recursos dependen en cada uno de los nodos físicos móviles del ancho de banda disponible de sus enlaces, su movilidad y de su velocidad de movimiento;

• almacenar dicha solicitud de asignación en dicho nodo físico móvil con la mayor cantidad de recursos;

• asignar el nodo principal de la red virtual a dicho nodo físico móvil con la mayor cantidad de recursos;

• iniciar, a partir del nodo central de la red virtual, un proceso de asignación del resto de nodos y enlaces virtuales a otros nodos físicos móviles y rutas físicas pertenecientes a la red de comunicación, siguiendo un criterio de mayor disponibilidad de recursos, que los pondera en función de la cantidad y la movilidad de los nodos;

• una vez que la totalidad de nodos y enlaces virtuales han sido asignados, mantener dicha red virtual alojada durante el tiempo indicado en la solicitud de asignación.

Los recursos de cada nodo físico móvil se calculan como el cociente entre el sumatorio del ancho de banda de sus enlaces y la suma de la unidad más el producto de su factor de movilidad por su velocidad de movimiento.

El factor de movilidad toma los siguientes valores:

• 0, para un nodo físico móvil estático durante un determinado periodo de tiempo;

• 1 , para un nodo físico móvil que comienza a moverse o a detenerse tras un determinado periodo de tiempo; • 2, para un nodo físico móvil que se mueve durante un determinado periodo de tiempo.

Si por falta de capacidad de procesamiento en dichos nodos físicos móviles o de ancho de banda en los enlaces físicos, la red virtual no puede ser asignada, se liberan los recursos asociados a la misma y se mantiene dicha solicitud de asignación en la memoria del nodo físico móvil con mayor cantidad de recursos para un futuro reintento.

Si el movimiento de un nodo físico móvil que tiene asignado un nodo virtual con requerimientos de localización, causa el cambio de celda de localización, se reasigna dicho nodo virtual y sus enlaces virtuales correspondientes, a otro nodo físico móvil válido en la celda correcta (solicitada).

Además, si el movimiento de un nodo físico móvil causa la ruptura de un enlace físico, que tiene asignado un enlace virtual, se reasigna dicho enlace virtual a otra ruta física válida de dicha red de comunicaciones.

Periódicamente y para una red virtual que permanece asignada durante un tiempo superior a un umbral determinado, los nodos virtuales reasignan su enlace virtual operativo a una nueva ruta física con un coste menor. Este proceso se denomina migración. En concreto, se calcula el coste de ambas rutas: actual y candidata, donde dicho coste se calcula para cada ruta física como el sumatorio del ancho de banda de cada enlace físico multiplicado por el número de saltos de la ruta, y en caso de que la ruta candidata sea de coste inferior, entonces se migra el enlace virtual y se liberan los recursos de la primera ruta física.

Preferentemente se escoge como nodo principal n ₀ de la red virtual el nodo de dicha red virtual con mayores requerimientos de capacidad de CPU y ancho de banda de sus enlaces y la numeración de los restantes nodos virtuales a asignar se realiza consecutivamente en orden decreciente de requerimientos de capacidad de CPU y ancho de banda de sus enlaces. En el proceso de asignación de nodos y enlaces virtuales se utiliza, opcionalmente, la técnica de División de Caminos (Path Splitting).

Los nodos físicos móviles utilizan un protocolo de comunicación que comprende, al menos, alguno de los siguientes mensajes:

• Un mensaje de asignación, que se utiliza para notificar desde un nodo físico móvil al resto de nodos físicos móviles la asignación de un nuevo nodo virtual y el valor de sus recursos actualizado;

• Un mensaje de solicitud, que contiene los recursos requeridos en la solicitud de alojamiento y el nodo virtual que se debe asignar al nodo físico móvil destino de dicho mensaje de solicitud;

• Un mensaje de error de alojamiento, que se utiliza para notificar un error durante el proceso de alojamiento de una red virtual debido a la escasez de recursos en un nodo físico móvil o en sus enlaces físicos donde dicho mensaje de error de alojamiento se envía a todos los nodos físicos móviles que tuvieran ya asignado un nodo virtual o formaran parte de un enlace virtual de dicha red virtual;

• Un mensaje de error por movilidad, que se envía desde un nodo físico móvil cuando se rompe uno de sus enlaces físicos que tiene un enlace virtual asignado, hasta el nodo físico extremo del enlace virtual afectado;

• Un mensaje de reasignación, que se envía desde un nodo físico móvil que cambia de celda de localización, y que tiene asignado un nodo virtual con requerimientos de localización, hasta un nodo físico ubicado en la celda abandonada, donde dicho mensaje de reasignación contiene información para solicitar un nuevo enlace virtual a los nodos virtuales vecinos;

• Mensaje de migración, que se envía a una pluralidad de nodos físicos móviles comprendidos en una nueva ruta física candidata a sustituir una asignación actual de enlace virtual, por motivos de optimización.

• Mensaje de liberación de migración, que se envía desde un nodo físico que tiene asignado un nodo virtual, como respuesta a un mensaje de migración previo, para liberar la ruta física de mayor coste.

En otro aspecto de la presente invención se proporciona un sistema que comprende medios adaptados para llevar a cabo el método descrito anteriormente. Finalmente, se proporciona un programa informático que comprende medios de código de programa informático adaptados para realizar las etapas del método descrito anteriormente, cuando dicho programa se ejecuta en un ordenador, un procesador de señal digital, una disposición de puertas de campo programable, un circuito integrado de aplicación específica, un microprocesador, un microcontrolador, y cualquier otra forma de hardware programable.

BREVE DESCRIPCION DE LOS DIBUJOS

Con objeto de ayudar a una mejor comprensión de las características del invento de acuerdo con un ejemplo preferente de realización práctica del mismo y para complementar esta descripción, se acompaña como parte integrante de la misma un juego de dibujos, cuyo carácter es ilustrativo y no limitativo. En estos dibujos:

La figura 1 muestra un escenario de realización de la invención, donde se ilustra una red de comunicaciones que comprende una pluralidad de nodos físicos móviles y una red virtual con una pluralidad de nodos virtuales que solicita ser alojada en dicha red de comunicaciones.

La figura 2 muestra un ejemplo de asignación de enlaces virtuales a rutas físicas mediante la técnica de División de Caminos (en inglés, Path Splitting).

La figura 3 muestra un ejemplo de la numeración propuesta para los nodos virtuales de la red virtual.

La figura 4 muestra el intercambio de mensajes entre los nodos de la red durante la reasignación de un nodo virtual, con requisitos de localización, en un nuevo nodo físico móvil cuando el nodo físico móvil que lo alojaba cambia de celda de localización.

La figura 5 muestra el intercambio de mensajes entre los nodos de la red durante la reasignación de un enlace virtual a una nueva ruta física cuando un nodo físico móvil detecta la ruptura del enlace físico que alojaba dicho enlace virtual.

La figura 6 muestra la migración de un enlace virtual a una nueva ruta física cuando transcurrido un determinado intervalo de tiempo se detecta una ruta física con un menor coste asociado que la ruta física actual. DESCRIPCIÓN DETALLADA DE LA INVENCIÓN

La presente invención proporciona un sistema y método de asignación de recursos virtuales orientado a redes AdHoc móviles MANets, del inglés Mobile AdHoc Networks) que minimiza los problemas derivados de la movilidad y la pérdida de enlaces físicos. Se dota a los operadores de red de la posibilidad de solicitar una localización geográfica aproximada de sus nodos virtuales mediante la división en celdas de la superficie cubierta por la infraestructura física. Se presenta un protocolo de asignación distribuido que se adecúa a redes compuestas por nodos de similares características donde la gestión es compartida por todos ellos, como ocurre en las redes MANets. Si bien el protocolo minimiza los efectos de la movilidad de los nodos del sustrato físico durante el proceso de asignación, debido al desconocimiento a priori de dicha movilidad y a su aleatoriedad se producen continuas rupturas de los enlaces físicos y cambios de celda de localización de los propios nodos físico, los cuales afectan al correcto funcionamiento de las VNets. Para solucionar este problema el sistema utiliza dos algoritmos de reasignación de recursos que permiten reducir la cantidad de VNets cuya correcta ejecución se interrumpe debido a los problemas de movilidad mencionados.

El escenario de realización de la invención mostrado en la figura 1 , consiste en una red de /V ^s nodos físicos móviles 1 1 situados en una infraestructura de tamaño (x, y) dividida en diferentes celdas de localización 12. Se caracteriza el sustrato como un grafo ponderado no dirigido G ^s = (N ⁸ , L ^s ), donde /V ^s representa el conjunto de nodos físicos y L ^s representa el conjunto de enlaces físicos disponibles en cada momento, puesto que estos se establecen y se pierden de manera dinámica. Cada enlace del sustrato P e L ^s 13 se caracteriza por su ancho de banda bw(P). Cada nodo del substrato rf e /V ^s se caracteriza también por sus recursos de CPU, su localización en el mapa, su factor de movilidad a(rf) y su velocidad de movimiento s(n ^s ).

Las entradas al sistema propuesto son las peticiones de alojamiento de VNets, que son mapeadas o rechazadas dependiendo del estado de la red y los recursos disponibles en el momento concreto de la llegada. Se modela cada solicitud de alojamiento de VNet como un grafo ponderado no dirigido G ^v = (N ^v , L ^v ), donde N ^v representa el conjunto de nodos virtuales y L ^s representa el conjunto de enlaces virtuales solicitados. Cada rf e N ^v 14 se caracteriza por su capacidad de CPU y su localización; y cada f e L ^v 15 se caracteriza por su capacidad de ancho de banda. Las peticiones llegan al sistema en un instante de tiempo a priori desconocido e indican su tiempo de duración. Los valores posibles del factor de movilidad de los nodos físicos móviles son:

• 0 - Para nodos estáticos durante un periodo de tiempo;

• 1 - Para nodos que recientemente han comenzado a moverse o detenerse;

• 2 - Nodos en movimiento durante un periodo de tiempo.

Se obtiene el índice de movilidad de un nodo como el producto del estado del mismo y la velocidad de movimiento.

Se define † como la función que representa el conjunto de enlaces físicos asociados a un nodo físico, P† n ^s .

La ecuación que permite cuantificar los recursos, H(n ^s ), de cada nodo físico se muestra en la ecuación 1 .

∑bw (l ^s )

H (n ^s ) ^~

l + a(n ^s ) - s(n ^s )

Como se puede observar, los recursos de un nodo vienen dados por la capacidad de ancho de banda restante de sus interfaces, el factor de movilidad y la velocidad de movimiento. El criterio que se aplica busca el nodo rf con un valor de H(n ^s ) máximo, es decir, valores elevados en el numerador, y valores bajos en el denominador. De esta manera, la elección de aquellos nodos en movimiento se ve penalizada.

El método utilizado se fundamenta en el intercambio de mensajes entre nodos vecinos del sustrato físico de manera que el algoritmo definido indica los pasos a realizar ante la ocurrencia de un suceso o la recepción de un mensaje. Mediante el intercambio de dichos mensajes, el sistema asigna los nodos virtuales rf y sus respectivos enlaces virtuales f a los nodos físicos rf y enlaces físicos P que componen la infraestructura física y repara la asignación inicial en caso de fallo por movilidad durante el tiempo de vida de la red virtual.

Si en un instante aleatorio de tiempo y para unos recursos específicos de la infraestructura, una nueva solicitud de alojamiento de VNet llega a un nodo cualquiera de la red física, este nodo consulta en su tabla de rutado el nodo físico con mayor cantidad de recursos y le retransmite la solicitud de alojamiento, de forma que dicho nodo comienza el proceso de asignación de recursos. Si bien los pasos a realizar definidos por el algoritmo son idénticos en todos los nodos, el nodo central almacena en memoria la solicitud de VNet hasta que ésta se completa por si ha de ser re-mapeada más adelante debido a un error causado por la movilidad.

Aquel nodo físico al cual le llega una nueva solicitud de mapeo comprueba en primer lugar si es capaz de soportar la CPU solicitada por el nodo virtual y los anchos de banda de los enlaces virtuales. De ser así, y mientras existan más nodos virtuales a mapear, el nodo reenvía la petición a los nodos físicos con mayor cantidad de recursos, y, que cumplan los requisitos de localización, en casa de solicitarse, encargados de alojar los vecinos virtuales de dicho nodo. Si alguno de los nodos físicos involucrados en el proceso no puede soportar la petición debido a la escasez de recursos, dicho nodo envía un mensaje de error hacia atrás de manera que el resto de nodos puede liberar la petición. Una vez completado el proceso de alojamiento, los nodos físicos alojan la VNet hasta cumplir el tiempo solicitado por el operador de red, siempre y cuando ésta no deba ser liberada debido a problemas derivados de la movilidad que no se puedan reparar mediante los algoritmos de reasignación de recursos. Preferentemente, si se permite la solicitud, el método implementa la conocida técnica de División de Caminos (en inglés, Path Splitting) que se muestra en la figura 2. Para ello se considera que los diferentes nodos que conforman la infraestructura física 21 disponen de varios enlaces físicos 22. De esta forma, si en un momento dado un nodo virtual 23 que debe asignar un enlace virtual de cierto ancho de banda hacia otro nodo virtual de la red 24 no dispone de dicho ancho de banda en ninguno de sus enlaces físicos, el enlace virtual se divide en varios caminos físicos, de forma que la suma de los anchos de banda de todos los caminos físicos tiene como resultado el ancho de banda solicitado por el operador de red para su enlace virtual. En el ejemplo de la figura se muestra un caso en que el nodo central virtual 23 necesita comunicar con el nodo destino virtual 24 con un ancho de banda de 40 unidades. En el caso de que los nodos no dispongan de varios enlaces físicos no existe mayor problema en la ejecución del algoritmo de asignación, simplemente se trata de un mapeo más restrictivo y la cantidad de VNets alojadas en el sistema es, probablemente, menor. Es decisión del operador decidir si sus enlaces virtuales permiten o no División de Caminos puesto que esta tecnología podría no ser interesante dependiendo de los servicios ofertados. En cualquier caso mediante la asignación de nodos virtuales en los nodos físicos con mayor cantidad de recursos se consigue balancear la utilización de la red y facilitar el alojamiento de VNets que no permitan Path Splitting.

Si bien se permite cualquier tipo de topología a ser solicitada, la numeración de nodos virtuales se realiza, como se muestra en la figura 3, asignando como nodo central η ^ν ₀ Ζλ el nodo que demanda la mayor cantidad de recursos y siguiendo un orden ascendente completando anillos de vecinos rf^ 32, n ^v ₂ 33 y n ^v ₃ 34. En el caso de que una petición no pueda ser alojada ésta se almacena en la memoria del nodo central n ^v ₀ 31 que inicio el mapeo de la petición para un futuro intento donde las características de la red sean diferentes, o es descartada, después de un número determinado de intentos, y por tanto eliminada del sistema.

Puesto que se trata de una red MANet, se hace uso de un protocolo de rutado proactivo que permite conocer el estado de toda la red de manera actualizada. Además de la ruta, el protocolo proporciona la información de CPU, ancho de banda y localización de cada nodo físico.

Tal como se ha comentado anteriormente, la principal innovación propuesta por el método es la utilización de una red MANet como infraestructura de mapeo de las VNets. Esto implica que movimientos de los nodos físicos pueden causar rupturas de enlaces o cambios de células de localización que afectan a las VNets alojadas, siendo por tanto necesario un método de adaptación a la nueva situación de la infraestructura. Dos son las situaciones de reasignación consideradas:

• Node Remapping como se muestra en la figura 4, en el instante en que, debido al movimiento, un nodo físico 41 cambia de celda de localización 42 comprueba si dispone de alguna VNet asignada con requerimientos de localización. Si es así, además de enviar los mensajes de notificación de esta situación 43 a los nodos vecinos virtuales 44, para la liberación de las rutas afectadas, selecciona un nodo válido 45 y le envía un mensaje 46 indicando la información necesaria para reasignar los enlaces afectados. Los nodos vecinos 44 informados de la situación entran en estado de reparación, considerando la VNet como no recuperable si tras un tiempo no han recibido un mensaje 47 indicando la información necesaria para reasignar sus enlaces afectados.

• Link Remapping como se puede observar en la figura 5, en el instante en que, debido al movimiento, los nodos físicos 51 y 52 detectan la ruptura de un enlace 53, estos nodos 51 y 52 comprueban si dicho enlace se encuentra asignado a alguna VNet. En caso de que así sea, envían mensajes 54 notificando esta situación a los extremos involucrados en la asignación 55 y 56. Puesto que ambos extremos de la ruta física 51 y 52 se percatan del error, y con el objetivo de evitar problemas debido a la duplicidad de mensajes para asignar nuevos enlaces y/o nodos, solo aquel nodo virtual con identificador numérico más bajo 55 trata de reparar el enlace mediante el envío de un nuevo mensaje de asignación 57. El otro extremo 56 por su parte entra en un estado de reparación de forma que si transcurrido un tiempo no se ha recibido un mensaje de reasignación 57 para el enlace virtual dañado, se considera la VNet como no recuperable y se procede a su liberación mediante mensajes de error.

A continuación se resume el objetivo de los mensajes empleados en el algoritmo para alojar y gestionar las VNets de manera distribuida entre todos los nodos que componen la MANet:

• Mapping message: similar al clásico mensaje Helio de rutado, este mensaje notifica al resto de nodos físicos la asignación de un nuevo nodo virtual y el valor de los recursos actualizado.

• Request message: se trata del mensaje utilizado para completar el alojamiento de la VNet. Contiene los recursos solicitados por el operador de red además del nodo virtual que ha de ser asignado al nodo destino del mensaje.

· Embedding Error message: notifica un error durante el proceso de alojamiento debido a la escasez de recursos en nodos extremos o intermedios de la ruta física. El mensaje se envía hacia atrás de forma que se complete la liberación en todos los nodos involucrados. • Mobility Error message 54: el nodo 51 , 52 que se percata de la ruptura de un enlace físico 53, envía este mensaje 54 al nodo extremo 55, 56 del enlace virtual afectado de manera que este pueda realizar las operaciones de reasignación oportunas. Puesto que el enlace puede encontrarse dividido en varias rutas físicas, cada nodo retransmite el mensaje de error por todas sus interfaces excepto por aquella donde lo recibió.

• Reallocate message 46: en el momento en que un nodo físico al cual ha sido asignado un nodo virtual 41 con restricción de localización cambia de célula de localización 42, este envía un mensaje de realojamiento 46 al nodo físico seleccionado en la célula correcta 45 con la información necesaria para solicitar un nuevo enlace virtual a los nodos virtuales vecinos.

Tal como se explicó anteriormente, los recursos de los nodos de la infraestructura física variarán debido a la movilidad y la presencia de VNets en el sistema. Con el propósito de optimizar los recursos de la red y reducir el coste que supone el alojamiento de los recursos virtuales al gestor de la infraestructura el método propuesto implementa la técnica conocida como migración, mostrada en la figura 6. Cada cierto tiempo periódico, y para aquellas VNets cuyo tiempo de duración sea mayor que un umbral definido, los nodos virtuales tratarán de migrar el enlace virtual operativo a otra ruta física de menor coste asociado, C(lv).

C(l ^v ) =∑bw(l ^s ) - hops (p)

Como podemos observar en la ecuación, definimos el coste de mapear un enlace virtual en el sustrato físico como el sumatorio del ancho de banda bw(l ^s ) multiplicado por el número de saltos hops(p) de todos los enlaces físicos I ^s , que conforman el enlace virtual .

Para llevar a cabo dicha migración el protocolo de comunicación entre los nodos físicos incluye también los siguientes mensajes:

· Migration message: permite el intento de migración de un enlace virtual.

• Migration Reléase message: el nodo virtual que recibe un mensaje de migración responde mediante este mensaje para liberar la asignación previa de recursos de aquellos nodos envueltos en la ruta física no seleccionada en la migración debido a su mayor coste.

En la figura 6 se puede observar la técnica de migración de una VNet a otra ruta física de menor coste. Así en el instante Tn, la VNet es asignada del modo indicado en la parte superior 61 , haciendo uso de Path Spiitting, y, en el instante Tn+k, tras la liberación de ancho de banda en algunos de los enlaces físicos de la red de comunicaciones, debido al desalojo de otras redes virtuales, la VNet migra a una ruta de menor coste y es asignada como se indica en la parte inferior 62 de la figura.