Abstract:
The disclosure discloses a method and system for complex flow classification of fragmented packets. The method includes determining whether a received fragment is an initial fragment, if the received fragment is an initial fragment, storing the initial fragment information and processing it, otherwise, looking for the matched initial fragment information, and performing the same action processing as the initial fragment. The application of the techniques provided in embodiments of the disclosure effectively solve the problem of complex flow classification of the fragmented packets based on the transport layer, thereby processing the initial fragment and its non-initial fragments with the same actions.

Description:
CROSS REFERENCE 
       [0001]    The application claims the priority of CN application No. 200610112323.5, filed on Sep. 1, 2006 with the State Intellectual Property Office of the People&#39;s Republic of China, entitled “METHOD, APPARATUS AND SYSTEM FOR COMPLEX FLOW CLASSIFICATION OF FRAGMENTED PACKETS”, the entire contents of which are incorporated herein by reference. 
       FIELD OF THE INVENTION 
       [0002]    The disclosure relates to the technical field of Quality of Service (QoS) of communication transmission, and more particularly, to a method, apparatus and system for complex flow classification of fragmented packets. 
       BACKGROUND 
       [0003]    With rapid development of computer networks, users have exploited new services on the Internet, such as remote teaching, remote medical, video telephone, television conference, video on demand, etc., besides the traditional WWW, E-Mail, File Transfer Protocol (FTP) applications. Enterprise users also hope to connect their branches distributed at different locations via a Virtual Private Network (VPN), so as to deploy some transactional applications. These new services are in common in that they have special requirements for the transmission performances, such as bandwidth, delay and delay jitter, etc. 
         [0004]    The continual appearances of new services present higher requirements for service capabilities of IP network. Users are no longer satisfied with simply delivering the packets to the destination, they expect better services during the delivering, such as supporting to provide private bandwidths for users, reduce the loss rate of packets, manage and avoid network congestion, control the traffic over the network, and set priorities of the packets, i.e., provide different services according to different data flows. All of these require that the network should have better service capabilities. 
         [0005]    Quality of Service (QoS) is a ubiquitous concept wherever the service supply and demand relationship exists. It evaluates the ability of the service provider to satisfy the service requirements of customers. Presently, the models for QoS generally have two types, the integrated service (Inter-Serv) model and differentiated service (Diff-Serv) model. The Diff-Serv model mainly employs simple flow classification (Behavior traffic classification) and complex flow classification with an Access Control List (ACL), wherein the complex flow classification provides differentiated services for different traffics by configuring the parameters such as a 5-tuplet (Differentiated Services Code Point, DSCP, code point value, type of protocol, IP address, transport layer port number, and type of the fragmented packets) in the packet header, so as to implement a traffic policy that is based on complex flow classification. Typically, the complex flow classification may be implemented by processing the packets based on the preset ACL policy. 
         [0006]    In end-to-end packet transmissions over a network, such as a packet transmission from one end NI of the network to another end N2 of the network, the packets are often transmitted in fragmented, i.e., an IP packet is disassembled into several IP packets to be transferred over the network sequentially. In fragmented packet transmission, the first IP packet of the fragmented packet is referred to as an initial fragment and the remaining is referred to as a non-initial fragment(s). Initial fragment has a format same as that of a normal IP packet, which is defined in RFC790 as in Table 1. 
         [0000]    
       
         
               
               
               
               
               
             
               
               
               
               
             
               
               
               
               
             
               
               
               
             
           
               
                   
                 TABLE 1 
               
               
                   
                   
               
             
             
               
                   
                 Version 
                 IHL 
                 ToS 
                 Total Length 
               
             
          
           
               
                   
                 Indentification 
                 Flags 
                 Fragment Offset 
               
             
          
           
               
                   
                 TTL 
                 Protocol_number 
                 Header Checksum 
               
             
          
           
               
                   
                 Source IP 
                   
               
               
                   
                 Destination IP 
               
               
                   
                 Transport layer packet header 
               
               
                   
                 Payload 
               
               
                   
                   
               
             
          
         
       
     
         [0007]    Non-initial fragments have a format that is slightly different from the initial fragment, since there is no transport layer packet header in the non-initial fragments, as shown in Table 2. 
         [0000]    
       
         
               
               
               
               
               
             
               
               
               
               
             
               
               
               
               
             
               
               
               
             
           
               
                   
                 TABLE 2 
               
               
                   
                   
               
             
             
               
                   
                 Version 
                 IHL 
                 ToS 
                 Total Length 
               
             
          
           
               
                   
                 Indentification 
                 Flags 
                 Fragment Offset 
               
             
          
           
               
                   
                 TTL 
                 Protocol_number 
                 Header Checksum 
               
             
          
           
               
                   
                 Source IP 
                   
               
               
                   
                 Destination IP 
               
               
                   
                 Payload 
               
               
                   
                   
               
             
          
         
       
     
         [0008]      FIG. 1  is a schematic diagram of transferring fragmented packets over a network in the prior art. As shown in  FIG. 1 , the input port of a router N 1  receives a fragmented packet which has been disassembled into three fragments, with frag 1  indicating an initial fragment, and with frag 2  and frag 3  each indicating a non-initial fragment. Assuming an ACL policy based on the transport layer port is configured at the input port of the router NI for complex flow classification of fragmented packets, frag 1  hits the policy since frag 1  has a transport layer port number, and may be processed, e.g., remark, Committed Access Rate (CAR), mirror, etc., according to this policy. Frag 1  has been modified (the priority has been modified or frag 1  has been dropped according to the car configuration) before it is forwarded from the router N 1 . For frag 2  and frag 3 , they do not have a transport layer port number due to the absent of a transport layer packet header in their packets, thus the two non-initial fragments cannot hit the policy and are normally IP forwarded without being processed according to this policy. For example, if a remark based on the port is configured, then it is possible to modify the Type of Service (ToS) field of only the initial fragment rather than the ToS fields of the non-initial fragments. So, for the same flow, the initial fragment is processed differently from the non-initial fragments during the whole forwarding process. Therefore, when all the fragments arrive at the destination, they cannot be parsed correctly, causing difficulty to the processing in the transport layer. 
       SUMMARY 
       [0009]    Accordingly, embodiments of the disclosure provide a method, apparatus and system for complex flow classification of fragmented packets, thereby processing an initial fragment and the non-initial fragments according to a same policy, so as to facilitate the processing in the transport layer. The specific schemes are as follow. 
         [0010]    A method for complex flow classification of fragmented packets includes: 
         [0011]    determining whether a received fragment is an initial fragment; 
         [0012]    if the received fragment is an initial fragment, determining an access control list (ACL) policy matched with the initial fragment based on transport layer information carried in the received initial fragment; storing, in correspondence with the ACL policy, initial fragment information extracted from the initial fragment; and processing the received fragment with the ACL policy; 
         [0013]    if the received fragment is a non-initial fragment, comparing the information of the received non-initial fragment with the stored initial fragment information; retrieving initial fragment information corresponding to the received fragment; and processing the received fragment with the ACL policy corresponding to the initial fragment information. 
         [0014]    An apparatus for complex flow classification of fragmented packets includes: 
         [0015]    a determining module, configured to determine whether a received fragment is an initial fragment; 
         [0016]    an initial fragment processing module, configured to, if the received fragment is an initial fragment, determine an access control list (ACL) policy matched with the initial fragment according to transport layer information carried in the received initial fragment, store initial fragment information extracted from the initial fragment in correspondence with the ACL policy, and process the received fragment with the ACL policy; 
         [0017]    a non-initial fragment processing module, configured to, if the received fragment is a non-initial fragment, compare information of the received non-initial fragment with the stored initial fragment information, retrieve initial fragment information corresponding to the received fragment, and process the received fragment with the ACL policy corresponding to this initial fragment information. 
         [0018]    A system for complex flow classification of fragmented packets includes a packet fragmenting device and a device for complex flow classification of fragmented packets, where: 
         [0019]    the packet fragmenting device is configured to disassemble a packet into fragments and send the fragments to the device for complex flow classification of fragmented packets; 
         [0020]    the device for complex flow classification of fragmented packets is configured to determine whether a received fragment is an initial fragment; and, if the received fragment is an initial fragment, determine an access control list (ACL) policy matched with this initial fragment according to transport layer information carried in the received initial fragment, store initial fragment information extracted from this initial fragment in correspondence with the ACL policy, and process the received fragment with the ACL policy; otherwise, compare information of the received fragment with the stored initial fragment information, retrieve initial fragment information corresponding to the received fragment, and process the received fragment with the ACL policy corresponding to this initial fragment information. 
         [0021]    As can be seen from the above technical schemes that, in embodiments of the disclosure, the ACL policy matched with the initial fragment is determined first, then the initial fragment information in correspondence with the ACL policy is stored, and thereby the corresponding ACL policy of the initial fragment is correlated with the initial fragment; and after receiving a non-initial fragment, the stored initial fragment information is compared with the non-initial fragment information, the initial fragment information corresponding to the non-initial fragment is retrieved, i.e., it is determined which one in the initial fragments recorded previously belongs to the same packet as the non-initial fragment; finally the non-initial fragment is processed with the ACL policy corresponding to the initial fragment. Hence, the non-initial fragments may be processed according to the ACL policy matched with the corresponding initial fragment, thereby effectively solving the problem of inconsistent processing for the initial fragment and its non-initial fragments in complex flow classification of fragmented packets in the networks. 
         [0022]    Further, to distinguish the fragments of different packets in a same data flow, the sequence ID of the packet may further be stored on the basis of storing the initial fragment information. So, for fragments of different packets with the same initial fragment information but hitting different policies due to the different transport layer information, the fragment information can be recorded more accurately, thereby ensuring the accurate processing of the non-initial fragments. Meanwhile, for fragments of different packets with the same initial fragment information and hitting the same policy, the sequence ID of the corresponding initial fragment is stored in correspondence with the same initial fragment information, thereby saving the memory. In addition, the memory space can also be saved by setting a time stamp for each packet. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS  
         [0023]      FIG. 1  is a schematic diagram of transferring fragmented packets over the network in the prior art; 
           [0024]      FIG. 2  is a schematic diagram of transferring different packets of a same data flow; 
           [0025]      FIG. 3  is a schematic diagram of a sequence in which the different fragmented packets shown in  FIG. 2  arrive at the apparatus; 
           [0026]      FIG. 4  is a flowchart of a method for complex flow classification of fragmented packets according to a first embodiment of the disclosure; 
           [0027]      FIG. 5  is a flowchart for periodic detection of fragmented packets according to a second embodiment of the disclosure; 
           [0028]      FIG. 6  is a schematic diagram of a system for complex flow classification of fragmented packets according to a third embodiment of the disclosure; and 
           [0029]      FIG. 7  is a schematic diagram of an apparatus for complex flow classification of fragmented packets according to the third embodiment of the disclosure. 
       
    
    
     DETAILED DESCRIPTION  
       [0030]    Embodiments of the disclosure are further described below in conjunction with, but not limited to, the accompanying drawings and the exemplary embodiments. 
         [0031]    In an embodiment of the invention, packet information is extracted from initial fragments of the fragmented packets, a non-initial fragment is compared with the information extracted from the initial fragments, and a corresponding policy operation is performed according to the comparison result, so that the initial fragment and its non-initial fragments are processed with the same policy action. 
         [0032]    While applying the technical schemes according to an embodiment of the disclosure, an ACL policy based on the transport layer information (e.g., a TCP/UPD port number) is configured for each data flow requiring policy processing. This ACL policy corresponds to a policy entry, including one or more actions that will be performed when this policy is applied. This policy entry is recorded in a policy action table (policy_action_table), and with the TCP/UPD port as a mask. 
         [0033]    For a normal packet, if the port number in the packet matches the port number of the policy, the policy action table is looked up and the packet is processed with normal actions. For a fragmented packet, an initial fragment and the non-initial fragments are processed differently. Specifically, in case of an initial fragment, the initial fragment information is stored and the initial fragment is processed according to the corresponding ACL policy. The stored initial fragment information may include information that distinguishes different data flows, such as the source IP address, the destination IP address, and the transport layer port number of the initial fragment. In case of a non-initial fragment, an initial fragment belonging to the same data flow as this non-initial fragment may be found according to the stored information, and the non-initial fragment may be processed according to the ACL policy corresponding to this initial fragment. 
         [0034]    In addition, for some networking environments, a data flow may pass through different paths. For example, in the network as shown in  FIG. 2 , the apparatus N 1  is configured with packet-by-packet sharing. Thus, two packets of a same data flow go through different paths. The two packets of the same data flow are denoted as pkt 1  and pkt 2 , wherein pkt 1  includes an initial fragment pkt 1 _frag 1  and non-initial fragments pkt 1 _frag 2  and pkt 1 _frag 3 , while pkt 2  includes an initial fragment pkt 2 _frag 1  and non-initial fragments pkt 2 _frag 2  and pkt 2 _frag 3 . The pkt 1  and pkt 2  are fragmented on N 2  and N 3 , respectively. Thus, when they arrive at N 4  and proceed from N 4  to N 5 , the arriving sequence of these fragments may be as shown in  FIG. 3 . Since the initial fragments of the two packets arrive first, and the two packets have identical information such as the source IP address (SIP) and the destination IP address (DIP) except the sequence ID (SequenceID) information, the SequenceID information must be considered in order to distinguish the non-initial fragments corresponding to different initial fragments. Therefore, embodiments of the disclosure preferably store the sequence ID information while storing the initial fragment information. 
         [0035]    The specific modes for carrying out embodiments of the disclosure are further described in detail below with the exemplary embodiments. 
       EMBODIMENT 1  
       [0036]    Taking the processing of the fragments of the two packets shown in  FIG. 3  as an example, this embodiment illustrates a specific mode for implementing embodiments of the disclosure. 
         [0037]    In this embodiment, whenever an initial fragment of the fragmented packets is received, a policy key value is constructed with the corresponding transport layer information (e.g., the TCP/UDP port number) extracted from this fragment, and this value is used as an index to look up the policy action table for a policy entry that matches this policy key value. If a matched policy entry is found, this policy is hit. At this time, the source IP address (SIP), the destination IP address (DIP), the transport layer protocol number and a fragment flag bit frag_flag of the initial fragment are written into a fragment information key table as a fragment information key value, the address of the matched policy entry is written into a fragment information table (frag_infor_table) corresponding to this fragment information key value as an action table index (action_index), and the sequence ID (sequence_id) is written into a sequence ID key table in correspondence to the fragment information table. Then the policy action table (policy_action_table) is looked up for a matched policy entry according to the action table index (action_index), and the fragments are processed according to the actions (filter, remark, CAR, etc.) which are recorded in the policy entry and are configured by the policy action table. 
         [0038]    The reasons for extracting the above information are as follows. 
         [0039]    Since a non-initial fragment only has an IP header and cannot match the transport layer related parameters configured by the policy, it should not look up the policy action table (policy_action_table) for the non-initial fragment by using a constructed policy key value as for a normal packet. For a non-initial fragment, it needs to determine whether the non-initial fragment header matches the information (the source IP address (SIP), the destination IP address (DIP), the protocol number and the fragment flag bit frag_flag described above) extracted from the initial fragment, so as to determine whether they belong to the same data flow. If they belong to the same data flow, the initial fragment corresponding to the non-initial fragment will be found according to the sequence ID in the sequence ID key table. Thus, it is possible to look up the action table using the action table index in the corresponding fragment information entry, and take the corresponding action. 
         [0040]    In this embodiment, the information of the initial fragments is stored in terms of a table, and the fragment information is stored in the fragment information key table. However, the specific applications of embodiments of the disclosure are not limited to the form of a table, and the relationships between the initial fragment information and the non-initial fragment information may be designed as needed. 
         [0041]      FIG. 4  is a detailed flowchart of a method for complex flow classification of fragmented packets according to Embodiment 1 of the disclosure. As shown in  FIG. 4 , this method includes the following steps. 
         [0042]    Step  101 : On arrival of a fragment at the router, it is determined whether the fragment is an initial fragment. If the fragment is an initial fragment, the process proceeds to step  102 ; otherwise, the process proceeds to step  112 . 
         [0043]    Whether the fragment is an initial fragment is determined by detecting whether the fragment has a transport layer packet header (with a transport layer port number). The fragment is an initial fragment if it has a transport layer packet header; otherwise, it is a non-initial fragment. 
         [0044]    Step  102 : Packet information (a source IP address (SIP), a destination IP address (DIP), a transport layer protocol number and a fragment flag bit frag_flag) is extracted from the initial fragment, and it is determined whether the packet information hits the policy action table. If the packet information hits the policy action table, the process proceeds to step  103 ; otherwise, the process proceeds to step  118 . 
         [0045]    The data structure of the policy key table is as shown in Table 3. 
         [0000]    
       
         
               
               
               
               
               
               
               
               
             
               
               
               
               
               
               
               
               
             
           
               
                 TABLE 3 
               
               
                   
               
               
                   
                   
                   
                   
                   
                   
                 Tcp/ 
                 trans- 
               
               
                   
                   
                   
                   
                   
                   
                 Udp 
                 port 
               
               
                   
                   
                   
                   
                   
                 pro- 
                 port 
                 layer 
               
               
                 Rule_id 
                 flag 
                 tos 
                 sip 
                 dip 
                 tocol 
                 number 
                 flag 
               
               
                   
               
             
             
               
                   
               
             
          
           
               
                   
                 masked 
                 masked 
                 masked 
                 masked 
                   
                   
                   
               
               
                   
                   
               
             
          
         
       
     
         [0046]    Since the policy only configures an ACL policy table based on the transport layer, it is necessary to extract packet information from the initial fragment and look up the policy table merely according to the Rule_id, the transport layer port number and other information of the transport layer in the fragment, while the other portions are masked. 
         [0047]    Step  103 : The fragment information key table is searched for the initial fragment information that is the same as the received initial fragment. If the initial fragment information that is the same as the received initial fragment is not found, the process proceeds to step  104 ; otherwise, the process proceeds to step  106 . 
         [0048]    Step  104 : The information of the initial fragment is written into the fragment information key table in the format of Table 4. 
         [0049]    The data structure of the fragment information kev table is as shown in Table 4. 
         [0000]    
       
         
               
               
               
               
               
               
               
               
             
           
               
                 TABLE 4 
               
               
                   
               
             
             
               
                 Rule_id 
                 Valid_flag 
                 sip 
                 dip 
                 protocol 
                 Frag_flag 
                 ttl 
                 tos 
               
               
                   
               
             
          
         
       
     
         [0050]    The meanings for the specific fields are given as follow: 
         [0051]    Valid_flag: represents a valid flag bit of the key table. If this flag bit is 0, it indicates that the entry is invalid; if this flag bit is 1, it indicates that the entry is valid. 
         [0052]    Rule_id: represents ACL configuration rule ID. 
         [0053]    The other fields are extracted from the packet header, in a similar way as extracted from the IP packet header. The extracted information is stored in the fragment information key table as a fragment information key value. 
         [0054]    Step  105 : The sequence ID in the initial fragment header is written into the sequence ID key table in correspondence with the fragment information key value determined in step  103 . 
         [0055]    The data structure of the sequence ID key table is as shown in Table 6. 
         [0000]                                    TABLE 6                           Rule_id   Valid_flag   Sequence_id                        
