Week 10: Distribution
Skip navigation Systems, Networks, and Concurrency School of Computing Search query Search ANU web, staff & maps Search current site content Search Menu Search query Search COMP2310/6310 Lectures Labs Assessment Resources Search ANU web, staff & maps Search current site content COMP2310/6310 Lectures Labs Assessment Resources menu Search query Search Search COMP2310/6310 Search query Search Tuesday: A1 Wednesday: A2 Labs: L12 Assessment: A2 Labs Weeks 1-2: Structured Programming Week 3: Tasks Week 4: Protection Week 5: Task Lifespans Week 6: Communicating Tasks Week 7: Load-Balancing Server Week 8: Implicit Concurrency Week 9: Synchronized Data Week 10: Distribution Week 12: Pipelines Related sites Piazza You are here » Labs » Week 10: Distribution Lab project skeleton for Lab 10 Pre-Laboratory Checklist You understand and can use local message passing. You understand memory-based synchronization. You understand and can apply implicit concurrency. You can create and control tasks. Objectives This lab will introduce you to distributed computing. You will use BSD socket based communication using TCP/IP connections to combine several (simulated) computers into one logical ring. Passing messages everywhere Network protocols are usually designed in layers, where each layer is an abstraction of some aspect of message passing. The lower layers are abstractions of the physical medium (copper, fibreglass, or air) and how connections are made. In higher layers, we start to see abstractions for routing messages to a particular node and then synchronizing over longer sequences of messages. This lab will work at this last level of abstraction. When used on the Internet, this is implemented as TCP/IP or Transmission Control Protocol over the Internet Protocol. We could directly interface with TCP/IP, but it’s usually best to use higher-level interfaces – such as the universally available BSD socket interfaces. BSD sockets can be used to send individual datagrams (i.e. messages without end-to-end flow control/synchronization, which translate into UDP/IP or User Datagram Protocol), or to connect nodes so they can exchange a continuous stream of messages with guarantees of arrival and correct order (which translates into TCP/IP). Similar to what we’ve seen in Ada, message passing via BSD sockets assumes a server and a client. The server opens a port (Ada: entry) which any client can use. To save you some time, we’ve abstracted over most of the finer details, and provided an Ada package of the essential steps to communicate over the Internet. First, we need to open a port to the network for other nodes to call: function Open_Server_Port (Port : Port_Type;
Server_Addr : Inet_Addr_Type := Any_Inet_Addr)
return Socket_Type;
We need to nominate a port to open, which is a number between 0 and 16#FFFF#. Not all of those port numbers will be available; some ports have specific purposes. For instance, port 0 is used for communications within your operating system, whereas port 22 is the default port for your ssh connections1. Generally, port numbers above 50,000 are not reserved so that you can use them freely for experimentation. The interface also accepts a local IP address. This can come in handy if your computer has multiple interfaces or if you only want to listen to connections from your own computer and not the outside world. The return value is a reference to the port you’ve opened so that you can refer to it later within other operations. This first step is similar to declaring an entry as part of your task definitions - they both define and open a communication mechanism. The second step is to accept a call from the outside, much like the accept statements from your previous exercises: function Accept_Connection (Server_Socket : Socket_Type;
Connection_Socket : out Socket_Type;
Connection_Address : out Sock_Addr_Type) return Stream_Access;
For the first parameter here, use the Socket_Type reference returned by the Open_Server_Port function. Like the accept statement we’ve used previously, this call blocks until a client actually calls in. When this happens, a channel to the client is established, and three values are returned. The main return value (the Stream_Access) is a reference to that channel, where you can now exchange information (more on this in a moment). The other two parameters are of lesser importance: Connection_Socket is only needed to eventually close the channel, and Connection_Address tells you which network node and port this call originated from. This may or may not be important - in this lab, it could be useful for debugging where things are coming from. Finally, a client needs some way to connect to an open server. This is implemented via: function Connect (Server_Addr : Inet_Addr_Type;
Port : Port_Type;
Connection_Socket : out Socket_Type) return Stream_Access;
For this function, we need to provide a network address and port on which to call. In return, we will receive a reference to a communication channel and a Connection_Socket (which, again, is for closing the channel). Now the server and client both have a reference to a bidirectional communication channel (both sides can read and write). If this channel was called Channel, we could transfer the value of a variable Message (of the type Message_Type) by saying: Message_Type'Write (Channel, Message);
on one computer node and: Message_Type'Read (Channel, Message);
on the connected computer node side. Keep in mind that the communication system here has no idea about types. It will not check that Message is actually of type Message_Type. This is both good and bad news. The good news is that this technique will work seamlessly between any self-respecting programming languages. So exchanging messages between, say, Python and Ada is easy - neither side will ever notice that the other side speaks a foreign language. But removing type checking is also bad news: there’s no type checking anymore. The two nodes have no way to identify or resolve disagreements about the message format. There are systems to amend this issue to a degree (usually called Middleware), but they will also reduce your freedom in programming languages and types. For now, you don’t need to worry about this too much; all your nodes in this lab are programmed in the same programming language, which makes consistent typing easier. If you stick with one language and one distribution system, then you can guarantee type safety rather easily, even if the processor architectures on your computing nodes are different. In almost all other cases, there will be some additional effort required. So the complete story on the server side could like something like: declare
Server_Socket : constant Socket_Type := Open_Server_Port (Port => 60043);
Connection_Socket : Socket_Type;
Connection_Address : Sock_Addr_Type;
Channel : constant Stream_Access :=
Accept_Connection (Server_Socket, Connection_Socket, Connection_Address);
Message : Message_Type;
begin
...
Message_Type'Read (Channel, Message);
...
Message_Type'Write (Channel, Message);
...
Close_Connection (Connection_Socket);
Close_Server (Server_Socket);
end;
While a client could for instance look like this: declare
Connection_Socket : Socket_Type;
Channel : constant Stream_Access :=
Connect (Server_Addr => Inet_Addr ("192.168.115.11"),
Port => 60043,
Connection_Socket => Connection_Socket);
Message : Message_Type := 42;
begin
...
Message_Type'Write (Channel, Message);
...
Message_Type'Read (Channel, Message);
...
Close_Socket (Connection_Socket);
end;
But what happens if the same node is a client on one channel and a server on another? Your lab exercise for this week… Exercise 1: Find the Ring Leader In previous labs, you’ve arranged tasks in a ring and passed messages along the ring. Now, we want to arrange several agents into a ring and run a distributed election algorithm. Here, we’ll use a slightly simplified form of an election algorithm by Ernest Chang and Rosemary Roberts in 19792. Find a unique id in each node. To make this interesting, we use a random value followed by our local address. Each node sends its own id around the ring (as an election bid). If a node receives a bid that is larger than its own bid, then it forwards this bid to the next node (and can forget about being elected). If a node receives a bid that is smaller than its own bid, then it drops this message without a trace (and can still be hopeful of being elected). If a node receives its own bid, then it knows that it is the new leader (and the node can send a confirmation message around the ring to indicate who is boss). This week’s framework already implements this algorithm and provides you with a command-line interface to set the address and port of the next node in your ring. Once you have solved this exercise, you should run the algorithm across several command-line terminals. Your job is to solve the following problem: in order to set up the token ring, you need to complete two blocking calls, namely Connect and Accept_Connection. Obviously, if all nodes block on Connect first and Accept_Connection second, then the ring will never be established. The other way round does not work either. It sounds like a classical concurrency/synchronization job… These two code blocks need to be embedded into your provided node code somehow: Put_Line ("Waiting for previous node to connect");
Incoming_Channel :=
Accept_Connection
(Server_Socket, Incoming_Connection_Socket, Incoming_Connection_Address);
Put_Line ("--> Previous node connected from: "
& Image (Incoming_Connection_Address));
and: Put_Line ("Waiting for next node to become available");
Outgoing_Channel :=
Connect (Server_Addr => CLP.Next_Addr,
Port => CLP.Next_Port,
Connection_Socket => Outgoing_Connection_Socket);
Put_Line ("--> Connected to next node at: "
& Image (CLP.Next_Addr) & ":" & Port_Type'Image (CLP.Next_Port));
Make sure that both Incoming_Channel and Outgoing_Channel have a valid value before they are used in subsequent read and write operations. Once your code works, you can use the command-line options: [-a {IP address of this node : String }]
[-n {IP address of next node : String }]
[-p {This node's port : Port_Type }]
[-q {Next node's port : Port_Type }]
to test your ring by starting two nodes on your own computer. For this, you open two terminals, navigate in both into the Executable directory of your current lab and type in one terminal: ./ring_node -p 50041 -q 50042 and in the other terminal: ./ring_node -p 50042 -q 50041 If this is working, try it again, with more terminals and more nodes. Remember - you need to match the port of each node with the next node, such that they form a ring. Don’t forget to commit and push your code to GitLab. What form of message passing did you exercise in this lab? Was this synchronous or asynchronous message passing? Is reading and/or writing to a channel potentially blocking? And if so: until when? You can conclude some of the answers from your working code. Research and discuss the options for the remaining answers with your tutor and classmates. Keen-eyed readers may have noticed there is an option -n for setting the IP address of the next node. This framework isn’t some toy implementation - it really does support connecting to other computers over a network. Unfortunately, while this is quite easy to do with the lab computers on campus, which are all on one local network, trying to make this work over the internet is rather painful, mostly due to something called NAT. If you’re lucky enough to share a local network with someone else taking this course - or you’ve set up some VPN software like Hamachi - or you’ve set up port forwarding - then try forming a ring with a node on someone else’s computer. Otherwise, don’t worry about it: it’s almost the same as running a ring inside your computer. Exercise 2 (advanced): Foreign languages Using your second favourite programming language, program a ring node that follows the same protocol as we provided. BSD Socket interfaces will be available in all self-respecting languages, but you need to make sure that you will conform to a common message format. If your second favourite language is not flexible enough to produce the current format, you can also change the format on the Ada side. For that you might look into the Interfaces.C packages. If you do this and get it working, push it to GitLab and let your tutors know - we like seeing what languages people use here! Outlook An understanding of how network sockets behave and how to handle dealing with several of them through concurrency will serve you well as you tackle the second assignment. You can look up reserved numbers around the Internet at http://www.iana.org/ - or, if your computer runs Linux, macOS, or similar, you can also check out the file /etc/services on your computer. ↩ in their short paper: An improved algorithm for decentralized extrema-finding in circular configurations of processes; Communications of the ACM, Volume 22 Issue 5, Pages 281-283, May 1979 ↩ Updated: 27 Oct 2021 / Responsible Officer: Director, School of Computing / Page Contact: Josh Milthorpe Contact ANU Copyright Disclaimer Privacy Freedom of Information +61 2 6125 5111 The Australian National University, Canberra CRICOS Provider : 00120C ABN : 52 234 063 906 You appear to be using Internet Explorer 7, or have compatibility view turned on. Your browser is not supported by ANU web styles. » Learn how to fix this » Ignore this warning in future
