Multi-homing är en teknik som används av Internet Service Provider (ISP) för att ansluta till Internet via olika nätverksleverantörer. För att fullt ut utnyttja de underliggande nätverken med minimala kostnader krävs en optimal routingstrategi av Internetleverantörerna. Denna studie undersöker den optimala routing strategin i fall där nätleverantörer debiterar Internetleverantörer enligt högsta procentuell prissättning. Vi kallar detta problem för top-percentil Traffic Routing Problem (TpTRP). TpTRP är ett flerstegs stokastiskt optimeringsproblem där routingbeslutet bör fattas innan man vet hur mycket trafik som ska trafikeras under den följande tidsperioden. Problemets stokastiska karaktär utgör den kritiska svårigheten i denna studie. I den här artikeln undersöks flera metoder för att modellera och lösa problemet. Vi börjar med att modellera TpTRP som ett flerstegs stokastiskt programmeringsproblem, vilket är svårt att lösa på grund av heltalsvariabler som införs av top-percentil prissättning. Flera förenklingar av det ursprungliga TpTRP undersöks sedan i den andra delen av detta arbete. Vissa av dessa tillåter analytiska lösningar som leder till begränsningar av den uppnåeliga optimala lösningen. Vi etablerar också gränser genom att undersöka flera "naiva" routing politik. I slutändan utforskar vi lösningen av TpTRP som ett stokastiskt dynamiskt programmeringsproblem genom en diskretisering av tillståndet utrymme. Detta gör att vi kan lösa medelstora fall av TpTRP till optimalitet och förbättra alla naiva routing politik.
Grothey m.fl. REF undersöker ett liknande problem genom en stokastisk dynamisk programmeringsmetod.
Top-percentile traffic routing problem by Dynamic Programming
{'venue': None, 'journal': None, 'mag_field_of_study': ['Computer Science']}