Multi-access Edge Computing (MEC) networks reduce service latency by caching services at the edge. A service request may be forwarded to the cloud for a response (Request Forwarding (R)), increasing Latency (L), and the service may be optionally downloaded, incurring a cost. If a download is in progress, the request may be buffered (a Delayed Hit (D)) if the remaining download time is less than the response time, adding to latency and previously overlooked. We argue that latency and cost must be considered separately, as the goal of MEC is to reduce latency. For the first time, we jointly consider Delayed Hits, Request Forwarding, resource constraints, download costs, and service caching, and introduce the DRL problem: minimizing Latency without assuming any request arrival pattern. We formulate this as an offline optimization problem (OPT). We propose an online algorithm called Online-DRL, derive its competitive ratio, and evaluate it using Google, SHARCNet and synthetic datasets. Compared to a simple baseline method, Online-DRL has up to 7.41% higher latency, but 92.54% lower cost, for Google traces. The results demonstrate that Online-DRL is a viable online algorithm for service caching

Network Functions (NFs) are chained to form Service Function Chains (SFCs). We consider the issue of migrating a flow from a set of NFs in an SFC instance to another. The NFs in the original chain are called the sNFs, and those in the new chain are called dNFs. Most work in the literature consider a correct migration to be one where the Flow Migration System (FMS) consisting of sNFs and dNFs, processes packets in the same order as the sNFs would have processed them in the absence of migration (property O). We argue that it is also useful to preserve the order in which packets leave the FMS in the face of migration, thereby preserving the property of External-Ordering (E). There is no existing work that preserves E. We propose an algorithm for flow migration of an SFC that preserves both O and E. It uses an NF to buffer packets instead of existing nodes, for scalability. Our experiments demonstrate that our solution causes no packet re-ordering while a solution that does not preserve E causes, in the worst case, 0.72% packets of a flow to be reordered on an average, for SFCs of length 8.

Network Functions (NFs) are responsible for ensuring security in the network, optimizing data traffic and balancing network load. NFs are chained to form Service Function Chains (SFCs). Flows may need to be migrated from a subset of NF instances (belonging to an SFC instance) to another for scaling out, scaling in, load balancing or software upgrades. When flows are migrated from an NF instance to another, states need to be migrated for the destination NF to function correctly. For the first time, we propose the correctness criteria for migration of a flow from an SFC instance to another. Existing algorithms for flow migration across NF instances require buffering packets. The amount of buffering required is not easily predictable, buffering is vulnerable to overflow attacks and do not tolerate packet bursts well. We propose an algorithm that does not require buffering or loss of packets, but causes reordering, for flow migration across SFC instances. The reordering that it causes is well managed by recent implementations of TCP, as is borne out by our experiments. Our simulations demonstrate that when a flow is migrated from an SFC instance with 2, 4, 6 and 8 NFs, the worst difference in the mean goodputs of cases with and without flow migration is only 3.6% and the best difference is 0.1%. Moreover, the implementations of NFs that are resistant to packet reordering strengthen our case.

In Multi-access Edge Computing, services are hosted at the edge of the network to reduce latency and congestion. Services comprise Network Functions which provide security and optimize the network, and signalling and data processing functions. Services are chained to constitute Service Function Chains (SFCs). For latency critical applications or when the cloud is inaccessible, we posit that all the services of an SFC must be cached at the edge. Since services may be common across SFCs and require resources, the set of services to evict when the cache is full must be chosen such that as many SFCs as possible have all their services cached. We call this the SFC Cache Replacement Problem (SFC-CRP) and argue that measuring the service hit rate is insufficient. For the first time, we define the problem, quantity how to measure whether all the services of an SFC are cached at the edge and formulate it as an optimization problem. We implement the solution and demonstrate its effectiveness over a simple LRU heuristic by evaluations using datasets which we have derived from real (Alibaba) cluster traces.

