Computer Network - Data Link Layer

Maximum data rate

For noiseless channel
If V be the number of discrete level and H be the bandwidth in Hz
maximum data rate = 2H log V
2H samples per second are required to completely reconstruct signals passed through loss pas filter of bandwidth H


For noisy channel
maximum data rate = Hlog(1+S/N)
conversion of S/N ratio to decible  = 10log(10,S/N) (to the base 10)
its irrespective of number of discrete levels

Data link layer
checks error transmission flow control
header and trailer attached to the network packet and called as frame
Ack is not a necessary service for data link its just optimization because instead of requiring n/w layer to send complete pkt again data link layer send the fragments that are not recieved


No Ack connectionless service
appropiate in case of real time traffic like voice where bad data is better than late data. used for less error prone channels

with Ack connectionless service
for unreliable channels like wireless


Framing methods
How do the receiver know in the continuous stream of data different frames
1)character count
2)flag byte with byte stuffing
include flag byte before header and after trailer
for each flag byte include escape character and one for each escape byte in data also
3)
to ensure that frame sequence never appears in the data
to frame sync sequence 01111110 containing six adjacent 1's a 0 bit is stuffed after every five 1's

Error detection and correction

error detecting code ,having enough information to identify error and
error correcting code, having enough redundacy to correct the corrupted data
consider data of m bits and r redundant bits
n = m+r
to detect d error we need distance d+1 code
to correct d error we would need 2d+1 code
 (n+1)2^m <= 2^n where n=m+r

Hamming rule
m+r+1 <= 2^r
this is lower limit on number of bits needed to correct single error in any of the n bits in message
we need to detect error in all the transmitted m+r bits and  
additional 1 is for no error

bits that are power of 2  {1 2 4 8 ...} are check bits rest are filled with data bits
each check bit forces the parity of some collection of bits including itself  A bit may be included in several parity computation

to which check bits the databit in position k contributes
like data bit at position contributes to check bits 1 2 8

A data bit k is checked by those check bits only

Problem A host uses odd parity to compute a hamming code
1)what is hamming code for bit sequence 1011001?

solution

from the hamming rule formula we find the minimum check bits required
it comes as r=4 for this message of size m=7 so total n =11
leave the check bits position which would be 1 2 4 8
and  calculate check bit for each data bit at that position
1 2  3  4  5 6 7 8 9 10 11
--------------------------
_ _  1  _  0 1 1 _ 0  0   1
find the check bits that contribute at each data positions

databit  check bit positions 
-------------------

3               0011
5               0101
6               0110
7               0111
9               1001
10             1010
11             1011

so check bit at position 2^0 forces parity for data bits at position {3,5,7,9,11} ={10101} odd
at position 2^1 to {3,6,7,10,11} = {11101} even
at position 2^2 to {5,6,7} ={011}even
at position 2^3 to {9,10,11} = {001} odd

so check bits at position 2 and 4 are 1
so hamming code is
0111 0 1 10 0  0   1

b)which bit is in error if following hamming code is recieved 0010011
solution
we have to include the check bit itself in parity check here
2^0 bit for {1,3,5,7} = 0101 error
2^1 for {2,3,6,7} = 0111 no error
2^2 for {4,5,6,7} =0011 error

error is in data position  2^0+2^2 = 5

Cyclic redundancy check

for polynomial of degree k include k zero bits at the end of the message m and divide m by polynomial g


upon receiving the checksummed frame receiver divides it by G(x) that is (T(x)+E(x))/G(x) T(x)/G(x) is zero so result of computation is E(x)/G(x) those error that are factor of polynomial will give zero other would give non zero result and would be caught

one bit error with CRC
E(x) = x^i so if G(x) has two or more terms it will give non zero remainder hence detected

Detecting double bit error
G(x) should not divide x^k + 1 for any k up to maximum  length of frame

Data link layer

control information or frame header(info also included)
1)kind whether any data in the frame or not
2)seq and ack


Problem A packet is divided in to 10 frames. chance frame getting correctly at receiver is .80 how many packet transmission required for successful
Solution  probability of successful transmission of packet = 1- .8^10
expected number of tranmission = {1 to infty} i (1-p)^i-1
geometric distribution
value = 1/p


