Adaptive Routing Approaches for Networked Many-Core Systems

Through advances in technology, System-on-Chip design is moving towards integrating tens to hundreds of intellectual property blocks into a single chip. In such a many-core system, on-chip communication becomes a performance bottleneck for high performance designs. Network-on-Chip (NoC) has emerged as a viable solution for the communication challenges in highly complex chips. The NoC architecture paradigm, based on a modular packet-switched mechanism, can address many of the on-chip communication challenges such as wiring complexity, communication latency, and bandwidth. Furthermore, the combined benefits of 3D IC and NoC schemes provide the possibility of designing a high performance system in a limited chip area. The major advantages of 3D NoCs are the considerable reductions in average latency and power consumption. There are several factors degrading the performance of NoCs. In this thesis, we investigate three main performance-limiting factors: network congestion, faults, and the lack of efficient multicast support. We address these issues by the means of routing algorithms. Congestion of data packets may lead to increased network latency and power consumption. Thus, we propose three different approaches for alleviating such congestion in the network. The first approach is based on measuring the congestion information in different regions of the network, distributing the information over the network, and utilizing this information when making a routing decision. The second approach employs a learning method to dynamically find the less congested routes according to the underlying traffic. The third approach is based on a fuzzy-logic technique to perform better routing decisions when traffic information of different routes is available. Faults affect performance significantly, as then packets should take longer paths in order to be routed around the faults, which in turn increases congestion around the faulty regions. We propose four methods to tolerate faults at the link and switch level by using only the shortest paths as long as such path exists. The unique characteristic among these methods is the toleration of faults while also maintaining the performance of NoCs. To the best of our knowledge, these algorithms are the first approaches to bypassing faults prior to reaching them while avoiding unnecessary misrouting of packets. Current implementations of multicast communication result in a significant performance loss for unicast traffic. This is due to the fact that the routing rules of multicast packets limit the adaptivity of unicast packets. We present an approach in which both unicast and multicast packets can be efficiently routed within the network. While suggesting a more efficient multicast support, the proposed approach does not affect the performance of unicast routing at all. In addition, in order to reduce the overall path length of multicast packets, we present several partitioning methods along with their analytical models for latency measurement. This approach is discussed in the context of 3D mesh networks.

Evaluation of Routing solution for Next Generation Open Platform

Verkkoon kytkettävien laitteiden määrä on lisääntynyt viime vuosina, joka luo tarpeen reitittimille ja niiden ominaisuuksille. On muodostunut uusi tarve laitteille, jotka voivat yhdistää erilaisia verkkoja toisiinsa. Tällaisen reitittimen rakentamiseen tarvitaan vakaa alusta. Tällaisella alustalla luodaan mahdollisuus kuormittaa järjestelmää ilman suuria ongelmia. Tällainen alusta on Open Platform, joka on suunniteltu tällaisille toiminnoille ja yhdessä oikeanlaisen verkkoratkaisun kanssa sitä voidaan käyttää sille suunnitellussa ympäristössä. Tämän diplomityön tarkoituksena on arvioida neljää eri reititysohjelmistoa ja kahta eri IP pinoa. Työssä käytetyt testit on suunniteltu arviointia varten ja niiden tarkoituksena on tuoda esille ohjelmistoissa esiintyvät viat ja ongelmat. Kaikki testit ovat samoja kaikille ohjelmille ja tehdään samassa ympäristössä. Testit analysoidaan niiden ajon jälkeen ja niiden tulosten avulla tehdään päätös mitä näistä ohjelmistoista tullaan käyttämään seuraavan sukupolven avoimella alustalla, joka tulee toimimaan Nokian Intelligent Service Nodessa. Tämä verkon laite toimii yhdyskäytävänäerilaisten verkkojen välillä.

Real-time Quality of Service Controller for Differentiated Services

