Optimal allocation of transmission network capacity

TEKNILLINEN KORKEAKOULU

Teknillisen fysiikan ja matematiikan osasto Teknillisen fysiikan koulutusohjelma

Marko Heino

Verkkokapasiteetin optimaalinen allokointi

Diplomi-insinöörin tutkintoa varten tarkastettavaksi jätetty diplomityö Työn valvoja professori Harri Ehtamo

Työn ohjaajat suunnittelupäällikkö Kauko Pulkkinen diplomi-insinööri Veikko Tahvanainen

TEKNILLINEN KORKEAKOULU DIPLOMITYÖN TIIVISTELMÄ

Tekijä:

Työn nimi:

Päivämäärä: 06.09.1999

Marko Heino

Verkkokapasiteetin optimaalinen allokointi Sivumäärä: 55

Osasto:

Professuuri:

Teknillisen fysiikan ja matematiikan osasto M at-2 Systeemianalyysi ja operaatiotutkimus Työn valvoja:

Työn ohjaajat:

Professori Harri Ehtamo

Suunnittelupäällikkö Kauko Pulkkinen, Sonera Oy

Diplomi-insinööri Veikko Tahvanainen, Sonera Oy

Tietoliikenneverkkojen kapasiteettitarve on viime vuosina kasvanut merkit­

tävästi. Kasvua ovat saaneet aikaan muun muassa Internetin, matkapuhelin­

ten ja laajakaistaisten liittymien yleistyminen. Tulevaisuudessa siirtokapasi­

teetin tarpeen odotetaan kasvavan entisestään. Tietoliikenneverkoista tulee kasvun mukana yhä monimutkaisempia, jolloin niiden suunnitteluun tarvi­

taan automaattisia työkaluja helpottamaan suunnittelutyötä.

Tässä työssä muodostetaan SDH-verkon (Synchronous Digital Hierarchy) kustannusmalli ja kehitetään menetelmä verkkokapasiteetin optimaaliselle mitoitukselle. Menetelmän avulla voidaan suorittaa suunnitteluprosessissa eteentulevia toistuvia laskutoimituksia. Lähtökohtana on joukko tietoliiken­

neyhteyksiä, joille täytyy hakea reitti siirtoverkon yli alkusolmusta loppusoi­

nnuin. Menetelmässä otetaan huomioon myös liikenteen järjestelyistä, var­

mistuksista ja vioittumistodennäköisyyksistä syntyviä lisäehtoja. Menetel­

mällä saadaan muodostettua yksinkertainen ja selkeä verkkorakenne siten, että liikenteelle asetetut ehdot toteutuvat.

Verkonmitoitustehtävä johtaa monihyödykeongelmaan, joka on yleistys ta­

vallisista virtausongelmista. Tässä työssä esitellään monihyödykeongelmien formulointitapoja ja joitakin ongelmien ratkaisemiseen kelpaavia mene­

telmiä. Menetelmistä käsitellään tarkemmin Fordin ja Fulkersonin kehit­

tämä implisiittinen polkujenmuodostusalgoritmi sekä tähän pohjautuvat primaalipartitiointir ja generalized upperbounding -menetelmät.

Menetelmä implementoitiin Microsoft Visual Basicilla ja liitettiin osaksi So­

nera Oy:ssä kehitettyä transmissioverkkojen suunnitteluohjelmaa. Menetel­

mästä on saatu nopea ja käyttökelpoinen työkalu käytännön verkkotopolo- giatarkasteluihin.

Avainsanat: SDH, verkkosuunnittelu, monihyödykevirtausongelmat

HELSINKI UNIVERSITY OF TECHNOLOGY

ABSTRACT OF MASTER’S THESIS

Author:

Title of thesis:

Finnish title:

Date: 06.09.1999 Department:

Chair:

Marko Heino

Optimal allocation of transmission network capacity Verkkokapasiteetin optimaalinen allokointi

Pages: 55___________________________

Department of Engineering Physics and Mathematics Mat-2 Systems Analysis and Operations Research Supervisor: Professor Harri Ehtamo

Instructors: Network planning manager Kauko Pulkkinen, Sonera Ltd Master of Science Veikko Tahvanainen, Sonera Ltd_____

Demand for telecommunication network capacity has recently grown signi­

ficantly. This growth has been caused, for example, by expanding of the Internet, mobile telephones and broadband services. It is expected that the need for transmission capacity will be even higher in the future. Therefore, networks are going to be so complicated that computer tools are needed in the network design process.

To help the network planning, a method for dimensioning of a SDH-network (Synchronous Digital Hierarchy) is presented. In the method a predefined group of logical connections is routed across the network from one node to another. Furthermore, some special conditions rosen from traffic arrange­

ments, different types of protections and failure probabilities are included in the model. Thus, the main task is to dimension the transmission capacity so that the requirements are fulfilled.

Network dimensioning problem belongs to multicommodity network flow (MCNF) problems, which are generalizations of ordinary network flow problems. In this thesis some alternative formulations for the MCNF problems are presented. Several methods for solving the problem are int­

roduced focusing on Implicit path generation, primal partitioning and gene­

ralized upperbounding. The two latter methods are strongly based on the first one.

The network dimensioning method presented in this thesis is included in a transmission network planning system developed in Sonera. In practice, the method has turn out to be quick and useful for network topology analyses.

Keywords: SDH, network design, multicommodity network flow

Alkusanat

Tämä työ on tehty Sonera Oy: n Verkkopa]velut-divisioonan Verkosto-yksikössä Helsingissä.

Haluan kiittää työni valvojaa, professori Harri Ehtamoa, hänen esittämistään arvokkaista ehdotuksista.

Työni ohjauksesta kiitän esimiestäni, suunnittelupäällikkö Kauko Pulkkista, sekä diplomi-insinööri Veikko Tahvanaista. Kiitän heitä myös kärsivällisyydestä luke­

mattomia kysymyksiäni kohtaan. Lisäksi haluan esittää kiitokseni kaikille muil­

lekin työhöni vaikuttaneille työkavereilleni.

Työni oikolukemisesta, neuvoista ja kannustuksesta haluan kiittää hyvää ystä­

vääni Niko Tyniä.

Lopuksi kiitän rakasta vaimoani Maria suuresta tuesta ja rohkaisusta, joka auttoi hankalimpien vaiheiden yli.

Helsingissä 6. syyskuuta 1999

Marko Heino

Sisältö

Tiivistelmä... i

Abstract... Ü Alkusanat... lii Sisältö... iv

Lyhenneluettelo... vii

1 Johdanto 1 2 Monihyödykevirtausongelmat 5 2.1 Yhden hyödykkeen virtausongelmat... 5

2.2 Monen hyödykkeen virtausongelmat... 7

2.3 Formulointi... 8

2.4 Ratkaisutapoja... 11

2.4.1 Implisiittinen sarakkeenmuodostus ... 12

2.4.2 Resurssiohjaava dekompositio... 15

2.4.3 Primaalipartitiointi... 16

2.4.4 Generalized upperbounding... 19

3 Kokonaislukuoptimointimenetelmät 22 3.1 Yleistä... 22

3.2 Branch and bound -menetelmät... 23

3.3 Dijkstran minimipolkualgoritmi... 26

4 Kapasiteetin allokointiongelma 28 4.1 Taustaa... 28

4.2 SDH-verkon rakenne... 29

4.3 Verkkosuunnittelussa huomioitavia asioita... 32

4.4 SDH-verkon mitoitusmalli... 36

4.4.1 Vaihe I: SDH-ylätason muodostus... 38

4.4.2 Vaihe II: VC-4 -yhteyksille kiinteästi varattu kapasiteetti . 39 4.4.3 Vaihe III: Restoration-varmistuksen vaatima kapasiteetti . 41 4.5 Varmistuksen toteutus alemmalla tasolla... 44

5 Menetelmän toteutus ja tulokset 46

6 Johtopäätökset 53

Viitteet 56

Liitteet 58

A Revised simplex 58

B Dantzig-Wolfe -dekompositio 61

C Jälkimmäisen esimerkkiverkon liikennematriisi 63

Lyhenneluettelo

ATM GSM IP SDH STM UMTS VC

Asynchronous Transfer Mode

Global System for Mobile Communications Internet Protocol

Synchronous Digital Hierarchy Synchronous Transport Module

Universal Mobile Telecommunications System Virtual Container

1 Johdanto

Viime vuosina tietoliikennekapasiteetin tarve on lisääntynyt huomattavasti. Tä­

hän muutokseen on vaikuttanut muun muassa Internetin räjähdysmäinen kasvu.

Internetin käyttäjämäärä on lähes kaksinkertaistunut joka vuosi. Lisäksi kapasi­

teettitarvetta on etenkin Suomessa lisännyt matkapuhelinten yleistyminen. Kes­

kimäärin joka toisella suomalaisella on matkapuhelinliittymä ja liittymätiheys kasvaa koko ajan. Tulevaisuudessa tietoliikennekapasiteetin tarpeen ennustetaan kasvavan entisestään. Matkapuhelinliikenteessä GSM:n (Global System for Mobi­

le Communications) rinnalle tulee kolmannen sukupolven laajakaistainen matka- puhelintekniikka, UMTS (Universal Mobile Telecommunications System). Täysin mahdottomalta ei tunnu myöskään ajatus, että tulevaisuudessa olisi jokaisessa ko­

titaloudessa kiinteä laajakaistainen tietoliikenneyhteys Teknillisen Korkeakoulun Ylioppilaskunnan opiskelija-asuntojen tapaan. Kapasiteettitarpeen lisääntymi­

nen luo sekä mahdollisuuksia että tarvetta tarkempaan verkkokapasiteetin op­

timointiin. Pelkästään varmistustavoitteet täyttävän verkon muodostaminen on hankalaa, puhumattakaan siitä, että verkon tila olisi jollain tavalla optimaalinen.

Kustannusten minimointi saattaa tuoda huomattavia säästöjä.

