Publications

This is a list of our recent publications. For a list organized per topic, please see the Projects page and, for a comprehensive list, with older publications, please visit DBLP, Google Scholar, or Microsoft Academic Search.

• 2019
  • Byzantine Collision-Fast Consensus Protocols
    • Rodrigo Saramago, Eduardo Alchieri, Tuanir Rezende, Lasaro Camargos
    • Transactions on Computational Collective Intelligence XXXIII
    • Atomic broadcast protocols are fundamental building blocks used in the construction of many reliable distributed systems. Atomic broadcast and consensus are equivalent problems, but the inefficiency of consensus-based atomic broadcast protocols in the presence of collisions (concurrent proposals) harms their adoption in the implementation of reliable systems, as the ones based on state machine replication. In the traditional consensus protocols, proposals that are not decided in some instance of consensus (commands not delivered) must be re-proposed in a new instance, delaying their execution. Moreover, whether different values (commands) are proposed in the same instance (leading to a collision), some of its phases must be restarted, also delaying the execution of these commands involved in the collision. The CFABCast (Collision-Fast Atomic Broadcast) algorithm uses m-consensus to decide …
• 2018
  • A game theoretical approach to model the channel selection dynamics in non-coordinated IEEE 802.11 networks
    • Sérgio L. D. L. Gramacho, Gustavo B. Figueiredo, Lasaro Camargos
    • Wireless Networks
    • The massive deployment of Wireless Local Area Networks has made interference mitigation between neighboring networks a challenging issue. These uncoordinated access networks aim at improving their operation by choosing the best wireless channel available, characterizing a competition over the restricted set of possible channels. This work analyses this competition using Game Theory and Markov Chains models, showing that such competitive behavior can lead to Nash Equilibria and that outcomes mostly will not be maximal. Additionally, partially and fully cooperative models are proposed and evaluated, allowing (a) individual players to increase global results using arbitrarily computed and non-rational moves, and (b) achieving maximal outcomes when considering the cooperation of up to all players.
    • [Paper]
  • Automated Diagnostic of Virtualized Service Performance Degradation
    • AHMED, J.; JOSEFSSON, T.; JOHNSSON, A.; FLINTA, C.; MORADI, F.; PASQUINI, R.; STADLER, R.
    • NOMS 2018 - 2018 IEEE/IFIP Network Operations and Management Symposium, 2018, Taipei, Taiwan.
  • NECOS Project: Towards Lightweight Slicing of Cloud Federated Infrastructures
    • SILVA, F. S. D.; LEMOS, M. O. O.; MEDEIROS, A.; NETO, A. J. V.; PASQUINI, R.; MOURA, D.; ESTEVE, C.; MAMATAS, L.; CORREA, S. L.; CARDOSO, K. V.; MARCONDES, C. A. C.; ABELEM, A. J. G.; NASCIMENTO, M. R.; GALIS, A.; CONTRERAS, L.; SERRAT, J.; PAPADIMITRIOU, P.
    • IEEE Netsoft 2018 - S4SI, 2018, Montreal, Canada
  • Comutador P4 com Suporte a Roteamento Multicaminhos
    • Lucas B. Fernandes, Pedro H. Ribeiro, Leonardo Martins, Rafael Pasquini, Luis F. Faina, Lasaro Camargos
    • WPEIF 2018
    • In this paper we describe a network switch with multi-path routing capabilities. The switch is implemented using P4, easily extensible and available as a free software project. The switch supports different routing policies, which adhere to different levels of QoS, making the network use very flexible.
    • [Paper]
  • On the Impossibility of Byzantine Collision-Fast Atomic Broadcast
    • Rodrigo Q. Saramago, Eduardo A. P. Alchieri, Tuanir F. Rezende, Lasaro Camargos
    • AINA 2017, May 2018
    • The inefficiency of Consensus-based Atomic Broadcast protocols in the presence of collisions (concurrent proposals) harms their adoption in the implementation of State Machine Replication. Proposals that are not decided in some instance of Consensus (commands not delivered) must be re-proposed in a new instance, delaying their execution. The CFABCast (\textit{Collision-Fast Atomic Broadcast}) algorithm uses M-Consensus to decide and deliver multiple values in the same instance. However, CFABCast is not Byzantine fault-tolerant, a requirement for many systems. Our first contribution is a modified version of CFABCast to handle Byzantine failures. Unfortunately, the resulting protocol is not collision-fast due to the possibility of malicious failures. In fact, our second contribution is to prove that there are no Byzantine collision-fast algorithms in an asynchronous model as traditionally extended to solve Consensus. \todo{... asynchronous model, even if extended with Unreliable Failure Detectors} Finally, our third contribution is a Byzantine collision-fast algorithm that bypasses the stated impossibility by means of a USIG (Unique Sequential Identifier Generator) trusted component.
  • Analysis of monitoring and multipath support on top of OpenFlow specification
    • Pedro H. A. Rezende, Paulo R. S. L. Coelho, Luis F. Faina, Lasaro Camargos
    • International Journal of Network Management
    • In general, traffic is pushed through a single path despite the existence of alternative paths in networks. For example, routing solutions based on spanning tree prune the topology to prevent loops, consequently preventing also the use of alternative paths. Research on quality of service frequently advocates that the use of alternative paths is interesting for enforcing Service Level Agreements (SLAs), bypassing bottlenecks created by shortest paths. In this paper, we are interested in analyzing the support for monitoring network traffic and for provisioning of multipaths in software-defined networking (SDN), given the strong platform it provides for experimentation of new networked solutions. Our approach firstly enriches the topology view at the control plane with data gathered through fine grain data plane monitoring. On the basis of such enriched view, our system determines the path, or multipaths, necessary to enforce the specified SLA. We propose 2 extension modules to an OpenFlow controller: SDNMon, which monitors the data plane to enrich the topology information at the control plane, and MP-Routing, which determines a set of paths, in the absence of a single path capable of enforcing the SLA. Both modules are extensively evaluated, and the results not only demonstrate what can be achieved in terms of accuracy in SDNMon and in terms of quality of service benefits in MP-Routing but also highlight some limitations of OpenFlow specification. On the basis of our findings, we propose a set of new counters to Per Port and Per Flow granularity levels of OpenFlow specification.
  • Learning from Network Device Statistics
    • Rolf Stadler, Rafael Pasquini, Viktoria Fodor
    • Journal of Network and Systems Management
    • We estimate end-to-end service metrics from network device statistics. Our approach is based upon statistical, supervised learning, whereby the mapping from device-level to service-level metrics is learned from observations, i.e., through monitoring the system. The approach enables end-to-end performance prediction without requiring an explicit model of the system, which is different from traditional engineering techniques that use stochastic modeling and simulation. The fact that end-to-end service metrics can be estimated from local network statistics with good accuracy in the scenarios we consider suggeststhat service-level properties are “encoded” in network-level statistics. We show that the set of network statistics needed for estimation can be reduced to a set of measurements along the network path between client and service backend, with little loss in estimation accuracy. The reported work is largely experimental and its results have been obtained through testbed measurements from a video streaming service and a KV store over an OpenFlow network.