making two changes to any valid code gives another valid code in case of parity so it has hamming distance of 2

MAC

Static channel allocation
if there are N users bandwith is divided in to N equal sized portions
mean time delay T
capacity of channel C bps
arrival rate of frames l frames/sec with mean 1/u bits/frame

service rate that is how many frames the channel can process = C/(1/u) =Cu  frames/sec
T = 1/ (uC - l)
that is when there is contention for channel we get the delay of T

For N subchannels
each with C/N bps capacity
frame arrival rate for each l/N frames/sec
Now T' = 1/(u(C/N) - (l/N))  = NT
that is mean dealy is N times that of single channel delay time

Dynamic Channel Allocation

Pure Aloha
feedback property of broadcasting : that is whenever a station transmits data it will also receive the same data so it has a way to know that if data got corrupted in transmission
terminal transmits whenever they have data to send without worry about collision
if two terminals try to transmit at the same time there will be collision data gets garbled and they need to send data again with random backoff time

Efficiency of Pure Aloha
frame time is the amount of time needed to transmit the fixed length frame
An infinite population of user generate new frames according to a poisson distribution with
mean N frames / frame time
If N>1 then  there will be collision on each transmission, that is channel can handle only 1 frame per frame time
we should have N<1 for reasonable throughput

There will be retransmissions of frame that suffered collision consider probability of k transmission attempts per frame time to be poisson distribution with mean G per frame time. G>= N
at low load G~= N at high loads number of collisons will be high so G>N

If there are N stations in the system
each station transmits with the probability p'
G is Average number of packets in the system
In period time t average packets will be  Np'
In vulnerable period of 2t it would be 2N*p'   //each transmits with p' only but for period of 2t

G' for vulnerable period is therefore 2Np'

Since G is the mean number of packet and from the poisson distribution we can find

Find the probability of k frame transmission give mean G
P[k] that is k packet trammisions occur

Probability that k frames are generated during a given frame time according to poisson distribution is
P[k] = (G^k e^-G)/k! where G is the mean number of frames


Expected number of transmission required for each sent frame = {k 1 to infty} kPk
e^2Np' or e^2G
What is throughput
P probability that a packet is successfully transmitted  //different from p' which is specific to station
Throughput average number of packets that can successfully go through
S = GP that is this fraction of transmitted frames escape collision

Find P, the probability that a packet is successfully transmitted
if t is the time to send frame then 2t is vulnerable period

P = probability of no other traffic during vulnerable period
probability of zero frame P[0] =  e^-Gfor duration of 2t its P[0] = e^-G'
so probability of no traffic during vulnerable period is e^-2G   or e ^-2Np'
and S = G * e^-2G  or
S in term of p' and N is S = Np' * e^-2Np'

When is maximum throughput achieved
Maximum through put is at G =1/2 or when power of  e is =1 by taking derivative wrt G
and is S= 1/2e or .184 so 18% is best channel utilization

Slotted Aloha

divides the time into discrete intervals each of frame time
user need to agree on slot boundaries
data is sent only at beginning of next slot
vulnerability period is halved t only

Probability of  successfully transmitting a packet in vulnerable period is e^-G
Probability of no other traffic in vulnerable period is e^-G which leads to
Throughput S =G e^-G
maximum throughput at G=1 with S =1/e = .368 that is 36.8%

Expected number of transmission required for each sent frame = {k 1 to infty} kPk
Pk probability requiring k transmission is from binomial distribution its
(1-p)^k-1*(p) where p is probability of successful transmission that is without collision
in case of slotted aloha its e^-G so
E = {k 1 to infty} k * (e^-G) (1-e^-G)^k-1  = e^G

Carrier Sense Multiple Access Protocol

stations listens to channel transmission and act accordingly

Persistent and Nonpersistent CSMA
first listen to channel, if busy wait until idle
if collision occurs , station waits random amount of time and starts all over again
1 persistent because transmits with probability 1 when finds channel idle

Cases in which collision can occur
if first station starts sending and second and already started transmission but because of propagation delay first station had sensed channel as free
while third station is transmitting and two stations are waiting for channel to be free they both will start with probability 1 so there will be collision

Non persistenet CSMA
In case of busy channel it doesnot continously sense the channel instead waits random amount of time

