Subject: [Roll] Metric document: draft-mjkim-roll-routing-metrics-00

From: JP Vasseur <[email-masked]>
Date: Thu, 18 Sep 2008 07:21:16 +0200

Dear all,

It might be a good time to start the discussion on
draft-mjkim-roll-routing-metrics-00. As pointed out during the meeting in
Dublin, this is a very first draft and the idea was to start with a large
set of possible metrics. We all know that many of the proposed metrics may
not be realistic especially in large scale networks (we learnt from the past
with ARPANET !) but again the idea was to start listing all potential
candidates and go from there.

Comments are very welcome. If OK with you, let¹s concentrate on the
technical aspects (editorial issues to be worked out at a larger stage).

Thanks.

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

---

From: David Meyer <[email-masked]>
Date: Fri, 19 Sep 2008 14:21:24 -0700

> candidates and go from there.

	All,

	Nice start. I've made several comments (both types,
	avoiding editorial where possible) in-line below. Search
	for dmm> 

	Thnx,

	Dave

Networking Working Group                                     M. Kim, Ed.
Internet-Draft                                                        KT
Intended status: Standards Track                        JP. Vasseur, Ed.
Expires: January 5, 2009                                   Cisco Systems
                                                                H. Chong
                                                                      KT
                                                            July 4, 2008

    Routing Metrics used for Path Calculation in Low Power and Lossy
                                Networks
                  draft-mjkim-roll-routing-metrics-00

Status of this Memo

   By submitting this Internet-Draft, each author represents that any
   applicable patent or other IPR claims of which he or she is aware
   have been or will be disclosed, and any of which he or she becomes
   aware will be disclosed, in accordance with Section 6 of BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF), its areas, and its working groups.  Note that
   other groups may also distribute working documents as Internet-
   Drafts.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   The list of current Internet-Drafts can be accessed at
   http://www.ietf.org/ietf/1id-abstracts.txt.

   The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html.

   This Internet-Draft will expire on January 5, 2009.

Abstract

   This document specifies routing metrics used in path calculation for
   Routing Over Low power and Lossy networks (ROLL).  Low power and
   Lossy Networks (LLNs) have unique characteristics compared with
   traditional wired networks or even with similar ones such as mobile
   ad-hoc networks as indicated in several application-specific
   requirements documents.  Since typical IGP routing metrics such as
   hop counts or link metrics are not sufficient for LLNs, 
   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
dmm> 
dmm> might give a sentence or two about why traditional IGP
dmm> metrics aren't sufficient in the LLN context

   this document
   specifies a new set of required link and node metrics suitable to

Kim, et al.              Expires January 5, 2009                [Page 1]

Internet-Draft          Routing Metrics for LLNs               July 2008

   LLNs.

Table of Contents

   1.  Note . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  3

   2.  Terminology  . . . . . . . . . . . . . . . . . . . . . . . . .  3

   3.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  3

   4.  Node attributes  . . . . . . . . . . . . . . . . . . . . . . .  5
     4.1.  Computational resources  . . . . . . . . . . . . . . . . .  6
     4.2.  Residual Energy  . . . . . . . . . . . . . . . . . . . . .  6
     4.3.  Current workload . . . . . . . . . . . . . . . . . . . . .  7
     4.4.  Node latency . . . . . . . . . . . . . . . . . . . . . . .  7
     4.5.  Data Aggregation attribute . . . . . . . . . . . . . . . .  7
     4.6.  Node degree  . . . . . . . . . . . . . . . . . . . . . . .  8
     4.7.  Dynamicity . . . . . . . . . . . . . . . . . . . . . . . .  9
     4.8.  Node reliability . . . . . . . . . . . . . . . . . . . . .  9

   5.  Link attributes  . . . . . . . . . . . . . . . . . . . . . . .  9
     5.1.  Bandwidth  . . . . . . . . . . . . . . . . . . . . . . . . 10
     5.2.  Reliability (Quality)  . . . . . . . . . . . . . . . . . . 10
     5.3.  Propagation delay  . . . . . . . . . . . . . . . . . . . . 10

   6.  Open issues  . . . . . . . . . . . . . . . . . . . . . . . . . 10

   7.  Security Considerations  . . . . . . . . . . . . . . . . . . . 11

   8.  IANA Considerations  . . . . . . . . . . . . . . . . . . . . . 12

   9.  Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 12

   10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 12
     10.1. Normative References . . . . . . . . . . . . . . . . . . . 12
     10.2. Informative References . . . . . . . . . . . . . . . . . . 12

   Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 12
   Intellectual Property and Copyright Statements . . . . . . . . . . 14

Kim, et al.              Expires January 5, 2009                [Page 2]

Internet-Draft          Routing Metrics for LLNs               July 2008

1.  Note

   Some of the routing metrics defined in this document may be subject
   to change or may even be removed in light of the routing requirements
   currently being specified by the Routing Over Low power and Lossy
   networks (ROLL) Working Group.  For the sake of illustration, some
   metrics are only meaningful in routing protocols that fall into the
   category of Distance Vector.  Since the Working Group has not yet
   determined which routing protocol will be chosen for Low power and
   Lossy Networks (LLNs), it is not yet possible to determine whether
   such metrics will be required.  Conversely, other metrics may be
   further required depending on which routing protocol is selected by
   the Working Group.

