Huu-Nghi Nguyen

Thomas Begin

Anthony Busson

Isabelle Guérin Lassous

Approximating the end-to-end delay using local measurements: a preliminary study based on conditional expectation

With Software-Defined Networking (SDN), computer networks will gain a better control and management on their physical resources and on flows requiring a specific type of QoS. To fulfil these objectives, networks must be able to characterize the end-to-end performance of flows, which are usually unknown and not directly measurable. Instead, networks have typically at their disposal only local measurements, collected at each node.

In this paper, we propose a new method to evaluate the variance of the end-to-end delay based only on measurements collected on nodes. The core of our solution is to link samples of waiting times at different nodes in order to approximate the corresponding covariance terms, needed to refine the approximate value of the sought variance. We evaluate the accuracy of our solution using two different scenarios. The obtained results show that the method is generally good, with a relative error on the estimated standard deviation of the end-to-end delay usually close to 5%, though it may exceed 10% when the network is facing high levels of load and experiencing packet losses.

I. INTRODUCTION

In recent years, Software-Defined Networking (SDN) has emerged as a promising paradigm for computer networks. In SDN, the network comprise switches and controllers. SDN switches are mostly dedicated to the forwarding of packets, and to statistic computation on the conveyed traffic. On the other hand, one or several controllers are in charge of managing the network. This includes tasks such as route computations as well as more elaborated tasks (e.g., load sharing, resource allocation, QoS provisioning, admission control). Therefore, within the SDN paradigm, the control plane is centralized, and all decisions are taken by the controllers. This approach starkly differs from the classical distributed approach of the Internet. SDN networks are expected to be more flexible, manageable, and prone to efficient optimization policies than their classical IP counterparts. This new technological framework also offers the opportunity to implement services, typically QoS, using a global knowledge of the network performance.

Thus, SDN controllers will be able to make their decisions (e.g., routing, resource allocation, admission control) based on end-to-end performances of flows. This ability appears as a huge potential asset for guaranteeing an end-to-end quality of service to certain flows. However, end-to-end performance measurements are typically hard to collect. A crucial question in this context is then: is it possible to infer end-to-end performance based only on local measurements collected on the SDN switches? In this paper, we tackle this issue for the end-to-end delay. Although each SDN switch can measure the delays spent by packets kept waiting before transmission, the end-to-end delays of packets cannot be directly derived from these local measurements. Indeed, correlations occur between these local delays, and the SDN controllers must handle them properly to obtain relevant indicators of the performance: variance, or distribution of the end-to-end delay. We propose a method to estimate the variance of the end-to-end delay experienced by packets within SDN networks.

This paper is organized as follows. In the next section, we present related work and the motivation of this work. In section III, we present the considered scenario, and the notation. We also decompose the different terms involved in the variance of the end-to-end delay. Most of these terms are measurable or computable locally by the SDN switches. We show that the correlation mainly lies in the successive waiting times (time spent by a packet in a buffer). Section IV describes our proposed method to evaluate this correlation. Numerical results are shown in section V. Section VI concludes this paper.

II. PROBLEM STATEMENT AND RELATED WORK

In this paper, we focus our efforts on the one-way end-toend delay of packets. Note that this quantity differs from the round-trip delay measurement, also know as RTT [START_REF] Almes | A Round-trip Delay Metric for IPPM -RFC 2681[END_REF], [START_REF] Hedayat | A Two-Way Active Measurement Protocol (TWAMP) -RFC 5357[END_REF]. Note that the former is not simply half of the latter because network paths are known to be asymmetric [START_REF] Paxson | End-to-end routing behavior in the internet[END_REF]. Also, depending on the application or type of traffic (e.g. FTP or VoIP/Video), the relevancy of each type of delays differs.

