Marco Chiesa

Position:

Postdoctoral Researcher cv

E-mail:

marco.chiesauclouvain.be

Office phone:

+32 010 47 87 18

Regular mail:

Office L5.02.01
Pôle en ingénierie informatique
Université de Louvain
Place Sainte Barbe, 2
1348, Louvain-la-neuve, Belgium


I am a researcher at the ICTEAM networking group of the University of Louvain, supervised by Marco Canini. I am involved in the ENDEAVOUR (H2020 EU funded) project, intended to bring Software-Defined Networking (SDN) functionality to inter-domain routing on the Internet. I received my Ph.D. from Roma Tre University in 2014, advised by Prof. Giuseppe Di Battista.

My research interests lie in computer networking and, more specifically, in aspects of Internet protocols and architectures ranging from security and privacy to network design and optimization, including Software Defined Networking (SDN) approaches to these challenges, next-generation Internet eXchange Points (IXPs), and beyond.

News


Key themes: Internet Exchange Point, SDN, BGP, Network Management

The focus of the project is to enable added-value services to be provided thanks to Software-Defined Networking (SDN), on top of Internet Exchange Points and other network interconnnection fabrics. The services would relate not only to the flexibility of the interconnection fabric, but most importantly to enable the content and data center ecosystem that is present at the interconnection fabric to collaborate. The ultimate goal is to create a service marketplace on top of the ecosystem composed of Cloud/data centers, networked applications, and the interconnection fabric.

The objective of ENDEAVOUR is to address current limitations of the Internet interconnection model, as well as to open the opportunity for novel services, creating the possibility for new economic models around the created ecosystems.

Read our use case paper »

Website: www.h2020-endeavour.eu

Start/end date: 01/01/2015 - 31/12/2017

Budget: 4.2M EUR

Other partners: Queen Mary University of London, University of Cambridge, DE-CIX, LAAS-CNRS, IBM Zurich

Key themes: Internet Exchange Point, BGP, privacy preservation

Internet eXchange Points (IXPs), where a quickly increasing number of networks exchange routing information, play an ever growing role in Internet inter-connection. To facilitate the exchange of routes among 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 from interaction with IXP administrators, and 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 an RS service that leverages Secure Multi-Party Computation (SMPC) techniques to keep peering policies confidential, while maintaining, and even extending, the functionalities of today's RSes. 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 our RS system can scale to support privacy-preserving route-computation even at IXPs with many hundreds of member networks.

View on BitBucket » Read our short paper » Watch our talk »

Join work with : Marco Canini (KAUST), Daniel Demmler (TU Darmstadt), Michael Schapira (HUJI), Thomas Schneider, (TU Darmstadt)

Key themes: Traffic Engineering, SDN, traffic uncertainty

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.

Read our short paper »

Joint work with: Gábor Rétvári (Budapest University of Technology and Economics), Michael Schapira (HUJI)

Key themes: SDN, robustness, resiliency, fast failover

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. 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-header-rewriting, 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 $4$ 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.

Read our full paper »

Joint work with: Andrei Gurtov (Linkoping), Aleksander Madry (MIT), Slobodan Mitrovic (EPFL), Ilya Nikolaevskiy (Aalto), Aurojit Panda (UC Berkeley), Michael Schapira (HUJI), Scott Shenker (ICSI/UC Berkeley)

Key themes: Traffic Engineering, ECMP, computational complexity

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 first consider the standard “splittable-flow” model of TE with ECMP, put forth in [18]. We settle a long-standing open question by proving that, in general, even approximating the optimal link-weight configuration for ECMP within any constant ratio is an intractable feat. We also initiate the analytical study of TE with ECMP on specific network topologies and, in particular, datacenter networks. We prove that while TE with ECMP remains suboptimal and computationallyhard for hypercube networks, ECMP can, in contrast, provably achieve optimal traffic flow for the important category of folded Clos networks. We next investigate the approximability of TE with ECMP in the more realistic “unsplittable-flow” model and present upper and lower bounds for scheduling “elephant” flows on top of ECMP (as in, e.g., Hedera [4]). Our results complement and shed new light on past experimental and empirical studies of the performance of TE with ECMP.

Read our full paper »

Joint work with: Guy Kindler (HUJI), Michael Schapira (HUJI)

