Methods and apparatus for routing packets using policy and network efficiency information

• US 6,775,280 B1
• Filed: 04/29/1999
• Issued: 08/10/2004
• Est. Priority Date: 04/29/1999
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Ma, Qingming, Waclawsky, John G.
• Primary Examiner(s): Pham, Chi
• Assistant Examiner(s): Ferris, Derrick W
• Application Number:
  US09/302,311
• Time in Patent Office: 1,930 Days
• Field of Search: 370/229, 370/230, 370/232, 370/234, 370/237, 370/238, 370/238.1, 370/352, 370/353, 370/354, 370/355, 370/356, 370/357, 370/389, 370/400, 370/409, 370/464, 370/469, 370/471, 370/902, 370/905, 370/392, 709/236, 709/240
• US Class Current: 370/392
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/20 Hop count for routing purposes, e.g. TTL
• 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/11 Identifying congestion
• CPC Class Codes: H04L 47/122 by diverting traffic away from congested entities
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering
• 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]

Abstract

A technique routes packets in a data communications device having multiple output ports. The technique involves obtaining, from a network, data having an associated quality of service (QoS). The technique additionally involves choosing one of the multiple output ports of the data communications device based on the associated QoS of the data, a pre-established policy, and network efficiency information for the multiple output ports. The technique further involves transmitting the data to the network through the chosen one of the multiple output ports.

Claims

1. In a data communications device having multiple output ports, a method to support routing of data in a connectionless network system, the method comprising the steps of:

obtaining as the data, data packets from a network, each data packet having an associated quality of service;

classifying the data packets obtained from the network;

for each classified data packet, choosing one of the multiple output ports of the data communications device based on the associated quality of service of that classified data packet, a pre-established policy, and network traffic congestion information associated with network traffic through the multiple output ports; and

transmitting each of the data packets to the network through a corresponding chosen one of the multiple output ports along a compliant network path, at least one of the data packets passing through the data communications device in a manner that circumvents a routing circuit configured to operate based on (i) a forwarding information base for forwarding best effort packets and (ii) a forwarding table for forwarding packets of a pre-established packet stream.

2. The method of claim 1 wherein the network traffic congestion information includes network load information describing network load environments at the multiple output ports, and wherein the step of choosing includes the steps of:

selecting, from a set of available network paths extending from the data communications device, a set of policy compliant network paths based on the associated quality of service of the data and the pre-established policy; and

identifying one of the set of policy compliant network paths based on the associated quality of service of the data and the network load information, the chosen one of the multiple output ports being an output port through which the identified one of the set of policy compliant network paths passes.

3. The method of claim 2 wherein the data is obtained within a packet having a designated destination, and wherein each policy compliant network path extends from the data communications device to the designated destination.

4. The method of claim 2 wherein the data is obtained within a packet, and wherein each policy compliant network path is capable of carrying the packet in accordance with the associated quality of service.

5. The method of claim 1 wherein the data is obtained within a packet having a quality of service field, and wherein the step of choosing includes the step of:

scanning the quality of service field of the packet to determine the associated quality of service of the data.

6. The method of claim 1 wherein the step of choosing includes the step of:

choosing one of the multiple output ports of the data communications device based on network topology information including adjacent hop data and propagation delay data.

7. The method of claim 1, further comprising the step of:

receiving the pre-established policy from another data communications device in the network prior to the step of choosing.

8. The method of claim 1 wherein the network traffic congestion information includes network load information describing network load environments at the multiple output ports.

9. The method of claim 1, wherein the data is obtained within a packet, and wherein the method further comprises the step of:

obtaining another packet that is associated with a best effort quality of service, and transmitting the other packet through a predetermined one of the multiple output ports without regard for the pre-established policy and the network traffic congestion information.

10. The method of claim 1, wherein the data is obtained within a packet, and wherein the method further comprises the step of:

obtaining another packet that belongs to a pre-established packet stream, and transmitting the other packet through a predetermined one of the multiple output ports without regard for the pre-established policy and the network traffic congestion information.

11. The method of claim 1 wherein the step of choosing one of the multiple output ports of the data communications device includes the steps of:

selecting, from a set of paths extending from the output ports of the data communications device, a set of compliant paths from the set of paths, wherein each compliant path within the set of compliant paths carries data in accordance with the associated quality of service of the obtained data; and

identifying one of the compliant paths from the set of compliant paths on which to forward the data packets based on the network traffic congestion information.

12. The method of claim 11 wherein the network traffic congestion information includes a respective network load value for each output port of the data communications device.

13. A method as in claim 1, wherein the step of obtaining the data packets includes obtaining data packets at an intermediate node of the network.

