1-3 Layers

physical(bit)

data link(frm)

-ECC&ARQ

network(pkt)

- rtng,flw cntrl

transport(msg)

flw cntrl,bfng,addsng

session(mng dlg)

-start up..

presentation

application

2-1psson Procs

T=fnt [[Delta]]t

P(k)=pr(k arvls in T)

assum psson

4 k[[epsilon]][0..[[infinity]]]

P(k)=([[lambda]]T)^ke^-[[lambda]]T/k!

[[Sigma]]P(k)=1

E(k)=mean/expt val

E(k)=[[Sigma]]kP(k)=[[lambda]]T

[[sigma]]k2=variance

=E[k-E(k)]^2

=E(k²)-E²(k)

=E(k)=[[lambda]]T

[[Iota]][[Phi]] [[lambda]]T>>1=> k/T ~[[lambda]]

T=m[[Delta]]t

P(k)=(a(m,k))P^kq^m-k

2-2 M/M/1/[[infinity]]

pr(arvl)=[[lambda]][[Delta]]t

pr(dptr)=u[[Delta]]t

Pn=pr(n in Q)

*asum stdy stat

*asum [[rho]]<1

[[rho]]=[[lambda]]/u

Pn[[lambda]]=Pn+1u

Pn=(1-[[rho]])[[rho]]ⁿ

isu(n=0,[[infinity]],Pn)=1

P0=P(Q empty)

1-P0=P(Q not empty)

=1-[[rho]]

E(n)=isu(n=0,[[infinity]],nPn)=f([[rho]],1-[[rho]])

E(T)=avg svc tim

[[lambda]]E(T)=E(n) by Little

E(T)=f([[rho]],[[lambda]](1-[[rho]]))

IF [[rho]]<<1 => E(T)=f(1,u)

E(W)=avg wt tim

E(T)=E(W)+1/u

E(q)=avg#in Q

E(q)=[[lambda]]E(W)

=[[lambda]]E(T)=[[lambda]]/u=E(n)-[[rho]]

M/M/1/N

isu(n=0,N,Pn)=1

P0=f(1-[[rho]],1-[[rho]]^N+1)

[[rho]]n=[[rho]]ⁿf(1-[[rho]],1-[[rho]]^N+1)

PB=pN=pr(Qis ful)

=calc prog 0 given [[rho]]

IF PB<<1 =>

PB~(1-[[rho]])[[rho]]^N

[[lambda]](1-PB)=[[gamma]]=thruput

=u(1-P0)

2-3 Little

[[tau]]=interval of time

A(t)=cumu arvls

D(t)=cumultv dptrs

L(t)=#waiting

L(t)=A(t)-D(t)

j=1,2...A(t)

tj=time of jth arvl

j=A(tj)

t'j=time pkt j lvs buff

=monotonically incrng

Wj=wait for pkt j

n([[tau]])=#arvls in [[tau]]

=A([[tau]])-A(0)

[[lambda]]([[tau]])=arvl rate durng [[tau]]

[[lambda]]([[tau]])=n([[tau]])/[[tau]]

isu(j=1,n([[tau]]),Wj)=i(o,[[tau]],L(t))dt

W([[tau]])=avg wait durng [[tau]]

=isu(j=1,n([[tau]]),Wj/n([[tau]]))

L([[tau]])=i(0,[[tau]],f(L(t),[[tau]]))dt

=avg buf lgth

n([[tau]])W([[tau]])/[[tau]]=L([[tau]])

=[[lambda]]([[tau]])W([[tau]])

if [[tau]]->[[infinity]] => L=[[lambda]]W

2-4 Q wth dscgmt

Stat-dpndt Q's:Brth-Dth Prc's

*arvl&svc rates=f(stat)

*M/M/m in this cls

*blkng systm wth no wtng room is in this cls

*Psson arivls

*expt svc

*eqlbrm is rchble

[[lambda]]n=arrvl rte with n in systm

pn=prob(n in systm)

un=dptr rte with n in systm

([[lambda]]n+un)pn

=[[lambda]]n-1

*pn-1+un+1pn+1

[[lambda]]npn=un+1pn+1

f(pn,po) =ipr(1=0,n-1,[[lambda]]i)/ipr(i=1,n,ui)

isu(n=0,N,pn)=1

M/M/2 case

*Asume

[[lambda]]n=[[lambda]],[[rho]]=[[lambda]]/2u

IF n=1 => un=u

IF n>=2 => BEGIN

un=2u

Po=prob(Q empty)

f(pn,po)=([[lambda]]/2u)^n-1([[lambda]]/u)

