ecen5273

#show link: underline
== Problem Set 1 #h(1fr) Jack Sangdahl

=== Problem 1
What advantage does a circuit-switched network have over a packet-switched
network?

A circuit-switched network can guarantee a certain amount of end-to-end
bandwidth for the duration of data transmission. Most packet-switched networks
(ie. the internet) cannot make any end-to-end guarantees with regard to
bandwidth.

=== Problem 2
What advantage does TDM have over FDM in a circuit-switched network?

FDM requires sophisticated analogue hardware to shift signal into appropriate
frequency bands. TDM is simple to implement, but it requires clock
synchronisation nodes.

=== Problem 3
We consider sending real-time voice from host A to host B over a packet-switched
network. Host A converts analogue voice to a digital 65 Kbps bit stream and
sends these bits into 56-byte packets. There is one link between hosts A and B
and the transmission rate is 1 Mbps and its propagation delay is 20 ms. As soon
as host A gathers a packet, it sends it to host B. As soon as Host B receives an
entire packet, it converts the packet's bits into an analogue signal. How much
time elapses from the time a bit is created until the bit is decoded?

Consider first bit in a packet. Before this bit can be transmitted, all of the
bits in the packet must be generated. This requires:

$ (56 times 8)/(65 times 10^3) = 0.006892 "sec" $

The time required to transmit the packet is:

$ (56 times 8)/(1 times 10^6) = 0.000448 "sec" $

The propagation delay is 0.02 seconds, meaning the delay until decoding is:

$ 0.006892 + 0.000448 + 0.02 = 0.02734 " sec" $
A similar analysis shows that all bits experience a delay of 27.34 ms delay.
Note, the answer could include decoding time at host B too.

=== Problem 4
Consider a Go-Back-N sliding window algorithm (1 packet is 250 bytes long)
running over a 100 Km point-to-point fibre link with bandwidth of 100 Mbps.

+ Compute the one-way propagation delay for this link, assuming that the speed of
  light is $2 times 10^8$ m/s in the fibre.

$ (100 "km")/(2 times 10^8 "ms") = 0.0005 "sec" $

+ Suggest a suitable timeout value for the algorithm to use. List factors you need
  to consider.

$ 2((250 times 8)/(8 times 10^8) + 0.5) = 2(0.02 + 0.5) = 1.04 "ms" $

+ Suggest N to achieve 100% utilisation in this link.

$ (1 times 10^8)(0.0005) = 50000 "bits" = 50000/(8 times 250) = 25 "packets" $

=== Problem 5
Suppose a 1 Gbps point-to-point link is being set up between the Earth and a new
lunar colony. The distance from the moon to the Earth is approximately 385,000
Km, and data travels over the link at the speed of light #sym.dash.em $3 times 10^8$ m/s.

+ Calculate the minimum RTT for the link.

Assuming that the packet transmission time is negligible, the minimum RTT can be
found by 2 times the distance from moon to Earth, divided by speed of light:

$ (2 times 385000000)/(3 times 10^8 "ms") = 2.57 "sec" $

+ Using the RTT as the delay, calculate the bandwidth delay product for the link.

Bandwidth delay product given by:

$ (1 "Gbps")(2.57 "sec") = 2.57 times 10^9 "bits" $

+ What is the significance of the bandwidth delay product computed above?

BDP represents the amount of data the sender can send before it's possible to
receive a response. In this context, bandwidth delay product refers to the
product of a data link's capacity and its round-trip delay time. The result, an
amount of data, is equivalent to the maximum amount of data on the network
circuit at any given time, ie. the data that has been transmitted, but not yet
acknowledged.

=== Problem 6
Host A wants to send a 1,000 KB file to host B. The RTT of the duplex link
between host A and host B is 160 ms. Packet size is 1 KB. A handshake between A
and B is needed before data packets can start transferring which takes $2 times "RTT"$.
Calculate the total required time of file transfer in the following cases. The
transfer is considered complete when the acknowledgement for the final packet
reaches A.

+ The bandwidth of the link is 4 Mbps. Data packets can be continuously
  transferred on the link.

