Dissertationen zum Thema „Embedding Network“

Pesquisas acadêmicas em virtualização de redes vêm sendo realizadas durante diversos anos, nos quais diferentes abordagens de alocação de redes virtuais foram propostas. Tais abordagens, no entanto, negligenciam requisitos operacionais importantes impostos por plataformas de virtualização. No caso de virtualização baseada em SDN/OpenFlow, um exemplo fundamental de tais requisitos operacionais é a disponibilidade de espaço de memória para armazenar regras em dispositivos OpenFlow. Diante dessas circunstâncias, argumentamos que a alocação de redes virtuais deve ser realizada com certo grau de conhecimento sobre infraestruturas físicas; caso contrário, após instanciadas, tais redes podem sofrer instabilidade ou desempenho insatisfatório. Considerando redes físicas baseadas em SDN/OpenFlow como um cenário importante de virtualização, propõe-se um arcabouço baseado na coordenação entre a alocação de redes virtuais e redes OpenFlow para realizar a instanciação de redes virtuais de forma adequada. A abordagem proposta desdobra-se nas seguintes contribuições principais: uma abstração de infraestruturas virtuais que permite que um requisitante represente os detalhes de seus requerimentos de rede de maneira aprofundada; um compilador ciente de privacidade que é capaz de pré-processar requisições com tal grau de detalhamento, ofuscando informações sensíveis e derivando requisitos operacionais computáveis; um modelo para a alocação de redes virtuais que visa a maximizar a viabilidade no nível físico. Resultados obtidos por meio de uma avaliação da nossa abordagem evidenciam que considerar tais requisitos operacionais, bem como computá-los de forma precisa, é imprescindível para garantir a “saúde” das redes virtuais hospedadas na plataforma de virtualização considerada.
Research on network virtualization has been active for a number of years, during which a number of virtual network embedding (VNE) approaches have been proposed. These approaches, however, neglect important operational requirements imposed by the underlying virtualization platforms. In the case of SDN/OpenFlow-based virtualization, a crucial example of an operational requirement is the availability of enough memory space for storing flow rules in OpenFlow devices. Due to these circumstances, we advocate that VNE must be performed with some degree of knowledge of the underlying physical networks, otherwise the deployment may suffer from unpredictable or even unsatisfactory performance. Considering SDN/OpenFlow-based physical networks as an important virtualization scenario, we propose a framework based on VNE and OpenFlow coordination for proper deployment of virtual networks (VNs). The proposed approach unfolds in the following main contributions a virtual infrastructure abstraction that allows a service provider to represent the details of his/her VN requirements in a comprehensive manner; a privacy-aware compiler that is able to preprocess this detailed VN request in order to obfuscate sensitive information and derive computable operational requirements; a model for embedding requested VNs that aims at maximizing their feasibility at the physical level. Results obtained through an evaluation of our framework demonstrate that taking such operational requirements into account, as well as accurately assessing them, is of paramount importance to ensure the “health” of VNs hosted on top of the virtualization platform.

The current Internet architecture presents a barrier to accommodate the vigorous arising demand for deploying new network services and applications. The next-generation architecture views the network virtualization as the gateway to overcome this limitation. Network virtualization promises to run efficiently and securely multiple dedicated virtual networks (VNs) over a shared physical infrastructure. Each VN is tailored to host a unique application based on the user’s preferences. This thesis addresses the problem of the efficient embedding of multiple VNs onto a shared substrate network (SN). The contribution of this thesis are twofold: First, a novel hierarchical SN management framework is proposed that efficiently selects the optimum VN mapping scheme for the requested VN from more than one proposed VN mapping candidates obtained in parallel. In order to accommodate the arbitrary architecture of the VNs, the proposed scheme divides the VN request into smaller subgraphs, and individually maps them on the SN using a variation of the exact subgraph matching techniques. Second, the physical resources pricing policy is introduced that is based on time-ofuse, that reflects the effect of resource congestion introduced by VN users. The preferences of the VN users are first represented through corresponding demand-utility functions that quantify the sensitivity of the applications hosted by the VNs to resource consumption and time-of-use. A novel model of time-varying VNs is presented, where users are allowed to up- or down-scale the requested resources to continuously maximize their utility while minimizing the VNs embedding cost. In contrast to existing solutions, the proposed work does not impose any limitations on the size or topology of the VN requests. Instead, the search is customized according to the VN size and the associated utility. Extensive simulations are then conducted to demonstrate the improvement achieved through the proposed work in terms of network utilization, the ratio of accepted VN requests and the SP profits.

Network virtualisation has become one of the most prominent solutions for sus-tainability towards the dramatic increase of data demand in next-generation mobile networks. In addition, apart from increasing the overall infrastructure utilisation, it also greatly improves the manageability, the scalability and the robustness of the network. In order to allow multiple virtual networks to coexist in the same substrate network, the need for efficient network sharing techniques is imperative. The main purpose of this work is to provide a holistic optimization framework for vir-tual network embedding solutions, where the actual user mobility effect is explicitly considered. First, the main focus is given on the study of the mobility effect and the impact of the mobility management techniques on the end-to-end communication of the mobile user. A hybrid-distributed mobility management scheme is proposed and compared against the latest mobility management schemes. Then, an optimisation framework for efficient mobility-aware virtual network embedding is proposed and evaluated by comparison with other works from the literature. Moving deeper in the area of virtual network embedding, the focus is given on minimizing the end-to-end delay and providing service differentiation, allowing in this way delay sensitive services to use the formed virtual networks with the minimum possible delay, as op-posed to other more elastic services that use the same substrate network. The last part of this work is the study and the analysis of the stochastic nature of the virtual network embedding parameters and the proposal of an optimisation framework for adjustable-robustness virtual network embedding. Driven by the benefits from virtualising the network and its functions, research as well as industry are expected to exploit in a greater degree than today the merits of this concept. The co-existence of multiple tenants not only will greatly change the network industry from a business perspective, but also will emphasise the need for more efficient and flexible network sharing techniques. This work belongs to the initial efforts to embrace and adopt the virtualisation concept in the next-generation wireless networks.

There are many machine learning techniques that cannot be performed on graph-data. Techniques such as graph embedding, i.e mapping a graph to a vector, can open up a variety of machine learning solutions. This thesis addresses to what extent static graph embedding techniques can capture important characteristics of an IT-architecture graph, with the purpose of embedding the graphs in a common euclidean vector space that can serve as the state space in a reinforcement learning setup. The metric used for evaluating the performance of the embedding is the security of the graph, i.e the time it would take for an unauthorized attacker to penetrate the IT-architecture graph. The algorithms evaluated in this work are the node embedding methods node2vec and gat2vec and the graph embedding method graph2vec. The predictive results of the embeddings are compared with two baseline methods. The results of each of the algorithms mostly display a significant predictive performance improvement compared to the baseline, where the F1 score in some cases is doubled. Indeed, the results indicate that static graph embedding methods can in fact capture some information about the security of an IT-architecture. However, no conclusion can be made whether a static graph embedding is actually the best contender for posing as the state space in a reinforcement learning framework. To make a certain conclusion other options has to be researched, such as dynamic graph embedding methods.
Det är många maskininlärningstekniker som inte kan appliceras på data i form av en graf. Tekniker som graph embedding, med andra ord att mappa en graf till ett vektorrum, can öppna upp för en större variation av maskininlärningslösningar. Det här examensarbetet evaluerar hur väl statiska graph embeddings kan fånga viktiga säkerhetsegenskaper hos en IT-arkitektur som är modellerad som en graf, med syftet att användas i en reinforcement learning algoritm. Dom egenskaper i grafen som används för att validera embedding metoderna är hur lång tid det skulle ta för en obehörig attackerare att penetrera IT-arkitekturen. Algorithmerna som implementeras är node embedding metoderna node2vec och gat2vec, samt graph embedding metoden graph2vec. Dom prediktiva resultaten är jämförda med två basmetoder. Resultaten av alla tre metoderna visar tydliga förbättringar relativt basmetoderna, där F1 värden i några fall uppvisar en fördubbling. Det går alltså att dra slutsatsen att att alla tre metoder kan fånga upp säkerhetsegenskaper i en IT-arkitektur. Dock går det inte att säga att statiska graph embeddings är den bästa lösningen till att representera en graf i en reinforcement learning algoritm, det finns andra komplikationer med statiska metoder, till exempel att embeddings från dessa metoder inte kan generaliseras till data som inte var använd till träning. För att kunna dra en absolut slutsats krävs mer undersökning, till exempel av dynamiska graph embedding metoder.

Virtualização permite o compartilhamento de uma rede física entre uma ou mais redes virtuais. O Problema de Mapeamento de Redes Virtuais é um dos principais desafios na virtualização de redes. Esse problema consiste em mapear uma rede virtual em uma rede física, respeitando restrições de capacidade. O presente trabalho mostra que encontrar uma solução factível para esse problema é NP-Difícil. Mesmo assim, muitas instâncias podem ser pode ser resolvidas na prática através da exploração de sua estrutura. Nós apresentamos um algoritmo de Branch & Price aplicado a instâncias de diferentes topologias e tamanhos. Os experimentos realizados sugerem que o algoritmo proposto é superior ao modelo de programação linear resolvido com CPLEX.
Virtualization allows one or more virtual networks to share physical infrastructures. The Virtual Network Embedding problem (VNEP) is one of the main challenges in the virtualization of physical networks. This problem consists in mapping a virtual network into a physical network while respecting capacity constraints. This work shows that finding a feasible solution for this problem is NP-Hard. However, many instances can be solved up to optimality in practice by exploiting the problem structure. We present a Branch & Price algorithm applied to instances of different topologies and sizes. The experimental results suggest that the proposed algorithm is superior to the Integer Linear Programming model solved by CPLEX.

As computer networks grow and demonstrate more complicated and intricate behaviors, traditional intrusion detections systems have fallen behind in their ability to protect network resources. Machine learning has stepped to the forefront of intrusion detection research due to its potential to predict future behaviors. However, training these systems requires network data such as NetFlow that contains information regarding relationships between hosts, but requires human understanding to extract. Additionally, standard methods of encoding this categorical data struggles to capture similarities between points. To counteract this, we evaluate a method of embedding IP addresses and transport-layer ports into a continuous space, called IP2Vec. We demonstrate this embedding on two separate datasets, CTU'13 and UGR'16, and combine the UGR'16 embedding with several machine learning methods. We compare the models with and without the embedding to evaluate the benefits of including network behavior into an intrusion detection system. We show that the addition of embeddings improve the F1-scores for all models in the multiclassification problem given in the UGR'16 data.
MS

