OpenFlow交换机流表溢出问题的缓解机制
|
摘要
在新兴的软件定义网络(Software Defined Networking,SDN)、OpenFlow交换机中,为满足OpenFlow协议宽匹配域的需求,SDN交换设备需要更大的查找表存储容量.当流表溢出时,将导致控制报文数目爆炸性增长、数据包传输时延增大等危害网络正常运行的后果.然而考虑成本因素,高速查找表容量不可能无限增加.即使单纯地增加流表容量,并不能使溢出的概率降低为零,且极不经济.本文分析了网络流量的特征,提出了一种流表共享方法(Flow Table Sharing,FTS),针对流表溢出现象带来的危害,完善了Table-Miss处理机制,有效遏制了由于流表溢出而引发的危害网络正常运行的情况.相比目前的Table-Miss处理方式,FTS对流表溢出情况下控制消息数量和RTT时间的优化都达到两个数量级.此外,该文针对流表扩散方法设计了简单高效的基于OpenFlow组表的随机路由选择算法,系统结构实施简单,可以方便地降级为现行的通用Table-Miss处理模式.
Software Defined Networking is an emerging network architecture,which decouples the control plane from the data plane and operates the global network with elaborate abstraction.The flow table plays an important role in an OpenFlow Switch(OFS)and is the key resource to support the SDN/OpenFlow abstraction.To provide wire-speed processing,fast memory(e.g.,TCAM,QDR,SRAM)is utilized to form the flow table.Unfortunately,the development of such kind of fast memories is far behind the hungry requirement on its usage,especially for the TCAM.As a result,the flow table installed in OFS has tremendous risk to be overflow,possibly leading to large quantity of Packet-In/Packet-Out messages between OFS and controller.Generally,an incoming packet from a flow is processed according to the action specified in the according flow entry in the flow table(s).If no entry is matched in the flow table,apacket-in message querying how to process the packet will be sent to the controller from the switch.If the number of active flows always touches the maximum number of entries in the flow table,the table-miss events are not avoidable.So that at first we investigate how to mitigate the overhead when occurring table-miss events based on the phenomenon of uneven flow table distribution.The basic idea is to distributethe packets facing table-miss event in heavily loaded switch to other lightly loaded switches instead of triggering packet-in messages always in hot switches.The conceptual simplicity of FTS idea hides two significant challenges.(1)How to select a right port randomly by SDN switch.(2)How to make this progress "pipeline-able"in a general SDN switch without changing its Hardware.The new mechanism proposed in this paper to handle the Table-Miss event is named Flow Table Sharing(FTS).The evaluations have demonstrated that FTS reduces both control messages quantity and RTT time by two orders of magnitude compared to current state-of-the-art OpenFlow Table-Miss handler.We first build a switch in MININET(test environment),and measure the number of control messages generated by setting up a new flow transfer(TCP,UDP)when the flow table of the switch is overflow,as well as the packet loss rate and the average delay.Then,we evaluate the flow table demand in the optimal way that all switches have enough flow table resources and set this result as the control group.Then,on the one hand,we evaluate the additional flow table demand which is required by rebuilding the interrupted flow,when the FTS try to fix the problem caused by the overflow.On the other hand,we evaluate the total flow table consumption which is required by building the new transmission for the first time,after the overflow happened.Even during the flow table overflow period,denial of service for new flows does not happen.We designed an external user switch-computed Group Table select algorithm and show its validity and fastness.It is easy to implement,easy to control and the current state-of-the-art OpenFlow Table-Miss handler is a special case of FTS.
Software Defined Networking is an emerging network architecture,which decouples the control plane from the data plane and operates the global network with elaborate abstraction.The flow table plays an important role in an OpenFlow Switch(OFS)and is the key resource to support the SDN/OpenFlow abstraction.To provide wire-speed processing,fast memory(e.g.,TCAM,QDR,SRAM)is utilized to form the flow table.Unfortunately,the development of such kind of fast memories is far behind the hungry requirement on its usage,especially for the TCAM.As a result,the flow table installed in OFS has tremendous risk to be overflow,possibly leading to large quantity of Packet-In/Packet-Out messages between OFS and controller.Generally,an incoming packet from a flow is processed according to the action specified in the according flow entry in the flow table(s).If no entry is matched in the flow table,apacket-in message querying how to process the packet will be sent to the controller from the switch.If the number of active flows always touches the maximum number of entries in the flow table,the table-miss events are not avoidable.So that at first we investigate how to mitigate the overhead when occurring table-miss events based on the phenomenon of uneven flow table distribution.The basic idea is to distributethe packets facing table-miss event in heavily loaded switch to other lightly loaded switches instead of triggering packet-in messages always in hot switches.The conceptual simplicity of FTS idea hides two significant challenges.(1)How to select a right port randomly by SDN switch.(2)How to make this progress "pipeline-able"in a general SDN switch without changing its Hardware.The new mechanism proposed in this paper to handle the Table-Miss event is named Flow Table Sharing(FTS).The evaluations have demonstrated that FTS reduces both control messages quantity and RTT time by two orders of magnitude compared to current state-of-the-art OpenFlow Table-Miss handler.We first build a switch in MININET(test environment),and measure the number of control messages generated by setting up a new flow transfer(TCP,UDP)when the flow table of the switch is overflow,as well as the packet loss rate and the average delay.Then,we evaluate the flow table demand in the optimal way that all switches have enough flow table resources and set this result as the control group.Then,on the one hand,we evaluate the additional flow table demand which is required by rebuilding the interrupted flow,when the FTS try to fix the problem caused by the overflow.On the other hand,we evaluate the total flow table consumption which is required by building the new transmission for the first time,after the overflow happened.Even during the flow table overflow period,denial of service for new flows does not happen.We designed an external user switch-computed Group Table select algorithm and show its validity and fastness.It is easy to implement,easy to control and the current state-of-the-art OpenFlow Table-Miss handler is a special case of FTS.
引文
[1]ONF Market Education Committee.Software-Defined Networking:The New Norm for Networks.Palo Alto,USA:Open Networking Foundation,2012
[2]McKeown N,et al.OpenFlow:Enabling innovation in campus networks.ACM SIGCOMM Computer Communication Review,2008,38(2):69-74
[3]Heller B.OpenFlow switch specification v1.5.0.Palo Alto,USA:Open Networking Foundation,2014
[4]Shahbaz M,Choi S,Pfaff B,et al.Pisces:A programmable,protocol-independent software switch//Proceedings of the2016 Conference on ACM SIGCOMM 2016 Conference.Florianopolis,Brazil,2016:525-538
[5]Katta N,Alipourfard O,Rexford J,et al.Infinite CacheFlow in software-defined networks//Proceedings of the 3rd Workshop on Hot Topics in Software Defined Networking.Chicago,USA,2014:175-180
[6]Qiao S,Hu C,Guan X,et al.Taming the flow table overflow in OpenFlow switch//Proceedings of the 2016Conference on ACM SIGCOMM 2016 Conference.Florianopolis,Brazil,2016:591-592
[7]Ku'zniar M,Pere2íni P,Kosti'c D.What you need to know about SDN flow tables//Proceedings of the International Conference on Passive and Active Network Measurement(ICPACM 2015).New York,USA,2015:347-359
[8]Allesina S,Bondavalli C.WAND:An ecological network analysis user-friendly tool.Environmental Modelling&Software,2004,19(4):337-340
[9]Kannan K,Subhasis B.Compact TCAM:Flow entry compaction in TCAM for power aware SDN//Proceedings of the Distributed Computing and Networking(DCN 2013).Berlin,Germany,2013:439-444
[10]Meiners C R,Liu A X,Torng E.Bit weaving:A non-prefix approach to compressing packet classifiers in TCAMs.Transactions on Networking(ToN),2012,20(2):488-500
[11]Kannan K,Subhasis B.FlowMaster:Early eviction of dead flow on SDN switches//Proceedings of the Distributed Computing and Networking(DCN 2014).Berlin,Germany,2014:484-498
[12]Li L E,Mao Z M,Rexford J.Toward software-defined cellular networks//Proceedings of the Conference on European Workshop Software Defined Networking(EWSDN).Darmstadt,Germany,2012:7-12
[13]Benson T,Anand A,Akella A,et al.MicroTE:Fine grained traffic engineering for data centers//Proceedings of the 7th Conference on Emerging Networking Experiments and Technologies.New York,USA,2011:8
[14]Cerrato I,Annarumma M,Risso F.Supporting fine-grained network functions through Intel DPDK//Proceedings of the Conference on European Workshop Software Defined Networking(EWSDN).London,UK,2014:1-6
[15]Jiang W,Wang Q,Prasanna V K.Beyond TCAMs:An SRAM-based parallel multi-pipeline architecture for terabit IP lookup//Proceedings of the 27th Conference on Computer Communications.Phoenix,USA,2008:1786-1794
[16]Jain S,Kumar A,Mandal S,et al.B4:Experience with a globally-deployed software defined wan.ACM SIGCOMMComputer Communication Review,2013,43(4):3-14
[17]Bosshart P,et al.P4:Programming protocol-independent packet processors.ACM SIGCOMM Computer Communication Review,2014,44(3):87-95
[18]Curtis A R,et al.DevoFlow:Scaling flow management for high-performance networks.ACM SIGCOMM Computer Communication Review,2011,41(4):254-265
[19]Koponen T,et al.Onix:A distributed control platform for large-scale production networks.Operating Systems Design and Implementation,2010,10:1-6
[20]Yu Minlan,et al.Scalable flow-based networking with difane.ACM SIGCOMM Computer Communication Review,2011,41(4):351-362
[21]Katta N,et al.Infinite CacheFlow in software-defined networks//Proceedings of the 3rd Workshop on Hot Topics in Software Defined Networking(HOTSDN 2014).Chicago,USA,2014:175-180
[22]Lantz B,Heller B,McKeown N.A network in a laptop:Rapid prototyping for software-defined networks//Proceedings of the 9th ACM SIGCOMM Workshop on Hot Topics in Networks.New Delhi,India,2010:19-24
[23]Qiao S,Xu C,Xie L,et al.Network recorder and player:Fpga-based network traffic capture and replay//Proceedings of the International Conference on IEEE Field-Programmable Technology.Shanghai,China,2014:342-345
[24]Liang Yong-Sheng,Zhang Ji-Hong,Zhang Nai-Tong.Measurement and analysis of forwarding delay in Ethernet architecture within tolerances of the IEEE specifications.Acta Electronica Sinica,2008,36(1):46-50(in Chinese)(梁永生,张基宏,张乃通.IEEE标准容限内以太网转发时延的测试与分析.电子学报,2008,36(1):46-50)
[25]Kleinrock L.Queueing Systems Volume 1:Theory.New York,USA:Wiley,1975
[26]Bolch G,et al.Single station queueing systems//Proceedings of the Queueing Networks and Markov Chains Modeling and Performance Evaluation with Computer Science(MPECS 1998)Applications(1998).New York,USA,1998:209-262
[27]Barbeau M,Kranakis E.Principles of Ad-Hoc Networking.New York,USA:John Wiley&Sons,2007
(1)The CAIDA UCSD Macroscopic Skitter Topology Dataset www.caida.org/tools/measurements/skitter
(1)https://github.com/qiaosiyi/test_overflow_random_foward
[2]McKeown N,et al.OpenFlow:Enabling innovation in campus networks.ACM SIGCOMM Computer Communication Review,2008,38(2):69-74
[3]Heller B.OpenFlow switch specification v1.5.0.Palo Alto,USA:Open Networking Foundation,2014
[4]Shahbaz M,Choi S,Pfaff B,et al.Pisces:A programmable,protocol-independent software switch//Proceedings of the2016 Conference on ACM SIGCOMM 2016 Conference.Florianopolis,Brazil,2016:525-538
[5]Katta N,Alipourfard O,Rexford J,et al.Infinite CacheFlow in software-defined networks//Proceedings of the 3rd Workshop on Hot Topics in Software Defined Networking.Chicago,USA,2014:175-180
[6]Qiao S,Hu C,Guan X,et al.Taming the flow table overflow in OpenFlow switch//Proceedings of the 2016Conference on ACM SIGCOMM 2016 Conference.Florianopolis,Brazil,2016:591-592
[7]Ku'zniar M,Pere2íni P,Kosti'c D.What you need to know about SDN flow tables//Proceedings of the International Conference on Passive and Active Network Measurement(ICPACM 2015).New York,USA,2015:347-359
[8]Allesina S,Bondavalli C.WAND:An ecological network analysis user-friendly tool.Environmental Modelling&Software,2004,19(4):337-340
[9]Kannan K,Subhasis B.Compact TCAM:Flow entry compaction in TCAM for power aware SDN//Proceedings of the Distributed Computing and Networking(DCN 2013).Berlin,Germany,2013:439-444
[10]Meiners C R,Liu A X,Torng E.Bit weaving:A non-prefix approach to compressing packet classifiers in TCAMs.Transactions on Networking(ToN),2012,20(2):488-500
[11]Kannan K,Subhasis B.FlowMaster:Early eviction of dead flow on SDN switches//Proceedings of the Distributed Computing and Networking(DCN 2014).Berlin,Germany,2014:484-498
[12]Li L E,Mao Z M,Rexford J.Toward software-defined cellular networks//Proceedings of the Conference on European Workshop Software Defined Networking(EWSDN).Darmstadt,Germany,2012:7-12
[13]Benson T,Anand A,Akella A,et al.MicroTE:Fine grained traffic engineering for data centers//Proceedings of the 7th Conference on Emerging Networking Experiments and Technologies.New York,USA,2011:8
[14]Cerrato I,Annarumma M,Risso F.Supporting fine-grained network functions through Intel DPDK//Proceedings of the Conference on European Workshop Software Defined Networking(EWSDN).London,UK,2014:1-6
[15]Jiang W,Wang Q,Prasanna V K.Beyond TCAMs:An SRAM-based parallel multi-pipeline architecture for terabit IP lookup//Proceedings of the 27th Conference on Computer Communications.Phoenix,USA,2008:1786-1794
[16]Jain S,Kumar A,Mandal S,et al.B4:Experience with a globally-deployed software defined wan.ACM SIGCOMMComputer Communication Review,2013,43(4):3-14
[17]Bosshart P,et al.P4:Programming protocol-independent packet processors.ACM SIGCOMM Computer Communication Review,2014,44(3):87-95
[18]Curtis A R,et al.DevoFlow:Scaling flow management for high-performance networks.ACM SIGCOMM Computer Communication Review,2011,41(4):254-265
[19]Koponen T,et al.Onix:A distributed control platform for large-scale production networks.Operating Systems Design and Implementation,2010,10:1-6
[20]Yu Minlan,et al.Scalable flow-based networking with difane.ACM SIGCOMM Computer Communication Review,2011,41(4):351-362
[21]Katta N,et al.Infinite CacheFlow in software-defined networks//Proceedings of the 3rd Workshop on Hot Topics in Software Defined Networking(HOTSDN 2014).Chicago,USA,2014:175-180
[22]Lantz B,Heller B,McKeown N.A network in a laptop:Rapid prototyping for software-defined networks//Proceedings of the 9th ACM SIGCOMM Workshop on Hot Topics in Networks.New Delhi,India,2010:19-24
[23]Qiao S,Xu C,Xie L,et al.Network recorder and player:Fpga-based network traffic capture and replay//Proceedings of the International Conference on IEEE Field-Programmable Technology.Shanghai,China,2014:342-345
[24]Liang Yong-Sheng,Zhang Ji-Hong,Zhang Nai-Tong.Measurement and analysis of forwarding delay in Ethernet architecture within tolerances of the IEEE specifications.Acta Electronica Sinica,2008,36(1):46-50(in Chinese)(梁永生,张基宏,张乃通.IEEE标准容限内以太网转发时延的测试与分析.电子学报,2008,36(1):46-50)
[25]Kleinrock L.Queueing Systems Volume 1:Theory.New York,USA:Wiley,1975
[26]Bolch G,et al.Single station queueing systems//Proceedings of the Queueing Networks and Markov Chains Modeling and Performance Evaluation with Computer Science(MPECS 1998)Applications(1998).New York,USA,1998:209-262
[27]Barbeau M,Kranakis E.Principles of Ad-Hoc Networking.New York,USA:John Wiley&Sons,2007
(1)The CAIDA UCSD Macroscopic Skitter Topology Dataset www.caida.org/tools/measurements/skitter
(1)https://github.com/qiaosiyi/test_overflow_random_foward