Virtualisering och softwarization av moderna datornätverk möjliggör definition och snabb distribution av nya nätverkstjänster som kallas servicekedjor: sekvenser av virtualiserade nätverksfunktioner (t.ex. brandväggar, cache, trafikoptimerare) genom vilka trafiken dirigeras mellan källa och destination. Detta dokument behandlar problemet med att ta emot och inbädda ett maximalt antal servicekedjor, dvs. ett maximalt antal källdestinationspar som leds via en sekvens av nätverksfunktioner som ska tilldelas, kapaciteras. Vi anser att en online variant av denna maximala tjänstekedjiga inbäddningsproblem, kort OSSEP, där förfrågningar kommer över tid, i värsta fall. Vårt huvudsakliga bidrag är en deterministisk O(log )-konkurrenskraftig online-algoritm, under antagandet att kapacitet är åtminstone logaritmiska i. Vi visar att detta är asymptotiskt optimalt inom klassen av deterministiska och randomiserade online-algoritmer. Vi utforskar också lägre gränser för offline approximation algoritmer, och bevisa att offline problemet är APX-hård för enhetskapacitet och liten ≥ 3, och även Poly-APX-hård i allmänhet, när det inte finns någon bunden på. Dessa approximation nedre gränser kan vara av oberoende intresse, eftersom de också omfattar andra problem som Virtual Circuit Routing. Slutligen presenterar vi en exakt algoritm baserad på 0-1 programmering, vilket innebär att den allmänna offline SCEP är i NP och genom ovanstående hårdhet resultat är NP-komplett för konstant.
Ref. REF föreslår en deterministisk onlinealgoritm för VNF-placering med beprövade övre och nedre gränser för beräkningstid.
Online Admission Control and Embedding of Service Chains
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}