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.

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.

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.

The decrease in price of internet access has brought clients' focus on a good internet service. Clients now demand guarantees for the bandwidth promised. We present a scheme in which clients are assured connection and bandwidth and if assured service is not provided, service providers pay penalty to them. The use of multi-SIM handheld devices such as mobiles and tablets have enabled clients to make a “choice” between multiple service providers for communication services. With competition, a client will prefer to connect to that provider who is providing the lowest price with guarantees. In this paper, we present a scenario of dynamic pricing and guarantees with penalties and providers have to decide on pricing strategies which will maximize their income. We present a solution among two service providers which achieves a Nash equilibrium with the maximizing of the expected income being the decision criterion.

The backup taken of a file system must be consistent, preserving data integrity across files in the file system. With file system sizes getting very large, and with demand for continuous access to data, backup has to be taken when the file system is active (is online). Arbitrarily taken online backup may result in an inconsistent backup copy. We propose a scheme referred to as mutual serializability to take a consistent backup of an active file system assuming that the file system supports transactions. The scheme extends the set of conflicting operations to include read-read conflicts, and it is shown that if the backup transaction is mutually serializable with every other transaction individually, a consistent backup copy is obtained. The user transactions continue to serialize within themselves using some standard concurrency control protocol such as Strict 2PL. We put our scheme into a formal framework to prove its correctness, and the formalization as well as the correctness proof are independent of the concurrency control protocol used to serialize user transactions. The scheme has been implemented and experiments show that consistent online backup is possible with reasonable overhead.

A model for storage and retrieval of relevant documents during a document production workflow in an office is presented. The objective of the workflow is to review a document by multiple reviewers, where each reviewer contributes her own comments during review based on other documents containing standing rules, precedents etc, which is termed, the context. Storage of such documents is modeled as a Page Cube and query languages analogous to relational languages have been proposed for easy and efficient retrieval.

The usual way of installing a new version of a software system is to shut down the running program and then install the new version. This necessitates a sometimes unacceptable delay during which service is denied to the users of the software. An online software replacement system replaces parts of the software while it is in execution, thus eliminating the shutdown. While a number of implementations of online version change systems have been described in the literature, little investigation has been done on its theoretical aspects. We describe a formal framework for studying online software version change. We give a general definition of validity of an online change, show that it is in general undecidable and then develop sufficient conditions for ensuring validity for a procedural language.