Accurate and comprehensive data acquisition is critical for modern data-driven environmental applications. Mobile Crowdsensing (MCS) offers an effective approach by leveraging user participation to collect environmental data through task assignment. To minimize costs, MCS platforms often partition the environment into subareas and utilize inference algorithms to extrapolate data for entire subareas based on partial sensing in a limited subset. However, determining the optimal set of users for sensing tasks remains challenging due to constraints such as user availability and the complexity of data inference models. This paper introduces Sensify, a task assignment strategy that optimizes data acquisition by accounting for data correlations and budget constraints. Sensify efficiently selects subareas and recruits cost-effective users for sensing tasks, incorporating user-specific contexts such as location and device power availability during task assignment. To adaptively manage the platform budget, the strategy considers a dynamic set of users with varying costs over time. A deep recurrent reinforcement learning-based network is employed to select optimal subareas for sensing, while user recruitment is dynamically optimized using a reinforcement learning approach. Specifically, a modified Contextual Combinatorial Multi-Armed Bandit (CC-MAB) framework is utilized to handle the volatility and variability in user costs. Experiments conducted on two real-world datasets demonstrate that Sensify can improve data acquisition by up to 7% compared to existing approaches.

Traffic sampling has become an indispensable tool in network management. While there exists a plethora of sampling systems, they generally assume flow rates are stable and predictable over a sampling period. Consequently, when deployed in networks with dynamic flow rates, some flows may be missed or under-sampled, while others are over-sampled. This paper presents the design and evaluation of dSamp, a network-wide sampling system capable of handling dynamic flow rates in Software-Defined Networks (SDNs). The key idea in dSamp is to consider flow rate fluctuations when deciding on which network switches and at what rate to sample each flow. To this end, we develop a general model for sampling allocation with dynamic flow rates, and then design an efficient approximate integer linear program called APX that can be used to compute sampling allocations even in large-scale networks. To show the efficacy of dSamp for network monitoring, we have implemented APX and several existing solutions in ns-3 and conducted extensive experiments using model-driven simulations. Our results indicate that, by considering dynamic flow rates, APX outperforms the existing solutions by up to 10% in sampling more flows at a given sampling rate.

Software-defined networks (SDNs) provide customizable traffic control by storing numerous rules in on-chip memories with minimal access latency. However, the current on-chip memory capacity falls short of meeting the growing demands of SDN control applications. While rule eviction and aggregation strategies address this challenge at the switch level, programmable data planes enable a more flexible approach through cooperative rule caching. However, current solutions rely on computationally intensive off-the-shelf solvers to perform rule placement across the network. In this paper, we present an efficient solution for the cooperative rule caching problem. We first present the design of a resource-efficient switch capable of caching rules for its neighbors alongside a lightweight protocol for retrieving cached rules. Then, we introduce RaSe, an approximation algorithm for minimizing rule lookup latency across the network through optimized cooperation-aware rule placement. We conduct a theoretical analysis of RaSe, followed by a P4-based proof-of-concept assessment in Mininet and a large-scale numerical evaluation using real-world network topology. In comparison with existing solver-based solutions, the proposed method obtains the solution 160 times faster and improves the average rule lookup latency by about 21% compared to several algorithmic baselines.

Decentralized federated learning (DFL) enables collaborative training of machine learning models without sharing sensitive data. As such, its application in vehicular networks has gained significant attention. At the core of DFL is the so-called model aggregation, in which each vehicle combines its locally trained model with those received from its neighboring vehicles to generate an updated model that, over time, converges to a global model shared by all vehicles. However, due to high mobility and wireless communication, vehicle-to-vehicle communication is lossy. As a result, a vehicle may receive its neighboring vehicle models only partially. A technical challenge in DFL is how to efficiently utilize such partial models to speed up model training without increasing the training overhead. In this paper, we present an Adaptive Model Aggregation (AMA) algorithm to address this challenge. Our algorithm runs asynchronously on each vehicle and uses a threshold to decide whether to use a partially received model for aggregation. We show that due to the mobility of vehicles, a static threshold is not sufficient and subsequently develop an algorithm based on the contextual multi-arm bandit theory to adaptively compute an optimal threshold for each vehicle based on the dynamics of the network. We evaluate the performance of AMA in realistic environments that include different mobility patterns. Our results show that AMA can decrease DFL aggregation overhead by 83% without reducing the training accuracy compared to non-adaptive aggregation.

