Uwe Steglich
email: uwe.steglich@etit.tu-chemnitz.de

Thomas Bauschert
email: thomas.bauschert@etit.tu-chemnitz.de

Christina Büsing
email: buesing@or.rwth-aachen.de

Manuel Kutschka
email: kutschka@math2.rwth-aachen.de

A Generic Multi-layer Network Optimization Model with Demand Uncertainty

Keywords: network, design, multi-layer, uncertainty, robustness

In this work we introduce a mixed integer linear program (MILP) for multi-layer networks with demand uncertainty. The goal is to minimize the overall network equipment costs containing basic node costs and interface costs while guarding against variations of the traffic demand. Multi-layer network design requires technological feasible inter-layer connections. We present and evaluate two layering configurations, top-bottom and variable. The first layering configuration utilizes all layers allowing shortcuts and the second enables layer-skipping. Technological capabilities like router-offloading and layers able to multiplex traffic demand are also included in the model. Several case studies are carried out applying the Γ -robustness concept to take into account the demand uncertainties. We investigate the dependency of the robustness parameter Γ on the overall costs and possible cost savings by enabling layer-skipping.

Introduction and Motivation

Today's telecommunication networks utilize different technologies for transporting multiple services like voice calls, web-content, television and business services. The traffic transported in networks is steadily increasing and operators have to extend their network capacities and migrate to new technologies. In the competitive market operators want to reduce overall network costs as much as possible. The nature of multi-layer networks allows a wide range of technological possibilities for transporting traffic through its layers. Evaluating all technological feasible interconnections provides a great potential in capital expenditures (CAPEX) savings. Also operational expenditures (OPEX) reductions are possible due to the different energy consumption of the network equipment of each layer.

The traffic demand influences network planning fundamentally. Conservative traffic assumptions lead to over provisioning and underestimated traffic values to a congested network. To strike a balance between these two extremes, concepts of uncertain demand modeling can be applied. The simplest way is to allocate a safety gap to the given traffic demand values. More sophisticated concepts are the Γ -robust approach by Bertsimas and Sim [START_REF] Bertsimas | Robust discrete optimization and network flows[END_REF][START_REF] Bertsimas | The price of robustness[END_REF] and the hose model approach by Duffield et al. [START_REF] Duffield | A flexible model for resource management in virtual private networks[END_REF]. Other formulations use stochastic programming, chance-constraints or a network design with several traffic matrices. Appropriate uncertainty models incorporate statistical insight of available historical data e.g. mean and peak demand values.

A further network planning challenge is the determination which technologies should be used in a multi-layered network. Multi-layer networks offer a high flexibility regarding the possibility of traffic offloading. Note that, it is not necessary that all nodes support all technologies.

Investigations about single-layer networks with uncertainty were performed for example by Koster et al. in [4] or by Orlowski in [START_REF] Orlowski | Optimal design of survivable multi-layer telecommunication networks[END_REF]. They focus on a logical (demand) layer and one physical layer. Multi-layer network models without demand uncertainty were proposed for example by Katib in [START_REF] Katib | IP/MPLS over OTN over DWDM multilayer networks: Optimization models, algorithms, and analyses[END_REF] or Palkopoulou in [START_REF] Palkopoulou | Homing Architectures in Multi-Layer Networks: Cost Optimization and Performance Analysis[END_REF]. The former deals with a strict layer structure of Internet Protocol/Multiprotocol Label Switching (IP/MPLS) over Optical Transport Network (OTN) over Dense Wavelength-Division Multiplex (DWDM) and the latter evaluates the influence of multi-homing in a multi-layer networking scenario. A multilayer network model with uncertainty was suggested in [START_REF] Belotti | A comparison of OTN and MPLS networks under traffic uncertainty[END_REF] by Belotti et al. The authors apply the Γ -robust optimization approach for a two-layer network scenario (MPLS, OTN) with demand uncertainty. In [START_REF] Kubilinskas | Design models for robust multi-layer next generation Internet core networks carrying elastic traffic[END_REF] Kubilinskas et al. propose three formulations for designing robust two-layer networks.

In this paper we deal with the following problem: Determine a cost optimal multi-layer network design allowing technology selection at each node and incorporating traffic demand uncertainty. Compared to other formulations, our proposed MILP formulation yields full flexibility regarding the number of layers and integrates layer-skipping and router offloading.

The paper is structured as follows: In Sect. 2 we shortly describe the relevant layers in today's communication networks. We present a generic multi-layer network optimization model and include traffic uncertainty constraints. Section 3 describes the input data used in the case studies: network topologies, traffic demand data, path sets and cost figures. The results of the multi-layer network optimization with demand uncertainty are presented in Sect. 4. Section 5 concludes the paper and gives an outlook on our future work.

Optimization Model

Generally, core networks may comprise the following technological layers: IP layer, MPLS layer, OTN layer and DWDM layer. With MPLS, network operators can establish explicit paths independently from the IP routing. OTN is specified in ITU-T G.709 [START_REF]Interfaces for the optical transport network[END_REF] and defines optical network elements enabling transport, switching and multiplexing of client signals. OTN introduces different Optical Transport Units (OTU) which serve as optical channel wrapper for Optical Data Units (ODU) in several granularities. Beyond OTN the optical multiplexing of different wavelengths onto one single fiber is realized by DWDM technology.

The traffic demand and its fluctuation can be treated as a further, logical layer. Thus, in our investigations we deal with five different layers.

A generic multi-layer network model was proposed in [START_REF] Palkopoulou | Homing Architectures in Multi-Layer Networks: Cost Optimization and Performance Analysis[END_REF] to evaluate different homing architectures. We apply some modifications to this model and extend it to cope with traffic demand uncertainty.

Given is a set of layers L and for all ℓ ∈ L an undirected graph with node set N ℓ and edges E ℓ . A path set P ℓ,j with candidate paths is introduced for each layer ℓ ∈ L and all commodities j. The interaction of two layers is also modeled by an edge. In the set I ℓ,n different basic node types per layer ℓ ∈ L and per node n ∈ N ℓ are specified. We define δ ℓ (n) to be the set of neighboring nodes of node n in layer ℓ.

We define the notation of layer sets as follows: L ℓ specifies the set containing all layers below the current layer ℓ. With L ℓ the set of layers above the current layer ℓ is indicated. We denote the highest, logical layer (DEMAND) with ℓ max and the lowest, physical layer (DWDM) with ℓ 0 . Layers with subinterfaces are contained in L sub .

The notation for the flow-variables x i,ii,iii,iv is as follows: i is the source layer, ii the destination layer, iii the commodity or edge and iv the candidate path. The demand parameter α ℓ,e specifies the nominal value and αℓ,e the deviation value (difference between peak and nominal) of all demands between a node pair j/edge e in layer ℓ.

Approach for Uncertainty

Traffic demand uncertainty is introduced in a general way. Fluctuations are described through the variables β ℓ,e for all layers ℓ ∈ L and edges e ∈ E ℓ . As uncertainty can be handled in different ways this allows us a universal formulation for these uncertainty variables. The uncertain traffic demand is transported in fractions across different layers.

We apply edge-based flow conservation. The constraints (1) describe the flow conservation including the uncertainty. On the left hand side all demands from higher layers except the highest layer are summed up and have to be less or equal to the sum of all outgoing demands on the right hand side. The multiplexing factor µ s,ℓ converts capacity granularities between the source s and current layer ℓ. Variables x s,ℓ,j,p contain the amount of traffic flowing in and x ℓ,s,e,p out of the current layer. With β ℓ,e we increase the amount of incoming demand by the uncertain demand. Via parameters α ℓ,e direct demand on a certain edge e in a layer ℓ is allowed.

s∈L ℓ \{ℓmax}, j∈Es, p∈P ℓ,j : e∈p µ s,ℓ x s,ℓ,j,p + α ℓ,e + β ℓ,e ≤ s∈L ℓ , p∈Ps,e x ℓ,s,e,p ∀ℓ ∈ L\ {ℓ 0 } , ∀e ∈ E ℓ .

(1)

We decided to use the Γ -robust approach by Bertsimas and Sim [START_REF] Bertsimas | Robust discrete optimization and network flows[END_REF][START_REF] Bertsimas | The price of robustness[END_REF] where the fluctuation variables β ℓ,e contain the worst case demand variation. New supplementary flow variables x are introduced. Uncertain flows start from layer ℓ max and terminate at a subset of lower layers. This holds true for all paths p in layer ℓ and for all commodities j. The formulation (2) explains the concept of Γ -robustness. The binary variables v j,p are relaxed to 0 ≤ v j,p ≤ 1 and are used to select at most Γ fractional demands to be on their peak value. The maximization ensures that these Γ uncertain demand fractions are chosen which have the largest influence on the necessary edge capacity. maximize j∈Es, p∈P ℓ,j : e∈p âj xs,ℓ,j,p v j,p

s.t. j∈Es v j,p ≤ Γ 0 ≤ v j,p ≤ 1 ∀s ∈ L, ∀e ∈ E ℓ , ∀ℓ ∈ L ℓmax (2)
As proposed in [START_REF] Bertsimas | Robust discrete optimization and network flows[END_REF][START_REF] Belotti | A comparison of OTN and MPLS networks under traffic uncertainty[END_REF] this linear program can be dualized. The dual problem (DP) of the optimization problem in (2) is shown in [START_REF] Duffield | A flexible model for resource management in virtual private networks[END_REF]. Compared to (2) the new dual variables ϑ ℓ,e and π ℓ,e,j,p are introduced. minimize Γ ϑ ℓ,e + j∈Es, p∈P ℓ,j : e∈p π ℓ,e,j,p s.t. ϑ ℓ,e + π ℓ,e,j,p ≥ αj xs,l,j,p ϑ ℓ,e , π ℓ,e,j,p ≥ 0 ∀s ∈ L, ∀e ∈ E ℓ , ∀ℓ ∈ L ℓmax [START_REF] Duffield | A flexible model for resource management in virtual private networks[END_REF] We use the DP to limit the lower bound of β ℓ,e in our multi-layer network optimization model with uncertainty as shown in constraints (4) and [START_REF] Orlowski | Optimal design of survivable multi-layer telecommunication networks[END_REF].

