Description
1. Delay-Bandwidth Product for Links in Series
Consider three nodes in series. Node A is connected to node B via a 150 Mbps fiber optic link, 2500 km in length.
Node B is connected to node C via a 1 Mbps link, 2 km in length. The links are full duplex. The rate of transmission
errors on the links, the time to switch a packet at node B, and the time to transmit an ACK are all negligible. A large
file is to be sent from node A to node C, and there is no other traffic on the links. Packets are 1.5 KB, including
headers.
a. Ignoring reliability and packet headers, what is the maximum throughput that can be achieved (in
Mbps)? Explain.
b. What is the round trip time from A to C?
c. What is the roundtrip bandwidth delay product for the path from A to C? (Specify the units you use).
d. Suppose an end-to-end sliding window protocol is used with SWS=RWS. What size of SWS is
optimal?
e. Why wouldn’t you want SWS to be many times larger than the value you suggested in part d?
2. Media Access Control
Suppose two nodes, A and B, are attached to opposite ends of a 450 m cable, and that they each have one frame of
500 bits (including all headers and preambles) to send to each other. Both nodes attempt to transmit at time t = 0.
Suppose there are four repeaters between A and B, each inserting a 10-bit delay. Assume the transmission rate is 10
Mbps, and CSMA/CD with backoff intervals of multiples of 512 bits is used. After the first collision, A draws K = 0
and B draws K = 1 in the exponential backoff protocol. Ignore the jam signal.
a. What is the one-way propagation delay (including repeater delays) between A and B in seconds?
Assume that the signal propagation speed is 2 × 10 8
m/sec.
b. At what time (in seconds) is A’s packet completely delivered at B?
c. Now suppose that only A has a packet to send and that the repeaters are replaced with bridges.
Suppose that each bridge has a 10-bit processing delay in addition to a store-and-forward delay. At
what time, in seconds, is A’s packet delivered at B?
3. Ethernet Timing
This problem is about the Ethernet/IEEE 802.11 access protocol. To be definite, suppose that if a host detects a
transmission while it is transmitting a frame, then: (i) if the host has already transmitted the 64 bit preamble, the host
stops transmitting the frame and sends a 32 bit jamming sequence; (ii) Else the host finishes transmitting the 64 bit
preamble and then sends a 32 bit jamming sequence. For simplicity, assume a collision is detected as soon as an
interfering signal first begins to reach a host. Suppose the packets are 512 bits long, which is the minimum length
allowed. Hosts A and B are the only active hosts on a 10 Mbps Ethernet and the propagation time between them is
20 µS, or 200 bit durations. Suppose A begins transmitting a frame at time t = 0, and just before the beginning of the
frame reaches B, B begins sending a frame, and then almost immediately B detects a collision.
a. Does A finish transmitting the frame before it detects that there was a collision? Explain.
b. What time does A finish sending a jamming signal? What time does B finish sending a jamming
signal?
c. What time does A first hear an idle channel again? What time does B first hear an idle channel again?
d. Suppose each host next decides to retransmit immediately after hearing the channel idle. After the
resulting (second) collision: When does A next hear the channel idle? When does B next hear the
channel idle?
e. Suppose after the second collision, A decides to wait 512 bit durations to retransmit (if it hears silence
after that long) and B decides to retransmit immediately after hearing a silent channel. Is the
transmission of host B successful?
f. At the time A was planning to send its second retransmission, it senses a carrier present. Suppose at
that particular time A decides to wait 3 x 51.2µs more until its next retransmission. What time does
host A finish sending its packet?
4. Server Bandwidth
Consider a server with direct memory access (DMA) in and out of main memory. Assume the server’s I/O bus speed
is 800Mbps and the memory bandwidth is 920Mbps.
a. How many switched 1.5Mbps links could be supported by the server?
b. Suppose the server switching time is such that it can forward packets at the rate of 1500 packets per
second. Determine the throughput as a function of the packet size.
c. At what packet size does the memory bandwidth become the limiting factor?
5. Switch Fabrics
Banyan and Batcher networks are two types of self-routing fabrics often used to construct large switches from
simpler components. A single stage of a n ´ n Banyan network consists of n/2 switches of dimension 2 ´ 2. An n ´ n
Batcher network can be made from two Batcher networks of size n/2 ´ n/2 plus a merge network with n/2 log2n
switches.
a. For n = 64, how many stages are required to route packets from the inputs to the outputs of a Banyan
Network?
b. How many 2 ´ 2 switches are required for the network in part a)?
c. Write down a recurrence relation T(n) for the number of switches in a Batcher network of size n ´ n.
d. Give the number of switches required for n = 32.
6. Spanning Tree Algorithm for Intelligent Bridges
Suppose the Perlman spanning tree algorithm and the bridge learning algorithm for forwarding are used for the
network shown below.
a. Indicate which bridge is root, which ports are root ports (i.e. the preferred port for reaching the root
bridge), which bridge is the designated bridge for each LAN, and which ports are designated ports (i.e.
the ports that connect some LAN to its given designated bridge). Hint: bridges that are not designated
bridges for any LAN, and ports that are not either root ports or designated ports do not play a role in
the routing of packets. The remaining bridges together with the LANs form a spanning tree.
b. Suppose after the configuration is complete, host Mars attaches to LAN B and host Venus attaches to
LAN E. Suppose Mars sends a message to Venus, then Venus sends a message to Mars, then Mars
sends a second message to Venus. For each of the three messages, indicate which LANs the message
is heard on.
B2
B4
B1
B6
B7
B8
B9
B5
B3
A
B
C
D
E
F
G
Mars
Venus
