CCIE 400-101: Network Principles - CEF Load Balancing and Polarization

on

Overview

  • Cisco IOS software supports two modes of load balancing: per-destination or per-packet. 
  • In per-destination mode, all packets for a given path are forwarded along the same path. This preserves packet order but might utilize the links unequally.
  • Per-packet load balancing guarantees equal utilization across all links but packets may arrive out of order and different delay may occur. 

CEF Load Balancing Algorithms

  • For per-destination load balancing, the router computes a hash out of the source and destination IP addresses. This hash points to exactly one of the entries in the adjacency table. 
  • If per-packet load balancing is used, the packets are distributed round robin over the available paths. 
  • Per-destination load balancing is enabled by default with CEF. 
  • Per-destination load balancing is the method of choice in most situations. 
  • Use per-packet load-balancing only between a single source-destination host pair to ensure equal link usage. 
  • The CEF load balancing algorithm is selected with the ip cef load-sharing algorithm command. 
  • Original algorithm: uses the same algorithm on every router and causes CEF polarization. 
  • Universal algorithm: allows each router to make a different decision for each source-destination address pair, which resolves load sharing imbalances. The default. 
  • Tunnel algorithm: designed to balance the per-packet load when only a few source and destination pairs are involved. 
  • Include-ports algorithm: uses the Layer 4 source and destination ports as part of the load balancing decision.

CEF Load Balancing Internal Mechanics

  • The CEF table points to 16 hash buckets, which point to the adjacency table for parallel paths.
  • Active paths are assigned internally to the 16 hash buckets. The path-to-bucket assignment varies with the type of load balancing and the number of active paths.
  • The 16 buckets are evenly filled with the active paths. If 16 isn't divisible by the number of active paths, the last few buckets that represent the remainder are disabled. 
  • The result of the hash function is used to pick one of the enabled buckets, and thus which path to use for the traffic flow.
  • Example: The hash buckets for two and three active paths. With three links (16 is not divisible by 3), the last bucket is disabled.



The following output shows the hash bucket assignments when two active paths are available.
RouterB#show ip cef  192.168.20.0 internal 
 192.168.20.0/24, version 66, per-destination sharing 
0 packets, 0 bytes 
  via 20.20.20.1, Serial2, 0 dependencies 
    traffic share 1 
    next hop 20.20.20.1, Serial2 
    valid adjacency 
  via 30.30.30.1, Serial3, 0 dependencies 
    traffic share 1 
    next hop 30.30.30.1, Serial3 
    valid adjacency 
  0 packets, 0 bytes switched through the prefix 
  Load distribution: 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 (refcount 1)

 The following output shows the hash bucket assignments when three active paths are available.
RouterB#show ip cef  192.168.20.0 interface 
 192.168.20.0/24, version 64, per-destination sharing 
0 packets, 0 bytes 
  via 20.20.20.1, Serial2, 0 dependencies 
    traffic share 1 
    next hop 20.20.20.1, Serial2 
    valid adjacency 
  via 30.30.30.1, Serial3, 0 dependencies 
    traffic share 1 
    next hop 30.30.30.1, Serial3 
    valid adjacency 
  via 10.10.10.1, Serial1, 0 dependencies 
    traffic share 1 
    next hop 10.10.10.1, Serial1 
    valid adjacency 

  0 packets, 0 bytes switched through the prefix 
  Load distribution: 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 (refcount 1) 
 

CEF Polarization

  • In short, CEF polarization refers to the utilization of a single ECMP link due to the use of the same hash algorithm and the same hash input. 
  • When there are two paths available, the router performs exclusive OR (XOR) operation on the lower-order bits of the source IP (SIP) and destination IP (DIP). 
  • Consider the graph below. Say hosts behind R1 want to reach R6's directly connected network 6.6.6.6/32. Traffic flows, whose hash result in 0, traverse through R2. Similarly, if the hash is equal to 1, packets are sent to R3. Now, if the routers use the same hash algorithm and the same hash input, the result will always be 1 for traffic that arrived on R3 from R1. Therefore, the equal-cost path through R4 will remain unused (the hash result is never 0). 



 Avoiding CEF Polarization

  1. Alternate between default (SIP+DIP) and full (SIP+DIP+Layer 4 ports) hashing input configuration at each layer of the network.
  2. Alternate between an even and odd number of ECMP links at each layer of the network.
  3. Use the unique-ID/universal-ID. The hash function is seeded with a 32-bit randomly generated, router-specific value, which ensures that the same source/destination pair hash into a different value on different routers along the path.

Comments

Post a Comment