Disaggregated Data Center (DDC) is a modern datacenter architecture that decouples hardware resources from monolithic servers into pools of resources that can be dynamically composed to match diverse workload requirements. While disaggregation improves resource utilization, it could negatively impact workload slowdown due to the latency of accessing disaggregated resources over the datacenter network. To this end, we consider CPU and memory disaggregation and conduct measurements to experimentally profile several popular datacenter workloads in order to characterize the impact of disaggregation on workload execution slowdown. We then develop a workload placement algorithm, called Iterative Rounding-based Placement (IRoP), that given a set of workloads, determines where to place each workload (i.e., on which CPU) and how much local and remote memory allocate to it. The key insight in designing IRoP is that the impact of remote memory latency on slowdown can be substantially masked by assigning workloads to higher-performing CPUs, albeit at the cost of higher energy consumption. As such, IRoP aims to find a workload placement that minimizes the DDC energy consumption while respecting a bounded slowdown for each workload. We provide extensive simulation results to demonstrate the flexibility of IRoP in providing a wide range of trade-offs between energy consumption and workload slowdown. We also compare IRoP with several existing baselines. Our results indicate that IRoP can reduce energy consumption and slowdown in the considered scenarios by up to 8% and 12%, respectively.

Virtual private clouds have become a huge trend because of their cost-efficiency. However, the complex and virtualized nature of clouds limits the ability of cloud tenants to pinpoint and amend performance degradation problems, such as packet drops. Existing monitoring systems are either designed for the physical network or insufficient to present the concrete reason for packet loss with low overhead. In this paper, we present a Packet Loss Diagnosis (PLD) system, a specific monitoring service designed to detect packet drops on cloud networks and report diagnosis information to tenants. PLD is based on the modern capabilities of P4 data plane programmable NICs and has a limited footprint in the network. It provides detailed information that enables tenants to locate and resolve their issues with respect to the abstraction of the services. It also meets the requirements of a monitoring system designed for large-scale multi-tenant clouds. We implemented the proposed scheme in P4 to demonstrate its viability and investigate its performance and overhead through extensive experiments and Mininet simulation. Our results show that PLD ensures full packet drop detection coverage and can notify tenants in real-time while imposing low overhead.

Edge computing provides computational resources in the vicinity of end-users to reduce delay compared to traditional remote clouds. However, the capacity of edge resources usually is not sufficient for the required computational demands. Therefore, it is necessary to design methods for employing these resources in an efficient manner. On the other hand, network function virtualization (NFV) is a promising solution to use the network resources in a more flexible way than traditional schemes. Although more focus has been on realization of NFV systems via virtual machines so far, recent studies show that container-based solutions can improve efficiency thanks to lightweight implementation and layered structure of containers. Nonetheless, to the best of our knowledge, there is no comprehensive study on the problem of orchestrating services composed of a chain of containerized network functions in edge networks. In this paper, we consider this scenario when service requests are submitted to the system and address important aspects of this problem such as downloading and sharing container layers and steering traffic among network functions. We present the formulation of the problem as an integer linear program (ILP) and prove its NP-hardness. Then, to handle this problem, we propose RCCO, a polynomial-time algorithm based on ideas from deterministic and randomized rounding framework. Our results from extensive evaluations show that the bandwidth consumption of the proposed algorithm compared to the optimal algorithm is higher by only about 4% while it can outperform baselines from literature by more than 37%.

As the scale and speed of modern networks continue to increase, traffic sampling has become an indispensable tool in network management. While there exist a plethora of sampling solutions, they either provide limited flow visibility or have poor scalability in large networks. This paper presents the design and evaluation of FlowShark, a high-visibility per-flow sampling system for Software-Defined Networks (SDNs). The key idea in FlowShark is to separate sampling decisions on short and long flows, whereby sampling short flows is managed locally on edge switches, while a central controller optimizes sampling decisions on long flows. To this end, we formulate flow sampling as an optimization problem and design an online algorithm with a bounded competitive ratio to solve the problem efficiently. To show the feasibility of our design, we have implemented FlowShark in a small OpenFlow network using Mininet. We present experimental results of our Mininet implementation as well as performance benchmarks obtained from packet-level simulations in larger networks. Our experiments with a machine learning based Traffic Classifier application show up to 27% and 19% higher classification recall and precision, respectively, with FlowShark compared to existing sampling approaches.