2.  Terminology

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", 'RECOMMENDED", "MAY", and "OPTIONAL" in this
   document are to be interpreted as described in [RFC2119].

   o  Access point: An infrastructure device that connects the low power
      and lossy networks to the backbone network like the Internet,
      mostly via access networks.

   o  Data sink: A device which collects data from nodes in a LLN.

   o  Dynamic LLN: Low power and Lossy Network where some nodes are
      mobile.

   o  ROLL: Routing Over Low-power and Lossy networks.

   o  Static LLN: Low power and Lossy Network where all nodes are
      static, not mobile.

dmm> looks likek most of this can be replaces with a citation to 
dmm> draft-vasseur-roll-terminology-01.txt	

3.  Introduction

   This document specifies routing metrics used in path calculation for
dmm> s/used/to be used/  (or maybe "for use")
   Routing Over Low power and Lossy networks (ROLL).  Low power and
   Lossy Networks (LLNs) have unique characteristics compared with
   traditional wired networks or even with similar ones such as mobile
   ad-hoc networks as indicated in several application-specific
   requirements documents.  Since typical IGP routing metrics such as
   hop counts or link metrics are not sufficient for LLNs, this document
   specifies a new set of required link and node metrics suitable to
   LLNs.
dmm> do you really want to say the the metrics are "required"?
dmm> How about s/required//

Kim, et al.              Expires January 5, 2009                [Page 3]

Internet-Draft          Routing Metrics for LLNs               July 2008

   Routing metrics can be classified according to the following set of
   characteristics:

   - Link versus Node metrics

   - Qualitative versus quantitative

   - Dynamic or static

   Historically, IGP such as OSPF and IS-IS have been using quantitative
dmm> citations for OSPF and IS-IS
   static link metrics.  Other mechanisms such as Multiprotocol Label
   Switching (MPLS) Traffic Engineering (TE) make use of other link
dmm> again, citation for MPLS/MPLS-TE
   attributes such as the available reserved bandwidth, affinities and
   so on to compute constrained shortest path for Traffic Engineering
s/path/paths/
   Label Switched Paths (TE LSPs).

   It must be noted that the use of dynamic metrics is not new and has
   been experimented in ARPANET 2, with a moderate success.  Indeed, a
dmm> citation for ARPANET 2
   very careful care must be given to the use of dynamic metrics that
   may lead to potential routing instabilities.

   In LLNs, it is required to take into account various node constraints
   when calculating the desirable path.  Node metrics include the node's
   resources like memory, energy and CPU (computational power).  Other
   node attributes such as the ability to act as an aggregator (node
   capable of performing data aggregation) may be of interest.
   Additionally, work load, transmission range and dynamicity (mobility,
   duty cycle, etc) may need to be taken into account.  Link attributes
   include propagation delay, reliability (quality) and available
   bandwidth.

   By contrast with the current Internet, LLNs are characterized by
   their dynamic nature, which not only applies to the link but also to
   the nodes in the networks.  Thus, it is required to specify various
   dynamic metrics.  For instance, even though a wireless sensor network
   topology is static in absence of failure, nodes' workload and
   resource such as residual energy and available memory are changing
   continuously and may have to be taken into account during the path
   computation.  Similarly, link attributes including latency and
   reliability are not static because moving obstacles can appear at any
   time.  Thus, they are real-time parameters.  That being said, very
   careful attention must be given to highly dynamic parameters that
   affect routing decision in order to preserve the routing stability.
   Furthermore, it is quite time- and energy-consuming process to update
   these dynamic metrics in a regular basis.  Therefore, we may regard
   them as static metrics in static LLNs to cut off overhead by
   compromising accuracy.

dmm> This last sentence is hard to understand. Maybe:
dmm> "Therefore we might treat such dynamic metrics as static
dmm> metrics in order to reduce computational overhead and
dmm> bandwidth utilization. Of course, this comes with a cost,
dmm> namely, reduced metric accuracy.

Kim, et al.              Expires January 5, 2009                [Page 4]

Internet-Draft          Routing Metrics for LLNs               July 2008

   Reliability is an example of quality parameter.  However, to be
   routing metrics for path calculation, quality parameters MUST be
   transformed to quantity values.  Some criteria SHOULD be set to make
   the quality parameters appear in quantity forms.  Quantity form can
   be numbers or levels.

   This document specifies a set of link and nodes metrics that can be
   used to compute the optimal path within a LLN.  Furthermore, some
   link or node attributes (e.g. level of link reliability, energy
   remaining on the node) can be used to perform constraint-based
   routing.  It is not required to use all the metrics and attributes
   specified in this document.  A particular implementation MAY use a
   subset or all of the metrics defined in this document.

   Note: finding the shortest path is not always best in LLNs since a
   reliable path is more preferable. !oThe optimal path!+/- here means
   the best path having regard to constraints.  The term !oconstrained
   shortest path!+/- may be used instead.

   The specification of the objective function used to compute the path
   is out of the scope of this document.

   Note: in the first revision of this document, link and node metrics
   are defined with no packet format or suggestions to encode the data.
   This will be determined in a further revision of this document.

