CSD008/COMP3616, Networks & Internet Systems: Problem Set 1 ----------------------------------------------------------- Solutions --------- ("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? Solution: a slot has the following possibilities: empty (no host tries to use the slot); successful (exactly one host tries to use the slot); and collision (two or more hosts try to use the slot). The fraction of the slots wasted due to collisions is the same as the probability of a collision, which is P_collision = 1 - P_empty - P_successful. If the probability of a host trying to use the channel in a slot is p, then the probability of a host NOT trying to use the channel in a slot is (1-p). There is only 1 way for the slot to be empty: if all n hosts don't try to use the channel in the slot. This happens with probability P_empty = (1-p)^n, since each of the n hosts doesn't try to use the channel with probability (1-p) and we assume all hosts act independently. The probability of exactly 1 host using the channel in a slot is p*(1-p)^(n-1): p for the host who tries to use the channel, and (1-p)^(n-1) for the other n-1 hosts who don't try to use the channel. But there are n different ways for exactly 1 node to use the channel in a slot, since it could be any of the n hosts who tries. Therefore the success probability is P_successful = n*(p*(1-p)^(n-1)). Therefore P_collision = 1 - (1-p)^n - n*(p*(1-p)^(n-1)) which is the fraction of slots wasted due to collisions. As a numerical example, if n=10 and p=0.1, the fraction of slots wasted due to collisions is P_collision = 0.2639, or approximately 26%. If n=10 and p=0.01, the fraction of slots wasted due to collisions drops to P_collision = 0.0043, or under 1%. In this case, the other probabilities are P_empty = 0.9044 and P_successful = 0.0913. So in this case the majority of the slots are wasted, but not due to collisions: since the probability of an individual host using the channel is so low, and there are only 10 hosts, the most likely scenario is that no host tries to use the channel in a slot. You should try some other numerical examples to get an understanding of how the individual host behaviours influence the performance of the overall system. 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? Solution: best average worst --------------------------------------------------------- star 2 2 2 bi-dir. ring* 1 approx n/4 approx n/2 full mesh 1 1 1 * there is a slight difference depending on whether n is even or odd 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 ? Solution: in a full mesh, need 11 new links. In a ring, need only 2 new links (assuming one existing link can be re-directed to one of the new nodes). You can see how to get these solutions by drawing the network topologies and simply counting the number of new links 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. Solution: packet switching is preferred to circuit switching when the traffic is bursty (answer c). Packet switching is not necessarily used if the delays have to be small or if 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. Solution: if the virtual circuit setup time was low or zero; or if the additional datagram header (see Problem 14) was large enough that it outweighed the effect of virtual circuit setup time. Also, if in-order delivery was required, and the datagrams were likely to get out of order, a virtual circuit would be preferable (though this is an unlikely requirement 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 ? Solution: each packet carries with it the virtual circuit identifier for its virtual circuit; these identifiers are chosen to be different for different virtual circuits. So by examining a packet's virtual circuit identifier field, node N can determine which virtual circuit the packet is travelling on. 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). Solution: in circuit switching, the bits are pipelined through the network; whereas in packet switching, it's packets that are pipelined through the network, but a packet can't be forwarded from an intermediate node until it's fully received at the node (hence the "store-and-forward" delay). Also, we assume here that packets can be transmitted back-to-back at the nodes, and that no processing time is needed at intermediate nodes once the packet has been fully received. Circuit switching : delay = (setup time) + (time to transmit x bits at the sender) + (propagation delay of last bit along the path) = s + (x/b) + kd Packet switching : delay = (time to transmit x bits at the sender) + (propagation delays of last bit of last packet along the path) + (packet retransmission delays at the intermediate nodes) and since we assumed that the number of bits x is a multiple of the packet length p, this delay is delay = (x/b) + kd + (k-1)(p/b) By comparing the two delay expressions, we see that the packet switched option is faster if s > (k-1)(p/b).