In recent years, the frequency and severity of network attacks have increased significantly, posing serious threats to network security. Network topology information is often exploited by attackers to identify critical bottlenecks, which are prime targets for attacks. Typically, attackers probe the network topology using network tomography or traceroute. Network tomography, compared to traditional methods like traceroute, offers greater flexibility and is more challenging to detect. These characteristics make it a preferred technique for attackers. In response, network operators seek to implement topology obfuscation strategies that expose a deliberately designed fake topology to mislead attackers. However, existing obfuscation techniques against network tomography have primarily focused on protecting tree-like topologies and have been insufficient in concealing bottleneck nodes and links. To this end, we propose TopoFaker, a novel topology obfuscation system designed to protect general network topologies while effectively concealing bottleneck nodes and links. TopoFaker consists of three main components: a topology generator that creates secure fake topologies, a policy deployer that ensures attackers perceive only the obfuscated topology, and obfuscation nodes that implement proactive delay policies in the data plane. Experimental evaluations on real-world network topologies demonstrate that TopoFaker effectively enhances network security by obscuring bottleneck nodes and links, achieving a 73.99% reduction in maximum degree centrality and a 79.48% reduction in maximum edge connectivity. Furthermore, TopoFaker reduces the average proactive delay time by 50.82%, minimizing the negative impact on normal packets misclassified due to the classifier’s false alarms. TopoFaker outperforms existing mechanisms by achieving a runtime of under one minute and reducing memory allocation by four orders of magnitude on large-scale problems.

The rapid development of unmanned aerial vehicle (UAV) technology and mobile edge computing (MEC) has created new opportunities for efficient data processing and transmission. UAV-assisted MEC enables data transmission from UAVs to a base station (BS) equipped with MEC capabilities. However, ensuring the security of these transmissions is a concern, especially when UAVs operate in open airspace. In this paper, we introduce a coordinated multi-point (CoMP) offloading model aimed at enhancing the secure transmission performance of the network. The airspace is divided into several equal-sized hexagonal cells, with multiple UAVs collaborating to offload data to a BS with MEC. During this process, the locations of potential eavesdroppers are randomized as they attempt to intercept the data transmitted by the UAVs. Based on this model, we first derive the success communication probability (SCP) for a typical BS and an eavesdropper using stochastic geometry. We then introduce the concept of secure transmission rate, precisely the average secrecy rate (ASR). Further, we characterize the ASR in the presence of random eavesdroppers. Finally, we analyze the effects of various parameters on transmission performance. The results of our simulations closely align with our numerical findings, confirming the accuracy of our analysis. Notably, the ASR of the proposed system is nearly four times higher than that of an offloading model without cooperation. Moreover, compared to a user-centric offloading model with CoMP, the ASR increases by 5.37 %, enhancing system performance and reducing search overheads.

As mobile device usage and data traffic increase, the demand for faster data processing becomes crucial. Mobile edge computing (MEC) meets this need by placing servers at the network’s edge for real-time computing. However, fixed terrestrial MEC servers struggle with scalability, limiting their effectiveness. Integrating unmanned aerial vehicles (UAV) with MEC technology offers a promising solution, enhancing communication efficiency and service quality. This paper proposes a joint communication and computation offloading model for coordinated multi-point (CoMP) UAV-assisted MEC networks utilizing hexagonal cell partitioning. Within each cell, a cluster of UAVs, each equipped with its own MEC server and connected to a central server via a reliable backhaul, collaborates to serve terrestrial user equipment. To analyze this system, we develop a unified analytical framework integrating stochastic geometry and queuing theory. Furthermore, we define the success probability of edge computing (SPEC) metric to quantitatively evaluate communication reliability and computational efficiency. Finally, we explore the effects of critical parameters on network performance. Simulation results closely match the theoretical predictions, confirming our proposed model’s validity and our analysis’s accuracy. Notably, our proposed model demonstrates an improvement in SPEC of approximately 57.24% over non-CoMP model and 24.97% over the user-centric CoMP model.

Edge computing is an emerging paradigm poised to process a substantial portion of latency-sensitive and computation-intensive tasks through edge service providers (ESPs). However, these ESPs typically operate independently and locally to serve their registered users. When processing burst tasks, the ESPs have to either scale up their respective capacities by introducing additional hardware or compromise user experience by rejecting some user requests, leading to high commercial investment or service degradation. Inspired by the promise of the win-win situation for ESPs and users, we envision a novel task offloading strategy that realizes the following rationales simultaneously: 1) collaborative service, 2) rapid response, and 3) sustainable profitability, while the existing methods fail to achieve them at one shot. To this end, we report CoEdge, a collaborative architecture for efficient task offloading among multiple ESPs in the edge network, aiming at simultaneously minimizing service delay for users and enhancing service profit for ESPs. To achieve this, CoEdge employs a central optimizer to implement a two-stage strategy that determines the task scheduling and service pricing hierarchically. We then formulate these problems and prove their NP-hardness. Additionally, we also propose efficient approximate algorithms to accommodate large-scale computing scenarios with low complexity. Experimental results using real-world datasets demonstrate that our CoEdge can significantly reduce service delay by 2.87x to 4.15x for users and considerably increase service profit by 32% for ESPs.

