Micro-flow management

• US 20020057699A1
• Filed: 04/19/2000
• Published: 05/16/2002
• Est. Priority Date: 04/19/2000
• Status: Active Grant

• Current Assignee: Electronics and Telecommunications Research Institute, Sable Networks, Inc.
• Original Assignee: Caspian Networks, Inc.
• Inventors: Roberts, Lawrence G.
• Granted Patent: US 6,574,195 B2
• Time in Patent Office: Days
• US Class Current: 370/395.32
• 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 micro-flow manager comprising:

a micro-flow recognizer adapted to receive a first data signal and to identify a flow block corresponding to the first data signal; and

a scheduler, coupled to the micro-flow classifier, adapted to trigger the transmission of a second data signal corresponding to the identified flow block associated with the first data signal.

2. The micro-flow manager of claim 1, wherein the first data signal is a micro-flow data signal.

3. The micro-flow manager of claim 1, wherein the first data signal is a data packet signal.

4. The micro-flow manager of claim 1, wherein the first data signal is an asynchronous transfer mode cell signal.

5. The micro-flow manager of claim 1, wherein the first data signal is a frame relay signal.

6. The micro-flow manager of claim 1, wherein the second data signal is a micro-flow data signal.

7. The micro-flow manager of claim 1 further comprising a micro-flow classifier, coupled to the micro-flow recognizer and to the scheduler, adapted to respond to the identification by the micro-flow recognizer of a flow block corresponding to the first data signal by retrieving state information from the identified flow block and constructing the second data signal based upon said state information and adapted to respond to the failure to identify a flow block corresponding to the first data signal by retrieving information from the first data signal, creating a new flow block and constructing the second data signal based upon the state information, said state information corresponds to the retrieved information from the first data signal.

8. The micro-flow manager of claim 1 further comprising a network trunk line interface, coupled to the micro-flow recognizer, adapted to reformat the first data signal.

9. The micro-flow manager of claim 1 further comprising a network trunk line interface, coupled to the micro-flow recognizer, adapted to reformat the second data signal.

10. A micro-flow linecard comprising:

a memory including a flow block table, wherein said flow block table includes a flow block including state information; and

an ingress micro-flow manager, coupled to the memory, adapted to receive a data signal and adapted to transmit a micro-flow data signal corresponding to the flow block.

11. The linecard of claim 10, wherein said data signal is a micro-flow data signal.

12. The linecard of claim 10, wherein said data signal is a data packet signal.

13. The linecard of claim 10 further comprising an egress micro-flow manager, coupled to the memory, adapted to receive a micro-flow data signal and to transmit a data signal.

14. The linecard of claim 10, wherein the ingress micro-flow manager includes a micro-flow recognizer adapted to receive the data signal and to search the flow block table for the flow block corresponding to the data signal.

15. The linecard of claim 14, wherein the ingress micro-flow manager further includes a micro-flow classifier adapted to respond to the identification by the micro-flow recognizer of a flow block corresponding to the data signal by retrieving state information from the identified flow block and constructing a micro-flow data signal based upon the retrieved state information and to respond to the failure to identify the flow block corresponding to the data signal by retrieving information from the data signal, creating within said flow block table a new flow block including state information corresponding to the retrieved information from the data signal and constructing a micro-flow data signal with said state information.

16. The linecard of claim 10, wherein the flow block table is a hash table.

17. The linecard of claim 10 wherein the flow block table is a content addressable memory.

18. The linecard of claim 10 wherein the state information includes quality of service information.

19. The linecard of claim 10 wherein the state information includes routing information.

20. The linecard of claim 10 wherein the ingress micro-flow manager further includes a scheduler adapted to schedule the transmission of the micro-flow data signal.

21. The linecard of claim 10 wherein the memory includes a layers table including state information corresponding to layer information, wherein said layer information corresponds to information retrieved from the data signal.

22. The linecard of claim 10 wherein the memory includes a policy table including state information corresponding to a policy designation, wherein said policy designation corresponds to information retrieved from the data signal.

23. The linecard of claim 10, wherein the memory includes a forwarding table including a destination address, wherein said destination address corresponds to information retrieved from the data signal.

24. The linecard of claim 23 further comprising a routing table including a route path corresponding to the destination address.

25. The linecard of claim 10 wherein the memory includes a storage block table adapted to store the data signal.

26. The linecard of claim 13 wherein the egress micro-flow manager includes a micro-flow recognizer adapted to receive the micro-flow data signal and to search the flow block table for the flow block corresponding to the micro-flow data signal.

