Re: What is the limit? (was RE: multi-homing fixes)
| If you had a router that could handle 2^32 prefixes, it will handle | the IPv4 Internet. Forever. The whole growth curve argument is | gone. Sure, just about anybody can build a router which has 2**32 forwarding directives burned into ROM. It gets easier with fewer interfaces, too. But, who wants a static network? In the early 90s we had a network where you could wait a week before the core of the Internet adapted to your topology change, and changed its routing towards a particular prefix. It wasn't really much fun. So, even though I convert (x/2)² into x/2 in what passes for my head, I think that it's pretty clear that the problem isn't the state at any given moment, but rather the rate of change of that state. | The global routing table cannot grow exponentially forever. And neither can the rate of change. The problem only has to be Too Hard to compute affordably, not NP-complete. (I bet others are already explaining this later in my $MAIL, but I seem to be stuck on doing things linearly today...) | For reference, there are approximately 10^80 electrons in the | universe (per several physics sources I found on the net). Oh cool, particle physics. How many degrees of freedom do these electrons have? Interesting point: a prefix in the global routing table CAN have one or more moments of inertia. Maybe something multilevel is even better. Something like following the contributions of constituent quark spin to a hadron or nucleon or would certainly be even more appropriate, since indeed an IGP perturbation can lead to fluctuation at the EGP (i.e. BGP) level, causing announcements to rotate about a set of interfaces. I bet Ahuja & Labowitz have even recorded this happening. Hey maybe there is some deep irony at work in that one can analogize the work of Dyson Sr (QED, QCD) and Jr (ICANN) in this way... | Not to minimze the short term issue, but to hand wave and say | "it's exponential and we'll never get ahead of it" is crap. It | won't be forever, so let's get ahead of it. There's lots of irony in that too. Other than the hand-wave, how do you propose to get (and stay) ahead of it? Sean.
On Wed, Aug 29, 2001 at 04:41:17PM -0700, Sean M. Doran wrote:
There's lots of irony in that too. Other than the hand-wave, how do you propose to get (and stay) ahead of it?
Take your pick, having people working on all of them would be a good plus. 1) More power in routers. A) Faster CPU's. B) More memory. C) More bandwidth in and out of the route processor. D) Multiprocessor designs. 2) Modification to registry allocation procedures to allow entities a greater probability of having a single large block. (Basic goal, reduce the number of prefixes per AS.) 3) Enhancements to current routing protocols (short term bandaids). A) State caching (so many changes are oscillations, why do a full recompute each time). B) Limiting the propagation of routes. Many of the "TE" routes today need to go to a small subset of the AS's that they reach today. C) Prioritizing updates. 4) New routing protocols, possibly using one or more of the following ideas / observations: A) The topology of the network is relatively static. That is links go up and down, but in general don't move. B) Many routing updates can happen much more slowly, particularly if it makes some updates happen more quickly. For instance, when two big providers bring up a new peering link, if that takes 45 seconds to propagate rather than 10, that's ok. When a link fails and there is a reroute, it should happen as quick as possible. C) There is no reason to withdraw a route (from the FIB at least, perhaps from some part of the RIB) if there is no alternative path. Routing to a black hole is routing to a black hole. D) Routes will always need to be carried for traffic engineering purposes. Provide mechanisms to control them. E) Inside of a single domain of control a protocol could 'share processing' across the network. F) Routing protocols that can take advantage of multiple CPU's are a good thing. Allowing them to be distributed across the network (in a more equitable fashion) may be useful. G) Offloading some route calculations may be useful. (Thinking about moble users going through a 'slow' (1-10 second) secondary routing fabric on their first connection in a new location). H) Cache redundant calculations. When there are 10 deaggregated routes in a row, do the O(complex) calculation first, and an O(1) lookup for the next 9. I) Potentially introduce hierarchy into the routing system. J) Sometimes keeping more state means doing less computation (and sometimes the opposite). K) Routing out of band can sometimes be more efficient. 5) New offloading protocols, systems, and service offerings: A) Do more fail over via DNS, web redirects, and other systems. Reduce the dependency on the routing system for those tasks. B) Have service providers bilaterally share IP space, and only deaggreate to each other to provide for redundant customers. C) Provide better support for 'floating IP' services (where the same IP 'exists' in multiple places at the same time. D) Make customers care less about their IP addresses. (Eg, move web servers closer to the core, leaving only access at the edge, allowing everything to outgoing NAT.) E) Sometimes 'burning into ROM' (or semi-permanent routing) is a good thing, many things are not dynamic, don't treat them as such. F) Authenticating routing information is a good thing, even if it doesn't happen in real time. G) Being able to get route attributes that allow you to tune priority and the like is a good thing, even if it doesn't happen in real time. H) QOS controls might be better applied to routing updates than to traffic. I'll work on some more ideas, that should keep people busy (and the debate hopping) for some time. -- Leo Bicknell - bicknell@ufp.org Systems Engineer - Internetworking Engineer - CCIE 3440 Read TMBG List - tmbg-list-request@tmbg.org, www.tmbg.org
On Wed, Aug 29, 2001 at 08:38:31PM -0400, Leo Bicknell wrote:
1) More power in routers.
This is useful and may give us enough time to get something better in place. But note that this only tackles the routing engine (the part that deals with such things like BGP & ISIS updates). The other part - the big fast forwarding engines - is where things are already getting very tricky. I suspect we may hit the edge in the forwarding engines first.
2) Modification to registry allocation procedures to allow entities a greater probability of having a single large block. (Basic goal, reduce the number of prefixes per AS.)
Ohh! Renumbering! If everyone renumbered such that there was one prefix per AS at (nearly) all times, then we would be in a *much* better position. The only known way to really make routing systems scale is to have the stuff the routing system deals with (the routing goo) match closely the topology of the system. If we could split the current 'address' into host identifiers and routing goo, then I suspect we would be a lot better off.
A) State caching (so many changes are oscillations, why do a full recompute each time).
Yup - see the various I'll Be Back work and the like.
B) Limiting the propagation of routes. Many of the "TE" routes today need to go to a small subset of the AS's that they reach today.
This is hard - its very hard to tell how far a route really needs to propogate. The NOPEER work has some potential here.
C) Prioritizing updates.
How? Needs much thought here.
B) Many routing updates can happen much more slowly, particularly
Aka route dampening. Query - how many ISPs use the RIPE dampening parameters?
C) There is no reason to withdraw a route (from the FIB at least, perhaps from some part of the RIB) if there is no alternative path. Routing to a black hole is routing to a black hole.
I suspect that this case only covers a small number of routes. I suspect that most routes have some covering aggregate; thus there is nearly always someplace else for the traffic to go.
I) Potentially introduce hierarchy into the routing system.
This is going to be needed.
K) Routing out of band can sometimes be more efficient.
I can tell you lots of horror stories about this. Trying to push traffic one way while the routing goes another can lead to undetected black holes. Not pretty.
A) Do more fail over via DNS, web redirects, and other systems. Reduce the dependency on the routing system for those tasks.
Howard Berkowitz is writting an informational draft on this sort of thing; please give him feedback.
B) Have service providers bilaterally share IP space, and only deaggreate to each other to provide for redundant customers.
That would seem to require the ISPs deeply cooperate with each other... Dunno if that is ever really going to happen.
C) Provide better support for 'floating IP' services (where the same IP 'exists' in multiple places at the same time.
That already works pretty well (anycast addresses). Problems I've seen with it have been detecting failures (see aroot experiment). You need really good monitoring systems in place to keep this sort of stuff working. --asp@partan.com (Andrew Partan)
| If you had a router that could handle 2^32 prefixes, it will handle | the IPv4 Internet. Forever. The whole growth curve argument is | gone.
Sure, just about anybody can build a router which has 2**32 forwarding directives burned into ROM. It gets easier with fewer interfaces, too. But, who wants a static network?
I do. and probably 99% of the userbase like me. Because, when *we* say static, we mean different to when you say static. Humpty Dumpty rules. Really, nobody wants dynamic routing. They just pretend its a feature, but given the amazingly static nature of cables in the ground and edge devices Kansas miraculously stays in the mid-west, I say in Brisbane mostly and what I want is a static declaration in the routing model of the world that says Brisbane is not in Kansas. And, based on what I hear from smarter people that is what BGP says. How much of the updates you see actually change anything about which of your links packets flow on? I bet its marginal change, not earth shattering change mostly. I mean, do you *WANT* to live on the edge of mt etna, or would you rather look at it from a stable place? Dynamic updates are chicken little. "THEY SKY IS FALLING! I CAN'T SEE <x>" followed 1/2 an hour later by "oh, yes I can" Better to say nothing to the world, and tell your next door friend who isn't under the cardboard sheet so they can help lift it for you. If you want dynamicism, do it locally please.
In the early 90s we had a network where you could wait a week before the core of the Internet adapted to your topology change, and changed its routing towards a particular prefix. It wasn't really much fun.
And guess what? Now we have a network where it can take two weeks to make an upstream edit their hand-crafted BGP and nothing has changed. Your point was?
And neither can the rate of change. The problem only has to be Too Hard to compute affordably, not NP-complete.
This is like a mathematical version of Godwins law. But, there would appear to be people who assert its not unafordable to compute the routes for the current, and the forseeable network. so its neither NP complete nor unaffordable. Its also irrelevant because it looks like prefix collapse on the global /24 or /32 table is workable for most% of the world forever in internet terms. Saying CiDR makes BIFF admit the NETWORK FAILED is well, like BIFF. Just because its set in capitals, doesn't make it TRUE!
| "it's exponential and we'll never get ahead of it" is crap. It | won't be forever, so let's get ahead of it.
There's lots of irony in that too. Other than the hand-wave, how do you propose to get (and stay) ahead of it?
Sean.
By filtering the /24's which when removed, drop > 1% < 20% of the routing table size (I invented those numbers) but lose >30% (I invented that one too) of the dynamicicsm of silly/pointless route annoucements, and appear to cause (after the two weeks of finding all the CNN like agencies on /24) a markedly marginal loss of connectivity for most% of the network. As if you also don't expect this to (a) work, and (b) continue to make previously believed exponential growth become more linear. Market forces also help. dotcom crash == merger & acquisitions == longterm baseline no questions asked handback for aggregation == less demand for new nets == less rate of growth of prefixes. rate of growth is measured in months and years. BGP updates are in tens of seconds. the relationships are not exactly 1:1 ratio are they? Its coming. Rant as much as you like, filtering is back on the agenda. And, I am willing to suggest once the brouhaha settles down, we all find it suprisingly pleasant afterwards. NOPEER is probably as relevant, because the /24 issue is about a more local horizon of announcement. As Geoff Huston says, NOPEER flies as far as your money. Randys /24 filters meet it at that point, and we all win. Mind you, those two weeks of CNN suing everyone in sight is going to be fun! My hope is this makes everyones mailfilters. I mentioned Godwins law so it should do. cheers -George
there would appear to be people who assert its not unafordable to compute the routes for the current, and the forseeable network.
and there are those of us who think we can probably do so iff we stop the explosion of /24s. randy
participants (5)
-
Andrew Partan
-
George Michaelson
-
Leo Bicknell
-
Randy Bush
-
smd@clock.org