US5218601A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for searching for alternate path in communication network
Assignee: Fujitsu Ltd
•
Filing: 1990-12-20
•
Granted: 1993-06-08
•
Expires: 2010-12-20
Abstract
Abstract A method includes the steps of a failure which occurs in a node or link, and b) identifying at most N (N is an integer equal to or greater than 2) nodes contained in each path affected by the occurrence of the failure. Each path is connected to a sender node which detects the failure, information is transferred to the sender node via the N nodes, and the sender node serves as a start point of each alternate path which is to be established. The method also includes the step of c) broadcasting a restoration message to links which outgo from the sender node, where the restoration message has an identifier of the sender node and identifiers of the N nodes specified for each path affected by the occurrence of the failure. The identifiers of the N nodes specified for each path being candidate nodes of an end point of each alternate path. The method als includes a step of d) determining whether or not a node being considered is one of the candidate nodes, where the node which is one of the candidate nodes is a destination node. Further, the method includes the steps of e) passing the restoration message through a repeater node which is a node other than the candidate nodes, and f) determining a route via which the restoration message has been transferred to the destination node to be an alternate path connected between the sender node and the destination node.
Inventors
- 👤 Takafumi Chujo
- 👤 Hiroaki Komine
- 👤 Keiji Miyazaki
- 👤 Takao Ogura
- 👤 Tetsuo Soejima
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 08:06
CPC Classifications
H; H04; H04Q; H04Q3/00; H04Q3/64; H04Q3/66; H04Q3/665; H04L; H04L1/00; H04L1/24; H04L45/00; H04L45/02; H04L45/24; H04L45/247; H04L45/28; H04Q3/0016; H04Q3/0062; H04Q3/0075; H04Q3/0079
Claims Analysis
Total Claims: 25
Claim 1
Independent Claim
277 words
A method for searching for an alternate path in a communication network which has a plurality of nodes and a plurality of links which mutually connect adjacent nodes, information being transferred via a path which goes through the nodes, said method comprising the steps of: a) detecting a failure which occurs in the communication network; b) identifying at most N nodes contained in each path affected by the occurrence of said failure and coupled to a sender node which detects said failure, each said path being connected to said sender node which detects said failure, said sender node serving as a start point of each alternate path which is to be established, where N is an integer equal to or greater than 2; c) broadcasting a restoration message to links which extend from said sender node, said restoration message having an identifier of said sender node and identifiers of said N nodes specified for each said path affected by the occurrence of said failure, the identifiers of said N nodes specified for each said path being candidate nodes of an end point of each said alternate path; d) determining whether or not a node which has received said restoration message is one of said candidate nodes, the node which is one of said candidate nodes and which has received said restoration message being a destination node; e) passing said restoration message through a relay node which is one of the nodes other than said candidate nodes; and f) determining a route via which said restoration message has been transferred to said destination node to be an alternate path connected between said sender node and said destination node.
Claim 2
Independent Claim
277 words
A method for searching for an alternate path in a communication network which has a plurality of nodes and a plurality of links which mutually connect adjacent nodes, information being transferred via a path which goes through the nodes, said method comprising the steps of: a) detecting a failure which occurs in the communication network; b) identifying at most N nodes contained in each path affected by the occurrence of said failure and coupled to a sender node which detects said failure, each said path being connected to said sender node which detects said failure, said sender node serving as a start point of each alternate path which is to be established, where N is an integer equal to or greater than 2; c) broadcasting a restoration message to links which extend from said sender node, said restoration message having an identifier of said sender node and identifiers of said N nodes specified for each said path affected by the occurrence of said failure, the identifiers of said N nodes specified for each said path being candidate nodes of an end point of each said alternate path; d) determining whether or not a node which has received said restoration message is one of said candidate nodes, the node which is one of said candidate nodes and which has received said restoration message being a destination node; e) passing said restoration message through a relay node which is one of the nodes other than said candidate nodes; and f) determining a route via which said restoration message has been transferred to said destination node to be an alternate path connected between said sender node and said destination node.
Claim 3
Dependent Claim
79 words
A method as claimed in claim 1, further comprising the steps of: generating, at each node, a path tracer which stores the identifiers of at most said N nodes; replacing the identifier of an oldest one of the nodes contained in said path tracer by its own identifier; and sending out said path tracer including its own said identifier to a next node located on a downstream side correspondign to a direction in which said path tracer is transferred.
Claim 4
Dependent Claim
73 words
A method as claimed in claim 2, further comprising the steps of: receiving, for each said path, said path tracer from a neighboring node located on an apparatus side in said direction; and storing the identifiers of at most said N nodes included in said path tracer, wherein said N nodes contained in each said path affected by the occurrence of said failure are identified from the identifiers stored by said storing step.
Claim 5
Dependent Claim
62 words
A method as claimed in claim 1, further comprising the step of bundling paths respectively having an identical sequence of identifiers of the nodes os that a plurality of groups respectively having bundled paths are obtained, wherein said step (c) includes sending the restoration message having, as the candidate nodes, the identifiers of the N nodes included in each of the groups.
Claim 6
Dependent Claim
67 words
A method as claimed in claim 1, further comprising the steps of: bundling paths respectively having an identical sequence of identifiers of the nodes so that a plurality of groups respectively having bundled paths are obtained; and selecting nodes included in at least one of the groups, wherein said step (c) includes sending the restoration message having, as the candidate nodes, the identifiers of the node selected.
Claim 7
Dependent Claim
61 words
A method as claimed in claim 1, further comprising the steps of: sending back an acknowledgement message to said sender node from the destination node; and receiving, at said sender node, said acknowledgement message from the destination node, wherein said step (f) comprises the step of determining the route on the basis of said acknowledgement message received from the destination node.
Claim 8
Dependent Claim
36 words
A method as claimed in claim 1, wherein said step (f) comprises the step of switching, at each node between said sender node and the destination node, its matrix switch, so that said route is formed.
Claim 9
Dependent Claim
25 words
A method as claimed in claim 1, wherein said restoration message comprises information concerning the number of paths affected by the occurrence of said failure.
Claim 10
Dependent Claim
23 words
A method as claimed in claim 1, wherein said restoration message comprises information identifying each path affected by the occurrence of said failure.
Claim 11
Dependent Claim
33 words
A method as claimed in claim 1, further comprising the step of writing the identifier of said relay node into the restoration message when the restoration message is sent from the relay node.
Claim 12
Dependent Claim
42 words
A method as claimed in claim 1, further comprising the steps of: deleting, at the destination node, one of the identifiers indicating said destination node from the restoration message; and broadcasting the restoration message with said one of the identifiers deleted therefrom.
Claim 13
Dependent Claim
33 words
A method as claimed in claim 1, further comprising the step of inserting at the sender node, a port identifier indicating a link which extends from the sender node, into the restoration message.
Claim 14
Dependent Claim
55 words
A method as claimed in claim 1, further comprising the step of bundling paths respectively having an identical sequence of identifiers of the nodes so that a plurality of groups respectively having bundled paths are obtained, wherein the restoration message comprises information about the identifier of one destination node defined for each of the groups.
Claim 15
Dependent Claim
61 words
A method as claimed in claim 5, further comprising the steps of: sending back an acknowledgement message to said sender node from the destination node; and receiving, at said sender node, said acknowledgement message from the destination node, wherein said step (f) comprises the step of determining the route on the basis of said acknowledgement message received from the destination node.
Claim 16
Dependent Claim
42 words
a method as claimed in claim 14, further comprisign the steps of: deleting, at the destination node, one of the identifiers indicating said destination node, from the restoration message; and broadcasting the restoration message with said one of the identifiers deleted therefrom.
Claim 17
Dependent Claim
33 words
A method as claimed in claim 15, further comprising the step of inserting, at the sender node, a port identifier indicating a link which extends from the sender node, into the restoration message.
Claim 18
Dependent Claim
33 words
A method as claimed in claim 14, further comprising the step of inserting, at the sender node, a port identifier indicating a link which extends from the sender node, into the restoration message.
Claim 19
Dependent Claim
41 words
A method as claimed in claim 14, wherein said step (f) comprises the step of determining, for each of the grups, an alternate path corresponding to a route related to said acknowledgement message which is first received by said sender node.
Claim 20
Dependent Claim
65 words
A method as claimed in claim 14, wherein said step of sending back the acknowledgement message comprises the step of sending back the acknowledgement message to said sender node from the destination node in response to the restoration message which is first received, the acknowledgement message not being sent back in response to restoration messages which are received after said restoration message is first received.
Claim 21
Dependent Claim
128 words
A method as claimed in claim 17, further comprising the steps of: storing said port identifier of said restoration message which is first received into said destination node; judging, at said destination node, whether or not the port identifier contained in the restoration message which is the second one received coincides with that stored in said destination node; neglecting the restoration message when it is judged that the port identifier contained in the restoration message which is the second one received coincides with that stored in said destination node; and sending ack the acknowledgement message to the sender node when it is judged that the port identifier contained in the restoration message which is the second one received does not coincide with that stored in the destination node.
Claim 22
Dependent Claim
60 words
A method as claimed in claim 20, further comprising the step of sending back no acknowledgement message to the sender node when it is judged that the port identifier cotnained in the restoration message which is the second one received, does not coincide with that stored in the destination node and when there is no path required to be restored.
Claim 23
Dependent Claim
127 words
A method as claimed in claim 12, further comprising the steps of: storing said port identifier of said restoration message which is first received into said destination node; judging, at said destination node, whether or not the port identifier contained in the restoration message which is the second one received coincides with that stored in said destination node; neglecting the restoration message when it is judged that the port identifier contained in the restoration message which is the second one received coincides with that stored in said destination node; and sending ack the acknowledgement message to the sender when it is judged that the port identifier contained in the restoration message which is the second one received does not coincide with that stored in the destination node.
Claim 24
Dependent Claim
60 words
A method as claimed in claim 22, further comprising the step of sending back no acknowledgement message to the sender node when it is judged that the port identifier contained in the restoration message which is the second one received doesn not coincide with that stored in the desitnation node and when there is no path required to be restored.
Claim 25
Dependent Claim
301 words
A method as claimed in claim 1, further comprising the steps of: bundling paths respectively having an identical sequence of identifiers of the nodes so that a plurality of groups respectively having bundled paths are obtained; and selecting nodes included in at least one of the groups, wherein said step (c) includes sending the restoration message having, as the candidate nodes, the identifiers of the node selected, said restoration message comprising information concerning the number of paths affected by the occurrence of said failure, information concerning an identifier of each path affected by the occurrence of said failure, and a port identifier indicating a link which extends from the sender node; deleting, at the destination node, one of the identifiers indicating said destination node from the restoration message; storing said port identifier of said restoration message which is first received into said destination node; judging, at said destination node, whether or not the port identifier contained in the restoration message which is the second one received coincides with that stored in said destination node; neglecting the restoration message when it is judged that the port identifier contained in the restoration message which is the second one received coincides with that stored in said destination node; sending back the acknowledgement message to the sender node when it is jduged that the port identifier contained in the restoration message which is the second one received does not coincide with that stored in the destination node; and receiving, at said sender node, said acknowledgement message from the destination node, wherein: said step (f) comprises the steps of determining the route on the basis of said acknowledgement message received from the destination node, and switching, at each node between said sender node and the destination node, its matrix switch so that said route is formed.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1996-06-07 | 1996-12-07 | 1997-06-08 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2000-06-07 | 2000-12-07 | 2001-06-08 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2004-06-07 | 2004-12-07 | 2005-06-08 | $7700.00 | Window Closed / Lapsed |