A model for virtual network embedding using Artificial Bee Colony

In a network virtualization environment, a significant research problem is that of virtual network embedding. As the network virtualization system is distributed in nature, an effective solution on how to optimally embed a dynamically generated virtual network request on the substrate networks that are owned and managed by multiple infrastructure providers needs proper attention. The problem is computationally hard, and therefore, many approaches, implying heuristics/meta‐heuristics, have been applied for the same. A meta‐heuristic, Artificial Bee Colony algorithm is getting popular due to its robustness toward complex problem solving. A novel approach based on Artificial Bee Colony to address the dynamic virtual network embedding problem in a multiple infrastructure provider scenario is proposed in this work. Bee population is initialized by using a greedy heuristic in which the number of substrate networks together with virtual network requests constructs a bee. Generated solution, in the population, is improvised by using greedy selection that explores a local search method adopted by the bees. In greedy selection, the new candidate source is memorized by the bee if its fitness is better than the fitness of the existing source. The performance study of the proposed model is done by simulation over various metrics such as embedding cost, embedding time, and acceptance ratio. A comparative study is conducted with other nature‐inspired virtual network embedding algorithms on these metrics. The findings affirm that the proposed virtual network embedding approach performs well and produces better results.     

Layer 1 Virtual Private Networks in Multidomain Next-Generation Networks

High-capacity e-science and consumer applications require transport networks that are dynamically provisioned. Rapid advances in next-generation SONET/SPH and optical switching along with GMPLS control have enabled many new services' provisioning capabilities. In particular, a key paradigm is the new layer 1 virtual private network framework, which allows clients to directly provision their own services without deploying expensive infrastructures. This article presents an overview of L1-VPN and describes a resource management scheme that will enable transport network virtualization across a multidomain network infrastructure. The scheme is implemented in both centralized and distributed control frameworks, and allows for dynamic sharing of transport resources. A case study of performance analysis results is presented showing a distributed control plane in a multidomain network architecture achieving higher VPN carrying capacity than a centralized control plane     

分布式环境中基于协商的虚拟网映射算法

网络虚拟化技术可以在共享的底层物理网络上为用户同时提供多种可定制的服务网络。目前的虚拟网映射算法比较依赖于集中式的管理节点,使其在可靠性和适用范围等方面存在诸多问题。为此,提出了一种分布式环境下的虚拟网映射算法,该算法通过多个节点之间的相互协商来完成虚拟网的映射,并且在降低通信开销和缩短虚拟链路的路径长度方面进行了相应改进。实验结果表明,该算法与同类型算法相比,在资源利用率和通信开销方面具有一定的优越性。     

Power-aware virtual optical network provisioning in flexible bandwidth optical networks [Invited]

Considering the virtual network infrastructure as a service, optical network virtualization can facilitate the physical infrastructure sharing among different clients and applications that require optical network resources. Obviously, mapping multiple virtual network infrastructures onto the same physical network infrastructure is one of the greatest challenges related to optical network virtualization in flexible bandwidth optical networks. In order to efficiently address the virtual optical network (VON) provisioning problem, we can first obtain the virtual links’ order and the virtual nodes’ order based on their characteristics, such as the bandwidth requirement on virtual links and computing resources on virtual nodes. We then preconfigure the primary and backup paths for all node-pairs in the physical optical network, and the auxiliary graph is constructed by preconfiguring primary and backup paths. Two VON mapping approaches that include the power-aware virtual-links mapping (PVLM) approach and the power-aware virtual-nodes mapping (PVNM) approach are developed to reduce power consumption for a given set of VONs in flexible bandwidth optical networks with the distributed data centers. Simulation results show that our proposed PVLM approach can greatly reduce power consumption and save spectrum resources compared to the PVNM approach for the single-line rate and the mixed-line rate in flexible bandwidth optical networks with the distributed data centers.     

Construction and maintenance of virtual backbone in wireless networks

In ad hoc wireless networks, there is no predefined infrastructure and nodes communicate with each other via peer communications. In order to make routing efficient in such networks the connected dominating set (CDS) can act as virtual backbone for the network. A smaller virtual backbone suffers less from the interference problem and incurs less maintenance overhead. Computing minimum CDS backbone is proven to be NP-Hard, it is therefore desirable to use efficient heuristic algorithms to find a virtual backbone of small size. Diameter and average backbone path length (ABPL) are other major criteria for evaluation of the backbone produced by an algorithm. In this paper, after giving a brief survey of classical CDS algorithms, two new centralized algorithms are described for the construction of the virtual backbone and their performance has been compared with five recent algorithms (two centralized and three distributed) along the parameters: size, diameter, and ABPL. The new algorithms perform better on most of the criteria. The re-construction of entire CDS upon movement or failure of a few nodes is very costly in terms of processing power, battery utilization, bandwidth utilization etc., as compared to maintaining the CDS for the affected nodes, since the re-construction of the CDS is to be performed for the whole network while maintenance involves the affected nodes and their neighbours only. A new distributed algorithm is described that maintains the virtual backbone on movement or failure of a single node. The overhead of CDS maintenance with this algorithm compares very favourably against that of re-construction.     