Besides, measurement schemes may either be intrusive [START_REF] Shalunov | A One-way Active Measurement Protocol (OWAMP) -RFC 4656[END_REF] or non-intrusive [START_REF] Mark | Passive One-way Delay Measurement -RFC 2026[END_REF]. Intrusive schemes rely on probe packets to assess the latency between two arbitrary nodes of the network. Because they operate without any knowledge on the network (high level of privacy ensured), many intrusive schemes were proposed [START_REF] Gummadi | King: Estimating latency between arbitrary internet end hosts[END_REF]- [START_REF] Wang | A measurement study on the impact of routing events on end-to-end internet path performance[END_REF]. Despite considerable efforts, intrusive measurement schemes still suffer from a somewhat lack of understanding (e.g. effect of probe packet size and rate), and furthermore, the probe traffic may itself cause buffer 978-1-5090-0284-9/16/$31.00 c 2016 IEEE overflows thereby representing a bias in the outcome [START_REF] Pasztor | The packet size dependence of packet pair like methods[END_REF]- [START_REF] Johnsson | Measuring the Impact of Active Probing on TCP[END_REF].

Note that the vast majority, if not all, of existing measurement schemes (intrusive and non-intrusive altogether) heavily relies on clock synchronization between the nodes [START_REF] Moon | Measurement and Analysis of End-to-end Delay and Loss in the Internet[END_REF]- [START_REF] Wang | Survey on the End-to-End internet Delay Measurements[END_REF]. This can be viewed as a major drawback since this typically requires to equip nodes with a highly-specialized and costly GPS device.

Instead, we propose to infer the empirical distribution of the one-way end-to-end delay of packets, and a fortiori its two first moments, without any need of clock synchronization. The proposed method belongs to non-intrusive measurement schemes. It only resorts to measurements that can be collected independently by each node (e.g. packet sizes, inter-arrival times, source and destination nodes). In a previous work [START_REF] Nguyen | Towards a passive measurement-based estimator for the standard deviation of the end-to-end delay[END_REF], we introduced a method to approximate the variance of the end-to-end delay in the case of a single flow with no competing traffic. Although this work represented an important milestone, we had to significantly revise our approach to deal with the case of multiple flows. We present the corresponding extension in this paper.

III. SCENARIOS, NOTATIONS AND VARIANCE DECOMPOSITION

A. Notation

Without loss of generality, we study only the end-to-end delay of a given flow. Let f 1 denote that flow. We refer to this flow as the primary flow, and to its path along the SDN network as the primary path. The random variable P f1 describes the packet size of the primary flow f 1 .

We label the nodes of the primary path from 1 to N . Links connecting two successive nodes k and k + 1 are characterized by their transmission capacity C k,k+1 (bps), and their propagation delay R k,k+1 (msec). Each node maintains a built-in buffer which is ruled by a First-Come First-Served discipline.

In addition to the primary flow, other flows may enter and leave the path at intermediate nodes of the primary path. We denote by f k,l the flow entering the primary path at node k, and leaving it at node l after hopping through lk along the path. Note that if a flow leaves the primary path, but then returns on a subsequent node, we will consider it as two different flows. Figure 1 illustrates such an example of a primary path of 4 nodes with a primary flow f 1 that is competing with one flow that leaves and re-enters into the primary path. In our model, this flow is split into two flows.

B. Assumptions

Throughout our work, we assume that nodes can measure for each packet they process:

• the size, • the departure time (time at which a packet leaves the node based on a non-synchronized local clock), • the destination address,

• the source address,

• the waiting time (time spent in the buffer waiting for transmission). Thanks to the combination of the source and destination addresses, nodes are able to distinguish the different flows. Finally, we assume that each node k knows the propagation delay and the capacity of subsequent links on the primary path, i.e., R l,l+1 and C l,l+1 for l ≥ k.

C. End-to-end delay decomposition

The time spent by any packet of a given flow f to go through a node k can de decomposed as a sum of random variables as follows:

