Scalable cluster-type router device and configuring method thereof

• US 6,496,510 B1
• Filed: 11/13/1998
• Issued: 12/17/2002
• Est. Priority Date: 11/14/1997
• Status: Expired due to Term

• Current Assignee: Alaxala Networks Corporation (Fortinet Inc.)
• Original Assignee: Hitachi, Ltd.
• Inventors: Morimoto, Shigeki, Tsukakoshi, Masato
• Primary Examiner(s): Kizou, Hassan
• Assistant Examiner(s): LOGSDON, JOSEPH B
• Application Number:
  US09/190,437
• Time in Patent Office: 1,495 Days
• Field of Search: 370/238, 370/254, 370/351, 370/389, 370/400, 370/912, 370/401, 709/201, 709/223, 709/224, 709/238, 709/239, 709/241, 709/242, 709/243
• US Class Current: 370/401
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/021 Ensuring consistency of routing table updates, e.g. by using epoch numbers
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 45/586 of virtual routers

Abstract

A router device is provided with a plurality of router node devices interconnected via internal transmission lines, in which each of the plurality of router node devices comprises a unit for connecting to a plurality of networks; a routing table describing paths via which packets are forwarded; a forwarding unit for forwarding a packet between one network and another, and for forwarding the packet between the network connected to the router node device and the network connected to some other router node device of the router device via some other router node device, according to the routing table; a routing information collection unit for collecting routing information from each router device connected to the network, not via other router node devices, to the router node device to create a routing table in each router device, the routing information being information to be exchanged among router devices, a distribution unit for distributing the collected routing information to other router node devices via the internal transmission lines; and a routing table generation unit for generating the routing table based on the collected routing information and the routing information distributed from the other router node devices.

Claims

1. A router device comprising a plurality of router node devices connected to networks respectively, wherein said plurality of router node devices are interconnected via internal transmission lines that are different from said networks, and each of said plurality of router node devices within said router device has a same ID allocated in said networks, each of said plurality of router node devices comprising:

means for connecting to said networks;

a routing table describing paths via which packets are forwarded;

forwarding means for forwarding packets between one network and another network, both of which networks are connected to the router node device, and for forwarding packets between the network connected to the router node device and the network connected to some other router node device of the router device via said some other router node device, said packet forwarding being performed according to the routing table;

network information collection means for collecting network information by routing protocols from some other router device connected to the network, not via other router node devices, said network information being of a network to which said other router device is connected;

generating means for generating a network connection information database using the information of said network thus collected;

sending means for sending, via said transmission lines, said network connection information database to some other router node device that is provided with the same ID;

receiving means for receiving from said some other router node device having the same ID, via said internal transmission lines, said network connection information database generated by said some other router node device having the same ID;

integrating means for integrating said network connection information database generated by one router node device and different network connection information database received from some other router node device; and

routing table generation means for generating the routing table based on the network connection information database thus integrated.

2. A network system comprising the router device according to claim 1 and a plurality of networks connected to the router device.

3. A router device comprising a plurality of router node devices interconnected via internal transmission lines, wherein:

each router node device has a plurality of forwarding units, each connected to a network, and a path calculation unit,

each of said plurality of forwarding units comprising;

a routing table describing paths via which packets are forwarded; and

forwarding means for forwarding, according to the routing table, packets between the network connected to the forwarding unit and the network connected either to some other forwarding unit of the same router node device or to some other forwarding unit of some other router node device via the some other forwarding unit; and

said path calculation unit comprising;

network information collection means for collecting network information from the other router devices connected to the network connected to each forwarding unit of the router node device, said network information being information to be exchanged among the router devices in order to create the routing table in each router device;

information means for informing the other router node devices of the collected network information via said internal transmission lines;

integration means for integrating the collected network information with the network information sent from the other router node devices;

routing table generation means for generating the routing table based on the integrated network information; and

distribution means for distributing the generated routing table to the forwarding units of the router node device.

4. The router device according to claim 3, wherein

said path calculation unit has a link state data base (LSDB);

said network information collection means exchanges routing protocol packets with other router devices connected to each network connected to each forwarding unit of the router node device in order to collect network connection information on the other router devices for use as the network information on the other router devices and stores the collected network information into the link state database, said routing protocol packets conforming to OSPF (Open Shortest Path First) stipulated by RFC (Request for Comments) issued by the IAB (Internet Architecture Board);

said information means informs the other router node devices of link state database contents;

said integration means integrates the link state database contents sent from the other router node devices into said link state database; and

said routing table generation means also generates the routing table based on the integrated link state database.

5. A plurality of router node devices used to construct a router device wherein, said plurality of router node devices are interconnected via internal transmission lines that are different from said networks, and each of said plurality of router node devices within said router device has a same ID, which is allocated in said networks, each of said plurality of router node devices comprising:

means for connecting to said networks;

a routing table for describing paths via which packets are forwarded;

forwarding means for forwarding packets between one network and another network, both networks being connected to the router node device, and for forwarding packets between the network connected to the router node device and the network connected to some other router node device of the router device via said some other router node, said packet forwarding being performed according to the routing table;

network information collection means for collecting network information by routing protocols from some other router device connected to the network connected, not via other router node devices, said network information being of a network to which said other router device is connected

generating means for generating a network connection information database using the information of said network thus collected;

sending means for sending, via said internal transmission lines, said network connection information database to some other router node device that is provided with the same ID;

receiving means for receiving from said other router node device having the same ID, via said internal transmission lines, said network connection information database generated by said other router node device having the same ID;

