Subject: Re: [GROW] RtgDir review: draft-ietf-grow-ix-bgp-route-server-operations-03.txt

From: Nick Hilliard <[email-masked]>
Date: Tue, 21 Oct 2014 01:06:23 +0100

John,

thanks for your extensive review - it has been very helpful.

On 18/09/2014 21:50, John G.Scudder wrote:
[...]
> - Throughout the document, various terms are used to describe what RFC 
> 4271 calls a "route". The definition given in RFC 4271 is:
> 
> Route A unit of information that pairs a set of destinations with the 
> attributes of a path to those destinations.  The set of destinations are
> systems whose IP addresses are contained in one IP address prefix
> carried in the Network Layer Reachability Information (NLRI) field of an
> UPDATE message.  The path is the information reported in the path
> attributes field of the same UPDATE message.
> 
> That is, one NLRI plus its path attributes, as carried in an UPDATE, is 
> a "route". I would suggest adopting this term, or "BGP route" if you 
> prefer, instead of terms such as "NLRI UPDATE message", "NLRI message", 
> "prefix UPDATE message", and even just plain "NLRI" and "message". Also 
> some, but not all, of the uses of "prefix". I think doing so will make 
> the document clearer, more readable, and more technically accurate. A 
> simple search for the terms I've called out should show most of them so 
> I won't enumerate them here unless you ask me to (feel free, if you 
> want).

good point: we hadn't realised that there was a specific definition of the
word/phrase, as it's thrown around so haphazardly in so many situations.
"BGP route" is probably a better choice.  I've also updated the Notational
Conventions section to include an xref to 4271.  Updated with some minor
rewordings in svn revisions r114 and r115.

> - Reference [RS-ARCH] is a dead link. I found a live copy at
> http://www.cs.usc.edu/assets/003/83191.pdf. It might be worth checking
> with the authors of RS-ARCH to ask what a good archival reference is.

this is now updated but from what I remember, this url has moved many times
since it was originally published.  I replied to Dan Romascanu:

: The location of this URL has not been static over the years, which means
: that in future, a web search may be required to locate it. The
: information included in the reference was deliberately chosen to
: ensure that it could be found by a future web search.

Even if the authors provide an archival reference, it could easily happen
that someone could reorganise it out of existence in a couple of years time
due to cutbacks in the university's IT or library department.

Long term link persistence for rfc references is a problem that the ietf
probably needs to deal with separately by downloading the content at the
time of publication and storing in its own archive.

> - S. 4.2 talks about scaling. I'm trying to make sense of the analysis:
> 
> Regardless of any Loc-RIB optimization technique is implemented, the 
> route server's control plane bandwidth requirements will scale according
> to O(P * N), where P is the total number of unique paths received by the
> route server and N is the total number of route server clients.
> 
> So far so good. (Except nit: there seems to be a word missing, such as
> "whether" as in "Regardless of whether any Loc-RIB...")

nit fixed.

> In the case where P_avg (the arithmetic mean number of unique paths
> received per route server client) remains roughly constant even as the
> number of connected clients increases, this relationship can be
> rewritten as O((P_avg * N) * N) or O(N^2).
> 
> I don't see where the second factor of N comes from. You're basically
> expanding the P in the first expression as P_avg * N -- but why? 

yes, this is not as clear as it could be.

First, to clarify: this paragraph is concerned only with network traffic
requirements, rather than with cpu / memory.

Assume for a moment that each client announces a constant P_avg unique
routes to the route-server and that there are N clients.  The total number
of unique paths received by the route server will be:

P_tot = P_avg * N

where for the sake of argument P_avg is constant.

The route server will create a RIB containing P_tot entries and will send
that N clients.  The total number of prefix announcements from the route
server will be O((P_tot) * N) = O((P_avg * N) * N) = O(N^2).  This is a
worst case situation and assumes that each prefix has a different attribute
set.

To clarify this in the text, I've changed to:

