Distributed route server

• US 6,069,895 A
• Filed: 08/29/1997
• Issued: 05/30/2000
• Est. Priority Date: 08/29/1997
• Status: Expired due to Term

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Nortel Networks Corporation
• Inventors: Ayandeh, Siamack
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): VANDERPUYE, KENNETH N
• Application Number:
  US08/921,028
• Time in Patent Office: 1,005 Days
• Field of Search: 370/389, 370/392, 370/395, 370/396, 370/397, 370/400, 370/238, 370/254, 370/399
• US Class Current: 370/399
• CPC Class Codes: H04L 2012/562 Routing
• CPC Class Codes: H04L 2012/5621 Virtual private network [VPN]; Private-network - network-interface (P-NNI)
• CPC Class Codes: H04L 2012/5623 Network design, dimensioning, topology or optimisation
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/10 Routing in connection-oriented networks, e.g. X.25 or ATM
• CPC Class Codes: H04L 45/583 Stackable routers
• CPC Class Codes: H04L 49/30 Peripheral units, e.g. input or output ports
• CPC Class Codes: H04L 49/309 Header conversion, routing tables or routing tags
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

A design for a network route server in which network routing functions are distributed throughout the processing elements that constitute a switching node, while maintaining the global identity and routing information exchange functions of a route server element (RSE). Intelligent line-cards are provided having the ability to route independently of the RSE. This removes the RSE as a bottleneck resource and ensures that the capacity of the switching node is limited only by the switching capacity of its switch fabric. The RSE serves the functions of network topology discovery and routing table construction using a network topology database and an optimal routing algorithm. Copies of the dynamically maintained routing tables are distributed to the intelligent line-cards on a periodic basis governed by predetermined criteria. Wider geographical distribution of the RSE is enabled and most efficient utilization of the switch fabric is ensured. Scaling of distributed switching architectures is also enabled. The advantage is a significant increase in switching capacity as well as an increased degree of network connectivity.

Claims

1. A network route server with a scalable switching architecture, comprising:

a route server element with which a node identity in the network is associated, the route server element including processor means for creating a routing table for the route server using a topology database and a routing algorithm, the route server element periodically copying the routing table to each of a scalable array of packet processing elements associated with the route server element;

each packet processing element having a link-port interface to the network, memory means for storing a copy of the routing table, and processor means for using the copy of the routing table to route packets received by the packet processing element, each packet processing element being enabled to autonomously route packets received by the packet processing element by referencing the copy of the routing table; and

a switch fabric for the switching of packets between the packet processing elements in accordance with routing information provided by the packet processing elements, the scalable array of packet processing elements having an aggregate capacity that is scalable to a capacity of the switch fabric.

2. A network route server with a scalable switching architecture as claimed in claim 1 wherein the route server further includes a backplane bus or similar means of distribution over a wide area for providing control connectivity between the route server element and the packet processing elements.

3. A network route server with a scalable switching architecture as claimed in claim 1 wherein switching connectivity is provided for data packets through a cell or packet switch fabric.

4. A network route server with a scalable switching architecture as claimed in claim 1 wherein the route server element further controls connection oriented services and provides connection oriented call admission, and data related to virtual circuits associated with connection oriented services are downloaded to the packet processing elements from the route server element each time a connection oriented service request is set up or torn down.

5. A network route server with a scalable switching architecture as claimed in claim 4 wherein data updates to the packet processing elements for data related to virtual circuits associated with connection oriented services are downloaded with priority over all other server traffic.

6. A network route server with a scalable switching architecture as claimed in claim 5 wherein the copying of the routing table is accomplished with a lesser priority than the data updates to the packet processing elements for data related to virtual circuits.

7. A network route server as claimed in claim 1 wherein the route server element periodically copies the routing table to each of the packet processing elements in a multi-cast mode.

8. A network route server with a scalable switching architecture as claimed in claim 1 wherein each packet processing element performs functions which include:

header translation and checksum processing;

packet lifetime processing;

packet routing; and

, advising adjacent nodes of a congested condition if packets have accumulated in the input or output buffers of the packet processing element.

9. A network route server with a scalable switching architecture, comprising:

