Subject: Re: question on link state routing protocols

From: [email-masked] (Noel Chiappa)
Date: Fri, 3 May 2013 12:31:10 -0400 (EDT)

> From: Donald Eastlake <[email-masked]>

    > It's a link state protocol so it remembers the latest version it has of
    > each fragment of link state information. If it receives an older version
    > or the current version it already has, it ignores it. Only if it
    > receives a newer version does it flood it.

Yes, yes, I understood that already, thanks.

    > It might also send that same current fragment it has again if it hears
    > from some participant on a link that that participant has an old version
    > either by that participant transmitting an old version of the fragment

But that is 'unlikely' to happen (I'll give the scenario for it to happen
below).

When the node in question ('Ni') first hears the newest update ('UxN') from
some node node ('Nx'), it will have sent that update to all its neighbour
nodes, including this hypothetical 'node with old update' ('Nu').

Since this update is reliable (at least in all the link-state protocols I know
of, which are i) new ARPANET, ii) OSPF, and iii) IS-IS - there aren't very
many), i.e. the recipient has to send an ACK, and the source keeps sending the
update until it gets that ACK, Ni will have kept sending UxN to Nu, trying to
get an acknowledgement from Nu for UxN.

Not only that, but _all_ of Nu's _other_ neighbours will _also_ have been
sending update UxN to Nu, since all nodes send new updates to _all_ their
neighbours (other than they one they got it from), until they get an ack for
UxN from Nu.

And of course Nu will have been trying to send update UxN-1 to Ni since Nu got
that update (because if it had gotten any ack for UxN-1 from Ni, it would not
send UxN-1 to Ni again).

So for Ni to be able to get a repeated old update UxN-1 from Nu, i) _none_ of
Ni's acknowledgement messages for UxN-1 to Nu could have gotten through to Nu,
and ii) _none_ of the UxN updates (sent by _all_ of Nu's neighbours) could
have gotten through to Nu. This seems to me unlikely - unless all of Nu's
interfaces have failed for incoming packets at the same time - which also
seems unlikely.

Now, if Nu is a 'test' router with only one interface, which has failed for
incoming packets, perhaps that could actually produce this symptom - but
that's a pretty odd corner case.

Or perhaps Nu has a coding error, in which case all bets are off, and you can't
trust anything it says anyway...

    > or by that participant transmitting meta information on what versions it
    > has of what fragments which meta information reveals that it is out of
    > date.

I think the same analysis as above applies here too, no?

	Noel

---

From: Donald Eastlake <[email-masked]>
Date: Fri, 3 May 2013 14:46:50 -0400

Hi Noel,

On Fri, May 3, 2013 at 12:31 PM, Noel Chiappa <[email-masked]> wrote:
>    ...

Well, I think there are things like OLSR and others but let's just use
IS-IS. There are lots of people who know more about IS-IS than I do
but it is the link state routing protocol that I know the most about.

While it is certainly possible that IS-IS routers are connected by a
link with link level acknowledgements and re-transmission, such as an
802.11 link, common link technologies such as Ethernet don't do that
as I'm sure you know. You seem to be saying that there are IS-IS level
acks and retransmission. Could you point out where in ISO/IEC
10589:200 or RFC 1195 or where ever this IS-IS level PDU ack and
retransmission is specified? Perhaps I missed it.

As far as I know, an IS-IS router just sends updated link state
fragments on its various interfaces, other than the one it received it
on, and trusts to the CSNP/PSNP mechanism and the like to fix up any
problems from lost packets. (It's actually more complex. To avoid
storms, in general it just sets a flag associated with the link state
fragment and the port. This flag setting may or may not cause the
fragment to be sent on that port. If the same fragment is received on
that port before the router gets around to sending, the flag gets
cleared. It will send it quickly if there hasn't been much link state
traffic recently but if there are lots of link state updates going on,
it may delay a while before scanning for transmit flags that are still
set to avoid update storms.)

If I'm all confused about this, hopefully you can set me straight.

Thanks,
Donald
=============================
 Donald E. Eastlake 3rd   +1-508-333-2270 (cell)
 155 Beaver Street, Milford, MA 01757 USA
 [email-masked]

---

From: "Fred Baker (fred)" <[email-masked]>
Date: Fri, 3 May 2013 19:22:35 +0000

On May 3, 2013, at 11:46 AM, Donald Eastlake <[email-masked]> wrote:

> You seem to be saying that there are IS-IS level

yes, there are such acks and retransmission. You might look at https://tools.ietf.org/html/rfc1142 (which reflects the 1990 spec, not the 1992 spec, and so will have some differences from current reality, but is publicly accessible without money) and specifically sections 7.3.14 and 7.3.17.

---

From: Donald Eastlake <[email-masked]>
Date: Fri, 3 May 2013 16:46:21 -0400

OK.

What I was saying was correct for broadcast links, as Noel said. I
understand my thinking may be different from how others think, but I
consider broadcast links to be the general case and p2p links a
configured special case. So unless someone says they are talking about
p2p links, I tend to think about the broadcast link case.

In any case, I don't think even on a p2p link there is a very tightly
coupled protocol where an immediate acknowledgement is always sent and
sub-second timeout always causes retransmission if an acknowledgement
hasn't been received. The receipt of a link state fragment on a p2p
link just sets a flag to request that an PSNP be eventually sent as an
acknowledgment. There are various timers with multi-second defaults.

Of course, for the flooding to be reliable (and it isn't much use if
it isn't reliable), you have to have some mechanism that will
eventually force retransmission/synchronization. But it seems to me
that the mechanisms in IS-IS can be orders of magnitude slower than a
tightly coupled link retransmission protocol would be. So, depending
on how reliable and consistent the links are and how richly
interconnected the routers are and how rapidly topological changes are
happening, I think there is room for things to occur such as receiving
an old update from an adjacent router.

Thanks,
Donald

---

From: "Fred Baker (fred)" <[email-masked]>
Date: Fri, 3 May 2013 21:19:21 +0000

On May 3, 2013, at 1:46 PM, Donald Eastlake <[email-masked]>
 wrote:
> hasn't been received.

Sub-second timeout doesn't case a retransmission. There is a timeout, and it causes retransmission.

> it seems to me
> tightly coupled link retransmission protocol would be. 

Well, OK. We could discuss LAPB or IEEE 802.2's equivalent. My first thought would be to say "haven't we been there before?"

My second thought would be to wonder what the causes of loss and eventual timeout are. We could, for example, mention forward error correction on your favorite link layer. A part of me wonders if there would be value in an implementation setting a very short "first" timeout, perhaps on the order of a small multiple of the propagation delay of the link (tens to hundreds of milliseconds) and resending the PDU if an ack hasn't been received by that time. Or, whatever, just send every message twice on the assumption that the peer knows how to drop duplicates. How probable is the event, and what is the cost/benefit ratio of addressing it?

If we think that links have a BER on the order of 1e-11 or better, and that the primary source of non-congestive loss is bit errors (there are ways to prevent congestive loss), it seems to me that we are dealing with a high cost for the error rate if we're doing a lot more than my "first" timeout.

---

From: Tony Li <[email-masked]>
Date: Fri, 3 May 2013 14:51:02 -0700

> My second thought would be to wonder what the causes of loss and eventual timeout are. We could, for example, mention forward error correction on your favorite link layer. A part of me wonders if t…

In my humble experience, the most frequent cause of lost protocol packets is indigestion on the receiver side, and it's bizarrely rare to boot.  

Why would we worry about optimizing for a 10-sigma outlier, and even if we did that, wouldn't we want to send less, not more?

Tony

---

From: "Les Ginsberg (ginsberg)" <[email-masked]>
Date: Fri, 3 May 2013 23:49:43 +0000

ISO 10589:2002 (THE REAL STANDARD) is freely available here:

http://standards.iso.org/ittf/PubliclyAvailableStandards/index.html

Please let's not refer to RFC1142 which I thought we had successfully buried years ago.
:-)

   Les

> -----Original Message-----
> From: [email-masked] [mailto:routing-discussion-
> [email-masked]] On Behalf Of Fred Baker (fred)
> Sent: Friday, May 03, 2013 12:23 PM
> To: Donald Eastlake
> Cc: Noel Chiappa; <[email-masked]>
> Subject: Re: question on link state routing protocols
> 
> 
> yes, there are such acks and retransmission. You might look at
> https://tools.ietf.org/html/rfc1142 (which reflects the 1990 spec, not the
> 1992 spec, and so will have some differences from current reality, but is
> publicly accessible without money) and specifically sections 7.3.14 and
> 7.3.17.
> _______________________________________________
> routing-discussion mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/routing-discussion

