Load distribution failure recovery system and method

• US 20010034853A1
• Filed: 04/12/2001
• Published: 10/25/2001
• Est. Priority Date: 04/13/2000
• Status: Abandoned Application

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Iwata, Atsushi, Takatama, Hirokazu
• Application Number:
  US09/833,042
• Publication Number:
  US 20010034853A1
• Time in Patent Office: Days
• US Class Current: 714/4
• CPC Class Codes: H04Q 2213/13103 Memory
• CPC Class Codes: H04Q 2213/13109 Initializing, personal profile
• CPC Class Codes: H04Q 2213/13141 Hunting for free outlet, circuit or channel
• CPC Class Codes: H04Q 2213/13164 Traffic (registration, measurement,...)
• CPC Class Codes: H04Q 2213/13166 Fault prevention
• CPC Class Codes: H04Q 2213/13167 Redundant apparatus
• CPC Class Codes: H04Q 2213/1338 Inter-exchange connection
• CPC Class Codes: H04Q 3/66 Traffic distributors

Abstract

A load distribution failure recovery device allowing the failure recovery process to be executed at the high performance rate and in a short time is disclosed. A link state memory retrievably stores link state information of the connection-oriented network. The link state database is used to dynamically calculate an alternate route for failure recovery when a failure notification is received. A route candidate memory retrievably stores a plurality of route candidates for each of possible endpoint nodes. A load distribution route calculator determines a route for a normally set up connection such that a route having a relatively small load is selected from a plurality of route candidates with a relatively high probability.

Claims

1. A load distribution device provided in each of nodes included in a network, comprising:

a link state memory retrievably storing link state information of the network, wherein the link state database is used to dynamically calculate an alternate route for failure recovery when a failure notification is received;

a route candidate memory retrievably storing a plurality of route candidates for each of possible endpoint nodes; and

a route determiner for determining a route for a normally set up connection, wherein a route having a relatively small load is selected from a plurality of route candidates with a relatively high probability.

2. The load distribution device according to

claim 1

, wherein the route determiner comprises:

a route quality checker for checking quality of each of the route candidates by referring to the link state information stored in the link state memory when receiving a connection setup request; and

a route candidate selector for selecting the route for a requested connection from the route candidates depending on the quality of each of the route candidates.

3. The load distribution device according to

claim 2

, wherein the route candidate selector selects a route candidate having a broadest available bandwidth as the route for a requested connection.

4. The load distribution device according to

claim 2

, wherein the route candidate selector selects a route candidate as the route for a requested connection from the route candidates in a round robin fashion.

5. The load distribution device according to

claim 2

, wherein the route candidate selector selects a route candidate as the route for a requested connection from the route candidates in a weighted round robin fashion using an available bandwidth of each of the route candidates as a weight.

6. The load distribution device according to

claim 2

, wherein the route candidate selector selects a route candidate having a shortest delay time as the route for a requested connection among the route candidates satisfying a requested quality.

7. The load distribution device according to

claim 2

, wherein the route candidate selector selects a route candidate having a smallest fluctuation in data arrival interval as the route for a requested connection among the route candidates satisfying a requested quality.

8. The load distribution device according to

claim 2

, wherein the route candidate selector selects a route candidate as the route for a requested connection from the route candidates in a weighted round robin fashion using a reciprocal of delay time for each of the route candidates as a weight.

9. The load distribution device according to

claim 2

, wherein the route candidate selector selects a route candidate as the route for a requested connection from the route candidates in a weighted round robin fashion using a reciprocal of fluctuation in data arrival interval for each of the route candidates as a weight.

10. The load distribution device according to

claim 2

, further comprising:

an on-demand route calculator for calculating a route satisfying a requested quality by referring to the link state memory when no route candidate is found in the route candidate selector.

11. The load distribution device according to

claim 1

, further comprising:

an alternate route determiner for determining an alternate route when a failure notification is received, wherein a route having a relatively small load is selected as the alternate route from a plurality of route candidates with a relatively high probability.

12. The load distribution device according to

claim 11

, wherein the alternate route determiner comprises:

a route quality checker for checking quality of each of the route candidates by referring to the link state information stored in the link state memory when receiving a failure notification message; and

a route candidate selector for selecting the alternate route for failure recovery from the route candidates depending on the quality of each of the route candidates.

13. The load distribution device according to

claim 12

, wherein the route candidate selector selects a route candidate having a broadest available bandwidth as the alternate route for failure recovery.

14. The load distribution device according to

claim 12

, wherein the route candidate selector selects a route candidate as the alternate route for failure recovery from the route candidates in a round robin fashion.

15. The load distribution device according to

claim 12

, wherein the route candidate selector selects a route candidate as the alternate route for failure recovery from the route candidates in a weighted round robin fashion using an available bandwidth of each of the route candidates as a weight.

