Method and system for managing of denial of service attacks using bandwidth allocation technology

[0001] The present invention is related to co-pending U.S. patent application Ser. No. ______ and entitled METHOD AND SYSTEM FOR PRIORITY ENFORCEMENT WITH FLOW CONTROL Docket No. RPS92001017 1 US1 and assigned to the assignee of the present invention. The present invention is also related to co-pending U.S. patent application Ser. No. ______ RPS920020028US1 and entitled DETECTING RANDOMNESS IN COMPUTER NETWORK TRAFFIC and assigned to the assignee of the present invention.

[0002] The present invention relates to computer systems, and more particularly to a method and system for managing attacks such as denial of service (DoS) attacks.

[0003] Driven by increasing usage of a variety of network applications, such as those involving the Internet, computer networks are of increasing interest. The Internet can be regarded as a collection of interconnected networks, also called autonomous systems. Autonomous systems are administrated under the same authority or under different authorities. Autonomous systems administered under the same authority are also referred to as clouds. In order to couple portions of a network together, to couple networks, or at the edge of an autonomous system, switches are often used. For example, FIG. 1 depicts a high-level block diagram of a switch 10 which can be used. This invention pertains to a switch 10 that includes a switch fabric 24 coupled with blades 7, 8 and 9. Each blade 7, 8 and 9 is generally a circuit board and includes at least a network processor 2 coupled with ports 4. The term network processor is interpreted broadly to include any packet-processing device in which packet recognition and flow control are programmable. Thus, the ports 4 are coupled with links that convey packets to or from other network nodes or hosts (not shown). The blades 7, 8 and 9 can provide traffic to the switch fabric 24 and accept traffic from the switch fabric 24. Thus, any host connected with one of the blades 7, 8 or 9 can communicate with another host connected to another blade 7, 8 or 9 or connected to the same blade. Although depicted as including network processors 2, in lieu of network processors 2, the switch 10 could include an equivalent level of programmability provided using another mechanism.

[0004] FIG. 2A depicts another simplified block diagram of the switch 10, illustrating some of the functions performed by network processors. The switch 10 couples links to other nodes or hosts (not shown) connected with ports A 12 with those links to other nodes or hosts (not shown) connected with ports B 36. The switch 10 performs various functions including classification of data packets provided to the switch 10, transmission of data packets across the switch 10 and reassembly of information into packets. These functions are provided by the classifier 18, the switch fabric 24 and the reassembler 30, respectively. The classifier 18 classifies packets which are provided to it and breaks each packet up into convenient-sized portions, which will be termed cells. The switch fabric 24 is a matrix of connections through which the cells are transmitted on their way through the switch 10. The reassembler 30 reassembles the cells into the appropriate packets. The packets can then be provided to the appropriate port of the ports B 36, and output through links to the next hop or final destination nodes or hosts. The classifier 18 may be part of one network processor 1, while the reassembler 30 may be part of another network processor 5. The portions of the network processor 1 and the network processor 5 depicted perform functions for traffic traveling from ports A 12 and to ports B 36, respectively. However, the network processors 1 and 5 also perform functions for traffic traveling from ports B 36 and to ports A 12, respectively. Thus, each network processor 1 and 5 can perform classification and reassembly functions. Furthermore, each network processor 1 and 5 can be a network processor 2 shown in FIG. 1.

[0005] Referring back to FIG. 2A, due to bottlenecks in transferring traffic across the switch 10, data packets may be required to wait prior to execution of the classification, transmission and reassembly functions. As a result, queues 16, 22, 28 and 34 may be provided. Coupled to the queues 16, 22, 28 and 34 are enqueuing mechanisms 14, 20, 26 and 32. The enqueuing mechanisms 14, 20, 26 and 32 place the packets or cells into the corresponding queues 16, 22, 28 and 34. Although the queues 16, 22, 28 and 34 are depicted separately, one of ordinary skill in the art will readily realize that some or all of the queues 16, 22, 28 and 34 may be part of the same shared physical memory resource.

[0006] Those skilled in the art will understand that such queues can represent processing bottlenecks or points of congestion. In particular, lengthy queuing delays diminish or cancel the value of packets that are eventually processed. Therefore proper operation of a network can include the purposeful and proactive discarding of some packets during instances of congestion by the enqueuing mechanisms 14 and 26.

[0007] FIG. 2B depicts further details of mechanisms in one such switch 10. Many of the components of the switch 10 are analogous to components of the switch 10. Such components are, therefore, labeled similarly. For example, the ports A 12 in the switch 10 correspond to the ports A 12 in the switch 10. In the switch 10, the queue A 16 and the queue A 22 share a single memory resource 19. Similarly, the queue 28 and the queue 34 are part of another single memory resource 31. Thus, in the switch 10, the queues 16, 22, 28 and 34 are logical queues partitioned from the memory resources 19 and 31.

