Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Les terminaux mobiles (smartphones et tablettes) sont devenus les terminaux les plus populaires pour accéder à Internet. Cependant, l'écosystème incluant les terminaux mobiles est maintenu opaque à cause des intérêts financiers des différents acteurs : les concepteurs des systèmes d'exploitation et des applications, les opérateurs des "stores", et les FAI. Cette opacité est renforcée par le peu de contrôle qu'ont les utilisateurs sur les informations échangées par leur terminal. Pour résoudre ce problème d'opacité et de manque de contrôle, on a créé une plate-forme, Meddle, qui utilise la redirection de trafic des terminaux mobiles pour analyser et modifier ce trafic. Contrairement aux solutions qui nécessitent d'être implémentées sur le terminal, Meddle combine les techniques de VPN et de "middlebox" pour offrir une solution indépendante de l'OS, du FAI et de l'accès radio. On a utilisé Meddle pour des expérimentations contrôlées et pour une étude utilisateurs approvée par un IRB. On a observé que des applications populaires sous iOS et Android exposaient des informations personnelles dans le traffic réseau en clair et chiffré. On a ensuite exploité Meddle pour prévenir ces fuites d'informations privées. On a également utilisé Meddle pour étudier les caractéristiques réseaux du trafic vidéo sur Internet. On a trouvé que ce trafic dépend fortement du type de terminal, de l'application utilisée pour regarder la vidéo (application native ou navigateur Web) et du contenant (HTML5, Flash, Silverlight). Ce résultat montre qu'un changement dans le terminal, l'application ou le contenant peut avoir un impact important sur le réseau. / Mobile devices are increasingly becoming the primary device to access the Internet. Despite this thriving popularity, the current mobile ecosystem is largely opaque because of the vested monetary interests of its key players: mobile OS providers, creators of mobile applications, stores for mobile applications and media content, and ISPs. This problem of opaqueness is further aggravated by the limited control end-users have over the information exchanged by their mobile devices. To address this problem of opaqueness and lack of control, we create a user-centric platform, Meddle, that uses traffic indirection to diagnose mobile devices. Compared to an on-device solution, Meddle uses two well-known technologies, VPNs and middleboxes, and combines them to provide an OS, ISP, and access technology agnositic solution. We use Meddle for controlled experiments and an IRB approved study, and ob- served that popular iOS and Android applications leak personally identifiable information in the clear and also over SSL. We then use Meddle to prevent further leaks. We also use our platform to detail the network characteristics of video streaming services, the most popular Web-service in the current Internet. We observe that the network traffic characteristics vary vastly with the device (mobile or desktop), application (native applications and also between individual desktop browsers), and container (HTML5, Flash, and Silverlight). This observation is important because the increased adoption of one application or streaming service could have a significant impact on the network traffic, for example, an increase in the usage of mobile applications.

Homologie simpliciale est un outil très efficace pour accéder à des informations importantes sur la topologie des réseaux sans fil, tels que : la couverture et la connectivité. Dans cette thèse, nous modélisons le réseau sans fil comme un déploiement aléatoire des cellules. Tout d’abord, nous introduisons un algorithme pour construire le complexe de Cech, qui décrit exactement la topologie du réseau. Ensuite, ˇ le complexe de Cech est utilisé dans des applications avancées. La première application est d’économiser ˇ l’énergie de transmission pour les réseaux sans fil. Cette application non seulement maximise la couverture de le réseau, mais réduit également la puissance de transmission. En même temps, la couverture et la puissance de transmission sont optimisées. La deuxième application est pour équilibrer la charge de trafic dans les réseaux sans fil. Cette application contrôle la puissance de transmission de chaque cellule dans le réseau, toujours sous contrainte de couverture. Avec la puissance d’émission contrôlée, les utilisateurs sont redirigés vers des cellules de charge plus faibles. Par conséquent, la charge du trafic est répartie entre lesdifférentes cellules. / Simplicial homology is a useful tool to access important information about the topology of wireless networks such as : coverage and connectivity. In this thesis, we model the wireless network as a random deployment of cells. Firstly, we introduce an algorithm to construct the Cech complex, which describes exactly the topology of the network. Then, the Cech complex is used in further applications. The first application is to save transmission power for wireless networks. This application not only maximizes the coverage of the network but also minimizes its transmission power. At the same time, the coverage and the transmission power are optimized. The second application is to balance the traffic load in wireless networks. This application controls the transmission power of each cell in the network, always under the coverage constraint. With the controlled transmission power, the users are redirected to connect to the lower traffic load cells. Consequentially, the balanced traffic load is obtained for the network.

