On offloading control plane applications to the data plane

ONOFFLOADING CONTROL PLANE APPLICATIONS TO THE DATA PLANE A Master’s Thesis Submitted to the Faculty of the Escola T` ecnica Superior d’Enginyeria de Telecomunicaci´ o de Barcelona Universitat Polit` ecnica de Catalunya presented by Albert Gran Alcoz In partial fulfilment of the requirements for the degree of Master in Telecommunications Engineering accepted on the recommendation of Prof. Dr. Laurent Vanbever Prof. Dr. Jos´ e Antonio L´ azaro Eidgen ¨ ossische Technische Hochschule Z¨ urich Networked Systems Group, 2018 On offloading control plane applications to the data plane, © 2018 To my parents Abstract Scheduling is one of the main active players in the quest for programmable networks. Despite the numerous research efforts that have been dedicated in latest years, not a single scheduling framework has resulted to be powerful enough to outperform the rest in a wide variety of scenarios. A new perspective to the problem has been therefore recently brought up, which suggests abandoning the pursue of a global scheduling solution, and moving into a more flexible and programmable conception. Network equipment should be designed to support different algorithms, from which it could select and configure the most appropriate one at each moment to face the instantaneous requirements of the dynamic nature in traffic demands. With the idea of making scheduling more programmable, new abstractions have been already defined, based on decoupling the process in two steps: a programmable-pipeline determining the order in which packets should be transmitted, and a fixed-logic push-in first-out (PIFO) queue draining packets in the desired arrangement. While PIFO abstraction is innovative and deeply promising, its hardware implementation is not straightforward. To the intrinsic difficulties of such a complex queuing design, adds the fact that ASIC production is by definition a multi-year process, propelling the release of a hardware built-in PIFO too far from expectations. Aiming to fill this temporal problem, in this thesis, a novel approach is proposed. Would it be possible to achieve a PIFO-behavior with the current resources available in nowadays networks? By trying to answer this question, we will embark in a journey that will span from revising the first quality of service proposals introduced at early networks, to discussions on how to reach predictability in potential future generations. Altogether, with the focus centered on squeezing the maximum benefit from the recent advances in network programmability, with special emphasis in the latest proceedings for programmable forwarding data planes. Acknowledgments First and foremost, I would like to express my deepest thanks to Professor Laurent Vanbever, for having given me the opportunity to be part of the Networked Systems Group during these months. For having believed in me since the very first day, and for all the time devoted, inspiring advice and endless support throughout all the project. You have been a reference for me, and working with you during these months has been a pleasure and an immense privilege. I would also like to thank Professor José Antonio Lázaro, for having been always there and for all the efforts in trying to make this stay possible. To the NSG fellows. Thank you Edgar, for all the insights, discussions and late-night talks. To Thomas, for the wise words and reflections towards my professional career, for all the holycows and uni-mensas; to Rudi, for the permanent good humor and positive vibes; and to Roland, Maria, Tobias and Ahmed, for having opened all the doors to me. I have always felt as one more in the family, and I will be forever grateful. To the best office-mates, Max, Andrea, Amine, Ferdinand, Alex and Markus. All those hours locked in the lab would not have been the same without your company. Thanks for sharing this experience with me. Let’s keep pushing. I would also like to thank everyone who has brought this experience far beyond the academic world. Sergi Caelles, for being my big brother during these months. Vas ser tu el que em va fer conèixer l’ETH, el que m’ha guiat professionalment. M’has ajudat a re-encendre la flama de voler seguir aprenent cada dia, apuntar el més amunt possible i escollir sempre el millor camí. Estic orgullós de tenir-te com a amic. Pablo, Yash, Yashveen, John, Guus, Daniel, Jay, thanks for being the best roommates I could have never asked for. Thanks to all my friends and family back home, for the continuous care and best wishes. And finally, to the two most important people in my life, my parents, tot el que sóc avui és gràcies a vosaltres, no em cansaré mai de dir-vos que, no hi ha paraules que expressin tot el que us estimo. Aquesta tesis és per vosaltres. Contents 1 Introduction 1 2 What About Predictable Networks? 3 2.1 Introduction ........................................ 3 2.2 Evolution of scheduling algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3 Our Algorithm 15 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.2 On strict priority PIFO’s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.3 What is a good strategy and what makes it good? . . . . . . . . . . . . . . . . . . . 18 3.4 Design of a dynamic allocation algorithm . . . . . . . . . . . . . . . . . . . . . . . 22 3.5 Proposed solution and why it works . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.6 Pros, cons and discussions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.7 Wrap-up ........................................... 29 4 Experiments and Results 31 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.2 Setting ranks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 4.3 Single-hop algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 4.3.1 First Come - First Served . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 4.3.2 Strict Priority ................................... 34 4.3.3 Shortest Flow First: Minimizing average flow completion times (FCT) . 39 4.3.4 Weighted Fair Queuing: Achieving short and long term fairness . . . . . 43 4.4 Multi-hop algorithms ................................... 51 4.4.1 FIFO+: Reducing tail packet delays . . . . . . . . . . . . . . . . . . . . . . 51 4.4.2 Least Slack Time First: Optimizing deadlines from the end-host . . . . . 56 4.5 Limitations and constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 4.6 Implementation in real networks: Barefoot Tofino . . . . . . . . . . . . . . . . . . 60 4.7 SP-PIFO for predictable networks. Next steps and open challenges . . . . . . . . 61 5 Conclusions and Future Work 65 Bibliography 67 6What About Predictable Networks? the requirements that the network has to prioritize above all. A clear example of such requirements can be found in voice services. For a conversation to take place, it is needed to guarantee a minimum of 30Kbps throughput (assume fore a given codec, overhead definition, and sampling rate), and a maximum of 30ms of jitter, 150ms of one-way delay and 1% of packet drops. With a lower service than that, the conversation would be not acceptable and the service would become useless. In this case, the resources allocated would be completely wasted, so satisfying the hard requirements is of crucial importance to be sure that the service will, at least, take place in a correct manner. Hard-constraints are given as detailed magnitudes. For example, a critical delay could be defined as, at most, 1ms for an urgent application, or 5ms for a more-relaxed one. Soft-requirements can be seen as just resource extensions to make the service better. Once having covered the hard basic needs, soft-requirements enhance the user experience. Those are not the biggest priority, but once all the hard requirements have been met, the network should consider how to distribute the remaining resources to satisfy application flows in a fair manner. An example of a soft-requirement for a file transfer protocol would be to maximize the throughput. It is not crucial for transferring the file to have a very high throughput, but doing it will make the transmission finish faster, which will be received with satisfaction from the end-user side. Once the basic demands have been covered, soft-requirements enter to action. They are given as maximizations: maximizing throughput, or minimizing flow completion time. With this distinction, the network task can be described as an optimization. For all flows in the network, with an origin-destination tuple clearly specified, and a set of hard and soft constraints, assuming a clearly defined and stable network topology, the objective is to minimize the difference between targeted performance and the average result finally achieved. Formally, let there be a set of flows f∈F , in which each flow is constrained by a hard performance target, ph , which can be decoupled in delay, throughput and jitter requirements {dh,th,jh} , plus some softly-desired demands ps={ds,ts,js} . The network objective is to minimize the difference between target performance and the average performance resulting from the allocation resources received, pa={da,ta,ja} , while guaranteeing that the hard-requirements are strictly satisfied. min pa ∆ps−a where: ∆ps−a=ps−pa s.t. pa>ph. (2.1) The optimization can be decoupled in three different optimizations, each concerning to one of the previously-defined requirement types. min da,ta,ja ∆ds−a,∆ts−a,∆js−a where: ∆ds−a=ds−da ∆ds−a=ts−ta ∆ds−a=js−ja s.t. da>dh ta>th ja>jh. (2.2) 2.1 Introduction 7 As a conclusion, a predictable network can be defined as a one-block system, with a clearly described input and output. –Input: *Workload (set of flows with requirements) * Topology of the network (assuming stability throughout the optimization: no link failures, no capacity variability) · Links with capacity · Switches, specifying if programmable and the set of queuing disciplines supported –Output: *Circuit building through tagging mechanism *Instantiation of queuing disciplines *Such that workload achieves QoS requirements •Centralized vs. distributed approaches : Interesting debate has recently arisen, discussing that the quality of service challenge has probably appeared due to the distributed nature of networks, in which decisions need to be taken at the local perspective of individual routers or end-hosts, loosing the sense of control over the packets experience throughout their journeys. Two type of philosophies appear: the ones thinking on a centralized solution to overcome those difficulties, and the supporters of a distributed approach, strongly moved by the recent advances in data plane programmability, specially in terms of saving-state capabilities and dynamic packet processing, who believe that recovering control in the inherited distributed nature is still possible, allowing us to keep the scalability, flexibility, and fault-tolerance advantages that have defined the way networks have been thought and brought where they are. •End-to-end solutions vs. critical switch : Another consideration is the one between the strict necessity of an end-to-end framework or a plug-an-play solution that can be effective even implemented on a single switch. It is clear that, in terms of performance, end-to-end solutions will theoretically provide more robustness and therefore better performance results. However, if the change requires replacing existing infrastructure, complex configurations or exigent user contribution, then the solution is with high probability not going to succeed. A fair reasoning is to dream about an end-to-end solution as a long term objective, but realistically focusing on a solution design to be implemented on progressive steps, and where the benefits can be realized even if it is only adopted on some of the network most critical switches. Any valid idea should be ambitious enough to work at an end-to-end level, not only taking action on every switch, but considering them all in a global manner. Again, when gathering control of the whole network, an immense range of possibilities emerge. By taking and structuring the network as one, it is possible to not only think of working with queues and schedulers in a single switch, but on carrying information between consecutive switches to perform network-wide optimizations throughout the path. This can be combined with monitoring and network telemetry to dynamically configure the best schedulers at each hop, or adopting congestion control mechanisms. Even more, routing could also contribute by determining the optimum links to use according to their capacities and utilization. Load-balancing could also enter and, with it, multi-path techniques. Dreaming big is easy, and sometimes is needed. Although the idealistic solution should be always kept in mind, any objective can only be fulfilled when sufficiently small steps are taken in a progressive manner. 8What About Predictable Networks? •Key players and techniques : Achieving predictable networks requires precise puzzling of different components. Everyone could increase the complexity as much as desired when thinking about the perfect solution. But, as considered in the previous lines, sometimes is important to focus on the principal actors taking the biggest part of the stake. Scheduling and path allocation are, without any doubt, the two big players in quality of service. In this thesis we will mainly focus on scheduling. The reason behind is the sense that path selection can depend on the scheduling algorithms supported around, and the background idea of merging route selection with dynamic configuration of programmable scheduling throughout the path. Being scheduling the crucial point towards predictable networks, our first objective is the analysis of different algorithms that have been implemented until now, to learn which are the challenges they try to solve and what are their advantages and weaknesses. These learnings will allow us to describe the best scenarios in which they can be used, which will be fundamental in the future to achieve predictable networks. At the end, not only will it be important to understand which queuing mechanisms should be used to achieve each type of quality of service, but also determining correct ways to combine them, not having to depend on a global algorithm for all situations, but designing combinations of them for maximizing performances in different scenarios. 2.2 Evolution of scheduling algorithms Scheduling just consists on determining the order in which packets should be transmitted at each switch or router throughout the network. And even being a super small piece of the whole QoS provisioning field, it has been extendedly researched since early days 1 . The first and most common algorithm is First Come First Served (FCFS) , in which the order of arrivals defines the resource allocation. All packets share the same buffer, with the packets arriving first being also the ones departing first. If the buffer gets full, new coming packets will be discarded. The main problem of FCFS is the non-guarantee of fairness between defined entities (for instance flows or users). A flow transmitting at high speed can capture an arbitrarily high fraction of the available bandwidth, or even block the transmission of other flows. A set of different FCFS queues, can work together under a Head of Line (HoL) Priority Queuing regime. A priority scheme is defined as the one in which low priority queues can only transmit when higher priority queues have finished draining all their packets. The same philosophy can be extended to separate the treatment of different types of traffic (e.g. real time and non-real time). In 1987, J. Nagle proposed Fair Queuing (FQ) [ Nag87 ], an algorithm that consisted on maintaining a separate queue for the packets coming from different instances, and serving those queues in a round-robin manner. This mechanism would prevent malicious sources to send packets at a too high throughput, which would just increase their personal queue. Although the idea of fairness was of crucial importance, the original FQ had several flaws. It did not consider that in a scenario with different packet sizes, although serving packets from different sources in a round-robin manner, big-size packets would still achieve higher throughput than smaller packets from other sources in the same round. 1 Scheduling is just one more technique, that added to buffer management, congestion control and traffic engineering, form the basis of quality of service. If scheduling by itself has been a widely studied area, with numerous contributions since early times, one can clearly note that a detailed study of the QoS approaches and techniques would demand far more time and effort than the sufficed in this document. Curious readers are encouraged to follow materials in [Zho18] for a more extended study on those matters. 2.2 Evolution of scheduling algorithms 9 Figure 2.1: Strict priority scheduling. Some other possibilities started to be explored. In Weighted Round Robin (WRR) [ Sem01 ], the technique was similar to traditional Round Robin [ HG86 ], with the main difference that each queue was given a certain weight. The way to proceed was just to normalize those weights so that they could become integers. The scheduler would then iterate in a Round Robin fashion among queues, serving as many packets as the converted-to-integer weight specified. This technique maintained max-min fairness only if the packets had the same size. In case the packets had variable size, then the weight-per-byte needed to be computed by dividing each queue weight by the average packet size of the queue and then this weightper-byte could be finally converted to integer and proceeded in the same manner (serving as many packets per queue as their normalized weights specified). However, this required the knowledge of the mean packet size per each session, as a dedicated queue per session was being assumed, making complex its implementation. To solve the challenge of needing the mean packet size in advance, Deficit Round Robin (DRR) [ SV95 ] was later proposed. The idea behind DRR was to set a counter per each queue that would track the amount of bytes sent by each flow. At each round, all counters would be set to a configured amount, defining the number of bytes that could be transmitted. Packets would be sent until this deficit was spent. Remaining packets would have to wait until the next round, when the deficit could be increased again. Those packetized versions of RR and DRR were able to achieve fairness in the long term. With the idea of providing instantaneous fairness, Fluid Flow Fair Queuing or Generalized Processor Sharing (GPS) [ PG93 ], assumed that traffic arrived in a fluid manner and the scheduler rotated the queues while serving an infinitesimal amount of information from each queue at each round. It was obviously just a theoretical hypothesis, as such a fluid model was not implementable, but it has served until today as basis for a wide range of packetized algorithms, which try to approximate this fluid fair behavior. In 1989 Shenker et al. presented Weighted Fair Queuing (WFQ) [ DKS89 ], also called Packetized- GPS (P-GPS), an improved version of FQ which simulated a hypothetical bit-by-bit round-robin fashion. The round at which the last packet of each flow would be transmitted if the bit-by-bit round-robin technique was followed, was computed per each packet in the flow. Packets were then ordered in increasing finishing-round value (or virtual finish time). Whenever a packet finished its transmission, the following one would be the one with the smallest finishing-round value. With this mechanism, they attempted to provide isolated and equitable access transmission bandwidth, preventing high rate flows from taking all the resources. Two different possibilities were allowed according to preemption. The preemptive version, in which if a new packet with smaller finishing-round value arrives while a bigger finishing-round value is being transmitted, the transmission should be stopped to give the opportunity to the new-coming one. They also presented the possibility of giving more promptness (less delay) to flows utilizing less than their fair share of bandwidth, by including a new variable when computing finishing-round values. 10 What About Predictable Networks? Figure 2.2: Finishing time computation in Weighted Fair Queuing. Weighted Fair Queuing was specially designed to allow slow-speed links to provide fair treatment to different flows of traffic. By prioritizing low-bandwidth traffic over high bandwidth one, malicious input streams could not starve other flows of link bandwidth by generating large amounts of traffic, as that would not provide the requested portion, but just harm his own transmission until the requested bandwidth was decreased. This way, WFQ forced each flow to transmit at a fair share of the available capacity. Weighted Fair Queuing was fair in the sense that its departure times, and the ones in Fluid Flow Fair Queuing remained bounded by the maximum size of the packet divided by the output link capacity. The biggest complain to this algorithm was, however, that each flow required its own queue, which would suppose numerous memory references, making them unfeasible for operating in high speed networks. Even today, this type of approximations is rarely seen implemented in core networks, as the number of flows is very large (potentially thousands) and maintaining the state information for all of them supposes a significant level of complexity. In 1990, Stochastic Fair Queuing (SFQ) [ McK90 ] was presented, as a probabilistic variant of Shenker’s algorithm to diminish its computational complexity inherent from the switch need of mapping source-destination pairs to a certain queue on a per-packet basis. In SFQ, the use of a hash function was proposed to easily map source-destination address tuples into fixed sets of queues. By periodically perturbing the hash function, the likelihood of hash collisions occurring during consecutive time intervals was substantially decreased. The general challenge remained the need of computing virtual finishing times, which required keeping track of the state for all backlogged users, posing a problem in terms of the real time computations. Further mechanisms to achieve fairness with smaller levels of complexity were therefore still required. New algorithms like Self-Clocked Fair Queuing (SCFQ), Start time fair queuing (STFQ) and Worst-case fair weighted fair queuing (WF2Q) [ Sah08 ] [ Gol94 ] presented alternative ways to make less tedious the computation of termination virtual times in WFQ. However, the price to pay was a reduction in the obtained fairness. A discussion on the main differences in their implementation details can be found in Section 4.3. Other techniques, such as resource reservation algorithms, also called reservation services, in which connections were forced to negotiate with the network resource scheduler the maximum and average throughputs at which they were allowed to transmit, and providing best-effort services to the rest of connections by using the remaining bandwidth counterparts, were also deeply discussed. With the rise of modern commercial operations, such as web services, cloud computing and storage, new challenges needed to be faced. In particular, data-centers experienced that most of their applications (financial services, social networking, recommendation systems and web search) often had very demanding latency requirements. Commonly adopted fair sharing schemes were far from optimal in terms of latency. This was mainly because latency-sensitive 2.2 Evolution of scheduling algorithms 11 flows often got queued up behind bursts of packets from large flows of coexisting workloads (like backup, replication, data mining etc.). Several protocols and algorithms were therefore presented trying to decrease the flow completion times in those scenarios, the called real-time schedulers. It is important to remark that in data centers the majority of the flows are mice (reduced sized with strict latency requirements), while only a few are elephant (throughput requirements). Traditional real-time scheduling techniques like Earliest Deadline First (EDF) , which focused on minimizing the number of missing-deadline (late) flows and Shortest Job First (SJF) , which minimized mean flow completion times, adopted priority queuing schemes to give preference to flows in terms of deadline (tighter deadline first) and flow sizes (short flows first) respectively. Their application in data centers was not completely straightforward because of the following reasons: • They were presented as centralized algorithms, which meant that they required global knowledge of flow information. • Prioritizing flows ideally would require each of the concurrent flows to have a unique priority class. Data centers could allocate thousands of flows, while modern switches only supported around 10 priority classes. • They assumed preemption, allowing newly arriving tasks with smaller deadlines to be completed before already scheduled tasks of lower priority levels. Still in the group of real-time schedulers, Shortest Remaining Processing Time (SRPT) was demonstrated to be the optimal algorithm for minimizing average FCT when scheduling over a single link. By prioritizing flows with least work remaining, it had the main advantage of achieving per-packet granularity, something that SJF had not been able to do. Its principal drawback, however, was the lack of consensus on how to optimally specify the deadline of each packet. Several recent algorithms based on SRPT, like pFabric, suggest using the received TCP acknowledgements to estimate these deadlines, and trying to make use of new programmable switches to update them as packets travel along the path. In 2011, D3 [ WBKR11 ] proposed a new technique to meet flow deadlines, in this case by following a first-come first-reserve (FCFR) basis. Every arriving flow to the switch would request a certain rate, where rate_requested is defined as f low_si ze / f low_deadline . If the rate requested was available in the output link, the switch would allocate it to the flow. D 3 results depended highly on the flow arrival order, and its performance was still far from the desired. With the idea of moving the complexity of priority scheduling to the end host, Preemptive Distributed Quick flow scheduling (PDQ) [HCG12] was presented in 2012. To avoid the problem of having a large number of flows and not enough queues to distinguish them all, it proposed adapting directly the flow transmission rates. By controlling each flow’s sending rate, PDQ regulated the traffic to retain packets from low-priority flows at senders, being able to achieve finer priority granularity with only FIFO tail-drop queues in the schedulers along the path. PDQ was presented as a distributed protocol instead of a scheduling algorithm, and was able to approximate a range of scheduling disciplines, specially designed to adapt traditional real time schedulers (EDF and SJF) to the distributed nature of data-centers. Its performance was based on letting switches explicitly communicate with end-hosts to let them know the available rate in their outputs, so that end-hosts could compute expected flow transmission times and packets could be scheduled accordingly. Although achieving great performance, it was quite a 12 What About Predictable Networks? complex protocol, which required a lot of synchronization between all parties as well as saving and exchanging a lot of information, both on switches and end-hosts. For the scheduling algorithm to work in a distributed manner, flow information needed to be exchanged via explicit feedback in the packet headers. The main idea was that a scheduling header could be added in the transport layer of each data packet, in which the end-host would send information to the switches about the flow ready to be transmitted, and the switches would return information about the available rate at which the flow could be (at most) transmitted. When a new flow needed to start communicating, the sender would send a probe (a packet with no data), with the scheduling header specifying the new flow information (size and maximum rate that the sender could achieve). The switch would then specify the achievable rate in the header, which would be received by the sender through the acknowledgement. Every time a the receiver would get a packet, it just had to copy the scheduling header received in the acknowledgement. Switches in the path monitored the incoming traffic they had in each of their queues. They would explicitly ask the sender to transmit data at a specific rate or to pause transmissions by only modifying the scheduler header. In 2013, pFabric [ AYS+13 ], suggested that all research efforts towards the latency problem in data-centers had been trying to use rate control to reduce FCT for short-flows. Some solutions had tried to do it implicitly, by keeping queues near empty through adaptive congestion controls and ECN-based feedbacks (like DCTCP [ AGM+10 ], D2TCP [ VHV12 ], and HULL [ AKE+12 ]). Although with those solutions, FCT was improved, they could not precisely determine the right flow rates. Moreover, keeping empty queues was challenging due to the bursty nature of traffic. The other solutions had tried to explicitly compute and assign rates from the network to each flow, to try to schedule them based on size or deadlines (like D 3 or PDQ). This last approach, although providing good performance, demanded too complex implementations. Believing that flow scheduling should be kept independent from rate control, pFabric proposed a simple transport design which managed to achieve near theoretically optimal FCTs. • End-hosts were required to specify a number on the header of each packet, which would represent its priority (e.g. the flow’s remaining size or the deadline). Priority would be set independently for each flow, with no need for coordination across flows or hosts. • Switches would base their scheduling by just following the priority number on the header. Buffers would be given very little size and preemption would be considered: if a packet arrived with a full buffer, the packet with less priority would be dropped. • Decoupled rate control was also simplified: flows would start transmitting at line-rate and would only decrease the rate in case of high and persistent packet loss detected. These two simple mechanisms would be sufficient for providing next-to-optimal performance. Although the idea of using packet headers in order to specify scheduling priorities was interesting, and would be incorporated a bit later in the PIFO proposal, the rank definitions that pFabric suggested were based on SRPT. They assumed transport layer knowledge when performing scheduling, fundamental to compute remaining flow time deadlines through TCP acknowledgement information. Despite the outstanding results of this configuration, SRPT deadline definition was not expected to be an easy task, as will be investigated throughout this thesis. 2.2 Evolution of scheduling algorithms 13 While the algorithms summarized in this section just suppose a very brief collection of all the alternatives presented in latest years, the amount of efforts devoted by the research community on the field, evidenced the common believe that it was possible to find a single algorithm which could perform well in all types of situations, in all different case scenarios. After pFabric, however, one big question was put on the table. Is there actually a universal packet scheduling? Is there an algorithm which outperforms all the others in all situations? A final solution, that would solve all the challenges in packet queuing and scheduling field at once? First Anirudh Sivaraman et. al. in "No Silver Bullet" [ SWSB13 ], and then Raddhika Mittal et. al. in "Universal Packet Scheduling" [ MARS15 ], suggested that there is not a single technique achieving best results in all possible cases. "No Silver Bullet" was first in stating the non-existence of a key algorithm to be used everywhere, anywhere, claiming that an election of the best scheduling candidate would strictly depend on what demands the applications running on top of the end-points would have. On a computer backup application requiring high throughput, the best way to process the packets would be completely different than the one for an interactive website demanding low page loading times. Following the same direction, "Universal Packet Scheduling" insisted that, although certain algorithms , when customized in particular manners, could be able to accurately replicate behaviors of other techniques, being the greatest Least Slack Time First (LSTF), there was not a universal packet scheduling outperforming the others in all type of situations on a strict sense. Both results enforced the need of changing the general research direction, and trying to work on making scheduling programmable. Instead of pouring efforts in the design of a single superstar algorithm, acting as a wildcard for all possible desired behaviors, the focus should be put on figuring out which technique, or combination of techniques (existing or new ones still to appear), would be the best ones to achieve the solicited specific requirements for every particular case scenario. Switches in the network would have to support a wide range of algorithms, with the flexibility enough to select the most adequate one at each moment to handle the diverse and continuously-changing application demands. Recent advances in programmable switches, make us believe in the possibility of having chips supporting multiple schemes and being able to dynamically select the appropriate ones through the programs running on top of them. Making scheduling programmable is the natural next step of nowadays networks, but until reaching that point there is still a lot of progress to be done. 3 Our Algorithm 3.1 Introduction While the latest changes in network programmability were quite promising and gave some fresh air to the networking sector, the scheduling field was not being part of this revolution. Anirudh Sivaraman et al. (MIT), thought that the reason why scheduling had not been made programmable in this new wave of arising programmable switches, was due to a lack of consensus in defining a proper abstraction, which could allow new schedulers to be defined and implemented under a common basis, serving as a reference for the research community to paddle in the same direction. In SIGCOMM ’16, they proposed a new framework, aiming to make from scheduling programmability in switches a reality [SSA+16]. They argued that, on its base, any scheduling algorithm could be decoupled in two main steps. The first, was defining the time at which each packet should be transmitted, with relation to the other packets. This is what they called ’ranking process’. In it, each packet had to be given an appropriate rank value, identifying the ideal position that the packet should occupy in the queue before being finally transmitted. Ranks could be just seen as relative positions to be occupied by new packets, with respect to the ones already enqueued at the time of the scheduling decision. The second step, once the packet ordering had been defined, was to place the packet in the queue following this rank. For that, the key player was what they defined as the Push-In First-Out queue. A PIFO queue could be described as a "data structure that allowed packets to be pushed into arbitrary locations in the queue, but only dequeued from the head". If achieving such type of queue structure was possible, then the biggest majority of packet scheduling algorithms could be implemented by just designing the appropriate ranking arrangements among them. With this new abstraction, scheduling in switches could be made completely programmable. Algorithm designers would only have to define a new ways of ranking packets according to the new requirements aimed to face. PIFO queues would do the rest, serving packets in the orders specified. As the PIFO mechanism could be shared by all algorithms, and the only variable component was the ranking definition, switches with PIFO implemented would allow scheduling programmability by just running new software in which new rankings were defined. In P4 switches, new P4 programs would be created, with scheduling algorithms tagging packets with the desired locations, so that every time a new packet arrived the intrinsic PIFO queue of the hardware could execute these policies by allocating the packets in the corresponding orders. While this proposed abstraction was really outstanding and will, for sure, suppose an inflection point in the scheduling history, Anirudh’s work kept the focus on the design of this new type of queues in hardware, pushing the vendors and silicon foundries to start working towards this new paradigm. Knowing that ASIC design is really tough, and that hardware production is usually a multi year process, it is reasonable to think that some time will need to elapse until 22 Our Algorithm Algorithm 3 Number of queues needed to achieve perfect PIFO. 1: ArrayList<Packet> packets; 2: ArrayList<Tuple> tuples; 3: /*Compute max and min position of the rank in the sequence*/ 4: for (int i=0; i<packets.size(); i++) do 5: if (!t.contains(tuples, packets.get(i).getRank())) then 6: Tuple tup = new Tuple(packets.get(i).getRank()); 7: tup.setMaxpos(i); 8: tup.setMinpos(i); 9: tuples.add(tup); 10: else 11: t.getTuple(tuples, packets.get(i).getRank()).setMaxpos(i); 12: end if 13: end for 14: Collections.sort(tuples); 15: /*Compute number of queues needed to achieve perfect PIFO according to max-min positions*/ 16: int numqueues = 1; 17: for (int i=1; i<tuples.size(); i++) do 18: if (tuples.get(i).getMinpos() < tuples.get(i-1).getMaxpos()) then 19: numqueues = numqueues + 1; 20: end if 21: end for 22: System.out.println("Result: " + numqueues + " queues are needed "); 3.4 Design of a dynamic allocation algorithm Until this point, we have only analyzed the cases which we can find when allocating packets under ’a posteriori’ criteria, checking the conflicts and scenarios once all the packets have been scheduled by analyzing the resulting output sequences. Now we will change the perspective of the problem towards a more dynamic view. This means that instead of knowing the full input sequence of packets, we will try to think in the same way the scheduler will have to, at a per packet basis. The only thing the scheduler knows is that it has received a packet with a rank. At each allocation decision, the scheduling does not have any information about future packet ranks, nor statistical distributions. We have seen that when a wider number of queues than the number of ranks is available, perfect PIFO can be easily achieved. Now, what happens when thas scenario is not possible? Which would be the ideal algorithm, under the assumption of a finite number of queues, when the number of queues is way smaller than number of possible ranks, each queue with infinite buffer length, and only knowledge of each packet rank under arrival (meaning that we don’t have any information about future packet ranks, nor statistical distributions)? One could easily think at first that the ideal algorithm would be the one allowing to modify the packets which have been already enqueued, so that in case one of the packets in queue blocks a new one which is coming, the enqueued packet could be switched to another queue and give room to the coming one. Obviously again this is not realistic, but helps us to identify once more what we will look for in our solution. 3.5 Proposed solution and why it works 23 1 2 3 4 5 6 7 8 9 10 11 12 1 10 100 1000 10000 100000 1000000 10000000 100000000 1000000000 Number of packets Number of permutations PIFO Ideal Strict Priority 1 Queue Strict Priority 2 Queues Strict Priority 3 Queues Strict Priority 4 Queues Strict Priority 5 Queues Strict Priority 6 Queues Strict Priority 7 Queues Strict Priority 8 Queues Strict Priority 9 Queues Strict Priority 10 Queues Strict Priority 11 Queue Figure 3.4: Number of permutations that each system is able to sort. As predicting traffic is not always possible and switching enqueued packets throughout queues can not be done, our designed solution is based on the paradigm of trying to minimize block probabilities. Several strategies can be followed when trying to deal with blocking events minimization. Treating all packets equally in terms of importance and just placing them in a way that the maximum number of packets can be allocated without blocking. That would be one design strategy. The other would be giving more relevance to packets with lower ranking, for instance, so that when blocking occurs, the ones receiving the worst effects are the ones with higher rankings. More complex ideas would include trying to compute, store, predict and use traffic distributions in terms of ranking, to adapt the queuing decisions following these patterns. However, this would require keeping state of the traffic statistics, and describing a mechanism to dynamically update them to the changes in the network. Although saving state is possible in current programmable switches, complex implementations are not recommendable with the state of the art technology. Those complex algorithms would probably offer a better performance. Note that we have designed this algorithm to be as simple as possible, with the eye put in making it possible to be implemented in current versions of P4 switches. As they don’t allow loops to take place, and the number of states which can be saved in a practical manner is not huge, we had a threshold between performance and feasibility in terms of implementation. Our goal was not to achieve a mathematical optimum in terms of allocation results, but to achieve an implementable version in the constrained versions of programmable switches we can have nowadays. 3.5 Proposed solution and why it works I. For each arriving packet, the ranking specified on its header is obtained. Queues are tracked bottom-up (from less priority to higher priority), observing which is the ranking level contained in the last enqueued packet from each queue. If the last packet ranking is minor or equal than current packet’s one, the packet is enqueued. Otherwise, the next queue is analyzed in the same manner and the procedure is repeated until reaching the last queue (highest priority). Packets reaching last queue will be enqueued whether their ranking is higher or lower than the one defining the queue. 24 Our Algorithm Figure 3.5: Strict Priority PIFO (SP-PIFO). a) Ranking of new packet is obtained: 3. b) Ranking of last packet in third queue is obtained: 9. c) Is 9 <= than 3? No: Jump to next queue. d) Ranking of last packet in second queue is obtained: 7. e) Is 7 <= than 3? No: Jump to next queue. As next queue is the first one, packet will be enqueued in the first queue. In this case 2 is smaller than 3, so there is no blocking. But even if there was blocking, packet would still be enqueued in that queue. II. After having understood the basic procedure now let’s move to the adaptive part, which is detecting blocking and acting to prevent repetition. For this, we need to define the concept of queue level. In the basic procedure of the algorithm, the queue level is the ranking of the packet which was enqueued last. In Figure 3.5, the highest priority queue has a level of 2 when the new packet arrives, mid-priority queue has a level of 7 and low-priority queue has a level of 9. When the new packet is enqueued, high priority queue updates its level to 3, following the rank of the newly enqueued packet. This queue level is the fundamental concept when trying to control blockings in the network and react accordingly. The key point here is to understand why blocking is happening in our algorithm and what does it mean. Then, what can we do to react and prevent it from possibly happening in future events. When starting to run the algorithm, all queues are empty, and initialized with a level of zero. Then the basic procedure takes place, with packets filling the queues and moving to the top as packets with different ranking levels come. When the queue filling reaches the first queue, there is no more space to keep expanding, and therefore ranking granularity has reached its possible end. It is in this moment when blocking can start occurring in the highest-priority queue. Blocking can be easily detected by comparing the rank of the new packet with the level of the queue. If the rank is lower than the level, blocking is going to take place. The fact of blocking happening informs us about the need for higher level of granularity in the top queue. It occurs when high rank packets are sharing the same queue as low rank packets, which would like to enjoy their assigned priority. Blocking therefore shows a problem of queue space granularity for the different rankings. And while not always happens, some times is possible to reach the desired level of granularity by re-designing the distribution of packets throughout the other queues, trying to squeeze the maximum efficiency in the distribution of rankings among available resources. To move some packet assignments to the lower queues, 3.6 Pros, cons and discussions 25 queue levels of smaller priority queues need to be decreased. This way, as packets start the procedure by checking the queues below, if they experience lower levels, there will be a higher probability that they will finish enqueued in those layers. And, as it is not only important to detect if there is blocking to react, but also to know if the blocking is big (wide difference from new rank to level), we will use the weighted inversion index to measure the blocking and react accordingly. To verify the proper performance of the designed algorithm, we have also developed a Java version to compare the obtained distributions with the theoretical ones, and see how close we are from the ideal results. As can be seen in the snippet below, the only required state to be saved in the switch is a variable queue level for each of the available priority queues. This state will be compared with the packet rank to determine the right allocation position, and after enqueuing the packet, in case blocking occurred, all the below queues will have their levels decreased an amount equivalent to the weighted inversion number of the blocking, to re-distribute weights among the queues and prevent possible blockings in future allocation decisions. Algorithm 4 Scheduling of each packet in the corresponding queue 1: for (int i=0; i<packets.size(); i++) do 2: for (int q=queueList.size()-1; q>=0; q- -) do 3: if ((queueList.get(q).getLevel()<= packets.get(i). getRank()) || (q==0)) then 4: int WIN = queueList.get(q). addPacket_and_getWIN(packets.get(i)); 5: if (WIN > 0) then 6: for (int w=queueList.size()-1; w>=q; w- -) do 7: queueList.get(w).setLevel(queueList.get(w). getLevel()-WIN); 8: end for 9: end if 10: break; 11: end if 12: end for 13: end for Example of execution 3.5.1. For a scenario with 70 packets, 5 queues and maximum rank set to 9: Random sequence of packets generated is: <- - - - {2}{2}{3}{6}{5}{1}{1}{5}{2}{3}{7}{7}{7}{3}{6}{5}{8}{2}{3}{8} - - - - Packets in queue 0: {1}{1}{2}{3}{3}{5}{2} Packets in queue 1: {5}{5}{6}{3} Packets in queue 2: {2}{2}{3}{6}{7}{7}{7}{8}{8} Output sequence when draining is performed after all allocations: {1}{1}{2}{3}{3}{5}{2}{5}{5}{6}{3}{2}{2}{3}{6}{7}{7}{7}{8}{8} Inversion number: 25 Weighted inversion number: 55 3.6 Pros, cons and discussions Self-learning and adaptiveness: As mentioned previously, one of the most important aspects of the algorithm is reacting to changes in the network. PIFO should be able to order any set of 26 Our Algorithm 123456789101112 1 10 100 1000 10000 100000 1000000 10000000 100000000 Number of packets Number of permutations PIFO Ideal Strict Priority 2 Queues Strict Priority 5 Queues Strict Priority 8 Queues Strict Priority 11 Queues SP-PIFO 2 Queues SP-PIFO 5 Queues SP-PIFO 8 Queues SP-PIFO 11 Queues Figure 3.6: Number of permutations that SP-PIFO is able to sort. ranks, allowing new arrangements to be developed and deployed on the fly. Some of them, like pFabric, will be implementable directly from end-hosts, by just introducing a new header to the packets or modifying existing fields. Others, will require coordination of switches along the path to specify the correct order, taking advantage of local information like queue depths, flow characteristics and output link capacities. There will be even some, trying to mix both praxis, with a first rank initialization at the end-host and ranking modifications throughout the path. In all cases, PIFO needs to be capable of adapting to the new ranks specified, both if they are big or small, and providing transparent progression as much as possible from the old sets to the new ones. In our proposed solution, thanks to the designed blocking reaction and the use of weighted inversion index, this changes can be detected and reacted in a fast rate. Moreover, as blocking is centralized at the highest priority queue, which is the one being drained in first place, their effect will be minimized, resulting on a seamless impact in the end-user quality of experience. Fast start for fast convergence: One of the main problems in the proposed algorithm is that, even when dealing with uniform traffic, it takes some time until converging to the most accurate queue-level distribution. Any alternative to better allocate queue levels from the very beginning, overcoming the transient time of stabilization, would require previous knowledge of the upcoming traffic to be received. As can be seen in the Example 3.5.1, the majority of inversions take place at the beginning of the execution, when queues are filling up. Although when running the algorithm in real time and draining the first packets while the queues are filling (instead of computing the whole allocation and draining at the end), this problem will vanish, we have liked to think about a possible rapid-convergence alternative. The objective is to prevent blocking from moment zero. When first packet comes, it will be placed in the middle queue. In case of working with a pair number of queues, just select one of the middle two. When the second packet comes, in case its rank is higher than the existing packet one, it will be placed in the middle queue of the queues above the one which is occupied by the first packet. In case the new rank is smaller, exactly the same but among the empty queues below. The idea is to keep the maximum space among filled queues, to give room for possible new ranks of coming packets. The price that is paid in exchange is complexity. This fast-start would need to be combined with the basic algorithm after the transient has elapsed. A highly-related discussion will be brought up in Section 4.3.2, in which we will see how resetting the queue 3.6 Pros, cons and discussions 27 levels to zero after they have finished draining all packets does not help in the performance because of the bursty nature of the traffic. Instead, keeping record of queue levels is a better option, as with high probability, the traffic distribution will not change from burst to burst, and we will prevent the scheduler from having to go through the transient queue level adaptation period again. Traffic knowledge in advance: Note that in general, any type of information that one might have about incoming traffic characteristics is positive, and can be used to achieve higher levels of personalization, and therefore accuracy, in the deployed solution. For instance, in an example with four queues, and a uniform traffic distribution among packets of eight different types of traffic, the best allocation would be just assigning in order two consecutive ranks to each of the queues. It is interesting to think about the advantages of knowing the traffic statistics in advance. Even just the maximum and minimum of the ranking levels that can be received, can suppose insights enough to improve the algorithm performance, making it focus on the particular scenario. If traffic distributions are known in advance, again, dedicated algorithms will outperform any adaptive one aiming to serve all types of scenarios. Working with traffic distributions, however, would require broad saving state capabilities, making the complexity grow if a fine granularity is willing to be achieved. In Section 4.3.3, an experiment proving how traffic knowledge can be used to improve the final performance will be showcased. In that particular case, our algorithm provides close to the optimal results, despite the intrinsic losses due to its transient adaptation time. Preventing starvation: Probably the biggest drawback we can find when working with strict priorities is queue starvation. When high priority queues happen to be continuously full as low-rank packets are received at a high rate manner, it can happen that lower queues can never start draining their packets, making them spend high amounts of time in queue, waiting for the high priority queues to finish their transmissions. When that happens, what should we do? Is that avoidable from just the ranking definition algorithm? Is this really a task for the PIFO queue? Our position in this case is first stating that starvation is a characteristic not only coming from the use of strict priority queues as a basis, but intrinsic from the PIFO definition. Whenever lower ranked packets arise, they will have preference over higher rank ones, making the last ones starve no matter how PIFO is implemented. It is true that in the case of mono-atomic rank increase, which was already underlined by the original PIFO authors for being the most characteristic one in the majority of schedulers, this starvation can be fought with the help of a virtual clock taking count of the current round and giving priority to packets having arrived before in the queues. But even in those cases, we would suggest playing with the queue rate definition capacity that P4, and most of the switches, provide. By correctly configuring the queue rates, in a manner that the highest priority queue does not occupy all the output bandwidth share, lower priority queues will still be able to drain some packets preventing cases of complete starvation. It is important to keep queues small sized and empty for the correct behavior of the algorithm. Queue depths, dropping and congestion control: Until this point, a single scenario has been analyzed in reference to the queue depth: the one in which all queues have unlimited queue length. However, in reality the buffer size is another variable to take into consideration. A whole field of research is focused on how to correctly design and configure queues, not only in terms of depth but also concerning drops and congestion prevention. Buffer management, as it is called, aims to achieve good queues, defined as those which allow temporary storage for incoming packets when the arrival of packets received exceeds the capacity of the egress link. As perfectly explained in [ NJ12 ], good queues need to be designed for accommodating 28 Our Algorithm the bursty nature of traffic and maintaining high levels of link capacity utilization. Bad queues, on the other side, are those which can never be drained and instead of dynamically filling up and draining in a natural manner, they just serve as a stopper for every packet that arrives. We will not focus on this well known buffer-bloat problem, but it will be interesting to think about which levels of congestion will be the appropriate ones to validate the performance of our schedulers, and how to generate good queues when implementing our simulations. Although we will not cover it throughout the thesis, our solution does not exempt congestion control and dropping management to take place. Algorithms like ECN and RED, could be also supported with the PIFO queues, and would be interesting to have implemented in order to achieve well-behaving queues and maximize performance results. In reference to dropping policies, we have only worked with the traditional tail-drop regime, in which each priority queue has its own depth and packets received later are just dropped. When the queues buffer-bloat, high rank packets will not only starve the lowest priority queues, but after the queue is filled, will start to be dropped. Starvation and dropping are intrinsic from the PIFO idea, whenever a pre-emptive approach is looked after, in which low rank packets will always have priority against low rank ones, even they arrive later to the queue. Any PIFO implementation will suffer, by nature, the starvation problem, and consecutive dropping problem no matter which queuing structure is being built on (even on hardware). This makes us think on the possibility of linking up ranking definition with dropping management. For instance, adjusting rank settings according to the state of the queues, so that dropping probabilities, or the effects on application traffic can be minimized. But then the question arises, is it really better to place for example the packet in a lower rank queue to avoid dropping or it is better to just drop it, so that the end-host can react to the congestion with a better retransmission. This type of dilemmas are the ones that, at the end, predictable networks will need to face. Efficient use of resources: An important strength of our algorithm is that responds efficiently to the monotonically increase of packet ranks within a flow. One of the major PIFO observations was that in most scheduling algorithms, ranks used to increase within a flow. Packets arriving later inside a same flow were allocated higher ranks than their predecessors. This can be very easily seen for example in time-based scheduling like virtual start time in STFQ. The virtual start of future packets will be obviously bigger than the one in previous packets. This intrinsic nature of the ranks is the basis of its behavior, where packets in increasing level of ranks can just be consequently allocated to the same queue, making an efficient use of the existing resources. This characteristic also serves for guaranteeing that packets will be prioritized in transmission order, preventing packet reordering at reception, and also reduces the number of elements that need to be sorted by the scheduler. A clear case for reinforcement learning: Finally, and just as a brainteaser, as it is out of the scope of this thesis, it is interesting to look at the PIFO problem from the machine learning point of view. It is compelling trying to know what would happen if we could let a neural network solve the problem for us, training the system with traffic arrivals and letting the weights be adapted according to the performance obtained after each given allocation. At the end, it can be seen as a chess game, in which each decision derives into a direct result, measurable, as a ground truth logic, to make the system learn and obtain the best allocation for the particular traffic statistical model. Of course, thinking of using machine learning for scheduling in real time would be too ambitious in terms of complexity and cost for what it is, but who knows if good strategies could be found off-line, to be applied afterwards for determined traffic models or statistical patterns. 3.7 Wrap-up 29 3.7 Wrap-up • What we have learned: –It is possible to approximate PIFO with strict priority queues. –The higher the number of queues, the better the approximation. – If the number of queues is equal to the number of rank levels, a perfect approximation can be reached. – Sometimes, depending on the particular input sequence, a tighter bound can be found in the number of queues needed for a perfect approximation. * We have defined the way this bound can be computed, and have implemented it on software. – We have described a new metric to evaluate and quantify the sortedness of a sequence: inversion number and weighted inversion number. – There are n k different possible allocation strategies to distribute n packets in k different queues. * We have implemented an exhaustive research program to compute and analyze them in terms of the two inversion metrics. • Finding the right way to distribute packets in a finite and small number of queues is not an easy task: –Players: * Number of packets (in posteriori scenario, but equivalent to difference between arrival and departure rate). *Set of possible ranks. *Number of queues. –Challenges: * Adapting to possible changes in ranking definition or variations in traffic arrivals. * Making efficient use of available resources (queues) to achieve the highest level of granularity at each moment. • Approach followed: – Minimize the number of collisions among all different rank levels, when treated equally. • First assumption: –No information about future packet ranks, nor statistical distribution. –Once a packet is enqueued, can not be switched from queue anymore. –Proposed solution: 30 Our Algorithm *All queues initialized at level zero. * Queue-levels are checked bottom-up. If queue level <= rank, packet enqueued. If analysis reaches top queue, packet enqueued. *Blocking is centralized at top queue. * To prevent future blocking, spreading down granularity a weighted inversion number amount. –Advantages: *Only need to save a single state per queue. *Simple implementation. *Adaptive to changes. *Blocking happens in highest-priority queue, minimizing effects in QoE. –Drawbacks: *Transient until some stability is reached. · Possible alternative: Fast start, aiming to use efficiently queues from beginning, try leaving maximum space between non-empty queues. More computational complexity required. –Open questions: * Is there a way to find the mathematical optimum without need for computing all the possible allocations, to compare SP-PIFO performance to the PIFO theoretical one? * Should we take care of starvation of low priority queues? Or should it be a task of transport control protocol via retransmissions with lower rank? Remember that the rank can be specified at the end-host and modified by the path switches. * In the same direction, should we play with queue size? Or is dropping and buffer management a task of the scheduling algorithm, not PIFO itself? * Should we treat better some ranks among others in terms of queue allocation? • Second assumption: – Predicting traffic is possible. Compute, store, predict and/or use traffic distribution statistics in terms of ranking can give several advantages. Main question is if traffic statistics are stable enough to be worth the amount of state-saving needed to implement such approach. Is this implementable in current hardware? * A simpler approach is to model certain traffic scenarios off-line, and try to take advantage of this knowledge a posteriori to efficiently allocate the resources. * Learning algorithms will be completely necessary when trying to mix different performance objectives under the same switching equipment. 4 Experiments and Results 4.1 Introduction After having analyzed the proposed algorithm in a theoretical manner, in this section we will tackle its practical implications. The final objective of developing an approximation for PIFO queuing behavior, is to make possible the implementation of more complex scheduling algorithms than the ones we can find intrinsically in nowadays switches. The continuously increasing demands for quality of service, evidences the need of complex algorithms defining the way packets should be treated to achieve certain objectives. In the previous chapter we have defined a way to approximate the PIFO behavior by using strict priority queues, a basic queuing style that we can find in all the switches deployed in current networks. In this chapter, we will focus on the other crucial point in the PIFO abstraction: setting ranks. We aim to verify if the designed PIFO approximation can actually be useful in practical implementations of complex scheduling strategies. A variety of scheduling algorithms have been presented since the appearance of first networks. All of them try to face different performance objectives: helping flows achieve fair bandwidth shares, minimizing packet flow completion times, reducing one-way delay tail latencies or even aiming to find a balance among combinations of them. In this chapter, we will select the most representative ones, and we will discuss how they could be adapted or translated to work under the PIFO abstraction. After implementing them in P4, we will verify if, with our solution and the appropriate rank allocation design, we are able to approximate the behavior that those algorithms were developed to provide, with a certain level of accuracy. It is very important to remark that our evaluation is completely focused on translating results that up to now have only been achievable in simulations, dedicated hardware or research testbeds, to existing networks and equipment. Following this purpose, we have decided not to use any type of software simulator like ns-2 nor queuing modifications on Linux traffic control. Software tools allow researchers to extend the functionality of real hardware equipment further than what they can really provide in real life. Although sometimes that enforces research, as allows the community to test possible future enhancements and protocol ideas, this extra flexibility and programmability that software provides, could be easily perceived as cheating, bringing us away from our initial mission. Instead, the only tools we will use are Mininet [ LHM10 ], a tool allowing the definition of realistic virtual network topologies on software to make testing easier, and the simple-switch definitions of P4 programming language, which can be run in the recently presented new generation of programmable switches. For the ease of implementation, we will focus the majority of experiments on the software virtualizations. However, in Section 4.6, we will showcase how the algorithm can perfectly be translated to hardware equipment. Not only we will provide the complete PIFO implementation for the most recent programmable silicon chip in the world, but we will also explain the main limitations that jumping to the physical world can suppose. 38 Experiments and Results Figure 4.6: SP-PIFO bandwidth allocation on progressive flow generation. Urgent-queue effect. 4.3.2.2 Hijacking the algorithm In the same way Internet provides flexibility to users around the world to virtually connect and exchange information in a diversified manner, it also offers a broad space for hackers to perform all type of malicious activities one could imagine. For this reason, any new algorithm or protocol designer should spend a non-slight amount of time to analyze possible security flaws and implications. Our case is not an exception. Specially when the logic behind is well known and understood, it is relatively easy to find manners of breaking the algorithm expected behavior or spoofing it to get higher rewards. Two types of attacks can be differentiated, based on the attacker objective. First, gathering the whole possible link rate for its own profit. Second, blocking the system to prevent flow transmissions from taking place in the output link (i.e. DDoS). With a solid knowledge of the system state at a specific moment, it is straightforward to attack the algorithm and make it allocate all the available resources to one of your transmissions. Assuming a scenario in which ranks are set from the end-host, the attacker only needs to know which is the minimum rank that non-malicious packets are allowed to specify. With this knowledge, the attacker will be able to place their packets in the highest priority queue by just advertising a rank in their packets with a level below than the regulated ones. Achieving the highest priority queue, as has been seen in the previous sub-section, does not necessarily guarantee high (or the highest in this case) transmission rates, as top queue can be shared by different flows, making them share the available output link capacity. The second step on the attack is then lowering the levels of bottom queues to prevent lower priority packets reach the top queue and enjoying this way, finally, the whole link resources for the attacker benefits. This type of attack is exemplified following the lately presented simulation, considering flow with identification number 20, an attacker. Flow 20 already has been defined with the lowest possible rank in the scenario, but as the number of flows is higher than the number of queues, and the transmissions are all at the same rate, it still has to share the output link with the rest of 4.3 Single-hop algorithms 39 Figure 4.7: SP-PIFO bandwidth allocation on progressive flow generation. Hijacking attack. the flows. To attack the system, it would just have to increase its transmission rate, for example from the default 10Mbps to 1000Mbps, to ramp up the blocking probability, and decrease this way lower priority queue levels, making higher-rank flows be directed to those bottom queues. With this strategy, the attacker is not only blocking the other flow transmissions, but is enjoying the highest possible bandwidth allocation. The main drawback of this technique, from the attacker perspective, is that the amount of traffic generated to deny the service of other flows is higher than the transmission goodput that the attacker can finally use. In other words, out of the 1000Mbps generated for the attack, only 10Mbps (the bottleneck) will be transmitted successfully to the destination, as the majority will be dropped in the switch. This same strategy can also be used as a denial of service attack, preventing non-malicious flows to travel through a selected link. When the objective is not to gather the network resources nor to deny transmissions from the switch, but just to break the logic behind traffic differentiation, a different approach can be followed. The rationale in this case is the inverse: trying to drastically increase the levels of low priority queues so that all non-malicious transmissions easily reach the top and collapse together at the highest-priority queue. As a result, one single FIFO queue is left available, breaking all the PIFO logic and making traffic differentiation impossible to be implemented. The attack execution is a bit more complex, as more than one flow transmission is required. In particular, N-1 attacking-flows are required, where N is the number of PIFO queues, each one destined to block one of the low priority queues. All flows will have assigned a rank value higher than the maximum regulated (meaning the rank scale non-malicious traffic use)rank and different from the other attacking-flows. By keeping those flows transmitting at a high rate, the attacker will minimize the effects of blocking reactions, making all non malicious traffic collide at the highest-priority queue. In this type of attack the malicious host is not obtaining any reward aside of breaking the traffic differentiation and priorization that PIFO would be providing. Although these attacks are intrinsic for the PIFO implementation, and therefore can be used for all scheduling alternatives, depending on the application running on top, more or less deeper effects can take place. 4.3.3 Shortest Flow First: Minimizing average flow completion times (FCT) There have been a number of algorithms proposing alternatives to diminish flow completion times. Shortest Remaining Processing Time (SRPT) has been proved to be optimal for minimizing average FCT when scheduling over a single link, prioritizing flows in order of remaining flow size. As the determining the deadline is not straightforward, several simplifications have been presented. The Shortest Flow First approximation, based on using the absolute flow size instead of the remaining flow size, has been shown to provide close-to-optimal results [ AYS+13 ]. 40 Experiments and Results Figure 4.8: Shortest Flow First (SFF) Flow Completion Time (FCT) and average bitrate results. In this section we will analyze if it is possible to reduce flow completion times by using these strategies under PIFO abstraction. As the pursuit is to measure flow completion times and not strict bandwidth share, we will use TCP connections. For this experiment D-ITG [ BDP12 ] will be used, a traffic generator with more customizable configurations than iperf. 15 flows will be created. But this time with two differences respect the previous simulation. Every flow will have different sizes. We define the size of the flow as the amount of data that has to be transmitted. The packet size and transmission rate will be defined by TCP. All of them will start their connections at the same time. And their rank will be set as the size of each flow, making use again of the ToS field to carry the rank information from the end-host to the switch. As in TCP transmissions ToS fields have to be multiple of 4 (the two lowest bits are reserved), the size of the flows will be set accordingly. Note that in the TCP protocol implementation, some packets are forced to be transmitted with ToS equal to 0, which has to be also considered in the PIFO implementation. hdr.ipv4.tos = flow.size; meta.rank = (bit<32>)hdr.ipv4.tos; Simulation results describe an average flow completion time in SFF is of 367.1148228667 seconds, while in FIFO remains 556.7540384 seconds. It is interesting to see the huge benefits that can be obtained by simply prioritizing small flows over big ones. The separation of big flows, also often called elephants, from small flows, often called mice, has been an objective of many areas inside the networking field. This differentiation, for instance, has been the basis of advanced circuit building and load balancing techniques, which have aimed to generate orthogonal paths for each flow type in the network (as much as possible), to improve global quality of service. The performed simulation can be taken as an illustrative example more demonstrating how important can it be to define differentiated treatment for different characteristics traffic flows. Is SFF PIFO-approximation the best rank allocation that we could achieve to minimize FCT for this particular scenario? Or, from another view, could we distribute packets from traffic flows in another manner among priority queues to achieve a lower average FCT under the same architecture? The answer to the last question is clearly yes. Being aware of the traffic being transmitted, one could adjust the allocation of traffic directly to SP queues to achieve better performances. For the particular case occupying us in this moment, if we know that we are dealing with 15 traffic flows of different sizes and we want to minimize FCT, we could avoid the transient of our algorithm by grouping consecutive traffic flows in pairs and allocating them directly to the queues in order of priority. The results of a manual mapping of flows to 4.3 Single-hop algorithms 41 Figure 4.9: Shortest Flow First (SFF) and manual allocation under traffic knowledge FCT results. strict priority queues can be seen in Figure 4.9. Taking the manual allocation as the ground truth, or the best possible reference strategy, it can be seen how our dynamic algorithm is quite close to the optimal one. The good point of our solution is that previous knowledge of the scenario or the traffic distribution is not required in advance. The algorithm adapts to changes. If the scheduling objective is suddenly switched, after a small transient time our algorithm will adapt. What we achieve in a dynamic manner without previous knowledge of the traffic can be improved when this knowledge is available. But then a different algorithm is required for each particular scenario, and that is not the challenge we are willing to solve. The improvement in the last flow is just due to the fact that it has a queue allocated for itself, so that it can gain access to the entire queue rate. 4.3.3.1 Adaptiveness One of the great points of our implementation is the ability to quickly re-adapt from a set of ranks to another. This characteristic is very powerful specially in those scenarios where ranks can be set by the end-hosts. Without need to reboot the switches on the path, a simple swap in the ranking definition will, after some transient time, result in a completely different output behavior. Imagine that a switch on a company network is carrying real-time transmission packets, with small ranks ranging from 50 to 59. In a certain moment, the company decides to use the link for a data center storage backup maintenances, with longer flows and bigger ranks, say from 10 to 90. In a normal switch with strict priority, a technician should manually remap the priority of those flows in each switch along the path. With our algorithm is just enough to start transmitting the new types of traffic with their updated ranks. Figure 4.10 depicts this adaptiveness of the PIFO approximation, in a scenario that starts from a switch reboot, with all the queue levels set to zero, to a transmission of several packets of flows ranked from 50 to 59, and finally to a rank update from the end host, which stops the previous transmission and starts sending packets of flows ranked from 10 to 90. It can be clearly seen how the algorithm adapts in a rapid manner, first changing the queue levels to the ranks of the first packets arriving after performing the swap (ranks 10, 20 and 30), and progressively, as higher-ranked packets start to come, lower priority queues adapt as well to accommodate those new entries. It is worth mentioning, that the change occurs with such rapidness, that we had to perform simulations limiting the access link at 1Mbps and the output at 0.5Mbps to be capable of capturing the evolution of different queue levels with sufficient detail. 4.3.3.2 Scalability Being this simulation the first in which a non mono-atomic increase arrival of ranks is handled, it is the right moment to pose an important question: Which is the limitation in terms of 42 Experiments and Results Figure 4.10: SP-PIFO adaptiveness performance. rank variability that the system is able to manage? It is clear that with 8 queues and 15 flows, the results obtained are quite promising. But what happens when the number of flows is not fifteen but a couple of hundreds or even thousands. Will the algorithm still provide any beneficial results? In fact, the number of flows is not what matters exactly, as having a very big number of flows sharing a small range of defined ranks is completely equivalent (from the PIFO implementation perspective) to having a single-but-very-long individual flow per each rank. The relevant parameter to take into account when considering scalability is the number of different ranks. The higher the number of ranks, the more difficult it will get for the scheduler to map them to the available strict priority queues. As has been shown in Section 3 of the thesis, the higher the number of ranks, the less-accurate the PIFO-approximation can be. Figure 4.11 depicts the result of transmitting 254 differently-ranked flows from h1 to h3. In this case we used the TTL field to mark the packets from the end-host. This is the maximum number of flows that D-ITG allows to transmit in one session. The bottleneck in this case has been switched to 80Mbps, in order to let the first packets of all flows reach the destination on time. If not, D-ITG drops the connection as soon as the source does not receive the first acknowledgement. We can see how the adaptiveness of the PIFO approximation allows the algorithm to improve the default FIFO performance with a high level of robustness. Resulting average flow completion times are 133.296 seconds for SFF versus 288.871 seconds in P4-FIFO. The intuition behind is that small flows will always go to the higher queues, no matter how many bigger flows are competing as well. As soon as short flows finish transmitting, bigger flows will move to higher priority queues, and progressively all flows will go from bottom queues to the top ones in order of rank. Finally, as more flows finish sending data, even the bigger ones will be able to reach the top, completing their transmissions as well. Again, this shows that scalability is not an issue for our implementation. As mentioned before, the main Achilles heel of the proposed algorithm is the starvation of higher rank flows while a huge amount of small flows want to transmit as well. In this same scenario, if small flows were transmitting in a continuous manner (assume infinite flow size), bigger flows would never reach the top, and their services would be completely denied. 4.3.3.3 Traffic distributions The last experiment of SFF consists on analyzing how the algorithm reacts to different type of traffic loads. With the fix number of 15 flows, we will change their characteristics in the following manner. Let’s define small flows as those ranging from 400 to 6000KBytes. And big 4.3 Single-hop algorithms 43 Figure 4.11: SP-PIFO scalability performance. Figure 4.12: SFF vs. P4-FIFO Average Flow Completion Time difference under progressively increasing percentage of small flows. flows from 20000KBytes to 25200KBytes, following the limitations of D-ITG and ToS field for rank specification. The first simulation will consist on a small flow and 14 big ones, with final flow sizes of {400, 20000, 20400, 20800, 21200, 21600, ..., 25200}. In the second simulation, we will remove the biggest one, to add the following smallest one: {400, 800, 20000, 20400, 20800, 21200, 21600, ..., 24800} and we will proceed in the same manner until the final simulation, which will have flows sized as {400, 800, 1200, 1600, ..., 6000}. We can see how SFF outperforms P4 Intrinsic FIFO for all workloads, making a special difference as traffic load gets bigger. This makes our result to be in complete consonance with [OS15]. 4.3.4 Weighted Fair Queuing: Achieving short and long term fairness Fairness is probably one of the most-wanted objectives when performing scheduling. Usually is considered under the max-min fairness criteria, defining a fair allocation as one in which no flow can get better treatment without hurting the performance of another flow with a lower level of service. In a more formal definition, it can be stated that "an allocation is fair if (1) no user receives more than its request, (2) no other allocation scheme satisfying condition 1 has a higher minimum allocation, and (3) condition 2 remains recursively true as we remove the minimal user and reduce the total resource accordingly" [Bal16]. As has been reviewed in previous sections, obtaining an allocation that satisfies max-min fairness among packets of different flows is not an easy task. Various techniques have been proposed over the years, each with specific implementation details. 44 Experiments and Results •Round Robin [ HG86 ]: This approach provides max-min fairness only for scenarios with fixed packet lengths. Ideally, it requires an individual queue per flow, from which the scheduler can drain packets at a one-packet-per-queue basis, iterating over the queues in a sequential manner. With this idea, a packet from each backlogged queue is drained at each round, allocating fair bandwidth shares to each contending flow. As having a physical queue per each flow is not realistic in practice, it is a common idea to map traffic flows into different classes. With each class having a dedicated queue, Round Robin scheduler just scans class queues in order, serving one packet from each nonempty queue at each round. With this solution, max-min fairness and protection is achieved among classes. More advanced proposals suggest replacing physical queues by state-saving on the switch. Virtual queues are generated by keeping track of some metrics like the virtual time and the instantaneous round number. For a very basic Round Robin implementation on P4, based on our PIFO approximation and the virtual queues methodology, it is enough to define counters tracking the number of packets sent by each flow. Flows with lower number of packets transmitted will have lower ranks, and therefore priority over flows with very steady connections. This first approach works for fixed packet length scenarios in which all flow transmissions start at the same time. However, real traffic usually operates by bursts, with some empty intervals between consecutive transmissions. In this case, the most common technique is to keep track of the round number. When new connections take place, instead of starting their packet counter from zero, they start from the current round number, preventing them from having complete priority over existing connections. Round Robin is still the root of a great majority of scheduling algorithms aiming to provide fairness. Most of their successors still keep the idea of per-flow virtual queues, trying to emulate the original Round Robin procedure, and keep track of the virtual round value to accommodate the bursty nature of traffic streams. •Weighted Round Robin and Variable-length Round Robin [ Sem01 ]: Traditional Round Robin is unfair if different flows or classes are given distinct weights. Assume the case in which 5 different classes are sharing the output link resources in a Round Robin manner, but we want the scheduler to allocate twice the fair proportion of resources to the first class, keeping the rest with the original distribution. Weighted Round Robin considers this scenario by modifying the basic Round Robin at the time of updating packet counters. Updating all class counters in steps of 2, except the first class counter, updated 1 by 1, the number of resources allocated to first class are directly doubled from the rest. Traditional Round Robin is also unfair if packets have different lengths. In this case, draining one packet per queue can mean allocating different number of resources to each class or flow. The appropriate modification for those scenarios in this case is increasing the counter not by one unit each time a packet is sent, but by the actual length of the packet. All those modifications are just updates from the original Round Robin scheduling algorithm, and they provide backwards compatibility (i.e. Variable-Length Weighted Round Robin will just work as a simple Round Robin if only fixed-length packets with same weight are considered). •Generalized Processor Sharing [ PG93 ]: This new branch of research proposed studying the opportunities of Round Robin from another perspective. They stated that ideal fairness could be found if an infinitesimal amount of data could be served from each flow queue at each round. As that is not implementable, they proposed different approximations to that model, usually referenced as Fluid Flow Fair Queuing or just Fluid Round Robin. When the infinitesimal amount is translated to 1 bit, then we have the bit-by-bit 4.3 Single-hop algorithms 45 Round Robin. Although none of those algorithms are realizable in practice, they serve as a theoretical basis for the upcoming (those yes implementable) approximations. •Weighted Fair Queuing [ DKS89 ]: The biggest and most famous GPS approximation, also known as packetized GPS or packet-by-packet GPS, suggests computing the finishing transmission time of packets as if they were transmitted through the bit-by-bit fluid model, and scheduling them in order of increasing finishing times. To do it, the notion of round number and finishing time are used. The round number (also called virtual time) is the number of virtual rounds completed under the fluid model, assuming that each round a bit is served from an active connection. Finish time is the round number at which a packet would finish transmission if it was transmitted with the bit-by-bit model. The idea is keeping track of those virtual variables (round and finishing time), and scheduling packets in order of finishing times. For the simple case in which flow virtual queues are continuously backlogged, the finish time of a packet k from flow i is equal to the finish time of the previous packet from the same flow, plus the transmission time of the current packet under the bit-by-bit basis. Fk i=Fk−1 i+ Lk i φi (4.1) For a more complex case considering that flows are not constantly transmitting, but can be idle for some time, finishing time can be accurately computed with the help of the round number. In case the queue is backlogged, the finishing time will be selected as in 4.1. Otherwise, the round number will be taken as the start transmission time: Fk i=max(Fk−1 i,R(t))+ Lk i φi (4.2) Although, on paper, weighted fair queuing is the most accurate algorithm for achieving max-min fairness, a precise computation of the round numbers is highly complex. Several variants have appeared making implementation details a bit easier. •Self Clocked Fair Queuing and Start Time Fair Queuing [ Sah08 ] [ Gol94 ]: In SCFQ, the round number is approximated to the finishing time of the last packet being served. By just updating the round number every time a new packet is scheduled, finishing time can be easily computed. The price to pay is an increase worst case delay. Fk i=max(Fk−1 i,CF)+ Lk i φi (4.3) Start time fair queuing aims to be more precise by working with both, start time and finishing time. The start time of a packet arriving into an inactive connection is the round number at the time the packet enters the switch. If it arrives into an active connection, meaning some previous packets are already in the queue waiting to be transmitted, then the start time is the finishing time of the previous packet. Packets are scheduled in order of start time and the round number is updated as the start time of the last packet being served. Other options like W F2Q aim to reduce the WFQ burstiness derived from the fact that flows need to wait for other flows to transmit before having consecutive access to the channel. And they do it by selecting at each scheduling decision packets only from the ones which would have started transmitting under the fluid model, instead of having to select among all available packets. 46 Experiments and Results To analyze how fairness can be implemented on our PIFO abstraction, we will focus on STFQ algorithm, for being the most accurate WFQ approximation. As can be seen, it is the first case in which the ranking definition needs to be configured from the switch itself, as local information is required, like the virtual time, and contributions from different flows need to be taken into account. Bandwidth share distributions will be evaluated, when various UDP transmissions are started demanding different rates. Obtained results for the main scenarios are depicted in Figure 4.13. In the first example, the sum of bandwidth demands is below the capacity and therefore all requirements are met. In the second example the capacity is exceeded with requirements of { 0 . 5 , 2 , 4 } Mbps. How should a max-min fair algorithm allocate bandwidth to the links? According to the max-min criteria: 5/3 = 1 . 66 would represent a bandwidth distribution of { 1 . 66 , 1 . 66 , 1 . 66 } Mbps to each flow. As 1 . 66 overfeeds the demands of flow 1, which only needs 0.5, the excess 1 . 66 − 0 . 5 = 1 . 16 is divided among the other remaining flows, 1 . 16/2 = 0 . 58, obtaining a distribution of { 0 . 5 , 2 . 24 , 2 . 24 } Mbps. But the second flow only needs 2. So we have an excess of 0.24, which will go to the third flow, being the final max-min fair distribution: { 0 . 5 , 2 , 2 . 48 } Mbps respectively, which is exactly what we obtain with our algorithm. But now let’s move to the important scenario. Example 3 shows how the algorithm responds under the requests of {0.5,2.5,4}Mbps. In this case we don’t achieve the max-min fair distribution of { 0 . 5 , 2 . 24 , 2 . 24 } Mbps. Instead, what we obtain is { 0 . 5 , 2 , 2 . 5 } Mbps. STFQ protects small rates from big ones in a strict sense, giving them complete priority. Although for most cases this provides max-min shares, forcing users with high rates to decrease their transmissions, one can find situations in which a simple difference of 0.1Mbps can suppose starvation of a slightly highly demanding flow in front of the lower one. For instance, in a case where the requirements are { 2 . 5 , 2 . 5 , 2 . 51 } Mbps, the two first flows would achieve their objectives while the third one would not even transmit. Although prioritizing lower rate flows it is already a big milestone, automatically penalizing malicious input streams, not allow misbehaving sources to get a higher share of the bandwidth or to generate delay on other flows by just transmitting packets at a higher rate, in some particular cases that can derive into unfair metrics. The explanation for this behavior arises from two main problems in the original STFQ adaptation to the PIFO abstraction. The first and most important one is that ranks, as defined originally, depend on packets arriving the switch, not served, under the consideration that all packets scheduled will be transmitted at some point. From our approximation point of view, a packet entering to the switch does not necessarily mean that this packet will be transmitted after a short time interval. Packets with low assigned levels of priority can be starved in lower priority queues during long time in congestion periods. And they can even be dropped after having been processed by the ingress. Therefore, enforcing fairness by considering how packets enter the switch (and not leave), is not the most adequate approach when working on strict priority queues. Instead, the number of packets really transmitted into the output link should be the ones controlling how fair shares are accomplished in our algorithm. At the same time, a lot of new packets can arrive and cross the ingress during the time in which a packet moves from ingress to egress. Therefore, the state updates should be only performed in one of the two, to avoid different flows having access to different values of the same variable. An algorithm scheduling new packets in reference to the amount of bytes really transmitted, would be closer to monitor and react on how fair the algorithm is behaving. Again, there is still a gap between the ingress and the egress. Scheduling according only to the packets being transmitted, means loosing the view of all those packets already in the queue. This will provide some variability on the short term, but on the long term, the desired fair bandwidth shares should be finally obtained. 4.3 Single-hop algorithms 47 Figure 4.13: Bandwidth share in Original Start Time Fair Queuing 5Mbps Bottleneck. 54 Experiments and Results repeat until completing the eight different queues. As can be also observed, although more and more packets occupy the levels of all strict priority queues, the highest priority flow will only perceive the packets of its own queue. Delay experienced by the packets transmitted, which will be the ones of the highest priority queue, will only see their transmissions affected by a maximum of 64 packets. Lower level queues will not have any effect on the delay perceived by the transmitting flow at each moment. Therefore, the maximum delay is on the order of 160ms, which results from the 64 packets encountered, each one of 1512Bytes given by the default iperf configuration, transmitted at 5Mbps rate. Note that due to the way queues have been designed, not blocking packets in an individual manner, instead of perceiving a constant value of 64 packets in queue, we experience continuous variations in the queue depth. Figure 4.18: Queue evolution and delay under progressive higher priority flow generation. 4.4.1.2 Effects on a single path Having analyzed the main components taking place in queuing delay, we can now dive into the effects of FIFO+ under a single flow transmission. Following the directives presented in the introduction to generate consecutive congestion in order to perceive FIFO+ effects, we will work under the scenario of Figure 4.19, but with link capacities of 5Mbps, 4.9Mbps, 4.8Mbps, 4.7Mbps and 4.6Mbps for (s1-s2),(s2-s3),(s3-s4),(s4-s5) and (s5-s6) respectively. A single flow will be transmitted from h1 to h6 experiencing the consecutively-decreasing bottleneck along the path. In reference to queue sizes, to compare FIFO and FIFO+ in a fair manner, we will allocate the same queue space for the two algorithms. Following the original work in [ CSZ92 ], the queue size will be set to 120 packets for FIFO and the equivalent 8 queues of 15 packets for FIFO+. After transmitting five UDP flows from h1 to h6 of 1Mbps each, observed results are: an average delay of 815ms with a percentile 99.9 of 997ms for FIFO, and an average delay of 177ms with a 99.9 percentile of 465ms for FIFO+. In contrary to what we were expecting, not only the 99.9 percentile is decreased, but also the average delay. This is due to the fact 4.4 Multi-hop algorithms 55 Figure 4.19: Multi-hop algorithms topology. that our PIFO implementation divides the initial FIFO queue on 8 strict priority slices. When under UDP congestion FIFO+ is applied, only packets from the highest priority queue are being transmitted. Instead of the total queue number of 120 that packets experience in FIFO, in FIFO+ only the 8th part of those packets are affecting the final delay. 4.4.1.3 Effects in traffic from different paths A more complex architecture using the two techniques to generate congestion, and observe the effects of FIFO+ when performing scheduling, is exactly depicted in Figure 4.19. On it, access links have been set to 1000Mbps, letting the connections among switches be the ones creating bottlenecks. Hosts 1, 2 and 3 will be responsible for generating traffic, congesting all links from s1 to s6. They will transmit following different types of distributions, all of them adding up a mean rate of 5Mbps. This way, traffic from h1 will first congest s1-s2 link. To it, traffic from h2 will be added in s2, to congest the link s2-s3. In s3, traffic from h3 will join, congesting s3-s4 as well, and finally, from s4 to s6, link capacities will be decreased progressively to make congestion take place until reaching the final destination. Concerning traffic distributions, three different simulations will be performed. On all of them, each host will be in charge of transmitting 5 flows. In the first simulation, flows will run constant UDP transmissions with packet departure rates of 125 packets per second and packet sizes of 1000Bytes. In the second simulation, each flow will still transmit packets of 1000Bytes, but this time under an exponentially distributed packet departure rate of average 125 packets per second. In the third simulation, a Pareto distribution will be used, of shape γ= 2 and scale δ= 4, for a mean inter-departure time of 8ms, giving also the equivalent 125 packets per second average rate. 1 The results obtained for each simulation are summarized in Table 4.2. In all cases, and in the same way that it was observed for the single-path experiment in Section 4.4.1.2, both the average and the tail delays are smaller in FIFO+ than in FIFO. Having already commented the queue slicing effect which causes this behavior, it is interesting to put the focus on how FIFO+ reacts when scheduling flows that have traveled different paths. As a quick remark, FIFO+ original idea was to just prioritize those packets that, within a given flow, had suffered higher waiting times in previous hops so that, at the end of the path, the tail delays of the flow could be in big part reduced, although increasing a little bit the average delay. However, what we encounter when applying FIFO+ on traffic flows from different paths is that, as all original deadlines are set with the same value, packets from flows having traveled longer distances will arrive to the colliding-switch with substantially smaller deadlines than closer flows. This will make FIFO+ not perform as it was originally expected, but just completely prioritizing packets from further sources over closer ones. This effect can be clearly observed in Figure 4.20. All packets, independently of whether they are transmitted from h1, h2 or h3 are initialized with 1 Note that any Pareto probability distribution is characterized by two parameters: shape γ and scale δ , where the mean of the distribution is defined by: µ=γ×δ γ−1. 56 Experiments and Results FIFO+ Constant Avg. Delay Percentile 99 Flows h1-h6 58 159 Flows h2-h6 55 158 Flows h3-h6 57 170 Overall 57 162 FIFO Constant Avg. Delay Percentile 99 Flows h1-h6 400 482 Flows h2-h6 245 297 Flows h3-h6 168 206 Overall 269 471 Pareto Avg. Delay Percentile 99 Flows h1-h6 49 166 Flows h2-h6 46 159 Flows h3-h6 52 171 Overall 49 165 Pareto Avg. Delay Percentile 99 Flows h1-h6 310 456 Flows h2-h6 204 285 Flows h3-h6 152 203 Overall 221 439 Exponential Avg. Delay Percentile 99 Flows h1-h6 48 163 Flows h2-h6 46 154 Flows h3-h6 50 167 Overall 48 162 Exponential Avg. Delay Percentile 99 Flows h1-h6 359 462 Flows h2-h6 229 287 Flows h3-h6 163 204 Overall 249 447 Table 4.2: Head tail-delay minimization performance for FIFO+ respect FIFO. the same deadline values. However, when FIFO+ is applied in s2, packets from h1 have already crossed s1, and their deadlines have been updated, while packets from h2 still have their ranks at initialization values when performing the scheduling. H1-packets are therefore completely prioritized over packets coming from h2. The same happens in s3. Packets coming from h1 have already crossed s1 and s2, with the corresponding waiting times in each switch. Packets from h2 have crossed s2, and packets from h3 are still in initialization state. Therefore FIFO+ directly prioritizes h1 and h2 packets, with smaller deadlines, above packets coming from h3. By extending this behavior throughout the following switches, at the end of the path, all flows finish achieving equivalent delays. While this behavior can be very beneficial for flows with packets having traveled longer distances, it can be seen as an unfair algorithm for flows crossing shorter paths. In order to achieve a fair FIFO+ implementation, deadlines in the end-hosts should be specified already taking into account which paths are aiming to be followed. For example, in our case, deadlines from h1 should be specified as greater than deadlines from h2. At the same time, deadlines from h2 should be configured bigger than the ones of h3, considering that packets coming from those sources will have to travel different distances (in terms of hops, and therefore waiting times in queues) before finding each other in the common path. This is the crucial reason, why scheduling algorithms in which deadlines have to be updated throughout the path, imply a high level of synchronization, sometimes very difficult to control. 4.4.2 Least Slack Time First: Optimizing deadlines from the end-host LSTF has been demonstrated to be the most versatile algorithm, being able to closely replicate behaviors of diverse scheduling techniques, by just prioritizing packets based on slack deadlines specified from the end-hosts [ MARS15 ]. One can easily observe that the "slack" definition in LSTF is equivalent to the "rank" definition in PIFO, or the "deadline" in EDF. Consequently, 4.4 Multi-hop algorithms 57 Figure 4.20: Queuing delay in FIFO+ and FIFO, experienced in traffic manager queues of consecutive switches along the path by constant 1Mbps transmissions UDP traffic generation. LSTF can be understood as a slice of the PIFO abstraction considering only those algorithms that can be implemented by setting ranks from the end-host and updating them along the path. This excludes LSTF from being able to replicate algorithms like WFQ, which can not be described with a single end-host ranking definition. All multi-tenant scenarios, in which information from different entities is required for concerns like isolation or fairness, are not implementable on a system like LSTF. With PIFO, and therefore also with our solution, those limitations are vanished through rank definitions directly implemented from the switch, as has been already discussed in Section 4.3.4. The interesting aspect of LSTF, further away from its similarities with PIFO, is the flexibility that it provides at the time of configuring deadlines. As those ranks, or slacks, can be defined at a per-packet granularity, in some cases, better results than traditional fixed-rank algorithms can be achieved. For the sake of familiarity with the demonstration, we will consider as baseline the widely researched SFF, and we will see how LSTF is able to outperform it, providing smaller flow completion times under certain circumstances. LSTF can be easily understood in this case as a mix between SFF and FIFO+, and the obtained results completely reflect it. As can be observed in Figure 4.21 and Table 4.3, LSTF implementation achieves in general very similar results to SFF. Following the same rationale than in FIFO+, we can see how the difference in deadlines of traffic having traversed different number of hops, impacts in a bad manner to flows from shorter paths. Those flows have to experience how all the packets from longer paths are prioritized over them, deriving in a worse performance than with the original algorithm. However, when focusing in traffic coming from h1, the action of updating deadlines with queuing times spent along the path, makes LSTF able to defeat SFF by minimizing even more the resulting average flow completion time. Nonetheless, the positive results of LSTF, can not always be generalized. For illustrative purposes and under the idea that LSTF is optimal in minimizing the number of deadlines not fulfilled from the ones specified, Table 4.3 also shows the results when LSTF deadlines are defined following the SFF flow completion times from the previous experiment. As can be observed, satisfying a higher number of deadlines, does not necessarily mean that the global performance will be improved. If the deadlines left to be achieved are the ones with higher impact in the final metric of interest, LSTF will not be able to outperform the desired result. This exhibits the lesson again, that LSTF, as well as FIFO+, and in general all the algorithms which have been implemented on the PIFO abstraction, requires precise levels of detail when 58 Experiments and Results SFF TCP Traffic Avg. FCT Flows h1-h6 46.38116 Flows h2-h6 43.12075 Flows h3-h6 43.94172 Overall 44.48121 LSTF (Flow Size) TCP Traffic Avg. FCT Flows h1-h6 45.81735 Flows h2-h6 45.59687 Flows h3-h6 45.45759 Overall 45.62394 LSTF (SFF Average Delay) TCP Traffic Avg. FCT Flows h1-h6 52.94233 Flows h2-h6 52.94233 Flows h3-h6 48.71241 Overall 52.43344 Table 4.3: Deadline definition strategies performance in Flow Completion Time (FCT). setting up its configuration. A part of showing how LSTF can be used to improve some algorithms design, this example recalls on the idea that deadline management can sometimes demand high levels of accuracy and fine detailed knowledge of the topology, specially in cases where updates are performed along the path. Together with the fact that benefits observed when applying those changes are usually not that significant in the final performance, all these reasons make us believe that the complexity required for using this type of algorithms is not always worth the effort for most common scenarios. 4.5 Limitations and constraints As it was stated in the original PIFO proposal, the new abstraction presented only allows the implementation of work conserving algorithms. This leaves out all those techniques which perform any type of rate modification or traffic shaping (non-work conserving) as well as hierarchical scheduling. The same exact restrictions apply to our strict priority approximation SP-PIFO. It is important to remark that the current version of P4 does not allow any non-work conserving policy, as the egress queues limitation can only be imposed by the output link bottleneck. While it is true that queues can have a rate limit specified, this limit can only be defined at compilation time, or through the control plane in software implementations. Individual queue rates can not be yet (according to the latest P4 version at the time of writing this report) dynamically modified by the P4 program directly. This lack of support for nonwork-conserving algorithms derived from the P4 specification has been the one stopping us from further researching those techniques in which rate limiting and traffic shaping is performed from the switch. In case future enhanced versions of P4 might allow rate control for transmissions through P4 program definitions, to be executed at line-rate, a new range of schedulers including all type of token buckets would then be implementable. Another interesting reflection is that PIFO is not a tool for preventing congestion by itself. SP-PIFO approximation is neither. With the proposed solution, congestion is not prevented and congestion is not eliminated, but congestion can be controlled. To eliminate congestion, strictly speaking, one would need to link PIFO to some mechanism capable of changing the paths that packets follow from source to destination. Although we would like to discuss this idea in future steps, and again, the higher the number of tools working together for a common purpose, the better the result that can be obtained, the presented version of SP-PIFO does not currently give answer to this type of scenarios. What SP-PIFO can do instead, is adapt packets priority in each switch, so that the negative effects of congestion can be minimized. By, for example, making sure that loss sensitive applications are protected in front of not delicate ones, the consequences of congestion can be controlled until the problem is dissolved. In this same example, if any rate-control was applied from the end hosts, users from applications with 4.5 Limitations and constraints 59 Figure 4.21: Flow Completion Time results for multi-hop scheduling techniques. lower level of priority would stop receiving acknowledgements and would probably decrease their rate. As ranks can be dynamically updated, once congestion is solved, packet ranks can be restored to the default values and the initial scheduling behaviors can be easily recovered. It is important to remark that congestions are just events that occur in very particular scenarios, while the majority of time networks run under low utilization levels. Is just in those determinate moments, when quality of service management jumps in and plays such an important role. More advanced techniques aiming to fight congestion have been classified under the "active queue management" field umbrella. Most of them try to predict when congestion is about to happen and react by sending back notifications to the origin hosts, so that they can adapt their transmission rates. The others tend to directly control congestion from the switch by taking advantage of intrinsic traffic shapers or rate limiters at the input. Although, as mentioned, the second group of techniques are not possible due to the lack of traffic shapers in current programmable switches, traditional notification-based active queue management techniques like RED and ECN are perfectly implementable and completely compatible with our solution. 60 Experiments and Results 4.6 Implementation in real networks: Barefoot Tofino One of the clearest requirements that we posed when starting the algorithm design, was making our solution implementable in real hardware. We discussed that most of proposals in nowadays literature relied on ns-3 software simulations or traffic control configurations, which, although providing great results, could be perceived as distant from what current infrastructure was actually able to realize. Following this idea, throughout our algorithm design, we have tried to keep the focus on what possibilities current network equipment was really offering. After having implemented and reviewed the performance of our scheme in software-simulations, we wanted to go a step further and demonstrate the feasibility of executing SP-PIFO in a real hardware switch. Conscious of the intrinsic difficulties that this requirement has supposed, in this section, we will summarize some of the challenges that we have encountered, together with the major insights that have helped us in defining a final accurate approach. When P4 authors exposed their original idea, the first proposal was to make from it a targetindependent high level programming language. One, that would easily represent new manners of processing packets within a common framework, and could then be directly deployed and executed in any P4-supporting switch. All this in a transparent manner, without having to know the intrinsic details of the underlying hardware, nor having to modify the program according to the specific target constraints. Each different switch would just have to define a specific compiler able to convert this P4 general description into the equivalent set of instructions that could finally be understood and executed by the particular selected chip. However, this initial (and quite idealistic) objective can be considered to be, still today, on its early stages. P4- supporting target manufacturers have not been able to provide compilers capable of directly translating P4-default programs into target-specific configurations. Instead, they provide alternative versions of P4 which already consider the most important hardware limitations, and are the ones that algorithm designers should use when aiming to translate their initial program descriptions to the final policies that the switch will be able to run. In this thesis, we decided to work with Barefoot Tofino, a high-performance P4 switch that we are glad to have in our lab, and which has been proven to be the fastest one in the world [ Bar16 ]. Although being fairly programmable, it is still some miles behind the state-of-the-art of P4 language evolution. In particular, Tofino is not compliant with the P4-16 latest specification (the one we have used throughout the thesis). It supports only P4-14 but, the latest Tofino-P4 compiler is still not able to directly convert original P4-14 programs into the equivalent set of instructions for the definitive pipeline configuration. Instead, same as happens with the rest of P4-compliant targets, a restricted and modified version of P4-14 is provided, which considers all the target physical restrictions and constraints that appear when working in real silicon implementations. This specific version of Tofino-P4, has shown us that even working with the behavioral model can sometimes be too optimistic in defining what will actually be implementable later on in hardware. To a certain extent, a common mistake when considering this new wave of programmable networks (and so it was our), is to think of programmable switches as forwarding CPUs, with great saving state capabilities and extended computation facilities. Reality is, however, that programmable switches are just forwarding instances which allow a narrow degree of flexibility. Even our program which, at first, seemed to be reasonably simple to implement, had to be re-designed in order to accommodate the final hardware limitations. The following content has been hidden for confidentiality purposes. Contact the author for further information in case of having explicit written permission by Barefoot Networks Inc. 4.7 SP-PIFO for predictable networks. Next steps and open challenges 61 4.7 SP-PIFO for predictable networks. Next steps and open challenges Having analyzed how effectively SP-PIFO can be used to make the traffic manager programmable and adapt to the different performance objectives, the consequent question arises: Now, what? Now that we have made the traffic manager programmable, with SP-PIFO providing flexibility, how can all this knowledge be applied? How should SP-PIFO be used? It is clear, that making the last remaining pipeline of the PISA architecture also programmable, opens a ton of new possibilities. The starting motivation of this thesis was moving towards predictable networks. Making scheduling programmable was a fundamental milestone to overcome. After having finished this thesis, with the objective of making scheduling programmable achieved, it is interesting to take some time and understand how our proposed solution can be used from now on. The next step towards network predictability is, without any doubt, bringing our SP-PIFO solution to the network perspective. Throughout this thesis we have been working under the assumption of a simple topology, aiming to achieve specific requirements. From now on, this focus should change. Instead, a whole network should be considered, in which the equipment is shared by a given workload where different performance objectives coexist. By itself, working on a global network instead than on a switch level, generates new questions to be discussed. If we add the fact that traffic flows sharing these resources do not aim to achieve the same type of requirements, that opens a wide range of challenges needed to be solved. In the new scenario, where the whole network is covered with SP-PIFO capable switches, the following 5 principal aspects need to be clearly considered. •How to correctly set the ranks: We have seen some examples for a single switch and a single objective. But in a network where not only multiple switches are considered but also a diverse group of objectives, the challenge of how to combine those immediately arises. Can we draw multiple paths? Are the requirements mutually exclusive? In some occasions it may be possible to partition the network following requested demands. But most probably, in the vast majority of cases this isolation of requirements is not feasible in practice. We will then need to adapt the SP-PIFO policies for the global best of the network. Those policies, will not necessarily have to be constant throughout the path. One can clearly imagine that delay-sensitive flows will probably have to cross switches giving them maximum priority but also other hops potentially implementing fairness or other types of algorithms. Which are the optimal SP-PIFO configurations to use across the network, to serve a given workload at each moment? This is the first question that the final system will definitely need to answer. •How to define and evaluate the application requirements: In order to know which are the best policies for a given workload distribution, is important to bring back the problem of how application requirements are specified and where do they come from. It is interesting to make here the reflection of probably the main reason why quality of service has not been successful up to now, which is the hazardous configuration of all the parameters that end-users were forced to manipulate in order to implement it. Tweaking all those parameters supposed a too high complexity, which stopped the big majority of users from using these techniques. In our view, the network should be the one in charge of adapting the services by itself, without having to depend on end-users responsibility to properly define the final strategies to follow. It is a task of the network to automatically configure the best polices, without need for end-users to even know 62 Experiments and Results what is going on at each moment. No need to configure parameters, no need to define requirements. The network should be able to determine what is good or bad for the application. For instance, a promising idea would be to perform load balancing of traffic flows through different paths, measuring the success of each option at the end and using this learning to optimize the best arrangement for future allocations. And this uncovers the next challenge to consider, which is how to correctly define application requirements and evaluate their fulfillment. Since the beginning of the thesis, it was made clear that the network should face the dynamically changing application flow requirements. It was seen that these requirements could be decoupled in jitter, delay and throughput and that they were attached to a desired certain level of quality experience. Quality of experience (QoE) is not an objective metric that can be quantified by the network. Is, instead, a perception by the end-user about how good or bad the received service was. Making the network aware of the final quality of experience received by the user is a key challenge that needs to be solved. And probably the most important one, as it is the basis for all the predictable networks paradigm. How can the user perception of a service be linked to a determined rank distribution? We require means for the network to have access to this information in a transparent way from the user perspective, to evaluate service performances and requirements for each type of connection. Some services like Skype calls, already provide mechanisms for the user to rate the quality of service experienced after this having taken place. It would be reasonable for us, to think about each service having an internal API, giving feedback to the network about the satisfaction of the user from the service. This API should transform users rating at high-level to low-level evaluation metrics that could be easily understood by the network to determine if the allocated policies were the correct, to train the learning system, and adapt future allocations with the knowledge and experience obtained. One possibility to have in mind, should be to think about an available API for each type of application, that sends feedback to the network according to the perception that the user had from the received service under the given conditions. This feedback could be used to adapt the ranking policies accordingly, while storing all this information in the system for performing more intelligent decisions in the future and achieving better results. •How to properly design a rank-setting architecture: Significant emphasis has to be put on describing a clear rank-setting architecture, defining both the appropriate entity (or entities) in charge of developing SP-PIFO rank policies, and the one (or ones) in charge of implementing those policies. Two main options are clearly presented: taking advantage of the centralized vision of a controller in an SDN-like philosophy, or applying a distributed paradigm. Both type of architectures have pros and cons. While a centralized architecture reaches a higher level of optimization thanks to the complete view of the network, it suffers from the single point of failure problem. At the same time, distributed solutions, less optimal but more robust to failures, could also suppose a big amount of overhead. Concerning where to execute those policies we have two main options. The first one is following what we have been doing in the thesis and letting end-hosts select the desired rank distribution. The other alternative, if a higher level of control is desired, would be to require access-switches to define those ranks. In this same group of challenges, another aspect to consider is how the policies can be mixed to achieve different objectives. Are those objectives mutually exclusive? As now a whole network is considered, not a single switch, we can think of paths where different rank definitions are used at each path. A certain flow may cross some switches implementing Weighted Fair Queuing, others Shortest Flow First and some others with just FIFO behav- 4.7 SP-PIFO for predictable networks. Next steps and open challenges 63 ior. Performance objectives have to be defined end-to-end and not at a per-hop level anymore. As a starting point, it is always easier to think about the centralized solution, with the controller optimizing the resources and spreading the policies through APIs with the style of OpenFlow. In the distributed case, instead, data plane packets should be the ones allowing switches to communicate with each other to optimize the SP-PIFO policies throughout the network. One could think of some type of feedback, used to communicate the final results of a specific rank arrangement, to be transmitted from the destination back to the origin, so that switches along the path could use the result information to update the polices accordingly. A simple example for the sake of understanding would be the one for delay. Assume that when a packet reached the destination, a notification could be generated if the achieved delay exceeded the expectations. With this notification, switches could set higher priority ranks for the same type of packets in future communications to increase the chances of the requirements being fulfilled. In this distributed version, two options could also be distinguished. The first would be letting the end-hosts specify the ranks for their connections. The other would be controlling the ranking definition from access-switches on the network. Depending on the desired level of control or independence of the end hosts, one or the other option could be applied. •How to synchronize rank-definitions along the path: As was already envisioned in subsection 4.4.1.3, for algorithms like FIFO+ in which rank definitions are dependent of the paths followed by each packet, when flows having traversed multiple paths encounter, their rank definitions can collide. A mechanism considering this type of problems should also be clearly considered. •How to accommodate traffic dynamism: While all the previous challenges can be studied with a static workload in the network, to bring the problem a bit forward, one should consider including the dimension of time. Assuming that the network does not have a fixed workload to serve, but needs to accommodate the dynamically changing traffic flows with varying requirements, for any types of architectures defined, the proper predictable network design should include means to update and adapt to the new demands that traffic could generate. This supposes not only ways to update the ranking policies along the switches, as the requirements distribution change over time, but also the need of defining admission policies to control whether new demands should be preempted or not, respect existing traffic flows on the network, for the global and fair benefit of the final users. All those questions - and more - will have to be answered in detail when trying to develop accurate and sophisticate solutions based on the new predictable networks paradigm. What it is clear, however, is that tools like SP-PIFO, after having proved the great versatility that it can adopt, and the wide range of results that it can achieve, will be key in enabling new paths and enforcing research to keep progressing towards that direction. The flexibility with which the proposed solution has been designed, together with the diverse implementation issues deeply discussed throughput this thesis, will make the transition to the forthcoming next generation predictable networks much more straightforward to realize.