Proposte di Tesi

by Administrator — last modified Jan 22, 2010 02:53 PM

Sono qui illustrati gli argomenti su cui sono disponibili tesi nell'ambito delle attività del NetGroup. Si tratta di una descrizione generale degli ambiti all'interno dei quali si collocano le tesi. Per ciascuno degli argomenti sono in genere disponibili più tesi, ognuna delle quali si concentra su un insieme di problematiche specifiche.

Proprio perchè¡ inserite in progetti costituiti da varie attività parallele, la maggior parte delle tesi proposte di seguito richiedono disponibilità a tempo pieno (tendenzialmente non si devono avere più di 1-2 esami arretrati per evitare prolungati periodi di sospensione del lavoro di tesi per la preparazione degli esami) e richiedono mediamente 6 mesi di lavoro a tempo pieno.

Tesi di ricerca all'estero

Il Netgroup ha la possibilità di attivare un certo numero di tesi di ricerca all'estero, coperte da un parziale rimborso spese. Queste tesi sono principalmente relative ad argomenti di packet processing ad alte prestazioni oppure alle tematiche di reti peer-to-peer. Per maggiori informazioni, contattare Fulvio Risso, specificando esplicitamente l'interesse per tesi di ricerca all'estero. Specificare anche la media esami, il numero di esami rimanenti, e il presunto periodo di disponibilità per cominciare il lavoro.

Available topics

Currently, the NetGroup is involved in the following topics:

Fast and Flexible Packet Processing
New Generation Internet and Peer to Peer Networks
Other topics

Fast and Flexible Packet Processing

Application-Layer packet filtering (high priority)

Currently no tools exist that are able to filter traffic at the application layer. The most widely used tool, tcpdump, is able to work only on layer-4 ports. This thesis aims at the implementation of a new (public domain) tool that is able to filter traffic at the application layer (e.g., the HTTP traffic is captured independently from the transport-layer port it comes) and it is based on the current capability of detecting application-layer traffic present in the NetBee library. The result will be instrumental to the implementation of a new set of network tools that are able to operate natively at the application-layer.

This thesis may require to spend part of the time in the labs of Telecom Italia, Torino.

High-speed and safe code for intercepting peer-to-peer traffic on ISP networks (high priority)

Internet Service Providers have a desperate need to monitor their traffic (especially peer-to-peer) at high-speed in real-time on their networks. One of the most problematic issue is that that code must be extremely dynamic (i.e. it can be changed on the field), fast, and safe (in order to get high speed it must run at the kernel level). This thesis aims at proposing and evaluating efficient techniques for efficient safe code generation, which aims at executing dynamic code inside the kernel of an operating system with the assurance not to have potential security hazards.

This thesis may require to spend part of the time in the labs of Telecom Italia, Torino.

Traffic monitoring at gigabit speed (high priority)

In these days, 10Gbps is becoming a common speed in the backbone of many Internet Service Providers.
At this speed, flexible traffic monitoring becomes a huge problem. While ISP still need to know some details of their traffic (many ISP have custom probes in order to measure some specific aspect of their traffic, e.g. the number of Bittorent requests), current architectures are not able to cope with the increasing speed while guaranteeing flexible measurements.
This thesis, in collaboration with Telecom Italia Labs, aims at evaluating some of the current hardware/software solutions for flexible network monitoring, pointing out strengths and weakness. The second part of the thesis aims at defining and validating a possible architecture that is capable to support 10Gbps on an ISP backbone.

High Speed Traffic Classifier for Real-Time Analysis (high priority)

While application-layer traffic classification is a widely investigated topic, many researchers focus on accuracy (capability to recognize many applications) while performance are often not taken in high consideration. However, with the ISP backbones often working at 10Gbps, performance are becoming a huge problem.
This thesis aims at evaluating the accuracy and the performance of different traffic classifiers, using a model that has been developed at Politecnico di Torino and Università di Brescia. Particularly, this thesis will address the problem of performance by defining a methodology for creating "realistic" traffic traces. This methodology aims at testing the classifiers also in some at-limit situation, stressing the capabilities of the classifiers under testing.

This thesis will be done in collaboration with Università di Brescia.

