`
`
`
`
`
`
`
`
`
`a2, United States Patent
`US 6,839,321 B1
`(10) Patent No.:
`
`
`
`
`
`
`Jan. 4, 2005
`(45) Date of Patent:
`Chiruvolu
`
`US006839321B1
`
`
`
`
`(54) DOMAIN BASED CONGESTION
`
`MANAGEMENT
`
`
`
`
`
`Inventor: Girish Vsr Chiruvolu, Richardson, TX
`
`(US)
`
`(75)
`
`
`
`
`
`
`
`
`
`(73) Assignee: Alcatel, Paris (FR)
`
`
`
`
`
`
`
`
`(*) Notice:
`Subject to any disclaimer, the term ofthis
`
`
`
`
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 918 days.
`
`
`
`
`
`
`
`(22)
`
`
`
`
`
`(21) Appl. No.: 09/618,196
`
`
`
`
`
`
`Filed:
`Jul. 18, 2000
`
`
`
`
`
`
`(SL)
`TInt, C7 eee cecessseeeneeneeneeneeneeneeneees HO4L 12/26
`(52) US. Ch we 370/230.1; 370/231; 370/235.1
`
`
`
`
`
`
`
`
`
`
`
`(58) Field of Search oo... cece 370/229-236,
`
`
`
`
`
`
`370/400, 401, 410, 412-416, 352-354;
`
`710/52-57
`
`
`
`(56)
`
`
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`
`
`
`
`
`4,736,363 A
`
`4,901,277 A
`
`5,088,032 A
`
`4/1988 Aubinetal.
`
`
`
`
`
`2/1990 Solowayet al.
`2/1992 Bosack
`
`
`
`
`
`
`(List continued on next page.)
`FOREIGN PATENT DOCUMENTS
`
`
`
`
`
`ABSTRACT
`(57)
`
`
`
`
`
`
`The Domain-based Congestion Management method and
`
`
`
`
`
`
`apparatus detects and regulates congestion in a Diff-serv
`
`
`
`
`
`
`network. It use an improvRED method for congestion detec-
`
`DE 43 16 872 Al=11/1994
`
`
`
`
`tion at the core routers and token bucket filters for traffic
`
`
`
`
`
`
`
`
`
`
`
`0 503 469 A2
`EP
`9/1992
`
`
`
`
`
`
`
`
`
`
`
`
`
`regulation at the ingress nodes.In addition, improvREDalso
`WO
`WO 00/41365
`7/2000
`
`
`
`
`
`
`
`
`
`
`
`provides feedback control. ImprovRED uses three thresh-
`OTHER PUBLICATIONS
`
`
`
`
`
`
`
`
`
`olds for detecting congestion: a minth, a maxth and a
`
`
`
`
`
`
`
`FeedbackThreshold, which lakes a value between the minth
`
`
`
`
`
`
`
`
`FM. Anjum et al. Fair Bandwidth Sharing Among Adaptive
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`and the maxth thresholds. Whenever the average queue size
`and Non—Adaptive Flowsin the Internet, Proceedings IEEE
`
`
`
`
`
`
`
`
`is greater than minth and less than Feedback-Threshold,all
`
`
`
`
`
`
`Infocom 1999. The Conference on Computer Communica-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`outgoing packets are marked appropriately to indicate a
`tions, 18Annual Joint Conference of the IEEE Computer
`
`
`
`
`
`
`potential onset of a congestion period. When the average
`
`
`
`
`
`
`
`
`and Communications Societies, New York, New York, Mar.
`
`
`
`
`
`
`
`queue size is greater th FeedbackThreshold (but less than
`
`
`
`
`
`
`
`21-25, 1999, Proceedings IEEE Infocom, The Computer
`
`
`
`
`
`
`
`
`maxth) packets are dropped probabilistically and all the
`
`
`
`
`
`
`
`Communica, vol. 3, Mar. 12, 1999, pp. 1412-1420.
`
`
`
`
`
`
`
`
`outgoing packets are marked appropriately to denote the
`
`
`
`
`
`
`
`
`
`
`W-J Kim et al., The FB—Red Algorithm for TCP over ATM,
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`dropping phase. Whenthe average queuesize is greater than
`IEEE Globecom 1998, Globecom 1998, The Bridge to
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`the maximum threshold, all incoming packets are dropped.
`Global Integration, Sydney, Nov. 8-12, 1998, IEEE Global
`
`
`
`
`
`
`Telecommunications Conference, New York, New York,
`
`
`
`
`
`
`
`IEEE, US, vol. 1, Nov. 8, 1998, pp. 551-555.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Fair Bandwidth Sharing Among Adaptive and Non—Adap-
`
`
`
`
`
`
`
`
`tive Flows in the Internet; Farooq M. Anjum , et al.
`
`
`
`XP-000878257; pp. 1412-1420.
`
`
`
`
`
`
`
`The FB-Red Algorithm for TCP over ATM; Wood—June
`
`
`
`
`
`Kim,et al; XP—000894360; pp. 551-555.
`
`
`
`
`
`
`Supporting Differentiated Services Using ATM ABR Ser-
`
`
`
`
`
`
`vice; Richard Rabbat, et al.; pp. 210-213.
`
`
`
`
`
`
`
`Service Differentiation Through End—-to End Rate Control in
`
`
`
`
`
`
`Low Bandwidth Wireless Packet Networks; Thyagarajan
`
`
`
`
`Nandagopal, et al.; pp. 211-220.
`
`
`
`
`
`
`A Simple Packet Scheduling and Buffer Management
`
`
`
`
`
`
`Schemefor Scalable Support of QoSin the Internet; KJ Loh,
`
`
`
`
`et al.; pp. 276-281.
`
`
`
`
`
`
`Randomized Token Buckets: Reducing the Buffers Required
`
`
`
`
`
`
`
`
`in Multiplexors, J. Andrew Fingerhut, et al., IEEE 1997, pp.
`
`
`
`
`
`
`215-219.
`
`
`
`
`
`
`
`
`Primary Examiner—Douglas Olms
`
`
`
`
`
`Assistant Examiner—Van Kim T. Nguyen
`
`
`
`
`
`
`
`(74) Attorney, Agent, or Firm—Sughrue, Mion, PLLC;
`
`
`
`
`Jessica W. Smith; V. Lawrence Sewell
`
`
`
`
`
`
`
`
`
`
`42 Claims, 16 Drawing Sheets
`
`
`
`
`
`{ ——» ROUNDTRIPESTIMATION
`BETWEE!
`ROOF
`
`
`INGRESSAND EGRESS NODES,
`
`
`
`;
`:
`:
`iei=
`id
`i=
`iB
`=
`
`THE LOCAL
`‘CONGESTIONCLEARANCE
`
`NOTIFICATIONOCCURS HERE
`
`
`
`
`
`
`THE LOCAL
`CONGESTIONNOTIFICATION
`
`OCCURS HERE
`
`
`2
`
`
`
`
`
`
`THRESHOLDVALUE
`OFAVE. QUEUE SIZE
`
`
`VARYING OF PKT_WT WITH DEMAND AND LCN MESSAGES
`
`
`
`
`
`
`
`
`
`
`AVERAGEQUEUESIZEATTHENGRESSTOF
`
`nibseeneeee
`
`°
`
`
`
`
`
`Splunk Inc.—Exhibit 1014 Page 1
`
`Splunk Inc. Exhibit 1014 Page 1
`
`

`

