Interdomain Traffic Engineering

In recent years, there has been a tremendous growth of Internet users primarily due to the emergence of multimedia applications and services. With the rapid growth in Internet traffic, Internet Service Providers (ISP) acknowledge that network management is important for which to manage their networks efficiently. In particular, ISPs attempt to control traffic routing in their networks in order to optimize the usage of their network resources. Traffic Engineering (TE) is the set of techniques that optimize operational IP network performance. ISPs may use TE to dimension their networks in order to maximize the ability in carrying future customer traffic demands. As the Internet is hierarchically structured, TE can be divided into two types: intradomain and interdomain. In intradomain TE, the operator of an AS controls traffic routing within the network by either optimizing the link weights of the corresponding routing protocols or establishing Label Switched Paths (LSPs) through MultiProtocol Label Switching (MPLS). Typical intradomain TE optimization objectives are to minimize network bandwidth consumption and to achieve load balancing within the network. In fact, most of the previous work after the concept of TE was introduced focused on intradomain TE. However, since it has been discovered that interdomain resources are frequently congestion points and typically incurred with charges, optimizing their resource utilization has become necessary. Therefore, the aim of interdomain TE is to control traffic across multiple domains using optimization objectives such as to achieve load balancing over interdomain resources and/or to minimize peering costs.

This section of the Quality of Service Management Information Portal serves as a focal point for research related to interdomain traffic engineering.

General Description

The Internet is a large decentralized inter-network composed of more than eighteen thousand domains. From a business perspective, the relationship between any two domains can be classified into one of the following two types:

• Transit service (customer-provider relationship): This type of relationship exists commonly between low- and high-tier domains. Low-tier domains (typically stub domains) purchase transit services from higher-tier domains for Internet connectivity.

• Peering: This type of relationship exists commonly between neighboring domains that are roughly equal in size and at the same tier. The domains agree to simply exchange traffic without making any payment to each other.

Domains in the Internet can be classified into transit domains and stub domains. Transit domains offer transit services, i.e. interdomain traffic delivery across the Internet. Stub domains, on the other hand, are the leaf domains of the domain-level hierarchy. They only send or receive traffic, and do not provide transit services to any other domain. In general, the two types of domain have different interdomain traffic engineering objectives. The incentive for transit domains to perform interdomain traffic engineering is normally to optimize network resources so as to maximize their incoming revenue. On the other hand, stub domains compose more than 80% of domains in the Internet and most of them are multi-homed. Hence, their principal interdomain issue is how to minimize the monetary expense of subscribing to Internet transit services from their domains.

Another dimension for categorizing interdomain traffic engineering is inbound and outbound traffic engineering, which focus respectively on how to control interdomain traffic entering or leaving a domain. A domain may only require either inbound or outbound traffic engineering, or both according to its business objectives. For example, a domain that contains popular content providers generates a large amount of traffic that needs to be sent out of the network efficiently, and thus outbound traffic engineering is needed. On the other hand, domains that have a large number of multimedia application receivers (e.g., Internet TV/MP3 subscribers) are typically traffic consumers. They therefore need to perform inbound TE in order to control traffic injected into their networks. Finally, since transit domains normally exchange Internet traffic between each other, both inbound and outbound TE may be required. Currently, there are two implementation methods for interdomain traffic engineering:

• BGP-based: by configuring BGP route attributes such as local preference so as to influence the BGP route selection criteria.
• MPLS-based: by establishing interdomain LSPs across multiple domains.

Since most domains in the Internet are self-governed entities and are effectively in competition with each other for customers, it is natural that they perform interdomain TE individually without considering their neighbors. However, recent research has found that when adjacent domains perform their interdomain TE selfishly, not only is the global network performance not optimized, but also the interdomain TE strategies of each domain may adversely affect each other. In this case, routing instability may occur, as domains need to change their path selection strategies whenever the TE decisions of their adjacent domains change. Such instability is primarily due to interdomain TE policy conflicts between domains. A desirable way to achieve overall good TE performance is to encourage domains to negotiate with each other in order to obtain a compromising solution that benefits all of them. This is known as cooperative-based interdomain TE.

Cooperative-based interdomain TE relies on the negotiation between two adjacent domains to achieve an agreement on how traffic is routed between their networks. The TE objectives of the adjacent domains should be jointly considered in order to achieve a 'win-win' agreement that is satisfied by participating domains. Such an agreement can be determined through intelligent optimization methods, taking into consideration the topologies, TE objectives and traffic matrices of the two domains.

Tutorials/Presentations

• Presentations by Dr. Olivier Bonaventure

Publications

