Managing Internet Bandwidth: The LEARN Experience

Managing Internet Bandwidth: The LEARN Experience

Gihan V. Dias <gihan@learn.ac.lk>
Lanka Education and Research Network

Abstract

Internet access is often constrained by the cost of international (and sometimes local) bandwidth.

A number of techniques may be used to attack this problem, but we have found that (1) They do not currently provide the level of control and flexibility we require, and (2) are not very effective when the majority of traffic is for web (including ftp) access.

Therefore, we have enhanced the "Squid" cache software to provide bandwidth management. While this does not deal with non-web (e.g. audio and video) traffic, currently we use QoS on our routers to handle these, and use the web cache to manage the web traffic.

We used several techniques: Caching, to avoid repeated fetching of data; Traffic Shifting, comprising off-line downloading and mirroring, to shift traffic to night-time, and Bandwidth Allocation, to assign bandwidth to units and user groups.

Dynamic Delay Pools were implemented which allow us to share the available bandwidth in an equitable fashion without unduly limiting users.

Offline Downloading allows large file downloads to be performed in off-peak hours.

Using these methods, we have been successful in providing a better service to users, by reducing non-critical usage during peak times. We plan to improve the system by introducing credit-based web access.

Introduction

The Lanka Education and Research Network (LEARN) provides Internet access to the universities and other institutes in Sri Lanka. Our mandate is to provide the best possible service within budgetary and other constraints. As an many other countries, Internet access is constrained by the cost of international (and sometimes local) bandwidth. Although the speeds of LANs and the Internet backbone are in the order of a Gb/s, the high cost of international bandwidth often means that dozens of users share 64kb/s of bandwidth. The result is that all the users are frustrated, and much of the bandwidth is wasted. Providing enough bandwidth to satisfy all users is financially infeasible, so we approached the problem from the angle that bandwidth is a fixed resource, which should be managed to yield the maximum benefit. Some consider that the cost of bandwidth is dropping rapidly, therefore this problem will only be temporary. However, we observe that although the cost of bandwidth has reduced, at the same time, the demand for bandwidth has increased. The net result has remained an insufficiency of bandwidth, and can be expected to be so in the future[1]. As the majority of our (incoming) traffic is for web access (for this paper, we consider ftp to be part of the web), we concentrated on management of web traffic at the application layer (and above). We used several techniques to manage our bandwidth: Caching, to avoid repeated fetching of data; Traffic Shifting, comprising off-line downloading and mirroring, to shift traffic to night-time, and Bandwidth Allocation, to assign bandwidth to units and user groups. We used off-the-shelf software (principally the Squid caching system) modified as needed. Review of previous work

QoS

The objective of much work on Quality of Service (QoS) is to provide desired levels of throughput, delay, etc. in the face of unreliable networks and congestion. While this is congruent with our objectives, QoS systems operate only in real-time, in response to the traffic. They do not generally attempt to manage traffic over a longer term. Also, QoS systems normally operate in an environment where the total bandwidth requirement of high-priority traffic is less than the available bandwidth. If high-priority traffic approaches or exceeds the available bandwith, performance degrades rapidly. In our environment, however, the offered traffic load is often several times the available bandwidth. For the above reasons, we did not pursue a QoS based approach, although there is no reason why QoS should not be used in conjunction with our system to support real-time traffic, etc.

Mirroring

Mirroring places copies of large, frequently accessed files close to the end-user. It is widely used to replicate ftp sites, and, in more sophisticated forms, to distribute web content. It reduces bandwidth usage by providing local access to these files, and by performing mirroring during off-peak hours. One of the main problems with mirroring is that the end-user must specifically request the file from the closest site. If he does not, due to laziness or ignorance, the item will not be fetched from the correct mirror site. More sophisticated schemes, based on using a web browser as an ftp client, and URL re-writing in a proxy, can be used to get around these shortcomings. however, we did not investigate these approaches in detail.

Caching

Web caching[2] is the storage of recently accessed pages locally, and delivery of subsequent requests for pages from the local cache rather than the original web site. The prime objective of caching is to improve user response time, but it also reduces the load on the long-distance links. Caching is widely used on the Web, and can provide bandwidth savings of up to 40%. A hierarchy of caches may be used to increase the effective cache size and thus improve the hit rate. Push caching attempts to place content in a cache before it is requested, either by looking at other caches, or by predicting usage. Some of these techniques are discussed in [3].

