United States Patent
`
`US 7,088,678 B1
`(10) Patent No.:
`(12)
`
`Freed et al.
`(45) Date of Patent:
`Aug. 8, 2006
`
`US007088678B1
`
`(54) SYSTEM AND METHOD FOR TRAFFIC
`SHAPING BASED ON GENERALIZED
`CONGESTION AND FLOW CONTROL
`
`(75)
`
`Inventors: Michael Freed, Pleasanton, CA (US);
`Satish Amara, Mt. Prospect, IL (US);
`Michael Borella, Naperv1lle, IL (US)
`(73) Assignee: 3Com Corporation, Marlborough, MA
`US
`(
`)
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`
`( * ) Notice:
`
`(21) App]. No.: 09/941,280
`
`(22)
`
`Filed:
`
`Aug. 27, 2001
`
`(51)
`
`Int. Cl.
`H04L 12/26
`(2006.01)
`(52) US. Cl.
`.................................... 370/230; 370/236.1
`(58) Field of Classification Search ..... 370/22972361,
`370/248, 412; 709/2327235
`See application file for complete search history.
`References Cited
`
`(56)
`
`5,608,446 A
`5,610,910 A
`5,623,542 A
`5,623,601 A
`
`..................... 348/6
`3/1997 Carr et al.
`3/1997 Focsaneanu et al.
`........ 370/351
`4/1997 Schneider et al.
`.......... 379/399
`4/1997 Vu ......
`395/187.01
`
`5,636,211 A
`5,675,732 A
`
`
`6/1997 Newlin ................... 370/465
`10/1997 Majeti et al.
`.......... 395/200.01
`(Continued)
`FOREIGN PATENT DOCUMENTS
`WO 99/11003
`3/1999
`
`W0
`
`.
`(Continued)
`
`Droms, R., Dynamic Host Configuration Protocol, Request
`for Comments 1541, Oct. 1993, pp. 1 to 31.
`
`(Continued)
`
`Primary ExamineriDuc Ho
`147321”an Exammjriphuongclgéu Bahi‘lfglyen 11 B hn
`£4 3b 112802036»
`g?“ or
`”mm C “me
`De
`‘1
`e
`ergho
`(57)
`
`ABSTRACT
`
`en
`
`U.S. PATENT DOCUMENTS
`
`4,644,533 A
`4,881,263 A
`4,996,685 A
`5’014’234 A
`5,138,712 A
`5,301,273 A
`5,347,304 A
`5,430,727 A
`5,442,749 A
`5,488,412 A
`5,489,897 A
`5,528,595 A
`5,586,121 2
`,
`,
`5,598,410 A
`5,600,717 A
`5,606,606 A
`
`................... 370/94
`2/1987 Braif et al.
`
`------- 380/21
`11/ 1989 Hefblson et 31~
`
`2/1991 Farese et 31'
`370581
`
`""" 364/900
`5/1991 Ed‘WdS’ Jr'
`8/1992 Corbin ....................... 395/700
`...................... 395/200
`4/1994 Konishi
`
`.
`9/1994 M011ra et a1.
`....... 348/12
`7/1995 Callon ..................... 370/85.13
`8/1995 Northcutt et a1,
`,,,,,, 395/20009
`1/ 1996 Majeti et a1.
`................. 348/10
`
`2/1996
`340/87039
`
`6/ 1996 Walsh-ct al.
`............. 370/85.13
`~~~~~~~~~~ £3;ng
`12/1332 ighneidetr it 31'
`oura e a . ............
`
`1/1997 Stone ...................... 370/469
`
`
`..... 379/399
`2/1997 Schneider et al.
`..
`.......... 379/399
`2/ 1997 Schneider et a1.
`
`A system and methods. are shown for traffic shaping and
`congestion av01dance in a computer network such as a
`data-over-cable network. A headend of the data-over-cable
`system includes a traffic shaper configured to calculate a
`packet arrival rate from a cable modem and a traffic condi-
`tioner configured to calculate an average queue size on an
`t
`t .
`t rf
`t
`t
`1
`t
`k F
`1
`th
`0“ 1’“ me ace 0 an ex ema He W.“ ‘
`or examP 6’
`6
`trafiic shaper compares the packet arrival rate to three packet
`aIfiVal threShOIdS induding a committed rate threshold, a
`control rate threshold and a peak rate threshold. If the
`calculated packet arrival rate falls between the committed
`threshold and control
`rate threshold,
`the traffic shaper
`applies a link layer mechanism, such as a MAP bandwidth
`allocation mechanism, to lower the transmission rate from
`the cable mOdem‘
`
`35 Claims, 5 Drawing Sheets
`
`____________________C
`l ROUTER
`
`TRAFFIC MANAGER
`
`[‘100120
`
`INCOMING
`INTERFACE m
`
`OUTGOING
`INTERFACE 1.15.
`
`
`
`
`CLIENT
`DEVICE
`
`
`
`102
`
`
`TRAFFIC
`
`TRAFFIC
`
` DATA
`CONDITIONING
`
`
`NETWORK
`SHAPER m
`1.12
`
`
`
`
`MEMORY
`UNIT 13;
`
`
`PROCESSOR
`.132.
`
`EX1015
`
`Palo Alto Networks v. Sable Networks
`
`IPR2020-01712
`
`EX1015
`Palo Alto Networks v. Sable Networks
`IPR2020-01712
`
`

