Abstract:
A system and method are disclosed, which controls congestion to efficiently transmit data through a network of grid node network in a grid computing environment where a large amount of data is processed. The system and method are performed in such a way that, according to a grid application program&#39;s request for distributed processing a large amount of data, the data is divided into packets, the node availability of respective nodes distributed in the grid network is measured with consideration to the bandwidth and the queue size of available grid nodes to avoid and control network congestion that may occur when the packets are processed by distributed processing using the respective nodes, the average node availability of all nodes is predicted using a statistical method, a threshold is calculated based on the predicted average node availability to set a dynamic congestion area representing the congestion level of the respective nodes, and the amount of packet transmission is controlled based on the congestion area. As the grid nodes are managed by controlling congestion, packet loss and packet delay are reduced and the rate of packet processing and the rate of node use are increased. Therefore, data can be stably transmitted to the grid user through the network with an improvement in the Quality of Service (QoS).

Description:
PRIORITY 
       [0001]    This application claims the benefit under 35 U.S.C. § 119(a) of a Korean patent application filed on Jun. 1, 2007 in the Korean Intellectual Property Office and assigned Serial No. 10-2007-0053763, and the entire disclosure of which is hereby incorporated by reference 
       BACKGROUND OF THE INVENTION 
       [0002]    1. Field of the Invention 
         [0003]    The present invention generally relates to grid computing systems. More particularly, the present invention relates to a system and method for controlling congestion in a grid network of nodes, which can efficiently transmit data in a grid-computing environment where a large amount of data is processed. 
         [0004]    2. Description of the Related Art 
         [0005]    Congestion in a grid network represents the situation where the traffic or equipment present in the grid network exceeds the available network capacity. This congestion causes packets to be delayed. If this congestion continues, then data packets form a queue. This causes a queuing delay. As a result, the congestion causes packet loss and data loss with packet delay. 
         [0006]    More specifically, since packet allocation and communication are frequently performed between a grid administrator and respective grid nodes, which have a variety of bandwidths and limited storage devices, in a grid network, there is a relatively high possibility of congestion. Here, the grid network allows a large amount of data requested by a grid application program to be transmitted and processed. 
         [0007]    A Transmission Control Protocol (TCP) as the transmission protocol usually used in a grid network discards packets at random, which are allocated in excess of the limit value if the grid node is in a congested state. On the contrary, if the grid node isn&#39;t in a congested state, the TCP allows packets corresponding to the discarded packets to be re-transmitted using a packet re-transmission mechanism. This increases the response time which causes data processing delays and makes the network unstable. 
         [0008]    In order to resolve these problems, an additional network congestion control system needs to be adapted to the grid network. The following describes conventional network congestion control techniques that have been studied to date. 
         [0009]    Wu Liu, Hai-Xin Duan, Jianping Wu, Xing Li, and Ping Ren&#39;s (hereinafter referred to as Wu Liu, et al.) “Algorithms for Congestion Detection and Control” in LNCS 3252, pp. 374˜381, describes the Early Congestion Detection &amp; Control gateway (ECDC) and a congestion control method for congestion avoidance and congestion control. 
         [0010]    Wu Liu, et al.&#39;s method performs congestion avoidance and congestion control in such a way that the average queue size of the respective nodes is calculated, and, if the respective nodes exceed a threshold, packets are discarded or the bits of the header in the packets are set. However, since Wu Liu, et al.&#39;s method utilizes only the present measurement value based on a single parameter to control congestion, the congestion presently generated may subsequently occur again. 
         [0011]    Also, P. Dickens presents “FOBS: A lightweight communication protocol for Grid Computing” in LNCS 2790, pp. 938˜946, in which the lightweight communication protocol provides a user-level communication mechanism for transmitting a large amount of data of computational grids, and an aggressive congestion control method. Dickens&#39; method employs the packet loss rate to control congestion, similar to the conventional TCP congestion control method, and, if the packet loss rate exceeds the threshold, reduces the transmission rate to avoid congestion in the network. 
         [0012]    However, since Dickens&#39; method determines the network congestion state based on the packet loss rate that is taken into account after the packet loss occurs, it has difficulty detecting and avoiding the initial congestion. 
         [0013]    Additionally, a conventional congestion control method has been disclosed in Korean Patent Publication No. 10-2005-0071403. 
         [0014]    These conventional network congestion control techniques control congestion in the network based on the size of priority queues for storing packets located at the nodes, or the size of congestion window. Although these conventional techniques may be relatively suitable for controlling the network congestion that is generated due to the bottleneck phenomena in a conventional network environment whose performance is limited, they require numerous grid nodes and thus are not appropriate for a grid network environment where a relatively large bandwidth is needed and a high network delay occurs. 
         [0015]    These conventional network congestion control techniques have a disadvantage in that the size of priority queues or the size of congestion window, which is used to set the congestion reference, is not sufficient to express the degree of congestion for a network of grid nodes, including various reference parameters, such as a bandwidth and idle channel, etc. Also, since the conventional techniques must frequently perform communication to measure congestion-related parameters, in real time, and thus cause network delays, they cannot cope with a grid node state that alters according to elapsed time and increased workload. In addition, since conventional techniques use the statistical critical values, they have difficulty reacting to dynamic changes in a grid node. Especially, if network workload is low, the conventional techniques do not sufficiently use the bandwidth of the network. Furthermore, these conventional techniques are disadvantageous in that packet loss increases and node use rate decreases since an aggressive congestion control mechanism discards packets of corresponding nodes when the amount of communication for real time measurement is increased and network congestion occurs. 
       SUMMARY OF THE INVENTION 
       [0016]    An aspect of the present invention is to address at least the above-mentioned problems and to provide at least the advantages described below. Accordingly, an aspect of the present invention is to provide a system and method for controlling grid network congestion that detects and controls congestion in a grid network that includes a relatively high bandwidth and a relatively high network delay to transmit data stably and reliably through the grid network thereby reducing packet loss and packet delay. 
         [0017]    Another aspect of the present invention is to provide a system and method for controlling grid network congestion that enhances the node use rate to improve the amount of packets processed through a packet adjusting unit that divides a large amount of data transmitted from a grid application program into packets to comply with the performance of the grid node, integrates the divided packets to undergo the distribution process, adjusts the packet transmission rate of the node based on the level of the congestion, and transmits the packets. 
         [0018]    Further another aspect of the present invention is to provide a system and method for controlling grid network congestion that observes grid node information, such as available bandwidth, size of storage queue and channel idle time, etc., stores them in a database, and provides node-related information necessary for packet scheduling and node management. 
         [0019]    Still another aspect of the present invention is to provide a system and method for controlling grid network congestion that measures unique availabilities of respective nodes to which the dynamic workload and available bandwidth are reflected in consideration of the nature of the grid network, predicts the average availability which alters according to time and load and sets the congestion area, thereby efficiently detecting and avoiding congestion. 
         [0020]    In accordance with an exemplary embodiment of the present invention, a system for controlling congestion in a grid network is provided. The system includes a node managing unit for collecting node status information from grid nodes and for providing the node status information in response to a message for requesting node information, a prediction unit for calculating node availabilities of the respective grid nodes, based on the node status information transmitted from the node managing unit, and for predicting the average node availability of all the grid nodes, a packet adjusting unit for setting a congestion area based on the average anode availability transmitted from the prediction unit and for allocating packets according to estimated congestion levels of the respective grid nodes, and a grid intermediary for searching for available grid nodes in the grid network, for dividing data transmitted from a grid application program into the packets to transmit them to the packet adjusting unit, and for collecting the packets processed by the packet adjusting unit to convert them into result data. 
         [0021]    In accordance with another exemplary embodiment of the present invention, a method for controlling congestion in a grid network configured to include a grid intermediary, a packet adjusting unit, a node managing unit, and a prediction unit is provided. The method includes by the node managing unit, collecting status information from respective grid nodes in each time period, receiving a message for requesting node information from the packet adjusting unit or the prediction unit, and transmitting a node information list including the status information, by the prediction unit, calculating node availabilities of the respective grid nodes based on the node information list, and predicting the average node availability of all the grid nodes using the second order exponential smoothing, and by the packet adjusting unit, setting a congestion area based on the average node availability transmitted from the prediction unit, estimating congestion levels of the respective grid nodes to accord packet allocation priority and to sort a node list, and sequentially allocating divided packets according to the node list. 
         [0022]    Other aspects, advantages, and salient features of the invention will become apparent to those skilled in the art from the following detailed description, which, taken in conjunction with the annexed drawings, discloses exemplary embodiments of the invention. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0023]    The above and other aspects, features, and other advantages of certain exemplary embodiments of the present invention will become more apparent from the following detailed description in conjunction with the accompanying drawings, in which: 
           [0024]      FIG. 1  is a schematic block diagram illustrating a system for controlling congestion in a grid network according to an exemplary embodiment of the present invention; 
           [0025]      FIG. 2  is a flowchart describing a method for controlling congestion in a grid network according to an exemplary embodiment of the present invention; 
           [0026]      FIG. 3  is a flowchart describing the information request information reception, and information transmission in the method for controlling congestion in a grid network according to an exemplary embodiment of the present invention; 
           [0027]      FIG. 4  is a flowchart describing the node availability measurement and average node availability prediction in the method for controlling congestion in a grid network according to an exemplary embodiment of the present invention; 
           [0028]      FIG. 5  is a flowchart describing the congestion area setting and packet allocation in the method for controlling congestion in a grid network according to an exemplary embodiment of the present invention; 
           [0029]      FIG. 6  is a flowchart describing a process for according packet allocation priority in a method for controlling congestion in a grid network according to an exemplary embodiment of the present invention; and 
           [0030]      FIG. 7  is a flowchart describing a process for sorting the node list in a method for controlling congestion in a grid network according to an exemplary embodiment of the present invention. 
       
    
    
       [0031]    Throughout the drawings, like reference numerals will be understood to refer to like parts, components and structures. 
       BRIEF DESCRIPTION OF SYMBOLS IN THE DRAWINGS 
       [0000]    
       
         
           
               100 : grid intermediary 
               110 : work requesting module 
               120 : result producing module 
               130 : grid registry 
               200 : packet adjusting unit 
               210 : congestion area setting module 
               220 : packet transmitting module 
               230 : result transmitting module 
               300 : node managing unit 
               310 : information requesting module 
               320 : information receiving module 
               330 : information transmitting module 
               340 : grid node database 
               400 : prediction unit 
               410 : list requesting module 
               420 : availability calculating module 
               430 : availability predicting module 
           
         
       
     
       DETAILED DESCRIPTION OF EXEMPLARY EMBODIMENTS 
       [0049]    The following description with reference to the accompanying drawings is provided to assist in a comprehensive understanding of exemplary embodiments to the present invention as defined by the claims and their equivalents. It includes various specific details to assist in that understanding but these are to be regarded as merely exemplary. Accordingly, those of ordinary skill in the art will recognize that various changes and modifications of the embodiments described herein can be made without departing from the scope and spirit of the invention. Also, descriptions of well-known functions and constructions are omitted for clarity and conciseness. 
         [0050]      FIG. 1  is a schematic block diagram illustrating a system for controlling congestion in a grid network according to an exemplary embodiment of the present invention. 
         [0051]    As shown in  FIG. 1 , the grid network congestion control system is configured to include a grid intermediary that divides data into sub-packets in response to a data process request received from a grid user (grid application program) and collects processed packets to convert them into result data, a packet adjusting unit that estimates the congestion level of grid nodes based on the congestion area to thus accord priority to the grid nodes, and then allocates the packets received from the grid intermediary a node managing unit that provides the node status information for packet allocation and node management, and a prediction unit that predicts an average node availability of all the grid nodes based on the node information and estimates the congestion area. 
         [0052]    In an exemplary embodiment of the present application, a “grid node” is referred to as a node that has a processor and a memory, etc. and is an element connected as part of a grid network. 
         [0053]    When a grid user requests to process a large amount of data, the grid intermediary  100  searches for grid nodes capable of processing the data. 
         [0054]    The grid intermediary  100  transmits packets to the packet adjusting unit  200  of a grid site where the searched grid node is located and collects processed packets to generate result data. To this end, the grid intermediary  100  is configured to include a work requesting module  110 , a result producing module  120 , and a grid registry  130 . The grid site represents a set of grid nodes. 
         [0055]    The grid registry  130  registers and searches for all grid nodes connected to the grid network. 
         [0056]    The work requesting module  110  receives a large amount of data from the grid user, divides corresponding data into packets, checks the grid registry  130  to search for a grid node capable of calculating data, and transmits the packets to the packet adjusting unit of the grid site including the searched grid node. 
         [0057]    The result producing module  120  collects processed packets, converts the format of the processed packets into the format requested by the grid application program to accordingly generate result data, and then transmits the result data to the grid application program. 
         [0058]    The node managing unit  300  is connected to the grid nodes. The node managing unit  300  serves to monitor the grid nodes and extracts the status information about the respective grid nodes to provide the node information. To this end, the node managing unit  300  is configured to include an information requesting module  310 , an information receiving module  320 , an information transmitting module  330 , and a grid node database  340 . 
         [0059]    The information requesting module  310  transmits a message for requesting status information to the grid nodes at certain time intervals. The information receiving module  320  collects result messages from respective grid nodes that receive the request message and stores the result messages in the grid node database  340 . Here, the result messages transmitted from the respective grid nodes may be in an XML format. Also, the information transmitting module  330  transmits node status information to the packet adjusting unit  200  or the prediction unit  400  in response to a message requesting the node information. 
         [0060]    The prediction unit  400  measures the node availabilities of the respective grid nodes and predicts the average node availability of all grid nodes, as a reference parameter for setting a congestion area, using the second-order exponential smoothing-based prediction method. To this end, the prediction unit  400  is configured to include a list requesting module  410 , an availability calculating module  420 , and an availability predicting module  430 . 
         [0061]    The list requesting module  410  requests and receives the node information list from the node managing unit  300 , which is used as basic data for calculating and predicting the node availability. The availability calculating module  420  calculates the node availabilities of the respective grid nodes based on the node information list, and stores them again in the grid node database  340  of the node managing unit  410 . The availability predicting module  430  measures the average of the node availabilities calculated at the current time point and predicts the average node availability using the second-order exponential smoothing, based on old data and current data. 
         [0062]    The packet adjusting unit  200  stores packets transmitted from the work requesting module  110  in a queue and sets the congestion area based on the average node availability received from the prediction unit  400 . 
         [0063]    The packet adjusting unit  200  requests node status information from the node managing unit  300  and receives the node information list from the node managing unit  300 . The packet adjusting unit  200  estimates the congestion levels of the respective nodes according to the node information list and the average node availability and then accords the packet allocation priority. The packet adjusting unit  200  transmits the packets to the respective grid nodes according to the packet allocation priority, stores the packets processed by the grid nodes in an output queue, and then transmits them to the result producing module  120  of the grid intermediary  100 . 
         [0064]    To this end, the packet adjusting unit  200  is configured to include a congestion area setting module  210 , a packet transmitting module  220 , and a result transmitting module  230 . 
         [0065]    The congestion area setting module  210  serves as the primary element of the network congestion control system and enables the congestion area to be estimated. The congestion area setting module  210  sets a congestion area, based on the average node availability transmitted from the prediction unit  400 . 
         [0066]    The congestion area setting module  210  loads node information from the grid node database  330 , estimates the congestion levels of the respective nodes, and accords the packet allocation priority. The packet transmitting module  220  includes an input queue for storing packets. The packet transmitting module  220  stores the divided packets transmitted from the work requesting module  110  in the input queue. The packet transmitting module  220  allocates the packets stored in the input queue to the respective grid nodes, in order, according to the packet allocation priority set by the congestion area setting module  210 . 
         [0067]    The result transmitting module  230  includes an output queue for storing packets. The result transmitting module  230  receives the packets processed by the respective grid nodes and stores them in the output queue. After the data has been processed into packets, the result transmitting module  230  sequentially transmits the packets, stored in the output queue, to the result producing module  120 . 
         [0068]    The following is a description of the operation of the grid network congestion control system as described above, and of a method for controlling congestion in a grid network, with reference to the relevant diagrams. 
         [0069]      FIG. 2  is a flowchart describing a method for controlling congestion in a grid network according to an exemplary embodiment of the present invention. First, the grid intermediary  100  searches for available grid nodes, divides data received from the grid application program into packets, and transmits the divided packets to the packet adjusting unit  200  (S 100 ). 
         [0070]    The node managing unit  300  collects status information from respective grid nodes each time period. If the node managing unit  300  receives a message requesting node information from the packet adjusting unit  200  or the prediction unit  400 , it transmits a node information list including the status information thereto (S 200 ). 
         [0071]    The prediction unit  400  calculates the node availabilities of the respective grid nodes based on the node information list and then predicts the average node availability of all grid nodes using the second-order exponential smoothing (S 300 ). 
         [0072]    The packet adjusting unit  200  sets a congestion area based on the average node availability received from the prediction unit  400 , estimates the congestion levels of the respective nodes to accord packet allocation priority and to sort node lists, and then sequentially allocates the divided packets according to the node lists (S 400 ). 
         [0073]    The grid node intermediary  100  collects the packets, processed by the respective grid nodes, from the packet adjusting unit  200  and generates result data based on the collected packets (S 900 ). 
         [0074]      FIG. 3  is a flowchart describing information request, information reception, and information transmission in a method for controlling congestion in a grid network according to an exemplary embodiment of the present invention. That is.  FIG. 3  is a flowchart describing step S 200  of  FIG. 2  in detail. 
         [0075]    The node managing unit  300  determines whether to receive a node information request message from the packet adjusting unit  200  or the prediction unit  400  (S 210 ). 
         [0076]    If the node managing unit  300  does not receive a node information request message at step S 210 , the information requesting module  310  transmits an inquiry message in an XML format to the respective grid nodes to collect status information about the nodes, at certain time intervals (S 220 ). 
         [0077]    The respective grid nodes having received the inquiry message prepare result messages responsive to the inquiry message, and transmit them to the node managing unit  300  (i.e. the information receiving module  320 ) (S 230 ). 
         [0078]    The information receiving module  320  stores the result messages relating to the status information received from the grid nodes in the grid node database  340  (S 240 ). 
         [0079]    On the contrary, if the node managing unit  300  receives a request message relating to node information from the packet adjusting unit  200  or the prediction unit  400  at step S 210 , the node managing unit  300  interrupts its current job and extracts node status information from the grid node database  340  (S 250 ). 
         [0080]    The information transmitting module  330  transmits the extracted node status information about the respective nodes, in a list to the packet adjusting unit  200  or the prediction unit  400  (S 260 ). 
         [0081]    After the node information list has been transmitted, the node managing unit  300  resumes the interrupted job (S 270 ). 
         [0082]      FIG. 4  is a flowchart describing node availability measurement and average node availability prediction in a method for controlling congestion in a grid network according to an exemplary embodiment of the present invention. That is,  FIG. 4  is a flowchart describing step S 300  of  FIG. 2  in detail. 
         [0083]    The list requesting module  410  checks whether to receive a request message of the average node availability from the congestion area setting module  210  of the packet adjusting unit  200  (S 310 ). 
         [0084]    If the list requesting module  410  receives the request of the average node availability at stet S 310 , it requests and receives the node information list, stored in the grid node database  340 , from the node managing unit  300  (S 320 ). 
         [0085]    The availability calculating module  420  calculates the node availabilities of the respective grid nodes based on the node information list using the following Equation (1) (S 330 ). 
         [0000]    
       
         
           
             
               
                 
                   
                     Av 
                     = 
                     
                       
                         ( 
                         
                           
                             T 
                             w 
                           
                           × 
                           
                             B 
                             w 
                           
                           × 
                           
                             Q 
                             a 
                           
                         
                         ) 
                       
                       / 
                       T 
                     
                   
                    
                   
                     
 
                   
                    
                   where 
                    
                   
                     
 
                   
                    
                   
                     
                       B 
                       w 
                     
                     = 
                     
                       
                         1 
                         m 
                       
                        
                       
                         
                           ∑ 
                           
                             i 
                             = 
                             1 
                           
                           m 
                         
                          
                         
                           
                             P 
                             s 
                           
                            
                           
                             ( 
                             
                               
                                 Ta 
                                 i 
                               
                               - 
                               
                                 Ts 
                                 i 
                               
                             
                             ) 
                           
                         
                       
                     
                   
                    
                   
                     
 
                   
                    
                   and 
                    
                   
                     
 
                   
                    
                   
                     
                       Q 
                       a 
                     
                     = 
                     
                       1 
                       - 
                       
                         
                           ( 
                           
                             
                               Q 
                               u 
                             
                             / 
                             
                               Q 
                               t 
                             
                           
                           ) 
                         
                         . 
                       
                     
                   
                 
               
               
                 
                   ( 
                   1 
                   ) 
                 
               
             
           
         
       
     
         [0086]    The variables in Equation 1 are defined as follows: 
         [0087]    Av: the node availability of a grid node 
         [0088]    T: the observation time 
         [0089]    T w : the channel wait time during the observation time. T 
         [0090]    B w : the average bandwidth of the grid nodes 
         [0091]    Q a : the queue size available by the grid node 
         [0092]    m: the number of paths capable of transmitting packets from a transmission node (e.g. a packet adjusting unit) to a receiving node (e.g. a grid node) 
         [0093]    P s : the general packet size 
         [0094]    i: the index of the packet transmission path 
         [0095]    T a : the time period that a receiver receives packets through the i-th path 
         [0096]    T s : the time period that a transmitter transmits packets through the i-th path 
         [0097]    Q t : the total queue size of a grid node 
         [0098]    Q u : the size of queues in use, of the total queues 
         [0099]    Referring to  FIG. 4 , the prediction unit  400  transmits the calculated node availability to the node managing unit  300  and then stores it again in the grid node database  340  (S 340 ). 
         [0100]    After that, the availability prediction module  430  of the prediction unit  400  calculates the average node availability of all grid nodes at the current time point (S 350 ), as in the following Equation (2). 
         [0000]    
       
         
           
             
               
                 
                   AVG 
                   = 
                   
                     
                       1 
                       n 
                     
                      
                     
                       
                         ∑ 
                         
                           i 
                           = 
                           1 
                         
                         n 
                       
                        
                       Avi 
                     
                   
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
           
         
       
     
         [0101]    The variables in Equation (2) are defined as follows: 
         [0102]    AVG: the average node availability 
         [0103]    Av: the node availability of a grid node 
         [0104]    i: the index of a grid node 
         [0105]    n: the number of total grid nodes 
         [0106]    The average node availability calculated by Equation (2) is referred to as time series data that are varied according to elapsed time and workload. 
         [0107]    If the average node availability is calculated each observation time point, the reference value of a congestion area by variables, such as workload or bandwidth, is changed so large to cause a problem: although a grid node that does not cause congestion at the current time point, the grid node may cause congestion at the next observation time point. 
         [0108]    The basic congestion control scheme takes old data related to congestion generation into consideration to prevent the same congestion from reoccurring in the near future. 
         [0109]    Therefore, the availability prediction module  430  predicts the average node availability at each observation time point using the second-order exponential smoothing (S 360 ), as in the following Equation (3). 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       FT 
                       
                         t 
                         + 
                         1 
                       
                     
                     = 
                     
                       
                         
                           ( 
                           
                             2 
                             + 
                             
                               α 
                               
                                 1 
                                 - 
                                 α 
                               
                             
                           
                           ) 
                         
                          
                         
                           F 
                           t 
                         
                       
                       - 
                       
                         
                           ( 
                           
                             1 
                             + 
                             
                               α 
                               
                                 1 
                                 - 
                                 α 
                               
                             
                           
                           ) 
                         
                          
                         
                           T 
                           t 
                         
                       
                     
                   
                    
                   
                     
 
                   
                    
                   where 
                    
                   
                     
 
                   
                    
                   
                     
                       F 
                       t 
                     
                     = 
                     
                       
                         α 
                          
                         
                             
                         
                          
                         
                           D 
                           t 
                         
                       
                       + 
                       
                         
                           ( 
                           
                             1 
                             - 
                             α 
                           
                           ) 
                         
                          
                         
                           F 
                           
                             t 
                             - 
                             1 
                           
                         
                       
                     
                   
                    
                   
                     
 
                   
                    
                   and 
                    
                   
                     
 
                   
                    
                   
                     
                       T 
                       t 
                     
                     = 
                     
                       
                         α 
                          
                         
                             
                         
                          
                         
                           F 
                           t 
                         
                       
                       + 
                       
                         
                           ( 
                           
                             1 
                             - 
                             α 
                           
                           ) 
                         
                          
                         
                           
                             T 
                             
                               t 
                               - 
                               1 
                             
                           
                           . 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   3 
                   ) 
                 
               
             
           
         
       
     
         [0110]    The variables in Equation 3 are defined as follows: 
         [0111]    FT: the estimated average node availability 
         [0112]    t: the current observation time point 
         [0113]    t+1: the next observation time point 
         [0114]    D: the measured average node availability calculated through Equation (2) 
         [0115]    α: the smoothing constant for according a weight value to old data and current data, 0&lt;α&lt;1 
         [0116]    F: the prediction variable for the first-order exponential smoothing 
         [0117]    T: the doubling-smoothed statistic 
         [0118]    After that, the prediction unit  400  transmits the estimated average node availability to the congestion area setting module  210  using Equation (3) and enters a wait state (S 370 ). 
         [0119]      FIG. 5  is a flowchart describing congestion area setting and packet allocation in a method for controlling congestion in a grid network according to an exemplary embodiment of the present invention. That is,  FIG. 5  is a flowchart describing step S 400  of  FIG. 2  in detail. 
         [0120]    First, the packet transmitting module  220  receives packets from the work requesting module  110  (S 410 ). 
         [0121]    The packet adjusting unit  200  inqueues the received packets in order in the input queue (S 420 ). 
         [0122]    The congestion area setting module  210  requests and receives the average node availability used as the reference parameter, for setting a congestion area from the prediction unit  400  (S 430 ). 
         [0123]    When the congestion area setting module  210  requests the node information list, which includes node information about the respective nodes from the node managing unit  300 , the node managing unit  300  extracts the node information list from the grid node database  330  and transmits it to the congestion area setting module  210  (S 440 ). 
         [0124]    The congestion area setting module  210  calculates the maximum threshold and the minimum threshold of the congestion area using the average node availability and the information list of the respective nodes, as per the following Equation (4), and then sets the congestion area (S 450 ). 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       Max 
                       th 
                     
                     = 
                     
                       
                         1 
                         
                           n 
                           1 
                         
                       
                        
                       
                         
                           ∑ 
                           
                             i 
                             = 
                             1 
                           
                           
                             n 
                             1 
                           
                         
                          
                         
                           ( 
                           
                             
                               Ra 
                               i 
                             
                             - 
                             
                               E 
                               avg 
                             
                           
                           ) 
                         
                       
                     
                   
                    
                   
                     
 
                   
                    
                   and 
                    
                   
                     
 
                   
                    
                   
                     
                       Min 
                       th 
                     
                     = 
                     
                       
                         1 
                         
                           n 
                           2 
                         
                       
                        
                       
                         
                           ∑ 
                           
                             i 
                             = 
                             1 
                           
                           
                             n 
                             2 
                           
                         
                          
                         
                           ( 
                           
                             
                               E 
                               avg 
                             
                             - 
                             
                               Ra 
                               i 
                             
                           
                           ) 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   4 
                   ) 
                 
               
             
           
         
       
     
         [0125]    The variables in Equation 4 are defined as follows: 
         [0126]    Max th : the maximum threshold 
         [0127]    Min th : the minimum threshold 
         [0128]    Ra: the node availability of respective grid nodes 
         [0129]    E avg : the estimated average node availability transmitted from the prediction unit 
         [0130]    i: the index of a grid node 
         [0131]    n 1 : the number of grid nodes having the node availability equal to and greater than the average node availability 
         [0132]    n 2 : the number of grid nodes having the node availability equal to and less than the average node availability 
         [0133]    The congestion area classifies the congestion state into three levels, red, green, and yellow levels. The red level represents a case where the node availability of a grid node is less than the minimum threshold, Ra&lt;Min th , and means that the grid node has a high probability of congestion occurrence and thus a high probability of packet loss and packet delay. 
         [0134]    The green level represents a case where the node availability is between the maximum threshold and the minimum threshold, Min th ≦Ra≦Max th , and means that a proper amount of packets are allocated and accordingly the packet process rate and node use rate are stably maintained. 
         [0135]    The yellow level represents a case where the node availability exceeds the maximum threshold, Max th &lt;Ra. For example, since the grid node of the yellow level reduces the use bandwidth and the node use rate of all grid networks, the yellow level means that the allocation amount of packets must be increased to adjust the node availability of a corresponding grid node to a proper level. 
         [0136]    The congestion area setting module  210  estimates congestion states of the respective grid nodes based on the congestion area (S 460 ). 
         [0137]    After that, the packet allocation priority is accorded to the respective grid nodes according to the congestion states (S 470 ), which will be described below with reference to the flowchart of  FIG. 6 . 
         [0138]      FIG. 6  is a flowchart describing a process for according the packet allocation priority in a method for controlling congestion in a grid network according to an exemplary embodiment of the present invention. 
         [0139]    First, the variables described in  FIG. 6  are defined as follows: 
         [0140]    NodeList: an array type list including status information about a grid node 
         [0141]    Priority: the priority according to the congestion state of a grid node 
         [0142]    length: the list length 
         [0143]    i: the index used for list search 
         [0144]    Max th : the maximum threshold 
         [0145]    Min th : the minimum threshold 
         [0146]    Ra: the node availability of the respective grid nodes 
         [0147]    Referring to  FIG. 6 , the packet adjusting unit  200  requests the node information from the grid node database  330  and receives it in a list form from the grid node database  330  (S 610 ). 
         [0148]    After that, the packet adjusting unit  200  compares the node availability of the respective grid nodes with the maximum threshold or the minimum threshold to accord the priority according to the congestion states of the respective grid nodes (S 620 ˜S 640 ). If the congestion state is at the yellow level, the priority becomes 1 (S 650 ). If the congestion state is at the green level, the priority becomes 2 (S 660 ). If the congestion state is at the red level, the priority becomes 3 (S 670 ). 
         [0149]    Also, the congestion area setting module  210  of the packet adjusting unit  200  sorts the node lists to allocate packets (S 470 ), which will be described below with reference to  FIG. 7 . 
         [0150]      FIG. 7  is a flowchart describing a process for sorting the node lists in a method for controlling congestion in a grid network according to an exemplary embodiment of the present invention. 
         [0151]    First, the variables described in  FIG. 7  are defined as follows: 
         [0152]    NodeList: the array type list including status information about a grid node 
         [0153]    length: the list length 
         [0154]    n, m: the index used for list search 
         [0155]    Priority: the priority allocated to a grid node 
         [0156]    Qsize: the size of an available queue possessed by a grid node 
         [0157]    Bandwidth: the minimum bandwidth of an available path possessed by a grid node 
         [0158]    Switch: the function exchanging positions between items 1 and 2 in the node list 
         [0159]    Referring to  FIG. 7 , the node lists are sorted based on the priority, the queue size, and the bandwidth. 
         [0160]    The congestion area setting module  210  sorts the node lists, in ascending order, based on the priority accorded to the respective grid nodes using the process of  FIG. 6  (S 710 ˜S 830 ). In particular, if a plurality of grid nodes has the same priority (S 760 ), the node whose available queue size is relatively large is located at the upper index (S 760 ˜S 790 ). Further, if a plurality of grid nodes has the same queue size as well as the same priority (S 800 ), the node that uses a lower bandwidth is located at the upper index (S 800 ˜S 830 ). 
         [0161]    Referring to  FIG. 5  back, the pack transmitting module  220  of the packet adjusting unit  200  dequeues packets from the input queue, one by one, and transmits the packets to the grid nodes registered in the sorted node list from the highest index to the lowest index in order (S 480 ). Here, the packets are not allocated to the grid nodes whose priority is 3, i.e. those which are at the red level. 
         [0162]    The result transmitting module  230  receives processed packets from the grid nodes and enqueues them in the output queue (S 490 ˜S 500 ). 
         [0163]    When all packets have arrived, the result transmitting module  230  dequeues the packets stored in the output queue  231  and transmits them to the result producing module  120  of the grid intermediary  100  (S 510 ˜S 520 ). 
         [0164]    As is apparent from the above description, the present invention provides a system and method for controlling congestion in a grid network that calculates and predicts node availability reflecting a variety of parameters, such as bandwidth, queue size, and channel wait time, and thus detects and controls congestion in a network more efficiently and precisely, thereby transmitting data through the network in a grid computing environment more efficiently and stably. 
         [0165]    Also, the system and method for controlling congestion in a grid network, according to the present invention, set a congestion area, estimate a congestion state of respective nodes, detect nodes in congestion and restrict the transmission amount of packets, thereby reducing the packet loss. 
         [0166]    Furthermore, the system and method for controlling congestion in a grid network, according to the present invention, control the transmission amount of packets according to the congestion state of the nodes so that: the processed amount of packets and the use rate of grid nodes are increased, network delays are reduced, and Quality of Service (QoS) is improved. 
         [0167]    While the present invention has been described with reference to certain exemplary embodiments thereof, those skilled in the art will appreciate that various modifications, additions and substitutions are possible, without departing from the scope and spirit of the invention as defined by the appended claims and their equivalents.