Case 6:20-cv-00890-ADA Document 1-1 Filed 09/29/20 Page 1 of 29
`Case 6:20-cv-00890-ADA Document 1-1 Filed 09/29/20 Page 1 of 29
`
`
`
`EXHIBIT A
`
`EXHIBIT A
`
`

`

`(12) United States Patent
`Chiruvolu
`
`USOO6839321B1
`(10) Patent No.:
`US 6,839,321 B1
`(45) Date of Patent:
`Jan. 4, 2005
`
`(54) DOMAIN BASED CONGESTION
`MANAGEMENT
`(75) Inventor: Girish Vsr Chiruvolu, Richardson, TX
`(US)
`
`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.
`(73) Assignee: Alcatel, Paris (FR)
`Supporting Differentiated Services Using ATM ABR Ser
`vice; Richard Rabbat, et al., pp. 210-213.
`(*) Notice:
`Subject to any disclaimer, the term of this
`Service Differentiation Through End-to End Rate Control in
`p isst i.s listed under 35
`Low Bandwidth Wireless Packet Networks; Thyagarajan
`a --
`(b) by
`ayS.
`Nandagopal, et al., pp. 211-220.
`(21) Appl. No.: 09/618,196
`A Simple Packet Scheduling and Buffer Management
`1-1.
`Scheme for Scalable Support of QoS in the Internet; KJ Loh,
`(22) Filed:
`Jul. 18, 2000
`et al., pp. 276-281.
`(51) Int. Cl." ................................................ H04L 12/26
`S. For s- - - - - - - -h - - - - - - - 370/230.1; 370/7.2. Randomized Token Buckets: Reducing the Buffers Required
`e O SeaC. .................................
`s
`Multipl
`J. Andrew F
`hut, et al., IEEE 1997, pp.
`370/400, 401, 410, 412–416, 352-354; tly eXOrS,
`reW Fingernul, et al.,
`, pp
`710/52-57
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`4f1988 Aubin et al.
`4,736,363 A
`2/1990 Soloway et al.
`4,901.277 A
`5,088,032 A
`2/1992 Bosack
`(List continued on next page.)
`FOREIGN PATENT DOCUMENTS
`
`DE
`EP
`WO
`
`43 16 872 A1 11/1994
`O SO3 469 A2
`9/1992
`WO OO/41365
`7/2000
`
`OTHER PUBLICATIONS
`F.M. Anjum et al. Fair Bandwidth Sharing Among Adaptive
`and Non-Adaptive Flows in the Internet, Proceedings IEEE
`Infocom 1999. The Conference on Computer Communica
`tions, 18" Annual Joint Conference of the IEEE Computer
`and Communications Societies, New York, New York, Mar.
`21-25, 1999, Proceedings IEEE Infocom, The Computer
`Communica, vol. 3, Mar. 12, 1999, pp. 1412-1420.
`W-J Kim et al., The FB-Red Algorithm for TCP over ATM,
`IEEE Globecom 1998, Globecom 1998, The Bridge to
`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.
`
`Primary Examiner Douglas Olms
`Assistant Examiner Van Kim T. Nguyen
`(74) Attorney, Agent, or Firm Sughrue, Mion, PLLC;
`Jessica W. Smith; V. Lawrence Sewell
`(57)
`ABSTRACT
`
`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
`tion at the core routers and token bucket filters for traffic
`regulation at the ingreSS nodes. In addition, improvRED also
`provides feedback control. ImprovRED uses three thresh
`olds for detecting congestion: a minth, a maxth and a
`FeedbackThreshold, which lakes a value between the minth
`and the maxth thresholds. Whenever the average queue Size
`is greater than minth and less than Feedback-Threshold, all
`outgoing packets are marked appropriately to indicate a
`potential onset of a congestion period. When the average
`queue Size is greater th FeedbackThreshold (but less than
`maxth) packets are dropped probabilistically and all the
`outgoing packets are marked appropriately to denote the
`dropping phase. When the average queue size is greater than
`the maximum threshold, all incoming packets are dropped.
`
`42 Claims, 16 Drawing Sheets
`
`Case 6:20-cv-00890-ADA Document 1-1 Filed 09/29/20 Page 2 of 29
`
`100
`
`----ROUNDRIFESTMATON
`BEEENAGENPAROF
`INGRESSANDEGRESSNODES,
`
`THEOAL
`CONGESTONNOTIFICATION
`OCCURSERE
`
`THELOCA
`CONGESTIONCLEARANCE
`NOTIFICATIONOCCURSHERE
`
`THRESHOLWALUE
`OFAWOUEUESIZE
`
`
`
`WARYING OFPKTWTWTHDEMAND ANDLCNMESSAGES
`
`

`

`US 6,839,321 B1
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`3/1993 Kramer et al.
`5.191,650 A
`2: A 3.E. this
`2- .
`.
`.
`f
`an et al.
`5,404.565 A 4/1995 Gould et al.
`5,408,562 A 4/1995 Yoshizawa et al.
`5,426,674. A 6/1995 Nemirovsky et al.
`5430,729 A 7/1995 Rahnema
`552,972 A 5/1996 Iki
`5596.722 A 1/1997 Rahnema
`5.644.713 A 7/1997 Makishima
`57.19853 A 2/1998 Ikeda
`2
`a - 2
`5,870,564 A 2/1999 Jensen et al.
`5881.241 A 3/1999 Corbin
`2Y-a-a-2
`5,884,043 A 3/1999 Teplitsky
`:
`5,914,936 A 6/1999 Hatono et al. .............. 370/230
`5,918,017 A 6/1999 Attanasio et al.
`5.996,021 A 11/1999 Civanlar et al.
`6,147,970 A 11/2000 Troxel ........................ 370/235
`
`6/2001 Skirmont .................... 370/229
`6,252,848 B1
`6,333,917 B1 * 12/2001 Lyon et al. ................. 370/412
`6,404,735 B1 * 6/2002 Beshai et al. ............... 370/230
`6,424,624 B1
`7/2002 Galand et al. .............. 370/231
`6,487,170 B1 * 11/2002 Chen et al. ................. 370/231
`6,510,160 B1
`1/2003 Nikuie et al. ...
`... 370/412
`2- - - 2
`6535,482 B1
`3/2003 Hadi Salim et al. ........ 370/229
`2- - - 2
`:
`6,556.578 B1
`4/2003 Silberschatz et al. ....... 370/412
`6,614,756 B1 * 9/2003 Morgenstern et al. ...... 370/230
`6,618,378 B1 * 9/2003 Giroux et al. ........... 370/395.1
`6,643,260 B1
`11/2003 Kloth et al. ................ 370/235
`6,646,988 B1 * 11/2003 Nandy et al.
`370/235
`6,657,962 B1 * 12/2003 Barri et al.
`370/235
`Y/ -
`:
`6,675.220 B1
`1/2004 McCloghrie et al. ....... 709/232
`6,680,906 B1 * 1/2004 Nguyen .........
`370/229
`6,680,907 B1 * 1/2004 Bonaventure
`370/229
`6,690,645 B1 * 2/2004 A
`tal
`370/230
`Y/ -- Y-2
`Weya et al. . . . . . . . . . . . . . . .
`
`
`
`* cited by examiner
`
`Case 6:20-cv-00890-ADA Document 1-1 Filed 09/29/20 Page 3 of 29
`
`

`

`U.S. Patent
`
`Jan. 4, 2005
`
`Sheet 1 of 16
`
`US 6,839,321 B1
`
`- Ds Dorain core
`Network
`
`- \
`
`Neighboring
`DS Dorain
`
`
`
`
`
`lost 1
`
`Fig. 1
`DFF-SERV DOMAIN
`(PRIOR ART)
`
`Case 6:20-cv-00890-ADA Document 1-1 Filed 09/29/20 Page 4 of 29
`
`

`

`U.S. Patent
`
`US 6,839,321 B1
`
`
`
`
`
`
`
`SEGON BHOO I'W WHL||800TW GEN BHIOL SNOIIVOIHIGOW
`
`
`
`
`
`
`
`Case 6:20-cv-00890-ADA Document 1-1 Filed 09/29/20 Page 5 of 29
`
`

`

`U.S. Patent
`
`Jan. 4, 2005
`
`Sheet 3 of 16
`
`US 6,839,321 B1
`
`
`
`
`
`
`
`NOILSB0NOO NIWWOG TWOOT ONLINESEHdB}} }}OH BWEHOS 118-ONAL BTdWISW
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Case 6:20-cv-00890-ADA Document 1-1 Filed 09/29/20 Page 6 of 29
`
`T?ETIGI
`
`

`

`U.S. Patent
`
`Jan. 4, 2005
`
`Sheet 4 of 16
`
`US 6,839,321 B1
`
`| 18 NOT
`
`
`
`BLÅ8 d'OSC]]SOL EH1
`
`
`
`
`
`Case 6:20-cv-00890-ADA Document 1-1 Filed 09/29/20 Page 7 of 29
`
`

`

`U.S. Patent
`
`Jan. 4, 2005
`
`Sheet 5 of 16
`
`US 6,839,321 B1
`
`
`
`TOKEN BUCKETFILTER CONNECTED TO OFFF-SERVDOMAIN
`FIG. 5A
`
`TBF
`
`g j
`
`R
`
`Case 6:20-cv-00890-ADA Document 1-1 Filed 09/29/20 Page 8 of 29
`
`COMPONENTS OF ATOKEN BUCKETFILTER
`FIG. 5B
`
`

`

`U.S. Patent
`
`Jan. 4, 2005
`
`Sheet 6 of 16
`
`US 6,839,321 B1
`
`DATAPACKET
`
`200
`
`WARY THE NUMBER OFTOKENS
`CONSUMED BYDATAOF UNIT SIZE,
`PktW), BASED ON DEMAND AND
`STATE,
`
`
`
`
`
`
`
`
`
`
`
`
`
`IS
`Pkt size:PktW. C
`AVAILABLE TOKENSIN BUCKET,
`N BUCKET
`
`
`
`
`
`
`
`
`
`
`
`DONT TRANSMT
`PACKET
`
`
`
`
`
`TRANSMIT PACKET
`
`Case 6:20-cv-00890-ADA Document 1-1 Filed 09/29/20 Page 9 of 29
`
`FLOWCHART FORTBF-BASED RATE CONTROL METHOD
`FIG.6A
`
`

`

`U.S. Patent
`
`Jan. 4, 2005
`
`Sheet 7 of 16
`
`US 6,839,321 B1
`
`
`
`PktWt:-1.0
`Initialize;
`PktWt is always within (minPkt Wt, maxPktWt
`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)
`PktWt-PktWt.
`MD (PktWt)-1230
`/* decrease the PktWt during congestion free periods, based on demand
`at TBF it?
`else {
`> 1) PktWt:--- max{1, PktWt: * MD(PktWt.) )
`if (PktWt
`( 1) PktWt -- min (1, PktWt, MI (PktWt)}}
`if (PktWt
`/* restore PktWt close to 1.0 */
`
`Y
`
`.
`if Pkt Wt. < 1.
`
`At congestion notification time
`(max.PktWt - 1) (1 - PktWt, , )
`Pktwit -- T - Till + 1
`(1 - minPktWt)
`f* The smaller the PktWt just before LCN, the bigger it will be during
`congestion period. A uniform mapping of minPktWt, 1) on to
`(l, maxPktWt) intervals */-1250
`During congestion period
`PktWt-PktWt: * MI (PktWt: ) if PktWt. # 1-1240
`On receipt of congestion clearance notification
`
`Case 6:20-cv-00890-ADA Document 1-1 Filed 09/29/20 Page 10 of 29
`
`Select a random time less than RTT and
`PktWt-PktWt: * MD (Pkt Wt:
`) --1220
`
`THE TBF-BASED CONGESTION MANAGEMENTALGORITHMAT INGRESS NODES
`FIG.6B
`
`

`

