Erlang Central

Token Passing Simulation

From ErlangCentral Wiki

Problem:

How to do a small Software Simulation of a "Token Passing" Network.

Note:

"Token Passing" transmission, adopted in Fiber Optical FDDI Standard, sees the Network as a Logical Ring, in which Data are sent by Packets always in the same direction. trough the next neighbor Station. Permission to Transmit is given to a Station by receiving a "void" Packet, called the "Token". When a Station receives the Token, it sends Packets (if any) upon the Ring, and holds the Token until the Packets come back, after having met their Destination Station; then, the Source Station releases the Token upon the Ring. The Packets, besides Data, bear Destination and Source IP Addresses, Control fields, and a "Status" field, which is updated by Destination Station in order to confirm receipt. The Other Stations, simply release the Packets upon the Ring after Address control.

Solution:

Network Stations can be simulated by Processes, and their IP Addresses by Pids or Registered Names of Processes. In this example, five Processes are used, with these registered names: stat0, stat1, stat2, stat3, stat4. Direction is from stat0 to stat1,.., to stat4 to stat0. Below, the code of three functions to be used interactively from the Eshell. The function start() spawns and registers those processes; function halt() will, at end, give them a signal for exiting normal; function shot() gives to stat0 a signal for the first Token release.

shot() ->
        stat0 ! go_token.

halt() ->
        stat0 ! finish,
        stat1 ! finish,
        stat2 ! finish,
        stat3 ! finish,
        stat4 ! finish.

start() ->
        register(stat4, spawn( tour, stat4, [])),
        register(stat3, spawn( tour, stat3, [])),
        register(stat2, spawn( tour, stat2, [])),
        register(stat1, spawn( tour, stat1, [])),
        register(stat0, spawn( tour, stat0, [])).

Below, the code of function stat0() for Process stat0. Receiving the go_token signal from function shot(), it sends to stat1, as next neighbor, the Token itself: a signal made by a Tuple holding the atom bones and a void list. The Tuple {bones,Things} represents a generic Packet, which may be as well the Token (if variable Things represent a void list), or a Data Packet (if such list is full): so, it's worth to check such List through the function analyze(), giving as arguments Things, stat0, and stat1. After the receive ends, stat0() calls itself recursively. The code for functions stat1(),..,stat4() is almost identical to that of stat0(), besides an obvious turn-over for "calling" and "next neighbor" process; you can leave or drop the "go_token" clause as you like, since the function shot() will shot anyway only upon stat0.

stat0() ->
        receive
                go_token ->
                        stat1 ! {bones,[]};
                finish ->
                        io:format("stat0 exits~n",[]),
                        exit(normal);
                {bones,Things} ->
                        analyse(Things, stat0, stat1)
        end,
        stat0().

Below, the code for function analyse(). Parameters What, Me, Next, correspond to: Things, "calling" process, "next neighbor" process. If What is a void list, process "Me" has got the Token, so sends to process "Next" the result of the function take_pkg(), which builds a Packet for "Me". Otherwise, process "Me" has got a true Packet, so calls the function pkg_came(), after getting from the List the Destination field, which is passed as parameter Dest, together with list "tail" Tail, Me and Next.

analyse(What, Me, Next) ->
        case What of
        [] ->
                io:format("~s received Token~n",[Me]),
                Next ! take_pkg(Me);
        _Else ->
        [Dest|Tail] = What,
                pkg_came(Dest, Tail, Me, Next)
        end.

Below, the code for function take_pkg(), which returns a different Packet according to the value of parameter "Me". The Packet is a Tuple holding the atom bones and a List of fields representing Destination, Source (Me), a Data field, and the "Status" field bearing the atom spilt. Data could be any language Type or Structure. Those shown are nests of Tuples bearing fancy "citizens" borrowed from James Joyce. So, this Simulation will send five Packets around the Ring; one for every Station.

take_pkg(Me) ->
        Data1 = {{citizen,'Leopold','Bloom'},{residence,'Dublin'},
                {country,'Ireland'},{profession,philosopher}},
     ----------------------------------------------------------------
        Data5 = {{citizen,'Timothy','Finnegan'},{residence,'Dublin'},
                {country,'Ireland'},{profession,carpenter}},
case Me of
        stat1 -> {bones,[stat0, Me, Data1, spilt]};
        stat2 -> {bones,[stat1, Me, Data2, spilt]};
        stat3 -> {bones,[stat2, Me, Data3, spilt]};
        stat4 -> {bones,[stat3, Me, Data4, spilt]};
        stat0 -> {bones,[stat4, Me, Data5, spilt]}
end.

Let's show the function pkg_came(), which mostly verifies if the Packet just received was destined to process "Me" or not. If Dest is "Me", the Source (Sour) and Data (Load) field are extracted from Tail, in order to rebuild the Packet updating the Status field from the original spilt to drunk (Dest has drunk what Sour has spilt for him). If the Packet was not destined to "Me", the function pkg_back() is invoked. The test Sour /= Dest is a caution against software mistakes, and if the test fails, an exit(error) occurs.

pkg_came(Dest, Tail, Me, Next) ->
        [Sour|Rest] = Tail,
        if Sour /= Dest ->
                case Dest of
                Me ->
                        [Load|_] = Rest,
                        io:format("OK: Packet destined to me: ~s~n",[Dest]),
                        io:format("It came from: ~s~n",[Sour]),
                        Next ! {bones,[Dest, Sour, Load, drunk]};
                _Else ->
                        pkg_back(Dest, Sour, Rest, Me, Next)
                end;
        true ->
                io:format("Error! same Sour as Dest: ~s ~s~n",[Sour,Dest]),
                exit(error)
        end.

Here is function pkg_back(), which verifies if the Packet came back to the Source Station. If so, the Status field is tested, to verify if it was updated by Destination Station; anyway, it's worth releasing the Token. With one exception, however. If process Me is stat0, all available Packets were already sent, and the Simulation pauses, expecting an interactive signal. Operator can choose to Repeat with functiom]n shot(), or to Stop with function halt(). If "Me" is not the Source Station, been verified already that it is not the Destination, it just releases the Packet to Next on the Ring.

pkg_back(Dest, Sour, Rest, Me, Next) ->
        case Sour of
        Me ->
                io:format("Packet came BACK to Sender: ~s~n",[Sour]),
                How = lists:last(Rest),
                if How == drunk ->
                        io:format("Destin ~s SIGNED Packet Receipt~n",[Dest]);
                true ->
                        io:format("Wrong Status: malfunction in Destin~s~n",[Dest])
                end,
                if Me /= stat0 ->
                        io:format("Let release the Token to ~s~n",[Next]),
                        Next ! {bones,[]};
                true ->
                        io:format("~s: No more Packets to send~n",[Me])
                end;
        _Else ->
                Next ! {bones,[Dest,Sour,Rest]}
        end.