A randomized solution to BGP divergence

The Border Gateway Protocol (BGP) is an interdomain routing protocol that allows each Autonomous System (AS) to define its own routing policies independently and use them to select the best routes. By means of policies, ASes are able to prevent some traffic from accessing their resources, or direct their traffic to a preferred route. However, this flexibility comes at the expense of a possibility of divergence behavior because of mutually conflicting policies. Since BGP is not guaranteed to converge even in the absence of network topology changes, it is not safe. In this paper, we propose a randomized approach to providing safety in BGP. The proposed algorithm dynamically detects policy conflicts, and tries to eliminate the conflict by changing the local preference of the paths involved. Both the detection and elimination of policy conflicts are performed locally, i.e. by using only local information. Randomization is introduced to prevent synchronous updates of the local preferences of the paths involved in the same conflict.

An Adaptive Policy Management Approach to BGP Convergence

The Border Gateway Protocol (BGP) is the current inter-domain routing protocol used to exchange reachability information between Autonomous Systems (ASes) in the Internet. BGP supports policy-based routing which allows each AS to independently adopt a set of local policies that specify which routes it accepts and advertises from/to other networks, as well as which route it prefers when more than one route becomes available. However, independently chosen local policies may cause global conflicts, which result in protocol divergence. In this paper, we propose a new algorithm, called Adaptive Policy Management Scheme (APMS), to resolve policy conflicts in a distributed manner. Akin to distributed feedback control systems, each AS independently classifies the state of the network as either conflict-free or potentially-conflicting by observing its local history only (namely, route flaps). Based on the degree of measured conflicts (policy conflict-avoidance vs. -control mode), each AS dynamically adjusts its own path preferences—increasing its preference for observably stable paths over flapping paths. APMS also includes a mechanism to distinguish route flaps due to topology changes, so as not to confuse them with those due to policy conflicts. A correctness and convergence analysis of APMS based on the substability property of chosen paths is presented. Implementation in the SSF network simulator is performed, and simulation results for different performance metrics are presented. The metrics capture the dynamic performance (in terms of instantaneous throughput, delay, routing load, etc.) of APMS and other competing solutions, thus exposing the often neglected aspects of performance.

Une architecture parallèle distribuée et tolérante aux pannes pour le protocole interdomaine BGP au cœur de l’Internet

L’augmentation du nombre d’usagers de l’Internet a entraîné une croissance exponentielle dans les tables de routage. Cette taille prévoit l’atteinte d’un million de préfixes dans les prochaines années. De même, les routeurs au cœur de l’Internet peuvent facilement atteindre plusieurs centaines de connexions BGP simultanées avec des routeurs voisins. Dans une architecture classique des routeurs, le protocole BGP s’exécute comme une entité unique au sein du routeur. Cette architecture comporte deux inconvénients majeurs : l’extensibilité (scalabilité) et la fiabilité. D’un côté, la scalabilité de BGP est mesurable en termes de nombre de connexions et aussi par la taille maximale de la table de routage que l’interface de contrôle puisse supporter. De l’autre côté, la fiabilité est un sujet critique dans les routeurs au cœur de l’Internet. Si l’instance BGP s’arrête, toutes les connexions seront perdues et le nouvel état de la table de routage sera propagé tout au long de l’Internet dans un délai de convergence non trivial. Malgré la haute fiabilité des routeurs au cœur de l’Internet, leur résilience aux pannes est augmentée considérablement et celle-ci est implantée dans la majorité des cas via une redondance passive qui peut limiter la scalabilité du routeur. Dans cette thèse, on traite les deux inconvénients en proposant une nouvelle approche distribuée de BGP pour augmenter sa scalabilité ainsi que sa fiabilité sans changer la sémantique du protocole. L’architecture distribuée de BGP proposée dans la première contribution est faite pour satisfaire les deux contraintes : scalabilité et fiabilité. Ceci est accompli en exploitant adéquatement le parallélisme et la distribution des modules de BGP sur plusieurs cartes de contrôle. Dans cette contribution, les fonctionnalités de BGP sont divisées selon le paradigme « maître-esclave » et le RIB (Routing Information Base) est dupliqué sur plusieurs cartes de contrôle. Dans la deuxième contribution, on traite la tolérance aux pannes dans l’architecture élaborée dans la première contribution en proposant un mécanisme qui augmente la fiabilité. De plus, nous prouvons analytiquement dans cette contribution qu’en adoptant une telle architecture distribuée, la disponibilité de BGP sera augmentée considérablement versus une architecture monolithique. Dans la troisième contribution, on propose une méthode de partitionnement de la table de routage que nous avons appelé DRTP pour diviser la table de BGP sur plusieurs cartes de contrôle. Cette contribution vise à augmenter la scalabilité de la table de routage et la parallélisation de l’algorithme de recherche (Best Match Prefix) en partitionnant la table de routage sur plusieurs nœuds physiquement distribués.