Γ ϑ ℓ,e + j∈Es, p∈P ℓ,j : e∈p π ℓ,e,j,p ≤ β ℓ,e ∀ℓ ∈ L\L 0 , ∀e ∈ E ℓ (4) ϑ ℓ,e + π ℓ,e,j,p ≥ µ ℓmax,ℓ αj xℓmax,ℓ,j,p ∀j ∈ E ℓmax , ∀p ∈ P ℓ,j : e ∈ p (5)
By constraints [START_REF] Katib | IP/MPLS over OTN over DWDM multilayer networks: Optimization models, algorithms, and analyses[END_REF] the sum of all fractions of uncertain demand x are enforced to be one.

ℓ∈L\{ℓmax}, p∈P ℓ,j xℓmax,ℓ,j,p = 1 ∀j ∈ E ℓmax (6)
Uncertainty also has to be applied to the inter-layer node capacities. The number of access interfaces h between the layers is influenced by the additional demand entering this specific layer. We introduce new constraints for the lower bound of access interfaces originating in the highest layer into all other layers. The Γ -robustness is introduced by additional dual variables ν ℓ,n and λ ℓ,n,j,p and reused fractional variables x. These extensions are shown in constraints [START_REF] Palkopoulou | Homing Architectures in Multi-Layer Networks: Cost Optimization and Performance Analysis[END_REF] and [START_REF] Belotti | A comparison of OTN and MPLS networks under traffic uncertainty[END_REF].

Γ ν ℓ,n + j∈δ ℓ (n), p∈P ℓ,j λ ℓ,n,j,p ≤ h ℓmax,ℓ,n ∀ℓ ∈ L\ {ℓ max } , ∀n ∈ N ℓmax (7)
ν ℓ,n + λ ℓ,n,j,p ≥ η ℓmax,ℓ αj xℓmax,ℓ,j,p ∀ℓ ∈ L\ {ℓ max } , ∀n ∈ N ℓmax , ∀j ∈ δ ℓ (n) , ∀p ∈ P ℓ,j (8)
With ( 1) and ( 4) to (8) all requirements for handling traffic demand uncertainty in the generic multi-layer network optimization model are specified.

MILP with Uncertainty Extension

The objective ( 9) is to minimize the overall costs in all layers ℓ ∈ L. Costs are induced by all basic nodes k ℓ and deployed interfaces y ℓ (access and network interfaces) in each layer ℓ.

minimize ℓ∈L (k ℓ + y ℓ ) (9)
For the intra-layer demand the needed number of network interfaces z ℓ,e are calculated by summing up all demands for all commodities in this layer -see constraints [START_REF]Interfaces for the optical transport network[END_REF].

j∈E ℓ , p∈P ℓ,j : e∈p x ℓ,ℓ,j,p ≤ z ℓ,e ∀ℓ ∈ L, ∀e ∈ E ℓ (10)
The inter-layer node capacities for all demands not originating in the highest layer have to fulfill the constraints [START_REF] Orlowski | SNDlib 1.0-survivable network design library[END_REF].

j∈δ ℓ (n), p∈P ℓ,j η s,ℓ x s,ℓ,j,p ≤ h s,ℓ,n ∀ℓ ∈ L\{ℓ max }, ∀s ∈ L ℓ \{ℓ max }, ∀n ∈ N s (11)
Edges from and a specific node might be used and thereby require installation of network interfaces. For cost calculation the number of installed network interfaces at a node is needed. This is formulated in constraints [START_REF] Huelsermann | Cost modeling and evaluation of capital expenditures in optical multilayer networks[END_REF]. z ℓ,e contains the number of network interfaces on edge e and w ℓ,n the number of network interfaces at node n of layer ℓ.

e∈δ ℓ (n) z ℓ,e ≤ w ℓ,n ∀ℓ ∈ L, ∀n ∈ N ℓ (12)
Some layers have a maximum demand limit per edge. This restriction is modeled in constraints (13) using parameter γ ℓ,e . z ℓ,e ≤ γ ℓ,e ∀ℓ ∈ L, ∀e ∈ E ℓ [START_REF] Koster | Towards robust network design using integer linear programming techniques[END_REF] For the node capacity constraints we have to distinguish between layers with and without subinterfaces. In both cases the node capacity is determined by the number of network interfaces w ℓ,n and the access interfaces h s,ℓ,n into this layer ℓ. In case of subinterfaces a conversion factor η s,ℓ is used. This is shown in constraints ( 14) and (15).

w ℓ,n + s∈L ℓ h s,ℓ,n ≤ q ℓ,n ∀ℓ ∈ L\L sub , ∀n ∈ N ℓ ( 14
)
w ℓ,n + s∈L ℓ η s,ℓ h s,ℓ,n ≤ q ℓ,n ∀ℓ ∈ L sub , ∀n ∈ N ℓ (15)
Finally, in constraints ( 16), the costs are calculated based on the number of interfaces deployed in all nodes. The parameters ϕ ℓ for basic nodes in layer ℓ and χ s,ℓ for access interfaces between layer s and ℓ are input parameters from the applied cost model.

n∈N ℓ ϕ ℓ w ℓ,n + s∈L ℓ , n∈N ℓ χ s,ℓ h s,ℓ,n ≤ y ℓ ∀ℓ ∈ L (16)
The parameter ψ ℓ,d represents the basic node costs depending on the basic node size d and layer ℓ. A binary decision variable r ℓ,d,n is used to decide whether this node type is used. The overall costs of all basic nodes k ℓ in a specific layer ℓ are derived by applying constraints (17).

n∈N ℓ , d∈I ℓ,n ψ ℓ,d r ℓ,d,n ≤ k ℓ ∀ℓ ∈ L (17)
The maximum number of interfaces of a node is specified by the basic node type and its capacity. Constraints (18) give an upper bound for the total number of deployed interfaces q ℓ,n .

q ℓ,n ≤ d∈I ℓ,n dr ℓ,d,n ∀ℓ ∈ L, ∀n ∈ N ℓ (18)
We restrict the installation of basic nodes at a location to exactly one type. This is enforced by constraints (19).

d∈I ℓ,n r ℓ,d,n ≤ 1 ∀ℓ ∈ L, ∀n ∈ N ℓ (19)
All bounds and limitations of the optimization variables are listed in (20).

k ℓ , y ℓ ≥ 0 ∀ℓ ∈ L x s,ℓ,j,p ≥ 0 ∀ℓ ∈ L, ∀s ∈ L, ∀j ∈ E s , ∀p ∈ P s,j xℓmax,ℓ,j,p ≥ 0 ∀ℓ max ∈ L max , ∀ℓ ∈ L, ∀j ∈ E ℓ , ∀p ∈ P ℓ,j z ℓ,e ∈ Z + ∀ℓ ∈ L, ∀e ∈ E ℓ h s,ℓ,n ∈ Z + ∀ℓ ∈ L, ∀s ∈ L ℓ , ∀n ∈ N ℓ w ℓ,n ≥ 0 ∀ℓ ∈ L, ∀n ∈ N ℓ q ℓ,n ∈ Z + ∀ℓ ∈ L, ∀n ∈ N ℓ r ℓ,d,n ∈ {0, 1} ∀ℓ ∈ L, ∀n ∈ N ℓ , ∀d ∈ I ℓ,n ϑ ℓ,e , π ℓ,e,j,p ≥ 0 ∀ℓ ∈ L, ∀j ∈ E ℓmax , ∀p ∈ P ℓ,j : e ∈ p ν ℓ,n , λ ℓ,n,j,p ≥ 0 ∀ℓ ∈ L\ {ℓ max } , ∀n ∈ N ℓmax , ∀j ∈ δ ℓ (n) , ∀p ∈ P ℓ,j (20)

MILP Size Estimation

In order to compare the complexity of the non-robust model with the model that includes Γ -robustness, we perform an estimation of the model sizes. In the following n is the number of nodes in all layers and p the overall number of paths in all layers.

The order of the number of variables increases from n 2 to n 2 p and the order of the created number of constraints increases from n 2 p to n 4 p for the model with uncertainty. This is caused by the dual variables and the required constraints for modeling the uncertainty in flow conservation and inter-layer node capacity.

The MILP size is a critical point in terms of computation time and optimality gap. A possible reduction of the model size can be achieved by merging layers, decreasing the set of candidate paths in selected layers and by omitting nodes in specific layers.

Input Data for the Case Studies

Example Network Topologies

It is assumed that all layers comprise the same node set. First of all, we define an artificial, small-scale 5-node network topology. It contains nodes A to E, bidirectional edges (A,B),(A,D),(A,E),(B,C),(C,D),(C,E) and has an average nodal degree of 2.40. Furthermore, we use the Abilene and Géant topologies from SNDlib [START_REF] Orlowski | SNDlib 1.0-survivable network design library[END_REF]. Abilene is a reference for a mid-scale network containing 12 nodes (avg. nodal degree 2.50) and Géant is a large-scale network with 22 nodes (avg. nodal degree 3.27).

Traffic Demand

For the 5-node network we assume nominal demand values of α = 20 GBit/s for all end-to-end node pairs. Overall 10 demand pairs exist in this network. The deviation of the demand values are assumed to be α = 0.5 • α for node pairs (A, B), (A, D) and to be α = 0.25 • α for the other node pairs. For Abilene and Géant traffic measurement traces can be found in SNDlib [START_REF] Orlowski | SNDlib 1.0-survivable network design library[END_REF]. We use the first week measurements and set α to the nominal value and α to the maximum minus the nominal value. In total Abilene has 66 and Géant 462 demand pairs.

Network Layers

In our case studies we consider five network layers: One logical layer DEMAND and four technological layers IP, MPLS, OTN and DWDM. However, the MILP theoretically supports an unlimited number of layers.

In Table 1 technologically feasible mappings between the layers are shown. We distinguish between variable and top-bottom configuration. The top-bottom configuration is a worst case scenario in terms of overall costs as all layers have to be used by all demands. The variable configuration enables a technology selection by skipping some of the layers.

For our calculations it is assumed that all layers have a interface granularity of 40 GBit/s except the logical demand layer which has a granularity of 1 GBit/s.

Cost Model

We only consider CAPEX costs for our case studies. In [START_REF] Huelsermann | Cost modeling and evaluation of capital expenditures in optical multilayer networks[END_REF] by Huelsermann et al. a CAPEX cost model for multi-layer networks is provided where the costs are separated into three main parts:

1. Basic node costs: chassis, power supplies, cooling, etc. 2. Interface costs: interfaces placed within one layer ℓ 3. Access interface costs: interfaces from a layer s to a layer ℓ All costs are normalized to the costs of a single 10G long-haul transponder and without any reference to a specific vendor. Basic node costs depend on the number of available slots. For IP and MPLS 16, 32, 48 and 64 slots with corresponding costs of 16.67, 111.67, 140.83 and 170.0 are distinguished. The costs for IP and MPLS equipment are assumed to be equal.

