Available online at www.sciencedirect.com
SCIENCE tft) DIRECT
Computer Communications 29 (2006) 879-892

www.elsevier.com/locate/comcom
Hybrid routing in next generation IP networks*
Antoine B. Bagula
Department of Computer Science, University of Stellenbosch, 7600 Stellenbosch, South Africa Available online 12 September 2005
Abstract
This paper presents a hybrid approach for routing flows in IP networks to achieve an optimal network configuration maximising bandwidth usage (optimality), minimising re-routing upon failure (reliability) and reducing the signalling overheads resulting from a full IP tunnelling (scalability). We formulate the routing of flows in IP networks as a service differentiated model where the IP flows are classified into high bandwidth demanding (HBD) and low bandwidth demanding (LBD) flows at the ingress of the network and handled differently into the core using a hybrid IGPCMPLS approach where the LBD flows are routed over the existing IGP paths while the HBD flows are carried over MPLS bandwidth-guaranteed tunnels. This model can be deployed in heterogenous network environments where HBD flows carrying real-time traffic and LBD flows transporting best-effort traffic are handled differently over a common transport network implementing traffic prioritization in response to natural or man-made emergencies. We consider the routing of flows within an IP domain's boundaries and evaluate the efficiency of the new routing approach under uniform and bursty traffic profiles. We apply the routing approach to compute paths for the traffic offered to a 20- and 50-node test networks. Simulation reveals that the hybrid routing approach outperforms both IGP and MPLS routing under the network conditions and test network models considered.
© 2005 Elsevier B.V. All rights reserved. Keywords: Online TE; Hybrid routing; OSPF; LIOA; CSPF
1. Introduction
The Internet has developed beyond a research network initially designed to offer best effort service to a small number of research institutions into a large decentralised network where traffic management methods such as Network Engineering (NE) and Traffic Engineering (TE), once the preserve of telephone networks, are being reinvented and used to support QoS through differing resource requirements delivery. NE moves bandwidth to where the traffic is offered to the network while TE moves the offered traffic to where bandwidth is available in the network to achieve QoS agreements between the available network resources and the application requirements. TE can discharge the network administrator from
This work is supported by grant numbers 2047362 and 2677 from the South African National Research Foundation, Siemens Telecommunications and Telkom SA Limited.
E-mail address: bagula@cs.sun.ac.za.
URL: http://www.cs.sun.ac.za/bagula.
the tedious manual configuration procedures by using QoS routing to select a path that is able to meet the application QoS requirements.
Several issues need to be resolved before IP QoS routing becomes wide-spread in the ISP networks. These include (1) the mapping of application QoS requirements into QoS mechanisms and (2) the deployment of these mechanisms within an Internet domain's boundaries to maximise the engineering and economic efficiency.
1.1. Mapping application QoS requirements into QoS mechanisms
Most current generation IP protocols were designed to deliver best-effort service to the IP applications when IP transport was concerned with only data transmission. The Internet has since developed into a common transport infrastructure requiring QoS routing to meet the QoS demanded by the mixture of real-time and best-effort applications carried by a multitude of access networks. These include applications with (1) hard real-time constraints such as remote sensing, voice over IP, home automation, (2) soft real-time constraints such as streaming video, and (3) best-effort constraints such as FTP, Secure Shell, etc. The wide-spread deployment of QoS routing by network operators will require mechanisms to (1) map the different applications into traffic flow classes, (2) identify the QoS to be provided to these flows, and (3) ensure QoS delivery for these flows. The last two steps have been extensively researched by the IP community but only few steps have been made in the quantitative evaluation of integrated systems combining the three steps and much less in the mapping of the application into traffic classes. This is according to some service provider opinion the reason for the slow deployment of QoS routing in the emerging multiservice Internet.
1.2. Deploying QoS within an Internet domain boundaries
Most currently deployed routing mechanisms for IP networks are based on routing metrics (cost metrics) which optimise system-wide measures of performance such as average response time, throughput, delay, etc. discounting the diversity of QoS requirements from the mixture of narrow- and broad-band applications carried by the new multi-service Internet. Managing cost to support QoS routing is a challenging problem, which has been tackled by the IP community using different optimisation approaches. These include (1) the use of cost metrics which reflect the current resource availability such as implemented by constraint-based routing (CBR) [1], (2) the deployment of traffic-aware routing algorithms [2,3] proposed in the context of Multiprotocol Label Switching (MPLS) [4], and (3) the deployment of multiple metrics used either separately or combined into a mixed cost metric such as proposed in [5]. Though overcoming the limitations of the OSPF [6] protocol, CBR is poorly equipped for traffic engineering support under heavy load conditions. The recently proposed traffic-aware algorithms are concerned with bandwidth maximisation only and incur additional complexity, which does not necessarily translate into equivalent performance gains. Multiple metric routing has been suggested to be used at best as an indicator in path selection since it may result in unknown composition rule for the path cost.
1.3. Contributions and outline
This paper revisits the problem of routing flows within an IP domain boundaries with the expectation of finding an optimal network configuration minimising re-routing upon failure (reliability), maximising bandwidth usage (optim-ality) and avoiding excessive signalling resulting from a full IP tunnelling (scalability) where each packet is switched over a Label Switched Path (LSP) [4]. We consider a new QoS routing approach where (1) best-effort and real-time applications are mapped into low bandwidth demanding (LBD) and high bandwidth demanding (HBD) traffic classes, respectively, (2) LBD flows are routed over the shortest paths while HBD flows are packed into bandwidth-guaranteed tunnels to achieve traffic growth, and (3) these flows are provided different services based on a cost-based route optimisation model. The main contributions of this paper are:
- Hybrid IGPCMPLS routing. We formulate the routing of flows in IP networks as a service differentiated model where the IP flows are classified into low bandwidth demanding (LBD) and high bandwidth demanding (HBD) flows at the ingress of the network and handled differently into the core to achieve the logical separation of a physical network into two virtual networks: (1) an IGP network where the LBD flows are routed along the shortest paths computed using the IGP model and (2) an MPLS network engineered to carry the HBD flows over bandwidth-guaranteed tunnels computed using the MPLS model. This model can be deployed in heterogeneous network environments where the traffic offered by realtime and best-effort applications is handled differently over a common core transport implementing traffic prioritisation in response to natural or man-made emergencies.
- Cost-based route optimisation. Different controls have been proposed by network operators to maximise bandwidth usage in IP networks [7]. These include (1) inflating the bandwidth requirements to control the utilisation of each link and (2) maximising the residual bandwidth to achieve load-balancing. Building upon these controls and the stochastic principle that different links can have different flow carrying probabilities, we consider a new route optimisation paradigm where (1) LBD and HBD flows are assigned different flow carrying probabilities and routed differently and (2) the HBD flows are packed into bandwidth tunnels to achieve traffic growth and provision for bursty traffic conditions. This can be useful in routing conditions where wired and wireless links are assigned different flow carrying probabilities and routed differently to optimise the use of a hybrid wiredCwireless network.
- Routing robustness. Modern IP networks require that both real-time traffic such as Voice over IP (VoIP) and best-effort traffic such as File Transport Protocol (FTP) applications be routed within an Internet domain's boundaries to maximise the engineering efficiency (network optimality and reliability) and the economic gain (revenue maximisation). Building upon these objectives, we applied the new hybrid routing approach to compute paths for the traffic offered to a 20- and 50-node test networks, each considered as a single Internet domain. We
simulated the hybrid routing scheme under uniform and bursty traffic conditions to evaluate the robustness of our model. Simulation revealed that the new hybrid routing approach outperforms IGP and MPLS routing in terms of the engineering and economic efficiency.
The reminder of this paper is organised as follows. Section 2 presents the hybrid routing approach. An application of the hybrid routing approach to compute paths for the flows offered to a 20- and 50-node test networks is presented in Section 3. Our conclusions are presented in Section 4.
2. The hybrid routing approach
Consider a network represented by a directed graph (N, L) where N is a set of nodes and L is a set of links. Assume that the network carries IP flows that belong to a set of service classes S= {Slbd, Shbd} where Slbd and Shbd define the set of low bandwidth demanding (LBD) and high bandwidth demanding (HBD) flows, respectively. Let Cl denote the capacity of link l and let Pie = Pigp(i, e)UPmpls(i, e) denote the set of paths connecting the ingress-egress pair (i, e) where Pigp(i, e) denote the set of paths found using the IGP routing approach while Pmpls(i, e) denote the set of paths computed using the MPLS routing approach. Assume a flow-differentiated services where a request to route a class service s2S flow of die bandwidth units between an ingress-egress pair (i, e) expressed by the tuple t=(i, e, die, s) is received and that future demands concerning IP flow routing requests are not known.
Let Lp = ^2l2pLl{tii, rl) denote the cost of path p where Ll(nl, rl) is the cost of link l when carrying nl flows and rl is the total bandwidth reserved by the IP flows traversing
link l.
The flow routing problem consists of finding the best feasible path ps 2 Pie where
Lp = min Lp (1)
die < min(Cl -rl)  for s 2SM (2)
l2ps
Yd  < min(Cl -rl)  for s 2Shbd (3)
l2ps
where g is a calibration parameter expressing the packing (inflation) rate for HBD flow requirements. Eq. (1) expresses the optimality of the routing process while Eqs. (2) and (3) express the feasibility of the flows.
We consider a hybrid routing model which is built upon
(1) the common knowledge that in a multi-service network HBD flows have higher blocking since it is harder to find enough resources when flows require large bandwidth and
(2) previous findings [8] revealing that the LBD flows
requiring less bandwidth may be routed over the shortest paths while the HBD flows are carried over IP tunnels to provide better grade-of-service to both flows. The key features of our hybrid routing approach are:
- Ingress flow classification into different traffic classes (LBD and HBD) based on bandwidth requirements and a cut-off parameter defining the limits between these classes.
- A route optimisation model aiming at maximising bandwidth usage (optimality), minimising rerouting upon failure (reliability) and avoiding a full IP tunnelling (scalability).
- Path selection using a mixed metric differentiating flows based on their link flow carrying probabilities and yielding shortest path routing for LBD flows while packing HBD flows into bandwidth tunnels.
2.1. Ingress flow classification
We consider a flow classification model where the IP flows are classified into two traffic classes referred to as low bandwidth demanding (LBD) and high bandwidth demanding (HBD) flows depending on their bandwidth requirements (die) and a cut-off parameter t defining the limit between LBD and HBD flows. The two traffic classes are defined by
Slbd(t) = {flows demanding die bandwidth units|eie(T) = 0}
(4)
Shbd(t) = {flows demandingdie bandwidthunits|eie(t) = 1}
(5)
where m<t<M and t > 0 is cut-off parameter defining the limit between LBD and HBD flows, m and M are, respectively, the lower and upper bounds for the bandwidth demand die and eie (t) is defined by
£i,e(t) =
di,e < T
di,e> t
(6)
Our flow classification model is loosely related to [9] where traffic flows are differentiated in a traffic driven LSP establishment model using a trigger-based mechanism depending on the total bandwidth in an ISP network. We note that the cut-off t used in this paper is an important parameter which can be set to a value defining the difference between LBD and HBD flows as perceived by the network operator based on his experience. It can also be assigned a value expressing the trade-off between different performance objectives (optimality, reliability and scalability) as shown in [8].
2.2. Cost-based route optimisation
The routing approach adopted in this paper is based on a route optimisation model where the IP flows are routed based on a mixed routing metric minimising re-routing upon failure (reliability), maximising bandwidth usage under different traffic conditions (optimality) and avoiding a full IP tunnelling leading to per-flow state in both the control and forwarding plane and resulting in excessive signalling through LSP setting up and tearing down (scalability).
2.2.1. Reliability
The main reliability objective of our routing approach is to minimise the damage to the network transport layer under failure expressed by the number of re-routed flows under failure. Let F be a set of possible failure patterns, wf the probability of the failure patternf2F and nf the number of re-routed flows under failure f. The expected number of rerouted flows under the set of failure patterns F is defined by
W =   Wf = Z) wfnf
f2F f2F
(7)
where Wf expresses the damage to the network transport layer under failure event f.
Assuming that a fibber cut is the most likely failure event in optical networks, we consider the set offailure events F= L and define a measure of reliability expressing the link loss
by
Wl = Z ws,lns,l = Z ^Z Ss,l,r
(8)
s2S
s2S
r2R
where wsri is the probability for class s flows to traverse link l2L referred to as the class s flow carrying probability, R = UieRie is the set of flows carried by the network, Rie is the subset of flows from node i to node e, nsl = ^2 &s,i,r is the number of class s flows carried by link l, nl =^2s^2 T2R &s,i,r is the total number of flows carried by link l referred to as its interference and
ds,l,r
1 class s flow r traverses link l 0 otherwise
(9)
2.2.2. Optimality
The network optimality may be achieved by (1) limiting resource consumption using shortest path routing and (2) improving the QoS level through load balancing. Shortest path routing leads to network un-balancing, an unwanted behaviour which can lead to performance degradation though the network provides resources to carry the offered traffic. Constraint-based routing (CBR) [1] algorithms such as Constraint Shortest Path First (CSPF) have been proposed to overcome the limitations related to traditional shortest path routing such as OSPF [6]. The CSPF routing approach is based on a load-balancing approach where the inverse of the link residual bandwidth 1/(Cl—fl) is minimised to lead the link far from a congestion region where the link load approaches its capacity. However, though performing better under low and moderate load conditions CSPF is outperformed by traditional shortest path routing at high load. Building upon this finding, we propose a new optimality parameter referred to as the link congestion distance which (1) considers both static and dynamic routing situations, (2) implements the packing of flows to achieve traffic growth and support for bursty traffic conditions, and (3) defines the distance from a congestion region where the link load approaches its capacity. We consider the packing of flows by inflating the bandwidth requirements to control the utilisation of all links as commonly recommended by network operators. The link congestion distance is defined
by
Dl(rl) = Cl — eUe(t)(rl C gdUe)
(10)
where sie(T) 2{0,1} is introduced to consider static and dynamic routing situations and g > 0 is a packing parameter expressing the packing (inflation) rate for the bandwidth requirements.
2.2.3. Scalability
The limitations related to the deployment of a full MPLS or IGP implementation are well documented. These include scalability problems in MPLS routing and optimality issues in IGP routing. The use of a hybrid IGPCMPLS routing approach has been recently standardised by the IETF as a best current practice [10] consisting of using the existent IGP path as alternative for a TE path when setting-up tunnels in an MPLS forwarding plane. We consider a similar routing approach taking into account an IGP path computed using an IGP metric and a MPLS path computed by a TE metric but using a different flow handling and forwarding model. In our model, the LBD flows are carried along IGP paths to reduce the per-flow state implementation and signalling overheads that could result from a full IP tunnelling while the HBD flows are routed over bandwidth-guaranteed tunnels computed using the MPLS model to improve the network efficiency.
2.3. Path selection algorithm
The joint reliability, optimality and scalability demanded by modern IP applications may be achieved by (1) combining the link interference minimisation and the congestion distance maximisation objectives into a mixed routing metric and (2) implementing differentiated flow handling using this mixed routing metric to achieve scalability through IGP routing and optimality through MPLS tunnelling. This joint objective is achieved by multiplying power values of the link loss and congestion distance to form a multiplicative metric expressed by
(11)
where 0 < a < 1 is a calibration parameter expressing the trade-off between reliability and optimality. We note that the cost metric presented above yields different routing modes depending on the values of the parameters 3i e(T), a and g. These include (1) OSPF routing for £iJj) = 0, (2) CSPF routing for (eie(t),a,g) = (1,0,0), (3) LIOA routing for (eie(t),g) = (1,0), and (4) Least Interference Routing (LIR) for (3i e(T) a)= (1 1). It was shown that a= 0.5 achieves the best trade-off between reliability and optimality in loosely related work [11].
Consider a request to route a flow of die bandwidth units between two nodes i and e. The algorithm proposed (hereafter referred to as Hybridmix) executes the following steps to route this flow:
(1) Ingress flow classification. set s= sie(T)
(2) Path selection.
(a) IGP routing.Ifs= 0 select the existing shortest path p2 Pigp(i, e) between i and e, set ps= p and goto step 3.
(b) Prune the network. Set Ll(nl, rl) = °° for each link l whose slack Cl— rl<die.
(c) Traffic aggregation. Select an existing tunnel p2 Pmpls(i, e) with enough bandwidth to carry the offered request, set ps= p and goto step 3.
(d) Find a new least cost path. Apply Dijkstra's algorithm using the link cost (11) to find a new
least cost path ps2 Pi,e and set Pmpls= PmplsC ps.
(3) Route the request.
• Assign the traffic demand die to pathps.

