Distributed architecture and associated protocols for efficient quality of service-based route computation

• US 6,597,684 B1
• Filed: 12/24/1997
• Issued: 07/22/2003
• Est. Priority Date: 12/24/1997
• Status: Expired due to Term

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Hung, Ling-Yue, Rabie, Saman A., Ali, Zafar, Gulati, Neeraj
• Primary Examiner(s): Ton, Dang
• Assistant Examiner(s): NGUYEN, TOAN D
• Application Number:
  US08/998,223
• Time in Patent Office: 2,036 Days
• Field of Search: 370/254, 370/255, 370/351, 370/400, 370/401, 370/410
• US Class Current: 370/351
• CPC Class Codes: H04L 2012/562 Routing
• CPC Class Codes: H04L 2012/5621 Virtual private network [VPN]; Private-network - network-interface (P-NNI)
• CPC Class Codes: H04L 2012/5631 Resource management and allocation
• CPC Class Codes: H04L 2012/5638 Services, e.g. multimedia, GOS, QOS
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 47/783 Distributed allocation of resources, e.g. bandwidth brokers
• CPC Class Codes: H04L 47/805 QOS or priority aware
• CPC Class Codes: H04L 47/822 Collecting or measuring resource availability data
• CPC Class Codes: H04L 47/826 Involving periods of time
• CPC Class Codes: H04L 47/829 Topology based
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

In a packet switching network, a distributed architecture provides efficient computation of routes in Quality of Service (QoS)-based routing scenarios. Using a client-server model, only designated route servers store and maintain a database containing the entire network topology, so that each network node is not required to store and maintain the network topology. Client nodes maintain a cache containing pre-computed routes so that they can often make routing decisions autonomously. A client contacts a designated route server only when the client cannot obtain from its local cache a route to a given destination that meets the performance requirements. A client cache may contain pre-computed routes with designated QoS profiles to all destinations or to a subset of destinations. Route servers may also contain caches, which may contain pre-computed routes to all destinations in the network with all QoS profiles, or may contain only a subset of such routes.

Each client node may also be provided with intelligence to learn, maintain and adapt local information based on the statistical usage of the network. Client caches may learn statically, i.e, the cache contains routes based on a QoS profile provided by the network service provider, or they may learn dynamically, i.e., routes are modified based on ongoing network usage statistics. The goal is to minimize the need to contact the route server as much as possible. Protocols are defined to maintain synchronization between the route server and its clients distributed across the network. These protocols need to be observed to ensure that all nodes have the latest view of the network topology stored at the route server.

Claims

1. A method for selecting a route between a source node and a destination node wherein the route satisfies a QoS profile, wherein the source node stores in a route cache a plurality of pre-computed routes originating at the source node, and wherein the source node is connected to a route server, the method comprising:

searching the route cache for a route satisfying the QoS profile; and

if no satisfying route is found in the route cache, obtaining a route from the server satisfying the QoS profile

updating the contents of the route cache based on network usage, wherein updating includes adding the route computed at the server to the route cache wherein the step of updating further includes;

for each pre-computed route in the route cache, measuring time since the pre-computed route was added to the route cache to provide a stored time;

comparing the stored times to a predetermined route lifetime; and

purging from the route cache the pre-computed routes whose stored time exceeds the route lifetime.

2. The method of claim 1 wherein the step of updating further includes:

If the route cache is full before the computed route is added, removing one of the pre-computed routes from the route cache.

3. The method of claim 1 wherein the step of updating further includes:

for each pre-computed route in the route cache, measuring a last accessed time since the pre-computed route was selected as the route between the source node and the destination node;

comparing the last accessed measured times;

if the route cache is full before the computed route is added, choosing one of the pro-computed routes to be removed from the route cache based on the comparison of last accessed measured times; and

removing the chosen one of the pre-computed routes from the route cache.

4. The method of claim 1 wherein the step of updating further includes:

for each pre-computed route in the route cache, maintaining a count of the number of times a pre-computed route is selected as the route between the source and the destination node;

comparing the counts;

if the route cache is fall before the computed route is added, choosing one of the pre-computed routes to be removed from the route cache based on the comparison of counts; and

removing the chosen one of the pre-computed routes from the route cache.

5. The method of claim 1, wherein the step of updating further includes:

for each pre-computed route in the route cache, measuring the time since the pre-computed route was selected as the route between the source node and the destination node;

for each pre-computed route in the route cache, maintaining a count of the number of times a pre-computed route is selected as the route between the source node and the destination node;

weighting the counts by the measured times;

comparing the weighted counts;

if the route cache is full before the computed route is added, choosing one of the pre-computed routs to be removed from the route cache based on the comparison of the weighted counts; and

removing the chosen one of the pre-computed routes from the cache.

6. The method of claim 5 wherein the step of weighting the counts by the measured times includes the substep of

calculating a holding priority during the kth time interval according to the equation H_k=w*H_k−

1+(1−

w) U<sub>k−

1</sub>, where U<sub>k−