[0008] FIG. 3 depicts various clouds 50, 52, 54, 56, 60, 62, 64, and 70 coupled via a cloud with high-bandwidth links and fast routers, typically referred to as backbone 80. Some switches 10 and/or 10 can reside at the boundaries of the clouds 50, 52, 54, 60, 62, 64 and 70 and the backbone 80 at which connections are made. For example, the cloud 50 typically includes one or more switches 10/10 at the connections made to clouds 52, 54, and 56. Furthermore, note that the clouds 50, 52, 54, 56, 60, 62, 64 and 70 can be viewed hierarchically depending upon their connection to the backbone 80 and the number of the remaining clouds 50, 52, 54, 56, 60, 62, 64 and 70 to which they are connected. For example, the cloud 56, which is only connected to the cloud 50, may be small and have a relatively peripheral connection to the backbone 80. The cloud 54 may be larger and higher in the hierarchy, serving as a connection point to the backbone 80 and other clouds for the clouds 50, 52, and 56.

[0009] Traffic, including data packets and administrative packets (also called control packets), traverses the clouds 50, 52, 54, 56, 60, 62, 64, and 70 and the backbone 80 at least in part by traveling through some switches 10/10. The switches 10/10 may provide a gateway to the Internet or other clouds 50, 52, 55, 56, 60, 62, 64, and 70. In addition, the switches 10/10 may also be used to provide customers with different services based, for example, on the price paid by a consumer for service. A consumer may wish to pay more to ensure a faster response or to ensure that the traffic for the customer will be transmitted even when traffic for other customers is dropped due to congestion. Thus, the concept of differentiated services has been developed. Differentiated services can provide different levels of service, for different customers, or different flows of traffic through the network.

[0010] Differentiated Services (DiffServ) is an established Internet Engineering Task Force (IETF) standard for providing differentiated services (see IETF RFC 2474 and related RFCs). The DiffServ architecture recognizes the importance of clouds for providing service guarantees in the Internet and is concerned with intra-cloud service levels. Appropriate service level agreements are assumed between clouds. At the edge of a cloud, incoming traffic is mapped into a limited number of traffic behavior aggregates. A behavior aggregate flow can be viewed at each point of potential congestion as the aggregate of all traffic of the same class. A class can mean a common technical requirement, such as very low latency, a common economic value, or any combination of such concepts. Furthermore, some traffic of sufficient value can be organized in a pipeline from one edge of a cloud or combination of clouds to another edge of a cloud or combination of clouds. Potentially, one behavior aggregate flow could have its own pipeline, but in general the local confluence of all traffic in one class or behavior aggregate flow at one point of congestion determines the treatment of packets in the class without regard to details of session membership.

[0011] Thus, within each behavior aggregate flow at each point of potential congestion there could be packets from one, a few, or many sessions between individual hosts. However, DiffServ is unconcerned with session membership within a behavior aggregate flow. Instead, DiffServ is concerned with the differentiated treatment of the behavior aggregate flows inside a cloud. According to DiffServ, excess bandwidth is to be allocated fairly between behavior aggregate flows. Furthermore, DiffServ defines fairness by providing criteria for measuring the level of service provided to each behavior aggregate flow. For example, to provide differentiated services, aggregate flows could be marked red, yellow, or green. When insufficient bandwidth exists to support the current flows in one or more of the behavior aggregate flows, packets in pipelines marked red could be discarded to a greater degree than packets in behavior aggregate flows marked yellow. Similarly, packets in behavior aggregate flows marked yellow could be discarded to a greater degree than packets in behavior aggregate flows marked green. Thus, three levels of service could be provided.

[0012] Traffic having different levels of services may travel through the clouds 50, 52, 54, 56, 60, 62, 64, and 70. However, one of ordinary skill in the art will readily realize that the clouds 50, 52, 54, 56, 60, 62, 64, and 70 and the systems within the clouds 50, 52, 54, 56, 60, 62, 64, and 70 are vulnerable to attack. In particular, individuals can generate malicious traffic through the clouds 50, 52, 54, 56, 60, 62, 64, and 70 which would adversely affect the performance of another system within the same cloud or system(s) in other clouds. For example, an individual with connectivity to one of the clouds, such as the cloud 50, could initiate an attack, such as a denial of service (DoS) attack, on a node or nodes in another cloud such as the cloud 70. For example, system(s) in the cloud 50 could flood system(s) in the cloud 70 with administrative packets such as SYN, FIN, RST packets in the protocol TCP; any ICMP packets; or analogous administrative, control, or signaling packets in any other protocols such as in SCTP. This DoS attack could escape the notice of the administrator of the corresponding autonomous system within the cloud 50. The DoS attack could adversely affect the performance of systems within the cloud 70, result in a significant loss of resources, and require a significant investment of resources for system recovery. In addition, the administrator of the cloud 50 could be financially liable for damage done to the systems of the cloud 70. Consequently, it is desirable to manage DoS attacks to limit their adverse effects.

[0013] FIG. 4 depicts a conventional method 90 for managing DoS attacks in switches such as the switches 10/10 and clouds such as the clouds 50, 52, 54, 56, 60, 62, 64, and 70. It is determined whether the rate at which administrative packets of a certain type traverse the switch 10/10 exceeds a particular maximum level, via step 92. If not, then step 92 is periodically repeated. If so, then a sufficient number of administrative packets are dropped so that the traffic in administrative packets traversing the switch 10/10 is suppressed to the maximum level, via step 94.

[0014] Although the conventional method 90 functions, one of ordinary skill in the art will readily recognize that the conventional method 90 is a rough, simplistic mechanism for managing malicious traffic through the clouds 50, 52, 54, 56, 60, 62, 64, and 70. Only a comparison of an observed rate to a maximum bandwidth indicates that any action should be taken to manage attacks. In addition, the conventional method 90 merely prevents the administrative packets from exceeding the maximum level. Thus, further improvement in the performance of the switch 10/10 is desirable.

