Search

İnternet kullanıcı sayısı ve trafik hacmindeki önemli artış, ağ yönlendirici tasarımı için yeni sorunlar ortaya çıkarmaktadır. Mevcut yönlendiriciler internet trafik artışına ayak uydurabilmek için, yüksek hızda bilgi hatlarını ve çok sayıda hat kartlarının kullanımını desteklemelidir, buda fiziksel alan, güç ve bellek kullanımında artışa gereksinim ortaya çıkarır.Bir yönlendiricinin temel görevleri arasında yer alan paket yönlendirme, internet altyapısı için performans dargeçidi durumundadır. Genel olarak, paket yönlendirme algoritmalarının çoğunluğu yazılım ile gerçeklenir. Fakat, donanım tabanlı çözümlerde yüksek çıkan iş miktarına sahip olmalarından ötürü son yıllarda popüler olmuşlardır. Çıkan iş oranının yanısıra, bellek verimliliği, artımlı / dinamik güncellemeler ve güç tüketimi paket yönlendirme mimarileri için temel başarım metrikleridir. Ağ yönlendiricileri için donanım tabanlı paket anahtarlama mimarileri içerik adreslenebilir bellek (TCAM) tabanlı ve dinamik/statik rastgele erişimli bellek (DRAM/SRAM) tabanlı çözümler olarak iki gruba ayrılabilir. TCAM- tabanlı yapılar basittir ve bu nedenle bugünkü yönlendiriciler için popüler çözümlerdir. Fakat TCAM pahalıdır, çok güç harcar ve yeni adresleme yapılarına ve yönlendirme protokollerineuyumlulukları azdır. Diğer yandan, SRAM daha yüksek yoğunluğa, düşük güç tüketimine, ve yüksek hıza sahiptir. SRAM tabanlı çözümlerde en uzun öntakı eşleşmesi (LPM) yapmak için kullanılan genel veri yapısı bir çeşit ağaç veri yapısıdır. Bu çözümlerde eşleşen en uzun öntakıyı bulmak için çok sayıda bellek giriş/çıkışı gerekmektedir. Bu nedenle çıkan iş oranını iyileştirebilmek için paralel ve boru hattı davranışlı teknikler kullanılmaktadır.Bu tezde yüksek başarımlı paket yönlendirme için TCAM ve SRAM tabanlı, paralel ve boru hattı davranışlı mimarileri incelendi. TCAM tabanlı paralel IP paket yönlendirme mimarisinin üzerine başarımını arttırmak için, bellek etkin bağımsız öntakı seti oluşturma algoritmasının kullanımını önerdik. Bu tezin temel katkısı olarak, öntakı ağacı kullanan IP paket araması için SRAM tabanlı, paralel, birbirini kesen ve değişken uzunluklu çoklu boru hatlı yeni bir dizilim yapısı (SAFIL) tasarladık. SAFIL üzerine inşa edilmis¸çift giriş çıkışlı SRAM tabanlı daha yüksek çıkan iş gücüne sahip bir IP arama mimarisi (SAFILD) de önerdik. IParaması için geleneksel öntakı ağaç yapısına alternatif olarak ise sıkışık kümelenmiş ağaç (CCT) olarak adlandırdığımız bellek etkin bir veri yapısı önerdik. Ayrıca, alan programlanabilir kapı dizilimi (FPGA) üzerinde yüksek bas¸arımlı IPv4/v6 araması ic¸in yeni bir boru hattı davranışlı birleştirilmiş uzunluk-içtakı araması yapan mimariyi (CLIPS) geliştirdik. Son olarak, paket sınıflandırması için bellek kullanımı etkin kümelenmiş sıradüzensel bir arama yapısı (CHSS) tasarladık. CHSS için ayrıca, FPGA üzerinde uygulanan doğrusal, boru hattı davranışlı SRAM tabanlı bir mimari önerdik. A substantial increase in the number of internet users and the traffic volume bring new challengesfor network router design. The current routers need to support higher link data rates and large number of line cards to accommodate the growth of the internet traffic, which necessitate an increase in physical space, power and memory use.Packet forwarding, which is one of the major tasks of a router, has been a performance bottleneckin internet infrastructure. In general, most of the packet forwarding algorithms are implemented in software. However, hardware based solutions has also been popular in recent years because of their high throughput performance. Besides throughput, memory efficiency, incremental/dynamic updates and power consumption are the basic performance challenges for packet forwarding architectures. Hardware-based packet forwarding engines for network routers can be categorized into two groups that are ternary content addressable memory (TCAM) based and dynamic/static random access memory (DRAM/SRAM) based solutions. TCAM-based architectures are simple and hence popular solutions for today?s routers. However, they are expensive, power-hungry, and oer little adaptability to new addressing and routing protocols. On the other hand, SRAM has higher density, lower power consumption, and higher speed. The common data structure used in SRAM-based solutions for performing longest prefix matching (LPM) is some type of a tree. In these solutions, multiple memoryaccesses are required to find the longest matched prefix. Therefore, parallel and pipelining techniques are used to improve the throughput.This thesis studies TCAM and SRAM based parallel and pipelined architectures for high performance packet forwarding. We proposed to use a memory efficient disjoint prefix set algorithm on TCAM based parallel IP packet forwarding engine to improve its performance. As a fundamental contribution of this thesis, we designed an SRAM based parallel, intersecting and variable length multi-pipeline array structure (SAFIL) for trie-based internet protocol (IP) lookup. We also proposed a novel dual port SRAM based high throughput IP lookup engine (SAFILD) which is built upon SAFIL. As an alternative to traditional binary trie, we proposed a memory efficient data structure called compact clustered trie (CCT) for IP lookup. Furthermore, we developed a novel combined length-infix pipelined search (CLIPS) architecture for high performance IPv4/v6 lookup on FPGA. Finally, we designed a memory efficientclustered hierarchical search structure (CHSS) for packet classification. A linear pipelined SRAM-based architecture for CHSS which is implemented on FPGA is also proposed. 156

