Method and apparatus for routing server redundancy in a network having carrier scale internetworking

• US 6,438,100 B1
• Filed: 08/05/1999
• Issued: 08/20/2002
• Est. Priority Date: 08/07/1998
• Status: Expired due to Term

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Alcatel Canada Inc. (Nokia Corporation)
• Inventors: Chen, Wan, Becka, Zdenek, Halpern, Joel M.
• Primary Examiner(s): HSU, ALPUS
• Application Number:
  US09/368,752
• Time in Patent Office: 1,111 Days
• Field of Search: 370/216, 370/217, 370/218, 370/254, 370/255, 370/256, 370/389, 370/395.1, 370/396, 370/397, 370/400, 370/401, 370/409, 370/428, 370/429, 709/201, 709/202, 709/203, 709/220, 709/221, 709/238, 709/249, 709/252, 714/1, 714/2, 714/3, 714/4
• US Class Current: 370/218
• CPC Class Codes: H04L 12/4604 LAN interconnection over a backbone network, e.g. Internet, Frame Relay

Abstract

A method and apparatus provides greater flexibility, scalability and manageability when multiple services are being supported by a Carrier Scale Internetworking (CSI) system by including processing that detects when connectivity to an Route Server Instance (RSI) host that is supporting an active RSI has failed and provides a replacement RSI host from a redundancy set. In additional, forwarders (i.e., core forwarder, edge forwarder, and/or default forwarder), upon detecting a change in the RSI host, connect to the new RSI host. RSI hosts in the redundancy set use a redundancy chain protocol to select the new RSI host to function as the active RSI. Note that an RSI host may be a virtual entity on a routing service control point (RSCP) that indicates that this RSI Host has the capability to become an active RSI, wherein an active RSI is an RSI Host that is running the RSI.

Claims

1. A Carrier Scale Internetworking (CSI) system that provides multiple services, the CSI system comprises:

a plurality of routing service control points, wherein each of the plurality of routing service control points includes at least one routing service instance to provide routing information for a realm, wherein the realm is a specific instance of one of the multiple services, and wherein at least one of the plurality of routing service control points includes the at least one routing service instance of another one of the plurality of routing service control points for redundancy;

a plurality of access terminations operable to provide user access to the CSI system;

a plurality of edge forwarders each operably coupled to at least one of the plurality of access terminations, wherein each of the edge forwarders establish associations with at least one routing service instance on at least one routing service control point to forward data to a user associated with the realm;

a default forwarder operably coupled to the plurality of edge forwarders, wherein the default forwarder receives packets for forwarding from at least one of the plurality of edge forwarders when the one of the plurality of edge forwarders is retrieving forwarding information;

a configuration server that maintains state information for a plurality of clients and provides operational information to at least one client of the plurality of clients, wherein the plurality of clients include at least some of the routing service control points, at least some of the edge forwarders, and the default forwarder.

2. The CSI system of claim 1 further comprises a core forwarder operably coupled to at least some of the plurality of edge forwarders, wherein the core forwarder provide a forwarding path for at least one of the plurality of edge forwarders when the one of the plurality of edge forwarders cannot hold full forwarding databases.

3. The CSI system of claim 2, wherein the core forwarder is operably coupled to the routing service engine to receive routing service instance instructions that indicate which forwarding paths to establish and how packets are to be forwarded.

4. The CSI system of claim 1, wherein each of the routing service instances generate routing information for at least one of:

a corresponding one of the plurality of edge forwarders and the default forwarder and provide the routing information to the at least one of the corresponding one of the plurality of edge forwarders and the default forwarder.

5. The CSI system of claim 4, wherein each of the routing service instances further function to exchange the routing information with other routing service instances inside the realm and outside the realm for maintaining routing control information or realm topology information.

6. The CSI system of claim 5, wherein the routing service instances are arranged into redundancy sets such that an active routing service instance is readily determinable by the CSI system for the realm by performing at least one of:

a routing service host/one of the plurality edge forwarders or the default forwarder to the configuration server interaction, routing service instance host to routing service instance host interaction, and the one of the plurality edge forwarders or the default forwarder to the routing service instance host interaction.

7. The CSI system of claim 6, wherein the corresponding one of the plurality of edge forwarders and the default forwarder and the routing service instance host further function to establish an initial one of the redundancy sets utilizing an ordered list of routing service instance hosts, wherein the routing service instance host uses the ordered list to determine which of the adjacent neighbors are active, and wherein the corresponding one of the plurality of edge forwarders and the default forwarder uses the ordered list to determine which of the routing service instances hosts to connect to.

8. The CSI system of claim 1, wherein each of the plurality of edge forwarders further functions to perform preliminary authentication of users.

9. The CSI system of claim 1, wherein the configuration server further functions to update state information for each of the plurality of clients when any configuration changes occur, where the changes include addition, deletion, and/or failure of relevant corresponding one of the plurality of routing service control points.

10. The CSI system of claim 1, wherein the operational information comprises identity of a routing service instance to be running on a corresponding one of the plurality of routing service control points, identity of realms for which the routing service instances are responsible, routing service control points redundancy information, and the control interface information.

11. The CSI system of claim 1, wherein the default forwarder further functions to provide temporary support for the realm when the realm requires detailed per-flow-forwarding policy.

12. The CSI system of claim 1, wherein each of the plurality of edge forwarders establish the association with the at least one routing service instance based on the configuration information received from the configuration server and registering with the at least one routing service instance as a client.

13. The CSI system of claim 1, wherein one of the plurality of edge forwarders establishes connections with at least one other of the plurality of edge forwarders based on information contained in the routing service instance or to establish a direct shortcut connection.