> Regardless of whether any Loc-RIB optimization technique is
> implemented, the route server's theoretical upper-bound network
> bandwidth requirements will scale according to O(P_tot * N), where
> where P_tot is the total number of unique paths received by the route 
> server and N is the total number of route server clients.

and then clarified

> Symbolically, this means that P_tot = P_avg * N.

> I think
> this would only apply if add-path all-paths was chosen as the path
> hiding mitigation strategy -- but this is not touched on in
> route-server-operations, only in ix-bgp-route-server, and besides that
> the beginning of the paragraph implies you're analyzing the multiple
> Loc-RIB strategy, so I don't guess all-path is what you were thinking
> of. If you're not doing all-path, the O(N^2) analysis is wrong AFAICT.
> To see this, consider that the inbound routes require O(P_avg * N) which
> is just O(N), but the number of routes you're going to advertise is
> bounded by the size of the Internet routing table, which is a constant
> for purposes of this analysis, so also O(N). In and out are summed, not
> multiplied, so the whole thing works out to be O(N), not O(N^2).

Some spherical cows in a vacuum may have been harmed during this analysis.

The problems revolve around the assumptions, namely:

1. P_tot = P_avg * N
2. P_avg is a realistic characterisation of the number of prefixes
announced by each client.
3. P_tot is unbounded
4. different attribute sets per prefix

You're correct that P_tot is bound above by the size of the DFZ and after a
certain stage, bandwidth requirements will be linear, O(N).  But until the
point at which this becomes the upper bound, theoretical scaling growth
will tends towards being quadratic.

Most prefixes will use one of a limited number of attribute sets, leading
to obvious transmission optimisation.

The stddev for P_n is very large indeed.  Consider AS6939 (currently 58k
prefixes) and Joe's WISP Service (1 prefix):  both are route-server users.

Yes, add-path would add another level of complication in the analysis, but
at the moment there are no ebgp add-path implementations, so we can't test.

> So I think this needs to either be corrected, or the assumptions need to
> be better explained. Moving on:
> 
> This quadratic upper bound on the network traffic requirements
> indicates that the route server model will not scale to arbitrarily
> large sizes.
> 
> If you continue to think this sentence is warranted, I think it should
> be better quantified. Of course nothing can scale to *arbitrarily* large
> sizes, but that still leaves a lot to the imagination. I would think it
> would be beneficial for an IX operator reading this document to be able
> to have some idea of how practical the limitation is. Since the analysis
> in question is looking at control traffic bandwidth consumption, it
> wouldn't be too onerous to throw some simple assumptions up against it
> -- for example, "if we suppose a RS receives on average 100,000 routes
> from each client with a rate of change of 10 routes/second, sends on
> average 1,000,000 routes to each client with a rate of change of 100
> routes/second, and that each route consumes on average 50 bytes in a BGP
> UPDATE message, simple arithmetic shows that a GigE connection to that
> RS will be fully saturated by the time the number of clients reaches
> 25,000." (Which does not seem like a very practical limitation, the RS
> will hit a CPU or memory bottleneck first.)
> 
> Anyway, maybe you will decide on reconsideration of the big-O analysis
> that this bit is not needed at all, which would be OK with me.

yes and no.  This stuff is implementation dependent and the big-O analysis
is only of limited value from a practical point of view.  It's fine for
smaller systems, but breaks for larger ones.

>From a measurement point of view, you're correct that cpu bottlenecks hit
first.  Implementation-wise, memory is cheap to fix; cpu is harder because
individual cores aren't speeding up much more these days, and so from an
implementation point of view, RSs benefit from careful Loc-RIB
optimisation.  Bandwidth is also cheap because you can throw a 10G pipe at
the server and the problem will then generally revert to a network card
driver problem if you can't depend on zero-copy data transmission or back
to a CPU problem if you have unique update sets per client.  CPU will be an
issue if you use actual Loc-RIB copies per client (quagga) instead of a
single virtual loc-ribs with per-client diffs (BIRD / IOS).  And most
organisations don't need their own loc-rib anyway.  After all, people
connect to route servers in order to interconnect promiscuously rather than
take the safer route of bilateral peering sessions.

