Note:

ps: 10^-12 s

ns: 10^-9 s

$\mu$ s: 10^-6 s

ms: 10^-3 s

KB : 10^3 B

MB : 10^6 B

GB : 10^9 B

TB : 10^12 B

L6 - MediumAccessControl

(a)

The throughput of Station is simply the chance of that station sending data successfully.

To ensure the station is sending data successfully, We need to make sure other stations wont send.

throughput of Station A: $P_A \times (1-P_B) \times (1-P_C) = 0.2\times 0.7 \times 0.6 = 0.084$

throughput of Station B: $(1-P_A) \times P_B \times (1-P_C) = 0.8 \times 0.3 \times 0.6 = 0.144$

throughput of Station C: $(1-P_A) \times (1-P_B) \times P_C = 0.8 \times 0.7 \times 0.4 = 0.224$

(b)

Throughput of the system is simply add up all the throughput of stations.

throughput of the system = 0.084 + 0.144 + 0.224 = 0.452

Note this is a normalized throughput (frames/frametime)

If we want the throughput in bit per second, assume we know the data rate R, We simply multiply R with Normalized Throughput to get the throughput in bps.

Consider the CSMA scheme. Data takes a propagation time to transfer.

The worst case is when A is sending to B and almost reach B, B send another data to A.

Therefore the vulnerable time is $2 \times t_p$

To make sure there is no collision, the frame transmission time should be $\geq 2t_p$

Since $T_{fr} \geq 2t_p$

minimum frame size = $T_{fr}\times R = 2t_p \times R$

where R is data rate.

Given the minimum frame size 512 bits when data rate of 10Mbps, we can first find out the $2t_p$ .

512 = $2t_p \times 10M$

$2t_p = 51.2M^{-1}$

For Data rate 100Mbps:

Minimum frame size = 5120 bits

For Data rate 1 Gbps:

Minimum frame size = 51200 bits

For Data rate 10 Gbps:

Minimum frame size = 512000 bits

(a)

Distance between A and C = 2000m

Propagation speed = $2 \times 10^8$ m/s

Propagation time of AC $= t_{pAC} = t_3 - t_1 = \frac{2000}{2\times 10 ^8} = 10\mu s$

Given $t_1 = 0$

$t_3 = t_1 + 10\mu s = 10\mu s$

Therefore station C hears the collision at $10 \mu s$ .

(b)

Distance between A and C = 2000m

Propagation speed = $2 \times 10^8$ m/s

Propagation time of CA $= t_{pCA} = t_4 - t_2 = \frac{2000}{2\times 10 ^8} = 10\mu s$

Given $t_2 = 3\mu s$

$t_4 = t_2 + 10\mu s = 13\mu s$

Therefore station A hears the collision at $13 \mu s$ .

©

Since station A hears the collision at $13 \mu s$ .

$t_4 - t_1 = 13\mu s$

Given data rate 10Mbps

$T_{fr(A)} = 10Mbps \times 13\mu s = 130$ bits

(d)

Station C hears the collision at $10 \mu s$ .

$t_3 - t_2 = 7\mu s$

Given data rate 10Mbps

$T_{fr(C)} = 10Mbps \times 7\mu s = 70$ bits

For Each sending frame, Primary station need to Poll the secondary Station, recieve the data from secondary Station and send the ACK with recieved. (Right graph step 3,4,5)

If Primary station polls and secondary station have nothing to send, the Secondary station will send a NAK. (Right graph step 1,2)

Thus the bytes exchanged for Each frame:

Poll + frame + ACK = 32 + 1000 + 32 = 1064 bytes

Bytes exchanged when Sending 1 Frame to 4 Stations:

$4 \times 1064 = 4256$ bytes

Bytes exchanged when Sending 5 Frames to all 4 Stations:

$4256 \times 5 = 21280$ bytes

After sending out data frame, Primary station still Poll to ask if the secondary station have anything to send. Since the secondary stations have nothing to send, it returns NAK.

Bytes exchanged when there is no more data to send:
POLL + NAK = 32 + 32 = 64 bytes

For 4 stations, $64 \times 4 = 256$ bytes

Therefore Total bytes exchanged:

$21280 + 256 = 21536$ bytes

Alice sends $(6)_{16} = (0110)_2$

Bob sends $(B)_{16} = (1011)_2$

According to Data representation in CDMA:

Therefore

Alice’s code $c_A$ = [+1, +1]

Alice’s data $d_A$ = [-1 +1 +1 -1]

Bob’s code $c_B$ = [+1, -1]

Bob’s data $d_B$ = [+1 -1 +1 +1]

Total Signal = $d_A \times c_A + d_B \times c_B$

We treat $d$ as 4 scalars

$d_A \times c_A =$ [-1 -1 +1 +1 +1 +1 -1 -1]

$d_B \times c_B =$ [+1 -1 -1 +1 +1 -1 +1 -1]

Total Signal = [0 -2 0 +2 +2 0 0 -2]

To decode the signal:

Let’s say Alice want to know what Bob recieved. Alice use Bob’s code to decode the total signal.

$c_B =$ [+1 -1]

[[0 -2] [0 +2] [+2 0] [0 -2]] $\cdot c_B = 2 \times d_B$

[[0 -2] [0 +2] [+2 0] [0 -2]] $\cdot$ [+1, -1] = [2 -2 2 2]

$d_B$ = [1 -1 1 1] = 1011

Let’s say Bob want to know what Alice recieved. Bob use Alice’s code to decode the total signal.

$c_A$ = [+1 +1]

[[0 -2] [0 +2] [+2 0] [0 -2]] $\cdot c_A = 2 \times d_A$

[[0 -2] [0 +2] [+2 0] [0 -2]] $\cdot$ [+1 +1] = [-2 2 2 -2]

$d_A$ = [-1 1 1 -1] = 0110

L7 - Local Area Network (LAN) and VLan

Maximum payload length = 1500 bytes. Therefore obviously the data cannot be encapsulated in 1 frame. We need 2 frames to be sent.

Size of the data in First Frame: 1500

For size of the data in second frame, notice here the Minimum payload length is 46 bytes.

Therefore we need to add 36 bytes as padding in the second frame to fulfill the minimum requirement.

Size of the data in Second Frame: 46 (with Padding)

End-to-end propagation delay $\tau$ means it takes $\tau$ to travel to another end.

A is located at one end

B,C is located at the other end

(a)

Collision happens to all frame, all frames are corrupted therefore No ACK, the frames are discorded and reschedules when time out.

(b)

Since it takes $\tau$ to travel to another end, B thought the channel is idle at $t = \frac{1}{2}\tau$ and therefore collisions happen.

C sense the channel busy and therefore will wait random amount of time to resense the channel.

©

Since it takes $\tau$ to travel to another end, B thought the channel is idle at $t = \frac{1}{2}\tau$ and therefore collisions happen.

At $\tau$ time, signal A arrived B, and B knows collision happens. Then B aborts the transmission and reschedule.

At $1.5\tau$ time, signal B arrived A, and A knows collision happens. Then A aborts the transmission and reschedule.

C sense the channel idle and therefore transmits the signal.

In a Gigabit Ethernet network, the data rate is 1 Gbps.

10^9 bits per 1000ms.

If a noise of 2ms,

Destroyed bits = $10^9 \times \frac{2}{1000}$ = 2000000 bits

Given the average size of a frame is 1000 bytes (i.e. 8000 bits)

Destroyed frames = 2000000 / 8000 = 250 frames.

However, since the noise can start from the beginning or near the end of the first packet, 250 or 251 frames are possibly destroyed.

(a)

What fraction of slots is wasted due to multiple simultanneous transmission attempts mean its asking the probability of collision.

P(Collision) = P(2 or more user sending) = 1- P(no one sending) - P(only 1 user sending)

Therefore P(Collision) = $1 - 0.65^5 - (0.35\times0.65^4)\times 5 = 1-0.116-0.312 = 0.572$

(b)

P(Collision) = $1 - (1-p)^N - N(p(1-p)^{N-1})$

Let $P_i$ = P[fail on first (i-1) attempts, succeed on i th]

Let $PF_i$ = P(fail on attempt i)

