Detour path determination method

• US 6,084,882 A
• Filed: 03/20/1995
• Issued: 07/04/2000
• Est. Priority Date: 06/18/1991
• Status: Expired due to Fees

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Amemiya, Shigeo, Tezuka, Koji, Ogura, Takao, Chujo, Takafumi
• Primary Examiner(s): VU, HUY DUY
• Application Number:
  US08/406,783
• Time in Patent Office: 1,933 Days
• Field of Search: 370/13, 370/16, 370/16.1, 370/60, 370/60.1, 370/94.1, 370/94.2, 370/58.1, 370/58.2, 370/58.3, 370/241, 370/242, 370/243, 370/244, 370/245, 370/246, 370/247, 370/248 , 370/249, 370/250, 370/252, 370/237, 370/351, 370/389, 370/392, 370/400, 370/401, 370/402, 370/408, 370/409, 370/410, 370/428, 371/8.1, 371/8.2, 371/11.1, 371/11.2, 340/825.03, 340/827, 340/825.01
• US Class Current: 370/409
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/10 Routing in connection-oriented networks, e.g. X.25 or ATM
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/28 using route fault recovery

Abstract

A detour path determination method wherein each node on a determined detour path stores in advance first and second nodes upstream of each node as well as an identifier(s) of a packet directional path(s); a number of an identifier(s) of a packet directional path(s) required for switching in each link extending from a downstream node one node downstream of each node on the detour path are set for respective nodes on the detour path beginning from the terminal node upstream; the identifier(s) of the packet directional path(s) set as above, and an identifier(s) of a corresponding packet directional path(s) at a start node of the detour path, are sent to a node one node upstream of the above each node; the start node updates a identification data table at the node, by an identifier(s) of a packet directional path(s) set downstream of the start node based on the corresponding identifier(s) of packet directional path(s) at a start node of the detour path, when the start node receives the above identifier(s) (FIG. 1).

Claims

1. A method for determining, in a packet communication network, at least one first identifier identifying at least one first packet directional path, which is to be logically defined in each of a plurality of links in a bypassing path, where said bypassing path bypasses a faulty signal path extending from a first node through a second node to a third node, said bypassing path extends from said first node through at least one midway node to said third node, and said at least one first packet directional path is to be determined corresponding to at least one second packet directional path which is logically defined in each of a plurality of links in the faulty signal path;

the packet communication network contains a plurality of nodes, and each of the plurality of nodes contains unused identifier storing means for storing, in said each of the plurality of nodes, information on at least one unused identifier each being available for use in identifying a packet directional path in each link incoming to the said each of the plurality of nodes; and

said third node contains original identifier storing means for storing, in said third node, at least one second identifier identifying said at least one second packet directional path in the link between the first node and the second node;

said method comprising the steps of;

(a) determining, in said third node, as said at least one first identifier identifying said at least one first packet directional path in the link between the third node and a first one of the at least one midway node located one node upstream of the third node on the bypassing path, at least one unused identifier among the at least one unused identifier stored in the third node by the unused identifier storing means, so that each of the at least one second identifier corresponds to one of the at least one first identifier determined in the link between the third node and the first one of the at least one midway node on the bypassing path;

(b) transferring, from the third node to the first one of the at least one midway node, said at least one second identifier and the at least one first identifier determined in the link between the third node and the first one of the at least one midway node, so that the correspondence between each of the at least one first identifier and one of the at least one second identifier, is recognizable;

(c) receiving, at each of the at least one midway node on the bypassing path, from one of the third node and a second one of the at least one midway node which is located one node downstream of said each midway node, said at least one second identifier and said at least one first identifier determined in the link between said each midway node and said one of the third node and the second one of the at least one midway node, and recognizing the correspondence between each of the at least one second identifier and one of the at least one first identifier determined in the link between said each midway node and said one of the third node and the second one of the at least one midway node;

(d) determining, after step (c), in said each midway node, as said at least one first identifier identifying said at least one first packet directional path in a link between said each midway node and one of the first node and a third one of the at least one midway node which is located one node upstream of said each midway node on the bypassing path, at least one unused identifier among the at least one unused identifier stored in said each midway node by the unused identifier storing means, so that each of the at least one first identifier determined in the link between said each midway node and said one of the first node and the third one of the at least one midway node on the bypassing path;

