Internet DRAFT - draft-floyd-pushback-messages
draft-floyd-pushback-messages
Internet Engineering Task Force Sally Floyd/ACIRI
INTERNET DRAFT Steve Bellovin/AT&T
draft-floyd-pushback-messages-00.txt John Ioannidis/AT&T
Kireeti Kompella/Juniper
Ratul Mahajan/UW
Vern Paxson/ACIRI
July, 2001
Expires: January, 2002
Pushback Messages for Controlling Aggregates in the Network
Status of this Memo
This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of RFC2026.
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.
Abstract
Floyd et al. Standards Track [Page 1]
Internet Draft Pushback Messages July 2001
1. Introduction
Pushback [MB01] is designed to detect and control high bandwidth
aggregates in the network. An aggregate is a collection of packets
with a common property. For instance, with the destination prefix as
the common property, all packets with a matching prefix define an
aggregate. During a time of severe congestion from a flash crowd or
from a denial of service (DoS) attack, a router might enforce a rate-
limit on the traffic aggregate responsible for the congestion. In
addition, the congested router could ask adjacent upstream routers to
limit the amount of traffic they send for that aggregate. This
upstream rate-limiting is called pushback and can be recursively
propagated to routers further upstream. It serves to spatially
isolate the traffic aggregate so that other traffic sharing the same
downstream links is not impaired by the aggregate.
By imposing only a rate limit, rather than a complete blockage, of
the aggregate, pushback aims to minimize "collateral damage" suffered
by the non-hostile traffic matching the aggregate during a DoS
attack. In general, the hope is that during a DoS attack, pushback
will propagate sufficiently far in the network so that non-hostile
traffic fits within the rate limit imposed on its specific path to
the destination, and accordingly does not have its performance
limited.
This document specifies messages passed between cooperating routers.
It does not address procedures in routers for identifying aggregates
to be rate-limited, or for determining the rate-limits for those
identified aggregates. The goal is to specify an experimental
standard for pushback messages so that we can learn from the
experimental use of pushback. We expect that the specifications for
pushback messages will evolve over time, as we gain more experience
with their use.
There are two main pushback messages - REQUEST and STATUS. Pushback
REQUEST messages are sent to upstream routers asking them to rate-
limit the aggregate. Such a request for rate-limiting is only
advisory; the upstream router is not compelled to follow the request.
As part of rate-limiting on behalf of the downstream router, the
upstream router sends periodic STATUS messages to the downstream
router. The STATUS messages report the arrival rate for that
aggregate at the upstream router, and enable the congested router to
take decisions regarding the continuance of pushback. In addition to
REQUEST and STATUS messages, REFRESH messages reinforce the soft-
state rate-limiting, and CANCEL messages terminate it.
Pushback messages can be used in two ways. In one pushback type,
pushback messages are used to request upstream rate-limiting for the
Floyd et al. Standards Track [Page 2]
Internet Draft Pushback Messages July 2001
specified aggregate. In a second pushback type (DUMMY_PROP),
pushback messages are used simply to get information about the
arrival rates of an aggregate at upstream routers.
A pushback in progress can be visualized as a tree (or, with
multipath routing, possibly a graph), where the congested router
initiating the pushback is the root. The parent of a router in the
tree is the downstream router from which it got the pushback REQUEST.
Routers that do not propagate pushback further are leaves of the
tree.
The following sections specify the format for pushback messages and
the timing of REFRESH and STATUS messages. This document also
specifies the procedures for propagating pushback REQUEST and REFRESH
messages further upstream, and for merging the resulting STATUS
messages from upstream routers.
2. The Common Header
All pushback messages have the following fields prepended in the
header.
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Version |AdF| Msg Type | Rate-Limiting Session ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Pushback Initiating Router's IP Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Sender's IP Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
The first field specifies the version of the pushback protocol the
sender speaks. The protocol described in this document is Version=0.
"AdF" specifies the type of address family used. Currently defined
values are IPv4=0 and IPv6=1. Other values are reserved for future
definition.
The message type is one of REQUEST (= 0), REFRESH (= 1), STATUS (=
2), or CANCEL (= 3). The fields following the common header are
dependent on the type of the message.
The Rate-limiting Session ID (RLSID) is generated by the congested
router initiating pushback. It MUST be unique among all current rate-
limiting sessions initiated by this router. The RLSID combined with
the IP address of the congested router defines a pushback session
over the whole network. A router receives both these fields from the
Floyd et al. Standards Track [Page 3]
Internet Draft Pushback Messages July 2001
downstream router requesting pushback. These fields enable the
routers to map incoming messages to the appropriate rate-limiting
session. A router MAY use its different addresses when initiating
different pushback sessions.
Note that if the router's address reflects a private addressing
realm, then it MUST be altered upon crossing into a different
addressing realm. Ideally this transformation uses a new address
unique to the router; if not available, then the address of the
router propagating pushback (by sending the message) into the
different realm is used.
The sender's IP address has been included in the pushback message,
making message interpretation independent of the IP source address
field. This eliminates any confusion regarding which interface's
address is included in that field (that is, whether it is the IP
address of the message-sending interface, or of some other interface
at the router). It also helps when pushback messages traverse
between routers that are not directly connected. If a sender sends
pushback messages to two peers in two different addressing realms, so
that the sender doesn't have a unique address to send to both peers,
then the sender will use different values for the sender's IP address
in the two messages.
Both the IP addresses will be 128 bit fields for IPv6.
2. The Pushback REQUEST Message
Pushback requests (type REQUEST=0) are sent upstream when a router
wants the aggregate to be rate-limited upstream. The fields in a
pushback REQUEST, in addition to the common header, are shown below.
Floyd et al. Standards Track [Page 4]
Internet Draft Pushback Messages July 2001
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| PType |SRMode | Max Depth | Depth in Tree | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Bandwidth Limit |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Expiration Time |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Status Frequency |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
| Congestion Signature |
...............................................
...............................................
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
"PType" denotes the type of pushback and determines the upstream
router's behavior in various ways. PType=0 (HI_DROP_PROP) requests
the upstream router to propagate pushback if the restricted aggregate
suffers a high drop rate due to the restriction. (This is the usual
mode of pushback.)
PType=1 (ALWAYS_PROP) requests that the upstream router propagate
pushback irrespective of the drop rate experienced by the aggregate.
It would typically be used when the aggregate is known with high
confidence to be malicious.
PType=2 (DUMMY_PROP) indicates no actual rate-limiting should take
place---the downstream router is just interested in the arrival rate
estimate of this aggregate. The extent of propagation of these
pushback messages is controlled by the congested router using "Max
Depth" (explained below) to determine the arrival rate of an
aggregate several hops upstream.
Other values of PType are reserved for future definition.
The pushback requester can specify the mode in which it wants
feedback with the "SRMode" (Status Reporting Mode) field. SRMode=0
(COMPACT) specifies the feedback should be just the total arrival-
rate estimate of the aggregate. SRMode=1 (CLOSEST) specifies the
feedback should include per-router feedback for upstream routers, and
if there is not room for all of them, then those closest (lowest hop
count) should be preferred. SRMode=2 (FURTHEST) is similar to
CLOSEST, but prefers routers further away from the congested router.
SRMode=3 (SAMPLE) specifies that instead a pseudo-random subset of
Floyd et al. Standards Track [Page 5]
Internet Draft Pushback Messages July 2001
the upstream routers should be included. These last two modes
facilitate different forms of mapping to aid with tracing back the
attack sources. Other values are reserved for future definition.
Using "Max Depth" the congested router can control the maximum number
of hops pushback will propagate to. The special value of 255
indicates unrestricted propagation; 254 indicates that pushback
should be propagated up to, but not across, the AS boundary.
The depth in the tree is the distance of the requesting node from the
root of the pushback tree. The depth of the root is zero, and a
child's depth is one more than the depth of its parent. Depth
information is useful in setting timers for sending feedback. If a
router receives overlapping pushback requests from multiple peers,
its depth is one more than the minimum depth of its parents.
The bandwidth limit is a single precision (32-bit) floating point
number in IEEE format, as described in [SPG97]. It expresses the
rate in bytes per second. It is only a requested upper bound for the
bandwidth to be given to the aggregate. If congested, the upstream
router could send less than that upper bound. In addition, the
upstream router is not *required* to observe the requested bound.
The expiration time is the time period after which the pushback
request expires if no REFRESH messages arrive. The status frequency
gives the time after which the upstream routers should send STATUS
messages downstream. Both the times are specified in milliseconds,
and represented using 32-bit integers in network byte order.
2.0.1 The Congestion Signature
The congestion signature is the description of the aggregate that is
to be rate-limited. Its specification is a major open question. As
an example, the attack signature might consist of the destination
prefix(es) characterizing the aggregate. At the other extreme, we
could allow arbitrary ACLs of fields in the packet header. For this
first experimental use of pushback, we will limit the congestion
signature to depend only on the source and destination IP addresses
in the packet header. This excludes the use of aggregates defined by
the protocol field in the IP header and the port numbers in the
transport header; an example is an aggregate consisting of all DNS
traffic.
Congestion signatures are specified as TLVs (type-length-value):
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Floyd et al. Standards Track [Page 6]
Internet Draft Pushback Messages July 2001
| Type | Length | Value .... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
...............................................
.....................Value.....................
...............................................
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| .... Value and final Padding .... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
The Length field includes the Type and Length fields, as well as the
length of the Value and any Padding.
Values are padded up to 32-bit alignment. If, after doing so, more
data remains in the datagram, then it's interpreted as another TLV.
Type=0 (SRC_PREFIX) indicates a source address prefix. Its Length is
4 bytes plus the length of an address in the format specified by AdF
above. The first octet of Value (bits 16 through 23 in the first
line of the above figure) are reserved. The second octet gives the
prefix length, in the range 1-32 (IPv4) or 1-128 (IPv6). Other
values are reserved.
Type=1 (DST_PREFIX) is the same but for destination address prefix.
When all prefixes in the list are of the same type, the congestion
signature describes packets that have the corresponding field (source
or destination) matching one of the prefixes in the list. In
presence of both source and destination prefixes, packets belonging
to the aggregate are those destined for one of the destination
prefixes *and* coming from one of the source prefixes.
2.1 Propagating a Pushback REQUEST Message
When propagating a pushback request upstream, the router MUST insert
the correct depth information, which is one more than the depth of
its parent(s).
In addition, the destination prefixes in the congestion signature
MUST be checked to see whether they have to be *narrowed*, to
restrict the rate-limiting only to traffic headed for the downstream
router that requested pushback, as follows. Suppose the congested
router X identifies a certain aggregate A with destination prefix
128.95/16. X will ask its upstream router Y (among others) to rate-
limit traffic from aggregate A (128.95/16). However, Y cannot use
the same specification directly because while Y could be forwarding
128.95.1/24 to X, it might not be forwarding the rest of 128.95/16 to
X. If Y (and routers upstream of Y) started rate-limiting all of
128.95/16, the network would drop traffic which would not have
Floyd et al. Standards Track [Page 7]
Internet Draft Pushback Messages July 2001
reached the congested router X.
To avoid this unnecessary packet-dropping, it is important that Y
look at its routing table to find prefixes within 128.95/16 that are
forwarded to X. Y has to check all extensions of the given prefix in
the routing table.
The issue of narrowing the congestion signature occurs when a
pushback request is propagated upstream by a router (thus becoming a
non-leaf in the tree), or when the pushback request is passed from
the output interface to an input interface at a router. The above
algorithm for narrowing the congestion signature works only for
congestion signatures with a destination address component in them.
It cannot be applied to other signatures, pure source-based ones, for
instance. We do not deal with the issue of narrowing non-
destination-based signatures in this document except noting that it
can be done given the right routing information at the upstream
router.
A router could receive requests from different downstream routers
with overlapping congestion signatures. Future work might address
the possibility of merging two different rate-limiting sessions in
this case.
2.2 Pushback REFRESH Messages
Pushback REFRESH messages are initiated by the congested router that
started the pushback, if it wants the pushback to continue. For
uninterrupted rate-limiting, these messages should be generated
before the rate-limiting expires at the upstream routers
The REFRESH message is identical to the REQUEST message, so that if
the upstream router has crashed in the meanwhile, the state can be
reestablished. However, the message type is set to REFRESH so that,
if state already exists, it is matched against the RLSID and router
address fields so that the receiving router does not have to go
through the process of setting up state from scratch.
REFRESH messages can change any field specified earlier in the
pushback REQUEST. On receiving the pushback REFRESH message the
upstream routers update the expiration time for the rate-limit
session and the limit imposed on the aggregate, and set the timer for
the STATUS message. Non-leaf routers in the pushback tree SHOULD
send REFRESH messages further upstream after dividing the rate limit
among upstream neighbors. If the aggregate specification has
changed, the router MUST check if the new aggregate needs to be
narrowed, using the process described above, before propagating the
pushback REFRESH.
Floyd et al. Standards Track [Page 8]
Internet Draft Pushback Messages July 2001
2.3 Pushback CANCEL Messages
The pushback CANCEL message is sent upstream to stop rate-limiting
the aggregate. It SHOULD be propagated upstream by routers that have
propagated pushback requests (non-leaf routers in the pushback tree).
The CANCEL message has no fields beyond those present in the common
header.
3. Pushback STATUS Messages
Upstream routers that receive a pushback REQUEST send pushback STATUS
messages to the router from whom they got their REQUEST. The
additional fields in the STATUS message are:
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Arrival Rate Estimate |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| SRMode| Rsrvd | Height | NumElem |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| <Router ID> |
| <Router Info> |
| <Arrival Rate at Router> |
...............................................
................................................
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
The arrival rate estimate is a single precision floating-point number
in IEEE format, as described in [SPG97]. It expresses the arrival
rate of the aggregate in bytes per second if there was no rate-
limiting upstream of the STATUS sender. The arrival rate for the
first STATUS message is computed over the interval since the receipt
of the pushback REQUEST. For the subsequent messages, it is computed
over the interval since the last STATUS message.
The SRMode field specifies the mode in which status is reported. It
is the same as that in the pushback REQUEST message. The supported
modes and their semantics are described in Section 2.
"Height" denotes the height of the sender in the pushback tree. It is
zero for leaf nodes, and one more than the maximum height among
children for non-leaf nodes. This field tells the receiver how far
pushback has propagated upstream of it.
Floyd et al. Standards Track [Page 9]
Internet Draft Pushback Messages July 2001
For status modes that return a list of routers, NumElem gives the
number of listed routers. Then, for each router
* Router ID gives an address identifying the router
* Router Info gives information associated with the router.
Currently, this consists of:
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|S| Reserved | Depth in Tree |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
S is a bit that if set means that the entry is Stale, meaning that no
new STATUS message has been received from the router since the last
time the sending router sent a STATUS message.
Depth in Tree reflects the depth of the router in the pushback tree.
3.1 Aggregating STATUS Messages
A parent node uses the STATUS messages from its children to construct
the STATUS message it sends downstream. The merger technique used
depends on the mode of the STATUS message. In COMPACT mode, the
parent node adds the arrival rate estimates received from the
children and its estimate from upstream routers that were not sent
pushback messages. In other modes, the lists obtained from the
various children are merged, and appended with the parent node's own
estimate, as indicated in the previous section. The height is one
more than the maximum height recieved from the children.
3.2 Timing of STATUS Messages
The status frequency specified in the pushback REQUEST and REFRESH
messages is the rate at which the originating router would like to
receive status reports. Since the upstream routers are at different
distances from the root, the timer values they set have to be
different. In particular, routers further away from the root should
set smaller timer values because they get messages late and their
STATUS messages take time getting to the root node.
On receiving a REQUEST or REFRESH message, the routers set a timer to
send the STATUS message. The value of this timer is the status
frequency minus the _depth_ * _k_, where _depth_ is the router's
depth in the pushback tree, and _k_ is a constant that signifies the
maximum round trip time for a message over a pushback tree edge
(including message processing time). _k_ should be configured to
some comfortable upper bound like 100 ms (it is same for all the
Floyd et al. Standards Track [Page 10]
Internet Draft Pushback Messages July 2001
routers in the pushback tree). For satellite hops or other links
with round-trip times greater than the configured value _k_, the
consequences will simply be stale STATUS messages.
Setting timers in this fashion means that parents are likely to
obtain fresh STATUS messages from their children before their own
STATUS message timer goes off. This in turn means that fresh STATUS
messages are sent further downstream after aggregation. If a parent
router's timer fires before it has received STATUS message from one
of its children, it MUST send its own STATUS message downstream using
the last value received from this child or its own estimate, and, if
including an individual rate report for this child, marking it with
S=1 to indicate it is Stale.
The status timer is set again immediately after sending the STATUS
messages downstream. The value of the timer is the same for all the
routers in this case, and is equal to the status frequency, since the
required offset has already been achieved. If a router receives a
REFRESH message before its status timer expires, new timers are set
as described above.
A small jitter can be applied to status timers so that the downstream
router recieves STATUS messages from its children at different times.
In some cases, the original sender of the pushback REQUEST might want
some variation in the status timers to provide some degree of
protection against gaming adversaries that try to time their bursts
to avoid detection. This variation could be achieved by the original
sender by making changes to the Status Frequency specified in the
pushback REFRESH messages.
4. Authentication for Pushback Messages
Pushback messages require some form of authentication, even if the
pushback messages are between adjacent routers. However, this
document currently does not specify the form of authentication to be
used.
5. Messages between Routers and Local Agents
Some routers might send packet headers from a sample of the traffic
to an agent for outboard processing, and receive control messages
back from the agent about identified aggregates to be rate-limited.
The router and local agent will also exchange control messages, for
example, to control the sampling at the router. The formats for
these messages will probably be addressed in a separate document.
Floyd et al. Standards Track [Page 11]
Internet Draft Pushback Messages July 2001
Because this is a purely local conversation between a router and an
attached local agent, it is not necessary that a router and its
attached local agent follow the protocol suggested in that document.
6. Messages exchanged with the NOC
In some cases the NOC (Network Operations Center) will want to have
final approval before an aggregate is rate-limited. Thus, one
category of pushback messages will be the messages exchanged with the
NOC. This draft currently does not specify these messages.
Conclusions
Acknowledgements
There is a list of people who can be either co-authors, or can be
acknowledged in this section. So far, this list includes the
following. The pushback authors: Ratul Mahajan, Steven M. Bellovin,
Sally Floyd, John Ioannidis, Vern Paxson, and Scott Shenker. From
Juniper: Kireeti Kompella. From Cisco: Barbara Fraser, David Meyer.
Other: Randy Bush.
References
[MB01] Ratul Mahajan, Steven M. Bellovin, Sally Floyd, John
Ioannidis, Vern Paxson, and Scott Shenker, Controlling High Bandwidth
Aggregates in the Network, February 2001. URL:
"http://www.aciri.org/pushback/".
[SPG97] S. Shenker, C. Partridge, R. Guerin. Specification of
Guaranteed Quality of Service. RFC 2212. September 1997.
Security Considerations
We will eventually address the potential DoS features and security
vulnerabilities of pushback in detail here.
IANA Considerations
AUTHORS' ADDRESSES
Sally Floyd
Phone: +1 510 666 2989
ACIRI
Email: floyd@aciri.org
URL: http://www.aciri.org/floyd/
Floyd et al. Standards Track [Page 12]
Internet Draft Pushback Messages July 2001
Steve Bellovin
Phone: +1.973.360.8656
AT&T Labs - Research
Email: smb@research.att.com
John Ioannidis
Phone: +1.973.360.7012
AT&T Labs - Research
Email: ji@research.att.com
Kireeti Kompella
Juniper Networks
1994 N. Mathilda Ave
Sunnyvale, CA 94089
Email: kireeti@juniper.net
Ratul Mahajan
Phone: +1 206 616 1853
Univerity of Washington
Email: ratul@cs.washington.edu
URL: http://www.cs.washington.edu/homes/ratul/
Vern Paxson
Phone: +1 510 666 2882
ACIRI
Email: vern@aciri.org
URL: http://www.aciri.org/vern/
This draft was created in July 2001.
It expires January 2002.
Floyd et al. Standards Track [Page 13]
