`United States Patent
`5,041,963
`[11] Patent Number:
`Ebersole et al.
`
`[45] Date of Patent: Aug. 20, 1991
`
`[54]
`
`[75]
`
`[73]
`
`[21]
`
`[22]
`[51]
`
`[52]
`
`[58]
`
`[56]
`
`LOCAL AREA NETWORKWITH AN ACTIVE
`STAR TOPOLOGY COMPRISING RING
`CONTROLLERS HAVING RING MONITOR
`LOGIC FUNCTION
`
`Inventors: Ronald J. Ebersole, Beaverton;
`Frederick J. Pollack, Portland, both
`of Oreg.
`Intel Corporation, Santa Clara, Calif.
`
`Assignee:
`
`Appl. No.: 291,700
`
`Filed:
`
`Dec. 29, 1988
`
`Int, C15 ceca GO6F 15/16; GO6F 11/30;
`GO6F 13/36; GO6F 13/00
`ULS. Ch.eee) 364/200; 364/221.6;
`364/221.7; 364/229.3; 364/230; 364/240;
`364/240.7; 364/241.1; 364/241.8; 364/242;
`364/242.95; 370/60; 370/94.1
`Field of Search.................. 364/200, 900; 370/85,
`370/86, 60, 94.1
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`6/1982 Girardiee eeeeeeeee 370/86
`4,334,305
`4,482,980 11/1984 Korowitz etal.
`.
`
`4,489,379 12/1984 Lanier etal. .....
`4,493,021
`1/1985 Agrawal etal. ..
`
`4,539,655 9/1985 Trussell et al.
`..
`4,754,395
`6/1988 Weisshaaret al.
`4,771,391
`9/1988 Blasbalg ........
`
`4,777,591 10/1988 Changetal. .
`4,835,673
`5/1989 Rushby et alo cecsccsecenene 364/200
`
`4,888,726 12/1989 Struger et al.0.0 364/900
`
`Primary Examiner—Stuart N. Hecker
`Assistant Examiner—George C. Pappas
`Attorney, Agent, or Firm—Owen L. Lamb
`
`ABSTRACT
`[57]
`A star local area network includes a ring bus hub (4)
`capable of being connected to a plurality of nodes(3, 5,
`_9) geographically distant from the hub by means of low
`speed serial
`links (18, 19, 21, 28). The nodes include
`processor means (2, 30, 31) for creating messages for
`transfer on the network. A plurality of duplex commu-
`nication links (18, 19, 21, 28) connect the nodes to the
`ring bus hub (4). The hub (40) is comprised ofa plurality
`of ring controllers (10, 12, 14, 16) driven by a common
`clock source (7). Each ring controller is connected by
`means of a number ofparallel lines to other ring con-
`trollers in series to form a closed ring. Each one (3) of
`the plurality of nodes is geographically distant from the
`hub (4) and is connected to a corresponding one (10) of
`the ring controllers by means of one (18, 19) of the
`duplex communication links. The node controllers in-
`cluding node interface means (40) for transmitting the
`messages as a contiguous stream of words on the duplex
`communication link. The ring controllers include ring
`bus interface means (42) for forming the messages into
`discrete data packets for insertion onto the ring bus and
`means (32, 34) for bufferring data messages received
`form the node and overthe ring bus.
`
`10 Claims, 2 Drawing Sheets
`
`afo Ls
`FNODE#3
`"5
`| (RING HUB
` LINODEWT 3
`
`
`
`RING MONITOR
`2
`
`
`(NODE ADDRESS
`
`
`(NODE {)
` CONTROLLER
`
`
`(NODE ADDRESS
`
`
`
`|||\|i|{
`
`Lemeeeeeee
`
`| t I | | I I||
`
`r
`
`RING
`CONTROLLER
`
`CONTROLLER
`(NODE 2)
`
`
`
`Petitioner Riot Games,Inc. - Ex. 1031, p. 1
`
`Petitioner Riot Games, Inc. - Ex. 1031, p. 1
`
`
`
`U.S. Patent
`
`Aug, 20, 1991
`
`Sheet 1 of 2
`
`5,041,963
`
`aanLo A ao
`[NODE#3
`1 TRING HUB
`1254——«LNODERA 3
`1
`t
`'
`PROTOCOL
`|
`PROCESSOR
`1
`I
`mi
`|
`
`0)
`
`RING
`CONTROLLER
`
`A
`
`prcc-oa----------
`
`(NODE ADDRESS
`
`
`F IG. {
`
`PROTOCOL
`PROCESSOR
`
`PINS
`
` SHARED 44 MODE 43
`SELECT
`
`FIG.2
`
`Petitioner Riot Games,Inc. - Ex. 1031, p. 2
`
`Petitioner Riot Games, Inc. - Ex. 1031, p. 2
`
`
`
`U.S. Patent
`
`Aug. 20, 1991
`
`Sheet 2 of 2
`
`5,041,963
`
`SYSTEM
`BUS
`
`
`
`
` CONTROLLER
`
`
`AP
`BUS 0
`
`(FIG.2) St
`
`TO NODE
`
`CONTROLLER
`
`(FIG.2)
`
`
`
`FIG.5 wessase rormar
`94
`96
`
`98
`
`FIG.GD icee 802.3 STANDARD GROUP MESSAGE FORMAT
`
`122
`
`120
`124
`I/G
`{
`CMMI
`reserved
`FIG. 7a inoivinval Locat ADDRESS FORMAT
`130
`432434
`
`126
`
`128
`LID
`
`136
`
`FIG.7b crovr Locat aooress Formar
`
`Petitioner Riot Games,Inc. - Ex. 1031, p. 3
`
`Petitioner Riot Games, Inc. - Ex. 1031, p. 3
`
`
`
`1
`
`5,041,963
`
`LOCAL AREA NETWORKWITHANACTIVE STAR
`TOPOLOGY COMPRISING RING CONTROLLERS
`HAVING RING MONITOR LOGIC FUNCTION
`
`CROSS REFERENCES TO RELATED
`APPLICATIONS
`
`This application is related to U.S. Pat. No. 4,939,724,
`granted on July 3, 1990 “Cluster Link Interfacez> of
`Ronald Ebersole, “Ring Bus Hub for a Star Local Area
`Net-work” Ser. No. 07/291,756 of Ronald Ebersole
`now abandonedand “Node Controller for a Local Area
`Network” Ser. No. 07/291,640 now abandoned of Ro-
`nald Ebersole, all filed concurrently herewith and as-
`signed to Intel Corporation.
`BACKGROUNDOF THE INVENTION
`1. Field of the Invention
`The invention relates to data processing systems and
`moreparticularly to a method and apparatus for inter-
`connecting a plurality of computer workstations with
`1/O devices and other workstations which allows the
`users to share I/O resources.
`2. Description of the Related Art
`A Local Area Network, or LAN,is a data communi-
`cations system which allows a number of independent
`devices to communicate with each other within a mod-
`erately-sized geographical area. The term LANis used
`to describe networks in which most of the processing
`tasks are performed bya workstation such as a personal
`computer rather than by a shared resource such as a
`main frame computer system.
`’
`With the advent of the inexpensive personal com-
`puter workstation, LANs equipped with various kinds
`of desktop computers are beginning to replace central-
`ized main frame computerinstallations. The economic
`advantage of a LANis that it permits a numberofusers
`to share the expensive resources, such as disk storage or
`laser printers, that are only needed occasionally.
`In a typical LAN network a desktop workstation
`performs processing tasks and serves as the user’s inter-
`face to the network. A wiring system connects the
`workstations together, and a software operating system
`handles the execution of tasks on the network. In addi-
`tion to the workstations, the LAN is usually connected
`to a number of devices which are shared among the
`workstations, such as printers and diskstorage devices.
`The entire system may also be connected to a larger
`computer to which users may occasionally need access.
`Personal computers are the most popular desktop work-
`stations used with LANs.
`The configuration of the various pieces of the net-
`workis referred to as the topology. In a star topology a
`switching controller is located at the center or hub of
`the network with all of the attached devices, the indi-
`vidual workstations, shared peripherals, and storage
`devices, on individual links directly connected to the
`central controller. In the star configuration, all of these
`devices communicate with each other through the cen-
`tral controller which receives signals and transmits
`them out to their appropriate destinations.
`A second kind of topologyis the bus topology. In this
`topology, wiring connects all of the devices on the
`LANto a commonbuswith the communications signal
`sent from one end of the bus to the other. Each signal
`has an address associated with it which identifies the
`
`10
`
`.
`
`20
`
`25
`
`35
`
`6
`
`65
`
`2
`particular device that is to be communicated with. Each
`device recognizes only its address.
`The third topology employs a circular bus route
`knownas a ring. In a ring configuration, signals pass
`around the ring to which the devices are attached.
`Both bus and ring networks are flexible in that new
`devices can be easily added and taken away. But be-
`cause the signal is passed from end to end on the bus, the
`length of the network cable is limited. Star topologies
`have the advantage that the workstations can be placed
`at a considerable distance from the central controller at
`the center of the star. A drawbackis that star topologies
`tend to be much slowerthan bus topologies because the
`central controller must intervene in every transmission.
`In a star configuration, the signaling methodis differ-
`ent than in bus or ring configurations. In the star config-
`uration the processor central controller processes all of
`the communication signals. In a bus topology there is no
`central controller. Each device attempts to sendsignals
`and enter onto the bus whenit needs to. If some other
`device trys to enter at the same time, contention occurs.
`To avoid interference between two competing signals,
`bus networks havesignaling protocols that allow access
`to the bus by only one device at a time. The moretraffic
`a network has, the more likely a contention will occur.
`Consequently,
`the performance of a bus network is
`degraded if it is overloaded with messages.
`Ring bus configurations have even more complex
`signaling protocols. The most widely accepted method
`in ring networks is knownas the tokenring, a standard
`used by IBM. Anelectronic signal, called a token, is
`passed around the circuit collecting and giving out
`message signals to the addressed devices on the ring.
`There is no contention between devices for access to
`the bus because a device does not signal to gain access
`to the ring bus; it waits to be polled by the token. The
`advantageis that heavy traffic does not slow down the
`network. However,it is possible that the token can be
`lost or it may become garbled or disabled by failure of
`a device on the network to pass the token on.
`The physical line which connects the components of
`a LAN is calied the network medium. The most com-
`monly used media are wire, cable, and fiber optics.
`Coaxial cable is the traditional LAN medium and is
`used by Ethernet TM, the most widely recognized stan-
`dard. The newest LAN transmission medium is fiber-
`optic cable which exhibits a superior performance over
`any of the other media.
`The Fiber Distributed Data Interface (FDDI) is an-
`other standard. FDDI is a token-ring-implementation
`fiber media that provides a 100 m-bit/second datarate.
`There is an increasing need for high-performance-
`internode communication,
`that is broader I/O band-
`width. The mainframe computer is being extended or
`replaced by department computers, workstations, and
`file servers. This decentralization of computers in-
`creases the amount of information that needs to be
`transferred between computers on a LAN. As comput-
`ers get faster, they handle data at higher and higher
`rates. The Ethernet TM standard is adequate for con-
`necting 20-30 nodes, each with a performance in the
`range of 1 to 5 mips. Ethernet TM is inadequate when
`the performance of these nodes ranges from 5 to 50
`mips.
`An I/O connectivity problem also exists that con-
`cerns I/O fanout and I/O bandwidth. The bandwidth
`problem was discussed above with respect to internode
`communication. The I/O fanout problem is related to
`
`Petitioner Riot Games,Inc. - Ex. 1031, p. 4
`
`Petitioner Riot Games, Inc. - Ex. 1031, p. 4
`
`
`
`3
`that central processing systems are getting
`the fact
`smaller and faster. As the computing speed increases,
`the system is capable of handling more and more I/O.
`However, as the systems get smaller, it becomes harder
`to physically connect the 1/O to the processors and
`memory. Even when enough L/O can be configured in
`the system, the I/O connectivity cost can be prohibi-
`tive. The reason is that the core system (processors and
`memory) must be optimized for high-speed processors
`and memoryinterconnect. The cost of each high-speed
`I/O connection to the core is relatively expensive.
`Thus, cost-effective I/O requires that the connection
`cost be spread over several I/O devices. On mainframe
`computers, the solution to the connectivity problem is
`solved by using a channel processor. A channel proces-
`sor is a sub-processor that controls the transfer of data
`between several I/O devices at a time by executing
`channel instructions supplied by the main processor.
`The main processor system is connected to several of
`these channel processors. Several channels can share
`one core connection.
`It is therefore an abject of the present invention to
`provide an improved LAN that allows high perfor-
`mance interdevice communication and has the ability to
`connect a number of I/O devices to the network.
`
`SUMMARYOF THE INVENTION
`
`The above objectis accomplished in accordance with
`the present invention by providing a LAN which com-
`bines the advantages of a star LAN with a ring bus
`LAN.Thestar configuration provides links to nodes at
`the relatively slow bandwith of the node link. The hub
`of the star uses the relatively high bandwidth of a ring
`bus.
`Nodesattach to the hub of the star through duplex
`communication links. Messages transferred between
`nodes are passed through the hub, which is responsible
`for arbitration and routing of messages. Unlike the prior
`bus topology, or ring topology, each nodeof the active
`star responds only to those messages that are intended
`for it. Routing of messages is accomplished by a destina-
`tion address in the header of the message. These ad-
`dresses are unique to each node and provide the means
`by which the hub keeps the communication between
`nodes independent.
`Theactive star configuration of the present invention
`has the advantagethatit increases network bandwidth.
`In typical networks the performance of the node’s
`means of attachmentto the network is equivalent to the
`network bandwidth. This is because messages can be
`transferred only at the rate of the media, and only one
`message can be transferred at a time. Ethernet, Star
`Lan, FDDI, all exhibit this characteristic as they are
`essentially broadcast buses, in which every node sees
`every other node’s traffic.
`In the active star configuration of the present inven-
`tion, every data communication is an independent com-
`munication between two nodes. Simultaneous, indepen-
`dent communication paths between pairs of nodes can
`be established at the same time. Each path can handle
`data transfers at the link media transmission speed, pro-
`viding a substantial increase in the total network band-
`widths. When two nodes want to communicate with the
`same destination, the hub arbitrates between them and
`buffers the message from the node that is locked out.
`An addressing mechanism maintains a consistent ad-
`dress environment across the complete network that
`facilitates routing. Each node address is composed of
`
`0
`
`_. 5
`
`25
`
`_
`
`40
`
`45
`
`55
`
`60
`
`5,041,963
`
`4
`twofields, one field providing a node address relative to
`the hub it is attached to, and the other field, a hub ad-
`dress relative to the other hubs in the network. The
`combination of these two fields is a unique network
`addressthat is used to route any messagetoits ultimate
`destination.
`The foregoing and other objects, features, and advan-
`tages of the invention will be apparent from the follow-
`ing more particular description of a preferred embodi-
`mentof the inventionas illustrated in the accompanying
`drawings.
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 is a functional block diagram of the Local
`Area Network of the present invention;
`FIG.2 is a functional block diagram ofthe interface
`controller shown in FIG. 1 used in one mode of opera-
`tion as a node controller and in another mode of opera-
`tion as a ring controller;
`FIG. 3 is a diagram of a micro based subsystem;
`FIG.4 is a block diagram ofa cluster I/O subsystem,
`FIG. 5 illustrates the message format,
`FIGS.6a and 66 illustrates the IEEE 802.3 standard
`message format; and,
`FIGS. 7a and 76 show the structure of the Local
`addressfield for a native Cluster node address.
`
`DESCRIPTION OF THE PREFERRED
`EMBODIMENT
`
`The interconnect architecture shown in FIG. 1 is
`designed to transfer blocks of data, called messages,
`between nodesattachedto it. The interconnect function
`is implemented in a single VLSI component known as
`the Cluster Interface Controller (CLIC), shownin FIG.
`2. The transfer of messages between nodes attached to
`the Cluster is controlled by a protocol running in each
`of the nodes, which maintains the orderly access and
`use of the network.
`The present application defines the Cluster architec-
`ture. The CLIC componentis described in application
`Ser. No. 07/291,640. The link between the node con-
`troller and the ring controller is more fully described in
`U.S. Pat. No. 4,939,724.
`The LAN architecture is based on an active star
`topology, as illustrated in FIG. 1. Nodes attach to the
`hub (4) ofthe star through duplex communicationlinks.
`Messages transferred between nodesall pass through
`the hub, which is responsible for arbitration and routing
`of messages. Unlike Ethernet TM or token rings, each
`node sees only those messages that are intended forit.
`Routing of messages is determined by a destination
`address in the header of the message. These addresses
`are unique to each node and provide the means for the
`hub to keep the communication between nodes indepen-
`dent.
`The active star configuration increases network
`bandwidth. In typical networks, the performance of the
`node’s attachment to the network is equivalent to the
`network bandwidth. This is because messages can be
`transferred only at the rate of the media, and only one
`can be transferred at a time. Ethernet T, Starlan TM,
`FDDI, etc. all exhibit
`this characteristic as they are
`essentially broadcast buses,
`in which every node sees
`every other node’s traffic.
`Hub-to-hub connectivity extends the capability of the
`network, providing for a much wider variety of config-
`urations. The network addressing mechanism maintains
`a consistent address ervironment across the complete
`
`Petitioner Riot Games,Inc. - Ex. 1031, p. 5
`
`Petitioner Riot Games, Inc. - Ex. 1031, p. 5
`
`
`
`5,041,963
`
`6
`MESSAGE FORMAT
`
`The message formatis illustrated in FIG. §. Starting
`(80) and ending (92) delimiters are shown separately to
`illustrate the dependency onthe actual link between the
`nodeand the hub. Framing bits are a function ofthe link
`and are removed/regenerated every time a message
`crosses a link boundary. The fields are defined as fol-
`lows:
`SD : Starting Delimiter (Link Dependent)
`DA: Destination Address (6 bytes)
`SA : Source Address (6 bytes)
`L: Length (2 bytes)
`INFO: Information (Up to 4.5 K bytes)
`FCS : Frame Check Sequence (4 bytes)
`ED : Ending Delimiter (Link Dependent)
`ADDRESS FIELDS
`
`ran 0
`
`roe 5
`
`25
`
`40
`
`45
`
`50
`
`The source address (SA) and destination address
`(DA) fields are 48-bits in length and have identical
`formats. The source address (84) identifies the node
`originating the message. The destination address identi-
`fies the node receiving the message. The IEEE 802.3
`standard defines two address lengths, 16-bit and 48-bit.
`Only the 48-bit length is used in the Cluster. The IEEE
`802.3 address format is shown in FIG. 6¢@ and 64. The
`fields are defined as follows. For FIG. 6a:
`I/G : Individual (|C) or Group (| 1) Address
`U/L : Locally Administered Address (| 1)
`ADDR| Station Address (46 bits)
`For FIG. 68:
`I/G : Individual (|0) or Group (| 1) Address
`U/L : Universal Address (}0)
`VID} Vendors Identification (22 bits)
`NA| Node Address (24 bits, assigned by Vendor)
`The I/G bit (94, 100) identifies the address as an
`individual or group address. Individual addresses are to
`a single node. Group can beto a subset of thetotal set
`of nodes on the network or all nodes (broadcast).
`Broadcast is defined as all address bits equal to 1. Indi-
`vidual and group addresses (other than broadcast) are
`further qualified by the U/L bit (96, 102). Universal
`addresses are unique addresses administered by the
`IEEE. Each manufacturer of 802.3 nodes, or control-
`lers, receives a vendor identification number from the
`IEEE. That manufacturer will then assign 24 bit node
`addresses to each product in sequence. The combina-
`tion of vendor ID and node ID creates a unique, univer-
`sal ID that can be used on any network.
`Locally administered addresses are defined within a
`single network and are independent. They allow special
`functions, grouping, etc. Cluster provides for both
`Local and Universal addresses. Native Cluster ad-
`dresses are encoded in the Local address and have an
`architecturally defined structure. The structure facilli-
`tates efficient routing between interconnected hubs.
`Nodesinterfacing to a Cluster network through a Node
`’ Controller (CLIC) are identified only by Local ad-
`dresses.
`Universal addresses are supported to allow attach-
`ment of 802.3 nodes without altering their software or
`hardware. Theintent is to provide a migration path and
`performance increase
`to existing nodes with no
`changes.
`
`network that facillitates routing. Each node addressis
`composed oftwofields, one providing a node address
`relative to the hubit is attached to and the other a hub
`address relative to the other hubs in the network. The
`combination is a unique network address, that is used to
`route any messageto its ultimate destination.
`A network is composed of only a few functional
`modules, as illustrated in FIG. 1. The interconnect func-
`tionality is contained in the Node controllers (6, 30) and
`Ring Controllers (10, 12, 14, 16), which are two sepa-
`rate personalities of one VLSI chip selected by a mode
`pin input to the CLIC component shown in FIG. 2. A
`significant amount of commonlogic exists in the CLIC
`for buffering and connecting to the media interface. The
`CLICwill be referred to as either a Node Controller or
`Ring Controller, depending on its function in the net-
`work.
`Mediainterfaces provide a method of connecting the
`CLIC to different link media, such as twisted pair wires,
`coax cable, or fiberoptic cable. Media interfaces typi-
`cally consist of an interface component or components
`designed for an existing network. For example,
`the
`combination of the 82501 Ethernet TM manchester en-
`coder-decoder component and a differential driver/-
`receiver allow interfacing to twisted pair wires.
`The hub (4) is a “register insertion ring”. The net-
`work uses the ring bus described in Ser. No. 07/291,756
`at the hub for arbitration and routing of messages. The
`hub is composed of the Ring Controllers (10, 12, 14, 16)
`and their media interfaces (18, 19, 21, 28). Every node
`controller has a corresponding Ring Controller at-
`tached via the media interfaces and the link between
`them. The ring controllers are connected as a unidirec-
`tional ring bus that closes on itself.
`The node is composed of the protocol processor(2),
`Node Controller (6), and media interface (18, 19). Al-
`though the protocol processoris not part of the present
`invention, it is shownto illustrate how a workstation is
`interfaced to a node controller. The protocol processor
`is responsible for supplying messages (to be sent on the
`network from the node) to the node controller (6), and
`removing messages received by the node controller
`from the network. Protocol handlers running on the
`protocol processor control the flow of messages be-
`tween the node and other nodes on the network. The
`network hub is responsible for actual transfer of the
`message to its destination.
`
`CLUSTER INTERFACE CONTROLLER(CLIC)
`The CLIC provides both the node and hubinterface
`capabilities of the Cluster. FIG. 2 illustrates the three
`major functional blocks of the CLIC and how they are
`related. The link interface (36, 37) is common to both
`the node and Ring Controller functions of the compo-
`nent. When used in a network, either the node interface
`(40) or ring bus interface (42) is selected (43), allowing
`the selected interface access to thelink interface (36, 37)
`and the I/O pins (44, 45) of the combined node/ring bus
`interface.
`
`NETWORK ADDRESSING
`
`The IEEE 802.3 Standard message format and ad-
`dress model are used in the Cluster. The Cluster pro-
`vides a link interface mode that allows a node imple-
`mented in accordance with the IEEE 802.3 standard to
`connect directly to the Cluster without a gateway or
`bridge. The adaption to the Cluster architecture is pro-
`vided by the Ring Controller (CLIC) component.
`
`65
`
`LENGTH FIELD
`
`The length field (L) is two bytes or 16-bits in length.
`it's value indicates the 'ength, in numberofbytes, of the
`
`Petitioner Riot Games,Inc. - Ex. 1031, p. 6
`
`Petitioner Riot Games, Inc. - Ex. 1031, p. 6
`
`
`
`5,041,963
`
`8
`
`NODE INTERFACE
`
`7
`INFOfield. The length field is not used by the Cluster
`Hardware.
`
`FRAME CHECK SEQUENCE FIELD
`Acyclic redundancy check (CRC)is used to generate
`a CRCvalue for the FCSfield (90). The FCS is 32-bits
`and is generated over the DA, SA, L, and INFO fields.
`The CRCis identical to the one used in the 802.3 stan-
`dard.
`
`MAXIMUM MESSAGE LENGTH
`Two maximum message lengths are enforced. The
`IEEE 802.3 standard has a maximum message length of
`1.5 K bytes, while Cluster will handle up to 4.5 K bytes.
`Native Cluster nodes (those with a Node Controller)
`have only Local addresses. Universal addresses are
`reserved for 802.3 nodes and implythat only 1.5 K byte
`messages may be sent to these nodes.
`Group messages are be restricted to 1.5 K bytes to
`enforce compatibility with 802.3 nodes. The smaller
`group messagesize also allows the use of a more effi-
`cient broadcast mechanism in the Cluster. Conse-
`quently, native Cluster group messages are restricted to
`1.5 K bytes.
`CLUSTER ADDRESS STRUCTURE
`
`FIGS. 7a and 76 show the structure of the Local
`address field for a native Cluster node address. Both
`group (FIG.7a) and individual address (FIG.7) struc-
`tures are illustrated. The I1/G field (120, 130) is the
`Individual or Group Address(1 bit). The CMMI field is
`the Cluster Management Message Identifier (6 bits). A
`24 bit field is reserved. The HIDfield is the Hub Identi-
`fier (8 bits). The LID filed is the Link Identifier (8 bits).
`The GID field is the Group Identifier (16 bits).
`LOCAL ADDRESS FORMAT
`The CMMI field is a Cluster defined field used to
`identify network control functions. A zero value in the
`field indicates that the message is to be handled nor-
`mally. A nonzero value identifies a special function to
`be performed by the CLIC selected by the HID and
`LID field.
`(CMMs) are ad-
`Cluster Management Messages
`dressed directly to a Ring Controller and are used to
`managefunctions in the network that cannot bedirectly
`handled by the hardware. Examples are network map-
`ping,initialization of routing functions, diagnostic eval-
`uation, and performance monitoring. Ring Controllers
`recognize the message as a CMM andtreatit as a nor-
`mal message unless it is addressed to them.If addressed
`to the Ring Controller,
`the function defined by the
`CMMIfield are performed. CMMsare described more
`fully in U.S. Pat. No. 4,939,724.
`All Cluster Hubs are given a unique HubIdentifier at
`initialization. All links attached to the hub are also as-
`signed a unique identifier relative to the hub they are
`attached. Up to 256 hubs, and 256 links per each hub,
`can be supported in a single Cluster network. A native
`Cluster node connected to a link takes on the address of
`the hub and link to which it is attached. 802.3 nodes
`mayuse either the Local address or a Universal address.
`The Group Identifier (GID) provides for multi-cast
`addressing. Local group addressing is not supported by
`Cluster hardware, deferring the interpretation to the
`node itself. All messages addressed to a group are
`broadcastto all nodes, where they canfilter the address.
`
`Two methodsofinterfacing a node to the Cluster are
`provided. The IEEE Standard 802.3 compatible link
`interface allows an unmodified 802.3 nodeto be directly
`attached to a Cluster through one ofseveral different
`available $02.3 media choices. High performance nodes
`use the Node Controller (CLIC) which is described in
`copending application Ser. No. 07/291,640. The Node
`Controller (CLIC) provides for high bandwidth links
`and supports low latency protocols.
`IEEE 802.3 LINK INTERFACE
`Two basic operational modes are incorporatedin the
`CLIC shown in FIG.2, the Node Controller mode and
`the Ring Controller mode. A commonblock of logic,
`including the FIFO buffers (32, 34), output link inter-
`face (36) and inputlink interface (37), are shared by two
`independent logic blocks (40, 42) that implement the
`operational modes. When the Node Controller interface
`logic (40) is selected, the internal interface (44) is dedi-
`cated to it, along with the I/O Interface pins (46), and
`the Ring Controller hub interface logic (42) is disabled.
`The I/O Interface pin functions and timing are deter-
`mined by the modeselected.
`The Node Controller provides a slave direct memory
`access (DMA)interface to a protocol processor respon-
`sible for controlling the Cluster connection. The slave
`DMAinterface is capable of very high transfer rates
`and incorporates additional
`functionality to support
`low-latency protocol development. The interface is
`optimized for use with a protocol processor/high per-
`formance DMA controller combination, such as an
`Intel 80386 with an Intel 82380 DMA controller, an
`Intel 80960CA with integrated DMA, or a Channel
`Processor (64). Two Cluster controller subsystems are
`illustrated in FIGS. 3 and 4.
`As shown in FIG. 3, a microprocessor is coupled
`with memory, the Node Controller, and a system bus
`interface. This is a high performance subsystem for use
`in a department computer or mainframe. The local
`memory is used for the protocol processor code and
`variables, with the actual messages transferred between
`system memory and the Node Controller. The combina-
`tion of large FIFO buffers and the low latency protocol
`support, makes this modelpractical, and avoiding extra
`copies.
`
`NODE CONTROLLER SUBSYSTEM
`CONTROLLER
`
`- 5
`
`20
`
`25
`
`tab0
`
`40
`
`The following sequence describes the general model
`for message reception and transfer to system memory:
`1. As the header of an incoming messageis received,
`it is transferred to local memory (54).
`2. Once the header has been transferred, the Node
`Controller interrupts the protocol processor (56).
`3. The processor(56) acknowledgesthe interrupt and
`examines the header.
`4, While the protocol processor examines the header,
`the remainder of the message is stored in the Node
`Controller Input FIFO (34), but is not transferred to the
`subsystem or memory.
`§. Once the disposition of the message has been deter-
`mined, the remainder of the message is transferred to
`the destination buffer in system memory (54).
`6. A final interrupt is generated,indicating the avail-
`ability of a status message, after the complete message
`has been transferred.
`
`55
`
`60
`
`65
`
`Petitioner Riot Games,Inc. - Ex. 1031, p. 7
`
`Petitioner Riot Games, Inc. - Ex. 1031, p. 7
`
`
`
`5,041,963
`
`10
`
`MESSAGE TRANSFER ON NODE
`CONTROLLERI/O BUS
`
`9
`7. The processor acknowledges the interrupt and
`reads the status register.
`8. The transfer is then completed based on thestatus
`received .
`The above sequenceallows processing of the message
`header to be overlapped with the receipt of the mes-
`sage. In many systems, the transfer to system memoryis
`faster than the transfer rate of incoming messages. The
`time spent in processing the header at the beginningis
`gained back in the transfer of the message. Copying the
`message into a local buffer is unnecessary due to the
`large buffer in the Node Controller and the flow control
`on the link to the hub.
`
`ALIGNMENT OF MESSAGE BUFFERS
`
`Messages provided by a system for transmission on a
`network can begin on any byte boundary within system
`memory and be any number of bytes long within the
`maximum and minimum size boundaries. The message
`can also be composed of multiple buffers chained to-
`gether with each buffer having different lengths and
`beginning on different boundaries. The Node Control-
`ler is designed as a 32-bit device to achieve high transfer
`rates with minimum impact on system bandwidth.
`The Node Controller does not provide for data align-
`ment,leaving that task to the protocol processor and/or
`DMAcontroller. Available DMA controllers provide
`alignment and assembly/disassembly capabilities that
`eliminate the need for providing them in the Node Con-
`troller.
`The Node Controller expects all messages to be trans-
`ferred as contiguous words (32-bits wide) starting with
`the first four bytes to be transferred. Messages less than
`an integral number of words long are designated in the
`control word initiating the message transfer. The last
`word of the message transferred to the Node Controller
`ts truncated based on the length provided in the control
`word.
`Input messages for the system are handled in a similar
`fashion. The status word provided at the end of the
`transfer into memory indicates the number of valid
`bytes in the last word of the message.
`The 16-bit bus mode also operates in the same way,
`except everything is an integral number of half-words
`instead of full words.
`
`MEMORY-MAPPED CONTROL/STATUS
`INTERFACE
`
`As described in the above-identified application Ser.
`No. 07/291,640, the Node Controller mode of the CLIC
`shown in FIG.1 is selected through an I/O pin (43)at
`component reset/initialization. The Node Controller
`mode configures the I/O pins (44, 45) as a local bus for
`interfacing to a nade. This interface (40) consists of a set
`of memory-mappedregisters that control the operation
`of the Node Controller.
`
`INTERRUPTS
`
`Interrupts are provided to notify the protocol proces-
`sor when various events, such as a message hasarrived,
`an error occurred, or output data is required. Format-
`ting and masking options are provided for handling the
`various interrupts. One or two interrupt lines can be
`use