La 5G apporte un nouveau concept, le network slicing (découpage du réseau en tranches). Cette technologie permet de généraliser le modèle économique des MVNO à des entreprises qui ont besoin d’opérer un réseau, sans que cela ne soit leur cœur de métier. Chaque tranche (slice) est un réseau virtuel de bout en bout, dédié et personnalisé, au-dessus d’une infrastructure partagée ; cette infrastructure elle-même être fournie par l’interconnexion de fournisseurs d’infrastructure: nous parlons dans ce cas d’infrastructure multi-domaine.L’objectif de cette thèse est d’étudier l’allocation de ces tranches dans une telle infrastructure multi-domaine. Le problème est connu comme l’incorporation de réseau virtuel (Virtual Network Embedding (VNE)). Il s’agit d’un problème NP-difficile. Pratiquement, le problème VNE recherche à quelles ressources physiques associer un ensemble d’éléments virtuels. Les ressources physiques décrivent ce qu’elles peuvent offrir. Les éléments virtuels décrivent ce qu’ils exigent. La mise en relation de ces offres et de ces demandes est la clé pour résoudre le problème VNE.En l’espèce, nous nous sommes intéressés à la modélisation et à la mise en place d’exigences de sécurité. En effet, nous nous attendons à ce que les acteurs à l’initiative des tranches appartiennent à des sphères éloignées des télécommunications. Or de la même façon qu’ils connaissent peu ce domaine, nous pouvons nous attendre à ce que leurs besoins, notamment de sécurité, s’expriment d’une façon sans précédent dans le contexte des tranches.Cette thèse présente un algorithme capable de traiter des exigences variées selon un modèle extensible fondé sur un solveur de satisfiabilité appliqué à des théories décidables (Satisfiability Modulo Theories (SMT)). Comparée à la programmation linéaire (Integer Linear Programming (ILP)), plus commune dans le domaine des VNE, cette formulation permet d’exprimer les contraintes à satisfaire de façon plus transparente, et d’auditer l’ensemble des contraintes.De plus, ayant conscience que les fournisseurs d’infrastructure sont réticents à exposer les informations relatives à leurs ressources physiques, nous proposons une résolution limitant cette exposition. Ce système a été implémenté et testé avec succès au cours du doctorat
5G brings a new concept called network slicing. This technology makes it possible to generalize the business model of MVNOs to companies in need to operate a network, without it being their core business. Each slice is an end-to-end, dedicated and customized virtual network, over a shared infrastructure; this infrastructure itself is provided by the interconnection of infrastructure providers: we refer to this case as a multi-domain infrastructure.The objective of this thesis is to study the allocation of these slices in such a multi-domain infrastructure. The problem is known as Virtual Network Embedding (VNE). It is an NP-hard problem. Practically, the VNE problem looks for which physical resources to associate a set of virtual elements. Physical resources describe what they can offer. Virtual elements describe what they require. Linking these offers and requests is the key to solve the VNE problem.In this thesis, we focused on modeling and implementing security requirements. Indeed, we expect that the initiators of the slices belong to areas distant from telecommunications. In the same way that they know little about this field, we can expect that their needs, especially in security, are novel in the slice context.This thesis presents an algorithm able to handling various requirements, according to an extensible model based on a Satisfiability Modulo Theories (SMT) solver. Compared to Integer Linear Programming (ILP), more common in the VNE field, this formulation allows to express the satisfaction constraints in a more transparent way, and allows to audit all the constraints.Moreover, being aware that infrastructure providers are reluctant to disclose information about their physical resources, we propose a resolution limiting this disclosure. This system has been successfully implemented and tested during the Ph.D

To create a fashionable outfit one needs to take into account several different similarity conditions between clothing items, such as season, colour, what kind of context the outfit is supposed worn in etc. This is of course a hard task for a human to do but an even harder task for a computer to solve. To make an algorithm take into account different similarity conditions from images Veit, Belongie, and Karaletsos [1] and Vasileva et al. [2] introduced two different models that utilizes predefined similarity conditions. Tan et al. [3] took inspiration from [1, 2] and created an algorithm that learns the similairty conditions in an unsupervised way and they tested their model on a dataset containing outfits created by regular people. In this thesiswe present a newfashion datset that has been created with the help of fashion experts from Hennes & Mauritz AB. We provide evidence that our reimplementation of the Similarity Condition Embedding Network (SCE-net) from [3] can pick out garments that complete an outfit as well as evaluate if the clothing items in an outfit are compatible or not on data that contains outifts for both men and women. We also show that the SCE-net can be trained on outfits for one gender and then predict on a dataset containing clothes for another gender. We further provide results that our network generalize well to unseen categories by training it on outfits without accessories and then test the network on outfits with accessories. In addition we also introduce a dataset that contains baskets of items for customers from Hennes & Mauritz online shop as well as their boutiques. On this data we provide evidence that our reimplementation of the SCE-net can predict the next item in a customers shopping basket.
För att skapa en mode riktigt klädes outfit behöver man ta hänsyn till flertalet olika faktoer, som t.ex. säsong, färg samt i vilken typ av sammanghang klädesutstyrseln är tänkt att bäras inom etc. Detta är naturligtvis en svår uppgift för en människa att göra men det är ett ännu svårare problem för en dator att lösa. För att lära en algorithm att ta hänsyn till olika likhetsvillkor introducerade Veit, Belongie och Karaletsos [1] och Vasileva m. fl. [2] två olika modeller som använder sig av förbestämda likhetsvillkor. Vidare blev Tan m. fl. [3] inspirerad av [1, 2] och skapade en algorithm som kan lära sig likhetsvillkor via oövervakad inlärning, denna modell testade dom på ett dataset som innehåller klädesutstyrsal som är skapade av vanliga människor. I detta examensarbete presenterar vi ett nytt modedataset som har skapats med hjälp av modeexperter från Henns & Mauritz AB. Vidare bevisar vi att våran implementering av Similarity Condition Embedding Network (SCE-net) från [3] kan välja ut ett klädesplagg som tillsammans med tidigare utvalda plagg skapar en outfit samt utvärdera om klädesplaggen i en outfit är kompatibla eller inte. Vi utför dessa tester på data som innehåller kläder för både män och kvinnor. Vi visar också att SCE-net tränas med data som innehåller kläder för ett kön för att senare prediktera kläder i outfits för ett annat kön. Vidare tillhandahåller vi resultat som påvisar att SCE-net generaliserar väl till osedda kategorier genom att träna modellen på outfits som inte innehåller accessoarer och sedan testar vi modellen på klädes utstyrslar som innehåller accessoarer. Utöver detta introducerar vi även ett dataset som innehåller artiklar från kunders kundvagnar från Hennes & Mauritz onlinebutiker samt deras fysiska butiker. Med hjälp av denna data visar vi att våran implementering av SCE-net kan prediktera nästa vara i en kunds varukorg.

Currently a growing number of users depend on the Edge Cloud Computing Paradigm in a Metro Optical Network (MON). This has led to increased competition among the Cloud Service Providers (CPs) to supply incentives for the user through guaranteed Quality of Service (QoS). If the CP fails to guarantee the QoS for the accepted request, then the user will move to another CP. Making an informed decision dynamically in such a sensitive situation demands that the CP knows the user's application requirements. The Software Defined Networking (SDN) paradigm enabled the CP to achieve such desired requirement. Therefore, a framework called Virtual Network Embedding on SDN-based Metro Optical Network (VNE-MON) is proposed in this Thesis. The use of SDN paradigm in the framework guarantees profit to the CP as well as QoS to the user.\par The design concept of the SDN control plane, raises concerns regarding its scalability, reliability and performance compared to a traditionally distributed network. To justify concerns regarding the SDN, the performance of VNE-MON and its possible dependancy on the controller location is investigated. Several strategies are proposed and formulated using Integer Linear Programming to determine the controller location in a MON. Performance results from the assessment of the VNE-MON illustrates that it is more stable compare to GMPLS-based network. It is evident that the controller location's attributes have a significant effect on the efficacy of the accepted VN request.

Face Recognition has been a long-standing topic in computer vision and pattern recognition field because of its wide and important applications in our daily lives such as surveillance system, access control, and so on. The current modern face recognition model, which keeps only a couple of images per person in the database, can now recognize a face with high accuracy. Moreover, the model does not need to be retrained every time a new person is added to the database. By using the face dataset from Digital Democracy, the thesis will explore the capability of this model by comparing it with the standard convolutional neural network based on pose variations and training set sizes. First, we compare different types of pose to see their effect on the accuracy of the algorithm. Second, we train the system using different number of training images per person to see how many training samples are actually needed to maintain a reasonable accuracy. Finally, to push the limit, we decide to train the model using only a single image per person with the help of a face generation technique to synthesize more faces. The performance obtained by this integration is found to be competitive with the previous results, which are trained on multiple images.

A virtualização de redes tem se tornado cada vez mais proeminente nos últimos anos. Tal técnica permite a criação de infraestruturas de rede que se adaptam a necessidades específicas de aplicações de rede distintas, além de dar suporte à instanciação de ambientes favoráveis para o desenvolvimento e avaliação de novas arquiteturas e protocolos. Apesar de esforços recentes (motivados principalmente pela busca de mecanismos para avaliar propostas relacionadas à Internet do Futuro) terem contribuído substancialmente para a materialização desse conceito, nenhum preocupou-se em conciliar alocação eficiente de recursos e satisfação de requisitos de segurança (e.g., confidencialidade). É importante ressaltar que, no contexto de redes virtuais, a proteção de infraestruturas de rede compartilhadas constitui condição fundamental para seu uso em larga escala. É de grande importância que o impacto negativo causado pelo aprovisionamento de segurança seja considerado no processo de mapeamento de redes virtuais, de forma a permitir o uso integral dos recursos físicos sem subestimar requisitos de capacidade. Portanto, nesta dissertação, são propostos um modelo ótimo e um al- goritmo heurístico para realizar o mapeamento de redes virtuais em substratos físicos que têm por objetivo otimizar a utilização de recursos físicos garantindo a satisfação de requisitos de segurança. Ambas as abordagens possuem uma modelagem precisa de custos adicionais associados a mecanismos de segurança usados para proteger re- des virtuais, e são capazes de atender requisições de redes virtuais de forma online. Além disso, são apresentados os resultados de um extensivo processo de avaliação realizado, incluindo uma comparação detalhada entre o modelo ótimo e o algoritmo heurístico. Os experimentos revelam que o modelo baseado em Programação Linear Inteira é capaz de alocar redes virtuais de forma ótima em substratos físicos com até cem roteadores, enquanto que o algoritmo heurístico é capaz de adaptar-se a infraestruturas maiores, provendo mapeamentos sub-ótimos em um curto espaço de tempo.
Network virtualization has become increasingly prominent in recent years. It enables the creation of network infrastructures that are specifically tailored to the needs of distinct network applications and supports the instantiation of favorable en- vironments for the development and evaluation of new architectures and protocols. Although recent efforts (motivated mainly by the search for mechanisms to eval- uate Future Internet proposals) have contributed substantially to materialize this concept, none of them has attempted to combine efficient resource mapping with ful- fillment of security requirements (e.g., confidentiality). It is important to note that, in the context of virtual networks, the protection of shared network infrastructures constitutes a fundamental condition to enable its use in large scale. Considering the negative impact of security provisions in the virtual network embedding process is of paramount importance in order to fully utilize physical re- sources without underestimating capacity requirements. Therefore, in this thesis we propose both an optimal model and a heuristic algorithm for embedding virtual networks on physical substrates that aim to optimize physical resource usage while meeting security requirements. Both approaches feature precise modeling of over- head costs of security mechanisms used to protect virtual networks, and are able to handle virtual network requests in an online manner. In addition, we present the results of an extensive evaluation we carried out, including a detailed comparison of both the optimal model and the heuristic algorithm. Our experiments show that the Integer Linear Programming (ILP) model is capable of optimally embedding virtual networks on physical infrastructures with up to a hundred routers, while the heuristic algorithm is capable of scaling to larger infrastructures, providing timely, sub-optimal mappings.

