Internet Draft                                             Shai Herzog
Expiration: Apr. July 1999                                           IPHighway
File: draft-ietf-rap-signaled-priority-00.txt draft-ietf-rap-signaled-priority-01.txt

            Signaled Preemption Priority Policy Element

                          November 18, 1998

                          January 22, 1999

Status of this Memo

  This document is an Internet Draft.  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.
  Internet Drafts may be updated, replaced, or obsoleted by other
  documents at any time.  It is not appropriate to use Internet Drafts as
  reference material or to cite them other than as a "working draft" or
  "work in progress".

  To learn the current status of any Internet-Draft, please check the
  1id-abstracts.txt listing contained in the Internet-Drafts Shadow
  Directories on ftp.ietf.org, nic.nordu.net, ftp.isi.edu, or
  munnari.oz.au.

  A revised version of this draft document will be submitted to the RFC
  editor as a Proposed Standard for the Internet Community.  Discussion
  and suggestions for improvement are requested.  This document will
  expire at the expiration date listed above. Distribution of this draft
  is unlimited.

Abstract

  This document describes a preemption priority policy element for use by
  signaled policy based admission protocols (such as [RSVP] and [COPS]).

  Preemption priority defines a relative importance (rank) within the set
  of flows competing to be admitted into the network. Rather than
  admitting flows by order of arrival (First Come First Admitted) network
  nodes may consider priorities to preempt some previously admitted low
  priority flows in order to make room for a newer, high-priority flow.

Table of Contents

Abstract...............................................................1
Table of Contents......................................................2
1.Introduction.........................................................3
2.Scope and Applicability..............................................3
3.Policy
3.Stateless Policy.....................................................4
4.Policy Element Format:...............................................4
4.Priority Merging Issues..............................................5 Format................................................4
5.Priority Merging Strategies..........................................6
5.1.Take Issues..............................................6
5.1.Priority Merging Strategies........................................7
5.1.1.Take priority of highest QoS.......................................6
5.2.Take QoS.....................................7
5.1.2.Take highest priority..............................................7
5.3.Force priority............................................7
5.1.3.Force error on heterogeneous merge.................................7 merge...............................8
5.2.Modifying Priority Elements........................................8
6.Error Processing.....................................................7 Processing.....................................................9
7.Security Considerations..............................................8
8.Example..............................................................8
8.1.Computing Considerations..............................................9
8.References..........................................................10
9.Author Information..................................................10
A.Appendix: Example...................................................11
A.1.Computing Merged Priority..........................................8
8.2.Translation Priority.........................................11
A.2.Translation (Compression) of Priority Elements.....................9
9.References...........................................................9
10. Author Information.................................................9 Elements....................11

1. Introduction

  Traditional Capacity based Admission Control (CAC) indiscriminately
  admits new flows until capacity is exhausted. exhausted (First Come First
  Admitted). Policy based Admission Control (PAC) on the other hand
  attempts to minimize the significance of order of arrival and use
  policy based admission criteria instead.

  One of the more popular policy criteria is the rank of importance of a
  flow relative to the others competing for admition into/through admission into a network
  node. Preemption Priority takes effect only when a set of flows
  attempting admission through a node represents overbooking of resources
  such that based on CAC some would have to be rejected. Preemption
  priority criteria help the node select the most important flows
  (highest priority) for admission, while rejecting the low priority
  ones.

  Network nodes which support preemption should consider priorities to
  preempt some previously admitted low priority low-priority flows in order to make
  room for a newer, high-priority flow.

  This document describe describes the format and applicability of the Preemption
  Priority preemption
  priority represented as a policy element in [RSVP-EXT].

