11/4/11 Communication Protocols for Embedded Systems

1/9 www.ece.cmu.edu/koopman/protsrvy/protsrvy.html
This article was published in:
Embedded Sstems Programming, 7(11), November 1994, pp. 46-58.
Communication Protocols
for Embedded Sstems
Bhargav P. Upender
bargutrc.utc.com
Philip J. Koopman, Jr.
koopmancmu.edu
The past Iew years have seen the beginning oI a trend to dramatically increase the embedded electronics content oI
automobiles, elevators, building climate control systems, jet aircraIt engines, and other traditionally electro-
mechanically controlled systems. In many large systems this increasing electronics content is being accompanied by a
proliIeration oI subsystems having separate CPUs.
The increase in the number oI processors in a system is oIten driven by computation and I/O growth. In some
development environments, the increase may also be driven by a need to ease system integration burdens among
multiple design groups or to provide system Ilexibility through "smart sensors" and "smart actuators". But, whatever the
reasons, once there is more than one CPU in a system there must be some means oI communication to coordinate
action.
While some high-end embedded systems communicate over a VME backplane or similar arrangement, the embedded
systems we're working on use physically distributed CPUs and thus involve some sort oI Local Area Network (LAN),
also called a multiplexed network or a communication bus. At the heart oI the LAN is the media access protocol,
which arbitrates (picks the next transmitter Ior) access to the shared network medium (typically a wire, Iiber, or RF
Irequency).
In this article, we will Iirst discuss the special considerations Ior networking real-time embedded systems. Then, we
describe several media access protocols that demonstrate Iundamentally diIIerent ways oI accessing the shared
medium. The protocols we discuss are: Connection Oriented Protocols, Polling, Time Division Multiple Access
(TDMA), Token Ring, Token Bus, Binary Countdown, Carrier Sense Multiple Access with Collision Detection
(CSMA/CD), and Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA). For each oI these
protocols, we will evaluate the strengths and weaknesses against the special considerations. We conclude the article by
presenting a protocol tradeoII chart which will enable you the select a protocol to Iit your needs. While no protocol is
perIect Ior all purposes, we think that a variation oI CSMA/CA oIIers the most versatility Ior many embedded systems
|1|.
SPECIAL CONSIDERATIONS FOR EMBEDDED
APPLICATIONS
In practice, we have Iound that embedded real-time networks require high eIIiciency, deterministic latency, operational
robustness, conIiguration Ilexibility, and low cost per node.
Because cost limits the network bandwidth available to many applications, protocol eIIiciency (message bits delivered
11/4/11 Communication Protocols for Embedded Systems
2/9 www.ece.cmu.edu/koopman/protsrvy/protsrvy.html
compared to raw network bandwidth) is very important. The embedded systems we have studied are characterized by
a predominance oI short, periodic messages. So, an obvious optimization is to reduce overhead bits used Ior message
packaging and routing (it is not unusual Ior 8 bits oI data to be packed in a message that is 32 or even 64 bits long).
Once message overhead has been reduced as much as possible, media access overhead must be reduced. For the
most part, this is accomplished by minimizing the network bandwidth consumed by arbitration (e.g., passing a token or
resolving collision conIlict). Because worst-case behavior is usually important, eIIiciency should be evaluated both Ior
light traIIic as well as heavy traIIic. For example, CSMA/CD (oIten used in workstation LANs) is highly eIIicient Ior
light traIIic but gives poor perIormance iI heavily loaded, while Token Bus protocols have the reverse properties.
Determinacy, or the ability to calculate worst-case response time is important Ior meeting the real-time constraints oI
many embedded control applications. A prioritization capability is usually included in systems to improve determinacy
oI messages Ior time-critical tasks such as exception handling and high-speed loop control. Priorities can be either
assigned by node number or by message type. Additionally, protocols can support local or global priority mechanisms.
In local prioritization, each node gets a turn at the network in sequence and sends its highest priority queued message
(thus potentially Iorcing a very high priority message to wait Ior other nodes to have their turns Iirst). In global
prioritization the highest priority message in the entire system is always transmitted Iirst. This mechanism, which is
Iundamentally enabled by the media access protocol, is highly desirable Ior many saIety critical applications.
Many applications require robust operation under extreme conditions. We call a protocol robust iI it can quickly detect
and recover Irom errors (e.g., duplicate or lost tokens), added nodes, and deleted nodes. In some systems it is also
important to quickly recover Irom a reset or power glitch that Iorces a restart oI the network.
Varied operating environments may dictate use oI a media access protocol that is Ilexible in supporting multiple media
as well as mixed topologies. For example, portions oI a system may require expensive Iiber in noisy environments,
while other portions can tolerate low-cost twisted pair wires in benign environments. Further, a bus topology may be
optimum Ior wires, but a ring or star topology maybe needed Ior Iiber.
Finally, a vital consideration is the cost per node. In this article, the order oI the media access discussion progresses
Irom very simple to complex, high perIormance protocols. Simple protocols require less hardware and soItware
resources and are thereIore likely to be less expensive. For extremely cost-sensitive high-volume applications, these
protocols are good candidates. However, Ior growth-expected applications, more advanced protocols provide a
stronger Ioundation. In general costs are decreasing over time due to advances in IC manuIacturing technology and the
increasing availability oI oII-the-shelI protocols. Consequently, we envision advanced cost-eIIective protocols used in
many embedded applications.
MEDIA ACCESS PROTOCOLS
Now that we have a Ieel Ior the issues to deal with in embedded networks, let's examine the various commonly
available media access protocols. While many variations and combinations are possible, we'll just discuss the plain
versions oI each protocol.
Connecion Oiened Poocol
BeIore LANs became popular, connection-oriented protocols were heavily used to connect remote terminals to
mainIrames. These protocols support only two nodes per physical transmission medium, and are typically connected
via modem with serial lines. Figure 1 shows an example oI a Iour-processor network using this protocol.
Communication between nodes not physically connected requires multiple transmissions through intermediate nodes.
These protocols are deterministic between directly connected nodes. For indirectly connected nodes, latency can be
high.
For an embedded system with modest communication requirements, this might be a cost eIIective protocol (readily
available hardware and soItware Irom mature technology). For demanding applications, nodes that handle a lot oI
11/4/11 Communication Protocols for Embedded Systems
3/9 www.ece.cmu.edu/koopman/protsrvy/protsrvy.html
pass-through traIIic can become swamped, prohibiting use oI low-cost nodes in a large system. Sometimes, this type
oI protocol is combined with a more complex communication system to provide backward compatibility to older
systems or to allow simple remote modem access to the system (e.g., BACnet). This type oI protocol is used by the
X.25 public network standard (network services oIIered by telephone companies) and IBM's System Network
Architecture (SNA) |2|.
Figure 1: An eample netork using connection oriented protocols
Polling
Polling is one oI the more popular protocols Ior embedded systems because oI its simplicity and determinacy. In this
protocol, a centrally assigned master periodically polls (by sending a polling message) the slave nodes, giving them
explicit permission to transmit on the network.
Figure 2: Master node sequentially polling slave nodes Ior inIormation
Figure 2 shows the polling order (dotted lines) oI a simple Iour-node bus network. The majority oI the protocol
soItware is stored in the master and the communication work oI slave nodes is minimal (thereIore, the network costs
tend to be smaller). This protocol is ideal Ior a centralized data acquisition system where peer-to-peer communication
and global prioritization are not required. However, in embedded systems we have worked with, the single-point-oI-
Iailure Irom the master node (or the cost oI installing redundant master hardware) is unacceptable. Additionally, the
polling process consumes considerable bandwidth regardless oI network load (poor eIIiciency). These protocols have
been standardized by the military (MIL-STD-1553B) Ior aircraIt subsystem communications. Some variants oI this
protocol allow inter-slave communication through the master as well as improved robustness by using multiple masters
(e.g., ProIibus).
Time Diiion Mliple Acce (TDMA)
TDMA is heavily used in satellite communications |3|, but is applicable to local area networks as well. In this protocol,
11/4/11 Communication Protocols for Embedded Systems
4/9 www.ece.cmu.edu/koopman/protsrvy/protsrvy.html
a e ae badca a fae c iga befe each d f eage chie cc f a he
de. Afe he c, each de ai dig i ie acaed ie ice a i Fige 3. Peface i iia
ig, b ih geae efficiec a hea ad de eiiai f idiida ig eage. C f ae
de ae geae ih TDMA ha ih ig, becae each ae de hae a abe ie bae eae
ice. A addiia eae f TDMA i he eed f fied-egh eage fi i ie ice. I e TDMA
aiai, ed ice ae caed b aci ageee ag de. Tie-baed c hae bee a i
aeace aicai. F eae, DATAC (Digia A Teia Acce Cicai) i beig ed
b NASA ad Beig.
Fige 3: Time Slice of TDMA poocol
Tke Rig
I a Te Rig e, he de ae ceced i a ig-ie ce ig i--i i a h i Fige
4. A ecia e iga i aed f de de ad he ig. Whe a de ha ehig ed, i
he e cicai, ed i eage a he a ad he ig, ad he ae he e . Sice -cae
e aiig ie ca eai be cacaed, hi c i deeiiic. Ude igh affic, Te Rig ha deae
e aig ehead. Hee, he c ide efficie hgh de hea affic cdii ice ide
e aig i iiied. A fee ieeai aeg i hae a e-bi dea a each de, a e ca
ii a de i N+T bi ie, hee N i he be f de ad T i he be f bi i he e. Gba
iiiai i accihed b aeig he ii fied f he e a i ii he de. Thi fied eabe he
de ih a highe ii ed eage he e. Iiiaiai f he e eage, ad deeci f
accidea dicaed e add cei ad c he c. A bea i he cabe a faied de
diabig he eie e i a c cce f a e. Cee, de ba hadae ad da ig
ae ed adde hi cce a addiia c. Becae he ig ceci heee ae i--i, i i
e ied f fibe ic. Cee, a LAN ad Wide Aea Ne (WAN) ae ig hi e f
c. F eae, FDDI (Fibe Diibed Daa Ieface) e da ce-aig ig achiee highe
eiabii ha b a gie.
11/4/11 Communication Protocols for Embedded Systems
5/9 www.ece.cmu.edu/koopman/protsrvy/protsrvy.html
Figure 4: Token passing in the Token Ring networks
Token Bus
The operation of a Token Bus is ver similar to a Token Ring -- a token is passed from node to node in a virtual ring
as in Figure 5. The holder of the token has the access to the network. Like Token Ring, Token Bus works well under
heav traffic with a high degree of determinac. However, Token Bus broadcasts the message simultaneousl to all
nodes instead of passing it bit-b-bit along a phsical ring. The minimum time for a token to traverse the logical ring of
nodes is thus N*T bit times instead of N+T bit times as in token ring (because there is no parallelism in the
connections). This makes global prioritiation of messages largel impractical.
Unlike unidirectional Token Ring, a break in the cable or a failed node does not necessaril disable the entire network.
A length reconfiguration process, where each node identifies its neighbors, is used to maintain the virtual ring when
nodes are added or deleted from the network. Because bus-like topologies are well suited for manufacturing plants,
MAP, Manufacturing Automation Protocol, adopted this protocol. Additionall, ARCnet [4], Attached Resource
Computer Network, uses this protocol for LAN connectivit and process control. Adaptive Networks' PLC-192
power line carrier chip uses a hbrid Token Bus protocol: under light traffic, nodes dnamicall join and leave from the
logical ring; under heav traffic, all nodes join the ring to maintain stabilit.
Fige 5: Token paing in Token B poocol
Binar Countdown
In Binar Countdown, also known as the Bit Dominance protocol, all nodes wait for an idle channel before transmitting
a messages. Competing nodes (transmitting simultaneousl) resolve contention b broadcasting a signal based on their
unique node identification value. The transmission medium must have the characteristic that one value (sa, a "1")
overrides the opposite value (a "0"). During this transmission, a node drops out of the competition if it detects a
dominant signal opposite to its own as shown in Figure 6. Thus, if a "1" signal is dominant, the highest numbered
transmitting node will win the competition and gains ownership of the channel.
11/4/11 Communication Protocols for Embedded Systems
6/9 www.ece.cmu.edu/koopman/protsrvy/protsrvy.html
Figure 6: Arbitration in Binar Countdown Protocols
Global prioritiation can be achieved b arbitrating over message ID values rather than the node IDs . Since the
arbitration is part of the message, this protocol has good throughput and high efficienc. Additionall, the protocol is
more robust because node configuration (transmission order) is not required and inactive nodes are ignored. However,
since all messages are prioritied, there is no simple wa to guarantee equall fair access among all nodes under heavil
loaded conditions. Also, some transmission techniques (such as current-mode transformer coupling commonl used in
high-noise environments) aren't compatible with the bit dominance requirement. Using this protocol, Bosch developed
the Controller Area Network (CAN[5]) specification for automotive applications. The Societ of Automotive
Engineers standard SAE J-1850 also uses this protocol.
Carrier Sense Multiple Access ith Collision Detection (CSMA/CD)
CSMA/CD has been widel researched with a large number of published variations[2]. In the simplest case, a node
waits for the network to go idle before transmission (as in binar countdown). If multiple stations transmit almost
simultaneousl (within a round-trip transmission dela on the network), the messages collide as in Figure 7. The nodes
must detect this collision, and resolve it b waiting for a random time before retring.
Figure 7: Collisions in CSMA/CD networks
The ke advantage to this protocol is that in principle it supports an unlimited number of nodes that don't require pre-
allocated slots or inclusion in token passing activities. Thus, CSMA/CD allows the nodes to enter and leave the
11/4/11 Communication Protocols for Embedded Systems
7/9 www.ece.cmu.edu/koopman/protsrvy/protsrvy.html
network without requiring network initialization and conIiguration. For light traIIic conditions, overhead is very small.
However, under heavy traIIic the overhead is unbounded due to high probability oI repeated collisions. Consequently,
this protocol has poor determinacy and low eIIiciency. Furthermore, detecting collisions may require analog circuitry
that adds to the system expense. In Iact, iI the network environment is very noisy or the wiring runs are long and poor
quality, collision detection may not work at all. The popular Ethernet protocol used in workstation LANs is based on
this protocol.
Caie Sene Mliple Acce ih Colliion Aoidance (CSMA/CA)
Many researchers have developed hybrid protocols that combine the light traIIic eIIiciency oI CSMA/CD with the
heavy traIIic eIIiciency oI token-based protocols. The resulting protocols are oIten called CSMA/CA, or collision
avoidance algorithms. As in CSMA/CD, nodes transmit aIter detecting an idle channel. However, iI two or more
stations collide, a jam signal is sent on the network to notiIy all nodes oI collision, synchronize clocks, and start
contention time slots. Each contention time slot, typically just over a network round-trip propagation delay time, is
assigned to a particular station. Each station is allowed to initiate transmission during its contention slot. Figure 8 shows
a slot progression Ior a three node network. In this example, transmitter 2 and 3 collide and initiate a jam. Contention
slots Iollow the jam signal. Since processor one has nothing to send, slot1 goes idle. Transmitter two starts sending its
message during slot2. Other stations detect the message, and stop the slot progression. AIter end oI the message, all
nodes initiate new contention slots. However, to ensure Iairness and determinacy, the slots are rotated (change
positions) aIter each transmission. Additionally, the pslots, or the priority slots can precede each slot progression to
support global prioritization Ior high priority messages. The network returns to an idle state when all the slots go
unused.
Fige 8: Slo pogeion in CSMA/CA poocol
The contention slots in CSMA/CA protocol help in avoiding collisions. In general, there are two distinct variations oI
CSMA/CA protocols. II the number oI slots equals the number oI stations, the protocol is called Reservation CSMA
or RCSMA. The RCSMA variation works eIIiciently under all traIIic conditions |6|. However, because oI the one-to-
one relation oI the node to the slot, RCSMA is not practical Ior a network with a large number oI nodes. In another
variation, the number oI slots are less than the number oI stations and the slot assignments are randomly allocated to
minimize collisions. Echelon's LON |7| (Local Operating Network) uses the latter variation and dynamically varies the
number oI slots based on expected traIIic prediction. Unlike CSMA/CD, there are ways to eliminate the need Ior
collision detection hardware, such as by sending dummy messages that keep slots going in the absence oI network
traIIic.
MEDIA ACCESS PROTOCOL SUMMARY AND
11/4/11 Communication Protocols for Embedded Systems
8/9 www.ece.cmu.edu/koopman/protsrvy/protsrvy.html
ADEOFF
In the above discussions we have described the major media access protocols and noted clear diIIerences. Table 1
summarizes some oI the common traits and our assessment oI their strengths and weaknesses Ior embedded real-time
applications. The important points to take into consideration when evaluating alternatives are:
Polling, TDMA, and connection-based protocols are simple, but may not provide suIIicient Ilexibility Ior
advanced systems.
Token-based protocols are predictable, but can have high overhead and require complex soItware to maintain
robustness.
Binary count-down protocols rely heavily on the bit dominance characteristics oI the physical medium.
CSMA/CD is a poor choice Ior hard real-time systems with heavy traIIic.
Table 1: Media Access Tradeoffs
For our embedded systems, we have Iound that CSMA/CA, and in particular Reservation CSMA is a good choice.
While your application will no doubt have characteristics that are somewhat diIIerent than ours, this article's discussion
oI the special considerations and media access protocol strengths and weaknesses should allow you to select the best
protocol to match your needs. We believe the electronic contents oI embedded systems will continue to grow, and
communication networks provide strong Ioundation Ior supporting this growth.
EFEENCE
[1] Upender, B. P. and Koopman, P. J., Embedded Communication Protocol Options, Proceedings of the
Embedded Sstems Conference, San Jose, CA, October 3-5, 1993.
[2] Tanenbaum, A. S., Computer Networks, 2nd ed., Prentice-Hall, Englewood Cliffs, NJ, 1989.
[3] Stallings, W. S., Data and Computer Communications, 3rd ed., Macmillan, New York, 1991.
11/4/11 Communication Protocols for Embedded Systems
9/9 www.ece.cmu.edu/koopman/protsrvy/protsrvy.html
[4] Hoswell, Katherine S. and Thomas, George M., ARCnet Factor LAN premier, Contemporar Control
Sstems Inc., Second Printing, Downers Grove, Illinois, 1988.
[5] Bosch, CAN Specification, ver. 2.0, Robert Bosch GmbH, Stuttgart, 1991.
[6] Chen and Li, Reservation CSMA/CD: A Multiple Access Protocol for LANs, IEEE Journal on Selected
Areas in Communications, Februar 1989.
[7] Enhanced Media Access Control with Echelon's LonTalk Protocol, LonWorks Engineering Bulletin,
Echelon Corp., August 1991.
AHOR INFORMAION
Bhaga Upende i an aociae eeach enginee a Unied Technologie Reeach Cene. Cenl, he i eploing
noel achiece and ppoing poocol fo diibed embedded em. He hold a BS in elecical engineeing
fom he Uniei of Connecic and an MS in elecical engineeing fom Conell Uniei. He can be conaced
ia email a [email protected]
Philip Koopman a a pincipal eeach enginee a Unied Technologie Reeach Cene. He deigned and
ealaed achiece and commnicaion poocol fo a aie of embedded applicaion. He peiol oked a
an embedded CPU achiec and a Na bmaine office. Koopman hold a BS and MS in compe engineeing
fom Renelae Polechnic Inie and a Ph.D. in compe engineeing fom Canegie Mellon Uniei. He ma
no be eached ia e-mail a [email protected]

Philip Koopman: [email protected]