WIXLIB

Performance Contracts forSoftware Network FunctionsRishabh Iyer, Luis Pedrosa, Arseniy Zaostrovnykh,Solal Pirelli, Katerina Argyraki, George Candea

Software Network Functions – Pros and Conso Increased flexibility o Reduced capital and operating expenses o Programming errors o Unexpected performance behaviour 2

Dealing with unexpected NF performanceo Goal: Comprehensive understanding of NF’s performance profilev Operators – capacity planning and anticipate attacksv Developers – informed development decisionso Previous work [NSDI’12, NSDI’18, SIGCOMM’18]v Focus on narrow subset of input workloadsv Offer few completeness guarantees3

Performance Contracts for NFso Abstraction for users to parameterize arbitrary input workloadso Predict performance for workload spec without running NFo Performance predicted as function of Performance Critical Variables (PCVs)o Per-packet metrics: Instruction count, memory accesses, latency (cycles)Performance ContractWorkloadPerformanceSpecPrediction4

Outlineo What is a performance contract?o How does Bolt generate contracts?o Evaluation & Use-Case5

Running example6

Running example7

Running example8

Running example9

Running exampleMACtable implementationHash 0Key AHash 1Hash 2Hash 3Key BKey CHash 4Hash 5Key D10

Performance Contracts ExamplePerformance Contract for MAC bridgeMetric: Lines of pseudo-codeTraffic ClassPerformance11

Performance Contracts ExamplePerformance Contract for MAC bridgeMetric: Lines of pseudo-codeTraffic ClassPerformanceInvalid HeaderValid, DestMAC knownValid, DestMAC unknown12

Performance Contracts ExamplePerformance Contract for MAC bridgeMetric: Lines of pseudo-codeTraffic ClassPerformanceInvalid Header3Valid, DestMAC known3! 20Valid, DestMAC unknown 3! 100! Number of hash collisions13

Using performance contractsSpec 1: Unconstrained trafficPerformance Contract for MAC bridgeMetric: Lines of pseudo-codeTraffic ClassPerformanceInvalid Header3Valid, DestMAC known3! 20Valid, DestMAC unknown 3! 100! Number of hash collisions14

Using performance contractsSpec 1: Unconstrained trafficPerformance Contract for MAC bridgeMetric: Lines of pseudo-code 0 max &'(()*)' *Predicted performance:3 max &'(()*)' * 100Traffic ClassPerformanceInvalid Header3Valid, DestMAC known30 20Valid, DestMAC unknown 30 1000 Number of hash collisions15

Using performance contractsSpec 2: No hash collisionsPerformance Contract for MAC bridgeMetric: Lines of pseudo-code ! 0Predicted performance:100Traffic ClassPerformanceInvalid Header3Valid, DestMAC known3! 20Valid, DestMAC unknown 3! 100! Number of hash collisions16

Using performance contractsSpec 3: Valid, no collisions,Performance Contract for MAC bridgeDestMAC knownMetric: Lines of pseudo-code ! 0Predicted performance:20Traffic ClassPerformanceInvalid Header3Valid, DestMAC known3! 20Valid, DestMAC unknown 3! 100! Number of hash collisions17

Using performance contractsSpec 3: Valid, no collisions,Performance Contract for MAC bridgeDestMAC knownMetric: Lines of pseudo-code ! 0Predicted performance:20Traffic ClassPerformanceInvalid Header3Valid, DestMAC known3! 20Valid, DestMAC unknown 3! 100! Number of hash collisionsContracts quantify performance for all traffic classes of the NFUsers query contract for performance of specific input workloads18

Outlineo What is a performance contract?o How does Bolt generate contracts?o Evaluation & Use-Case19

Generating performance contracts recursivelyNF chainFirewallNAT Bridge 20

Generating performance contracts recursivelyIndividual NFStateless CodeStateful NFdata structuresMACtableput(), get()21

Generating performance contracts recursivelyIndividual NFStateless Code(Simple to analyze)*Stateful NFdata structures(Hard to analyze)*MACtableput(), get()*A.Zaostrovnykh, S.Pirelli, L.Pedrosa, K.Argyraki, G.Candea “AFormally Verified NAT” SIGCOMM 201722

Generating performance contracts recursivelyo Well defined separation between stateful and stateless NF code*o NFs typically have well defined, isolated stateo Encapsulate NF state using a library of data structureso Stateful data structures – Base case of recursive processo Analyze once, reuse across NFs*A.Zaostrovnykh, S.Pirelli, L.Pedrosa, K.Argyraki, G.Candea “AFormally Verified NAT” SIGCOMM 201723

