Flow Routing Project Page
Welcome to Thomas Dreibholz's
Flow Routing Project Page
Quick Navigation
Latest News
- July 14, 2011
Updated Internet Drafts - July 24, 2010
BibTeX entries have been added to the Research section.
- July 5, 2009
pdated the drafts in the Standardization section. - May 24, 2009
A new journal article has been added to the Research section. - March 05, 2009
The Internet Drafts in the Standardization section have been updated. - January 05, 2009
The slides of the FGCN 2008 talk have been added to the Research section. - September 29, 2008
This project is still alive! There are two new research papers on the QoS Device in the Research section! Furthermore, the Standardization section has been updated with the latest IPv4 Flowlabel drafts. - News Archive
Go to the News Archive
What is our Flow Routing project?
Introduction
The Internet was originally designed as a best effort network to support simple applications like electronic mail and file transfers via low-speed links. Since high-speed gigabit backbones have become widespread within the last few years and high-speed links are even available for home-users in the form of DSL (digital subscriber line), new multimedia applications like audio on demand (AoD), video on demand (VoD), audio/video conferences and Internet telephony are possible. But while a best effort delivery is sufficient for classical TCP/IP-based applications like web browsing, the new applications require strict delivery guarantees. For example, the perceptual quality of a video conference may be poor when it does not get a constant bitrate of 2 MBit/s.
Flow-State Aware Routing
In the early ages of the Internet memory had been scarce and extremely expensive. Therefore, routing had been realized on a per-packed basis. While this scheme achieved a cost advantage in reducing the amount of memory required in routers, it has become a severe problem in today's routers. Nowadays, memory is quite inexpensive - therefore, per-packet routing does not achieve a significant cost advantage - but networks are very fast. That is, a tremendous amount of CPU power is needed to efficiently route packets at speeds of multiple gigabits per second. Flow-state aware routing can significantly reduce this effort: instead of making a routing decision for every packet, a router memorizes flow identities and only makes a routing decision once for each flow. Maintaining flow tables containing even millions of flows is significantly cheaper than routing each packet (routing tables for BGP routers can grow very large!), resulting in flow-state aware routing becoming even less expensive than classical per-packet routing. Flow-routing may be implemented incrementally, that is flow-based routers can co-exist with classical routers in the same network as shown in the figure above. For details on flow routing, see [Anagran].
Our QoS Concept
Flow-state aware routing not only offers the advantage of inexpensive routing, it also makes it possible to implement Quality of Service (QoS) mechanisms. The goal of our project is a simple and efficient QoS protocol to provide QoS assurances to certain flows, which can be implemented for flow routers (and also for classical, packet-based routers with some additional effort). A key assumption for our QoS concept - based on observations by IP broadband providers - is that service providers (e.g. audio and video media libraries) are connected via a high-speed internetwork to the access providers of the customers as shown here:
The customers may be connected via an edge node to Access Providers by e.g. DSL links, TV cable, Wireless LAN (IEEE 802.11), UMTS or ATM. Different service providers may simultaneously deliver content to a single customer. Core bandwidth is usually over-provided, therefore, it is further assumed that the link to the customer becomes the main bottleneck of the system and the edge node is the place where congestion occurs.
As long as the user does not request more media flows than available link bandwidth, there should be no problem. But let us consider the following scenario as shown in the figure here:
One family member requests a sports video at 5 MBit/s, another one requests a soap opera at 3 MBit/s and yet another requests an action video at 5 MBit/s via a single 10 MBit/s link. This is a situation where packet loss is likely to occur. Since all flows have equal priority, the packet loss is likely to affect all flows. It is possible that the quality reduction is so severe that all flows are of unacceptable quality. Clearly, an edge node that was able to apply an intelligent discard policy, focusing loss on a single (or as few as possible) flows, would minimise disruption to the total number of flows (see [Smith91]).
The basic principle may be illustrated using the simplest scenario: all content is constant bitrate. Assume that the customer adds new flows one at a time with some short interval (e.g. some seconds) before the next flow is added. Then congestion happens through the "last straw" (i.e. "Its the last straw which breaks the camel's back" - Proverb) principle. In other words, there is no congestion until a flow is added which takes the combined bitrate above the capacity available for that customer. It is easy to see that by simply deleting the packets of this latest flow, congestion would be removed. This suggests, that the QoS protocol needs to memorise the identity of the latest flow and be prepared to delete the packets of this flow. Then, it would be possible to protect the remaining flows from congestion.
Our QoS Protocol
We can now extend this scenario to include variable bitrate flows; here, the QoS protocol needs to memorize the last r flows. When congestion occurs, the device still tries to delete the packets of the latest flow but is prepared to drop packets of the other r-1 flows if congestion persists. Further complexity is added as we move from a strictly "last flow suffers" world into a policy-based world where the latest flow is not necessarily the one that will be targeted.
Having set out the principle of the device, we can now describe the functionality.
As shown here, the device contains the following functions for each of its customer links:
The Output Buffer holds the data to be sent via the link to the customer. This is necessary to cope with bursty traffic. Its current fill level is reported to the Control Logic. Note, the set of customer buffers need not be separate, they can be implemented e.g. using a global memory area.
The Flow Register keeps a list of flows that are the focus of packet discard (the so called Drop Window, see below).
The Packet Handling Unit receives incoming packets and identifies whether they belong to flows which are currently the focus of packet discard by using the Flow Register. It also applies a discard function to the packets. That is, it drops packets of flows selected by the Control Logic for focused packet discard.
Flows are added to and removed from the Flow Register by the Control Logic. Furthermore, it controls the packet drop behaviour by examining the Output Buffer's load level. In case of congestion, it decides which flows are the focus of packet dropping and triggers the packet dropping by the Packet Handling Unit.
A key assumption is that service providers (e.g. audio and video media libraries) are connected via a high-speed internetwork to the access providers of the customers as shown here: We propose that at start up a new flow begins with the sending of a "Start Packet", which contains all information necessary to identify the packets of the flow (e.g. source and destination addresses, flow label or port numbers), a Rate Advisory, that is the (estimated) peak rate of the flow, a policy field which contains a policy for the flow (e.g. to move it directly to the Guaranteed Area, see below), a priority field that contains the priority of the flow and finally a sub-components field that contains information about different layers of the flow (so called layered transmission, see [Dre01]). Notice also that this device fits with the connection-less paradigm in that the sources are only required to transmit a Start Packet and then, without waiting further, start to transmit their data. There is no negotiation, unlike classical RSVP.
When the edge node receives a Start Packet for a new flow, the Control Logic adds the flow to the Flow RegisterPolicies allow a refinement of this behaviour.. This register contains the identities of all flows that are in the Drop Window, and are a potential focus of packet discard in the case of congestion. The Drop Window has a limited number of entries (configured by the administrator) and the sum of all flows' Rate Advisories within the window should be >= N% of the link bandwidth.
With the duration of time, flows gradually move through the Drop Window into the Guaranteed Area. This movement within the Drop Window actually consists of a re-classification of flows so that they become less likely to be targeted. The default policy is that the latest flow will be the subject of immediate discards in the event of congestion and only when discards on this flow fail to reduce congestion will the additional flows be targeted.
After arriving in the Guaranteed Area, flows will not be the focus of packet discard any longer, except in cases of rare and very extreme congestion where the amount of packets necessary to drop exceeds the amount of packets currently sent by flows within the Drop Window. (The fact that up to N% of the link bandwidth is available for discard should make such an action very rare.) Even in these circumstances, the Guaranteed Area is not subjected to random losses. Rather, the device randomly selectsBy selecting a packet from the Output Buffer and obtaining its flow identity. one new flow at a time from the Guaranteed Area and adds it temporarily to the Drop Window, thereby increasing the packets available for discard to > N%.
Returning to the description of the normal movement of flows through the Drop Window to the Guaranteed Area, the default policy is to move the flow that has been within the Drop Window for the longest time into the Guaranteed Area, when the remaining additional flows themselves constitute >= N% of the link bandwidth. Other useful policies are e.g. to move video conferences first.
Note that it is a special property of our device that it is not necessary to save the identities of flows within the Guaranteed Area. It is implicitly assumed that all packets not belonging to flows of the Drop Window are flows of the Guaranteed Area. Therefore, only a constant space is required for each customer link's Drop Window; this significantly improves the device's scalability. Normally, flows within the Drop Window are just overwritten by new flows; however the device also has a mechanism, based on time and/or packet count, to remove flows from the window. This property ensures efficiency and scalability.
As stated, the flows within the Drop Window are the focus of packet discard in case of congestion. The Control Logic detects congestion by monitoring the buffer fill level. If the congestion reaches a certain configured threshold, it triggers packet discard by the Packet Handling unit. This is applied to all packets of (usually) the latest flow added to the Drop Window. Furthermore, the source and receiver of the flow are notified about the congestion by a Congestion Notification message in the form of an Alarm Packet. If congestion continues after this action and the buffer fill level reaches a second threshold, then the Control Logic instructs the Packet Handling unit to begin discarding on all the other flows in the Drop Window. Again alarm messages are sent to the sources and receivers. Since the Rate Advisory sum of all flows in the Drop Window is <= N of the link bandwidth, there should be sufficient droppable packets. Only in some rare cases of extreme congestion (for example by a malicious user), may it be necessary to drop packets from flows within the Guaranteed Area.
Beside simplicity, efficiency and scalability, our described edge node further provides the following advantages compared to RSVP: a guarantee is provided for the admitted flows except under extreme and very rare traffic conditions. Selected flows will be targeted for packet loss, other flows can continue without any loss or undesirable packet delays. It is possible to admit flows without knowing the remaining capacity of the link and admit variable bitrate flows without being constrained to accept only a set of flows whose peak rates are less than the available capacity, but it is not necessary to keep active/ceased state information on admitted flows. The admission of flows does not require a suspension of higher-level session control protocols; a sender is only required to send a Start Packet.
Research
Wenyu Zhu, Thomas Dreibholz, Erwin P. Rathgeb, Xing Zhou
A Scalable QoS Device for Broadband Access to Multimedia Services
SERSC International Journal of Multimedia and Ubiquitous Engineering (IJMUE)
May 2009
Paper as PDF file BibTeXWenyu Zhu, Thomas Dreibholz, Erwin P. Rathgeb, Xing Zhou
A Scalable QoS Device for Broadband Access to Multimedia Services
2nd IEEE Future Generation Communication and Networking Conference (FGCN)
Sanya/People's Republic of China
December 2008
Paper as PDF file BibTeX
Slides as PDF fileWenyu Zhu, Thomas Dreibholz, Erwin P. Rathgeb
Analysis and Evaluation of a Scalable QoS Device for Broadband Access to Multimedia Services
33rd IEEE Local Computer Networks Conference (LCN 2008)
Montreal/Canada
October 2008
Paper as PDF file BibTeX
Poster as PDF fileJohn L. Adams, Avril IJsselmuiden, Larry Roberts.
An advanced QoS protocol for real-time content over the internet
IWQoS 2005. 13th Int. Workshop, Passau, Germany. In: Springer Lecture Notes in Computer Science LNCS 3552, Eds. Hermann de Meer and Nina Bhatti., pp 164-177.
BibTeXThomas Dreibholz, Avril IJsselmuiden, John L. Adams
An Advanced QoS Protocol for Mass Content
30th IEEE Local Computer Networks Conference (LCN 2005)
Sydney/Australia
November 2005
Paper as PDF file BibTeX
Poster as PDF fileJohn L. Adams, Larry Roberts, Avril IJsselmuiden.
Changing the internet to support real-time content supply from a large fraction of broadband residential users
BT Tech. Journal, Special Edition on QoS. April 2005 Vol. 23, No. 2 pp 217-231Thomas Dreibholz, Avril IJsselmuiden, John L. Adams
Simulation of an advanced QoS protocol for mass content
Second International Conference HET-NETs '04 on Performance Modelling and Evaluation of Heterogeneous Networks
Ikley, West Yorkshire/United Kingdom
July 2004
Paper as PDF file (7 pages) BibTeX
Slides as PDF file (ca. 22 MBytes!)Thomas Dreibholz, Avril Smith, John L. Adams
Realizing a scalable edge device to meet QoS requirements for real-time content delivered to IP broadband customers
10th IEEE International Conference on Telecommunications (ICT'2003),
Papeete/Tahiti, French Polynesia
February 2003
Paper as PDF file (7 pages) BibTeX
Paper as PostScript/GZip file (7 pages)
Slides as PDF fileThomas Dreibholz
Management of Layered Variable Bitrate Multimedia Streams over DiffServ with A Priori Knowledge
Masters Thesis, University of Bonn, Institute for Computer Science
February 2001
Thesis as PDF file (183 pages - ca. 7 MBytes!) BibTeXJohn L. Adams, Avril Smith, Christopher J. Adams
Use of the cell loss priority tagging mechanism in ATM switches
Proc. ICIE 91, Singapore, Dec. 1991.
Paper as PDF file (6 pages - ca. 22 MBytes!) BibTeX
Standardization
draft-dreibholz-ipv4-flowlabel-15.txt
An IPv4 Flowlabel Option
Previous versions: Version 14 Version 13, Version 12, Version 11, Version 10, Version 09, Version 08, Version 07, Version 06, Version 05, Version 04, Version 03, Version 02, Version 01, Version 00draft-adams-qos-broadband-00.txt
A New QoS Mechanism for Mass-Market BroadbandJohn L. Adams, Avril Smith
Packet discard control for broadband services
European Patent Application No. EP 01 30 5209. Issue June 2001.
Document as PDF file (65 pages)John L. Adams, Avril Smith
A new QoS mechanism for mass-market broadband
ITU-T Contribution, D184, Q4, SG13, Geneva, January 2002.
Document as PDF file (14 pages)
Our Implementation
Currently, our QoS protocol has not yet been implemented. Our plan is to implement the device's functionality as a Queuing Discipline (QDisc) for Linux Traffic Control. This implementation is offered as a student project.