=2[[rho]]ⁿ

IF M/M/2/[[infinity]] =>

Po=(1-[[rho]])(1+[[rho]])

pn= f(1(1-[[rho]]),1-[[rho]]²)

E(n)

=isu(n=0,[[infinity]],npn)= f(2[[rho]],1-[[rho]]²)

E(T)=avg tim dly=wat tim+svc tim

E(T)=E(n)/[[lambda]]

max thrghput,2u, is'nt attnd becse N=0,1

[[gamma]]=avg thrput 4 2 svr cse

[[gamma]]=uP1+2u(1-Po-P1)

Pb=prob(blkng)

IF M/M/2/[[infinity]] & Pb=0 => BEGIN

[[gamma]]=[[lambda]]

[[rho]]=[[lambda]]/u

Po=e^-[[rho]]

Pn/Po=([[lambda]]/u)ⁿ/n!

IF un=nu => [[gamma]]=[[lambda]]

END

Q with dscgmnt

ie. t-phns

[[lambda]]n=[[lambda]]/(n+1)

[[lambda]] is known=max arrival rate

un=u 4 all n

IF Q has [[infinity]] buffer => BEGIN

[[rho]]=[[lambda]]/u

Po=e^-[[rho]]

Pn/Po=([[lambda]]/u)ⁿ/n!

E(n)=isu(m=0,[[infinity]],nPn) = [[rho]]

E(T)=E(n)/[[lambda]]=1/u

[[gamma]]=isu(n=0,[[infinity]],[[lambda]]nPn)

=u(1-e^-[[rho]])

uE(T)=normalized avg dly

=uE(n)/[[gamma]]=[[rho]]/(1-e^-[[rho]])/b>

M/M/N/N T-phns

pure loose systm

1<=n<=N

[[lambda]]n=[[lambda]]

IF n=N => PB=1

un=nu

[[gamma]]=[[lambda]]

[[rho]]=[[lambda]]/u

Pn=f([[rho]]ⁿ/n!,isu(l=0,N,[[rho]]^l/l!))

PB=PN Erlang-b dist

E(n)=[[rho]](1-PB)

[[Iota]][[Phi]] [[rho]]>>N&PB->1 => [[gamma]]max=Nu

E(t)=1/u=E(n)/[[gamma]]

2-5 M/G/1 Q:Mean value analysis

G=general svc tim dist.

*arbtry but knwn svc dist.

*arrival is psson

*buffer is [[infinity]]'ly long

[[rho]]=[[lambda]]/u

s²=variance of svc tim dist.

[[sigma]]²=1/u²

E(n)

=f([[rho]],1-[[rho]])[1-f([[rho]],2)(1-u²[[sigma]]²)]

[[Epsilon]]([[Tau]])=[[Epsilon]]([[nu]])/[[lambda]]

E([[tau]])=1/u

E(w)

=avg wt tim on Q

E([[tau]]²)=2nd mnt of svc tim dist.

E([[tau]]²)=[[sigma]]²+1/u²

E(w)

=E(T)-1/u=f([[lambda]]E([[tau]]²),2(1-[[rho]]))

E(w)=E(T)-1/u

E(w)=f([[lambda]]E([[tau]]²),2(1-[[rho]]))

[[sigma]]v2=[[rho]]+[[lambda]]2[[sigma]]2=variance of pkt # arrvng in svc interval

E(n)

=[[rho]]/2 + [[sigma]]v2/(2(1-[[rho]]))

M/D/1

D=dtrmnstc svc tim

Asume

[[infinity]][[pi]][[kappa]][[tau]][[sigma]] [[eta]][[alpha]]v[[epsilon]] [[sigma]][[alpha]]u[[epsilon]] [[sigma]]v[[chi]] [[lambda]][[nu]][[tau]][[eta]],1/u

s²=0

E(n)=f([[rho]],1-[[rho]])(1-f([[rho]],2))

IF [[rho]]<<1 => E(n)=[[rho]]/(1-[[rho]])

[[Epsilon]]([[Tau]])=[[Epsilon]]([[nu]])/[[lambda]]

E(w)=E(T)-1/u

E(w)=f([[lambda]]E([[tau]]²),2(1-[[rho]]))

[[sigma]]v2=[[rho]]+[[lambda]]2[[sigma]]2

E(n)=f([[rho]],2) + f([[sigma]]v2,2(1-[[rho]]))

2-6 Non-prmptive prrity Q's

[[rho]]=#([[chi]][[lambda]][[sigma]][[suchthat]][[sigma]])