Tämän työn tarkoituksena on rakentaa SDH-verkon (Synchronous Digital Hie­

rarchy) siirtokapasiteetin kustannusmalli, jossa huomioidaan käytännön verkko- suunnittelussa eteentulevia seikkoja. Päätavoitteena on mitoittaa siirtojärjestei­

nä äkapasiteetti siten, että ennustettu liikenne pystytään sekä välittämään että varmistamaan annettujen tavoitteiden mukaisesti. Työssä kehitetään siirtover­

kon mitoitusmenetelmä, joka huomioi liikenteen erilaiset varmistus- ja järjeste­

ly vaatimukset sekä yhteyksien vikaaniumistodennäköisyydet ja epäkäytettävyy- sajat. Tavoitteena on luoda verkkosuunnittelijan työtä helpottava työkalu, joka mahdollistaa liikenne-ennusteisiin pohjautuvan verkon visualisoinnin ja jossa osa suunnitteluprosessista on automatisoitu. Työkalun avulla voi verkkosuunnitteli- ja paremmin havaita verkossa eteentulevat ongelmakohdat ja pullonkaulat ja voi keskittyä tehokkaammin niiden eliminointiin. Kehitettävä menetelmä implemen­

toidaan Microsoft Visual Basicila ja yhdistetään osaksi Sonera OY:ssä kehitet­

tyä siirtoverkkojen suunnitteluohjelmaa. Jotta ohjelman sisäistä tietorakennet­

ta voitaisiin hyödyntää mahdollisimman hyvin, koodataan kaikki algoritmit itse.

Vaikka työssä tarkastellaankin SDH-verkon mitoitusta, voidaan samaa menetel­

mää soveltaa pienillä muutoksilla myös muiden verkkoarkkitehtuurien, esimer­

kiksi ATM- (Asynchronous Transfer Mode) ja IP-verkkojen (Internet Protocol) suunnitteluun.

SDH-verkko muodostuu useista tasoista. Alimmaisena on kaapeliverkko, johon si­

sältyvät laiteasemat, kaapelikaivannot (eli ojat, joissa voi kulkea yksi tai useampia kaapeleita) sekä itse kaapelit. Kaapeliverkko sekä sen päälle sijoittuva siirtolai- teverkko muodostavat verkon fyysiset tasot. Siirtolaitteita ovat verkon osuuksil­

la olevat siirtojärjestelmät, jotka kuljettavat nimensä mukaisesti liikennettä sol­

musta toiseen. Fyysisiä siirtolaitteita ovat myös solmut, joilla voi olla erilaisia vikaantumistodennäköisyyksiä ja epäkäytettävyysaikoja, kapasiteetteja sekä ky­

kyjä kytkeä liikennettä. Myös solmujen hinnat voivat vaihdella. Tässä työssä ei solmujen ominaisuuksia kuitenkaan oteta huomioon. Siirtoverkon kuljettama lii­

kenne koostuu solmusta toiseen kulkevista yhteyksistä. Alatason yhteydet yh­

distetään suurempikapasiteettisiksi VC-4 -signaaleiksi (Virtual Container), jotka siirretään siirtojärjestelmässä viereiseen solmuun. Liikenteellisiä tasoja verkossa on siis kaksi: alemman tason yhteydet sekä VC-4 -yhteyksistä muodostuva yläta­

so. Sekä ala- että ylätason yhteydet ovat verkko-operaattorin myytäviä tuotteita.

Yhteyksiä voidaan käyttää joko suoraan kahden pisteen väliseen tiedonsiirtoon tai niiden avulla voidaan muodostaa erilaisia palveluverkkoja, esimerkiksi ATM-, IP- tai yrityksen sisäisiä vaihdeverkkoja. Jokaiselle tasolle muodostuu oma verkkon­

sa kuvan 1 mukaisesti. Tässä työssä oletetaan sekä kaapeliverkko että alemman

Palveluverkot

Loogiset yhteydet

Fyysinen siirtolaiteverkko

Kaapeliverkko

Kuva 1: Kaaviokuva SDH-verkon tasoista.

tason liikenne tunnetuiksi ja mitoitetaan ylemmän tason liikenne ja siirtojärjes- telmäverkko.

Loogiset yhteydet ovat yleensä jollakin tavalla varmistettuja. Yhteyden varmis­

tuksella pyritään hoitamaan liikenne ilman suurempaa katkosta erilaisissa vikati­

lanteissa. Varmistuksen toteuttamiseen on kaksi periaatteeltaan erilaista tapaa.

1+1 -varmistuksessa yhteydelle muodostetaan kaksi erillistä reittiä. Yhteyden tarvitsema kapasiteetti on varattu koko ajan molemmilta reiteiltä, jolloin lii­

kenne voidaan varsinaisen reitin vikaantuessa siirtää nopeasti varatielle. 1+1- eli protection-varmistus voidaan toteuttaa joko alemmalla tai ylemmällä tasol­

la. Ylemmän tason yhteydet voidaan varmistaa myös dynaamisesti restoration- varmistuksella, jossa varatie haetaan vasta vian sattuessa.

Verkkokapasiteetilla on siis kolme erilaista käyttötarkoitusta:

1. Yhteyden varsinaisen reitin vaatima kapasiteetti,

2. 1+1 -varmistetun yhteyden varatien vaatima kapasiteetti ja 3. restoration-varmistukseen käytettävä varakapasiteetti.

Restoration-varmistukseen käytettävä kapasiteetti on verkonhallintajärjestelmän vapaasti käytettävissä. Kapasiteettia voidaan käyttää useamman eri aikoihin sat­

tuvan vian varmistamiseen. Yhteyksien varsinaisten reittien sekä 1+1 -varmistet­

tujen yhteyksien varareittien vaatima kapasiteetti taas on koko ajan varattu etu­

käteen nimettyä yhteyttä varten. Tätä kapasiteettia ei voida käyttää muun lii­

kenteen varmistamiseen, vaikka reitillä ei olisikaan liikennettä. Tässä työssä ke­

hitettävässä menetelmässä mitoitetaan siirtojärjestelmäkapasiteetti kolmessa toi­

sistaan erillisessä vaiheessa. Ensimmäisessä vaiheessa muodostetaan alemman ta­

son yhteyksistä ylätaso. Toisessa vaiheessa lasketaan ylätason yhteyksille koko ajan varattuna oleva kapasiteetti. Yhteyksille, jotka eivät ole 1+1 -varmistettuja, muodostetaan varsinainen reitti suoraan lyhintä yhteyden päätepisteet yhdistä­

vää polkua pitkin. 1+1 -varmistetuille yhteyksille taas haetaan kaksi eri kaa- pelikaivannoissa kulkevaa polkua siten, että polkujen yhteenlaskettu pituus on mahdollisimman pieni. Menetelmän kolmannessa vaiheessa määrätään tarvittava siirtojärjestelmäkapasiteetti, kun myös restoration-varmistus otetaan huomioon.

Menetelmän kolmeen eri vaiheeseen jakamisella saadaan yhteyksille muodostettua mahdollisimman lyhyet reitit. Tällöin niiden vikaaniumistodennäköisyys on mah­

dollisimman pieni. Haittapuolena on se, että tarvittava järjestelmäkapasiteetti ei välttämättä ole aivan minimissään.

Kolmannessa vaiheessa suoritettava restoration-varmistuksen vaatiman kapasitee­

tin haku toteutetaan simulointityyppisesti. Jokainen kaapelikaivanto asetetaan vuorollaan kelvottomaksi, ja haetaan kaivannossa kulkeneille liikennekimpuille uudet reitit. Mikäli vian restorointiin ei ole tarpeeksi verkkokapasiteettia, muo­

dostetaan sitä lisää siten, että kapasiteetin kokonaiskustannus minimoituu. Tätä kapasiteettia voidaan käyttää hyväksi muiden kaivantojen restoroinnissa.

Kaapelikaivannon restoration-ongelma kuuluu tehtävätyypiltään monihyödyke- virtausongelmiin. Nämä eroavat tavallisista virtausongelmista siten, että niissä on monta toisiinsa sekoittumatonta virtausta, joilla kaikilla on omat virtausehton- sa. Virtaukset vuorovaikuttavat toistensa kanssa esimerkiksi kuluttamalla samaa siirtokapasiteettia tai materiaaliresursseja. Formuloimalla ongelma polkumuodos- sa voidaan yksittäiselle yhteydelle antaa helposti lisärajoituksia. Polkumuodossa formuloidut monen hyödykkeen virtausongelmat ratkaistaan yleensä joko For­

din ja Fulkersonin esittelemällä implisiittisellä sarakkeenmuodostusmenetelmällä [10] tai siitä kehitetyillä partitiointi- tai dekompositiomenetelmillä. Tässä työssä muodostettava optimointiongelma ratkaistaan suoraan implisiittistä sarakkeen- muodostusmenetelmää soveltaen. Restoration-ongelmassa on päätösmuuttujilla myös kokonaislukurajoitukset, joista osa ei toteudu automaattisesti. Kokonaislu- kurajoitusten toteutuminen varmistetaan branch and bound -algoritmilla [19].

Työn alussa kuvataan erilaisia monen hyödykkeen virtausongelman formulointi- tapoja ja esitetään joukko polkuformuloinnilla muodostetun ongelman ratkaise­

miseen käytettäviä menetelmiä. Lisäksi käsitellään Branch and bound -algoritmi, jota käytetään optimointitehtävän kokonaislukuratkaisun hakemisessa. Työn kes­

kivaiheella kuvataan SD H-verkon rakenne ja suunnittelussa huomioitavia asioita.

Tämän jälkeen muodostetaan verkon mitoitusmalli sekä tälle ratkaisumenetelmä.

Työn lopussa sovelletaan kehitettyä menetelmää kahteen yksinkertaiseen testi- verkkoon.

2 Monihyödykevirtausongelmat

Tässä luvussa tarkastellaan yhden tai useamman hyödykkeen kuljettamista ver­

kon yli. Näitä hyödykkeiden siirto-ongelmia kutsutaan virtausongelmiksi, kos­