14. A method as in claim 13, wherein the step of obtaining the data packets at an intermediate node includes obtaining data packets that are transmitted from a source node to a destination node of the network.

15. The method of claim 1 wherein the step of classifying includes the step of classifying a first data packet and a second data packet, and wherein the step of choosing includes the steps of:

after the step of classifying, identifying one of the multiple output ports through which to send the first data packet; and

after the step of classifying, identifying one of the multiple output ports through which to send the second data packet regardless of whether the first and second data packets belong to a same connection session.

16. The method of claim 15 wherein the first data packet and the second data packet belong to the same connection session;

wherein the step of identifying one of the multiple output ports through which to send the first data packet includes the step of;

picking a first output port through which to send the first data packet; and

wherein the step of identifying one of the multiple output ports through which to send the second data packet includes the step of;

picking a second output port through which to send the second data packet, the second output port being different than the first output port even though the first and second data packets belong to the same connection session.

17. A data communications device supporting routing of data in a connectionless network system, the data communications device comprising:

an input port that obtains the data as data packets from a network, each data packet having an associated quality of service;

multiple output ports; and

a control circuit, coupled to the input port and the multiple output ports, that for each data packet, (i) chooses one of the multiple output ports based on the associated quality of service of the data, a pre-established policy, and network traffic congestion information associated with network traffic through the multiple output ports, and (ii) transmits each data packet to the network through a corresponding chosen one of the multiple output ports, the control circuit supporting transmission of at least one of the data packets to the connectionless network system through a corresponding chosen one of the multiple output ports, the at least one of the data packets passing through the data communications device in a manner that circumvents a routing circuit configured to operate based on (i) a forwarding information base for forwarding best effort packets and (ii) a forwarding table for forwarding packets of a pre-established packet stream.

18. The data communications device of claim 17 wherein the network traffic condition information includes network load information describing network load environments at the multiple output ports, and wherein the control circuit includes:

a policy stage that selects, from a set of available network paths extending from the data communications device, a set of policy compliant network paths based on the associated quality of service of the data and the pre-established policy; and

an efficiency stage, coupled to the policy stage, that identifies one of the set of policy compliant network paths based on the associated quality of service of the data and the network load information, the chosen one of the multiple output ports being an output port through which the identified one of the set of compliant network paths passes.

19. The data communications device of claim 18 wherein the data is obtained within a packet having a designated destination, and wherein each policy compliant network path extends from the data communications device to the designated destination.

20. The data communications device of claim 18 wherein the data is obtained within a packet, and wherein each policy compliant network path is capable of carrying the packet in accordance with the associated quality of service.

21. The data communications device of claim 17 wherein the data is obtained within a packet having a quality of service field, and wherein the control circuit includes:

classifying circuitry that scans the quality of service field of the packet to determine the associated quality of service of the data.

22. The data communications device of claim 17 wherein the control circuit includes:

circuitry that chooses one of the multiple output ports of the data communications device based on network topology information including adjacent hop data and propagation delay data.

23. The data communications device of claim 17, further comprising:

memory that receives the pre-established policy from another data communications device in the network, and stores the pre-established policy within a policy table.

24. The data communications device of claim 17 wherein the network traffic congestion information includes network load information describing network load environments at the multiple output ports.

25. The data communications device of claim 17, wherein the data is obtained within a packet, and wherein the data communications device further comprises:

a routing circuit that obtains another packet that is associated with a best effort quality of service, and queues the other packet for transmission through a predetermined one of the multiple output ports without regard for the pre-established policy and the network traffic congestion information.

26. The data communications device of claim 17, wherein the data is obtained within a packet, and wherein the data communications device further comprises:

a routing circuit that obtains another packet that belongs to a pre-established packet stream, and queues the other packet for transmission through a predetermined one of the multiple output ports without regard for the pre-established policy and the network traffic congestion information.

27. The data communications device of claim 17 wherein control circuit is configured to:

select, from a set of paths extending from the output ports of the data communications device, a set of compliant paths from the set of paths, wherein each compliant path within the set of compliant paths carries data in accordance with the associated quality of service of the obtained data; and

identify one of the compliant paths from the set of compliant paths on which to forward the data packets based on the network traffic congestion information.

28. The data communication device of claim 27 wherein the network traffic congestion information includes a respective network load value for each output port of the data communications device.

29. A data communications device as in claim 17, wherein the data communications device obtains the data packets at an intermediate node of the network.

30. A data communications device as in claim 29, wherein the obtained data packets are transmitted from a source node to a destination node of the network.

