Patent Publication Number: US-8976661-B2

Title: Network self-protection

Description:
This application claims the benefit of U.S. Provisional Application No. 61/585,337, entitled, “NetFuse: Fighting Flares in the Cloud,” filed on Jan. 11, 2012, the contents of which are incorporated herein by reference. 
    
    
     BACKGROUND OF THE INVENTION 
     The present invention relates to a network and, more particularly, to a self-protected network. 
     Modern data center networks are constructed with advanced infrastructures and well-engineered protocols and are operated with extreme cautions. However, the fierce challenge of network failures is still unchanged, if not intensified, especially as an ever growing population of applications and services enter the era of Cloud. Amazon EC2, for instance, was largely down on Apr. 21, 2011 due to a routing misconfiguration that mistakenly rerouted high-volume external traffic into the low-capacity internal network [3]. As a consequence, thousands of businesses and websites were out of service and seventy-five million PlayStation gamers were affected [5]. Another recent example is the three-day blackout of Blackberry in October 2011 as a result of a core switch failure. 
     To mitigate these problems, a surge of recent efforts are currently underway and have demonstrated encouraging results. One school of people approach the problem by designing next-generation network infrastructures that can improve network bisection bandwidth and provide malleability in the network routing topology [5, 6, 8]. Another group of researchers focus on designing network transport protocol [1, 9] that is particularly fine tuned for data center networks. A last bunch of people seek to propose improved resource placement [2, 7] schemes that can optimize the network resource allocation. At the same time, however, we believe that the cascading catastrophic network failures are unlikely to be prevented without proper considerations of two fundamental assumptions that do not hold in data centers. 
     We design NetFuse, which is, analogously to the fuse boxes in the electrical circuits, a self-protection mechanism that seeks to detect and respond to a variety of network problems and protect the necessary network services. Specifically, NetFuse employs a multi-dimensional flow aggregation algorithm that automatically determines an optimal set of clustering criteria and identifies the suspicious flows that are likely to cause network problems under these criteria. Then, NetFuse adaptively regulates the identified flows according to the network feedback. Due to the light-weight sensing capabilities inherent in the OpenFlow technologies, NetFuse is currently implemented in OpenFlow networks as a proxy device between the switches and the controller. This way, NetFuse can not only intercept the control messages and infer the network states, but also offload the excessive processing overhead for the controller, thereby improving scalability of the entire system. 
     [1] M. Alizadeh, A. Greenberg, D. A. Maltz, J. Padhye, P. Patel, B. Prabhakar, S. Sengupta, and M. Sridharan, “Data Center TCP (DCTCP),” in Proc. ACM SIGCOMM, August 2010. 
     [2] H. Ballani, P. Costa, T. Karagiannis, and A. Rowstron, “Towards Predictable Datacenter Networks,” in Proc. ACM SIGCOMM, August 2011. 
     [3] Why Amazon&#39;s cloud Titanic went down. [Online] Available: http://money.cnn.com/2011/04/22/technology/amazon_ec2_cloud outage/index.htm. 
     [4] G. Cormode, S. Muthukrishnan, and D. Srivastava, “Finding hierarchical heavy hitters in data streams,” in Proc. In Proc. of VLDB, 2003, pp. 464-475. 
     [5] A. Greenberg, J. R. Hamilton, N. Jain, S. Kandula, C. Kim, P. Lahiri, D. A. Maltz, P. Patel, and S. Sengupta, “VL2: a Scalable and Flexible Data Center Network,” in Proc. ACM SIGCOMM, August 2009. 
     [6] C. Guo, G. Lu, D. Li, H.Wu, X. Zhang, Y. Shi, C. Tian, Y. Zhang, and S. Lu, “BCube: a High Performance, Server-Centric Network Architecture for Modular Data Centers,” in Proc. ACM SIGCOMM, August 2009. 
     [7] C. Guo, G. Lu, H. J. Wang, S. Yang, C. Kong, P. Sun, W. Wu, and Y. Zhang, “SecondNet: A Data Center Network Virtualization Architecture with Bandwidth Guarantees,” in Proc. ACM CoNEXT, November 2010. 
     [8] R. N. Mysore, A. Pamboris, N. Farrington, N. Huang, P. Miri, S. Radhakrishnan, V. Subramanya, and A. Vandat, “PortLand: a Scalable Fault-Tolerant Layer 2 Data Center Network Fabric,” in Proc. ACM SIGCOMM, August 2009. 
     [9] V. Vasudevan, A. Phanishayee, H. Shah, E. Krevat, D. G. Anderson, G. R. Ganger, G. A. Gibson, and B. Mueller, “Safe and Effective Fine-Grained TCP Retransmissions for Datacenter Communication,” in Proc. ACM SIGCOMM, August 2009. 
     [10] C. Wilson, H. Ballani, T. Karagiannis, and A. Rowstron, “Better Never than Late: Meeting Deadlines in Datacenter Networks,” in Proc. ACM SIGCOMM, August 2011. 
     [11] A. Wundsam, D. Levin, S. Seetharaman, and A. Feldmann, “OFRewind: Enabling Record and Replay Troubleshooting for Networks,” in Proc. USENIX Annual Technical Conference, June 2011. 
     [12] Y. Zhang, S. Singh, S. Sen, N. Duffield, and C. Lund, “Online identification of hierarchical heavy hitters: algorithms, evaluation, and applications,” in Proc. Proceedings of the 4th ACM SIGCOMM conference on Internet measurement, ser. IMC &#39;04. 
     BRIEF SUMMARY OF THE INVENTION 
     NetFuse leverages the powerful network sensing capabilities of OpenFlow&#39;s unique messaging mechanism. As a standalone product, NetFuse can proactively protect the network infrastructure from hard-to-find problems and prevent failure propagation. This is very important for Cloud service providers or data center operators and can rescue the network from disastrous network downtime and service disruption. NetFuse is also a value added services that can be built over OpenFlow switches and therefore are expected to boost the sales and marketing of OpenFlow devices. 
     An objective of the present invention is to detect, or react to, a network problem such as network overload. 
     An aspect of the present invention includes a device used in a network, comprising a network monitor to monitor a network state and to collect statistics for flows going through the network, a flow aggregation unit to aggregate flows into clusters and identify flows that can cause a network problem, and an adaptive control unit to adaptively regulate the identified flow according to network feedback. 
     Another aspect of the present invention includes a method used in a network, comprising monitoring a network state and to collect statistics for flows going through the network, aggregating flows into clusters and identify flows that can cause a network problem, and adaptively regulating the identified flow according to network feedback. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  depicts a system architecture. 
         FIG. 2  depicts a flow chart related to the system architecture. 
         FIG. 3  depicts an example reasonable flow aggregations. 
         FIG. 4  depicts a flowing diagram that illustrates Procedure  1 . 2 . 
         FIG. 5  depicts an example of different flow aggregations. 
         FIG. 6  depicts Algorithm  1 . 
         FIG. 7  depicts preliminary experiment results. 
         FIG. 8  depicts FatTree network topology. 
     
    
    
     DETAILED DESCRIPTION 
     As illustrated in  FIG. 1 , NetFuse comprises three major components: network monitor, flow aggregation, and adaptive control. First, NetFuse continuously monitors the network states and collect statistics for flows going through the network. Then, during flow aggregation, NetFuse identifies the suspicious flows that are likely to cause network problems. Finally, NetFuse adaptively regulates the identified flows according to the network feedback. 
     Leveraging the light-weight sensing capabilities inherent in the OpenFlow technologies, NetFuse is currently implemented in OpenFlow networks as a proxy device between the switches and the controller. But NetFuse is not limited to OpenFlow and can be applied to general network systems if monitoring data are available. 
     The above system architecture can be mapped to the flow chart in  FIG. 2 . 
     Procedure  1 : Flow Aggregation 
     This procedure seeks to aggregate flows into clusters and find the cluster that is most likely to be responsible for certain network problems. In the input of this procedure is flow statistics and the output is clusters of suspicious flows. Procedure  1 . 1  and  1 . 2  are specific solutions that accomplish this goal. 
     Procedure  1 . 1 : Single-Dimensional Aggregation 
     First, define a score S(P) to measure the significance of the overloading flows: S(P)=(max(F)−m − (F))/m − (F), where m −  is the low median operator. Then, the goal is to find the aggregation that best reveals the overloading behavior, i.e., P*=max P S(P). Next, select or define the aggregations that reveal overloading behavior, based on best practice or operator specifications for the aggregation rules.  FIG. 3  is an example set of aggregation rules. 
     For aggregation rules that require a threshold value, we define the value according to different applications. There are many ways to determine this. 
     After all the above information is available, the algorithm simply chooses one aggregation rules, clusters flows based on this rule, and outputs the set of flows with the highest score or the score exceeding the predetermined threshold values. 
     Procedure  1 . 2 : Multi-Dimensional Aggregation 
     In practice, the overloading can be caused by specific applications at specific network regions, corresponding to a combination of multiple aggregation conditions on different flow properties. This procedure correlate multiple aggregation rules and identify the combination of rules that most evidently real the network problems. As illustrated in  FIG. 4 , this procedure is essentially a breadth-first search algorithm with branch pruning to enumerate the multi-dimensional flow. 
     Procedure  2 : Adaptive Control 
     This procedure applies adaptive control on flows generated in Procedure  1 . Procedure  2 . 1  is one way to realize this adaptive control. 
     Procedure  2 . 1 : Toxin-Antitoxin Control 
     When NetFuse apply extra delays to an overloading flow f&#39;s RTT (round-trip delay time), NetFuse tests the aggressiveness of f&#39;s response. If f reduces its rate, the extra delay will also be reduced, and eventually it will no longer suffer extra delay but enjoy the original data path; otherwise, the extra delay increases and eventually fills the buffer, dropping all packets of f. If the target rate of f is r, while f&#39;s current rate demand (measured at NetFuse box buffer queue) is r f , the extra delay NetFuse put on f is: (r f −r)×r f ×RTT/r. Assuming the flows employ TCP (Transmission Control Protocol) and thus the flow rate is inversely proportional to RTT, since r f ˜RTT, the extra delay on f intends to reduce flow rate from r f  to r. In practice, well-behaving flows respond to the extra delay by lowering the rate to or under r, and thus it will see no more extra delay at NetFuse; ill-behaving flows may continue take higher rate than they should, and NetFuse will continue delaying their packets, with possible mandatory drops. 
     The foregoing is to be understood as being in every respect illustrative and exemplary, but not restrictive, and the scope of the invention disclosed herein is not to be determined from the Detailed Description, but rather from the claims as interpreted according to the full breadth permitted by the patent laws. It is to be understood that the embodiments shown and described herein are only illustrative of the principles of the present invention and that those skilled in the art may implement various modifications without departing from the scope and spirit of the invention. Those skilled in the art could implement various other feature combinations without departing from the scope and spirit of the invention.