_
`
`United States Patent [19]
`' Brand et al.
`
`lllllllllllllllllllllllllllllllllllllllllllllllIllllIllllllllllllllllllllll
`
`US005237566A
`
`[11]- Patent Number:
`[45] Date of Patent:
`
`5,237,566
`Aug, 17, 1993
`
`[54] NETWORK HUB FOR MAINTAININGNODE
`BANDWIDTH IN A SINGLENODE
`NETWORK
`
`[75] Inventors: Robert C. Brand, Andover, Mass.;
`~
`Stanf d L. M ti 1 Pal Alt ,
`Calif-f"
`n p y’
`o
`0
`
`4,773,067 9/19ss Duxbury m1. ................. .. 370/60.1
`4,843,606 6/1989 Bux et a1. . . . . . . . . . .
`. . . .. 370/85.4
`4,887,076 12/1929 Kent et a1. .............. .. 370/61
`4,910,731 _3/1990 Sakurai et a1.
`370/60
`4,947,387 8/1990 Knorpp et a1. .................... .. 370/60
`Primary Examiner—Douglas W. Olms
`Assistant Examiner-Hassan Kizou
`Attorney, Agent. or Firm-—Townsend and Townsend
`Khourie and Crew
`ABSTRACI
`[57]
`A hub network system is provided for communication
`between nodes‘ The system can be used, e-g-1 when one
`node can be een?sured for beseband bus topology win
`munication, such as LocalTalk TM communication.
`The node can communicate using the entire bandwidth
`of the medium, such as 230 Kbps bandwidth, even
`though other nodes are connected to the network using
`the hub card. Preferably, the hub card includes a multi
`processor system with a shared memory for providing
`high internal effective bandwidth communication, such
`as 15 Mbps communication. A proxy scheme is pro
`vided so that the hub topology is transparent to any
`“(:16 ‘flue? can operate as thm’gh ‘1 were con?gured m
`a “5 °P° °gy'
`
`-
`
`-
`
`-
`
`_
`173] Asslgnee: Unsermm-Bess, 1116-, Salim Clara,
`C3111:
`[21] Appl. No.: 331,217
`[22] Filed:
`Mm" 30, 1989
`[51] 1m. (:1.5 ........................................... .. H04L 12/44
`[52] us. 01. ...................... .. 370/61; 370/94.3
`[58] Field of Search ..................... .. 370/85.1, 94.3, 61,
`370/67, 85.13, 85.14, 91, 92, 85.4, 60.1, 85.3, 66,
`68, 60; 379/88; IMO/825.03, 825.52
`.
`References Cited
`U~S- PATENT DOCUMENTS
`4,058,672 11/1977 Crager et a1,
`4,549,047 10/1985 Brian et a1. ..
`18;
`gaidya
`- - - - - - - ~
`4,716,408 12/1987 O’Connor et a].
`4,751,701 6/1988 ROOS et a]. ..... ..
`
`370/61
`379/88
`9 - - - e '
`6?
`.... .. 370/854
`370/85.3
`
`.
`
`[56]
`
`,
`
`,
`
`amo et
`
`. ............. ..
`
`4,769,812 9/1988 Shimizu . . . . . . . .
`
`. . . .. 370/67
`
`4,771,420 9/ 1988 Deschaine ........................... .. 370/68
`
`15 Claims, 6 Drawing Sheets
`
`0|
`
`10!
`
`. llb
`
`166
`,5,
`clSc
`
`15°
`‘u
`la.
`
`r149
`sun-9110111
`_—" PROCESSOR
`511D
`IITSIGFIACCE
`
`1411
`
`"9
`
`—-
`
`I“
`
`1281
`w
`5
`sumo
`_ 11010111
`
`clGd
`m
`SUB-GROUP
`m
`|M\D_£_____- PMC5551111
`I
`AND 1
`
`"Him-M11111“ c 16h
`1811
`'
`.
`.
`r181
`18+
`.
`[I61
`“5'9"”?
`I!)
`‘ PROCESSOR
`5k
`AID
`m1~u-L———-—— urges:
`|6l
`|a|~o-—L————————-‘
`in
`In
`SUB-GROUP
`I611
`nocssson
`18W '
`"0
`160
`|,,,-6_-L—-—---— Imam:
`|6p
`to“
`l8p~D—-L—__'_
`016
`
`B
`/
`
`22%
`
`12
`
`1°
`
`80186
`D “m
`BASE
`noczsson
`512 1 m1
`161 [men
`l
`
`24
`
`26
`
`IEO“
`IOWLE
`
`1
`
`P10 IITERFIBE
`
`Petitioner Apple Inc. - Ex. 1012, p. 1
`
`

`
`US. Patent
`
`Aug. 17, 1993
`
`Sheet 1 of 6
`
`5,237,566
`
`I
`
`3
`
`a
`
`
`5a.. 2::
`
`:2: 5%.".
`:25 § .5. v. Na
`
`i w.
`
`E96:
`3525
`E: n :2
`
`5882:
`“528.23
`
`22
`
`S25;
`“53
`
`@388:
`.5¢5.==w
`
`E2
`
`355?
`22:
`
`3:52. 0:
`
`:388:
`$25.25
`
`==
`
`E5885
`@8555
`
`2:
`
`85:25
`22:
`
`Petitioner Apple Inc. - Ex. 1012, p. 2
`
`

