Qing Nets

The following is a MSWord Formula format document with all the queuing results needed in CPE 471.

m=#srvrs

ui=dprtr rte of srvr i

=capacity of link, usually all the same.

[[lambda]]i=arrvl rate into node i.

[[gamma]]=net arrvl rate

E(T)=network wide avg delay

E(n)=avg # of pkts in net

[[gamma]]E(T)=E(n)

Open

Jackson

ASSUME M cascaded M/M/1 Q's

E(T)=f(1,[[gamma]])isu(i=1,m,f([[lambda]]i,ui-[[lambda]]i))

[[rho]]iui=[[lambda]]i

Shortest Path Routing

min-hop means all weights 1

Alg A-Dijkstra

*makes a minimum weight spanning tree

*does not give routing table

w=next node

D(v)=dist from src 1 to node v

l(i,j)=cost from i to j

Initial Step

N={1}

for each v not in N DO

BEGIN

D(v)=l(1,v)

if v not connected to 1 then

D(v)=[[infinity]]

END

WHILE all nodes not in N DO BEGIN

find w not in N which makes D(w) min.

add w to N.

for each node not in N

{update D(v)}

D(v)=Min[D(v),D(w)+l(w,v)]

END

Use TABLE BELOW

step|N|D(2)|D(3)...|w

0|{1} |1|[[infinity]]|2

B-Alg

assume dest=1

Make a table:

V -> 2 3 4 ... N

step nd nd nd

0

1

2

Under the n you place the next node you know about from dest. under d you place min weight. Propagate till done

Dist-B-Algorithm

Assume 1 is dest.

NODE

step# 2 3 4 5 .. #msgs

{adj-list 4 ech nd}

initizlize start out with inf.

done when msg #=0

Predecessor Alg

send P to previous node

1-2-3-4

l(1,2)<-[[infinity]]

2 3 4 msg#

1 3 2 4 3

ini 1 p 2 p 3 -

0 * p 2 p 3 1

1 * p * p 3 1

2 * p * p * 0

Useful Formulas

isu(i=1,N,i)=f(N(N+1),2)

isu(i=1,N,i²)=f(N(N+1)(2N+1),6)

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

=time pkt wts in Q b 4 xmission begins

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 then [[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.

all stations equally spaced

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

if controller at end

then [[tau]]'= f([[tau]],2) (1+N)

if controller in middle

then [[tau]]'=f([[tau]],2)(1+f(N,2))

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

=walk time

t=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

TOKEN Passing Bus

in bus token addressed to specific station. If token passed to neighbors [[tau]]=rnd trip delay

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

tf=

m[[rho]][(f(E[m²],E[m]²)+(4e+2)a+5a²

+4e(2e-1)a²]/

2{1-[[rho]][1+(2e+1)a]}

+1+f(a,2) + 2ea -

f((1-e^-2a[[rho]])(f(2,[[rho]]) +f(2a,e)-6a),2[Fp([[lambda]])e^-[[rho]]a-1-1+e^-2[[rho]]a])<> f(t)=frm lngth dist

Fp([[lambda]])=Laplacian(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)²

lm|max=max normalized thruput rate

[[lambda]]|max=f(m,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