La coloration de graphes est un problème central de l'optimisation combinatoire. C'est un domaine très attractif par ses nombreuses applications. Différentes variantes et généralisations du problème de la coloration de graphes ont été proposées et étudiées. La coloration d'arêtes d'un graphe consiste à attribuer une couleur à chaque arête du graphe de sorte que deux arêtes ayant un sommet commun n'ont jamais la même couleur, le tout en utilisant le moins de couleurs possibles. Dans la première partie de cette thèse, nous étudions le problème de la coloration d'arêtes ℓ-distance, qui est une généralisation de la coloration d'arêtes classique. Nous menons une étude combinatoire et algorithmique du paramètre. L'étude porte sur les classes de graphes suivantes : les chaines, les grilles, les hypercubes, les arbres et des graphes puissances. Le paramètre de la coloration d'arêtes ℓ-distance permet de modéliser des problèmes dans des réseaux assez grands. Cependant, avec la multiplication du nombre de nœuds, les réseaux sont de plus en plus vulnérables aux défaillances (ou pannes). Dans la deuxième partie, nous nous intéressons aux algorithmes tolérants aux pannes et en particulier les algorithmes auto-stabilisants. Nous proposons un algorithme auto-stabilisant pour la coloration propre d'arêtes. Notre solution se base sur le résultat de vizing pour utiliser un minimum de couleurs possibles. Par la suite, nous proposons un algorithme auto-stabilisant de clustering destine a des applications dans le domaine de la sécurité dans les réseaux mobiles Ad hoc. La solution que nous proposons est un partitionnement en clusters base sur les relations de confiance qui existent entre nœuds. Nous proposons aussi un algorithme de gestion de clés de groupe dans les réseaux mobiles ad hoc qui s'appuie sur la topologie de clusters préalablement construite. La sécurité de notre protocole est renforcée par son critère de clustering qui surveille en permanence les relations de confiance et expulse les nœuds malveillants de la session de diffusion.

Les réseaux mobiles 4G basés sur la norme LTE (Long Term Evolution), sont des réseaux tout IP. Les différents problèmes de transport IP comme le retard, la gigue et la perte despaquets peuvent fortement dégrader la qualité des communications temps réel telles que la téléphonie. Les opérateurs ont mis en oeuvre des mécanismes d’optimisation du transport de la voix dans le réseau afin d'améliorer la qualité perçue. Cependant, les algorithmes propriétaires de gestion de la qualité dans les terminaux ne sont pas spécifiés dans les standards. Dans ce contexte, nous nous intéressons aux mécanismes d'adaptation de média, intégrés dans les terminaux afin d'améliorer la qualité d’expérience (QoE). En particulier, nous évaluons de manière expérimentale des métriques QoE de la voix sur LTE (VoLTE) en utilisant une méthode de test standardisée. Nous proposons d’améliorer la méthode de test et discutons la manière dont cette méthode peut être étendue pour évaluer les performances du buffer de gigue. Nous évaluons également de manière expérimentale la qualité de WebRTC dans différentes conditions radios en utilisant un réseau réel. Nous évaluons l'impact du buffer de gigue et de la variation du débit sur la qualité mesurée. Pour améliorer la robustesse des codecs contre la perte de paquets, nous proposons d’utiliser une redondance simple au niveau applicatif. Nous implémentons cette redondance pour le codec EVS (Enhanced Voice Service) et nous évaluons ses performances. Enfin, nous proposons un protocole de signalisation qui permet d’envoyer des requêtes de redondance au cours d’une communication afin d’activer ou désactiver celle-ci dynamiquement. / Fourth-generation mobile networks, based on the Long Term Evolution (LTE) standard, are all- IP networks. Thus, mobile telephony providers are facing new types of quality degradations related to the voice packet transport over IP network such as delay, jitter and packet loss. These factors can heavily degrade voice communications quality. The real-time constraint of such services makes them highly sensitive to delay and loss. Network providers have implemented several network optimizations for voice transport to enhance perceived quality. However, the proprietary quality management algorithms implemented in terminals are left unspecified in the standards. In this context, we are interested in media adaptation mechanisms integrated in terminals to enhance the overall Quality of Experience (QoE). In particular, we experimentally evaluate Voice over LTE (VoLTE) QoE metrics such as delay and Mean Opinion Score (MOS) sing a standardized test method. We propose some enhancements to the actual test method and discuss how this method can be extended to evaluate de-jitter buffer performance. We also experimentally evaluate WebRTC voice quality in different radio conditions using a realLTE test network. We evaluate the impact of jitter buffer and bit rate variations on the measured quality. To enhance voice codec robustness against packet loss, we propose a simple application layer redundancy. We implemented it for the Enhanced Voice Service (EVS) codec and evaluate it. Finally, we propose a signaling protocol that allows sending redundancy requests during a call to dynamically activate or deactivate the redundancy mechanism.

