Micro-flow management

• US 6,574,195 B2
• Filed: 04/19/2000
• Issued: 06/03/2003
• Est. Priority Date: 04/19/2000
• Status: Expired due to Term

• Current Assignee: Electronics and Telecommunications Research Institute, Sable Networks, Inc.
• Original Assignee: Caspian Networks, Inc.
• Inventors: Roberts, Lawrence G.
• Primary Examiner(s): TON, DANG T
• Application Number:
  US09/552,278
• Publication Number:
  US 20020057699A1
• Time in Patent Office: 1,140 Days
• Field of Search: 370/335,395,401,229,230,231,232,233,234,235,237,411,412-418,465,351,352,444
• US Class Current: 370/235
• CPC Class Codes: H04L 41/5019 Ensuring fulfilment of SLA
• CPC Class Codes: H04L 41/5045 Making service definitions prior to deployment
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/302 Route determination based on requested QoS
• CPC Class Codes: H04L 45/38 Flow based routing
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/22 Traffic shaping
• CPC Class Codes: H04L 47/2408 for supporting different services, e.g. a differentiated services [DiffServ] type of service
• CPC Class Codes: H04L 47/2433 Allocation of priorities to traffic types
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/2483 involving identification of individual flows
• CPC Class Codes: H04L 47/283 in response to processing delays, e.g. caused by jitter or round trip time [RTT]
• CPC Class Codes: H04L 47/30 in combination with information about buffer occupancy at either end or at transit nodes

Abstract

New switching technology relies upon state information for providing a previously unavailable degree of quality of service. In particular, by providing the ability to give service guarantees to uniquely identifiable sets of packets (“micro-flows”), different qualities of service can be offered for each transmission. The QoS associated with each micro-flow is characterized by a set of descriptors. These descriptors are communicated to each switch by the first packet of the micro-flow associated with the descriptors.

Claims

1. A method for routing a micro-flow in a network comprising a plurality of network hops, the method comprising the steps of:

receiving at a network hop a first data packet;

establishing the first data packet as corresponding to a given micro flow;

extracting a set of quality of service characteristics from the first data packet and retaining the set of quality of service characteristics in association with the given micro flow;

receiving a second data packet;

determining whether the second data packet corresponds to the given micro flow; and

automatically associating the set of quality of service characteristics to the second data packet where it is determined that the second data packet corresponds to the given micro flow.

2. The method of claim 1, wherein determining whether the second data packet corresponds to the given micro flow includes examining a set of identifying information found in the second data packet.

3. The method of claim 1, further comprising:

maintaining a flow block that stores the set of quality of service characteristics.

4. The method of claim 3, wherein the flow block is maintained in a flow block table that associates the set of quality of service characteristics to packets in the given micro flow.

5. The method of claim 4, wherein network layer and transport layer information are retrieved from data packets and used to correlate them to the given micro flow.

6. The method of claim 5, wherein a hash key is generated from the network layer and transport layer information, and the hash key is used to identify the flow block in the flow block table.

7. The method of claim 1, wherein the set of quality of service characteristics includes a transmission rate constraint.

8. The method of claim 1, wherein the set of quality of service characteristics includes a delay variation constraint.

9. The method of claim 7, wherein the transmission rate constraint is compared to a determined rate for packets in the given micro flow, and wherein the second data packet is discarded where the determined rate for the second data packet exceeds the transmission rate constraint.

10. The method of claim 9, wherein the determined rate is derived from an arrival rate for packets in the given micro flow into a switch corresponding to the network hop.

11. The method of claim 1, further comprising:

using the set of quality of service characteristics to selectively apply a queuing technique to the given micro flow to adjust the transmission rate of the given micro flow.

12. The method of claim 11, wherein the queuing technique includes weighted fair queuing.

13. The method of claim 9, further comprising:

retrieving path information for the given micro flow prior to comparing the determined rate to the transmission rate constraint.

14. The method of claim 1, further comprising:

after the first data packet is received at the network hop, identifying a next network hop by determining whether a candidate network hop can accommodate transmission of packets in the given micro flow according to the set of quality of service characteristics.

15. The method of claim 1, wherein the first data packet and the second data packet are IP packets.

16. The method of claim 1, wherein the first data packet and the second data packet are deencapsulated after they are received from a trunk line.

17. The method of claim 1, further comprising:

extracting policy information from the first data packet; and

adjusting the value of at least one of the set of quality of service characteristics based upon the extracted policy information.

18. The method of claim 1, wherein extracting the set of quality of service characteristics comprises extracting layer information from the first data packet, and determining the set of quality of service characteristics from stored information relating quality of service characteristics to layer information.

19. A line card for routing a micro-flow in a network comprising a plurality of network hops, the line card comprising the steps of:

an interface, configured to receive at a network hop a first data packet and a second data packet;

a micro flow classifier, in operative communication with the interface, configured to establish the first data packet as corresponding to a given micro flow, extract a set of quality of service characteristics from the first data packet; and

a micro flow recognizer, in operative communication with the interface and the micro flow classifier, configured to retain the set of quality of service characteristics in association with the given micro flow, determine whether the second data packet corresponds to the given micro flow, and automatically associate the set of quality of service characteristics to the second data packet where it is determined that the second data packet corresponds to the given micro flow.

