| |
|
|
ADSL Bandwidth Management HOWTODan Singletary
This document describes how to configure a Linux router to more effectively manage outbound traffic on an ADSL modem or other device with similar bandwidth properties (cable modem, ISDN, etc). Emphasis is placed on lowering the latency for interactive traffic even when the upstream and/or downstream bandwidth is fully saturated.
1. IntroductionThe purpose of this document is to suggest a way to manage outbound traffic on an ADSL (or cable modem) connection to the Internet. The problem is that many ADSL lines are limited in the neighborhood of 128kbps for upstream data transfer. Aggravating this problem is the packet queue in the ADSL modem which can take 2 to 3 seconds to empty when full. Together this means that when the upstream bandwidth is fully saturated it can take up to 3 seconds for any other packets to get out to the Internet. This can cripple interactive applications such as telnet and multi-player games. 1.1. New Versions of This DocumentYou can always view the latest version of this document on the World Wide Web at the URL: http://www.tldp.org. New versions of this document will also be uploaded to various Linux WWW and FTP sites, including the LDP home page at http://www.tldp.org. 1.2. Email Discussion ListFor questions and update information regarding ADSL Bandwidth Management please subscribe to the ADSL Bandwidth Management email list at http://jared.sonicspike.net/mailman/listinfo/adsl-qos. 1.3. DisclaimerNeither the author nor the distributors, or any other contributor of this HOWTO are in any way responsible for physical, financial, moral or any other type of damage incurred by following the suggestions in this text. 1.4. Copyright and LicenseThis document is copyright 2002 by Dan Singletary, and is released under the terms of the GNU Free Documentation License, which is hereby incorporated by reference. 1.5. Feedback and correctionsIf you have questions or comments about this document, please feel free to contact the author at dvsing@sonicspike.net. 2. Background2.1. PrerequisitesThe method outlined in this document should work in other Linux configurations however it remains untested in any configuration but the following:
2.2. LayoutIn order to keep things simple, all references to network devices and configuration in this document will be with respect to the following network layout diagram:
2.3. Packet QueuesPacket queues are buckets that hold data for a network device when it can't be immediately sent. Most packet queues use a FIFO (first in, first out) discipline unless they've been specially configured to do otherwise. What this means is that when the packet queue for a device is completely full, the packet most recently placed in the queue will be sent over the device only after all the other packets in the queue at that time have been sent. 2.3.1. The UpstreamWith an ADSL modem, bandwidth is asymmetric with 1.5Mbit/s typical downstream and 128kbit/sec typical upstream. Although this is the line speed, the interface between the Linux Router PC and the ADSL modem is typically at or above 10Mbit/s. If the interface to the Local Network is also 10Mbit/s, there will typically be NO QUEUING at the router when packets are sent from the Local Network to the Internet. Packets are sent out eth0 as fast as they are received from the Local Network. Instead, packets are queued at the ADSL modem since they are arriving at 10Mbit/s and only being sent at 128kbit/s. Eventually the packet queue at the ADSL modem will become full and any more packets sent to it will be silently dropped. TCP is designed to handle this and will adjust it's transmit window size accordingly to take full advantage of the available bandwidth. While packet queues combined with TCP result in the most effective use of bandwidth, large FIFO queues can increase the latency for interactive traffic. Another type of queue that is somewhat like FIFO is an n-band priority queue. However, instead of having just one queue that packets line up in, the n-band priority queue has n FIFO queues which packets are placed in by their classification. Each queue has a priority and packets are always dequeued from the highest priority queue that contains packets. Using this discipline FTP packets can be placed in a lower priority queue than telnet packets so that even during an FTP upload, a single telnet packet will jump the queue and be sent immediately. This document has been revised to use a new queue in linux called the Hierarchical Token Bucket (HTB). The HTB queue is much like the n-band queue described above, but it has the capability to limit the rate of traffic in each class. In addition to this, it has the ability to set up classes of traffic beneath other classes creating a hierarchy of classes. Fully describing HTB is beyond the scope of this document, but more information can be found at http://www.lartc.org 2.3.2. The DownstreamTraffic coming inbound on your ADSL modem is queued in much the same way as outbound traffic, however the queue resides at your ISP. Because of this, you probably don't have direct control of how packets are queued or which types of traffic get preferential treatment. The only way to keep your latency low here is to make sure that people don't send you data too fast. Unfortunately, there's no way to directly control the speed at which packets arrive, but since a majority of your traffic is most likely TCP, there are some ways to slow down the senders:
3. How it WorksThere are two basic steps to optimize upstream bandwidth. First we have to find a way to prevent the ADSL modem from queuing packets since we have no control over how it handles the queue. In order to do this we will throttle the amount of data the router sends out eth0 to be slightly less than the total upstream bandwidth of the ADSL modem. This will result in the router having to queue packets that arrive from the Local Network faster than it is allowed to send them. The second step is to set up priority queuing discipline on the router. We'll investigate a queue that can be configured to give priority to interactive traffic such as telnet and multi-player games. The final step is to configure the firewall to prioritize packets by using fwmark. 3.1. Throttling Outbound Traffic with Linux HTBAlthough the connection between the router and the modem is at 10Mbit/s, the modem is only able to send data at 128kbit/s. Any data sent in excess of that rate will be queued at the modem. Thus, a ping packet sent from the router may go to the modem immediately, but may take a few seconds to actually get sent out to the Internet if the queue in the modem has any packets in it. Unfortunately most ADSL modems provide no mechanism to specify how packets are dequeued or how large the queue is, so our first objective is to move the place where the outbound packets are queued to somewhere where we have more control over the queue. We'll do this by using the HTB queue to limit the rate at which we send packets to the ADSL modem. Even though our upstream bandwidth may be 128kbit/s we'll have to limit the rate at which we send packets to be slightly below that. If we want to lower the latency we have to be SURE that not a single packet is ever queued at the modem. Through experimentation I have found that limiting the outbound traffic to about 90kbit/s gives me almost 95% of the bandwidth I could achieve without HTB rate control. With HTB enabled at this rate, we've prevented the ADSL modem from queuing packets. 3.2. Priority Queuing with HTBAt this point we still haven't realized any change in the performance. We've merely moved the FIFO queue from the ADSL modem to the router. In fact, with Linux configured to a default queue size of 100 packets we've probably made our problem worse at this point! But not for long... Each neighbor class in an HTB queue can be assigned a priority. By placing different types of traffic in different classes and then assigning these classes different priorities, we can control the order in which packets are dequeued and sent. HTB makes it possible to do this while still avoiding starvation of any one class, since we're able to specify a minimum guaranteed rate for each class. In addition to this, HTB allows for us to tell a class that it may use any unused bandwidth from other classes up to a certain ceiling. Once we have our classes set up, we set up filters to place traffic in classes. There are several ways to do this, but the method described in this document uses the familiar iptables/ipchains to mark packets with an fwmark. The filters place traffic into the classes of the HTB queue based on their fwmark. This way, we're able to set up matching rules in iptables to send certain types of traffic to certain classes. 3.3. Classifying Outbound Packets with iptablesThe final step in configuring your router to give priority to interactive traffic is to set up the firewall to define how traffic should be classified. This is done by setting the packet's fwmark field. Without getting into too much detail, here is a simplified description of how outbound packets might be classified into 4 classes with the highest priority class being 0x00:
Obviously, this can be customized to fit your needs. 3.4. A few more tweaks...There are two more things that you can do to improve your latency. First, you can set the Maximum Transmittable Unit (mtu) to be lower than the default of 1500 bytes. Lowering this number will lower the average time you have to wait to send a priority packet if there is already a full-sized low-priority packet being sent. Lowering this number will also slightly decrease your throughput because each packet contains at least 40 bytes worth of IP and TCP header information. The other thing you can do to improve latency even on your low-priority traffic is to lower your queue length from the default of 100, which on an ADSL line could take as much as 10 seconds to empty with a 1500 byte mtu. 3.5. Attempting to Throttle Inbound TrafficBy using the Intermediate Queuing Device (IMQ), we can run all incoming packets through a queue in the same way that we queue outbound packets. Packet priority is much simpler in this case. Since we can only (attempt to) control inbound TCP traffic, we'll put all non-TCP traffic in the 0x00 class, and all TCP traffic in the 0x01 class. We'll also place "small" TCP packets in the 0x00 class since these are most likely ACK packets for outbound data that has already been sent. We'll set up a standard FIFO queue on the 0x00 class, and we'll set up a Random Early Drop (RED) queue on the 0x01 class. RED is better than a FIFO (tail-drop) queue at controlling TCP because it will drop packets before the queue overflows in an attempt to slow down transfers that look like they're about to get out of control. We'll also rate-limit both classes to some maximum inbound rate which is less than your true inbound speed over the ADSL modem. 3.5.1. Why Inbound Traffic Limiting isn't all That GoodWe want to limit our inbound traffic to avoid filling up the queue at the ISP, which can sometimes buffer as much as 5 seconds worth of data. The problem is that currently the only way to limit inbound TCP traffic is to drop perfectly good packets. These packets have already taking up some share of bandwidth on the ADSL modem only to be dropped by the Linux box in an effort to slow down future packets. These dropped packets will eventually be retransmitted consuming more bandwidth. When we limit traffic, we are limiting the rate of packets which we will accept into our network. Since the actual inbound data rate is somewhere above this because of the packets we drop, we'll actually have to limit our downstream to much lower than the actual rate of the ADSL modem in order to assure low latency. In practice I had to limit my 1.5mbit/s downstream ADSL to 700kbit/sec in order to keep the latency acceptable with 5 concurrent downloads. The more TCP sessions you have, the more bandwidth you'll waste with dropped packets, and the lower you'll have to set your limit rate. A much better way to control inbound TCP traffic would be TCP window manipulation, but as of this writing there exists no (free) implementation of it for Linux (that I know of...). 4. ImplementationNow with all of the explanation out of the way it's time to implement bandwidth management with Linux. 4.1. CaveatsLimiting the actual rate of data sent to the DSL modem is not as simple as it may seem. Most DSL modems are really just ethernet bridges that bridge data back and forth between your linux box and the gateway at your ISP. Most DSL modems use ATM as a link layer to send data. ATM sends data in cells that are always 53 bytes long. 5 of these bytes are header information, leaving 48 bytes available for data. Even if you are sending 1 byte of data, an entire 53 bytes of bandwidth are consumed sent since ATM cells are always 53 bytes long. This means that if you are sending a typical TCP ACK packet which consists of 0 bytes data + 20 bytes TCP header + 20 bytes IP header + 18 bytes Ethernet header. In actuality, even though the ethernet packet you are sending has only 40 bytes of payload (TCP and IP header), the minimum payload for an Ethernet packet is 46 bytes of data, so the remaining 6 bytes are padded with nulls. This means that the actual length of the Ethernet packet plus header is 18 + 46 = 64 bytes. In order to send 64 bytes over ATM, you have to send two ATM cells which consume 106 bytes of bandwidth. This means for every TCP ACK packet, you're wasting 42 bytes of bandwidth. This would be okay if Linux accounted for the encapsulation that the DSL modem uses, but instead, Linux only accounts the TCP header, IP header, and 14 bytes of the MAC address (Linux doesn't count the 4 bytes CRC since this is handled at the hardware level). Linux doesn't count the minimum Ethernet packet size of 46 bytes, nor does it take into account the fixed ATM cell size. What all of this means is that you'll have to limit your outbound bandwidth to somewhat less than your true capacity (until we can figure out a packet scheduler that can account for the various types of encapsulation being used). You may find that you've figured out a good number to limit your bandwidth to, but then you download a big file and the latency starts to shoot up over 3 seconds. This is most likely because the bandwidth those small ACK packets consume is being miscalculated by Linux. I have been working on a solution to this problem for a few months and have almost settled on a solution that I will soon release to the public for further testing. The solution involves using a user-space queue instead of linux's QoS to rate-limit packets. I've basically implemented a simple HTB queue using linux user-space queues. This solution (so far) has been able to regulate outbound traffic SO WELL that even during a massive bulk download (several streams) and bulk upload (gnutella, several streams) the latency PEAKS at 400ms over my nominal no-traffic latency of about 15ms. For more information on this QoS method, subscribe to the email list for updates or check back on updates to this HOWTO. 4.2. Script: myshaperThe following is a listing of the script which I use to control bandwidth on my Linux router. It uses several of the concepts covered in the document. Outbound traffic is placed into one of 7 queues depending on type. Inbound traffic is placed into two queues with TCP packets being dropped first (lowest priority) if the inbound data is over-rate. The rates given in this script seem to work OK for my setup but your results may vary.
5. Testing the New QueueThe easiest way to test your new setup is to saturate the upstream with low-priority traffic. This depends how you have your priorities set up. For the sake of example, let's say you've placed telnet traffic and ping traffic at a higher priority (lower fwmark) than other high ports (that are used for FTP transfers, etc). If you initiate an FTP upload to saturate upstream bandwidth, you should only notice your ping times to the gateway (on the other side of the DSL line) increasing by a small amount compared to what it would increase to with no priority queuing. Ping times under 100ms are typical depending on how you've got things set up. Ping times greater than one or two seconds probably mean that things aren't working right. 6. OK It Works!! Now What?Now that you've successfully started to manage your bandwidth, you should start thinking of ways to use it. After all, you're probably paying for it!
7. Related Links
| ||||||||||||||||||||||||||||||||||||||