Bootstrap Router Hash Function
RFC 7761 describes a hash function used to load balance multicast groups between Rendezvous Point (RP) candidates when you are using Bootstrap Router (BSR). The hash function isn’t straight forward and I was unable to find a resource that described it in detail. One feature of the hash function is an adjustable hash mask length. I think it’s important to understand what the function does and how adjusting the mask impacts RP selection. I do my best to describe it here and provide some resources to help you select the best hash mask length for your environment.
The Hash Function #
The RFC describes the function as follows:
Value(G,M,C(i))=(1103515245 * ((1103515245 * (G&M)+12345) XOR C(i)) + 12345) mod 2^31
Where C(i) is the RP address, M is a hash-mask and G is the multicast group address. The RFC goes on to state that for non-IPv4 networks, a derivation function should be used to make C(i), M and G 32-bit values. While not stated explicitly in the RFC, this seems to imply all values used in the function and the result of the function should be unsigned 32-bit integers. When I implemented the function in python I found this to be the case.
Note that in this function, the only value that changes on a per RP basis is the Group. Since we are ANDing the group with a mask, the hash value stays the same for n groups in a row, where n=232 - Mask Length. To illustrate this, let’s consider the following:
G = 239.1.1.1
M = 30
| Value | Byte 0 | Byte 1 | Byte 2 | Byte 3 | Operation |
|---|---|---|---|---|---|
G | 1110 1111 | 0000 0001 | 0000 0001 | 0000 0001 | |
M | 1111 1111 | 1111 1111 | 1111 1111 | 1111 1100 | AND |
| Result | 1110 1111 | 0000 0001 | 0000 0001 | 0000 0000 |
Notice that the AND operation unsets the least significant bit. With a mask length of 30, the two least significant bits will be unset by the operation. This means 239.1.1.0, 239.1.1.1, 239.1.1.2 and 239.1.1.3 will all hash to the same value. To drive the point home, let’s look at another:
G = 239.7.7.7
M = 31
| Value | Byte 0 | Byte 1 | Byte 2 | Byte 3 | Operation |
|---|---|---|---|---|---|
G | 1110 1111 | 0000 0111 | 0000 0111 | 0000 0111 | |
M | 1111 1111 | 1111 1111 | 1111 1111 | 1111 1110 | AND |
| Result | 1110 1111 | 0000 0100 | 0000 0100 | 0000 0110 |
Here we used a mask length of 31, which causes only the least significant bit to be unset. In this case 239.7.7.6 and 239.7.7.7 will hash to the same value for a given RP.
Selecting a Hash Mask Length #
So, what does the above mean for our hash mask length selection? When you have multiple RPs, each RP will be selected at a minimum 232 - Mask Length times in a row. RFC 7761 recommends a length of 30 for IPv4 and 126 for IPv6, but doesn’t really expand on why. It seems arbitrary, except both result in four groups in a row hashing to the same value for each RP. This is fine if you have more than four multicast groups behind a group of RPs or your group addresses aren’t consecutive. Otherwise, a different mask length might make sense.
It should also be noted that even though only four groups in a row hash to the same value, the same RP can win more times in a row. The winning streak will always be in multiples of 232 - Mask Length. Depending on your luck, your group addresses could lie in a winning streak for on of your RPs. If this happens, it’s probably a good idea to try a shorter mask length as there will be more chances for a different RP to win.
In a recent deployment, I found that a length of 31 led to the best results. What length works for you will vary with the number of RPs you have, your multicast groups and your RP addresses. Since the algorithm is psuedo-random, but predictable I recommend playing around with hash lengths to figure out what works for your addressing scheme. You can do so here.
Using Python to Calculate and Analyze Hash Values #
I thought it would be interesting to look at the distribution of winning RPs with various mask lengths, RP values and number of RPs in order to get a feel for how changing masks affects RP selection.
I stress that this was done as a cursory check and that different RP addresses would yield slightly different results. Like I said before, I recommend playing around with the hash calculator to find what works best for you.
Note: At the bottom of each of the results is something I’m calling a win map. I’ve truncated the win map and placed a link to the full results below the output. The win map is a 256 character wide map where a digit represents which candidate RP would’ve been selected for each group. The map is ordered left to right, where the far left is the group with 0 in the last octet of it’s address. Since we are spanning an entire /8, each win map is 16777216 lines long.
I may play with this a bit more in the future. If I do, I’ll add additional results here.
Two RPs per Group #
RPs: 10.0.0.1, 10.0.0.2
Group Range: 239.0.0.0-239.255.255.255
Hash Mask of 30 #
max streak 20
TOTAL WINS
rp wins
10.0.0.1 9086396
10.0.0.2 7690820
1111000000001111111100000000111111111111000000001111000011111111111111110000000011110000000011111111000000000000111111110000111100000000000000001111111100000000000000000000111111111111000000001111000000001111000011110000000011110000111100001111000000000000
1111111100001111111100001111000011111111000000000000111100000000111111110000000011110000000011110000111111110000111100001111000000001111000000001111000000001111111100001111000000001111000011110000111100000000111111110000000011111111000011110000000011110000
1111000000000000000011110000000011110000000000001111111100001111000011110000111111110000111100000000111100001111111111110000000000001111111100001111000000000000000011111111000000000000000000001111111100000000000011110000111111110000000000000000111100001111
0000000000000000111111111111000011111111000011110000111111110000111100001111000000001111000000000000111100000000111100000000111100001111000011110000000011110000000011110000000011111111000000001111000011110000111100000000111100001111111100001111111100000000
1111000000001111000011110000000011110000111100000000111100000000000011111111000011110000000000001111111100000000000011111111000011111111000000000000111111111111000011110000000011110000111111110000111100000000111111111111000000000000111100001111111100000000
0000000011110000111111110000000000001111111100000000111111110000111111111111111100001111000000001111000011110000000011111111000000001111111100000000000011110000111111110000111100000000111100000000111111110000000011110000000000001111000000001111000011111111
0000111111110000000011111111000000001111111100001111111100001111000000001111000000001111111100000000111100000000000011111111000000000000111111110000111111110000000000001111000000001111111100000000111111111111000000001111000000001111111111110000000011110000
0000111111110000000000000000111100001111111100000000000011111111000000001111000000001111111111110000000011110000000011111111111100000000111111110000000011111111000000001111111100001111111100001111000011111111000000001111111100000000111100000000000011110000
0000111100001111111100001111111100000000111111110000000011111111000011111111000011110000000011110000000000001111000000001111111100000000111111110000111100001111111100001111111100000000000011110000000011111111000000001111111111110000000011110000000011111111
1111000000001111000000001111111100000000000011111111000011110000000000000000111111110000000011110000000011111111111100000000111100001111111111111111000000001111111100000000111100000000000011111111000011111111000011110000111111110000000000001111000000001111
Hash Mask of 31 #
max streak 18
TOTAL WINS
rp wins
10.0.0.1 8621200
10.0.0.2 8156016
1111001100001100110000110011110011111111000000001100001111111100111111110000000011110011001111111100001100000000111111110011110000000011001100001111111100000000000000110011110011111111000000001100001100111100000011110011000011110011111100001100001100000000
1111110000111100110000111111000011001111001100000000111100110000111111110000001111000000001111000000111111110000110000111111000000001111000000001111000000111111110000111111000000001111001111000000111100110000110011110000001111001100001111000000001111110000
1100001100110000000011110011000011000000001100111100111100111100000011000011110011000011111100000000111100111111110011000011000000001111111100111100000000110000000011111111000000000000001100111100111100110000000011000011111111000000001100110000111100111111
0000000000110000110011111111001111001100001111110000110011110011110000001111001100001111001100000011110000110011110000000011111100001100001111110000000011110000000011110000001111111100001100111111000011110011110000000011111100001111111100001111110000000011
1100001100111111000011000011001111000000111100110000111100000011001111001111000011000000000000111100110000110011000011001111001111111100000000110000111111111111001111000000001111000011111111110000110000000011111111001111000000000000110000111111110000000000
0000000011110011111111000000001100001100111100110011110011000011111111111100111100001100001100111111000011110011000011111100001100111100111100000011000011000011110011000000111100000000111100000011111111000011000011110000001100111100000000111111000011111111
0000111111110000001111001111000000111111110000111111110000111111001100001111000000001111110000110000110000000000001111001100001100000000110011110011111111110000001100001111001100001111110000110011110011111111001100001100001100111111110011110000000011110000
0011111111000011000000000000111100111100110000000011000011111111000000111100000000111100111111000000000011000011001111111100111100110000111111110011001111001111000000111111110000111100110000001111000011001111000000001100110000110000111100110000001111000000
0011110000001111111100001111111100000011110011110000000011111100001111111100001111110000000011110011000000111100001100001100111100000011110011000011110000001111111100001100111100000000000011110011000011111100001100111100111111110000000011000011000011111111
1111000000001111001100111111110000110000000011111111001111000000001100110000111111110000000011000000001111001111111100000000110000111111110011001111001100001111111100110011110000110000000011111111001111001100001111110000110011110011000000001111001100001111
Hash Mask of 32 #
max streak 13
TOTAL WINS
rp wins
10.0.0.1 8388600
10.0.0.2 8388616
1110011101011100100001100011110011101111010100001000011110111101111011100001000011100111011111111100001000010101111011110111100001000010001101011110111100010000000001100011110111101010010100011000011100111101000010100011000011100111111100011100011000010101
1110110001111001110000101111010110001111001100000101111000110001111011100001011110000100001111010100101011110000100001111110000101011110000101011110000001111011110000101011010100001111011110000101111000100001110011100001011111001100001110010100001011110001
1000011100100001010111100111000111000000001000111100111000111101000011000111100111010110101000010000111001111111110111000010000101001110111101111000010000100001010111101111000000000100011000111101111000100001000011000111101111010100001000110000111001111011
0001010001100001110111101110011110001100001010110101100011110011100001011110001100011110011000000011110001100011110101000010111100001000011110100001010111100001000011110100001110111100001000111111000011110111100001010110101000011110111100001111110001000011
1101011000101111000110000111001010010101111000110000111001000010001111001110000110000000010001111001110101100010000110001111001110111101010000100001111011111111011110000100001010010111111011110000100001000010101111011110000000000000110001111011110001000000
0001000011110111101010010100011000011100111101100011100011000011101111111100111100011000011101101011000111100111000010111100011000111100111000000111000011000111100010000101111000010000111101000010101111000010000111110000011101111000010101111110000111101111
0000101111110100001111011110000101111010100001111010100001111110001100001110010000001011110001100001110000000100011110001100011100000001100011110011101011110100001100011110011101011011100001100011110111111110011100001000011100101011110111100001000010100101
0111101111000010000000010000111101111000100001000010000111101111010100101000010000111001111111000101000110000111011111111001111000110000101011110111001111001110000001111010110001111000110000001110000110001111010100001001110000100001111000100101011110000100
0111110000011110111100001010111101000011110111100001010110101000011110111100001111110101000011110111000001111100011000011100101001010111100011000011100000001110111100011000111101000001000111100111010111101000011000111100111011110101000011000111000111111111
1110000100001110011101111011110000100001010010101111011110000100001000100001111011110101000010000100001111011110101001010000100001111111110110001110001100001110111101110011110001100001010111101110011110001100001011110101100011110011000000011110001100011110
Four RPs per Group #
RPs: 10.0.0.1, 10.0.0.2, 10.0.0.3, 10.0.0.4
Group Range: 239.0.0.0-239.255.255.255
Hash Mask of 30 #
max streak 20
TOTAL WINS
rp wins
10.0.0.1 465204
10.0.0.2 4078024
10.0.0.3 7923424
10.0.0.4 4310564
3333222222221111333322222222111133331111222222223333222211111111333311112222222233332222222211113333222222223333333311112222111122222222222222223333111122223333000022222222111133331111222222223333222222221111000011112222222233330000111122223333222222223333
3333111122221111333322223333333333331111222233332222111122222222333311112222222233332222222211112222111133332222333322223333333300001111222222223333000022221111333322223333333322221111222211112222111122222222333311112222333333331111222211112222000033332222
3333222222223333222211112222222233332222222233333333111100001111222211112222111133330000333322222222111122221111333311112222222222221111333333333333222222223333222211113333222222222222222233333333111122222222222211112222111133332222000022222222111122221111
2222000022222222111111113333222233331111222211112222111133332222111122223333333322221111222222222222111122222222333333332222111122221111222211112222222233332222222211110000222233331111222200001111222233332222333322222222111122221111333322221111111122222222
3333333322221111222211112222222211112222333322222222111122222222222211113333222233333333000022223333111122220000222211113333222233331111222222222222111133331111222211112222222233333333333311112222111122222222111111113333222222223333333322223333111122222222
2222333333332222333311112222222222221111333322222222111133332222333311113333111122221111222222223333222233332222222211113333222222221111111122222222333333332222333311112222111122222222333322222222111133332222222211112222222222221111222222223333222233331111
2222111133332222222211113333222200001111333322223333111122221111222222223333222222221111333322222222111122222222222211113333222222222222333311112222111133332222222222223333222222221111333322222222111133331111000022223333222222221111333311112222222211112222
2222111133332222222222222222111122221111333322222222222233331111222222223333222222221111333311112222222233332222222211113333111122222222333311112222222233331111222222221111111122221111333322223333222233331111222222223333111122222222333333332222222233332222
2222111122221111333322223333111122222222333311112222222233331111222211113333222233332222222211112222333300001111222222223333111122222222333311112222111122221111333322223333111122222222222211112222222233331111222222223333111133333333222211112222333333331111
Hash Mask of 31 #
max streak 12
TOTAL WINS
rp wins
10.0.0.1 4194314
10.0.0.2 4426920
10.0.0.3 4194316
10.0.0.4 3961666
3333221122001100330022112233110033331111220022003300221111331100331111112200220033332211223311223300221122003300331111112233110022002211223322003333111122003300000022112233110033331111220022003300221122331100000011112233220033330011113322003300221122003300
3333110022331100330022113333330033001111221133002200111122332200333311112200221133002200223311002200111133332200330022113311330000001111220022003333000022331111330022113333333322001111223311002200111122332200330011112200331133001100223311002200001133332200
3300221122113300220011112233220033002200223333113300111100331100220011002233110033000011333322002200111122331111330011002233220022001111333333113300220022333300220011113333220022002200221133113300111122222200220011002233111133002200003322112200111122331111
2200000022332200110011113333221133001100223311112200110033332211110022003333331122001111223322002233110022332211330033002222111122001100223311112200220033332200220011110000221133331100223300111111220033332211330022002233111122001111333322001133110022002211
3300331122331111220011002233221111002200333322112200111122002211223311003333220033003300000022113300110022330022220011003333221133331133220022112200111133331111223311002200221133003311333311112200110022002211113311003333220022003333330022113333110022002200
2200330033332211332211002200221122001100333322222233110033002211332211113300111122001100221122113333220033332211220011113300221122331100111122002233333333002211330011002200111122002200333322002222111133002211220011112200222222331100220022113322220033331111
2200111133112200223311003311220000331111330022113333110022111111223322003333223322001111330022112200110022002200223311003300221122002200330011112233112233112200223322003333221122001111330022112233110033111111003322003300221122331111330011112200220011112233
2233111133002211220022002200111122331100330022002233220033331111220022223300220022331100333311332200220033002211223311113300111122332200331111112233221133001111220022221111110022331100330022333333220033001111220022003300110022332200333333112200221133002200
2233110022001111333322003322111122002211330011112200220033111100223311113300221133332200220011112211330000331133223322003300111122002211330011002233110022001111333322003300111122002200220011112233220033221100223322113300111133333300220011002211330033221111
3333220022001111221133113333110022332200220011113333221133000000221122112200111133332200220011002200221133001111333322002200110022331111330011003333221122001111331133112222110022332200220011113333221133001100221111112200110033332211220022003311221122001111
Hash Mask of 32 #
max streak 8
TOTAL WINS
rp wins
10.0.0.1 4077999
10.0.0.2 4543204
10.0.0.3 4078003
10.0.0.4 4078010
3132231122031102300223122033130231321211210320023002231110331101311013122003200231322311213311213102201220033101311213112133100221022012203121013132131120033002030223122033130131321012220320013002231120331301030210122033200231320311113320013102231220033301
3132130221331001310220123233310130021311201330022103131220332001313211132003231133022302203313012102101231332002300223113212300101031312200322013132000221331011310220123033333120021311213310022103131220322001310211132003331131021302203310012102001331332001
3002231120123001210313122133200131022002203230113102131200331201200213022133100131030313303220012002131321331211310313022032200121021113313333113002230220323001210313123133200020022103211230113103131220222001200211022133101131032302003220112002131221331011
2003030221322001110313133132221130021302203210112103100231332011100221013132301120031312213220002033110321322011310331022022131120021002213310122003230131322001200013110102201130331302203200111113200231332311300223012132101220031312313120021233110321022011
3103331220321311200310022133201310032301313220112002131221022010203313023132200130003002010223113003130121320022200310023133201130331331210220122003131231311311223310022102201333033311313213112002100221022013103313013132200320023032310223113033130021022002
2003300231332311302010012102231220031300313323232033100231022011302313113102131120031002211123133333200131322311200210113102231220331302111220032133303231022311300210002103131320032002313321032020101131022012200313112002232121331002210323113122200131321311
2002101131112302203313013112200101331012300223113032100221131313203320023132233320021011310223122003130220022303213310023100231120022001300213112033102231132302203320013132231121031011300223122031110131131313013320023002231120321011310313122003200210122331
2133101131022012200220012002131121331002300022022032200131321311210320223002230220331001313313322103200130022311213111113003131220332002331013112133201131021312200223211012130221331003310220323132200130021311210120023003130220322001313230122103231130022300
2233110320031312313320023022131121022011310313122003230133121002213310113102201131312101200213112113300201331332213220013102101222012311300213022033100323021212313320013002131122022001200313122133230131221002213220113102131031333301200213022113300131231311
3132200120021112211333113333130220322001210210123133231130020302201220132303131231332201200210022102201131031312303223012002100221331211310310003132201120021112311333112023130221322001210311123132231130021102201213112103100231332011200220013112201120031312
Code used to find these results #
import ipaddress
from datetime import datetime
from numpy import uint32, bitwise_and, bitwise_xor
from functools import partial
from multiprocessing import Pool
from warnings import filterwarnings
def calculate_hash(rp_address, group, mask):
"""
implements the hash function from RFC 7761
"""
# supress overflow warnings. These are expected with 32bit arithmetic
filterwarnings('ignore', category=RuntimeWarning)
result = uint32(bitwise_and(group,mask))
result = uint32(uint32(1103515245) * uint32(result)) + uint32(12345)
result = uint32(bitwise_xor(result, rp_address))
result = uint32(uint32(1103515245) * uint32(result))
result = uint32(uint32(result) + uint32(12345))
result = uint32(uint32(result) % uint32(2**31))
return result
def iter_rp(rp_list, mask, group):
"""
iterates over the RP list, calls calculate_hash and stores the results
"""
group_result = []
group_winner = ''
winner_val = 0
for rp in rp_list:
value = calculate_hash(uint32(rp), uint32(group), mask)
result = {
'rp': str(rp),
'value': value
}
if value > winner_val:
winner_val = value
group_winner = rp
group_result.append(result)
return {
'group': group,
'group_results': group_result,
'group_winner': group_winner
}
def calculate_winners(results, rp_list):
# values used to calculate streak lengths
previous_result = ''
streak = 1
max_streak = 0
# stores win counts
wins = [0] * len(rp_list)
# stores a list of winning RP numbers in order from lowest group number to highest
win_string = ''
# stores the overall results
result_string = ''
for group_result in results:
# calculate streak length
if group_result['group_winner'] == previous_result:
streak = streak + 1
else:
streak = 1
if streak >= max_streak:
max_streak = streak
# build the result string for the current group
result_string = result_string + "{}\t{}\t{}\n".format(str(group_result['group']), str(group_result['group_winner']), streak)
# increment the wins count and build the win_string
winner_index = rp_list.index(group_result['group_winner'])
wins[winner_index] += 1
win_string = win_string + str(winner_index)
# Add a line break to the win_string at byte boundries
# this allows us to build a winning RP map
if bitwise_and(uint32(group_result['group']), uint32(255)) == 255:
win_string = win_string + '\n'
# set the prior result to current result
previous_result = group_result['group_winner']
# build win_summary
win_summary = ("max streak %r\n" %(max_streak))
win_summary = win_summary + '\nTOTAL WINS\nrp\t\t\twins\n'
for rp in rp_list:
win_summary = win_summary + "{}\t{}\n".format(str(rp), wins[rp_list.index(rp)])
return result_string, win_summary, win_string
def save_results(results, rp_list, start_group, end_group, mask_length):
# create a timestamp for use in filenames
timestamp = datetime.now().strftime("%Y%m%dT%H%M%S")
# settings string to be copied at the beginning of each file
settings_string = 'RPs: '
for rp in rp_list:
settings_string = settings_string + '{} '.format(str(rp))
settings_string = settings_string + '\nMask Length: {}\n Start Group: {}\n End Group: {}\n'.format(mask_length, start_group, end_group)
win_results, win_summary, win_string = calculate_winners(results, rp_list)
# save the win_string to a file
with open(timestamp + '_win_map.txt', 'a') as f:
f.write(settings_string)
f.write(win_summary)
f.write(win_string)
save_rp_wins = input('save RP Win list to file? [n]/y :').lower()
if('y' in save_rp_wins):
# save the winning RPs to a file
with open(timestamp + '_winning_rps.txt', 'a') as f:
f.write(settings_string)
f.write(win_summary)
f.write('group\t\twinner\tstreak\n')
f.write(win_results)
save_hash_values = input('save hash values to file? [n]/y :').lower()
if('y' in save_hash_values):
# save hash values to a file
with open(timestamp + '_rp_hash_values.txt', 'w') as f:
f.write(settings_string)
f.write('group\t\t')
for rp in rp_list:
f.write(str(rp) + '\t')
f.write('\n')
# store the results in a buffer first and then write to the file
group_result_buffer = ''
for group_result in results:
group_result_buffer = group_result_buffer + str(group_result['group']) + '\t'
for result in group_result['group_results']:
group_result_buffer = group_result_buffer + str(result['value']) + '\t'
group_result_buffer = group_result_buffer + '\n'
f.write(group_result_buffer)
if __name__ == '__main__':
rp_list = []
group_list = []
# prompt for user inpt
mask_length = uint32(input('mask length: '))
rp_input = input('rp addresses (separated by spaces): ')
start_group = ipaddress.IPv4Address(input('starting group: '))
end_group = ipaddress.IPv4Address(input('ending group: '))
# build the rp_list based on user input
for rp in rp_input.split():
rp = ipaddress.IPv4Address(rp)
rp_list.append(rp)
# build a list of groups, required for using Pool.map()
curr_group = start_group
while curr_group <= end_group:
group_list.append(curr_group)
curr_group+=1
# convert the mask_length to an actual bitmask of the appropriate length
mask = uint32((2**mask_length) - 1 << 32-mask_length)
# spawn 16 processes to calculate results
with Pool(16) as pool:
results = pool.map(partial(iter_rp, rp_list, mask), group_list)
# save the results to a file
save_results(results, rp_list, start_group, end_group, mask_length)