Apparatus and method for classifying data packet flows

• US 6,917,588 B1
• Filed: 05/16/2000
• Issued: 07/12/2005
• Est. Priority Date: 05/16/2000
• Status: Expired due to Fees

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Nandy, Biswajit B., Seddigh, Nabil N., Liu, Yajun, Bennett, Don W., Cao, Carl F., Wang, Dabin
• Primary Examiner(s): Ton, Dang
• Assistant Examiner(s): MEHRA, INDER P
• Application Number:
  US09/571,160
• Time in Patent Office: 1,883 Days
• Field of Search: 370/230.1, 370/253, 370/395.21, 370412-416, 370/468, 370/229, 370/231.1, 370/395.3, 370/395.42, 370/395.43, 370/410, 370/232, 370/395.1, 370/395.4
• US Class Current: 370/230.1
• CPC Class Codes: H04L 45/742 Route cache; Operation thereof
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers

Abstract

Currently there are two techniques used to classify data packet flows, those techniques being static and dynamic. A proper combination of these two techniques can allow for the advantages of both techniques to be gained while reducing their respective disadvantages. With this combined flow classification method a flow is classified initially with the use of a static classification method while, at the same time, a dynamic classification method is initiated. If at any point during the dynamic classification method, the classifications derived from the static and dynamic algorithms converge, the flow'"'"'s classification is henceforth assigned by the dynamic classification method. If a predetermined number of packets or length of time that would be required for the dynamic and static classification algorithms to converge is exceeded, the flow'"'"'s classification, once again, is henceforth assigned by the dynamic classification method. This allows the initial classification of the flow to occur quickly with the static classification method and the accuracy of dynamic flow classification techniques to take over once such a classification is deemed accurate.

Claims

1. A computing apparatus arranged to receive a flow of data packets, the computing apparatus comprising:

static flow classification logic that operates to determine a static classification for the flow using static information corresponding to at least one of the packets;

dynamic flow classification logic that operates to determine a dynamic classification for the flow using dynamic information corresponding to a plurality of the packets within the flow; and

classification selection logic that operates to initially assign the static classifications to the flow and subsequently assign the dynamic classification to the flow once at least one transitional test is passed.

2. A computing apparatus according to claim 1, wherein the transitional test is passed when the dynamic classification becomes equal to the static classification.

3. A computing apparatus according to claim 1, wherein the transitional test is passed when a predetermined number of packets within the flow have been received.

4. A computing apparatus according to claim 3, wherein the predetermined number of packets is equal to an estimated minimum number of packets required for the dynamic classification to become equal with the static classification.

5. A computing apparatus according to claim 3, wherein the predetermined number of packets is equal to a predetermined decision factor multiplied by an estimated minimum number of packets required for the dynamic classification to become equal to the static classification;

and

wherein the predetermined decision factor is between one and a maximum tolerance factor in which the estimated minimum number of packets could be in error by.

6. A computing apparatus according to claim 1, wherein the transitional test is passed when a predetermined time period has expired from initially receiving packets of the flow.

7. A computing apparatus according to claim 6, wherein the predetermined time period comprises an estimate of a time required for the dynamic classification to become equal to the static classification.

8. A computing apparatus according to claim 6, wherein the predetermined time period comprises a predetermined decision factor multiplied by an estimate of a time required for the dynamic classification to become equal to the static classification;

and

wherein the predetermined decision factor is between one and a maximum tolerance factor in which the estimate of the time could be in error by.

9. A computing apparatus according to claim 1, wherein the at least one transitional test is passed when at least one of first and second transitional tests is passed;

and

wherein the first transitional test is passed when the dynamic classification becomes equal to the static classification and the second transitional test is passed when a predetermined number of packets within the flow have been received.

10. A computing apparatus according to claim 9, wherein the predetermined number of packets is equal to an estimated minimum number of packets required for the dynamic classification to become equal to the static classification.

11. A computing apparatus according to claim 9, wherein the predetermined number of packets is equal to a predetermined decision factor multiplied by an estimated minimum number of packets required for the dynamic classification to become equal to the static classification;

and

wherein the predetermined decision factor is between one and a maximum tolerance factor in which the estimated minimum number of packets could be in error by.