• Update the link occupancy and interference if s = 1. For each link l2ps set rl: = rlCdie and l: = ns,lC 1.
Note that the path selection has the same complexity as Dijkstra's algorithm: O(N2) or lower depending on the implementation of the Dijkstra's algorithm. We also observe that step (a) can be moved after step, (b) to consider a Constraint Based Routing approach where both LBD and HBD flows are subject to admission control (network pruning). This approach may be relevant in routing conditions where the IGP metric is used to complement a TE metric as recently proposed
by [10].
3. An implementation
This section presents simulation experiments conducted using a 20- and 50-node test networks illustrated by Fig. 1 to compare the performance achieved by our routing algorithm referred to as Hybridmix to (1) IGP routing using the Open
Shortest Path First (OSPF), (2) MPLS routing using CSPF
and the Least Interference Optimisation Algorithm (LIOA)
[11].
The 50-node network has 1225 ingress-egress pairs and 202 uni-directional links with 38,519,241 units of bandwidth. The 20-node network has 190 ingress-egress pairs and 244 uni-directional links with 6,515,881 units of bandwidth. An equal number of 50,000 flow requests are offered to the I-E pairs. The link capacities were chosen to model the capacity ratio of OC-12 and OC-48 circuits.
More realistic network topologies representing real or fictitious ISP networks can be used. However, most of these realistic networks do not often provide the required mesh factor allowing the investigation of some of the routing