IP-verkkojen hyvin tunnettu haitta on, että nämä eivät pysty takaamaan tiettyä palvelunlaatua (Quality of Service) lähetetyille paketeille. Seuraavat kaksi tekniikkaa pidetään lupaavimpina palvelunlaadun tarjoamiselle: Differentiated Services (DiffServ) ja palvelunlaatureititys (QoS Routing). DiffServ on varsin uusi IETF:n määrittelemä Internetille tarkoitettu palvelunlaatumekanismi. DiffServ tarjoaa skaalattavaa palvelujen erilaistamista ilman viestintää joka hypyssä ja per-flow –tilan ohjausta. DiffServ on hyvä esimerkki hajautetusta verkkosuunnittelusta. Tämän palvelutasomekanismin tavoite on viestintäjärjestelmien suunnittelun yksinkertaistaminen. Verkkosolmu voidaan rakentaa pienestä hyvin määritellystä rakennuspalikoiden joukosta. Palvelunlaatureititys on reititysmekanismi, jolla liikennereittejä määritellään verkon käytettävissä olevien resurssien pohjalta. Tässä työssä selvitetään uusi palvelunlaatureititystapa, jota kutsutaan yksinkertaiseksi monitiereititykseksi (Simple Multipath Routing). Tämän työn tarkoitus on suunnitella palvelunlaatuohjain DiffServille. Tässä työssä ehdotettu palvelunlaatuohjain on pyrkimys yhdistää DiffServ ja palvelunlaatureititysmekanismeja. Työn kokeellinen osuus keskittyy erityisesti palvelunlaatureititysalgoritmeihin.

Cost Models for Routing and Wavelength Assignment in Wavelength-Division Multiplexing Optical Net

WDM (Wavelength-Division Multiplexing) optiset verkot on tällä hetkellä suosituin tapa isojen määrän tietojen siirtämiseen. Jokaiselle liittymälle määrätään reitin ja aallonpituus joka linkin varten. Tarvittavan reitin ja aallon pituuden löytäminen kutsutaan RWA-ongelmaksi. Tämän työn kuvaa mahdollisia kustannuksen mallein ratkaisuja RWA-ongelmaan. Olemassa on paljon erilaisia optimoinnin tavoitteita. Edellä mainittuja kustannuksen malleja perustuu näillä tavoitteilla. Kustannuksen malleja antavat tehokkaita ratkaisuja ja algoritmeja. The multicommodity malli on käsitelty tässä työssä perusteena RV/A-kustannuksen mallille. Myöskin OB käsitelty heuristisia menetelmiä RWA-ongelman ratkaisuun. Työn loppuosassa käsitellään toteutuksia muutamalle mallille ja erilaisia mahdollisuuksia kustannuksen mallein parantamiseen.

Effective Social Intranet. Case: Mobile Routing Business Unit, Tellabs

The purpose of this thesis is to examine what the normative, effective social Intranet solution is for Tellabs Mobile Routing business unit in terms of sharing knowledge more openly and effectively, fostering innovation, and improving team spirit and positive employee experience. Additionally, these aspects are researched from the intra- and inter-organizational points of view. The research is based on previous literature and empirical interviews. Based on these two items, an eight-fold recommendation proposal was created to change the current Intranet to become an effective social Intranet.

Achieving EU energy targets – Impacts of evolutionary and revolutionary transition paths on power systems

Ambitious energy targets set by EU put pressures to increase share of renewable electricity supply in this and next decades and therefore, some EU member countries have boosted increasing renewable energy generation capacity by implementing subsidy schemes on national level. In this study, two different change approaches to increase renewable energy supply and increase self-sufficiency of supply are assessed with respect to their impacts on power system, electricity market and electricity generation costs in Finland. It is obtained that the current electricity generation costs are high compared to opportunities of earnings from present-day investor’s perspective. In addition, the growth expectations of consumptions and the price forecasts do not stimulate investing in new generation capacity. Revolutionary transition path is driven by administrative and political interventions to achieve the energy targets. Evolutionary transition path is driven by market-based mechanisms, such as market itself and emission trading scheme. It is obtained in this study that in the revolutionary transition path operation of market-based mechanisms is distorted to some extent and it is likely that this path requires providing more public financial resources compared to evolutionary transition path. In the evolutionary transition path the energy targets are not achieved as quickly but market-based mechanisms function better and investment environment endures more stable compared to revolutionary transition path.

Benchmark of routing protocols regarding green considerations

