Service providers are starting to offer next-generation E-Line (point-to-point) and E-LAN (multipoint-to-multipoint) Ethernet services over their existing SONET/SDH networks. While Ethernet typically is "best-effort", these emerging services are expected to be "carrier-class" with strict bandwidth guarantees. Consequently, spanning tree creation, critical to any Ethernet network is fundamentally changed; each tree hop now needs to have sufficient capacity to meet the requisite bandwidth demands. In this paper, we introduce the bandwidth-endowed spanning tree (BEST) problem. Unlike the polynomial complexity of standard spanning tree algorithms, BEST is NP-complete, raising questions about the scalability of these services. We propose offline and online algorithms and study their performance using extensive simulations. We show that leveraging the Virtual Concatenation protocol (ITU-T G.707) is key to practical algorithms that are both effective and efficient. Inspite of the theoretical hardness, the online algorithms we propose are a good match to "optimal", offline integer programming benchmarks, demonstrating the viability of next-generation Ethernet services.

The virtual concatenation protocol in SONET/SDH has ushered in a novel routing paradigm that enables a circuit to be "split" and routed over multiple paths. However, this diverse routing causes differential delay among the paths which can impact service if not accounted for in the routing. In this paper, we introduce the differential delay aware routing problem and show that it is not only NP-complete but is also provably hard to approximate within a constant factor. However, by transforming it into a flow routing formulation, we can derive effective, practical solutions. We present various algorithms and use extensive simulations to show that they are a good match to an "ideal" integer linear programming formulation. We also highlight how the differential delay data allows individual link delays to be reverse-engineered. We propose three algorithms to derive link delays including one that leverages the flexibility in the virtual concatenation protocol bits. Given the rise of next-generation applications such as online games where latency information is key, this knowledge of link delays, heretofore only loosely approximated, enables the telecom infrastructure to be more effective in supporting these applications.

We investigate the problem of precomputing bandwidth guaranteed paths as a cheaper replacement for on-demand routing. The focus in the prior precomputation literature has been on minimizing storage and computational overhead of the precomputation process. This paper instead explores the "quality" of precomputed paths and attempts to answer the following question: given a traffic ingress-egress node pair and storage for k routes, what paths should be materialized for good routing performance? We argue that the min-hop formulation typically assumed in prior precomputation work is a poor offline strategy. We instead propose an efficient maxflow based algorithm called MobiFlow. We show via simulations that it outperforms min-hop algorithms such as K-shortest path on several metrics including number of requests rejected and the fraction of the bandwidth routed. Furthermore, the algorithm has a low computational complexity and degrades gracefully on network failures, making it very attractive to implement in practice.

We study the problem of bandwidth fragmentation in links that comprise rings and meshes in SONET networks. Fragmentation is a serious challenge for network operators since it creates "holes" in the transport pipe causing new demands to be rejected, in spite of sufficient bandwidth being available. Unlike the well-studied, general fragmentation problem, link defragmentation is "hard" and novel due to some unique constraints imposed by the SONET standard. Since a defragmentation operation typically occurs on a network carrying live traffic, in addition to the "quality" of the output, any link defragmentation algorithm has to avoid traffic hit and also optimize the "cost" of reorganizing circuits. We propose an algorithm called mobipack that is optimal in its defragmentation quality. Moreover, we demonstrate via extensive simulations, that it also achieves its goal in a hitless manner with only marginal additional cost over the optimal, making it extremely attractive to use in practice

This paper addresses the issue of reliable transport of emerging data services in Ethernet over SONET (EoS) networks that require protection guarantees beyond standard best effort delivery. We argue that the current consensus of using Ethernet spanning tree and a SONET 1+1 protection, while providing reliability, is an inefficient use of resources. Instead, we claim that EoS opens novel opportunities for protection heretofore unavailable in other environments. In particular, the deployment of virtual concatenation and LCAS protocols enables "route splitting", creating a fundamentally new routing paradigm for circuit-switched environments. We propose a scheme called PESO, appropriate for EoS, with innovative routing, failure notification and switching components. More importantly, it is competitive with SONET protection without its 100% bandwidth overhead. We also suggest a enhancement in LCAS that can further improve PESO'S switching time. PESO leverages the underlying protocols, making it extremely attractive to implement and use in practice.

Shrinking capital expenditure budgets are forcing telecom service providers to explore engineering tools that extract greater utilization from their existing transport infrastructure. In this paper, we explore the challenges in engineering SONET rings to support higher traffic volumes. Unlike network design tools, engineering operations have to reconfigure live traffic and do so in a hitless manner. We present an efficient algorithm called MobiRing that accounts for the unique constraints imposed by the SONET standard. In spite of the hardness of the optimization problems, we show using extensive simulations that the greedy approach of MobiRing performs extremely well. More importantly, MobiRing is able to achieve hitless reconfigurations and therefore, very attractive to use in practice. This ability to do effective, hitless engineering opens the possibility that network engineering, traditionally a very infrequent operation, can now be done proactively to maintain high levels of network utilization.

MPLS traffic engineering has primarily focused on efficient route setups. However, as data traffic explodes, there is an increased demand for tools that enable network-wide tuning in order to maintain high levels of end-to-end network efficiency. Network tuning aims to pro-actively reconfigure traffic without causing any service disruption. In this paper, we explore the requirements on management systems to support tuning. Network design tools have similar goal; however, the additional requirement for online, hitless optimization fundamentally differentiates tuning from traditional network design. We present an efficient algorithm for network tuning called MobiTree. Using extensive simulation results, we show that the greedy approach in MobiTree outperforms prior traffic design schemes. More importantly, it achieves the gains while ensuring a hitless reconfiguration. Given its low overhead, we propose MobiTree as an effective solution to implement in practice.

The problem of routing bandwidth guaranteed paths in wavelength-routed, WDM optical mesh networks is explored. A WDM mesh network offers great flexibility in dynamically reconfiguring the optical core to match the IP layer demands. In this paper, we argue that IP subnets can limit the reconfigurability potential of the WDM mesh network. We show that finding the shortest IP-hop path, normally admitting a straightforward polynomial solution on the WDM mesh, is NP-hard in the presence of subnets. We propose a new algorithm called MobiTwist that finds the optimal shortest path when accounting for subnets. We also observe that subnets impose a routing penalty by forcing longer paths for bandwidth demands. Consequently, they create a trade-off between lower network efficiency if subnets are honored (due to longer paths) or, an upfront overhead of dynamically changing subnets to derive shorter paths. We propose the MobiFlex algorithm that attempts to achieve a balance by finding the shortest path given an upper limit on the number of subnet violations acceptable. The inherent hardness of the routing problem due to subnets precludes a solution with low worst-case complexity. However, we present performance results that show that both the algorithms proposed are extremely efficient in routing demands, and in practice, do so in polynomial time.