1</sub> is the count during the (k−

1)st interval, and w is a number such that 0<

=w<

=1; and

wherein the step of choosing one of the pre-computed routes to be removed includes the substep of

during the time period p, choosing the one of the pre-computed routes with the lowest H_p.

7. The method of claim 1 wherein the step of updating further includes:

for each pre-computed route in the route cache, measuring time since the pre-computed route was added to the route cache;

choosing one of the pro-computed routes to be purged from the mute cache based on the measured time; and

purging the chosen one of the pre-computed routes from the route cache.

8. The method of claim 1 wherein the step of updating further includes:

for each pre-computed route in the route cache, maintaining a count of the number of times a pre-computed route is selected as the route between the source node and the destination node;

updating the purged route based on a current state of the network; and

adding the updated route to the route cache if the count before purging exceeds a threshold.

9. A packet switching network comprising:

a route server;

a source node connected to a route server;

a destination node;

a route cache connected to the source node, the route cache containing a plurality of pre-computed routes originating at the source node; and

means for selecting a route between the source node and the destination node that satisfies a QoS profile, the means comprising;

means for searching the route cache for a route satisfying to the QoS profile;

means for obtaining a route from the server that satisfies the QoS profile if no satisfying route is found in the route cache;

means for updating the route cache based on network usage, wherein the means for updating includes means for adding lee route computed at the server to the route cache, wherein the means for updating further includes;

for each pre-computed route in the route cache, means for measuring time since the pre-computed route was added to the route cache;

means for comparing the measured times to a predetermined route lifetime; and

means for purging from the route cache the pre-computed routes whose measured time exceeds the route lifetime.

10. The network of claim 9 wherein the means for updating further includes:

means for removing one of the pre-computed routes from the route cache if the route cache is full before the computed route is added,

means for choosing one of the pre-computed routes to be removed from the route cache based on the comparison of counts if the route cache is full before the computed route is added; and

means for removing the chosen one of the pre-computed routes from the route cache.

11. The network of claim 9 wherein the means for updating further includes:

means for measuring time since each pre-computed route was selected as the route between the source node and the destination node;

means for comparing the measured times;

means for choosing one of the pre-computed routes to be removed from the route cache based on the comparison of measured times if the route cache is fall before the computed route is added; and

means for removing the chosen one of the pre-computed routes from the route cache.

12. The network of claim 9 wherein the means for updating further includes:

means for maintaining a count of the number of times each pre-computed route is selected as the route between the source node and the destination node;

means for comparing the counts;

means for choosing one of the pre-computed routes to be removed from the route cache based on the comparison of counts if the route cache is fall before the computed route is added; and

means for removing the chosen one of the pre-computed routes from the route cache.

13. The network of claim 9 wherein the means for updating further includes:

means for measuring time since each pre-computed route was selected as the route between the source node and the destination node;

means for maintaining a count of the number of times each pre-computed route is selected as the route between the source node and the destination node;

means for weighting the counts by the measured times;

means for comparing the weighted counts;

means for choosing one of the pre-computed routes to be removed from the route cache based on the comparison of weighted counts if the route cache is full before the computed route is added; and

means for removing the chosen one of the pre-computed routes from the route cache.

14. The network of claim 13 wherein the means for weighting tie counts by the measured times includes

means for calculating a holding priority during he kth time interval according to the equation H_k=w* H_k−

1+(1−

w) U<sub>k−

1</sub>, where U<sub>k−

1</sub> is the count during the (k−

1)st interval, and w is a number such that 0<

=w<

=1;

and wherein the means for choosing one of the pre-computed routes to be removed includes

means for choosing, during the time period p, the one of the pre-computed routes with the lowest H_p.

15. The network of claim 9 further comprising:

means for purging a pre-computed route from the route cache.

16. The network of claim 9 wherein the means for updating further includes:

for each pre-computed route in the route cache, means for measuring time since the pre-computed route was added to the route cache;

means for choosing one of the pre-computed routes to be purged from the route cache based on the measured time; and

means for purging the chosen one of the pre-computed routes from the route cache.

17. The network of claim 9 wherein the means for updating further includes:

for each pre-computed route in the route cache, means maintaining a count of the number of times a pre-computed route is selected as the route between the source node and the destination node;

means for updating the purged route based on a current state of the network; and

means for adding the updated route to the route cache if the count before purging exceeds a threshold.

18. A packet switching network comprising:

a plurality of route servers;

a plurality of client network nodes, each client node connected to a route server;

a route cache connected to each client node, the route cache containing a plurality of pre-computed routes originating at the client node;

a route cache connected to each route server containing a second plurality of pre-computed routes;

means for selecting a route between a first node and a second node that satisfies a QoS profile, the means comprising;

means for searching the client route cache for a route satisfying the QoS profile;

means for searching the server route cache for a route satisfying the QoS profile if no satisfying route is found in the client route cache; and

means for computing a route at the server that satisfies the QoS profile if no satisfying route is found in the server route cache.