Gregory R. Ruth <email@example.com>
GTE Laboratories Inc.
Usage accounting is urgently needed to support network management and cost recovery for the Internet of the future. The Internet has become a worldwide commercial enterprise serving millions. The new user base demands consistently high-quality service and reliability, and their applications impose strenuous service requirements. The very service architecture itself is changing, introducing new levels. These developments create substantial requirements for Internet traffic accounting. This paper summarizes the driving forces for Internet accounting, assesses progress to date, and recommends future research and development.
Keywords: Internet accounting, network management, cost recovery, resource allocation, network analysis, Integrated Services Architecture.
In the past decade the Internet has evolved from a modest government-sponsored research network to a worldwide commercial enterprise serving millions. The number of Internet users and user networks, the aggregate traffic volume, and data transfer speeds have all grown exponentially for years. The expanded user base expects a consistently high quality of service and reliability, even as its applications make increasing demands on network performance. Integrated services architecture (ISA) defines new classes of service for distinguished packet streams. These fundamental changes in the Internet give rise to new economic and technical requirements that can only be met by implementing comprehensive traffic measurement.
Initially, the Internet appeared to be "free" to its users. It was funded by government grants and academic research budgets. Local costs were often buried in corporate and organizational facilities budgets. But in recent years the Internet has grown too large and diverse to be supported by hidden subsidies. The U.S. National Science Foundation no longer underwrites backbone costs. In order to maintain growth and performance, service provision had to be transferred to for-profit Internet service providers (ISPs). The Internet has become a business.
Today, ISPs levy access charges for Internet use. Full-time connectors are charged a flat monthly rate according to the speed of the access line. Part-time users are charged a fixed monthly fee or by the minute, or a combination of both. These cost recovery schemes are easy to implement, but they fail to reflect the actual cost of providing Internet service, thus producing discrepancies between revenues and costs that put ISPs at risk.
A comprehensive inter-carrier settlement structure (like that used among telephone companies) does not exist on the Internet. Financial arrangements among directly connected ISPs are purely ad hoc; ISPs negotiate bilateral agreements with one another as they see fit. Pairs of backbone ISPs generally have peering agreements by which they agree to carry one another's traffic at no cost. Smaller, more local ISPs typically pay to connect to larger ones with wider coverage. Such inter-ISP payments are simply fixed monthly amounts and not based on actual traffic volumes.
The Internet has undergone several other fundamental changes in recent years. The most readily apparent is its exponential growth: in the number of users, the number of hosts/servers (end systems), the number of networks/autonomous systems, the number of service providers, and the volume of traffic.
New service paradigms have emerged. Historically, most Internet traffic was due to electronic mail, file transfer, and remote login (Telnet). Throughput and delay requirements were modest. By contrast, the most popular applications of today's Internet--Web surfing, real-time multimedia (audio/video/image), multicast, and electronic commerce--impose far more demanding requirements.
Additionally, the integrated services architecture will introduce new classes of service into the Internet. Today's Internet is engineered to provide best-effort delivery of packets; the ISA will add two premium service classes: guaranteed (bandwidth and delay) service and controlled load service. In order to provide these services, the Internet of the future will have to allocate resources for distinguished traffic flows. A resource reservation for premium service must be agreed on by each node in the flow's path and will be governed by local policy.
Internet usage accounting is often connected with recovering the aggregate cost of providing service through usage-based end-user charges and inter-ISP settlements. But there are other equally important motivations for traffic measurement. It is indispensable for managing and allocating network resources, especially in connection with the implementation of service discrimination (the ISA). Traffic analysis, both for operational and capacity planning purposes, requires usage accounting at various levels of detail. These drivers are discussed in the following paragraphs.
As the Internet is no longer a subsidized research experiment, but rather an interlocking combination of business ventures that must support themselves, it is necessary for each ISP to recover its costs by levying a schedule of charges on its users.
Prices that are out of line with costs do not long endure in free markets. Demand for overpriced service will dry up and demand for underpriced service will increase until it is impossible to meet the demand at the artificially low price (witness the recent AOL debacle in the U.S.) Markets in the real world are seldom perfect (or even nearly so), so price correction does not occur instantaneously. Furthermore, external constraints (e.g., government regulation) can support pricing anomalies, but sooner or later either the direct users abuse the underpriced service or middlemen (arbitrageurs), highly motivated by financial reward, find a way to skirt constraints and make money by buying cheap and selling dear.
In today's Internet pricing is based on access. But access pricing has very little correlation with the actual cost of providing the service. That is because the Internet architecture is designed to take advantage of the statistical probability that at any given time only a very small fraction of the total access capacity will be used. Telephone network design takes advantage of such statistical sharing, too. These networks are not engineered to handle the (extremely unlikely) eventuality of every network user wanting to place a call simultaneously, but only to support the highest reasonably expected peak call volumes. Internet technology takes this a step further. Whereas telephone networks take advantage of traffic statistics at the very coarse level of each individual phone call, the technology of the Internet applies statistical multiplexing at the level of the individual packet and is thus able to realize far greater economies.
However, any engineering design based on statistical improbability carries with it a certain likelihood that the worst-case expectation will be exceeded. With a network that has thousands of routers and a complex topology, temporary localized overloads resulting from a random accumulation of higher-than-expected traffic are frequent. (Of course nonrandom causes such as imperfect network design, backhoe fade, or social phenomena may play a part, as well.) A great deal of Internet technology has been invented to deal with traffic control. For example, routing algorithms conspire to route traffic around jams and TCP implementations throttle back their offered load when the network begins to lose packets. But overloads still occur. These overloads are termed "congestion."
Although Internet performance (throughput, delay, packet loss, etc.) degrades gracefully with increasing congestion, it suffers nonetheless. Moreover, in certain cases, the dynamics of Internet protocols and applications can cause untreated congestion to escalate. Finally, it is not easy to fix congestion in real time by adding capacity. Therefore, it is desirable to prevent needless congestion and control and remedy it when it occurs. This is done by pushing back on the senders. One way to do that is through negative performance (as when one's phone call busies out and one hangs up and tries again a few minutes later.) A fairer and more socially beneficial form of back pressure is usage pricing.
Taken to their logical limit, usage prices would become spot prices for particular transport services, for example, this millisecond's price for transmitting a kilobyte of traffic from A to B, as determined by supply and demand (i.e., free-market auction.) This model (with simplifying assumptions!) has been investigated  and shown to maximize the overall social benefit to the user community. However, it would be extremely impractical to calculate and apply such spot prices in real time. Further research  broadens the concept of pricing pushback to usage-constraining fees. Instead of using precisely tuned prices to optimize aggregate Internet performance, the idea is to use appropriate usage pricing to encourage responsible, efficient use of the Internet.
Because of the proliferation of service providers on the Internet today, each with its own particular cost-recovery requirements and marketing strategy, uniform pricing architecture is unlikely to emerge. Therefore, an accounting architecture that is flexible enough to admit a wide range of cost-recovery schemes is called for.
Even if the existing bilateral agreements persist, ISPs will likely want to measure traffic between one another to check whether the expected volumes are in line with the assumptions on which their agreements are based. Ultimately, though, when integrated services appear, inter-ISP settlements will become inevitable because differential service pricing will be necessary between ISPs (as for end users). Thus, it will be necessary to measure and distinguish traffic volumes according to service classes.
The primary resource offered on the Internet is data transfer. This resource is neither cheap nor limitless. The usage-constraining fees discussed above effectively allocate resources so that the Internet will operate efficiently. But there may be objectives beyond efficiency of operation, such as temporal load balancing (encouraging a shift of traffic from peak periods to off-peak periods) and discouraging antisocial behavior (e.g., greedy TCP implementations or spamming). Usage accounting can be used with pricing differentials (discounts and surcharges) to promote these goals. It has also been proposed  that direct, immediate feedback (in place of or in addition to end-of-the-month usage charges) of resource consumption to end systems, so that users and their applications can adjust their behavior as appropriate, would be even more effective in promoting efficient use the network.
The advent of ISA presents additional resource requirements. In the original, egalitarian, one-service-class-fits-all Internet, resources were allocated uniformly among all users. Service discrimination requires queuing disciplines within network nodes to ensure that flows with reservations for premium services receive the promised service. Included in the ISA is the specification of an offered-traffic profile (the "Tspec") as part of the resource reservation. Preferred service is given only to those packets that conform to the Tspec. Enforcement requires measurement of the rate and volume of the flow.
It has been shown  that service discrimination will not work properly without corresponding pricing discrimination. This is hardly surprising, since if all services cost exactly the same, more users will request the best service than the system can accommodate. Thus, the implementation of ISA will require a differential pricing scheme (and corresponding accounting) where flows that receive better service will pay more.
Local policy (implemented in the local policy module [LPM] of a network node) determines which reservation requests for premium services are honored. Besides the question of capacity availability, this decision may be based on the identity of the requester and the status of his account with his service provider. If the ISP allocates premium services by selling monthly allotments (e.g., 100 kilopackets of controlled load service) the LPM will have to keep track of how much of that allotment has been used up. If the ISP simply prices premium services by total usage (e.g., $ 0.05 per kilopacket of controlled service without limit), the LPM has to count premium service packets for each user to bill him or her at the end of the month.
Traditionally, network analysis has focused on the operation of a single organization's network. Thus, it was common simply to watch the utilizations of nodes and links. If certain thresholds were consistently exceeded, capacity was added incrementally. Periodically, the network topology was redesigned to fit the current load. But, as Braun and Claffy have observed , in the context of today's enormous and complex Internet such simple measurements and adjustments are inadequate to maintain network performance. ISPs need to cooperate to make mutually beneficial design and operational decisions. The two-level IGP/BGP routing hierarchy is no longer adequate to ensure balanced traffic load over expensive links. Today's "traffic engineering" requires static routing based on careful analysis of traffic flows and resource consumption. To achieve this depth of understanding accurate traffic measurements are needed.
Enterprise networks, too, will want to understand the traffic they interchange with their service providers in more detail than mere link utilization offers in order to make better decisions about controlling traffic within their own networks and about interconnecting to the outside.
Additionally, both end users and neighbor ISPs will want to establish service level agreements with their service providers. All of this will require some traffic accounting. In most cases sampling will be sufficient; in some cases total packet accounting will be necessary.
The requirements for a usage accounting system are varied and conflicting. They may be summarized as follows.
Internet users view usage accounting from the perspective of the usage-based cost recovery system and local policy enforcement it can support. They want these to be accurate and fair. They want usage-based cost recovery to be simple so that their costs are easy to understand, predict and control.
From the viewpoint of the service providers and the Internet as a whole, the accounting system should be robust, scaleable, and relatively simple. It should have low impact on the performance of network service both in terms of added traffic and processing overhead by network elements. It should support usage-based cost recovery and inter-ISP settlements, which means it must be secure and produce accurate and complete accounting. It should support resource allocation in general and ISA in particular. It must support a wide variety of network management activities including performance measurement, fault isolation, resource allocation, local policy implementation, traffic engineering, and network planning. These functions require that the accounting system be able to measure traffic at granularities varying from very coarse (e.g., AS-to-AS traffic matrices) to very fine (e.g., at the level of individuals and applications). It must able to distinguish among traffic carried at different service levels. And the ability to estimate volumes by sampling techniques will be desirable in some cases.
The chief organization for the development of Internet standards is the Internet Engineering Task Force (IETF). Taking input from all segments of the Internet community - users, researchers, service providers and vendors - it has made a good start on the problem of Internet accounting.
A great deal of work has been done in collecting and analyzing Internet operation statistics in recent years. Among the most notable are the efforts of Claffy, Braun, et al. at the National Laboratory for Applied Network Research , the Routing Arbiter project (Merit and USC/ISI), and the Internet Performance Measurement and Analysis (IPMA) project (Merit and the University of Michigan). These have contributed substantially to the definition of Internet accounting requirements and issues and continue to pave the way for standards development.
The IETF has several working groups (WGs) attacking the Internet accounting problem from different approaches. In the Operation Requirements Area the Real-Time Traffic Flow Measurement (RTFM) Working Group has defined an architecture  and mechanisms - including an SNMP MIB  - for traffic measurement and collection. Based on the WG's draft specifications two independent implementations of the traffic measurement system have been produced and are in use in operational networks today.
Related work is going on in the Benchmarking Methodology WG. The IP provider metrics (IPPM) effort there is defining metrics for the performance of networks and associated methodologies for measuring them.
Another relevant development is taking place in the Transport Area's RSVP (Resource ReSerVation Protocol) WG. This working group is designing a signaling protocol for reserving premium Internet services according to the Integrated Services Architecture, including the notions of the traffic flow that is to receive the special service, and its corresponding traffic specification (Tspec), which describes the traffic profile for that flow. An adjunct to this work is the development of specifications for local policy modules for controlling resource allocation. Both Tspecs and LPMs will present requirements for traffic measurement.
The RTFM architecture for traffic flow measurement makes use of three elements: the traffic meters, which perform the actual traffic measurements; meter readers, which reliably and securely collect usage data from meters; and the accounting system manager, which configures meters and controls meter readers. Additional components process the measurement data for specific applications. Applications for cost recovery would include pricing systems, billing systems, and payment systems. Other applications are resource management, performance analysis, and capacity planning.
Each meter is placed at a point of interest in the Internet to measure the traffic through that point. The traffic flowing through a meter is partitioned into a set of streams or "flows" by a rule set configured in the meter. A flow is a logical abstraction defined by one or both endpoints (source and destination) and by its duration (measurement start and stop times). Thus, for example, one flow could be defined as "all packets originating at IP address 126.96.36.199 and destined for IP address 188.8.131.52." Another flow may be defined as "all packets originating at 184.108.40.206," without specifying where they are being sent. The endpoints of a flow may be specified in finer or coarser detail ("granularity") as the occasion demands. That is, an endpoint may be (ranging from finest to coarsest) an IP address with a TCP port number, an IP address with a protocol identifier, just an IP address, an address prefix (indicating a network), or even a MAC layer address (indicating a router port if the meter is instrumented within a router.) For example, it is possible to define a flow that consists of "all packets going from network 132.197 to network 132.196" or another consisting of "all packets entering port 1 of my router and exiting port 5 of the router."
This flexibility allows the same traffic measurement mechanism to be applied to many of the uses described above: individual usage accounting for cost accounting, inter-ISP settlements, network analysis, etc. It does not, however, support the distinction of flows by service class, which will be necessary to implement differential pricing. This capability will require communication with the flow classifier element of the ISA .
The RTFM architecture as currently defined measures the total number of packets or bytes within a traffic flow. It does not, however, support traffic sampling. Extending the types of quantities a meter may measure beyond simple volume (e.g., flow throughput, packet interarrival time histograms) is the subject of ongoing development in the RTFM WG.
The design and placement of meters raise important issues. Meters are most easily instrumented within network switching nodes (e.g., routers) because these devices already process packet headers. Such placement inevitably affects the performance of the switching nodes, though. Alternatively, meters can be instrumented as stand-alone devices in line with the network links. However, to minimize impact on network performance, meters should be instrumented in parallel with communications paths rather than in series with them. This can easily be accomplished in broadcast subnetworks (e.g., Ethernets) but is more difficult in nonbroadcast networks (e.g., SONET). MCI has pioneered in this area with its OC3MON device, which uses an optical splitter to observe traffic on a fiber without interrupting the flow.
Another issue in meter design is the amount of processing performed by the meter itself versus the amount done by applications off-line. The meter could perform minimal processing and transfer raw data to the collector. However, it is better to process traffic data closest to the point of measurement (in the meter) in order to reduce the amount of data that must be transmitted over the network. This also offloads processing from the applications. The RTFM working group has taken this latter position and is developing mechanisms that enable the meter to identify, sort, collate, and process data as they are collected.
There are a number of challenging problems in Internet traffic accounting that have not yet been solved.
There is a need to define and implement a traffic accounting system for the Internet. This system must be able to support not only cost recovery and carrier settlements, but resource management and network analysis functions as well. Traffic accounting MIBs and record formats must be standardized. The model of the RTFM working group can serve as a starting point. It should be extended to support measurement of a wider range of traffic statistics, include a facility for sampling, and support service class distinction for flows.
The growth in multicast traffic and the advent of IPv6 and Mobile IP will present special challenges for Internet traffic accounting, indicating a need for further research.
Facilities for the application of cost recovery ancillary systems to track customer accounts, provide billing services, and allow (possibly real-time) payment over the network must be developed.
 R. Braden, D. Clark, S. Shenker, "Integrated Services in the Internet Architecture: an Overview," RFC 1633, June 1994.
 H-W. Braun, K. Claffy, "Network Analysis Issues for a Public Internet," in B. Kahin and J. Keller (eds.), "Public Access to the Internet," MIT Press, Cambridge, Mass., 1995.
 N. Brownlee, C. Mills, G. Ruth, "Traffic Flow Measurement: Architecture," RFC 2063, January 1997.
 N. Brownlee, "Traffic Flow Measurement: Meter MIB," RFC 2064, January 1997.
 K. Claffy, H-W. Braun, G. Polyzos, "A Parameterizable Methodology for Internet Traffic Flow Profiling," IEEE Journal on Selected Areas in Communications, Vol. 13, No. 8, October 1995.
 R. Cocchi, S. Shenker, D. Estrin, L. Zhang, "Pricing in Computer Networks: Motivation, Formulation and Example," IEEE/ACM Transactions on Networking, Vol. 1, No. 6, December 1993.
 D. Estrin, L. Zhang, "Design Considerations for Usage Accounting and Feedback in Internetworks," ACM Computer Communications Review, 1990, Vol. 20, No. 5.
 S. Herzog, D. Estrin, "Sharing the Cost of Multicast Trees: An Axiomatic Analysis," Computer Communications Review, Vol. 25, No. 4, October 1995.
 D. Hirsh, C. Mills, G. Ruth, "Internet Accounting: Background," RFC 1272, November 1991.
 J. MacKie-Mason, H. Varian, "Pricing the Internet," in B. Kahin and J. Keller (eds.), "Public Access to the Internet," MIT Press, Cambridge, Mass., 1995.
 S. Shenker, D. Clark, D. Estrin, S. Herzog, "Pricing in Computer Networks: Reshaping the Research Agenda," Telecommunications Policy, Vol. 20., No. 3, April 1996.