This paper addresses Connectivity-aware Virtual Network Embedding (CoViNE) problem, which consists in embedding a virtual network (VN) on a substrate network while ensuring VN connectivity (without any bandwidth guarantee) against multiple substrate link failures. CoViNE provides a weaker form of survivability incurring less resource overhead than traditional VN survivability models. To optimally solve CoViNE, we present an Integer Linear Program (ILP), namely CoViNE-opt. CoViNE-opt enumerates an exponential number of edge-cuts in a VN severely limiting its scalability. Therefore, we decompose CoViNE into three sub-problems: i) augmenting a VN with virtual links to provide necessary connectivity, ii) identifying the virtual links that should be embedded disjointly, and iii) computing a VN embedding while satisfying the disjointness constraints. We introduce conflicting set abstraction that allows to address sub-problems (i) and (ii) without enumerating all the edge-cuts of a VN. We propose two novel solutions to CoViNE leveraging conflicting set, namely CoViNE-ILP and CoViNE-fast. CoViNE-ILP uses a heuristic algorithm to address sub-problems (i) and (ii), while an ILP is used for sub-problem (iii). In contrast, CoViNE-fast uses heuristics for solving all three sub-problems. Through simulation, we evaluate the optimality and scalability of our solutions and demonstrate a failure restoration use-case enabled by CoViNE.

A key challenge in network virtualization is to efficiently map a virtual network (VN) on a substrate network (SN), while accounting for possible substrate failures. This is known as the survivable VN embedding (SVNE) problem. The state-of-the-art literature has studied the SVNE problem from infrastructure providers' (InPs') perspective, i.e., provisioning backup resources in the SN. A rather unexplored solution spectrum is to augment the VN with sufficient spare backup capacity to survive substrate failures and embed the resulting VN accordingly. Such augmentation enables InPs to offload failure recovery decisions to the VN operator, thus providing more flexible VN management. In this paper, we study the problem of jointly optimizing spare capacity allocation in a VN and embedding the VN to guarantee full bandwidth in the presence of multiple substrate link failures. We formulate the optimal solution to this problem as a quadratic integer program that we transform into an integer linear program. We also propose a heuristic algorithm to solve larger instances of the problem. Based on analytical study and simulation, our key findings are: 1) provisioning shared backup resources in the VN can yield ~33% more resource efficient embedding compared to doing the same at the SN level and 2) our heuristic allocates ~21% extra resources compared to the optimal, while executing several orders of magnitude faster.

Network virtualization (NV), considered as a key enabler for overcoming the ossification of the Internet allows multiple heterogeneous virtual networks to co-exist over the same substrate network. Resource allocation problems in NV have been extensively studied for single layer substrates such as IP or Optical networks. However, little effort has been put to address the same problem for multi-layer IP-over-optical networks. The increasing popularity of multi-layer networks for deploying backbones combined with their unique characteristics ( e.g., topological flexibility of the IP layer) calls for the need to carefully investigate the resource provisioning problems arising from their virtualization. In this paper, we address the problem of multi-layer virtual network embedding (MULE; similar to multi-layer networks, this hybrid species brings the best of two species together.) on IP-over-optical networks. We propose two solutions to MULE: 1) an integer linear program formulation for the optimal solution (OPT-MULE) and 2) a heuristic to address the computational complexity of the optimal solution (FAST-MULE). We demonstrate through extensive simulations that on average our heuristic performs within $\boldsymbol \approx 1.47\boldsymbol \times $ of optimal solution while executing several orders of magnitude faster. Simulation results also show that FAST-MULE incurs ≈66% less cost on average than the state-of-the-art heuristic while accepting ≈60% more virtual network requests on average.

