Subject: Re: [Roll] Suggestions for draft-ji-roll-traffic-aware-objective-function-00

From: Remous-Aris Koutsiamanis <[email-masked]>
Date: Tue, 16 Jan 2018 14:09:33 +0100 (CET)

Hello Derek,
thank you so much for the extremely helpful discussion. I have a question
regarding the aggregation mode.

On Fri, Dec 22, 2017 at 3:48 AM, Houjianqiang (Derek) <houjianqiang@huawei
.com> wrote:

> Hi Chenyang,
>
> Regarding your questions, please see my response in line.
>
> 2.      I noticed one weak point of your solution and I have come up with
> some possible ways to solve that. Nodes select their preferred parent node
> based on the PTRs of their potential parents (if I understand it right).
> For the two-hop cases in your draft, it's fine, but for multi-hop cases,
> the downstream nodes are unaware of the PTRs of the sink nodes (nodes
> connected to the root). For example, in the right pattern of Figure 2 in
> your draft, if new nodes come in below C1/C2/D1/D2, then the new nodes will
> prefer to choose C1/C2/D1 rather than D2 (PTR_D2 is larger). Let's say new
> node E1->C1, E2->C2, E3->D1, and assume E1/E2/E3 have PTR = 1pkt/s, then in
> this case, PTR_C1 = PTR_C2 = PTR_D1 = 2 pkt/s, PTR_A = 6 pkt/s. This in the
> end triggers D1 switches from A to B. So my point is when new nodes join in
> the downstream, they strongly influence the upstream connections. This
> effect causes an unstable RPL network and should be minimized. One way I
> come up with is to use the aggregatio
>  n mode in the Metric Container so that new nodes are able to know the
> whole PTRs along a link to the root and then select based on the whole link
> condition. Another possible way is you can define a new "RANK" computation
> that includes the PTRs along a link, e.g. RANK_C1 = PTR_A+0.5*PTR_C1.
>
> [RE] You are right about the weak point,thank you.
> About the aggregation mode,if I understand correct that requires node to
> inform its direct child about its transmission rate change(new node joins
> its subtree,child changes parent etc),that may increase the frequency of
> DIO messages?
>
> >> [Derek] The frequency of sending DIO is determined by Trickle
> algorithm, not the aggregation mode. RPL adapts the sending rate of DIO
> messages by extending the Trickle algorithm. In a network with stable links
> the control messages will be rare whereas an environment in which the
> topology changes frequently will cause RPL to send control information more
> often.
>

So, in this draft, the PTR information is sourced directly from the traffic
each node has "seen", e.g. if a node has seen 2 packets in the last second,
it will report this 2pkts/sec. You have proposed using the aggregation mode
in the Metric Container to alter the number reported.
As far as I can tell it would work like this:
A node measures its own observed PTR: PTR_OWN.
However, it also receives DIO messages from other nodes. When it gets a DIO
message from its preferred parent it extracts the parent's reported
PTR: PTR_PARENT.
Before getting a DIO message the default is PTR_PARENT=0.
So, when the node needs to broadcast a new DIO of its own, the PTR value it
reports is PTR = PTR_OWN + PTR_PARENT.
Therefore, in the example on the right in Figure 2, the reported PTRs from
the nodes will not be the shown ones but:
R: 6, A: 3 + 6 (from R) = 9
B: 3 + 6 (from R) = 9
C1, C2, D1: 1 + 9 (from A) = 10
D2: 3 + 9 (from B) = 12

So when a new node E1 with PTR_OWN=1pkt/sec comes under C1,C2,D1,D2 it will
avoid D2 and it will pick one of C1,C2,D1 and report its own PTR via DIO as:
E1: 1 + 10 (from say C1) = 11
in the same way:
E2: 1 + 10 (from say C2) = 11
E3: 1 + 10 (from say C1) = 11

Is this what you have in mind?

