21.3 UDP Implementation with One Program and One Receiver
| Team-FLY |
| This section discusses an Internet Radio implementation using UDP. UDP is an unreliable protocol in which messages may be delivered out of order. Start by assuming that the protocol is reliable with in-order delivery (UDP approximately satisfies these assumptions on a LAN) and then modify the programs to take into account the behavior of UDP on the Internet. Table 21.1. Summary of Internet Radio project variations.
21.3.1 Simple implementationCopy Program 20.2, ( client_udp.c ) on page 699 into UDPRecv.c and compile it as UDPRecv . UDPRecv sends a message to a server and reads a response. Modify UDPRecv to receive messages of at most 1000 bytes after sending the initial message. The program should take an optional third command-line argument, the name of a file. If called with three command-line arguments, UDPRecv writes the received information to the specified file. Otherwise, UDPRecv writes the received information to /dev/audio . Copy Program 20.1 ( server_udp ) on page 698 into UDPSend.c and compile it as UDPSend . Modify UDPSend to take two command-line arguments: a port number and a file name. The UDPSend listens on the specified port for client requests . When UDPSend receives a request (any message), it opens the file and copies the file contents to the requesting host in 1000-byte messages. Since the Internet Radio application sends 8000 byte/second audio, UDPSend should sleep for one second after sending each eight messages. After sending the entire file, UDPSend waits for another request. For each of these programs remember to change the value of BUFSIZE from 1024 to 1000. Exercise 21.1How would the message size , number of messages per block and sleep time between blocks change for a file containing CD-quality audio rather than voice-quality audio? Answer: CD-quality audio consists of two channels of 16-bit values played at a rate of 44.1 kHz, which translates to a throughput of 176,400 bytes/sec or 1.4112 Mbps. With a 1000-byte message size, the sender must write an average of 176.4 packets per second. Sending 176 packets per second can result in underflow for long transmissions, whereas sending 177 packets per second can result in receiver buffer overflow. A packet size of 1225 bytes evenly divides the data rate and still fits within a typical Ethernet packet. In this case, the sender should send 144 packets per second. Exercise 21.2How does UDPRecv open the output file? Answer: The UDPRecv function opens the file by calling open with three parameters: the pathname, flags and permissions. The flags are O_WRONLY, O_CREAT and O_TRUNC . Set the permissions appropriately. Exercise 21.3How can you use UDPSend to send the file myaudio.au to remote receivers? Answer: Decide on a port number to use, say, 16001, and start the program with the following command. UDPSend 16001 myaudio.au Exercise 21.4Suppose the program from Exercise 21.3 is running on os1.cs.utsa.edu . How should you start UDPRecv to receive the transmission? Answer: UDPRecv os1.cs.utsa.edu 16001 Exercise 21.5What happens if you omit the call to sleep from UDPSend ? Answer: The program sends the file as fast as it can, limited by the speed of the network, the speed of disk access and the size of the network buffers. A client like UDPRecv does not buffer its input and the audio device can only handle eight messages a second. Once the buffers of the audio device are full, UDPRecv blocks while outputting to the audio device and may miss some of the transmission from the server. Exercise 21.6Suppose that as in Exercise 21.5 the input file contains a 30-minute radio program. How many bytes of buffer space does the receiver need to fully buffer the transmission? Answer: For 8000 byte per second audio, the receiver needs 30*60*8K = 14 megabytes. Exercise 21.7Modify UDPSend so that it sleeps for one second after every nine messages instead of eight. What does the output of UDPRecv sound like? What if it sleeps after every seven messages? Which is more annoying? Answer: If UDPSend sleeps after nine messages, it sends about nine messages a second. Since the receiver can only process eight messages a second, it misses about 1/8-second of sound every second over a long transmission, causing jumps in the audio. If UDPSend sleeps after only seven messages, the receiver sometimes blocks while waiting for input from the network and cannot keep the local audio buffer full. There would be pauses in the audio, sometimes in the middle of a word. The loss of 1/8 second of audio every second is annoying, but understandable for spoken audio. The brief pauses caused by sending the audio too slowly is sometimes more annoying. Of course, this judgment is subjective and you may judge differently. Exercise 21.8What drawbacks does sleeping for 1 second after every eight messages have in controlling flow? Answer: This sleep strategy does not take into account the overhead in transmitting the messages or the scheduling delays caused by other processes in the system. For example, if these delays average 100 ms for every eight messages, the server sends 1 second of audio every 1.1 seconds, causing slight pauses in the audio at the receiver. The POSIX description of sleep states that the suspension time may be longer than requested because of scheduling or other activity by the system. Exercise 21.9How could you fix the problem of an inaccurate data rate because of the inaccuracy of sleep ? Answer: Use a timer that generates an interrupt every second. Each time the interrupt occurs, send the required messages. You should avoid sending the information from the interrupt service routine. Have the interrupt server routine set a flag, and use sigsuspend to wait for the interrupt, as in Example 8.26. Consider using absolute time as discussed in Section 9.6. Exercise 21.10How would the original implementation behave under Test Case 1 and Test Case 2? Answer: Under Test Case 1, the receiver loses some of the transmission if it is delayed long enough. The amount lost depends on the amount of time the process is suspended , the size of the receiver buffers and the size of the network subsystem buffers on the receiver host. Under Test Case 2, the output file at the receiver is usually identical to the input file for senders and receivers on the same uncongested local area network. It takes the same time to write the data to a file as to the audio device because the sender limits the rate at which it transmits the data. 21.3.2 Termination of the receiverConnectionless communication protocols such as UDP do not indicate when the transmission is complete, so the receiver does not know when to terminate. There are several ways to handle the termination problem. The sender can transmit a special message reporting that it has sent all of the data. The special message must be distinguishable from audio data. Since in most audio formats, any data is possible, the special message might be embedded in the audio data. Alternatively, the receiver can use the timeout capability of UICI. If it receives no data in a certain length of time, say, 5 seconds, the receiver assumes that the transmission has ended and terminates. Receivers using this approach could terminate prematurely unless they use a very large timeout value. Another method relies on the atomic nature of UDP messages ”a UDP message is either received in its entirety or is not received at all. The receiver assumes that all messages except the last one are exactly 1000 bytes. If the size of the file is not a multiple of 1000 bytes, the last message has fewer than 1000 bytes and the receiver knows that this is the last message. If the file is a multiple of 1000 bytes, the sender transmits a message of length 0 after the last message. Copy UDPSend.c into UDPSendEnd.c , and copy UDPRecv.c into UDPRecvEnd.c . Modify these programs to transmit a zero-length message to signify the end of the transmission. Exercise 21.11Propose another method of termination that uses the atomicity of UDP messages. Answer: The receiver uses a receive buffer of size 1001 instead of 1000. The sender transmits a message of size 1001 after the last message containing data. If the receiver reads a message of size 1001, it knows that the transmission has completed. Exercise 21.12Under what circumstances does the solution proposed in Exercise 21.11 cause the receiver to not terminate? How can you fix this? Answer: UDP is an unreliable protocol, so the receiver never terminates if the last message never arrives. You can handle this problem by using u_recvfrom_timed with a very long value of the timeout, say, 30 seconds. 21.3.3 Buffering by the receiver to handle network latencyOne of the problems with streaming audio (or video) is that the transmission time may not be constant. Periods of heavy network traffic cause messages to be delayed or lost. For now we assume that the messages are received in order and never lost, but there may be short periods (equivalent to the time to play a few messages) in which no messages are received. The receiver can compensate for this uneven transmission by allocating buffers and filling many of the buffers before starting to play the first message. The receiver must fill the buffers from incoming network messages concurrently with the emptying and playing of the buffers. Exercise 21.13A naive approach to handling the buffers is for the receiver to alternate between reading from the network and writing to the audio device. What is wrong with this idea? Answer: Depending on the rate at which messages arrive , there may be times when a network message is available but the receiver blocks while waiting to write to the audio device. At other times, the audio device buffers may be empty and the receiver blocks while waiting for input from the network, even though there are process buffers containing data for the audio device. Exercise 21.14How would you implement a solution in which the receiver forks a child process that reads only from the network, filling the process buffers. The parent receiver process empties the process buffers, sending to the audio device. Answer: The process buffers must reside in shared memory, and the receiver parent and child must use interprocess synchronization mechanisms to access the shared memory. The receiver buffer problem is a standard producer-consumer problem involving two file descriptors that must be monitored concurrently. We discuss three possible solutions to this problem ” select , multiple threads and parent-child processes. In the first solution, the receiver calls select to determine which file descriptor is ready. The receiver has one descriptor for reading and one for writing in contrast to Program 4.12, which monitors two file descriptors for reading. Copy UDPRecvEnd.c into UDPRecvSelect.c and compile it as UDPRecvSelect . Modify the program to call select to monitor the two file descriptors. Preallocate NUMBUF buffers. Use a value of NUMBUF that corresponds to about 10 seconds of audio, and do not start sending anything to the audio device until at least half the process buffers are filled. Exercise 21.15What is a buffer overflow and what is a buffer underflow? How would you handle these conditions? Answer: A buffer overflow means that the network has available data but the receiver does not have a free buffer. Overflows occur when the sender produces data faster than the receiver uses it. A buffer underflow means that the audio device requires data but the receiver does not have any filled buffers. Underflows occur when the audio device uses data faster than the sender transmits it or when the network incurs heavy packet loss. When select reports that data is available from the network but no buffer is free, the receiver should block on writing to the audio device until a buffer can be freed. If this does not happen soon enough, the network subsystem may drop messages because its buffers are full. Similarly, when select reports that a write to the audio device would not block but there is no data to write, the receiver should block while waiting for data from the network. Since only a single process accesses the process buffers, the receiver does not have a critical section in the select implementation. However, the programming is still tricky, since the program can be in one of three states: only reading from the network (initially and when the buffers are empty), only writing to the audio device (when the buffers are full), and using select . The threaded solution uses a producer thread responsible for reading from the network and a consumer thread responsible for outputting to the audio device. Each thread just blocks when its input or output is not ready. Use Program 16.14 and Program 16.11 as models for your solution. Take care that the producer thread does not obtain exclusive access to the buffer before blocking for network input. Similarly, the consumer thread should not hold exclusive access to the buffer before waiting for audio output to return from its previous write. Copy UDPRecvEnd.c into UDPRecvThread.c and compile it as UDPRecvThread . Modify UDPRecvThread so that it implements the threaded solution. A third solution uses a child process to output to the audio device while the parent reads from the network. The process buffers can be implemented with shared memory, as described in Section 15.3. As in the threaded implementation, the critical sections that access the shared buffer must be protected. Copy UDPRecvEnd.c into UDPRecvShared.c and compile it as UDPRecvShared . Modify UDPRecvShared so that it implements the parent-child solution. The child process terminates when it has finished reading from the network. The parent terminates when the process buffers are empty and the child has terminated . Exercise 21.16How can the parent determine whether the child process has terminated? Answer: The parent checks to see if the child has terminated only when the process buffers are empty. A simple wait call blocks until the child finishes, leading to a deadlock when the buffers fill. Use waitpid with the NOHANG option, or catch the SIGCHLD signal and set a flag when the child terminates. Exercise 21.17What happens when the process that is sending to the audio device terminates while the audio device still has data in its buffer? Answer: The outcome depends on the system you are using. On some systems, if you exit while the audio buffer contains data, the audio stops. An explicit call to close on the audio device may block until the audio device buffers are empty. Exercise 21.18How would the three implementations of the buffered receiver behave under Test Case 1 and Test Case 2? Answer: All three implementations behave similarly under Test Case 1 and Test Case 2. Under Test Case 1, the receiver loses some of the transmission if it is delayed long enough; however, the amount lost would be decreased by the amount stored in the input buffer. Under Test Case 2, the output file should usually be identical to the input file if run on a local area network that was not too busy. Because the rate is determined by the sender, it takes about the same time to save the data to a file as to write it to the audio device. 21.3.4 Buffering by the receiver to handle out-of-order deliveryThe UDP protocol does not force in-order delivery of packets. Out-of-order packets are seldom observed on a LAN in which there is only one path between sender and receiver, but UDP packets are often delivered out of order on the Internet. The usual way to handle out-of-order transmission is with sequence numbers. Each message starts with a header containing a sequence number that is incremented by the sender for each message sent. For this part of the project, we assume that a 32-bit sequence number is sufficient. Exercise 21.19Suppose an 8000 byte per second audio stream uses 1000-byte messages. How long does it take for the audio stream to overflow a 32-bit sequence number? Answer: A 32-bit unsigned sequence number representation has 2 32 possible values. Since the audio stream sends one message every 1/8 second, it takes 2 29 seconds (approximately 17 years ) to wrap around. Exercise 21.20Suppose a 2-gigabyte per hour stream of video uses 1000-byte messages. How long does it take for the video stream to overflow a 32-bit sequence number? Answer: Using unsigned 32-bit integers, the video stream takes about 2100 hours (about 3 months) to overflow its sequence number. Exercise 21.21How would you design a message to contain a sequence number and 1000 bytes of audio? Answer: Prepend a 4-byte header to the message body so that messages are now 1004 bytes. The header represents the message sequence number in network byte order. Exercise 21.22The code segment below reads 1000 bytes of audio from the open file descriptor filefd and sends it along with a 32-bit sequence number to a remote host as a single UDP message. Aside from the lack of error checking, what is wrong with this implementation? #define BUFSIZE 1000 char buf[BUFSIZE+4]; uint32_t seq; r_read(filefd, buf+4, BUFSIZE); *(uint32_t *)buf = htonl(seq++); u_sendtohost(sendfd, buf, BUFSIZE+4, hostn, port); Answer: Some systems force integers to be aligned on word boundaries, and the declaration of buf does not guarantee word alignment. You can fix the alignment problem by using memcpy rather than statement assignment, as illustrated by the following code. uint32_t seqn; seqn = htonl(seq++); memcpy(buf, &seqn, 4); Exercise 21.23What happens if the sequence number is sent in one 4-byte message followed immediately by a 1000-byte message containing the audio data? Answer: This approach does not solve the out-of-order delivery problem. Even assuming the receiver reads a 4-byte message followed by a 1000-byte message, the sequence number in the first message might not correspond to the audio data in the second message. Exercise 21.24Design a buffer scheme for a receiver to store messages that might arrive out of order. Answer: A receiver with NUMBUF buffers places message number n into buffer slot n % NUMBUF . Each buffer slot has a flag, filled , that specifies whether the corresponding buffer slot contains unsent audio data. The receiver must prevent the following errors.
Exercise 21.25How should you modify the synchronization of a threaded implementation to support the buffer scheme described in Exercise 21.24? Answer: A typical threaded implementation based on Program 16.11 blocks the producer if no buffer slots are available. Modify this code so that the producer blocks after reading an item from the network if the corresponding buffer is not available. The consumer no longer blocks when totalitems is 0, but instead blocks if the next buffer slot is empty. Exercise 21.26The solution described in Exercise 21.25 has a potential deadlock. How could this deadlock happen and how could it be avoided? Answer: Suppose there are eight buffers. Sequence numbers 0 and 1 have been processed by the producer and the consumer . The producer receives messages with sequence numbers 3, 4, 5, 6, 7, 8, 9, and 11, missing both 2 and 10. The consumer blocks while waiting for message number 2 from slot 2 to be filled. The producer blocks while waiting for slot 3 to be emptied so that it can insert sequence number 11. The consumer should time out and move on to the next slot if the current item is not available when it is time to send the next packet to the audio device. For the scenario described in this exercise, the consumer removes message number 3, allowing the writer to put message 11 in the buffer. Copy UDPSendEnd.c into UDPSendSeq.c and compile it as UDPSendSeq . Modify UDPSendSeq to send 1004-byte messages with sequence numbers. Copy one of your implementations from Section 21.3.3 into UDPRecvSeq and compile it as UDPRecvSeq . Modify UDPRecvSeq to handle out-of-order delivery of messages. Test these together. Exercise 21.27How does the termination criterion change when sequence numbers are used? Answer: The receiver knows that the last message has been received if the message length is not 1004. A message of length 4 specifies the end, with no audio data in the message. The receiver terminates after reading this message once the buffer is empty. The receiver should also terminate under a long timeout condition when the buffers are empty. Exercise 21.28How does the synchronization in the threaded implementation of the receiver change when messages can be received out of order? Answer: The synchronization of the consumer is almost the same. The consumer now blocks when the filled flag of the next slot is clear rather than when nitems is 0. The producer does not know which slot is needed until it reads the message. One solution is to have the producer read a message into a local buffer, check the sequence number, and block if the corresponding slot is not available. Be sure to implement producer and consumer blocking in a loop that checks whether the blocking condition has changed. Testing the out-of-order receiver on a LAN is difficult since programs rarely receive out-of-order UDP messages. To test receiver handling of out-of-order messages usually requires that the messages actually be sent out of order. Copy UDPSendSeq.c into UDPSendSeqTest.c and compile it as UDPSendSeqTest . Modify UDPSendSeqTest to occasionally delay a message for 1, 2 or 3 messages. Use a separate buffer for a delayed message and an integer counter specifying how long to delay. You should also pick a threshold value between 0 and 1. If the threshold is 0, the sender transmits packets in order. For thresholds greater than 0, the sender transmits a greater fraction of the packets out of order. The sender sets the counter to 0 when it starts and checks the counter each time it is ready to send a message. A nonzero counter indicates that a delayed message exists. If the counter is greater than 1, the sender decrements it and sends the current message. If the counter is equal to 1, the sender decrements it and sends the current message followed by the delayed message in the buffer. If the counter is 0, the sender picks a pseudorandom number between 0 and 1. If the value is not below the threshold, the sender transmits the current message. If the value is less than the threshold, the sender places the message in the buffer and sets the counter to 1, 2 or 3 (at random). |
| Team-FLY |
EAN: 2147483647
Pages: 274