Network Virtualization (NV), considered as a key enabler for overcoming the ossification of the Internet allows multiple heterogeneous virtual networks to co-exist over the same substrate network. Resource allocation problems in NV have been extensively studied for single layer substrates such as IP or Optical networks. However, little effort has been put to address the same problem for multi-layer IP-over-Optical networks. The increasing popularity of multi-layer networks for deploying backbones combined with their unique characteristics (e.g., topological flexibility of the IP layer) calls for the need to carefully investigate the resource provisioning problems arising from their virtualization. In this paper, we address the problem of MUlti-Layer virtual network Embedding (MULE) on IP-overOptical networks. We propose two solutions to MULE: an Integer Linear Program (ILP) formulation for the optimal solution and a heuristic to address the computational complexity of the optimal solution. We demonstrate through extensive simulations that on average our heuristic performs within ≈1.47 × of optimal solution and incurs ≈66% less cost than the state-of-the-art heuristic.

Perceived as a key enabling technology for the future Internet, Network Virtualization (NV) allows an Infrastructure Provider (InP) to better utilize their Substrate Network (SN) by provisioning multiple Virtual Networks (VNs) from different Service Providers (SPs). A key challenge in NV is to efficiently map the VN requests from SPs on an SN, known as the Virtual Network Embedding (VNE) problem. VNE algorithms are typically online in nature. A VN embedding can become suboptimal over time due to the arrival and departure of other VNs as well as due to changes in SN such as failures. One way to mitigate the impact of such dynamism is to periodically reallocate resources for the existing VNs. VNE reallocation can increase an InP's revenue by decreasing bandwidth consumption and by increasing the possibility of accepting future VNs. In this paper, we study Reallocation of Virtual Network Embedding (ReViNE) problem to minimize the number of over utilized substrate links and total bandwidth cost on the SN. We propose an Integer Linear Programming formulation for the optimal solution (ReViNE-OPT) and a simulated annealing based heuristic (ReViNE-FAST) to solve larger problem instances. Simulation results show that on average our proposed heuristic performs within ∼19% of the optimal solution. Moreover, ReViNE-FAST generates more than 2.5× better solutions compared to the state-of-the-art simulated annealing based heuristic for VNE reallocation.

A service-function chain, or simply a chain, is an ordered sequence of service functions, e.g., firewalls and load balancers, composing a service. A chain deployment involvesselectingand instantiating a number of virtual network functions (VNFs), i.e., softwarized service functions,placingVNF instances, androutingtraffic through them. In the current optimization-models of a chain deployment, the instances of the same function are assumed to be identical, while typical service providers offer VNFs with heterogeneous throughput and resource configurations. The VNF instances of the same function are installed in a single physical machine, which limits a chain to the throughput of a few instances that can be installed in one physical machine. Furthermore, theselection,placement, androutingproblems are solved in isolation. We present distributed service function chaining that coordinates these operations, places VNF-instances of the same functiondistributedly, and selects appropriate instances from typical VNF offerings. Such a deployment uses network resources more efficiently and decouples a chain’s throughput from that of physical machines. We formulate this deployment as a mixed integer programming (MIP) model, prove its NP-Hardness, and develop a local search heuristic called Kariz. Extensive experiments demonstrate that Kariz achieves a competitive acceptance-ratio of 76%–100% with an extra cost of less than 24% compared with the MIP model.

Network virtualization has evolved as a key enabling technology for offering the next generation network services. Recently, it is being rolled out in data center networks as a means to provide bandwidth guarantees to cloud applications. With increasing deployments of virtual networks (VNs) in commercial-grade networks with commodity hardware, VNs need to tackle failures in the underlying substrate network. In this paper, we study the problem of recovering a batch of VNs affected by a substrate node failure. The combinatorial possibilities of alternate embeddings of the failed virtual nodes and links of the VNs make the task of finding the most efficient recovery both non-trivial and intractable. Furthermore, any recovery approach ideally should not cause any service disruption for the unaffected parts of the VNs. We take into account these issues to design a generalized recovery approach that can achieve customized objectives such as fair treatment on the failed VNs, partial treatment based on priority, and so on. We provide integer linear programming (ILP) formulations for two variants of our recovery scheme, namely, fair recovery model and priority-based recovery model. We also propose a fast and scalable heuristic algorithm to tackle the computational complexity of the ILP solution. Evaluation results demonstrate that our heuristic performs close to the optimal solution and outperforms the state-of-the-art algorithm.