`Case 6:20-cv-00890-ADA Document 1-1 Filed 09/29/20 Page 11 of 29
`e
`s
`
`mP.
`
`S.U
`
`a
`
`O.t.203m52naw
`
`lB
`
`l.mnNo:
`
`
`
`zozwmozoomwfizmmflwwymfizflmazmm0.mmmx95802952252n
`
`Soxmmmxbmm...................................................................m...............wwHmmmmm.mmmMmnWW._HM.......................................m.......................J
`10.”wmo<mwm§20..oz<oz<2moI._._>>EICEu_OOz_>~_<>Wl00We6,19:wSmumwage950m:PUm3<>
`8U.........n.....no>1t____1.wmUmum%.m_mmwwmA.--.....%---mmm0FX.DMEu0.MHADM29./Bn4.Anmm“:288m.”n03h20:51:02
`
`
`
`
`

`

`U.S. Patent
`
`Jan. 4, 2005
`
`Sheet 9 of 16
`
`US 6,839,321 B1
`
`
`
`Case 6:20-cv-00890-ADA Document 1-1 Filed 09/29/20 Page 12 of 29
`
`

`

`U.S. Patent
`
`Jan. 4, 2005
`
`Sheet 10 of 16
`
`US 6,839,321 B1
`
`
`
`sd
`
`ZEQW Z
`
`Case 6:20-cv-00890-ADA Document 1-1 Filed 09/29/20 Page 13 of 29
`
`SdqW Z
`
`381
`
`

