Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1998-11-13
2002-12-17
Kizou, Hassan (Department: 2662)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S351000, C370S400000, C709S238000, C709S242000, C709S243000
Reexamination Certificate
active
06496510
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to technology for routing packets over a network, and more particularly to technology for a router device, composed of a plurality of interconnected router node devices and externally behaving as a single router, to send and receive routing information to or from other routers.
2. Description of Related Art
A router which transfers packets from a terminal on a network to a terminal on another network exchanges routing information with another router to perform dynamic routing and, based on this routing information, generates a table, called a routing table, which contains a set of entries that each specify a packet destination address and the next-hop used to reach that destination.
Two protocols are known for exchanging routing information and for generating a routing table based on the information: one is a Distance Vector Algorithm (DVA) based protocol, such as Routing Information Protocol (RIP) stipulated by Request for Comments (RFC) 1058 prepared by the Internet Engineering Task Force (IETF) and issued from the Internet Architecture Board (IAB), and the other is a Link-State Algorithm (LSA) based protocol such as Open Shortest Path First (OSPF) stipulated by RFC 1247.
A RIP-based router exchanges routing table entries with another router and determines a routing path according to the number of hops (the number of routers to the destination), while an OSPF-based router exchanges network connection state information (addresses and so on) and determines a path based on a cost determined by considering many factors including the number of hops. It should be noted that, in exchanging routing information among routers, a particular packet called a routing protocol packet is used.
To increase performance, a router has been proposed which has its function divided into two (using two processors): a packet forwarding function and a routing table generation function. This configuration prevents the packet forwarding function from being affected by the load on the routing table generation function. This technology is described in “Packet Magazine Third Quarter 1995” published by Cisco.
SUMMARY OF THE INVENTION
The present inventors have been studying so as to accomplish a router device capable of processing at higher speed using a router configured of two portions, one is a part for forwarding packets and the other is a part for executing a protocol for generating a routing table as described above. As an example, they have proposed that a plurality of routers configured as described above are used as router nodes interconnected via a plurality of high-speed transmission lines to have a single router. Such a configuration have been described in the Japanese Patent Application (Hei 10-185921).
As a method for generating routing tables on such a router composed of a plurality of router nodes using the table generation method designed for use on a conventional router not composed of a plurality of router nodes, the present inventors have proposed that one of the following two methods is used.
In the first method, each router node acts as if it was a conventional router not composed of a plurality of nodes. In this case, each router node exchanges routing protocol packets with other routers and other router nodes connected to that router node to create its own routing table.
In the second method, one of the plurality of router node units stores therein the routing information on all other router nodes and only this router node exchanges routing protocol packets with all other routers connected to the router device composed of the plurality of router nodes. Collected routing information is then distributed to all other router nodes.
However, in the first method, one router node must be equivalent to one router when sending or receiving routing protocol packets and generating the routing table. Therefore, a router composed of a plurality of router nodes must be equivalent, at least, to one network or one sub-net composed of a plurality of routers. This means that a host address must be assigned to each router node and that one network address or sub-net address must be assigned to the router composed of the plurality of router nodes. Thus, this method results in inefficient address usage.
In the second method, the router node which processes routing protocol packets for the plurality of nodes is too busy to generate or update routing table entries within an allowable time, sometimes discarding packets or causing a traffic problem.
It is an object of the present invention to provide a router device composed of a plurality of router nodes to perform routing protocol processing without using extra addresses and without exerting a heavy load on a particular router node.
To achieve the above object, the present invention provides, for example, a method for use in a router device which connects to a plurality of networks and in which a plurality of router node devices, each forwarding packets according to a routing table describing paths via which the packets are forwarded, are interconnected by internal transmission lines. The method, provided for processing a routing protocol for generating the routing table, wherein a process in said routing protocol processing, for collecting routing information requested for generating the routing table from the other router device, comprises the steps of causing each of the router node devices to collect routing information from router devices connected to the network connected, not via other router nodes, to the router node device; and collecting and integrating the routing information collected by each router node device via the internal transmission lines.
In this processing method, because each router node performs a part of the processing performed by one router device, a router device composed of a plurality of router nodes may be treated as a single router device from the viewpoint of address usage. Thus, there is no need to assign network addresses or sub-net addresses to a router device composed of a plurality of router nodes. In addition, the plurality of router nodes collect routing information from other router devices connected to the router device, preventing the processing load from being concentrated on a particular router node.
REFERENCES:
patent: 5018133 (1991-05-01), Tsukakoshi et al.
patent: 5473599 (1995-12-01), Li et al.
patent: 5892912 (1999-04-01), Suzuki et al.
patent: 6047330 (2000-04-01), Stracke, Jr.
patent: 6049524 (2000-04-01), Fukushima et al.
patent: 6085238 (2000-07-01), Yuasa et al.
patent: 6192051 (2001-02-01), Lipman et al.
J. Ge and H. Qian. Cluster-Based Virtual Router. 2002 IEEE. pp. 102-109.*
J. Cao and F. Zhang. Optimal Configuration in Hierarchical Network Routing. 1999 IEEE. pp. 249-254.*
“New Cisco 7500 Delivers More Routing Muscle”, Packet Magazine Archives, Third Quarter 1995, Cisco Systems Inc.
“Configuring High System Availability Operation” Route Switch Processor (RSP2) Installation and Configuratioin Cisco Connection Documentation, Enterprise Series vol. 3, No. 5@1996.
Morimoto Shigeki
Tsukakoshi Masato
Antonelli Terry Stout & Kraus LLP
Hitachi , Ltd.
Kizou Hassan
Logsdon Joe
LandOfFree
Scalable cluster-type router device and configuring method... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Scalable cluster-type router device and configuring method..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scalable cluster-type router device and configuring method... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2981254