Many network attacks, like link flooding attacks (LFAs), heavily rely on network topology information. Therefore, network topology obfuscation has been applied to counteract network topology inference and prevent topology information leakage. One effective way is to scheme a fake topology intentionally for attackers to map out. Focusing on reducing the similarity between the real and fake topologies, however, existing methods cannot promise that critical information of the network, such as critical nodes and links, is well hidden. To this end, we propose a new topology obfuscation mechanism, namely ChameleonNet, to protect the critical topology information of a given network. Specifically, ChameleonNet achieves topology obfuscation through a two-stage operation: 1) generating fake topology and 2) deploying fake topology. Our experiments on three real-world and two large-scale generated network topologies demonstrate that ChameleonNet can effectively reduce similarity between inferred and real topologies by 31%-37% and reliably hide critical topology information in terms of multiple statistical metrics.

Edge storage systems have drawn many efforts to extend the storage and service capabilities of cloud data centers. A pivotal aspect lies in the data-sharing mechanism, which integrates geographically dispersed weak edge servers into an efficient storage system. It enables users to launch data operations at any server and retrieve the desired data across the distributed system. However, it remains open to meeting the increasing demand for similarity retrieval across edge servers. The intrinsic reason is that the existing solutions can only return an exact data match for a query while more general edge applications require the data similar to a query input from any server. To fill this gap, this paper pioneers the similarity edge data sharing mechanism, a new paradigm to support high-dimensional similarity search at network edges. First, through deeply thinking about the nature of similarity data sharing, we propose the problem of Optimal Indexing and formulate it as the optimal transport problem from the data space to the network space. On this basis, we propose Prophet, the first known architecture for similarity data indexing at the edge. We first divide the feature space of data into plenty of subareas, then project both subareas and edge servers into a virtual space where the distance between any two points can reflect not only data similarity but also network latency. When any edge server submits a request for data insert, delete, or query, it computes the data feature and the virtual coordinate; and then iteratively forwards the request via greedy routing based on the forwarding tables and the virtual coordinates. By Prophet, similar high-dimensional features would be stored by a common server or several nearby servers. Compared with distributed hash tables in P2P networks, Prophet requires to visit logarithmic servers for a data request and reduces the network latency from the logarithmic to the constant level of the server number. Evaluation results indicate that Prophet achieves the comparable retrieval accuracy and significantly shortens the query latency compared with centralized schemes, while the load balancing performance is nearly optimal.

Service Function Chaining (SFC) dynamically links multiple Virtual Network Functions (VNFs) to provide flexible and scalable network services for network entities and users. Implementing SFCs at the network edge provides instant VNF service yet is confined by the limited edge resources. Existing strategies suggest either to deploy new VNFs for diverse service provision or to deploy more installed VNFs for reliable service provision. However, these one-sided optimizations fail to realize comprehensive improvements in the network service quality. To this end, the motivation of this paper is to consider a more comprehensive SFC deployment plan to provide more efficient network services. In this paper, we propose DeepSFC, an online SFC deployment scheme at network edge. Our DeepSFC considers the impact of resource allocations and deployment locations on the average latency of overall service requests. It realizes an elegant trade-off between the diversity and the availability of SFCs by adopting the Deep Reinforcement Learning (DRL) method. To be specific, we first determine the type and number of VNFs that need to be deployed. Thereafter, we optimize the deployment locations of these chosen VNFs in the service chain, considering the impact of dynamic bandwidth in the real network. For more general scenarios wherein users’ service requirements change or the deployed server crashes, we further relocate the VNF deployment with the joint consideration of performance degradation and migration cost. Evaluation results show that DeepSFC outperforms its competitors in various experimental settings and responds the requests with lower average latency.

Traditional network functions are typically implemented using specialized hardware appliances, which are expensive and difficult to upgrade. Network Function Virtualization (NFV) offers an effective approach to address these challenges by implementing comparable functionalities on commercial servers through software-based virtualization. In NFV, a sequence of Virtual Network Functions (VNFs) is orchestrated to form a Service Function Chain (SFC) that provides flexible network services. However, scheduling SFCs with multiple resource constraints to achieve high reliability poses a critical challenge. Existing approaches often assume offline scheduling and overlook the dynamic nature of heterogeneous resource loads across regions. Moreover, they primarily focus on individual VNFs rather than considering the cross-region scheduling of the entire SFC, which can result in increased transmission delay. In this paper, we investigate the problem of service function chain scheduling across multiple regions (SFCS-MR) with deadline constraints, aiming to maximize the success rate of requests. We formulate this problem as an Integer Linear Programming (ILP) model and prove its NP-hardness. To address this problem effectively, we propose a two-stage algorithm that determines whether an SFC requires cross-region scheduling and selects the suitable regions for its execution. Through extensive experimental evaluations, we demonstrate that our cross-region SFC scheduling solution can achieve a maximum improvement of 32.42% in the overall request success rate compared to benchmarks.

