Load sharing and redundancy scheme

• US 6,751,191 B1
• Filed: 06/29/1999
• Issued: 06/15/2004
• Est. Priority Date: 06/29/1999
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Kanekar, Bhushan Mangesh, Davar, Jonathan, Rajendran, Saravanakumar
• Primary Examiner(s): Rao, Seema S.
• Assistant Examiner(s): Jagannathan, Melanie
• Application Number:
  US09/342,859
• Time in Patent Office: 1,813 Days
• Field of Search: 370/216-220, 370/221, 370/401, 370/416, 370/236.1, 370/236.2, 370/469, 370/254, 370/255, 370/389, 370/392, 714/2, 714/3, 709/208, 709/213-216, 709/220, 709/238, 709/239, 709/242, 709/249, 709/203
• US Class Current: 370/217
• CPC Class Codes: H04L 12/4641 Virtual LANs, VLANs, e.g. virtual private networks [VPN] LAN interconnection over a bridge based backbone H04L12/462; encapsulation techniques H04L12/4633; routing of packets H04L45/00; packet switches H04L49/00; virtual private networks for security H04L63/0272
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/58 Association of routers

Abstract

Methods and apparatus for providing a device for forwarding packets in a network are disclosed. A first router and a second router having a shared set of interfaces are provided, enabling the first router and the second router to share forwarding data for forwarding packets on the shared set of interfaces.

Claims

1. A device for forwarding packets in a network, comprising:

a first router having a first processor and a first memory associated therewith; and

a second router having a second processor and a second memory associated therewith, the first router and the second router having a shared set of interfaces, the shared set of interfaces enabling the first router and the second router to share forwarding data for forwarding packets on the shared set of interfaces and to share updates including at least one of synchronized state information indicating states of ports associated with the set of interfaces and VLAN membership.

2. The device as recited in claim 1, wherein the first router and the second router are provided in a single device, thereby enabling communication between the first router and the second router, wherein the communication occurs in a backplane of the device such that the first router replaces the second router upon detection of failure of the second router.

3. The device as recited in claim 1, wherein

the first memory includes a first set of forwarding data associated with the first router; and

the second memory includes a second set of forwarding data associated with the second router, the first set of forwarding data and the second set of forwarding data comprising layer 2 protocol information and layer 3 protocol information for forwarding packets;

wherein the first set of forwarding data associated with the first router includes forwarding data updates sent from the second router to the first router prior to the failure of the second router.

4. The device as recited in claim 3, wherein the forwarding data updates include layer 2 protocol updates.

5. The device as recited in claim 3, wherein the first set of forwarding data associated with the first router further includes data obtained by the first router from the shared set of interfaces prior to the failure of the second router.

6. The device as recited in claim 5, wherein the data obtained by the first router includes one or more shortcuts established by the second router, the one or more shortcuts specifying layer 3 forwarding information.

7. The device as recited in claim 1, further comprising a memory coupled to at least one of the routers, the memory storing a set of configuration information for configuring the first router and the second router.

8. The system as recited in claim 7, wherein the set of configuration information comprising a number of ports associated with both the first router and the second router, a type of the ports associated with both the first router and the second router, and a single set of security information associated with both the first router and the second router.

9. A method of forwarding packets in a network, comprising:

providing a first router;

providing a second router, the first router and the second router sharing a single set of interfaces;

sending synchronized state information indicating states of ports associated with the set of interfaces and VLAN membership information via the set of interfaces; and

detecting a failure of the second router such that the first router forwards packets received at the single set of interfaces in response to the detection of failure of the second router.

10. The method as recited in claim 9, further including

providing the first router and the second router in a single device, wherein the failure is detected through a signal sent within the device from the second router to the first router.

11. The method as recited in claim 9, further comprising:

maintaining a first set of forwarding data associated with the first router;

maintaining a second set of forwarding data associated with the second router, the first set of forwarding data and the second set of forwarding data comprising layer 2 protocol information and layer 3 protocol information for forwarding packets;

sending forwarding data updates from the second router to the first router prior to the failure of the second router; and

updating the first set of forwarding data associated with the first router with the forwarding data updates sent from the second router.

12. The method as recited in claim 11, wherein the forwarding data updates include layer 2 protocol updates.

13. The method as recited in claim 11, further comprising:

