Interdomain QoS Paths Finding Based on Overlay Topology and QoS Negotiation Approach

1. Introduction

The real time multimedia services, delivered on Internet networks, raised new challenges for the network regarding the end to end (E2E) quality of services (QoS) control in order to ensure the proper delivery of the services from content provider (source) to content consumer (destination). But, despite a lot of studies and research done, the actual traffic processing in real Internet deployments is still mostly best effort. Several approaches have been proposed, focused on provisioning aspects – usually solved in the management plane - and then performing monitoring and adjustments in the control plane: e.g., well known dynamic techniques have been standardized, like IntServ, Diffserv, or combinations. Offering multimedia services in multi-domain heterogeneous environments is an additional challenge at network/ transport level. Service management is important here for provisioning, offering, handling, and fulfilling variety of services. Appropriate means are needed to enable a large number of providers in order to extend their QoS offerings over multiple domains. To this aim, an integrated management system can be a solution to preserve each domain independency while offering integration at a higher (overlay) layer in order to achieve E2E controllable behaviour.

This chapter deals with the problem of establishing QoS enabled aggregated multi-domain paths, to be later used for many individual streams. A general framework is described exposing the ideas of overlay topologies solutions. Then a simple but extendable procedure is proposed, running at management level, to find (through communication between domain managers) several potential inter-domain end to end paths. Then, using a resource negotiation process performed also in the management plane, QoS enabled aggregated pipes, spanning several IP domains, are established. All these functions are performed at an overlay level, based on abstract characterization of intra and inter-domain capabilities delivered by an intra-domain resource manager. This is important in the sense that each domain (or, Autonomous System – AS) can preserve its own independency in terms of resource management. The subsystem is part of an integrated management multi-domain system, dedicated to end to end distribution of multimedia streams.

The QoS path finding solution presented here is not like a traditional routing process: it is not implemented on routers, and it does not choose a route between network devices, but between two or more nodes of an overlay virtual topology described at inter-domain level. Together with the intra-domain QoS routing available inside each network domain we will obtain an E2E QoS routing solution.

We recall that in our context, QoS enabled aggregated pipes are established (at request of a Service Provider entity), in advanced to the real traffic flow transportation. These are mid-long term virtual links. Related to this, the main advantage of the proposed solution is that, by separating the process of path finding from the QoS negotiation, the path searching process doesn’t need to work real time. So, one can find several paths in very complex overlay topologies. Also, the overlay topology is made simple by virtualisation: each domain (including its manager) is considered as an abstract node in the virtual topology. Therefore the solution is scalable and capable to work in cases of large topologies, being no need for a hierarchical approach.

This Chapter is organized as follows: the Section 2 contains the state of the art in QoS inter-domain routing; the Section 3 shortly describes the general Enthrone architecture focusing on the service management at the network level. The Section 4 introduces the proposed QoS inter-domain path finding solution. Section 5 presents details about the implementation and Section 6 contains conclusions, possibilities of extensions and open issues.

2. State of the art

Because our approach deals with QoS path finding and routing, a short overview of the available approaches for QoS routing is presented below [13] [14] [15] [17] [18]. We distinguish between intra - and inter-domain QoS problems.

The intra-domain QoS routing solutions could be divided in two major approaches.

Classically, intra-domain QoS routing protocols run on the routers and find paths with QoS constraints from source to destination. While having the advantage of being an Internet philosophy compliant solution, i.e., completely distributed and dynamic, this approach does not offer at the domain level an image of the available resources. For mid-long term paths with QoS guarantees a centralized solution is better. This introduces a domain central manager having knowledge of the total resource allocation inside the domain. To find the routes it could use an algorithm to determine QoS routes between source and destination. In this case the QoS routing process would be run by a dedicated module of the domain manager. Note that such a solution would centralize completely the routing and would not benefit from Internet intra-domain routing protocols. Other approach is that the manager can collect information from routers which are capable to compute QoS constrained paths. The main thing is that the resulted routes are installed on the network equipments at the initiative of the manager which commands such actions to a network controller. Usually the QoS routing process is triggered by a new request addressed to the manager for a QoS path through the domain.

For inter-domain QoS routing also we can distinguish between two kinds of approaches. The first one proposes enhancements for the BGP protocol in order to support QoS features. The BGP advertises QoS related information between autonomous systems (ASes), and the routing table is build taking into consideration this additional QoS information. The Q-BGP protocol, proposed in MESCAL project [20], is such an example.

