Router device and cut-through path control method for realizing load balancing at intermediate routers

• US 7,009,987 B1
• Filed: 10/29/1999
• Issued: 03/07/2006
• Est. Priority Date: 10/30/1998
• Status: Expired due to Fees

• Current Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Matsuzawa, Shigeo, Mogi, Akiyoshi, Konno, Toru
• Primary Examiner(s): Chin, Wellington
• Assistant Examiner(s): HO, CHUONG T
• Application Number:
  US09/429,632
• Time in Patent Office: 2,321 Days
• Field of Search: 370/395, 370/397, 370/410, 370/409, 370/395.3, 370/395.31, 370/395.32, 370/389, 370/392, 370/395.43, 370/352, 370/401, 370/393, 370/396, 370/390, 370/398, 709/203, 709/227, 709/238, 709/242
• 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/24 Multipath
• CPC Class Codes: H04L 45/40 Wormhole routing
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/101 based on network conditions
• CPC Class Codes: H04L 67/1036 Load balancing of requests to servers for services different from user content provisioning, e.g. load balancing across domain name servers
• CPC Class Codes: H04L 69/14 Multichannel or multilink protocols
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers

Abstract

A router device and a cut-through path control method capable of carrying out the load balancing at an intermediate router device which actually has a multi-path information, without requiring a special processing at the edge router are disclosed. At a router device at which multi-path exists, one router among a plurality of routers that can possibly be a next hop router is selected so as to contribute to a load balancing, according to a whole or a prescribed part of information regarding a state of cut-through path set up in which the router device is involved, at a time of setting up a cut-through path in the multi-path, and a prescribed control for setting up the cut-through path with that one router as the next hop router is carried out. Also, one cut-through path that contributes to the load balancing when a route change is made is selected among cut-through paths for which the route change at the router device is possible, and a route of that one cut-through path is changed so as to contribute to the load balancing.

Claims

1. A cut-through path control method at a router device at which multi-path exists, comprising:

selecting one router among a plurality of routers that can possibly be a next hop router so as to contribute to a load balancing, according to a whole or a prescribed part of information regarding a state of cut-through path set up in which the router device is involved, at a time of setting up a cut-through path in the multi-path; and

carrying out a prescribed control for setting up the cut-through path with said one router as the next hop router,

wherein the selecting step selects said one router according to a number of already set up cut-through paths that are used to route packets to a same destination node such that numbers of cut-through paths at said plurality of routers are uniformly distributed among said plurality of routers,

wherein the selecting step includes the sub-steps of;

assigning possible residue values starting from 0 that are obtainable by dividing a given integer by a total number of said plurality of routers, respectively to said plurality of routers, one residue value per each router; and

selecting one of said plurality of routers which is assigned with a residue value obtained by dividing the number of already set up cut-through paths by the total number of said plurality of routers as said one router.

2. The method of claim 1, further comprising the steps of:

sending a message for setting up the cut-through path to said one router; and

making an information setting necessary for utilizing the cut-through path when the cut-through path is set up.

3. The method of claim 1, further comprising the steps of:

sending a message for setting up the cut-through path to said one router when no other already set up cut-through path to said one router exists, and making an information setting necessary for utilizing the cut-through path when the cut-through path is set up; and

making another information setting necessary for merging the cut-through path with an already set up cut-through path to said one router when the already set up cut-through path exists.

4. The method of claim 1, wherein the setting up of the cut-through path starts at a timing of receiving a message for setting up the cut-through path from a node device on an upstream side.

5. The method of claim 1, further comprising the steps of:

selecting one cut-through path that contributes to the load balancing when a route change is made, among cut-through paths for which the route change at the router device is possible; and

changing a route of said one cut-through path so as to contribute to the load balancing.

6. The method of claim 5, further comprising the step of:

checking a traffic amount to each of a plurality of node devices that are next hop nodes of cut-through paths from the router device at prescribed timings;

wherein the selecting step selects said one cut-through path that satisfies a prescribed condition regarding the traffic amount when a level of imbalance among traffic amounts to said plurality of node devices exceeds a prescribed tolerable range, said one cut-through path being in a multi-path with one node device with less traffic amount as a next hop node; and

the changing step changes the route of said one cut-through path by changing the next hop node of said one cut-through path to another node device with more traffic amount.

7. The method of claim 6, wherein the selecting step and the changing step are repeated until the level of imbalance becomes within the prescribed tolerable range or there is no more cut-through path that can be selected by the selecting step.