16. The load distribution device according to

claim 12

, wherein the route candidate selector selects a route candidate having a shortest delay time as the alternate route for failure recovery among the route candidates satisfying a required quality.

17. The load distribution device according to

claim 12

, wherein the route candidate selector selects a route candidate having a smallest fluctuation in data arrival interval as the alternate route for failure recovery among the route candidates satisfying a required quality.

18. The load distribution device according to

claim 12

, where in the route candidate selector selects a route candidate as the alternate route for failure recovery from the route candidates in a weighted round robin fashion using a reciprocal of delay time for each of the route candidates as a weight.

19. The load distribution device according to

claim 12

, wherein the route candidate selector selects a route candidate as the alternate route for failure recovery from the route candidates in a weighted round robin fashion using a reciprocal of fluctuation in data arrival interval for each of the route candidates as a weight.

20. The load distribution device according to

claim 12

, further comprising:

an on-demand route calculator for calculating an alternate route satisfying a required quality by referring to the link state memory when no route candidate is found in the route candidate selector.

21. A node in a network, comprising:

a connection setup request receiver;

a connection setup processor;

a link state memory retrievably storing link state information of the network, wherein the link state database is used to dynamically calculate an alternate route for failure recovery when a failure notification is received;

a route candidate memory retrievably storing a plurality of route candidates for each of possible endpoint nodes; and

a route determiner for determining a route for a normally set up connection to set up the requested connection, wherein a route having a relatively small load is selected from a plurality of route candidates with a relatively high probability.

22. The node according to

claim 21

, wherein the route determiner comprises:

a route quality checker for checking quality of each of the route candidates by referring to the link state information stored in the link state memory when receiving a connection setup request; and

a route candidate selector for selecting the route for the requested connection from the route candidates depending on the quality of each of the route candidates.

23. The node according to

claim 21

, further comprising:

an alternate route determiner for determining an alternate route when a failure notification is received, wherein a route having a relatively small load is selected as the alternate route from a plurality of route candidates with a relatively high probability.

24. The node according to

claim 23

, wherein the alternate route determiner comprises:

a route quality checker for checking quality of each of the route candidates by referring to the link state information stored in the link state memory when receiving a failure notification message; and

a route candidate selector for selecting the alternate route for failure recovery from the route candidates depending on the quality of each of the route candidates.

25. The node according to

claim 21

, further comprising:

a link state memory controller for updating at least the link state memory when one of a link state message and a failure notification message is received.

26. A load distribution method in each of nodes included in a network, comprising the steps of:

a) retrievably storing link state information of the network, wherein the link state database is used to dynamically calculate an alternate route for failure recovery when a failure notification is received;

b) retrievably storing a plurality of route candidates for each of possible endpoint nodes; and

c) determining a route for a normally set up connection, wherein a route having a relatively small load is selected from a plurality of route candidates with a relatively high probability.

27. The load distribution method according to

claim 26

, wherein the step (c) comprises the steps of:

checking quality of each of the route candidates by referring to the link stats information when receiving a connection setup request; and

selecting the route for a requested connection from the route candidates depending on the quality of each of the route candidates.

28. The load distribution method according to

claim 26

, further comprising the step of:

d) determining an alternate route when a failure notification is received, wherein a route having a relatively small load is selected as the alternate route from a plurality of route candidates with a relatively high probability.

29. The load distribution method according to

claim 28

, wherein the step (d) comprises the steps of:

checking quality of each of the route candidates by referring to the link state information when receiving a failure notification message; and

selecting the alternate route for failure recovery from the route candidates depending on the quality of each of the route candidates.

30. A recording medium storing a computer program for performing a load distribution operation in each of nodes included in a network, the computer program comprising the steps of:

a) retrievably storing link state information of the network, wherein the link state database is used to dynamically calculate an alternate route for failure recovery when a failure notification is received;

b) retrievably storing a plurality of route candidates for each of possible endpoint nodes; and

c) determining a route for a normally set up connection, wherein a route having a relatively small load is selected from a plurality of route candidates with a relatively high probability.

31. The recording medium according to

claim 30

, wherein the step (c) comprises the steps of:

checking quality of each of the route candidates by referring to the link state information when receiving a connection setup request; and

selecting the route for a requested connection from the route candidates depending on the quality of each of the route candidates.

32. The recording medium according to

claim 30

, further comprising the step of:

d) determining an alternate route when a failure notification is received, wherein a route having a relatively small load is selected as the alternate route from a plurality of route candidates with a relatively high probability.

33. The recording medium according to

claim 32

, wherein the step (d) comprises the steps of:

checking quality of each of the route candidates by referring to the link state information when receiving a failure notification message; and

selecting the alternate route for failure recovery from the route candidates depending on the quality of each of the route candidates.