A distributed mobility control scheme in LISP networks

The locator identifier separation protocol (LISP) has been made as an identifier-locator separation scheme for scalable Internet routing. However, the LISP was originally designed for fixed network environment, rather than for mobile network environment. In particular, the existing LISP mobility control schemes use a centralized map server to process all the control traffics, and thus they are intrinsically subject to some limitations in mobile environment, such as large overhead of mapping control traffics at central map server and degradation of handover performance. To overcome these problems, we propose a distributed mobility control scheme in LISP networks. In the proposed scheme, we assume that a mobile host has a hierarchical endpoint identifier which contains the information of its home network domain. Each domain has a distributed map server (DMS) for distributed mapping management of Endpoint Identifiers (EIDs) and Locators (LOCs). For roaming support, each DMS maintains a home EID register and a visiting EID register which are used to keep the EID-LOC mappings for mobile hosts in the distributed manner. For performance analysis, we compare the control traffic overhead (CTO) at map servers, the signaling delay required for EID-LOC mapping management, and the handover delay for the existing and proposed schemes. From numerical results, it is shown that the proposed distributed scheme can give better performance than the existing centralized schemes in terms of CTO, total signaling delay for EID-LOC mapping management, and handover delay.     

Distributed parallel algorithms for online virtual network embedding applications

Network virtualization (NV) has ubiquitously emerged as an indispensable attribute to enable the success of the forthcoming virtualized networks (eg, 5G network and smart Internet of Things [IoT]). Virtual network embedding (VNE) is the major challenge in NV that allows multiple heterogeneous virtual networks (VNs) to simultaneously coexist on a shared substrate infrastructure. A great number of VNE algorithms have been proposed, but over the past decades, most of them are only targeting for VNE node mapping. In this paper, we propose two distributed parallel genetic algorithms, which are based on two versions of crossover and mutation schemes, for online VN link embedding problems with low latency and high efficiency. Furthermore, we conduct a time analysis on the executing time of independently distributed parallel computing machines in details. This comprehensive analysis validates the parallel computing scalability on an identical number of predefined parallel machines. Extensive simulations have shown that our proposed algorithms can achieve better performance than integer linear programming (ILP)–based solutions while meeting the stringent time requirements for online VN embedding applications. Our proposed algorithms yield superior performance in running time with 32.78% up to 1727.8% faster than existing popular VNE algorithms. Additionally, the theoretical analysis indicates that the execution time can be reduced to logarithmic times by applying proposed distributed parallel algorithms.     

Distributed mapping management of identifiers and locators in mobile‐oriented Internet environment

Many schemes have recently been proposed for the separation of identifier (ID) and locator (LOC), which include the Host Identity Protocol, the Identifier‐Locator Network Protocol, and the Locator Identifier Separation Protocol. However, all of these schemes were originally designed in fixed network environment, rather than mobile network environment. In particular, these schemes are based on a centralized map server that is used as an anchor point for mobile nodes, and thus intrinsically subject to some limitations in a mobile environment. In this paper, we propose a distributed ID‐LOC mapping management scheme in a mobile‐oriented Internet environment. In the proposed scheme, we assume that a host has a globally unique and hierarchical Host ID (HID) that contains the information of its home network domain. Each network domain has a distributed map server for distributed management of ID‐LOC mappings. For roaming support, each distributed map server maintains its own home HID register and visiting HID register, which are used to keep the mappings of HID and LOCs for mobile nodes in the distributed manner. By performance analysis, it is shown that the proposed distributed scheme can give better performance than the existing centralized schemes in terms of ID‐LOC binding update and data delivery costs. Copyright © 2012 John Wiley & Sons, Ltd.     

Latency-driven distribution: infrastructure needs of participatory entertainment applications

This article evaluates network and server infrastructure requirements to support real-time flows associated with networked entertainment applications. These include the state information flow to update the status of the virtual environment and immersive communication flows such as voice, video, gesture, and haptics communication. The article demonstrates that scaling these applications to large geographical spreads of participants requires distribution of computation to meet the latency constraints of the applications. This latency-driven distribution of computation is essential even when there are no limitations on the availability of computational resources in one location. The article provides detailed results on distributed server architectures for two of these real-time flows, state information and immersive voice communication. It also identifies a generic set of requirements for the underlying network and server infrastructure to support these applications and propose a new design, called switched overlay networks, for this purpose.     

