Size-aware Scheduling of TCP Flows
The Internet Traffic Managers (ITM) Group
Computer Science Department
Boston University
Scheduling policies that give preference to short jobs, such as Shortest Job First (SJF) and Shortest Remaining Processing Time (SRPT) first scheduling, are long-known to be beneficial to reducing the mean response time of the system. Since the delivery of Internet documents can be viewed as an instance of job scheduling problem, it is presumably beneficial to give high priority to the transfer of short flows.
In this project, we investigate the problem of practical deployment of size-aware scheduling of Internet flows. Specifically, we focus on the management of congestion-responsive flows, such as TCP flows, which dominate the current Internet backbone traffic.
Providing differentiated service to different classes of flows requires enhanced functionalities be supported at intermediate routers. The Internet Traffic Managers architecture fits our needs in this regard. Internet Traffic Managers (ITM's) are special network elements that are strategically placed at the edges of network domains (e.g., in front of busy web servers or at exchange/peering points between administrative domains), so that various control strategies can be applied to incoming traffic to achieve certain performance optimization goals. A more detailed description of the architecture can be found at the Internet Traffic Managers website.
There are two issues that need to be addressed in the implementation of network scheduling:
- Since we do not want to disturb the end users, how can the routers tell the size of the flows without a priori knowledge?
- To reduce the cost of implementation, service differentiation beyond the ITM must be done on per-class basis. However, it is also desirable to have predictable end-to-end performance, so that it is easy to adaptively tune control parameters at the ITM to achieve the best performance.
Traffic Manager: Threshold-based Classification
Figure 1: Threshold-based packet classification
As shown in Figure 1, the traffic manager (router at the edge of the domain) maintains a counter for each flow, recording how many packets have been transmitted. Packets from every new flow by default obtain the highest priority (colored in red in the figure). However, once this counter exceeds some pre-defined threshold, the priority of the remaining packets is reduced to the next lower level (colored in blue in the figure). Coloring (packet classification) is accomplished by tagging corresponding field, or DiffServ Code Point, at the packet header.
Core Router: AQM with Proportional Dropping
Figure 2: AQM with propotional dropping
To achieve a scalable but tunable control, we propose to implement proportional dropping for packets of different classes at the bottleneck queue. This can be achieved by a simple extension of the RED queue, as shown in Figure 2. From the TCP friendly equation, the throughput of a TCP flow is roughly proportional to the square root of the loss rate it experiences in transmiting packets. Therefore, proportional dropping implies proportional throughput differentiation. Such statistical performance guarantee makes it easy to adapt control parameters, such as the packet classification threshold, according to changes in network state.
The development of the adaptive controller is covered in the technical details section.