ka ne ovat analogisia vesijohtoverkon virtausprofiilin kanssa [13]. Aluksi esitel­

lään yhden hyödykkeen ongelma, joka edustaa perinteistä virtaustehtävätyyp- piä. Tämän jälkeen tarkastellaan laajennettua virtausongelmaa, jossa siirrettä­

viä hyödykkeitä on useita. Monen hyödykkeen virtausongelmalle esitetään kaksi formulointi- sekä useita ratkaisutapoja.

Transmissioverkon tehtävänä on yhteyksien kuljetus verkon yli, jolloin jokaiselle yhteydelle on haettava reitti alku- ja loppusolmujen välille. Useamman yhtey­

den reititysten suunnittelu johtaa monen hyödykkeen virtausongelmaan, jossa voi kapasiteettirajoitusten lisäksi olla myös muita, esimerkiksi liikenteen järjeste- lyvaatimuksista johtuvia rajoituksia. Vastaavan tyyppisiä tehtäviä syntyy myös ATM-verkon mitoituksessa käytettävien virtuaalipolkujen reititysongelmissa [8].

2.1 Yhden hyödykkeen virtausongelmat

Tarkastellaan aluksi tehtäviä, joissa siirrettäviä hyödykkeitä on vain yksi. Tyy­

pillisiä yhden hyödykkeen virtausongelmia ovat esimerkiksi virtapiiritarkastelut ja erilaiset tie- tai kuljetusverkostojen optimoinnit [15].

Tarkastellaan suunnistettua verkkoa G (Af, A), missä Ai on solmujen ja A osuuk­

sien joukko. Mikäli verkko ei ole suunnistettu, voidaan se suunnistaa korvaamalla jokainen suunnistamattoman sivu kahdella suunnistetulla sivulla [12]. Esimerkik­

si maantiet ovat yleensä kaksisuuntaisia, jolloin niistä muodostettava verkko on suunnistamaton. Verkon suunnistaminen vastaisi kahden vastakkaisiin suuntiin kulkevan kaistan tarkastelemista kaksisuuntaisen tien sijasta. Merkitään solmus­

ta i solmuun j kulkevaa sivua solmuparilla ja määritellään jokaiselle sol­

mulle i G Af lähtevien ja tulevien sivujen joukot A(i) = {j G Af | (г, j) G A} ja В (i) = {j e Af I (j, i) e A}.

Olkoon fij > 0 osuudella (i,j) G A oleva virtaus, ja F¿ solmussa г syntyvä virtaus.

Solmu on lähde, jos > 0 ja nielu, jos F¿ < 0. Jokaisessa solmussa vallitsee materiaalitasapaino, jonka mukaan solmuun tuleva ja solmusta lähtevä virtaus ovat yhtä suuret (vrt. Kirchoffin laki). Tällöin solmua i vastaavat virtausehdot (materiaalibalanssi) esitetään muodossa

E fa - E /у = Fit i e и. (i)

jeA(i) jeB(i)

Kuva 2: Esimerkki verkko.

Esimerkiksi kuvan 2 kaltaisessa verkossa solmujen ja osuuksien joukot ovat Af = {1, 2, 3, 4, 5}, ja A = {(1,5), (4,5), (5,2), (5,3), (5,4)}. Solmusta 5 lähtevien sivujen joukko on A(5) = {(5,2), (5,3), (5,4)} ja solmuun tulevien sivujen joukko B(5) = {(l, 5), (4,5)}, joten solmun 5 materiaalitasapaino on muotoa

(/52 + /53 + /54) — (/15 + /45) = Fb^-

Olkoon N solmujen ja M sivujen lukumäärä. Indeksoidaan sivut yhdestä M:ään, jolloin verkon rakenne voidaan esittää N x M -dimensioisella solmu-sivu -saavu- tettavuusmatriisilla E = [£*,•], missä

{

Kuvan 2 verkon solmu-osuus -matriisi on muotoa

E = 1

-1 -1

1 -1 -1 1 1-1 1

Esitetään virtausprofiili vektorina / = (/1 ... /м)Г> missä fj on virtaus osuudella j e Л, ja määritellään vektori b = (Fx ... Fm)t. Virtausehdot (1) voidaan nyt esittää matriisimuodossa

E f = b, ⁽2)

Virtausehtojen (2) lisäksi tehtävässä on usein myös muita rajoitusehtoja, esimer­

kiksi kapasiteettirajoituksia. Virtausongelmissa on yleisesti kaksi erilaista tehtävä­

tyyppiä. Maksimivirtausongelmassa pyritään maksimoimaan verkon yli kulkevaa virtausta. Minimikustannusongelmassa taas minimoidaan kiinteästä virtauksesta aiheutuvaa kustannusta.

2.2 Monen hyödykkeen virtausongelmat

Mikäli tarkasteltavana on useita toisiinsa sekoittumattomia hyödykkeitä, puhu­

taan monihyödykevirtausongelmasta. Monen hyödykkeen virtausongelmissa on jokaisella hyödykkeellä oma virtausprofiilinsa, ja hyödykkeiden keskenäinen vuo­

rovaikutus ilmenee esimerkiksi kilpailuna yhteisestä kapasiteetista tai resursseista.

Esimerkiksi jakeluverkon suunnittelu yritykselle, jonka tuotteet viedään kuluttu- jan lähelle yhden jakeluverkoston avulla, johtaa monen hyödykkeen virtausongel-

maan.

F2 —-(¿) Fy®

Ei + F2 —*(з) X

1 ®

Kuva 3: Kahden lähteen yhdistäminen.

Tässä työssä tarkasteltavan siirtoverkon suunnitteluongelman yksi osa on reittien hakeminen yhteyksille. Usean yhteyden reititysongelma on monen hyödykkeen virtaustehtävä, jossa yhteydet käyttävät yhteistä siirtokapasiteettia ja kullakin yhteydellä on täsmälleen yksi lähde ja yksi nielu. Vaikka jatkossa tarkastellaan

vain tällaisia tehtäviä, käyvät tarkastelut myös muillekin lähde- ja nieluyhdistel- mille. Mikä tahansa yhdistelmä saadaan kyseiseen muotoon lisäämällä tehtävään kaksi apusolmua, joista toiseen kerätään kaikkiin lähdesolmuihin tulevat virtauk­

set ja toiseen nielusolmuista poistuvat virtaukset. Kuvassa 3 on esimerkki lähde- solmujen yhdistämisestä.

Myös monihyödykevirtausongelmissa on tavallisten virtausongelmien tapaan kak­

si tehtävätyyppiä. Maksimivirtausongelmissa pyritään maksimoimaan verkon yli kulkevaa kokonaisvirtausta, kun minimikustannusongelmissa halutaan toteuttaa annetut virtausvaatimukset mahdollisimman pienillä kokonaiskustannuksilla [2].

Tehtävätyypit eroavat toisistaan vain kohdefunktion suhteen, virtausehdot ovat molemmissa samat. Seuraavassa esitetään kaksi ekvivalenttia formulointia ongel­

malle, jossa verkon sivuilla on äärellinen kapasiteetti.

2.3 Formulointi

Tarkastellaan aluksi virtausformulointia, joka on edellä esitetyn yhden hyödyk­

keen ongelman yleistys. Olkoon K hyödykkeiden lukumäärä ja (sk, tk) hyödyk­

keen k lähde- ja nielusolmut, k = l,...,K. Määritellään lisäksi muuttujat fk = hyödykkeen k virtaus osuudella j E A, fk > 0,

Fk = verkon läpi solmusta sk solmuun tk kuljetettava hyödykkeen k virtaus.

Hyödykkeen k virtausehdot voidaan esittää yhtälöä (2) vastaavassa muodossa

Efk = bk, (3)

missä fk = [/f ... fb}T, bk = $ ... bkM\T ja ' Fk, i = sk

< -Fk, i = tk 0, muuten.

Olkoon d=[d\ ... d\f]T, missä dj > 0 on osuuden j kapasiteetti. Olkoon lisäksi gk hyödykkeen k kuluttama kapasiteetti yhden yksikön virtausta kohden. Tällöin

kapasiteettirajoitus on muotoa

ЕЛ‘<*

Jfc=l

Tehtävä saadaan siis virtausformuloinnilla muotoon

I fffk < d

I k~l Efk = bk, k=l,...,K.

(4)

(5)

Sama tehtävä voidaan formuloida myös toisin. Polkuformuloinnissa päätösmuut- tujina ovat solmuja sk ja tk yhdistäville käyville poluille allokoidut virtaukset.

Olkoon J(k) alku- ja loppusolmut yhdistävien käypien polkujen lukumäärä ja xk >0 polulle j allokoitu virtaus, j = 1 ,...,J(k). Muodostetaan hyödykkeen k polku-osuus -matriisi Ak siten, että

k _ f 1, jos polku j kulkee sivun i kautta u _ \ 0, muuten.

Muodostetaan lisäksi polkuvektori xk = [x* ... хк^]т, jolloin hyödykkeen vir- tausvektori on

fk = Akxk.

Vaatimus Fk:n yksikön virtauksesta solmusta sk solmuun tk yksinkertaistuu muo­

toon

J(k)

E 4 = ^k.

J=1

Virtausongelma (5) voidaan esittää nyt muodossa

E

J{k)

ExJ = F“, k=l,...,K.

j=1

(6)

Polkuformuloinnissa (6) ei oteta lainkaan kantaa verkon suunnistukseen. Verkko voi siis olla joko suunnistettu tai suunnistamaton. Suunnistus vaikuttaa polkujen lukumäärään ja polun etsimiseen, mutta formulointiin tai kohdassa 2.4 esitettä­

vien ratkaisualgoritmien pääkohtiin se ei vaikuta.

Tarkastellaan esimerkin vuoksi yksinkertaista kuvan 4 mukaista verkkoa, jonka hyödykkeet on esitetty taulukossa 1.

Kuva 4: Esimerkkiverkon topologia.

Taulukko 1: Esimerkkiongelman hyödykkeet.

Hyödyke Solmu 1 (lähde)