An operational approach to validate the path of BGP

BGP (Border Gateway Protocol) is a fundamental component of the current Internet infrastructure. However, BGP is vulnerable to a variety of attacks, since it cannot ensure the authenticity of the path attributes announced by BGP routers. Despite several solutions have been proposed to address this vulnerability, none of them is operational in real-world due to their immense impact on original BGP. In this paper, we propose a Deployable Path Validation Authentication scheme, which can effectively validate the path of BGP. Through analysis and simulation we show that this scheme has little impact on the performance and memory usage for the original BGP, and can be adopted in practice as an operational approach.

Purification, biochemical characterization and localization at single cell resolution of Matrix Gla Protein (MGP) and Bone Gla Protein (BGP) in the teleost fish Argyrosomus regius

Tese de dout. em Química, Faculdade de Ciências do Mar e do Ambiente, Univ. do Algarve, 2002

Serum bone formation marker correlation with improved osseointegration in osteoporotic rats treated with simvastatin

Objective: Simvastatin has been shown to enhance osseointegration of pure titanium implants in osteoporotic rats. This study aimed to evaluate the relationship between the serum level of bone formation markers and the osseointegration of pure titanium implants in osteoporotic rats treated with simvastatin. Materials and methods: Fifty-four female Sprague Dawley rats, aged 3 months old, were randomly divided into three groups: Sham-operated group (SHAM; n=18), ovariectomized group (OVX; n=18), and ovariectomized with Simvastatin treatment group (OVX+SIM; n=18). Fifty-six days after ovariectomy, screw-shaped titanium implants were inserted into the tibiae. Simvastatin was administered orally at 5mg/kg each day after the placement of the implant in the OVX+SIM group. The animals were sacrificed at either 28 or 84 days after implantation and the undecalcified tissue sections were processed for histological analysis. Total alkaline phosphatase (ALP), bone specific alkaline phosphatase (BALP) and bone Gla protein (BGP) were measured in all animal sera collected at the time of euthanasia and correlated with the histological assessment of osseointegration. Results: The level of ALP in the OVX group was higher than the SHAM group at day 28, with no differences between the three groups at day 84. The level of BALP in the OVX+SIM group was significantly higher than both OVX and SHAM groups at days 28 and 84. Compared with day 28, the BALP level of all three groups showed a significant decrease at day 84. There were no significant differences in BGP levels between the three groups at day 28, but at day 84 the OVX+SIM group showed significantly higher levels than both the OVX and SHAM groups. There was a significant increase in BGP levels between days 28 and 84 in the OVX+SIM group. The serum bone marker levels correlated with the histological assessment showing reduced osseointegration in the OVX compared to the SHAM group which is subsequently reversed in the OVX+SIM group.

On the Size Distribution of Autonomous Systems

