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 _______________________________________________ GROW mailing list [email protected] https://www.ietf.org/mailman/listinfo/grow