Path Sets

In the DWDM layer k-shortest paths are calculated choosing k = 5 for smallto mid-scale and k = 2 for large-scale networks. The DWDM-paths are modified and extended to provide path sets for the higher layers.

In [START_REF] Palkopoulou | Homing Architectures in Multi-Layer Networks: Cost Optimization and Performance Analysis[END_REF] different bypassing options Unrestricted, Restricted, Opaque and Transparent were proposed. These options create different candidate paths for an end-to-end connection within a single layer. We apply the Restricted, Opaque and Transparent option for non-DWDM path sets. In addition to the k-shortest paths (Opaque) also the direct connection between source and destination exists (Transparent, bypassing at all intermediate nodes). Further paths are introduced by the Restricted option where specific nodes are skipped after a specific node hop count is exceeded. By use of these path sets we allow, that specific nodes might be skipped and traffic is offloaded. We assume a fully meshed graph in the logical DEMAND layer.

Results

In this section we present the results of our case studies. The main target is to evaluate whether our multi-layer network optimization model with uncertainty is solvable for realistic problem sizes applying off-the-shelf solvers.

For our calculations we use a conventional PC with multi-core CPU (Intel R ⃝ Core TM i7-3930K CPU @ 3.20GHz) and 64 GBytes of memory. Operating system is Ubuntu in version 11.04. AMPL is used in version 20111121 and IBM R ⃝ ILOG R ⃝ CPLEX R ⃝ in version 12.5. For the MIP gap tolerance the CPLEX default value of 1e-4 is used and the time limit is set to 86400s (1 day).

In [START_REF] Koster | Towards robust network design using integer linear programming techniques[END_REF] was shown that choosing Γ to about 6% of the number of demands is already sufficient to provide total robustness. Therefore, we perform a parameter study regarding Γ and increase it from 0 (no uncertainty) up to 10 (at most ten demands on peak value). With the top-bottom configuration the overall realruntime for the 5-node network is 124.2s (user-runtime 1264.6s). As can be seen from Fig. 1 increasing Γ rises the CAPEX costs up to 23% and influences mainly the DWDM layer. The reason is that the traffic demand is in the range of 50% of the interface capacities. Already two demands on nominal value utilize the interfaces completely. The course of the curve for the variable configuration is similar, except that the MPLS and OTN layers are skipped. The cheapest solution is to apply IP-over-DWDM in this case. The calculation time for variable configuration is slightly smaller compared to top-bottom with a real-runtime of 73.6s (user-runtime 672.9s). CAPEX increases by 25.6% when Γ is varied from 0 to 10. In case of the variable configuration the optimization results for Abilene and Géant are different compared to the 5-node network: the OTN layer is not skipped. The computing times and memory requirements increase substantially. For Abilene the computing time increases to a real-runtime of 218999.3s (userruntime 1835679.0s) and for Géant to a real-runtime of 39625.0s (user-runtime 401265.4). The reason why Géant has a lower runtime is that only a set of k = 2 shortest paths are used compared to k = 5 for Abilene. If we use k = 5 also for Géant, CPLEX terminates with a out of memory exception.

In Fig. 2, for the Géant network a strong dependency on the parameter Γ can be observed. Already the step from no uncertainty to Γ = 1 raises CAPEX by 70.4%. For Γ = 10 a CAPEX increase of 117.2% is discovered.

The cost of the Abilene network does not change when introducing uncertainty. Independently from Γ the CAPEX costs are 1537.04 for the IP layer, 117.05 for the OTN layer and 86.76 for the DWDM layer. The MPLS layer is skipped. For none of the Abilene-runs the optimality gap was reached. Probably the reason is that the traffic demands do not match well to the granularity of the interface capacities yielding sufficient spare capacity to accommodate the traffic fluctuations. It is planned to perform further investigations on this issue.

For both topologies (Abilene, Géant) the MPLS layer is skipped, but the OTN layer is used for grooming IP demands. This behavior is correct as the cost parameters of IP and MPLS are assumed to be equal.

Conclusion and Outlook

We introduced a generic multi-layer network optimization model with traffic uncertainty applying the Γ -robust approach. The model has full flexibility regarding the number of layers. Path sets are calculated with the special bypassing options Unrestricted, Restricted and Opaque or Transparent. These options allow router offloading and shortcuts for selected layers. Two possible layer mapping configurations top-bottom and variable are considered. The former yields a worstcase solution for passing all layers with shortcuts and the latter a cost minimal solution with shortcuts and layer-skipping. We evaluated the MILP for different network sizes. Compared to the nonrobust model the computing time for the robust model increases significantly. When using off-the-shelf solvers especially in mid-and large-scale networks todays computational power is still not sufficient to solve the problem to an optimality gap of 1e-4. Hence, more advanced mathematical techniques for modeling and solving are needed.

By decreasing the size of the path sets for specific layers and the optimality gap for the multi-layer network model with uncertainty even large-scale networks remain solvable. Computing times are reasonable but the solver requires very large memory for improving the initial solution. Also modeling alternatives should be investigated for their potential to decrease the memory consumption for larger networks.

In our future work we will investigate several options to improve scalability and memory consumptions. We will analyze how different robustness metrics are influenced by the Γ parameter setting. Furthermore, we will continue our studies with an improved cost model allowing more realistic comparisons of the MPLS and the OTN layer options.

Fig. 1 .

 1 Fig. 1. CAPEX costs versus Γ uncertainty parameter for the 5-node network with top-bottom configuration

Fig. 2 .

 2 Fig. 2. CAPEX costs versus Γ uncertainty parameter for the Géant network with variable configuration

Table 1 .

 1 Layer mapping configurations top-bottom and variable

	configuration layer ℓ	L ℓ	L ℓ
		DEMAND ∅	IP
		IP	DEMAND	MPLS, OTN, DWDM
	variable	MPLS	IP	OTN, DWDM
		OTN	IP, MPLS	DWDM
		DWDM	IP, MPLS, OTN ∅
		DEMAND ∅	IP
		IP	DEMAND	MPLS
	top-bottom	MPLS	IP	OTN
		OTN	MPLS	DWDM
		DWDM	OTN	∅

Acknowledgments. This work was supported by the German Federal Ministry of Education and Research (BMBF) via the research project ROBUKOM [14].


Martin Drašar
email: drasar@ics.muni.cz

Protocol-Independent Detection of Dictionary Attacks

Keywords: traffic classes, anomaly detection, network behavior analysis

Data throughput of current high-speed networks makes it prohibitively expensive to detect attacks using conventional means of deep packet inspection. The network behavior analysis seemed to be a solution, but it lacks in several aspects. The academic research focuses on sophisticated and advanced detection schemes that are, however, often problematic to deploy into the production. In this paper we try different approach and take inspiration from industry practice of using relatively simple but effective solutions. We introduce a model of malicious traffic based on practical experience that can be used to create simple and effective detection methods. This model was used to develop a successful proof-of-concept method for protocol-independent detection of dictionary attacks that is validated with empirical data in this paper.

Introduction

Conventional methods of deep packet inspection (DPI) are being replaced with methods of network behavior analysis (NBA). The ordinary traffic volume often exceeds units and tens of gigabits per second. This is a problem for classic methods of DPI and signature matching that start to demand more processing power than the current hardware can supply. NBA methods are seen as a potential remedy, because of their ability to work with aggregated data and to detect unknown threats [START_REF] Sperotto | An Overview of IP Flow-Based Intrusion Detection[END_REF].

The development of NBA methods diverged into two branches that pursue different goals using different means. On the one hand, there is the academic research with a lot of theoretical work and application of sophisticated concepts. On the other hand, there is the industry practice of using relatively simple, but effective methods to protect from current threats.

In this paper we try to bring these two branches together by introducing a model of an attack traffic based on practical experiences with network protection in the University's CSIRT 1 . This model can be used to design anomaly detection schemes that are effective and relatively easy to implement as is demonstrated by creating a proof-of-concept method for detection of dictionary attacks.

This paper is divided into six sections. Section 2 describes dictionary attacks. It also presents current advancements in dictionary attack detection and evaluates their detection schemes. Section 3 introduces the concept of traffic classes to describe attacking traffic. Section 4 is focused on a connection between traffic classes and different types of attacks. Section 5 presents the detection method based on properties of one traffic class and also evaluates its effectiveness. Section 6 concludes the paper.

Dictionary Attacks

Dictionary attacks exploit valid authentication mechanism, abusing the fact that users tend to choose weak credentials [START_REF] Menezes | Identification and Entity Authentication[END_REF]. It is complicated to detect such attacks, especially low-profile ones, because an isolated attack attempt differs from a legitimate one only by intention and not any measurable properties. That is why they are so prevalent [START_REF]SSH Password Authentication Report[END_REF], [START_REF] Seifert | Analyzing Malicious SSH Login Attempts[END_REF], [START_REF] Thames | A Distributed Active Response Architecture for Preventing SSH Dictionary Attacks[END_REF]. However, they do not receive enough academic attention as most research is focused on DoS attacks, botnet activity and other disturbant behavior [START_REF] Sperotto | An Overview of IP Flow-Based Intrusion Detection[END_REF].

There is a large variety of industry-provided tools to detect dictionary attacks. They are often tied to one particular service and detection is done on a machine or an application level. Such tools, however, often lack knowledge of network context and can be bypassed by distributed low-profile attacks. Agentbased [START_REF] Dasgupta | CIDS: An agent-based intrusion detection system[END_REF] and SIEM systems partially solve this problem by matching anomalies from end computers in one central point. They require specific software to be configured in end computers and thus fail with BYOD paradigm, though. Network-level monitoring gives a context and does not require any alteration in end computers.

We present four tools for network-level detection of dictionary attacks. SSH-Monitor detects SSH attacks by matching attack signatures [START_REF] Vykopal | A Flow-Level Taxonomy and Prevalence of Brute Force Attacks[END_REF]. It also comes with an observation that an attack is always preceded with a port scan and that most often two or more machines are targeted. SSHCure is based on an observation that an SSH attack is divided into three phases with distinct flow properties: the scanning phase, the brute-force phase and the die-off phase [START_REF] Hellemons | SSHCure: A Flow-Based SSH Intrusion Detection System[END_REF].