Is Dynamic Code Generation a Better Solution for Packet Processing Programs?

Often, packet processing applications are made up of a piece of software (i.e., "the program") and a set of rules written in memory.

For instance, we can take an Intrusion Detection System as example. In the most common implementation, the program loads the first rule from memory (e.g. accept packet if ip.src == X) at packet arrival, and checks the packet agains that rule. If the rule is not satisfied, the program loads the second rule (e.g., accept packets in which ip.dst == Y) and checks the packet agains the second rule. This process is repeated for all the rules, and it will restart from the beginning when a new packet arrives. This behaviour can be modelled as a loop() over the set of rules.

This approach has the advantage that the program can be generated once, and then its behaviour changes according to the input rules. However, this approach cannot guarantee high speed, because the code is not optimized.

Another approach consists in defining a set of structures in memory (e.g., finite state machine) whose structure is dynamically created based on the input rules. These structures drive the execution of the program till an exit condition is reached. A third approach consists in taking the rules and creating dynamically a piece of assembly that implement the processing logic. While this approach introduce some security concern (is the code safe?), it can guarantee higher performances.

This thesis aims at comparing these three approaches from a theoretical point of view (through the creation of a model that is able to predict the processing cost of each technology), and validate these results on a simple, real packet processing application (e.g., packet filtering). The results obtained through this thesis will be extremely useful to understand if dynamic code generation approaches can really guarantee a significant increment in performance, despite their increase in complexity and the security issues involved in these technologies.

The thesis does not intend to address any security issue.

Balancing Hardware and Software in modern Packet Processing Applications

L'esigenza di garantire una maggiore sicurezza agli utenti è sempre più pressante nell'ambito delle reti. In particolare, la capacità di effettuare controlli di livello applicativo (es. firewall, antivirus, IDS) sugli apparati di rete è ritenuta fondamentale per poter garantire la sicurezza dell'infrastruttura anche a fronte di host compromessi. Tuttavia, la velocità delle reti attuali è destinata a crescere in maniera notevole e velocità di accesso maggiori di 1Gbps sono ormai abbastanza comuni, con la conseguente nascita di problemi sulla capacità di implementare soluzioni di controllo efficaci sugli apparati di rete.

La tesi si propone pertanto di affrontare questo problema determinando l'architettura dei componenti hardware e software per ottenere la flessibilità voluta senza andare a scapito della velocità ; la soluzione proposta farà uso dell'architettura di processamento di traffico NetVM, sviluppata presso il Politecnico di Torino. In particolare, la tesi prevede le seguenti fasi:

studio dell'architettura di un applicativo di alto livello (es. snort)
suddivisione delle sue funzioni in blocchi logicamente distinti
definizione di un modello che ne definisca i requisiti e i costi di processamento, valutandone la fattibilità di una loro loro implementazione in hardware
applicazione del modello per determinare le prestazioni ottenibili dall'applicativo qualora parte delle funzionalià siano realizzare in software, altre in hardware
determinazione del "best mix" tra software e hardware, considerando di voler massimizzare le prestazioni data una certa capacità dell'hardware stesso (ad es. in termini di gates disponibili sul chip)

Hardcoding dinamico di algoritmi di pattern e regular expression matching

Nei dispositivi di rete quali router, firewall, IDS, il control plane ha la necessità di istruire in modo dinamico il data plane riguardo alle regole (di forwarding, classificazione, filtraggio, pattern matching) da applicare ai pacchetti in ingresso, in base alle istruzioni fornite dall'amministratore. Ciò avviene generalmente attraverso la compilazione di tabelle, grafi, o strutture dati più complesse, mantenuti in una memoria condivisa tra i due piani. Il control plane in base all'insieme di regole specificate dall'utente aggiorna dinamicamente tali strutture, che vengono sfruttate dai componenti del data plane eseguendo del codice statico.

