Embedding of virtual network (VN) requests on top of a shared physical network poses an intriguing combination of theoretical and practical challenges. Two major problems with the state-of-the-art VN embedding algorithms are their indifference to the underlying substrate topology and their lack of re-optimization mechanisms for already embedded VN requests. We argue that topology-aware embedding together with re-optimization mechanisms can improve the performance of the previous VN embedding algorithms in terms of acceptance ratio and load balancing. The major contributions of this thesis are twofold: (1) we present a mechanism to differentiate among resources based on their importance in the substrate topology, and (2) we propose a set of algorithms for re-optimizing and re-embedding initially-rejected VN requests after fixing their bottleneck requirements. Through extensive simulations, we show that not only our techniques improve the acceptance ratio, but they also provide the added benefit of balancing load better than previous proposals. The metrics we use to validate our techniques are improvement in acceptance ratio, revenue-cost ratio, incurred cost, and distribution of utilization.

Embedding of virtual network (VN) requests on top of a shared physical network poses an intriguing combination of theoretical and practical challenges. Two major problems with the state-of-the-art VN embedding algorithms are their indifference to the underlying substrate topology and their lack of re-optimization mechanisms for already embedded VN requests. We argue that topology-aware embedding together with re-optimization mechanisms can improve the performance of the previous VN embedding algorithms in terms of acceptance ratio and load balancing. The major contributions of this thesis are twofold: (1) we present a mechanism to differentiate among resources based on their importance in the substrate topology, and (2) we propose a set of algorithms for re-optimizing and re-embedding initially-rejected VN requests after fixing their bottleneck requirements. Through extensive simulations, we show that not only our techniques improve the acceptance ratio, but they also provide the added benefit of balancing load better than previous proposals. The metrics we use to validate our techniques are improvement in acceptance ratio, revenue-cost ratio, incurred cost, and distribution of utilization.

Meshes and hypercubes are two most important communication and computation structures used in parallel computing. Network embedding problems for meshes and hypercubes on traditional network architectures have been intensively studied during the past years. With the emergence of new network architectures, the traditional network embedding results are not enough to solve the new requirements. The main objective of this thesis is to design efficient network embedding schemes for realizing meshes and hypercubes on a group of future network architectures. This thesis is organized into two parts. The first part focuses on embedding meshes/tori on a group of double-loop networks by evaluating the traditional embedding metrics, since double-loop networks have been intensively studied and proven to have many desirable properties for future network architecture. We propose a novel tessellation approach to partition the geometric plane of double-loop networks into a set of parallelogram tiles, called P-shape. Based on the characteristics of P-shape, we design a simple embedding scheme, namely P-shape embedding, that embeds arbitrary-shape meshes and tori on double-loop networks in a systematic way. A main merit of P-shape embedding is that a large fraction of embedded mesh/torus edges have edge dilation 1, resulting in a low average dilation. These are the first results, to our knowledge, on embedding meshes and tori on general doubleloop networks which is of great significance due to the popularity of these architectures. Our P-shape construction bridges between regular graphs and double-loop networks, and provides a powerful tool for studying the topological properties of double-loop networks. In the second part, we study efficient embedding schemes for realizing hypercubes on a group of array-basedWDMoptical networks by analyzing the new embedding metric of wavelength requirement, as WDM optical networking is becoming a promising technology for deployment in many applications in advanced telecommunication and parallel computing. We first design routing and wavelength assignments of both bidirectional and unidirectional hypercubes on WDM optical linear arrays, rings, meshes and tori with the consideration of communication directions. For each case, we identify a lower bound on the number of wavelengths required, and design the embedding scheme and wavelength assignment algorithm that uses a provably near-optimal number of wavelengths. To further reduce the wavelength requirement, we extend the results to WDM ring networks with additional links, namely WDM chordal rings. Based on our proposed embedding schemes, we provide the analysis of chord length with optimal number of wavelengths to realize hypercubes on 3-degree and 4-degree WDM chordal rings. Furthermore, we propose an embedding scheme for realizing dimensional hypercubes on WDM optical arrays by considering the hypercubes dimension by dimension, called lattice embedding, instead of embedding hypercubes with all dimensions. Based on lattice embedding, the number of wavelengths required to realize dimensional hypercube on WDM arrays can been significantly reduced compared to the previous results. By our embedding schemes, many communications and computations, originally designed based on hypercubes, can be directly implemented in WDM optical networks, and the wavelength requirements can be easily derived using our obtained results. / http://proxy.library.adelaide.edu.au/login?url= http://library.adelaide.edu.au/cgi-bin/Pwebrecon.cgi?BBID=1345349 / Thesis (Ph.D.) - University of Adelaide, School of Computer Science, 2008