`
`
`US 6,839,321 B1
`
`
`Page 2
`
`
`
`U.S. PATENT DOCUMENTS
`
`
`
`
`
`
`
`
`
`
`3/1993 Kramer etal.
`5,191,650 A
`
`
`
`cleo pehneider
`oe A
`/
`ain et al.
`rts
`
`
`
`
`
`
`
`
`
`
`4/1995. Gouldet al.
`5,404,565 A
`:
`4/1995 Yoshizawaet al.
`5,408,562 A
`
`
`
`
`:
`
`
`
`6/1995 Nemirovskyet al.
`5,426,674 A
`
`
`
`7/1995 Rahnema
`5430729 A
`
`
`
`5591972 A
`5/1996.
`Iki
`
`
`
`1/1997 Rahnema
`5506722 A
`
`
`7/1997 Makishima
`5644.713 A
`
`
`
`2/1998 Tkeda
`5719853 A
`oan.
`
`
`
`
`
`2/1999 Jensenetal.
`5,870,564 A
`
`
`
`3/1999 Corbin
`5 881241 A
`
`ood.
`.
`
`
`
`3/1999 Teplitsky
`5,884,043 A
`
`
`
`
`
`6/1999 Hatono et al. we. 370/230
`5,914,936 A
`
`
`
`
`6/1999 Attanasioet al.
`5,918,017 A
`
`
`
`
`11/1999 Civanlaret al.
`5,996,021 A
`
`
`
`
`6,147,970 A * 11/2000 Troxel ...... eee 370/235
`
`
`
`
`
`*
`
`
`
`
`
`
`
`
`
`6/2001 Skirmont........... ee 370/229
`6,252,848 B1 *
`
`
`
`
`
`
`
`6,333,917 B1 * 12/2001 Lyonetal. ............ 370/412
`
`
`
`
`
`
`
`6,404,735 B1 *
`6/2002 Beshai et al... 370/230
`
`
`
`
`
`
`
`6,424,624 Bl *
`7/2002 Galand et al. ec 370/231
`6,487,170 B1 * 11/2002 Chenet al. vce 370/231
`
`
`
`
`
`
`
`en
`6,510,160 B1 *
`1/2003 Nikuieetal. .........
`... 370/412
`
`
`
`
`
`
`
`
`
`.
`oe
`.
`
`6,535,482 B1 *
`3/2003 Hadi Salim etal. ........ 370/229
`
`
`
`
`
`
`
`
`
`
`«
`eS
`:
`
`
`
`
`
`
`
`6,556,578 B1
`4/2003 Silberschatz et al.
`....... 370/412
`
`
`
`
`
`
`
`6,614,756 B1 *
`9/2003 Morgenstern etal.
`...... 370/230
`
`
`
`
`
`
`
`6,618,378 B1 *
`9/2003 Giroux etal.
`........... 370/395.1
`
`
`
`
`
`
`
`6,643,260 B1 * 11/2003 Klothetal. we. 370/235
`
`
`
`
`
`
`
`6,646,988 B1 * 11/2003 Nandyetal. ...
`... 370/235
`6,657,962 B1 * 12/2003 Barri et al. oe. 370/235
`
`
`
`
`
`
`
`
`«
`an
`:
`
`
`
`
`
`
`
`6,675,220 B1
`1/2004 McCloghrie et al.
`....... 709/232
`
`
`
`
`
`
`6,680,906 B1 *
`1/2004 Nguyen..........
`w.. 370/229
`
`
`
`
`
`
`. 370/229
`6,680,907 Bl *
`1/2004 Bonaventure
`
`
`
`
`
`6.690645 BL *
`2/2004 A
`tal
`370/230
`
`
`
`
`WEVA CL A versrerecesees
`205
`
`
`* cited by examiner
`
`
`
`
`
`
`
`
`
`Splunk Inc.
`
`Exhibit1014
`
`Page 2
`
`Splunk Inc. Exhibit 1014 Page 2
`
`

`

`
`U.S. Patent
`
`
`
`
`Jan. 4, 2005
`
`
`
`
`
`Sheet 1 of 16
`
`
`
`US 6,839,321 B1
`
`Noighboring
`DS Demain
`
`
`
`
`
`
`
`
`bs Domain core
`
`
`
`
`Network
`
`teteteses,
`“
`
`\
`He
`ranettvovteeneesy,
`oa
`
`c
`.
`
`
`
`t{\
`
`
`
`Host 1
`
`
`
`Fig. 1
`
`DIFF-SERV DOMAIN
`
`
`(PRIOR ART)
`
`
`
`Splunk Inc.
`
`Exhibit1014
`
`Page 3
`
`Splunk Inc. Exhibit 1014 Page 3
`
`