• 2017
  • Algoritmo de Difusão Atômica Rápido à Despeito de Colisões Tolerante a Falhas Bizantinas
    • Rodrigo Q. Saramago, Eduardo Alchieri, Tuanir F. Rezende, Lasaro Camargos
    • SBRC 2017, May 2017
    • O uso de protocolos de Difusão Atômica baseados em Consenso na implementação de Máquinas de Estados Replicadas esbarra na ineficiência destes protocolos na presença de colisões, isto é, propostas simultâneas. Isso porquê propostas não decididas no Consenso (comandos não entregues) devem ser repropostas em novas instâncias, aumentando seu tempo de entrega e atrasando sua execução. O algoritmo CFABCast (Collision-Fast Atomic Broadcast) utiliza uma variante do Consenso, o M-Consenso, para decidir e entregar múltiplos valores por instância. CFABCast, contudo, não tolera falhas bizantinas, requisito importante em diversos cenários. Como primeira contribuição deste artigo, propomos uma versão modificada do CFABCast que tolera falhas bizantinas. Apesar de ser baseado em um algoritmo rápido à despeito de falhas, nosso algoritmo não é rápido ante a possibilidade de falhas bizantinas. De fato, nossa segunda contribuição é a conjectura de que nenhum algoritmo possa sê-lo no modelo assíncrono. Finalmente, nossa terceira contribuição é a proposta de um algoritmo que é rápido à despeito de falhas bizantinas, contornando a impossibilidade pela extensão do modelo computacional com o componente seguro USIG (Unique Sequential Identifier Generator).
  • DSVis: Ferramenta para Edição e Visualização de Rastros de Execução de Sistemas Distribuídos
    • Tulio Barbosa, Daniel Naves, Luis Faina, Lasaro Camargos
    • Salão de Ferramentas, SBRC 2017, May 2017
  • On Making Generalized Paxos Practical
    • Tuanir F. Rezende, Pierre Sutra, Rodrigo Q. Saramago, Lasaro Camargos
    • AINA 2017, March 2017
    • Generalized Paxos (GPaxos) is a recent solution for Generalized Consensus, a distributed problem to which several key agreement problems reduce. We envision that GPaxos may unify within a single and novel Agreement-as-a-Service infrastructure multiple distributed protocols. To date this potential is however not fully unleashed, due to the steep learning curve of the protocol and the high complexity of its implementation. Moreover, before GPaxos reaches a real world usage, several computationally expensive operations have to be optimized and simplified. This paper aims at closing this gap between theory and practice. To this end, we first provide a concise tour of Generalized Paxos, hardly found elsewhere. Then, we assess the versatility of the Generalized Consensus problem by presenting a variation of GPaxos that solves the lease coordination problem. Our last contribution consists in three optimizations that apply to the critical phases of the algorithm: i)a method to quickly start a new round, ii)a novel approach to execute a checkpoint, and, iii)a data structure that speeds-up the agreement detection.
    • [Paper]
