• Login
    View Item 
    •   Home
    • Theses and Dissertations
    • Theses and Dissertations
    • View Item
    •   Home
    • Theses and Dissertations
    • Theses and Dissertations
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Browse

    All of TUScholarShareCommunitiesDateAuthorsTitlesSubjectsGenresThis CollectionDateAuthorsTitlesSubjectsGenres

    My Account

    LoginRegister

    Help

    AboutPeoplePoliciesHelp for DepositorsData DepositFAQs

    Statistics

    Most Popular ItemsStatistics by CountryMost Popular Authors

    Efficient and robust resource allocation for network function virtualization

    • CSV
    • RefMan
    • EndNote
    • BibTex
    • RefWorks
    Thumbnail
    Name:
    Sallam_temple_0225E_14206.pdf
    Size:
    1.226Mb
    Format:
    PDF
    Download
    Genre
    Thesis/Dissertation
    Date
    2020
    Author
    Sallam, Gamal
    Advisor
    Ji, Bo, 1982-
    Committee member
    Wu, Jie, 1961-
    Payton, Jamie
    Bai, Li
    Department
    Computer and Information Science
    Subject
    Computer Science
    Network Function Virtualization
    Placement and Allocation
    Resource Allocation
    Robust Sequence Submodular
    Permanent link to this record
    http://hdl.handle.net/20.500.12613/329
    
    Metadata
    Show full item record
    DOI
    http://dx.doi.org/10.34944/dspace/313
    Abstract
    With the advent of Network Function Virtualization (NFV), network services that traditionally run on proprietary dedicated hardware can now be realized using Virtual Network Functions (VNFs) that are hosted on general-purpose commodity hardware. This new network paradigm offers a great flexibility to Internet service providers (ISPs) for efficiently operating their networks (collecting network statistics, enforcing management policies, etc.). However, introducing NFV requires an investment to deploy VNFs at certain network nodes (called VNF-nodes), which has to account for practical constraints such as the deployment budget and the VNF-node limited resources. While gradually transitioning to NFV, ISPs face the problem of where to efficiently introduce NFV; here, we measure the efficiency by the amount of traffic that can be served in an NFV-enabled network. This problem is non-trivial as it is composed of two challenging subproblems: 1) placement of VNF-nodes; 2) allocation of the VNF-nodes' resources to network flows. These two subproblems must be jointly considered to satisfy the objective of serving the maximum amount of traffic. We first consider this problem for the one-dimensional setting, where all network flows require one network function, which requires a unit of resource to process a unit of flow. In contrast to most prior work that often neglects either the budget constraint or the resource allocation constraint, we explicitly consider both of them and prove that accounting for them introduces several new challenges. Specifically, we prove that the studied problem is not only NP-hard but also non-submodular. To address these challenges, we introduce a novel relaxation method such that the objective function of the relaxed placement subproblem becomes submodular. Leveraging this useful submodular property, we propose two algorithms that achieve an approximation ratio of $\frac{1}{2}(1-1/e)$ and $\frac{1}{3}(1-1/e)$ for the original non-relaxed problem, respectively. Next, we consider the multi-dimensional setting, where flows can require multiple network functions, which can also require a different amount of each resource to process a unit of flow. To address the new challenges arising from the multi-dimensional setting, we propose a novel two-level relaxation method that allows us to draw a connection to the sequence submodular theory and utilize the property of sequence submodularity along with the primal-dual technique to design two approximation algorithms. Finally, we perform extensive trace-driven simulations to show the effectiveness of the proposed algorithms. While the NFV paradigm offers great flexibility to network operators for efficient management of their networks, VNF instances are typically more prone to error and more vulnerable to security threats compared with dedicated hardware devices. Therefore, the NFV paradigm also poses new challenges concerning failure resilience. That has motivated us to consider robustness with respect to the class of sequence submodular function maximization problem, which has a wide range of applications, including those in the NFV domain. Submodularity is an important property of set functions and has been extensively studied in the literature. It models set functions that exhibit a diminishing returns property, where the marginal value of adding an element to a set decreases as the set expands. This notion has been generalized to considering sequence functions, where the order of adding elements plays a crucial role and determines the function value; the generalized notion is called sequence (or string) submodularity. In this part of the dissertation, we study a new problem of robust sequence submodular maximization with cardinality constraints. The robustness is against the removal of a subset of elements in the selected sequence (e.g., due to malfunctions or adversarial attacks). Compared to robust submodular maximization for set function, new challenges arise when sequence functions are concerned. Specifically, there are multiple definitions of submodularity for sequence functions, which exhibit subtle yet critical differences. Another challenge comes from two directions of monotonicity: forward monotonicity and backward monotonicity, both of which are important to proving performance guarantees. To address these unique challenges, we design two robust greedy algorithms: while one algorithm achieves a constant approximation ratio but is robust only against the removal of a subset of contiguous elements, the other is robust against the removal of an arbitrary subset of the selected elements but requires a stronger assumption and achieves an approximation ratio that depends on the number of the removed elements. Finally, we consider important problems that arise in the production networks, where packets need to pass through an ordered set of network functions called Service Function Chains (SFC) before reaching the destination. We study the following problems: (1) How to find an SFC-constrained shortest path between any pair of nodes? (2) What is the achievable SFC-constrained maximum flow? We propose a transformation of the network graph to minimize the computational complexity of subsequent applications of any shortest path algorithm. Moreover, we formulate the SFC-constrained maximum flow problem as a fractional multicommodity flow problem and develop a combinatorial algorithm for a special case of practical interest.
    ADA compliance
    For Americans with Disabilities Act (ADA) accommodation, including help with reading this content, please contact scholarshare@temple.edu
    Collections
    Theses and Dissertations

    entitlement

     
    DSpace software (copyright © 2002 - 2023)  DuraSpace
    Temple University Libraries | 1900 N. 13th Street | Philadelphia, PA 19122
    (215) 204-8212 | scholarshare@temple.edu
    Open Repository is a service operated by 
    Atmire NV
     

    Export search results

    The export option will allow you to export the current search results of the entered query to a file. Different formats are available for download. To export the items, click on the button corresponding with the preferred download format.

    By default, clicking on the export buttons will result in a download of the allowed maximum amount of items.

    To select a subset of the search results, click "Selective Export" button and make a selection of the items you want to export. The amount of items that can be exported at once is similarly restricted as the full export.

    After making a selection, click one of the export format buttons. The amount of items that will be exported is indicated in the bubble next to export format.