AIRCC PUBLISHING CORPORATION
Allocation of Virtual Firewall Functions in Nfv-Based Networks With Minimum Network Cost
Department of Computer and Information Science, Seikei University, Japan
NFV-based network implements a variety of network functions with software on general-purpose servers and this allows the network operator to select any capacity and location of network functions without any physical constraints. It is essential for economical NFV-based network design to determine the place where each network function should be located in the network and what its capacity should be. The authors proposed an algorithm of virtual routing function allocation in the NFV-based network for minimizing the network cost and provided effective allocation guidelines for virtual routing functions.
This paper proposes the deployment algorithm of virtual firewall function in addition to virtual routing function for minimizing the network cost. Our evaluation results have revealed the following: (1) Installing a packet filtering function, which is a part of the firewall function, in the sending-side area additionally can reduce wasteful transit bandwidth and routing processing and thereby reduce the network cost. (2) The greater the number of packets filtered by packet filtering function in the sending-side area, the more the reduction of network cost is increased. (3) The greater the bandwidth cost relative to the routing function cost, the greater the effect of statistical multiplexing on reducing the network cost. (4) The proposed algorithm would be approaching about 95% of the deployment with the optimal solution.
NFV, resource allocation, the virtual routing function, minimum total network cost
Virtualization is a technique to make a single physical entity appear multiple logical entities or, conversely, to make multiple physical entities look like a single logical entity. Network functions virtualization (NFV) - represents an application of virtualization technology to network functions. It enables a piece of software that can conventionally operate only on a specific piece of hardware to operate on a general-purpose server, making it possible to build a network quickly and to operate it in a flexible manner. It has already been commercially introduced in public mobile networks .
In an NFV-based network, a variety of network functions is implemented in software on general-purpose servers. This makes it possible to select the capacity and location of each function without any physical constraints. It is essential to optimize the location and capacity of each network function for economical NFV-based network design. A new deployment method should be required, as the existing deployment method that has limitations on capacity and deployment location cannot be used as it is. As a deployment method for NFV-based network, there is a method of efficiently allocating already installed physical resources to the virtual network function as a short-term perspective. This has been studied as VNE (Virtual Network Assignment) problems . In addition, the research from a medium-term to long-term perspective is required to decide the optimal physical resource capacity and deployment location, when expanding the network or adding new network functions. Many types of researches have been carried out on the former, but less research has not been done on the latter.
From a medium-term to long-term perspective, the authors previously focused on the routing function, which is an important network function, and proposed the algorithm for allocating virtual routing functions in a way that minimizes the network cost or the network power consumption . The authors evaluated the proposed algorithm on a ladder model that simulates the shape of Japan, and developed multiple effective functional allocation guidelines. The guidelines show the trend for the capacity required for each network function and the optimal location of each function, which depend on the routing function cost relative to the bandwidth cost and the inter-area traffic distribution. The authors also clarified the influence of quality conditions such as the maximum allowable network delay on its deployment guidelines . These guidelines provide network operators with critical information needed in designing and building an NFV-based network. For example, whether the total network cost can be reduced by 2% or by 20% can significantly affect the business decision. In an example presented in reference , it was shown that if the number of areas that the packets are allowed to pass through is up to three, the network cost rises by about 40%, and the service fee would go up accordingly. If the network operator desires to limit a rise in the service fee to 20% or less, it is necessary to allow packets to pass through up to four areas in the above example. In this way, a quantitative evaluation can provide network design guidelines.
Assuming the deployment of firewall function in addition to routing function, this paper proposes the joint deployment algorithm of virtual routing function and virtual firewall function to minimize the NFV-based network cost and derives effective allocation guidelines for two virtual network functions.
The rest of this paper is organized as follows. Section 2 explains related works. Section 3 proposes the joint deployment algorithm of virtual routing function and virtual firewall function to minimize the NFV-based network cost. In particular, it is proposed to place an additional packet filtering function, which is a part of the firewall function, in the sending-side area. Section 4 evaluates the proposed joint deployment algorithm and proposes the allocation guidelines for virtual routing function and the virtual firewall function. Finally, Section 5 provides conclusion. This paper is an extension of the study in Reference .
2. Related Works
One of the related studies is the VNE (virtual network resource allocation) problem, which is a problem of allocating virtual nodes and links to a physical network efficiently , , . Reference  evaluates the allocation of multiple VNFs. Reference  proposes a functional allocation assuming a hybrid arrangement in which dedicated hardware and virtual functions are used. References  and  proposes dynamic resource allocation and scheduling. Reference  evaluates the virtualization of S-GW (serving GW) and P-GW (packet data network GW) functions in a mobile network in terms of network load and network delay. Based on an evaluation made on a network that simulates the network structure of the U.S.A., it shows that four data centers that completely virtualize these GWs are required. Reference  proposes a method for solving the virtual DPI allocation problem with minimum cost.
The authors proposed a resource allocation method in a cloud environment in which computing power and access bandwidths are allocated simultaneously -. The key point of this method is how to pack as many requirements (simultaneously requiring two different types of the resource of computing power and access bandwidths with service quality being not uniform) as possible into multiple sets of computing power and bandwidths.
Most of the above evaluations deal with how to pack (allocate) virtual network functions to finite physical network resources efficiently. In contrast, reference  and this paper try to develop allocation guidelines that indicate how much capacity is required for each virtual network function and where each function should be allocated in the network, both of which depend on the relative costs of the routing function and the bandwidth and the inter-area traffic distribution. These guidelines should be required for network carriers when they design and build an NFV-based network.
3. Allocation Algorithm Of Routing And Firewall Functions With Minimum Network Cost
3.1 Conditions for Firewall Function Allocation and Proposed Allocation Algorithm
As shown in Figure 1, network functions can be classified into three categories : those that output a smaller volume of traffic than the volume of their input traffic, those that output volume traffic equal to the volume of their input traffic, and those that output a larger
Figure 1. Network functions classified by input and output changes in traffic volume
Volume of traffic than the volume of their input traffic. The firewall function is one of the important network functions and belongs to the first category. It is necessary to deal with unauthorized intrusion prevention in accordance with the situation and condition. Therefore, firewall functions are generally placed on the receiving-side, not on the sending-side. Unlike the routing function, it is difficult to assume that the firewall function of one area will be integrated into that of another area. Thus, it is proposed that the firewall function is left deployed on the receiving-side area and only the packet filtering function, which is a part of its function, is placed in the sending-side area additionally, in order to reduce the network cost. As the packet filtering function filters packets based on only each packet’s IP address and port number, and is irrespective of the particular traffic situation, it is easy to place it to another area.
Figure 2 illustrates an example of placing an additional packet filtering function in the sending-side area, assuming that a routing function is allocated in every area. This packet filtering function is the same as that in the firewall function which is placed in the receiving-side area. If each packet filtering function removes 30% of the traffic (100pps in Figure 2) generated in the sending-side area, it reduces the volume of traffic that is sent to the receiving-side area by 30%. As a result, the bandwidth cost for carrying 60*L bps (L: packet length in bits), the routing function cost for handling 90pps, and the firewall function cost for handling 30pps are respectively saved compared to the case where no packet filtering function is placed in the sending-side area. That is, the additional packet filtering function will be placed only when the total cost reduction is greater than the cost of the additional packet filtering function for handling 100pps.
Figure 2. Example of the effect of additional packet filtening function deployment
3.2 Additional Deployment Judgment on Packet Filtering Function
Although the additional deployment (not moving) judgment on the packet filtering function could be performed on each sending-side area, it is assumed in this study that all target sending-side areas are collectively carried out. Here, the target sending-side area is an area where the traffic is generated for the receiving-side area. The following judgment is performed independently for each receiving-side area from an area with a small area number. If the network cost can be reduced when the additional deployment is performed only for the packet filtering function in all target sending-side areas, additional deployment is made to all target sending-side areas. The capacity of the packet filtering function additionally deployed is determined as the amount of traffic towards the receiving-side area from each sending-side area. If the network cost cannot be reduced, it is not additionally deployed. Figure 3 shows the additional deployment judgment flow of packet filtering function.
Figure 3. Additional deployment judgement flow of packet filtering function
3.3 Guidelines for Routing Function Allocation
Guidelines for allocating routing functions need to be studied for each different traffic type, as shown in Figure 4:
(1) Input traffic to an output traffic from each area
As discussed in Section 3.1, a firewall function is placed in each receiving-side area. Therefore, a virtual routing function to handle the input traffic to and the output traffic from
Figure 4 Two different traffic types for allocation routing functions
Each area is placed in each area. This is different from the previous study  where only virtual routing functions were considered.
(2) Relay traffic between areas
As in the case where the allocation of only virtual routing functions was considered , virtual routing functions are placed in specific areas in such a way that the network cost is minimized. The statistical multiplexing effects, which can be gained by binding multiple traffic flows, are taken into consideration this time. The cost-reducing effect of circuit multiplexing is explained below using Figure 5. This figure assumes that there are three traffic flows going in the same direction. Their maximum speeds are respectively V1, V2 and V3. When these flows are statistically multiplexed by the virtual routing function in a relay area, the maximum speed of the resulting traffic becomes V0, which is lower than the total of V1 to V3. If the reduction in the bandwidth cost of the subsequent relay areas is larger than the cost of the virtual routing function used, this multiplexing is adopted. Otherwise, the traffic flows are not multiplexed.
Figure 5 .Effect of statistical multiplexing
The following algorithm for routing function allocation is proposed. First, a routing function is placed in every relay area based on the traffic flows between areas. In other words, relay bandwidths are allocated on the assumption that the statistical multiplexing effect is large enough. Next, the relay area farthest from the network center is selected. If the removal of the routing function in the selected area results in a reduction in the network cost, that routing function is removed. This means that the statistical multiplexing effect is not sought. Then, the next farthest
relay area from the network center is selected, and the same decision-making process as above is executed. This is repeated for all the remaining relay areas.
4.Evaluation Of The Proposed Routing Function Allocation Algorithm
4.1 Evaluation Conditions
1) We have developed a simulation program in C language that executes the algorithm for allocating the routing function and the firewall function proposed in Section 3.
2) Network structure: The ladder-shaped model illustrated in Figure 6, which simulates the shape of Japan, is used as in Reference .
Figure 6 .Ladder shaped network topology which simulates the shape of Japan
3) Traffic flow: The traffic flow is the same as that used in Reference . It is also supposed that the amount of traffic between Area #5 and each of the remaining area is M times that of traffic between other areas .
4) Routing policy: The same routing policy as adopted in reference  is also applied.
5) Network cost calculation: The network cost is greatly affected by the ratio (ZC) of the routing function cost to the bandwidth cost, and the ratio (WC) of the firewall function cost to the bandwidth cost. These ratios are defined as follows:
Where αC is the routing function cost per packet per second, βC is the bandwidth cost per Mbps per 10km, and γC is the firewall function cost per packet per second. The fixed cost, which is the necessary cost even if traffic is 0, is not taken into consideration here, as in reference .
6) Filtering coefficient: The probability at which input traffic passes through a packet filtering function is defined as Pr. For example, Pr=0.9 means that the 90% of entire traffic passes through while Pr=0 means that all packets in the traffic are discarded. It is assumed in this study that the value of Pr is the same for all areas.
7) Filtering cost coefficient: The ratio of the packet filtering function cost to the entire firewall function cost is defined as f. For example, f=0.3 means that 30% of the firewall function cost is a packet filtering function cost.
8) Statistical multiplexing coefficient: The ratio of the bandwidth resulting from multiplexing communication flows statistically to the bandwidth required before this multiplexing is defined as g. For example, g=0.7 means that the bandwidth required after multiplexing is 70% of the bandwidth required before multiplexing.
4.2 Evaluation Results and Discussions
The evaluation results are shown in Figures. 7 to 14. Figure 7 shows the effect of Pr, Figure 9 the effect of WC, Figure 10 the effect of f, Figure 11 the effect of g, and Figure 13 the effect of ZC. The vertical axis of each figure shows a normalized total network cost. Figures 7, 9, 10, 11 and 13 also include data for the solution with the minimum network cost and the details of network cost data. Figure 8 shows the final allocation of additional packet filtering functions. Figure 12 and 14 shows the final allocations of routing functions for inter-area relay traffic as affected by g and ZC respectively. Figures 1 to 14 are the results calculated assuming the following parameter values; Zc=0.02, Wc=0.1, f=0.4, M=5, g=0.5, Pr=0.8. When using a different parameter value, its value is described in the figure.
This paper also compares the proposed algorithm with the optimal solution which has the lowest cost (‘solution with minimum network cost’, in each Figure) and can be obtained by checking all possible cases.
The following points are clear from these Figures:
(a) The smaller the filtering coefficient, Pr, the smaller the network cost.
<Reason> The smaller the Pr is, the smaller the volume of traffic that is passed by the packet filtering function. This reduces the routing function cost and the bandwidth cost. In Figure 7, the total of the firewall function cost and the packet filtering function cost for the cases of Pr=0.4 and Pr=0.8 is more or less the same as that for the case of no additional packet filtering function. However, both the bandwidth cost and the routing function cost are reduced by half.
In the condition of Figure 7, the additional deployment of packet filtering functions can be advantageous when Pr is not less than 0.7. One of the main objectives of this paper is to provide such network design guidelines.
(b) Assuming NFV-based packet filtering function, it is possible to add small additional capacity which could not be realized by the conventional non-NFV based method. In the example of Pr=0.7 in Figure 7, the network cost can be reduced by about 20% compared with the conventional network equipment, by the additional packet filtering deployment based on NFV. The additional packet filtering functions are not placed in all areas as it is not economical in the conventional network design, as illustrated in Figure 8. It should be an example of the effect unique to NFV.
(c) The smaller the Wc is and the smaller f is, the smaller the network cost.
<Reason> As Wc becomes smaller; the costs of the firewall function and the additional packet filtering function become smaller, as shown in Figure 9. Meanwhile, the routing function cost and the bandwidth cost remain unchanged. Thus, the total network cost is reduced. Moreover, in the example shown in Figure 10, halving the value of f does not change the firewall function cost, the routing function cost or the bandwidth cost, but reduces the cost of the additional packet filtering function. Thus, the network cost can be reduced.
(d) The smaller the statistical multiplexing coefficient, g, and the smaller the cost ratio, Zc, the smaller the network cost. Also, the smaller g is and the smaller Zc is, the more distributed the final allocation of routing functions for relay traffic become.
<Reason> The smaller the g is, the greater the effect of statistical multiplexing. This results in a smaller demand for bandwidth. As shown in Figure 11, all types of cost other than the bandwidth cost for the case of g=0.4 are more or less the same as those for g=0.8. However, the bandwidth cost is almost halved. Moreover, as g becomes smaller, it becomes more advantageous to allocate routing functions for inter-area relay traffic. As a result, the final allocation of the routing functions for this type of traffic becomes more distributed, as shown in Figure 12. As shown in Figure 13, the smaller Zc is, the smaller the network cost. Moreover, as Zc becomes smaller, the amount of reduction in the routing function cost becomes larger, making it more advantageous to allocate routing functions for inter-area relay traffic, as shown in Figure 14.
(e) The proposed algorithm would be approaching about 95% of the deployment with minimum network cost, as in Figures 7 and 10.
The above evaluations are based on a ladder-shaped network model with 10 areas (Figure 6). Even if the number of areas is increased to 100, for example, or a star-shaped or a loop-shaped model is used, the proposed function allocation algorithm can be applied basically. Therefore, the main trends discussed above and the proposed network design guidelines can be also be applicable to such cases. However, additional evaluations are necessary to decide where and how many virtual network functions should be allocated.
Figure 7. Impact of Pr on network cost
Figure 8. Final topology of additional packet filtering function allocation to each area
Figure 9.Impact of Wc on network cost
Figure 10.Impact of f on network cost
Figure 11.Impact of g on network cost
Figure 12.Final topology of routing function allocation for inter –area relay traffic
Figure 13.Impact of Zc on network cost
Figure 14.Final topology of routing Function
This paper has proposed the joint deployment algorithm of virtual routing function and virtual firewall function for minimizing the network cost, and has evaluated the proposed algorithm on a ladder model that simulates the shape of Japan, and developed multiple effective functional allocation guidelines.
It will be necessary to evaluate the proposed algorithm taking the fixed costs for routing function, firewall function, and bandwidth into consideration. It will be also necessary to study the optimal function allocation for cases where virtual cache function, WAN optimization function or DPI function is required.
We would like to thank Mr. Kenichiro HIDA for his help with the evaluation.
 M. Chiosi et al., “Network Functions Virtualization – An Introduction, Benefits, Enablers, Challenges and Call for Action,” ETSI NFV, Oct. 2012.
 “Network Functions Virtualisation (NFV); Architectual Framework,” ETSI GS NFV 002 v1.2.1, Dec. 2014.
 R.Mijumbi, J.Serrat, J.Gorricho, N.Bouten, F.D.Trurck and R.Boutaba, “Network Function Virtualization: State-of-the-art and Research Challenges,” IEEE Communications Surveys & Tutorials, Vol. 18, Issue 1, pp.236-262, 2016.
 NTT docomo press release
 J.G.Herrera and J.F.Botero, “Resource allocation in NFV: A comprehensive survey,” IEEE Trans. on Network and Service Management, Vol.13, No.3, pp.518-532, 2016.
 KenichiroHida and Shin-ichi Kuribayashi, “Virtual routing function allocation method for minimizing total network power consumption,” 18th International Conference on Information and Communication Systems (ICICS Venice 2016), Aug. 2016.
 KenichiroHida and Shin-ichi Kuribayashi, “NFV-based virtual routing function deployment under network delay,” 19th International Conference on Computer Communications and Applications (ICCCA Kyoto 2017), Nov. 2017.
 A.Fischer, J.F.Botero, M.T.Beck, H.Meer, and X.Hesselbach,” Virtual Network Embedding: A Survey”, IEEE Communications Surveys & Tutorials, Vol. 15, No.4, 2013.
 X.Wei, S.Hu, H.Li, F.Yang and Y.Jin, “A Survey on Virtual Network Embedding in Cloud Computing Centers”, The Open Automation and Control Systems Journal, Vol. 6, pp.414-425, 2014.
 S. Mehraghdam, M. Keller, and H. Karl, “Specifying and placing chains of virtual network functions,” in Cloud Networking (CloudNet), 2014 IEEE 3rd International Conference on, Oct 2014, pp. 7–13.
 H. Moens and F. D. Turck, “VNF-P: A model for efficient placement of virtualized network functions,” in Network and Service Management (CNSM), 2014 10th International Conference on, Nov 2014, pp. 418–423.
 R.Mijumbi, J.Serrat, J.Gorricho, N.Boutenz, F.Turckz and S.Davy, “Design and Evaluation of Algorithms for Mapping and Scheduling of Virtual Network Functions,” 1st IEEE Conference on Network Softwarization (NetSoft), pp.1-9, 2015.
 S.Clayman, E.Mainiy, A.Galis, A.Manzaliniz and N. Mazzocca, “The Dynamic Placement of Virtual Network Functions,”IEEE Network Operations and Management Symposium (NOMS),pp.1-9, 2014.
 A.Basta, W.Kellerer, M.Hoffmann, H.J.Morper, and K.Hoffmann, “Applying NFV and SDN to LTE Mobile Core Gateways; The Functions Placement Problem,” 4th Workshop on All Things Cellular: Operations, Applications and Challenges 2014, pp.33-38, Aug. 2014.
 M.Bouet, J.Leguay and V.Conan, “Cost-based placement of vDPI functions in NFV infrastructures,” International Journal of Network Management, pp.490-506, 2015.
 S.Tsumura and S.Kuribayashi, “Simultaneous allocation of multiple resources for computer communications networks”, APCC2006, 2F-4 (2006.8)
 S.Kuribayashi, “Optimal Joint Multiple Resource Allocation Method for Cloud Computing Environments”, International Journal of Research and Reviews in Computer Science (IJRRCS), Vol.2, No.1, pp.1-8, Feb. 2011.
 S.Kuribayashi,“Resource Allocation Method for Cloud Computing Environments with Different Service Quality to Users at Multiple Access”, International Journal of Computer Networks & Communications (IJCNC) Vol.7, No.6, pp.33-51, Nov.2015.
 S.Kuribayashi,“Evaluation of Congestion control Methods for Joint Multiple Resource Allocation in Cloud Computing Environments”, International Journal of Computer Networks & Communications (IJCNC) Vol.9, No.3, pp.41-54, May 2017.
 S. Mehraghdam, M. Keller, and H. Karl, “Specifying and placing chains of virtual network functions,”2014 IEEE 3rd International Conference onCloud Networking (CloudNet),pp.7-13,Oct 2014.
 K. Hida and S. Kuribayashi, “Joint Deployment of Virtual Routing Functionand Virtual Firewall Function in NFV-Based Network with Minimum Network,” Advances in Network-Based Information Systems-2019, pp.333-345, Aug. 2018．
Shin-ichi Kuribayashi received the B.E., M.E., and D.E. degrees from Tohoku University, Japan, in 1978, 1980, and 1988 respectively. He joined NTT Electrical Communications Labs in 1980. He has been engaged in the design and development of DDX and ISDN packet switching, ATM, PHS, and IMT 2000 and IP-VPN systems. He researched distributed communication systems at Stanford University from December 1988 through December 1989. He participated in international standardization on ATM signaling and IMT2000 signaling protocols at ITU-T SG11 from 1990 through 2000. Since April 2004, he has been a Professor in the Department of Computer and Information Science, Faculty of Science and Technology, Seikei University. His research interests include resource management for NFV and SDN-based networks, QoS control, traffic control for cloud computing environments and green network. He is a member of IEEE and IEICE.