Backup peer pool for a routed computer network

• US 6,065,062 A
• Filed: 12/10/1997
• Issued: 05/16/2000
• Est. Priority Date: 12/10/1997
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Systems, Inc.
• Inventors: Clark, Wayne, Bordonaro, Frank, Periasamy, Ravi, Naderi, Ramin, Patel, Kushal A.
• Primary Examiner(s): Rinehart, Mark H.
• Assistant Examiner(s): Thompson, Marc D.
• Application Number:
  US08/987,899
• Time in Patent Office: 888 Days
• Field of Search: 709/227, 709/238, 709/239, 709/242, 709/228, 709/241, 709/244, 370/351, 370/355, 370/396, 370/397, 370/400, 340/825.02, 340/827, 340/825.01
• US Class Current: 709/242
• CPC Class Codes: H04L 12/462 LAN interconnection over a bridge based backbone
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/58 Association of routers
• CPC Class Codes: H04L 69/40 for recovering from a failure of a protocol instance or entity, e.g. service redundancy protocols, protocol state redundancy or protocol service redirection management of faults, events, alarms or notifications in data switching networks H04L41/06

Abstract

Backup peers in an asymmetrically organized computer network are organized into a "pool" of available devices that are activated as necessary. The network comprises a set of remote peers and a set of local peers directly associated with a central computational facility, the local peers facilitating connection between the remote peers and the central facility. During the capabilities exchange, the "primary" local peer to which the remote peer connects provides a list of backup peer devices to the remote peer. If the primary peer fails (or if the rate of message exchange falls below some predetermined threshold), the remote peer can use the backup information to access a backup peer from the pool. The invention allows each backup peer to be assigned to multiple remote peers, with the total number of backup peers determined by aggregate backup utilization (rather than simply assigning an individual backup peer to each primary peer regardless of whether such a high level of redundancy is justified).

Claims

1. In a computer network comprising a plurality of remote routing devices and a plurality of local routing devices connected to a central computational facility, the remote and local routing devices being capable of establishing connections facilitating exchange of data between the remote routing devices and the computational facility by way of the local routing devices, a method of providing connection backup between a remote routing device and the computational facility, the method comprising:

a. designating, for each local routing device, at least one backup routing device capable of establishing an internetwork-level data-transfer connection between a remote routing device and the computational facility; and

b. upon connection between a remote routing device and a local routing device, supplying the remote routing device with information identifying at least one designated backup local routing device to thereby facilitate an internetwork-level connection between the remote routing device and the computational facility by way of the at least one identified routing device.

2. The method of claim 1 wherein a capabilities exchange takes place upon connection between the remote routing device and the local routing device, the information-supplying step taking place during the capabilities exchange, the local and remote devices communicating by means of data-link switching.

3. The method of claim 1 wherein at least some of the backup routing devices are dedicated devices physically distinct from the local routing devices, the backup routing devices being fewer in number than the local routing devices.

4. The method of claim 3 wherein a plurality of backup routing devices is designated for each local routing device and each backup routing device is designated by a plurality of local routing devices, backup routing devices being designated by each local routing device in a hierarchical order of preference varying for at least some of the local routing devices so as to distribute backup responsibilities among the backup devices.

5. The method of claim 1 wherein at least some of the local routing devices also serve as backup routing devices.

6. The method of claim 1 wherein the connection-facilitating information provided to a remote routing device comprises a network address for each of a plurality of designated backup devices.

7. The method of claim 1 wherein a plurality of backup routing devices is designated for each local routing device, the connection-facilitating information originating with each local routing device.

8. The method of claim 7 wherein the designated backup routing devices are selected so as to minimize a cost of connection between the remote routing device and the backup routing devices.

9. The method of claim 8 wherein the backup routing devices each have a traffic level and a hardware configuration, the cost being based on the traffic level and the hardware configuration, and telecommunication charges for the connection between the remote routing device and the the backup routing devices.

10. The method of claim 7 wherein the designated backup routing devices are selected so as to balance traffic loads across the backup routing devices.

11. The method of claim 1 wherein a plurality of backup routing devices is designated for each local routing device, the connection-facilitating information originating, for each remote routing device, with the local routing device to which it is connected and the designated backup routing devices.

12. The method of claim 7 wherein a plurality of backup routing devices periodically report cost information to each local routing device, each local routing device designating backup routing devices based on the reported cost information.

13. The method of claim 1 wherein a plurality of backup routing devices is designated for each remote routing device, the connection-facilitating information originating with each remote routing device.

14. The method of claim 13 wherein a remote routing device chooses among the designated backup devices so as to minimize a cost of connection between the remote routing device and the backup routing devices.

15. The method of claim 13 wherein a remote routing device chooses among the designated backup devices so as to balance traffic loads across the backup routing devices.

16. For use in computer network having a plurality of remote routing devices and a plurality of local routing devices, an apparatus comprising:

a. a central computational facility to which the remote routing devices are connected, the remote and local routing devices being capable of establishing connections facilitating internetwork-level exchange of data between the remote routing devices and the computational facility by way of the local routing devices; and

b. means for providing connection backup between a remote routing device and the computational facility, said means comprising;

i. means for designating, for each local routing device, at least one backup routing device capable of establishing an internetwork-level data-transfer connection between a remote routing device and the computational facility; and

ii. means for supplying, upon connection between a remote routing device and a local routing device, the remote routing device with information identifying at least one designated backup local routing device to thereby facilitate an internetwork-level connection between the remote routing device and the computational facility by way of the at least one identified routing device.