In the last decade we have observed a tremendous adoption of distributed applications and a trend to host services in private or public clouds. However, service providers still need to own an infrastructure to test their applications or services. A similar problem is faced by network operators when they want to introduce a new service in their production network. It is very difficult to determine the behavior of a new application or service without deploying it in the production environment. Bugs or misconfiguration can cause service outage and trigger customer churn along with loss of reputation. There are several publicly available testbeds such as Emulab, GENI or OFELIA that allow users to lease physical and virtual resources for emulation. However, these testbeds do not provide performance guarantee. Acquisition of physical instances provides performance guarantee and isolation, but compromises overall system utilization. On the other hand, acquisition of virtualized instances lack guarantee and isolation resulting in an unrealistic emulation outcome. To address these limitations, we propose EASE, a next generation multi-tenant infrastructure emulator with an aim to maximize hardware utilization while providing performance guarantee, isolation and full-fledged support for SDN and NFV.

Network visualization (NV) has evolved as a key enabling technology for offering the next generation network services. Recently, it is being rolled out in data center networks as a means to provide bandwidth guarantees to cloud applications. With increasing deployments of virtual networks (VNs) in commercial-grade networks with commodity hardware, VNs need to tackle failures in the underlying substrate network. In this paper, we study the problem of recovering a batch of VNs affected by a substrate node failure. The combinatorial possibilities of alternate embeddings of the failed virtual nodes and links of the VNs makes the task of finding the most efficient recovery both non-trivial and intractable. Furthermore, any recovery approach ideally should not cause any service disruption for the unaffected parts of the VNs. We take into account these issues to design a recovery approach for maximizing recovery and minimizing the cost of recovery and network disruption. We provide an Integer Linear Programming (ILP) formulation of our recovery scheme. We also propose a fast and scalable heuristic algorithm to tackle the computational complexity of the ILP solution. Evaluation results demonstrate that our heuristic performs close to the optimal solution and outperforms the state-of-the-art algorithm.

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. In this paper, we advocate that VNE must be performed with some 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 an approach based on VNE and OpenFlow coordination for proper deployment of virtual networks (VNs). The proposed approach unfolds in the following main contributions: (i) a virtual infrastructure abstraction that allows a service provider to represent the details of his/her VN requirements in a comprehensive manner; (ii) a privacy-aware compiler that is able to preprocess this detailed VN request in order to obfuscate sensitive information and derive computable operational requirements; and (iii) a model for embedding requested VNs ensuring their feasibility at the physical level. The results obtained through our evaluation demonstrate that taking such operational requirements into account, as well as accurately assessing them, is of paramount importance to ensure the correct behavior of VNs hosted on top of the virtualization platform.

Network virtualization is enabling infrastructure providers (InPs) to offer new services to higher level service providers (SPs). InPs are usually bound by Service Level Agreements (SLAs) to ensure various levels of resource availability for different SPs' virtual networks (VNs). They provision redundant backup resources while embedding an SP's VN request to conform to the SLAs during physical failures in the infrastructure. An extreme of this backup resource provisioning is to reserve a dedicated backup of each element in an SP's VN request. Such dedicated protection scheme can enable an InP to ensure fast VN recovery, thus, providing high uptime guarantee to the SPs. In this paper, we study the 1 + 1-Protected Virtual Network Embedding (1 + 1-ProViNE) problem. We propose Dedicated Protection for Virtual Network Embedding (DRONE), a suite of solutions to the 1 + 1-ProViNE. DRONE includes an Integer Linear Programming (ILP) formulation for optimal solution (OPT-DRONE) and a heuristic (FAST-DRONE) to tackle the computational complexity in computing the optimal solution. Trace driven simulations show that FAST-DRONE allocates only 14.3% extra backup resources on average compared to the optimal solution, while executing 200-12000x faster.

