Skip to content

LWMAC: avoid receiving duplicate broadcast packet.#7442

Closed
zhuoshuguo wants to merge 3 commits intoRIOT-OS:masterfrom
zhuoshuguo:lwmac_eliminate_duplicate_bcast
Closed

LWMAC: avoid receiving duplicate broadcast packet.#7442
zhuoshuguo wants to merge 3 commits intoRIOT-OS:masterfrom
zhuoshuguo:lwmac_eliminate_duplicate_bcast

Conversation

@zhuoshuguo
Copy link
Copy Markdown
Contributor

@zhuoshuguo zhuoshuguo commented Aug 3, 2017

This PR solves the problem of LWMAC that nodes will sometimes receive duplicate broadcast packet.

When broadcasting a packet in LWMAC, the sender keep transmitting the same frame for fully a GNRC_LWMAC_BROADCAST_DURATION_US duration which is slightly longer than a LWMAC cycle duration, to guarantee that all neighbour node will at least receive a copy. However, in case the start of the broadcast duration is right with the start of a neighbour receiver's wake-up period, this neighbour receiver may receive duplicate broadcasting frames in their adjacent two cycles' wake-up periods. Namely:

|-Wakeup-|----------sleep-------------|-Wakeup-|----------sleep-------------|
|********* broadcasting period **********|

This PR solves this problem by introducing some parameters to record recent broadcasting information, e.g., the ID and bcast sequence of the broadcasting sender. Once the receiver indicates receiving duplicate broadcast frames (i.e., bcast-node-ID and bcast-sequence are the same as in the last cycle), it ignores the duplicate copy.

@jnohlgard
Copy link
Copy Markdown
Member

I think this functionality is rather useful for more than LWMAC. I need something like this in ContikiMAC as well.
Would it make sense to move this deduplication to the _recv function in https://github.com/RIOT-OS/RIOT/blob/master/sys/net/gnrc/link_layer/netdev/gnrc_netdev_ieee802154.c ?

@jnohlgard
Copy link
Copy Markdown
Member

In IEEE 802.15.4, the (source address, sequence number) tuple should be enough to determine if a packet is a dup, since the standard specifies that the sequence number (DSN) shall increment on each new packet transmitted, but not for retransmissions.

@zhuoshuguo
Copy link
Copy Markdown
Contributor Author

In IEEE 802.15.4, the (source address, sequence number) tuple should be enough to determine if a packet is a dup, since the standard specifies that the sequence number (DSN) shall increment on each new packet transmitted, but not for retransmissions.

That is it, agreed. But not enough, see below.

Would it make sense to move this deduplication to the _recv function in https://github.com/RIOT-OS/RIOT/blob/master/sys/net/gnrc/link_layer/netdev/gnrc_netdev_ieee802154.c ?

That is a good idea, but I currently foresee it maybe a little bit complicated if we merge this functionality into gnrc_netdev_ieee802154.c. The reason is that, if we want to do so, we may need a timeout module for gnrc_netdev_ieee802154.c. Why we need a timeout module? Because, there is a possibility that: in case (1) node-A firstly sends a data with a sequence number of (e.g.,) 0x25 to node-B; (2) then, node-A turns to send 255 packets to other nodes (not node-B); (3) node-A again turns to send a new packet to node-B with a sequence of exactly 0x25 (the same as the last one it sends to node-B); then, in case that node-B didn't receive any packet since the last time node-A sent to it, node-B will drop this packet (regarded as duplicate packet) while it shouldn't.

The only way to avoid this bug is that, node-B should understand that, the two packets, both from node-A, both with sequence 0x25, are not the same packet, which we should use some kind of timeout window tool to differentiate them, i.e., we only regard the two packets are the same in a narrow time window.

@miri64
Copy link
Copy Markdown
Member

miri64 commented Sep 6, 2017

Would it make sense to move this deduplication to the _recv function in https://github.com/RIOT-OS/RIOT/blob/master/sys/net/gnrc/link_layer/netdev/gnrc_netdev_ieee802154.c ?

Or rather invest in the future and do it as a follow-up to #7409 instead ;-).

@zhuoshuguo
Copy link
Copy Markdown
Contributor Author

By the way, just to make it clear. ;-) the issues I mentioned here, for unicast and broadcast, are not the same, they are two different problems. This PR solves LWMAC duplicate bcast packet problem that I guess many low duty-cycle MACs will encounter. LWMAC doesn't have duplicate unicast packet problem due to its preamble-preambleACK-data transmission scheme.

@miri64
Copy link
Copy Markdown
Member

miri64 commented Sep 6, 2017

@zhuoshuguo I think your example is a classical case of over-complicating the situation. For a MAC protocol this might be something to consider, but just as a measure of keeping duplicated packets at bay this sounds like overkill (or: if a wrong packet get's accidentally in dropped in a corner-case: so what, upper layers may resend). Also: since @gebart is proposing to add this to the recv of the IEEE 802.15.4 glue-code to GNRC, you also still can add a timing-based implementation for a MAC protocol.

@zhuoshuguo
Copy link
Copy Markdown
Contributor Author

@miri64 @gebart So, let me build a new PR for adding duplicate packet check for rev of IEEE 802.15.4? ;-)