Each flow usually needs to traverse a specific service function chain (SFC), which is composed of multiple network functions implemented through virtualization technology or hardware, before reaching their destinations. All network functions are deployed across commodity nodes inside a network environment. Each flow needs to change its default routing path to visit the corresponding SFC correctly. These changed routing paths will cause network load imbalance. Therefore, an intelligent routing planning method is needed to balance the traffic load while satisfying various SFC requirements of different flows. In this paper, we propose to leverage SRv6, a new routing technology, to centrally plan the routing path for each flow with any SFC request. We then present a general model of the SFC planning problem (SFCP), planning flows’ routing paths to minimize the maximum link utilization of the network, and prove that the problem is NP-hard. For this reason, we transform the SFCP problem into a graph theory optimization problem and propose SFCPlanner, an online SFC planning method based on deep reinforcement learning. Moreover, we design the node mask and incremental training mechanisms to make SFCPlanner achieve better performance. The experiment results show that our SFCPlanner can solve the SFCP problem in large-scale networks more precisely. It can reduce the maximum link utilization by 32% compared with the benchmark algorithm while ensuring each flow traverses the correct SFC.

The rapid growth of mobile video traffic and user demand poses a more stringent requirement for efficient bandwidth allocation in mobile networks where multiple users may share a bottleneck link. This provides content providers an opportunity to jointly optimize multiple users’ experiences but users often suffer short connection durations and frequent handoffs because of their high mobility. In this paper, we propose an end-to-end scheme, VSiM, for supporting mobile video streaming applications in heterogeneous wireless networks. The key idea is allocating bottleneck bandwidth among multiple users based on their mobility profiles and Quality of Experience (QoE)-related knowledge to achieve max-min QoE fairness. Besides, the QoE of buffer-sensitive clients is further improved by the novel server push strategy based on HTTP/3 protocol without affecting the existing bandwidth allocation approach or sacrificing other clients’ view quality. VSiM is lightweight and easy to deploy in the real world without touching the underlying network infrastructure. We evaluated VSiM experimentally in both simulations and a lab testbed on top of the HTTP/3 protocol. We find that the clients’ QoE fairness of VSiM achieves more than 40% improvement compared with state-of-the-art solutions, i.e., the viewing quality of clients in VSiM can be improved from 720p to 1080p in resolution. Meanwhile, VSiM provides about 20% improvement of average QoE.

In Network Function Virtualization (NFV), a series of Virtual Network Functions (VNFs) organized in a specific order (called Service Function Chain, SFC) could offer an end-to-end network service for a network flow. Recently, with the new results of the exploration of VNF parallelism, hybrid SFC (SFC contains parallel VNFs) is proposed to reduce the SFC execution delay. However, it remains challenging and open to optimally embed multiple hybrid SFCs into the network. In this paper, we target at the optimal embedding problem of multiple hybrid SFCs with the purpose of minimizing the cost in an online scenario. Specifically, we propose SFT-Box, an online approach that can respond to hybrid SFC embedding requests in real-time. SFT-Box is designed to i) transform SFCs from the traditional sequential form to a standardized hierarchical Service Function Tree (SFT) form, ii) calculate and store the low-cost sub-solutions of embedding common SFTs, and iii) provide prompt solution response based on stored sub-solutions. To the best of our knowledge, this is the first work to address the online optimal embedding problem of multiple hybrid SFCs. With extensive evaluations, we demonstrate that, compared with the benchmark methods, SFT-Box can achieve up to 30% cost-saving and at least$22\times $latency reduction in enabling real-time response.

The modern network is equipped with many service functions to acquire high-quality service. The emergence of network function virtualization (NFV) provides a convenient way to accomplish the network services in the form of virtual network function (VNF) and also makes the scheduling solution of VNFs flexible. The VNFs can be deployed on commodity servers as software processes. Besides, multiple VNFs are chained in a specified order as a service function chain (SFC) to serve a given flow, increasing the scheduling difficulty to minimize the average flow completion time. In this paper, we study the problem of scheduling multiple SFCs with the constraint of different resource limitations in various commodity servers. This problem is typically formulated as an Integer Linear Programming (ILP) problem, which is NP-hard. To well tackle this problem, we propose a deep reinforcement learning (DRL) approach. It involves multi-step decision making, which can be naturally transformed into a DRL problem. We design specific reward and state representations for such a multi-resource scheduling problem. We also consider how to use DRL to handle online requests of SFCs. The experiment results demonstrate that the DRL approach can significantly reduce the average completion time of a set of SFC and achieves a cost saving of 39.94% against the benchmark method.

