2010 technical reports

Fundamental limitations of traditional data center network architectures have led to the development of architectures that provide enormous bisection bandwidth for up to hundreds of thousands of servers. Because these architectures rely on homogeneous switches, implementing one in a legacy data center usually requires replacing most existing switches. Such forklift upgrades are typically prohibitively expensive; instead, a data center manager should be able to selectively add switches to boost bisection bandwidth. Doing so adds heterogeneity to the network’s switches and heterogeneous high-performance interconnection topologies are not well understood. Therefore, we develop the theory of heterogeneous Clos networks. We show that our construction needs only as much link capacity as the classic Clos network to route the same traffic matrices and this bound is the optimal. Placing additional equipment in a highly constrained data center is challenging in practice, however. We propose LEGUP to design the topology and physical arrangement of such network upgrades or expansions. Compared to current solutions, we show that LEGUP finds network upgrades with more bisection bandwidth for half the cost. And when expanding a data center iteratively, LEGUP’s network has 265% more bisection bandwidth than an iteratively upgraded fat-tree.

Sensor networks are extremely vulnerable to denial-of-service (DoS) attacks due to their shared communication medium and the constrained power supply of the devices. We examine the scenario where one player attempts to send a message m to another player in a single-channel network. Assume an adversary that jams for  T instances where T is unknown to either player and where cost is measured in terms of energy expenditure. We give a protocol guaranteeing delivery of m while the ratio of either player's expected cost to the adversary's cost is O(T^(varphi-2)) ~ O(T0.382) where varphi= (1+ sqrt(5))/2 is the golden ratio.
Our result implies that to prevent communication of m, the adversary incurs an asymptotically higher cost than the expected cost incurred by either correct player. This property holds even when the receiver suffers a Byzantine fault.  We extend our analysis to multiple receivers and later, to a multi-hop setting where both senders  and  receivers can suffer Byzantine faults. Our work pertains to a wide variety of adversaries that are energy constrained. Notably, we can tolerate an adaptive adversary who launches attacks using knowledge of the past actions of all players. Moreover, in networks with a sufficient amount of communication traffic, we can tolerate a reactive adversary who may detect a transmission in the current time slot and then decide to jam. Finally, we apply our result to the fundamental network communication problem of reliable broadcast which deals with conveying a message from one player to all other players in the network.  In a popular sensor network grid model, we give a reliable broadcast protocol that, in comparison to previous work in the grid, offers improved resilience to DoS attacks.