Wednesday, March 25, 2009

Making BGP use some other port than 179.

By default BGP uses port 179 for both incoming and outgoing connections. This can be a problem because port 179 is a privileged port which can only be opened for listening as root.

Quagga can easily be configured to use some other port than 179.

Do the following to make BGP listen on port 1790 instead of port 179.

Edit the file /etc/quagga/debian.conf as root:

sudo vi /etc/quagga/debian.conf

Set the bgpd_options to the following:

bgpd_options=" --daemon -A 127.0.0.1 --bgp_port 1790"

Restart quagga as follows:

sudo /etc/init.d/quagga restart

Verify that BGP is actually listening on port 1790:

$ netstat -ant
Active Internet connections (servers and established)
Proto Recv-Q Send-Q Local Address Foreign Address State
tcp 0 0 0.0.0.0:1790 0.0.0.0:* LISTEN
tcp6 0 0 :::1790 :::* LISTEN


Do the following to make BGP use port 1790 instead of port 179 for outgoing connections:

Go into the CLI for BGP:

telnet localhost 2605
[...]
Password: zebra

Go into configuration mode:

bgpd> ena
bgpd# configure terminal

Configure BGP as follows:

router bgp xxxx
neighbor x.x.x.x remote-as xxxx
neighbor x.x.x.x port 1790

Save the configuration using the "write" command:

write

Verify that BGP actually uses 1790 as the outgoing port as follows (you can do a "clear ip bgp *" to make BGP initiate an outgoing connection faster):

$ sudo tcpdump port 1790
tcpdump: verbose output suppressed, use -v or -vv for full protocol decode
listening on eth0, link-type EN10MB (Ethernet), capture size 96 bytes
00:05:17.791499 IP cayle-spandons-ubuntu.local.51002 > cayle-spandons-computer.local.1790: S 395668408:395668408(0) win 5840
00:05:17.792250 IP cayle-spandons-computer.local.1790 > cayle-spandons-ubuntu.local.51002: R 0:0(0) ack 395668409 win 0

Sunday, February 1, 2009

Erlang.org course exercises for masters, slaves, and error handling.

The Erlang.org website contains one programming exercise dealing masters, slaves, and error handling.

The requirements are as follows (copied from the Erlang.org website):

Write a module ms with the following interface:

start(N) - Start the master and tell it to start N slave processes. Register the master as the registered process master.

to_slave(Message, N) - Send a message to the master and tell it to relay the message to slave N. The slave should exit (and be restarted by the master) if the message is die.

The master should detect the fact that a slave processes dies and restart it and print a message that it has done so.

The slave should print all messages it recieves except the message die

The source code for my solution is:






%% Erlang exercises: Masters and Slaves, error handling
%%
%% See http://erlang.org/course/exercises.html for details.

-module(masterslave).
-author('Cayle Spandon').

-export([start/1, stop/0, to_slave/2]).

start(NrSlaves) ->
MasterPid = spawn(fun() -> master_start(NrSlaves) end),
register(master, MasterPid),
ok.

stop() ->
master ! die,
ok.

to_slave(Message, SlaveNr) ->
master ! {to_slave, Message, SlaveNr},
ok.

slave_pid_to_nr(SlavePid, SlavePids) ->
slave_pid_to_nr(SlavePid, SlavePids, 1).

slave_pid_to_nr(SlavePid, [SlavePid | _Tail], SlaveNr) ->
SlaveNr;

slave_pid_to_nr(SlavePid, [_Head | Tail], SlaveNr) ->
slave_pid_to_nr(SlavePid, Tail, SlaveNr + 1).

slave_change_pid(OldSlavePid, NewSlavePid, SlavePids) ->
lists:map(
fun(Pid) ->
if
Pid == OldSlavePid ->
NewSlavePid;
true ->
Pid
end
end,
SlavePids
).

master_start(NrSlaves) ->
process_flag(trap_exit, true),
io:format("master: started~n", []),
SlavePids = [spawn_link(fun() -> slave_start(SlaveNr) end) || SlaveNr <- lists:seq(1, NrSlaves)],
master_loop(SlavePids).

master_loop(SlavePids) ->
receive
die ->
io:format("master: received die~n"),
lists:foreach(fun(SlavePid) -> SlavePid ! die end, SlavePids);
{to_slave, Message, SlaveNr} ->
io:format("master: forward ~p to slave ~p~n", [Message, SlaveNr]),
SlavePid = lists:nth(SlaveNr, SlavePids),
SlavePid ! Message,
master_loop(SlavePids);
{'EXIT', SlavePid, _Reason} ->
SlaveNr = slave_pid_to_nr(SlavePid, SlavePids),
io:format("master: slave ~p died~n", [SlaveNr]),
NewSlavePid = spawn_link(fun() -> slave_start(SlaveNr) end),
NewSlavePids = slave_change_pid(SlavePid, NewSlavePid, SlavePids),
master_loop(NewSlavePids)
end.

