CSL374 Fall 2011: Assignment on bandwidth probing

In this assignment, we will create some bandwidth probing tools for the GPRS/EDGE data connections on our Blackberry and Nokia mobile phones. We will run two classes of tests, based on whether or not we have access to another endpoint on the Internet to which we want to measure different performance metrics.

Set 1: Third-party servers

  1. End-to-end latency: You know that this can be measured by a simple ping test, but since the Blackberry phones do not allow programming of raw IP packets, we will use what's informally known as an HTTP ping. Just like a GET method, HTTP also has a HEAD method to which the server sends an empty reply. You should write an HTTP client that makes a number of HEAD requests for this file and reports back the average latency (and standard deviation) in getting a reply. Do this with persistent and non-persistent HTTP connections. Do you notice a difference? Why? Why do we use a HEAD request and not a regular GET or POST request here?

  2. TCP download rate: This should be simple -- just download a file multiple times and report the average download rate. But is it really that simple? Write an HTTP client that uses the GET method to download a 2KB file multiple times from here, and gives the average download rate, and the standard deviation. Now trying doing the same experiment for a larger file of 70KB. Is there a difference? Why? Try the same experiment with a 5MB file as well.

  3. Variation with signal strength and time of day: Modify your HTTP clients for latency and download rates to also log the GPS location, time at which the measurements were conducted, and the signal strength. Then plot variations with time of day and with the signal strength. Do you notice any trends? You can also consider using heat map APIs to plot the trends on a map.

Set 2: Custom services on the servers

We have written a UDP server that can be used to bounce back packets, something like PING but more flexible. Clients can send UDP messages of varying lengths, and the server reports back with a timestamp of when it received each packet. Clients can also request for responses of different lengths. For ease of programming, each UDP packet can be marked as having a sequence number within a train of packets, for example, you can generate a packet train of 10 packets where each packet will have a train identifier embedded within it, and a sequence number from 1..10 within the train. This can be used to create some very interesting bandwidth tests, but before we go there, let us study the protocol we have implemented.

Packet format: Clients can send two types of UDP messages -- ECHO and STAT. ECHO messages are like PINGs, tagged with a unique (train identifier, sequence number within the train) tuple for each packet, and request the server to reply back with a packet of a desired length.

            Method: ECHO
            Id: 12345678
            Seqno: 2
            Length: 1024
            Padding, pad-character = SPACE

This notifies the server that the ECHO message is part of a train of packets with an identifier 12345678, a sequence number of 2 within the train, and that the server should reply back with a packet of length 1024. If you indicate a length of 0, then the server will not generate a reply at all. The ECHO message can also be padded with SPACE characters, to create large request packets with a maximum size of 10KB. Thus, you can effectively throttle the uplink by sending large ECHO messages, but not request for a reply. Similarly, you can throttle the downlink by sending small ECHO messages and request for large ECHO replies. For formatting purposes, note that each header line is terminated with a NEWLINE. The reply of the server to these ECHO messages is similar:

            Method: ECHO
            Id: 12345678
            Seqno: 2
            Time: 172583863532899
            Padding, pad-character = SPACE

The reply contains a timestamp (in milliseconds) of when the server received the message, and details of the identifier and sequence number of the ECHO request. If the requested packet length is greater than the space taken up by the different headers, the server pads the extra bytes with SPACE characters. Note that UDP is an unrealiable protocol, so it is possible that you may not get replies to certain requests, either because the request was lost or the reply was lost. Note also that the identifier, sequence number, and timestamp are all of the long type.

We next describe the STAT message. This becomes relevant if a bunch of ECHO packets are sent as part of the same packet train, ie. ECHO messages with the same identifier but different sequence numbers. The server replies back with a cumulative statistic of when each message was received. The STAT request looks like this:

            Method: STAT
            Id: 12345678

The STAT response will contain the following:

            Method: STAT
            Id: 12345678
            RESP: 1, 172583863532896
            RESP: 2, 172583863532899
            RESP: 3, 172583863532902

Each RESP line here indicates the timestamp at which a particular sequence number was received. You can create packet trains of up to 24 ECHO packets, and then use the STAT request to get back timestamps of all the requests. This is especially relevant if you turn off replies from the server for a few messages in your packet train. Note that it is possible that the reply could contain messages in a different order than how you would have dispatched the requests. Why? Also note that the client and server have different clocks, so rather than use the absolute timestamps that are reported, you should always work with relative values such as the inter-arrival time of consecutive packets, or the round-trip times between ECHO packets and replies.