This paper explores reasons for the high degree of variability in the sizes of ASes that have recently been observed, and the processes by which this variable distribution develops. AS size distribution is important for a number of reasons. First, when modeling network topologies, an AS size distribution assists in labeling routers with an associated AS. Second, AS size has been found to be positively correlated with the degree of the AS (number of peering links), so understanding the distribution of AS sizes has implications for AS connectivity properties. Our model accounts for AS births, growth, and mergers. We analyze two models: one incorporates only the growth of hosts and ASes, and a second extends that model to include mergers of ASes. We show analytically that, given reasonable assumptions about the nature of mergers, the resulting size distribution exhibits a power law tail with the exponent independent of the details of the merging process. We estimate parameters of the models from measurements obtained from Internet registries and from BGP tables. We then compare the models solutions to empirical AS size distribution taken from Mercator and Skitter datasets, and find that the simple growth-based model yields general agreement with empirical data. Our analysis of the model in which mergers occur in a manner independent of the size of the merging ASes suggests that more detailed analysis of merger processes is needed.

On the Stable Paths Problem and a Restricted Variant

Interdomain routing on the Internet is performed using route preference policies specified independently, and arbitrarily by each Autonomous System in the network. These policies are used in the border gateway protocol (BGP) by each AS when selecting next-hop choices for routes to each destination. Conflicts between policies used by different ASs can lead to routing instabilities that, potentially, cannot be resolved no matter how long BGP is run. The Stable Paths Problem (SPP) is an abstract graph theoretic model of the problem of selecting nexthop routes for a destination. A stable solution to the problem is a set of next-hop choices, one for each AS, that is compatible with the policies of each AS. In a stable solution each AS has selected its best next-hop given that the next-hop choices of all neighbors are fixed. BGP can be viewed as a distributed algorithm for solving SPP. In this report we consider the stable paths problem, as well as a family of restricted variants of the stable paths problem, which we call F stable paths problems. We show that two very simple variants of the stable paths problem are also NP-complete. In addition we show that for networks with a DAG topology, there is an efficient centralized algorithm to solve the stable paths problem, and that BGP always efficiently converges to a stable solution on such networks.

An Adaptive Management Approach to Resolving Policy Conflicts

The Border Gateway Protocol (BGP) is the current inter-domain routing protocol used to exchange reachability information between Autonomous Systems (ASes) in the Internet. BGP supports policy-based routing which allows each AS to independently define a set of local policies on which routes it accepts and advertises from/to other networks, as well as on which route it prefers when more than one route becomes available. However, independently chosen local policies may cause global conflicts, which result in protocol divergence. In this paper, we propose a new algorithm, called Adaptive Policy Management Scheme(APMS), to resolve policy conflicts in a distributed manner. Akin to distributed feedback control systems, each AS independently classifies the state of the network as either conflict-free or potentially conflicting by observing its local history only (namely, route flaps). Based on the degree of measured conflicts, each AS dynamically adjusts its own path preferences---increasing its preference for observably stable paths over flapping paths. APMS also includes a mechanism to distinguish route flaps due to topology changes, so as not to confuse them with those due to policy conflicts. A correctness and convergence analysis of APMS based on the sub-stability property of chosen paths is presented. Implementation in the SSF network simulator is performed, and simulation results for different performance metrics are presented. The metrics capture the dynamic performance (in terms of instantaneous throughput, delay, etc.) of APMS and other competing solutions, thus exposing the often neglected aspects of performance.

Evolution of matrix and bone gamma-carboxyglutamic acid proteins in vertebrates