p persistent CSMA
applies to slotted channels
in case of idle channel it transmits with probability p and with probability 1-p defers till next slot

CSMA with collision detection

In CSMA stations donot transmit when they detects the channel as busy
In case of collision detection stations aborts transmission if they detect collision
saves channel bandwidth and time

How much time will it take for station to realize there has been collision
consider t to be propagation delay between farthest stations
transmission from station1 reaches station2 at time t0+t  if station1 transmits at t0
now if station2 starts transmitting just before the signal from station1 reaches station2 there will be collision and station2 will find it immediately but it will take 2t-e time to reach station1
So in the worst case a station cannot be sure that it has seized the channel until it has transmitted for period 2t without hearing collision
we model it as slotted aloha with 2t contention period(slot width)
Since station must continually  monitor the channel for collision so CSMA CD with single channel are half duplex because the receiving logic is used in sensing

Collision Free protocol

A bit map method
contention period consists of N slots and jth station sends a 1 in the jth slot if it has data queued for transmission After contention period is over each station is aware of other stations and they start transmitting in numerical order
Performance
low order stations has to wait on average 1.5N slots and
high order stations wait on average .5N slots
the mean for all stations is N slots
overhead per frame is N bits and amount of data d bits then efficiency is d/N+d
at high load its d/d+1

Ethernet

Manchester Encoding
used in Ethernet
to unambigously determine the start end or middle of each bit without reference to external clock
each bit is divided into two equal intervals.
A binary 1 bit is sent by having the voltage set high during the first interval and low in the second
A binary 0 bit is just the reverse low during first and then high.
requires twice as much bandwidth than straight binary encoding
to send data at 10Mbps signal has to change 20million times/sec

Differential Manchester
1 bit is indicated by absence of a transition at start of interval
0 bit is indicated by presence of a transition at start of interval
signal changes in the middle for both

Ethernet MAC protocol
preamble of 8bytes
sender and destination address 6byte address
0 for ordinary address and 1 for group address, group address allows multiple station to listen to single address its called multicast and address of all 1's is broadcast address
there are 48 - 2
type field tell the which process to give frame to according to proctocol name in type
data field is up to 1500 bytes maximum or including the destination and source address its 1518bytes
This doesnot include the Preamble and Start framedelimiter which are total 8 bytes
minimum data length also specified because
1)byte of 0 causes problem of stray bits in the channel so to distinguish valid frames from garbage there is minimum size of 64 bytes for frame and if data portion of frame is less than 46 bytes the padding is done
2)if the stations complete transmission of short frame before the noise burst gets back to it the sender would assume successful transmission only after time 2t can it know if collision occured
so for 10Mbps LAN with cable length of 2500meters , the worst round trip time has been determined as 50microsec Therefore minimum frame should be transmitted for at least this much time
Transmission of a bit on 10Mbps takes 100nsec so smallest frame should have 500 bits and so is the minimum frame for ethernet is 512 bits or 64bytes

So minimum frame size in ethernet including preamble and sfd is 512 + 64 bits

Checksum 32bit hashcode of data only error detection like CRC

Binary exponential backoff Algorithm(in case of collision not when senses channel busy)
After collision time is divided into discrete slots whose length is equal to 2t
After first collision each station waits either 0 or 1 slot times before trying again
After second collision each station waits either 0 1 2 3 at random
After third it would be 0  ..2^3-1

After 10 collisions its fixed at 1023 only if collision still happens and reaches 16 then its reported as failure

the value k that each station chooses depends on which collision number is it for that station

Problem

If two stations A and B collide  at first transmission A wins first backoff transmits successfully and then both tries to send again and collides again what is probability that A wins second backoff
Here slots avaiable for A are 0 and 1 because its 1st round for A
and for B slots available are 0 1 2 3 because its 2nd round for B
So the probability that A wins is if A chooses 0 and B chooses 123 anything or A chooses 1 and B chooses 2or 3
P(A wins) = 1/2 * 3/4 + 1/2 *2/4 = 5/ 8

