6.02 Practice Problems: Packet and Circuit Switching, and Little's Law

Problem . Little's Law.

1. At the supermarket a checkout operator has on average 4 customers and customers arrive every 2 minutes. How long must each customer wait in line on average?
   Throughput time = 4 customers / 1/2 customer/minute = 8 minutes

2. A restaurant holds about 60 people, and the average person will be in there about 2 hours. On average, how many customers arrive per hour? If the restaurant queue has 30 people waiting to be seated, how long does each person have to wait for a table?
   Rate = 60 customers / 2 hrs = 30 customers / hr
   Waiting time = 1 hour

3. A fast-food restaurant uses 3,500 kilograms of hamburger each week. The manager of the restaurant wants to ensure that the meat is always fresh, i.e., the meat should be no more than two days old on average when used. How much hamburger should be kept in the refrigerator as inventory?
   Rate = 3,500 kilograms per week (= 500 kilograms per day)
   Average flow time = 2 days
   Average inventory = Rate x Average flow time = 500 x 2 = 1,000 kilograms
   (Note that the variables are all in the same time frame i.e. days)

Problem .

Calculate the latency (total delay from first bit sent to last bit received) for the following:

1. Sender and receiver are separated by two 1-Gigabit/s links and a single switch. The packet size is 5000 bits, and each link introduces a propagation delay of 10 microseconds. Assume that the switch begins forwarding immediately after it has received the last bit of the packet and the queues are empty.
   For each link, it takes 1 Gigabits/5 Kbits = 5 microseconds to transmit the packet on the link, after which it takes an additional 10 microseconds for the last bit to propagate across the link. Thus, with only one switch that starts forwarding only after receiving the whole packet, the total transfer delay is two transmit delays + two propagation delays = 30 microseconds.

2. Same as (A) with three switches and four links.
   For three switched and thus four links, the total delta is four transmit delays + four propagation delays = 60 microseconds.

Problem .

Network designers generally attempt to deploy networks that don't have single points of failure, though they don't always succeed. Network topologies that employ redundancy are of much interest.

A. Draw an example of a six-node network in which the failure of a single link does not disconnect the entire network (that is, any node can still reach any other node).

B. Draw an example of a six-node network in which the failure of any single link cannot disconnect the entire network, but the failure of some single node does disconnect it.

C. Draw an example of a six-node network in which the failure of any single node cannot disconnect the entire network, but the failure of some single link does disconnect it.

Note: Not all the cases above may have a feasible example.

Problem .

Under what conditions would circuit switching be a better network design than packet switching?

Problem .

Circuit switching and packet switching are two different ways of sharing links in a communication network. Indicate True or False for each choice.

1. Switches in a circuit-switched network process connection establishment and tear-down messages, whereas switches in a packet-switched network do not.
   True.

2. Under some circumstances, a circuit-switched network may prevent some senders from starting new conversations.
   True.

3. Once a connection is correctly established, a switch in a circuit-switched network can forward data correctly without requiring data frames to include a destination address.
   True.

4. Unlike in packet switching, switches in circuit-switched networks do not need any information about the network topology to function correctly.
   False.

Problem .

Consider a switch that uses time division multiplexing (rather than statistical multiplexing) to share a link between four concurrent connections (A, B, C, and D) whose packets arrive in bursts. The link's data rate is 1 packet per time slot. Assume that the switch runs for a very long time.

1. The average packet arrival rates of the four connections (A through D), in packets per time slot, are 0.2, 0.2, 0.1, and 0.1 respectively. The average delays observed at the switch (in time slots) are 10, 10, 5, and 5. What are the average queue lengths of the four queues (A through D) at the switch?

   With TDMA, each connection gets to send 1 packet every 4 time slots, or .25 packets/slot. And with TDMA, the behavior of each connection is independent of what's happening on the other connections. All of the arrival rates are less than this number, so the queue lengths are bounded.

   Using Little's Law: N = λ*D, so

   A: N = 0.2 * 10 = 2 packets
   B: N = 0.2 * 10 = 2 packets
   C: N = 0.1 * 5 = .5 packets
   D: N = 0.1 * 5 = .5 packets

2. Connection A's packet arrival rate now changes to 0.4 packets per time slot. All the other connections have the same arrival rates and the switch runs unchanged. What are the average queue lengths of the four queues (A through D) now?
   Following the reasoning above, the queues for connections B, C and D are unaffected by the change in A's arrival rate, so the average queue lengths.

   The arrival rate on connection A now exceeds the outgoing rate, so the queue length on A is unbounded.

Problem .

Alyssa P. Hacker has set up eight-node shared medium network running the Carrier Sense Multiple Access (CSMA) MAC protocol. The maximum data rate of the network is 10 Megabits/s. Including retries, each node sends traffic according to some unknown random process at an average rate of 1 Megabit/s per node. Alyssa measures the network's utilization and finds that it is 0.75. No packets get dropped in the network except due to collisions, and each node's average queue size is 5 packets. Each packet is 10000 bits long.

1. What fraction of packets sent by the nodes (including retries) experience a collision?
   Network capacity is 10⁷ bits/s and each packet is 10⁴ bits, so the network can transmit up to 1000 packets/s.

   If the utilization is .75, then 750 packets are delivered each second. In that time the 8 nodes each send 100 packets, for a total of 800 packets. So 50 packets must be lost due to collision, which 50/800 = 6.25%.

2. What is the average queueing delay, in milliseconds, experienced by a packet before it is sent over the medium?
   N = 5 packets, λ = 100 packets/s
   D = N/λ = 5/100 = .05 s.