slave_start(SlaveNr) ->
io:format("slave ~p: started~n", [SlaveNr]),
slave_loop(SlaveNr).

slave_loop(SlaveNr) ->
receive
die ->
io:format("slave ~p: received die~n", [SlaveNr]);
Message ->
io:format("slave ~p: received ~p~n", [SlaveNr, Message]),
slave_loop(SlaveNr)
end.

Thursday, January 29, 2009

Erlang.org course exercises for spawning processes and exchanging messages

The Erlang.org website contains a number of programming exercises dealing with spawning processes and exchanging messages between them:

Write a function which starts 2 processes, and sends a message M times forwards and backwards between them. After the messages have been sent the processes should terminate gracefully.

%% Erlang exercises: Interaction between processes and concurrency, problem number 1.
%%
%% Write a function which starts 2 processes, and sends a message M times forewards and backwards between them.
%% After the messages have been sent the processes should terminate gracefully.
%%
%% See http://erlang.org/course/exercises.html for details.

-module(processes1).
-author('Cayle Spandon').

-export([solve/0, solve/1]).

solve() ->
solve(10).

solve(NrMsgs) ->
Pid1 = spawn(fun() -> process_1() end),
spawn(fun() -> process_2(Pid1, NrMsgs) end),
ok.

process_1() ->
io:format("Process 1 starts.~n"),
process_1_loop(),
io:format("Process 1 ends.~n").

process_1_loop() ->
receive
{From, {message, More}} ->
io:format("Process 1 received message ~p.~n", [More]),
io:format("Process 1 sends message_reply.~n"),
From ! {self(), {message_reply}},
if
More ->
process_1_loop();
true ->
ok
end
end.

process_2(Pid1, NrMsgs) ->
io:format("Process 2 starts.~n"),
process_2_loop(Pid1, 1, NrMsgs),
io:format("Process 2 ends.~n").

process_2_loop(Pid1, MsgNr, NrMsgs) ->
io:format("Process 2 sends message nr ~p.~n", [MsgNr]),
More = (MsgNr < NrMsgs),
Pid1 ! {self(), {message, More}},
receive
{Pid1, {message_reply}} ->
io:format("Process 2 received message_reply.~n"),
if
More ->
process_2_loop(Pid1, MsgNr + 1, NrMsgs);
true ->
ok
end
end.


Write a function which starts N processes in a ring, and sends a message M times around all the processes in the ring. After the messages have been sent the processes should terminate gracefully.

%% Erlang exercises: Interaction between processes and concurrency, problem number 2.
%%
%% Write a function which starts N processes in a ring, and sends a message M times around all the processes in the
%% ring. After the messages have been sent the processes should terminate gracefully.
%%
%% See http://erlang.org/course/exercises.html for details.

-module(processes2).
-author('Cayle Spandon').

-export([solve/0, solve/2]).

solve() ->
solve(3, 2).

solve(NrProcesses, NrLoops) ->
Pids = [spawn(fun() -> process_init(ProcessNr, NrProcesses) end) || ProcessNr <- lists:seq(1, NrProcesses)],
[FirstPid | _] = Pids,
set_next_pids(FirstPid, Pids),
FirstPid ! {message, 1, NrLoops}.

set_next_pids(FirstPid, [Pid1, Pid2 | OtherPids]) ->
Pid1 ! {set_next_pid, Pid2},
set_next_pids(FirstPid, [Pid2 | OtherPids]);

set_next_pids(FirstPid, [LastPid]) ->
LastPid ! {set_next_pid, FirstPid}.

process_init(ProcessNr, NrProcesses) ->
io:format("Process ~p of ~p: waiting for set_next_pid message~n", [ProcessNr, NrProcesses]),
receive
{set_next_pid, NextPid} -> ok
end,
io:format("Process ~p of ~p: next pid is ~p~n", [ProcessNr, NrProcesses, NextPid]),
process_loop(ProcessNr, NrProcesses, NextPid).

