(19) United States
`(12) Patent Application Publication (10) Pub. No.: US 2002/0023168 A1
`Bass et al.
`(43) Pub. Date:
`Feb. 21, 2002
`
`US 200200231 68A1
`
`(54) METHOD AND SYSTEM FOR NETWORK
`PROCESSORSCHEDULING BASED ON
`SERVICE LEVELS
`(75) Inventors: Brian Mitchell Bass, Apex, NC (US);
`Jean Louis Calvignac, Cary, NC (US);
`Marco C. Heddes, Cary, NC (US);
`Michael Steven Siegel, Raleigh, NC
`(US); Fabrice Jean Verplanken, La
`Gaude (FR)
`Correspondence Address:
`Joscelyn G. Cockburn
`IBM Corporation 2Y7/B656
`PO Box 12195
`Research Triangle Park, NC 27709 (US)
`(73) Assignee: International Business Machines Cor
`poration, Armonk, NY
`
`(21) Appl. No.:
`
`09/834,141
`
`(22) Filed:
`
`Apr. 12, 2001
`Related U.S. Application Data
`(63) Non-provisional of provisional application No.
`60/196,831, filed on Apr. 13, 2000.
`Publication Classification
`
`(51) Int. Cl. .................................................. G06F 15/16
`
`(52) U.S. Cl. .............................................................. 709/232
`
`(57)
`
`ABSTRACT
`
`A System and method of moving information units from an
`output flow control toward a data transmission network in a
`prioritized Sequence which accommodates Several different
`levels of Service. The present invention includes a method
`and System for Scheduling the egreSS of processed informa
`tion units (or frames) from a network processing unit
`according to Service based on a weighted fair queue where
`position in the queue is adjusted after each Service based on
`a weight factor and the length of frame, a proceSS which
`provides a method for and System of interaction between
`different calendar types is used to provide minimum band
`width, best effort bandwidth, weighted fair queuing Service,
`best effort peak bandwidth, and maximum burst size speci
`fications. The present invention permits different combina
`tions of Service that can be used to create different QoS
`specifications. The “base' services which are offered to a
`customer in the example described in this patent application
`are minimum bandwidth, best effort, peak and maximum
`burst size (or MBS), which may be combined as desired. For
`example, a user could specify minimum bandwidth plus best
`effort additional bandwidth and the system would provide
`this capability by putting the flow queue in both the NLS and
`WFO calendar. The system includes tests when a flow queue
`is in multiple calendars to determine when it must come out.
`
`Flow Flow
`O
`1
`
`
`
`Flow
`2047
`
`- - - - -
`
`-- a-
`
`- - - -
`
`20
`
`LS
`
`NLS
`
`231
`
`s
`Discard
`--
`3
`
`260a
`- - - -
`
`|-
`Port
`Port
`Port
`Port
`O
`39
`38
`1
`High Priority Target Port Queues
`1
`
`Y -
`
`250
`
`-
`Port
`O
`
`Peak Bandwidth
`Shaping
`3
`y
`
`260
`a
`- -
`
`-
`
`Port
`
`Port
`Port
`39
`1
`Low Priority Target Port Queues
`2
`
`5
`
`272
`Wra
`4
`
`Splunk Inc. Exhibit 1042 Page 1
`
`

`

`Patent Application Publication Feb. 21, 2002 Sheet 1 of 13
`
`US 2002/0023168A1
`
`I "OICH
`
`V/ TSVOJ
`
`
`
`ETTEIT ONE
`
`
`
`ETTET OBC]
`
`
`
`NG] - WWd
`
`CERCICIE|8|WE
`
`XETCHWOO
`
`
`
`S??OSSE OO?Ho?
`
`ETTET?ONE
`
`
`
`ETTET OBCI
`
`3)NITTGEHOS
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Splunk Inc. Exhibit 1042 Page 2
`
`

`

`Patent Application Publication Feb. 21, 2002 Sheet 2 of 13
`
`US 2002/0023168 A1
`
`enenbu? NO
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Splunk Inc. Exhibit 1042 Page 3
`
`

`

`Patent Application Publication
`
`Feb. 21, 2002. Sheet 3 of 13
`
`US 2002/0023168A1
`
`
`
`9
`
`
`
`
`
`
`
`
`
`O
`N
`N
`
`Splunk Inc. Exhibit 1042 Page 4
`
`

`

