We study a class of robust network design problems motivated by the need to scale core networks to meet increasingly dynamic capacity demands. Past work has focused on designing the network to support all hose matrices (all matrices not exceeding marginal bounds at the nodes). This model may be too conservative if additional information on traffic patterns is available. Another extreme is the fixed demand model, where one designs the network to support peak point-to-point demands. We introduce a capped hose model to explore a broader range of traffic matrices which includes the above two as special cases. It is known that optimal designs for the hose model are always determined by single-hub routing, and for the fixed- demand model are based on shortest-path routing. We shed light on the wider space of capped hose matrices in order to see which traffic models are more shortest path-like as opposed to hub-like. To address the space in between, we use hierarchical multi-hub routing templates, a generalization of hub and tree routing. In particular, we show that by adding peak capacities into the hose model, the single-hub tree-routing template is no longer cost-effective. This initiates the study of a class of robust network design (RND) problems restricted to these templates. Our empirical analysis is based on a heuristic for this new hierarchical RND problem. We also propose that it is possible to define a routing indicator that accounts for the strengths of the marginals and peak demands and use this information to choose the appropriate routing template. We benchmark our approach against other well-known routing templates, using representative carrier networks and a variety of different capped hose traffic demands, parameterized by the relative importance of their marginals as opposed to their point-to-point peak demands.
Our work was partly motivated by work in @cite_1 , where Selective Randomized Load Balancing ( @math ) is used to design minimum- cost networks. They showed that networks whose design is based on oblivious routing techniques (and specifically @math ) can be ideal to capture cost savings in IP networks. This is because optimal designs reserve capacity on long paths, where one may employ high-capacity optical circuits, and partially avoid expensive IP equipment costs at internal nodes (their empirical study incorporated IP router, optical switching, and fiber costs). In this paper, instead of a design based on hub routing to a small number of hubs, we consider more general @math , as discussed in @cite_12 .
@cite_1 @cite_12
2076704288 2963728009 2121223271 2132734927
We consider the problem of building cost-effective networks that are robust to dynamic changes in demand patterns. We compare several architectures using demand-oblivious routing strategies. Traditional approaches include single-hop architectures based on a (static or dynamic) circuit-switched core infrastructure and multihop (packet-switched) architectures based on point-to-point circuits in the core. To address demand uncertainty, we seek minimum cost networks that can carry the class of hose demand matrices. Apart from shortest-path routing, Valiant's randomized load balancing (RLB), and virtual private network (VPN) tree routing, we propose a third, highly attractive approach: selective randomized load balancing (SRLB). This is a blend of dual-hop hub routing and randomized load balancing that combines the advantages of both architectures in terms of network cost, delay, and delay jitter. In particular, we give empirical analyses for the cost (in terms of transport and switching equipment) for the discussed architectures, based on three representative carrier networks. Of these three networks, SRLB maintains the resilience properties of RLB while achieving significant cost reduction over all other architectures, including RLB and multihop Internet protocol multiprotocol label switching (IP MPLS) networks using VPN-tree routing. We consider load balancing in a network of caching servers delivering contents to end users. Randomized load balancing via the so-called power of two choices is a well-known approach in parallel and distributed systems. In this framework, we investigate the tension between storage resources, communication cost, and load balancing performance. To this end, we propose a randomized load balancing scheme which simultaneously considers cache size limitation and proximity in the server redirection process. In contrast to the classical power of two choices setup, since the memory limitation and the proximity constraint cause correlation in the server selection process, we may not benefit from the power of two choices. However, we prove that in certain regimes of problem parameters, our scheme results in the maximum load of order @math (here @math is the network size). This is an exponential improvement compared to the scheme which assigns each request to the nearest available replica. Interestingly, the extra communication cost incurred by our proposed scheme, compared to the nearest replica strategy, is small. Furthermore, our extensive simulations show that the trade-off trend does not depend on the network topology and library popularity profile details. This paper deals with throughput scaling laws for random ad hoc wireless networks in a rich scattering environment. We develop schemes to optimize the ratio lambda(n) of achievable network sum capacity to the sum of the point-to-point capacities of source-destinations (S-D) pairs operating in isolation. Our focus in this paper is on fixed signal-to-noise ratio (SNR) networks, i.e., networks where the worst case SNR over the S-D pairs is fixed independent of n. For such fixed SNR networks, which include fixed area networks as a special case, we show that collaborative strategies yield a scaling law of lambda(n)=Omega(1 n1 3) in contrast to multihop strategies which yield a scaling law of lambda(n)=Theta(1 radicn). While networks where worst case SNR goes to zero do not preclude the possibility of collaboration, multihop strategies achieve optimal throughput. The plausible reason is that the gains due to collaboration cannot offset the effect of vanishing receive SNR. This suggests that for fixed SNR networks, a network designer should look for network protocols that exploit collaboration Load balanced routing in a network, i.e., minimizing the maximum traffic load any node carries for unsplittable flows, is a well known NP-hard problem. Finding practical algorithms remains a long standing challenge. In this paper we propose greedy routing using virtual coordinates that achieves both small path stretch ratio (compared to shortest path) and small load balancing ratio (compared to optimal load balanced routing), in a large scale wireless sensor network deployed densely inside a geometric domain with complex shape. We first provide a greedy routing scheme on a disk with a stretch ratio of at most 2, and under which the maximum load is a factor 4√2 smaller than the maximum load under shortest path routing. This is the first simple routing scheme with a small stretch that has been proven to outperform shortest path routing in terms of load balancing. Then we transform a network of arbitrary shape to a disk by an area preserving map φ. We show that both the path length and the maximum traffic load in the original network only increases by an additional factor of d2, where d is the maximum length stretch of φ. Combined with the result on a disk we again achieve both bounded stretch and bounded load balancing ratio. Our simulation results evaluated the practical performance on both quality measures.