`US007295516Bl
`
`c12) United States Patent
`Ye
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 7,295,516 Bl
`Nov. 13, 2007
`
`(54) EARLY TRAFFIC REGULATION
`TECHNIQUES TO PROTECT AGAINST
`NETWORK FLOODING
`
`(75)
`
`Inventor: Baoqing Ye, Nashua, NH (US)
`
`(73) Assignee: Verizon Services Corp., Waltham, MA
`(US)
`
`( *) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 1068 days.
`
`(21) Appl. No.: 10/010,774
`
`(22)
`
`Filed:
`
`Nov. 13, 2001
`
`(51)
`
`Int. Cl.
`H04J 1116
`(2006.01)
`H04J 3/16
`(2006.01)
`G06F 11100
`(2006.01)
`U.S. Cl. ...................... 370/232; 370/236; 370/468;
`726/22
`(58) Field of Classification Search ..... 370/229-236.1,
`370/395.1, 465
`See application file for complete search history.
`
`(52)
`
`6,865,185 Bl*
`7,058,015 Bl*
`7,062,782 Bl*
`7,092,357 Bl*
`7,188,366 B2 *
`2002/0101819 Al*
`2003/0172289 Al*
`
`3/2005 Patel et al . ................. 370/412
`6/2006 Wetherall et al . ........... 370/236
`6/2006 Stone et al.
`.................. 726/22
`8/2006 Ye
`............................. 370/230
`3/2007 Chen et al. ................... 726/23
`8/2002 Goldstone ................... 370/229
`9/2003 Soppera ...................... 713/200
`
`OTHER PUBLICATIONS
`
`H-Y Chang S. F. Wu, C. Sargor, and X. Wu, "Towards Tracing
`Hidden Attackers on Untrusted IP Networks", pp. 1-19.
`S. Savage, D. Wetherall, A. Karlin and T. Anderson, "Practical
`Network Support for IP Traceback", Technical Report UW-CSE-
`00-02-01, University of Washington, 6 pgs.
`
`(Continued)
`
`Primary Examiner----Chau Nguyen
`Assistant Examiner-Nittaya Juntima
`
`(57)
`
`ABSTRACT
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`4,769,811 A *
`9/1988 Eckberg et al. ............. 370/236
`5,090,011 A *
`2/1992 Fukuta et al ................ 370/230
`5,309,431 A *
`5/1994 Tominaga et al.
`.......... 370/235
`5,457,687 A * 10/1995 Newman .................... 370/232
`5,706,279 A *
`1/1998 Teraslinna .................. 370/232
`5,835,484 A * 11/1998 Yamato et al. .............. 370/230
`5,901,140 A *
`5/1999 Van As et al. .............. 370/236
`5,914,936 A *
`6/1999 Hatono et al. .............. 370/230
`6,028,842 A *
`2/2000 Chapman et al. ........... 370/235
`6,144,714 A * 11/2000 Bleiweiss et al ............ 375/376
`3/2001 Ogawa et al. ......... 370/395.52
`6,208,653 Bl*
`6,424,620 Bl *
`7/2002 Nishihara ................... 370/229
`6,463,036 B2 * 10/2002 Nakamura et al. ....... 370/236.1
`6,657,961 Bl* 12/2003 Lauffenburger et al . .... 370/231
`6,724,721 Bl*
`4/2004 Cheriton ..................... 370/229
`6,735,702 Bl *
`5/2004 Yavatkar et al. .............. 726/13
`
`Methods and apparatus for providing an Anti-Flooding
`Flow-Control (AFFC) mechanism suitable for use in defend(cid:173)
`ing against flooding network Denial-of-Service (N-DoS)
`attacks is described. Features of the AFFC mechanism
`include (1) traffic baseline generation, (2) dynamic buffer
`management, (3) packet scheduling, and ( 4) optional early
`traffic regulation. Baseline statistics on the flow rates for
`flows of data corresponding to different classes of packets
`are generated. When a router senses congestion, it activates
`the AFFC mechanism of the present invention. Traffic flows
`are classified. Elastic traffic is examined to determine if it is
`responsive to flow control signals. Flows of non-responsive
`elastic traffic is dropped. The remaining flows are compared
`to corresponding class baseline flow rates. Flows exceeding
`the baseline flow rates are subject to forced flow rate
`reductions, e.g., dropping of packets.
`
`11 Claims, 10 Drawing Sheets
`
`902
`
`904
`
`906
`
`908
`
`DESTINATIONNODETRANSMITSPATHINFORMATIONTO
`BOTTLENECK NODE
`
`910
`
`INRESPONSETOCONGESTIONCONTROLMETHOD,UPSTREAM
`NODE#'PLIESFORCEDREDUCTIONTOFLOW(S}DIRECTEDTO
`DESTINATIONINDICATEDINETRSIGNAL
`
`914
`
`916
`
`EX1008
`Palo Alto Networks v. Sable Networks
`IPR2020-01712
`
`
`
`US 7,295,516 Bl
`Page 2
`
`OTHER PUBLICATIONS
`
`"Characterizing and Tracing Packet Floods Using Cisco Routers",
`downloaded from: wysiwyg:/ /23/http://www.cisco.com/warp/pub(cid:173)
`lic/707 /22.html, 5 pgs.
`"Cert® Advisory CA-1996-26 Denial-of-Service Attack via ping",
`downloaded
`from:
`http://www.cert.org/advisories/CA-1996-26.
`html, 4 pgs., last revised Dec. 5, 1997.
`"Cert® Advisory CA-1996-21 TCP SYN Flooding and IP Spoofing
`Attacks", downloaded from: http://www.cert.org/advisories/CA-
`1996-21.html on Mar. 14, 2002, pp. 1-8, last revised Nov. 29, 2000.
`S. Blake, D. Black, M. Carlson, E. Davies, Z. Wang, W. Weiss, "An
`Architecture for Differentiated Services", Network Working Group
`Request For Comments: 2475, downloaded from: ftp://ftp.isi.edu/
`in-notes/rfc2475.txt on Mar. 14, 2002, Dec. 1998, pp. 1-32.
`L. Houvinen and J. Hursti, "Denial of Service Attacks: Teardrop and
`Land", Department of Computer Science Helsinki University of
`Technology, downloaded
`from:
`http://www.hut.fi/-ilhuovine/
`hacker/dos.html on Mar. 14, 2002, pp. 1-12.
`SecurityFocus home mailing list: BugTraq "The "mstrearn" distrib(cid:173)
`uted denial of service attack tool", downloaded from: http://online.
`securityfocus.corn/archive/1/57854 on Mar. 14, 2002, May 1, 2000,
`pp. 1-22.
`
`Bellovin and Leech AT&T Labs Research, "ICMP Traceback Mes(cid:173)
`sages", Network Working Group Internet Draft, downloaded from:
`http://www.ietf.org/internet-drafts/draft-ietf-itrace-00.txt on Jul. 9,
`2001, Mar. 2001, pp. 1-9.
`S. Floyd and V. Paxson, "Why We Don't Know How To Simulate
`The Internet", AT&T Center for Internet Research, Oct. 11, 1999,
`pp. 1-13.
`S. Floyd and K. Fall, "Promoting the Use of End-to-End Congestion
`Control in the Internet", May 3, 1999, pp. 1-16.
`K. Thompson, G. J. Miller, and R. Wilder, "Wide-Area Internet
`Traffic Patterns and Characteristics", IEEE Network, Nov./Dec.
`1997, pp. 10-23.
`S. Floyd and V. Jacobson, "Link-sharing and Resource Management
`Models for Packet Networks", IEEE/ACM Transactions on Net(cid:173)
`working, vol. 3, No. 4, Aug. 1995, 22 pgs.
`S. Floyd and V. Jacobson, "Random Early Detection Gateways for
`Congestion Avoidance", Lawrence Berkeley Laboratory University
`of California, 1993, pp. 1-22.
`
`* cited by examiner
`
`
`
`U.S. Patent
`U.S. Patent
`
`Nov. 13, 2007
`Nov. 13,2007
`
`Sheet 1 of 10
`Sheet 1 of 10
`
`US 7,295,516 Bl
`US 7,295,516 B1
`
`110
`
`112
`
`0
`
`114
`
`C")
`0
`
`0
`
`0 C
`FIDO
`
`HGURE1
`
`w
`a::::
`::J
`(!)
`LL
`
`<D
`0:::
`
`0 cc
`
` 108
`
`CY)
`"<'"""
`
`0)
`0:::
`
`0\
`CX) i N
`i
`
`"<'"""
`
`0:,
`0:::
`
`""" N
`
`"<'"""
`
`N
`N
`"<'"""
`
`LO
`0:::
`
`i
`
`"d"
`0:::
`
`,F
`
`/;
`
`0
`N
`"<'"""
`
`tO
`"<'"""
`T"""
`
`C')
`0:::
`
`I
`i
`
`N
`0:::
`
`CX)
`0
`T"""
`
`
`
`U.S. Patent
`
`Nov. 13, 2007
`
`Sheet 2 of 10
`
`US 7,295,516 Bl
`
`NETWORK NODE
`
`200
`
`/
`
`21 0
`
`/
`
`202
`
`/
`
`CPU
`
`204
`
`I
`
`PACKET
`FORWARDING
`ENGINE
`
`'---...
`
`216
`
`I
`TRAFFIC
`MONITORING
`ROUTINE
`
`214
`
`/
`
`RECYCLING
`TABLE
`
`MEMORY
`218
`/
`TRAFFIC
`CLASSIFIER
`
`/220
`
`FORWARDING AND
`FLOW CONTROL
`ROUTINE
`
`222
`
`-
`
`TRAFFIC BASELINE
`GENERATING
`MODULE
`
`224
`
`--
`
`DYNAMIC BUFFER
`MANAGER
`MODULE
`
`/226
`PACKET
`SCHEDULER
`MODULE
`
`/ 228
`EARLY-TRAFF IC
`REGULATOR
`MODULE
`
`232
`/
`TRAFFIC
`BASELINES
`
`/230
`
`CURRENT TRAFFIC STATISTICS
`235
`237
`239
`
`/[;]
`
`TOTAL
`BITS
`
`S
`
`234
`I
`MULTIPLE CLASS
`BASED PACKET
`QUEUES
`
`---.....
`231
`
`233
`
`1.
`
`--L-O_N_G -TE_R_M-TRA-FF-IC--.
`STATISTICS
`
`1/0INTERFACE
`
`V
`
`208
`
`TO/FROM ROUTERS AND/OR HOST DEVICES
`
`FIGURE 2
`
`
`
`U.S. Patent
`
`Nov. 13, 2007
`
`Sheet 3 of 10
`
`US 7,295,516 Bl
`
`325
`
`INCOMING
`PACKET
`STREAM FOR
`TIME PERIOD AT
`
`START
`
`301
`
`RECEIVE PACKETS
`
`302
`
`CLASSIFY PACKETS INTO CLASSES, EACH
`CLASS BEIING DEFINED BY DESTINATION
`ADDRESS,PROTOCOL TYPE,AND
`APPLICATION TYPE
`
`303
`
`FOR EACH CLASS DO:
`
`304
`
`GENERA TE SUM OF
`MAXIMUM NUMBER OF
`BITS RECEIVED FROM
`ANY ONE FLOW
`DURING EACH SECOND
`OF TIME PERIOD AT
`
`GENERATE SUM OF
`TOT AL BITS RECEIVED
`DURING TIME AT FOR
`ALL FLOWS IN CLASS
`
`GENERATE SUM OF
`305 MINIMUM NUMBER OF
`BITS RECEIVED FROM
`ANYONE FLOW
`DURING EACH SECOND
`OF TIME PERIOD AT
`
`SUBTRACT MAX AND MIN SUMS FROM
`TOTAL SUM TO GENERATE MODIFIED SUM
`
`307
`
`DIVIDE MODIFIED SUM BY SECONDS IN TIME PERIOD AT AND
`NUMBER OF FLOWS IN CLASS MINUS 2 TO GENERATE
`CURRENT AVERAGE FLOW DATA RATE
`
`308
`
`STORE CURRENT AVERAGE FLOW
`DATA RATE
`
`310
`
`RETRIEVE STORED AVERAGE FLOW DATA
`RATES FOR TIME PERIOD AT FROM STORED
`STATISTICS FOR PRECEDING WEEKS
`
`EXCLUDE FROM SET OF AVERAGE FLOW RATES,
`INCLUDING PRECEDING WEEKS AND CURRENT WEEK,
`MIN AND MAX AVERAGE FLOW RATE
`
`312
`
`314
`
`GENERATE AVERAGE FLOW RATE BASELINE, FOR GIVEN
`CLASS, BY AVERAGING REMAINING FLOW RATES
`
`316
`
`STORE GENERATED CLASS
`FLOW RA TE BASELINE
`
`318
`
`FIGURE 3
`
`
`
`Protocol Type
`Aoolication Type
`Average Baseline
`(Arrival Rate bit/sec)
`
`Traffic Type
`Protocol Type
`Aoolication Type
`Arrival Rate
`Flow (s)
`Arrival Rate Per Flow
`
`Traffic Tvoe
`Protocol Type
`Aoolication Type
`Throughput (bit/sec)
`Flow (s)
`Responsiveness
`Aaaressiveness
`Throughput
`
`'t 404
`f_ 402
`Class Flow Baseline Table For Destination D2
`TCP
`
`'t 406
`
`'t 408
`
`UDP
`
`400
`
`Web
`
`1000
`
`FTP
`
`500
`
`Class 1
`Class 2
`FIGURE 4
`
`Flow Statistics Before Processing
`Elastic
`TCP
`
`Web
`FTP
`1100
`3500
`I F2
`I F5
`I F3
`F4
`I 1200 I 1500
`700 I 400
`Class 1
`Class 2
`FIGURE 6
`
`Traffic Throughput After Processing
`Elastic
`TCP
`
`FTP
`400
`
`Web
`1800
`F2
`F4
`F5
`YES
`NO
`YES
`YES
`YES
`NO
`1000
`400
`0
`Class 1
`Class 2
`FIGURE 7
`
`F3
`NO
`YES
`0
`
`Echo
`
`200
`
`DNS
`
`100
`
`Class 3
`
`Class4
`
`Best-Effort
`UDP
`
`Echo
`780
`I F7
`F6
`I 500
`180
`Class 3
`
`ONS
`290
`I F9
`F8
`200 I 90
`Class 4
`
`Best-Effort
`UDP
`
`Echo
`380
`
`F7
`F6
`NIA
`NIA
`YES
`NO
`200
`180
`Class 3
`
`DNS
`200
`
`F9
`F8
`NIA
`NIA
`NO
`YES
`90
`100
`Class 4
`
`600
`
`700
`
`F1
`800
`
`F1
`YES
`NO
`800
`
`e •
`
`00
`•
`~
`~
`~
`
`~ = ~
`
`z 0
`~ ....
`
`~
`
`~
`N
`0
`0
`-....J
`
`rJJ =(cid:173)
`('D a
`0 ....
`....
`
`.i;...
`
`0
`
`d r.,;_
`-....l
`'N
`\0
`UI
`tit
`
`"'""' 0--, = "'""'
`
`
`
`U.S. Patent
`
`Nov. 13, 2007
`
`Sheet 5 of 10
`
`US 7,295,516 Bl
`
`START
`
`502
`
`y
`
`N
`
`~20
`
`I INTIATE ETR
`I SIGNALING
`
`l,- 506
`I
`
`CLASSIFY INCOMING
`TRAFFIC INTO FLOWS
`
`508
`
`FOR EACH
`FLOW:
`
`ELASTIC
`
`BEST EFFORT
`
`N
`
`y
`
`520
`
`N
`
`216
`
`BASELINE
`
`REGULATE
`FORWARDING
`RATE
`
`529
`
`527
`
`FORWARD PACKETS SUBJECT TO
`APPLIED FORWARDING RATE
`REDUCTION
`
`FORWARD
`PACKETS
`
`STOP
`
`530
`
`FIGURE 5
`
`
`
`U.S. Patent
`
`Nov. 13, 2007
`
`Sheet 6 of 10
`
`US 7,295,516 Bl
`
`ORIGINAL ARRIVAL
`RATE ""o
`
`800
`
`/
`
`MIN
`MAX
`THRESHOLD THRESHOLD
`802 804
`~
`
`t
`
`I
`I
`I
`
`ff~
`
`DROPPING-RA TE v
`
`FIGURE 8
`
`OUTGOING RA TE
`
`•
`
`""ouT
`
`
`
`U.S. Patent
`
`Nov. 13, 2007
`
`Sheet 7 of 10
`
`US 7,295,516 Bl
`
`START ETR
`
`902
`
`~ 00
`
`DETECT POTENTIAL CONGESTION
`COLLAPESE AT CURRENT NODE
`(BOTTLENECK NODE)
`
`904
`
`SEND MESSAGE FROM
`BOTTLENECK NODE TO
`DESTINATION NODE TO
`INITIATE A BACKTRACING
`OPERATION
`
`DESTINATION NODE DETERMINES
`PATH OF PACKET(s)
`CORRESPONDING TO FLOW(S)
`CAUSING BOTTLENECK
`
`906
`
`908
`
`DESTINATION NODE TRANSMITS PATH INFORMATION TO
`BOTTLENECK NODE
`
`910
`
`BOTTLENCK NODE SENDS AN ETR SIGNAL INCLUDING, E.G.,
`DESTINATION ADDRESS, TO UPSTREAM NODE(s) INDICATED IN
`RECEIVED PATH INFORMATION
`
`912
`
`IN RESPONSE TO CONGESTION CONTROL METHOD, UPSTREAM
`NODE APPLIES FORCED REDUCTION TO FLOW(S) DIRECTED TO
`DESTINATION INDICATED IN ETR SIGNAL
`
`914
`
`STOP
`
`916
`
`FIGURE 9
`
`
`
`U.S. Patent
`
`Nov. 13, 2007
`
`Sheet 8 of 10
`
`US 7,295,516 Bl
`
`228
`
`NETWORK NODE ETR MODULE
`
`1030
`
`MAIN ETR
`CONTROL
`ROUTINE
`
`/1034
`
`/1038
`
`Bt-S
`SUBROUTINE
`
`Rt-R
`SUBROUTINE
`
`/1036
`
`/1042
`
`ETR-S
`SUBROUTINE
`
`ETR-R
`SUBROUTINE
`
`FIGURE 10A
`
`228'
`
`HOST DEVICE ETR MODULE
`
`/1032
`
`/ 1040
`
`Rt-S
`SUBROUTINE
`
`Bt-R
`SUBROUTINE
`
`FIGURE 108
`
`
`
`U.S. Patent
`
`Nov. 13, 2007
`
`Sheet 9 of 10
`
`US 7,295,516 Bl
`
`DESTINATION NODE
`
`1032
`'
`
`Rt-S
`SUBROUTINE ""
`
`_J
`
`. .
`
`Bt-R
`r SUBROUTINE
`
`I
`
`.,..,.... 1 10
`
`1040
`y
`
`+ H
`...-1112
`1110~
`.
`
`1114 .......,
`·o·
`Rt-R
`SUBROUTINE
`~1116
`ETR-S
`SUBROUTINE
`
`1038
`-...
`
`1036
`
`'
`
`1034
`---
`Bt-S
`SUBROUTINE
`t
`~1135
`MAIN ETR 1030
`I
`CONTROL V
`I
`ROUTINE
`I BOTTLENECK NODE
`-1118 ~1126
`,,
`I
`Bt-S
`ETR-R
`SUBROUTINE
`SUBROUTINE
`1036
`.A
`,,
`-1120
`I
`\
`MAIN ETR 10301
`ETR-S
`I
`SUBROUTINE f+ CONTROL /
`ROUTINE
`I
`I
`r1124
`FROM
`UPSTREAM
`NODE
`
`v1 27
`
`120
`
`V
`
`1034
`V
`
`UPSTREAM NODE
`
`1042
`'
`
`,;- 1122
`
`TO
`UPSTREAM
`NODE
`
`FIGURE 11
`
`
`
`U.S. Patent
`U.S. Patent
`
`Nov. 13, 2007
`m
`
`Sheet 10 of 10
`01f00
`
`US 7,295,516 Bl
`US 7,295,516 B1
`
`
`
`SEz_<Io,E<n_moOzxmoamz
`
`I-
`I-
`0::
`z
`<(
`I
`
`nuopkmmSE
`
`0
`I-
`I-
`0::
`
`~
`
`N
`w
`0:::
`:::>
`(9
`LL
`
`0 ±
`I'-
`~ 0
`CL N
`......
`w
`0
`0
`z
`:::<:::
`a::
`0
`s
`I-
`w
`z
`
`mmow?
`
`LO
`0
`N ......
`
`
`
`0:: w
`>
`i:u
`0
`w
`0::
`
`~ Y'. w
`I- 0 0
`I- w 0 Ozz
`
`(I)
`
`
`
`
`B,MaoZI|AlIAI
`
`.Ezmfim......wxomzE2cm$59.womsowNatom.
`
`a:
`
`N a:
`
`C
`Ct:'.
`
`a:
`w
`I-
`:::>
`0
`0::
`
`w
`(..)
`0::
`:::>
`0 u:,
`
`...
`I
`I
`
`...
`I
`
`N
`......
`N ......
`
`0 ......
`N
`......
`
`co
`0
`N ......
`
`NFNF3N?wow?wow?wow?
`
`
`
`(0
`0
`N ...-
`
`"" 0
`N ...-
`
`N
`0
`N ...-
`
`
`
`
`
`US 7,295,516 Bl
`
`1
`EARLY TRAFFIC REGULATION
`TECHNIQUES TO PROTECT AGAINST
`NETWORK FLOODING
`
`FIELD OF THE INVENTION
`
`The present invention is directed to connnunication sys(cid:173)
`tems, and more particularly, to flow control methods and
`apparatus suitable for use in network congestion control,
`especially when systems are under flooding Denial-of-ser(cid:173)
`vice attacks.
`
`BACKGROUND OF THE INVENTION
`
`2
`Another disadvantage of the signature capture system is
`that the signature collection methods are an aftermath
`defense approach. Thus, such an approach helps in prevent(cid:173)
`ing future attacks with known signatures, but is of limited
`5 use during initial attacks.
`In view of the above discussion, it is apparent that there
`is a need for methods of effectively identifying malicious
`traffic flows, e.g., traffic flows from individuals and/or
`sources involved in launching an N-DoS attack. There is
`10 also a need for methods and apparatus for reducing and/or
`eliminating the effects of malicious traffic flows associated
`with N-DoS attacks. It is desirable that at least some
`congestion control methods be capable oflimiting malicious
`traffic prior to a significant collapse or restriction on legiti-
`15 mate network traffic occurs.
`
`SUMMARY OF THE INVENTION
`
`Data networks are used today to transmit vast amounts of
`data. Such networks comprise elements sometimes called
`nodes. Nodes may be, e.g., routers, switches, and/or end(cid:173)
`hosts. Among those nodes, routers or switches are called
`network nodes. End-hosts can serve as the source or desti(cid:173)
`nation of data transmitted through a network. In many 20
`packet networks, data is transmitted between a source and
`destination device as a flow of packets. Flows of packets can
`be categorized by a wide range of factors including, e.g., the
`type of protocol used to form and/or transmit the packet
`and/or the specific type of application to which the packet 25
`corresponds.
`As known in the art, it is connnon to monitor traffic flows
`and store flow statistics in a database, e.g., for purposes of
`load balancing and traffic route determination. Gathered
`traffic information for a node typically includes information 30
`such as packet flow rates and, for each flow, protocol type,
`application type, source IP address, source port number,
`destination IP address, destination port number, etc. Such
`detailed statistics along with information about the time
`periods in which such statistics are gathered can be used to 35
`group traffic flows into a wide number of classes depending
`on the intended purpose of grouping the traffic.
`Flooding Network DoS (N-DoS) attacks occur in a net(cid:173)
`work when one or more sources send large amounts of data
`to a destination node, e.g., web page server, in an attempt to
`interfere with the normal servicing of traffic at the destina(cid:173)
`tion node. Flows of traffic used to implement N-DoS attack
`can be considered malicious since their purpose is to inter(cid:173)
`fere with the connnunication and servicing of legitimate
`network traffic.
`Malicious flows associated with an flooding N-DoS attack
`often create congestion at certain nodes located prior to, i.e.,
`upstream from, the flaw's destination node. The nodes at
`which congestion occurs are sometimes referred to as bottle(cid:173)
`neck nodes.
`As a result of malicious sources flooding a bottleneck
`node with traffic, legitimate traffic passing through the
`bottleneck node may be subject to dropping of packets
`thereby preventing
`legitimate connnunications. Thus,
`N-DoS attacks negatively effect legitimate users, and/or
`even cause its victim's services (e.g. web sites) to crash due
`to excessive loading.
`One known technique for protecting against N-DoS
`attacks involves explicit signature capture and analysis. For
`example, those signatures can be connnunication port num(cid:173)
`bers, daemon names or commands, or contained in IP packet
`payload. Unfortunately these approaches can be ineffective
`and may result in negative consequences for legitimate
`users, because the signatures can change over time making
`a captured signature useless in identifying a malicious
`source during a subsequent attack.
`
`40
`
`The present invention is directed to congestion control
`methods and apparatus. Various methods and apparatus of
`the invention are well suited for defending against flooding
`network Denial-of-Service (N-DoS) attacks.
`An Anti-Flooding Flow-Control (AFFC) mechanism of
`the present invention monitors, analyzes, and regulates
`traffic flows at network nodes, e.g., routers, based on the
`flaw's behavior. In a node, the AFFC mechanism of the
`invention, utilizes a traffic baseline generating module, a
`dynamic buffer manager module, a packet scheduler mod(cid:173)
`ule, and optionally, an early traffic regulator (ETR) module.
`Each module may be implemented using software and/or
`hardware.
`In some embodiments traffic baselines are generated
`external to a node using traffic information for the particular
`node. The generated baselines are then supplied to the
`dynamic buffer manager and packet scheduler in the node.
`In such embodiments, the traffic baseline module may be
`implemented as a stand-alone device separate from packet
`forwarding nodes. This can reduce the processing burden
`placed on such nodes by the AFFC methods of the invention.
`While the AFFC mechanism can be implemented in a
`single node, for more effective network protection it can be
`implemented in multiple network nodes. AFFC modules,
`e.g., ETR modules, of different nodes may, and in various
`embodiments do, interact with one another to perform a
`multi-node approach to congestion control.
`The traffic baseline generating module receives and ana(cid:173)
`lyzes traffic statistics to generate baseline flow statistics,
`e.g., diurnal flow statistics, for individual periods of time,
`e.g., hours or minutes of a day in a week. The traffic
`50 baselines are generated for each node based on the traffic
`through the node over an extended period of time, e.g.,
`multiple weeks.
`As part of the flow control method, the current data flow
`rates are compared to the corresponding baseline flow rate
`55 for the same period of time and type of traffic. Flows are
`determined to be aggressive if they have an arrival rate that
`is higher than the baseline for flow of its type. In accordance
`with the present invention, under certain circumstances
`aggressive flows are targeted for forced data rate reductions.
`60 In addition to aggressive flows, unresponsive elastic flows
`may be blocked independently of traffic baselines.
`The dynamic buffer manager module 224 and packet
`scheduler module 226 are the mechanisms by which forced
`reductions in data flow rates are implemented at a node in
`65 response to the presence of congestion. In accordance with
`the invention the forced data flow reduction functionality of
`the buffer manager and packet scheduler normally remain
`
`45
`
`
`
`US 7,295,516 Bl
`
`10
`
`4
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 illustrates a communications system incorporating
`nodes that implement the present invention.
`FIG. 2 illustrates an exemplary router implemented in
`accordance with the present invention that may be used as
`one of the routers shown in FIG. 1.
`FIG. 3 illustrates the steps of an exemplary traffic baseline
`generation routine of the invention.
`FIG. 4 illustrates an exemplary flow baseline table gen(cid:173)
`erated and used in accordance with an embodiment of the
`present invention.
`FIG. 5 illustrates the steps of an Anti-Flooding Flow(cid:173)
`Control (AFFC) method implemented in accordance with an
`exemplary embodiment of the present invention.
`FIG. 6 illustrates an exemplary set of internet traffic
`statistics measured right during a period of potential con(cid:173)
`gestion collapse at a bottleneck node.
`FIG. 7 illustrates an exemplary set of router throughput
`statistics resulting from the AFFC method of the invention
`being applied at a bottleneck node to the flows listed in FIG.
`6.
`
`FIG. 8 illustrates the dropping of packets from a queue in
`accordance with the invention.
`FIG. 9 illustrates an early traffic regulation method of the
`invention.
`FIGS. lOA and 10B illustrate early traffic regulation
`modules implemented in accordance with the invention.
`FIGS. 11 and 12 illustrate signaling between various
`nodes performed in accordance with the invention.
`
`DETAILED DESCRIPTION
`
`3
`inactive. However, when congestion is detected or a control
`message is received from another network node as part of
`the ETR method of the invention, the forced data flow
`reduction functionality in a node is activated. An ETR
`message triggering activation of the buffer manager and 5
`packet scheduler functionality may be received from, e.g., a
`downstream node confronting a potential collapse due to
`congestion.
`The dynamic buffer manager module 224 of the invention
`determines packet dropping rates to be applied to different
`data flows, e.g., those flows identified as being allowable but
`aggressive. The packet scheduler module 226 determines
`current packet forwarding rates, e.g., flow rates.
`During periods of congestion during which the forced 15
`data flow reduction is applied, incoming data flows are
`processed based on their traffic types, elastic traffic and best
`effort traffic. Elastic traffic, which is not responsive to
`congestion signaling, e.g., ECN (Explicit Congestion Noti(cid:173)
`fication) or packet dropping, is considered malicious and 20
`dropped.
`Elastic traffic that is responsive to congestion signals is
`considered allowable.
`For both elastic traffic and best-effort traffic, allowable 25
`traffic flows are determined to be aggressive if the flow rate
`of the allowable flow exceeds a corresponding baseline flow
`rate. Allowable non aggressive flows, e.g., flows having a
`flow rate equal to or lower than a corresponding baseline
`flow rate are forwarded without being subject to flow rate 30
`reduction. Allowable flows that are found to be aggressive,
`are subject to forced reductions in their flow rates during
`periods of congestion. The applied flow rate reduction may,
`e.g., reduce the flow rate of an aggressive flow, to or below
`the corresponding flow rate baseline.
`To support different packet drop rates for each allowable
`aggressive flow, packets from different allowable aggressive
`flows are stored in different packet forwarding queues. e.g.,
`one per allowable aggressive flow. In some embodiments,
`e.g., where sufficient memory is not available to support one 40
`queue per flow, a group of flows (e.g. from the same domain)
`may be processed per queue.
`The dynamic buffer manager module 224 of the invention
`determines packet dropping rates to be applied to different
`data flows, e.g., those flows identified as being allowable but
`aggressive. The packet scheduler module 226 determines
`current packet forwarding rates, e.g., flow rates. As men(cid:173)
`tioned above, the current flow rates are compared to the
`baseline flow rates and packets are dropped, e.g., when the
`current flow rate exceeds the baseline flow rate. Accord-
`ingly, incoming flows are subject to different reductions in
`their flow rates as a function of their normal baselines and
`their current arrival rates. In the case of malicious traffic
`flows, such forced data rate reductions may be interpreted as
`punishing of the malicious flows.
`ETR is a mechanism by which congestion control, and
`forced data rate reductions can be triggered in nodes
`upstream of a bottleneck node where the congestion occurs.
`ETR messages are used to activate flow reduction in the
`upstream nodes. Thus ETR offers protection for downstream
`nodes facing potential collapse due to congestion by reduc(cid:173)
`ing the flow of traffic directed to the node suffering from
`congestion.
`Numerous additional features and advantages of the 65
`invention are discussed in the detailed description which
`follows.
`
`50
`
`The present invention is directed to congestion control
`35 methods and apparatus. The methods and apparatus of the
`present invention are well suited for defending against
`network Denial-of-Service (N-DoS) attacks.
`FIG. 1 illustrates a communications system 100 imple(cid:173)
`mented in accordance with the present invention. The sys(cid:173)
`tem 100 comprises a plurality of sources 102, 104, 106, an
`internet 108 and a plurality of destination nodes 110, 112,
`114. The internet 108 may be a corporate internet or the
`world wide Internet. The internet 108 comprises a plurality
`ofnodes Rl through RlO 116, 118, 120, 122, 124, 126, 127,
`45 128, 130, 132 connected together as shown in FIG. 1 by the
`use of solid lines. Each of the nodes may be, e.g., a router
`or a switch. Arrows are used in FIG. 1 to indicate the flow
`of packets, e.g., between source devices Sl, S2, ... , SN,
`102, 104, 106 and destination device 112. While FIG. 1
`shows flows of packets to destination device D2 112 from
`sources Sl, S2, ... , SN, 102, 104, 106 the communications
`paths in the system 100 between the routers and devices are
`bi-directional allowing for responses, e.g., packets and mes(cid:173)
`sages, to be transmitted in the reverse direction as well. In
`55 the FIG. 1 embodiment source Sl 102 is coupled to the
`internet 108 by router Rl 116. In addition, source S2 is
`coupled to the internet 108 by router R4 122, while source
`SN 106 is coupled to the internet 108 by router RS 128.
`Router R7127 couples each of the three destination devices,
`60 Dl 110, D2 112, and D3 114, to the internet 108. As a result
`packets from any one of the sources 102, 104, 106 will pass
`through router R7 prior to reaching one of the destination
`devices 110, 112, 114.
`Since traffic directed to a destination device, e.g., device
`D2 112, will pass through the router R 7 127 regardless of the
`source of the traffic, router R7 127 represents a potential
`congestion point. For purposes of explaining the invention,
`
`
`
`US 7,295,516 Bl
`
`5
`
`5
`router R7 127 will be referred to as a "bottleneck" node
`since it is the point in system 100 where traffic bottlenecks
`may occur when excessive amounts of traffic are directed to
`one of the destination devices Dl, D2, D3 110, 112, 114.
`Relative to the bottleneck node 127, system elements, e.g.,
`routers and sources located to the left of bottleneck node
`127, are upstream nodes. System elements, e.g., devices Dl,
`D2, D3 110, 112, 114 to the right of the bottleneck node 127,
`are downstream nodes since they follow bottleneck node
`127 in terms of the exemplary traffic flows shown in FIG. 1. 10
`A flooding N-DoS attack works by transmitting a large
`amount of traffic from one or more sources to a particular
`destination, e.g., a web page server, which is the target of the
`N-DoS attack. For purposes of explaining the invention,
`when discussing an exemplary N-DoS attack it will be
`assumed that destination device D2 112 is the target of the
`exemplary attack. The exemplary N-DoS attack will result in
`bottleneck node 127 being flooded with useless information,
`corresponding to malicious data flows associated with the
`N-DoS attack.
`FIG. 2 illustrates an exemplary router 200 implemented
`according to one embodiment of the present invention. The
`router 200 may be used as, any one of the routers shown in
`FIG. 1 including edge router 127 which serves for discussion
`purposes as the exemplary bottleneck node. Router 200
`comprises of a CPU 202, a packet forwarding engine 204, an
`I/O interface 208 and a memory 210. These elements are
`coupled together by bus 206.
`The CPU 202 controls operation of the router 200 under
`direction of various routines stored in memory 210. The 30
`packet forwarding engine 204 is responsible for controlling
`the forwarding of packets under direction of various routines
`executed by the CPU 202. As part of the forwarding process
`packet forwarding engine 204 may store received packets
`corresponding to different flows and/or classes in different 35
`queues. In accordance with the congestion control mecha(cid:173)
`nisms of the present invention some received packets may
`be dropped by the packet forwarding engine, e.g., when the
`router 200 is incapable of forwarding packets at the rate at
`which they are received. The I/O interface 208 couples the 40
`router to other routers and/or host devices, e.g., source
`and/or destination devices. Thus, via I/O interface 208 the
`router 200 receives and transmits packets.
`Memory 210 includes a traffic monitoring routine 216,
`traffic classifier 218, forwarding and flow control routine 45
`220, traffic baseline generating module 222, dynamic buffer
`manage module 224, packet schedule module 226, early
`traffic regulator (ETR) module 228, traffic statistics 230,
`traffic baselines 232, a Recycling table 214, and a plurality
`of class based packet queues 234. The traffic statistics 230 50
`include current traffic statistics 231 and long term, e.g.,
`weekly traffic statistics 233. The various modules 222, 224,
`226, 228 may be implemented as, e.g., software routines.
`Alternatively, the modules could be implemented in hard(cid:173)
`ware, e.g., in the router 200, to enhance processing speed. 55
`The traffic monitoring routine 216 monitors to detect
`when the rate at which packets are received exceeds the
`maximum forwarding packet rate of the router 200 for a
`period of time corresponding to the buffering capacity of the
`router 200. This condition corresponds to saturation at the 60
`router 200 necessitating the dropping of some received
`packets. The traffic monitoring routine 216 notifies the
`forwarding and flow control routine 220 when saturation
`occurs and the length of the period of saturation.
`The traffic classifier 218 is used to classify packets into 65
`different classes and/or flows of traffic based on such factors
`as source address, destination address, protocol type, and
`
`6
`application type. The application type is determined from
`the port number or message type information included in a
`packet. The level, e.g., resolution, of traffic classification
`applied by the classifier 218 may depend on the application
`for which the classifier is being used. The traffic classifier
`can be called by the traffic baseline generating module 222
`and/or the forwarding and flow control routine 220 during
`normal operation.
`Forwarding and flow control routine 220 is responsible
`for controlling the forwarding and flow control of packets in
`accordance with the present invention. The forwarding and
`flow control routine 220 is responsible for activating the
`dynamic buffer manager module 224, packet scheduler
`15 module 226 and early traffic regulator module 228 used to
`implemented forced reductions in flow data rates in accor(cid:173)
`dance with the present invention when the router 200 is
`saturated by packet traffic, e.g., for a preselected period of
`time. By limiting implementation of all or some of the flow
`20 reduction features of the present invention until saturation of
`a node has occurred for a period of time, application of the
`anti-flooding flow reduction techniques can be limited to
`cases where flooding is likely to be occurring or to cases
`where a traffic collapse at the node is likely to occur if steps
`25 are not taken to avoid the collapse. In addition, false alarms
`of which can be induced by occasional short-term traffic
`spikes can be reduced or eliminated.
`Traffic baseline generating module 222 operates i