[0015] Accordingly, what is needed is a system and method for providing better management of denial of service attacks. The present invention addresses such a need.

[0016] The present invention provides a method and system for managing attacks in a computer system. The computer system is used in sending, receiving, or sending and receiving a plurality of packets, which include a plurality of administrative packets. The method and system include determining whether congestion of administrative packets, as defined in the present application, exists. Congestion of the administrative packets indicates that a potential attack exists. The method and system also comprise discarding a portion of the plurality of administrative packets if it is declared that the congestion of the administrative packets exists. The portion of the plurality of packets is sufficient to ensure that a remaining portion of the plurality of packets transmitted is not more than a maximum administrative packet bandwidth and, if sufficient offered traffic load exists, not less than a minimum administrative packet bandwidth.

[0017] According to the system and method disclosed herein, the present invention allows denial of service attacks to be detected and accounted for gracefully, allowing for high utilization, low latency, fast convergence to a desired allocation and fair allocation in that excess bandwidth is allocated fairly among different pipes.

[0018] FIG. 1 is a high-level block diagram of a switch.

[0019] FIG. 2A is a simplified block diagram of a switch.

[0020] FIG. 2B is a simplified block diagram of another switch.

[0021] FIG. 3 is a simplified block diagram of a number of interconnected clouds.

[0022] FIG. 4 is a flow chart depicting a conventional method for managing attacks such as DoS attacks using a switch.

[0023] FIG. 5 is a high-level flow chart depicting one embodiment of a method in accordance with the present invention for managing DoS attacks, preferably using a switch.

[0024] FIG. 6 is a flow chart depicting one embodiment of a method in accordance with the present invention for managing DoS attacks, preferably using a switch.

[0025] FIG. 7 is a more detailed flow chart of one embodiment of a method in accordance with the present invention for managing DoS attacks, preferably using a switch.

[0026] FIG. 8 is a more detailed flow chart of a second embodiment of a method in accordance with the present invention for managing DoS attacks, preferably using a switch.

[0027] The present invention relates to an improvement in computer systems and computer networks. The following description is presented to enable one of ordinary skill in the art to make and use the invention and is provided in the context of a patent application and its requirements. Various modifications to the preferred embodiment will be readily apparent to those skilled in the art and the generic principles herein may be applied to other embodiments. Thus, the present invention is not intended to be limited to the embodiment shown, but is to be accorded the widest scope consistent with the principles and features described herein.

[0028] The present invention provides a method and system for managing attacks in a computer system. The computer system is used in sending, receiving, or sending and receiving a plurality of packets, which include a plurality of administrative packets. The method and system comprise determining whether a congestion of the administrative packets exists. Congestion of the administrative packets indicates that a potential attack exists. The method and system also comprise discarding a portion of the plurality of administrative packets if it is declared that congestion exists. The present invention includes several definitions of congestion, and the different definitions can be used individually or in combinations. The portion of the plurality of packets is sufficient to ensure that a remaining portion of the plurality of packets transmitted is not more than a maximum administrative packet bandwidth and, if sufficient offered traffic exists, not less than a minimum administrative packet bandwidth.

[0029] According to the system and method disclosed herein, the present invention allows denial of service attacks to be detected and managed gracefully, and at the same time assuring high utilization, low latency, fast convergence to a desired allocation and fair allocation in that excess bandwidth is allocated at each point of potential congestion predictably and fairly among different behavior aggregate flows or pipes.

[0030] The present invention will be described in terms of particular computer systems, such as switches, network processors, gateways, autonomous systems, and clouds. However, one of ordinary skill in the art will readily recognize that this method and system will operate effectively for other and/or additional computer systems. The present invention is also described in the context of switches including network processors. One of ordinary skill in the art will recognize that the present invention is applicable to switches not including network processors, but which have an analogous level of programmability. The present invention is also described in the context of denial of service attacks. However, one of ordinary skill in the art will also readily recognize that the method and system operate effectively for other types of attacks involving anomalously large flow rates of certain types of packets. The present invention is described in the context of switches located at the edges of clouds. However, one of ordinary skill in the art will readily recognize that the computer systems could be located elsewhere. In addition, one of ordinary skill in the art will readily recognize that the present invention could be employed only at selected clouds while retaining a high degree of effectiveness.

[0031] To more particularly illustrate the method and system in accordance with the present invention, refer now to FIG. 5, depicting one embodiment of a method 100 for managing attacks, such as a denial of service attacks, in a computer system. The method 100 is preferably accomplished using technology described in co-pending U.S. patent application Ser. No. ______ and entitled METHOD AND SYSTEM FOR PRIORITY ENFORCEMENT WITH FLOW CONTROL and assigned to the assignee of the present invention. Applicants hereby incorporate by reference the above-mentioned co-pending U.S. patent application. The method 100 can be used with the switch 10 or 10 shown in FIGS. 1, 2A and 2B. Thus, the method 100 can be carried out in a switch 10 having multiple blades 7, 8 and 9 and multiple ports on each blade 7, 8 or 9. In addition, for clarity, the method 100 will be described in conjunction with the enqueuing mechanism 20 and queue 22 of switch 10 depicted in FIG. 2A. However, the method 100 can be used with the enqueuing mechanism 14 and queue 16 of switch 10, with the enqueuing mechanism 26 and queue 28 of switch 10, or with other switches (not shown) having different and/or additional components.

