North American Network Operators Group

Date Prev | Date Next | Date Index | Thread Index | Author Index | Historical

Re: Load balancing in routers

  • From: Richard A Steenbergen
  • Date: Sun Apr 07 18:54:13 2002

On Sun, Apr 07, 2002 at 02:38:46PM -0700, abhijit bare wrote:
> 
> Does anybody know what are load balancing algorithms
> by most routers ? Where can I more information about
> this ?

That is somewhat of a vague question, but lets see here... The first
question is at what layer the load balancing is going to happen, which is
basically either layer 2, layer 3, or "other".

Layer 2 switches (and routers using multiple layer 2 circuits) do a form
of load balancing based on the MAC address of the sender and receiver.  
Probably the versions most people are famialer with is Cisco EtherChannel,
or IEEE 802.3ad. A single virtual port is presented to the world, composed
of multiple physical "member" ports. The actual forwarding of the frames
is determined by a relatively simple hash on the src and dst MAC addresses
which aims to keep a "flow" of frames between any given stations on the
same physical port, to prevent frame reordering and other such nastiness.  
While the aggregate bandwidth across such a trunk may be that of multiple
physical links, the bandwidth of any given src/dst flow is limited to a
single physical link. Usually the hash is admin configurable because of
the nature of load balancing on layer 2 addresses. For example, if you had
1 router with 2 ports to a switch, and 2 devices hanging off that switch,
transmitting to the 1 router, without an admin configurable hash it is
quite possible to end up with all "flows" on a single link. Failure
recovery is usually configurable too, if 1 link in a bundle of 8 goes
down, you can either drop 1/8th of your packets, move the traffic from
that 1 interface to only 1 other interface, or change your hash algorithm
and redistribute all traffic evenly among all interfaces. Unless
explicitly configured, most layer 2 devices will not have multiple
simultanious forwarding paths due to the possability of a loop.

Layer 3 devices usually do a form a load balancing called "equal cost" 
forwarding. If you have two routes to a single prefix (say you have two 
physical links), and both have the same routing "cost", packets may be 
load balanced across those links. Some mechanisms (for example Cisco CEF) 
can do this on a per-destination (flow-based) basis, to prevent packet 
reordering. But some protocols can't support this, for example UDP or ICMP 
traceroutes usually don't get grouped into a "flow", so you can see this 
kind of load balancing in practice on the internet when you get back 
traceroute answers from different probes on the same hop.

"Other" layer devices, such as layer 4-7 load balancers (which only
loosely fit under the definition of "router") may have other algorithms,
such as round robin, or least weighted. In order to do more advanced
things, such as non-equal capacity load balancing, you need to have
knowledge of the "load" on a link (or the servers in the case of 4-7 load
balancers). This is something that "routers" have typically avoided, and 
I'm not aware of any router vendors who attempt to do load balancing based 
on the load of a link.

Did you have any more specific questions?

-- 
Richard A Steenbergen <[email protected]>       http://www.e-gerbil.net/ras
PGP Key ID: 0x138EA177  (67 29 D7 BC E8 18 3E DA  B2 46 B3 D8 14 36 FE B6)