Multiplex communications – Pathfinding or routing
Reexamination Certificate
1999-12-18
2004-08-31
Olms, Douglas (Department: 2661)
Multiplex communications
Pathfinding or routing
C370S401000
Reexamination Certificate
active
06785260
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to communication networks, and, more particularly, to routing of best-effort and quality-of-service flows in a communication network.
BACKGROUND OF THE INVENTION
In packet networks such as the Internet, a simple static shortest path routing algorithm is commonly employed. A packet is sent on the shortest path to the destination. To determine the shortest path each link is assigned a weight and the shortest path is the one with the smallest aggregate weight. If there are multiple shortest paths, the shortest path is chosen arbitrarily. The key characteristic of this routing scheme is that the weights are assigned statically. The routes are static—not in the sense that the routes cannot change—but in the sense that the routes are load insensitive. Hence, route changes occur only when a change in the topology of the network occurs, i.e. a link is deleted or added. This topology-driven static shortest path routing may suffice in networks that provide a single best effort service in which there is no guarantee about whether and when a packet will be delivered. It may, however, not be adequate in networks that wish to provide Quality of Service (“QoS”) guarantees. For example, with reference to
FIG. 1
, consider if a network
100
provided bandwidth guarantees to a flow. A flow, as is known in the art, is a sequence of packets from a source to a destination and, or our purposes, is synonymous with a connection. Assuming each link specified in FIG.
1
is given an identical weight, all flows originating from node
101
and destined to
105
will be routed over path
101
-
102
-
103
-
104
-
105
. If a large number of flows originating from
101
and terminating at
105
request guaranteed bandwidth, then the links
102
-
103
and
103
-
104
may get saturated and flows may be denied their request. This may occur even though the alternate path
101
-
102
-
106
-
107
-
104
-
105
between
101
and
105
may have the capacity to support the flows that have been denied their request.
In order to exploit the available capacity on alternate routes, the concept of QoS routing has been proposed. See, e.g., E. Crawley et al., “A Framework for QoS Based Routing in the Internet,” RFC 2386, IETF Network Working Group, August 1998; R. Guerin et al., “QoS Routing Mechanisms and OSPF Extensions,” RFC 2676, IETF Network Working Group, August 1999, both of which are incorporated herein by reference. There are a large number of QoS routing algorithms. The characteristic common to all of these schemes is that they employ dynamically obtained information about load at each of the links to determine the path over which a flow should be routed. The path of a flow may be determined by source routing in which a flow setup message carries the entire path for the flow or by hop-by-hop routing. QoS routing algorithms have a few limitations.
First, in order to route packets of flows with the same destination over multiple routes, they require a connection-oriented network layer (i.e., the ability to “pin” the path of a flow). Thus, it is difficult to employ them in connectionless networks such as the Internet without substantial modifications to the basic architecture. Second, they can introduce routing and load oscillations resulting in higher instability in the performance seen by best-effort traffic. To illustrate, when the path
101
-
102
-
103
-
104
becomes loaded in
FIG. 1
, traffic will be diverted onto path
101
-
102
-
106
-
107
-
104
. This will increase the load on path
101
-
102
-
106
-
107
-
104
. Subsequently, when the load on path
101
-
102
-
103
-
104
reduces, the traffic will again be diverted onto path
101
-
102
-
103
-
104
. Thus, the best effort traffic flowing on those two paths will observe high instability in the performance—which is undesirable.
Accordingly, there is a substantial need for introducing new ways of routing QoS and best effort flows that avoids the disadvantages of the prior art.
SUMMARY OF THE INVENTION
The present invention permits quality-of-service routing without using any flow pinning or per-flow state mechanisms. In accordance with the present invention, load insensitive routing techniques are utilized for QoS traffic while load sensitive routing techniques are utilized for best effort traffic. In accordance with a preferred embodiment of the present invention, conventional static shortest path routing is utilized for flows that require QoS guarantees while known QoS routing techniques are utilized for best effort flows. Unlike the prior art, a single queue per class per link can be utilized at a network node. The present invention has numerous advantages over the prior art including reduced protocol overhead, lower cost, and reduced route instability.
These and other advantages of the invention will be apparent to those of ordinary skill in the art by reference to the following detailed description and the accompanying drawings.
REFERENCES:
patent: 5940372 (1999-08-01), Bertin
patent: 5995503 (1999-11-01), Crawley
patent: 6252856 (2001-06-01), Zhang
patent: 6292489 (2001-09-01), Fukushima
patent: 6321271 (2001-11-01), Kodialam
patent: 6347078 (2002-02-01), Narvaez-Guarnieri
patent: 6400681 (2002-06-01), Bertin
patent: 6493317 (2002-12-01), Ma
patent: 6538989 (2003-03-01), Carter
patent: 6538991 (2003-03-01), Kodialam
“Routing High-bandwidth traffic in min-max fair share networks”, Qingming Ma et al, Aug. 1997.*
“Routing traffic with Quality-of-Service Guarantees in Integrated Services Networks”, Qinming Ma et al, 1997.*
“On path selection for traffic with bandwidth guarantees”, Qinming Ma et al, IEEE, Oct. 1997.*
“Quality-of-service routing for traffic with performance guarantees”, Qinming Ma et al, 1997.
Goyal Pawan
Hjalmtysson Gisli
A.T.&T. Corp.
Olms Douglas
Pizarro Ricardo M.
LandOfFree
Method and apparatus for routing of best-effort and quality... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for routing of best-effort and quality..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for routing of best-effort and quality... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3342552