Efficient and consistent update of the network routing rules is a challenging task that significantly affects the performance, correctness, and security of Software-Defined Networks (SDN). In this work, we consider the problem of minimizing the makespan of updating the routing rules in SDNs, while guaranteeing three crucial consistency requirements: (1) WayPoint Enforcement, (2) Loop Freedom, and (3) Conflict Freedom. This problem is known to be NP-hard, and thus we focus on designing approximate algorithms that run in polynomial time without incurring TCAM storage overhead. To compute consistent rule-update schedules, we propose two algorithms, calledTimeXandRMS.TimeXemploys the solution of a linear program (LP) to address the makespan minimization goal systematically.RMSis an LP-independent heuristic that provides higher scalability. We demonstrate and utilize a property of rule-updates, called reversibility, to reduce the makespan in RMS. Extensive simulations show that our algorithms reduce the makespan by 2% to 18% and attain a 4.9$\times$speedup compared to previous studies. Moreover, Mininet experiments reveal that the proposed algorithms can mitigate the transient congestion caused by conflicting flows.

As network virtualization becomes ubiquitous, legacy hardware-based traffic monitoring systems are no longer viable for dynamic traffic inspection at arbitrary locations in virtual networks. In this paper, we present the design and evaluation of Open Virtual Tap (OVT), a software-defined solution to replace hardware taps for traffic monitoring in OpenFlow virtual networks by utilizing mirroring capabilities of OpenFlow switches. The key idea behind OVT is the joint configuration of all switches in the substrate physical network in order to efficiently mirror flows from all virtual networks. We show that such a design avoids inefficiencies that result from existing software-based traffic mirroring solutions in which each virtual network configures its own switches independently of other virtual networks. We evaluate OVT using model-driven simulations as well as Mininet experiments with realistic applications for intrusion detection and video telephony analysis. Specifically, in our experiments, we observe that OVT can achieve up to 20% improvement in flow coverage compared to existing traffic mirroring approaches.

Edge computing (EC)is a promising solution to enable the next-generation delay-critical network services which are not conceivable in the traditional cloud-based architecture. EC takes the computing and storage resources closer to the end-users at the edge of the networks to eliminate the propagation delays caused by geographical distances. However, due to the lack of facilities such as cooling systems, the capacity of available resources in the edge is far less than that in the remote clouds. So, efficient utilization of the edge resources has a profound impact on the effectiveness of the edge computing paradigm. Load balancing is a key factor in achieving resource efficiency and high utilization. In this paper, we present the design of EVBLB, an efficient load balancing algorithm based on Voronoi tessellation (VT) that assigns the users' service requests to the edge servers while considering the density of edge resources in the area and the distance of the users from the assigned servers. Building on the notion of VT not only allows us to achieve these goals, but is also computable in linear time, which significantly improves the scalability and responsiveness of our proposed method as compared to existing studies. Our simulation results show that EVBLB outperforms two conventional baselines in terms of throughput, response time, task completion time, and request blocking rate.

In Mobile Edge Computing (MEC), the network's edge is equipped with computing and storage resources in order to reduce latency by minimizing communication with remote clouds. However, the available computing capacity at the edge is limited compared to that of remote clouds. A promising solution for efficient utilization of the limited capacity at the edge is fine-grained processing of user demands via Virtual Network Functions (VNFs). In this approach, user service demands are expressed as Service Function Chains (SFCs), which are composed of virtual network functions. Such service composition allows constituent VNFs to be flexibly deployed at the edge or in the cloud such that the service latency is minimized. The increasing number of users, however, challenges the scalability of system-managed SFC orchestration. To address this problem, we propose a user-managed online SFC orchestration framework at the edge of the network, called CHANGE, that minimizes service latency by jointly considering the effect of user mobility, edge capacity and service migration. We first present the theoretical foundations of CHANGE and then evaluate its performance via model-driven simulations and realistic Mininet-WiFi emulations. Our results show that CHANGE can improve latency performance by nearly 20% compared to other approaches.