Network virtualization and overlay networks have emerged as powerful tools for improving the flexibility of the Internet. Overlays are used to provide a wide range of useful services in today's networking environment, and they are also viewed as important building blocks for an agile and evolvable future Internet. Regardless of the specific service it provides, an overlay needs assistance in several areas in order to perform properly throughout its existence. This dissertation focuses on the mechanisms underlying the provision of auxiliary support services that perform control and management functions for overlays, such as overlay assignment, resource allocation, overlay monitoring and diagnosis. The priorities and objectives in the design of such mechanisms depend on network conditions and the virtualization environment. We identify opportunities for improvements that can help provide auxiliary services more effectively at different overlay life stages and under varying assumptions. The contributions of this dissertation are the following: 1. An overlay assignment algorithm designed to improve an overlay's diagnosability, which is defined as its property to allow accurate and low-cost fault diagnosis. The main idea is to increase meaningful sharing between overlay links in a controlled manner in order to help localize faults correctly with less effort. 2. A novel definition of bandwidth allocation fairness in the presence of multiple resource sharing overlays, and a routing optimization technique to improve fairness and the satisfaction of overlays. Evaluation analyzes the characteristics of different fair allocation algorithms, and suggests that eliminating bottlenecks via custom routing can be an effective way to improve fairness. 3. An optimization solution to minimize the total cost of monitoring an overlay by determining the optimal mix of overlay and native links to monitor, and an analysis of the effect of topological properties on monitoring cost and the composition of the optimal mix of monitored links. We call our approach multi-layer monitoring and show that it is a flexible approach producing minimal-cost solutions with low errors. 4. A study of virtual network embedding in software defined networks (SDNs), identifying the challenges and opportunities for embedding in the SDN environment, and presenting two VN embedding techniques and their evaluation. One objective is to balance the stress on substrate components, and the other is to minimize the delays between VN controllers and switches. Each technique optimizes embedding for one objective while keeping the other within bounds.

O atual sucesso da Internet vem inibindo a disseminação de novas arquiteturas e protocolos de rede. Especificamente, qualquer modificação no núcleo da rede requer comum acordo entre diversas partes. Face a isso, a Virtualização de Redes vem sendo proposta como um atributo diversificador para a Internet. Tal paradigma promove o desenvolvimento de novas arquiteturas e protocolos por meio da criação de múltiplas redes virtuais sobrepostas em um mesmo substrato físico. Adicionalmente, aplicações executando sobre uma mesma rede física podem ser isoladas mutuamente, propiciando a independência funcional entre as mesmas. Uma de suas mais promissoras vantagens é a capacidade de limitar o escopo de ataques, através da organização de uma infraestrutura em múltiplas redes virtuais, isolando o tráfego das mesmas e impedindo interferências. Contudo, roteadores e enlaces virtuais permanecem vulneráveis a ataques e falhas na rede física subjacente. Particularmente, caso determinado enlace do substrato seja comprometido, todos os enlaces virtuais sobrepostos (ou seja, alocados neste) serão afetados. Para lidar com esse problema, a literatura propõe dois tipos de estratégias: as que reservam recursos adicionais do substrato como sobressalentes, protegendo contra disrupções; e as que utilizam migração em tempo real para realocar recursos virtuais comprometidos. Ambas estratégias acarretam compromissos: o uso de recursos sobressalentes tende a tornar-se custoso ao provedor de infraestrutura, enquanto a migração de recursos demanda um período de convergência e pode deixar as redes virtuais inoperantes durante o mesmo. Esta dissertação apresenta ORE (Opportunistic Resilience Embedding – Mapeamento com Resiliência Oportunística), uma nova abordagem de mapeamento de redes para proteger enlaces virtuais contra disrupções no substrato físico. ORE é composto por duas estratégias: uma proativa, na qual enlaces virtuais são alocados em múltiplos caminhos para mitigar o impacto de uma disrupção; e uma reativa, a qual tenta recuperar, parcial ou integralmente, a capacidade perdida nos enlaces virtuais afetados. Ambas são modeladas como problemas de otimização. Ademais, como o mapeamento de redes virtuais é NP-Difícil, ORE faz uso de uma meta-heurística baseada em Simulated Annealing para resolver o problema de forma eficiente. Resultados numéricos mostram que ORE pode prover resiliência a disrupções por um custo mais baixo.
Recently, the Internet’s success has prevented the dissemination of novel networking architectures and protocols. Specifically, any modification to the core of the network requires agreement among many different parties. To address this situation, Network Virtualization has been proposed as a diversifying attribute for the Internet. This paradigm promotes the development of new architectures and protocols by enabling the creation of multiple virtual networks on top of a same physical substrate. In addition, applications running over the same physical network can be isolated from each other, thus allowing them to coexist independently. One of the main advantages of this paradigm is the use of isolation to limit the scope of attacks. This can be achieved by creating different, isolated virtual networks for each task, so traffic from one virtual network does not interfere with the others. However, routers and links are still vulnerable to attacks and failures on the underlying network. Particularly, should a physical link be compromised, all embedded virtual links will be affected. Previous work tackled this problem with two main strategies: using backup resources to protect against disruptions; or live migration to relocate a compromised virtual resource. Both strategies have drawbacks: backup resources tend to be expensive for the infrastructure provider, while live migration may leave virtual networks inoperable during the recovery period. This dissertation presents ORE (Opportunistic Resilience Embedding), a novel embedding approach for protecting virtual links against substrate network disruptions. ORE’s design is two-folded: while a proactive strategy embeds virtual links into multiple substrate paths in order to mitigate the initial impact of a disruption, a reactive one attempts to recover any capacity affected by an underlying disruption. Both strategies are modeled as optimization problems. Additionally, since the embedding problem is NP-Hard, ORE uses a Simulated Annealing-based meta-heuristic to solve it efficiently. Numerical results show that ORE can provide resilience to disruptions at a lower cost.

'The Company' had introduced 'Being Responsible' a program for the embedding of responsibility-sustainability. Corporate responsibility-sustainability here describes efforts to address entangled cares of responsibility and sustainability. The program showed potential to change the business model, which led to the research problem: 'How can responsibility-sustainability programs change business models?'In this thesis, business models are understood as three dynamically interlinked states: Logics, devices and actor networks. Business model change may happen through the embedding of responsibility-sustainability into any of these states, and through the dynamics between them. Main conceptual lenses are organizational institutionalism and actor-network theory, which are connected through a social constructionist philosophy. Qualitative methods used include an in-depth case study of The Company (104 interviews with 72 interviewees) and thematic analyses of business model descriptions (devices) of FTSE corporations (100 documents).Seven papers study distinct aspects of the research problem: Papers 1 and 2 provide a conceptual basis. Papers 3 and 4 study how the embedding of responsibility-sustainability into the FTSE100s' business model devices changed the logics they described. Papers 5-7 study embedding into The Company's business model actor network. I found how embedding of responsibility-sustainability into the three states of commercial business models happened through three processes: Blending of logics, combination of device elements and translation between actors. Such embedding of responsibility-sustainability led to misalignment and tensions between responsibility-sustainability and the dominant commercial logic. This misalignment in turn fueled the dynamics of change between logics, devices and actor networks. First, this thesis contributes to an emerging literature on the dynamics of business model logics, devices and actor networks. It makes explicit the distinction between these states and illustrates how their dynamics provide novel insight into business model change. Secondly, I showcase how actor-network theory may complement the activity systems study of business models as well as stakeholder thinking in responsibility-sustainability research. Insights into how to use devices to change business models and to embed responsibility-sustainability appear relevant for practitioners.

As the "network of network", the Internet has been playing a central and crucial role in modern society, culture, knowledge, businesses and so on in a period of over two decades by supporting a wide variety of network technologies and applications. However, due to its popularity and multi-provider nature, the future development of the Internet is limited to simple incremental updates. To address this challenge, network virtualization has been propounded as a potential candidate to provide the essential basis for the future Internet architecture. Network virtualization is capable of providing an open and flexible networking environment in which service providers are allowed to dynamically compose multiple coexisting heterogeneous virtual networks on a shared substrate network. Such a flexible environment will foster the deployment of diversified services and applications. A major challenge in network virtualization area is the Virtual Network Embedding (VNE), which aims to statically or dynamically allocate virtual nodes and virtual links on substrate resources, physical nodes and paths. Making effective use of substrate resources requires high-efficient and survivable VNE techniques. The main contribution of this thesis is two high-performance p-Cycle-based survivable virtual network embedding approaches. These approaches take advantage of p-Cycle-based protection techniques that minimize the backup resources while providing a full VN protection scheme against link and node failures.

Network virtualization is recognized as an enabling technology for the future Internet. It aims to overcome the resistance of the current Internet to architectural change and to enable a new business model decoupling the network services from the underlying infrastructure. The problem of embedding virtual networks in a substrate network is the main resource allocation challenge in network virtualization and is usually referred to as the Virtual Network Embedding (VNE) problem. VNE deals with the allocation of virtual resources both in nodes and links. Therefore, it can be divided into two sub-problems: Virtual Node Mapping where virtual nodes have to be allocated in physical nodes and Virtual Link Mapping where virtual links connecting these virtual nodes have to be mapped to paths connecting the corresponding nodes in the substrate network. Application of network virtualization relies on algorithms that can instantiate virtualized networks on a substrate infrastructure, optimizing the layout for service-relevant metrics. This class of algorithms is commonly known as VNE algorithms. This thesis proposes a set of contributions to solve the research challenges of the VNE that have not been tackled by the research community. To do that, it performs a deep and comprehensive survey of virtual network embedding. The first research challenge identified is the lack of proposals to solve the virtual link mapping stage of VNE using single path in the physical network. As this problem is NP-hard, existing proposals solve it using well known shortest path algorithms that limit the mapping considering just one constraint. This thesis proposes the use of a mathematical multi-constraint routing framework called paths algebra to solve the virtual link mapping stage. Besides, the thesis introduces a new demand caused by virtual link demands into physical nodes acting as intermediate (hidden) hops in a path of the physical network. Most of the current VNE approaches are centralized. They suffer of scalability issues and provide a single point of failure. In addition, they are not able to embed virtual network requests arriving at the same time in parallel. To solve this challenge, this thesis proposes a distributed, parallel and universal virtual network embedding framework. The proposed framework can be used to run any existing embedding algorithm in a distributed way. Thereby, computational load for embedding multiple virtual networks is spread across the substrate network Energy efficiency is one of the main challenges in future networking environments. Network virtualization can be used to tackle this problem by sharing hardware, instead of requiring dedicated hardware for each instance. Until now, VNE algorithms do not consider energy as a factor for the mapping. This thesis introduces the energy aware VNE where the main objective is to switch off as many network nodes and interfaces as possible by allocating the virtual demands to a consolidated subset of active physical networking equipment. To evaluate and validate the aforementioned VNE proposals, this thesis helped in the development of a software framework called ALgorithms for Embedding VIrtual Networks (ALEVIN). ALEVIN allows to easily implement, evaluate and compare different VNE algorithms according to a set of metrics, which evaluate the algorithms and compute their results on a given scenario for arbitrary parameters.

