There is an increasing adoption of machine learning for encoding data into vectors to serve online recommendation and search use cases. As a result, recent data management systems propose augmenting query processing with online vector similarity search. In this work, we explore vector similarity search in the context of Knowledge Graphs (KGs). Motivated by the tasks of finding related KG queries and entities for past KG query workloads, we focus on hybrid vector similarity search (hybrid queries for short) where part of the query corresponds to vector similarity search and part of the query corresponds to predicates over relational attributes associated with the underlying data vectors. For example, given past KG queries for a song entity, we want to construct new queries for new song entities whose vector representations are close to the vector representation of the entity in the past KG query. But entities in a KG also have non-vector attributes such as a song associated with an artist, a genre, and a release date. Therefore, suggested entities must also satisfy query predicates over non-vector attributes beyond a vector-based similarity predicate. While these tasks are central to KGs, our contributions are generally applicable to hybrid queries. In contrast to prior works that optimize online queries, we focus on enabling efficient batch processing of past hybrid query workloads. We present our system, HQI, for high-throughput batch processing of hybrid queries. We introduce a workload-aware vector data partitioning scheme to tailor the vector index layout to the given workload and describe a multi-query optimization technique to reduce the overhead of vector similarity computations. We evaluate our methods on industrial workloads and demonstrate that HQI yields a 31× improvement in throughput for finding related KG queries compared to existing hybrid query processing approaches.

5G transport networks will support dynamic services with diverse requirements through network slicing. Elastic Optical Networks (EONs) facilitate transport network slicing by flexible spectrum allocation and tuning of transmission configurations. A major challenge in supporting dynamic services is the lack of priori knowledge of future slice requests. As a consequence, slice embedding can become sub-optimal over time, leading to spectrum fragmentation and skewed utilization. This in turn can block future slice requests, impacting operator revenue. To address this issue, operators can periodically re-optimize slice embedding for reducing fragmentation. In this paper, we address this problem of re-optimizing network slice embedding on EONs for minimizing fragmentation. The problem is solved in its splittable version, which significantly increases problem complexity, but also offers more opportunities for a larger set of re-configuration actions. We employ simulated annealing for systematically exploring the large solution space. We also propose a greedy algorithm to address the practical constraint of limiting the number of re-configuration steps. Moreover, we present a novel method based on Deep Reinforcement Learning (DRL) for determining when performing re-configuration is most effective. Our extensive simulations demonstrate that the greedy algorithm yields a solution very close to that obtained using simulated annealing while requiring orders of magnitude lesser re-configuration actions. Finally, we show that by applying the greedy algorithm periodically on the network according to the DRL-based time selection algorithm, a significant improvement in the total number of accepted slice requests can be achieved with only performing a limited number of re-configuration operations.

Communication networks are undergoing a major transformation through softwarization, which is changing the way networks are designed, operated, and managed. The enhanced programmability enabled by softwarization creates unique opportunities for adapting network function and resources in support of applications and users with diverse requirements. To effectively leverage the flexibility provided by network softwarization and realize its full potential, it is of paramount importance to devise proper mechanisms for allocating resources to different applications and users and for monitoring their usage over time. The overarching goal of this dissertation is to advance state-of-the-art in how resources are allocated and monitored and build the foundation for effective resource management in softwarized networks. Specifically, we address four resource management challenges in all three key enablers of network softwarization. First, we challenge the current practice of realizing network services with monolithic software network functions and propose a microservice-based disaggregated architecture enabling finer-grained resource allocation and scaling. Then, we devise optimal solutions and scalable heuristics for establishing virtual networks with guaranteed bandwidth and guaranteed survivability against failures in multi-layer IP-over-Optical and single-layer IP substrate networks, respectively. Finally, we propose adaptive sampling mechanisms for balancing the overhead of softwarized network monitoring and the accuracy of the network view constructed from monitoring data.