`
`Petitioner Apple Inc. - Ex. 1012, p. 3
`
`

`
`Petitioner Apple Inc. - Ex. 1012, p. 4
`
`

`
`US. Patent
`
`Aug. 17, 1993
`
`Sheet 4 of 6
`
`5,237,566
`
`mm PROCESSOR
`(59a
`ADDRESS SPACE 8000:”
`P II
`RARED
`BUFFER
`MEMORY
`
`(59b
`8802;)“
`P #2
`RARED
`BUFFER
`MEMORY
`
`59c‘
`92/30
`£1? #3
`RARED
`BUFFER
`IEMDRY
`
`/ 59‘
`98:00
`LIE/#4
`SHARED
`BUFFER
`IEIDRY
`
`SUBDRDUP
`PROCESSOR
`ADDRESS
`SPACE
`60o\
`20°00“
`
`60b) 8000h
`
`H5- 44
`
`“P #1
`
`up #2
`
`“P #3
`
`MP #4
`
`5A
`R/ V!
`
`£21
`R10
`
`6_22
`
`R/D
`
`L!
`RID
`
`_5_2_e
`
`RID
`
`El
`
`Q2!
`RID
`
`Q1
`RID
`
`60C}
`
`‘
`
`0000b
`
`£21
`
`R/0
`
`‘A
`RI!
`
`E
`RID
`
`60d\
`saooon % - 522
`RID
`
`R/0
`
`Q22
`RID
`
`‘32
`
`RN
`
`600‘
`40000
`
`F I6 45.
`
`Petitioner Apple Inc. - Ex. 1012, p. 5
`
`

`
`US. Patent
`
`Aug. 17, 1993
`
`Sheet 5 of 6
`
`5,237,566
`
`_
`
`_ L
`
`
`
`
`
`_ E 2 _ a E 3.. _ E a. a". _
`
`
`
`I l l I l I l l l l l l | | | l l I ll Ill.l..ll.ln.lll.lll.lll|llllll_
`
`_ .(é _ 55 .2: _ we? a? ‘E E5: _ " (“NV 3 Ex 2.3 E, E :52: n
`
`_ 2.. :2 35 y 5 2:8 _
`
`m a: a as: gum“ = m: 2 " é
`
`
`_ .E .iiv u L E. 1-1L- Ful?l. i . _ lw /\ _ _ _ _ /\ _
`u L 2.. 8w 5%“ III»; 5:5. “ 2 a? “A?! _ 3w 0 _ .E T -. gnu . u \ 2a“
`5. _
`
`
`
`_ £Q-\\r.lll|l- rlll l. I L ,llllllru?? _
`
`
`
`
`
`" 31L 0N? _ . 3v 2.3 L2 L§r_ s. _
`
`
`
`rllllmgutlllrb? l l I l l . l l I I I l l l I I l I I I I l | l I I I I I I l I ll.
`
`
`
`n . l _ ,ré _
`
`_ _
`
`_ llllJ s<_~-s<_~ Id _ _
`_ Q as 53%. n
`.5 5:2 _. a ...
`
`
`
`
`
`n a a. ,2? n
`" Es. 5. =§w= cm "
`
`
`
`:7. ma 6.; at“ ||||||||||||||||| .. I ¢_
`
`‘g l oi 5L a7.” a. . u
`
`
`
`
`2.. E E 2.. “will... a?! _
`
`
`
`
`
`E 2 EN . 2N * :N 2., n _
`
`
`
`
`
`E a “mull... ‘Na 2 x E u
`
`
`
`\ mill.- 5. as: _
`
`.m. GD‘ llll I embarks? .smr| 1 I I.
`
`
`
`_. =2? :2: _
`
`
`
`
`
`NmN wow; New . . .\=~_ _
`
`_
`
`Petitioner Apple Inc. - Ex. 1012, p. 6
`
`