4.  Node attributes

   Most node attributes may be taken as static attributes in LLNs since
   it might require quite amount of resources to get exact values of the
   attributes and update them periodically.  Furthermore, the use of
   dynamic metrics is subject to routing instabilities and must be used
dmm> s/is subject/can cause/
   with extreme care.  However, critical parameters like residual power
dmm> you might want to consider the total power of a given path
dmm> as well (especially when optimizing network lifetime).
dmm> See, e.g., "Wireless sensor networks: a survey",
dmm> I.F. Akyildiz, et. al., Computer Networks (38), 2002,, 393-422.

   might need to be considered dynamic and monitored continuously in
   some scenarios.  Implementation MUST make use of multi-threshold

dmm> s/Implmentation/An implementation/

   scheme rather than fine granular metric update so as to avoid

dmm> The term "multi-threshold scheme" hasn't been described

   constant routing changes.

   In LLNs, it is not uncommon to have highly heterogeneous nodes in
   term of capabilities (e.g node being battery operated or not, amount
   of memory, !|) and functionalities.  More capable and stable nodes
   can assist the most constrained ones for routing packets, which
   results in extension of network lifetime and efficient network
   operations.  Therefore, node metrics SHOULD be carefully maintained
   and utilized for routing.  This has the following strong implication
   referred to as constrained-based routing whereby the computed path
   may not be the shortest path according to some specified metrics.

dmm> maybe: "This implies that constraint-based routing will be
dmm> used in some cases."

Kim, et al.              Expires January 5, 2009                [Page 5]

Internet-Draft          Routing Metrics for LLNs               July 2008

   Mechanisms must be designed to ensure lack of routing loops in the
   presence of constrained based routing with a non connection oriented
   environment.
dmm> "Routing should be loop-free" (?). In addition, what kind of
dmm> micro-loops (if any) are to be tollerated? I would imagine
dmm> that this is application specific. However, there is a
dmm> convergence time v. energy utilization question here
dmm> (possibly also application specifc).

4.1.  Computational resources

   Memory and CPU resources can be considered as computational ones and
   are potentially important routing metrics in LLNs because in some
   environments nodes are resource constraint.  Resource-awareness
   SHOULD be employed to routing protocols strictly or loosely
   considering trade-off between cost and benefit.

4.2.  Residual Energy

   Low power is one of the most distinguished features of LLNs, so
   residual energy MUST be considered as a pivotal metric in
   environments where nodes are battery powered.  Residual energy should
   be taken as a relative value considering statistical node lifetime
   and other conditions like the role of the node in the network.  For
   example, if the node's expected lifetime is 5 years and the remaining
   energy is only one fifth, then the energy is quite precious resources
   to the node.  In such cases, the routing protocol decision should be

dmm> so "relative" above means relative to other resources that
dmm> are considered "more important"? How would we quantify that?

   such that potentially a suboptimal path would be used for some
   traffic so as to increase the network life duration.  Furthermore, in

dmm> this implies that the routing protocol needs (must?) have a
dmm> global view of the residual energy of the network (likely
dmm> the rate at which certain devices are being dischared as
dmm> well, and which ones are battery powered and which ones are
dmm> mains powered). Is that what is intended?

   case absence of the node affects the network connectivity critically,
   the node SHOULD be avoided to save its power.  Hence, whenever
   possible, the node should not be selected as a router (an
   intermediate node to deliver data), thus the support for constrained-
   based routing is needed.  If the battery can be simply charged or the
   node can be easily replaced with another same kind of node, then it
   is not really a matter to use up the battery.  Such information
   should be defined as a node attribute to be used in combination with
   the energy level.  Algorithms defining how such metrics and
   attributes should be combined are outside of the scope of this
   document.

   Generally, the residual energy should be taken as a dynamic metric.
   Most battery operated devices have ability to estimate the remaining
   energy [I-D.ietf-roll-indus-routing-reqs].  However, initial energy
   status can be considered as a static metric in some situations where
   monitoring current energy status demands quite resources.  Simply
   categorizing devices into two classes, main-powered and battery-
   powered, can be good enough to select a routing path for highly
   constrained scenarios, which contributes to prolonging network
   lifetime.  To maximize network lifetime, it is essential to maintain
   energy balance among nodes in LLNs.
dmm> ^^^^^^^^^^^^
dmm> how is "energy balance" defined?

Kim, et al.              Expires January 5, 2009                [Page 6]

Internet-Draft          Routing Metrics for LLNs               July 2008

4.3.  Current workload

   Workload of a node is somewhat difficult to be measured and compared.
   It is also difficult to express the workload in a quantitative form.
   However, it could be an important metric to select a path in LLNs,
   especially when data processing along the data path is required or
   queuing delays must be minimized for highly sensitive traffic.
   Putting the workload as a "heavy" or "light" one bit metric can give
   a good advice to select a path for routing, thus providing a
   sufficient level of granularity, similarly to the "overload" bit used
   in protocols such as IS-IS.  An implementation may then decide to