In Mobile Ad-hoc Networks (MANET) the participating nodes have several roles such as sender, receiver and router. Hence there is a lot of energy consumed by the nodes for the normal working of the network since each node has many different roles. Also in MANET the nodes keep moving constantly and this in turn consumes a lot of energy. Since battery capacity of these nodes is limited it fails to fulfil the high demand of energy. The scarcity of energy makes the energy conservation in mobile ad-hoc networks an important concern. There is several research carried out on the energy consumption of mobile ad-hoc networks these days. Some of this research suggests sleep mode, transmission power control, load balancing etc. In this thesis, we are comparing various proposed energy efficient models for some of the ad-hoc protocols. We compare different energy efficient models for Optimised Linked State Algorithm (OLSR) and Ad-hoc On Demand Distance Vector (AODV). The routing protocols are compared for different parameters such as average remaining energy, number of nodes alive, payload data received and performance with different mobility speed. The simulation results helps in benchmarking the various energy efficient routing models for OLSR and AODV protocols. The benchmarking of the routing protocols can be based on many factors but this thesis concentrates on benchmarking the MANET routing protocols mainly based on the energy efficiency and increased network lifetime.

Viability of part cargoes in tramp shipping company’s routing and scheduling decisions

Operational excellence of individual tramp shipping companies is important in today’s market, where competition is intense, freight revenues are modest and capital costs high due to global financial crisis, and tighter regulatory framework is generating additional costs and challenges to the industry. This thesis concentrates on tramp shipping, where a tramp operator in a form of an individual case company, specialized in short-sea shipping activities in the Baltic Sea region, is searching ways to map their current fleet operations and better understand potential ways to improve the overall routing and scheduling decisions. The research problem is related to tramp fleet planning where several cargoes are carried on board at the same time, which are here systematically referred to as part cargoes. The purpose is to determine the pivotal dimensions and characteristics of these part cargo operations in tramp shipping, and offer both the individual case company and wider research community better understanding of potential risks and benefits related to utilization of part cargo operations. A mixed method research approach is utilized in this research, as the objectives are related to complex, real-life business practices in the field of supply chain management and more specifically, maritime logistics. A quantitative analysis of different voyage scenarios is executed, including alternative voyage legs with varying cost structure and customer involvement. An on-line-based questionnaire designed and prepared by case company’s decision group again provides desired data of predominant attitudes and views of most important industrial customers regarding the part cargo-related operations and potential future utilization of this business model. The results gained from these quantitative methods are complied with qualitative data collection tools, along with suitable secondary data sources. Based on results and logical analysis of different data sources, a framework for characterizing the different aspects of part cargo operations is developed, utilizing both existing research and empirical investigation of the phenomenon. As conclusions, part cargoes have the ability to be part of viable fleet operations, and even increase flexibility among the fleet to a certain extent. Naturally, several hinderers for this development is recognized as well, such as potential issues with information gathering and sharing, inefficient port activities, and increased transit times.

Nested Rollout Policy Adaptation for optimizing vehicle selection in complex VRPs

The goal of Vehicle Routing Problems (VRP) and their variations is to transport a set of orders with the minimum number of vehicles at least cost. Most approaches are designed to solve specific problem variations independently, whereas in real world applications, different constraints are handled concurrently. This research extends solutions obtained for the traveling salesman problem with time windows to a much wider class of route planning problems in logistics. The work describes a novel approach that:  supports a heterogeneous fleet of vehicles  dynamically reduces the number of vehicles  respects individual capacity restrictions  satisfies pickup and delivery constraints  takes Hamiltonian paths (rather than cycles) The proposed approach uses Monte-Carlo Tree Search and in particular Nested Rollout Policy Adaptation. For the evaluation of the work, real data from the industry was obtained and tested and the results are reported.

Haitallisen liikenteen havaitseminen ja suodattaminen operaattoriverkoissa

Suomen Viestintävirasto Ficora on antanut määräyksen 13/2005M, jonka mukaan internet-palveluntarjoajalla tulee olla ennalta määritellyt prosessit ja toimintamallit sen omista asiakasliittymistä internetiin lähtevän haitallisen liikenteen havaitsemiseksi ja suodattamiseksi. Määräys ei sinällään aseta ehtoja, kuinka asetetut vaatimukset kukin internet-palveluntarjoaja täyttää. Tässä diplomityössä annetaan määritelmät haitalliselle liikenteelle ja tutkitaan menetelmiä, joilla sitä voidaan havainnoida ja suodattaa paikallisen internet-palveluntarjoajan operaattoriverkoissa. Suhteutettunapaikallisen internet-palveluntarjoajan asiakasliittymien määrään, uhkien vakavuuteen ja tällaisen systeemin kustannuksiin, tullaan tämän työn pohjalta ehdottamaan avoimen lähdekoodin tunkeutumisenhavaitsemistyökalua nopeaa reagointia vaativiin tietoturvaloukkauksiin ja automatisoitua uudelleenreitititystä suodatukseen. Lisäksi normaalin työajan puitteissa tapahtuvaan liikenteen seurantaan suositetaan laajennettua valvontapöytää, jossa tarkemmat tutkimukset voidaan laittaa alulle visualisoitujen reaaliaikaisten tietoliikenneverkon tietovoiden kautta.