(e) transferring, from said each midway node to said one of the first node and the third one of the at least one midway node, said at least one second identifier and said at least one first identifier determined in the link between said each midway node and said one of the first node and the third one of the at least one midway node, so that the correspondence between each of the at least one second identifier and one of the at least one first identifier determined in the link between said each midway node and said one of the first node and the third one of the at least one midway node, is recognizable; and

(f) receiving, at the first node, from a fourth one of the at least one midway node located one node downstream of the first node one the bypassing path, said at least one second identifier and the at least one first identifier determined in the link between the first node and said the fourth one of the at least one midway node, and recognizing the correspondence between each of the at least one second identifier and one of the at least one first identifier determined in the link between the first node and said the fourth one of the at least one midway node.

2. A method according to claim 1, wherein at least one of said steps (b) and (e) include a bit map conversion sub-step for converting, before transferring said at least one second identifier, said at least one second identifier into bit map data each bit of which corresponds to a possible value of one of the at least one second identifier, and each bit corresponding to the value of one of the at least one second identifier is valid.

3. A method according to claim 1, wherein at least one of said steps (b) and (e) include, before transferring said at least one first identifier and the at least one second identifier,

a leading identification data detection sub-step for detecting a leading value of said at least one second identifier;

a final identification data detection sub-step for detecting a final value of said at least one second identifier; and

a bit map conversion sub-step for converting, before transferring said at least one second identifier, the at least one second identifier into bit map data, where the it map data begins with a bit corresponding to the leading value of the at least one second identifier, and ends with a bit corresponding to the final value of the at least one second identifier, each bit of the bit map data corresponds to a possible value, between the leading and final values, of the at least one second identifier, and each bit corresponding to the value of one of the at least one second identifier is valid.

4. A method according to claim 1, wherein at least one of said steps (b) and (e), the leading value of the at least one first identifier determined in the link between the third node and the first one of the at least one midway node, and the number of the at least one first identifier determined in the link between the third node and the first one of the at least one midway node, are transferred instead of the at least one first identifier.

5. A system for determining, in a packet communication network, at least one first identifier identifying at least one first packet directional path, which is to be logically defined in each of a plurality of links in a bypassing path, where said bypassing path bypasses a faulty signal path extending from a first node through a second node to a third node, said bypassing path extends from said first node through at least one midway node to said third node, and said at least one first packet directional path is to be determined corresponding to at least one second packet directional path which is logically defined in each of a plurality of links in the faulty signal path;

the packet communication network contains a plurality of nodes, and each of the plurality of nodes comprises unused identifier storing means for storing information on at least one unused identifier each being available for use in identifying a packet directional path in each link incoming to the said each of the plurality of nodes; and

said third node comprises;

original identifier storing means for storing at least one second identifier identifying said at least one second packet directional path in the link between the first node and the second node;

first determining means for determining, as said at least one first identifier identifying said at least one first packet directional path in the link between the third node and a first one of said at least one midway node located one node upstream of the third node on the bypassing path, at least one unused identifier among the at least one unused identifier stored in the third node by the unused identifier storing means, so that each of the at least one first identifier determined in the link between the third node and said first one of said at least one midway node on the bypassing path; and

first transferring means for transferring, to the first one of said at least one midway node, said at least one second identifier and the at least one first identifier determined in the link between the third node and the first one of said at least one midway node, so that the correspondence between each of the at least one first identifier and one of the at least one second identifier, is recognizable,

each of said at least one midway node on the bypassing path comprises;

first receiving means for receiving from one of the third node and second one of the at least one midway node, said at least one second identifier and said at least one first identifier determined in the link between said each midway node and said one of the third node and the second one of the at least one midway node, and recognizing the correspondence between each of the at least one second identifier and one of the at least one first identifier determined in the link between said each midway node and said one of the third node and the second one of the at least one midway node;

second determining means for determining as said at least one first identifier identifying said at least one first packet directional path in a link between said each midway node and one of the first node and a third one of the at least one midway node which is located one node upstream of said each midway node on the bypassing path, at least one unused identifier among the at least one unused identifier stored in said each midway node by the unused identifier storing means; and

second transferring means for transferring, from said each midway node to said one of the first node and the third one of the at least one midway node, said at least one second identifier and said at least one first identifier determined in the link between said each midway node and said one of the first node and the third one of the at least one midway node, so that the correspondence between each of the at least one second identifier and one of the at least one first identifier determined in the link between said each midway node and said one of the first node and the third one of the at least one midway node, is recognizable,

