CS 636 Internetworking CS#636#Internetworking#ROUTER#ALGORITHMICS#Lecture#18##Measurement#PrimiBves#1 CS 636 InternetworkingExisBng#router#infrastructure#• Routers#come#with#SNMP#– Not#very#fine#grained#(only#per‐interface)##– Not#useful#for#debugging#delay#or#loss#problems#• Routers#come#with#NetFlow#– Only#useful#for#per‐flow#staBsBcs##– Not#useful#for#debugging#performance#problems#• Routers#come#with#syslogs#– Some#informaBon#in#ad#hoc#fashion#– Very#liTle#informaBon#regarding#delays#and#losses#2 Wisconsin Networking SeminarApplying#exisBng#techniques#• Standard#approach#is#acBve#probes#and#tomography#– Join#results#from#many#paths#to#infer#per‐link#properBes##– Can#be#applied#to#measuring#all#the#metrics#of#interest#• LimitaBons#– Overheads#for#sending#probes#may#limit#granularity#• Cannot#be#used#to#measure#things#like#μbursts#(10s#of#μsecs)#– Lack#of#Bght#end‐to‐end#Bme‐synchronizaBon#• Typical#NTP#error#is#on#the#order#of#milliseconds#– Tomography#inaccurate#due#to#under‐constrained#formulaBon#No guarantee that metrics measured by probes are representative of those experienced by any particular traffic flow 3 Wisconsin Networking SeminarMoBvaBon#If we could make changes to routers, what new primitives should we add to aid in debugging performance problems? 4 Wisconsin Networking Seminar• Model#• Why#simple#data#structures#do#not#work#• LDA#for#average#delay#and#variance#• ExploiBng#LDAs#to#detect#microbursts#Outline#5 Wisconsin Networking Seminar• Packets#always#travel#from#S#to#R#– R#to#S#is#considered#separately#• Divide#Bme#into#equal#bins#(measurement#intervals)#– Interval#depends#on#granularity#required#(typically#sub‐second)##• Both#S#and#R#maintain#some#state#D#about#packets#– State#is#updated#upon#packet#departure#• S#transmits#DS#to#R#– R#computes#the#required#metric#as#f(DS#,#DR)#Sender#S# Receiver#R#DS#DR#Abstract#segment#model#6 Wisconsin Networking Seminar AssumpBon#1:#FIFO#link#between#sender#and#receiver# AssumpBon#2:#Fine‐grained# per‐segment#Bme#synchronizaBon#– Using#IEEE#1588#protocol,#for#example# AssumpBon#3:#Link#suscepBble#to#loss#as#well#as#variable#delay# AssumpBon#4:#A#liTle#bit#of#hardware#can#be#put#in#the#routers# You#may#have#objecBons,#we#will#address#common#ones#later#Sender#S# Receiver#R#AssumpBons#7 Wisconsin Networking Seminar• Constraint#1:#Very#liTle#high‐speed#memory#• Constraint#2:#Limited#communicaBon#budget#• Constraint#3:#Constrained#processing#capacity#• Consider#a#run‐of‐the‐mill#OC‐192#(10‐Gbps)#link#– 250‐byte#packets#implies#5#million#packets#per#second##Sender#S# Receiver#R#Constraints#8 Wisconsin Networking Seminar• Store#a#packet#counter#at#S#and#R.#• S#sends#the#counter#value#to#R#periodically#• R#computes#loss#by#subtracBng#its#counter#value#from#S’s#counter#Sender#S# Receiver#R#counter counter 1 123 2Loss = 3 – 2 = 1 CompuBng#loss#Sender#S#9 Wisconsin Networking Seminar• A#naïve#first#cut:#Bmestamps#– Store#Bmestamps#for#each#packet#at#sender,#receiver#– Aher#every#cycle,#S#sends#the#packet#Bmestamps#to#R#– R#computes#individual#delays,#and#computes#average#– 5M#packets#require#~#25,000#packets#(200#labels/pkt)#10#12#15#23#26#35#Sender#S# Receiver#R#13#14#20#47/3#=#15.7#Avg delay CompuBng#delay#(naïve)#Extremely high communication and storage costs 10 Wisconsin Networking Seminar• (Slightly)#beTer#approach:#sampling#– Store#Bmestamps#for#only#sampled#packets#at#sender,#receiver#– Aher#every#cycle,#sender#sends#the#packet#Bmestamps#to#the#receiver#for#the#sampled#packets#– 1#in#100#sampling#means#~#250#packets#10#15#23#35#Sender#S# Receiver#R#13#20#33/2#=#16.5#Avg delay CompuBng#delay#(sampled)#Less expensive, but we can do better…. 11 Wisconsin Networking Seminar• ObservaBon:#AggregaBon#can#reduce#cost#– Store#sum#of#the#Bmestamps#at#S#&#R#– Aher#every#cycle,#S#sends#its#sum#CS#to#R#– R#computes#average#delay#as#(CS#–#CR)#/#N#– Only#one#counter#and#one#packet#to#send#– Average#representaBve#of#all#packets#Sender#S# Receiver#R#84‐37/3#=#15.7#Avg delay counter 10+12+15 23+26+35 Delay#with#no#packet#loss#counter Works great, if packets were never lost… 12 Wisconsin Networking Seminar• Lost#packets#can#cause#significant#errors#• k#packet#losses#results#in#an#error#of#O(Wk/N)#– W#is#the#absolute#Bmestamp#– N#is#number#of#packets#• Quick#fix##1:#make#W#relaBve#to#the#first#packet#– Error#is#O(T/N)#where#T#is#the#size#of#the#measurement#interval#• Failed#quick#fix##2:#Bloom#filter#will#not#work#– Always#a#finite#false#posiBve#probability#Sender#S# Receiver#R#58‐37/3#=#7#counter 10+12+15 23+35 Delay#in#the#presence#of#loss#counter Avg delay 13 Wisconsin Networking Seminar• (Much)#beTer#idea:##– Spread#loss#across#several#buckets#– Discard#buckets#with#lost#packets#• Lossy#Difference#Aggregator#(LDA)#– Hash#table#with#packet#count#and#Bmestamp#sum#Sender#S# Receiver#R#10#12#15#17#23#26# 39#+#+# +#23#65#1#2#25#29#2#2#0#36#0#2#‐# =#36/2=#18#Delay#in#the#presence#of#loss#Sender#S#14 Wisconsin Networking Seminar• Packet#loss#– k#packet#losses#can#corrupt#up#to#k#buckets#– If#k#<<#B,#then#only#a#small#subset#of#buckets#corrupted#• Problem:#High#loss#implies#many#bad#buckets#• SoluBon:#Sampling#– Control#sampling#rate#such#that#no#more#than#some#fracBon#of#buckets#corrupted##– Can#also#be#formulated#to#maximize#expected#number#of#good#samples#Analysis#of#LDA#15 Wisconsin Networking SeminarAdjusBng#sampling#rate#Sender#S# Receiver#R#10#12#15#17#+#+#Sender#S#10# 10#15# 15#12#10#39#+#26# 26#23# 23# 23#23#+# +#S R p1 p2 p3 p4 23#65#1#2#10#29#1#2#13#36#1#2#‐# =#49/3=#16.3#16 Wisconsin Networking SeminarMaking#it#fast#Sender#S# Receiver#R#10#12#15#17#+#+#Sender#S#10# 10#15#15#12#10#+# +#S H( ) = 000010 (2) H( ) = 000111 (7) H( ) = 001101 (13) H( ) = 110110 (54) 17 Wisconsin Networking Seminar 0-3 4-11 12-27 28-59• JiTer#is#a#measure#of# variance#in#delay##• Can#we#adapt#LDA#to#measure#variance#?##• SoluBon#idea:#inspired#by#sketching#[AMS96]#– Consider#random#variable#Xi#that#takes#values#+1#and#‐1#with#probability#½#–