|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
540:691 SEMINAR IN INDUSTRIAL & SYSTEMS ENGINEERING |
|
|
Some
Combinatorial Optimization Problems Dr.
Mauricio G. C. Resende Abstract: Combinatorial optimization problems are abundant in the telecommunications industry and the successful solution of these problems has played an important role in telecommunications and its widespread use. Optimization arises in problems as varied as planning and design of optical and wireless networks, routing, restoration, network survivability, e-commerce, and search engine design. In this talk, we report on four problems that we have recently come across while working at an industrial research center of a large communications services company. The focus of our research is on developing heuristics to find good-quality solutions for these problems. Telephone migration occurs when an organization upgrades to a newer phone switch (PBX) and needs to move all the phones using the old switch to the new one. PBX switches implement many features in which groups of phones can interact. One example is the "multi-line hunt group" where up to 100 phones are placed in a cycle and any call coming into any phone in the group will cycle through the group until it is answered. Another example is "call pickup" where any phone in the group can answer any call made to other phones in the group. Given a number of periods in which to migrate the phones and a maximum number of phones that can be moved per period, we want to complete the migration process in the time horizon while minimizing the disruption to the features provided by the switches. Traffic migration occurs when traffic is to be moved from an outdated network to a new one. At each time period, a node in the old network is decommissioned and deloaded. i.e. all traffic coming into it or going out of it is moved to a given node in the new network. After a few nodes have been decommissioned, there will be some traffic in the old network, some traffic in the new network, and some traffic between the two networks for which temporary capacity will have to be provided. The objective is to minimize this capacity by determining the order in which the old nodes are decommissioned. The Internet is divided into many routing domains, called autonomous systems. An autonomous system, or simply AS, is a network that consists of routers and links connecting the routers. These ASes interact to control and deliver Internet Protocol (IP) traffic. They typically fall under the administration of a single institution, such as a company, a university, or a service provider. Intra-domain traffic engineering aims to make more efficient use of network resources within an AS. Interior Gateway Protocols such as OSPF (Open Shortest Path First) are commonly used to select the paths along which traffic is routed within an AS. These routing protocols direct traffic based on link weights assigned by the network operator. Each router in the AS computes shortest paths and creates destination tables used to direct each packet to the next router on the path to its final destination. Given a set of traffic demands between origin-destination pairs, the "OSPF weight setting problem" consists in determining weights to be assigned to the links so as to optimize a cost function, typically associated with a network congestion measure. It is also the role of the routing protocol to specify how the network should react to changes in the network topology, such as arc or router failures. In such situations, IP traffic is re-routed through the shortest paths not of one or more "pipes", where pipes can have different capacities and costs. We consider a survivable IP network design problem, where we need to assign OSPF weights and select a subset of pipes to assign to each arc, aiming to produce efficient OSPF-routed networks with minimum total "pipe" cost needed to route the required demand and handle any single arc or router failure.
Speaker is hosted by Wanpracha Chaovalitwongse Tel: 732-445-5469, Email: wchaoval@rci.rutgers.edu
|
||
| CoRE Building |
|
||
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
