Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userEiffel: Efficient and Flexible Software Packet Scheduling
199
0
0.0
(
0
)
Added by
Ahmed Saeed
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Packet scheduling determines the ordering of packets in a queuing data structure with respect to some ranking function that is mandated by a scheduling policy. It is the core component in many recent innovations to optimize network performance and utilization. Our focus in this paper is on the design and deployment of packet scheduling in software. Software schedulers have several advantages over hardware including shorter development cycle and flexibility in functionality and deployment location. We substantially improve current software packet scheduling performance, while maintaining flexibility, by exploiting underlying features of packet ranking; namely, packet ranks are integers and, at any point in time, fall within a limited range of values. We introduce Eiffel, a novel programmable packet scheduling system. At the core of Eiffel is an integer priority queue based on the Find First Set (FFS) instruction and designed to support a wide range of policies and ranking functions efficiently. As an even more efficient alternative, we also propose a new approximate priority queue that can outperform FFS-based queues for some scenarios. To support flexibility, Eiffel introduces novel programming abstractions to express scheduling policies that cannot be captured by current, state-of-the-art scheduler programming models. We evaluate Eiffel in a variety of settings and in both kernel and userspace deployments. We show that it outperforms state of the art systems by 3-40x in terms of either number of cores utilized for network processing or number of flows given fixed processing capacity.
rate research
Read More
A common situation occurring when dealing with multimedia traffic is having large data frames fragmented into smaller IP packets, and having these packets sent independently through the network. For real-time multimedia traffic, dropping even few packets of a frame may render the entire frame useless. Such traffic is usually modeled as having {em inter-packet dependencies}. We study the problem of scheduling traffic with such dependencies, where each packet has a deadline by which it should arrive at its destination. Such deadlines are common for real-time multimedia applications, and are derived from stringent delay constraints posed by the application. The figure of merit in such environments is maximizing the systems {em goodput}, namely, the number of frames successfully delivered. We study online algorithms for the problem of maximizing goodput of delay-bounded traffic with inter-packet dependencies, and use competitive analysis to evaluate their performance. We present competitive algorithms for the problem, as well as matching lower bounds that are tight up to a constant factor. We further present the results of a simulation study which further validates our algorithmic approach and shows that insights arising from our analysis are indeed manifested in practice.
Quite a few algorithms have been proposed to optimize the transmission performance of Multipath TCP (MPTCP). However, existing MPTCP protocols are still far from satisfactory in lossy and ever-changing networks because of their loss-based congestion control and the difficulty of managing multiple subflows. Recently, a congestion-based congestion control, BBR, is proposed to promote TCP transmission performance through better use of bandwidth. Due to the superior performance of BBR, we try to boost MPTCP with it. For this propose, coupled congestion control should be redesigned for MPTCP, and a functional scheduler able to effectively make use of the characteristics of BBR must also be developed for better performance. In this paper, we first propose Coupled BBR as a coupled congestion control algorithm for MPTCP to achieve high throughput and stable sending rate in lossy network scenarios with guaranteed fairness with TCP BBR flows and balanced congestion. Then, to further improve the performance, we propose an Adaptively Redundant and Packet-by-Packet (AR&P) scheduler, which includes two scheduling methods to improve adaptability in highly dynamic network scenarios and keep in-order packet delivery in asymmetric networks. Based on Linux kernel implementation and experiments in both testbed and real network scenarios, we show that the proposed scheme not only provides higher throughput, but also improves robustness and reduces out-of-order packets in some harsh circumstances.
Multipath TCP (MPTCP) is a transport layer protocol that allows network devices to transfer data over multiple concurrent paths, and hence, utilizes the network resources more effectively than does the traditional single-path TCP. However, as a reliable protocol, MPTCP still needs to deliver data packets (to the upper application) at the receiver in the same order they are transmitted at the sender. The out-of-order packet problem becomes more severe for MPTCP due to the heterogeneous nature of delay and bandwidth of each path. In this paper, we propose the forward-delay-based packet scheduling (FDPS) algorithm for MPTCP to address that problem. The main idea is that the sender dispatches packets via concurrent paths according to their estimated forward delay and throughput differences. Via simulations with various network conditions, the results show that our algorithm significantly maintains in-order arrival packets at the receiver compared with several previous algorithms.
Extended Berkeley Packet Filter (BPF) has emerged as a powerful method to extend packet-processing functionality in the Linux operating system. BPF allows users to write code in high-level languages (like C or Rust) and execute them at specific hooks in the kernel, such as the network device driver. To ensure safe execution of a user-developed BPF program in kernel context, Linux uses an in-kernel static checker. The checker allows a program to execute only if it can prove that the program is crash-free, always accesses memory within safe bounds, and avoids leaking kernel data. BPF programming is not easy. One, even modest-sized BPF programs are deemed too large to analyze and rejected by the kernel checker. Two, the kernel checker may incorrectly determine that a BPF program exhibits unsafe behaviors. Three, even small performance optimizations to BPF code (e.g., 5% gains) must be meticulously hand-crafted by expert developers. Traditional optimizing compilers for BPF are often inadequate since the kernel checkers safety constraints are incompatible with rule-based optimizations. We present K2, a program-synthesis-based compiler that automatically optimizes BPF bytecode with formal correctness and safety guarantees. K2 produces code with 6--26% reduced size, 1.36%--55.03% lower average packet-processing latency, and 0--4.75% higher throughput (packets per second per core) relative to the best clang-compiled program, across benchmarks drawn from Cilium, Facebook, and the Linux kernel. K2 incorporates several domain-specific techniques to make synthesis practical by accelerating equivalence-checking of BPF programs by 6 orders of magnitude.
Software-defined networking (SDN) provides an agile and programmable way to optimize radio access networks via a control-data plane separation. Nevertheless, reaping the benefits of wireless SDN hinges on making optimal use of the limited wireless fronthaul capacity. In this work, the problem of fronthaul-aware resource allocation and user scheduling is studied. To this end, a two-timescale fronthaul-aware SDN control mechanism is proposed in which the controller maximizes the time-averaged network throughput by enforcing a coarse correlated equilibrium in the long timescale. Subsequently, leveraging the controllers recommendations, each base station schedules its users using Lyapunov stochastic optimization in the short timescale, i.e., at each time slot. Simulation results show that significant network throughput enhancements and up to 40% latency reduction are achieved with the aid of the SDN controller. Moreover, the gains are more pronounced for denser network deployments.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