RdpMonitor is an extension of previous tools that is focused on a detection of RDP attacks [START_REF] Vizváry | Flow-based Detection of RDP Brute-force Attacks[END_REF]. Honeyscan uses synergy of honeypots and network monitoring to detect various dictionary attacks [START_REF] Husák | Flow-based Monitoring of Honeypots[END_REF].

These tools, although each taking a different approach, share similar properties. They use thresholds, focus on statistical properties, and do not take into account the character of a traffic, i. e. variations in attack. Attackers could easily subvert these tools by changing their behavior, but practical experience shows they are not likely to. One reason is the supply of bruteforcing tools that in general operate on the same principle. They attack as much as a network or a user lets them and do not alter traffic character. Their attacks are then very similar and therefore detectable. In the terminology described further, they all belong to one traffic class.

Traffic Classes

A traffic class is a concept that tries to formally describe the character of an attack traffic by focusing on markers of automated action without special-casing for networks of different sizes. It is tailored for NetFlow, but it can be modified to work with e. g. packets. A basic primitive in this concept is a slice -a set of flows from one source IP address in a given time interval. This slice is characterized by four traffic dimensions.

The first traffic dimension is visibility that describes traffic in terms of newly created flows. It is quantized into two values that are functions of current defense capabilities of given network. Traffic in a slice is visible if there is at least one detection mechanism in a network that will mark it as anomalous/suspicious based on flow analysis. Traffic in a slice is stealthy otherwise. As a result the dimension is relevant for networks of different sizes and detection capabilities.

The second dimension is periodicity that describes temporal relations between flows in a slice. It has three possible values. Aperiodic traffic has no discernible pattern in flow occurrence. Periodic traffic has a pattern in flow occurrence. Constant traffic has roughly the same number of flows in all slices of the same length.

The third dimension is similarity that deals with flow similitude. Flows in a slice can be similar or different based on arbitrary criteria. In this paper we use overall byte count and duration as a discriminant.

The fourth dimension is the target count that has two possible values: one target and many targets.

Dimensions that we introduced are orthogonal, so one value for each dimension can be chosen for every traffic sample. Therefore, any traffic can be described as a combination of these dimensions. Let any such combination of traffic dimensions be called the traffic class.

Relation Between Traffic Classes and Attacks

By combining all dimensions we get 24 traffic classes in total. However, they can be categorized into several groups depending on a dominant detectable dimension.

The first group is noisy traffic that consist of all visible combinations. Because traffic is considered visible if it was marked as an attack by at least one mechanism, this entire group of traffic classes is marked as an anomaly or an attack. Although this group covers one half of traffic classes, it does not necessarily cover half of attacks a network is facing. For example, a network with only a port scan detection based on thresholding would be able to detect periodic, aperiodic and distributed scanners, but would fail to detect dictionary attacks, DoS or massive spamming.

The second group is flat traffic that consist of stealthy and constant combinations. This group covers traffic generated by bruteforcing tools as described in Section 2. Traffic with constant pattern that is disrupted only by network conditions and eventual proxy delays. However, not all flat traffic can be considered anomalous or harmful as there are valid use cases for such pattern, e. g. keep-alive. It is important to be aware that constant traffic is defined in terms of constant creation of new flows in given slice and not e. g. constant byte rate. Such constant appearance of new flows in case of authenticated protocols like SSH or RDP is always suspicious.

The third group is spiked traffic that consist of stealthy and periodic combinations. This group is a superset of flat traffic and it contains anomalies like beaconing [START_REF] Balland | An Analysis of Network Beaconing Activity for Incident Response[END_REF], but also a lot of traffic that looks anomalous but in fact is not.

The fourth group is episodic traffic that consist of stealthy and aperiodic combinations. This group is interesting because there is no discernible pattern in flow occurrence. Virtually nothing in the character of traffic points to whether it is an attack or not. Unless an attacker crosses some threshold, such attacks are undetectable on a network level.

Detecting Dictionary Attacks by Detecting Flat Network Traffic

In this section we present a proof-of-concept method that is built upon the assertion that flat traffic to authenticated services is always suspicious. We then analyze results of this method and compare it with other detection mechanisms running in the same network. This method was developed and tested in the campus network of Masaryk University (about 15.000 devices online every day) in the course of two months from February 24, 2013 to April 24, 2013.

When designing the detection method, we have directly applied the definition of constant traffic that says that traffic is constant if all slices of the same length have roughly the same number of flows. However, we had to decide on three key characteristics -length of slices, their relative temporal position, and measure of their equal flow count. For the sake of brevity, we omit analyses behind our choices and present here only the final decisions. These analyses, however, are available upon request.

The method works with 60 second slices of 5-minute batches of NetFlow data. These slices are adjacent and non-overlapping, i. e. there are at most 5 slices for one source IP address in a batch. Slice flow count equality is given by a function that measures the relative difference between flow count in adjacent non-zero slices. The method was successfully used with following protocols: FTP(S), SSH, Telnet, LDAP, HTTP(S), AFP, RDP and SMTP. Flat traffic detection for HTTP(S) was found to be ineffective, because valid AJAX updates common on Web 2.0 tend to produce flat traffic pattern.

Identification of Attackers

Figure 1 presents the number of identified instances of flat traffic in 5-minute traffic windows and unique source IP addresses for various thresholds of relative difference. Only differences up to 100 % were taken into account. Anything higher was automatically considered non-flat traffic. As was expected, series of identified source IP addresses grow faster than the graphs of attacks. In case of SSH and RDP services that are often targets of attacks, even the 50 % threshold was enough to identify more than 90 % of potential attackers. Ground-truth evaluation of data is complicated because the detection was carried out on an unannotated data, therefore, we have decided to compare our results with three other detection mechanisms deployed in the same network. We chose 60 % as a relative difference threshold and identified 3139 unique IP addresses targeting port TCP/3389. RdpMonitor [START_REF] Vizváry | Flow-based Detection of RDP Brute-force Attacks[END_REF] that detects attacks on this port found at the same time 852 attackers of which our method detected 410. Our method also identified 320 unique IP addresses targeting port TCP/22. SSHMonitor [START_REF] Vykopal | A Flow-Level Taxonomy and Prevalence of Brute Force Attacks[END_REF] found 29 attackers on this port of which we found 5, and honeyscan [START_REF] Husák | Flow-based Monitoring of Honeypots[END_REF] found 57 attackers of which we found 15. Manual inspection of a sample of remaining addresses undetected by other tools concluded that they were likely to be actual attacks. However, conclusive proof is not available because the data on targeted end hosts is not available. The likely reason why the proof-of-concept method detects order of magnitude more attackers than deployed methods is their high threshold to avoid false positives.

Conclusion

In this paper we have presented a model of attack traffic that puts emphasis on a distinction between artificial and human-initiated traffic. Based on this model, we created the proof-of-concept method that successfully detects one type of attacks against various services. By applying concepts of this model, other methods can be devised that will detect other previously overlooked attacks that currently hide below detection thresholds. Relative simplicity of this model and its application also lowers bars for industry adoption.

Detection of malicious traffic based on a character of traffic proved to be a promising approach. In our future work, we will explore other detection schemes based on a character of traffic that can be used as a stand-alone or complementary detection mechanisms. We will also research other possible traffic classes and their respective groupings.

Fig. 1 .

 1 Fig. 1. Amount of flat traffic and its sources based on a relative difference threshold

Computer Security Incident Response Team -organizational unit responsible for maintaining security of the University's network

Acknowledgment This paper is based on a work supported by the Czech Ministry of Interior under Identification code VF2013201531.


Giulia Mauri
email: gmauri@elet.polimi.it

Giacomo Verticale
email: vertical@elet.polimi.it

Distributing Key Revocation Status in Named Data Networking

Introduction

Content Centric Networking (CCN) [START_REF] Jacobson | Networking named content[END_REF] is a new network paradigm designed to satisfy user needs considering the growth of data demand. Named Data Networking (NDN) [START_REF] Zhang | Named data networking (ndn) project[END_REF] is a research project that is developing the future Internet architecture using the principles behind CCN. In this novel architecture, the contents are addressed by their name and not by their location. Thus, the attention is shifted from user to content, resulting in a caching network that is more efficient and flexible than an IP network for content distribution and management with beneficial effects on timely delivery. In NDN, the content objects are divided into chunks, each digitally signed by its producer, and most papers assume that verification is made only by the content consumer. In order to perform signature verification, a node needs the signer's key, which can be easily retrieved by issuing a standard interest message. Although content verification at the end node prevents disruptive attacks in which false data is delivered to applications, the verification of key validity is also necessary. Otherwise, false data would be cached and forwarded instead of correct data resulting in a denial of service and paving the way for more sophisticated attacks.

Indeed, content signed with a compromised key may remain in caches for an indeterminate amount of time, and possibly be served to end users. Even if caches implement a freshness mechanism that deletes content that has been in the cache longer than a given threshold, a compromised node could resend data making it extremely difficult to remove from the network the objects signed with a compromised key. In the standard PKIX (Public Key Infrastructure Certificate X.509) [START_REF] Cooper | Internet x.509 public key infrastructure certificate and certificate revocation list (crl) profile[END_REF], the issue of delivering key revocation status to the end nodes is solved by using the OCSP (Online Certificate Status Protocol) protocol [START_REF] Myers | X.509 internet public key infrastructure,online certificate status protocol -ocsp[END_REF].

This paper proposes a way to implement similar functionality of OCSP protocol in the NDN scenario. In particular, we suggest three alternative ways to guarantee key freshness proposing two reactive methods and comparing them with a proactive method that is based on the ccnx-repository synchronization protocol. Finally, we use the open-source ndnSIM [START_REF] Afanasyev | ndnsim: Ndn simulator for ns-3[END_REF] package to run simulations for different network scenarios. We evaluate the performance in terms of latency, throughput and hit ratio gained by the proposed methods.

Attacker Model

Our attacker model assumes an active eavesdropper, a malicious non-intrusive attacker, with the following properties:

-It behaves as a legitimate node of the network and communicates with any other node. In particular, it can send interests for contents and receiver the corresponding data packets; -In response to an interest message it can deliver content packets created on the fly and signed with any signature for which it knows the corresponding signing key or with an invalid signature; -In response to an interest message it can reply any content it knows even if the corresponding signing key is known to be compromised.

We observe that the attacker cannot (1) modify other nodes' routing tables and (2) break any cryptographic algorithm. The attacker purpose is to inject bad contents into the end-node caches. Particularly, the saboteur could reach his goal in two ways:

1. responding to Interests with corrupted Data packets; 2. signing false packet with a revoked key.

We consider a packet corrupted if its signature is invalid, while false if its signature is valid but generated with a compromised key.

We state that the protocol is secure if it is not possible that a honest endnode (we call it consumer or leaf node) accepts a corrupted or false packet in its cache or delivers it to its neighbors.

Our proposal

Since the attacker has the ability to retrieve and use old keys to sign messages, in this section we provide three methods to guarantee that in a predefined time interval the key has not been revoked.

In the following paragraph, first we present two reactive modes based on a CCNx approach and then we report a proactive mode based on CCNx synchronization protocol.

Nonce-based In this method, we guarantee the up-to-date status of the key assuring that the key would be sent directly by the possessor. Particularly, the requesting node sends an Interest for the key specifying the AnswerOriginKind, that is 0, and it means "do-not-answer-from-content-store". The node expects to receive a Data packet containing the key and signed with the root key.

TimeStamp-based In this case, the node sends an Interest for the key to all its neighbors specifying in the name a timestamp that indicates a threshold validity. When a node receives the Interest, it checks if it has the key and if its key TimeStamp is more recent than the Interest TimeStamp, i.e. T S I < T S D . If the condition is satisfied, the node sends the corresponding Data packet containing the key. Otherwise, the node forwards the Interest to the following node. If no node has the fresh key, the Interest is forwarded till the original key possessor.

Proactive Mode As comparison, we consider the proposal of [START_REF] Bian | Deploying key management on ndn testbed[END_REF] and we adapt it for our purpose. All the key names have the conventional prefix "/keys" in order to facilitate the key management. The keys stored in ccnx-repositories are revoked, that is all the keys that are no longer valid to sign a packet. The repositories are synchronized using ccnx-sync protocol. Particularly, the root node defines the Revoked Key Collection where it can store the keys, then a SyncAgent is responsible for keeping Repository up to date as some changes happen. Every ∆t seconds, where ∆t is a time interval longer than the timestamp of the previous section, the synchronization between root and router repositories is performed using a RootAdvise message.

Security Evaluation

We suppose indispensable in the content-centric scenario that each end-node should follow the signature verification process for each data packet and that it should check the key freshness. Moreover, we hypothesize that an attacker can only obtain or find invalid keys. In other words, we guarantee that a node doesn't accept a corrupted or false packet in its cache or delivers it to its neighbors within a time interval longer than ∆t, that depends on freshness method used. Thus, we can say that the network is secure under these assumptions.

Numerical Results

In this subsection, we present simulative results to evaluate which is the impact on network performance for implementing key retrieval. Especially, we report only data concerning delay, due to space constraints, considering the different choices that a node can make for the freshness method.

In Figure 1 are depicted the mean round trip times to obtain data and key as a function of content class (the lower is the class, the higher is the popularity). Results are reported for the first 20 classes of popularity. The round trip time is the interval of time that incurs from the first interest sent for a data till the corresponding key reception. The delay is highly correlated to the distance between user and content and also to the content popularity. Moreover, the latency depends on the freshness method used: the Nonce-based method requires more time than the others because the key is asked more frequently and it comes from the root, that is the farthest node; the proactive mode is the faster method, since the revoked key repositories are synchronized off-line; while the TimeStamp-based approach stays in the middle and it depends also on time interval length of key validity. We note that increasing the key validity interval, the delays of proactive mode and timestamp methods coincide. Observing the results, we think that the timestamp-method not only prevents nodes accepting a corrupted or false packet in their cache but also achieves the better compromise in terms of delay, throughput and hit ratio. Moreover, we believe that the proactive mode can be used when the channel capacity is limited, since the revoked key update is done off-line. While, the nonce-based method guarantees that the keys have a shorter interval of uncertainty but we have to introduce more traffic on the network and also wait more time for each content.

Conclusion

Whenever a cryptographic key is revokated, the nodes should reject all the contents signed with that key and these packets should be removed from the network. This paper compares three possible methods to achieve this result. In the reactive methods, the consumer nodes request status certificates for the keys they need. The freshness of these certificates can be verified by using nonces or timestamps. In the proactive method revocation lists are broadcast using the ccnx synchronization protocol. We compare the performance of content retrieval in terms of delay, throughput and hit ratio. We conclude that the solution based on timestamps provides the best compromise between delay and key status distribution overhead. This research represents also a first step into the problem of authenticity and integrity of contents.

Fig. 1 .

 1 Fig. 1. Mean latency related to popularity classes in tree topology considering alternative freshness methods


Lang Xie
email: langxie@item.ntnu.no

Poul E Heegaard
email: poul.heegaard@item.ntnu.no

Yuming Jiang
email: jiang@item.ntnu.no

Modeling and Quantifying the Survivability of Telecommunication Network Systems under Fault Propagation

Keywords: survivability, analytical models, fault propagation

This paper presents a generic state transition model to quantify the survivability attributes of a telecommunication network under fault propagation. This model provides a framework to characterize the network performance during the transient period that starts after the fault occurrence, in the subsequent fault propagation, and until the network fully recovers. Two distinct models are presented for physical fault and transient fault, respectively. Based on the models, the survivability quantification analysis is carried out for the system's transient behavior leading to measures like transient connectivity. Numerical results indicate that the proposed modeling and analysis approaches perform well in both cases. The results not only are helpful in estimating quantitatively the survivability of a network (design) but also provide insights on choosing among different survivable strategies.

Introduction

Telecommunication networks are used in diverse critical aspects of our society, including commerce, banking and life critical services. The physical infrastructures of communication systems are vulnerable to multiple correlated failures, caused by natural disasters, misconfigurations, software upgrades, latent failures, and intentional attacks. These events may cause degradations of telecommunication services for a long period. Understanding the functionality of a network in the event of disasters is provided by survivability analysis. Here, qualitative evaluation of network survivability may no longer be acceptable. Instead, we need to quantify survivability so that a network system is able to meet contracted levels of survivability.

Fault propagation

An undesired event is an event which impacts system normal operation. It triggers faults, which cause an error. When the error becomes visible outside the system boders, we have a failure, i.e., the system does not behave as specified. An excellent explanation of fault, error, failure pathology is given in [START_REF] Avizienis | Basic concepts and taxonomy of dependable and secure computing[END_REF]. The types of such events include operational mistakes, malicious attacks, and large-scale disasters.

When multiple network elements (e.g. nodes or links) go down simultaneously due to a common event, we have multiple correlated failures. Different from single random link or node failure, multiple failures are often caused by natural disasters such as hurricane, earthquake, tsunami, etc., or human-made disasters such as electromagnetic pulse (EMP) attacks and weapons of mass destruction (WMD) [START_REF] Reuters | Experts Warn of Substantial Risk of WMD Attack[END_REF]. Correlated failures can be cascading where the initial failures are followed by other failures caused by some propagating events. Therein, a network system may be vulnerable to a time sequence of single destructive faults. It starts by an initial event on a part of network and spreads to another part of the network. The propagation continues in a cascade-like manner to other parts. This phenomena is denoted as fault propagation. As few examples: the power outages and floods caused by 2005 US hurricane Katrina resulted in approximately 8% of all customarily routed networks in Louisiana outaged [START_REF] Kwasinski | Telecommunications power plant damage assessment for Hurricane Katrina -site survey and follow-up results[END_REF]; in the March 2011 earthquake and tsunami in east Japan, almost 6720 wireless base stations experienced long power outage [START_REF] Adachi | The restoration of telecom power damages by the Great East Japan Earthquake[END_REF]. Also, some studies warn that risk of WMD attacks on telecommunication networks is rising [START_REF] Reuters | Experts Warn of Substantial Risk of WMD Attack[END_REF]. Different from error propagation, fault propagation does not necessarily occur among interconnected network equipments. Since a fault may be an external event, it can occur in isolated parts of a network. The difference between fault propagation and error propagation is illustrated in Fig. 1. With the aim of developing a more realistic survivability model, fault propagating phenomena must be taken into account.

Related work

Survivability is defined as the system's ability to continuously deliver services in compliance with the given requirements in the presence of failures and other undesired events [START_REF] Heegaard | Network survivability modeling[END_REF]. Most of the literature on network survivability quantificaiton has been done on combating single-link or node failures [START_REF] Zolfaghari | Framework for network survivability performance. Selected Areas in Communications[END_REF], [START_REF] Yun | Survivability analysis of telephone access network[END_REF], [START_REF] Fei | On the Survivability of Wireless Ad Hoc Networks with Node Misbehaviors and Failures. Dependable and Secure Computing[END_REF]. Only a few studies have considered multiple failures. A state transition model for base station exposed to channel failures and disastrous failures was proposed in [START_REF] Jindal | Analytical survivability model for fault tolerant cellular networks supporting multiple services[END_REF]. Nevertheless, this model only considers one base station without multiple or correlated base station failures. Our previous work [START_REF] Lang | Modeling and Analysis of the Survivability of an Infrastructure-Based Wireless Network[END_REF] uses a continuous-time Markov chain (CTMC) to model and analyze the survivability of an infrastructure-based wireless network in the presence of disastrous failures and repairs. However, it considers only a single disaster scenario where failures are not correlated.

Very few studies have considered the quantification of network survivability against correlated failures caused by some propagating events. Therefore, there exists a critical need for appropriate quantitative, model-based evaluation techniques to address this limitation. In our previous work [START_REF] Lang | Network Survivability under Disaster Propagation: Modeling and Analysis[END_REF], we propose an approximative survivability model to take a disaster propagation scenario into account. To the best of our knowledge, this is the first work to quantify the survivability and the failure and repair rate tradeoffs of networks. However, such model does not distinguish the state of system before and after repair. We further relax these approximations and develop a more realistic mode in [START_REF] Lang | Modelling and Analysis of the Survivability of Telecommunication Network[END_REF]. However, only a particular case of a three-subnetwork system is considered in this work.

In this paper we generalize our previous work in [START_REF] Lang | Modelling and Analysis of the Survivability of Telecommunication Network[END_REF]. The resulting model turns out to be a general model that considers the fault propagation among n (n > 0) subnetworks. Specifically, transient failures are integrated into the proposed model. The analysis results are helpful in estimating quantitatively the survivability, in terms of certain chosen performance metrics of a network (design). Further, they provide insights on specifying the values of repair rates required to achieve a contracted service performance and availability. Our goals are providing some critical inputs for network design and operation. For example, in network deployment in coastal areas, which are vulnerable to specific disaster types like flooding as well as hurricanes, the knowledge of network survivability is useful.

