CSD008/COMP3616, Networks & Internet Systems: Problem Set 1
-----------------------------------------------------------

Reminders: There are no marks associated with these problems,
 and you do not hand in your answers. Solutions will be
 distributed shortly. "Tanenbaum" refers to the 4th Edition.

1. (Tanenbaum, chapter 1, problem 10) A disadvantage of a
 broadcast subnet is the capacity wasted when multiple hosts
 attempt to access the channel at the same time. As a
 simplistic example, suppose that time is divided into
 discrete "slots", with each of the n hosts attempting to
 use the channel with probability p during each slot. What
 fraction of the slots are wasted due to collisions?

2. (Tanenbaum, chapter 2, problem 41) 3 packet-switching
 networks each contain n nodes. The first network has a
 star topology with a central switch; the second is a
 (bidirectional) ring; and the third is fully
 interconnected, with a wire from every node to every
 other node. What are the best, average, and worst case
 transmission path lengths in hops?

3. Suppose you want to add two new computers to an existing
 network with five computers. If the network has a fully
 connected mesh topology, how many new links are needed ?
 If the network instead had a ring topology, how many new
 links would be needed ?

4. When is packet switching usually preferred to circuit
 switching ? (Note: more than one answer may be correct)

   (a) always;
   (b) when network delays have to be small;
   (c) when the input traffic is bursty;
   (d) when the transmission rate is high.

5. Datagram packet switching is often preferred to virtual
 circuit packet switching for the transmission of a short
 message (one that can be split up into a small number of
 packets). State one condition under which virtual circuit
 packet switching could be preferred even for short messages.

6. If 2 virtual circuits pass through a network node N, and
 packets are travelling on both virtual circuits at the same
 time so that node N sees an interleaved stream of packets,
 how does node N know which packets belong to the first
 virtual circuit and which packets belong to the second ?

7. (Tanenbaum, chapter 2, problem 42) Compare the delay in
 sending a message of length x bits over a k-hop path in a
 circuit-switched network and in a (lightly-loaded) datagram
 packet-switched network. The circuit setup time is s seconds,
 the propagation delay is d seconds per hop, the packet size
 is p bits, and the data rate at each node is b bits per
 second. Under what conditions on s, k, b, and p does the
 packet-switched network have a lower delay ?

 Assume that x is a multiple of p (in other words, the
 total number of bits to be transmitted is a multiple of
 the packet length). The x bits to be transmitted in the
 packet-switched network include the packet headers (in
 other words, the header bits are already accounted for
 in x). Finally, assume the packet-switched network is
 lightly loaded (in other words, the queueing delays in
 each intermediate node can be taken to be zero).