Vi anser uppgiften att dator (kombinerad) funktion kartläggning och routing för förfrågningar i Software-definierade nätverk (SDNs). Funktionskartläggning avser tilldelning av noder i substratnätverket till olika bearbetningssteg som förfrågningar måste genomgå. Routing avser tilldelning av en sökväg i substratnätverket som börjar i en källa nod för begäran, passerar noderna som tilldelas funktioner för denna begäran, och slutar i en destination för begäran. Algoritmen antingen avvisar en begäran eller helt tjänar en begäran, och dess mål är att maximera summan av fördelarna med den betjänade begäran. Lösningen måste hålla kant och vertex kapacitet. Vi följer det ramverk som föreslås av Even et al.[1] för specificering av bearbetningskrav och dirigering av ansökningar via diagram över bearbetning och dirigering (PR-grafer). Inom denna ram har varje begäran en efterfrågan, en fördel och PR-graf. Vårt huvudresultat är en randomiserad approximationsalgoritm för vägberäkning och funktionsplacering med följande garanti. Låt m betecknar antalet länkar i substratnätverket, ε betecknar en parameter sådan att 0 < ε < 1, och opt f betecknar den maximala fördelen som kan uppnås med en fraktionerad lösning (en där förfrågningar kan delvis serveras och flödet kan delas längs flera vägar). Låt c min betecknar den minsta kanten kapacitet, och låt d max betecknar den maximala efterfrågan. Låta Max betecknar en övre gräns på antalet bearbetningssteg en begäran genomgår. Om c min/(- max · d max ) = (log m)/ε 2 ), med sannolikhet minst 1. De viktigaste egenskaperna hos denna utveckling är i) separation mellan dataplanet och lednings- eller kontrollplanet, ii) specificering av förvaltningen av nätverket från ett globalt perspektiv, iii) införande av nätuttag som ger en enkel nätverksmodell och iv) programmerbarhet för nätverkskomponenter. I detta dokument fokuserar vi på ett algoritmiskt problem som nätverksförvaltaren behöver lösa i en NFV/SDN-inställning. Detta problem kallas vägberäkning och funktionsplacering. Path beräkning är helt enkelt uppgiften att fördela vägar till förfrågningar. Dessa vägar omfattas av kapacitetsbegränsningarna för nätverkslänkarna och nätknutpunkternas kapacitet att vidarebefordra dem. I moderna nätverk är nätverkandet inte begränsat till att vidarebefordra paket från källor till destinationer. Begäran kan komma i form av flöden (dvs. strömmar av paket från en källnod till en destinationsnod med en angiven paketsats) som måste genomgå bearbetningssteg på väg till sin destination. Exempel på bearbetningssteg är komprimering, kryptering, brandväggsvalidering, djuppaketkontroll etc. NFV:s kristallkula är införandet av abstraktioner som gör det möjligt att, per begäran, ange krav som bearbetningssteg, giltiga platser för varje bearbetningssteg och tillåtna uppsättningar länkar längs vilka paket kan skickas mellan bearbetningsstegen. Ett viktigt exempel för ett sådant mål är att stödja säkerhetskrav som föreskriver att okrypterade paket inte passerar opålitliga länkar eller nå opålitliga noder. Ur algoritmisk synvinkel kombinerar problemet med vägberäkning och funktionsmappning två olika optimeringsproblem. Enbart beräkning av tågläge (dvs. ren pakettransport utan bearbetning av paket) är ett problem med paketering av tåglägen. Enbart funktionskartläggning (dvs. i vilket fall paket endast behöver behandlas men inte styras) är ett problem med lastbalansering. För att ge en känsla av problemet, överväga ett särskilt fall av förfrågningar om strömmar, som var och en måste genomgå samma sekvens av k bearbetningssteg w 1, w 2,. .., w k. Detta innebär att service av en begäran från s i till t i realiseras genom en konkatering av k + 1 vägar: ; t i, där bearbetningsfasen w i äger rum i node v i. Observera att noderna v 1,. .., v k behöver ingen vara distinkt och den konkatenterade vägen p 0 • p 1 • · · • p k behöver inte vara enkel. En samling av tilldelningar som tjänar en uppsättning förfrågningar inte bara ådrar sig en vidarebefordran belastning på nätverkselementen, det ådrar sig också en beräkningsbelastning på noderna. Beräkningsbelastningen skapas av behovet av att utföra bearbetningsstegen för förfrågningarna. Tidigare verk. De flesta papper om ämnet resort till heuristik eller icke-polynomalgoritmer. Exempelvis används blandprogrammering [6]. Onlineversionen studeras i [1] där ny standby/accept servicemodell introduceras. Bidrag och tekniker. Enligt rimliga antaganden (dvs. logaritmisk kapacitet-efterfrågan förhållande och tillräckligt stor optimal nytta), presenterar vi den första offline approximation algoritm för väg beräkning och funktion placering problem. Vår utgångspunkt är modellen för SDN-förfrågningar som presenteras i [1]. I denna modell, varje begäran representeras av en särskild graf, kallas en plats-och-rutt graf (pr-graf, i korthet). Pr-grafen representerar både routingkravet och de bearbetningskrav som streamens förpackningar måste genomgå. Vi bygger också på tekniken med grafprodukter för att representera giltiga förverkliganden av förfrågningar [1]. Vi föreslår en bråkdels lättnad av problemet. Den fraktionerade avslappningen består av en uppsättning fraktionerade flöden, var och en över en annan produkt graf. Varje flöde är fraktionerat i den meningen att det kan tjäna endast en del av en begäran och kan dela Even, Rost och Schmid 3 flöde bland flera vägar. Vi betonar att de fraktionerade flödena inte utgör ett flöde av flera råvaror eftersom de är över olika grafer. Felprocentsproblemet är dock en allmän förpackning av LP [4]. Vi löser avslappningen och tillämpar randomiserad avrundning [4] för att hitta en ungefärlig lösning. Även om randomiserad avrundning är mycket välkänd och förekommer i många läroböcker och tidningar, förekommer versionen av det allmänna förpackningsproblemet endast på en halv sida i Raghavans avhandling [4, s. 41]. Ett specialfall med enhetskrav och enhetsförmåner visas i [3]. Kanske ett av inläggen i detta dokument är en fullständig beskrivning av analysen av randomiserad avrundning för det allmänna förpackningsproblemet. I Even et al. [1] En modell för SDN-förfrågningar, baserad på så kallade place-and-route grafer (pr-grafer) och produktgrafer presenteras. Modellen är ganska allmän, och tillåter varje begäran att ha flera källor och destinationer, varierande bandbredd efterfrågan baserat på bearbetningssteg, uppgift specifik kapacitet, förbjudna platser för bearbetning, och förbjudna länkar för routing mellan bearbetningssteg, etc. Vi ser över en förenklad version av denna modell så att vi kan definiera problemet med vägberäkning och funktionsplacering. Substratnätverket är ett fast nätverk av servrar och kommunikationslänkar. Nätverket representeras av en graf N = (V, E), där V är uppsättningen noder och E är uppsättningen av kanter. Noder och kanter har kapacitet. Kapaciteten hos en kant e betecknas med c(e), och kapaciteten hos en nod v  på V betecknas med c (v). Genom skalning kan vi anta att min x-V-E c(x) = 1. Vi noterar att nätverket är statiskt och oriktat (nämligen varje kant representerar en dubbelriktad kommunikationslänk), men kan innehålla parallella kanter. Varje begäran anges av en tuple, Där komponenterna är följande: är en riktad (acyklisk) graf kallas plats-och-väg graf (pr-graf). Det finns en enda källa (respektive, diskho) som motsvarar källan (resp. Bestämmelseland) för begäran. Vi betecknar källan och sjunka noder i G j av s j och t j, Respektive. De övriga hörnen motsvarar tjänster eller bearbetningssteg i en begäran. Kanterna på pr-grafen är riktade och anger företrädesförhållandet mellan pr-vertices. 2. Utgångspunkten är följande: Efterfrågan på r j är d j och förmånen är b j. Genom skalning kan vi anta att min j b j = 1. är en uppsättning av "tillåtna" noder i N som kan utföra tjänst x, och U j (y) är en uppsättning av "tillåtna" kanter av N som kan genomföra routing kravet som motsvarar y. För varje begäran r j, produktnätverket pn( N, r j ) definieras på följande sätt. Den nod uppsättning av pn(N, r j ), betecknad V j, definieras som V j  på YJ (U j (y) × {y}). Vi hänvisar till undergruppen U j (y) × {y} som y-skiktet i produktgrafen. Kantuppsättningen pn(N, r j ), betecknad E j, består av två typer av kanter E j = E j,1  till E j,2 definieras enligt följande.  Bearbetning kanter ansluter två kopior av samma nätverk vertex i olika lager. E j,2 = (v, y), (v, y) y = y är 2 kanter med en gemensam endpoint x, och v U j (x). Betrakta en patch i produktgrafen pn(N, r j ) som börjar i s j - lager och slutar i t j - lager, där s j och t j är källan och sjunka hörn av pr-graf G j. En sådan väg p representerar rutteringen av begäran r j från dess ursprung till dess destination och de bearbetningsstadier som den genomgår. De bearbetning kanter longp representerar noder där bearbetning stadier av r j äger rum. Ruttkanterna inom varje lager representerar stigar längs vilka begäran levereras mellan bearbetningsstegen. Denna förordning träder i kraft den tjugonde dagen efter det att den har offentliggjorts i Europeiska unionens officiella tidning. En patch i produktnätverket pn(N, r j ) som börjar i (källa) s j - lager och slutar i (sink) t j - lager är ett giltigt förverkligande av begäran r j. Vi noterar att i [1] projektionen avp till substratet nätverket kallas en giltig realisera. Projektionen av hörn av pn(N, r j ) till hörn i N kartor en vertex (u, y) till u. Genom definitionen av produktgraf, denna projektion kartor vägar i pn(N, r j ) till vägar i N. Betrakta den väg p i N som är resultatet av projektionen av en patch i produktgrafen. Observera att p kanske inte är helt enkelt även iff är enkelt. Anmärkning. Betrakta en patch i produktgrafen pn(N, r j ). Multipliciteten av en kant e = (u, v) i substratnätverket N inp är antalet routing kanter inp som projektet att e, formellt: På samma sätt är multipliciteten av en vertex v  på V inp antalet bearbetning kanter inp att projektet till v, formellt: Kapacitet Restriktioner. LetP = {p i } i-I betecknar en uppsättning giltiga insikter för en delmängd {r i-} i-I-R av förfrågningar. SetP uppfyller kapacitetsbegränsningarna om definitionen av PCFP-problemet. Inmatningen i PCFP-problemet består av ett substratnätverk N = (V, E) och en uppsättning förfrågningar {r i } i till I. Målet är att beräkna giltiga insikter P = {p i } i på en delmängd I I sådan att: (1)P uppfyller kapacitetsbegränsningarna, och (2) förmånen jag b i är maximal. Vi hänvisar till framställningarna r i sådan att i I som den accepterade begäran; framställningar r i sådan att i I \ I kallas avslagna framställningar. Även, Rost och Schmid Tillnärmning Algoritmen för PCFP Den approximativa algoritmen för PCFP-problemet beskrivs i detta avsnitt.  Vi definierar nu den fraktionerade avslappningen av PCFP-problemet. Istället för att tilldela en giltig realisationp i per accepterad begäran r i, Vi tilldelar en fraktionerad flowf i i produktgrafen pn(N, r i ). Källan till flowf i är källskiktet (dvs. en superkälla som är ansluten till alla noder i källlagret). På samma sätt är destinationen utanför i målskiktet. Efterfrågan off i i är d i (därav f i o ≤ d i ). Liksom i det integrerade fallet ackumuleras kapacitetsbegränsningarna för alla ansökningar. Nämligen, låt f i betecknar projektionen utanför i till substratet nätverket. Kantkapacitetsbegränsningen för e är i f i (e) ≤ c(e). En liknande begränsning definieras för vertex kapacitet. Fördelarna med en fraktionerad lösning Vi betonar att denna bråkdelsavslappning inte är ett flöde av flera råvaror. Anledningen är att varje f i är över en annan produkt graf. Men fraktionerad avslappning är en allmän förpackning LP. Algoritmen använder en parameter 1 > > 0. Algoritmen fortsätter enligt följande. Dela upp alla kapaciteter med (1 + ε). Namn, c(e) = c(e)/(1 + ε) andc(v) = c(v)/(1 + ε). Beräkna en maximal fördel fraktionerad PCFP lösning {f i } i. 3. Vad är det som händer? Tillämpa den randomiserade avrundningsprocessen oberoende på varje flöde i över produktnätverket pn(N, r j ). (Se bilaga B för en beskrivning av förfarandet). Låt p i betecknar sökvägen i pn(N, r i) (om någon) som tilldelas att begära r i genom det randomiserade avrundningsförfarandet. Låt {f i } i betecknar projektionen av p i till substratnätverket. Observera att varje f i är ett osplitterbart allt-eller-ingenting flöde. Projektionen av p i kan inte vara en enkel väg i substratet, därav flödet f i (e) kan vara en multipel av efterfrågan d i. I denna förordning gäller följande definitioner: Diametern på en pr-graf G j är längden på en längsta väg i G j från källan s j till destinationen t j. Vi betecknar diametern på G j genom  på (G j ). Diametern på G j är väl definierad eftersom G j är acyklisk för varje begäran r j. I alla applikationer vi är säkra på, är diametern (G j ) konstant (d.v.s. mindre än 5). Anmärkning. Låt  på max max j till I (G j ) betecknar den maximala diametern av en begäran. Låt c min betecknar den minsta kanten kapacitet, och låt d max betecknar den maximala efterfrågan. Låt opt f betecknar en maximal fördel fraktionerad PCFP-lösning (med avseende på den ursprungliga kapaciteten c(e) och c(v)). Låt alg betecknar den lösning som beräknas av algoritmen. Låt B(S) beteckna nyttan av en lösning S. Definiera β(ε) (1 + ε) ln(1 + ε) − ε. Vårt mål är att bevisa följande teorem.  Vi anmärker i asymptotiska termer, Theorem anger att om cmin  på max·dmax =  och sedan alg uppfyller kapacitetsbegränsningarna med sannolikhet 1 - O(1/ på E) och uppnår en fördel av (1 - O(ε) · B(opt f ) med sannolikhet 1 Bevis. Beviset är baserat på det faktum att randomiserad avrundning tillämpas på varje flöde i oberoende. Således trängsel av en kant i alg är summan av oberoende slumpvariabler. Samma sak gäller för B (alg). Beviset går vidare genom att tillämpa Chernoffs gränser. Bevis på Eq. 1. Vad är det för fel på dig? För enkelhetens skull antar vi att det inte finns några vertex-kapaciteter (dvs. c(v) = ∞). Beviset är baserat på den Chernoff som är bunden i Theorem 5. För att applicera den bundna, fixera en substratkant e  på E. Kom ihåg att f i (e) är en flödesväg som erhålls genom en projektion av en väg i produktnätverket pn(N, r i ). Låt Villkoren i Theorem 5 är uppfyllda av följande skäl. Observera att 0. Låt alg(e) beteckna den belastning som uppstår på kanten e av alg. Nämligen alg(e) i en f i (e). Observera att alg(e) ≥ (1 + ε) ·c(e) iff ifi Från Theorem 5 drar vi slutsatsen att: Eq. 1 följer genom att tillämpa en union bunden över alla kanter. Bevis på Eq. 2. Utgångspunkten är följande: Beviset är baserat på den Chernoff bundet anges i Theorem 6. För att tillämpa den bundna, låt kapacitet. Villkoren i Theorem 6 är uppfyllda av följande skäl. Eftersom Vi noterar att i fallet med identiska förmåner (dvs. alla förmåner lika en och därmed b max = 1) kan man stärka uttalandet. Om B(opt f ) > c min, då den stora kapacitet antagande innebär att B(opt f )/(d max · b max ) ≥ c min /d max ≥ ε −2 · ln  på  på E. Detta innebär att B(alg) ≥ (1 − O(ε)) · B(opt f ) med sannolikhet minst 1 − 1/poly( skael). Genom att lägga till sannolikheterna för de två möjliga misslyckanden (dvs., överträdelse av kapacitet och liten nytta) och med hänsyn till preskalering av kapacitet, får vi att med sannolikhet minst 1 − O(1/poly( ska)), randomiserade avrundning returnerar ett allt-eller ingenting unsplittable multi-commodity flöde vars nytta är minst 1 − O (ε) gånger den optimala fördelen. Teorem 3 ger en övre gräns för sannolikheten för att alg inte är möjlig och att B (alg) är långt från B(opt f ). Dessa gränser innebär att vår algoritm kan ses som en version av en asymptotisk PTAS i följande mening. Antag att parametrarna b max och d max inte är en funktion av. När fördelen med den optimala lösningen opt f ökar ökar sannolikheten för att B(alg) ≥ (1 − O(ε) · B(opt f ) ökar. Å andra sidan behöver vi förhållandet mellan kapacitet och efterfrågan vara logaritmiskt, det vill säga c min ≥  och ((-) max · d max · ln -E)/ε 2 ). Vi anser att förhållandet mellan kapacitet och efterfrågan verkligen är stort i realistiska nät. Forskning som stöds av EU-projektet UNIFY FP7-IP-619609.
Med hänsyn till approximationsalgoritmer, Even et al. Använt slumpmässig avrundning i REF för att uppnå en konstant approximation för ansökningar om inbäddning av linjer på godtyckliga substratdiagram under starka antaganden om både fördelar och kapacitet.