process_loop(ProcessNr, NrProcesses, NextPid) ->
receive
{message, Loop, NrLoops} ->
io:format("Process ~p of ~p: receive message with loop ~p of ~p~n", [ProcessNr, NrProcesses, Loop, NrLoops]),
if
ProcessNr == NrProcesses ->
NewLoop = Loop + 1;
true ->
NewLoop = Loop
end,
NextPid ! {message, NewLoop, NrLoops},
if
Loop < NrLoops ->
process_loop(ProcessNr, NrProcesses, NextPid);
true ->
io:format("Process ~p: ends~n", [ProcessNr]),
ok
end
end.


Write a function which starts N processes in a star, and sends a message to each of them M times. After the messages have been sent the processes should terminate gracefully.

%% Erlang exercises: Interaction between processes and concurrency, problem number 3.
%%
%% Write a function which starts N processes in a star, and sends a message to each of them M times. After the messages
%% have been sent the processes should terminate gracefully.
%%
%% See http://erlang.org/course/exercises.html for details.

-module(processes3).
-author('Cayle Spandon').

-export([solve/0, solve/2]).

solve() ->
solve(3, 2).

solve(NrProcesses, NrLoops) ->
SpokePids = [spawn(fun() -> spoke_process_start(ProcessNr) end) || ProcessNr <- lists:seq(1, NrProcesses)],
spawn_link(fun() -> hub_process_start(SpokePids, NrLoops) end),
ok.

spoke_process_start(ProcessNr) ->
io:format("spoke_process ~p: start~n", [ProcessNr]),
spoke_process_loop(ProcessNr).

spoke_process_loop(ProcessNr) ->
receive
{From, ping_request, More} ->
io:format("spoke_process ~p: receive ping_request~n", [ProcessNr]),
io:format("spoke_process ~p: send ping_reply~n", [ProcessNr]),
From ! {self(), ping_reply}
end,
if
More ->
spoke_process_loop(ProcessNr);
true ->
io:format("spoke_process ~p: end~n", [ProcessNr]),
ok
end.

hub_process_start(SpokePids, NrLoops) ->
io:format("hub_process: start~n"),
hub_process_loop(SpokePids, NrLoops).

hub_process_loop(_SpokePids, 0) ->
io:format("hub_process: end~n"),
ok;

hub_process_loop(SpokePids, LoopNr) ->
More = (LoopNr > 1),
io:format("hub_process: loop ~p~n", [LoopNr]),
ping_all_spokes(SpokePids, More),
hub_process_loop(SpokePids, LoopNr - 1).

ping_all_spokes([], _More) ->
ok;

ping_all_spokes([SpokePid | RemainingSpokePids], More) ->
ping_spoke(SpokePid, More),
ping_all_spokes(RemainingSpokePids, More).

ping_spoke(SpokePid, More) ->
io:format("hub_process: send ping_request spoke ~p~n", [SpokePid]),
SpokePid ! {self(), ping_request, More},
receive
{From, ping_reply} ->
io:format("hub_process: receive ping_reply from spoke ~p~n", [From])
end,
ok.

Sunday, January 25, 2009

Erlang solutions for Euler problems 19, 24, 25 and 48.

Solving project Euler problems has been fun and useful to learn the basics of sequential programming in Erlang and to get used to heavy emphasis on tail-recursion in Erlang.

However, the programs for solving Euler problems tend to use only a very small subset of the Erlang features: they generally don't use binaries, don't spawn processes, don't send messages, don't have error handling, don't use mnesia, etc.

I will continue to work on Euler problems in the background (because they are fun) but to take my learning of Erlang to the next level I have chosen a different set of exercises, namely the ones which are listed in the exercises section of the Erlang website.

Below are the Erlang programs for Euler problem numbers 19, 24, 25 and 48. This brings me to a grand total of 25 solved Euler problems and gives me bragging rights for reaching "Level 1".

While working on Euler problem 67 I discovered what I think is a bug in function io:fread. I posted this bug on stack overflow and on the erlang mailing list, but I haven't had any response yet.

Code for Erlang problem 19:

%% Project Euler, problem 19
%%
%% How many Sundays fell on the first of the month during the twentieth century?

-module(euler19).
-author('Cayle Spandon').

-export([solve/0]).

is_leap_year(Year) ->
if
Year rem 400 == 0 ->
true;
Year rem 100 == 0 ->
false;
Year rem 4 == 0 ->
true;
true ->
false
end.

days_in_month(Month, Year) ->
case Month of
1 -> 31;
2 ->
case is_leap_year(Year) of
true -> 29;
false -> 28
end;
3 -> 31;
4 -> 30;
5 -> 31;
6 -> 30;
7 -> 31;
8 -> 31;
9 -> 30;
10 -> 31;
11 -> 30;
12 -> 31
end.

