| |
|
MSc Project: Packet classification using geometric embeddings
|
|
| |
> |
Overview:
Packet classification is a router function that allows fast search and
classification of arriving packets, based on bit-patterns found in them, for
deciding what action to perform. Traditionally the bit-patterns involved
were the address fields of the IP header, and the respective action was
limited to dropping or forwarding the packet.
Modern routers, however, are expected to perform a wide range of actions
from quality of service (QoS) management, prioritisation, access control,
intrusion detection and other. To enable such actions a
number or additional fields need to be matched in a packet, including for
example port numbers, flow labels etc. A list of filter rules implementing
a classifier is then responsible for selecting packets and assigning them to actions.
As this task needs to take place at line card speeds, the algorithm that
searches for filters that match the packet needs to be efficient, and is
often implemented in hardware.
The goal of this project will be to experiment with a strategy for an alternative
(compressed) representation of the filter rules aiming to reduce the number
of steps that the search algorithm needs to make a decision. The idea lies
in mapping the search patterns of interest to a geometric space (embedding)
and associating (classifying) incoming packets with regions in that space.
|
|
| |
> |
Workplan:
Given a set of forwarding and filter rules for QoS-based routing,
firewalling, and other applications, one will need to produce a mapping
of these rules in a multi-dimensional geometric space. Each rule
essentially will correspond to a set of coordinates in that space.
From this representation 3 goals are set.
- Produce a classification data structure (decisions trees) that will
allow fast lookup of the filters that match a packet
- Consider a way for efficiently storing the classidier such that the
amount of memory needed is as minimal as possible
- Test what are the constraints for performing fast updates of the
classifier when new filter rules are added
A comparative evaluation of the approach with ones from the literature
may be carried out in the course of project, given enough time.
NOTE: Given the exploratory/research character of the project. The pursue
of one or more of these goals can suffice for the completion of the project.
|
|
| |
> |
Knowledge areas:
In this project the student will be relying on and developing his knowledge on
- Internet routing, packet classification and Quality-of-Service management
- Decision trees and Data classification algorithms
|
|
| |
> |
Work environment:
|
|
 |
Page updated: 2012-04-24,
Computer Networks Group [cn.cs.unibas.ch]
|
|
