System and method for network tunneling utilizing micro-flow state information

• US 6,977,932 B1
• Filed: 01/16/2002
• Issued: 12/20/2005
• Est. Priority Date: 01/16/2002
• Status: Expired due to Term

• Current Assignee: Sable Networks, Inc.
• Original Assignee: Caspian Networks, Inc.
• Inventors: Hauck, Scott
• Primary Examiner(s): HO, DUC CHI
• Application Number:
  US10/051,864
• Time in Patent Office: 1,434 Days
• Field of Search: 370/401, 370/469, 370/235, 370/229, 370/230, 370/386, 370/389, 370/391, 370/392, 370/400
• US Class Current: 370/392
• CPC Class Codes: H04L 12/4633 Interconnection of networks using encapsulation techniques, e.g. tunneling
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/38 Flow based routing
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]
• CPC Class Codes: H04L 47/12 Avoiding congestion; Recovering from congestion
• CPC Class Codes: H04L 69/14 Multichannel or multilink protocols
• CPC Class Codes: Y02D 30/50 in wire-line communication networks, e.g. low power modes or reduced link rate

Abstract

Network tunneling methods and apparatus utilizing flow state information are provided. A router includes an ingress linecard having logic that selects a particular network tunnel for a received micro-flow. The ingress linecard further includes logic that selects a particular egress linecard and a particular port to utilize for transmitting the micro-flow. The router also includes an aggregate flow block that includes tunnel specific information for the selected network tunnel. The tunnel specific information includes but is not limited to label action and outgoing label(s), Layer 2 tunneling action or Layer 3 actions. The aggregate flow block further includes statistics for the selected network tunnel. In addition, the router includes a flow block having flow state information for the micro-flow. The flow block also includes an identifier that associates the flow block with the aggregate flow block.

Claims

1. A method for network tunneling utilizing flow state information, comprising the operations of:

creating a flow block having flow state information for a received first data packet of a micro-flow;

storing a tunnel identifier for the micro-flow in the flow block, the tunnel identifier identifying a selected network tunnel to be used to transmit the data packet;

indexing an aggregate flow block using the tunnel identifier, the aggregate flow block having tunnel specific information for the selected network tunnel; and

transmitting the data packet using the selected network tunnel based on the tunnel specific information;

wherein statistics for the selected network tunnel are stored using the aggregate flow block.

2. A method as recited in claim 1, wherein the statistics include utilization statistics for the selected network tunnel.

3. A method as recited in claim 1, wherein the first data packet is received at a particular ingress linecard.

4. A method as recited in claim 3, wherein the ingress linecard sends the first data packet to a particular output port of a network tunnel multi-link interface based on utilization of the output port.

5. A method as recited in claim 4, wherein the ingress linecard sends the first data packet to the output port having the least utilization.

6. A method as recited in claim 1, further comprising the operation of storing the tunnel specific information obtained from the aggregate flow block in the created flow block.

7. A method as recited in claim 6, wherein the tunnel specific information includes at least one of an outgoing label, and an outgoing layer 2 type for an egress router.

8. A method as recited in claim 7, further including the operation of transmitting a subsequent data packet based on the tunnel specific information stored in the flow block.

9. A router capable of network tunneling utilizing flow state information, comprising:

an aggregate flow block having tunnel specific information for a particular network tunnel; and

a flow block having flow state information for a micro-flow, the flow block further including an identifier that associates the flow block with the aggregate flow block;

wherein the aggregate flow block stores statistics for the particular network tunnel.

10. A router as recited in claim 9, wherein the aggregate flow block includes an outgoing label associated with the particular network tunnel.

11. A router as recited in claim 10, wherein the aggregate flow block includes a label action associated with the particular network tunnel.

12. A router as recited in claim 11, wherein the outgoing label and the label action are copied from the aggregate flow block to the flow block upon creation of the flow block.

13. A router as recited in claim 11, further comprising a plurality of aggregate flow blocks, each aggregate flow block being associated with a separate network tunnel.

14. A router as recited in claim 13, further comprising a plurality of flow blocks, each flow block associated with a separate micro-flow.

15. A router as recited in claim 14, wherein the plurality of flow blocks includes flow state information for a particular micro-flow.

16. A router as recited in claim 9, wherein the statistics include utilization statistics for the particular network tunnel.

17. A method for network tunneling utilizing flow state information, comprising the operations of:

receiving a first data packet of a micro-flow at an ingress linecard of a router;

creating a flow block having flow state information for a received first data packet of a micro-flow;

storing a tunnel identifier for the micro-flow in the flow block, the tunnel identifier identifying a selected network tunnel to be used to transit the data packet;

determining a particular output port on a specific egress linecard for transmitting the micro-flow;

transmitting the first data packet to the specific egress linecard;

indexing an aggregate flow block using the tunnel identifier, the aggregate flow block having tunnel specific information for the selected network tunnel; and

transmitting the data packet along the selected network tunnel using the particular output port based on the tunnel specific information;

wherein statistics for the selected network tunnel are stored using the aggregate flow block.

18. A method as recited in claim 17, wherein the particular output port is a least utilized output port associated with the selected network tunnel.

19. A method as recited in claim 17, wherein the particular output port is determined based on time.

20. A method as recited in claim 17, wherein the statistics include utilization statistics for the selected network tunnel.

21. A method as recited in claim 17, further comprising the operation of storing the tunnel specific information obtained from the aggregate flow block in the created flow block.

22. A method as recited in claim 21, wherein the tunnel specific information includes an outgoing label.

23. A method as recited in claim 22, further including the operation of transmitting a subsequent data packet based on the tunnel specific information stored in the flow block.

24. A router capable of network tunneling utilizing flow state information, comprising:

an ingress linecard having logic that selects a particular network tunnel for a received micro-flow, the ingress linecard further including logic that selects a particular egress linecard and a particular port to utilize for transmission of the micro-flow;

an aggregate flow block having tunnel specific information for the selected network tunnel, the aggregate flow block further including statistics for the selected network tunnel; and

a flow block having flow state information for the micro-flow, the flow block further including an identifier that associates the flow block with the aggregate flow block.

25. A router as recited in claim 24, wherein the aggregate flow block includes an outgoing label associated with the particular network tunnel.

26. A router as recited in claim 25, wherein the aggregate flow block includes a label action associated with the particular network tunnel.

27. A router as recited in claim 26, wherein the outgoing label and the label action are copied from the aggregate flow block to the flow block upon creation of the flow block.

28. A router as recited in claim 24, wherein the statistics include utilization statistics for the selected network tunnel.

29. A router as recited in claim 24, further comprising a plurality of aggregate flow blocks, each aggregate flow block being associated with a separate network tunnel.

30. A router as recited in claim 29, further comprising a plurality of flow blocks, each flow block associated with a separate micro-flow.

31. A router as recited in claim 30, wherein the plurality of flow blocks includes flow state information for a particular micro-flow.

32. A method for network tunneling utilizing flow state information, comprising the operations of:

receiving a first data packet of a micro-flow at an ingress linecard of a router;

creating a flow block having flow state information for a received first data packet of a micro-flow;

storing an aggregate flow block tunnel identifier for the micro-flow in the flow block, the aggregate flow block tunnel identifier identifying a selected network tunnel to be used to transmit the data packet;

determining a particular output port on a specific egress linecard for transmitting the micro-flow, the particular output port is determined from the aggregate flow block tunnel identifier; and

transmitting the first data packet and all subsequent data packets to the specific egress linecard using the aggregate flow block tunnel identifier;

wherein statistics for the selected network tunnel are stored using the aggregate flow block tunnel identifier.