31. The data communications device of claim 17 wherein the control circuit, when choosing output ports and transmitting data packets, is configured to:

after classifying a first data packet, identifying one of the multiple output ports through which to send the first data packet; and

after classifying a second data packet, identifying one of the multiple output ports through which to send the second data packet regardless of whether the first and second data packets belong to a same connection session.

32. The data communications device of claim 31 wherein the first data packet and the second data packet belong to the same connection session;

wherein the control circuit is configured to identify a first output port through which to send the first data packet, and identify a second output port through which to send the second data packet, the second output port being different than the first output port even though the first and second data packets belong to the same connection session.

33. A data communications device for routing data in a connectionless network system, comprising:

an input port configured to couple to a data packet source, each data packet from the data packet source having an associated quality of service;

multiple output ports configured to couple to potential data packet targets;

means for classifying each data packet from the data packet source;

means for choosing, for each data packet from the data packet source, one of the multiple output ports based on the associated quality of service of the data, a pre-established policy, and network traffic congestion information associated with network traffic through the multiple output ports, after that data packet has been classified; and

means for transmitting each data packet to the network through a corresponding chosen one of the multiple output ports along a compliant path, at least one data packet passing through the data communications device in a manner that circumvents a routing circuit configured to operate based on (i) a forwarding information base for forwarding best effort packets and (ii) a forwarding table for forwarding packets of a Pre-established packet stream.

34. The data communications device of claim 33 wherein the means for choosing includes:

means identifying an output port for each classified packet regardless of whether the classified packets belong to a same connection session.

35. In a data communications device supporting packet-switched routing of data packets based on a multi-stage routing decision, a method for routing data comprising:

receiving a particular data packet having an associated quality of service, the particular data packet including destination information identifying a destination network node to which the particular data packet is destined;

at a first stage in the multi-stage routing decision;

classifying the particular data packet based on a quality of service and destination information associated with the particular data packet; and

identifying a compliant set of available paths able to carry the particular data packet to the destination network node associated with the particular data packet in accordance with the associated quality of service;

at a second stage following the first stage of the multi-stage routing decision;

selecting a particular path from the compliant set of available paths on which to forward the particular data packet based on network traffic congestion information associated with the compliant set of available paths; and

transmitting the particular data packet to the network node through a corresponding chosen one of the multiple output ports on the particular path, the particular data packet passing through the data communications device in a manner that circumvents a routing circuit configured to operate based on (i) a forwarding information base for forwarding best effort packets and (ii) a forwarding table for forwarding packets of a pre-established packet stream.

36. A method as in claim 35 further comprising:

monitoring traffic associated with the multiple output ports to generate the network traffic congestion information utilized in the second stage to select the particular path on which to forward the particular data packet.

37. A method as in claim 36, wherein selecting a particular path in the second stage further involves:

queuing the particular data packet in one of lesser used output queues, at least two of the multiple output queues having different associated delays for transmission of data packets over corresponding networks to a destination node.

38. A method as in claim 37, wherein monitoring traffic associated with the multiple output ports includes measuring fullness of corresponding multiple output queues associated with the multiple output ports.

39. A method as in claim 38, wherein selecting a particular path from the compliant set of available paths in the second stage includes:

selecting a least used path from the compliant set of paths on which to transmit the particular data packet to the destination network node.

40. A method as in claim 39 further comprising:

in addition to the particular data packet, obtaining a data packet associated with a best effort quality of service; and

transmitting the data packet associated with a best effort quality of service through a predetermined one of the multiple output ports regardless of the network traffic condition information.

41. In a data communications device having multiple output ports, a method for routing data through the data communications device, the method comprising:

in a classification module of the data communications device, extracting source and destination information and a quality of service delay from a connectionless packet;

in a policy stage of the data communications device and based on the extracted source and destination information and the quality of service delay, generating a list of compliant paths from multiple paths which are capable of carrying the connectionless packet to a targeted destination, the list of compliant paths being generated by concurrently applying a policy from a policy table and network topology information from a network topology table, the network topology table providing hop data and propagation delay data to eliminate paths which are unable to carry the connectionless packet to the targeted destination within a quality of service policy constraint specified by the policy;

in an efficiency stage of the data communications device, selecting one of the compliant paths from the list of compliant paths based on network load information obtained from external traffic monitors disposed at the output ports to measure network load congestion at the output ports; and

transmitting the connectionless packet out an output port associated with the selected one of the compliant paths, the connectionless packet passing through the data communications device in a manner that circumvents a routing circuit configured to operate based on (i) a forwarding information base for forwarding best effort packets and (ii) a forwarding table for forwarding packets of a pre-established packet stream.