How transmission in Ethernet works
1)Once it has the ethernet frame it senses the channel
If idle then start transmitting the frame
If channel is busy it must wait until it find the channel idle plus a additional wait of 96 bit times once it find it idle
2)monitors the channel after starting transmission If no signal from other stations found it has successful transmission if it finds the signal from other stations it stops transmission and transmits 48 bit jam signal instead
3)After transmitting the jam signal it enters exponential backoff and chooses the value K at random from 0 to 2^k-1 Then it waits for K*512 bit times and repeats again.

Why is jam signal required
In case B aborts the transmission after detecting transmission from A and has not put enough bits on the line, A may not be able to detect the signal and hence B needs to send jam signal


Performance of Ethernet
k stations are always ready to transmit
if each tranmits during contention period with probability p then probability A that some station acquires the channel is
A = k(1-p)^k-1p

A is maximized when p=1/k with A -> 1/e as k>infty

Expected number of slots per contention  = {j:1 to infty} jA(1-A)^j-1  = 1/A
each slot has duration of 2t the mean contention interval is 2t/A
for optimum value of p, expected number of contentions  =e
and contention interval would be at most 2te = 5.4e

Channel Efficiency
If mean frame takes P sec to transmit
Channel efficiency = P/(P+2t/A)
the longer the cable the longer will be contention interval

P=F/B framelength /bandwidth
A = 1/e for optimal case
t = L/c  , c is speed of signal propagation and L is length of cable

Channel efficiency = F/B/(F/B + 2(L/c)*(e)) = 1/(1+2BLe/cF)

Problem bandwidth C =100Mbps  10000 bits/frame  arrival rate 900frames/sec Delay for average frame?
Solution T = 1/(uC -l) 
mean frame length 1/u = 1/10000 =  10^-4

Problem Let N stations share 56-kbps pure Aloha. Each outputs 1000bit frame on average once 100sec
maximum value of N
Solution
required bandwidth for each station is 1000/100 bit/sec 10bit/sec
In Pure aloha usable bandwidth  is .184*56kbps = 10.3kbps
so N * (bandwidth for each station) = allowed bandwidth
N= 10300/10

In pure aloha, at small load,transmission can start instantly for slotted it has to wait for next slot introducing mean 1/2 slot of delay

Problem 10000 stations compete for slotted aloha channel Average station makes 18request/hour A slot is 125micro sec What is approx total channel load
Solution  Load is number of request in slot time
number of request per sec = 18/3600 = .005 request/sec
total number of request = .005*10000 = 50 request/sec
In slot period of 125micro sec number of request = 50 *125*10^-6 req/sec = 50/8000

Problem All formula  for slotted Aloha
G is number of requests in the vulnerable period = (number of request/sec) * vulnerable period
Solution Probability of success in slotted aloha is e^-G
Probability of success on kth transmission is (1-e^-G)^k e^-G
Expected number of transmission attempts =e^G

Problem In slotted Aloha 10% of slots are idle
1)what is G
probability of successful transmission is .1
so G= -ln P =-ln .1 =2.3
2)channel overload or underload
since G>1 so its overload

Problem If backlogged station donot accept new arrivals at MAC and unbacklogged accepts only single
Consider arrival rate of .05 arrival/slottime at each station by independent process, backlogged attempt retransmission with probability .02 in each slot
1)what is probability of arrival of new frame at MAC of unbacklogged & backlogged station
unbacklogged station will accept only first arrival
Probability of no arrivals = e^G
probability for at least one arrival at unbacklogged  = 1-e^-G  where G is .05
= .05
MAC of backlogged do not accept new arrivals so P=0
2)If there are 20 stations and 5 of them are backlogged what is probibility that one of the backlogged will see successfull transmission
For successful transmission no arrivals should be at backlogged station p= (e^-G)^15 = (1-.05)^15 = .472
For unbacklogged only one of them should transmit that is rest 4 should not transmit(
C(5 1)(1-.02)^4 * (.02)

Backlogged station do not accepts new arrivals at MAC because they donot have buffer So effective arrival rate at medium will decrease as the number of backlogged station increases
Poisson arrival rate is distributed equally at each station so if we arrival rate at medium is l then arrival rate at station is l/m for each m stations

Probability of unbacklogged station to transmit is 1- e^-G
Probability of i unbacklogged station transmit at next slot =
(ways to choose among i unbacklogged stations) (probability of transmitting for i unbacklogged stations)*(probability of not transmitting for remaining unbacklogged station)


Problem How long does a station has to wait before it can retransmit again
1)bit map protocol
assume frame is d bits If stations is the highest numbered
N bit of contention period + period when all N-1 transmits ( when last station wants to send just after its contention slot is gone)
= N + (N-1)*d   (assumption same 1bit for single slot time)

Problem Two CSMA/CD stations are trying to transmit multiframe file After each frame is sent they contend for channel using backoff algorithm
1)What is probability that contention ends on round k
Using backoff exponential algo
At round one they have single slot and they both try to transmit in that and hence collides
At round two there are 2 slots waiting for 0 and 1
At i th round station  can choose to wait in any 2^i-1 slots

Probability of choosing any one slot in ith period is 1/(2^i-1)
probability of both station choosing same slot is (1/2^i-1) * (1/2^i-1) = 1/2^2(i-1)
Total probability of choosing any of the 2^i-1 slot is hence P = 2^i-1 * (1/2^2(i-1)) = 1/2^i-1
this is probability of collision in ith round
for success on kth round we should have k-1 round in collison and kth round on success
that is
{product i:1 to k-1 }(1/2^i-1)  * (1- 1/2^i-1) 

 Problem what is baud rate in case of Ethernet
Solution
Ethernet uses manchester encoding which uses two signals to represent a bit so baud rate is 2 times the data rate because it has 1/2 bits/signal. In case of binary encoding baud rate = data rate
so for Ethernet 10mbps it should be 20megabaud

Problem Consider node A and B on the same 10Mbps Ethernet, propagation delay between two nodes is 225bit times
1)Node A starts transmitting and before it finishes node B starts transmitting .Can a finish transmitting before it detects that B has transmitted
The first bit from A reaches B at t=225 In the worst case B starts transmission at t=224 this transmission would reach A at 224+225(sent from B) =449 Since minimum frame size is 512+64 bit times A should be still transmitting and would detect collision
2)Suppose A and B both sends frame at the same time, the frames collide and then both chose different values of K in CSMA/CD Can retransmission collide Assume A chooses K=0 and B K=1?
Solution
At t=0 A and B starts transmitting
At t=225 both hears each other signals and start transmitting jam signal which is 48 bit time so
At t=225+48=273 both finishes transmitting jam signal, last bit of jam signal takes another 225 bit time to reach A and B
Immediately after sending the jam signal A B starts in exponential backoff
At t=273 A starts sensing the channel for transmission and B waits for 1*512 bit time that is 273+512=785  
A waits for the jam signal from B to reach it
At t=273+225=498 jam signal from B reaches A and A finds the channel idle and now before transmitting A has to wait for 96 bits
At t=498+96=594 A starts transmitting
A's first bit would reach B at 594+225 =819
so B would find the channel idle at 785 and would start wait in 96 bit period that is 881
At t=819 B would find signal from A and would not transmit

Problem Consider CSMA/CD network with 1Gbps over 1km cable. The speed of signal is 2*10^5km/sec.What is the minimum frame size
Solution propagation time = 5microsec
RTT = 10microsec
It should transmit for at least RTT period that is 1Gps*10microsec = 10^9 *10*10^-6 = 10000bits


Baud and Bit rate
Baud rate is signal /sec while bit rate is bits/sec
bit rate = baud rate * bits/signal

If we are using 1 bit per signal its same
If we are using
Baud rate in case of serial data transfer baud rate = bit rate single bit is used to represent signal
1 start bit 1/2 stop bit 0/1 parity bit for serial communication asynchronous
Example
1)calculate overhead for data size 7 bit ,1stop and no parity
overhead = 2/9 *100
2)represent 0101 1010 with 1 stop and no parity
start bit represented with 1 bit and stop with 0
1 0101 1010 0
3)time to transfer 4Mbits at 9600 baud rate
since in serial communication baud rate = bit rate we have
time = 4Mbits/9600 sec =

Stop and wait protocol

Line utilization is 1/(1+2a)   or transmission time/ (transmission+RTT)
L packet size and  u bandwidth
transmission time = L/u
a= propagation time / transmission time
transmission time is time to transmit a frame

Sliding window

Link utilization
1             when n >1+2a
N/1+2a   else


