OpenFlow rule placement in carrier backhaul networks for multicast applications

Amado, Rafael George (2022). OpenFlow rule placement in carrier backhaul networks for multicast applications. Mémoire de maîtrise électronique, Montréal, École de technologie supérieure.

Prévisualisation

PDF Télécharger (770kB) | Prévisualisation

Résumé

Today, mobile consumers increasingly use multicast applications (e.g., online gaming, Virtual/ Augmented Reality (VR/AR), social media) to stream video through carrier networks. Thanks to its flexibility, OpenFlow-enabled Software-defined networking (SDN) allows the enforcement of high-level policies and support end-to-end network-slicing, which are substantial for these applications’ requirements. A higher abstraction level hides the complexity of the network devices and exposes a simple interface to operators. However, this flexibility brings the complex task of allocating the low-level rules in the actual network, which requires handling constraints such as limited available memory on the switches and the capacity of the links. Due to legacy switch models, prior work focuses only on Flow Table entries that cannot efficiently support multicast traffic from one device (or server) to many devices across the network.

Our approach is to leverage the use of Group Tables, which is recently introduced in the OpenFlow 1.1 specification, to support multicast flows and save switch memory. Traffic to multiple destinations can be aggregated to match a single Flow Table entry per switch, saving significant link resources. The controller has the challenging task of calculating where to efficiently install Flow and Group Tables entries (rules) in the network.

In this thesis, we optimize rule placement in resource-constrained Openflow networks for both unicast and multicast flows. We formulate our model as an Integer Nonlinear Programming (INLP) problem, considering the network’s limitations, such as the memory capacity of both Flow and Group Tables and the available link bandwidth. The objective is to maximize the traffic delivered to the destinations under resource constraints. To solve this model, we use a solver (Gurobi) to obtain the optimal allocation and propose two algorithms to calculate the rule allocation in polynomial time: a greedy approach named OpenFlow Multicast Allocation Algorithm (OFMAA) and an improved version based on Steiner-tree (ST-OFMAA).

Our experimental results on three different topologies show that Group Table is a key factor in reducing memory usage across the network. Our solution can support a higher number of flows than the solutions proposed by prior work, which do not consider Group Tables, by reducing both the link usage by up to 30% and the number of flow entries needed to deliver the traffic to destinations by 22%.

Titre traduit

Placement des règles OpenFlow dans les réseaux de liaison de l’opérateur pour les applications de multidiffusion

Résumé traduit

Aujourd’hui, les consommateurs mobiles utilisent de plus en plus les applications de multidiffusion (par exemple, les jeux en ligne, la réalité virtuelle/augmentée (RV/RA), les médias sociaux) pour diffuser des vidéos via les réseaux des opérateurs. Grâce à sa flexibilité, la mise en réseau définie par logiciel (SDN) compatible OpenFlow permet l’application de politiques de haut niveau et prend en charge le découpage du réseau de bout en bout, ce qui est substantiel pour les exigences de ces applications. Un niveau d’abstraction plus élevé masque la complexité des périphériques réseaux et expose une interface simple aux opérateurs. Cependant, cette flexibilité implique la tâche complexe d’allouer les règles de bas niveau dans le réseau réel, ce qui nécessite de gérer des contraintes telles que la mémoire disponible limitée pour les commutateurs et la capacité des liaisons. En raison des modèles de commutateurs hérités, les travaux antérieurs se concentrent uniquement sur les entrées de la table de flux qui ne peuvent pas prendre en charge efficacement le trafic multidiffusion d’un périphérique (ou serveur) vers de nombreux périphériques sur le réseau.

Notre approche consiste à tirer parti de l’utilisation des Tables de Groupe, récemment introduites dans la spécification OpenFlow 1.1, pour prendre en charge les flux de multidiffusion et économiser la mémoire du commutateur. Le trafic vers plusieurs destinations peut être agrégé pour correspondre à une seule entrée de Table de Flux par commutateur, ce qui permet d’économiser des ressources de liaison importantes. Le contrôleur a la tâche difficile de calculer où installer efficacement les entrées (règles) des Tables de Flux et de Groupe dans le réseau.

Dans cette thèse, nous optimisons le placement des règles dans les réseaux Openflow à ressources limitées pour les flux monodiffusion et multidiffusion. Nous formulons notre modèle comme un problème de Programmation Non-linéaire en Nombres Entiers (PNLNE), en tenant compte des limites du réseau, telles que la capacité de mémoire des Tables de Flux et de Groupe et la bande passante de liaison disponible. L’objectif est de maximiser le trafic livré aux destinations sous contraintes de ressources. Pour résoudre ce modèle, nous utilisons un solveur (Gurobi) pour obtenir l’allocation optimale et proposons deux algorithmes pour calculer la règle d’allocation en temps polynomial : une approche gloutonne nommée OpenFlow Multicast Allocation Algorithm (OFMAA) et une version améliorée basée sur Steiner-tree (ST-OFMAA).

Nos résultats expérimentaux sur trois topologies différentes montrent que la Table de Groupe est un facteur clé pour réduire l’utilisation de la mémoire sur le réseau. Notre solution peut prendre en charge un nombre de flux plus élevé que les solutions proposées par les travaux antérieurs, qui ne tiennent pas compte des tables de groupe, en réduisant à la fois l’utilisation des liens jusqu’à 30% et le nombre d’entrées de flux nécessaires pour acheminer le trafic vers les destinations de 22%.

Type de document:	Mémoire ou thèse (Mémoire de maîtrise électronique)
Renseignements supplémentaires:	"Thesis presented to École de technologie supérieure in partial fulfillment of a master’s degree with thesis in in telecommunication networks". Comprend des références bibliographiques (pages 39-43).
Mots-clés libres:	réalité virtuelle, réalité augmentée, réseaux sociaux, réseaux définis par logiciel, optimisation des politiques de routage, placement de règles de multidiffusion, openflow, table de groupe
Directeur de mémoire/thèse:	Directeur de mémoire/thèse Cheriet, Mohamed
Codirecteur:	Codirecteur Nguyen, Kim Khoa
Programme:	Maîtrise en ingénierie > Génie
Date de dépôt:	27 mai 2022 13:44
Dernière modification:	27 mai 2022 13:44
URI:	https://espace.etsmtl.ca/id/eprint/3000

Gestion Actions (Identification requise)

Dernière vérification avant le dépôt