@article{d56af0f556c444fbb83d29ab93511c5f,
title = "Optimal path selection for minimizing the differential delay in Ethernet-over-SONET",
abstract = "We consider the problem of minimizing the differential delay in a virtually concatenated Ethernet-over-SONET (EoS) system by suitable path selection. In such a system, a service provider can dynamically add virtual channels to or drop them from a Virtually Concatenated Group (VCG). A new virtual channel can be added to the VCG provided that the differential delays between the new channel and the existing ones are within a certain limit that reflects the available memory buffer of the EoS system. We model the problem of finding such a virtual channel as a constrained path selection problem, where the delay of the required (feasible) path is constrained not only by an upper bound but also by a lower bound. We consider two cases: exactly known link delays and imprecisely known link delays. For the first case, we propose two algorithms for finding a feasible path. The first is based on a link metric that linearly combines the original link weight (the link delay) and its inverse. The theoretical properties of such a metric are studied and used to develop a highly efficient heuristic for path selection. The second algorithm is a {"}backward-forward{"} heuristic in which the nodes in the graph are prelabeled during the backward phase. The labels are then used in the forward phase to identify a feasible path. For the imprecise-link-state case, the problem is modeled as one of finding the most probable feasible path, where link weights are random variables. A {"}backward-forward{"} heuristic is proposed which again uses prelabeling of the graph in the backward direction followed by a forward search that attempts to minimize an objective function. Simulations are conducted to evaluate the performance of the proposed algorithms and to demonstrate the advantages of the probabilistic path selection approach over the classic trigger-based approach.",
keywords = "Differential delay, Ethernet-over-SONET/SDH, Path selection, Virtual concatenation",
author = "Satyajeet Ahuja and Marwan Krunz and Turgay Korkmaz",
note = "Funding Information: This work was supported by NSF under grants ANI-0095626, ANI-0313234, and ANI-0325979, and by the Center for Low Power Electronics (CLPE) at the University of Arizona. CLPE is supported by NSF (Grant # EEC-9523338), the State of Arizona, and a consortium of industrial partners. Any opinions, findings, conclusions, and recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the NSF. An abridged version of this paper was presented at the International Conference on Computer Communications and Networks (ICCCN), Chicago, USA, October 11–13, 2004. Funding Information: Marwan Krunz is an associate professor of electrical and computer engineering at the University of Arizona and is the director of the broadband networking and wireless communications laboratory. He received his Ph.D. degree in EE from Michigan State University in 1995. After a brief stint as a postdoctoral researcher at the Department of Computer Science, the University of Maryland, College Park, he joined the University of Arizona in January of 1997. He held visiting research positions at INRIA (Sophia Antipolis, France), HP Labs (Palo Alto, California), and US West (now Qwest) Advanced Technologies (Boulder, Colorado). His research interests lie in the fields of computer networking and wireless communications. His recent research includes power/rate control for ad hoc and sensor networks, medium access and routing protocols, media streaming over wireless channels, quality of service (QoS) routing, optical networking, and characterization of web traffic and its applications in the design of efficient web caching/prefetching policies. He previously worked on traffic analysis and performance evaluation, packet video modeling, and QoS provisioning in high-speed networks. He has published more than 90 journal articles and refereed conference papers in these areas, and has filed three US patent applications. His research has been funded by several federal grants and industrial contracts. He is a recipient of the National Science Foundation CAREER Award. He currently serves on the editorial board for the IEEE/ACM Transactions on Networking and the Computer Communications Journal. He was a guest co-editor for special issues in IEEE Micro and IEEE Communications Magazines. He served as a technical program chair for the IEEE INFOCOM 2004 Conference, the IEEE International Conference on Sensor and Ad hoc Communications and Networks (SECON 2005), and the 9th Hot Interconnects Symposium. He currently serves as a TPC chair for the IEEE WoWMoM 2006 Conference, to be held in Buffalo, New York, June 2006. He has served and continues to serve on the executive and technical program committees of numerous conferences and on the panels of several NSF directorates. ",
year = "2006",
month = sep,
day = "15",
doi = "10.1016/j.comnet.2005.09.034",
language = "English (US)",
volume = "50",
pages = "2349--2363",
journal = "Computer Networks",
issn = "1389-1286",
publisher = "Elsevier",
number = "13",
}