So yeah, scaling is still a serious problem.  The performance difference
between the fastest and slowest RS implementations is measured in orders of
magnitude.

Which comes back to the issue of where to draw the line.  There's piles
that could be said, much of it highly implementation dependent (i.e. not
especially suitable for a persistent recommendation document).  Probably it
would be useful to have a better explanation of how the assumptions break
down in practice on larger systems.

I've added a new paragraph before "Tackling Scaling Issues" which reads:

> In practice, most prefixes will be associated with a limited number of
> BGP path attribute sets, allowing more efficient transmission of BGP
> routes from the route server than the theoretical analysis suggests.  In
> the analysis above, P_tot will increase monotonically according to the
> number of clients, but will have an upper limit of the size of the full
> default-free routing table of the network in which the IXP is located. 
> Observations from production route servers have shown that most route
> server clients generally avoid using custom routing policies and
> consequently the route server may not need to deploy per-client
> Loc-RIBs.  These practical bounds reduce the theoretical worst-case
> scaling scenario to the point where route-server deployments are
> manageable on even on larger IXPs.

the next paragraph starts:
> 4.2.1.  Tackling Scaling Issues
>             The problem of scaling route servers still presents serious
>             practical challenges and requires careful attention.  Scaling
>             analysis indicates problems [...]

> - S 4.2.2.1,
> 
> If the route server operator has prior knowledge of interconnection
> relationships between route server clients, then the operator may
> configure separate Loc- RIBs only for route server clients with unique
> outbound routing policies.
> 
> It wasn't obvious to me what "outbound" applies to -- the client? The
> RS? -- and for that matter why an inbound policy (on the RS) might not
> apply. Possibly this could be remedied by simply dropping the adjective
> "outbound".

removing "outbound" reduces the ambiguity; probably it's reduced enough to
make the meaning clear from the context but being an author, it's difficult
to tell (r116).

> - S. 4.2.1.2,
> 
> destination splitting would require significant co-ordination between
> the route server operator and each route server client
> 
> It's not clear to me why it would "require significant co-ordination",
> depending on what resource you're trying to conserve. Two examples of
> how you could avoid coordination while still getting benefit: You could
> have clients send all their routes to all the RSes, but have RSes filter
> out the prefixes they don't care about. [...] Or better still, the
> RS could use ORF towards the clients to control what routes the clients
> will send.

I had some things in mind when writing this section which related to each
side co-ordinating which prefixes should be announced.  Probably this was a
stupid way of handling things.  This has been reworded to:

> ...Loc-RIBs and performing the best-path calculation on each.
> 
> In practice, the route server operator would need all route server
> clients to send a full set of BGP routes to each route server.  The
> route server operator could then selectively filter these prefixes for
> each route server by using either BGP Outbound Route Filtering <xref
> target="RFC5291" /> or else inbound prefix filters configured on client
> BGP sessions.

The section deliberately doesn't go into the nitty-gritty of managing these
prefix lists (r124).

> - S. 4.6.1,
> 
> OLD: Prefixes sent to the route server are tagged with specific
> [RFC1997] or [RFC4360] BGP community attributes
> 
> I don't think the naked references scan well as adjectives in this
> context. I suggest
> 
> NEW: Prefixes sent to the route server are tagged with specific standard
> [RFC1997] or extended [RFC4360] BGP community attributes

good point - fixed (r117).

> - Also in S. 4.6.1,
> 
> OLD: As both standard and extended BGP communities values are
> restricted to 6 octets
> 
> Actually standard communities are restricted to less than that. Perhaps
> reword as
> 
> NEW: As both standard and extended BGP communities values are
> restricted to 6 octets or fewer