Another category of inter-domain QoS routing solutions are based on the overlay network idea [13] [14]. An overlay network is built, which abstracts each domain with a node, represented by the domain service manager, or with several nodes represented by the egress routers from that domain. Then protocols are defined between nodes for exchanging QoS information and, based on this information, QoS routing algorithms are used to choose the QoS capable path. In [13] a Virtual Topology (VT) solution is proposed. The VT is formed by a set of virtual links that map the current link state of the domain without showing internal details of the physical network topology. Then a Push and a Pull model for building the VT at each node are considered and analyzed. In the Push model each AS advertise their VT to their neighbor ASes. This model is suited for small topologies. In the Pull model the VT is requested when needed, and only from the ASes situated along the path between source and destinations, path which is determined using BGP routing information. If BGP kept several routes between source and destination than the VTs for each domain situated along the founded paths are requested. Based on this VTs information the QoS route from source to destination is calculated. After that an end to end QoS negotiation protocol is used to negotiate the QoS resources along the path.

One problem with these solutions is that they suppose that the ASes make available for others their virtual resource topology information. This requirement could be not accepted by the actual network providers, due to their confidentiality policy regarding their resource availability.

Also, these solutions are based on an end to end QoS negotiation process. After the QoS path is found, the negotiation process is started. The QoS routing process previously performed in advance would increasing the chance of negotiation success, but the overall process implies two QoS –related searching processes: building the QoS topology and secondly negotiation in order to reserve resources.

This chapter proposes a simpler approach by separating the process of path searching in a virtual topology (built by abstracting each domain with a node) from the process of QoS negotiation (QoS searching path). By combining these two processes we will obtain a QoS inter-domain routing solution.

This solution has been developed and integrated in an E2E QoS management system [2] [8] [9] [10]. The system was proposed and implemented by an European consortium in the FP6 European project ENTHRONE [2] [3] [4] [5], and continued with ENTHRONE II [6] [7] [8]. The ENTHRONE project developed an integrated management solution to solve the end-to-end QoS – enabled transportation of multimedia flows over heterogeneous networks, from content sources to terminals. It proposes an integrated management solution that covers the entire audio-visual service distribution chain, including protected content handling, distribution across networks and reception at user terminals.

The overlay QoS path finding solution is based on the overlay network topology abstracting each pair (IP domain + manager) with a node. The overlay network graph in this case is only a connectivity one, with no information about the resources available intra and inter-domain. Several alternative inter-domain paths are computed, at overlay level, for each destination domain. Then, the end to end QoS negotiation mechanism is used to ask for and to reserve resources. Together they will act as a QoS inter-domain routing algorithm.

3. Enthrone End to End QoS Management System

As mentioned before the ENTHRONE project, IST 507637 (continued with ENTHRONE II, IST 038463) European project, had as main objective the delivery of real time multimedia flows with end to end quality of services (QoS) guarantees, over IP based networks. To achieve this goal, a complex architecture has been proposed, which cover the entire audio-visual service distribution chain, including content generation, protection, distribution across QoS-enabled heterogeneous networks, and delivery of content at user terminals [2] [3] [4] [5] [6] [7]. A complete business model has been considered, containing actors (entities) such as: Service Providers (SP), Content Providers (CP), Network Providers (NP), Customers (Content Consumers – CC), etc.

3.1. Enthrone basic concepts

ENTHRONE has defined an E2E QoS multi-domain Enthrone Integrated Management Supervisor (EIMS). It considers all actors mentioned above and their contractual service related relationships, Service Level Agreements (SLA) and Service Level Specifications (SLS), as defined in [2] [3] [4] [5] [6] [7]. One of the main EIMS components is the service management (SM). It is independent of particular management systems used by different NPs in their domains, and it is implemented in a distributed way, each network domain containing Service Management entities. They are present in different amounts in SP, CP, NP, CC entities, depending on the entity role in the E2E chain. The SM located in NPs should cooperate with each IP domain manager and also with other actors in the E2E chain.

Figure 1 shows the general architecture and emphasizes the cascaded model for pSLS negotiation.

Figure 1.

Forwarded cascaded model for pSLS negotiation.

Legend:

EIMS@CP, EIMS@SP, EIMS@NP – ENTHRONE Integrated Management Supervisor at: Content Provider (CP), Service Provider (SP) and Network Provider (NP)

sTVM –Source TV and Multimedia Processor ( Content server)

AAN – Access Aggregation Network; AANP – AAN Provider

RM@AANP – Resource Manager of AAN (it is ENTHRONE compliant), TM Terminal Manager

ENTHRONE supposes a multi-domain network composed of several IP domains and access networks (AN) at the edges. The CPs, SP, CCs, etc., are connected to these networks. The QoS transport concepts of ENTHRONE are shortly described below.

First, QoS enabled aggregated pipes, to be negotiated based on forecasted data (and later installed in the network), span the core network, which is part of the multi-domain network. They are mid-long term logical pipes built by the Service Management entities. The aggregated QoS enabled pipe, called pSLS pipe (we also will use the term pSLS-link), is identified by the associated pSLS agreement (Provider SLS) established between the Network Providers, in order to reserve the requested resources. Each pSLS-link belongs to a given QoS class, [20].

Then, slices/tracks of pSLS-links are used for individual flows based on individual cSLA/SLS contracts, concluded after CC requests addressed to the SP. An individual QoS enabled pipe is identified by a cSLS agreement, which is established between the manager of the Service Provider (EIMS@SP) and a CC for reserving the necessary resources for the requested quality of service. Several cSLSs pipes are included at the core network level by an aggregated pSLS pipe, belonging to the same QoS class.

In the data plane of core IP domains, Diffserv or MPLS can be used to enforce service differentiation corresponding to the QoS class defined. In the ANs, the traffic streams addressed to the users (Content Consumers) is treated similar to the intserv, i.e. individual resource reservations and invocations are made for each user.

3.2. Service Management at Network Provider

The EIMS architecture at NP (EIMS@NP) contains four functional planes: the Service Plane (SPl) establishes appropriate SLAs/SLSs among the operators/ providers/customers. The Management Plane (MPl) performs long term actions related to resource and traffic management. The Control Plane (CPl) performs the short term actions for resource and traffic engineering and control, including routing. In a multi-domain environment the MPl and CPl are logically divided in two sub-planes: inter-domain and intra-domain. Therefore, each domain may have its own management and control policies and mechanisms. The Data Plane (DPl) is responsible to transfer the multimedia data and to set the DiffServ traffic control mechanisms to assure the desired level of QoS.

One main task of the EIMS@NP is to find, negotiate and establish QoS enabled pipes, from a Content Server (CS), belonging to a Content Provider, to a region where potential clients are located. Each pipe is established and identified by a chain of pSLS agreements, between successive NP managers. The forwarded cascaded model is used to build the pSLS pipes [5]. The pipes are unidirectional ones. An E2E negotiation protocol is used to negotiate the pSLS pipe construction across multiple network domains [5].

The process of establishing a pSLS–link/pipe is triggered by the SP. It decides, based on market analyses and users recorded requirements, to build a set of QoS enabled pipes, with QoS parameters described by a pSLS agreement. It starts a new negotiation session for each pSLS pipe establishment. It sends a pSLS_Subscribe_request to the EIMS@NP manager of the Content Consumer network domain. The EIMS@NP manager performs the QoS specific tasks such as admission control (AC), routing and service provisioning. To this aim it splits the pSLS request into intra-domain respectively inter-domain pSLS request. It also performs intra-domain routing to find the intra-domain route for the requested pSLS, and then it performs intra-domain AC. If these actions are successfully accomplished, and if the pSLS pipe is an inter-domain one, then the manager uses the routing agent to find the ingress point in the next domain, does inter-domain AC and then send a pSLS Subscribe request towards the next domain. This negotiation is continued in the chain and up to the destination domain, i.e., the domain of the CC access network. If the negotiation ends successfully the QoS enabled pipe is considered logically established along the path from source to destination.

The Figure 2 shows the signalling message sequence associated to the pSLS-link negotiation.

The actual installation and configuration of routers is considered in ENTHRONE a separate action and is done in invocation phase in a similar signalling way, plus the “vertical” commands given by EIMS@NP to the intra-domain resource manager.

After the pSLS pipe is active (i.e. subscribed and invoked) the Service Provider is ready to offer the new service to the users from the access network situated at the end of the pipe. Now the process of cSLS individual agreements establishment, for this new pSLS pipe, could be started.

Figure 2.

pSLS negotiation for QoS enabled path establishment (negotiation and installation).

4. Finding an end to end path with guarantied quality

4.1. General considerations

The main concepts of ENTRONE as stated in [8] are:

• E2E QoS over multiple domains is a main target of EIMS.

• But each AS has complete autonomy regarding the network resources, including off-line traffic engineering (TE), network dimensioning and dynamic routing.

Each Network Service Manager (cooperating with Intra-domain network resources manager) is supposed to know about its network resources in terms of QoS capabilities. ENTHRONE assumes that each AS manager has an abstract view of its network and output links towards neighbours in a form of a set of virtual pipes (called Traffic Trunks in ENTHRONE I, see [5] [6]) each such pipe belonging to a given QoS class.

A solution to the route finding problem is to define/use routing protocols with QoS constraints called QoS routing protocols. They can find a path between source and destination satisfying QoS constraints.

While finding the QoS path is only a first step, then maintaining the QoS with a given level of guarantees during the data transfer requires additional actions of resource management, including AC applied to new calls.

EIMS@NP management system performs these tasks. It is a centralized manager knowing the topology and resources of a domain: otherwise, if using Diffserv only, in the core one cannot hope to have guaranteed QoS. Being a central management node for a network domain, a centralized QoS routing solution is appropriate inside the domain.

On the other side the multiple domain pSLS-links should also belong to some QoS classes and therefore inter-domain QoS aware routing information is necessary to increase the chances of successful pSLS establishment when negotiating the pSLSes. Several approaches are possible for inter-domain provisioning of QoS-enabled routing for ENTHRONE system, and they will be presented in the next sections. These solutions are based on the overlay topology approach.

4.2. Overlay QoS virtual topologies

The overlay solutions come out of the ideas expressed in the section above. Also this approach has been considered in [13] [14] which propose a Virtual Topology Service (VTS) offering multiple domains QoS enabled virtual pipes. The VTS abstracts the physical network details of each AS and can be integrated with BGP. Note that the pSLS links already proposed in the ENTHRONE project are similar.

Therefore one can define two separate types of network services providers: NP itself owning and responsible of the network infrastructure, which is actually an Infrastructure Provider; the overlay (virtual) network services provider (ONSP), which in our case is represented by EIMS@NP, which establishes agreements with other similar providers the final target being to offer QoS enabled pSLS-links.

In the ENTHRONE system each AS can assure QoS enabled paths towards some destination network prefixes while implementing its own network technology: DiffServ, MPLS, etc. Each AS is seen in an abstract way as an Overlay Network Topology (ONT) expressed in terms of TTs (traffic trunks) characterized by the bandwidth, latency, jitter, etc. The Overlay Network Service (ONS) is responsible for getting the ONT of each AS on a path in order to give to the source AS information related to QoS towards a given destination. The End to End Negotiation Service, which is supported by the EIMS@NP, will then negotiate the pSLS contracts with the chosen domains in order to reserve resources and then to invoke them. The ONS can be modeled in two ways, [13] [14]: a proactive (Push) model and a reactive one (also called pull or on demand) model in order to obtaining the overlay (virtual) topologies of other ASes.

In the proactive case every AS advertises its ONT to other ASes without being requested for, while the proactive model assumes that overlay topologies are obtained on demand by an AS which is interested to reach a given destination prefix.

The proactive (push) model has the advantage offered by traditional IP proactive routing protocols: the ONTs of other ASes are already available at a given AS because they are periodically advertised among AS managers; therefore latency in offering a route to a new request is small. The advertisement can also be done at each AS manager initiative, so this model allows promotion of some routes to other domains. This can be subject of policies. The dynamicity is high (advertisements can be event driven). But the proactive model is more complex than the reactive model. Scalability problems may exist, because of high control traffic volume and also flooding the neighbor ASes with (maybe) not needed information. The managers will keep information on some routes that are of no interest for them (yet).

The reactive (on-demand) model is simpler than the proactive model, because an AS will query each domain of a given path to get the ONTs. No advertising mechanism is necessary. The scalability is higher because only the ONTs of the chosen routes will be obtained. Studies show that the mean E2E communication in the Internet traverses between 3 and 4 domains. Therefore the number of domains to be queried to obtain the ONTs is small. The pull model latency when finding a path is higher (need time for queries and calculations). The updates of ONT knowledge is not event driven because the lack of an advertisement mechanism. In [13], a notification message is proposed to solve this problem, i.e., to allow a domain to notify other domains about local events. Then the source domain can invoke the VTS to obtain a new set of ONTs.

Figure 3.

Overlay network topology of ASk – example.

4.3. Proactive approach

Each AS Manager (e.g. NSM@NP manager in ENTHRONE case) knows its ONT. Figure 3 presents a graphic diagram showing several ASes. The ONT of ASk includes all unidirectional TTs of ASk. One TT can be internal to ASk or external, linking the ASk with other neighbor domains. One external TT is defined from an egress point (router) of the domain up to the input of an ingress router of a neighbor domain. Each TT belongs to a given QoS class and may be characterized by parameters like bandwidth (B), delay (D), etc. It is the responsibility of the AS manager to find out these values by using internal mechanisms. Two styles, different in terms of flexibility, can be applied in the proactive solution, as described below:

4.3.1. Maximum flexibility: Proactive ONT advertisements

Each AS Manager advertises its ONT to the neighbors, and also the ONTs learned from other domains. In such a way (similar to the procedures used in the link-state routing protocols) each AS manager will become aware of the inter-domain overlay virtual topology and, applying some constrained routing algorithm, can select its paths to given destinations. The Figure 4 shows this process.

This solution is based on flooding so it exposes scalability problems. It can be useful for “regional” scenarios in which the number of ASes is not high. In [13] it is mentioned that a regional scenario may be formed by “condominiums of domains”; group of domains which agreed on advertising overlay topologies to each other. All the ASes making part of the same condominium will eventually know the overlay topologies of other ASes. In such regions of domains one could apply different business policies/rules and create new relationships to make the interactions more customer-oriented.

Figure 4.

ONT advertisement.

4.3.2. Minimum flexibility: Proactive vector paths advertisements

At the other extreme there is a solution in which each AS knows its ONT and some path vectors (in the BGP meaning) reported by other ASes. In such case the advertisements do not contains ONTs but vector paths (in the sense of BGP, but having additional QoS information). Each AS wanting to reach a given destination will compute the best path(s) using its ONT and paths reported by other ASes (based on constrained routing algorithm). The degree of freedom in path selection is minimum in the sense that a given AS manager can only select among paths proposed by the other domains and maybe benefit from its own ONT. But the scalability is better. The Figure 6 shows this solution in a simplified manner.