Running the tests: The server is running at public IP 124.124.247.5, port 9010. You will have to write UDP clients on your Blackberry and Nokia devices to run the different tests described next.

For your help though, you can also download the server and sample client packages here, and try to write some local tests to become familiar with the protocol before you start programming on the mobile devices. You can start the server as: bash runserver.sh [port number], where [port number] indicates the port number at which you want to run the server, the default being 9010. A sample client program is also given that can be executed as bash runclient.sh. By default this connects to a server running locally on port 9010.

Do the following tests:
  1. Buffer size estimate: In GPRS networks, your mobile client communicates to the Internet via a special gateway called GGSN (GPRS gateway serving node). Like any other router, the GGSN has internal buffers but we do not know whether these buffers are maintained per source or is there one common buffer for all sources communicating through the GGSN, what is the maximum buffer size, what is the packet dropping policy of the buffer, etc. You can find out the buffer size by sending a large train of packets dispatched back-to-back, and track which packets are received at the server. The GGSN will start dropping packets when the train size gets bigger than the available buffer size. Note that back-to-back packets can be sent by making UDP send calls followed by a flush. So, start with 512 byte packets with 5 packets sent back to back, then repeat with a larger number of packets. Report the buffer size and dropping policy you were able to identify. Does the buffer size change with time? Can this tell you something about whether a common buffer is maintained at the GGSN, or per-source buffers?

  2. Buffer drain time: Once you identify the buffer size, let us find out the buffer drain time. You can do this by sending two consecutive packet trains with a gap between them, the gap being such that all packets from both the trains get through to the server. Keep in mind that GPRS supports a maximum throughput of around 150Kbps, so if you identify a buffer size of 20KB (for example) then you should start probing with a train gap of around 1 sec. Find out the buffer drain times and repeat your experiments at different times of day.

  3. Uplink Vs. downlink: The experiments above find the buffer behaviors along the uplink. How can you design experiments to find the downlink buffer behavior? Hint: Send small uplink packets and request the server to respond with bigger packets to flood the downlink. Find out the buffer sizes, dropping policy, shared or per-source buffers, drain times, etc for the downlink.

  4. Transport layer throughput: The buffer size and drain times above will effectively give you the uplink and downlink throughput that GPRS supports. Compare this with the TCP throughput you found out earlier in part-1 of the assignment. Do you notice any differences? Also compare with another way to find out the throughput by simply sending a small train of packets and find out the difference in arrival times of the first and last packet in the train. Report if you observe any differences in the three ways of measuring the throughput. Why do you think there are differences? Does this give you any ideas to design your own transport layer protocol that could potentially work better than TCP?

  5. Scheduling:The GGSN would be serving multiple sources, and would hence be following different policies to schedule transmission across different flows. It could be using a common queue to serve packets in a FIFO manner, or it could be using multiple per-source queues and do a round robin across different queues dispatching one packet from each queue in each round, or two packets in each round, etc. We want to find out the scheduling behavior being followed by the GGSN. You can do this by using a cool technique called packet-pairs: Send a pair of tiny packets with a small spacing between them and observe the spacing at which the packets are received at the server. If you see that the inter-arrival spacing varies widely for the same inter-dispatch spacing, it probably means that there is a shared queue and cross-traffic creeps in between the pair of packets. Using the aggregate throughput measurements you have done above, can you find the amount of cross-traffic at different times of day? On the other hand, if the inter-arrival spacing does not vary for different inter-dispatch spacing, it probably means that there are multiple per-source queues and the GGSN schedules multiple packets together from each queue. In this second case, you can start to alter the size of the packet pairs, or even send packet triples and quadruples to find out how many packets (or how much data) does the GGSN schedule in each round from every queue. Report your observations and inferences by plotting the inter-dispatch times against the inter-arrival times. Experiment with packet pair gaps of 1, 10, 50, 100, 500, 1000ms; and packet sizes of 32, 64, 128, 512, 1024, 2048 bytes,
Note that whenever you give measurements, do not just report one value but the average/min/max/std. deviation that you have observed. This holds for all the experiments above, including the buffer sizes, drain times, throughput, etc.

References

  1. httping
  2. Tools for bandwidth measurement
  3. J. Strauss, D. Katabi, and F. Kaashoek, "A Measurement Study of Available Bandwidth Measurement Tools", IMC 2003