Internet DRAFT - draft-heitz-idr-msdc-bgp-aggregation
draft-heitz-idr-msdc-bgp-aggregation
IDR J. Heitz
Internet-Draft D. Rao
Intended status: Standards Track Cisco
Expires: April 25, 2019 October 22, 2018
Aggregating BGP routes in Massive Scale Data Centers
draft-heitz-idr-msdc-bgp-aggregation-00
Abstract
A design for a fabric of switches to connect up to one million
servers in a data center is described. At that scale, it is
impractical for every switch to maintain knowledge about every other
switch and every other link in the fabric. Aggregation of routes is
an excellent way to scale such a fabric. However, aggregation
presents some problems under link failures or switch failures. This
design solves those problems.
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 [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 https://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 April 25, 2019.
Copyright Notice
Copyright (c) 2018 IETF Trust and the persons identified as the
document authors. All rights reserved.
Heitz & Rao Expires April 25, 2019 [Page 1]
Internet-Draft MSDC BGP Aggregation October 2018
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(https://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
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. Solution Overview . . . . . . . . . . . . . . . . . . . . . . 3
3. Problems with negative routes . . . . . . . . . . . . . . . . 4
4. Use of a negative route in BGP . . . . . . . . . . . . . . . 4
5. Implementation Notes to Reduce CPU Time Consumption . . . . . 5
6. Smooth Startup and Avoidance of Too Many Negative Routes . . 5
7. Avoidance of Transients . . . . . . . . . . . . . . . . . . . 6
8. Configuration . . . . . . . . . . . . . . . . . . . . . . . . 7
9. South Triggered Automatic Disaggregation (STAD) . . . . . . . 7
10. Configuration for STAD . . . . . . . . . . . . . . . . . . . 8
11. Security Considerations . . . . . . . . . . . . . . . . . . . 9
12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 9
13. Acknowldgements . . . . . . . . . . . . . . . . . . . . . . . 9
14. References . . . . . . . . . . . . . . . . . . . . . . . . . 9
14.1. Normative References . . . . . . . . . . . . . . . . . . 9
14.2. Informative References . . . . . . . . . . . . . . . . . 9
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 9
1. Introduction
[RFC7938] defines a massive scale data center as one that contains
over one hundred thousand servers. It describes the advantages of
using BGP as a routing protocol in a Clos switching fabric that
connects these servers. It laments the need to announce all routes
individually, because of the problems associated with route
aggergation. A fabric design that scales to one million servers is
considered enough for the forseeable future and is the design goal of
this document. Of course, the design should also work for smaller
fabrics.
A switch fabric to connect one million servers will consist of
between 35000 and 130000 switches and 1.5 million to 8 million links,
depending on how redundantly the servers are connected to the fabric
and the level of oversubscription in the fabric. A switch that needs
to store, send and operate on hundreds of routes is clearly cheaper
than one that needs to store, send and operate on millions of links.
Heitz & Rao Expires April 25, 2019 [Page 2]
Internet-Draft MSDC BGP Aggregation October 2018
A switch running BGP and aggregating its routes needs to send only
one route. In the ideal case, each switch receives just one route
from each of its neighbors. For each link or a neighbor that fails,
the switch should send just one extra route. No single link failure
needs to be known by every switch in the fabric and some switch
failures do not need to be known by every switch either. The routes
that advertise these failures should only propagate to those switches
that need to know about them. During normal operation, the number of
failures are few, so the number of advertisements are few.
A route that advertises a failure is called a negative route.
Negative routes are not a new idea, but they are unpopular, because
they cause a number of problems. This document solves the problems.
2. Solution Overview
In a Clos network all northbound links can reach all destinations and
there is typically only one or very few southbound links to reach any
specific destination. Therefore, traffic from source to destination
is spread to all available northbound links, reaches all the spines
and then concentrates southbound towards its destination. When a
link fails, then a spine will lose connectivity to some southbound
destiunations. That means any northbound link to that spine also
loses connectivity to the same destinations.
When the fabric is fully connected with no failed links, then the
forwarding tables in the switches can simply contain multipath
aggreagate routes to all the northbound links. Each of the multipath
routes is the same, so traffic is spread out smoothly among these
routes. As soon as a link fails, the forwarding tables must exclude
the resultant unreachable destinations from some of the northbound
links. The way to do that is to add specific routes for the failed
destinations to point at the remaining links that can reach those
destinations. Since traffic will always prefer specific routes to
aggregate routes, the traffic to the failed destinations will no
longer take the aggregate routes.
Two methods to create these specific routes are described. One way
is to send a negative route from the point where the failure is
detected. Receivers use the negative route to punch holes out of the
aggregate routes and create the specific routes by subtracting the
negative route from the aggregates. This method is described
starting at section 4. The other method creates the specific routes
at the point of the failure and announces them in BGP. This method
is described starting at section 9.
Heitz & Rao Expires April 25, 2019 [Page 3]
Internet-Draft MSDC BGP Aggregation October 2018
3. Problems with negative routes
- Massive failures can cause lots of negative routes and overwhelm
the switches.
- In order for a switch to know what has failed, it must know what
is supposed to be up. For it to know this requires either an
error prone algorithm or an error prone configuration.
- During certain network events that cause multiple routes to be
sent and/or withdrawn, the messages may race each other and cause
transient loss of connectivity to paths that were otherwise
unaffected by the event. This occurs in link state routing
protocols as well.
- Computation of forwarding table entries may consume a lot of CPU
time in pathological cases. However, even in pathological cases,
this is still much less CPU time than it takes to compute an SPF
in a million links.
4. Use of a negative route in BGP
Three new BGP well known communities are defined:
- Hole-Punch: A route with this community can punch a hole out of
another route with a shorter netmask that covers the address
space of this route.
- Punch-Accept: A route with this community can have holes punched
out of it by hole punch routes.
- Do-not-Aggregate; Do not aggregate this route.
A fabric switch will aggregate routes learnt from neighbors to its
south. It must know all the routes that are expected to complete the
aggregate. It will announce the aggregate with the Punch-Accept
community. If any of the routes that are expected to complete the
aggregate are missing, then it will announce those missing routes
with the Hole-Punch and Do-not-Aggregate communities along with the
aggregate route.
A receiver of a route with the Hole-Punch community will give it a
lower than normal local preference and will search the BGP table for
other routes with the following properties:
- a shorter netmask than this route,
- covers the address space of this route,
Heitz & Rao Expires April 25, 2019 [Page 4]
Internet-Draft MSDC BGP Aggregation October 2018
- has the Punch-Accept community,
- is installed in the Routing Table.
This is the candidate set. Then, it will remove any routes that have
a shorter netmask than the route with the longest netmask in the set.
The final candidate set of routes will all have the same prefix. For
each route in the candidate set, BGP will create a new route with the
same prefix as the Hole-punch route and the same attributes as the
Punch-Accept route. This new route is called a chad route. If a
route has an MPLS label, then the label is considered part of the
attributes, not part of the prefix.
Chad routes will take part in bestpath and multipath selection. If a
chad route becomes a bestpath or a multipath, it will be installed in
the Routing Table. However, chad routes are not advertised by
default. That means if a chad route is bestpath and other routes
exist for the same prefix, then no route is advertised for that
prefix.
If a chad route has the same nexthop (and MPLS label, if labels are
used) as a hole-punch route of the same prefix, then the chad route
becomes hidden. Hidden means that it cannot take part in route
selection.
5. Implementation Notes to Reduce CPU Time Consumption
This section is not normative.
When a Punch-Accept route is received, BGP needs to scan a subtree of
the BGP prefix table rooted at the prefix of the Punch-Accept route
to look for Hole-Punch routes that might create chad routes from it.
That subtree could be large. To reduce the number of routes to scan,
a separate prefix table is created to store copies of the Hole-Punch
routes. The number of Hole-Punch routes is expected to be much
smaller than the total number of routes. That makes the scan much
quicker. The Hole-Punch routes must additionally be stored in the
regular BGP route table.
6. Smooth Startup and Avoidance of Too Many Negative Routes
When several switches of a data center fabric start up at the same
time, many negative routes can be transiently created before the
whole system is up.
When the BGP process starts, it will typically start in receive-only
mode for some time, then perform route selection and send out it's
own updates. To ensure a smooth startup of the data center when many
Heitz & Rao Expires April 25, 2019 [Page 5]
Internet-Draft MSDC BGP Aggregation October 2018
nodes start at the same time, the startup sequence is modified as
follows.
- All BGP speakers SHOULD send EOR after sending all routes after
the BGP session becomes established.
- When all southbound configured BGP neighbors have sent their EOR,
the BGP speaker will perform route selection and send all updates
to the northbound neighbors and then send EOR. If some
southbound neighbors cannot establish, a timer will be used to
prevent waiting forever.
- After the previous step completes, when all northbound configured
BGP neighbors have sent their EOR, the BGP speaker will perform
route selection and send all updates to the southbound neighbors
and then send EOR. If some northbound neighbors cannot
establish, a timer will be used to prevent waiting forever.
- If the number of received negative routes causes too many
forwarding entries, then BGP can look for aggreagate routes that
are accompanied by many hole-punch routes and invalidate some of
the aggregate routes and their accompanying hole-punch routes.
If the number of received negative routes is too many to hold in
the BGP table, then BGP can shut down neighbor sessions that are
sending the most negative routes.
7. Avoidance of Transients
If one event were to cause both an aggregate and a hole-punch route
to be announced at the same time, but the hole-punch route were to
arrive late, a transient could result. The following rules prevent
that.
- It is common practice for aggregate routes to be withdrawn when
no components of the aggregate exist. Hole-Punch routes need to
always be announced, even if the aggregate is not.
- After a BGP session establishes, no routes that are received from
it should be installed in the RIB until the EOR is received from
that session.
- If overlapping hole-punch routes need to be updated and
withdrawn, then the updates must be sent before the withdraws.
- If overlapping hole-punch and punch-accept routes need to be
updated, then the hole-punch routes must be updated first.
Heitz & Rao Expires April 25, 2019 [Page 6]
Internet-Draft MSDC BGP Aggregation October 2018
- If overlapping hole-punch and punch-accept routes need to be
withdrawn, then the punch-accept routes must be withdrawn first.
8. Configuration
All the BGP sessions need to be configured on each switch. The BGP
sessions need to be configured as northbound or southbound. The
routes that are expected to complete an aggregate route must be
configured.
A companion document describes a protocol that can discover and
configure the entire fabric. If that companion document is used,
then no IP addresses or tier designations or any other location
dependent configuration is required on the switches.
9. South Triggered Automatic Disaggregation (STAD)
In this method, a node that is south of a failed link or node
announces its prefix(es) along alternative links with a hint to
trigger automatic disaggregation or inhibit their suppression on
upstream tier nodes. These disaggregated or unsuppressed routes
traverse along redundant paths and disjoint planes to switches in
other clusters in the topology where they are used in forwarding.
The hint is in the form of a well known BGP community. A few new
well known communities are used in this scheme.
- Do-not-Aggregate : Do not aggregate this route
- Tier : An Extended Community identifying the tier of the
originated route
- Dis-Aggregate : Triggers announcement of more specific routes at
receiving node
The techniques in this draft assume a CLOS topology of the form
described in [Figure 3] of RFC7938 where an access switch such as a
TOR forms the lowest tier and is connected to multiple northbound
upper tier switches; which in turn are connected to multiple upper
tier switches, forming disjoint planes across the topology with fan-
outs.
A figure illustrating the topology will be added in a subsequent
version.
Upon a link failure, the node south of the failure announces its
prefix to it's other northbound BGP sessions with the Do-Not-
Advertise community.
Heitz & Rao Expires April 25, 2019 [Page 7]
Internet-Draft MSDC BGP Aggregation October 2018
A higher tier node that receives a route with a Do-not-Aggregate
community will not suppress this route when there is a local covering
aggregate, but will propagate it further as is.
This procedure enables the more specific route to reach the
appropriate tier switches in other clusters where the topology fans
out on multiple northbound links. The received paths for the more
specific prefix form a multipath excluding the links which would lead
to failed paths in the topology.
A route that is advertised with the Do-Not-Aggregate community as per
this section will also add a Tier extended community. If this
extended community is present, then the Do-Not-Aggregate community is
only applicable at tiers that are more north than the tier indicated
in the extended community.
The Tier Extended Community ensures that the unsuppressed specific
routes do not propagate further beyond the corresponding fan-out
points in the other clusters.
If all the northbound links or BGP sessions at a node have failed,
then the node will announce its southbound route with the Dis-
Aggregate community. This signals all it's south-side nodes to
advertise their north-bound routes with the Do-Not-Aggregate
community along the other north-bound links.
These techniques are applicable to any tier in the topology.
At the lowest tier, if there are servers that are attached to more
than one fabric switch (eg. TOR), then the host routes (or
configured more-specific routes) for the server are not aggregated by
the TOR to it's connected upper tier switches. In this case, these
routes are aggregated by the upper-tier switches towards the rest of
the topology.
10. Configuration for STAD
Each switch has the notion of northbound and southbound sessions or
links. In addition, it is assigned to a tier in the hierarchy. The
switch uses this configuration to drive the procedures described in
the section above. A switch at the lowest tier (eg. a TOR) will have
server subnet prefixes configured. Switches at higher tiers have
aggregates configured.
Heitz & Rao Expires April 25, 2019 [Page 8]
Internet-Draft MSDC BGP Aggregation October 2018
11. Security Considerations
TBD
12. IANA Considerations
TBD
13. Acknowldgements
14. References
14.1. Normative References
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997,
<https://www.rfc-editor.org/info/rfc2119>.
14.2. Informative References
[RFC7938] Lapukhov, P., Premji, A., and J. Mitchell, Ed., "Use of
BGP for Routing in Large-Scale Data Centers", RFC 7938,
DOI 10.17487/RFC7938, August 2016,
<https://www.rfc-editor.org/info/rfc7938>.
Authors' Addresses
Jakob Heitz
Cisco
170 West Tasman Drive
San Jose, CA, CA 95134
USA
Email: jheitz@cisco.com
Dhananjaya Rao
Cisco
170 West Tasman Drive
San Jose, CA, CA 95134
USA
Email: dhrao@cisco.com
Heitz & Rao Expires April 25, 2019 [Page 9]