A virtualização de redes é um mecanismo que permite a coexistência de múltiplas redes virtuais sobre um mesmo substrato físico. Um dos desafios de pesquisa abordados na literatura é o mapeamento eficiente de recursos virtuais em infraestruturas físicas. Embora o referido desafio tenha recebido considerável atenção, as abordagens que constituem o estado-da-arte apresentam alta taxa de rejeição, i.e., a proporção de solicitações de redes virtuais negadas em relação ao total de solicitações efetuadas ao substrato é elevada. Nesta dissertação, caracteriza-se, inicialmente, a relação entre a qualidade dos mapeamentos de redes virtuais e as estruturas topológicas dos substratos subjacentes. Avalia-se as soluções exatas de um modelo de mapeamento online sob diferentes classes de topologias de rede. A partir do entendimento dos fatores topológicos que influenciam diretamente o processo de mapeamento de redes virtuais, propõe-se uma estratégia para planejar a expansão de redes de provedores de infraestrutura de forma a reduzir consistentemente a taxa de rejeição de requisições de redes virtuais e melhor aproveitar os recursos ociosos da mesma. Os resultados obtidos evidenciam que grande parte das rejeições de redes virtuais ocorre em situações em que há grande disponibilidade de recursos, mas alguns poucos já saturados acabam inviabilizando, em função de características de conectividade do substrato, o atendimento de novas requisições. Ademais, os resultados obtidos utilizando a estratégia proposta evidenciam que o fortalecimento de partes-chave da infraestrutura levam a uma ocupação muito mais satisfatória. Uma expansão de 10% a 20% dos recursos da infraestrutura contribui para um aumento sustentado de até 30% no número de redes virtuais aceitas e de até 45% no aproveitamento dos recursos em comparação com a rede original.
Network virtualization is a mechanism that allows the coexistence of multiple virtual networks on top of a single physical substrate. One of the research challenges addressed recently in the literature is the efficient mapping of virtual resources on physical infrastructures. Although this challenge has received considerable attention, state-of-the-art approaches present, in general, a high rejection rate, i.e., the ratio between the number of denied virtual network requests and the total amount of requests is considerably high. In this thesis, we characterize the relationship between the quality of virtual network mappings and the topological structures of the underlying substrates. Exact solutions of an online embedding model are evaluated under different classes of network topologies. From the understanding of the topological factors that directly influence the virtual network embedding process, we propose an expansion strategy of physical infrastructure in order to suggest adjustments that lead to higher virtual network acceptance and, in consequence, to improved physical resource utilization. The obtained results demonstrate that most of rejections occur in situations in which a significant amount of resource is available, but a few saturated devices and links, depending on connectivity features of the physical substrate, hinder the acceptance of new requests. Moreover, the obtained results using the proposed strategy evidence that an expansion of 10% to 20% of the infrastructure resources leads to a sustained increase of up to 30% in the number of accepted virtual networks and of up to 45% in resource usage compared to the original network.

The use of mobile devices to support students’ learning experiences is a growing area of interest in higher education (Wankel & Blessinger, 2013). This study adopts an ‘umbrella’ term of m-learning to consider the use of mobile and wireless technologies to support students in a blended learning environment. Whilst m-learning pedagogy has received considerable attention (e.g. Attewell, 2005, Sharples et. al. 2007, Kukulska-Hulme, 2012), the process of adopting this potentially disruptive innovation within universities has been neglected. This study addresses this gap by attempting to answer the research question: How do university organizations (business models, modes of operation, people and processes) adapt to a potentially disruptive innovation like m-learning and what factors and working practices support or hinder embedding? Possible frameworks for studying innovation are reviewed, including Rogers’ innovation diffusion framework (Rogers, 1962), Actor-Network Theory (Latour, 2005) , Activity Theory ngestr m 1987), Structuration Theory (Giddens, 1984), theories of disruptive innovation (Christensen, 1997) and the Technology Acceptance Model (Venkatesh and Davis, 2000), Actor-Network Theory (ANT) is chosen as the most promising theoretical lens for an in-depth investigation of m-learning embedding, and a participative fieldwork approach is developed that uses Law and Callon’s ANT notion of ‘points of passage’ between local and global networks (Law and Callon, 1991) to illuminate factors and working practices that affect embedding. A framework based on Law and Callon’s work is developed through a year-long study of competing text messaging projects within a university and developed further through a three-year, longitudinal case study involving five universities using smartphone applications to assess students in medical practice situations. Several institutional issues are identified that help or hinder embedding, such as fragmentation of IT strategy and decision-making, and the need to provide students with a compelling offer of multiple institutional services on their mobiles. The role of people and artefacts in forming a link, or ‘point of passage’ between m-learning projects ‘local networks’) and institutional IT strategies and services ‘global networks’) is found to be of central interest for understanding processes of embedding. A clear path to an ANT analysis is demonstrated starting from interview and observation data, using coding techniques borrowed from grounded theory (Schatzman and Strauss, 1973) and finishing with Law and Callon’s local-global network model, which is used to compare and contrast embedding trajectories of the case study institutions. Systematic comparison enables a three dimensional model of embedding trajectories to be built, which extends Law and Callon’s work and places in sharper focus the importance of establishing a path by which local initiatives can be evaluated strategically and, where appropriate, incorporated in a timely manner into a university’s IT strategy. Grounded in extensive longitudinal research, the study offers a contribution to methodology through its demystification of ANT; a contribution to theory through its three dimensional model for mapping embedding trajectories; and a contribution to practice by highlighting specific issues that affect mobile technology adoption in higher education, such as having a compelling, multi-service offer, appropriate mobile tariffs for undertaking mandatory assessment and guidelines for incorporating knowledge gained from technology experiments into institutional strategies and decision-making. The study concludes by highlighting opportunities for using its model to explore challenges of embedding faced not only by formal projects but by ‘maverick’ innovators and for potentially disruptive technologies other than m-learning, such as Web 2.0 services.

La virtualisation de réseau permet de créer des réseaux logiques, dits virtuels sur un réseau physique partagé dit substrat. Pour ce faire, le problème d’allocation des ressources aux réseaux virtuels doit être résolu efficacement. Appelé VNE (Virtual Network Embedding), ce problème consiste à faire correspondre à chaque nœud virtuel un nœud substrat d’un côté, et de l’autre, à tout lien virtuel un ou plusieurs chemins substrat, de manière à optimiser un objectif tout en satisfaisant un ensemble de contraintes. Les ressources de calcul des nœuds et les ressources de bande passante des liens sont souvent optimisées dans un seul réseau substrat. Dans le contexte multi-domaine où la connaissance de l’information de routage est incomplète, l’optimisation des ressources de nœuds et de liens est difficile et souvent impossible à atteindre. Par ailleurs, pour assurer la continuité de service même après une panne, le VNE doit être réalisé de manière à faire face aux pannes. Dans cette thèse, nous étudions le problème d’allocation de ressources (VNE) sous diverses exigences. Pour offrir la virtualisation dans le contexte de réseau substrat multi-domaines, nous proposons une méthode de mappage conjoint des liens inter-domaines et intra-domaines. Avec une information réduite et limitées annoncées par les domaines, notre méthode est capable de mapper simultanément les liens intra-domaines et les liens inter-domaines afin d’optimiser les ressources. De plus, pour améliorer la robustesse des réseaux virtuels, nous proposons un algorithme d’évitement des pannes qui minimise la probabilité de panne des réseaux virtuels. Des solutions exactes et heuristiques sont proposées et détaillées pour des liens à bande passante infinie ou limitée. En outre, nous combinons l’algorithme d’évitement des pannes avec la protection pour proposer un VNE robuste et résistant aux pannes. Avec cette nouvelle approche, les liens protégeables puis les liens les moins vulnérables sont prioritairement sélectionnés pour le mappage des liens. Pour déterminer les liens protégeables, nous proposons une heuristique qui utilise l’algorithme du maxflow afin de vérifier etdedéterminerlesliensprotégeablesàl’étapedumappagedesliensprimaires. Encasd’insuffisance de ressources pour protéger tous les liens primaires, notre approche sélectionne les liens réduisant la probabilité de panne
Network virtualization allows to create logical or virtual networks on top of a shared physical or substrate network. The resource allocation problem is an important issue in network virtualization. It corresponds to a well known problem called virtual network embedding (VNE). VNE consists in mapping each virtual node to one substrate node and each virtual link to one or several substrate paths in a way that the objective is optimized and the constraints verified. The objective often corresponds to the optimization of the node computational resources and link bandwidth whereas the constraints generally include geographic location of nodes, CPU, bandwidth, etc. In the multi-domain context where the knowledge of routing information is incomplete, the optimization of node and link resources are difficult and often impossible to achieve. Moreover, to ensure service continuity even upon failure, VNE should cope with failures by selecting the best and resilient mappings. Inthisthesis,westudytheVNEresourceallocationproblemunderdifferentrequirements. To embed a virtual network on multi-domain substrate network, we propose a joint peering and intra domain link mapping method. With reduced and limited information disclosed by the domains, our downsizing algorithm maps the intra domain and peering links in the same stage so that the resource utilization is optimized. To enhance the reliability of virtual networks, we propose a failure avoidance approach that minimizes the failure probability of virtual networks. Exact and heuristic solutions are proposed and detailed for the infinite and limited bandwidth link models. Moreover, we combine the failure avoidance with the failure protection in our novel protection-level-aware survivable VNE in order to improve the reliability. With this last approach, the protectable then the less vulnerable links are first selected for link mapping. To determine the protectable links, we propose a maxflow based heuristic that checks for the existence of backup paths during the primary mapping stage. In case of insufficient backup resources, the failure probability is reduced

Performance analysis of Digital Subscriber Line (DSL) technologies, which are implemented on existing telephone subscriber loops, is of vital importance to DSL service providers. This type of analysis requires accurate prediction of the local loop structure and precise identification of the cable parameters. These cables are the main components of the loop and are typically comprised of multi-conductor twisted pair type currently being used on existing telephone subscriber loops. This system identification problem was investigated through the application of single port measurements, with preference being placed on measurements taken from the service provider's end of the loop under investigation. Once the cabling system has been identified, the performance analysis of the loop was obtained through simulation. Accurate modeling is an important aspect of any system identification solution; therefore, the modeling of the twisted pair cables was thoroughly investigated in this research. Early modeling attempts of twisted pair cabling systems for use with (DSL) technology has not been vigorously investigated due to the difficulty in obtaining wideband physical data necessary for the task as well as the limitations of simulators to accurately model the skin effects of the conductors. Models are developed in this research that produce a wideband representation of the twisted pair cables through the use of the data measured in high frequency spectra. The twisted-pair cable models were then applied to the system identification problem through a de-embedding type approach. The identification process accurately characterizes the sections of the subscriber loop closest to the measurements node, and these identified sections were then modeled and de-embedded from the system measurement in a layer removing, or "peeling", type process. After each identified section was de-embedded from the system measurement, the process was repeated until the entire system was identified. Upon completion of the system identification process, the resulting system model was simulated between the central office (CO) and resulting identified customer nodes for the evaluation of performance analysis. The performance analysis allows the providers to identify points where the DSL technology is feasible, and where so, the rates of the data transfer to the nodes that can be expected.
Ph. D.