27. The linecard of claim 13 wherein the egress micro-flow manager includes a scheduler adapted to schedule the transmission of the data signal.

29. The linecard of claim 28 wherein the flow block table is a hash table.

30. The linecard of claim 28 wherein the flow block table is a content addressable memory.

31. The linecard of claim 28 wherein the state information includes quality of service information.

32. The linecard of claim 28 wherein the state information includes routing information.

33. The linecard of claim 28 further comprising:

a micro-flow classifier, coupled to the micro-flow recognizer, adapted to respond to the identification by the micro-flow recognizer of a flow block corresponding to the data signal by retrieving state information from the flow block and constructing a micro-flow data signal based upon the state information and to respond to the failure to identify a flow block corresponding to the data signal by retrieving information from the data signal, creating a new flow block including state information based upon the retrieved information from the data signal and constructing a micro-flow data signal based upon the state information.

34. The linecard of claim 33 further comprising a scheduler, coupled to the micro-flow classifier, adapted to schedule the transmission of the micro-flow data signal.

35. The linecard of claim 33 further comprising a layers table, coupled to the micro-flow classifier, including state information corresponding to layer information, wherein said layer information corresponds to information from the data signal.

36. The linecard of claim 33 further comprising a policy table, coupled to the micro-flow classifier, including state information corresponding to a policy designation, wherein said policy designation corresponds to information from the data signal.

37. The linecard of claim 28, wherein the data signal is a data packet signal.

38. The linecard of claim 28, wherein the data signal is a asynchronous transfer mode cell signal.

39. The linecard of claim 28, wherein the data signal is a frame relay signal.

40. The linecard of claim 33 further comprising a forwarding table, coupled to the micro-flow classifier, including a primary destination address, wherein said primary destination address corresponds to information from the data signal.

41. The linecard of claim 40, wherein said forwarding table includes a secondary destination address, wherein said secondary linecard destination address corresponds to information from the data signal.

42. The linecard of claim 40 further comprising a routing table, coupled to the micro-flow classifier, including a primary route through a fabric switch core to the primary destination address.

43. The linecard of claim 41 further comprising a routing table, coupled to the micro-flow classifier, including a secondary route through a fabric switch core to the secondary destination address.

44. The linecard of claim 28 further comprising a storage block table, coupled to the micro-flow recognizer, adapted to store the data signal.

45. The linecard of claim 28 further comprising a network trunk line interface, coupled to the micro-flow recognizer, adapted to receive a data signal and to transmit a reformatted data signal.

46. The linecard of claim 28 wherein said network trunk line interface deencapsulates the data signal and transmits the deencapsulated data signal to the micro-flow recognizer.

48. The switch of claim 47 further comprising an egress linecard, coupled to the switch core, adapted to receive the micro-flow data signal from the switch core and adapted to transmit a data signal.

50. The linecard of claim 49 wherein said retrieved information includes layer information.

51. The linecard of claim 49 wherein said retrieved information includes a quality of service descriptor.

52. The linecard of claim 49 further comprising a scheduler, coupled to the micro-flow classifier, adapted to schedule the transmission of a micro-flow data signal corresponding to the new flow block.

28. A micro-flow linecard comprising:

a flow block table including a plurality of flow blocks, wherein each of said flow blocks includes state information; and

a micro-flow recognizer adapted to receive a data signal and to search the flow block table for one of the plurality of flow blocks corresponding to information retrieved from the data signal.

47. A micro-flow switch comprising:

a switch core adapted to route a micro-flow data signal; and

an ingress linecard, coupled to the switch core, adapted to receive a data signal and to transmit the micro-flow data signal to the switch core.

49. A micro-flow linecard comprising:

a flow block table including a plurality of flow blocks, wherein each of said flow blocks includes state information; and

a micro-flow classifier, coupled to the micro-flow recognizer, adapted to retrieve information from a data signal and to associate a flow block with the retrieved information.

53. A micro-flow network comprising:

a first micro-flow switch, adapted to receive a first data signal and to transmit a micro-flow data signal; and

a second micro-flow switch, coupled to the first micro-flow switch, adapted to receive the micro-flow data signal and to transmit a second data signal.

54. The micro-flow network of claim 53 wherein the first data signal is a micro-flow data signal.

55. The micro-flow network of claim 53 wherein the second data signal is a micro-flow data signal.

57. A flow block of claim 56, wherein said transmission rate value is a guaranteed rate value.

58. A flow block of claim 56, wherein said transmission rate value is an available rate value.