(i) the processing delay, which is the necessary time to handle the packet header and to commute the packet to the proper network interface of the node -it is considered as negligible (it is also close to constant and thus its variance is null); (ii) the transmission delay S f k that corresponds to the time to transmit physically the packet on the link -it depends on the packet size and the link capacity; (iii) the waiting time W f k that amounts to the time spent by the packet kept in the buffer before its transmission; (iv) the propagation delay R k,k+1 which is the time to propagate one bit from node k to node k + 1 -it is supposed constant and its variance is consequently null. It follows that the local delay for a packet of flow f 1 at node k, i.e. the time between its arrival at node k and its arrival at the next node k + 1, can be expressed as:

D f1 k = W f1 k + S f1 k + R k . (1)
Note that this local delay, D f1 k , can be measured at node k. Therefore, we can formulate the end-to-end delay of the primary flow D f1 as:

D f1 = N -1 k=1 W f1 k + S f1 k + R k . (2)
From ( 2), the mean of the end-to-end delay can be straightforwardly derived. It suffices that each node along the path sends an estimate of the mean local delay D f1 k to the SDN controller. Then, the SDN controller simply computes the sum. However, computing the variance requires a more complex algorithm as the correlations between the local delays have to be taken into account. Using the properties of the variance on (2), and noting that R k,k+1 is a constant, we obtain:

V[D f1 ] = V N -1 k=1 W f1 k + V N -1 k=1 S f1 k + 2 × 1≤k<l≤N -1 Cov(W f1 k , S f1 l ). (3)
S f1 k is a linear function of P f1 , namely

S f1 k = P f 1 C k,k+1 . It follows that V N -1 k=1 S f1
k can be easily computed given the packet size distribution. Typically, this computation can be

f 1 1 2 3 4 C 1,2 C 2,3 C 3,4 5 f 1,2 (a) Real scenario. f 1 1 2 3 4 C 1,2 C 2,3 C 3,4 f 1,2 f 3,4 (b) Modeled scenario.
Figure 1: A specific scenario where one flow leaves and re-enters into the primary path. In the realistic scenario, flows f 1,2 leaves at node 2 and re-enters at node 3. In the modeled scenario, flows f 1,2 is split into 2 flows f 1,2 and f 3,4 .

carried out on the first node of the primary path. For each incoming packet, the node computes the transmission time over each subsequent link of the primary path, and sum them up to obtain a sample of

N -1 k=1 S f1 k .
The empirical variance is then obtained from this set of samples. As for the term Cov(W f1 k , S f1 l ), it can be computed in an analogous way. Indeed, each node k measures the waiting time W f1 k , and then compute S f1 l based on the actual packet size and the link capacity C l,l+1 . By doing so, we obtain an estimation of the empirical covariance term in [START_REF] Paxson | End-to-end routing behavior in the internet[END_REF]. Therefore, only the first term in (3) is left unknown.

We expand this variance term of the waiting times as follows:

V N -1 k=1 W f1 k = N -1 k=1 V W f1 k + 2 × 1≤k<l≤N -1 Cov W f1 k , W f1 l . (4)
Note that in (4), the sum of V W f1 k can be estimated locally at each node. Thus, using (3) and (4), our issue of estimating the variance of the end-to-end delay boils down to evaluating the correlation between the waiting times:

Cov(W f1 k , W f1 l ).
We propose a technique to evaluate this quantity in the next section.

IV. ESTIMATING CORRELATIONS BETWEEN THE SUCCESSIVE WAITING TIMES

Intuitively, the correlation between waiting times of successive nodes should be more important than between nodes that are distant of several hops. Consequently, we evaluate only Cov(W f1 k , W f1 k+1 ) for 1 ≤ k ≤ N -1 and neglect the other terms. Simulation results will show that this assumption does not introduce significant errors.

The rationale of the proposed method is to allow the SDN controller to link samples of the waiting times on the two nodes k and k + 1 to estimate their covariances. This link is made through a recurrent function that can be computed/implemented on both nodes k and k + 1. This function infers the waiting time at node k + 1 from local measures at node k. Nodes k and k + 1 computes conditional expectation of their local waiting times according to this function. The controller is then able to map the conditional expectations according to the value of the recurrent function. To help the reader to understand which quantity is measured and which one is inferred, all quantities/samples that are inferred have a hat ( w for instance), and the ones that are measured by the nodes do not have it.

Our method is based on the following conditional expectation of E[W f1 k W f1 k+1 ]:

E W f1 k W f1 k+1 = E E W f1 k W f1 k+1 W f1 k+1 . (5)
To obtain an estimation of Equation 5we propose the following approach. It is possible for a node to infer the waiting time at the next node. Indeed, it can measure the departure time of the leaving packets. These times correspond to the arrival time at the next node. Let us denote p m the packet size of the m-th packet (m ≥ 1). We also consider the variable δ m k,k+1 that describes the inter-arrival time between packets m-1 and m at node k+1 inferred at node k. s m k is the transmission time of packet m at node k (it is locally measured or directly deduced from the packet length). Assuming that the server discipline is FIFO (First In-First Out), the waiting time and inter-arrival time at the next queue can be inferred through the following recurrent function:

w m k,k+1 = max{0, w m-1 k,k+1 + s m-1 k -δ m-1 k,k+1 } δ m k,k+1 = s m k + max{0, δ m-1 k,k+1 -w m-1 k,k+1 -s m-1 k }, m > 1. (6)
where w m k,k+1 is thus the waiting time of the packet m at node k + 1 inferred by node k. We denote W f1 k,k+1 the random variable which corresponds to these samples. Node k + 1 will use the same recurrent function to obtain the values inferred by node k. The corresponding random variable is denoted W f1 k+1,k+1 . Local waiting times measured on the two nodes k and k + 1 can then be mapped through the inferred values of w m k+1 . Equation 5 is then approximated as:

E E W f1 k W f1 k+1 W f1 k+1 ≈ E E W f1 k W f1 k,k+1 E W f1 k+1 W f1 k+1,k+1
.

The right hand side of Equation ( 7) is computed by the use of two histograms evaluated at node k. Node k divides the range of the computed values of W f1 k,k+1 into L disjoint intervals. The i th of these intervals is denoted ∆ i . Node k measures the waiting time of packet m, denoted w m k and uses the recurrent function given by Equation 6to obtain the corresponding sample w m k,k+1 of the inferred waiting time at the next queue (node k + 1). It obtains a set of couples (w m k , w m k,k+1 ). In order to approximate conditional expectations in Equation 7, in the interval ∆ i , we set:

E W f1 k W f1 k,k+1 (i) = 1 c i M m=1 w m k 1 l w m k,k+1 ∈∆i . ( 8
)
where c i is the number of samples w m k,k+1 lying in the interval ∆ i , and M the total number of samples.

Node k +1 is able to apply exactly the same recurrent function to infer the values of w j k,k+1 computed by node k. From the inter-arrival times (that are measured on node k + 1), it applies recurrently the first equation of the equation system 6. These samples are denoted w m k+1,k+1 : waiting time on node k + 1 of packet m inferred at node k + 1. They correspond to the previously defined random variable W f1 k+1,k+1 . These samples can be different on the one computed by node k as some packets can be lost. We set:

E W f1 k+1 W f1 k+1,k+1 (i) = 1 c i M m=1 w m k+1 1 l w m k+1,k+1 ∈∆i . ( 9
)
where c i is the number of samples w m k+1,k+1 in ∆ i , and M the total number of samples.

Our estimator of Equation 7is then given by:

E[ E[W f1 k W f1 k,k+1 ]E[W f1 k+1 W f1 k+1,k+1 ]] = L i=1 c i M E W f1 k W f1 k,k+1 (i) • E W f1 k+1 W f1 k+1,k+1 (i) (10)