fixed (r118).

> - Also in S. 4.6.1,
> 
> route server operator should take care to ensure that the predefined BGP
> community values mechanism used on their route server is compatible with
> [RFC4893] 4-octet autonomous system numbers.
> 
> I suspect an RS operator reading this might be left scratching his or
> her head and asking "what does it mean for me to be compatible with
> RFC4893 in this context"? It would be kind to offer them some guidance,
> since after all this is a guidance document.

It was hard to work out where to draw the line here.

There's a simplistic mechanism used by several IXPs which is described in
the IRRDBs (see "aut-num: AS2128" for example).   It implicitly depended on
the global and local administrator fields having at least as many bits as
an ASN but unfortunately, it was conceived before the ASN32 era, so in
order for it to work properly today, we would need asn32:asn32 support in
bgp communities.  The only BGP community proposal which extends beyond a
total of 48 bits is  draft-raszuk-wide-bgp-communities, which hasn't
progressed beyond work-in-process.

When writing the document, we had a dilemma about whether to mention this
signalling scheme and by doing so, give it some form of descriptive
legitimacy even though we know it has serious operational problems, or
simply to say "look, you can do this sort of prefix announcement control
using bgp communities, but make sure it works with asn32s".  We chose the
latter.

I've added in a note to say that asn32:asn32 is not possible:

> As both standard and extended BGP community values are currently 
> restricted to 6 octets or fewer, it is not possible for both the global
> and local administrator fields in the BGP community to fit a 4-octet
> autonomous system number.  Bearing this in mind, the route server
> operator SHOULD take care to ensure that the predefined BGP community
> values mechanism used on their route server is compatible with <xref
> target="RFC4893"/> 4-octet ASNs.

This makes it clear why the asn32 requirement is important, without giving
legitimacy to the current known broken systems used (r125).

> - S. 4.7: Where you say "non-commutative" I think you mean
> "non-transitive".

