Abstract-Vi undersöker problemet med optimal begäran routing och innehåll caching i ett heterogent nätverk som stöder i-nätverk innehåll caching med målet att minimera genomsnittlig fördröjning innehåll access. Här kan innehåll antingen nås direkt från en back-end-server (där innehåll finns permanent) eller erhållas från en av flera cachefiler i nätverket. För att komma åt en del av innehållet, måste en användare besluta om att dirigera sin begäran till en cache eller back-end server. Dessutom måste caches avgöra vilket innehåll som ska cache. Vi undersöker problemet komplexiteten i två problemformuleringar, där den direkta vägen till back-end-servern är modellerad som i) en trängselkänslig eller ii) en trängsel-okänslig väg, som återspeglar om fördröjningen av den ofångade sökvägen till back-end-servern beror på användarens begäran belastning, respektive. Vi visar att problemet är NP-komplett i båda fallen. Vi bevisar att problemet med trängsel-okänslig modell kan lösas optimalt i polynom tid om varje innehåll begärs av endast en användare, eller när det finns högst två cache i nätverket. Vi identifierar också en strukturell egenskap hos användar-cache grafen som potentiellt gör problemet NP-komplett. För den trängselkänsliga modellen bevisar vi att problemet fortfarande är NP-komplett, även om det bara finns en cache i nätverket och varje innehåll bara begärs av en användare. Vi visar att ungefärliga lösningar kan hittas för båda modellerna inom en (1 −1/e) faktor av den optimala lösningen, och demonstrera en girig algoritm som finns inom 1% av optimal för små problemstorlekar. Genom spårdrivna simuleringar utvärderar vi prestandan hos våra giriga algoritmer, som visar upp till en 50% minskning av den genomsnittliga fördröjningen över lösningar baserade på LRU-innehåll caching.
Författarna i REF överväger ett hybridnätverk med in-network caching och de föreslår en (1 − 1/e) - approximation girig algoritm.
On the complexity of optimal routing and content caching in heterogeneous networks
{'venue': '2015 IEEE Conference on Computer Communications (INFOCOM)', 'journal': '2015 IEEE Conference on Computer Communications (INFOCOM)', 'mag_field_of_study': ['Computer Science']}