• 2016
  • XOR-Based Routing Protocols in Vehicular Ad Hoc Networks: How Well Do They Perform?
    • Rodolfo Oliveira, Rafael Pasquini, Miguel Luis, Luis Bernardo
    • Wireless Personal Communications, October 2016
    • This paper presents a performance analysis of exclusive-or logical operator (XOR)-based flat routing protocols in high mobility conditions, considering a vehicular ad hoc network (VANET) formed in a highway scenario. The main advantage of XOR-based routing is related to their logarithmic requirement of information per node in order to perform traffic forwarding, providing the basis to achieve better scalability levels for the routing mechanism convergence. First, this paper describes a protocol that incorporates several adaptations of the existing XOR-based routing algorithms for wired networks, in order to cope with the network mobility. Then it is proposed an improved version of it, XORi, which modifies the protocol’s information gathering process to accommodate the specific dynamic nature of VANETs topology in highways. Finally, the performance of XOR-based protocols is compared with other topology-based and position-based routing protocols. Simulation results allow us to characterize the performance of this class of protocols through the comparison of the path availability, end-to-end path delay, average path length and path duration. When a moderate density of nodes is considered, simulations show that XOR-based algorithms achieve almost the same path availability rate as link state algorithms, such as OLSR, and for high density of nodes, XOR-based algorithms scale better in terms of delay when compared to source routing algorithms, such as DSR.
    • [Paper]
  • Replicação de Máquina de Estado Baseada em Prioridade com PRaft
    • Paulo Pinho, Luciana Rech, Lau Cheuk Lung, Miguel Correia, Lasaro Camargos
    • XXXIV Simpósio Brasileiro de Redes de Computadores e Sistemas Distribuídos (SBRC-2016).
    • Replicação de máquina de estado é uma abordagem para criar serviços distribuídos tolerantes a faltas. O sistema se mantém correto enquanto tolera a falta de algumas de suas réplicas. Essas réplicas devem executar a mesma sequência de requisições, problema que é resolvido por algoritmos de ordem total como o Raft. Alguns serviços podem precisar que as requisições tenha diferentes níveis de prioridade, para que umas sejam executadas antes de outras. Neste trabalho propõe-se um algoritmo, PRaft, que introduz a ideia de replicação de máquina de estado baseado em prioridades ao Raft, modificando-o para considerar a prioridades das requisições
    • [Paper]
  • Roteamento Multicaminhos em Redes Definidas por Software
    • Pedro H.A. Rezende, Luís F. Faina, Lásaro Camargos e Rafael Pasquini
    • XXXIV Simpósio Brasileiro de Redes de Computadores e Sistemas Distribuídos (SBRC-2016).
    • Este artigo apresenta e avalia um mecanismo para suportar roteamento multicaminhos em Redes Definidas por Software (SDN) OpenFlow. Utilizando informações do monitoramento de vazão e atraso para fluxos, tendo por base consultas explícitas a contadores OpenFlow mantidos nos elementos derede, o modulo proposto de multicaminhos é capaz de ramificar fluxos na rede, de tal forma a atender demandas de largura de banda. O mecanismo multicaminhos proposto, diferentemente do MPTCP (MultiPath TCP), não requer nenhuma atualização na pilha de protocolos existente nos sistemas finais. Por ser uma solução desenvolvida diretamente no controlador OpenFlow, é capaz de tratar qualquer fluxo utilizando a rede. Os resultados apresentados neste artigo demonstram o funcionamento do mecanismo de multicaminhos, evidenciando o comportamento da solução frente a existência ou não de tráfego concorrente através dos enlaces compondo a rede.
    • [Paper]
  • An Architecture for Traffic Sign Management in Smart Cities
    • Everton R. Lira, Enrique Fynn, Paulo R. S. L. Coelho, Luis F. Faina, Lasaro J. Camargos, Rodolfo S. Villaça and Rafael Pasquini.
    • The 30-th IEEE International Conference on Advanced Information Networking and Applications (AINA-2016).
    • This paper introduces and evaluates a Traffic Sign Management Architecture (TSMA), which represents a paradigm shift for the deployment of traffic sign infrastructure in the context of Intelligent Transport Systems, Vehicular Networks and Smart Cities. The proposal addresses limitations of the current traffic control model by enabling remote updates of traffic signs and displaying them on the vehicular navigation system display to improve their legibility. TSMA is an architecture developed to provide V2I interaction using a commodity technology, Wi-Fi, through the beacon-stuffing technique. The initial design of TSMA’s security mechanisms is also presented in this paper. Evaluations were performed on a developed prototype and simulation environments.
    • [Paper]
  • An Architecture for Monitoring and Improving Public Transportation Systems
    • Pedro H. S. Duarte, Luis F. Faina, Lasaro J. Camargos, Luciano B. de Paula and Rafael Pasquini.
    • The 30-th IEEE International Conference on Advanced Information Networking and Applications (AINA-2016).
    • Brazilian public transportation systems are facing a significant demand reduction, mainly due to the poor quality of the offered services, lack of information regarding lines and timetables, high cost and lack of investment from the government. Even though it is not trivial to improve financial aspects related to the public transportation system, this work claims that the overall system quality can be improved through ubiquitous data collection according to a proposed ontology, which is the basis for knowledge extraction to support the required quality of experience improvements. The proposed architecture relies on standard technologies available nowadays, providing a low cost solution for the required data collection and analysis. This paper presents the proposed inter-networking architecture and ontology, then evaluates the system performance using a prototype developed with standard solutions.
    • [Paper]
  • Priority-Based State Machine Replication with PRaxos
    • Paulo Pinho, Luciana Rech, Lau Cheuk Lung, Miguel Correia and Lasaro Camargos
    • The 30-th IEEE International Conference on Advanced Information Networking and Applications (AINA-2016).
    • [Paper]
  • AR2C2: Actively Replicated Controllers for SDN Resilient Control Plane
    • Eros S. Spalla, Diego R. Mafioletti, Alextian B. Liberato, Gilberto Ewald, Christian E. Rothenberg, Lasaro Camargos, Rodolfo S. Villaca, Magnos Martinello
    • IEEE/IFIP Network Operations and Management Symposium (NOMS 2016).
    • [Paper]