Fig. 1. The 20- and 50- node test networks.

Fig. 2. The traffic profiles. (a) Uniform traffic profile. (b) Bursty traffic profile.
concepts presented in this paper. These practical networks have not been studied in this paper for space limitations.
We consider two types of traffic: uniform where the demands di,e are uniformly distributed in the interval [m, M] as illustrated by Fig. 2(a) and bursty where the demands di,e present periods of bursts over the simulation period as illustrated by Fig. 2(b).
The parameter values for the simulation experiments are presented in terms of the offered flow routing requests, the value of the calibration parameter a, the flow request rates A, the flow holding time the cut-off parameter t, the demand range [ m, M], the number of simulation trials T and the number of flow requests per trial N. The flow arrival and services processes are Poisson. Each flow bandwidth demand di,e is uniformly distributed in the range [m, M]. We considered short-lived flows only since initial experiments revealed the same performance patterns for shortlived (1//x= 1) and long-lived flows (1//x = 00).
3.1. Performance parameters
The relevant performance parameters used in the simulation experiments are (1) the quality of the paths expressed by the path length, the path multiplicity and the preferred path usage, (2) the engineering efficiency expressed by the network optimality and reliability: the percentage flow acceptance ACC, the average link utilisation UTIL, the average interference AV and the maximum link interference MAX, (3) the network scalability expressed by the network gain, and (4) the economic efficiency expressed by the HBD flow acceptance/rejection. The path length determines the average path length in number of hops. It gives an indication on resource consumption: a longer path ties up more resources than a shorter path. The path multiplicity expresses the average number of paths used by a source-destination pair. It gives an indication of the load balancing capability of an algorithm: a higher value of this parameter is an indication of a more balanced network. The preferred path usage expresses how often a path finding algorithm routes flows on the preferred path connecting an I-E pair (the path most used by an I-E pair is defined as the preferred path). ACC is the percentage of flows which have been successfully routed by the network. UTIL is the average link utilisation. It gives an indication of the potential for a network to achieve traffic growth: a least utilised network has a higher potential to achieve traffic growth than a highest utilised network. AV is the average number of flows carried by the network while MAX is the number of flows carried by the most interfering link. The link interference (average and/or maximum) gives an indication of the number of flows which must be re-routed upon a single link failure: an algorithm which achieves lower interference is more reliable since it leads to rerouting fewer flows upon failure. The network gain determines the reduction in number of signalling operations resulting from a full IP tunnelling using MPLS. The economic efficiency is expressed by the economic gain resulting from rejecting less HBD flows: an algorithm rejecting/accepting fewer/more HBD flows will achieve higher economic efficiency in situations where the HBD flows carrying real-time traffic are the highest income generator flows.
3.2. Simulation experiments
Several simulation experiments were conducted under varying traffic conditions (different demand ranges [m, M]) and traffic profiles (uniform and bursty)) to evaluate (1) the impact of the link flow routing stochasticity on the network efficiency, (2) the efficiency of different packing models, (3) the impact of the packing granularity on the network efficiency, (4) the efficiency of the different algorithms, (5) the quality of the paths carrying the LBD flows, the dominant flows in the network, and (6) the impact of the hybrid routing approach on the network scalability.
The results of the experiments are depicted by different figures and tables. Each entry of Table 1 presents the average of each of the performance parameter described
above: ACC, UTIL, AV and MAX. Table 2 presents the
averages of the number of LBD and HBD paths found by the hybrid routing algorithm and the network gain. These averages are computed at 95% confidence interval within 0.1% of the point estimates. Our choice of the best performance values is based on a trade-off between the
Table 1
Exp 5: Comparing different algorithms
Uniform	20-node network				50-node network				
	ACC	UTIL	AV	MAX	ACC	UTIL	AV	MAX	