2. Scope and Applicability

  The Framework document for Policy-based Admission Control [Fwk] policy-based admission control [RAP]
  describes the various components that participate in policy decision
  making (i.e., PDP, PEP and LPD). The emphasis of PREEMPTION_PRI
  elements is to be simple simple, stateless, and get processed quick enough light-weight such that they
  could be implemented internally within a node’s LDP (Local Decision
  Point).

  Certain base assumptions are made in the usage model for PREEMPTION_PRI
  elements:

  - They are created by PDPs

     In a model where PDPs control PEPs at the periphery (boarder of the policy
     domain (e.g., in border routers), PDPs reduce their entire set sets of relevant
     policy rules into a single priority criteria. criterion. This priority as
     expressed in the PREEMPTION_PRI element can then be communicated to in-cloud core nodes,
     downstream PEPs of the same policy domain, which have LPDs but no
     controlling PDP.

  - They are can be processed by LDPs

     PREEMPTION_PRI elements are interpreted and are forwarded locally
     within in-cloud core nodes (in their LDP modules). Policy ignorant processed by LDPs of nodes (PINs) that do not
     have a controlling PDP. LDPs may interpret these objects, and forward
     them as is, or
     they can perform local merging and to forward an equivalent merged
     PREEPMTION_PRI
     PREEMPTION_PRI policy element. In both cases, whether for
     interpretation only or for merging, LDPs must follow the merging strategy as specified
     that was encoded by PDPs in the policy element itself. PREEMPTION_PRI objects. (Clearly, a
     PDP, being a superset of LDP, may act as an LDP as well).

  - They are enforced by PEPs

     PREEMPTION_PRI elements interact with a node’s traffic control
     module (and capacity admission control) to enforce priorities, and
     to perform preemption of
     preempt previously admitted flows if when the need arises.

3. Stateless Policy

  Signaled Preemption Priority is stateless (does not require past
  history or external information to be interpreted). Therefore, when
  carried in COPS messages for the outsourcing of policy decisions, these
  objects are included as COPS Stateless Policy Data Decision objects
  (see [COSP, COPS-RSVP]).

4. Policy Element Format: Format

  The format of Policy Data objects is defined in [RSVP-EXT]. A single
  Policy Data object may contain one or more policy elements, each
  representing a different (and perhaps orthogonal) policy.

  The format of Preemption Priority preemption priority policy element is as follows:

     +-------------+-------------+-------------+-------------+
     | Length (12)               | P-Type = PREEMPTION_PRI   |
     +------+------+-------------+-------------+-------------+
     | Flags       | M. Strategy | Error Code  | Reserved(0) |
     +------+------+-------------+-------------+-------------+
     | Preemption Priority       | Defending Priority        |
     +------+------+-------------+-------------+-------------+
  Length: 16 bits

     Always 12. The overall length of the policy element, in bytes.

  P-Type: 16 bits

     PREEMPTION_PRI  Preemption Priority  = 1
     The preemption priority policy element, element number was assigned by IANA
     as registered
                    with IANA. defined in [RSVP-EXT].

  Flags: 8 bits

     Reserved (always 0).

  Merge Strategy: 8 bit

     1    Take priority of highest QoS: recommended
     2    Take highest priority: aggressive
     3    Force Error (fail) on heterogeneous merge

  Reserved: 8 bits

  Error code: 8 bits

     0  No error.  NO_ERROR        Value used for all regular PP elements. PREEMPTION_PRI elements
     1  Preemption  PREEMPTION      This previously admitted flow was preempted
     2  Heterogeneous  HETEROGENEOUS   This PP element encountered heterogeneous merge

  Reserved: 8 bits

     Always 0.

  Preemption Priority: 16 bit (0..2^16) (unsigned)

     The priority of the new flow compared with the defending priority of
     previously admitted flows. Higher values represent higher Priority.

  Defending Priority: 16 bits (unsigned)

     Once a flow was admitted, the preemption priority becomes
     irrelevant. Instead, its defending priority is used to compare with
     the preemption priority of new flows.

     For any specific flow, its preemption priority must always be less
     than or equal to the defending priority. A wide gap between
     preemption and defending priority provides leeway for added stability: moderate
     preemption priority makes it harder for a flow to preempt others,
     but once it succeeded, the higher defending priority makes it easier
     for the flow to escape avoid preemption itself. This mechanism provides
     some order dependency, although it is not absolute, as is the case a mechanism
     for CAC.

4. balancing between order dependency and priority.

5. Priority Merging Issues

  Consider the case where two RSVP reservations merge:

         F1: QoS=High,  Priority=Low
         F2: QoS=Low,   Priority=High

  F1+F2= F3: QoS=High,  Priority=???

  Quite clearly, the

  The merged reservation F3 should have QoS=Hi, but what Priority should
  it assume? Several negative side-effects have been identified that can may
  affect such a merger:

  Free-Riders:

  If F3 assumes Priority=High, the result is that then F1 managed to get got a free ride for his high QoS, ride, assuming high
  priority that was only intended to the low QoS F2. If one associates
  costs as a function of QoS and priority, F1 receives an “expensive”
  priority without having to “pay” for it.

  Denial of Service:

  If F3 assumes Priority=Low, the merged flow could be preempted or fail
  even though F2 presented high priority.

  Denial of service is also a mirror image virtually the inverse of the free-rider problem;
  given competition problem.
  When flows compete for resources among the flows, resources, if one flow receives undeserving high
  priority it should may be able to preempt another deserving flow (hence one
  free-rider turns out to be another’s denial of service).

  Instability:

  The combination of preemption priority, killer reservation and blockade
  state [RSVP] may increase the instability of admitted flows where a
  reservation may be preempted, reinstated, and preempted again
  periodically.

5.

5.1. Priority Merging Strategies

  In merging situations LDPs may receive multiple preemption  elements for a
  merged flow
  and must compute the priority of the merged flow according to the
  following rules:

  a. Preemption priority and defending priority are merged and computed
     separately, irrespective of each other.

  b. Participating priority elements are selected.

     All priority elements are examined according to their merging
     strategy to decide whether they should participate in the merged
     result (as specified bellow).

  c. Take the The highest priority of all those who participate.

  d. A node may wish to reduce the number of PP elements it forwards by
     translating multiple PP elements into their equivalent one. In this
     case, it can only combine participating PP priority elements is
     computed.

  The remainder of this section describes the same different merging strategy into one (by taking
  strategies the highest priority amongst
     them). This effectively compress can be specified in the number of forwarded PP elements
     at most to the number of different merging strategies, regardless of
     the number of receivers (See the example in Section 8.2).

  The remainder of this section describes the different merging
  strategies the can be specified in the PREEMTION_PRI PREEMPTION_PRI element.

5.1.

5.1.1. Take priority of highest QoS

  The PP PREEMPTION_PRI element would participate in the merged reservation
  only if it belongs to a flow that contributed to the merged QoS level
  (i.e., that its QoS requirement does not constitute a subset another
  reservation.)
  A simple way to determine whether a flow contributed to the merged QoS
  result is to compute the merged QoS with and without it and to compare
  the results (although this is clearly not the most efficient method).

  The thinking behind reasoning for this approach is that the highest QoS flow is the one
  dominating the merged reservation and as such, such its priority should
  dominate it as well. This approach is the most amiable to the
  prevention of priority distortions such as free-riders and denial of
  service.

  This is a recommended merging strategy.

5.2.

5.1.2. Take highest priority

  All PP PREEMPTION_PRI elements participate in the merged reservation.

  This strategy allows all receivers to participate and contribute to the
  preemption disassociates priority even if they don’t contribute to the merged
  reservation. It and QoS level, and therefore is therefor
  highly subject to free-riders and its
  mirror inverse image, denial of service.

  This is not a recommended method, but may be simpler to implement.

5.3.

5.1.3. Force error on heterogeneous merge

  A PP PREEMPTION_PRI element with this strategy cannot may participate in a merged reservation only
  if any all other flow flows in the merged reservation has a have the same QoS level
  that is substantially different from its own.
  (heterogeneous flows).

  The determination of what
  is “substantially different” QoS level is up to the local node.

  The thinking behind reasoning for this approach is that most cases encounter
  homogenous receivers that use similar QoS levels. Furthermore, it assumes the use of PREEMPTION_PRI in that the heterogeneous case is
  relatively rare and too complicated to deal with and should not with, thus it better be permitted.
  prohibited.

  This strategy lends itself to denial of service, when a single receiver
  specifying a non-compatible QoS level may cause denial of service for
  all other receivers of the merged reservation.

  Note: The determination of heterogeneous flows applies to QoS level
  only (FLOWSPEC values), and is a matter for local (LDP) definition.
  Other types of heterogeneous reservations (e.g. conflicting reservation
  styles) are handled by RSVP and are unrelated to this PREEMPTION_PRI
  element.

5.2. Modifying Priority Elements

  When POLICY_DATA objects are protected by integrity, LDPs should not
  attempt to modify them. They must be forwarded as-is or else their
  security envelope would be invalidated. In other cases, LDPs may modify
  and merge incoming PREEMPTION_PRI elements to reduce their size and
  number according to the following rule:

  - Merging is performed for each merging strategy separately.

     There is no known algorithm to merge PREEMPTION_PRI element of
     different merging strategies without loosing valuable information
     that may affect OTHER nodes.

  - For each merging strategy, the highest QoS of all participating
     PREEMPTION_PRI elements is taken and is placed in an outgoing
     PREEMPTION_PRI element of this merging strategy.

  This approach effectively compresses the number of forwarded
  PREEMPTION_PRI elements to at most to the number of different merging
  strategies, regardless of the number of receivers (See the example in
  Appendix A.2).

6. Error Processing

  A PREEMPTION_PRI error object is sent back toward the appropriate
  receivers when an error involving PP PREEMPTION_PRI elements occur.

  Preemption

  PREEMPTION

  When a previously admitted flow is preempted, a copy of the PREEMPTING preempting
  flow’s PP PREEMPTION_PRI element is sent downstream to back toward the receiver (with PDP that
  originated the
  preemption error set). preempted PREEMPTION_PRI object. This allows receivers (or PDPs) to PDP, having
  information on both the preempting and the preempted priorities may
  construct a higher priority PP PREEMPTION_PRI element that may cause the flow in an effort to be re-instated. re-
  instate the preempted flow.

  Heterogeneity

  When a flow F1 with Heterogeneous Error merging strategy set in its PP
  PREEMPTION_PRI element encounters heterogeneity the PP PREEMPTION_PRI
  element is sent back toward receivers with the appropriate Heterogeneity error code
  set.

7. Security Considerations

  The integrity of PREEMPTION_PRI is guaranteed, as any other policy
  element, by the encapsulation into a Policy Data object [RSVP-EXT].

  Further security mechanism mechanisms are not warranted, especially considering
  that preemption priority aims to provide simple and quick guidance to
  routers within a trusted zone or at least a single zone (no zone
  boundaries are crossed).

8. References

  [RSVP-EXT]  Herzog, S. "RSVP Extensions for Policy Control", Internet-
          Draft, draft-ietf-rap-rsvp-ext-02.txt, Jan. 1999.

  [COPS-RSVP]  Boyle, J., Cohen, R., Durham, D., Herzog, S., Raja,n R.,
          Sastry, A., “COPS usage for RSVP” Internet-Draft, draft-ietf-
          rap-cops-rsvp-02.txt, Jan 1999.

  [RAP]   Yavatkar, R., et al., "A Framework for Policy Based Admission
          Control",IETF <draft-ietf-rap-framework-02.txt>, Jan., 1999.

  [COPS]  Boyle, J., Cohen, R., Durham, D., Herzog, S., Raja,n R.,
          Sastry, A., "The COPS (Common Open Policy Service) Protocol",
          IETF <draft-ietf-rap-cops-05.txt>, Jan. 1999.

  [RSVP]  Braden, R. ed., "Resource ReSerVation Protocol (RSVP) -
          Functional Specification.", IETF RFC 2205, Proposed Standard,
          Sep. 1997.

9. Author Information

  Shai Herzog, IPHighway
  Parker Plaza, Suite 1500
  400 Kelby St.
  Fort-Lee, NJ 07024
  (201) 585-0800
  herzog@iphighway.com

A.        Appendix: Example

  The following examples describe the computation of merged priority
  elements as well as the translation (compression) of PP PREEMPTION_PRI
  elements.

8.1.

A.1. Computing Merged Priority

                               r1
                              /   QoS=Hi (Pr=3, St=Highest QoS)
                             /
           s1-----A---------B--------r2  QoS=Low (Pr=4, St=Highest PP)
                   \         \
                    \         \   QoS=Low  (Pr=7, St=Highest QoS)
                     r4        r3

             QoS=Low (Pr=9, St=Error)

           Example 1: merging Preemption Priority Merging preemption priority elements

  Example one describes a multicast scenario with one sender and four
  receivers each with each own PP PREEMPTION_PRI element definition.

  r1, r2 and r3 merge in B. The resulting priority is 4.

  Reason: The PP PREEMPTION_PRI of r3 doesn’t participate (since r3 is not
  contributing to the merged QoS) and the priority is the highest of the PP
  PREEMPTION_PRI from r1 and r2.

  r1, r2, r3 and r4 merge in A. The resulting priority is again 4: r4
  doesn’t participate because its own QoS=Low is incompatible with the
  other (r1) QoS=High. An error PP PREEMPTION_PRI should be sent back to r4
  telling it that its PP PREEMPTION_PRI element encountered heterogeneity.

8.2.

A.2. Translation (Compression) of Priority Elements

  Given this set of participating PP PREEMPTION_PRI elements, the following
  compression can take place at the merging node:

  From:
           (Pr=3, St=Highest QoS)
           (Pr=7, St=Highest QoS)
           (Pr=4, St=Highest PP)
           (Pr=9, St=Highest PP)
           (Pr=6, St=Highest PP)
  To:
           (Pr=7, St=Highest QoS)
           (Pr=9, St=Highest PP)

9. References

  [RSVP]  Braden, R. ed., "Resource ReSerVation Protocol (RSVP) -
          Functional Specification."  Internet-Draft, draft-ietf-rsvp-
          spec-16.txt, June 1997.

  [COPS]  Boyle, J., Cohen, R., Durham, D., Herzog, S., Raja,n R.,
          Sastry, A., "The COPS (Common Open Policy Service) Protocol",
          Internet-Draft <draft-ietf-rap-cops-02.txt>, Aug. 1998.

  [RSVP-EXT] Herzog, S. "RSVP Extensions for Policy Control", Internet-
          Draft, draft-ietf-rap-rsvp-ext-00.txt, Apr. 1998.

  [Fwk]   R. Yavatkar, D. Pendarakis, R. Guerin.  "A Framework for Policy
          Based Admission Control", Internet-Draft <draft-ietf-rap-
          framework-00.txt>, November, 1997.

10. Author Information

  Shai Herzog, IPHighway
  Parker Plaza, Suite 1500
  400 Kelby St.
  Fort-Lee, NJ 07024
  (201) 585-0800
  herzog@iphighway.com