Vid stor mängd data i form av kundomdömen kan det vara ett relativt tidskrävande arbeteatt bedöma varje omdömes sentiment manuellt, om det är positivt eller negativt laddat. Denna avhandling har utförts för att automatiskt kunna klassificera kundomdömen efter positiva eller negativa omdömen vilket hanterades med hjälp av maskininlärning. Tre olika djupa neurala nätverk testades och jämfördes med hjälp av två olika ramverk, TensorFlow och Keras, på både större och mindre datamängder. Även olika inbäddningsmetoder testades med de neurala nätverken. Den bästa kombination av neuralt nätverk, ramverk och inbäddningsmetod var ett Convolutional Neural Network (CNN) som använde ordinbäddningsmetoden Word2Vec, var skriven i ramverket Keras och gav en träffsäkerhetpå ca 88.87% med en avvikelse på ca 0.4%. CNN gav bäst resultat i alla olika tester framför de andra två neurala nätverken, Recurrent Neural Network (RNN) och Convolutional Recurrent Neural Network (CRNN)
With large amount of data in the form of customer reviews, it could be time consuming to manually go through each review and decide if its sentiment is positive or negative. This thesis have been done to automatically classify client reviews to determine if a review is positive or negative. This was dealt with by machine learning. Three different deep neural network was tested on greater and lesser datasets, and compared with the help of two different frameworks, TensorFlow and Keras. Different embedding methods were tested on the neural networks. The best combination of a neural network, a framework and anembedding was the Convolutional Neural Network (CNN) which used the word embedding method Word2Vec, was written in Keras framework and gave an accuracy of approximately 88.87% with a deviation of approximately 0.4%. CNN scored a better result in all of the tests in comparison with the two other neural networks, Recurrent NeuralNetwork (RNN) and Convolutional Recurrent Neural Network (CRNN).

Cloud Infrastructure-as-a-Service (IaaS) is a form of utility computing which has emerged with the recent innovations in the service computing and data communication technologies. Regardless of the fact that IaaS is attractive for application service providers, satisfying user requests while ensuring cloud operational objectives is a complicated task that raises several resource management challenges. Among these challenges, limited controllability over network services delivered to cloud consumers is prominent in single datacenter cloud environments. In addition, the lack of seamless service migration and optimization, poor infrastructure utilization, and unavailability of efficient fault tolerant techniques are noteworthy challenges in geographically distributed datacenter clouds. Initially in this thesis, a datacenter resource management framework is presented to address the challenge of limited controllability over cloud network traffic. The proposed framework integrates network virtualization functionalities offered by software defined networking (SDN) into cloud ecosystem. To provide rich traffic control features to IaaS consumers, control plane virtualization capabilities offered by SDN have been employed. Secondly, a quality of service (QoS) aware seamless service migration and optimization framework has been proposed in the context of geo-distributed datacenters. Focus has been given to a mobile end-user scenario where frequent cloud service migrations are required to mitigate QoS violations. Finally, an SDN-based dynamic fault restoration scheme and a shared backup-based fault protection scheme have been proposed. The fault restoration has been achieved by introducing QoS-aware reactive and shared risk link group-aware proactive path computation algorithms. Shared backup protection has been achieved by optimizing virtual and backup link embedding through a novel integer linear programming approach. The proposed solutions significantly improve bandwidth utilization in inter-datacenter networks while recovering from substrate link failures.

Submitted by PPG Ci?ncia da Computa??o (ppgcc@pucrs.br) on 2018-12-12T11:28:20Z No. of bitstreams: 1 Romulo Reis de Oliveira_DIS.pdf: 1719302 bytes, checksum: 005f38fa0c94cb6b97ce5f6ad6ec70ed (MD5)
Approved for entry into archive by Sheila Dias (sheila.dias@pucrs.br) on 2018-12-14T11:26:14Z (GMT) No. of bitstreams: 1 Romulo Reis de Oliveira_DIS.pdf: 1719302 bytes, checksum: 005f38fa0c94cb6b97ce5f6ad6ec70ed (MD5)
Made available in DSpace on 2018-12-14T11:50:26Z (GMT). No. of bitstreams: 1 Romulo Reis de Oliveira_DIS.pdf: 1719302 bytes, checksum: 005f38fa0c94cb6b97ce5f6ad6ec70ed (MD5) Previous issue date: 2015-04-24
Hybrid synchrony virtual networks arose by combining network virtualization, which allows the co-existence of several virtual networks in the same shared physical substrate, providing infrastructure in a flexible and economic way, with partial synchrony network architecture, which is relevant in distributed systems in order to build reliable systems. One of the main challenges in network virtualization is the efficient mapping of virtual resources in the substrate network, since it is a NP-Hard complexity problem. When considering the synchrony of virtual and physical resources it becomes more difficult to map, making it unfeasible to calculate the optimal solution in real environments. Thus, heuristic approaches are necessary for finding semi-optimal solutions faster. In this work, four heuristics for mapping hybrid synchrony virtual networks are adapted. In order to evaluate these heuristics, two sets of experiments were executed. In the first set is compared the optimal solutions with their respective semi-optimal solutions, the results show the heuristics? efficiency are better when the virtual network requests are smaller, furthermore there were some semi-optimal solution mapping costs equivalent to the optimal solution mapping cost. The second set of experiments evaluates the heuristics performance using a physical substrate closer to real context and a larger number of virtual network requests. The results of this second set of experiments demonstrate that even with a larger number of virtual requests and a larger substrate, the solutions were computed in acceptable time.
As redes virtuais de sincronia h?brida surgiram da combina??o entre a virtualiza??o de redes, a qual permite a coexist?ncia de v?rias redes virtuais no mesmo substrato f?sico compartilhado fornecendo infraestrutura de maneira flex?vel e econ?mica, e arquitetura de redes com sincronia parcial, essa relevante em sistemas distribu?dos para construir sistemas confi?veis. Um dos principais desafios em virtualiza??o de redes ? o mapeamento eficiente dos recursos virtuais na rede de substrato, pois ? um problema de complexidade NP-Dif?cil. Ao considerar a sincronia dos recursos virtuais e f?sicos, se torna mais dif?cil efetuar esse mapeamento, inviabilizando o c?lculo da solu??o ?tima em ambientes reais. Sendo assim, abordagens heur?sticas s?o necess?rias para encontrar solu??es semi-?timas de maneira mais r?pida. Neste trabalho s?o adaptadas quatro abordagens heur?sticas para efetuar o mapeamento de redes virtuais de sincronia h?brida. Para avaliar o desempenho dessas heur?sticas foram efetuados dois conjuntos de experimentos. No primeiro conjunto de experimentos s?o comparadas as solu??es ?timas e as respectivas solu??es semi-?timas, os resultados indicaram que a efici?ncia das heur?sticas s?o melhores quando as requisi??es de redes virtuais s?o menores, al?m disso houveram alguns custos de solu??es semi-?timas equivalentes ao custo de mapeamento da solu??o ?tima. O segundo conjunto de experimento avalia o desempenho das heur?sticas utilizando um substrato de rede mais pr?ximo do contexto real e um maior n?mero de requisi??es de redes virtuais. Os resultados desse segundo experimento demonstram que mesmo com um n?mero maior de requisi??es de redes virtuais e um substrato maior, as solu??es foram calculadas em tempo aceit?vel.

Avec l’avènement de l’ère intellectuelle et de l’Internet of Everything (IoE), les besoins de la communication mondiale et des applications diverses ont explosé. Cette révolution exige que les futurs réseaux de communication soient plus efficaces, intellectuels, agiles et évolutifs. De nombreuses technologies réseau sont apparues pour répondre à la tendance des réseaux de communication de nouvelle génération tels que les réseaux optiques élastiques (EONs) et la virtualisation de réseau. De nombreux défis apparaissent avec les apparences de la nouvelle architecture et de la nouvelle technologie, telles que le routage et l’allocation de ressource spectrale (RSA) dans les EONs et l’intégration de réseaux virtuels (Virtual Network Embedding ou VNE) dans la virtualisation de réseau.Cette thèse traite la conception et l’analyse d’algorithmes d’approximation dans trois problèmes d’optimation du RSA et du VNE : les impacts de la distribution du trafic et de la topologie du réseau sur le routage tout optique, de l’allocation de ressource spectrale, et du VNE dans les topologies des chemins et cycles. Pour le routage tout optique, le premier sous-problème du RSA, il y a toujours un problème en suspens concernant l’impact de la distribution du trafic et de la topologie EON. Comme le routage tout optique joue un rôle essentiel pour la performance globale de la RSA, cette thèse fournit une analyse approfondi théorique sur ces impacts. Pour le deuxième sous-problème du RSA, l’allocation de ressource spectrale, deux chemins optiques quelconques partageant des fibres optiques communes pourraient devoir être isolés dans le domaine spectral avec une bande de garde appropriée pour empêcher la diaphonie et / ou réduire les menaces de sécurité de la couche physique. Cette thèse considère le scénario dans lequel les exigences de bandes de garde réelles optiques sont différentes pour différentes paires de chemins, et étudie comment affecter les ressources spectrales efficacement dans une telle situation. L’hétérogénéité de la topologie des demandes de réseau virtuel (VNR) est un facteur important qui entrave les performances de la VNE. Cependant, dans de nombreuses applications spécialisées, les VNR ont des caractéristiques structurelles communes par exemple, des chemins et des cycles. Pour obtenir de meilleurs résultats, il est donc essentiel de concevoir des algorithmes dédiés pour ces applications en tenant compte des caractéristiques topologiques. Dans cette thèse, nous prouvons que les problèmes VNE dans les topologies de chemin et de cycle sont NP-difficiles. Afin de les résoudre, nous proposons des algorithmes efficaces également analysons leurs ratios d’approximation
With the coming of intellectual era and Internet of Everything (IoE), the needs of worldwide communication and diverse applications have been explosively growing. This information revolution requires the future communication networks to be more efficient, intellectual, agile and scalable. Many technologies have emerged to meet the requirements of next generation communication networks such as Elastic Optical Networks (EONs) and networking virtualization. However, there are many challenges coming along with them, such as Routing and Spectrum Assignment (RSA) in EONs and Virtual Network Embedding (VNE) in network virtualization. This dissertation addresses the algorithm design and analysis for these challenging problems: the impacts of traffic distribution and network topology on lightpath routing, the distance spectrum assignment and the VNE problem for paths and cycles.For lightpath routing, the first subproblem of the RSA, there is always a pending issue that how the changes of the traffic distribution and EON topology affect it. As the lightpath routing plays a critical role in the overall performance of the RSA, this dissertation provides a thoroughly theoretical analysis on the impacts of the aforementioned two key factors. To this end, we propose two theoretical chains, and derive the optimal routing scheme taking into account two key factors. We then treat the second subproblem of RSA, namely spectrum assignment. Any two lightpaths sharing common fiber links might have to be isolated in the spectrum domain with a proper guard-band to prevent crosstalk and/or reduce physical-layer security threats. We consider the scenario with diverse guard-band sizes, and investigate how to assign the spectrum resources efficiently in such a situation. We provide the upper and lower bounds for the optimal solution of the DSA, and further devise an efficient algorithm which can guarantee approximation ratios in some graph classes.The topology heterogeneity of Virtual Network Requests (VNRs) is one important factor hampering the performance of the VNE. However, in many specialized applications, the VNRs are of some common structural features e.g., paths and cycles. To achieve better outcomes, it is thus critical to design dedicated algorithms for these applications by accounting for topology characteristics. We prove the NP-Harness of path and cycle embeddings. To solve them, we propose some efficient algorithms and analyze their approximation ratios