异构备份式的虚拟网映射方法研究

在云计算和数据中心环境中,底层单个物理服务器的失效将对上层虚拟网络的服务性能造成很大的影响,现有利用冗余备份的方法能够在一定程度上降低底层物理设备失效带来的影响,但未考虑到物理服务器的同构性所带来的问题,为此,该文提出一种异构备份式的虚拟网映射方法。首先,只对关键的虚拟机进行冗余备份,降低备份资源的开销;然后,确保提供备份虚拟机的物理服务器与原物理服务器的系统类型的异构性,提高虚拟网的弹性能力;最后,以最小化链路资源开销作为虚拟网的映射目标,进一步降低备份资源的开销。实验表明,该方法在保证虚拟网络映射性能的前提下,能够大大提高虚拟网络的弹性能力。     

OpenFlow网络测量分析系统的设计实现

OpenFlow网络目前缺少支持定量测量分析各种创新应用或机制的有效手段。以升级OpenFlow网络设备为具有本地日志功能的OpenFlow测量实体为基础,设计了一种基于集中式服务器控制测量实体进行分布式测量的机制,制定了其间的通信规程OpenFlow测量控制协议(OMCP),同时基于正则表达式、散列技术和可扩展的统计函数库等方式设计了一种分析测量日志的功能。原型系统的实验表明,OpenTrace服务器能够灵活部署和控制分布式测量任务,OpenTrace系统不仅能够定量地重现数据平面的数据流传输过程而且能够重现控制平面的控制事件交互过程,从而可为量化分析OpenFlow网络应用和新型机制提供广泛的性能数据。     

应对灾难风险的多虚拟机快速协同撤离机制研究

大规模灾难事件可能对通信网基础设施造成严重的威胁和破坏。针对大规模灾难风险下虚拟网的生存性问题,该文提出一种多虚拟机快速协同撤离(MRCE)机制。该机制采用后复制迁移技术实现虚拟机的在线迁移,通过基础迁移带宽的分配和升级,对属于同一虚拟网的多个风险虚拟机进行快速协同撤离,以减少单个虚拟网的撤离完成时长,降低损毁风险。仿真结果表明,该机制能在不同考察周期内获得较好的虚拟网撤离完成率和平均撤离完成时长。     

Distributed resource allocation for DS-CDMA-based multimedia ad hocwireless LANs

Power control in direct sequence code division multiple access (DS-CDMA) systems and power/rate allocation in multirate DS-CDMA based networks is an open and interesting research area which has attracted much attention. However, with a few exceptions, most researchers have emphasized centralized resource allocation algorithms for cellular systems where the base station keeps track of the requirements of the various users and is thus responsible for the management of network resources. Ad hoc wireless local area networks (WLANs), on the other hand, are generally configured as peer-to-peer networks with no centralized hub or controller. Thus resource allocation has to be conducted in a distributed fashion. We address the issue of distributed resource management for multirate DS-CDMA based multimedia WLANs by (1) presenting a distributed resource allocation protocol, known as distributed resource negotiation protocol (DRNP) that builds on the RTS/CTS bandwidth reservation mechanism provided by IEEE 802.111, and provides quality of service (QoS) guarantees through distributed control of resources in DS-CDMA based multimedia WLANs and (2) investigating the performance of various resource allocation schemes within the context of DRNP, in terms of network wide metrics such as overall throughput and blocking rates     

集中与分布:协同虚拟网络映射

结合传统集中式和分布式两类算法各自的特性,提出了协同虚拟网络映射算法。该算法保留了集中式算法中拥有全局视野的中心控制实体,负责总体控制和关键决策,同时将具体映射方案的计算过程交给有限的底层网络子集实现;唯一的中心控制实体与多个底层节点相互配合协作,共同完成虚拟网络映射的整个过程。该算法继承了集中式和分布式算法各自的优势,有效弥补了二者的缺陷,初步的仿真试验也证明了其可行性和有效性。     

基于多移动代理的网络性能管理系统

基于移动代理的网络性能管理,利用移动代理的移动性、智能性、灵活性和强大的扩展能力,通过对整个网络进行本地和全局的性能监控和性能数据采集,提供实时数据采集、分析和可视化工具,最终为管理员完成可视化的性能报告。能够对网络实施高效、实时和准确的性能管理,而且移动代理的平台无关性又可方便地实现跨平台的网络管理,在复杂网络的管理方面有着极大的优势。根据多移动代理的设计模式,借助于UML建模工具构建了一个性能管理系统,清晰地描述了该系统的静态和动态结构,克服了传统的集中式网络性能管理的诸多缺点。     

Maximizing the number of users in an interactive video-on-demand system