The evolution of calcified tissues is a defining feature in vertebrate evolution. Investigating the evolution of proteins involved in tissue calcification should help elucidate how calcified tissues have evolved. The purpose of this study was to collect and compare sequences of matrix and bone γ-carboxyglutamic acid proteins (MGP and BGP, respectively) to identify common features and determine the evolutionary relationship between MGP and BGP. Thirteen cDNAs and genes were cloned using standard methods or reconstructed through the use of comparative genomics and data mining. These sequences were compared with available annotated sequences (a total of 48 complete or nearly complete sequences, 28 BGPs and 20 MGPs) have been identified across 32 different species (representing most classes of vertebrates), and evolutionarily conserved features in both MGP and BGP were analyzed using bioinformatic tools and the Tree-Puzzle software. We propose that: 1) MGP and BGP genes originated from two genome duplications that occurred around 500 and 400 million years ago before jawless and jawed fish evolved, respectively; 2) MGP appeared first concomitantly with the emergence of cartilaginous structures, and BGP appeared thereafter along with bony structures; and 3) BGP derives from MGP. We also propose a highly specific pattern definition for the Gla domain of BGP and MGP. Previous Section Next Section BGP1 (bone Gla protein or osteocalcin) and MGP (matrix Gla protein) belong to the growing family of vitamin K-dependent (VKD) proteins, the members of which are involved in a broad range of biological functions such as skeletogenesis and bone maintenance (BGP and MGP), hemostasis (prothrombin, clotting factors VII, IX, and X, and proteins C, S, and Z), growth control (gas6), and potentially signal transduction (proline-rich Gla proteins 1 and 2). VKD proteins are characterized by the presence of several Gla residues resulting from the post-translational vitamin K-dependent γ-carboxylation of specific glutamates, through which they can bind to calcium-containing mineral such as hydroxyapatite. To date, VKD proteins have only been clearly identified in vertebrates (1) although the presence of a γ-glutamyl carboxylase has been reported in the fruit fly Drosophila melanogaster (2) and in marine snails belonging to the genus Conus (3). Gla residues have also been found in neuropeptides from Conus venoms (4), suggesting a wider prevalence of γ-carboxylation.

Cloning of the Bone Gla Protein gene from the teleost fish Sparus aurata (gilthead seabream). Molecular organization, developmental appearance and evolutionary implications

Tese de Doutoramento, Biologia Molecular, Faculdade de Ciências do Mar e do Ambiente, Universidade do Algarve, 2001

Effects of vitamin K deficiency and its mechanisms in vertebrate's early development: zebrafish as a model

Disertação de mestrado, Ciências Biomédicas, Departamento de Ciências Biomédicas e Medicina, Universidade do Algarve, 2015

HSP72 preserves muscle function and slows progression of severe muscular dystrophy

Duchenne muscular dystrophy (DMD) is a severe and progressive muscle wasting disorder caused by mutations in the dystrophin gene that result in the absence of the membrane-stabilizing protein dystrophin¹, ², ³. Dystrophin-deficient muscle fibres are fragile and susceptible to an influx of Ca²⁺, which activates inflammatory and muscle degenerative pathways⁴, ⁵, ⁶. At present there is no cure for DMD, and existing therapies are ineffective. Here we show that increasing the expression of intramuscular heat shock protein 72 (Hsp72) preserves muscle strength and ameliorates the dystrophic pathology in two mouse models of muscular dystrophy. Treatment with BGP-15 (a pharmacological inducer of Hsp72 currently in clinical trials for diabetes) improved muscle architecture, strength and contractile function in severely affected diaphragm muscles in mdx dystrophic mice. In dko mice, a phenocopy of DMD that results in severe spinal curvature (kyphosis), muscle weakness and premature death⁷, ⁸, BGP-15 decreased kyphosis, improved the dystrophic pathophysiology in limb and diaphragm muscles and extended lifespan. We found that the sarcoplasmic/endoplasmic reticulum Ca²⁺-ATPase (SERCA, the main protein responsible for the removal of intracellular Ca²⁺) is dysfunctional in severely affected muscles of mdx and dko mice, and that Hsp72 interacts with SERCA to preserve its function under conditions of stress, ultimately contributing to the decreased muscle degeneration seen with Hsp72 upregulation. Treatment with BGP-15 similarly increased SERCA activity in dystrophic skeletal muscles. Our results provide evidence that increasing the expression of Hsp72 in muscle (through the administration of BGP-15) has significant therapeutic potential for DMD and related conditions, either as a self-contained therapy or as an adjuvant with other potential treatments, including gene, cell and pharmacological therapies.

Preparation and thermal characterization of inclusion complex of Brazilian green propolis and hydroxypropyl-beta-cyclodextrin

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)