Abstract-In-network innehåll caching har använts i både Internet och cellulära nätverk för att minska fördröjningen av innehåll-access. Vi undersöker problemet med att utveckla optimala gemensamma routing- och cachepolicyer i ett nätverk som stöder cachelagring i nätverk med målet att minimera förväntad fördröjning av innehållsåtkomst. Här kan behövligt 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 innehåll måste användarna alltså besluta om de ska skicka sina förfrågningar till en cache eller back-end-server. Dessutom måste caches bestämma vilket innehåll som ska cache. Vi undersöker två varianter av problemet, där sökvägarna till back-end-servern kan betraktas som antingen trängselkänsliga eller trängselokänsliga, vilket återspeglar om den försening som en begäran skickas till back-end-servern beror på begäran belastning, respektive. Vi visar att problemet med optimal gemensam cachelagring och routing är NP-komplett i båda fallen. Vi bevisar att problemet kan lösas på ett optimalt sätt i polynom om varje del av innehållet begärs av endast en användare, eller när det finns högst två cache i nätverket. Vi identifierar också den strukturella egenskapen hos användar-cache grafen som gör problemet NP-komplett. För den trängselkänsliga fördröjningsmodellen visar vi att problemet fortfarande är NP-komplett, även om det bara finns en cache i nätverket och varje innehåll begärs av endast en användare. Vi visar att ungefärliga lösningar kan hittas för båda fallen inom en (1 −1/e) faktor från den optimala, och demonstrera en girig lösning som numeriskt visas vara inom 1% av optimal för små problemstorlekar. Genom spårdrivna simuleringar utvärderar vi prestandan hos våra giriga lösningar för gemensam cachelagring och routing, som visar upp till 50% minskning av den genomsnittliga fördröjningen över lösningen av optimerad routing till senast använda caches.
Dessutom undersöktes problemet med gemensam cachelagring och routing i nätverk i REF och ungefärliga lösningar presenterades för att minimera användarnas åtkomstfördröjning.
On the Complexity of Optimal Request Routing and Content Caching in Heterogeneous Cache Networks
{'venue': 'TNET', 'journal': None, 'mag_field_of_study': ['Computer Science']}