Method for rerouting a data stream

• US 5,590,118 A
• Filed: 08/23/1995
• Issued: 12/31/1996
• Est. Priority Date: 08/23/1994
• Status: Expired due to Fees

• Current Assignee: Alcatel NV (Nokia Corporation)
• Original Assignee: Alcatel NV (Nokia Corporation)
• Inventors: Nederlof, Leo
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): PHILLIPS, MATTHEW
• Application Number:
  US08/518,268
• Time in Patent Office: 496 Days
• Field of Search: 370/16, 370/16.1, 370/94.1, 370/60, 370/54, 379/221, 379/273, 395/182.02, 340/825.01, 340/827
• US Class Current: 370/218
• 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/28 using route fault recovery
• CPC Class Codes: H04L 69/40 for recovering from a failure of a protocol instance or entity, e.g. service redundancy protocols, protocol state redundancy or protocol service redirection management of faults, events, alarms or notifications in data switching networks H04L41/06
• CPC Class Codes: H04Q 2213/13141 Hunting for free outlet, circuit or channel
• CPC Class Codes: H04Q 2213/13167 Redundant apparatus
• CPC Class Codes: H04Q 3/0079 involving restoration of networks, e.g. disaster recovery, self-healing networks
• CPC Class Codes: H04Q 3/66 Traffic distributors

Abstract

A method is described for rerouting a data stream previously routed via a route through a switching network which has now failed. The method includes the steps of detecting the failure on a link (L19) between first (SN1) and second (SN9) switching nodes in one of these switching nodes (SN1); transmitting from this one switching node (SN1) a request message (REQ) with first (IDA) and second (IDB) address fields containing addresses of the first (1) and second (9) switching nodes, respectively; in each switching node having received the request message (REQ) retransmitting it, until an alternative route for the data stream is found between two end switching nodes of said alternative route; and by one of these end switching nodes (SN1) chosen according to a predetermined rule after the alternative route has been found, allocating the data stream to this alternative route and transmitting it thereon.

Claims

1. A method for rerouting, upon failure of a route, a data stream previously routed via said route through a switching network which includes a plurality of switching nodes (SN1..SN9) with respective addresses (1..9) and interconnected by respective links (L12..L89) used for setting up routes, and said method including the steps of:

detecting said failure of said route on one of said links (L19) between first (SN1) and second (SN9) said switching nodes in at least said first switching node (SN1);

transmitting from said first switching node (SN1) and on each but said one of said links connected to it, a request message (REQ) having first (IDA) and second (IDB) address fields containing addresses of said first (1) and second (9) switching nodes, respectively;

in each of said switching nodes having received said request message (REQ) on a link, retransmitting said request message (REQ) on each link connected to it but said link on which said request message (REQ) was received, until an alternative route for said data stream is found between two end switching nodes of said alternative route;

allocating said data stream to said alternative route and transmitting it thereon, characterized in that said allocation step is performed by a said end switching node (SN1) chosen amongst said two end switching nodes according to a predetermined rule, the choice being made after said alternative route has been found.

2. A method according to claim 1, characterized in that said predetermined rule is based on the addresses (1,9) of said end switching nodes.

3. A method according to claim 1, characterized in that, when said request message (REQ) is received in an intermediate one (SN3) of said switching nodes which already received a further request message whose first and second address fields include the addresses of said second (9) and first (1) switching nodes, respectively, said alternative route is found between said first (SN1) and second (SN9) switching nodes, said intermediate switching node (SN3) choosing said switching node (SN1) performing said allocation.

4. A method according to claim 1, characterized in that, when said request message (REQ) is received in said second switching node (SN9), said alternative route is found between said first (SN1) and second (SN9) switching nodes, said second switching node (SN9) thereupon choosing said switching node (SN1) performing said allocation.

5. A method according to claim 1, characterized in that, when said request message (REQ) is received in an intermediate one (SN7) of said switching nodes which already received a request message originating from a third switching node (SN8) and whose second address field includes the address (6) of said second switching node (SN6), said alternative route is found between said first (SN5) and third (SN8) switching nodes, said intermediate switching node (SN7) choosing said switching node (SN5) performing said allocation.