Wireless Application Test Bed and Simulations for Broadband Mobile Communications Systems

Langattoman laajakaistaisen tietoliikennetekniikan kehittyminen on herättänyt kiinnostuksen sen ammattimaiseen hyödyntämiseen yleisen turvallisuuden ja kriisinhallinnan tarpeisiin. Hätätilanteissa usein olemassa olevat kiinteät tietoliikennejärjestelmät eivät ole ollenkaan käytettävissä tai niiden tarjoama kapasiteetti ei ole riittävä. Tästä syystä on noussut esiin tarve nopeasti toimintakuntoon saatettaville ja itsenäisille langattomille laajakaistaisille järjestelmille. Tässä diplomityössä on tarkoitus tutkia langattomia ad hoc monihyppy -verkkoja yleisen turvallisuuden tarpeiden pohjalta ja toteuttaa testialusta, jolla voidaan demonstroida sekä tutkia tällaisen järjestelmän toimintaa käytännössä. Työssä tutkitaan pisteestä pisteeseen sekä erityisesti pisteestä moneen pisteeseen suoritettavaa tietoliikennettä. Mittausten kohteena on testialustan tiedonsiirtonopeus, lähetysteho ja vastaanottimen herkkyys. Näitä tuloksia käytetään simulaattorin parametreina, jotta simulaattorin tulokset olisivat mahdollisimman aidot ja yhdenmukaiset testialustan kanssa. Sen jälkeen valitaan valikoima yleisen turvallisuuden vaatimusten mukaisia ohjelmia ja sovellusmalleja, joiden suorituskyky mitataan erilaisten reititysmenetelmien alaisena sekä testialustalla että simulaattorilla. Tuloksia arvioidaan ja vertaillaan. Multicast monihyppy -video päätettiin sovelluksista valita tutkimusten pääkohteeksi ja sitä sekä sen ominaisuuksia on tarkoitus myös oikeissa kenttäkokeissa.

Innovation Benchmark Study: Analysis of Innovation Processes in Finnish Companies

Liikevaihdon orgaaninen kasvu on ensisijainen tekijä ja haaste yritysjohdolle yrityksen omistaja-arvon kasvattamiseksi. Tutkimus tarkastelee suosivatko suomalaisyritykset pääasiallisesti olemassa olevaa liiketoimintaa palvelevia innovaatioita vai tukevatko nykyhetken toimintatavat myös uusia kasvua kiihdyttäviä radikaaleja innovaatioita. Lisäksi työ kartoitti suomalaisyritysten innovaatioprosessien kehitysalueita käyttäen itsearviointitutkimusta.Tulokset johtivat kolmeen johtopäätökseen. Tutkimus osoitti, että vastaajayritykset ovat keskittyneet innovaatiotoiminnassaan vahvasti ydinliiketoimintaansa, jättäen potentiaaliset kasvumahdollisuudet huomioimatta. Yritykset tavoittelevat maksimaalisia tuottoja keskittymällä tuotteidensa korkeaan suorituskykyyn. Lyhyen aikavälin epärealistiset tuotto-odotukset sekä projekteille suunnatut arviointikriteerit rajoittavat liiketoimintaa mullistavien radikaalien innovaatioiden kehittymistä organisaatiossa. Toiseksi, tutkimus osoitti, että suuri osa yrityksistä käyttää perinteisen projektien arviointi- ja kehitysprosessin lisäksi vaihtoehtoisia ja huonosti kontrolloitavissa olevia kehitysprosesseja, mikäli projektille annetaan kielteinen rahoituspäätös standardin prosessin sisällä. Kolmanneksi, suomalaisyritysten innovaatioprosesseissa paljastui merkittäviä puutteita mitattavien elementtien suhteen.