CS 636 Internetworking CS#636#Internetworking#ROUTER#ALGORITHMICS#Final#Review#1 CS 636 InternetworkingCS 636 Internetworking Measurement#CS 636 Internetworking 23 IP#Network#Management# What is happening in my network ?  How much traffic flows towards a given destination ?  What are the popular applications in my network?  How much should I charge my customer ?  … Network Operator Flow Measurement helps answer these questions ! CS 636 Internetworking4 Flow#Measurement#• Flow#is#a#combinaEon#of#various#header#fields#• Measuring#characterisEcs#of#a#flow#such#as##– number#of#packets,##– number#of#bytes,##– protocol#specific#flags#such#as#SYN/FIN/RST#etc.#• Ag gregates#computed#from#individual#flow#records#collected#from#various#routers#– Popular#applicaEons#obtained#via#aggregaEon#on#port#number#– Customer#traffic#metered#based#on#aggregaEon#on#desEnaEon#(and/or#source)#IP#address/prefix#CS 636 Internetworking5 NetFlow#• Widely#used#and#supported#in#routers#• Flow#is#a#five‐tuple#consisEng#of#SIP,#DIP,#SP,#DP,#Protocol#• Flow#records#contain#number#of#packets,#bytes,#Emestamps,#TCP#flags#• For#every#packet,#if#flow#exists,#update#counters,#otherwise,#create#a#flow#record#• Flow#records#expired#based#on#– TCP#flags#(FIN#or#RST),#inacEve#Emeout,#acEve#Emeout#(30#mins)#• At#high#line#rates,#all#the#three#resources,#memor y,#CPU#and#reporEng#bandwidth#become#boYlenecks#CS 636 Internetworking6 Flow#Measurement#at#Routers#Update flow record Packet Arrival Create flow if first packet Bottleneck 3: Reporting Bandwidth Bottleneck 2: Memory Utilization Bottleneck 1: CPU Processing Smart sampling (size dependent): Bandwidth Sample and hold: Memory, Bandwidth Packet sampling: CPU, Memory, Bandwidth Report expired flows to monitoring station CS 636 Internetworking7 Sampled#NetFlow#• Sample#packets#with#1#in#N#probability#– Configurable#N#to#reduce#memory,#processing#and#bandwidth#requirements#– Flow#records#updated#only#for#sampled#packets#– MulEply#by#N#for#each#flow#record#when#it#expires#• Problems#with#Sampled#NetFlow#– One#parameter#to#control#all#resources#limits#flexibility#– Strong#dependence#on#traffic#mix;#small#flows#exhaust#memory#and#affect#accuracy#CS 636 Internetworking8 AdapEve#NetFlow#[estan04]#• Divides#Eme#into#equal#measurement#bins#• Adapt#sampling#probability#in#each#bin#based#on#traffic#mix#– Begin#with#high#sampling#rate,#reduce#sampling#rate#as#memory#fills#up#• Problems#with#ANF#– High#memory#uElizaEon#as#it#needs#two#sets#for#seamless#operaEon#– Large#flows#get#reported#many#different#Emes#– Every#renormalizaEon#step#requires#extra#CPU#cycles#CS 636 Internetworking9 Flow#Slices:#Pudng#it#all#together#Packet sampling with probability q Flow Slicing with probability p Multifactor Smart Sampling Packet arrival Flow record sent to monitoring Reduces Bottleneck 1: CPU Reduces Bottleneck 2: Memory Reduces Bottleneck 3: Bandwidth CS 636 Internetworking10 Flow#measurement#soluEons#Reduce CPU Reduce Memory Reduce Bandwidth Packet arrival Flow record sent to monitoring Smart sampling Multifactor smart sampling Smart sampling Smart sampling N/A NetFlow Adaptive flow slicing probability Static sampling probability Adaptive Sampling Probability Static Sampling Probability Flow Slices Adaptive NetFlow Sampled NetFlow CS 636 Internetworking11 Flow#Slices:#Control#CPU#Packet Arrival lookup Entry not found Packet Sampling with probability q • Packet#sampling#stage#controls#CPU#usage#• Choose#q#as#maximum#probability#required#to#operate#within#CPU#constraints#Flow memory CS 636 Internetworking12 Flow#Slices:#Control#Memory#• Probability#‘p’#controls#the#rate#at#which#records#are#created#• Every#record#expired#ager#a#slice#duraEon#of#‘t’##• Slice#duraEon#controls#staleness#of#data##• Configurable#inacEvity#Emeout#• Can#adapt#slicing#probability#based#on#traffic#mix#any#Eme.#Flow slicing with probability p Packet Arrival lookup Entry not found Create flow Flow memory Packet Sampling with probability q Time out after slice duration or after inactivity timeout CS 636 Internetworking13 Unbiased#esEmators#• Produces#unbiased#esEmators#for#packet,#byte#and#SYN#counters##– Proofs#in#the#paper#• When#a#new#flow#is#created#ager#it#passes#the#flow#slicing#stage:#– Set#the#packet#counter#to#1/p##– Set#the#byte#counter#to#b/p#(b#is#size#of#the#first#packet)#– Set#the#“SYN#counter”#to#1/p,#if#packet#has#a#SYN#flag,#0#otherwise#CS 636 InternetworkingCS 636 Internetworking Usage‐based#Sampling#CS 636 Internetworking 14ObjecEve#CS 636 Internetworking 15CS 636 Internetworking Heav y#HiYers#CS 636 Internetworking 16Why#are#heavy#hiYers#important?#• Network#monitoring:#Current#tools#report#top#applicaEons,#top#senders/receivers#of#traffic#• Security:#Malicious#acEviEes#such#as#worms#and#flooding#DoS#aYacks#generate#much#traffic#• Capacity#planning:#Largest#elements#of#traffic#matrix#determine#network#growth#trends#• AccounEng:#Usage#based#billing#most#important#for#most#acEve#customers#17 CS 636 InternetworkingProblem#definiEon#• Iden%fy(and(measure(all#streams#whose#traffic(exceeds(threshold#(0.1%#of#link#capacity)#over#certain#Eme#interval#(1#minute)#– Streams#defined#by#fields#(e.g.#desEnaEon#IP)#– Single#pass#over#packets#– Small#worst#case#per#packet#processing#– Small#memory#usage#– Few#false#posiEves#/#false#negaEves#18 CS 636 InternetworkingMeasuring#the#heav y#hiYers#• Unscalable#soluEon:#keep#hash#table#with#a#counter#for#each#stream#and#report#largest#entries#• Inaccurate#soluEon:#count#only#sampled#packets#and#compensate#in#analysis#• Ideal#soluEon:#count#all#packets#but#only#for#the#heavy#hiYers#19 CS 636 InternetworkingHow#do#mulEstage#filters#work?#Array of counters Hash(Pink) 20 CS 636 InternetworkingHow#do#mulEstage#filters#work?#Collisions are OK 21 CS 636 InternetworkingHow#do#mulEstage#filters#work?#Stream memory stream1 1 Insert Reached threshold stream2 1 22 CS 636 InternetworkingStage 2 How#do#mulEstage#filters#work?#Stream memory stream1 1 Stage 1 23 CS 636 InternetworkingConservaEve#update#Gray = all prior packets 24 CS 636 InternetworkingConservaEve#update#Redundant Redundant 25 CS 636