next_date({Day, Month, Year, Dow}) ->
NewDow = (Dow + 1) rem 7,
case Day == days_in_month(Month, Year) of
false ->
NewDay = Day + 1,
NewMonth = Month,
NewYear = Year;
true ->
case Month == 12 of
false ->
NewDay = 1,
NewMonth = Month + 1,
NewYear = Year;
true ->
NewDay = 1,
NewMonth = 1,
NewYear = Year + 1
end
end,
{NewDay, NewMonth, NewYear, NewDow}.

is_first_of_month_sunday({Day, _Month, _Year, Dow}) ->
(Day == 1) and (Dow == 0).

solve() ->
solve({1, 1, 1900, 1}, 0).

solve(Date = {_Day, _Month, Year, _Dow}, Count) ->
NextDate = next_date(Date),
if
Year < 1901 -> % Not in 20th century yet
solve(NextDate, Count);
Year =< 2000 ->
case is_first_of_month_sunday(Date) of
false -> NewCount = Count;
true -> NewCount = Count + 1
end,
solve(NextDate, NewCount);
true ->
Count
end.


Code for Erlang problem 24:

%% Project Euler, problem 24
%%
%% What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?
%%
%% Note that we compute ALL permutations of the 10 digits even though we only need the first million. I can't figure
%% out an easy way to "break off the comprehension early" and I thought the code using comprehension was too elegant
%% to pass up. This algorithm still finishes well within the allowed 1 minute.

-module(euler24).
-author('Cayle Spandon').

-export([solve/0, permutations/1]).

permutations([]) -> [[]];
permutations(L) -> [[H|T] || H <- L, T <- permutations(L--[H])].

solve() -> lists:nth(1000000, permutations("0123456789")).


Code for Erlang problem 25:

%% Project Euler, problem 25
%%
%% What is the first term in the Fibonacci sequence to contain 1000 digits?

-module(euler25).
-author('Cayle Spandon').

-export([solve/0, solve/1]).

nr_digits(N) ->
if
N < 10 ->
1;
true ->
1 + nr_digits(N div 10)
end.

fibonacci(WantedDigits) ->
fibonacci(WantedDigits, 1, 1, 2).

fibonacci(WantedDigits, Prev, Current, Term) ->
NrDigits = nr_digits(Current),
if
NrDigits >= WantedDigits ->
Term;
true ->
fibonacci(WantedDigits, Current, Prev + Current, Term + 1)
end.

solve() ->
solve(1000).

solve(WantedDigits) ->
fibonacci(WantedDigits).


Code for Erlang problem 48:

%% Project Euler, problem 48
%%
%% Find the last ten digits of 1^1 + 2^2 + ... + 1000^1000.

-module(euler48).
-author('Cayle Spandon').

-export([solve/0, solve/1]).

last_ten_digits(N) -> N rem 10000000000.

n_pow_n(N) -> n_pow_n(N, N).
n_pow_n(N, 1) -> N;
n_pow_n(N, Rem) -> N * n_pow_n(N, Rem-1).

sum_of_powers(Max) -> lists:sum([n_pow_n(N) || N <- lists:seq(1, Max)]).

solve() ->
solve(1000).

solve(Max) ->
last_ten_digits(sum_of_powers(Max)).

Saturday, January 24, 2009

Erlang solution for Euler problem 23

In project Euler problem number 23 we are asked to find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.

In the problem description we are told that we only need to try the numbers up to 28123.

The function sum_of_divisors(N) to determine the sum of the proper divisors of a number N has been used before, more recently in project Euler problem number 21.

Once we have sum_of_divisors/1, the function is_abundant(N) which determines whether a given number N is an abundant number is trivial to write.

This, in turn, allows us to write all_abundant_numbers_up_to(Max) which computes the list of all abundant numbers up to and including Max in order of increasing value. We use this function to compute all abundant number up to 28123.

The next step is to write function all_pairs_of_abundant_numbers_up_to(Max) which computes a list of which contains all numbers N which satisfy the following two conditions:
  1. N = N1 + N2 where N1 and N2 are both amicable numbers.
  2. N <= Max.
The next step is to write a function all_non_pairs_up_to(Max) which generates a list of numbers up to and including Max which are not a sum of two amicable numbers. We do this by sorting the list we generated in the previous step and finding all "holes" in the list. Note that we have to deal with the fact that the sorted list contains dupplicates.

Putting it all together we end up with the following Erlang program. Note that we make extensive use of list comprehensions.

