Galaxy: adaptive client-server load balancing on bounded-degree network overlays

In this work we describe the Galaxy system which enables communication between disconnected computers by providing a set of public waypoints which accept incoming data from sources and subsequently relay the data to destinations. A prototype of this system has been built which has a Windows Explorer frontend interface and Java-based relay server code deployed on the global PlanetLab network. The primary focus of this thesis is the theoretical analysis of the Galaxy distributed loadbalancing algorithm which attempts to maximize the throughput of the system and provide a measure of fairness to each Galaxy client. The analysis is carried out by first modeling the Galaxy system network as a bipartite graph G = (U ∪ V, E) where each communicating sender/receiver pair is a single node u ∈ U, each node v ∈ V is a relay, and each edge e = (u, v) represents a network connection between a client u and proximate relay v. We call degree-bounded bipartite graphs with maximum client out-degree Δ and minimum relay in-degree δ as “(Δ, δ) Dual Bounded”. We show that on (Δ, δ) Dual Bounded networks the Galaxy load-balancing algorithm always reaches at least a fraction of optimal equal to min(1, D2-d2D2 -dD-D ) and that this bound is tight. Further, we show that the Galaxy load-balancing algorithm converges in O(|U|) rounds and achieves constant-competitiveness in only O(log(Δ)) time rounds. This result suggests that (1) we minimize the number of relays to which each client may connect and maximize the number of clients to which each relay is connected, and (2) provides exact bounds on throughput and the time required to reach convergence as functions of the structure of the network. In addition to being useful for our Galaxy system, the throughput bound given above is also applicable to other distributed Internet services which use TCP/IP.