• Quoitin, B., Uhlig, S., Pelsser, C., Swinner, L. & Bonaventure, O., "Interdomain Traffic Engineering with BGP," IEEE Communications Magazine, Volume 41 (5), pp. 122 – 128, May 2003
• Yang, Y.R., Xie, H., Wang, H., Siberschatz, A., Krishnamurthy, A., Liu, Y. & Li, L., "On Route Selection for Interdomain Traffic Engineering," IEEE Network Magazine, Volume 19 (6), pp. 20-27, November-December 2005
• Feamster, N., Borkenhagen, J. & Rexford, J., "Guidelines for Interdomain Traffic Engineering," ACM SIGCOMM Computer Communication Review, Volume 33 (5), pp. 19-30, October 2003
• Goldenberg, D., Qiu, L., Xie, H., Yang, Y.R. & Zhang, Y., "Optimizing Cost and Performance for Multihoming," Proc. ACM SIGCOMM Conference, Portland, Oregon, USA, August-September 2004
• Bressoud, T., Rastogi, R. & Smith, M.A., "Optimal Configuration for BGP Route Selection," IEEE International Conference on Computer Communications (INFOCOM), pp. 916-926, March-April 2003
• Uhlig, S. & Bonaventure, O., "Designing BGP-based Outbound Traffic Engineering Techniques for Stub ASes," ACM SIGCOMM Computer Communication Review, Volume 34 (5), pp. 89-106, October 2004
• Chang, R, & Lo, M., "Inbound Traffic Engineering for Multihomed ASs Using AS Path Prepending," IEEE Network Magzine, pp. 18-25, March-April 2005
• Mahajan, R., Wetherall, D. & Anderson,T., "Negotiation Based Routing Between Neighboring Domains," Proc. Networked System Design and Implementation (NSDI), May 2005
• Ho, K.H., Wang, N., Trimintzios, P. & Pavlou, G., "Multi-objective Egress Router Selection Policies for Inter-domain Traffic with Bandwidth Guarantees," Proc. IFIP Networking Conference, Athens, Greece, May 2004
• Ho, K.H., Wang, N., Trimintzios, P., Pavlou, G. & Howarth, M., "On Egress Router Selection for Inter-domain Traffic with Bandwidth Guarantees," Proc. IEEE International Workshop on High Performance Switching and Routing (HPSR), Phoenix, Arizona, USA, April 2004
• Uhlig, S. & Quoitin, B., "Tweak-it: BGP-based Interdomain Traffic Engineering for Transit ASes," Proc. Next Generation Internet Networks Conference, pp. 75-82, April 2005
• Gao, R., Dovrolis, C. & Zegura, E., "Interdomain Ingress Traffic Engineering through Optimized AS Path Prepending," Proc. IFIP Networking Conference, Waterloo, Canada, May 2005.
• Quoitin, B. & Bonaventure, O., "A Cooperative Approach to Inter-domain Traffic Engineering," Proc. Next Generation Internet Networks (NGI) Conference, April 2005
• Amin, M., Ho, K.H., Pavlou, G. & Howarth, M., "Making Outbound Route Selection Robust to Egress Point Failure," Proc. IFIP Networking Conference, Coimbra, Portugal, May 2006
• Ho, K.H., Georgoulas, S., Amin, M. & Pavlou, G., "A Robustness Approach to Inter-AS Outbound Traffic Engineering," Proc. IEEE International Conference on Communications, June 2006
• Ho, K.H., Howarth, M., Wang, N., Pavlou, G. & Georgoulas, S., "Joint Optimization of Intra- and Inter-Autonomous System Traffic Engineering," Proc. IFIP/IEEE Network Operations and Management Symposium (NOMS), Vancouver, Canada, April 2006
• Ho, K.H., Pavlou, G., Georgoulas, S. & Amin, M., "A Route Deflection Approach to Minimize Routing Disruptions for Inter-AS Traffic Engineering," Poster, Proc. IEEE International Conference on Computer Communications (INFOCOM), Barcelona, Spain, April 2006
• Howarth, M., Boucadair, M., Flegkas, P., Wang, N., Pavlou, G., Morand, P., Coadic, T., Griffin, D., Asgari, H. & Georgatsos, P., "End-to-end Quality of Service Provisioning Through Inter-provider Traffic Engineering," Computer Communications, Volume 29 (6), pp. 683-702, Elsevier, March 2006

Related Links

• European Network of Excellence for the Management of Internet Technologies and Complex Services (EMANICS)
• European IST Projects MESCAL and AGAVE

Dissemination

The list of journals, conferences and technical societies related to interdomain traffic engineering does not mean to be exhaustive rather it is indicative. For additions/updates please contact the webmaster.

Journals

• IEEE Transactions on Network and Service Management
• Journal of Network and Systems Management
• IEEE Communication Magazine
• IEEE Network Magazine
• IEEE/ACM Transactions on Networking
• IEEE Journal on Selected Areas of Communications
• Elsevier Computer Networks
• Elsevier Computer Communications
• ACM SIGCOMM Computer Communications Review

Major Conferences

• IEEE International Conference on Communications (ICC)
• IEEE Global Communications Conference (GLOBECOM)
• IFIP/IEEE Network Operations and Management Symposium (NOMS)
• IFIP/IEEE International Symposium on Integrated Network Management (IM)
• IEEE International Conference on Computer Communications (INFOCOM)
• ACM SIGCOMM Conference

Technical Societies

• IETF Inter-domain Routing Chapter
• IEEE Technical Committee on Computer Communications (TCCC)

Software/Tools

• The Network Simulator (ns2)
• TOTEM
• SSFNET Simulator