Computer Laboratory

Malcolm Scott

Supervision questions: Digital Communication II (2008)

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 questions for my 2008 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 gradually appear here over the coming days/weeks.)

You are expected to produce solutions to the relevant questions before each supervision and 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 or the tray outside Cockcroft 4 if you also email me so that I know to collect it — but 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:

If you find you are spending an inordinately long time on a question, I suggest you abandon it and move onto the next; the mark allocation (whilst very approximate) should give you a rough idea of how you should divide your time between the questions. If there is a particular part of the course you would like explaining, whether or not this is covered by the questions I set, please make a note on your submission or email me before the supervision so that I can plan 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.: a table would be a suitable format for your answer, or maybe bullet points. I'm not after an essay :-). [30 marks]

2. The OSI model

  1. What is the OSI model used for? [2 marks]
  2. 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]
  3. Where would each of the following fit into the OSI model?
    • a HTTP/HTTPS proxy server;
    • 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. TCP/IP over ATM

  1. Why is it desirable to run IP traffic over an ATM network? Discuss the problems of doing so, including:
    • address resolution;
    • subnetting;
    • the holding time problem.
    [6 marks]
  2. Why might it be better to run TCP over ATM and ignore IP? [4 marks]

4. IP and IP addressing

  1. Describe briefly the important features of the structure of an IP packet inside an Ethernet packet [8 marks]
  2. Compare the checksums used by the Ethernet, IP and TCP protocols, mentioning for each:
    • the algorithm used;
    • when it is checked;
    • the information checksummed;
    • the errors it is designed to catch.
    [10 marks]
  3. 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. Who does fragmentation?
    4. Who does reassembly?
    5. Describe how an IP packet is broken into fragments.
    6. Describe the reassembly process.
    7. Why is IP fragmentation bad?
    [8 marks]
  4. 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]
    1. 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.
    2. 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?
    [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. 2004 Paper 7 Question 2part (b) only
  3. 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]
  4. 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. 2007 Paper 9 Question 4
  3. 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. [about 6 marks]

12. Quality of Service

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

Outstanding topics

Please tell me whether the lecturer has spent much time on the following topics. I am happy to cover them, but there is little point if they are only mentioned in passing.

  • MPLS (I can rant about this if required, and present my research as a far better alternative ;-) )
  • QoS routing (the lecture is mostly about multicast routing, which we've already covered, but if he spent significant time on the latter part of the lecture, maybe we should talk about that)
  • Traffic management (theoretically an entire lecture, but I don't think I've seen more than vague mention of the principles in exam questions — i.e. we may have already covered this in enough detail when talking about ATM etc., and the rest is covered as part of QoS above)
  • The lecture entitled "Politics, Economics and Philosophy" (which appears to mainly be a course on how to be an ISP, compressed into one lecture!)

The following questions were set in 2007 and not 2008, but are archived here for posterity.

13. Recent exam questions

Please answer as you would do so in an exam (but with the aid of notes if necessary). You might like to hand-write your answers so that you have practice answering questions without the aid of a text editor. I will try to mark your answers as the examiner would, but his mark schemes are in my opinion rather vague...

  1. 2006 Paper 7 Question 2
  2. 2007 Paper 7 Question 2
  3. 2007 Paper 8 Question 4

X1. Extra question: ficticious design problem

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)

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 Phil Tuddenham who compiled a set of questions from which these are loosely derived. He is, however, not to blame for question X1.