# Homework Week 3:
## Problem 1:
Now we discuss some definitions:
The CSMA method does not tell us what to do in case there is a collision. Carrier sense multiple access with collision detection(CSMA/CD) adds to the CSMA algorithm to deal with the collision. In CSMA/CD, the size of a frame must be large enough so that collision can be detected by the sender while sending the frame. So, the frame transmission delay must be at least *two times* the maximum propagation delay. Assume some station transmitted data packet and successfully get to the destination but it is just the BEST CASE, so we have to take the WORST CASE scenario in which there will be contention slots.
Contention slots are those slots that are not able to transmit their journey due to the collision. Suppose station A transmitted data but collide and the worst-case time wasted is 2Tp and then some station B found out a way to transmit the data so it took : Tp(propagation delay) + Tt(transmission time)
Now we don't know how many contention slots, we consider the worst case to be of n contention slots.
As in slide 22, we have the throughput equation below:
T = $T_t\over{T_t+T_p+C*2T_p}$
$T_t$ transmission time
$T_p$ propagation time
C the average contention interval\

In CSMA/CD, for success, only 1 station should transmit while other shouldn't. Let p be the probability to transmit data succesfully.
P is probability of contention resolved:

**P=Np$(1-p)^{N-1}$** ( by using Binomial distribution)

The mean value of contention interval is expressed as expectation value of slot length:
E = $\sum_{i=1}^{\propto} i.P(success)$
(i slots with a collisions or no transmission followed by a slot transmission)
= $\sum_{i=1}^{\propto}i.(1-P)^i.P$
= ${1-P}\over P$ = **C**
## Problem 2:
Now we have the throughput equation:
T = $T_t\over{T_t+T_p+C*2T_p}$
= $T_t\over{T_t+T_p+(1-P/P)*2T_p}$
= $1\over1+a+2a.(1-P/P)$ **(1)**
By taking derivative of Psuccess we find max occurs at p = 1/N
Followed by slide 21 we have P~success~max=$(1-{1\over N})^{N-1}$
=>lim P -> $1\over e$
T -> $1\over{1+5a}$
with a = $T_p / T_t$

**Plot and discuss following figures**
### a) Throughput T vs a (values from 0.01 to 100) for different p =0.05, 0.1 and 0.2 when N =10.

clc,clearvars,close all 

a = linspace(0.01,100)
N = 10

p1 = 0.05
P1 = N*p1*(1-p1)^(N-1)
T1 = 1 ./(1 + a + ( 1-P1) ./ P1 )


p2 = 0.1
P2 = N*p2*(1-p2)^(N-1)
T2 = 1 ./(1 + a + ( 1-P2) ./ P2 )

p3 = 0.2
P3 = N*p3*(1-p3)^(N-1)
T3 = 1 ./(1 + a + ( 1-P3) ./ P3 )
  
plot(T1,a)
hold on
plot(T2,a)
hold on
plot(T3,a)
hold on

grid on 
xlabel('T')
ylabel('a')
title('Throughput T vs a')
legend('T1','T2','T3')

We have the figures here:
**Zoom in xlim**



### b) T vs a for different number of user N = 10, 20, 30 when p =0.1

clc,clearvars,close all 

a = linspace(0.01,100)
p = 0.1

N1 = 10
P1 = N1*p*(1-p)^(N1-1)
T1 = 1 ./(1 + a + ( 1-P1) ./ P1 )


N2 = 20
P2 = N2*p*(1-p)^(N2-1)
T2 = 1 ./(1 + a + ( 1-P2) ./ P2 )

N3 = 30
P3 = N3*p*(1-p)^(N3-1)
T3 = 1 ./(1 + a + ( 1-P3) ./ P3 )
  
plot(T1,a)
hold on
plot(T2,a)
hold on
plot(T3,a)
hold on

grid on 
xlabel('T')
ylabel('a')
title('Throughput T vs a')
legend('T1','T2','T3')


Now we discuss about that figures above:
* We see from this figures that as throughput does not depend on N and p. We can change the value of throughput by changing the value of a or the value of T~prop~ and T~trans~. We see this formula **(1)** that if T~prop~ approaches 0, the throughput approaches 1.
* If distance increases, T~prop~ increases, thus the efficiency of CSMA decreases.
* CSMA is not suitable for long-distance networks like WAN but works optimally for LAN.
* Transmission Time >= 2* Propagation Time
## Problem 3:
### Consider the delay of pure ALOHA at low load. Which one is less? Explain your answer.
#### Solution:
When the load is low, collisions will be less and there are more chances of a frame to be transmitted successfully. In case of pure ALOHA, each station will transmit a frame whenever it is ready
But in case of slotted ALOHA, if the load is low, a station has to wait for the start of next time slot to transmit its frame even if the frame is ready
Hence, delay in slotted ALOHA will be more than pure ALOHA.
## Problem 4:
### A large population of ALOHA users manages to generate 50 requests/sec, including both originals andretransmissions. Time is slotted in units of 40 msec.
a) What is the chance of success on the first attempt?
b) What is the probability of exactly k collisions and then a success?
c) What is the expected number of transmission attempts needed?
#### Solution:
Now we have Poisson distribution here :
P(k) = {e^-G} * G^k\over{k!} where G is the number of frames generated in one frame transmission time
Here we are now finding number of frames that are generated in 1 slot time which is given as 40 msec.
So, number of frames generated in 40 msec = ($50\over1000$)* 40 = 2
Thus the value of G we obtained = 2
Now we solve each part one by one with that value we obtained above.
a) P(success on the first attempt) = P(0)= $e^-G$ = $e^-2$=0.1353
b) P(succes after k collisions) = $(P(defeat))^k$ * P(success)=$(1-e^-G)^k$ * $e^-G$=$(1-e^-2)^k$ * $e^-2$
c) We have expected number of attempts that obtained by equation:
1.P(1) + 2.P(2) + 3.P(3) + .......
= $\sum_{k=1}^{\propto} k.P(k)$
where P(k) is the probability of success at $k^{th}$ attempt.
= $\sum_{k=1}^{\propto} k.e^-G.(1-e^-G)^{k-1}$
= 7.39 = 8
Because the number of attempts must be an integer.