İnternetin kullanımının artması birçok konuda olduğu gibi internet trafik sınıflandırmaya olan ihtiyacı giderek arttırmaktadır. İnternet trafik sınıflandırma internet servis sağlayıcılar (ISS), kamu kurumları veya özel şirketler için oldukça önemli bir kullanım alanı oluşturmaktadır. Bunun nedeni, her bir kuruluşun kendi internet trafiğini izlemek istemesidir. Buna ilaveten internet trafik sınıflandırma trafik önceliklendirme, trafik şekillendirme ve bant genişliği paylaşımı sağlama gibi ağ yönetim görevleri için kullanılmaktadır. Ayrıca, ağ güvenliği, dinamik erişim kontrolü ve saldırı tespiti gibi internet ağ güvenliği sağlama ve yeni nesil internet ağ mimarilerinin tasarımın da internet trafik sınıflandırmaya ihtiyaç vardır. İnternet trafik sınıflandırma mimarisi tasarımında önemli kriterlerden biri yüksek hızlarda yüksek sınıflandırma doğruluğunu destekleyebiliyor olmasıdır. Özellikle gerçek zamanlı trafik sınıflandırma yapabilmek için 100+ Gpbs hızlara ulaşabilen trafik sınıflandırma mimarisine ihtiyaç vardır. Önerilen mevcut sınıflandırma yöntemlerinin çoğu yazılım tabanlı çözümler olmakla birlikte bu çözümlerin bu hızlara ulaşabilmesi oldukça güçtür. Dolayısıyla yüksek hızlarda internet trafik sınıflandırma yapabilmek için yazılım tabanlı çözümler yerine yüksek hızlarda trafik sınıflandırma yapabilen donanım tabanlı mimariler tercih edilmektedir. Donanım tabanlı mimariler, yüksek hızlara ulaşmalarının yanı sıra bellek verimliliği, çıkan yüksek iş oranı (throughput), dinamik güncelleme ve düşük gecikme gibi trafik sınıflandırma kriterlerinde de yüksek başarım sağlamaktadırlar. Önerilen mevcut internet trafik sınıflandırma çözümlerinden port tabanlı, DPI tabanlı ve sezgisel tabanlı yöntemler şifreli trafik altında ve dinamik port atamalarında düşük performans göstermektedir. Son yıllarda, özellikle şifreli trafik ve dinamik port atamaları altında yüksek doğruluk elde eden makine öğrenmesi (machine learning - ML) tabanlı yöntemler tercih edilmektedir. ML tabanlı yöntemler, trafik akışının (traffic flow) sadece istatistiksel özelliklerine bakarak trafik sınıflandırma yapmaktadır. Yüksek hızlı ve gerçek zamanlı ML tabanlı trafik sınıflandırma için donanım mimarileri tasarımına ihtiyaç vardır. Bu tezde gerçek zamanlı, yüksek hızlarda ve doğrulukta trafik sınıflandırma yapabilmek için makine öğrenmesi tabanlı ve donanım üzerinde gerçeklenen trafik sınıflandırma yöntemleri incelendi. Bu tezin ana katkısı olarak paralel boru hatlı (pipeline) mimariler üzerinde uygulanan yüksek hızlarda ve doğrulukta sınıflandırma yapabilen makine öğrenmesi tabanlı Genişletilmiş Simple CART (E-SC) mimarisi önerilmiştir. Aynı zamanda, benzer katkıları sağlamak amacıyla her bir uygulama sınıfından bir ağaç elde edilen ve ağaçları bitmaplerle zenginleştirilmiş iki aşamalı hibrit bir yapı olan Simple CART Ormanları (SCF) mimarisi önerilmiştir. Son olarak yüksek doğrulukta ve oldukça düşük sınıflandırma gecikmesi sağlayan tek adımlı Bitmap Kodlu Simple CART (BC-SC) veri yapısı önerilmiştir. Alanda Programlanabilir Kapı Dizilimleri (FPGA) tabanlı paralel ve boru hattı üzerinde tasarlanmıştır. Increasing use of the internet is growing the need for internet traffic classification as for many subjects. Internet traffic classification covers a very important usage area for private companies, public institutions, governments and Internet Service Providers (ISPs). The reason for this is that each institution wants to monitor its own internet traffic. In addition, internet traffic classification is used for network management tasks such as traffic prioritization, traffic shaping and bandwidth sharing provisioning. Additionally, internet networking security such as dynamic access control and intrusion detection, and the design of next-generation internet network architectures also require internet traffic classification. One of the important criteria in designing internet traffic classification architecture is that it can support high classification accuracy at high speeds. Especially, in order to make real time traffic classification, reaching up to 100+ Gbps speed internet traffic classification architecture is needed. While most of the proposed classification methods are software based solutions, it is very difficult for these solutions to reach such speeds. Thus, in order to make internet traffic classification faster, hardware-based architectures that can make traffic classification in high speeds are preferred on behalf of softwarebased solutions. Hardware-based architectures are highly successful on traffic classification criterion such as low latency, dynamic update, high throughput, memory efficiency besides reaching higher speeds. Among the proposed Internet traffic classification solutions, port based, DPI based and intuitive based methods show poor performance under encrypted traffic and dynamic port assignments. In recent years, machine learning (ML) based methods, which obtain high accuracy especially under encrypted traffic and dynamic port assignments, have been preferred. ML based methods perform traffic classification by only examining the statistical features of traffic flow. There is a need for designing hardware architectures for high-speed and real-time ML based traffic classification. In this thesis, machine-learning based hardware traffic classification methods were examined in order to achieve real time, high speed and accuracy traffic classification. As the main contribution on this dissertation, Extended-Simple CART (ESC) architecture is proposed that can achieve high accuracy and speed on parallel pipelined architectures. In the meantime, in order to make the similar contributions, Simple CART Forests (SCF) architecture is proposed, which is a two-staged hybrid structure and whose trees are enriched with bitmaps. Finally, a single-step Bitmap Coded Simple CART (BC-SC) data structure is recommended that provides high accuracy and fairly low classification latency. The BC-SC data structure is designed on Field Programmable Gate Arrays (FPGAs) based parallel and pipeline.