2017

  1. Arnaud Dethise, Marco Chiesa, Marco Canini. Poster: Privacy-Preserving Detection of Inter-Domain SDN Rules Overlaps. In SIGCOMM 2017, 2017. Poster.
  2. Christoph Dietzel, Gianni Antichi Ignacio Castro, Eder Fernandes, Marco Chiesa. Demo: SDN-enabled Traffic Engineering and Advanced Blackholing at IXPs. In Symposium on SDN Research (SOSR 2017), 2017. Poster.
  3. Thanh Dang Nguyen, Marco Chiesa, Marco Canini. Decentralized Fast Consistent Updates . In Symposium on SDN Research (SOSR 2017), 2017.
  4. Marco Chiesa, Roberto di Lallo, Gabriele Lospoto, Habib Mostafaei, Massimo Rimondini, Giuseppe Di Battista. PrIXP: Preserving the Privacy of Routing Policies at Internet eXchange Points. In Proc. IFIP/IEEE International Symposium on Integrated Network Management (IM 2017), 2017. To appear.

2016

  1. Marco Chiesa, Ilya Nikolaevskiy, Slobodan Mitrovic, Andrei Gurtov, Aleksander Madry, Michael Schapira, Scott Shenker. On the Resiliency of Static Forwarding Tables. IEEE/ACM Transactions on Networking. 2016.
  2. Marco Chiesa, Gabor Retvari, Michael Schapira. Lying Your Way to Better Traffic Engineering . In International Conference on emerging Networking EXperiments and Technologies (CONEXT 2016), 2016. [ Slides]
  3. Marco Chiesa, Guy Kindler, Michael Schapira. Traffic engineering with Equal-Cost-Multipath: An algorithmic perspective. IEEE/ACM Transactions on Networking. 2016.
  4. Thanh Dang Nguyen, Marco Chiesa, Marco Canini. Towards Decentralized Fast Consistent Updates . In Applied Networking Research Workshop (ANRW 2016), 2016. [ Slides]
  5. Marco Chiesa, Daniel Demmler, Marco Canini, Michael Schapira, Thomas Schneider. Towards Securing Internet eXchange Points Against Curious onlooKers . In Applied Networking Research Workshop (ANRW 2016), 2016. [ Poster] [ Slides]
  6. Marco Chiesa, Christoph Dietzel, Gianni Antichi, Marc Bruyere, Ignacio Castro, Mitch Gusat, Thomas King, Andrew W. Moore, Thanh Dang Nguyen, Philippe Owezarski, Steve Uhlig, Marco Canini. Inter-domain Networking Innovation on Steroids: Empowering IXPs with SDN Capabilities. IEEE Communications Magazine special issue on SDN Use Cases for Service Provider Networks. 2016. to appear. [ Paper PDF]
  7. Marco Chiesa, Andrei Gurtov, Aleksander Madry, Slobodan Mitrovic, Ilya Nikolaevskiy, Michael Schapira, Scott Shenker. On the Resiliency of Randomized Routing Against Multiple Edge Failures . In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), 2016. [Technical Report on ArXiv] [ Slides]
  8. Marco Chiesa, Ilya Nikolaevskiy, Slobodan Mitrovic, Andrei Gurtov and Aleksander Madry, Aurojit Panda, Michael Schapira, Scott Shenker. The Quest for Resilient (Static) Forwarding Tables . In 35th IEEE International Conference on Computer Communications (IEEE INFOCOM 2016), 2016. [Technical Report on ArXiv] [ Slides]

2015

  1. Marco Chiesa, Giuseppe Di Battista, Thomas Erlebach, Maurizio Patrignani. Computational Complexity of Traffic Hijacking under BGP and S-BGP. Theoretical Computer Science. 600:143-154. 2015.