Augmented Reality (AR) and Virtual Reality (VR) games are some of the emerging use cases of 5G in the area of ultra-Reliable and Low Latency Communications (uRLLC). A multiplayer AR/VR game broadly consists of compute-intensive tasks which convert the raw data generated from sensory sources such as wearables, smartphones, etc., to action data such as location, orientation, intention, etc., and services that process the action data. Services generate a common response to all players by taking action data as input. The total response time must be as low as 20 milliseconds for a good user experience and to prevent motion sickness. While considering these aspects, the multiplayer game must be scalable, and users should be able to move. Multi-access edge computing (MEC) helps to improve performance by partially/fully offloading such tasks from mobile devices and latency-sensitive services from the cloud to a server at the edge called the MEC host. We propose, for the first time, an online mobility-aware heuristic in a Multi-access Edge Computing Network (MEN) to reduce the response time, specifically the Game Frame Time (GFT), consistently, for an improved Quality of Experience (QoE), for such games. This is done by jointly offloading tasks and placing services, and migrating both whenever required. Additionally, for improved response, the network is partitioned into regions, and a service instance is placed on a MEC host, called the Region Coordinator (RC), in each region, in a decentralized manner. When a new player joins, an old player leaves, or old players move, the number of players and their mobility patterns change in a particular region. This may require allocating or moving tasks from one MEC host to another and migrating services to a new RC. While tasks and services are migrated, the associated state and data must be moved to the destination MEC host. Our experiments demonstrate that the standard deviation for the mean GFT is 0 ms in the best case and 9.26 ms in the worst case, providing a uniform user experience, even when mobility is as high as 50% (it means 50% of the players are moving). When there is mobility, the GFT increases by 28.29% in the best case and 37.18% in the worst case, compared to a no-mobility scenario. We also demonstrate that, given computing power, there is a tradeoff between responsiveness and GFT.

Network Functions (NFs) provide security and optimization services to networks by examining and modifying packets and by collecting information. When NFs need to be scaled out to manage higher load or scaled in to conserve energy, flows need to be migrated from one instance of an NF, called the source instance, to another, called the destination instance, or from one chain of instances to another chain of instances. Before flows are migrated, the state information associated with the source instance needs to be migrated to the destination instance. Packets that arrive at the destination instance meanwhile need to be either buffered or dropped until the state information is migrated, for correct functioning of some stateful NFs, while for some others, the destination NF may continue to function. We define the properties of Loss-freedom, where the flow migration system does not drop packets, No-buffering, where it does not buffer packets, and Order-preservation, where it processes packets in the same manner as the source NF, if there was no flow migration. We formalize these properties, for the first time, and prove that it is impossible for a flow migration algorithm in stateful NFs to guarantee satisfying all three of the properties of Loss-freedom (L), Order-preservation (O) and No-buffering (N) during flow migration, even if messages or packets are not lost. We demonstrate how existing algorithms operate with regard to these properties and prove that these properties are compositional.

To make meaningful decisions about a network, network-wide and consistent measurement of the sizes of all flows is essential. Existing measurement efforts assume that the path of a flow remains the same throughout, while in practice, it changes due to load balancing, network updates etc. It is also assumed that the controller is aware of path-changes, which may not be true always due to activities confined entirely to the data plane. To approximately measure the sizes of all flows, in a path-agnostic manner, we propose that flow ids may be stored, and corresponding measurements stored in sketches, and the memory available may be split between both. Moreover, measurement sketches may be distributed across a network for efficient resource usage, on a subset of switches, called the contributing switches, such that a packet gets counted only once per path, instead of multiple times, as is currently done. When the counters of a sketch corresponding to a flow header are full, the counters in the next contributing switch in the path of the packet may begin counting the flow. We propose a switch algorithm that stores per-epoch measurements and evicts and resets them periodically and lazily. The controller adds the flow sizes estimated from individual sketches and flow identifiers of an epoch, to get the total flow sizes. We implement and evaluate the algorithm on a simulated data center network, with realistic workloads and demonstrate its feasibility.

Network elements, such as switches, network functions, or middleboxes must preserve states that they maintain on a per-flow basis, during switch updates in a software defined network. If all the packets of a flow, in both the forward and reverse directions, either use the new or the old set of rules but not a combination of both during an update, per-bidirectional-flow consistency (PBFC) is preserved. We propose a PBFC-preserving update as a general solution to solve consistency problems occurring in stateful network elements, during updates for service chaining, network virtualization, and server load balancing. In our update algorithm, ProFlow, the number of switches modified is proportional (equal) to the number of affected switches, improving efficiency. It requires no path computation, packet buffering or network function modifications and works regardless of the relative execution speeds of switches or links, or the number or type of stateful elements, at line rate. It supports wildcarded rules, unlimited concurrent disjoint updates, and practical timing asynchrony. Our prototype in P4 demonstrates that during a ProFlow update, new flows maintain their throughput while old flows undergo a marginal reduction, where the first affected switch in the flow-path has both new and old rules.

Per-packet consistency (PPC) is preserved, if during an update to a Software Defined Network (SDN), every packet either matches the new rules added or the old rules to be deleted, but not a combination of both. We propose a general update algorithm called PPCU that preserves PPC, is concurrent and provides an all-or-nothing semantics for an update, irrespective of the execution speeds of switches and links, while confining changes to only the affected switches and affected rules.