Baloo Managing time
Discuss all matters and configuration related to time management in Baloo.
Baloo is responsible for managing time at two different layers:
- At the LINK layer, it triggers the execution of the synchronous transmission primitives. The primitives run on a a high-frequency timer (due to the extreme time sensitivity of their operations).
- At the middleware layer, it schedules the rounds and slots, for which a low-frequency timer is sufficient.
The available frequency sources depend on the platform. Below are listed the values of the current implementations.
| Platform | Low-freq timer | High-freq. timer |
|---|---|---|
| sky | 32 kHz | 4.2 MHz |
| dpp-cc430 | 32 kHz | 3.25 MHz |
The execution of the middleware protothread is based on the firings of a real-time timer (an rtimer-ext, see the dedicated page); thus, the middleware executes in interrupt context. Other running processes (e.g., Baloo pre- and post-processes) are interrupted by the middleware.
In the current implementation, Baloo's callbacks are executed by the middleware, which implies that they also run in interrupt context, which may cause problems in case of overruns. With a different implementation, the middleware could interrupt an overrunning callback to ensure that communication slots start on time, but that is not desirable in general; an interrupted callback would have to be considered as a failure by the NET layer. In such a case, successfully participating in the corresponding data slot would not really matter anyway.
To mitigate this problem, the middleware monitors the execution time of the callbacks. If a callback overruns and the middleware cannot guarantee the timely execution of the next slot, this slot is skipped (i.e., the node does not participate at all in this slot, similarly as with the slot skipping feature) and a notification event is sent to the network layer. With this approach, Baloo can guarantee to respect the timing requirement for synchronous transmissions as long as the callbacks have enough time to complete their execution. To satisfy this condition, the available time between slots for the execution of the callbacks is controlled by a dedicated configuration parameter: the gap time.
Since the callbacks implement the protocol logic at NET layer, the user is responsible to configure suitable gap times.
Note
This default strategy may lead to a starvation problem if a callback “never” returns, e.g., if it relies on another software sitting at higher layers. Allowing the user to interrup overrunning callbacks is part of our work-in-progress list.
In Baloo, there are five types of time-related variables
- Round period
- Absolute time
- Slot time
- Guard time
- Gap time
The first two relates to inter-round timing and the last three to intra-round timing.
As presented in the control packet description, the time and period fields of the schedule section respectively hold the absolute network time and the time interval until the next round.
To keep these variables small while offering a large range of possible settings to the user, Baloo implements four different time scales for these variables: 1s, 100ms, 10ms, and 1ms. The values in the time and period fields are interpreted by the middleware as multiple of the selected time scale, which can be set by the user with the following macro (typically done in project-conf.h)
#define GMW_CONF_PERIOD_TIME_BASE { GMW_CONF_PERIOD_TIME_BASE_1s < OR >
GMW_CONF_PERIOD_TIME_BASE_100ms < OR >
GMW_CONF_PERIOD_TIME_BASE_10ms < OR >
GMW_CONF_PERIOD_TIME_BASE_1ms }
The time scale is set to GMW_CONF_PERIOD_TIME_BASE_1s by default.
The time field is not used by the middleware to schedule communication. In Baloo, everything is organised based on the relative time from a previous round. In other words, the middleware schedule a future round based on the start time of the current round and the period contained in the schedule.
The time field mostly serves timestamping purposes (e.g., in a data collection scenario, distributed nodes may use the global time information to timestamp their sensor readings). It is not necessary to the correct behavior of Baloo.
The period corresponds to the time interval between the sending time of two consecutive control packets. At the end of a round, the middleware schedules itself to execute again early enough such that the sending of the control packet can start according to the defined period; for example, leaving enough time to compile the control information in the control packet, executing Baloo's pre-process, accounting for the guard time, etc.).
Within one round, the timing of operations is configured based on slot, guard and gap times, each of which can be configured independently for the control packet. The interplay between the different parameters is illustrated below.
The slot, gap, and guard times define when the different nodes start the execution of the different slots in the round.
The slot time corresponds to the maximal time a primitive is allowed to execute; in other words, the execution of a running primitive is interrupted if the slot time is exceeded.
By default, slot times can be set with a 500us precision, resulting in a value range of 0 to 127.5ms.
Note
If longer slot times are required, the user may modify the time base for the slot time by changing the value of theGMW_CONF_SLOT_TIME_BASEmacro ingmw-conf.h. It is however not intended to be modified by the standard user. Although technically possible, modifying the slot time scale may have unforseen consequences and break Baloo.
The user can easily set the desired slot time with the following helper macro, which converts a numerical value in microsecond into the corresponding setting (rounded up based on the configured time scale)
#define GMW_US_TO_SLOT_TIME(t)The expected execution time of some synchronous transmission primitives (e.g. Glossy) can be precisely computed. Baloo implements some helper macros that compute such estimates, which can be useful to define slot times.
/*
* Minimum duration in us of a Glossy flood according to "Energy-efficient
* Real-time Communication in Multi-hop Low-power Wireless Networks"
* (Zimmerling et al.) plus 250 us of slack time.
* GMW_T_HOP(len) should return the duration in us the radio hardware needs to
* transmit a packet of length len.
* @param len total size of the packet sent by the hardware
* @param n number of retransmissions, a glossy parameter
* @param hops maximal number of hops in the network
* */
#define GMW_T_SLOT_MIN(len, n, hops) ((hops + (2 * n) - 1) * \
GMW_T_HOP(len) + \
250 )
/* same formula but adapted for the strobing mode */
#define GMW_T_SLOT_STROBE_MIN(len, n) (n * (GMW_T_HOP(len) + \
STROBING_CONF_TX_TO_TX_DELAY) + 250 )In additions, macros holding the desired number of retransmissions and the (expected) maximal number of hops in the network are available (shown below with their default values - see gmw-conf.h)
#define GMW_CONF_TX_CNT_CONTROL 4
#define GMW_CONF_TX_CNT_DATA 3
#define GMW_CONF_MAX_HOPS 5For data slots, the slot time can be dynamically adapted at runtime using the slot_time field is the control's configuration section. Unless configured otherwise, Baloo uses the GMW_CONF_T_DATA macro, which is initialized using the GMW_T_SLOT_MIN helper macro.
In the particular case of contention slots, the slot time is statically set using the GMW_CONF_T_CONT macro, which has a default value of 8ms.
For control slots, the slot time is statically set using the GMW_CONF_T_CONTROL macro. Unless configured otherwise, GMW_CONF_T_CONTROL is initialized using the GMW_T_SLOT_MIN helper macro.
The guard time corresponds to the amount of time a node starts trying to receive a packet in a given slot before the scheduled start of that slot. This is a standard way of dealing with small synchronization errors between senders and receivers.
Baloo performs time synchronization using Glossy, which achieves synchronization error of the order of microseconds. However, between two synchronization events, local clocks of different nodes drift apart, which Baloo compensates for using the guard time. In addition, a simple clock-drift compensation mechanism is implemented
For data slots, the guard time is statically set using the GMW_CONF_T_GUARD_SLOT macro, which has a default value of 500us. This setting is also used for contention slots.
For control slots, the guard time is statically set using the GMW_CONF_T_GUARD_ROUND macro, which is set equal to GMW_CONF_T_GUARD_SLOT by default.
The gap time corresponds to the time between consecutive data slots, in between which some callback functions must be executed. As illustrated above, the guard time is also included in the gap time.
By default, gap times can be set with a 100us precision, resulting in a value range of 0 to 25.5ms.
Note
If longer gap times are required, the user may modify the time base for the slot time by changing the value of theGMW_CONF_GAP_TIME_BASEmacro ingmw-conf.h. It is however not intended to be modified by the standard user. Although technically possible, modifying the gap time scale may have unforseen consequences and break Baloo.
The user can easily set the desired gap time with the following helper macro, which converts a numerical value in microsecond into the corresponding setting (rounded up based on the configured time scale)
#define GMW_US_TO_GAP_TIME(t)For data slots, the gap time can be dynamically adapted at runtime using the gap_time field is the control's configuration section. Unless configured otherwise, Baloo uses the GMW_CONF_T_GAP macro, which has a default value of 4ms. This setting is also used for contention slots.
For control slots, the gap time is statically set using the GMW_CONF_T_GAP_CONTROL, which set equal to GMW_CONF_T_GAP by default.
The middleware implements a very simple clock drift compensation algorithm. When a node is synchronized (i.e., in the Running), the round period is measured and compared to the period from the control structure. The difference is used to estimate the clock drift: drift_estimate = (new_estimate + drift_estimate)/2
This clock drift compensation feature is active by default. If desired, the user can desactivate it by setting the following macro equal to 0 (typically in project-conf.h).
#define GMW_CONF_USE_DRIFT_COMPENSATION