Throughput-Optimal Routing in Adversarial Networks.

摘要

Reliance on networks as a means to transmit communication between sources has exploded in the past two decades, e.g. via wireless networks, satellite communication, and the Internet. With such a pervasive presence in our every day lives, it is not surprising that there has been a corresponding explosion in research concerned with routing protocols that perform well in a variety of network settings. Motivated by understanding theoretical bounds in routing performance, we explore in this dissertation the feasibility of routing in highly unreliable networks.;We begin by modeling a network as a graph with vertices representing nodes and edges representing the links between them, and consider two forms of unreliability: unpredictable edge-failures, and deliberate deviation from protocol specifications by corrupt nodes. The first form of unpredictability represents networks with dynamic topology, whose links may be constantly going up and down; while the second form represents malicious insiders attempting to disrupt communication by deliberately disobeying routing rules, by e.g. introducing junk messages or deleting or altering messages. Within these networks, we focus on end-to-end communication between a sending node and a receiving node, and evaluate routing protocols on the basis of through-put performance.;This dissertation is split between four main chapters, representing four different network models demonstrating increasing levels of unreliability. The first of these is a synchronous network consisting of honest nodes and with dynamic topology (with certain connectivity assumptions which restrict the frequency of link failures between nodes). In this network setting, we present a routing protocol that enjoys provably optimal throughput performance. The next chapter allows for corrupt nodes, and we present a protocol that (asymptotically) matches the throughput performance of the optimal protocol in the honest node network model, concluding that the extra security against misbehaving nodes can be achieved "for free.";Motivated by the fact that most networks encountered in practice are asynchronous, we next consider a network model that demonstrates both asynchronicity as well as eliminating the connectivity assumptions , but assumes that the nodes in the network behave honestly . Because no connectivity assumptions are made in this network setting, an absolute guarantee of throughput performance is not possible. Instead, we utilize competitive analysis to measure the efficiency of a given protocol by comparing its performance to that of an ideal off-line protocol, the latter having perfect information to future edge failures and able to route optimally based on this extra information. We use competitive analysis to prove matching upper and lower bounds on achievable throughput performance in this network setting.;Finally, we combine our results of the above network models to construct a protocol for a network model that simultaneously demonstrates all forms of unreliability: asynchronous, local control, dynamic topology with no connectivity assumptions, and susceptible to malicious nodes. We construct a routing protocol for this highly unreliable network setting, and use competitive analysis to prove this protocol achieves optimal throughput performance.