The rapid growth of mobile video traffic and user demand poses a more stringent requirement for efficient bandwidth allocation in mobile networks where multiple users may share a bottleneck link. This provides content providers an opportunity to optimize multiple users’ experiences jointly, but users often suffer short connection durations and frequent handoffs because of their high mobility. This paper proposes an end-to-end scheme, VSiM, to support mobile video streaming applications in heterogeneous wireless networks. The key idea is allocating bottleneck bandwidth among multiple users based on their mobility profiles and Quality of Experience (QoE)-related knowledge to achieve max-min QoE fairness. Besides, the QoE of buffer-sensitive clients is further improved by the novel server push strategy based on HTTP/3 protocol without affecting the existing bandwidth allocation approach or sacrificing other clients’ view quality. We evaluated VSiM experimentally in both simulations and a lab testbed on top of the HTTP/3 protocol. We find that the clients’ QoE fairness of VSiM achieves more than 40% improvement compared with state-of-the-art solutions, i.e., the viewing quality of clients in VSiM can be improved from 720p to 1080p in resolution. Meanwhile, VSiM provides about 20% improvement on average of the averaged QoE.

Data centers usually employ scale-out network topologies to provide sufficient network bandwidth for applications. The traditional equal-cost multi-path (ECMP) routing method is proposed to tackle the serious load imbalance problem across all links. However, it does not achieve the desired performance and still incurs low network throughput. Consequently, researchers recently redesigned some load balancing mechanisms for data center networks (DCNs) from different design dimensions. However, it remains open to systematically measure and evaluate their performance in various settings. It is impractical for evaluators to implement or simulate involved load balancing mechanisms. In this paper, we propose a unified framework, UFLB, which can well model and emulate representative load balancing mechanisms for data center networks in a lightweight way. This framework has overcome three significant challenges: model traffic distribution in the symmetry as well as asymmetry data center networks, characterize mainstream load balancing methods, and systematically combine them with high accuracy. We evaluate the effectiveness of our model under not only general settings of data center networks but also some special settings, such as various link failures and asymmetric topologies. The results indicate that the deviation rate of UFLB is within 15% against the implementation of load balancing mechanisms, such as ECMP, CONGA, DRILL, HERMES, PRESTO, in NS2, while it can be several orders of magnitude faster.

The limitation on the flight range motivates a hybrid monitoring system, wherein trucks carrying drones drive to pre-planned positions and then free drones for task execution. While the flight range limitation is mitigated, it is challenging to determine the destination of trucks and drones and set airborne cameras. This paper optimizes the joint Deployment of trUcks and dronEs for objecT monitoring (DUET), that is, deploy a set of trucks where each truck carries drones, and each drone is equipped with a varifocal camera such that the overall monitoring utility for target objects is maximized. To tackle the DUET problem, we first model the hybrid system and monitoring utility; then, discretize the solution space of DUET with performance bound. In this way, the problem is transformed into a two-level combinatorial optimization problem satisfying submodularity. To address it, a two-level greedy algorithm with $\frac{{{{(e - 1)}^2}}}{{e(2e - 1)}} \cdot (1 - \varepsilon )$ approximation ratio is proposed to select deployment strategies. After the strategy selection, an optimal method is devised to carefully adjust the strategy for energy saving and communication improvement without loss of monitoring utility. Both simulations and field experiments are conducted to evaluate the proposed framework, which outperforms baseline algorithms on monitoring utility by at least 28.4% and 40%, respectively.

Owing to the advancement of the Internet of Things (IoT) and 5G mobile technologies, various IoT devices produce massive data, which is usually transferred to nearby sites, such as edge nodes or datacenters. Many large-scale IoT applications need to analyze the data distributed across multiple sites to obtain final results. A dominant challenge of this type of data analytics is the heterogeneities of resource capacities across geo-distributed sites. In this article, we find that the resource capacity as well as the resource price differ among sites, and the price heterogeneity has a significant impact on geo-distributed IoT data analytics. Thus, each geo-distributed IoT data analytics job prefers to minimize the job execution cost while guaranteeing its deadline requirement under the resource constraints of involved sites. Specifically, we propose to jointly consider the resource heterogeneities of both capacity and price, and minimize the cost of each job before its deadline. We characterize this optimization problem as a quadratically constrained quadratic programming problem. To tackle such an NP-hard problem, we propose the minimize the job completion cost before a given deadline (MCGL) method, which calculates a task placement solution by the gradient adjustment strategy according to the remarkable negative correlation relationship between job completion time and job completion cost of geo-distributed IoT data analytics job. The task placement strategy can optimize resource cost with respect to the deadline requirement of any geo-distributed data analytics job. The trace-driven evaluations indicate that MCGL significantly reduces the total cost compared with existing methods; moreover, they satisfy the deadline constraints simultaneously.