dmm> might be useful to cite documents that define the IS-IS
dmm> overload bit. 
   exclude from its routes any node with a "heavy" value for workload
   unless there is no alternative.

4.4.  Node latency

   Node latency is the time span from the arrival time to the departure
   time of a given packet at a node.  It is primarily made up of packet
   processing time and packet transmission time.  Node latency is highly
   correlated with other metrics.  For instance, heavy workload
   increases node latency while enough computational resources can
   reduce it.  Therefore, in some LLNs where available resources and
   current workload can be measured, they can facilitate to estimate
   node latency or may substitute it.

4.5.  Data Aggregation attribute

   Some nodes may sense (get) similar or same data if the nodes are
dmm> s/(get) similar or same /or receive the same (or similar)
   located in a close area due to data correlation.
dmm> BTW, this is frequently called "overlap" in the
dmm> literature. See e.e., "Adaptive Protocols for Information
dmm> Dissemination in Wireless Sensor Networks", Joanna Kulik,
dmm> Wendi Rabiner, Hari Balakrishnan,1999
dmm> http://www.cs.washington.edu/education/courses/590es/01au/papers/2.pdf

   Thus, data
   aggregation/fusion can be performed.  Data fusion involves more
dmm> s/can be performed/may be possible/
   complicated processing to improve accuracy of the output data while
   data aggregation mostly aims to reduce the amount of data.
   Especially in urban applications where sensor nodes collect
dmm> s/Especially/Sensing overlap is common/
   environmental information and send it to a data sink, quite a number
   of sensor nodes sense same kind or same value of data.  In the Figure
   1, let us assume that three nodes A, B and C need to send sensed data
   to the data sink.  Node A sensed "xyz" and sent this data to node C.
   Since C also sensed same data, it has no additional information from
   node A. However, because the data node B sent is "xqz", node C
   aggregates this data with its own data "xyz" resulting in "xyqz".
   Therefore, node C sends "xyqz" to the data sink.  In this example,
   each node's data requires 3 bytes.  If no aggregation is performed,
   node C needs to send 9 byte data to the sink, but C only sends 4
   bytes thanks to data aggregation.

Kim, et al.              Expires January 5, 2009                [Page 7]

Internet-Draft          Routing Metrics for LLNs               July 2008

                            A               B
                         |------|        |------|
                         | xyz  |        | xqz  |
                         |______|        |______|
                               \          /
                                \        /
                                 \  C   /             sink
                                 |------|    xyqz   |------|
                                 | xyz  |-----------|      |
                                 |______|           |______|

                        Figure 1: Data aggregation

   Some applications MAY make use of the aggregation node attribute in
   their routing decision so as to minimize the amount of traffic on the
   network, thus potentially increasing its life time in battery
   operated environments.

dmm> So this is a form of data-aware routing. How far to we think
dmm> we need to go in this direction? I did notice that 
dmm> I-D.ietf-roll-indus-routing-reqs also suggests the need for 
dmm> data-aware routing. 
dmm> 
dmm> For a good discussion of (some of the) issuess, see, e.g.,
dmm> 
dmm> "Directed Diffusion: A scalable and robust communication
dmm> paradigm for sensor networks", Ramesh Govindan, Deborah
dmm> Estrin, 2000 http://netweb.usc.edu/estrin/papers/diffusion.ps
dmm> 
dmm> (its just one such approach)

   To make data aggregation possible, the routing protocol needs to
   capture the time and location dependent correlation among sensed data
   from nodes on the possible routes, which is quite challenging.
   Obtaining correlation structure also demands high resource (energy)
   consumption and in-network processing itself may have high
   complexity.  Consequently, in most applications, data aggregation may
   not be adopted for routing.  However, simply choosing nodes that have
   the same kind of sensors with the source node can increase the chance
   to aggregate data, so it can be helpful for path formation regardless
   of having data-aware routing capability.  

dmm> nice heuristic. Do we have a citation that examines the 
dmm> use of this heuristic?

   Applications where high directional data flow is expected in a
   regular basis may take advantage of data aggregation supported
   routing.

4.6.  Node degree

   Node degree is the number of neighbors that can send a message to the
   node directly.  In other words, neighbors are nodes located within
   the transmission range of the node.  Generally, a high node degree
   can be helpful for quick route recovery when the next hop node on the
   route cannot be accessible.  Therefore, it may be beneficial to
   choose a node with a high degree to construct a route.  On the
   contrary, a node with a high degree has a high possibility to have
   heavy workload in a busy network.  Therefore, node degree has to be
   carefully utilized in routing decision.

dmm> basically this is an "amplication effect" [RFC 3439]

Kim, et al.              Expires January 5, 2009                [Page 8]

Internet-Draft          Routing Metrics for LLNs               July 2008

4.7.  Dynamicity

   Node dynamicity can be measured by many different factors such as
   mobility, transmission range, duty cycle, and the rate at which node
   joins and leaves the network.  Node dynamicity directly affects the
   network topology and connectivity, which in turn may trigger route
   reestablishment process.  For that reason, node dynamicity needs to
   be monitored and presented in a quantity form utilizing a well
dmm>                               ^^^^^^^^
dmm> Do you mean quantative (v. qualatative)?

   defined objective function.  Thus, less dynamic nodes should be
   preferred for path selection.  