[0032] The method 100 is preferably repeated at a constant frequency. It is also preferably used to manage attacks at when traffic enters or leaves a cloud 50, 52, 54, 56, 60, 62, 64, or 70. Thus, the switch 10 is preferably located at the edge of a cloud 50, 52, 54, 56, 60, 62, 64, or 70 and provides traffic to or from an external destination or source, respectively. The method 100 will, therefore, be described in the context of the cloud 54 receiving or sending packets. However, nothing prevents the method 100 from being used in another portion of the cloud 50, 52, 54, 56, 60, 62, 64, or 70, between individual hosts, between networks, and/or between autonomous systems in a cloud 50, 52, 54, 56, 60, 62, 64, or 70. Moreover, the method 100 is preferably performed in addition to differentiated services being performed. Consequently, in the absence of action being taken, as described below, excess bandwidth is preferably fairly allocated among different behavior aggregate flows at points of potential congestion.

[0033] Referring to FIGS. 2A and 5, the method 100 preferably commences after the network administrator for the cloud 54, or other authorized user, has set a minimum bandwidth guarantee and maximum bandwidth limit for administrative packets. Note that the minimum bandwidth guarantee could be zero. Alternatively, the minimum bandwidth guarantee and the maximum bandwidth limit could be equal. In a preferred embodiment, the minimum bandwidth guarantee and the maximum bandwidth limit are for all administrative packets such as all SYN, SYN/ACK, RST, FIN packets in TCP or all ICMP packets. However, in an alternate embodiment, there can be different minimum and maximum bandwidths assigned for different types of administrative packets. Thus, for example, RST packets may be treated differently than SYN packets.

[0034] Whether congestion exists for the administrative packets is determined via step 102. In a preferred embodiment, step 102 is performed by the enqueuing mechanism 20 for the queue 22. Step 102 preferably includes determining whether some portion of the administrative packets in the aggregate flow meets or exceeds the corresponding maximum bandwidth limit. For example, if the maximum bandwidth limit described above is for all administrative packets, step 102 preferably determines whether all of the administrative packets flowing through the switch 10 would exceed the corresponding maximum bandwidth limit. In another embodiment, statistics for the queue 22 can be used to determine whether congestion exists in step 122. For example, the occupancy of the queue, the rate of change of the occupancy of the queue, or other statistics could be used as a measure of congestion of administrative packets in step 102. Furthermore, other measures of congestions, such as suspicious randomness (described below), can also be used. In a preferred embodiment, a simple OR of all selected conditions for congestion could be used. Alternative embodiments could use AND and OR operations on combinations of such signals. For example, in yet another embodiment, statistics for the queue 22 can be combined with determination of suspicious randomness. The occupancy of the queue 22, the rate of change of the occupancy of the queue 22, or other statistics could be used as a measure of congestion that, when combined with suspicious randomness, would lead to excessive randomness being determined to exist.

[0035] If it is determined that congestion exists, preferably by any suitable combination of AND or OR operations applied to congestion signals, then a portion of the plurality of administrative packets is discarded, via step 104. The portion of the plurality of packets discarded in step 104 is sufficient to ensure that a remaining portion of the administrative packets transmitted is not more than the maximum packet bandwidth limit and, provided sufficient offered traffic exists, not less than the minimum bandwidth guarantee. Sufficient offered traffic exists when the traffic of administrative packets entering the enqueuing mechanism 20 is at least the minimum bandwidth guarantee. If the maximum bandwidth limit is exceeded, then the portion of administrative packets discarded preferably rapidly increases and drives the rate of transmitted administrative packets in the pipeline to at or below the maximum bandwidth limit. In a preferred embodiment, if congestion signal continuously is true, then the portion of administrative packets discarded rapidly increases and drives the rate of transmitted administrative packets in the pipeline to the minimum bandwidth guarantee. For example, the portion of administrative packets transmitted may be exponential decreased. In other words, the portion of the administrative packets transmitted is repeatedly multiplied by a positive number less than one, such as 31/32, at every instance of a certain time interval to rapidly drive the administrative traffic to the minimum bandwidth. However, in an alternate embodiment, a different number of administrative packets are discarded in step 104. In addition, the rates of certain administrative packets discarded in step 104 preferably correspond to the administratively configured minimum bandwidth guarantee and maximum bandwidth limit. For example, if the minimum bandwidth guarantee and maximum bandwidth limit described above are for all administrative packets, step 104 preferably discards a portion of all administrative packets. In addition, step 104 is preferably performed by the enqueuing mechanism 20. As a result, the discarded administrative packets preferably do not reach the corresponding queue 22. The discard mechanism periodically returns to 102 to refresh the discard rate.

[0036] If it is determined that congestion does not exist for the administrative packets and if there is excess bandwidth as defined above, then a portion of the excess bandwidth may be allocated to the administrative packets, via step 106. For example, the fraction of transmitted administrative packets may be increased linearly until some limit is reached. Note that step 106 could be implemented in accordance with the method and apparatus described in the above-identified co-pending U.S. patent application entitled METHOD AND SYSTEM FOR PRIORITY ENFORCEMENT WITH FLOW CONTROL Docket No. RPS920010171 US 1. Step 102 is then returned to.