obtaining data from the shared set of interfaces by the first router prior to the failure of the second router; and

incorporating the obtained data in the first set of forwarding data.

14. The method as recited in claim 13, wherein the data obtained by the first router includes one or more shortcuts established by the second router, the one or more shortcuts specifying layer 3 forwarding information.

15. The method as recited in claim 9, further comprising:

assigning a shared IP address and shared MAC address to the first router and the second router;

assigning a first MAC address to the first router;

assigning a second MAC address to the second router; and

configuring a default gateway such that a default gateway IP address is associated with the shared IP address.

16. The method as recited in claim 15, further comprising:

associating the shared IP address with the first MAC address.

17. The method as recited in claim 16, further comprising:

associating the shared IP address with the second MAC address in response to a failure of the first router.

18. The method as recited in claim 15, wherein configuring a default gateway includes configuring a first default gateway and a second default gateway, the method further comprising:

associating a first host with a first default gateway; and

associating a second host with a second default gateway, wherein the first default gateway and the second default gateway are identified with at least one of the first router and the second router, thereby enabling a packet to be forwarded via the first or the second default gateway when at least one of the source and destination of the packet identifies the first host or the second host.

19. The method as recited in claim 9, further comprising:

determining whether the first router or the second router functions as a master router.

20. The method as recited in claim 19, wherein determining whether the first router or the second router functions as a master router comprises:

ascertaining from priorities assigned to the first router and the second router which of the first router and the second router functions as the master router.

21. The method as recited in claim 19, wherein determining comprises:

receiving a signal at the first router from the second router;

ascertaining whether the signal asserts that the second router is the master router;

wherein when it is ascertained that the signal asserts that the second router is the master router, it is ascertained that the first router is the slave router; and

wherein when it is ascertained that the signal does not assert that the second router is the master router, it is ascertained that the first router is the master router.

22. The method as recited in claim 9, further comprising:

reading a configuration file for configuration information for both the first router and the second router, wherein at least some of the configuration information is identical for the first router and the second router.

48. The method as recited in claim 15, wherein a plurality of VLANs are coupled to the set of interfaces.

49. The method as recited in claim 48, further comprising:

performing load distribution among the first router and the second router based upon a source of incoming packets.

50. The method as recited in claim 48, further comprising:

associating the plurality of VLANs with one or more default gateways.

51. The method as recited in claim 48, further comprising:

associating one or more of the plurality of VLANs with the default gateway.

52. The method as recited in claim 15, further comprising:

associating one or more of the set of interfaces with the default gateway.

53. The method as recited in claim 49, wherein the source is one of the plurality of VLANS.

23. In a master router, a method of forwarding packets received at a set of interfaces, the method comprising:

maintaining a routing table;

running a protocol;

updating a database in the master router with updates, the updates including at least one of synchronized state information indicating states of ports associated with the set of interfaces and VLAN membership of the master router; and

sending the updates to a slave router, thereby enabling the slave router to forward packets received at the set of interfaces using the updates received from the master router.

24. The method as recited in claim 23, wherein the protocol is a layer 2 protocol and the updates include layer 2 protocol updates, wherein sending the updates comprises:

sending synchronized state information from the master router to the slave router to synchronize states of ports associated with the set of interfaces.

25. The method as recited in claim 23, wherein the updates do not include information associated with the routing table maintained by the master router, wherein sending the updates comprises:

sending VLAN membership of the master router to the slave router such that the slave has access to each VLAN associated with the master router upon failure of the master router.

26. The method as recited in claim 23, wherein sending the updates comprises:

sending synchronized state information from the master router to the slave router to synchronize states of ports associated with the set of interfaces; and

sending VLAN membership of the master router to the slave router such that the slave has access to each VLAN associated with the master router upon failure of the master router.

27. The method as recited in claim 26, further comprising:

using the synchronized state information on the slave router in response to a detection of failure of the master router.

28. The method as recited in claim 23, further including:

sending forwarding engine information from the master router to the slave router such that the second forwarding engine is initialized; and

sending hardware information from the master router to the slave router, the hardware information including at least one of temperature and indication of power supply failure.

29. In a slave router, a method of forwarding packets received at a set of interfaces, the method comprising:

maintaining a routing table;

receiving updates from a master router running a protocol, the updates including at least one of synchronized state information indicating states of ports associated with the set of interfaces and VLAN membership of the master router; and

