Saturday, July 26, 2008

Default Address Selection Part 2

Finally i was able to find time to finish off the long awaited squeal. In this article i would like to give an insight into kernel algorithm implementation of the same. The diagrams in this article are personally drawn by me using primitive tools :-). Please ignore the poor quality.

So before we proceed i would like to alert the readers that i would not be covering the full address selection algorithm. The Default Address Selection is mainly divided into

  • Source Address Selection (kernel)
  • Destination Address Selection (glibc - getaddrinfo())

This article will mainly concentrates on source address selection done in the kernel. So we will assume that destination address selection is already done and we will concentrate on source address selection. The picture below shows a very broad flow diagram of destination address selection.

From the flow chart it is clear that destination address selection is done using glibc. The reason for this is the fact that an application must decide on destination address before it hits the network stack. For example, a browser (app) can either connect via an ip address or via a internet address ( which has to be resolved using DNS. If its the later case then there are chances that DNS request can return multiple ip addresses. If this is the case then sorting will have to be done in the dns resolution call. Once the destination address is selected the "packet framing" request hits the kernel as shown in the flow chart. The kernel then looks up the route table (forward information base [FIB]) to figure out the route to the destination address. If there is no valid entry in the table, an error is returned to the calling application stating "No Route To Host". If we hit the bullseye in the route lookup, then the kernel needs to find appropriate source address. This is done in the call fib6_rule_action(). This ends the destination address selection part.

Source Address Selection Algorithm:

In the function fib6_rule_action( ), the source address lookup function ipv6_get_saddr( ) is called. It is at this stage we start analysing the algorithm. The flow chart shown below explains the code flow.

As seen, the flow chart is divided into two small parts to make explaination easier. The algorithm starts off with initializations for type, scope and label of destination address. This is required to compare the value against the equivalent value of candidate source address. The candidate source address list refers to all the ipv6 address across all the interfaces of the system.

We now have a source address set, and from this list the correct source address has to be finalized. A scoring machanism is maintained for each address to finially pick the winner. The address with highest score will become the chosen candidate. The scores are made based on passing each rule. Each rules as per the order is explained below. Remember, as we pass on from each rule, we keep droping candidates from the candidate set, so as to eventually arrive at the right source address.

Rule 0: Localize source candidate set for destination address which is link/site-local.
This means if the destination address is either a linklocal or a site local address, then the source address must be selected from the same link as the outgoing interface. This reduces the posibility of any global address being assigned as source address for a destination address that is linklocal.

Rule 1: Prefer Same Address. If the source address is equal to the destination address, select that address as the preferred address.
SA: 2001::1
SB: 2001::2
Dest Address : 2001::1
Select: 2001::1

Rule 2: Prefer Same Scope. Select the source address with higer scope than the destination address.
If Scope(SA) < Scope(SB) : If Scope(SA) < Scope(D), prefer SB

Rule 3: Avoid Deprecated Address. In a group of 2 candidate source address with equal scope, one is found to be deprecated, avoid that address.
Src Address 1 : 2001::1
Src Address 2 : 2001::2 (deprecated)
Select :: 2001::1

Rule 4:
Prefer Home Address. If a candidate source address SA1 is both home and care-of address, prefer that to a candidate source address SA2 which is only a care-of address. On the other hand if SA1 is a home address and SA2 a care-of address then prefer SA1. In other words home address is given higher priority. I have not tested this case as i dont have mobile ipv6 support enabled in my kernel. Thats the reason ill skip the example in this case. If anyone has tested this let me know :-).

Rule 5: Prefer Outgoing Interface. This rule is petty straightforward. If the outgoing interface used to send to the destination address is known, the source address selection candidates must belong only to that interface. If SA is from interface eth0 and SB is from interface eth1, and the interface used to send packets to destination is eth0, then prefer SA. If the interface has multiple suitable candidates the move on the next rule.
eth0: 2001::1 eth1: 2001::2 ;
Dest : eth0: 2002::5
Select : 2001::1

Rule 6:
Prefer Label. This rule selects the source address from the candidate set based on label value. A user defined label table is maintained in the kernel via netlink to match the values. The label value of the destination address must match the label value of any of the source address candidates. If there is a match then source address is selected else the candidate set is passed on to the next rule. The label values can be modified and set as desired by the administrator using "ip" command.
Label Table:
SrcA 2001::1 3
SrcB 2001::2 4
SrcC 2001::3 5
Dest fec0::3 4
Select : 2001::2

Rule 7:
Prefer Public Address. This rule is also pretty straightforward. If SA is a public address and SB is temporary address, prefer SA. This is irrespective of the destination. The RFC states that an API must be provided to reverse this preference by the application. At the time of writing this article no such API is present in linux.
SA fec0::1 configured by "ip -6 addr add fec0::1 dev eth0"
SB fec0::2 configured by radvd (temporary address)
Select: fec0::1

Rule 8: Prefer Longest Matching Prefix.
The last rule is to match the longest prefix as possible. This is the last resort to single down the source address. From the list of source addresses the prefix matching is done to see which source has the longest prefix value similar to the destination.
SA: 2001:3fff:2e33:6fff::1
SB: 2001:3fff:2e33:23ff::2
Dest: 2001:3fff:2e33:23ff::3
Select: 2001:3fff:2e33:23ff::2

After all the rules are passed and still a candidate source could not be selected then linux basically picks up the last address registered among the final list of potential source address list.

SA: 2001::1
SB: 2001::2
SC: 2001::3
Select: 2001::3

NOTE: Multiple usages of SA, SB... and Src A, Dest/D refers to Source Address A/B and Destination address. Excuse me for using these representations without informing.

No comments: