Lent supervision work

Supervision 1 - Computer Networking (1)

As there have not been sufficient lectures as yet there is no work set for this supervision. Expect double work for next time

Supervision 2 - Databases (1)

Write out a glossary of terms and notation for the various concepts Relational Schema, Relational Algebra, and Relational Caculii.

Complete tripos question 2008-6-8. You may omit the questions on outer-joins.

Complete tripos question 2004-5-8.

You should set yourself up with a database system so that you can experiement with SQL queries. One easy option is to download HSQLDB. Unzip the archive file and then launch a database GUI by running java -cp hsqldb/lib/hsqldb.jar org.hsqldb.util.DatabaseManagerSwing.

Supervision 3 - Computer Networking (2)

Lecture 1 discusses the Internet protocol stack and the OSI reference model. Describe each. Explain the purpose of each layer in the Internet protocol stack with reference to an example use of the Internet. What interface/functionality does each layer expose to the one above?

You may need to consult other sources than the lecture notes. Write your answer as if it needs to be understood by a good Part 1A student who has not seen this content before

Consider a communication network consisting of a room full of people in which one or more people are exchanging thoughts by talking. Identify one or more corresponding components for each of the abstract terms node, channel, entity, layer, transmission, coding, addressing and multiplexing. If the correspondence is not exact then explain why and give the closest one you can.

You are given a network consisting of n links in a row, each of B bandwidth and latency L. In the following questions, we refer to cases where some quantities are big. By that we mean consider the limit where that quantity becomes infinitely large or infinitesimally small. Note that some quantities are linked (i.e., if the payload P gets smaller, the number of packets Q must get larger to keep Q × P = F).

What do the letters in CSMA/CD and CSMA/CA represent? Describe a usage of each, how it is implemented in practice and explain the motivation for the choice.

Multiplexing:

CRCs

Briefly explain ARP and DHCP. What are the key concepts that they have in common? Which other aspects of Computer Networking have you seen which use these concepts?

Supervision 4 - Databases (2)

Update and extend your glossary to include any new terms and notation

Draw out the Entity Relationship example from the previous supervision for students and their marks in exam papers. Include a relational schema, and a valid relational instance. Make sure you label all your keys.

For each of the queries below provide a definition in SQL, Relational Algebra, Tuple Relational Calculus, Domain Relational Calculus

What does NULL mean in SQL? Give an example truth table in three-valued logic. Give an example of why NULL might produce unexpected behaviour. What is the case for and against its use?

Consider the following SQL query SELECT min(price),max(price),name,restaurants.id from restaurants,reviews where restaurants.id = reviews.restaurantsid and reviews.rating >= 2.5 group by restaurants.id, restaurants.name having max(price) < 100. What does it do? Infer a relational schema and give a relational instance. For each of Relational Algebra, TRC and DRC either give an equivalent query or explain why it cannot be expressed.

Complete tripos question 2007-6-8.

Supervision 5 - Computer Networking (3)

What is Network Address Translation? What problem does it solve? How does it work (consider TCP and UDP)? What is the NAT traversal problem? Outline 3 solutions.

Define routing and forwarding. What do we mean by 'valid' routing state? What is basic architecture of a router? Describe the three types of switching fabrics and give pros and cons. Explain why we need buffers and discuss the considerations into how big they should be.

Consider a datagram network using 32-bit addresses. Suppose a router has four links, numbered 0 through 3, and packets are to be forwarded to the link interfaces as follows:

Destination Address rangeLink interface
StartEnd
11100000 00000000 00000000 00000000 11100000 11111111 11111111 11111111 0
11100001 00000000 00000000 00000000 11100001 00000000 11111111 11111111 1
11100001 00000001 00000000 00000000 11100001 11111111 11111111 11111111 2
otherwise 3

Provide a forwarding table that has four entries using longest prefix matching which forwards packets to the correct link interfaces. Give your answer using both binary string notation (See Kurose and Ross, Chapter 4, Section 4.2.2 for an example) and a.b.c.d/x notation. Describe how your table determines the appropriate link interface for datagrams with destination addresses: 11001000 10010001 01010001 01010101, 11100001 00000000 11000011 00111100, 11100001 10000000 00010001 01110111

Prefix trees (or Tries) can be used to implement longest prefix matching. Explain the datastructure, its invariants, how the various operations on it proceed and how to implement longest prefix matching using it. Optional: if you wish you may provide a commented Java, ML, C or C++ program in answer to this question. For extra fun have a look at optimising a bitwise trie using __builtin_clz() in GCC.

Describe the role of the important fields in an IP header. How does IP deal with problems of data corruption, lost packets, network loops and oversized packets?

Six important changes between IPv6 and IPv4 are: Eliminated fragmentation; Eliminated header length; Eliminated checksum; New options mechanism; Expanded addresses; Added Flow Label. Explain what each of these means and what the motivation was for the change.

What is a spanning tree? Explain how it can be used with reference to network switches. Describe an algorithm for computing the spanning tree of a network.

Complete tripos question: 2008-6-3

Supervision 6 - Databases (3)

Update your glossary to include the remainder of the important terms, concepts and definitions from the course. Think about how you structure it—you are trying to produce a reference for someone who has completed the course rather than a logical breakdown for teaching order. Those of you who I deem have done a good job will be rewarded with a copy of my glossary for the course as an additional reference.

What is the difference between OLTP and OLAP? Give an example scenario for each. Use your OLAP scenario to explain the operation of a data cube and star schema. How do these approaches relate to NoSQL-style data stores?

Complete tripos questions 2010-4-5, 2009-4-7, 2008-5-8

Supervision 7 - Computer Networking (4)

Complete Question 19 (Error control, ARQ) from Topic 5 (Transport) of the supervision questions

You are given a ZIP file containing an Eclipse project which implements a UDP client and server. Download this project and use File->Import->Existing project into workspace to import the project into your Eclipse workspace. After compiling the project you can do: java uk.ac.cam.acr31.arqtest.Server 9898 0 1000 and java uk.ac.cam.acr31.arqtest.Client 9899 localhost 9898 0 1000 to see the log of packets received and messages exchanged. The project contains a simple wrapper for DatagramSocket called TestDatagramSocket which simulates packet loss and link propagation delays—try changing the 0 in the command-line to 0.5 and you'll start to see messages getting lost. Your task is to extend this Client and Server to implement RDT3.0 from the notes (reliable transmission but no pipelining). Hint: you can use DatagramSocket.setSoTimeout to set a timeout on the socket i.e. setSoTimeout(1000) will mean that your call to DatagramSocket.read will throw a SocketTimeoutException if the packet doesn't arrive within 1000ms.

Complete question 20 (TCP specifics) from Topic 5 (Transport) of the supervision questions

Complete tripos question: 2011-5-5, 2011-5-6

The derivation of the equation for througput in terms of drop rate (and the definition of drop rate) are nicely explained in the paper "The macroscopic behavior of the TCP congestion avoidance algorithm", ACM SIGCOMM Computer Communication Review, Volume 27 Issue 3, July 1997. You can find a copy in the ACM digital library, or on Google