Problem 1.
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/5Kb = 5 micro seconds to transmit the
packet on the link, after which it takes an additional 10 micro
seconds 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.
Problem 2. Little's Law.
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?
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)
A hardware vendor manufactures $300 million worth of PCs per
year. On average, the company has $45 million in accounts receivable.
How much time elapses between invoicing and payment?
Rate= $300 million per year
Average "inventory" = $45 million
Average "flow time" = 45 / 300 per year = .15 years = 1.8 months = 54 days
Problem 3.
Consider the following networks: network I (containing nodes A, B, C) and network II
(containing nodes D, E, F).
The Distance Vector Protocol described in class is used in both
networks. Assume advertisements are sent every 5 time steps, all
links are fully functional and there is no delay in the links. Nodes
take zero time to process advertisements once they receive them. The
HELLO protocol runs in the background every time step in a way that
any changes in link connectivity are reflected in the next DV
advertisement. We count time steps from t=0 time steps.
Please fill in the following table:
Event
Number of time steps
A's routing table has an entry for B
A's routing table has an entry for C
D's routing table has an entry for E
F's routing table has an entry for D
A's routing table has an entry for B: 5 time steps
A's routing table has an entry for C: 10 time steps
D's routing table has an entry for E: 5 time steps
F's routing table has an entry for D: 5 time steps
Now assume the link B-C fails at t = 51 and link D-E fails
at t = 71 time steps. Please fill in this table:
Event
Number of time steps
B's advertisements reflect that C is unreachable
A's routing table reflects C is unreachable
D's routing table reflects a new route for E
B's advertisements reflect that C is unreachable: 55 time steps
A's routing table reflects C is unreachable: 55 time steps
D's routing table reflects a new route for E: 75 time steps
Problem 4.
Alyssa P. Hacker manages MIT's internal network that runs link-state
routing. She wants to experiment with a few possible routing
strategies. Of all possible paths available to a particular
destination at a node, a routing strategy specifies the path that must
be picked to create a routing table entry. Below is the name Alyssa
has for each strategy and a brief description of how it works.
MinCost: Every node picks the path that has the smallest sum of link
costs along the path. (This is the minimum cost routing you
implemented in the lab).
MinHop: Every node picks the path with the smallest number of hops
(irrespective of what the cost on the links is).
SecondMinCost: Every node picks the path with the second lowest sum
of link costs. That is, every node picks the second best path with
respect to path costs.
MinCostSquared: Every node picks the path that has the smallest sum of
squares of link costs along the path.
Assume that sufficient information (e.g., costs, delays,
bandwidths, and loss probabilities of the various links) is exchanged
in the link state advertisements, so that every node has complete
information about the entire network and can correctly implement the
strategies above. You can also assume that a link's properties don't
change, e.g., it doesn't fail.
Help Alyssa figure out which of these strategies will work
correctly, and which will result in routing with loops. In case of
strategies that do result in routing loops, come up with an example
network topology with a routing loop to convince Alyssa.
Answer: All except SecondMinCost will work fine.
To see why SecondMinCost will not work: consider the triangle topology
with 3 nodes A, B, D, and equal cost on all the links. The second
route at A to D is via B, and the second best route at B to D is via
A, resulting in a routing loop.
How would you implement MinCostSquared in a distance-vector
protocol?
To implement MinCostSquared, your integrate_announcement routine
would add the square of the link cost (instead of just the link cost)
to any route costs advertised over that link.
Problem 5.
Consider the following chain topology:
A ---- B ----- C ---- D ---- E
A is sending packets to E using a reliable transport protocol. Each
link above can transmit one packet per second. There are no queues or
other sources of delays at the nodes (except the transmission delay of
course).
What is the RTT between A and E?
8 seconds
What is the throughput of a stop-and-wait protocol at A in the
absence of any losses at the nodes?
1/8 pkts/s
If A decides to run a sliding window protocol, what is the optimum
window size it must use? What is the throughput achieved when using
this optimum window size?
Suppose A is running a sliding window protocol with a window size
of four. In the absence of any losses, what is the throughput at E?
What is the utilization of link B-C?
throughput=0.5 pkts/s, utilization=0.5
Consider a sliding window protocol running at the optimum window
size found in part 3 above. Suppose nodes in the network get
infected by a virus that causes them to drop packets when odd
sequence numbers. The sliding window protocol starts
numbering packets from sequence number 1. Assume that the sender
uses a timeout of 40 seconds. The receiver buffers out-of-order
packets until it can deliver them in order to the application. What
is the number of packets in this buffer 35 seconds after the sender
starts sending the first packet?
Answer: 7.
With a window size of 8, the sender sends out packets 1--8 in the
first 8 seconds. But it gets back only 4 ACKs because packets 1,3,5,7
are dropped. Therefore, the sender transmits 4 more packets (9--12) in
the next 8 seconds, 2 packets (13--14) in the next 8 seconds, and 1
(sequence number 15) packet in the next 8 seconds. Note that 32
seconds have elapsed so far. Now the sender gets no more ACKs because
packet 15 is dropped, and it stalls till the first packet times out at
time step 40. Therefore, at time 35, the sender would have transmitted
15 packets, 7 of which would have reached the receiver. But because
all of these packets are out of order, the receiver's buffer would
have 7 packets.
Problem 6.
Which of these statements are true for correctly implemented
versions of stabilized unslotted Aloha, stabilized slotted Aloha, and
Time Division Multiple Access (TDMA)? Assume that the slotted and
unslotted versions of Aloha use the same stabilization method and
parameters.
When the number of nodes is large, unslotted Aloha has a lower
maximum throughput than slotted Aloha.
True. By a factor of 2: 1/2e instead of 1/e.
When the number of nodes is large and nodes transmit data according
to a Poisson process, there exists some offered load for which
the throughput of unslotted Aloha is higher than the throughput of
slotted Aloha.
False.
TDMA has no packet collisions.
True. TDMA eliminates collisions by explicitly allotting time slots.
There exists some offered load pattern for which TDMA has lower
throughput than slotted Aloha.
True. For example, a skewed workload in which some nodes have much
more traffic to send than others.
Problem 7.
Binary exponential backoff is a mechanism used in some MAC protocols.
Which of the following statements is correct?
A. It ensures that two nodes that experience a collision in a
time slot will never collide with each other when they each
retry that packet.
B. It ensures that two or more nodes that experience a collision in a
time slot will experience a lower probability of colliding with each
ther when they each retry that packet.
C. It can be used with slotted Aloha but not with carrier sense multiple access.
D. Over short time scales, it improves the fairness of the
throughput achieved by different nodes compared to not using the
mechanism.
B is true. The others are false.
Problem 8.
Consider a shared medium with N nodes running the slotted Aloha MAC
protocol without any backoffs. A "wasted slot" is one in which no
node sends data. The fraction of time during which no node uses the
medium is the "waste" of the protocol.
If the sending probability is p, what is the waste? What are
the smallest and largest possible values of the waste?
(1-p)N. 0 and 1.
If the Aloha sending probability, p, for each node is picked so
as to maximize the utilization, what is the corresponding waste?
1/e --> same as the utlization!
Problem 9.
Alyssa and Ben are all on a shared medium wireless network running a
variant of slotted Aloha. Their computers are configured such that Alyssa is
1.5 times as likely to send a packet as Ben. Assume that both computers are
backlogged.
For Alyssa and Ben, what is their probability of transmission
such that the utilization of their network is maximized?
With just two nodes U = (A's throughput + B's throughput)/max rate.
max rate is 1 packet per time step (slotted Aloha)
find max U by differentiating and setting to 0, solving for p
0 = 2.5 - 6p => p = 2.5/6 = 5/12
So P_a = 5/8, P_b = 5/12.
What is the maximum utilization?
Determine Umax by substituting 5/12 for p in equation for U in part A.
Umax = (2.5)(5/12) - (3)(25/144) = 25/48 = 0.5208
Problem 10.
True or false?
Assume that the shared medium has N nodes and they are always
backlogged.
In a slotted Aloha MAC protocol using binary exponential backoff,
the probability of transmission will always eventually converge to some
value p, and all nodes will eventually transmit with probability p.
False - In a binary exponential backoff, the probability of
transmission constantly changes. If the a transmission succeeds, then
the probability goes up. If the transmission fails, the probability
goes down.
Using carrier sense multiple access (CSMA), suppose that a node
"hears" that the channel is busy at time slot t. To maximize utilization,
the node should not transmit in slot t and instead transmit the packet
in the next time slot with probability 1.
False - The node should not transmit at time t+1 with 100%
probability. Other nodes may have also "heard" that the channel is
busy and would want to send a packet at time t+1. So the node should
send with a probability less than 100% to reduce the possibility of a
collision.
There is some workload for which an unslotted Aloha with
perfect CSMA will not achieve 100% utilization.
True - Multiple nodes may think that the channel is idle and send a
packet at the same time, resulting in a collision. Thus, the
utilization can never reach 100%.
Problem 11. Time-domain multiplexing.
Eight Cell Processor cores are connected together with a shared
bus. To simplify bus arbitration, Ben Bittdidle, young IBM
engineer, suggested time-domain multiplexing (TDM) as an arbitration
mechanism. Using TDM each of the processors is allocated a
equal-sized time slots on the common bus in a round-robin fashion.
He's been asked to evaluate the proposed scheme on two types of
applications: 1) core-to-core streaming, 2) random loads.
1) Core-to-core streaming setup: Assume each core has the same stream bandwidth requirement.
Help Ben out by evaluating the effectiveness (bus utilization) of
TDM under these two traffic scenarios.
1) All cores have same bandwidth requirements during streaming, so,
bus utilization is 100%
2) Each core is given 12.5% of bus bandwidth, but not all cores can
use it, and some need more than that. So bus utilization is: 12.5% +
12.5% + 10% + 5% + 1% + 3% + 1% + 12.5% = 57.5%
Problem 12.
Circuit switching and packet switching are two different ways of
sharing links in a communication network. Indicate True or False for
each choice.
Switches in a circuit-switched network process connection establishment and
tear-down messages, whereas switches in a packet-switched network do not.
True.
Under some circumstances, a circuit-switched network may prevent some senders
from starting new conversations.
True.
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.
Unlike in packet switching, switches in circuit-switched networks do not need
any information about the network topology to function correctly.
False.
Problem 13.
Which of the following tasks does a router R in a packet-switched network perform when it gets
a packet with destination address D? Indicate True or False for each choice.
R looks up D in its routing table to determine the outgoing link.
True.
R sends out a HELLO packet or a routing protocol advertisement to its neighbors.
False.
R calculates the minimum-cost route to destination D.
False.
R may discard the packet.
True.
Problem 14.
Over many months, you and your friends have painstakingly collected a
1,000 Gigabytes (aka 1 Terabyte) worth of movies on computers in your
dorm (we won't ask where the movies came from). To avoid losing it,
you'd like to back the data up on to a computer belonging to one of
your friends in New York.
You have two options:
A. Send the data over the Internet to the computer in New York. The data rate for transmitting
information across the Internet from your dorm to New York is 1 Megabyte per second.
B. Copy the data over to a set of disks, which you can do at 100
Megabytes per second (thank you, firewire!). Then rely on the US
Postal Service to send the disks by mail, which takes 7 days.
Which of these two options (A or B) is faster? And by how much?
Method A takes (1000 * 109 bytes)/(106 bytes/s) = 11.5 days
Method B takes (1000 * 109 bytes)/(100 * 106 bytes/s) + 7 days = 7.1 days
Method B is 4.4 days faster than Method A!
Problem 15.
Alice and Bob are responsible for implementing Dijkstra's
algorithm at the nodes in a net- work running a link-state
protocol. On her nodes, Alice implements a minimum-cost algorithm. On
his nodes, Bob implements a "shortest number of hops"
algorithm. Give an example of a network topology with 4 or more nodes
in which a routing loop occurs with Alice and Bob's
implementations running simultaneously in the same network. Assume
that there are no failures.
(Note: A routing loop occurs when a group
of k ≥ 1 distinct nodes, n_0 , n_1 , n_2 , …, n_(k-1) have routes
such that n_i's next-hop (route) to a destination is n_(i+1 mod k).
In the picture below, the grey nodes (A in particular) run
Bob's algorithm (shortest number of hops), while the white
nodes (B in particular) run Alice's (minimum-cost).
Suppose the destination is E. A will pick B as its next hop because
ABE is the shortest path. B will pick A as its next hop because BACDE
is the minimum-cost path (cost of 4, compared to 11 for the ABE
path). The result is a routing loop ABABAB...
Problem 16.
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
the network.
Problem 17.
Consider the network shown below. The number near each link is its cost.
We're interested in finding the shortest paths (taking costs into
account) from S to every other node in the network. What is the
result of running Dijkstra's shortest path algorithm on this network?
To answer this question, near each node, list a pair of numbers: The
first element of the pair should be the order, or the iteration of the
algorithm in which the node is picked. The second element of each pair
should be the shortest path cost from S to that node.
To help you get started, we've labeled the first couple of nodes: S
has a label (Order: 0, Cost: 0) and A has the label (Order: 1, Cost:
2).
A: order = 1, cost = 2
E: order = 2, cost = 3
B: order = 3, cost = 4
C: order = 4, cost = 5
D: order = 5, cost = 6
Problem 18.
Consider any two graphs(networks) G and G' that are identical except
for the costs of the links. Please answer these questions.
The cost of link l in graph G is c_l > 0, and the cost of
the same link l in Graph G' is k*c_l, where k > 0 is a constant
and the same scaling relationship holds for all the links.
Are the shortest paths between any two nodes in the two graphs
identical? Justify your answer.
Yes, they're identical. Scaling all the costs by a constant factor doesn't
change their relative size.
Now suppose that the cost of a link l in G'
is k*c_l + h, where k > 0 and h > 0 are
constants. Are the shortest paths between any two nodes in the two
graphs identical? Justify your answer.
No, they're not necessarily identical. Consider two paths between nodes A and
B in graph G. One path takes 3 hops, each of cost 1, for a total cost of 3. The
other path takes 1 hop, with a cost of 4. In this case, the shortest path between
nodes A and B is the first one.
Consider k=1 and h=1 and compute the costs and shortest paths in G'. Now the
3-hop path has cost 6 and the 1-hop path has cost 5. In G' the shortest path is
the second path.
Problem 19.
Ben Bitdiddle implements a reliable data transport protocol intended
to provide "exactly once" semantics. Each packet has an 8-bit
incrementing sequence number, starting at 0. As the connection
progresses, the sender "wraps around" the sequence number once it
reaches 255, going back to 0 and incrementing it for successive
packets. Each packet size is S = 1000 bytes long (including all packet
headers).
Suppose the link capacity between sender and receiver is C = 1
Mbyte per second and the round-trip time is R = 100 milliseconds.
What is the highest throughput achievable if Ben's
implementation is stop-and-wait?
The highest throughput for stop-and-wait is (1000 bytes)/(100ms) =
10 Kbytes/s.
To improve performance, Ben implements a sliding window
protocol. Assuming no packet losses, what should Ben set the window
size to in order to saturate the link capacity?
Set the window size to the bandwidth-delay product of the link, 1 Mbyte/s
* 0.1 s = 100 Kbytes.
Ben runs his protocol on increasingly higher-speed bottleneck
links. At a certain link speed, he finds that his implementation stops
working properly. Can you explain what might be happening? What
threshold link speed causes this protocol to stop functioning
properly?
Sequence number wraparound causes his protocol to stop functioning
properly. When this happens, two packets with different content but
the same sequence number are in-flight at once, and so an ack for the
firstt spuriously acknowledges the second as well, possibly causing
data loss in Ben's "reliable" protocol. This happens when
Problem 20.
A sender S and receiver R are connected over a network that has k
links that can each lose packets. Link i has a packet loss rate of p_i
in one direction (on the path from S to R) and q_i in the other (on the
path from R to S). Assume that each packet on a link is received or
lost independent of other packets, and that each packet's loss
probability is the same as any other's (i.e., the random process
causing packet losses is indepedent and identically distributed).
Suppose that the probability that a data packet does not reach
R when sent by S is p and the probability that an ACK packet sent by R
does not reach S is q. Write expressions for p and q in terms of the
p_i's and q_i's.
If all p's are equal to some value α << 1 (much smaller
than 1), then what is p (defined above) approximately equal to?
p = 1 - (1 - &alpha)k ≈1 - (1 - kα) = kα
Suppose S and R use a stop-and-wait protocol to
communicate. What is the expected number of transmissions of a packet
before S can send the next packet in sequence? Write your answer in
terms of p and q (both defined above).
The probability of a packet reception from S to R is 1-p and the probability of an ACK reaching
S given that R sent an ACK is 1-q. The sender moves from sequence number k to k + 1 if the
packet reaches and the ACK arrives. That happens with probability (1-p)(1-q). The expected
number of transmissions for such an event is therefore equal to 1/((1-p)(1-q)).
Problem 21.
On the Internet, TCP checksums all the data it sends even when each
link on the path has its own CRC-based checksum. Should TCP save the
network bandwidth consumed by its checksums over such paths and get
rid of it?
No. Errors in the switch or the end point's network layer
could cause the data to be corrupted even though each link has good
error detection.
Problem 22.
Consider a 40 kbit/s network link connecting the earth to the
moon. The moon is about 1.5 light-seconds from earth.
1 Kbyte packets are sent over this link using a stop-and-wait
protocol for reliable delivery, what data transfer rate can be
achieved? What is the utilization of the link?
Stop-and-wait sends 1 packet per round-trip-time so the data
transfer rate is 1 Kbyte/3 seconds = 333 bytes/s = 2.6 Kbit/s.
The utilization is 2.6/40 = 6.5%.
If a sliding-window protocol is used instead, what is the
smallest window size that achieves the maximum data rate? Assume that
error are infrequent. Assume that the window size is set to achieve
the maximum data transfer rate.
Achieving full rate requires a send window of at least
Consider a sliding-window protocol for this link with a window
size of 10 packets. If the receiver has a buffer for only 30 undelivered
packets (the receiver discards packets it has no room for, and sends
no ACK for discarded packets), how bits of sequence number are needed?
The window size determines the number of unacknowledged packets the
transmitter will send before stalling, but there can be arbitrarily
many acknowledged but undelivered (because of one lost packet) packets
at the receiver. But if only 30 packets are held at the receiver,
after which it stops acknowledging packets except the one it's
waiting for, the total number of packets in transit or sitting in
the receivers buffer is at most 40.
So a 6-bit sequence number will be sufficent to ensure that all
unack'ed and undelivered packets have a unique sequence number (avoiding
the sequence number wrap-around problem).
Problem 23.
Huffman and other coding schemes tend to devote more bits to the coding of
(A) symbols carrying the most information
(B) symbols carrying the least information
(C) symbols that are likely to be repeated consecutively
(D) symbols containing redundant information
Answer is (A). Symbols carrying the most information, i.e., the symbols that are less
likely to occur. This makes sense: to keep messages as short as possible, frequently
occurring symbols should be encoded with fewer bits and infrequent symbols with
more bits.
Problem 24.
Consider the following two Huffman decoding tress for a variable-length
code involving 5 symbols: A, B, C, D and E.
Using Tree #1, decode the following encoded message: "01000111101".
Starting at the root of the decoding tree, use the bits of the message
to traverse the tree until a leaf node is reached; output that symbol.
Repeat until all the bits in the message are consumed.
0 = A
100 = B
0 = A
111 = E
101 = C
Suppose we were encoding messages with the following
probabilities for each of the 5 symbols: p(A) = 0.5, p(B) = p(C) =
p(D) = p(E) = 0.125. Which of the two encodings above (Tree #1 or
Tree #2) would yield the shortest encoded messages averaged over many
messages?
Using Tree #1, the expected length of the encoding for one symbol is:
1*p(A) + 3*p(B) + 3*p(C) + 3*p(D) + 3*p(E) = 2.0
Using Tree #2, the expected length of the encoding for one symbol is:
2*p(A) + 2*p(B) + 2*p(C) + 3*p(D) + 3*p(E) = 2.25
So using the encoding represented by Tree #1 would yield shorter messages on the
average.
Using the probabilities of part (B), if you learn that the first symbol in a message is "B",
how many bits of information have you received?
bits of info received = log2(1/p) = log2(1/.125) = 3
Using the probabilities of part (B), If Tree #2 is used to encode messages what is the average
length of 100-symbol messages, averaged over many messages?
In part (B) we calculated that the expected length of the encoding for
one symbol using Tree #2 was 2.25 bits, so for 100-symbol messages the
expected length is 225 bits.
Problem 25.
Huffman coding is used to compactly encode the species of fish tagged
by a game warden. If 50% of the fish are bass and the rest are evenly
divided among 15 other species, how many bits would be used to encode
the species when a bass is tagged?
If a symbol has a probability of ≥ .5, it will be incorporated into the
Huffman tree on the final step of the algorithm, and will become a child
of the final root of the decoding tree. This means it will have a 1-bit
encoding.
Problem 26.
Ben Bitdiddle has been hired by the Registrar to help redesign the grades
database for WebSIS. Ben is told that the database only needs to store one of five
possible grades (A, B, C, D, F). A survey of the current WebSIS repository reveals the
following probabilities for each grade:
Grade
Probability of occurrence
A
p(A) = 18%
B
p(B) = 27%
C
p(C) = 25%
D
p(D) = 15%
F
p(E) = 15%
Given the probabilities above, if you are told that a
particular grade is "C", give an expression for the number of bits of
information you have received.
# of bits for "C" = log(1/pC) = log(1/.25) = log(4) = 2
Ben is interested in storing a sequence of grades using as few
bits as possible. Help him out by creating a variable-length encoding
that minimizes the average number of bits stored for a sequence of
grades. Use the table above to determine how often a particular grade
appears in the sequence.
using Huffman algorithm:
- since D,F are least probable, make a subtree of them, p(D/\F) = 30%
- now A,C are least probable, make a subtree of them, P(A/\C) = 43%
- now B,DF are least probable, make a subtree of them P(B/\(D/\F)) = 55%
- just AC,BDF are left, make a subtree of them (A/\C)/\(B/\(D/\F))
- so A = 00, B = 10, C = 01, D = 110, F = 111
Problem 27.
Consider a sigma-delta modulator used to convert a particular analog waveform
into a sequence of 2-bit values. Building a histogram from the 2-bit values we get the
following information:
Modulator value
# of occurrences
00
25875
01
167836
10
167540
11
25974
Using probabilities computed from the histogram, construct a
variable-length Huffman code for encoding these four values.
If we transmit the 2-bit values as is, it takes 2 bits to send
each value (doh!). If we use the Huffman code from part (A) what is
the average number of bits used to send a value? What compression
ratio do we achieve by using the Huffman code?
sum(pi*len(code for pi)) = 1.7005, which is 85% of the original 2- bit per symbol
encoding.
Using Shannon's entropy formula, what is the average information content
associated with each of the 2-bit values output by the modulator? How does this
compare to the answers for part (B)?
sum(pi*log2(1/pi)) = 1.568, so the code of part(B) isn't quite as efficient as
we can achieve by using an encoding that codes multiple pairs as in one code
symbol.
Problem 28.
Several people at a party are trying to guess a 3-bit binary number. Alice is
told that the number is odd; Bob is told that it is not a multiple of 3 (i.e., not 0, 3, or 6);
Charlie is told that the number contains exactly two 1's; and Deb is given all three of
these clues. How much information (in bits) did each player get about the number?
N = 8 choices for a 3-bit number
Alice: odd = {001, 011, 101, 111} M=4, info = log2(8/4) = 1 bit
Bob: not a multiple of 3 = {001, 010, 100, 101, 111} M=5, info = log2(8/5) = .6781 bits
Charlie: two 1's = {011, 101, 110} M=3, info = log2(8/3) = 1.4150
Deb: odd, not a multiple of 3, two 1's = {101}, M=1, info = log(8/1) = 3 bits
Problem 29.
In honor of Daisuke Matsuzaka's first game pitching for the Redsox, the
Boston-based members of the Search for Extraterrestrial Intelligence (SETI) have
decided to broadcast a 1,000,000 character message made up of the letters "R", "E", "D",
"S", "O", "X". The characters are chosen at random according the probabilities given in
the table below:
Letter
p(Letter)
R
.21
E
.31
D
.11
S
.16
O
.19
X
.02
If you learn that one of the randomly chosen letters is a vowel
(i.e., "E" or "O") how many bits of information have you received?
p(E or O) = .31 + .19 = .5, log2(1/pi) = 1 bit
Nervous about the electric bill for the transmitter at Arecibo,
the organizers have asked you to design a variable length code that
will minimize the number of bits needed to send the message of
1,000,000 randomly chosen characters. Please draw a Huffman decoding
tree for your code, clearly labeling each leaf with the appropriate
letter and each arc with either a "0" or a "1".
Huffman algorithm:
choose X,D: X/\D, p = .13
choose S,XD: S/\(X/\D), p = .29
choose R,0: R/\O, p = .40
choose E,SXD: E/\(S/\(X/\D)), p = .6
choose RO,ESXD: (R/\O) /\ (E/\(S/\(X/\D)))
code: R=00 O=01 E=10 S=110 X=1110 D=1111
Using your code, what bit string would they send for "REDSOX"?
00 10 1111 110 01 1110
Problem 30.
You're playing an on-line card game that uses a deck of 100 cards containing 3 Aces, 7 Kings, 25
Queens, 31 Jacks and 34 Tens. In each round of the game the cards are shuffled, you make a bet
about what type of card will be drawn, then a single card is drawn and the winners are paid off.
The drawn card is reinserted into the deck before the next round begins.
How much information do you receive when told that a Queen has
been drawn during the current round?
information received = log2(1/p(Queen)) = log2(1/.25) = 2 bits
Give a numeric expression for the average information content received when
learning about the outcome of a round.
Construct a variable-length Huffman encoding that minimizes the length of
messages that report the outcome of a sequence of rounds. The outcome of a single round is
encoded as A (ace), K (king), Q (queen), J (jack) or X (ten). Specify your
encoding for each of A, K, Q, J and X.
Encoding for A: 001
Encoding for K: 000
Encoding for Q: 01
Encoding for J: 11
Encoding for X: 10
Using your code from part (C) what is the expected length of a message reporting
the outcome of 1000 rounds (i.e., a message that contains 1000 symbols)?
(.07+.03)(3 bits) + (.25+.31+.34)(2 bits) = 2.1 bits average symbol length using Huffman code.
So expected length of 1000-symbol message is 2100 bits.
The Nevada Gaming Commission regularly receives messages in which the
outcome for each round is encoded using the symbols A, K, Q, J and X. They discover that
a large number of messages describing the outcome of 1000 rounds (i.e. messages with 1000
symbols) can be compressed by the LZW algorithm into files each containing 43 bytes in
total. They immediately issue an indictment for running a crooked game. Briefly explain
their reasoning.
In order to achieve such a dramatic compression ratio, the original
messages much have exhibited a very regular pattern - regular patterns
would be very rare if the outcomes were truly random, hence the
conclusion that the game was rigged. LZW should exhibit some
improvement over Huffman since it will compactly encode pairs,
triples, etc. But for messages of only 1000 symbols that process
would not achieve an almost 10-to-1 improvement over Huffman.
Problem 31.
X is an unknown 8-bit binary number. You are given another 8-bit
binary number, Y, and told that the Hamming distance between X (the
unknown number) and Y (the number you know) is one.
How many bits of information about X have you been given?
You've learned that X differs in exactly 1 of its 8 bits from the known number
Y. So that means that knowing Y, we've narrowed down the value of
X to one of 8 choices. Bits of information = log2(256/8) = 5 bits.
Problem 32.
In Blackjack the dealer starts by dealing 2 cards each to himself and
his opponent: one face down, one face up. After you look at your
face-down card, you know a total of three cards. Assuming this was
the first hand played from a new deck, how many bits of information do
you now have about the dealer's face down card?
We've narrowed down the choices for the dealer's face-down card from
52 (any card in the deck) to one of 49 cards (since we know it can't
be one of three visible cards. bits of information = log2(52/49).
Problem 33.
The following table shows the current undergraduate and MEng enrollments for the School of
Engineering (SOE).
Course (Department)
# of students
Prob.
I (Civil & Env.)
121
.07
II (Mech. Eng.)
389
.23
III (Mat. Sci.)
127
.07
VI (EECS)
645
.38
X (Chem. Eng.)
237
.13
XVI (Aero & Astro)
198
.12
Total
1717
1.0
When you learn a randomly chosen SOE student's department you
get some number of bits of information. For which student department
do you get the least amount of information?
We'll get the smallest value for log2(1/p) by choosing the choice
with the largest p => EECS.
Design a variable length Huffman code that minimizes the average number of
bits in messages encoding the departments of randomly chosen groups of students. Show
your Huffman tree and give the code for each course.
code for course I: 0 1 1 0
code for course II: 0 1 0
code for course III: 0 1 1 1
code for course VI: 1
code for course X: 0 0 0
code for course XVI: 0 0 1
There are of course many equivalent codes derived by swapping the
"0" and "1" labels for the children of any interior node of the decoding
tree. So any code that meets the following constraints would be fine:
code for VI = length 1
code for II, X, XVI = length 3
code for I, III = length 4
If your code is used to send messages containing only the encodings of the
departments for each student in groups of 100 randomly chosen students, what's the
average length of such messages? Write an expression if you wish.
an empty routing tree generated by Dijkstra's algorithm for node A
(to every other node) is shown below. Fill in the missing nodes and
indicate the order that each node was added and its associated
cost. For reference, node C's completed routing tree is shown as well.
Now assume that node F has been added to the network along with
links L1, L2 and L3.
What are the constraints on L1, L2 and L3 such that node A's
routing tree matches the topology shown below, and it is known that
node F is not the last node added when using Dijkstra's algorithm?
Problem 35. MAC protocol
Randomized exponential backoff is a mechanism used to stabilize
contention MAC protocols. Which of the following statements is
correct?
It ensures that two nodes that experience a collision in a
time-slot will never collide with each other when they each
retry that packet.
False. They might get unlucky and back-off the same amount.
It ensures that two or more nodes that experience a collision
n a time-slot will experience a lower probability of colliding with
ach other when they each retry that packet.
True. The probability of a repeat collision is a smaller in each
subsequent backoff.
It can be used with slotted Aloha but not with CSMA.
False. It can be used in any contention protocol.
Problem 36.
Next generation Ntel processor will contain 64 cores and have an
on-chip network with one router per core. Router has 5 ports (north,
south, east, west and a local port to core). Ntel engineers would
like to size the network so it supports data traffic for 1TFlop/s
computation. Assume that roughly 1Byte of traffic is needed for each
floating point operation.
Determine the bandwidth of router-to-router links to support
1TFlop/s computation under uniform random traffic assumption (i.e.
assume that each core wants to communicate to all other cores with
same probability).
Half of the generated traffic in one half of the cores will go to the
other half of the cores, hence the router to router links in the
middle of the chip have to support the traffic.
(1/2)*(Ncores/2)*Rcore = sqrt(Ncores)*B (where B is the router-to-router
link bandwidth)
What would be the router-to-router link size needed to support
the same computation provided that a communication pattern is only
between neighboring cores (e.g in chain/ring like core (1,1) to core
(1,2), core(1,2) to core (1,3), etc).
B' = Rcore = 1TFlop/s*1Byte/Flop / Ncores = 16 GB/s
What is the diameter of this mesh network (assuming x-y
routing)?
Diameter of the network is 14 (7 x hops and 7 y hops).
A message between two cores is usually a cache line (512 b). It
is divided into packets (flits) that are as wide as the
router-to-router link. Assuming 2GHz processor frequency and
router-to-router link frequency, determine the flit size (i.e. how
many wires there are per link), to support link bandwidth in a). How
many flits per message?
B = 32 GB/s, nb = 32 GB/s / 2 GHz = 16 B = 128 b, so flit size is 128 bits.
There are 4 flits per message.
Assuming that link latency is 1 cycle, router latency is 2
cycles (without queue delay), determine the worst-case latency that a
message experiences in the lightly loaded network (so called zero-load
latency, ZLL).
Since diameter of the network is 14, zero load latency consists of 14
link traversals, 15 router traversals, and serialization latency at
the source.
Since message has 4 flits, and link bandwidth is flit per cycle,
serialization latency is 4 cycles.
ZLL = 4+ 14*1+15*2 = 48 cycles.
Problem 37. "Information, please"
You're given a standard deck of 52 playing cards that you start
to turn face up, card by card. So far as you know, they're in
completely random order. How many new bits of information do you get
when the first car is flipped over? The fifth card? The last card?
First card: log2(52/1)
Fifth card: log2(48/1)
Last card: log2(1/1) = 0 (no information since, knowing the other
51 cards, one can predict with certainty the last card)
Suppose there three alternatives ("A", "B" and "C") with the
following probabilities of being chosen:
p("A") = 0.8
p("B") = 0.1
p("C") = 0.1
We might encode the of "A" with the bit string "0", the choice
of "B" with the bit string "10" and the choice of "C" with the bit
string "11".
If we record the results of making a sequence of choices by
concatenating in left-to-right order the bit strings that encode
each choice, what sequence of choices is represented by the bit
string "00101001100000"?
AABBACAAAAA
Using the encoding of the previous part, what is the expected
length of the bit string that encodes the results of making 1000
choices? What is the length in the worst case? How do these numbers
compare with 1000*log2(3/1), which is the information content of
1000 equally-probable choices?
In the worst case, each choice would take 2 bits to encode = 2000 bits.
1000*log2(3/1) = 1585. In general, a variable-length encoding of sequences
of N choices with differing probabilities gets better compression than can
be achieved if the choices are equally probable.
Consider the sum of two six-sided dice. Even when the dice are
"fair" the amount information conveyed by a single sum depends on what
the sum is since some sums are more likely than others, as shown in
the following figure:
What is the average number of bits of information provided by the sum
of 2 dice? Suppose we want to transmit the sums resulting from rolling
the dice 1000 times. How many bits should we expect that transmission
to take?
Average number of bits = sum (p_i)log2(1/p_i) for i = 2 through
12. Using the probabilities given in the figure above the average
number of bits of information provided by the sum of two dice is
3.2744.
So if we had the perfect encoding, the expected length of the
transmission would be 3274.4 bits. If we encode each sum separately we
can't quite achieve this lower bound -- see the next question for
details.
Suppose we want to transmit the sums resulting from rolling the
dice 1000 times. If we use 4 bits to encode each sum, we'll need 4000
bits to transmit the result of 1000 rolls. If we use a variable-length
binary code which uses shorter sequences to encode more likely sums
then the expected number of bits need to encode 1000 sums should be
less than 4000. Construct a variable-length encoding for the sum of
two dice whose expected number of bits per sum is less than
3.5. (Hint: It's possible to find an encoding for the sum of two dice
with an expected number of bits = 3.306.)
Using Huffman's algorithm, we arrive at the following encoding which
has 3.3056 as the expected number of bits for each sum.
Can we make an encoding for transmitting 1000 sums that has an
expected length smaller than that achieved by the previous part?
Yes, but we have to look at encoding more than one sum at a time,
e.g., by applying the construction algorithm to pairs of sums, or
ultimately to all 1000 sums at once. Many of the more sophisticated
compression algorithms consider sequences of symbols when constructing
the appropriate encoding scheme.
Problem 38. MAC protocols
Three users X, Y and Z use a shared link to connect to the
Internet. Only one of X, Y or Z can use the link at a given time. The
link has a capacity of 1Mbps. There are two possible strategies for
accessing the shared link:
TDMA: equal slots of 0.1 seconds.
"Taking turns": adds a latency of 0.05 seconds before taking the
turn. The user can then use the link for as long as it has data to
send. A user requests the link only when it has data to send.
In each of the following two cases, which strategy would you pick and why?
X, Y and Z send a 40KBytes file every 1sec.
TDMA. Why: Each of the users generate a load of 40KB/s = 0.32Mbps,
which can be fully transmitted given the share of 0.33Mbps available
per user when partitioning the channel with TDMA. Taking turns on the
other hand does not offer enough capacity for all the files to be
transmitted: 3*0.32 + 3*0.05 = 1.11s > 1s, and would incur extra
overhead.
X sends 80KBytes files every 1sec, while Y and Z send 10KBytes
files every 1sec.
Taking Turns Why: First, by using TDMA, X does not have enough
capacity to transmit, 80KB/s = 0.640Mbps > 0.33Mbps. Second, with
TDMA, Y and Z waste 3 out of 4 slots. On the other hand, when taking
turns, there is enough capacity to transmit all the data:
0.64+0.05+0.08+0.05+0.08+0.05=0.95s.
Problem 39. Reliable transport protocols
Sender S communicates with receiver R using a flow control protocol
with a window of 3 packets. This means that S can send at most 3
unacknowledged packets at a time. Each packet has a sequence number
starting from 1. R always acknowledges a packet by sending back to A
the sequence number of that packet (i.e., when R receives a packet
with sequence number 2 it sends an acknowledgement (ack) containing 2
to S.) Ignore packet transmission times, and assume that neither the
packets nor the ack are reordered in the network.
Let RTT denote the round-trip time between S and R. S uses two
mechanisms to retransmit a packet:
"timeout": S retransmits a packet if it has not received an ack
for it within T seconds after sending the packet, where T > RTT.
"out-of-order ack": S retransmits an unacknowledged packet p
when it receives an ack with a sequence number higher than p. For
example, if packet 3 hasn't been acknowledged, and S receives ack 4,
then S assumes that R hasn't received packet 3 and retransmits it
immediately.
Assume S wants to transfer a file that spawns exactly 8 packets to
R as fast as possible. During the transfer at most one packet (or ack)
is lost. For all questions below express your answer in terms of T and
RTT.
What is the minimum time it could take to transfer the file?
The file transfer time is the time between the moment S sends the
first packet and the moment it receives the last ack.
3*RTT: No packet or ack is lost.
What is the maximum possible file transfer time assuming S uses
only the "timeout" retransmission mechanism? Please give a scenario
which achieves the maximum transfer time. This scenario should
indicate which packet (or ack) is dropped, if any.
3*RTT + T: A packet in the last window is lost.
Repeat question (b) but now assume that S uses both the
"timeout" and "out-of-order ack" retransmission mechanisms.
Same as (b), if the last packet is lost.
Problem 40. Reliable data delivery
Consider two nodes, A and B. Suppose the network path from A to B
has a bandwidth of 5 KB/s (5,000 bytes per second) and a propagation
time of 120 msec. The path in the reverse direction, from B to A, has
a bandwidth of 10 KB/s and a propagation time of 80 msec. Let data
packets have a size (including all headers) of 500 bytes and
acknowledgment packets a size of 100 bytes.
Give a numeric expression for the throughput A can achieve in
transmitting to B using Stop-and-Wait. You can treat a 500-byte data
packet as transferring 500 bytes of useful data (that is, ignore that
it’s a bit less due to the headers).
The transmission time of a data packet from A to B is (500 B)/(5 KB/s)
= 100msec.
The transmission time of an acknowledgment from B to A is (100
B)/(10 KB/s) = 10 msec.
The total propagation time is 80+120 = 200 msec. Thus an RTT for
sending a data packet and receiving an acknowledgment for it is
200+100+10 = 310 msec.
With Stop-and-Wait, A sends one data packet per RTT, so the
throughput it can achieve is (500 B)/(310 msec) = 500/0.310 B/s =
1613 B/s.
Give a numeric expression for the size of the window, in terms
of number of data packets, that A must use in order to transfer its
data as fast as possible, if A instead uses Sliding Window.
To go as fast as possible, A must use a window that is at least as
large as the bandwidth-delay product, which is (5 KB/s)(310 msec) =
1,550 bytes.
The question asks for how many data packets, which is given by:
Ceiling[ 1550 B / (500 B/pkt) ] = 4 pkts
What is the maximum rate A can achieve?
When using a window greater or equal to the bandwidth-delay product, a
sender can achieve a rate -- i.e., how fast it can transmit over
time -- equal to the bandwidth of the path. Therefore, the window of 4
pkts suffices for A to achieve a rate of 5 KB/s.
If the bandwidth of the path from B to A drops to 100
bytes/sec, can A still achieve this rate? If so, roughly how much
smaller or bigger is the new window size? If not, what is the new
limit on the rate A can achieve?
When the bandwidth in the reverse direction drops so drastically, not
only does the transmission time of the acknowledgments go way up (to
1000 msec), but even more critically, the window can only advance once
per 1000 msec, since that's the minimum spacing between two
acknowledgments. Therefore A can only send one data packet per second,
and has its maximum rate reduced to 500 B / 1000 msec = 500 B/s.
Problem 41. Reliable data delivery
Consider a sliding window protocol between hosts A and B. Suppose
the link propagation delay is 1 time unit, the retransmission timeout
is 3 time units, and the window size is 3. Assume the link drops
every third packet, i.e., the link drops the 1st, 4th, 7th, ... data
packets. (Note that here "kth" packet means the kth packet
transmitted on the link, and NOT the sequence number of the packet.)
How long does it take to successfully transmit 6 packets between A and
B? Ignore the transmission times and the queuing delay, and assume
that no acknowledgments are lost.
time
A
B
1
send #1 [lost]
2
send #2
3
send #3
ACK #2
4
resend #1 [lost]
ACK #3
5
send #4
6
send #5
ACK #4
7
resend #1 [lost]
ACK #5
8
send #6
9
ACK #6
10
resend #1
11
ACK #1
Problem 42. MAC protocols -- token passing
Token-passing is an alternative to contention-based channel access
protocols like ALOHA. Here, the N nodes in the broadcast network are
numbered 0, 1, ..., N-1. The token starts at node 0. A node can send
a frame if, and only if, it has the token. When node i with the token
has a frame to send, it sends the frame and then passes the token to
node (i + 1) mod N. If node i with the token does not have a frame to
send, it passes the token to node (i+1) mod N. To pass the token, a
node broadcasts a token frame on the radio channel. A data frame
occupies the channel for time Tf and a token frame occupies the
channel for time Tk.
If s of the N nodes in the network have data to send when they
get the token, what is the utilization of the channel?
The easiest way to solve this problem is to observe that the system
may be viewed as operating in "rounds", where in one round each node
gets one chance to send data. The total time of a round is:
N*Tk + s*Tf
because each node must broadcast the token and in addition s nodes
send data frames. Now, in this round, the amount of useful (payload)
time spent by the system is s*Tf . Therefore, the utilization is
[s*Tf] / [s*Tf + N*Tk]
There's a slightly longer way to solve this problem too, starting
from the basic definition of utilization. The channel utilization is
the rate at which data frames are sent divided by the channel rate
(i.e., data load / rate). The channel rate is 1 frame every Tf
seconds. The rate at which data frames are sent is s frames every
"round", or s frames every s*Tf + N*Tk seconds. The answer follows.
Both approaches are actually the same; a useful trick for quick
calculations of utilization is to just take the ratio of the time
spent on the channel doing actual work (sending useful data).
In theory, token passing seems like a good way of avoiding
packet collisions. However, in practice, there are a few significant
complicating issues that such a scheme must handle in wireless
broadcast networks. State one of them.
There are many problems that need to be solved. The loss of a token
packet could bring the system to a halt unless we have a plan for
coping with it and restarting operation. Also, a node that has the
token might crash or be powered off. And last but not least, we need a
way to handle nodes joining and leaving the network dynamically, so we
need a way to assign identifiers to nodes to produce a round-robin
order. Of these, the most important reason is the first: coping with
token loss.
Problem 43. MAC protocols: Aloha
Note: this problem is useful to review how to set up and solve problems
related to Aloha-like access protocols, but the calculations shown in the
answer are more complex than we would ask on a quiz.
Consider a network with four nodes, where each node has a dedicated
channel to each other node. The probability that any node transmits is
p. Each node can only send OR receive one packet at a time. What is
the utilization of the network? Assume each packet takes 1 time
slot. Assume each node has 3 queues -- one for each other node -- and
that each is backlogged.
Utilization is the expected number of packets that get through in each
slot divided by the maximum (2, i.e. when A always transmits to B and
C always transmits to D).
P[4 nodes transmit] = p4
P[3 nodes transmit] = 4p3(1-p)
P[2 nodes transmit] = 6p2(1-p)2
P[1 node transmits] = 4p(1-p)3
p[0 nodes transmit] = (1-p)4Expected packets through if 4 nodes transmit = 0
No one is free to receive a packet.
Expected packets through if 3 nodes transmit = 1*(3/27) = 1/9
Without loss of generality, assume that A,B and C transmit. There are
27 combinations of destinations that they can transmit to (each can
choose one of 3). Of these, only 3 result in the successful
transmission of one packet (e.g. A->D,B->C,C->B) or
(B->D,A<->C) or (C->D,A<->B)
Expected packets through if 2 nodes transmit = 2*(2/9) = 4/9
Similar to above, assume that A and B transmit. There are 9
combinations of destinations. Of these, only 2 result in the
successful transmission of 2 packets (A->D,B->C) or (A->C,B->D).
Expected packets through if 1 node transmits = 1
No matter who the node transmits to, it will get through.
Expected packets through if 0 nodes transmit = 0
No packets sent.
Suppose that there are three nodes seeking access to a shared
medium using slotted Aloha, where each packet takes one slot to
transmit. Assume that the nodes are always backlogged, and that each
has probability p_i of sending a packet in each slot, where i = 1, 2
and 3 indexes the node. Suppose that we assign more the sending
probabilities so that
What are the probabilities that maximize the utilization and
the corresponding utilization?
Differentiating U and sett the result equal to zero we obtain
dU/dp = 4 - 20p + 18p2 = 0
has two roots at p=0.2616 and 0.8495. However, only the root at 0.2616 is
feasible since the other leads to a value of p_1 that is greater than 1. Thus,
p_1 = 0.5232, p_2 = 0.2616 and p_3 = 0.2616.
The corresponding utilization is 0.4695.
Problem 45. MAC protocols: Aloha
Suppose that two nodes are seeking access to a shared medium using
slotted Aloha with binary exponential backoff subject to maximum and
minimum limits of the probability pmax = 0.8 and pmin = 0.1. Suppose
that both nodes are backlogged, and at slot n, the probabilities the
two nodes transmit packets are p_1 = 0.5 and p_2 = 0.3.
What are the possible values of p_1 at slot n+1? What
are the probabilities assocated with each possible value?
p_1 increases to 0.8 if node 1 transmits a packet and node 2 does not
transmit a packet. Probability of this event:
(p_1)(1 - p_2) = 0.5*0.7 = 0.35
p_1 decreases to 0.25 if node 1 transmits a packeet and node 2 also
transmits a packet. Probability of this event:
(p_1)(p_2) = 0.15
Otherwise p_1 stays the same with probability 1 - 0.35 - 0.15 = 0.5.
What are the possible values of p_2 at slot n+1? What are
the probabilities associated with each possible value?
p_2 increases to 0.6 if node 2 transmits a packet and node 1 does not
transmit a packet. Probability of this event:
(p_2)(1 - p_1) = 0.3*0.5 = 0.15
p_2 decreases to 0.15 if node 2 transmits a packeet and node 1 also
transmits a packet. Probability of this event:
(p_1)(p_2) = 0.15
Otherwise p_2 stays the same with probability 1 - 0.15 - 0.15 = 0.7.