MapReduce has become a prevalent programming model for building data processing applications in the cloud. While being widely used, existing MapReduce schedulers still suffer from an issue known as partitioning skew, where the output of map tasks is unevenly distributed among reduce tasks. Existing solutions follow a similar principle that repartitions workload among reduce tasks. However, those approaches often incur high performance overhead due to the partition size prediction and repartitioning. In this paper, we present DREAMS, a framework that provides run-time partitioning skew mitigation. Instead of repartitioning workload among reduce tasks, we cope with the partitioning skew problem by controlling the amount of resources allocated to each reduce task. Our approach completely eliminates the repartitioning overhead, yet is simple to implement. Experiments using both real and synthetic workloads running on a 21-node Hadoop cluster demonstrate that DREAMS can effectively mitigate the negative impact of partitioning skew, thereby improving the job completion time by up to a factor of$2.29$over the native Hadoop YARN. Compared to the state-of-the-art solution, DREAMS can improve the job completion time by a factor of$1.65$.

Middleboxes or network appliances like firewalls, proxies, and WAN optimizers have become an integral part of today's ISP and enterprise networks. Middlebox functionalities are usually deployed on expensive and proprietary hardware that require trained personnel for deployment and maintenance. Middleboxes contribute significantly to a network's capital and operation costs. In addition, organizations often require their traffic to pass through a specific sequence of middleboxes for compliance with security and performance policies. This makes the middlebox deployment and maintenance tasks even more complicated. Network function virtualization (NFV) is an emerging and promising technology that is envisioned to overcome these challenges. It proposes to move packet processing from dedicated hardware middleboxes to software running on commodity servers. In NFV terminology, software middleboxes are referred to as virtualized network functions (VNFs). It is a challenging problem to determine the required number and placement of VNFs that optimizes network operational costs and utilization, without violating service level agreements. We call this the VNF orchestration problem (VNF-OP) and provide an integer linear programming formulation with implementation in CPLEX. We also provide a dynamic programming-based heuristic to solve larger instances of VNF-OP. Trace driven simulations on realworld network topologies demonstrate that the heuristic can provide solutions that are within 1.3 times of the optimal solution. Our experiments suggest that a VNF-based approach can provide more than 4× reduction in the operational cost of a network.

Network virtualization is enabling infrastructure providers (InPs) to offer new services to service providers (SPs). InPs are usually bound by service level agreements to ensure various levels of resource availability for different SPs' virtual networks (VNs). They provision redundant backup resources while embedding an SP's VN request to conform to the SLAs during physical failures in the infrastructure. An extreme backup resource provisioning is to reserve a mutually exclusive backup of each element in an SP's VN request. Such dedicated protection scheme can enable an InP to ensure fast VN recovery, thus, providing high uptime guarantee to the SPs. In this paper, we study the 1 + 1-Protected Virtual Network Embedding (1 + 1-ProViNE) problem. We propose Dedicated Protection for Virtual Network Embedding (DRONE), a suite of solutions to the 1 + 1-ProViNE problem. DRONE includes an integer linear programming formulation for optimal solution (OPT-DRONE) and a heuristic (FAST-DRONE) to tackle the computational complexity of the optimal solution. Trace driven simulations show that FAST-DRONE allocates only 14.3% extra backup resources on average compared to the optimal solution, while executing 200-1200 times faster. Simulation results also show that FAST-DRONE can accept four times more VN requests on average compared to the state-of-the-art solution for providing dedicated protection to VNs.

Internet applications are deployed on the same network infrastructure, yet they have diverse performance and functional requirements. The Internet was not originally designed to support the diversity of current applications. Network virtualization enables heterogeneous applications and network architectures to coexist without interference on the same infrastructure. Embedding a virtual network (VN) into a physical network is a fundamental problem in network virtualization. A VN embedding that aims to survive physical (e.g., link) failures is known as the survivable VN embedding (SVNE). A key challenge in the SVNE problem is to ensure VN survivability with minimal resource redundancy. To address this challenge, we propose survivability in multi-path link embedding (SiMPLE). By exploiting path diversity in the physical network, SiMPLE provides guaranteed VN survivability against single link failure while incurring minimal resource redundancy. In case of multiple arbitrary link failures, SiMPLE provides maximal survivability to the VNs. We formulate this problem as an integer linear program and implement it using GNU linear programming kit. We propose a greedy proactive approach to solve larger instances of the problem in case of single link failures. In presence of more than one link failures, we propose a greedy reactive algorithm as an extension to the previous one, which opportunistically recovers the lost bandwidth in the VNs. Simulation results show that SiMPLE outperforms full backup and shared backup schemes for SVNE, and produces near-optimal results.