`
`US. ‘Patent
`
`Aug. 17, 1993
`
`Sheet 6 of 6
`
`5,237,566
`
`[In
`
`F. F m
`w w h.
`
`z.
`
`1‘! If
`
`mm.“
`mm
`ms
`
`R
`U M
`M m M k
`
`N m
`
`DESTINATI
`
`uupwus
`SOURCE
`TYPE
`Emmi Him‘ 1.0.
`FIELD
`lI22
`H24
`m Is
`FIG 6.
`
`m. f
`W Lu
`
`JU-.|
`
`m- -i-
`mJU
`SQ.
`
`m
`
`Ml l l | I | II |
`
`
`
`(PU: w. m
`
`A B 0
`
`4L5;
`
`m- .M W...
`
`.. m, m
`
`1
`
`w. mm mm m mm mm
`
`E m
`
`I
`80H 80H
`
`0 80H
`
`254
`255
`
`3
`
`inc; 8.
`
`Petitioner Apple Inc. - Ex. 1012, p. 7
`
`

`
`5
`
`10
`
`25
`
`35
`
`20
`
`5,237,566
`2
`communicate at about 230 Kbps, if no other nodes were
`using the system for communication. A system with
`multiple nodes, each of which is attempting to make
`communication over the medium, results in an effective
`bandwidth for each node which is less than 230 Kbps.
`The amount of reduction of bandwidth depends on the
`number of nodes added and the amount of network
`activity attempted by each node.
`.
`The LocalTalk TM network system includes a num
`ber of well-de?ned characteristics. Access to the bus is
`managed by a protocol known as “Carrier Sense Multi
`ple Access With Collision Avoidance” (CSMA/CA).
`The LocalTalkTMsystem also includes protocols for
`assigning node identi?ers, addressing particular nodes,
`assembling and appending data transmission signals,
`such as frames, error detection, and the like. Because of
`the speci?city of such protocols, as well as the speci?c
`ity of the associated hardware and software, it is not
`possible to connect a LocalTalk TM network or node to
`another type of network without extensive modi?ca
`tion. A more complete description of LocalTalk TM is
`found in Inside Appletalk, by Gursharan S. Sidhu, Rich
`ard F. Andrews, and Alan B. Oppenheimer, Apple
`Computer, Jul. 14, 1986, incorporated herein by refer
`ence to the extent needed for understanding the inven
`tion.
`Interfacing devices, generally known as “gateways,”
`have been developed for connecting a LocalTalk TM
`network to another type of network. These gateways,
`however, do not solve the problem of decreasing band
`width resulting from increasing nodes, and thus merely
`pass on this problem to another network.
`In spite of these difficulties, the LocalTalk TM net
`work remains a heavily implemented system, and many
`installations are in existence which are con?gured to use
`or to be connected to such a system. Additionally, many
`types of software have been written for the purpose of
`using a LocalTalk TM network.
`'Accordingly, it would be useful to provide a network
`system which can accommodate existing hardware and
`software intended for previous decreasing-bandwidth
`systems, but which solves the problem of decreasing
`bandwidth, i.e., which permits each node to communi
`cate over the medium at the full medium bandwidth.
`
`1
`
`NETWORK HUB FOR MAINTAINING NODE
`BANDWIDTH IN A SINGLE-NODE NETWORK
`
`The present invention relates to a hub-type data com
`munications network and, in particular, to a network
`hub which maintains full media bandwidth for a plural
`ity of nodes.
`BACKGROUND INFORMATION
`A multitude of devices and methods for data commu
`nication over a network system are known. Network
`systems can be characterized by a number of design
`aspects, each typically having particular advantages
`and disadvantages. One design aspect of a network
`system is known as the “network topology.” Examples
`of topologies which are in use are a bus topology, a ring
`topology, and a star or hub topology. In a bus topology,
`a single linearly con?gured communications line is pro
`vided, and each data terminal or node connects to the
`line at some point along its length. In a ring topology,
`each node or data terminal communicates directly with
`two neighbors arranged in a topologically circular man
`ner. In a star topology, a central unit or hub communi
`cates to each node along dedicated lines.
`Another aspect of network design involves the data
`transfer rate or bandwidth type of a communication
`system. The two basic bandwidth types are broadband
`systems and baseband systems. In a broadband system,
`several data terminals share a single communication
`medium through a frequency-division scheme. In a
`baseband con?guration, the signals are unmodulated,
`and sharing of a medium requires time division between
`the nodes. In either system, when more than one data
`terminal is con?gured for transmission along a single
`medium at the same time, neither data terminal can have
`exclusive use of the medium over the entire theoreti
`cally available bandwidth for that medium. Thus, the
`effective bandwidth, i.e., the data transfer rate which
`actually results between two nodes, becomes reduced
`40
`when multiple nodes or data terminals, each con?gured
`for communication, are connected to a single medium.
`A particular network system typically is designed for
`particular types of network topology and bandwidth
`type. For this reason, it is normally not possible to pro
`vide a data terminal and associated software which is
`con?gured, for example, for a bus topology and, with
`out modi?cation, construct such terminals in a ring or
`star topology. Similarly, it is normally not possible to
`connect, without modi?cation, a data terminal con?g
`ured for baseband communication to a broadband net
`work.
`A number of network systems are susceptible to the
`above-noted problem, wherein addition of nodes to the
`system causes an effective decrease in the bandwidth for
`each node. One particular such network system is the
`LocalTalk TM (formerly known as “Appletalk® Per
`sonal Network”). LocalTalkTM and Appletalk® are
`trademarks of Apple Computers, Inc., Cupertino, Calif.
`The LocalTalk TM system is a baseband network that
`uses a bus topology. The LocalTalk TM system is de
`scribed as having a maximum or upper-limit bandwidth
`in its present con?guration. In present descriptions of
`this product, the maximum bandwidth or raw data rate
`is stated to be 230.4 kilobits per second (Kbps). Of
`65
`course, it is possible that future versions of Local
`Talk TM will have a higher maximum bandwidth. In the
`present system, a single node on such a network could
`
`45
`
`50
`
`55
`
`60
`
`SUMMARY OF THE INVENTION
`The present invention includes using nodes or tenni
`nals which are con?gured for a bus topology baseband
`network system, such as a LocalTalk TMnetwork sys
`tem, and connecting such nodes or terminals in a star or
`hub topology. The hub is designed to emulate the bus
`topology in the sense that the nodes or terminals trans
`mit and receive communications using substantially the
`same protocols as originally used, for example, Local
`Talk TM protocols. However, because each node or
`data terminal is connected directly to the hub by a dedi
`cated line, each node or terminal can employ the entire
`bandwidth available for that dedicated line. In the case
`of a LocalTalk TM node, this bandwidth is 230 Kbps.
`The present invention achieves a point-to-point con
`nectivity or a single node network. It is a network in the
`sense that one node can communicate with other nodes.
`However, the network is single-node in the sense that
`each node has substantially the same bandwidth capabil
`ity it would have if it were the only node on the net
`work.
`One general method which might be used to achieve
`emulation of a bus topology without substantially de
`
`Petitioner Apple Inc. - Ex. 1012, p. 8
`
`

`
`. 5
`
`30
`
`5,237,566
`4
`3
`ity during RTS-CT S protocol according to the present
`grading performance would be to provide a hub which
`invention.
`performs the necessary processing at high rates of
`speed. Such a system would require both a fast proces
`DETAILED DESCRIPTION OF THE
`sor and a fast memory; however, it would also be ex
`PREFERRED EMBODIMENTS
`pected to be prohibitively dif?cult to build and main
`Referring to FIG. 1, a con?guration for the hub 8 of
`tain, as well as prohibitively expensive. Accordingly, in
`the preferred embodiment is depicted. Preferably, the
`‘the preferred embodiment, the desired emulation is
`hub 8 is mountable on a single board, such as a
`achieved while avoiding the use of extremely fast and
`9"X14.5" board. Preferably, the board is compatible
`expensive processors and memory.
`with existing network hardware and/or software, such
`The preferred embodiment involves a proxy system
`as the Access/One TM system produced by Unger
`in which the hub sends and receives data emulating the
`mann, Bass, Inc., of Santa Clara, Calif. As depicted in
`original network protocols by formulating and using
`FIG. 1, the hub 8 includes three major portions: a main
`proxy messages. By using these proxy messages, the
`processor unit 10; a shared memory unit 12; and four
`actual star topology is “transparent” to the nodes,
`subgroup processors 14a, 14b. 14c, and 14d. Each of the
`which can continue to operate substantially as if they
`subgroup processors 14a-14d is connectable to up to
`were connected to a bus topology, albeit at a full, e.g.,
`four nodes 18 using four communication lines or chan
`230 Kbps, bandwidth.
`nels each 16a-16p. Preferably, the communication lines
`In addition to formulating and providing the proxy
`or channels 16a, 16b, 16c, 16d are single 22 or 24 AWg
`messages as needed, the hub also provides for very high
`shielded or unshielded twisted pair wire, and can be
`speed data communication, such as for communication
`about 300 meters in length, preferably up to about 330
`from one node to another node, or from one node to
`meters in length. In addition to permitting communica
`another network. The high speed communication, up to
`tion among the nodes 180-18p, the hub 8 is used to
`about 15-16 megabits per second (Mbps) or more is
`provide communication from one or more of the nodes
`achieved by use of a shared memory system in which
`1811-18]; to another network. Each node 18a-18p can
`25
`data received from one node can be stored in a memory
`include a single data terminal or can include a plurality
`location, and can be transmitted directly from that
`of data terminals, e.g., serially interconnected in so
`memory location to a destination without writing the
`called “daisy chain” fashion. Communication to an
`data to a second memory location.
`other network is through a connection, such as a bus
`The hub has enough processing power to perform the
`connection, to the card’s backplane (data) bus 22. Inter
`above-described emulation and the above-described
`face circuitry in the form of a media module 24 is pro
`high speed communications with sufficient rapidity that
`vided to con?gure the communication for transmittal to
`communications to and from individual nodes is not
`another medium. The interface circuitry 24 can be pro
`impaired. In this way, the effective bandwidth for each
`vided for communication with another LocalTalkTM
`node is the full bandwidth theoretically available for the
`network, an Ethernet TM network, a token ring net
`medium to which the node is connected. The necessary
`work, or other types of networks. Preferably, a proces
`processing power is provided, in the preferred embodi
`sor interface controller (PIC) 26 is provided for pur
`ment, by a multiprocessor system. In the preferred sys
`poses of system monitoring, error detection and correc
`tem, four microprocessors are provided, each of which
`tion, and similar functions.
`processes communications to and from four nodes, to
`In operation, when it is desired to establish communi
`provide a total capacity of 16 nodes. A ?fth processor is
`cation between a ?rst node, e.g., 18c, and a second node,
`provided to coordinate the hub operation. A shared
`e.g., 181', the ?rst node 180 initiates communication over
`memory is provided with each of the four node proces
`its communication line 16c. The corresponding sub
`sors having read privileges throughout the shared mem
`group processor 140 routes the communication, which
`ory, and exclusive write privileges in a portion of the
`might be a protocol signal or frame, or a data signal or
`shared memory.
`frame, to a portion of the shared memory unit 12 in
`which that subgroup processor 140 has permission to
`write. The main processor 10 can read the contents of
`the memory in the shared memory unit 12 and, using
`methods described more thoroughly below, can deter
`50
`.mine the destination of the communication which has
`been received. When the destination is the second node
`181', the main processor 10 can communicate to the
`appropriate subgroup processor 14c by writing a mes
`sage in the shared memory unit 12, which can be read
`by the subgroup processor 14c, as described more fully
`below. The subgroup processor 14c then accesses the
`portion of the shared memory unit 12 where the com
`munication from the ?rst node 18c is stored, and routes
`this communication along the appropriate communica
`tion line 161' to the intended destination node l8i. When
`the intended destination node is other than one of the 16
`nodes 18a-18p, which directly communicate with the
`hub, the main processor 10 con?gures the communica
`tion, as necessary, for transmittal to another medium,
`using the interface circuitry of the media module 24.
`The main processor 10 then routes the communication,
`properly con?gured and framed, as necessary, to the
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`FIG. 1 is a schematic block diagram of the hub inter
`face according to one embodiment of the present inven
`tion;
`FIG. 2 is a block diagram of the main processor de
`picted in FIG. 1;
`FIG. 3 is a memory map for the main processor mem
`Ory;
`55
`FIG. 4A and 4B is a memory map for the memory
`shared by the subgroup node processors;
`FIG. 5 is a block diagram of a single one of the sub
`group processors depicted in FIG. 1;
`'
`FIG. 6 is a schematic diagram of a delimited frame
`according to an AppleTalk ® Link Access Protocol;
`60
`FIG. 7 schematically illustrates the relative timing of
`bus, source node, and destination node activity during
`acquisition and RTS-CTS protocol according to a pre
`vious networking scheme;
`FIG. 8 is a schematic diagram of a Heard From Vec
`tor Table; and
`FIG. 9 schematically illustrates the relative timing of
`source-hub channel and destination-hub channel activ
`
`40
`
`45
`
`Petitioner Apple Inc. - Ex. 1012, p. 9
`
`

`
`10
`
`25
`
`20
`
`5,237,566
`.
`5
`backplane (bus) 22 whence the message is ultimately
`sor’s I/O address (OCOh). Such a read operation causes
`the I/O interrupt PAL 76 of the subgroup processor
`transmitted to its destination.
`Referring now to FIG. 2, in the preferred embodi
`(FIG. 5) to issue a signal. For the ?rst subgroup proces
`sor 140, the signal is provided on line 770 (seen in FIGS.
`ment, the main processor unit 10 includes a processor,
`5 and 2). Similar signals can be provided over lines 77b,
`such as an Intel 80186 CPU-based processor 28. As
`described below in connection with FIG. 3, the proces
`77c, and 77d (FIG. 2) from subgroup processors 14b,
`14c, and 140’, respectively. Any of these signals 77a-77d
`sor 28 can address an address space of 1 Mbyte. Of this,
`640 k bytes are directly addressable by the main proces
`sets a corresponding ?ip-?op 79a-79d, which triggers
`sor, distributed between a 512 k byte DRAM 52 and a
`one of the microprocessor 28 interrupt lines 81, 83. The
`128 k byte shared memory unit 12 accessed through a
`Model 80186 microprocessor, which, as noted above, is
`four-way address bus 32a, 32b, 32c, 32d via a memory
`the microprocessor of the preferred embodiment, has
`controller or arbitor 12b (FIG. 5) and through a data
`only two interrupt lines available 81, 83. The ?rst and
`bus 270. An additional 128 k bytes of the address space
`second subgroup processors effect an interrupt on inter
`is used for a 128 k programmable read only memory
`rupt line number two (INTZ) 81 of processor 28 via an
`(PROM) 224. The communication to the shared mem
`OR gate 85a. The third and fourth subgroup processors
`ory unit 12 is the means by which the processor 28
`14b, 14c effect an interrupt on interrupt line number
`communicates with the subgroup processors 14a-14a'.
`three (INT3) 83 of the processor 28 via an OR gate 85b.
`A l6-bit output port is provided on ?rst and second
`The processor 28, in the interrupt handling routine, then
`output port chips 34a, 34b. A reset signal 35 from the
`reads the status ports 441', 44]‘, 44k, 441 to determine
`processor 28, when asserted, places the output port
`which subgroup processor 14a-14a' caused the inter
`chips 34a, 34b in a reset or start mode when the signal 35
`rupt. The processor 28 resets the interrupt ?ip-?ops by
`is asserted and, when the signal 35 is deasserted, places
`performing an I/O write to one of the four I/O ports
`the output port chips 34a, 34b in normal or operational
`460-4611. The ?rst, second, third, and fourth ports 46a,
`mode. Bit 4 (signal line 36d) of the output port chip 340
`46b, 46c, 46d are used to effect ?ip-?op resets after
`is the enable bit for the media module 24. When bit 4 is
`interrupts originating from the ?rst, second, third, and
`asserted, typically after power-up, the media module 24
`fourth subgroup processors 14a, 14b, 14c, 14d, respec
`is in a reset mode. Deassertion of bit 4 takes the media
`tively.
`module out of reset mode, whereupon it performs diag
`Access to the I/O ports 46a—46d is via a 3-to-8 de
`nostic self-tests, then begins normal operation. Bits
`coder 190, controlled by an I/O chip-select line 192 and
`12-15 (signal lines 36m-36p) of the output port chip 34b
`a write line 194. The 3-to-8 decoder 190 can send chip
`are used for the reset for each of the subgroup proces
`enable signals to the output port chips 34a, 34b over a
`sors 14a-14d, as described below. Bits 8-11 (signal lines
`chip-enable line 193. The U0 chip-select signal 192 is
`36i-36I) of the output port chip 34b are reserved for use
`also used for control of the input registers 42a, 42b. In
`with a high-speed option board. The high-speed option
`this case, the output port chip-select signal 195 results
`board (not shown) is an accessory which can be pro
`from the OR-ing of the I/O chip-select signal 197 with
`vided to allow the hub 8 to operate at an increased
`the read signal 199 from the main processor 28. The full
`speed, such as 3-4 times normal LocalTalk TM speeds.
`physical lines for the I/O chip-select signal 197 and read
`Such a board will typically comprise logic cell arrays
`signal 199 between the processor 28 and the OR gate
`con?gured as reclocking circuitry. Bits 0 and 1 (signal
`201 are not shown.
`lines 36a, 36b) of the output port chip 34a are used for
`The main processor 28 accesses the 512 k bytes of
`LED (light-emitting diode) control.
`DRAM 52 via a high-speed memory access controller
`A 16-bit input or status port is provided on ?rst and
`(HMAC) 48. The HMAC 48 also conducts the refresh,
`second input port chips 42a, 42b. Status bit 0 (signal line
`parity generation, checking, and test functions for the
`44a) of the input port chip 420 is read off the backplane
`DRAM 52. The processor 28 communicates with the
`bus 22 to provide an indication of the mode in which the
`HMAC 48 over two bus lines 196 and 198, under con
`backplane is operating (e.g., Ethernet TM mode, token
`trol of four signal lines 202, 204, 206, 208, and a clock
`ring mode, etc.). Status bit 3 (signal line 44d) of the
`signal 210. The ?rst bus 196 is a dual function bus which
`input port chip 420 indicates whether the media module
`acts either as an address bus for bits 0-15 or a data bus
`24 is enabled, while status bits 12-15 (signal lines
`for bits 0-15. The second bus 198 acts as an address bus
`44m-44p) of the input port chip 42b indicate the state of 50
`only for bits 16-19. The read enable 202 and write en
`each subgroup processor halt line. Status bits 4-7 (signal
`able 204 lines control the timing of reads and writes to
`lines 44e-44h) of the input port chip 420 are reserved for
`the 5l2 k DRAM 52. The address latch enable line 206
`use with the high-speed option board, described above.
`controls the timing of _memory addressing. The byte
`Status bit 1 (signal line 44b) of the input port chip 420 is
`high enable line 208, when energized, indicates that a
`used in connection with board temperature sensing.
`write operation is to be performed on the high byte (bits
`Status bits 8-11 (signal lines 441', 44]‘, 44k, 441) of the
`8-15) of a memory location. The byte high enable 208 is
`input port chip 42b are used to identify which of the
`a feature of the 80186 processor which, as noted above,
`subgroup processors 14a-14d has interrupted the pro
`is the preferred model for the processor 28. The 16
`cessor 28 after an interrupt signal is received. Each
`MHz clock signal 210 is used for general timing pur
`subgroup processor 14a-14d can send an interrupt sig
`poses. The HMAC 48, in turn, communicates with the
`nal to the main processor 28. Typically, such interrupts
`media module 24 over an address bus 212 and data/ad
`will not be needed for routine node-to-node messages,
`dress bus 214, controlled by a bus grant signal 216 and
`but are used when a subgroup processor 14a—14d needs
`bus request signal 218. The HMAC 48 communicates
`to convey information to the main processor unit 10,
`with the DRAM 52 using a DRAM address bus 220 and
`such as upon occurrence of an error condition. Any of 65
`the subgroup processors 14a-14d (FIG. 1) requiring the
`a DRAM Row Address Strobe (RAS), Column Ad
`dress Strobe (CAS), and Write Enable (WE) control
`attention of the main processor 28 can issue an interrupt
`line 222.
`request by performing a read operation to that proces
`
`35
`
`40
`
`55
`
`Petitioner Apple Inc. - Ex. 1012, p. 10
`
`

`
`15
`
`20
`
`25
`
`7
`The HMAC 48 also provides the processor 28 access
`to the PROM 224, using latched address bus 226. The
`PROM 224, controlled using a PROM chip select line
`228, contains boot memory The PROM 224 communi
`cates with the 512 k DRAM 52 via a data bus line 230.
`Because there are ?ve processors 10, 14a, 14b, 14c,
`14d which must have access to the shared memory unit
`12, speci?c hardware, including a memory-control pro
`grammable array logic (PAL) 92 residing in each of the
`subgroup processors 14a, 14b, 14c, 14d (FIG. 5), is pro
`vided to control access of these processors to the shared
`memory unit 12. In the preferred embodiment, the ac
`cess is by a so-called "round-robin scheme,” in which
`the main processor unit 10 and each of the subgroup
`processors 14a, 14b, 14c, 14d are provided access for a
`predetermined amount of time in a sequential repeating
`fashion. A number of “round-robin” schemes are possi
`ble. In one preferred embodiment, access is divided
`among 16 recurring, sequential time slots. All even time
`slots (0, 2, 4, 6, 8, 10, 12, 14) are allocated for access by
`the main processor 28. Time slots 1 and 9 are allocated
`for access by the ?rst subgroup processor 140. Time
`slots 3 and 11 are allocated for access by the second
`subgroup processor 14b. Time slots 5 and 13 are allo
`cated for access by the third subgroup processor 14c.
`Time slots 7 and 15 are allocated for access by the
`fourth subgroup processor 14d. The duration of the
`time slots varies according to the amount of contention
`for memory. When there is no contention, the main
`processor 28 will complete access in O-wait state time,
`and the subgroup processors 14a, 14b, 14c, 14d will
`complete access in l-wait state time. As contention
`increases, wait states are added to both the main proces
`sor times slots and the subgroup processor time slots.
`Referring now to FIG. 3, the distribution of the mem
`ory address space which is addressable by the processor
`28, is shown. That portion 54 of the address space be
`tween addresses 80000 and 9FFFF is reserved for ad
`dressing the shared memory unit 12, described more
`fully below. The media module 24 will not have direct
`40
`access to the shared memory address space 54. The
`lower portions 56a, 56b (addresses 00000-7FFFF) of
`the address space represent memory which is used by
`the main processor 28 in its normal operations, and is
`memory space which is shared with the media module
`45
`24. The upper memory (EOOOO-FFFFF) 58 portion of
`the address space is used to address the PROM 224,
`which is used for booting the processor 28.
`Referring now to FIG. 4A, a map of the address
`space 54, which is used by the main processor unit 10 to
`address the shared memory unit 12, is depicted. FIG. 4B
`is a table of the address space used by the subgroup
`processors 14a-14a' to address the same memory loca
`tions. Although the memory locations depicted in
`FIGS. 4A and 4B are the same, the addresses used by
`the main processor 28 (FIG. 4A) differ from the ad
`dresses for the same memory locations which are used
`by the subgroup processors 14a, 14b, 14c, 14d (FIG.
`4B). The addresses 59a, 59b, 59c, 59d, marking bound
`aries within the shared memory address space 54 used
`by the main processor unit 10, are indicated across the
`top of FIG. 4A. The addresses 60a, 60b, 60c, 60d, 60e,
`marking boundaries within the shared memory address
`space 54 used by the subgroup processors 14a, 14b, 14c,
`14d, are indicated along the left side of FIG. 4B. The
`65
`columns of FIG. 4B indicate, for each subgroup proces
`sor l4a—14d, whether that processor has read only
`(R/O) access to the block of memory depicted in that
`
`5,237,566
`8
`row, or has read and write access (RM to the block of
`memory depicted in that row. As seen in FIG. 4B, the
`shared memory address space is con?gured so that each
`of the subgroup processors 14 has read capability or
`permission in the entire shared memory unit 12. How
`ever, each of the subgroup processors 14a-14d has per
`mission to write, to the exclusion of the other subgroup
`processors, only in certain prede?ned portions of the
`shared memory unit 12. For example, the ?rst subgroup
`processor 14a can read from any of the shared memory
`blocks, as seen from the designations in the fast column
`620, 62e, 621', 62m. However, the ?rst subgroup proces
`sor 140 can write only in the ?rst 32 k memory block
`620 of the shared memory unit 12. None of the other
`subgroup processors 14b-14d can write in this block, as
`shown by the R/O designations in the remaining col
`umns 62b, 62c. 62d of the ?rst row. Similarly, the sec
`ond subgroup processor 1412 can read from any of the
`shared memory locations, as seen from the designations
`in the second column 62b. 62)‘: 62]’, 62n, but can write in
`only one of the 32k blocks of shared memory 62].~ None
`of the other subgroup processors 14a, 14c-14d can write
`in this block of memory, as shown by the R/O designa
`tion in the remaining columns 62e. 62g, 62h of the sec
`ond row.
`A number of schemes can be used to alert one of the
`subgroup processors 14d-14d that there is a message in
`memory which that subgroup 14a-14d should access.
`According to one scheme, each subgroup processor
`14a-14d is assigned a portion of the shared memory unit
`12 as a “pointer” area. When a message is written any
`where in the shared memory unit 12 which a particular
`subgroup processor 14a~14d should access, a pointer is
`written to the pointer area for that subgroup processor.
`The pointer can be, e.g., the starting address for the
`memory location where the message is stored. As each
`subgroup processor gains access to the shared memory
`unit 12, it scans the pointer area which has been as
`signed to it and, if any pointer has been written therein,
`can read from the memory location indicated by that
`pointer.
`The resulting shared memory scheme provides for