Then the mean number of retransmission attempts before one station successfully retransmits is given by

$E[\text { retransmission }]=\sum_{i=1}^{\infty} i P_{i}$

For 2 stations: $\mathrm{PF}_{\mathrm{i}}=1 / 2^{\mathrm{K}} \text { where } \mathrm{K}=\min (n, 10)$

$PF_i = \frac{1}{2^i}$

$P_{i}=\left(1-P F_{i}\right) \times \prod_{j=1}^{i-1} P F_{j}$

$\begin{aligned} &\mathrm{PF}_{1}=0.5 \mathrm{P}_{1}=0.5\\ &\mathrm{PF}_{2}=0.25 \quad \mathrm{P}_{2}=0.375\\ &\mathrm{PF}_{3}=0.125 \quad \mathrm{P}_{3}=0.109\\ &\mathrm{PF}_{4}=0.0625 \quad \mathrm{P}_{4}=0.015\\ &\text { The remaining terms are negligible, } E[\text { retransmission }]=1.637 \end{aligned}$

(a)

When X sends to Z the packet is forwarded on all links

B1, B2, B3 learns where X is

Y’s network interface would see this packet because B2 broadcasted when it is looking for Z.

(b)

When Z sends to X, all switches already know X’s location. so each switch forwards the packet only on the link towards X, that is B3->B2->B1->X.

Meanwhile all switches learn the Z’s position.

Y’s network interface would not see this packet. B2 knows the X’s location already and will forward it to B1 instead of broadcasting.

©

When Y send to X, B2 and B1 learns where Y is.

Z’s network interface would not see this packet.

(d)

Before Z sends to Y, all the Switches already learnt where Z is.

W’s network interface would see this packet because B3 does not know where Y is, and broadcast to all links.

L8- Wireless LAN and Switching Networks

If CTS and RTS frames were as long as the standard DATA and ACK frames, there would be no advantage. The chance of collision of CTS/RTS frames are higher because the overhead would become larger.

Since CTS and RTS does not carry any data, they are supposed to be small and therefore to minimize the chance of collision.

The RTS/CTS exchange is only useful when the RTS/CTS frames are significantly smaller than the DATA frames.

A Link-layer switch has no MAC address because a Link-layer switch is just a relate device for forwarding the data. Link-layer switch is connected to the hosts via point-to-point dedicated connections. There is no need to have the MAC address of switch when the host want to communicate with switch. From user point of view, we don’t care the MAC address of switch because it is plug and play, the switch won’t become an end point in any communication link.

In Wireless network case, Users need to connect to access point in order to communicate with other users. Access point is served as a end point in this link. So From user point of view, we need to know MAC address of Access Point. Access Point is connected to the hosts via a multicast network (i.e. air), the MAC address is needed to let Access Point communicate more efficiently. When a host sends a frame to the Access Point, all other hosts drop the received copy of the frame at the MAC sublayer when they find that the frame does not belong to them.

802.11 Frame format

Header = 34 bytes

(a)

Data frame size = payload + header = 1200 + 34 = 1234 bytes

(b)

If we fragment the frame into 3 fragments each 400 payload:

The size of each fragment = 400 + 34 = 434 bytes

©

Total bytes sent = 434 x 3 = 1302 bytes

(d)

Extra bytes: 1302 - 1234 = 68 bytes.

802.11 Wireless Frame

First, A send data to the AP1

Communication from station A to the AP1 occurs in a wireless environment (802.11).

To DS= 1, From DS = 0

Therefore the frame would be:

| Address1: AP1 | Address2: A | Address3: C | N/A |

Then AP1 is communicating to AP2. (Through a standard Ethernet Frame, not 802.11 wireless frame)

Communication from the AP1 to the AP2 occurs in a wired environment (802.3)

Therefore the frame would be:

| Destination address : C | Source address : A |

Next, AP2 send data to C

Communication from the AP2 to station C occurs in a wireless environment (802.11).

To DS=0 , From DS = 1

Therefore the frame would be:

| Address1: C | Address2: AP2 | Address3: A | N/A |

(a)

“each ISP has connnfigured its AP to operate over channel 11” means the 2 APs are using the same Wifi standard (same frequency channel).

