Case 4:17-cv-00141-ALM Document 17-3 Filed 05/19/17 Page 1 of 11 PageID #: 214
`
`(12)
`
`United States Patent
`Lemaire et al.
`
`(10) Patent N0.:
`(45) Date of Patent:
`
`US 6,205,149 B1
`*Mar. 20, 2001
`
`US006205149B1
`
`(54) QUALITY OF SERVICE CONTROL
`MECHANISM AND APPARATUS
`
`(75) Inventors: gmmgiA'TLemalrg’ ?Ctlfn;APa“l J‘
`laco e, oWnsen ; 0 n .
`
`5,353,283 * 10/1994 Tsuchiya ............................ .. 370/230
`5,461,611 * 10/1995 Drake, Jr. ........................... .. 370/420
`
`5,485,455 * 1/1996 Dobbins ............................. .. 370/401
`5,550,816 * 8/1996 Hardwick ........................... .. 370/392
`*
`
`
`Flanders, Ashland; David Lipschutz, Lexington; Leonard Schwartz,
`Bedford; David C. Ready, WestWood;
`William D. Townsend, Groton, all Of
`MA (Us)
`
`(73) Assignee: 3Com Corporation, Santa Clara, CA
`(US)
`
`(*) Notice:
`
`This patent issued on a continued pros-
`ecution application ?led under 37 CFR
`1.53(d), and is subject to the tWenty year
`?gtzarm provlslons of 35 USC'
`'
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`(21) Appl. No.: 08/927,650
`
`Sep- 11, 1997
`(22) Flled:
`(51) Int. cl.7 ................................................... .. H04L 12/28
`(52)
`370/401; 370/400
`(58) Field Of Search ................................... .. 370/395, 400,
`370/401, 412, 420, 421, 428, 429, 396,
`397, 407, 410
`
`(56)
`
`_
`References Cited
`U.S. PATENT DOCUMENTS
`
`* *
`
`
`
`’
`’
`1/1997
`5’598’410
`5,625,622 * 4/1997
`5,666,353 * 9/1997
`395/20053
`5,774,656 * 6/1998 Hattorl
`__ 370/409
`5,920,705 * 7/1999 Lyon
`6,094,435 * 7/2000 Hoffman ............................ .. 370/414
`
`*
`
`.
`.t d b
`C1 6
`y exammer
`
`Primary Examiner—Douglas W. Olms
`Assistant Examiner—Ricardo M. Pizarro
`(74) Attorney, Agent, or Firm—Weingarten, Schurgin,
`Gagnebin & Hayes LLP
`
`(57)
`
`ABSTRACT
`
`.
`.
`_
`_
`bl
`f
`d t
`d
`(“Q S”)
`Q lt
`f S
`varla es or pre e ermme
`o
`ervlce
`ua1y o
`protocol Type data units are stored in a cache memory. For
`data units that are associated With a ?ow, thirteen bytes
`selected out of the Internet Protocol (“IP”) header are
`employed as at least a portion of a key to perform a Cache
`lookup to obtain at least one Quality of Service variable
`from the cache. Both routing and QoS information may be
`stored in the cache for retrieval upon a single lookup
`Operation‘
`
`5,136,580 * 8/1992 Videlock ............................ .. 370/403
`
`24 Claims, 4 Drawing Sheets
`
`70’
`
`so
`DETERMINE
`¥ PROTOCOL
`TYPE
`
`83
`
`N
`
`GET ENTRY FROM
`54
`\
`QCR SELECTOR
`
`PROVlDE LOOKUP 90
`J
`KEY
`
`86
`
`GET PRIORITY
`DESIGNATION
`FROM QCR TABLE
`
`92
`EMPLOY ACA J
`
`@A
`
`