dmm> is that true, even if a more "dynamic" path has better (optimizes)
dmm> residual energy or some other metric of interest? i.e., is
dmm> the statement too general?

   In the most constrained LLN environments, classifying nodes
   into only static and dynamic can be very helpful in routing
   decision.  

dmm> Maybe something like this:
dmm> "In the most constrained LLN environments, the simple heuristic
dmm> of classifying nodes into static or dynamic can be very
dmm> helpful in routing decision."
dmm> I think that is what you mean...if not, then ?

   Note that this node metric may either be static or
   dynamic.  In the later case, the network administrator will
   have to use consistent metric values.

4.8.  Node reliability

   Node reliability is deeply related to node dynamicity such that node
   reliability deteriorates as node dynamicity increases.  However, node
   reliability is a wider concept than node dynamicity since node
dmm> s/wider/more general/
   reliability is influenced by more factors.  For example, node's
   unexpected failure cuts off node reliability, but it is not really
dmm> s/cuts of node/reduces a node's/  (I think that's what you mean)
   related to node dynamicity.  Therefore, node dynamicity metric can be
   covered by node reliability metric.  However, it is very challenging
   to estimate or monitor node reliability.  A specific function needs
   to be defined to get values of the reliability metric from a variety
   of features affecting node reliability.

   Node reliability is a crucial metric in LLNs compared with in other
   conventional or even wireless networks considering that nodes in LLNs
   may stay in a sleep mode most of the time.  

dmm> maybe :
dmm> "Node reliability can be a crucial metric in LLNs, since
dmm> nodes in LLNs may stay in a sleep mode most of the time."
dmm> Again, I think that's what you mean.

   A sleeping node should
dmm> question here about 2119 language. SHOULD NOT v. should not
   not be an intermediate node to deliver a packet, thus status of a
   node must be monitored or can be anticipated.  Additionally, residual
dmm> s/can be anticipated/should be predictable/
   energy of a node should be predictable not to make the node suddenly
   die during routing process due to battery out.  Nodes on the chosen
   path for routing should be reliable.

5.  Link attributes

   There are several dynamic link attributes especially in wireless
   LLNs.  Even in case of static LLNs where nodes are stationary, there
   are always variables like appearance of obstacles and signal
   interference.  Similar to node attributes, link attributes can be
   considered as static ones in static LLNs not only because it is very
   challenging to update them in a real-time manner, but also it is
   quite time- and energy-consuming work.  However, in dynamic LLNs, we
   may need to take these attributes as dynamic metrics and make use of

Kim, et al.              Expires January 5, 2009                [Page 9]

Internet-Draft          Routing Metrics for LLNs               July 2008

   current real-time values whenever necessary.  Values of dynamic
   metrics cannot be obtained easily.  One way to get values of dynamic
   metrics is to use historical data and average them within a specified
   time window.

5.1.  Bandwidth

   Bandwidth can be taken as a link capacity metric.  It can be
   evaluated as nodes' communicational capability, too.  
dmm> perhaps:
dmm> Bandwidth can be also be used to represent a node's
dmm> communication capability.
dmm> Is that what you mean?

   It must be
   remembered that in case of wireless link, the link capacity is shared
   among nodes in a single wireless link.

5.2.  Reliability (Quality)

   Link reliability can be measured by the Bit Error Rate (BER), Mean
   Time Between Failures (MTBF) or link churn defined as the rate at
   which links change between good and bad
   [I-D.levis-roll-protocols-survey].  Link reliability is closely
   related to node reliability especially in wireless LLNs.  Two nodes
   which form a link affect directly to the link reliability as follows:
   if one node falls in a sleep mode or moves away beyond of the
   transmission range from the other node, the link vanishes away.
dmm> s/vanishes away/vanishes/
dmm> 
dmm> But more generally, I think what you are trying to say that
dmm> if there if one (or both) end of a link either dies or
dmm> moves, the link should be removed from routing. Correct? If
dmm> so, that is sensible. If not, what did you have in mind?

   However, link reliability is also influenced by other factors like
   unexpected obstacles or temporary interference.

   Just like node reliability is critical, link reliability is also
   essential for routing given that most nodes have very short duty
   cycles.  Change of link quality directly gives rise to that of
   network connectivity.  

dmm> couldn't parse the last sentence. I'm guessing you mean to
dmm> say something to the effect that "A change in link quality can
dmm> effect network topology."

   Therefore, link quality may be taken into
   account as a critical routing metric.  Increasing link and node
   reliability together enhances route robustness.  Therefore, choosing
   reliable links and nodes during route establishment process improves
   robustness of the selected routes.

5.3.  Propagation delay

   Propagation delay is the time taken for the packet to traverse the
   link from the source node to the target node.  Path (route) latency
   is made up of nodes' latency and links!_ propagation delay on the
   path.  

dmm> I think you mean:
dmm> Path (route) latency is usually computed as the sum of the 
dmm> latencies of the indivudal nodes along a the path.
dmm> 
dmm> also, note the !_ 

   As mentioned earlier, it can be obtained by making average
   from historical data.