Network virtualization can offer more flexibility and better manageability for the future Internet by allowing multiple heterogeneous virtual networks (VN) to coexist on a shared infrastructure provider (InP) network. A major challenge in this respect is the VN embedding problem that deals with the efficient mapping of virtual resources on InP network resources. Previous research focused on heuristic algorithms for the VN embedding problem assuming that the InP network remains operational at all times. In this thesis, we remove that assumption by formulating the survivable virtual network embedding (SVNE) problem and developing baseline policy heuristics and an efficient hybrid policy heuristic to solve it. The hybrid policy is based on a fast re-routing strategy and utilizes a pre-reserved quota for backup on each physical link. Our evaluation results show that our proposed heuristic for SVNE outperforms baseline heuristics in terms of long term business profit for the InP, acceptance ratio, bandwidth efficiency, and response time.

Network virtualization can offer more flexibility and better manageability for the future Internet by allowing multiple heterogeneous virtual networks (VN) to coexist on a shared infrastructure provider (InP) network. A major challenge in this respect is the VN embedding problem that deals with the efficient mapping of virtual resources on InP network resources. Previous research focused on heuristic algorithms for the VN embedding problem assuming that the InP network remains operational at all times. In this thesis, we remove that assumption by formulating the survivable virtual network embedding (SVNE) problem and developing baseline policy heuristics and an efficient hybrid policy heuristic to solve it. The hybrid policy is based on a fast re-routing strategy and utilizes a pre-reserved quota for backup on each physical link. Our evaluation results show that our proposed heuristic for SVNE outperforms baseline heuristics in terms of long term business profit for the InP, acceptance ratio, bandwidth efficiency, and response time.

No description available.

<p>Latent variable models are widely used in modern data science for both statistic and dynamic data. This thesis focuses on large-scale latent variable models formulated for time series data and static network data. The former refers to the state space model for dynamic systems, which models the evolution of latent state variables and the relationship between the latent state variables and observations. The latter refers to a network decoder model, which map a large network into a low-dimensional space of latent embedding vectors. Both problems can be solved by adaptive stochastic gradient Markov chain Monte Carlo (MCMC), which allows us to simulate the latent variables and estimate the model parameters in a simultaneous manner and thus facilitates the down-stream statistical inference from the data. </p> <p><br></p> <p>For the state space model, its challenge is on inference for high-dimensional, large scale and long series data. The existing algorithms, such as particle filter or sequential importance sampler, do not scale well to the dimension of the system and the sample size of the dataset, and often suffers from the sample degeneracy issue for long series data. To address the issue, the thesis proposes the stochastic approximation Langevinized ensemble Kalman filter (SA-LEnKF) for jointly estimating the states and unknown parameters of the dynamic system, where the parameters are estimated on the fly based on the state variables simulated by the LEnKF under the framework of stochastic approximation MCMC. Under mild conditions, we prove its consistency in parameter estimation and ergodicity in state variable simulations. The proposed algorithm can be used in uncertainty quantification for long series, large scale, and high-dimensional dynamic systems. Numerical results on simulated datasets and large real-world datasets indicate its superiority over the existing algorithms, and its great potential in statistical analysis of complex dynamic systems encountered in modern data science. </p> <p><br></p> <p>For the network embedding problem, an appropriate embedding dimension is hard to determine under the theoretical framework of the existing methods, where the embedding dimension is often considered as a tunable hyperparameter or a choice of common practice. The thesis proposes a novel network embedding method with a built-in mechanism for embedding dimension selection. The basic idea is to treat the embedding vectors as the latent inputs for a deep neural network (DNN) model. Then by an adaptive stochastic gradient MCMC algorithm, we can simulate of the embedding vectors and estimate the parameters of the DNN model in a simultaneous manner. By the theory of sparse deep learning, the embedding dimension can be determined via imposing an appropriate sparsity penalty on the DNN model. Experiments on real-world networks show that our method can perform dimension selection in network embedding and meanwhile preserve network structures. </p> <p><br></p>

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.

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.

Due to the existence of multiple stakeholders with conflicting goals and policies, alterations to the existing Internet architecture are now limited to simple incremental updates; deployment of any new, radically different technology is next to impossible. To fend off this ossification, network virtualization has been propounded as a diversifying attribute of the future inter-networking paradigm. In this talk, we provide an overview of the network virtualization environment (NVE) and address two basic problems in this emerging field of networking research. The identity management problem is primarily concerned with ensuring interoperability across heterogeneous identifier spaces for locating and identifying end hosts in different virtual networks. We describe the architectural and the functional components of a novel identity management framework (iMark) that enables end-to-end connectivity across heterogeneous virtual networks in the NVE without revoking their autonomy. The virtual network embedding problem deals with the mapping of virtual nodes and links onto physical network resources. We argue that the separation of the node mapping and the link mapping phases in the existing algorithms considerably reduces the solution space and degrades embedding quality. We propose coordinated node and link mapping to devise two algorithms (D-ViNE and R-ViNE) for the online version of the problem under realistic assumptions and compare their performance with the existing heuristics.