Abstract-En Internet Service Provider måste tillhandahålla transittjänst för trafik mellan sina kunder och sina leverantörer och samtidigt försöka minimera nätutnyttjandet och balansera trafiken efter kapaciteten hos dess gräns routrar. Centralt för valet av gränsroutrar för transittrafikflöden är Border Gateway Protocol (BGP) mellan oberoende systemkollegor, genom vilka linjeannonser för nätprefix avgör valet av gränsroutrar för varje trafikflöde. I detta dokument undersöks problemet med att fastställa en optimal uppsättning gränsroutrar för reklam för prefix för nät i syfte att minimera kostnaden för trafik över en leverantörs nät av transittjänster, samtidigt som man bibehåller de begränsningar av egress bandbredden som gäller för gränsroutrar. Egress bandbredd begränsningar beaktas eftersom det finns anekdotiska bevis för att antyda att peering länkar mellan ASes är ofta flaskhals länkar på Internet, och så det optimala utnyttjandet av dessa länkar är också avgörande. Efter att exakt ha formulerat optimeringsproblemet i enlighet med driften av BGP relaterar vi problemet till det Generaliserade Uppdragsproblemet och utvecklar heuristiska lösningar för att lösa det. Simuleringsresultat från en implementering visar upp till 37% förbättring i utnyttjandet av peering länkar jämfört med heta potatis routing.
Observera dock att problemet som beaktas i REF, som är en variation av den Generalized Inlämningsproblem (GAP), är NP-Hard, medan COP kan lösas i polynom tid.
Optimal configuration for BGP route selection
{'venue': 'IEEE INFOCOM 2003. Twenty-second Annual Joint Conference of the IEEE Computer and Communications Societies (IEEE Cat. No.03CH37428)', 'journal': 'IEEE INFOCOM 2003. Twenty-second Annual Joint Conference of the IEEE Computer and Communications Societies (IEEE Cat. No.03CH37428)', 'mag_field_of_study': ['Computer Science']}