A brokerless edge service marketplace could play a significant role in enabling an eco- system where a large number of edge providers and Communication Service Providers (CSPs) offer Mobile Edge Infrastructure Services (EISs) to providers of edge-based applications and services. The marketplace would be the bridge between EIS providers and their customers, managing the relations between actors in the mobile edge eco- system. One of the key services of the marketplace is service selection where not only a list of EISs matching the customers’ demands is provided but also enables service selection based on the customers’ requirements to fully automate the process.We firstly consider different selection scenarios and investigate essential parameters for service selection in such a marketplace, including (i) important attributes of EISs such as coverage area, latency, pricing, etc, and (ii) the requirements of edge-based applications such as latency and reliability. We formulate how these application requirements can be fulfilled by choosing the right set of EISs among available services in the marketplace as two different optimization problems considering average latency and cost as separate objectives to minimize. First, we relax the objective function in average delay minimization problem, which is a linear-fractional programming problem. We solve the relaxed version of the problem by Branch and bound (BnB) and Bound and Branch with Priority Queue (BnBPQ) algorithms. Additionally, we relax the objective function in total monetary cost minimization problem which is an integer linear programming problem. We propose Best Fit (BF) and Improved Best Fit (IBF) algorithms to solve the problem. Furthermore, the IBM CPLEX Optimizer [1] is also implemented to solve the two problems. The evaluation shows that the algorithms we implemented can solve the problems with results close to optimal as compared to the results of exhaustive search and shorter run time than exhaustive search. Meanwhile, the CPLEX can solve the problem well, but it’s not scalable for huge problem instances since the problems are NP-complete and not solvable in polynomial time. / En marknadslös marknadsföring på kanten av tjänster kan spela en viktig roll för att möjliggöra ett ekosystem där ett stort antal kantleverantörer och acp CSP erbjuder Mobile acp EIS till leverantörer av kantbaserade applikationer och tjänster. Marknadsplatsen skulle vara bron mellan ac EIS leverantörer och deras kunder och hantera relationerna mellan aktörer i det mobila ekosystemet. En av marknadens viktigaste tjänster är val av tjänster där inte bara en lista över acp EIS som matchar kundernas krav tillhandahålls utan också möjliggör serviceval baserat på kundernas krav för att automatisera processen helt.Vi överväger för det första olika urvalsscenarier och undersöker väsentliga parametrar för val av tjänster på en sådan marknadsplats, inklusive (i) viktiga attribut för acp EIS som täckningsområde, latens, prissättning osv. Och (ii) kraven på kant- baserade applikationer som latens och tillförlitlighet. Vi formulerar hur dessa applikationskrav kan uppfyllas genom att välja rätt uppsättning acp EIS bland tillgängliga tjänster på marknaden som två olika optimeringsproblem med tanke på genomsnittlig latens och kostnad som separata mål för att minimera. Först slappnar vi av objektivfunktionen i ett genomsnittligt förseningsminimeringsproblem, vilket är ett linjärt-fraktionellt programmeringsproblem. Vi löser den avslappnade versionen av problemet med ac BnB och ac BnBPQ algoritmer. Dessutom slappnar vi av objektivfunktionen i totala monetära kostnadsminimeringsproblem som är ett heltal linjärt programmeringsproblem. Vi föreslår ac BF och ac IBF algoritmer för att lösa problemet. Dessutom implementeras IBM CPLEX Optimizer cite cplex för att lösa de två problemen. Utvärderingen visar att algoritmerna vi implementerade kan lösa problemen med resultat som är nära optimala jämfört med resultaten av uttömmande sökning och kortare körtid än uttömmande sökning. Under tiden kan CPLEX lösa problemet väl, men det är inte skalbart för stora problemstillfällen eftersom problemen är NP-kompletta och inte lösbara under polynom tid.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:kth-281243 |
| Date | January 2020 |
| Creators | Li, Wenhao |
| Publisher | KTH, Skolan för elektroteknik och datavetenskap (EECS) |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | Swedish |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | TRITA-EECS-EX ; 2020:596 |
Page generated in 0.002 seconds