`Patent Application Publication
`
`Feb. 21, 2002. Sheet 4 of 13
`
`US 2002/0023168A1
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Splunk Inc. Exhibit 1042 Page 5
`
`

`

`Patent Application Publication Feb. 21, 2002 Sheet 5 of 13
`
`US 2002/0023168 A1
`
`
`
`
`
`Packet enqueue
`to a flow queue
`
`list
`management
`action:
`enqueue frame
`
`1109
`
`Service for flow queue not in any calendar
`
`1100
`
`No
`
`1110
`
`Yes
`ote
`
`To F.G. 6
`
`No
`
`Yes
`
`1111
`
`1122
`
`NO
`
`Yes
`
`
`
`
`
`
`
`ff f3
`
`
`
`
`
`Add pointer
`to NLS
`calendar at
`Current time
`
`Add pointer
`to LLS
`calendar at
`Current time
`
`Yes
`
`Configuration
`ero
`
`1115
`
`Add pointer to WFOR at
`location specified by WFQ
`Distance Calculation for
`Flow Startup
`
`Oinred = 1
`
`Qinue = 1
`
`1116
`
`
`
`
`
`MBSCredit. W=MBS.V
`
`Set
`NextGreenTime to
`Current time
`
`
`
`1121
`
`Qin User:1
`
`Splunk Inc. Exhibit 1042 Page 6
`
`

