skip to main content
article

TIE breaking: tunable interdomain egress selection

Published: 01 August 2007 Publication History

Abstract

In a large backbone network, the routers often have multiple egress points they could use to direct traffic toward an external destination. Today's routers select the "closest" egress point, based on the intradomain routing configuration, in a practice known as early-exit or hot-potato routing. In this paper, we argue that hot-potato routing is restrictive, disruptive, and convoluted and propose an alternative called TIE (Tunable Interdomain Egress selection). TIE is a flexible mechanism that allows routers to select the egress point for each destination prefix based on both the intradomain topology and the goals of the network administrators. In fact, TIE is designed from the start with optimization in mind, to satisfy diverse requirements for traffic engineering and network robustness. We present two example optimization problems that use integer-programming and multicommodity-flow techniques, respectively, to tune the TIE mechanism to satisfy networkwide objectives. Experiments with traffic, topology, and routing data from two backbone networks demonstrate that our solution is both simple (for the routers) and expressive (for the network administrators).

References

[1]
{1} Y. Rekhter, T. Li, and S. Hares, "A Border Gateway Protocol 4 (BGP-4)," RFC 4271, 2006.
[2]
{2} R. Teixeira, A. Shaikh, T. Griffin, and J. Rexford, "Dynamics of hotpotato routing in IP networks," in Proc. ACM SIGMETRICS, Jun. 2004, pp. 307-319.
[3]
{3} R. Teixeira, N. Duffield, J. Rexford, and M. Roughan, "Traffic matrix reloaded: Impact of routing changes," in Proc. Passive Active Measurement Workshop, Boston, MA, Mar./Apr. 2005, pp. 251-264.
[4]
{4} C. Labovitz, A. Ahuja, A. Bose, and F. Jahanian, "Delayed internet routing convergence," IEEE/ACM Trans. Netw., vol. 9, pp. 293-306, Jun. 2001.
[5]
{5} G. Iannaccone, C.-N. Chuah, S. Bhattacharyya, and C. Diot, "Feasibility of IP restoration in a tier-1 backbone," IEEE Network Mag., vol. 18, no. 2, pp. 13-19, Mar.-Apr. 2004.
[6]
{6} B. Fortz, J. Rexford, and M. Thorup, "Traffic engineering with traditional IP routing protocols," IEEE Commun. Mag., vol. 40, no. 10, pp. 118-124, Oct. 2002.
[7]
{7} J. Rexford, "Route optimization in IP networks," in Handbook of Optimization in Telecommunications, P. Pardalos and M. Resende, Eds. New York: Springer Science + Business Media, 2006.
[8]
{8} N. Feamster, J. Winick, and J. Rexford, "A model of BGP routing for network engineering," in Proc. ACM SIGMETRICS, Jun. 2004, pp. 331-342.
[9]
{9} S. Uhlig, "A multiple-objectives evolutionary perspective to interdomain traffic engineering," Int. J. Comput. Intell. Appl., pp. 215-230, Jun. 2005.
[10]
{10} E. Rosen, A. Viswanathan, and R. Callon, "Multiprotocol label switching architecture," RFC 3031, 2001.
[11]
{11} B. S. Davie and Y. Rekhter, MPLS: Technology and Applications. San Francisco, CA: Morgan Kaufmann, 2000.
[12]
{12} "ILOG CPLEX 9.0 User's Manual," ILOG, SA, France, 2003.
[13]
{13} R. Teixeira, T. Griffin, A. Shaikh, and G. Voelker, "Network sensitivity to hot-potato disruptions," in Proc. ACM SIGCOMM, Sep. 2004, pp. 231-244.
[14]
{14} B. Fortz and M. Thorup, "Increasing internet capacity using local search," Comput. Optim. Appl., vol. 29, no. 1, pp. 13-48, 2004.
[15]
{15} N. Feamster, H. Balakrishnan, J. Rexford, A. Shaikh, and J. van der Merwe, "The case for separating routing from routers," in ACM SIGCOMM Workshop Future Directions Network Architecture, Aug. 2004, pp. 5-12.
[16]
{16} O. Bonaventure, S. Uhlig, and B. Quoitin, "The case for more versatile BGP route reflectors," 2004 {Online}. Available: draft-bonaventure-bgp-route-reflectors-00.txt
[17]
{17} R. Chandra, P. Traina, and T. Li, "BGP communities attribute," RFC 1997, 1996.
[18]
{18} BGP Cost Community, {Online}. Available: http://www.cisco.com/ en/US/products/sw/iosswrel/ps5207/products_feature_guide09186a 00801a7f74.html
[19]
{19} D. Katz, K. Kompela, and D. Yeung, "Traffic engineering (TE) extensions to OSPF Version 2," RFC 3630, 2003.
[20]
{20} H. Smit, "Intermediate system to intermediate system (IS-IS) extensions for traffic engineering (TE)," RFC 3784, 2004.
[21]
{21} D. Awduche, "MPLS and traffic engineering in IP networks," IEEE Commun. Mag., vol. 37, no. 12, pp. 42-47, Dec. 1999.
[22]
{22} S. Kandula, D. Katabi, B. Davie, and A. Charny, "Walking the tightrope: Responsive and yet stable traffic engineering," in Proc. ACM SIGCOMM, Aug. 2005, pp. 253-264.
[23]
{23} T. Bressoud, R. Rastogi, and M. Smith, "Optimal configuration of BGP route selection," in Proc. IEEE INFOCOM, 2003, vol. 2, pp. 916-926.
[24]
{24} A. Akella, B. Maggs, S. Seshan, A. Shaikh, and R. Sitaraman, "A measurement-based analysis of multi-homing," in Proc. ACM SIGCOMM, Aug. 2003, pp. 353-364.
[25]
{25} D. K. Goldenberg, L. Qiu, H. Xie, Y. R. Yang, and Y. Zhang, "Optimizing cost and performance for multihoming," in Proc. ACM SIGCOMM , Sep. 2004, pp. 79-92.
[26]
{26} R. Mahajan, D. Wetherall, and T. Anderson, "Negotiation-based routing between neighboring ISPs," in Proc. USENIX Symp. Networked Systems Design Implementation, Boston, MA, May 2-4, 2005.
[27]
{27} J. Winick, S. Jamin, and J. Rexford, "Traffic engineering between neighboring domains," 2002 {Online}. Available: http://www.cs. princeton.edu/~jrex/papers/interAS.pdf

