Opensample: A Low-latency, Sampling-based Measurement Platform for Software Defined Data Center

Editor's Notes

• #3: Let me start with a new concept of software defined networking (SDN) in network research area. The SDN introduces the possibility of building self-tuning networks by replacing the distributed, per-switch control planes of traditional network with a (logically) centralized control plane. And all functionalities of network control plane is moving to a centralized controller running on commodity server, and it constantly monitor network conditions and react rapidly to important events such as congestions and network failures. We will call this a control-loop consisting of measurement, decision, and control. i) gathering traffic and other measurements from the network ii) using the gathered information to compute iii) installing forwarding behaviors in the switches
• #4: So due to this decoupling between control- and data-plane in the SDN, it naturally introduces a new problem that increasing latency of a control loop in six or seven orders of magnitude greater than legacy architecture. The red values show latency of each component contributed to the SDN’s control loop, and these values are measured from our testbed. With our x86 64bits high-performance mainframe, it takes about 100 us to calculate a new routing path for a new flow in large scale topology, and takes about 10ms to install a new path configuration to a number of switches. However, in the case of measurement, it takes about from 100ms to 1second, depending on flow table sizes. Therefore, the measurement is a bottleneck point of a control loop, which is two or three orders of magnitude greater than the others.
• #5: Moreover, this control loop problem is getting worse in the case of the high speed Software Defined Data Center, running at 10/40 Gbps link speed. We believe the value of a tens of seconds for measurement is too slow to react to any, but the largest network events such as link failures, VM migrations, and bulk data movement. In other words, the problem induced by transient conditions such as conflicting small-to-medium flows cannot be identified fast enough to respond before they disappear, resulting in frequent bursts of congestion. Therefore, we need a much lower latency network monitoring mechanism.
• #6: So how fast should measurement do for practical Software-Defined Data Center? These graphs show the opposite traffic characteristics of data centers. The left hand side in this slide shows a CDF of flow duration and represents a traffic characteristic in university’s data center running web servers and file servers and so on…The right hand side in this slide shows a same result, but represents production data center that usually runs Big Data applications such as MAPREDUCE. Both are reproduced by using the datasets stated below, respectively. As you can see 80% of flows are shorter than 9~10 seconds. So a second of control loop latency is effective for traffic engineering. However, in production DC, 90% of flows are shorter than 100ms. Therefore, traffic engineering running every a second is now no longer effective at all. Further, we believe that this situation is getting worse toward high-speed data center networks such as 10/40Gbps. Therefore, ideally a measurement system for SDDC would be near-real-time, this is a latency on the order of milliseconds.
• #7: So why are state-of-the-art measurements so slow? The answer is this didn’t need to be fast traditionally. As shown in the figure, switch’s CPUs are usually wimpy, and bandwidth between ASIC and CPU are shared medium such as PCI-E meaning that it is too slow. So nowadays a new architecture of switch is introduced by adding a fast and multiple cores and directly connecting with CPU and ASIC using XAUI or AURORA interfaces. Although these new technologies could help to remedy the over taxing on switch’s CPU, but a big gap between CPUs and ASICs is still existed.
• #8: Now let’s take a look at packet sampling is a viable solution. Before answering this question, we need to know of how sampling works. Packet sampling is based on the estimation theory called maximum likelihood estimation. Roughly say that the number of packets passing through a given switch is the number of packets captured multiplied by sampling ratio. For example, suppose 1 million packets transiting in a given measurement time and sampling probability is .25%, corresponding with 1-in-400. So 2,500 packets are sampled, meanwhile, let’s consider 1000 packets are classified as class A. Then, we can roughly estimate this flow statistics as 400,000 packets of class A are in a given network.
• #9: But since the theory behind this inference is based on large number theory, the estimation has some variance regarding with the number of samples. We call this estimation accuracy which is proportional to square root of the number of samples. Therefore, it is desirable that the number of packet of class A are in avg. 400,000 with some variance. For example, in the range between 381,000 and 419,000.
• #10: So how many samples really we can get from switch. To figure it out, we was carrying out a micro benchmark with IBM RackSwitch G8264. We generate a single TCP connection at 10Gbps with TCP perf to saturate a switch’s port, then measures how many samples are arrived every second at a collector. Here is a result as we increase a sampling ratio from 1-in-10,000 to 1-in-250, which is maximum sampling ratio we can manipulate. As you can confirm that only avg. 350 packets are arrived every second at around 1-in-1,000. This is due to the same reason we previously explained, wimpy CPU and low bandwidth between CPUs and ASICs.
• #11: Do you think this value is really useful to estimate flow statistics? No. The situation is getting worse when we consider a real traffic patterns. In average, only 60 flows and in that 3000 packets are arrived at each TOR switch in any 100ms time window. This means the avg. flow has 50 packets in a 100ms window. Even if all 50 packets from a given flow are sampled, we can only estimate the flow’s actual rate with approximately 30% error.
• #12: Well, there are two approaches to gather more samples that are… Increasing sampling probability or increasing an measurement interval, but they all violate an OpenSample’s design goal of low-latency and low-cost.
• #13: Therefore, we think differently and finally we propose a protocol-aware flow statistics detection algorithm in OpenSample. OpenSample exploits the fact that 99% of total traffic in data centers are TCP flows, so if we can get two distinct packet headers of a given flow having a timestamp and a TCP sequence number, we can easily and exactly calculate a flow statistics.
• #14: Let me give you a simple example of extracting flow statistics. Consider a packet of flow S is arrived at timestamp1, and at timestamp2 a T1’s packet is arrived, and at timestamp3 a second packet of flow S is arrived. At this point we can extract a throughput of flow S from this equation. A throughput of Flow T is analogous. Further, this algorithm can be thought of being as streaming algorithm instead of batch algorithm like maximum likelihood estimation.
• #15: Now let’s look at how we estimate port utilization. For this, we just use maximum likelihood estimation that regards all packets passing through a specific port as super flow in measurement interval. So port utilization can be calculated as # of samples multiplied by sampling rate.
• #17: Now we analyze our algorithm in terms of probability of flow statistics detection. To determine this, we develop an analytical model of the probability of getting at least two different samples from a single switch. Moreover, we also use a simple simulator to validate this model. For analytical simplicity, we assume packet arrival process follows Poisson process. Since there is no risk of sampling the same packet twice at a single switch, the probability of getting two samples from the same flow at the same switch is the probability of getting two more samples from the same flow. More formally…
• #18: When considering the case of more than one switch, the analysis becomes more complex because it must account for the possibility of sampling the same packet twice at two different switches. However, for realistic numbers of switches k, and probability of packet sampled, p, the probability of sampling the same packet more than once at different switches is too low enough that it effectively acts as the one switch model with a probability of packet sampled of kp, called effective sampling probability.
• #19: This figure shows the results of both an analytical model (line) and a simulation (dot) as varying number of switches and sampling ratio. As can be seen, the intuitive approximation of multiple switches model to the one switch model is well matched. Further, you can see that 80% of small flows can be detected with practical parameters of sampling ratio and the number of switches. Also this shows that even for low sampling ratio, increasing the number of switches drastically improves the probability that we will get two distinct samples with low-cost. Meanwhile, the lines with half the sampling ratio, but twice the switches closely follow each other. For example, one switch with 1 in 5000 sampling produces the same result as two switches with 1 in 10000 sampling.
• #20: Now let’s see the analysis of the algorithm in terms of detection delay getting two samples in a given flow. Since we assume that packet arrival process follows Poisson process, the random variable D, delaying to acquire two samples from a given flow follows the sum of two random variables X1 and X2, which represent the arrival time of the first and second sampled packets, respectively. And the two random variables follow exponential distribution. Therefore, the result is the sum of inter-arrival time of first and second sampled packets.
• #21: Here is the graph showing the results of flow detection delay with the parameter k=3 which is a typical 3-hop path in data center and for packet inter-arrival times of 1000us and 10 us representing slow (12Mbps) and fast (1.2Gbps) flows, assuming 1K packets. As can be seen, we easily detect all fast flows in less than 100ms even with sampling ratio of 1 in 1000 in high speed network (the yellow line).
• #22: Now, in order to evaluate our OpenSample measurement platform, we implement it which is java-based collector with Netty NIO framework and implement sFlow v5.0 standard. The OpenSample collector reconstruct flow and port statistics using XXX and XXX, repectively. Further, we use Floodlight SDN controller and implement a centralized flow scheduler using Greedy algorithm and Linear programming. But mostly we use greedy algorithm because it is much practical for moderate network sizes.
• #23: And we use Mininet V2.0 to carry out some benchmarks because it has an advantage that our implementation can be used for real physical testbed also. Further, since Mininet is a SDN emulator running in a single host and makes virtual network that real traffic flows, the results produced in the emulator can be easily reproducible in real-testbed.
• #24: We use a three-level k=4 FatTree as a network topology to emulate a data center network having 10 Mbps link speed, but a real network would use a much larger switch radix such as k=64 having 10 Gbps. Well, although there is 1000 times discrepancy between the emulated environment and physical one due to the limitation of the resources in a single host, because Mininet uses Linux traffic shaping to emulate fixed-speed links, giving the emulated network realistic congestion and queuing delays, the same results can be seen in real physical testbed by scaling up the configuration. We run the workloads on an emulated single large non-blocking switch to determine the maximum throughput when constrained only by host NIC speeds that shows optimum performance on the FatTree, because a non-blocking is a graphically identical to FatTree. In order to carry out the benchmarks between them, we implement three flow schedulers such as…
• #25: This figure shows the throughput of a variety of workloads on our emulated configuration. Although a FatTtree is topologically a rearrangeable non-blocking topology, there is a significant gap between naïve ECMP forwarding and the hypothetical single non-blocking switch (orange bar) due to collisions where multiple flows are hashed onto the same link. This gap makes the case for traffic engineering with perfect flow scheduling it should be possible to approach the throughput of a non-blocking switch. Further, except ECMP, all other measurement mechanism shows good performance for a flow scheduler because elephant flows are prevailed.
• #26: However, the situation is changed when short flows are prevailed, which are less than a second. The most of flows are almost always finished before the controller can detect them, then reschedule them. In this scenario, OpenSample-TCP performs significantly better than either polling or MLE, because it detects and schedules elephant flows earlier. In most cases it achieves performance close to a non-blocking switch. Often it outperforms the alternatives by 25-50%.
• #27: This figure provides deeper insight into the behavior of the measurement systems in the context of traffic engineering. The left hand side in this slide shows the fraction of bytes left in a flow at the time it is detected by each measurement system. And the right hand side in this slide shows the fraction of bytes left in a flow at the time it is actually rerouted, this is after the new forwarding rules have been installed. The results show that MLE and OpenSample-TCP dramatically outperform Polling when it comes to detecting short flows. When accounting for the scheduling interval, the time needed to compute routes and install the new routes, the advantage of MLE had vanished, but OpenSample-TCP is still able to significantly outperform the alternatives. In conclusion, OpenSample-TCP can detect elephant flows far earlier than the alternatives and, when used to drive traffic engineering, it enables the traffic engineering mechanism to schedule up to 60% of the bytes that hosts send and to a 150% improvement in aggregate throughput when most flow sizes are small.
• #28: This table gives an intuition of the source of the performance gains. It shows both the total bytes transferred in the 30s duration of the experiment and the percentage of those bytes that the traffic engineeering manages to schedule. The fraction of bytes scheduled can be considered a figure of merit for traffic engineering, since any bytes that are no scheduled are more likely to be subject to congestions. By this metric, OpenSample-TCP schedules over twice the fraction of bytes as the polling system. Moreover, we can see that the reduced congestion allowed the workload to send twice as much data in the same time, resulting in doubling throughput.
• #31: In today’s talk, we present OpenSample that is a low-latency, sampling-based network measurement platform for SDDC. Targeted at building faster control loop as fast as 100 ms, instead of a 1-5 seconds control loop of state-of-the-art monitoring mechanisms. From this improvement, performance of a flow scheduler can be improved up to 150% over one running on both ECMP and a polling-based solution even with short flows. Further, it is deployable right away without a new hardware or modifying end-host’s kernel stack, because the algorithm we used does not incur any modification in hardware.