Load sharing and redundancy scheme

• US 7,006,431 B1
• Filed: 11/26/2003
• Issued: 02/28/2006
• 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, Rajendran, Saravanakumar, Davar, Jonathan
• Primary Examiner(s): Duong, Frank
• Assistant Examiner(s): Jagannathan, Melanie
• Application Number:
  US10/723,371
• Time in Patent Office: 825 Days
• Field of Search: 370216-221, 370254-255, 370/389, 370/392, 370/401, 370/469, 370/236.1, 370/236.2, 370/416, 709238-249, 709/208, 709/220, 709213-216, 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 sharing a set of interfaces;

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

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

2. The device as recited in claim 1, wherein the first router and the second router are implemented in a single device, wherein the failure is detected through a signal sent within the device from the second router to the first router.

3. The device as recited in claim 1, further comprising:

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

means for 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;

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

means for updating the first set of forwarding data associated with the first router with the forwarding data updates sent from 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, further comprising:

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

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

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:

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

means for assigning a first MAC address to the first router;

means for assigning a second MAC address to the second router; and

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

8. The device as recited in claim 7, wherein a plurality of VLANs are coupled to the set of interfaces.

9. The device as recited in claim 8, further comprising:

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

10. The device as recited in claim 8, further comprising:

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

11. The device as recited in claim 8, further comprising:

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

12. The device as recited in claim 8, further comprising:

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

13. The device as recited in claim 9, wherein the source is one of the plurality of VLANS.

14. The device as recited in claim 8, further comprising:

means for associating the shared IP address with the first MAC address.

15. The device as recited in claim 14, further comprising:

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

16. The device as recited in claim 8, wherein the means for configuring a default gateway includes configuring a first default gateway and a second default gateway, the device further comprising:

means for associating a first host with a first default gateway; and

means for 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.

17. The device as recited in claim 1, further comprising:

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

18. The device as recited in claim 17, wherein the means for determining whether the first router or the second router functions as a master router comprises:

means for 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.

19. The device as recited in claim 17, wherein the means for determining comprises:

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

means for 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.

20. The device as recited in claim 1, further comprising:

means for 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.

21. A master router adapted for forwarding packets received at a set of interfaces, comprising:

means for maintaining a routing table;

means for running a protocol;

means for 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

means for 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.

22. The master router as recited in claim 21, wherein the protocol is a layer 2 protocol and the updates include layer 2 protocol updates, wherein the means for sending the updates comprises:

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

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

means for 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.

24. The master router as recited in claim 21, wherein the means for sending the updates comprises:

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

means for 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.

25. The master router as recited in claim 24, further comprising:

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

26. The master router as recited in claim 21, further comprising:

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

means for 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.

27. A slave router adapted for forwarding packets received at a set of interfaces, comprising:

means for maintaining a routing table;

means for 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

means for 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.

28. The slave router as recited in claim 27, wherein the protocol is a layer 2 protocol and the updates include layer 2 protocol updates.

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

30. The slave router as recited in claim 27, further comprising:

means for detecting a failure of the master router; and

means for running the protocol on the slave router.

31. The slave router as recited in claim 27, further comprising:

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

32. A switching system including a master router and a slave router having a shared set of interfaces, comprising:

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

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

means for 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;

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

means for 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.

33. The switching system as recited in claim 32, wherein obtaining packet header data from the shared set of interfaces is performed via the slave router.

34. The switching system as recited in claim 32, 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.

35. The switching system as recited in claim 32, further comprising:

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

means for maintaining a second routing table associated with the slave router.

36. The switching system as recited in claim 35, wherein the second routing table associated with the slave router is not recalculated in response to a failure of the master router.

37. The switching system as recited in claim 32, further comprising:

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

38. The switching system as recited in claim 37, wherein the means for updating the second set of forwarding data comprises:

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

39. 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, the system for forwarding a packet received at the set of interfaces comprising:

means for 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;

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

means for 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.

40. The system as recited in claim 39, 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 system further comprising:

means for detecting a failure of the master router; and

means for 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.

41. The system as recited in claim 40, further comprising:

means for 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.

42. The system as recited in claim 41, further comprising:

means for forwarding a packet via the second forwarding engine.

43. The system as recited in claim 39, 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 system further comprising:

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

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

44. The system as recited in claim 43, wherein the first routing protocol and the second routing protocol are different.

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

46. A computer-readable medium storing thereon computer-readable instructions for forwarding packets in a network, the network including a first router and a second router, the first router and the second router sharing a set of interfaces, comprising:

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

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

47. The computer-readable medium as recited in claim 46, wherein the first router and the second router are implemented in a single device, wherein the failure is detected through a signal sent within the device from the second router to the first router.

48. The computer-readable medium as recited in claim 46, further comprising:

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

instructions for 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;

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

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

