Intent

Map keys from one keyset to another. Allows nodes to translate global names to local, optimized names.

Also Known As

Phil's Crazy Idea

Example TinyOS Components

...

Motivation

The Global Keyset pattern provides a way for motes to communicate state or data. Often, a program wants to allocate state for each key of the Global Keyset -- for example, state for reach paramter that can be queried or configured remotely. However, a Global Keyset is usually sparse, and provides no information on how many elements it has.

One approach is to allocate state at run-time. For example, an allocator component can take requests for state (e.g., in initialization), and bind a state element to a global ID. This uses CPU cycles to allocate the state, and also imposes a RAM overhead, as it requires the allocating component to store the ID in RAM. Additionally, finding the element associated with a global key requires searching the set of elements. Finally, there is the issue of knowing how many elements to allocate; if there are too few, this mismatch will not be detected until runtime.

In this example -- configurable parameters -- we'd like to be able to use something like the Service Instance pattern for each parameter. However, parameters are a Global Keyset, so users can easily name them and motes can agree on what parameter is being name, and the Service Instance pattern uses a Local Keyset to refer to its instances. We need an efficient way to map between a Global and Local Keyset.

The Keyset Map provides such a capability. Using component wiring, it defines keyset translation at compile-time, removing the CPU and RAM overhead inherent in a run-time approach. The mapping itself is in terms of parameterized interfaces.

Applicability

Use the Local Keyset pattern when:

Use the Local Keyset pattern when:

• Two or more components refer to the same things through different keysets
• Those components need to coordinate

Structure

Participants

• GlobalSvc: The component that provides access to elements in terms of a Global Keyset.
• LocalSvc: The component that provides access to elements in terms of a Local Keyset.
• User: The component that uses the element provided by GlobalSvc in terms of a global key.

Consequences

Implementation

Sample Code

In this example, the DripC component follows the Dispatcher pattern for configurable system parameters. Users can send key-value pairs to a network, which propagate epidemically. The key is a global key, so that motes agree on what parameter it corresponds to. However, each configurable parameter requires some state (e.g., its version), so DripC needs to use the Service Instance pattern, embodied by the DripStateC component, to maintain this state.

configuration DripC {
  provides interface Drip[uint8_t globalID];
  uses interface DripState[uint8_t globalID];
}

configuration DripStateC {
  provides interface DripState[uint8_t localID];
}

configuration User {
  uses interface Drip;
}


User.Drip -> DripC.Drip[GLOBAL_PARAM_CONSTANT];
// The mapping
DripC.DripState[GLOBAL_PARAM_CONSTANT] -> DripStateC.DripState[unique("DripState")];

DripC refers to a parameter in terms of its global key -- in this case, GLOBAL_PARAM_CONSTANT -- while DripStateC refers to a paramter in terms of its local key, generated by unique.

Known Uses

The Drip parameter configuration component -- described above -- uses a Keymap.

Related Patterns

The Keymap allows you to map between arbitrary keysets, but the common use is to map between components that use Global Keysets and those that use Local Keysets.