oops!  Those maths lectures have receded way too far into the distance :-(

r119.

> - S. 4.7:
> 
> Problems of this form can be dealt with using [RFC5881] bidirectional 
> forwarding detection.
> 
> It's not clear to me how certain non-transitive forwarding failures can
> be dealt with using BFD. To take an example, suppose clients A, B and C
> peer with RS. The IX fabric has a failure such that A and B can both
> reach RS, but not each other. C has connectivity to everyone. Prefix X
> is advertised to RS by both B and C. For whatever reason, RS selects X
> via B to advertise to A. Even if A runs BFD towards B, at best A can
> determine that the route from RS can't be used. A isn't able to fail
> over to C's route as it would in the full-mesh case, since it's not
> aware of it. Depending on A's other connectivity, this may result in
> sub-optimal routing towards X, or complete loss of connectivity to X.
> 
> It's beyond the scope of the draft to solve this problem, but the text
> could be made more accurate. A minimal fix would be
> 
> Problems of this form can be partially mitigated using [RFC5881]
> bidirectional forwarding detection.
> 
> although you might want to go on a bit longer to explain what problems
> can't be mitigated.

You're right, this was obscure.  Incidentally, you may or may not have
noticed the overtones of Section 4 of this document:

> http://www.convergence.cx/drafts/draft-scholl-idr-advisory-01-df-input.txt

Whatever about the wisdom of bgp advisory mechanism, using it for BFD
negotiation was pretty alarming.  But that is a side issue.

Almost all IXP participants would get transit connectivity separately to
their IXP connectivity, so BFD in this situation should in theory cause A
to mark B as unreachable, and would then reroute elsewhere.  In practice,
this is not going to be a major issue.  Non-transitive connectivity
problems tend to be uncommon and any time they happen, IXP participants
would be happy that their traffic had been routed off the affected
infrastructure.

An explanatory note has been added:

> Even if automatic BFD session configuration were possible, practical 
> problems would remain.  If two IXP route server clients were configured
> to run BFD between each other and the protocol detected a non-transitive
> loss of reachability between them, each of those routers would
> internally mark the other's prefixes as unreachable via the BGP path
> announced by the route server.  As the route server only propagates a
> single best path to each client, this could cause either sub-optimal
> routing or complete connectivity loss if there were no alternative paths
> learned over other BGP sessions.

updated in r126.

> - S. 4.8:
> 
> This problem is not specific to route servers and it can also be 
> implemented using bilateral peering sessions.  However, the potential 
> damage is amplified by route servers because a single BGP session can be
> used to affect many networks simultaneously.
> 
> This is true, but there is a more severe way RSes aggravate the problem:
> In a full mesh, a router can (and usually does) directly enforce a "no
> third-party next hops" policy against its peers. An RS peer by
> definition cannot enforce this policy against the RS, so the RS is the
> only place it can be enforced.

given a suitable policy language, rsclients could use as-path + nhip
matching, but yeah, point taken.  If they're using a route server, they
won't do this.

The next paragraph is now prefixed with:

> Because route server clients cannot easily implement next-hop policy
> checks against route server BGP sessions, route server operators SHOULD
> check that the BGP NEXT_HOP attribute for BGP routes received from a
> route server client matches the interface address of the client.

r127.

> - S. 4.8:
> 
> Route server operators SHOULD check that the BGP NEXT_HOP attribute for
> NLRIs received from a route server client matches the interface address
> of the client.  If the route server receives an NLRI where these
> addresses are different
> 
> so far so good (modulo my first comment about the use of "NLRI", of
> course), but:
> 
> and where the announcing route server client is in a different
> autonomous system to the route server client which uses the next hop
> address,
> 
> Is the RS sincerely expected to enforce the above? I suppose it could be
> implemented automatically although imperfectly, by noticing that
> multiple clients are in the same neighbor AS and noticing when they use
> each other as third-party next hops, but AFAIK people generally don't
> try to figure this out, they just do what you've said in the preceding
> sentence -- make sure the NH matches the interface address. If you
> really do propose that the RS should allow third-party next hops but
> only from clients in a common AS, I think you should talk about it
> specifically and in more detail. If you didn't really mean that, then I
> suggest you drop the clause.

We were advised by one or two of the larger IXPs that some IXP participants
did NH-IP redirection tricks with multiple connections into their peering
LANs with different IP addresses and that they were unhappy that this might
be implicitly discouraged.  Organisation names were mentioned.

It's possible to implement this check in BIRD - in fact it would
be relatively easy given the programmatic approach that most IXPs use.  For
example, http://git.io/p8qsyw could do this with some modest config changes
- bear in mind this is all database+template driven and you can easily pull
out a list of other NHIPs for the same ASN on the same LAN.

So you could just override the BIRD policy code above on a per peer basis
with something like this:

asn65000_addrs = [ 192.0.0.100, 192.0.0.200, 192.0.0.220 ];

if !( bgp_next_hop ~ asn65000_addrs ) then {
	reject "bad next-hop";
} else {
	accept;
}

I've added a note:

> Permitting next-hop rewriting for the same autonomous system allows an
> organisation with multiple connections into an IXP configured with
> different IP addresses to direct traffic off the IXP infrastructure
> through any of their connections.

r130.

> - S. 5:
> 
> On route server installations which do not employ path hiding mitigation
> techniques, the path hiding problem outlined in section Section 4.1 can
> be used in certain circumstances to proactively block third party prefix
> announcements from other route server clients.
> 
> I don't understand what this means. Specifically, I don't know what it
> means to "proactively block third party prefix announcements" or for
> that matter, even what you mean by "third party prefix announcements" in
> this context. (As a term of art, I normally understand "third party
> announcement" in a BGP context to mean announcing a third-party next hop
> as you discuss in S. 4.8). I also don't know what the "certain
> circumstances" are, quite likely these should be given at least a little
> color if not entirely spelled out.

this sentence has caused confusion for other reviewers too.  It's a subtle
problem which is difficult to summarise (and to implement!).  We put in a
reference to draft-ietf-idr-ix-bgp-route-server, which describes the
problem in more detail.  I've tentatively changed this to:

> On route server installations which do not employ path hiding mitigation
> techniques, the path hiding problem outlined in
> draft-ietf-idr-ix-bgp-route-server could be used by an IXP participant
> to prevent the route server from sending any BGP routes for a particular
> prefix to other route server clients, even if there were a valid path to
> that destination via another route server client.

r122.

> Also, a nit -- the xref expansion has put "section section" into your
> text.

ouch, punked three times in the same section section!

now fixed (r121, r123).

> - S. 7:
> 
> BIRD, OpenBGPD and Quagga, whose open source BGP implementations include
> route server capabilities
> 
> Great, cool, but:
> 
> which are compliant with this document.
> 
> I'm not sure what it actually means to be "compliant" with a document
> that "describes operational considerations". Perhaps just drop the
> phrase?

oops.  This was inappropriately cut-n-paste from
draft-ietf-idr-ix-bgp-route-server, which describes changed that needs to
be complied with.

Dropped (r120).

> Nits:

all nits dealt with in follow-up to Adrian Farrel's email.

I've posted -04.

Nick

---

From: "John G. Scudder" <[email-masked]>
Date: Tue, 21 Oct 2014 14:22:59 -0400

Hi Nick,

A few remarks and nits below. You can assume that I'm fine with anything I've trimmed.

On Oct 20, 2014, at 8:06 PM, Nick Hilliard <[email-masked]> wrote:
...
> thanks for your extensive review - it has been very helpful.

You're welcome.

...
> probably needs to deal with separately

Agreed.

> by downloading the content at the

I bet that would run afoul of copyright release issues in many cases, but in any case I'd be glad to see the issue addressed somehow. By someone else.

...
>> server and N is the total number of route server clients.

where where in the
the spring

> Some spherical cows in a vacuum may have been harmed during this analysis.

:-)