---

From: "Stan Ratliff (sratliff)" <[email-masked]>
Date: Sat, 4 May 2013 00:58:16 +0000

> In my humble experience, the most frequent cause of lost protocol packets is indigestion on the receiver side, and it's bizarrely rare to boot.  

Not for wireless nets. ;-) With more and more mobile wireless popping up, and the need for those devices to participate in routing (instead of being and end-user device), the problem will get worse, IMO.

> Why would we worry about optimizing for a 10-sigma outlier, and even if we did that, wouldn't we want to send less, not more?

I completely agree that sending less is preferable, especially on "disadvantaged" links like RF. But from what I've seen, users *want* to deploy on the order of thousands of routing nodes in a network (think of a brigade of soldiers, each with 3 or 4 intelligent devices of some sort), do it wirelessly, *and* stream HD video all over the place… (Note that I said users *want* to do this, not that it's actually possible). ;-)

Regards,
Stan

---

From: Tony Li <[email-masked]>
Date: Fri, 3 May 2013 19:42:34 -0700

> Not for wireless nets. ;-) With more and more mobile wireless popping up, and the need for those devices to participate in routing (instead of being and end-user device), the problem will get worse…

Fair, but this is exactly why 802.11 has a built-in link layer mechanism.  No need to replicate it at a higher layer.

> I completely agree that sending less is preferable, especially on "disadvantaged" links like RF. But from what I've seen, users *want* to deploy on the order of thousands of routing nodes in a netw…

Good, so how about we focus on what's possible instead?

T

---

From: "Stan Ratliff (sratliff)" <[email-masked]>
Date: Mon, 6 May 2013 14:50:37 +0000

> Fair, but this is exactly why 802.11 has a built-in link layer mechanism.  No need to replicate it at a higher layer.

The inefficiencies in 802.11 make it (IMO) good for the last hop to an end-user, but lousy for transit. Add the problems of mobility in, and it becomes unusable in a routing context. 

> Good, so how about we focus on what's possible instead?

I'd love to see some focus on routing protocols deployed in greater numbers (e.g. hundreds, up to a thousand routers), running efficiently on lower bandwidth links like wireless. I think we'd get commercially viable product well before the defense-oriented use case I described above. This just seemed like a good opportunity to bring the topic up. 

Regards,
Stan

---

From: "Fred Baker (fred)" <[email-masked]>
Date: Mon, 6 May 2013 17:26:13 +0000

>From my perspective, that's the argument for solutions like TRILL and manet, which use layer 3 concepts on what I would consider a layer 3 network, just the sub-layer below IP. 

As to streaming HD video among a brigade of soldiers, I tend to think the requirements get overstated. Aerial platforms and other theatre assets can help a lot with the individual connectivity. In the US's 21st century wars, patrol actions have far outnumbered battalion or brigade level actions, even in places like the battle for Marjeh in 2009 when several battalions took positions to oust a well-deployed insurgency. When one is driving or walking somewhere and wondering "where might I find an IED" or "a sniper", what has usually happened is that a photo was taken on each of several reconnaissance flights, sophisticated algorithms have identified that someone walked through a field and perhaps spent some time at a specific place between photo shoots, and the patrol can be given a photograph with a circle around a place rather than a live feed, or a one-frame-per-second feed, getting the same operational results. Their return is likely to be the same, and more about "am I looking at the same place you are" than "let me give you more detail on that."

The places where one hears a lot about large scale sensor networks are similarly not usually everyone-streaming-HD-to-a-certain-place. Deborah Estrin published several papers in the late 1990's about tracking California wildfires, for example. Her model was to distribute a large number of styrofoam "golf balls" with the intelligence and power resources one might find in a wristwatch, which would communicate back to a central location about what they found. She started from IP, but pretty quickly discovered that what was really needed in the application was something more akin to an isobar or isotherm map, and the best way to deliver it was to summarize information from sensor to sensor rather than having sensors relay datagrams for each other - a concept that I suspect fed into the CCN space. Putting that into a military context, one could imagine a field of sensors distributing data about the amount of motion in their areas, which would quickly settle down into "there's a lot of noise in this general field" that might relate to dust or plants, and "there is a solid object moving at a certain rate in the vicinity of a certain set of sensors".

As seems to always be the case, what users want may have no bearing on what they actually need.