Computer Laboratory

Supervisions 2009/2010

Supervision questions: Digital Communication II

This is the set of questions for my supervisions in Digital Communication II. I will typically email you a list of question numbers before each supervision, but if not, attempt the next two or three. (More questions will appear here as I set them, so come back if you want to make an early start on some of the future work.)

Administrativa & handing in work

I expect you to make a good attempt at producing solutions to the relevant questions before each supervision. I prefer submissions by email (PDF or text format). Please submit your work 24 hours before the supervision. If you want to submit a hard copy of the work to student administration, please hand it in before 17:00 two days before the supervision (i.e. before Wednesday, 17:00 for a Friday afternoon supervision) as I will have to scan it. Remember that Student Administration is closed on weekends.

When emailing me regarding supervisions, please only use my lab address, or your email will be misfiled and may slip by unnoticed:

The questions I set for a supervision are generally intended to take an average student 4-5 hours to answer to a satisfying standard. However, I do realise that some of these allow for fairly verbose answers. If you find you feeling like you are spending too long on a question, I suggest you finish your answer in bullet-point style and move on to the next question. The mark allocation (whilst very approximate) should give you a rough idea of how you should divide your time between the questions, as well as how much credit I expect a similar question to be worth in the exam. It will also serve as a guide for me when marking the questions.

If there is a particular part of the course you would like explaining, or questions you have about the lectures (independent of whether they are covered by the questions or not), please let me know in an email before the supervision so that I can prepare appropriately.

1. The telephone network, the Internet and ATM networks

  1. Compare the digital telephone network, the Internet and ATM in the following categories:
    • design philosophy,
    • addressing,
    • routing,
    • signalling,
    • connection establishment,
    • congestion control,
    • quality of service,
    • multiplexing multiple connections onto a single link,
    • particular implementation challenges, considering the trend towards larger and faster networks,
    • security considerations.
    N.B.: You are welcome (and encouraged) to provide your answer in table or bullet point format. However, I would ask you to write out your answer for two of the above points in the style that you would use when answering an exam question. [30 marks]

2. The OSI model

  1. What is the OSI model used for? [2 marks]
  2. What do you think a common problem with using the OSI model to describe real-world technologies is? [2 marks]
  3. Describe the 7 layers of the OSI model, giving for each:
    • a brief description of the layer;
    • an example;
    • where/how it's implemented in the Internet in interconnection equipment (e.g. routers) and end systems.
    [14 marks]
  4. Where would each of the following fit into the OSI model?
    • a HTTP/HTTPS proxy server (consider both an intercepting proxy [often called "transparent proxy"] and a normal, user-configured proxy);
    • a VPN (i.e. tunnelling IP packets over an encrypted channel based on UDP or similar);
    • RFC 1149;
    • RFC 2549 and Quality-of-Service schemes in general.
    [6 marks]

3. ATM Networks

  1. What is the difference between soft state and hard state? Which of the two is ATM using? [2 marks]
  2. Why is it desirable to run IP traffic over an ATM network? Why might it not be? [2 marks]
  3. Discuss the problems of IP-over-ATM, with respect to:
    • address resolution;
    • subnetting and broadcast/multicast;
    • the holding time problem.
    [6 marks]
  4. Why might it be better to run TCP over ATM and ignore IP? [2 marks]
  5. 2009 Paper 9 Question 7 [20 marks]

4. IP and IP addressing

  1. Regarding IP fragmentation and reassembly:
    1. What is a network MTU and why is it necessary?
    2. Why is IP fragmentation unavoidable at times?
    3. Describe how an IP packet is broken into fragments.
    4. Describe the reassembly process.
    5. Why is IP fragmentation bad?
    [6 marks]
  2. Describe the evolution of IP addressing (class-based networks, subnetting, CIDR) including, for each:
    • the idea
    • the motivation
    • how a router looks up the next hop for a packet
    Do not discuss routing protocols (e.g. OSPF) or DHCP or NAT boxes yet. [9 marks]
  3. How do you think the setup, topology and technologies used to implement the internet backbone and those used for end systems (e.g. corporate networks/ASes, LANs) differ?
    [Hint: Consider for example whether a single Ethernet backbone with local, manually configured routing tables would be suitable for either.] [5 marks]