`

`Case 6:20-cv-00890-ADA Document 1-1 Filed 09/29/20 Page 14 of 29
`Case 6:20-cv-00890-ADA Document 1-1 Filed 09/29/20 Page 14 of 29
`
`US. Patent
`
`M024,
`
`whS
`
`0
`
`US 6,839,321 B1
`
`uE:
`m53
`FJ33ca2_Se2958mmmagmaEmemmoo
`vagaw202
`
`53
`
`8mm:
`
`832
`
`Nummd
`
`38K
`
`among
`
`82..3
`
`83$
`
`2‘GE
`
`mzmxom200ommOmommm1...“.0moz<2m0mmmm
`
`mmmmozE
`#50E
`
`$2.
`
`882
`
`mmoop<
`
`8$82
`
`
`
`
`
`Eon2:3Hzm2m>omm§._._<mw>owmg._._<mm>o
`
`msmxom28
`
`
`
`$0..55%tos.
`
`wsmzom
`
`£35<0.909am
`
`

`

`U.S. Patent
`
`Jan. 4, 2005
`
`Sheet 12 of 16
`
`US 6,839,321 B1
`
`186 || 1/’0
`
`Z69817' ],
`
`069699' ],
`
`
`
`S38|| SSE-JONI LW (SQN00BS) MWIEG EÐVAJBAW | NOLIWZITIIN
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Case 6:20-cv-00890-ADA Document 1-1 Filed 09/29/20 Page 15 of 29
`
`

`

