Multiplex communications – Data flow congestion prevention or control – Flow control of data transmission through a network
Reexamination Certificate
1998-12-18
2002-12-10
Nguyen, Steven (Department: 2665)
Multiplex communications
Data flow congestion prevention or control
Flow control of data transmission through a network
C370S395520
Reexamination Certificate
active
06493317
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to computer networking technology, and in particular to traffic engineering techniques in a multi-service class routing network.
Future Internet will support multiple classes of service in addition to best-effort service. A variety of service models have been proposed to deliver different levels of end-to-end Quality-of-Service (QoS) to applications. These services require network support of packet scheduling, signaling protocols (e.g., RSVP) and admissions policies. As diverse as these models are, there is a common theme: the network gives preferential treatment to flows in one class over flows in other classes, and bandwidth is the key QoS parameter.
A representative prototypical example of an integrated services network supports at least two different traffic classes: bandwidth-guaranteed and best-effort traffic. Bandwidth-guaranteed traffic may include both guaranteed service traffic and differentiated service traffic (differentiated service traffic may include assured forwarding and/or expedited forwarding). The network resources are shared by these two service classes. As a result of the different resource sharing models (allocation/reservation for guaranteed sessions and fair sharing for best-effort sessions), guaranteed sessions have priority over best-effort sessions. Once resources are allocated for guaranteed sessions, they are no longer available for best-effort sessions, unless the allocated resources are unused by guaranteed sessions. The packet scheduler in a router or switch ensures that the guaranteed traffic will receive, at a minimum, its allocated share of bandwidth. The portion of the link capacity available to best-effort traffic is typically allocated according to max-min fair sharing policy. Given a fixed traffic load of guaranteed sessions, the resources available to best effort traffic will be influenced by the routing for guaranteed sessions. In such a prototypical multi-class network, if the routing algorithm for guaranteed sessions ignores the load of, or even the presence of, lower priority traffic, as is commonly done, the result is that the throughput of guaranteed traffic is optimized while the performance of best-effort sessions is ignored.
With the integration of voice, video, and data traffic, the aggregate bandwidth requirement of applications is getting higher. More network infrastructures are being built with high-end routers/switches having a large number of interfaces. As a result, the network connectivity is dramatically increasing. Although ISPs do their best to configure their network topologies to match expected traffic load, the traffic load changes dynamically and the routers/switches can go down from time to time. Therefore, the network traffic load often mismatches the underlying network topology, resulting in some links being very congested while other links sit idle. Traffic engineering is an important network service that enables ISPs to balance the traffic load and improve the overall bandwidth efficiency. The importance of traffic engineering has long been recognized in the telecommunication industry and is receiving increased attention in the data networking industry, largely due to growing traffic loads and network sizes.
The main goal of traffic engineering is to achieve network resource efficiency by directing certain traffic flows to travel through some explicit routes other than the default paths determined by routing protocols, such as, for example, OSPF, EIGRP, and BGP. Conventionally, the key to achieving this goal is to select paths for selected traffic flows which meet the following two criteria:
(1) Conserve resources the selected path should consume as few resources as possible, especially when the network load is heavy; and
(2) Balance load the selected path should preferably not be congested, especially when the network load is concentrated.
These two criteria often conflict with each other: A path that consumes fewest network resources may be very congested. On the other hand, a path that is less congested may be many hops longer than the minimum-hop path to a particular node. Striking a balance between these two criteria when selecting a path has been the focus of recent studies in traffic engineering. Different service classes may deploy different resource sharing policies among their traffic flows. As a result, different traffic engineering algorithms may be used for different service classes.
While traffic engineering for individual traffic classes has been addressed in both telecommunication industry and data networking industry, traffic engineering that improves inter-class resource sharing for a network that supports multiple classes of service has received little attention. Current techniques statically partition link resources between different service classes and perform traffic engineering for each traffic class based on the resource availability for that traffic class. This approach is problematic since it is difficult if not impossible to make such a partition without either rejecting connections for guaranteed traffic (resulting in low network throughput) or causing congestion or starvation of best-effort traffic. Moreover, the traffic loads of the different traffic classes are not always evenly distributed over the network. For example, guaranteed sessions can be concentrated in one part of the network, while best-effort sessions can be concentrated in another part of the network. Static partitioning cannot adapt to such an imbalance.
Another common approach is to use the measured link utilization of both guaranteed traffic as well as best-effort traffic as the link state for the both traffic classes. This means that the traffic engineering algorithm for guaranteed traffic takes full consideration of the load conditions of best effort traffic, and routes guaranteed sessions along the links with low utilization. However, link utilization is not always a good indicator of how much bandwidth is available to reserve. For example, very bursty best-effort sessions can consume all link bandwidth, which leads to high utilization of the link, even though the link in question has reservable bandwidth. Thus, the traffic engineering algorithm for guaranteed traffic may reject a request even though reservable bandwidth is available.
Traffic engineering techniques in a multi-service class network may differ greatly from traffic engineering techniques in a single-service class network. Not only is there a need to take care of resource utilization efficiency within respective service classes, but there is also a need to avoid congestion or starvation of traffic flows having lower priority. For example, in a network that supports both bandwidth-guaranteed traffic and best-effort traffic, resources available to best-effort traffic rely on how guaranteed flows are routed. Guaranteed flows can reserve all bandwidth on certain links, thus result in congestion for, or even starvation of, best effort sessions. Additionally, statically partitioning the link resources can also result in low network throughput because of dynamic traffic mix. Thus, routing in a multi-class network is more than simply selecting for each flow an “optimal” path according to the routing algorithms developed for the traffic class of this flow, since such an “optimal” path can worsen the congestion condition of other flows belonging to different traffic classes.
It is therefore desirable to provide a multi-class traffic engineering technique which improves inter-class resource sharing efficiency and achieves high network throughput of each class of service in the network. It is also desirable to provide a multi-class traffic engineering technique that dynamically distributes link resources across different traffic classes based on load conditions of each traffic class. It is further desirable to provide a multi-class traffic engineering technique which is simple in design, and does not require modifications to existing routing algorithms employed for individual service classes within
Beyer Weaver & Thomas LLP.
Cisco Technology Inc.
Nguyen Phuongchau Ba
Nguyen Steven
LandOfFree
Traffic engineering technique for routing inter-class... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Traffic engineering technique for routing inter-class..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Traffic engineering technique for routing inter-class... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2927713