Exit Zen
50
../../protocols/routing.rst:158
English
To efficiently spread the load over different paths, routers need to implement `per-flow` load-balancing. This implies that they must forward all the packets that belong to the same flow on the same path. Since a TCP connection is always identified by the four-tuple (source and destination addresses, source and destination ports), one possibility would be to select an outgoing interface upon arrival of the first packet of the flow and store this decision in the router's memory. Unfortunately, such a solution does not scale since the required memory grows with the number of TCP connections that pass through the router.
0/6250 · 625
51
../../protocols/routing.rst:160
English
Fortunately, it is possible to perform `per-flow` load balancing without maintaining any state on the router. Most routers today use hash functions for this purpose :rfc:`2991`. When a packet arrives, the router extracts the Next Header information and the four-tuple from the packet and computes :
0/2980 · 298
52
../../protocols/routing.rst:162
English
:math:`hash(NextHeader,IP_{src},IP_{dst},Port_{src},Port_{dst}) \pmod{N}`
0/730 · 73
53
../../protocols/routing.rst:164
English
In this formula, `N` is the number of outgoing interfaces on the equal cost paths towards the packet's destination. Various hash functions are possible, including CRC, checksum or MD5 :rfc:`2991`. Since the hash function is computed over the four-tuple, the same hash value will be computed for all packets belonging to the same flow. This prevents reordering due to load balancing inside the network. Most routers support this kind of load-balancing today [ACO+2006]_.
0/4700 · 470
54
../../protocols/routing.rst:169
English
Footnotes
0/100 · 9
55
../../protocols/routing.rst:170
English
See http://bgp.potaroo.net/index-as.html for reports on the evolution of the number of Autonomous Systems over time.
0/1160 · 116
56
../../protocols/routing.rst:173
English
OSPF can support `virtual links` to connect routers together that belong to the same area but are not directly connected. However, this goes beyond this introduction to OSPF.
0/1740 · 174
57
../../protocols/routing.rst:175
English
The OSPF Designated Router election procedure is defined in :rfc:`2328`. Each router can be configured with a router priority that influences the election process since the router with the highest priority is preferred when an election is run.
0/2430 · 243
58
../../protocols/routing.rst:178
English
In some networks, there are several dozens of paths towards a given destination. Some routers, due to hardware limitations, cannot install more than 8 or 16 paths in their forwarding table. In this case, a subset of the computed paths is installed in the forwarding table.
0/2720 · 272
The translation has come to an end.