Video prefetching is a technique that has been proposed for the transmission of variable-bit-rate (VBR) videos over packet-switched networks. The objective of these protocols is to prefetch future frames at the customers' set-top box (STB) during light load periods. Experimental results have shown that video prefetching is very effective and it achieves much higher network utilization (and potentially larger number of simultaneous connections) than the traditional video smoothing schemes. The previously proposed prefetching algorithms, however, can only be efficiently implemented when there is one centralized server. In a distributed environment there is a large degradation in their performance. In this paper we introduce a new scheme that utilizes smoothing along with prefetching, to overcome the problem of distributed prefetching. We show that our scheme performs almost as well as the centralized prefetching protocol even though it is implemented in a distributed environment. In addition, we introduce a call admission control algorithm for a fully interactive video-on-demand (VoD) system that utilizes this concept of distributed video prefetching. Using the theory of effective bandwidths, we develop an admission control algorithm for new requests, based on the user's viewing behavior and the required quality of service (QoS).     

Connected Dominating Sets in Wireless Networks with Different Transmission Ranges

Since there is no fixed infrastructure or centralized management in wireless ad hoc networks, a Connected Dominating Set (CDS) has been proposed to serve as a virtual backbone. The CDS of a graph representing a network has a significant impact on the efficient design of routing protocols in wireless networks. This problem has been studied extensively in Unit Disk Graphs (UDG), in which all nodes have the same transmission ranges. However, in practice, the transmission ranges of all nodes are not necessarily equal. In this paper, we model a network as a disk graph and introduce the CDS problem in disk graphs. We present two efficient approximation algorithms to obtain a minimum CDS. The performance ratio of these algorithms is constant if the ratio of the maximum transmission range over the minimum transmission range in the network is bounded. These algorithms can be implemented as distributed algorithms. Furthermore, we show a size relationship between a maximal independent set and a CDS as well as a bound of the maximum number of independent neighbors of a node in disk graphs. The theoretical analysis and simulation results are also presented to verify our approaches.     

虚拟多天线无线传感器网络

提出一种基于虚拟多天线技术的分布式和协作的无线传感器网络,分析了该虚拟多天线无线传感器网络的性能。同点到点的无线传感器网络相比较,在天线传输信号能量相同的情况下,虚拟多天线无线传感器网络的误比特概率(BER)更小;或者在同样误比特概率情况下,虚拟多天线无线传感器网络的天线传输信号能量更低。这些特性能够提高无线传感器网络的性能或延长无线传感器网络的使用寿命。     

Distributed network computing over local ATM networks

Communication between processors has long been the bottleneck of distributed network computing. However, recent progress in switch-based high-speed local area networks (LANs) may be changing this situation. Asynchronous transfer mode (ATM) is one of the most widely-accepted and emerging high-speed network standards which can potentially satisfy the communication needs of distributed network computing. We investigate distributed network computing over local ATM networks. We first study the performance characteristics involving end-to-end communication in an environment that includes several types of workstations interconnected via a Fore Systems' ASX-100 ATM switch. We then compare the communication performance of four different application programming interfaces (APIs). The four APIs were Fore Systems' ATM API, the BSD socket programming interface, Sun's remote procedure call (RPC), and the parallel virtual machine (PVM) message passing library. Each API represents distributed programming at a different communication protocol layer. We evaluated two popular distributed applications, parallel matrix multiplication and parallel partial differential equations, over the local ATM network. The experimental results show that network computing is promising over local ATM networks, provided that the higher level protocols, device drivers, and network interfaces are improved     

Distributed Mapping Management of Identifiers and Locators in LISP-based Mobile Networks

The Locator Identifier Separation Protocol (LISP) has been proposed as an identifier-locator separation scheme for scalable Internet routing. However, LISP was originally designed in the fixed network environment rather than in the mobile network environment. In particular, the existing LISP mobility schemes are based on a centralized map server that is used as an anchor point for mobile nodes, and thus intrinsically subject to some limitations in mobile environment. In this paper, we propose a distributed mapping management of Endpoint Identifiers (EIDs) and Locators (LOCs) in mobile LISP networks. We use Routing LOC (RLOC) and Local LOC (LLOC) as locators for mobile hosts. RLOC represents the IP address of the domain gateway, and LLOC is the IP address of the access router that a host is currently attached to. For EID-LOC mapping management, each network domain has a Distributed Map Server (DMS) over its gateway. Each DMS keeps track of the EID-LOC mapping information for mobile hosts in the distributed way. The proposed scheme is also a network-based approach, in which each access router, instead of a host, performs the mapping management operations. From the performance analysis, we can see that the proposed distributed scheme can give better performance than the existing schemes in terms of the signaling delays required for EID-LOC mapping update and query operations.