The increasing sophistication of attacks over the last years such as the proliferation of complex multi-steps attacks, calls for new monitoring models and methods for diagnosing the attacks’ severity and mitigating them in a timely manner. In this paper, we propose an in-network monitoring approach capable of detecting a set of composed behaviors and consequently triggering different levels of alerts and reactions. Our approach is based on a Petri Net model capable of aggregating individual attacks into a multi-step composition. To this end, we propose a method for deriving a Match-Action Table (MAT) abstraction from a Petri net model. MATs can be then deployed on a P4 programmable data plane, enabling flexible re-composition of attack detection steps at runtime. We demonstrate the feasibility of our proposal by modeling the detection of a multi-step DNS cache poisoning attack and implementing the model on a P4 programmable data plane.

The simple programming model and very low-overhead I/O capabilities of emerging packet processing techniques leveraging kernel-bypass I/O and poll-mode processing is gaining significant popularity for building high performance softwaremiddleboxes(akaVirtual Network Functions (VNFs)). However, existing OS schedulers fall short in rightsizing CPU allocation to poll-mode VNFs due to the schedulers’ shortcoming in capturing the actual processing cost of these VNFs. This issue is further exacerbated by their inability to consider VNF processing order when VNFs are chained to form Service Function Chains (SFCs). The state-of-the-art VNF schedulers proposed as an alternative to OS schedulers areintrusive, requiring the VNFs to be built with scheduler specific libraries or having carefully selected scheduling checkpoints. This highly restricts the VNFs that can properly work with these schedulers. In this article, we presentUNiS, aUser-spaceNon-intrusive work-flow aware VNFScheduler. Unlike existing approaches, UNiS is non-intrusive, i.e., does not require VNF modifications and treats poll-mode VNFs as black boxes. UNiS is also workflow-aware, i.e., takes SFC processing order into account while scheduling VNFs. Testbed experiments show thatUNiSis able to achieve a throughput within 90 and 98 percent of that achievable using an intrusive co-operative scheduler for synthetic and real data center traffic, respectively.

5G transport networks will support dynamic services with diverse requirements through network slicing. Elastic Optical Networks (EONs) facilitate transport network slicing by flexible spectrum allocation and tuning of transmission configurations such as modulation format and forward error correction. A major challenge in supporting dynamic services is the lack of a priori knowledge of future slice requests. In consequence, slice embedding can become sub-optimal over time, leading to spectrum fragmentation and skewed utilization. This in turn can block future slice requests, impacting operator revenue. Therefore, operators need to periodically re-optimize slice embedding for reducing fragmentation. In this paper, we address this problem of re-optimizing network slice embedding on EONs for minimizing fragmentation. The problem is solved in its splittable version, which significantly increases problem complexity, but offers more opportunities for a larger set of re-configuration actions. We employ simulated annealing for systematically exploring the large solution space. We also propose a greedy algorithm to address the practical constraint to limit the number of re-configuration steps taken to reach a defragmentated state. Our extensive simulations demonstrate that the greedy algorithm yields a solution very close to that obtained using simulated annealing while requiring orders of magnitude lesser number of re-configuration actions.

Elastic Optical Networks (EONs) enable finer-grained resource allocation and tuning of transmission configurations for right-sized resource allocation. These features make EONs excellent choice for 5G transport networks supporting highly dynamic traffic with diverse Quality-of-Service (QoS) requirements. 5G network slices are expected to host applications with a dynamic nature (e.g., augmented/virtual reality broadcasting), which will result in slice resource requirement changing over time. The initial resource allocation to network slices has to be adapted to accommodate such changes without causing significant disruption to existing traffic and using minimal additional resources. In this paper, we address the problem of scaling bandwidth demand of network slices on an EON-enabled 5G transport network. In contrast to the state-of-the-art, we do not assume any specific technologies for minimizing disruption when accommodating the scaling request. Rather, we propose an Integer Linear Program (ILP) and a heuristic algorithm for accommodating scaling requests by choosing from a comprehensive set of reconfiguration actions. We carefully design a novel cost model for capturing traffic disruptions and additional resource usage by these different actions. Our extensive simulations using realistic network topologies shed light on the trade-off between additional resource usage and disruption while accommodating slice scaling requests by employing a comprehensive set of reconfiguration actions. Simulation results also show that our heuristic algorithm can find solutions that remain within 10% of ILP-based solutions, while executing several orders of magnitude faster than ILP.

