TABLE III THE QUALITY OF PIPELINE profile tables entries n=10n=20n=30n=40n=50n=100 single 121 44 961 1681 2601 1020 multi-nonopt-dep 43 63 83 103 123 223 multi-opt-nondep 120 232 350 460 570 1120 multi-opt-dep 40 60 0 100 120 220 TABLE IV notion of dependent labels to refine the label sets generated by PERFORMANCE:PINGALL TIME the taint analysis.The dependent labels are used at the runtime for flow table entry generation to further reduce the number of profile pingall time(s)】 n=10n=20n=30Tn=40n=50n=100 table entries.The evaluation results show that POMP generates single 0.60 6. 28 78 18T 2831 ovsk 0.10 0.60 high-quality forwarding pipelines.POMP pipeline for learning 13 2.4 3.7 15 multi-nonopt-dep 0.20 0.78 18 3.1 4.9 20 switches uses up to 47x fewer number of table entries.and is multi-opt-nondep 0.54 2.1 4.5 7.8 12 47 up to 137x faster than single table. multi-opt-dep 0.19 0.76 1.7 3.1 4.8 19 Note that,although the learning switches example is used throughout the paper to demonstrate the key ideas,POMP TABLE V is a general purpose language for SDN programming.In PERFORMANCE:NUMBER OF PACKETIN addition to these APIs used in learning switches,there are packet in profile more provided,including those for environment management. n=10 n=20 n=30 n=40 n=50n=100 single 117 423 939 1643 2549 10099 The set of POMP APIs is as expressive as those in Maple. multi-nonopt-dep 6 女 79 92 111 223 multi-opt-nondep 124 258 351 452 562 1134 REFERENCES multi-opt-dep 47 72 80 93 112 221 [1]P.Bosshart,D.Daly,G.Gibb,M.Izzard,N.McKeown,J.Rexford C.Schlesinger,D.Talayco,A.Vahdat,G.Varghese,and D.Walker "P4:Programming protocol-independent packet processors,"S/GCOMM number of table entries.Also,unlike POMP that generates flow Comput.Commun.Rev.,vol.44,no.3,pp.87-95,Jul.2014 [2]H.Song."Protocol-oblivious forwarding:Unleash the power of SDN table entries reactively at runtime,Magellan generates table through a future-proof forwarding plane,"in Proc.of HotSDN.2013. entries proactively by enumerating all possible executions of pp.127-132. the network policy before its deployment.Moreover.Magellan [3]P.Bosshart,G.Gibb,H.-S.Kim,G.Varghese,N.McKeown,M.Iz- zard,F.Mujica,and M.Horowitz,"Forwarding metamorphosis:Fast provides no mechanisms for protocol oblivious programming. programmable match-action processing in hardware for SDN,"in Proc. Concurrent NetCore [13]extends NetCore [7]to support ofS1 GCOMM,2013,pp.99-110. multi-tables,but it requires the programmer to manually define [4] M.Shahbaz,S.Choi,B.Pfaff,C.Kim,N.Feamster,N.McKeown,and J.Rexford,"Pisces:A programmable,protocol-independent software the layout of flow tables instead of generating it automatically switch."in Proc.of SIGCOMM.2016.pp.525-538. from high-level policies as we do in POMP. [5]A.Voellmy.J.Wang.Y.R.Yang.B.Ford,and P.Hudak,"Maple: Stateful NetKAT [14]and SNAP [15]extend NetKAT [6] Simplifying SDN programming using algorithmic policies,"in Proc.of SIGCOMM,2013.pp.87-98. and NetCore [7]respectively to support persistent states [6]C.J.Anderson,N.Foster,A.Guha,J.-B.Jeannin,D.Kozen, in emerging SDN data plane.They are for quite different C.Schlesinger,and D.Walker,"Netkat:Semantic foundations for purposes (to take advantage of the switch-local computation networks,"in Proc.of POPL,2014.pp.113-126. [7]C.Monsanto.N.Foster.R.Harrison.and D.Walker."A compiler power)and do not handle multi-table pipelines. and run-time system for network programming languages,"in Proc.of P4 Runtime [16]provides a way for control plane to control P0PL,2012,Pp.217-230. P4 switches.The programmer can use P4 Runtime APIs to [8]S.Hunt and D.Sands,"On flow-sensitive security types,"in Prof.of POPL,2006.pp.79-90. install flow table entries at runtime.In POMP,the programmer (9]B.Lantz,B.Heller,and N.McKeown,"A network in a laptop:Rapid doesn't use P4 Runtime APIs.The switch abstraction layer prototyping for software-defined networks,"in Proc.of Homets-IX. (see Fig.1)accepts entries generated by the runtime of POMP, 2010,Pp.191-19:6 [10]"P4 behavioral model,"https://github.com/p4lang/behavioral-model,ac- then calls P4 Runtime APIs to install entries for P4 switches. cessed:2017-07-31. [11]"Open vSwitch,"http://openvswitch.org/,accessed:2017-07-31. VIII.CONCLUSION [12]A.Voellmy,S.Chen,X.Wang,and Y.R.Yang."Magellan:Generating POMP is a general purpose SDN programming environment multi-table datapath from datapath oblivious algorithmic SDN policies,' supporting both protocol oblivious programming and auto- in Proc.of SIGCOMM,2016,pp.593-594. [13]C.Schlesinger,M.Greenberg.and D.Walker."Concurrent netcore: matic multi-table pipelining.It extends the C language with From policies to pipelines,"in Proc.of ICFP.2014.pp.11-24. a set of APIs and a runtime system to allow programmers to [14]J.McClurg,H.Hojjat,N.Foster,and P.Cemny,"Event-driven network programming,"in Proc.of PLDI,2016,pp.369-385. write algorithmic,data-plane agnostic network policy for SDN [15]M.T.Arashloo,Y.Koral,M.Greenberg.J.Rexford,and D.Walker, programming.It then applies static taint analysis techniques to "Snap:Stateful network-wide abstractions for packet processing."in automatically infers compact and efficient multi-table pipelines Proc.of SIGCOMM.2016,pp.29-43. [16]"P4 runtime,"https://p4.org/p4-runtime/,accessed:2017-12-27. from the high-level network policy.It also introduces a novelTABLE III THE QUALITY OF PIPELINE profile # tables # entries n = 10 n = 20 n = 30 n = 40 n = 50 n = 100 single 1 121 441 961 1681 2601 10201 multi-nonopt-dep 5 43 63 83 103 123 223 multi-opt-nondep 3 120 232 350 460 570 1120 multi-opt-dep 3 40 60 80 100 120 220 TABLE IV PERFORMANCE: PINGALL TIME profile pingall time (s) n=10 n=20 n=30 n=40 n=50 n=100 single 0.60 6.1 28 78 181 2831 ovsk 0.10 0.60 1.3 2.4 3.7 15 multi-nonopt-dep 0.20 0.78 1.8 3.1 4.9 20 multi-opt-nondep 0.54 2.1 4.5 7.8 12 47 multi-opt-dep 0.19 0.76 1.7 3.1 4.8 19 TABLE V PERFORMANCE: NUMBER OF PACKETIN profile # packet in n=10 n=20 n=30 n=40 n=50 n=100 single 117 423 939 1643 2549 10099 multi-nonopt-dep 46 74 79 92 111 223 multi-opt-nondep 124 258 351 452 562 1134 multi-opt-dep 47 72 80 93 112 221 number of table entries. Also, unlike POMP that generates flow table entries reactively at runtime, Magellan generates table entries proactively by enumerating all possible executions of the network policy before its deployment. Moreover, Magellan provides no mechanisms for protocol oblivious programming. Concurrent NetCore [13] extends NetCore [7] to support multi-tables, but it requires the programmer to manually define the layout of flow tables instead of generating it automatically from high-level policies as we do in POMP. Stateful NetKAT [14] and SNAP [15] extend NetKAT [6] and NetCore [7] respectively to support persistent states in emerging SDN data plane. They are for quite different purposes (to take advantage of the switch-local computation power) and do not handle multi-table pipelines. P4 Runtime [16] provides a way for control plane to control P4 switches. The programmer can use P4 Runtime APIs to install flow table entries at runtime. In POMP, the programmer doesn’t use P4 Runtime APIs. The switch abstraction layer (see Fig. 1) accepts entries generated by the runtime of POMP, then calls P4 Runtime APIs to install entries for P4 switches. VIII. CONCLUSION POMP is a general purpose SDN programming environment supporting both protocol oblivious programming and auto￾matic multi-table pipelining. It extends the C language with a set of APIs and a runtime system to allow programmers to write algorithmic, data-plane agnostic network policy for SDN programming. It then applies static taint analysis techniques to automatically infers compact and efficient multi-table pipelines from the high-level network policy. It also introduces a novel notion of dependent labels to refine the label sets generated by the taint analysis. The dependent labels are used at the runtime for flow table entry generation to further reduce the number of table entries. The evaluation results show that POMP generates high-quality forwarding pipelines. POMP pipeline for learning switches uses up to 47x fewer number of table entries, and is up to 137x faster than single table. Note that, although the learning switches example is used throughout the paper to demonstrate the key ideas, POMP is a general purpose language for SDN programming. In addition to these APIs used in learning switches, there are more provided, including those for environment management. The set of POMP APIs is as expressive as those in Maple. REFERENCES [1] P. Bosshart, D. Daly, G. Gibb, M. Izzard, N. McKeown, J. Rexford, C. Schlesinger, D. Talayco, A. Vahdat, G. Varghese, and D. Walker, “P4: Programming protocol-independent packet processors,” SIGCOMM Comput. Commun. Rev., vol. 44, no. 3, pp. 87–95, Jul. 2014. [2] H. Song, “Protocol-oblivious forwarding: Unleash the power of SDN through a future-proof forwarding plane,” in Proc. of HotSDN, 2013, pp. 127–132. [3] P. Bosshart, G. Gibb, H.-S. Kim, G. Varghese, N. McKeown, M. Iz￾zard, F. Mujica, and M. Horowitz, “Forwarding metamorphosis: Fast programmable match-action processing in hardware for SDN,” in Proc. of SIGCOMM, 2013, pp. 99–110. [4] M. Shahbaz, S. Choi, B. Pfaff, C. Kim, N. Feamster, N. McKeown, and J. Rexford, “Pisces: A programmable, protocol-independent software switch,” in Proc. of SIGCOMM, 2016, pp. 525–538. [5] A. Voellmy, J. Wang, Y. R. Yang, B. Ford, and P. Hudak, “Maple: Simplifying SDN programming using algorithmic policies,” in Proc. of SIGCOMM, 2013, pp. 87–98. [6] C. J. Anderson, N. Foster, A. Guha, J.-B. Jeannin, D. Kozen, C. Schlesinger, and D. Walker, “Netkat: Semantic foundations for networks,” in Proc. of POPL, 2014, pp. 113–126. [7] C. Monsanto, N. Foster, R. Harrison, and D. Walker, “A compiler and run-time system for network programming languages,” in Proc. of POPL, 2012, pp. 217–230. [8] S. Hunt and D. Sands, “On flow-sensitive security types,” in Prof. of POPL, 2006, pp. 79–90. [9] B. Lantz, B. Heller, and N. McKeown, “A network in a laptop: Rapid prototyping for software-defined networks,” in Proc. of Hotnets-IX, 2010, pp. 19:1–19:6. [10] “P4 behavioral model,” https://github.com/p4lang/behavioral-model, ac￾cessed: 2017-07-31. [11] “Open vSwitch,” http://openvswitch.org/, accessed: 2017-07-31. [12] A. Voellmy, S. Chen, X. Wang, and Y. R. Yang, “Magellan: Generating multi-table datapath from datapath oblivious algorithmic SDN policies,” in Proc. of SIGCOMM, 2016, pp. 593–594. [13] C. Schlesinger, M. Greenberg, and D. Walker, “Concurrent netcore: From policies to pipelines,” in Proc. of ICFP, 2014, pp. 11–24. [14] J. McClurg, H. Hojjat, N. Foster, and P. Cern ˇ y, “Event-driven network ´ programming,” in Proc. of PLDI, 2016, pp. 369–385. [15] M. T. Arashloo, Y. Koral, M. Greenberg, J. Rexford, and D. Walker, “Snap: Stateful network-wide abstractions for packet processing,” in Proc. of SIGCOMM, 2016, pp. 29–43. [16] “P4 runtime,” https://p4.org/p4-runtime/, accessed: 2017-12-27