`U.S. Patent
`
`US 6,839,321 B1
`
`Case 6:20-cv-00890-ADA Document 1-1 Filed 09/29/20 Page 16 of 29
`
`

`

`Case 6:20-cv-00890-ADA Document 1-1 Filed 09/29/20 Page 17 of 29
`Case 6:20-cv-00890-ADA Document 1-1 Filed 09/29/20 Page 17 of 29
`
`US. Patent
`
`61
`
`US 6,839,321 B1
`
`
`.o:o3
`..omwcom
`
`2:8v
`
`
`m$892958mg:8%68929585%:nameHmmam:emo88e.on8.2oe.....
`
`
`
`...........m...._om"w...on
`
`
`
` .”w.a?m8m8NH,8m....H..H_.SNm02mwanJ8—A8m
`
`AONBHOEHd
`
`
`
`
`
`m5nzo_H<N:_.5._.<mimzow200-202
`
`
`
`
`
`uwdnzo_._.<N_._F3._.<mEmIOm200-202
`
`
`
`
`
`mm<Immomm—._.mx0<n_nozo_._.:m_m._.w_o
`
`
`
`mm<zmmomo520$.m0zo_.5m_mhm_o
`
`$502#60mi2zoEaso$82#50ME220.218
`msmxom28-2022:;95:828-202It;
`
`
`
`
`mm;.OI<9.O_n_
`
`

`