Figure 5.

Phase 1: Path advertisments from ASm, ASn sent to ASk for destination ASz.Rj.

Figure 6.

Phase 2: Paths computed and selected by Ask.

We distinguish two phases:

• ASk receives from the ASn advertisements messages having the generic form M[Path(n-x)], indicating a path vector to destination – ASz domain, Router Rj. In a similar way, other messages are received from other domains. Note that actually these messages are not synchronized.

ASk uses its own ONT values and computes one or more “best” or “equivalent” paths for each QoS class, Figure 6 shows two such paths computed and selected as acceptable ( to be also advertised to other domains)

4.4. On demand approach

The domains do not advertise their overlay topologies to the neighbouring domains. The ONT is obtained by each domain at request if it wants to know the ONTs of other domains. When a given AS needs to find an E2E QoS-enabled inter-domain route, it queries its BGP local table and determines the possible routes towards the destination. BGP delivers a list of ASes to follow for a path to destination. Then the initiator domain can query each domain on the path chain towards the destination and gets the ONT of the domains specifically for that route. Based on this the initiator domain can get more routes to the destination than BGP offers.

Figure 7.

Hub model to obtain the ONTs in the on-demand model.

Figure 7 shows an example in which the domain ASk needs to reach a destination ASz with a required QoS set of values for this path.

The manager of the domain ASk queries its local BGP table and finds the BGP route to the destination ASz, through ASp, ASq, ASr. The ASk manager invokes the overlay topology service (OTS) to obtain the ONT of each domain. Figure 7 presents for this a hub model. Note that there can be more than one BGP path to the destination ASz. Therefore ASk can recursively query each domain in each path and find the best path towards the destination.

After obtaining all the ONTs of each possible route towards domain ASz, the source domain ASk can use a Constraint Shortest Path (CSP) algorithm to find the best route that fits the QoS requirements. The path calculation can be done using only one attribute or more than one (bandwidth, latency, loss). It may happen that after obtaining the ONTs of each route towards a destination, the ASk can realize that there is no route that satisfies the QoS requirements. A solution to this is proposed in [13]: to make use of the Internet hierarchy to collect more alternative routes towards a given destination. Taking into account the hierarchy of ASes in the world, going upwards this hierarchy may produce several routes which have been not advertised initially by BGP.

Suppose that the stub domain ASk is multi-homed with domains ASq and ASp and it has received two BGP routes from its providers to reach prefixes at domain ASz. The first route is ASq, ASr, ASz and the second is ASp, ASz. Then, to increase the number of paths to query for ONTs, the OTS can invoke its providers and asks other BGP routes that were not initially advertised. In this case, domain ASp would return to domain ASk the paths ASu, ASz and ASz towards ASz,

So, ASk will have one more route available. In general this procedure can be used when a domain is multi-homed

4.5. The proposed overlay inter-domain QoS path finding solution

We proposed a simplified version [1], which takes into account the following assumption regarding the specific characteristics of the Enthrone system:

• The number of E2E QoS enabled pipes is not very large because they are long term aggregated pipes.

• The number of NP entities is much lower than the number of routers.

• The EIMS@NPs are implemented on powerful and reliable machines, having enough computing and storage capabilities.

• The inter-domain core IP topology is stable during the inter-domain routing process; this is fulfilled within the assumptions of this work.

This solution is also based on the idea of Overlay Virtual Network (OVN) similar as in [13], but the OVN consists only of network domains (autonomous systems) abstracted as nodes. Each node will be represented by an EIMS@NP in this Overlay Virtual Network. This virtual network contains only information on connectivity between the domains, represented by the EIMS@NP nodes, or additionally static information regarding the inter-domain QoS parameters: links bandwidth, maximum jitter and delay, mean jitter and delay, etc.

This overlay virtual connectivity topology (OVCT) can be learned statically (offline) or dynamically.

The statically approach considers that the OVCT is built on a dedicated server – a topology server, like in the Domain Name Service (DNS). When a Network Provider wants to enter in the Enthrone system, then its EIMS@NP should register on this topology server. The topology server will return the Overlay Virtual Connectivity Topology. So we will consider that each EIMS@NP has the knowledge of this connectivity topology.

In the dynamic case each EIMS@NP, if it wants to build the OVCT, will query its directly linked (at data plane level) neighbour domains’ managers. It is supposed that it has the knowledge of such neighbours.

Each queried EIMS@NP returns only the list of its neighbours. At receipt of such information, the queerer EIMS@NP updates its topology database (note that this process is not a flooding one as in OSPF). Then it queries the new nodes learned and so on. The process continues until the queerer node EIMS@NP learns the whole graph of “international” topology.

As we mentioned above the graph contains as nodes the EIMS@NPs which means that is made from the Network Service Managers of Enthrone capable domains, as shown in Figure 8.

Figure 8.

Overlay Virtual Connectivity Network.

