Supervision exercises: Computer Networking (2011)
These past supervision questions are for historical interest only. The current course has changed somewhat. Current students should find their supervision questions elsewhere.
This is the set of exercises for my 2011 supervisions in Computer Networking. This course primarily looks at practical aspects of the Internet, and so some of these exercises involve a practical component. These will help you gain important skills which you will probably find useful in the future, either in the real world or as part of your research. You will be pleased to know that the written exercises should be relatively quick to allow you time for the more fun pratical exercises.
Of course, exam questions will look nothing like this and may expect you to remember incidental facts from the lectures which are not covered here. I can't feasibly set a question on every single fact presented in the slides, but if you have specific queries please do ask, preferably in advance of the supervision so that I have chance to prepare some examples.
You are expected to produce solutions (written or typed) to all the relevant questions for each supervision and to email them to me at least 24 hours before the supervision starts. You may alternatively submit solutions on paper via the letterbox by Student Admin if you also email me so that I know to collect them—but consider the tradeoff between latency and throughput (allow an additional 24-48 hours and remember that Student Admin's postal service does not operate on weekends). It is often more effective to scan and email handwritten solutions than to rely on the postal service...
When emailing me regarding supervisions (or any other lab business) please only use my lab address, or your email will be misfiled and may slip by unnoticed:
- What is the OSI model used for? [2 marks]
- For the lower four layers of the OSI model, give for each:
- a brief description of the layer;
- an example from the Internet;
- where it's implemented in the Internet in interconnection equipment and end systems.
- Where would each of the following systems fit into the OSI model?
- a HTTP/HTTPS proxy server;
- a VPN (i.e. encapsulating encrypted IP packets inside another protocol);
- RFC 1149.
1.2. The Domain Name System (DNS)—practical
A tool called "dig" is used to interrogate DNS servers for debugging purposes. On a Linux machine (e.g. the PWF), familiarise yourself with the "dig" command, and in particular the "+trace" option which performs an iterative DNS query starting at the root servers and tells you the steps involved. ("man dig" will provide documentation.) If you don't have access to a machine with dig installed, there is a web-based version available (the "Trace" checkbox corresponds to the "+trace" command-line option).
Obtain a trace of the DNS delegation path (i.e. "dig +trace") for a DNS name of your choice (e.g. www.cam.ac.uk). Explain what the output means.
1.3. Wireshark basics—practical
Wireshark is a tool to capture network packets sent from and received by your computer. We will use it in future supervisions, but I would like you to familiarise yourself with it now by using it to capture a few packets of some simple protocol, e.g. a HTTP request and response. Print the packet trace in some form (a screenshot is fine) and point out what it shows you.
Wireshark needs administrative privileges to capture packets, so will not work on the PWF. You can install it on your own machine, though (it works on Linux, Windows or OS X). If you cannot get it to work, or do not have a suitable computer, let me know and I'll try to help.
2.1 Client/server vs. peer-to-peer
- Compare (briefly) the relative merits of client/server and peer-to-peer models. [4 marks]
- Classify each of the systems below as client/server, peer-to-peer or hybrid, and explain why the designers may have decided to implement the system in that way:
- The CST supervision system can be thought of as a peer-to-peer network. The department or your college acts as a rendezvous point or tracker, keeping lists of students and supervisors and enabling them to communicate directly, with the intention that the supervisor will pass knowledge (data) to the student. Furthermore a student who has taken the course may then choose to become a PhD student and rejoin the network as a supervisor in order to reshare the data. Comment on the durability and scalability of this system. [2 marks]
2.2 Choice of transport protocol
Explain in what situations you would choose to use TCP, and when you would use UDP. You might like to consider example cases such as:
- Fast transactions (where you want to send a short notification to another system with minimal latency)
- Bulk data transfers
- Timeliness (suppose data is being output from a sensor at one sample per second, and it is important for the receiver to have the most recent value of the sensor's reading rather than all values—i.e. it is better for the receiver to get the current value rather than an outdated value)
[4 marks]—inspired by Computer Networking, 3rd ed, review questions 2.3 & 2.5
2.3 HTTP performance
Here, we consider the performance of HTTP, comparing non-persistent HTTP with persistent HTTP. Suppose the page your browser wants to download is 100K bits long, and contains 10 embedded images (with file names img01.jpg, img02.jpg, … img10.jpg), each of which is also 100K bits long. The page and the 10 images are stored on the same server, which has a 300 msec roundtrip time (RTT) from your browser. We will abstract the network path between your browser and the Web server as a 100 Mbps link. You can assume that the time it takes to transmit a GET message into the link is zero, but you should account for the time it takes to transmit the base file and the embedded objects into the "link." This means that the server-to-client "link" has both a 150 msec one-way propagation delay, as well as a transmission delay associated with it. (Review page 39 in the textbook if you are uncertain about the difference between transmission delay and propagation delay.) In your answer, be sure to account for the time needed to set up a TCP connection (1 RTT).
- Assuming non-persistent HTTP (and assuming no parallel connections are open between the browser and the server), how long is the response time—the time from when the user requests the URL to the time when the page and its embedded images are displayed? Be sure to describe the various components that contribute to this delay.
- Again, assume non-persistent HTTP, but now assume that the browser can open as many parallel TCP connections to the server as it wants. What is the response time in this case?
- Now assume persistent HTTP (HTTP1.1). What is the response time, assuming no pipelining?
- Now suppose persistent HTTP with pipelining is used. What is the response time?
[4 marks]—Computer Networking, 3rd ed, review question 2.8
2.4 Application-layer protocols—practical
- Describe the main protocol messages exchanged and actions taken in a SMTP transaction (in which a client sends email to a server). Try interacting with a SMTP server yourself. (On the University network, you can use ppsw.cam.ac.uk, and can interact with it using the Telnet command on any Linux system and some Windows systems: telnet ppsw.cam.ac.uk 25.) See if you can successfully deliver email using handcrafted SMTP to my address.
- Pick some other application-layer protocol (not SMTP, HTTP or DNS as we've already talked about those).
- Use Wireshark to capture a single transaction of that protocol; use a capture filter to exclude packets of other protocols.
- Select one particular packet which shows something interesting happening in this protocol, and view the dissection of this packet (the panel between the packet list and the raw hexadecimal data). Describe the purpose of this packet and label on a screenshot some important fields.
- How would you go about reimplementing Wireshark's packet dissector, i.e. writing code to turn the raw packet data into a human-readable inventory of the contents of the packet?
Firstly, if you didn't finish exercise 2.4 from the previous supervision, please do so. If you're having problems with capture filters, note that they can be set in the Capture Options dialog, and take the form of a simple human-readable language; "tcp port 80" for example would capture HTTP. If you are unsure which port number you should be looking at, refer to the IANA list and/or the documentation for the protocol you are interested in.
3.1 TCP flow control
This question is adapted from 2002 Paper 9 Question 3, which is actually a Digital Communication II question. You should still be able to answer it, but you may give less detail than a Part II student might!
TCP incurs loss to discover the available capacity.
- Why does it do this? [1 mark]
- How can packet loss usually be detected without the sender waiting for an ACK timeout? How quickly can an overflowing buffer be detected? [2 marks]
- Describe the AIMD (Additive Increase, Multiplicative Decrease) mechanism, and fast recovery, and show how this leads to the characteristic "saw tooth" throughput behaviour of TCP over time. (Draw a sample graph of congestion window vs. time, and label what has happened at various points.) [5 marks]
- Consider a TCP connection operating in steady-state whereby each time the congestion window increases to W segments a single packet loss occurs. In terms of W and the round trip time (R), derive a simple formula for the time between the minimum and maximum data rates achieved. In this optimal scenario, how many packets are sent between each loss event? [4 marks]
- Derive the connection's average throughput in terms of the fraction of packets lost (p), the connection's round trip time (R), and the segment size (B). [4 marks]
- Under what conditions is this very simplistic model likely to be accurate? [3 marks]
- Remind yourself of the demonstration of TCP ARQ shown in the lectures (and the notes about the video).
- What might happen if you were to make the buffer much smaller (e.g. 1-2 packets)? [2 marks]
- Suppose the link shown were shared with a UDP Voice-over-IP call. What would be the effect on this call? How might this effect be avoided? [2 marks]
3.2 IPv4 and IPv6 details
- Draw the structure of an IPv4 packet and an IPv6 packet. Briefly describe the purpose of each IP header field. (You might want to make use of Wireshark to examine some real-life IP headers.) [6 marks]
- Where in this structure would you look to find a link-layer header (e.g. Ethernet) and a transport-layer header (e.g. TCP)? [2 marks]
- Automatic configuration is the process by which a host obtains an IP address and other details necessary to communicate at the network layer.
- Explain the protocol used for IPv4 autoconfiguration. [3 marks]
- List the two mechanisms which could be used for IPv6 autoconfiguration, and explain the differences and motivations behind each. [3 marks] (This may go beyond the course material, but you should do a little research!)
- Describe the evolution of IP addressing (class-based networks, subnetting, CIDR) including, for each:
- the basic operation
- the motivation for this scheme's introduction
- how a router looks up the next hop for a packet
- Suppose the internet is a single Ethernet backbone connected to many sites, with manually controlled routing tables at each site.
- Describe briefly how the address allocation and routing tables might be set up.
- Today only the very end systems use this approach. Why is it not possible to use this approach for the majority of today's Internet, and why can end systems still use it?
4.1 Routing protocols
- State the purpose of routing protocols and routing tables. [2 marks]
- What is an AS? Contrast interior and exterior routing without describing in detail specific routing algorithms or protocols. [6 marks]
- What are the pros and cons of distance vector versus link state routing protocols? Give examples derived from protocols in use today. [10 marks]
- Where are hybrid schemes employed and why? [5 marks]
(NB: when I and many others say "NAT", what we strictly mean is NAPT, also known as IP masquerading.)
- Why is NAT useful? [2 marks]
- What extra steps must a router take in order to perform NAT? [3 marks]
4.3 IPv6 transition mechanisms
IPv6 transition mechanisms exist to enable hosts to communicate using IPv6 over an infrastructure which is still partially IPv4-based. They generally involve encapsulating or tunnelling an IPv6 packet inside an IPv4 packet for part of its journey.
- During the initial rollout of IPv6, network support for IPv4 remains ubiquitous. So why might two dual-stacked (i.e. both IPv6- and IPv4-capable) hosts want to communicate using IPv6 if they could continue to do so using IPv4? [3 marks]
- Explain the operation of two different IPv6 transition mechanisms. [8 marks]
- Transition mechanisms are considered to be less reliable than native IPv6 connectivity. Explain why, with examples. [4 marks]
4.4 Multiple access
- Describe the CSMA/CD algorithm used on Ethernets to manage capacity and contention for a shared resource. [5 marks]
- Describe how CSMA/CD does not work on wireless networks, and how this leads to CSMA/CA. [5 marks]
5.1 More wireless multiple access: CDMA
Consider a CDMA scenario with two senders and two receivers. The chipping rate is 8 mini-slots for each data bit. The 8-bit CDMA code for sender 1 is 1, -1, 1, -1, 1, -1, 1, 1. The 8-bit CDMA code for sender 2 is 1, 1, 1, -1, 1, 1, -1, -1. (See figure below.)
- Sender 1 has two data bits to send: a 1 followed by a -1; sender 2 also has two data bits to send: a -1 followed by a 1. The figure below shows the first two mini-slot bits sent by each sender, and the first two mini-slot combined bits values in the channel. Compute the remaining sequence of mini-slot bits sent into the channel by sender 1 and by sender 2, and the remaining combined bit values on the channel—i.e. fill in the grey-shaded regions in the figure to the right. [3 marks]
- Assume now that there are two receivers. Receiver 1 wants to obtain the two data bits sent from sender 1 and knows sender 1's CDMA code; similarly, receiver 2 wants to receive the two data bits sent from sender 2 and knows sender 2's CDMA code. Both receivers receive the 16 mini-slotted bits in the combined channel (which you calculcated earlier). Show how each receiver performs the CDMA decoding operation in order to fill in the right-hand grey-shaded regions. [3 marks]
(Computer Networking, 3rd ed, review questions 6.2 & 6.3)
5.2 802.11 wireless networking in reality
Suppose you enter a café with your laptop to find many separate wi-fi networks run by different neighbours with which your laptop's wireless interface can associate. Your laptop associates with the access point with the strongest signal—but the signal strengths of the access points vary over time, so your association will also change over time (every few minutes). We are interested in the effects of a changing link-level association, and the consequent change of IP address when an association changes.
- Suppose you are browsing the web using HTTP/1.0, and only occasionally downloading web pages. Is the changing link-layer association and change of IP address likely to be a problem for you? [2 marks]
- Now suppose that you want to perform a file transfer over TCP that is so large that it is likely that your laptop's link-layer association will change during the file transfer. Is the changing association and consequent change of IP address likely to be an issue for you? [4 marks]
- If you identified any potential problems, how could you (at least partially) work around them? [3 marks]
(Computer Networking, 3rd ed, review question 6.4)
5.3 Quality of Service architectures
- Consider the IntServ (RSVP-based) and DiffServ QoS architectures.
- Compare the nature of "guarantee" that is made in each and the time scale on which these are altered. [4 marks]
- Compare where state resides in each case, and how much state there is. [3 marks]
- Consider the resource efficiency of each scheme in terms of link bandwidth. [2 marks]
- Describe the behaviour of a core router in a DiffServ environment, recalling that each packet will have a Type of Service field describing its designated Per Hop Behaviour. [5 marks]
- Leaky bucket:
- What can a leaky bucket scheduler be used for? [4 marks]
- How would you select its parameters? [4 marks]
- System design: Suppose you rent an ADSL1 connection for your shared house. You find that sometimes—particularly when your housemates are downloading films via P2P—your online gaming experience suffers heavy lag and voice-over-IP is barely useable due to intermittent audio dropouts and high delay. Your home router is Linux-based and you have full control over its behaviour. What are the likely causes of your problems, and what could you do about them (without depriving your housemates of their films)? [8 marks]
- Before Skype, it was generally considered that today's Internet could not reliably support high-quality real-time multimedia applications. Why? How did Skype manage to sidestep these issues? [8 marks]
- Answer 2010 Paper 5 Question 7 (unless you are the group which has already done this question).
Supervision 6 (revision)
For your final supervision I suggest you answer a few past exam questions. You are welcome to pick your own, but here are a few suggestions (bearing in mind the course has been substantially refactored recently, several of these are from older courses but have been selected to roughly align with the material you have covered). Digital Communication II is actually a closer match for the new course than Digital Communication I.
If you tell me before 4pm on Thursday 26th May which exam questions you will be attempting / have attempted, I will obtain the examiner's notes and mark your work as if in an exam. I am out of the country as of Friday 27th May but can be reachable by email.
Recent questions specifically on this course
- 2010 Paper 5 Question 7 (Skype; protocol design and tradeoffs)
- 2010 Paper 5 Question 8 (TCP/IP packet processing on hosts)
- 1998 Paper 8 Question 2 from Digital Communication II (interesting high-level question on TCP)
- 2004 Paper 7 Question 2 from Digital Communication II (TCP)
- 2003 Paper 8 Question 3 from Digital Communication II (TCP)
Generic flow control
- 2006 Paper 7 Question 2 from Digital Communication II (flow control)—possibly uses terminology not covered in this course, but you can probably work out what it means
- 2009 Paper 5 Question 7 from Digital Communication I (flow control, network emulation)—the last part is slightly off-syllabus but you should be able to make a good guess
Generic error control
- 1998 Paper 5 Question 3 from Digital Communication I (packet loss and error control)—note that "ARQ" is a somewhat old term for "error control" i.e. retransmission of lost packets; in the case of TCP, this is tied somewhat to flow control but is logically separate
- 2007 Paper 5 Question 3 from Digital Communication I (layering and multiplexing)
- 1996 Paper 6 Question 3 from Digital Communication I (layers / protocol design)
- 2008 Paper 7 Question 3 from Digital Communication II (OSI model bookwork, and layer violations)
- 1995 Paper 5 Question 3 from Digital Communication I (layering + routing/addressing)—note that a "MAC level bridge" would these days more usually be called a switch
Routing and addressing
- 2008 Paper 6 Question 3 from Digital Communication I (addressing and routing)
- 2010 Paper 9 Question 6 from Digital Communication II (routing protocols)—note that part (c) is not covered by this course, but I have mentioned it in supervisions
- 1998 Paper 6 Question 3 from Digital Communication I (protocol design)
- 1995 Paper 5 Question 3 from Digital Communication I (layering + routing/addressing)—note that a "MAC level bridge" would these days more usually be called a switch
Media access control
- 2009 Paper 8 Question 5 from Digital Communication II (media access control and QoS)
- 2001 Paper 9 Question 3 from Digital Communication II (access network technologies: note that this material was not covered in much detail in that course either, so this question was intended to be answered to some extent from your intuition)—also note that "current technology" has moved on a fair distance since 2001 so I will try to update the mark scheme!
- 2007 Paper 8 Question 4 from Digital Communication II (routing protocols + impact on other protocols)