The run time of this implementation (on my MacBook Pro) is 41 seconds which is only barely within the allowed one minute. That, along with the rather complex structure of the program, makes me think there is a short-cut which I missed. After punching in my correct solution I browsed the message board for problem 23. It turns out there is a much faster way to find the sum of factors which only loops to sqrt(N) instead of N/2.

%% Project Euler, problem 23
%%
%% Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.

-module(euler23).
-author('Cayle Spandon').

-export([solve/0]).

sum_of_divisors(N) ->
sum_of_divisors(N, 1, N div 2, 0).

sum_of_divisors(N, Try, MaxTry, Sum) ->
if
Try > MaxTry ->
Sum;
N rem Try == 0 ->
sum_of_divisors(N, Try + 1, MaxTry, Sum + Try);
true ->
sum_of_divisors(N, Try + 1, MaxTry, Sum)
end.

is_abundant(N) ->
sum_of_divisors(N) > N.

all_abundant_numbers_up_to(Max) ->
[ N || N <- lists:seq(1, Max), is_abundant(N) ].

all_pairs_of_abundant_numbers_up_to(Max) ->
AbundantNumbers = all_abundant_numbers_up_to(Max),
[ N1 + N2 || N1 <- AbundantNumbers, N2 <- AbundantNumbers, N1 + N2 =< Max ].

all_non_pairs_up_to(Max) ->
Pairs = all_pairs_of_abundant_numbers_up_to(Max),
SortedPairs = lists:sort(Pairs),
holes_in_list([ 0 | SortedPairs]).

holes_in_list([H1, H2 | Tail]) when H2 > H1 + 1 ->
lists:seq(H1 + 1, H2 - 1) ++ holes_in_list([H2 | Tail]);
holes_in_list([_H1, H2 | Tail]) ->
holes_in_list([H2 | Tail]);
holes_in_list(_List) ->
[].

solve() ->
lists:sum(all_non_pairs_up_to(28123)).

Erlang solution for Euler problem 21

In project Euler problem number 21 we are asked to evaluate the sum of all amicable pairs under 10000.

To determine whether a given number N1 is an amicable number we determine the sum of all divisors of N1. This gives us another number N2. If N1 and N2 form an amicable pair, then the sum of the divisors of N2 should be N1 again. And also, we have to ignore all solutions where N1 = N2.

Once we have written the function is_amicable_pair/1 as described above, we simple try all number from 1 thru 9999 and sum all amicable numbers we find.

Here is the Erlang code:

%% Project Euler, problem 21
%%
%% Evaluate the sum of all amicable pairs under 10000.

-module(euler21).
-author('Cayle Spandon').

-export([solve/0, sum_of_divisors/1, is_amicable/1]).

sum_of_divisors(N) ->
sum_of_divisors(N, 1, N div 2, 0).

sum_of_divisors(N, Try, MaxTry, Sum) ->
if
Try > MaxTry ->
Sum;
N rem Try == 0 ->
sum_of_divisors(N, Try + 1, MaxTry, Sum + Try);
true ->
sum_of_divisors(N, Try + 1, MaxTry, Sum)
end.

is_amicable(N) ->
CandidateOther = sum_of_divisors(N),
ShouldBeN = sum_of_divisors(CandidateOther),
(N == ShouldBeN) and (N /= CandidateOther).

sum_of_amicable_numbers(N) ->
sum_of_amicable_numbers(1, N, 0).

sum_of_amicable_numbers(Try, MaxTry, Sum) ->
IsAmicable = is_amicable(Try),
if
Try >= MaxTry ->
Sum;
IsAmicable ->
sum_of_amicable_numbers(Try + 1, MaxTry, Sum + Try);
true ->
sum_of_amicable_numbers(Try + 1, MaxTry, Sum)
end.

solve() ->
solve(10000).

solve(N) ->
sum_of_amicable_numbers(N).

Erlang solution for Euler problem 20

Project Euler problem number 20 in which we are asked to find the sum of the digits of 100! is not particularly exiting, so here without further ado is my solution in Erlang:


%% Project Euler, problem 20
%%
%% Find the sum of digits in 100!

-module(euler20).
-author('Cayle Spandon').

-export([solve/0]).

fact(0) -> 1;
fact(N) -> N * fact(N-1).

sum_of_digits(N) when N < 10 -> N;
sum_of_digits(N) -> (N rem 10) + sum_of_digits(N div 10).

solve() ->
solve(100).

solve(N) ->
sum_of_digits(fact(N)).