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

From: "Michael Behringer (mbehring)" <[email-masked]>
Date: Fri, 20 Jan 2012 17:42:29 +0100

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

---

From: Paul Mockapetris <[email-masked]>
Date: Sat, 21 Jan 2012 06:03:07 +0100

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.

At 05:42 PM 1/20/2012, you wrote:
>_______________________________________________
>ncrg mailing list
>[email-masked]
>https://www.irtf.org/mailman/listinfo/ncrg

---

From: Fred Baker <[email-masked]>
Date: Fri, 20 Jan 2012 23:49:34 -0800

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.
> 
> 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),
> Has anyone done a good description of the factors involved and their relationship?
> 
> i.e. simplistically
> 
> 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.

---

From: "Michael Behringer (mbehring)" <[email-masked]>
Date: Fri, 27 Jan 2012 17:59:46 +0100

Hi Paul, 

> -----Original Message-----
> From: Paul Mockapetris [mailto:[email-masked]]
> Sent: 21 January 2012 06:03
> To: Michael Behringer (mbehring); [email-masked]
> Subject: Re: [ncrg] Network Complexity Research Group: Meeting in
Paris
>     e.g. RFC 4984, not to mention NDN

Routing has been discussed, because it's what people in the room
understand. (My take)

Personally I'd be quite interested to hear thoughts on the complexity of
other systems as well, for example DNS (to pick a completely random
example ;-)   DNS works obviously very well, thus the complexity is
organised in a way that does NOT lead to catastrophic failures, thus my
feeling: We can learn something here. 
 
> Cost_Route_Calculations = K2 * Number-routes * log(Number-routes) *

So Keith Jones did a lot of work on TCO, which I think is a quite neat
"metric" for complexity, if well done. (see soap box 3 on this page:
http://networkcomplexity.org/wiki/index.php?title=Agenda) 
This goes down the bits and pieces, but (afaik) doesn't look into the
cost of a route update though. Intuitively, a more complex routing
algorithm consumes more CPU cycles thus costs more. Probably however
this is too far from monetary cost to make sense to compare?

You find some random collection of thoughts on 
http://networkcomplexity.org/wiki/index.php?title=Definition

> make it easier to think about the scaling properties of say, LISP vs

Something to elaborate on. Personally, I'd be quite interested to hear
your thoughts in more detail. Would you be prepared to do a presentation
at the NCRG?

Michael

---

From: Scott Brim <[email-masked]>
Date: Fri, 27 Jan 2012 12:48:49 -0500

> 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 tha…

Just because BGP is used as a conduit for multiple processes doesn't
increase complexity.  A conduit is no more complex because of the
various cables running through it.  The mux/demux behavior on each end
can be complicated but not complex, as long as interactions between
the clients using BGP (the cables) do not become interdependent.  Of
course this says nothing about the complexity of the processes that
use it such as routing :-p