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).
- Circuit-switching: At time t = 0, the first node sends out a circuit reservation packet (of size R) which is sent to the second node, which then receives the full packet and then forwards it to the next node. This is continued at each node, until the reservation packet arrives at the last node (after traversing n links). After this reservation message is processed at the last node (the destination), the last node sends back a reservation conﬁrmation message (also of size R) back to the first hop. Because the circuit is established before this conﬁrmation is sent, this packet need not be processed at each node; instead, the bits ﬂow through the nodes without any delay. Once the confirmation message is received at the first node (the source), the source immediately starts sending the file (which is of size F) at the full bandwidth of the link. Note that when the file is transferred, the data is not stored-and-forwarded at any of the intermediate nodes but is just passed through without delay. Also, we ignore the teardown message, since it is only sent after the file arrives. Assuming no problems in transmission along the way, at what time does the last bit of the file arrive at the last node (the destination)?
- Packet-switching: Here the file is broken into Q packets of size D, each with header size H and payload size P. Since the entire file must be carried, Q * P = F. At time t = 0, the source (the first node) sends the ﬁrst packet, which is stored-and-forwarded at each of the subsequent nodes until it reaches the destination (the last node). As soon as the source ﬁnishes sending the first packet, it sends the second packet (at full link bandwidth). Note that the source does not wait until the first packet arrives at the next node before starting the next transmission, it starts sending the next packet as soon as it has ﬁnished transmitting the previous packet. We assume that a node can immediately send a packet out on the next link as soon as the last bit has arrived from theprevious link (i.e., there is no time required to process the packet before sending it on the next link). Assuming no packet drops or other errors, at what time does the last bit of the file arrive at the destination?
- If the file size F is very large, which is faster and why? (Assume that the header size H has not changed.)
- If the payloads become small (but the header size remains constant), which is faster and why?
- If the bandwidth B is very large, which is faster and why? And by what ratio (in the limit)
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.
- Several real-time video streams are to share the same lower-layer channel.
- Give one example of a lower-layer channel in which the flows might be scheduled, and one in which scheduling is not possible.
- A lecturer remarks that “centralised multiplexing” offers potential gains in efficiency over non-centralised multiplexing. Give two reasons why this can improve efficiency. What, in general terms, is the “centralised” facility necessary for these gains to be possible?
- Using an example, describe why specifying a scheduling policy in terms of priority may cause problems, even where it is safe to use priority within the scheduling mechanism. [Hint: consider CPU scheduling in an operating system.]
- Code-division multiple access (CDMA) is a code-division multiplexing system, used for mobile telephony.
- What is a code? What property of codes causes them to be "nearly orthogonal" to each other?
- Two transmitters, A and B, both want to transmit a four-bit message at the same time using CDMA. Transmitter A has code 10010111 and message 1001. Transmitter B has code 00111101 and message 0011. Write down the bit sequences transmitted by A and B. Write down the bit sequence seen by a receiver, stating any assumption you make. Show that the original messages of both A and B may be recovered.
- Explain, giving an example, how to write a binary message (i.e. a sequence of binary digits) as a polynomial.
- Outline send and receive procedures for CRC-based message coding and error detection. What information must be agreed in advance by the sender and receiver?
- Draw a shift register which will compute the remainder on division of an input polynomial by the CRC-8 polynomial x8 + x2 + x1 + 1.
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
- The name of the student with a CRSID of acr31
- Students and their marks in exam papers
- Students who got a first (or some other definition of a good mark)
- Papers which no-one got a good mark on
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 range||Link interface|
|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|
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?
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
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