Compressed BGP Update Message
draft-przygienda-idr-compressed-updates-00
The information below is for an old version of the document.
| Document | Type | Active Internet-Draft (individual) | |
|---|---|---|---|
| Author | Tony Przygienda | ||
| Last updated | 2017-03-10 | ||
| Stream | (None) | ||
| Formats | plain text xml htmlized pdfized bibtex | ||
| Stream | Stream state | (No stream defined) | |
| Consensus boilerplate | Unknown | ||
| RFC Editor Note | (None) | ||
| IESG | IESG state | I-D Exists | |
| Telechat date | (None) | ||
| Responsible AD | (None) | ||
| Send notices to | (None) |
draft-przygienda-idr-compressed-updates-00
Network Working Group A. Przygienda
Internet-Draft Juniper
Intended status: Standards Track March 10, 2017
Expires: September 11, 2017
Compressed BGP Update Message
draft-przygienda-idr-compressed-updates-00
Abstract
Specification of compressed BGP update message formats and
procedures.
Requirements Language
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 RFC 2119 [RFC2119].
Status of This Memo
This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/.
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."
This Internet-Draft will expire on September 11, 2017.
Copyright Notice
Copyright (c) 2017 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must
Przygienda Expires September 11, 2017 [Page 1]
Internet-Draft draft-przygienda-idr-compressed-updates-00 March 2017
include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2
2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4
3. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 4
4. Procedures . . . . . . . . . . . . . . . . . . . . . . . . . 5
4.1. Decompression Capability Negotiation . . . . . . . . . . 5
4.2. Compressed BGP Update Messages . . . . . . . . . . . . . 5
4.3. Compressor Overflow . . . . . . . . . . . . . . . . . . . 6
4.4. Compressor Restarts . . . . . . . . . . . . . . . . . . . 6
4.5. Error Handling . . . . . . . . . . . . . . . . . . . . . 6
5. Special Considerations . . . . . . . . . . . . . . . . . . . 7
5.1. Impact on Network Sniffing Tools . . . . . . . . . . . . 7
6. Packet Formats . . . . . . . . . . . . . . . . . . . . . . . 7
6.1. Decompressor Capability . . . . . . . . . . . . . . . . . 7
6.2. Compressed Update Messages . . . . . . . . . . . . . . . 8
7. Security Considerations . . . . . . . . . . . . . . . . . . . 9
8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 9
9. Normative References . . . . . . . . . . . . . . . . . . . . 9
Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 10
1. Introduction
BGP as a protocol evolved over the years to carry more and more
information and this trend seems to continue unabated. And while
lots of the growth can be contributed to the advent of new address
families spurred by [RFC2283], steady increase in attributes and
their size adds to that. Recently, even the same NLRI may be
advertised multiple times by the means of ADD-PATH
[ID.draft-ietf-idr-add-paths-15] extensions. All those developments
drive up the volume of information BGP needs to exchange to
synchronize RIBs of the peers.
Although BGP update format provides a simple "semantic" compression
mechanism that avoids the repetition of attributes if multiple NLRIs
share them already, in practical terms, the packing of updates has
proven a difficult challenge. The packing attempts are further
undermined by the plethora of "per NLRI-tagging" attributes such as
extended communities [RFC4360].
One could of course dismiss the growing, raw volume of the data
necessary to exchange BGP information between two peers as a mere
trifle given the still rising link bandwidths, alas we are facing
Przygienda Expires September 11, 2017 [Page 2]
Internet-Draft draft-przygienda-idr-compressed-updates-00 March 2017
other sustained trends that would make the reduction of data volume
exchanged by BGP highly desirable:
o Link delays will remain constant until radically new transmission
mechanisms become common place [QUANT]. Bare those developments,
and given the prevailing constant ethernet MTU, increasing volume
of BGP traffic will cause more and more IP packets to be sent with
the BGP synchronization speed being limited by the expanding
bandwith-delay product.
o The data volume, which for one peer may be reasonable, becomes
less so when many of those need to be refreshed due to [RFC4724]
and [RFC7313] interactions. Use of those techniques is expected
to increase due to increasing demands on BGP reliability and novel
variants of state synchronization between peers.
o BGP message length is limited to 4K which in itself is a
recognized problem. Extensions to the message length
[ID.draft-ietf-idr-bgp-extended-messages-12] are being worked on
but this puts its own requirements and memory pressure on the
implementations and ultimately will not help with attributes
exceeding 4K size limit in mixed environments.
o Virtualization techniques introduce an increasing amount of
context switches an IP packet has to cross between two BGP
instances. Coupled with difficulties in estimating a reasonable
TCP MSS in virtualized environments the number of IP packets TCP
starts to generate more and more overhead before real BGP update
processing can happen.
Obviously, unless we change BGP encoding drastically by e.g.
introducing more context to allow for semantic compression, we cannot
expect a reduction in data volume without paying some kind of price.
Ideas such as changing BGP format to allow for decoupling of
attribute value updates from the NLRI updates could be a viable
course of action. The challenges of such a scheme are significant
and since such "compression" would extend the semantics and formats
of the updates as we have them today, former and future drafts may
interact with such an approach in ways not discernible today. Last
but not least, attempting to introduce a smarter, context-rich
encoding is likely to cause dependency problems and slow-down in BGP
encoding procedures.
Fortunately, some observations can be made and an emerging trend
exploited to attempt a reduction in BGP data volumes without this
kind of disadvantage:
Przygienda Expires September 11, 2017 [Page 3]
Internet-Draft draft-przygienda-idr-compressed-updates-00 March 2017
o BGP updates are very repetitive. Smallest change in attribute
values causes extensive repetition of all attributes and any
difference prevents packing of NLRIs in same update. On top, each
update message BGP still carries a marker that largely lost its
practical value some time ago. One could summarize that by saying
that BGP updates tend to exhibit very low entropy.
o CPU cycles available to run control protocols are getting more and
more abundant as does to a certain extent memory. They tend to
not be available anymore in easily harvested "single core with
higher frequency" form factors but as multiple cores that
introduce the usual pitfalls of parallelization. In short,
getting a lot of independent work done is getting cheaper and
cheaper while speeding up a single strain of execution depending
on previous results less so. This opens nevertheless the
possibility to apply different filters on BGP streams, possibly
even executing in parallel threads. One possible filter can
compress the data in a manner completely transparent to the rest
of existing implementation.
Hence, we suggest in this draft the removal of redundancy in the BGP
update stream via Huffman codes which can be applied as filter to a
BGP update stream concurrently to the rest of the BGP processing and
per peer. Subsequently, this document describes an optional scheme
to compress BGP update traffic with a deflate variant of Huffman
encoding [RFC1950], [RFC1951].
In broadest terms, such a scheme will be beneficial if a BGP
implementation finds itself in an I/O constrained scenario while
having spare CPU cycles disponible. Compression will ease the
pressure on TCP processing and synchronization as well as reduce raw
number of IP packets exchanged between peers.
2. Terminology
3. IANA Considerations
This document requests IANA to assign new BGP message type value and
and a new optional capability value in the BGP Capability Codes
registry. The suggested value for the Compressed Updates message
type is 6 and for the Capability Code the suggested value is 76.
IANA is requested as well to assign a new subcode in the "BGP Cease
NOTIFICATION message subcodes" registry. The suggested name for the
code point is "Decompression Error". The suggested value is 10.
Przygienda Expires September 11, 2017 [Page 4]
Internet-Draft draft-przygienda-idr-compressed-updates-00 March 2017
4. Procedures
4.1. Decompression Capability Negotiation
The capability to *decompress* a new, optional message type carrying
compressed updates is advertised via the usual BGP optional
capability negotiation technique.
A peer MUST NOT send any compressed updates towards peers that did
not advertise the capability to decompress. A peer MAY send
compressed updates towards peers that advertised such capability.
4.2. Compressed BGP Update Messages
A new BGP message is introduced under the name of "Compressed BGP
Update". It contains inside arbitrary number of normal BGP update
messages following each other and compressed while following the
rules below:
1. Compressed and uncompressed BGP updates MAY follow each other in
arbitrary order with exception of compressor overflow scenario
per Section 4.3. After decompression of the stream of compressed
and interleaved uncompressed BGP update messages the resulting
sequence of updates does not have to be identical to the sequence
in a stream generated without compression. However, the
uncompressed sequence MUST ensure that the ultimate semantics of
the updates are the same to the peer as in the no-compression
case.
2. The updates contained within the compressed BGP update message
MUST be stripped of the initial marker while preserving the BGP
update message header. The length field in the BGP update header
retains its original value.
3. Each compressed BGP Update MUST carry a sequence of non-
fragmented original updates, i.e. it cannot contain a part of an
original BGP update. Section 4.3 presents the only exception to
this rule.
4. Each compressed BGP Update MUST be sent as a block, i.e. the
decompression MUST be able to yield decompressed results of the
update without waiting for further compressed updates. This is
different from the normally used stream compression mode.
Section 4.3 presents the only exception to this rule.
5. The compressed update message MAY exceed the maximum message size
but in such case compressor overflow per Section 4.3 MUST be
invoked.
Przygienda Expires September 11, 2017 [Page 5]
Internet-Draft draft-przygienda-idr-compressed-updates-00 March 2017
4.3. Compressor Overflow
To achieve optimal compression rates it is desirable to provide to
the compressor enough data so the resulting compressed update is as
close to the maximum BGP update size as possible. Unfortunately, a
Huffman with adapting dictionary compresses at always varying ratio
which can lead to an overflow unless it is used very conservatively.
A special provision, optionally to be used at the sender's
discretion, allows for such overruns and simplifies the handling of
overflow events.
In case the compressed block size exceeds the maximum BGP update
size, the compressing peer MUST set the according bit in the
compressed update generated and MUST proceed it with one and only one
compressed update with the overflow and compressor restart bit
cleared and the remainder of the block. No other BGP update messages
are allowed in the TCP stream between the compressed update of a
certain compressor and its overflow fragment. In case of any
deviations, the error procedures of Section 4.5 MUST be followed.
The receiving peer MUST concancenate the first compressed update and
the following overflow update as a single compressed block and apply
decompression to it.
The first update MAY be smaller than the maximum BGP update size.
4.4. Compressor Restarts
In certain scenarios it is beneficial for the compressing peer to be
able to restart any of the compressors at any point in the ongoing
BGP session. To indicate such an occurrence, each compressed update
CAN carry a flag signaling to the decompressing peer that it MUST
restart the given de-compressor before attempting to handle the
update.
4.5. Error Handling
If the decompression fails for any reason, the failure MUST cause
immediate CEASE notification with a newly introduced subcode of
"Decompression Error" (as documented in the IANA BGP Error Codes
registry). The peer which experienced the failure MAY initiate the
connection again but it SHOULD NOT advertise the decompressor
capability until an administrative reset of the session or re-
configuration of the peer. This will achieve self-stabilization of
the feature in case of implementation problems.
The compressing peer MAY send such CEASE notification as well and
close the peer. It is at the discretion of the decompressing peer
Przygienda Expires September 11, 2017 [Page 6]
Internet-Draft draft-przygienda-idr-compressed-updates-00 March 2017
given such a notification to omit the decompression capability on the
next OPEN.
5. Special Considerations
5.1. Impact on Network Sniffing Tools
Network sniffing tool today have the capability to monitor an ongoing
BGP session and try to reconstruct the state of the peers from the
updates parsed. Obviously, with compression enabled, such a monitor
cannot follow the compressed updates unless the session is monitored
from the first compressed update on.
Several possibilities to deal with the problem exist, the simplest
one being the restart of the compressors on a periodic basis to allow
the monitoring tool to 'sync up'. It goes without saying that this
will be detrimental to the compression ratio achieved.
Another possibility would have been to periodically send the Huffman
dictionary over the wire but this complexity has been left out as to
not overburden this specification. Moreover, at the current time,
such a capability is not part of any standard Huffman implementation
that could be easily referred to.
6. Packet Formats
6.1. Decompressor Capability
Decompressor Capability is following the normal procedures of
[RFC5492]. In its generic form the option can support different
compressors in the future.
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Code | Length | type| de/compressor parameters|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
This document specifies only DEFLATE Huffman support per [RFC1950].
Przygienda Expires September 11, 2017 [Page 7]
Internet-Draft draft-przygienda-idr-compressed-updates-00 March 2017
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Code | Length | CM | CINFO | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Code: TBD, suggested value of 76.
Length: 1 octet.
CM: 3 bits of CM indicating DEFLATE compressed format value as
specified in [RFC1950].
CINFO: 4 bits of CINFO as specified in [RFC1950]. Invalid values
MUST lead to the capability being ignored. The compressing peer
MUST use this value for the parametrization of its algorithm.
6.2. Compressed Update Messages
This carries the original updates in a single message with content
adhering to Section 4.2.
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Length | Type |R|O| ULI | ID# |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| compressed data ...
+-+-+-+-+-+-+-+-+-+- ...
Type: TBD, suggested value is 6.
Length: 2 octets.
ID#: 3 bits. Indicates the number of the compressor used. Up to 8
compressors MAY be used by the compressing peer to allow for
multiple thread of execution to compress the BGP update stream.
Accordingly the decompressing side MUST support up to 8
independent decompressors.
R: If the bit is set, the according de-compressor MUST be initialized
before the following compressed data is decompressed per
Section 4.4. The bit MAY be set on first compressed update sent
for the compressor on the session or is otherwise implied sapienti
Przygienda Expires September 11, 2017 [Page 8]
Internet-Draft draft-przygienda-idr-compressed-updates-00 March 2017
sat. The bit MUST NOT be set on the overflow fragment in case of
overflow.
O: If the bit is set, procedures in Section 4.3 MUST be applied. If
both the R-bit and the O-bit are set, the de-compressor must be
re-initialized before the update and its overflow is assembled and
decompression attempted.
ULI: Original uncompressed length indication as to be interpreted as
2**(11+ULI). This MUST indicate a buffer large enough the
decompressed data (including overflow) will fit in. The
indication MAY be ignored by the receiver but should allow for
efficient buffer allocation. The field MUST be ignored on
overflow fragment.
7. Security Considerations
This document introduces no new security concerns to BGP or other
specifications referenced in this document.
8. Acknowledgements
Thanks to John Scudder for some bar discussions that primed the
creative process. Thanks to Eric Rosen, Jeff Haas, Acee Lindem and
Jeff Tantsura for their careful reviews.
9. Normative References
[ID.draft-ietf-idr-add-paths-15]
Walton et al., D., "Advertisement of Multiple Paths in
BGP", internet-draft draft-ietf-idr-add-paths-15.txt, May
2016.
[ID.draft-ietf-idr-bgp-extended-messages-12]
Bush et al., R., "Advertisement of Multiple Paths in BGP",
internet-draft draft-ietf-idr-bgp-extended-messages-
12.txt, May 2016.
[QUANT] Zyga, L., "Worldwide Quantum Web May Be Possible with Help
from Graphs", New Journal on Physics , June 2016.
[RFC1950] Deutsch, P. and J-L. Gailly, "ZLIB Compressed Data Format
Specification version 3.3", RFC 1950,
DOI 10.17487/RFC1950, May 1996,
<http://www.rfc-editor.org/info/rfc1950>.
Przygienda Expires September 11, 2017 [Page 9]
Internet-Draft draft-przygienda-idr-compressed-updates-00 March 2017
[RFC1951] Deutsch, P., "DEFLATE Compressed Data Format Specification
version 1.3", RFC 1951, DOI 10.17487/RFC1951, May 1996,
<http://www.rfc-editor.org/info/rfc1951>.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997,
<http://www.rfc-editor.org/info/rfc2119>.
[RFC2283] Bates, T., Chandra, R., Katz, D., and Y. Rekhter,
"Multiprotocol Extensions for BGP-4", RFC 2283,
DOI 10.17487/RFC2283, February 1998,
<http://www.rfc-editor.org/info/rfc2283>.
[RFC4360] Sangli, S., Tappan, D., and Y. Rekhter, "BGP Extended
Communities Attribute", RFC 4360, DOI 10.17487/RFC4360,
February 2006, <http://www.rfc-editor.org/info/rfc4360>.
[RFC4724] Sangli, S., Chen, E., Fernando, R., Scudder, J., and Y.
Rekhter, "Graceful Restart Mechanism for BGP", RFC 4724,
DOI 10.17487/RFC4724, January 2007,
<http://www.rfc-editor.org/info/rfc4724>.
[RFC5492] Scudder, J. and R. Chandra, "Capabilities Advertisement
with BGP-4", RFC 5492, DOI 10.17487/RFC5492, February
2009, <http://www.rfc-editor.org/info/rfc5492>.
[RFC7313] Patel, K., Chen, E., and B. Venkatachalapathy, "Enhanced
Route Refresh Capability for BGP-4", RFC 7313,
DOI 10.17487/RFC7313, July 2014,
<http://www.rfc-editor.org/info/rfc7313>.
Author's Address
Tony Przygienda
Juniper
1137 Innovation Way
Sunnyvale, CA
USA
Email: prz@juniper.net
Przygienda Expires September 11, 2017 [Page 10]