Solmu 2 (nielu)

1 1 4

2 2 3

3 2 4

Käypien polkujen lukumäärät ovat J(l) = 3, J(2) = 4 ja J(3) = 3. Esimerkkion­

gelman rajoitusyhtälöiden kerroinmatriisiksi saadaan

4 4 4 1 *? ^{4 T}_z3² ** 1

*1 ^{Xx23 Xx33} Sl ⁵² S3 54 S 5

i 1 i i 1 i i 1

1 ¹ i 1 ¹ i 1 i

i 1 1 1 ¹ 1 ^{1 i}

1 ^{1 1 i 1 i 1 i}

i 1 i 1 ¹ i 1 i

i 1 i 1 1 1

1 i 1 ⁱ 1 ^{1 1}

1 1 1 i i 1

missä si,...,s5 ovat kapasiteettiehtoja vastaavat slack-muuttujat. Matriisin (7) kolme ensimmäistä saraketta vastaavat siis hyödykkeen 1, neljä seuraavaa hyö­

dykkeen 2 ja seuraavat kolme hyödykkeen 3 polkumuuttujia.

Taulukossa 2 on vertailtu virtaus-ja polkuformuloinnilla saatavien ongelmien di­

mensioita. Polkuformuloinnissa rajoitusehtojen lukumäärä on pienempi kuin vir- tausformuloinnissa eli kanta vaatii vähemmän muistia, ja kannan käänteismat- riisin päivitys tapahtuu nopeammin. Toisaalta muuttujien lukumäärä on paljon isompi, mutta kaikkia muuttujia ei tarvitse pitää eksplisiittisesti muistissa, vaan ne voidaan muodostaa kohdassa 2.4.1 esitettävällä Fordin ja Fulkersonin ehdot­

tamalla sarakkeenmuodostusmenetelmällä.

Taulukko 2: Eri formuloinneilla muodostuvat optimointiongelmat.

Rajoitusehtojen lkm Päätösmuuttujien lkm Virtausformulointi

Polkuformulointi

(M + 1 )K M + K

2 M

E J{k)

k=l

Polkuformulointi on hyvin käyttökelpoinen verkonmitoitustehtävissä, koska tehtä­

vään voidaan helposti lisätä polkuihin kohdistuvia rajoituksia. Käytännön suun­

nittelussa saatetaan esimerkiksi vaatia, että polku ei saa kulkea yli kymmenen solmun läpi. Tällaisten ehtojen lisääminen virtausformuloinnilla muodostettuun tehtävään on hankalaa.

2.4 Ratkaisutapoja

Monihyödykevirtausongelmien ratkaisutavat jaetaan kolmeen päätyyppiin [14]:

1. kustannusohj aavat dekompositiomenetelmät, 2. resurssiohjaavat dekompositiomenetelmät ja 3. partitiointimenetelmät.

Tässä luvussa esitetään kustannusohj aavista menetelmistä Fordin ja Fulkersonin esittelemä implisiittinen sarakkeenmuodostusmenetelmä. Lisäksi esitetään resurs­

siohj aavien menetelmien käyttöön johtava formulointi. Partitiointimenetelmistä käydään läpi primaalipartitiointi sekä generalized upper bounding -menetelmä

(GUB), jotka ovat kumpikin implisiittisen sarakkeenmuodostusmenetelmän so­

velluksia.

2.4.1 Implisiittinen sarakkeenmuodostus

Tarkastellaan polkuformuloinnilla (6) muodostettua monen hyödykkeen virtaus- ongelmaa. Ford ja Fulkerson suosittelivat tehtävän ratkaisussa käytettäväksi imp­

lisiittistä sarakkeenmuodostusmenetelmää [10], jossa sovelletaan liitteessä A esi­

tettyä Revised Simplex -algoritmia ja hyödynnetään ongelman rakennetta. Kaik­

kia polkumuuttujia ei käsitellä eksplisiittisesti, vaan niitä muodostetaan vasta tarvittaessa. Menetelmästä on kehitetty kohdissa 2.4.3 ja 2.4.4 esitettävät parti- tiointimenetelmät ja se on antanut idean myös yleisempien tehtävien ratkaisussa käytettävälle Dantzig-Wolfe -dekompositiolle.

Olkoon Ci osuudelle i allokoidun yhden yksikön virtauksen aiheuttama kustan­

nus. Oletetaan yksinkertaisuuden vuoksi, että tämä kustannus on sama kaikille hyödykkeille. Tällöin yhden yksikön virtaus polulla x) aiheuttaa kustannuksen Eiii e*A* = J A), missä c = [ci ... cM]T ja A) = [A*j- ... AkMj]T. Mimimikus- tannusongelma on standardimuodossaan

min z

K J(k)

Ê È 44

k=1j=1

J(k)

j=i

£4

missä s = [si ... sM]T on slack-vektori. Jaetaan tehtävän muuttujat K + l:een ryhmään, joista ensimmäinen koostuu slack-muuttujista ja loput K eri hyödyk­

keiden polkumuuttujista. Tarkastellaan Revised Simplex -algoritmissa (liite A) tarvittavan redusoidun kustannuksen määräämistä eri muuttujatyypeille.

к J(k)

E E cTA)x) fc=i j=i

= d (8⁾

= Fk, k = l,...,K,

1. Slack-muuttujan Sj sarake on muotoa

P/ = e,(M + K), j = 1,..., M,

missä 6j(M + K) on M + /f-dimensioinen vektori, jonka j:s alkio on 1 ja lo­

put nollia. Muuttujan Sj kerroin kohdefunktiossa on nolla, joten muuttujaa vastaava redusoitu kustannus on

Cj = Y P* - 0 = Yj, missä Y = [yj ... Ym+k] on duaaliratkaisu.

2. Polkumuuttujan xj sarake on

PJ =

4

ek(K) jolloin muuttujan redusoitu kustannus on

c* = Y P* — cT A *

M

= EW-CiMt + W

i=l

Yleensä Revised Simplex -algoritmissa viedään kantaan lupaavin muuttuja eli se, jonka redusoitu kustannus on suurin. Implisiittisessä sarakkeenmuodostusmene-

telmässä tarkastellaan ensiksi lupaavinta slack-muuttujaa s,*, missä j* — argmax { cj} = argrnax {Yj} .

Jos redusoitu kustannus cj. > 0, viedään kantaan. Jos cj. < 0, tarkastel­

laan seuraavaksi ensimmäisen hyödykkeen lupaavinta polkua x}.. Tämän polun redusoitu kustannus on

Cv. = max

{ci}

|£(у;-с)а;,. + ум+1|

= YM+1 + . mini fe(c¡ - yi)4¿}

= max j=i,...,J(i) I jr

Minimi määräätään etsimällä lyhin solmut s1 jät1 yhdistävä polku verkosta, jossa sivun i kustannus on c¿ — . Koska slack-muuttujaa ei voitu tuoda kantaan, pätee

Yi < 0, i =

Toisaalta taas virtausten kustannukset ovat ei-negatiivisia, joten

Ci — Yi > 0, i = 1,... ,M.

Tällöin minimipolku voidaan etsiä kohdassa 3.3 esitetyllä Dijkstran algoritmilla.

Jos löydettyä minimipolkua vastaava redusoitu kustannus cj. > 0, viedään pol­

ku Xj. kantaan. Muuten siirrytään tarkastelemaan seuraavaa hyödykettä. Tällä tavoin käydään läpi kaikki hyödykkeet, kunnes löytyy kohdefunktion arvoa pa­

rantava polku. Mikäli tällaista polkua ei ole olemassa, on tehtävän minimi löyty­

nyt. Muut algoritmin vaiheet noudattavat täsmälleen revised simplex -algoritmin kohtia (liite A). Dijkstran sijasta voitaisiin myös hakea tehtävän alussa kaikille hyödykkeille lyhimmät polut. Tämän jälkeen lyhimpiä polkuja voitaisiin päivit­

tää tarpeen vaatiessa sopivalla primaalisella lyhimmän polun hakualgoritmilla, kuten esimerkiksi tunnustenkorjausmenetelmällä [5].

Ford ja Fulkerson suosittelivat, että jos jollekin hyödykkeelle löydetään kohde- funktion arvoa parantava polku, viedään se heti kantaan. Vaihtoehtoinen mah­

dollisuus olisi etsiä ensiksi jokaiselle hyödykkeelle minimipolku ja valita näistä paras. Cremeans et ai. käsittelevät tätä tapaa tarkemmin viitteessä [4].

Implisiittinen sarakkeenmuodostusmenetelmä on antanut idean myös Dantzig- Wolfe -dekompositiolle, jonka avulla voidaan ratkaista yleisempiä LP-ongelmia.

Menetelmä soveltuu kuvan 5 kaltaisiin kulmalohkomuodossa oleviin systeemei­

hin, joissa on osassa rajoitusyhtälöistä lähes kaikki muuttujat mukana. Loput rajoitusyhtälöt taas ovat lohkomuotoisia ja eri lohkot keskenään riippumattomia.

Yhteiset rajoitusyhtälöt

Kuva 5: Lohkomuotoinen rajoitusyhtälöryhmä.

Dantzig-Wolfe -dekompositiossa tehtävä jaetaan lähes riippumattomista lohkois­

ta muodostettaviin aliongelmiin, jotka ratkaistaan itsenäisesti. Master-ongelmas-

sa valitaan kantaan tuleva muuttuja aliohjelmissa muodostetuista ääripisteistä huomioiden yhteiset rajoitusyhtälöt. Algoritmi on kuvattu liitteessä B.

2.4.2 Resurssiohjaava dekompositio

Implisiittinen sarakkeenmuodostus ja Dantzig-Wolfe -dekompositio ovat kustan- nusohjaavia dekompositiomenetelmiä, joissa pääongelmassa määrätään aliongel- mille kustannukset ja aliongelmissa haetaan toisistaan riippumattomasti ehdok­