This article proposes a new approach for detecting and mitigating the impact of misbehaving TCP end-hosts, specifically the Optimistic ACK attack, and Explicit Congestion Notification (ECN) abuse. In contrast to the state-of-the-art, we show that it is possible to mitigate such misbehavior leveraging emerging programmable data planes while not requiring any end-host or protocol modifications. A key challenge in doing so is to implement expressive, complex and stateful functions in the data plane within its restricted programming model. In this regard, we propose a security monitoring function that uses Extended Finite State Machine (EFSM) abstraction for monitoring stateful protocols in the data plane. We also design a mechanism for mapping a protocol's EFSM to programmable data plane primitives. Our evaluation results demonstrate that our approach can fully or partially restore the throughput loss caused by misbehaving end-hosts that manipulate TCP congestion control through misinformation.

Network Function Virtualization (NFV) promises to reduce the capital and operational expenditure for network operators by moving packet processing from purpose-built hardware to software running on commodity servers. However, the state-of-the-art in NFV is merely replacing monolithic hardware with monolithic Virtual Network Functions (VNFs), i.e., software that realizes different network functions. This is a good first step towards transitioning to NFV, however, common functionality is repeatedly implemented in monolithic VNFs. Repeated execution of such redundant functionality is particularly common when VNFs are chained to realize Service Function Chains (SFCs) and results in wasted infrastructure resources. This stresses the need for re-architecting the NFV ecosystem, through modular VNF design and flexible service composition. From this perspective, we propose MicroNF (μNF in short), a disaggregated packet processing architecture facilitating the deployment of VNFs and SFCs using reusable, loosely-coupled, and independently deployable components. We have implemented the proposed system, including the different architecture components and optimizations for improving packet processing throughput and latency. Extensive experiments on a testbed demonstrate that: (i) compared to monolithic VNF based SFCs, those composed of μNFs achieve the same packet processing throughput while using less CPU cycles per packet on average; and (ii) μNF-based SFCs can sustain the same packet processing throughput as those based on state-of-the-art run-to-completion VNF architecture while using lesser number of CPU cores.

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.

5G network slicing allows partitioning of network resources to meet stringent end-to-end service requirements across multiple network segments, from access to transport. These requirements are shaping technical evolution in each of these segments. In particular, the transport segment is currently evolving in the direction of elastic optical networks (EONs), a new generation of optical networks supporting a flexible optical-spectrum grid and novel elastic transponder capabilities. In this paper, we focus on the reliability of 5G transport-network slices in EON. Specifically, we consider the problem of slicing 5G transport networks,i.e., establishing virtual networks on 5G transport, while providing dedicated protection. As dedicated protection requires a large amount of backup resources, our proposed solution incorporates two techniques to reduce backup resources: (i) bandwidth squeezing,i.e., providing a reduced protection bandwidth than the original request; and (ii) survivable multi-path provisioning. We leverage the capability of EONs to fine tune spectrum allocation and adapt modulation format and forward error correction for allocating spectrum resources. Our numerical evaluation over realistic network topologies quantifies the spectrum savings achieved by employing EON over traditional fixed-grid optical networks, and provides new insights on the impact of bandwidth squeezing and multi-path provisioning on spectrum utilization. One key takeaway from our evaluation is that multi-path provisioning can guarantee up to 40% of the bandwidth requested by a VN during failures by provisioning only 10% additional spectrum resources. This also caused VN blocking ratio for BSR up to 40% to remain very close to that of the no-backup case.