Problem .

Little's law can be applied to a variety of problems in other fields. Here are some simple examples for you to work out.

1. F freshmen enter MIT every year on average. Some leave after their SB degrees (four years), the rest leave after their MEng (five years). No one drops out (yes, really). The total number of SB and MEng students at MIT is N. What fraction of students do an MEng?
   a = fraction of students who do MEng
   λ = F
   D = (1-a)*4 + a*5 = 4 + a
   N = λ*D → N/F = 4 + a → a = N/F - 4

2. A hardware vendor manufactures $300 million worth of equipment per year (= invoice$/year). On average, the company has $45 million in accounts receivable (= invoice$). How much time elapses between invoicing and payment?
   λ = 300e6 invoice$/year
   N = 45e6 invoice$
   D = N/λ = 45/300 = .15 years = 55 days
   

3. While reading a newspaper, you come across a sentence claiming that "less than 1% of the people in the world die every year". Using Little's law (and some common sense!), explain whether you would agree or disagree with this claim. Assume that the number of people in the world does not decrease during the year (this assumption holds).
   N = people
   λ = .01*N people/year
   D = N/λ = N/(.01*N) = 100 years = life span!

   Since our life span is less than 100, the stated λ must not be correct.

4. (This problem is actually almost related to networks.) Your friendly 6.02 professor receives 200 non-spam emails every day on average. He estimates that of these, 50 need a reply. Over a period of time, he finds that the average number of unanswered emails in his inbox that still need a reply is 100.

   1. On average, how much time does it take for the professor to send a reply to an email that needs a response?
      λ = 50 emails/day
      N = 100 emails
      D = N/λ = 100/50 = 2 days

   2. On average, 6.02 constitutes 25% of his emails that require a reply. He responds to each 6.02 email in 60 minutes, on average. How much time on average does it take him to send a reply to any non-6.02 email?
      average D = 2 days = 48 hours = (.25)(1 hour) + (.75)(x hours)
      x = (48 - .25)/.75 = 63.67 hours

Problem .

You send a stream of packets of size 1000 bits each across a network path from Cambridge to Berkeley. You find that the one-way delay varies between 50 ms (in the absence of any queueing) and 125 ms (full queue), with an average of 75 ms. The transmission rate at the sender is 1 Mbit/s; the receiver gets packets at the same rate without any packet loss.

1. What is the mean number of packets in the queue at the bottleneck link along the path (assume that any queueing happens at just one switch).
   λ = 1 Mb/s = 1000 packets/s
   D = 75-50 ms = 25 ms
   N = λ*D = (1000 p/s)*(.025 s) = 25 packets

You now increase the transmission rate to 2 Mbits/s. You find that the receiver gets packets at a rate of 1.6 Mbits/s. The average queue length does not change appreciably from before.

2. What is the packet loss rate at the switch?
   Send 2000 packets/sec, receive 1600 packets/sec, so loss rate must be 1 - (1600/2000) = 20%.

3. What is the average one-way delay now?
   N = 25 packets (unchanged from above)
   λ = 1600 packets/sec
   D = N/λ = 25/1600 = 15.6 ms

Problem .

Consider the network topology shown below. Assume that the processing delay at all the nodes is negligible.

1. The sender sends two 1000-byte data packets back-to-back with a negligible inter-packet delay. The queue has no other packets. What is the time delay between the arrival of the first bit of the second packet and the first bit of the first packet at the receiver?
   After the first bit of the first packet arrives at the receiver, it will take 1 millisecond for the rest of the packet to arrive (1000 bytes at 1 million bytes/sec).

   Since the connection from the sender is much faster than the connection to the receiver, the second packet arrives in the queue before the first packet has been completely sent to the receiver. That means that the first bit of the second packet is available for sending right after the last bit of the first packet.

   So the total delay is 1 ms.

2. The receiver acknowledges each 1000-byte data packet to the sender, and each acknowledgment has a size A = 100 bytes. What is the minimum possible round trip time between the sender and receiver? The round trip time is defined as the duration between the transmission of a packet and the receipt of an acknowledgment for it.
   The propagation time from the sender to the receiver is 11 ms, which is how long the first bit of a packet takes to arrive assuming no queueing delay in the switch. It then takes another 1 ms for the rest of the packet to arrive. So it takes 12 ms for the complete packet to arrive at the receiver.

   After the complete packet has arrived, the receiver generates an acknowledgment, which takes another 10.1 ms to completely arrive at the switch. Assuming the switch doesn't forward the acknowledgment until it completely arrives, then it takes another 1.001 ms for the acknowledgment to completely arrive at the sender.

   Round trip time = 12 + 10.1 + 1.001 = 23.101 ms. In less picky mode, we'd probably ignore the transmission times of the small packet (.101 ms) as being relatively immaterial.

Problem .

Annette Werker has developed a new switch. In this switch, 10% of the packets are processed on the "slow path", which incurs an average delay of 1 millisecond. All the other packets are processed on the "fast path", incurring an average delay of 0.1 milliseconds. Annette observes the switch over a period of time and finds that the average number of packets in it is 19. What is the average rate, in packets per second, at which the switch processes packets?

Problem .

Alyssa P. Hacker designs a switch for a circuit-switched network to send data on a 1 Megabit/s link using time division multiplexing (TDM). The switch supports a maximum of 20 different simultaneous conversations on the link, and any given sender transmits data in frames of size 2000 bits. Over a period of time, Alyssa finds that the average number of conversations simultaneously using the link is 10. The switch forwards a data frame sent by a given sender every δ seconds according to TDM. Determine the value of δ