6. A method according to claim 5, characterized in that said switching node (SN3) choosing the switching node (SN1) performing said allocation, upon having made said choice, transmits to said end switching node (SN1) chosen to perform said allocation a confirmation message (CNF).

7. A method according to claim 6, characterized in that said switching node (SN1) chosen to perform said allocation, upon receipt of said confirmation message (CNF), transmits a connection message (CON) to the other end switching node (SN9) indicating thereto said allocation of said data stream to said alternative route.

8. A method according to claim 7, characterized in that, when a said switching node on said alternative route between said switching node choosing said switching node performing said allocation and said second end switching node not chosen to perform said allocation receives a said connection message (CON), said switching node transmits a RELREQOUT release message (RELREQOUT) on each link connected to said switching node whereon superfluous bandwidth is reserved previously.

9. A method according to claim 8, characterized in that, when a said RELREQOUT release message (RELREQOUT) is received in said switching node choosing said switching node performing said allocation, a RELCONFIN release message (RELCONFIN) is transmitted by said switching node choosing said switching node performing said allocation to indicate that a confirmation message (CNF) previously transmitted therefrom should be cancelled or that the bandwidth specified therein should be reduced.

10. A method according to claim 6, characterized in that said confirmation message (CNF) includes a bandwidth field with the bandwidth allocated to said alternative route.

11. A method according to claim 6, characterized in that, when a said switching node receives a said confirmation message (CNF), said switching node transmits a RELREQOUT release message (RELREQOUT) on each link connected to said switching node whereon superfluous bandwidth is reserved previously.

12. A method according to claim 6, characterized in that, when a said switching node receives a said confirmation message (CNF) wherein superfluous bandwidth is allocated to said alternative route, a RELCONFOUT release message (RELCONFOUT) is transmitted on said link whereon said confirmation message (CNF) is received.

13. A method according to claim 1, characterized in that said request message (REQ) includes bandwidth fields (BWAB, BWBA) with the bandwidth requested on the link on which it is transmitted from and to the switching node transmitting it, and that upon receipt of said request message (REQ) in the latter switching node, said requested bandwidth is reserved therein.

14. A method according to claim 13, characterized in that, when said requested bandwidth is larger than the sum of bandwidths available to and from said latter switching node on all links connected to said latter switching node but said link on which said request message (REQ) is received, said latter switching node stores an excess request message in a hold buffer provided thereto in said latter switching node, said excess request message indicating that an excess bandwidth requested in said received request message (REQ) is not yet requested in transmitted request messages.

15. A method according to claim 14, characterized in that said excess request message includes bandwidth fields with said excess bandwidth from and to said latter switching node respectively and further includes a signature field with a signature of said received request message (REQ).

16. A method according to claim 14, characterized in that, when later on bandwidth on a link connected to said latter switching node which is different from said link whereon said request message (REQ) is received becomes available, a request message is transmitted on said link whereon said bandwidth becomes available, wherein the bandwidth requested equals the minimum of said excess bandwidth and said bandwidth that becomes available, and said excess request message is modified in such a way that it indicates remaining not yet requested bandwidth.

17. A method according to claim 16, characterized in that, when said minimum equals said excess bandwidth, said excess request message is erased from said hold buffer.

18. A method according to claim 13, characterized in that said request message (REQ) includes an overrequest field (OVERRQ) which when the sum of the bandwidths requested for a same alternative route in request messages transmitted by a said switching node is larger than the bandwidth requested by a request message for said same alternative route received by the latter switching node, includes the latter received requested bandwidth.

19. A method according to claim 13, characterized in that, when said requested bandwidth is larger than the sum of bandwidths available to and from said latter switching node on all links connected to said latter switching node but said link on which said request message (REQ) is received, and when there is no chance that later on bandwidth becomes available on a link connected to said latter switching node which is different from said link whereon said request message (REQ) is received, said latter switching node transmits a RELREQIN release message (RELREQIN) on said link whereon said request message (REQ) is received to indicate that bandwidth reserved thereon should be released.