OSPF	86	47	358	13509	75	52	261	1007	
CSPF	94	47	340	11560	83	52	255	893	
LIOA	96	49	332	9969	84	55	250	729	
Hybridmix	96	49	332	1103	85	52	250	731	
Bursty	ACC	UTIL	AV	MAX	ACC	UTIL	AV	MAX	
OSPF	74	56	335	12070	63	60	237	878	
CSPF	82	56	325	10735	68	60	235	787	
LIOA	83	59	320	9594	70	63	231	666	
Hybridmix	85	58	319	1057	77	60	232	660	
Table 2
Network scalability
Uniform profile	Plbd	Phbd	Plsp	G1	G2	
20-node	20133	12254	5089	62%	84%	
50-node	20819	13536	8319	61%	75%	
Bursty profile	Plbd	Phbd	Plsp	G1	G2	
20-node	15746	13019	1129	55%	96%	
50-node	16961	14291	3991	54%	87%	
different values achieved by the different performance parameters. The calibration parameters a and T have been set to a= 0.5 to balance the impact of optimality and reliability and T= 0.60 to achieve the best trade-offbetween optimality, reliability and simplicity in agreement with [8]
and [11].
3.2.1. Experiment 1. The impact of the flow routing stochasticity
We conducted a first set of experiments to evaluate the impact of the flow routing stochasticity ws>l on the engineering and economic efficiency under varying traffic conditions (different demand ranges [m, M]) and profiles (uniform and bursty). The experimental results presented in Figs. 3 and 4 for uniform traffic profiles and Figs. 5 and 6 for bursty conditions reveal that the flow routing probability wlbd,l= 0(whbd,l= 1) leads to better performance under both traffic profiles: (1) higher flow acceptance, (2) reduced