One of the crucial building blocks for Information Centric Networking ICN is a name based routing scheme that can route directly on content names instead of IP addresses. However, moving the address space from IP addresses to content names brings the scalability issues to a whole new level, due to two reasons. First, name aggregation is not as trivial a task as the IP address aggregation in BGP routing. Second, the number of addressable contents in the Internet is several orders of magnitude higher than the number of IP addresses. With the current size of the Internet, name based, anycast routing is very challenging specially when routing efficiency is of prime importance. We propose a name-based routing scheme αRoute for ICN that offers efficient bandwidth usage, guaranteed content lookup and scalable routing table size. αRoute consists of two components: an alphanumeric Distributed Hash Table DHT and an overlay to underlay Internet topology mapping algorithm. Simulation results show that αRoute performs significantly better than Content Centric Network CCN in terms of network bandwidth usage, lookup latency and load balancing.

Middleboxes or network appliances like firewalls, proxies, and WAN optimizers have become an integral part of today's ISP and enterprise networks. Middlebox functionalities are usually deployed on expensive and proprietary hardware that require trained personnel for deployment and maintenance. Middleboxes contribute significantly to a network's capital and operational costs. In addition, organizations often require their traffic to pass through a specific sequence of middleboxes for compliance with security and performance policies. This makes the middlebox deployment and maintenance tasks even more complicated. Network Function Virtualization (NFV) is an emerging and promising technology that is envisioned to overcome these challenges. It proposes to move packet processing from dedicated hardware middleboxes to software running on commodity servers. In NFV terminology, software middleboxes are referred to as Virtual Network Functions (VNFs). It is a challenging problem to determine the required number and placement of VNFs that optimize network operational costs and utilization, without violating service level agreements. We call this the VNF Orchestration Problem (VNF-OP) and provide an Integer Linear Programming (ILP) formulation with implementation in CPLEX. We also provide a dynamic programming based heuristic to solve larger instances of VNF-OP. Trace driven simulations on real-world network topologies demonstrate that the heuristic can provide solutions that are within 1.3 times of the optimal solution. Our experiments suggest that a VNF based approach can provide more than 4 χ reduction in the operational cost of a network.

Internet applications are deployed on the same network infrastructure, yet they have diverse performance and functional requirements. The Internet was not originally designed to support the diversity of current applications. Network Virtualization can enable heterogeneous applications and network architectures to coexist without interference on the same infrastructure. Embedding a Virtual Network (VN) into a physical network is a fundamental problem in Network Virtualization. A VN Embedding that aims to survive physical (e.g., link) failures is known as the Survivable Virtual Network Embedding (SVNE). A key challenge in the SVNE problem is to ensure VN survivability with minimal resource redundancy. To address this challenge, we propose SiMPLE. By exploiting path diversity in the physical network, SiMPLE provides guaranteed VN survivability against single link failure. In addition, SiMPLE produces highly surviv-able VN embeddings in presence of multiple link failures while incurring very low resource redundancy. We provide an ILP formulation for this problem and implement it using GLPK. We also propose a greedy algorithm to solve larger instances of the problem. Simulation results show that our solution outperforms full backup and shared backup schemes for SVNE, and produces near-optimal results.