If the Enthrone system will be implemented at large scale the number of nodes in the graph will be large, which means that the time required calculating the routing table will be also large. But because the topology structure changes events (adding new EIMS domains) are not frequent (it might happen at weeks, months), the topology construction process could run at large time intervals (once a day for example). In this case the routes calculation is triggered also at large time intervals, which means that there are no real time constraints. Another consequence is that the messages used to build the OVCT will not overload significantly the network. Enthrone capable domains can be separated by normal domains, with no Enthrone capabilities. In this case we consider that static initially QoS enabled pipes are built between Enthrone capable domains, pipes crossing the Enthrone non capable domains. The domains (Enthrone non capable) will be transparent for the Enthrone domains.

On the graph learned each EIMS@NP can compute several paths between different sources and destinations, thus being capable to offer alternative routes to the negotiation function.

The number of hops is used as a primary metric for the path choosing process. By the “hop” term we refer to a node in the Overlay Virtual Topology.

The process of route selection is as follows:

• When a request for a new pSLS arrived at one EIMS@NP, this will select the best path to the destination (the next EIMS@NP node that belong to this path), based on the overlay routing table.

• After the next hop is selected, the EIMS@NP will check if it has an intra-domain QoS enabled path for this route, i.e., between an appropriate ingress router and an egress router to the chosen next hop domain. If there is no such QoS enabled route, the next hop EIMS@NP node is selected from the overlay routing table.

• In case that a QoS enabled route intra-domain is found, the EIMS@NP, based on mechanisms defined in Enthrone, triggers a request for a new pSLS or a modified pSLS negotiation to the chosen EIMS@NP neighbor.

• This process continues until the destination is reached. If the negotiation ends with success than the pSLS pipe with guaranteed QoS parameters is found. If the process fails then the EIMS@NP will choose another overlay path to the destination and starts a new negotiation.

In Figure 9 the messages sequence for pSLS negotiation process in the case of multiple paths towards the destination is shown. The Service Provider decides to build a pSLS enabled pipe between a source located in the NP1 domain and a destination located in NP5 domain. We consider for this example that the working overlay topology is the one given in Figure 8. One can see that we have four possible routes between NP1 and NP5 domains. The first two of them, in terms of cost value, are the routes through NP6 and NP7 respectively. In Figure 9 it is illustrated the case when the pSLS negotiation along the route NP1-NP6-NP5 fails, due to admission control rejection in NP6 domain, either on intra-domain pipe inside NP6 domain, or on the inter-domain pipe between the NP6 and NP5 domains.

When it receives the rejection response at the pSLS subscription request the NP1 domain checks for an alternate route towards the NP5 domain. It finds the route through the NP7 domain and starts a new negotiation using this new route. This negotiation ends successfully, so the QoS enabled pipe between NP1 and NP5 will follow the route NP1-NP7-NP5.

This solution has the advantage of being simple and that it not require at an AS the knowledge of current traffic trunks for the other network domains as in [13].

A drawback of our solution (proposed above) is a larger failure probability in negotiating a segment (therefore a longer mean time for negotiation process), if comparing with solutions which calculate the QoS path before the negotiation process. The latter approach increases the probability that the negotiation finished with success at the first try.

The path finding process described above is not based on BGP information at all. BGP is used only for best effort traffic. The process of QoS routing takes place at service management level. But it is possible in principle to use such BGP information.

5. Routing Tables

5.1. Design Details

As mentioned before this solution is based on the knowledge of the overlay network connectivity topology. The topology can be kept in a form of a square matrix. The dimension M is equal to the number of nodes in the overlay topology network. Each entry rij, has an integer value. A zero value means that there is no direct connectivity between the nodes i and j. A value different from zero, value 1 for example, implies that there is a direct connection between the two nodes: Lij represents the link between nodes i and j (more precisely, between the two domains there are some linked routers). Because the matrix is a sparse one it can be easily compress in order to be stored in case that the dimension M is large.

Based on this overlay topology each EIMS@NP builds a routing table which contains, for each destination node in the network, several possible paths to this destination node, and the costs associated with each of these paths. Because in the routing table several entries will exists for each destination, the QoS negotiation process will be able to be carried on successively on multiple paths, increasing the probability that a path fulfilling the QoS requirements is found.

Figure 9.

MSC for QoS negotiation in case of multiple paths towards a given destination.

Because the number of possible paths from source to a certain destination could be high we have limited it to the first four ones, with the lowest costs. If the number of neighbours are less than four, than the number of possible routes towards a destination is limited to this number. It is used the same principle as in the case of distance vector protocols. In the case when there are several paths to the same destination EIMS@NP node, using as first next hop the same node, in the routing table we will store the best cost of all the possible paths going through that node.

This is not a limitation because in our case the routing decision is taken hop by hop so the source node has no idea what route to the destination will be chosen at the node where the paths are splitting. An EIMS@NP does not need to keep the whole path information (but the total cost only) because it cannot influence the route chosen decision at the next hops along the path.