wherein: Rule_id: represents the ACL configuration rule ID;
 
         [0056]    if the value of Valid_flag is 1, it indicates that the entry is valid; and if this flag bit is 0, it indicates that the entry is invalid; 
         [0057]    Sequence_id is the unique flag to determine whether a non-initial fragment belongs to the same packet as the initial fragment. 
         [0058]    In this embodiment, to distinguish the situations where packets of the same data flow go through different paths as shown in  FIG. 2 , it preferably stores the sequence ID information in this step to distinguish different packets of the same data flow. However, in a networking environment where the same data flow does not go through different paths, this step may be omitted. 
         [0059]    Step  106 : A time stamp of the initial fragment is written into the sequence ID table corresponding to the sequence ID key table, and the process proceed to step  110 . 
         [0060]    The data structure of the sequence ID table is as shown in Table 7: 
         [0000]                    TABLE 7                   Pkt_timestamp                    
wherein Pkt_timestamp represents the time stamp written after the first packet match action, and is used for periodic detection.
 
         [0061]    Generally, the time period of storing the initial fragment for a packet is limited to some extent. The time stamp written in this step may be used to control a packet. If the initial fragment information has been stored for a time period longer than a given time without receiving the final fragment of the packet, then the stored initial fragment information may be dropped. 
         [0062]    Step  107 : It is further determined whether the sequence ID key table corresponding to the found initial fragment information contains the initial fragment ID received in step  101 . If such a sequence ID key table is found, the process proceeds to step  108 ; otherwise, the process proceeds to step  109 . 
         [0063]    Since the initial fragment information same as the received initial fragment is found in step  103 , which means that some entry in the fragment information key table is found, then the searching of the sequence ID key table corresponding to this entry in step  107  for the received initial fragment ID continues in this step. The initial fragment ID is the sequence ID information of the packet. If the initial fragment ID is found, then this ID has been used before and its corresponding time stamp needs to be updated; otherwise, a sequence ID corresponding to the initial fragment is created in the sequence ID key table corresponding to the fragment information key value, and the corresponding time stamp is stored. 
         [0064]    Step  108 : The time stamp, corresponding to the sequence ID key that is found, is updated; and the process proceeds to step  110 . 
         [0065]    Step  109 : The sequence ID of the initial fragment is written into the sequence ID key table corresponding to the fragment information key value that is found, the time stamp is recorded, and the process proceeds to step  110 . 
         [0066]    Step  110 : The action table index corresponding to the policy that is hit in step  102  is written into the fragment information table corresponding to the fragment information key value stored in step  103 . 
         [0067]    In this step, the action table index corresponding to the policy that is hit is the address of the policy entry. 
         [0068]    The data structure of the fragment information table is as shown in Table 5: 
         [0000]    
       
         
               
             
           
               
                 TABLE 5 
               
               
                   
               
             
             
               
                 Action_index 
               
               
                   
               
             
          
         
       
     
         [0069]    The field Action_index in this table is an action table index to find a specified policy entry in the policy action table, and a corresponding action (filter, remark, CAR . . . ) may be performed according to the content of this entry. 
         [0070]    Step  111 : The policy action table is searched according to the action table index, and the initial fragment is processed correspondingly. 
         [0071]    Step  112 : Packet information is extracted from the IP header of a non-initial fragment, and it is determined whether it hits the fragment information key table. If it hits, it indicates that the non-initial fragment belongs to the same data flow packet as the fragment in the table that is hit, and a fragment information entry corresponding to the fragment information key entry will be returned, and then the process proceeds to step  113 . Otherwise, it indicates that the non-initial fragment does not have a same data flow in the fragment information key table, i.e., there is no matched ACL policy, and then the process proceeds to step  118 . 
         [0072]    Step  113 : A sequence ID key value is constructed according to the sequence ID in the non-initial fragment, and it is checked whether it hits the entry in the sequence ID key table. If it hits the entry, the process proceeds to step  114 ; otherwise, the process proceeds to step  118 . 
         [0073]    In this step, hitting the entry means that the same sequence ID key value is found in the sequence ID key table. 
         [0074]    Step  114 : It is determined whether the non-initial fragment is the final fragment of the packet, and if it is the final fragment of the packet, the process proceeds to step  115 ; otherwise, the process proceeds to step  116 . 
         [0075]    Step  115 : The valid flag bit in the corresponding sequence ID key table is cleared, which indicates that the sequence ID entry has been released, and then the process proceeds to step  117 . 
         [0076]    Step  116 : The corresponding time stamp in the sequence ID table is updated, and then the process proceeds to step  117 . 
         [0077]    Step  117 : The policy action table is searched according to the action table index, the initial fragment is processed correspondingly, and then the processing terminates. 
         [0078]    Step  118 : Performing forwarding process normally without complex flow classification policy processing. 
         [0079]    The relationships among the entries of the policy table, the fragment information table and the sequence ID key table are as follow: 
         [0000]    
       
         
               
             
           
               
                   
               
             
             
               
                 
                   
                             
                     
                         
                         
                     
                   
                 
               
               
                   
               
             
          
         
       
     
         [0080]    In consideration that the fragments of the same flow should arrive after an interval of 8 packets, an experiential value is chosen while designing, and thus each flow may retain 8 fragments at a moment. Of course, it may be designated according to the practice about how many fragments may be retained in a flow. 
         [0081]    The entries of the fragment information key table are corresponding to the entries of the fragment information table one by one, as well as the entries of the sequence ID key table with the entries of the sequence ID table. In implementation, a key value is constructed to search the corresponding key table; and if the corresponding key table is found by using the constructed key value, an entry of the information table or sequence table corresponding to the entry of the key table will be returned. 
       EMBODIMENT 2  
       [0082]    A middle or final fragment of a fragmented packet may be lost in a congested network. In the case that a middle fragment is lost, this is unperceivable for a router if the packet is fragmented, but would be perceived when the packet in a higher layer is reproduced after the fragments arriving at the terminal, and will be processed in accordance with some mechanism (such as a retransmission mechanism) in this layer. In the case that the final fragment is lost, the fragment information table (frag_info_table) and the sequence ID table (sequenceID_table) cannot obtain the final fragment, the resources are occupied and impossible to be released. Hence, the space cannot be allocated to other flows. Accordingly, embodiments of the disclosure define a time stamp for each entry in the sequence ID table. If this sequence ID is not released after a certain time period, this fragment is considered as having been dropped, thus the corresponding sequence ID will be aged, as well as the corresponding entry in the fragment information table. 
         [0083]    Referring to  FIG. 5 , the detection and updating process for the fragment information table in a congested network is as follow. 
         [0084]    Step  201 : The valid fragment information key tables (if the valid flag is set to 1, it indicates that this entry is valid) is detected periodically and in a polling way. For the valid fragment information key tables, the sequence ID tables under each fragment information table is detected (by setting the valid flag bit in the sequence ID key value structure to 1 to determine whether it matches the sequence ID key) to determine whether an entry is hit. An entry is valid if it is hit, and then the process proceeds to step  202 . If none entry is hit, then all sequence ID entries under the fragment information table are invalid, and then the process proceeds to step  203 . 
         [0085]    Step  202 : It is examined whether the time stamp in the entry exceeds a threshold, and the process proceeds to step  204  if it exceeds the threshold; otherwise the process proceeds to step  205 . 
         [0086]    Step  203 : The corresponding fragment information table is released. 
         [0087]    Step  204 : The Valid_flag in the corresponding sequence ID key table is set to 0, indicating that this sequence ID entry is invalid. 
         [0088]    Step  205 : The time stamp is updated (during the transmission of each packet, there is a hardware clock timer to update the time stamp based on the display of the clock timer). If the entries in all sequence ID key tables under a fragment information table are invalid, this information table is released by clearing the valid flag bit in the fragment information key table. 
         [0089]    The above method according to an embodiment of the disclosure is significant for extending applications of QoS in networks. 
       EMBODIMENT 3   
       [0090]    Embodiments of the disclosure also provide an apparatus and system for complex flow classification of fragmented packets, which will be described in this embodiment. 
         [0091]      FIG. 6  is a specific block diagram of a system for complex flow classification of fragmented packets in this embodiment, which may be employed to implement the methods illustrated in  FIG. 4  and  FIG. 5 . As shown in  FIG. 6 , this system includes a packet fragmenting device and a device for complex flow classification of fragmented packets. 
         [0092]    In this system, the packet fragmenting device is configured to disassemble the packets and send the fragments to the device for complex flow classification of fragmented packets. 
         [0093]    The device for complex flow classification of fragmented packets is configured to determine whether a received fragment is an initial fragment, and if it is an initial fragment, determine an access control list (ACL) policy matched with this initial fragment based on the transport layer information carried in the received initial fragment, store the initial fragment information extracted from this initial fragment in correspondence with the ACL policy, and process the received fragment with this ACL policy; otherwise, compare the information of the received fragment with the stored initial fragment information to find the initial fragment information corresponding to the received fragment, and process the received fragment with the ACL policy corresponding to this initial fragment information. 
         [0094]      FIG. 7  is a specific block diagram of an apparatus for complex flow classification of fragmented packets in this embodiment, which may be applied in the system illustrated in  FIG. 6 . As shown in  FIG. 7 , the apparatus for complex flow classification of fragmented packets in this embodiment includes the following modules: 
         [0095]    a determining module, configured to determine whether a received fragment is an initial fragment; 
         [0096]    an initial fragment processing module, configured to, if the received fragment is an initial fragment, determine an access control list (ACL) policy matched with the initial fragment according to the transport layer information carried in the received initial fragment, store the initial fragment information extracted from the initial fragment in correspondence with the ACL policy, and process the received fragment with the ACL policy; and 
         [0097]    a non-initial fragment processing module, configured to, if the received fragment is a non-initial fragment, compare the information of the received fragment with the stored initial fragment information, retrieve the initial fragment information corresponding to the received fragment, and process the received fragment with the ACL policy corresponding to the initial fragment information. 
         [0098]    The initial fragment processing module includes: 
         [0099]    an initial fragment processing unit, configured to: extract packet information from the initial fragment and detect whether it hits a preset policy action table, if it hits, store the packet information and the sequence ID of the initial fragment, and process the fragment according to the policy entry that is hit; otherwise, forward the fragment directly without complex flow classification. 
         [0100]    The non-initial fragment processing module includes: 
         [0101]    a non-initial fragment processing unit, configured to: extract packet information and sequence ID from the non-initial fragment to determine whether they hit the fragment information and sequence ID of initial fragments that are stored, and process the non-initial fragment as an initial fragment that is hit; otherwise, forward the fragment directly without complex flow classification. 
         [0102]    To reserve the memory, the non-initial fragment processing unit further includes: 
         [0103]    a non-initial fragment processing sub-unit, configured to determine whether the non-initial fragment is the final fragment of the fragmented packet, and delete the stored sequence ID if it is the final fragment; otherwise, retain the sequence ID. 
         [0104]    The initial fragment processing unit further includes: 
         [0105]    a time stamp setting unit, configured to set a time stamp for each sequence ID. 
         [0106]    Accordingly, the non-initial fragment processing unit further includes: 
         [0107]    a periodic detection sub-unit, configured to periodically detect whether the time stamp exceeds a threshold, and set the corresponding sequence ID of the time stamp as invalid if it exceeds the threshold; otherwise update the time stamp and continue detecting, and delete all the sequence IDs of a packet when all sequence IDs of the packet are invalid. 
         [0108]    The embodiments described above are merely some of the preferred embodiments of the disclosure, the variations and alternatives made within the scope of the technical schemes of the disclosure by those skilled in the art should be encompassed within the scope of the disclosure.