From owner-Big-Internet@munnari.oz.au Fri Apr 3 04:20:59 1992 Received: by munnari.oz.au (5.64+1.3.1+0.50) id AA09373; Fri, 3 Apr 1992 04:21:12 +1000 (from owner-Big-Internet) Return-Path: Received: from SPARTA.COM by munnari.oz.au with SMTP (5.64+1.3.1+0.50) id AA09367; Fri, 3 Apr 1992 04:20:59 +1000 (from woody@sparta.com) Received: by sparta.com (5.65/1.34) id AA21222; Thu, 2 Apr 92 13:25:02 -0500 Date: Thu, 2 Apr 92 13:25:02 -0500 From: woody@sparta.com (Robert "Woody" Woodburn) Message-Id: <9204021825.AA21222@sparta.com> To: lars@spectrum.CMC.COM In-Reply-To: Lars Poulsen's message of Thu, 26 Mar 92 19:50:56 GMT <1992Mar26.195056.28742@spectrum.CMC.COM> Subject: routing vs ADs Cc: Big-Internet@munnari.OZ.AU, woody@sparta.com Hi Lars, IDPR was very heavily worked on last summer, but I don't know what the current status is. The internet drafts on the information servers have not been revised since July '91, and I don't think there was a working group meeting in San Diego, but the protocol does not appear to have moved to "Proposed Standard" RFC publication. Maybe Bob Hinden or Martha Steenstrup can tell us what the current status is ? As far as the IDPR software goes, SAIC is currently doing most of the implementation work to integrate IDPR with gated. We are shooting for a public release by early August with an alpha release in mid to late June. We are also trying to flush out possible participants for experiments as we get things going, so anybody who would be willing to lend a machine (or pair of machines to form the whole VG) in their AD (AS) would be more than welcome. wood y PS: my sparta address comes from the fact that we are sub to sparta working on their premises for a larger contract of which the IDPR development is just a part. From owner-Big-Internet@munnari.oz.au Sat Apr 4 03:27:05 1992 Received: by munnari.oz.au (5.64+1.3.1+0.50) id AA18862; Sat, 4 Apr 1992 03:27:14 +1000 (from owner-Big-Internet) Return-Path: Received: from venera.isi.edu by munnari.oz.au with SMTP (5.64+1.3.1+0.50) id AA18857; Sat, 4 Apr 1992 03:27:05 +1000 (from postel@ISI.EDU) Received: from bel.isi.edu by venera.isi.edu (5.65c/5.65+local-4) id ; Fri, 3 Apr 1992 09:27:09 -0800 Date: Fri, 3 Apr 92 09:26:27 PST From: postel@ISI.EDU Posted-Date: Fri, 3 Apr 92 09:26:27 PST Message-Id: <9204031726.AA24250@bel.isi.edu> Received: by bel.isi.edu (4.1/4.0.3-4) id ; Fri, 3 Apr 92 09:26:27 PST To: big-internet@munnari.oz.au Subject: supernetting Cc: postel@ISI.EDU Ok. So we somehow assign addresses in clumps so that nets that are close together (topologically, geographically, or conceptually) get adjacent addresses. How do the routers figure out when they can collapse the separate routing table entries for each network in to a single entry? Just for some of us that maybe a little slow can some one explain the algorithm that routers will use to do this entry merging? Thanks. --jon. From owner-big-internet@munnari.oz.au Sat Apr 4 12:01:06 1992 Received: by munnari.oz.au (5.64+1.3.1+0.50) id AA29070; Sat, 4 Apr 1992 12:01:15 +1000 (from owner-big-internet) Return-Path: Received: from GINGER.LCS.MIT.EDU by munnari.oz.au with SMTP (5.64+1.3.1+0.50) id AA24672; Sat, 4 Apr 1992 08:15:48 +1000 (from jnc@ginger.lcs.mit.edu) Received: by ginger.lcs.mit.edu id AA14317; Fri, 3 Apr 92 17:15:32 -0500 Date: Fri, 3 Apr 92 17:15:32 -0500 From: jnc@ginger.lcs.mit.edu (Noel Chiappa) Message-Id: <9204032215.AA14317@ginger.lcs.mit.edu> To: big-internet@munnari.oz.au, postel@isi.edu Subject: Re: supernetting Cc: jnc@ginger.lcs.mit.edu There's one simple algorithm which I have seen around for about 10 years which is guaranteed to produce optimal results; i.e. does the condensing as soon as it can, and results in the same forwarding choices in all cases as non-condensed information. I'll describe it in terns of net and subnet routes, but it of couse works for any address hierarchy. Anytime you have a bunch of route A.X1, A.X2 .... A.Xn (where Xi is a subnet of network A, for instance), in updates you send you can replace all the separate routes to A.Xi with a single route to A whenever all the routes A.Xi in your table are through the same next hop. This works recursively; if further off in the networks nets A, B, ... K (which all share a prefix) are found to have the same next hop, the individual routes cn be replaced with a single route to the group. This algorithm is of most use only where there are not artificial route aggregation mechanisms. We have an instance of this now, where in most cases subnet routes are not allowed outside a network. Note that this algorithm works even if the router in question is not connected to net A, i.e. you are allowing subnet routes of net A to leak out into surrounding networks to allow picking of optimal entry routers into net A. I think this algorithm works also at the time you put routes into the tables, not just when sending updates; i.e. you can have only a single entry in your routing table. There are some special cases I don't recall offhand, though. The only drawback to this algorithm in its basic form is that it's computationally fairly expensive, since you have to find groups of routes which share a prefix and the same next hop, etc. Probably smart coding and saving a bunch of precomputed intermediate information would make it cheaper. Noel From owner-Big-Internet@munnari.oz.au Sun Apr 5 02:33:42 1992 Received: by munnari.oz.au (5.64+1.3.1+0.50) id AA14206; Sun, 5 Apr 1992 02:33:49 +1000 (from owner-Big-Internet) Return-Path: Received: from GINGER.LCS.MIT.EDU by munnari.oz.au with SMTP (5.64+1.3.1+0.50) id AA14203; Sun, 5 Apr 1992 02:33:42 +1000 (from jnc@ginger.lcs.mit.edu) Received: by ginger.lcs.mit.edu id AA16300; Sat, 4 Apr 92 11:33:36 -0500 Date: Sat, 4 Apr 92 11:33:36 -0500 From: jnc@ginger.lcs.mit.edu (Noel Chiappa) Message-Id: <9204041633.AA16300@ginger.lcs.mit.edu> To: big-internet@munnari.oz.au, postel@isi.edu Subject: Re: supernetting Cc: jnc@ginger.lcs.mit.edu Oh, one difficulty I forgot to mention about that scheme is how you pick the metric you advertise on the single route. Clearly, all the individual subroutes probably have different metrics. I'm not sure what the optimal algorithm is (by optimal I mean the algorithm which assigns the lowest possible number to the aggregate metric without creating routing loops). I'm pretty sure that if you use the min of all the metrics, you could potentially generate routing loops. Consider the case where R1 and R2 are both connected to nets A.X1 and B, and R1 gets to all A.Xi through R2, which has other connections. R1 makes up an advertisement for A, using the lowest metric for any piece of A, and sends it on B. R2 gets it, decides R1 is a better route to parts of A than its existing individual routes. Bingo; routing loop. Of course, this one will probably break itself, but a little thought might find stable routing loops. I think using the max of all the metrics is probably safe, but I have this feeling that it will result in non-optimal routing. I have this even fainter feeling that there is no optimal algorithm (using the definition above) without global knowledge (sort of like there is no optimal paging algorithm without knowledge of future reference patterns). Whenever you aggregate information, you have to throw some away, and when you have incomplete information its hard to guarantee that you are not creating a problem. However, this is just a feeling, not a proof. I know Yakov Rekhter has thought about this some, and maybe he has the metric setting algorithm. Perhaps some of the more mathematically inclined (like John Moy and Marth Steenstrup) have some thoughts? Noel From owner-Big-Internet@munnari.oz.au Sun Apr 5 04:34:07 1992 Received: by munnari.oz.au (5.64+1.3.1+0.50) id AA15914; Sun, 5 Apr 1992 04:34:16 +1000 (from owner-Big-Internet) Return-Path: Received: from MrBill.CAnet.CA by munnari.oz.au with SMTP (5.64+1.3.1+0.50) id AA15904; Sun, 5 Apr 1992 04:34:07 +1000 (from dennis@MrBill.CAnet.CA) Received: by MrBill.CAnet.CA id <105487>; Sat, 4 Apr 1992 13:33:39 -0000 From: Dennis Ferguson To: jnc@ginger.lcs.mit.edu Subject: Re: supernetting Cc: big-internet@munnari.oz.au, postel@isi.edu Message-Id: <92Apr4.133339gmt.105487@MrBill.CAnet.CA> Date: Sat, 4 Apr 1992 13:33:33 -0000 > Anytime you have a bunch of route A.X1, A.X2 .... A.Xn (where Xi is a > subnet of network A, for instance), in updates you send you can replace all > the separate routes to A.Xi with a single route to A whenever all the routes > A.Xi in your table are through the same next hop. This works recursively; > if further off in the networks nets A, B, ... K (which all share a prefix) > are found to have the same next hop, the individual routes cn be replaced > with a single route to the group. This is true, but I don't think it is practically useful. Suppose A.X1 has other connectivity. If your route to A.X1 goes down you must somehow signal this to the wider area routing so that it knows when it should consider using alternate paths to reach A.X1. With the scheme above the only way to do this would be to cease advertising A and instead advertise all of the remaining A.Xi whenever A.X1 goes down. And note that this also works recursively, so the loss of a route to A.X1 may result in explosions of routing information elsewhere. Of course, we currently don't have a routing protocol which can tell us automatically whether A.X1, or any other A.Xi, has alternate connectivity (and hence whether it is topologically significant to the wider area routing) or not. This means that in the absense of other information routing will only work correctly if we assume the worst, that all of A.Xi is topologically significant, which means that if the routes to any individual A.Xi go away we'll need to advertise the remaining bits of A unsummarized. This implies that (1) you can only aggregate to A if *all* routes which are subordinate to A are known and are to be forwarded in the same direction, and (2) if any part of A goes unreachable you need to announce the remainder explicitly to signal this. Now if I look just at the subnets of 128.100 using these rules it appears to me that the best we could do it collapse this to about a dozen routes. This compares to the single route (128.100.0.0 mask 255.255.0.0) which is advertised now, and no further aggregation would be possible since there are holes. Worse, every time a subnet went unreachable we'd need to modify our off-campus announcement, whereas now the wider world remains blissfully ignorant of this since they only know about the route to 128.100.0.0 mask 255.255.0.0. This is no improvement. > This algorithm is of most use only where there are not artificial > route aggregation mechanisms. We have an instance of this now, where in most > cases subnet routes are not allowed outside a network. Note that this > algorithm works even if the router in question is not connected to net A, > i.e. you are allowing subnet routes of net A to leak out into surrounding > networks to allow picking of optimal entry routers into net A. There is nothing "artificial" about aggregating subnets to a network, it is simply a rule which defines the extent of the topological significance of the subnet information. The rule doesn't only tell you that you must aggregate subnets at a network boundary, it also tells you that you can aggregate subnets at a network boundary since it guarantees (or enforces) that none of the subnet information will be topologically significant beyond that boundary. And this, indeed, forced you to design your use of addresses so this was true Now if you remove that rule (the only one we had up to this point) I think you can do no aggregation of address information at all unless you obtain knowledge of topological extent from elsewhere. And currently the only way we have to do this is configuration, by someone who "knows" what is significant and what isn't. This potentially allows much greater efficiency, but achieves this essentially through hand optimization. Until someone invents a better way to discover topological extent automatically, this is what we're faced with. Dennis Ferguson University of Toronto From owner-Big-Internet@munnari.oz.au Sun Apr 5 08:43:42 1992 Received: by munnari.oz.au (5.64+1.3.1+0.50) id AA19492; Sun, 5 Apr 1992 08:43:49 +1000 (from owner-Big-Internet) Return-Path: Received: from GINGER.LCS.MIT.EDU by munnari.oz.au with SMTP (5.64+1.3.1+0.50) id AA19486; Sun, 5 Apr 1992 08:43:42 +1000 (from jnc@ginger.lcs.mit.edu) Received: by ginger.lcs.mit.edu id AA17376; Sat, 4 Apr 92 17:43:32 -0500 Date: Sat, 4 Apr 92 17:43:32 -0500 From: jnc@ginger.lcs.mit.edu (Noel Chiappa) Message-Id: <9204042243.AA17376@ginger.lcs.mit.edu> To: big-internet@munnari.oz.au, dennis@mrbill.canet.ca Subject: Re: supernetting Cc: jnc@ginger.lcs.mit.edu O Cognitory Ones (following the new non-carbon-ist IETF line :-): I think the algorithm can 'sucessfully' handle all these sorts of problems, but clearly the resulting routing may not have the degree of aggregation that you want. In the case you cite, if R1 lost its existing route to A.X1, I assume it would get a route to A.X1 from elsewhere, assuming A.X1 was not partitioned from the net. If that new route is still through the same next hop, then it can still aggregate. If the new route is through a different next hop, it can't. If it had no route to A.X1 at all, it would still be valid to aggregate to a single A route. We simply can't make the rule that you have to have all routes to all A.Xi from A.X1 to A.Xn before you can aggregate down to a single route A. Since we tend to have incomplete assignment of the numbering space (i.e. you have room for subnets 1-62 but only have 17 active), you'd almost *never* get complete aggregation, unless you happened to have a power of two's worth of numbers in actual use! I think the algorithm has to be that if all A.Xi which fall under the A mask which you have are through the same next hop, you can aggregate, even if there are various A.Xi 'missing'; i.e. no route to them at all. we currently don't have a routing protocol which can tell us automatically whether A.X1, or any other A.Xi, has alternate connectivity ... or not I don't understand this at all. First, the whole point of dynamic routing protocols is to find alternate connectivity when something breaks. If by your comment you meant that no routing protocol provides you with that information about alternate connectivity at all times (as opposed to telling you in response to a break), that's still not true, since any link state system can always tell whether A.Xi has alternate connectivity. Your comments about aggregating subnets at a network boundary relate to some thoughts I've been having. I went off to think about the problem I raised in the second message (what do you pick for a metric?), and I wondered how OSPF solved this same problem (since it allows arbitrary ranges inside an area to be aggregated to single entries outside the area). Turns out OSPF finesses the problem in exactly the same way; it uses the hand-configured area boundary to state explicity when aggregation must occur. The metric is simply the min of the distances to any piece. If the pieces are discontiguous (i.e. if subnets of a net are in two areas), OSPF does not handle that. If you are guaranteed that all the pieces of something are inside a boundary, and inside that boundary you don't do any aggregation, then you can aggregate the info going across the boundary (on exit) and assign any metric you want and not create routing loops. It's when you try and calculate the boundary in a distributed way, in real time, that you run into problems. Hmm. Maybe CIDR uses configured boundaries? Any CIDRites listening to this? How does it work? Noel From owner-Big-Internet@munnari.oz.au Sun Apr 5 08:55:12 1992 Received: by munnari.oz.au (5.64+1.3.1+0.50) id AA19701; Sun, 5 Apr 1992 08:55:27 +1000 (from owner-Big-Internet) Return-Path: Received: from GINGER.LCS.MIT.EDU by munnari.oz.au with SMTP (5.64+1.3.1+0.50) id AA19686; Sun, 5 Apr 1992 08:55:12 +1000 (from jnc@ginger.lcs.mit.edu) Received: by ginger.lcs.mit.edu id AA17421; Sat, 4 Apr 92 17:55:03 -0500 Date: Sat, 4 Apr 92 17:55:03 -0500 From: jnc@ginger.lcs.mit.edu (Noel Chiappa) Message-Id: <9204042255.AA17421@ginger.lcs.mit.edu> To: big-internet@munnari.oz.au, jnc@ginger.lcs.mit.edu Subject: Re: supernetting Cc: jnc@ginger.lcs.mit.edu Something that I've realized in thinking about this algorithm and the metric problem I mentioned in the second message is that this algorithm is not in fact optimal as I claimed in the first message. It may also result in non-optimal routing. The test of all routes to subpieces taking the same next hop is in fact simply a test which says when you are "far enough away" that aggregation is probably reasonable. If you are not making any different choices about where to send traffic to the pieces of A, then it's doubtful that anyone who is sending traffic to A through you will want to. However, it may well be that the routing info could have been aggregated upstream of you with no harm. If R1 is getting to all of A through R2, and R2 gets to some of A through one router Ri1 and some through another Ri2, this algorithm would only aggregate leaving R1, whereas in fact it could have been aggregated leaving R2. So, it's not optimal aggregation. Also, even though R1 gets to all of A through R2, I can imagine topologies in which R3 would find it optimal to get to parts of A through R1 and parts of A through some other path. Clearly, if R1 has aggregated its "subroutes" to A into a single route, with consequent collapse of the metrics, R3 no longer has enough information to tell which path us optimal. Hmm. So, this algorithm is not optimal, just a simple algorithm which should work reasonably well (assuming an algorithm for picking a metric can be found which is guaranteed not to cause loops). Perhaps this is another case of the general rule in the Nimrod paper that there's an unavoidable cost/cost tradeoff in aggregation of routing information; the cost of sending routing information versus the cost of traffic taking non-optimal routes? Noel From owner-Big-Internet@munnari.oz.au Sun Apr 5 10:19:09 1992 Received: by munnari.oz.au (5.64+1.3.1+0.50) id AA20971; Sun, 5 Apr 1992 10:19:28 +1000 (from owner-Big-Internet) Return-Path: Received: from GINGER.LCS.MIT.EDU by munnari.oz.au with SMTP (5.64+1.3.1+0.50) id AA20968; Sun, 5 Apr 1992 10:19:09 +1000 (from jnc@ginger.lcs.mit.edu) Received: by ginger.lcs.mit.edu id AA17948; Sat, 4 Apr 92 19:19:03 -0500 Date: Sat, 4 Apr 92 19:19:03 -0500 From: jnc@ginger.lcs.mit.edu (Noel Chiappa) Message-Id: <9204050019.AA17948@ginger.lcs.mit.edu> To: big-internet@munnari.oz.au, dennis@mrbill.canet.ca, jnc@ginger.lcs.mit.edu Subject: Re: supernetting I checked the Supernetting document, and sure enough, CIDR does use configured boundaries for aggregation. This has the advantage of not only avoiding the problem with setting the metric, but it also allows 'exception' routing; i.e. if all A.Xi are inside a boundary, but A.Xq has picked up and moved elsewhere, you can still send an aggregate route for A out from the routers on the boundary. The routers connected to A.Xq also send out individual routes for A.Xq, so most routers in the system will have two routes, one for A and one for A.Xq. When routers elsewhere in the system go to route packets to A, they do so on a 'longest match' basis; i.e. packets for A.Xq will use that route, whilst all other A packets use the A route. Oh well, looks like we're in for a lot more tasty configuration in routers..... Noel From owner-Big-Internet@munnari.oz.au Sun Apr 5 14:02:40 1992 Received: by munnari.oz.au (5.64+1.3.1+0.50) id AA24493; Sun, 5 Apr 1992 14:02:48 +1000 (from owner-Big-Internet) Return-Path: Received: from MrBill.CAnet.CA by munnari.oz.au with SMTP (5.64+1.3.1+0.50) id AA24490; Sun, 5 Apr 1992 14:02:40 +1000 (from dennis@MrBill.CAnet.CA) Received: by MrBill.CAnet.CA id <105487>; Sat, 4 Apr 1992 23:02:34 -0000 From: Dennis Ferguson To: big-internet@munnari.oz.au, jnc@ginger.lcs.mit.edu Subject: Re: supernetting Message-Id: <92Apr4.230234gmt.105487@MrBill.CAnet.CA> Date: Sat, 4 Apr 1992 23:02:22 -0000 > we currently don't have a routing protocol which can tell us > automatically whether A.X1, or any other A.Xi, has alternate > connectivity ... or not > > I don't understand this at all. First, the whole point of dynamic > routing protocols is to find alternate connectivity when something breaks. If > by your comment you meant that no routing protocol provides you with that > information about alternate connectivity at all times (as opposed to telling > you in response to a break), that's still not true, since any link state > system can always tell whether A.Xi has alternate connectivity. I did want to answer this, though the point may be moot. If a router is aggregating A.Xi and just advertising to you a route to A, how are you going to find out that its route to A.X1 has gone away so you can use the alternate route you know of? Before and after the breakage you'll still just have a route to A, nothing will have changed. With your scheme the router might tell you by sending all of A.Xi unaggregated if it knew about the other route to A.X1 also, but there is no guarantee that it will know of other routes even if you do. Routing protocols can't find alternate connectivity when something breaks if they don't know that something is broken, and one of the effects of aggregation (and a desireable effect at that) is that the wider area routing isn't necessarily burdened with the comings and goings of routes which are subordinate to the aggregate when that breakage isn't something that can be fixed that way. You do, however, want to see transitions for routes you can do something about (because you have alternate connectivity), but we don't yet have a routing protocol which can tell automatically which parts of an aggregate need to be exposed to the wider area routing and which can just be hidden behind the aggregate. You need to configure this. I think the comment about link state routing systems is circularly incorrect. It is true that a link state system knows everything about connectivity within a single SPF area, but this is irrelevant since you can't aggregate anything within a single SPF area, only at its borders (look where OSPF and ISIS do it). If A.X1 is in another SPF area you not only can't tell if it has alternate connectivity, but you might not even know when A.X1 is unreachable if the only thing you have from the other area is the aggregate A. The question is, do you need to know if A.X1 is unreachable? The only way the router doing the aggregation is going to know this is if it is configured. Dennis Ferguson University of Toronto From owner-Big-Internet@munnari.oz.au Mon Apr 6 04:08:16 1992 Received: by munnari.oz.au (5.64+1.3.1+0.50) id AA10712; Mon, 6 Apr 1992 04:08:26 +1000 (from owner-Big-Internet) Return-Path: Received: from [158.222.1.2] by munnari.oz.au with SMTP (5.64+1.3.1+0.50) id AA10709; Mon, 6 Apr 1992 04:08:16 +1000 (from brian@lloyd.com) Received: by ray.lloyd.com (4.1/SMI-4.1/Brent-911016) id AA00335; Sun, 5 Apr 92 11:07:18 PDT Date: Sun, 5 Apr 92 11:07:18 PDT From: brian@lloyd.com (Brian Lloyd) Message-Id: <9204051807.AA00335@ray.lloyd.com> To: postel@ISI.EDU Cc: big-internet@munnari.oz.au In-Reply-To: postel@ISI.EDU's message of Fri, 3 Apr 92 09:26:27 PST <9204031726.AA24250@bel.isi.edu> Subject: supernetting Reply-To: brian@lloyd.com It is not necessary for a distant router to know that a network is unreachable so long as some router along the way knows that the network is unreachable. If you are aggregating routes to blocks of networks that are served by a single AS you need not know that a particular network is unreachable until you reach the service AS. At that point a router within the AS can send back the destination/network unreachable message. OK, so this is suboptimal. It will work and it does simplify routing. I am perfectly willing to accept the compromise. Brian Lloyd, WB6RQN Lloyd & Associates Principal and Network Architect 3420 Sudbury Road brian@lloyd.com Cameron Park, CA 95682 voice (916) 676-1147 -or- (415) 725-1392 From owner-Big-Internet@munnari.oz.au Tue Apr 7 02:36:46 1992 Received: by munnari.oz.au (5.64+1.3.1+0.50) id AA18054; Tue, 7 Apr 1992 02:36:59 +1000 (from owner-Big-Internet) Return-Path: Received: from SAFFRON.ACC.COM by munnari.oz.au with SMTP (5.64+1.3.1+0.50) id AA18044; Tue, 7 Apr 1992 02:36:46 +1000 (from fbaker@acc.com) Received: by saffron.acc.com (4.1/SMI-4.1) id AA04250; Mon, 6 Apr 92 09:36:14 PDT Date: Mon, 6 Apr 92 09:36:14 PDT From: fbaker@acc.com (Fred Baker) Message-Id: <9204061636.AA04250@saffron.acc.com> To: jnc@ginger.lcs.mit.edu Subject: Re: supernetting Cc: big-internet@munnari.oz.au, postel@isi.edu >> There's one simple algorithm which I have seen around for about 10 >> years which is guaranteed to produce optimal results; i.e. does the >> condensing as soon as it can, and results in the same forwarding >> choices in all cases as non-condensed information. >> Anytime you have a bunch of route A.X1, A.X2 .... A.Xn (where Xi is >> a subnet of network A, for instance), in updates you send you can >> replace all the separate routes to A.Xi with a single route to A >> whenever all the routes A.Xi in your table are through the same next >> hop. One additional item: the metric advertised must be the least among the available choices. If it is not, the aggregation can change route choices. Agreed that this is a sufficient condition; is it a necessary one? For example, if I have two neighbors on the same interface, can I aggregate their routes together? Is the aggregation point the next hop router, the subnet that the next hop router is in, or perhaps the fact that *I* am advertising the route ? Let me give you a case to think through: (a) One millistep beyond your suggestion, if I have a subnet A.1 and neighbors on it advertising A.2, A.3, ..., then I think I can simply advertise A. True? (b) Suppose I have a subnet B; I am B.1 and I have neighbors B.2 and B.3. B.2 is advertising routes to all subnets { A.even numbers } and B.3 is advertising routes to all subnets { A.odd numbers }. Does it work for me to advertise A? If so, and presuming that the answer generalizes (which is part of the question), then I can aggregate routes that have the same *next-hop-interface*, not just the *next-hop-router*. (c) Now, suppose I have two neighbors, B.2 and C.2; I am B.1 and C.1. B.2 is advertising routes to all subnets { A.even numbers } and C.2 is advertising routes to all subnets { A.odd numbers }. Does it work for me to advertise A? If so, and presuming that the answer generalizes (which is part of the question), then I can aggregate routes that the folks I'm advertising to will choose to send via me. I'd be curious if there exist counterexamples for these... Fred From owner-Big-Internet@munnari.oz.au Tue Apr 7 04:46:57 1992 Received: by munnari.oz.au (5.64+1.3.1+0.50) id AA20876; Tue, 7 Apr 1992 04:47:08 +1000 (from owner-Big-Internet) Return-Path: Received: from regal.cisco.com by munnari.oz.au with SMTP (5.64+1.3.1+0.50) id AA20864; Tue, 7 Apr 1992 04:46:57 +1000 (from dkatz@cisco.com) Received: by regal.cisco.com; Mon, 6 Apr 92 11:43:08 -0700 Date: Mon, 6 Apr 92 11:43:08 -0700 From: Dave Katz Message-Id: <9204061843.AA22235@regal.cisco.com> To: fbaker@acc.com, jnc@ginger.lcs.mit.edu Subject: Re: supernetting Cc: big-internet@munnari.oz.au, postel@isi.edu Right, the rule of thumb would be that you can announce an aggregated route for routes that have the same next-hop as seen from the neighbors to which you are advertising (namely, yourself). In the BGP/IDRP context, metrics (and looping) are non-issues, but aggregation of path information is. From owner-Big-Internet@munnari.oz.au Mon Apr 6 09:37:13 1992 Received: from wolf.cisco.com by regal.cisco.com with TCP; Mon, 6 Apr 92 09:37:12 -0700 Received: from munnari.OZ.AU by wolf.cisco.com with TCP; Mon, 6 Apr 92 09:40:38 -0700 Received: by munnari.oz.au (5.64+1.3.1+0.50) id AA18054; Tue, 7 Apr 1992 02:36:59 +1000 (from owner-Big-Internet) Received: from SAFFRON.ACC.COM by munnari.oz.au with SMTP (5.64+1.3.1+0.50) id AA18044; Tue, 7 Apr 1992 02:36:46 +1000 (from fbaker@acc.com) Received: by saffron.acc.com (4.1/SMI-4.1) id AA04250; Mon, 6 Apr 92 09:36:14 PDT Date: Mon, 6 Apr 92 09:36:14 PDT From: fbaker@acc.com (Fred Baker) Message-Id: <9204061636.AA04250@saffron.acc.com> To: jnc@ginger.lcs.mit.edu Subject: Re: supernetting Cc: big-internet@munnari.oz.au, postel@isi.edu Status: R >> There's one simple algorithm which I have seen around for about 10 >> years which is guaranteed to produce optimal results; i.e. does the >> condensing as soon as it can, and results in the same forwarding >> choices in all cases as non-condensed information. >> Anytime you have a bunch of route A.X1, A.X2 .... A.Xn (where Xi is >> a subnet of network A, for instance), in updates you send you can >> replace all the separate routes to A.Xi with a single route to A >> whenever all the routes A.Xi in your table are through the same next >> hop. One additional item: the metric advertised must be the least among the available choices. If it is not, the aggregation can change route choices. Agreed that this is a sufficient condition; is it a necessary one? For example, if I have two neighbors on the same interface, can I aggregate their routes together? Is the aggregation point the next hop router, the subnet that the next hop router is in, or perhaps the fact that *I* am advertising the route ? Let me give you a case to think through: (a) One millistep beyond your suggestion, if I have a subnet A.1 and neighbors on it advertising A.2, A.3, ..., then I think I can simply advertise A. True? (b) Suppose I have a subnet B; I am B.1 and I have neighbors B.2 and B.3. B.2 is advertising routes to all subnets { A.even numbers } and B.3 is advertising routes to all subnets { A.odd numbers }. Does it work for me to advertise A? If so, and presuming that the answer generalizes (which is part of the question), then I can aggregate routes that have the same *next-hop-interface*, not just the *next-hop-router*. (c) Now, suppose I have two neighbors, B.2 and C.2; I am B.1 and C.1. B.2 is advertising routes to all subnets { A.even numbers } and C.2 is advertising routes to all subnets { A.odd numbers }. Does it work for me to advertise A? If so, and presuming that the answer generalizes (which is part of the question), then I can aggregate routes that the folks I'm advertising to will choose to send via me. I'd be curious if there exist counterexamples for these... Fred From owner-Big-Internet@munnari.oz.au Tue Apr 7 05:12:34 1992 Received: by munnari.oz.au (5.64+1.3.1+0.50) id AA21395; Tue, 7 Apr 1992 05:12:43 +1000 (from owner-Big-Internet) Return-Path: Message-Id: <9204061912.21395@munnari.oz.au> Received: from DRAGON.BBN.COM by munnari.oz.au with SMTP (5.64+1.3.1+0.50) id AA21392; Tue, 7 Apr 1992 05:12:34 +1000 (from tmallory@BBN.COM) To: Fred Baker Cc: big-internet@munnari.oz.au, rschaaf@BBN.COM, tdonahue@BBN.COM, akoifman@BBN.COM Subject: Re: supernetting In-Reply-To: Your message of Mon, 06 Apr 92 09:36:14 -0700. <9204061636.AA04250@saffron.acc.com> Date: Mon, 06 Apr 92 15:06:41 -0400 From: Tracy Mallory Folks, I've a specific comment/question and some global comments. My goal is not to distract the ongoing discussions on route merging or metric selection, but to make sure, at least in my own mind, that the efforts are still on-track. Specific: My current picture is that routers attempt to merge as many network numbers as possible into a single mask/value pair. It seems that the address space covered by such a super-route need not be complete: it is enough that all routes known to the router with the appropriate prefix can be advertised to the same neighbor. If this is not the case then it seems unlikely that we can get enough compression to be worthwhile. If it is the case, then a router with a persistent incomplete database could become a block hole for networks reachable via other nets. If in fact the compression is governed by careful hand-maintained configuration at the borders of AS's, super AS's, etc., then this is probably not a scalable solution. Global: I've been watching the supernetting discussion for some time now, and am having some doubts that it will come together cleanly in the near future. The recent discussion on metric selection highlights the problem that we are no longer able to Keep It Simple S., and I'd add that we are having trouble Keeping It Clean (Kids ?-). My concern is that supernetting seems mostly to be an attempt to perform compression on large numbers of routes within the constraints of our flat address assignments, and without a clear model for hierarchy in the routing topology. Is it simply an attempt at a stop-gap solution to allow existing routers to cope (I profess ignorance of the original charter for the supernetting effort)? The compression issue has several facets, perhaps the most important three of which are 1) active routing table size, 2) cpu processing load for routing table maintenance, and 3) network load associated with routing table updates. (I've lumped message size, bandwidth, etc. into 3). Routing table size: I'd guess that it will be the case that all routers that perform more than local routing will need disks in the future, and that it will probably be sufficient to keep a cache of active routes for current traffic. Disks are cheap, and debugging network configuration tables is not. CPU load: No good answers, except that I'd hope to see a clear movement toward hierarchy in the address space sooner rather than later. Breaking the world into areas, and providing sub-optimum routing between areas, especially between more distant areas, seems like an obvious direction that IS-IS, OSPF, etc. use now. For topology information without immediate dependence on DNS, a new, topology-sensitive, assignment of autonomous system numbers is an idea that I haven't yet heard proposed. Network load: Has anyone used Lempel-Ziv, or some such, to simply compress a current BGP routing update? I've been burnt in the past, as has the networking community in general, by using knowledge-based compression techniques whose assumpions later proved to restrictive. (It was this last question that got me started writing today.) Thanks, Tracy From owner-Big-Internet@munnari.oz.au Tue Apr 7 06:31:56 1992 Received: by munnari.oz.au (5.64+1.3.1+0.50) id AA22991; Tue, 7 Apr 1992 06:32:07 +1000 (from owner-Big-Internet) Return-Path: Received: from GINGER.LCS.MIT.EDU by munnari.oz.au with SMTP (5.64+1.3.1+0.50) id AA22984; Tue, 7 Apr 1992 06:31:56 +1000 (from jnc@ginger.lcs.mit.edu) Received: by ginger.lcs.mit.edu id AA28052; Mon, 6 Apr 92 16:31:42 -0400 Date: Mon, 6 Apr 92 16:31:42 -0400 From: jnc@ginger.lcs.mit.edu (Noel Chiappa) Message-Id: <9204062031.AA28052@ginger.lcs.mit.edu> To: fbaker@acc.com, tmallory@bbn.com Subject: Re: supernetting Cc: akoifman@bbn.com, big-internet@munnari.oz.au, jnc@ginger.lcs.mit.edu, rschaaf@bbn.com, tdonahue@bbn.com Tracy, I think we backed into a topic (automatic aggregation of routes) which is a tough problem, but one which the original proposers bypassed (perhaps with good reason :-). While it's intellectually interesting, it's thus not clear that it's immediately relevant. The one potential fly in the ointment comes with your contention that the manual configuration issues will in fact be too onerous. This is a position that does not match that taken by the authors. If you are in fact correct, then it would seem that we would have to fall back to some automatic mechanism. I must confess that given the difficulties now being reported int the maintainence of policy routing databases, I sympathise with your skepticism of the scaling issues on the manual configuration, but not being in operations myself I can't say for sure. One thing I will say is that most systems which have complex details usually have problems which nobody forsees, and which only bite you once you've started to actually use it. Usually, the more complex the details, the longer the real-time period to shake these things out. It is this which leads me to be nervous about supernetting. Noel From owner-Big-Internet@munnari.oz.au Fri Apr 10 03:21:43 1992 Received: by munnari.oz.au (5.64+1.3.1+0.50) id AA11323; Fri, 10 Apr 1992 03:21:51 +1000 (from owner-Big-Internet) Return-Path: Message-Id: <9204091721.11323@munnari.oz.au> Received: from BBN.COM by munnari.oz.au with SMTP (5.64+1.3.1+0.50) id AA11319; Fri, 10 Apr 1992 03:21:43 +1000 (from kwe2@BBN.COM) From: "Kent W. England" Subject: Policy routing nightmare [Re: supernetting] To: jnc@ginger.lcs.mit.edu Cc: big-internet@munnari.oz.au In-Reply-To: <9204062031.AA28052@ginger.lcs.mit.edu> Date: Wed, 8 Apr 92 22:16:46 EDT Mail-System-Version: > > I must confess that given the difficulties now being reported int >the maintainence of policy routing databases, I sympathise with your >skepticism of the scaling issues on the manual configuration, but not being >in operations myself I can't say for sure. > ... > Noel Oh, an architect who recognizes operational implications of protocols! Thank you and bless you. :-) Operators would like to implement policies that have "global" (large-scale) significance, but we can only configure policies that have "local" significance (ie, a single router or a backbone). The coordination issue of making all the "local" policies "globally" consistent is the hard part. Actually, just trying to create all the necessary global policies, discover all the localities that must be involved, and then configure them locally in various places and make them stay around is a killer. Making inter-domain routing work is making policy routing work and it is a big piece of what a transit NOC does these days. (And costs a lot of money in staff time we could be spending making the Internet bigger instead of hairier.) If we create a new system of routing that has classless supernetting with lots of local optimization tweaks in it that have global significance, made by local experts who understand local topology and policy, and then expect someone to make consistent global policy with nothing more than fingers and keyboards, we will be perpetuating the current operational nightmare of policy routing coordination and maintenance. For example, my favorite supernetting trick is default routing. With every router out there pointing a default in god-knows-which-direction and not able to tell any other router (including the defaultee) which way it's pointing ... It's just crazy, as far as policy routing maintenance goes. The Internet is a maelstrom of datagram flotsam following defaults around to find the Big Bit Bucket. --Kent From owner-Big-Internet@munnari.oz.au Thu Apr 16 05:06:06 1992 Received: by munnari.oz.au (5.64+1.3.1+0.50) id AA16564; Thu, 16 Apr 1992 05:06:16 +1000 (from owner-Big-Internet) Return-Path: Received: from babyoil.ftp.com by munnari.oz.au with SMTP (5.64+1.3.1+0.50) id AA16561; Thu, 16 Apr 1992 05:06:06 +1000 (from stev@ftp.com) Received: from stev.hunny.ftp.com by ftp.com via PCMAIL with DMSP id AA01952; Wed, 15 Apr 92 15:07:51 -0400 Date: Wed, 15 Apr 92 15:07:51 -0400 Message-Id: <9204151907.AA01952@ftp.com> To: jnc@ginger.lcs.mit.edu Subject: Re: supernetting From: stev@ftp.com (stev knowles) Cc: big-internet@munnari.oz.au, postel@isi.edu, jnc@ginger.lcs.mit.edu Sender: stev@ftp.com Repository: babyoil.ftp.com Originating-Client: hunny.ftp.com Oh, one difficulty I forgot to mention about that scheme is how you pick the metric you advertise on the single route. Clearly, all the individual subroutes probably have different metrics. I'm not sure what the optimal algorithm is (by optimal I mean the algorithm which assigns the lowest possible number to the aggregate metric without creating routing loops). there are two problems here. if my connection to one regional goes down, i want the other to pick up my traffic ('cuase that is why i pay *twice*). this will require regional 1 to advertise high metrics, and require regional 2 to cut it off with smaller metrics. the subtle point here is that it will require regional 1 and 2 to talk together, and to cooperate. while i think that this supernetting will work in the beginning, i wonder if in a short amount of time all the exceptions that will start floating around will create more problems than it solved.