Dans cette thèse, nous nous intéressons à plusieurs problèmes liés à la conception de réseaux géométriques et aux plongements isométriques dans le plan.Nous commençons par étudier la généralisation du problème du réseau de Manhattan classique aux plans normés. Étant donné un ensemble de terminaux, nous recherchons le réseau de longueur totale minimum qui connecte chaque paire de terminaux par un plus court chemin dans la métrique définie par la norme. Nous proposons un algorithme d'approximation facteur 2.5 pour ce problème en temps O(mn^3) avec n le nombre de terminaux et m le nombre de directions de la boule unitaire. Le deuxième problème étudié est une version orientée des réseaux de Manhattan dont le but est de construire un réseau orienté de taille minimum dans lequel pour chaque paire de terminaux u, v est relié par un plus court chemin rectilinéaire de u vers v et un autre de v vers u. Nous proposons un algorithme d'approximation facteur 2 pour ce problème en temps O(n^3) où n est le nombre de terminaux.Nous nous intéressons ensuite à la recherche d'un spanner (un sous-graphe approximant les distances) planaire pour les graphes de disques unitaires (UDG) qui modélise les réseaux ad hoc sans fils. Nous présentons un algorithme qui construit un spanner planaire avec un facteur d'étirement constant en terme de distance de graphe pour UDG. Cet algorithme utilise uniquement des propriétés locales et peut donc être implémenté de manière distribuée.Finalement nous étudions le problème de la reconnaissance des espaces plongeables isométriquement dans le plan l_1 pour lequel nous proposons un algorithme en temps optimal O(n^2) pour sa résolution, ainsi que la généralisation de ce problème aux plans normés dont la boule unitaire est un polygone convexe central symétrique
In this thesis, we study several problems related to the design of geometric networks and isometric embeddings into the plane.We start by considering the generalization of the classical Minimum Manhattan Network problem to all normed planes. We search the minimum network that connects each pair of terminals by a shortest path in this norm. We propose a factor 2.5 approximation algorithm in time O(mn^3), where n is the number of terminals and m is the number of directions of the unit ball.The second problem presented is an oriented version of the minumum Manhattan Network problem, we want to obtain a minimum oriented network such that for each pair u, v of terminals, there is a shortest rectilinear path from u to v and another path from v to u.We describe a factor 2 approximation algorithm with complexity O(n^3) where n is the number of terminals for this problem.Then we study the problem of finding a planar spanner (a subgraph which approximates the distances) of the Unit Disk Graph (UDG) which is used to modelize wireless ad hoc networks. We present an algorithm for computing a constant hop stretch factor planar spanner for all UDG. This algorithm uses only local properties and it can be implemented in distributed manner.Finally, we study the problem of recognizing metric spaces that can be isometrically embbed into the rectilinear plane and we provide an optimal time O(n^2) algorithm to solve this problem. We also study the generalization of this problem to all normed planes whose unit ball is a centrally symmetric convex polygon

In today’s society services centered around voices are gaining popularity. Being able to provide the users with voices they like, to obtain and sustain their attention, is of importance for enhancing the overall experience of the service. Finding an efficient way of representing voices such that similarity comparisons can be performed is therefore of great use. In the field of Natural Language Processing great progress has been made using embeddings from Deep Learning models to represent words in an unsupervised fashion. These representations managed to capture the semantics of the words. This thesis sets out to explore whether such embeddings can be found for audio data as well, more specifically voices from narrators of audiobooks, that captures similarities between different voices. For this two different Convolutional Neural Networks are developed and evaluated, trained on spectrogram representations of the voices. One is performing regular classification while the other one uses pairwise relationships and a Kullback–Leibler divergence based loss function, in an attempt to minimize and maximize the difference of the output between similar and dissimilar pairs of samples. From these models the embeddings used to represent each sample are extracted from the different layers of the fully connected part of the network during the evaluation. Both an objective and a subjective evaluation is performed. During the objective evaluation of the models it is first investigated whether the found embeddings are distinct for the different narrators, as well as if the embeddings do encode information about gender. The regular classification model is then further evaluated through a user test, as it achieved an order of magnitude better results during the objective evaluation. The user test sets out to evaluate whether the found embeddings capture information based on perceived similarity. It is concluded that the proposed approach has the potential to be used for representing voices in a way such that similarity is encoded, although more extensive testing, research and evaluation has to be performed to know for sure. For future work it is proposed to perform more sophisticated pre-proceessing of the data and also to collect and include data about relationships between voices during the training of the models.
I dagens samhälle ökar populariteten för röstbaserade tjänster. Att kunna förse användare med röster de tycker om, för att fånga och behålla deras uppmärksamhet, är därför viktigt för att förbättra användarupplevelsen. Att hitta ett effektiv sätt att representera röster, så att likheter mellan dessa kan jämföras, är därför av stor nytta. Inom fältet språkteknologi i maskininlärning har stora framstegs gjorts genom att skapa representationer av ord från de inre lagren av neurala nätverk, så kallade neurala nätverksinbäddningar. Dessa representationer har visat sig innehålla semantiken av orden. Denna uppsats avser att undersöka huruvida liknande representationer kan hittas för ljuddata i form av berättarröster från ljudböcker, där likhet mellan röster fångas upp. För att undersöka detta utvecklades och utvärderades två faltningsnätverk som använde sig av spektrogramrepresentationer av röstdata. Den ena modellen är konstruerad som en vanlig klassificeringsmodell, tränad för att skilja mellan uppläsare i datasetet. Den andra modellen använder parvisa förhållanden mellan datapunkterna och en Kullback–Leibler divergensbaserad optimeringsfunktion, med syfte att minimera och maximera skillnaden mellan lika och olika par av datapunkter. Från dessa modeller används representationer från de olika lagren av nätverket för att representera varje datapunkt under utvärderingen. Både en objektiv och subjektiv utvärderingsmetod används. Under den objektiva utvärderingen undersöks först om de funna representationerna är distinkta för olika uppläsare, sedan undersöks även om dessa fångar upp information om uppläsarens kön. Den vanliga klassificeringsmodellen utvärderas också genom ett användartest, eftersom den modellen nådde en storleksordning bättre resultat under den objektiva utvärderingen. Syftet med användartestet var att undersöka om de funna representationerna innehåller information om den upplevda likheten mellan rösterna. Slutsatsen är att det föreslagna tillvägagångssättet har potential till att användas för att representera röster så att information om likhet fångas upp, men att det krävs mer omfattande testning, undersökning och utvärdering. För framtida studier föreslås mer sofistikerad förbehandling av data samt att samla in och använda sig av data kring förhållandet mellan röster under träningen av modellerna.

Person Re-Identification (ReID) is the process of associating images of the same person taken from different angles, cameras and at different times. The task is very challenging as a slight change in the appearance of the person can cause troubles in identifying them. In this thesis, the Re-Identification task is applied in the context of soccer games. In soccer games, the players of the same team wear the same outfit and colors, thus the task of Re-Identification is very hard. To address this problem, a state-of-the-art deep neural network based model named AlignedReID and a variation of it called Vanilla model are explored and compared to a baseline approach based on Euclidean distance in the image space. The AlignedReID model uses two feature extractor branches, one global and one local feature extractor. The Vanilla approach is a variation of the AlignedReID which uses only the global feature extractor branch of the AlignedReID. They are trained using two different loss functions, the Batch Hard and its soft-margin variation. The triplet loss is used, where for each loss calculation a triplet of images is used, an anchor, a positive pair (coming from the same person) and a negative pair. By comparing the metrics used for their evaluation, that is rank-1, rank-5, mean Average Precision (mAP) and the Area Under Curve (AUC), and by statistically comparing their mAPs which is assumed to be the most important metric, the AlignedReID model using the Batch Hard loss function outperforms the rest of the models with a mAP of 81\% and rank-1 \& rank-5 above 98\%. Also, a qualitative evaluation of the best model is presented using Grad-CAM, in order to figure how the model decides which images are similar by investigating in which parts of the images it focuses on to produce their embedding representations. It is observed that the model focuses on some discriminative features, such as face, legs and hands other than clothing color and outfit. The empirical results suggest that the AlignedReid is usable in real world applications, however further research to get a better understanding of the generalization to different cameras, leagues and other factors that may affect appearance would be interesting.

Textual data is one of the most widespread forms of data and the amount of such data available in the world increases at a rapid rate. Text can be understood as either a sequence of characters or words, where the latter approach is the most common. With the breakthroughs within the area of applied artificial intelligence in recent years, more and more tasks are aided by automatic processing of text in various applications. The models introduced in the following sections rely on deep-learning sequence-processing in order to process and text to produce a regression algorithm for classification of what the text input refers to. We investigate and compare the performance of several model architectures along with different hyperparameters. The data set was provided by e-Avrop, a Swedish company which hosts a web platform for posting and bidding of public procurements. It consists of titles and descriptions of Swedish public procurements posted on the website of e-Avrop, along with the respective category/categories of each text. When the texts are described by several categories (multi label case) we suggest a deep learning sequence-processing regression algorithm, where a set of deep learning classifiers are used. Each model uses one of the several labels in the multi label case, along with the text input to produce a set of text - label observation pairs. The goal becomes to investigate whether these classifiers can carry out different levels of intent, an intent which should theoretically be imposed by the different training data sets used by each of the individual deep learning classifiers.
Data i form av text är en av de mest utbredda formerna av data och mängden tillgänglig textdata runt om i världen ökar i snabb takt. Text kan tolkas som en följd av bokstäver eller ord, där tolkning av text i form av ordföljder är absolut vanligast. Genombrott inom artificiell intelligens under de senaste åren har medfört att fler och fler arbetsuppgifter med koppling till text assisteras av automatisk textbearbetning. Modellerna som introduceras i denna uppsats är baserade på djupa artificiella neuronnät med sekventiell bearbetning av textdata, som med hjälp av regression förutspår tillhörande ämnesområde för den inmatade texten. Flera modeller och tillhörande hyperparametrar utreds och jämförs enligt prestanda. Datamängden som använts är tillhandahållet av e-Avrop, ett svenskt företag som erbjuder en webbtjänst för offentliggörande och budgivning av offentliga upphandlingar. Datamängden består av titlar, beskrivningar samt tillhörande ämneskategorier för offentliga upphandlingar inom Sverige, tagna från e-Avrops webtjänst. När texterna är märkta med ett flertal kategorier, föreslås en algoritm baserad på ett djupt artificiellt neuronnät med sekventiell bearbetning, där en mängd klassificeringsmodeller används. Varje sådan modell använder en av de märkta kategorierna tillsammans med den tillhörande texten, som skapar en mängd av text - kategori par. Målet är att utreda huruvida dessa klassificerare kan uppvisa olika former av uppsåt som teoretiskt sett borde vara medfört från de olika datamängderna modellerna mottagit.

