=Paper=
{{Paper
|id=Vol-1291/ewili14_17
|storemode=property
|title=The Wi-STARK Architecture For Resilient Real-Time Wireless Communications
|pdfUrl=https://ceur-ws.org/Vol-1291/ewili14_17.pdf
|volume=Vol-1291
|dblpUrl=https://dblp.org/rec/conf/ewili/SouzaR14
}}
==The Wi-STARK Architecture For Resilient Real-Time Wireless Communications==
The Wi-STARK Architecture For Resilient Real-Time Wireless Communications∗ Jeferson L. R. Souza José Rufino jsouza@lasige.di.fc.ul.pt jmrufino@ciencias.ulisboa.pt Departamento de Informática, Faculdade de Ciências, Universidade de Lisboa, Portugal Laboratório de Sistemas Informáticos de Grande-Escala (LaSIGE) Navigators Research Team ABSTRACT 1. INTRODUCTION AND MOTIVATION Networking communications play an important role to se- Advances in microelectronics enable the development and in- cure a dependable and timely operation of distributed and tegration of networking computing systems in environments real-time embedded system applications; however, an effec- with different levels of criticality, monitoring and controlling tive real-time support is not yet properly addressed in the physical entities such as nuclear reactors, physical structure wireless realm. This paper presents Wi-STARK, a novel of buildings and bridges, and power grids. In these kind architecture for resilient and real-time wireless communi- of environments, usually known as Cyber Physical Systems cations within an one-hop communication domain. Low (CPS), communications may have safety-critical constrains, level reliable (frame) communications, node failure detec- implying a mandatory provision of real-time communication tion, membership management, and networking partition guarantees to secure the dependable and timely operation of control are provided; since these low level services extend the entire system. and build upon the exposed interface offered by networking technologies, Wi-STARK is in strict compliance with wire- The literature addressing real-time support on the wireless less communication standards, such as IEEE 802.15.4 and realm can be classified into two distinct domains: (a) com- IEEE 802.11p. The Wi-STARK service interface is then munication protocols and architectures, and (b) schedulabil- offered as operating system primitives, helpful for building ity analysis. distributed control applications. The one-hop dependabil- ity and timeliness guarantees offered by Wi-STARK are a The contributions to real-time communication protocols and fundamental step towards an effective design of real-time architectures, such as [16, 17, 18], are concerned with the wireless networks with multiple hops, including end-to-end provision of end-to-end guarantees within multiple hop net- schedulability analysis of networking operations. works. However, some of them require strong assumptions with respect a global notion of time (synchronised clocks Categories and Subject Descriptors among all nodes of a multiple hop network), which is a prob- C.4 [Computer System Organisation]: [Fault tolerance]; lem by itself without an easy solution. Furthermore, the C.3 [Special-Purpose and Application Based Systems]: used error model only assumes the loss of data frames, ne- Real-time and embedded systems; C.2.1 [Computer Com- glecting the effects that control frame errors may have on the munication Networks]: Network Architecture and De- operation of the Medium Access Control (MAC) sublayer, sign—Wireless communication which may generate network partitions during long periods of time. These partitions may imply an unpredictable tem- Keywords poral behaviour and thus those protocols and architectures wireless communications, real-time, dependability, timeli- may, at the best, only provide probabilistic real-time guar- ness, resilience, fault tolerance, Wi-STARK antees. The schedulability analysis of wireless networking commu- ∗This work was partially supported by the EC, through project nications [3, 11, 12] aims to verify if all transmissions can IST-FP7-STREP-288195 (KARYON); by FCT/DAAD, through meet their deadlines for a given traffic workload, consider- the transnational cooperation project PROPHECY; and by FCT, ing the end-to-end temporal guarantees wanted for a target through project PTDC/EEI-SCR/3200/2012 (READAPT) and through LaSIGE Strategic Project PEst-OE/EEI/UI0408/2014. network. Such end-to-end guarantees depend on the real- time guarantees secured within each single hop. Single hop guarantees can, on its turn, be derived from the temporal behaviour provided by the networking technology (commu- nication protocols included), which must take into account the expected error conditions. EWiLi’14, November 2014, Lisbon, Portugal. Copyright retained by the authors. Conjugating dependability and real-time message delivery guarantees with wireless communications is a difficult prob- lem. Instead of following the classic approach described in the wireless communication literature, and trying to estab- lish those guarantees end-to-end —using a traditional point- to-point communication model —we take a divide to conquer approach, which is motivated by the following statement: If no real-time guarantees can be offered within commu- nications at one-hop of distance, no real-time guaran- tees can be offered within multiple hop communications at all. That means, any dependable real-time message delivery guar- antee has to be secured first within the one-hop of distance wireless space, prior to be extended end-to-end, across mul- tiple hops. Thus, this paper presents a design overview Figure 1: The Wireless Network Segment (WnS) of a novel wireless communications architecture dubbed abstraction Wi-STARK, which has three main goals: (1) taking advan- tage of the intrinsic broadcast properties of the shared wire- channels; and W represents the set of networking access less communication medium within one-hop space, (2) pro- protocols utilised in the support of frame transmissions. As viding dependability and real-time guarantees within such illustrated in the graphical representation of Fig. 1, the in- one-hop space, and (3) ensuring the feasibility of end-to-end tersection of the communication range of all nodes within schedulability analysis given the bounded transmission delay the WnS constitutes its broadcast domain, where each node guarantees within each single hop. The Wi-STARK design xj ∈ X is able to sense any transmission from any other is compliant with wireless communications standards, be- node xq ∈ X. ing able to offer at the lowest level of communications a set of useful and semantically rich services such as reliable and timely communications, node failure detection, membership 2.1 Fault Model The failure of a networking component (a channel c ∈ C or management, and networking partition control. Since these a node x ∈ X) is identified using an omission fault model, services are built upon the exposed interface offered by cur- where frame errors are transformed into omissions. The oc- rent networking technologies, the Wi-STARK architecture currence of frame errors may be originated by disturbances can be easily implemented using Commercial Off-The-Shelf caused by the presence of electromagnetic interferences on (COTS) components. The Wi-STARK service interface can the communication channel, or malfunction within the node easily be made available at the operating system Application machinery, being accounted as omissions for the purpose of Programming Interface (API). monitoring networking components. To present the details concerning the design of the For each received frame, each node x ∈ X locally accounts Wi-STARK architecture, this paper is organised as follows: observed omissions. When the number of observed omis- section 2 presents a brief description of the system model, sions exceeds the component’s omission degree bound, fo , which is the foundation for the design of the Wi-STARK the failure of such component can be locally signed. Errors architecture; section 3 presents the main components and occurred at the wireless communication medium may affect characteristics of the Wi-STARK architecture; section 4 only some nodes, which implies omissions may be accounted presents the primitives and semantics of the Wi-STARK ser- inconsistently at the different nodes of the WnS. vice interface; and finally, section 5 presents the conclusion and future directions of the design and applicability of the Both omissions with origin in the channel and at the channel Wi-STARK architecture. end-points (i.e., the nodes) are accounted for. When succes- sive frames are received with errors from a given channel 2. SYSTEM MODEL input — i.e. a node x ∈ X — exceeding a given omission All networking communications described in this paper are degree bound, a node persistent failure is detected and sig- performed within the scope of a physical and data link layer nalled; when no traffic is received from node x ∈ X within abstract networking model dubbed Wireless network Seg- a bounded monitoring time interval, a node crash failure is ment (WnS), which establishes a broadcast domain where detected and signalled. all wireless nodes are one-hop of distance from one another. This simple approach empowers the achievement of a first Each node x ∈ X may also inconsistently experience a tem- and fundamental result: the capability of exploiting the broad- porary loss of connectivity with the WnS, caused by a phe- cast nature of the shared one-hop communication space. nomenon dubbed network inaccessibility [13]. A period of network inaccessibility may be induced by glitches in the The formalisation of the WnS is expressed by a 4-Tuple, MAC sublayer operation, such as those that may result def W nS = hX, xm , C, W i, where X is the set of wireless nodes from the omission of a MAC control frame (e.g., beacon). members of the WnS; xm is the WnS coordinator, xm ∈ X; The network cannot be considered failed; it only enters into C represents a set of radio frequency (RF) communication a temporary state where the communication service is not Property WnS3 (Error Detection) has both detection and signalling facets; the detection facet, traditionally provided by classical MAC sublayers, derives directly from frame pro- tection through a frame check sequence (FCS) mechanism, which most utilised algorithm is the cyclic redundancy check (CRC); the signalling facet is provided by the FCS exten- sion introduced in [15], which is able to signal omissions detected in frames received with errors. No fundamental modifications are needed to the wireless MAC standards, such as IEEE 802.15.4 [8]. The use of such unconventional extension is enabled by emerging controller technology, such WnS1 - Broadcast: correct nodes, receiving an uncorrupted frame transmission, receive the same frame; as reprogrammable technology and/or open core MAC sub- layer solutions, which are present, for example, in the devel- WnS2 - Frame Order : any two frames received at any two opment kits from ATMEL [1]. With the CRC polynomials correct nodes are received in the same order at both nodes; used in wireless MAC sublayers, the residual probability of WnS3 - Error Detection: correct nodes detect and signal undetected frame errors is negligible [4, 5]. any corruption done during frame transmissions in a locally received frame; Property WnS4 (Bounded Omission Degree) formalises for WnS4 - Bounded Omission Degree: in a known time inter- a channel, c ∈ C, the failure semantics introduced earlier in val Trd , omission failures may occur in at most k transmissions; the fault model definition, being the abstract channel omis- WnS5 - Bounded Inaccessibility : in a known time interval sion degree bound, k ≥ fo . The omission degree of a WnS Trd , a wireless network segment may be inaccessible at most i abstract channel can be bounded, given the error character- times, with a total duration of at most Tina ; istics of its wireless transmission medium [4, 9, 13]. WnS6 - Bounded Transmission Delay : any frame trans- mission request is transmitted on the WnS, within a bounded The Bounded Omission Degree property is one of the most delay Ttd + Tina . complex properties to secure in wireless communications. Securing this property with optimal values and with a high Figure 2: WnS abstract channel properties degree of dependability coverage may require the use of multiple RF channels. In [15] we have advanced on how provided to some or all of the nodes. The loss of connectiv- this can be achieved by monitoring channel omission errors, ity due to transient node mobility is also treated under the and switch between RF channels upon detecting the channel inaccessibility model. omission degree bound has been exceeded. Mobility may drive nodes to outside of the WnS, as illus- The time domain behaviour of a WnS is described by the re- trated in Fig. 1, where node x2 using channel c moves from maining properties. Property WnS6 (Bounded Transmission the geographic position P (x2 ) to the geographic position Delay) specifies a maximum frame transmission delay, which P 0 (x2 ). In despite of x2 transmissions at the new position is Ttd in the absence of faults. The value of Ttd includes the may reach all nodes of the WnS, the transmissions from the medium access and transmission delays and it depends on WnS coordinator, xm ∈ X, do not reach node x2 at posi- message latency class and overall offered load bounds [6, tion P 0 (x2 ). The permanent mobility of a node to outside of 10]. The value of Ttd does not include the effects of omis- the WnS broadcast domain is then transformed into a node sion errors. In particular, Ttd does not account for possible crash failure in our fault model. frame retransmissions. However, Ttd may include extra de- lays resulting from longer WnS access delays derived from 2.2 WnS abstract channel properties subtle side-effects caused by the occurrence of periods of network inaccessibility [13]. Therefore, the bounded trans- Communications at the lowest levels of the networking pro- mission delay includes Tina , a corrective term that accounts tocol stack can be abstracted by a set of correctness, depend- for the worst case duration of inaccessibility glitches, given ability, and timeliness properties, which are not dependent the bounds specified by property WnS5 (Bounded Inacces- on any particular networking technology. In the context of sibility). The inaccessibility bounds depend on, and can the WnS model such properties are seen as being provided be predicted by the analysis of MAC sublayer characteris- by a single abstract communication channel dubbed WnS tics [13]. abstract channel, as illustrated in Fig. 2. Property WnS1 (Broadcast) formalises that it is physically 3. THE Wi-STARK ARCHITECTURE impossible for a node x ∈ X to send conflicting informa- The Wi-STARK is a new low level architecture that takes tion (in the same broadcast) to different nodes, within the advantage of the intrinsic broadcast property of the shared broadcast domain of the WnS [2], BX (c), for a given channel wireless communication medium, and of the set of correct- c ∈ C (see Fig. 1). ness, ordering, dependability, and timeliness properties of- fered by the WnS abstraction (Section 2.2) to establish a Property WnS2 (Frame Order ) is common in network tech- robust, resilient and real-time one-hop communication do- nologies (wireless technologies included), being imposed by main for wireless networks. the wireless communication medium of each channel c ∈ C, and resulting directly from the serialisation of frame trans- The Wi-STARK architecture design is open and flexible, missions on the shared wireless communication medium. being composed by two layers dubbed Channel Layer and 3.2 MAC Sublayer: serviceMAC The MAC sublayer illustrated in Fig. 3 is the standard MAC sublayer present in the traditional wireless networking proto- col stack, such as those specified within the IEEE 802.15.4 [8] and IEEE 802.11p [7] wireless standards. In the context of the Wi-STARK architecture such standard MAC sublayer is dubbed serviceMAC, offering only conventional unreliable data frame and management service interfaces. No mod- ifications are needed for its integration in the Wi-STARK architecture. In this sense, the Wi-STARK architecture is highly flexible supporting the integration of any MAC sub- layer, including the real-time variants proposed in [16, 17]. 3.3 Mediator Layer The Mediator Layer is an extensible sublayer, specially de- signed to mediate the communication flow from (and to) the high level protocol layers, as illustrated in Fig. 3. The Me- Figure 3: The Wi-STARK Architecture diator Layer is responsible for the semantically rich service interface offered by Wi-STARK, effectively augmenting the Mediator Layer. As shown in Fig. 3, these layers are by services offered by the standard MAC sublayer. Three main design wrapping the standard MAC sublayer to improve: components compose the Mediator Layer : the Real-Time the control and use of RF communication channels; and, Communication Suite, the Timeliness & Partition Control, the services offered to high level protocol layers. and the Networking & Management Control. 3.1 Channel Layer 3.3.1 Real-time Communication Suite The Channel Layer (Fig. 4) is a thin layer that provides The Real-Time Communication Suite (RTCS) is the compo- a common interface to transparently control the use of a nent responsible for the data communication services offered given RF communication channel c ∈ C for purposes of by the Wi-STARK architecture, as illustrated in Fig. 5. The frame transmission and reception, incorporating useful ex- RTCS includes a Message Request Dispatcher that forwards tensions to enhance the dependability of communications. A any high level message transmit request to the adequate in- RF communication channel c ∈ C is an abstract represen- stance of the RTCS protocol bundle. Messages submitted tation of the wireless transmission medium plus a piece of at the Wi-STARK service interface have a maximum length hardware dubbed RF transceiver, which conjugates a resid- for allowing the encapsulation of their content in exactly one ual part of the MAC sublayer, herein called, basicMAC and frame, without necessity of fragmentation. the physical (PHY) layer itself. The table of Fig. 5 specifies the fundamental properties (re- The Channel Layer extends the basicMAC to exploit the cipients, ordering, and reliability) characterising the differ- exposed RF transceiver interface, and the parametrisation ent variants of the protocols to be included in the RTCS features thereof. In particular, the Channel Layer imple- protocol bundle. For example: a totally ordered reliable ments: the FCS extension (specified in [15]), which secures message delivery targeting all correct nodes features the well the WnS3 property of the WnS; the accounting of channel known atomic broadcast primitive. This specification is open omissions and the detection of a RF communication chan- and extensible: other attributes (e.g., temporal order ) and nel failure, upon exceeding the omission degree bound, k other properties (e.g., urgency) can be included. (accordingly with WnS4); the RF communication channel switch strategy specified in [15]. The Wi-STARK architecture design provides two funda- mental guarantees to the high level protocol layers and ap- plications: Temporal-bounded communications: every transmitted message1 is successfully received by all relevant correct nodes of the WnS within a known temporal bound, TT x−Data . The value of TT x−Data is directly derived from the combi- nation of four important properties of the WnS: WnS3 (Er- ror Detection), WnS4 (Bounded Omission Degree), WnS5 (Bounded Inaccessibility), and WnS6 (Bounded Transmis- sion Delay). In the absence of errors, the Wi-STARK pro- tocols execute in a single round and the upper bound for all correct nodes of the WnS receiving a message success- fully is: TTwc−ne x−Data = 2.Ttd ; being Ttd the maximum frame transmission delay in the absence of errors. Figure 4: Channel Layer 1 A message is a high level protocol layer data service unit. Figure 6: Timeliness & Partition Control 3.3.2 Timeliness & Partition Control The Timeliness & Partition Control (TPC) presents the transversal components that deals with the temporal aspects of the service offered by the Wi-STARK architecture. As shown in Fig. 6, the TPC component incorporates Time Ser- vices that include the management of protocol timers and other services used in the temporal control of Wi-STARK Real-Time Communication Suite components. Property Attributes Single node (Unicast); The Partition Handler is focused to detect the occurrence, and to be aware of any partitioning incidents caused by the Recipients Multiple nodes (Multicast); presence of periods of network inaccessibility. Controlling All nodes (Broadcast) networking inaccessibility allows the use of optimal timeout Ordering Unordered; Totally ordered values, which are automatically extended [14] when a pe- riod of inaccessibility occurs, preventing the propagation of Reliability Unreliable; Reliable premature timeout errors to other components and to high protocol layers. Figure 5: Real-Time Communication Suite 3.3.3 Networking & Management Control The Networking & Management Control component (illus- In the presence of errors, frames2 may have to be retransmit- trated in Fig. 7) incorporates all the functionalities of the ted and the protocols within the Wi-STARK architecture Mediator Layer responsible for managing the dependable may require more than one round to be executed, up to a operation of each node x ∈ X. The management responsi- limit given by k + i + 1 (as specified by properties WnS4 and bilities assigned to the Mediator Layer include controlling WnS5); all relevant correct nodes can successfully receive all internal configuration of the Wi-STARK architecture, any message transmitted with any reliable commu- the parameters of the MAC sublayer (basicMAC and ser- nication protocol provided by the Wi-STARK architecture viceMAC included), and the provision of management ser- in, at most, TTwc x−Data = (k + i + 1) × (2.Ttd ) + Tina . The vices to support the WnS formation. timer utilised by reliable protocols to control protocol exe- cution is configured with its optimal value (i.e., Ttd ), and All configurations can be performed statically or dynami- extended (if needed) by the real value of the network inac- cally. The static configuration is target for hard real-time cessibility, tina , adding up to at most Tina [14]. environments where all analyses of the traffic pattern, er- ror conditions, and mobility models are performed offline, A failure of the RF communication channel in use is detected being stored in the Wi-STARK Information Base (Fig. 7). by the violation of k, the channel omission degree bound The Mediator Layer (self-)adaptation and dynamic config- (WnS4), being the Wi-STARK architecture able to switch uration capabilities are related with mixed-critical and soft to another channel to keep the networking communications real-time requirements, which are outside the scope of this operational; the duration of the “communication blackout” paper. resultant from that channel failure is then incorporated in the network inaccessibility model through Tina . The membership and node failure detection offered by the Mediator Layer were designed to control and establish a con- Message delivery : every transmitted message is delivered sistent view of all members of the WnS, which is represented to all relevant correct nodes of the WnS. by the abstract set, X. Message delivery guarantees emerge from reliable commu- 4. Wi-STARK DATA SERVICE INTERFACE nication protocols of the Wi-STARK architecture, which In the perspective of networking protocol developers, the de- exploit the nature of the shared wireless communication pendability and timeliness guarantees offered by the medium (properties WnS1 and WnS2) to offer totally or- Wi-STARK architecture are represented by a set of funda- dered delivery guarantees. mental primitives for transmission and reception of messages to/from the network, which are specified in Table 1. 2 A frame is the MAC sublayer protocol data unit. All of the primitives present in the Wi-STARK data service [4] D. Eckhardt and P. Steenkiste. Measurement and Analysis of The Error Characteristics of An In-Building Wireless Network. In 2nd SIGCOMM Conference, 1996. [5] T. Fujiwara, T. Kasami, A. Kitai, and S. Lin. On The Undetected Error Probability for Shortened Hamming Codes. IEEE Trans. on Comm., 33(6), June 1985. [6] M. Hameed, H. Trsek, O. Graeser, and J. Jasperneite. Performance Investigation And Optimization of IEEE 802.15.4 For Industrial Wireless Sensor Networks. In IEEE 13th ETFA Conference, September 2008. [7] IEEE 802.11p. Wireless Access in Vehicular Environments - IEEE Standard 802.11p, 2010. Figure 7: Networking & Management Control Amendment to IEEE Standard 802.11-2007. [8] IEEE 802.15.4. Part 15.4: Wireless Medium Access Wi-STARK data service interface Control (MAC) And Physical Layer (PHY) Primitives Description Specifications For Low-Rate Wireless Personal Area Networks (WPANs) - IEEE standard 802.15.4, 2011. Requests a message transmission us- MLA.Data.request ing one of the Wi-STARK communi- [9] M. Petrova, J. Riihijarvi, P. Mahonen, and S. Labella. cation protocols. Performance Study of IEEE 802.15.4 Using Measurements And Simulations. In WCNC For reliable services, it confirms mes- MLA.Data.confirm sage delivery at recipients. Otherwise, Conference, Las Vegas, NV, USA, April 2006. it confirms only message transmission. [10] I. Ramachandran, A. K. Das, and S. Roy. Analysis of The Contention Access Period of IEEE 802.15.4 MAC. MLA.Data.indication Notifies the arrival of a message. ACM Trans. on Sensor Networks, 3, March 2007. [11] A. Saifullah, Y. Xu, C. Lu, and Y. Chen. Priority Table 1: Wi-STARK data service interface Assignment For Real-Time Flows in WirelessHART Networks. In 23rd ECRTS Conference, July 2011. [12] W. Shen, T. Zhang, M. Gidlund, and F. Dobslaw. interface are easily integrated into embedded and real-time SAS-TDMA: A Source Aware Scheduling Algorithm operating systems, being available as system calls associated For Real-Time Communication In Industrial Wireless to the wireless networking protocol stack. Sensor Networks. Springer Wireless Networks Journal, 19(6), August 2013. 5. CONCLUSION [13] J. L. R. Souza and J. Rufino. Characterization of This paper presented the architectural design of Wi-STARK, inaccessibility in wireless networks - A Case Study on a novel low level architecture for resilient and real-time one- IEEE 802.15.4 Standard. In IFIP 3th IESS hop wireless communications. The definition of Wi-STARK Conference, September 2009. is based on the establishment of an abstract communication [14] J. L. R. Souza and J. Rufino. An Approach to model dubbed Wireless network Segment (WnS), which offer Enhance The Timeliness of Wireless Communications. a set of correctness, dependability, and timeliness properties In 5th UBICOMM Conference, Lisbon, Portugal, to support the design of resilient communication services for November 2011. wireless networks. [15] J. L. R. Souza and J. Rufino. Analysing And Reducing Network Inaccessibility in IEEE 802.15.4 Wi-STARK is compliant with wireless standards such as Wireless Communications. In IEEE 38th LCN IEEE 802.15.4 and IEEE 802.11p, being capable to offer Conference, Sydney, Australia, October 2013. support for low level reliable message communication, node [16] Y.-H. Wei, Q. Leng, S. Han, A. Mok, W. Zhang, and failure detection and membership, and networking partition M. Tomizuka. RT-WiFi: Real-Time High-Speed control. Future directions involves the incorporation of the Communication Protocol For Wireless Cyber-Physical Wi-STARK service interface in the API of embedded real- Control Applications. In IEEE34th RTSS Conference, time operating systems, and the extension of one-hop guar- December 2013. antees for multi-hop networking scenarios. [17] Y. Xue, B. Ramamurthy, and M. C. Vuran. SDRCS: A Service-Differentiated Real-Time Communication 6. REFERENCES Scheme For Event Sensing in Wireless Sensor [1] ATMEL Coorporation. IEEE 802.15.4 MAC Software Networks. Computer Networks, 55(15), June 2011. Package - User guide, May 2012. [18] X. Zhu, S. Han, P.-C. Huang, A. Mok, and D. Chen. [2] O. Babaog̃lu and R. Drummond. Streets of MBStar: A Real-Time Communication Protocol For Byzantium: Network Architectures for Fast Reliable Wireless Body Area Networks. In 23rd ECRTS Broadcasts. IEEE Trans. on Soft. Engineering, Conference, July 2011. SE-11(6), June 1985. [3] O. Chipara, C. Lu, and G.-C. Roman. Real-Time Query Scheduling for Wireless Sensor Networks. IEEE Trans. on Computers, 62(9), September 2013.