`Case 6:20-cv-00890-ADA Document 1-1 Filed 09/29/20 Page 18 of 29
`Case 6:20-cv-00890-ADA Document 1-1 Filed 09/29/20 Page 18 of 29
`
`US. Patent
`
`Jan. 4, 2005
`
`Sheet 15 0f 16
`
`US 6,839,321 B1
`
`m.¢
`
`
`
`
`
`aowg20.5.8mm<E“.95”28v3.m3NSF
`
`
`
`mdnzOF<N._.E:2£51an.200
`
`
`
`
`
`mw<xmmomoEva/EmozQSmEhwE
`
`$002$50$2..2zo_._.<m:o
`
`mEmIOm200I._._>>
`
`m3.OE
`
`AONEHDEHJ
`
`md
`
`m4.
`
` <3.OE
`“6%”28e3m2N2e3
`
`mm<ImmomoExo/EmozO_._.:m_me_o
`$520.58mg:
`
`uwduzo_._.<N_.__.S._.<mzmxom560
`meOzmmooME.H<20.2130
`
`méwrom2001.55
`
`OO‘
`
`—
`
`AONSHOEEH
`
`
`

`

`U.S. Patent
`
`Jan. 4, 2005
`
`Sheet 16 of 16
`
`US 6,839,321 B1
`
`
`
`utilization 0.5
`Ltilizatch 0.8
`utilization 0.7 -
`utilization 0.8
`futi: .:
`utilization 1.
`utilization
`utilization
`
`: ?tilization
`
`.
`
`.
`
`utilization 0.5
`uttan.6
`filiation 0.7 .
`utilization 0.6
`Jizai: .
`utilization 1.1 ...o.
`J2ation 2
`
`30
`
`40
`
`SO
`
`70
`60
`domain-RTT (mis)
`
`80
`
`90
`
`100
`
`30
`
`40
`
`50
`
`70 -
`60
`domain-R(ms)
`
`80
`
`90
`
`100
`
`(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 WARIATION
`
`Case 6:20-cv-00890-ADA Document 1-1 Filed 09/29/20 Page 19 of 29
`
`

`

`US 6,839,321 B1
`
`1
`DOMAIN BASED CONGESTION
`MANAGEMENT
`
`FIELD OF INVENTION
`This invention is related to the field of congestion man
`agement Schemes for 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 to Statistical 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 Schemes are essential for 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 Scheme that 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
`mechanisms through either packet dropping or explicit con
`gestion notification (ECN) by marking packets of a Session.
`However, the end-to-end reaction to congestion is critically
`dependent on round trip 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
`individual traffic 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.
`Core State-less fair queuing (CSFO) has been proposed in
`order to eliminate the bookkeeping of each flow State at core
`routers. However, the key focus of CSFQ is 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 can lead 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 number of flows at the core routers. In
`addition, Diff-serv moves the complexity of per-flow band
`width management to intelligent edge routers. A Diff-Serv
`cloud comprises i) a set of edge nodes known as ingress or
`egreSS nodes depending on the traffic flow direction that may
`maintain per-flow State and ii) a set of core nodes that 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)
`
`Case 6:20-cv-00890-ADA Document 1-1 Filed 09/29/20 Page 20 of 29
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`packet dropping and buffering Strategies at various routers,
`also known as Per-Hop-Behaviors (PHBs); and iii) choice of
`an appropriate queue that maps to the type of Service that
`was chosen by the application as indicated by the TOS bits.
`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 PHBs that run on core routers can be adaptively tuned
`to compensate for the loose admission control at the edges
`where traffic 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) and ii)
`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 Schemes are 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 not be 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 wo (0<wd-1), with the arrival of nth packet, the
`average queue Size is given as follows
`avgQsize, (1-w).avgQsize, 1+w.currentOsize,
`(1)
`The allowed range of the average queue Size before
`packets are dropped determines the allowed burst sizes.
`Thus RED can accommodate traffic bursts unlike drop-tail
`FIFO-based queue thresholds, as the average queue Size
`does not Solely depend on the current queue size.
`RED employs two queue thresholds, i.e., 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
`Pindicating 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
`
`