As the development of new generation mobile communication technology, the mobile core network also needs to be upgraded by new network technologies, e.g., software defined networking (SDN) and network function virtualization (NFV). With NFV, virtual network functions (VNFs) can be deployed on commodity devices to support various network function requirements and attain system's flexibility and elasticity in network edge. Meanwhile, a set of selected VNFs are usually chained as a service function chain (SFC) to serve a given flow in a specified order. Since the devices have heterogeneous execution environments and the VNFs have various requirements, one fundamental challenge is how to embed SFC for each flow on the shared NFV infrastructure (NFVI) with the goal of minimizing the flow completion time. Furthermore, multiple flows always compete for resources of those devices hosting SFCs. In this general setting, there is an urgent need to study efficient scheduling mechanism to minimize the total completion time of all flows. In this paper, by jointly considering VNF placement and flow scheduling, we first formulate this problem as an integer programming problem, and further prove that it is NP-hard in general case. We then design a PDG method to find the optimal solution in single flow case and an LRD method to achieve a high-quality feasible solution in multiple flows case. The extensive experiment results indicate that our LRD method can reduce the total completion time of all flows by 22.04, 60.99 and 39.95, percent against three compared methods, respectively.

Many organizations nowadays have multiple sites at different geographic locations. Typically, transmitting massive data among these sites relies on the interconnection service offered by ISPs. Segment Routing over IPv6 (SRv6) is a new simple and flexible source routing solution which could be leveraged to enhance interconnection services. Compared to traditional technologies, e.g., physical leased lines and MPLS-VPN, SRv6 can easily enable quick-launched interconnection services and significantly benefit from traffic engineering with SRv6-TE. To parse the SRv6 packet headers, however, hardware support and upgrade are needed for the conventional routers of ISP. In this paper, we study the problem of SRv6 incremental deployment to provide a more balanced interconnection service from a traffic engineering view. We formally formulate the problem as an SRID problem with integer programming. After transforming the SRID problem into a graph model, we propose two greedy methods considering short-term and long-term impacts with reinforcement learning, namely GSI and GLI. The experiment results using a public dataset demonstrate that both GSI and GLI can significantly reduce the maximum link utilization, where GLI achieves a saving of 59.1% against the default method.

Many hardware-based security middleboxes have been deployed in the networks to defend against different threats. However, these hardware middleboxes are hard to upgrade or migrate. The emergence of network functions virtualization (NFV), which realizes various security functions in the form of virtual network functions (VNFs), brings many benefits to network security. To improve the security level further, several VNFs are coordinated in a pre-defined order to form service function chains (SFCs). It is expected that the SFCs are embedded properly with low cost, including the VNF setup cost and the flow routing cost. In this paper, we find that when an SFC is required by multiple flows for the identical network security threats, the total cost could be reduced by embedding an aggregated service function tree (ASFT) instead of multiple independent SFCs. We formally characterize the integer programming model of this problem and prove that it is NP-hard. Then we propose a performance-guaranteed approximation algorithm and prove that the algorithm could find the optimal solution in a special case. Extensive experiments indicate that our method can reduce the total cost by$22.0\%$and$24.1\%$against two compared algorithms, respectively.

Existing Internet routing protocols much focus on providing interconnection service for independent autonomous systems (ASes) rather than end-to-end low latency transmission. Nowadays, a growing number of applications and platforms have high requirements for low latency. However, developing new routing protocols in the wide area network that provides low latency routing service is very challenging, and remains an open problem due to the obstacles of compatibility, feasibility, scalability and efficiency. On the other hand, the ignorance of latency performance results in triangle inequality violations (TIV). In this paper, we leverage TIV and a new routing technology, SRv6, to build a new distributed routing protocol, SRv6 underlay federation (SRUF), which aims to provide low-latency routing services in network core. We design a novel method to find alternative paths with lower latency between any pair of ASes in SRUF. This method can achieve high scalability as it incurs only$O(n)$bandwidth overhead in each member of SRUF. SRv6 is then employed to steer the flows along the selected indirect low-latency paths, while keeping compatibility to legacy routing systems. The experimental results with realworld datasets demonstrate that SRUF can effectively reduce the average end-to-end delay by 5.4% ~ 58.9%.

Blockchain-powered edge computing (BEC) is a promising extension to strengthen the security and the trustworthiness among collaborative edge clouds for delivering computation-intensive and delay-sensitive services in the environments of IoT and 5G. A fundamental challenge is how to respond to the maximum number of IoT requests at the network edge instead of the remote cloud. Although some work has been done to consider service provisioning and request scheduling in collaborative edge clouds, they assume that a single service is used to respond to each request. This assumption, however, is not practical to meet the demand of emerging IoT applications. In reality, the request needs to call a set of services with a chain-based structure. To tackle this challenge, in this article, we first propose a chain-based service request model for emerging IoT applications and further study the joint service provisioning and request scheduling problem for chain-based service requests at the network edge. We characterize this problem as an integer linear programming (ILP) model and prove the NP-hardness of this joint optimization problem. Furthermore, we prove that the related problem is of approximate submodularity with an approximation ratio guarantee. Finally, a novel two-stage optimization (TSO) scheme is proposed, and the results of extensive experiments show the efficiency and the effectiveness of the TSO scheme.