> will tends towards being quadratic.

I agree with all that. However I think the point at which DFZ size becomes the upper bound is well below the point at which a practical problem rears its ugly head.

> is only of limited value from a practical point of view.  

Agreed -- which leads me to wonder if its inclusion in the document contributes more light than it does smoke.

> It's fine for

"on even on" -> "even on".

With the addition, I think the new section is sufficiently correct. I'm just not sure it helps the reader very much. I leave it to you to decide.

> make the meaning clear from the context but being an author, it's difficult

WFM.

Regards,

--John

---

From: Nick Hilliard <[email-masked]>
Date: Tue, 21 Oct 2014 22:58:51 +0100

> the spring

cut-n-paste typo.  Not present in the .txt.

> I agree with all that. However I think the point at which DFZ size
> becomes the upper bound is well below the point at which a practical
> problem rears its ugly head.

the reason the draft was originally written was because scaling problems
were hurting production deployments.  Many of these problems are handled
better in the more sophisticated RS implementations, but we got a lot of
feedback from several RS developers who were surprised at how subtly
difficult optimisation was in practice.  From this perspective, the authors
felt that it was important for RS operators to understand that there's more
going on under the hood of a RS than they might realise, so that they won't
go off and do something that might on some level seem like a good idea, but
which would inadvertently pessimize away any algorithm efficiencies in
modern RS implementations.  Also there are some more elderly RS
implementations which still suffer from many of the problems described
(e.g. quagga).  We'd prefer to leave the section in.

> "on even on" -> "even on".

oops, fixed (r142).

Nick

---

From: John Scudder <[email-masked]>
Date: Tue, 21 Oct 2014 22:58:29 +0000

On Oct 21, 2014, at 5:58 PM, Nick Hilliard <[email-masked]> wrote:
...
> We'd prefer to leave the section in.

Ok. 

--John