dmm> I think you mean:
dmm> As mentioned earlier, propogation delay can be obtained
dmm> averagin historical data.
dmm> 
dmm> So where does this historical data reside?

6.  Open issues

   Other items to be addressed in further revisions of this document
   include:

Kim, et al.              Expires January 5, 2009               [Page 10]

Internet-Draft          Routing Metrics for LLNs               July 2008

   o  Traffic flow requirement: selection of applicable routing metrics
      needs to be performed depending on application and traffic flow
      requirements.  For example, when latency is not a matter at all,
      it is possible to remove latency related metrics in the objective
      function to calculate the routing path.  As such, different
      applications or Service Level Agreement (SLA) might demand
      different routing metric combination for path calculation, which
      forms a different route.  Moreover, some routing algorithm may
      support Multi-topology routing with the ability to compute routes
      based on the traffic flow requirements using different set of
      metrics.

   o  Metric weights exploitation: weights for the listed metrics should
      be decided according to applications and data flows.  

dmm> are you suggesting data-aware routing here?

      For example,
      latency critical applications in military scenarios SHOULD put a
dmm> s/in military scenarios//
dmm> (since this would be true in any latency critical application)
      high weight to latency metrics rather than resource metrics.  On
      top of that, applicable metrics or optimized weights may need to
      be changed on demand.

   o  Metrics related to security: Metrics that security is associated
      with need to be further considered.  If a route is comprised of
      authenticated and authorized nodes for the data, then the route
      should be preferable.

   o  Consideration of routing efficiency and stability: LLNs are highly
      constrained networks, thus it is hard to maintain many metrics for
      efficient routing due to resource demand and overhead.  

dmm> maybe:
dmm> Since LLNs are highly constrained networks, maintaining many
dmm> different routing metrics is challenging.

      Routing should be lightweight.  

dmm> again, 2119 language. should be v. SHOULD BE

      In addition, careful condition should be given to the
      dynamic nature of some metrics and their implication on
      routing stability.
dmm> you mention this several times (rightfully so). It might be
dmm> nice to have a citation for this.

   o  Influence of network topology and density: Network topology and
      network density need to affect route construction in such a way
      that they need to give some input to metric decision.  For
      example, star topology and mesh topology should employ different
      routing protocols.  

dmm> why? should be made explict

      Obviously they need to adopt different routing
      metrics.  

dmm> Again, why? should be made explict

      Similarly, network density in terms of average node
      degree needs to be considered when setting routing metrics and
      weights.  Network size in terms of physical and total number of
      nodes needs to be taken into account, too.  In addition, influence
      of network deployment on routing metrics should be further
      studied.

dmm> I couldn't parse this last sentence (In addition, influence
dmm> of network deployment on routing metrics should be further
dmm> studied).

7.  Security Considerations

   Routing metrics should be handled in a secure and trustful manner.
   For instance, a malicious node can not advertise falsely that it has

Kim, et al.              Expires January 5, 2009               [Page 11]

Internet-Draft          Routing Metrics for LLNs               July 2008

   good metrics for routing and belong to the established path to have a
   chance to intercept packets.

dmm> This section needs to be expanded. Let me know if you'd like
dmm> me to contribute some text.

8.  IANA Considerations

   This document requests no action by IANA.

9.  Acknowledgements

   The authors would like to acknowledge the contributions of Dr.
   YoungJae Kim for his review and comments.

10.  References

10.1.  Normative References

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119, March 1997.

10.2.  Informative References

   [I-D.ietf-roll-indus-routing-reqs]
              Networks, D. and P. Thubert, "Industrial Routing
              Requirements in Low Power and Lossy Networks",
              draft-ietf-roll-indus-routing-reqs-00 (work in progress),
              April 2008.

   [I-D.levis-roll-protocols-survey]
              Levis, P., Vasseur, J., and D. Culler, "Overview of
              Existing Routing Protocols for Low Power and Lossy
              Networks", draft-levis-roll-protocols-survey-00 (work in
              progress), May 2008.

Kim, et al.              Expires January 5, 2009               [Page 12]

Internet-Draft          Routing Metrics for LLNs               July 2008

Authors' Addresses

   Mijeom Kim (editor)
   Future Tech Lab., KT
   17 Woomyeon-dong, Seocho-gu
   Seoul  137-792
   Korea

   Phone: +82-2-526-6063
   Fax:   +82-2-526-5071
   Email: [email-masked]

   JP Vasseur (editor)
   Cisco Distinguished Engineer
   11, Rue Camille Desmoulins
   L'Atlantis  92782 Issy Les Moulineaux
   France

   Email: [email-masked]

   Hakjin Chong
   Future Tech Lab., KT
   17 Woomyeon-dong, Seocho-gu
   Seoul  137-792
   Korea

   Phone: +82-2-526-5070
   Fax:   +82-2-526-5071
   Email: [email-masked]

Kim, et al.              Expires January 5, 2009               [Page 13]

Internet-Draft          Routing Metrics for LLNs               July 2008

Full Copyright Statement

   Copyright (C) The IETF Trust (2008).

   This document is subject to the rights, licenses and restrictions
   contained in BCP 78, and except as set forth therein, the authors
   retain all their rights.

   This document and the information contained herein are provided on an
   "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
   OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND
   THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS
   OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF
   THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
   WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.