[0037] Because congestion of administrative packets is used as a trigger for discarding a greater portion of the administrative packets traveling through the switch 10, the method 100 can manage attacks, such as DoS attacks. Furthermore, because of the use of minimum and maximum administrative packet bandwidth values, the method 100 can more effectively protect against attacks, such as DoS attacks, by rapidly but gracefully reducing the number of administrative packets flowing through the switch while improving performance of the switch 10. For example, excess bandwidth is still allocated in a fair manner, and the fraction of administrative packets discarded may then be varied to ensure that an appropriate amount of suspicious traffic is discarded.

[0038] FIG. 6 depicts one embodiment of a method 110 for managing attacks, such as a denial of service attacks, in a computer system. The method 110 is preferably one implementation of the method 100. The method 110 is preferably accomplished using technology described in the above-identified co-pending U.S. patent application. The method 110 can be used with the switch 10 or 10 shown in FIGS. 1, 2A and 2B. Thus, the method 110 can be carried out in a switch 10 having multiple blades 7, 8 and 9 and multiple ports on each blade 7, 8 or 9. In addition, for clarity, the method 110 will be described in conjunction with the enqueuing mechanism 20 and queue 22 of switch 10 depicted in FIG. 2A. However, the method 110 can be used with the enqueuing mechanism 14 and queue 16 of switch 10, with the enqueuing mechanism 26 and queue 28 of switch 10, or with other switches (not shown) having different and/or additional components.

[0039] The method 110 is preferably repeated at a constant frequency. It is also preferably used to manage attacks at when traffic enters or leaves a cloud 50, 52, 54, 56, 60, 62, 64, or 70. Thus, the switch 10 is preferably located at the edge of a cloud 50, 52, 54, 56, 60, 62, 64, or 70 and provides traffic to or from an external destination or source, respectively. The method 110 will, therefore, be described in the context of the cloud 54 receiving or sending packets. However, nothing prevents the method 110 from being used in another portion of the cloud 50, 52, 54, 56, 60, 62, 64, or 70, between individual hosts, between networks, and/or between autonomous systems in a cloud 50, 52, 54, 56, 60, 62, 64, or 70. Moreover, the method 110 is preferably performed in addition to differentiated services being performed. Consequently, in the absence of action being taken, as described below, excess bandwidth is preferably fairly allocated among different behavior aggregate flows at points of potential congestion.

[0040] Referring to FIGS. 2A and 6, the method 110 preferably commences after the network administrator for the cloud 54, or other authorized user, has set a minimum bandwidth guarantee and maximum bandwidth limit for administrative packets. Note that the minimum bandwidth could be zero. Alternatively, the minimum bandwidth guarantee and maximum bandwidth limit could be equal. In a preferred embodiment, the minimum bandwidth guarantee and maximum bandwidth limit are for all administrative packets such as all SYN, SYN/ACK, RST, FIN packets in TCP or all ICMP packets. However, in an alternate embodiment, there can be different minimum and maximum bandwidth values assigned for different types of administrative packets. Thus, for example, RST packets may be treated differently than SYN packets.

[0041] Whether excessive rates of transmission of some type(s) of administrative packets exist is determined via step 112. Thus, step 112 is one method for determining whether congestion exists. In a preferred embodiment, step 112 is performed by the enqueuing mechanism 20 for the queue 22. Step 112 preferably includes determining whether some portion of the administrative packets in the aggregate flow meets or exceeds the corresponding maximum bandwidth limit. For example, if the maximum bandwidth limit described above is for all administrative packets, step 112 preferably determines whether all of the administrative packets flowing through the switch 10 would exceed the corresponding maximum bandwidth limit.

[0042] If it is determined that congestion exists because of excessive rates of transmission of administrative packets, then a portion of the plurality of administrative packets is discarded, via step 114. The portion of the plurality of packets discarded in step 114 is sufficient to ensure that a remaining portion of the administrative packets transmitted is not more than the maximum packet bandwidth limit and, provided sufficient offered traffic exists, not less than the minimum bandwidth guarantee. Thus, an increasing fraction of administrative packets are discarded in step 114 until and unless the minimum bandwidth guarantee is reached. In a preferred embodiment, if the maximum bandwidth limit is exceeded, then the portion of administrative packets discarded rapidly increases and drives the rate of transmitted administrative packets in the pipeline to at or below the maximum bandwidth limit. In a preferred embodiment, if congestion signal continuously is true, then the portion of administrative packets discarded rapidly increases and drives the rate of transmitted administrative packets in the pipeline to the minimum bandwidth guarantee. For example, the portion of administrative packets transmitted may be exponential decreased. In other words, the portion of administrative packets transmitted may be repeatedly multiplied by a positive number less than one, such as 31/32, at every instance of a certain time interval to rapidly drive the administrative traffic to the minimum bandwidth guarantee. However, in an alternate embodiment, a different number of administrative packets are discarded in step 114. In addition, the rates of certain administrative packets discarded in step 114 preferably correspond to the administratively configured minimum and maximum bandwidth values. For example, if the minimum bandwidth guarantee and maximum bandwidth limit described above are for all administrative packets, step 114 preferably discards a portion of all administrative packets. In addition, step 114 is preferably performed by the enqueuing mechanism 20. As a result, the discarded administrative packets preferably do not reach the corresponding queue 22. The discard mechanism periodically returns to 112 to refresh the discard rate.

