Subject: [Roll] More comments and some questions on the protocol-survey draft

From: Alexandru Petrescu <[email-masked]>
Date: Thu, 29 Jan 2009 20:12:35 +0100

In this mail I argue about:
-Table Scalability can't be a factor to disqualify any protocol (specs
  are eminently silent about how tables are represented and thus
  how they scale).
-Loss Response can't be a factor to discard NEMO (MR only sends to HA,
  not to n destinations upon link up/down events).
-Control Cost tests can very well accept MIP-based NEMO protocol in that
  MIP and ND have rate limitation.

-Asking about Link and Node cost metrics: maybe that's it actually.

-Suggest corrections to the use of "Neighbor disovery" term, makes think
  of "Neighbor Discovery"
-suggest that ND doesn't risk storms of replied RAs to a RS, because
  they're randomly spaced in time.
-suggest that addresses being a direct expression of the underlying
  network topology is a deep Internet assumption that can't be changed.
-ask about necessity of asymmetric support.

For details, when time permits, see below.

> 4.2.  Table Scalability
> 
> Scalability support for large networks of sensors is highlighted as a
>  key requirement by all three application requirements documents.
[...]
> More precisely, routing table size scaling with O(N) or O(L) fails. A
>  table that scales O(D) (assuming no N or L) passes.

This is a problem of representing data structures, and not of the
protocol per se.  I hope some protocol isn't discarded by some
dangerously false assumptions on the way it represents its so-called
tables in the memory.

For example there exist various implementations of Binding Cache (of
MIP) and Neighbor Cache (of ND) which are more or less efficient.  Some
are quick at finding, others at inserting, others are smaller, and so on.

Also related to this:
> For example, a node with 4kB of RAM, a typical amount for top-end 
> microcontrollers, cannot store full neighbor state when it has 1000 
> other nodes nearby.

LEt's see: which addresses IPv4 or IPv6?  How are they represented?  Are
they covered by a long or short prefix length (subnet address)?  Which
link layer?

And is it assumed that a micro-controller needs to talk to 1000
neighbors at the same time?  Because the Neighbor Cache only holds the
neighbors to which a node has recently talked to, there are tweakable
expiry timers.  And I doubt there exists a link layer supporting this
assumption of one-to-1000 simultaneous neighbors communication.

> 4.3.  Loss Response
> 
> In low power and lossy networks, links routinely come and go due to 
> being close to the signal-to-noise threshold at the physical layer. 
> It is important that link churn not trigger unnecessary responses by 
> the routing protocol.
[...]
> A protocol which requires many link changes to propagate across the 
> entire network fails.  Protocols which constrain the scope of 
> information propagation to only when they affect routes to active 
> destinations, or to local neighborhoods, pass.  Protocols which allow
>  proactively path maintenance pass if the choice of which paths to 
> maintain is user-specified.
> 
> More precisely, loss responses that require O(N) transmissions fail, 
> while responses that can rely on O(1) local broadcasts or O(D) route 
> updates pass.

I think Mobile IP-based NEMO protocol should pass this test.  Whenever
the Mobile Router's egress interface comes down or up only the HA (Home
Agent) is let know about it, it's not O(N), it's simply 1.  Besides, it
has a retransmission control specified, such as to not make too much noise.

> 4.4.  Control Cost
[...]
> a common case [I-D.ietf-roll-indus-routing-reqs].  In terms of 
> routing structure, any proposed LLN routing protocol ought to support
>  the autonomous organization and configuration of the network at the 
> lowest possible energy cost [I-D.ietf-roll-urban-routing-reqs].
> 
> All routing protocols must transmit additional data to detect 
> neighbors, build routes, transmit routing tables, or otherwise 
> conduct routing.  As low-power wireless networks can have very low 
> data rates, protocols which require a minimum control packet rate can
>  have an unbounded control overhead per data packet.  This is 
> particularly true for event-driven networks, which only report data 
> when certain conditions are met.  Regions of a network which never 
> meet the condition can be forced to send significant control traffic 
> even when there is no data to send.  For these use cases, hard-coded 
> timing constants are unacceptable, because they imply a prior 
> knowledge of the expected data rate.
> 
> Of course, protocols require the ability to send at least a very 
> small amount of control traffic, in order to discover a topology. But
>  this bootstrapping discovery and maintenance traffic should be 
> small: communicating once an hour is far more reasonable than 
> communicating once a second.  So while control traffic should be 
> bounded by data traffic, it requires some leeway to bootstrap and 
> maintain a long-lived yet idle network.
> 
> In the case of control traffic, the communication rate (sum of 
> transmissions and receptions at a node) is a better measure than the 
> transmission rate (since energy is consumed for both transmissions 
> and receptions).  Controlling the transmission rate is insufficient, 
> as it would mean that the energy cost (sum of transmission and 
> receptions) of control traffic could grow with O(L).
> 
> A protocol fails the control cost criterion if its per-node control 
> traffic (transmissions plus receptions) rate is not bounded by the 
> data rate plus a small constant.

