João Luís Sobrinho and Master Student Miguel Ferreira won an ACM SIGCOMM best paper award for their work on “Routing on Multiple Optimality Criteria”.


ACM SIGCOMM is the flagship annual conference of the ACM Special Interest Group on Data Communications. The conference was a virtual event that took place from August 11 to August 14, 2020.

The awarded paper addresses the problem of optimal path routing for generic optimality criteria. Such criteria depend on the nature of the network and on the applications supported by it. For example, an optimal path to convey a file is not necessarily optimal to stream a video.

Current routing protocols, such as BGP, EIGRP, and OSPF, are unable to route data-packets on optimal paths for all but the simplest optimality criteria. The paper presents routing protocols that route optimally for generic optimality criteria. A key idea underlying the design of these protocols is the selection of routing paths in two stages. In the first stage, the nodes of the network collectively compute a minimal set of paths from every source to every destination that is mathematically guaranteed to contain the optimal path. In the second stage, every source identifies the optimal path to every destination within the minimal set of paths computed during the first stage. The paper also shows how path selection in two stages allows simultaneous routing on multiple optimality criteria. Returning to the earlier example, the routing protocols proposed enable concurrent conveyance of files and streaming of videos along the respective optimal paths.

Internet routing has been subject to slow innovation cycles involving network operators and router vendors. The breakthrough on optimal path routing brought by this paper coupled with progresses on network programmability promise a richer set of routing options for future networks.

This year ACM SIGCOMM awarded two best papers, João and Miguel’s and another authored by 12 researchers from Google, out of 250 submissions and 53 accepted papers.