Rapid technological advancement has induced widespread adoption of smart, powerful and multi-purpose enduser devices (e.g., phones, tablets, set-top boxes, gaming console etc.) in our daily life. Unfortunately, the available mechanisms for accessing, configuring and controlling these devices are still primitive, and require physical access to the devices. Enabling remote access to these devices through a widely used protocol, such as HTTP, can significantly improve their usability and can foster innovative applications. However, the end-devices are often NATed by home gateways, which is not suitable for HTTP access over the Internet. In this work, we present a mechanism for seamless traversal of HTTP traffic through home gateways. Our approach builds upon the existing Web-technology. It allows remote access using global DNS names, despite the end-devices having local IPs. As a proof of concept, we realize the proposed architecture on the well-accepted OpenWRT platform, and report experimental results on device access performance.

No abstract available.

Centralized social networking and media sharing portals provide inadequate support for preserving user privacy, content ownership and control. These problems can be mitigated through distributed Web services as demonstrated by a number of academic projects and industrial deployments. In general, these distributed services do not assign globally recognized, persistent names to the user devices. As a result, these solutions work in isolation and also cannot inter-operate with traditional Web technology. In this work, we present a decentralized and scalable platform, named pWeb, for distributing web services, like online social networks and media streaming, across end-user devices. pWeb assigns Internet compatible names to end-user devices, and provides name resolution and directory services. A user can retain ownership, and make the services and contents in his devices searchable and accessible at different privacy levels, e.g., friends, family and public. New services can be easily developed and deployed over the pWeb platform. We have developed a working prototype of the platform, and to demonstrate its effectiveness we have implemented a video streaming application for Android and Windows platforms. We also present performance results from our prototype implementation.

With the proliferation of cloud computing, virtu-alization has become the cornerstone of modern data centers and an effective solution to reduce operational costs, maximize utilization and improve performance and reliability. One of the powerful features provided by virtualization is Virtual Machine (VM) migration, which facilitates moving workloads within the infrastructure to reach various performance objectives. As recent virtual resource management schemes are more reliant on this feature, a large number of VM migrations may be triggered simultaneously to optimize resource allocations. In this context, a challenging problem is to find an efficient migration plan, i.e., an optimal sequence in which migrations should be triggered in order to minimize the total migration time and impact on services. In this paper, we propose CQNCR (read as sequencer), an effective technique for determining the execution order of massive VM migrations within data centers. Specifically, given an initial and a target resource configuration, CQNCR sequences VM migrations so as to efficiently reach the final configuration with minimal time and impact on performance. Experiments show that CQNCR can significantly reduce total migration time by up to 35% and service downtime by up to 60%.

Software Defined Networking promises to simplify network management tasks by separating the control plane (a central controller) from the data plane (switches). OpenFlow has emerged as the de facto standard for communication between the controller and switches. Apart from providing flow control and communication interfaces, OpenFlow provides a flow level statistics collection mechanism from the data plane. It exposes a high level interface for per flow and aggregate statistics collection. Network applications can use this high level interface to monitor network status without being concerned about the low level details. In order to keep the switch design simple, this statistics collection mechanism is implemented as a pull-based service, i.e. network applications and in turn the controller has to periodically query the switches about flow statistics. The frequency of polling the switches determines monitoring accuracy and network overhead. In this paper, we focus on this trade-off between monitoring accuracy, timeliness and network overhead. We propose PayLess - a monitoring framework for SDN. PayLess provides a flexible RESTful API for flow statistics collection at different aggregation levels. It uses an adaptive statistics collection algorithm that delivers highly accurate information in real-time without incurring significant network overhead. We utilize the Floodlight controller's API to implement the proposed monitoring framework. The effectiveness of our solution is demonstrated through emulations in Mininet.

With the growing adoption of Software Defined Networking (SDN), there is a compelling need for SDN emulators that facilitate experimenting with new SDN-based technologies. Unfortunately, Mininet [1], the de facto standard emulator for software defined networks, fails to scale with network size and traffic volume. The aim of this paper is to fill the void in this space by presenting a low cost and scalable network emulator called Distributed OpenFlow Testbed (DOT). It can emulate large SDN deployments by distributing the workload over a cluster of compute nodes. Through extensive experiments, we show that DOT can overcome the limitations of Mininet and emulate larger networks. We also demonstrate the effectiveness of DOT on four Rocketfuel topologies. DOT is available for public use and community-driven development at dothub.org.