The emergence of large-scale dynamic sets in networked and distributed applications attaches stringent requirements to approximate set representation. The existing data structures (including Bloom filter, Cuckoo filter, and their variants) preserve a tight dependency between the cells or buckets for an element and the lengths of the filters. This dependency, however, degrades the capacity elasticity, space efficiency and design flexibility of these data structures when representing dynamic sets. In this paper, we first propose the Index-Independent Cuckoo filter (I2CF), a probabilistic data structure that decouples the dependency between the length of the filter and the indices of buckets which store the information of elements. At its core, an I2CF maintains a consistent hash ring to assign buckets to the elements and generalizes the Cuckoo filter by providing optional${k}$candidate buckets to each element. By adding and removing buckets adaptively, I2CF supports the bucket-level capacity alteration for dynamic set representation. Moreover, in case of a sudden increase or decrease of set cardinality, we further organize multiple I2CFs as a Consistent Cuckoo filter (CCF) to provide the filter-level capacity elasticity. By adding untapped I2CFs or merging under-utilized I2CFs, CCF is capable of resizing its capacity instantly. The trace-driven experiments indicate that CCF outperforms its alternatives and realizes our design rationales for dynamic set representation simultaneously, at the cost of a little higher complexity.

A large number of servers are interconnected using a specific datacenter network to deliver the infrastructure as a service (IaaS). Multicast can jointly utilize the network resources and further reduce the consumption of network bandwidth more than individual unicast. The source of a multicast service, however, does not need to be in a specific location as long as certain constraints are satisfied. This means the multicast can have uncertain sources, which could reduce the network resource consumption more than a traditional multicast service and further improve the quality of service. In this paper, we propose a novel reliable multicast service with uncertain sources named ReMUS. The goal is to minimize the sum of the transfer cost and the recovery cost, although finding such a ReMUS is very challenging. Thus, we design a source-based multicast method to solve this problem by exploiting the flexibility of sources when no recovery nodes exist in the network. Furthermore, we design a general multicast method to jointly exploit the benefits of uncertain sources and recovery nodes to minimize the total cost of ReMUS. We conduct extensive evaluations under Internet2 and datacenter networks. The results indicate that our methods can efficiently realize the reliable and scalable multicast with uncertain sources, irrespective of the settings of networks and multicasts. To the best of our knowledge, we are the first to study the reliable multicast service under uncertain sources.

City-wide package delivery has become popular due to the dramatic rise of online shopping. It places a tremendous burden on the traditional logistics industry, which relies on dedicated couriers and is labor-intensive. Leveraging the ridesharing systems is a promising alternative, yet existing solutions are limited to one-hop ridesharing or need consignment warehouses as relays. In this paper, we propose a new package delivery scheme which takes advantage of multi-hop ridesharing and is entirely consignment free. Specifically, a package is assigned to a taxi which is guided to deliver the package all along to its destination while transporting successive passengers. We tackle it with a two-phase solution, named PPtaxi. In the first phase, we use the Multivariate Gaussian distribution and Bayesian inference to predict the passenger orders. In the second phase, both the computation efficiency and solution effectiveness are considered to plan package delivery routes. We evaluate PPtaxi with a real-world dataset from an online taxi-taking platform and compare it with multiple benchmarks. The results show that the successful delivery rate of packages with our solution can reach 95 percent on average during the daytime, and is at most 46.9 percent higher than those of the benchmarks.

Large-scale datacenters are the key infrastructures of cloud computing. Inside a datacenter, a large number of servers are interconnected using a specific datacenter network to deliver the infrastructure as a service (IaaS) for tenants. To realize novel cloud applications like the network virtualization and network isolation among tenants, the principle of software-defined network (SDN) has been applied to datacenters. In the setting, multiple distributed controllers are deployed to offer a control plane over the entire datacenter to efficiently manage the network usage. Despite such efforts, cloud datacenters, however, still lack a scalable and resilient control plane. Consequently, this paper systematically studies the coverage problem of controllers, which means to cover all network devices using the least number of controllers. More precisely, we tackle this essential problem from three aspects, including the minimal coverage, the minimal fault-tolerant coverage, and the minimal communication overhead among controllers. After modelling and analyzing such three problems, we design efficient approaches to approximate the optimal solution, respectively. Extensive evaluation results indicate that our approaches can significantly save the number of required controllers, improve the fault-tolerant capability of the control plane and reduce the communication overhead of state synchronization among controllers. The design methodologies proposed in this paper can be applied to cloud datacenters with other networking structures after minimal modifications.

