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?
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)
Calculate the latency (total delay from first bit sent to last bit
received) for the following:
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.
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.
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.
Here is an example topology for part A (left) and B (right).
C. Impossible. If the failure of some link disconnects the network,
then pick a node adjacent to that link and fail it. The link in
question will fail, and the network will be disconnected, violating
the condition that the failure of any single node cannot disconnect
Under what conditions would circuit switching be a better network
design than packet switching?
Circuit switching offers
guaranteed capacity. Once a circuit has been estabilished,
a TDMA slot has been reserved in each cycle to service this connection.
no reordering of packets. Since all packets travel the same
path, the arrive in the same order as sent.
bounded delay. Packets move at a fixed pace along the
links in the circuit, so their arrival time can be predicted with
no lost packets. Since there are no collisions or queue
overflows, packets don't get dropped by the network.
Various streaming applications (VOIP, video streaming, real-time
monitoring, ...) would benefit from these features.
Circuit switching and packet switching are two different ways of
sharing links in a communication network. Indicate True or False for
Switches in a circuit-switched network process connection establishment and
tear-down messages, whereas switches in a packet-switched network do not.
Under some circumstances, a circuit-switched network may prevent some senders
from starting new conversations.
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.
Unlike in packet switching, switches in circuit-switched networks do not need
any information about the network topology to function correctly.
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.
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
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.
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.
What fraction of packets sent by the nodes (including retries)
experience a collision?
Network capacity is 107 bits/s and each packet is
104 bits, so the network can transmit up to
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%.
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.
Little's law can be applied to a variety of problems in other
fields. Here are some simple examples for you to work out.
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
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
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.
(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.
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
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
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.
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.
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%.
What is the average one-way delay now?
N = 25 packets (unchanged from above)
λ = 1600 packets/sec
D = N/λ = 25/1600 = 15.6 ms
Consider the network topology shown below. Assume that the processing
delay at all the nodes is negligible.
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.
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.
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?
N = 19 packets
D = (.1)(1 ms) + (.9)(.1 ms) = .19 ms
λ = N/D = 19/.00019 = 100000 packets/s
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 δ
Each frame (2000 bits) takes 2e3/1e6 = 2 ms. With 20 conversations,
it takes 20*2 = 40 ms for one complete cycle (δ) through the TDM schedule.