Maximum interference under light and moderate load profiles (M<700), and (3) higher economic efficiency expressed by a slightly lower number of rejected HBD flows. Note that the reliability performance degradation (higher maximum interference) under higher load conditions (M>700) is outweighed by the relative optimality (higher flow acceptance) and economic gain (lower HBD rejection) under these conditions. and 6.
3.2.2. Experiment 2. Different packing models
We conducted a second set of experiments to evaluate different packing models under various traffic conditions and profiles. We considered three flow packing models: (1) packing only LBD flows (g >0 for sie(r) = 0), (2) packing only HBD flows (g>0 for sie(r) = 1), and (3) packing both flows (g>0 for sie(r) = 0 and sie(r)= 1). The results illustrated by Figs. 7 and 8 for uniform traffic profiles and Figs. 9 and 10 for bursty conditions reveal that packing
Fig. 3. Exp. 1: Engineering efficiency under uniform profile. (a) Flow acceptance. (b) Max interference.

Fig. 4. Exp. 1: Economic efficiency under uniform profile. (a) HBD-LBD rejection. (b) HBD rejection.

Fig. 5. Exp. 1: Engineering efficiency under bursty profile. (a) Flow acceptance. (b) Max interference.
HBD only and packing both classes of flows leads to the same (coincided curves) and better performance in terms of flow acceptance. HBD packing and LBD packing produce the same LBD flow rejection under uniform traffic profile but HBD packing decreases considerably the LBD flow rejection as illustrated by Fig. 8. HBD packing leads to higher HBD-LBD flow rejection difference (space between the HBD and LBD curves) under both traffic profiles but with a higher difference under bursty profile resulting from a 10% increase in the HBD flow rejection and a 10% decrease in the LBD flow rejection compared to LBD packing as depicted by Fig. 10(b).
3.2.3. Experiment 3. The packing granularity
We conducted a third set of experiments to evaluate the impact (granularity) of the HBD flow packing on the network efficiency. Figs. 11 and 12 depicting the results obtained for uniform profile and Figs. 13 and 14 illustrating the results for bursty profile show the relative improvements resulting from the implementation of the packing model. These figures reveal that Packing (g>0) leads to engineering efficiency improvements compared to the standard Hybrid routing model (g = 0) under both traffic profiles: (1) higher flow acceptance and (2) reduced Maximum interference under light and moderate traffic