>
> About rank computation,nodes with larger transmission rate will have
> larger rank than its neighbor nodes so there is a possibility it selects
> its neighbor as parent and increase the traffic of other subtree.
> I don't know if I described it in the right way,I'll send a example if
> needed.
>
> >>[Derek] I guess I have got what you mean. Let's still take the right
> pattern in Figure 2 in your draft as an example, are you saying that when
> PTR_D2 becomes larger, e.g. 5pkt/s, then PTR_B = 5. If using the "RANK"
> equation I suggested above, then RANK_A = 3, RANK_B = 5, RANK_D1 = 3.5,
> RANK_D2 = 7.5. In this case node D2 may change its parent from B to D1. If
> this is what you mean, definitely we don't want to see this happen. To
> avoid this, you should specify when and under what condition the parent
> switch will happen. The PARENT_SWITCH_THRESHOLD of D2 should be related to
> RANK_B together with PTR_D2. I mean since the downstream nodes influence
> the RANK of their upstream parent, then node D2 should compute what RANK_B
> will be if without the contribution of D2 itself.
>
> Regards,
> Derek Jianqiang Hou
>
> -----Original Message-----
> From: Chenyang JI [mailto:[email-masked]]
> Sent: Thursday, December 21, 2017 8:35 PM
> To: Houjianqiang (Derek) <[email-masked]>
> Cc: roll <[email-masked]>
> Subject: Re: Suggestions for draft-ji-roll-traffic-aware-ob
> jective-function-00
>
> Good morning,
>
> Thank you a lot for the suggestions,they are very helpful.
> I added some response below the suggestions after [RE]
>
>
> 1.      The format  of your PTR metric should be modified in order to be
> consistent with current Metric framework as define in RFC6551. Based on my
> understanding, you are not requiring IANA to assign a new "DAGMC type" but
> rather a new "Routing-MC-Type" inside the DAG Metric Container. There is a
> DAG Metric Container Format in RFC6551 you can follow and put your PTR
> inside the container as a new metric object. Your co-author Georgios has
> given a good example in his draft "draft-pkm-roll-nsa-extension-00". The
> metric container gives you many functions, such as combining PTR with other
> metrics like ETX (constraint), ChildCount (metric) and HopCount (metric),
> which has been mentioned in your draft.
>
> [RE] I'll make a new figure to clarify that Transmission rate is included
> in Metric container.
>
>
> 2.      I noticed one weak point of your solution and I have come up with
> some possible ways to solve that. Nodes select their preferred parent node
> based on the PTRs of their potential parents (if I understand it right).
> For the two-hop cases in your draft, it's fine, but for multi-hop cases,
> the downstream nodes are unaware of the PTRs of the sink nodes (nodes
> connected to the root). For example, in the right pattern of Figure 2 in
> your draft, if new nodes come in below C1/C2/D1/D2, then the new nodes will
> prefer to choose C1/C2/D1 rather than D2 (PTR_D2 is larger). Let's say new
> node E1->C1, E2->C2, E3->D1, and assume E1/E2/E3 have PTR = 1pkt/s, then in
> this case, PTR_C1 = PTR_C2 = PTR_D1 = 2 pkt/s, PTR_A = 6 pkt/s. This in the
> end triggers D1 switches from A to B. So my point is when new nodes join in
> the downstream, they strongly influence the upstream connections. This
> effect causes an unstable RPL network and should be minimized. One way I
> come up with is to use the aggregatio
>  n mode in the Metric Container so that new nodes are able to know the
> whole PTRs along a link to the root and then select based on the whole link
> condition. Another possible way is you can define a new "RANK" computation
> that includes the PTRs along a link, e.g. RANK_C1 = PTR_A+0.5*PTR_C1.
>
> [RE] You are right about the weak point,thank you.
> About the aggregation mode,if I understand correct that requires node to
> inform its direct child about its transmission rate change(new node joins
> its subtree,child changes parent etc),that may increase the frequency of
> DIO messages?
> About rank computation,nodes with larger transmission rate will have
> larger rank than its neighbor nodes so there is a possibility it selects
> its neighbor as parent and increase the traffic of other subtree.
> I don't know if I described it in the right way,I'll send a example if
> needed.
>
>
> Regards
> Chenyang
>
> ----- Original Message -----
> From: "Houjianqiang" <[email-masked]>
> To: "Chenyang JI" <[email-masked]>
> Cc: "roll" <[email-masked]>
> Sent: Thursday, December 21, 2017 7:49:08 AM
> Subject: Suggestions for draft-ji-roll-traffic-aware-objective-function-00
>
> Hi Chenyang,
>
> Nice to see that you are involved in improving the parent selection in RPL
> network, and thanks for bringing the idea "Packet Transmission Rate" into
> roll WG. Your solution is very useful, especially when traffic generated
> from different nodes is "highly" uneven. I have read through your draft and
> provide my comments and suggestions as below.
>
>
> 1.      The format  of your PTR metric should be modified in order to be
> consistent with current Metric framework as define in RFC6551. Based on my
> understanding, you are not requiring IANA to assign a new "DAGMC type" but
> rather a new "Routing-MC-Type" inside the DAG Metric Container. There is a
> DAG Metric Container Format in RFC6551 you can follow and put your PTR
> inside the container as a new metric object. Your co-author Georgios has
> given a good example in his draft "draft-pkm-roll-nsa-extension-00". The
> metric container gives you many functions, such as combining PTR with other
> metrics like ETX (constraint), ChildCount (metric) and HopCount (metric),
> which has been mentioned in your draft.
>
>
>
> 2.      I noticed one weak point of your solution and I have come up with
> some possible ways to solve that. Nodes select their preferred parent node
> based on the PTRs of their potential parents (if I understand it right).
> For the two-hop cases in your draft, it's fine, but for multi-hop cases,
> the downstream nodes are unaware of the PTRs of the sink nodes (nodes
> connected to the root). For example, in the right pattern of Figure 2 in
> your draft, if new nodes come in below C1/C2/D1/D2, then the new nodes will
> prefer to choose C1/C2/D1 rather than D2 (PTR_D2 is larger). Let's say new
> node E1->C1, E2->C2, E3->D1, and assume E1/E2/E3 have PTR = 1pkt/s, then in
> this case, PTR_C1 = PTR_C2 = PTR_D1 = 2 pkt/s, PTR_A = 6 pkt/s. This in the
> end triggers D1 switches from A to B. So my point is when new nodes join in
> the downstream, they strongly influence the upstream connections. This
> effect causes an unstable RPL network and should be minimized. One way I
> come up with is to use the aggregatio
>  n mode in the Metric Container so that new nodes are able to know the
> whole PTRs along a link to the root and then select based on the whole link
> condition. Another possible way is you can define a new "RANK" computation
> that includes the PTRs along a link, e.g. RANK_C1 = PTR_A+0.5*PTR_C1.
>
>
>
> 3.      The PTR computation method hasn't been illustrated in your draft.
> After thinking a bit more, here is my suggestion. The first method that
> came into my mind is to compute base on a time cycle, e.g. count the number
> of packet per 10 seconds, but then I denied this method for three reasons:
> 1. Nodes may have sleep mode and cannot do this PTR computation when
> sleeping; 2. a fixed time cycle may not be accurate to reflect PTR because
> nodes may send packets at different rate at different time, e.g. 1pkt/s,
> 1pkt/hour, 1pkt/day; 3. frequently computing PTR consumes more energy. I
> suggest doing the PTR computation based on the time points when sending
> packets. For example, a node send Packet_n-1 at time t_n-1 and send
> Packet_n at time t_n, then 1 / (t_n - t_n-1) reflects the packet rate. Then
> The PTR at time t_n could be
>
> PTR_n = alpha * 1 / (t_n - t_n-1) + (1 - alpha) * PTR_n-1,
>
> where alpha are constant between 0 to 1. In this way, nodes refresh their
> PTR when sending packets, and the PTR equation gives a smooth variation
> that guarantees the stability of a RPL network.
>
> Hopefully my suggestions could help to improve the quality of your draft.
>
> Best regards,
> Derek Jianqiang Hou
>
> Related drafts and RFC:
> https://datatracker.ietf.org/doc/draft-ji-roll-traffic-aware
> -objective-function/
> https://datatracker.ietf.org/doc/rfc6551/
> https://datatracker.ietf.org/doc/draft-pkm-roll-nsa-extension/
> _______________________________________________
> Roll mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/roll
>

