Incentive-Compatible Differentiated Scheduling

Martin Karsten, Yunfeng Lin, and Kate Larson

Fourth Workshop on Hot Topics in Networks (HotNets IV)

Paper, Presentation Slides

Abstract: In this paper, we take a novel approach at service differentiation in packet-switched networks. Existing mechanisms for delay control and differentiation typically require some form of explicit resource allocation and consequently, admission control. We propose incentive-compatible differentiated scheduling as a basic building block for Internet service provisioning. This scheduling scheme enables policy-free approximate service differentiation without admission control, for example at Internet peering exchanges. In addition, the same building block can also facilitate precise service differentiation in combination with several forms of admission control. We present the basic design of a scheduling algorithm and discuss its implementation details and design alternatives. We prove that the algorithm has strong game-theoretic properties and present some initial simulations illustrating the effect of this scheduler on Internet traffic.

FIFO Service with Differentiated Queueing

Martin Karsten


Paper (DOI)
Presentation Slides

Abstract: This paper presents a novel approach to minimally invasive service differentiation in packet-switched networks. Instead of actively managing service allocation, a simple differentiated queueing algorithm provides traffic classes with essentially the same best-effort service that would result from plain FIFO service using a single queue for all traffic. However, each class is served from a separate virtual queue, which is configured with an individual deterministic delay bound that is enforced in the presence of dynamically varying packet arrival rates. The main advantage of such a scheme for service differentiation is administrative simplicity, because it only needs minimal configuration by a network operator and does not necessarily require control plane functionality. Further, it does not inherently prefer some traffic classes over others and thus satisfies even the most radical definitions of network neutrality. In the paper, the basic approach is motivated with the help of various use case scenarios. A fairly simple and efficient algorithm is presented to implement the differentiated queueing scheme. Finally, a number of simulation experiments and results are shown that confirm the intuitive functionality of the algorithm.

Traffic-Driven Implicit Buffer Management - Delay Differentiation Without Traffic Contracts

Martin Karsten, Daniel S. Berger, Jens Schmitt

International Teletraffic Congress 2016 (ITC 28)

Technical Report

Abstract: Different network applications have different service preferences regarding packet delay and buffering. Delay management requires scheduling support at routers, which traditionally also requires some form of traffic specification and admission control. In contrast, this paper studies the problem of guaranteeing queueing delay bounds for multiple service classes without traffic contracts and without affecting the throughput rate for each class. A solution to this problem is given by decoupling throughput and delay management via traffic-driven implicit buffer management. Using this concept, the Delay Segment FIFO (DSF) packet scheduler guarantees differentiated delay targets in the presence of unregulated throughput rates. This decoupling represents a modular approach and DSF embodies a small and self-contained feature set. Furthermore, DSF's service model satisfies even a strict interpretation of network neutrality, while effectively guaranteeing delay targets for multiple service classes. DSF's design and service characteristics are analyzed mathematically and validated through simulations.