Lightweight Policing and Charging for Packet Networks

1. Introduction

2. Assumptions & definitions

3. Principles and architecture

3.1 Charging granularity

3.2 The direction of value flow

3.3 Charging system topology

Fig 3.1 - Zero bits for charging

• pricing levels
• data reporting frequency and granularity
• audit of the revenue flow

3.4 Pricing

3.4.2 Price control. We propose that price control should operate in two scopes: i) a base price for each class of service typically applied to a whole provider domain and varying over fairly long timescales, much as prices vary today; and ii) an optional premium on this price for congestion avoidance (see next section). How base prices are set is outside the scope of this paper. However, we expect continuing automation of today's price setting processes, with inputs based on network load monitoring, routing alternatives; resource availability in lower classes of service; new capacity costs and lead-times; the competitive position; and commercial strategy. Base prices would be disseminated electronically, as described in the previous section.
        It is also possible that each tariff for each class of service for each direction could be further subdivided by various ranges of local and remote address. Thus, if there were spare capacity in just one region of a network, it might be possible to offer lower prices to customers based on the combination of their address and the remote address of any flow. These combinations would be the ones known to route through the lightly loaded region. We do not believe distance based pricing is very likely, but it is possible within the present architecture. Tariffs can include weightings to be applied to the standard price for combinations of source and destination address prefix lists.

3.4.3 Congestion avoidance pricing. Above, we suggest how to control price either for whole domains or, if necessary, for regions within a domain. However, our price dissemination mechanism is not scalable enough to control the congestion of any queue on any interface on any router in the Internet. Because data is bursty, such congestion can appear and disappear in different queues fairly rapidly. This would require a price announcement from every queue and some way of targeting these announcements just to those edge-systems transmitting through that queue at that time. Worse, we really want to charge for ignoring congestion back-off protocols, rather than charge for innocent use of a path that becomes congested. Even if price announcements could be targeted, we wish to allow each provider commercial freedom. This would include the freedom to absorb peaks and troughs in prices from neighbouring providers in order to present simpler pricing to neighbouring customers. In such scenarios, congestion prices for whole network regions would become lost in the noise.
        Instead, the mechanism we suggest is to use existing congestion signalling, which effectively creates a signalling channel from any point of congestion to the end-systems using it. Various schemes exist or are proposed for the Internet, which avoid a congestion avalanche by highlighting the packets that are causing the congestion. This can either be done implicitly by dropping them (as detected by TCP and RTCP [RFC1889]) or explicitly, e.g. using the explicit congestion notification (ECN) bits [Floyd94] proposed for diff-serv. All these methods require the co-operation of the receiver to notify the sender of congestion through an end-to-end protocol.
        We could require all these congestion signalling protocols to be changed to make the marks on the packets represent a shadow price [Kelly98]. Instead, we can try to keep the protocols as they are and re-introduce the commercial freedom given by edge-pricing. We do this by including congestion signalling as one of the parameters pre-programmed to drive the active tariff. That is, by assuming a competitive market, we can allow providers to each map this shadow price to their own real market price. Thus, congestion can still be signalled in a standard way, but it can refer to charging information indirectly. This is again in compliance with the principle of keeping transmission and charging infrastructures separate. Backbone providers would charge their neighbours heavy penalties for congestion being ignored. In turn their neighbours would probably translate these into heavy penalties for end customers if they ignored congestion. However, other neighbours might choose to exercise their freedom and offer fixed prices while translating upstream price increases into denials of access to their customers rather than price changes.
        As one might expect, before a router signals the need for congestion avoidance, the network should: i) attempt to re-route around the congestion; ii) borrow capacity from 'lower' classes of service; and/or iii) introduce or at least request extra capacity (possibly automatically). Further, we are not suggesting that the provider should always avoid congestion using price. It may be that it is decided (possibly through a rule-based system) that more revenue can be gained by allowing the network to fill and denying service to subsequent requests. Thus, even if congestion onset is signalled, we allow the network provider to control how strongly (and even whether) congestion signals cause a price rise, by multicast 'tuning' of everyone's active tariffs. Also note that the level of overprovisioning determines how often congestion avoidance pricing is required. It could be arranged to occur as infrequently as 'equipment engaged tone' does in the PSTN.
        We must also repeat that we can use the hierarchy of service classes to advantage because they can borrow capacity from each other. We can manage the load on each logical service class with price because we can always grow the size of each logical class (as long as there is sufficient best effort buffer at the bottom). It is only the best effort level that needs to have the ability to deny service - and it already does that by dropping packets. We should be clear that we are talking about congestion avoidance in a logical class of service. This scheme is unlikely to make sense for congestion control with best effort traffic. Thus we assume the onset of congestion is signalled before any packets have to be dropped. A logical service class that is approaching capacity could start penalising end-systems that didn't back off at the first sign of congestion, completely under the autonomous control of the active tariff. This would be particularly appropriate where a logical service class was designed for applications that couldn't tolerate much (or any) packet drop - the reason ECN was proposed in the first place. Using active tariffs also avoids any need for an avalanche of price rise signalling.
        Kelly has already shown congestion pricing can be stable if everyone is using the same algorithm. However, making congestion control dependent on such unpredictable factors as customer sensitivity to real market prices and provider profit motive could be dangerous for total network stability. More work is required to find if there is a class of algorithms that simultaneously allow commercial freedom but still exhibit stability in reasonable scenarios.
        A more practical problem is that the direction of congestion signalling, whether implicit or explicit, is typically towards the receiver. The receiver is then trusted to reflect this information back to the sender. The receiver has an interest in the sender not backing off, therefore, it may be necessary to charge the receiver if she ignores congestion, giving an incentive to reflect the network's signals correctly. To allow heterogeneity, we cannot assume the remote ISP will operate congestion charging, but we can assume it has an incentive to reduce congestion, which is all that is necessary. For instance, the remote ISP might instead, choose to run spot checks to ensure that its receivers are complying with end-to-end congestion control protocols. Finally, we propose charging the sender of the original data flow on the basis of incoming congestion signalling (from the original receiver) if it is necessary to encourage correct congestion behaviour.
        For TCP and RTCP it is necessary to bury into the transport layer header of the returning packets to measure the original sender's liability for charges. If the transport layer is encrypted, this presents a nasty 'layering interaction'. However, it gives the receiver an incentive not to encrypt congestion feedback, which is unnecessary for security anyway. Therefore, either explicit or implicit congestion signalling can be measured, whether at the edge-router or at the end-system, and therefore form the basis of charging.
        We have ensured the incentives are correct for non-co-operating sets of senders and receivers. Before any host chooses to ignore congestion back-off requirements and instead pay the price, the following steps are available to more co-operative sets of customers:

1. the end-systems should consider setting QoS requirements to a 'higher' class (if cheaper than the fine for ignoring congestion at the current class)
2. the end-systems should decide it is essential to ignore the congestion, given the fine for doing so might be quite high
3. both (all) end-systems should agree to ignore the congestion

3.4.4 Optimistic access control. Typically, three per-packet operations are added to routing and forwarding to create a multi-service packet network: classification, policing and scheduling. Of these, classification and policing involve look-ups into tables of potentially dynamic state. These tables can become large, requiring a few levels of look-up hierarchy, each of which takes resource. Further, state introduces complexity in keeping it current, keeping it in the right place and garbage collecting the resources it uses when it is finished with. Soft state is often used to alleviate these problems. However, as routes change, keeping route dependent state on the correct router introduces further complexity.
        As far as classification is concerned, diff-serv has already taken the step of confining the number of possible classifications to a small non-dynamic table, thereby making classification and scheduling simple and independent of flow state. However, in all known multi-service network proposals, each packet cannot be forwarded until it has been checked against policing policies - 'pessimistic access control' [Linington98]. Examples are token bucket policing against RSVP flowspecs or diff-serv SLAs [Clark95]. The flow cannot continue in parallel to the policing process because the only punishment available is to hurt the packet in question. This is a particular problem in connectionless networks where any one packet cannot necessarily be related to a later packet. Novel, ultra-fast forwarding techniques will give little benefit if policing becomes the major component of latency (Amdahl's Law [Ware72]).

Fig 3.2 - Admission control at source

In contrast, because metering is passive, we can use 'optimistic access control' where packets are allowed through without checking, but customers know they will have to answer for whatever they do. The optimistic model can only exist within some wider pessimistic context. A charging system offers just such a context. For instance, a customer may only be given an Internet account after revealing her verifiable identity, or paying a deposit. Once past this pessimistic hurdle, optimistic access to more specific parts of the service can be allowed, protected only by a punishment (respectively legal action or docking the deposit) if payment doesn't match metered activity. Metering is passive because it can proceed on the memory copy of the header, in parallel to the flow of the service. Therefore latency is always kept low in this optimistic model. Thus, the combination of an optimistic within a pessimistic model needs just a single blocking test. The effect of this single test can persist for months or even years.
        Through adding a dynamic price mechanism, we can ensure that those people least willing to use a service at a certain price deny themselves access. The provider is then freed from having to fend off flash crowds with an avalanche of admission control signalling  (Fig 3.2a) or the complexity of RSVP blockade state. With the tariff pre-loaded into the customer machine, we can even avoid any 'raise price' signalling at the time of congestion (Fig 3.2b-c). Thus, potentially, we have even moved both admission control and policing to the customer machine.

3.5 Metering, accounting and payment

• service usage is metered, M, where it is also aggregated under simple rules arbitrated by the meter controller, MC
• accounting, Act, consolidates results from possibly a number of meters and deals with hard storage and customer identity
• rating, Ra, is where prices are applied to the usage data to calculate charges.
• ultimately payment, Pa, of the calculated charges will be required

Fig 3.3 - Metering, accounting and payment architecture

External control (not shown) of each side of these systems is primarily by the contract, particularly the tariff, which determines what to measure, what and how often to report, and current pricing. An agent of the customer or provider respectively arbitrates this control. Control is typically implemented by caching a policy in the relevant object, whilst listening for policy update events. Feedback to complete the control loop is shown flowing from bulk measurement on the provider side ('bulk' means queue lengths etc. rather than individual flows).
        We use the term reconciliation to cover the 'pay-and-display' model and traditional billing. In both cases, the aim is agreement over the level of usage. The most efficient level to reconcile customer and provider is after prices have been applied, as shown. Both sides may wish to police reconciliation, with failure to reconcile triggering some defensive action. In the case of the provider this is shown as ceasing access, but less drastic measures may precede this. Payment is also policed by the provider - it is no use agreeing on the amount owing then not checking the amount paid. Rather than expect total accuracy in reconciliation, the system would be designed to ensure discrepancies due to system problems were as likely to be positive as negative. Arbitrary packet loss from flows in either direction between the two meters clearly makes this impossible. Therefore the two meters should ideally sit on either end of the same link. If link layer error correction is in use, metering should occur after correction. Metering should be as low as possible in the stack to avoid any contention for resources within the stack due to packets with different QoS classes. Ultimately, as long as packet losses were low, both parties could write them off by widening their tolerance to reconciliation discrepancies. This introduces a security flaw, as either side can try to probe the limits of the other's tolerance. Marginally higher prices for everyone would have to cover these potential losses - similar to the cost of pilfering, spillage and spoilage in the retail trades.
        Next we discuss who is considered liable for charges. We assert that network metering should only be concerned with apportioning use of the network service to various network addresses. The identity service, I, in Fig 3.3 is responsible for the mapping between network address and real world identities. This is another example of the principle of separation between network and charging. Address allocations themselves need to be 'metered' and 'usage data' sent to the accounting function to be consolidated with the network usage-data for each address (shown as dotted arrows). Examples of address allocation schemes are dynamic host configuration protocol (DCHP), network address translators (NATs), mobile cell hand-off and multicast address allocations, joins and leaves. A many to one mapping between addresses and identities must be assumed. For instance, one customer becomes liable for reception charges for any traffic to a multicast address group as soon as the join to the group from her machine is measured (in this case it is the link address in the join request that is relevant).
        Finally, it is architecturally imperative that accounting and payment are treated totally separately. The process of reconciling the account with the provider proceeds in two stages: first it is agreed which usage occurred, then which usage the customer is liable to pay for. That is, the local customer's account should always include all the usage data for both sent and received traffic, whoever might pay for it. Account reconciliation can occur on a completely different schedule to payment and with any arbitrary other party.
        Because the architecture we have described applies all the principles given, it will charge correctly even in the most demanding scenario. However, in inter-domain scenarios it will only be efficient by using the 'split edge-pricing' model. For instance, Briscoe works through an example scenario with inter-domain multicast and heterogeneous QoS per receiver [Briscoea99]. That example also shows how different apportionments of charges between senders and receivers can be achieved for multicast, again by dealing separately with such issues - end-to-end rather than along the same path as the data.

3.6 Charging inter-operation

3.6.2 Inter-provider. So far, it may have been assumed that all scenarios only applied to edge providers and customers. However, only the previous section, on inter-operation with higher layers, is specifically about end systems. The rest of the architecture is just as applicable to an inter-provider relationship. Briscoe [Briscoea99] shows how any two ISPs have a customer-provider relationship, depending only on the sign of the difference between the 'half' prices that they charge each other. We propose that all the principles described above apply equally to this relationship - the architecture is recursive. For pricing, tariffs would be announced from each provider to its neighbours. Each provider could base its prices on the costs it was receiving from its neighbours, combined with its own commercial objectives. (Even if the edge-pricing model weren't used, non-neighbouring providers could still receive these price announcements.) We should clarify that, while the architecture is recursive, it may not be appropriate to use identical technology inter-provider. We can use multicast and Java between relatively centralised systems managing loading and pricing for whole network domains. However, alternative, fully distributed mechanisms are the subject of continuing research.
        For accounting reconciliation, each pair of neighbours could either both measure or, for efficiency, agree only one need measure - then the other need only sample. In fact this is similar to the standardised model for international carrier accounting in the PSTN [ITU_D.150]. Here, both parties measure everything but the payment is based on the payer's data. Unlike the PSTN though, as long as payments are normalised end-to-end first (as recommended earlier) the choice of factors to measure at any inter-provider boundary is local to that pair of providers. Thus, even if edge-provider to edge-customer charging is at packet granularity, charging between the same edge-provider and a peer-provider could be by average link utilisation per service class.
        Recursion also applies for corporate customers, where there may be a need to apportion costs between departments. The accounting reports would first be reconciled between end-systems and departmental accounting systems. Then departments would aggregate and reconcile with corporate and provider systems. The model can even be applied recursively to multi-user machines. Each user simply runs an accounting object that reports to the machine's accounting object. Intra-machine accounting would be based on addressing above the network layer as already discussed under Assumptions. In all these recursive models, the detailed accounting within one system can either be encapsulated from the broader system or revealed if the commercial relationship requires it. If there is any shortfall between the total of all the details and the total the provider expects, that is the responsibility of the party at that level to underwrite.
        This neatly brings us to the final issue to resolve in this paper: "What about failure to deliver the specified service?" With an end-to-end service, it can be very costly to apportion blame when things go awry. If the customer has paid for reliability, who should give the refund if a packet is dropped? If latency is guaranteed, who gives the refund if some network has used too much of the delay budget? Briscoe [Briscoea99] proposes a pragmatic principle for these circumstances. If a customer disputes payment and their local provider accepts their case (or can't be bothered to argue) all providers on the end-to-end path share the same fate, losing the associated revenue, or at least not bothering to account for the refund between themselves. This is akin to peering between ISPs today, but need only be applied to the exceptional cases of failure. Hence this is termed 'exception peering'. Just as with peering, occaisional audit would be necessary to ensure gains and losses were within acceptable tolerance of each other.

4. Early results

Other than producing the architecture summarised here, we have also implemented example prototypes of the system components described above, primarily in Java. These include the provider and customer ends of the tariff dissemination mechanism and a generic accounting system for either providers or customers with remote control capabilities. These are described in Rizzo et al and Tassel et al [Rizzo99, Tassel99].

Fig 4.1 - Demonstration of dynamic tariff dissemination and pricing

Implementation proves that the architectural separation is clean, as there is minimal necessity for standardisation. We implement active tariffs in Java, the most complex one to date being 8kB on the wire. The receiver end includes a modified class loader to switch to new tariff objects on the fly. Remote method calls are turned into objects for dissemination then back into calls once received. The incoming object currently undergoes rudimentary checks: for a trusted code signature and to check conformance with the expected interface by introspecting the class of the object. We have also built a component for integrating local charging into any Java application. It requires only a minor edit to the relevant socket calls, being based on Tassel et al [TasselBri97].

Fig 4.2 - Policy control of price adaptation agent demo

 The whole charging system currently consumes 1.6MB of storage on the customer device, including 875kB for a stripped NeTraMeT [Brownlee97], which we use for metering that complies broadly with the real-time flow measurement (RTFM) architecture  [RFC2063]. We are about to start more scientific experiments, but initial indications show that the charging system consumes about 3% of CPU time on a 400MHz Pentium II for moderate traffic loads. Because the code is intended as a flexible research testbed, no attempt at streamlining has been made. This might reduce storage and system load further, particularly where single purpose Internet devices are concerned.

5. Limitations and further work

• Dispersal of software critical to an ISP's revenue flow into an unreliable installation environment. Although we can fall back to traditional billing, our scalability benefits rely on this fall back not being needed too often. This should be less of a problem with single purpose devices than general-purpose computers.
• Customer acceptance of foreign code installing and running itself on their systems. We have implemented rudimentary checks described above, but further work is required to allay customer security fears.
• Resource allocation purely by price could lead to bursty hogging. The laws of economics should protect us against the static effects of hogging [Clark95] - the hogs will pay for the capacity they hog, leaving the remainder for the rest of us. However, heavily bursty traffic from relatively few price insensitive customers may cause a disproportionate need for over-capacity.
• Demand management by price could fail if deterrents like penalties or credit blacklisting suddenly became too weak, e.g. due to crisis events. Rather than remove admission control from the network, it may be advisory to leave a vestigial 'defence in depth' to be turned on in emergencies.
• Meter discrepancies between customer and provider. This becomes a problem with lossy access link technologies.
• Lack of experience of dynamic pricing behaviour of customers and providers [Edell99]. Experiments are needed where risk aversity is distinguished from the nuisance of dynamic pricing. Also futures pricing of communications is a sparsely researched topic.

6. Conclusions

Acknowledgements: Pete Bagnall, David Freestone, Ben Strulo, Trevor Burbridge, Jake Hill, Tony Reeder, Steve Rudkin, Sarom Ing, Ian Marshall, Alan O'Neill, Maff Holladay, Phil Flavin, James Cochrane, (BT); Jon Crowcroft (UCL)

References