Le passage à l’échelle des protocoles de routage est un des problèmes les plus critiques pour les réseauxmobiles sans fil à grande envergure. Dans ce cadre, le concept de clusterisation peut être mis à profit dans lafonction de routage afin d’améliorer les performances de ces réseaux. En premier lieu, cette thèse présentenotre algorithme de clusterisation à 1-saut alpha-SSCA (α-Stability Structure Clustering Algorithm) qui apour objectif d’améliorer la stabilité de la structure des clusters. Un algorithme générique de clusterisationà K-sauts est également proposé en ayant le même but de stabilité visé par alpha-SSCA tout en réduisant lenombre de clusters générés et en étant indépendant de la métrique d’élection des cluster-heads. Ensuite, nousprésentons notre proposition d’un protocole de routage à état des liens des clusters qui exploite les apports denotre mécanisme de clusterisation α-SSCA. Ce protocole, appelé CLSR (Cluster-based Link State Routing),vise à réduire le trafic de contrôle afin d’améliorer les performances du réseau à large échelle. Nous avonsproposé aussi une version hiérarchique du protocole CLSR. Ce protocole de routage introduit une hiérarchiedans la structure des clusters qui permet de réduire le nombre de clusters en groupement des clusters prochesdans un même cluster. L’objectif principal de ce protocole hiérarchique est d’améliorer la scalabilité de CLSRquand le nombre de noeuds dans le réseau augmente considérablement. / Scalability is one of critical challenges for routing protocols in large scale mobile wireless networks. In thiscontext, clustering technique seems a promising approach to overcome the scalability problem. First, we proposea one hop clustering algorithm, alpha-SSCA (alpha-Stability Structure Clustering Algorithm), whichaims to improve the stability of the clusters structure. Second, we present a proposal of a generic K-hopsclustering algorithm which is independent of the metrics used to elect cluster-heads. The main contributionof this last algorithm is to enhance the stability of the clusters structure while reducing the number of clusters.Clustering mechanism is introduced in our proposed routing protocol CLSR (Cluster-based Link StateRouting) in order to reduce the control overhead. The main objective of CLSR is to take profit of the stablestructure of clusters to enhance the network scalability.We propose also a second proactive link-state protocolwhich is based on hierarchical clustering. This protocol makes use of hierarchical clustering to more reducethe routing overhead.

Les graphes dynamiques sont un outil de plus en plus utilisé dans des contextes variés où il s'avère nécessaire de modéliser des environnements changeants ou incertains. Les modèles aujourd'hui proposés sont dédiés à ces applications précises. Il n'existe pas de modèle général reprenant, hors de tout contexte applicatif, ces caractéristiques. D'autre part la résolution de problèmes liés à ces environnements dynamiques et incertains est problématique. Nous proposons, ici, la formalisation d'un modèle général de graphe dynamique. <br /><br />Nous étudions la résolution de problèmes dans ces graphes à l'aide de méthodes inspirées de mécanismes d'intelligence collective. <br /><br />Les modèles proposés sont validés dans le contexte applicatif des réseaux mobiles ad hoc. Une approche originale de construction et de maintien de chemins de communication sous plusieurs contraintes est proposée. Le problème de la construction et du maintien d'une forêt couvrante dans un réseau mobile ad hoc est également étudié.

Conçus à l'origine pour le trafic best-effort, les réseaux mobiles ad hoc (MANET) sont de plus en plus amenés à acheminer le trafic des applications imposant des contraintes de qualité de service (QoS). Les solutions pour le routage à QoS dans les MANET ont généralement été proposées comme des extensions optionnelles des protocoles best-effort. Par exemple, les liaisons y sont toujours considérées comme symétriques au sens de la connectivité, alors qu'elles ne le sont évidemment pas au sens de la QoS. De plus, dans les solutions proposées dans le cadre du protocole proactif Optimized Link State Routing (OLSR), l'effort algorithmique pour la QoS se fait souvent au détriment de l'optimisation de la diffusion qui est pourtant une des activités les plus consommatrices de ressources. L'approche proposée dans cette thèse consiste à intégrer les aspects liés à la QoS dans la représentation des MANET dès la conception du protocole de routage. Prenant pour cible le protocole OLSR, nous proposons une formulation du problème de la sélection des relais multipoints (MPR) sous forme de programme mathématique pour permettre à la fois l'optimisation de la diffusion et la prise en compte des paramètres de la qualité de service. Une heuristique proposée pour réaliser la sélection des MPR indépendamment du nombre et du type de métriques est également proposée. L'heuristique appliquée à quatre métriques ainsi que les autres mécanismes proposés sont ensuite intégrés dans OLSR. Les évaluations ciblant une application à fortes contraintes de qualité de service en établissent les performances aussi bien en environnement ouvert qu'en agglomération.