20. A method according to claim 1, characterized in that said request message (REQ) includes a hop count value which upon each rebroadcasting thereof is increased by one.

21. A method according to claim 1, characterized in that, when said request message (REQ) is received in an intermediate one of said switching nodes which already transmitted on said link whereon said request message (REQ) is received in said intermediate switching node, a further request message whose first and second address fields include the addresses of said second and first switching nodes respectively, said alternative route is found between said first and second switching nodes, either said intermediate node or said node where said request message (REQ) is received from being designated confirmation node, said confirmation node transmitting a confirmation message to said end switching node chosen to perform said allocation and the one of said intermediate node and said node where said request message is received from which is not said confirmation node transmitting a RELNACK release message (RELNACK) on said link whereon said request message (REQ) and said further request message are transmitted to either cancel said request message (REQ) or said further request message depending on the choice of said confirmation node.

22. A method according to claim 1, characterized in that, whenever available bandwidth is requested in two said request messages transmitted in opposite directions on a said ink by two of said switching nodes connected thereto, one of said switching nodes is designated master node whilst the other is designated slave node, said available bandwidth being assigned to said request message transmitted by said master node and said request message transmitted by said slave node being cancelled by a RELNACK release message (RELNACK).

23. A method according to claim 1, characterized in that said switching network is a cell switching network, said data stream being a cell stream, and that said request, confirmation and connection messages are each confined to one cell transmitted through said cell switching network.

24. A method according to claim 1, characterized in that said switching network operates according to the asynchronous transfer mode (ATM) protocol.

25. A method according to claim 1, characterized in that said switching network operates according to the synchronous digital hierarchy (SDH) protocol.

33. A method according to claim 1, characterized in that it is used for rerouting a plurality of data streams, and that when not all data streams have been restored after a predetermined time has elapsed, then a method for rerouting the data streams which have not been restored includes the steps of:

broadcasting trigger messages in a controller node;

in each of said switching nodes having received a said trigger message on a receipt link, transmitting to said controller node an information message containing the amounts of bandwidth available on the links connected to it, and rebroadcasting said trigger message on each link connected to it but said link on which said trigger message was received;

in said controller node, calculating from said received amounts of bandwidth an alternative route for said data stream and thereupon allocating said route to said data stream;

transmitting said data stream on said alternative route, characterized in that a said switching node having detected said failure is, according to a predetermined rule, chosen as said controller node;

whereby the rest of said data streams are restored.

26. A method for rerouting upon failure of a route, a data stream previously routed via said route through a switching network which includes a plurality of switching nodes (SN1..SN9) with respective addresses (1..9) and interconnected by respective links (L12..L89) used for setting up routes, said method including the steps of:

broadcasting trigger messages in a controller node;

in each of said switching nodes having received a said trigger message on a receipt link, transmitting to said controller node an information message containing the amounts of bandwidth available on the links connected to it, and rebroadcasting said trigger message on each link connected to it but said link on which said trigger message was received;

in said controller node, calculating from said received amounts of bandwidth an alternative route for said data stream and thereupon allocating said route to said data stream;

transmitting said data stream on said alternative route, characterized in that a said switching node having detected said failure is, according to a predetermined rule, chosen as said controller node.

27. A method according to claim 26, characterized in that it includes the additional steps of:

in a said switching node having detected said failure, transmitting control messages having a control field for containing the address of said controller node and which is initialized with the address of said detecting switching node;

in each switching node receiving a said control message, transmitting an adapted said control message whose control field is adapted according to a predetermined rule.

28. A method according to claim 27, characterized in that said predetermined rule is based on the contents of the control field of said received control message and the address of said switching node in which it is received.

29. A method according to claim 26, characterized in that said trigger message includes a hop count value which upon each rebroadcasting thereof is increased by one.

30. A method according to claim 26, characterized in that said trigger message includes a controller field including the address of said controller node.

31. A method according to claim 26, characterized in that each said switching node receiving a said trigger message stores an identity of said link on which said trigger message was received in a storage means thereof.

32. A method according to claim 26, characterized in that said information message also contains information as to which paths are terminated in the switching node from which it originates.