5. DNS

  1. Outline the purpose of DNS, and the major types of query it can answer. [4 marks]
  2. Describe the hierarchical nature of DNS with regard to the delegation of responsibility between organisations. Explain how a recursive DNS server would resolve a query. [4 marks]
    (Optional: you might like to illustrate your answer by using the Linux tool "dig"; the "+trace" option would be particularly useful.)
  3. Do you think DNS is an example of a well-designed system? [8 marks]
  4. DNS can be used as an additional way of multiplexing several web sites onto one IP address ("virtual hosting"). How does this work? What are the design challenges faced when implementing this neatly in an OSI-style protocol stack (HTTP, TCP, IP)? [4 marks]

6. Routing and multicast

  1. Compare and contrast routing in the modern-day telephone network and the Internet. [8 marks]
  2. What is an AS? Contrast interior and exterior routing without describing in detail specific routing algorithms or protocols. [6 marks]
  3. 2008 Paper 8 Question 3
  4. 2004 Paper 9 Question 7parts (a), (b) and (d) only
  5. 2004 Paper 8 Question 3parts (a) and (b) only

7. Error control

  1. Describe the problem of packet insertion and the solutions adopted by TCP. [6 marks]
  2. Round trip time (RTT) estimation:
    1. Why does TCP need to estimate RTTs? [2 marks]
    2. Describe two RTT estimation algorithms. [4 marks]
  3. Compare and contrast two schemes for packet retransmission in TCP. [4 marks]

8. Flow control

  1. 2002 Paper 9 Question 3
  2. Rate-based flow control:
    1. Why might we want to use a rate-based rather than a window-based flow control system? [2 marks]
    2. Compare and contrast the flow control schemes of TCP, NETBLT and Packet Pair. [4 marks]
  3. Using diagrams, illustrate TCP flow control in different versions (the x-axis of your diagram should be time, and the y-axis should be window size):
    1. normal, basic TCP flow control (additive increase, multiplicative decrease),
    2. with the slow start feature enabled,
    3. with fast retransmit enabled.
    [9 marks]
  4. 2004 Paper 7 Question 2part (b) only
  5. Suppose open loop flow control is to be added to the Internet.
    1. What is open loop flow control? [2 marks]
    2. What new tasks must Internet routers perform in order to provide open loop flow control? [4 marks]
    3. Describe and compare delay and jitter, considering how they arise in networks and the applications to which they are important. [3 marks]
    4. What is a leaky bucket and where would it be used? How do we choose bucket parameters? [4 marks]

9. Scheduling and queue management

  1. Outline the scheduling and queueing behaviour of today's internet routers, and why this is bad for certain types of application. [4 marks]
  2. Compare the pros and cons of the packet-dropping policies of drop-from-head, drop-from-tail and drop-all. [3 marks]
  3. What is Random Early Detection and how does it result in smoother TCP flows? For which applications is it bad? [4 marks]
  4. 2003 Paper 7 Question 2

10. Switch fabric design

  1. (from 2002 Paper 8 Question 3)
    Explain why building switches and routers that are able to keep up with transmission link rates is becoming increasingly difficult. [4 marks]
  2. A circuit switch is required to switch 100,000 calls at a telephone interchange.
    1. An engineer proposes to solve the problem using a time slot interchange system. What is the problem with this? [2 marks]
    2. Propose a more suitable design for the switch [3 marks]
  3. Describe the operation of the following types of packet switch fabric, paying particular attention to the kinds of blocking which can occur:
    • CPU-driven ("first generation switch")
    • Shared bus ("second generation switch")
    • Crossbar
    • Banyan
    • Batcher Banyan
    [12 marks]
  4. Explain the relative merits of input buffering, internal buffering and output buffering in a crossbar packet switch as methods of dealing with blocking. [3 marks]

