Analytical Model of the Buffer Memory of an OpenFlow Switch in a Software-Defined Network (SDN)

Introduction. Programmable SDN networks and the OpenFlow network device management protocol were created to improve automation of modern computer network management and support the specified quality of cloud services, that is, for tasks solved by dynamically redistributing network resources between users. One of the core elements of software-defined networks is the OpenFlow flow switch, and its most important component is the buffer memory. Using an internal software pipeline, the switch distributes and balances loads between network links. This provides the flexibility of centralized network resource management.

Quantitative performance evaluation of networks involves identifying the probabilistic and temporal characteristics of switching nodes. This is done by widely used queuing theory (QT) methods, which only approximately define and model processes in an OpenFlow switch and its buffer memory. This results in underestimated, unrealistic performance of the designed network devices, overloading the switch buffer memory, and loss of network packets. To address this challenge, a different modeling approach is proposed. This work aims to develop and evaluate an analytical model for OpenFlow switch buffer memory in SDN using advanced queueing theory approaches. For this, the discrete Laplace-Stieltjes transform (DLT) is used, taking into account the statistical characteristics of packet flows and the throughput of communication channels for a given packet loss probability. A similar mathematical model based on the classical QT is described in [1], but it does not eliminate the problems that arise due to the approximate description of network processes.

Scientific literature offers design solutions for improving data network elements, demonstrating the importance and relevance of the scientific and technical problem being solved. OpenFlow models for switches in software-defined networks (SDN) are the subject of works by Raghav S.S., Baskakov A.E., Volkov A.S., Filippov I.A., Nikishin K.I., Gurin E.I., Tikhonenko O.M., Gorbunov A.V., Lebedev A.V., Samouylov K.E.., Shalimov I.A., and others. In [2], a fairly comprehensive review of network solutions based primarily on classical QT is given. Finite-capacity systems with a recurrent input flow, a Markovian service process, and infinite-capacity buffers are studied. The modeling methods are based on replacing recurrent arrival flows with simpler ones. The dependence of the volume of requests on the service time is assumed to be given or neglected. The probability of packet loss is supposed to be negligible. Such models often assume packet loss when the buffer is fully occupied, but this assumption is not always accurate. They also assume an unlimited total memory capacity and a well-defined relationship between message volume and service time. Most publications lack finite expressions for analyzing switch service quality, taking into account the specifics of buffer memory allocation, loss indicators, and load. In these cases, the authors use numerical methods from off-the-shelf software packages.

The scientific novelty of this research lies in the improvement of classical queuing theory methods, which support the analysis of systems with arbitrarily distributed arrival and service requests. The practical significance of the results is confirmed by two factors. First, an analytical model of the buffer memory of an OpenFlow switch in an SDN network is created, allowing for a sufficiently accurate analysis. Second, it opens the possibility of selecting alternative design options at the design stage. The efficiency of the proposed model is assessed under simulation. The resulting performance metrics provide evaluating the efficiency of an OpenFlow switch in an SDN network.

Materials and Methods. The incoming SDN network packet flow enters an OpenFlow switch, which extracts metadata, checks it against entries in address tables, and determines the forwarding direction. The network operating system of the SDN controller distributes the packets into flows configured by the OpenFlow classifier. The OpenFlow switch integrates multiple flow tables managed by the central controller through instructions and packet forwarding. The SDN controller periodically updates its records of the network structure, load, resources used, and reserves. Accordingly, it establishes forwarding rules for all incoming flows, sequentially distributes them to the switch OpenFlow output ports, sets new action parameters, and performs distribution or transmission back into the network. This utilizes the switch software pipeline, which consists of sequential flow tables.

Packets not identified in the flow tables are sent to another switch port or forwarded to the controller for field modification. The SDN controller generates switch output ports, address tables, and data flow classifiers [3].

Much attention is paid to issues of network device management, and ready-made design solutions are available. Despite this, new, efficient methods and protocols for network load management are being developed, and network management protocols are constantly being refined. The short period of operational experience with SDN networks and the lack of systematic testing results for switching equipment on the OpenFlow platform necessitate further research using analytical and simulation models.

Thus, the switch structural diagram can be represented as a queueing system (QS) with limited memory. Its input receives a flow of packets with arbitrary distributions of the number and volume of requests. The operating mode of such a system will be stationary if the average number of requests arriving per unit of time does not exceed the maximum possible service rate. One of the most challenging tasks is determining the mean values and variances of the switch total buffer memory capacity, as well as the memory capacity for constructing flow tables [4]. Assume that there are no packet flow queues at the input of a high-performance central control server. In this case, the switch operation in steady-state mode can be described by the apparatus of queuing systems with Laplace-Stieltjes transforms. Data distribution and processing using a software pipeline is modeled as a multiphase random process [5].