Problem Consider one way propagation time of .35sec, transmission rate of 1Mbps, and packet of 1000 bits ack time negligible
1)minumum timeout period for stop and wait ARQ

Timeout from end of the packet is 2*propagation delay
if we consider from start of packet it will add tramission time to this qunatity
2)minimum window size for go-Back N for 100% utilization assuming no errors?
window should be sufficiently large so as to transmit for the period until ack recieved
N /(1+2a) >=1
N >= 1+2a
frame transmission time = 1000/10^6 sec = 1ms
propagation time = .35
a= .35/10^-3 =  350

N = 701

Problem Consider 10Mbps bandwidth with propagation delay of 270ms and frame size of 10K-bit What is link utilization for stop and wait ARQ assuming probability of single frame error =10^-3
Solution line utlization = (1-P)/(1+2a)
For goback N its
N(1-p)/(q+2a)(1-p+Np)



Token Ring
Token cirulates in the ring topology LAN
when station wants to transmit data it converts token into data frame and start transmission at last it converts it in token back and circulates it in the ring
At each station a delay is introduced on data transmission
Release after transmission

Ring latency number of bits that can be in transit simultaneously or time for bit to circulate ring

Reinsertion strategies
1)Multi-Token operation: Free token transmitted immediately after the last bit of data frame ,that is, as soon as station has transmitted its data it will release free token
2)Single-Token operation: free token is inserted after last bit of busy token is received back that is free token is independent of data frame and depends on the ring length
If frame is longer than latency then that would mean busy token is recieved and its still transmitting so station would release free token when last bit of data frame is transmitted like multi token
3)Single frame operation
free token inerted when last bit of transmitted frame is received back at station

utilization = 1/ (1+a/N)
X maximum frame transmission time allowed per station
Throughput
Multi token



Problem consider a ring topology LAN with total length 2d with two stations d apart Ack is recieved by circulation of packet itself There are N=10 other stations on the ring each introduces delay of 1 bit
Solution
1)find the 1bit delay that is howlong is delay at each station in seconds
1Mbps is capacity so it would take 1microsec delay
2)total delay for N+2 stations = 12microsec
3)find how long it takes for 100 bit packet to fully circulate the ring and return to sender
propagation delay is 2d*5microsec = 10microsec Adding one bit delay gives 22microsec to fully circulate distance of 2d
4)transmission time of host 100/1M = 100microsec
5)host A will recieve the last bit at 122microsec for 100 bit packet
6)so for 10000 packets it would take 10000*122 = 1.22sec

Problem Consider there are N stations in token ring LAN Frame size is L bit, RMbps speed ,b bits latency per adapter d m between each stations with v speed find effective transfer time for all 3 strategy
Solution
1)Reinsertion after completion of transmission or Multi-Token operation
that is token is inserted after the transmission is complete
time to pass token to next station =  propagation time + bit latency delay, assuming token transmission time negligible
effective transmission time = frame transmission time + time to pass token to next station
                                        = L/R + (d/v+b/R)
Efficiency = L/R /(L/R+(d/v+b/R))

2)reinsertion after return of token or Single Token operation
where token is inserted after last bit of busy token is received back or if transmission is still in progress then when busy token is received then after transmission ends

Effective time = Max(frame transmission time,ring latency ) + time to pass token to next station
ring latency = time required for bit to circulate ring = N(d/v+b/R)
                   = Max{L/R,N(d/v+b/R)} + (d/v+b/R)
3)Reinsertion after return of frame or Single frame operation
time for last bit of frame to reach back to station = frame transmission time + ring latency
Effective transmission time = frame transmission time + ring latency + time to pass token to next station
Effective transmission time = L/R +  N(d/v+b/R) + (d/v+b/R)

Throghput
1)Single Frame
effective time = frame transmission X + ring latency τ'
consider normal ring latency a' = τ'/X
ρmax =  MX/(M(X+τ') +τ') = 1/(1+a'(1+1/m))
1)Multiple token
effective time = frame transmission X + ring latency τ'
consider normal ring latency a' = τ'/X
ρmax =  MX/(M(X+τ') +τ') = 1/(1+a'(1+1/m))


If each station transmits up to k frames/token Maximum throghput ?


References

nptel.iitm.ac.in/courses/.../Computer%20networks/pdf/M3L2.pdf