Intellectual Property

   The IETF takes no position regarding the validity or scope of any
   Intellectual Property Rights or other rights that might be claimed to
   pertain to the implementation or use of the technology described in
   this document or the extent to which any license under such rights
   might or might not be available; nor does it represent that it has
   made any independent effort to identify any such rights.  Information
   on the procedures with respect to rights in RFC documents can be
   found in BCP 78 and BCP 79.

   Copies of IPR disclosures made to the IETF Secretariat and any
   assurances of licenses to be made available, or the result of an
   attempt made to obtain a general license or permission for the use of
   such proprietary rights by implementers or users of this
   specification can be obtained from the IETF on-line IPR repository at
   http://www.ietf.org/ipr.

   The IETF invites any interested party to bring to its attention any
   copyrights, patents or patent applications, or other proprietary
   rights that may cover technology that may be required to implement
   this standard.  Please address the information to the IETF at
   [email-masked].

Kim, et al.              Expires January 5, 2009               [Page 14]

---

From: "MiJeom Kim" <[email-masked]>
Date: Wed, 24 Sep 2008 20:53:04 +0900

Hi Dave,

I really appreciate your kind and detail comments. Mostly I agree with
you in your opinion. However, there are still things I'd like to discuss.
See the red arrows.

(So if there is no red arrow, your comments will be reflected in the next
revision.)

Thank you.
Mijeom.

On Sat, Sep 20, 2008 at 6:21 AM, David Meyer <[email-masked]> wrote:

> ===> I think the sentence "LLNs have unique characteristics" is the
> reason. And this is the abstract, so I omitted all the details. However,
> it's not difficult to add some specific reasons such as resource
> constraints, so if you still think it's better to add, let me know.

> ===> Only ROLL is in the draft, so I think it's better to leave them for
> now.
>
> 3.  Introduction
>
> ===> Of course, considering a given path will make better route selection
> possible than considering only individual nodes and links. It applies to not
> only power but also most other metrics, I believe. However, it's very
> challenging to consider paths in LLNs due to resource constraints and there
> are implementation issues. We may need to delay this issue until path
> calculation using the metrics is discussed.

> ===> Initially, I meant with "relative" that the residual energy should
> not be evaluated with absolute values. For example, both devices A and B
> have the same amount of residual energy to last 1 year. A is essential in
> the network such that the absence of the node causes network partition and A
> is neither rechargeable nor replaceable. However, B is easily replaceable.
> Then, 1 year of the power lifetime is a relative value to both devices. There
> may be several ways to quantify that even though these are challenging. When
> a device is produced or deployed, some parameters indicating the device is
> rechargeable or replaceable easily or not can be set manually. Or some
> parameters indicating the role of the device in the network can be set by
> the device itself using context aware capability such that it can recognize
> itself as a pivotal device to maintain network connectivity.

> ===> The routing protocol does not need to have a global view, but it just
> needs to choose the best next hop among possible candidates.

===> I may say the amounts of residual energy of all nodes in the network
are fairly even.

4.3.  Current workload

4.4.  Node latency

  Thus, data
  aggregation/fusion can be performed.  Data fusion involves more
dmm> s/can be performed/may be possible/
  complicated processing to improve accuracy of the output data while
  data aggregation mostly aims to reduce the amount of data.
  Especially in urban applications where sensor nodes collect
dmm> s/Especially/Sensing overlap is common/
===> Even though "overlap" is frequently used in the literature, we might
need a definition for the term if we want to use it here. I cannot see any
reason to use the term "overlap" here, though. And the suggested
substitution results in connection of two sentences using comma, which is
incorrect.

                           A               B
                        |------|        |------|
                        | xyz  |        | xqz  |
                        |______|        |______|
                              \          /
                               \        /
                                \  C   /             sink
                                |------|    xyqz   |------|
                                | xyz  |-----------|      |
                                |______|           |______|

dmm> So this is a form of data-aware routing. How far to we think
dmm> we need to go in this direction? I did notice that
dmm> I-D.ietf-roll-indus-routing-reqs also suggests the need for
dmm> data-aware routing.
===> I do agree that data-aware routing is very challenging especially with
resource constraints. As I mentioned below, we need to make the data
aggregation mechanism as simple as possible to reduce overhead. Further
discussion is needed.

dmm>

dmm> nice heuristic. Do we have a citation that examines the
dmm> use of this heuristic?
===> No, unfortunately we do not have a citation. This is just an idea.

4.6.  Node degree

dmm> basically this is an "amplication effect" [RFC 3439]
===> you mean amplification? Actually I have not seen the reference. Do you
think it's better to include the citation?

4.7.  Dynamicity

  defined objective function.  Thus, less dynamic nodes should be
  preferred for path selection.
dmm> is that true, even if a more "dynamic" path has better (optimizes)
dmm> residual energy or some other metric of interest? i.e., is
dmm> the statement too general?
===> Dynamicity is just one metric. And we have more metrics to be used in
path calculation. Thus, we need a weight for each metric. The sentence does
not say that dynamicity is the most important metric over other metrics.