2014

  1. Marco Chiesa, Ilya Nikolaevskiy, Aurojit Panda, Andrei Gurtov, Michael Schapira, Scott Shenker. Exploring the Limits of Static Failover Routing. Technical Report arXiv:1409.0034, Cornell University, 2014.
  2. Alberto Dainotti, Claudio Squarcella, Emile Aben, Kimberly C. Claffy, Marco Chiesa, Michele Russo, Antonio Pescape'. Analysis of Country-wide Internet Outages Caused by Censorship. IEEE/ACM Transactions on Networking. 22(6):1964-1977. 2014.
  3. Marco Chiesa. The Role of Routing Policies in the Internet: Stability, Security, and Load-Balancing, Doctoral Thesis, Universita' degli Studi di Roma ``Roma Tre'', Dottorato di Ricerca in Ingegneria, Sezione Informatica ed Automazione, XXVI Ciclo, 2014. [ Thesis (PDF)] [ Presentation (PDF)]
  4. Marco Chiesa, Gabriele Lospoto, Massimo Rimondini, Giuseppe Di Battista. Intra-Domain Routing with Pathlets. Computer Communications. 46:76-86. 2014.
  5. Marco Chiesa, Guy Kindler, Michael Schapira. Traffic engineering with Equal-Cost-Multipath: An algorithmic perspective. In 33th IEEE International Conference on Computer Communications (IEEE INFOCOM 2014), IEEE, pages 1590-1598, 2014. [ Full Paper] [ Presentation at INFOCOM'14 ]
  6. Patrizio Angelini, Till Bruckdorfer, Marco Chiesa, Fabrizio Frati, Michael Kaufmann, Claudio Squarcella. On the Area Requirements of Euclidean Minimum Spanning Trees. Computational Geometry: Theory and Applications. 47(2):200-213. 2014. Special Issue on Selected Papers from WADS '11.

2013

  1. Marco Chiesa, Luca Cittadini, Laurent Vanbever, Stefano Vissicchio, Giuseppe Di Battista. Using Routers to Build Logic Circuits: How Powerful is BGP?. In Proc. International Conference on Network Protocols (IEEE ICNP 2013), IEEE, pages 1-10, 2013. [BEST PAPER AWARD ] [ Presentation at ICNP'13 ]
  2. Marco Chiesa, Gabriele Lospoto, Massimo Rimondini, Giuseppe Di Battista. Intra-Domain Pathlet Routing. In 22nd International Conference on Computer Communications and Networks (IEEE ICCCN 2013), IEEE, pages 1-9, 2013. [ Presentation at ICCCN'13]
  3. Marco Chiesa, Gabriele Lospoto, Massimo Rimondini, Giuseppe Di Battista. Intra-Domain Pathlet Routing. Technical Report arXiv:1302.5414, Cornell University, 2013.

2012

  1. Marco Chiesa, Giuseppe Di Battista, Thomas Erlebach, Maurizio Patrignani. Computational Complexity of Traffic Hijacking under BGP and S-BGP. Technical Report arXiv:abs-1205-4564, Cornell University, 2012.
  2. Marco Chiesa, Giuseppe Di Battista, Thomas Erlebach, Maurizio Patrignani. Computational Complexity of Traffic Hijacking under BGP and S-BGP. In Proc. 39th International Colloquium on Automata, Languages and Programming (ICALP '12), Springer Verlag, volume 7392 of Lecture Notes in Computer Science, pages 476-487, 2012. [see arXiv extended version] [ Presentation at ICALP'12]

2011

  1. Alberto Dainotti, Claudio Squarcella, Emile Aben, Kimberly C. Claffy, Marco Chiesa, Michele Russo, Antonio Pescape'. Analysis of Country-wide Internet Outages Caused by Censorship. In 2011 Internet Measurement Conference (IMC '11), ACM, IMC '11, pages 1-18, 2011. [ PDF]
  2. Patrizio Angelini, Till Bruckdorfer, Marco Chiesa, Fabrizio Frati, Michael Kaufmann, Claudio Squarcella. On the Area Requirements of Euclidean Minimum Spanning Trees. In, F. K. H. A. Dehne, J. Iacono, J.-R. Sack, editors, 12th Algorithms and Data Structures Symposium (WADS '11), Springer, volume 6844 of Lecture Notes in Computer Science, pages 25-36, 2011.
  3. Marco Chiesa, Luca Cittadini, Giuseppe Di Battista, Stefano Vissicchio. Local Transit Policies and the Complexity of BGP Stability Testing. In 30th IEEE International Conference on Computer Communications (IEEE INFOCOM 2011), IEEE, pages 2957-2965, 2011. [ Presentation at INFOCOM'11]
  4. Patrizio Angelini, Till Bruckdorfer, Marco Chiesa, Fabrizio Frati, Michael Kaufmann, Claudio Squarcella. On the Area Requirements of Euclidean Minimum Spanning Trees. Technical Report RT-DIA-183-2011, Dept. of Computer Science and Automation, Roma Tre University, 2011.

White to move. What is the best continuation to this brilliant chess puzzle?

You are forced to enter into a dark room. Inside the room, there is a table with $100$ non-overlapping coins placed on its surface. Each coin is either colored white or black. Once you enter the room, you cannot distinguish whether a coin has its upper side colored in black or white. You will be saved only if you will be able to partition the coins into two groups, each group with the same number of coins with the white side oriented upwards. You are allowed to flip the coins as many time as you want. Luckily, before entering the room, you overheard a vital information: 70 coins have their black side oriented upwards while the 30 remaining coins have their white side oriented upwards. Will you be able to survive?

There are $n$ prisoners serving a long-time sentence. One day, the director of the prison communicates them that the day after they will be disposed in a row in such a way that each prisoner will only be able to see the prisoners in front of him. Each prisoner will be wearing a hat, without knowing it color, which can be either black or white. As such, each prisoner does not know the color of its hat but he can see the color of the hats of the prisoners in front of him. Starting from the latter prisoner (the one that sees all the other prisoners), each prisoner will be asked to loudly guess the color of its hat by saying either "white" or black". Everyone can hear the answers. The prisoner will be killed if it fails to guess the color of its hat and it will be saved otherwise. The prisoners decides to agree on the strategy that guarantees the maximum number of survivors. How many people will survive for certain the day after?