said first node comprises;

second receiving means for receiving from a fourth one of the at least one midway node located one node downstream of the first node on the bypassing path, said at least one second identifier and the at least one first identifier determined in the link between the first node and said the fourth one of the at least one midway node, and recognizing the correspondence between each of the at least one second identifier and one of the at least one first identifier determined in the link between the first node and said the fourth one of the at least one midway node.

6. A system according to claim 5, wherein said first transferring means includes a bit map conversion means for converting, before transferring said at least one second identifier, said at least one second identifier into bit map data each bit of which corresponds to a value of the at least one second identifier, and each bit corresponding to the value of one of the at least one second identifier is valid.

7. A system according to claim 5, wherein at least one of said first and second transferring means comprises:

a leading identification data detection means for detecting, before transferring said at least one second identifier, a leading value of said at least one second identifier;

a final identification data detection means for detecting, before transferring said at least one second identifier, a final value of said at least one second identifier; and

a bit map conversion means for converting, before transferring said at least one second identifier, the at least one second identifier into bit map data, where the bit map data begins with a bit corresponding to the final value of the at least one second identifier, each bit of the bit map data corresponds to a possible value, between the leading and final values, of the at least one second identifier, and each bit corresponding to the value of one of the at least one second identifier is valid.

8. A system according to claim 5, wherein in the operation of at least one of said first and second transferring means, the leading value of the at least one first identifier determined in the link between the third node and the first one of said at least one midway node, and the number of the at least one first identifier determined in the link between the third node and the first one of said at least one midway node, are transferred instead of the at least one first identifier.

9. A system according to claim 5, wherein said second node contains means for transferring, to said third node, said at least one second identifier;

and said third node contains means for receiving the at least one second identifier from the second node, to store the at least one second identifier in said original identifier storing means.

10. A node apparatus usable in each of a plurality of nodes in a packet communication network, said node apparatus comprising:

unused identifier storing means for storing information on at least one unused identifier each being available for use in identifying a packet directional path in each link incoming to the said each node;

original identifier storing means for storing, as at least one original identifier, at least one first identifier identifying at least one first packet directional path directed to said each node, in a link between a first node which is located one node upstream of said each node on a working path and a second node which is located two nodes upstream of said each node on said working path, where said working path extends from said second node to said each node, and said at least one first packet directional path is logically defined on the working path;

determining means for determining, as at least one second identifier identifying at least one second packet directional path in a link between said each node and one of at least one midway node located one node upstream of said each node on a bypassing path, at least one unused identifier among the at least one unused identifier stored in the unused identifier storing means in said each node, where said bypassing path extends from said second node through said at least one midway node to said each node to bypass said working path, and each of said at least one second directional path is determined so as to correspond to one of the at least one first identifier; and

transferring means for transferring to said one of at least one midway node, said at least one first identifier and the at least one second identifier determined by the determining means in the link between said each node and said one of at least one midway node, so that the correspondence between each of the at least one first identifier and one of the at least one second identifier determined in the link between said each node and said one of at least one midway node, is recognizable.

11. A node apparatus usable in each of at least one midway node which a bypassing path in a packet communication network passes through, where said bypassing path bypasses a working path extending from a first node through a second node to a third node, and at least one first identifier is determined for identifying at least one first packet directional path logically defined in a link between the first and second node on the working path, said node apparatus comprising:

unused identifier storing means for storing information on at least one unused identifier each being available for use in identifying a packet directional path in each link incoming to the said each node;

receiving means for receiving, from a downstream-side one of at least one midway node located one node downstream of said each node on the bypassing path, said at least one first identifier and at least one second identifier, and recognizing the correspondence between each of said at least one first identifier and one of said at least one second identifier, where said at least one second identifier identifies at least one second packet directional path in a link between said each node and the downstream-side one of at least one midway node on the bypassing path;

determining means for determining as at least one third identifier identifying said at least one first packet directional path in a link between said each node and an upstream-side one of at least one midway node located one node upstream of said each node on said bypassing path, at least one unused identifier among the at least one available identifier stored by the unused identifier storing means in said each node, so that a correspondence between each of the at least one first identifier and one of the at least one third identifier, is recognizable; and

transferring means for transferring, to the upstream-side one of at least one midway node on said bypassing path, said at least one first identifier and the at least one third identifier, so that the correspondence between each of said at least one first identifier and one of said at least one third identifier, is recognizable.