[nsp] ip load-sharing per-packet - cef accelerated ?

[Chris Whyte]

Yes, I thought it used to be on CCO too. I also remember there being
more algorithm options at the time of the writing but my memory is
sometimes fuzzy. It's quite possible there have been changes (removed
options) since then too. It's also very possible that Neil's doc was an
internal-only one. Lastly, I don't think a lot of people have a good
grasp on the polarization issue. But then maybe I'm wrong. Anyway, I've
pasted a copy of the explanation below for those who care.

Btw, that's the right ddts but the description (via CCO) appears to be
lacking.

Thanks,

Chris

**********************

The problem
-----------

When per-destination load balancing is used in a network where paths
traverse different routers (a divergent network), traffic is not load
balanced after the initial hop.

                 R21
                /   \
             R11     \
            /   \     |
           /     R22  |
          /         \ |
     --R01           R31--
          \         / |
           \     R23  |
            \   /     |
             R12     /
                \   /
                 R24

   Figure 1: Divergent network

Consider the network in figure 1.  In this network, per-destination
load balancing is enabled in routers R01, R11 and R12.  Load balancing
is not employed in routers R21, R22, R23, R24 and R31.  Traffic
arriving at router R01 will be load balanced 50%/50% across links
R01:R11 and R01:R12.  Using the existing implementation of
per-destination load balancing, the traffic arriving at router R11
from R01 will be split 100%/0% between links R11:R21 and R11:R22.  The
traffic arriving at router R12 from R01 will be split 0%/100% between
links R12:R23 and R12:R24.

Analysis
--------

Per-destination load balancing works by hashing the source and
destination IP addresses of packets, and distributing the result
across the number of paths for the destination IP address:

   path = h(ipSrc, ipDst, pathCount)

For a given ipSrc, ipDst, and pathCount, the hash algorithm will
always produce the same path.  

Refering to figure 1, non-biased traffic (defined to be traffic that
has never been load balanced) arriving at R01 will be split 50/50
between links R01:R11 and R01:R12 by this hash algorithm.

Because we know that all the traffic on link R01:R11 was the result of
the hash algorithm choosing the first path out of a possible two
paths, the same hash algorithm in router R11 will put all this traffic
out on first path out of a possible two paths from router R11,
i.e. path R11:R21.  This results in a 100%/0% split of traffic leaving
router R11.  Conversely, router R12 will split the traffic 0%/100%,
since the traffic arriving at router R12 picks the second path of two
possible paths.

A nice way to think about this is in terms of polarising filters.
When the traffic is received at router R01, the load balancing
algorithm will split and polarise the traffic.  The polarised traffic
arriving at router R11 goes through the same filter, so all the
traffic will go to router R21.

A more complex example
----------------------

The question has been raised as to why this failure to load balance
traffic is not seen more often in the field.  There are a couple of
answers.  First, the algorithm only fails in a divergent network.  The
network in figure 2 shows equal load balancing on all three links
between R01 and R11 and between R11 and R21.  This network
architecture is most often thought about when envisaging load
balancing.

         /-------\     /-------\    
        /         \   /         \   
     R01-----------R11-----------R21
        \         /   \         /   
         \-------/     \-------/    

   Figure 3: Non-divergent network

Secondly, real divergent networks are more complex.  Consider the
network shown in figure 3.

                 R21
                /   \
             R11     \
            /   \     |
           /     R22  |
          /         \ |
    A--R01           R31--B
          \         / |
           \     R23  |
            \   /     |
             R12     /
            /   \   /
           /     R24
          /
    C--R02
          \         
           \     R25
            \   /   
             R13    
                \   
                 R26
    
   Figure 3: Complex divergent network

Looking at the traffic splits, there is a 50%/50% split at R01 and R02
from traffic sources at A and C.  At R12, the R01 traffic will be
split 0%/100% and the R02 traffic will be split 100%/0%.  The
aggregate of traffic out of R12 is therefore 100%(R01)/100%(R02).  

However, the load balancing problem can still be seen when you
consider the bandwidth of traffic.  If A generates 40Mbit/s of traffic
at R01, and C generates 80Mbit/s of traffic at R02, link R12:R23 will
see 40Mbit/s and link R12:R24 will see 20Mbit/s, or a 66%/33% load
balance split at R12.

*********************************



> -----Original Message-----
> From: Sean Crocker [mailto:crockers at mail.trinicom.com] 
> Sent: Wednesday, March 12, 2003 5:22 AM
> To: Tony Tauber; Jared Mauch; Chris Whyte
> Cc: cisco-nsp at puck.nether.net
> Subject: RE: [nsp] ip load-sharing per-packet - cef accelerated ?
> 
> 
> I could swear that doc was freely available on CCO, but cannot find
> it.  CSCdm87756 is the bug.  I suppose people would have to ask their
> account teams about details if they don't already know, although the
> nature of the problem is simple enough to describe.
> 
> Sean
> 
> >I used to have an excellent ip cef LB doc (written by Neil J) that
> >described every option and the potential problem it solved.
> >Unfortunately, I can't seem to locate it. I believe it's 
> also documented
> >in a DDTS. Maybe someone from cisco will chime in since I 
> highly suspect
> >they know what doc I'm referring to. :-) Of course, it might also be
> >outdated by now...
>