Fig. 6. Exp. 1: Economic efficiency under bursty profile. (a) HBD-LBD rejection. (b) HBD rejection.

Fig. 7. Exp. 2: Engineering efficiency under uniform profile. (a) Flow acceptance. (b) Max interference.

Fig. 8. Exp. 2: Economic efficiency under uniform profile. (a) LBD packing. (b) HBD packing.
load conditions (M<700). These figures also reveal higher economic efficiency expressed by lower HBD flow rejection for the standard Hybrid model (g = 0). We also observe (1) reliability degradation (higher maximum interference) with the inflation rate (for the inflation rates x and y, Max(x) >Max(y)if x<y) and (2) optimality improvement with the inflation rate (for the inflation rates x and y, ACC(x) > ACC(y) for x> y). These results suggest the selection of an appropriate value for the inflation rate to achieve the best trade-off between reliability and optimality. For the test network and traffic conditions considered we found that g = 6 achieves this trade-off. We also noticed that the inflation rate has a much smaller impact on the reliability performance degradation (higher maximum interference) under higher load conditions (MO700) compared to the impact of the link flow stochasticity. This degradation is outweighed by the optimality (higher flow acceptance) achieved under these conditions.

Fig. 9. Exp. 2: Engineering efficiency under bursty profile. (a) Flow acceptance. (b) Max interference.