`

`3
`probability of dropping is a function of average queue Size
`and is given by
`
`US 6,839,321 B1
`
`Pdrop F Pina
`drop
`
`(avg Osize - minih)
`(maxih - minth)
`
`(2)
`
`where P is 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
`transmission rate).
`SUMMARY OF THE INVENTION
`The present invention is a method and apparatus that 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 marks all 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 reduces its traffic
`rate in proportion to the amount of traffic 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 bucket to 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(b) 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.
`
`Case 6:20-cv-00890-ADA Document 1-1 Filed 09/29/20 Page 21 of 29
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`FIG. 9 depicts a simulation setup.
`FIG. 10 shows the performance of the DCM method vs.
`non-feedback based congestion control.
`FIG. 11 illustrates the delay performance of the DCM
`method.
`FIGS. 12(a) and 12(b) depicts a sample average queue
`Size and the distribution of packet weight at an ingreSS Token
`Bucket Filter for a utilization factor of 0.8.
`FIGS. 13(a) and 13(b) illustrate the distribution of con
`gestion periods for a non-DCM method at the core node.
`FIGS. 14(a) and 14(b) 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-RTT variation.
`
`DETAILED DESCRIPTION OF THE
`INVENTION
`The present invention is a feedback-based congestion
`control for a Diff-serv domain called Domain-based Con
`gestion Management (DCM). One improvement it 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 Schemes that 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 adjust their 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
`(or input) nodes (I) of a likely onset of a congestion (free)
`period. (In a preferred embodiment, the Local Congestion
`Notification message is an LCN bit(s) set in a data packet).
`In addition, an associated feedback control loop is intro
`duced into the DCM scheme. Upon detecting the LCN bit set
`by any of the congested core nodes (C), egress (or output)
`nodes (E) shall report to corresponding ingress nodes (I)
`about the onset of a congestion period. The ingreSS nodes, as
`a result, shall respond to LCN messages. The LCN messages
`
`