V. NUMERICAL RESULTS

We now investigate the general accuracy of our proposed solution. To simulate the real behavior of a network, and thus getting the exact value for the variance of the end-toend delays, we use the discrete-event simulator NS-3 [START_REF] Henderson | Network Simulations with the ns-3 Simulator[END_REF]. This allows us to consider different network configurations (in terms of nodes, links, and buffers). The submitted traffic, namely the primary flow and the other flows, is replayed from a real trace that was collected from a campus at the university of Stuttgart (Germany) [START_REF] Sass | The dormitory network "Selfnet" of the University of Stuttgart[END_REF]. The trace contains around 44 million events, and corresponds to 4 hours of communications between 6 and 10 P.M. The packet size spreads a large range of values, from 64 to 1500 bytes.

Once the simulator has been setup and run, we compute the standard deviation of the end-to-end delay as found by our solution. The standard deviation is statistically equivalent to the variance (σ = √ V), and has the same unit as the endto-end delay (in seconds). The computation is carried out on 100 consecutive packets. We repeat 1440 replications of the same experience using various parts of the trace in order to evaluate the statistical behavior of each solution. Note that, in order to evaluate the performance of our solution, we also run an Oracle solution. This latter collects the end-to-end delays of each of the 100 probe packets, and then derives the corresponding variance using the classical variance estimator. Note that this can be easily done in the simulator since the synchronization clock inside NS-3 is no longer an issue.

In addition to the results brought by our solution, we include those delivered by a trivial technique. The trivial method simply approximates the end-to-end variance by summing together the variance of the sojourn delays (waiting and transmission) at each node along the primary path. By nature, the trivial method neglects the covariance terms.

We consider two scenarios. Our first scenario, scenario A, deals with a network composed of 4 nodes and a total of two flows. Figure 2a depicts the corresponding topology. We set the buffer at each node to a length of 15,000 bytes. The transmission capacity of the links are fixed to C 1,2 =8, C 2,3 =5, C 3,4 =3 Mbps. The primary path is shared by a secondary flow that enters at node 2 and leaves at node 3. The secondary flow sends its packets at a mean rate of 2 Mbps. As for the primary flow, f 1 , we consider three levels of sending rate, namely 0.5, 1 and 1.5 Mbps.

The results for the scenario A are presented in Figures 3a,3b,3c. It displays the cumulative distribution function of the relative error (in percents) committed by our solution and by the trivial solution. When the rate of the primary flow f 1 is set to 0.5 Mbps, Figure 3a shows that, in more than 95% of replications, our solution leads to a relative error for the variance of the end-to-end delay less than 10%. Using the trivial solution in these same conditions, only around 15% of replications have an error below 10%. Figures 3b and3c report the corresponding results when the primary flow f 1 is increased to 1 and 1.5 Mbps, respectively. Although the values slightly differ, the overall behavior of the proposed solution and the trivial remains roughly the same.

We now turn to scenario B, illustrated by Figure 2b. Here, the network comprises 6 nodes and a larger number of flows. The transmission capacities of the links are as follows: C 1,2 =6, C 2,3 =4, C 3,4 =7, C 4,5 =3, C 5,6 =5 Mbps. As for the multiple secondary flows, the secondary flows f 1,2 , f 2,4 , f 2,5 , f 3,4 , f 4,6 have sending rate of 1, 0.8, 0.2, 2 and 0.2 Mbps, respectively. Note that, under these conditions, we ensure that the incoming rate at each link remains below 70% of its capacity. Again, we consider three levels of sending rate for the primary flow, namely 0.5, 1 and 1.5 Mbps.

Figures 3d,3e, 3f show the results found for scenario B. Broadly speaking, the results are generally poorer than in scenario A. For example, with a primary flow of rate 1 Mbps, 80% (compared to 95%) of replications lead to a relative error on the variance of the end-to-end delay less than 10%. Nonetheless, the proposed solution still significantly outperforms the trivial solution. Also, we notice that as the intensity of the sending rate of f 1 increases, the accuracy of our solution decreases. We believe that stems from the