`

`Patent Application Publication Feb. 21, 2002. Sheet 6 of 13
`
`US 2002/0023168 A1
`
`1210
`
`NO
`
`FIG. 6
`
`
`
`No
`
`NextRed Time
`LATER current
`
`
`
`
`
`
`
`Add pointer
`to LS
`Calendar at
`Current time
`
`1215
`
`Add pointer to
`LLS calendar at
`NextRedTime
`
`
`
`NextRed Time
`LATER Current
`
`Add pointer
`to NLS
`Calendar at
`current time
`
`Add pointer to
`NLS Calendar at
`NextRedTime
`1213
`
`1100
`
`C Yes
`ofo
`FOFG. 5
`
`1200
`
`
`
`No
`
`Yes
`
`G. 8
`To Fl
`
`1209
`
`A
`QinRed-12 Yes -02
`
`1200
`
`Yes
`
`2O3
`1
`
`No
`
`Qin BlueF1
`
`Update
`MBSCredit:
`Credit earned
`
`1218
`
`Qinred=1
`
`1279
`
`No
`
`12O1
`
`No
`
`12O2
`
`No
`
`
`
`
`
`1220
`
`Current time
`LATER
`NextGreenTime
`
`
`
`(a
`
`To FG 7
`
`No
`
`Oin Blue=1
`
`1204
`
`1205
`
`1221
`
`
`
`Set
`NextGreenTime to
`Curtent time
`
`
`
`Add pointer to WFO at
`location specified by
`WFO Distance
`Calculation for FiOW
`Startup
`
`
`
`Timestamps are valid, but the flow queue is not in all of the
`Calendar's it needs to be in.
`
`Splunk Inc. Exhibit 1042 Page 7
`
`

`

`Patent Application Publication Feb. 21, 2002 Sheet 7 of 13
`
`US 2002/0023168A1
`
`FIG. 7
`
`12O2
`
`NO
`
`Go From FG 6
`
`
`
`1302
`
`NextGreenTime
`LATER
`Current time
`
`
`
`
`
`
`
`
`
`
`
`Add pointer to WFOR at
`location specified by
`WFO Distance
`Calculation for FiOW
`Startup
`
`1305
`
`
`
`
`
`Add pointer to
`PBS at
`NextGreenTime
`
`1306
`
`Qin Blue=1
`
`
`
`QinGne 1
`
`
`
`Peak component is not in calendar, there is no
`minimum bandwidth component
`
`Splunk Inc. Exhibit 1042 Page 8
`
`

`

`Patent Application Publication Feb. 21, 2002 Sheet 8 of 13
`
`US 2002/0023168A1
`
`FIG. 8
`
`Addpointer to WFaat 1407
`location specified by
`WFOR Distance
`Calculation for Flow
`Startup
`
`4.08
`
`NetGreenTime
`LATER
`Current time
`
`
`
`Add pointer to WFO at 1411
`location specified by
`WFO Distance
`Calculation for Flow
`Startup
`
`1409
`
`
`
`
`
`
`
`Add pointer to
`PBS at
`NextGreenTime
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`from F.G. 6
`
`No
`
`NC
`
`
`
`
`
`144
`A
`Qin Elue1
`
`
`
`
`
`1413
`
`1414
`
`MBSCredit)0
`
`Yes
`
`Peak is not in calendar, minimum bandwidth component is in calendar.
`
`Note that NextGreenTime stamp is examined to determine attachement to either WFOR or PBS
`
`If MBS is specified, the MBSCredit is examined and if positive, adding the flow queue to either the WFO or
`the PBS is permitted.
`
`Splunk Inc. Exhibit 1042 Page 9
`
`

`

`Patent Application Publication Feb. 21, 2002 Sheet 9 of 13
`
`US 2002/0023168A1
`
`FIG. 9
`
`505
`
`LLS
`or NLS
`eels Yes
`
`527
`
`PBS
`Calendar
`
`Yes
`
`management
`action:
`dequeue frame
`
`TO FIG. 11
`
`B O505
`
`()
`
`513
`
`To FIG. 13
`
`
`
`update
`MBSCredit:
`Credit used
`
`TO FIG. 12
`
`Flow Queue
`Service
`
`
`
`
`
`
`
`
`
`
`
`Each calendar type is serviced
`(only one per scheduler tick).
`flow queues are reattached
`only if there are sufficient
`frames in the flow dueue.
`flow queues added into WFO
`with peak bandwidth components
`get the NextGreenTime
`stamp updated.
`
`520
`
`update
`NextGreenTime
`using
`NextGreenTime
`Calculation for
`flow not
`in violation
`
`
`
`
`
`
`
`
`
`
`
`NO
`
`
`
`No
`
`NextGreenTime
`LATER
`Current time
`
`
`
`528
`
`521
`
`Yes
`
`
`
`
`
`526
`MBSCredit20
`
`Yes
`
`OinSlue=0
`
`
`
`
`
`
`
`
`
`
`
`
`
`add pointer to
`WFQ at
`OCation
`specified by
`WFQ
`distance
`calculation
`
`MBSCredit2>OD-Yes
`
`517
`add pointer to PBS at
`time specified by
`NextGreen Time
`Calculation for flow in
`violation
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`add pointer to
`WFO at
`location
`specified by
`WFO
`distance
`Calculation
`
`518
`
`
`
`
`
`update
`NextGreenTime using
`NextGreenTime
`calculation for flow in
`violation
`
`Splunk Inc. Exhibit 1042 Page 10
`
`

`

`Patent Application Publication Feb. 21, 2002 Sheet 10 of 13
`
`US 2002/0023168 A1
`
`FIG. 1 O
`
`500
`
`Yes
`
`Flow queue service
`When QCnt F O at
`start of Service
`
`From FG. 9
`
`
`
`
`
`
`
`Qin Red=0
`FrameCount=0
`Qinuse=O
`NextRedValid=0}
`
`ChinBlueFO
`FrameCount=0
`
`548
`
`PBS
`Calendar
`
`Yes
`
`549
`
`QinGreen=0
`FrameCount=0
`{NextGrn.Valid=0}
`
`
`
`
`
`
`
`NextGreenTime
`LAER
`Current time
`
`
`
`NextGrn.Valid=0}
`
`
`
`Braced {} text indicates function
`necessary to support flow queue
`aging. NextRedValid and
`NextGrnValid are flags used only to
`Support a flow queue aging design.
`(reference 542,545,546,547,549)
`
`Splunk Inc. Exhibit 1042 Page 11
`
`

`

`Patent Application Publication Feb. 21, 2002 Sheet 11 of 13
`
`US 2002/0023168 A1
`
`LLS or NLS Service
`
`
`
`FIG 11
`
`From FIG. 9
`
`
`
`1101
`
`management
`action.
`dequeue frame
`
`FrameCount
`
`Yes
`
`add pointer to
`LLS at time
`specified by
`distance
`calculation
`
`add pointer to
`NLS at time
`specified by
`distance
`Calculation
`
`1111
`
`NextRecTime
`and Red Residue
`as specified from
`distance
`Calculation
`
`Splunk Inc. Exhibit 1042 Page 12
`
`

`