In tale scenario, la necessità di flessibilità , i.e. la necessità di poter cambiare a runtime il set di regole da applicare sui pacchetti in ingresso al dispositivo, implica una separazione netta tra l'algoritmo utilizzato (fisso) ed i dati (variabili). Ad esempio, supponendo che l'apparato di rete in questione sia un router, il programma di classificazione e forwarding eseguito dal processore sarà fisso e precompilato, mentre le regole potranno variare in modo dinamico a seconda delle necessità dell'amministratore. Tale approccio, anche se di semplice implementazione, soffre di grosse limitazioni sulle prestazioni ottenibili in termini di throughput, a causa della necessità da parte degli algoritmi di effettuare ripetuti lookup in memoria.

Una possibile soluzione a questo problema è quella di fondere gli algoritmi ed i dati su cui questi devono operare mediante tecniche di hardcoding. Ciò consente di eliminare gran parte degli accessi alla memoria, poichÃš il programma lavora su dati costanti. Gli svantaggi di tale approccio consistono nel notevole incremento delle dimensioni del programma e nella necessità di implementare un meccanismo di generazione dinamica del codice per offrire la possibilità di variare a runtime il comportamento dell'apparato.

Lo scopo della tesi Ãš quello di applicare tali considerazioni all'implementazione degli algoritmi di pattern e regular expression matching comunemente utilizzati nei sistemi di intrusion detection:

Studio degli algoritmi di pattern matching
Profiling e caratterizzazione degli stessi in termini di occupazione di memoria e prestazioni ottenibili nelle implementazioni correnti (e.g. in Snort)
Definizione delle linee guida per un'implementazione hardcoded di tali algoritmi e individuazione dei vincoli imposti dall'approccio
Implementazione di un generatore dinamico di codice e dimostrazione dei risultati ottenuti

La tesi verrà preferibilmente svolta in inglese in collaborazione con Cisco Systems, USA.

Design and implementation of a C-like programming language for packet processing

Network processors are special-purpose programmable units designed to process packets at the speed required by modern networks. A large number of different network processors from multiple vendors is currently available, providing the designer with a wide range of different architectures and instruction sets. The downside of this varied environment is the lack of common programming tools.

In order to help the programmers write portable packet processing applications the NetGroup has developed the Network Virtual Machine (NetVM), a virtual machine and architecture that allows writing code once and translating it automatically to native executable code for a variety of commercially available network processors. However, the NetVM is currently programmed by writing applications in its specific assembly-level language, the NetIL.

The aims of this thesis are to design and develop a C-like programming language to write packet processing applications and to implement a compiler that emits NetIL code, thus proving it possible to write portable, optimized packet processing applications in a high-level language.

The language design shall be carefully crafted to take into account the peculiarities of the NetVM architecture that makes available a number of memory devices and functional units such as coprocessors. Moreover, a design goal is to allow the NetVM compiler generate executable code as efficiently as possible, by taking appropriate measures such as carefully limiting the amount of aliasing between memory pointers.

Despite its apparent complexity, this task is expected to last about 4 months. The reason is that most of the code already exists (e.g. the LLVM compiler) and that only the front-end is requires, since both the optimizer and the backend have already been implemented and integrated in the NetVM framework.

Layer 7 processing on a systolic pipelined network processor

Systolic processors are fully synchronous, data-driven machines composed of many interconnected processing units. Data flows from one stage to another every clock cycle, and every processing unit executes a single instruction on the data it receives before forwarding it to the downstream stage. These architectures have been successfully used for signal processing and have now been proposed for packet processing as well under the form of pipelined systolic processors, where the processing units are arranged as a very long pipeline. This design is already commercially available with the Xelerated X11 network processor.

Systolic processors are intrinsically parallel as a large number of packets can be under processing at different pipeline depths at the same time, and provide good and dependable performance by achieving wire speed and allowing the programmer to determine the throughput of the system by means of statical analysis only. However, they are currently mainly targeted towards layer 2 and layer 3 processing.

The aim of this thesis is to determine the feasibility of implementing layer 4-7 processing on systolic pipelined architectures. This poses a number of problems in terms of thread synchronization (systolic machines cannot stall execution, so the traditional mutual exclusion primitives cannot be implemented) and application state upkeep.

The thesis will consist in defining what primitives the programmer needs in order to write a prototype application (such as TCP session tracking) and implementing it on a real hardware platform (such as the Xelerated X11 network processor), highlighting the amount of hardware support required to correctly reproduce the desired semantics for accessing shared data.

