Transport Area Working Group B. Briscoe Internet-Draft BT & UCL Expires: August 31, 2006 February 27, 2006 Emulating Border Flow Policing using Re-ECN on Bulk Data draft-briscoe-tsvwg-re-ecn-border-cheat-00 Status of this Memo By submitting this Internet-Draft, each author represents that any applicable patent or other IPR claims of which he or she is aware have been or will be disclosed, and any of which he or she becomes aware will be disclosed, in accordance with Section 6 of BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet- Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt. The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. This Internet-Draft will expire on August 31, 2006. Copyright Notice Copyright (C) The Internet Society (2006). Abstract Scaling per flow admission control to the Internet is a hard problem. A recently proposed approach combines Diffserv and pre-congestion notification (PCN) to provide a service slightly better than Intserv controlled load. It scales to networks of any size, but only if domains trust each other to comply with admission control and rate policing. This memo claims to solve this trust problem without losing scalability. It describes bulk border policing that emulates per-flow policing with the help of another recently proposed extension to ECN, involving re-echoing ECN feedback (re-ECN). With Briscoe Expires August 31, 2006 [Page 1] Internet-Draft Bulk Border Policing using Re-ECN February 2006 only passive, bulk measurements at borders, sanctions can be applied against cheating networks. Status (to be removed by the RFC Editor) This memo is posted as an Internet-Draft with the intent to eventually progress to informational status. It is envisaged that the necessary standards actions to realise the system described would sit in three other documents currently being discussed (but not on the standards track) in the IETF Transport Area [Re-TCP], [RSVP-ECN] & [PCN]. The authors seek comments from the Internet community on whether combining PCN and re-ECN is a sufficient solution to the admission control problem. Briscoe Expires August 31, 2006 [Page 2] Internet-Draft Bulk Border Policing using Re-ECN February 2006 Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Requirements Notation . . . . . . . . . . . . . . . . . . . . 5 3. The Problem . . . . . . . . . . . . . . . . . . . . . . . . . 5 3.1. The Traditional Per-flow Policing Problem . . . . . . . . 5 3.2. Generic Scenario . . . . . . . . . . . . . . . . . . . . . 7 4. Re-ECN Protocol for an RSVP Transport . . . . . . . . . . . . 9 4.1. Protocol Overview . . . . . . . . . . . . . . . . . . . . 9 4.2. Re-ECN Abstracted Network Layer Wire Protocol (IPv4 or v6) . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 4.3. Protocol Operation . . . . . . . . . . . . . . . . . . . . 13 4.4. Aggregate Bootstrap . . . . . . . . . . . . . . . . . . . 15 4.5. Flow Bootstrap . . . . . . . . . . . . . . . . . . . . . . 16 5. Emulating Border Policing with Re-ECN . . . . . . . . . . . . 17 5.1. Policing Overview . . . . . . . . . . . . . . . . . . . . 18 5.2. Pre-requisite Contractual Arrangements . . . . . . . . . . 21 5.3. Emulation of Per-Flow Rate Policing: Rationale and Limits . . . . . . . . . . . . . . . . . . . . . . . . . . 23 5.4. Policing Dishonest Marking . . . . . . . . . . . . . . . . 24 5.5. Competitive Routing . . . . . . . . . . . . . . . . . . . 25 5.6. Fail-safes . . . . . . . . . . . . . . . . . . . . . . . . 26 6. Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 7. Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . 29 8. Design Choices and Rationale . . . . . . . . . . . . . . . . . 29 9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 30 10. Security Considerations . . . . . . . . . . . . . . . . . . . 30 11. Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . 31 12. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 31 13. Comments Solicited . . . . . . . . . . . . . . . . . . . . . . 31 14. References . . . . . . . . . . . . . . . . . . . . . . . . . . 31 14.1. Normative References . . . . . . . . . . . . . . . . . . . 31 14.2. Informative References . . . . . . . . . . . . . . . . . . 32 Appendix A. Implementation . . . . . . . . . . . . . . . . . . . 33 A.1. Ingress Gateway Algorithm for Blanking the RE bit . . . . 33 A.2. Bulk Downstream Congestion Metering Algorithm . . . . . . 34 A.3. Algorithm for Sanctioning Negative Traffic . . . . . . . . 35 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 36 Intellectual Property and Copyright Statements . . . . . . . . . . 37 Briscoe Expires August 31, 2006 [Page 3] Internet-Draft Bulk Border Policing using Re-ECN February 2006 1. Introduction The Internet community largely lost interest in the Intserv architecture after it was clarified that it would be unlikely to scale to the whole Internet [RFC2208]. Although Intserv mechanisms proved impractical, the services it aimed to offer are still very much required. A recently proposed approach [CL-arch] combines Diffserv and pre- congestion notification (PCN) to provide a service slightly better than Intserv controlled load [RFC2211]. It scales to any size network, but only if domains trust each other to comply with admission control and rate policing. This memo describes border policing measures to sanction networks that cheat each other. The approach provides a sufficient emulation of flow rate policing at trust boundaries but without per-flow processing. The emulation is not perfect, but it is sufficient to ensure that the punishment is at least proportionate to the severity of the cheat. The aim is to be able to claim that controlled load service can scale to any number of endpoints, even though such scaling must take account of the increasing numbers of networks and users who may all have conflicting interests. To achieve such scaling, this memo combines two recent proposals, both of which it briefly recaps: o A framework for admission control over Diffserv using pre- congestion notification [CL-arch] describes how bulk pre- congestion notification on routers within an edge-to-edge Diffserv region can emulate the precision of per-flow admission control to provide controlled load service without unscalable per-flow processing; o Re-ECN: Adding Accountability to TCP/IP [Re-TCP]. The trick that addresses cheating at borders is to recognise that border policing is mainly necessary because cheating upstream networks will admit traffic when they shouldn't only as long as they don't directly experience the downstream congestion their misbehaviour can cause. The re-ECN protocol ensures upstream nodes honestly declare expected downstream congestion in all forwarded packets, which we then use to emulate border policing. Rather than the end-to-end arrangement used when re-ECN was specified for the TCP transport [Re-TCP], this memo specifies re-ECN in an edge-to-edge arrangement, making it applicable to the Diffserv admission control scenario in the framework. Also, rather than using a TCP transport for regular congestion feedback, this memo specifies re-ECN using RSVP as the transport. We use the proposed minor extension of RSVP that allows it to carry congestion feedback [RSVP- Briscoe Expires August 31, 2006 [Page 4] Internet-Draft Bulk Border Policing using Re-ECN February 2006 ECN], which is much less frequent but more precise than TCP. Of course, network operators may choose to process per-flow signalling at their borders for their own reasons, such as per-flow accounting. But the goal of this document is to show that per-flow processing at borders is no longer necessary in order to provide end- to-end QoS using flow admission control. To be clear, we are absolutely opposed to standardisation of technology that embeds particular business models into the Internet. Our aim here is to provide a new metric (downstream congestion) at trust boundaries. Given the well-known significance of congestion in economics, operators can then use this new metric in their interconnection contracts if they choose. This will enable competitive evolution of new business models (for examples see [IXQoS]), alongside more traditional models that depend on more costly per-flow processing at borders. We specify this protocol solution in detail in Section 4, after specifying the inter-domain policing problem more precisely and briefly recapping the framework for providing admission control using pre-congestion notification in Section 3. Having described the solution, this memo continues as follows: {ToDo: } 2. Requirements Notation The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC2119]. 3. The Problem 3.1. The Traditional Per-flow Policing Problem If we claim to be able to emulate per-flow policing with bulk policing at trust boundaries, we need to know exactly what we are emulating. So, even though we expect it to become a historic practice, we will start from the traditional scenario with per-flow policing at trust boundaries to explain why it has always been considered necessary. To be able to take advantage of a reservation-based service such as controlled load, a source must reserve resources using a signalling protocol such as RSVP [RFC2205]. But, even if the source is authorised and admitted at the flow level, it cannot necessarily be Briscoe Expires August 31, 2006 [Page 5] Internet-Draft Bulk Border Policing using Re-ECN February 2006 trusted to send packets within the rate profile it requested. For instance, without data rate policing, a source could reserve resources for an 8kbps audio flow but transmit a 6Mbps video (theft of service). More subtly, the sender could generate bursts that were outside the profile it had requested. In traditional architectures, per-flow packet rate-policing is expensive and unscalable but, without it, a network is vulnerable to such theft of service (whether malicious or accidental). Perhaps more importantly, if flows are allowed to send more data than they were permitted, the ability of admission control to give assurances to other flows will break. A signalled request refers to a flow of packets by its flow ID tuple (filter spec [RFC2205]) (or its security parameter index (SPI)& nbsp[RFC2207] if port numbers are hidden by IPsec encryption). But merely opening a pin-hole for packets that match an admitted flow ID is an insufficient policing mechanism. The packet rate must also be policed to keep the flow within the requested flow spec [RFC2205]. Just as sources need not be trusted to keep within their requested flow spec, whole networks might also try to cheat. We will now set up a concrete scenario to illustrate such cheats. Imagine reservations for unidirectional flows from senders, through at least two networks, an edge network and its downstream transit provider. Imagine the edge network charges its retail customers per reservation but also has to pay its transit provider a charge per reservation. Typically, both its selling and buying charges might depend on the duration and rate of each reservation. The level of the actual selling and buying prices are irrelevant to our discussion (most likely the network will sell at a higher price than it buys, of course). A cheating ingress network could systematically reduce the size of its retail customers' reservation signalling requests before forwarding them to its transit provider (and systematically reinstate the responses on the way back). It would then receive an honest income from its upstream retail customer but only pay for fraudulently smaller reservations downstream. Equivalently, a cheating ingress network may feed the traffic from a number of flows into an aggregate reservation over the transit that is smaller than the total of all the flows. Because of these fraud possibilities, in traditional QoS reservation architectures the downstream network polices at each border. The policer checks that the actual sent data rate of each flow is within the signalled reservation. Reservation signalling could be authenticated end to end, but this wouldn't prevent the aggregation cheat just described. For this Briscoe Expires August 31, 2006 [Page 6] Internet-Draft Bulk Border Policing using Re-ECN February 2006 reason, and to avoid the need for a global PKI, signalling integrity is typically only protected on a hop-by-hop basis  [RFC2747]. A variant of the above cheat is where a router in an honest downstream network denies admission to a new reservation, but a cheating upstream network still admits the flow. For instance, the networks may be using Diffserv internally, but Intserv admission control at their borders [RFC2998]. The cheat would only work if they were using bulk Diffserv traffic policing at their borders, perhaps to avoid the cost/complexity of Intserv border policing. As far as the cheating upstream network is concerned, it gets the revenue from the reservation, but it doesn't have to pay any downstream wholesale charges and the congestion is in someone else's network. The cheating network may calculate that most of the flows affected by congestion in the downstream network aren't likely to be its own. It may also calculate that the downstream router is probably not actually congested, but rather it is denying admission to new flows to protect bandwidth assigned to other lower priority services. To summarise, in traditional reservation signalling architectures, if a network cannot trust a neighbouring upstream network to rate-police each reservation, it has to check for itself that the data fits within each of the reservations it has admitted. 3.2. Generic Scenario We will now describe a generic internetworking scenario that we will use to describe and to test our bulk policing proposal. It consists of a number of networks and endpoints that do not fully trust each other to behave. In Section 6 we will tie down exactly what we mean by partial trust, and we will consider the various combinations where some networks do not trust each other and others are colluding together. Briscoe Expires August 31, 2006 [Page 7] Internet-Draft Bulk Border Policing using Re-ECN February 2006 _ ___ _____________________________________ ___ _ | | | | _|__ ______ ______ ______ _|__ | | | | | | | | | | | | | | | | | | | | | | | | | | | | |Inter-| |Inter-| |Inter-| | | | | | | | | | | | | | ior | | ior | | ior | | | | | | | | | | | | | |Domain| |Domain| |Domain| | | | | | | | | | | | | | A | | B | | C | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +----+ +-+ +-+ +-+ +-+ +-+ +-+ +----+ | | | | | | | | | | |B| |B| |B| |B| |B| |B| | | | | | | | |==| |==|Ingr|==|R| |R|==|R| |R|==|R| |R|==|Egr |==| |==| | | | | | |G/W | | | | | | | | | | | | | |G/W | | | | | | | | | +----+ +-+ +-+ +-+ +-+ +-+ +-+ +----+ | | | | | | | | | | | | | | | | | | | | | | | | | | |____| |______| |______| |______| |____| | | | | |_| |___| |_____________________________________| |___| |_| Sx Ingress Diffserv region Egress Rx End Access Access End Host Network Network Host <-------- edge-to-edge signalling -------> (for admission control) <-------------------end-to-end QoS signalling protocol-------------> Figure 1: Generic Scenario (see text for explanation of terms) An ingress and egress gateway (Ingr G/W and Egr G/W in Figure 1) connect the interior Diffserv region to the edge access networks where routers (not shown) use per-flow reservation processing. Within the Diffserv region are three interior domains, A, B and C, as well as the inward facing interfaces of the ingress and egress gateways. An ingress and egress border router (BR) is shown interconnecting each interior domain with the next. There may be other interior routers (not shown) within each interior domain. In two paragraphs we now briefly recap how pre-congestion notification is intended to be used to control flow admission to a large Diffserv region. The first paragraph describes data plane functions and the second describes signalling in the control plane. We omit many details from [CL-arch] including behaviour during routing changes. For brevity here we assume other flows are already in progress across a path through the Diffserv region before a new one arrives, but how bootstrap works is described in Section 4.4. Figure 1 shows a single simplex reserved flow from the sending (Sx) end host to the receiving (Rx) end host. The ingress gateway polices incoming traffic within its admitted reservation and remarks it to Briscoe Expires August 31, 2006 [Page 8] Internet-Draft Bulk Border Policing using Re-ECN February 2006 turn on an ECN-capable codepoint [RFC3168] and the controlled load (CL) Diffserv codepoint. Together, these codepoints define which traffic is entitled to the enhanced scheduling of the CL behaviour aggregate on routers within the Diffserv region. The CL PHB of interior routers consists of a scheduling behaviour and a new ECN marking behaviour that we call 'pre-congestion notification' [PCN]. The CL PHB simply re-uses the definition of expedited forwarding (EF) [RFC3246] for its scheduling behaviour. But it incorporates a new ECN marking behaviour, which sets the ECN field of an increasing number of CL packets to the admission marked (AM) codepoint as they approach a threshold rate that is lower than the line rate. The use of virtual queues ensures real queues have hardly built up any congestion delay. The level of marking detected at the egress of the Diffserv region, is then used by the signalling system in order to determine admission control. The end-to-end QoS signalling (e.g. RSVP) for a new reservation takes one giant hop from ingress to egress gateway, because interior routers within the Diffserv region are configured to ignore RSVP. The egress gateway holds flow state because it takes part in the end-to-end reservation. So it can classify all packets by flow and it can identify all flows that have the same previous RSVP hop (a CL-region-aggregate). For each CL-region-aggregate of flows in progress, the egress gateway maintains a per-packet moving average of the fraction of pre-congestion-marked traffic. Once an RSVP PATH message for a new reservation has hopped across the Diffserv region and reached the destination, an RSVP RESV message is returned. As the RESV message passes, the egress gateway piggy-backs the relevant pre-congestion level onto it [RSVP-ECN]. Again, interior routers ignore the RSVP message, but the ingress gateway strips off the pre-congestion level. If the pre-congestion level is above a threshold, the ingress gateway denies admission to the new reservation, otherwise it returns the original RESV signal back towards the data sender. Once a reservation is admitted, its traffic will always receive low delay service for the duration of the reservation. This is because ingress gateways ensure that traffic not under a reservation cannot pass into the Diffserv region with the CL DSCP set. So non-reserved traffic will always be treated with a lower priority PHB at each interior router. 4. Re-ECN Protocol for an RSVP Transport 4.1. Protocol Overview First we need to recap the way routers accumulate congestion marking Briscoe Expires August 31, 2006 [Page 9] Internet-Draft Bulk Border Policing using Re-ECN February 2006 along a path. Each ECN-capable router marks some packets with CE, the marking probability increasing with the length of the virtual queue at its egress link [PCN]. With multiple ECN-capable routers on a path, the ECN field accumulates the fraction of CE marking that each router adds. The combined effect of the packet marking of all the routers along the path signals congestion of the whole path to the receiver. So, for example, if one router early in a path is marking 1% of packets and another later in a path is marking 2%, flows that pass through both routers will experience approximately 3% marking. The packets crossing an inter-domain trust boundary within the Diffserv region will all have come from different ingress gateways and will all be destined for different egress gateways. We will show that the key to policing against theft of service is to be able to measure expected downstream pre-congestion on the paths between a border router and the egress gateways that packets are headed for. With the original ECN protocol, if CE markings crossing the border had been counted over a period, they would have represented the accumulated upstream pre-congestion that had already been experienced by those packets. The general idea of re-ECN is for the ingress gateway to continuously encode path congestion into the IP header, where path means from ingress to egress gateway. Then at any point on that path (e.g. between domains A & B in Figure 2 below), IP headers can be monitored to subtract upstream congestion from expected path congestion in order to give the expected downstream congestion still to be experienced until the egress gateway. Briscoe Expires August 31, 2006 [Page 10] Internet-Draft Bulk Border Policing using Re-ECN February 2006 _____________________________________ _|__ ______ ______ ______ _|__ | | | A | | B | | C | | | +----+ +-+ +-+ +-+ +-+ +-+ +-+ +----+ | | |B| |B| |B| |B| |B| |B| | | |Ingr|==|R| |R|==|R| |R|==|R| |R|==|Egr | |G/W | | | | |: | | | | | | | | |G/W | +----+ +-+ +-+: +-+ +-+ +-+ +-+ +----+ | | | |: | | | | | | |____| |______|: |______| |______| |____| |_____________:_______________________| : | : | |<-upstream-->:<-expected downstream->| | congestion : congestion | | u v ~= p - u | | | |<--- expected path congestion, p --->| Figure 2: Re-ECN concept 4.2. Re-ECN Abstracted Network Layer Wire Protocol (IPv4 or v6) In this section we define the names of the various codepoints of the re-ECN protocol, deferring description of their semantics to the following sections. First we recap the re-ECN wire protocol proposed in [Re-TCP]. It uses the two bit ECN field broadly as in RFC3168 [RFC3168]. It also uses a new re-ECN extension (RE) bit. The actual position of the RE bit is different between IPv4 & v6 headers so we will use an abstraction of the IPv4 and v6 wire protocols by just calling it the RE bit. [Re-TCP] proposes using bit 48 (currently unused) in the IPv4 header for the RE bit, while it proposes an ECN extension header for IPv6. Unlike the ECN field, the RE bit is intended to be set by the sender and remain unchanged along the path, although it can be read by network elements that understand the re-ECN protocol. In the scenario used in this memo, an ingress gateway changes the setting of the RE bit, acting as a proxy for the sender, as permitted in the specification of re-ECN. Although the RE bit is a separate, single bit field, it can be read as an extension to the two-bit ECN field; the three concatenated bits in what we will call the extended ECN field (EECN) make eight codepoints available. When the RE bit setting is "don't care", we use the RFC3168 names of the ECN codepoints, but [Re-TCP] proposes the following six codepoint names for when there is a need to be more specific. Briscoe Expires August 31, 2006 [Page 11] Internet-Draft Bulk Border Policing using Re-ECN February 2006 +-------+------------+------+-------------+-------------------------+ | ECN | RFC3168 | RE | re-ECN | re-ECN meaning | | field | codepoint | bit | codepoint | | +-------+------------+------+-------------+-------------------------+ | 00 | Not-ECT | 0 | NRECT | Not re-ECN-capable | | | | | | transport | | 00 | Not-ECT | 1 | NF | No feedback | | | | | | | | 01 | ECT(1) | 0 | Re-Echo | Re-echoed congestion | | | | | | and RECT | | 01 | ECT(1) | 1 | RECT | re-ECN capable | | | | | | transport | | 10 | ECT(0) | 0 | --CU-- | Currently unused | | | | | | | | 10 | ECT(0) | 1 | --CU-- | Currently unused | | | | | | | | 11 | CE | 0 | CE(0) | Congestion experienced | | | | | | with Re-Echo | | 11 | CE | 1 | CE(-1) | Congestion experienced | +-------+------------+------+-------------+-------------------------+ Table 1: Re-cap of Default Extended ECN Codepoints Proposed for Re- ECN As permitted by RFC3168, [PCN] proposes new semantics for the ECN codepoints when combined with a Diffserv codepoint (DSCP) that uses pre-congestion notification. It also proposes various alternative encodings for these semantics, attempting to fit five states into the four available ECN codepoints by making various compromises. The five states are Not-ECT, ECT (ECN-capable transport), the ECN Nonce, Admission Marking (AM) and Pre-emption Marking (PM). One of the five states was for the ECN Nonce [RFC3540], but the capability we describe in this memo supercedes any need for the Nonce. The ECN Nonce is an elegant scheme, but it only allows a sending node (or its proxy) to detect suppression of congestion marking by a cheating receiver. Thus the Nonce requires the sender or its proxy to be trusted to respond correctly to congestion. But this is precisely the main cheat we want to protect against (as well as many others). One of the compromises that [PCN] explores ("Alternative 5") leaves out support for the ECN Nonce. Therefore we use that one. Then, with the addition of the RE bit, the 8 encodings of the extended ECN (EECN) field become those defined in the table below. Note that these codepoints only take on the semantics in the table below when combined with a Diffserv codepoint that the operator has defined as supporting pre-congestion notification. Briscoe Expires August 31, 2006 [Page 12] Internet-Draft Bulk Border Policing using Re-ECN February 2006 +--------+-----------+------+-------------+-------------------------+ | ECN | PCN | RE | re-ECN | re-ECN meaning | | field | codepoint | bit | codepoint | | +--------+-----------+------+-------------+-------------------------+ | 00 | Not-ECT | 0 | NRECT | Not re-ECN-capable | | | | | | transport | | 00 | Not-ECT | 1 | NF | No feedback | | | | | | | | 01 | ECT(1) | 0 | Re-Echo | Re-echoed congestion | | | | | | and RECT | | 01 | ECT(1) | 1 | RECT | re-ECN capable | | | | | | transport | | 10 | AM | 0 | AM(0) | Admission Marking with | | | | | | Re-Echo | | 10 | AM | 1 | AM(-1) | Admission Marking | | 11 | PM | 0 | PM(0) | Pre-emption Marking | | | | | | with Re-Echo | | 11 | PM | 1 | PM(-1) | Pre-emption Marking | +--------+-----------+------+-------------+-------------------------+ Table 2: Extended ECN Codepoints if the Diffserv codepoint uses Pre- congestion Notification (PCN) For the rest of this memo, we will not distinguish between Admission Marking and Pre-emption Marking (unless stated otherwise). We will call both "congestion marking". With the above encoding, congestion marking can be read to mean any packet with the left-most bit of the ECN field set. All but the "not re-ECN-capable transport" (NRECT) field imply the presence of an ECN-capable transport. Congested PCN-capable routers must drop rather than mark packets carrying the NRECT codepoint. Note that adding PCN-capability to a router will involve checking the RE bit as well as the ECN field and DSCP before deciding whether to drop or to mark a packet during congestion. Router implementations might well append the RE bit to their internal representation of the ECN field, treating them internally as one 3-bit extended ECN value. 4.3. Protocol Operation In this section we will give an overview of the operation of the re- ECN protocol for an RSVP transport, deferring a detailed specification to the following sections. The re-ECN protocol involves a simple tweak to the action of the gateway at the ingress edge of the CL region. In the framework just described [CL-arch], for each active traffic aggregate across the CL region (CL-region-aggregate) the ingress gateway will hold a fairly Briscoe Expires August 31, 2006 [Page 13] Internet-Draft Bulk Border Policing using Re-ECN February 2006 recent Congestion-Level-Estimate that the egress gateway will have fed back to it, piggybacked on the signalling that sets up each flow. For instance, one aggregate might have been experiencing 3% pre- congestion (that is, congestion marked octets whether Admission Marked or Pre-emption Marked). In this case, the ingress gateway MUST clear the RE bit to "0" for the same percentage of octets of CL- packets (3%) and set it to "1" in the rest (97%). Appendix A.1 gives a simple pseudo-code algorithm that the ingress gateway may use to do this. The RE bit is set and cleared this way round for incremental deployent reasons (see [Re-TCP]). To avoid confusion we will use the term `blanking' (rather than marking) when the RE bit is cleared to "0", so we will talk of the `RE blanking fraction' as the fraction of octets with the RE bit cleared to "0". ^ | | RE blanking fraction 3% | +----------------------------+====+ | | | | 2% | | | | | | congestion marking fraction| | 1% | | +----------------------+ | | | | | 0% +----+=====+---------------------------+------> ^ <--A---> <---B---> <---C---> ^ domain | ^ ^ | ingress | | egress 1.00% 2.00% marking fraction Figure 3: Example Re-ECN Codepoint Marking fractions (Imprecise) Figure 3 illustrates our example. The horizontal axis represents the index of each congestible resource (typically queues) along a path through the Internet. The two superimposed plots show the fraction of each ECN codepoint observed along this path, assuming two congested routers somewhere within domans A and C. And the table below shows the downstream pre-congestion measured at various border observation points along the path. These figures are actually reasonable approximations derived from more precise formulae given in Appendix A of [Re-TCP]. The RE bit is not changed by interior routers, so it can be seen that it acts as a reference against which the congestion marking fraction can be compared along the path. Briscoe Expires August 31, 2006 [Page 14] Internet-Draft Bulk Border Policing using Re-ECN February 2006 +--------------------------+---------------------------------------+ | Border observation point | Approximate Downstream pre-congestion | +--------------------------+---------------------------------------+ | ingress -- A | 3% - 0% = 3% | | A -- B | 3% - 1% = 2% | | B -- C | 3% - 1% = 2% | | C -- egress | 3% - 3% = 0% | +--------------------------+---------------------------------------+ Note that the ingress determines the RE blanking fraction for each aggregate using the most recent feedback from the relevant egress, arriving with each new reservation, or each refresh. These arrive relatively infrequently compared to the speed with which congestion changes. Although this feedback will always be out of date, on average positive errors will cancel out negative over a sufficiently long duration. In summary, the network adds pre-congestion marking in the forward data path, the egress feeds its level back to the ingress in RSVP, then the ingress gateway re-echoes it into the forward data path by blanking the RE bit. Hence the name re-ECN. Then at any border within the Diffserv region, the pre-congestion marking that every passing packet will be expected to experience downstream can be measured to be the RE blanking fraction minus the congestion marking fraction. 4.4. Aggregate Bootstrap When a new reservation PATH message arrives at the egress, if there are currently no flows in progress from the same ingress, there will be no state maintaining the current level of pre-congestion marking for the aggregate. While the reservation signalling continues onward towards the receiving host, the egress gateway returns an RSVP message to the ingress with a flag [RSVP-ECN] asking the ingress to send a specified number of data probes between them. This bootstrap behaviour is all described in the framework [CL-arch]. However, with our new re-ECN scheme, the ingress does not know what proportion of the data probes should have the RE bit blanked, because it has no estimate yet of pre-congestion for the path across the Diffserv region. To be conservative, following the guidance for specifying other re- ECN transports in [Re-TCP], the ingress SHOULD set the NF codepoint of the extended ECN header in all probe packets (Table 2). As per the framework, the egress gateway measures the fraction of congestion-marked probe octets and feeds back the resulting pre- congestion level to the ingress, piggy-backed on the returning Briscoe Expires August 31, 2006 [Page 15] Internet-Draft Bulk Border Policing using Re-ECN February 2006 reservation response (RESV) for the new flow. Probe packets are identifiable by the egress because they have the ingress as the source and the egress as the destination in the IP header. It may seem inadvisable to expect the NF codepoint to be set on probes, given legacy firewalls etc. might discard such packets (because this flag had no prevous legitimate use). However, in the deployment scenarios envisaged for this admission control framework, each domain in the Diffserv region has to be explicitly configured to support the controlled load service. So, before deploying the service, the operator MUST reconfigure such a misbehaving middlebox to allow through packets with the RE bit set. Note that we have said SHOULD rather than MUST for the NF setting behaviour of the ingress for probe packets. This entertains the possibility of an ingress implementation having the benefit of other knowledge of the path, which it re-uses for a newly starting aggregate. For instance, it may hold cached information from a recent use of the aggregate that is still sufficiently current to be useful. It might seem pedantic worrying about these few probe packets, but this behaviour ensures the system is safe, even if the proportion of probe packets becomes large. 4.5. Flow Bootstrap It might be expected that a new flow within an active aggregate would need no special bootstrap behaviour. If there was an aggregate already in progress between the gateways the new flow was about to use, it would inherit the prevailing RE blanking fraction. And if there were no active aggregate, the aggregate bootstrap behaviour would be appropriate and sufficient for the new flow. However, for a number of reasons, at least the first packet of each new flow SHOULD be set to the NF codepoint, irrespective of whether it is joining an active aggregate or not. If the first packet is unlikely to be reliably delivered, a number of NF packets MAY be sent to increase the probability that at least one is delivered to the egress gateway. If each flow does not start with an NF packet, it will be seen later that sanctions may be incorrectly applied at the interface before the egress gateway. It will often be possible to apply sanctions at the granularity of aggregates rather than flows, but in an internetworked environment it cannot be guaranteed that aggregates will be identifiable in remote networks. So setting NF at the start of each flow is a safe strategy. For instance, a remote network may have Briscoe Expires August 31, 2006 [Page 16] Internet-Draft Bulk Border Policing using Re-ECN February 2006 equal cost multi-path (ECMP) routing enabled, causing flows between the same gateways to traverse different paths. After an idle period of more than 1 second, the ingress gateway SHOULD set the EECN field of the next packet it sends to NF. This REQUIREMENT allows the design of network policers to be deterministic. If the ingress gateway can guarantee that the network(s) that will carry the flow to its egress gateway all use a common identifier for the aggregate (e.g. a single MPLS network without ECMP routing), it MAY NOT set NF when it adds a new flow to an active aggregate and an NF packet need only be sent if a whole aggregate has been idle for more than 1 second. 5. Emulating Border Policing with Re-ECN Note: In the rest of this memo, where the context makes it clear, we will loosely use the term 'congestion' rather than using the stricter 'downstream pre-congestion'. Also we will loosely talk of positive or negative traffic, meaning traffic where the moving average of the downstream pre-congestion metric is persistently positive or negative respectively. The notion of positive and negative downstream pre-congestion is because downstream pre-congestion is calculated by subtracting the congestion marking fraction from the RE blanking fraction. Therefore packets can be considered to have a 'value multiplier' of +1, 0 or -1. Blanking the RE bit increments the 'value multiplier' of a packet. Congestion marking a packet decrements 'the value multiplier' (whether admission marking or pre-emption marking). Both together cancel each other out (a neutral or zero 'value- multiplier'). The NF codepoint is an exception. It has the same positive 'value multiplier' as a re-echoed packet. The table below specifies unambiguously the value multipliers of each extended ECN codepoint. Briscoe Expires August 31, 2006 [Page 17] Internet-Draft Bulk Border Policing using Re-ECN February 2006 +-------+------+-------------+--------------+-----------------------+ | ECN | RE | re-ECN | 'Value | re-ECN meaning | | field | bit | codepoint | multiplier' | | +-------+------+-------------+--------------+-----------------------+ | 00 | 0 | NRECT | n/a | Not re-ECN-capable | | | | | | transport | | 00 | 1 | NF | +1 | No feedback | | 01 | 0 | Re-Echo | +1 | Re-echoed congestion | | | | | | and RECT | | 01 | 1 | RECT | 0 | re-ECN capable | | | | | | transport | | 10 | 0 | AM(0) | 0 | Admission Marking | | | | | | with Re-Echo | | 10 | 1 | AM(-1) | -1 | Admission Marking | | 11 | 0 | PM(0) | 0 | Pre-emption Marking | | | | | | with Re-Echo | | 11 | 1 | PM(-1) | -1 | Pre-emption Marking | +-------+------+-------------+--------------+-----------------------+ Table 4: 'Sign' of Extended ECN Codepoints Just as we will loosely talk of positive and negative traffic when we mean the level of downstream pre-congestion in the stream of traffic, we will also talk of positive or negative packets, meaning whether a packet contributes positively or negatively to downstream pre- congestion. 5.1. Policing Overview To emulate border policing, the general idea is for each domain to apply financial penalties to its upstream neighbour in proportion to the amount of downstream pre-congestion that the upstream network sends across the border. This seems to encourage everyone to understate downstream pre-congestion to reduce the penalties they incur. But it is in the last domain's interest to create a balancing upward pressure by applying sanctions to flows where the marking fraction goes negative before the egress gateway. Of course, some domains may trust other domains to comply without applying sanctions or penalties. In these cases, no penalties need be applied. The re-ECN protocol ensures downstream pre-congestion marking is passed on correctly whether or not penalties are applied to it, so the system works just as well with a mixture of some domains trusting each other and others not. Figure 4 uses the same example as in previous sections to show the downstream pre-congestion marking fraction, v, across a path through the Internet. Downward arrows show the pressure for each domain to Briscoe Expires August 31, 2006 [Page 18] Internet-Draft Bulk Border Policing using Re-ECN February 2006 underdeclare downstream pre-congestion in traffic they pass to the next domain, because of the penalties. Note that at the last egress of the Diffserv region, domain C should not agree to pay any penalties to the egress gateway for pre-congestion passed to the egress gateway. Downstream pre-congestion to the egress gateway should have reached zero here, so if domain C agreed to pay for any downstream pre-congestion, it would give the egress gateway an incentive to overdeclare pre-congestion feedback and take the resulting profit from domain C. Providers should be free to agree the contractual terms they wish between themselves, so this memo does not propose to standardise how these penalties would be applied. It is sufficient to standardise the re-ECN protocol so the downstream pre-congestion metric is available if providers choose to use it. However, Section 5.2 gives some examples of how these penalties might be implemented. p e n a l t i e s / | \ A : : : | | <--A---> <---B---> <---C---> domain | V : : : 3% | +-----+ | | : | | | V V : 2% | | +----------------------+ : | | downstream pre-congestion | : 1% | | : | : | | : | : 0% +----+----------------------------+====+------> : : : A : : : : | : ingress : : : egress 1.00% 2.00%: pre-congestion | sanctions Figure 4: Policing Framework, showing creation of opposing pressures to underdeclare and overdeclare downstream pre-congestion, using penalties and sanctions Any traffic that persistently goes negative by the time it leaves a domain must not have been marked correctly in the first place. A domain that discovers such traffic can adopt a range of strategies to protect itself. Which strategy it uses will depend on policy, because it cannot immediately assume malice---there may be an innocent configuration error somewhere in the system. So this memo also does not propose to standardise any particular mechanism, but Section 5.4 does give examples of how the underlying re-ECN protocol Briscoe Expires August 31, 2006 [Page 19] Internet-Draft Bulk Border Policing using Re-ECN February 2006 could be used to apply sanctions to persistently negative traffic. The ultimate sanction would be to drop such negative traffic indiscriminately, without regard to flows. A less drastic sanction might be to focus drop on specific packets in specific flows to remove the negative bias while doing minimal harm. In all cases a management alarm SHOULD be raised on detecting persistently negative traffic and any automatic sanctions taken SHOULD be logged. Even if the chosen policy is to take no automatic action, the cause can then be investigated manually. The incentive for domains not to tolerate negatively marked traffic depends on financial penalties never being negative. That is, any level of negative marking only equates to zero penalty. In other words, penalties are always paid in the same direction as the data, and never against the data flow. This is consistent with the definition of physical congestion; when a resource is underutilised, it is not negatively congested, its congestion is just zero. So, although short periods of negative marking can be tolerated to correct temporary overdeclarations due to lags in the feedback system, persistent downstream negative congestion can have no physical meaning and therefore must signify a problem. The upward arrow at the egress of domain C at its border with the egress gateway in Figure 4 represents this incentive not to allow negative traffic. But the same upward pressure applies at every domain border (arrows not shown). With the above penalty system, each domain seems to have a perverse incentive to fake pre-congestion. For instance domain B's profit depends on the difference between pre-congestion at its ingress (its revenue) and at its egress (its cost). So if B overstates internal pre-congestion it seems to increase its profit. However, we can assume that domain A could bypass B, routing through other domains to reach the egress. So the competitive discipline of least-cost routing can ensure that any domain tempted to fake pre-congestion for profit risks losing all its usage revenue. The least congested route would eventually be able to win this competitive game, only as long as it didn't declare more fake pre-congestion than the next most competitive route. Again, this memo does need to standardise any particular mechanism for routing based on re-ECN. Section 5.5 explains why no new standards would be needed for congestion routing as long as re-ECN marking had been standardised. That section also points to papers concerning optimising routing in the presence of usage charging. Briscoe Expires August 31, 2006 [Page 20] Internet-Draft Bulk Border Policing using Re-ECN February 2006 5.2. Pre-requisite Contractual Arrangements The re-ECN protocol has been chosen to solve the policing problem because it embeds a downstream pre-congestion metric in passing CL traffic that is difficult to lie about and can be measured in bulk. The ability to emulate border policing depends on network operators choosing to use this metric as one of the elements in their contracts with each other. Already many inter-domain agreements involve a capacity and a usage element. The usage element may be based on volume or various measures of peak demand. We expect that those network operators that choose to use pre-congestion notification for admission control would also be willing to consider using this downstream pre-congestion metric as a usage element in their interconnection contracts for admission controlled traffic. Appendix A.2 gives a suggested algorithm for metering downstream congestion at a border router. It could hardly be simpler. It involves accumulating the volume of packets with the RE bit blanked and the volume of those with congestion marking and subtracting the two. In order to discard a persistent negative balance (see above), time is slotted into periods of say 10secs (or a time sufficient for a few rounds of feedback depending on the level of aggregation). Every timeslot, a positive balance between the two counters is accumulated into a long-term counter and reset. Whereas, if the balance during any timeslot is negative, it is discarded and a management alarm SHOULD also be raised. Over an accounting period (say a month) the single metric in the long term counter represents all the downstream congestion caused by traffic passing the border meter. Congestion has the dimension of [byte], being the product of volume transferred [byte] and percentage pre-congestion [dimensionless]. The above algorithm effectively gives a measure of the volume transferred, but modulated by pre-congestion expected downstream. So volume transferred during off-peak periods counts as nearly nothing, while volume transferred at peak times counts very highly. The re- ECN protocol allows one network to measure how much pre-congestion has been 'dumped' into it by another network. And then in turn how much of that pre-congestion it dumped into the next downstream network. Once this downstream pre-congestion metric is available, operators are free to choose how they incorporate it into their interconnection contracts [IXQoS]. Some may include a threshold volume of pre- congestion as a quality measure in their service level agreement, perhaps with a penalty clause if the upstream network exceeds this Briscoe Expires August 31, 2006 [Page 21] Internet-Draft Bulk Border Policing using Re-ECN February 2006 threshold over, say, a month. Others may agree a set of tiered monthly thresholds, with increasing penalties as each threshold is exceeded. But, it would be just as easy and more precise to do away with discrete thresholds, and instead make the penalty rise smoothly with the volume of pre-congestion by applying a price to pre- congestion itself. Then the usage element of the interconnection contract would directly relate to the volume of pre-congestion caused by the upstream network. Typically, where capacity charges are concerned, lower tier customer networks pay higher tier provider networks. So money flows from the edges to the middle of the internetwork where there is greater connectivity. But penalties or charges for usage normally follow the same direction as the data flow---the direction of control at the network layer. So, where a tier 2 provider sends data into a tier 3 customer network, we would expect the penalty clauses for sending too much pre-congestion to be against the tier 3 network, even though it is the provider. The relative direction of penalties and charges is a constant source of confusion. It may help to remember that data will be flowing in the other direction too. So the provider network has as much opportunity to levy usage penalties as its customer, and it can set the price or strength of its own penalties higher if it chooses. Usage charges in both directions tend to cancel each other out, which confirms that usage-charging is less to do with revenue raising and more to do with encouraging load control discipline in order to smooth peaks and troughs, improving utilisation and quality. To focus the discussion, from now on, unless otherwise stated, we will assume a downstream network charges its upstream neighbour in proportion to the pre-congestion it sends, B_v, using the notation of Appendix A.2. If they previously agreed the (fixed) price per byte of pre-congestion would be L, then the bill at the end of the month will simply be the product L.B_v, plus any fixed charges they may also have agreed. We are well aware that the IETF tries to avoid standardising technology that depends on a particular business model. But our aim is merely to show that border policing can at least work with this one model, then we can assume that operators might experiment with the metric in other models. Effectively tiered thresholds are just more coarse-grained approximations of the fine-grained case we choose to examine. Of course, operators are free to complement this pre- congestion-based usage element of their charges with traditional capacity charging, and we expect they will. Briscoe Expires August 31, 2006 [Page 22] Internet-Draft Bulk Border Policing using Re-ECN February 2006 5.3. Emulation of Per-Flow Rate Policing: Rationale and Limits The important feature of charging in proportion to congestion volume is that the penalty aggregates and deaggregates correctly along with packet flows. This is because the penalty rises linearly with bit rate and linearly with congestion, because it is the product of them both. So if the packets crossing a border consist of a thousand flows, and one of those flows doubles its rate, the ingress gateway forwarding that flow will have to put twice as much congestion marking into the packets of that flow. And this extra congestion marking will add proportionately to the charges levied at every border the flow crosses in proportion to the amount of pre-congestion remaining on the path. As importantly, pre-congestion itself rises super-linearly with utilisation of a particular resource. So if someone tries to push another flow into a path that is already signalling enough pre- congestion to warrant admission control, the penalty will be a lot greater than it would have been to add the same flow to a less congested path. So, the system as a whole is fairly insensitive to the actual level of pre-congestion that each ingress chooses for triggering admission control. The deterrent against exceeding whatever threshold is chosen rises very quickly with a small amount of cheating. These are the properties that allow re-ECN to emulate per-flow border policing of both rate and admission control. When a whole inter- network is operating at normal (typically very low) congestion, the pre-congestion marking from virtual queues will be a little higher--- still low, but more noticeable. But this does not imply that usage /charges/ must also be low. That depends on the /price/ L. For instance, combining capacity and volume charges is quite a common feature of interconnection agreements in today's Internet, particularly since p2p file-sharing became popular. Imagine that the monthly payment between two networks is made up of a volume charge and a capacity charge, and they usually turn out to be in a ratio of about 1:2 (not atypical). If charging for volume were replaced with charging for congested volume, one would expect the price of congestion to be arranged so that the total charge for usage remained about the same---still about one third of the total settlement. Because that is obviously the charge that the market has found is necessary to push back against usage. So, if an average pre- congestion fraction turned out to be 0.1%, one would expect that the price L per byte of pre-congestion would be about 1000 times the previously used per byte price for volume (before congestion metrics were available). Briscoe Expires August 31, 2006 [Page 23] Internet-Draft Bulk Border Policing using Re-ECN February 2006 From the above example it can be seen why operators will become acutely sensitive to the congestion they cause in other networks, which is of course the desired effect to encourage networks to /control/ the congestion they allow their users to cause to others. Effectively, usage charges will continuously flow from ingress gateways to the places where there is mild pre-congestion, in proportion to the data rates from those gateways and to the path pre- congestion. If anyone sends even one flow at higher rate, they will immediately have to pay proportionately more usage charges. Because there is no knowledge of reservations within the Diffserv region, no interior router can police whether the rate of each flow is greater than each reservation. So the system doesn't truly emulate rate-policing of each flow. But there is no incentive to pack a higher rate into a reservation, because the charges are directly proportional to rate, irrespective of the reservation. However, if virtual queues start to fill on any path, even though real queues will still be able to provide low latency service, pre- congestion marking will rise fairly quickly. It may eventually reach the threshold where the ingress gateway would deny admission to new flows. If the ingress gateway cheats and continues to admit new flows, the affected virtual queues will rapidly fill, even though the real queues will still be little worse than they were when admission control should have been invoked. The ingress gateway will have to pay the penalty for such an extremely high pre-congestion level, so the pressure to invoke admission control should become unbearable. The above mechanisms protect against rational operators. In Section 5.6 we discuss how networks can protect themselves from accidental or deliberate misconfiguration in neighbouring networks. 5.4. Policing Dishonest Marking As CL traffic leaves the last network before the egress gateway (domain C) the RE blanking fraction should match the congestion marking fraction, when averaged over a sufficiently long duration (perhaps ~10s to allow a few rounds of feedback through regular signalling of new and refreshed reservations). If domain C doesn't trust the networks around it to behave honestly, it should install a monitor at its egress. This monitor aims to detect flows of CL packets that are persistently negative. If flows are positive, domain C need take no action---this simply means an upstream network must be paying more penalties than it needs to. Appendix A.3 gives a suggested algorithm for the monitor. Briscoe Expires August 31, 2006 [Page 24] Internet-Draft Bulk Border Policing using Re-ECN February 2006 Note that the monitor operates on flows but we would like it not to require per-flow state. This is why we have been careful to ensure that all flows MUST start with a packet marked with the NF codepoint. If a flow does not start with the NF codepoint, a monitor is likely to treat it unfavourably. This incentivises setting of the NF codepoint. This also means that a monitor will be resistant to state exhaustion attacks from other networks, as the monitor never creates state unless an NF packet arrives. And an NF packet counts positive, so it will cost a lot for a network to send many of them. Monitor algorithms will often maintain an average fraction of RE blanked packets across flows. When maintaining an average across flows, a monitor MUST ignore packets with the NF codepoint set. An ingress gateway sets the NF codepoint when it does not have the benefit of feedback from the ingress. So counting packets with FE cleared would be likely to make the average unnecessarily positive, providing headroom (or should we say footroom?) for dishonest (negative) traffic. If the monitor detects a persistently negative flow, it could drop sufficient negative and neutral packets to force the flow to not be negative. This is the approach taken for the 'egress dropper' in [Re-TCP], but for the scenario in this memo, where everyone would expect everyone else to keep to the protocol it is probably more advisable to raise a management alarm. So all ingresses cannot understate downstream pre-congestion without getting logged. Then the network operator can deal with the offending network at the human level, out of band. 5.5. Competitive Routing Goldenberg et al [Smart_rtg] refers to various commercial product and presents its own algorithms for moving traffic between multihomed routes based on usage charges. None of these systems require any changes to standards protocols because the choice between the available border gateway protocol (BGP) routes is based on a combination of local knowledge of the charging regime and local measurement of traffic levels. If, as we propose, charges or penalties were based on the level of re-ECN measured in passing traffic, a similar optimisation could be achieved without requiring any changes to standard routing protocols. We must be clear that applying pre-congestion-based routing to this admission control system remains an open research issue. Traffic engineering based on congestion requires careful damping to avoid oscillations, and should not be attempted without adult supervision Briscoe Expires August 31, 2006 [Page 25] Internet-Draft Bulk Border Policing using Re-ECN February 2006 :) Mortier & Pratt [ECN-BGP] have analysed traffic engineering based on congestion. Without the benefit of re-ECN, they they had to add a path attribute to BGP to advertise a route's downstream congestion (actually they proposed that BGP should advertise the charge for congestion, which we believe wrongly embeds an assumption into BGP that congestion will be charged for). 5.6. Fail-safes The mechanisms described so far create incentives for rational operators to behave. That is, one operator aims to make another behave responsibly by applying penalties and expecting a rational response that trades off costs against benefits. It is usually reasonable to assume that other network operators behave rationally (policy routing can avoid those that might not). But this approach does not protect against the misconfigurations and accidents of other operators. Therefore, we propose the following two similar mechanisms at a network's borders to provide "defence in depth": Highly positive flows RE blanked packets should be sampled and a small regular sample picked randomly as they cross a border interface. Then subsequent packets matching the same source and destination address and DSCP should be monitored. If the RE blanking rate is well above a threshold (to be determined by operational practice), a management alarm SHOULD be raised, and the flow MAY be automatically subject to focused drop. Persistently negative flows congestion marked packets should be sampled and a small regular sample picked randomly as they cross a border interface. Then subsequent packets matching the same source and destination address and DSCP should be monitored. If the RE blanking rate minus the congestion marking rate is persistently negative, a management alarm SHOULD be raised, and the flow MAY be automatically subject to focused drop. Both these mechanisms rely on the fact that highly postive (or negative) flows will appear more quickly in the sample by selecting randomly solely from positive (or negative) packets. Note that there is no assumption that users behave rationally. The system is protected from the vagiaries of irrational user behaviour by the ingress gateways, which transform internal penalties into a deterministic, admission control mechanism that prevents users from misbehaving, by directly engineered means. Briscoe Expires August 31, 2006 [Page 26] Internet-Draft Bulk Border Policing using Re-ECN February 2006 6. Analysis The domains in Figure 1 are not expected to be completely malicious towards each other. After all, we can assume that they are all co- operating to provide an internetworking service to the benefit of each of them and their customers. Otherwise their routing polices would not interconnect them in the first place. However, we assume that they are also competitors of each other. So a network may try to contravene our proposed protocol if it would gain or make a competitor lose, or both, but only if it can do so without being caught. Therefore we do not have to consider every possible random attack one network could launch on the traffic of another, given anyway one network can always drop or corrupt packets that it forwards on behalf of another. Therefore, we only consider new opportunities for /gainful/ attack that our proposal introduces. But to a certain extent we can also rely on the in depth defences we have described (Section 5.6 ) intended to mitigate the potential impact if one network accidentally misconfiguring the workings of this protocol. In the generic scenario we introduced in Figure 1 the ingress and egress gateways are shown in the most generic arrangement, without any surrounding network. This allows us to consider more specific cases where these gateways and a neighbouring network are operated by the same player. As well as cases where the same player operates neighbouring networks, we will also consider cases where the two gateways collude as one player and where the sender and receiver collude as one. Collusion of other sets of domains are less likely, but we will consider such cases. In the general case, we will assume none of the nine trust domains across the figure fully trust any of the others. Taking the generic scenario in Figure 1, as we only propose to change routers within the Diffserv region, we assume the operators of networks outside the region will be doing per-flow policing. That is, we assume the networks outside the Diffserv region and the gateways around its edges can protect themselves. So our primary concern is to be able to protect networks that don't do per-flow policing from those that do. The ingress and egress gateways are the only way the outer 'enemy' can get at the middle victim, so we can consider the gateways as the representatives of the 'enemy' as far as domains A, B and C are concerned. We will call this trust scenario 'edges against middles'. Earlier in this memo, we outlined the classic border rate policing problem (Section 3). It will now be useful to spell out the motivations that would create the lack of trust as the root cause of Briscoe Expires August 31, 2006 [Page 27] Internet-Draft Bulk Border Policing using Re-ECN February 2006 the problem. The more reservations a gateway can allow, the more revenue it receives. The middle networks want the edges to comply with the admission control protocol when they become so congested that their service to others might suffer. The middle networks also want to ensure the edges cannot steal more service from them than they pay for. In the context of this 'edges aginst middles' scenario, the re-ECN protocol has two main effects: o The more pre-congestion there is on a path across the Diffserv region, the higher the ingress gateway has to declare downstream pre-congestion v_0. o because downstream pre-congestion should on average be zero at the egress An executive summary of our security analysis can be stated in two parts, distinguished by the type of collusion considered. In the first case collusion is limited to neighbours in the feedback loop. In other words, two neighbouring networks can be assumed to act as one. Or the egress gateway might collude with domain C. Or the ingress gateway might collude with domain A. Or ingress and egress gateways might collude with each other. In these cases where only neighbours in the feedback loop collude, all parties have a positive incentive to declare downstream pre- congestion truthfully, and the ingress gateway has a positive incentive to invoke admission control when congestion rises above the admission threshold in any network in the region (including its own). No party has an incentive to send more traffic than declared in reservation signalling (even though only the gateways read this signalling). In short, no party can gain at the expense of another. In the case of other forms of collusion (e.g. between domain A and C) it would be possible for say A & B to create a tunnel between theselves so that A would gain at the expense of B. But C would then lose the gain that A had made. Therefore the value to A & C of colluding to mount this attack seems questionable. It is made more questionable, because the attack can be statistically detected by B using the second defence in depth mechanism mentioned already. Note that C can effectively prevent A attacking it through a tunnel, by treating the tunnel end point as a direct link to a neighbouring network, which falls back to the regular scenario without collusion. {ToDo: Due to lack of time, the full write up of the security analysis is deferred to the next version of this memo.} Briscoe Expires August 31, 2006 [Page 28] Internet-Draft Bulk Border Policing using Re-ECN February 2006 Finally, it is well known that the best person to analyse the security of a system is not the designer. Therefore, our confident claims must be hedged with doubt until others with an incentive to break it have mounted a full analysis. 7. Extensions If a different signalling system, such as NSIS, were used, but providing admission control in a similar way using pre-congestion notification (e.g. with RMD [NSIS-RMD]) a similar approach to re-ECN could be used. 8. Design Choices and Rationale The case for using re-feedback (a generalisation of re-ECN) to police congestion response and provide QoS is made in [Re-fb]. Essentially, the insight is that congestion crosses layers from the physical upwards. Therefore re-feedback polices congestion response based on physical interfaces not addresses. That is, the congestion leaving a physical interface can be policed at the interface, rather than the congestion on packets that claim to come from an address, which may be spoofed. Also, re-feedback does not actually require feedback. A source must act conservatively before it gets feedback. On the subject of lack of feedback, the no feedback (NF) codepoint is motivated by arguments for a state set-up bit in IP to prevent state exhaustion attacks. This idea was first put forward by David Clark and documented in [Handley_Steps_DoS]. The idea is that network layer datagrams should signal explicitly when they require state to be created in the layer above (e.g. at flow start). Then the higher layer can refuse to create any state unless a datagram declares this intent. We believe the NF codepoint can be used to serve the same purpose as the proposed more generic state-set-up bit. The re-feedback paper [Re-fb] also makes the case for using an economic interpretation of congestion, which is the basis of the incentives-based approach used in this memo. That paper also makes the case against the use of classic feedback if the economic interpretation of congestion is to be realised. The problem with using classic feedback for policing congestion is that it opens up receiving networks to `denial of funds' attacks. {ToDo: Further Design Rationale will be included in future versions of this memo} Briscoe Expires August 31, 2006 [Page 29] Internet-Draft Bulk Border Policing using Re-ECN February 2006 9. IANA Considerations {ToDo:}This memo includes no request to IANA (yet). 10. Security Considerations This whole memo concerns the security of a scalable admission control system. In particular the analysis section. Below some specific security issues are mentioned that did not fit elsewhere in the memo or which comment on the robustness of the security provided by the design. Firstly, we must repeat the statement of applicability in the analysis: that we only consider new opportunities for /gainful/ attack that our proposal introduces. Despite only involving a few bits, there is sufficient complexity in the whole system that there are numerous possibilities for attacks not catered for. But as far as we are aware, none reap any benefit to the attacker. It will always be possible for one network to cause damage to another neighbouring network's traffic by dropping or corrupting it as it forwards it. Therefore we do not believe networks would set their routing policies to interconnect in the first place if they didn't trust the other networks not to damage their traffic without any /direct/ gain to themselves. Having said this, we do want to highlight some of the weaker parts of our argument. We have argued that networks will be dissuaded from faking congestion marking by the possibility that upstream networks will route round them. As we have said, these arguments are intuitive and will remain fairly tenuous until proved in practice, particularly close to the egress where less competitive routing is likely. We should also point out that the approach in this memo was only designed to be robust for admission control. We do not claim the incentives will always be strong enough to force correct flow pre- emption behaviour. This is because pre-emption of flows tends to be associated with much higher damage to an operator's reputation for robust quality than denying admission. However, in general the incentives for correct flow pre-emption are similar to those for admission control. Finally, it may seem that the 8 codepoints that have been made available by extending the ECN field with the RE bit have been used rather wastefully. In effect the RE bit has been used as an orthogonal single bit in nearly all cases. The only exception being when the ECN field is cleared to "00". The mapping of the codepoints Briscoe Expires August 31, 2006 [Page 30] Internet-Draft Bulk Border Policing using Re-ECN February 2006 in an earlier version of this proposal used the codepoint space more efficiently, but the scheme became vulnerable to a network operator focusing its congestion marking to mark more positive than neutral packets in order to reduce its penalties. {ToDo: More security considerations will undoubtedly be added in future versions of this memo.} 11. Conclusions Using pre-congestion is a promising technique to control flow admissions that will scale to any size network. However, it requires a mechanism to ensure that networks can interconnect even if they do not trust each to keep to the admission control protocols. We claim that the re-ECN protocol provides such a mechanism, so that one network can detect and prevent another network in the system fro cheating for its own gain. 12. Acknowledgements All the following have given helpful comments and some may become co- authors of later drafts: Arnaud Jacquet, Alessandro Salvatori, Steve Rudkin, David Songhurst, John Davey, Ian Self, Anthony Sheppard (BT), Stephen Hailes (UCL), Francois Le Faucheur, Anna Charny (Cisco), Jozef Babiarz, Kwok-Ho Chan, Corey Alexander (Nortel), David Clark, Bill Lehr, Sharon Gillett (MIT) and comments from participants in the CFP/CRN inter-provider QoS and broadband working groups. 13. Comments Solicited Comments and questions are encouraged and very welcome. They can be addressed to the IETF Transport Area working group's mailing list , and/or to the authors. 14. References 14.1. Normative References [PCN] Briscoe, B., Eardley, P., Songhurst, D., Le Faucheur, F., Charny, A., Liatsos, V., Babiarz, J., Chan, K., and S. Dudley, "Pre-Congestion Notification", draft-briscoe-tsvwg-cl-phb-01 (work in progress), March 2006. Briscoe Expires August 31, 2006 [Page 31] Internet-Draft Bulk Border Policing using Re-ECN February 2006 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. [RFC2211] Wroclawski, J., "Specification of the Controlled-Load Network Element Service", RFC 2211, September 1997. [RFC3168] Ramakrishnan, K., Floyd, S., and D. Black, "The Addition of Explicit Congestion Notification (ECN) to IP", RFC 3168, September 2001. [RFC3246] Davie, B., Charny, A., Bennet, J., Benson, K., Le Boudec, J., Courtney, W., Davari, S., Firoiu, V., and D. Stiliadis, "An Expedited Forwarding PHB (Per-Hop Behavior)", RFC 3246, March 2002. [RSVP-ECN] Le Faucheur, F., Charny, A., Briscoe, B., Eardley, P., Babiarz, J., and K. Chan, "RSVP Extensions for Admission Control over Diffserv using Pre-congestion Notification", draft-lefaucheur-rsvp-ecn-00 (work in progress), October 2005. [Re-TCP] Briscoe, B., Jacquet, A., and A. Salvatori, "Re-ECN: Adding Accountability for Causing Congestion to TCP/IP", draft-briscoe-tsvwg-re-ecn-tcp-01 (work in progress), March 2006. 14.2. Informative References [CL-arch] Briscoe, B., Eardley, P., Songhurst, D., Le Faucheur, F., Charny, A., Babiarz, J., and K. Chan, "A Framework for Admission Control over DiffServ using Pre-Congestion Notification", draft-briscoe-tsvwg-cl-architecture-02 (work in progress), March 2006. [ECN-BGP] Mortier, R. and I. Pratt, "Incentive Based Inter-Domain Routeing", Proc Internet Charging and QoS Technology Workshop (ICQT'03) pp308--317, September 2003, . [IXQoS] Briscoe, B. and S. Rudkin, "Commercial Models for IP Quality of Service Interconnect", BT Technology Journal (BTTJ) 23(2)171--195, April 2005, . [NSIS-RMD] Bader, A., Westberg, L., Karagiannis, G., Kappler, C., and T. Phelan, "RMD-QOSM - The Resource Management in Diffserv Briscoe Expires August 31, 2006 [Page 32] Internet-Draft Bulk Border Policing using Re-ECN February 2006 QOS Model", draft-ietf-nsis-rmd-06 (work in progress), February 2006. [RFC2205] Braden, B., Zhang, L., Berson, S., Herzog, S., and S. Jamin, "Resource ReSerVation Protocol (RSVP) -- Version 1 Functional Specification", RFC 2205, September 1997. [RFC2207] Berger, L. and T. O'Malley, "RSVP Extensions for IPSEC Data Flows", RFC 2207, September 1997. [RFC2208] Mankin, A., Baker, F., Braden, B., Bradner, S., O'Dell, M., Romanow, A., Weinrib, A., and L. Zhang, "Resource ReSerVation Protocol (RSVP) Version 1 Applicability Statement Some Guidelines on Deployment", RFC 2208, September 1997. [RFC2747] Baker, F., Lindell, B., and M. Talwar, "RSVP Cryptographic Authentication", RFC 2747, January 2000. [RFC2998] Bernet, Y., Ford, P., Yavatkar, R., Baker, F., Zhang, L., Speer, M., Braden, R., Davie, B., Wroclawski, J., and E. Felstaine, "A Framework for Integrated Services Operation over Diffserv Networks", RFC 2998, November 2000. [RFC3540] Spring, N., Wetherall, D., and D. Ely, "Robust Explicit Congestion Notification (ECN) Signaling with Nonces", RFC 3540, June 2003. [Re-fb] Briscoe, B., Jacquet, A., Di Cairano-Gilfedder, C., Salvatori, A., Soppera, A., and M. Koyabe, "Policing Congestion Response in an Internetwork Using Re-Feedback", ACM SIGCOMM CCR 35(4)277--288, August 2005, . [Smart_rtg] Goldenberg, D., Qiu, L., Xie, H., Yang, Y., and Y. Zhang, "Optimizing Cost and Performance for Multihoming", ACM SIGCOMM CCR 34(4)79--92, October 2004, . Appendix A. Implementation A.1. Ingress Gateway Algorithm for Blanking the RE bit The ingress gateway receives regular feedback reporting the fraction of congestion marked octets for each aggregate arriving at the Briscoe Expires August 31, 2006 [Page 33] Internet-Draft Bulk Border Policing using Re-ECN February 2006 egress. So for each aggregate it should blank the RE bit on the same fraction of octets. It is more efficient to calculate the reciprocal of this fraction when the signalling arrives, Z_0 = 1 / Congestion- Level-Estimate, which will be the number of bytes of packets the ingress should send with the RE bit set between those it sends with the RE bit blanked. Z_0 will also take account of the sustainable rate reported during the flow pre-emption process, if necessary. A suitable pseudo-code algorithm for the ingress gateway is as follows: ==================================================================== B_i = 0 /* interblank volume */ for each packet { b = readLength() /* set b to packet size */ B_i += b /* accumulate interblank volume */ if B_i < b * Z_0 { /* test whether interblank volume... */ writeRE(1) } else { /* ...exceeds blank RE spacing * pkt size*/ writeRE(0) /* ...and if so, clear RE */ B_i = 0 /* ...and re-set interblank volume */ } } ==================================================================== A.2. Bulk Downstream Congestion Metering Algorithm To meter the bulk amount of downstream pre-congestion in passing traffic an algorithm is needed that accumulates the size of packets with RE blanked (or NF set) and subtracts the size of congestion marked packets, but ignores a persistently negative balance over a duration of T ~ 10secs, say. Three counters need to be maintained: B_v: accumulated pre-congestion volume B_s: pre-congestion volume in timeslot B_t: total data volume A suitable pseudo-code algorithm for a border router is as follows: Briscoe Expires August 31, 2006 [Page 34] Internet-Draft Bulk Border Policing using Re-ECN February 2006 ==================================================================== B_v = 0 B_s = 0 B_t = 0 t = timeNow() + T /* divide into timeslots of few secs */ for each packet { b = readLength() /* set b to packet size */ B_t += b /* accumulate total volume */ if readRE() == 0 || readEECN() == NF { B_s += b /* increment... */ } elseif readECN() == 1X { B_s -= b /* ...or decrement B_s... */ } /*...depending on EECN field */ if timeNow() > t { /* every timeslot... */ if B_v > 0 { /* count a negative balance as zero */ B_v += B_s /* otherwise accumulate the balance */ } B_s = 0 /* re-set the temp counter... */ t += T /* ...for the next timeslot */ } } ==================================================================== At the end of an accounting period this counter B_v represents the pre-congestion volume that penalties could be applied to, as described in Section 5.2. For instance, accumulated volume of pre-congestion through a border interface over a month might be B_v = 5PB (petabyte = 10^15 byte). This might have resulted from an average downstream pre-congestion level of 1% on an accumulated total data volume of B_t = 500PB. A.3. Algorithm for Sanctioning Negative Traffic {ToDo: Write up dropper with flow management algorithm and variant with bounded flow state.} Briscoe Expires August 31, 2006 [Page 35] Internet-Draft Bulk Border Policing using Re-ECN February 2006 Author's Address Bob Briscoe BT & UCL B54/77, Adastral Park Martlesham Heath Ipswich IP5 3RE UK Phone: +44 1473 645196 Email: bob.briscoe@bt.com URI: http://www.cs.ucl.ac.uk/staff/B.Briscoe/ Briscoe Expires August 31, 2006 [Page 36] Internet-Draft Bulk Border Policing using Re-ECN February 2006 Intellectual Property Statement The IETF takes no position regarding the validity or scope of any Intellectual Property Rights or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; nor does it represent that it has made any independent effort to identify any such rights. Information on the procedures with respect to rights in RFC documents can be found in BCP 78 and BCP 79. Copies of IPR disclosures made to the IETF Secretariat and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementers or users of this specification can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr. The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement this standard. Please address the information to the IETF at ietf-ipr@ietf.org. Disclaimer of Validity This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Copyright Statement Copyright (C) The Internet Society (2006). This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights. Acknowledgment Funding for the RFC Editor function is currently provided by the Internet Society. Briscoe Expires August 31, 2006 [Page 37]