`

`US 7,088,678 B1
`
`Page 2
`
`
`
`U.S. PATENT DOCUMENTS
`5,675,742 A
`10/1997 Jain etal.
`................... 395/200
`
`
`5,678,041 A
`”“997 1331“” et 31 ~
`395/609
`
`~
`5,708,654 A
`“1998 AIME et 31'
`370/242
`$33: 2:119 ~~~~~~~~~~~~~~~~~~~ 395/20054
`23:22?) A
`,
`,
`ndt et 31'
`~~~~~~~~~~~~~ 395/200'5
`2335132? A
`39525050348
`$33: 3133““ 2311'
`
`'
`’
`’
`1.2““
`'
`
`
`5784597 A
`”998 Chm et 31'
`”5552
`
`.....
`5,790,198 A
`8/1998 Roop et a1.
`348/460
`8,1998 Sistanizadeh et 31.
`.
`5790 548 A
`370,401
`
`’
`’
`8/1998 Fox et a1. ............... 380/24
`5,790,677 A
`
`8,1998 McClure et 31.
`. 395,200.61
`5,790,770 A
`
`.. 395/20082
`5,790,806 A
`8,1998 Koperda ..
`8/1998 Kline ............ 370/230
`5,793,747 A
`
`8/1998 Sudia ................ 380/23
`5,799,086 A
`
`9/1998 Laursen et 31.
`.
`5,805,804 A
`. 395/20002
`5,809,252 A
`9/1998 Beighe et 31.
`..
`. 395/20057
`5,812,819 A
`9/1998 Rodwin et al.
`.
`..... 395/500
`.. 395/200.57
`5,815,664 A
`9/1998 Asano ........
`
`............... 370/449
`5,818,845 A
`10/1998 Moura et al.
`10/1998 Manghirmalani
`5,819,028 A
`et a1.
`.....
`395/1851
`
`18/133: Ewen -t~~-i~~
`3953/3895:
`oura e a .
`......
`
`10/1998 Focsaneanu etal.
`..
`370/389
`
`~ 395/20054
`11/ 1998 Nelson etal'
`~~
`
`‘ ””0068
`11/ 1998 “mg et 31'
`‘
`11/1998 Cohen ........... 370/433
`12/1998 Radia et a1.
`.
`. 395/187.01
`
`12,1998 Dillon et a1.
`. 395,200.47
`
`
`12,1998 Cole et 31.
`709,245
`
`1/1999 Moura et 31.
`370/449
`
`1/1999 Kanaj et 31
`709/238
`
`..... 348/12
`2/1999 Laubach et 31.
`
`2/1999 Dellaverson et 31.
`. 340/825.52
`.............. 395/187.01
`3/1999 Lim et al.
`4/1999 Kompella et al.
`.......... 370/236
`
`4/1999 Mohamed
`.370/401
`................. 370/351
`5/1999 Jones et al.
`6/1999 Compliment et al.
`..... 709/223
`6/1999 Spofford et al.
`....... 395/200.56
`$333 E1111? ”in ~~~~~~~~~~~~~~ ”57/339223
`3' """"""""""
`"""""
`'
`
`”999 CPHY et 31' """""""" 370/401
`$333 EEQQAAAA“““““““ 322%?
`
`8,1999 Bhagwat et 31"”: ......... 713,201
`8/1999 Chen etal.
`.................. 455/5.1
`
`9,1999 Sidey ......
`.709/223
`................... 709/219
`9/1999 Lee etal.
`9/1999 Tanno ................... 395/200.59
`
`................... 370/232
`11/1999 Yin etal.
`11/1999 Yoshida et al.
`............. 709/245
`
`................ 370/429
`11/1999 Burns et al.
`11/1999 Rowney etal.
`............. 713/201
`
`12,1999 Kawafuji et 31.
`370,401
`............. 709/223
`12/1999 BaWden etal.
`........... 370/329
`12/1999 Craddock et al.
`
`
`12,1999 Colby et 31.
`709,226
`12/1999 Woundy ..................... 370/401
`1/2000 Li etal.
`..................... 709/219
`
`.................... 455/3.1
`1/2000 Wu etal.
`1/2000 Fijolek etal.
`.............. 709/218
`
`2/2000 Woundy .....
`. 370/410
`.................. 455/5.1
`2/2000 Chen et a1.
`3/2000 Ramanathan et al.
`....... 370/241
`4/2000 Bauman ..................... 370/229
`
`2,312,245? 2
`,
`,
`5,828,666 A
`5,835,720 A
`5335727 A
`5,841,777 A
`5,848,233 A
`5,852,721 A
`5,854,901 A
`5,859,852 A
`5,864,679 A
`5,870,134 A
`5,872,523 A
`5,884,024 A
`5,892,754 A
`5,894,479 A
`5,903,558 A
`5909549 A
`5,913,037 A
`25335413 2
`A
`’
`’
`5923559 A
`2853323 A
`5’941’988 A
`5:943:604 A
`5,954,797 A
`5,958,007 A
`5,960,177 A
`
`5,982,748 A
`5,987,524 A
`
`5,991,306 A
`5,996,076 A
`5999536 A
`6,003,077 A
`6,005,851 A
`6,006,264 A
`6,009,103 A
`6,012,088 A
`
`6,014,545 A
`6,018,767 A
`6,031,841 A
`6,032,019 A
`6,041,041 A
`6,046,979 A
`
`6,046,983 A *
`2:823:23: A
`6,049,826 A
`6,052,724 A
`6,058,421 A
`6,061,349 A
`6,064,372 A
`6,065,049 A
`6,070,187 A
`6,070,242 A
`6070 246 A
`5
`5
`6,073,178 A
`6,075,787 A
`6091709 A
`6,094,431 A
`6,104,700 A
`6,112,258 A
`6,122,254 A
`6,128,298 A
`6,130,879 A
`6,130,880 A
`6,137,792 A
`6,137,793 A
`2:123:33; A
`6,170,061 B1
`6,178,455 B1
`6185624 B1
`’
`’
`6,189,102 Bl
`6,208,656 Bl
`6,212,563 B1
`6,216,171 B1
`6,223,222 B1
`6,233,224 B1*
`6,240,464 B1
`6,243,369 B1
`6,260,072 Bl
`6,269,099 B1
`6,272,150 B1
`6,275,853 B1
`6,289,377 B1
`2133122: :1
`,
`,
`6,301,618 B1
`6,308,328 B1
`6,331,987 B1
`633L163 B1
`6,337,858 B1
`6351773 Bl
`6,370,147 Bl
`
`6,442,158 Bl
`6449391 Bl
`
`6490727 Bl
`6510462 Bl
`6,625,118 B1*
`6365485 131*
`6,868,063 131*
`6,904,015 B1*
`6914383 131*
`”OZ/0122050 A1
`
`W0
`
`FOREIGN PATENT DOCUMENTS
`W0 00/67385
`11/2000
`
`4/2000 Hasegawa et al.
`....... 370/2361
`$888 gfiéignan
`3322;
`
`4/2000 Beser ..........
`709/222
`
`................ 709/223
`4/2000 Willie etal.
`5/2000 Fijolek etal.
`.............. 709/225
`5/2000 Coile etal.
`................. 370/389
`5/2000 Kahkoska ................... 345/173
`5/2000 Beser ......................... 709/218
`5/2000 Subramaniam et al.
`..... 709/220
`5/2000 Wong et al.
`................ 713/201
`5/2000 Beser ......................... 713/201
`
`
`
`~-
`
`
`
`................ 709/229
`6/2000 Wong etal.
`..
`370/395
`6/2000 Bobeck et al.
`370/235
`700% Harrison etal~
`370/395
`70000 Yamato etal.
`............ 370/235
`8/2000 Haddock et al.
`8/2000 Miller et a1.
`.................. 710/19
`9/2000 Aydemir et al.
`370/235
`10/2000 Wootton et a1.
`370/392
`10/2000 Liu ................
`370/230
`10/2000 Naudus et al.
`.............. 370/235
`10/2000 Jonas etal.
`................. 370/354
`.. 370/360
`10/2000 Gorman etal.
`
`$3888 Edajfimeilét'a.
`33;:
`
`1/2001 Beser ......................... 713/201
`1/2001 Schutte etal.
`.............. 709/228
`2,2001 Fi.olek etal
`709,239
`J
`' “““““““
`2/2001 Beser ......................... 713/201
`
`3/2001 Hrastar et a1.
`370/401
`
`4/2001 Beser ..........
`709/227
`..
`4/2001 150110 et £11.
`709/250
`
`4/2001 Fijolek et al.
`.............. 709/227
`5/2001 Yamashita et al.
`.......... 370/231
`
`5/2001 Fijolek eta1~ ~~~~~
`709/250
`6/2001 Grimwood et al.
`370/335
`
`..
`.. 709/241
`7/2001 Rodriguez-Moral
`
`.............. 370/389
`7/2001 Borella et al.
`8/2001 Hrastar ....................... 370/486
`8/2001 Beser et 31.
`709/223
`
`.
`9/2001 Lalwaney etal.
`709/222
`1232::
`13/2231 58:31“,~~~~~
`ras ar e a .
`..............
`10/2001 Sitaraman etal.
`.......... 709/227
`10/2001 Bowcutt etal.
`............ 725/111
`12/2001 Beser ......................... 370/486
`
`”/2001 Bowman'Am‘Mh
`709/231
`................. 370/356
`1/2002 Petty et a1.
`”002 F1101eket al~
`~~~~~~~~~~~~~~ 709/228
`“002 Beser ~~~~~~~~~~
`370/401
`
`
`
`370/352
`370/516
`
`”002 Beser ~~~~~~~~~~
`
`”002 Bums et31~ ~
`
`725/129
`”/2002 Nflzarathy et al~
`
`370/432
`~~~~~
`“2003 1311013“? 31~
`370/236
`9/2003 Hadl Sallm et a1.
`
`370/412
`”005 P4319431 ~~~~~
`
`~~ 370/236
`”005 De Cn°dder
`..
`6/2005 Chen ei a1.
`370/235
`
`7/2005 Dhamnlkota~
`3709301
`”002 Sandberg ~~~~~
`345/705
`
`
`370/248
`”OZ/0186660 A” ”/2002 Bahadlroglu ~
`725/107
`2003/0028891 A1
`”003 HardtetaL
`5/2003 Barham et 31.
`............. 709/235
`2003/0097461 1A1)!<
`
`

`

