Difference between revisions of "New Message"

From TinyOS Wiki
Jump to: navigation, search
(Comparing Proposals)
(Scenarios)
Line 208: Line 208:
 
''' Scenario 5 '''
 
''' Scenario 5 '''
  
We have two separate communication stacks, both of which send packets at max MPDU length.  What is the memory overhead of packets allocated for the Ieee154-only-stack?
+
We have two separate communication paths for the stack, both of which send packets at max MPDU length.  What is the memory overhead of packets allocated for the Ieee154-only-path?
  
 
  App -> E2ESecurity -> E2ETransport -> Route -> Ieee154 -> Radio
 
  App -> E2ESecurity -> E2ETransport -> Route -> Ieee154 -> Radio
   +----------------------- Ieee154 --------------------------^
+
   +------------------------------------------------^

Revision as of 00:02, 20 August 2010

TinyOS needs a new message buffer abstraction due to the need for variable headers.

Proposals

The following proposals exists.

Proposal See
KISS https://www.millennium.berkeley.edu/pipermail/tinyos-devel/2010-August/004518.html
Jan's https://www.millennium.berkeley.edu/pipermail/tinyos-devel/2010-August/004519.html
M1 https://www.millennium.berkeley.edu/pipermail/tinyos-devel/2010-August/004525.html
M2 https://www.millennium.berkeley.edu/pipermail/tinyos-devel/2010-August/004525.html (alternative proposal mentioned in section V)
YAMP https://www.millennium.berkeley.edu/pipermail/tinyos-devel/2010-August/004524.html

Comparing Proposals

The following table compares the proposals based on bound on number of times a header needs to be copied, bound on the number of time data needs to be copied, memory allocated per packet, communication stack layer modularity, and how headers of underlying layers are accessed.

