I 1111111111111111 11111 111111111111111 IIIII IIIII IIIII IIIII 1111111111 11111111
`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
`
`Cloudflare - Exhibit 1008, page 1
`
`

`

`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
`
`Cloudflare - Exhibit 1008, page 2
`
`

`

`

`

`

`

`

`

`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--, = "'""'
`
`Cloudflare - Exhibit 1008, page 6
`
`

`

`

`

`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
`
`Cloudflare - Exhibit 1008, page 8
`
`

`

`

`

`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
`
`Cloudflare - Exhibit 1008, page 10
`
`

`

`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
`
`Cloudflare - Exhibit 1008, page 11
`
`

`

`

`

`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
`
`Cloudflare - Exhibit 1008, page 13
`
`

`

`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,
`
`Cloudflare - Exhibit 1008, page 14
`
`

`

`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 in par(cid:173)
`allel with the forwarding and flow control routine 220 to
`generate traffic baselines for various traffic flows at prese(cid:173)
`lected intervals. As will be discussed below, the traffic
`baselines 232 are generated from the traffic statistics 230
`which are produced over an extend period of time, e.g., days
`or weeks. Traffic baselines 232 are stored in memory for use
`in forced traffic flow reduction operations implemented in
`the router 200 in accordance with the invention.
`The dynamic buffer manager module 224 and packet
`scheduler module 226 implement in accordance with the
`invention are responsible for performing forced reductions
`in the rate of packet flows through the router 200. The
`amount of the flow reduction applied to individual flows or
`flow groups is determined as a function of the traffic
`baselines 232.
`Early traffic regulator module 228 is used to send early
`traffic regulation (ETR) signals, e.g., messages, to upstream
`nodes to trigger the congestion control and forced packet
`flow reductions techniques of the present invention to be
`implemented in the upstream node. In the case of a node
`receiving an ETR message, the ETR module 228 is respon(cid:173)
`sible for responding to the ETR message by implementing
`forced packet flow rate reductions. In some embodiments
`the forced packet flow rate reductions in response to an ETR
`message are on flows directed to the node which was the
`source of the ETR message while in other embodiments, the
`forced packet flow rate reductions are limited to flows
`destined for target IP address( es) identified in the received
`ETR message.
`An exemplary traffic baseline generating routine 300,
`which can be used as the traffic base line generating module
`222, is shown in FIG. 3.
`Traffic baseline generation involves removing spikes in a
`time window corresponding to a daily period of time and
`removing short-term abnormal traffic patterns which may be
`encountered over a period of weeks. Furthermore, depend(cid:173)
`ing on the implementation, traffic classification for baseline
`generation purposes need not be limited to simply protocol
`
`Cloudflare - Exhibit 1008, page 15
`
`

`

`US 7,295,516 Bl
`
`5
`
`7
`types and IP addresses but may also be based on the
`application type and/or port numbers associated with pack(cid:173)
`ets.
`The routine 300 starts in step 301 wherein the routine is
`executed by the CPU 202. Then in step 302, packets 325 for
`a current time period li.T are received. The time period li.T
`may be fixed or any desired length depending on the
`environment and specific traffic patterns and/or day and time
`of week for which the flow rate baseline is being generated.
`The packets 325 correspond
`to multiple destination 10
`addresses and sources. Accordingly, many flows of traffic
`are represented in the received packet stream 325. Each
`packet
`includes source
`IP addresses, destination IP
`addresses, protocol type information, port number and/or
`message type information. As discussed above, port number 15
`and/or message type information can be used to identify an
`application to which the packet corresponds. li.T in the
`exemplary embodiment is a time segment, e.g., 30 minute
`time segment, from a 24 hour time period. ti. T can be either
`constant through the day, e.g., 30 minutes, or vary at 20
`different time of the day, e.g., 120 minutes from 2 A.M. to
`4 A.M. vs. 30 minutes for other busier times of the day.
`Holidays may be treated as special cases for purposes of data
`collection and baseline generation if desired, e.g., due to
`very different traffic patterns on those days.
`In step 303, each packet is classified based on destination
`address, protocol type and application type. The resulting
`sets of data correspond to individual classes of traffic.
`Some exemplary protocol types are TCP and UDP, while
`some exemplary applications that use TCP are web traffic 30
`and FTP traffic. An exemplary application that uses UDP is
`Echo traffic. Accordingly, the first exemplary traffic class
`might include TCP packets for a