A scalable approach to sharing network capacity: Weighted fair queuing without queues and without scheduling

Master

Weighted fair queuing (WFQ) has been a widely used component of networks since it was first proposed in the late 1980s. It involves scheduling jobs (packets in the case of the Internet) so that each user gets the weighted share of capacity they have contracted to receive. It is proposed to implement and test a simple idea we have had that uses a completely different approach but still achieves a similar outcome to WFQ. Our idea is being used by a commercial traffic management equipment vendor at large scale in production networks, but all their test results are private. All we know is that this company found that their existing state-of-the-art WFQ algorithms failed somewhere above 200MB/s, while our algorithm (implemented in software) was still working fine up to 4Gb/s.

Outline of approach: Traditionally, scheduling has been designed so that any user offering more load than their 'weighted-fair' share builds a queue. Since WFQ was first proposed, it has become recognised that queuing delay should be minimised, and active queue management (AQM) technology has been introduced within each user queue (e.g. flow-queuing controlled delay aka. fq_CoDel). AQM randomly drops (or marks) an increasing number of packets dependent on queuing delay. In the proposed approach, all users share a single queue with a single AQM algorithm. A simple "token-bucket" policer is associated with each user to monitor their rate of drops (or marks) and it discards their traffic if they exceed their 'weighted-fair' share of drops (or marks). Such policing of a single queue is much more efficient than creating one queue per user and scheduling all their outputs. It is also amenable to distributed implementation.

Goal

The aim of this project is to conduct publishable performance tests for our algorithm. As well as supporting higher link rates, we believe our algorithm should also be able to efficiently support orders of magnitude more users than state-of-the-art WFQ algorithms, which can only support tens of users efficiently.

The project builds in stages, so that some success can be assured at each step, while more capable students can still be stretched. Step #1: Implement the algorithm and functional test; Step #2: Build testing environment; Step #3: Perform testing over at least two dimensions (bit-rate and number of users); Step #4: Prepare a paper for submission to a suitable research venue (based on the Masters thesis material).

Learning outcome

  • Best practice in Linux kernel programming
  • Operating systems design, particularly networking
  • Internet transport protocol design and behaviour: TCP, UDP, AQM, ECN etc
  • Writing a top-flight research paper

Qualifications

  • Good programming skills
  • Good grounding in operating systems
  • Good grounding in Internet protocols
  • Interest in algorithms research

Supervisors

Bob Briscoe