The emergence of large-scale dynamic sets in networking applications attaches stringent requirements to approximate set representation. The existing data structures (including Bloom filter, Cuckoo filter, and their variants) preserve a tight dependency between the cells or buckets for an element and the lengths of the filters. This dependency, however, degrades the capacity elasticity, space efficiency and design flexibility of these data structures when representing dynamic sets. In this paper, we first propose the Index-Independent Cuckoo filter (I2CF), a probabilistic data structure that decouples the dependency between the length of the filter and the indices of buckets which store the information of elements. At its core, an I2CF maintains a consistent hash ring to assign buckets to the elements and generalizes the Cuckoo filter by providing optional k candidate buckets to each element. By adding and removing buckets adaptively, I2CF supports the bucket-level capacity alteration for dynamic set representation. Moreover, in case of a sudden increase or decrease of set cardinality, we further organize multiple I2CFs as a Consistent Cuckoo filter (CCF) to provide the filter-level capacity elasticity. By adding untapped I2CFs or merging under-utilized I2CFs, CCF is capable of resizing its capacity instantly. The trace-driven experiments indicate that CCF outperforms its alternatives and realizes our design rationales for dynamic set representation simultaneously, at the cost of a little higher complexity.

Usually, a data flow needs to traverse a series of network functions, which is called a service function chain (SFC), before reaching its destination. The emergence of network function virtualization (NFV) makes the embedding solution of the SFC flexible as far as the deployment location is concerned. When providers embed the SFC into a substrate network, they will hope to minimize the setup cost of the SFC and link connection cost toward clients. For unicast, since there is one path connecting the source node to the destination node, all functions of the SFC are just needed to be deployed along the path. However, when embedding the SFC for a multicast task, the topology of the SFC may change because the function deployment locations have impacts on the traffic delivery cost. Thus, a service function tree (SFT) may be a better choice. Given the huge space of SFT embedding solutions, however, it is extremely hard to find the optimal one such that the total traffic delivery cost is minimized. In this paper, we tackle the optimal SFT embedding problem in the NFV enabled multicast task. Specifically, we formally define the problem and formulate it with an integer linear programming (ILP), which turns out to be NP-hard. Then, a two-stage method is proposed to deal with the problem with an approximation ratio of$1+\rho $, where$\rho $is the best approximation ratio of Steiner tree and can be as small as 1.39. With extensive experimental evaluations, we demonstrate that by applying our SFT embedding solution, the delivery cost of multicast traffic can be reduced by 22.05% at most against three benchmarks.

The design of distributed control plane is an essential part of SDN. While there is an urgent need for verifying the control plane, little, however, is known about how to validate that the control plane offers assurable performance, especially across various failures. Such validation is hard due to two fundamental challenges. First, the number of potential failure scenarios could be exponential or even non-enumerable. Second, it is still an open problem to model the performance change when the control plane employs different failure recovery strategies. In this paper, we first characterize the validation of the distributed control plane as a robust optimization problem and further propose a robust validation framework to verify whether a control plane provides assurable performance across various failure scenarios and multiple failure recovery strategies. Then, we prove that identifying an optimal recovery strategy is NP-hard after developing an optimization model of failure recovery. Accordingly, we design two efficient failure recovery strategies, which can well approximate the optimal strategy and further exhibit good performance against potential failures. Furthermore, we design the capacity augmentation scheme when the control plane fails to accommodate the worst failure scenario even with the optimal failure recovery strategy. We have conducted extensive evaluations based on an SDN test bed and large-scale simulations over real network topologies. The evaluation results show the efficiency and effectiveness of the proposed validation framework.

In network traffic engineering, multicast is designed to deliver the same content from a single source to a group of destinations. Recently, NFV enabled multicast has been developed by deploying virtual network functions (VNFs) over the target network. To fulfill the multicast task with a service function chain (SFC) requirement, a service function tree (SFT) embedded in the shared multicast tree has to be built. Given the huge space of SFT embedding solutions, however, it is extremely hard to find the optimal one such that the total traffic delivery cost is minimized. In this paper, we tackle the optimal SFT embedding problem in NFV enabled multicast task. Specifically, we formally define the problem and formulate it with an integer linear programming (ILP), which turns out to be NP-hard. Then, a two-stage algorithm is proposed to deal with the problem with an approximation ratio of 1+p, where p is the best approximation ratio of Steiner tree and can be as small as 1.39. With extensive experimental evaluations, we demonstrate that by applying our SFT embedding solution, the cost saving of multicast traffic delivery can be up to 22.41%, compared with the random SFT embedding strategy.