8. The method of claim 6, wherein the selecting step selects one or a plurality of optimal solutions for said one cut-through path.

9. The method of claim 4,

wherein said selecting step selects said one router according to a number of already set up cut-through paths that are used to route packets to a same destination node that is also included in the message for setting up the cut-through path that is received by said router device.

10. A cut-through path control method at a router device at which multi-path exists, comprising:

selecting one router among a plurality of routers that can possibly be a next hop, router so as to contribute to a load balancing, according to a whole or a prescribed part of information regarding a state of cut-through path set up in which the router device is involved, at a time of setting up a cut-through path in the multi-path; and

carrying out a prescribed control for setting up the cut-through path with said one router as the next hop router,

wherein the selecting step selects said one router according to a number of already set up cut-through paths that are used to route packets to a same destination node such that numbers of cut-through paths at said plurality of routers are evenly distributed among said plurality of routers according to link rates with respect to said plurality of routers,

wherein the selecting step includes the sub-steps of;

assigning possible residue values starting from 0 that are obtainable by dividing a given integer by a total of elements constituting an integer ratio indicating or approximating a ratio of the link rates with respect to said plurality of routers, respectively to said plurality of routers, as many residues values as a number proportional to a link rate with respect to each router per each router; and

selecting one of said plurality of routers which is assigned with a residue value obtained by dividing the number of already set up cut-through paths by the total of the elements constituting the integer ratio as said one router.

11. The method of claim 10, further comprising the steps of:

sending a message for setting up the cut-through path to said one router; and

making an information setting necessary for utilizing the cut-through path when the cut-through path is set up.

12. The method of claim 10, further comprising the steps of:

sending a message for setting up the cut-through path to said one router when no other already set up cut-through path to said one router exists and making an information setting necessary for utilizing the cut-through path when the cut-through path is set up; and

making another information setting necessary for merging the cut-through path with an already set up cut-through path to said one router when the already set up cut-through path exists.

13. The method of claim 10, wherein the setting up of the cut-through path starts at a timing of receiving a message for setting up the cut-through path from a node device on an upstream side.

14. The method of claim 13, wherein said selecting step selects said one router according to a number of already set up cut-through paths that are used to route packets to a same destination node that is also included in the message for setting up the cut-through path that is received by said router device.

15. The method of claim 10, further comprising the steps of:

selecting one cut-through path that contributes to the load balancing when a route change is made, among cut-through paths for which the route change at the router device is possible; and

changing a route of said one cut-through path so as to contribute to the load balancing.

16. The method of claim 15, further comprising the step of;

checking a traffic amount to each of a plurality of node devices that are next hop nodes of cut-through paths from the router device at prescribed timings;

wherein the selecting step selects said one cut-through path that satisfies a prescribed condition regarding the traffic amount when a level of imbalance among traffic amounts to said plurality of node devices exceeds a prescribed tolerable range, said one cut-through path being in a multi-path with one node device with less traffic amount as a next hop node; and

the changing step changes the route of said one cut-through path by changing the next hop node of said one cut-through path to another node device with more traffic amount.

17. The method of claim 16, wherein the selecting step and the changing step are repeated until the level of imbalance becomes within the prescribed tolerable range or there is no more cut-through path that can be selected by the selecting step.

18. The method of claim 16, wherein the selecting step selects one or a plurality of optimal solutions for said one cut-through path.

19. A router device at which multi-path exists, comprising:

a processing unit configured to select one router among a plurality of routers that can possibly be a next hop router so as to contribute to a load balancing, according to a whole or a prescribed part of information regarding a state of cut-through path set up in which the router device is involved, at a time of setting up a cut-through path in the multi-path;

a control unit configured to carry out a prescribed control for setting up the cut-through path with said one router as the next hop router; and

a transfer unit configured to transfer datagrams using the cut-through path,

wherein the processing unit selects said one router according to a number of already set up cut-through paths that are used to route packets to a same destination node such that numbers of cut-through paths at said plurality of routers are uniformly distributed among said plurality of routers,

wherein the processing unit;

assigns possible residue values starting from 0 that are obtainable by dividing a given integer by a total number of said plurality of routers, respectively to said plurality of routers, one residue value per each router; and

selects one of said plurality of routers which is assigned with a residue value obtained by dividing the number of already set up cut-through paths by the total number of said plurality of routers as said one router.

20. The router device of claim 19, further comprising:

a selecting unit configured to select one cut-through path that contributes to a load balancing when a route change is made, among cut-through paths for which the route change at the router device is possible;

a route changing unit configured to change a route of said one cut-through path so as to contribute to the load balancing.

21. The router device of claim 20, further comprising:

a measurement unit configured to check a traffic amount to each of a plurality of node devices that are next hop nodes of cut-through paths from the router device at prescribed timings;

wherein the selecting unit selects said one cut-through path that satisfies a prescribed condition regarding the traffic amount when a level of imbalance among traffic amounts to said plurality of node devices exceeds a prescribed tolerable range, said one cut-through path being in a multi-path with one node device with less traffic amount as a next hop node; and

the route changing unit changes the route of said one cut-through path by changing the next hop node of said one cut-through path to another node device with more traffic amount.

22. The router device of claim 19, wherein the control unit sends a message for setting up the cut-through path to said one router, and makes an information setting necessary for utilizing the cut-through path when the cut-through path is set up.

23. A router device at which multi-path exists, comprising:

a processing unit configured to select one router among a plurality of routers that can possibly be a next hop router so as to contribute to a load balancing according to a whole or a prescribed part of information regarding a state of cut-through path set up in which the router device is involved, at a time of setting up a cut-through path in the multi-path;

a control unit configured to carry out a prescribed control for setting up the cut-through path with said one router as the next hop router; and

a transfer unit configured to transfer datagrams using the cut-through path,

wherein the processing unit selects said one router according to a number of already set up cut-through paths that are used to route packets to a same destination node such that the numbers of cut-through paths at said plurality of routers are evenly distributed among said plurality of routers according to link rates with respect to said plurality of routers,

wherein the processing unit;

assigns possible residue values starting from 0 that are obtainable by dividing a given integer by a total of elements constituting an integer ratio indicating or approximating a ratio of the link rates with respect to said plurality of routers, respectively to said plurality of routers, as many residues values as a number proportional to a link rate with respect to each router per each router; and

selects one of said plurality of routers which is assigned with a residue value obtained by dividing the number of already set up cut-through paths by the total of the elements constituting the integer ratio as said one router.

24. The router device of claim 23, further comprising:

a selecting unit configured to select one cut-through path that contributes to a load balancing when a route change is made, among cut-through paths for which the route change at the router device is possible; and

a route changing unit configured to change a route of said one cut-through path so as to contribute to the load balancing.

25. The router device of claim 24, further comprising:

a measurement unit configured to check a traffic amount to each of a plurality of node devices that are next hop nodes of cut-through paths from the route device at prescribed timings;

wherein the selecting unit selects said one cut-through path that satisfies a prescribed condition regarding the traffic amount when a level of imbalance among traffic amounts to said plurality of node devices exceeds a prescribed tolerable range, said one cut-through path being in a multi-path with one node device with less traffic amount as a next hop node; and

the route changing unit changes the route of said one cut-through path by changing the next hop node of said one cut-through path to another node device with more traffic amount.

26. The router device of claim 23, wherein the control unit sends a message for setting up the cut-through path to said one router, and makes an information setting necessary for utilizing the cut-through path when the cut-through path is set up.

27. A computer usable medium having computer readable program code embodied therein for causing a computer to function as a router device at which multi-path exists, the computer readable program code comprising:

first computer readable program code for causing said computer to select one router among a plurality of routers that can possibly be a next hop router so as to contribute to a load balancing, according to a whole or a prescribed part of information regarding a state of cut-through path set up in which the router device is involved, at a time of setting up a cut-through path in the multi-path;

second computer readable program code for causing said computer to carry out a prescribed control for setting up the cut-through path with said one router as the next hop router; and

third computer readable program code for causing said computer to transfer datagrams using the cut-through path,

wherein the first computer readable program code causes said computer to select said one router according to a number of already set up cut-through paths that are used to route packets to a same destination node such that numbers of cut-through paths at said plurality of routers are uniformly distributed among said plurality of routers,

wherein the first computer readable program code causes said computer to;

assign possible residue values starting from 0 that are obtainable by dividing a given integer by a total number of said plurality of routers, respectively, to said plurality of routers, one residue value per each router; and

select one of said plurality of routers which is assigned with a residue value obtained by dividing the number of already set up cut-through paths by the total number of said plurality of routers as said one router.

28. The computer readable program code of claim 27, further comprising:

fourth computer readable program code for causing said computer to select one cut-through path that contributes to a load balancing when a route change is made, among cut-through paths for which the route change at the router device is possible; and

fifth computer readable program code for causing said computer to change a route of said one cut-through path so as to contribute to the load balancing.

29. A computer usable medium having computer readable program code embodied therein for causing a computer to function as a router device at which multi-path exists, the computer readable program code comprising:

first computer readable program code for causing said computer to select one router among a plurality of routers that can possibly be a next hop router so as to contribute to a load balancing, according to a whole or a prescribed part of information regarding a state of cut-through path set up in which the router device is involved, at a time of setting up a cut-through path in the multi-path;

second computer readable program code for causing said computer to carry out a prescribed control for setting up the cut-through path with said one router as the next hop router; and

third computer readable program code for causing said computer to transfer datagrams using the cut-through path,

wherein the first computer readable program code causes said computer to select said one router according to a number of already set up cut-through paths that are used to route packets to a same destination node such that numbers of cut-through paths at said plurality of routers are evenly distributed among said plurality of routers according to link rates with respect to said plurality of routers,

wherein the first computer readable program code causes said computer to;

assign possible residue values starting from 0 that are obtainable by dividing a given integer by a total of elements constituting an integer ratio indicating or approximating a ratio of the link rates with respect to said plurality of routers, respectively to said plurality of routers, as many residues values as a number proportional to a link rate with respect to each router per each router; and

select one of said plurality of routers which is assigned with a residue value obtained by dividing the number of already set up cut-through paths by the total of the elements constituting the integer ratio as said one router.

30. The computer readable program code of claim 29, further comprising:

fourth computer readable program code for causing said computer to select one cut-through path that contributes to a load balancing when a route change is made, among cut-through paths for which the route change at the router device is possible; and

fifth computer readable program code for causing said computer to change a route of said one cut-through path so as to contribute to the load balancing.

31. A cut-through path control method at a router device at which multi-path exists, comprising:

selecting one router among a plurality of routers that can possibly be a net hop router so as to contribute to a load balancing, according to a whole or a prescribed part of information regarding a state of cut-through path set up in which the router device is involved, at a time of setting up a cut-through path in the multi-path; and

carrying out a prescribed control for setting up the cut-through path with said one router as the next hop router,

wherein the selecting step selects said one router according to a number of already set up cut-through paths that are used to route packets to a same destination node such that numbers of cut-through paths at said plurality of routers are uniformly distributed among said plurality of routers,

wherein the selecting step includes the sub-steps of;

assigning operation values obtained by carrying out a prescribed operation for possible residue values starting from 0 that re obtainable by dividing a given integer by a total number of said plurality of routers, respectively to said plurality of routers, one operation value per each router; and

selecting one of said plurality of routers which is assigned with an operation value obtained by carrying out the prescribed operation for a residue value obtained by dividing the number of already set up cut-through paths by the total number of said plurality of routers as said one router.

32. A cut-through path control method at a router device at which multi-path exists, comprising:

selecting one router among a plurality of routers that can possibly be a next hop router so as to contribute to a load balancing, according to a whole or a prescribed part of information regarding a state of cut-through path set up in which the router device is involved, at a time of setting up a cut-through path in the multi-path; and

carrying out a prescribed control for setting up the cut-through path with said one router as the next hop router,

wherein the selecting step selects said one router according to a number of already set up cut-through paths that are used to route packets to a same destination node such that numbers of cut-through paths at said plurality of routers are evenly distributed among said plurality of routers according to link rates with respect to said plurality of routers,

wherein the selecting step includes the sub-steps of;

assigning operation values obtained by carrying out a prescribed operation for possible residue values starting from 0 that are obtainable by dividing a given integer by a total of elements constituting an integer ratio indicating or approximating a ratio of the link rates with respect to said plurality of routers, respectively to said plurality of routers, as many operation values as a number proportional to a link rate with respect to each router per each router; and

selecting one of said plurality of routers which is assigned with an operation value obtained by carrying out the prescribed operation for a residue value obtained by dividing the number of already set up cut-through paths by the total of the elements, constituting the integer ratio as said one router.

33. A router device at which multi-path exists, comprising:

a processing unit configured to select one router among a plurality of routers that can possibly be a next hop router so as to contribute to a load balancing, according to a whole or a prescribed part of information regarding a state of cut-through path set up in which the router device is involved, at a time of setting up a cut-through path in the multi-path;

a control unit configured to carry out a prescribed control for setting up the cut-through path with said one router as the next hop router; and

a transfer unit configured to transfer datagrams using the cut-through path,

wherein the processing unit selects said one router according to a number of already set up cut-through paths that are used to route packets to a same destination node such that numbers of cut-through paths at said plurality of routers are uniformly distributed among said plurality of routers,

wherein the processing unit;

assigns operation values obtained by carrying out a prescribed operation for possible residue values starting from 0 that are obtainable by dividing a given integer by a total number of said plurality of routers, respectively to said plurality of routers, one operation value per each router; and

selects one of said plurality of routers which is assigned with an operation value obtained by carrying out the prescribed operation for a residue value obtained by dividing the number of already set up cut-through paths by the total number of said plurality of routers as said one router.

34. A router device at which multi-path exists, comprising:

a processing unit configured to select one router among a plurality of routers that can possibly be a next hop router so as to contribute to a load balancing, according to a whole or a prescribed part of information regarding a state of cut-through path set up in which the router device is involved, at a time of setting up a cut-through path in the multi-path;

a control unit configured to carry out a prescribed control for setting up the cut-through path with said one router as the next hop router; and

a transfer unit configured to transfer datagrams using the cut-through path,

wherein the processing unit selects said one router according to a number of already set up cut-through paths that are used to route packets to a same destination node such that the numbers of cut-through paths at said plurality of routers are evenly distributed among said plurality of routers according to link rates with respect to said plurality of routers,

wherein the processing unit;

assigns operation values obtained by carrying out a prescribed operation for possible residue values starting from 0 that are obtainable by dividing a given integer by a total of elements constituting an integer ratio indicating or approximating a ratio of the link rates with respect to said plurality of routers, respectively to said plurality of routers, as many operation values as a number proportional to a link rate with respect to each router per each route; and

selects one of said plurality of routers which is assigned with an operation value obtained by carrying out the prescribed operation for a residue value obtained by dividing the number of already set up cut-through paths by the total of the elements constituting the integer ratio as said one router.

35. A computer usable medium having computer readable program code embodied therein for causing a computer to function as a router device at which multi-path exists, the computer readable program code comprising:

first computer readable program code for causing said computer to select one router among a plurality of routers that can possible be a next hop router so as to contribute to a load balancing, according to a whole or a prescribed part of information regarding a state of cut-through path set up in which the router device is involved, at a time of setting up a cut-through path in the multi-path;

second computer readable program code for causing said computer to carry out a prescribed control for setting up the cut-through path with said one router as the next hope router; and

third computer readable program code for causing said computer to transfer datagrams using the cut-through path,

wherein the first computer readable program code causes said computer to select said one router according to a number of already set up cut-through paths that are used to route packets to a same destination node such that numbers of cut-through paths at said plurality of routers are uniformly distributed among said plurality of routers,

wherein the first computer readable program code causes said computer to;

assign operation values obtained by carrying out a prescribed operation for possible residue values starting from 0 that are obtainable by dividing a given integer by a total number of said plurality of routers, respectively to said plurality of routers, one operation value per each router; and

select one of said plurality of routers which is assigned with an operation value obtained by carrying out the prescribed operation for a residue value obtained by dividing the number of already set up cut-through paths by the total number of said plurality of routers as said one router.

36. A computer usable medium having computer readable program code embodied therein for causing a computer to function as a router device at which multi-path exists, the computer readable program code comprising:

first computer readable program code for causing said computer to select one router among a plurality of routers that can possible be a next hop router so as to contribute to a load balancing, according to a whole or a prescribed part of information regarding a state of cut-through path set up in which the router device is involved, at a time of setting up a cut-through path in the multi-path;

second computer readable program code for causing said computer to carry out a prescribed control for setting up the cut-through path with said one router as the next hop router; and

third computer readable program code for causing said computer to transfer datagrams using the cut-through path,

wherein the first computer readable program code causes said computer to select said one router according to a number of already set up cut-through paths that are used to route packet to a same destination node such that numbers of cut-through paths at said plurality of routers are evenly distributed among said plurality of routers according to link rates with respect to said plurality of routers,

wherein the first computer readable program code causes said computer to;

assign operation values obtained by carrying out a prescribed operation for possible residue values starting from 0 that are obtainable by dividing a given integer by a total of elements constituting an integer ratio indicating or approximating a ratio of the link rates with respect to said plurality of routers, respectively to said plurality of routers, as many operation values as a number proportional to a link rate with respect to each router per each router; and

select one of said plurality of routers which is assigned with an operation value obtained by carrying out the prescribed operation for a residue value obtained by dividing the number of already set up cut-through paths by the total of the elements constituting the integer ratio as said one router.