Traditional networking paradigm, with destination-based forwarding, provides low processing latency in terms of lookup time and it can scale to huge number of rules for traffic engineering. On the other hand, it lacks flexibility in terms of the packet header fields that can be used to implement the traffic engineering rules. The global view of the network or network abstraction is also lacking here, hence it is harder to program the network.

The flexibility and programmability problem are two reasons, among others, that motivate the rise of the Software-Defined Network (SDN) paradigm: higher flexibility for traffic engineering and easier programmability for finer traffic engineering rules. SDN offers a huge degree of flexibility in the network for traffic engineering, for example in an OpenFlow-based network infrastructure, up to 38 packet header fields can be observed. This degree of flexibility comes however with a cost in terms of lookup times for packet forwarding, it does not scale for huge number of rules. The SDN paradigm also introduces the centralized control plane, which makes it easier to program the network. One of the well-known implementation of SDN is an overlay network, which builds a virtual network as an abstraction of the physical network. It simplifies the logical topology and provides more flexibility in terms of network programmability. In the overlay network implementation the rules are placed centrally in the centralized controller, rather than distributed to the network devices, hence it is easier to manage and program the network. The drawback of the centralized rules storing is that the requirement of storage space to store the rules is increasing significantly.

Consequently, while SDN offers high flexibility and network programmability, it comes with problems for traffic engineering: high processing latency and storage requirement. With the increasing number of applications hosted in the network and the increasing needs for finer traffic engineering, more scalable ways to implement finer traffic engineering rules are needed, so the system can scale even with high number of rules.

In this thesis, we address of problem of rule aggregation, a process to combine multiple rules without losing the accuracy of the original individual rules. We also address the problem of packet classification, a process to decide which flow that a packet belongs to and to determine which action needs to be taken for that packet. We propose one possible solution for rule aggregation and packet classification for overlay networks, focusing on 5-tuple traffic engineering rules, with the goal to minimize the storage space requirement and processing latency. The observed system performance metrics are the number of entries stored in the system, the number of entries observed for classification and the lookup times. The proposed solution is evaluated by means of system-level simulation and implementation in the Open Overlay Router and Vector Packet Processing (VPP) platform using synthetic rules generated with real-world distribution. The results are compared with a system without using the proposed rule aggregation and packet classification method. The results show that with the incorporation of both methods, the requirement for storage space and the processing latency can be reduced significantly. As an example, we note that 58.6% maximum saving in the storage required and 29.6% maximum delay reduction can be achieved.

Den traditionella nätverk paradigm, med destination baserad vidarebefordring, ger låg bearbetning fördröjning i form av lookup tider och det kan skalas till stort antal regler för trafikstyrning. Å andra sidan, det saknar flexibilitet när det gäller paketrubrikfält, som kan användas för att genomföra trafikstyrning reglerna. Den globala utsiktet över nätverket eller nätverksabstraktion saknas också här, och därför är det svårare att programmera nätverket.

Problem med flexibiliteten och programmerbarheten problem är två skäl, som, bland annat, motiverar ökningen av Programvarustyrd Network (SDN) paradigm: större flexibilitet för trafikstyrning och enklare programmerbarhet för finare trafikstyrningsreglerna. SDN erbjuder ett stort mått av flexibilitet i nätverket för trafikstyrning, till exempel i en Openflow-baserad nätverksinfrastruktur, upp till 38 pakethuvudfält kan observeras. Denna flexibilitet kommer dock med en kostnad i form av lookup tider för paketbefordran, det skalar inte för stort antal regler. SDN paradigmet inför också den centraliserade styrplanet, vilket gör det lättare att programmera nätverket. En av de välkända genomförande av SDN är ett overlay nät, som bygger ett virtuellt nätverk som en abstraktion av det fysiska nätverket. Det förenklar den logiska topologin och ger mer flexibilitet när det gäller nätverksprogrammerbarhet. I overlay nätet är reglerna placerade i centraliserade kontrollern, snarare än distribuerade till nätverksenheterna, därför är det lättare att hantera och programmera nätverket. Nackdelen med den centraliserade lagring av reglerna är att kravet på lagringsutrymme för att lagra reglerna ökar avsevärt.

Följaktligen medan SDN ger hög flexibilitet och nätverksprogrammerbarhet, kommer det med problem för trafikstyrning: hög processorfördröjning och krav för lagring. Med det ökande antalet applikationer i nätverket och de ökande behoven av finare trafikstyrning, behövs det mer skalbara sätt att genomföra finare trafikstyrningsregler, så att systemet kan skala även med stort antal regler.

I denna avhandling tar vi itu med problemet med aggregering av reglarna, en process att kombinera flera regler utan att förlora noggrannheten av de ursprungliga enskilda reglerna. Vi vänder oss också till problemet med paketklassificering, en process att avgöra vilket flöde som ett paket tillhör och för att avgöra vilka åtgärder som behöver vidtas för att viderbefordra paketet. Vi föreslår en möjlig lösning för regelnaggregering och paketklassificering för overlay-nätverk, med fokus på 5-tuple trafikstyrning regler, med målet att minimera lagerutrymmeskrav och bearbetning latens.

De observerade prestandastatistik är antalet regler som lagrats i systemet, antalet regler som observerades för klassificering och lookup fördröjning.

Den föreslagna lösningen utvärderas med hjälp av systemnivåsimulering och implementering i en Open Overlay Router och Vector Packet Processing (VPP) plattform med hjälp av syntetiska regler som genereras med verklig fördelning. Resultaten jämförs med ett system utan att använda den föreslagna aggregering och paketklassificeringsmetod. Resultaten visar att med införandet av båda metoderna kan kravet på lagringsutrymme och bearbetningsfördröjning minskas avsevärt. Som ett exempel kan 58,6% maximal besparing i lagringsutrymme och 29,6% maximal fördröjning reduktion uppnås.