kaita kantaan tulevaksi muuttujaksi. Myös resurssiohjaavassa dekompositiossa tehtävä jaetaan master-ongelmaan ja kutakin hyödykettä vastaaviin aliongelmiin.

Masterongelmassa jaetaan käytettävissä olevat resurssit (kapasiteetti) aliongel- mille. Tämän jälkeen aliongelmissa ratkotaan tavallisia yhden hyödykkeen mini- mikustannusvirtausongelmia. Näiden ratkaisujen perusteella päivitetään resurs­

sien jakoa ja jatketaan iteraatiota [14].

Tarkastellaan virtausformuloinnilla muodostettua minimikustannustehtävää, joka on muotoa

K „ . minz — E c /

Efk = £*,‘/t = l (9)

E/‘ <

k= 1

Olkoon yk hyödykkeen k virtaukselle jaettu kapasiteetti. Tehtävä (9) voidaan esittää ekvivalentissa muodossa

min z

£ fc

*=i

E r

E

4

fc=i

< d,

(10)

missä z*k on aliongelman

• T rk

mm Zk — c f

Efk = bk (11)

fk < yk

optimiratkaisu [2]. Aliongelmat (11) ovat tavallisia yhden hyödykkeen virtauson- gelmia. Hyödykkeille varattavia kapasiteetteja yk muutellaan masterongelmassa

(10). Aliongelman k ratkaisu on vektorin yk jatkuva funktio. Vastaavasti mas- terongelman kohdefunktio z = z(yl, ..., yK).

Epälineaarinen optimointitehtävä (10 - 11) voidaan ratkaista monella eri tavalla.

Tangentiaaliapproksimaatiossa muodostetaan lineaariset approksimaatiot funk­

tioista z*k(yk). Approksimaatio on sitä parempi, mitä lähempänä ollaan aliongel­

man optimia. Optimissa esitys on tarkka. Tätä eksplisiittistä riippuvuutta käyte­

tään hyväksi master-ongelmassa redusoitujen kustannusten laskemisessa.

Käypien suuntien menetelmässä tarkastellaan ongelman käypää ratkaisua y. Me­

netelmässä haetaan lupaavin suunta dy, joka on käypä. Suunta on käypä, jos on olemassa A0 > 0 siten, että y + Xdy on käypä kaikilla 0 < A < A0. Lupaavin suun­

ta tarkoittaa sitä, että dy minimoi kohdefunktion z(yl,..., yK) suuntaderivaatan ottaen edellä mainitun käypyysehdon huomioon.

Aligradienttioptimoinnin lähtökohtana on se, että lupaavimman käyvän suunnan etsiminen on liian raskas minimointiongelma. Aligradienttioptimoinnissa tyydy- täänkin mihin suuntaan tahansa, joka parantaa kohdefunktion arvoa ja on käypä.

Tässä mainitut ratkaisumenetelmät on kuvattu tarkemmin viitteissä [2] ja [14].

2.4.3 Primaalipartitiointi

Edellä esitetyssä implisiittisessä sarakkeenmuodostusmenetelmässä jaetaan muut­

tujat kahteen tyyppiin: polkumuuttujat ja slackit. Farvolden, Powell ja Lustig ja­

kavat kannassa olevat muuttujat kolmeen ryhmään [9]:

1. polkumuuttujat, joita vastaavien hyödykkeiden virtaus on sijoitettu vain yhdelle polulle,

2. polkumuuttujat, joita vastaavien hyödykkeiden virtaus on jakautunut vä­

hintään kahdelle eri polulle, 3. slack-muuttujat.

Olkoon yksinkertaisuuden vuoksi U ensimmäistä ja U toista polkutyyppiä vas­

taavien hyödykkeiden joukot. Olkoon lisäksi V saturoitumattomien ja V saturoi­

tuneiden sivujen joukko.

Järjestetään muuttujat siten, että ensimmäisenä ovat joukon U ja toisena jou­

kon Ы kaunassa olevat polut. Viimeisenä ovat slackit. Rajoitusehdot järjestetään siten, että esimmäisenä ovat joukon U hyödykkeiden virtausehdot. Toisena ovat joukon Ы hyödykkeiden virtausehdot sekä joukon V sivuja vastaavat kapasiteet- tiehdot. Lopuksi tulevat joukon V sivuja vastaavat kapasiteettiehdot. Näiden jär­

jestelyiden ansiosta voidaan kanta В esittää muodossa Г Iй

В -

д°

д1

о V

д2

о о Jv

(12)

missä Iй ja Iv ovat identiteettimatriiseja [9].

Palataan kohdassa 2.3 esitettyyn esimerkkiongelmaan. Tarkastellaan tilannetta, jossa polkumuuttujat £3, x2, xf ja x\ ovat kannassa ja sivu 3 on saturoitunut.

Hyödykejoukot ovat tällöin U = {1, 2} ja Ü = {3}. Sivujen joukot taas ovat V = {1, 2, 4, 5} ja V = {3}. Kanta В saadaan tällöin taulukossa 3 esitettyyn muotoon.

Taulukko 3: Esimerkkiongelman kantamatriisi.

4 x\ 1 X? x\ 1 s 1 S2 S4 £5

1 0 1 0 0 1 0 0 0 0

0 1 1 0 0 1 0 0 0 0

0 0 1 1 1 1 0 0 0 0

0 0 1 1 0 1 0 0 0 0

0 1 1 0 1 1 1 0 0 0

0 1 1 0 0 1 0 1 0 0

0 0 1 0 0 1 0 0 1 0

1 0 ! 0 1 1 0 0 0 1

Revised simplex -algoritmissa ratkaistaan kantaan tulevalle muuttujalle rajoi- tusyhtälöiden kerroinvektori a yhtälöstä Ba = P. Jaetaan a ja P rajoitusyhtä-

löiden partitiointia vastaaviin osiin a

a a a 1

2 3

F =

" P1 ' p2 p3

Tällöin rajoitusyhtälöiden kertoimet saadaan ratkaistua yhtälöryhmästä (13):

o

o

A0 V 0 a2 = F2

A1 A2 Iv a3 _ F3

Iй a1 = P1

< A°al+Va2 = P2 A1a1+A2a2 + Iva3 = P3 ' a1 = Pl

< Va2 = P2-A°al

a3 = P3 — (A1 a1 + A2 a2).

(13)

Työskentelykanta V on ei-singulaarinen neliömatriisi, jonka dimensio on joukkoon Ü kuuluvien hyödykkeiden kannassa olevien polkujen lukumäärä [9]. Sivujen ka­

pasiteetit ovat tyypillisesti suuria verrattuna yksittäisen hyödykkeen vaatimaan kapasiteettiin, jolloin suurin osa hyödykkeistä kuluu joukkoon U ja työskentely- kannan dimensio pysyy suhteellisen pienenä.

Kannasta voi lähteä vain sellainen muuttuja, jota vastaava vektorin a alkio on positiivinen. Tähän perustuen voidaan pivotoinnit rajata yhdeksään eri tyyppiin [9]. Pivotointityypeissä nimetään ne muuttujat, jotka voivat poistua kannasta, kun kantaan tulevan muuttujan tyyppi tunnetaan. Olkoon esimerkiksi x£, hyö­

dykkeen k^U kannassa oleva polku. Oletetaan, että kantaan tuleva muuttuja on Xj ja että kummankaan polun varrella ei ole yhtään saturoitunutta linkkiä. Täl­

löin kannasta voi poistua joko tai slack-muuttuja, jota vastaava sivu ei kuulu polkuun x^, mutta kuuluu polkuun x£. Edellinen pivoitointityyppi ei vaikuta työskentelykantaan V mitenkään, ja jälkimmäisessäkin tyypissä kannan käänteis- matriisin päivitys onnistuu ilman matriisioperaatioita. Suurin osa pivotoinneista on jompaa kumpaa edellä esitetyistä tyypeistä [9], joten kannan käänteismatriisin päivitys on pääsääntöisesti nopea ja yksinkertainen toimenpide.

2.4.4 Generalized upperbounding

Generalized upperbounding -menetelmä (GUB) on suosittu partitiointitapa, joka on varsin samankaltainen edellä esitetyn primaalipartitioinnin kanssa [2, 9]. Siinä valitaan jokaiselle hyödykkeelle yksi avainpolku, jota vastaavaa rajoitusyhtälöi- den saraketta kutsutaan avainsarakkeeksi. Muuttujat jaetaan kolmeen ryhmään:

avainpolut, muut polut ja slack-muuttujat. Tällä tavoin saadaan kantamatriisis- ta eristettyä mahdollisimman suuri identiteettimatriisi. Oletetaan, että tehtävälle on löydetty käypä kanta. Kanta voidaan tällöin esittää muodossa

' Ак An It AK В