[0043] If it is determined that congestion does not exist for the administrative packets and if there is excess bandwidth as defined above, then a preferably increasing fraction of the administrative packets is transmitted, via step 116. For example, the fraction of transmitted administrative packets may be increased linearly until some limit is reached. Note that step 116 could be implemented in accordance with the method and apparatus described in the above-identified co-pending U.S. patent application. Step 112 is then returned to.

[0044] Because congestion of administrative packets is used as a trigger for discarding a greater portion of the administrative packets traveling through the switch 10, the method 110 can manage attacks, such as DoS attacks. Furthermore, because of the use of minimum and maximum administrative packet bandwidth values, the method 110 can more effectively protect against attacks, such as DoS attacks, by rapidly but gracefully reducing the number of administrative packets flowing through the switch while improving performance of the switch 10. For example, excess bandwidth is still allocated in a fair manner, and the fraction of administrative packets discarded may then be varied to ensure that an appropriate amount of suspicious traffic is discarded.

[0045] FIG. 7 is a more detailed flow chart of one embodiment of a method 120 in accordance with the present invention for managing DoS attacks, preferably using a switch. The method 120 can be viewed as one implementation of the method 100. The method 120 is preferably accomplished using technology described in the above-identified co-pending U.S. patent application. The method 120 can be used with the switch 10 or 10 shown in FIGS. 1, 2A and 2B. Thus, the method 120 can be implemented in a switch 10 having multiple blades 7, 8 and 9 and multiple ports on each blade 7, 8 or 9. In addition, for clarity, the method 120 will be described in conjunction with the enqueuing mechanism 20 and queue 22 of switch 10 depicted in FIG. 2A. However, the method 120 can be used with other enqueuing mechanisms or switches (not shown) having different and/or additional components. The method 120 is also preferably used to manage attacks at when traffic enters or leaves a cloud 50, 52, 54, 56, 60, 62, 64, or 70. Thus, the switch 10 is preferably located at the edge of a cloud 50, 52, 54, 56, 60, 62, 64, or 70 and provides traffic to or from an external destination or source, respectively. The method 120 will, therefore, be described in the context of the cloud 54 receiving or sending packets. Moreover, the method 120 is preferably performed in addition to differentiated services being performed. Consequently, in the absence of action being taken, as described below, excess bandwidth is preferably allocated in a fair manner among different behavior aggregate flows at a point of potential congestion.

[0046] Referring to FIGS. 2A and 7, the method 120 preferably commences after the network administrator for the cloud 54, or other authorized user, has set a minimum bandwidth guarantee and maximum bandwidth limit for red packets in a particular behavior aggregate flow. Note that the minimum bandwidth guarantee could be zero. Alternatively, the minimum bandwidth guarantee and maximum bandwidth limit could be positive and equal. In a preferred embodiment, the minimum bandwidth guarantee and maximum bandwidth limit are for the red pipeline, discussed below.

[0047] Certain administrative packets are marked red before they enter the cloud 54 by a machine outside the cloud 54 or as they the cloud 54, via step 122. In one embodiment, all administrative packets are marked red in step 122. In an alternative embodiment, only certain administrative packets are marked red in step 122. In another alternative embodiment, certain administrative packets are marked red in step 122 when a certain tag in the packet header fields (e.g., the DiffServ code point header field) indicates that the packet should be marked red. In one embodiment, whether administrative packets are marked red and which administrative packets are marked red depends upon other factors. In one such alternate embodiment, the marking of administrative packets depends upon the flow of administrative packets through a token bucket mechanism. For example, an implementation of such mechanisms as described in IETF RFC 2697 and IETF RFC 2698 could be used. In such an embodiment, administrative packets can be marked based upon the committed information rate (CIR), and peak information rate (PIR), committed burst size (CBS), and peak burst size (PBS). The CIR and PIR, over a sufficiently long time interval, correspond roughly to the concepts of minimum bandwidth guarantee and maximum bandwidth limit. If a flow rate exceeds PIR for a sufficiently long time, many or most packets in the flow will be marked red in step 122. Otherwise, the administrative packets may be marked another color. To maintain order, the administrative packets are fed into one flow control mechanism with different probabilities of transmission into a common queue based upon color. The packets marked red have a lower probability of transmission into the common queue than yellow or green packets. In the embodiments described above, step 122 is preferably performed within the enqueuing mechanism 20.

[0048] It is determined whether an excessive transmission rate of the red, administrative exists, packets, via step 124. Thus, step 124 is one method for determining whether congestion exists. In a preferred embodiment, step 124 is performed by the enqueuing mechanism 20 for the queue 22. Step 124 preferably includes determining whether the red, administrative packet flow rate exceeds the corresponding maximum bandwidth limit.