Parkinson hastalığı ülkemizde ve dünyada Alzheimer hastalığından sonra en yaygın görülen, sinir sistemini etkileyen motor becerileri (yazma, denge, yutkunma, vb.), konuşma zorluğu, ses kısıklığı, düşünme ve davranış fonksiyonların kısmen veya tamamen kaybolmasına neden olan ve gündelik yaşantıyı olumsuz yönde etkileyen nörodejeneratif (sinir sisteminde geri dönüşü olmayan) hastalıklardan biridir. Hastalığın kesin bir tedavisi olmamakla birlikte hastaların gündelik yaşantılarını etkileyen semptomları azaltmayı sağlayan ilaç tedavisi uygulanmaktadır. Konuşma ve ses bozuklukları, Parkinson hastalığı sürecinin erken teşhisinde başvurulan en belirleyici semptomlardır. Bu amaçla bu çalışmada sesin müzikal özelliklerinin Parkinson hastalığının teşhisindeki etkisi incelenmiştir. Bu doğrultuda, Parkinson hastası ve sağlıklı bireylerden alınan ham ses kayıtlarından sesin ritim, ton, tını, perde ve dinamiklik gibi özellikleri çıkartılarak yapay öğrenme algoritmaları ile hangi özelliklerin hastalığı teşhis etmede daha başarılı olduğu araştırılmıştır.Bu tez çalışması, sesin müzikal özelliklerinin, Parkinson hastalığının teşhisinde kullanıldığı literatürdeki ilk örnek çalışma olacaktır. Parkinson's disease becomes a prevalent neurodegenerative disorder comes after Alzheimer's diseases in our country as well as all around the world. It affects the nervous system motor skills (writing, balance, swallowing, etc.), speech and voice production difficulties, mental and behavioral functions partially or completely. While not being a definitive treatment of this disease, drug therapy is being applied to reduce the symptoms affecting the daily lives of patients.Speech and voice disorders are one of the most significative symptoms of early diagnosis of the Parkinson's disease process. For this purpose, in this study, the effect of musical features on the diagnosis of Parkinson's disease was investigated. The rhythm, tone, timbre, pitch and dynamics features of the voice were extracted from the raw voice recordings of patients with Parkinson's disease and healthy individuals and the machine learning algorithms were used to determine which feature is more successful in diagnosing the disease.This thesis study will be the first case study in the literature in which the musical properties of sound are used in the diagnosis of Parkinson's disease. 96

