**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 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 requiredit 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**

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**

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

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**

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**

**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 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 backoffHere 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%20ne

**two**rks/pdf/M3L2.pdf