14. The CSI system of claim 1, wherein at least one of the plurality of edge forwarders classifies packets according to the realm and quality of service, marks and manipulates packets, and provides differential policing and scheduling for flows based on instructions from a corresponding one of the plurality of routing service control points.

15. A method for providing multiple services on a Carrier Scale Internetworking (CSI) system, the method comprises the steps of:

identifying at least one routing service instance of at least one of a plurality of routing service control points to provide routing for a realm, wherein the realm is a specific instance of one of the multiple services;

establishing an association between one of a plurality of edge forwarders with at least one routing service instance on at least one routing service control point to forward data to a user associated with the realm;

receiving, by a default forwarder, packets for forwarding from at least one of the plurality of edge forwarders when the one of the plurality of edge forwarders is retrieving forwarding information;

maintaining state information for a plurality of clients, wherein the plurality of clients include at least some of the routing service control points, at least some of the edge forwarders, and the default forwarder; and

providing operational information to at least one client of the plurality of clients.

16. The method of claim 15 further comprises providing a forwarding path for at least one of the plurality of edge forwarders when the one of the plurality of edge forwarders cannot hold full forwarding databases.

17. The method of claim 16 further comprises receiving routing service instance instructions that indicate which forwarding paths to establish and how packets are to be forwarded.

18. The method of claim 15 further comprises:

generating routing information for at least one of;

a corresponding one of the plurality of edge forwarders and the default forwarder; and

providing the routing information to the at least one of the corresponding one of the plurality of edge forwarders and the default forwarder.

19. The method of claim 18 further comprises:

exchanging the routing information between routing service instances inside the realm and outside the realm for maintaining routing control information or realm topology information, wherein the exchange is performed by transmitting chain updates to adjacent neighbors.

20. The method of claim 19 further comprises arranging the routing service instances into redundancy sets such that an active routing service instance is readily determinable by the CSI system for the realm by performing at least one of:

a routing service host/one of the plurality edge forwarders or the default forwarder to the configuration server interaction, routing service instance host to routing service instance host interaction, and the one of the plurality edge forwarders or the default forwarder to the routing service instance host interaction.

21. The method of claim 20 further comprises establishing an initial one of the redundancy sets utilizing an ordered list of routing service instance hosts, wherein the routing service instance host uses the ordered list to determine which of the adjacent neighbors are active, and wherein the corresponding one of the plurality of edge forwarders and the default forwarder uses the ordered list to determine which of the routing service instances hosts to connect to.

22. The method of claim 15 further comprises updating state information for each of the plurality of clients when any configuration changes occur, where the changes include addition, deletion, and/or failure of relevant corresponding one of the plurality of routing service control points.

23. The method of claim 15 further comprises establishing connections between the plurality of edge forwarders based on configuration instructions or to establish a direct shortcut connection.

24. A Carrier Scale Internetworking (CSI) system that provides multiple services, the CSI system comprises:

a processing module; and

memory operably coupled to the processing module, wherein the memory stores operational instructions that cause the processing module to;

(a) identify at least one routing service instance of at least one of a plurality of routing service control points to provide routing for a realm, wherein the realm is a specific instance of one of the multiple services;

(b) establish an association between one of a plurality of edge forwarders with at least one routing service instance on at least one routing service control point to forward data to a user associated with the realm;

(c) receive, as a default forwarder, packets for forwarding from at least one of the plurality of edge forwarders when the one of the plurality of edge forwarders is retrieving forwarding information;

(d) maintain state information for a plurality of clients, wherein the plurality of clients include at least some of the routing service control points, at least some of the edge forwarders, and the default forwarder; and

(e) provide operational information to at least one client of the plurality of clients.

25. The CSI system of claim 24, wherein the memory further comprises operational instructions that cause the processing module to provide a forwarding path for at least one of the plurality of edge forwarders when the one of the plurality of edge forwarders cannot hold full forwarding databases.

26. The CSI system of claim 25, wherein the memory further comprises operational instructions that cause the processing module to receive routing service instance instructions that indicate which forwarding paths to establish and how packets are to be forwarded.

27. The CSI system of claim 24, wherein the memory further comprises operational instructions that cause the processing module to:

generate routing information for at least one of;

a corresponding one of the plurality of edge forwarders and the default forwarder; and

provide the routing information to the at least one of the corresponding one of the plurality of edge forwarders and the default forwarder.

28. The CSI system of claim 27, wherein the memory further comprises operational instructions that cause the processing module to:

exchange the routing information between routing service instances inside the realm and outside the realm for maintaining routing control information or realm topology information, wherein the exchange is performed by transmitting chain updates to adjacent neighbors.

29. The CSI system of claim 28, wherein the memory further comprises operational instructions that cause the processing module to arrange the routing service instances into redundancy sets such that an active routing service instance is readily determinable by the CSI system for the realm by performing at least one of:

a routing service host/one of the plurality edge forwarders or the default forwarder to the configuration server interaction, routing service instance host to routing service instance host interaction, and the one of the plurality edge forwarders or the default forwarder to the routing service instance host interaction.

30. The CSI system of claim 29, wherein the memory further comprises operational instructions that cause the processing module to establish an initial one of the redundancy sets utilizing an ordered list of routing service instance hosts, wherein the routing service instance host uses the ordered list to determine which of the adjacent neighbors are active, and wherein the corresponding one of the plurality of edge forwarders and the default forwarder uses the ordered list to determine which of the routing service instances hosts to connect to.

31. The CSI system of claim 24, wherein the memory further comprises operational instructions that cause the processing module to update state information for each of the plurality of clients when any configuration changes occur, where the changes include addition, deletion, and/or failure of relevant corresponding one of the plurality of routing service control points.

32. The CSI system of claim 24, wherein the memory further comprises operational instructions that cause the processing module to establish connections between the plurality of edge forwarders based on configuration instructions or to establish a direct shortcut connection.