Automatic route determination method

• US 5,719,861 A
• Filed: 06/14/1996
• Issued: 02/17/1998
• Est. Priority Date: 06/15/1995
• Status: Expired due to Fees

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Okanoue, Yasuyo
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): Patel, Ajit
• Application Number:
  US08/663,805
• Time in Patent Office: 613 Days
• Field of Search: 370/351, 370/401, 370/402, 370/400, 370/408, 370/406, 370/218, 370/217
• US Class Current: 370/351
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04L 45/28 using route fault recovery

Abstract

In a network including a simple element having no routing function, each node includes a health-check function to keep track of the respective statuses of its managing simple elements. A source node broadcasts an address request signal (TARP) including the ID of a destination simple element and then waits for its response signal. Each node, receiving the address request signal, further broadcasts it when neither managing nor normally communicating with the destination simple element, and otherwise sends the response signal back to the source node. When the response signal is received from another node, the source node transmits a management message to the destination simple element via the node sending the response signal. Since it is checked that each node normally communicates with its managing simple elements by the health-check function, the node cannot send the response signal in the case where some failure exists between the node itself and the destination simple element.

Claims

1. In a network comprising a plurality of nodes each operating with a routing protocol and a plurality of network elements each connecting between adjacent nodes and having no routing protocol, wherein a network element is managed by adjacent nodes connected through the network element, a method for transferring a message from a first node to a destination network element, comprising the steps of:

a) broadcasting a request signal from the first node to the network, the request signal including source information indicating the first node and destination information indicating the destination network element;

b) sending a response signal from a second node back to the first node, the second node managing the destination network element and normally communicating with the destination network element; and

c) transferring the message from the first node to the destination network element via the second node.

2. The method according to claim 1, wherein the step (a) comprises the steps of:

at each node receiving the request signal,

checking whether the node itself manages the destination network element; and

broadcasting the request signal when the node itself does not manage the destination network element.

3. The method according to claim 1, wherein the step (a) comprises the steps of:

at each node receiving the request signal,

d) checking whether the node itself manages the destination network element;

e) checking whether the node itself normally communicates with the destination network element when the node itself manages the destination network element; and

f) broadcasting the request signal when the node itself does not normally communicates with the destination network element.

4. The method according to claim 3, wherein the step (e) comprises the steps of:

transmitting a check signal to a network element which is managed by the node itself at predetermined time intervals;

determining that the node itself normally communicates with the destination network element when receiving a response signal from the destination network element within a predetermined time period; and

determining that the node itself does not normally communicates with the destination network element when receiving no response signal from the destination network element within the predetermined time period.

5. The method according to claim 1, wherein the step (b) comprises the steps of:

at each node receiving the request signal,

g) checking whether the node itself manages the destination network element;

h) checking whether the node itself normally communicates with the destination network element when the node itself manages the destination network element; and

i) sending the response signal back to the first node when the node itself normally communicates with the destination network element.

6. The method according to claim 5, wherein the step (h) comprises the steps of:

transmitting a check signal to a network element which is managed by the node itself at predetermined time intervals;

determining that the node itself normally communicates with the destination network element when receiving a response signal from the destination network element within a predetermined time period; and

determining that the node itself does not normally communicates with the destination network element when receiving no response signal from the destination network element within the predetermined time period.

7. The method according to claim 1, wherein:

at the first node,

receiving a management message from outside, the management message including the destination information indicating the destination network element which is a target of the management message;

checking whether the first node itself manages the destination network element;

checking whether the first node itself normally communicates with the destination network element when the first node itself manages the destination network element;

producing the request signal when the first node itself does not manage the destination network element;

broadcasting the request signal to the network;

checking whether the response signal is received within a predetermined time period; and

transmitting the management message to the destination network element through a route via the second node when the response signal is received from the second node within a predetermined time period.

8. The method according to claim 1, wherein:

at the first node,

receiving a management message from outside, the management message including the destination address indicating the destination network element which is a target of the management message;

checking whether the first node itself manages the destination network element;

