Secure Overlay Network Design∗

Due to the increasing security threats on the Internet, new overlay network architectures have been proposed to secure privileged services. In these architec-tures, the application servers are protected by a defense perimeter where only traffic from entities called servlets are allowed to pass. End users must be autho-rized and can only communicate with entities called access points (APs). APs relay authorized users ’ requests to servlets, which in turn pass them to the servers. The identity of APs are publicly known while the servlets are typically secret. All communications are done through the public Internet. Thus all the entities involved form an overlay network. The main component of this distributed sys-tem consists of n APs and m servlets. A design for a network is a bipartite graph with APs on one side, and the servlets on the other side. If an AP is compromised by an attacker (or fails), all the servlets that are connected to it are subject to attack. An AP is blocked, if all servlets connected to it are subject to attack. We consider two models for the failures: In the stochastic model, w