updating a database with the updates received from the master router, thereby enabling the slave router to forward packets received at the set of interfaces upon failure of the master router.

30. The method as recited in claim 29, wherein the protocol is a layer 2 protocol and the updates include layer 2 protocol updates.

31. The method as recited in claim 29, wherein the updates do not include information associated with a layer 3 protocol.

32. The method as recited in claim 29, further comprising:

detecting a failure of the master router; and

running the protocol on the slave router.

33. The method as recited in claim 29, further comprising:

sending acknowledgement of the updates from the slave router to the master router.

34. A method of forwarding packets in a switching system, the system comprising a master router and a slave router having a shared set of interfaces, the method comprising:

maintaining a first set of forwarding data for the master router and a second set of forwarding data for the slave router;

sending forwarding data updates from the master router to the slave router;

sending at least one of synchronized state information indicating states of ports associated with the set of interfaces and VLAN membership of the master router to the slave router;

obtaining packet header data from the shared set of interfaces; and

updating the second set of forwarding data with the forwarding data updates sent from the master router and the packet header data obtained from the shared set of interfaces.

35. The method as recited in claim 34, wherein obtaining packet header data from the shared set of interfaces is performed with the slave router.

36. The method as recited in claim 34, wherein the forwarding data updates include layer 2 protocol updates and the packet header data obtained from the shared set of interfaces includes one or more shortcuts established by the master router, the one or more shortcuts specifying layer 3 forwarding information.

37. The method as recited in claim 34, further comprising:

maintaining a first routing table associated with the master router; and

maintaining a second routing table associated with the slave router.

38. The method as recited in claim 37, wherein the second routing table associated with the slave router is not recalculated in response to a failure of the master router.

39. The method as recited in claim 34, further comprising:

updating the second set of forwarding data in response to a failure of the master router.

40. The method as recited in claim 39, wherein updating the second set of forwarding data comprises:

invalidating one or more shortcuts established by the master router, the one or more shortcuts specifying layer 3 forwarding information.

41. In a system including a first router and a second router having a shared set of interfaces, a first forwarding engine coupled to the set of interfaces and the first router, the first forwarding engine being associated with a first set of forwarding engine tables for facilitating forwarding of packets in hardware, and a second forwarding engine coupled to the set of interfaces and the second router, the second forwarding engine being associated with a second set of forwarding engine tables for facilitating forwarding of packets in hardware, a method of forwarding a packet received at the set of interfaces comprising:

sending at least one of synchronized state information indicating states of ports associated with the set of interfaces and VLAN membership of the first router to the second router;

observing the packet at the set of interfaces to obtain information from the packet; and

updating the first and second sets of forwarding engine tables with the obtained information such that the packet is associated with at least one of the first router and the second router, thereby enabling the first router and the second router to forward a packet using the obtained information.

42. The method as recited in claim 41, wherein the first forwarding engine has an associated layer 2 table and layer 3 table, and the second forwarding engine has an associated layer 2 table and layer 3 table, wherein the layer 2 tables each associate one or more MAC addresses with the first router or the second router, and wherein the layer 3 tables each specify one or more shortcuts including layer 3 forwarding information, each one of the shortcuts being associated with a flow associated with a source IP address and destination IP address, the method further comprising:

detecting a failure of the master router; and

updating entries in the layer 2 table associated with the slave router such that each one of the entries is mapped to the slave router rather than the master router.

43. The method as recited in claim 42, further comprising:

removing selected entries in the layer 3 table associated with the slave router, the selected entries specifying shortcuts associated with the master router, thereby enabling replacement entries to be created upon forwarding of packets such that the replacement entries specify shortcuts associated with the slave router.

44. The method as recited in claim 43, further comprising:

forwarding a packet via the second forwarding engine.

45. The method as recited in claim 41, wherein the first router has an associated first routing table for facilitating forwarding of packets in software and the second router has an associated second routing table for facilitating forwarding of packets in software, the method further comprising:

running a first routing protocol on the first router and a second routing protocol on the second router; and

separately building the first routing table and the second routing table.

46. The method as recited in claim 45, wherein the first routing protocol and the second routing protocol are different.

47. The method as recited in claim 45, wherein the first routing protocol and the second routing protocol are identical.