The two APs will typically have different SSIDs and MAC addresses. A wireless device will recieve the beacon frames from the APs, then associate with one of the SSIDs (i.e. one of the APs). After association, there is a virtual link between the device and the AP. Suppose the new device associates with AP1. When the device sends a frame, it will be addressed to AP1. Although AP2 will also receive the frame, it will not process the frame because the frame is not addressed to it. Thus, the two ISPs can work in parallel over the same channel. However, the two ISPs will be sharing the same wireless bandwidth. If wireless stations in different ISPs transmit at the same time, there will be a collision.

(b)

Now if two wireless stations in different ISPs (and hence different channels) transmit at the same time, there will not be a collision.

We need to send a DIFS before sending RTS

We need to send a SIFS before sending CTS, Frame, ACK

$T_{total}$ = DIFS + RTS + SIFS + CTS + SIFS + Frame + SIFS + ACK

= DIFS + 3 x SIFS + $t_{RTS} + t_{CTS} + t_{data} + t_{ACK}$

Don’t forget 802.11 frame has 34 bits header.

Tranmission time of data $t_{data} = \frac{(1000+34) \times 8 bits}{12Mbps} = 689.3\mu s$

Normally, the time for SIFS and DIFS will be given. And for CTS and RTS, if the size of the frame is given, simply calculate the transmission time for RTS and CTS based on the data rate. But in this example, the values are not given.

Throughput(bps) = $\frac{1000\times 8}{T_{total}}$

Hops means the link (Edges). If there is N hops, there is N-1 routers (nodes) .

Call setup time: Switching need time to setup.

(a)

Compute the end-to-end delay for

Circuit switching,

Virtual Circuit Packet Switching ,

and Datagram Packet Switching

Circuit switching

Time of Circuit switching = Call Setup Time + Message Delivery Time

$T_{circuit} = S + T_{message}$

$T_{message} = t_{fr} + t_p$

$t_{fr} = \frac{\text{message length in bits}}{\text{data rate (in bps)}} = \frac{L}{B}$

$t_p = \text{number of hops} \times \text{propagation delay per hop} = N \times D$

Therefore:

$T_{circuit} = S + \frac{L}{B} + N\times D$

= $0.2 + \frac{3200}{9600} + 4 \times 0.001 = 0.537$ sec

Datagram Packet Switching

Note Datagram Packet Switching has no call setup phase.

Data bits per packet = $\text{packet size} - \text{overhead}= P - H$

Packets needed: $\frac{\text{message length in bits}}{\text{data bits per packet}} = \frac{L}{P-H} = \frac{3200}{1008} = 3.17$ packets (4 packets needed)

$T_{Datagram}$ = Time to Transmit and Deliver all packets through first hop + Time to Deliver last packet across remaining hops (2nd, 3rd, and 4th) (known as Store and Forward delay)

$T_{Datagram} = 4 \times (t_{fr})+ t_p + 3(t_{fr} + t_p)$

$t_{fr} = \frac{\text{packet size}}{\text{data rate}}= \frac{P}{B}$

$t_p = \text{propagation delay per hop} = D$

Therefore:

$T_{Datagram} = 4 \times (\frac{P}{B})+ D + 3(\frac{P}{B} + D)$

$= 4 \times \frac{1024}{9600} + 0.001 + 3(\frac{1024}{9600} + 0.001) = 0.752$ sec

Virtual Circuit Packet Switching

Time of Virtual Circuit Packet Switching = Call Setup Time + Datagram Packet Switching Time

$T_{vc} = S + T_{Datagram}$

Therefore:

$T_{VC} = 0.2 + 0.752 = 0.952$ sec

(b)

Circuit Switching vs. Diagram Packet Switching

$\text{Number of Packets} = N_p = \lceil \frac{L}{P-H} \rceil$

$T_{Datagram} = N_p(\frac{P}{B}) + (N-1)(\frac{P}{B}) + N \times D$

Circuit Switching vs. Virtual Circuit Packet Switching

Datagram vs. Virtual Circuit Packet Switching

$\mathrm{T}_{\mathrm{d}}=\mathrm{TV}-\mathrm{S}$