`

`
`U.S. Patent
`
`
`
`Jan. 4, 2005
`
`Sheet 2 of 16
`
`
`
`US 6,839,321 B1
`
`yeyoedAranaud
`youaxeSjtqayyJt‘(0'T)Yateananbsyayoedbutobyno[TeTO}(ZITq'TIIG)sItTq94yTeW
`
`
`
`
`
`00T———abezaaepaqybtambutaow[eTquauodxauopaseqaztsananbaberaaeayyaqe{noTep
`
`
`
`
`
`OpT——>aguAqpaptoapseAqt{tqeqozdayyyqtHqayoeday]ananbusazodosp
`
`
` abeiaae)Jt{OST——(T'T)YaTAsqeyoedGurobano[[eJoy(ZITq'TIIq)SITqayyyAeW
`
`
`
`
`
`09T-——mSqeyoedHbutwooutayydoip(yzxew<aztsananb
`
`
`
`
`
`
`
`OlT——Weyoedayyananbua(yQuIW>azIsananbaberaae)jt
`
` ay}anaenbua}(plousaryLyoeqpaey>eztsanenbabertane>yqutIw)JT OZT——>‘ayoed
`
`(yaxXew>azIsananb-abexaae5proysariy,yoeqpeay)jT
`
`OfT——(TT)seqasAtsnotaead
`
`
`
`
`
`TeATiae
`
`
`
`SACON3YOOLYWHLINOSTYG3ySHLOLSNOILVOISIGOW
`
`
`
`éOld
`
`Splunk Inc.
`
`Exhibit 1014
`
`Page 4
`
`Splunk Inc. Exhibit 1014 Page 4
`
`

`

`
`U.S. Patent
`
`
`
`
`Jan. 4, 2005
`
`
`
`
`Sheet 3 of 16
`
`
`
`US 6,839,321 B1
`
`
`
`
`
`aseudsso]jayoedouyng‘paunod0ucsabu0s(e907
`
`
`
`
`
`
`
`UIBWOPJOdBUlpeN90UoI}seBu04jng'vONsabuCd|e00]ON
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`UIEWOPSiu}0}dnJe}OSpa}d9}epUCSeBuoDON
`
`apousseibaauyeaqualaju|Lgae
`
`
`
` aseud
`
`
`
`sso|jayoedulpuepewnod0uoNsaBbuoo2907]
`
`
`
`
`
`
`
`NOILSSONO9NIVWOG1V907ONILNASSYd3ayYOJAWSHOSLIG-OMLFIdWISV
`
`
`
`
`
`
`
`€Old
`
`
`
`Splunk Inc.
`
`Exhibit 1014.
`
`Page5
`
`Splunk Inc. Exhibit 1014 Page 5
`
`
`
`
`

`

`
`U.S. Patent
`
`
`
`
`Jan. 4, 2005
`
`
`
`
`Sheet 4 of 16
`
`
`
`US 6,839,321 B1
`
`
`
`LINO3WEOd—LaNo
`
`
`
`
`
`
`
`
`
`
`
`————__LNI0d3009AY3S431I0.————_
`
`
`
`
`
`
`
`QGASANNAILNSYYNO
`
`
`
`JLASdOS/SOLSHL
`
`
`
`vyOld
`
`Splunk Inc.
`
`Exhibit 1014
`
`Page6
`
`Splunk Inc. Exhibit 1014 Page 6
`
`
`
`

`

`
`U.S. Patent
`
`
`
`
`Jan. 4, 2005
`
`
`
`
`Sheet 5 of 16
`
`
`
`US 6,839,321 B1
`
`
`
` TOKEN BUCKETFILTER CONNECTED TO DIFF-SERV DOMAIN
`
`
`
`
`
`
`FIG. SA
`
`
`
`TBF
`
`
`
`we
`
`
`
`
`R
`
`
`
`COMPONENTS OF A TOKEN BUCKETFILTER
`
`FIG. 5B
`
`
`
`Splunk Inc.
`
`Exhibit1014
`
`Page7
`
`Splunk Inc. Exhibit 1014 Page 7
`
`

`

`
`U.S. Patent
`
`
`
`
`Jan. 4, 2005
`
`
`
`
`Sheet 6 of 16
`
`
`
`US 6,839,321 B1
`
`DATA PACKET
`
`
`
`200
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`VARY THE NUMBER OF TOKENS
`
`
`
`
`
`
`CONSUMEDBYDATA OFUNIT SIZE,
`
`
`
`
`
`PkiWt!, BASED ON DEMAND AND
`
`STATE,
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`PACKET TRANSMIT PACKET
`
`
`
`iS
`
`
`
`
`Pkt_sizesPktWt! <=
`
`
`
`
` DON'T TRANSMIT
`
`
`
`AVAILABLE TOKENS IN BUCKET,
`
`
`
`
`IN BUCKET?
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`FLOWCHART FOR TBF-BASED RATE CONTROL METHOD
`
`FIG. 6A
`
`
`
`Splunk Inc.
`
`Exhibit1014
`
`Pages
`
`Splunk Inc. Exhibit 1014 Page 8
`
`

`

`
`U.S. Patent
`
`
`
`
`Jan. 4, 2005
`
`
`
`
`Sheet 7 of 16
`
`
`
`US 6,839,321 B1
`
`
`
`
`
`Pkt Wt) +—- 1.0
`Initialize:
`
`
`
`
`
`
`
`PktWt) is always within [minPktWt?,maxPktwe?]
`
`
`
`
`
`
`
`
`MD is a monotonously decreasing function that takes a value (0,1)
`
`
`
`
`
`
`
`
`
`MI is a monotonously increasing function that takes a positive value
`
`
`
`
`
`
`
`
`
`
`
`j denotes the label corresponding to fixed route between a given pair
`
`
`
`of ingress/egress nodes
`
`
`
`
`
`
`
`
`
`
`for every ith round trip time (between ingress and egress nodes)
`
`
`
`During congestion-free periods
`
`
`
`
`
`
`
`if(average TBF queue size at ingress node == DemandThrsh?)
`
`
`
`) «230
`Pktwe? ~«— pkewt),
`* mD(pktwe),
`
`
`
`
`
`
`
`
`
`/* decrease the pktwt? during congestion free periods, based on demand
`
`
`at TBF */
`
`else {
`
`
`
`
`
`
`
`
`
`> 1) PktWt]-«— max(1, PktWt] ,* MD(Pktwe]_,))
`if (PktWt? ,
`
`
`
`
`
`
`
`
`< 1) Pktwe) — min(1, pkewt),* MI(Pktwtd_,)1}
`if (Pkewt?.,
`
`
`
`
`
`
`
`/* restore PktWt? close to 1.0 */
`
`
`
`
`
`
`
`
`
`
`
`.
`
`
`7
`
`
`
`if Pkewe).< 1.
`
`
`
`
`
`
`
`
`the bigger it will be during
`
`
`[minPktWt?, 1) on to
`
`
`
`* MD(PkeWt), ) 7220
`
`
`
`
`
`At congestion notification time
`
`
`
`
`)
`(maxPkewt)
`- 1) (1 - Pkewtd.,
`
`
`
`PRtWt} q— ———______—______rd 5}
`
`
`
`(1 - minPkewt?)
`
`
`
`
`
`
`
`/* The smaller the Pkewe? just before LCN,
`
`
`
`
`
`congestion period.
`A uniform mapping of
`
`
`
`
`(1, maxPktWet?)
`intervals */~—7 250
`
`
`
`During congestion period
`
`
`
`
`
`
`
`Pkewt)«+— Pkewe), * MI(Pktwt).) if Pkewt),
`
`
`
`
`
`On receipt of congestion clearance notification
`
`
`
`
`
`
`
`
`Select a random time less than RTT and,
`
`
`
`
`PktWe) -«— Pkewt? ,
`
`
`
`
`
`
`
`
`
`
`# 1+ 240
`
`
`
`
`
`
`
`
`
`THE TBF-BASED CONGESTION MANAGEMENTALGORITHM AT INGRESS NODES
`FIG. 6B
`
`
`
`
`
`Splunk Inc.
`
`Exhibit1014
`
`Page9
`
`Splunk Inc. Exhibit 1014 Page 9
`
`

