lIlllllllllllllllIlllllllllllllllllllllllllllllIlllllllllllllllllllllllllll
`
`USOO5428636A
`5,428,636
`[11] Patent Number:
`[451 Date Of Patent: * Jun. 27, 1995
`
`Tymes .
`Miller et al. .
`Bertagna et a1. .
`Huang et a1. .
`Wakatsuki et a1. .
`Mahany et a1. .
`Tymes .
`Hauptschein et a1. ........... .. 370/95.l
`
`5,029,183 7/1991
`5,031,098 7/1991
`5,055,660 10/1991
`5,058,200 10/1991
`5,065,003 11/1991
`5,070,536 12/1991
`5,103,461 4/1992
`5,117,422 5/1992
`5,128,932 7/1992
`Li ........................................ .. 370/60
`5,142,531 8/1992
`Kirby .
`5,142,550 8/1992
`Tymes .
`5,150,360 9/1992
`Perlman et a1. .
`5,157,687 10/1992 Tymes .
`5,280,480 1/1994 PittetaL.
`
`FOREIGN PATENT DOCUMENTS
`
`281334 9/ 1988 European Pat. Off. .
`53-10206 1/1978 Japan .
`WO9202084 2/1992 WIPO .
`
`OTHER PUBLICATIONS
`L. Kleinrock and F. A. Tobagi, “Packet Switching in
`Radio Channels; Part IV-Stability Considerations &
`Dynamic Control in Carrier Sense Multiple Access,”
`(List continued .on next page.)
`
`Primary Examiner-David C. Cain
`Attorney, Agent, or Firm-McAndrews, Held & Malloy,
`Ltd.
`
`ABSTRACT
`1 [57]
`An apparatus and a method for routing data in a radio
`data communication system having one or more host
`computers, one or more intermediate base stations, and
`one or more RF terminals organizes the intermediate
`base stations into an optimal spanning-tree network to
`control the routing of data to and from the RF terminals
`and the host computer efficiently and dynamically.
`1 Communication between the host computer and the RF
`terminals is achieved by using the network of intermedi
`_ ate base stations to transmit the data.
`
`United States Patent [19]
`Meier
`
`I [54]
`
`RADIO FREQUENCY LOCAL AREA
`NETWORK
`
`[75]
`[73]
`
`Inventor: Robert C. Meier, Cedar Rapids, Iowa
`Assignee: Norand Corporation, Cedar Rapids,
`Iowa
`
`[ * ] Notice:
`
`[21]
`[22]
`
`Appl. No.:
`Filed:
`
`The portion of the term of this patent
`subsequent to Mar. 15, 2011 has been
`disclaimed.
`59,447
`May 7, 1993
`
`[63]
`
`[51]
`[52]
`
`[58]
`
`[56]
`
`Related US. Application Data
`Continuation-in-part of Ser. No. 56,827, May 3, 1993,
`Pat. No. 5,295,154, which is a continuation of Ser. No.
`769,725, Oct. 1, 1991, abandoned.
`
`Int. Cl.6 ............................................. .. H04K 1/00
`US. Cl. .................................... .. 375/202; 370/60;
`370/85.1; 370/94.1; 379/221; 379/209
`Field of Search ................... .. 375/1; 370/60, 85.6,
`370/94.1, 95.1, 77, 93; 379/221, 209; 340/825
`References Cited
`U.S. PATENT DOCUMENTS
`
`4,164,628 8/ 1979 Ward et a1. .
`4,332,027 5/ 1982 Malcom et a1. .
`4,352,955 10/1982 Kai et a1. .
`4,369,443 l/ 1983 Giallanza et a1. .
`4,420,682 12/ 1983 Huber .
`4,644,532 2/ 1987 George et a1. .
`4,670,899 6/1987 Brody et al. .
`4,679,244 7/ 1987 Kawasaki et a1. .
`4,689,786 8/1987 Sidhu et a1, .
`4,789,983 12/1988 Acompora et a1. .
`4,835,372 5/ 1989 Gombrich .
`4,864,559 9/1989 Perlman .
`4,884,266 11/1989 P?aumer .
`4,885,780 12/1989 Glopal et a1, ..................... .. 379/221
`4,910,794 3/ 1990 Mahany .
`4,916,441 4/ 1990 Gombrich .
`4,924,462 5/1990 Sojka .
`4,940,974 7/1990 Sojka .
`4,956,783 9/ 1990 Teranishi et a1. .
`5,008,882 4/1991 Peterson et a1. .
`5,018,133 5/1991' Tuskokoski et a1. .
`
`55.,
`
`/ 16
`
`13 Claims, 1 Drawing Sheet
`
`\
`\
`
`1
`22
`I
`
`E'“
`
`20
`
`\
`\
`
`ERF 104
`
`E“
`
`I
`I
`
`l
`
`I 1:1
`
`RF
`
`1 14
`
`[:1 /RF 118
`
`000001
`
`VIASAT 1029
`IPR of U.S. Pat. No. 5,960,074
`
`

`
`5,428,636
`Page 2
`
`OTHER PUBLICATIONS
`IEEE/Transactions on Communications, vol. COM-25
`No. 10, Oct. 1977.
`M. B. Pursley, “The role of Spread Spectrum in Packet
`Radio Networks,” Proceedings of the IEEE, vol. 75,
`No. 1.
`J. O. Onunga & R. W. Donaldson, “Performance Anal
`. ysis of CSMA with Priority Acknowledgements on
`Noisy Data Networks with Finite User Population,”
`IEEE Transactions on Comm, V39, N7, 791.
`
`L. Kleinroch & J. Silvester, “Spatial Rouse in Multihop
`Packet Radio Networks,” Proceedings of the IEEE
`V75, N1, Jan. 1987.
`F. Backes, “Transparent Bridges for Interconnection of
`IEEE 802 LANs,” IEEE Network, V2 N1 Jan. 1988.
`Internation a1 Standard ISO/DIS 8802-22.
`A. S. Tannenbaum, “Computer Networks,” Prentice
`Hall., Second Edition.
`‘
`D. E. Comer, “Internetworking with TCP/IP”, Pren
`tice Hall.
`
`000002
`
`

`
`US. Patent
`
`June 27, 1995
`
`5,428,636
`
`mwsmiou /
`
`OP
`
`.Tvl/
`
`uQQmm
`
`men-mm
`
`mQoEm
`
`woe-mm
`moo-KL
`
`/
`/
`/
`
`HHK
`
`m: “E
`
`‘ \ on
`
`\\
`
`\
`
`
`
`. P o: “E8 “EN 89%
`
`I _ \\\ Q?
`
`t: “Em
`
`N: “3%
`
`\
`
`000003
`
`

`
`5,428,636
`2
`nal send data to an intermediate station, the intermedi
`ate station send the data to a base station, and the base
`station send the data directly to the host computer.
`Communicating with a host computer through more
`than one station is commonly known as a multiple-hop
`communication system.
`Dif?culties often arise in maintaining the integrity of
`such multiple-hop RF data communication systems.
`The system must be able to handle both wireless and
`hard-wired station connections, ef?cient dynamic rout
`ing of data information, RF terminal mobility, and inter
`ference from many different sources.
`
`1
`
`RADIO FREQUENCY LOCAL AREA NETWORK
`
`CROSS-REFERENCE TO RELATED
`APPLICATIONS
`The present application is a continuation in part of
`the application of Robert C. Meier, U.S. Ser. No.
`08/O56,827, ?led May 3, 1993 (Attorney Docket Nos.
`10127USO2; DN37882X), now U.S. Pat. No. 5,295,154,
`issued Mar. 15, 1994, which is itself a continuation of
`Meier et al., U.S. Ser. No. 07/769,425, ?led Oct. 1, 1991
`(Attorney Docket Nos. 9lP668; DN37882), now aban
`doned.
`
`AUTHORIZATION PURSUANT TO 37 C.F.R.
`1.7(d) AND (3)
`A portion of the disclosure of this patent document
`contains material which is subject to copyright protec
`tion. The copyright owner has no objection to the fac
`simile reproduction by anyone of the patent document
`or the patent disclosure, as it appears in the Patent and
`Trademark Of?ce patent ?le or records, but otherwise
`reserves all copyright rights whatsoever.
`
`SUMMARY OF THE INVENTION
`The present invention solves many of the problems
`inherent in a multiple-hop data communication system.
`The present invention comprises an RF Local-Area
`Network capable of ef?cient and dynamic handling of
`data by routing communications between the RF Ter
`minals and the host computer through a network of
`intermediate base stations.
`In one embodiment of the present invention, the RF
`data communication system contains one or more host
`computers and multiple gateways, bridges, and RF
`terminals. Gateways are used to pass messages to and
`from a host computer and the RF Network. A host port
`is used to provide a link between the gateway and the
`host computer. In addition, gateways may include
`bridging functions and may pass information from one
`RF terminal to another. Bridges are intermediate relay
`nodes which repeat data messages. Bridges can repeat
`data to and from bridges, gateways and RF terminals
`and are used to extend the range of the gateways.
`The RF terminals are attached logically to the host
`computer and use a network formed by a gateway and
`the bridges to communicate with the host computer. To
`set up the network, an optimal con?guration for con
`ducting network communication spanning tree is cre
`ated to control the ?ow of data communication. To aid
`understanding by providing a more visual description,
`this con?guration is referred to hereafter as a “spanning
`tree” or “optimal spanning tree”.
`Speci?cally, root of the spanning tree are the gate
`ways; the branches are the bridges; and non-bridging
`stations, such as RF terminals, are the leaves of the tree.
`Data are sent along the branches of the newly created
`optimal spanning tree. Nodes in the network use a back
`ward learning technique to route packets along the
`correct branches.
`One object of the present invention is to route data
`ef?ciently, dynamically, and without looping. Another
`object of the present invention is to make the routing of
`the data transparent to the RF terminals. The RF termi
`nals, transmitting data intended for the host computer,
`are unaffected by the means ultimately used by the RF
`Network to deliver their data.
`It is a further object of the present invention for the
`network to be capable of handling RF terminal mobility
`and lost nodes with minimal impact on the entire RF
`data communication system.
`
`25
`
`INCORPORATION BY REFERENCE
`The Applicant hereby incorporates herein by refer
`ence the following patent applications: pending applica
`tion Ser. No. 08/056,827, ?led May 3, 1993, in the name
`of Robert C. Meier (Attorney Docket Nos. l0127US02;
`DN37882X); and abandoned application Ser. No.
`07/769,425, ?led Oct. 1, 1991, in the names of Meier et
`al. (Attorney Docket Nos. 91 P 668; DN37882).
`BACKGROUND OF THE INVENTION
`In a typical radio data communication system having
`one or more host computers and multiple RF terminals,
`communication between a host computer and an RF
`terminal is provided by one or more base stations. De
`pending upon the application and the operating condi
`tions, a large number of these base stations may be re
`quired to adequately serve the system. For example, a
`radio data communication system installed in a large
`factory may require dozens of base stations in order to
`cover the entire factory floor.
`In earlier RF data communication systems, the base
`stations were typically connected directly to a host
`computer through multi-dropped connections to an
`Ethernet communication line. To communicate be
`tween an RF terminal and a host computer, in such a
`system, the RF terminal sends data to a base station and
`the base station passes the data directly to the host com
`puter. Communicating with a host computer through a
`base station in this manner is commonly known as hop
`ping. These earlier RF data communication systems
`used a single-hop method of communication.
`In order to cover a larger area with an RF data com
`munication system and to take advantage of the deregu
`lation of the spread-spectrum radio frequencies, later
`developed RF data communication systems are orga
`nized into layers of base stations. As in earlier RF data
`communications systems, a typical system includes mul
`tiple base stations which communicate directly with the
`RF terminals and the host computer. In addition, the
`system also includes intermediate stations that commu
`nicate with the RF terminals, the multiple base stations,
`and other intermediate stations. In such a system, com
`munication from an RF terminal to a host computer
`may be achieved, for example, by having the RF termi
`
`55
`
`65
`
`BRIEF DESCRIPTION OF THE DRAWING
`The FIG. 1 is a functional block diagram of an RF
`data communication system incorporating the RF local
`area network of the present invention.
`
`000004
`
`

`
`LII
`
`25
`
`5,428,636
`4
`known methods of communicating via radio freouenc'i"
`(RF) link or via a direct wire link. In the pi
`embodiment of the present invention, the RF
`comprised of spread-spectrum transmissions using a
`polling protocol. Although a polling protocol is pre
`ferred, a carrier-sense multiple-access (CSMA), busy~
`tone, or any other protocol might also manage the com»
`munication traf?c on the RF link.
`HELLO packets contain 1) the address of the sender,
`2) the hopping distance that the sender is from the root,
`3) a source address, 4) a count of nodes in the subtree
`which ?ow through that bridge, and 5) a list of system
`parameters. Each node in the network is assigned a
`unique network service address and a node-type identi»
`?er to distinguish between different nodes and different
`node types. The distance of a node from the root node
`is measured in hops times the bandwidth of each hop.
`The gateway root is considered to be zero hops away
`from itself. The unattached bridges are in a LIST I
`state. During the LISTEN state, a bridge will listen to
`the HELLO messages that are broadcast. By listening
`to the HELLO messages, bridges can learn which
`nodes are attached to the spanning tree. The unattached
`bridges analyze the contents of the HELLO messages
`to determine whether to request attachment to the
`broadcasting node. In the preferred embodiment, a
`bridge attempts to attach to the node that is logically
`closest to the root node. In the preferred embodi
`’
`the logical distance is based upon the number of
`needed to reach the root node and the bandwidth or
`those hops. The distance the attached node is Z. ~/'
`from the root node is found in the second field of the
`HELLO message that is broadcast.
`In another embodiment of the present invention, the
`bridges consider the number of nodes attached to £11"
`attached node as well as the logical distance of ‘1.
`attached node from the root node. If an attached 110?. i
`overloaded with other attached nodes, the unattached
`bridge may request attachment to a less loaded node.
`After attaching to an attached node, the newly at
`tached bridge (the child) must determine its dista ce
`from the root node. To arrive at the distance of
`child from the root node, the child adds the broadcast
`distance of its parent from the root node to the distance
`of the child from its parent. In the preferred embodi
`ment, the distance of a child from its parent is basec ~
`the bandwidth of the data communication link.
`or
`example, if the child attaches to its parent via a hard
`wired link (data rate 26,000 baud), then the distance of
`that communication link might equal, for example, one
`hop. However, if the child attaches to its parent via a:
`RF link (data rate 9600 baud), then the distance of
`"
`communication link might correspondingly be equal 3
`hops. The number of the hop corresponds direct]; to
`the communication speed of the link. This may not only
`take into consideration baud rate, but also such factors
`as channel interference.
`Initially, only the root gateway node 20 is broadcast
`
`30
`
`3
`DETAILED DESCRIPTION OF THE
`INVENTION
`The FIG. 1 is a functional block diagram of an RF
`data communication system. In one embodiment of the
`present invention, the RF data communication system
`has a host computer 10, a network controller 14 and
`bridges 22 and 24 attached to a data communication link
`16. Also attached to the data communication link 16 is
`a gateway 20 which acts as the root node for the span
`ning tree of the RF data network of the present inven
`tion. A bridge 42 is attached to the gateway 20 through
`a hard-wired communication link and bridges 40 and 44
`are logically attached to gateway 20 by two indepen
`dent RF links. Additional bridges 46, 48, 50 and 52 are
`also connected to the RF Network and are shown in the
`FIG. 1. Note that, although shown separate from the
`host computer 10, the gateway 20 (the spanning tree
`root node) may be part of host computer 10.
`The FIG. 1 further shows RF terminals 100 and 102
`attached to bridge 22 via RF links and RF terminal 104
`attached to bridge 24 via an RF link. Also, RF terminals
`106, 108, 110, 112, 114, 116, 118, and 120 can be Seen
`logically attached to the RF Network through their
`respective RF links. The RF terminals in FIG. 1 are
`representative of non-bridging stations. In alternate
`embodiments of the present invention, the RF Network
`could contain any type of device capable of supporting
`the functions needed to communicate in the RF Net
`work such as hard-wired terminals, remote printers,
`stationary bar code scanners, or the like. The RF data
`communication system, as shown in FIG. 1, represents
`the con?guration of the system at a discrete moment in
`time after the initialization of the system. The RF links,
`as shown, are dynamic and subject to change. For ex
`ample, changes in the structure of the RF data commu
`nication system can be caused by movement of the RF
`terminals and by interference that affects the RF com
`munication links.
`In the preferred embodiment, the host computer 10 is
`an IBM 3090, the network controller 14 is a model
`RC3250 of the Norand Corporation, the data communi
`cation link 16 is an Ethernet link, the nodes 20, 22, 24,
`40, 42, 44, 46, 48, 50 and 52 are intelligent base trans~
`ceiver units of the type RB4000 of the Norand Corpora
`tion, and the RF terminals 100, 102, 104, 106, 108, 110,
`112, 114, 116, 118 and 120 are of type RTllOO of the
`Norand Corporation.
`The optimal spanning tree, which provides the data
`pathways throughout the communication system, is
`stored and maintained by the network as a whole. Each
`node in the network stores and modi?es information
`which speci?es how local communication traf?c should
`?ow. Optimal spanning trees assure ef?cient, adaptive
`(dynamic) routing of information without looping.
`To initialize the RF data communication system, the
`gateway 20 and the other nodes are organized into an
`optimal spanning tree rooted at the gateway 20. To
`form the optimal spanning tree, in the preferred em
`bodiment the gateway 20 is assigned a status of AT
`TACHED and all other bridges are assigned the status
`UNA'I'I‘ACHED. The gateway 20 is considered at
`tached to the spanning tree because it is the root node.
`Initially, all other bridges are unattached and lack a
`parent in the spanning tree. At this point, the attached
`gateway node 20 periodically broadcasts a speci?c type
`of polling packet referred to hereafter as “HELLO
`packets”. The HELLO packets can be broadcast using
`
`35
`
`45
`
`50
`
`55
`
`60
`
`65
`
`ing HELLO messages and only nodes 40, 42 and within range of the HELLO messages broadcast by ac
`
`gateway. Therefore, after the listening period has e2:
`pired, nodes 40, 42 and 44 request attachment to the
`gateway node 20. The unattached nodes 40, 42, and (4!»
`send ATTACI-I.request packets and the attached g e
`way node 20 acknowledges the ATTACHrequest
`packets with local ATTACHcon?rm packets. T1"
`newly attached bridges are assigned the
`TACHED and begin broadcasting their own .i.
`
`000005
`
`

`
`10
`
`45
`
`5,428,636
`6
`5
`terminals by monitoring the traf?c from terminals to the
`packets, looking for other unattached bridges. Again,
`root. If a packet arrives from a terminal that is not con
`the remaining unattached nodes attempt to attach to the
`tained in the routing table of the node, an entry is made
`attached nodes that are logically closest to the root
`in the routing table. The entry includes the terminal
`node. For example, node 48 is within range of HELLO
`address and the address of the node that sent the packet.
`messages from both nodes 40 and 42. However, node 40
`In addition, an entry timer is set for that terminal. The
`is three hops, via an RF link, away from the gateway
`entry timer is used to determine when RF terminals are
`root node 20 and node 42 is only one hop, via a hard
`actively using the attached node. Nodes maintain
`wired link, away from the gateway root node 20. There
`entries only for terminals that are actively using the
`fore, node 48 attaches to node 42, the closest node to the
`node for communication. If the entry timer expires due
`gateway root node 20.
`to lack of communication, the RF terminal entry is
`The sending of HELLO messages, ATTACH.re
`purged from the routing table.
`quest packets and ATTACH.con?rm packets continues
`The RF links among the RF terminals, the bridges,
`until the entire spanning tree is established. In addition,
`and the gateway are often lost. Therefore, a connection
`attached bridges may also respond to HELLO mes
`oriented data-link service is used to maintain the logical
`sages. If a HELLO message indicates that a much closer
`node-to-node links. In the absence of network traffic,
`route to the root node is available, the attached bridge
`periodic messages are sent and received to ensure the
`sends a DETACH packet to its old parent and an AT
`stability of the RF link. As a result, the loss of a link is
`TACH.request packet to the closer node. To avoid
`quickly detected and the RF Network can attempt to
`instability in the system and to avoid overloading any
`establish a new RF link before data transmission from
`given node, an attached bridge would only respond to a
`the host computer to an RF terminal is adversely af
`HELLO message if the hop count in a HELLO packet
`fected.
`is greater than a certain threshold value, CHANGEL
`Communication between terminals and the host com
`THRESHOLD. In the preferred embodiment, the
`puter is accomplished by using the resulting RF Net
`value of the CHANGE_THRSHOLD equals 3. In this
`work. To communicate with the host computer, an RF
`manner, an optimal spanning tree is formed that is capa—
`terminal sends a data packet in response to a poll from
`ble of transmitting data without looping.
`the bridge closest to the host computer. Typically, the
`Nodes, other than the gateway root node, after ac
`RF terminal is attached to the bridge closest to the host
`knowledging an ATTACH.request packet from a pre
`computer. However, RF terminals are constantly listen
`viously unattached node, will send the ATTACH.re
`ing for HELLO and polling messages from other brid
`quest packet up the branches of the spanning tree to the
`ges and may attach to, and then communicate with, a
`gateway root node. As the ATTACH.request packet is
`bridge in the table of bridges that is closer to the partic
`being sent to the gateway root node, other nodes at
`ular RF terminal. Under certain operating conditions,
`tached on the same branch record the destination of the
`duplicate data packets can be transmitted in the RF
`newly attached node in their routing entry table. When
`Network. For example, it is possible for an RF terminal
`the A'I'I‘ACHrequest packet reaches the gateway root
`to transmit a data packet to its attached node, for the
`node, the gateway root node returns an end-to-end
`node to transmit the acknowledgement frame, and for
`ATTACHcon?rm packet.
`the RF terminal not to receive the acknowledgement.
`After the spanning tree is initialized, the RF terminals
`Under such circumstances, the RF terminal will re
`listen for periodically broadcasted Hello packets to
`transmit the data. If the duplicate data packet is updated
`determine which attached nodes are in range. After
`into the database of the host computer, the database
`receiving HELLO messages from attached nodes, an
`would become corrupt. Therefore, the RF Network of
`RF terminal responding to an appropriate poll sends an
`the present invention detects duplicate data packets. To
`A'I'TACl-Lrequest packet to attach to the node logi
`ensure data integrity, each set of data transmissions
`cally closest to the root. For example, RF terminal 110
`receives a sequence number. The sequence numbers are
`is physically closer to node 44. However, node 44 is
`continuously incremented, and duplicate sequence num
`three hops, via an RF link, away from the gateway root
`bers are not accepted.
`node 20 and node 42 is only one hop, via a hard-wired
`When a bridge receives a data packet from a terminal
`link, away from the gateway root node 20. Therefore,
`directed to the host computer, the bridge forwards the
`RF terminal 110, after hearing HELLO messages from
`data packet to the parent node on the branch. The par
`both nodes 42 and 44, attaches to node 42, the closest
`ent node then forwards the data packet to its parent
`node to the gateway root node 20. Similarly, RF termi
`node. The forwarding of the data packet continues until
`nal 114 hears HELLO messages from nodes 48 and 50.
`the gateway root node receives the data packet and
`Nodes 48 and 50 are both four hops away from the
`sends it to the host computer. Similarly, when a packet
`gateway root node 20. However, node 48 has two RF
`arrives at a node from the host computer directed to an
`terminals 110 and 112 already attached to it while node
`RF terminal, the node checks its routing entry table and
`50 has only one RF terminal 116 attached to it. There
`forwards the data packet to its child node which is
`fore, RF terminal 114 will attach to node 50, the least
`along the branch destined for the RF terminal. It is not
`busy node of equal distance to the gateway root node
`necessary for the nodes along the branch containing the
`20.
`RF terminal to know the ultimate location of the RF
`The attached node acknowledges the ATTACHre
`terminal. The forwarding of the data packet continues
`quest and sends the ATTACH.request packet to the
`until the data packet reaches the ?nal node on the
`gateway root node. Then, the gateway root node re
`branch, which then forwards the data packet directly to
`turns an end-to-end ATTACH.con?rm packet. In this
`the terminal itself.
`manner, the end-to-end ATTACl-Lrequest functions as
`Communication is also possible between RF termi
`a discovery packet enabling the gateway root node, and
`nals. To communicate with another RF terminal, the
`all other nodes along the same branch, to learn the
`RF terminal sends a data packet to its attached bridge.
`address of the RF terminal quickly. This process is
`When the bridge receives the data packet from a termi
`called backward learning. Nodes learn the addresses of
`
`50
`
`65
`
`000006
`
`

`
`7
`nal directed to the host computer, the bridge checks to
`see if the destination address of the RF terminal is lo
`cated within its routing table. If it is, the bridge simply
`sends the message to the intended RF terminal. If not,
`the bridge forwards the data packet to its parent node.
`The forwarding of the data packet up the branch con
`tinues until a common parent between the RF terminals
`is found. Then, the common parent (often the gateway
`node itself) sends the data packet to the intended RF
`terminal via the branches of the RF Network.
`During the normal operation of the RF Network, RF
`terminals can become lost or unattached to their at
`tached node. If an RF terminal becomes unattached, for
`whatever reason, its routing entry is purged and the RF
`terminal listens for HELLO or polling messages from
`any attached nodes in range. After receiving HELLO
`or polling messages from attached nodes, the RF termi
`nal sends an ATTACHrequest packet to the attached
`node closest to the root. That attached node acknowl
`edges the ATTACHrequest and sends the AT
`TACH.request packet onto the gateway root node.
`Then, the gateway root node returns an end-to-end
`ATTACH.con?rm packet.
`Bridges can also become lost or unattached during
`normal operations of the RF Network. If a bridge be
`comes lost or unattached, all routing entries containing
`the bridge are purged. The bridge then broadcasts a
`HELLO.request with a global bridge destination ad
`dress. Attached nodes will broadcast HELLO packets
`immediately if they receive an ATTACHrequest
`packet with a global destination address. This helps the
`lost node re-attach. Then, the bridge enters the LIS
`TEN state to learn which attached nodes are within
`range. The unattached bridge analyzes the contents of
`broadcast HELLO messages to determine whether to
`request attachment to the broadcasting node. Again, the
`bridge attempts to attach to the node that is logically
`closest to the root node. After attaching to the closest
`node, the bridge begins broadcasting HELLO messages
`to solicit ATTACH.requests from other nodes or RF
`40
`terminals.
`The spread-spectrum system provides a hierarchical
`radio frequency network of on-line terminals for data
`entry and message transfer in a mobile environment.
`The network is characterized by sporadic data traf?c
`over multiple-hop data paths consisting of RS485 or
`ethernet wired links and single-channel direct se
`quenced spread spectrum links. The network architec
`ture is complicated by moving, hidden, and sleeping
`nodes. The spread spectrum system consists of the fol
`lowing types of devices:
`Terminal controller—A gateway which passes mes
`sages from a host port to the RF network; and which
`passes messages from the network to the host port. The
`host port (directly or indirectly) provides a link be
`tween the controller and a “host” computer to which
`the terminals are logically attached.
`Base station—An intermediate relay node which is
`used to extend the range of the controller node. Base
`station-to-controller or base station-to-base station links
`can be wired or wireless RF.
`Terminal——Norand RF hand-held terminals, printers,
`etc. In addition, a controller device has a terminal com
`ponent.
`The devices are logically organized as nodes in an
`(optimal) spanning tree, with the controller at the root,
`internal nodes in base stations or controllers on
`branches of the tree, and terminal nodes as (possibly
`
`45
`
`55
`
`65
`
`5,428,636
`
`20
`
`8
`mobile) leaves on the tree. Like a sink tree, nodes close:
`to the root of the spanning tree are said to be “do -
`stream” from nodes which are further away. Cor.
`versely, all nodes are “upstream” from the root. Packets
`are only sent along branches of the spanning tree.
`Nodes in the network use a “BACKWARD LE --
`f
`ING” technique to route packets along the branches of
`the spanning tree.
`Devices in the spanning tree are logically categorized
`as one of the following three node types:
`1) Root (or root bridge)-—A controller device 15
`functions as the root bridge of the network
`ning tree. In the preferred embodiment, the span
`ning tree has a single root node. Initially, all con
`trollers are root candidates from which a root node
`is selected. This selection may be based on
`hopping distance to the host, preset priority, ran»
`dom selection, etc.
`2) Bridge—An internal node in the spanning
`which is used to “bridge” terminal nodes toge . .7
`into an interconnected network. The root none is
`also considered a bridge and the term “bridge”
`may be used to refer to all non-terminal nodes or all
`non-terminal nodes except the root, depending on
`the context herein. A bridge node consists of a
`network interface function and a routing funct.
`3) Terminal—leaf node in the spanning tree. A te
`nal node can be viewed as the software entity
`terminates a branch in the spanning tree.
`A controller device contains a terminal node(s) and a
`
`v1.1
`
`
`
`bridge node. The bridge node is the root node if controller is functioning as the root bridge. A base Cta»
`
`tion contains a bridge node. A terminal device cont
`a terminal node and must have a network inter.ace
`function. A “bridging entity” refers to a bridge node c:
`to the network interface function in a terminal.
`The basic requirements of the system are the follow
`ing.
`a) Wired or wireless node connections.
`b) Network layer transparency.
`c) Dynamic/automatic network routing con?gure»
`tion.
`d) Terminal mobility. Terminals should be able to
`move about the RF network without losing a:
`end-to-end connection.
`e) Ability to accommodate sleeping terminals.
`f) Ability to locate terminals quickly.
`g) Built-in redundancy. Lost nodes should have
`mal impact on the network.
`h) Physical link independence. The bridging alx' -
`rithm is consistent across heterogeneous ph
`links.
`The software for the spread-spectrum system is func
`tionally layered as follows.
`Medium Access Control (MAC)
`The MAC layer is responsible for providing reli
`.
`transmission between any two nodes in the network (i
`terminal-to-bridge). The MAC has a channel access
`control component and a link control component. The
`link control component facilitates and regulates p
`to-point frame transfers in the absence of collision de
`tection. The MAC channel access control compo ‘
`regulates access to the network. Note that her in
`.
`MAC layer is also referred to as the Data Link. layer.
`Bridging Layer
`The bridging layer, which is also referred to herein a:
`the network layer, has several functions as rollows.
`
`000007
`
`

`
`10
`
`5
`
`20
`
`25
`
`l. The bridging layer uses a “HELLO protocol” to
`organize nodes in the network into an optimal
`spanning tree rooted at the root bridge. The span
`ning tree is used to prevent loops in the topology.
`Interior branches of the spanning tree are relatively
`stable (i.e. controller and relay stations do not
`move often). Terminals, which are leaves on the
`spanning three, may become unattached, and must
`be reattached, frequently.
`2. The bridging layer routes packets from terminals to
`the host, from the host to terminals, and from ter
`minals to terminals along branches of the spanning
`tree.
`3. The bridging layer provides a service for storing
`packets for SLEEPING terminals. Packets which
`cannot be delivered immediately can be saved by
`the bridging entity in a parent node for one or more
`HELLO times.
`The bridging layer propagates lost node informa
`4.
`tion throughout the spanning tree.
`5. The bridging layer maintains the spanning tree
`links.
`6. The brid