@miri64
Copy link
Copy Markdown
Member

miri64 commented Sep 6, 2017

@miri64 @gebart So, let me build a new PR for adding duplicate packet check for rev of IEEE 802.15.4? ;-)

I can do that as well, as a follow-up to #7409.

@zhuoshuguo
Copy link
Copy Markdown
Contributor Author

OK, so I leave it to you. ;-)

@miri64
Copy link
Copy Markdown
Member

miri64 commented Sep 6, 2017

Done. See #7577

@miri64
Copy link
Copy Markdown
Member

miri64 commented Sep 6, 2017

(or 787dff1 just for the change ;-))

@miri64
Copy link
Copy Markdown
Member

miri64 commented Sep 6, 2017

Off-topic: lwMAC needs to be ported to gnrc_netif2 at some point as well (but let's merge it first).

@miri64 miri64 self-assigned this Sep 19, 2017
@miri64 miri64 self-requested a review September 19, 2017 12:08
@miri64 miri64 added Type: enhancement The issue suggests enhanceable parts / The PR enhances parts of the codebase / documentation GNRC Area: network Area: Networking labels Oct 28, 2017
@kYc0o kYc0o mentioned this pull request Oct 30, 2017
15 tasks
@miri64
Copy link
Copy Markdown
Member

miri64 commented Nov 15, 2017

I guess with #7577 in place and #7895 already merged, I think we can close this one. Re-open if you disagree.

@miri64 miri64 closed this Nov 15, 2017
@zhuoshuguo
Copy link
Copy Markdown
Contributor Author

Hi, Martine. Actually, I would like to keep this PR. I understand that #7577 does solve similar problems, but not completely for LWMAC broadcasting.
The reason is quite tricky:
there is a possibility that, especially in dense network,

S-1: |-Wakeup-|----------sleep-------------| D |-------------sleep-----------
                                             |
                                             v
R   : |-Wakeup-|----------sleep-------------|-Wakeup-|----------sleep-------------|
S-2: |********* broadcasting period **********|

sender-1 may wake up to the receiver's (second wakeup, in the above figure) wake-up period and sends its data just ahead of a repeated packet from sender-2 to the receiver (refresh the sequence number recorded in #7577 ). In this case, #7577 will not work to release the duplicate broadcast packet from sender-1, while the revisions in this PR can. I totally understand that this case is with little chance, and rarely to happen. But, it did happens sometimes..

I know I may be over-complicating again... :-\

@miri64
Copy link
Copy Markdown
Member

miri64 commented Nov 15, 2017

Ok, then can you maybe base this PR on the other one?

@miri64 miri64 reopened this Nov 15, 2017
@zhuoshuguo
Copy link
Copy Markdown
Contributor Author

zhuoshuguo commented Nov 15, 2017

Yes, definitely, I need to rebase.

But, actually I am not sure how sensitive I should be when dealing with this kind of problems. Since, #7577 has already eliminated a very hug portion of the duplicate problem. So, maybe we can close this PR, without costing extra memory introduced by this PR. It depends on how careful we want LWMAC to be when dealing with duplicate broadcast packets. :-)

@miri64
Copy link
Copy Markdown
Member

miri64 commented Nov 15, 2017

Do as you like it best :-)

@zhuoshuguo
Copy link
Copy Markdown
Contributor Author

OK, so let me keep it here. :-)

@miri64
Copy link
Copy Markdown
Member

miri64 commented Nov 27, 2017

@zhuoshuguo now that you are leaving, are there any plans for this PR?

@miri64
Copy link
Copy Markdown
Member

miri64 commented Mar 15, 2018

Ping @zhuoshuguo?

@zhuoshuguo
Copy link
Copy Markdown
Contributor Author

@miri64 Will handle it soon~

@zhuoshuguo zhuoshuguo force-pushed the lwmac_eliminate_duplicate_bcast branch from 49fbad4 to f29bd5c Compare March 30, 2018 01:55
@zhuoshuguo
Copy link
Copy Markdown
Contributor Author

@miri64 Rebased~

@zhuoshuguo
Copy link
Copy Markdown
Contributor Author

Ping~ locally tested through on samr21-xpro boards, it works for the designed bcast feature.

@miri64
Copy link
Copy Markdown
Member

miri64 commented Jun 5, 2018

Needs rebase again... Sorry :(.

@miri64 miri64 removed the GNRC label Oct 5, 2018
@miri64
Copy link
Copy Markdown
Member

miri64 commented Aug 5, 2019

Ping @zhuoshuguo?

@stale
Copy link
Copy Markdown

stale bot commented Feb 6, 2020

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. If you want me to ignore this issue, please mark it with the "State: don't stale" label. Thank you for your contributions.

@stale stale bot added the State: stale State: The issue / PR has no activity for >185 days label Feb 6, 2020
@stale stale bot closed this Mar 8, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

Area: network Area: Networking State: stale State: The issue / PR has no activity for >185 days Type: enhancement The issue suggests enhanceable parts / The PR enhances parts of the codebase / documentation

Projects

None yet

Development

Successfully merging this pull request may close these issues.

4 participants