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.
Oblivious routing approaches to network optimization have been used in many different contexts from switching ( @cite_23 @cite_28 @cite_4 ) to overlay networks ( @cite_27 @cite_26 ), or fundamental tradeoffs in distributed computing @cite_24 @cite_17 to name a few. In each case mentioned above, the primary performance measure is network congestion (or its dual problem throughput). In fact, one could summarize the early work by Valiant, Borodin and Hopcroft as saying that randomization is necessary and sufficient for oblivious routing to give @math congestion in many packet network topologies; @math being the number of nodes.
@cite_26 @cite_4 @cite_28 @cite_24 @cite_27 @cite_23 @cite_17
2117358494 2119016372 2107997203 2085399064 2145818650
Routers built around a single-stage crossbar and a centralized scheduler do not scale, and (in practice) do not provide the throughput guarantees that network operators need to make efficient use of their expensive long-haul links. In this paper we consider how optics can be used to scale capacity and reduce power in a router. We start with the promising load-balanced switch architecture proposed by C-S. Chang. This approach eliminates the scheduler, is scalable, and guarantees 100 throughput for a broad class of traffic. But several problems need to be solved to make this architecture practical: (1) Packets can be mis-sequenced, (2) Pathological periodic traffic patterns can make throughput arbitrarily small, (3) The architecture requires a rapidly configuring switch fabric, and (4) It does not work when linecards are missing or have failed. In this paper we solve each problem in turn, and describe new architectures that include our solutions. We motivate our work by designing a 100Tb s packet-switched router arranged as 640 linecards, each operating at 160Gb s. We describe two different implementations based on technology available within the next three years. Link bundling is a way to increase routing scalability whenever a pair of label switching routers in MPLS are connected by multiple parallel links. However, link bundling can be inefficient as a label switched path (LSP) has to be associated with a particular link. In this paper, we show that the efficiency of link bundling can be significantly improved if traffic can be effectively distributed across the parallel links. We propose an IP switch architecture that is capable of distributing flows both inside the switch and among the parallel links based on operations that are relatively simple to implement. The switch requires no speedup, guarantees in-sequence packet delivery for a given flow, avoids complex coordination algorithms, and can achieve LSP throughput higher than the line rate. By means of simulation using IP traces, we investigate the performance of the proposed switch, and show that the switch achieves good load-balancing performance. We describe extensions to the basic architecture which allows for very large bundle size, handles incremental upgrade strategy, improves reliability, and accommodates nonIP traffic. Consider @math nodes connected by wires to make an n-dimensional binary cube. Suppose that initially the nodes contain one packet each addressed to distinct nodes of the cube. We show that there is a distributed randomized algorithm that can route every packet to its destination without two packets passing down the same wire at any one time, and finishes within time @math with overwhelming probability for all such routing requests. Each packet carries with it @math bits of bookkeeping information. No other communication among the nodes takes place.The algorithm offers the only scheme known for realizing arbitrary permutations in a sparse N node network in @math time and has evident applications in the design of general purpose parallel computers. Parallel communication algorithms and networks are central to large-scale parallel computing and, also, data communications. This paper identifies adverse source-destination traffic patterns and proposes a scheme for obtaining relief by means of randomized routing of packets on simple extensions of the well-known omega networks. Valiant and Aleliunas have demonstrated randomized algorithms, for a certain context which we call nonrenewal, that complete the communication task in time O (log N ) with overwhelming probability, where N is the number of sources and destinations. Our scheme has advantages because it uses switches of fixed degree, requires no scheduling, and, for the nonrenewal context, is as good in proven performance. The main advantage of our scheme comes when we consider the renewal context in which packets are generated at the sources continually and asynchronously. Our algorithm extends naturally from the nonrenewal context. In the analysis in the renewal context we, first, explicitly identify the maximum traffic intensities in the internal links of the extended omega networks over all source-destination traffic specifications that satisfy loose bounds. Second, the benefits of randomization on the stability of the network are identified. Third, exact results, for certain restricted models for sources and transmission, and approximate analytic results, for quite general models, are derived for the mean delays. These results show that, in the stable regime, the maximum mean time from source to destination is asymptotically proportional to log N . Numerical results are presented. A principle task in parallel and distributed systems is to reduce the communication load in the interconnection network, as this is usually the major bottleneck for the performance of distributed applications. We introduce a framework for solving online problems that aim to minimize the congestion (i.e. the maximum load of a network link) in general topology networks. We apply this framework to the problem of online routing of virtual circuits and to a dynamic data management problem. For both scenarios we achieve a competitive ratio of O(log sup 3 n) with respect to the congestion of the network links. Our online algorithm for the routing problem has the remarkable property that it is oblivious, i.e., the path chosen for a virtual circuit is independent of the current network load. Oblivious routing strategies can easily be implemented in distributed environments and have therefore been intensively studied for certain network topologies as e.g. meshes, tori and hypercubic networks. This is the first oblivious path selection algorithm that achieves a polylogarithmic competitive ratio in general networks.