17. The apparatus of claim 16 wherein the remote routing device and the local routing device are configured to perform a capabilities exchange upon connection therebetween, the connection-facilitating information being supplied during the capabilities exchange, the local and remote devices communicating by means of data-link switching.

18. The apparatus of claim 16 wherein at least some of the backup routing devices are dedicated devices physically distinct from the local routing devices, the backup routing devices being fewer in number than the local routing devices.

19. The apparatus of claim 18 wherein a plurality of backup routing devices is designated for each local routing device and each backup routing device is designated by a plurality of local routing devices, backup routing devices being designated by each local routing device in a hierarchical order of preference varying for at least some of the local routing devices so as to distribute backup responsibilities among the backup devices.

20. The apparatus of claim 16 wherein at least some of the local routing devices also serve as backup routing devices.

21. The apparatus of claim 16 wherein the connection-facilitating information provided to a remote routing device comprises a network address for each of a plurality of designated backup devices.

22. The apparatus of claim 16 wherein a plurality of backup routing devices is designated for each local routing device, the connection-facilitating information originating with each local routing device.

23. The apparatus of claim 22 wherein the designated backup routing devices are selected so as to minimize a cost of connection between the remote routing device and the backup routing devices.

24. The apparatus of claim 23 wherein the backup routing devices each have a traffic level and a hardware configuration, the cost being based on the traffic level and the hardware configuration, and telecommunication charges for the connection between the remote routing device and the backup routing devices.

25. The apparatus of claim 22 wherein the designated backup routing devices are selected so as to balance traffic loads across the backup routing devices.

26. The apparatus of claim 16 wherein a plurality of backup routing devices is designated for each local routing device, the connection-facilitating information originating, for each remote routing device, with the local routing device to which it is connected and the designated backup routing devices.

27. The apparatus of claim 22 wherein a plurality of backup routing devices are configured to periodically report cost information to each local routing device, each local routing device being configured to designate backup routing devices based on the reported cost information.

28. The apparatus of claim 16 wherein a plurality of backup routing devices is designated for each remote routing device, the connection-facilitating information originating with each remote routing device.

29. The apparatus of claim 28 wherein the remote routing devices are configured to choose among the designated backup devices so as to minimize a cost of connection between the remote routing device and the backup routing devices.

30. The apparatus of claim 28 wherein the remote routing devices are configured to choose among the designated backup devices so as to balance traffic loads across the backup routing devices.

31. In a computer network comprising a plurality of remote routing devices and a plurality of local routing devices connected to a central computational facility, the remote and local routing devices being capable of establishing connections facilitating exchange of data between the remote routing devices and the computational facility by way of the local routing devices, a computer storage medium containing executable instructional code, execution of the code facilitating connection backup between a remote routing device and the computational facility according to steps comprising:

a. designating, for each local routing device, at least one backup routing device capable of establishing an internetwork-level data-transfer connection between a remote routing device and the computational facility; and

b. upon connection between a remote routing device and a local routing device, supplying the remote routing device with information identifying at least one designated backup local routing device to thereby facilitate an internetwork-level connection between the remote routing device and the computational facility by way of the at least one identified routing device.

32. The medium of claim 31 wherein a capabilities exchange takes place upon connection between the remote routing device and the local routing device, the information-supplying step taking place during the capabilities exchange.

33. The medium of claim 31 wherein at least some of the backup routing devices are dedicated devices physically distinct from the local routing devices, the backup routing devices being fewer in number than the local routing devices.

34. The medium of claim 33 wherein a plurality of backup routing devices is designated for each local routing device and each backup routing device is designated by a plurality of local routing devices, backup routing devices being designated by each local routing device in a hierarchical order of preference varying for at least some of the local routing devices so as to distribute backup responsibilities among the backup devices.

35. The medium of claim 31 wherein at least some of the local routing devices also serve as backup routing devices.

36. The medium of claim 31 wherein the connection-facilitating information provided to a remote routing device comprises a network address for each of a plurality of designated backup devices.

37. The medium of claim 31 wherein a plurality of backup routing devices is designated for each local routing device, the connection-facilitating information originating with each local routing device.

38. The medium of claim 37 wherein the designated backup routing devices are selected so as to minimize a cost of connection between the remote routing device and the backup routing devices.

39. The medium of claim 38 wherein the backup routing devices each have a traffic level and a hardware configuration, the cost being based on the traffic level and the hardware configuration, and telecommunication charges for the connection between the remote routing device and the the backup routing devices.

40. The medium of claim 37 wherein the designated backup routing devices are selected so as to balance traffic loads across the backup routing devices.

41. The medium of claim 31 wherein a plurality of backup routing devices is designated for each local routing device, the connection-facilitating information originating, for each remote routing device, with the local routing device to which it is connected and the designated backup routing devices.

42. The medium of claim 37 wherein a plurality of backup routing devices periodically report cost information to each local routing device, each local routing device designating backup routing devices based on the reported cost information.

43. The medium of claim 31 wherein a plurality of backup routing devices is designated for each remote routing device, the connection-facilitating information originating with each remote routing device.

44. The medium of claim 43 wherein a remote routing device chooses among the designated backup devices so as to minimize a cost of connection between the remote routing device and the backup routing devices.

45. The medium of claim 43 wherein a remote routing device chooses among the designated backup devices so as to balance traffic loads across the backup routing devices.