Let’s suppose that the EIMS@NPk node has the neighbour nodes EIMS@NPm, EIMS@NPn, EIMS@NPp. The routing table from EIMS@NPk node to EIMS@NPl node will be:

Destination	EIMS@NP l	EIMS@NP l	EIMS@NP l
Nex Hop	EIMS@NP m	EIMS@NP p	EIMS@NP n
Cost (Nb of hops)	5	0	3

Table 1.

Routing table at node K for node L destination.

The EIMS@NP at node k builds such a record for each node in the overlay network. This process, of searching several possible paths for each possible destination, in this overlay network topology, is an expensive one in terms of calculation. But based on the assumptions presented above, which are realistic ones, if such a management system will be implemented in the network domains, this routing table building process will be run only on topology updates, which means at very long time intervals. Such a process will put low computing overhead on the Service Manager. Also, it could be scheduled to run on intervals with low management activity [5]. Taking this in consideration, it could be considered that the routing table is a static one, and the route search process reduces to a simple database search one. We do not need to run the searching algorithm for each pSLS subscription request. It is enough to search, in the routing table, the route to the destination with the smallest cost, and forward the request to the chosen next node. If the negotiation for QoS parameters along this path failed, then we will chose the next path, in terms of cost, from the routing table.

5.2. Possible Improvements

It is said that the solution did not take into consideration any QoS parameters, in the first phase, for path building process. This task left for the QoS negotiation process.

A possible improvement is to take into account some general data about the QoS parameters, in the path finding phase. For example, based on agreements with Service Managers of some domains, or based on some general QoS parameters of the domains, the Policy Based Management module could associate different costs for the links in the topology matrix. It is supposed that domains agreed to share these parameters, such as: the min/mean/max delay and jitter, introduced by the domain. In such a way the Policy module could influence the routing decision process. In this case the matrix element rij could have the value Cij if the link Lij exists. The value Cij is the cost for the link Lij, and could be established by weighting appropriately the general QoS parameters mentioned above. These weights could be established by the domain administrator and transmitted to the Policy module.

The cost of a link could be also modified based on statistics regarding the acceptance or rejection rate of previous negotiated pSLS pipes. For example, if some domain with a good link cost rejects several times the requesting domain could modify the costs of the links crossing that domain.

When the path cost is computed it could be taken into account the existence of resource price agreements between some domains. These agreements could be negotiated using pull model, based on some statistics. For example an EIMS@NP node has two different paths towards a destination with similar path costs. It chose the path with a better cost, but it also could periodically request resource price information from both neighbour nodes crossed by the two paths. If the second node has available resources and is interested to carry traffic from the source domain, it will propose a better resource price as a response to resource price requests. So the EIMS@NP source node could modify the routing table by improving the path cost for the second path, and the future pSLS pipe requests will be routed through the second path. Such a resource price communication could be easily implemented because the EIMS@NP managers are built as web-services, which implies very flexible communication capabilities.

5.3. Overlay topology building

For our solution we have chosen to build the overlay topology by means of successive interrogations of all the available nodes. The node which decides to build/refresh overlay the topology starts to interrogate all the other overlay nodes about their neighbours. It starts with its direct connected neighbours and then continues interrogating the new found neighbours, and so on.

For the EIMS@NP implementation we have used the web service technology. The interfaces between the EIMS@NP modules are implemented using WSDL language. The interdomain path finding WSDL interface it is used by EIMS@NP to interact with other EIMS@NPs in order to build the overlay topology used to search for interdomain overlay paths.

The interdomain path finding WSDL interface has defined the following messages:

• getEimsNeighborsRequest ()

• getEimsNeighborsResponse(EimsNeighborsArray eimsNeighbors)

• getDomainQoSRequest ()

• getDomainQoSResponse(DomainQoS qos)

The first two messages are used by the Overlay Path Building module from EIMS@NP subsystem to build the overlay topology. The response message contains an array with all the neighbours of the interrogated domain, and their associated data about the web services addresses, identification, IP addresses.

The next two messages are used to get general information about the QoS parameters of the domain: min/max/mean delay and jitter, mean transit cost, max bandwidth. These values refer to the transit parameters for the domain. We have considered that such information could be offered by each domain without affecting its confidentiality policy. These parameters are used to establish the cost associated with a link between two neighbour domains. For establishing the cost we have weighted the normalized values for these parameters. The weights were chosen arbitrarily, such as their sum to be one. No studies have been done to find the optimal values.

The format of messages parameters are given in table 2.

Table 2.

Data type section for the interdomain path finding WSDL interface.

In order to be able to perform the pSLS negotiation and to obtain the overlay topology we have defined several database tables used to store the data required by the above mentioned operations. These tables are shortly described next:

• Overlay_topology table – it contains data about each EIMS node in the topology, such as the addresses of the web-services available, the IP address, the domain identifier, and the QoS parameters. It is updated by the Inter-domain Overlay Path module at each overlay topology building cycle. It is used by the overlay routing process to build the overlay topology matrix used in the overlay route searching process.

