Minimum concave cost multicommodity network design

Download

index.pdf

Date

2005

Author

Say, Fatih

Metadata

Show full item record

Item Usage Stats

238
views

134
downloads

Minimum Concave Cost Multicommodity Network Design Problem arises in many application areas, such as transportation planning, distributed energy system and especially both circuit and packet switching backbone network design. Exact concave optimization algorithms have been developed, but these methods are applicable if the network size is small. Therefore, these problems are usually solved by non-exact iterative methods. In this thesis work, methods proposed for circuit switching and packet switching network design are evaluated in detail. After a comprehensive literate survey, Yaged̕s Linearization, Minoux greedy and Minoux accelerated greedy methods are found to be applicable to circuit switching network design when both solution quality and computational time is considered. Previously, it has been found that Minoux greedy methods may create routings with cycles and in order to eliminate these cycles a modification has been proposed. In this work, this modification is extended and evaluated in detail. Similarly, Gerla and Kleinrock̕s Concave Branch Elimination, Gersht̕s greedy and Stacey̕s Concave Link Elimination methods are investigated within the context of packet switching network design. All of these methods consider aggregate flows on each link simultaneously re-routing more than one commodity in one step. This thesis work also considers an alternative disaggregate approach, where only one commodity is handled at a time. Finally, algorithms proposed for circuit switching network design problem are adapted to the packet switching case and an extensive comparative computational study is performed to point out the best method with respect to time and solution quality for a number of networks and cost structure. Computational results have shown that modification on Minoux greedy to eliminate cycles leads to considerable improvements and the disaggregate approach

Subject Keywords

Computer engineering.

URI

http://etd.lib.metu.edu.tr/upload/12606432/index.pdf
https://hdl.handle.net/11511/15469

Collections

Graduate School of Natural and Applied Sciences, Thesis

Suggestions

OpenMETU
Core

Minimum concave cost multicommodity network design Bazlamaçcı, Cüneyt Fehmi (Springer Science and Business Media LLC, 2007-12-01) The minimum concave cost multicommodity network design problem (MCMNDP) arises in many application areas, such as transportation planning, energy distribution systems and especially in the design of both packet and circuit switching backbone networks. Exact concave cost optimization algorithms have been developed but they are applicable only if the network size is small. Therefore, MCMNDP is usually solved using non-exact iterative methods. In this paper, such heuristic techniques proposed within the contex...
Performance evaluation of routing protocols in wireless ad hoc networks with service differentiation Yılmaz, Semra; Koçyiğit, Altan; Erten, Murat; Department of Information Systems (2003) An ad hoc network is a collection of wireless mobile nodes dynamically forming a temporary network without the use of any fixed network infrastructure or centralized administration. Due to the limitations in the wireless environment, it may be necessary for one mobile host to enlist the aid of other hosts in forwarding a packet to its destination. In order to enable communication within the network, a routing protocol is needed to discover routes between nodes. The primary goal of ad hoc network routing pro...
Software implementations of QoS scheduling algorithms for high speed networks / Pehlivanlı, Aydın; Schmidt, Şenan Ece; Department of Electrical and Electronics Engineering (2015) The end to end Quality of Service (QoS) support for the dominating multimedia traffic in the contemporary computer networks is achieved by implementing schedulers in the routers and deploying traffic shapers. To this end, realistic modeling and simulation of these components is essential for network performance evaluation. The first contribution of this thesis is the design and implementation of a C++ simulator QueST (Quality of Service simulaTor) for this task. QueST is a modular cycle accurate simulator w...
A new approach for the scalable intrusion detection in high-speed networks Şahin, Ümit Burak; Schmidt, Şenan Ece; Department of Electrical and Electronics Engineering (2007) As the networks become faster and faster, the emerging requirement is to improve the performance of the Intrusion Detection and Prevention Systems (IDPS) to keep up with the increased network throughput. In high speed networks, it is very difficult for the IDPS to process all the packets. Since the throughput of IDPS is not improved as fast as the throughput of the switches and routers, it is necessary to develop new detection techniques other than traditional techniques. In this thesis we propose a rule-ba...
Routing optimization methods for communication networks Demircan, Ahmet Emrah; Leblebicioğlu, Mehmet Kemal; Department of Electrical and Electronics Engineering (2005) This study discusses the routing optimization techniques and algorithms for communication networks. Preventing data loss on overloaded communication links and utilizing link bandwidths efficiently are the main problems of traffic engineering. Load balancing and routing problems are solved using both by heuristics such as genetic algorithms, and simulation techniques. These algorithms work on destination-based or flow-based routing techniques and mainly change the link weight system or try to select the best...

Citation Formats

F. Say, “Minimum concave cost multicommodity network design,” M.S. - Master of Science, Middle East Technical University, 2005.