`~~
`JOHNS HOPKINS
`SHERIDAN LIBRARIES f!
`UNIVERSITY MUSEUMS
`
`DECLARATIO 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 per onal knowledge of the facts listed below.
`
`2.
`
`The Milton S. Ei enhower 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 periodical . Specifically, Exhibit A
`
`shows the article titled "Communication Protocol for Embedded System " as in appear in the
`
`ovember 1994 issue of Embedded Systems Programming. This is volume 7, issue 11 of this
`
`publication.
`
`4.
`
`The tamp on the back cover of the November 1994 issue of Embedded Sy t~ms
`
`Programming reads "OCT 28 1994." It is the regular practice of the Milton S. Ei enhower
`
`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 isitor
`
`of the 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 Baltimore, MD 21218 410-516-8328 Fax 410-516-5080 www.llbrary.jhu.edu
`
`
`
`
`
`Apple Exhibit 1021
`Apple Inc. v. Rembrandt Wireless
`IPR2020-00033
`Page 00001
`
`
`
`EXHIBIT A
` ÿÿ
`
`ÿ ÿ ÿ ÿ ÿ ÿ ÿ ÿ ÿ ÿ ÿ ÿ ÿ ÿ ÿ ÿ ÿ
`
`Exhibit 1218 02/12
`
`
`
`IPR2020-00033 Page 00002
`
`IPR2020-00033 Page 00002
`
`
`
`• ti)MBEA 11 U.S. $3.95 CANADA $4.95
`R 1994 A MILLER FREEMAN PUBLICATION
`
`.
`
`Ada Achieves Orbit
`f Cruising with Ada
`~ 1
`Basics of Networking ~ ,).·
`. C
`C t .
`,
`on a1ners 1n ++
`Plauger on Prediction
`
`,
`
`.,
`
`.~-·
`
`A Satellitej as·e Stug,y
`)\
`i
`It
`,!"
`J
`
`t
`
`111
`11' 1111111 I I I II I I 11 'l 11
`
`111ll 1
`8 ll ll 0l'l '3tJOt'll.L 7\18
`,UIStJ3AINO SN1>4dOH SNHOr
`.Ld30 SWltJ3S
`A\:l\ftJ817 \:13MOHN3Sl3 S NO.L 711-'l
`VI/ 9
`91
`L£t,6
`"6/\ON I U•6 1/0ll I VOLOOOO 160#
`S3.1\f.LS 03Xlrl ................. l:1.1.:18NX8M
`
` ÿ ÿ
`
`
`IPR2020-00033 Page 00003
`
`
`
`VOL 7 NO. 11 NOVEMBER 1994
`
`able of Contents
`
`lICHARD RIEHLE. Like C++ before it, Ada is
`g criticisms behind and finding acceptance in a
`Cl~ of embedded applications. This case study
`, the trials and triumphs of a satellite design
`·~ decision to shift to Ada.
`
`8 Cruising with Ada
`
`00-WHILE JONES. Too many developers let their
`dictate their designs. In this system design mani(cid:173)
`.Jones looks at the dangers of inappropriate design
`ologics and the advantages of Ada as a proto(cid:173)
`tool for a typical microcontroller application.
`
`Communication Protocols for
`Embedded Systems
`BHARGAV UPENDER AND PHILIP KOOPMAN.
`e networking architectures were designed without
`ded or real-time concerns i.n mind. Here's an
`iew of the tradeoffs in choosing different embed(cid:173)
`aetworking protocols.
`
`Containers and Templates
`
`'BRUCE ECKEL. Container classes are quite useful.
`lemenling them, however, often requires template
`rt. In keeping with our emphasis on "under the
`"details, this month's intr,oduction to C++ contain(cid:173)
`is also an exploration in the use of templates.
`
`ON THE COVER:
`If your geosynchro(cid:173)
`nous service calls
`are getting too
`expeosive, try
`shifting to Ada.
`Cover by
`Rupen 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-)272) IS published monthly by Miller Freeman Inc., 600 Hamson Sl. San Francisco. CA 94107. (415) 905-2200. Plea,e dit<Ct odvcrtismg aod
`. - .~ u, dus address. SUDSCRlPTION RA TE for 1hc Urutcd States is $49.9S for 12 issues. C1.11Ddian/Mex1c3fl ordtrs mwt be accompanied by payment in U.S. funds with additional pos"Se
`,=. AU other fmign subscnptions must be prtpaid in U.S. funds with ndd1LJonal postage of$ IS pet y<ar for :&urface mail and $40 per yeas for airmail. POSTMASTER: Alt subscription ordcn.
`nh<ldim dw!JeS ahould be sent to EMBEDDED SYSTEMS PROGRAMMING, P.O. Box 420046. Palm Coul FL 32142-0046. For cuslom<r service, telephone toll-free (800) 829-55)7 •
`.... four 10 six weeks for change of address to lake effect. Secood-<:lass postage ts paid at San Franctsco, CA and a<lditiotul mailing offices. EMBEDJ)ED SYSTEMS PROGRAMMING is a
`tndcmarlc owned t,y the parent company, Miller Ft<etlWI Inc. AU matmal published in EMBEDDED SYSTEMS PROGRAMMING is copyright o• 1994 by Miller Fnocman Inc. All righlS
`ltptodltouon ofmatenal oppcanng in EMBEDDED SYSTEMS PROGRAMMING is fotbidden without pennis,ion. EMBEDDED SYSTEMS PROGRAMMING is available on microfilm/fiche
`,m,ry M1crn6lms International, 300 N. Zeeb Rd.. Aon Arbor, Ml 48106, (l13) 761-4700.
`
`NOVEMBER 1994 EMBEDDED SYSTEMS PROGRAMMING 3
`
` ÿ ÿ
`
`
`IPR2020-00033 Page 00004
`
`
`
`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)
`ditionaUy electro-mechanically con(cid:173)
`trolled 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 1/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 acruators."
`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 VME
`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
`i
`access protocol, which picks the next
`
` ÿ ÿ
`
`NOVEMBER 1994
`
`transmitter for access to the shared
`work medium, typically a wire,
`or RF frequency.
`In this article, we will discUSI
`special considerations for net\\
`real-time embedded systems, and
`at several media access protocof4
`demonstrate fundamentally di
`ways of accessing the shared
`The protocols are: connection
`protocols, pollin~ time division
`pie access (TOMA), token ring.
`bus, binary countdown, earner
`multiple access with collision
`tion (CSMA/CD), and carrier
`multiple access with collision a
`ance (CSMA/CA). For each or
`we will evaluate the siren~
`weaknesses against special COl15
`tions. A protocol tradeoff chart
`enable you to select a protoo4 •
`your needs. While no pro1ocor is
`feet for all purposes, a vari~
`CSMA/CA offers the most ,,
`for many embedded systems.1
`
`SPECIAL CONSIDERATIONS
`
`I n practice, we have found
`
`real-time ne
`embedded
`require high efficiency, de
`1st1c latency, operational
`configuration nexibility, and low
`per node.
`Because cost limits the
`bandwidth available to many
`
`IPR2020-00033 Page 00005
`
`
`
`i,n;,protocol efficiency (message bits
`ltivered compared to raw network
`lundwidth) is very important. The
`Olbedded systems we have studied are
`9racterized by a predominance of
`tliort. periodic messages. So, an obvi-
`1111S l1ptimization is to reduce overhead
`bits used for message packaging and
`lioting. (It is not unusual for eight bits
`of data to be packed in a message that
`u32or even 64 bits long.)
`Once message overhead has been
`Dluced as much as possible, media
`i,:cess overhead must be reduced. For
`die most part, this is accomplished by
`IDUllmizing the network bandwidth
`IIJDSumed by arbitration (such as pass(cid:173)
`ing a toktn or resolving collision con(cid:173)
`ftict). Because worst-case behavior is
`l\t11,lll}' important. efficiency should
`be evaluated for both light and heavy
`bllic. For example, CSMNCD (often
`lllCil in workstation LANs) is highly
`tfficient for light traffic but gives poor
`,rfonnance if heavily loaded, while
`riken bus protocols have the reverse
`,o,>erties.
`Oeterrninacy, or the ability to calcu(cid:173)
`late worst-case response time,
`is
`tmportant for meeting the real-time
`mnstraints of many embedded control
`41>lications. A prioritization capabili(cid:173)
`ty is usually included in systems to
`liprove detenninacy of messages for
`nme-critical tasks such as exception
`lmdling and high-speed loop control.
`friorities can be assigned by node
`mber or message type. Additionally,
`tffililC(llS can support local or global
`,iority mechanisms. In local prioriti(cid:173)
`ation. each node gets a tum at the net(cid:173)
`work in sequence and sends its highest
`~ority queued message (thus poten(cid:173)
`tially forcing a very high-priority mes(cid:173)
`sage to wait for other nodes to have
`lheir turns first). ln global prioritiza(cid:173)
`tion. the highest priority message in the
`entire system is always transmitted
`first. This mechanism, which is funda(cid:173)
`mentally enabled by the media access
`:-mtocol, is highly desirable for many
`rcty-<:ritical applications.
`Many applications require robust
`
`Because worst(cid:173)
`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, for example),
`added nodes, and deleted nodes. In
`some systems, it's important to quick(cid:173)
`ly recover from a reset or power glitch
`that forces a restart of the network.
`Varied operating environments may
`dictate use of a media access protocol
`that is flexible in supporting multiple
`media and mixed topologies. Portions
`of a system may require expensive
`fiber in noisy environments, 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 for fiber.
`A vital consideration 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-volume applica(cid:173)
`tions, these protocols are good candi(cid:173)
`dates. However, for growing applica(cid:173)
`tions, more advanced protocols pro(cid:173)
`vide a stronger foundation. In general,
`costs are decreasing over time due to
`
` ÿ ÿ
`
`
`Us
`
`will
`
`ared net(cid:173)
`re, fiber,
`
`,CUSS the
`tworking
`and look
`,cols that
`different
`medium.
`1-orienled
`on multi(cid:173)
`ng, token
`~er sense
`~n detec(cid:173)
`ier sense
`n avoid(cid:173)
`of these,
`gths and
`onsidera-
`an will
`col to fit
`ol is per(cid:173)
`iation of
`rcrsatility
`
`und that
`1etworlcs
`letennin(cid:173)
`oustn~
`low cost
`
`network
`applica-
`
`IPR2020-00033 Page 00006
`
`
`
`Communication Protocols
`
`advances in IC manufacturing technol(cid:173)
`ogy and the increasing availability of
`off-the-shelf protocols. Consequently,
`we envision advanced cost-effective
`protocols used in many embedded
`applications.
`
`MEDIA ACCESS PROTOCOLS
`
`N ow that we hav,e a feel for the
`
`issues in embedded networks,
`let's examine various com(cid:173)
`monly available media access proto(cid:173)
`cols. While many variations and com(cid:173)
`binations are possible, we'll discuss
`the plain versions of each protocol.
`Before LANs became popular, con(cid:173)
`nection-oriented protocols were heavi(cid:173)
`ly used to connect remote terminals to
`mainframes. These protocols support
`only two nodes per physical transmis(cid:173)
`sion medium and are typically con(cid:173)
`nected via modem with serial lines.
`Figure I shows an example of a four(cid:173)
`processor network using this protocol.
`Communication between nodes not
`physically connected requires multiple
`transmissions through intermediate
`nodes. These protocols are determinis(cid:173)
`tic between directly connected nodes.
`For indirectly connected nodes, latency
`can be high.
`For an embedded system with mod(cid:173)
`est communication requirements, this
`might be a cost-effective protocol
`(readily available hardware and soft(cid:173)
`ware from mature technology). For
`demanding applications, nodes that
`handle a lot of pass-through traffic can
`become swamped, prohibiting use of
`low-cost nodes in a Large system.
`Sometimes, this type of protocol is
`combined with a more complex com(cid:173)
`munication system to provide back(cid:173)
`ward compatibility to older systems or
`to allow simple remote modem access
`to the system (such as BACnet). This
`type of protocol is used by the X.25
`public ner.vork standard (ner.vork ser(cid:173)
`vices offered by telephone companies)
`and IBM's system network architec(cid:173)
`ture (SNA).2
`Polling is one of the more popular
`protocols
`for embedded systems
`because of its simplicity and determi-
`
`nacy. In this protocol, a centrally
`assigned master periodically sends a
`polling message to the slave nodes,
`giving them explicit permission to
`transmit on the network.
`Figure 2 shows the polling order
`(dotted lines) of a simple four-node
`bus network. The majority of the pro(cid:173)
`tocol software is stored in the master
`and the communication work of slave
`nodes is minimal (therefore, the net(cid:173)
`work costs tend to be smaller). This
`protocol is ideal for a centralized data(cid:173)
`acquisition system where peer-to-peer
`communication and global prioritiza(cid:173)
`tion are not .required. However, the sin(cid:173)
`gle-point-of-failure from the master
`node (or the cost of installing redun(cid:173)
`dant master hardware) is often unac(cid:173)
`ceptable. Additionally, the polling
`process consumes considerable band(cid:173)
`width regardless of network load (poor
`
`e fficiency). These protocols
`standardized by the milifall
`STD-1553B) for aircraft 1
`communications. Some \anatti
`protocol allow inter-slavec
`tion through the master as
`improved robustness by usmg
`masters (as does Profibus).
`
`T irne di visioa multiJJII
`
`(TOMA) is heavilJ
`satellite communicailll
`applicable to LANs as welll II
`protocol, a network master ,
`a frame sync signal before e3dl
`of messages to synchroruze c
`au the nodes. After the sync,
`transmits during its uniquely
`time slice, as shown in f.
`Performance is similar to pol
`with greater efficiency at hea~
`
`FIGURE 1
`An example network using co1111ection-orie11ted protocols.
`
`FIGURE 2
`Master node sequentially polling slave nodes for information ..
`
`Master
`
`c- ......... ,, ••s---....... __ ~-~-- - -
`
`\ 1st
`
`Bus
`
`Slave)
`
`Slave2
`
`50 EMBEDDED SYSTEMS PROGRAMMING NOVEMBER 1994
` ÿ ÿ
`
`
`IPR2020-00033 Page 00007
`
`
`
`Communication Protocols
`
`optics. So, many LANs and wide area
`networks (WANs) are moving to this
`type of protocol. For example, fiber
`distributed data interface (FODJ) uses
`dual counter-rotating rings to achieve
`higher reliability than bus or star
`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 broadcastl
`message simultaneously to all
`instead of passing it bit-by-bit alq
`physical ring. The minimum time flt
`token to traverse the logical ring
`nodes is thus N•T bit times instt.311
`N+ T bit times as in token ring (
`there is no parallelism in the co
`tions). This makes global prioriti
`of messages largely impractical,
`Unlike unidirectional token ~
`break in the cable or a failed node
`not necessarily disable the entile
`work. A
`lengthy reconfi
`process, where each node identilill
`neighbors, is used to maintain the ·
`tual ring when nodes are added
`
`FIGURE 3
`The time slices ofTDMA protocols.
`
`Master
`
`Bus
`
`~
`' ' ' '
`t >
`
`la
`
`la
`
`,
`
`, ,
`
`:f
`
`,
`
`, ,
`
`, ~-- , ,•
`
`la 3 s
`
`FIGURE 4
`Token passing in the token ring networks.
`
`Token
`
`due to elimination of individual polling
`messages. Costs for slave nodes are
`greater with TOMA than with polling,
`because each slave node must have a
`stable time base to measure slices. An
`additional weakness for TOMA is the
`need for fixed-length messages to fit
`into time slices. lo some TOMA varia(cid:173)
`tions, unused slices are truncated by
`tacit agreement among nodes. Time(cid:173)
`based protocols have been popular in
`aerospace a pplications. For example,
`digital autonomous terminaJ access
`communications (DATAC) is being
`used by NASA and Boeing.
`ln a token ring network, the nodes
`are connected in a ring-like structure
`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,
`sends its message all the way a.round
`the ring, and passes the token on. Since
`worst-case token waiting time can eas(cid:173)
`ily be calculated, this protocol is deter(cid:173)
`ministic. Under light traffic, token ring
`has moderate token passing overhead.
`However, the protocol provides effi(cid:173)
`cient throughput under heavy traffic
`conditions si nee idle token passing is
`mi nimized.
`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 T is 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 only 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
`disabling the entire network is a com(cid:173)
`mon concern
`for many users.
`Consequently, node bypass hardware
`and dual rings are used to address this
`concern at additional cost. Because the
`ring connections themselves are point(cid:173)
`to-point, it is well suited for fiber
`
`52 EMBEDDED SYSTEMS PROGRAMMING NOVEMBER 1994
` ÿ ÿ
`
`
`IPR2020-00033 Page 00008
`
`
`
`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 (ARCnct)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.
`ln 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
`(tnmsmitting 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 "I") overrides the oppo(cid:173)
`site value (a "O"). 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, ifa "I" signal is dominant, the
`highest numbered transmitting node
`wins the competition and gains owner(cid:173)
`ship of the channel.
`be
`can
`Global
`prioritization
`achieved by arbitrating over message
`ID values rather than the node IDs.
`Since the arbitration is part of the mes(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 prioriiized, 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)
`former coupling commonly used in
`high-noise environments) aren't com(cid:173)
`patible with the bit dominance require(cid:173)
`ment. Using this protocol, Bosch
`developed the controller area network
`(CAN) specification for automotive
`applications.5 The
`Society of
`
`Automotive Engineers s tandard SAE
`J-1850 also uses this protocol.
`
`CARRIER SENSE MULTIPLE ACCESS
`
`C arrier sense multiple access
`
`collision
`with
`detection
`(CSMA/CD) has been widely
`researched with a large number of pub(cid:173)
`lished variations. In the simplest case,
`a node waits for the network to go idle
`before transmission (as in binary
`countdown). If multiple stations trans(cid:173)
`mit almost simultaneously (within a
`row1d-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 supports an unlim(cid:173)
`ited number of nodes that don't require
`preallocated slots or inclusion in token
`
`passing acttv111es.
`nodes to enter and leave the n
`without requiring network imll ·
`tion and configuration. For light
`conditions, overhead is very
`However, under heavy traffic, die
`overhead is unbounded due to ·
`probability of repeated collis~
`Consequently, this protocol has
`determinacy and
`low cffic1
`furthermore, detecting collisiollf
`require analog circuitry, adding to die
`system expense. In fact, if the a~
`environment is very noisy or di
`wiring runs are long and of poor
`ty, collision detection may not wotk.f
`all. The popular Ethernet protocc,li&!lli
`in workstation LANs is based on a
`protocol.
`Many hybrid protocols combinatll
`light traffic efficiency of CSMMI
`with the heavy traffic cfficieJlll"'
`
`FlGURE 5
`Token passing in token bus protocols.
`
`Token
`----------
`-----·--------
`
`FIGUR.E 6
`Arbitration in binary coumdown protocols.
`
`Node JD
`
`7
`MSB
`
`6
`
`Node 72
`(01001000) :
`
`0
`
`0
`
`Node 7 1
`co1000111) :
`Node 42 ! 0
`0
`(00101 010) "'": .....;;;.__.,....;;;.~
`:
`
`5
`
`()
`
`4
`
`0
`
`3
`
`2
`
`0
`
`0
`
`0
`
`0
`
`0
`
`,
`.
`.
`!
`•
`•
`,
`1
`: ~ :
`:
`:
`:
`:
`:
`:Node 7, loseshfr,
`. 1----- Wade 4i loses here
`:
`:
`.
`'
`'
`
`54 EMBEDDED SYSTEMS PROGRAMMING NOVEMBER 1994
` ÿ ÿ
`
`
`Bit Slices
`
`IPR2020-00033 Page 00009
`
`
`
`Communication Protocols
`
`token-based protocols. The resulting
`protocols are often called carrier sense
`multiple access with collision 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, slot! 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 CSMA/CD networks.
`
`Bus
`
`Collision
`
`FIGURE 8
`Slot progression in CSMAICA protocols.
`
`CPUI
`I
`
`CPU2
`
`CPU3
`
`•
`I - -
`
`Bus
`
`CPU2 &3
`Collide
`I
`
`Jam PSlot Slot!
`
`/
`
`Priority Slot
`
`Time
`
`expected traffic prediction.7 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 described the major
`
`media access protocols and
`noted clear differences.
`Table l 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, TOMA, and connection-
`
`'··-(cid:141)
`
`(cid:141) --·
`
`Collision
`
`based protocols are simple, but
`not provide sufficient 0e1'ibilil
`advanced systems.
`• Token-based protocols are
`dictable, but can have high 01
`and require complex software to
`tain robusu1ess.
`• Binary count-down protocolf
`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, paruc
`RCSMA, is a good choice. While
`application will no doubt .have c
`teristics that are somewhat dJ
`
`56 EMBEDDED SYSTEMS PROGRAMMING NOVEMBER 1994
` ÿ ÿ
`
`
`IPR2020-00033 Page 00010
`
`
`
`Replace Four
`Conventional PC/104
`Modules with
`One SuperXr"'
`CMF8680 cpuModule™
`Embedded PCIXT Controller with
`Intelligent Power Management
`@~ C
`c 1'\o•
`
`PC/XT compatibility with 286 emulation
`14 MHz, 16-bit 8086 CPU
`+SV only; 1.6W at 14.3 MHz, 1 W at 7.2 MHz
`Intelligent sleep modes, 0.1 W in Suspend
`ROM-DOS and RTD enhanced BIOS
`Compatible with MS-DOS & real-time
`operating systems
`1 M bootabte 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
`Pa.raltel, XT keyboard & speaker ports
`Optional X-Y keypad scanning/PCMCIA
`interface
`(cid:127) Watchdog timer & real-lime clock
`
`Expand This Or Any PC/104 System
`with the
`CM106 Super VGA
`Controller utilityModule TM
`(cid:127) Mono/color STN & TFT flat panel support
`(cid:127) Simultaneous CRT & LCD operation
`(cid:127) Resolution to 1024 x 768 pixels I $223 1
`(cid:127) Displays up to 256 colors
`
`100 " '
`
`Speed Product Development with the
`DS8680 Development System
`Your DS8680 includes the CMF8680, CM102
`keypad scanning/PCMCIA, CM104 with 1.8'
`85MB hard drive, CM106 SVGA controller &
`DM5406 12-bit, 100 kHz dataModule™ in an
`enclosure with external power supply, 3.5'
`floppy, keyboard, keypad, TBS0 terminal
`board, SIGNAL-VIEW"", SIGNAL'MATH"',
`MS-DOS, SSD software & rtdLinxT" 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 / Fax: (814) 234-5218
`RTD E u ropa • RTD Scandinavia
`Aeat Tlme Devices ts a rounder ot the PC/104 Consortium.
`
`CIRCLE # 30 ON READER SERVICE CARD
`
`Efficiency Efficiency
`Heavy Deter- Priori- Robust-
`Light
`Traffic
`Traffic
`rninacy tization
`ness
`
`TABLE 1
`Media access tradeoffs.
`
`... Good
`- Ok
`... Poor
`
`ConnecLion
`
`Polli.og
`
`TDMA
`
`Token Ring
`
`Token Bus
`
`Binary Cnt .
`
`CSMA/CD
`
`CSMNCA
`
`...
`...
`...
`...
`...
`...
`
`...
`...
`...
`...
`...
`...
`...
`
`...
`...
`...
`...
`...
`...
`...
`
`...
`...
`...
`
`...
`
`Physical
`Layer
`Flexibil.
`
`..
`
`t
`t
`
`...
`...
`...
`
`t
`
`..
`
`t
`t
`
`...
`...
`...
`
`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. (cid:127)
`
`Bhargav Upe11der is an associate
`e11gi11eer
`at United
`research
`Technologies
`Research
`Center.
`C11rrently . he is exploring novel archi(cid:173)
`tectures and s11pporti11g protocols for
`distributed embedded systems. He
`holds a BS in electrical engineering
`from the University of Connecticut a11d
`an MS in electrical e11.gi11eeri11g from
`Cornell University in New York. He
`can be co111acted electro11ica/ly al
`barg@utrc.utc.com.
`
`is a principal
`Philip Koopman
`research
`engineer
`at United
`Technologies Research Center. He
`currently designs and evaluates archi(cid:173)
`tectures and communicalion protocols
`for a variety of embedded applications.
`He has previously worked as an
`embedded CPU architect and a Navy
`s11bmari11e officer. Koop111a11 holds a
`BS and MS i11 computer engineering
`from Rensselaer Polytechnic Institute
`
` ÿ ÿ
`
`
`and a PhD in computer engin
`from Carnegie Mellon Unfrwir,.
`may be reached e/ec/ronia(IIJ,
`koopma11@utrc.utc.com.
`
`REFERENCES
`1. Upender, B. P. and Koopm.vQ~
`J.,
`Embedded
`Communi
`Protocol Optio11s, San Jose, C
`Proceedings of the Embedded S
`Conference, October 1993.
`2. Tanenbaum, A: S., Cu'"p
`Networks, 2nd ed., Englewood C ·
`NJ: Prentice-Hall, I 989.
`3. Stallings, W. S.,
`Computer Communications, 3rd
`New York: Macmillan, 1991.
`4. Hoswell, Katherine S.
`Thomas, George M., ARCnet Fa
`LAN Primer, Second Pnn ·
`llliooil
`Downers
`Grove,
`Contemporary Control Systel!lll Inc.
`1988.
`5. Bosch, CAN Speci1icati~ wt
`2.0, Robert Bosch GmbH, Stuttpif
`1991.
`6. Chen and Li, Reserv•
`CSMAICD: A Multiple Aceall
`Protocol for LANs, IEEE Journal a
`Selected Areas in Communic.dil
`February 1989.
`7. Enhanced Media Access Con/Ill
`with Echelon 's Lon Talk Pro1,,.-rJ.
`LonWorks Engineering Bull •
`Echelon Corp., August 1991.
`
`IPR2020-00033 Page 00011
`
`
`
`KERNEL & DEVELOPMENT TOOLS
`
`The Reliable Pre111iun1 Soluti011
`You Can Adlllally Afford To Use.
`
`....... •-..-...-\ ____ .._ __ ....
`:.:-1·:i·:--"-__ ,.,,
`·-· ...... ,. ___ _...,,
`::.;.::::=~-s~
`u •--J'l• ... _., , f
`
`~------
`... ~~.:~.,-~·
`
`s...r::"-:::=--.. ----
`
`.... iea, . . . ~ . r .
`
`~.-..,~
`~""'~,
`-----~ .......
`_...,..., ..
`-••l~-.-.ai-.
`,O.\,.,.<N·•·• .. -..,
`
`[] --
`
`•
`
`'r••ll'IO-C'~l••')C'l. .... ,-. ....
`!It. ,.,,_ t .....,. o.'~b ...... _ .....
`-,.w,~,;,........u ---~ ...
`fQ,.91,.,..o.,.--.-..,_ .... ..,_-.,..
`
`..
`
`PCl&non
`
`SUN \&>ion
`The Only Royatty ... Fteer Fully-Integrated Solution Available
`Backed By Over 25 Years Of Malket Leadership:
`THE PRECISE SOLU110N from lntet111ebic:s
`
`'I
`I
`
`EMBEDDED.
`l'l\mtllll£\llDIII
`
`The Precise Solution integrates the
`very best of lntemietria fidd-proven
`compiler and debugger technology
`with the leading-edge M QX real-time
`executive from Precise Software
`Technologies, Inc.
`The Precisc-'.MQX technology repre(cid:173)
`sents over a decade of rich kernel
`heritage. Whert MQX is combined
`with the lnterrndrics task-aware
`tools, the result is a premium, f