Proposal Bound on header copy Bound on data copy Bound on memory allocated per packet Modularity in stack Header access
KISS O(#format) O(#format) MDPU + metadata Limited. All header data is reset on format, so a layer would have to know how to restore them from the underlying layers. Through layer of interest as a dynamical offset in the buffer.
Jan O(#layers) O(1) - if a received packets new headers are unaligned with buffer MDPU + metadata + 2 Doubtful. Vars are passed from layer to layer. Headers of (+1) sub-layers will have to be passed through intermediate layers.
M1 O(#format or adjust) O(#footers) - if footers on received packet are removed and there's not enough space for new headers MDPU + MAX_FOOTER_LENGTH + metadata + 1 Yes, layers can be arbitrary stacked Through layer of interest as a dynamical offset in the buffer.
M2 O(#format or adjust) O(#format or adjust) - whenever a footer is added or removed MDPU + metadata + 1 Yes, layers can be arbitrary stacked Through layer of interest as a dynamical offset in the buffer.
YAMP O(1) - when copied between metadata and actual header never MAX_DATA_LENGTH + MAX_HEADER_LENGTH + MAX_FOOTER_LENGTH + metadata + 2 Limited. If packet formatting layers are separated from communication logic layers, it enables modularity of the communication logic layers. Through layer of interest on a static location in the buffer.

The proposals needs to be able to handle the scenarios listed below. The following table summarizes how each proposal handle the scenarios.

Scenario\Proposal KISS Jan's M1/M2 YAMP
Scenario 1 The App formats the packet with the desired security mode. Routing layer would need to format the packet when addr mode changes and hence need to know how to restore headers of all layers below (need to be reformatted with the security mode set from App). Routing layer would pass on Ieee154 security mode from App to Ieee154 layer. Routing layer would adjust the Ieee154 layers addr mode which leaves everything else unchanged. Routing layer would set the metadata addressing fields of the Ieee154 layer.
Scenario 2 Routing layer would need to format the packet when it changes communication stack (or when addr mode is changed as for scenario 1). The routing layer would have to know how to transfer a packet from Ieee154 (and Radio1) format to PropertaryPacket (and Radio2) format. Routing layer would have to retrieve all sub-layer parameters on receive and them pass them on to the right communication stack on send. The routing layer would have to know how to transfer a packet from Ieee154 (and Radio1) format to PropertaryPacket (and Radio2) format. Routing layer would need to format the packet when it changes communication stack. The routing layer would have to know how to transfer a packet from Ieee154 (and Radio1) format to PropertaryPacket (and Radio2) format. The App could set the Ieee154 and PropertaryPacket parameters for the packet when passed to the routing layer, but when the routing layer receives a packet from one communication stack, it would need to set the according metadata of the other communication stack. Again, The routing layer would have to know how to transfer a packet from Ieee154 (and Radio1) format to PropertaryPacket (and Radio2) format.
Scenario 3 The radio layer has statically allocated space in the metadata field of the message structure and provides a Metadata interface for protocols to access it. The routing layer can access the radios metadata through this interface. The radio layer has statically allocated space in the metadata field of the message structure and provides a Radio interface for protocols to access it. The routing layer can access the radios metadata through this interface. The radio layer has statically allocated space in the metadata field of the message structure and provides a Radio interface for protocols to access it. The routing layer can access the radios metadata through this interface.
Scenario 4 The routing layer would need to format the packet to change addr mode. This format will fail, and the case can be handled before the packet is passed on to the lower layers. The routing layer would pass on the packet to the lower layers which would fail at the layer which realizes that the packet is too big. The routing layer would need to adjust the packet to change addr mode. This adjust will fail, and the case can be handled before the packet is passed on to the lower layers. The routing layer would pass on the packet to the lower layers. The assembly of the packet at the lowest layer will fail and return.
Scenario 5 0 0 0 E2E_SEC_HEADER_LENGTH + E2E_TRANSPORT_HEADER_LENGTH + ROUTE_HEADER_LENGTH

To sum it all up, lets try and keep an overview of why/why not a proposal should be used.

NOTE: THE FOLLOWING TABLE IS NOT UPDATED

Proposal Why should we NOT use this? Why should we use this?
KISS The data is moved every time the header length is changed. A protocol layer needs to be aware if its underlying layers whenever a packet is formatted within a communication stack.
Jan's Intermediate layers would have to pass on parameters of lower layers from upper layers.
M1 Memory overhead with many footers (thought to be rare) memmove of data very very rare. Modular architecture, only need to be aware of underlying layers when packet changes communication stack.
M2 Data memmove everytime footer added or removed Modular architecture, only need to be aware of underlying layers when packet changes communication stack.
YAMP Memory overhead. Especially in scenario 2 where metadata for both Ieee154 and ProprietaryPacket needs to be allocated. No need for memmove of data. (Limited) Modular architecture (restricted by a total order of layers), only need to be aware of underlying layers when packet changes communication stack.

Scenarios

Scenarios that the new message abstractions should be able to handle.

Scenario 1

We have a single communication stack where the header size depends on the Ieee154 security mode and addressing length.

Layers:

App -> Route -> Ieee154 -> Radio

App internals:

Set Ieee154 security mode on packet
Send to route

Route internals:

Set Ieee154 addr mode on packet
Send to Ieee154

Scenario 2

We have a split communication with two different radios sending different packet formats. In this case we have to assume that the routing layer knows about its underlying layers in order to transfer a packet from Ieee154 format to the Proprietary format and vice versa. This means that the routing layer can choose one of the two underlying formats as its standard one, and expose that interface to the upper layers. Lets say it chooses Ieee154 as its standard format and for simplicity store all packets internally as Ieee154 packets (alternatively it can use a flag in the metadata to indicate the format of the packet stored).

Layers:

App -> Route -> Ieee154 -> Radio1
         +----> ProprietaryPacket -> Radio2

App internals:

Set Ieee154 security mode on packet (from the App it looks like the routing layer sends Ieee154 packets).
Send to route

Route internals:

if send on Ieee154
    Set Ieee154 addr mode on packet
    Send to Ieee154
else
    Set proprietary addr mode on packet
    Send to ProprietaryPacket

Scenario 3

We have a single communication stack where the Radio layer stores the incoming (and outgoing if ACK is used) RSSI and LQI of a packet.

Layers:

App -> Route -> Ieee154 -> Radio

Radio internals:

Sets its RSSI and LQI of a packet.

Route internals:

Gets the RSSI and LQI from a packet and uses this to update its routing table

Scenario 4

We have a single communication stack where the routing layer gets (from App or a neighbor) a packet so long that it can only be sent with a short Ieee154 addresses but it wants to send the packet with long Ieee154 addresses. How is this handled?

Layers:

App -> Route -> Ieee154 -> Radio

Routing internals:

Sets Ieee154 addr mode
Send to Ieee154? (<-- note the ?)

Scenario 5

We have two separate communication paths for the stack, both of which send packets at max MPDU length. What is the memory overhead of packets allocated for the Ieee154-only-path?

App -> E2ESecurity -> E2ETransport -> Route -> Ieee154 -> Radio
 +------------------------------------------------^