Repositório Colecção:
http://hdl.handle.net/10198/2984
2015-09-04T03:50:30ZPerformance analysis of algorithms for calculation of SRLG disjoint paths of min-sum cost in GMPLS networks
http://hdl.handle.net/10198/10643
Título: Performance analysis of algorithms for calculation of SRLG disjoint paths of min-sum cost in GMPLS networks
Autor: Gomes, Teresa; Soares, Miguel; Craveirinha, José; Melo, Paulo; Jorge, Luísa; Mirones, Vítor; Brizído, André
Resumo: Ensuring the resilience of telecommunications networks is an ongoing concern of telecommunications operators. In a Generalized Multiprotocol Label Switching (GMPLS) [4], network information about sets of links that share risks of failure, called Shared Risk Link Groups (SRLG), can be distributed [3]. This information allows Path Computation Elements (PCE) [1] to determine protected routes, i.e. compute a pair (or set) of SRLG-disjoint paths. A PCE must respond quickly to requests without requiring too many resources. This shows the importance of developing efficient algorithms for determining the SRLG disjoint paths.
Firstly, a new version of Conflicting SRLG-Exclusion Min Sum (CoSE-MS) heuristic [2,5] which seeks to determine a pair of SRLG-disjoint paths with minimum additive cost, adequate for dedicated global protection in GMPLS networks, will be described. The new version, designated CoSE-MScd, uses an improved version (designated MSHd) of the Modified Suurballe's Heuristic (MSH) proposed in [6] and modifies the process of selection of the
conflicting SRLGs used in [2]. The Iterative Modified Suurballes's Heuristic (IMSH) [6] and the new variant IMSHd, which results from the replacement of MSH by MSHd in IMSH, will also be presented. Secondly, the heuristics kCoSE-MScd and kIMSHd are proposed. To the best of our knowledge these procedures are a first proposal for seeking a set of k (k > 2) node and SRLG disjoint paths of minimal additive cost; these heuristics use a generalization of MSH for obtaining a set of k node and SRLG disjoint paths, which we designate as kMSH.
The two heuristics have a similar structure, but the first uses CoSE-MScd to collect a set of node and SRLG disjoint path pairs and the second uses IMSHd for that same purpose.
The network used for evaluating the heuristics' performance was the largest biconnected component of an image of a real network with 231 nodes and 471 edges. Ten different random seeds where used to generate different distributions of SRLGs for that component, resulting in 10 different networks (with the same topology). The accuracy of the solutions obtained by the heuristics was evaluated solving an ILP formulation of the problem, using CPLEX 12.3 on a Desktop.
Experimental results in an embedded system (core clock 330MHz, 128 MB RAM), showed that CoSE-MScd is more efficient than CoSE-MS, without compromising its accuracy. IMSHd is more accurate than IMSH (for the same number of iterations) at the cost of more CPU time. The experimental results obtained using kIMSH and kCoSE-MScd show that although both heuristics are quite effective in calculating a set of k = 3; 4 node and SRLG disjoint paths, however only 55%-59% of the sets of size k = 3 have optimal cost, and this value decreases for k = 4. The relative error of the total cost of the sub-optimal paths sets is about 7.5% for k = 3 and close to 15% for k = 4. Nevertheless given the great difficulty in obtaining optimal sets of node and SRLG disjoint paths, these proposals and results seem relevant in this area.2012-01-01T00:00:00ZAdopting an opensource integrated library system in academic libraries: experiences so far with Koha and RFID at Polytechnic Institute of Bragança
http://hdl.handle.net/10198/9260
Título: Adopting an opensource integrated library system in academic libraries: experiences so far with Koha and RFID at Polytechnic Institute of Bragança
Autor: Alves, Paulo; Reais, António; Alves, Evandro
Resumo: Open source has a major role in several applications in education, government and business. In higher
education the adoption of open source software in Library management is not so common as in virtual
learning environments, content management systems and portals. Even considering the fact that open
source Integrated Library Systems are in the market for a long time, there are several barriers that
libraries are facing when considering the adoption of open source. This paper highlights the advantages
of adopting an open source Library Management System and describes the migration process from a
commercial system to Koha and the integration of RFID for books circulation and user identification.2012-01-01T00:00:00ZAn effective algorithm for obtaining the set of all minimal cost pairs of disjoint paths with dual arc costs
http://hdl.handle.net/10198/7498
Título: An effective algorithm for obtaining the set of all minimal cost pairs of disjoint paths with dual arc costs
Autor: Gomes, Teresa; Craveirinha, José; Jorge, Luísa
Resumo: In today’s telecommunications networks it is necessary, for reliability reasons, to use protection schemes involving the calculation of two (or more) disjoint paths for each node-to-node connection, especially when large amounts of traffic have to be routed in the network. This concern is
particularly relevant in optical networks, namely WDM (Wavelength Division Multiplexing) networks due to the very high rates supported by lightpaths, and in the Internet using MPLS (Multiprotocol
Label Switching). In this context the problem of obtaining optimal (arc or node) disjoint paths, for increasing network reliability while minimising bandwidth consumption, is extremely important.
The problem of finding k disjoint paths from s to t (two distinct nodes), in a network with k different costs on every arc such that the total cost of the paths is minimised is NP-complete even for k = 2,
when the relationship between the k arc costs (in the same arc) is arbitrary. When k = 2 these networks are usually designated as dual arc cost networks.
In this paper we propose an exact algorithm for finding the whole set of arc-disjoint path pairs, with minimal cost in a network with dual arc costs. The addressed problem can be formalised as follows.
Let G = (V,E) be a directed network with node set V = {v1, v2, . . . , vn} and and arc set E =
{e1, e2, . . . , em} (were n and m designate the number of nodes and arcs in G, respectively), where
two different non-negative cost functions (or metrics) in the arcs, are defined:
η(j) : E → IN0 (j = 1, 2) (1)
η(j)((va, vb)) = c(j)
vavb (va, vb) ∈ E (2)
The cost C(j) of a (loopless) path p in G with respect to metric η(j), is:
C(j)(p) =
X
(va,vb)∈p
c(j)
vavb (j = 1, 2) (3)
Let path p, p = hv1, e1, v2, . . . , vi−1, ei−1, vii, be given as an alternate sequence of nodes and arcs
from G, such that the tail of ek is vk and the head of ek is vk+1, for k = 1, 2, . . . , i − 1 (all the vi in
p are different). Let the set of nodes in p be V ∗(p) and the set of arcs in p be E∗(p). Two paths
p = hv1, e1, v2, . . . , vi−1, ei−1, vii and q are arc-disjoint if E∗(p) ∩ E∗(q) = ∅. Two paths p and q are
disjoint if V ∗(p) ∩ V ∗(q) = ∅, and are internally disjoint if {v2, . . . , vi−1} ∩ V ∗(q) = ∅. We will say that
two paths are node disjoint if they are internally disjoint.
The addressed problem is to find the whole set of pairs (p, q) of arc disjoint paths which minimise the
total cost of the pair, defined by:
C[(p, q)] = C(1)(p) + C(2)(q) (4)
where p and q have the same source and sink node.
An exact algorithm for solving this NP-complete problem will be proposed, based on a condition which
guarantees that the optimal path pair cost has been obtained. This optimality condition is based on
the calculation of increasingly tightened upper and lower bounds on the optimal cost. A formal proof
of the correctness of the algorithm is described. Extensive experimentation is presented to show the
effectiveness of the algorithm.
It will also be explained how the proposed approach can also be used for obtaining the minimal cost
disjoint path pair with constraints on the maximum number of arcs allowed per path, a problem of interest in various applications, namely in telecommunication networks.2008-01-01T00:00:00ZMulti-scheme recovery in MPLS networks: preliminary results for a multischeme approach
http://hdl.handle.net/10198/7494
Título: Multi-scheme recovery in MPLS networks: preliminary results for a multischeme approach
Autor: Jorge, Luísa; Gomes, Teresa
Resumo: MultiProtocol Label Switching (MPLS) networks have been proposed as a solution to offer reliable, efficient and differentiated telecommunication services. Nowadays several applications require high quality service and cannot recover from traffic loss using retransmissions. Routing protocols can be robust and survivable but take a long time to recover from faults, which will not be acceptable for many applications. Therefore several schemes and frameworks for MPLS recovery have been proposed to handle failures quickly [3].
The authors proposed [2] a multi-scheme recovery approach, which intends to increase overall network resilience, while using network resources efficiently by taking into account resilience requirements of different class types. This approach tries to offer protection to a set of services by choosing the most appropriate recovery scheme, taking into account the service class, the network state, and the characteristics of available recovery schemes. The appropriate recovery scheme [3] will therefore be chosen based on a combination of quantitative measures and qualitative classification.
The proposed recovery multi-scheme tries to ensure support for strict QoS guarantees, for different DiffServ classes [1], including in failure conditions. Bandwidth reservation (including, if required, pre-reservation) is carried out on a per-Diffserv class basis not just to the normal case but also in failure situations while trying to optimize the use of network resources. This work presents preliminary performance results from a study of the proposed multi-scheme.
References
[1] Faucheur, F. L. & Lai, W., 2003. Requirements for support of differentiated services aware MPLS traffic engineering. IETF RFC 3564.
[2] Jorge, L. M. G.& Gomes, T. M., "Multi-scheme recovery in MPLS networks", C.Guedes Soares & E. Zio (editores), Safety and Reliability for Managing Risk, Volume 3, Taylor & Francis (Balkema), Actas do congresso ESREL 2006, Estoril, 18-22 de Setembro
de 2006, pág. 2263-2271, 2006.
[3] Jorge, L. M. G.& Gomes, T. M., Luísa Maria Garcia Jorge, Teresa Martinez Gomes, "Survey of Recovery Schemes in MPLS Networks", W. Zamojski, J. Mazurkiewicz, J. Sugier e T. Walkowiak (editores), DepCoS - RELCOMEX 2006, Dependability of Computer Systems, 25-27 de Maio de 2006, Szklarska Poreba, Polónia. pág. 110-118, 20062009-01-01T00:00:00Z