20. The line card of claim 19, wherein the micro flow recognizer determines whether the second data packet corresponds to the given micro flow by examining a set of information found in the second data packet.

21. The line card of claim 19, further comprising:

a flow block table, in operative communication with the micro flow recognizer, configured to maintain a flow block that stores the set of quality of service characteristics.

22. The line card of claim 21, wherein the flow block table associates the set of quality of service characteristics to packets in the given micro flow.

23. The line card of claim 22, wherein network layer and transport layer information are retrieved from data packets and used to correlate them to the given micro flow.

24. The line card of claim 23, wherein a hash key is generated from the network layer and transport layer information, and the hash key is used to identify the flow block in the flow block table.

25. The line card of claim 19, wherein the set of quality of service characteristics includes a transmission rate constraint.

26. The line card of claim 19, wherein the set of quality of service characteristics includes a delay variation constraint.

27. The line card of claim 25, further comprising:

a policing scheduler, configured to discard the second data packet where the determined rate for the second data packet exceeds the transmission rate constraint.

28. The line card of claim 27, wherein the determined rate is derived from an arrival rate for packets in the given micro flow into a switch corresponding to the network hop.

29. The line card of claim 19, wherein the set of quality of service characteristics are used to selectively apply a queuing technique to the given micro flow to adjust the transmission rate of the given micro flow.

30. The line card of claim 29, wherein the queuing technique includes weighted fair queuing.

31. The line card of claim 25, wherein path information for the given micro flow is retrieved prior to comparing the determined rate to the transmission rate constraint.

32. The line card of claim 19, further comprising:

an egress micro flow manager, configured to identify a next network hop by determining whether a candidate network hop can accommodate transmission of packets in the given micro flow according to the set of quality of service characteristics.

33. The line card of claim 19, wherein the first data packet and the second data packet are IP packets.

34. The line card of claim 19, wherein the first data packet and the second data packet are deencapsulated after they are received from a trunk line.

35. The line card of claim 19, wherein the micro flow classifier extracts policy information from the first data packet, and adjusts the value of at least one of the set of quality of service characteristics based upon the extracted policy information.

36. The line card of claim 19, wherein extracting the set of quality of service characteristics comprises extracting layer information from the first data packet, and determining the set of quality of service characteristics from stored information relating quality of service characteristics to layer information.

37. A apparatus for routing a micro-flow in a network comprising a plurality of network hops, the apparatus comprising the steps of:

means for receiving at a network hop a first data packet and a second data packet;

means for establishing the first data packet as corresponding to a given micro flow and extracting a set of quality of service characteristics from the first data packet; and

means for determining whether the second data packet corresponds to the given micro flow by retaining the set of quality of service characteristics in association with the given micro flow, and automatically associating the set of quality of service characteristics to the second data packet where it is determined that the second data packet corresponds to the given micro flow.

38. The apparatus of claim 37, wherein the means for determining determines whether the second data packet corresponds to the given micro flow by examining a set of identifying information found in the second data packet.

39. The apparatus of claim 37, further comprising:

a flow block table, for maintaining a flow block that stores the set of quality of service characteristics.

40. The apparatus of claim 39, wherein the flow block table associates the set of quality of service characteristics to packets in the given micro flow.

41. The apparatus of claim 40, wherein network layer and transport layer information are retrieved from data packets and used to correlate them to the given micro flow.

42. The apparatus of claim 41, wherein a hash key is generated from the network layer and transport layer information, and the hash key is used to identify the flow block in the flow block table.

43. The apparatus of claim 37, wherein the set of quality of service characteristics includes a transmission rate constraint.

44. The apparatus of claim 37, wherein the set of quality of service characteristics includes a delay variation constraint.

45. The apparatus of claim 43, further comprising:

means for discarding the second data packet where the determined rate for the second data packet exceeds the transmission rate constraint.

46. The apparatus of claim 45, wherein the determined rate is derived from an arrival rate for packets in the given micro flow into a switch corresponding to the network hop.

47. The apparatus of claim 37, wherein the set of quality of service characteristics are used to selectively apply a queuing technique to the given micro flow to adjust the transmission rate of the given micro flow.

48. The apparatus of claim 47, wherein the queuing technique includes weighted fair queuing.

49. The apparatus of claim 45, wherein path information for the given micro flow is retrieved prior to comparing the determined rate to the transmission rate constraint.

50. The apparatus of claim 37, further comprising:

means for determining whether a candidate network hop can accommodate transmission of packets in the given micro flow according to the set of quality of service characteristics.

51. The apparatus of claim 37, wherein the first data packet and the second data packet are IP packets.

52. The apparatus of claim 37, wherein the first data packet and the second data packet are deencapsulated after they are receive from a trunk line.

53. The apparatus of claim 37, wherein the means for establishing extracts policy information from the first data packet, and adjusts the value of at least one of the set of quality of service characteristics based upon the extracted policy information.

54. The apparatus of claim 37, wherein extracting the set of quality of service characteristics comprises extracting layer information from the first data packet, and determining the set of quality of service characteristics from stored information relating quality of service characteristics to layer information.