Total time given by the sum of initial handshake, transmit time for 1000
packets, RTT, and terminating handshake:

$ (5 times 160) + (2(1000) times 8)/(2(1000) times 4) = 2.8 "sec" $

+ Assume that we have "unlimited" bandwidth on the link, meaning that we assume
  transmit time to be zero. After sending 50 packets, A needs to wait one RTT
  before sending next group of 50 packets.

Total time given by the sum of initial handshake, transmit time and RTT for 50
packets, multiplied by 20, and terminating handshake:

$ 320 + 160 times 20 + 320 = 3.84 "sec" $

+ The bandwidth of the link is 4 Mbps. During the first transmission, A can send
  one ($2^(1 - 1)$) packets, during the 2nd transmission A can send $2^(2 - 1)$ packets,
  during the 3rd transmission A can send $2^(3 - 1)$ packets, and so on. Assume A
  still needs to wait for 1 RTT between each transmission.

Between each transmission, one RTT is required, so we need 10. Total time given
by the sum of initial handshake, transmission time for 1000 packets, 10 RTT, and
terminating handshake:

$ 14 times 160 + 2 = 4.24 "sec" $

=== Problem 7
Determine the width of a bit on a 10 Gbps link. Assume a copper wire, where the
speed of propagation is $2.3 times 10^8$ m/s.

Width of a bit on a 10 Gbps link is given by speed divided by bandwidth:

$ (2.3 times 10^8)/(10 times 10^9) = 0.023 arrow.r 2.3 "cm/bit" $

Thus, a single bit has a width of 2.3 cm on the wire.

=== Problem 8
Suppose two hosts, A and B, are separated by 20,000 Km and they are connected by
a direct link of 1 Gbps. Suppose the propagation speed over the link is $2.5 times 10^8$ m/s.

+ Calculate the BDP of the link.

$ 1 times 10^9 ((20000 times 10^3)/(2.5 times 10^8)) = 80000000 "bits" $

+ Consider sending a file of 800,000 bits from host A to host B as one large
  message. What is the maximum number of bits that will be in the link at any
  given time?

The maximum number of bits in the link is given by the smallest value of the
file size or the BDP, so in this case, it's the file size of 800,000 bits.

+ What is the width (in metres) of a bit in the link?

$ (2.5 times 10^8)/(10 times 10^9) = 0.25 "metres" $

+ Suppose now the file is broken up into 20 packets with each packet containing
  40,000 bits. Suppose that each packet is acknowledged by the receiver and the
  transmission time of an acknowledgement packet is negligible. Finally, assume
  that the sender cannot send a packet until the preceding one is acknowledged.
  How long does it take to send the file?

First calculate the propagation delay:

$ (20000 times 10^3)(2.5 times 10^8) = 0.08 "sec" $

Next calculate transmission time per packet:

$ 40000/(1 times 10^9) = 0.00004 "sec" $

Total time given by number of packets times transmission time per packet, plus
propagation delay:

$ 20(0.00004 + 2(0.08)) = 3.2 "sec" $

=== Problem 9
Suppose there is a 10 Mbps microwave link between a geostationary satellite and
its base station on Earth. Every minute the satellite takes a digital photo and
sends it to the base station. Assume a propagation speed of $2.4 times 10^8$ m/s.
The geostationary satellite is 36,000 Km away from Earth's surface.

+ What is the propagation delay of the link?

$ 36000/(2.4 times 10^8) = 150 "ms" $

+ What is the BDP, R times propagation delay?

$ 150(10 times 10^6) = 1500000 arrow.r 1.5 "MBit" $

+ Let $x$ denote the size of the photo. What is the minimum value of $x$ for the
  microwave link to be continuously transmitting?

Data is transferred at 10 Mbps, so 600 Mbits over period of 60 seconds. So $600/8 = 75$ Mbyte.

=== Problem 10
Explain collision domain and broadcast domain with respect to a hub, switch, and
a router

- *Collision Domain*: the part of network where packet collisions can occur
- *Broadcast Domain*: the part of network where a broadcast packet is forwarded,
  meaning it dictates how far a broadcast packet can tranverse