[ Ik C Oi J L Ik C

missä Ak on avainpolkuja ja AN muita kannassa olevia polkuja vastaava ka- pasiteettiehtojen kerroinmatriisi. Kannassa olevien ei-avainpolkujen virtausehdot ovat matriisissa C, jonka sarake v on siis es(K), jos matriisin An sarake v vastaa hyödykkeen s polkua. Matriisin ït sarakkeet ovat kannassa olevia slack-muuttujia vastaavia yksikkövektoreita. Avainpolut on järjestetty siten, että niiden virtaus- ehdoista saadaan muodostettua K x A-dimensioinen identiteettimatriisi Ik- Yk­

sinkertaisuuden vuoksi on merkitty В = [Адг It\ ja С = [C Oi].

Järjestetään kantavektori XB muotoon XB = [xk xnk S]t, missä xk on avain- poluista, xNK muista kannassa olevista poluista ja S kannassa olevista slack- muuttujista koostuva vektori [16]. Tehdään seuraavaksi muuttujan vaihdos xk =

xk + Cxnk, jossa hyödykkeen s uusi avainpolku on kaikkien hyödykkeen kannas­

sa olevien polkujen summa. Olkoon uusi päätösmuuttujavektori muotoa XB = [xK xnk S]t, jolloin vanhojen ja uusien päätösmuuttuj ien välillä on yhteys

XB Ik C

0 Im XB = TXB, (15)

missä Im on M x M -identiteettimatriisi. Tehtävään saadaan uusi kanta vastaa­

maan muunnettuja muuttujia:

BXB = BT~lXB = BXB.

Uusi kanta on muotoa

В = ВТ-1 'AK B' Ik -C

.Ik C

o

Ak B--AKC

Ik 0

AK V ' Ik 0 >

missä V — В - AKC. Kannalle В löydetään helposti käänteismatriisi:

B~l 0 IK

P-1 -V-lAK ’

jonka jälkeen saadaan alkuperäisen kannan käänteismatriisi muodossa 0-1 _ [ -CV-1 IK + CV-lAK

■p-i -V~XAK ⁽¹⁶⁾

Sen sijaan, että päivitettäisiin täyden kannan (M + K) x (M + K") -dimensioista käänteismatriisia S"1, riittää M x M -dimensioisen työskentely kannan V kään- teismatriisin päivitys simplex-algoritmin toteuttamiseen. Tällöin käänteismatrii- sin tallentaminen vaatii vähemmän muistia ja päivitys on nopeampaa [16].

GUB ja kohdassa 2.4.3 esitetty primaalipartitiointi ovat muuttujien järjestelyn osalta varsin lähellä toisiaan. Joukon U polkuja vastaa GUEkssa avainpolut. Ei- avainpolut taas kuuluisivat primaalipartitioinnissa joukkoon U. Erona on se, että osa avainpoluista kuuluisi primaalipartitioinnissa jaettujen hyödykkeiden jouk­

koon Ü. Primaalipartitiointi käyttää hyväkseen jakautuneiden hyödykkeiden ja saturoituneiden linkkien välistä yhteyttä, GUB:ssä taas saadaan kannasta eris­

tettyä suurempidimensioinen identiteettimatriisi [9].

GUB-partitioinnissa saatetaan kantamatriisi muuttujanvaihdoksen avulla muo­

dosta

В =

muotoon

B =

' È A\ .. ■ Ak

C h

■ In .

Г V Ai ... An

0 h

In .

Tästä syystä GUB-partitiointia voidaan soveltaa vastaavalla tavalla myös virtaus- formuloinnilla muodostettuun monihyödykevirtausongelmaan [2, 11].

Partitiointimenetelmissä siis eristetään kantamatriisista В työskentelykanta V, jonka käänteismatriisia päivitetään algoritmin aikana. Tavoitteena on saada työs- kentelykannan dimensio malidollisimman pieneksi, jolloin käänteismatriisin päi­

vitys nopeutuu. Vastaavaan tulokseen päästään myös kantamatriisin LU-hajotel- malla, jossa muodostetaan ala- ja yläkolmiomatriisit L ja U siten, että В = LU

[2].

3 Kokonaislukuoptimointimenetelmät

3.1 Yleistä

Tässä luvussa tarkastellaan kokonaislukuongelmia sekä niiden ratkaisemista. Ko- konaislukuongelmia ovat esimerkiksi optimointitehtävät, joissa päätösmuuttujat ovat lukumääriä tai digitaalisia muuttujia. Jos optimointitehtävän kaikki muuttu­

jat ovat kokonaislukuja, kutsutaan tehtävää puhtaaksi kokonaislukuongelmaksi.

Jos vain osalla muuttujista on kokonaislukurajoitus ja osalla ei, puhutaan seka- lukuongelmasta.

Kokonailukuongelmien ratkaisemisen tekee hankalaksi se, että yksittäisen pisteen optimaalisuutta ei voida päätellä suoraan alkuperäisen tehtävän avulla. Mikäli muuttujien vaihteluvälit ovat suuria, voidaan kokonaislukumuuttujia approksi­

moida jatkuvilla muuttujilla. Usein myös se, että lineaaristen tehtävien ratkaisu löytyy jostakin ratkaisuavaruuden ääripisteestä, riittää takaamaan kokonaisluku- ratkaisun. Tällöin ratkaisussa ei tarvitse välittää kokonaislukurajoituksista ja teh­

tävä voidaan ratkaista tavallisilla optimointimenetelmillä. Kokonaislukuongelmia ratkotaan yleensä jollain seuraavista menetelmistä [18, 21]:

• Branch and bound -menetelmillä, joissa käypää aluetta jaetaan osaongel­

miin

• leikkausmenetelmillä, joissa käyvästä alueesta leikataan osia pois

• Lagrangen relaksaatiolla, jossa rajoitusehdot liitetään osaksi kustannus- funktiota

SDH-verkon mitoitusmallissa on sekä polkumuuttujilla että järjestelmien luku­

määrillä kokonaislukurajoitus. Polkumuuttujien kokonaislukuratkaisun takaami­

seksi riittää kuitenkin se, että järjestelmälukumäärät ovat kokonaislukuja. Tällöin polkumuuttujien kokonaislukurajoitusta ei tarvitse huomioida tehtävää ratkais­

tessa. Polkuformuloinnilla muodostetussa tehtävässä kaikkia muuttujia ei tunne­

ta eksplisiittisesti. Tästä syystä usein kokonaislukuongelmissa käytettävät leik­

kausmenetelmät ja Langrangen relaksaatio eivät sovellu tehtävän ratkaisemiseen.

Branch and bound-menetelmää sen sijaan voidaan käyttää vaikka kaikkia muut­

tujia ei ekplisiittisesti tunnetakaan. Koska kokonaislukurajoitukset huomioidaan vain järjestelmälukumäärien osalta, on kokonaislukumuuttujien määrä suhteelli­

sen pieni, jolloin branch and bound-menetelmä toimii riittävällä nopeudella.

Monen hyödykkeen virtausongelmien ratkaisemiseen käytettävässä implisiittisessä sarakkeenmuodostusalgoritmissa ja sen johdannaisissa on tehtävän aliongelmana lyhimmän polun haku. Lyhimmän polun haku on erikoistapaus kokonaislukuon- gelmista.

Tässä luvussa kuvataan yleisen sekalukuongelman ratkaisussa käytettävät branch and bound-menetelmät. Lisäksi esitetään Dijkstran algoritmi, joka on tehokkain lyhimmän polun hakualgoritmi [7].

3.2 Branch and bound -menetelmät

Optimointitehtävän ratkaisuavaruutta voidaan pitää rajoitettuna, joten käypiä kokonaislukuratkaisuj a on äärellinen määrä. Seuraavassa tarkastellaan branch and bound -menetelmiä, jotka perustuvat kokonaislukuratkaisuj en luettelointiin.

Luetteloinnilla pyritään hylkäämään ei-lupaavia pisteitä mahdollisimman tehok­

kaasti.

Tarkastellaan yksinkertaisuuden vuoksi puhdasta, lineaarista kokonaislukuopti- mointiongelmaa

min 2 = стх /17ч

ehdolla x G S,

missä x = [xi ... xN]T ja S on käypien kokonaislukupisteiden joukko. Branch and bound -menetelmissä ei kokonaislukurajoituksia käsitellä suoraan, vaan niissä ratkotaan jatkuvia tehtäviä, joiden ratkaisuavaruutena on alkuperäisen tehtävän ratkaisuavaruuden osa [18]. Algoritmin alussa muodostetaan joukko T siten, että käypien pisteiden joukko S CT. Yksinkertaisimmillaan tämä vastaa kokonaislu- kurajoituksen poistamista eli relaksoimista. Branch and bound -menetelmissä on kaksi perusoperaatiota [3]:

• Branching-. Jaetaan T osajoukkoihin Ti,..., Tq ja ratkaistaan toisistaan riip-

pumattomasti aliongelmat

minz¿ = cT x z1R\

ehdolla x € Ti} i = 1,... ,q.

Osajoukkojen ei tarvitse ”täyttää” T:tä eli ei vaadita että T c Ti U ... U Tq.

Yhtään käypää kokonaislukuratkaisua ei kuitenkaan hylätä. Osajoukkot voi­

vat myös mennä päällekäin. Jaon tavoitteena on rajata ratkaisuavaruudesta alkuperäisten kokonaislukurajoitusten suhteen ei-käypää aluetta mahdolli­

simman tehokkaasti pois.

• Bounding: Aliongelmien (18) optimiratkaisut z* ovat alarajoja alkuperäi­

sen tehtävän minimille. Näitä rajoja hyväksikäyttäen saadaan aliongelmat järjestykseen, jossa lupaavin aliongelma on ensimmäisenä. Jos aiemmin löy­

detty kokonaislukuratkaisu zmin < z*, hylätään aliongelma.

Jos aliongelman optimiratkaisu ei täytä alkuperäisen tehtävän kokonaisluku vaa­

timuksia, jaetaan se uusiin aliongelmiin. Tuloksena syntyy täten branch and bound -puu, jonka solmuja ovat aliongelmat. Sellaista solmua, jota ei olla vielä käsitelty, kutsutaan aktiiviseksi. Branch and bound -algoritmien tehokkuus riip­

puu sekä haarautumisen että alarajan määräämisen toteutuksesta. Eri algoritmit eroavat toisistaan juuri näissä toimenpiteissä. Ensimmäisen algoritmin kehittivät Land ja Doig vuonna 1960 [18].

Land-Doig -algoritmissa ratkaistaan aluksi alkuperäisestä tehtävästä (17) muo­

dostettu jatkuva optimointitehtävä

min z = cTx /jq\

ehdolla x € T,

missä x — [x\ ... xm]t. Jos tehtävällä on kokonaislukuratkaisu, on alkuperäi­

selle tehtävälle (17) löydetty ratkaisu. Muuten valitaan haarautumismuuttujaksi jokin kokonaislukurajoitusta rikkova muuttuja xk. Olkoon xl haarautumismuut- tujan arvo optimissa ja [x£] sen kokonaislukuosa. Seuraavaksi muodostetaan kak­

si aliongelmaa, joista toiseen on lisätty rajoitus xk < [x*k] ja toiseen rajoitus xk > [x£] +1. Jaossa poistetaan siis ratkaisuavaruudesta väli [x£] < xk < [я£] +1, johon ei voi kuulua yhtään kokonaislukuratkaisua. Jaossa rajataan kuitenkin al­

kuperäisen tehtävän optimipiste pois aliongelmien ratkaisuista. Tällä tavalla lisät­

tyjä rajoitusehtoja ei tarvitse käsitellä erikseen omina rajoitusyhtälöinään, vaan ne voidaan huomioida suoraan muuttujien ala- ja ylärajoina. Tällöin voidaan ala­

rajat poistaa muuttujanvaihdoksella aliongelmista ja ratkaista tehtävät liitteessä

A esitetyllä ylärajatekniikalla. Jos aliongelman optimiratkaisu ei ole kokonaislu­

ku, suoritetaan jako uudestaan aliongelmalle.

Menetelmässä on kaksi valintakohtaa: käsiteltävän solmun ja haarautumismuuttu- jan valinta. Lupaavin aktiivisista solmuista on se, jonka alaraja on pienin. Lupaa­

vimman solmun valinnassa on kuitenkin aiempien optimikantojen käyttö hanka­

laa. Voidaan olettaa, että solmun aliongelmien ratkaisut ovat lähellä isä-ongelman ratkaisua. Tällöin kannattaisi optimikanta aina tallettaa, jotta sitä voitaisiin käyt­

tää myöhemmin hyödyksi alisolmun ratkaisemisessa. Aktiivisten solmujen luku­

määrä voi kuitenkin olla hyvin suuri, jolloin kantojen tallentelu vaatisi varsin paljon muistia.

Valinta voidaan suorittaa myös LIFO-säännöllä (last-in first-out), jossa käsitte­

lyyn valitaan viimeksi muodostettu solmu. Toisin sanoen viimeiseksi käsitellyn solmun haaroista toinen talletetaan jatkokäsittelyä varten ja toinen ratkaistaan heti. Tällöin edellisessä osaongelmassa ratkaistu kanta on lähellä uuden solmun optimiratkaisua. Valitsemalla käsiteltävä solmu tällä tavoin päädytään myös mah­

dollisimman nopeasti käypään ratkaisuun, koska tällä tavoin tarkasteltavilla sol­

muilla on paljon kokonaislukuratkaisuun tähtääviä rajoituksia. Lisäksi solmun valinta saadaan suoritettua mahdollisimman nopeasti. Menetelmässä jää kuiten­

kin vielä kaksi valintatilannetta: haarautumismuuttujan ja haaran valinta. Kum­

paankaan valintaan ei voida muodostaa yleispäteviä sääntöjä, vaan ne riippuvat tarkasteltavasta tehtävästä.

Algoritmia voidaan parantaa tiukentamalla aliongelmien alarajoja. Tämä onnis­

tuu siten, että lisätään optimikantaan aliongelmaan tuleva rajoitus ja suoritetaan yksi duaalisimplex-iteraatio. Tämän jälkeen kohdefunktion arvosta saadaan tiu­

kempi alaraja aliongelman optimille [18]. Käsiteltäväksi solmuksi valitaan joko solmu, jolla on kaikista aktiivisista solmuista pienin alaraja, tai LIFO-sääntöä soveltaen viimeksi käsitellyn solmun aliongelmista se, jolla on pienempi alara­

ja. Isoissa tehtävissä ovat nämä alarajat kuitenkin liian optimistisia, koska niissä oletetaan, että yksi duaalisimplex-iteraatio riittäisi saattamaan kanta käyväksi.

Jos tehtävässä on paljon muuttujia ja rajoitusyhtälöitä, on todennäköistä että iteraatioita tarvitaan useita. Isoja tehtäviä ratkaistaessa kannattaakin käyttää sekä haarautumismuuttujan että käsiteltävän solmun valinnassa erilaisia, tehtä­

vätyypistä riippuvia heuristisia sääntöjä, joilla voidaan tehdä kohtuullisen hyviä valintoja nopeasti [18].

3.3 Dijkstran minimipolkualgoritmi

Lyhimmän polun haku on erityistapaus kokonaislukuongelmista. Verkon tuoma erityisrakenne voidaan ottaa huomioon, jolloin tehtävää ei kannata ratkaista ylei­

sillä menetelmillä. Kun haetaan lyhintä polkua kahden annetun solmun välille, on Dijkstran algoritmi tehokkain algoritmi [7]. Algoritmissa haetaan verkolle vi- rittäjäpuu, jota pitkin verkon solmusta s päästään solmuun t minimikustannuk­

sella [12, 15]. Jos halutaan löytää lyhimmät polut jokaisesta solmusta kaikkiin muihin solmuihin, on olemassa tehokkampiakin algoritmeja [6]. Tässä työssä ha­

lutaan löytää Velin yksi polku kerrallaan, joten Dijkstran algoritmi sopii tällöin parhaiten.

Dijkstran algoritmi perustuu solmuille annettaviin tunnuksiin [12]. Solmu saa pysyvän tunnuksen, jos lyhin polku solmusta s on löytynyt. Olkoon VC niiden solmujen joukko, joilla on pysyvä tunnus. Olkoon vastaavasti PL(i) lyhimmän solmujen s ja г E VC välisen polun pituus. Seuraavaksi pysyvä tunnus annetaan sellaiselle solmulle k £ VC, joka mimimoi summan PL(i) + Uk, missä i E VC ja lik kustannus siirryttäessä solmusta г solmuun k. Virittäjäpuuhun lisättävä solmu saa tunnuksekseen PL(k) = PL(i) + lik. Solmujen lisäämistä jatketaan niin kauan, kunnes solmu t saa pysyvän tunnuksen tai joukkoon VC ei voida enää lisätä yhtään solmua. Jos loppusolmu t ^ VC, ei solmujen s ja t välillä ole polkua.

Solmun valinnan nopeuttamiseksi ylläpidetään myös väliaikaisia tunnuksia TL(i), joissa ilmoitetaan solmujen s ja i VC välisen parhaan polkuehdokkaan pituus.

Aputunnuksia käyttäen on algoritmi seuraavanlainen [15]:

Algoritmi 1: Dijkstran minimipolkualgoritmi

Step 0: [Alustus] VC = {s}, PL(s) = 0. Kaikille muille solmuille määrätään väliaikainen tunnus TL(j) = lsj (= oo, jos solmusta s ei ole sivua solmuun j).

Step 1: [Tunnuksen kiinnittäminen] Virittäjäpuuhun lisätään solmu k, missä k = argmin (TL(j) | j £ VC).

j

Jos TL(k) = oo, ei solmujen s ja t välillä ole polkua. Muuten PL(k) = TL(k) ja VC = VC U {k}. Jos k = t, on haluttu polku löytynyt ja algoritmi lopetetaan.

Step 2: [Aputimnusten päivitys] Määrätään uudet aputunnukset TL{j) = min({TL(j), PL(k) + lkj} | j ¿ VC).

Palataan kohtaan 1.

4 Kapasiteetin allokointiongelma

4.1 Taustaa

Tietoliikenneala on käymässä läpi huomattavia muutoksia. Alalle ennustetaan samanlaista kasvua, minkä tietokonemaailma on kokenut 20 viimeisen vuoden aikana [20]. Tähän asti on suurin kapasiteettitarve syntynyt puhelinliikenteestä, mutta kiinteiden ja langattomien laajakaistaisten palveluiden kysyntä ja tarjon­

ta lisääntyvät nopeasti. Muutoksen syynä on ollut tekniikan kehittyminen, jonka ansiosta esimerkiksi matkapuhelimista ja WWW-surffailusta on tullut hyvin suo­

sittuja.

Tulevaisuudessa vaaditaan verkko-operaattoreilta entistä suurempia tiedonsiirto­

kapasiteetteja entistä halvemmalla. Myös reguloinnin poistuminen ja markkinoi­

den globalisoituminen monimutkaistaa tilannetta. Siirtoverkkojen suunnittelu on haasteiden edessä: verkkojen monimutkaistumisesta huolimatta niistä pitäisi saa­

da varmempia ja kustannustehokkaampia.

Tässä työssä rakennetaan suunnittelussa käytettävät yleisperiaatteet huomioiva malli siirtoverkon kustannustehokkaalle mitoitukselle. Optimointiongelman rat­

kaisualgoritmi toteutetaan Visual Basic -ohjelmointikielellä ja liitetään osaksi So- nerassa kehitettyä verkonsuunnittelutyökalua. Työkalun tarkoituksena on avustaa suunnittelua siten, että suunnittelija huomaa helpommin verkossa olevat ongel­

makohdat ja pullonkaulat ja voi keskittyä tehokkaammin niihin. Työkalu keskit­

tyy vain SDH-verkon (Synchronous Digital Hierarchy) suunnitteluun. Ongelma ei kuitenkaan riipu verkkotyypistä, vaan menetelmä soveltuu pienillä muutoksilla myös muunlaisien verkkojen (esimerkiksi pakettikytkentäiset IP- ja ATM-verkot) mitoitukseen.

Seuraavassa kuvataan SDH-verkon rakenne ja esitetään suunnittelussa huomioi­

tavia periaatteita. Tämän jälkeen rakennetaan siirtoverkon mitoitusmalli.

4.2 SDH-verkon rakenne

SDH-tekniikkaa käyttävä siirtoverkko voidaan jakaa karkeasti kuvassa 6 esitettyi­

hin tasoihin [17]:

Palvelut: data, puhelinpalvelut, GSM, ...

SDH-alataso: VC-12, VC-2, VC-3

SDH-ylätaso: VC-4

Siirtojärjestelmät: STM-N

Siirtomedia: kuitu, kuparikaapeli, radioaallot

Kuva 6: SDH-verkon tasot.

Palvelutasolla jonkin palvelun vaatima kapasiteetti voi riippua voimakkaasti esi­

merkiksi vuorokaudenajasta. Palveluverkot rakennetaan kuitenkin siirtoverkosta varattavien kiinteiden päästä-päähän -yhteyksien (point-to-point) avulla. Yhtey­

det voivat olla myös isompia kokonaisuuksia, joihin on koottu pienempikapasi- teettisiä yhteyksiä. Päästä-päähän -yhteydet ovat siirtoverkosta myytäviä tuot­

teita ja ne muodostavat SDH-alatason. Alatason perussignaaleita voi olla kolmea eri kapasiteettia: VC-12, VC-2 ja VC-3 (lyhenne VC tulee sanoista Virtual Con­

tainer, virtuaalikontti). Lisäksi perussignaaleja voidaan yhdistää konkatenoinnil- la. Tällöin syntyy esimerkiksi signaali VC-2-2c, jossa on kaksi VC-2 -signaalia.

VC-12 -signaalin kapasiteetti on noin 2 Mbit/s, eli se voi välittää esimerkiksi 32 yhtäaikaista kiinteän verkon puhelinyhteyttä. Signaalia pidetään runkoverkon pe­

rusyksikkönä ja varsin usein signaalien kapasiteetit ilmoitetaan sen monikertana,

2Mbit/s ekvivalentteina (2Mekv). Yhteyksien laatuvaatimukset (varmistusvaati- mukset) riippuvat yhteyden käyttötarkoituksesta eli tuoteryhmästä.

Alatason signaalit kootaan ylätason VC-4 -signaaliksi kuvassa 7 esitetyn SDH- mapituskaavion mukaisesti. Kuvassa on esitetty myös perussignaalien kapasitee­

tit. Mapituskaavion mukaisesti VC-4 -signaali voi koostua esimerkiksi 63 kappa­

leesta VC-12 -signaaleja tai 21:stä VC-12 -signaalista ja 2:sta VC-3 -signaalista.

VC-4 -signaali voi olla myös vajaa, sisältäen esimerkiksi vain 45 kappaletta VC- 12 -signaaleja. Ylätasoa kutsutaan myös VC-4 -tasoksi, koska sen ainoa signaa- lityyppi on VC-4. Sekä ylä- että alatason signaaleja kutsutaan myös yhteyksik­

si. VC-4 -yhteyksiä saatetaan kutsua myös VC-4 -ryhmiksi, koska ne koostuvat useista alemman tason signaaleista.

[2Mekv]

VC-2 * STM-N

VC-12

63 21

3

1

Kuva 7: Yksinkertaistettu SDH-mapituskaavio ja perussignaalien kapasiteetit.

SDH-siirtojärjestelmät siirtävät ylätason VC-4 -signaaleja. Järjestelmien tunnuk­

set ovat muotoa STM-N, missä lyhenne STM tulee sanoista Synchronous Trans­

port Module (synkroninen kuljetusmoduli). Numero N taas ilmoittaa järjestelmän kapasiteetin STM-1 -ekvivalentteina, eli kuinka monta VC-4 -signaalia järjestelmä pystyy siirtämään. SDH-tekniikassa käytössä olevat siirtojärjestelmäkapasiteetit on esitetty taulukossa 4.

Siirtoverkkoon kuuluu olennaisena osana myös solmut, joiden välillä siirtojär­

jestelmät ovat. Solmujen tehtävänä on ohjata alatason yhteydet oikeisiin VC- 4 -ryhmiin ja nämä taas haluttuihin siirtojärjestelmiin. Lisäksi laitteilla voidaan

Taulukko 4: SDH-verkon siirtojärjestelmien kapasiteetit.

Järjestelmä

Kapasiteetti 2Mekv STM-lekv

STM-1 63 1

STM-4 252 4

STM-16 1008 16

STM-64 4032 64

toteuttaa liikenteen varmistuksia. Solmuilla on oma kapasiteettinsa, vikaantumis- mahdollisuutensa sekä kustannuksensa. Lisäksi solmuilla voi olla erilaisia kyky­

jä kytkeä liikennettä. Tässä työssä solmut jätetään kuitenkin yksinkertaisuuden vuoksi huomioimatta.

Siirtojärjestelmät tarvitsevat aina myös fyysisen siirtomedian, joita on kolmea tyyppiä [20]: optinen kuitu, kuparikaapeli ja radiolinkit. Kuparikaapelilla on niin lyhyt kantomatka, että sitä voidaan runkoverkossa hyödyntää vain asemien sisäi­

sissä yhteyksissä. Radiolinkkejä saatetaan käyttää jos kaapelin kaivaminen mak­

saisi suhteettoman paljon ja tarvittava siirtokapasiteetti on vähäinen. Suurikapa­

siteettisten radiolinkkien käyttö on kuitenkin hyvin vähäistä. Näistä syistä SDH- verkon siirtomediana on pääsääntöisesti optinen kuitu. Kuitukimppu yhdistetään kaapeliksi, joka kulkee kaapelikaivannossa. Samassa kaivannossa voi kulkea useita kaapeleita. Siirtojärjestelmät ovat kaksisuuntaisia, jolloin ne varaavat kaapelista kaksi kuitua, yhden kumpaankin suuntaan.

Jokainen tasoista muodostaa oman verkkonsa: esimerkiksi VC-12 -yhteys voi kul­

kea usean VC-4 -yhteyden kautta. Yksittäinen VC-4 -yhteys taas saattaa kulkea usean siirtojärjestelmän kautta ja siirtojärjestelmä voi mennä montaa eri kaapelia pitkin. Kuvassa 8 on esitetty edellä kuvatut verkkotasot.

Siirtoverkossa voi sattua monenlaisia vikoja. Pienet laiteviat katkaisevat yksit­

täisen yhteyden tai VC-4 -ryhmän. Myös siirtojärjestelmät saattavat vikaantua.

Kaivinkone voi katkaista kokonaisen kaapelikaivannon, jolloin yhtäaikaisesti vi­

kaantuu useita siirtojärjestelmiä. Laiteasemilla sattuva tulipalo taas voi vioittaa solmun, jolloin kaikki solmusta lähtevät kaivannot katkeavat. Tällainen vikatilan­

ne on kuitenkin niin harvinainen, että siihen ei käytännössä tarvitse varautua.

Tällöin pahin tarkasteltava vika on kaivannon katkeaminen, johon myös kaikki pienemmätkin viat sisältyvät.

Loogiset yhteydet

VC-4 -taso

Siirtojärjestelmät

Kaapelikai vannot

Kuva 8: Tietoliikenneverkon verkkotasot.

Tässä työssä keskitytään siirtojärjestelmätason sekä liikenteen ylä- ja alatasojen suunnitteluun. Liikennetarve ja kaapelireitit oletetaan tunnetuiksi. Lisäksi olete­

taan että kussakin kaapelissa on rajaton määrä kuituja käytettävänä.

4.3 Verkkosuunnittelussa huomioitavia asioita

SDH-siirtoverkon ainoa tehtävä on tietoliikenneyhteyksien siirtäminen pisteestä toiseen halutulla laatutasolla. Tällöin myös suunnittelun ensisijaisema tavoitteena täytyy olla ennustetun liikenteen tarpeiden toteuttaminen. Näitä tarpeita ovat yh­

teyksien siirron lisäksi varmistusvaatimukset. Osalle liikenteestä sekuntin kestävä katkos on liikaa, joten vian sattuessa on varmistuksen toimittava hyvin nopeasti.

Osalle yhteyksistä taas riittää hieman hitaampi varmistus. Myös erilaiset palve­

luverkot voidaan toteuttaa SDH-verkossa kulkevien yhteyksien päälle. Tällaiset yhteydet eivät välttämättä tarvitse lainkaan SDH-varmistusta, jos palveluverkko

varmistaa itse oman liikenteensä. Suunnittelun tärkeä tavoite on myös pitää siir­

toverkko selkeänä ja yksinkertaisena, muuten myöhemmin tehtävät muutokset ja laajennukset hankaloituvat.

Suunnittelun aikataulut vaihtelevat eri tasoilla huomattavasti. Suunnitteluajat on esitetty karkealla tasolla taulukossa 5. Kaapelikaivannot suunnitellaan vuosien päähän, koska kaivaminen voidaan suorittaa vain kesällä ja rakentamisprosessiin kuuluu muun muassa kaivuulupien anomista. Uuden siirtojärjestelmän käyttöön­

ottoa hidastava tekijä on laitevalmistajan toimitusaika. Siirtojärjestelmiä suun­

nitellaankin kuukausi- ja vuositasolla. SDH-ylä- ja alatasolle tehtävät asennukset ovat nopeita, SDH-ylätasolla muutoksia tehdään viikottain ja alatasolla päivit­

täin.

Taulukko 5: Eri tasojen suunnittelun aikasyklit.

Taso Aikasykli

kaivannot

siirto j ärj estelmät SDH-ylätaso SDH-alataso

vuosi -

kuukausi - vuosi viikko - kuukausi päivä

SDH-alatasoa rakennetaan asiakaslähtöisesti, minkä johdosta alatasolle ei voi­

da tehdä pitemmän tähtäimen suunnittelua. VC-4 -taso muodostuu kuitenkin sekä myydyistä että alatason tarpeisiin perustetuista VC-4 -yhteyksistä, joten suunnittelussa on jotenkin huomioitava myös alataso. Suunnittelun lähtökohta­

na käytetään alatasolle ennustettua liikennetarvetta, joka siis on joukko päästä- päähän yhteyksiä. Kullekin yhteydelle on nimetty tuoteryhmä, joka ilmaisee yh­

teyden käyttötarkoituksen. Erilaisia käyttötarkoituksia voivat olla esimerkiksi data-, lankapuhelin- ja matkapuhelinliikenne. Tuoteryhmä ilmaisee myös yhtey­

den varmistusvaatimukset. Seuraavassa on esitetty ylätason muodostuksessa käy­

tettävät kaksi pääperiaatetta:

1. Alatason yhteydet reititetään aina lyhintä reittiä pitkin.

2. Jos kahden solmun välillä oleva yhden tuoteryhmän liikennetarve ylittää tietyn raja-arvon, perustetaan solmujen välille tälle tuoteryhmälle omistettu (dedikoitu) VC-4 -ryhmä.