Neighbor Discovery and Mobile IPv6 both have built-in rate limitation
mechanisms.

> For example, a protocol using a beacon rate only passes if it can be
>  turned arbitrarily low, in order to match the data rate.

Both MIP and ND do that.  It's turned arbitrarily low by an
administrator.  I hope that's ok.

> 4.5.  Link and Node Cost
> 
> These two criteria specify how a protocol chooses routes for data 
> packets to take through the network.  Classical routing algorithms 
> typically acknowledge the differing costs of paths and may use a 
> shortest path algorithm to find paths.  This is a requirement for low
>  power networks, as links must be evaluated as part of an objective 
> function across various metric types, such as minimizing latency and
>  maximizing reliability [I-D.ietf-roll-indus-routing-reqs].
> 
> However, in low power networks it is also desirable to account for 
> the cost of forwarding through particular routers.  Applications 
> require node or parameter constrained routing, which takes into 
> account node properties and attributes such as power, memory, and 
> battery life that dictate a router's willingness or ability to route
>  other packets.  Home routing requirements note that devices will
> vary in their duty cycle, and that routing protocols should prefer
> nodes with permanent power [I-D.ietf-roll-home-routing-reqs].  The
> urban requirements note that routing protocols may wish to take
> advantage of differing data processing and management capabilities
> among network devices [I-D.ietf-roll-urban-routing-reqs].  Finally, 
> industrial requirements cite differing lifetime requirements as an 
> important factor to account for [I-D.ietf-roll-indus-routing-reqs]. 
> Node cost refers to the ability for a protocol to incorporate router
>  properties into routing metrics and use node attributes for 
> constraint-based routing.
> 
> A "pass" indicates that the protocol contains a mechanism allowing 
> these considerations to be considered when choosing routes.

Sorry, which considerations more precisely?

Do you mean we don't have a routing metric saying "energy level"/
"memory size"?  Is it this?

If yes I think I could make a separate thread with various reflections
on the topic.

> Neighbor discovery is a critical component of any routing protocol.

Terminology: as already described in the draft, "Neighbor Discovery"
being a specific Internet-area protocol RFC 4861, independent of any
routing protocol (could be called the ARP of IPv6).  Thus reading the
above phrase may make one think ND is a critical component of any
routing protocol - it's not.  The lexical situation is worse knowing
that OSPF calls a Neighbor _almost_ the same thing as an ND neighbor.

As such, the above phrase is very difficult to parse.

> 8.1.  IPv6 Neighbor Discovery
> 
> IPv6 neighbor discovery provides mechanisms for nodes to discover 
> single-hop neighbors as well as routers that can forward packets past
>  the local neighborhood.  There is an implicit assumption that the 
> delegation of whether a node is a router or not is static (e.g., 
> based on a wired topology).  The fact that all routers must respond 
> to a Router Solicitation requires that the number of routers with a 
> 1-hop neighborhood is small, or there will be a reply implosion.

RAs sent in response to a RS are randomly spaced in time, tunable timer, 
thus I would qualify that neither as explosion nor as implosion, because 
they're not simultaneous.  ND specifiers often complained about 'storms' 
they experienced with faulty cards and ARP and thus felt ND could do 
better, I think it went on ok.

> Furthermore, IPv6 neighbor discovery's support of address 
> autoconfiguration assumes address provisioning, in that addresses 
> reflect the underlying communication topology.

I'm afraid this touches on a fundamental Internet design: yes addresses
reflect the underlying communication topology.  So what?  I hope the
intention is not to design some protocol which assumes the addresses do
not reflect the underlying communication topology.

I'm afraid we may have a big big misunderstanding here.

> IPv6 neighbor discovery does not consider asymmetric links.

And?  Does ROLL consider asymmetric links?  Which ones?  In what are
they asymmetric?  Bandwidth?  Reachability?  MTU?

For example, whereas WiFi radio channel may look asymmetric bandwidth
ul/dl (from the MAC layer), when the ND looks at that MAC it sees it
symmetric.

Maybe ND is enough for these apparently asymmetric links?

> Nevertheless, it may be possible to extend and adapt IPv6's 
> mechanisms to wireless in order to avoid response storms and 
> implosions.

I think this has already been done with many protocols in IPv6 space.
ND is a typical example, but also Mobile IPv6.  I think OSPF for IPv6
also has means to avoid storms and implosions.

Or I don't understand at all the requirement.

Alex

_______________________________________________
Roll mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/roll