The advanced QT method used in this paper allows for the creation of models of numerous real systems, including switching ones. It can be reasonably assumed that such systems have stationary characteristics, and that the parameters of the input packet flow do not affect the order and time of its processing. We also assume that each flow is characterized by a random number of packets, that is, its volume takes only positive discrete values, and this, with a high degree of probability, reflects the real situation.

A switch forwarding pipeline consists of one or more address tables connected in series. Input network traffic, described by an arbitrary distribution law, enters the conveyor and is sequentially processed by k address tables.

It is assumed that the query processing time for each table is random and exponential. The sum of the times of all processing stages forms the final service time distribution (the Erlang k distribution). It is known that a k-order Erlang flow with parameters (µ, r) can be represented as the sum of r random flows with parameters μ_i, and the characteristics of the system under consideration can be obtained from the characteristics of its constituent elements [6]. Then, the stationary probabilities p(i₁,…, i_r) of the system under consideration:

The structure of the switch record set is shown in Figure 1.

A simplified structure of an OpenFlow switch is shown in Figure 2.

The time intervals between packets are random. The input flow is Markovian, but its service time does not obey an exponential distribution, that is, the analyzed processing of input flows contains a Markovian component. Therefore, this system can be studied using the mathematical apparatus of semi-Markovian processes [7], and the distribution function of the time intervals of the process in state i will be an arbitrarily distributed random variable [8]. The intervals between the end of service and the next arrival of service requests are subject to the same distribution. We also assume that random packet flows, determined by the Erlang distribution function, arrive via m channels with intensities

For M/G/1/n system, the Laplace-Stieltjes transform of the distribution function of the volume of the serviced packet R(x):

Here, g_i > 0 — packet reception delay time on the i-th channel, f — distribution parameter, s — complex parameter of the Laplace-Stieltjes transform. In this expression, it functions as a multiplier in the exponent and allows finding the moments of the distribution of a random variable of any degree.

Mean value and variance:

where ρ_i — input channel loading,

Then the volume of packet flow is DLT:

Mean values and variance:

We consider that the probability of packet flow loss [9]:

where

L(x) = 1 – e^–fx — distribution function (DF) of the packet flow volume;

D(x) = p(δ < x) — DF of the total volume of packet flow δ.

DF moments R(x):

where φ₁ = 1/f — mean packet flow volume; δ₁, δ₂ — moments of the total volume of packet flow.

Finding the explicit form of the DF D(x) does not seem possible. In [10], it is shown that when performing calculations, this function can be approximated quite accurately by the expression:

Here,

 — incomplete gamma function;

p₀ — probability of no service requests; Γ(p) = γ(p, ∞) — gamma function; p and g — parameters determined from the condition of equality of the corresponding moments of the switch memory volume:

The numerical values of the DF D(x) are obtained through simulation modeling by standard numerical methods, which allow the solution to be reduced to a finite number of arithmetic operations. The results of the simulation modeling are virtually identical to the results of the analytical modeling described in this article, demonstrating the validity of the developed model.

When forming network flows, the following actions are performed [11].

1. Identification of the traffic packet flow.
2. Packet-to-flow classification for the flow being formed.
3. Formation of network packet flows or transmission of an unidentified packet to the management controller.

The function of allocating the service time for the input packet flow B(t) = p + (1 – p)(1 – e^pt), and its DLT [12]:

Mean service time:

If the system load ρ = aβ₁ = a(1 – p)/p, then the DLT service waiting time:

Then the mean value of the waiting time is:

The image has the form of rational fraction (A_n(p))/(B_n(p)). P₁, P₂,…, P_n — roots of multiplicity r₁, r₂,…, r_n, where r₁ + r₂ + ⋯ + r_n = m и

.

This means that the original can be found from formula [13]:

For simple roots of the denominator P₁, P₂,…, P_n:

The inversion of the DLT function W(q) is determined by the relation:

The distribution function of random variable V has the form:

For the case

,

mean value of stationary waiting time:

Mean value of stationary service time:

These random variables are approximated by the DF

.

Here,

,

Γ(p) = γ(p,∞), p₀ — stationary probability of no requests:

Obviously, the phases of transmission of network packets leaving the switch can be described by the graph (Fig. 3) [14].

