Computational Optimization Problems in Local Access Networks, SONET Rings and Lightwave

本地接入网络、SONET 环和光波中的计算优化问题

• 批准号: 9301751
• 负责人: Daniel Bienstock
• 金额: $ 26.29万
• 依托单位: Columbia University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1993
• 资助国家: 美国
• 起止时间: 1993-08-01 至 1997-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9301751&HistoricalAwards=false
• 关键词: Computational; Optimization; Problems; Local; Access

9301751 Bienstock The purpose of this research is to develop, implement, and test practical algorithms for optimization problems in various areas of telecommunications. The problems to be studied arise in concrete settings and have the common feature of being extremely intractable from a computational viewpoint; the focus will be on building experimentally practical and theoretically sound algorithms. The first area of interest concerns capacity expansion problems in local access networks. The resulting optimization problems turn out to be rather intractable from the point of view of integer programming. However, we have recently developed a fast and accurate heuristic for a variant of this problem used by Bellcore in its planning; we plan to extend the analysis and the heuristic to handle more complex and detailed models. The second problem area is that of SONET rings. This is an emerging field which will be for increasing importance in the near future, and there are many important optimization problems that arise in this context (for example, the assignment of capacity to a given ring sa as to handle traffic requests between the nodes in the ring). The last problem area concerns lightwave networks. A problem that has received some attention is that of assigning frequencies to the transmitters and receivers in a network, and then to route traffic requests in the resulting logical network, sa as to achieve minimum congestion over all possible frequency assignments and routings. This is an extremely intractable optimization problem; nevertheless, preliminary experience with a special-purpose algorithm has been encouraging. The approach for studying these problems will encompass both the theoretical analysis needed to develop new tools, and , building upon successful recent work, the implementation of resulting algorithms, with added emphasis on speed and practicality of the resulting code. ***

9301751 Bienstock本研究的目的是开发、实现和测试用于电信各个领域优化问题的实用算法。所要研究的问题产生于具体环境中，从计算的角度来看具有极其棘手的共同特征；重点将是建立实验实际和理论上合理的算法。第一个感兴趣的领域涉及本地接入网的容量扩展问题。从整数规划的角度来看，所得到的优化问题是相当棘手的。然而，我们最近开发了一种快速而准确的启发式，用于Bellcore在其规划中使用的这个问题的变体；我们计划扩展分析和启发式来处理更复杂和详细的模型。第二个问题领域是SONET环。这是一个新兴的领域，在不久的将来会变得越来越重要，在这种情况下会出现许多重要的优化问题（例如，将容量分配给给定的环，以处理环中节点之间的流量请求）。最后一个问题涉及光波网络。一个受到一定关注的问题是为网络中的发射器和接收器分配频率，然后在由此产生的逻辑网络中路由流量请求，以便在所有可能的频率分配和路由上实现最小的拥塞。这是一个极其棘手的优化问题；然而，特殊用途算法的初步经验令人鼓舞。研究这些问题的方法将包括开发新工具所需的理论分析，以及建立在最近成功的工作基础上的最终算法的实现，并强调最终代码的速度和实用性。＊＊＊