L’informatique en nuage (Cloud computing) est une technologie prometteuse facilitant la réservation et de l'utilisation des ressources d’une manière flexible et dynamique. En plus des ressources informatiques traditionnelles, les utilisateurs du Cloud attendent à ce que des ressources réseaux leurs soient dédiées afin de faciliter le déploiement des fonctions et services réseau. Ils souhaitent pouvoir gérer l'ensemble d'un réseau virtuel (VN) ou infrastructure. Ainsi, les fournisseurs du Cloud doivent déployer des solutions de provisionnement des ressources dynamiques et adaptatives afin d’allouer des réseaux virtuels qui reflètent les besoins variables dans le temps des applications hébergés dans le Cloud. L’état de l’art sur l’allocation des réseaux virtuels s’est uniquement intéressé au problème de mapping des nœuds et liens virtuels composant une demande de réseau virtuel dans les nœuds et chemins du réseau de physique (infrastructure Cloud), connu sous le nom du problème de virtual network embedding (VNE). Peu d'attention a été accordée à la gestion des ressources allouées pour répondre en permanence aux besoins variables des réseaux virtuels hébergés dans le réseau physique et afin d'assurer une utilisation efficace des ressources. L'objectif de cette thèse est de permettre l'allocation des réseaux virtuels d’une manière dynamique et préventive pour faire face aux fluctuations de la demande au cours de la durée de vie du réseau virtuel, et pour améliorer l'utilisation des ressources du substrat. Pour atteindre ces objectifs, la thèse propose d'adaptation des algorithmes d'allocation des ressources pour répondre à l’évolution des demandes du réseau virtuel. Premièrement, nous allons étudier en profondeur l'extension d'un nœud virtuel, à savoir le cas où un nœud virtuel hébergé nécessite plus de ressources alors le nœud physique qui l’héberge n'a pas assez de ressources disponibles. Deuxièmement, nous allons améliorer la proposition précédente afin de considérer la rentabilité du réseau de substrat. Et enfin, nous allons gérer la variation de la demande en bande passante dans les liens virtuels. Par conséquent, la première partie de cette thèse fournit un algorithme heuristique qui traite la fluctuation de la demande dans les nœuds virtuels. L'idée principale de l'algorithme est de réallouer un ou plusieurs nœuds virtuels co-localisés dans du nœud de substrat, qui héberge le nœud en évolution pour libérer des ressources (ou faire de la place) pour le nœud en évolution. En plus de réduire le coût de réaffectation, notre proposition prend en compte et réduit l'interruption de service pendant la migration. L'algorithme précédent a été étendu pour concevoir un algorithme de reconfiguration préventif pour améliorer la rentabilité du réseau physique. En fait, notre proposition profite de la perturbation de la demande de ressources pour ranger le réseau physique à un coût minimal et sans perturbations. Lors de la réaffectation des nœuds virtuels pour faire place pour le nœud en extension, nous réaffectant les liens virtuels les plus congestionnées dans des ressources physiques moins saturées afin d’équilibrer la charge sur le réseau. Notre proposition offre le meilleur compromis entre le coût de réaffectation et l'équilibrage des charges. Enfin, un framework distribué, parallèle et à vue locale a été mis au point pour traiter toutes les formes de fluctuations de la demande en bande passante dans les liens virtuels. Elle se compose d'un contrôleur et trois algorithmes exécutés dans chaque nœud du substrat d'une manière distribuée et parallèle. Le framework est basé sur l'auto-stabilisation, et peut gérer de nombreuses et différentes formes de variations de la demande de bande passante simultanément
Cloud computing is a promising technology enabling IT resources reservation and utilization on a pay-as-you-go manner. In addition to the traditional computing resources, cloud tenants expect compete networking of their dedicated resources to easily deploy network functions and services. They need to manage an entire Virtual Network (VN) or infrastructure. Thus, Cloud providers should deploy dynamic and adaptive resource provisioning solutions to allocate virtual networks that reflect the time-varying needs of Cloud-hosted applications. Prior work on virtual network resource provisioning only focused on the problem of mapping the virtual nodes and links composing a virtual network request to the substrate network nodes and paths, known as the Virtual network embedding (VNE) problem. Little attention was paid to the resource management of the allocated resources to continuously meet the varying demands of embedded virtual networks and to ensure efficient substrate resource utilization. The aim of this thesis is to enable dynamic and preventive virtual network resources provisioning to deal with demand fluctuation during the virtual network lifetime, and to enhance the substrate resources usage. To reach these goals, the thesis proposes adaptive resource allocation algorithms for evolving virtual network requests. We adress the extension of an embedded virtual node requiring more resources and consider the substrate network profitability. We also deal with the bandwidth demand variation in embedded virtual links. We first provide a heuristic algorithm to deal with virtual nodes demand fluctuation. The work is extended by designing a preventive re-configuration scheme to enhance substrate network profitability. Finally, a distributed, local-view and parallel framework was devised to handle embedded virtual links bandwidth fluctuations. The approach is composed of a controller and three algorithms running in each substrate node in a distributed and parallel manner. The framework is based on the self-stabilization approach, and can manage various forms of bandwidth demand variations simultaneously

Current systems for counting cars on parking lots usually use specialized equipment, such as barriers at the parking lot entrance. Usage of such equipment is not suitable for free or residential parking areas. However, even in these car parks, it can help keep track of their occupancy and other data. The system designed in this thesis uses the YOLOv4 model for visual detection of cars in photos. It then calculates an embedding vector for each vehicle, which is used to describe cars and compare whether the car has changed over time at the same parking spot. This information is stored in the database and used to calculate various statistical values like total cars count, average occupancy, or average stay time. These values can be retrieved using REST API or be viewed in the web application.

L'importanza di metodi automatici per la classificazione ed estrazione di informazioni da testi è cresciuta significativamente negli ultimi anni, a causa della produzione sempre maggiore di questo tipo di dati, specialmente tramite piattaforme web. Questo ha portato allo sviluppo di nuovi algoritmi per analizzare testi non strutturati. Le tecniche di "Embedding", che associano parole o parti di testo di lunghezza variabile a vettori di dimensione fissa mantenendo relazioni di similarità semantica, sono state un grande progresso per il campo del "Natural Language Processing". Inoltre, avanzamenti nelle tecniche di Deep Learning hanno migliorato significativamente la classificazione del testo, grazie agli affinamenti delle architetture delle reti neurali ricorrenti, in grado di processare sequenze di dimensioni variabili. Lo scopo di questo lavoro è stata la realizzazione di un prototipo che utilizzasse le tecniche citate per classificare documenti ed estrarre parti di testo. Il dominio di riferimento era composto da documenti amministrativi redatti da notai. Per la classificazione sono state utilizzate reti ricorrenti di tipo LSTM, e due tipologie di "embedding": a livello di parole ed a livello di frase. La prima tecnica è risultata più performante sull'insieme dei documenti di test, raggiungendo il 98,8% di accuratezza, mentre la seconda si è fermata al 96,7%. L'estrazione di parti rilevanti del testo è stata impostata come un problema di classificazione multi classe a livello della singola frase, utilizzando "word embedding" e reti ricorrenti LSTM. Complessivamente l'accuratezza ha raggiunto l'85,5% sull'insieme di test, mostrando però risultati non uniformi sulle singole classi. Tuttavia, si è rilevata una confusione ridotta tra le classi che rappresentavano le informazioni da estrarre. I modelli predittivi sono stati integrati in un prototipo, che ha permesso di verificare anche qualitativamente le buone prestazioni delle tecniche impiegate.

碩士
國立臺灣大學
資訊網路與多媒體研究所
105
Network embedding is used for extracting the feature representations of a network and benefits many machine learning tasks, such as classification, link prediction, etc. This model embeds the interactions among the vertices into the low-dimension representations, which greatly preserve the relations of the vertices. However, to simplify the learning procedure, most previous work treats all the vertices as the same type and thus ignores the interaction type of two vertices in different fields. In the light of this, we propose a field-aware network embedding model which can separately embed the distinct kinds of the interactions into the learned representations. Our experimental results show that integrating such field-aware information indeed improves the performance of the state-of-the-art network embedding algorithm.

碩士
國立臺灣大學
電機工程學研究所
107
Static network embedding has been widely studied to convert the sparse structure information to a dense latent space for various applications. However, real networks are continuously evolving, and deriving the whole embedding for every snapshot is computationally intensive. In this paper, therefore, we explore streaming network embedding to 1) efficiently identify the nodes required to update the embeddings under multi-type network changes and 2) carefully revise the embeddings to maintain transduction over different parts of the network. Specifically, we propose a new representation learning framework, named Graph Memory Refreshing (GMR), to preserve both structural information and embedding consistency for streaming network embedding. We prove that GMR is more consistent than other state-of-the-art methods. Experimental results manifest that GMR outperforms the baselines in both the accuracy and the running time.

