3

So I read that when a router knows two paths with equal cost to a destination it can perform load balancing. This load balancing occurs interdomain or intradomain. I can't undestand that because I know that BGP choose the "small" ip address when two paths has the same cost.

5

To answer this question, we have to define the term "domain". Easily spoken, the Internet is a network of networks. In BGP terminology, there are many Autonomous Systems (AS) on the Internet, each of them being a network (or domain). One company for example may have a very large network, but is represented by a single AS, hence is a single "node" in BGP.

The term interdomain routing describes the process of routing prefixes between Autonomous Systems, whereis intradomain routing refers to routing inside a single AS.

Im not sure however what you mean with your last sentence. When two paths to the same destination have the same cost (that is in most basic BGP the length of the AS path, hence the number of ASs the route has crossed). For detailed discussion how BGP chooses paths look for example at this Cisco document.

Update

As turned out in the comments I might have mis-interpreted the OPs question. The question actually is how load-balancing is performed and where are the differences in load-balancing in common interdomain routing protocols and intradomain routing protocols.

Interdomain Routing

BGP, being the de-facto standard for interdomain routing, will not perform load-balancing by default. It can however be configured to do so. Two main options exist here:

  1. Configuring BGP to pair using loopback interface and use some unterlying routing (for example static routing or another internal routing protocol) to provide to equal paths to the opposite side, which will effectively turn on load-balancing
  2. Using the BGP multipathing feature, which is however a little more complex. One has to consider whether load-balancing should be performed with an iBGP (internal) or eBGP (external) peer or possibly both. To be candidates for multipathing, the routes must be equal in the following attributes:
    • Weight
    • Local preference
    • AS-PATH Length
    • Origin
    • MED

You can find detailed information on BGP multipathing by searching for this keyword or having a look at this Cisco document.

Intradomain Routing

Most of the internal routing protocols support easier load-balancing. As soon as the one metric being used is equal, multiple equal costs routes can be installed into the routing table. OSPF for example by default uses up to four equal cost routes. Other routing protocols such as EIGRP can even do unequal cost multipathing. Refer to the definition of the actual routing protocol to find out their default behaviour.

Final sentence

To make on thing clear: it is up to the routing protocol whether equal paths can be used or not. In any case, if there are equal paths, both paths are installed into the local forwarding table on the router and other, not ruouting protocol specific, mechanisms such as CEF on Cisco routers are used for the actual load-balancing.

| improve this answer | |
  • I don't think it answers. I do know what domain means. I want to know how load balancing is performed since the BGP best path selection algorithm does not have anything about it. – R. Luis Jun 24 '16 at 21:14
  • 1
    Hm, maybe I misunderstood your question. BGP per-se does not perform load-balancing until configured to do so. Basically there are two options: pair between loopback interfaces and use some other underlying routing to have multiple equal paths or configure BGP to use more than one path with equal metric, in cisco terminology "maximum-paths 2". Then normal ECMP (equal cost multipathing) is performed, which is normally based on hashing mechanisms. Does this answer your question? I will edit then. – waza-ari Jun 24 '16 at 21:20
  • And for OSPF, is there any type of load balancing? – R. Luis Jun 24 '16 at 21:51
  • Short answer: yes. OSPF will do equal cost multipathing using equal routes. It is enabled by default for up to 4 equal routes. Will update my answer with more details tomorrow. – waza-ari Jun 24 '16 at 21:55
  • @R.Luis: Updated my answer, I hope it now more matches your question. – waza-ari Jun 25 '16 at 9:56
3

Two paths with equal cost is often called equal-cost multipath (ECMP) mechanism. ECMP often works well, but there are a few caveats. Before you get to the issue of running BGP over parallel links, it’s important to look at how traffic is split over multiple parallel links.

The simplest way to do this is transmit packet 1 over link A, packet 2 over link B, packet 3 over link A again, packet 4 over link B, and so on. This is per-packet load balancing. The problem with per-packet load balancing is that when packets 1, 3, and 4 are 1500-byte data packets that belong to the same TCP session, but packet 2 is a small TCP ACK packet, packet 3 has to wait for packet 1 to be transmitted, but packet 4 doesn’t have to wait nearly as long behind the much shorter packet 2, so packet 4 ends up being transmitted before packet 3.

So per-packet load balancing causes reordering. In theory, that’s fine, as TCP will simply buffer the reordered packets and deliver the data inside to the receiving application in the right order. However, receiving packets out of order makes TCP think there was packet loss, so it retransmits packets and slows down its transmission rate. To avoid such issues, routers and switches work hard to make sure that all packets that belong to the same TCP session (or UDP flow) are transmitted over the same link. Of course this in turn has the downside that a single TCP session can only make use of one link; thus ECMP is only useful if the traffic consists of multiple TCP sessions.

Routers and switches usually aren’t in the position to keep track of individual TCP sessions so their packets can be transmitted over the same link. Instead, they look at a few fields in the IP/TCP/UDP/ICMP header and group packets together based on the contents of those fields. Some switches can’t even look inside the IP header, and thus perform load balancing based on the Ethernet MAC addresses. That doesn’t work so well, because this way all the traffic between two routers is transmitted over the same link.

A more granular way to perform load balancing is based on the 3-tuple: the protocol number in the IP header (i.e., TCP, UDP, ICMP, …) and the IP source and destination addresses. This works better than just using the MAC addresses to determine which packets should be transmitted over the same link. The best way to perform ECMP is using the 5-tuple: the protocol number, the IP addresses and the TCP or UDP source and destination port numbers. Routers and switches implementing ECMP calculate a hash function over these fields and then use (part of) the resulting hash value to select the link to transmit the packet over. (See RFC 2992) As the fields in the 5-tuple are the same for all packets belonging to the same session and thus the hash is the same, all packets belonging to the same session end up using the same link. This works well, but in practice, it can still take as many as a thousand TCP sessions before all the links are utilized equally.

Before the ECMP algorithm can distribute packets over parallel links, routing protocols such as BGP must first be convinced to use multiple links in parallel. There are three ways BGP and ECMP can work together:

  • Bundling the links at the Ethernet level, using IEEE 802.3ad or EtherChannel
  • With one BGP session over multiple links using loopback addresses
  • With a separate BGP session over each of the parallel links

For load balancing to happen, the following path attributes need to be the same for the prefixes learned over the parallel BGP sessions:

  • weight
  • local preference
  • AS path length
  • origin
  • MED

the neighbor AS or the entire AS path (depending on IOS version) Using a separate BGP session for each of the parallel links uses more memory and CPU cycles, so in general this is not the preferred option. However, this option does have an important benefit: unlike the two other options, this one also works if the links connect to different routers on the other side, as long as the attributes listed above are the same.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.