Fig. 10. Exp. 2: Economic efficiency under bursty profile. (a) LBD packing. (b) HBD packing.

Fig. 11. Exp. 3: Engineering efficiency under uniform profile.
3.2.4. Experiment 4. A mixed routing model
Building upon the precedent experimental results, we conducted a fourth set of experiments to evaluate the efficiency of a mixed routing approach (MIX) combining the flow routing stochasticity using differentiated flows handling (DFH) and HBD flow packing using the inflated bandwidth requirement (IBR) model with wlbd l = 0(whbdl=1) and g = 6 under various traffic conditions and profiles. Figs. 15 and 16 present the results for uniform traffic profiles and Figs. 17 and 18 depict the results under bursty conditions. These figures reveal
the relative improvements resulting from the implementation of the MIX model: (1) MIX (g = 6 and wlbdl = 0) leads to engineering efficiency improvements compared to both the IBR (g = 30) and DFH (whb<u= 1) and the standard Hybrid routing model using (g = 0 and wlbd)l = whbdl = 0.5). We note that the mixed model (MIX) overcomes (1) the reliability performance degradation (higher maximum interference) observed under higher load conditions (MO 700) for the other two models (IBR and DFH) and (2) the economic gain degradation under heavy load conditions previously observed by achieving
(b) HBD rejection

Fig. 12. Exp. 3: Economic efficiency under uniform profile.

Fig. 13. Exp. 3: Engineering efficiency under bursty profile.

Fig. 14. Exp. 3: Economic efficiency under bursty profile.
the same HBD-LBD flow rejection difference under both traffic profiles.
3.2.5. Experiment 5. Comparing different algorithms
We conducted a set of experiments to compare the performance of the four routing algorithms using the demand ranges [m, M] = [1, 150] for the 20-node network and [m, M] = [1, 400] for the 50-node network and the cutoff values t= 100 for the 20-node network and t = 250 for the 50-node network. These experiments were conducted under uniform and bursty traffic profiles. The results presented in Table 1 reveal that the hybrid routing algorithm based on Hybridmix performs better than the four other algorithms. It achieves (1) the same and best optimality as MPLS routing using LIOA where optimality is expressed by the flow percentage acceptance and (2) the best reliability where reliability is expressed by the average and maximum interference. These results observed for the 20- and 50-node

Fig. 15. Exp. 4: Engineering efficiency under uniform profile.

Fig. 16. Exp. 4: Economic efficiency under uniform profile.

Fig. 17. Exp. 4: Engineering efficiency under bursty profile.
test networks reveal the same performance pattern for the different algorithms under uniform and bursty traffic profiles but with performance degradation under bursty conditions.
3.2.6. Experiment 6. The quality of paths for LBD flows
The quality of the paths carrying LBD flows illustrated by Fig. 19 shows that approximately 70% of the routes used by the three routing algorithms (OSPF, LIOA, and
Hybridmix) are at most 3 hops long (Fig. 19(a)). The three algorithms thus perform equally well in terms of resource consumption. Hybridmix achieves the best route multiplicity and route usage. OSPF performs worse in terms of path multiplicity (Fig. 19(b)) and path usage (Fig. 19(c)). These results show that Hybridmix achieves the best stability in terms of path selection and balances the flows over the network better than the LIOA and OSPF models.

Fig. 18. Exp. 4: Economic efficiency under bursty profile.