49. The computer-readable medium as recited in claim 48, wherein the forwarding data updates include layer 2 protocol updates.

50. The computer-readable medium as recited in claim 48, further comprising:

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

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

51. The computer-readable medium as recited in claim 50, 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.

52. The computer-readable medium as recited in claim 46, further comprising:

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

instructions for assigning a first MAC address to the first router;

instructions for assigning a second MAC address to the second router; and

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

53. The computer-readable medium as recited in claim 52, wherein a plurality of VLANs are coupled to the set of interfaces.

54. The computer-readable medium as recited in claim 53, further comprising:

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

55. The computer-readable medium as recited in claim 53, further comprising:

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

56. The computer-readable medium as recited in claim 53, further comprising:

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

57. The computer-readable medium as recited in claim 52, further comprising:

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

58. The computer-readable medium as recited in claim 54, wherein the source is one of the plurality of VLANS.

59. The computer-readable medium as recited in claim 52, further comprising:

instructions for associating the shared IP address with the first MAC address.

60. The computer-readable medium as recited in claim 59, further comprising:

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

61. The computer-readable medium as recited in claim 52, wherein the instructions for configuring a default gateway includes configuring a first default gateway and a second default gateway, the computer-readable medium further comprising:

instructions for associating a first host with a first default gateway; and

instructions for 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.

62. The computer-readable medium as recited in claim 46, further comprising:

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

63. The computer-readable medium as recited in claim 62, wherein the instructions for determining whether the first router or the second router functions as a master router comprises:

instructions for 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.

64. The computer-readable medium, as recited in claim 62, wherein the instructions for determining comprises:

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

instructitons for 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.

65. The computer-readable medium as recited in claim 46, further comprising:

instructions for 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.

66. A computer-readable medium storing thereon computer-readable instructions for enabling a master router to forward packets received at a set of interfaces, comprising:

instructions for maintaining a routing table;

instructions for running a protocol;

instructions for 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

instructions for 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.

67. The computer-readable medium as recited in claim 66, wherein the protocol is a layer 2 protocol and the updates include layer 2 protocol updates, wherein the instructions for sending the updates comprises:

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

68. The computer-readable medium as recited in claim 66, wherein the updates do not include information associated with the routing table maintained by the master router, wherein the instructions for sending the updates comprises:

instructions for 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.

69. The computer-readable medium as recited in claim 66, wherein the instructions for sending the updates comprises:

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

instructions for 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.

70. The computer-readable medium as recited in claim 69, further comprising:

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

71. The computer-readable medium as recited in claim 66, further comprising:

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

instructions for 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.

72. A computer-readable medium storing thereon computer-readable instructions for enabling a slave router to forward packets received at a set of interfaces, comprising:

instructions for maintaining a routing table;

instructions for 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

instructions for 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.

73. The computer-readable medium as recited in claim 72, wherein the protocol is a layer 2 protocol and the updates include layer 2 protocol updates.

74. The computer-readable medium as recited in claim 72, wherein the updates do not include information associated with a layer 3 protocol.

75. The computer-readable medium as recited in claim 72, further comprising:

instructions for detecting a failure of the master router; and

instructions for running the protocol on the slave router.

76. The computer-readable medium as recited in claim 72, further comprising:

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

77. A computer-readable medium storing thereon computer-readable instructions for implementing a switching system including a master router and a slave router having a shared set of interfaces, comprising:

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

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

instructions for 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;

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

instructions for 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.

78. The computer-readable medium as recited in claim 77, wherein obtaining packet header data from the shared set of interfaces is performed via the slave router.

79. The computer-readable medium as recited in claim 77, 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.

80. The computer-readable medium as recited in claim 77, further comprising:

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

instructions for maintaining a second routing table associated with the slave router.

81. The computer-readable medium as recited in claim 80, wherein the second routing table associated with the slave router is not recalculated in response to a failure of the master router.

82. The computer-readable medium as recited in claim 77, further comprising:

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

83. The computer-readable medium as recited in claim 82, wherein updating the second set of forwarding data comprises:

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

84. A computer-readable medium storing thereon computer-readable instructions for supporting 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, the computer-readable medium storing thereon computer-readable instructions for forwarding a packet received at the set of interfaces, comprising:

instructions for 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;

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

instructions for 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.

85. The computer-readable medium as recited in claim 84, 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, further comprising:

instructions for detecting a failure of the master router; and

instructions for 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.

86. The computer-readable medium as recited in claim 85, further comprising:

instructions for 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.

87. The computer-readable medium as recited in claim 86, further comprising:

instructions for forwarding a packet via the second forwarding engine.

88. The computer-readable medium as recited in claim 84, 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, further comprising:

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

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

89. The computer-readable medium as recited in claim 88, wherein the first routing protocol and the second routing protocol are different.

90. The computer-readable medium as recited in claim 88, wherein the first routing protocol and the second routing protocol are identical.