Re: [ncrg] Network Complexity Research Group: Meeting in Paris

[Fred Baker <[e-mail]>]

On Jan 20, 2012, at 9:03 PM, Paul Mockapetris wrote:

> I live in Paris, so I'm expecting to attend.  This isn't really a proposal for an agenda item, though if it piques anyone's interest, I'm happy to discuss.
> 
> I have a question (not being a router person):
> 
> 1. BGP seems to be one of the the preferred lab animals for complexity folks, or at least the canonical example.
> 2. We have been hearing that scalability of the current routing system is a big problem (at least for core routers),
>   e.g. RFC 4984, not to mention NDN
> 
> Has anyone done a good description of the factors involved and their relationship?
> 
> i.e. simplistically
> 
> Cost_router=Cost_interfaces + Cost_Backplane + Cost_Route_Calculations
> 
> Cost_interfaces = K1 * Number_routes * Number_interfaces
> 
> Cost_Route_Calculations = K2 * Number-routes * log(Number-routes) * Updates_sec
> 
> etc, etc.
> 
> Obviously, it will vary somewhat between IPv4 and IPv6 because addresses are bigger, and whether you are implementing a lot of VPNs, interface speeds, etc, etc.
> 
> But it seems like fundamental limits would lurk wherever there are exponential or superlinear or linear costs that would be good guidelines in system design.  The utility of the model would be to make it easier to think about the scaling properties of say, LISP vs NDN.

There has been some interesting work on complexity, and we've had a couple of workshops. You might enjoy some of the papers written by http://berkeley.intel-research.net/sylvia/ on complexity.

I think at least part of what we have concluded - at least what I have concluded - is that the fundamental issues of complexity aren't so much in what is actually done, but what is perceived as being done. For me, a canonical example is the behavior of TCP congestion control and its interactions with, for example, streaming media. You're familiar with the histrionics and heuristics that TCP goes through in figuring out what its parameters should be. Adaptive Bitrate Video sits atop that, and tries to figure out from video segment to video segment how to encode the data in order to deliver the best quality picture/sound for a mumble second interval, and to do so makes crude measurements - it downloads one video segment, measures its size in bytes and the time it took to deliver, calculates, and says "well, gee, the encoding that will get the net video segment here in time with the most information is..." - and uses that encoding on the next file. If TCP had an API that could deliver an estimated bit rate (MSS*cwnd/RTT), TCP could probably deliver at least as good an answer, and probably better. We don't want to complicate the application with variables like loss rate, cwnd, MSS, or RTT, but a floating point number in some multiple of bits per second could be pretty useful.

Another example might be the difference between OSPF and TBRPF. Both use SPF trees, and TBRPF could use OSPF messages if it chose to. The big difference between the two from an external perspective is that TBRPF exchanges a lot less messages (and therefore uses less power) than OSPF. Part of that is that where OSPF has every router or DR advertise every LSA to all of its neighbors, TBRPF presumes that the only router that really needs to advertise a given LSA to a given neighbor is the router that the neighbor will choose as its next hop - if that works, the rest are all surplus. Internally, each router calculates not only its own route table but (in a limited sense, as in "will it select me as the next hop for this prefix") all of those of its immediate neighbors. A lot more spinning of wheels under the hood, but externally, less noisy and less complex.

I don't know that anyone has done a full analysis of BGP. It's probably fair to say that modern BGP isn't a routing protocol; it's an information distribution protocol, and one of the processes that uses its information routes IP. Other processes route MPLS LSPs by one of several rubrics, route IP datagrams via MPLS LSPs, manage remote filters, and other things. That's a lot of complexity right there, let alone "so how do we make sense of MEDs and all that?". There is some good work being done by Tim Griffin at Cambridge, however, who is trying to put mathematical structures around BGP to determine whether the intersection of an announcement policy and an acceptance policy results in stable routing. That will be pretty useful once we understand it better.

> At 05:42 PM 1/20/2012, you wrote:
>> Just a short note that the NCRG will have a meeting at the upcoming IETF
>> in Paris. The slot is not yet known.
>> 
>> This is also a call for agenda items: If you would like to present your
>> work on network complexity, please let us know!
>> 
>> See:
>> http://irtf.org/ncrg
>> http://networkcomplexity.org/
>> 
>> Michael
>> _______________________________________________
>> ncrg mailing list
>> [e-mail]
>> https://www.irtf.org/mailman/listinfo/ncrg
> 
> _______________________________________________
> ncrg mailing list
> [e-mail]
> https://www.irtf.org/mailman/listinfo/ncrg