ANU - CECS - COMP2310/6310 Assignment 2, 2013 COMP2310/COMP6310: Concurrent and Distributed Systems Semester 2 2013 COMP2310 Assignment 2: Network Simulator Deadline: 17:00 on Friday 25 October (Please report any errors, omissions and ambiguities to the course lecturer) (Amendments to this document after its release will be marked in blue) This assignment is worth 12% of your total course mark. It will be marked out of 24. Submission This assignment must be submitted electronically. This can be done using the following commands (according to your enrollment): submit comp2310 ass2 netSim.c submit comp2310 ass2 NetSim.java (and similarly for comp6310). NetSim.java may be submitted if part or all of the solution is written in Java. Extensions See the course Assessment page. How Late Penalty from 24 Marks less than 5 hours -0 between 5 and 7 hours -2 between 12 and 24 hours (1 day) -4 between 24 and 48 hours (2 days) -8 between 48 and 72 hours (3 days) -16 more than 72 hours (4 days) -32 (forget it!) Note: no extensions will be given for system downtime after the deadline! Submit what you have before the deadline as a precaution! Objectives To implement a concurrent algorithm using two Posix-based concurrency architectures: forks and sockets (or other form of IPC). To gain experience in Unix system calls and libraries related towards communication and concurrency, including using appropriate defensive programming methods. To gain insight into aspects of distributed computing, including the concepts of packets and routing, issues arising from lack of a global centralized time and in reliability. Background Networks are a fundamental element of CDS and indeed of computer science in general. In this assignment you simulate basic routing mechanism on nodes in a network, with processors simulating network nodes and messages on sockets (or any suitable form of IPC) simulating packets. Problem Description A packet can be modelled as a message with the following fields: srcAddr: source address destAddr: destination address msgLen: message length msgId: message id pktId: packet id The message id (initially 0) increases by 1 one as each message is sent from a particular source address and the message length is in the number of packets of the message, i.e. 0 ≤ packet id < message length . The payload (data) of each packet need not be modelled (we also assume that the payload size is fixed across all packets). The addresses would in real life be an IP address; we will abstract this and simply use an non-negative integer id (although on one level, IP address are unsigned 32-bit integers anyway). We will ignore that in packet address, a port number is a component of an address (we could imagine that the port number is encoded in msgId). The network of p nodes will have node id i in the range 0 ≤ i < p; its connectivity is represented by the ith entry of the node table, which has the format (across a line of text): ni idi,0 .. idi,ni-1 where idi,j, 0 ≤ idi,j < p, is the id of the node connected on the j link of node i. The ordering of these ids is not significant, i.e. a link is defined by only its endpoints {i, idi,j}. It may be assumed that there are no duplicates in idi,0 .. idi,ni-1, and i ≠ idi,j. The network will be specified in a text file containing p on the first line and the respective lines of the node table on the next p lines. For example, 4 nodes connected in a square would be specified as:
4
2 3 1
2 0 2
2 3 1
2 0 2
Note that the order of node ids across each line is not significant. Time across the network progresses in units of a jiffy. There will be one jiffy of delay between when a node receives a packet and when it sends it. There is also one jiffy of delay between the sending of packets on the source node of a message. A network schedule of is a list of messages with items in the following format: time srcAddr destAddr msgLen where time is in units of jiffys and is the (local) time when node srcAddr sends the first packet of a message of length msgLen to node destAddr (if this time has already passed, the message should sent as soon as possible). The special entry: t -1 -1 -1 will cause termination of all processes at (or as soon as possible after) local time t It may be assumed that time is non-decreasing as we traverse down the list, that srcAddr ≠ destAddr, there is at most 1 message per srcAddr per timestep and msgLen ≤ 4. Example network specification files and schedules will be made available on partch:/dept/dcs/comp2310/public/ass2; the utility program genNetConf in the CS Linux student system can be used to generate network specification files from common network topologies (i.e. ring, tree, star, mesh); type the command genNetConf for how to use it. Requirements If you submit netSim.c, it must launch the simulation, i.e. when compiled, it must have the following synopsis: $ netSim netFile schedFile If you submit only NetSim.java, it must launch the simulation with the synopsis: $ export _JAVA_OPTIONS="-XX:+UseSerialGC" $ java -cp NetAux.jar:. -ea NetSim netFile schedFile Here netFile is the name of a text file containing a network specification, and schedFile is the name of a text file containing a network schedule. Launching the simulation must involve creating a group of p processes (possibly including the initial process) which each simulates one node of the network. Each process must initiate messages according to the schedule in schedFile, and forward any packets it receives to an appropriate node. Sockets are recommended for the passing of packets, although any form of IPC may be used. When possible, all messages must be (eventually) delivered; indeed, it is desirable they get delivered along a path of shortest distance. Please note the following for your program: it may assume that netFile and schedFile are in the correct format and that netFile has been generated by genNetConf. it use the netAux library (or netAux class, which has methods of exactly the same names and signatures) to get the value of the network jiffy, and to log the sending and receiving of messages and packets. Your code should produce no other output. They will be tested on a 4-core Linux machine like those in the CS student labs, so make sure it works on these machines! They should be written with good programming style (C code should not produce any warnings when compiled with the -Wall option!). They should be well commented and formatted to a standard width of 80 characters, so as to enable the reader (this includes your tutor/marker!) to both easily read it and understand how it works. Identifiers should be meaningful and (unless their role is trivial) commented where declared, any constants should be named rather than hard-coded, and defensive programming should be used. The latter includes checks being made for system calls that can fail due to resource limitations (anyting that creates a file descriptor or process); once detected, a message should be generated with a call to the system error function perror() and the process should exit with a status of 2. It also includes using assert to perform other kinds of checks (including overflow of any fixed-length data structures that you use). All file descriptors should be closed before the process exits. All submitted files must have a preamble making a declaration about the work you have submitted. The provided template files (netSim.c, NetSim.java) come with such a preamble. You must add your name and student number where indicated. If you need to modify the declaration, e.g. you did in fact receive substantial assistance from another person who is not course staff, you should modify the text to say so. Code obtained from the internet will receive no marks even if acknowledged. The solution on the problem on all the given network topologies is non-trivial. You can simplify the problem by restricting msgLen = 1, and use restricted topologies (e.g. a ring and star) and still gain 60% of marks Compilation and Running Codes On and Off-site, Java API On the CS student system, the commands $ gcc -Wall -I $COMP2310/include -o netSim netSim.c $COMP2310/lib/netAux.o For those who will use Java, please contact Brian (brian.lee@anu.edu.au) with your UniID first so that we can organize your account setting. After the change, the commands $ export _JAVA_OPTIONS="-XX:+UseSerialGC" $ javac -cp NetAux.jar:. NetSim.java should be sufficient to compile the respective programs. To run offsite, download the netAux.h, netAux.c and/or NetAux.jar file to your working directory. The commands to compile the C and Java program is now: $ gcc -Wall -o netSim netSim.c NetAux.c $ javac -cp NetAux.jar:. NetSim.java The standard Java classes ProcessBuilder (a combined fork/exec), Socket, and Selector may be useful for this assignment. There are tutorials for Java sockets (also text Coulouris et al, sect 4.2.2, 4.2.4) and select too.