With widespread deployment of virtualization technologies in datacenter networks, traditional tools used for network monitoring, such as hardware taps, become unfit. This is due to the inability of hardware solutions for dynamic deployment and virtual network monitoring. This paper presents the design and evaluation of SoftTap, a scalable alternative to hardware taps which is capable of operating over both physical and virtual switches. SoftTap is based on port and flow mirroring capabilities of commodity OpenFlow switches and is not limited to a specific network architecture or topology. A key design challenge in SoftTap is the fast computation of switch mirroring configurations in large-scale deployments. Our design is based on novel polynomial time approximation algorithms that are shown to achieve bounded approximation ratios compared to optimal solutions. We evaluate SoftTap using model-driven simulations as well as realistic Mininet experiments. Specifically, our simulations consider large networks to show the scalability of SoftTap. Mininet experiments, on the other hand, consider its real-world utility by implementing an intrusion detection system (IDS) and a VoIP metering application on top of SoftTap. In our experiments, under SoftTap, IDS achieves up to 25% higher detection recall, while VoIP metering achieves up to 23% less packet loss compared to existing mirroring-based traffic monitoring approaches.

Virtual Network Embedding (VNE) is an essential component of network virtualization technology. Prior works on VNE mainly focused on resource efficiency and did not address the scalability as a first-grade objective. Consequently, the ever-increasing demand and size render them less-practical. The few existing designs for mitigating this problem either do not extend to multi-resource settings or do not consider the physical servers and network simultaneously. In this work, we develop GraphViNE, a parallelizable VNE solution based on spatial Graph Neural Networks (GNN) that clusters the servers to guide the embedding process towards an improved runtime and performance. Our experiments using simulations show that the parallelism of GraphViNE reduces its runtime by a factor of 8. Also, GraphViNE improves the revenue-to-cost ratio by about 18%, compared to other simulated algorithms.

In network function virtualization, a service function chain (SFC) specifies a sequence of virtual network functions that user traffic has to traverse to realize a network service. The problem of SFC orchestration has been extensively studied in the literature. However, most existing works assume deterministic demands and resort to costly runtime resource reprovisioning to deal with dynamic demands. In this work, we formulate the deadline-aware co-located and geo-distributed SFC orchestration with demand uncertainty as robust optimization problems and develop exact and approximate algorithms to solve them. A key feature of our formulation is the consideration of end-to-end delay in service chains by carefully modeling load-independent propagation delay as well as load-dependent queueing and processing delays. To avoid frequent resource reprovisioning, our algorithms utilize uncertain demand knowledge to compute proactive SFC orchestrations that can withstand fluctuations in dynamic service demands. Extensive simulations are conducted to evaluate the performance of our algorithms in terms of ability to cope with demand fluctuations, scalability, and relative performance against other recent algorithms.

In content distribution networks, a key objective is the efficient utilization of the network that interconnects geographically distributed datacenters. This is a challenging problem due to vastly different characteristics and requirements of bulk and realtime transfers that share the interconnection network. Bulk transfers aim at delivering a copy of a usually large file to multiple datacenters before a deadline, while realtime transfers are absolutely delay-intolerant with unsteady and dynamic demands. In this paper, we consider the problem of multicasting deadline-critical bulk transfers in an inter-datacenter network in the presence of unknown and fluctuating demand by realtime transfers. Specifically, we develop a joint admission control and routing algorithm called PMDx, which anticipates future realtime demands and proactively reserves just the right amount of network resources in order to serve future realtime transfers without adversely affecting network utilization or bulk transfer deadlines. We show that the PMDx algorithm is a 2/δ-approximation with probability 1 - ϵ, and runs in polynomial time proportional to ln(1/ϵ)/(1 - δ)2, for 0 < δ,ϵ < 1. We also provide extensive model-driven simulation results to study the behaviour of our algorithms in real world network topologies. Our results confirm that PMDx is very close to the optimal, and improves the utilization of the network by 14% compared to a recently proposed algorithm.

In network function virtualization, network services are implemented as service function chains (SFCs). An extensive body of work exists on SFC orchestration, although a vast majority of them consider reactive algorithms that reprovision resources in response to service demand fluctuations. As such, they result in unpredictable and often significant delays that negatively affect the performance of delay-sensitive SFCs. In this paper, we consider proactive SFC orchestration and develop exact and approximate algorithms that perform well under general service demands without requiring frequent resource reprovisioning. Specifically, we first formulate SFC orchestration with deadline as a mixed integer non-linear program and show that it can be reduced to a second-order cone program, which can be solved using standard optimization software, albeit for small problem instances. We then design an approximate algorithm for large problem instances by applying iterative rounding and variable fixing techniques to the exact problem formulation. We present extensive model-driven simulation results to study the behavior of our algorithms in small and large problem instances and demonstrate their ability to achieve any desired provisioning-reprovisioning trade-off. We further compare the performance of our approximate algorithm against two recently proposed algorithms called FFCA and MaxZ.