Description
1. Purpose: In this assignment, you will become more familiar with the another type of IPC: messagepassing via message queue/mailbox and the use signals. In addition, you will also learn about interruptdriven programming (via alarm and I/O signals).
2. Background: In this assignment, you will simulate the basic mechanism of TCP (TransmissionControlProtocol)protocol that is commonly used for sending data through the Internet. TCP enables two processes running on any Internetconnected machines to exchange data. In this assignment we will only simulate the way the protocol is used to exchange data between different processes on a single machine. We will also only implement a very simple version of TCPstyle messagepassing without many of its core features. 2.1. Packets In general, the data that is sent through a packetswitched network is broken down into one or more packet (s) depending on the data’s size and the packet’s size (the packet size is fixed). Each packet consists of some header fields and data. The header fieldsmayconsistofinformationsuchasthesender’s identity, packet number, length of data encapsulated in the packet, etc., while the data stored is theactual content of the message. Figure 1 shows an example of a single packet.
In this specific example, the message is the top figure. Below this depicts a single packet (#5) of the message. The maximum size ofdatathatcanbestoredinasinglepacketis32B.Thus,ifthetotalmessage is 170B, the sender needs to send 6packetsintotal(5containing32Bofthemessageand1containingthe last 10B of the message). On the receiving side, the receiver will also receive the message as a series of packets and deliver the original message by combining each individual packet’s data in the correct order (#1, #2, .. #6). In the Internet (and in our lab), the packets may arrive to the receiver in an arbitrary order! While receiving each individual packet, the receiver needs to notify the sender that the packet has been successfully received, which is called anacknowledgement (ACK )thatisalsoenclosedinapacket.Ifthe sender does not receive an ACK foranyofthetransmittedpacketafteracertainamountoftime,thesender will TIMEOUT and resend every packet whose ACK has not yet been received (i.e. acknowledged) by the receiver. This mechanism is used to handle various issues in computer networks such as packet loss (Figure 2a), corrupted data, etc. 1
2.2. Sliding Window Sending a single packet at a time may result in a long total time to send the whole message if onepacket must be acknowledged before the next is sent. Thus, it is desirable to send multiple ( n) packets simultaneously and wait for multiple ACKs at a time. A group of packets that is sent together is called a window (of size n). Figure 2a has a window size = 1 and Figure 2b has a window size = 3. While sending multiple packets at a time is desirable, this may lead to an issue where the receiver may receive the packets unordered. This may happen since any of the packetsmaygetlostinthemiddleofthe network or transferred via slower network path. Thus, the receiver has tobeabletoconstructthemessage even if the packets come in a random order. In asliding window protocol, the sender can send another packet whenever it receives anACKforasentpacketinsteadofwaitingforallACKstoarrive.(InFigure2b, the sender can send packet 4 right after it receives an ACK for an earlierpacket,e.g. packet1).Thus,the sliding window protocol allows the sender to have at most n packets in transit (i.e. not acknowledged) ata time. Initially when the window is empty, n packets will be sent together. After this, packets are sent when ACKs arrive to maintain the window n . 3. Description: In this assignment, you will implement several APIs (inprocess.candprocess.h ) that willbecalledby an application program to exchange messages using the protocol discussed in the previous section. This program can act as a receiver, sender process, or both. We have provided an application program, application.c , that will use the APIs defined in process.c . When we refer to sender or receiver process this istheapplicationprogramoperatingaseitherasenderorreceiveratthatpointintime.There are 3 APIs/functions that will be called by the application program: 1. int init(char *process_name, key_t key, int wsize, int delay, int to, int drop); The init API is the initialization function that needs to be called before callingsend_messageor receive_message . API There aretwofunctionsperformedbyinit .First,itwillcreateamessage 2
queue for the given key and save the application process’ information (pid, process’ name, and mailbox id) to a file that is shared totheotherprocessesthatmaywishtocommunicatewithit.The pid will beusedtosendasignaltoanotherprocess,theprocessnamewillbeusedtonamethefile, and the key will be used to get the process’ mailbox. The mailbox is the place where a sender process sends packets and a receiver process retrieves packets. There is a mailbox created for each process that callsinit . Second,itwillsavethemessageconfiguration(wsize :windowsize, delay : maximum delay, to : timeout, and drop : drop rate) and set signal handlers (SIGIO and SIGALRM) that will be used throughout the program. A SIGIO signal will be sent by the sender process usingkillto indicate that a new packet has been placed into the receiver’s mailbox. This willbehandledbythereceive_packet(intsig) function. ASIGALRMsignalisusedtoindicateaTIMEOUT.Wheneverthesenderprocesssendsapacketto other process’ mailbox, the sender willsetaTIMEOUTandwaitforanACKfromthereceiver.Ifthe ACK is not received before the TIMEOUT expires,thesenderwillresendanypacketswhoseACKs have not yet been received (this is handled by the timeout_handler(int sig) function). 2.int send_message(char *receiver, char* content); This API is used to send a message to another process. To send a message to another process: the sender process first has to obtain the receiver’s information (pid, and mailbox key) from the receiver’s file (named with the receiver’s name,receiver ), break down the message (content ) into one or more packets, send each packet to the receiver’s mailbox, and send a SIGIO signalto the receiver. The sender needs to set a TIMEOUT and wait for ACKs from the receiver toindicate whether the packets have been successfully sent. 3.int receive_message(char *data); This API is used to indicate that the program is ready to receive a message from any sender. If there is more than one sender that triestosendamessage,onlythemessagefromthefirstsender will be read. Any other senders will TIMEOUT and cancel sending the message. In this function, your program shouldpause/block until a SIGIO message isreceived,indicatingthatthereisanew packet in the mailbox. The program should save the content of thepacketandsendanACKtothe sender. Once all packets are received, the message will be saved to the data and returned. In this assignment,youaregiventheapplicationprogram(application.c )whereitwillcalltheinitAPI, and perform as a sender/receiver depending on the user’s input. A sender process will call the send_message API whereas a receiver process will call thereceive_message API. All The tasks you need to implement are as follow:
Part A (60 points) 1. Initialization The application program ( application.c ) takes 6 inputs from the user: 1. Name: the process name (you can assume there is no other process with the same name) 2. Mailbox key: the key of the mailbox 3. Window size: the size of the window (you can set it to 1 for this part) 4. Max delay: maximum delay in sending an ACK (in seconds) 5. Timeout: maximum waiting time to resend a packet (in seconds) 6. Drop rate: the probability of a packet to be lost (in %) When the program gets these parameters, it will pass these inputs to the init API which will save the name, mailbox key and pid to a file and set the configuration of the messaging mechanism.
3
The program provided inapplication.cwaits for the user’s input viascanf() toperformwhetherasa sender or a receiver. A sender process requires two other inputs from the user: 1. the receiver’s name, 2. the message. On the other hand, a receiver process will wait/block until it receives a new message in its mailbox. 2. Sending a Message A message that is provided by a usermayvaryinsize(<MAX_SIZE).Whilegettingamessage,thesender will: 1. Break the message into one or more packets. 2. Send each packet to the receiver’s mailbox using a sliding window. 3. Send a SIGIO signal, which will notify the receiver that a new packet has arrived to the mailbox. 4. Set an alarm as a TIMEOUT. IfthereisaTIMEOUT,resendallsentpacketswhoseACKshavenot yet been received. 5. Wait for an ACK for each sent packet. The basic structure ofthepacketisgiveninfileprocess.h ,whichcontainsthetypeofpacket(DATA/ACK) and the sender’s name. Once all ACKs have been received,theprocesswillwaitforanotheruser’sinputto determine whether to send a new message or wait for a message from another process. 3. Receiving a Message When the receiver gets a SIGIO, the receiver will retrieve all packets sent to its mailbox and reply toeach received packet with an ACK. In constructing a message, the receiver needs toknowwhetherthepacketit receives is a new packet or a duplicate (duplicates may be sent by the sender if an ACK for the packet is delayed and causes thesendertoretransmitafteraTIMEOUT).Inaddition,thereceiverneedstodetermine whether the packet belongs to a new message, or an uncompleted message, or a duplicate for an old message. Once the message has been successfully constructed, the process will print the message tothe standard output and wait for another user’sinputtodeterminewhethertosendanewmessageorwaitfora message from another process. NOTE : To simulate packet loss inthenetwork,weprovidedadrop_packetfunction(aprobabilityfunction that may drop apacket)thatyoumust usewhenreceivingapacket.Inaddition,wealsoprovidedadelayin responding to a packet. These two conditions are used to triggeraTIMEOUTatthesenderside.Thereare no TIMEOUTs within the receiver process.
Part B (30 points) 1. Sliding Window In this part, youwillimplementaslidingwindowmechanism,i.e.,thesenderneedstoensurethat n packets are in flight at a time, where n is the size of the window. Once an ACK isreceived,thenextpacket(ifany) will be sent right away. As mentioned in Section 2, sending n packets at a time may result in an random arrival order of packets. Thus, your receiver has to be able to put the data content of each packet in the correct order in assembling the message. NOTE : To simulate the random arrival order of thepackets,yoursendermustusetheget_nextfunction that we provide. This function will return a packet number that you need to send next.
Part C (10 points) 1. Error Handling & Robustness You should handle any possible errors for:
4
● System call failure. ● Memory leak (you have to free any allocated memory when it is no longerneeded).Youmaywant to use Valgrind to check if your program has a memory leak problem. ● When a sender is trying to send a message to an unavailable receiver, the sender shouldretryon TIMEOUT until a maximum number of TIMEOUTs (MAX_TIMEOUTdefined inprocess.h ). Once the number of TIMEOUTs reaches the MAX_TIMEOUTthreshold, the send_message API will return and the application program will wait for new user input. ● If there are multiplesenderssendingmessagestothesamereceiverconcurrently,thereceivermay simply ignore the message from the later sender. This should cause the later sender to timeout.
2. Documentation You must include a README containing the following information: ● Your group ID and each member’s name and X500. ● How to compile and run your program. ● A brief explanation on how your program works. In addition you should also address these questions: ● What is the effect of having a very short TIMEOUT period and a very long TIMEOUT period? ● What is the effect of having a very small window size (e.g., n=1) and a very large window size? Within your code you should use one or two sentencestodescribeeachfunctionthatyouwrite.Youdonot need to comment every line of your code. However, you might want to comment portions of your code to increase readability. At the top of your README file, please include the following comment: /* CSci4061 S2016 Assignment 3 * Name: , * X500: , */ 4. Simplification: ● You may assume that the process name for every process at a given time is unique. ● You may assume that the message is a null terminated stringwithout any spaces atthesender side. Therefore, the message must be null terminated when returned to the receiver. 5. Miscellaneous: ● As in lab #2, we have given some complete functions, and some partial functions to help you. All datatypeshavebeenprovided.Youarefreetoignoreorchangeoftheprovidedcodeifyouwish.In particular feel free to optimize. ● Useful functions: memcpy, sigprocmask, alarm, kill, msgrcv, msgsnd,msgget, signal/sigaction, pause, getpid ● alarm(0) turns off any pending alarms ● Be aware of race conditions: block signals to handle these cases as needed ● Remember to reset any global state once messagepassing is done to enable new messages as needed
5. Test Cases: All tests will be done in a CSE labs UNIX machines. So, you need to make sure that yourprogramcanbe compiled and run using one of those machines. You may consider these following cases for testing:
5
● Invalid process information. ● Short/long message with small/large packet size. ● Multiple processes that exchange data between them in a sequential order (e.g.:A→B,C→A,B → A, B → C). In this scenario that application instance at runs A, B, C respectively can keep running and change whether it is a sender or receiver based on user input. ● Handle packet loss (both in sending DATA and ACK) and delay. ● Handle unordered packets. ● Handle duplicate packets (you should also consider the case where a duplicate packet isreceived when the message has already been completed).
6. Deliverables: 1. Files containing your code 2. A README file (readme and c code should indicate this is assignment 3). All files should becompressedintoasingletarfile,namedassignment3_group.tarand submitted through Moodle. This is your official submission that we will grade. We will only grade the most recent and ontime submission. Failing to follow the submission instruction may result in a 5% deduction.
7. Sample Snapshot: The sample program below was run with a packet size = 4. Sender: Receiver:
