Topological properties for a wide area network planning and a dynamic programming approach for designing the access network
A wide area network (WAN) can be considered as a set of sites and a set of communication lines that interconect the sites. Topologically a WAN is organized in two levels: the Backbone Network and the Access Network composed of a certain number of Local Access Network. Each local access network usual...
Guardat en:
| Autor principal: | |
|---|---|
| Format: | masterThesis |
| Idioma: | anglès |
| Publicat: |
2011
|
| Matèries: | |
| Accés en línia: | http://hdl.handle.net/20.500.12008/2963 |
| Etiquetes: |
Sense etiquetes, Sigues el primer a etiquetar aquest registre!
|
| Sumari: | A wide area network (WAN) can be considered as a set of sites and a set of communication lines that interconect the sites. Topologically a WAN is organized in two levels: the Backbone Network and the Access Network composed of a certain number of Local Access Network. Each local access network usually has a tree-like structure, rooted at a single site of the backbone, and connected users (terminal sites) either directly to this backbone site or to a hierarchy of intermediate concentrator sites which are connected to the backbone site. The backbone network has usually a meshed topology, and this purpose is to allow efficient and reliable communication between the switch sites that act as connection points for the local access networks. In this thesis we tackled the problem of designing a WAN by breaking it down into two inter-related sub-problems: the Access Network Design Problem (ANDP) and the Backbone Network Design Problem (BNDP). In both models we considered only the construction costs, e.g. the costs of digging trenches and placing a fiber cable into service. Our aim in this thesis is the study of the ANDP and the BNDP problems. We concentrate on the ANDP with the objective of to propose a new approach for solving this problem. We study differents results related to the topological structure of the ANDP solutions. We present the clustering approach as one of the strategies more frequently used by the commercial tools of the design. We also formulate the ANDP as a Steiner Problem in Graphs (SPG). Given the complexity of the ANDP (the problem belongs to the NP-Hard class); it is very useful to provide techniques capable of reducing the dimension of the original problem to an equivalent smaller problem. After we concentrate on some structural property about the BNDP. Finally we propose recurrences to solve the ANDP and BNDP which are based on Dynamic Programming and Dynamic Programming with Static-Space Relaxation methodology. |
|---|