4.8.  Node reliability

dmm> maybe :

  A sleeping node should
dmm> question here about 2119 language. SHOULD NOT v. should not
===> I think "should not" is okay for now. Need further discussion.

5.  Link attributes

5.1.  Bandwidth

  It must be

5.3.  Propagation delay

dmm> I think you mean:
dmm> Path (route) latency is usually computed as the sum of the
dmm> latencies of the indivudal nodes along a the path.
===> No, I mean path latency is the sum of all node latencies (section 4.4)
and all link propagation delays (senction 5.3) along the path. If the
original sentence is hard to read, I may change it.

dmm>
dmm> also, note the !_

dmm> I think you mean:
dmm> As mentioned earlier, propogation delay can be obtained
dmm> averagin historical data.
dmm>
dmm> So where does this historical data reside?
===> each node should maintain the data. It does not need to keep all the
historical data but just maintain an average. However, I also think that it
costs high and has not much benefit since propagation delay is mostly
negligible. Need further discussion.

6.  Open issues

dmm> are you suggesting data-aware routing here?
===> Yes, but trade-off should be further discussed.

     For example,
     latency critical applications in military scenarios SHOULD put a
dmm> s/in military scenarios//
dmm> (since this would be true in any latency critical application)
===> I know what you mean, but this is an example. Thus I think it's better
to have "in military scenarios" since it helps to understand the example.

dmm> maybe:

dmm> again, 2119 language. should be v. SHOULD BE
===> I prefer should be for now.

     In addition, careful condition should be given to the
     dynamic nature of some metrics and their implication on
     routing stability.
dmm> you mention this several times (rightfully so). It might be
dmm> nice to have a citation for this.
===> I do not have any reference here. To me it is quite obvious. But if you
think a citation is still needed, I will try to find.

dmm> why? should be made explict
===> Actually, I intended to remove this final bullet, but accidentally I
didn't delete in the first draft. I will remove it for the next submission.

dmm> This section needs to be expanded. Let me know if you'd like
dmm> me to contribute some text.
===> I would very appreciate if you contribute.

8.  IANA Considerations

9.  Acknowledgements

10.  References

Authors' Addresses

  Mijeom Kim (editor)
  Future Tech Lab., KT

  Phone: +82-2-526-6063
  Fax:   +82-2-526-5071
  Email: [email-masked]

  JP Vasseur (editor)

  Email: [email-masked]

  Hakjin Chong
  Future Tech Lab., KT

  Phone: +82-2-526-5070
  Fax:   +82-2-526-5071
  Email: [email-masked]

Full Copyright Statement

Intellectual Property

---

From: David Meyer <[email-masked]>
Date: Wed, 24 Sep 2008 12:31:40 -0700

Hey MiJeom,

> I really appreciate your kind and detail comments. 

	Any time.

> Mostly I agree with you in your opinion. However, there are
> still things I'd like to discuss. 

	Sure, makes good sense.

> >   hop counts or link metrics are not sufficient for LLNs,

	Nah, this isn't a big deal.

> > calculation using the metrics is discussed.

	Fair enough. I'll note that we need to keep the number of
	metrics that we consider in any CBR solution (e.g., 3 or
	perhaps 4, if we want to be practical).

> > the network such that the absence of the node causes network
> > partition and A  is neither rechargeable nor
> > replaceable. However, B is easily replaceable.  Then, 1 year
> > of the power lifetime is a relative value to both devices. There 

	Understood. Those "relative values" then will have to have
	well methods for both computation and propogation (I
	guess that goes w/o saying, even though I just did :-)).
> > needs to choose the best next hop among possible candidates.

	Ok, it sounded like a global energy mininumization
	problem (which I point out that some WSNs can do; of
	course, such WSNs aren't IP based).

> ===> I may say the amounts of residual energy of all nodes in the network

	Ok. I didn't take that from the statement. Maybe clarify?

> substitution results in connection of two sentences using comma, which is

	Ok, not a big deal (just pointing out that there is some
	existing terminology for this condition).

> ===> No, unfortunately we do not have a citation. This is just an idea.

	My point was that it would be nice to understand its
	properties. 

> think it's better to include the citation?

	Well, its a common issue when you have meshiness.

> not say that dynamicity is the most important metric over other metrics.

	Humm, ok. I'm not sure but for no its fine.

> ===> I think "should not" is okay for now. Need further discussion.

	I asked the IESG for convential wisdom regarding 2119
	language in non-protocol specs. I didn't get much
	guidance, so I'm guessing its a non-issue.

> original sentence is hard to read, I may change it.

	Might be a good idea. Looks like (at least)
	mis-interpreted what you meant.

> negligible. Need further discussion.

	Agreed, thnx.

> ===> Yes, but trade-off should be further discussed.

	Again, agreed.

> to have "in military scenarios" since it helps to understand the example.

	My point was that the latency issue isn't specific to the
	military example. You might give this as *one* example of
	a latency constrained application.

> didn't delete in the first draft. I will remove it for the next submission.

	Sure, happens.

> ===> I would very appreciate if you contribute.

	I'll send text.

	Thnx,

	Dave