Subject: Re: [6tsch] TSCH: info for each(?) link in Enhanced Beacon frames

From: <[email-masked]>
Date: Mon, 10 Jun 2013 10:09:22 +0000

Dear All,
Regarding to our last call on Friday,  I would like to continue this discussion about the maximum number of links' information (or "link object") that can be included in EB? Can we think about sending the information about the entire reserved links/cells in the EB(s)? I would like to know, Is there any way to define a CellBitMap to enable us to include the entire reserved links/cells by each node in the one or several EB(s)?

Our motivation:
In the distributed approach, this information can be used by the receivers to schedule (internal) collision-free[*] links with others. In this case, this information is not just used for enabling the receivers to contact with the sender of ADV/EB. This information enables the receivers to collect the list of used cells in their neighborhood. The content of information in each "link object" can be different from the existing information in the EB for each link. For instance, the link option or link type might not be needed in this case. On the other hand, neighbor ID (the other side of link) might be needed to be included in the "link object".
In order to create a soft link, based on this information about its neighborhood, Node A in the Link Reservation Request may suggest the set of (internal) collision-free links to the receiver. The receiver (Node B) also based on this information in its own neighborhood, will choose one link from the suggested links that is also free in its neighborhood (that might be different from sender's neighborhood) and reply to the sender by Link Reservation Response.

[*] In realistic setting, where the interference range is more than transmission range, this information will not guarantee the completely (internal) collision-free communication. But it can be used to not repeat the reserved cells in our two-hop neighborhood. In addition, the collision caused by a pair of nodes who are using the same cell in outside of two-hop neighborhood can be detected, by monitoring the status of that reserved cell (By considering the mechanisms discussed in "2.8 Monitoring" section in draft-wang-6tsch-6tus-00).

Best wishes,
Pouria Zand

---

From: Thomas Watteyne <[email-masked]>
Date: Tue, 18 Jun 2013 11:31:36 -0700

Pouria,

This is an EXTREMELY important point you raise, and I'd really like to dig
a bit deeper. Please bear with me through the long e-mail.

My 2 cents on this (and I'm sure most of this is very well known): EBs were
designed to contain not the full schedule of a node, but rather to carry
just enough information for the new node to know how to contact the
network. Once that initial connection is established, the "network" can
assign more cells/frames in the new node's schedule. This information comes
either from a PCE, or from some distributed resource allocation protocol,
but none of that is defined in IEEE802.15.4e.

If I understand your e-mail correctly, you're looking for a way for a mote
to periodically indicate what its schedule to its neighbors is, hence the
idea of encoding that in the EB. When negotiating a soft link, the two
neighbors can instruct each other of the already used cells in their
respective neighborhoods, and pick one not used by either side.

There are number of preliminary points I'd like to make, and which I hope
we agree on:
- regardless of what we do, communication will never be collision-free.
Race conditions in the allocation of cells between neighbors and more
importantly the wireless nature of the medium make it impossible to
guarantee collision free communication. So the best we can achieve with
this technique is to make an "informed decision" about what cell to use.
- in the same vein, there has to be a mechanism to detect collisions, and
re-schedule the affected cell(s). This is what Qin has called the
monitoring process in 6tus [1].

With your proposal, we basically have two opposed approaches:
1. pick a new soft cell randomly in the schedule, and rely on the
monitoring process to move that in the schedule. Extremely simple and
lightweight approach.
2. have each node announce its schedule periodically (through custom IEs in
the EBs, or through some other mechanism), and use that information
during negotiation  Potentially more efficient, but possibly much more
overhead.

What would really be interesting is to know where the boundary lies between
1 and 2. It seems pretty clear that, in a very sparse network, 1 is the
best option. Yet, as the traffic increases, 2 becomes appealing.

I have the feeling that the boundary is really high, i.e. 1 will work well,
unless you get to a really full schedule. Would you be interested in
looking at this from a statistical and/or simulation point of view?

Thomas

[1] http://tools.ietf.org/html/draft-wang-6tsch-6tus-01#section-2.8

On Mon, Jun 10, 2013 at 3:09 AM, <[email-masked]> wrote:

>  Dear All,****
>
> Regarding to our last call on Friday,  I would like to continue this
> discussion about the maximum number of links’ information (or “link
> object”) that can be included in EB? Can we think about sending the
> information about the entire reserved links/cells in the EB(s)? I would
> like to know, Is there any way to define a CellBitMap to enable us to
> include the entire reserved links/cells by each node in the one or several
> EB(s)?****
>
> * *
>
> *Our motivation*:****
>
> In the distributed approach, this information can be used by the receivers
> to schedule (internal) collision-free[*] links with others. In this case,
> this information is not just used for enabling the receivers to contact
> with the sender of ADV/EB. This information enables the receivers to
> collect the list of used cells in their neighborhood. The content of
> information in each “link object” can be different from the existing
> information in the EB for each link. For instance, the link option or link
> type might not be needed in this case. On the other hand, neighbor ID (the
> other side of link) might be needed to be included in the “link object”. *
> ***
>
> In order to create a soft link, based on this information about its
> neighborhood, Node A in the *Link Reservation Request* may suggest the
> set of (internal) collision-free links to the receiver. The receiver (Node
> B) also based on this information in its own neighborhood, will choose one
> link from the suggested links that is also free in its neighborhood (that
> might be different from sender's neighborhood) and reply to the sender by
> * Link Reservation Response*.****
>
> ** **
>
> [*] In realistic setting, where the interference range is more than
> transmission range, this information will not guarantee the completely
> (internal) collision-free communication. But it can be used to not repeat
> the reserved cells in our two-hop neighborhood. In addition, the collision
> caused by a pair of nodes who are using the same cell in outside of two-hop
> neighborhood can be detected, by monitoring the status of that reserved
> cell (By considering the mechanisms discussed in “2.8 Monitoring” section
> in draft-wang-6tsch-6tus-00).****
>
> ** **
>
> Best wishes,****
>
> Pouria Zand****
>
> _______________________________________________
> 6tsch mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/6tsch

 <https://www.ietf.org/mailman/listinfo/6tsch>

---

From: Xavier Vilajosana <[email-masked]>
Date: Tue, 18 Jun 2013 12:12:19 -0700

Thomas, Pouria, all,

we can have multiple slotFrame coexisting and a slotFrame can have more 
than 1000 slots, I don't think a bitmap can be used to announce that 
information in very dense schedules.  I bet for case 1 depicted by 
Thomas, where monitoring of bad links might trigger reallocation, this 
would be simple and will eventually find good approximations to the 
optimal. The only problem might be to avoid continuous jumping or at 
least characterize it to see how will behave w.r.t the schedule density.

What can be done by 6tus distributed negotiation process is to propose 
candidate links (Schedule IE) to the neighbour when reserving and let 
the neighbour pick someone that fits into its schedule, this can be done 
using a bitmap [1].

[1] http://tools.ietf.org/html/draft-wang-6tsch-6tus-01#section-2.5.1.7 
<http://tools.ietf.org/html/draft-wang-6tsch-6tus-01#section-2.8>

regards,
Xavi

Al 18/06/13 11:31, En/na Thomas Watteyne ha escrit:
> Pouria,
>
> This is an EXTREMELY important point you raise, and I'd really like to 
> dig a bit deeper. Please bear with me through the long e-mail.
>
> My 2 cents on this (and I'm sure most of this is very well known): EBs 
> were designed to contain not the full schedule of a node, but rather 
> to carry just enough information for the new node to know how to 
> contact the network. Once that initial connection is established, the 
> "network" can assign more cells/frames in the new node's schedule. 
> This information comes either from a PCE, or from some distributed 
> resource allocation protocol, but none of that is defined in 
> IEEE802.15.4e.
>
> If I understand your e-mail correctly, you're looking for a way for a 
> mote to periodically indicate what its schedule to its neighbors is, 
> hence the idea of encoding that in the EB. When negotiating a soft 
> link, the two neighbors can instruct each other of the already used 
> cells in their respective neighborhoods, and pick one not used by 
> either side.
>
> There are number of preliminary points I'd like to make, and which I 
> hope we agree on:
> - regardless of what we do, communication will never be 
> collision-free. Race conditions in the allocation of cells between 
> neighbors and more importantly the wireless nature of the medium make 
> it impossible to guarantee collision free communication. So the best 
> we can achieve with this technique is to make an "informed decision" 
> about what cell to use.
> - in the same vein, there has to be a mechanism to detect collisions, 
> and re-schedule the affected cell(s). This is what Qin has called the 
> 2. have each node announce its schedule periodically (through custom 
> IEs in the EBs, or through some other mechanism), and use that 
> information during negotiation Potentially more efficient, but 
> possibly much more overhead.
>
> What would really be interesting is to know where the boundary lies 
> between 1 and 2. It seems pretty clear that, in a very sparse network, 
> 1 is the best option. Yet, as the traffic increases, 2 becomes appealing.
>
> I have the feeling that the boundary is really high, i.e. 1 will work 
> well, unless you get to a really full schedule. Would you be 
> interested in looking at this from a statistical and/or simulation 
> point of view?
>
> Thomas
>
> On Mon, Jun 10, 2013 at 3:09 AM, <[email-masked] 
> <mailto:[email-masked]>> wrote:
>
>     Dear All,
>
>     Regarding to our last call on Friday,  I would like to continue
>     this discussion about the maximum number of links' information (or
>     "link object") that can be included in EB? Can we think about
>     sending the information about the entire reserved links/cells in
>     the EB(s)? I would like to know, Is there any way to define a
>     CellBitMap to enable us to include the entire reserved links/cells
>     by each node in the one or several EB(s)?
>
>     **
>
>     *Our motivation*:
>
>     In the distributed approach, this information can be used by the
>     receivers to schedule (internal) collision-free[*] links with
>     others. In this case, this information is not just used for
>     enabling the receivers to contact with the sender of ADV/EB. This
>     information enables the receivers to collect the list of used
>     cells in their neighborhood. The content of information in each
>     "link object" can be different from the existing information in
>     the EB for each link. For instance, the link option or link type
>     might not be needed in this case. On the other hand, neighbor ID
>     (the other side of link) might be needed to be included in the
>     "link object".
>
>     In order to create a soft link, based on this information about
>     its neighborhood, Node A in the *Link Reservation Request* may
>     suggest the set of (internal) collision-free links to the
>     receiver. The receiver (Node B) also based on this information in
>     its own neighborhood, will choose one link from the suggested
>     links that is also free in its neighborhood (that might be
>     different from sender's neighborhood) and reply to the sender by
>     *Link Reservation Response*.
>
>     [*] In realistic setting, where the interference range is more
>     than transmission range, this information will not guarantee the
>     completely (internal) collision-free communication. But it can be
>     used to not repeat the reserved cells in our two-hop neighborhood.
>     In addition, the collision caused by a pair of nodes who are using
>     the same cell in outside of two-hop neighborhood can be detected,
>     by monitoring the status of that reserved cell (By considering the
>     mechanisms discussed in "2.8 Monitoring" section in
>     draft-wang-6tsch-6tus-00).
>
>     Best wishes,
>
>     Pouria Zand
>
>
>     [email-masked] <mailto:[email-masked]>

---

From: Qin Wang <[email-masked]>
Date: Wed, 19 Jun 2013 04:35:19 +0800

Hi,

(1) I fully agree with Thomas that "regardless of what we do, communication
will never be collision-free", therefore, a monitoring processing in 6tus
is necessary. And then, what we need to do is to find better solution,
instead of best solution (it may not exist).

(2)  I think, during a process of softcell reservation, telling the
receiver the candidate set  from the sender's point of view, instead of the
cell set used by sender, will provide more information, and thus is more
effective, because a candidate cell should be a cell not be used by the
sender, and not likely be collided by the neighbors of the sender.

(3)  Regarding to express the candidate set, many methods can be used, such
as cell list, bitmap, maybe others.

(4) Regarding to reporting cell usage periodically, IMHO, it could be very
low energy and low bandwidth efficient if considering the dynamic of
network and the uncertainty of wireless environment.

Thought?
Qin

On Wed, Jun 19, 2013 at 3:12 AM, Xavier Vilajosana <
[email-masked]> wrote:

> information in very dense schedules.  I bet for case 1 depicted by Thomas,
> where monitoring of bad links might trigger reallocation, this would be
> simple and will eventually find good approximations to the optimal. The
> only problem might be to avoid continuous jumping or at least characterize
> it to see how will behave w.r.t the schedule density.
>
> candidate links (Schedule IE) to the neighbour when reserving and let the
> neighbour pick someone that fits into its schedule, this can be done using
> a bitmap [1].
>
> [1] http://tools.ietf.org/html/draft-wang-6tsch-6tus-01#section-2.5.1.7<http://tools.ietf.org/html/draft-wang-6tsch-6tus-01#section-2.8>
>
> regards,
> Xavi
>
> were designed to contain not the full schedule of a node, but rather to
> carry just enough information for the new node to know how to contact the
> mote to periodically indicate what its schedule to its neighbors is, hence
> the idea of encoding that in the EB. When negotiating a soft link, the two
> 2. have each node announce its schedule periodically (through custom IEs
> in the EBs, or through some other mechanism), and use that information
> between 1 and 2. It seems pretty clear that, in a very sparse network, 1 is
> the best option. Yet, as the traffic increases, 2 becomes appealing.
>
> well, unless you get to a really full schedule. Would you be interested in
>> EB(s)?
>> receivers to schedule (internal) collision-free[*] links with others. In
>> this case, this information is not just used for enabling the receivers to
>> contact with the sender of ADV/EB. This information enables the receivers
>> to collect the list of used cells in their neighborhood. The content of
>> other side of link) might be needed to be included in the “link object”.
>>
>> * Link Reservation Response*.
>>
>>
>>
>> in draft-wang-6tsch-6tus-00).
>>
>>
>>
>> Best wishes,
>>
>> Pouria Zand
>>
> 6tsch mailing [email-masked]://www.ietf.org/mailman/listinfo/6tsch
>
>
>

---

From: Kris Pister <[email-masked]>
Date: Tue, 18 Jun 2013 13:41:32 -0700

Pouria -
  this is good stuff, and I'm glad to see you pursuing it.  When we 
first started talking about working in the IETF to standardize the gap 
between 6lowpan and 15.4e I thought that surely all of those IP 
devotees, who had been so certain that centralized network management 
didn't work, would step up and demonstrate how to do it right with a 
distributed approach.  I do think that you can build perfectly good 
networks this way, and in fact we'll have some advantages over centrally 
managed networks - speed and mobility for sure, I'm not convinced about 
scalability.

Bitmaps of occupied TX and RX cells in Information Elements seems like a 
good idea to me - maybe there are better ways to do it.  The one thing 
that I would ask is that you not make it a *requirement* that these IEs 
be in EBs.  I have no problem if you want to make it optional, for those 
networks that want to use it, or even mandatory as a response to a 
request.  But please let's not burden every EB with that information.

Clearly having complete knowledge of the neighbor link tables enables 
you to optimize link schedules.  I'm curious to know, though, how well 
you can do with just random choice, with some feedback on bad links.  If 
we look at randomly assigned links in a superframe with L_max cells (=S 
slots * C channels), and consider the collision domain to be the union 
of the neighbors of mote A and mote B (conservative, but the bound is 
achieved occasionally in practice), then the probability that a cell is 
unoccupied is
P0 = e^-GL where
GL = L_a / L_max where
L_a is the number of assigned cells (either TX, or RX, or both).

If we're using 15.4e at 2.4GHz, then C is probably 15.  If this local 
piece of the network has scheduled on average something in every slot, 
then GL=1/15, and P0=0.94.  So randomly selected links are usually going 
to work.  Having an average of one link assigned per slot in a given two 
mote neighborhood is really high, at least for any network that I've 
ever built or sold.  Sometimes we approach this at the DAG root.  This 
is not to say that transmitting neighbor tables is not a good thing, 
just that you can build a lot of applications with very simple (random) 
cell allocation.  So sending the neighbor tables is not necessary for 
many/most networks, but would be a nice option to have for future 
optimizations.

ksjp

p.s. an interesting question arises about the goodput of a random link 
assignment approach.  Many of the links will be non-colliding. Those 
that do collide will exhibit slotted aloha collision statistics...or 
will they?  With a mix of non-colliding and potentially colliding links 
at each mote, what is the network goodput?  I'm sure that someone has 
written a paper on this for MPLS or something, but I've never seen one.

On 6/10/2013 3:09 AM, [email-masked] wrote:
> discussion about the maximum number of links' information (or "link 
> object") that can be included in EB? Can we think about sending the 
> information about the entire reserved links/cells in the EB(s)? I 
> would like to know, Is there any way to define a CellBitMap to enable 
> us to include the entire reserved links/cells by each node in the one 
> or several EB(s)?
>
> **
>
> *Our motivation*:
>
> receivers to schedule (internal) collision-free[*] links with others. 
> In this case, this information is not just used for enabling the 
> receivers to contact with the sender of ADV/EB. This information 
> enables the receivers to collect the list of used cells in their 
> neighborhood. The content of information in each "link object" can be 
> different from the existing information in the EB for each link. For 
> instance, the link option or link type might not be needed in this 
> case. On the other hand, neighbor ID (the other side of link) might be 
> needed to be included in the "link object".
>
> set of (internal) collision-free links to the receiver. The receiver 
> (Node B) also based on this information in its own neighborhood, will 
> choose one link from the suggested links that is also free in its 
> neighborhood (that might be different from sender's neighborhood) and 
> reply to the sender by *Link Reservation Response*.
>
> (internal) collision-free communication. But it can be used to not 
> repeat the reserved cells in our two-hop neighborhood. In addition, 
> the collision caused by a pair of nodes who are using the same cell in 
> outside of two-hop neighborhood can be detected, by monitoring the 
> status of that reserved cell (By considering the mechanisms discussed 
> in "2.8 Monitoring" section in draft-wang-6tsch-6tus-00).
>
> Best wishes,
>
> Pouria Zand
>
>
>

---

From: <[email-masked]>
Date: Wed, 19 Jun 2013 11:47:00 +0000

Dear Kris, All,
Many thanks for your complete explanation. I completely agree with you that "Bitmaps of occupied cells" can be sent in possible other ways and there is no "requirement" to just include those information in EB. As you mentioned, we can make it optional for some applications and/or use another mechanisms (e.g. request-response) to get those information from the neighbors. For those possible applications that might need very dense schedules (more than one link per slot) in two-hop neighborhood, we might be able to decrease the probability of cell re-allocation at the cost of increasing the network overhead (caused by exchanging occupied cells info).

Qin, Thomas-
I completely agree with you that without monitoring processing, the collision-free communication is not achievable, in a distributed manner.
I attached a Figure to illustrate the concept more clearly for others as well. In summary, in order to choose a soft link on edge (A, B) (as is shown in Figure (a)), the "cell usage information" might be helpful during the soft link negotiation. Those information (i) enables node A to propose a set of unused cells in his neighborhood (as is shown in Figure (b)) as candidate cells in the Link Reservation Request , and (ii) enables node B to pick up a cell that is not used either in his neighborhood (as is shown in Figure (c)) and then reply by Link Reservation Response.
For sure this method might have some costs (e.g. increasing the management overhead) and might not be suitable for those applications that doesn't have every dense schedule. But it might be affordable for those applications that require dense schedules, at the cost of more management overhead.
In addition, I would like to add one approaches to the Thomas's list:
1. pick a new soft cell randomly in the schedule, and rely on the monitoring process to move that in the schedule. Extremely simple and lightweight approach.
2. have each node announce its schedule periodically (through custom IEs in the EBs, or through some other mechanism), and use that information during negotiation Potentially more efficient, but possibly much more overhead.
3. the combination of (2) and monitoring process.
As Thomas mentioned, there could be a different boundaries in which using methods (1), (2) or (3) would be considerable. As Kris and Thomas suggest, I think evaluating different scenarios (i.e. regular schedule and dense schedule) can be useful to clarify those boundaries. To measure the network goodput and management overhead in those approaches.

Xavi-
I agree with you that having multiple slotFrames with different length, make it difficult to use bitmap in the very dense schedule. In this case, we might look for a better way. For instance, considering the request-response mechanism and/or exchanging the changes in a node's cell usages bitmap instead of reporting all cell usage bitmap periodically.

In this figure I assumed that the Tx range and interference ranges are equal. In the realistic setting that those ranges are not equal, the monitoring process will be useful.

Best Wishes,
Pouria

From: [email-masked] [mailto:[email-masked]] On Behalf Of Kris Pister
Sent: Tuesday, June 18, 2013 10:42 PM
To: [email-masked]
Subject: Re: [6tsch] TSCH: info for each(?) link in Enhanced Beacon frames

Pouria -
 this is good stuff, and I'm glad to see you pursuing it.  When we first started talking about working in the IETF to standardize the gap between 6lowpan and 15.4e I thought that surely all of those IP devotees, who had been so certain that centralized network management didn't work, would step up and demonstrate how to do it right with a distributed approach.  I do think that you can build perfectly good networks this way, and in fact we'll have some advantages over centrally managed networks - speed and mobility for sure, I'm not convinced about scalability.

Bitmaps of occupied TX and RX cells in Information Elements seems like a good idea to me - maybe there are better ways to do it.  The one thing that I would ask is that you not make it a *requirement* that these IEs be in EBs.  I have no problem if you want to make it optional, for those networks that want to use it, or even mandatory as a response to a request.  But please let's not burden every EB with that information.

Clearly having complete knowledge of the neighbor link tables enables you to optimize link schedules.  I'm curious to know, though, how well you can do with just random choice, with some feedback on bad links.  If we look at randomly assigned links in a superframe with L_max cells (=S slots * C channels), and consider the collision domain to be the union of the neighbors of mote A and mote B (conservative, but the bound is achieved occasionally in practice), then the probability that a cell is unoccupied is
P0 = e^-GL where
GL = L_a / L_max where
L_a is the number of assigned cells (either TX, or RX, or both).

If we're using 15.4e at 2.4GHz, then C is probably 15.  If this local piece of the network has scheduled on average something in every slot, then GL=1/15, and P0=0.94.  So randomly selected links are usually going to work.  Having an average of one link assigned per slot in a given two mote neighborhood is really high, at least for any network that I've ever built or sold.  Sometimes we approach this at the DAG root.  This is not to say that transmitting neighbor tables is not a good thing, just that you can build a lot of applications with very simple (random) cell allocation.  So sending the neighbor tables is not necessary for many/most networks, but would be a nice option to have for future optimizations.

ksjp

p.s. an interesting question arises about the goodput of a random link assignment approach.  Many of the links will be non-colliding.  Those that do collide will exhibit slotted aloha collision statistics...or will they?  With a mix of non-colliding and potentially colliding links at each mote, what is the network goodput?  I'm sure that someone has written a paper on this for MPLS or something, but I've never seen one.
On 6/10/2013 3:09 AM, [email-masked]<mailto:[email-masked]> wrote:
Dear All,
Regarding to our last call on Friday,  I would like to continue this discussion about the maximum number of links' information (or "link object") that can be included in EB? Can we think about sending the information about the entire reserved links/cells in the EB(s)? I would like to know, Is there any way to define a CellBitMap to enable us to include the entire reserved links/cells by each node in the one or several EB(s)?

Our motivation:

Best wishes,
Pouria Zand

6tsch mailing list

[email-masked]<mailto:[email-masked]>

---

From: Qin Wang <[email-masked]>
Date: Wed, 19 Jun 2013 20:14:05 +0800

Hi Pouria,

Just one comment on "exchanging the *changes* in a node’s cell usages
bitmap instead of reporting all cell usage bitmap periodically."

I think one of motivations to use decentralized reservation is dealing with
mobility. That means nodes are joining and leaving relatively frequently.
So, exchanging the *changes* may not give the moving node the picture of
cell usage around it,

Thought?
Qin

On Wed, Jun 19, 2013 at 7:47 PM, <[email-masked]> wrote:

>  *Dear Kris, All,*
>
> Many thanks for your complete explanation. I completely agree with you
> that “Bitmaps of occupied cells” can be sent in possible other ways and
> there is no “requirement” to just include those information in EB. As you
> mentioned, we can make it optional for some applications and/or use another
> mechanisms (e.g. request-response) to get those information from the
> neighbors. For those possible applications that might need very dense
> schedules (more than one link per slot) in two-hop neighborhood, we might
> be able to decrease the probability of cell re-allocation at the cost of
> increasing the network overhead (caused by exchanging occupied cells
> info).   ****
>
> ** **
>
> *Qin, Thomas-*
>
> I completely agree with you that without monitoring processing, the
> collision-free communication is not achievable, in a distributed manner. *
> ***
>
> I attached a *Figure* to illustrate the concept more clearly for others
> as well. In summary, in order to choose a *soft link* on edge (A, B) (as
> is shown in Figure (a)), the “cell usage information” might be helpful
> during the *soft link* negotiation. Those information (i) enables node A
> to propose a set of unused cells in his neighborhood (as is shown in Figure
> (b)) as candidate cells in the* Link Reservation Request* , and (ii)
> enables node B to pick up a cell that is not used either in his
> neighborhood (as is shown in Figure (c)) and then reply by *Link
> Reservation Response*. ****
>
> For sure this method might have some costs (e.g. increasing the management
> overhead) and might not be suitable for those applications that doesn’t
> have every dense schedule. But it might be affordable for those
> applications that require dense schedules, at the cost of more management
> overhead.  ****
>
> In addition, I would like to add one approaches to the Thomas’s list: ****
>
> lightweight approach.****
>
> overhead.****
> *3. the combination of (2) and monitoring process*. ****
>
> As Thomas mentioned, there could be a different boundaries in which using
> methods (1), (2) or (3) would be considerable. As Kris and Thomas suggest,
> I think evaluating different scenarios (i.e. regular schedule and dense
> schedule) can be useful to clarify those boundaries. To measure the network
> goodput and management overhead in those approaches. ****
>
> ** **
>
> *Xavi-*
>
> I agree with you that having multiple slotFrames with different length,
> make it difficult to use bitmap in the very dense schedule. In this case,
> we might look for a better way. For instance, considering the
> request-response mechanism and/or exchanging the *changes* in a node’s
> cell usages bitmap instead of reporting all cell usage bitmap
> periodically.  ****
>
> ** **
>
> In this figure I assumed that the Tx range and interference ranges are
> equal. In the realistic setting that those ranges are not equal, the
> monitoring process will be useful.****
>
> ** **
>
> ****
>
> ** **
>
> Best Wishes,****
>
> Pouria  ****
>
> ** **
>
> ** **
>
> ** **
>
> *From:* [email-masked] [mailto:[email-masked]] *On Behalf
> Of *Kris Pister
> *Sent:* Tuesday, June 18, 2013 10:42 PM
> *To:* [email-masked]
> *Subject:* Re: [6tsch] TSCH: info for each(?) link in Enhanced Beacon
> frames****
>
> ** **
>
> Pouria -
>  this is good stuff, and I'm glad to see you pursuing it.  When we first
> started talking about working in the IETF to standardize the gap between
> 6lowpan and 15.4e I thought that surely all of those IP devotees, who had
> been so certain that centralized network management didn't work, would step
> up and demonstrate how to do it right with a distributed approach.  I do
> think that you can build perfectly good networks this way, and in fact
> we'll have some advantages over centrally managed networks - speed and
> mobility for sure, I'm not convinced about scalability.
>
> good idea to me - maybe there are better ways to do it.  The one thing that
> I would ask is that you not make it a *requirement* that these IEs be in
> EBs.  I have no problem if you want to make it optional, for those networks
> that want to use it, or even mandatory as a response to a request.  But
> please let's not burden every EB with that information.
>
> Clearly having complete knowledge of the neighbor link tables enables you
> to optimize link schedules.  I'm curious to know, though, how well you can
> do with just random choice, with some feedback on bad links.  If we look at
> randomly assigned links in a superframe with L_max cells (=S slots * C
> channels), and consider the collision domain to be the union of the
> neighbors of mote A and mote B (conservative, but the bound is achieved
> occasionally in practice), then the probability that a cell is unoccupied
> is
> P0 = e^-GL where
> GL = L_a / L_max where
> piece of the network has scheduled on average something in every slot, then
> GL=1/15, and P0=0.94.  So randomly selected links are usually going to
> work.  Having an average of one link assigned per slot in a given two mote
> neighborhood is really high, at least for any network that I've ever built
> or sold.  Sometimes we approach this at the DAG root.  This is not to say
> that transmitting neighbor tables is not a good thing, just that you can
> build a lot of applications with very simple (random) cell allocation.  So
> sending the neighbor tables is not necessary for many/most networks, but
> would be a nice option to have for future optimizations.
>
> ksjp
>
> assignment approach.  Many of the links will be non-colliding.  Those that
> do collide will exhibit slotted aloha collision statistics...or will they?
> With a mix of non-colliding and potentially colliding links at each mote,
> what is the network goodput?  I'm sure that someone has written a paper on
> this for MPLS or something, but I've never seen one.****
>
> On 6/10/2013 3:09 AM, [email-masked] wrote:****
>
> Dear All,****
>
> * *****
>  ****
>  ****
> ****
> _______________________________________________****
>
> 6tsch mailing list****
>
> [email-masked]****
>
> https://www.ietf.org/mailman/listinfo/6tsch****
>
>  ** **
>

---

From: <[email-masked]>
Date: Wed, 19 Jun 2013 13:18:24 +0000

Hi Qin,

Many thanks for your comment. I see your point.

For sure exchanging just changes might not be a good solution. In addition, the existing node might lose some information about the changes, due to the possible interference and packet drops.
So, I think we need to think more about the possible solutions.
Just as a quick response we might have active and passive approaches:

  1.  Active approach (Request-response mechanism): The combination of requesting the changes and all cell usages might work. For instance, we might consider the request-response mechanism for the new node, to get all cell usages from its neighbors, upon joining. Then the new node might be able to periodically use the same mechanism to ask about the changes in the neighbors' cell usage.
  2.  Passive approach (Broadcasting mechanism): We might be able to segment those information into several segments and consider index for each segment. We might need to broadcast several messages to report all cell usage. Each node periodically broadcasts those information.
  3.  Hybrid approach (Request-response and broadcasting mechanism): Each node broadcast the changes that are identified by the sequence number periodically. The new node that joins the network (or old device who has not received the changes from its neighbor for a while or missed some segments), might use the request-response mechanism for asking the all cell usages.

Am I right?
Pouria

From: Qin Wang [mailto:[email-masked]]
Sent: Wednesday, June 19, 2013 2:14 PM
To: Zand, P. (EWI)
Cc: [email-masked]; [email-masked]
Subject: Re: [6tsch] TSCH: info for each(?) link in Enhanced Beacon frames

Hi Pouria,

Just one comment on "exchanging the changes in a node's cell usages bitmap instead of reporting all cell usage bitmap periodically."

I think one of motivations to use decentralized reservation is dealing with mobility. That means nodes are joining and leaving relatively frequently. So, exchanging the changes may not give the moving node the picture of cell usage around it,

Thought?
Qin

On Wed, Jun 19, 2013 at 7:47 PM, <[email-masked]<mailto:[email-masked]>> wrote:
Dear Kris, All,
Many thanks for your complete explanation. I completely agree with you that "Bitmaps of occupied cells" can be sent in possible other ways and there is no "requirement" to just include those information in EB. As you mentioned, we can make it optional for some applications and/or use another mechanisms (e.g. request-response) to get those information from the neighbors. For those possible applications that might need very dense schedules (more than one link per slot) in two-hop neighborhood, we might be able to decrease the probability of cell re-allocation at the cost of increasing the network overhead (caused by exchanging occupied cells info).

Qin, Thomas-

Xavi-

Best Wishes,
Pouria

From: [email-masked]<mailto:[email-masked]> [mailto:[email-masked]<mailto:[email-masked]>] On Behalf Of Kris Pister
Sent: Tuesday, June 18, 2013 10:42 PM
To: [email-masked]<mailto:[email-masked]>
Subject: Re: [6tsch] TSCH: info for each(?) link in Enhanced Beacon frames

Pouria -

ksjp

Our motivation:

Best wishes,
Pouria Zand

6tsch mailing list

---

From: Maria Rita PALATTELLA <[email-masked]>
Date: Wed, 19 Jun 2013 13:23:40 +0000

Dear Pouria, all,

many thanks for this very interesting discussion. I have few additional comments.

I am afraid the “cell usage information”  exchange can generate a lot of overhead. For instance, one thing that comes in my mind is the generation of redundant information. If you look at  Fig. (b) and (c), you can notice that most of node A's  2-hop neighbors are also node B's two-hop neighbors (the two-hop ranges mainly overlap).Then, I wonder why we should transmit the same information twice?
For sure, node A will not suggest in its Link Reservation Request to node B a cell that is used by their common neighbors. Do you agree with me? Or am I missing something?

Moreover I am not in favor of the random approach (1) you are suggesting. Acting in a very blind way, will give extra-work to the monitoring process, and then to the re-scheduling procedure.
I would prefer to carefully select the cells, instead of keeping in monitoring and reallocating them.

Best regards,
Maria Rita

________________________________
From: [email-masked] [[email-masked]] on behalf of [email-masked] [[email-masked]]
Sent: Wednesday, June 19, 2013 1:47 PM
To: [email-masked]; [email-masked]
Subject: Re: [6tsch] TSCH: info for each(?) link in Enhanced Beacon frames

Dear Kris, All,
Many thanks for your complete explanation. I completely agree with you that “Bitmaps of occupied cells” can be sent in possible other ways and there is no “requirement” to just include those information in EB. As you mentioned, we can make it optional for some applications and/or use another mechanisms (e.g. request-response) to get those information from the neighbors. For those possible applications that might need very dense schedules (more than one link per slot) in two-hop neighborhood, we might be able to decrease the probability of cell re-allocation at the cost of increasing the network overhead (caused by exchanging occupied cells info).

Qin, Thomas-
I completely agree with you that without monitoring processing, the collision-free communication is not achievable, in a distributed manner.
I attached a Figure to illustrate the concept more clearly for others as well. In summary, in order to choose a soft link on edge (A, B) (as is shown in Figure (a)), the “cell usage information” might be helpful during the soft link negotiation. Those information (i) enables node A to propose a set of unused cells in his neighborhood (as is shown in Figure (b)) as candidate cells in the Link Reservation Request , and (ii) enables node B to pick up a cell that is not used either in his neighborhood (as is shown in Figure (c)) and then reply by Link Reservation Response.
For sure this method might have some costs (e.g. increasing the management overhead) and might not be suitable for those applications that doesn’t have every dense schedule. But it might be affordable for those applications that require dense schedules, at the cost of more management overhead.
In addition, I would like to add one approaches to the Thomas’s list:
1. pick a new soft cell randomly in the schedule, and rely on the monitoring process to move that in the schedule. Extremely simple and lightweight approach.
2. have each node announce its schedule periodically (through custom IEs in the EBs, or through some other mechanism), and use that information during negotiation Potentially more efficient, but possibly much more overhead.
3. the combination of (2) and monitoring process.
As Thomas mentioned, there could be a different boundaries in which using methods (1), (2) or (3) would be considerable. As Kris and Thomas suggest, I think evaluating different scenarios (i.e. regular schedule and dense schedule) can be useful to clarify those boundaries. To measure the network goodput and management overhead in those approaches.

Xavi-
I agree with you that having multiple slotFrames with different length, make it difficult to use bitmap in the very dense schedule. In this case, we might look for a better way. For instance, considering the request-response mechanism and/or exchanging the changes in a node’s cell usages bitmap instead of reporting all cell usage bitmap periodically.

Best Wishes,
Pouria

Pouria -

ksjp

p.s. an interesting question arises about the goodput of a random link assignment approach.  Many of the links will be non-colliding.  Those that do collide will exhibit slotted aloha collision statistics...or will they?  With a mix of non-colliding and potentially colliding links at each mote, what is the network goodput?  I'm sure that someone has written a paper on this for MPLS or something, but I've never seen one.
On 6/10/2013 3:09 AM, [email-masked]<mailto:[email-masked]> wrote:
Dear All,
Regarding to our last call on Friday,  I would like to continue this discussion about the maximum number of links’ information (or “link object”) that can be included in EB? Can we think about sending the information about the entire reserved links/cells in the EB(s)? I would like to know, Is there any way to define a CellBitMap to enable us to include the entire reserved links/cells by each node in the one or several EB(s)?

Our motivation:
In the distributed approach, this information can be used by the receivers to schedule (internal) collision-free[*] links with others. In this case, this information is not just used for enabling the receivers to contact with the sender of ADV/EB. This information enables the receivers to collect the list of used cells in their neighborhood. The content of information in each “link object” can be different from the existing information in the EB for each link. For instance, the link option or link type might not be needed in this case. On the other hand, neighbor ID (the other side of link) might be needed to be included in the “link object”.
In order to create a soft link, based on this information about its neighborhood, Node A in the Link Reservation Request may suggest the set of (internal) collision-free links to the receiver. The receiver (Node B) also based on this information in its own neighborhood, will choose one link from the suggested links that is also free in its neighborhood (that might be different from sender's neighborhood) and reply to the sender by Link Reservation Response.

[*] In realistic setting, where the interference range is more than transmission range, this information will not guarantee the completely (internal) collision-free communication. But it can be used to not repeat the reserved cells in our two-hop neighborhood. In addition, the collision caused by a pair of nodes who are using the same cell in outside of two-hop neighborhood can be detected, by monitoring the status of that reserved cell (By considering the mechanisms discussed in “2.8 Monitoring” section in draft-wang-6tsch-6tus-00).

Best wishes,
Pouria Zand

6tsch mailing list

---

From: <[email-masked]>
Date: Wed, 19 Jun 2013 13:48:33 +0000

Hi Maria Rita,
Many thanks for your comments.
Please note that for sure in this mechanism we will have more communication overhead. The point is address the requirements of those applications that might require very dense schedule.
Regarding to your comment about the redundant information, node A does not use this information just for negotiation with node B to create a soft link. Node A might need to create a soft link with other neighbors (e.g. C, D, or E), then node A will use that information to create a soft link with them as well.
I think Kris provide a complete explanation, that why random approach will be satisfactory for most of the applications with regular requirements.
Best Wishes,
Pouria

From: Maria Rita PALATTELLA [mailto:[email-masked]]
Sent: Wednesday, June 19, 2013 3:24 PM
To: Zand, P. (EWI); [email-masked]; [email-masked]
Subject: RE: [6tsch] TSCH: info for each(?) link in Enhanced Beacon frames

Dear Pouria, all,

I am afraid the "cell usage information"  exchange can generate a lot of overhead. For instance, one thing that comes in my mind is the generation of redundant information. If you look at  Fig. (b) and (c), you can notice that most of node A's  2-hop neighbors are also node B's two-hop neighbors (the two-hop ranges mainly overlap).Then, I wonder why we should transmit the same information twice?
For sure, node A will not suggest in its Link Reservation Request to node B a cell that is used by their common neighbors. Do you agree with me? Or am I missing something?

Best regards,
Maria Rita

From: [email-masked] [mailto:[email-masked]] On Behalf Of [email-masked]
Sent: Wednesday, June 19, 2013 3:18 PM
To: [email-masked]
Cc: [email-masked]; [email-masked]
Subject: Re: [6tsch] TSCH: info for each(?) link in Enhanced Beacon frames

Hi Qin,

Am I right?
Pouria

From: Qin Wang [mailto:[email-masked]]
Sent: Wednesday, June 19, 2013 2:14 PM
To: Zand, P. (EWI)
Cc: [email-masked]<mailto:[email-masked]>; [email-masked]<mailto:[email-masked]>
Subject: Re: [6tsch] TSCH: info for each(?) link in Enhanced Beacon frames

Hi Pouria,

Thought?
Qin

Qin, Thomas-

Xavi-

Best Wishes,
Pouria

Pouria -

ksjp

Our motivation:

Best wishes,
Pouria Zand

6tsch mailing list

---

From: Xavier Vilajosana <[email-masked]>
Date: Wed, 19 Jun 2013 11:00:39 -0700

This problem is not new, in P2P communities I've seen many different 
approaches to deal with keeping a distributed state (consistency). I 
think there are 2 main directions, pessimistic and optimistic, 
pessimistic approaches aim to enforce all nodes with the same 
information which requires transmitting the exact state to the 
neighbours and make sure it is installed there, usually this is done in 
master-slave architectures where the master tells the slaves what to do 
and won't fit to our scenario (this is the PCE case in fact)

A more scalable approach is to tolerate a little bit of 
de-synchronization (optimistic consistency) and think that eventually 
all nodes will learn about the scheduling state. With that approach we 
can have scheduling problems in case 2 nodes do not have their schedule 
completely synchronized, however monitoring can help to detect that and 
correct eventually. My opinion is that the schedule does not change so 
much so having optimistic approaches would work well (in terms of 
scalability). To achieve that, nodes might send portions of their 
schedule, assuming that eventually all schedule will be sent, it will 
take time but neighbours might learn all information from others 
"eventually".

As Kris said, however, we need to find how useful that will be and what 
are the cases where this will work better than just simple random 
selection and monitoring, assuming our schedules are sparse. If this is 
an optional feature seems that all cases can be covered.

regards,
Xavi

Al 19/06/13 06:48, En/na [email-masked] ha escrit:
> Please note that for sure in this mechanism we will have more 
> communication overhead. The point is address the requirements of those 
> applications that might require very dense schedule.
>
> Regarding to your comment about the redundant information, node A does 
> not use this information just for negotiation with node B to create a 
> soft link. Node A might need to create a soft link with other 
> neighbors (e.g. C, D, or E), then node A will use that information to 
> create a soft link with them as well.
>
> I think Kris provide a complete explanation, that why random approach 
> will be satisfactory for most of the applications with regular 
> requirements.
>
> Best Wishes,
>
> Pouria
>
> *From:*Maria Rita PALATTELLA [mailto:[email-masked]]
> *Sent:* Wednesday, June 19, 2013 3:24 PM
> *To:* Zand, P. (EWI); [email-masked]; [email-masked]
> *Subject:* RE: [6tsch] TSCH: info for each(?) link in Enhanced Beacon 
> frames
>
> Dear Pouria, all,
>
> I am afraid the "cell usage information"  exchange can generate a lot 
> of overhead. For instance, one thing that comes in my mind is the 
> generation of redundant information. If you look at  Fig. (b) and (c), 
> you can notice that most of node A's  2-hop neighbors are also node 
> B's two-hop neighbors (the two-hop ranges mainly overlap).Then, I 
> wonder why we should transmit the same information twice?
> For sure, node A will not suggest in its *Link Reservation Request* to 
> node B a cell that is used by their common neighbors. Do you agree 
> with me? Or am I missing something?
>
> Moreover I am not in favor of the random approach (1) you are 
> suggesting. Acting in a very blind way, will give extra-work to the 
> monitoring process, and then to the re-scheduling procedure.
> *From:[email-masked] [mailto:[email-masked]] *On 
> Behalf Of [email-masked]
> *Sent:* Wednesday, June 19, 2013 3:18 PM
> *To:* [email-masked]
> *Cc:* [email-masked]; [email-masked]
> frames
> For sure exchanging just changes might not be a good solution. In 
> addition, the existing node might lose some information about the 
> changes, due to the possible interference and packet drops.
>
>  1. *Active approach (Request-response mechanism)*: The combination of
>     requesting the changes and all cell usages might work. For
>     instance, we might consider the *request-response* mechanism for
>     the new node, to get all cell usages from its neighbors, upon
>     joining. Then the new node might be able to periodically use the
>     *same* mechanism to ask about the changes in the neighbors' cell
>     usage.
>  2. *Passive approach (Broadcasting mechanism)*: We might be able to
>     segment those information into several segments and consider index
>     for each segment. We might need to broadcast several messages to
>     report all cell usage. Each node periodically broadcasts those
>     information.
>  3. *Hybrid approach (Request-response and broadcasting mechanism):
>     *Each node**broadcast the changes that are identified by the
>     sequence number periodically. The new node that joins the network
>     (or old device who has not received the changes from its neighbor
>     for a while or missed some segments), might use the
>     *request-respons*e mechanism for asking the all cell usages.
>
> Am I right?
>
> Pouria
>
> *From:*Qin Wang [mailto:[email-masked]]
> *Sent:* Wednesday, June 19, 2013 2:14 PM
> *To:* Zand, P. (EWI)
> *Cc:* [email-masked] <mailto:[email-masked]>; 
> frames
> Just one comment on "exchanging the *changes* in a node's cell usages 
> I think one of motivations to use decentralized reservation is dealing 
> with mobility. That means nodes are joining and leaving relatively 
> frequently. So, exchanging the *changes* may not give the moving node 
> the picture of cell usage around it,
>
> Thought?
>
> Qin
>
> that "Bitmaps of occupied cells" can be sent in possible other ways 
> and there is no "requirement" to just include those information in EB. 
> As you mentioned, we can make it optional for some applications and/or 
> use another mechanisms (e.g. request-response) to get those 
> information from the neighbors. For those possible applications that 
> might need very dense schedules (more than one link per slot) in 
> two-hop neighborhood, we might be able to decrease the probability of 
> cell re-allocation at the cost of increasing the network overhead 
> (caused by exchanging occupied cells info).
>
> *Qin, Thomas-*
>
> collision-free communication is not achievable, in a distributed manner.
>
> I attached a *Figure* to illustrate the concept more clearly for 
> others as well. In summary, in order to choose a /soft link/ on edge 
> (A, B) (as is shown in Figure (a)), the "cell usage information" might 
> be helpful during the /soft link/ negotiation. Those information (i) 
> enables node A to propose a set of unused cells in his neighborhood 
> (as is shown in Figure (b)) as candidate cells in the*Link Reservation 
> Request* , and (ii) enables node B to pick up a cell that is not used 
> either in his neighborhood (as is shown in Figure (c)) and then reply 
> by *Link Reservation Response*.
>
> For sure this method might have some costs (e.g. increasing the 
> management overhead) and might not be suitable for those applications 
> that doesn't have every dense schedule. But it might be affordable for 
> those applications that require dense schedules, at the cost of more 
> management overhead.
>
> *3. the combination of (2) and monitoring process*.
>
> As Thomas mentioned, there could be a different boundaries in which 
> using methods (1), (2) or (3) would be considerable. As Kris and 
> Thomas suggest, I think evaluating different scenarios (i.e. regular 
> schedule and dense schedule) can be useful to clarify those 
> boundaries. To measure the network goodput and management overhead in 
> those approaches.
>
> *Xavi-*
>
> I agree with you that having multiple slotFrames with different 
> length, make it difficult to use bitmap in the very dense schedule. In 
> this case, we might look for a better way. For instance, considering 
> the request-response mechanism and/or exchanging the *changes* in a 
> node's cell usages bitmap instead of reporting all cell usage bitmap 
> periodically.
>
> monitoring process will be useful.
>
> Best Wishes,
>
> Pouria
>
> *From:[email-masked] <mailto:[email-masked]> 
> [mailto:[email-masked] <mailto:[email-masked]>] *On 
> Behalf Of *Kris Pister
> *To:* [email-masked] <mailto:[email-masked]>
> frames
> networks this way, and in fact we'll have some advantages over 
> centrally managed networks - speed and mobility for sure, I'm not 
> convinced about scalability.
>
> Bitmaps of occupied TX and RX cells in Information Elements seems like 
> a good idea to me - maybe there are better ways to do it.  The one 
> thing that I would ask is that you not make it a *requirement* that 
> these IEs be in EBs.  I have no problem if you want to make it 
> optional, for those networks that want to use it, or even mandatory as 
> a response to a request.  But please let's not burden every EB with 
> that information.
>
> you can do with just random choice, with some feedback on bad links.  
> If we look at randomly assigned links in a superframe with L_max cells 
> (=S slots * C channels), and consider the collision domain to be the 
> union of the neighbors of mote A and mote B (conservative, but the 
> bound is achieved occasionally in practice), then the probability that 
> a cell is unoccupied is
> P0 = e^-GL where
> GL = L_a / L_max where
> then GL=1/15, and P0=0.94.  So randomly selected links are usually 
> going to work.  Having an average of one link assigned per slot in a 
> given two mote neighborhood is really high, at least for any network 
> that I've ever built or sold.  Sometimes we approach this at the DAG 
> root.  This is not to say that transmitting neighbor tables is not a 
> good thing, just that you can build a lot of applications with very 
> simple (random) cell allocation.  So sending the neighbor tables is 
> not necessary for many/most networks, but would be a nice option to 
> have for future optimizations.
>
> ksjp
>
> will they?  With a mix of non-colliding and potentially colliding 
> links at each mote, what is the network goodput?  I'm sure that 
> someone has written a paper on this for MPLS or something, but I've 
> never seen one.
>
> On 6/10/2013 3:09 AM, [email-masked] <mailto:[email-masked]> wrote:
>
>     Dear All,
>

---

From: Kris Pister <[email-masked]>
Date: Wed, 19 Jun 2013 11:13:46 -0700

Isn't some form of trickle the right way to do this?  Maybe some issues 
with distribution over a two-hop neighborhood?

ksjp

On 6/19/2013 11:00 AM, Xavier Vilajosana wrote:
> neighbours and make sure it is installed there, usually this is done 
> in master-slave architectures where the master tells the slaves what 
> to do and won't fit to our scenario (this is the PCE case in fact)
>
> can have scheduling problems in case 2 nodes do not have their 
> schedule completely synchronized, however monitoring can help to 
> detect that and correct eventually. My opinion is that the schedule 
> does not change so much so having optimistic approaches would work 
> well (in terms of scalability). To achieve that, nodes might send 
> portions of their schedule, assuming that eventually all schedule will 
> be sent, it will take time but neighbours might learn all information 
> from others "eventually".
>
> As Kris said, however, we need to find how useful that will be and 
> what are the cases where this will work better than just simple random 
> selection and monitoring, assuming our schedules are sparse. If this 
> is an optional feature seems that all cases can be covered.
>
> regards,
> Xavi
>
>
>
>
>> communication overhead. The point is address the requirements of 
>> those applications that might require very dense schedule.
>>
>> Regarding to your comment about the redundant information, node A 
>> does not use this information just for negotiation with node B to 
>> create a soft link. Node A might need to create a soft link with 
>> other neighbors (e.g. C, D, or E), then node A will use that 
>> information to create a soft link with them as well.
>>
>> generation of redundant information. If you look at  Fig. (b) and 
>> (c), you can notice that most of node A's  2-hop neighbors are also 
>> node B's two-hop neighbors (the two-hop ranges mainly overlap).Then, 
>> I wonder why we should transmit the same information twice?
>> For sure, node A will not suggest in its *Link Reservation Request* 
>> to node B a cell that is used by their common neighbors. Do you agree 
>>  1. *Active approach (Request-response mechanism)*: The combination
>>     of requesting the changes and all cell usages might work. For
>>     segment those information into several segments and consider
>>     index for each segment. We might need to broadcast several
>>     messages to report all cell usage. Each node periodically
>>     broadcasts those information.
>> I think one of motivations to use decentralized reservation is 
>> dealing with mobility. That means nodes are joining and leaving 
>> relatively frequently. So, exchanging the *changes* may not give the 
>> moving node the picture of cell usage around it,
>>
>> Thought?
>>
>> Qin
>>
>> Many thanks for your complete explanation. I completely agree with 
>> you that "Bitmaps of occupied cells" can be sent in possible other 
>> ways and there is no "requirement" to just include those information 
>> in EB. As you mentioned, we can make it optional for some 
>> applications and/or use another mechanisms (e.g. request-response) to 
>> get those information from the neighbors. For those possible 
>> applications that might need very dense schedules (more than one link 
>> per slot) in two-hop neighborhood, we might be able to decrease the 
>> probability of cell re-allocation at the cost of increasing the 
>> network overhead (caused by exchanging occupied cells info).
>>
>> *Qin, Thomas-*
>>
>> (A, B) (as is shown in Figure (a)), the "cell usage information" 
>> might be helpful during the /soft link/ negotiation. Those 
>> information (i) enables node A to propose a set of unused cells in 
>> his neighborhood (as is shown in Figure (b)) as candidate cells in 
>> the*Link Reservation Request* , and (ii) enables node B to pick up a 
>> cell that is not used either in his neighborhood (as is shown in 
>> Figure (c)) and then reply by *Link Reservation Response*.
>>
>> that doesn't have every dense schedule. But it might be affordable 
>> for those applications that require dense schedules, at the cost of 
>> more management overhead.
>>
>> length, make it difficult to use bitmap in the very dense schedule. 
>> In this case, we might look for a better way. For instance, 
>> considering the request-response mechanism and/or exchanging the 
>> *changes* in a node's cell usages bitmap instead of reporting all 
>> cell usage bitmap periodically.
>>
>> In this figure I assumed that the Tx range and interference ranges 
>> are equal. In the realistic setting that those ranges are not equal, 
>> the monitoring process will be useful.
>>
>> Best Wishes,
>>
>> Pouria
>>
>> first started talking about working in the IETF to standardize the 
>> gap between 6lowpan and 15.4e I thought that surely all of those IP 
>> Bitmaps of occupied TX and RX cells in Information Elements seems 
>> like a good idea to me - maybe there are better ways to do it.  The 
>> one thing that I would ask is that you not make it a *requirement* 
>> that these IEs be in EBs.  I have no problem if you want to make it 
>> optional, for those networks that want to use it, or even mandatory 
>> as a response to a request.  But please let's not burden every EB 
>> with that information.
>>
>> you to optimize link schedules.  I'm curious to know, though, how 
>> well you can do with just random choice, with some feedback on bad 
>> links.  If we look at randomly assigned links in a superframe with 
>> L_max cells (=S slots * C channels), and consider the collision 
>> domain to be the union of the neighbors of mote A and mote B 
>> (conservative, but the bound is achieved occasionally in practice), 
>> then the probability that a cell is unoccupied is
>> P0 = e^-GL where
>> GL = L_a / L_max where
>> piece of the network has scheduled on average something in every 
>> slot, then GL=1/15, and P0=0.94.  So randomly selected links are 
>> usually going to work. Having an average of one link assigned per 
>> slot in a given two mote neighborhood is really high, at least for 
>> any network that I've ever built or sold.  Sometimes we approach this 
>> at the DAG root.  This is not to say that transmitting neighbor 
>> tables is not a good thing, just that you can build a lot of 
>> applications with very simple (random) cell allocation.  So sending 
>> the neighbor tables is not necessary for many/most networks, but 
>> p.s. an interesting question arises about the goodput of a random 
>> link assignment approach. Many of the links will be non-colliding.  
>> Those that do collide will exhibit slotted aloha collision 
>> statistics...or will they?  With a mix of non-colliding and 
>> potentially colliding links at each mote, what is the network 
>> goodput?  I'm sure that someone has written a paper on this for MPLS 
>> or something, but I've never seen one.
>>
>>     this discussion about the maximum number of links' information
>>     (or "link object") that can be included in EB? Can we think about
>>     CellBitMap to enable us to include the entire reserved
>>     links/cells by each node in the one or several EB(s)?
>>
>>     **
>>
>>     *Our motivation*:
>>
>>     used to not repeat the reserved cells in our two-hop
>>     neighborhood. In addition, the collision caused by a pair of
>>     nodes who are using the same cell in outside of two-hop
>>     neighborhood can be detected, by monitoring the status of that
>>     reserved cell (By considering the mechanisms discussed in "2.8
>>     Monitoring" section in draft-wang-6tsch-6tus-00).
>>
>>     Best wishes,
>>
>>     Pouria Zand
>>

---

From: Philip Levis <[email-masked]>
Date: Wed, 19 Jun 2013 12:30:48 -0700

Yes -- as far as I know, there isn't a better (faster, more efficient) algorithm than RFC6206 for reaching eventual consistency in a wireless network. P2P is not a good place to start because it is based on a graph abstraction with neighbor sets. etc. I can look closer at the exact problem problem you're discussing to figure out whether I think Trickle would work well, if you like.

Phil

On Jun 19, 2013, at 11:13 AM, Kris Pister wrote:

> Isn't some form of trickle the right way to do this?  Maybe some issues with distribution over a two-hop neighborhood?
> 
> ksjp
> 
>> This problem is not new, in P2P communities I've seen many different approaches to deal with keeping a distributed state (consistency). I think there are 2 main directions, pessimistic and optimistic, pessimistic approaches aim to enforce all nodes with the same information which requires transmitting the exact state to the neighbours and make sure it is installed there, usually this is done in master-slave architectures where the master tells the slaves what to do and won't fit to our scenario (this is the PCE case in fact)
>> 
>> A more scalable approach is to tolerate a little bit of de-synchronization (optimistic consistency) and think that eventually all nodes will learn about the scheduling state. With that approach we can have scheduling problems in case 2 nodes do not have their schedule completely synchronized, however monitoring can help to detect that and correct eventually. My opinion is that the schedule does not change so much so having optimistic approaches would work well (in terms of scalability). To achieve that, nodes might send portions of their schedule, assuming that eventually all schedule will be sent, it will take time but neighbours might learn all information from others "eventually". 
>> 
>> As Kris said, however, we need to find how useful that will be and what are the cases where this will work better than just simple random selection and monitoring, assuming our schedules are sparse. If this is an optional feature seems that all cases can be covered.

---

From: Thomas Watteyne <[email-masked]>
Date: Wed, 19 Jun 2013 23:18:10 -0700

+1 on the use of Trickle. It would indeed be great if you could look at the
applicability.

Per http://tools.ietf.org/html/rfc6206#section-5, we need to identify what
Trickle considers consistent, inconsistent, and what other events can cause
a Trickle timer reset.

A first step might be to identify what we believe is a fully consistent
network. I see multiple, slightly different, definitions:
1. when all nodes know the full TSCH schedule of all their (2-hop?)
neighbors
2. when there are no MAC-layer collisions, i.e. no communication happens on
the same slotoffset/channeloffset within that neighborhood

Of course, condition 1 is sufficient for condition 2 to be satisfied. I
would argue that, since condition 2 is the end goal of the network,
satisfying condition 2 might be enough. That is, it's OK if you don't know
the complete schedule of your neighbors, as long as you can communicate
without collision. It is in fact possible that two cells are reused between
two pairs of nodes, if at least one of these pairs never uses that cell, no
Trickle reset is needed.

Thomas

On Wed, Jun 19, 2013 at 12:30 PM, Philip Levis <[email-masked]> wrote:

> Yes -- as far as I know, there isn't a better (faster, more efficient)
> algorithm than RFC6206 for reaching eventual consistency in a wireless
> network. P2P is not a good place to start because it is based on a graph
> abstraction with neighbor sets. etc. I can look closer at the exact problem
> problem you're discussing to figure out whether I think Trickle would work
> well, if you like.
>
> Phil
>
> approaches to deal with keeping a distributed state (consistency). I think
> there are 2 main directions, pessimistic and optimistic, pessimistic
> approaches aim to enforce all nodes with the same information which
> requires transmitting the exact state to the neighbours and make sure it is
> installed there, usually this is done in master-slave architectures where
> the master tells the slaves what to do and won't fit to our scenario (this
> is the PCE case in fact)
> >>
> de-synchronization (optimistic consistency) and think that eventually all
> nodes will learn about the scheduling state. With that approach we can have
> scheduling problems in case 2 nodes do not have their schedule completely
> synchronized, however monitoring can help to detect that and correct
> eventually. My opinion is that the schedule does not change so much so
> having optimistic approaches would work well (in terms of scalability). To
> achieve that, nodes might send portions of their schedule, assuming that
> eventually all schedule will be sent, it will take time but neighbours
> might learn all information from others "eventually".
> >>
> are the cases where this will work better than just simple random selection
> and monitoring, assuming our schedules are sparse. If this is an optional
> feature seems that all cases can be covered.
>
>
>

---

From: <[email-masked]>
Date: Thu, 20 Jun 2013 07:53:54 +0000

Hi Thomas,

Just one minor comment on "1. when all nodes know the full TSCH schedule of all their (2-hop?) neighbors".
Shall we say 1-hop neighbors? I think, one node by collecting the schedule of all its one-hop neighbors can know the schedule of its two-hop neighborhood that might conflict with its communication. In the received schedule information from one hop neighbor, the links between the one-hop and two-hop neighbors are also included. Am I right?

Best Wishes,
Pouria

From: [email-masked] [mailto:[email-masked]] On Behalf Of Thomas Watteyne
Sent: Thursday, June 20, 2013 8:18 AM
To: Philip Levis
Cc: 6TSCH; Kris Pister
Subject: Re: [6tsch] TSCH: info for each(?) link in Enhanced Beacon frames

+1 on the use of Trickle. It would indeed be great if you could look at the applicability.

Per http://tools.ietf.org/html/rfc6206#section-5, we need to identify what Trickle considers consistent, inconsistent, and what other events can cause a Trickle timer reset.

A first step might be to identify what we believe is a fully consistent network. I see multiple, slightly different, definitions:
1. when all nodes know the full TSCH schedule of all their (2-hop?) neighbors
2. when there are no MAC-layer collisions, i.e. no communication happens on the same slotoffset/channeloffset within that neighborhood

Of course, condition 1 is sufficient for condition 2 to be satisfied. I would argue that, since condition 2 is the end goal of the network, satisfying condition 2 might be enough. That is, it's OK if you don't know the complete schedule of your neighbors, as long as you can communicate without collision. It is in fact possible that two cells are reused between two pairs of nodes, if at least one of these pairs never uses that cell, no Trickle reset is needed.

Thomas

On Wed, Jun 19, 2013 at 12:30 PM, Philip Levis <[email-masked]<mailto:[email-masked]>> wrote:
Yes -- as far as I know, there isn't a better (faster, more efficient) algorithm than RFC6206 for reaching eventual consistency in a wireless network. P2P is not a good place to start because it is based on a graph abstraction with neighbor sets. etc. I can look closer at the exact problem problem you're discussing to figure out whether I think Trickle would work well, if you like.

Phil

---

From: Maria Rita PALATTELLA <[email-masked]>
Date: Thu, 20 Jun 2013 07:57:39 +0000

Pouria, I do agree with you.
1-hop also include the 2- hop information. The RX cells for the 1-hop neighbor, are the TX cells for the 2-hop neighbor.

Maria Rita

From: [email-masked] [mailto:[email-masked]] On Behalf Of [email-masked]
Sent: Thursday, June 20, 2013 9:54 AM
To: [email-masked]; [email-masked]
Cc: [email-masked]; [email-masked]
Subject: Re: [6tsch] TSCH: info for each(?) link in Enhanced Beacon frames

Hi Thomas,

Best Wishes,
Pouria

From: [email-masked]<mailto:[email-masked]> [mailto:[email-masked]] On Behalf Of Thomas Watteyne
Sent: Thursday, June 20, 2013 8:18 AM
To: Philip Levis
Cc: 6TSCH; Kris Pister
Subject: Re: [6tsch] TSCH: info for each(?) link in Enhanced Beacon frames

Thomas

Phil

---

From: Thomas Watteyne <[email-masked]>
Date: Thu, 20 Jun 2013 01:31:30 -0700

Absolutely!
Thomas

On Thu, Jun 20, 2013 at 12:57 AM, Maria Rita PALATTELLA <
[email-masked]> wrote:

>  Pouria, I do agree with you.****
>
> 1-hop also include the 2- hop information. The RX cells for the 1-hop
> neighbor, are the TX cells for the 2-hop neighbor.****
>
> ** **
>
> Maria Rita****
>
> ** **
>
> Of [email-masked]
> *Sent:* Thursday, June 20, 2013 9:54 AM
> *To:* [email-masked]; [email-masked]
> Hi Thomas,****
> Just one minor comment on “1. when all nodes know the full TSCH schedule
> of all their (2-hop?) neighbors”.****
>
> Shall we say 1-hop neighbors? I think, one node by collecting the schedule
> of all its one-hop neighbors can know the schedule of its two-hop
> neighborhood that might conflict with its communication. In the received
> schedule information from one hop neighbor, the links between the one-hop
> and two-hop neighbors are also included. Am I right?  ****
>
> ** **
>
> Best Wishes,****
>
> Pouria  ****
>
> ** **
>
> *From:* [email-masked] [mailto:[email-masked]<[email-masked]>]
> *On Behalf Of *Thomas Watteyne
> *Sent:* Thursday, June 20, 2013 8:18 AM
> *To:* Philip Levis
> *Cc:* 6TSCH; Kris Pister
> +1 on the use of Trickle. It would indeed be great if you could look at
> the applicability.****
>
> ** **
>
> Per http://tools.ietf.org/html/rfc6206#section-5, we need to identify
> what Trickle considers consistent, inconsistent, and what other events can
> cause a Trickle timer reset.****
>
> ** **
>
> network. I see multiple, slightly different, definitions:****
>
> neighbors****
> 2. when there are no MAC-layer collisions, i.e. no communication happens
> on the same slotoffset/channeloffset within that neighborhood****
>
> ** **
>
> Trickle reset is needed.****
>
> ** **
>
> Thomas****
>
> ** **
>
> ** **
>
> On Wed, Jun 19, 2013 at 12:30 PM, Philip Levis <[email-masked]>
> wrote:****
>
> Phil****

---

From: Qin Wang <[email-masked]>
Date: Thu, 20 Jun 2013 20:11:04 +0800

Hi Pouria and Maria Rita,

I think there is a difference between just 1-hop information and 2-hop
information. For example,

Assume nodeA Tx to nodeB @ cell-1, and nodeC is in the radio range of
nodeA. nodeD is a neighbor of nodeC, but not a neighbor of nodeB.

Then, from the schedule of nodeC (i.e. the RX cells of nodeC), nodeD cannot
know nodeA is its 2-hop neighbor.

Thought?
Qin

---

From: <[email-masked]>
Date: Thu, 20 Jun 2013 12:59:31 +0000

Hi Qin,
You mean the case that edge(A, B) is not in the two-hop neighborhood of node D, but is in the two-hop neighborhood of node C. Am I right?
If yes, for creating a soft link between node D and C, node D will send a "Link Reservation Request" including a candidate set of links based on its two-hop information. Node D might suggest the cell-1 that is used on edge (A, B). However, node C upon receiving the request, will do another check based on his two-hop neighborhood information and will not chose that cell-1. That is because node C knows about the cell-1 on edge(A, B) in its two-hop neighborhood.
In other cases, that node D intend to create a soft link with other nodes (e.g. E or F), and if those nodes are not one-hop neighbors of node A, then edge(A,B) is not considered as a conflict edge with edges of (D, E) or (D, F).
Am I right?
Best wishes,
Pouria

From: Qin Wang [mailto:[email-masked]]
Sent: Thursday, June 20, 2013 2:11 PM
To: Maria Rita PALATTELLA
Cc: Zand, P. (EWI); [email-masked]; [email-masked]; [email-masked]; [email-masked]
Subject: Re: [6tsch] TSCH: info for each(?) link in Enhanced Beacon frames

I think there is a difference between just 1-hop information and 2-hop information. For example,

Assume nodeA Tx to nodeB @ cell-1, and nodeC is in the radio range of nodeA. nodeD is a neighbor of nodeC, but not a neighbor of nodeB.

Then, from the schedule of nodeC (i.e. the RX cells of nodeC), nodeD cannot know nodeA is its 2-hop neighbor.

Thought?
Qin

On Thu, Jun 20, 2013 at 3:57 PM, Maria Rita PALATTELLA <[email-masked]<mailto:[email-masked]>> wrote:
Pouria, I do agree with you.
1-hop also include the 2- hop information. The RX cells for the 1-hop neighbor, are the TX cells for the 2-hop neighbor.

Maria Rita

From: [email-masked]<mailto:[email-masked]> [mailto:[email-masked]<mailto:[email-masked]>] On Behalf Of [email-masked]<mailto:[email-masked]>
Sent: Thursday, June 20, 2013 9:54 AM
To: [email-masked]<mailto:[email-masked]>; [email-masked]<mailto:[email-masked]>
Cc: [email-masked]<mailto:[email-masked]>; [email-masked]<mailto:[email-masked]>

Hi Thomas,

Best Wishes,
Pouria

Thomas

Phil

---

From: "Alfredo Grieco" <[email-masked]>
Date: Thu, 20 Jun 2013 14:59:44 +0200

Dear all, 
 
This discussion let emerge many interesting points.
 
Perhaps, it is time to start thinking (at least optionally) to something in
the middle between a fully deterministic approach where all data packets are
transmitted according to a pre-assigned schedule along the path towards the
root and a fully distributed one, where collision may happen at each hop.
 
Based on the considerations of Kris on the efficiency of slotted aloha, we
just require to build schedules on those links with a very low rank (let's
say r0), which are closer to the root and have to sustain a higher load,
while using slotted aloha for links closer to the leaves of the tree.   
 
This just requires some timeslots between the boundaries of these two
regions (let's say below rank r0 and above r0) of the network to accommodate
some extra delay from packets coming from the leaves. At the same time this
approach would dramatically lower the complexity of all the operations
required for building and maintaining the schedule and decrease the
signaling overhead. The value of r0 has to be tuned based on the intensity
of the traffic.
 
Any thoughts ?
 
Cheers
 
Alfredo
 
Da: [email-masked] [mailto:[email-masked]] Per conto di Qin
Wang
Inviato: Thursday, June 20, 2013 2:11 PM
A: Maria Rita PALATTELLA
Cc: [email-masked]; [email-masked]; [email-masked];
[email-masked]; [email-masked]
Oggetto: Re: [6tsch] TSCH: info for each(?) link in Enhanced Beacon frames

 
Assume nodeA Tx to nodeB @ cell-1, and nodeC is in the radio range of nodeA.
nodeD is a neighbor of nodeC, but not a neighbor of nodeB.

Thought?
Qin

 
On Thu, Jun 20, 2013 at 3:57 PM, Maria Rita PALATTELLA
<[email-masked]> wrote:
Pouria, I do agree with you.
1-hop also include the 2- hop information. The RX cells for the 1-hop
neighbor, are the TX cells for the 2-hop neighbor.
 
Maria Rita
 
From: [email-masked] [mailto:[email-masked]] On Behalf Of
[email-masked]
Sent: Thursday, June 20, 2013 9:54 AM
To: [email-masked]; [email-masked]
Cc: [email-masked]; [email-masked]

Hi Thomas,
 
Just one minor comment on "1. when all nodes know the full TSCH schedule of
all their (2-hop?) neighbors".
Shall we say 1-hop neighbors? I think, one node by collecting the schedule
of all its one-hop neighbors can know the schedule of its two-hop
neighborhood that might conflict with its communication. In the received
schedule information from one hop neighbor, the links between the one-hop
and two-hop neighbors are also included. Am I right?  
 
Best Wishes,
Pouria  
 
From: [email-masked] [mailto:[email-masked]] On Behalf Of
Thomas Watteyne
Sent: Thursday, June 20, 2013 8:18 AM
To: Philip Levis
Cc: 6TSCH; Kris Pister
Subject: Re: [6tsch] TSCH: info for each(?) link in Enhanced Beacon frames

 

Thomas

Phil

approaches to deal with keeping a distributed state (consistency). I think
there are 2 main directions, pessimistic and optimistic, pessimistic
approaches aim to enforce all nodes with the same information which requires
transmitting the exact state to the neighbours and make sure it is installed
there, usually this is done in master-slave architectures where the master
tells the slaves what to do and won't fit to our scenario (this is the PCE
case in fact)
de-synchronization (optimistic consistency) and think that eventually all
nodes will learn about the scheduling state. With that approach we can have
scheduling problems in case 2 nodes do not have their schedule completely
synchronized, however monitoring can help to detect that and correct
eventually. My opinion is that the schedule does not change so much so
having optimistic approaches would work well (in terms of scalability). To
achieve that, nodes might send portions of their schedule, assuming that
eventually all schedule will be sent, it will take time but neighbours might
learn all information from others "eventually".

---

From: Qin Wang <[email-masked]>
Date: Thu, 20 Jun 2013 21:16:34 +0800

Pouria,

Your understanding on the topology is correct.

As you described above, when nodeC selects a cell from the candidate set
from nodeD, nodeC has to use the knowledge that edge(A,B) is in its 2-hop
neighborhood, instead of just using the local schedule in nodeC. That means
the complete knowledge in a node should include the 2-hop information.
Correct?

Qin

On Thu, Jun 20, 2013 at 8:59 PM, <[email-masked]> wrote:

>  Hi Qin,****
>
> You mean the case that edge(A, B) is not in the two-hop neighborhood of
> node D, but is in the two-hop neighborhood of node C. Am I right?****
>
> If yes, for creating a soft link between node D and C, node D will send a
> “Link Reservation Request” including a candidate set of links based on its
> two-hop information. Node D might suggest the cell-1 that is used on edge
> (A, B). However, node C upon receiving the request, will do another check
> based on his two-hop neighborhood information and will not chose that
> cell-1. That is because node C knows about the cell-1 on edge(A, B) in its
> two-hop neighborhood.****
>
> In other cases, that node D intend to create a soft link with other nodes
> (e.g. E or F), and if those nodes are not one-hop neighbors of node A, then
> edge(A,B) is not considered as a conflict edge with edges of (D, E) or (D,
> F).****
>
> Am I right?  ****
>
> Best wishes,****
>
> Pouria****
>
> ** **
>
> *From:* Qin Wang [mailto:[email-masked]]
> *Sent:* Thursday, June 20, 2013 2:11 PM
> *To:* Maria Rita PALATTELLA
> *Cc:* Zand, P. (EWI); [email-masked]; [email-masked];
> [email-masked]; [email-masked]
>
> Hi Pouria and Maria Rita,****
>
> ** **
>
> information. For example, ****
>
> ** **
>
> nodeA. nodeD is a neighbor of nodeC, but not a neighbor of nodeB.****
>
> ** **
>
> Then, from the schedule of nodeC (i.e. the RX cells of nodeC), nodeD
> cannot know nodeA is its 2-hop neighbor.****
>
> ** **
>
> Thought?****
>
> Qin****
>
>  ****
>
> ** **
>
>   ****
>
> ** **
>
> ** **
>
> ** **
>
> [email-masked]> wrote:****
>
> *Cc:* [email-masked]; [email-masked]****
>
>
> feature seems that all cases can be covered.****
>

---

From: Maria Rita PALATTELLA <[email-masked]>
Date: Thu, 20 Jun 2013 13:16:41 +0000

Qin, it is exactly as Pouria explained.
Generally speaking, the idea is to propagate the information hop-by-hop among some of the neighbor nodes. Each node doesn't need to have a full picture of the network. The combination of the partial information that each node has, will allow them to properly select the soft cells within the TSCH schedule. In the worst scenario, if the cells allocation isn't properly done, the monitoring algorithm will help in detecting that.
Maria Rita

________________________________
From: [email-masked] [[email-masked]]
Sent: Thursday, June 20, 2013 2:59 PM
To: [email-masked]; Maria Rita PALATTELLA
Cc: [email-masked]; [email-masked]; [email-masked]; [email-masked]
Subject: RE: [6tsch] TSCH: info for each(?) link in Enhanced Beacon frames

Hi Qin,
You mean the case that edge(A, B) is not in the two-hop neighborhood of node D, but is in the two-hop neighborhood of node C. Am I right?
If yes, for creating a soft link between node D and C, node D will send a “Link Reservation Request” including a candidate set of links based on its two-hop information. Node D might suggest the cell-1 that is used on edge (A, B). However, node C upon receiving the request, will do another check based on his two-hop neighborhood information and will not chose that cell-1. That is because node C knows about the cell-1 on edge(A, B) in its two-hop neighborhood.
In other cases, that node D intend to create a soft link with other nodes (e.g. E or F), and if those nodes are not one-hop neighbors of node A, then edge(A,B) is not considered as a conflict edge with edges of (D, E) or (D, F).
Am I right?
Best wishes,
Pouria

Thought?
Qin

Maria Rita

Hi Thomas,

Just one minor comment on “1. when all nodes know the full TSCH schedule of all their (2-hop?) neighbors”.
Shall we say 1-hop neighbors? I think, one node by collecting the schedule of all its one-hop neighbors can know the schedule of its two-hop neighborhood that might conflict with its communication. In the received schedule information from one hop neighbor, the links between the one-hop and two-hop neighbors are also included. Am I right?

Best Wishes,
Pouria

Thomas

Phil

---

From: Qin Wang <[email-masked]>
Date: Thu, 20 Jun 2013 21:26:02 +0800

Maria Rita,

I fully agree with what you said. There is trade-off, i.e. how much
information a node should hold, (None, 1-hop, 2-hop), and then monitoring
will take care of rest. Should it be configurable?

Qin

On Thu, Jun 20, 2013 at 9:16 PM, Maria Rita PALATTELLA <
[email-masked]> wrote:

> Generally speaking, the idea is to propagate the information hop-by-hop
> among some of the neighbor nodes. Each node doesn't need to have a full
> picture of the network. The combination of the partial information that
> each node has, will allow them to properly select the soft cells within the
> TSCH schedule. In the worst scenario, if the cells allocation isn't
> properly done, the monitoring algorithm will help in detecting that.
> Maria Rita
>
>  ------------------------------
> *From:* [email-masked] [[email-masked]]
> *Sent:* Thursday, June 20, 2013 2:59 PM
> *To:* [email-masked]; Maria Rita PALATTELLA
> *Cc:* [email-masked]; [email-masked]; [email-masked];
> [email-masked]
> node D, but is in the two-hop neighborhood of node C. Am I right?
>
> two-hop neighborhood.
> F).
> cannot know nodeA is its 2-hop neighbor.
>
>
>
> Thought?
>
> Qin
>
>
>
>
>
>
>
>
>
>
>
>
>
> of all their (2-hop?) neighbors”.
>
> the applicability.
> cause a Trickle timer reset.
>
>
>
> on the same slotoffset/channeloffset within that neighborhood
>
>
>
> wrote:

---

From: <[email-masked]>
Date: Thu, 20 Jun 2013 14:03:06 +0000

Qin,
May be we can talk on this figure,
Each node can get this 2-hop neighborhood information by collecting the cell-usage of its 1-hop neighbors. Then during the negotiation for a soft link on an edge (e.g. edge (A, B)), the combination of node A and node B's 2-hop neighborhood information, create a virtual 2-hop neighborhood information around that edge.
Would you please explain what does 1-hop information include?

Best Wishes,
Pouria

Sent: Thursday, June 20, 2013 3:26 PM

Maria Rita,

I fully agree with what you said. There is trade-off, i.e. how much information a node should hold, (None, 1-hop, 2-hop), and then monitoring will take care of rest. Should it be configurable?

Qin

On Thu, Jun 20, 2013 at 9:16 PM, Maria Rita PALATTELLA <[email-masked]<mailto:[email-masked]>> wrote:
Qin, it is exactly as Pouria explained.
Generally speaking, the idea is to propagate the information hop-by-hop among some of the neighbor nodes. Each node doesn't need to have a full picture of the network. The combination of the partial information that each node has, will allow them to properly select the soft cells within the TSCH schedule. In the worst scenario, if the cells allocation isn't properly done, the monitoring algorithm will help in detecting that.
Maria Rita
________________________________
From: [email-masked]<mailto:[email-masked]> [[email-masked]<mailto:[email-masked]>]
Sent: Thursday, June 20, 2013 2:59 PM
To: [email-masked]<mailto:[email-masked]>; Maria Rita PALATTELLA
Cc: [email-masked]<mailto:[email-masked]>; [email-masked]<mailto:[email-masked]>; [email-masked]<mailto:[email-masked]>; [email-masked]<mailto:[email-masked]>
Subject: RE: [6tsch] TSCH: info for each(?) link in Enhanced Beacon frames
Hi Qin,
You mean the case that edge(A, B) is not in the two-hop neighborhood of node D, but is in the two-hop neighborhood of node C. Am I right?
If yes, for creating a soft link between node D and C, node D will send a "Link Reservation Request" including a candidate set of links based on its two-hop information. Node D might suggest the cell-1 that is used on edge (A, B). However, node C upon receiving the request, will do another check based on his two-hop neighborhood information and will not chose that cell-1. That is because node C knows about the cell-1 on edge(A, B) in its two-hop neighborhood.
In other cases, that node D intend to create a soft link with other nodes (e.g. E or F), and if those nodes are not one-hop neighbors of node A, then edge(A,B) is not considered as a conflict edge with edges of (D, E) or (D, F).
Am I right?
Best wishes,
Pouria

From: Qin Wang [mailto:[email-masked]<mailto:[email-masked]>]
Sent: Thursday, June 20, 2013 2:11 PM
To: Maria Rita PALATTELLA
Cc: Zand, P. (EWI); [email-masked]<mailto:[email-masked]>; [email-masked]<mailto:[email-masked]>; [email-masked]<mailto:[email-masked]>; [email-masked]<mailto:[email-masked]>
Subject: Re: [6tsch] TSCH: info for each(?) link in Enhanced Beacon frames

Thought?
Qin

Maria Rita

Hi Thomas,

Best Wishes,
Pouria

Thomas

Phil

---

From: Qin Wang <[email-masked]>
Date: Thu, 20 Jun 2013 22:47:51 +0800

Pouira,

I think we have same thinking. Let me make it more clear as follows.
(1) Aloha: select a cell not used in local schedule
(2) 1-hop selection:  a cell not used by both Tx node and Rx node
(3) 2-hop selection: a cell not used by both Tx node and Rx node, and their
neighbors.

In case (3), the information needed includes the cell set used by
neighbors. Actually, I don't like case (3). Maybe we can find a solution
between case (2) and case (3), i.e. some part of knowledge about the cell
set used by neighbors, which provide high performance to cost ratio.

Thought?

Qin

On Thu, Jun 20, 2013 at 10:03 PM, <[email-masked]> wrote:

>  Qin,****
>
> May be we can talk on this figure,****
>
> Each node can get this 2-hop neighborhood information by collecting the
> cell-usage of its 1-hop neighbors. Then during the negotiation for a soft
> link on an edge (e.g. edge (A, B)), the combination of node A and node B’s
> 2-hop neighborhood information, create a virtual 2-hop neighborhood
> information around that edge.  ****
>
> Would you please explain what does 1-hop information include?****
>
> ** **
>
> ****
>
> Best Wishes,****
>
> Pouria****
>
> ** **
>
> ** **
>
> *Sent:* Thursday, June 20, 2013 3:26 PM
>
> Maria Rita,****
> will take care of rest. Should it be configurable?****
>
> ** **
>
> Qin****
>
> ** **
>

---

From: Philip Levis <[email-masked]>
Date: Thu, 20 Jun 2013 07:35:16 -0700

On Jun 20, 2013, at 5:59 AM, Alfredo Grieco <[email-masked]> wrote:

> Perhaps, it is time to start thinking (at least optionally) to something in the middle between a fully deterministic approach where all data packets are transmitted according to a pre-assigned schedule along the path towards the root and a fully distributed one, where collision may happen at each hop.
>  
> Based on the considerations of Kris on the efficiency of slotted aloha, we just require to build schedules on those links with a very low rank (let’s say r0), which are closer to the root and have to sustain a higher load, while using slotted aloha for links closer to the leaves of the tree.   
>  
> This just requires some timeslots between the boundaries of these two regions (let’s say below rank r0 and above r0) of the network to accommodate some extra delay from packets coming from the leaves. At the same time this approach would dramatically lower the complexity of all the operations required for building and maintaining the schedule and decrease the signaling overhead. The value of r0 has to be tuned based on the intensity of the traffic.

If you want to explore supporting this approach, I suggest you take a look at

Gahng-Seop Ahn, Emilano Miluzzo, Andrew Campbell, Se Gi Hong, and Francesca Cuomo. "Funneling-MAC: A Localized, Sink Oriented MAC for Boosting Fidelity in Sensor Networks." In Proceedings of the Fourth ACM Conference on Embedded Networked Sensor Systems (SenSys), 2006. 

It does exactly what you describe: by default uses a CSMA/slotted approach but in areas of high contention (close to a root) overlays a strict TDMA schedule. IIRC, there is source code available.

Phil

---

From: Philip Levis <[email-masked]>
Date: Thu, 20 Jun 2013 07:46:57 -0700

> Of course, condition 1 is sufficient for condition 2 to be satisfied. I would argue that, since condition 2 is the end goal of the network, satisfying condition 2 might be enough. That is, it's OK…

The general challenge of disambiguating losses from collisions is such that I'd be wary of 2. One could define an inconsistency as when schedules incorrectly overlap, but that might require too much information. I'd suggest something much simpler. 

Each Trickle message is a set of hashes. Each hash is over the sorted one-hop neighbor set of a node. If a node A has neighbors B and C, it transmits a message with hash(neighbors(A)), hash(neighbors(B)), hash(neighbors(C)). Each hash is computed with a pseudorandom salt value regenerated on each transmission to avoid hash collisions (removing the tradeoff of hash size and collision probability). 

If a node hears a Trickle message in which every hash agrees with the hashes it has (i.e., the hashes of the intersection of those in the message and the neighbor lists the node holds), that is a consistent transmission.

If a node hears a Trickle message in which a hash disagrees, that is an inconsistency event.

When a node changes its neighbor list or changes the neighbor list of one of its neighbors, that is an inconsistency event.

Another approach might be to, rather than using hashes, using version numbers. Then you enter all of the wraparound problems, of course. But otherwise you'll need some mechanism so the authoritative source isn't drowned out by many old copies.

Is this what you're thinking of? I can think a bit more about if if you like.

Phil

---

From: "Alfredo Grieco" <[email-masked]>
Date: Thu, 20 Jun 2013 17:16:45 +0200

Great Phil,

I will try to jointly exploit the approach you mention with our recent
proposal DeTAS described here:

N. Accettura, M. R. Palattella, G. Boggia, L. A. Grieco, and M.
Dohler,"Decentralized Traffic Aware Scheduling for Multi-hop Low Power Lossy
Networks in the Internet of Things", WoWMoM 2013.

Cheers and thanks

Alfredo

-----Messaggio originale-----
Da: Philip Levis [mailto:[email-masked]] 
Inviato: Thursday, June 20, 2013 4:35 PM
A: Alfredo Grieco
Cc: [email-masked]
Oggetto: Re: [6tsch] TSCH: info for each(?) link in Enhanced Beacon frames

On Jun 20, 2013, at 5:59 AM, Alfredo Grieco <[email-masked]>
wrote:

> Perhaps, it is time to start thinking (at least optionally) to something
in the middle between a fully deterministic approach where all data packets
are transmitted according to a pre-assigned schedule along the path towards
the root and a fully distributed one, where collision may happen at each
hop.

If you want to explore supporting this approach, I suggest you take a look
at

Gahng-Seop Ahn, Emilano Miluzzo, Andrew Campbell, Se Gi Hong, and Francesca
Cuomo. "Funneling-MAC: A Localized, Sink Oriented MAC for Boosting Fidelity
in Sensor Networks." In Proceedings of the Fourth ACM Conference on Embedded
Networked Sensor Systems (SenSys), 2006. 

It does exactly what you describe: by default uses a CSMA/slotted approach
but in areas of high contention (close to a root) overlays a strict TDMA
schedule. IIRC, there is source code available.

Phil=

---

From: Thomas Watteyne <[email-masked]>
Date: Thu, 20 Jun 2013 17:13:51 -0700

Alfredo,

What you propose looks like Funneling MAC [1] (2006!). I believe this
corresponds to the hybrid case we identified, where the schedule is managed
by a combination of centralized and distributed solutions. If we decide to
support this (I remember people were a bit reluctant given the complexity),
I would suggest to put the mechanisms in to do that, but let implementation
pick the exact policy.

Thomas

[1] http://dl.acm.org/citation.cfm?id=1182837

On Thu, Jun 20, 2013 at 5:59 AM, Alfredo Grieco <[email-masked]>wrote:

> Dear all, ****
>
> ** **
>
> This discussion let emerge many interesting points.****
>
> ** **
>
> hop.****
> just require to build schedules on those links with a very low rank (let’s
> while using slotted aloha for links closer to the leaves of the tree.   **
> **
>
> ** **
>
> regions (let’s say below rank r0 and above r0) of the network to
> accommodate some extra delay from packets coming from the leaves. At the
> same time this approach would dramatically lower the complexity of all the
> operations required for building and maintaining the schedule and decrease
> the signaling overhead. The value of r0 has to be tuned based on the
> intensity of the traffic.****
>
> ** **
>
> Any thoughts ?****
>
> ** **
>
> Cheers****
>
> ** **
>
> Alfredo****
>
> ** **
>
> *Da:* [email-masked] [mailto:[email-masked]] *Per conto
> di *Qin Wang
> *Inviato:* Thursday, June 20, 2013 2:11 PM
> *A:* Maria Rita PALATTELLA
> *Cc:* [email-masked]; [email-masked]; [email-masked];
> *Oggetto:* Re: [6tsch] TSCH: info for each(?) link in Enhanced Beacon
> frames****
>
> ** **
>

---

From: Thomas Watteyne <[email-masked]>
Date: Thu, 20 Jun 2013 17:26:15 -0700

Phil,

One nice feature of a TSCH network is that a mote can have multiple cells
scheduled to the same neighbor. These cells live at different
slotOffset/channelOffset coordinates in the TSCH schedule (~a matrix), yet,
since channel hopping is enabled, the performance of those cells (e.g. PDR)
is expected to be the same. If you schedule 5 cells between A and B, and 4
of them have a PDR of 80% and 1 a PDR of 30%, something is going on. That
something is most likely collisions. I completely agree with you that
trying disambiguate losses from collisions is a really slippery slope, but
I believe TSCH is an exception.

If I read your proposal well, the state that Trickle maintains consistency
of is the list of neighbors of each node (right?). In a TSCH network.
however, it's very usual to keep the same list of neighbors, but change the
schedule to them, i.e. the list of cells you are scheduled to TX and RX
data with that neighbor. Such a schedule change can either provoke or
prevent collisions, so IMO it should be part of the state Trickle handles.
Does this make sense?

Thomas

On Thu, Jun 20, 2013 at 7:46 AM, Philip Levis <[email-masked]> wrote:

> The general challenge of disambiguating losses from collisions is such
> that I'd be wary of 2. One could define an inconsistency as when schedules
> incorrectly overlap, but that might require too much information. I'd
> suggest something much simpler.
>
> Each Trickle message is a set of hashes. Each hash is over the sorted
> one-hop neighbor set of a node. If a node A has neighbors B and C, it
> transmits a message with hash(neighbors(A)), hash(neighbors(B)),
> hash(neighbors(C)). Each hash is computed with a pseudorandom salt value
> regenerated on each transmission to avoid hash collisions (removing the
> tradeoff of hash size and collision probability).
>
> If a node hears a Trickle message in which every hash agrees with the
> hashes it has (i.e., the hashes of the intersection of those in the message
> and the neighbor lists the node holds), that is a consistent transmission.
>
> When a node changes its neighbor list or changes the neighbor list of one
> of its neighbors, that is an inconsistency event.
>
> Another approach might be to, rather than using hashes, using version
> numbers. Then you enter all of the wraparound problems, of course. But
> otherwise you'll need some mechanism so the authoritative source isn't
> drowned out by many old copies.
>

---

From: Maria Rita PALATTELLA <[email-masked]>
Date: Fri, 21 Jun 2013 09:29:32 +0000

Hi Qin,

It may be configurable. Based on the application, and its requirements, we may decide to share less or more information among neighbor nodes.

Maria Rita

Cc: [email-masked]; [email-masked]; [email-masked]; [email-masked]; [email-masked]

Maria Rita,

Qin

Thought?
Qin

Maria Rita

Hi Thomas,

Best Wishes,
Pouria

Thomas

Phil