[en] Packet forwarding in Software-Defined Networks
(SDN) relies on a centralised network controller which enforces
network policies expressed as forwarding rules. Rules
are deployed as sets of entries into network device tables.
With heterogeneous devices, deployment is strongly bounded
by the respective table constraints (size, lookup time, etc.) and
forwarding pipelines. Hence, minimising the overall number of
entries is paramount in reducing resource consumption and
speeding up the search. Moreover, since multiple control plane
applications can deploy own rules, conflicts may occur. To avoid
those and ensure overall correctness, a rule validation mechanism
is required. Here, we present a compilation mechanism for rules
of diverging origins that minimises the number of entries. Since
it exploits the semantics of rules and entries, our compiler fits a
heterogeneous landscape of network devices. We evaluated compiler
implementations on both software and hardware switches
using a realistic testbed. Experimental results show a reduction
in both produced table entries and forwarding delay.
Disciplines :
Computer science
Author, co-author :
Hommes, Stefan ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT)
Valtchev, Petko; Université du Québec à Montréal
Blaiech, Khalil; Université du Québec à Montréal
Hamadi, Salaheddine; Université du Québec à Montréal
Cherkaoui, Omar; Université du Québec à Montréal
State, Radu ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT)
External co-authors :
yes
Language :
English
Title :
Optimising Packet Forwarding in Multi-Tenant Networks using Rule Compilation
Publication date :
November 2017
Event name :
International Symposium on Network Computing and Applications (NCA 2017)
Event place :
Cambridge, MA, United States
Event date :
from 30-10-2017 to 01-11-2017
Audience :
International
Main work title :
Optimising Packet Forwarding in Multi-Tenant Networks using Rule Compilation
N. McKeown, T. Anderson, H. Balakrishnan, G. Parulkar, L. Peterson, J. Rexford, S. Shenker, and J. Turner, "Openflow: Enabling innovation in campus networks," SIGCOMM Comput. Commun. Rev., vol. 38, no. 2, pp. 69-74, Mar. 2008. [Online]. Available: http://doi.acm.org/10.1145/1355734.1355746
[Online]. Available: http://www.openvswitch.org
R. Sherwood, G. Gibb, K.-K. Yap, G. Appenzeller, M. Casado, N. McKeown, and G. Parulkar, "FlowVisor: A network virtualization layer," Deutsche Telekom Inc. R&D Lab, Stanford University, Nicira Networks, Tech. Rep., 2009. [Online]. Available: http://archive.openflow. org/downloads/technicalreports/openflow-tr-2009-1-flowvisor.pdf
A. Al-Shabibi, M. De Leenheer, M. Gerola, A. Koshibe, G. Parulkar, E. Salvadori, and B. Snow, "OpenVirteX: Make your virtual SDNs programmable," in Proc. of the 3rd WS on Hot Topics in SDN, ser. HotSDN '14. ACM, 2014, pp. 25-30. [Online]. Available: http://doi.acm.org/10.1145/2620728.2620741
X. Jin, J. Gossels, J. Rexford, and D. Walker, "Covisor: A compositional hypervisor for software-defined networks," in Proceedings of the 12th USENIX Conference on Networked Systems Design and Implementation, ser. NSDI'15. Berkeley, CA, USA: USENIX Association, 2015, pp. 87-101. [Online]. Available: http://dl.acm.org/citation.cfm?id=2789770. 2789777
A. Blenk, A. Basta, M. Reisslein, and W. Kellerer, "Survey on network virtualization hypervisors for software defined networking," IEEE Communications Surveys Tutorials, vol. 18, no. 1, pp. 655-685, Firstquarter 2016.
J. C. Mogul, A. AuYoung, S. Banerjee, L. Popa, J. Lee, J. Mudigonda, P. Sharma, and Y. Turner, "Corybantic: Towards the modular composition of SDN control programs," in Proc. of the 12th ACM Workshop on Hot Topics in Networks, ser. HotNets-XII. ACM, 2013, pp. 1:1-1:7. [Online]. Available: http://doi.acm.org/10.1145/2535771. 2535795
T. Koponen, M. Casado, N. Gude, J. Stribling, L. Poutievski, M. Zhu, R. Ramanathan, Y. Iwata, H. Inoue, T. Hama, and S. Shenker, "Onix: A distributed control platform for large-scale production networks," in Proc. of the 9th USENIX Conf. on Operating Systems Design and Implem., ser. OSDI'10. USENIX Association, 2010, pp. 351-364.Online. Available: http://dl.acm.org/citation.cfm?id=1924943.1924968
B. Yan, Y. Xu, H. Xing, K. Xi, and H. J. Chao, "Cab: A reactive wildcard rule caching system for software-defined networks," in Proc. of the 3rd WS on Hot Topics in SDN, ser. HotSDN '14. ACM, 2014, pp. 163-168. Online . Available: http://doi.acm.org/10.1145/2620728.2620732
N. Katta, O. Alipourfard, J. Rexford, and D. Walker, "Infinite cacheflow in software-defined networks," in Proceedings of the Third Workshop on Hot Topics in Software Defined Networking, ser. HotSDN '14. New York, NY, USA: ACM, 2014, pp. 175-180. [Online]. Available: http://doi.acm.org/10.1145/2620728.2620734
S. Hamadi, K. Blaiech, P. Valtchev, O. Cherkaoui, and R. State, "Compiling packet forwarding rules for switch pipelined architecture," in IEEE INFOCOM 2016-The 35th Annual IEEE International Conference on Computer Communications, April 2016, pp. 1-9.
A. X. Liu, C. R. Meiners, and E. Torng, "Tcam razor: A systematic approach towards minimizing packet classifiers in tcams," IEEE/ACM Transactions on Networking, vol. 18, no. 2, pp. 490-500, April 2010.
C. R. Meiners, A. X. Liu, and E. Torng, "Bit weaving: A non-prefix approach to compressing packet classifiers in tcams," IEEE/ACM Trans. Netw., vol. 20, no. 2, pp. 488-500, Apr. 2012. [Online]. Available: http://dx.doi.org/10.1109/TNET.2011.2165323
Y. Kanizo, D. Hay, and I. Keslassy, "Palette: Distributing tables in software-defined networks," in 2013 Proc. IEEE INFOCOM, 2013, pp. 545-549.
K. Kogan, S. Nikolenko, O. Rottenstreich, W. Culhane, and P. Eugster, "Sax-pac (scalable and expressive packet classification)," in Proceedings of the 2014 ACM Conference on SIGCOMM, ser. SIGCOMM '14. New York, NY, USA: ACM, 2014, pp. 15-26. [Online]. Available: http://doi.acm.org/10.1145/2619239.2626294
C. R. Meiners, A. X. Liu, E. Torng, and J. Patel, "Split: Optimizing space, power, and throughput for tcam-based classification," in Proceedings of the 2011 ACM/IEEE Seventh Symposium on Architectures for Networking and Communications Systems, ser. ANCS '11. Washington, DC, USA: IEEE Computer Society, 2011, pp. 200-210. [Online]. Available: http://dx.doi.org/10.1109/ANCS.2011.36
K. Blaiech, S. Hamadi, S. Hommes, P. Valtchev, O. Cherkaoui, and R. State, "Rule compilation in multi-tenant networks," in Proceedings of the Symposium on Architectures for Networking and Communications Systems, ser. ANCS '17. Piscataway, NJ, USA: IEEE Press, 2017, pp. 97-98. [Online]. Available: https://doi.org/10.1109/ANCS.2017.34
The Open Networking Foundation, "OpenFlow Switch Specification," Jun. 2012.
S. Natarajan, X. Huang, and T. Wolf, "Efficient conflict detection in flow-based virtualized networks," in 2012 International Conference on Computing, Networking and Communications (ICNC), Jan 2012, pp. 690-696.
M. A. Ruiz-Sanchez, E. W. Biersack, and W. Dabbous, "Survey and taxonomy of ip address lookup algorithms," IEEE Network, vol. 15, no. 2, pp. 8-23, Mar 2001.
B. Ganter and R. Wille, Formal concept analysis: mathematical foundations. Springer, 1999.
B. A. Davey and H. A. Priestley, Introduction to Lattices and Order, 2nd ed. Cambridge University Press, 2002.
K. Denecke et al., Galois connections and applications. Springer Science & Business Media, 2013, vol. 565.
L. Szathmary et al., "Constructing iceberg lattices from frequent closures using generators," in Discovery Science. Springer, 2008, pp. 136-147.
L. Szathmary, P. Valtchev, A. Napoli, and R. Godin, Efficient Vertical Mining of Frequent Closures and Generators. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009, pp. 393-404. [Online]. Available: http://dx.doi.org/10.1007/978-3-642-03915-7-34