11. Multiple access

  1. We need a multiple access protocol to connect mobile phones and base stations.
    1. What measures do we care about when we design such a system? [4 marks]
    2. Compare centralised and distributed access control. Which should we use here and why? [5 marks]
    3. Describe two schemes that could be used. Are they centralised or distributed? [6 marks]
  2. 2009 Paper 8 Question 5
  3. 2007 Paper 9 Question 4parts (b) and (c) only
  4. Discuss the problems which might be faced when designing a multiple access protocol for a satellite link, in which the delay is large, and suggest a scheme which could be used. [6 marks]

12. Quality of Service

  1. 2000 Paper 9 Question 3
  2. 2004 Paper 9 Question 7parts (c) and (e) only

X1. Extra question: ficticious design problem

N.B.: This questions was originally conceived and set by Malcolm Scott and is replicated here with his permission. I have modified it very slightly, but the original idea is Malcolm's.

Background information

In the University of Granta, the colleges manage their networks independently but are provided with interconnectivity amongst themselves and to the internet, in the form of the Granta University Data Network (GUDN), an IPv4 network in which each college has a connection to a core router.

Each student is allocated (for the sake of simplicity) a single IPv4 address by the college to which they belong. This address may be one of the following:

  • a public address, able to send and receive packets to/from any other address on the internet directly
  • a GUDN-wide private address, able to send and receive packets to/from any other address on the GUDN directly; provision for internet connectivity is a University-wide HTTP/HTTPS/FTP proxy server and PERHAPS a network address translation (NAT) router provided by the college [look that up if you don't know what it is]
  • a college-wide private address, able to send and receive packets within the college network only, or via a NAT (always provided in this case) to other hosts in the GUDN or the internet

Generally colleges follow a unified policy, i.e. every student is allocated the same kind of address. There may be occasional exceptions, e.g. where private addresses are normally issued but a public address may be provided if there is academic justification (rare).

For any of these types of address, there will most likely be a firewall which blocks some sorts of traffic. This may vary from just blocking certain known-malicious ports, to blocking all connections to student machines and some outbound connections too.

Traffic within the GUDN is entirely free to colleges (although a minority charge students for it anyway). Internet traffic is chargeable to the colleges, who generally either pass on the charges with a heavy markup, or take other steps to try to reduce this cost. Colleges may cut off or otherwise penalise heavy users (of internet or GUDN-internal traffic) after they pass some arbitrary college-defined threshold. You may assume the existence of a few "friendly" colleges with public IP addresses, little or no firewalling, and no limit/charges on GUDN-internal traffic.


Students wish to share home-made videos of college life amongst themselves in a peer-to-peer manner, entirely legally. The college marketing departments disapprove of this as many of the videos show aspects of college life which they believe would best not be made common knowledge. Depending on the amount of influence the marketing department of a college has influence over the IT department, there will most likely be attempts at the college level (not usually coordinated between colleges) to shut down any such file sharing network. The University as a whole couldn't care less and will not try to shut down the network centrally.

The ideal solution would:

  • Be implementable by students, i.e. within the constraints of the network they are given
  • Avoid bandwidth charges by only transferring bulk data within the GUDN
  • Avoid single points of failure which could be shut down
  • Avoid relying overly on "friendly" colleges as pressure on the IT department to stop this may result in restriction of policies there
  • Allow students in as many different colleges as possible share files (e.g. restricting the network to students with public IP addresses is unacceptable; ideally it should also work for students with private IP addresses and no NAT)
  • May assume the existence of a Student-Operated Computing Club (SOCC) that provides a free hosting facility, but cannot host the material to be shared directly.
  • May assume the existence of a Public Workstation Network (PWN) that can be used to tunnel traffic through, but cannot be used to do this extensively as such behaviour would be flagged up by network monitoring systems and would result in the facility being restricted or withdrawn.

A complete solution may be impossible. However, please outline a rough design for as good a solution as you think possible.

You may wish to refer to the Advanced Systems Topics 2005-6 mini-course on P2P to see what kinds of things are possible with P2P networks — although the precise details of the operation of the P2P network are not necessary for your answer.

My thanks to Malcolm Scott, whose set of DigiComm II questions these are partly based on. Further thanks (by transitivity!) to Phil Tuddenham, on whose question set Malcolm's questions were loosely derived from.