59. A flow block of claim 56 further comprising a packet discard time limit value.

60. A flow block of claim 56 further comprising a micro-flow timeout period value.

56. A flow block comprising:

a transmission rate value;

and a delay variation value.

61. A micro-flow data packet including:

a label field; and

a quality of service field.

62. The micro-flow data packet of claim 61, wherein the quality of service field includes:

a transmission rate value;

and a delay variation value.

63. The micro-flow data packet of claim 62, wherein the transmission rate value is a guaranteed rate value.

64. The micro-flow data packet of claim 62, wherein the transmission rate value is an available rate value.

65. A method for generating a flow block corresponding to a data signal, the method comprising the steps of:

retrieving information from the data signal;

determining state information corresponding to the retrieved information; and

associating the state information with the data signal.

66. The method of claim 65, wherein the retrieved information is layer information.

67. The method of claim 66, wherein determining state information corresponding to the layer information includes the step of determining the protocol type of the layer information.

68. The method of claim 66 wherein determining state information corresponding to the layer information includes the step of determining the port type of the layer information.

69. The method of claim 66, wherein determining state information corresponding to the layer information includes the step of determining the real-time transport protocol type of the layer information.

70. The method of claim 65, wherein the retrieved information is policy information.

71. The method of claim 70, wherein the policy information includes service level agreement information.

72. The method of claim 70, wherein the policy information includes virtual private network information.

73. The method of claim 65, wherein the retrieved information is a quality of service field including a quality of service descriptor.

74. The method of claim 65 further comprising the steps of:

determining a path across a switch core fabric based upon the retrieved information; and

storing the path information within the flow block associated with the data signal.

75. The method of claim 65 further comprising the step of determining the path across a switch core fabric based upon the state information.

76. The method of claim 65 comprising the additional step of storing the state information within a flow block table.

77. A method for routing a micro-flow comprising the steps of:

receiving a data signal; and

associating the data signal with a flow block.

78. The method of claim 77 further comprising the step of constructing a micro-flow data signal corresponding to the data signal based upon the flow block.

79. The method of claim 77 further comprising the step of transmitting a micro-flow data signal corresponding to the data signal.

80. The method of claim 78 wherein the step of associating the data signal with the flow block includes the step of assigning a label to the micro-flow data signal, wherein said label corresponds to the flow block.

81. The method of claim 78 wherein the step of associating the data signal with the flow block includes the step of inserting a quality of service field in the micro-flow data signal.

82. The method of claim 81 wherein the step of inserting the quality of service field includes the step of inserting state information from the flow block into the quality of service field.

83. The method of claim 82 wherein the quality of service field includes a transmission rate value.

84. The method of claim 83 wherein the quality of service field includes a delay variation value.

85. The method of claim 79 wherein the transmission of the micro-flow data packet is scheduled based upon state information retrieved from the flow block.

86. The method of claim 77 further comprising the step of responding to the data signal exceeding the transmission rate value of the flow block by discarding the data signal.

87. A method for routing a micro-flow comprising the steps of:

receiving a plurality of data signals;

associating a flow block to the plurality of data signals;

transmitting a plurality of micro-flow data signals, wherein the plurality of micro-flow data signals includes a label field corresponding to the flow block and wherein the first micro-flow data signal of the plurality of micro-flow data signals also includes a quality of service field including state information from the flow block.

88. The method of claim 87 further comprising the step of scheduling the transmission of the plurality of micro-flow data signals to ensure compliance with the state information from the flow block.

89. The method of claim 88 wherein the state information includes a transmission rate constraint.

90. The method of claim 88 wherein the state information includes a delay variation constraint.

91. The method of claim 87 wherein the step of associating the flow block with the plurality of data signals includes the additional steps of:

retrieving information from a first data signal of the plurality of data signals;

determining state information corresponding to retrieved information from the first data signal;

storing the state information in the flow block; and

associating the state information within the flow block with each data signal of the plurality of data signals.

92. A method for routing a plurality of micro-flows comprising the steps of:

receiving a first micro-flow data signal and a second micro-flow data signal at a first switch;

transmitting a micro-flow data signal corresponding to a first micro-flow of the plurality of micro-flows to a second switch; and

transmitting a micro-flow data signal corresponding to a second micro-flow of the plurality of micro-flows to a third switch.

93. The method of claim 92 comprising the additional step of scheduling the transmission of the micro-flow signal corresponding to the first micro-flow and the micro-flow signal corresponding to the second micro-flow to ensure compliance with the state information associated with the first micro-flow and the second micro-flow.