Change search
Refine search result
1 - 27 of 27
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Rows per page
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sort
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
Select
The maximal number of hits you can export is 250. When you want to export more records please use the Create feeds function.
  • 1. Alowayed, Y.
    et al.
    Canini, M.
    Marcos, P.
    Chiesa, Marco
    KTH.
    Barcellos, M.
    Picking a partner: A fair blockchain based scoring protocol for autonomous systems2018In: ANRW 2018 - Proceedings of the 2018 Applied Networking Research Workshop, Association for Computing Machinery (ACM), 2018, p. 33-39Conference paper (Refereed)
    Abstract [en]

    We tackle the problem of enabling Autonomous Systems to evaluate network providers on the basis of their adherence to Service Level Agreements (SLAs) regarding interconnection agreements. In current Internet practices, choices of interconnection partners are driven by factors such as word of mouth, personal relationships, brand recognition and market intelligence, and not by proofs of previous performance. Given that Internet eXchange Points provide increasingly more peering choices, rudimentary schemes for picking interconnection partners are not adequate anymore. Although the current interconnection ecosystem is shrouded in confidentiality, our key observation is that recently-emerged blockchain technology and advances in cryptography enable a privacy-preserving decentralized solution based on actual performance measurements. We propose the concept of SLA score to evaluate network providers and introduce a privacy-preserving protocol that allows networks to compute and verify SLA scores.

  • 2. Angelini, P.
    et al.
    Bruckdorfer, T.
    Chiesa, Marco
    Roma Tre University, Italy.
    Frati, F.
    Kaufmann, M.
    Squarcella, C.
    On the area requirements of Euclidean minimum spanning trees2014In: Computational geometry, ISSN 0925-7721, E-ISSN 1879-081X, Vol. 47, no 2, p. 200-213Article in journal (Refereed)
    Abstract [en]

    In their seminal paper on Euclidean minimum spanning trees, Monma and Suri (1992) proved that any tree of maximum degree 5 admits a planar embedding as a Euclidean minimum spanning tree. Their algorithm constructs embeddings with exponential area; however, the authors conjectured that there exist n-vertex trees of maximum degree 5 that require c(n) x c(n) area to be embedded as Euclidean minimum spanning trees, for some constant c > 1. In this paper, we prove the first exponential lower bound on the area requirements for embedding trees as Euclidean minimum spanning trees.

  • 3. Angelini, P.
    et al.
    Bruckdorfer, T.
    Chiesa, Marco
    Roma Tre University, Italy.
    Frati, F.
    Kaufmann, M.
    Squarcella, C.
    On the area requirements of Euclidean minimum spanning trees2011In: Algorithms and Data Structures: 12th International Symposium, WADS 2011, New York, NY, USA, August 15-17, 2011. Proceedings, Springer Berlin/Heidelberg, 2011, Vol. 6844, p. 25-36Conference paper (Refereed)
    Abstract [en]

    In their seminal paper on Euclidean minimum spanning trees [Discrete & Computational Geometry, 1992], Monma and Suri proved that any tree of maximum degree 5 admits a planar embedding as a Euclidean minimum spanning tree. Their algorithm constructs embeddings with exponential area; however, the authors conjectured that c(n) x c(n) area is sometimes required to embed an n-vertex tree of maximum degree 5 as a Euclidean minimum spanning tree, for some constant c > 1. In this paper, we prove the first exponential lower bound on the area requirements for embedding trees as Euclidean minimum spanning trees.

  • 4. Antichi, Gianni
    et al.
    Castro, Ignacio
    Chiesa, Marco
    KTH, School of Electrical Engineering and Computer Science (EECS), Communication Systems, CoS, Network Systems Laboratory (NS Lab). Université catholique de Louvain.
    Fernandes, Eder L.
    Lapeyrade, Remy
    Kopp, Daniel
    Han, Jong Hun
    Bruyere, Marc
    Dietzel, Christoph
    Gusat, Mitchell
    Moore, Andrew W.
    Owezarski, Philippe
    Uhlig, Steve
    Canini, Marco
    ENDEAVOUR: A Scalable SDN Architecture For Real-World IXPs2017In: IEEE Journal on Selected Areas in Communications, ISSN 0733-8716, E-ISSN 1558-0008, Vol. 35, no 11, p. 2553-2562Article in journal (Refereed)
    Abstract [en]

    Innovation in interdomain routing has remained stagnant for over a decade. Recently, Internet eXchange Points (IXPs) have emerged as economically-advantageous interconnection points for reducing path latencies and exchanging ever increasing traffic volumes among, possibly, hundreds of networks. Given their far-reaching implications on interdomain routing, IXPs are the ideal place to foster network innovation and extend the benefits of software defined networking (SDN) to the interdomain level. In this paper, we present, evaluate, and demonstrate ENDEAVOUR, an SDN platform for IXPs. ENDEAVOUR can be deployed on a multi-hop IXP fabric, supports a large number of use cases, and is highly scalable, while avoiding broadcast storms. Our evaluation with real data from one of the largest IXPs, demonstrates the benefits and scalability of our solution: ENDEAVOUR requires around 70% fewer rules than alternative SDN solutions thanks to our rule partitioning mechanism. In addition, by providing an open source solution, we invite everyone from the community to experiment (and improve) our implementation as well as adapt it to new use cases.

  • 5.
    Chiesa, Marco
    et al.
    Roma Tre University, Italy.
    Cittadini, L.
    Di Battista, G.
    Vanbever, L.
    Vissicchio, S.
    Using routers to build logic circuits: How powerful is BGP?2013In: 2013 21st IEEE International Conference on Network Protocols (ICNP), IEEE Computer Society, 2013, article id 6733584Conference paper (Refereed)
    Abstract [en]

    Because of its practical relevance, the Border Gateway Protocol (BGP) has been the target of a huge research effort since more than a decade. In particular, many contributions aimed at characterizing the computational complexity of BGP-related problems. In this paper, we answer computational complexity questions by unveiling a fundamental mapping between BGP configurations and logic circuits. Namely, we describe simple networks containing routers with elementary BGP configurations that simulate logic gates, clocks, and flip-flops, and we show how to interconnect them to simulate arbitrary logic circuits. We then investigate the implications of such a mapping on the feasibility of solving BGP fundamental problems, and prove that, under realistic assumptions, BGP has the same computing power as a Turing Machine. We also investigate the impact of restrictions on the expressiveness of BGP policies and route propagation (e.g., route propagation rules in iBGP and Local Transit Policies in eBGP) and the impact of different message timing models. Finally, we show that the mapping is not limited to BGP and can be applied to generic routing protocols that use several metrics.

  • 6.
    Chiesa, Marco
    et al.
    Roma Tre University, Italy.
    Cittadini, L.
    Di Battista, G.
    Vissicchio, S.
    Local transit policies and the complexity of BGP Stability Testing2011In: INFOCOM, 2011 Proceedings IEEE, Institute of Electrical and Electronics Engineers (IEEE), 2011, p. 2957-2965, article id 5935136Conference paper (Refereed)
    Abstract [en]

    BGP, the core protocol of the Internet backbone, is renowned to be prone to oscillations. Despite prior work shed some light on BGP stability, many problems remain open. For example, determining how hard it is to check that a BGP network is safe, i.e., it is guaranteed to converge, has been an elusive research goal up to now. In this paper, we address several problems related to BGP stability, stating the computational complexity of testing if a given configuration is safe, is robust, or is safe under filtering. Further, we determine the computational complexity of checking popular sufficient conditions for stability. We adopt a model that captures Local Transit policies, i.e., policies that are functions only of the ingress and the egress points. The focus on Local Transit policies is motivated by the fact that they represent a configuration paradigm commonly used by network operators. We also address the same BGP stability problems in the widely adopted SPP model. Unfortunately, we find that the most interesting problems are computationally hard even if policies are restricted to be as expressive as Local Transit policies. Our findings suggest that the computational intractability of BGP stability be an intrinsic property of policy-based path vector routing protocols that allow policies to be specified in complete autonomy.

  • 7.
    Chiesa, Marco
    et al.
    KTH, School of Electrical Engineering and Computer Science (EECS), Communication Systems, CoS, Network Systems Laboratory (NS Lab). Université Catholique de Louvain, Belgium.
    Demmler, D.
    Canini, M.
    Schapira, M.
    Schneider, T.
    SIXPACK: Securing internet eXchange points against curious onlookers2017In: CoNEXT 2017 - Proceedings of the 2017 13th International Conference on emerging Networking EXperiments and Technologies, Association for Computing Machinery (ACM), 2017, p. 120-133Conference paper (Refereed)
    Abstract [en]

    Internet eXchange Points (IXPs) play an ever-growing role in Internet inter-connection. To facilitate the exchange of routes amongst their members, IXPs provide Route Server (RS) services to dispatch the routes according to each member's peering policies. Nowadays, to make use of RSes, these policies must be disclosed to the IXP. This poses fundamental questions regarding the privacy guarantees of route-computation on confidential business information. Indeed, as evidenced by interaction with IXP administrators and a survey of network operators, this state of affairs raises privacy concerns among network administrators and even deters some networks from subscribing to RS services. We design sixpack1, an RS service that leverages Secure Multi-Party Computation (SMPC) to keep peering policies confidential, while extending, the functionalities of today's RSes. As SMPC is notoriously heavy in terms of communication and computation, our design and implementation of sixpack aims at moving computation outside of the SMPC without compromising the privacy guarantees. We assess the effectiveness and scalability of our system by evaluating a prototype implementation using traces of data from one of the largest IXPs in the world. Our evaluation results indicate that sixpack can scale to support privacy-preserving route-computation, even at IXPs with many hundreds of member networks.

  • 8.
    Chiesa, Marco
    et al.
    Université catholique du Louvain, Belgium.
    Demmler, D.
    Canini, M.
    Schapira, M.
    Schneider, T.
    Towards securing internet eXchange points against curious onlooKers2016In: ANRW 2016 - Proceedings of the ACM, IRTF and ISOC Applied Networking Research Workshop, Association for Computing Machinery (ACM), 2016, p. 32-34Conference paper (Refereed)
    Abstract [en]

    The growing relevance of Internet eXchange Points (IXPs), where an increasing number of networks exchange routing information, poses fundamental questions regarding the privacy guarantees of confidential business information. To facilitate the exchange of routes among their members, IXPs provide Route Server (RS) services to dispatch the routes according to each member's export policies. Nowadays, to make use of RSes, these policies must be disclosed to the IXP. This state of affairs raises privacy concerns among network administrators and even deters some networks from subscribing to RS services. We design SIXPACK (which stands for "Securing Internet eXchange Points Against Curious onlooKers"), a RS service that leverages Secure Multi-Party Computation (SMPC) techniques to keep export policies confidential, while maintaining the same functionalities as today's RSes. We assess the effectiveness and scalability of our system by evaluating our prototype implementation and using traces of data from one of the largest IXPs in the world.

  • 9.
    Chiesa, Marco
    et al.
    Roma Tre University, Italy.
    Di Battista, G.
    Erlebach, T.
    Patrignani, M.
    Computational complexity of traffic hijacking under BGP and S-BGP2012In: Automata, Languages, and Programming: 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part II, Springer, 2012, Vol. 7392, no PART 2, p. 476-487Conference paper (Refereed)
    Abstract [en]

    Harmful Internet hijacking incidents put in evidence how fragile the Border Gateway Protocol (BGP) is, which is used to exchange routing information between Autonomous Systems (ASes). As proved by recent research contributions, even S-BGP, the secure variant of BGP that is being deployed, is not fully able to blunt traffic attraction attacks. Given a traffic flow between two ASes, we study how difficult it is for a malicious AS to devise a strategy for hijacking or intercepting that flow. We show that this problem marks a sharp difference between BGP and S-BGP. Namely, while it is solvable, under reasonable assumptions, in polynomial time for the type of attacks that are usually performed in BGP, it is NP-hard for S-BGP. Our study has several by-products. E. g., we solve a problem left open in the literature, stating when performing a hijacking in S-BGP is equivalent to performing an interception.

  • 10.
    Chiesa, Marco
    et al.
    Université catholique du Louvain, Belgium.
    Di Battista, G.
    Erlebach, T.
    Patrignani, M.
    Computational complexity of traffic hijacking under BGP and S-BGP2015In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 600, p. 143-154Article in journal (Refereed)
    Abstract [en]

    Harmful Internet hijacking incidents put in evidence how fragile interdomain routing is. In particular, the Border Gateway Protocol (BGP), which is used to exchange routing information between Internet entities, called Autonomous Systems (ASes), proved to be prone to attacks launched by a single malicious AS. Recent research contributions pointed out that even S-BGP, the secure variant of BGP that is being deployed, is not fully able to blunt traffic attraction attacks. Given a traffic flow between two ASes, we study how difficult it is for a malicious AS to devise a strategy for hijacking or intercepting that flow. The goal of the attack is to attract a traffic flow towards the malicious AS. While in the hijacking attack connectivity between the endpoints of a flow can be disrupted, in the interception attack connectivity must be maintained. We show that this problem marks a sharp difference between BGP and S-BGP. Namely, while it is solvable, under reasonable assumptions, in polynomial time for the type of attacks that are usually performed in BGP, it is NP-hard for S-BGP. Our study has several by-products. E.g., we solve a problem left open in the literature, stating when performing a hijacking in S-BGP is equivalent to performing an interception.

  • 11.
    Chiesa, Marco
    et al.
    Université catholique du Louvain, Belgium.
    DI Lallo, R.
    Lospoto, G.
    Mostafaei, H.
    Rimondini, M.
    DI Battista, G.
    PrIXP: Preserving the privacy of routing policies at Internet eXchange Points2017In: Proceedings of the IM 2017 - 2017 IFIP/IEEE International Symposium on Integrated Network and Service Management, Institute of Electrical and Electronics Engineers (IEEE), 2017, p. 435-441, article id 7987309Conference paper (Refereed)
    Abstract [en]

    Internet eXchange Points (IXPs) serve as landmarks where many network service providers meet to obtain reciprocal connectivity. Some of them, especially the largest, offer route servers as a convenient technology to simplify the setup of a high number of bi-lateral peerings. Due to their potential to support a quick and easy interconnection among the networks of multiple providers, IXPs are becoming increasingly popular and widespread, and route servers are exploited increasingly often. However, in an ever-growing level of market competition, service providers are pushed to develop concerns about many aspects that are strategic for their business, ranging from commercial agreements with other members of an IXP to the policies that are adopted in exchanging routing information with them. Although these aspects are notoriously sensitive for network service providers, current IXP architectures offer no guarantees to enforce the privacy of such business-critical information. We re-design a traditional route server and propose an approach to enforce the privacy of peering relationships and routing policies that it manages. Our proposed architecture ensures that nobody, not even a third party, can access such information unless it is the legitimate owner (i.e., the IXP member that set up the policy), yet allowing the route server to apply the requested policies and each IXP member to verify that such policies have been correctly deployed. We implemented the route server and tested our solutions in a simulated environment, tracking and analyzing the number of exchanged control plane messages.

  • 12.
    Chiesa, Marco
    et al.
    Université catholique du Louvain, Belgium.
    Dietzel, C.
    Antichi, G.
    Bruyére, M.
    Castro, I.
    Gusat, M.
    King, T.
    Moore, A. W.
    Nguyen, T. D.
    Owezarski, P.
    Uhlig, S.
    Canini, M.
    Inter-domain networking innovation on steroids: Empowering IXPs with SDN capabilities2016In: IEEE Communications Magazine, ISSN 0163-6804, E-ISSN 1558-1896, Vol. 54, no 10, p. 102-108, article id 7588277Article in journal (Refereed)
    Abstract [en]

    While innovation in inter-domain routing has remained stagnant for over a decade, Internet exchange points (IXPs) are consolidating their role as economically advantageous interconnection points for reducing path latencies and exchanging ever increasing amounts of traffic. As such, IXPs appear as a natural place to foster network innovation and assess the benefits of SDN, a recent technological trend that has already boosted innovation within data center networks. In this article, we give a comprehensive overview of use cases for SDN at IXPs, which leverage the superior vantage point of an IXP to introduce advanced features like load balancing and DDoS mitigation. We discuss the benefits of SDN solutions by analyzing real-world data from one of the largest IXPs. We also leverage insights into IXP operations to shape benefits not only for members but also for operators.

  • 13.
    Chiesa, Marco
    et al.
    Université catholique du Louvain, Belgium.
    Gurtov, A.
    Madry, A.
    Mitrovic, S.
    Nikolaevskiy, I.
    Schapira, M.
    Shenker, S.
    On the resiliency of randomized routing against multiple edge failures2016In: 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing , 2016, Vol. 55, article id 134Conference paper (Refereed)
    Abstract [en]

    We study the Static-Routing-Resiliency problem, motivated by routing on the Internet: Given a graph G = (V, E), a unique destination vertex d, and an integer constant c > 0, does there exist a static and destination-based routing scheme such that the correct delivery of packets from any source s to the destination d is guaranteed so long as (1) no more than c edges fail and (2) there exists a physical path from s to d? We embark upon a study of this problem by relating the edge-connectivity of a graph, i.e., the minimum number of edges whose deletion partitions G, to its resiliency. Following the success of randomized routing algorithms in dealing with a variety of problems (e.g., Valiant load balancing in the network design problem), we embark upon a study of randomized routing algorithms for the Static-Routing-Resiliency problem. For any k-connected graph, we show a surprisingly simple randomized algorithm that has expected number of hops O(|V|k) if at most k-1 edges fail, which reduces to O(|V|) if only a fraction t of the links fail (where t < 1 is a constant). Furthermore, our algorithm is deterministic if the routing does not encounter any failed link.

  • 14.
    Chiesa, Marco
    et al.
    Roma Tre University, Italy.
    Kindler, G.
    Schapira, M.
    Traffic engineering with Equal-Cost-Multipath: An algorithmic perspective2014In: INFOCOM, 2014 Proceedings IEEE, Institute of Electrical and Electronics Engineers (IEEE), 2014, p. 1590-1598, article id 6848095Conference paper (Refereed)
    Abstract [en]

    To efficiently exploit network resources operators do traffic engineering (TE), i.e., adapt the routing of traffic to the prevailing demands. TE in large IP networks typically relies on configuring static link weights and splitting traffic between the resulting shortest-paths via the Equal-Cost-MultiPath (ECMP) mechanism. Yet, despite its vast popularity, crucial operational aspects of TE via ECMP are still little-understood from an algorithmic viewpoint. We embark upon a systematic algorithmic study of TE with ECMP. We consider the standard model of TE with ECMP and prove that, in general, even approximating the optimal link-weight configuration for ECMP within any constant ratio is an intractable feat, settling a long-standing open question. We establish, in contrast, that ECMP can provably achieve optimal traffic flow for the important category of Clos datacenter networks. We last consider a well-documented shortcoming of ECMP: suboptimal routing of large ("elephant") flows. We present algorithms for scheduling "elephant" flows on top of ECMP (as in, e.g., Hedera [1]) with provable approximation guarantees. Our results complement and shed new light on past experimental and empirical studies of the performance of TE with ECMP.

  • 15.
    Chiesa, Marco
    et al.
    Université catholique du Louvain, Belgium.
    Kindler, G.
    Schapira, M.
    Traffic engineering with equal-cost-multipath: An algorithmic perspective2017In: IEEE/ACM Transactions on Networking, ISSN 1063-6692, E-ISSN 1558-2566, Vol. 25, no 2, p. 779-792, article id 7588075Article in journal (Refereed)
    Abstract [en]

    To efficiently exploit the network resources operators, do traffic engineering (TE), i.e., adapt the routing of traffic to the prevailing demands. TE in large IP networks typically relies on configuring static link weights and splitting traffic between the resulting shortest paths via the Equal-Cost-MultiPath (ECMP) mechanism. Yet, despite its vast popularity, crucial operational aspects of TE via ECMP are still little-understood from an algorithmic viewpoint. We embark upon a systematic algorithmic study of TE with ECMP. We consider the standard model of TE with ECMP and prove that, in general, even approximating the optimal link-weight configuration for ECMP within any constant ratio is an intractable feat, settling a long-standing open question. We establish, in contrast, that ECMP can provably achieve optimal traffic flow for the important category of Clos datacenter networks. We last consider a well-documented shortcoming of ECMP: suboptimal routing of large ("elephant") flows. We present algorithms for scheduling "elephant" flows on top of ECMP (as in, e.g., Hedera) with provable approximation guarantees. Our results complement and shed new light on past experimental and empirical studies of the performance of TE with ECMP.

  • 16.
    Chiesa, Marco
    et al.
    Roma Tre University.
    Lospoto, G.
    Rimondini, M.
    Di Battista, G.
    Intra-domain pathlet routing2013In: 2013 22nd International Conference on Computer Communications and Networks (ICCCN), IEEE Communications Society, 2013, article id 6614145Conference paper (Refereed)
    Abstract [en]

    Internal routing inside an ISP network is the foundation for lots of services that generate revenue from the ISP's customers. A fine-grained control of paths taken by network traffic once it enters the ISP's network is therefore a crucial means to achieve a top-quality offer and, equally important, to enforce SLAs. Many widespread network technologies and approaches (most notably, MPLS) offer limited (e.g., with RSVP-TE), tricky (e.g., with OSPF metrics), or no control on internal routing paths. On the other hand, recent advances in the research community are a good starting point to address this shortcoming, but miss elements that would enable their applicability in an ISP's network. We extend pathlet routing by introducing a new control plane for internal routing that pursues the following qualities: it is designed to operate in the internal network of an ISP; it enables fine-grained management of network paths with suitable configuration primitives; it is scalable because routing changes are only propagated to the network portion that is affected by the changes; it supports independent configuration of specific network portions without the need to know the configuration of the whole network; it is robust thanks to the adoption of multipath routing; it supports the enforcement of QoS levels; it is independent of the specific data plane used in the ISP's network; it can be incrementally deployed and it can nicely coexist with other control planes. Besides formally introducing the dissemination mechanisms and algorithms of our control plane, we propose an experimental validation in the simulation framework OMNeT++ that we use to assess the effectiveness and scalability of our approach.

  • 17.
    Chiesa, Marco
    et al.
    Roma Tre University, Italy.
    Lospoto, G.
    Rimondini, M.
    Di Battista, G.
    Intra-domain routing with pathlets2014In: Computer Communications, ISSN 0140-3664, E-ISSN 1873-703X, Vol. 46, p. 76-86Article in journal (Refereed)
    Abstract [en]

    Internal routing inside the network of an Internet Service Provider (ISP) affects the performance of lots of services that the ISP offers to its customers and is therefore critical to adhere to Service Level Agreements (SLAs), achieve a top-quality offer, and earn revenue. Existing technologies (most notably, MPLS) offer limited (e.g., with RSVP-TE), tricky (e.g., with OSPF metrics), or no control on internal routing paths. Recent research results address these shortcomings, but miss a few elements that would enable their application in an ISP's network. We introduce a new control plane, based on pathlet routing (Godfrey et al., 2009) [2], designed to operate in the network of an ISP and offering several nice features: it enables steering of network paths at different levels of granularity; it is scalable and robust; it supports independent configuration of specific network regions and differentiation of Quality of Service (QoS) levels; it can nicely coexist with other control planes and is independent of the data plane used in the ISP's network. Besides formally introducing the messages and algorithms of our control plane, we propose an experimental scalability assessment and comparison with OSPF, conducted in the simulation framework OMNeT++.

  • 18.
    Chiesa, Marco
    et al.
    Université catholique du Louvain, Belgium.
    Nikolaevskiy, I.
    Mitrovic, S.
    Gurtov, A.
    Madry, A.
    Schapira, M.
    Shenker, S.
    On the Resiliency of Static Forwarding Tables2017In: IEEE/ACM Transactions on Networking, ISSN 1063-6692, E-ISSN 1558-2566, Vol. 25, no 2, p. 1133-1146, article id 7728092Article in journal (Refereed)
    Abstract [en]

    Fast reroute and other forms of immediate failover have long been used to recover from certain classes of failures without invoking the network control plane. While the set of such techniques is growing, the level of resiliency to failures that this approach can provide is not adequately understood. In this paper, we embarked upon a systematic algorithmic study of the resiliency of forwarding tables in a variety of models (i.e., deterministic/probabilistic routing, with packet-headerrewriting, with packet-duplication). Our results show that the resiliency of a routing scheme depends on the "connectivity" k of a network, i.e., the minimum number of link deletions that partition a network. We complement our theoretical result with extensive simulations. We show that resiliency to four simultaneous link failures, with limited path stretch, can be achieved without any packet modification/duplication or randomization. Furthermore, our routing schemes provide resiliency against k - 1 failures, with limited path stretch, by storing log(k) bits in the packet header, with limited packet duplication, or with randomized forwarding technique.

  • 19.
    Chiesa, Marco
    et al.
    Université catholique du Louvain, Belgium.
    Nikolaevskiy, I.
    Mitrović, S.
    Panda, A.
    Gurtov, A.
    Maidry, A.
    Schapira, M.
    Shenker, S.
    The quest for resilient (static) forwarding tables2016In: INFOCOM 2016 - The 35th Annual IEEE International Conference on Computer Communications, IEEE, Institute of Electrical and Electronics Engineers (IEEE), 2016, article id 7524552Conference paper (Refereed)
    Abstract [en]

    Fast Reroute (FRR) and other forms of immediate failover have long been used to recover from certain classes of failures without invoking the network control plane. While the set of such techniques is growing, the level of resiliency to failures that this approach can provide is not adequately understood. We embark upon a systematic algorithmic study of the resiliency of immediate failover in a variety of models (with/without packet marking/duplication, etc.). We leverage our findings to devise new schemes for immediate failover and show, both theoretically and experimentally, that these outperform existing approaches.

  • 20.
    Chiesa, Marco
    et al.
    KTH, School of Electrical Engineering and Computer Science (EECS), Communication Systems, CoS, Network Systems Laboratory (NS Lab).
    Retvari, Gabor
    MTA BME Informat Syst Res Grp, H-1521 Budapest, Hungary..
    Schapira, Michael
    Hebrew Univ Jerusalem, IL-9190401 Jerusalem, Israel..
    Oblivious Routing in IP Networks2018In: IEEE/ACM Transactions on Networking, ISSN 1063-6692, E-ISSN 1558-2566, Vol. 26, no 3, p. 1292-1305Article in journal (Refereed)
    Abstract [en]

    To optimize the flow of traffic in IP networks, operators do traffic engineering (TE), i.e., tune routing-protocol parameters in response to traffic demands. TE in IP networks typically involves configuring static link weights and splitting traffic between the resulting shortest-paths via the equal-cost-multipath (ECMP) mechanism. Unfortunately, ECMP is a notoriously cumbersome and indirect means for optimizing traffic flow, often leading to poor network performance. Also, obtaining accurate knowledge of traffic demands as the input to TE is a non-trivial task that may require additional monitoring infrastructure, and traffic conditions can be highly variable, further complicating TE. We leverage recently proposed schemes for increasing ECMP's expressiveness via carefully disseminated bogus information (lies) to design COYOTE, a readily deployable TE scheme for robust and efficient network utilization. COYOTE leverages new algorithmic ideas to configure (static) traffic splitting ratios that are optimized with respect to all (even adversarial) traffic scenarios within the operator's "uncertainty bounds". Our experimental analyses show that COYOTE significantly outperforms today's prevalent TE schemes in a manner that is robust to traffic uncertainty and variation. We discuss experiments with a prototype implementation of COYOTE.

  • 21.
    Chiesa, Marco
    et al.
    Université catholique du Louvain, Belgium.
    Rétvári, G.
    Schapira, M.
    Lying your way to better traffic engineering2016In: CoNEXT 2016 - Proceedings of the 12th International Conference on Emerging Networking EXperiments and Technologies, Association for Computing Machinery (ACM), 2016, p. 391-398Conference paper (Refereed)
    Abstract [en]

    To optimize the flow of traffic in IP networks, operators do traffic engineering (TE), i.e., tune routing-protocol parameters in response to traffic demands. TE in IP networks typically involves configuring static link weights and splitting traffic between the resulting shortest-paths via the Equal- Cost-MultiPath (ECMP) mechanism. Unfortunately, ECMP is a notoriously cumbersome and indirect means for optimizing traffic flow, often leading to poor network performance. Also, obtaining accurate knowledge of traffic demands as the input to TE is elusive, and traffic conditions can be highly variable, further complicating TE.We leverage recently proposed schemes for increasing ECMP's expressiveness via carefully disseminated bogus information ("lies") to design COYOTE, a readily deployable TE scheme for robust and efficient network utilization. COYOTE leverages new algorithmic ideas to configure (static) traffic splitting ratios that are optimized with respect to all (even adversarially chosen) traffic scenarios within the operator's "uncertainty bounds". Our experimental analyses show that COYOTE significantly outperforms today's prevalent TE schemes in a manner that is robust to traffic uncertainty and variation. We discuss experiments with a prototype implementation of COYOTE.

  • 22. Dainotti, A.
    et al.
    Squarcella, C.
    Aben, E.
    Claffy, K. C.
    Chiesa, Marco
    Roma Tre University, Italy.
    Russo, M.
    Pescape, A.
    Analysis of country-wide internet outages caused by censorship2014In: IEEE/ACM Transactions on Networking, ISSN 1063-6692, E-ISSN 1558-2566, Vol. 22, no 6, p. 1964-1977, article id 6678649Article in journal (Refereed)
    Abstract [en]

    In the first months of 2011, Internet communications were disrupted in several North African countries in response to civilian protests and threats of civil war. In this paper, we analyze episodes of these disruptions in two countries: Egypt and Libya. Our analysis relies on multiple sources of large-scale data already available to academic researchers: BGP interdomain routing control plane data, unsolicited data plane traffic to unassigned address space, active macroscopic traceroute measurements, RIR delegation files, and MaxMind's geolocation database. We used the latter two data sets to determine which IP address ranges were allocated to entities within each country, and then mapped these IP addresses of interest to BGP-announced address ranges (prefixes) and origin autonomous systems (ASs) using publicly available BGP data repositories in the US and Europe. We then analyzed observable activity related to these sets of prefixes and ASs throughout the censorship episodes. Using both control plane and data plane data sets in combination allowed us to narrow down which forms of Internet access disruption were implemented in a given region over time. Among other insights, we detected what we believe were Libya's attempts to test firewall-based blocking before they executed more aggressive BGP-based disconnection. Our methodology could be used, and automated, to detect outages or similar macroscopically disruptive events in other geographic or topological regions.

  • 23. Dainotti, A.
    et al.
    Squarcella, C.
    Aben, E.
    Claffy, K. C.
    Chiesa, Marco
    Roma Tre University, Italy.
    Russo, M.
    Pescapé, A.
    Analysis of country-wide internet outages caused by censorship2011In: IMC '11 Proceedings of the 2011 ACM SIGCOMM conference on Internet measurement conference, 2011, p. 1-17Conference paper (Refereed)
    Abstract [en]

    In the first months of 2011, Internet communications were disrupted in several North African countries in response to civilian protests and threats of civil war. In this paper we analyze episodes of these disruptions in two countries: Egypt and Libya. Our analysis relies on multiple sources of large-scale data already available to academic researchers: BGP interdomain routing control plane data; unsolicited data plane traffic to unassigned address space; active macroscopic traceroute measurements; RIR delegation files; and MaxMind's geolocation database. We used the latter two data sets to determine which IP address ranges were allocated to entities within each country, and then mapped these IP addresses of interest to BGP-announced address ranges (prefixes) and origin ASes using publicly available BGP data repositories in the U.S. and Europe. We then analyzed observable activity related to these sets of prefixes and ASes throughout the censorship episodes. Using both control plane and data plane data sets in combination allowed us to narrow down which forms of Internet access disruption were implemented in a given region over time. Among other insights, we detected what we believe were Libya's attempts to test firewall-based blocking before they executed more aggressive BGP-based disconnection. Our methodology could be used, and automated, to detect outages or similar macroscopically disruptive events in other geographic or topological regions.

  • 24. Dethise, A.
    et al.
    Chiesa, Marco
    Université catholique du Louvain, Belgium.
    Canini, M.
    Privacy-preserving detection of inter-domain SDN rules overlaps2017In: SIGCOMM Posters and Demos 2017 - Proceedings of the 2017 SIGCOMM Posters and Demos, Part of SIGCOMM 201722 August 2017, Association for Computing Machinery (ACM), 2017, p. 6-8Conference paper (Refereed)
    Abstract [en]

    SDN approaches to inter-domain routing promise better traffic engineering, enhanced security, and higher automation. Yet, naïve deployment of SDN on the Internet is dangerous as the control-plane expressiveness of BGP is significantly more limited than the data-plane expressiveness of SDN, which allows fine-grained rules to deflect traffic from BGP's default routes. This mismatch may lead to incorrect forwarding behaviors such as forwarding loops and blackholes, ultimately hindering SDN deployment at the inter-domain level. In this work, we make a first step towards verifying the correctness of inter-domain forwarding state with a focus on loop freedom while keeping private the SDN rules, as they comprise confidential routing information. To this end, we design a simple yet powerful primitive that allows two networks to verify whether their SDN rules overlap, i.e., the set of packets matched by these rules is non-empty, without leaking any information about the SDN rules. We propose an efficient implementation of this primitive by using recent advancements in Secure Multi-Party Computation and we then leverage it as the main building block for designing a system that detects Internet-wide forwarding loops among any set of SDN-enabled Internet eXchange Points.

  • 25. Dietzel, C.
    et al.
    Antichi, G.
    Castro, I.
    Fernandes, E. L.
    Chiesa, Marco
    Université catholique du Louvain.
    Kopp, D.
    SDN-enabled traffic engineering and advanced blackholing at IXPs2017In: SOSR 2017 - Proceedings of the 2017 Symposium on SDN Research, 2017, p. 181-182Conference paper (Refereed)
    Abstract [en]

    While the clean slate approach proposed by Software Defined Networking (SDN) promises radical changes in the stagnant state of network management, SDN innovation has not gone beyond the intra-domain level. For the inter-domain ecosystem to benefit from the advantages of SDN, Internet Exchange Points (IXPs) are the ideal place: a central interconnection hub through which a large share of the Internet can be affected. In this demo, we showcase the ENDEAVOUR platform: a new software defined exchange approach readily deployable in commercial IXPs. We demonstrate here our implementations of traffic engineering and Distributed Denial of Service mitigation, as well as how member networks cash in on the advanced SDN-features of ENDEAVOUR, typically not available in legacy networks.

  • 26. Nguyen, T. D.
    et al.
    Chiesa, Marco
    Université catholique du Louvain, Belgium.
    Canini, M.
    Decentralized consistent updates in SDN2017In: SOSR 2017 - Proceedings of the 2017 Symposium on SDN Research, Association for Computing Machinery (ACM), 2017, p. 21-33Conference paper (Refereed)
    Abstract [en]

    We present ez-Segway, a decentralized mechanism to consistently and quickly update the network state while preventing forwarding anomalies (loops and blackholes) and avoiding link congestion. In our design, the centralized SDN controller only pre-computes information needed by the switches during the update execution. This information is distributed to the switches, which use partial knowledge and direct message passing to efficiently realize the update. This separation of concerns has the key benefit of improving update performance as the communication and computation bottlenecks at the controller are removed. Our evaluations via network emulations and large-scale simulations demonstrate the efficiency of ez-Segway, which compared to a centralized approach, improves network update times by up to 45% and 57% at the median and the 99th percentile, respectively. A deployment of a system prototype in a real OpenFlow switch and an implementation in P4 demonstrate the feasibility and low overhead of implementing simple network update functionality within switches.

  • 27. Nguyen, T. D.
    et al.
    Chiesa, Marco
    Université catholique du Louvain, Belgium.
    Canini, M.
    Towards decentralized fast consistent updates2016In: ANRW 2016 - Proceedings of the ACM, IRTF and ISOC Applied Networking Research Workshop, Association for Computing Machinery (ACM), 2016, p. 19-25Conference paper (Refereed)
    Abstract [en]

    Updating data plane state to adapt to dynamic conditions is a fundamental network control operation. Software-Defined Networking (SDN) offers abstractions for updating network state while preserving consistency properties. However, realizing these abstractions in a purely centralized fashion is inefficient, due to the inherent delays between switches and the SDN controller, we argue for delegating the responsibility of coordinated updates to the switches. To make our case, we propose ez-Segway, a mechanism that enables decentralized network updates while preventing forwarding anomalies and avoiding link congestion. In our architecture, the controller is only responsible for computing the intended network configuration. This information is distributed to the switches, which use partial knowledge and direct message passing to efficiently schedule and implement the update. This separation of concerns has the key benefit of improving update performance as the communication and computation bottlenecks at the controller are removed. Our extensive simulations show update speedups up to 2x.

1 - 27 of 27
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf