US 7,009,987 B1 · Router device and cut-through path control method for realizing load balancing at intermediate routers

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.

Claims36

Dependent claims

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.

5 more elements

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.

5 more elements

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.

6 more elements

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.

6 more elements

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.

6 more elements

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.

6 more elements

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.

6 more elements

Dependencies are inferred from the claim text.

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

Life of this patent

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

Life of this patent

Abstract

Claims36