Best,
Aris

---

From: "Houjianqiang (Derek)" <[email-masked]>
Date: Wed, 17 Jan 2018 03:26:51 +0000

Hi Aris,

Thanks for your question, please see my response in line. 

> On Fri, Dec 22, 2017 at 3:48 AM, Houjianqiang (Derek)
> <houjianqiang@huawei .com> wrote:
> 
> > Hi Chenyang,
> >
> > some possible ways to solve that. Nodes select their preferred parent
> > node based on the PTRs of their potential parents (if I understand it right).
> > For the two-hop cases in your draft, it's fine, but for multi-hop
> > cases, the downstream nodes are unaware of the PTRs of the sink nodes
> > (nodes connected to the root). For example, in the right pattern of
> > Figure 2 in your draft, if new nodes come in below C1/C2/D1/D2, then
> > the new nodes will prefer to choose C1/C2/D1 rather than D2 (PTR_D2 is
> > larger). Let's say new node E1->C1, E2->C2, E3->D1, and assume
> > E1/E2/E3 have PTR = 1pkt/s, then in this case, PTR_C1 = PTR_C2 =
> > PTR_D1 = 2 pkt/s, PTR_A = 6 pkt/s. This in the end triggers D1
> > switches from A to B. So my point is when new nodes join in the
> > downstream, they strongly influence the upstream connections. This
> > effect causes an unstable RPL network and should be minimized. One way
> > I come up with is to use the aggregatio  n mode in the Metric
> > Container so that new nodes are able to know the whole PTRs along a
> > link to the root and then select based on the whole link condition.
> > Another possible way is you can define a new "RANK" computation that
> includes the PTRs along a link, e.g. RANK_C1 = PTR_A+0.5*PTR_C1.
> >
> > About the aggregation mode,if I understand correct that requires node
> > to inform its direct child about its transmission rate change(new node
> > joins its subtree,child changes parent etc),that may increase the
> > frequency of DIO messages?
> >
> > algorithm, not the aggregation mode. RPL adapts the sending rate of
> > DIO messages by extending the Trickle algorithm. In a network with
> > stable links the control messages will be rare whereas an environment
> > in which the topology changes frequently will cause RPL to send
> > control information more often.
> >
> 
> So, in this draft, the PTR information is sourced directly from the traffic each
> node has "seen", e.g. if a node has seen 2 packets in the last second, it will
> report this 2pkts/sec. You have proposed using the aggregation mode in the
> Metric Container to alter the number reported.
> However, it also receives DIO messages from other nodes. When it gets a
> DIO message from its preferred parent it extracts the parent's reported
> PTR: PTR_PARENT.
> So when a new node E1 with PTR_OWN=1pkt/sec comes under C1,C2,D1,D2
> it will avoid D2 and it will pick one of C1,C2,D1 and report its own PTR via DIO
> as:

