Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1999-04-29
2004-08-10
Pham, Chi (Department: 2663)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S230000
Reexamination Certificate
active
06775280
ABSTRACT:
BACKGROUND OF THE INVENTION
A typical data communications network includes multiple host computers that are linked together by a combination of data communications devices and transmission media. In general, the host computers communicate by (i) packaging data using a standardized protocol or format such as a network packet or cell (hereinafter generally referred to as a packet), and (ii) exchanging the packaged data through the data communications devices and transmission media.
In some networks, the packaged data is classified into different Quality of Service (QoS) classes that dictate how competing traffic flows are provided resources. Such resource allocation affects how quickly the packaged data travels from a source to a destination. For example, a distinction may be drawn between packets carrying video data (i.e., video packets belonging to a video QoS class) and packets carrying general data (i.e., general data packets belonging to a general data QoS class such as Best Effort Service). In this arrangement, a data communications device routes video packets through a network differently than general data packets due to different link resource availability and resources being allocated differently based on the QoS class of the packets.
There are different types of QoS routing techniques. In one QoS routing technique (hereinafter called QoS class-prioritized routing), a data communications device internally prioritizes the processing of different QoS class packets in accordance with a pre-established QoS policy. For example, in accordance with one such QoS policy, a data communications device gives higher priority to video packets relative to general data packets. Accordingly, if the data communications device simultaneously receives a video packet and a general data packet (e.g., through multiple input ports), the QoS policy directs the device to process the video packet before the general data packet. As a result, in QoS class-prioritized routing, packet destinations (i.e., receiving host computers) generally perceive different responses, or Qualities of Service, for different QoS classes (e.g., faster video transmissions than general data transmissions).
In another QoS routing technique (hereinafter called load-directed routing), the data communications device generally directs packets through the network based on network load conditions. For example, suppose that the data communications device has multiple output ports to data paths that eventually lead to the same remote destination (i.e., the same receiving host computer). When the data communications device receives a video packet destined for that remote destination, the device transmits the video packet out the output port expected to lead to a low traffic area of the network. On the other hand, when the device receives a general data packet destined for the same remote destination, the device transmits the general data packet out a different output port expected to lead to a high traffic area of the network. With this arrangement, the video packet should travel through the network faster than the general data packet. Accordingly, the load-directed routing technique generally provides the same result as the QoS class-prioritized routing technique. That is, packet destinations (i.e., receiving host computers) generally perceive different Quality of Service or responses for different QoS classes (e.g., quicker video transmissions than general data transmissions).
SUMMARY OF THE INVENTION
In contrast to conventional quality of service (QoS) routing techniques that route data exclusively based on a QoS policy, or that route data exclusively based on load-balancing criteria, the invention is directed to techniques for routing data in a manner that simultaneously satisfies a QoS policy constraint, and a network efficiency constraint (e.g., load balancing). That is, embodiments of the invention provide load-balancing while, at the same time, satisfying QoS requirements.
One technique involves obtaining data from a network using a data communications device having multiple output ports. This technique further involves choosing one of the output ports based on an associated quality of service of the data, a pre-established QoS policy, and network efficiency information. The technique then involves transmitting the data to the network through the chosen output port. Accordingly, the technique satisfies both a QoS policy constraint as well as a network efficiency constraint.
Preferably, the data resides in a packet having a source field, a destination field and a QoS field. In this situation, the device scans the source and destination fields to determine the source and intended destination (e.g., host computers) of the packet. Alternatively, only the destination and QoS fields are used. Similarly, the device scans the QoS field of the packet to determine the associated QoS of the data. The associated QoS may be in the form of a number identifying a particular QoS class, a delay bound indicating a limit on the amount of time permitted for the data to travel from its source to its destination, a bandwidth requirement, a combination of such criteria or other criteria.
In one particular technique, the network efficiency information includes network load information describing network load conditions at the output ports of the data communications device. In one embodiment, the network load information is gathered and distributed among data communication devices within the network. That is, the data communications device that operates in accordance with the invention receives the network load information from neighboring devices that observe the local network environment. Alternatively, the network load information is acquired from traffic monitors that observe network traffic at the output ports.
With the network load information, the data communications device chooses one of the multiple output ports of the data communications device for data transmission. First, a policy stage of the data communications device selects, from a set of available network paths extending from the device, a set of QoS policy compliant network paths based on the associated QoS class of the data and the pre-established QoS policy. Next, using the network load information as a load distribution constraint, an efficiency stage of the device identifies one of the policy compliant network paths based on the associated QoS of the data and the network load information. The chosen output port is an output port through which the identified one of the set of policy compliant network paths passes.
It should be understood that each of the policy compliant network paths preferably extends from the data communications device to a designated destination identified by the destination field of the packet. Furthermore, each policy compliant network path preferably is capable of carrying the data (e.g., formatted as a packet) in accordance with the associated QoS of the packet.
Furthermore, for the above-described particular technique, it should be understood that the modularization of the data communications device's operation into a policy stage and an efficiency stage adds flexibility to the device. For example, one pre-established policy can be substituted with another in the policy stage without interfering with the operation of the efficiency stage. Similarly, different load balancing rules can be imposed in the efficiency stage without interfering with the operation of the policy stage. Accordingly, various policy and load balancing algorithms can be incorporated in the data communications device in order to optimize and customize its operation.
A thorough explanation of particular QoS policies and routing algorithms that are suitable for use by the invention are described in a thesis entitled, “Quality-of-Service Routing in Integrated Services Networks,” by Qingming Ma, published May, 1999 (although dated January, 1998), Carnegie Mellon University, Pittsburgh, Pa., CMU-CS-98-138, the teachings of which are hereby incorporated by reference in their entire
Ma Qingming
Waclawsky John G.
Chapin & Huang , L.L.C.
Cisco Technology Inc.
Ferris Derrick W
Huang, Esq. David E.
Pham Chi
LandOfFree
Methods and apparatus for routing packets using policy and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatus for routing packets using policy and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for routing packets using policy and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3307239