From [15], the probability of system M/M/m/n being in the state p_k is known:

Here, ρ = λ/μ — load.

Accordingly, the probability of the state p_m+s is:

Then the intensity of the output flow is:

According to [16], taking into account lost packets, the output flow intensity:

Time spent by packets in the system:

Waiting time for packets in the queue:

Service time:

The presented expressions allow deriving the basic characteristics of an OpenFlow switch. In this case, packet flow processing and management, as well as interaction with the central network controller are taken into account. Buffer memory is considered a shared, dynamically allocated resource and is determined by constraints on the percentage of lost packets for a given loss probability. Acceptable model constraints:

• arbitrary distribution of the relationship between the volume of data flows and their service time;
• assumed discreteness of the distribution of the structure of information flows.

Research Results. Thus, as part of this study, a model of an OpenFlow switch is developed to calculate and evaluate its buffer memory. Using the mathematical apparatus of semi-Markovian processes and Laplace-Stieltjes transforms, the following parameters are defined:

• packet flow loss probability;
• their statistical characteristics;
• computing device throughput.

Packet flow processing consists of multiple independent sequential phases, and the service time across them is exponentially distributed. Therefore, the proposed model is based on a multiphase servicing procedure, in which the service time is determined by the n-th order Erlang distribution, and the moments of the distribution functions are found using the Laplace-Stieltjes transform.

Tables 1 and 2 show the results of analytical modeling of the switch buffer memory volume and the dependence of the mean service waiting time on the load. In this case, it increases from 0.1 to 0.9. Switch memory capacity is measured by the number of mean input packet flows.

The simulation results were obtained using self-similar network traffic described by a Pareto distribution with a parameter of 1.5. If the system load is less than 50%, the simulation-based characteristics for the P/G/1 system deviate slightly from the mean values obtained in the analytical modeling. At loads exceeding 50%, the values increase several-fold. The indicators increase sharply as the switch load reaches 70% and increase exponentially if this level is exceeded.

Discussion. The results of this scientific work were obtained under the condition that the distribution function of the intensity of the packet flow was independent of the phase that processed them, as well as the constant nature of the volume of the packet flow. Only in this case the result of the Laplace–Stieltjes transformation was valid for the memory size of the switch.

The main drawback of the results is that the obtained estimates are only reliable at the level of partial distributions. The OpenFlow network switch model is built on the assumption of using shared dynamically allocated buffer memory, and the considered phases of request flow processing are assumed to be independent. Therefore, the results of the study can only be used if the time is equal to:

• input of a packet flow into the switch memory;
• its output to the communication channel.

Such conditions should be considered acceptable, taking into account the capabilities of modern data processing and transmission tools.

The simulation results presented in Tables 1 and 2 are obtained taking into account the specified loss characteristics and current network load. At low loads, queues do not overflow, packets are not lost, and linear dependences are maintained. At moderate, and specifically high loads, network packet flow processing is described by nonlinear dependences. The discrepancy between the analytical and simulation results is due to the explosive nature of self-similar network traffic and the rather approximate nature of its description by the Pareto distribution.

Obviously, the feasibility of using the proposed model is determined by the current switch load. This model can be used in the design of network elements of software-defined networks to analyze their resilience to various information impacts.

The results of the presented research for a load of up to 50% are practically identical to the results obtained within the framework of classical methods of queuing theory [5]. Critical losses of input packet flows start at a switch load of 50%. A further increase in load is not considered; therefore, neither the behavior nor the stability of the system under higher loads are assessed.

The performance level of the proposed model corresponds to the known results of simulation modeling using self-similar network traffic described by the Pareto distribution.

Conclusion

1. An analytical model of the OpenFlow buffer memory of a software-defined network (SDN) switch was developed to determine:

• mean values and variance of the switch total buffer memory;
• memory volumes for constructing address flow tables.

2. Analytical expressions were obtained to determine the following characteristics of the quality of service of a software-defined network switch:

• output packet flow rate, taking into account losses;
• packet sojourn time in the system;
• packet waiting time in the queue;
• service time;
• dependence of the buffer memory size and the average service waiting time on the load.

3. The model performance was confirmed by a comparison of the results of analytical and simulation modeling when the switch load varied from 0.1 to 0.9.

4. The model allows testing SDN networks without using physical equipment to justify switch parameters taking into account its environment.

It is expected that the next article, devoted to the development of a model for the functioning of an SDN switch, will take into account the flow of requests both from the external network and from the management controller (server).