The rest of the paper is organized as follows. In Section 2, we develop Markov models for a system from the survivability quantificaiton view point. Section 3 analyzes the models that may be used to find the transient probabilities leading to the computation of transient survivability measures. Numerical results of the analysis performed on the models are presented in Section 4. Finally, Section 5 gives the conclusions along with some future directions in this area.

Markov Model for Survivability Quantification

A network system that is survivable consists of network design and management procedures to mitigate the effects of failures on the network services. To analyze and quantify the survivability attributes of such a network system, we have to take into account the propagating behavior of a fault as well as the network system's response to the fault propagation. Therefore, we would require a composite survivability model that incorporates the behavior of both these elements.

Network View

The network can be viewed as a directed graph consisting of nodes and directed edges. A node can be a single network equipment or a subnetwork. The directed edges denote the directions of possible disaster propagation among various nodes. We suppose the number of subnetworks in the networked system is n (n > 0). Furthermore, we assume a disastrous event initially occurred on one subnetwork and then propagated from the affected subnetwork to another within a random time period. The process continues until no more subnetwork failures occur. Here, we mainly consider the multiple failures caused by some events such as natural disasters, intentional attacks, etc, which are among the main reasons that trigger fault propagation.

Fig. 2. Network example with three subnetworks

To illustrate the above view, we use a wireless network example. As depicted in Fig. 2, it consists of n (e.g. n = 3) subnetworks. The view shows the actual geographic layout of the network elements, such as cell site, radio network controller (RNC), mobile switching center (MSC) and so on. Assume a disastrous event occurs in subnetwork-1 at the beginning. Then the disastrous event propagates its effect to subnetwork-2, subnetwork-3 in successive steps. For the sake of illustration, the number of network elements in the figure does not necessarily equal to the real number. Our objective is to investigate the network performance during the transient period that starts after the disaster occurrence, in the subsequent disaster propagation and until the network fully recovers. For this, we define the (i) undesired events to be disastrous events, (ii) service to be the connections between access points and subscribers, (iii) service requirement to be a minimum number of access points that need to be operational for the service. It is remarked that our focus is "connectivity" and our focus is not about how to obtain the performance metric at a real network or network component. Thus we do not consider the dynamics brought by routing and traffic flows further in this paper.

We need a methodology to capture the transient variation of performance under fault propagation, as well as tractable. In what follows, we introduce a phased recovery model to quantify the survivability of network under fault propagation caused by disaster. The model is constructed stepwise, starting with only permanent hardware failures and gradually extending it to include software and transient hardware failures. The discussion here is not limited into a wireless network. We believe the methods and analysis presented can be applied to other telecommunication networks such as a public switched telephone network (PSTN), a data network, or an optical network.

Model I: Permanent hardware failures

The first model only considers failures that require manual repair, i.e., permanent hardware failures caused by the disasters (e.g. hurricanes, tornados, floods, earthquakes, and tsunamis) and environment (e.g. power outages).

A fault always tries to bring a network system into a failure state. This requires the fault to spend time and effort. In general, this time or effort is best modeled as a random variable. Once a fault is detected, the system needs to initiate appropriate recovery actions. The basic nature of this response would be to try to make the system move back to a normal state from a failure state. This movement requires time or effort on the system. As before, this time or effort is best modeled as a random variable that is described by a suitable probability distribution function. The system's response to a fault may be described by the states and transitions between these states. In order to analyze the survivability attributes of a network system, we need to consider the actions undertaken by a fault as well as the system's response to a fault. The transient period of our interest is assumed to evolve as a continuous-time stochastic process {X(τ ) : τ ≥ 0}. The state X of the n-subnetworks at any time τ can be completely described by the collection of the state of each subnetwork. That is, a n-dimensional vector

X(τ ) = (X 1 (τ ), X 2 (τ ), • • • , X n (τ )), τ ≥ 0, (1)
where for each subnetwork X l (τ ) = p (l is discrete; l = 1, • • • , n) represents the state that a permanent hardware failure has occurred on the l-th subnetwork at time τ , X l (τ ) = o in the case when the l-th subnetwork works normally at time τ , and X l (τ ) = r if the l-th subnetwork has been repaired at time τ . Here, it is assumed that the service in state r restores to the same value as in normal state o.

The propagation is assumed to have 'memoryless' property: the probability of disastrous events spreading from one given subnetwork to another depends only on the current system state but not on the history of the system. The affected subnetwork can be repaired in a random period. Moreover, all the times of the disaster propagation and repair are exponentially distributed.

With the above assumptions, the transient process X(τ ) can be mathematically modeled as a continuous-time Markov chain (CTMC) with state space

Ω = {(X 1 , X 2 , • • • , X n ) : X 1 , X 2 , • • • , X n ∈ {p, o, r}}. The transition rate ma- trix of X(τ ) is Q.
In brief, the following summarizes the model:

the state of each subnetwork at time t lies within the set {p, o, r}, -at the initial time t = 0, a disastrous event hits the 1-st subnetwork, which changes the system state to (p, o, • • • , o), -the disaster propagates from the subnetwork l (l is discrete; l = 1, • • • , n) to subnetwork l + 1 according to Poisson processes with rate λ p(l+1) , -a disastrous event can occur on only one subnetwork at a time, -each subnetwork has a specific repair process which is all at once and the repair time of subnetwork l is exponentially distributed with mean 1/µ pl , -subnetworks with permanent failure are not repaired before all subnetworks are affected by the disaster, -the propagation or repair transition is determined only by the current state, not on the path until reaching the current state.

Table 1. Transition generation rules for Q

Condition Q ab a→b Propagation phases: ′ r ′ ∈ a&& ′ r ′ ∈ b, a[0] = b[0] = ′ p ′ λp2 (p, o, • • • , o) → (p, p, o, • • • , o) . . . . . . λpn (p, • • • , p, o) → (p, • • • , p) Repair phases: f (b) = f (a) + 1, a[i] = b[j] = ′ r ′ , µpj i, j ∈ 1 • • • n, j = i *Note: 1. f is the function to return the number of 'r' in the state; 2. state (r, • • • , r) = (o, • • • , o).
Our previous work [START_REF] Lang | Modelling and Analysis of the Survivability of Telecommunication Network[END_REF] has provided a 3-subnetwork example in Section 2.1.

Here we make a further step in constructing a general model for a network with n subnetworks. We consider the transition from one certain state a to b with rate Q ab , where the state is represented as a vector as the form in Eq. (1). To distinguish the states in repair phases, we use a function f to counter the number of ′ r ′ in the state. Table . 1 summarises the rules in constructing the infinitesimal generation matrix of model I for a network with a general number of subnetworks n (n > 0; n is discrete).

Model II: Transient failures

Transient failure is a brief malfunction that often occurs at irregular and unpredictable times, which has in most systems a significant impact on the reliability and survivability. Some examples of transient failures are electromagnetic interference and radiation, noise on a transmission line and alpha-particles passing through RAM flipping bits. The restoration after a transient failure does not require manual maintenance and repair, it is often the case that the automatic reboot fix the problem. As an important type of failure, transient failure is largely overlooked in network survivability modeling. In the following, we will integrate the impact of transient failures into the system model.

It is necessary to distinguish between permanent and transient failures. We add a new value to the state space, that is, X l (t) = t represents the state that a transient failure has occurred on the l-th subnetwork at time τ . The following summarizes the increased model assumptions:

the state of each subnetwork at time τ lies within the set {p, t, o, r}, -the disaster propagates from the subnetwork l (l is discrete; l = 1, • • • , n) to subnetwork l + 1 according to Poisson processes with rate λ p(l+1) , -transient failures occur according to a Poisson process of intensity λ t , -the restoration of a transient failure does not require manual repair, it is assumed that the automatic reboot (with mean rate µ t ) fix the problem, which implies a shorter repair/restoration time, i.e., µ t > µ p , -each subnetwork has a specific repair process which is all at once and the repair time of subnetwork l is exponentially distributed with mean 1/µ pl , -a subnetwork with a permanent failure cannot fail due to transient failures, -a subnetwork with a transient failure can fail due to a permanent failure, -when a subnetwork is repaired both permanent and transient failures are removed. 3. This diagram is an extension of the model I example which has been presented in [START_REF] Lang | Modelling and Analysis of the Survivability of Telecommunication Network[END_REF] On state (p, p, p), the CTMC may jump to three possible states: firstly, it may jump to state (p, p, r) if the subnetwork-3 is recovered (this occurs with rate µ p3 ); secondly, it may jump to state (r, p, p) if the subnetwork-1 is recovered (this occurs with rate µ p1 ); and thirdly, the CTMC may jump to state (p, r, p) if the subnetwork-2 is recovered (this occurs with rate µ p2 ).

It should be observed that the frequency of the initial event is not considered in the survivability model because the focus is: given that an undesired event has occurred what is the nature of performance degradation just after such event until the system stabilizes again. This is indicated by the dashed line in Fig. 3. Section 3 will discuss the use of the Markov model and transient probabilities to arrive at the transient suvivability model analysis.

Model Analysis

In this section we discuss and derive survivability attributes based on the Markov models presented in the previous section. It was explained earlier that to carry out the survivability quantification analysis, we need to analyze the Markov model of the system that was described by its state transition diagram. In order to compute survivability measure, we need to first compute the transient probabilities of the model states.

Let

π(τ ) = [π (p,o,••• ,o) (τ ) • • • π (o,o,••• ,o) (τ )
] denote a row vector of transient state probabilities at time τ . In order to calculate π(τ ), the Kolmogorov-forward equation expressed in the matrix form should be satisfied as follows:

dπ(τ ) dτ = π(τ )Q, ( 2
)
where Q is the transition rate matrix. Then the transient state probability vector can be obtained as follows:

π(τ ) = π(0)e Qτ , (3)
where e Qτ is defined as follows:

e Qτ = ∞ i=0 Q i τ i i! . (4)
The simplest method to compute Eq. ( 4) is to truncate the summation to a large number (e.g., K), which can be expressed as follows:

e Qτ = K i=0 Q i τ i i! . (5)
The other common alternative methods to obtain the transient probability vector π(τ ) include uniformization [START_REF] Jensen | Markoff chains as an aid in the study of Markoff processes[END_REF], matrix exponential approach [START_REF] Trivedi | Probability and Statistics with Reliability[END_REF]. Here we take uniformization approach as the model analysis example. Let q ii be the diagnoal element of Q and I be the unit matrix, then the transient state probability vector is obtained as follows:

π(τ ) = π(0) ∞ i=0 e -βτ (βτ ) i i! P i , (6)
where β ≥ max i |q ii | is the uniform rate parameter and P = I + Q/β. Truncate the summation to a large number (e.g., K), the controllable error ǫ can be computed from

ǫ = 1 -e -βτ K i=0 (βτ ) i i! . ( 7
)
Whenever the system is in state i ∈ Ω, a reward is assigned at a rate Υ (i), where Υ denotes a reward function. Since Υ i is the reward rate associated with state i, and so Υ i can take any of the |Ω| values. The vector of reward rates associated with the state is expressed as

Υ = [Υ 1 , Υ 2 , ..., Υ |Ω| ].
Here, the reward rate can be many types, such as economic return vector or cost vector in business continuity preparedness planning.

We currently equate survivability performance with connectivity, the percentage of users connected successfully. Based on the above calculated transient probabilities, the measure of interest is obtained as reward measures from the CTMC model. Then, the expected instantaneous reward rate E[Υ X(τ ) ] gives the average connectivity of the system at time t, which is expressed as follows:

E[Υ X(τ ) ] = Υ • π T (τ ). ( 8
)
As stated in Section 2 complete description of this Markov model requires the knowledge of various model parameters. Clearly for the model to be accurate, it is important to estimate the model parameters accurately. In this paper, our focus is more on developing a methodology for analyzing quantitatively the survivability attributes of a network rather than model parameterization.

Numerical Example

In this section, we perform numerical experiments for the case study in Section 2.1. First, we apply and compare model I and model II in this network example for different values of fault propagation rates. Then we study the impact of differents repair rates on model II's performance.

For the parameters setting of the proposed models, we refer to the data from Japan 2011 earthquake situation report [START_REF] Adachi | The restoration of telecom power damages by the Great East Japan Earthquake[END_REF]. In doing so, our model parameters fall in ranges which represent the typical real system's behavior. Our experimental setup consists of three subnetworks and the disaster occurs at subnetwork-1 initially. We set the transition rates as follows: λ p2 = λ p3 = 0.67, λ t = 50, µ t = 100, µ p1 = µ p2 = µ p3 = 0.097, given in units of events per day. For simplicity, the average number of users per each base station is assumed to be the same. Then the percentage of connected users is equal to the fraction of available base stations. The rewards at each model state are shown in Table 2. First, we compare model I and model II in this network example for different values of fault propagation rates. In fig. 4, when λ p2 = λ p3 = 0.67, there is a gap between model I and model II curves. Compared to model I, the fraction of active users in model II decreases more sharply. On the other hand, as expected, when fault propagation rates increase, i.e., λ p2 = λ p3 = 1.8, then model I and model II curves are close to each other. The impact of transient failure and repair is not as evident as in former case.

Then we study the impact of different repair rates on model II's performance. We vary the transient and permanent failure repair rate values, and the results are summarized in Fig. 5. Consider the scenario in which the permanent failure repair rate is low (µ p1 = µ p2 = µ p3 = 0.3). In this scenario, the fraction of active users is low (roughly 0.3, 2 hours after the failure when µ t = 10). However, when the permanent failure repair rates are relatively higher (µ p1 = µ p2 = µ p3 = 3), the fraction of active users sharply increases. In both figures, the effect of the transient failure repair rate is not as evident for longer observation time (after 8 hours). As shown in 5(b), the value of transient failure repair rate µ t which makes the fraction of active users achieve 60% in two days is µ t > 100.

Conclusions and Future Work

In this paper we have presented an approach for quantitative assessment of network survivability against fault propagation. First, we considered the case where physical fault propagation is considered. Second, we considered the case in which both physical and transient fault are incorporated. The impact of different parameters, such as fault propagation rates, repair rates were studied. Users can choose different models depending on the real cases. For example, if both physical and transient faults occurred, model II is more appropriate; otherwise, model I is enough for the requirement. The main goal of this paper is to construct the models, rather than model parameterization.

One of the goals of our future work is to collect more real data. This information should provide us with a better understanding of the behavior exhibited by faults, help us to refine its stochastic description and lead to better estimates of the model parameters. Another goal of our future work is to consider geographic factors. We will extend the system state by adding more dimensions representing geographical characterizations.

Fig. 1 .

 1 Fig. 1. Comparison of fault propagation and error propagation

Fig. 3 .

 3 Fig. 3. A state transition diagram for model II

8 Fig. 4 . 3 Fig. 5 .

 8435 Fig. 4. Comparison of the fraction of connected users in model I and II for different values of fault propagation rates

  . Given the initial state is (p, o, o), the CTMC may jump to state (p, p, o) if the propagation occurs with rate λ p2 ; or it may jump to state (p, t, o) or (p, o, t) with rate λ t due to transient failures. Time to restart to fix the transient failures is assumed to be exponentially distributed with rate µ t . Similarily, on state (p, p, o), the CTMC may jump to state (p, p, p) if the propagation continues with rate λ p3 ; or it may jump to state (p, p, t) with rate λ t for transient failures. As for the other transition structures, model II is the same with model I.

Table 2 .

 2 Rewards: fraction of available base stations

	Parameter Value Parameter Value
	Υ1	0.560	Υ8	0.871
	Υ2	0.429	Υ9	0.611
	Υ3	0.040	Υ10	1.000
	Υ4	0.429	Υ11	0.430
	Υ5	0.483	Υ12	0.130
	Υ6	0.169	Υ13	0.040
	Υ7	0.560	Υ14	0.040


Péter Megyesi
email: megyesi@tmit.bme.hu

Sándor Molnár
email: molnar@tmit.bme.hu

Analysis of Elephant Users in Broadband Network Traffic

Keywords: traffic measurement, traffic analysis, elephant flows, elephant users

Elephant and mice phenomena of network traffic flows have been an interesting research area in the past decade. Several operational broadband measurement results showed that the majority of the traffic is caused by a small percentage of large flows, called the elephants. In this paper, we investigate the same phenomenon in regards of users. Our results show that even though the packet level statistics of elephant users and elephant flows show similar characteristics, there is only a small overlap between the two phenomena.

Introduction

Traffic profiling is a crucial objective for network monitoring and management purposes. Flow characterization has been given a large attention by the research community in the past decade. Flows has been classified by their size of traffic (as elephant and mice) [START_REF] Thompson | Wide Area Internet Traffic Patterns and Characteristics[END_REF] [2] [START_REF] Estan | New directions in traffic measurement and accounting: Focusing on the elephants, ignoring the mice[END_REF], by their duration in time (as tortoise and dragonfly) [START_REF] Brownlee | Understanding Internet traffic streams: dragonflies and tortoises[END_REF], by their rate (as cheetah and snail ) [START_REF] Lan | A measurement study of correlations of Internet flow characteristics[END_REF] and by their burstiness (as porcupine and stingray) [START_REF] Lan | A measurement study of correlations of Internet flow characteristics[END_REF]. Several studies were written about the correlation between these flow behaviors [START_REF] Markovich | Bivariate statistical analysis of TCP-flow sizes anddurations[END_REF] [START_REF] Molnár | Three-Dimensional Characterization of Internet Flows[END_REF].

However, current literature lacks in profiling users in such regards. In this paper we investigate the elephant and mice phenomena regarding Internet users. We analyzed two recent measurements taken from high speed operational networks and found that elephant users show similar packet level characteristics to elephant flows. We also determined that there is a much smaller overlap between these two phenomena that one would expect. We found that only a small portion (10%-30%) of elephant flows are generated by elephant users and also the generation of elephant flows is not a necessary condition for being an elephant user. These results indicate that further investigation of user characterization could aid network operators in the future to apply different services or charging policies for different users.

The contribution of this paper is threefold. First, to our knowledge, our study is the first that presents the discussed characteristics of elephant users. Second, we point out that there is only a small overlap between elephant flows and elephant users. Finally, our measurements from recent networks show that the elephant and mice phenomena of flows and users are still present in todays networks.

This paper is organized as follows. Section 2 presents the related work. In Section 3 we give the definition of elephants and the properties of the two datasets we used for our research. Section 4 presents the results of our measurements. Finally, in Section 5 we conclude our work.

Related Work

There are several different definitions for elephant flows in the literature. In [START_REF] Papagiannaki | A pragmatic definition of elephants in internet backbone traffic[END_REF] authors propose two techniques to identify elephants. The first approach is based on the heavy-tail nature of the flow bandwidth distribution, and one can consider a flow as an elephant if it is located in this tail. The second approach is more simple, elephants are the smallest set of flows whose total traffic exceeds a given threshold. Estan and Varghese [START_REF] Estan | New directions in traffic measurement and accounting: Focusing on the elephants, ignoring the mice[END_REF] used a different definition. They considered a flow as an elephant if its rate exceeds the 1% of the link utilization.

However, the definition given by Lan and Heidemann [START_REF] Lan | A measurement study of correlations of Internet flow characteristics[END_REF] become a rule of thumb in later literature (e.g. both [START_REF] Molnár | Three-Dimensional Characterization of Internet Flows[END_REF] and [START_REF] Callado | A Survey on Internet Traffic Identification[END_REF] use this definition). They define elephant flows as flows with a size larger than the average plus three times the standard deviation of all flows. They use the same idea for categorize flows by their duration, rate and burstiness as tortoise, cheetah and porcupine, respectively. [START_REF] Lan | A measurement study of correlations of Internet flow characteristics[END_REF] was also the first study that presented the cheetah and snail and the porcupine and stingray classifications. Tortoise and dragonfly properties of traffic flows were first investigated in [START_REF] Brownlee | Understanding Internet traffic streams: dragonflies and tortoises[END_REF]. Here, the authors considered a flow as tortoise simply if its duration was lager than 15 minutes. Given the generality and the rule of thumb nature of the definition by Lan and Heidemann [START_REF] Lan | A measurement study of correlations of Internet flow characteristics[END_REF] we will use the same definition for elephants later in this paper.

In [START_REF] Sarvotham | Connection-level analysis and modeling of network traffic[END_REF] Sarvotham et al. present a comprehensive study that traffic bursts are usually caused by only few number of high bandwidth connections. They separate the aggregated traffic into two components, alpha and beta by their rate in every 500ms time window. If the rate of the flow is greater than a given threshold (mean plus three standard deviations) than the traffic is alpha, otherwise it is beta. Authors determine that while the alpha component is responsible for the traffic bursts, the beta component has similar second order characteristics to the original aggregate.