`

`Case 4:17-cv-00141-ALM Document 17-3 Filed 05/19/17 Page 2 of 11 PageID #: 215
`
`U.S. Patent
`
`Mar. 20, 2001
`
`Sheet 1 0f 4
`
`US 6,205,149 B1
`
`mcmaxomm
`
`2)
`
`w wlw. 3 .3 3
`
`
`
`2:82 2522 2502 2302
`
`
`
`
`
`
`
`282262 momt?s 8%95 8%25 96:25
`
`
`
`
`
`
`
`
`
`
`
`
`
`{362 {262 {@502 {@202
`
`

`

`n2e9mm.mm
`
`ma%mmmHS
`
`112B“.3”.9DMw5,
`
`Case 4:17-cv-00141-ALM Document 17-3 Filed 05/19/17 Page 3 of 11 PageID #: 216
`aC
`w
`6
`
`7..mS.
`eU
`
`l1S6528Eon.a.mUmziosz3Himw>mommmaPI
`
`I16mmmama.ngmm,
`
`m.mmmmogM.mQEOmEEOEmPMam965wPmszE
`wagon:
`
`
`
`
`
`
`
`NEE;magmaEOE:magma7memwmooEacmmmooEacmmwwomn.n4E3::2ng
`335:827.185%;.H.manmz
`
`
`

`

`Case 4:17-cv-00141-ALM Document 17-3 Filed 05/19/17 Page 4 of 11 PageID #: 217
`
`U.S. Patent
`
`Mar. 20, 2001
`
`Sheet 3 0f 4
`
`US 6,205,149 B1
`
`70”‘ RECEIVE FRAME
`
`DETERMINE
`PROTOCOL
`TYPE
`
`80L
`
`83
`
`@ Y
`
`N
`
`8L GET ENTRY FROM
`QCR SELECTOR
`
`PROVIDE LOOKUP )0
`KEY
`
`‘
`GET PRIORITY
`86
`\ DESIGNATION
`FROM QCR TABLE
`
`END
`
`92
`EMPLOY ACA _J
`
`FIG. 3
`
`

`

`Case 4:17-cv-00141-ALM Document 17-3 Filed 05/19/17 Page 5 of 11 PageID #: 218
`
`U.S. Patent
`
`Mar. 20, 2001
`
`Sheet 4 0f 4
`
`US 6,205,149 B1
`
`CLASS OF SERVICE
`0
`7
`
`PROTOCOL IP
`TYPE
`
`TCP
`
`,
`
`I
`
`IS
`
`QCR SELECTOR 81
`FIG. 4
`
`QCR TABLE 82
`
`EUE PRIORITY
`C:
`
`(NNA-AAAAJ :A-ANNNNM) (AJCDQJCDOOODOJD
`
`FIG. 5
`
`0123
`1230
`6 2301
`3012 END
`
`END
`
`FIG. 7
`
`0123
`1023
`01 23
`2013
`0123
`1023
`0123
`
`1023
`0123
`2013
`0123
`1023
`0123 END
`
`

`

`Case 4:17-cv-00141-ALM Document 17-3 Filed 05/19/17 Page 6 of 11 PageID #: 219
`
`US 6,205,149 B1
`
`1
`QUALITY OF SERVICE CONTROL
`MECHANISM AND APPARATUS
`
`CROSS-REFERENCE TO RELATED
`APPLICATIONS
`
`Not Applicable
`
`STATEMENT REGARDING FEDERALLY
`SPONSORED RESEARCH OR DEVELOPMENT
`Not Applicable
`
`BACKGROUND OF THE INVENTION
`The present invention is generally related to telecommu
`nications networks, and more particularly to implementing
`Quality of Service (“QoS”) processing control Within such
`netWorks.
`Devices such as bridges and routers are employed to
`move data units betWeen end-stations in a telecommunica
`tions netWork. The data units may represent various types of
`traf?c including voice, video and computer data. Because
`some traffic may be associated With real time
`communication, processing of certain data units may be
`particularly time critical. For example, processing delay or
`loss of data units associated With a real time voice or video
`transmission could signi?cantly degrade the quality of such
`communication. HoWever, delays in eXchange of some types
`of computer data may not signi?cantly affect the quality of
`such communication. It may also be desirable to prioritiZe
`traf?c Within a given type of communication.
`One method for prioritiZing data units in a telecommu
`nications netWork is With QoS parameters. Each data unit
`Within the telecommunications netWork includes a header
`portion and a data portion. The header portion includes
`information for handling the data unit such as Source
`Address and Destination Address information. The header
`may also include a QoS priority indicator. It is knoWn to
`insert QoS information in the transport layer of the header.
`Devices Which receive and retransmit data units Within the
`telecommunications netWork then eXamine the QoS portion
`of the header of such data units and assign priority accord
`ingly. HoWever, QoS has not yet been implemented in an
`effective manner.
`
`BRIEF SUMMARY OF THE INVENTION
`In accordance With the present invention, Quality of
`Service (“QoS”) variables for data units of at least one
`predetermined protocol Type are stored in a cache memory.
`For data units in a one Way connection (“?oW”) With
`identi?ed Source Address and Destination Address, thirteen
`bytes selected out of the Internet Protocol (“IP”) header are
`employed as at least a portion of a key to perform a cache
`lookup to obtain at least one QoS variable. The QoS variable
`is employed to prioritiZe the data unit for processing.
`Enhanced performance is provided for data units of a
`speci?ed protocol type that are associated With a ?oW. Both
`routing and QoS information can be loaded into the cache.
`Such routing and QoS information can then be retrieved by
`executing a single cache lookup.
`Token buckets may be employed to facilitate QoS imple
`mentation. A token bucket is associated With at least one
`?oW. Tokens are then added to the token bucket at speci?ed
`time intervals. A counter is employed to track token count,
`and the rate at Which tokens are added indicates a rate limit
`for frames that can be scheduled through the token bucket.
`The token count indicates the number of bytes that can be
`sent through the bucket, thereby de?ning a transmission rate
`limit.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`55
`
`60
`
`65
`
`2
`In order to further facilitate smooth operation the bridge/
`router can implement a Random Early Drop (“RED”) pro
`cedure. Logic circuits generate a “congested ports” bitmask
`to indicate Which output ports are deemed to be close to
`over?oWing. For each output port Which is indicated to be
`congested, the logic circuits con?gure a “RED shift value.”
`The RED shift value is the length in bits of a bitmask that
`is ANDed With a random number to yield a result, N, that
`indicates a number of frames to be queued. The Nth frame
`is intentionally dropped. Hence, a relatively small number of
`packets are dropped such that end-stations recogniZe the
`situation and respond by transmitting at a loWer rate, thereby
`relieving congestion and reducing the chance that output
`queues Will over?oW.
`
`BRIEF DESCRIPTION OF THE DRAWING
`
`The invention Will be more fully understood in vieW of the
`folloWing Detailed Description of the Invention, in conjunc
`tion With the DraWing, of Which:
`FIG. 1 is a simpli?ed block diagram of a telecommuni
`cations bridge/router;
`FIG. 2 is a block diagram Which illustrates the mother
`board and netWork interface modules of FIG. 1;
`FIG. 3 is a How diagram Which illustrates implementation
`of QoS control;
`FIG. 4 illustrates memory tables employed by the bridge/
`router for QoS control; and
`FIGS. 5—7 illustrates queue prioritiZation.
`
`DETAILED DESCRIPTION OF THE
`INVENTION
`
`Referring to FIGS. 1 and 2, a bridge/router for use in a
`telecommunications netWork includes a motherboard 12 and
`at least one netWork interface module 14 Which are inter
`connected through a backplane 16. Separate interface mod
`ules support Ethernet, Fiber Distributed Data Interface
`(“FDDI”) and Asynchronous Transfer Mode (“ATM”) traf
`?c. In one embodiment each 10/100 Mb Ethernet interface
`module has siX ports, each gigabit Ethernet interface module
`has one port, each FDDI interface module has siX ports and
`each ATM interface module has tWo OC3 ports or one OC12
`port. The ports provide connections to other devices in the
`netWork, through Which data units can be received and
`transmitted. Incoming data units may be bridged, routed,
`translationally bridged and ?ltered by the bridge/router.
`Logic circuits in the motherboard and interface modules are
`responsible for data unit reception and transmission, parsing
`Data Link and NetWork Layer headers, looking up source
`and destination Media Access Control (“MAC”) and Net
`Work Layer addresses and making forWarding decisions.
`The motherboard 12 includes an Address Cache ASIC
`(“ACA”) 26 With associated address cache memory 28, a
`Frame Processor (“FP”) 30 and a Master Buffer ASIC
`(“MBA”) 32. The Address Cache ASIC 26 is responsible for
`performing cache 28 lookups on Destination Addresses
`(“DAs”) and Source Addresses (“SAs”). The Address Cache
`ASIC is employed to obtain MAC addresses for bridging
`support and NetWork Layer addresses for routing support.
`The Master Buffer ASIC 32 is responsible for data buffer
`management in buffer RAM 22.
`Each netWork interface module includes buffer RAM 22,
`a Transmit ASIC (“TA”) 25 and a Receive ASIC (“RA”) 27.
`The Transmit ASIC and Receive ASIC are speci?c to the
`type of data traf?c Which the netWork interface device is
`designed to support (such as Ethernet, ATM and FDDI). The
`
`

`

`Case 4:17-cv-00141-ALM Document 17-3 Filed 05/19/17 Page 7 of 11 PageID #: 220
`
`US 6,205,149 B1
`
`3
`Receive ASIC 27 functions to perform a preliminary analy
`sis on incoming data units. The Transmit ASIC 25 functions
`to transmit data units.
`The Receive ASIC 27 includes a Receive State Machine
`(“RXSM”) 40, a Receive Header Processor (“RHP”) 46 and
`a Receive Frame Processor (“RFP”) 48. The Receive State
`Machine is responsible for receiving data units through one
`or more ports from an associated communications link. After
`receiving a data unit, the Receive State Machine 40 gener
`ates data unit status information. The status information,
`Which contains error information and byte and frame count
`data on a per port basis, is stored in registers 44. The Receive
`Header Processor 46 is responsible for identifying data units
`to be bridged or routed, determining inbound data unit
`encapsulation type, and performing protocol speci?c pro
`cessing for routed data units. The Receive Header Processor
`also determines Which VLAN, if any, each incoming frames
`is received on. There are different versions of Receive
`Header Processors 46 for different netWork interface types,
`e.g., Ethernet, FDDI and ATM. The Receive Header Pro
`cessor 46 is primarily implemented in microcode. A Receive
`Segmentation DMA controller (“RSEG”) 50 controls stor
`age of received data units Within appropriate buffer RAM 22
`locations and forWards status information to the Receive
`Frame Processor 48. Information in a VLAN forWarding
`table 49 is employed by the Receive Frame Processor 48 to
`verify if the data unit is alloWed to be forWarded through the
`outbound interface. In particular, the Receive Frame Pro
`cessor 48 is responsible for making forWarding decisions
`based on information supplied by the Receive Header Pro
`cessor 46, Address Cache ASIC 26, Receive State Machine
`40, the RSEG 50 and VLAN con?guration information
`contained in con?guration tables associated With the
`Receive Frame Processor. The Receive Frame Processor 48
`also generates Transmit Vectors for data units being pro
`cessed in hardWare over a fast processing path and Receive
`Vectors for data units being passed to the Frame Processor
`30 softWare for further processing over a sloWer path. The
`Receive Frame Processor 48 is implemented partially in
`microcode.
`The Transmit ASIC 25 includes a Transmit State Machine
`(“TXSM”) 58, a plurality of Transmit State Machine FIFOs
`59, and a Transmit Header Processor (“THP”) 60. A Trans
`mit Segmentation Controller (“TSEG”) 61 serves to move
`data unit segments from locations Within the Buffer RAM 22
`into an input FIFO designated as the TSEG FIFO 63, Which
`comprises an input FIFO to the Transmit Header Processor
`60. The Transmit Header Processor 60 performs any neces
`sary header translations and, upon completion of such
`translations, moves the translated header to the Transmit
`State Machine FIFO 59.
`The Transmit Header Processor 60 also inserts VLAN
`tags into frames as necessary. Data units are forWarded from
`the Transmit State Machine FIFO 59 over the respective
`output port 20 of the netWork interface module 14. The
`Transmit State Machine 58 is responsible for controlling
`transmission of data units from the respective output port 20.
`FolloWing transmission, the Transmit State Machine gener
`ates data unit transmit status information Which is stored in
`registers 66. The status information includes error informa
`tion and transmit byte and frame count information on a per
`port basis. Different versions of the Transmit State Machine
`58 are provided for different netWork interface module
`types, e.g., Ethernet, FDDI and ATM.
`FIGS. 3 and 4 illustrate data unit processing in conjunc
`tion With a netWork interface module con?gured for Ethernet
`type traf?c. When an Ethernet frame enters the Receive
`
`35
`
`40
`
`45
`
`55
`
`10
`
`15
`
`20
`
`25
`
`30
`
`4
`Header Processor 46 as shoWn in step 70, the header portion
`of the frame is eXamined as shoWn in step 72. Given 20 a
`header With the format: Destination Address (“DA”)/Source
`Address (“SA”)/Type (e.g., IPv4, Appletalk etc.)/Internet
`Protocol (“IP”) header, the OrganiZation Unique Identi?er
`(“OUI”) is compared to the upper three bytes of the DA. If
`the OUI does not match the upper three bytes of the DA,
`then the frame is forWarded to the Frame Processor 30 for
`further processing by softWare as shoWn in step 74. If the
`OUI matches the upper three bytes of the DA, then the loWer
`three bytes of the DA are eXamined to determine Whether the
`value indicated by the loWer three bytes of the DA falls
`Within a prede?ned range as shoWn in step 76. The upper and
`loWer bounds of the prede?ned range are maintained in ?rst
`and second respective registers. The loWer three bytes of the
`DA are compared With each of the ?rst and second registers
`to determine Whether the loWer three bytes of the DA fall
`Within the prede?ned range. If the loWer three bytes of the
`DA do not fall Within the range, then the frame is forWarded
`to the Frame Processor 30 for further processing by softWare
`as shoWn in step 74. If the loWer three bytes of the DA fall
`Within the prede?ned range, then the DA matches the
`address speci?ed for the bridge/router and the location of the
`Type ?eld is eXamined as shoWn in step 78. In particular, the
`value of the ?eld folloWing the SA ?eld is compared With a
`predetermined value (1500) beloW Which the ?eld is
`assumed to be a Type ?eld.
`The speci?c protocol Type is determined as shoWn in step
`80, Where prede?ned values correspond to speci?c Types,
`e.g., 0800 corresponds to IPv4. The frame is then examined
`to determine if it is associated With a How as shoWn in step
`83. A?oW is a one Way connection of frames With positively
`identi?ed Source Address and Destination Address. Step 83
`may be implemented as folloWs:
`
`bridgedPacket = (unicast && NOT this MAC DA);
`if (packet not IP) {
`?oW=FALSE;
`} else if ((packet is broadcast) II (packet is an IP fragment))
`?oW=FALSE;
`} else if (bridgedPacket && (NOT Bridged-FloW-Enable)) {
`floW=FALSE
`} else if ((COS-Means-FloW &&
`((packet is PACE) II (packet is 802.1 CoS
`tagged)» II
`(Bridged-Means-Flow && bridgedPacket) II
`(Routed-Means-FloW && !bridgedPacket)) {
`floW=TRUE;
`}else if (packet IP protocol is in IP FloW Filter table) {
`if ( (packet is UDP) &&
`(packet is unicast) &&
`(UDP dest port !=1698) &&
`(UDP dest port != 1699) &&
`(
`(UDP dest port < UDP port rangel low) {I
`(UDP dest port > UDP port rangel high)) &&
`(UDP dest port < UDP port range2 low) {I
`(UDP dest port > UDP port range2 high))
`
`(
`
`60
`
`65
`
`If the frame is associated With a How (?oW=TRUE), a
`13-byte IPv4 ?oW ID is employed an indicated in step 90.
`The 13-byte ?oW ID includes IP protocol Type, IP SA, IP
`DA, and UDP Source and Destination ports. The Address
`Cache ASIC 26 is then employed, and QoS variables are
`
`

`

`Case 4:17-cv-00141-ALM Document 17-3 Filed 05/19/17 Page 8 of 11 PageID #: 221
`
`US 6,205,149 B1
`
`5
`returned as shown in step 92. In particular, the Address
`Cache ASIC 26 returns a token bucket depth indicator, a
`transmit queue designator, a loss ?ag, an excess transmit
`queue designator, an excess loss ?ag, a designator for excess
`action to be taken on non- conforming frames, a retag enable
`indicator and a retag class designator. The excess transmit
`queue designator designates the transmit queue for non
`conforming frames. If retag enable is set then the frame will
`be retagged and requeued rather than dropped in the event
`that bridge/router traf?c prevents initial queueing and trans
`mission. Since both routing and QoS information are stored
`in the address cache, frame forwarding can be commenced
`after a single lookup operation.
`The Address Cache ASIC also returns a QoS enable bit.
`When set, the QoS enable bit indicates that the QoS
`information in the Cache is valid. When not set the QoS
`enable bit indicates that the frame is not actually associated
`with a ?ow, even though the result ?ow=TRUE was reached
`in step 83. When ?ow=TRUE and the QoS enable bit
`indicates that the frame is not actually associated with a
`?ow, the frame is processed as a non-?ow frame.
`If the frame is not associated with a How (?ow=FALSE),
`the Receive Header Processor forwards the MAC DA, IP
`DST or IP SRC and DST, and lookup key length indicator to
`the ACA. The protocol Type and Class of Service (“CoS”)
`are employed as indices into the QCR Selector 81 as shown
`in step 84 to obtain a 4-bit value. The 4-bit value is then
`employed as an index into the QoS Control Register
`(“QCR”) Table 82 as shown in step 86. The QCR Table 82
`provides a priority designation in one of eight priority levels.
`Each entry in the QCR Table 82 includes eight ?elds
`totalling 32-bits. 20-bits are employed to designate token
`bucket depth. 2-bits are employed to designate which of the
`four queues associated with each port to transmit on. 1-bit is
`employed as a loss ?ag. The loss ?ag indicates the loss bit
`setting of the transmit vector. 2-bits are employed to desig
`nate the excess transmit queue, which designates the trans
`mit queue for non-conforming frames. 1-bit is employed as
`an excess loss ?ag. 2-bits are employed to designate excess
`action to be taken on non-conforming frames. 1-bit is
`employed for retag enable, and 3-bits are employed to
`designate retag class. If retag enable is set then the frame
`will be retagged and requeued rather than dropped if bridge/
`router traffic prevents initial queueing and transmission.
`There are sixteen class-based QCRs which the Receive
`Frame Processor employs to assign QoS variables on a
`per-traf?c class basis. The QCRs may be assigned as fol
`lows:
`
`QCR 0
`QCR 1
`QCR 2
`QCR 3
`QCR 4
`QCR 5
`QCR 6
`QCR 7
`QCR 8
`QCR 9
`QCR 10
`QCR 11
`QCR 12
`QCR 13
`QCR 14
`QCR 15
`
`IP Unicast (Best Effort, except TCP/IP)
`IP Multicast (non-RSVP flows)
`IP Broadcast
`TCP/IP
`IPX Unicast
`IPX Multicast and Broadcast
`Appletalk Unicast
`Appletalk Broadcast and Unicast
`8021p Class O
`8021p Classes 2-4
`8021p Classes 5-7
`Unused
`Unused
`Unused
`Unused
`Default Class - all frames not otherwise classi?ed
`
`The QCR selector 81 has separate sections 85 for unicast,
`multicast and broadcast traf?c. Within each section, the
`
`6
`Receive Header Processor protocol number is employed as
`an index to obtain a word. TCP/IP is handled as a separate
`protocol to allow UDP and TCP frames to be given different
`QoS control. The 802.1p traf?c class is used to select the
`correct nibble within the word. The QCR selector may be
`implemented as:
`
`10
`
`15
`
`nibble qcrSelectorTable [192];
`if(packet is TCP/IP){ //this passed from RHP to RFP
`protocolIndex = 6;
`} else if (rhpProtocolIndex > 5) {
`protocolIndex = 7;
`} else { //rhpProtocolIndex is between 0 and 5 inclusive
`protocolIndex = rhpProtocolIndex;
`//protocolIndex now ranges from O to 7 inclusive
`}
`if (packet is unicast) {
`qcrIndex = O;
`
`if (packet is broadcast) {
`qcrIndex = 64;
`
`if (packet is multicast) {
`qcrIndex = 128;
`
`qcrIndex+=protocolIndex<<3;
`//if packet was PACE or 802.1q CoS tagged -
`//take three bits of C05 from RHP
`qcrIndex+=RHP.CoS;
`qcr = qcrTable[qcrIndex];
`
`25
`
`Token buckets are employed in SRAM to implement QoS
`parameters with traf?c control algorithms. The token bucket
`algorithm is implemented in a packet scheduler. Each token
`bucket is initially empty at a time Zero. Tokens are added to
`a token counter at speci?ed intervals of time to indicate a
`rate limit for frames that can be scheduled through the token
`bucket. The token count re?ects a credit for how many bytes
`can be sent through the bucket without violating a speci?ed
`rate limit. The bucket has a maximum depth which re?ects
`buffering available for the bucket and also governs the ?rst
`level of traf?c scheduled through the bucket. The token
`count never exceeds the bucket depth.
`There are 128 token buckets and each token bucket is
`speci?ed by a 20-bit token counter and a 12-bit token bucket
`rate (128*32=4 Kbits). The twelve bit token bucket depth is
`expressed in units of 256 bytes, so bucket depths range from
`256 bytes to 212 times that or 1 Mbyte. The token bucket
`rate is expressed in units of 16 bytes per millisecond. Each
`bucket may control up to the aggregate incoming data rate
`on all ports associated with an interface module.
`FIG. 5 illustrates queue prioritiZation on a per port basis.
`Four queues, designated 0, 1, 2 and 3 are associated with
`each port, and each frame is associated with at least one such
`queue for transmission. The Master Buffer ASIC is con?g
`ured with a queue drainage schedule that governs the
`relative rate at which each of the four queues is drained to
`the Transmit Header Processor. Frames are sequentially
`loaded in the queues and selected for transmission based
`upon the illustrated prioritiZation ordering scheme. Frames
`associated with queue 0 are always given the highest priority
`and frames associated with queue 3 are always given lowest
`priority. Queue 1 is a lower priority than queue 0, and higher
`priority than queues 2 or 3. However, queues 1 and 2
`implement cross over sharing at a predetermined depth (six
`frames deep is shown) into each such queue. In the illus
`trated example when ?ve frames associated with queue 1 are
`transmitted, two frames associated with queue 2 are then
`transmitted, assuming such queues are loaded with frames.
`Traf?c associated with queue 0 is preferably of a protocol
`Type that will not utiliZe all available bandwidth and starve
`
`35
`
`45
`
`55
`
`65
`
`

`

`Case 4:17-cv-00141-ALM Document 17-3 Filed 05/19/17 Page 9 of 11 PageID #: 222
`
`US 6,205,149 B1
`
`7
`queues 1, 2 and 3. For example, RSVP Type traf?c can be
`limited by other mechanisms Within the bridge/router and
`hence may be assigned to queue one. Further, administrative
`overhead data transmitted in frames betWeen devices in the
`netWork may be assigned to queue 0 in order to facilitate
`smooth netWork operation.
`In the alternative embodiment illustrated in FIG. 6 equal
`Weighting is given to each queue. As a result, each queue is
`presented With drainage equal opportunities. FIG. 7 illus
`trates a drainage schedule With relative Weighting of 8-4-2-1.
`Multiple drainage schedules may be employed, and each
`port can be drained according to any of the drainage sched
`ules.
`In order to further facilitate smooth operation the bridge/
`router implements a Random Early Drop (“RED”) proce
`dure. The Frame Processor 30 con?gures a congested ports
`bitmask to indicate to the Receive Frame Processor 48
`Which output ports are deemed to be nearly full of queued
`frames. The Frame Processor determines Which output ports
`are congested based upon Master Buffer ASIC 32 statistics
`and Master Buffer ASIC queue lengths. For each output port
`Which is congested, the Frame Processor con?gures a “RED
`shift value.” The RED shift value is a length, in bits, of a
`bitmask that is ANDed With a random number generated by
`the Receive Frame Processor. The resulting number, N, is
`the number of frames to be queued, and the Nth frame is
`intentionally dropped. When the Nth frame is dropped, a
`neW random number is generated and the countdoWn to the
`neXt dropped frame begins. The drop rate resulting from the
`RED procedure is a function of the RED shift value and the
`generated random numbers. In particular, Drop Rate=
`TotalDrops/TotalPackets=2/(N+1).
`The Frame Processor dynamically adjusts the RED shift
`value for congested output ports based on feedback from the
`Master Buffer ASIC. Hence, small numbers of packets are
`dropped before output queues are over?owing, and a per
`centage of the end-stations generating the congesting traf?c
`should respond With loWer transmission rates.
`Having described the preferred embodiments, other
`embodiments that incorporate concepts of the presently
`disclosed invention Will become apparent to those of skill in
`the art. Therefore, the invention should not be vieWed as
`limited to the disclosed embodiments but rather should be
`vieWed as limited only by the spirit and scope of the
`appended claims.
`What is claimed is:
`1. A method for assigning at least one Quality of Service
`variable to an Ethernet frame in a telecommunications
`device, comprising the steps of:
`receiving said Ethernet frame at a netWork interface
`module of said device con?gured for Ethernet type
`traffic, said received Ethernet frame having a header;
`determining if said received Ethernet frame includes both
`positively identi?ed source and destination addresses,
`Wherein said determining if said received Ethernet
`frame includes both positively identi?ed source and
`destination addresses includes comparing a unique
`identi?er With a ?rst portion of a destination address
`selected from the header, Wherein said unique identi?er
`is associated With the bridge/router, and comparing a
`second portion of the destination address With a pre
`determined range of values in the event that the unique
`identi?er matches the ?rst portion of the destination
`address;
`determining, in the event that the second portion of the
`destination address is Within the predetermined range
`
`10
`
`3O
`
`35
`
`45
`
`55
`
`65
`
`8
`of values, Whether a protocol type of said received
`Ethernet frame is an IP protocol type, Wherein said
`determining Whether said protocol type of said Ethernet
`frame is an IP protocol type includes comparing the
`protocol type With at least one predetermined value;
`associating said received Ethernet frame With a How in the
`event said received Ethernet frame includes both posi
`tively identi?ed source and destination addresses; and
`in the event said protocol type of said received Ethernet
`frame is an IP protocol type and said received Ethernet
`frame is associated With a ?oW, indexing into a memory
`Within said device using selected portions of said
`header to obtain, via a single lookup, both said at least
`one quality of service variable and routing information
`associated With said received Ethernet frame.
`2. The method of claim 1 further including the step of
`determining a data unit protocol type from the protocol type
`?eld of the selected portions of the data unit header, and
`determining a class of service and employing the data unit
`protocol type and class of service to obtain a transmission
`priority designator if the data unit is determined not to be
`associated With a ?oW.
`3. Apparatus for determining a Quality of Service variable
`to be employed by a telecommunications device When
`processing a received Ethernet frame, comprising:
`a netWork interface module con?gured for Ethernet type
`traffic, said netWork interface module operative to
`receive said Ethernet frame, and Wherein said Ethernet
`frame includes a header;
`a memory in Which at least one Quality of Service
`variable is stored together With routing information;
`a ?lter operative to determine Whether said received
`Ethernet frame is associated With a How by ascertaining
`Whether a protocol type of said received Ethernet frame
`is an IP protocol type and Whether said header portion
`of the received Ethernet frame indicates a source
`address and a destination address that are both posi
`tively identi?ed, Wherein said ?lter is operative to
`ascertain Whether said protocol type of said received
`Ethernet frame is an IP protocol type by
`comparing the protocol type ?eld of the received Eth
`ernet frame With at least one predetermined value to
`determine said protocol type of said received Ether
`net frame, and
`Wherein said ?lter is operative to ascertain Whether said
`source address and said destination address are posi
`tively identi?ed by
`comparing a unique identi?er associated With the
`bridge/router With a ?rst portion of the destination
`address, and
`comparing a second portion of the destination address
`With a predetermined range of values if the unique
`identi?er matches the ?rst portion of the destination
`address; and
`processor circuitry operative to select a How identi?er
`including at least a portion of said header to obtain, via
`a single lookup, both said at least one Quality of
`Service variable and routing information associated
`With said received Ethernet frame.
`4. The apparatus of claim 3 Wherein the processor cir
`cuitry is operative to determine a data unit protocol type and
`class of service and to employ the data unit protocol type and
`class of service to obtain a transmission priority designator
`if the data unit is determined not to be associated With a ?oW.
`5. The method of claim 1, Wherein said at least one
`Quality of Service variable includes a token bucket depth
`indicator.
`
`

`

`Case 4:17-cv-00141-ALM Document 17-3 Filed 05/19/17 Page 10 of 11 PageID #: 223
`
`US 6,205,149 B1
`
`9
`6. The method of claim 1, wherein said at least one
`Quality of Service variable includes a transmit queue des
`ignator.
`7. The method of claim 1, Wherein said at least one
`Quality of Service variable includes a loss ?ag.
`8. The method of claim 1, Wherein said at least one
`Quality of Service variable includes an eXcess transmit
`queue designator.
`9. The method of claim 1, Wherein said at least one
`Quality of Service variable includes an eXcess loss ?ag.
`10. The method of claim 1, Wherein said at least one
`Quality of Service variable includes a designator for eXcess
`action to be taken on non-conforming frames.
`11. The method of claim 1, Wherein said at least one
`Quality of Service variable includes a retag enable indicator.
`12. The method of claim 1, Wherein said at least one
`Quality of Service variable includes a retag class designator.
`13. The method of claim 1, Wherein said at least one
`Quality of Service variable includes a Quality of Service
`enable bit indicating Whether the at least one Quality of
`Service variable is