With the growing adoption of Software Defined Networking (SDN) technology, there is a compelling need for an SDN emulator that can facilitate experimenting with new SDN solutions. Unfortunately, Mininet, the de facto standard emulator for software defined networks, fails to scale with network size and traffic volume. To address these limitations, we developed Distributed OpenFlow Testbed (DOT), a highly scalable emulator for SDN. It can emulate large SDN deployments by distributing the workload over a cluster of compute nodes. Moreover, DOT can emulate a wider range of network services compared to other publicly available SDN emulators and simulators. Our demonstration will illustrate several features of DOT including: (i) how easy it is to setup the emulator, (ii) how to deploy a topology using a single configuration file, (iii) how to run a connectivity test to ensure that the emulated network is properly deployed, and (iv) how to control and monitor the emulated components from a centralized location. We will also showcase DOT by emulating two applications: (i) policy based traffic steering through middleboxes and (ii) traffic monitoring.

Software Defined Networking (SDN) has emerged as a new paradigm that offers the programmability required to dynamically configure and control a network. A traditional SDN implementation relies on a logically centralized controller that runs the control plane. However, in a large-scale WAN deployment, this rudimentary centralized approach has several limitations related to performance and scalability. To address these issues, recent proposals have advocated deploying multiple controllers that work cooperatively to control a network. Nonetheless, this approach drags in an interesting problem, which we call the Dynamic Controller Provisioning Problem (DCPP). DCPP dynamically adapts the number of controllers and their locations with changing network conditions, in order to minimize flow setup time and communication overhead. In this paper, we propose a framework for deploying multiple controllers within an WAN. Our framework dynamically adjusts the number of active controllers and delegates each controller with a subset of Openflow switches according to network dynamics while ensuring minimal flow setup time and communication overhead. To this end, we formulate the optimal controller provisioning problem as an Integer Linear Program (ILP) and propose two heuristics to solve it. Simulation results show that our solution minimizes flow setup time while incurring very low communication overhead.

One of the crucial building blocks for Information Centric Networking (ICN) is a name based routing scheme that can route directly on content names instead of IP addresses. However, moving the address space from IP addresses to content names brings scalability issues to a whole new level, due to two reasons. First, name aggregation is not as trivial a task as the IP address aggregation in BGP routing. Second, the number of addressable contents in the Internet is several orders of magnitude higher than the number of IP addresses. With the current size of the Internet, name based, anycast routing is very challenging specially when routing efficiency is of prime importance. We propose a novel name-based routing scheme (αRoute) for ICN that offers efficient bandwidth usage, guaranteed content lookup and scalable routing table size.

The peer—to—peer paradigm has great potential of providing the next generation Web hosting infrastructure. Profound advancements in P2P technology in the last decade have proven its capability to provide functionality similar to traditional client—server systems at a much larger scale with relatively lower cost. Existing centralized website hosting technology has a number of inherent deficiencies including scalability, single point of failure, administration overhead, hosting expenses, etc. P2P Web hosting can effectively address these problems and hence open a new era for next generation Web hosting. However peer availability and content location are highly dynamic in a P2P network. This dynamism raises a number of research challenges related to naming, addressing, indexing, and searching in a P2P environment. In this paper we identify the practical requirements for devising a secure, persistent, and human—friendly naming scheme for P2P Web hosting and propose a novel naming scheme that satisfies all these requirements. We also present extensive simulation results validating the accuracy, scalability and fault-resilience of the proposed naming scheme.

Ensuring content availability in a persistent manner is essential for providing any consistent service over peer-to-peer (P2P) systems. This paper introduces an efficient protocol, called DATA, to design highly available P2P systems irrespective of peer uptime and churn. Our approach utilizes the diurnal pattern of globally dispersed peers to develop a grouping strategy where each group aims to ensure 24 × 7 data availability within the group. Simulation results reveal that our protocol converges fast and ensures high availability for each group with minimal overhead.

