Fast path forwarding of link state advertisements using reverse path forwarding

• US 6,871,235 B1
• Filed: 12/10/1999
• Issued: 03/22/2005
• Est. Priority Date: 12/10/1999
• Status: Expired due to Fees

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Cain, Bradley
• Primary Examiner(s): Dharia, Rupal
• Assistant Examiner(s): Mirza, Adnan M
• Application Number:
  US09/458,403
• Time in Patent Office: 1,929 Days
• Field of Search: 709/238, 709/239, 709/240, 709/241, 370/351
• US Class Current: 709/239
• CPC Class Codes: H04L 45/02 Topology update or discovery

Abstract

A link state advertisement protocol message received from an originating device over an inbound interface is forwarded over the fast path according to a reverse path forwarding determination. Specifically, a reverse path forwarding check is performed in order to determine the reverse path forwarding interface for the originating device. A forwarding state that indicates the reverse path forwarding interface may be installed, in which case the forwarding state may be used to determine the reverse path forwarding interface. If the inbound interface is determined to be the reverse path forwarding interface for the originating device, then the link state advertisement protocol message is forwarded over the fast path. Otherwise, the link state advertisement protocol message is not forwarded over the fast path. The link state advertisement protocol message continues to be processed and forwarded by the control plane as usual for robustness.

Claims

1. A method for propagating a link state advertisement protocol message by a network device in a communication network, the network device having a plurality of interfaces, a fast path for forwarding protocol messages, and a control plane for processing protocol messages, the method comprising:

receiving a link state advertisement protocol message from an originating device over an inbound interface;

determining whether the inbound interface is a reverse path forwarding interface for the originating device; and

forwarding the link state advertisement protocol message by the fast path, if and only if the inbound interface is determined to be the reverse path forwarding interface for the originating device.

2. The method of claim 1, wherein determining whether the interface is the reverse path forwarding interface for the originating device comprises:

performing a reverse path forwarding check to determine the reverse path forwarding interface for the originating device; and

determining whether the inbound interface is the reverse path forwarding interface indicated by the reverse path forwarding check.

3. The method of claim 2, wherein performing the reverse path forwarding check comprises:

performing the reverse path forwarding check based upon a router identifier in the link state advertisement protocol message, the router indicator identifying the originating device.

4. The method of claim 2, further comprising:

installing a forwarding state indicating the reverse path forwarding interface for the originating device.

5. The method of claim 1, wherein determining whether the inbound interface is the reverse path forwarding interface for the originating device comprises:

performing a reverse path forwarding check on the inbound interface to determine whether the inbound interface is the reverse path forwarding interface for the originating device.

6. The method of claim 5, wherein performing the reverse path forwarding check comprises:

performing the reverse path forwarding check based upon a router identifier in the link state advertisement protocol message, the router indicator identifying the originating device.

7. The method of claim 1, wherein determining whether the inbound interface is the reverse path forwarding interface for the originating device comprises:

maintaining a number of forwarding states, each forwarding state indicating a reverse path forwarding interface for one of a number of originating devices;

finding a forwarding state for the originating device in the forwarding table; and

determining whether the inbound interface is the reverse path forwarding interface indicated by the forwarding state for the originating device.

8. The method of claim 1, further comprising:

routing the link state advertisement protocol message to the control plane; and

processing the link state advertisement protocol message by the control plane.

9. The method of claim 8, further comprising:

forwarding the link state advertisement protocol message by the control plane.

10. A device for propagating a link state advertisement protocol message in a communication network, the device comprising:

a plurality of interfaces;

a control plane for processing protocol messages; and

a fast path coupled to the control plane and to the plurality of interfaces, the fast path comprising;

receiving logic operably coupled to receive a link state advertisement protocol message from an originating device over an inbound interface; and

fast path forwarding logic responsive to the receiving logic and operably coupled to forward the link state advertisement protocol message if and only if the inbound interface is a reverse path interface for the originating device.

11. The device of claim 10, further comprising:

reverse path forwarding logic operably coupled to determine the reverse path forwarding interface for the originating device.

12. The device of claim 11, further comprising:

forwarding state installation logic responsive to the reverse path forwarding logic and operably coupled to install a forwarding state in a forwarding table indicating the reverse path forwarding interface for the originating device.

13. The device of claim 10, wherein the fast path forwarding logic comprises:

reverse path forwarding logic operably coupled to perform a reverse path forwarding check on the inbound interface to determine whether the inbound interface is the reverse path forwarding interface for the originating device.

14. The device of claim 10, wherein the fast path forwarding logic comprises:

outbound interface determination logic operably coupled to determine outbound interface(s) for forwarding the link state advertisement protocol message.

15. The device of claim 10, further comprising a forwarding table having at least one forwarding state indicating the reverse path forwarding interface for the originating device.

16. The device of claim 15, wherein the fast path forwarding logic is operably coupled to forward the link state advertisement protocol message if and only if the inbound interface is the reverse path forwarding interface indicated by said forwarding state.

17. The device of claim 10, wherein the fast path forwarding logic is operably coupled to route the link state advertisement protocol message to the control plane for local processing of the link state advertisement protocol message.

18. The device of claim 17, wherein the control plane is operably coupled to forward the link state advertisement protocol message via the fast path.

19. A program product comprising a computer readable medium having embodied therein a computer program for propagating a link state advertisement protocol message by a network device in a communication network, the network device having a plurality of interfaces, a control plane for processing protocol messages, and a fast path for forwarding protocol messages, the computer program comprising:

receiving logic programmed to receive a link state advertisement protocol message from an originating device over an inbound interface; and

fast path forwarding logic responsive to the receiving logic and programmed to forward the link state advertisement protocol message if and only if the inbound interface is a reverse path interface for the originating device.

20. The program product of claim 19, wherein the computer program further comprises:

reverse path forwarding logic programmed to determine the reverse path forwarding interface for the originating device.

21. The program product of claim 20, wherein the computer program further comprises:

forwarding state installation logic responsive to the reverse path forwarding logic and programmed to install a forwarding state in a forwarding table indicating the reverse path forwarding interface for the originating device.

22. The program product of claim 19, wherein the fast path forwarding logic comprises:

reverse path forwarding logic operably coupled to perform a reverse path forwarding check on the inbound interface to determine whether the inbound interface is the reverse path forwarding interface for the originating device.

23. The program product of claim 19, wherein the fast path forwarding logic comprises:

outbound interface determination logic programmed to determine outbound interface(s) for forwarding the link state advertisement protocol message.

24. The program product of claim 19, wherein the network device includes a forwarding table having at least one forwarding state indicating the reverse path forwarding interface for the originating device, and wherein the fast path forwarding logic is programmed to forward the link state advertisement protocol message if and only if the inbound interface is the reverse path forwarding interface indicated by said forwarding state.

25. The program product of claim 19, wherein the fast path forwarding logic is programmed to route the link state advertisement protocol message to the control plane for local processing of the link state advertisement protocol message.