#### Position:

Assistant Professor

mchiesakth.se

#### Office directions:

Electrum Building, 4th floor
Room 13.0 (in front of Reno)
How to reach Electrum? Maps
Where is my room? PDF

#### Regular mail:

Kistagången 16
164 40, Kista
Sweden

I am an Assistant Professor in the Network System Lab group of the Communication Systems department at the KTH Royal Institute of Technology.

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.

Prior to join KTH, I was a postdoctoral researcher in the INL networking group at the Université catholique de Louvain, supervised by Marco Canini, and a postdoctoral researcher at the Hebrew University of Jerusalem supervised by Michael Schapira. In 2013, I was a visiting scholar in the Berkeley NetSys Lab at the University of Berkeley supervised by Scott Shenker. I received my Ph.D. from Roma Tre University in 2014, advised by Prof. Giuseppe Di Battista. I was involved in the ENDEAVOUR (H2020 EU funded) project, intended to bring Software-Defined Networking (SDN) functionality to inter-domain routing on the Internet.

### 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.

Website: www.h2020-endeavour.eu

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

Budget: 4.2M EUR

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.

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.

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.

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.

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

## 2018

1. Pedro Marcos, Marco Chiesa, Lucas Muller, Pradeeban Kathiravelu, Christoph Dietzel, Marco Canini, Marinho Barcellos. Dynam-IX: a Dynamic Interconnection eXchange. In International Conference on emerging Networking EXperiments and Technologies (CoNEXT 2018), ACM, 2018. To Appear.
2. Arnaud Dethise, Marco Chiesa, Marco Canini. Prelude: Ensuring Inter-Domain Loop-Freedom in SDN-Enabled Networks . In Asia-Pacific Workshop on Networking (APNet 2018), 2018.
3. Roshan Sedar, Michael Borokhovich, Marco Chiesa, Gianni Antichi, Stefan Schmid. Supporting Emerging Applications With Low-Latency Failover in P4 . In ACM Workshop on Networking for Emerging Applications and Technologies (NEAT 2018), 2018. To appear.
4. Marco Chiesa, Gabor Retvari, Michael Schapira. Oblivious Routing in IP Networks. IEEE/ACM Transactions on Networking. 2018. To appear.
5. Pradeeban Kathiravelu, Marco Chiesa, Pedro de Botelho Marcos, Marco Canini, Luís Veiga. Moving Bits with a Fleet of Shared Virtual Routers . In IEEE/IFIP Networking 2018, 2018. To appear.
6. Klaus-Tycho Foerster, Mahmoud Parham, Marco Chiesa, Stefan Schmid. TI-MFA: Keep Calm and Reroute Segments Fast. In Global Internet Symposium (GI 2018), IEEE, 2018. To appear.

## 2017

1. Marco Chiesa, Daniel Demmler, Marco Canini, Michael Schapira, Thomas Schneider. SIXPACK: Securing Internet eXchange Points Against Curious onlooKers. In International Conference on emerging Networking EXperiments and Technologies (CoNEXT 2017), ACM, pages 120-133, 2017. [ PDF] [ Slides PDF]
2. Gianni Antichi, Ignacio Castro, Marco Chiesa, Eder Fernandes, Remy Lapeyrade, Daniel Kopp, Jong Han, Marc Bruyere, Christoph Dietzel, Mitch Gusat, Andrew W. Moore, Philippe Owezarski, Steve Uhlig, Marco Canini. ENDEAVOUR: A Scalable SDN Architecture for Real-World IXPs. IEEE JSAC Special issue on Emerging Technologies in Software-driven Communication. 35(2553-2562). 2017. [Free access PDF]
3. Arnaud Dethise, Marco Chiesa, Marco Canini. Extended abstract: Privacy-Preserving Detection of Inter-Domain SDN Rules Overlaps. In SIGCOMM, ACM, pages 6-8, 2017. Poster. [ Extended Abstract] [ Poster]
4. 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), ACM, pages 181-182, 2017. Demo. [ Extended abstract] [ Poster]
5. Thanh Dang Nguyen, Marco Chiesa, Marco Canini. Decentralized Fast Consistent Updates . In Symposium on SDN Research (SOSR 2017), ACM, pages 21-33, 2017. [ Paper] [ Technical Report]
6. 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), IEEE, 2017. [ Pre-print]
7. 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. 25(2):1133-1146. 2017. [ Pre-print]
8. Marco Chiesa, Guy Kindler, Michael Schapira. Traffic engineering with Equal-Cost-Multipath: An algorithmic perspective. IEEE/ACM Transactions on Networking. 25(2):779-792. 2017. [ Pre-print]

## 2016

1. Marco Chiesa, Gabor Retvari, Michael Schapira. Lying Your Way to Better Traffic Engineering. In International Conference on emerging Networking EXperiments and Technologies (CoNEXT 2016), ACM, pages 391-398, 2016. [ Paper PDF] [ Slides]
2. Thanh Dang Nguyen, Marco Chiesa, Marco Canini. Towards Decentralized Fast Consistent Updates . In Applied Networking Research Workshop (ANRW 2016), 2016. [ Slides]
3. 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]
4. 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. 54(10):102-108. 2016.
5. 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]
6. 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. [ Pre-print] [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?