The peer-to-peer paradigm has great potential of contributing to the next generation web-hosting infrastructure. Profound advancements in P2P technologies in the last decade have proven their capability to provide the same functionality as traditional client-server systems at a much larger scale and much lower cost. Existing centralized website hosting technology has a number of inherent deficiencies, including: scalability issues; single point of failure; administrative overhead; and hosting expenses. P2P Web hosting can effectively address these problems and open a new era for the next generation web technology. Unlike the current web however, peer availability and content placement are highly dynamic in P2P networks. This dynamism raises a number of research challenges related to naming, indexing, searching and hosting in P2P environments. In this paper we identify the practical requirements for devising a persistent naming scheme for P2P web-hosting on top of highly dynamic non-persistent P2P networks and present a novel naming architecture for satisfying these requirements.

Efficient discovery of information based on partially specified and misspelled query keywords is a challenging problem in large scale peer-to-peer (P2P) networks. This paper presents QPM, a P2P search mechanism for efficient information retrieval with misspelled and partial keywords. QPM uses the double metaphone algorithm to phonetically match misspelled query keywords with advertised keywords. For achieving bandwidth efficiency and similarity matching, QPM incorporates second order Reed-Muller code within the Plexus protocol having a logarithmic routing efficiency on overlay network size. QPM supports large scale networks and achieves better resilience to peer failure by maintaining redundant routing paths and by systematically placing index replicas. The concept presented in this paper is supported by necessary experimental evaluation.

Flexibility and efficiency are the prime requirements for any P2P search mechanism. Existing P2P systems do not provide satisfactory solution for achieving these two conflicting goals. Unstructured search protocols (as adopted in Gnutella and FastTrack) provide search flexibility but exhibit poor performance characteristics. Structured search techniques (mostly Distributed Hash Table (DHT)-based), on the other hand, can efficiently route queries but support exact-match semantic only. In this paper we have defined Distributed Pattern Matching (DPM) problem and have presented a novel P2P architecture, named Distributed Pattern Matching System (DPMS), as a solution. Possible application areas of DPM include P2P search, service discovery and P2P databases. In DPMS, advertised patterns are replicated and aggregated by the peers, organized in a lattice-like hierarchy. Replication Improves availability and resilience to peer failure, and aggregation reduces storage overhead. An advertised pattern can be discovered using any subset of its 1-bits. Search complexity in DPMS is logarithmic to the total number of peers in the system. Advertisement overhead and guarantee on search completeness is comparable to that of DHT-based systems. We have presented mathematical analysis and simulation results to demonstrate the effectiveness of DPMS.

Flexibility and efficiency are the prime requirements for any P2P search mechanism. Existing P2P systems do not seem to provide satisfactory solution for achieving these two conflicting goals. Unstructured search protocols (as adopted in Gnutella and FastTrack), provide search flexibility but exhibit poor performance characteristics. Structured search techniques (mostly distributed hash table (DHT)-based), on the other hand, can efficiently route queries to target peers but support exact-match queries only. In this paper we present a novel P2P system, called distributed pattern matching system (DPMS), for enabling flexible and efficient search. Distributed pattern matching can be used to solve problems like wildcard searching (for file-sharing P2P systems), partial service description matching (for service discovery systems) etc. DPMS uses a hierarchy of indexing peers for disseminating advertised patterns. Patterns are aggregated and replicated at each level along the hierarchy. Replication improves availability and resilience to peer failure, and aggregation reduces storage overhead. An advertised pattern can be discovered using any subset of its 1-bits; this allows inexact matching and queries in conjunctive normal form. Search complexity (i.e., the number of peers to be probed) in DPMS is O (log N + zetalog N/log N), where N is the total number of peers and zeta is proportional to the number of matches, required in a search result. The impact of churn problem is less severe in DPMS than DHT-based systems. Moreover, DPMS provides guarantee on search completeness for moderately stable networks. We demonstrate the effectiveness of DPMS using mathematical analysis and simulation results