• 2015
  • Fast Abstract: Implementation and evaluation of Collision-fast Atomic Broadcast protocols
    • Rodrigo Saramago and Lasaro Camargos.
    • 2015 Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN 2015).
    • [Paper]
  • Mechanism Reduction via Adjacency Matrix Power
    • Lásaro Camargos, João Marcelo Vedovoto, Ricardo Serfaty, Aristeu da Silveira Neto.
    • 5th International Workshop on Model Reduction in Reacting Flows (IWMRRF 2015).
    • Mechanism reduction is badly needed in large scale chemical simulations. Most graph based approaches, such as Directed Relation Graphs, derive the dependency of a species on all the others using single paths between them, which is not optimal. But since calculating the optimal solution has prohibitive costs, in this paper we propose the use of all the paths of a given large size to approximate the dependency.
    • [Slides][Paper]
  • Plataforma para Monitoramento de Métricas de Nível de Serviço em Redes Definidas por Software.
    • Pedro Rezende, Paulo Rodolfo da Silva Leite Coelho, Luis Fernando Faina, Lasaro Camargos, Rafael Pasquini
    • Simpósio Brasileiro de Redes de Computadores e Sistemas Distribuídos, SBRC'15.
    • This paper presents and evaluates a platform for monitoring service-level metrics in OpenFlow Software Defined Networks (SDN), named SDNMon. The platform supports frequent network observation, at different granularity levels, including per-flow observation, being able to present accurate on-the-fly statistics regarding throughput and delay. The evaluation considered two statistical data gathering approaches, a proposed polling-based mechanism which collects information kept by OpenFlow counters at the network elements, and an alternate sampling-based mechanism which uses sFlow.
    • [Slides][Paper]
  • Estrategias para Resiliencia em SDN : Uma Abordagem Centrada em Multi-Controladores Ativamente Replicados.
    • Eros Spalla, Diego Rossi Mafioletti, Alextian Liberato, Christian Esteve Rothenberg, Lasaro Camargos, Rodolfo Villaca, Magnos Martinello.
    • Simpósio Brasileiro de Redes de Computadores e Sistemas Distribuídos, SBRC'15.
    • Software Defined Networking (SDN) are based on the separation of control and data planes. The SDN controller, although logically centralized, should be effectively distributed for fault tolerance and high availability. Since the specification of OpenFlow 1.2, there are new features that allow the switches to communicate with multiple controllers that can play different roles – master, slave, and equal. However, these roles alone are not sufficient to guarantee a resilient control plane and the actual implementation remains an open challenge for SDN designers. In this paper, we explore the OpenFlow roles for the design of resilient SDN architectures relying on multi-controllers and propose an active replication based architecture. As a proof of concept, a strategy of active replication was implemented in the Ryu controller, using the OpenReplica service to ensure consistent state among the distributed controllers. The prototype was tested with commodity routerBoards/MikroTik switches and evaluated for latency in failure recovery and switch migration for different workloads. We observe a set of trade-offs in real experiments with varying workloads at both the data and control plane.
    • [Slides][Paper]
  • Exploring the Hamming Distance in Distributed Infrastructures for Similarity Search.
  • R da Silva Villaça, R Pasquini, LB de Paula, MF Magalhães.
  • Modeling and Processing for Next-Generation Big-Data Technologies, jan 2015.
  • Nowadays, the amount of data available on the Internet is over Zettabytes (ZB). Such condition defines a scenario known in the literature as Big Data. Although traditional databases are very efficient for finding and retrieving specific content, they are inefficient on Big Data scenario, since the great majority of such data are unstructured and scattered across the Internet. In this way, new databases are required in order to support similarity search. In order to handle such challenging scenario, the proposal in this chapter is to explore the Hamming similarity existent between content identifiers that are generated using the Random Hyperplane Hashing function. Such identifiers provide the basis for building distributed infrastructures that facilitate the similarity search. In this chapter, we present two different approaches: a P2P solution (Hamming DHT) and a Data Center solution (HCube). Evaluations are presented and indicate that both are capable of improving the recall in a similarity search.
