In one embodiment, a computer-implemented method includes receiving a network graph describing a network having two or more nodes. An application graph is received describing a data stream application. The application graph includes one or more vertices, each corresponding to an operator of the application and associated with a list of nodes. A first vertex of the application graph corresponds to a first operator and is associated with two or more nodes. The application graph is augmented, which includes replicating the first operator such that the augmented graph includes a copy of the first operator at each of the nodes associated with the first vertex. The application is deployed over the network based on the augmented graph, such that a copy of the first operator is deployed at each of the nodes associated with the first vertex. A route through the augmented graph is selected for a data stream.