`

`U.S. Patent
`
`Jan. 4, 2005
`
`Sheet 8 of 16
`
`US 6,839,321 B1
`
`
`
`
`
`NOLLVOLEILONNOLIS39NO9
`
`33HSNd90
`
`asre
`
`!SNL
`{ado-2Tete
`
`
`
`ZOld
`
`
`
`3ZIS3NIND“SAV40
`
`3IVWACTOHS3YHL
`
`EWANNOLSEONODNOUWWIISdMGNNOY-—|
`
`
`
`
`wanneeeecteecececeeeeteeeeeeeeteeeeteesLecceeeeeenececeeceeedeeceeceeeeeeeeseersetdeeeeeseeed
`
`SSOVSS3WNOTONVONVW30HLIMLMLydJOONIAMYA
`
`JQL SSIYONI HL LY 3ZI$ 33ND JOVUSAY
`
`SplunkInc.
`
`Exhibit 1014
`
`Page 10
`
`aS
`
`o—
`LHOISM LaXSVd
`Me = oo en eeee
`
`Splunk Inc. Exhibit 1014 Page 10
`
`

`

`
`U.S. Patent
`
`
`
`
`Jan. 4, 2005
`
`
`
`
`Sheet 9 of 16
`
`
`
`US 6,839,321 B1
`
`
`
`one
`
` WDIdXWNIMPIdNIW
`
`
`
`
`YALNOYFYOOVLVALVLSG31S39NO9SHSLNOY3409LYSLVLS3IYSNOWSIONOD
`
`i''''i‘t‘‘‘4{4''.‘4a'!
`
`
`
`
`
`
`
`
`
`JCONSSIYONILYONVW3GONIAYVAHLIMONOTY
`
`
`
`
`
`SOINVNAGIMLyd40WVHSVIOSLVLS
`
`8Old
`
`SplunkInc.
`
`Exhibit1014
`
`Page 11
`
`Splunk Inc. Exhibit 1014 Page 11
`
`

`

`
`
`US 6,839,321 B1
`
`oO.
`
`—-
`
`—L
`
`u
`WY
`
`zo
`
`2<
`
`—_
`
`—
`
`
`U.S. Patent
`
`
`
`Jan. 4, 2005
`
`
`
`
`Sheet 10 of 16
`
`
`NL
`
`u
`
`
`
`
`
`”a
`
`2 =~
`
`N
`
`.
`
`ke
`
`O
`=> u
`=
`17p
`uu
`
`
`
`wo
`a.
`
`2 =™
`
`N
`
`
`
`Splunk Inc.
`
`Exhibit1014
`
`Page 12
`
`uc
`
`o
`
`Splunk Inc. Exhibit 1014 Page 12
`
`

`

`U.S. Patent
`
`Jan. 4, 2005
`
`Sheet 11 of 16
`
`US 6,839,321 B1
`
`
`
`
`
`
`
` x(SSO1LMdNIGagNOLLONGSYSALTY)(A)$49143409
`
`
`
`
`
`WdHLIMLNSW3AONdINIT1¥u3A0SSOTTIVYSAO
`
`E2901
`
`LL9¢EL
`
`9S8'PL
`
`€229'SL
`
`“ULA
`
`
`
`AWSHOSWdGaSOdOud3HLJOJONVWHOSYAd
`
`3801LANOWd40%JWSHOSWOd
`
`OlSls
`SSSYONIIW|YOOLV
`S48SSQON
`
`3W3H9SWOVEdaS4NON
`
`SSOTNd%‘(3HO9)034
`
`
`
`88ht
`
`ccte'9
`
`SP69'2
`
`8c0E01
`
`96F'Lt
`
`C692cb
`
`34091V
`
`(x}SIGON
`
`NOLLW2l
`
`SplunkInc.
`
`Exhibit1014
`
`Page 13
`
`Splunk Inc. Exhibit 1014 Page 13
`
`

`

`
`U.S. Patent
`
`
`
`
`Jan. 4, 2005
`
`
`
`
`Sheet 12 of 16
`
`
`
`US 6,839,321 B1
`
`NOILWZITILA
`S481SSAYONILY(SGNOO3S)AV1SGJOVYSAV
`
`
`
`
`LE61220
`
`
`
`—S16%26'0
`
`£22200}
`
`
`
`c6SEL¢|
`
`
`
`O6E6EE'|
`
`
`
`LZE68€|
`
`
`
`JIWSHOSWOdSHLSOJONVWYOAYAdAVIS
`
`LbSls
`
`SplunkInc.
`
`Exhibit1014
`
`Page 14
`
`
`
`
`
`
`
`
`
`
`
`
`
`Splunk Inc. Exhibit 1014 Page 14
`
`

`

`
`U.S. Patent
`
`
`
`Jan. 4, 2005
`
`Sheet 13 of 16
`
`
`
`US 6,839,321 B1
`
`Pid4z1s0
`
`006!OS}OO8LOSZLOOZLOS9t0091
`
`
`
`(So3S)SWIL
`
`0008
`
`0002
`
`0009
`
`000s
`
`000%
`
`0008
`
`0002
`
`0001
`
`AONANOAYS
`
`|
`
`al
`
`OSS}
`00S0
`
`OSl!002:o0€
`
`OSE
`
`481 SSSYONI NY LV 3ZIS ANAND “SAV
`
`
`
`@'0=“TILANOLLNEIMISIOLMid
`
`
`
`
`
`
`
`
`
`AGONSSSYONINYLWAZISNANO“SAV
`
`debSls
`
`VelOld
`
`SplunkInc.
`
`Exhibit1014
`
`Page 15
`
`Splunk Inc. Exhibit 1014 Page 15
`
`

`

`U.S. Patent
`
`Jan. 4, 2005
`
`Sheet 14 of 16
`
`ete)OPb
`
`O8l
`
`3]9b
`
`|02!
`
`ss
`=
`AONSNDAYS
`
`2c
`
`o
`
`US 6,839,321 B1
`
`60=NOILWZIILALVSWSHOSWOG-NON
`
`
`'8°0=NOILVZITILAIvSWAHOSWOC-NON
`
`
`
`S30ON3uO00SHLyNOILVYNd
`
`
`
`AWAHOSWOd-NONHLM
`
`ASVHddOUdLANOVd4ONOILNEIYLSIG
`
`
`
`
`3SVHddOUdLaWOVdJONOILNSILSId
`S3GON3x09SHLVNOLEN
`
`AWSHOSWOG-NONHLIM
`
`
`deb“Old
`
`VelOld
`
`
`
`(SO4S)NOIWYNG3SVHddowd
`
`
`
`
`
`l
`
`
`
`
`
`
`
`($938)NOILLVUNG3SVWHddONd
`
`S é
`02ShOLS
`09osOpof02OF
`
`AONSNOAYS
`
`SplunkInc.
`
`Exhibit1014
`
`Page 16
`
`Splunk Inc. Exhibit 1014 Page 16
`
`

`

`U.S. Patent
`
`Jan. 4, 2005
`
`Sheet 15 of 16
`
`US 6,839,321 B1
`
`GpbrS€€SZzSISpbvSe€Se2St+tgod0
` dvbOldVrlSls
`
`
`
`
`
`ASWHddOUGL3MOVdJONOILNEHLSIG3SWHddOWdLaWOVd4ONOILNEIYLSIA
`
`
`
`
`
`
`
`
`
`(S93S)NOLLVYNGSSVHddONG:WOd(SOaS)NOLLWYNGSSVHddOUd‘Wod
`60=NOILWZITILNLYSWAHOSWOG‘80=NOLLYZITILLALYAWSHOSWOG
`
`
`
`S3CON3H09SHILVNOIVUNGS300N3YO9SHLVNOILWYNG
`JW3HOSWOHLIMJWSHOSWO”HLIM
`-wam00SL
`Ccm50002<
`
`
`o00¢
`
`00SZ
`
`0001
`
`00S
`
`AONSNDaAYs
`
`SplunkInc.
`
`Exhibit1014
`
`Page 17
`
`Splunk Inc. Exhibit 1014 Page 17
`
`

`

`
`U.S. Patent
`
`
`
`
`Jan. 4, 2005
`
`
`
`
`Sheet 16 of 16
`
`
`
`US 6,839,321 B1
`
`
`
`
`
`
`
`Packetloss%atcorenodes
`
`..
`
`[ass% w
`Total(core+TBF)packet
`
`
`
`utilization 0.5
`utilization O.$—-
`
`
`
`
`suiation 0.6
`ublizateca 0.6
`
`
`
`uilizalion 0.7 -
`utilization 0.7 -
`
`
`
`
`utilization 0.6
`utilization 0.6
`
`
`
`
`dehaaton 03
`uta ain 0
`
`
`
`
`
`utilization 1.1. -+--
`utilization 1.1
`utilization 1.213
`
`
`uidization 4
`utilization 1.2
`uulization
`
`
`
`oe
`"
`cg cere times
`
`
`
`
`
`
`
`
`
`40
`
`
`
`50
`
`
`
`60
`7O
`
`
`
`domain-RTT (ms)
`
`
`
`80
`
`
`
`90
`
`
`
`100
`
`
`
`
`
`
`
`
`
`
`
`domain-RTT (ms}
`
`
`
`
`
`
`
`
`
`
`
`
`
`(a) packet loss % at core nodes;
`
`
`
`
`
`
`
`
`
`
`(b) Total packet loss in the system (core +TBF)
`
`Fig. 15
`
`
`
`PERFORMANCE OF THE DCM SCHEME WITH DOMAIN-RTT VARIATION
`
`
`
`
`
`
`
`
`
`Splunk Inc.
`
`Exhibit1014
`
`Page 18
`
`Splunk Inc. Exhibit 1014 Page 18
`
`

`

`
`
`US 6,839,321 B1
`
`
`
`
`1
`
`
`DOMAIN BASED CONGESTION
`
`MANAGEMENT
`
`
`
`FIELD OF INVENTION
`
`
`
`
`
`
`
`
`This invention is related to the field of congestion man-
`
`
`
`
`
`
`
`agement schemesfor controlling the flow of packets over the
`Internet.
`
`
`
`
`
`BACKGROUND OF INVENTION
`
`
`
`
`
`
`
`
`
`Potential congestion periods can occur for a number of
`
`
`
`
`
`
`
`
`possible reasons such as i) burstiness that is inherent in
`
`
`
`
`
`
`
`nodes and generated due tostatistical multiplexing at nodes
`
`
`
`
`
`
`
`along a given path; and ii) non-adaptive greedy applications
`
`
`
`
`
`
`
`
`that may often cause (potential) congestion periods leading
`
`
`
`
`
`
`
`
`
`to severe packet loss conditions which affect other sessions
`
`
`
`
`
`
`
`that share network resources. Congestion avoidance and
`
`
`
`
`
`
`management schemesare essentialfor a better utilization of
`network resources.
`
`
`
`
`
`
`
`
`
`Generally, congestion control schemes have two phases
`
`
`
`
`
`
`
`viz. i) early congestion detection and avoidance; and ii) a
`
`
`
`
`
`
`
`congestion management schemethat begins to operate once
`
`
`
`
`
`
`
`a congestion period occurs. Several congestion management
`
`
`
`
`
`
`
`
`schemes have been proposed so far. For example, binary
`
`
`
`
`
`
`feedback-based congestion management schemes rely on
`
`
`
`
`
`
`
`end sources to react to the congestion messages. Similarly,
`
`
`
`
`
`
`
`the current Internet relies on end-to-end congestion control
`
`
`
`
`
`
`
`mechanismsthrough either packet dropping or explicit con-
`
`
`
`
`
`
`gestion notification (ECN) by marking packets of a session.
`
`
`
`
`
`
`However, the end-to-end reaction to congestionis critically
`
`
`
`
`
`
`
`
`
`dependent on roundtrip time (RTT) between the end hosts.
`
`
`
`
`
`
`
`Explicit rate management algorithms have also been
`
`
`
`
`
`
`
`
`proposed in the context of ATM. However, the explicit rate
`notification schemes that indicate the rates to which the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`individualtraffic sources have to adapt are too complex to be
`
`
`
`
`
`
`
`implemented and require extensive processing at the core
`
`
`
`
`
`
`
`
`switches (or routers). They also need to generate periodic
`
`
`
`
`
`
`
`
`resource management (RM) cells that cause extra traffic.
`
`
`
`
`
`
`Furthermore, these schemes, in particular, require per-flow
`
`
`
`
`
`
`
`
`state maintenance that cannot be tailored easily to suit the
`
`
`heterogeneous Internet.
`
`
`
`
`
`
`
`
`Corestate-less fair queuing (CSFQ) has been proposed in
`
`
`
`
`
`
`
`
`order to eliminate the book keepingof each flow state at core
`
`
`
`
`
`
`
`routers. However, the key focus of CSFQis on achieving fair
`
`
`
`
`
`
`
`bandwidth allocation. It relies on end hosts(traffic sources)
`
`
`
`
`
`
`
`to detect available bandwidth or congestion at the bottleneck
`
`
`
`
`
`
`
`
`
`
`nodes. The long round trip time between a given pair of
`
`
`
`
`
`
`
`
`
`source and destination nodes canlead to late reaction by the
`
`
`
`
`
`
`
`sources to the congestion notification. As a result, CSFQ
`
`
`
`
`
`may not be adequate in reducing packet loss.
`
`
`
`
`
`
`
`Differentiated services (Diff-serv) over the Internet Pro-
`
`
`
`
`
`
`
`
`tocol (IP) have been proposed to avoid maintaining state
`
`
`
`
`
`
`
`information of large numberof flows at the core routers. In
`
`
`
`
`
`
`addition, Diff-serv moves the complexity of per-flow band-
`
`
`
`
`
`
`width managementto intelligent edge routers. A Diff-serv
`
`
`
`
`
`
`
`cloud comprises i) a set of edge nodes knownas ingress or
`
`
`
`
`
`
`
`
`egress nodes dependingon thetraffic flow direction that may
`
`
`
`
`
`
`
`
`
`maintain per-flow state andii) a set of core nodesthat do not
`
`
`
`
`
`
`
`
`maintain per-flow state information and carry a large number
`
`
`
`
`
`
`of aggregated flows (see FIG. 1).
`Overview of Diff-serv architecture
`
`
`
`
`
`
`
`
`
`
`The crux of Differentiated Services (DS)is that packets
`
`
`
`
`
`
`
`
`
`
`get different levels of service based on Type of Service
`
`
`
`
`
`
`
`
`(TOS)bits. These include i) traffic policing that leads to
`
`
`
`
`
`
`
`
`marking of the packets that are out of profile (violation of
`
`
`
`
`
`
`
`
`some traffic parameter as specified, e.g., peak-rate);
`ii)
`
`10
`
`
`
`20
`
`25
`
`
`
`30
`
`35
`
`
`
`40
`
`
`
`45
`
`
`
`50
`
`
`
`55
`
`
`
`60
`
`
`
`65
`
`
`
`
`2
`
`
`
`
`
`
`
`packet dropping and buffering strategies at various routers,
`
`
`
`
`
`
`also knownas Per-Hop-Behaviors (PHBs); andiii) choice of
`
`
`
`
`
`
`
`
`
`
`an appropriate queue that maps to the type of service that
`
`
`
`
`
`
`
`was chosen by the application as indicated by the TOSbits.
`
`
`
`
`
`
`The flow or flow-aggregate information is maintained only
`
`
`
`
`
`
`
`
`
`at a few selected routers, such as edge routers. Thus,
`
`
`
`
`
`per-low/aggregate monitoring is avoided at core routers.
`
`
`
`
`
`
`
`
`The PHBsthat run on core routers can be adaptively tuned
`
`
`
`
`
`
`
`
`
`to compensate for the loose admission control at the edges
`
`
`
`
`
`
`
`
`wheretraffic of various classes are injected in to the network
`
`
`
`
`
`
`
`with a goal of predictable QoS. However, best-effort service
`still constitutes a considerable amount of net traffic. The
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`allocation of the bandwidth available for best effort depends
`
`
`
`
`
`
`
`on the policy of individual Internet Service Providers (ISPs)
`
`
`
`
`
`
`
`
`and the service level agreements with other neighboring DS
`domains.
`
`
`
`
`
`
`
`
`
`Currently there are two classes of services defined in the
`
`
`
`
`
`
`
`
`context of Diff-serv viz.: i) the Assured service (AS) andii)
`
`
`
`
`
`
`
`
`Premium service (PS). They are respectively mapped onto
`
`
`
`
`
`
`
`Assured forwarding (AF) and Expedited forwarding (EF)
`
`
`
`
`
`
`per-hop-behaviors (PHBs). The AF PHB forwards packets
`
`
`
`
`
`
`
`according to their priorities. Thus,
`in the event of
`
`
`
`
`
`
`
`
`congestion, high priority packets receive better service than
`
`
`
`
`
`
`
`
`
`low priority packets. The EF PHB aims at reducing the
`
`
`
`
`
`
`
`
`
`queuing delays and emulates a leased line service from the
`
`
`
`end user’s perspective.
`
`
`
`
`Nevertheless, congestion management schemesare essen-
`
`
`
`
`
`
`
`tial for good network utilization, even with priority-based
`
`
`
`
`
`
`packet handling schemes. Potential congestion periods can
`arise and it is difficult to assess the available bandwidth
`
`
`
`
`
`
`
`
`unless the core routers are enhanced with robust resource
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`management schemes. Thus, each of the ingress nodes
`
`
`
`
`
`
`
`(unaware of an onset congestion period) can potentially
`
`
`
`
`
`
`
`inject more traffic into the core network of a Diff-serv
`
`
`
`
`
`
`
`domain. ECN has been proposed, however,
`the ECN
`
`
`
`
`
`
`requires end-hosts to interact and respond to the congestion
`notification.
`
`Red
`
`
`
`
`
`
`
`Active queue management algorithms, such as Random
`
`
`
`
`
`
`
`Early Detection (RED), can be employed in order to detect
`
`
`
`
`
`
`
`
`and avoid any potential network collapse due to congestion.
`
`
`
`
`
`
`Congestion detection can be based on buffer monitoring by
`
`
`
`
`
`
`
`setting a threshold value for buffer occupancy. However,
`
`
`
`
`
`
`
`simple buffer occupancy-based techniques may notbe suf-
`
`
`
`
`
`
`
`
`
`ficient to handle bursty traffic because bursty traffic may
`
`
`
`
`
`
`
`
`temporarily lead to a buffer occupancy greater than the
`
`
`
`
`
`
`
`threshold value. This leads to frequent congestion
`
`
`
`
`avoidance/management triggering mechanisms. In contrast
`
`
`
`
`
`
`
`
`to simple buffer monitoring, the RED algorithm calculates
`
`
`
`
`
`
`
`
`
`
`an average queue size by using a low-pass filter with an
`
`
`
`
`
`
`exponential weighted moving average (EWMA). With a
`
`
`
`
`
`
`
`
`
`constant wq (O<wq<1), with the arrival of nth packet, the
`
`
`
`
`
`average queue size is given as follows
`
`
`avgQsize,=(1-w,).avgQsize,, -+w,.currentQsize,,
`
`
`
`
`
`
`
`
`The allowed range of the average queue size before
`
`
`
`
`
`
`
`packets are dropped determines the allowed burst sizes.
`
`
`
`
`
`
`Thus RED can accommodatetraffic bursts unlike drop-tail
`
`
`
`
`
`
`
`FIFO-based queue thresholds, as the average queue size
`
`
`
`
`
`
`
`
`does not solely depend on the current queuesize.
`
`
`
`
`
`
`
`
`RED employs two queue thresholds,
`ie., minth and
`
`
`
`
`
`
`
`maxth. Whenever the average queue is between the minth
`
`
`
`
`
`
`
`
`
`threshold value and the maxth threshold, the RED algorithm
`
`
`
`
`
`
`
`
`drops (or marks) packets randomly with certain probability
`
`
`
`
`
`
`P4,op indicating an incipient congestion.If the average queue
`
`
`
`
`
`
`
`
`
`
`size exceeds the maxth, it drops all the packets until the
`
`
`
`
`
`
`
`
`
`average queue size falls below the maxth threshold. The
`SplunkInc.
`Exhibit1014
`Page 19
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`@)
`
`
`
`
`
`
`
`Splunk Inc. Exhibit 1014 Page 19
`
`

`

`
`3
`
`
`
`
`
`probability of dropping is a function of average queue size
`
`
`and is given by
`
`
`
`
`
`US 6,839,321 B1
`
`
`
`
`4
`
`
`
`
`FIG. 9 depicts a simulation setup.
`
`
`
`
`
`
`
`FIG. 10 showsthe performance of the DCM method vs.
`
`
`
`
`non-feedback based congestion control.
`
`
`
`
`
`
`
`
`
`
`
`
`
`(2)
`Pp,
`=P
`(avgOsize — minth)
`
`
`FIG. 11 illustrates the delay performance of the DCM
`
`
`
`crop ~©me’ axth—minth)
`method.
`
`
`
`
`
`
`
`
`
`FIGS. 12(a@) and 12(b) depicts a sample average queue
`
`
`
`
`
`
`
`size and the distribution of packet weightat an ingress Token
`Bucket Filter for a utilization factor of 0.8.
`
`
`
`
`
`
`
`
`
`
`
`
`
`FIGS. 13(a) and 13(5)illustrate the distribution of con-
`
`
`
`
`
`
`
`
`gestion periods for a non-DCM method at the core node.
`
`
`
`
`
`
`
`
`FIGS. 14(a@) and 14(6) illustrate the drop phase duration
`for the DCM method for the utilization factors 0.8 and 0.9
`
`
`
`
`
`
`
`
`
`
`
`respectively.
`
`
`
`
`
`
`FIG. 15 illustrates the performance of the DCM method
`with domain-RTTvariation.
`
`
`
`
`
`
`
`
`
`
`
`whereP,,,. 1s the maximum probability of a packet drop. It
`
`
`
`
`
`
`
`
`
`is shown that
`the average queue size is substantially
`
`
`
`
`
`
`
`
`decreased with random packet dropping. This mitigates the
`
`
`
`
`
`
`tail-dropping effects and the associated synchronization of
`
`
`
`
`
`
`
`various TCP (application) back-offs (reduction in traffic
`
`
`transmissionrate).
`SUMMARYOF THE INVENTION
`
`
`
`
`
`
`
`
`
`
`The present invention is a method and apparatusthat uses
`
`
`
`
`
`thresholds for regulating congestion.
`It deterministically
`
`
`
`
`
`
`
`marks outgoing packets by setting a LCN bit(s) when an
`
`
`
`
`
`
`
`
`
`average queue size of a token bucket filter is between a
`
`
`
`
`
`
`minimum threshold and a feedback threshold. In addition,it
`
`
`
`
`
`
`
`probabilistically drops incoming packets and marksall out-
`
`
`
`
`
`
`
`
`going packets when the average queue size is between a
`
`
`
`
`
`
`
`feedback threshold and a maximum threshold. Finally, all
`
`
`
`
`
`
`
`
`incoming packets are dropped when the average queue size
`
`
`
`
`
`equals or exceeds said maximum threshold.
`
`
`
`
`
`
`
`In another preferred embodiment, the present invention is
`
`
`
`
`
`
`
`
`an apparatus and method for regulating traffic flow in a
`differentiated services network between nodes. First a core
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`node detects congestion. Next, and egress node sends a
`
`
`
`
`
`
`
`congestion feedback notification message to at least one
`
`
`
`
`
`
`
`
`ingress node. In response, the ingress node reducesits traffic
`
`
`
`
`
`
`
`
`rate in proportion to the amountoftraffic that it was injecting
`
`
`
`
`
`
`
`into the network when congestion was detected.
`
`
`
`
`
`
`
`
`In still another preferred embodiment, the present inven-
`
`
`
`
`
`
`
`
`tion comprises a method and apparatus for regulating the
`
`
`
`
`
`
`
`
`
`traffic rate at an ingress node by varying the number of
`
`
`
`
`
`
`
`
`tokens consumed by a data packet and transmitting the data
`
`
`
`
`
`
`
`packet if the number of tokens consumed by the packet is
`less than the available tokens.
`
`
`
`
`
`
`
`
`
`
`
`
`
`In still another preferred embodiment, the present inven-
`
`
`
`
`
`
`
`
`tion is an apparatus for controlling traffic flow in a differ-
`
`
`
`
`
`
`
`entiated services domain. It is comprised of a plurality of
`
`
`
`
`
`
`
`
`
`three types of nodes,
`ingress, egress and core nodes.
`
`
`
`
`
`
`
`Furthermore, each ingress node has a corresponding token
`
`
`
`
`
`
`
`
`
`bucket filter which is used to regulate the flow of data
`
`
`
`
`
`
`
`
`packets. The token bucket filter is comprised of a token
`
`
`
`
`
`
`
`
`generator and a bucketto hold at least one generated token.
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`
`
`
`FIG. 1 contains the architecture of a Diff-serv domain.
`
`
`
`
`
`
`
`
`
`
`FIG. 2 illustrates the improvRED method.
`
`
`
`
`
`
`FIG. 3 illustrates a simple 2-bit scheme used to indicate
`
`
`
`
`
`
`
`the onset of a congestion period at the core nodes.
`
`
`
`
`
`FIG. 4 is the definition of DSCP byte.
`
`
`
`
`
`
`
`FIG. 5(a) illustrates a token bucket filter connected to a
`Diff-serv domain.
`
`
`
`
`
`
`
`
`
`FIG. 5(5) illustrates the components of a token bucket
`filter.
`
`
`
`
`
`
`
`
`FIG. 6(a)is a flowchart for the Token Bucket Filter-based
`rate control method.
`
`
`
`
`
`
`
`
`
`FIG. 6(b) illustrates a Token Bucket Filter-based conges-
`
`
`
`
`
`
`
`tion management method used with ingress nodes.
`
`
`
`
`
`
`
`FIG. 7 illustrates the varying of packet weight with
`
`
`
`
`demand and LCN messages.
`
`
`
`
`
`
`FIG. 8 depicts a possible discrete state implementation of
`
`
`
`the algorithm in FIG. 7.
`
`10
`
`15
`
`
`
`
`
`
`
`
`
`
`
`
`20
`
`25
`
`
`
`30
`
`35
`
`
`
`40
`
`
`
`45
`
`
`
`50
`
`
`
`55
`
`
`
`60
`
`
`
`65
`
`
`
`
`
`DETAILED DESCRIPTION OF THE
`
`
`INVENTION
`
`
`
`
`
`
`invention is a feedback-based congestion
`The present
`control for a Diff-serv domain called Domain-based Con-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`gestion Management (DCM). One improvementit has over
`
`
`
`
`
`
`
`existing congestion control schemes is the advantage of
`
`
`
`
`
`
`
`shorter RTTs between a given pair of ingress/egress nodes of
`
`
`
`
`
`
`
`
`a Diff-serv domain. This is in contrast to the long end-to-end
`
`
`
`
`
`
`
`RTTs of existing congestion control schemesthat invariably
`
`
`
`
`
`
`
`
`
`result in large latency of reaction to transient congestion
`
`
`
`
`
`
`
`
`periods. In addition, the present invention is not complex
`
`
`
`
`
`
`
`
`and requires no flow state maintenance at the core routers.
`
`
`
`
`
`
`
`Therefore, it can react quickly to transient congestion peri-
`
`
`
`
`
`
`
`
`ods that occur locally within a Diff-serv cloud. Furthermore,
`
`
`
`
`
`
`
`shorter RTTs between a given pair of ingress/egress nodes
`can lead to faster detection and better utilization of the
`
`
`
`
`
`
`
`
`
`
`transient available bandwidth in the core Diff-serv domain.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`The present invention improves upon the Random Early
`
`
`
`
`
`
`Detection (RED) and explicit congestion notification
`mechanisms to handle best-effort traffic. The DCM scheme
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`is based on an improvement
`to the RED scheme
`
`
`
`
`
`
`(improvRED)of low complexity running on the core routers
`
`
`
`
`
`
`
`and an adaptive Token Bucket Filter (TBF)-based traffic
`
`
`
`
`
`
`
`regulation at the ingress nodes. It is a method and apparatus
`
`
`
`
`
`
`
`
`
`
`that allows all
`the ingress nodes (I) to share available
`
`
`
`
`
`
`
`
`
`bandwidth and adjusttheir rates of traffic injection such that
`
`
`
`
`
`
`
`
`
`the average congestion periods are reduced inside the Diff-
`
`
`
`
`
`
`
`
`serv domain. This leads to an overall
`improvement
`in
`utilization.
`
`
`
`
`
`
`
`The DCM scheme is a distributed congestion control
`
`
`
`
`
`
`
`algorithm that runs on each of the ingress nodes. On the one
`
`
`
`
`
`
`
`
`
`hand,it helps the ingress nodes to avoid packet loss during
`
`
`
`
`
`
`
`
`congestion periods and, on the other hand, detects available
`
`
`
`
`
`
`
`bandwidth during congestion-free periods. In addition, the
`
`
`
`
`
`
`RED mechanism is improved to distinguish between an
`
`
`
`
`
`
`
`onset of a likely congestion period (marking phase) and a
`
`
`
`
`
`
`
`persistent congestion period that invariably incurs packet
`
`
`
`drops (dropping phase).
`
`
`
`
`
`
`Feedback,in the form of a Local Congestion Notification
`
`
`
`
`
`
`
`
`(LCN) message (or message), is used to notify the ingress
`