Back to search

Cornell University

Throughput and Latency in Reconfigurable Networks

Abstract

dc:description.abstract

Oblivious routing has a long history in both the theory and practice of networking. In this dissertation, we initialize the formal study of oblivious routing in the context of reconfigurable networks, a new architecture that has recently come to the fore in data center networking, due to its increased energy efficiency and scaling potential. We focus on the tradeoffs between maximizing throughput and minimizing latency in this space. For every constant throughput rate, we characterize the minimum latency (up to a constant factor) achievable by an oblivious reconfigurable network design. The tradeoff curve turns out to be surprisingly subtle: it has an unexpected scalloped shape, reflecting the fact that routing becomes more costly when average path length is not an integer, since equalizing the path lengths is not achievable. We show that in order to guarantee the throughput value, Valiant load balancing is necessary, which lengthens routing paths by a factor of two. However, we also show that a strictly superior latency-throughput tradeoff is achievable when the throughput bound is relaxed to hold with high probability. The same improved tradeoff is also achievable with guaranteed throughput under time-stationary demands, provided the latency bound is relaxed to hold with high probability and that the network is allowed to be semi-oblivious, using an oblivious (randomized) connection schedule but demand-aware routing.

Degree

thesis:*
Name thesis:degree_name
Ph. D., Computer Science
Level thesis:degree_level
Doctor of Philosophy
Discipline thesis:degree_discipline
Computer Science
Grantor
Cornell University
Year dc:date.issued
2024

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Wilson, Tegan
Chair dc:contributor.chair
  • Kleinberg, Robert
Committee members dc:contributor.committeemember
  • Williamson, David
  • Tardos, Eva

Rights

dc:rights
Statement dc:rights
  • Attribution 4.0 International
Language dc:language.iso
en

Identifiers

dc:identifier.*
Dc Identifier Bibid
16611849
Dc Identifier Other
ProQuest Submission ID: 14425
ProQuest Publication ID: 31336723

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Wilson, Tegan. Throughput and Latency in Reconfigurable Networks. Doctor of Philosophy thesis, Cornell University, 2024. https://hdl.handle.net/1813/116620