a route server element with which a node identity in the network is associated, the route server element including processor means for executing a topology discovery protocol and maintaining a topology database of the network, and for creating a routing table for the route server using the topology database and a routing algorithm, the route server element periodically copying the routing table to each of a scalable array of packet processing elements associated with the route server element;

each packet processing element having a link-port interface to the network, memory means for storing a copy of the routing table, and processor means for using the copy of the routing table to route packets received by the packet processing element, each packet processing element being enabled to autonomously route packets received by the packet processing element by referencing the copy of the routing table; and

a switch fabric for the switching of packets between the packet processing elements in accordance with routing information provided by the packet processing elements, the scalable array of packet processing elements having an aggregate capacity that is scalable to a capacity of the switch fabric.

10. A network route server with a scalable switching architecture as claimed in claim 9 wherein the control connectivity comprises a backplane bus, or is overlaid on the switch fabric for distributed implementations.

11. A network route server with a scalable switching architecture as claimed in claim 10 wherein the route server is geographically distributed and the control connectivity is provided by data packets communicated through the switch fabric.

12. A network route server with a scalable switching architecture as claimed in claim 10 wherein the control connectivity is provisioned 30% over anticipated peak load traffic to keep the routing table update interval low.

13. A route server with scalable switching architecture as claimed in claim 10 wherein a frequency at which the route server element periodically copies the routing table to each of the packet processing elements is greater than the time required by the route server element to calculate a new routing table and less than or equal to a maximum interval represented by the average time required to process N link state packets where N represents the number of links in a network area occupied by the route server.

14. A route server with scalable switching architecture as claimed in claim 13 wherein the routing table is copied to each of the packet processing elements whenever network topology changes or significant fluctuations in traffic that affect routing occur, regardless of whether the maximum interval has expired since a last copy process.

15. A route server with a scalable switching architecture as claimed in claim 10 wherein packets are switched in a dual level priority scheme wherein routing control packets or control cells are switched with a higher priority than payload traffic, and VCI table updates are communicated at a higher priority than routing table updates.

16. A network route server with a scalable switching architecture, comprising:

a route server element with which a node identity in the network is associated, the route server element including processor means for executing a topology discovery protocol and maintaining a topology database of the network, and for creating a routing table for the route server using the topology database and a routing algorithm, the route server element periodically copying the routing table to each of an array of packet processing elements associated with the route server element, and a call admission control module which is responsible for the admission of connection oriented services through the server, the call admission control module receiving virtual circuit connection requests and downloading to a packet processing element, which is to establish the virtual circuit, data related to the virtual circuit;

each packet processing element having a link-port interface to the network, memory means for storing a copy of the routing table, and processor means for using the copy of the routing table to route packets received by the processing element, each packet processing element is enabled to autonomously route packets received by the packet processing element by referencing the copy of the routing table, and to route connection oriented packets in accordance with the data downloaded from the route server element when a virtual circuit is set up;

control connectivity for exchanging control data between the route server element and the packet processing element; and

a switch fabric for the switching of packets between the packet processing elements in accordance with routing information provided by the packet processing elements, the packet processing elements having an aggregate capacity that is scalable to a capacity of the switch fabric.

17. A method of routing packets or cells in a network using a route server having a route server element, a plurality of packet processing elements with link-port interfaces, a processor and a memory to permit the packet processing elements to perform routing functions to the network and a switch fabric, comprising:

a) periodically creating at the route server element a routing table using a topology database and a routing algorithm;

b) periodically copying the routing table to a memory in each of the packet processing elements;

c) using the copy of the routing table at each packet processing element to route packets received at the link-port interface of the packet processing element; and

d) switching packets between the packet processing elements in accordance with routing information provided by the packet processing elements using the copy of the routing table and the routing functions.

18. The method of routing packets or cells in a network as claimed in claim 17 further including the steps of:

a) controlling at the route server element connection-oriented services and connection-oriented call admission and downloading to the route server elements data related to virtual circuits associated with connection-oriented services each time a connection-oriented service request is set up or torn down.

19. The method of routing packets or cells in a network as claimed in claim 17, further including the steps of:

a) executing at the route server element a topology discovery protocol and maintaining the topology database in response to outputs from the topology discovery protocol.