Analyzing stateful data structures!"# %#&'()"* -(./0 .')1"0, * 30'0", )%( -4, . .o Cannot account for all possible packet histories - Path explosiono BUT, performance of MACtable depends ONLY on number of hash collisions24

Performance Critical Variables (PCVs)o Abstract away NF state specificitieso Succinctly summarize impact of packet history, configuration on performanceo Tailor legibility and detail to audienceContract for MACtable putTraffic ClassUnconstrainedPerformance1! 2Contract for MACtable getTraffic ClassKey presentKey absentPerformance2! 122! 7! Number of hash collisionsOnly PCV required to summarize perf in terms of lines of pseudo-code25

Generating Performance Contracts for NFso Symbolically execute stateless code to traverse all execution pathso While traversing each pathv Keep track of performance metrics for stateless codev Plug in contracts for stateful code using path constraints26

Generating Performance Contracts for NFsInvalid3Valid127

Generating Performance Contracts for NFsInvalid3Valid11C 2Traffic ClassUnconstrainedPerformance1! 2Contract for MACtable put28

Generating Performance Contracts for NFsInvalid3Valid11C 2DestMAC knownDestMAC unknown2C 122C 7Traffic ClassKey presentKey absentPerformance2" 122" 7Contract for MACtable get29

Generating Performance Contracts for NFsInvalid3Valid11C 2DestMAC knownDestMAC unknown2C 1252C 79030

Generating Performance Contracts for NFsPerformance Contract for MAC bridgeTraffic ClassPerformanceInvalid Header3Valid, DestMAC known3! 20Valid, DestMAC unknown 3! 100! Number of hash collisionsInvalid3Valid11C 2DestMAC knownDestMAC unknown2C 1252C 79031

Performance Contracts for NF chainso Generate performance contracts for individual NFs in chaino Pair together traffic classes from communicating NFso For each pair - AND respective constraints togetherv Equate packet sent by first NF to packet received by second32

Performance Contract for NF chains - ExampleFirewallFirewallDrops packetswith IP optionsRouterFast path – No IPoptionsSlow path – IPoptionsRouterTraffic Class PerfF1IP opt20F2 No IP opt 50Traffic Class PerfIP opt500 R1No IP opt60 R2NF chainTraffic Class PerfIP opt20No IP opt 110 F1 F2, R2 33

Outlineo What is a performance contract?o How does Bolt generate contracts?o Evaluation and Use-Case34

Evaluation setup & methodologyo 4 NFs - NAT, Maglev-like LB, MAC bridge, LPM routero Analyze NF logic DPDK NIC driver*o Metrics – instructions executed, memory accesses, execution cycleso Testbed - Intel Xeon E5-2667v2 3.3GHz, 82599ES 10Gb NICso Compare predicted vs measured performance for various packet classesTester*S.Pirelli, A.Zaostrovnykh, G.Candea “ADevice under TestFormally Verified NAT Stack” KBNETS Workshop - SIGCOMM 201835

Predictions for Instruction Count, Memory AccessesResults for Maglev-like Load BalancerDescriptionLB1Unconstrained trafficLB2Client packet, new flowLB3Client packet, existing flow,unresponsive backendLB4Client packet, existing flow,existing backendLB5Heartbeat packetsInstruction Count (IC)Memory Accesses (MA)10Prediction Gap (%)Class86420LB1LB2LB3LB4LB5ClassMax prediction gap – 7.5% (IC) and 7.6% (MA)36

Why is there a prediction gap?o Source 1: Trade-off between precision and legibility in PCVsv Can be overcome by exposing more detailo Source 2: Differences between analyzed and production codev Disabled link time optimizations in analyzed code37

Use Case – Informed cost-benefit analysiso Example: Bridge with randomized hash tablev Incorporates random key into hash functionv Rehashes all entries with a new key when collisions greater than a thresholdo Question: Where to place threshold?v Avoid rehashing under normal operationv Should rehash under attack38

Use Case – Informed cost-benefit analysisPredicted IC1060.1CCDF1050.011040.0011031234567Predicted IC18Number of hash collisions39

Use Case – Informed cost-benefit analysisPredicted ICCCDF1060.1CCDF1050.011040.0011031234567Predicted IC18Number of hash collisionsBolt allows operators to visualize the consequences of their decisions 40

Performance Contracts for NFso Abstraction for users to parameterize arbitrary input workloadso Predict performance for workload spec without running NFo Performance predicted as function of Performance Critical Variables (PCVs)bolt-perf-contracts.github.io41

Backup Slideso Distillero Results – IC, MAo Results – NF chainso Results – Latencyo Full Blown Contract42

The Bolt Distillero Users need to know which traffic classes are likelyo Bolt is a static analysis tool, cannot know probabilities of each traffic classo The Bolt Distillerv Input – A representative packet tracev Output - Execution path taken by each packet & values of PCVsv Users can then extrapolate the likelihood and query contract accordinglyBack43

Predictions for Instruction Count, Memory AccessesResults for NAT, BridgeClassDescriptionNAT1Unconstrained traffic10NAT2Client packet, new flow8NAT3Existing flowNAT4External, dropped packetBR1Unconstrained trafficBR2Broadcast trafficBR3Unicast trafficPrediction Gap (%)Instruction Count (IC)Memory Accesses (MA)6420NAT1NAT2NAT3NAT4BR1BR2BR3ClassBackBolt predicts IC & MA accurately, irrespective of NF/Traffic Class44

Predictions for NF chainso NFs chained togetherv Firewall – drops packets with IP optionsv Router – Fast path (No IP options), Slow path (packets with IP options)Instruction Count (IC)Memory Accesses (MA)ClassDescriptionC1Packets with IP optionsC2Packets without IP optionsPrediction Gap (%)1086420C1BackClassC245

Predictions for Latency (Execution Cycles)Results for Maglev-like Load BalancerDescriptionLB1Unconstrained trafficLB2Client packet, new flowLB3Client packet, existing flow,unresponsive backendLB4LB5Client packet, existing flow,existing backendHeartbeat packetsExecution Cycles10Over-estimation RatioClass86420LB1LB2LB3ClassLB4LB5Back9x for pathological traffic, 3x for typical traffic46

Predictions for Execution CyclesResults for LB,NAT, Bridge,LPMBack47

Full Blown ContractBack48

Outline oWhat is a performance contract? oHow does Bolt generate contracts? oEvaluation & Use-Case 5. Running example 6. Running example 7. Running example 8. Running example 9. Key A Running example 10 Hash 0 Hash 1 Hash 2 Hash 3 Hash 4 Hash 5 Key B Key C Key D MACtable implementation. PerformanceContracts Example 11 Performance Contract for MAC_bridge Traffic Class Performance