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 (google.com) 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.
Eg:
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.
Eg:
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.
Eg:
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.
Eg:
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.
Eg:
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.
Eg:
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.
Eg:
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.
Eg:
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.

Script To Convert cd's to Dvd

#!/bin/bash
# convert cd's into single DVD
#

#functions

iso_fn () {
disc
cp -r /tmp/cd1/.discinfo /tmp/isoimage
OUT=`cat /tmp/stdout1 | grep 1`
sed '4s/1/'$OUT'/g' /tmp/isoimage/.discinfo > /tmp/stdout2
mv -f /tmp/stdout2 /tmp/isoimage/.discinfo
cd /tmp/isoimage

echo " Enter the label for DVD"
read name
echo " Enter the name & location to store the image example /DVD1.iso"
read locate
mkisofs -v -r -T -J -V "$name" -b isolinux/isolinux.bin -c isolinux/boot.cat -no-emul-boot \
-boot-load-size 4 -boot-info-table -o "$locate" /tmp/isoimage
echo " successfuly completed now burn the "$locate" image into DVD"
echo " Do you want to create another image [y/n]"
read -n 1 CH
if [ "$CH" -eq "y" ]; then clean ;. testlap2.sh; else echo " Try later"; fi
cd $OLDPWD
}

clean () {
umount /tmp/cd* 2> /dev/null
rm -rf /tmp/isoimage /tmp/cd* 2> /dev/null
}

disc () {

echo > /tmp/stdout1 2> /dev/null
while [ "$J" -le "$C" ]
do
if [ "$J" -eq "$C" ]; then printf "$J" >> /tmp/stdout1 ; else printf "$J," >> /tmp/stdout1; fi
let "J +=1"
done

}

sync_fn () {

E=$D
while [ "$E" -ge "$J" ]
do
rsync -rv /tmp/cd"$E"/* /tmp/isoimage
let "E -=1"
done
iso_fn
}

#starting from here
#declaration
I=1
J=1
echo " Give the appropriate source you have "
echo " 1.cdrom 2.iso images 3.clean"
read NUM
mkdir -p /tmp/isoimage
rm -rf /tmp/cd* 2>/dev/null
case $NUM in

1)echo " Enter total no of cds"
read C

while [ "$I" -le "$C" ]
do
mkdir -p /tmp/cd$I
echo " Insert the $I cd "
eject && sleep 20 && eject -t && \
dd if=/dev/cdrom of=/tmp/cd"$I".iso && \
mount -o,loop /tmp/cd"$I".iso /tmp/cd"$I" && \
let "I += 1"
done
sync_fn
;;

2)echo " Enter the total no of isoimages"
read C
D=$C
while [ "$I" -le "$C" ]
do
mkdir -p /tmp/cd$I
echo " Give the path for isoimage $I for example /misc/cd$I.iso "
read SPATH
mount -o,loop "$SPATH" /tmp/cd"$I"
let "I +=1"
done
sync_fn
;;

3)
clean
clear
echo "cleaned"
. testlap2.sh
;;

*)echo " you have pressed invalid key"
#2> /dev/null
;;

esac

Follow up to "Hardy Heron..... Ubuntu's latest!"

Adding two more to the Ugly things in Hardy....

1. If the network cable is not plugged in, while start up the corresponding ethernet drivers for wired network
is not loaded. When i manually modprode it, i still don't see a eth0 interface and dmesg doesn't give any error!!

2. Suddenly, after the recent updates the sound stopped working and kmix started cribbing.
I realized that the snd-hda-intel ( sound driver for intel chipsets) was not loaded.
I had to manually modprobe it in.

This surely bad and takes Ubuntu away from being user friendly. I wonder if a naive user would be able to figure out the problem ..

Hardy Heron ... Ubuntu's latest !

I installed Ubuntu latest LTS (Long Term Support) release Hardy Heron on my Thinkpad T60p. I have heard/read a lot of good, bad and ugly things about Hardy.

Here's mine.

The Good

Installation goes smooth. This is something the Ubuntu folks have mastered.
Wireless, Suspend to Ram and Hibernate work out of the box.
Earlier neither of these worked for my T60p with Atheros Wireless Card and ATI Graphics Card.
I guess the drivers improved with the kernel that shipped with Hardy.
But can't take the credit away from Ubuntu for proper packaging.
This is another thing that Ubuntu does really well.

The Bad

Why is a beta version of Firefox 3 shipped with a LTS version? Ok, the updates install the GA version of Firefox.
The only reason i see is that they expected Firefox 3 would be released very soon and a upgrade would be easier.
Seems reasonable ? For a naive Desktop user (their potential market) can't say so!
The beta version of Firefox 3 crash abruptly and / or consumes a lot of CPU and becomes slow.

$sudo apt-get install kde
This command doesn't install all essential components for kde to be setup right like knetworkmanager, dolphin, kaffeine etc.
I had to do a
$sudo apt-cache search kubuntu | sudo apt-get install -y

Is Ubuntu at fault or kde or the way the repos are organized ?

The Ugly

When i put the lid of the laptop down and lift it up, the entire gui screen get borked. The redrawing mechanism seems to be the culprit. When i switch to a another terminal and back, the gui screen comes to normal.
It took a while for me to realize this. I just kept killing the X session.


Final verdict: The Good features (which i desperately wanted) win over the rest and i am happy [:)]