`Patent Application Publication Feb. 21, 2002 Sheet 12 of 13
`
`US 2002/0023168A1
`
`FIG. 12
`
`
`
`513
`
`No
`
`FrameCount
`
`From FIG. 9
`
`
`
`WFC Calendar
`When there is an assured bandwidth component,
`the flow queue is removed from the WFO allowing
`the last frame to be serviced from the NLSILSS
`calendar. If there is a peak bandwidth component,
`the NextGreenTime stamp is updated.
`
`601
`
`FrameCount
`
`Yes
`
`FrameCount
`
`Yes
`
`No
`
`Yes
`
`
`
`Qin Eue=O
`
`604
`
`A
`O605
`
`O FIG. 6
`
`
`
`608
`
`
`
`NextGreenTime
`LATER
`Current time
`
`Yes
`
`607
`
`
`
`
`
`
`
`update
`NextGreetTime using
`NextGreenTime
`calculation for flow not
`in violation
`
`
`
`
`
`
`
`
`
`update
`NextGreetTime using
`NextGreenTime
`Calculation for flow
`in violation
`
`Splunk Inc. Exhibit 1042 Page 13
`
`

`

`Patent Application Publication Feb. 21, 2002 Sheet 13 of 13
`
`US 2002/0023168 A1
`
`1.
`52
`
`FIG. 13
`
`PBS
`Calendar
`
`From FG 9
`
`s
`
`135
`
`
`
`
`
`Port queue
`congested
`
`Yes
`
`management
`action:
`dequeue
`
`NextGreenTime using
`NextGreenTime
`calculation. When flow
`is not in violation
`
`update
`MBSCredit:
`Credit used
`
`1312
`
`FrameCount
`
`Yes
`
`
`
`
`
`Add pointer to WFOR at
`location specified by
`WFO Distance
`Calculation for Flow
`Startup
`
`Add pointer to WFC at
`location specified by
`WFO distance
`calculation
`
`Service PBS Calendar. flow queue is always removed from this
`calendar. NextGreen Time is always recalculated. flow queue is
`placed into WFC only when there is sufficient frames in the
`queue. If MBS is specified, a test for available Credit is performed.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Splunk Inc. Exhibit 1042 Page 14
`
`

`

