,HlllllllllllllllIlllllllllIlllllllll||||||||l|Illlllllllllllllllllllllllll
`U8005566170A
`
`United States Patent
`Bakke et al.
`
`[191
`
`[11] Patent Number:
`
`5,566,170
`
`[45] Date of Patent:
`
`Oct. 15, 1996
`
`[54]
`
`METHOD AND APPARATUS FOR
`ACCELERATED PACKET FORWARDING
`
`I
`
`[751
`
`Inventors: Mark A. Bekke, Maple Grove;
`Edward J. Fiore, Ramsey, both of
`Minn.
`.
`
`’
`
`[73]
`
`{21]
`
`[22]
`
`[51]
`[52]
`
`[581
`
`[56]
`
`Assignee: Storage Technoloy Corporation,
`Louisville, Colo.
`
`App]. No.: 366,221
`
`Filed:
`
`We. 29,1994
`
`Int. 01.6 ........................'..... HML 12/56; GO6F 13/00
`US. Cl. ........................... 379/69; 370/942; 395/650;
`~
`'
`'
`.
`395/800
`
`Field of Search ,................................. 37058.], 58.2,
`370/583,, 60, 60.1, 61, 79.82, 83, 85.13,
`85.14, 94.1, 94.2, 94.3, 99; 395/200, 325,
`‘
`375, 650, 800
`
`'
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`5,134,610
`5,249,292
`
`370/60
`7/1992 Shand etal
`. 395/650
`9/1993 Chiappa .......
`
`5,278,834
`5,280,476
`5,414,702
`5,414,707
`5,430,709
`
`.. 3170/94.]
`1/1994 Mazzola ......
`
`
`.' 370/601
`1/1994 Kojiina etal.
`
`5/1995 Kudoh .................. 370/60
`
`5/1995 Johnston eta].
`370/79
`
`7/1995 Galloway .......................
`....... 370/13
`
`*
`
`Primary Examiner—Alpus H. 'Hsu
`Attorney, Agent, or_Fimz—-Patterson and Keough
`
`[57]
`
`ABSTRACT
`
`A method andvapparatus are provided to transfer protocol
`data units within a communication network. This transfer-
`ring is accomplished with a protocol data unit preprocessor ,
`utilized in a protocol data unit forwarding device that is
`operated in the communication network. The preprocessor,
`includes an identification mechanism which determines
`media header information of a protocol data unit received
`from over the communication network. Subsequently, a
`validation mechanism validates the media header informa-
`tion. In addition, modification mechanisrn adds next opera—
`tion information to the media header information based upon
`the determined media header information such that subse-
`quent processing of the protocol data unit by the protocol
`data unit forwarding device is reduced.
`
`29 Claims, 6 Drawing Sheets
`
`[100
`
`.-!I.-. V
`PROCESSOR
`
`
`
`UNIFIED 1008
`
`UNIFIED 1008
`
`

`

`- US. Patent
`
`Oct. 15, 1996
`
`Sheét l of 6
`
`5,566,170
`
`5k.
`
`N0_..mm_.
`
`.moE<o<
`
`XEOE
`
`w0<mmm._.2_
`
`vEOEMZ
`
`why/«LEE?—
`
`
`
`
`
`EOmmwOOEQmenEDn—4<Ew2wmmm,ro.4u.I...Om.
`
`
`
`firmly.EOEm-F.0.”—
`
`
`
`

`

`US. Patent
`
`1
`
`Oct. 15, 1996
`
`Sheet 2 of 6
`
`5,566,170
`
`N.GE . GE.
`
`5%EE
`
`5
`
`
`

`

`US. Patent
`
`Oct. 15, 1996
`
`Sheét 3 of 6
`
`5,566,170
`
`‘
`
`INPUT
`BUFFER
`
`200
`
`2
`
`06
`
`‘
`
`210
`
`T
`
`212
`
`CHECK 48 BIT
`DA
`
`VALIDATE DA
`AND SA
`
`FORWARD TYPE ‘
`DECISlON
`
`CHECK 48 BIT
`SA
`
`‘
`
`214
`
`SOURCE
`ROUTE INFO
`
`
`
`YES
`
`‘ 16
`
`.
`'ROTOCOL
`
`TYPE>1500V
`
`,
`
`.No
`
`1B
`
`'
`
`_
`
`20
`
`.
`NO FORWARD
`’
`ONLY
`
`.
`
`_
`
`Y
`
`ES
`
`Y
`
`DETERMINE
`TYPE
`
`
`
`IPX, AT, SNAP,
`IPX SAP, IPX
`BROKEN
`
`FIG. 3
`
`

`

`\
`
`US. Patent
`
`Oct. 15, 1996 '
`
`Sheet 4 of 6
`
`5,566,170 I
`
`224
`
`
`
`ENGTH=
`
`
`AND
`
`VERSION=4
`
`YES
`
`232
`
`N0
`
`226
`
`BAD PDU
`
`DETERMINE
`
`TYPE OF
`
`SERVICE
`
`,
`
`‘ 236
`
`No
`
`238
`
`BAD PDU
`
`YES
`
`240
`
`
`
`'
`
`IME TO LlV
`EXPIRED
`
`
`
`NO
`
`242
`
`SET FLAG
`
`YES
`
`244
`
`DECREIVIENT
`TIME TO LIVE
`
`I
`
`’ 246
`
`250
`
`_
`
`.
`
`LOAD DA,
`TOS, AND VR
`INTO CAM
`
`,
`
`ADD
`RECEIVE
`INFO TO PDU
`
`248
`
`WRITE CAM
`RESULTS TO
`REGISTER
`
`FIG. 4
`
`

`

`US. Patent
`
`Oct. 15, 1996
`
`Sheet 5 orb
`
`5,566,170
`
`
`
`_K|PPAD_YTES
`
`264
`
`PAD
`COUNT S 6
`
`66
`
`BAD PDU
`
`263 -
`
`.
`
`NO
`
`.
`
`268
`
`CLEAR
`INTRA-LAN
`BIT
`
`‘
`
`270
`
`SK'P SlX
`BYTES
`
`272
`
`_
`
`274
`
`LOAD DA, VR,
`ANDID INTO‘
`CAM
`
`, WRITE CAM
`RESULTS TO
`REGISTER
`
`SKIP SEVEN
`BYTES
`
`’
`
`
`
`276
`
`84
`
`N0.
`
`
`[SIT COUN
`EXCEEDED '
`
`
`286
`YES
`
`288
`
`290
`
`INCREMENT
`VISIT COUNT
`
`ADD
`RECE'VE
`INFO TO PDU
`
`-
`
`,
`
`-
`
`‘ FIG. 5
`
`

`

`US. Patent
`
`Oct. 15, 1996
`
`Sheet 6 of 6
`
`5,566,170
`
`300
`
`DETERMINE
`
`MEDIA HEADER
`
`INFORMATION
`
`VALIDATE
`
`MEDIA HEADER
`
`INFORMATION
`
` 302
`
`304
`
`306
`
`308
`
`ADD NEXT
`
`OPERATION
`
`INFORMATION
`
`FORWARD ‘
`
`PROTOCOL
`
`DATA UNIT .
`
`‘ FIG. 6.
`
`

`

`5,566,170
`
`1
`METHOD AND APPARATUS FOR
`ACCELERATED PACKET FORWARDING
`
`RELATED INVENTIONS
`
`The present invention is related to:
`Co-pending U.S. patent application Ser. No. 08/366,225
`filed-on Dec. 23, 1994, which is entitled “Method And
`Apparatus For Accelerated Packet Processing" by Geof
`Stone,
`Co-pending U.S. patent application Ser. No. 08/366,226
`filed on Dec. 23, 1994, which is entitled “MethodAnd
`Apparatus For Radix Decision Packet Processing" by Geof
`Stone,
`
`Co-pending U.S. patent application Ser. No 08/366,227
`filed on Dec. 23, 1994, which is entitled “Method And
`Apparatus For Virtual Switching" by Ken Hardwick, et al.;
`and which were all
`filed concurrently herewith and
`assigned to the assignee of the present invention.
`
`10
`
`15
`
`20.
`
`FIELD OF THE INVENTION
`
`The present invention relates generally to data commu-
`nication networks. More particularly, the present invention
`relates to protocol data unit forwarding systems that direct
`the flow of protocol data units in the data communication
`networks.
`
`BACKGROUND OF THE INVENTION
`
`In a data communication network, a forwarding device
`(eg., a data packet switch) directs protocol data units (e.g.,
`data packets) from one network node to another, These data
`packets may include voice, video, or data information as
`well as any combination thereof.
`To better understand how forwarding devices work within
`a data communication network, an analogy may be helpful.
`In many respects, data communication networks are similar
`to postal delivery systems, with pieces of mail, such as
`letters or packages, being comparable to the data packets
`which are transferred within a data communication network;
`In a postal delivery system, the pieces of mail may be input
`into the postal delivery system in a variety of ways. Once
`within the postal delivery system, all of the pieces of mail
`are collected and transported to nearby processing facilities
`where the pieces of mail are sorted for further processing.
`Although each piece of mail will have a unique delivery
`address, most of the pieces of mail are automatically sorted
`by a shorter zip code or some other type of routing code
`Letters without zip codes must be sorted and processed by
`hand. Some postal delivery systems also have special forms
`of encoded delivery addresses, such as Post Olfice box
`numbers at a Post Oflice, which are not recognizable by
`other postal delivery systems such as Federal Express or
`_ United Parcel Service. Regardless of which particular postal
`delivery system the piece of mail is deposited into, once the
`mail has been sorted by destination it is routed through
`additional intermediary processing facilities until it arrives
`at the local indicated by the destination on the piece of mail.
`At this point, the zip code or roofing code is no longer
`sufficient to deliver the piece of mail to the intended desti-
`nation and the local delivery ofiice must further decode the
`destination address in order to deliver the piece of mail to the
`intended recipient. In addition to processing pieces of mail
`for routing the mail to the correct destination, the pieces of
`mail may go on through several other processing steps. For
`example, if the piece of mail is going out of the country, it
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`65
`
`2
`must go through a customs operation in each country. If the
`national postal delivery system is being used to deliver the
`piece of mail then it must also be transferred from one
`national postal delivery system to another. In a private postal
`delivery system however, this transfer step would not be
`necessary. The pieces of mail may also be monitored or
`filtered for such things as mail fraud violation or shipment
`of hazardous materials.
`
`~ Data packets are manipulated in a data communication
`network} in a manner similar to that by which pieces of mail
`are delivered in a postal delivery system. Data packets, for
`example, aregenerated by many diiferent types of devices
`and are placed onto a communication network. Typically, the
`data packets are concentrated into a forwarding device, such
`as a local bridge or router, and are then directed by desti~
`nation over one or more media types (e.g., fiber optic) which
`are connected to destination devices that could be other
`larger or smaller bridges or routers. These destination
`devices then deliver the data packet to its terminal end point
`(i.e., the end user). Along the way the data communication
`network may perform filtering and monitoring functions
`with respect to the data packets.
`'
`Just like postal delivery systems have experienced ever
`increasing volumes of mail which must be delivered, the
`volume ‘of protocol data units being transferred across
`computer networks continues to increase as experience is
`being gained with this new form of communication delivery
`system and as more and more applications, with more and
`more expansive means are being developed. In addition,
`quickly changing technology has made the underlying data
`transmission resources for computer communication net-
`works relatively inexpensive. Fiber optics, for example,
`ofier data transfer rates in the gigabyte per second range.
`The capability or through put of a forwarding device and
`a computer communication network can be measured either
`by the number of data packets per second or by the number
`of bits per second which pass through the forwarding device.
`The former measure is importantbecause in typical network
`traflic, the bulk of protocol data units or data packets. are
`small and the critical parameter is how many data packets a
`forwarding device can handle. If network trafiic is weighted
`by packet size, however, the bulk of the data is carried in
`.large packets. In large bulk data transfers, the second mea-
`sure of how many hits are being transferred is more impor-
`tant regardless of the number of data packets that are
`handled. This tension between packet transfer rate versus bit
`transfer rate is a continuing dichotomy in through put
`measurements of forwarding devices. Regardless of which
`through put measure is used, there'rs a need for through put
`rates that are substantially higher than the through put rates
`currently available'in forwarding devices.
`The existing types of forwarding devices which offer the
`greatest potential to meet the increasing demand on through
`put rates are packet switches. Several classes of packet
`switches exist. Each class differs substantially from the other
`class of devices, but all may be commonly referred to as
`packet switches or forwarding devices.
`A first class of packet switches is that commonly used in
`digital telephone exchanges. By analogy, these switches can
`perform the functions only of a mail carrier picking up and
`delivering mail along a single route. These switches are
`intended only to transfer packets among the devices in a ‘
`single station, such as a telephone exchange. The format of
`the packet in these systems is chosen to make the hardware
`in the switch as simple as possible; and this usually means
`that the packets include fields designed for direct use by the
`
`

`

`5,566,170
`
`4
`
`10
`
`15
`
`35
`
`4
`
`The approach which uses faster processors simply keeps
`pace with processor dependent (future) demands because the
`trafiic which the packet switch will handle will depend upon
`the speed of the user processors being used to generate the
`nafiic. Those user processors, like the processors in the
`packet switches, will increase in speed at more or less the
`same rate. Accordingly, there is no overall increase in the
`ability of the future packet switch over present packet
`switches, relative to traflic load. Furthermore, this approach
`may be impractical as not being cost-effective for wide-
`spread use. For example, two high speed machines, distant
`from each other, must have intermediate switches which are v
`all equally as powerful; deployment on a large scale of such
`expensive switches is not likely to be practicable.
`‘
`The approach which increases the execution rate of the
`software itself by, for example, removing excess instructions
`or writing the code in assembly language, leads to a limit
`beyond which an increase in performance cannot be made.
`The gains which result are typically small (a few percent)
`and the engineering costs of such distortions in the software
`are significant in the long term. This type of assembly code
`optimization restricts the ability to enhance the softWare as
`well as port the software to a different processor platform.
`The use of multiple processors to avoid the “processor
`bottleneck" provides some gains but again has limits. Given
`a code path to forward a data packet, it is not plausible to
`split that path into more than a few stages. Typically these
`stages would involve network input, protocol functions, and
`network output. The basis for this limitation is the overhead
`incurred to interface the difi‘erent processors beyond a
`limited number of task divisions. That is, after acertain
`point,
`the increase in interface overhead outv'veighs the
`savings obtained from. the additional stage. This is particu-
`larly true because of the need to tightly integrate the various
`components; for example, congestion control at the protocol
`level requires dose coordination with the output device.
`Also, the interface overhead costs are made more severe by
`the complication of the interface which is required.
`.
`.
`.
`In general then, the multiprocessor approach is not the
`0' answer to substantially mcreasmg the throughput of the
`packet switching network. This has been borne out by
`several attempts by technically well-regarded groups to
`build packet switches using this approach. While aggregate
`throughput over a large number of interfaces can be
`obtained, this is, in reality, little different than having a large
`number of small switches. It has thus far proven implausible
`to substantially speed up a single stream using the multi-
`processing approach.
`'
`A need still exists for an improved protocol data unit (i.e.,
`frame, cell, or packet) forwarding system which solves the
`above~mentioned problems in a manner which can better
`handle large numbers of input streams, large numbers of
`output destinations and lines, many difl’erent types of com-
`munication protocols, and large and small data packets at
`both high bit throughput rates and high packet throughput
`rates, while maintaining reasonable costs and complexity.
`
`30
`
`3
`hardware. The capabilities of this class of switches (for
`example,
`in such areas as congestion control) are very
`limited in order to keep the hardware simple.
`A second class of packet switches is used in smaller-or
`restricted computer netWorks, such as X.25 networks. By
`analogy, these switches are equivalent to the Post Office in
`a single town with no connection to other Post Oflices. In
`some sense, these switches are little difierent from the first
`class of packet switches described above, but there is one
`- substantial diiference. The format of the packets (that is, the
`protocols) handled by the second class of packet switches is
`much more complex. This greater complexity is necessary
`because the protocols are designed to work in less restricted
`environments, and because the packet switches must provide
`a greater range of services. While the formats interpreted by
`the first class of switches are chosen for easy implementa-
`tion in hardware, the data packets handled by this second
`class of switches are generally intended to be interpreted by
`software (which can easily and economically handle the v
`greater complexity) and provides the inherit benefit of
`incremental flexibility in the design of the packet switch.
`In a third class of packet switches, the packet protocols
`are intended to be used in very large data networks having
`many very dissimilar links (such an mix of very high speed
`local area networks (LANs) and low speed long distance
`point to point lines). Examples of such protocols are the
`United States designed Transmission Control Protocol/In-
`temetwork Program (TOP/1P), and the International Stan-
`dards Organization’sintemetworking Protocol/Connection-
`less Network Service (IPICLNS) protocols.
`In addition,
`this third class of switches (commonly
`referred to as bridge/routers) often must handle multiple
`protocols simultaneously. This third class of switches is very
`similar to the mail processing devices used in the modern
`postal system. Just as there are many countries, there are
`many data, packet protocols used in computer networks.
`While a single postal system was once thought
`to be
`sufficient to handle mail going anywhere in the world, today
`several competing systems like United Parcel Service, Fed-
`eral Express, and the U.S. Postal Service exist to handle the
`special needs of mail going to every country, state, city,
`town, and street in the world. Similarly, in computer com-
`munication systems, the packet switches are more involved
`in the carrying of data, and must understand some of the
`details of each protocol to be able to correctly handle data
`packets Which are being conveyed in that protocol. The
`routers in this third class of packet switches often have to
`make fairly complex changes to the data packets as they pass
`through the packet switch.
`-
`It is this latter class of packet switches to which the
`, following detailed description primarily relates. It will be
`appreciated howavcr, that the detailed description of this
`invention can readily be applied to the first and second class
`of switches as well. In current conventional packet switch
`design, a programmed general purpose processor examines
`each data packet as it arrives over the network interface and
`then processes that packet. Packet processing requires
`assignment of the data packet to an outbound network
`interface for transmission over the next communications link
`in the data path. While attempts are being made to build
`higher speed packet switches, based on this architecture of
`using general purpose processors, the attempts have not
`been very successful. One approach is to use faster proces~
`sors, another is to make the software run. faster, and a third '
`is to apply multiple processors to the processing task. All of 65
`these approaches fail to meet the increasing performance
`demands for packet switches for the reasons noted below.
`
`45
`
`50
`
`55
`
`SUMMARY OF THE lNVEN’HQN
`The present invention provides a packet-forwarding sys-
`tem With improved throughput performance by means of a *
`method and apparatus for accelerated packet forwarding. In
`accordance with a first aspect of the invention, a protocol
`data unit preprocessor is used in a protocol data unit for-
`warding device utilized in a communication network to
`transfer protocol data units within the communication net-
`
`

`

`5,566,170
`
`5
`work. The preprocessor includes an identifier which deter-
`mines media header information of a protocol data unit
`received from over the communication network. In addition,
`the validation mechanism is operatively coupled to the
`identifier to validate the media header information. Also, a -
`modifier device is operatively coupled to theyidentifier to
`perform necessary modifications to the media header (e.g.,
`add next operation information) based upon the determined
`media header information such that subsequent processing
`of the protocol data unit by the protocol data unit forwarding
`device is reduced.
`'
`
`10
`
`With reference to the postal delivery analogy, the present
`invention can be likened to a system which both increases
`the speed at Which pieces of mail can be moved through the
`postal delivery system and provides an ability to handle in
`a common system pieces of mail entered into a variety of
`different postal delivery systems. By utilizing the prepro-
`cessor of the present invention to identify and verify the
`media header or address information of a protocol data unit
`and then using this information to generate a modified
`address that facilitates quicker processing of the protocol
`data units, the present invention is able to significantly
`increase-the through put of the forwarding device, both in
`terms of the number of data packets per second and in terms
`of the'number of bits per second which pass through the
`forwarding device.
`'
`The media header information typically includes at a
`minimum the encapsulation type, protocol type, frame type,
`media destination, and source route information. This infor~
`mation is used by the modifier device to add next operation
`information which specifies a particular operation such as
`route, bridge, or source route bridge to perform on the
`received protocol data unit. It should be noted that a media
`destination may be multicast, a urticast match,’or a unith
`non-match destination.
`'
`
`In order to accelerate the forwarding of a received pro-
`tocol data unit, the identifier preferably is configured to
`determine the media header
`information after having
`received only a portion (i.e., the first several bits" or bytes) of
`the protocol data unit. Similarly, the modifier device pref-
`erably is configured to modify the media header after having
`received only a portion of the protocol data unit. Both of
`these optimizations are particularly important when manipu-
`lating large protocol data units which extend over several
`frames or consist of several smaller parts that are received at
`various times and/or from various incoming interfaces.
`In accordance with a second aspect of the invention, a
`method of operating a forwarding device within a commu-
`nication network is provided to forward a protocol data unit
`received by the forwarding device. This method is per-
`formed by device-implemented steps in a first and second
`processor. In the first processor, media header information of
`a protocol data unit is determined based upon a portion of
`the protocol data unit which is received from over a com-
`munication network, the media header information is vali~
`dated, and next operation information is added to the media
`header information based upon the determined media header
`information such that subsequent processing of the protocol
`data unit by a forwarding processor is reduced. In a second
`processor, the protocol data unit is forwarded based upon the
`next operation information.
`The validating step preferably consists of performing one
`or more validation schemes. These validation schemes
`include, but are not limited to, time to live, hop count,
`checksum, header type, header version, network header
`length, check options, source route header length, and check
`
`15
`
`.
`
`20
`
`25
`
`30
`
`35
`
`45
`
`50
`
`55
`
`65
`
`6
`for duplicate local area network identifiers. In conjunction
`with using, these validation schemes, a step may be added to
`the preferred embodiment method prior to the step of
`forwarding the protocol data unit. This additional step would
`involve modifying the protocol data unit in accordance with '
`next operation information by decrementing a time to live,
`incrementing a hop count, modifying a checksum, truncating
`a protocol data unit, and/or removing a frame check
`sequence from the protocol data unit. In addition, it may be
`necessary to pad bytes of data to the protocol data unit to
`enhance the forwarding process such that the header infor-
`mation is aligned on optimal boundaries.
`These and various other features as well as advantages
`which characterize the present invention will be apparent
`upon reading of the following detailed description and
`review of the associated drawings.
`
`BRIEF DESCRD’TION OF THE DRAWINGS
`
`FIG. 1 is a block diagramof a prior art network device.
`FIG. 2 is a block diagram of a preferred embodiment
`network device in accordance with the present invention.
`FIGS. 3, 4, and 5 are block diagrams of an operational
`example of the preferred embodiment network device shown.
`in FIG. 2.
`,
`
`. FIG. 6 is a flowchart of the.preferred embodiment opera-
`tions of the network device shown in FIG. 2 in accordance
`with-the present invention.
`‘
`
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENT
`
`As will be appreciated by those skilled in the art, com-
`munication networks and their operations can be described
`according to the Open Systems Interconnection (081) model
`which includes seven layers including an application, pre-
`sentation, session,
`transport, network,
`link, and physical
`layer. The 081 model was developed by the International
`Organization for Standardization (ISO) and is described in
`“The Basics Book of 081 and Network Management"by
`Motorola Codex from Addison—Wesley Publishing Com-
`pany‘, Inc., 1993 (First Printing September 1992).
`Each layer of the 081 model performs a specific data
`communications task, a service to and for the layer that
`precedes it (e.g., the network layer provides a service for the
`transport layer). The process can be likened to placing a
`letter in a series 'of envelopes before it's sent through the
`postal system. Each succeeding envelope adds another layer
`.of processing or overhead information necessary to process
`the transaction. Together, all the envelopes help make sure
`the letter gets to the right address and that the message
`received is identical to the message sent. Once the entire
`package is received at its destination, the envelopes are
`opened one by one until the letter itself emerges exactly as
`written.
`
`In a data communication transaction, however, each end
`user is unaware of the envelopes, which perform their
`functions transparently. For example, an automatic bank
`teller machine transaction can be tracked through the mul-
`tilayer 081 system. One multiple layer system (Open Sys—
`tem A) provides an application layer that is an interface to
`a person attempting a transaction, while the other multiple
`layer system (Open System B) provides an application layer
`that interfaces with applications software in a bank’s host
`computer. The corresponding layers in Open Systems A and
`B are called peer layers and communicate through peer
`
`

`

`' 5,566,170
`
`7
`
`'Ihese peer protocols provide communication
`protocols.
`support for a user’s application, performing transaction
`related tasks such as debiting an account, dispensing cur-
`rency, or crediting an account.
`Actual data flow between the two open systems (Open
`System A and Open System B), however, is from top to
`bottom in one open system (Open System A, the source),
`across the communications line, and then from bottom to top
`in the other open system (Open System B, the destination).
`Each time that user application data passes downward from
`one layer to the next
`layer in the same system more
`processing information is added. When that information is
`removed and processed by the peer layer in the other system,
`it causes various tasks (error correction, flow control, etc.) to
`be performed. The user is unaware of any of this, of course,
`but in fact that's what’s happening while the words, “Please
`wait, your transaction is being processed" appears on the
`screen.
`'
`
`The ISO has specifically defined all seven layers, which .
`are summarized below in the order in which the data actually
`flow as they leave the source:
`Layer 7, the application layer, provides for a user appli~
`cation (such as getting money from an automatic bank
`teller machine) to interface with the OSI application
`- layer. That OSI application layer has a corresponding
`peer layer in the other open system, the bank's host
`computer.
`Layer 6,
`the presentation layer, makes sure the user
`information (a request for $50 in cash to be debited
`from your checking account) is in a format (i.e., syntax
`or sequence of ones and zeros) the destination open
`system can understand.
`Layer 5, the session layer, provides synchronization con-
`trol of data between the open systems (i.e., makes sure
`the bit configurations that pass through layer 5 at the
`source are the same as those that pass through layer 5
`at the destination).
`Layer 4, the transport layer, ensures that an end—to—end
`connection has been established between the two open
`systems (i.e., layer 4 at the destination “confirms the
`request for a connection," so to speak, that it has
`received from layer 4 at the source).
`Layer 3, the network layer, provides routing and relaying
`of data through the network (among other things, at
`layer 3 on the outbound side an “address" gets slapped
`on the “envelope" which is then read by layer 3 at the
`destination).
`Layer 2, the data link layer, includes flow control of data
`as they pass down through this layer in one open system
`and up through the peer layer in the other open system.
`Layer 1, the physical interface layer, includes the ways in
`which data communications equipment is connected
`mechanically and electrically, and the means by which
`the data move across those physical connections from
`layer 1 at the source to layer 1 at the destination.-
`Shown in FIG. 1, is a prior art network device 159
`described in us. Pat. No. 5,249,292 issued Sep. 28, 1993 to
`J. Noel Chiappa. The Chiappa ’292 patent describes a data
`packet switch 150 that operates at OSI layers 1 through 3
`which provides a solution to many of the previously-men-
`tioned problems. The Chiappa '292 patent discloses a high
`speed'data packet switching circuit which has a software
`controlled primary processing unit 172 (i.e., a general pur-
`pose processor) and a plurality of network interface units
`160, 164, and 168 each connected to an input network 152
`(i.e., inbound interface) for receiving incoming data packetI
`
`10
`
`15
`
`30
`
`35
`
`45
`
`so
`
`55
`
`65
`
`8
`streams as well as an output network 176 (i.e., outbound
`interface) for transmitting outgoing data packet streams for
`that network. It should be noted that a single input and
`output network are described by the Chiappa ’292 patent.
`The input network 152 includes a data byte buifer 154
`which temporarily stores portions of incoming data packet
`streams for the the primary processing unit 172 to subse-
`quently analyze or switch to a network interface unit.
`Similarly, the output network 176 includes a bufl’er 178 for
`storing data bytes until the primary processing unit 172
`releases modified data packets as an outgoing data packet
`stream 180' for transmission on the output network. Two
`types of network interface units are taught by the Chiappa
`’292 patent. The first type is a general purpose network
`interface 160 which merely performs the network layer
`functions and a separate interface adaptor 158 which per~
`forms data link layer functions such as flow control for data
`bytes coming from a specific type of physical interface layer
`device. The second type of network interface unit is a special
`purpose network interface 164 which combines the func-
`tions of the general purpose network interface 160 and
`interface adaptor 158 into a single device.
`In addition, a plurality of high speed data stream hardware
`control circuits 162, 166, and 170 (i.e., flow blocks) are
`provided for processing data packets in response to instruc
`tions for the primary processing unit 172. For example, data
`packet 180 of onedata stream is assigned to flow block 162
`and passes through interface adaptor 158 while being
`manipulated by network interface 160. Data packet 180‘is
`modified by flow block 162 into modified data packet 180'
`prior to transmission on an outbound network.
`Also, circuitry 156 and 174 (a multiplexer and a demul‘
`tiplexer, respectively) is included for interconnecting the
`primary processing unit 172, the interface units 160, 164,
`and 168 and the data stream control- circuits 162, 166, and
`170. The primary processing unit 172 receives, from the
`input network 152, at least a first one of the data packets 180
`of each new data packet stream and assigns, by way of
`control lines 182 and 184 to circuitry 156 and 158, respec-
`tively, that stream to be processed by' one of the data stream
`control circuits 162 without further processing by the pri-
`mary processing unit 172. When a user desires to handle
`more data streams simulataneously, more how blocks and
`network interfaces are added for the primary processing unit
`172 to which incoming data streams are'switche'd. The
`Chiappa ’292 patent thus performs routine, repetitive pro-
`cessing steps on the further packets of the data stream using
`high speed hardware circuitry 162, while the initial process-
`ing and other non-repetitive or special processing of the data
`packets are performed in software.
`Unfortunately, the Chiappa ’292 patent as well as the
`software-based solutions on general purpose microproces-
`sors do not completely solve the “processor bottleneck”
`problem (i.e., primary processing unit 172 must still analyze
`each data stream at least once) and as a result a need still
`exists for an improved protocol data unit (i.e., frame, cell, or
`packet) forwarding system which solves this problem, as
`well as others, in a manner which can better handle large
`numbers of input streams from one or more networks, large
`numbers of output destinations and lines, and large and
`small data packets at both high bit throughput rates and high
`packet throughput rates, while maintaining reasonable costs
`and complexity.
`Referring to