li=psson arrval rate of cls i, 1<=i<=r

f(1,uk) = avg svc tim 4 cls k

ASUME non-preemptive svc.

p=a cls such that 1<=p<=r. 1 > priority than 2.

to=tim pkt of cls p arrives

wp=wait tim of p

To=tim 4 pkt in svc to comp svc.

Tk=tim 4 all other pkts <= p to comp svc.

T'k=tim 4 all other pkts < p to complete svc which arrived during wp

wp

= To +isu(k=1,p,Tk) +isu(k=1,p-1,T'k)

E(wp) = E(To) + isu(k=1,p,E(Tk)) +isu(k=1,p-1,E(T'k))

let E(mk)=avg # of pkts on cls k wtng 4 svc

E(Tk)=f(E(mk),uk)

=[[rho]]kE(wk)

[[rho]]k=[[lambda]][[kappa]]/uk

E(T'k)=f([[lambda]]kE(wp),uk)

=[[rho]]kE(wp)

E(To)=f([[lambda]][[Epsilon]]([[tau]]²),2)

=isu(k=1,r,f([[lambda]]E([[tau]]k2),2))

E(wp)

= f(E(To),(1-[[sigma]]p)(1-[[sigma]]p-1))

where [[sigma]]p=isu(k=1,p,[[rho]]k) & [[rho]]k=[[lambda]][[kappa]]/uk

ASUME 2 CLS's

E(W1) =f(E(To),1-[[rho]]1)

E(W2) =f(E(To),(1-[[rho]]1)(1-[[rho]]))

= f(E(W1),1-[[rho]]) where [[rho]]=[[rho]]1+[[rho]]2

if no priority => M/G/1 queue with

E([[tau]]2)=f(1,[[lambda]])([[lambda]]1 E([[tau]]12) + [[lambda]]2 E([[tau]]22))

4 n cases: isu(k=1,n,[[rho]]E(wk))=[[rho]]E(w)

4 Data link layer

ensures orderly,correct delivery of pkts btwn adj nodes.

HDLC=high level data link cntl

ARQ=automatic repeat request

Stop&wait

*one frm@a time.

*ack/nak

*rexmit.

*good 4 1/2 dplx.

*redced [[lambda]] in fll-dplx if long Tp

Go Back-n or continuous xmission

*Tack wt but tmout[[radical]]

*on Nak or

Tmot=>rxmt

*1 ack 4 many frms

Selective repeat

* nak or timout=> repition of 1 frm.

*rcvr must reorder.

3 long Tp => long buff

4 3=>not cmmrcl

5 4 may change

4-1 Stop&wait protocal

Ti=tim to xmit frm

Tout=timout lnth

2Tp=rnd trp dly time

=Tproc+tim 2 xmit ack

Tproc=rcvr processing tim

If no ack recv'd => Tt'=Tout+Ti=min tim btwn succesive frms

Asume half dpx:

Ts=tim to xmit ack or nack

Tv=avg xmission tim=Tv=Tt+(1-p)isu(i,[[infinity]],ipⁱTt)=Tt/(1-p)

[[lambda]]max=1 pckt/Tt sec's=max throughput=1/Tv

p=prob(frm er)

[[lambda]]=actual avg arrival rate

a=Tt/Ti >= 1

[[rho]]=[[lambda]]Ti<=(1-p)/a

IF 2Tp + Ts <<Ti => [[rho]]<1-p & a=1

4-2 Go-Back-N protocal

Asume

*full dpx-good if propagation delay is not small

*sequence numbers are unrestricted

*Nak & timout -> ARQ

*Ti=min tim between xmission Ti=Tt

*Ti=fixed frm lnth

*Tout fixed (ack arrives or re-xmit)

Tv=Ti+(1-p)isu(i,[[infinity]],ipⁱTt)

=Ti[f(1+(a-1)p,1-p)]

p=prob(frm er)

a=Tt/Ti

=1+(Tout/Ti)

asume saturatn

[[lambda]]max=1/Tv

= f((1-p),Ti[1+(a-1)p])

[[rho]]=[[lambda]]Ti=normalized throughput

<(1-p)/[1+(a-1)p]

If a=1 =>

2Tp+Ts << 1

IF sepert acks => 2Tp+Ts=min tim 2 rcv ack

IF acks are in frms the 2Tp+Ti=min tim 2 rcv ack

4-2-1 Thruput efcncy & optm pkt lnth

asume indpndnt occurance

Pb = prob(bit er)

l = lnth of pkt fld

l' = lnth of cntrl fld

P = frm er prblty

P=1- (1-Pb)^l+l'

= 1- Qb^l+l'

Qb=1-Pb

If Pb << 1 => P=(l+l')Pb

[[lambda]]max=satrtn stat xmission rate

D=avg data rate

asume sat xmission

GO bak-N-scheme

(4-9) D=[[lambda]]maxl

=(1-p)f(l,tI)[1+(a-1)P]

IF a=1 => (4-9) is stop & wait as well

tI=f((l+l'),c)

c=link xmssion rate

D/C = (f(l,l+l'))[f(1-p,1+(a-1)p)] <= 1

let tout=2tp+2tI

if a=1 or (a-1)p<<1 => lopt

=f(l',2)[r(1-f(4,l'logeqb))-1]

if pb<<1 or pbl'<<1 => lopt=r(l'/pb) -l'

and p=(l+l')pb

If Pb cnst&P=(l+l')Pb => lopt=r(l'/Pb) - l'

4-3 HDCL

Frm types:

I(informtn)

no info:

S(super)

U(unnumbered)

*blw ack N(R-1)

RR-rdy 2 rcv

RNR-not RR-bsy

REJ-rej all rst

P/F=comnd/respnd

4-3-1 [[gamma]] 4 HDCL

*finite m

*spfc ECC

*rules

1 REJ used once/frm

2 timout used

3 p/f@endof tim xmitter sends RR

m=seq#modulus

m-1=max#frms out

tp=1 way prop dly

tI=lngth of I frm

=(l+l')/c

l'=48

ts=lngth of S frm

=l'/c

tack=2tp+ts

Assum

*tout=2tp+2tI>tack

*tack<=(m-2)tI

P=P(frm err)

tv=avg tim 2 xmit frm of lngth tI

=tI+PE(T1)+f(P²T2,1-P)

T1=rnd tim 4 1st rpt

T2=avg tim 4 rexmit

L=max#I frms flwng er bfr rcvy strtd

L

=min{m-2,ëf(tout,tI)ø+1}

T1=[[tau]](x)

=(x+1)tI+tack+tI

P^x(1-P)=P(x frms in er & 1 no ER)

HDLC SUMMARY

if tack<=(m-2)tI =>tv

=tI+PE(T1)+f(P²,1-P)T2

E(T1)=

isu(x=0,L-1,(1-P)P^x[[tau]](x))

+P²[[tau]](L)

T2=[[tau]](L)

if LtI<(x+1)tI+tack=>

[[tau]](x)=(x+2)tI+tack ELSE [[tau]](x)=(x+2)tI

+[trnc(f(tack,tI)+1)]tI

if tout<=L tI => [[tau]](L)

=LtI+ts+tack+tI else

=tout+ts+tack+tI

[[lambda]]max=1/tv

D/C=l/(tvC)

SERIES APPROX.

isu(n=0,[[infinity]],1/xⁿ) =f(x,x-1)

isu(x=1,n,1/x!) = e

e^x=isu(n=0,[[infinity]],xⁿ/n!)

PROBABILITY

x=r.v.

E[x]=mean

E[X²]=2nd moment

[[sigma]]²=variance

[[sigma]]²=E[x²]-E[x]

m Fixed Dist

m=r.v.=msg lngth

[[sigma]]²=0

E[m²]=E[m]

m Exponential Dist

[[sigma]]m2=f(1,[[lambda]]2)

E[m]=f(1,[[lambda]])

E[m²]=f(2,[[lambda]]²)

[[rho]]=N=n[[lambda]]o(^-,m)

2o(^-,m)=E[m²]

POLLING

CONTROLLED ACCESS

D=Inbound delay

E(D)=avg access delay

m=msg xmission time

C=channel capacity

o(^-,l)=avg pkt lngth

l'=ovrhd bits

o(^-,m)=(o(^-,l)+l')/C

D=E(D)+o(^_,m)

E=avg number of retransmission attempts per message transmitted

K=retransmission interval

ts=sync time

tc=scan time

tp=length of polling message, i.e. 48 bits/4800 baud

L=walk time

[[rho]]=total trfic intensity

[[rho]]=sum([[rho]]i)=S

[[tau]]=rnd trip delay tim

[[tau]]'=overall propagation delay for N stations

[[lambda]]=per station rate of packet generation

[[rho]]=N[[lambda]]o(^_,m)

o(^-,t)c=L/(1-[[rho]])

E(D)=

=f(L,2) f(1-[[rho]]/N,1-[[rho]]) + f(N[[lambda]]E(m²),2(1-[[rho]]))

E(m²)=second moment of frame length

m fixed,

E(D)=f(o(^-,tc),2)(1-f([[rho]],N))+f(N[[lambda]][[omicron]](-,m)²,2(1-[[rho]]))

inbound delay is:

D=E(D)+ o(^-,m)

if m exp dist =>[[rho]]=N and

E(D)=[[phi]]([[rho]][[omicron]](^-,m),1-[[rho]]) and o(^-,m)=1/[[lambda]] and 1-[[rho]]/N=0

Roll Call Polling

-each station interrogated by cc.

L=Ntp+Nts+[[tau]]'

if all stations equally spaced then [[tau]]'= f([[tau]],2) (1+N)

Hub Polling

-cc institutes, station completes then xfer control

Lhub=[[tau]]+Nts

o(^-,tc)=L/(1-[[rho]])

RANDOM ACCESS POLLING

Time division

Frequency division

S=newly arriving pkt intensity=normalized throuput.

G=actual traffic intensity=utilization= normalized carried load

[[lambda]]'=total rate of pkts attmpting xmission including rexmission.

[[lambda]]=rate of pkts generated by each station.

[[lambda]]>[[lambda]]'

S/G=prob of no collision

E=avg # of rexmission attmpts/msg xmitted

K=rexmission interval in m units.

R=rnd trip delay+processing time in m unit intervals

Pure (Unslotted) aloha

wasteful of bandwidth about .18 of capacity

Assume m fixed

pkt avrls poisson

rexmission poisson

S=[[rho]]=N[[lambda]]m

Smax=f(1,2e) = .18

Nmax=f(.18,[[lambda]]m)

1/u=m

G=N[[lambda]]'m

[[lambda]]'=total#of pkts attempting to xmit over the channel, newly generated&rexmitted

[[lambda]]'>[[lambda]]

E=f([[lambda]]',[[lambda]]) - 1

S=Ge^-2G

G/S=1+E

E=e^2G-1

D=avg time required to succesfully rexmit a message.

D=m[1+R+E(R+f(k+1,2))]

Slotted Aloha

S=N[[lambda]]m

Nmax=f(.36,[[lambda]]m),

S=Ge^-,G

Peak ,value for S@G=1

S=.368

D/m=

1.5+R+E[R+.5+f(K+1,2)]

if K >5 =>S=Ge^-G

E=e^2G-1

are good aprox.'s

let k=5Local Area Networks

b=station latency in bits

N=number of stations

L=ring latency

[[tau]]=once around

propagation delay

c=channel capacity b/s

L=[[tau]]+Nb/c

tf=avg xfer time

=time to xfer data from one station to another

TOKEN PASSING RING OR BUS?? What is difference?

L/2=avg rng prop dly

tf=

f(L(1-[[rho]]/N)+[[lambda]]E(m²),2(1-[[rho]]))

+m+L/2

[[rho]]=[[lambda]]m

[[lambda]]=total avg tfc in syst.

m=avg frm lngth

CSMA/CD

[[rho]]max=1/[1+6.44a]

a=[[tau]]/m

[[tau]]=R/d

R=rate of prop in m/s

d=dist. in meters

f(t)=frm lngth dist

Fp([[lambda]])=Laplician(f(t))

M is fixed

E[m²]/E[m]²=1

[[Phi]][[pi]]([[lambda]])=e^-[[rho]]

^{M is Exp.}

E[m²]/E[m]²=2

Fp([[lambda]])=1/(1+[[rho]])

[[rho]]max=1/[1+6.44a]

[[tau]][[phi]]|u[[iota]][[nu]]=u+[[tau]]/2 as [[rho]]->0

tf=m+f([[lambda]]E[m²],2(1-[[rho]])) as a->0

Token Rings xfer delay-thruput -exp distb. pkt lng single pkt mode-complete rcpt of frm bfr rlsng tkn

[[rho]]=[[lambda]]m+[[lambda]]L

E[m²]=[[sigma]]²+(m+L)²

[[lambda]]m|max=max normalized thruput rate

[[lambda]]m|max=1/(1+L/m)

single token mode-token passed on when recieved back by xmitting station

f(t)=frm lngth dist.

f(t)=(1/m)e^-t/mu(t)

u(t)=unit step

f(t)=exp dist.

f'(t)=

(1-e^-l/m)d(t-L)

+f(1,m)e^-t/mu(t-L)

E(t)=L+me^-l/m

=m(l/m+e^-l/m)

[[rho]]max=[[lambda]]maxm

=1/(l/m+e^-l/m)

[[rho]]=[[lambda]]m