- *Hub*: combines collision domains. Each port in a hub has same collision domain,
  meaning only one device can transmit a packet at a time
- *Switch*: separates collision domain, alleviating the issue mentioned above, and
  combines broadcast domain
- *Router*: separates broadcast domain

=== Problem 11
Consider the following networked computers connected by bridge X and Y. Bridge X
has interface 1, 2, and 3. Bridge Y has interface 1 and 2. Assume at the
beginning the address tables of bridge X and Y are all empty. Write down the
address tables of bridge X and Y after the following communication finished
(Assume that the receiver does not respond to the packet sent by the sender).

#align(center)[
  #image("img/fig1.png", width: 70%)
  Figure 1
]

+ A send packet to C
+ B send packet to D
+ C send packet to E
+ E send packet to A
+ D send packet to A

#align(
  center,
)[
  Bridge X
  #table(
    columns: 2, table.header[*Address*][*Interface*], [A], [1], [B], [1], [C], [2], [D], [3], [E], [3],
  )
  Bridge Y
  #table(
    columns: 2, table.header[*Address*][*Interface*], [A], [1], [B], [1], [C], [1], [D], [2], [E], [1],
  )
]

=== Problem 12
Given the extended LAN shown in Figure 2, indicate which ports are not selected
by the spanning tree algorithm. Note that the bridge with the smallest ID
becomes a root.

#align(center)[
  #image("img/fig2.png", width: 70%)
  Figure 2
]

Both ports beloning to B2, the port belonging to B5 spanning to F, and port
belonging to B6 spanning to I, all are not selected by the spanning tree
algorithm.

=== Problem 13
Still considering Figure 2 above, if bridge B1 suffers catastrophic failure,
indicate which ports are not selected by the spanning tree algorithm.

If B1 fails, only the port belonging to B6 spanning to I is not selected.

=== Problem 14
Consider the GBN protocol with a sender window size of 4 and a sequence number
range of 1,024. Suppose that at time $t$, the next in-order packet that the
receiver is expecting has a sequence number of $k$. Assume that the medium does
not reorder messages. Answer the following questions:

+ What are the possible sets of sequence numbers inside the sender's window at
  time $t$? Justify your answer.

Suppose receiver has received packet $k - 1$, as well as all other preceding
packets, and has confirmed via an ACK. If all of these ACKs have been
acknowledged by the sender, then the sender's window is $[k, k + N - 1]$. Next,
suppose none of the ACKs have been received by the sender. In this case, the
sender's window contains $k - 1$, and the $N$ packets leading up to and
including $k - N$. Now, the sender's window is $[k - N, k - 1]$, meaning the
sender's window is of size $N = 3$ and begins somewhere in range $[k - N, k]$.

+ What are all the possible values of the ACK filed in all possible messages
  currently propagating back to the sender at time $t$? Justify your answer.

If the receiver is waiting for packet $k$, it has acknowledged it has received
packet $k - 1$, as well as $N - 1$ packets before that. If none of these ACKs
have been received by the sender, thn ACK messages with values of $[k - N, k - 1]$ may
still be propagating back. Since the sender has already sent $[k - N, k - 1]$,
the sender must have already received an ACK for $k - N - 1$. Once the receiver
has acknowledged for $k - N -1$, it will never send an ACK that is less than $k - N - 1$.

+ With the Go-Back-N protocol, is it possible for the seto receive an ACK for a
  packet that falls outside of its current window? Justify your answer with an
  example.

Yes, this scenario is possible. Suppose the sender has a window size of 3 and
sets packets 0, 1, and 2 at time T0. At time T1, the receiver acknowledges
packets 0, 1, and 2. At T2, the sender times out and retries sending packets 0,
1, and 2. At T3, the receiver acknowledges the duplicate packets 0, 1, and 2. At
T4, the sender receives the ACKs that the receiver sent at T1. The sender's
window is now packets 3, 4, and 5. At T5, the sender receives the ACKs that the
receiver sent at T2.