12. A computing apparatus according to claim 1, wherein the at least one transitional test is passed when at least one of first and second transitional tests are passed;

and

wherein the first transitional test is passed when the dynamic and static classifications become equal and the second transitional test is passed when a predetermined time period has expired from initially receiving packets of the flow.

13. A computing apparatus according to claim 12, wherein the predetermined time period comprises an estimate of a time required for the dynamic classification to become equal to the static classification.

14. A computing apparatus according to claim 12, wherein the predetermined time period comprises a predetermined decision factor multiplied by an estimate of a time required for the dynamic classification to become equal to the static classification;

and

wherein the predetermined decision factor is between one and a maximum tolerance factor in which the estimate of the time could be in error by.

15. A computing apparatus according to claim 1, wherein the static information corresponding to at least one data packet of the flow comprises protocol header information.

16. A computing apparatus according to claim 1, wherein the data packets within the flow are Transmission Control Protocol (TCP) packets.

17. A computing apparatus arranged to receive a flow of data packets, the computing apparatus comprising:

static flow classification logic that operates to determine a static classification for the flow using static information corresponding to at least one of the packets;

dynamic flow classification logic that operates to determine a dynamic classification for the flow using dynamic information corresponding to a plurality of the packets within the flow; and

classification selection logic that operates to initially determine if the static and dynamic classifications are equal;

if the static and dynamic classifications are initially equal, assign the dynamic classification to the flow; and

, if the static and dynamic classifications are not initially equal, initially assign the static classification to the flow and subsequently assign the dynamic classification to the flow once at least one transitional test is passed.

18. A method for assigning a flow classification to a flow of data packets, the method comprising:

determining a static classification for the flow using static information corresponding to at least one of the packets;

determine a dynamic classification for the flow using dynamic information corresponding to a plurality of the packets within the flow;

initially assigning the static classification to the flow; and

subsequently assigning the dynamic classification to the flow once at least one transitional test is passed.

19. A method according to claim 18, wherein the transitional test is passed when the dynamic classification becomes equal to the static classification.

20. A method according to claim 18, wherein the transitional test is passed when a predetermined number of packets within the flow have been received.

21. A method according to claim 18, wherein the transitional test is passed when a predetermined time period has expired from initially receiving packets of the flow.

22. A method according to claim 18, wherein the at least one transitional test is passed when at least one of first and second transitional tests is passed;

and

wherein the first transitional test is passed when the dynamic classification becomes equal to the static classification and the second transitional test is passed when a predetermined number of packets within the flow have been received.

23. A method according to claim 22, wherein the predetermined number of packets is equal to an estimated minimum number of packets required for the dynamic classification to become equal to the static classification.

24. A method according to claim 22, wherein the predetermined number of packets is equal to a predetermined decision factor multiplied by an estimated minimum number of packets required for the dynamic classification to become equal to the static classification;

and

wherein the predetermined decision factor is between one and a maximum tolerance factor in which the estimated minimum number of packets could be in error by.

25. A method according to claim 18, wherein the at least one transitional test is passed when at least one of first and second transitional tests is passed;

and

wherein the first transitional test is passed when the dynamic and static classifications become equal and the second transitional test is passed when a predetermined time period has expired from initially receiving packets of the flow.

26. A method according to claim 25, wherein the predetermined time period comprises an estimate of a time required for the dynamic classification to become equal to the static classification.

27. A method according to claim 25, wherein the predetermined time period comprises a predetermined decision factor multiplied by an estimate of a time required for the dynamic classification to become equal to the static classification;

and

wherein the predetermined decision factor is between one and a maximum tolerance factor in which the estimate of the time could be in error by.

28. A method for assigning a flow classification to a flow of data packets, the method comprising:

determining a static classification for the flow using static information corresponding to at least one of the packets;

determining a dynamic classification for the flow using dynamic information corresponding to a plurality of the packets within the flow;

determining if the dynamic and static classifications are initially equal;

if the dynamic and static classifications are initially equal, assigning the dynamic classification to the flow, and

if the dynamic and static classifications are not initially equal, initially assigning the static classification to the flow and subsequently assigning the dynamic classification to the flow once at least one transitional test is passed.