United States Patent [19J
`Stone
`
`I lllll 1111111111111111 11111111111111111111111111111111111111111111111111111
`US005598410A
`[lll Patent Number:
`[45] Date of Patent:
`
`5,598,410
`*Jan.28, 1997
`
`[54] METHOD AND APPARATUS FOR
`ACCELERATED PACKET PROCESSING
`
`[75]
`
`Inventor: Geoffrey C. Stone, Minneapolis, Minn.
`
`[73] Assignee: Storage Technology Corporation,
`Louisville, Colo.
`
`[ *] Notice:
`
`The term of this patent shall not extend
`beyond the expiration date of Pat. No.
`5,546,390.
`'
`
`[21] Appl. No.: 366,225
`
`[22] Filed:
`
`Dec. 29, 1994
`
`Int. Cl.6
`............................. H04L 12/56; G06F 13/00
`[51]
`[52] U.S. CI . ........................... 370/469; 395/800; 395/670
`[58] Field of Search .................................. 370/58.1, 58.2,
`370/58.3, 60, 60.1, 61, 79, 82, 83, 85.13,
`85.14, 94.1, 94.2, 94.3, 99; 395/200, 325,
`375,650,800
`
`[56]
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`5,134,610
`5,200,953
`5,249,292
`5,278,834
`
`7 /1992 Shand et al. .............................. 370/60
`4/1993 Spatafore et al .................... 370/85.12
`9/1993 Chiappa .................................. 395/650
`1/1994 Mazzola ................................. 370/94.1
`
`5,280,476
`5,307,343
`5,414,702
`5,414,707
`5,430,709
`
`1/1994 Kojima et al .......................... 370/60.1
`4/1994 Bostica et al ............................. 370/60
`5/1995 Kudoh ....................................... 370/60
`5/1995 Johnston et al. .......................... 370n9
`7/1995 Galloway .................................. 370/13
`
`Primary Examiner-Alpus H. Hsu
`Attorney, Agent, or Firm-Timothy R. Schulte
`
`[57]
`
`ABSTRACT
`
`A method and apparatus are provided to transfer protocol
`data units within a communication network. This transfer(cid:173)
`ring is accomplished with a protocol data unit processor that
`is operated in the communication network. The processor
`includes a preprocessor which establishes subsequent pro(cid:173)
`cessing requirements of a particular protocol data unit
`received from the communication network to generate at
`least one associated directive for the particular protocol data
`unit. Subsequently, a synchronizing mechanism synchro(cid:173)
`nizes the particular protocol data unit witb the at least one
`associated directive to generate a synchronized protocol data
`unit. A restructuring device restructures the synchronized
`protocol data unit in accordance with the at least one
`associated directive for the protocol data unit to generate a
`restructured protocol data unit. In addition, a method of
`operating the protocol data unit processor in a heterogeneous
`communication network is provided.
`
`31 Claims, 7 Drawing Sheets
`
`RESTRUCTURE
`PROTOCOL DATA
`UNIT
`
`310
`
`PROVIDE
`PROTOCOL DATA
`UNIT TO OTHER
`COMPONENTS
`
`312
`
`ZSCALER Ex. 1005 p.1
`
`

`

`J;,181' .. ·--' ~ 158
`
`•••
`
`- - · - - I
`
`,-150
`
`162
`
`FLOW
`BLOCK
`
`L1.~1·
`
`d •
`00. •
`
`~ a. ~ a
`
`~
`
`N
`JXi
`"""" ~
`~
`-..J
`
`rJJ. =(cid:173)tD
`
`~
`i-
`s,
`
`-..J
`
`Ul
`~ Ul
`"' QC
`~ =
`
`.&;.
`
`~
`
`ZSCALER Ex. 1005 p.2
`
`164
`
`168
`
`=··· 1,~~~~A~~ t ,-:cg~
`rnJ ... I I~~~~~~~ I--
`
`-166
`
`170
`FLOW
`BLOCK
`
`CTD •••
`
`174
`
`OIJ ..•
`
`-
`
`-
`
`- _I
`
`172
`SOFTWARE CONTROLLED
`GENERAL PURPOSE PROCESSOR
`
`rnJ .•. I
`
`J
`
`182
`
`I_ -
`
`-
`
`-
`
`FIG. 1
`-PRIOR ART·
`
`

`

`U.S. Patent
`
`Jan. 28, 1997
`
`Sheet 2 of 7
`
`5,598,410
`
`-.;I'
`
`•
`
`r------------,
`.
`l o
`I
`I~
`I
`
`§
`
`§
`
`§
`
`0
`
`0 .,... \..
`
`LO
`0
`,-
`
`t'IJ
`C\I
`,-
`
`C\J .
`(!J
`u..
`
`a.
`a.
`I
`
`C\l
`0
`
`r - - - - -·
`,...
`~ ~
`,...
`I C\I
`,...
`,~
`I
`,...
`,'a
`
`I
`L _ _ _
`
`-
`
`-
`
`I
`
`- - - - - - ,
`
`§
`.
`
`§
`
`-
`
`-
`
`-
`
`_J
`
`ZSCALER Ex. 1005 p.3
`
`

`

`U.S. Patent
`
`Jan. 28, 1997
`
`Sheet 3 of 7
`
`5,598,410
`
`..,
`
`r-(cid:173)
`
`,~ :
`
`I~
`I~
`,,.,..
`
`0
`T""
`
`T " "~
`
`0
`0
`T""
`
`L. -
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`_J
`
`~
`
`r - - - - - - -
`
`co
`0
`T""
`
`.
`CJ
`LL
`
`CL
`CL
`:c
`
`C\I
`
`r
`0 ..-
`~
`I ..-
`1 ~
`I~
`I
`
`-
`
`-
`
`-
`
`-
`
`-
`
`_J
`
`..,
`
`co ..(cid:173)
`..-
`
`§
`
`§
`- - -
`
`§
`- - - - _,
`
`ZSCALER Ex. 1005 p.4
`
`

`

`U.S. Patent
`
`Jan. 28, 1997
`
`Sheet 4 of 7
`
`5,598,410
`
`r - - -
`1~
`:
`,'-§
`
`§
`
`§
`
`§
`
`0 ..-
`
`..-~
`
`L
`
`-,
`
`I
`I
`_J
`
`0
`
`0 ..-\..
`
`r - - - - - - -
`
`co
`0 ..-
`
`~ .
`CJ
`LL
`
`a..
`a..
`::c
`
`-
`
`-
`
`-
`
`-
`
`-
`
`_J
`
`-,
`
`§
`
`§
`
`C\I
`
`I C\I
`..-
`I
`....
`
`r
`0 ..-
`~
`,~
`1 '--a
`
`I
`L
`
`-
`
`-
`
`ZSCALER Ex. 1005 p.5
`
`

`

`-
`
`-
`
`-
`~ M
`- u
`
`. rrE X
`
`11 ,
`
`/'
`
`MUX BY 4
`
`...
`-
`
`I
`
`I
`
`I
`
`l
`
`f
`
`i- .... I-
`
`•
`
`-
`- I-
`M
`... ~ u
`rr= X
`... , l
`i...--210
`
`r+-
`
`CALL
`RETURN
`STACK
`
`LJ
`
`,---105
`
`2 12
`
`Cj
`•
`00
`•
`~
`
`~ a
`
`20 V
`...
`
`-
`
`DUAL
`HEADER
`RAM
`
`I
`
`f ,..-226
`
`..
`I
`RAM
`ADDRESS
`SWITCH'
`l
`HEADER
`LOAD
`CONTROL
`
`l
`
`(230
`
`..
`
`... i-.
`
`/236
`
`COMPARATOR
`
`~
`-~~ ....
`
`N
`
`I,=
`I,=
`.....:t
`
`rJ'.J =(cid:173)n:i
`
`~
`(I)
`s,
`.....:t
`
`ti)
`,..
`ti)
`\C
`00
`,..
`~
`
`~ =
`
`ZSCALER Ex. 1005 p.6
`
`(202
`
`( 2 0
`
`1 r
`
`INSTRUCTION
`MEMORY
`
`--
`
`~
`
`--
`-
`-
`~ -
`
`~
`
`;=:i=.
`
`L
`A
`T
`C
`H
`
`r (214
`
`'f,,. -234
`~
`M
`u _.
`
`-..
`
`X
`
`..
`
`ALU
`
`-
`.
`
`:!!!I
`L
`A
`
`..... T
`.......
`
`C
`H
`
`t.-,,--216
`
`~
`
`,__
`
`•
`
`REGISTER
`~
`RAM
`
`.... _
`'
`I'-..
`
`REGISTER
`~
`/STACK
`RAM
`
`20
`
`208
`
`FIG. 5
`
`

`

`U.S. Patent
`
`Jan.28, 1997
`
`Sheet 6 of 7
`
`5,598,410
`
`0
`0
`C\I
`
`0
`,.-
`
`0
`
`0
`C\I
`C\I
`
`v
`C\I
`N
`
`,--
`
`,.-
`
`,.-
`
`• • •
`•
`
`,-
`
`,....
`
`C\I
`C\J
`C\I
`
`c.o
`•
`(!J -u..
`
`ZSCALER Ex. 1005 p.7
`
`

`

`U.S. Patent
`
`Jan. 28, 1997
`
`Sheet 7 of 7
`
`5,598,410
`
`---300
`
`--£....-
`
`START
`
`302
`
`RECEIVE TWO
`DIFFERENT TYPES
`OF PROTOCOL
`DATA UNITS
`
`304
`
`306
`
`GENERATE
`ASSOCIATED
`DIRECTIVE
`
`SYNCHRONIZE
`EACH PROTOCOL
`DATA UNIT WITH
`ASSOCIATED
`DIRECTIVE
`
`RESTRUCTURE
`PROTOCOL DATA
`UNIT
`
`310
`
`PROVIDE
`PROTOCOL DATA
`UNIT TO OTHER
`COMPONENTS
`
`312
`
`FIG. 7
`
`ZSCALER Ex. 1005 p.8
`
`

`

`5,598,410
`
`1
`METHOD AND APPARATUS FOR
`ACCELERATED PACKET PROCESSING
`
`RELATED INVENTIONS
`
`The present invention is related to:
`Co-pending U.S. patent application Ser. No. 08/366,221,
`filed on Dec. 23, 1994, which is entitled "Method And
`Apparatus For Accelerated Packet Forwarding" by Mark
`Bakke et al.,
`Co-pending U.S. patent application Ser. No. 08/366,221,
`filed on Dec. 23, 1994, which is entitled "Method And
`Apparatus For Radix Decision Packet Processing" by Geof
`Stone,
`Co-pending U.S. patent application Ser. No. 08/366,221,
`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.
`
`FIELD OF THE INVENTION
`
`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
`5 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
`10 network in a manner similar to that by which pieces of mail
`are delivered in a postal delivery system. Data packets, for
`example, are generated by many different types of devices
`and are placed onto a communication network. Typically, the
`data packets are concentrated into a forwarding device, such
`15 as a local bridge or router, and are then directed by desti(cid:173)
`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
`20 (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,
`30 quickly changing technology has made the underlying data
`transmission resources for computer communication net(cid:173)
`works relatively inexpensive. Fiber optics, for example,
`offer 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 important because in typical network
`traffic, 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 traffic 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 bits are being transferred is more impor(cid:173)
`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 is 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
`
`The present invention relates generally to data commu(cid:173)
`nication networks. More particularly, the present invention
`relates to protocol data unit forwarding systems that direct 25
`the flow of protocol data units in the data communication
`networks.
`
`BACKGROUND OF THE INVENTION
`
`35
`
`In a data communication network, a forwarding device
`(e.g., 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 40
`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 45
`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 50
`hand. Some postal delivery systems also have special forms
`of encoded delivery addresses, such as Post Office box
`numbers at a Post Office, which are not recognizable by
`other postal delivery systems such as Federal Express or
`United Parcel Service. Regardless of which particular postal 55
`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 routing code is no longer 60
`sufficient to deliver the piece of mail to the intended desti(cid:173)
`nation and the local delivery office 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 65
`mail may go on through several other processing steps. For
`example, if the piece of mail is going out of the country, it
`
`ZSCALER Ex. 1005 p.9
`
`

`

`5,598,410
`
`15
`
`20
`
`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 5
`analogy, these switches are equivalent to the Post Office in
`a single town with no connection to other Post Offices. In
`some sense, these switches are little different from the first
`class of packet switches described above, but there is one
`substantial difference. The format of the packets (that is, the 10
`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(cid:173)
`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
`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 as a mix of very high speed
`local area networks (LANs) and low speed long distance 25
`point to point lines). Examples of such protocols are the
`United States designed Transmission Control Protocol/In(cid:173)
`ternetwork Program (TCP/IP), and the International Stan(cid:173)
`dards Organization's lnternetworking Protocol/Connection(cid:173)
`less Network Service (IP/CLNS) 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(cid:173)
`eral Express, and the U.S. Postal Service exist to handle the 40
`special needs of mail going to every country, state, city,
`town, and street in the world. Similarly, in computer com(cid:173)
`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 45
`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 however, 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 60
`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(cid:173)
`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.
`
`4
`The approach which uses faster processors simply keeps
`pace with processor dependent (future) demands because the
`traffic which the packet switch will handle will depend upon
`the speed of the user processors being used to generate the
`traffic. 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 traffic load. Furthermore, this approach
`may be impractical as not being cost-effective for wide(cid:173)
`spread use. For example, two high speed machines, distant
`from each other, must have intermediate switches which are
`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 different processors beyond a
`limited number of task divisions. That is, after a certain
`point, the increase in interface overhead outweighs the
`savings obtained from the additional stage. This is particu(cid:173)
`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.
`Currently, most bridge/router
`implementations rely
`heavily on off-the-shelf microprocessors to perform the
`packet forwarding functions. The best implementations are
`able to sustain processing rates approaching 100,000 packets
`per second (PPS). When dealing with media such as ethernet
`or current telecommunications lines, this processing rate is
`more than adequate. When faster media such as Fiber
`Distributed Data Interchange (FDDI) is used, existing pro-
`cessing rates may still be sufficient as long as there is only
`one such high packet rate interface present. When multiple
`high packet rate interfaces are used, 100,000 PPS become
`inadequate. Current software-based implementations for
`bridges/routers are simply not capable of media-rate packet
`forwarding on emerging media such as asynchronous trans(cid:173)
`fer mode (ATM) or Optical Connection-12 Synchronous
`Optical Network (OC-12 SONET) which can accommodate
`55 communication rates up to 6 times the current 100 megabits
`per second limits to rates of 600 megabits per second.
`It should be noted that the ever increasing power of
`off-the-shelf microprocessors might solve the throughput
`problem, but this is probably a vain hope. For example a
`single OC-24 ATM interface can sustain nearly 3 million
`internetworking protocol (IP) packets per second. This is
`over 30 times the rates achieved by the current best software
`techniques. If processing power doubles every year, the wait
`for sufficient processing power to make a software approach
`viable would be at least 4-5 years. In addition, the media
`capabilities will likely continue to increase over such a span
`of years. Additionally, any such processor will likely require
`
`30
`
`35
`
`50
`
`ZSCALER Ex. 1005 p.10
`
`

`

`5,598,410
`
`5
`large amounts of the fastest (most expensive) memory
`available to operate at full speed, resulting in an unaccept(cid:173)
`ably high system cost.
`In general then, the multiprocessor approach is not the
`answer to substantially increasing 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(cid:173)
`processing approach.
`A need still exists for an improved protocol data unit (i.e.,
`frame, cell, or packet) forwarding system which solves the
`above-identified problems in a manner which can better
`handle large numbers of input streams, large numbers of
`output destinations and lines, many different types of com(cid:173)
`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.
`
`SUMMARY OF THE INVENTION
`
`10
`
`6
`The preprocessor preferably establishes the subsequent
`processing requirements of the particular protocol data unit
`by identifying, verifying, and generating at least one asso(cid:173)
`ciated directive for the particular protocol data unit. In
`5 addition, the restructuring device preferably restructures the
`synchronized protocol data unit by deleting, inserting, and
`replacing bits in the synchronized protocol data unit in
`accordance with the at least one associated directive for the
`protocol data unit. Alternatively, the restructuring device
`may, in addition to or in place of modifying particular bits,
`monitor the synchronized protocol data unit by dropping,
`sending, sending a copy of, and/or auditing the contents of
`the synchronized protocol data unit in accordance with the
`at least one associated directives for the protocol data unit.
`In order to accelerate the processing of a received proto-
`15 col data unit, the preprocessor preferably is configured to
`operate on a first and a second protocol data unit such that
`the preprocessor can interleave processing of both the first
`and the second protocol data unit during a single time span.
`In addition, multiple preprocessors connected in either par-
`20 allel or series may be used to increase the through put of
`protocol data units. This use of multiple preprocessors may
`necessitate the use of a more sophisticated synchronizing
`mechanism which is able to track and synchronize more that
`one protocol data unit at a time with the particular associated
`25 directives for each protocol data unit. In addition, the
`preprocessor is configured to establish the at least one
`associated directive for the particular protocol data unit after
`having received only a portion (i.e., the first several bits or
`bytes) of the protocol data unit. The preprocessor may need
`to buffer into memory or store a portion of the particular
`protocol data unit as it is received until a large enough
`portion or the particular portion of the protocol data unit
`which enables the identification of the particular protocol
`data unit is received. Similarly, the restructuring device
`35 preferably is configured to operate on the synchronized
`protocol data unit prior to the protocol data unit processing
`device receiving all of the protocol data unit. This optimi(cid:173)
`zation can be taken a step further by outputting a portion of
`the restructured protocol data unit to a transmitting device
`40 prior to receiving all of the protocol data unit. All of these
`optimizations are particularly important when manipulating
`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 protocol data unit processing device
`in a heterogeneous communication network is provided to
`transfer protocol data units within the communication net(cid:173)
`work. This method is performed by device-implemented
`steps in a series of distinct processing steps that can be
`implemented in one or more processors. In the first process-
`ing step a first and a second protocol data unit are received
`from the communication network where the first and the
`second protocol data unit are of different types. The second
`55 processing step involves establishing the subsequent pro(cid:173)
`cessing requirements of the first and the second protocol
`data unit to generate at least one associated directive for each
`protocol data unit. Each protocol data unit is synchronized
`with the at least one associated directive for each protocol
`data unit to generate a first and a second synchronized
`protocol data unit, respectively. Then, each synchronized
`protocol data unit is restructured in accordance with the at
`least one associated directive for each protocol data unit to
`generate a first and a second restructured protocol data unit,
`respectively. Finally, the first and the second restructured
`protocol data unit are provided to other components in the
`communication network.
`
`30
`
`The present invention provides a packet processing sys(cid:173)
`tem with improved throughput performance by means of a
`method and apparatus for accelerated processing of protocol
`. data units. The present invention addresses the problem of
`media rate forwarding of packets at gigabyte rates by
`providing an architecture for the design of bridges/routers
`that are capable of forwarding packets across different media
`which can sustain multi-gigabyte rates. This architecture
`also includes design approaches for implementing key fea(cid:173)
`tures of a packet-forwarding device operating at these high
`transfer rates, such as filtering functions. By splitting pro(cid:173)
`cessing functions, the present invention avoids the "proces(cid:173)
`sor bottleneck" inherent in prior art processing device archi(cid:173)
`tectures.
`In accordance with a first aspect of the invention, a
`protocol data unit processor is used in a communication
`network to transfer protocol data units within the commu(cid:173)
`nication network. The processor includes a preprocessor
`which establishes subsequent processing requirements of a
`particular protocol data unit received from the communica(cid:173)
`tion network to generate at least one associated directive for 45
`the particular protocol data unit. Subsequently, a synchro(cid:173)
`nizing mechanism synchronizes the particular protocol data
`unit with the at least one associated directive to generate a
`synchronized protocol data unit. A restructuring device
`restructures the synchronized protocol data unit in accor- 50
`dance with the at least one associated directive for the
`protocol data unit to generate a restructured protocol data
`unit. In addition, a method of operating the protocol data unit
`processor in a heterogeneous communication network is
`provided.
`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 60
`different postal delivery systems. By utilizing the prepro(cid:173)
`cessor and restructuring device of the present invention to
`split the required protocol data unit processing functions, the
`present invention is able to significantly increase the through
`put of the processing device, both in terms of the number of 65
`data packets per second and in terms of the number of bits
`per second which pass through the processing device.
`
`ZSCALER Ex. 1005 p.11
`
`

`

`5,598,410
`
`7
`The first and the second protocol data unit may differ from
`one another in several ways in the heterogeneous commu(cid:173)
`nication network including but not limited to being of
`different physical layer media types, different link layer
`signaling protocols, and/or different network layer proto(cid:173)
`cols.
`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 DESCRIPTION OF THE DRAWINGS
`
`10
`
`15
`
`8
`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 com(cid:173)
`puter. The corresponding layers in Open Systems A and B
`5 are called peer layers and communicate through peer pro(cid:173)
`tocols. These peer protocols provide communication support
`for a user's application, performing transaction related tasks
`such as debiting an account, dispensing currency, or cred(cid:173)
`iting 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,
`20 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(cid:173)
`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 messages 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 t