• Eims_neighbors table – stores information about the neighbours for each EIMS node contained in the overlay_topology table. It is also updated by the Inter-domain Overlay Path module at each overlay topology building cycle.

• Overlay_interdomain_routes table – is used to store several alternative routes towards a destination overlay node. The number of alternative routes is limited to four. It is managed by the overlay routing process.

• Local_eims table – stores information about the local NetSrvMngr@NP such as: IP address, web services ports, domain Id. It is managed by the system administrator.

• Border_routers table – stores information about the local domains border routers. It contains the border routers IP address and neighbour EIMS reached through this border router. It is managed by the system administrator.

• Access_networks table – stores information about the access networks for the local domain. It contains the access network IP address and the border router IP address. It is managed by the system administrator.

• Local Eims_neighbors table - stores information about the EIMS neighbours for the local domain. It contains information about the border routers used to connect the local domains and the neighbors, border router IP address, web service port addresses, etc. It is managed by the system administrator.

• Domain_qos_parameters table – it is used to store global QoS parameters about the domain. It is managed also by the system administrator.

5.4. Functionality tests

This solution was implemented on the test-bed built at our university in the Enthrone project framework [21] [22]. The test-bed consists of three Autonomous Systems, each managed by a Network Service Manager (EIMS@NP). The EIMS@NP managers are implemented using web services technology. Between domains the BGP protocol is used to route the best effort traffic. A Network Manager is used to install the pSLS pipes on network devices. Also the test-bed has a Service Provider EIMS Manager, and the other modules required by the Enthrone system. The connectivity tests involved only the Network Provider managers and Service Provider manager.

The EIMS@SP was used to trigger pSLS subscribe requests, between a Content Provider and one of the available Access Networks, until the resources on the lowest cost path between the chosen source and destination, were exhausted. Then it has been triggered additional requests between the same source and destination. These new requests were admitted but the pSLS pipes were built along the next cheapest path between the chosen end points.

Because the testbed is a small one, is difficult to evaluate the performances of the proposed solution for a large number of domains. We have measured how fast, a request for getting the neighbours EIMS from a network domain, is served. We have obtained a mean time less than 0.1s per request. If we take for example a topology consisting of 1000 domains then, because we can consider that the total processing time is increasing linearly with the number of domains, the total processing time required to obtain the overlay topology is about 100s. We can increase it with 50% to take into account that at a large number of domains the local processing time, between two interrogations could be higher. So we could consider that for 1000 domains the topology building process takes about 150s, which is an acceptable value. Also, the solution used to build the overlay topology implies a large number of messages to be exchanged in order to build the topology. Each node should communicate with the other nodes. But the messages exchanged are small, because each of them contains only a few data about the neighbors of the interrogated node. If it have been adopted a link state like protocol to build the topology, then the messages would have been very big in case of large number of domains, so the amount of signaling data in the network would have been bigger. Also in our case we don’t have convergence problems.

It has not been evaluated till now the time needed to compute several paths towards all the destinations nodes in the overlay topology.

The testbed used is not appropriate to test the scalability for the path finding process performed in the first phase. It could only be used to see that routing table is built correctly, containing several paths towards each destination domain in the topology. Then, several requests for QoS enabled pSLS pipes have been triggered. These pipes were built along the first path specified in the routing table. When the resources on this path were exhausted, during the negotiation process, the next route was used for the following pSLS pipe. These tests proved that the solution is able to find QoS enabled pipes, in a multi domain environment.

6. Conclusion

This chapter has proposed a simple solution for solving the problem of QoS enabled inter-domain path finding, applicable when Network Service Management systems exist in each domain capable of constructing mid-long term pSLS pipes with imposed QoS parameters.

Because the solution does not require at a domain the knowledge of other domain resources, it could be attractive and accepted by the real life network providers. Another advantage is that it does not burden a given domain manager with the need of knowing the available traffic trunks of other network domains. Also, by separating the process of path finding from the QoS negotiation, the path searching process doesn’t need to work real time. So we can find several paths in very complex overlay topologies. Also, by simplifying the overlay topology, considering only the domain managers as topology nodes, the solution might work for very complex topologies, being no need for an hierarchical approach.

The solution has as a main disadvantage that it does work only in the presence of a QoS negotiation system capable. It is based on this feature to check the QoS constraints on the paths founded in the overlay topology. Another disadvantage is that, it may not find the best QoS enabled path, as could be the case with other solutions.

The solution has proved to be simple to implement and is well suited for ENTHRONE Integrated Management System. It is also naturally extensible for more sophisticated techniques in QoS capable paths finding.

Further studies and simulations will be done in order to validate this solution for a real network environment. Also, it has been supposed that, because the path finding process could be run offline and the topology is a simplified one, a non hierarchical solution could be adopted for Internet. Simulations should be done to establish the amount of resources need by such a process.