In 5G networks, slicing allows partitioning of network resources to meet stringent end-to-end service requirements across multiple network segments, from access to transport. These requirements are shaping technical evolution in each of these segments. In particular, the transport segment is currently evolving in the direction of the so-called elastic optical networks (EONs), a new generation of optical networks supporting a flexible optical-spectrum grid and novel elastic transponder capabilities. In this paper, we focus on the reliability of 5G transport-network slices in EON. Specifically, we consider the problem of slicing 5G transport networks, i.e., establishing virtual networks on 5G transport, while providing dedicated protection. As dedicated protection requires a large amount of backup resources, our proposed solution incorporates two techniques to reduce backup resources: (i) bandwidth squeezing, i.e., providing a reduced protection bandwidth with respect to the original request; and (ii) survivable multi-path provisioning. We leverage the capability of EONs to fine tune spectrum allocation and adapt modulation format and Forward Error Correction (FEC) for allocating rightsize spectrum resources to network slices. Our numerical evaluation over realistic case-study network topologies quantifies the spectrum savings achieved by employing EON over traditional fixed-grid optical networks, and provides new insights on the impact of bandwidth squeezing and multi-path provisioning on spectrum utilization.

Elastic Optical Network (EON) virtualization has recently emerged as an enabling technology for 5G network slicing. A fundamental problem in EON slicing (known as Virtual Network Embedding (VNE)) is how to efficiently map a virtual network (VN) on a substrate EON characterized by elastic transponders and flexible grid. Since a number of 5G services will have strict latency requirements, the VNE problem in EONs must be solved while guaranteeing latency targets. In existing literature, latency has always been modeled as a constraint applied on the virtual links of the VN. In contrast, we argue in favor of an alternate modeling that constrains the latency of virtual paths. Constraining latency over virtual paths (vs. over virtual links) poses additional modeling and algorithmic challenges to the VNE problem, but allows us to capture end-to-end service requirements. In this paper, we first model latency in an EON by identifying the different factors that contribute to it. We formulate the VNE problem with latency guarantees as an Integer Linear Program (ILP) and propose a heuristic solution that can scale to large problem instances. We evaluated our proposed solutions using real network topologies and realistic transmission configurations under different scenarios and observed that, for a given VN request, latency constraints can be guaranteed by accepting a modest increase in network resource utilization. Latency constraints instead showed a higher impact on VN blocking ratio in dynamic scenarios.

Network operators must continuously scale the capacity of their optical backbone networks to keep apace with the proliferation of bandwidth-intensive applications. Today’s optical networks are designed to carry large traffic aggregates with coarse-grained resource allocation, and are not adequate for maximizing utilization of the expensive optical substrate. Elastic Optical Network (EON) is an emerging technology that facilitates flexible allocation of fiber spectrum by leveraging finer-grained channel spacing, tunable modulation formats and Forward Error Correction (FEC) overheads, and baud-rate assignment, to right size spectrum allocation to customer needs. Virtual Network Embedding (VNE) over EON has been a recent topic of interest due to its importance for 5G network slicing. However, the problem has not yet been addressed while simultaneously considering the full flexibility offered by an EON. In this paper, we present an optimization model that solves the VNE problem over EON when lightpath configurations can be chosen among a large (and practical) set of combinations of paths, modulation formats, FEC overheads and baud rates. The VNE over EON problem is solved in its splittable version, which significantly increases problem complexity, but is much more likely to return a feasible solution. Given the intractability of the optimal solution, we propose a heuristic to solve larger problem instances. Key results from extensive simulations are: (i) a fully-flexible VNE can save up to 60% spectrum resources compared to that where no flexibility is exploited, and (ii) solutions of our heuristic fall in more than 90% of the cases, within 5% of the optimal solution, while executing several orders of magnitude faster.

Existing shortest path-based routing in wide area networks or equal cost multi-path routing in data center networks do not consider the load on the links while taking routing decisions. As a consequence, an influx of network traffic stemming from events such as distributed link flooding attacks and data shuffle during large scale analytics can congest network links despite the network having sufficient capacity on alternate paths to absorb the traffic. This can have several negative consequences such as service unavailability, delayed flow completion, packet losses, among others. In this regard, we propose SPONGE, a traffic engineering mechanism for handling sudden influx of network traffic. SPONGE models the network as a stochastic process, takes the switch queue occupancy and traffic rate as inputs, and leverages the multiple available paths in the network to route traffic in a way that minimizes the overall packet loss in the network. We demonstrate the practicality of SPONGE through an OpenFlow based implementation, where we periodically and pro-actively re-route network traffic to the routes computed by SPONGE. Mininet emulations using real network topologies show that SPONGE is capable of reducing packet drops by 20% on average even when the network is highly loaded because of an ongoing link flooding attack.