Sanal yönlendiriciler ağ servislerinin artan taleplerini karşılamak için önemli bir çözüm olmuştur. Sanal yönlendiriciler tek bir donanım platformu kullanarak birden fazla ağa eş zamanlı olarak hizmet sunabilirler; böylece tasarruf sağlarlar. Sanal yönlendiriciler farklı internet servis sağlayıcılarına ait birden fazla yönlendirme tablosunu idame ettirebilir, her bir internet servis sağlayıcı için IP adresi arama ve yönlendirme faaliyetlerini ortak bir platform kullanarak yürütebilirler. Sanal yönlendiricilerde IP adresi arama işlemi paketlerin taşıdığı servis sağlayıcı bilgisi kullanılarak gerçekleştirilir. IP adresi arama için çeşitli yazılım ve donanım çözümleri geliştirilmiştir. Donanımsal çözüm olarak TCAM ve SRAM kullanılırken, yazılım tabanlı çözümlerde daha yavaş olan ağaç yapıları yer alır. Donanımsal ortamın bellek imkanlarının kısıtlı olması uygulamalardaki temel darboğazı oluşturur. Servis sağlayıcılara ait yönlendirme tabloları ayrı ayrı saklanabilir ancak bunun için büyük miktarda bellek gerekmektedir, bu durumda sanal yönlendiriciler önemli bir bellek kazancı sağlayamamaktadır. Tablolardaki benzerliklerden yararlanabilmek için tablolar genellikle birleştirilerek tek bir ortak veri yapısı oluşturulmaktadır.Bellek büyüklüğünü azaltmak, adres arama performansını yükseltmek ve güncelleme işlemleri sanal yönlendiriciler için öne çıkan önemli konulardır. Adres arama performansı gecikme süresi ve birim zamanda gerçekleşen arama sayısı kriterleri ile değerlendirilir.Bu tez çalışmasında, birleştirilmiş bir ağaç (trie) veri yapısı önerilmiş ve bellek ihtiyacının azaltılması hedeflenirken, arama ve güncelleme işlemlerinde de verimlilik sağlanmıştır. IPv4/IPv6 çekirdek ve kenar yönlendiricilere ait gerçek prefix tabloları birleştirilerek tek bir ağaç (trie) oluşturulmuştur. Birleştirilmiş ağaçtaki bazı bölümlerin az sayıda prefix verisi saklamak için yüksek sayıda boş hücre bulundurduğu gözlenmiştir. Çalışmanın çıkış noktası, ağaçtaki bu düşük yoğunluklu bölgeleri ağacın yapısını değiştirmeden ayıklayarak bellek kullanımını azaltmaktır. Esas ağaçtan alınan prefix verileri ikinci bir ağaç (2-3 tree) kullanarak saklanacaktır. 2-3 ağaç yapısı diğer ağaçlara göre hızlı güncelleme yeteneğinden dolayı tercih edilmiştir. Budama ölçütü prefix verilerinin çoğunun esas ağaçta (trie) kalmasını sağlayacak şekilde belirlenmiştir. Önerdiğimiz yapı mevcut çözümlerle kıyaslandığında, IPv4 çekirdek yönlendiricilerinde %5, diğer tipteki yönlendiricilerde %35 seviyelerinde bellek tasarrufu elde etmiştir. Böylece bellek etkinliği arttırılmış ve her bir güncellemenin tek bir yazma mesajı ile gerçekleştirilmesine olanak sağlanmıştır. Önerdiğimiz yapı her bir adres arama işlemini bir saat döngüsünde gerçekleştirebilir niteliktedir ve gecikme süresi de trie yapısı kullanan diğer çözümler ile eşdeğerdir. Virtual router is an essential solution to fulfill the increasing demands of network services. A virtual router, having a single hardware platform, serves several networks concurrently and hence provides cost saving.A virtual router maintains multiple forwarding tables that belong to separate internet service providers (ISPs) and performs IP lookup and forwarding functionality for each ISP in one common platform. IP lookup in a virtual router is performed by inspecting the incoming packets that also carry information about their ISPs. There exist various software and hardware IP lookup solutions in the literature. In software solutions tree or trie based data structures are usually employed which are relatively slower. Hardware solutions use TCAMs or SRAMs and are much faster. Limited on-chip memory is the main bottleneck for hardware implementations. If all ISP forwarding tables of a virtual router are stored separately then a large amount of memory is required and there occurs no benefit for having a virtual router. Therefore tables are usually merged in such a way that the overlapping parts are stored in one common data structure more efficiently. Decreasing the size of the memory and increasing the performance of look up and update tasks are among the primary concerns and challenges in virtual routers. Lookup performance is considered by means of latency and throughput issues.In this thesis, we investigate and propose an efficient trie overlapping approach and aim to decrease the memory requirement while achieving a good IP lookup and update performance. During this study, we examine real life prefix tables that belong to existing routers. We first merge these IPv4/IPv6 core and edge router tables in a simple manner into a single trie and observe that some parts of the trie use a large number of nodes to store a small number of prefixes. This observation has motivated and led us to reduce the size of the trie by truncating some of these low density subtries without destroying the advantageous trie structure too much. 2-3 tree data structure is then proposed to be used as a secondary storage to keep the deleted prefixes from the trie separately. 2-3 tree is preferred because of its support for incremental updates. Our thesis identifies truncation metrics and we use them to keep most of the prefixes still in the trie.Our approach is evaluated and we have shown that it is possible to achieve around 5% reduction in memory size for IPv4 core routers and around 35% reduction for other type of routers in comparison to existing trie merging solutions. Hence memory efficiency is increased while supporting an update process that is possible using a single write bubble. Our solution achieves one lookup per clock cycle throughput and operates with a latency that is standard among other trie based solutions. 111