Robust Solutions for the WDM Routing and Provisioning Problem: Models, Algorithms and Software
Jeffery L. Kennington
And
Eli V. Olinick
All-optical networks with wavelength division multiplexing (WDM) capabilities are prime candidates for future long haul and metro data networks. The simplified processing and management of these very-high-bandwidth networks make them very attractive. It is anticipated that these networks will be used for vital commercial transactions such as order processing and inventory control (e-Commerce) as well as for voice communication. Many of the companies in the Richardson Telecom Corridor are involved in the design, development, and deployment of these networks. In order to meet customer demand for information services with high reliability and fast response times, WDM networks must be fault-tolerant. To be economically viable, they must be efficiently designed. The objective of our research program is to develop the methodology and prototype software tools for designing and provisioning state-of-the-art WDM networks.
Designing the least-cost, fault-tolerant WDM network to satisfy a given set of point-to-point demands between customer sites can be quite challenging. Typical design parameters include the location of the physical links between the customer sites on the network, the number of fibers to be used on each link, the number of channels to be used on each fiber, the number of optical amplifiers and regenerators needed to support the channels, and the location of line terminating equipment required to support the point-to-point demands. In addition to determining the physical infrastructure of the network, a complete design must also specify routings for the anticipated traffic. In some applications, the user requires spare capacity in the network along with a protection strategy to guard the network against node and/or link failures.
Given the costs of the equipment mentioned above, an optimization model can be constructed to help select a minimum-cost design and routing assignment for some demand forecast.
Since growth in this industry is difficult to predict there is concern that an optimal design for an erroneous forecast may prove to be inferior. If the forecast is too low, the network will not have enough capacity to handle the demand and network owner will likely lose business. Conversely, a network designed for forecast that turns out to predict more demand than is realized will be over provisioned with expensive, underutilized equipment.
In this investigation we are developing a design methodology that accounts for the uncertainty in the demand forecasts in the case where protection is not required. We call our strategy a robust design methodology for optical network provisioning. A robust design is one that will work well over a wide range of possible demand scenarios. Our optimization models account for the uncertainty in the future demands in a new and unique way. Using state-of-the-art mathematical modeling and optimization software systems we are currently analyzing test cases to evaluate our approach as compared to the traditional techniques.
Jeffery L. Kennington is a Professor in the Department of Engineering Management, Systems and Information at SMU, where he specializes in the design and analysis of algorithms for telecommunication problems. He has served as a consultant for MCI where he assisted in the development of software tools for their real-time restoration project. He is currently an Associate Editor for Telecommunication Systems, an Associate Editor for Networks, and is on the Editorial Board of Computational Optimization and Applications. His publications include over 45 referred journal articles; he has been the PI for over $2.3 million in research grants, and computer software developed by his research group has been used worldwide. In addition, he frequently teaches a sophomore level course in C programming and is the recipient of the outstanding undergraduate teaching award for the years 1997, 1998, and 1999. Professor Kennington is the author (with R. V. Helgason) of the John Wiley book, Algorithms for Network Programming, and are co-editor (with R. Barr and R. V. Helgason) of the Kluwer book, Interfaces in Computer Science and Operations Research: Advances in Metaheuristics, Optimization, and Stochastic Modeling Techniques.
Eli V. Olinick is an Assistant Professor in the Department of Engineering Management, Systems and Information at SMU. He completed his B.S. in Applied Mathematics (1989) at Brown University and earned his M.S. (1994) and Ph.D. (1999) in Industrial Engineering and Operations Research at the University of California at Berkeley where he wrote his Ph.D. thesis on "Optimization Algorithms for Survivable Network Design Problems." His research interests are in applied optimization and network design problems. As a graduate student at Berkeley, he was an active member of the Remote Interactive Optimization Testbed (http://riot.ieor.berkeley.edu) developing optimization applications on the World Wide Web. He has taught courses in linear programming, operations research models, and engineering economics at SMU and Berkeley. He received the Alpha Pi Mu and Academic Senate Outstanding Graduate Student Instructor awards at Berkeley in 1998.
Projects
2002-2003
2001-2002
Technical Reports
Special Emphasis