Network Function Virtualization (NFV) promises to reduce the capital and operational expenditure for network operators by moving packet processing from purpose-built hardware to software running on commodity servers. However, the state-of-the-art in NFV is merely replacing monolithic hardware with monolithic Virtual Network Functions (VNFs), i.e., software that realizes different network functions. This is a good first step towards deploying NFV, however, common functionality is repeatedly implemented in monolithic VNFs. Repeated execution of such redundant functionality is particularly common when VNFs are chained to realize Service Function Chains (SFCs) and results in wasted infrastructure resources. This stresses the need for re-architecting the NFV ecosystem, through modular VNF design and flexible service composition. From this perspective, we propose MicroNF ( μNF in short), a disaggregated packet processing architecture facilitating the deployment of VNFs and SFCs using reusable and independently deployable components. Experimental results show that compared to monolithic VNF based SFCs, μNF-based ones achieve the same throughput by using less CPU cycles per packet on average.

The rapid development of technologies such as photo-intensive social networks, on-demand video streaming, online gaming, and the Internet of Things (IoT) is causing a tremendous growth of traffic volume. Such large-scale expansion is leading to higher energy consumption and carbon footprint for the telecommunication industry. Governments are trying to minimize the environmental impact by introducing regulations and taxes; driving companies to use renewable energy. However, renewable energy is still not as cost-effective compared to traditional sources of energy (i.e., brown energy), and their availability varies significantly across time and geographic locations. Therefore, it is a challenge for telecommunication companies to comply with regulations and minimize carbon footprint without significantly increasing their operational cost. In this context, we propose an Energy Smart Service Function Chain Orchestrator called ESSO. ESSO reduces the overall carbon footprint of a telecommunication network by opportunistically adapting Service Function Chain (SFC) locations to utilize more energy at locations with surplus renewable energy. ESSO minimizes brown energy consumption by migrating SFCs across different locations. In addition, ESSO provisions SFC components in a manner that allows switches, switch ports, and servers to be put into low-power consumption state. Our trace-driven simulations on real ISP topologies show that considering the availability of renewable energy sources during SFC embedding even for a small-scale network can result in 2-3× reduction in carbon footprint.

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.

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.

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.

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.

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.

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.

In this paper, we investigate the benefits of adding autonomic capabilities inside the operating system. We have developed and implemented a solution that focuses on three use cases (continuous file permission compliance, dynamic disk cleanup, and accidental removal protection) for the file system, and encapsulates all the respective file system monitoring, troubleshooting and error remedial operations in a Linux kernel module. The main benefits of this approach are the capability to detect issues instantly when they occur, and fix these issues transparently, with the invoking applications being unaware of their occurrence. These capabilities are not present in external agent architectures, including contemporary configuration management systems, like Puppet, Chef, or CFEngine. We have built a prototype and evaluated the performance of the most resource intensive use case, dynamic disk cleanup, using the FileBench file system benchmarking tool.

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.

The longest common subsequence (LCS) problem is a classic and well-studied problem in computer science. Palindrome is a word which reads the same forward as it does backward. The longest common palindromic subsequence (LCPS) problem is a variant of the classic LCS problem which finds a longest common subsequence between two given strings such that the computed subsequence is also a palindrome. In this paper, we study the LCPS problem and give two novel algorithms to solve it. To the best of our knowledge, this is the first attempt to study and solve this problem.

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.

Vehicular Communication Networks and Systems (VCNS) and Intelligent Transportation Systems (ITS) are one of the most attractive and challenging topics in recent days since a well efficient protocol for vehicular communication can facilitate the reduction of traffic congestion and can provide us with many more promising applications. In this paper, we propose a protocol for vehicle-to-infrastructure (V2I) and vehicle-to-vehicle (V2V) communication. As one of the challenging parts of this paper, we present an experimental testbed in which two major applications of V2I & V2V communication (i.e. traffic congestion detection and emergency warning) is implemented. Based on careful analysis, we also calculate some key system parameters which reflect the efficiency of the protocol in different applications.