Efficient precomputation of quality-of-service routes

Details Efficient precomputation of quality-of-service routes Efficient precomputation of quality-of-service routes

1999-06-24

2003-10-14

Rao, Seema S. (Department: 2666)

Multiplex communications

Data flow congestion prevention or control

Flow control of data transmission through a network

C370S255000, C370S351000, C370S395500

Reexamination Certificate

active

06633544

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates generally to communication networks. In particular, the present invention is directed to a method and apparatus for computing, storing and allocating efficient routing connections between nodes in a network.
BACKGROUND INFORMATION
The performance and efficiency of packet switched networks is heavily dependent upon the routing algorithm implemented at the switches or routers in the network. In particular, the success of distributed audio and video applications hinges on predictable performance in the underlying communication network. A network can provide throughput and delay guarantees by reserving resources for individual connections or flows. The routing algorithm plays a pivotal role in this process by locating paths that can satisfy the performance requirements of arriving connections. This is particularly important for handling high-bandwidth multimedia streams, which often consume a relatively large fraction of the link capacity. Quality-of-service (“QoS”) routing has the potential to optimize the usage of network resources and increase the likelihood of accepting new connections by selecting paths based on existing network load and connection traffic parameters. For example, there has been considerable effort and attention to the use of the Internet for the delivery of multimedia traffic. However, because multimedia traffic requires high bandwidth and low latency, the necessity for efficient methods to insure QoS are exacting.
Efficient QoS routing requires effective techniques for computing routes and exchanging link-state information. Link-state is typically propagated in a periodic fashion or in response to a significant change in available capacity. For example, a link may advertise its available bandwidth metric whenever it changes by more than 10% since the previous update message. In addition, a minimum time between update messages is often imposed to avoid excessive link-state update traffic.
QoS guarantees may be implemented by utilizing a connection-oriented environment as opposed to a pure packet switched network. In a connection-oriented environment, a route is determined for each connection or flow and resources are reserved across the route (for each link) for the duration of a connection. In contrast, in a purely packet switched network, the route traversed by individual packets may change during the duration of a connection and resources are not reserved. For example, the ATM Forum's PNNI (“Private Network Network Interface”) standard defines a routing protocol for distributing topology and load information throughout the network, and a signaling protocol for processing the forwarding connection-establishment requests from the source. Similarly, proposed QoS extensions to the OSPF (“Open Shortest Path First Routing”) protocol include an “explicit routing” mechanism for source-directed IP (“Internet Protocol”) routing. MPLS (“MultiProtocol Label Switching”) includes a similar technique for constraint-based routing.
A number of packet routing algorithms are known. Many networks such as the Internet employ a static routing scheme. In static routing, all links in a network or domain are associated with a cost metric set in advance by a network adrninistrator. This link metric information is shared across the network domain such that each router is aware of the cost metric for every link in the network. Each router computes the lowest cost route to every other router in the network using a shortest-path algorithm such as Dijkstra's algorithm. Typically, the set of lowest-cost routes is stored in a routing table or cache at each router. When a packet arrives at a router, the router determines a next router to forward the packet to based upon the information in the static routing tables. Because in static routing all routers utilize identical information, all routers will calculate the same route for a packet. In the case of static link costs, propagation of link-state information between routers in a domain need only be effected infrequently, for example in the case of a link failure. Otherwise, the link state information, by definition, remains current.
However, static routing is inefficient because the load upon each link in a network or domain exhibits dynamic loading. Thus, the static costs associated with each link are inaccurate and the computation of the shortest cost route between a source and destination node, which rely upon these static cost metrics links, will not generate accurate results either. The inefficiency of static routing is most pronounced in a scenario where a highly sought resource suddenly becomes available on a network.
An attractive alternative to static routing is dynamic load-sensitive routing in which the cost metric for each link is continuously updated based upon the load measurement for the link. However, load-sensitive routing has an associated set of significant overheads. Namely, the distribution of link information itself increases the load on the network because each router is required to communicate the cost of each link to other routers as the link-state fluctuates. Second, link-state information may be dated or stale before it is used. This typically occurs because the time required to transmit link-state information is on the same order as the time required to send a packet (because both routing decisions and link-state is transmitted at the packet level). However, although load sensitive routing may prove inefficient at the packet level, in a connection oriented network, where connections are established for some length of time, load sensitive routing can improve efficiency.
A second issue regarding the implementation of routing policies concerns the distribution of the processing load required to compute routes through a network. In hop-by-hop routing, the routing work is shared among all nodes in a route, such that each node computes the next node in the route. However, in general, hop-by-hop routing is inefficient because it is desirable to know in advance, before a route is selected, that each link in the route can support the bandwidth required for a connection. Also, computing load-sensitive routes in a hop-by-hop fashion can lead to routing loops.
In source-directed routing, a source router or switch selects an entire route based upon connection throughput requirements and the available resources in the network (i.e., recent link state information). Each switch maintains its own view of the available link resources, distributes link-state information to other switches, and selects routes for new connections. To improve the scalability of these protocols in large configurations, the switches and links may be assigned to smaller peer groups or areas that exchange detailed link-state information. A network may be comprised of a multitude of peer groups or areas. Within a domain, each router has global knowledge of all links in its peer groups or areas and the associated cost metrics for these links. However, routers in a peer group or area typically only have limited knowledge about the link-state of the routers and links in external peer groups.
A goal of source-directed link-state routing is to minimize the probability that a chosen connection route will fail due to inadequate bandwidth. When a new connection is requested (i.e., the source is alerted to the bandwidth and destination for a connection), the source computes a route for the connection using the most recent link-state information. Based on the required bandwidth for the connection, the source node may eliminate some links because they cannot support the required bandwidth. For example, infeasible links may be pruned using the test (util(
1
)+b>1?), where util(
1
) is a utilization parameter associated with the current connection request and b is the bandwidth currently used on the link. Then, the source router runs a shortest path algorithm (e.g., Dijkstra's algorithm) in order to calculate the lowest cost path to the destination node. These costs are typically based

Affiliated with

Also associated with

Rating

Efficient precomputation of quality-of-service routes does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Efficient precomputation of quality-of-service routes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient precomputation of quality-of-service routes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3153699