integrating means for integrating said network connection information database generated by one router node device and different network connection information database received from some other router node device; and

routing table generation means for generating the routing table based on the network connection information database thus integrated.

6. A method for processing a routing protocol for generating a routing table, for use in a router device comprising a plurality of router node devices connected to networks and interconnected via internal transmission lines, comprises the steps of:

causing each of said router node devices to collect network information by routing protocols from other router devices connected to the network, not via other router nodes, to the router node device, said network information being of a network to which the other router devices are connected;

generating a network connection information database using the network information collected;

sending and receiving, via said internal transmission lines, said network connection information database to and from other router node devices that are provided with the same ID;

integrating said network connection information database generated by one router node device and network connection information database received from other router node devices; and

generating the routing table based on the network connection information database thus integrated.

7. A method for processing a routing protocol for generating a routing table, for use in a router device comprising a plurality of router node devices connected to networks and interconnected via internal transmission lines, said method comprising the steps of:

causing each of said plurality of router node devices to collect network information from other router devices connected to the network, not via other router nodes, to the router node in order to create the routing table in the router device, said network information being information to be exchanged among router devices;

distributing collected network information among said plurality of router nodes via said internal transmission lines; and

causing each of said plurality of router node devices to create the routing table based on the collected network information and the network information distributed by other router node devices.

8. A router device comprising a plurality of router nodes connected to respective networks, and interconnected via internal transmission lines different from said networks, each of said router nodes forming the router device comprising:

means for connecting to said networks;

a routing table for describing paths via which packets are forwarded;

forwarding means for forwarding packets, in accordance with the routing table, between one network and another network connected to the router node, and for forwarding packets, in accordance with the routing table, between the network connected to the router node and the network connected to another router node within the router device via said another router node;

network information collection means for collecting network information by routing protocols from another router device connected to the network, not via other router nodes, said network information being of a network to which said another router device is connected;

generating means for generating a network connection information database using the information of said network thus collected;

sending means for sending, via said internal transmission lines, without using said routing protocols, said network connection information database to other router nodes that are provided with the same ID;

receiving means for receiving from other router nodes having the same ID, via said internal transmission lines, without using said routing protocols, said network connection information database generated by said other router nodes having the same ID;

integrating means for integrating said network connection information database generated by one router node and network connection information database received from other router nodes; and

routing table generation means for generating the routing table based on the network connection information database thus integrated.

9. A router device according to claim 8, wherein:

each of said router nodes is provided with a forwarding unit; and

each of said router nodes has distribution means for distributing the routing table thus generated to the forwarding unit provided therein.

10. A router device according to claim 9, wherein:

said network information collection means exchanges routing protocol packets with other router devices connected to the network connected to the forwarding unit of the router node in order to collect network connection information on the other router devices for use as the network information on the other router devices and store the collected network information into said network connection information database, said routing protocol packets conforming to OSPF (Open Shortest Path First) stipulated by RFC (Request for Comments) issued by the IAB (Internet Architecture Board);

said sending means informs the other router nodes of updated contents of said network connection information database, when said network connection information database is updated;

said integration means updates the network connection information database using the updated contents of said network connection information database received from the other router nodes; and

said routing table generation means generates the routing table based on said network connection information database thus updated.

11. An arrangement, comprising:

a plurality of routers each having a unique ID; and

a cluster-type router connected to the routers, via different networks, including a plurality of router nodes interconnected to serve as a single router with a single unique ID and to perform routing functions using the same unique ID, each of said router nodes within the cluster-type router comprising;

a packet sender/receiver arranged to send and receive routing protocol packets which contains network connection information to/from the routers, via different networks;

a link state database arranged to store the network connection information;

a database integrator arranged to integrate any update network connection information from other router nodes within the cluster-type router in the link state database;

a routing table calculator arranged to calculate a minimum cost required to reach different networks using the link state database, and to store results in a routing table for subsequent distribution to all other router nodes within the cluster-type router for updates.

12. An arrangement according to claim 11, wherein each of the router nodes within the cluster-type router is further provided with a forwarding unit to forward data packets according to contents of the routing table, and a routing table distributor to distribute the results in the routing table to all other router nodes within the cluster-type router for updates, via the forwarding unit.

13. An arrangement according to claim 12, wherein the routing table calculator is further configured to read from the link state database, perform path calculations, update the routing table, and inform the routing table distributor that the routing table has been updated.

14. An arrangement according to claim 12, wherein the routing table distributor is further configured to receive the update on the routing table, and to inform the forwarding unit that the routing table has been updated.

15. An arrangement according to claim 12, wherein the packet sender/receiver, the database integrator, the routing table calculator and the routing table distributor are implemented as processes executed by a processor.

16. An arrangement according to claim 11, wherein all router nodes within the cluster-type router share the same unique ID, and a selected group of router nodes is connected to different routers, via a different network.

17. An arrangement according to claim 11, wherein contents of the link state database in each router node within the cluster-type router are identical, and include information pertaining to different router ID, networks, interface addresses and cost factors that are based on the bandwidth of the network and a user policy.

18. An arrangement according to claim 11, wherein the packet sender/receiver is further configured to update the link state database and inform the data integrator and the routing table calculator that the database has been updated.

19. An arrangement according to claim 11, wherein the database integrator is further configured to receive the update on the link state database from the packet sender/receiver and inform all other router nodes within the cluster-type router that the database has been updated.

20. An arrangement according to claim 11, wherein the database integrator is further configured to receive the update on the link state database from another router node within the cluster-type router, update the link state database accordingly, and to inform the routing table calculator that the database has been updated.