Network load distribution system and network load distribution method

• US 6,760,314 B1
• Filed: 06/30/2000
• Issued: 07/06/2004
• Est. Priority Date: 07/02/1999
• Status: Active Grant

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Iwata, Atsushi
• Primary Examiner(s): Chin, Wellington
• Assistant Examiner(s): PHAM, BRENDA H
• Application Number:
  US09/608,954
• Time in Patent Office: 1,467 Days
• Field of Search: 370/254, 370/255, 370/229, 370/230, 370/231, 370/235, 370/238, 370/237, 370/238.1, 370/252, 370/351, 370/395.31, 370/410, 370/411, 370/256
• US Class Current: 370/254
• CPC Class Codes: H04L 43/00 Arrangements for monitoring or testing data switching networks
• CPC Class Codes: H04L 43/026 using flow identification
• CPC Class Codes: H04L 43/16 Threshold monitoring
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04L 45/42 Centralised routing

Abstract

A load distribution system of a network having a plurality of nodes connected to each other with links includes a load distribution server for receiving network state information from the plurality of nodes and determining an optimum link metric based on the network state information to transmit the optimum link metric to the plurality of nodes, whereby dynamic path selection is conducted at each node based on the optimum link metric.

Claims

1. An apparatus for use in a network having a plurality of nodes connected with links, the apparatus comprising:

a network load distribution system including a load distribution server for receiving network state information from said plurality of nodes and determining an optimum link metric based on said network state information and transmitting said optimum link metric to said plurality of nodes, wherein

dynamic path selection is conducted at each node based on said optimum link metric.

2. The apparatus according to claim 1, wherein said network state information includes:

network topology information indicative of a mode of connection of said node to each said adjacent node;

link metric information indicative of a value of a link metric assigned to a direction of transmission from said node to each said adjacent link; and

traffic flow information indicative of a traffic characteristic and a traffic parameter at said node.

3. The apparatus a according to claim 1, wherein said network state information includes:

network topology information indicative of a mode of connection of said node to each said adjacent node;

link metric information indicative of a value of a link metric assigned to a direction of transmission from said node to each said adjacent link;

link load information indicative of a use band and a maximum usable band on each said link adjacent to said node in a direction of transmission from said node; and

traffic flow information indicative of a traffic characteristic and a traffic parameter at said node.

4. The apparatus according to claim 1, wherein said load distribution server includes:

a path selection emulator for emulating operation of path selection for all of said nodes in said network,

said path selection emulator, while referring to said network state information and changing a value of a link metric in said path selection emulator, repeatedly conducting emulation to obtain said optimum link metric.

5. The apparatus according to claim 1, wherein

said network state information includes:

network topology information indicative of a mode of connection of said node to each said adjacent node;

link metric information indicative of a value of a link metric assigned to a direction of transmission from said node to each said adjacent link, and

traffic flow information indicative of a traffic characteristic and a traffic parameter at said node; and

said load distribution server includes

a path selection emulator for emulating operation of path selection for all of said nodes in said network,

said path selection emulator, while referring to said network state information and changing a value of a link metric in said path selection emulator, repeatedly conducting emulation to obtain said optimum link metric.

6. The apparatus according to claim 1, wherein

said network state information includes:

network topology information indicative of a mode of connection of said node to each said adjacent node;

link metric information indicative of a value of a link metric assigned to a direction of transmission from said node to each said adjacent link;

link load information indicative of a use band and a maximum usable band on each said link adjacent to said node in a direction of transmission from said node; and

traffic flow information indicative of a traffic characteristic and a traffic parameter at said node; and

said load distribution server includes;

a path selection emulator for emulating operation of path selection for all of said nodes in said network,

said path selection emulator, while referring to said network state information and changing a value of a link metric in said path selection emulator, repeatedly conducting emulation to obtain said optimum link metric.

7. The apparatus according to claim 4, wherein said load distribution server obtains said optimum link metric by repeatedly conducting said emulation by means of said path selection emulator while changing a value of a link metric in said path selection emulator such that a link load of each said link in said network is equal for each said link.

8. The apparatus according to claim 4, wherein said load distribution server obtains said optimum link metric by repeatedly conducting said emulation by means of said path selection emulator while changing a value of a link metric in said path selection emulator such that a value obtained by dividing the amount of use bands of each said link in said network by the amount of real link bands is equal for each said link.

9. The apparatus according to claim 1, wherein for said dynamic path selection, at each said node, a routing table of said node is updated based on said optimum link metric and furthermore, said optimum link metric is notified to and from other said node adjacent to said node by a routing protocol to update the routing table based on information from said adjacent node.

10. The apparatus according to claim 1, wherein one or a plurality of said nodes in said network have said load distribution server provided therein.

11. The apparatus according to claim 1, wherein one or a plurality of said nodes in said network have said load distribution server provided therein, said load distribution server notifying said node having said load distribution server provided therein to each of other nodes not having said load distribution server provided therein by said routing protocol to recognize a position of the load distribution server.

12. The apparatus according to claim 1, wherein one or a plurality of said nodes in said network have said load distribution server provided therein, and when said network is connection-oriented, an existing connection is changed as well according to said optimum link metric at the time of notification of said optimum link metric to and from said adjacent node.

13. The apparatus according to claim 1, wherein one or a plurality of said nodes in said network have said load distribution server provided therein, when said network is connection-oriented, an existing connection is changed as well according to said optimum link metric at the time of notification of said optimum link metric to and from said adjacent node, and at the time of changing said existing connection, after newly establishing an optimum connection while leaving said existing connection as it is and making a detour for the service of said existing connection to said new optimum connection so as to prevent interruption of services by said existing connection, said existing connection is cut off.

21. The apparatus according to claim 1, wherein at least one node is connected to less than all the nodes.

14. A load distribution method in a network having a plurality of nodes connected with links, wherein:

a load distribution server receives network state information from said plurality of nodes and determines an optimum link metric based on said network state information to transmit said optimum link metric to said plurality of nodes; and

dynamic path selection is conducted at each node based on said optimum link metric.

15. The network load distribution method as set forth in claim 14, wherein said network state information includes:

network topology information indicative of a mode of connection of said node to each said adjacent node;

link metric information indicative of a value of a link metric assigned to a direction of transmission from said node to each said adjacent link; and

traffic flow information indicative of a traffic characteristic and a traffic parameter at said node.

16. The network load distribution method as set forth in claim 14, wherein said network state information includes:

network topology information indicative of a mode of connection of said node to each said adjacent node;

link metric information indicative of a value of a link metric assigned to a direction of transmission from said node to each said adjacent link;

link load information indicative of a use band and a maximum usable band on each said link adjacent to said node in a direction of transmission from said node; and

traffic flow information indicative of a traffic characteristic and a traffic parameter at said node.

17. The network load distribution method as set forth in claim 14, wherein at said load distribution server, a path selection emulator for emulating operation of path selection for all of said nodes in said network repeatedly conducts emulation while referring to said network state information and changing a value of a link metric in said path selection emulator to obtain said optimum link metric.

18. The network load distribution method as set forth in claim 14, wherein

said network state information includes:

network topology information indicative of a mode of connection of said node to each said adjacent node;

link metric information indicative of a value of a link metric assigned to a direction of transmission from said node to each said adjacent link; and

traffic flow information indicative of a traffic characteristic and a traffic parameter at said node; and

said load distribution server includes;

a path selection emulator for emulating operation of path selection for all of said nodes in said network repeatedly conducts emulation while referring to said network state information and changing a value of a link metric in said path selection emulator to obtain said optimum link metric.

19. The network load distribution method as set forth in claim 14, wherein

said network state information includes:

network topology information indicative of a mode of connection of said node to each said adjacent node;

link metric information indicative of a value of a link metric assigned to a direction of transmission from said node to each said adjacent link;

link load information indicative of a use band and a maximum usable band on each said link adjacent to said node in a direction of transmission from said node; and

traffic flow information indicative of a traffic characteristic and a traffic parameter at said node; and

said load distribution server includes;

a path selection emulator for emulating operation of path selection for all of said nodes in said network repeatedly conducts emulation while referring to said network state information and changing a value of a link metric in said path selection emulator to obtain said optimum link metric.

20. The network load distribution method as set forth in claim 14, wherein for said dynamic path selection, at each said node, a routing table of said node is updated based on said optimum link metric and furthermore said optimum link metric is notified to and from other said node adjacent to said node by a routing protocol to update the routing table based on information from said adjacent node.