Method and system for optimizing the connection set up time in high speed communication networks for recovering from network failure

• US 6,038,212 A
• Filed: 10/07/1997
• Issued: 03/14/2000
• Est. Priority Date: 12/13/1996
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Galand, Claude, Ouvry, Yves, Bidard, Jean, Chobert, Jean-Paul, Maurel, Olivier, Brun, Gerard
• Primary Examiner(s): Kizou, Hassan
• Assistant Examiner(s): Elallam, Ahmed
• Application Number:
  US08/946,243
• Time in Patent Office: 889 Days
• Field of Search: 370/216, 370/217, 370/218, 370/221, 370/225, 370/228, 370/237, 370/242, 370/244, 370/245, 370/254, 370/255, 370/256, 370/351, 370/389, 370/396, 370/400, 340/825.01, 340/827, 379/221, 709/239
• US Class Current: 370/216
• CPC Class Codes: H04L 2012/562 Routing
• CPC Class Codes: H04L 2012/5623 Network design, dimensioning, topology or optimisation
• CPC Class Codes: H04L 2012/5627 Fault tolerance and recovery
• CPC Class Codes: H04L 49/253 using establishment or release of connections between ports
• CPC Class Codes: H04L 49/309 Header conversion, routing tables or routing tags
• CPC Class Codes: H04L 49/557 Error correction, e.g. fault recovery or fault tolerance
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

This method enables optimizing the time required for reestablishing connections between end users attached to a data communication network, which connections were disrupted due to a network failure. The network includes access nodes and transit nodes interconnected with network links/trunks (with no specific distinction being herein required between both designations of a communication line). The end users are attached to the network through access nodes and each said access node permanently stores an image of the current network trunk including the number N_i of connections currently supported by said network trunk. Upon detection of a trunk failure, each access node supporting connections affected by said failure, is made aware of the total number (N_i) of connections in each priority group affected by the failure, together with a network dependent parameter (TP) representing the elementary processing time required to reroute a single network connection. Then each access node may independently, start a first reconnection set-up procedure at a time Ri randomly selected between zero and (N_i -n_i) *TP, where n_i is the number of connections supported by the access node in each priority group, and then space the required subsequent reconnections set-ups by a time equal to (T_i -R_i)/n_i, with T_i =N_i *TP.

Claims

1. A method for optimizing the connection set-up time and correlative communication bandwidth occupation required to perform connection reroutings to recover from network failure, in a high speed communication network interconnecting end-users via so-called connection paths through network nodes and trunks, said nodes including access nodes and intermediate nodes, said users being attached to the network via access nodes, each node storing an image of current operating network into a so-called Topology Database including the current number of connections (n) originating in an access node for each network trunk and including means for updating said image, said method including:

detecting a network failure and identifying a trunk involved in said network failure;

noting the total number (N) of connections affected by said trunk failure;

broadcasting said number (N) throughout the network wherein each network access node affected by said trunk failure is being provided with said number N information;

providing each said access node with a network dependent parameter (TP), representing the elementary processing time required for rerouting a single network connection;

providing each said affected access node with a random number (R) between zero and (N-n)×

TP;

computing a delay TNP=(T-R)/n , wherein T=N×

TP; and

,

in each access node affected by said trunk failure, starting reconnection set-up operations at time R and spacing the subsequent connections set-ups by a time equal to TNP.

2. A method for optimizing the connection set-up time and correlative communication bandwidth occupation required to recover from network failure, according to claim 1, in a multipriority environment wherein various Qualities of Service (QoS) may be assigned to the network users, whereby said total number (N) of connections affected by said trunk failure is split into so-called priority groups including N1, N2, . . . , affected connections, respectively, said method being characterized in that said reconnections are set-up in a decreasing priority order.

3. A method for optimizing the connection set-up time and correlative communication bandwidth occupation required to recover from network failure, according to claim 2 wherein the time to wait before starting the processing of reconnection of a given priority group of connections is computed for being equal to the sum of times required for processing all reconnections of higher priority groups involved in the reconnection process.

4. A method for optimizing the connection set-up time and correlative communication bandwidth occupation required to recover from multiple trunk failures within the network by rerouting the connections affected by said failures, characterized in that the network trunks references are listed in each said nodes Topology Databases in a predefined order, whereby the rerouting operations are performed as defined in claims 1 through 3 on trunk by trunk bases in said predefined list order.

5. A method according to claims 1 or 2 wherein said connection reroutings are due to a trunk failure deriving from the performance of so-called connection preemptions.

6. A method for optimizing the connection set-up time and correlative communication bandwidth occupation required to perform connection reroutings to recover from network failure, according to claim 2 wherein said number of priority groups is selected for being equal to four.

7. A method for optimizing the connection set-up time and correlative communication bandwidth occupation required to perform connection reroutings to recover from network failure, according to claim 6 wherein said broadcasting operation is performed via a so-called spanning Tree arrangement of the network.

8. A system for optimizing the connection set-up time and correlative communication bandwidth occupation required to perform connection reroutings to recover from network failure, in a high speed communication network (100) interconnecting end-users via so-called connection paths through network nodes (101-108) and links/trunks (109), said nodes including access nodes(102, 103, 104, 105), and intermediate nodes (101, 106, 107, 108), said users being attached to the network via access nodes, each node storing an image of current operating network into a so-called Topology Database including the current number of connections (n) originating in said access node for each network trunk, and including means for updating said image, said system including:

means for detecting a network failure and identifying a node and trunk involved in said network failure;

means for addressing said involved node Topology Database and deriving the total number (N) of connections affected by said trunk failure, therefrom;

means for broadcasting said number (N) and a network dependent parameter (TP), representing the elementary processing time required for rerouting a single network connection, throughout the network via a so-called network spanning Tree arrangement whereby each network access node affected by said trunk failure is being provided with said (N) and (TP) parameters;

means for providing each said affected access node with a random number (R) between zero and (N-n)×

TP;

means for computing in each said affected access node a delay TNP=(T-R)/n, wherein T=N×

TP; and

counter in each access node affected by said trunk failure, for starting said reconnection set-up process at time R and spacing the subsequent connections set-ups by a time equal to TNP.

9. A system according to claim 8, for optimizing the connection set-up time and correlative communication bandwidth occupation required to recover from network failure, in a multipriority environment wherein several Qualities of Service (QoS) may be assigned to the network users, whereby said total number (N) of connections affected by said link failure is split into so-called priority groups including N1, N2, . . . affected connections, respectively, said system being characterized in that each said access node includes:

computer for computing Ni*TP with i=1, 2, 3, . . . up to the total predefined number of priority groups;

means for initializing each said counter means in each access node affected by the trunk failure with a value equal to Σ

Ni*TP, for i being equal to each priority level higher than the level of the priority group being currently processed,

whereby the reconnection process of a given priority group is being properly initially delayed in each access node and then each subsequent reconnection set-up properly initialized in order to minimize colliding reconnection requests.