Fig. 19. Exp. 6: The quality of the LBD paths.
3.2.7. Experiment 7. The network scalability
The number of IP tunnels that should be set-up in the hybrid network in the absence of LSP aggregation is the same as the number of HBD flows offered to the network. This number can be considerably reduced by LSP aggregation. We evaluated the scalability of the hybrid routing approach in the absence of LSP aggregation and under LSP aggregation to evaluate the relative gains achieved by the two networks. The corresponding network gains are referred to as G1 (in absence of LSP aggregation) and G2 under LSP aggregation. These gains are defined by
G1 = 100  1
IP,
hbdl
|Pi,<
G2 = 1001 1—^ 1
IP,.
(12)
(13)
where Pie = Plbd U Phbd, Plbd is the set of paths carrying the LBD flows, Phbd is the set of paths carrying the HBD flows in the absence of LSP aggregation and Plsp is the set of paths carrying the HBD flows under LSP aggregation.
Table 2 shows the number of paths found by each of the path sets Plbd, Phbd and Plsp and the network gains G1 and G2 achieved. The results presented in Table 2 using the demand ranges [m, M] = [1, 150] for the 20-node network and [m, M] = [1, 600] for the 50-node network show that an IP network implementing IGP C MPLS routing can achieve up to G1 = 62% network gains under uniform profile and G1 = 55% network gain under bursty profile in the absence of LSP aggregation. These results under LSP aggregation reveal up to G2 = 84% network gains under uniform profile and G2 = 96% network gains under bursty traffic conditions. These results are in agreement with (1) [8] where similar scalability was achieved by a hybrid IGP C MPLS network in the absence of LSP aggregation and (2) [12] a loosely related work that showed that a relatively small number of MPLS paths is sufficient to greatly improve a network's quality of service.
4. Conclusion
This paper presents a hybrid approach for routing flows in IP networks to achieve an optimal network configuration maximising bandwidth usage (optimality), minimising rerouting upon failure (reliability) and reducing the signalling overheads resulting from a full IP tunnelling (scalability). We consider a TE model implementing ingress flow classification and differentiated core handling to achieve the logical separation of a physical network into two virtual networks: (1) an IGP network carrying low bandwidth demanding flows and (2) an MPLS network where high bandwidth demanding flows are routed over bandwidth-guaranteed tunnels. Using per flow simulation, we show that an IGP C MPLS routing approach outperforms both IGP and MPLS routingonseveral performance indexes and demonstrate that using a hybrid IGPC MPLS routing approach thousands of flows may be established in a network without per flow state implementation in both the control and forwarding planes in a network.
Recently, the IETF literature has been deluged with proposals to achieve inter-domain TE; some proposing simple extensions to BGP4 while other supporting new inter-domain routing proposals. The evaluation of these extensions and proposals in a hybrid IGPC MPLS setting have been reserved for future work.
References
[1] E. Crawley, R. Nair, B. Jajagopalan, H. Sandick, A Framework for QoS-based Routing in the Internet, Request for comments, http:// www.ietf.org/rfc/rfc2386.txt, August 1998.
[2] K. Kar, M. Kodialam, T.V. Lakshman. Minimum interference routing with application to MPLS traffic engineering, Proceedings of the IEEE
INFOCOM, Tel-Aviv, Israel, March 2000.
[3] S. Suri, M. Waldvogel, P. Warkhede, Profile-based Routing: a new
framework for MPLS Traffic Engineering, Proceedings of the QofIS,
Lecture Notes in Computer Science, vol. 2156, September 2001. [4] E.C. Rosen, A. Viswanathan, R. Callon. Multiprotocol Label
Switching Architecture, Request for comments, http://www.ietf.org/
rfc/rfc3031.txt, 2001. [5] Z. Wang, W. Crowcroft, Quality-of-service routing for supporting
multimedia applications, IEEE Transactions on Communications 4
(1996) 1228-1234. [6] J. Moy, OSPF Version 2, Request for comments, http://www.ietf.org/
rfc/rfc1583.txt, March 1994. [7] X. Xiao, A. Hannan, B. Bailey, Traffic engineering with MPLS in the
internet, IEEE Network March/April (2000).
[8] Antoine B. Bagula, Online traffic engineering: a hybrid IGPCMPLS routing approach, Proceeding of the QofIS, Lecture Notes in Computer Science, vol. 3266, September 2004.
[9] S. Uh ig, O. Bonaventure. On the cost of using MPLS for interdomain traffic. Proceeding of the QofIS, Berlin, September
2000.
[10] F. Faucheur et al., Use of interior gateway protocol (IGP) metric as a second traffic engineering(TE) metric, Request for comments, http://
www.ietf.org/rfc/rfc3785.txt, May 2004.
[11] A. Bagula, M. Botha, A.E. Krzesinski, Online traffic engineering: the least interference optimization, Proceedings of the ICC Conference,
Paris, June. 2004.
[12] A. Riedl, Optimized routing adaptation in IP networks utilizing
OSPF and MPLS, Proceedings of the ICC Conference, May 2003.