f 1 1 2 3 4 C 1,2 C 2,3 C 3,4 f 2,3 f 2,3
Bottleneck (a) Small study case with one bottleneck.

f 1 + f 1,2 1 2 3 4 5 6 C 1,2 C 2,3 C 3,4 C 4,5 C 5,6 f 1,2 f 2,4 + f 2,5 f 2,5 f 3,4 f 3,4 + f 2,4 f 4,6
Bottleneck Bottleneck (b) Bigger study case with two bottlenecks.

Figure 2: The primary flow f 1 workload is set to 0.5, 1.0 and 1.5 (Mbps). In Figure 2a, the utilization rates at the first bottleneck are 50%, 60% and 70%. In Figure 2b, the utilization rates at the first bottleneck are 37%, 50% and 63%, at the second bottleneck are 32%, 50% and 66%. increasing number of packet losses that disrupt our method. Interestingly, the trivial methods tends to enhance as the rate of f 1 grows, but stays far less accurate than the proposed solution. We believe that this improvement occurs because at higher level of loads, the queuing delays become less variable and so their correlation tends to decrease. Finally, Table I summarizes the results obtained in these two scenarios by our solution. We observe that in the many studied examples, regardless of the actual value of sending rate for f 1 , the relative errors on the estimation of the variance of the end-to-end delay remains below 10% in over 90% of the replications explored. The mean relative error of our method tends to peak when the traffic load is high (with a corresponding relative error around 10%), and in general, delivers accurate results with a mean relative error less than or close to 5% in most cases.

VI. CONCLUSION

With the development of SDN, computer networks aim at gaining a better control on the management of their resources. This may lead to cost savings and to a better handling of flows requiring a specific type of QoS. However, to fulfil these objectives, networks must be able to characterize the end-toend performance of flows. Unfortunately, computer networks are usually not equipped with tools that allow direct end-toend measurements. Instead, networks have typically at their disposal only local measurements, collected at each node. Although evaluating the mean value of a path metric is usually rather simple, things are becoming much more complex for higher-order moments.

In this paper, we propose a new method to evaluate the variance of the end-to-end delay based only on measurements collected on nodes. The core of our solution is to link samples of waiting times at different nodes in order to approximate the corresponding covariance terms, needed to refine the approximate value of the sought variance. We evaluate the accuracy of our solution using two different scenarios. The obtained results show that the method is generally good, with a relative error on the estimated standard deviation of the end-to-end delay usually close to 5%, though it may exceed 10% when the network is facing high levels of load and experiencing packet losses.

  Scenario B. Rate of f1: 0.5 Mbps. Scenario B. Rate of f1: 1.0 Mbps. Scenario B. Rate of f1: 1.5 Mbps.

Figure 3 :

 3 Figure 3: Cumulative distribution function of the relative errors for the standard deviation of the end-to-end delay for different workloads of the primary flow f 1 .

Table I :

 I Overall distribution of the relative error on the standard deviation of the end-to-end delay.

			Rate of f 1 : 0.5 Mbps			Rate of f 1 : 1 Mbps			Rate of f 1 : 1.5 Mbps
	Error	≤ 10%	≤ 20%	> 30%	Mean	≤ 10%	≤ 20%	> 30%	Mean	≤ 10%	≤ 20%	> 30%	Mean
	σ sol-scen-A	96.11	99.31	0.07	1.84	93.26	99.17	0.07	3.05	94.01	98.96	0.21	3.19
	σ sol-scen-B	93.06	99.58	0.14	3.80	79.40	97.77	0.07	6.02	63.37	93.75	0.07	8.47

ACKNOWLEDGMENT

This work is funded by the French National Research Agency ANR INFRA DISCO under the "ANR-13-INFR-013" project.