Compression

Link compression can provide up to 4:1 increase in effective bandwidth for compressible data such as HTML files. However, much of the volume of web content comprises pre-compressed files such as images, audio and compressed data. Therefore we do not believe that compression will provide us with a marked advantage. Also, none of the service providers available offered compression as a service. Therefore we did not investigate this topic further.

Content Limitation

The range of accessible content may be restricted in several ways: (1) by limiting the sites accessible to a limited list, (2) by preventing access to sites on a "stop list", or (3) by restricting access based on file type, size, or needed bandwidth. The first method would be useful for providing material for a course. The second would not be appropriate in a university setting. The third is incorporated into our system both explicitly and implicitly, as described below.

Our Approach

For our system, we examined user activities and encouraged users towards bandwidth-conserving behaviour. We also categorised users based on their bandwidth requirements. Users' activities span a range of volume and interactivity. By studying the characteristics of web sites, we observed that most sites containing large, multimedia content had low academic significance (e.g., "adult" sites). Most technical sites, on the other hand, were low on graphics, and had more textual content which took time to read. We concluded that a small average bandwidth (of the order of 1 kByte/s) was sufficient to provide access to a large percentage of useful websites. However, we noted that some useful websites required larger amounts of bandwidth to use effectively. File downloading, in almost all cases, is not time-critical. A delay of 1 hour in downloading a file is only a minor inconvenience. With a little forward planning, almost all file downloads could be scheduled overnight. Therefore file downloads, defined as accessing large files (say over 100kB), may be given low priority. For each category of users, we allocated an amount of bandwidth during peak hours. during off-peak hours, when sufficient bandwidth is available, uers should be able to use as much bandwidth as they need. We also encouraged file downloading at night, by providing a user-friendly interface to schedule downloads. Since this system is only for web (including ftp) access, we implemented it as part of a web proxy. By using a transparent proxy, users are automatically served by the proxy for all web access. We chose the squid[4] cache server, a popular, powerful, open source software as the base of our system. Many of the features we required were configured directly in Squid, and others were implemented by modifying the software.

Bandwidth Allocation

The LEARN network consists of approx. 10 sites. At the beginning of 2000, these shared just 256kb/s of bandwidth. Most sites ran their own cache servers, and LEARN ran a central cache which acted as parent to the other caches, and also acted as a transparent proxy to ensure that all web accesses used the cache.

Delay Pools

Squid's delay pools feature[5] was configured to allocate bandwidths to each site. As cache hits fall outside this allocation, sites effectively receive a bonus when accessing popular pages. This method benefited smaller sites, which did not exceed their allocation, and thus obtained fast access times. The load offered by larger sites, on the other hand, exceeded their bandwidth allocation, thus resulting in their traffic being delayed. This method was adopted as it was considered equitable. It was observed that a significant proportion of the traffic comprised file downloads. If these were eliminated or reduced, the performance of interactive web access would improve. Our primary strategy for downloads was to encourage off-line downloading (described below), and restrict downloading during peak hours. Accordingly, we configured the delay-pools (initially at U. Moratuwa) to allocate bandwidth per-user (i.e., IP address). After some experimentation an average bandwidth of 1 kB/s was decided on. This was found to be acceptable (though by no means ideal) for most sites. However, waiting for a page to download at this speed was p-a-i-n-f-u-l-l-y s-l-o-w. Therefore, the pool size (which specifies how much data can be accessed before bandwidth limitation is enforced) was set to allow a "reasonable" page to be accessed quickly. After experimentation, this value was set to 90kB, which allows approx. two average web pages to be viewed without delay. File downloads, on the other hand, are quickly limited to 1kB/s. It was noted that the parent-children cache configuration, although recommnded by Squid, resulted in significantly more delay than a single cache. Therefore, we modified the cache configuration so that each site-cache accessed the Internet directly, but used Squid's cache digest feature to check if a file was available in another cache, and if so, to obtain it from there.

Dynamic Delay Pools

One of the major limitations of Squid's delay-pools implementation (and the other bandwidth allocation methods we examined) was that even if a user accesses the web at night, when the overall usage is minimal, he only receives the allocated bandwidth. Therefore, the system is inefficient, and users have no incentive to use the system during off-peak hours. Therefore, we modified Squid to allocate delay pools dynamically. Each cache is allocated an overall bandwidth, and the bandwith allocation of each user and user group is dynamically varied to keep the overall usage near the overall allocation. During low-usage periods, each user gets an essentially unlimited bandwidth. With this feature, we can provide much better access speeds to off-peak users, who are thus encouraged to use the system during off-peak times for high-volume appications.