Global Optimizations for Packet Processing Software

Current network devices are composed by a set of different modules. For instance, a network device often include a security module (for checking Access Control Lists), an L2/L3 forwarder, a NAT, a firewall, and more.

In order to increase modularity, all these modules are coded from different people, and are operating independently on the network device. That is, a packet enters the network device, it is processed by the first module, then it goes to the second, and so on. Being these modules independent, the processing usually restarts from scratch, leading to a large amount of overhead. For instance, each module checks whether the packet is IP, if it contains a TCP payload, and more. In the past, some research groups proposed a way to combine together packet filters (e.g. PathFinder, 1994). However, packet filters are only a specific application in the packet processing field, although rather common.

This thesis aims extending previous results and undestanding the challenges of creating more modular programs that can share part of the processing (e.g., merging different Control FLow Graphs) in order to optimize performance. The final outcome of this thesis is the definition of a possible software architecture and the associated algorithms that are required to solve this problem.

Bloom filters as a memory data structure for traffic classification

The necessity of precisely classifying network traffic is increasing in importance. There are many reasons for which it is necessary to precisely identify network traffic: security, quality of service, network statistics, etc...

One of the actual problems in network traffic classification is the memory occupation of data structure needed for maintaining network status; in large networks, the number of concurrent sessions can easily grow up over 1 million. Data structures actually used within traffic classifier are optimized for high speed accesses and updates but the memory occupied grows linearly with the number of data memorized (i.e. hash-tables, binary-trees).

Bloom filters are data structures that, using multiple hash functions, permit to memorize data maintaining unchanged the memory occupied, irrespective of the number of data memorized. The main problem of bloom filters is the precision; when a bloom filter is queried for a certain key, it can produce a positive result even if the key is not actually contained within the data structure.

The objective of this dissertation is to evaluate the advantage in terms of memory occupation by using bloom filters for maintaining network status information in a network traffic classifier, paying attention about the impact on precision.

Sviluppo di applicazioni su network processor Cavium

I network processor sono processori progettati espressamente per l'applicazione negli apparati di rete. Essi dispongono dunque di un'architettura ideata il supporto ad operazioni che un processore general purpose non sarebbe in grado di eseguire con lo stesso livello di efficienza.

Lo scopo delle tesi in questo ambito è lo sviluppo di alcune applicazioni e funzionalità di rete su processori Cavium Octeon sfruttando i vantaggi offerti dalla loro specifica architettura. A seconda dello specifico progetto di tesi, lo sviluppo può partire da zero o puÃ² eventualmente essere basato su codice esistente perchè¡ sviluppato in progetti precedenti dal NetGroup, oppure disponibile nel pubblico dominio o in sistemi operativi aperti.

Le maggiori sfide di questa attivitÃ sono l'utilizzo di architetture di processing innovative (ogni processore ha 16 cores ed un certo numero di unità hardware dedicate), e lo sfruttamento del parallelismo intrinseco a questa architettura per ottenere prestazioni elevate.

Automatic partitioning of packet processing applications

Multicore processors designed for packet processing have often tens and sometimes hundreds of cores. The classical partitioning of the workload that consists in executing the same program on all the cores has the advantage of being extremely simple, but the efficiency may be poor due to concurrency hazards.
In that model, a new packet will be delivered to a given core, which will be the only responsible to process that data. If some shared structures (e.g. the session table) are needed, all the cores may become busy waiting for that resource, which might be kept in the shared memory.
We speculate that a clever partition of the workload can mitigate this effect. The packet can start its processing on core1, then migrate to core2 which has the duty of accessing the shared resource. If the number of processors that need to access to that resource is limited, the contention will be limited. Optimally, if we are able to reduce the amount of processing that requires the shared resource, we can imagine that we can concentrate that process on a single core, which can keep the shared data in its memory and avoid the concurrency issues at all.
This thesis aims at exploring this problem, by identifying automatically the sections of the code who present security hazards and by proposing an automatic partition of the workload in order to minimize these issues.

A faster, better Snort

