The Internet is an interconnection of multiple networks called domains. Inter-domain routing is ensured by BGP which preserves each domain’s independence and announces routes arbitrarily chosen by domains. BGP messages carry no information concerning quality parameters of announced routes. The authors’ goal is to provide domains with information regarding the congestion state of other domains without any changes in BGP. A domain, which is aware of heavily congested domains, can choose a bypass instead of a route exhibiting possible problems with QoS satisfaction. They propose a mechanism which sends alert messages in order to notify domains about the congestion state of other domains. The major difficulty consists in avoiding flooding the Internet with signaling messages. The authors’ solution limits the number of alerts by taking advantage of the hierarchical structure of the Internet set by P2C and P2P relationships. Their algorithm is distributed and heuristic because it is a solution to an NP-complete and inapproximable problem. They prove these properties by reducing the Steiner problem in directed acyclic graphs to our problem of alert diffusion. The simulations show that our mechanism significantly diminishes the number of unavailable domains and routes compared to those obtained with BGP routing and with a theoretical centralized mechanism.
TopIntroduction
The Internet is an interconnection of multiple networks called domains. We may see it as an inter-domain network. The transmission in the Internet may have to transit through several domains. The Internet connectivity is discovered by BGP (Border Gateway Protocol) (Rekhter, Watson, & Li, 1995) which is deployed in all the existing domains. This protocol was exclusively designed to transport information about possibilities of domain connections preserving at the same time the domain confidentiality and their independence, notably by letting domains choose connectivity information to be diffused on individual basis. It is well adapted to inter-domain routing because, despite of its possibly slow convergence and the complexity of routers, it is scalable.
The best-effort approach on both levels (IP, BGP) allows for the current Internet functioning thanks to over-dimensioning. Taking into consideration the growing number of Internet users and the development of different types of Internet applications, the introduction of QoS (Quality of Service) mechanisms is unavoidable. There are three ways to introduce the QoS into the inter-domain routing:
• replacing BGP by a new protocol,
• modifying BGP in order to adapt it to carry QoS information,
• deploying another protocol to transport QoS information, a protocol which works independently of BGP but collaborates with it.
As it is impossible to replace BGP incrementally by another protocol, the first of the possibilities listed above has to be rejected. The second approach seems to be more realistic, despite of the fact that incremental deployment is impossible. However, some attempts such as q-BGP (Boucadair, 2005) were proposed, which keeps routing tables for each class of service. This protocol also allows domains to have their own QoS criteria which are not necessarily adapted to being managed by normalized service definitions. Moreover, it does not take into account a current network state because a congestion detection mechanism is absent. In our opinion the most promising approach is the last one. In the next paragraph we discuss directions which have been taken in order to apply it in practice.
We consider two paradigms for the introduction of QoS into the Internet: flow-based and connectionless. The first one is based on an individual flow management. It requires the cooperation of network elements in order to set paths which satisfy required quality constraints and to allocate resources for individual flows. Propositions built on the flow-based paradigm are implemented on the intra-domain level (Braden, Zhang, Berson, Herzog, & Jamin, 1997). Generally, the flow-based paradigm is not adapted to the inter-domain level. The number of flows present on this level is too great to be managed individually. Moreover, domains are not interested in revealing information about their resources to other potentially competing domains. The flow-based paradigm should thus not be totally rejected as it is the only way to guarantee strict QoS requirements (Bless, 2004; Pan, Hahne, & Schulzrinne, 2000; Pelsser & Bonaventure, 2006). This paradigm may be applied to a small number of critical requests which need to satisfy strict QoS requirements. In practice, the number of strict QoS requests may be limited by assigning either a prohibitive price or an administrative restriction to them. For the other demands for QoS without strict guarantee, the second paradigm which is connectionless should be used.
The principle of the connectionless paradigm is represented by the rejection of flow management. Packets are divided into classes and the priority traffic, i.e. packets of the most privileged class, is, indeed, treated with priority. The connectionless paradigm is at the heart of the DiffServ architecture (Blake, Black, Carlson, Davies, Wang, & Weiss, 1998).