Recent advances in Next Generation Networks envision the
1 Traf?c Engineering of Tunnel-based Networks having Class Speci?c Diversity Requirements
Shekhar Srivastava and Deep Medhi
Computer Science&Electrical Engineering Department
School of Computing and Engineering
University of Missouri-Kansas City
Kansas City,MO64110
Abstract—Tunnel-based networks such as Multi-protocol La-bel switching(MPLS)are suitable for providing diversity guar-antees to different service classes or customers.Based on the number of active tunnels to handle,router capabilities can be taxed due to the limited amount of memory and/or processing power of these routers.In this paper,we present a mixed-integer linear program formulation for a traf?c engineering problem where such tunnel restriction are taken into account in addition to standard capacity constraints while addressing diversity requirement of services.Due to large size of the formulation,we also present an accompanied solution approach based on Lagrangian relaxation and sub-gradient optimization. We then present results towards impact of diversity constraint upon the tunneling and capacity restrictions.We observed that the networks having higher amounts of capacity and demands with higher level of survivability are much more sensitive to number of allowed tunnels in the network.The impact is even more prominent for sparsely-connected,large-sized networks. Index Terms—Diversity Constraint,Tunnel-based Networks, Optimization formulation,Lagrangian Decomposition Algorithm.
I.I NTRODUCTION
Recent advances in Next Generation Networks envision the presence of service class based protection along with the tradi-tional Quality-of-Service approaches(end-to-end delay and/or jitter).Such developments are fueled by the requirement of guaranteed protection for many critical and recently introduced applications.
Observe that such mechanisms would come at a premium in terms of cost and complexity.This is due to extra provisioning and signalling required to support many of these mechanisms such as p-cycles[15],fast reroute[7],or backup path[14] (see[12]for a detailed survey).However,many not-so-critical applications would not be worth/willing to pay the extra cost and could do without such detailed/complex mechanism.Ap-plications that can tolerate delays and degraded performance but are extremely vulnerable to‘total loss of connection’fall into this category.Therefore,they need a different kind of protection which should be simple,should not require complex signalling/allocation mechanisms and should ensure that single link failures do not lead to total loss of connection.Such a simple-yet-effective protection can be provided by‘diversity constraint’.Diversity constraint([4],[8]and[16])ensures that Corresponding author:dmedhi@https://www.wendangku.net/doc/8c6786800.html, demands are alloacted such that individual links/nodes carry less than a speci?ed fraction()of any demand.This ensures that in the event of link/node failures,at least(1-)fraction of the total demand is survived.This averts the possibility of total loss of connection for these applications in the event of link or node failures.
Such a restriction can be enforced if the network has the capability to do so.For this purpose,we consider a tunnel-based network such as MPLS(multi-protocol label switching) network.Other tunnel-based networks include ATM(Asyn-chronous Transfer Mode),WDM(wavelength division multi-plexing)based optical networks,etc.
For MPLS networks,multiple label switched path(LSP) tunnels could be set up between source and destination nodes; allocation to these tunnels could be such that individual links/nodes do not carry more than fraction of a demand.It is obvious that having such a restriction would not require any complex reallocation or recon?guration procedures but would drastically increase the active number of tunnels in a network. This could lead to a limitation for MPLS networks[1].That is because each LSP tunnel setup would require additional pro-cessing power and memory at the router interfaces(discussed further in Section II).
Therefore,our interest here is to consider traf?c engineering of a network with multiple service classes,each having a pre-determined diversity requirement,and consider any restriction on number of tunnels imposed by the processing power and memory requirements of the LSRs.While we use MPLS and LSPs to explain the problem,the model is applicable to other tunnel-based networks as well.
A.Contributions of the Paper
We start with presenting our approach towards capturing the restriction of processing power and memeory requirements of the LSRs.We determined that they translate into number of active LSP tunnels on a link referred to as tunneling restriction. Furthermore,we present a mathematical formulation which incorporates tunneling,capacity and diversity constraint in an integrated mixed integer linear program.The formulation neatly enforces the tunneling constraint by introducing a tunnel activity variable.Diversity constraint is introduced as a bound on the?ow variables.We also extend the basic model to introduce a tunnel cost.The formulation was found to
2
be having large number of binary variables and constraints, which makes the formulation hard to solve for large sized networks.Hence we also present a solution approach based on Lagrangian relaxation and subgradient optimization This resulted in solving smaller sub-problems in an iterative fashion and then constructing the?nal solution.One of the sub-problems was of integer linear in nature.We also present a proof that showed that the continuous relaxation of the sub-problem had an optimal binary solution which can be obtained by using the Simplex algorithm.Our work here extends work presented in[13]in multiple ways:the model presented incorporates diversity as well as extended cost model,and our computational results consider various factors and parameters in a systematic manner.
Using the solution technique,we study the interplay be-tween capacity,tunneling and diversity constraints.It was ob-served that minor relaxations in the survivability requirement of demands translates into much fewer values of required tunnels to achieve similar performance.We also observed that the networks having higher amounts of capacity and demands with higher level of survivability are much more sensitive to number of allowed tunnels in the network.The impact is even more prominent for sparsely-connected,large-sized networks. The problem of minimising the required label space was discussed by Applegate and Thorup in[1].They evaluated the number of required labels for each LSR in order to suc-cessfully embed any given optimal solution.This is achieved by using“to trees”and they present a construction and an accompanied proof to show that such an allocation is possible for any given optimal allocation.The approach is interesting and gives a lower bound towards the design speci?cation for to-be-installed LSRs.We,however take a different view point.How can the capability of routers(in terms of the tunnels/labels that they can support)be embeded in a traf?c engineering formulation and what is its impact?We assert that such a view point is more practical.This is for two reasons. First is that most traf?c engineers are given LSRs connected by links and projected demands and asked to determine routing.The possibility of being able to enforce/upgarde the capabilities of the routers in the network might not be a viable option.Secondly,MPLS networks could be comprised of wide variety of LSRs ranging from slow/less capable legacy LSRs to fast/very capable,recently installed LSRs.Enforcing the same capability in terms of storage memory and processing power could require discarding of many otherwise-useable LSRs. The rest of the papar is organized as follows.In Section II, we study the details of processing and memory requirements for an LSR to support large number of tunnels.In Section III, we present the traf?c engineering formulation.In Section IV, we present the solution approach based on a decomposition algorithm to solve the formulation.In Section V,we present results for demonstrating the interplay between capacity,tun-neling and diversity constraints.We conclude in Section VI
II.C ONSTRUCTING T UNNEL C ONSTRAINT
In this section,we discuss the functional details of an LSR in order to isolate the operations which could become a bottle-neck in its functioning,in the event of overwhelming number of tunnels being setup in the network.
An edge LSR does four fundamental operations in an MPLS network.First operation is the computation of the best path that a packet should take through the network to its destination.This computation could incorporate various policies and network constraints.The operation is performed on regular intervals by the route processor and the frequency of operation is con?gured by the service provider.
The second operation is performed when a new orignat-ing/terminating/passing LSP is being set up or an older origi-nating/terminating/passing LSP is being re-provisioned.Set-up of LSP requires activation of label distribution protocol(LDP) which appends a label in the label forwarding information base (LFIB)of each incoming interface of the intermediate LSRs of the LSP.The route chosen by the LSP is determined by the best path computed during the?rst operation.
Third operation is performed for each and every incoming packet on an https://www.wendangku.net/doc/8c6786800.html,bel values are extracted from the label?eld found in the incoming packet on an interface and used as an index in the LFIB.After a match is found,the interface replaces the label in the packet with the outgoing label from the subentry and sends the packet over the speci?ed outgoing interface to the next hop speci?ed by the subentry.In case the node happens to be the destination of the packet(or the corresponding LSP),the label is removed and the packet is sent to the local interface.
The fourth function corresponds to the actual transmission of the packet over the physical link on the interface determined by the subentry towards the next hop.In case the transmission channel is busy,the packet is placed in the speci?ed queue and transmitted in the order of its arrival or any scheduling mechanism followed by the outgoing interface.Although an LSR could be involved in many other operations and functions, we assume that these four operations as most impactful funtions towards the consumption of the processing power and memory requirements of an interface of the LSR. Observe that the?rst operation is independent of the number of tunnels set up in the MPLS network.If we assume that the traf?c does not vary too much over medium to large time scales,then second operation of con?guring/recon?guring LSPs would not cause major concerns in terms of overload. However,the interface card needs to have suf?cient memory to store all the required entries of the labels for each incoming LSP.Observe that the size of LFIB increases linearly with the increasing number of incoming LSPs on the interface.The fourth operation is impacted by the amount of allocated traf?c and available bandwdith on the out going link and is mostly referred to as capacity constraint in the literature([11],[17]). However,third operation is performed for every incoming packet on the interface of a LSR.The processing power at each interface should be enough to successfully determine the output interface and label of each incoming packet in an acceptable time.Observe that the time required to?nd the entry(lookup operation)for each packet increases with larger size of the LFIB.Therefore,the processing requirement at an interface of a LSR increases with the number of active LSPs passing through the interface.
3
In conclusion,for tunnel-based networks,such as MPLS, number of tunnels incoming on an interface determine the memory and processing requirements of the interface.Hence restricting the active number of tunnels on an interface would avoid overloading the LSRs.This restriction is equivalent to restricting the number of tunnels passing through the link con-nected to the interface assuming that the interfaces connected to the link have the same capailities.For links connected to interfaces having different capabilities(connecting slow and fast routers),we determine the tunnel restriction based on the slower/less capable router.We refer to the approach of restricting the active number of tunnels on a link as tunneling restriction/constraint.
III.T RAFFIC E NGINEERING F ORMULATION
In this section,we present an integrated traf?c engineering formulation which incorporates capacity,tunnel and diversity restrictions.Capacity restriction is incorporated by ensuring that the?ow on any link is less than the capacity of the link.Tunnel constraint is honored by enforcing that the active number of tunnels on a link are resticted.Diversity constraint restricts the fraction of demand that can be allocated to any one tunnel.
We consider an aggregated-?ow based network,where traf-?c data(packets)arriving to a source,for a speci?c destination needs to be sent over one of the active tunnels between the source and the destination.The data volume is estimated using either service level agreement based approaches[11]or using measurement based concrete measures[17].Other techniques could also be used(see[9],and references there in).We assume that information is available regarding data volume for each service class of all the demands.We also assume that tunnels are not shared between the service classes.Each service class maintains its own set of tunnels between source and destinations.We?rst describe the notation:
:Set of nodes in the Network
:Set of nodegroups with traf?c
:Set of links
:Capacity of link
:Set of service classes at nodegroup
:Maximum number of tunnels allowed on link
:Revenue from carrying unit demand volume of service class and nodegroup
:Traf?c demand for service class and nodepair
:Minimum value of?ow on any path
:Maximum fraction of?ow for service class and nodepair allowed on any path
We are given the following information:,,,,, ,,,and.For demand connecting a pair of ingress and egress nodes,due to the capacity,diversity and tunnel limitation,it is clear that just considering the shortest path is too limiting and does not address the overall traf?c engineering problem.Hence we initially generate a set of candidate paths for each service class and demand pair.We use a k-shortest path algorithm to generate the set of paths ()for each service class of each demand.A.Basic Model
Let be the number of candidate paths generated for service class of demand.We now introduce the fractional?ow variable associated with the path for service class of request which takes a value between0and1as the fraction of demand allocated to path.
1)Demand Constraint:As discussed earlier,due to capac-ity,tunnel and diversity limitations,it is quite possible that a demand may not be routed(while proper network design would try to avoid such situations by over-engineering;from a traf?c engineering modeling standpoint,it is necessary to incorporate this variable to avoid infeasibility of the problem). To consider this aspect,we have the following constraint
(1a)
2)Diversity Constraint:In order to incorporate the diver-sity constraint,we need to restrict the fraction of the total demand which can be allocated to a tunnel.Therefore,we have to put an upper-bound on the fractional?ow variable. Such a bound would suf?ce to introduce diversity constraint. We consider as the diversity restriction of the service class of demand.The constraint is
(1b) 3)Capacity Constraint:Next,we construct the bandwidth requirements by restricting the?ow on a link.To address the fraction of?ow of a service class of the demand on each link (for each path),we now introduce the indicator notation to map between the demand,the service class and the link,as they relate to paths as follows:
if path for service class of nodepair
uses link
otherwise.
Thus,the bandwidth needed on any link(denoted by)to carry?ow for different service classes and demands can now be captured by the amount
Since each link has capacity,we thus have the following constraints for each link:
(1c)
Note the constraints discussed,so far,are already present in the literature and have been thoroughly studied[11].The following constraints are based on additional requirements enforced in this paper upon the engineering of a network. 4)Tunnel Mapping:Now,we consider the number of active tunnels sharing a link.At this end,we?rst need to have a variable that captures if any given path is being used or not. The value take by such a variable depends on the value taken by the corresponding?ow variable.Hence we de?ne as the(binary)tunnel activity variable,which is1if a path is
4
being used to route?ows and0otherwise.Such a functionality can be achieved by incorporating following two constraints:
(1d)
(1e) These constraints incorporate and force dependencies between variables,and.Lets consider is0,constraint(1d) forces to be0.On the other hand,when is0, constraint(1e)forces to be0.Sometimes,we want to ensure that the minimal?ow volume on any tunnel should be greater than a predetermined constant(units).The value of the constant can be determined based on the minimal?ow volume that warrants the setting up and maintenance of a new tunnel.We use the parameter,,in order to limit the activation of tunnels having very low bandwidth.
5)Tunnel Constraint:Based on the discussion in Section II, we enforce that any link should have less that active tunnels.In the rest of the paper,we assume that such a number is determined before hand by considering each link and the interfaces that it is connected to.Now,we force tunnel constraint using
(1f)
(1g) The objective of the formulation is to maximize the total revenue generated by the?ow carried by the network.The traf?c engineering Problem(P)can be formulated as
(2)
subject to the set of constraints(1).It may be noted that this model builds on[13]by incorporating diversity constraints with an attempt to provide further insights into the constraints and parameters of the model.
B.Extended Model
A limitation of the basic model is that it does not incorporate cost due to tunneling.That is,although capabilities of routers (in terms of processing/memory requirements)restrict the maximum number of tunnels on a link,each active tunnel incurs a setup/maintenance cost to the network.From the perspective of a service provider,setup and maintenance of each tunnel requires resources of the network.Certainly, enforcing the tunneling constraint ensures that such resources are available in the network,but the revenue and tunnel cost dependency captures the decision whether the resources should be allocated to a demand or not.Thus,we now discuss how the basic model can be extended.
Consider a demand from source to which can be carried over a path and be the revenue generated from carrying the demand.Assume that the value of is positive and hence carrying the demand by path would lead to higher revenue.Also assume that the links of the path can support the additional tunnel in terms of capacity and number of active tunnels.Then based on the basic model,the demand should be accepted.But,from the perspective of a service provider,it is possible that cost of set-up/maintenance of the tunnel using path is more than the revenue generated by carrying the demand volume.Such a scenario is possible when path has high number of hops because of which the cost of setting up such a tunnel and then maintaining it would be more than the revenue generated by carrying the demand.
A service provider might choose to refuse such a demand to ensure overall optimum.
The current objective function considers the revenue gener-ated by the carried?ow,which is equal to
(3)
Since maximizing the function does not account for the cost to the network in carrying the above mentioned?ow,we need to capture the routing/maintenance cost of these?ows.If is the routing cost of the candidate tunnel,,
and.Then,the total routing cost will be
(4)
The function captures the revenue generated by the network which needs to be maximized and function computes the total routing cost which needs to be minimized.Since,both the objectives are relevant in engineering a network,it is desirable to combine them into an integrated objective function.This is accomplished by weighing one of the functions by a weight factor and taking the difference with the other function and then maximizing the overall function.If we use the normalized weight for the function,then the weight factor(specif-ically,for each and)is needed only for function.Thus,we have the combined objective function as
(5)
Note that in general,routing cost of a tunnel can be determined based on many different aspects.On one hand,one could determine the cost of maintaining the tunnel based on only the setup and maintenance cost which will be additive in the number of hops taken by the tunnel.Such a criteria can be referred to as Hop Based Routing(HPR)cost and will be equal to
On the other hand,cost of tunnel can be determined by con-sidering the forwarding cost associated with the maintenance of the tunnel.In which case,it will be computed based on the ?ow allocated to the tunnel.Such a cost could be referred to as Flow Based Routing(FBR)cost and can be captured as
However,in our case,we compute the cost of routing a tunnel based on both the criteria,that is based on setup and maintenance as well as forwarding required to maintain the tunnel.Hence the total routing cost depends on the volume of
5
?ow on the tunnel and the number of hops and is additive in both.Such a cost could be referred to as Flow and Hop based Routing(FHR)cost and can be captured as
(6)
Hence substituting the value of in the combined objective function,we get
Note that the function is non-linear in nature due to term .But,when coupled with constraints(1d)and(1e),it can be directly inferred that.Hence function can be rewritten and rearranged as
(7) For simplicity,we use the notation
We now present the extended formulation(P)as
(8) subject to the set of constraints(1).
C.Problem Size
The Problem(P)is a Mixed Integer Linear Program with number of variables being
(,binary)
(,continuous).
The number of constraints required to be satis?ed are
(Constraints1d and1e)
(Constraint1a)
(Constraints1c and1f).
For the experimental networks presented in Figures(2-5), we discuss the size of the Problem(P)in Table I.We consider three service classes and demand between every pair of nodes. We consider,15,6,15and15candidate paths()for each service class of each demand of experimental networks I,II, III and IV,respectively.In Table II,we show the number of variables and constraints for even larger networks.For these, we only consder one service class and?ve candidate paths for each demand pair.We assume demand between every pair of nodes.
Typically,generic MIPs are solved using the branch-and-bound algorithm and/or Gomory’s cutting plan method.But such approaches are not quite practical for problems of large size.The Formulation(P)presented above grows with the size
TABLE I
S IZE OF P ROBLEM(P)FOR EN S
ENs#constraints binary
29706174 EN II270
29706188 EN IV2025
#Variables
binary
2506125
3008850
35012075
40015800
45020025
50024750
where,
Note that for a given and,the Lagrangian is separable in and and reduces to solving two independent subproblems
where
subject to constraints(1a),(1c)and(1b)and
subject to constraints(1f)and(1g).
Thus,to solve the original Problem(P),we use the algo-rithmic steps shown in Algorithm1.
1:Generate for all
2:and.
3:Solve and and derive and
4:Solve for and update the values of and
5:Check for the convergence of the iterations,if not con-verged:go to Step
,we have an optimal binary solution of
with for.
The initial inductive assumption is satis?ed as the solution of is binary,since
if
otherwise. Note that for integral and,,as an object either?lls totally or not at all.Hence for,variable takes either the value or.
Now assume that for all integer vectors such that, there exists a binary optimal solution for. We now need to show that has a binary so-lution for each.Let be the optimal solution for and
for,and consider the two feasible binary solutions of:
:with
:with,
for.Let
=and
=and
=. Consider a set of feasible solutions of de?ned as=.The solution consists of fractional values for some of its components and can be written in the following form:
=
=
=
Observe that is a feasible point since by construction ,is a convex combination of and,since
.
We de?ne which is the revenue when the knapsack contains exactly a fraction of object and some amounts of objects
(fractional are possible)which are required to be chosen to?ll optimally a knapsack smaller by in volume.
We show that the Problem for all ,the optimal revenue is=
,and thus,is the optimal and binary solution of.
We show this by contradiction.Suppose,there exists
such that and .Consider a feasible solution=-of
(see Figure1).Because the considered problem is linear,we have
(9) and hence we have.This is a con-tradiction,since we have assumed that is the optimal solution among the all possible values of. Hence the values of,lie on the line segment joining points and.Due to optimality of all,the solution set always contains either ()or().
(11) We assume that the iterations()have converged as soon as ,for chosen value of as error margin.Regarding the generation of a feasible solution,it is known that the?nal solution derived from the algorithm presented above might not be feasible(some of the constraints might be violated)and hence feasible solution needs to be derived at each step of the iteration from the given values of and.The approach we use is to assume the values of(the binary variable)as given and solve the complete Problem(P),which is a linear program, to get feasible values of and compute the value of the
8
1
3
2
11
7
12
8
6
9
10
Fig.2.
Experimental Network I
1
2
3
4
56
Fig.3.Experimental Network II
1
2
3
4
5
6
7
8
9
10
11
12
Fig.4.Experimental Network III 1
2
345
6
7
8
9
10
Fig.5.Experimental Network IV
objective function .During the course of the algorithm,we
store the solution which has the maximum value of objective
function and it is the solution
of the Formulation (P ).Corresponding to the solution,we also store the values of and which are used in further analyzing the solution.
V.R ESULTS
AND
D ISCUSSION
The aim of this section is two-fold:(a)to study the convergence behavior of the decomposition algorithm,(b)to show the interaction between tunneling,capacity and diversity constraints,At this end,we have implemented the decompo-sition algorithm in ,where,we solve the subproblems using CPLEX callable libraries [6].
We conduct the study for experimental networks shown in Figures 2 5.These networks are taken from already published literature [14].For these experimental networks we provide detailed results and help user derive insights into the behavior.EN I has 12nodes,18edges and average nodal degree (ratio of number of edges to number of nodes)of 1.5.EN II has 6nodes,12links and an average nodal degree of 2.0.EN III has 12nodes,25links and an average nodal degree of 2.08.EN IV has 10nodes,26links and an average nodal degree of 2.6.Observe that EN IV is the most well connected network where as EN I is the least.
For the given experimental networks,we consider capacity of Mbps for each link (referred to as baseline capacity).We assume demand between all pairs of nodes.We also assume that each demand has three service classes,where each class has a volume of 100Mbps.We de?ne the value
of diversity constraint
for ,where is the relative diversity requirement of service class and is the normalizing factor.We assume that service class 1(s =1)has highest survivability requirement and hence assume
,service class 2has less stringent requirement and
hence,we assume and for service class 3,we assume
.Since,we assumed that service class 1has highest
survivability requirement,we also assumed that the revenue is higher for that service class and accordingly for other service
classes as well.Hence we assumed
,and for .
0 20
40 60 80 100 120 140 160 50
100
150 200 250 300 V a l u e o f ε --------->
Interations (i) ------->
EN I EN II EN III EN IV
Fig.6.
Convergence results with and 0 50 100 150 200 250 300 350 400 450 50
100
150 200 250 300
V a l u e o f ε --------->
Interations (i) ------->
EN I EN II EN III EN IV
Fig.7.Convergence results with and
0.2 0.4 0.6 0.8 1 1.2 1.4 1.6
50
100
150 200 250 300
V a l u e o f ε --------->
Interations (i) ------->
EN I EN II EN III EN IV
Fig.8.
Convergence results with and 0
0.1
0.20.30.40.50.60.750
100150200250
V a l u e o f ε --------->
Interations (i) ------->
100 node
Fig.9.Convergence results for 100node network
A.Convergence Behavior
We start with the ?rst aim where we establish the con-vergence based on the value of ,where is the iteration count.Notice that captures the resultant step-size based on which duals are updated at each iteration.As the algorithm progresses,the value of decreases and the algorithm stops when .For the study,we assumed that the normal-izing factor .
In order to fully understand the convergence behavior,we study the convergence under three different scenarios.In the ?rst scenario,we ensure that both the tunneling and the capacity constraints are stringent.Hence we assume that
and each link has capacity of 622Mbps.We present
the value of for increasing for the experimental networks in Figure 6.In the next scenario,we ensure that the tunneling constraint is stringent where as network is over-provisioned in terms of capacity.Hence we take and make capacity of each link equal to three times its present value.We present convergence results in Figure 7.Further,we evaluate the counter scenario where (over-provisioned in number of tunnels)and capacity is still 622Mbps (stringent in capacity)and present convergence results in Figure 8.Similar results were observed for other scenarios as well.Note that for all the scenarios the value of decreases in steps.This can be attributed to the parameter ,which is halved if the solution does not improve for 40consecutive iterations.Hence the value of will decrease due to smaller value of .Moreover,we also observed that the for tunnel constrained scenarios,the primal feasible solution ()is much smaller than the relaxed primal solution ().This can be explained by observing that the relaxation is taken around the tunneling constraint.Hence when the tunnels are fewer in number,the primal feasible solution has to reject a lot of ?ows due to non-availability of tunnels.However,for the scenarios which are over-provisioned in number of available tunnels,the tunnels constraint is nearly obviated and the capacity constraint determines the ?ow allocation.In this case the feasible primal solution closely follows the relaxed primal solution.
0.2 0.4 0.6 0.8 1 1.2 600
800
1000 1200 1400 1600 1800 2000 V a l u e o f F A D --------->
Increasing Capacity (Mbps)------->
EN-I EN-II EN-III EN-IV
0.2 0.4 0.6 0.8 1 1.2
600
800
1000 1200 1400 1600 1800 2000 V a l u e o f F U C --------->
Increasing Capacity (Mbps)------->
EN-I EN-II EN-III EN-IV
0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 1.1 1.2 1.3 600
800
1000 1200 1400 1600 1800 2000
V a l u e o f M L U --------->
Increasing Capacity (Mbps)------->
EN-I EN-II EN-III EN-IV
Fig.10.
FAD,FUC and UML for ,
with increasing capacity for ENs
0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 1.1 1.2 1.3 600
800
1000 1200 1400 1600 1800 2000
V a l u e o f F A D --------->
Increasing Capacity (Mbps)------->
EN-I EN-II EN-III EN-IV
0.4 0.5 0.6 0.7 0.8 0.9 1 1.1 1.2
1.3 600
800
1000 1200 1400 1600 1800 2000
V a l u e o f F U C --------->
Increasing Capacity (Mbps)------->
EN-I EN-II EN-III EN-IV
0.5 0.6
0.7 0.8 0.9 1 1.1 1.2 1.3 600
800
1000 1200 1400 1600 1800 2000
V a l u e o f M L U --------->
Increasing Capacity (Mbps)------->
EN-I EN-II EN-III EN-IV
Fig.11.FAD,FUC and UML for ,
with increasing capacity for ENs
In conclusion,we can say that the convergence of the algorithm is good.Note that we could also solve 100node networks (Table II)on a shared machine in less than 300seconds.The networks were randomly generated and we present the convergence behavior for one of them in Figure 9.Moreover,at each step of the decomposition algorithm,we solve linear programs.Fairly sophisticated techniques exist for solving large linear programs in the literature [3].They can be directly applied to extend the approach for even larger size networks.
In the following sections,we use the decomposition al-gorithm to study the formulation to understand the interplay between the tunneling,capacity and diversity constraint.The intention is to understand the performance of network under various provisioning scenarios and the role of various param-eters towards the solution of the formulation.B.Impact of Capacity Constraint
In order to study the role of capacity constraint,we con-ducted experiments where we varied the values of tunneling and diversity constraints while increasing capacity from base line value (100%)to three times the baseline capacity (300%).We present the value of fraction of accepted demands (FAD),the fraction of used capacity (FUC)and the utilization of maximum loaded link (UML)for and in
Figure 10and
and in Figure 11,respectively.We observed that the presence of fewer number of tunnels prevents the demands from utilizing the excess capacity in the network.The effect gets ampli?ed when coupled with smaller values of which prevents a tunnel from accepting more ?ow,even if the links have unused capacity and demands are getting refused.Furthermore,higher survivability requirement translates into demands requiring more and more tunnels,thus leading to increased requirement of tunnels in the network.Therefore,minor relaxations in the survivability requirement
of demands translates into much fewer values of required tunnels to achieve similar performance.C.Impact of Tunnel constraint
Next,we study the role of tunneling constraint and the way in which the formulation responds to increasing number of tunnels for various provisioning scenarios.Here,we present results showing the changes in values of FAD,FUC and MLU where available number of tunnels are increased from 10to 50.We consider and baseline capacity in Figure 12and
and 300%of the baseline capacity in Figure 13.The
intention is to isolate the regions where tunneling constraint is critical to achieve higher utilization of the network resources.We observed that for network operating under the state of overload in terms of capacity,fairly small number of tunnels are required to sustain the network in its high load state.These small numbers are further lowered by decreasing the survivability level of the demands supported by the net-work.Interestingly,we found that the networks having higher amounts of capacity and higher levels of survivability are much more sensitive to number of allowed tunnels in the network.The impact is even more prominent for sparsely-connected,large-sized networks like EN-I and EN-III.
D.Impact of Diversity Constraint
In this section,we study the role of diversity constraint towards the utilization of available capacity in the network.Hence we present the value of FAD,FUC and MLU for values of from 0.15to 0.95with and baseline capacity in Figure 14and and 300%of the baseline capacity in Figure 15.Note that changing the value of does not alter the relative survivability requirement amongst the service classes.When we decrease the value of ,we scale up the over all survivability requirement of all the service classes in the network.
0 0.2 0.4 0.6 0.8 1 1.2 1.4 10
15
20 25 30 35 40 45 50 V a l u e o f F A D --------->
Increasing # tunnels------->
EN-I EN-II EN-III EN-IV
0.4
0.5 0.6 0.7 0.8 0.9 1 1.1 1.2
1.3 1.4 10
15
20 25 30 35 40 45 50 V a l u e o f F U C --------->
Increasing # tunnels------->
EN-I EN-II EN-III EN-IV
0.4
0.5 0.6 0.7 0.8 0.9 1 1.1 1.2 1.3 1.4 10
15
20 25 30 35 40 45 50
V a l u e o f M L U --------->
Increasing # tunnels------->
EN-I EN-II EN-III EN-IV
Fig.12.
FAD,FUC and UML for ENs with
and baseline capacity for increasing #of tunnels
0.2
0.4 0.6 0.8 1 1.2 1.4 10
15
20 25 30 35 40 45 50
V a l u e o f F A D --------->
Increasing # tunnels------->
EN-I EN-II EN-III EN-IV
0.2
0.4 0.6 0.8 1 1.2 1.4 10
15
20 25 30 35 40 45
50
V a l u e o f F U C --------->
Increasing # tunnels------->
EN-I EN-II EN-III EN-IV
0.2
0.4 0.6 0.8 1 1.2 1.4 10
15
20 25 30 35 40 45
50
V a l u e o f M L U --------->
Increasing # tunnels------->
EN-I EN-II EN-III EN-IV
Fig.13.FAD,FUC and UML for ENs with
and 300%of baseline capacity for increasing #of tunnels
0.2 0.4 0.6 0.8 1 1.2 0.3
0.4
0.5
0.6
0.7
0.8
0.9
V a l u e o f F A D --------->
Increasing value of h * ------->
EN-I EN-II EN-III EN-IV
0.4
0.5 0.6 0.7 0.8 0.9 1 1.1 1.2
1.3 0.3
0.4
0.5
0.6
0.7
0.8
0.9
V a l u e o f F U C --------->
Increasing value of h * ------->
EN-I EN-II EN-III EN-IV
0.4
0.5
0.6 0.7 0.8 0.9 1 1.1 1.2 1.3 0.3
0.4
0.5
0.6
0.7
0.8
0.9
V a l u e o f M L U --------->
Increasing value of h * ------->
EN-I EN-II EN-III EN-IV
Fig.14.
FAD,FUC and UML for ENs with
and baseline capacity with increasing
0.2
0.4 0.6 0.8 1 1.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 V a l u e o f F A D --------->
Increasing value of h * ------->EN-I EN-II EN-III EN-IV
0.2
0.4 0.6 0.8 1 1.2
0.3 0.4 0.5 0.6 0.7 0.8 0.9 V a l u e o f F U C --------->
Increasing value of h * ------->
EN-I EN-II EN-III EN-IV
0.3
0.4 0.5 0.6 0.7 0.8 0.9 1 1.1 1.2 1.3 0.3 0.4 0.5 0.6 0.7 0.8 0.9
V a l u e o f M L U --------->
Increasing value of h * ------->
EN-I EN-II EN-III EN-IV
Fig.15.FAD,FUC and UML for ENs with and 300%of baseline capacity with increasing
Interestingly,a reasonably high (0.65)suf?ces to ensure high levels of utilization of network capacity.In other cases with fewer tunnels,even for much lower levels of survivability (=0.95),the available capacity is not utilized.That is to say that the demands are refused (value of FAD is less than one)although un-utilized capacity is available in the network (FUC and MLU are less than one).Hence such small amounts of tunnels are extremely unacceptable for such well-provisioned (in terms of capacity)networks.More so,in order to provide higher levels of survivability in a large,sparsely-connected network,a sacri?ce has to be made in terms of fraction of accepted demands.That is,in extreme cases,it might require rejection of demands in order to ensure higher survivability standards to the accepted demands.
E.Impact of Tunnel Cost
Note that we had assumed ,and for .In order to study the impact of weight factor on the allocation of ?ows and tunnels,we vary the value of
from 0.1to 0.9.We present the values of FAD,FUC
and MLU with and baseline capacity in Figure 16and and 300%of the baseline capacity in Figure 17.
Note that as the value of increases,longer (multi-hop)paths are no more pro?table and hence solution moves towards allocating more and more ?ows to min-hop paths.Such a behavior translates directly into much lower values of FUC
and MLU.More so,the value of
and determine the set of acceptable paths for a service class of a demand.For given and ,service class 3(s=3)tunnels with fewer
0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
1.1 0.1
0.2
0.3
0.4 0.5 0.6 0.7 0.8 0.9 V a l u e o f F A D --------->
Weight factor θ ------->
EN-I EN-II EN-III EN-IV
0.65
0.7 0.75 0.8 0.85 0.9 0.95 1 1.05
1.1 0.1
0.2 0.3
0.4 0.5 0.6 0.7 0.8 0.9
V a l u e o f F U C --------->
Weight factor θ ------->
EN-I EN-II EN-III EN-IV
0.7 0.75
0.8 0.85 0.9 0.95 1 1.05 1.1 0.1
0.2 0.3
0.4 0.5 0.6 0.7 0.8 0.9
V a l u e o f M L U --------->
Weight factor θ ------->
EN-I EN-II EN-III EN-IV
Fig.16.
FAD,FUC and UML for
and baseline capacity with increasing
0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
1.1 0.1
0.2 0.3
0.4 0.5 0.6 0.7 0.8 0.9 V a l u e o f F A D --------->
Weight factor θ ------->
EN-I EN-II EN-III EN-IV
0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
1.1 0.1
0.2 0.3
0.4 0.5 0.6 0.7 0.8 0.9
V a l u e o f F U C --------->
Weight factor θ ------->
EN-I EN-II EN-III EN-IV
0.3 0.4
0.5 0.6 0.7 0.8 0.9 1 1.1 0.1
0.2 0.3
0.4 0.5 0.6 0.7 0.8 0.9
V a l u e o f M L U --------->
Weight factor θ ------->
EN-I EN-II EN-III EN-IV
Fig.17.FAD,FUC and UML for
and 300%of baseline capacity with increasing
than four hops would still lead to positive revenue,where as for service class 2tunnels with less than six hops are still acceptable and for service class 1tunnels with 10hops can be used for allocating ?ows.Hence the diversity constraint and the tunnel cost have a balancing impact.Smaller value of the diversity constraint forces a demand volume to take multiple paths (which are also longer path),but such long paths are no longer pro?table (for a given )and hence formulation chooses to reject the extra demand volume inspite of the presence of capacity and tunnels on the links.
VI.C ONCLUSION
In this paper,we present a diversity based protection ap-proach for low cost,best-effort services in a tunnel based network to avoid any total loss of connection due to node/link failures.Introduction of such a diversity based approach could lead to over whelming number of tunnels in the network.Hence we also introduced tunneling constraint by restricting the number of active tunnels on a link.Diversity reservation is embedded by restricting the fraction of allocated demand on a tunnel.We also extend the model to incorporate a hop and ?ow based tunnel cost.The integrated model is a mixed integer linear program.We also present a Lagrangian relaxation based decomposition approach to solve the problem for large networks.The approach requires solving multiple programs of smaller size and simultaneously updating the dual so as to arrive at the ?nal https://www.wendangku.net/doc/8c6786800.html,ing the solu-tion approach,we present results demonstrating the interplay between tunneling,capacity and diversity constraints.The results showed that the tunnel constraint has similar effect as that of the capacity.Particularly,for large-sized,sparsely-connected networks,tunneling and diversity constraints affect the solution more drastically.More so,for networks having stringent survivability requirements,presence of higher num-ber of tunnels on each link becomes crucial.
R EFERENCES
[1] D.Applegate and M.Thorup.Load Optimal MPLS routing with N+M
Labels.In Proceedings of INFOCOM ,San Francisco,2003.IEEE.[2]L.Bahiense,F.Barahoma,and O.Porto.Solving Steiner Tree Problem
in Graphs with Lagrangian Relaxation.Journal of Combinatorial Optimization ,7:259–282,2003.
[3]V .Chvatal.Linear Programming .A Series of Books in the Mathematical
Sciences.Freeman,1983.
[4] B.Gavish,P.Trudeau,M.Dror,M.Gendreau,and L.Mason.Fiberoptic
Circuit Network Design under Reliability Constraints.IEEE Journal on Selected Areas of Communication ,7(8):1181–1187,1989.
[5]K.Holmberg and J.Hellstrand.Solving the uncapicitated network design
problem by a Lagrangian heuristic and branch-and-bound.Operations Research ,46:247–259,1998.
[6]ILOG Corporation,USA.Manual of Cplex Callable Libraries .
[7]M.Kodialam and T.V .Lakshman.Dynamic Routing of Locally
Restorable Bandwidth Guaranteed Tunnels Using Aggregate Link In-formation.In Proceedings of INFOCOM ,pages 376–85,2001.
[8] D.Medhi.Diverse Routing for Survivability in a ?ber-based Sparse Net-work.In Proceedings of International Conference on Communications .IEEE,June 1991.
[9] A.Medina,N.Taft,K.Salamatian,S.Bhattacharyya,and C.Diot.
Traf?c Matrix Estimation:Existing Techniques and New Directions.In Proceeding of SIGCOMM .ACM,2002.
[10]M.Minoux.Mathematical Programming -Theory and Algorithms .J.
Wiley &Sons,1986.
[11] D.Mitra and K.Ramakrishnan.A case study of Multiservice,Multipri-ority Traf?c Engineering Design of Data Networks.In Proceedings of GLOBECOM .IEEE,1999.[12]M.Pi′o ro and D.Medhi.Routing,Flow,and Capacity Design in
Communication and Computer Networks .Morgan Kauffmann,2004.[13]S.Srivastava, B.Krithikaivasan, D.Medhi,and M.Pi′o ro.Traf?c
Engineering in the Presence of Tunneling and Diversity Constraints:Formulation and Lagrangean Decomposition Approach.In Proceedings of International Teletraf?c Congress ,Berlin,2003.Elsevier Science.[14]S.Srivastava,S.R.Thirumalasetty,and https://www.wendangku.net/doc/8c6786800.html,work Traf?c
Engineering with varied levels of Protection in Next Generation Internet.In A.Girard,B.Sans′o ,and F.V′a zquez-Abad,editors,25Anniversary GERAD Issue for Performance Evaluation and Planning Methods for the Next Generation Internet .Kluwer Publisher,2005.
[15] D.Stamatelakis and W.Grover.Theoretical underpinnings for the
ef?ciency of restorable networks using precon?gured cycles (p-cycles).IEEE Transactions on Communications ,48(4),2000.
[16]T.H.Wu.Fiber Network Service Survivability .Artech House,1992.[17]X.Xiao,A.Hannan,B.Bailey,and L.Ni.Traf?c Engineering with
MPLS in the Internet.IEEE Network Magazine ,pages 28–33,March 2000.
vlookup函数的使用方法及实例.doc
vlookup函数的使用方法及实例vlookup函数的使用方法及实例 excel中vlookup函数的应用，重要在于实践。 下面我们先了就下函数的构成;接着举个例子说下;最后总结下急提下遇到的相关问题： (本作者采用的是excel2003版，不过这函数在任何版本都适应) 2首先我们介绍下使用的函数vlookup 的几个参数，vlookup是判断引用数据的函数，它总共有四个参数，依次是： 1、判断的条件 2、跟踪数据的区域 3、返回第几列的数据 4、是否精确匹配 该函数的语法规则如下： =VLOOKUP(lookup_value,table_array,col_index_num,range_looku p) 该函数的语法规则可以查看到，如下图： (excel07版) 如下图，已知表sheet1中的数据如下，如何在数据表二sheet2 中如下引用：当学号随机出现的时候，如何在B列显示其对应的物理成绩? 根据问题的需求，这个公式应该是：
vmdk文件损坏打不开怎么修复vmware vmdk文件损坏打不开修复方法一 EasyRecovery数据恢复软件支持恢复VMDK文件并存储在本地文件系统中。由于数据和有关虚拟服务器的配置信息都存储在VMDK文件中，而每个虚拟系统下通常又有多个VMDK镜像，此时选择正确的VMDK镜像对成功的完成文件恢复扫描而言就显得至关重要了。载入VMDK镜像并选择对应的卷，以开始扫描VMDK文件。 根据EasyRecovery软件给出的提示操作，完成VMDK文件恢复。 当然要想保证VMDK文件恢复的顺利进行，还需注意以下几点： 1、当发现数据丢失之后，不要进行任何操作，因操作系统运行时产生的虚拟内存和临时文件会破坏数据或覆盖数据; 2、不要轻易尝试Windows的系统还原功能，这并不会找回丢失的文件，只会为后期的恢复添置不必要的障碍; 3、不要反复使用杀毒软件，这些操作是无法找回丢失文件的。 vmware vmdk文件损坏打不开修复方法二
交互式多模型算法仿真与分析
硕037班 刘文3110038020 2011/4/20交互式多模型仿真与分析IMM算法与GBP算法的比较，算法实现和运动目标跟踪仿真，IMM算法的特性分析 多源信息融合实验报告
交互式多模型仿真与分析 一、 算法综述 由于混合系统的结构是未知的或者随机突变的，在估计系统状态参数的同时还需要对系统的运动模式进行辨识，所以不可能通过建立起一个固定的模型对系统状态进行效果较好的估计。针对这一问题，多模型的估计方法提出通过一个模型集{}(),1,2,,j M m j r == 中不同模型的切换来匹配不同目标的运动或者同一目标不同阶段的运动，达到运动模式的实时辨识的效果。 目前主要的多模型方法包括一阶广义贝叶斯方法（BGP1），二阶广义贝叶斯方法（GPB2）以及交互式多模型方法等（IMM ）。这些多模型方法的共同点是基于马尔科夫链对各自的模型集进行切换或者融合，他们的主要设计流程如下图： M={m1,m2,...mk} K 时刻输入 值的形式 图一 多模型设计方法 其中，滤波器的重初始化方式是区分不同多模型算法的主要标准。由于多模型方法都是基于一个马尔科夫链来切换与模型的，对于元素为r 的模型集{}(),1,2,,j M m j r == ，从0时刻到k 时刻，其可能的模型切换轨迹为 120,12{,,}k i i i k trace k M m m m = ，其中k i k m 表示K-1到K 时刻，模型切换到第k i 个， k i 可取1,2,,r ，即0,k trace M 总共有k r 种可能。再令1 2 1 ,,,,k k i i i i μ+ 为K+1时刻经由轨迹0,k trace M 输入到第1k i +个模型滤波器的加权系数，则输入可以表示为 0,11 2 1 12|,,,,|,,,???k k trace k k k i M k k i i i i k k i i i x x μ++=?∑ 可见轨迹0,k trace M 的复杂度直接影响到算法计算量和存储量。虽然全轨迹的
五种大数据压缩算法
?哈弗曼编码 A method for the construction of minimum-re-dundancy codes, 耿国华1数据结构1北京:高等教育出版社,2005:182—190 严蔚敏,吴伟民.数据结构(C语言版)[M].北京:清华大学出版社,1997. 冯桂,林其伟,陈东华.信息论与编码技术[M].北京:清华大学出版社,2007. 刘大有,唐海鹰,孙舒杨,等.数据结构[M].北京:高等教育出版社,2001 ?压缩实现 速度要求 为了让它(huffman.cpp)快速运行，同时不使用任何动态库，比如STL或者MFC。它压缩1M数据少于100ms（P3处理器，主频1G）。 压缩过程 压缩代码非常简单，首先用ASCII值初始化511个哈夫曼节点： CHuffmanNode nodes[511]; for(int nCount = 0; nCount < 256; nCount++) nodes[nCount].byAscii = nCount; 其次，计算在输入缓冲区数据中，每个ASCII码出现的频率： for(nCount = 0; nCount < nSrcLen; nCount++) nodes[pSrc[nCount]].nFrequency++; 然后，根据频率进行排序： qsort(nodes, 256, sizeof(CHuffmanNode), frequencyCompare); 哈夫曼树，获取每个ASCII码对应的位序列： int nNodeCount = GetHuffmanTree(nodes); 构造哈夫曼树 构造哈夫曼树非常简单，将所有的节点放到一个队列中，用一个节点替换两个频率最低的节点，新节点的频率就是这两个节点的频率之和。这样，新节点就是两个被替换节点的父
LZ77压缩算法实验报告
LZ77压缩算法实验报告 一、实验内容 使用C++编程实现LZ77压缩算法的实现。 二、实验目的 用LZ77实现文件的压缩。 三、实验环境 1、软件环境：Visual C++ 6.0 2、编程语言：C++ 四、实验原理 LZ77 算法在某种意义上又可以称为“滑动窗口压缩”，这是由于该算法将一个虚拟的，可以跟随压缩进程滑动的窗口作为术语字典，要压缩的字符串如果在该窗口中出现，则输出其出现位置和长度。使用固定大小窗口进行术语匹配，而不是在所有已经编码的信息中匹配，是因为匹配算法的时间消耗往往很多，必须限制字典的大小才能保证算法的效率；随着压缩的进程滑动字典窗口，使其中总包含最近编码过的信息，是因为对大多数信息而言，要编码的字符串往往在最近的上下文中更容易找到匹配串。 五、LZ77算法的基本流程 1、从当前压缩位置开始，考察未编码的数据，并试图在滑动窗口中找出最长的匹 配字符串，如果找到，则进行步骤2，否则进行步骤3。 2、输出三元符号组( off, len, c )。其中off 为窗口中匹
配字符串相对窗口边 界的偏移，len 为可匹配的长度，c 为下一个字符。然后将窗口向后滑动len + 1 个字符，继续步骤1。 3、输出三元符号组( 0, 0, c )。其中c 为下一个字符。然后将窗口向后滑动 len + 1 个字符，继续步骤1。 六、源程序 /********************************************************************* * * Project description: * Lz77 compression/decompression algorithm. * *********************************************************************/ #include VLOOKUP函数调用方法如下：（本次以提取RRU挂高数据为例） 一、本次涉及的相关文档。 1．《某地区TD宏站现场勘测数据汇总表》如表1-1，共1000多站，本次共列出104个站点的信息： 查看原文档请双击图标：某地区TD宏站现场 查勘数据汇总表，表1-1抓图如下： 2．某工程报价单，共30个宏站，如表1-2（本报价单其他信息均删除，只保留了站点名） 查看原文档请双击图标：某工程报价单.xlsx ，表1-2抓图如下： 二、本次我们以从表1-1中提取表1-2中30个站点的RRU挂高为例，具体步骤如下： 1．先在表1-2中增加“RRU挂高”这一列，然后先提取“某城关水泵厂南”的RRU挂高。操作方法为双击下图所示灰色表格，然后鼠标左键单击列表上面的fx插入函 数。 2．点fx后弹出如下图标，在下拉列表中选择“VLOOKUP”，点确定。 3．点确定后，弹出VLOOKUP函数调用表，包含4个部分（lookup_value、Table_array、C ol_index_num、Range_lookup）。 lookup_value:需要在数据表首列进行搜索的值，本次值为表1-1中的位置B2，用 鼠标单击表1-1中的“某城关水泵厂南”，即可自动输入。。 Table_array：需要在其中搜索数据的信息表，即在表1-2中选择一个搜索区域， 注意所选区域第一列必须是与Lookup_value中查找数值相匹配的 列（本次表1-1中的B列），最后一列必须大于等于RRU挂高那一列 （大于等于C列）,至于下拉行数肯定要大于等于106行。如下图： 选择相关区域后，VLOOKUP表中的Table_array会自动输入表1-1中所选区域，如 下图： 实验名称：LZSS压缩算法实验报告 一、实验内容 使用Visual 6..0 C++编程实现LZ77压缩算法。 二、实验目的 用LZSS实现文件的压缩。 三、实验原理 LZSS压缩算法是词典编码无损压缩技术的一种。LZSS压缩算法的字典模型使用了自适应的方式，也就是说，将已经编码过的信息作为字典， 四、实验环境 1、软件环境：Visual C++ 6.0 2、编程语言：C++ 五、实验代码 #include -- need byte-swap function for big endian CPU */ #define READ_LE32(X) *(uint32_t *)(X) #define WRITE_LE32(X,Y) *(uint32_t *)(X) = (Y) /* this assumes sizeof(long)==4 */ typedef unsigned long uint32_t; /* text (input) size counter, code (output) size counter, and counter for reporting progress every 1K bytes */ static unsigned long g_text_size, g_code_size, g_print_count; /* ring buffer of size N, with extra F-1 bytes to facilitate string comparison */ static unsigned char g_ring_buffer[N + F - 1]; /* position and length of longest match; set by insert_node() */ static unsigned g_match_pos, g_match_len; /* left & right children & parent -- these constitute binary search tree */ static unsigned g_left_child[N + 1], g_right_child[N + 257], g_parent[N + 1]; /* input & output files */ static FILE *g_infile, *g_outfile; /***************************************************************************** initialize trees *****************************************************************************/ static void init_tree(void) { unsigned i; /* For i = 0 to N - 1, g_right_child[i] and g_left_child[i] will be the right and left children of node i. These nodes need not be initialized. Also, g_parent[i] is the parent of node i. These are initialized to NIL (= N), which stands for 'not used.' For i = 0 to 255, g_right_child[N + i + 1] is the root of the tree for strings that begin with character i. These are initialized to NIL. Note there are 256 trees. */ for(i = N + 1; i <= N + 256; i++) g_right_child[i] = NIL; for(i = 0; i < N; i++) g_parent[i] = NIL; } /***************************************************************************** Inserts string of length F, g_ring_buffer[r..r+F-1], into one of the trees (g_ring_buffer[r]'th tree) and returns the longest-match position and length via the global variables g_match_pos and g_match_len. If g_match_len = F, then removes the old node in favor of the new one, because the old one will be deleted sooner. excel博大精深，其使用中有许多细节的地方需要注意。 vlookup函数的使用，其语法我就不解释了，百度很多，其实我自己也没看懂语法的解释，下面就按照我自己的理解来说说怎么用的。首先，这个函数是将一个表中的数据导入另一个表中，其中这两个表有一列数据是相同项，但是排列顺序不同。举例说明； 表1 表2 将表1中的face量一列导入表2中，但两表中的名称一列的排列顺序是不同的。此时需要使用vlookup函数。 下面介绍vlookup的使用方法。 将鼠标放到表2中的D2单元格上，点击fx,会出现一个对话框，里面有vlookup函数。若在常用函数里面没有，下拉找“查找与引用”，里面有此函数。点确定。表示此函数是在表2中的D2单元格中应用。 此时出现对话框： 在第个格里输入B2，直接用鼠标在表2中点击B2单元格即可。表示需要在查找的对象是表2中的B2单元格中的内容。 然后是第二个格，点表1，用鼠标选择整个表的所有数据。表示要在表1中的B1—C14区域查找表2中的B2单元格中的内容。 第三个格里输入在表2中要导入的列数在表1中的列数的数字。在此例中为C列，其列数数字为2.表示将表1中（B1—C14）区域中查找到的单元格里的内容相对应的列（第2列）中的单元格中的内容（face量列中的数据）导入表2中相应的单元格（D2）。 最后一个格中输入“0”。表示查找不到就出现#N/A。点确定，即出现相应数据，然后下拉复制格式。 当下拉出现这种情况的时候： 其实是其查找区域在下拉过程中随着行的改变而改变了。需要对查找区域做一下固定。其方法为，在选择区域后，在区域前面加“$”号（$B$1：$C$14）。 多媒体数据压缩实验报告 篇一：多媒体实验报告_文件压缩 课程设计报告 实验题目：文件压缩程序 姓名：指导教师：学院：计算机学院专业：计算机科学与技术学号： 提交报告时间：20年月日 四川大学 一，需求分析： 有两种形式的重复存在于计算机数据中，文件压缩程序就是对这两种重复进行了压 缩。 一种是短语形式的重复，即三个字节以上的重复，对于这种重复，压缩程序用两个数字：1.重复位置距当前压缩位置的距离；2.重复的长度，来表示这个重复，假设这两个数字各占一个字节，于是数据便得到了压缩。 第二种重复为单字节的重复，一个字节只有256种可能的取值，所以这种重复是必然的。给 256 种字节取值重新编码，使出现较多的字节使用较短的编码，出现较少的字节使用较长的编码，这样一来，变短的字节相对于变长的字节更多，文件的总长度就会减少，并且，字节使用比例越不均 匀，压缩比例就越大。 编码式压缩必须在短语式压缩之后进行，因为编码式压缩后，原先八位二进制值的字节就被破坏了，这样文件中短语式重复的倾向也会被破坏（除非先进行解码）。另外，短语式压缩后的结果：那些剩下的未被匹配的单、双字节和得到匹配的距离、长度值仍然具有取值分布不均匀性，因此，两种压缩方式的顺序不能变。 本程序设计只做了编码式压缩，采用Huffman编码进行压缩和解压缩。Huffman编码是一种可变长编码方式，是二叉树的一种特殊转化形式。编码的原理是：将使用次数多的代码转换成长度较短的代码，而使用次数少的可以使用较长的编码，并且保持编码的唯一可解性。根据 ascii 码文件中各 ascii 字符出现的频率情况创建 Huffman 树，再将各字符对应的哈夫曼编码写入文件中。同时，亦可根据对应的哈夫曼树，将哈夫曼编码文件解压成字符文件. 一、概要设计： 压缩过程的实现: 压缩过程的流程是清晰而简单的: 1. 创建 Huffman 树 2. 打开需压缩文件 3. 将需压缩文件中的每个 ascii 码对应的 huffman 编码按 bit 单位输出生成压缩文件压缩结束。 VLOOKUP函数的使用方法(入门级) VLOOKUP函数是Excel中几个最重函数之一，为了方便大家学习，兰色幻想特针对VLOOKUP 函数的使用和扩展应用，进行一次全面综合的说明。本文为入门部分 一、入门级 VLOOKUP是一个查找函数，给定一个查找的目标，它就能从指定的查找区域中查找返回想要查找到的值。它的基本语法为： VLOOKUP（查找目标，查找范围，返回值的列数，精确OR模糊查找) 下面以一个实例来介绍一下这四个参数的使用 例1：如下图所示，要求根据表二中的姓名，查找姓名所对应的年龄。 公式：B13 =VLOOKUP(A13,$B$2:$D$8,3,0) 参数说明： 1 查找目标：就是你指定的查找的内容或单元格引用。本例中表二A列的姓名就是查找目标。我们要根据表二的“姓名”在表一中A列进行查找。 公式：B13 =VLOOKUP(A13,$B$2:$D$8,3,0) 2 查找范围（VLOOKUP(A13,$B$2:$D$8,3,0) ）：指定了查找目标，如果没有说从哪里查找，EXCEL肯定会很为难。所以下一步我们就要指定从哪个范围中进行查找。VLOOKUP的这第二个参数可以从一个单元格区域中查找，也可以从一个常量数组或内存数组中查找。本例中要从表一中进行查找，那么范围我们要怎么指定呢？这里也是极易出错的地方。大家一定要注意，给定的第二个参数查找范围要符合以下条件才不会出错： A 查找目标一定要在该区域的第一列。本例中查找表二的姓名，那么姓名所对应的表一的姓名列，那么表一的姓名列（列）一定要是查找区域的第一列。象本例中，给定的区域要从第二列开始，即$B$2:$D$8，而不能是$A$2:$D$8。因为查找的“姓名”不在$A$2:$D$8区域的第一列。 B 该区域中一定要包含要返回值所在的列，本例中要返回的值是年龄。年龄列（表一的D列）一定要包括在这个范围内，即：$B$2:$D$8，如果写成$B$2:$C$8就是错的。 3 返回值的列数（B13 =VLOOKUP(A13,$B$2:$D$8,3,0)）。这是VLOOKUP第3个参数。它是一个整数值。它怎么得来的呢。它是“返回值”在第二个参数给定的区域中的列数。本例中我们 价值工程 置，是一项十分有意义的工作。另外恶意代码的检测和分析是一个长期的过程，应对其新的特征和发展趋势作进一步研究，建立完善的分析库。 参考文献： [1]CNCERT/CC.https://www.wendangku.net/doc/8c6786800.html,/publish/main/46/index.html. [2]LO R,LEVITTK,OL SSONN R.MFC:a malicious code filter [J].Computer and Security,1995,14(6):541-566. [3]KA SP ER SKY L.The evolution of technologies used to detect malicious code [M].Moscow:Kaspersky Lap,2007. [4]LC Briand,J Feng,Y Labiche.Experimenting with Genetic Algorithms and Coupling Measures to devise optimal integration test orders.Software Engineering with Computational Intelligence,Kluwer,2003. [5]Steven A.Hofmeyr,Stephanie Forrest,Anil Somayaji.Intrusion Detection using Sequences of System calls.Journal of Computer Security Vol,Jun.1998. [6]李华,刘智,覃征,张小松.基于行为分析和特征码的恶意代码检测技术[J].计算机应用研究，2011，28（3）：1127-1129. [7]刘威，刘鑫，杜振华.2010年我国恶意代码新特点的研究.第26次全国计算机安全学术交流会论文集，2011，（09）. [8]IDIKA N,MATHUR A P.A Survey of Malware Detection Techniques [R].Tehnical Report,Department of Computer Science,Purdue University,2007. 0引言 现有的压缩算法有很多种，但是都存在一定的局限性，比如：LZw [1]。主要是针对数据量较大的图像之类的进行压缩，不适合对简单报文的压缩。比如说，传输中有长度限制的数据，而实际传输的数据大于限制传输的数据长度，总体数据长度在100字节左右，此时使用一些流行算法反而达不到压缩的目的，甚至增大数据的长度。本文假设该批数据为纯数字数据，实现压缩并解压缩算法。 1数据压缩概念 数据压缩是指在不丢失信息的前提下，缩减数据量以减少存储空间，提高其传输、存储和处理效率的一种技术方法。或按照一定的算法对数据进行重新组织，减少数据的冗余和存储的空间。常用的压缩方式[2,3]有统计编码、预测编码、变换编码和混合编码等。统计编码包含哈夫曼编码、算术编码、游程编码、字典编码等。 2常见几种压缩算法的比较2.1霍夫曼编码压缩[4]：也是一种常用的压缩方法。其基本原理是频繁使用的数据用较短的代码代替，很少使用 的数据用较长的代码代替，每个数据的代码各不相同。这些代码都是二进制码，且码的长度是可变的。 2.2LZW 压缩方法[5,6]：LZW 压缩技术比其它大多数压缩技术都复杂，压缩效率也较高。其基本原理是把每一个第一次出现的字符串用一个数值来编码，在还原程序中再将这个数值还成原来的字符串，如用数值0x100代替字符串ccddeee"这样每当出现该字符串时，都用0x100代替，起到了压缩的作用。 3简单报文数据压缩算法及实现 3.1算法的基本思想数字0-9在内存中占用的位最 大为4bit ， 而一个字节有8个bit ，显然一个字节至少可以保存两个数字，而一个字符型的数字在内存中是占用一个字节的，那么就可以实现2:1的压缩，压缩算法有几种，比如，一个自己的高四位保存一个数字，低四位保存另外一个数字，或者，一组数字字符可以转换为一个n 字节的数值。N 为C 语言某种数值类型的所占的字节长度，本文讨论后一种算法的实现。 3.2算法步骤 ①确定一种C 语言的数值类型。 —————————————————————— —作者简介：安建梅（1981-），女，山西忻州人，助理实验室，研究方 向为软件开发与软交换技术；季松华（1978-），男，江苏 南通人，高级软件工程师，研究方向为软件开发。 数据快速压缩算法的研究以及C 语言实现 The Study of Data Compression and Encryption Algorithm and Realization with C Language 安建梅①AN Jian-mei ；季松华②JI Song-hua （①重庆文理学院软件工程学院，永川402160；②中信网络科技股份有限公司，重庆400000）（①The Software Engineering Institute of Chongqing University of Arts and Sciences ，Chongqing 402160，China ； ②CITIC Application Service Provider Co.，Ltd.，Chongqing 400000，China ） 摘要：压缩算法有很多种，但是对需要压缩到一定长度的简单的报文进行处理时，现有的算法不仅达不到目的，并且变得复杂， 本文针对目前一些企业的需要，实现了对简单报文的压缩加密，此算法不仅可以快速对几十上百位的数据进行压缩，而且通过不断 的优化，解决了由于各种情况引发的解密错误，在解密的过程中不会出现任何差错。 Abstract:Although,there are many kinds of compression algorithm,the need for encryption and compression of a length of a simple message processing,the existing algorithm is not only counterproductive,but also complicated.To some enterprises need,this paper realizes the simple message of compression and encryption.This algorithm can not only fast for tens of hundreds of data compression,but also,solve the various conditions triggered by decryption errors through continuous optimization;therefore,the decryption process does not appear in any error. 关键词：压缩；解压缩；数字字符；简单报文Key words:compression ；decompression ；encryption ；message 中图分类号：TP39文献标识码：A 文章编号：1006-4311（2012）35-0192-02 ·192· VLOOKUP函数是Excel中的一个纵向查找函数，它与LOOKUP函数和HLOOKUP函数属于一类函数，在工作中都有广泛应用。VLOOKUP是按列查找，最终返回该列所需查询列序所对应的值；与之对应的HLOOKUP是按行查找的。 VLOOKUP函数的语法结构 整个计算机就相当于一门语言，首先我们就是要获取该函数的语法结构。以下是官网的语法结构 VLOOKUP（lookup_value, table_array, col_index_num, [range_looku p]）。 书上表述就是VLOOKUP（查找值，查找范围，查找列数，精确匹配或者近似匹配） 在我们的工作中，几乎都使用精确匹配，该项的参数一定要选择为false。否则返回值会出乎你的意料。 VLOOKUP函数使用示范 vlookup就是竖直查找，即列查找。通俗的讲，根据查找值参数，在查找范围的第一列搜索查找值，找到该值后，则返回值为：以第一列为准，往后推数查找列数值的这一列所对应的值。这也是为什么该函数叫做vlookup（v为vertic al-竖直之意，lookup即时英文的查找之意）。 现有如下手机的每日销售毛数据（图左），A分销商需要提供四个型号的销售数据（图右） 这个时候，你大概可能回去一个一个人工查找，因为我所提供的数据数量很少，但是其实工作中这种数据很庞大的，人工查找无疑即浪费时间，而且不能让A分销商相信你所提供数据的准确性。接下来，我们就需要本次的主角登场了。使用vlookup函数。 第一步：选中要输入数据的单元格，=VLOOKUP（H3,$A$3:$F$19,5,FALSE）如图 压缩编码算法设计与实现实验报告 一、实验目的：用C语言或C++编写一个实现Huffman编码的程序，理解对数据进行无损压缩的原理。 二、实验内容：设计一个有n个叶节点的huffman树，从终端读入n个叶节 点的权值。设计出huffman编码的压缩算法，完成对n个节点的编码，并写出程序予以实现。 三、实验步骤及原理： 1、原理：Huffman算法的描述 (1)初始化，根据符号权重的大小按由大到小顺序对符号进行排序。 (2)把权重最小的两个符号组成一个节点， (3)重复步骤2，得到节点P2，P3，P4……，形成一棵树。 (4)从根节点开始顺着树枝到每个叶子分别写出每个符号的代码 2、实验步骤： 根据算法原理，设计程序流程，完成代码设计。 首先，用户先输入一个数n，以实现n个叶节点的Huffman 树； 之后，输入n个权值w[1]~w[n]，注意是unsigned int型数值； 然后，建立Huffman 树； 最后，完成Huffman编码。 四、实验代码：#include int min(HuffmanTree t,int i) { int j,flag; unsigned int k = MAX; for(j=1;j<=i;j++) if(t[j].parent==0&&t[j].weight VLOOKUP函数的使用方法（入门级）一、入门级 VLOOKUP是一个查找函数，给定一个查找的目标，它就能从指定的查找区域中查找返回想要查找到的值。它的基本语法为： VLOOKUP（查找目标，查找范围，返回值的列数，精确OR模糊查找) 下面以一个实例来介绍一下这四个参数的使用 例1：如下图所示，要求根据表二中的姓名，查找姓名所对应的年龄。 公式：B13 =VLOOKUP(A13,$B$2:$D$8,3,0) 参数说明： 1 查找目标：就是你指定的查找的内容或单元格引用。本例中表二A列的姓名就是查找目标。我们要根据表二的“姓名”在表一中A列进行查找。 公式：B13 =VLOOKUP(A13,$B$2:$D$8,3,0) 2 查找范围（VLOOKUP(A13,$B$2:$D$8,3,0) ）：指定了查找目标，如果没有说从哪里查找，EXCEL肯定会很为难。所以下一步我们就要指定从哪 个范围中进行查找。VLOOKUP的这第二个参数可以从一个单元格区域中查找， 也可以从一个常量数组或内存数组中查找。本例中要从表一中进行查找，那么范 围我们要怎么指定呢？这里也是极易出错的地方。大家一定要注意，给定的第二 个参数查找范围要符合以下条件才不会出错： A 查找目标一定要在该区域的第一列。本例中查找表二的姓名，那么姓名 所对应的表一的姓名列，那么表一的姓名列（列）一定要是查找区域的第一列。 象本例中，给定的区域要从第二列开始，即$B$2:$D$8，而不能是$A$2:$D$8。 因为查找的“姓名”不在$A$2:$D$8区域的第一列。 B 该区域中一定要包含要返回值所在的列，本例中要返回的值是年龄。年 龄列（表一的D列）一定要包括在这个范围内，即：$B$2:$D$8，如果写成$B $2:$C$8就是错的。 3 返回值的列数（B13 =VLOOKUP(A13,$B$2:$D$8,3,0)）。这是VLO OKUP第3个参数。它是一个整数值。它怎么得来的呢。它是“返回值”在第 二个参数给定的区域中的列数。本例中我们要返回的是“年龄”，它是第二个参 数查找范围$B$2:$D$8的第3列。这里一定要注意，列数不是在工作表中的列 数（不是第4列），而是在查找范围区域的第几列。如果本例中要是查找姓名所 交互式多模型算法卡尔曼滤波仿真 1 模型建立 分别以加速度u=0、1、2代表三个不同的运动模型 状态方程x(k+1)=a*x(k)+b*w(k)+d*u 观察方程z(k)=c*x(k)+v(k) 其中，a=[1 dt;0 1],b=[dt^2/2;dt],d=[dt^2/2;dt],c=[1 0] 2 程序代码 由两个功能函数组成，imm_main用来实现imm 算法，move_model1用来生成仿真数据，初始化运动参数 function imm_main %交互式多模型算法主程序 %初始化有关参数 move_model %调用运动模型初始化及仿真运动状态生成函数 load movedata %调入有关参数初始值（a b d c u position velocity pmeas dt tg q r x_hat p_var） p_tran=[0.8 0.1 0.1;0.2 0.7 0.1;0.1 0.2 0.7];%转移概率 p_pri=[0.1;0.6;0.3];%模型先验概率 n=1:2:5; %提取各模型方差矩阵 k=0; %记录仿真步数 like=[0;0;0];%视然函数 x_hat_hat=zeros(2,3);%三模型运动状态重初始化矩阵 u_=zeros(3,3);%混合概率矩阵 c_=[0;0;0];%三模型概率更新系数 %数据保存有关参数初始化 phat=[];%保存位置估值 vhat=[];%保存速度估值 xhat=[0;0];%融合和运动状态 z=0;%量测偏差（一维位置） pvar=zeros(2,2);%融合后估计方差 for t=0:dt:tg; %dt为为仿真步长；tg为仿真时间长度 k=k+1;%记录仿真步数 ct=0; %三模型概率更新系数 c_max=[0 0 0];%混合概率规范系数 p_var_hat=zeros(2,6);%方差估计重初始化矩阵, %[x_hat_hat p_var_hat]=model_reinitialization(p_tran,p_pri,x_hat,p_var);%调用重初始化函数，进行混合估计，生成三个模型重初始化后的运动状态、方差 %混合概率计算 for i=1:3 u_(i,:)=p_tran(i,:)*p_pri(i); end for i=1:3 c_max=c_max+u_(i,:); end 目 录 实验一用C/C++语言实现游程编码 实验二用C/C++语言实现算术编码 实验三用C/C++语言实现LZW编码 实验四用C/C++语言实现2D-DCT变换13 实验一用C/C++语言实现游程编码 1. 实验目的 1) 通过实验进一步掌握游程编码的原理； 2) 用C/C++语言实现游程编码。 2. 实验要求 给出数字字符，能正确输出编码。 3. 实验内容 现实中有许多这样的图像，在一幅图像中具有许多颜色相同的图块。在这些图块中，许多行上都具有相同的颜色，或者在一行上有许多连续的象素都具有相同的颜色值。在这种情况下就不需要存储每一个象素的颜色值，而仅仅存储一个象素的颜色值，以及具有相同颜色的象素数目就可以，或者存储一个象素的颜色值，以及具有相同颜色值的行数。这种压缩编码称为游程编码，常用(run length encoding，RLE)表示，具有相同颜色并且是连续的象素数目称为游程长度。 为了叙述方便，假定一幅灰度图像，第n行的象素值为： 用RLE编码方法得到的代码为：0@81@38@501@40@8。代码中用黑体表示的数字是游程长度，黑体字后面的数字代表象素的颜色值。例如黑体字50代表有连续50个象素具有相同的颜色值，它的颜色值是8。 对比RLE编码前后的代码数可以发现，在编码前要用73个代码表示这一行的数据，而编码后只要用11个代码表示代表原来的73个代码，压缩前后的数据量之比约为7:1，即压缩比为7:1。这说明RLE确实是一种压缩技术，而且这种编码技术相当直观，也非常经济。RLE所能获得的压缩比有多大，这主要是取决于图像本身的特点。如果图像中具有相同颜色的图像块越大，图像块数目越少，获得的压缩比就越高。反之，压缩比就越小。 译码时按照与编码时采用的相同规则进行，还原后得到的数据与压缩前的数据完全相同。因此，RLE是无损压缩技术。 VLOOKUP函数 使用举例 如图 vlookup函数示例 所示，我们要在A2:F12区域中提取100003、100004、100005、100007、100010五人的全年总计销量，并对应的输入到I4:I8中。一个一个的手动查找在数据量大的时候十分繁琐，因此这里使用VLOOKUP函数演示： 首先在I4单元格输入“=Vlookup(”，此时Excel就会提示4个参数。 Vlookup结果演示 第一个参数，很显然，我们要让100003对应的是I4，这里就输入“H4,” ； 第二个参数，这里输入我们要查找的区域(绝对引用)，即“$A$2:$F$12,”； 第三个参数，“全年总计”是区域的第六列，所以这里输入“6”，输入“5”就会输入第四季度的项目了； 第四个参数，因为我们要精确的查找工号，所以留空即可。 最后补全最后的右括号“)”，得到公式“=VLOOKUP(H4,$A$2:$F$12,6)”，使用填充柄填充其他单元格即可完成查找操作。 VLOOKUP函数使用注意事项 说到VLOOKUP函数，相信大家都会使用，而且都使用得很熟练了。不过，有几个细节问题，大家在使用时还是留心一下的好。 一．VLOOKUP的语法 VLOOKUP函数的完整语法是这样的： VLOOKUP(lookup_value,table_array,col_index_num,range_lookup) 1．括号里有四个参数，是必需的。最后一个参数range_lookup是个逻辑值，我们常常输入一个0字，或者False;其实也可以输入一个1字，或者true。两者有什么区别呢？前者表示的是完整寻找，找不到就传回错误值#N/A；后者先是找一模一样的，找不到再去找很接近的值，还找不到也只好传回错误值#N/A。这对我们其实也没有什么实际意义，只是满足好奇而已，有兴趣的朋友可以去体验体验。 2．Lookup_value是一个很重要的参数，它可以是数值、文字字符串、或参照地址。我们常常用的是参照地址。用这个参数时，有三点要特别提醒：A）参照地址的单元格格式类别与去搜寻的单元格格式的类别要一致，否则的话有时明明看到有资料，就是抓不过来。特别是参照地址的值是数字时，最为明显，若搜寻的单元格格式类别为文字，虽然看起来都是123，但是就是抓不出东西来的。VLOOKUP函数的使用方法(图解说明_很详细)
LZSS压缩算法实验报告
excel中的vlookup函数的使用方法及注意事项
多媒体数据压缩实验报告
VLOOKUP函数的使用方法(从入门到精通)
数据快速压缩算法的C语言实现
vlookup函数的使用方法实例
压缩编码算法设计与实现实验报告
VLOOKUP函数地使用方法
交互式多模型算法卡尔曼滤波仿真
数据压缩实验指导书
vlookup函数使用说明