Advanced Internet Services - CS 6998-03: Homework 2

Please submit your solutions by email to the TA by the due date of Tuesday, March 3, 1998, end of day.

  1. What is the signal-to-noise ratio (in dB) for a 16-bit linear quantizer, assuming that all amplitude values are equally likely (i.e., equally distributed)? Use the integral expression given in the course notes. (Further information is given in a brief note.)
  2. Write a program to measure the signal-to-noise ratio (SNR), in dB, of the GSM (full-rate) voice codec for a real speech sample. The codec is available after 1 and 2 iterations of the codec. Thus, perform two experiments:
    1. toast and untoast and compute the SNR;
    2. toast, untoast, toast and untoast and then compute the SNR.
    In each step, you use the output of the previous step.

    The coder and decoders are called toast and untoast; they are part of the source distribution mentioned there. For Solaris, binaries can be found at CUCS at ~hgs/sun5/bin/toast and ~hgs/sun5/bin/untoast; for other platforms, you will have to compile it yourself. You might want to ask on the class bulletin board if you suspect that somebody else has already a version for your platform. (Also, the GSM web page has a pointer to a DOS version.) You should take the /usr/demo/SOUND/sounds/sample.au file (also available here) as your input. Be careful that you measure the SNR for 16-bit linear encoding. The sox program (~hgs/sun5/bin/sox) can help you convert audio formats. A local copy of the man page is available. Sox calls the 16-bit files "raw" audio files. The file size of a 16-bit file should be slightly less than twice that of the original, mu-law sample.au file. "Raw" 16-bit audio files don't have the initial audio file header. After decompression, a file may get somewhat longer since GSM compresses audio in blocks of 20 ms (160 samples) and pads the input file as needed. When comparing files of unequal length, compare only the common beginning - not that this would make much of a difference in the overall result.

    You will need to extract sound samples from the input and output (after compressing and decompressing) audio file. It is probably easiest to use the 16-bit output produced by either untoast or sox, rather than working directly with .au files.

    In case you are interested: The format of Sun .au files is explained in the Solaris header file /usr/demo/SOUND/include/multimedia/audio_filehdr.h and the sound file FAQ, part 2.

  3. Using Kruskal's algorithm (or whatever else you are familiar with from your data structures class), construct a minimum spanning tree for the network below:
    You can either write a program or execute the algorithm by hand and show your intermediate steps and final result.
  4. Using the network from the previous problem: Assume the source is at the top left corner of the network. Construct a source-based tree that minimizes delay. Compare the number of links, the total link cost and the average cost (delay) that it takes to distribute a packet to all other nodes to the minimum spanning tree computed in the previous problem. (The link costs are as shown on the figure.)
  5. Assume that a single host on a local network wants to join a multicast group via IGMP. No other host on the local network is a member of this group at that time. Unfortunately, this LAN has a high packet loss probability of p = 10%. According to the IGMP Version 2 specification (RFC 2236), the host sends two Membership Reports within ten seconds and then waits for the General Query issued by the router every 125 seconds. To simplify the calculation, assume that the Max Response Time is zero, i.e., the host responds immediately after receiving a GQ.

    You may assume for simplicity that the host joins "in the middle" of a General Query interval, i.e., the general query takes place 52.5 seconds after the host joins the group. (See Kleinrock, Queueing Systems, Vol. 1., p. 169f, if you want to know the mathematical details.)

    What is the average time until the host can receive multicast packets? Note that older textbooks typically describe version 1 of IGMP, with a fixed delay between a General Query and the host answer.

  6. Write a simple RTP packet audio receiver. RTP (RFC1889, and RFC1890) will be explained in detail in one of the next classes, but, for now, it suffices to know that it uses UDP/IP and that the header looks like shown below, with all fields in network byte order. One line in this ASCII figure represents 32 bits. 
     0                   1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|V=2|P|X|  CC   |M|     PT      |       sequence number         |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                           timestamp                           |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|           synchronization source (SSRC) identifier            |
+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+
|            contributing source (CSRC) identifiers             |
|                             ....                              |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    You can ignore all but the sequence number, timestamp and SSRC fields for now.

    The receiver should listen at a multicast address specified as a dotted decimal (e.g., 224.2.0.1) on the command line and display the arrival time (Unix gettimeofday() values, that is, seconds and microseconds since Jan. 1, 1970), SSRC (in hexadecimal), timestamp, sequence number to stdout. (The next assignment will then add the playout delay mechanism and the previous programming assignment to actually play back audio samples to the speaker.) We will set up an audio transmitter on the CS local area network for testing purposes. The transmitter sends data to multicast address 224.2.0.25, port 1234. If you are outside Columbia, you can install, for example, the vat audio tool to send multicast for a variety of platforms. (Most recent versions of Unix and Windows'95 and NT can send and receive multicast, at least within a LAN.) If you use vat, be sure to start it in RTP mode, that is as "vat -r destination/port". Your multicast receiver and vat must be on different hosts, since vat disables local echo.

    A line of output from your program might look like this: 

    849847.483848 8c3a5d21 1020 17
899847.503000 8c3a5d21 1180 18
    Your assignment should contain about 10 lines of output.