《《Compiling Packet Programs to Reconfigurable Switches》改编演讲PPT.ppt》由会员分享，可在线阅读，更多相关《《Compiling Packet Programs to Reconfigurable Switches》改编演讲PPT.ppt（47页珍藏版）》请在三一文库上搜索。
1、Compiling Packet Programs to Reconfigurable Switches,Lavanya Jose, Lisa Yan,Nick McKeown, and George Varghese,1,Research funded by AT&T, Intel, Open Networking Research Center.,2,Author,Lavanya JoseLisa YanNick McKeownGeorge Varghese,3,Author,Lavanya JoseLisa YanNick McKeownGeorge Varghese,4,The
2、 Mckeown Group,5,http:/yuba.stanford.edu/group_wp/,Author,Lavanya JoseLisa YanNick McKeownGeorge Varghese,6,In the next 20 minutes,Fixed-function switch chips will be replaced by reconfigurable switch chipsWe will program them using languages like P4We need a compiler to compile P4 programs to recon
3、figurable switch chips.,7,Fixed-Function Switch Chips,Parser,L3,L2,Packet,Packet,8,L2,v4,v6,ACL,Control Flow Graph,Switch Pipeline,Fixed-Function Switch Chips,Parser,L2 Table,IPv4 Table,IPv6 Table,ACL Table,L2,v4,v6,ACL,MyEncap,MyEncap,9,10,Fixed-Function Switch Chips Are Limited,Cant add new forwar
4、ding functionalityCant add new monitoring functionalityCant move resources between functions,Reconfigurable Switch Chips,Parser,Fixed Action,Fixed Action,Fixed Action,L2 Table,Fixed Action,IPv4 Table,IPv6 Table,ACL Table,Match Table,Match Table,Match Table,Match Table,L2,v4,v6,ACL,11,Protocol Indepe
5、ndent Switch,Reconfigurable Switch Chips,Parser,L2 Table,IPv4 Table,ACL Table,IPv6,MyEncap,L2,v4,v6,ACL,MyEncap,MyEncap,IPv4,IPv4,12,IPv6,IPv4,RMT & Intels FlexPipe,Reconfigurable chips are inevitable.,13,Parser,Fixed Action,Fixed Action,Fixed Action,L2 Table,Fixed Action,IPv4 Table,IPv6 Table,A
6、CL Table,Match Table,Match Table,Match Table,Match Table,P4 (http:/p4.org/),parser parse_ethernet extract(ethernet);select(latest.etherType) 0 x800 : parse_ipv4; 0 x86DD : parse_ipv6; ,table ipv4_lpm reads ipv4.dstAddr : lpm; actions set_next_hop; drop; ,control ingress apply(l2_table); if (valid(ip
7、v4) apply(ipv4_table); if (valid(ipv6) apply(ipv6_table); apply (acl);,14,(ANCS13),Parser,Match ActionTables,Control Flow Graph,Configuring Switch Chips,P4 code,Compiler,Compiler Target,15,Control Flow Graph,L2,Table Dependency Graph (TDG),v4,v6,ACL,L2,v4,v6,ACL,Table Dependency Graph,16,Step 1: P4
8、Program,17,18,Header widths,Action ALU input,Memory Type,Table parallelism,More resource constraints,Action Memory,Map match action tables in a TDG to a switch pipeline while respecting dependency and resource constraints.,The Compiler Problem,19,Two Switches We Studied,1,2,3,4,32,RMT32 Stages(SIGCO
9、MM 2013),20,Memory information for RMT,Two Switches We Studied,1,4,3,5,2,FlexPipe5 Stages(Intel FM6000),21,Memory information for FlexPipe,Two Switches We Studied,1,2,3,4,32,1,4,3,5,2,RMT32 Stages(SIGCOMM 2013),FlexPipe5 Stages(Intel FM6000),22,23,Two Switches We Studied,word-packing,First approach:
10、 Greedy,Prioritize one constraintSort tablesMap tables one at a time,Parser,24,1,2,3,4,Sort by # dependencies,First approach: Greedy,Parser,Prioritize one constraintSort tablesMap tables one at a time,2,3,4,Sort by match width,25,FFLFirst Fit by LevelFFDFirst Fit Decreasing FFLSFirst Fit by Level an
11、d Size MCFMost Constrained First,26,First approach: Greedy,Too many constraints for Greedy,Any greedy must sort tables based on a metric that is a fixed function of constraints.As the number of constraints gets larger, its harder for a fixed function to represent the interplay between all constraint
12、s.Can we do better than greedy?,27,Second approach:Integer Linear Programming (ILP),Find an optimal mapping.,Pros:Takes in all constraintsDifferent objectivesSolvers exist (CPLEX),28,Cons:Blackbox solverEncoding is an art Slow,ILP Setup,min # stagessubject to: dependency constraints,29,table sizes a
13、ssigned,memoriesassigned,table sizes specified,memories inphysical stage,Experiment Setup,30,Greedy vs ILP,A Typical TDG,31,Metrics: Greedy vs ILP,Ability to fit program in chipOptimalityRuntime,32,Experiment Results,33,5-stage FlexPipe,RMT for L2L3-Complex,Greedy vs ILPs,34,Greedy vs ILP,35,ILP sol
14、ution(16 stages),Greedy vs ILP,36,FFL-16 solution(19 stages),Greedy vs ILPs,37,Comparing greedy heuristics,38,TDG for L2L3-Mtag,Comparing greedy heuristics,39,FFLS solution (21 stages).,FFL solution (19 stages).,Comparing greedy heuristics,40,FFLS solution (21 stages).,Comparing greedy heuristics,41
15、,FFL solution (19 stages).,Comparing greedy heuristics,42,TDG for L2L3-Mtag,Prioritize dependencies, not table size!,Sensitivity Experiments,To improve ILP running timeTo improve Greedy Optimality Original ILP solution 16 stages in12.13s 104 cycles in233.84s ILP Improvement 12.13s to 7.1s 233.84s to
16、 66.29s,43,Use ILP to suggest best Greedy for program type.,44,Critical constraintsDependency critical: 16 13 stagesAdditional resource constraints less importantCritical resourcesTCAM memories critical: 16 14 stagesResults for one of our datacenter L2/L3 use cases,ILP Run time,Number of constraints
17、? Not obvious. E.g., RMTMin. stage: few secs.Min. power: few secs.Min. pipeline latency 10 x slowerNumber of variables? How fine-grained is the resource assignment? E.g., FlexPipeOne match entry at a time: many days.100-500 match entries at a time: 1 hr,Conclusion,Challenge: Parallelism and constrai
18、nts in reconfigurable chips makes compiling difficult.TDG: highlights parallelism in program.ILP: better if enough time, fitting is critical, or objectives are complicated. Best Greedy: ILP can choose via notion of critical constraints and critical resources.,46,Thank you!,47,Research funded by AT&T, Intel, Open Networking Research Center.,