[0049] If it is determined that an excessive transmission rate exists for the red pipeline, then a portion of the plurality of red packets is discarded, via step 126. The portion of the plurality of packets discarded in step 126 is after at most a brief time sufficient to ensure that a remaining portion of the red packets transmitted is not more than the maximum bandwidth limit. Preferably, step 126 discards an increasing fraction of the red packets unless and until the minimum bandwidth guarantee is reached. In a preferred embodiment, if congestion persists, then the increasing portion of red packets discarded rapidly drives the transmitted red packets to, but not below, the minimum bandwidth guarantee. For example, the portion of red packets transmitted may be exponentially decreased over certain time intervals to rapidly drive the red traffic in the pipeline to the minimum bandwidth guarantee. However, in an alternate embodiment, a different number of red packets are discarded in step 126. In addition, step 126 is preferably performed by the enqueuing mechanism 20. As a result, the discarded administrative packets preferably do not reach the corresponding queue 22. Step 124 is then returned to.

[0050] If it is determined that an excessive transmission rate does not exist for the red pipeline, which the red packets traverse, then, if there is excess bandwidth, a preferably increasing fraction of the red packets are transmitted, via step 128. For example, the bandwidth allocated to the red pipeline packets may be increased linearly until some limit is reached. The bandwidth allocated to red packets may be linearly increased until the excess bandwidth is small or zero. Note that step 128 may be optional. In a preferred embodiment, because the method 120 is assumed to be performed with differentiated services as a background, the excess bandwidth may still be allocated even in the absence of step 128. The allocation of excess bandwidth would then be performed by the mechanism that performs differentiated services, such as the method and apparatus described in the above-identified co-pending U.S. patent application. Step 124 is then returned to.

[0051] Because administrative packets are marked red and congestion of the red pipeline is used as a trigger for discarding a greater portion of the red packets traveling through the switch 10, the method 120 can manage attacks, such as DoS attacks. Furthermore, because of the use of minimum bandwidth guarantee and maximum bandwidth limit for the red pipeline, the method 120 can more effectively protect against attacks, such as DoS attacks, by rapidly reducing the number of administrative packets flowing through the switch while improving performance of the switch 10. For example, excess bandwidth is still allocated in a fair manner, and the fraction of administrative packets discarded may then be varied to ensure that an appropriate amount of suspicious traffic is discarded.

[0052] FIG. 8 is a more detailed flow chart of a second embodiment of a method 130 in accordance with the present invention for managing DoS attacks, preferably using a switch. The method 130 can be viewed as one implementation of the method 100. The method 130 is preferably accomplished using technology described in co-pending U.S. patent application Ser. No. ______ RPS920020028US1 and entitled DETECTING RANDOMNESS IN COMPUTER NETWORK TRAFFIC and assigned to the assignee of the present invention. The method 130 can be used with the switch 10 or 10 shown in FIGS. 1, 2A and 2B. Thus, the method 130 can be carried out in a switch 10 having multiple blades 7, 8 and 9 and multiple ports on each blade 7, 8 or 9. In addition, for clarity, the method 130 will be described in conjunction with the enqueuing mechanism 20 and queue 22 of switch 10 depicted in FIG. 2A. However, the method 130 can be used with other enqueuing mechanisms and/or other switches (not shown) having different and/or additional components. The method 130 is also preferably used to manage attacks at when traffic enters or leaves a cloud 50, 52, 54, 56, 60, 62, 64, or 70. Thus, the switch 10 is preferably located at the edge of a cloud 50, 52, 54, 56, 60, 62, 64, or 70 and provides traffic to or from an external destination or source, respectively. The method 130 will, therefore, be described in the context of the cloud 54 receiving or sending packets. However, nothing prevents the method 130 from being used in another portion of the cloud 50, 52, 54, 56, 60, 62, 64, or 70, between individual hosts, between networks, and/or between autonomous systems in a cloud 50, 52, 54, 56, 60, 62, 64, or 70. Moreover, the method 130 is preferably performed in addition to differentiated services being performed. Consequently, in the absence of action being taken, as described below, excess bandwidth is preferably fairly allocated between different behavior aggregate flows and different levels of service provided for different pipelines.

[0053] Referring to FIGS. 2A and 8, the method 130 preferably commences after the network administrator for the cloud 54, or other authorized user, has set a minimum bandwidth guarantee and maximum bandwidth limit for administrative packets. Note that the minimum bandwidth guarantee could be zero. Alternatively, the minimum bandwidth guarantee and maximum bandwidth limit could be positive and equal. In a preferred embodiment, the minimum and maximum bandwidth values are for all administrative packets. However, in an alternate embodiment, the minimum bandwidth guarantee and maximum bandwidth limit can be configured for different types of administrative packets. Thus, for example, RST packets may be treated differently than SYNs.