`

`S
`are used to indicate the congestion State at the relevant core
`routers, based on the average queue Size at their TBFs.
`The average queue Size at the end of an adaptation interval
`(set to RTT) associated with a given pair of ingreSS/egress
`nodes (I/E) is used as a measure of demand for network
`bandwidth at the underlying ingress nodes (I). However,
`traffic rates associated with each ingress node (I) shall be
`varied in proportion to the amount of traffic each ingreSS
`node (I) is injecting at the onset of congestion. During the
`congestion management period, the ingress node (I) that
`injected more traffic at the time of an onset congestion, shall
`be responsible for a greater reduction in transmission rates
`during congestion recovery period. This leads to a fair
`resource utilization among ingreSS nodes (I).
`The Domain-based Congestion Management Method
`The DCM scheme comprises three main features: use of
`a improvPED method and apparatus for congestion detec
`tion at the core nodes or routers (C), congestion feedback in
`the form of LCN bits and use of token bucket filters (TBF)
`to regulate traffic at ingress nodes (I).
`Improved RED
`Random probabilistic dropping/marking of packets
`affects individual Sessions proportional to their traffic rates.
`In existing congestion control Schemes, egreSS nodes can not
`estimate the degree of congestion at a bottleneck core router
`from the ECN bits of the packets. Yet, it would be beneficial
`if the egreSS nodes (E) are able to detect a potential onset of
`congestion period So as to minimize packet losses and to
`delay or prevent a corresponding congestion period.
`Therefore, the present invention provides an early feedback
`So as to minimize packet losses and to delay or prevent a
`corresponding congestion period. The DCM Scheme intro
`duces an improved RED, called improvRED, that basically
`improves the original RED to provide feedback control.
`In addition, an additional threshold, FeedbackThreshold
`(or Feedback), is introduced in the present invention. It takes
`a value between the minth (or minimum) and the maxth (or
`maximum) thresholds. The improvRED will be under a
`deterministically rather than probabilistically marking phase
`whenever the average queue Size is greater than minth and
`less than FeedbackThreshold. During this phase, all outgo
`ing packets are marked appropriately to indicate a potential
`onset of a congestion period and involves no packet drops
`130.
`When the average queue Size is equal to or greater than
`FeedbackThreshold, but less than maxth, packets are
`dropped probabilistically 140 and all the outgoing packets
`are marked appropriately to denote the dropping phase 150.
`Both the marking and dropping phases are considered as
`indicators of potential congestion State at core nodes. These
`phases are experienced by the core nodes (C) to varying
`degrees as a result of the following condition (for an onset
`of a congestion period)
`
`copag
`
`where IR (t) denotes the incoming traffic rate at the con
`gested node associated with an ingress node (I) at time t and
`R is the service rate (link capacity) of the corresponding
`congested core node (C). Condition 3 is a necessary condi
`tion to drive the core node to a potential congested State
`through queue build-ups. As a result of the above condition
`the underlying core node (C) shall be in either of the
`drop/mark phase for short durations until the DCM scheme
`regulates the traffic Such that the congested node is brought
`back to a congestion-free state. (The State where the average
`queue Size is less than minth is referred to as a congestion
`free state). When the average queue Size is greater than
`maXth, all incoming packets are dropped 160.
`
`Case 6:20-cv-00890-ADA Document 1-1 Filed 09/29/20 Page 22 of 29
`
`US 6,839,321 B1
`
`6
`The improvement behind the introduction of a Feedback
`Threshold is to avoid packet drops before any congestion
`control schemes ply in. The improvRED method is illus
`trated in the FIG. 2.
`In order to indicate the onset of a congestion period at the
`core nodes (C), feedback in the form of a simple 2-bit
`scheme is proposed that is depicted in FIG.3. The bits (bit1,
`bit2) serve as a notification to the egreSS nodes (E) of a
`Specific congestion State in the Diff-Serv domain. (The bits
`are set by the core nodes (C)). The egreSS nodes (E) shall
`appropriately notify corresponding ingress nodes (I) of the
`potential congestion at the core nodes (C).
`The details of the integration of the 2 bit-scheme with the
`last two bits of the differentiated service code point (DSCP)
`byte follows. (It is assumed that an LCN bit is available that
`is reset at every ingress node (I) and core nodes (C) can set
`it whenever they are congested).
`LCN Message
`AS discussed above, feedback, in the form of a Local
`Congestion Notification (LCN) bit or bits, is used notify the
`ingreSS nodes (I) of a likely onset of congestion period. The
`IP (Internet protocol) provides the Type of Service (TOS)
`byte in the IP packets that can be used for explicit classifi
`cation and the type of treatment (priority) the packet should
`receive at the intermediate routers. The TOS byte has been
`redefined as differentiated services code point (DSCP) byte
`in the context of Diff-serv. The definition of DSCP byte is
`described in K. Nichols, S. Blake, F. Baker, and D. Black,
`Definition of the Differentiated Services Field (DS Field) in
`the Ipv4 and Ipv6 Headers (RFC 2474), work in progress,
`1998, hereby incorporated by reference, and Summarized in
`FIG. 4. The first leftmost 6 bits of the DSCP byte are
`intended to define various PHBS and their associated Ser
`vices. Bits 7 and 8 are used for explicit congestion notifi
`cation (ECN).
`Whenever a router detects congestion, it sets the ECN bit
`(bit 8) of the DSCP byte so that the receiver can alert the
`Source of the network congestion at an intermediate router.
`The source node, in turn, may respond to the ECN bit by
`adaptively decreasing the traffic transmission rate. This
`mechanism is incorporated into many transportation proto
`cols such as TCP and contributes to a healthy network that
`can avoid congestion-collapse.
`Benefits of ECN include: i) avoidance of collapse of the
`network, and ii) flexibility of adapting to network conditions
`by the end applications. The Internet can provide an indi
`cation of an incipient congestion when using an active queue
`management Scheme Such as RED. In a preferred
`embodiment, the response to the ECN bit set packet by the
`Sender