Snort (http://www.snort.org) is one of the best Intrusion Detection Systems available on the Internet. Our Research group implemented a clone of that software, which is running on the NetVM virtual platform (http://www.nbee.org/). This platform has been demonstrated being extremely efficient for other applications (e.g. packet filtering), and it is able to execute programs faster than the equivalent software written in C.

However, the current implementation of the Snort clone is not complete. First, some algorithms are not optimized; second, some features (e.g. the capability to inspect TCP sessions) are currently missing.

The aim of this thesis is to complete the NetVMSnort prototype, demonstrating that a software written for the NetVM platform runs definitely faster than the equivalent software written in C. This result is instrumental for demonstrating that current compilers (e.g., GCC) are not the optimal choice for writing packet processing software.

Automatic Processing for Space Telemetry Data (high priority)

Nel settore spazio, settore piccoli/medi satelliti scientifici si sta cercando di standardizzare e creare prodotti riusabili o comunque riconfigurabili in modo da evitare ogni volta nuovi sviluppi, contrariamente allo stato attuale dove ogni nuovo progetto richiede un nuovo sviluppo. Questo vale per tutte le parti di un satellite e anche per la parte di comunicazione (telemetria e comandi).

Sebbene lo standard CCSDS sia un standard consolidato e regoli la comunicazione tra satellite e Ground station ci sono altre variabili che comunque fino ad ora non permettono il totale riutilizzo di parti già sviluppate. Nasce quindi l'esigenza di avere un layer di comunicazione indipendente dall'interfaccia fisica utilizzata, indipendente dal protocollo e dal formato dei pacchetti, e teoricamente riutilizzabile in ogni applicazione (si dovrà considerare l'utilizzo con differenti sistemi operativi (realtime, RTEMS, VxWorks, DSP/BIOS e non Linux, Windows) e differenti processori (Intel, IBM PPC, DSP Texas e Analog Devices).

La tesi si propone di applicare la tecnologia NetPDL (http://www.nbee.org), sviluppata dal Netgroup, a queste problematiche, permettendo di ottenere una maggiore riusabilità del codice di gestione delle comunicazioni satellitari.
Il lavoro sarà differenziato tra il segmento di volo e per il segmento di terra, in quanto il segmento di volo richiede standard di qualità più alti in modo proporzionale alla criticità dell'applicazione. La tesi verterà su uno solo dei due segmenti.
La tesi verrà svolta in collaborazione con la Carlo Gavazzi Space (http://www.cgs.it); opzionalmente è possibile svolgere la tesi a Milano.

I campi di applicazione nel settore spazio in cui CGS è coinvolta sono numerosi:

piccoli/medi satelliti scientifici e per osservazione della terra (camere iperspettrali e sensori SAR)
stazioni di ricezione dei lanciatori Europei (Arianne5, vega, soyuz)
sistemi di integrazione validazione e test di satelliti e sottosistemi
sistemi di simulazione d'assetto etc.
comunicazione tra i sottosistemi del satellite (OnBoard Data Handling, Power Distribution Unit, GPS, Star Sensor,etc)

New Generation Internet and Peer to Peer Networks

A safer and faster aMule

Frutto di una recente collaborazione con Telecom Italia Labs, il NetGroup ha definito alcuni algoritmi dedicati al Peer-to-Peer (P2P). Tali meccanismi hanno come obbiettivo

La riduzione del tempo di download osservata dagli utenti
La significativa riduzione del consumo di banda dell'Internet Service Provider (ISP)
L'anonimizzazione degli utenti sulla rete P2P

La tesi verterà sull'implementazione di tali algoritmi nel contesto del client P2P aMule.

Scalable and effective routing approaches for data-oriented networks

A possible view of the future Internet is a scenario where the well-known connection-oriented model will become more data-oriented, i.e., the main paradigm driving network operation will be the retrieval of data. This topic is known as data-oriented networking. In this scenario, each single document has to be accessed independently of its location, i.e., each document has to be routable according to a novel data-oriented paradigm that has to drive routing decisions. This approach is powerful and can potentially revolutionize the operation of future computer networks, but data-oriented routing could suffer from scalability issues due to the extremely large amount of data it has to deal with.

The aim of this thesis is to propose proper algorithms to efficiently perform scalable routing in data-oriented networks. Thus, the work will start from a critical analysis of the data-oriented routing approach, in order to point out its strengths and potential lacks.

Effective data caching strategies for next-generation networks

The Internet is generally used to retrieve data and information. The latest news, favorite songs, software applications are some examples. These data are generally stored in a limited number of network nodes and are sent lots of times through the network without any modification. This is not efficient, especially because the same information often pass through the same routers during subsequent downloads.

This thesis aims at studying novel approaches to effectively enable data caching in the Internet, in order to improve both network utilization and quality of service perceived by users. The focus of the work will mainly be on (but not limited to) peer-to-peer networks and applications.

Efficient management of network resources in peer-to-peer overlays

Analysis and measurements run over some Internet Service Provider (ISP) networks show that a significant amount of the traffic over the Internet is produced by peer-to-peer applications. These are historically user-driven applications that operate without the support of ISPs and, thus, without any knowledge about the underlying network topology. This could be very inefficient for both users, which experience low-rate transfers, and ISPs, which have to deal with link congestion due to these large amounts of traffic.

This thesis aims at studying and validating novel approaches for ISPs to effectively control peer-to-peer overlays topology, in order to improve both resource utilization and quality of service perceived by users.

Virtual private peer-to-peer networks

Existent peer to peer protocols have been developed to implement a simple and untrusted data sharing mechanism between unknown users. Thus, they cannot be adopted to exchange sensible data in a business environment.

This thesis aims at studying novel peer to peer approaches which can offer secure data-sharing between trusted users, in order to enable a business-oriented data-sharing service that can be suitable also for enterprises. In particular, the purpose of the work is to define proper policies and algorithms which can effectively enable a secure peer to peer data sharing. These include the overlay architecture and, most of all, the security-related protocols to apply in these novel systems.

Policies and algorithms for service-oriented P2P overlays

The idea of sharing resources across the network has become very popular during the last few years, leading to a diversified scenario in which shared resources include not just files and videos but also storage and CPU cycles. Peer to Peer (P2P) and Grid computing are the most common techniques currently deployed to support resource sharing. In particular, P2P paradigm identifies large-size distributed systems where unstable and transient users dynamically exchange specific resources, such as files (e.g., Gnutella, eMule, bitTorrent) or interact to each other (e.g., Skype). On the other hand, Grid mainly refers to limited-size distributed computational and storage systems usually intended to provide support to intensive computation tasks and complex data management. P2P and Grid recently met in what is known as Desktop Grid computing (e.g., SETI@home, Folding@home), i.e., a distributed computing paradigm that aims to exploit unused resources (storage, computational power, etc.) available on widely located (home) computers. Thus, Desktop Grids are essentially distributed systems where hosts with limited resources (e.g., few free CPU cycles) can submit jobs to other available hosts. This paradigm can be generalized to a distributed service-oriented platform where users can ask for specific services to each other. The idea is that services which are currently provided by centralized solutions migrate to decentralized P2P-based approaches, thus ensuring performances, scalability, and robustness.

This thesis aims at studying a service-oriented architecture where all nodes with proper characteristics are joined in a peer-to-peer overlay network and can offer their services. In particular, the purpose of the work is to define proper policies and algorithms which can effectively enable a P2P-based service oriented platform. These include the overlay architecture, the look-up technique, and the servant choice.

Policies and algorithms for a distributed relay service architecture

The evolutionary trend of the next generation fixed/mobile communication system is towards IP-based networks. A system of this type has to deal with the heterogeneity of end-systems that are present in the network. In particular, private IP address based nodes behind Network Address Translators (NATs), public IPv4 nodes, and IPv6 nodes have to be able to communicate and interwork. Several techniques to enable direct communications have been proposed, but in lots of cases a relay node that acts as intermediary is required. This service is usually offered by a centralized server, with consequent issues concerning the scalability and the robustness of the solution.

In essence, this thesis aims at investigating a specific scenario which can be considered as a case study for the topics explained in the previous thesis description. In particular, the purpose of the work is to define proper policies and algorithms which can effectively enable a distributed relay service. These, again, include the overlay architecture, the look-up technique, and the relay choice.

Sections

Personal tools