[0054] It is determined whether suspicious randomness in the administrative packets exists, via step 132. Thus, step 132 is one method for determining whether congestion exists. Stated differently, suspicious randomness can be considered to be a type of congestion. In a preferred embodiment, step 132 is performed by the enqueuing mechanism 20 for the queue 22. In general, suspicious randomness includes randomness that is indicative of malicious traffic, such as the types of randomness described below. In one embodiment, suspicious randomness could include traffic that simply has more variable values in some respect (such as numerous, sequential Source Address (SA) values), as opposed to evidently random values. In a preferred embodiment, step 132 includes determining whether some particular type of the administrative packets in the aggregate flow meets or exceeds a particular maximum bandwidth limit. For example, step 132 may include both determining whether field values (such as SA) are random and determining whether certain well-known flood attack types of administrative packets, such as TCP SYN, TCP SYN/ACK, TCP RST, ICMP host unreachable, or ICMP TTL, have exceeded a minimum bandwidth guarantee for the corresponding type of administrative packet. Step 132 might also include detecting Smurf attacks, preferably by determining whether numerous ICMP pings use a target's address as the source address of the ICMP ping. In another embodiment, step 132 includes limiting ICMP pings, to prevent ping flooding on high bandwidth links that have low bandwidth connectivity. In such an embodiment, a hash function on the source address, or other fields, of the packets may be calculated. In one embodiment, the hash of the SA (or other field or fields) for each of N consecutive packets is calculated. The hash value calculated preferably has B bits. The N packets are considered to constitute an epoch. The hash values are then stored, preferably in a register. The number, N, of consecutive packets preferably can vary. The number N is adjusted at the end of each epoch so that a particular fraction, F, of the hash values is used each epoch. This fraction is preferably one-fourth of the possible 2^B hash values. The allowed number of consecutive packets that constitute an epoch also has a desired maximum value, M. Preferably, an exponential weighting method is used to update the number of packets, N, in an epoch. In particular, in a preferred embodiment, N(i1)K*N(i)if number of hits is less than F, then (1K)*M and 0 otherwise. Here, K is a dimensionless constant such as that is greater than or equal to zero and less than one. Updating this equation will ensure that N comes to a desired state. In such an embodiment, suspicious randomness would be considered to exist when N decreases below a particular level. In other words, in such an embodiment, when N is near M, suspicious randomness or high variability that is not evidently random is considered not to exist. In addition, statistics on fields of some administrative packets, such as the Destination Address (DA) of packets such as SYN packets, could be used as above to determine suspicious randomness. If a large number of different destination addresses is detected, then suspicious randomness would be considered to exist in step 132.

[0055] If it is determined that suspicious randomness exists in some type of administrative traffic in combination with a traffic rate in excess of a minimum bandwidth guarantee, then a portion of the plurality of administrative packets can be discarded, via step 134. The portion of the plurality of packets discarded in step 134 is sufficient to ensure that a remaining portion of the administrative packets transmitted is not more than the maximum packet bandwidth limit and, assuming that there is a sufficient offered traffic load, not less than the minimum bandwidth guarantee. Thus, step 134 preferably discards an increasing fraction of the administrative packets until the minimum bandwidth guarantee is reached. In a preferred embodiment, the portion of administrative packets discarded during instances of excessive randomness rapidly drives the transmitted administrative packets in the behavior aggregate flow of the traffic type to its minimum bandwidth guarantee. For example, the portion of administrative packets transmitted may be exponentially decreased with a certain constant period to rapidly drive the administrative traffic to the minimum guarantee. However, in an alternate embodiment, a different number of administrative packets are discarded in step 134. In addition, the type of administrative packets discarded in step 134 preferably matches the corresponding type(s) of packets monitored for suspicious randomness. In addition, step 134 is preferably performed by the enqueuing mechanism 20. As a result, the discarded administrative packets preferably do not reach the corresponding queue 22.

[0056] If it is determined that suspicious randomness does not exist, then, if there is excess bandwidth, a preferably increasing fraction of the administrative packets is transmitted, via step 136. For example, the fraction of transmitted traffic of the administrative packets may be increased linearly a limit of one is reached. Note that step 136 can be considered to be optional. In a preferred embodiment, because the method 130 is assumed to be performed with differentiated services as a background, the excess bandwidth may still be allocated even in the absence of step 136. The allocation of excess bandwidth would then be performed by the mechanism that performs differentiated services, such as the method and apparatus described in the first above-identified co-pending U.S. patent application.

[0057] Because suspicious randomness is used as a trigger for discarding a greater portion of the administrative packets traveling through the switch 10, the method 130 can manage certain attacks, such as DoS attacks. Furthermore, because of the use of minimum and maximum administrative packet bandwidth values, the method 130 can more effectively protect against attacks, such as DoS attacks, by rapidly reducing the number of administrative packets flowing through the switch while improving performance of the switch 10. For example, excess bandwidth is still allocated in a fair manner, and the fraction of administrative packets discarded may then be varied to ensure that an appropriate amount of suspicious traffic is discarded.

[0058] Thus, using the methods 100, 110, 120, and/or 130, attacks, such as DoS attacks can be better managed. In addition, the method 100 may include one or more of the methods 110, 120 and/or 130. In addition, the manner in which packets are discarded and bandwidth is allocated allows for denial of service attacks to be detected and accounted for gracefully, high utilization, low latency, fast convergence to a desired allocation and fair allocation in that excess bandwidth is allocated equally among different pipes.

[0059] A method and system has been disclosed for responding to attacks, such as DoS attacks in a computer system. Software written according to the present invention is to be stored in some form of computer-readable medium, such as memory, CD-ROM, or transmitted over a network, and executed by a processor. Consequently, a computer-readable medium is intended to include a computer readable signal which, for example, may be transmitted over a network. Although the present invention has been described in accordance with the embodiments shown, one of ordinary skill in the art will readily recognize that there could be variations to the embodiments and those variations would be within the spirit and scope of the present invention. Accordingly, many modifications may be made by one of ordinary skill in the art without departing from the spirit and scope of the appended claims.