`SHERIDAN LIBRARIES &
`UNIVERSITY MUSEUMS
`
`DECLARATION OF JON MEARS
`
`I, Jon Mears, declare as follows:
`
`1.
`
`I am a staff member of the Milton S. Eisenhower Library, which is located at
`
`Johns Hopkins University. I have personal knowledge of the facts listed below.
`
`2.
`
`The Milton S. Eisenhower Library is open to the public. Any member of the
`
`public may enter the Milton S. Eisenhower Library and view the periodicals in the library' s
`
`collection.
`
`3.
`
`The document attached as Exhibit A is a scan of a portion of a periodical that I
`
`located in the Milson S. Eisenhower Library' s collection of periodicals. Specifically, Exhibit A
`
`shows the article titled "Communication Protocols for Embedded Systems" as in appears in the
`
`November 1994 issue of Embedded Systems Programming. This is volume 7, issue 11 ofthis
`
`publication.
`
`4.
`
`The stamp on the back cover of the November 1994 issue of Embedded Systems
`
`Programming reads "OCT 28 1994." It is the regular practice of the Milton S. Eisenhower
`
`Library to stamp periodicals with the date the periodical is added to the library' s catalog. Once a
`
`periodical is in the library' s catalog, it is made available in the library for viewing by any visitor
`
`ofthe library.
`
`I declare under penalty of perjury that the foregoing is true and correct.
`
`Dated: March 11 , 2014
`
`Office of the Dean
`3400 N. Charles Street Ba ltimore, MD 21218 410-516-8328 Fax 410-516-5080 www.library.jhu.edu
`
`Exhibit 1218 01/12
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`EXHIBIT A
`
`EXHIBIT A
`
`Exhibit 1218 02/12
`
`Exhibit 1218 02/12
`
`
`
`S6'17$ "O"N":l S6'£$ ·s·n ~ ~ tJ38~nN
`NOI1\f:Jil8nd N\fV\1338::1 tJ3lliVII \f 1766~
`
`1 .. 1.1 ... 11 •• 1.1 ••• 111 •• 1 .. 11 •• 1
`BALTIMORE, MD 21218
`JOHNS HOPKINS UNIVERSITY
`SERIALS DEPT
`MIL TONS EISENHOWER LIBRARY
`6 AA
`16
`9437
`#091 00007041220# 9411 NOV94
`#BXNBFTW··· ............. MIXED STATES
`
`Exhibit 1218 03/12
`
`
`
`VOL. 7 NO. 11 NOVEMBER 1994
`
`able of Contents
`
`2 Ada for Space Applications
`
`criticisms behind and finding acceptance in a
`of embedded applications. This case study
`the trials and triumphs of a satellite design
`'· decision to shift to Ada.
`
`8 Cruising with Ada
`
`DO-WHILE JONES. Too many developers Jet their
`dictate their designs . In this system design mani(cid:173)
`Jones looks at the dangers of inappropriate design
`logies and the advantages of Ada as a proto-
`tool for a typical microcontroller application.
`
`Communication Protocols for
`Embedded Systems
`BHARGAV UPENDER AND PHILIP KOOPMAN.
`networking architectures were designed without
`or real-time concerns in mind. Here's an
`of the tradeoffs in choosing different embed(cid:173)
`networking protocols.
`
`Containers and Templates
`
`BRUCE ECKEL. Container classes are quite useful.
`them, however, often requires template
`. In keeping with our emphasis on "under the
`details, this month's introduction to C++ contain(cid:173)
`is also an exploration in the use of templates.
`
`I'
`
`I
`
`111
`
`ON THE COVER:
`T f your geosynchro(cid:173)
`nous service cal ls
`are getting too
`expensive, try
`shifting to Ada.
`Cover by
`Rupert Adley.
`
`COLUMNS+
`DEPARTMENTS
`7 #include
`
`Dangerous Curves
`
`9 Real-Time
`
`Competitive Urges
`by Tyler Sperry
`
`82 Embedded Marketplace
`
`88 Advertiser Index
`
`89 Break Points
`
`I Consultant, Part II
`by Jack G. Ganssle
`
`93 State of the Art
`
`What Happens Next?
`by P.J. Plauger
`
`SYSTEMS PROGRAMMING (ISSN 1040-3272) is published monthly by Miller Freeman Inc., 600 Harrison St., San Francisco, CA 94107, (41 5) 905-2200. Please direct advertising and
`ies to this address. SU BSCRIPTION RATE for the United States is $49.95 for 12 issues. Canadian/Mexican orders must be acco mpanied by payment in U.S. funds with additional postage
`. All other foreign subscriptions must be prepaid in U.S. funds wi th additional postage ofS 15 per year for surface mail and $40 per year for ainnail. POSTMASTER: All subscription orders,
`address changes should be sent to EMBEDDED SYSTEMS PROGRAMM ING, P.O. Box 420046, Palm Coast, FL 32142-0046. For customer service, telephone toll-free (800) 829-5537.
`four to six weeks for change of address to take effect. Second-class postage is paid at San Francisco, CA and additional mailing offices. EMBEDDED SYSTEMS PROGRAMM ING is a
`owned by the parent company, Miller Freeman Inc. All material published in EMBED DED SYSTEMS PROGRAMMING is copyright <!;) 1994 by Miller Freeman Inc. All rights
`m of materi al appea ri ng in EMBEDDED SYSTEMS PROGRAMMING is forbidden without pennission. EMBEDDED SYSTEMS PROGRAMM ING is avai lable on microfilm/fiche
`Microfilms International, 300 N. Zeeb Rd., Ann Arbor, Ml 48106, (313) 761-4700.
`
`NOVEMBER 1994 EMBEDDED SYSTEMS PROGRAMMING 3
`
`~'
`
`Exhibit 1218 04/12
`
`
`
`Communication
`Protocols for
`Embedded Systems
`
`There's more to connecting multiple CPUs
`than just stringing wires or cable. Your
`choice of network protocol, in particular,
`determine system performance.
`
`T he past few years have
`
`seen a growing trend to
`dramatically increase the
`embedded
`electronics
`content of automobiles,
`elevators, building climate control sys(cid:173)
`tems, jet aircraft engines, and other tra(cid:173)
`ditionally electro-mechanically con(cid:173)
`tro lled systems. In many large systems,
`this increasing electronics content is
`accompanied by a proliferation of sub(cid:173)
`systems with separate CPUs.
`The
`increase
`in
`the number of
`processors in a system is often driven
`by computation and I/0 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 flexibility
`through
`"smart sensors" and "smart actuators."
`Whatever the reasons, once there is
`more than one CPU in a system, there
`must be some means of communica(cid:173)
`tion to coordinate action.
`While some high-end embedded
`systems communicate over a YME
`backplane or similar arrangement, the
`embedded systems we ' re working on
`use physically distributed CPUs
`involving some sort of local area net(cid:173)
`work (LAN), also called a multiplexed
`network or a communication bus. At
`the heart of the LAN is the media
`access protocol, which picks the next
`
`NOVEMBER 1994
`
`work medium, typically a wire.
`or RF frequency.
`In this article, we will discuss
`special considerations for
`real-time embedded systems, and
`at several media access protocols
`demonstrate fundamentally
`ways of accessing the shared
`The protocols are:
`protocols, polling, time division
`pie access (TDMA), token ring.
`bus, binary countdown, carrier
`multiple access with collision
`tion (CSMA/CD), and carrier
`multiple access with collision
`ance (CSMA/CA). For each of
`we will evaluate the strengths
`weaknesses against special
`tions. A protocol tradeoff chart
`enab le you to se lect a protocol to
`your needs. While no protocol is
`feet for all purposes, a variation
`CSMA/CA offers the most
`for many embedded systems 1
`
`SPECIAL CONSIDERATIONS
`
`I n practice, we have found
`
`real-time
`embedded
`require high efficiency,
`IStic latency, operational
`configuration flexibility, and low
`per node.
`Because cost limits the
`bandwidth available to many
`
`Exhibit 1218 05/12
`
`
`
`tions. protocol efficiency (message bits
`delivered compared to raw network
`bandwidth) is ve ry important. The
`embedded systems we have studied are
`characterized by a predominance of
`short, periodic messages. So, an obvi(cid:173)
`ous optimi zation is to reduce overhead
`bits used for message packaging and
`routing. (It is not unusual fo r eight bits
`of data to be packed in a message that
`is32 or even 64 bits long.)
`Once message overhead has been
`reduced as much as possible, medi a
`access overhead must be reduced. For
`the most part, this is accomplished by
`minimizing the network bandwidth
`consumed by arbi tration (such as pass(cid:173)
`mg a tok.-n or resolving collision con(cid:173)
`flict). Because worst-case behavior is
`typically important, efficiency should
`be evaluated for both light and heavy
`traffic. For example, CSMA/CD (often
`used in workstation LANs) is highly
`efficient fo r light traffic but gives poor
`performance if heavily loaded, while
`token bus protocols have the reverse
`properties.
`Detenninacy, or the ability to calcu(cid:173)
`late worst-case response
`time,
`is
`important fo r meeting the real-time
`constraints of many embedded contro l
`applications. A prioritizati on capabili(cid:173)
`ty is usuall y included in systems to
`improve determinacy of messages for
`time-critical tasks such as excepti on
`handling and hi gh-speed loop control.
`Priorities can be assigned by node
`number or message type. Additionall y,
`protocols can support local or global
`priority mechanisms. In loca l prioriti(cid:173)
`zation, each node gets a turn at the net(cid:173)
`work in sequence and sends its hi ghest
`priority queued message (thus poten(cid:173)
`tially forc ing a very hi gh-priori ty mes(cid:173)
`sage to wa it fo r other nodes to have
`their turns fi rst). ln global prioritiza(cid:173)
`tion, the highest priori ty message in the
`entire system is always transmitted
`first. Thi s mechanism, which is fun da(cid:173)
`mentally enabled by the media access
`protocol, is hi ghl y desirable for many
`.afety-critical app licati ons.
`Many appl ications require robust
`
`Because worst-
`case behavior is
`typically
`important,
`efficiency should
`be evaluated for
`both light and
`heavy traffic.
`
`operation under extreme conditions.
`We call a protocol robust if it can
`quickly detect and recover from errors
`(duplicate or lost tokens, fo r example),
`added nodes, and deleted nodes. In
`some systems, it's important to qui ck(cid:173)
`ly recover from a reset or power glitch
`that forces a restatt of the network.
`Vari ed operating environments may
`dictate use of a media access protocol
`that is flexible in supporting multiple
`medi a and mixed topologies. Portions
`of a system may require expensive
`fi ber in noisy envi ronments, while
`other portions can tolerate low-cost
`twisted pair wires in benign environ(cid:173)
`ments. A bus topology may be opti(cid:173)
`mum for wires, but a ring or star topol(cid:173)
`ogy may be needed fo r fi ber.
`A vital considerati on is the cost per
`node. In this article, the order of the
`media access discussion progresses
`from very simple to complex, high(cid:173)
`performance protocols. Simple proto(cid:173)
`cols require less hardware and soft(cid:173)
`ware resources and are therefore likely
`to be less expensive. For extremely
`cost-sensitive high- vo lume applica(cid:173)
`tions, these protocols are good candi(cid:173)
`dates. However, fo r growing applica(cid:173)
`tions, more adva nced protocols pro- .
`vide a stronger foundati on. In general,
`costs are decreasing over time due to
`
`NOVEMBER 1994
`
`Js
`
`will
`
`ared net(cid:173)
`re, fiber,
`
`;cuss the
`tworking
`and look
`cols that
`different
`medium.
`-oriented
`on multi(cid:173)
`,ng, token
`·ier sense
`on detec(cid:173)
`·ier sense
`Dn avoid-
`of these,
`tgths and
`~on s idera
`chart will
`)CO( to fit
`~ol is per(cid:173)
`ri ation of
`versatility
`I
`
`:o und that
`networks
`determin(cid:173)
`obustness,
`d low cost
`
`e network
`:1y applica-
`
`Exhibit 1218 06/12
`
`
`
`Communication Protocols
`
`advances in IC manufactu ri ng technol(cid:173)
`ogy and the increasing avai lab ility of
`off-the-shelf protocols. Conseq uently,
`we envis ion advanced cost-effective
`protocols used in many embedded
`applications.
`
`MEDIA ACCESS PROTOCOLS
`
`N ow that we have a fee l for the
`
`issues in embedded networks,
`let' s examine various com(cid:173)
`monly ava ilable med ia access proto(cid:173)
`cols. Wh ile many variat ions and com(cid:173)
`binations are poss ible, we ' ll discuss
`the plain vers ions of each protocol.
`Before LANs became popul ar, con(cid:173)
`nection-oriented protoco ls were heavi(cid:173)
`ly used to connect remote termina ls to
`mainframes. These protocols suppmt
`only two nodes per phys ica l transmi s(cid:173)
`sion med ium and are typicall y con(cid:173)
`nected via modem with serial li nes.
`Figure l shows an examp le of a fo ur(cid:173)
`processor network using thi s protoco l.
`Comm uni cati on betwee n nodes not
`physicall y connected requi res mu ltipl e
`transmi ss ions
`thro ugh
`in termedi ate
`nodes. These protoco ls are deteimin is(cid:173)
`tic between directl y connected nodes.
`For ind irectly conn ected nodes, latency
`can be hi gh.
`For an embedded system w ith mod(cid:173)
`est communicati on requirements, this
`mi ght be a cost-effective p rotocol
`(readil y ava ilable hardware and soft(cid:173)
`ware from mature technology). For
`demanding application s, nodes that
`handle a lot of pass-through traffic can
`become swamped, prohibiting use of
`low-cost nodes
`in a large system.
`Sometimes, thi s type of protocol is
`combined with a more compl ex com(cid:173)
`munication system to provide back(cid:173)
`ward compatibi lity to older systems or
`to allow simple remote modem access
`to the system (such as BACnet) . Thi s
`type of protocol is used by the X.25
`public network standard (network ser(cid:173)
`vices offered by te lephone companies)
`and IBM' s system network archi tec(cid:173)
`ture (SNA).2
`Po lling is one of the more popul ar
`protocols
`for embedded
`systems
`because of its simplicity and determi-
`
`nacy. In thi s protocol, a centra ll y
`assigned master periodicall y sends a
`polling message to the slave nodes,
`giving th em exp lic it permission to
`transm it on the network.
`Figure 2 shows the poll ing order
`(dotted lines) of a simple four-node
`bus network. The majori ty of the pro(cid:173)
`tocol software is stored in the master
`and the communicati on work of slave
`nodes is mi nimal (therefore, the net(cid:173)
`work costs tend to be smaller). Thi s
`protocol is idea l for a centra lized data(cid:173)
`acq ui sition system where peer-to-peer
`communication and global prioritiza(cid:173)
`tion are not required. However, the sin(cid:173)
`gle-poi nt-of-failure fro m the master
`node (or the cost of install ing redun(cid:173)
`dan t master hardware) is often unac(cid:173)
`ceptabl e. A dd itiona lly, the po ll ing
`process consumes considerable band(cid:173)
`width regardl ess of network load (poor
`
`effi ciency). These protocols
`standardi zed by the military
`STD-l 553B) fo r aircraft
`communi cati ons. Some
`protocol all ow inter-slave
`tion through the master as
`improved robustness by using
`masters (as does Profibus).
`
`T ime di vision multiple
`
`(TDMA) is heavily
`satell ite commu1wca•nm> U1
`applicable to LANs as well.'
`protocol, a network master
`a frame sync signal before
`of messages to synchronize
`all the nodes. After the sync.
`transmits during its uniquely
`tim e sli ce, as shown in
`Perfo rmance is similar to
`
`FIGURE 1
`An example network using connection-oriented protocols.
`
`CPUI
`
`CPU2
`
`FIGURE 2
`Master node sequentially polling slave nodes for information ..
`
`Bus
`
`Slave!
`
`Slave2
`
`50 EMBEDDED SYSTEMS PROGRAMMING N O VEM 8 ER 1994
`
`Exhibit 1218 07/12
`
`
`
`Communication Protocols
`
`optics. So, many LANs and wide area
`networks (WAN s) are moving to this
`type of protocol. For example, fiber
`di stributed data interface (FDDl) uses
`dual counter-rotating rings to achieve
`hi g her reliability
`than bus or sta r
`topologies.
`
`TOKEN BUS
`
`T he operation of a token bus is
`
`very 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 heavy traffic
`with a high degree of determinacy.
`
`However, token bus broadcasts
`message simultaneously to all
`instead of passing it bit-by-bit
`physical ring. The minimum time
`token to traverse the logical ring
`nodes is thus N*T bit times instead
`N + T bit times as in token ring
`there is no parallelism in the
`tions) . This makes global nnr•ntiJ·~hM
`of messages large ly impractical.
`U nlike unidirectional token ring.
`break in the cab le or a failed node
`not necessarily disable the entire
`work. A
`lengthy
`recontionr•t•i""'
`process, where each node identifies
`nei ghbors, is used to maintain the
`tual ring when nodes are added
`
`FIGURE 3
`The time slices ofTDMA protocols.
`
`Master
`
`FIGURE 4
`Token passing in the token ring networks.
`
`due to elimination of individual polling
`messages. Costs for slave nodes are
`greater with TDMA than with polling,
`because each slave node must have a
`stable time ba e to measure slices. An
`additional weakness for TDMA is the
`need for fixed-length messages to fit
`into time slices. ln some TDMA varia(cid:173)
`tions, unused slices are truncated by
`tacit agreement among nodes. Time(cid:173)
`based protocols have been popular in
`aerospace applications. For example,
`digita l autonomous terminal access
`communications (DATA C) is being
`used by NASA and Boeing.
`In a token ring network, the nodes
`are connected in a ring-like structw-e
`using point-to-point links as shown in
`Figure 4 . A special token signal is
`passed from node to node around the
`ring. When a node has something to
`send , it stops the token circulation,
`se nds its message all the way around
`the ring, and passes the token on. Since
`worst-case token waiting time can eas(cid:173)
`ily be calculated, thi s protocol is deter(cid:173)
`mini stic. Under light traffic, token ring
`has moderate token passing overhead.
`However, the protocol provides effi(cid:173)
`cient throughput under heavy traffic
`conditions since idle token passing is
`minimized.
`A frequent implementation strategy
`is to have a one-bit delay at each node,
`so a token can visit all nodes in N+ T
`bit times, where N is the number of
`nodes and Tis the number of bits in the
`token. Global prioritization is accom(cid:173)
`plished by altering the priority field of
`the token as it visits the nodes. This
`field enables on ly the nodes with a
`high priority to send messages on the
`network. Initialization of the token
`message and detection of accidentally
`duplicated or lost tokens adds com(cid:173)
`plexity and cost to the protocol.
`A break in the cable or a failed node
`di sabling the entire network is a com(cid:173)
`mon
`concern
`for many
`users.
`Consequently, node bypass hardware
`and dual rings are used to address thi s
`concern at additional cost. Because the
`ring connections them se lves are point(cid:173)
`to-point,
`it is well suited for fiber
`
`52 EMBEDDED SYSTEMS PROGRAMMING NOVEMBER 1994
`
`Exhibit 1218 08/12
`
`
`
`Communication Protocols
`
`deleted from the network. Because
`bus-like topologies are well suited for
`manufacturing plants, manufacturing
`automation protocol (MAP) adopted
`this protocol. Additionally, attached
`resource computer network (ARCnet)4
`uses this protocol for LAN connectivi(cid:173)
`ty and process control. Adaptive
`Networks' PLC- 192 power line carrier
`chip uses a hybrid token bus protocol:
`under light traffic, nodes dynamically
`join and leave from the logical ring(cid:173)
`under heavy traffic, all nodes join the
`ring to maintain stability.
`In binary countdown, also known as
`the bit dominance protocol, all nodes
`wait for an idle channel before trans(cid:173)
`mitting a message. Competing nodes
`(transm itting simultaneously) resolve
`contention by broadcasting a signal
`based on their unique node identifica(cid:173)
`tion value. The transmission medium
`must have the characteristic that one
`value (say, a "1") overrides the oppo(cid:173)
`site value (a "0"). During this trans(cid:173)
`mission, a node drops out of the com(cid:173)
`petition 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
`wins the competition and gains owner(cid:173)
`ship of the channel.
`be
`can
`prioritization
`Global
`achieved by arbitrating over message
`ID values rather than the node IDs.
`Since the arbitration is pa11 of themes(cid:173)
`sage, this protocol has good throughput
`and high efficiency. Additionally, the
`protocol is more robust because node
`configuration (transmission order) is
`not required, and inactive nodes are
`ignored. However, since all messages
`are prioritized, there is no simple way
`to guarantee equally fair access among
`all nodes under heavily loaded condi(cid:173)
`tions. Also, some transmission tech(cid:173)
`niques (such as current-mode trans(cid:173)
`fom1er coupling commonly used in
`high-noise environments) aren't com(cid:173)
`patible with the bit dominance require(cid:173)
`this protocol, Bosch
`ment. Using
`developed the controller area network
`(CAN) specification for automotive
`applications .s
`The
`Society
`of
`
`54 EMBEDDED SYSTEMS PROGRAMMING NOVEMBER 1994
`
`Bit Slices
`
`Automotive Engineers standard SAE
`J-1850 also uses this protocol.
`
`CARRIER SENSE MULTIPLE ACCESS
`
`C arrier sense multiple access
`
`detection
`collision
`with
`(CSMA/CD) has been widely
`researched with a large number of pub(cid:173)
`lished variations. ln the simplest case,
`a node waits for the network to go idle
`before
`transmission (as
`in binary
`countdown). Tf multiple stations trans(cid:173)
`mit almost simultaneously (within a
`round-trip transmission delay on the
`network), the messages collide, as in
`Figure 7. The nodes must detect this
`collision and resolve it by waiting for a
`random time before retrying.
`The key advantage to this protocol is
`that, in principle, it suppo11s an unlim(cid:173)
`ited number of nodes that don ' t require
`preallocated slots or inclusion in token
`
`passing activities.
`nodes to enter and leave the
`without requiring network
`tion and configuration. For light
`conditions, overhead is very small.
`However, under heavy traffic,
`overhead is unbounded due to
`probability of repeated collisions.
`Consequently, this protocol has pooc
`determinacy and
`low
`efficiency
`Furthermore, detecting collisions may
`require analog circuitry, adding to the
`system expense. In fact, if the network
`environment is very noisy or the
`wiring runs are long and of poor qual~
`ty, collision detection may not work a!
`all. The popular Ethernet protocol used
`in workstation LANs is based on this
`protocol.
`Many hybrid protocols combine the
`light traffic efficiency of CSMACD
`with the heavy traffic efficiency of
`
`FIGURE 5
`Token passing in token bus protocols.
`
`Token
`
`--..... -
`
`FIGURE 6
`Arbitration in binary countdown protocols.
`
`Node !D
`
`7
`MSB
`
`6
`
`Node 72
`(0 1001000) :
`
`0
`
`5
`
`0
`
`Node 71
`(01000 11 I) :
`
`0 !il 0
`
`4
`
`0
`
`0
`
`3
`
`2
`
`., '
`
`I 0
`
`'
`'
`'
`'
`'
`'
`'
`Node42
`'
`0
`0
`'
`'
`'
`(001010 10) : ~! !
`!Node 7{ loses hrre
`:
`,
`:Node 42 loses h¢re
`
`Exhibit 1218 09/12
`
`
`
`Communication Protocols
`
`token-based protocols. The resulting
`protocols are often called carrier sense
`multiple access with coli is ion avoid(cid:173)
`ance (CSMA/CA). As in CSMA/CD,
`nodes transmit after detecting an idle
`channel. However, if two or more sta(cid:173)
`tions collide, a jam signal is sent on the
`network to notify all nodes of collision,
`synchronize clocks, and start con(cid:173)
`tention 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 transmis(cid:173)
`sion during its contention slot. Figure 8
`shows a slot progression for a three
`node network. In this example, trans(cid:173)
`mitters 2 and 3 collide and initiate a
`jam. Contention slots follow the jam
`signal. Since processor I has nothing
`to send, slotl goes idle. Transmitter 2
`starts sending its message during slot2 .
`Other stations detect the message, and
`stop the slot progression.
`After the end of the message, all
`nodes initiate new contention slots.
`However, to ensure fairness and deter(cid:173)
`minacy, the slots are rotated (change
`positions) after each
`transmission.
`Additionally, the priority slots (pslots)
`can precede each slot progression to
`support global prioritization for high(cid:173)
`priority messages. The network returns
`to an idle state when all the slots go
`unused.
`The contention slots in CSMA/CA
`protocol help avoid collisions. In gen(cid:173)
`eral, there are two distinct variations of
`CSMA/CA protocols. If the number of
`slots equals the number of stations, the
`protocol is called reservation CSMA
`(RCSMA) . The RCSMA variation
`works efficiently under all traffic con(cid:173)
`ditions.6 However, because of the one(cid:173)
`to-one relation of the node to the slot,
`RCSMA is not practical for a network
`with a large number of nodes. In anoth(cid:173)
`er variation, the number of slots is less
`than the number of stations, and the
`slot assignments are randomly allocat(cid:173)
`ed to minimize collisions. Echelon's
`local operating network (LON) uses
`the latter variation and dynamically
`varies the number of slots based on
`
`FIGURE 7
`Collisions in CSMAICD networks.
`
`FIGURE 8
`Slot progression in CSMA ICA protocols.
`
`CPU!
`
`CPU2
`
`CPU3
`
`Bus
`
`CPU2 & 3
`Collide
`I
`
`Priority Slot
`
`Time
`
`expected traffic prediction .? Unlike
`CSMA/CD, there are ways to eliminate
`the need for collision detection hard(cid:173)
`ware, such as sending dummy mes(cid:173)
`sages that keep slots going in the
`absence of network traffic.
`
`PROTOCOL TRADEOFFS
`
`W e have describ.ed the major
`
`media access protocols and
`noted clear differences.
`Table 1 summarizes some of the com(cid:173)
`mon traits and our assessment of their
`strengths and weaknesses for embed(cid:173)
`ded real-time applications. The impor(cid:173)
`tant points to take into consideration
`when evaluating alternatives are:
`
`• Polling, TDMA, and connection-
`
`Collision
`
`based protocol s are simple, but
`not provide sufficient flexibility
`advanced systems.
`• Token-based protocols are
`dictable, but can have high
`and require complex software to
`tain robustness.
`• Binary count-down protocols
`heavily on the bit dominance
`teristics of the physical medium.
`• CSMA/CD is a poor choice for
`real-time
`systems with
`traffic.
`
`For our embedded systems. we
`found that CSMA/CA,
`RCSMA, is a good choice. While
`application will no doubt have
`teristics that are somewhat
`
`56 EMBEDDED SYSTEMS PROGRAMMING NOVEMBER 1994
`
`Exhibit 1218 10/12
`
`
`
`Replace Four
`Conventional PC/1 04
`Modules with
`One SuperXTn:.
`CMF8680 cpuModule™
`Embedded PC/XT Controller with
`Intelligent Power Management
`
`TABLE 1
`Media access tradeoffs.
`
`i'- Good
`- Ok
`~ Poor
`
`Connection
`
`Polling
`
`TDMA
`
`Token Ring
`
`Token Bus
`
`Binary Cnt.
`
`CSMA/CD
`
`CSMA/CA
`
`Efficiency Efficiency
`Priori-
`Deter-
`Light
`Heavy
`Traffic
`Traffic minacy tization
`i'-
`i'-
`i'-
`i'-
`i'-
`
`~
`~
`i'-
`
`i'-
`i'-
`i'-
`
`i'-
`+
`i'-
`i'-
`~
`i'-
`
`Robust-
`ness
`i'-
`~
`~
`
`i'-
`i'-
`i'-
`
`...
`-t
`-t
`
`-t
`...
`-t
`-t
`
`~
`~
`i'-
`
`~
`i'-
`
`i'-
`
`than ours, this article's discussion of
`the special considerations and media
`access protocol strengths and weak(cid:173)
`nesses should allow you to select the
`best protocol to match your needs. We
`believe the electronic contents of
`embedded systems will continue to
`grow, and communication networks
`provide strong foundation for support(cid:173)
`ing this growth. 1::..~~
`
`Bhargav Upender is an associate
`research
`engineer
`at United
`Technologies
`Research
`Center.
`Currently, he is exploring novel archi(cid:173)
`tectures and supporting protocols for
`distributed embedded systems. He
`holds a BS in electrical engineering
`ji-om the University of Connecticut and
`an MS in electrical engineering from
`Cornell University in New York. He
`can be contacted electronically at
`barg@utrc. utc. com.
`
`Philip Koopman
`is a principal
`research
`engineer
`at United
`Technologies Research Center. He
`currently designs and evaluates archi(cid:173)
`tectures and communication protocols
`for a variety of embedded applications.
`He has previously worked as an
`embedded CPU architect and a Navy
`submarine officer. Koopman holds a
`BS and MS in computer engineering
`from Rensselaer Polytechnic Institute
`
`and a PhD in computer
`from Carnegie Mellon Universi~·.
`may be reached electronicallr
`koopman@utrc. utc. com.
`
`REFERENCES
`I. Upender, B. P. and Koopman.
`J. ,
`Embedded
`Comm
`Protocol Options , San Jose,
`Proceedings of the Embedded
`Conference, October 1993.
`2. Tanenbaum, A. S.,
`Networks, 2nd ed., Englewood
`NJ: Prentice-Hall, 1989.
`3. Stallings, W. S. ,
`Computer Communications,
`New York: Macmillan, 1991.
`4. Hoswell , Katherine
`Thomas, George M. , ARCnet F
`LAN Primer, Second
`Printing.
`Downers
`Grove,
`Illinois
`Contemporary Control Systems Inc.,
`1988.
`5. Bosch, CAN Specification. ver
`2.0, Robert Bosch GmbH, Stuttgart
`1991 .
`6. Chen and Li, Reserration
`CSMA/CD: A Multiple Access
`Protocol for LANs, IEEE Journal oo
`Selected Areas in Communications,
`February 1989.
`7. Enhanced Media Access ContrrJ
`with Echelon's Lon Talk Protocol,
`Lon Works Engineering Bulletin,
`Echelon Corp. , August 1991.
`
`• PC/XT compatibility with 286 emulation
`• 14 MHz, 16-bit 8086 CPU
`• +5V only; 1.6W at 14.3 MHz, 1 W at 7.2 MHz
`• Intelligent sleep modes, 0.1 Win Suspend
`• ROM-DOS and RTD enhanced BIOS
`• Compatible with MS-DOS & real-time
`operating systems
`• 1M boatable Solid State Disk & free software
`• 4K-bit configuration EEPROM (2K for user)
`• 2M on-board DRAM
`• IDE & floppy interfaces
`• CGA CRT/LCD controller
`• Two RS-232 ports, one RS-485 port
`• Parallel , XT keyboard & speaker ports
`• Optional X-Y keypad scanning/PCMCIA
`interface
`• Watchdog timer & real-time clock
`
`Expand This Or Any PC/1 04 System
`with the
`CM1 06 Supe r VGA
`Controller utilityModule TM
`• Mono/color STN & TFT flat panel support
`• Simultaneous CRT & LCD operation
`• Resolution to 1024 x 768 pixels I $223 1
`• Displays up to 256 colors
`
`100 "''·
`
`Speed Product Development with the
`DS8680 Development System
`Your DS8680 includes the CMF8680, CM1 02
`keypad scanning/PCMCIA, CM1 04 with 1.8"
`85MB hard drive , CM106 SVGA controller &
`DM5406 12-bit, 100kHz dataModule™ in an
`enclosure with external power supply, 3.5"
`floppy, keyboard , keypad , TB50 terminal
`board, SIGNAL"VIEW™, SIGNAL"MATHTM ,
`MS-DOS, SSD software & rtdlinxrM for just
`$2950.
`For more information on our PC/ 104 and
`ISA bus products, call today.
`
`Real Time Devices USA
`200 Innovation Blvd. • P.O. Box 906
`State College, PA 16803 USA
`(814) 234-8087 I Fax: (814) 234-5218
`RTD Europa • RTD Scandinavia
`Real Time Devices is a founder of the PC/1 04 Consortium.
`
`CIRCLE # 30 ON READER SERVICE CARD
`
`Exhibit 1218 11/12
`
`
`
`KERNEL & DEVELOPMENT TOOLS
`
`il1e Reliable Prelniurn Solution
`Can Acbally AHord 1b Use.
`foni • t Slylt • -.Q~ -~ :•
`
`flit
`
`fi1'tt '"~ ~141'"'"'-
`f'<>~~'""'
`=~=~~~~7~;.
`
`f!W:~ ~"'
`-~;~_ ;:~ ;~-~J
`
`Ql>to11
`
`. .
`
`. .. ...
`
`"lOin!
`
`........ 1.._...,._ . .,..,_.,
`~~-· ~~~_.:7,£.~~~::~~--'*····
`.._,,, )
`=~:=:_sr:::: ::.:::. ..
`=...::-
`.. _. ___
`:~·~.:"".:::.!.,·:.:-~~-· .. -·_ ........... -
`- -------- ·····----------------------------··1
`
`.. ........
`
`"""'"
`
`Al..Q0111'iii:Dt..OOI \ 1Uc:
`Al..(liXX)(lOO()Ol..o'JOOOOI<;..l
`
`Al-OOOOOOOOO~l'O
`
`.O.~l lli.UDC-0000J10F
`
`ilo.~OOOOOOOOO'i..()()(I(X)l •~
`
`J.'-OOilR(loo;..oooooooJ
`
`A7..001lii'U01-'l00001.t0
`
`PC \.0n-ion
`
`'""'~-,.,..~ll'l~t....O)
`
`•
`
`•.;
`
`. . . llrdlll'l l ltlll o ~lll
`
`·--~-· ~~~
`
`OM J<"'OOO
`
`-!·-,-
`
`......... ---~·-...
`
`'""""
`
`Updt"
`
`TD 0,.11011)0, 10-())10000 ~t~tTO ~ .. dy,HO III-4•
`
`TO-O.l!OIIbCI. IO-O>lQOOI.J.TI(...,_....,.f.«kMHO""'>!I
`
`T0-0lo110ill0,10-0.1000l.IO"'IIH.dvHOM!.ol
`TO.Q:I<I IOotbO.IO--O>·lOOOJ, Moii'I.TI>i',ll<v A.ny&b'k«< . Nofltl.9)
`
`SUN \.0rsion
`
`The Only Royalty-Freer Fully-Integrated Solution Available
`Backed By Over 25 Years Of Market Leadership:
`THE PRECISE SOLU110N from lntet111elrics
`
`MOTO R OLA The Precise Solu cion i nregrates the
`very best oflnrermetrics field-proven
`compiler and debugger technology
`wicl1 the leading-edge MQX real-time
`executive from Precise Sofrware
`Technologies, Inc.
`
`The Precise/MQX technology repre(cid:173)
`senrs over a decade of rich kernel
`heritage. When MQX is combined
`with the !ntermetrics task-aware
`rools, the result is a premium, fully(cid:173)
`integrated solmion ... all from one
`source!
`
`With compLete, royalty-free packages
`starting as low as $8500 and support(cid:173)
`ed by a solid, public company, you can
`complete your 68XXX project quickly,
`with affordabiliry and confidence.
`
`Our 68XXX Precise Solution
`for PC/Windows or SUN:
`Precise/MQX Real lime Executive
`
`PassKey/MQX Kernel-Aware
`Windows Cross-Debugger
`forPCorSUN
`
`lnterTools Optimizing C Compiler
`
`Optional Windows Integrated
`Development Environment
`
`TCP/IP, AS