Tese de mestrado, Engenharia Informática (Arquitectura, Sistemas e Redes de Computadores) Universidade de Lisboa, Faculdade de Ciências, 2016
A virtualização de redes tornou-se uma técnica poderosa que permite que várias redes virtuais, criadas por diferentes utilizadores, operem numa infraestrutura partilhada. Com o avanço de tecnologias como Redes Definidas por Software1, a virtualização de redes ganhou um novo ímpeto e tornou-se uma funcionalidade central em ambientes de computação em nuvem. Um dos grandes desafios que a virtualização de redes apresenta é como utilizar de forma eficiente os recursos oferecidos pelas redes físicas dos fornecedores de infraestruturas, nomeadamente os nós - entidades de uma rede com capacidade computacional – e ligações – entidades de uma rede que transportam dados entre pares de nós. De forma a resolver este problema, vários trabalhos da área de virtualização de redes têm sido desenvolvidos [1]. Em particular, têm sido propostos algoritmos que encontram formas eficazes para decidir onde mapear os nós e as ligações virtuais na rede física. Estes algoritmos podem assumir uma de três aproximações diferentes: soluções exatas, que resolvem pequenas instâncias do problema e encontram soluções ótimas para a localização dos recursos virtuais na rede física; soluções baseadas em heurísticas, que se focam em obter um bom resultado, próximo do ótimo, em pouco tempo; e meta-heurísticas, que usam técnicas específicas independentes do problema para achar um resultado próximo do ótimo. Tipicamente o objetivo destes algoritmos é achar estes mapeamentos tendo em conta determinadas métricas, como qualidade de serviço, custos económicos ou confiabilidade. Neste contexto, uma das métricas menos exploradas é a garantia da segurança das redes virtuais, um tema que é cada vez mais importante, especialmente em ambientes de computação em nuvem. As plataformas de virtualização propostas recentemente dão aos utilizadores a liberdade para especificarem de forma arbitrária as topologias virtuais para as suas redes e esquemas de endereçamento. Estas plataformas têm sido desenvolvidas considerando apenas um provedor de nuvem, forçando os clientes a confiarem que este provedor mantém os seus dados e cargas de trabalho seguros e disponíveis. Infelizmente, existem evidências de que problemas nestes ambientes ocorrem, tanto de natureza maliciosa (ataques causados através de algum elemento corrompido na rede) como benigna (falhas em elementos individuais da rede, ou falhas causadas, por exemplo, por catástrofes, afetando vários elementos da rede em simultâneo) [2]. Deste modo, nesta tese defendemos que a segurança e a confiabilidade são dois fatores críticos e, por isso, devem ser considerados durante o processo de mapeamento das redes virtuais. Nesse sentido, neste trabalho definimos um problema denominado Mapeamento de Redes Virtuais Seguro e Confiável, e construímos um algoritmo que resolve este problema num ambiente constituído por várias nuvens (i.e., múltiplos provedores de recursos físicos). Ao considerar-se um ambiente como este, evita-se que o cliente fique restringido a apenas um provedor, aumentando a possibilidade de a sua rede e o seu serviço resistirem a falhas em elementos da rede física ou interrupções numa nuvem, através da replicação dos serviços por diversas nuvens. A segurança das redes virtuais também é melhorada na medida em que os serviços mais sensíveis podem ser colocados em nuvens que oferecem maiores garantias de segurança. O problema em si tem como principal objetivo mapear redes virtuais sobre a rede física, distribuída potencialmente por diferentes nuvens, utilizando a menor quantidade de recursos, e satisfazendo, ao mesmo tempo, os seguintes requisitos: (i) cada nó e ligação virtual é mapeado na rede física satisfazendo os requisitos de capacidade de computação e de largura de banda, respetivamente, e também os requisitos de segurança e confiabilidade associados; (ii) cada nó virtual ´e mapeado num nó físico cuja localização satisfaz os requisitos do primeiro (isto é, se por exemplo um nó virtual procura uma nuvem que forneça um nível de máxima segurança, o nó físico que será alocado tem de pertencer a uma nuvem com essa característica); (iii) a rede virtual está protegida contra erros na rede física ou disrupção numa nuvem, de modo a cumprir os requisitos de confiabilidade. O algoritmo que apresentamos nesta tese cobre todos os requisitos deste problema, juntando, pela primeira vez, as propriedades segurança e confiabilidade. Adicionalmente, esta solução considera um ambiente de múltiplos domínios (neste caso, múltiplas nuvens), de maneira a eliminar eventuais limitações que surgem quando se usa um único provedor de nuvem. A solução criada é uma solução exata, desenvolvida através de uma técnica de otimização de programação inteira mista, e tem como objetivo minimizar os custos de mapeamento de redes virtuais, cobrindo sempre os seus requisitos de segurança e confiabilidade. Nesta solução são definidas diversas restrições que têm de ser cumpridas para que uma rede virtual possa ser mapeada sobre uma rede física. O nosso algoritmo oferece vários níveis de segurança e confiabilidade que podem ser escolhidos na definição das redes virtuais, nomeadamente associados aos nós e às ligações que as compõem. O cliente pode escolher arbitrariamente que níveis deseja para cada recurso virtual, para além de poder especificar também a topologia da sua rede e os requisitos de capacidade de computação e largura de banda para os nós e ligações, respetivamente. Sumariamente, nesta tese consideramos que são suportados vários níveis de segurança para os nós e ligações virtuais, que vão desde segurança por omissão, isto é, garantias mínimas de segurança, até à inclusão de mecanismos criptográficos que garantem maior segurança. Em relação à confiabilidade, os clientes podem optar por adicionar redundância aos seus recursos virtuais de modo a tolerar falhas. Quando é requisitada redundância, os clientes podem escolher, para cada nó virtual, se desejam a respetiva reserva adicional na mesma nuvem onde se encontra o nó primário, tolerando apenas falhas locais, ou localizada noutra nuvem, com o intuito de aumentar a probabilidade de a sua rede virtual sobreviver a uma disrupção¸ ao de uma nuvem. Na nossa solução, as nuvens são também distinguidas entre si consoante o nível de confiança que fornecem ao cliente. Podem ser consideradas nuvens públicas (pertencentes a provedores), privadas (pertencentes aos próprios clientes), entre outras. A definição de diferentes tipos de nuvem dá a possibilidade ao cliente de escolher as nuvens consoante a sensibilidade da sua informação. Nesta tese é ainda apresentada uma interface de programação de aplicações, que fornece como funcionalidade o mapeamento de redes virtuais segura e confiável, e que pode ser utilizada por plataformas de virtualização que tenham em conta ambientes de múltiplos domínios [3]. Quanto aos resultados, quando segurança e confiabilidade são requisitadas pelas redes virtuais, os mesmos mostram que existe um custo adicional (já esperado) para fornecer estas propriedades. No entanto, um ligeiro ajuste no preço dos recursos permite aos fornecedores de infraestruturas que fornecem segurança e confiabilidade obter um lucro semelhante (ou superior) ao dos fornecedores que não fornecem este tipo de propriedades. Os resultados mostram ainda que o nosso algoritmo se comporta de maneira similar ao algoritmo mais utilizado para mapeamento de redes virtuais, D-ViNE [4, 5], quando os requisitos de segurança e confiabilidade não são considerados. Apesar de serem uma boa base para novos trabalhos na área, as soluções exatas Não escalam (este tipo de soluções apenas consegue resolver problemas num tempo razoável se estes forem de pequena escala). Deste modo, como trabalho futuro, o primeiro caminho a tomar será o desenvolvimento de uma heurística que garanta as propriedades de segurança e confiabilidade.
Network virtualization is emerging as a powerful technique to allow multiple virtual networks (VN), eventually specified by different tenants, to run on a shared infrastructure. With the recent advances on Software Defined Networks (SDN), network virtualization – traditionally limited to Virtual Local Area Networks (VLAN) – has gained new traction. A major challenge in network virtualization is how to make efficient use of the shared resources. Virtual network embedding (VNE) addresses this problem by finding an effective mapping of the virtual nodes and links onto the substrate network (SN). VNE has been studied in the network virtualization literature, with several different algorithms having been proposed to solve the problem. Typically, these algorithms address various requirements, such as quality of service (QoS), economic costs or dependability. A mostly unexplored perspective on this problem is providing security assurances, a gap increasingly more relevant to organizations, as they move their critical services to the cloud. Recently proposed virtualization platforms give tenants the freedom to specify their network topologies and addressing schemes. These platforms have been targeting only a datacenter of a single cloud provider, forcing complete trust on the provider to run the workloads correctly and limiting dependability. Unfortunately, there is increasing evidence that problems do occur at a cloud scale, of both malicious and benign natures. Thus, in this thesis we argue that security and dependability is becoming a critical factor that should be considered by VNE algorithms. Motivated by this, we define the secure and dependable VNE problem, and design an algorithm that addresses this problem in multiple cloud environments. By not relying on a single cloud we avoid internet-scale single points of failures, ensuring the recovery from cloud outages by replicating workloads across providers. Our solution can also enhance security by leaving sensitive workloads in more secure clouds: for instance, in private clouds under control of the user or in facilities that employ the required security features. The results from our experiments show that there is a cost in providing security and availability that may reduce the provider profit. However, a relatively small increase in the price of the richer features of our solution (e.g., security resources) enables the provider to offer secure and dependable network services at a profit. Our experiments also show that our algorithm behaves similarly to the most commonly used VNE algorithm when security and dependability are not requested by VNs.

碩士
國立臺灣大學
資訊工程學研究所
106
This paper introduces network embedding into phone call graph which is more useful in many AI tasks than extracts features manually. However, most of existing methods of network embedding could not precisely capture all of the information of the phone call graph. In this paper, we propose a new perspective for phone call graph embedding called Phone2vec, which optimizes a new loss function with call frequency and call duration considered. The experiment results and the further analysis show that the proposed method capture both attribute indeed and makes a substantial improvement against the state-of-the-art baselines.

碩士
國立臺灣大學
資訊工程學研究所
106
This work studies the problem of embedding knowledge graph into low-dimensional vector space, which is very useful in many AI tasks. However, most existing methods could not precisely and flexibly characterize knowledge graph in its relation mapping properties such as one-to-many, many-to-one, and many-to-many, and could not efficiently find extra hidden relative entities for a given relationship. In this work, we propose a novel perspective for knowledge graph embedding by maximizing the probability of observed graph named ”TransPN”, which can well preserve the variety of complex relations by using the bidirectional translation and dynamical relation projection. Moreover, we are the first to introduce virtual adversarial training to enhance the robustness of our embedding results named ”TransPN-Adv”. The experiment results show that the proposed method makes a substantial improvement against the state-of-the-art baselines.

Network virtualization is a technology that enables multiple virtual instances to coexist on a common physical network infrastructure. This paradigm fostered new business models, allowing infrastructure providers to lease or share their physical resources. Each virtual network is isolated and can be customized to support a new class of customers and applications. To this end, infrastructure providers need to embed virtual networks on their infrastructure. The virtual network embedding is the (NP-hard) problem of matching constrained virtual networks onto a physical network. Heuristics to solve the embedding problem have exploited several policies under different settings. For example, centralized solutions have been devised for small enterprise physical networks, while distributed solutions have been proposed over larger federated wide-area networks. In this thesis we present a policy-based architecture for the virtual network embedding problem. By policy, we mean a variant aspect of any of the three (invariant) embedding mechanisms: physical resource discovery, virtual network mapping, and allocation on the physical infrastructure. Our architecture adapts to different scenarios by instantiating appropriate policies, and has bounds on embedding efficiency, and on convergence embedding time, over a single provider, or across multiple federated providers. The performance of representative novel and existing policy configurations are compared via extensive simulations, and over a prototype implementation. We also present an object model as a foundation for a protocol specification, and we release a testbed to enable users to test their own embedding policies, and to run applications within their virtual networks. The testbed uses a Linux system architecture to reserve virtual node and link capacities.

碩士
國立清華大學
資訊工程學系
103
Network virtualization is a technology which allows multiple heterogeneous virtual networks (VNs) to coexist on one substrate network (SN) at the same time and makes the internet more flexible and manageable. The main challenge for network virtualization is how to map a VN to a SN efficiently, which is known as the virtual network embedding (VNE) problem. VNE problem is proved as an NP-Hard problem, previous works have presented several heuristic algorithms to solve VNE problem. In this thesis, we present a virtual network embedding algorithm which is focus on minimizing the average path length of the virtual links. Unlike the two-stage algorithm, our algorithm adopts node mapping and link mapping in the same time. Our algorithm maps the largest adjacent bandwidth virtual node to SN then map the virtual links to the substrate shortest paths which has the maximum bottleneck bandwidth. Simulation results show that our algorithm has better mapping successful rate and shorter average path length of the virtual links than others.