checking whether the first node itself normally communicates with the destination network element when the first node itself manages the destination network element;

producing the request signal when the node itself does not normally communicates with the destination network element;

broadcasting the request signal to the network;

checking whether the response signal is received within a predetermined time period; and

transmitting the management message to the destination network element through a route via the second node when the response signal is received from the second node within a predetermined time period.

9. The method according to claim 1, wherein:

at the second node,

receiving the address request signal

checking whether the second node itself manages the destination network element;

checking whether the second node itself normally communicates with the destination network element when the second node itself manages the destination network element; and

sending the response signal back to the first node when the second node itself normally communicates with the destination network element.

10. The method according to claim 8, wherein:

at the second node,

receiving the request signal

checking whether the second node itself manages the destination network element;

checking whether the second node itself normally communicates with the destination network element when the second node itself manages the destination network element; and

sending the response signal back to the first node when the second node itself normally communicates with the destination network element.

11. The method according to claim 7, wherein the route is a detouring route.

12. A network system comprising:

a plurality of nodes each operating with a routing protocol; and

a plurality of simple elements each connecting between adjacent nodes and having no routing protocol, each simple element being managed by adjacent nodes connected through the simple element,

wherein each node comprises;

a routing table;

a status table;

status checking means for checking whether the node itself normally communicates with a simple element which is managed by the node itself and storing a status of the simple element into the status table;

checking means for checking whether the node itself manages a given target simple element by referring to the routing table;

target resolution means for broadcasting an address request signal to the network when the node itself does not manage the target simple element or when the node itself does not normally communicates with the target simple element, the address request signal including source information indicating a source node and destination information indicating the target simple element, and for sending a response signal back to the source node when the node itself manages the target simple element and normally communicates with the target simple element; and

message transmission means for checking whether the response signal is received from a first node within a predetermined time period and transmitting a message from the source node to the target simple element via the first node by updating the routing table when the response signal is received from the first node within the predetermined time period.

13. The network system according to claim 12, wherein the status checking means comprises:

transmission control means for transmitting a check signal to the simple element which is managed by the node itself at predetermined time intervals; and

control means for determining that the node itself normally communicates with the simple element when receiving a response signal from the simple element within a predetermined time period and for determining that the node itself does not normally communicates with the simple element when receiving no response signal from the simple network element within the predetermined time period.

16. The network system according to claim 12, wherein the simple elements include a repeater.

17. The network system according to claim 12, wherein the simple elements include a bridge.

18. The network system according to claim 12, wherein the nodes include a router.

19. The network system according to claim 12, wherein the nodes include a gateway.

14. A network system comprising:

a plurality of nodes each operating with a routing protocol; and

a plurality of simple elements each connecting between adjacent nodes and having no routing protocol, each simple element being managed by adjacent nodes connected through the simple element,

wherein each node comprises;

a routing table;

a status table;

status checking means for checking whether the node itself normally communicates with a simple element which is managed by the node itself and storing a status of the simple element into the status table;

receiving means for receiving a management message from outside, the management message including destination information indicating a target simple element which is a target of the management message;

checking means for checking whether the node itself manages the target simple element by referring to the routing table;

first control means for broadcasting an request signal to the network when the node itself does not manage the target simple element or when the node itself does not normally communicates with the target simple element, the request signal including source information indicating a source node and destination information indicating the target simple element, and for sending a response signal back to the source node when the node itself manages the target simple element and normally communicates with the target simple element; and

second control means for checking whether the response signal is received from a first node within a predetermined time period, and transmitting the management message to the target simple element through a route via the first node by updating the routing table when the response signal is received from the first node within the predetermined time period.

15. The network system according to claim 14, wherein the status checking means comprises:

transmission control means for transmitting a check signal to the simple element which is managed by the node itself at predetermined time intervals; and

control means for determining that the node itself normally communicates with the simple element when receiving a response signal from the simple element within a predetermined time period and for determining that the node itself does not normally communicates with the simple element when receiving no response signal from the simple network element within the predetermined time period.

20. The network system according to claim 14, wherein the route is a detouring route.