• 2014
  • HCube: Routing and similarity search in Data Centers.
    • Rodolfo Villaça, Rafael Pasquini, Luciano B de Paula and Maurício Magalhães.
    • Journal of Network and Computer Applications, sep 2014.
    • The current Big Data scenario is mainly characterized by the huge amount of data available on the Internet. Some deployed mechanisms for handling such raw data rely on Data Centres (DCs) based on massive storage, memory and processing capacity, in which solutions like BigTable, MapReduce and Dynamo process information in order to provide its retrieval. The HCube presents a DC alternative for data storage/retrieval based on the similarity search, in which similar content is concentrated on servers physically close within the HCube, simplifying the recovery of similar data. A similarity search is performed using a primitive get(k,sim), in which k represents the reference content and sim a similarity threshold. The HCube network is organized in a three dimensional structure, in which the Gray Space Filling Curve (SFC) in conjunction with the Random Hyperplane Hashing (RHH) function and the XOR-based flat routing mechanism offer an efficient and powerful mechanism for the similarity search. In this context, this work presents the HCube networking solution, detailing the benefits of using the Gray SFC and the XOR-based flat routing mechanism for the similarity search.
    • [Slides][Paper]
  • Collision-fast Atomic Broadcast.
    • Rodrigo Schmidt, Lasaro Camargos and Fernando Pedone.
    • AINA 2014.
    • Atomic Broadcast, an important abstraction in dependable distributed computing, is usually implemented by solving infinitely many instances of the well-known consensus problem. Some asynchronous consensus algorithms achieve the optimal latency of two (message) steps but cannot guarantee this latency even in good runs, those with timely message delivery and no crashes. This is due to collisions, a result of concurrent pro-posals. Collision-fast consensus algorithms, which decide within two steps in good runs, exist under certain conditions. Their direct application to solving atomic broadcast, though, does not guarantee delivery in two steps for all messages unless a single failure is tolerated. We show a simple way to build a fault-tolerant collision-fast Atomic Broadcast algorithm based on a variation of the consensus problem we call M-Consensus. Our solution to M-Consensus extends the Paxos protocol to allow multiple processes, instead of the single leader, to have their proposals learned in two steps.
    • [Slides][Paper]
  • ASN-FWD: Shrinking the IPv4 Share on the Forwarding Information Base.
    • Marta C. C. Lacerda, Marcos Siqueira, Paulo R. S. L. Coelho, Luis F. Faina, Lasaro J. Camargos, Christian Esteve Rothenberg and Rafael Pasquini.
    • AINA 2014.
    • This paper presents a proposal for shrinking the number of IPv4 FIB (Forwarding Information Base) entries required on routers. Traffic forwarding under the proposed mechanism is based on the current ASNs (Autonomous System Numbers), and can be gradually adopted by ISPs. We find that, at the cost of adding 8 bytes per packet, the proposed ASN-FWD technique is capable of providing full IPv4 traffic forwarding based on ASN information, which is correspondent to 10\% of the current number of IPv4 prefixes present on FIB of routers. Among its main benefits, the proposed approach alleviates the pressure on the amount of FIB shipped on routers, and paves the way for a worldwide adoption of IPv6.
    • [Slides][Paper]
  • Node Position Forecast in MANET with PheroCast.
    • Paulo R. Coelho, Enrique Fynn, Luis F. Faina, Rafael Pasquin, and Lasaro Camargos.
    • AINA 2014.
    • In mobile ad hoc networks (MANET) nodes are free to move on the environment and interact with each other and with the infra-structure, enabling a multitude of applications and services. However, the same mobility that is key to MANET is also the greater limiting factor in the quality of the services provided in this environment, since the infrastructure must keep adapting to the mobility. This paper describes algorithms for predicting the future position of mobile nodes in MANET, allowing the infrastructure to proactively adapt. Our algorithms maintain the recent movement history of nodes in a compact representation, a graph, based on stigmergy of ant colonies. Predictions are generated through a limited depth first search. We have experimented this method against real world data and the results show that the prediction is accurate for short time horizons (30 seconds) in a metropolitan area (Seattle) divided in a grid of two or three-block square cells, in 77.8% of the cases. This method may be used in optimizing MANET and enabling novel applications, for example, proactive hand-off, tailored content generation, and proactive routing.
    • [Slides][Paper]
• 2013
  • eSylph.
    • Sabrina Maia and Lasaro Camargos.
    • 12° International Meeting of Art and Technology: Poetic Prospective [#12.ART].
    • Computational art exhibition "EmMeio#5", 2013. (watch a demo on vimeo and read more on the main author's web site).