[Jianqiang Hou] Yes, you are right. Thanks for your interpretation, it reflects the first method I suggest. 
And to explain a bit more I have in mind, after I read Ji's draft, what I was thinking is what is the main factors in this traffic-aware OF? I think the traffic near the route is more important than the traffic on the bottom, especially for the sink nodes, that's why I suggest new nodes should be aware of the traffic along the link. The sample patterns in Ji's draft are quite simple cases, and if I induce a bit variation then you will see the one-hop PTR is not enough. Based on the current figure we are talking about (Figure 2. Balanced), if node A and B are far away in distance, C1/C2/D1 are fixed to A while D2 is fixed to B. Then when PTR_C1 increases, here let's say to 4pkt/s, that results to the pattern shown below (hopefully the font format does not influence it too much). In this case, when new node E1 joins, the "one-hop PTR" strategy puts C2/D1 in the first priority as potential parent, but if considering PTR_A and PTR_B, E1 should connects to D2. And moreover, I suppose simple aggregation by adding up PTRs along a link may not be the best choice because nodes near the root are more important and should have higher weight on PTRs, this is the reason I came up with the second method in my suggestion.

                       9pkt/s (R)
                               ^
                               |
               +--------+----------------+
               |                                           |
               +                                           +
      6pkt/s (A)                       3pkt/s (B)
               ^                                          ^
               |                                          |
   +------+------+             +--------+
   |          |          |              |
   +          +          +             +
   (C1)  (C2)   (D1)        (D2)
  4pkt/s 1pkt/s 1pkt/s   3pkt/s

Regards,
Derek