Lors d'une transmission vidéo sur les réseaux mobiles, les données doivent être efficacement comprimées pour s'adapter à la bande passante réduite du support. Cependant, plus un flux multimédia est comprimé, plus il est sensible aux erreurs de transmission. Pour garantir un signal exempt d'erreur à l'entrée du décodeur source, plusieurs mécanismes sont incorporés dans le récepteur. Ces techniques consistent principalement à retransmettre les paquets erronés et/ou à rajouter des redondances aux données transmises. Ces méthodes sont efficaces, mais entraînent une consommation excessive de ressources. Récemment, le concept de décodage conjoint a été proposé. Il consiste à utiliser les redondances inhérentes contenues dans les informations transmises pour améliorer la qualité du décodage multimédia. Dans cette thèse, nous explorons cet axe et proposons un nouveau schéma de décodage conjoint exploitant les propriétés sémantiques et syntaxiques du flux ainsi que les codes de détection d'erreurs (CRC) protégeant les paquets. Parallèlement, nous étudions les problématiques d'intégration des schémas de décodage conjoint dans les récepteurs traditionnels et nous montrons que de nombreuses modifications sont nécessaires. Nous proposons ensuite un principe universel permettant de résoudre simplement les difficultés en exploitant différemment la structure protocolaire. Ces techniques ont été testées en considérant une transmission vidéo H.264/AVC point-à-point sur un support WiFi. Les résultats obtenus ont confirmé l'intérêt du décodage robuste par une amélioration significative du bilan de liaison.

Selon l'Union Internationale des Télécommunications (UIT), la progression importante du nombre de téléphones mobiles à travers le monde a dépassé toutes les prévisions avec un nombre d'utilisateurs estimé à 6 Mds en 2011 dont plus de 75% dans les pays développés. Cette progression importante produit une pression forte sur les opérateurs de téléphonie mobile concernant les ressources radio et leur impact sur la qualité et le degré de service (GoS) dans le réseau. Avec des demandes différenciées de services émanant de différentes classes d'utilisateurs, la capacité d'identifier les types d'utilisateurs dans le réseau devient donc vitale pour l'optimisation de l'infrastructure et des ressources. Dans la présente thèse, une nouvelle approche de classification des utilisateurs d'un réseau cellulaire mobile est proposée, en exploitant les données du trafic réseau fournies par deux opérateurs de téléphonie mobile en Afrique du Sud. Dans une première étape, celles-ci sont décomposées en utilisant deux méthodes multi-échelles ; l'approche de décomposition en mode empirique (Empirical Mode Decomposition approach - EMD) et l'approche en Ondelettes Discrètes (Discrete Wavelet Packet Transform approach - DWPT). Les résultats sont ensuite comparés avec l'approche dite de Difference Histogram qui considère le nombre de segments de données croissants dans les séries temporelles. L'approche floue de classification FCM (Fuzzy C-means) est utilisée par la suite pour déterminer les clusters, ou les différentes classes présentes dans les données, obtenus par analyse multi-échelles et par différence d'histogrammes. Les résultats obtenus montrent, pour la méthode proposée, une séparation claire entre les différentes classes de trafic par rapport aux autres méthodes. La deuxième partie de la thèse concerne la proposition d'une approche d'optimisation des ressources réseau, qui prend en compte la variation de la demande en termes de trafic basée sur les classes d'abonnés précédemment identifiés dans la première partie. Une nouvelle approche hybride en deux niveaux pour l'allocation des canaux est proposée. Le premier niveau considère un seuil fixe de canaux alloués à chaque cellule en prenant en considération la classe d'abonnés identifiée par une stratégie statique d'allocation de ressources tandis que le deuxième niveau considère une stratégie dynamique d'allocation de ressources. Le problème d'allocation de ressources est formulé comme un problème de programmation linéaire mixte (Mixed-Integer Linear programming - MILP). Ainsi, une approche d'allocation par période est proposée dans laquelle un groupe de canaux est alloué de façon dynamique pour répondre à la variation de la demande dans le réseau. Pour résoudre le problème précédent, nous avons utilisé l'outil CPLEX. Les résultats obtenus montrent qu'une solution optimale peux être atteinte par l'approche proposée (MILP)