`US 2002/0023168 A1
`
`Feb. 21, 2002
`
`METHOD AND SYSTEM FOR NETWORK
`PROCESSORSCHEDULING BASED ON SERVICE
`LEVELS
`
`CROSS REFERENCE TO RELATED PATENTS
`0001. This patent relates to and claims the benefit of
`Provisional Patent Application Ser. No. 60/196,831 filed
`Apr. 13, 2000.
`0002 The present invention is related to the following
`documents, all of which are assigned to the assignee of the
`present invention and which are specifically incorporated
`herein by reference:
`0003 Patent application Ser. No. 09/384,691, filed Aug.
`27, 1999 by Brian Bass et al., entitled “Network Processor
`Processing Complex and Methods”, sometimes referred to
`herein as the Network Processing Unit Patent or NPU
`Patent.
`0004 U.S. Pat. No. 5,724,348 entitled “Efficient Hard
`ware/Software Interface for a Data Switch’ issued Mar. 3,
`1998, which patent is sometimes referred to herein as the
`Interface Patent.
`0005 Patent application Ser. No. 09/330,968 filed Jun.
`11, 1999 and entitled “High Speed Parallel/Serial Link for
`Data Communications, Sometimes referred to as the Link
`Patent.
`0006 Various patents and applications assigned to IBM
`for its multiprotocol Switching Services, Sometimes referred
`to as “MSS', some of which include Cedric Alexander as an
`inventor, and are sometimes referred to as the MSS Patents.
`0007 Patent application Ser. No. 09/548,907 (Docket
`RAL9-00-0010) filed Apr. 13, 2000 by Brian M. Bass et al.
`and entitled “Method and System for Network Processor
`Scheduler”. This patent is sometimes referred to herein as
`the Scheduler Structure Patent.
`0008 Patent application Ser. No. 09/548,910 (Docket
`RAL9-00-0014) filed Apr. 13, 2000 by Brian M. Bass et al.
`and entitled “Method and System for Network Processor
`Scheduling Outputs Based on Multiple Calendars”. This
`patent is Sometimes referred to herein as the Calendar
`Scheduling Patent.
`0009 Patent application Ser. No. 09/548,911 (Docket
`RAL9-00-0015) filed Apr. 13, 2000 by Brian M. Bass et al.
`and entitled “Method and System for Network Processor
`Scheduling Based on Calculation”. This patent is sometimes
`referred to herein as the Calculation Patent.
`0010 Patent application Ser. No. 09/548,912 (Docket
`RAL9-00-0017) filed Apr. 13, 2000 by Brian M. Bass et al.
`and entitled “Method and System for Network Processor
`Scheduling Outputs. Using Queuing”. This patent is Some
`times referred to herein as the Queuing Patent.
`0011 Patent application Ser. No. 09/548,913 (Docket
`RAL9-00-0018) filed Apr. 13, 2000 by Brian M. Bass et al.
`and entitled “Method and System for Network Processor
`Scheduling Outputs using Disconnect/Reconnect Flow
`Queues. This patent is Sometimes referred to herein as the
`Reconnection Patent.
`0012 Patent application Ser. No. 09/546,651 (Docket
`RAL9-00-0007) filed April, 2000 by Peter I. A. Barriet al.
`
`and entitled “Method and System for Minimizing Conges
`tion in a Network”. This patent is sometimes referred to
`herein as the Flow Control Patent.
`0013 Patent application Ser. No. 09/547,280 (Docket
`RAL9-00-0004) filed Apr. 11, 2000 by M. Heddes et al. and
`entitled “Unified Method and System for Scheduling and
`Discarding Packets in Computer Networks”. This patent is
`Sometimes referred to herein as the Packet Discard Patent.
`
`BACKGROUND OF THE INVENTION
`0014) 1. Field of the Invention
`0015 The present invention relates to communication
`network apparatuS Such as is used to link together informa
`tion handling Systems or computers of various types and
`capabilities and to components and methods for data pro
`cessing in Such an apparatus. The present invention includes
`an improved System and method for Scheduling the distri
`bution of information units from a flow control system
`coupled to a plurality of network processing unit toward a
`data transmission network through a PMM and MAC. More
`particularly, the present invention involves Scheduling using
`a plurality of algorithms to handle a plurality of users who
`are processing variable size information packets or frames,
`providing an order to the frames being provided from the
`flow control system (which may be of the type described in
`the referenced Flow Control Patent) toward the data trans
`mission network. The present invention includes a System
`for establishing and enforcing different types of Service
`levels for the flows of different users.
`0016 2. Background Art
`0017. The description of the present invention which
`follows is based on a presupposition that the reader has a
`basic knowledge of network data communications and the
`routers and Switches which are useful in Such network
`communications. In particular, this description preSupposes
`familiarity with the International Standards Organization
`(“ISO”) model of network architecture which divides net
`work operation into layers. A typical architecture based on
`the ISO model extends from a Layer 1 (which is sometimes
`referred to a “L1”) being the physical pathway or media
`through which Signals are passed upward through Layers 2
`(or “L2), 3 (or “L3’), and so forth to Layer 7 which is the
`layer of application programming resident in a computer
`System linked to the network. Throughout this document,
`references to Such layers as L1, L2, L3 are intended to refer
`to the corresponding layer of the network architecture. The
`present description also is based on a fundamental under
`Standing of bit Strings used in network communication
`known as packets and frames.
`0018 Bandwidth considerations (or the amount of data
`which a system can handle in a unit of time) are becoming
`important in today's view of network operations. Traffic
`over networks is increasing, both in sheer Volume and in the
`diversity of the traffic. At one time, Some networks were
`used primarily for a certain type of communications traffic,
`Such as voice on a telephone network and digital data over
`a data transmission network. Of course, in addition to the
`Voice Signals, a telephone network would also carry a
`limited amount of “data” (Such as the calling number and the
`called number, for routing and billing purposes), but the
`primary use for Some networks had, at one point in time,
`been Substantially homogenous packets.
`
`Splunk Inc. Exhibit 1042 Page 15
`
`

`

`US 2002/0023168 A1
`
`Feb. 21, 2002
`
`0.019 A substantial increase in traffic has occurred as a
`result of the increasing popularity of the Internet (a public
`network of loosely linked computerS Sometimes referred to
`as the worldwide web or “www.”) and internal analogs of it
`(Sometimes referred to as intranets) found in private data
`transmission networks. The Internet and intranets involve
`transmission of large amounts of information between
`remote locations to Satisfy an ever-growing need for remote
`access to information and emerging applications. The Inter
`net has opened up to a large number of users in geographi
`cally dispersed areas an exploding amount of remote infor
`mation and enabled a variety of new applications, Such as
`e-commerce, which has resulted in a greatly-increased load
`on networks. Other applications, Such as e-mail, file transfer
`and database access further add load to networks, Some of
`which are already under Strain due to high levels of network
`traffic.
`0020 Voice and data traffic are also converging onto
`networks at the present time. Data is currently transmitted
`over the Internet (through the Internet Protocol or IP) at no
`charge, and Voice traffic typically follows the path of lowest
`cost. Technologies such as voice over IP (VOIP) and voice
`over asynchronous transfer mode or ATM (VoATM) or voice
`over frame relay (VoFR) are cost-effective alternatives for
`transmission of Voice traffic in today's environment. AS
`these Services migrate, the industry will be addressing issues
`Such as the changing cost Structure and concerns over the
`trade off between cost of Service and quality of Service in the
`transmission of information between processors.
`0021 Aspects of quality of service include the capacity
`or bandwidth (how much information can be accommodated
`in a period of time), the response time (how long does it take
`to process a frame) and how flexible is the processing (does
`it respond to different protocols and frame configurations,
`Such as different encapsulation or frame header methods).
`Those using a resource will consider the quality of Service
`as well as the cost of Service, with the tradeoffs depending
`on the situation presented.
`0022. Some prior art systems handle outgoing informa
`tion units from a processing System in a variety of ways. One
`Suggestion is to use a round robin Scheduler which fairneSS
`amongst a Set of queues. Another one employs Several
`different levels of priorities and a queue for each. In Such a
`System, you have an absolute priority where the highest
`priority work is processed first and the lowest priority work
`may never be processed.
`0023 Still another method of scheduling outputs
`involves a plurality of prioritized lists of work to be pro
`cessed.
`It is also known to use a hierarchical packet sched
`0024.
`uling System. There are even Systems which use Several
`different Scheduling methods in determining the order in
`which information units are to be sent toward a data trans
`mission network, using a combination of different Schedul
`ing techniques.
`0.025. Other systems have used a weighted priority tech
`nique implemented in the form of a round robin—which
`Serves all queues, with Some queues Served more frequently
`than other queues, based on an algorithm which defines the
`level of Service. Even Such a weighted priority System would
`provide Service to a user who continually exceeds the
`
`Service levels assigned to it, continuing to Serve, albeit leSS
`often, even as it exceeds the assigned Service level and
`making it difficult for the system to enforce a level of service
`policy.
`0026 Considering the size of a transmission packet or
`frame in determining which customers to Serve adds a
`measure of fairness to a Service System, in that a user who
`is processing large frames takes up more of the System
`capacity and therefore should receive Service leSS often than
`a user with Small frames. Some of the prior art Systems
`consider the size of the transmission packet or frame in
`allocating resources, while others do not. Some communi
`cation Systems use a uniform, fixed-size packet, making
`consideration of packet size unnecessary, but others do not
`consider the Size of the packet in allocating resources.
`0027 Other prior art system are directed to handling
`information units which are of a common size as in the
`so-called Asynchronous Transfer Mode (or ATM) system, so
`that size of the information unit is not considered in deter
`mining the priority of the current or a future information
`unit. An ATM system with a weight-driven scheduler is one
`of the solutions which is known in the prior art to schedule
`outputs from an ATM system.
`0028. In any such system which involves weighting and
`queueing, it is desirable to allow for different types of
`service-for example, minimum bandwidth, best effort
`bandwidth, weighted fair queuing Service, best effort peak
`bandwidth, and maximum burst size. While each of these
`types of Service level are well known and accommodated in
`the prior art, it is a challenge to allow for the use of the any
`or all of them in the same System. It is also desirable to
`implement the weighted fair queuing using a System which
`considers the size of the transmission packet in determining
`the priority to be assigned to the packet in the queue.
`0029. Thus, the prior art systems for handling data pack
`ets for transmission to a network have undesirable disad
`Vantages and limitations which have an effect on the per
`ceived fairness of the System.
`
`SUMMARY OF THE INVENTION
`0030 The present invention overcomes the disadvan
`tages and limitations of the prior art Systems by providing a
`Simple, yet effective, way of handling information units or
`frames coming out of a processing System and directing
`frames to output ports for dispatch to an data transmission
`network while providing a variety of different type of service
`levels in the same System.
`0031. The present invention allows a single processing
`System to accommodate users which have Service level
`agreements which include characteristics Such as minimum
`bandwidth, best effort bandwidth, weighted fair queuing
`Service, best effort peak bandwidth, and maximum burst size
`Specifications, and any combinations of these characteristics
`in the same agreement.
`0032. The present invention has the advantage that it
`allows the efficient use of resources and requires a minimum
`overhead to accommodate the various types of Service
`levels. The present System establishes the types of Service
`level agreement characteristics (also referred to as QoS) and
`provides the mechanism for enforcing them through
`manipulation of flow queues within a combination of time
`
`Splunk Inc. Exhibit 1042 Page 16
`
`

`

`US 2002/0023168 A1
`
`Feb. 21, 2002
`
`based calendars and weighted fair queuing calendars. The
`present invention also uses a technique for enforcing a level
`of Service characteristic (for example, a minimum band
`width) by determining the earliest time for the next service
`as a result of the current Service, then testing the next request
`for service to determine whether it is after the allowable time
`for the next service based on the bandwidth established for
`the user.
`0033. The present invention also allows for the use of any
`unused bandwidth by others through the use of a weighted
`fair queuing System which allows for the individual users to
`compete on a weighted fair basis for bandwidth which is
`unused at any given time. That is, even if bandwidth has
`been established for a user (for example, a user with a
`minimum bandwidth), when that bandwidth is not being
`used for that user, it may be used by others.
`0034. The system and method of the present invention
`allows for the fair use of the unused bandwidth by consid
`ering the size of the packet when determining the Service
`order. That is, a user who sends a large packet is Serviced
`later in the queue for unused bandwidth than a user who
`Sends a Small packet.
`0035. The method to accomplish different levels of ser
`Vice is accomplished by establishing different calendars,
`both time based and weighted fair queuing and assigning
`flow queues to locations in one or more calendars. The
`calendarS Selected are determined based on the Service level
`agreement which has been requested and paid for. Then, a
`user who has paid for a minimum bandwidth receives
`priority over others while that user is operating within and
`does not exceed that bandwidth. To the extent that the user
`with a minimum bandwidth exceeds that bandwidth, then
`the user may compete with other users for weighted fair use
`bandwidth allocation according to his Service level agree
`ment using a method which considers the length of the
`transmission packet. Similarly, a user who has arranged for
`a best effort bandwidth is provided with that bandwidth to
`the extent that it is available and a user who has arranger for
`best effort peak bandwidth or maximum burst size service is
`accorded the Services in the System for allocating bandwidth
`of the present invention.
`0036). Other objects and advantages of the present inven
`tion will be apparent to those skilled in the relevant art in
`view of the following description of the preferred embodi
`ment, taken together with the accompanying drawings and
`the appended claims.
`BRIEF DESCRIPTION OF THE DRAWINGS
`0037 Having thus set forth some of the limitations and
`disadvantages of the prior art and Some objects and advan
`tages of the present invention, other objects and advantages
`will be apparent to those skilled in the relevant art in view
`of the following description of the drawings illustrating the
`present invention of an improved routing System and method
`in which:
`0.038
`FIG. 1 is a block diagram for an interface device
`including embedded processor complex which is described
`in the NPU Patent, showing a DN Enqueue system and
`Scheduler useful in practicing the present invention;
`0.039
`FIG. 2 is a block diagram of an embedded proces
`Sor complex of type shown in FIG. 1, with the DN Enqueue
`(and its included Scheduler) useful in understanding the
`present invention;
`
`0040 FIG. 3 illustrates the scheduler of FIGS. 1-2,
`illustrating a System for Scheduling egreSS of variable length
`packets according to the preferred embodiment of the
`present invention, in an "egreSS Scheduler';
`0041
`FIG. 4 illustrates timer base calendar according to
`the preferred embodiment;
`0042 FIGS. 5-8 illustrates the method and system for
`enqueuing packets into the Scheduler System; and
`0043 FIGS. 9-13 are logic flow charts of the calculations
`performed in the egreSS Scheduler of the present invention,
`illustrating the Servicing of a Selected flow queue and
`calendar using the System of the present invention to provide
`minimum bandwidth, best effort bandwidth, weighted fair
`queuing Service, best effort peak bandwidth and maximum
`burst size Specifications, as different method of Sharing
`bandwidth among users.
`0044) DETAILED DESCRIPTION OF THE PRE
`FERRED EMBODIMENT
`0045. In the following description of the preferred
`embodiment, the best implementations of practicing the
`invention presently known to the inventors will be described
`with Some particularity. However, this description is
`intended as a broad, general teaching of the concepts of the
`present invention in a Specific embodiment but is not
`intended to be limiting the present invention to that as shown
`in this embodiment, especially since those skilled in the
`relevant art will recognize many variations and changes to
`the Specific structure and operation shown and described
`with respect to these figures.
`0046 FIG. 1 shows a block diagram of the interface
`device chip that includes the substrate 10 and a plurality of
`Subassemblies integrated on the Substrate. The Subassem
`blies are arranged into an upside configuration and a down
`Side configuration, with the "upside” configuration (Some
`times also referred to as an “ingress”) referring to those
`components relating to data inbound to the chip from a data
`transmission network (up to or into the chip) and “down
`Side” (sometimes referred to as an "egress') referring to
`those components whose function is to transmit data from
`the chip toward the data transmission network in an out
`bound fashion (away from the chip or down and into the
`network). Data flows follow the respective arrangements of
`the upside and downside configurations; thus, there is a
`upside data flow and a downside data flow in the System of
`FIG. 1. The upside or ingreSS configuration elements
`include an Enqueue-Dequeue-Scheduling UP (EDS-UP)
`logic 16, multiple multiplexed MAC's-UP (PMM-UP) 14,
`Switch Data Mover-UP (SDM-UP) 18, System Interface
`(SIF) 20, Data Align Serial Link A (DASL-A) 22 and Data
`Align Serial Link B (DASL-B) 24. Data links are more fully
`described in the Link Patent referenced above, and reference
`should be made to that document for a greater understanding
`of this portion of the system. It should be understood that the
`preferred embodiment of the present invention uses the data
`links as more fully described in that patent, other Systems
`can be used to advantage with the present invention, par
`ticularly those which Support relatively high data flows and
`System requirements, Since the present invention is not
`limited to those Specific auxiliary devices Such as the data
`links which are employed in the preferred embodiment.
`0047 The components depicted on the downside (or
`egress) of the system include data links DASL-A26 and
`
`Splunk Inc. Exhibit 1042 Page 17
`
`

`

`US 2002/0023168 A1
`
`Feb. 21, 2002
`
`DASIL-B 28, system interface SIF 30, Switch data mover
`SDM-DN 32, enqueue-dequeue-scheduler EDS-DN 34 and
`multiple multiplexed MAC's for the egress PMM-DN 36.
`The substrate 10 also includes a plurality of internal static
`random access memory components (S-RAM's), a traffic
`management scheduler (TRAFFIC MGT SCHEDULER,
`also known as the Egress Scheduler) 40 and an embedded
`processor complex 12 described in greater depth in the NPU
`Patent referenced above. An interface device 38 is coupled
`by the respective DMU busses to PMM 14,36. The interface
`device 38 could be any suitable hardware apparatus for
`connecting to the L1 circuitry, Such as Ethernet physical
`(ENET PHY) devices or asynchronous transfer mode fram
`ing equipment (ATM FRAMER), both of which are
`examples of devices which are well known and generally
`available for this purpose in the trade. The type and size of
`the interface device are determined, at least in part, by the
`network media to which the present chip and its System are
`attached A plurality of external dynamic random acceSS
`memory devices (D-RAMS) and a S-RAM are available for
`use by the chip.
`0.048 While here particularly disclosed for networks in
`which the general data flow outside the relevant Switching
`and routing devices is passed through electric conductors
`Such as wires and cables installed in buildings, the present
`invention contemplates that the network Switches and com
`ponents thereof could be used in a wireleSS environment as
`well. For example, the media access control (MAC) ele
`ments herein disclosed may be replaced with Suitable radio
`frequency devices, such as those made from Silicon germa
`nium technology, which would result in the conne