Network Function Virtualization (NFV) is an emerging technology, which enables service agility, flexibility and cost reduction by replacing traditional hardware middleboxes with Virtual Network Functions (VNFs) running on general-purpose servers. Service Function Chain (SFC) constitutes an end-to-end service by organizing a series of VNFs in a specific order. Particularly, hybrid SFC (SFC with parallel VNFs) is proposed to much reduce the traffic delay in sequential SFCs. Nevertheless, how to strategically select VNF instances and links in hybrid SFC embedding remains an open problem. In this paper, we target at the cost minimization and address the optimal hybrid SFC embedding problem. Specifically, we first develop a novel abstraction model for the hybrid SFC with Directed Acyclic Graph (DAG), which helps convert diverse hybrid SFCs to the standardized DAG-SFC form. Then, we formulate the optimal DAG-SFC embedding problem as an integer optimization model and propose a greedy method (called BBE) to solve the NP-hard problem. MBBE method is developed upon BBE method to further cut down the computation complexity in model solving. Extensive simulation results demonstrate the effectiveness of our approach for cost reduction in hybrid SFC embedding.

Multicast can efficiently reduce the consumption of network resources by jointly serving multiple destinations with a single source node along a Steiner tree. Nowadays many applications employ a given replica system to improve the service quality; hence, each file and its replicas are usually distributed among multiple servers. In this setting, uncertain multicast is proposed as a novel and general model of multicast transfer. That is, a multicast group offers multiple source nodes instead of a single one. As a result, the multicast routing usually forms a forest, consisting of multiple isolated trees. In this paper, we focus on characterizing and constructing the minimum cost forest (D-MCF) for any uncertain multicast, which satisfies the constraint of end-to-end delay, between any pair of source and destination in the resulting forest at the same time. Prior methods for building a minimum cost forest for an uncertain multicast remain inapplicable to this new problem. Accordingly, we first show an observation about the D-MCF problem and formalize it as an Integer Programming model. We then prove that D-MCF is a NP-hard problem and accordingly design two efficient algorithms, the partition algorithm (PA) and the combination algorithm (CA), to approximate the optimal solution. PA first divides uncertain multicast into several deterministic multicast groups and then combines those routing trees for deterministic multicast. In contrast, CA combines each feasible unicast path for each destinations. Analyses and evaluations indicate that our two methods can produce more desired routing forest than prior method regardless of the delay bound. Also, our PA method can achieve better balance between the performance and time consumption than our CA method. The evaluation results show that PA can reduce 49.02% total cost at the cost of incurring extra 12.59% time consumption, significantly outperforming the CA method.

Summary Multicast performs better than unicast in delivering the same content from a fixed single source to a set of destinations. Many efforts have been made to optimize such kind of deterministic multicast, such as minimizing the transmission cost of each multicast session. In practice, it is not necessary that the source of each multicast session has to be in a specific location, as long as certain constraints are satisfied. Accordingly, applications usually meet a novel multicast with uncertain sources, ie, uncertain multicast. That is, multiple nodes have the responsibility to act as the root node of a multicast session. Prior proposals have addressed an uncertain multicast by constructing the minimum cost forest. However, it is still unknown how to efficiently share the network resources, when a set of uncertain multicast occupies the network simultaneously. To tackle such a challenging issue, we present the packing problem of uncertain multicasts (MPU) to minimize the total transmission cost, under the constraint of link capacity. We prove that the MPU problem is NP‐hard. An intrinsic solution is constructing the minimum cost forest for each uncertain multicast individually. This method, however, is inefficient and may be infeasible because of the constraint of link capacity. Thus, we design 2 dedicated greedy methods, named priority‐based and adjusting congested link, to approximate the optimal solution. The comprehensive results indicate that both of our 2 methods can find a feasible solution for the MPU problem. Moreover, given a set of uncertain multicasts, the adjusting congested link method can generate a desired transmission structure for each uncertain multicast and achieve the least total cost when packing them.

Multicast is designed to jointly deliver content from a single source to a set of destinations. It can efficiently save the bandwidth consumption and reduce the load on the source. The appearance of SDN provides opportunities to deploy flexible protocols, including multicast and its variants. However, in many important applications, it is not necessary that the source of a multicast transfer has to be in specific location as long as certain constraints are satisfied. Such facts bring a novel multicast with uncertain sources, abbreviated as uncertain multicast. It brings new opportunities and challenges to reduce the bandwidth consumption. In this paper, we focus on the uncertain multicast and construct a forest with the minimum cost (MCF), to enable that each destination reaches to one and only one source. Prior approaches, relying on traditional multicast, remain inapplicable to the MCF problem. Therefore, we propose two (2+ε)-approximation methods, named P-MCF and E-MCF, which can be deployed in SDN controllers. We conduct experiments on our SDN testbed together with large-scale simulations under the random SDN network. All manifest that our MCF approach always occupies less network links and incurs less network cost for an uncertain multicast than the traditional Steiner minimum tree (SMT) of any related multicast, irrespective of the used network topology and the setting of multicast transmissions.