The term elephant user appears in [START_REF] Liu | Model of Network Traffic Based on Network Applications and Network Users[END_REF] where the authors calculate the Gini coefficient for the user distribution. The Gini coefficient is usually used in economics for measuring statistical dispersion of a distribution. They calculate the value of the Gini coefficient for the distribution of the number of bytes generated by the users as 0.7895 but no further discussion is presented.

In [START_REF] Pietrzyk | On profiling residential customers[END_REF] authors investigate application penetration in residential broadband traffic. They calculate the results separately for the top 10 heavy-hitters (the top 10 users that generated the most traffic) in their measurement data. Besides pointing out the fact that the majority of the data is generated by a small group of users the paper does not tackle any further issues about elephant users.

Methodology

In this section we present the source of the two network traces we used in this study. We also give the definition of elephants and the metrics we used to analyze them.

Datasets

The first trace was measured by the The Cooperative Association for Internet Data Analysis (CAIDA) [START_REF]The Cooperative Association for Internet Data Analysis[END_REF] in a 10 Gbit/s backbone link between Chicago and San Jose. They periodically take measurements on this link and make them available for the research community upon request in an anonymous format (removed payload and hashed IP addresses). We analyzed multiple subsets of these data and since we found similar result we chose one given time period to present our findings. This trace was recorded on 13:15 (UTC), 20th of December 2012 and contains four minutes of network traffic. Furthermore, we refer to this measurement as CAIDA Trace.

The second measurement was taken in the campus network of the Budapest University of Technology and Economics (BME) on 16:31 (CET), 18th of December 2012 and contains six minutes of traffic. The measured link was a 10Gigabit Ethernet port of a Cisco 6500 Layer-3 switch which transfers the traffic of two buildings on the campus site to the core layer of the university network. This measurement is not available to the public. However, we consider the results relevant to present since our findings are similar to the CAIDA Trace even though the nature of network is different. We refer to this measurement as BME Trace.

Table 1 presents the basic statistics of the two traces. Generally, the CAIDA Trace contains more data than the BME Trace by one order of magnitude.

Measuring Elephants

During the identification of elephant users and flows we use the definition presented in [START_REF] Lan | A measurement study of correlations of Internet flow characteristics[END_REF]: a user or a flow is considered an elephant if its flow size or traffic volume is grater than the average plus three times the standard deviation of all the flow sizes or traffic volumes of flows and users, respectively. Table 1 presents the values of these threshold for the two traces. The elephant and mice phenomena clearly exist: less than a thousandth of the users and flows are responsible for roughly 60%-80% of the total traffic.

In the next section we firstly show that the elephant phenomenon also exist with different threshold levels by plotting the cumulative distribution of user and flow sizes against theirs cumulative proportion of the total traffic. Furthermore, we present the comparison of the following three packet level metrics, (1) byte and packet throughput, (2) packet size distribution and (3) inter packet time distribution. We chose these metrics because they are the most frequently used packet level characteristics for comparing traffic traces [START_REF] Molnár | How to Validate Traffic Generators?[END_REF]. Additionally, we investigate presence of both elephant and non-elephant flows in the traffic of elephant users. 4 Measurement Results

User and Flow Sizes

In Figure 1 one can investigate the elephant and mice phenomena for both traces.

Here we plotted the cumulative distribution of user traffic volumes and flow sizes against theirs cumulative proportion of the total traffic. In Table 2 we collected the complementary values in percentage (1 minus the actual value) of the curves in Figure 1 for different thresholds. Ratio presents the proportion of users and flows whose traffic was larger than the Threshold value and Traffic represents their total share from the aggregated traffic.

Byte and Packet Throughput

In Figure 2 the traffic of elephant users and elephant flows are plotted against the original traffic. The relative difference are also presented. In case of the BME Trace the elephants are responsible for sufficient amount of the total traffic (80%-85%), while in the CAIDA Trace this ration is a bit smaller (60%-70%). Since the traffic of elephants seems to follow the bursts in the original traffic (the relative differences are also smaller at these peaks), the results suggests that elephant users are main cause for traffic burstiness. Figure 3 present the number of packets in every one second time interval. Here, the relative difference is much higher than in case of the byte throughput. In the CAIDA Trace elephants are responsible for only roughly 30%-40% of the total packets, while in case of the BME Trace this number is ratio is 50%-70%. Intensity of elephants are also following the packet burst of the original aggreagte since the relative difference is smaller in traffic peaks.

Packet Sizes

Packet size distributions of the two measurements is given in Figure 4. The joint property in both traces is that ratio of maximum and minimum sized packets is larger in elephants than in the original aggregate. Packets with intermediate size share similar proportion. We collected a few numerical example to Table 3 to present this phenomenon. Table 4 present the ratio of number of packet in elephants compared to the number in the original aggregate under different conditions. It is clear from the values that elephants contains the majority of maximum sized packet and elephant flows exclude the majority of minimum sized packets. The ratio of minimum sized packets in elephant users shows different behavoir in the two measurements.

Inter Packet Times

Inter arrival time between consecutive packets corresponding the elephant users or flows are presented in Figure 5. The curves show similar characteristics for elephant users and elephant flows. The cdf curves of elephants are increasing slower than the original aggregate's which is an expected behavior since traffic of elephants are the rarefaction of the original packet stream. In Figure 6 every dot represents an elephant user according to the generated number of elephant flows and mice flows. These results indicate that there is no correlation between the number of elephant flows and mice flows generated by an elephant users. Furthermore, a user can be an elephant without generating any elephant flows. There was 53 elephant users in the CAIDA Trace who did not generated any elephant flow. They account for 8% of all elephant users in the CAIDA Trace. In the BME Trace this number is only 3, but since there were only 56 elephant users in that measurement their share is 5%. Another interesting result is that in case of the CAIDA Trace only the 9.13% of elephant flows were generated by elephant users. In case of the BME Trace this value is higher, namely 37.85%. These result clearly indicate that the overlap between the elephant user and elephant flow phenomenons could be much smaller in some cases that one would expect.

Conclusion

In this paper we investigated the elephant and mice phenomena of Internet users in recent broadband network measurements. We found that elephant users show similar packet-level characteristics to the well-investigated elephant flow phenomenon. However, we pointed out that only a small portion (10%-30%) of elephant flows were generated by elephant users. We also found that the generation of elephant flows by a user is not a necessary condition for being an elephant user.

As future work we would like to further analyze the elephant user phenomenon in the same way that elephant flows were analyzed in [START_REF] Lan | A measurement study of correlations of Internet flow characteristics[END_REF] [START_REF] Sarvotham | Connection-level analysis and modeling of network traffic[END_REF]. Such study would aid us in the understanding of how particular users are affecting the second-order characteristics of network traffic.

Fig. 1 :

 1 Fig. 1: The elephant and mice phenomena presented by cumulative distribution of user traffic volume and flow sizes and their cumulative proportion of the total traffic

Fig. 3 :

 3 Fig. 2: Traffic of elephants

Fig. 4 :

 4 Fig. 4: Packet size distributions of elephants

Fig. 5 :

 5 Fig. 5: Inter Packet Time distributions of elephants

Fig. 6 :

 6 Fig. 6: The number of elephant and non-elephant flows generated by elephant users

Table 1 :

 1 Statistics of the two traces used for analysis

		CAIDA Trace	BME Trace
	Number of packets	105444780	6804958
	Number of users	680300	63668
	Number of flows	3876982	264117
	Total traffic	65.6 Gbyte	5.66 Gbyte
	Elephant user threshold	15.9 Mbyte	13.7 Mbyte
	Number of elephant users	661	56
	Proportion of elephant users	0.097%	0.088%
	Total traffic of elephant users	71.5%	84.5%
	Elephant flow threshold	2.3 Mbyte	4.96 Mbyte
	Number of elephant flows	2714	151
	Proportion of elephant flows	0.07%	0.057%
	Total traffic of elephant flows	61.7%	83.41%

Table 2 :

 2 Proportion of elephants with different thresholds

		CAIDA Trace	BME Trace
	Threshold in Mbyte	Users	Flows	Users	Flows
		Ratio Traffic Ratio Traffic Ratio Traffic Ratio Traffic
	0.1	2.17% 95.48% 1.21% 85.29% 1.21% 98.75% 0.53% 94.84%
	0.5	0.8% 92.44% 0.29% 74.21% 0.53% 96.97% 0.16% 91.08%
	1	0.54% 90.55% 0.18% 69.56% 0.37% 95.66% 0.11% 89.46%
	2	0.37% 88.17% 0.11% 63.71% 0.23% 93.45% 0.08% 87.04%
	5	0.23% 83.48% 0.04% 52.03% 0.14% 89.96% 0.06% 83.23%
	10	0.13% 76.92% 0.02% 42.87% 0.1% 86.35% 0.03% 73.56%
	15	0.1% 72.2% 0.017% 37.25% 0.08% 83.96% 0.025% 70.65%
	20	0.08% 68.78% 0.011% 32.09% 0.06% 80.91% 0.02% 66.67%
	50	0.03% 53.55% 0.003% 17.88% 0.03% 68.12% 0.007% 47.93%

Table 3 :

 3 Packet proportions under different conditions

		CAIDA Trace	BME Trace
	Condition	Original	Elephant	Elephant	Original	Elephant	Elephant
		Aggregate	Users	Flows	Aggregate	Users	Flows
	PS <= 54 Byte	18.9%	11.9%	7.4%	20.9%	21.0%	2.9%
	PS <= 66 Byte	44.3%	16.7%	9.9%	30.1%	29.4%	3.3%
	PS >= 1450 Byte 32.8%	66.3%	72.8%	44.8%	54.6%	79.1%
	PS = 1514 Byte	27.6%	54.2%	61.4%	28.5%	33.9%	49.7%

Table 4 :

 4 Ratio of number of packets in elephants compared to the original

		CAIDA Trace	BME Trace
	Condition	Elephant	Elephant	Elephant	Elephant
		Users	Flows	Users	Flows
	PS <= 54 Byte	25.0%	12.3%	74.7%	6.8%
	PS <= 66 Byte	15.0%	7.0%	71.0%	5.3%
	PS >= 1450 Byte 80.6%	70.2%	90.2%	88.6%
	PS = 1514 Byte 81.2%	70.3%	88.4%	87.8%

Acknowledgments. The authors would like to thank CAIDA for granting access to the measurement data that was analyzed in this paper. The research was supported by OTKA-KTIA grant CNK77802.