System for generating explicit routing advertisements to specify a selected path through a connectionless network to a destination by a specific router

• US 5,881,246 A
• Filed: 06/12/1996
• Issued: 03/09/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: Salkewicz, William M., Zhang, Zhaohui, Crawley, Eric S.
• Primary Examiner(s): Luu, Le Hien
• Application Number:
  US08/661,311
• Time in Patent Office: 1,000 Days
• Field of Search: 380/49, 370/236, 370/396, 370/392, 370/397, 395/200.72, 395/200.68, 395/200.7, 395/200.69
• US Class Current: 709/238
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/03 by updating link state protocols

Abstract

A system for providing explicit routing functions in a connectionless network. A specific router selects a path through the connectionless network to a destination. Explicit routing advertisements are generated by the specific router and contain information regarding the selected path. Routing state is installed according to information contained in the explicit routing advertisements. The explicit routing advertisements are forwarded to each next hop router. Each next hop router installs routing state, generates the explicit routing advertisement, and forwards the explicit routing advertisement to further propagate the routing information.

Claims

1. A method for providing explicit routing functions in a connectionless network, said method comprising the steps of:

selecting a path through said network to a destination, said path selected by a specific router;

generating explicit routing advertisements (ERAs) containing information regarding said selected path, said ERAs generated by said specific router;

installing a routing state according to information contained in said ERAs;

forwarding said ERAs to each next hop router; and

repeatedly installing routing state, generating said ERAs, and forwarding said ERAs to other routers along the path until all routers on the path have installed routing state.

2. The method of claim 1 wherein said ERAs include an encoded distribution tree generated by said specific router.

3. The method of claim 2 wherein said ERAs include an offset value to identify certain portions of said encoded distribution tree.

4. The method of claim 2 wherein said ERAs include an adjust offset value and a child offset value to identify certain portions of said encoded distribution tree.

5. The method of claim 2 wherein each next hop router changes an offset value in a received ERA to identify relevant portions of said encoded distribution tree for all routers on the path.

6. The method of claim 1 further including the step of flushing said installed routing states when said path is no longer needed.

7. The method of claim 6 wherein the step of flushing said installed routing states includes forwarding a flushing ERA along said path.

8. A method for providing an explicit route to a destination in a connectionless network, said method comprising the steps of:

a) selecting a path through said network to said destination, said path selected by a specific router;

b) generating an explicit routing advertisement (ERA) for said specific router, said ERA containing information regarding said selected path;

c) generating a next hop ERA for each next hop router and forwarding said ERA to its associated next hop router;

d) installing a routing state in said next hop router according to information contained in said next hop router ERA; and

e) repeating steps c) and d) until all routers on the path have installed routing state.

9. The method of claim 8 wherein said ERAs include an encoded distribution tree generated by said specific router.

10. The method of claim 9 wherein said ERAs further include an offset value to identify certain portions of said encoded distribution tree.

11. The method of claim 9 wherein said ERAs include an adjust offset value and a child offset value to identify certain portions of said encoded distribution tree.

12. The method of claim 9 wherein each next hop router changes an offset value in a received next hop ERA to identify relevant portions of said encoded distribution tree for all routers on the path.

13. The method of claim 8 further including the step of flushing said installed routing states when said path is no longer needed.

14. The method of claim 13 wherein the step of flushing said installed routing states includes forwarding a flushing ERA along said path.