`US 7,088,678 B1
`
`Page 3
`
`OTHER PUBLICATIONS
`
`RFC 791, Internet Protocol, DARPA Internet Program Pro—
`tocol Specification, Sep. 1981, pp. 1-37.
`Postel, J., Internet Protocol, DARPA Internet Program Pro—
`tocol Specification, RFC 792, Sep. 1981, pp. 1-14.
`Postel, J., User Datagram Protocol, RFC 768, Aug. 28,
`1980, pp. 1-3.
`RFC 793, Transmission Control Protocol, DARPA Internet
`Program Protocol Specification, Sep. 1981, pp. 1-68.
`Case, I. et al., A Simple Network Management Protocol
`(SNMP), RFC 1157, May 1990, pp. 1-26.
`Sollins, K., The TFIP Protocol (Revision 2), RFC 1350, Jul.
`1992, pp. 1-9.
`Alexander, S., DHCP Options and BOOTP Vendor Exten—
`sions, RFC 2132, Mar. 1997, pp. 1-37.
`“Radio Frequency Interface Specification (Interim Specifi-
`cation) SP-RFIv1.1-103-991105”, MCNS Holdings, L.P.,
`1999, pp. Ii to 366.
`“Cable Modem to Customer Premise Equipment Interface
`Specification (Interim) SP-CMCI-IO2-980317”, Multimedia
`Cable Network Systems (MCNS) Holdings, L.P., Cable
`Television Laboratories, Inc., 1998, pp. ii to 40.
`“Operations
`Support
`System Interface
`Specification
`Baseline Privacy Interface MIB (Interim Specification)
`SP-OSSI-BPI-IO1-980331”, MCNS Holdings, L.P., 1997
`and 1998, pp. ii to 33.
`“Cable Modem Termination System-Network Side Interface
`Specification (Interim Specification) SP-CMTS-NSIIOl-
`960702”, MCNS Holdings, L.P., 1996, pp. ii to 13.
`“Removable Security Module
`Interface Specification
`(Interim Specification) SP-RSMI-101-980204”, MCNS
`Holdings, L.P., Cable Television Laboratories, Inc., 1997,
`pp. ii to 47.
`“Baseline Privacy Interface Specification (Interim) SP-BPI-
`[01-970922”, MCNS Holdings, L.P., 1997, pp. ii to 65.
`“Operations
`Support
`System Interface
`Specification
`(Interim) SP-OSSIIO1-970403”, MCNS Holdings, L.P.,
`1997, pp. 1 to 30.
`“Radio Frequency Interface Specification (Interim Specifi-
`cation) SP-RFI-102-971008”, MCNS Holdings, L.P., 1997,
`pp. ii to 186.
`“Cable Modem Telephony Return Interface Specification
`(Interim) SP-CMTRI-IO1-970804”, MCNS Holdings, L.P.,
`Cable Television Laboratories, Inc., 1997, pp. ii to 73.
`
`“Security System Specification (Interim Sepcification)
`SP-SSI-IO1-970506”, MCNS Holdings, L.P., 1997, pp. ii to
`103.
`
`“Internet Engineering Task Force”, Request for Comments
`2131, Dynamic Host Configuration Protocol (DHCP), Mar.
`1997, pp. 1 to 42.
`IPCDN Telephony Return MIB,
`S. Adiraju, J. Fijolek,
`Internet Engineering Task Force, Internet Draft, “<draft-ietf-
`ipcdn-tri-mib-00.1.txt>,” Mar. 1998, pp. 1 to 26.
`Kyees, P]. et a., ADSL: A New Twisted—Pair Access to the
`Information Highway, IEEE Communications Magazine,
`vol. 33, Issue 4, Apr. 1995, pp. 52-60.
`Huang, Yin-Hwa et al., Design of an MPEG-Based Set—Top
`Boxfor Video on Demand Services, Acoustics, Speech, and
`Signal Processing, 1995, ICASSP-95., 1995 International
`Conference, vol. 4, ISBN: 0-7803-2431-5, May 9-12, 1995,
`pp. 2655-2658.
`“A Solution for the Priority Queue Problem of Deadline-
`Ordered Service Disciplines,” N.R. Figueira, IEEE Intema-
`tional Conference on Computer Communications and Net-
`works, Sep. 22-25, 1997, pp. 320-325.
`“Radio Frequency Interface Specification (Interim Specifi-
`cation) SP-RFI-IO4-980724”, MCNS Holdings, L.P., 1997,
`pp. li to 196.
`Ramakrishnan, K., A Proposal to Add Explicit Congestion
`Notification (ECN) to IP, RFC 2481, Jan. 1999, pp. 1 to 24.
`ITU-T I.732, Fucntional Characteristics ofATMEquipment,
`Oct. 2000.
`
`ITU-T I.363.3, B—ISDN AIM Apaptation Layer Specifica—
`tion: Ijzpe 3/4 AAL, Aug. 1996.
`ITU-T 1326, Functional Architecture ofTransport Networks
`Based on AIM, Nov. 1995.
`“Radio Frequency Interface Specification (Interim Specifi-
`cation) SP-RFI-I05-991105”, MCNS Holdings, L.P., 1999,
`pp. li to 202.
`“Radio Frequency Interface Specification (Interim Specifi-
`cation) SP-RFIv1.1-IO6-001215”, MCNS Holdings, L.P.,
`2000, pp. ii to 432.
`WAP Architecture, Wireless Application Protocol Architec—
`ture Specification, Version 12, Jul. 12, 2001, pp. 2-24.
`www.cotse.com, Congestion Avoidance Overview, Oct. 30,
`2000, pp. 1-8.
`
`* cited by examiner
`
`

`

`U.S. Patent
`
`00
`
`0.5
`
`mS
`
`US 7,088,678 B1
`
`$2.282.m,2:
`m:law:mofimmpz.amofimmkz.M025930
`
`
`
`m._550m
`
`5II
`<53wz_zoEn_zoom2&5:0E5;
`N:lM5.9552c:mum/Em
`
`oakFNMDGE
`
`>MOEmE
`
`a._._z_.._
`
`MOmwm—UOME
`
`MNH
`
`ll}"ll[llllill||l|llllltllljl|lll
`
`NOV
`
`._.Zm_u_0
`
`m0_>m_o
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Aug. 8, 2006
`
`Sheet 2 of 5
`
`US 7,088,678 B1
`
`com
`
`NmmDGE
`
`
`
`Din—4M;
`
`amun—dim
`
`Din—4m;
`
`msz_._._n_zOU
`
`3M
`
`nzmo<m=._
`
`a3:22
`
`
`
`Nmm0<z<_>_O_u_n_<m._.
`
`
`
`
`
`555zo:<z_s_mm:Emacsm._m<o
`
`xxO>>._.mZ<._.<n_
`
`mam
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Aug. 8, 2006
`
`Sheet 3 of 5
`
`US 7,088,678 B1
`
`
`
`mEm._<>_mm<5.on
`
`A33
`
`hmxo<m
`
`205mmmemo
`
`.39
`
`Hamsmno
`
`85
`
`.rzmfio mmanna—u—
`
`SEBozwmmzh
`
`SEQJOImmmzpsouSozwmmzp
`
`x<mm
`
`
`
`.5528nmEzzoo
`
`
`
`¥m0>>hmz<._.<D
`
`$22981an».
`
`
`
`>h_.__m<momn_206mm
`
`.5on30.5
`
`
`
`1:;moan.55.on
`
`m._m<wE
`
`>>o._"_
`
`.6528
`
`206mm
`
`.23
`
`m0_>mn
`
`
`
`wadmm0<z<2O_n_u_<m._.
`
`
`
`
`
`EMJJOEHZOUDin—ditmmnzlmDEED—.5
`
`

`

`U.S. Patent
`
`Aug. 8, 2006
`
`Sheet 4 0f 5
`
`US 7,088,678 B1
`
`FIGURE 4A
`
`a
`
`START
`
`RECEIVE DATA PACKETS FROM A NETWORK
`
`DEVICE ON A TRAFFIC SHAPER
`
`COMPUTE A PACKET ARRIVAL RATE
`
`ON AN INCOMING INTERFACE
`
`APPLY AT LEAST THREE THRESHOLD LEVELS
`
`TO THE COMPUTED PACKET ARRIVAL RATE
`
`402
`
`404
`
`406
`
`408
`
`
`ACTION REQUIRED?
`
`NO
`
`410
`
`FORWARD THE
`
`DATA PACKETS
`
`YES
`
`TO CONTROL THE PACKET ARRIVAL RATE
`
`
`ENABLE
`FLOW CONTROL?
`
`
`YES
`
`414
`
`9
`
`ENABLE A LINK LAYER MECHANISM SUCH AS
`
`A TIME SLOT ALLOCATION MECHANISM
`
`

`

`U.S. Patent
`
`Aug. 8, 2006
`
`Sheet 5 0f 5
`
`US 7,088,678 B1
`
`FIGURE 43
`
`
`
`SUCCESSFUL
`
`CONTROL?
`
`YES
`
`N0
`
`ENABLE
`
`PACKET DROP WITH
`
`‘ ROBABILITY?
`
`YES
`
`COMPUTE A PACKET DROP PROBABILITY
`
`NO
`
`DROP DATA PACKETS BASED ON
`
`THE CALCULATED PROBABILITY
`
`422
`
`
`
`
`o—~o
`
`
`
`
`
`
`
`
`
`
`
`DROP THE DATA PACKETS RECEIVED
`
`FROM THE CLIENT DEVICE
`
`424
`
`
`
`

`

`US 7,088,678 B1
`
`1
`SYSTEM AND METHOD FOR TRAFFIC
`SHAPING BASED ON GENERALIZED
`CONGESTION AND FLOW CONTROL
`
`FIELD OF THE INVENTION
`
`The present invention relates to communications in com-
`puter networks. More specifically, it relates to a system and
`method for traffic shaping based on general congestion and
`flow control.
`
`BACKGROUND OF THE INVENTION
`
`In high-speed networks, routers are required to meet
`certain quality-of-service requirements associated with com-
`municating network entities. As is known in the art, the
`quality-of-service is a communication network attribute that
`exists between two network entities requiring a predeter-
`mined network service level. The basic network parameters
`typically affecting network performance are bandwidth and
`delays since the application traffic between two network
`entities in a computer network may require a certain mini-
`mum bandwidth or may be sensitive to delays. Thus, in the
`simplest terms, the quality-of-service means providing con-
`sistent and predictable data delivery services to communi-
`cating network entities requiring a predetermined level of
`network service. Further, the quality-of-service is the ability
`of a network element, such as an application process, host or
`router to have some level of assurance that its traffic and
`
`service requirements can be satisfied.
`In general, the quality-of-service elements manage net-
`work resources according to application demands and net-
`work management settings and, thus, cannot provide cer-
`tainty that resource sharing occurs. Therefore, quality-of-
`service with a guaranteed service level requires resource
`allocation to individual data streams through the network. In
`current implementations, a priority for quality-of-service
`developers has been to ensure that resources allocated to the
`best-effort traffic are not limited after reservations are made.
`
`However, equally important is that the high-priority appli-
`cations do not disable low-priority Internet applications.
`The key mechanisms for providing a predetermined level
`of quality-of-service include an admission control,
`traffic
`shaping, packet classification, packet marking and packet
`scheduling. In quality-of-service enabled Internet Protocol
`(“IP”) networks, it is necessary to specify a traffic profile for
`a connection or a set of connections. Traffic shaping or traffic
`conditioning is typically used, for example, to control the
`rate of data transmitted out of an interface so that it matches
`
`to
`the speed of the remote target interface and, further,
`ensure that the traffic conforms to a predetermined policy
`level. Thus, traffic shaping is primarily used to control the
`access to available bandwidth, to ensure that traffic conforms
`to a predetermined set of policies, and to regulate the flow
`of traffic in order to avoid congestion that can occur if the
`transmitted traffic exceeds the access speed of its remote,
`target interface.
`Traffic shaping is typically implemented on an edge router
`or core router and provides a mechanism to control the
`amount and volume of data being sent into the network as
`well as the rate at which the data is being sent. The
`predominant methods for traffic shaping include a leaky
`bucket method and a token bucket method. The leaky bucket
`is typically used to control the rate at which data is sent into
`the network and provides a mechanism by which bursty data
`can be shaped into a steady data stream. The leaky bucket
`implementation is typically employed for shaping traffic into
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`flows with a fixed rate of admission into the network and is
`
`generally ineffective in providing a mechanism for shaping
`traffic into flows with variable rates of admission.
`
`The token bucket provides a method for traffic shaping
`and ingress rate control. The token bucket provides a control
`mechanism that dictates when data can be transmitted based
`
`on the presence of tokens in a bucket and uses network
`resources by allowing flows to burst up to configurable burst
`threshold levels. In the token bucket implementation, tokens
`are “put” into the bucket at a certain rate, and the bucket has
`a predetermined capacity. In such an implementation, if the
`bucket fills up to its top capacity, newly arriving tokens are
`discarded. Similarly, if the bucket is full of tokens, incoming
`tokens overflow and are not available for future packets.
`Thus, at any time, the largest burst of data a source can send
`into a network is roughly proportional to the size of the
`bucket. In the token burst implementation, a system admin-
`istrator may configure a token generation rate and a depth of
`the burst.
`
`In addition to traffic shaping, the token bucket methods
`may be employed for congestion avoidance. As is known in
`the art, congestion avoidance refers to methods of control-
`ling an average queue size on an outgoing interface of a
`router such as an edge router. The primary mechanism used
`by the token bucket and leaky bucket for shaping the traffic
`includes dropping the incoming data packets to the network.
`Some routers handle dropping the packets using a technique
`typically referred to as tail dropping. Using tail dropping, a
`router simply drops packets indiscriminately, i.e., without
`regard to priority or class of service, for example. Other
`methods that have been used to avoid congestion more
`effectively than tail dropping include a Random Early
`Detection (“RED”), a Flow-based Random Early Detection
`(“FRED”), or
`a Weighted Random Early Detection
`(“WRED”).
`When RED is not configured, output buffers fill during
`periods of congestion. When the buffers are full, tail drop
`occurs, and all additional packets are dropped. Since the
`packets are dropped all at once, global synchronization of
`Transmission Control Protocol hosts can occur as multiple
`hosts reduce their transmission rates. As the congestion
`clears, the Transmission Control Protocol sources increase
`their data transmission rates, resulting in waves of conges-
`tion followed by periods where the transmission link is not
`fully used.
`The Random Early Detection mechanism controls the
`data congestion by dropping or marking packets with a drop
`probability. Typically, an algorithm used by the Random
`Early Detection mechanism may sample a queue length on
`a router and compare it
`to two threshold levels, a low
`threshold level and a high threshold level. For example, if
`the queue length is less than the low threshold level, no
`packets are dropped and packets are forwarded to a desti-
`nation address. If the queue length is between the low
`threshold level and the high threshold level, incoming pack-
`ets are dropped with a probability that is directly propor-
`tional to the queue length, and, if the queue length is greater
`than the high threshold level, all
`incoming packets are
`dropped.
`The Random Early Detection mechanism reduces the
`chances of tail dropping by selectively dropping packets
`when, for example, an output interface begins to show signs
`of congestion. By dropping some packets early rather than
`waiting until the buffer is full, Random Early Detection
`avoids dropping large numbers of packets at once and
`minimizes the chances of global synchronization.
`
`

`

`US 7,088,678 B1
`
`3
`The Weighted Random Early Detection generally drops
`packets selectively based on IP precedence so that packets
`with a higher IP precedence are less likely to be dropped
`than packets with a lower precedence. In such an imple-
`mentation, higher priority traffic is delivered with a higher
`probability than lower priority traffic. The Weighted Ran-
`dom Early Detection is more useful in the core routers of a
`network, rather than at
`the edge routers that assign IP
`precedence to packets as they enter the network.
`While the Random Early Detection mechanism and the
`variation thereof have been widely studied and employed in
`the existing computer networks, they suffer from a number
`of disadvantages. The Random Early Detection mechanism
`as well as the Weighted Random Early Detection mechanism
`signal
`the source about the congestion by dropping the
`packets and have the ability to control only a predetermined
`type of data, specifically, Transmission Control Protocol
`data.
`
`5
`
`10
`
`15
`
`Thus, the need remains for a system and method for traffic
`shaping in computer networks.
`
`20
`
`SUMMARY OF THE INVENTION
`
`In accordance with embodiments of the present invention,
`some of the problems associated with traffic shaping are
`overcome.
`
`25
`
`4
`
`Another embodiment of a method for traffic shaping in a
`data-over-cable system involves, receiving at least one data
`packet on a traffic manager from a cable modem via an
`upstream communication link and, responsive thereto, cal-
`culating at least one flow control parameter, such as a packet
`arrival rate or a queue size on an outgoing interface. Next,
`the method involves comparing a value of the at least one
`flow control parameter to at least three flow control thresh-
`old levels including a committed threshold level, a control
`threshold level and a peak threshold level. If the value of the
`at least one flow control parameter falls between the com-
`mitted threshold level and the control threshold level, the
`method involves controlling a bandwidth allocation for
`upstream transmission from the cable modem.
`An embodiment of a computer system, according to the
`present invention, includes an input interface arranged to
`receive at least one data packet from a network entity via an
`upstream communication link, an output interface arranged
`to send the at least one data packet to an external network,
`and a traffic manager connected to the input interface and the
`output interface. The traffic manager is arranged to calculate
`at least one flow control parameter using the at least one data
`packet received from the network entity and compares it to
`a set of flow control
`thresholds including a committed
`threshold level, a control threshold level, and a peak thresh-
`old level. The traffic manager is further arranged to apply a
`flow control mechanism to control data flow from the
`
`An embodiment of a method for traffic shaping in a
`computer network, according to the present
`invention,
`involves receiving at
`least one data packet on a traffic
`manager from a user network entity and, responsive thereto,
`calculating at least one flow control parameter using the at
`least one data packet from the user network entity. Next, the
`at least one flow control parameter is compared to at least
`three threshold levels including a committed threshold level,
`a control threshold level and a peak threshold level. Accord-
`ing to one embodiment of the present invention, the traffic
`manager includes a traffic shaper. In such an embodiment,
`the method includes calculating a data packet rate on the
`traffic shaper. If a value of the at least one flow control
`parameter, i.e. a data packet rate, falls between the commit-
`ted threshold level and the control
`threshold level,
`the
`method includes applying a link layer control mechanism to
`control data flow from the user network entity. The link layer
`control mechanism may involve controlling a transmit slot
`allocation for transmission from the user network entity. In
`a data-over-cable system, the traffic manager may employ a
`bandwidth allocation mechanism, such as MAP, to control
`upstream bandwidth allocation for the user network entity.
`Another embodiment of a method for traffic shaping
`according to the present invention involves, receiving at
`least one data packet on a traffic manager including a traffic
`conditioner from a user network entity and, responsive
`thereto, calculating at least one flow control parameter such
`as a queue size on an outgoing interface using the at least one
`data packet from the user network entity. Next, the queue
`size is compared to at least three threshold levels including
`a committed threshold level, a control threshold level and a
`peak threshold level. If a value of the queue size falls
`between the committed threshold level and the control
`
`threshold level, the method includes applying a link layer
`control mechanism to control data flow from the user
`
`network entity. The link layer control mechanism may
`involve controlling a transmit slot allocation for transmis-
`sion from the user network entity. In a data-over-cable
`system, the traffic manager may employ a bandwidth allo-
`cation mechanism, such as MAP, to control upstream band-
`width allocation for the user network entity.
`
`network entity is a value of the at least one flow control
`parameter falls between the committed threshold level and
`the control threshold level.
`
`30
`
`These as well as other aspects and advantages of the
`present invention will become more apparent to those of
`ordinary skill in the art by reading the following detailed
`description, with reference to the accompanying drawings.
`
`35
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`invention are
`Exemplary embodiments of the present
`described with reference to the following drawings,
`in
`which:
`
`40
`
`45
`
`50
`
`55
`
`60
`
`FIG. 1 is a functional block diagram illustrating a system
`architecture suitable for application of the present invention;
`FIG. 2 is a functional block diagram illustrating a data-
`over-cable system for traffic shaping and congestion avoid-
`ance according to an embodiment of the present invention;
`FIG. 3 is a block diagram illustrating an exemplary
`implementation of threshold levels for traffic shaping and
`congestion avoidance according to an embodiment of the
`present invention; and
`FIGS. 4A74B are a flowchart illustrating a method for
`traffic shaping in a data-over-cable system according to an
`embodiment of the present invention.
`
`DETAILED DESCRIPTION OF PREFERRED
`EMBODIMENTS
`
`FIG. 1 is a functional block diagram illustrating an
`exemplary embodiment of a network architecture 100 suit-
`able for application to the present
`invention for traffic
`shaping based on flow control and generalized congestion.
`FIG. 1 shows the architecture 100 including a data network
`118, such as a public Internet Protocol (IP) network to which
`a router 120 is linked via a network connection 116. A user
`
`65
`
`network entity, such as a client device 102, is linked to the
`router 120 via a communication link 104. The communica-
`
`tion link 104, as will be described in greater detail below,
`may include a cable connection, a wireless connection, a
`
`

`

`US 7,088,678 B1
`
`5
`dial-up connection, or any other network connection utiliz-
`ing a network protocol including link-layer mechanisms for
`controlling data transmission from the client device 102.
`In the network architecture 100 illustrated in FIG. 1, the
`router 120 may include an edge router. Edge routers typi-
`cally assign IP priority to packets as the packets enter the
`network so that core routers on the network may use the
`priority parameters specified in the packets to determine
`how to forward the packets to the next hop on the network.
`The router 120 includes a traffic manager 106 for traffic
`shaping according to one embodiment of the present inven-
`tion, in which, upon a receipt of at least one data packet from
`the client device 102, the traffic manager 120 calculates at
`least one flow control parameter and compares it to at least
`three threshold levels including a committed threshold level,
`a control threshold level and a peak threshold level. If the
`value of the calculated flow control parameter falls between
`the committed threshold level and the control
`threshold
`
`level, the traffic manager 120 applies a link-layer control
`mechanism to control data flow from the client device 102,
`as will be described in greater detail below.
`The traffic manager 106 includes a traffic shaper 110 and
`a traffic conditioner 112. FIG. 1, as well as subsequent
`figures, illustrates an embodiment in which the traffic shaper
`110 and the traffic conditioner 112 are separate entities,
`where the traffic shaper 110 controls data flow one an
`incoming interface 108, and the traffic conditioner 112
`controls data flows on an outgoing interface 114. However,
`it should be understood that in a preferred embodiment the
`router 120 may include a single entity including the func-
`tionality of both the traffic shaper 110 and the traffic con-
`ditioner 112.
`
`The traffic shaper 110 calculates a flow control parameter
`such as a data arrival rate on the incoming interface 108.
`When the traffic shaper 110 calculates the data arrival rate,
`it compares the data arrival rate with a predetermined set of
`traffic shaping thresholds. If the flow control parameter
`calculated on the traffic shaper 110 includes a data arrival
`rate,
`the traffic shaper 110 compares it to at least three
`threshold levels including a committed rate threshold level,
`a control rate threshold level and a peak rate threshold level.
`In such an embodiment, if the data arrival rate falls between
`the committed threshold level and the control
`threshold
`
`level, the traffic manager 106 enables a flow control mecha-
`nism to control