User Groups

In the initial implementation, all users had equal status. However, LEARN's requirement was for lecturers and researchers to have good performance, while undergraduates need not have the same performance. Also, some universities, faculties, and research groups were willing to pay for more performance, while others were not. Our modified Squid provides for multiple user (i.e., IP address) groups to be defined, and for each group to be assigned a per-user bandwidth and a per-group bandwith. Users within a group are allocated any unused bandwidth for that group, and unused overall bandwidth is allocated to groups which require it. Currently, only two groups are defined: general users, who are allocated 1kb/s, and researchers, who are allocated 3kb/s. With 3kb/s we find that most web sites can be accessed with no delaying.

Traffic Shifting

Although mirroring is a popular method of traffic shifting, we have not yet implemented any major mirrors in LEARN, though we plan to do so. We implemented an off-line downloading mechanism[6] to encourage users to download files during off-peak hours.

Off-line Downloading

Our off-line downloading system was implemented using Squid as a re-director. Users accessing ftp: URLs are served by our program, which presents them with a directory listing in which each file has two links, one for normal downloading, and the other for off-line downloading. If the off-line link is selected, the specified file is queued for later download, and the user notified by e-mail when the download is complete. The system keeps a cache of recently downloaded files, and retrieves such files immediately when requested again. The download queue is sorted by file size. Therefore, small files are downloaded first. As a some bandwidth is allocated to this system even during peak hours, users requsting small files may receive them within minutes, sometimes even faster than an on-line download.

Evaluation and Future Work

Providing Internet services with limited bandwidth is a thankless task. Despite a many-fold increase in bandwidth, demand continues to outstrip supply, and users continue to complain that the Internet is slow. However, one dept. which said that "Internet is so slow we never use it" then acknowledeged they get good performance on week-ends. The bandwidth limit for general users, although low, provides a better overall performance than in a free-for-all situation, as it prevents a few aggressive users from using much of the bandwidth. However, it was found that some users were using multiple workstations to perform downloads in parallel. The limit for researchers is equivalent to an anlaog modem connection, and even pages containing large graphics were viewable at an acceptable rate. The off-line downloading system had only a limited deployment, and did not become very popular. We plan to re-launch this service once the necessary resources are available. As one cannot make a silk purse from a sow's ear, one must have sufficient bandwidth to provide an acceptable service even using bandwidth management techniques. When large numbers of users access the Internet, the bandwidth needs to increase proportionately. The other alternative is to limit the number of stations with Internet access. Then, while not everyone can access the net at a given time, those who do so will get acceptable performance. We plan to improve the dynamic delay pools system to be based on user-id instead of IP address, and to allow users to request the bandwidth they need, based on a credit system. We also plan to provide for bandwidth reservations, for lab classes, videoconferencing, etc. The development of a system where a number of caches, other bandwidth users, and routers can negotiate their bandwidth requirements with each other using a protocol such as RSVP is also being examined.

Acknowledgments

I wish to acknowledge all those at LEARN and the University of Moratuwa who assisted in this work, and provided ideas and feed-back, and especially Sidath Bandara who implemented the off-line downloading system and Chamara Gunaratne who implemented the dynamic delay pools.

References

1. M.S.D. Fernando et.al., "Multimedia Message Distribution in a Constrained Environment," Proc. INET '95, Internet Society, 1995.

2. Jim Gettys, Tim Berners-Lee and Henrik Frystyk Nielsen, "Replication and Caching Position Statement," World-Wide Web Consortium, http://www.w3.org/Propagation/Activity

3. Gihan V. Dias, Graham Cope and Ravi Wijayaratne "A Smart Internet Caching System," Proc. INET '96, Internet Society, 1996.

4. The Squid Web Poxy Cache, http://www.squid-cache.org/

5. David Luyer, "Delay Pools," Squid Frequently Asked Questions, http://www.
squid-cache.org/Doc/FAQ/FAQ.html

6. Sidath Bandara and Gihan Dias, "A Smart Cache for a Central Off-line Download System," Proc. 5th Research for Industry Symposium, University of Moratuwa, 1999.