Cited By

View all
  • (2015)A novel framework to mitigate the negative impacts of green techniques on BGPJournal of Network and Computer Applications10.1016/j.jnca.2014.10.01248:C(22-34)Online publication date: 1-Feb-2015
  • (2012)Explicitly accommodating origin preference for inter-domain traffic engineeringProceedings of the 27th Annual ACM Symposium on Applied Computing10.1145/2245276.2245389(583-587)Online publication date: 26-Mar-2012
  • (2012)Rehoming edge links for better traffic engineeringACM SIGCOMM Computer Communication Review10.1145/2185376.218538542:2(65-71)Online publication date: 29-Mar-2012
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking
IEEE/ACM Transactions on Networking  Volume 15, Issue 4
August 2007
243 pages

Publisher

IEEE Press

Publication History

Published: 01 August 2007
Published in TON Volume 15, Issue 4

Author Tags

  1. BGP
  2. egress-point selection
  3. internet routing
  4. network operations and management

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 03 Mar 2025

Other Metrics

Citations

Cited By

View all
  • (2015)A novel framework to mitigate the negative impacts of green techniques on BGPJournal of Network and Computer Applications10.1016/j.jnca.2014.10.01248:C(22-34)Online publication date: 1-Feb-2015
  • (2012)Explicitly accommodating origin preference for inter-domain traffic engineeringProceedings of the 27th Annual ACM Symposium on Applied Computing10.1145/2245276.2245389(583-587)Online publication date: 26-Mar-2012
  • (2012)Rehoming edge links for better traffic engineeringACM SIGCOMM Computer Communication Review10.1145/2185376.218538542:2(65-71)Online publication date: 29-Mar-2012
  • (2010)Redundant multicast routing in multilayer networks with shared risk resource groupsComputers and Operations Research10.1016/j.cor.2009.12.00937:10(1731-1739)Online publication date: 1-Oct-2010
  • (2009)Fast network failure recovery using multiple BGP routing planesProceedings of the 28th IEEE conference on Global telecommunications10.5555/1811982.1812020(3841-3846)Online publication date: 30-Nov-2009
  • (2009)A Closed-Loop Control Traffic Engineering System for the Dynamic Load Balancing of Inter-AS TrafficJournal of Network and Systems Management10.1007/s10922-009-9142-417:4(343-370)Online publication date: 1-Dec-2009
  • (2008)Impact of hot-potato routing changes in IP networksIEEE/ACM Transactions on Networking10.1109/TNET.2008.91933316:6(1295-1307)Online publication date: 1-Dec-2008
  • (2008)On model-driven self-engineering of inter-domain trafficComputer Communications10.1016/j.comcom.2008.05.03131:14(3360-3371)Online publication date: 1-Sep-2008

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media