Method and apparatus for providing quality of service routing in a network

• US 5,995,503 A
• Filed: 06/12/1996
• Issued: 11/30/1999
• Est. Priority Date: 06/12/1996
• Status: Expired due to Term

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Bay Networks, Inc. (Nortel Networks Corporation)
• Inventors: Sanchez, Cheryl A., Salkewicz, William M., Zhang, Zhaohui, Crawley, Eric S.
• Primary Examiner(s): NGUYEN, CHAU T
• Application Number:
  US08/661,312
• Time in Patent Office: 1,266 Days
• Field of Search: 370/400, 370/401, 370/402, 370/256, 370/254, 370/255, 370/238, 370/351, 395/200.48, 395/200.5, 395/200.57, 395/200.68, 395/200.69, 395/200.82
• US Class Current: 370/351
• CPC Class Codes: H04L 45/08 Learning-based routing, e.g. using neural networks or artificial intelligence

Abstract

A system for providing quality of service routing functions in a connectionless network having multiple nodes. The system generates a link resource advertisement for each node in the network. Each link resource advertisement includes information regarding link resources available on a particular node in the network. The system also generates resource reservation advertisements for each node in the network. Each resource reservation advertisement includes information regarding a particular node'"'"'s current reservations for a data flow. Network paths are calculated in response to a quality of service request. The calculations are performed based on information contained in the link resource advertisements and resource reservation advertisements.

Claims

1. A method for providing quality of service routing functions in a connectionless network having a plurality of nodes, said method comprising the steps of:

generating a link resource advertisement for each node in said network, each link resource advertisement including information regarding link resources available on a particular node in said network;

generating resource reservation advertisements for each node in said network, each resource reservation advertisement including information regarding a particular node'"'"'s reservations; and

calculating network paths in response to a quality of service request, said calculation based on said link resource advertisements and said resource reservation advertisements.

2. The method of claim 1 wherein said link resource advertisement includes a delay factor associated with each link coupled to the node.

3. The method of claim 1 wherein said link resource advertisement includes the largest amount of available resources for each of the node'"'"'s links.

4. The method of claim 1 wherein said link resource advertisement includes the available bandwidth on each link coupled to the node.

5. The method of claim 1 further including the step of supporting a path between a source and a destination, said path providing the requested quality of service.

6. The method of claim 5 wherein said path established between said source and said destination is pinned such that the path does not change in response to changes in available link resources.

7. The method of claim 5 wherein said path established between said source and said destination is pinned such that the path does not change in response to changes in network topology not affecting the pinned path.

8. The method of claim 1 wherein said network path is calculated based upon information contained in said link resource advertisements.

9. The method of claim 1 wherein said network path is calculated by considering only links and nodes having sufficient available resources.

10. The method of claim 1 wherein said link resource advertisement is a modified link state advertisement as used in the open shortest path first (OSPF) routing protocol.

11. A method for providing quality of service (QoS) routing functions in a network using the open shortest path first (OSPF) routing protocol, said method comprising the steps of:

generating a link resource advertisement for each router in said network, each link resource advertisement including information regarding link resources available on a particular router in said network;

generating resource reservation advertisements for each router in said network, each resource reservation advertisement including information regarding a particular router'"'"'s reservations; and

selecting a path for a requested QoS in based on information contained in said link resource advertisement and said resource reservation advertisement.

12. The method of claim 11 wherein said link resource advertisement includes a delay factor associated with each link coupled to the router.

13. The method of claim 11 wherein said link resource advertisement includes the available bandwidth on each link coupled to the router.

14. The method of claim 11 wherein said selected path is pinned such that the path does not change in response to changes in available link resources.

15. The method of claim 11 wherein said selected path is pinned such that the path does not change in response to changes in network topology not affecting the pinned path.

16. A method for providing quality of service (QoS) routing functions in a connectionless network having a plurality of nodes, said method comprising the steps of:

advertising network resources to said nodes in said network;

selecting a path through said network satisfying a requested QoS routing based on said advertised network sources, said advertised network sources comprising information regarding link resources of a particular node in said network and information regarding a particular node'"'"'s reservation in said network;

reserving network resources along said selected path; and

pinning said selected path such that the path does not change in response to changes in network resources.

17. The method of claim 16 wherein said path through said network is selected by considering network links having sufficient available resources for the required QoS.

18. The method of claim 16 wherein the step of advertising network resources further includes advertising a link resource advertisement including information regarding link resources available on a particular node in said network.

19. The method of claim 16 wherein the step of advertising network resources further includes advertising a resource reservation advertisement including information regarding a particular node'"'"'s reservations.

20. A method for establishing a quality of service (QoS) routing through a connectionless network having a plurality of nodes, said method comprising the steps of:

requesting a particular QoS routing through said network;

determining resources available on each node in said network;

determining resources currently reserved on each node in said network;

selecting a path having sufficient resources to satisfy said QoS routing requirements the path selection based upon information regarding link resources available on a particular node in said network and information regarding a particular node'"'"'s reservations in said network; and

reserving resources along said selected path.

21. The method of claim 20 wherein the step of selecting a path includes considering only network links having sufficient available resources for the required QoS.

22. The method of claim 20 wherein said selected path is pinned such that the path does not change in response to changes in available resources.