UNIVERZITET U BEOGRADU ELEKTROTEHNIČKI FAKULTET ZORAN G. ČIČA IMPLEMENTACIJA FUNKCIJA PAKETSKOG PROCESIRANJA U INTERNET RUTERIMA VELIKOG KAPACITETA Doktorska disertacija Beograd, 2012. BELGRADE UNIVERSITY SCHOOL OF ELECTRICAL ENGINEERING ZORAN G. ČIČA IMPLEMENTATION OF PACKET PROCESSING FUNCTIONS IN HIGH CAPACITY INTERNET ROUTERS PhD Thesis Belgrade, 2012. MENTOR: dr Aleksandra Smiljanić, vanredni profesor, Beogradski Univerzitet, Elektrotehnički fakultet ČLANOVI KOMISIJE: dr Miodrag Popović, redovni profesor, Beogradski Univerzitet, Elektrotehnički fakultet dr Žarko Markov, naučni savetnik, Institut Iritel dr Milan Bjelica, docent, Beogradski Univerzitet, Elektrotehnički fakultet DATUM ODBRANE: IMPLEMENTACIJA FUNKCIJA PAKETSKOG PROCESIRANJA U INTERNET RUTERIMA VELIKOG KAPACITETA REZIME: Internet predstavlja jedan od najvažnijih temelja razvoja modernog društva i učestvuje u svim aspektima svakodnevnog života - poslovnom, socijalnom, zabavnom, edukativnom itd. Internet je postigao globalni uspeh zahvaljujući svojoj robusnosti i mogućnosti da povezuje različite tehnologije u jednu meñusobno povezanu mrežu. Osnovu arhitekture Interneta čine ruteri koji omogućavaju globalnu povezanost svih delova Internet mreže. Pošto ruteri čine osnovnu gradivnu jedinicu Interneta, performanse i mogućnosti rutera imaju ogroman uticaj na kvalitet rada Internet mreže. Broj Internet korisnika neprestano raste. Takoñe, razvijaju se i nove aplikacije i servisi koji zahtevaju sve veće protoke, usled čega se u Internet mreži instaliraju linkovi sve većih kapaciteta. Kao posledica, količina saobraćaja na Internetu neprestano raste, pa samim tim Internet ruteri postaju sve opterećeniji, naročito u jezgru Internet mreže gde je saobraćaj najintezivniji. Internet ruteri moraju neprestano da se usavršavaju i unapreñuju, da bi mogli veoma brzo obrañivati ogromne količine podataka. Dodatne otežavajuće okolnosti sa stanovišta obrade podataka u ruterima su potreba za uvoñenjem mehanizama kvaliteta servisa i multikast saobraćaj koji je sve popularniji. Mnogi istraživači i naučnici rade na unapreñivanju funkcionalnosti rutera i razvoju novih rešenja i algoritama koji treba da omoguće efikasniji rad rutera. Meñutim, velik problem u razvoju novih rešenja i unapreñenja postojećih funkcija je zatvorenost rutera komercijalnih proizvoñača pa samim tim razvijana rešenja se tipično ispituju zasebno bez potpune integracije sa svim funkcijama rutera. Ovakav način ispitivanja je nepotpun jer ne omogućava kompletan uvid u kvalitet rada novog rešenja u realnom okruženju. Da bi se izbegli navedeni problemi, razvojni tim pod vodstvom dr Aleksandre Smiljanić je u okviru projekta „Sistemska integracija Internet rutera“ podržanog od strane Ministarstva za Nauku i tehnološki razvoj Republike Srbije započeo razvoj prototipa Internet rutera. Konačni cilj projekta je bio razvoj komercijalnog proizvoda, meñutim, pored ovog cilja namera je bila i da se obezbedi otvorena platforma istraživačima i studentima na kojoj bi mogli da proučavaju internu strukturu i arhitekturu rutera i da razvijaju i testiraju nova rešenja u realnom okruženju. Internet ruteri se sastoje iz dve celine tj. ravni - ravan podataka i kontrolna ravan. Ravan podataka je zadužena za brzu obradu korisničkih paketa i stoga je implementirana hardverski. Kontrolna ravan je zadužena za komunikaciju sa okruženjem (drugim ruterima, administratorima itd.) i ona se implementira softverski radi veće fleksibilnosti. U okviru ove teze je razvijen deo ravni podataka koji vrši procesiranje korisničkih paketa. U tezi je objašnjena uloga i funkcije ravni podataka i kontrolne ravni. Takoñe je izvršena klasifikacija i analiza postojećih arhitektura rutera. U okviru projekta „Sistemska integracija Internet rutera“ je odlučeno da se razvija jednostepena arhitektura, pa je stoga odabrana arhitektura rutera sa baferima na ulazu jer je ona najskalabilnija i omogućava podršku velikom broju portova velikih brzina. Usvojeno je da prototip rutera radi sa gigabitskim eternet portovima pošto su oni bili najekonomičniji i najdostupniji u trenutku razvoja prototipa, a omogućavali su testiranje velikih kapaciteta. Ravan podataka se sastoji od paketskih procesora i komutatora (paketskog sviča). U okviru ove teze je izvršena implementacija i analiza paketskih procesora. Prvo su navedene i objašnjene sve funkcije koje paketski procesor mora da izvrši. Paketski procesori su implementirani na FPGA čipovima, pri čemu se u okviru jednog FPGA čipa smeštaju četiri paketska procesora. FPGA čipovi su izabrani za razvoj jer imaju visoke performanse, a njihova konfiguracija se može lako modifikovati što ih čini veoma pogodnim za razvoj. Izvršena je podela funkcija paketskog procesiranja na logičke celine tzv. module. Ulazni modul sloja linka vrši obradu eternet okvira na ulazu u ruter. Ulazni mrežni modul obrañuje IP pakete koji su izdvojeni iz eternet okvira u ulaznom modulu sloja linka. Lukap modul vrši IP lukap tj. pretragu lukap tabele radi odreñivanja na koji izlaz rutera IP paket treba da se prosledi. SGS modul, na osnovu naprednog SGS algoritma, vrši rasporeñivanje ćelija za slanje kroz komutator ka izlazima rutera. Ćelije imaju fiksnu dužinu i dobijaju se segmentacijom IP paketa u ulaznom mrežnom modulu. DDR2 kontroler je modul koji obezbeñuje baferisanje ćelija koje čekaju svoj trenutak za prosleñivanje ka izlazu u DDR2 SDRAM memoriju koja se koristi zbog svog velikog kapaciteta. SERDES modul vrši konverziju paralelnog u serijski prenos i obrnuto radi ostvarivanja brze (multigigabitske) komunikacije sa komutatorom. Izlazni mrežni modul vrši rekonstrukciju IP paketa iz ćelija na izlazu rutera, a izlazni modul sloja linka vrši formiranje eternet okvira za slanje na izlazni link rutera. Svi navedeni moduli su kreirani koristeći VHDL programski jezik i implementirani na FPGA čipove. U razvijenom prototipu rutera je napravljena štampana ploča koja sadrži osam paketskih procesora rasporeñenih na dva FPGA čipa i komutator rasporeñen na jedan FPGA čip. Izvršeno je testiranje razvijenih i implementiranih paketskih procesora, pri čemu je testiranje izvršeno i u realnom okruženju gde se prototip rutera povezivao sa ruterima kompanije Cisco, kao i softverskim ruterima na Linux platformi. Implementirane funkcije paketskog procesiranja predstavljaju najvažniji deo ravni podataka i omogućavaju jasan uvid u način funkcionisanja rutera. Realizovane funkcije se mogu lako modifikovati i unapreñivati, a takoñe se mogu dodavati i nove funkcije čime razvijeni paketski procesori dobijaju na istraživačkom, ali i edukativnom značaju. Implementirani paketski procesori predstavljaju prvi originalan doprinos ove teze. Pored same implementacije izvršena je i analiza svih funkcija paketskog procesora da bi se utvrdila potencijalna uska grla u skalabilnosti rutera koje se ogleda u mogućnosti povećanja broja portova i brzine portova, tj. samog kapaciteta rutera. Analizom je utvrñeno da su najkritičnije funkcije baferisanje ćelija i IP lukap. Baferisanje ćelija je kritično sa stanovišta zahtevanih protoka i dimenzije bafera koji rastu sa povećanjem broja i brzine portova. IP lukap postaje kritičan sa porastom brzine portova kao i neizbežnom tranzicijom na duže IPv6 adrese. U drugome delu teze je izvršena klasifikacija postojećih lukap algoritama koji definišu rad IP lukapa. Postoje tri klase lukap algoritama - algoritmi zasnovani na strukturi stabla, TCAM algoritmi i algoritmi bazirani na heširanju. Sve tri klase su detaljno opisane i analizirane, sa posebnim osvrtom na najpoznatije predstavnike svake klase. Izložena klasifikacija predstavlja značajnu pomoć budućim istraživačima u ovoj oblasti. U tezi je takoñe dat predlog tri nova lukap algoritma koji predstavljaju originalan doprinos ove teze koji je rezultirao objavljivanjem radova u časopisima sa SCI liste, kao i meñunarodnim konferencijama iz ove oblasti. Predloženi lukap algoritmi su detaljno opisani i analizirani. Utvrñeno je da su predloženi lukap algoritmi veoma efikasni i pogodni za hardversku implementaciju jer ekonomično troše hardverske resurse. Izvršena je implementacija predloženih lukap algoritama na FPGA čip, čime je potvrñena njihova hardverska ekonomičnost. Predloženi lukap algoritmi podržavaju velike IPv4 i IPv6 lukap tabele, i ostvaruju visok protok IP lukapa čime su podržani portovi velikih brzina. Veoma je važno naglasiti da se predloženi novi lukap algoritmi mogu integrisati u bilo koji ruter. Takoñe, predloženi lukap algoritmi su uporeñeni sa već postojećim lukap algoritmima i utvrñeno je da predloženi lukap algoritmi imaju minimalne memorijske zahteve koji predstavljaju hardverski resurs koji implementacije lukap algoritama najviše troše. Predloženi lukap algoritmi imaju znatno bolje performanse u slučaju velikih IPv6 lukap tabela u odnosu na postojeće lukap algoritme, što je od ogromnog značaja s obzirom na neminovnu potpunu tranziciju Interneta na duže IPv6 adrese. KLJUČNE REČI: Internet, ruter, paketski svič, ravan podataka, paketsko procesiranje, FPGA, VHDL, IP lukap NAUČNA OBLAST: Telekomunikacije i elektronika UŽA NAUČNA OBLAST: Arhitektura svičeva i rutera UDK BROJ: 621.3 IMPLEMENTATION OF PACKET PROCESSING FUNCTIONS IN HIGH CAPACITY INTERNET ROUTERS ABSTRACT: Internet is one of the most important parts of the modern society. It participates in all aspects of everyday’s life - business, social, entertainment, education etc. Internet achieved global success thanks to its robustness and internetworking between various technologies. Routers enable Internet’s global connectivity and thus represent the foundation of the Internet. As routers are the main components of the Internet, their performances and capabilities have great impact on Internet quality performances. The number of Internet users continuously grows. New applications and services that demand high throughput are constantly developed, and as consequence higher capacity links are installed. The Internet traffic continuously grows, so Internet routers are more and more loaded with traffic, especially in the Internet core, where Internet traffic is most intensive. Therefore, Internet routers must be always upgraded to support high speed processing of large amount of the Internet traffic. QoS mechanisms and multicast traffic represent additional difficulties in the future router development. Many researchers and scientists are involved in router development process that includes development of new solutions and algorithms that enable more efficient router performances. However, the main problem in the development process is the closed router architecture in routers of commercial companies, thus developed solutions are tested without complete integration with the rest of the router functions. This leads to incomplete development and testing. To avoid aforementioned problems, research team led by Aleksandra Smiljanić started Internet router prototype development in the project „System integration of the Internet router“ supported by the Serbian Ministry of Science. The main goal of the project was development of the commercial router. Also, very important goal was development of the open source platform for researchers and students that would be used for the education purposes, as well as the research purposes where new solutions could be tested in the real environment. Internet routers contain two planes - data plane and control plane. Data plane is implemented in hardware and is responsible for fast IP packet processing. Control plane is implemented in software and is responsible for communication with router’s environment (neighbor routers, administrators and etc.). In this PhD thesis IP packet processors are developed and implemented. IP packet processors represent the most important part of the data plane. The role and functions of data plane and control plane are given in this PhD thesis. Also, classification and analysis of the existing router architectures is given. As the decision was to implement router prototype based on the single stage architecture, router architecture based on input buffers was chosen as this architecture is the most scalable among the single stage architectures. Router prototype supports gigabit ethernet ports. Gigabit ethernet ports were chosen as they were the most economical choice at the time when the router prototype development started. Gigabit ethernet ports enable the testing of high capacities in the developed router prototype. Data plane contains packet processors and crossbar. Implementation and analysis of packet processors is given in this thesis. First, the list of all packet processing functions is given and each function is explained. Packet processors are implemented on FPGAs, where four packet processors fit on one FPGA. FPGA chips are selected as they have very high performances and can be reconfigured which makes them very attractive in the research process. Packet processing functions are grouped in modules. Link layer input module processes incoming ethernet frames. Network input module processes IP packets extracted from incoming ethernet frames. Lookup module performs IP lookup where lookup table is examined to determine output port to which the IP packet should be forwarded. SGS module, based on the advanced SGS scheduling algorithm, schedules cells for the transmission to output ports via crossbar. Cells have fixed size and are result of the IP packet segmentation in the network input module. DDR2 controller is the module that stores cells in buffers. The buffers are implemented in DDR2 SDRAM memory as these memories have very large storage capacities. SERDES module performs serial to parallel conversion and vice versa in its communication to crossbar over high capacity internal links. Output network module reassembles IP packets, while output link layer module encapsulates reassembled IP packets in the ethernet frames for the transmission over the output link. All aforementioned modules are developed using the VHDL programming language and implemented on the FPGA chips. Printed board has been designed and it contains eight packet processors implemented on two FPGA chips and crossbar implemented on one FPGA chip. Implemented packet processors were tested using the real environment that included Cisco routers and Linux based software routers. As previously mentioned, implemented packet processors are the most important part of the data plane. Implemented packet processors can be modified and upgraded, and new functions can also be added. Thus, developed packet processors can be used for research and education purposes. The developed packet processors represent the first original contribution of this thesis. All packet processing functions are analyzed to determine which functions are potential bottlenecks in the router scalability. Analysis shows that the most critical functions are cell buffering and IP lookup. Cell buffering becomes critical when the number of ports or capacity of ports is increased because needed buffer throughput or size can become too large for practical implementation. IP lookup becomes critical when the port speed is increased and also when the IP addresses becomes longer which is inevitable due to the transition to longer IPv6 addresses. Classification of existing lookup algorithms is given in this thesis. There are three classes of the lookup algorithms - tree based lookup algorithms, TCAM lookup algorithms and hash based lookup algorithms. A detailed description and analysis is given for all three classes of the lookup algorithms. Also, the most popular lookup algorithms in every class are thoroughly described and analyzed. The provided classification represents significant help for any researcher in this area. Three new lookup algorithms are proposed in this thesis. The proposed lookup algorithms represent the original contribution of this thesis that resulted in several publications in renowned magazines and conferences. A detailed description and analysis of the proposed lookup algorithms is given. The proposed lookup algorithms are hardware efficient as they economically use hardware resources. All proposed lookup algorithms are implemented on FPGA chips. The FPGA implementation shows that the proposed lookup algorithms frugally use FPGA resources and thus are suitable for hardware implementation. The proposed lookup algorithms support very large IPv4 and IPv6 lookup tables and achieve very high lookup throughput and thus support high speed ports. It is important to notice that the proposed lookup algorithms can be integrated in any router. The proposed lookup algorithms are also compared with the existing lookup algorithms. The comparison shows that the proposed lookup algorithms have minimal memory requirements. Memory requirements represent the most used hardware resource by lookup algorithms. The proposed lookup algorithms significantly outperform existing lookup algorithms in the case of very large IPv6 lookup tables, which is important property as the transition to longer IPv6 addresses is inevitable. KEYWORDS: Internet, router, packet switch, data plane, packet processing, FPGA, VHDL, IP lookup SCIENTIFIC AREA: Communications and electronics SCIENTIFIC SUBAREA: Switch and router architecture UDC NUMBER: 621.3 SADRŽAJ 1. UVOD ...................................................................................................................................................... 1 2. ARHITEKTURA RUTERA .................................................................................................................. 4 2.1. TIPOVI ARHITEKTURA RUTERA .......................................................................................................... 7 3. FPGA IMPLEMENTACIJA PAKETSKIH PROCESORA ............................................................ 15 3.1. ARHITEKTURA PROTOTIPA RUTERA ................................................................................................. 17 3.2. IMPLEMENTACIJA PAKETSKOG PROCESORA ..................................................................................... 21 3.2.1. Ulazni modul sloja linka ......................................................................................................... 25 3.2.2. Ulazni mrežni modul ............................................................................................................... 26 3.2.3. Lukap modul ........................................................................................................................... 28 3.2.4. SGS rasporeñivač ................................................................................................................... 32 3.2.5. DDR2 kontroler ...................................................................................................................... 34 3.2.6. SERDES modul ....................................................................................................................... 37 3.2.7. Izlazni mrežni modul ............................................................................................................... 38 3.2.8. Izlazni modul sloja linka ......................................................................................................... 40 3.2.9. Interfejs ka procesorskom modulu .......................................................................................... 40 3.2.10. Performanse implementacije paketskog procesora............................................................... 41 4. PREGLED LUKAP ALGORITAMA................................................................................................. 44 4.1. LUKAP ............................................................................................................................................. 44 4.2. KLASIFIKACIJA LUKAP ALGORITAMA ............................................................................................... 49 4.3. ALGORITMI ZASNOVANI NA STRUKTURI STABLA ............................................................................. 51 4.3.1. Kompresija putanje ................................................................................................................. 52 4.3.2. Guranje prefiksa u listove stabla ............................................................................................ 53 4.3.3. Multibitska stabla ................................................................................................................... 54 4.3.4. Bitmap tehnika ........................................................................................................................ 57 4.3.5. Kompresija nivoa .................................................................................................................... 59 4.3.6. Paralelizacija i pajplajn ......................................................................................................... 60 4.3.7. Predstavnici lukap algoritama zasnovanih na strukturi stabla............................................... 61 4.4. TCAM ALGORITMI .......................................................................................................................... 72 4.4.1. Optimizacija potrošnje ............................................................................................................ 74 4.4.2. Optimizacija kapaciteta .......................................................................................................... 77 4.4.3. Predstavnici TCAM lukap algoritama .................................................................................... 78 4.5. ALGORITMI BAZIRANI NA HEŠIRANJU .............................................................................................. 83 4.5.1. Blum filtri ................................................................................................................................ 86 4.5.2. Predstavnici lukap algoritama baziranih na heširanju ........................................................... 89 5. PREDLOG NOVIH LUKAP ALGORITAMA .................................................................................. 93 5.1. BPFL ............................................................................................................................................... 94 5.1.1. Analiza performansi BPFL-a ................................................................................................ 103 5.1.2. BPFLSM ............................................................................................................................... 108 5.1.3. BPFLSS ................................................................................................................................. 113 5.2. POREĐENJE PREDLOŽENIH LUKAP ALGORITAMA SA POSTOJEĆIM REŠENJIMA ................................. 118 5.3. FPGA IMPLEMENTACIJA PREDLOŽENIH LUKAP ALGORITAMA ........................................................ 127 6. ZAKLJUČAK ..................................................................................................................................... 130 LITERATURA ....................................................................................................................................... 131 SPISAK SKRAĆENICA ........................................................................................................................ 139 A. MEMORIJSKI ZAHTEVI LUKAP ALGORITAMA ZA ANALIZIRANE IPV4 I IPV6 LUKAP TABELE .................................................................................................................................................. 140 A.1. POSTOJEĆI LUKAP ALGORITMI ...................................................................................................... 140 A.1.1. FIPL algoritam ..................................................................................................................... 140 A.1.2. EHAF algoritam ................................................................................................................... 142 A.1.3. POLP algoritam ................................................................................................................... 142 A.1.4. Stablo sa prioritetima ........................................................................................................... 145 A.1.5. Osnovni TCAM algoritam .................................................................................................... 148 A.1.6. TCAM algoritam sa kofama promenljive veličine ................................................................ 149 A.1.7. M-12Wb ................................................................................................................................ 152 A.1.8. Osnovni lukap heš algoritam ................................................................................................ 153 A.1.9. PFHT algoritam ................................................................................................................... 158 A.2. PREDLOŽENI NOVI LUKAP ALGORITMI ........................................................................................... 162 A.2.1. BPFL i njegove modifikacije (BPFLSM i BPFLSS) ............................................................. 162 B. MRT FORMAT LUKAP TABELA RUTERA ............................................................................... 167 BIOGRAFIJA ......................................................................................................................................... 172 1 1. UVOD Internet je postao nezaobilazan element svakodnevnog života, pa se u razvijenim zemljama čak svrstava u elementarna ljudska prava. Ljudi svakodnevno koriste Internet u različite svrhe: poslovne, zabavne, društvene itd. Moderno poslovanje je nezamislivo bez upotrebe Interneta u cilju pružanja informacija o samoj firmi i njenim delatnostima, ostvarivanju kontakata sa poslovnim partnerima, pružanja usluga korisnicima poput e- kupovine itd. S druge strane Internet značajno učestvuje i u društvenom i zabavnom životu. Socijalne mreže su doživele ogroman napredak i omogućavaju jednostavno povezivanje ljudi. Takoñe, Internet omogućava pristup raznovrsnom multimedijalnom sadržaju, pri čemu multimedijalni striming sadržaji dobijaju sve više na popularnosti i značaju poput IPTV. Pored toga, Internet se posmatra i kao ‘živa’ enciklopedija koja omogućava pronalaženje raznovrsnih informacija od interesa. Na osnovu svega navedenog očigledno je da je Internet nosilac današnjeg informacionog društva i integralni deo svakodnevnog života. Otuda je neophodno raditi na daljem usavršavanju Internet tehnologije i omogućavanju još kvalitetnijih karakteristika i usluga Internet mreže. Osnovu Internet infrastrukture čine ruteri koji omogućavaju globalnu povezanost i integrisanost mreža različitih tehnologija i karakteristika. Ruteri vrše usmeravanje IP paketa tako da oni stignu do željenog odredišta. Ali, da bi izvršili osnovnu funkciju, ruteri implementiraju niz funkcija koje doprinose kvalitetu i raznovrsnosti usluga Internet mreže. S obzirom da broj Internet korisnika i dalje raste, kao i sam Internet saobraćaj, linkovi sve većih kapaciteta se postavljaju u Internet mrežu. Isto tako pored tradicionalnog saobraćaja poput veb surfovanja, čitanja mejlova, transfera fajlova i sl., danas je sve zastupljeniji i multimedijalni saobraćaj u realnom vremenu koji ima potpuno drugačije zahteve u pogledu kvaliteta servisa koji Internet mreža treba da pruži. Multimedijalne aplikacije zahtevaju veoma male varijacije kašnjenja, ograničena kašnjenja s kraja na kraj, a u slučaju prenosa kvalitetnog video zapisa i visoke protoke. Takoñe i multikast saobraćaj postaje sve prisutniji pri čemu on donosi nove probleme u implementaciji rutera jer značajno više opterećuje interne resurse rutera klasičnih 2 arhitektura koje su uglavnom dizajnirane za podršku unikast saobraćaja nemajući u vidu podršku za multikast saobraćaj. Stoga su moderni ruteri veoma složeni ureñaji koji moraju da podržavaju velike kapacitete linkova, a samim tim i veliku količinu saobraćaja koji prolazi kroz njih, pri čemu ne smeju da postanu usko grlo daljeg razvoja Interneta. U okviru projekta ‘Sistemska integracija Internet rutera’ podržanog od strane Ministarstva za nauku i tehnološki razvoj Srbije, razvijen je prototip Internet rutera velikog kapaciteta. U okviru rada na razvoju prototipa bilo je neophodno implementirati ravan podataka rutera kroz koju bi se usmeravali korisnički IP paketi. Paketski procesori implementiraju funkcije ravni podataka. U njima se vrši prijem i ispitivanje paketa, rasporeñivanje paketa za slanje ka izlaznim portovima, kao i samo slanje paketa na izlazni link rutera. Ova teza predstavlja rezultate rada na razvoju paketskog procesora u okviru razvijanog prototipa rutera. U ovaj razvoj su uključena i originalna rešenja koja prevazilaze ograničenja postojećih algoritama. U okviru ove teze je razvijen i implementiran paketski procesor koji se koristi u okviru prototipa Internet rutera i on predstavlja prvi doprinos ove teze. Implementacija je izvršena na FPGA (Field Programmable Gate Array) čipovima pošto oni omogućavaju laku modifikaciju i unapreñenje dizajna, kao i dodavanje dodatnih funkcionalnosti paketskom procesoru. Trenutna verzija prototipa rutera ima osam gigabitskih eternet portova. Pored omogućavanja pravilnog rada samog prototipa, implementirani paketski procesor ima još dva bitna aspekta - edukativni i istraživački. Naime, implementirani prototip omogućava studentima lakše razumevanje rada delova rutera, ali i mogućnost implementacije pojedinih funkcionalnosti paketskog procesora i njihovo testiranje u realnom okruženju, odnosno na razvojnoj platformi koju čine paketski procesor i prototip rutera. Takoñe je bitan i istraživački aspekt. Razvijeni prototip rutera predstavlja otvorenu platformu koja omogućava domaćim istraživačima razvoj i implementaciju naprednih funkcionalnosti paketskog procesora i njihovo testiranje u realnom okruženju. Pri tome je omogućen fokus samo na pojedine funkcionalnosti paketskog procesora pošto bi razvijeno rešenje trebalo samo integrisati sa (postojećim) ostatkom paketskog procesora, pa nije neophodan razvoj kompletnog paketskog procesora da bi se ispitao samo jedan njegov deo. 3 Cilj istraživačkog tima koji je radio na razvoju prototipa rutera je i podrška za portove velikih brzina (10Gb/s i većih). Otuda je u okviru teze izvršeno i ispitivanje potencijalnih uskih grla u proširenju kapaciteta rutera tj. njegove skalabilnosti. Utvrñeno je da IP lukap i realizacija paketskih bafera predstavljaju najkritičnije tačke u povećanju brzine paketskog procesora. Prema lukap algoritmu se odreñuje za svaki IP paket na koji izlazni port treba da se usmeri, i zatim se ti paketi čuvaju u baferima dok čekaju na prosleñivanje ka izlaznim portovima rutera. U drugom delu teze je izvršena klasifikacija postojećih lukap algoritama. Takoñe, detaljno su opisani i analizirani najpoznatiji predstavnici svake klase. Izložena klasifikacija i analiza predstavljaće veliku pomoć budućim istraživačima lukap algoritama. Potom je dat predlog novih lukap algoritama koji predstavljaju originalni doprinos ove teze koji je rezultirao objavljivanjem nekoliko naučnih radova u renomiranim časopisima i konferencijama. Predloženi lukap algoritmi su detaljno opisani i matematički analizirani. Utvrñeno je da predloženi lukap algoritmi troše minimalne hardverske resurse što je i potvrñeno njihovom hardverskom implementacijom. Takoñe, korišćenjem tehnika paralelizacije i pajplajna je postignut visok protok predloženih lukap algoritama koji u najgorem slučaju iznosi 64Gb/s, pri čemu je važno naglasiti da bi ova brzina u najgorem slučaju bila i veća ako bi se koristili integrisani čipovi boljih performansi. Izvršena je i komparativna analiza predloženih lukap algoritama sa postojećim lukap algoritmima koja je pokazala velike prednosti predloženih lukap algoritama, naročito u pogledu velikih IPv6 lukap tabela, što je od posebnog značaja imajući u vidu neminovan prelaz Interneta na duže IPv6 adrese. Teza je organizovana u šest poglavlja. Posle uvoda, u drugom poglavlju je dat opis strukture rutera i pregled arhitektura rutera što je neophodno da bi se bolje shvatila pozicija paketskog procesora u ruteru. U trećem poglavlju je izložena implementacija paketskog procesora namenjena i upotrebljena u razvijenom prototipu rutera, pri čemu su opisani i analizirani svi delovi paketskog procesora. U četvrtom poglavlju je objašnjena uloga lukap algoritma i klasifikovani su postojeći lukap algoritmi pri čemu su analizirani najpoznatiji predstavnici svake klase. U petom poglavlju su predloženi novi lukap algoritmi pri čemu je data njihova analiza kao i rezultati implementacije. Takoñe su predloženi lukap algoritmi uporeñeni sa postojećim lukap algoritmima. Šesto poglavlje predstavlja zaključak teze u kom su data završna razmatranja. 4 2. ARHITEKTURA RUTERA Ruteri predstavljaju osnovne mrežne elemente Interneta koji omogućavaju globalnu povezanost Internet mreže. Osnovna funkcija rutera jeste usmeravanje IP paketa kroz Internet do njihovog konačnog odredišta. Meñutim, iako naizgled ruteri obavljaju jednostavnu osnovnu funkciju oni su veoma složeni ureñaji. Da bi uopšte mogli da vrše svoju osnovnu funkciju usmeravanja IP paketa, neophodno je da poznaju topologiju mreže u kojoj se nalaze. Otuda je neophodno da ruteri implementiraju protokole rutiranja koji omogućavaju automatsko i dinamičko učenje rutera o topologiji mreže u kojoj se nalaze i na osnovu koje mogu da prave svoje lukap tabele tj. tabele usmeravanja koje su neophodne za obavljanje funkcije usmeravanja paketa. Pošto ruteri predstavljaju osnovnu komponentu Interneta koja je neophodna za njegovo funkcionisanje, neophodno je uspostaviti mehanizme zaštite i bezbednosti rutera od raznih zlonamernih napada koji mogu negativno da utiču na rad rutera, a samim tim i na rad Internet mreže, pa ruteri moraju da implementiraju i mehanizme autentifikacije, autorizacije, šifrovanja podataka, filtriranja paketa i drugih mehanizama zaštite. Važno je i da ruteri uvek budu raspoloživi tj. da vreme ispada iz rada rutera bude što manje, stoga je važno uspostaviti i kvalitetne mehanizme nadgledanja, pri čemu je važno omogućiti i udaljeni nadzor i pristup ruteru. S obzirom na veoma raznovrstan saobraćaj po pitanju zahteva u pogledu kvaliteta servisa, ruter mora da podrži i mehanizme za ostvarivanje različitih nivoa kvaliteta servisa, poput uvoñenja prioriteta pri opsluživanju, rezervacije kapaciteta i sl. Kapaciteti linkova takoñe rastu, pri čemu ruteri mogu sadržati i velik broj portova, pa je neophodno da ruter ima velik kapacitet tako da može da prosleñuje veoma velike količine paketa u jedinici vremena sa svojih ulaznih na svoje izlazne portove. Pored ovih navedenih osobina i zahteva koje ruter mora da poseduje i podrži, postoji i niz drugih, te je očigledno da je ruter veoma složen ureñaj. 5 Slika 2.1. – Funkcije kontrolne ravni i ravni podataka rutera S obzirom na složenost rutera, napravljena je podela rutera na dve ravni – ravan podataka i kontrolnu ravan [1]-[7]. Ova podela je načinjena na osnovu poslova koje ruter mora da izvrši. Na slici 2.1 su prikazane funkcije koje izvršavaju ravan podataka i kontrolna ravan. S jedne strane je potrebno da se obavi usmeravanje korisničkih paketa velikog protoka kao osnovna funkcija rutera. S druge strane je neophodan velik skup kontrolnih protokola neophodnih za ispravno i kvalitetno obavljanje osnovne funkcije rutera. Kontrolni protokoli podrazumevaju razmenu kontrolnih poruka čiji je protok znatno manji. Istovremeno rezultat kontrolnih protokola se često aplicira na sve portove. Zbog toga se razdvajaju ravan podataka koja obuhvata obradu korisničkih paketa, i kontrolna ravan koja podrazumeva obradu kontrolnih podataka. Zbog svojih različitih priroda, ravan podataka se implementira u hardveru, a kontrolna ravan u softveru. Naime, protokoli kontrolne ravni se izvršavaju na procesoru opšte namene. Na ovaj način kontrolna ravan postaje laka za održavanje i unapreñivanje, a funkcije kontrolne ravni koje ruter treba da podrži se lako dodaju kao novi procesi operativnog sistema ili aplikacije koje se izvršavaju koristeći operativni sistem rutera koji je podržan na centralnom procesoru opšte namene. Proizvoñači rutera, kao i neki autori, često dodatno razlikuju kontrolnu ravan i ravan menadžmenta [8]-[11]. One se izvršavaju u okviru istog operativnog sistema rutera, tako da sa stanovišta fizičke pozicije ove dve ravni u ruteru nema nikakve razlike, a jedina razlika je u skupu funkcija. Kontrolna ravan se odnosi na mehanizme i funkcije kontrole rada ravni podataka poput protokola rutiranja, mehanizama kvaliteta 6 servisa, rezervacije resursa, multikast podrške i dr. Menadžment ravan se odnosi na funkcije upravljanja ruterom poput konfigurisanja rada rutera, nadgledanja rada rutera, alarmiranja u slučaju neispravnosti, omogućavanja udaljenog pristupa ruteru i dr. Slika 2.2. – Struktura rutera velikog kapaciteta Tipična struktura rutera velikog kapaciteta je prikazana na slici 2.2. Sledeći moduli sačinjavaju rutere velikog kapaciteta [1]-[7]: • linijski moduli • procesorski moduli • komutacioni moduli • bekplejn Linijski i komutacioni moduli pripadaju ravni podataka, dok procesorski moduli pripadaju kontrolnoj ravni. Linijski moduli sadrže ulazne/izlazne portove i implementiraju prva tri sloja OSI referentnog modela u ravni podataka i izvršavaju ranije navedene funkcije ravni podataka. Linijskih modula tipično ima više pošto ruteri velikih kapaciteta implementiraju veliki broj portova. Dizajn rutera je tipično modularan i skalabilan, da bi se prilagodio različitim saobraćajnim opterećenjima. Komutacioni modul izvršava prosleñivanje paketa sa ulaznih na odgovarajuće izlazne portove. Često se ovaj modul označava i kao krosbar modul, paketski svič ili komutaciona matrica (switching fabric). U praksi se najčešće koristi termin paketski svič. Procesorski modul sadrži procesor na kome se postavlja operativni sistem rutera i koji izvršava funkcije kontrolne ravni. Uobičajeno, ruteri sadrže samo jedan procesorski modul, ali ih može biti i više ukoliko kapacitet rutera to zahteva. Svi moduli se hardverski prave u vidu kartica koje se povezuju na bekplejn. Bekplejn ili bekpanel predstavlja štampanu ploču 7 koja definiše pozicije kartica (pozicije gde se utiskuju linijski moduli, a gde procesorski i komutacioni) i koji vrši meñusobno povezivanje modula. Na ovaj način je omogućen modularan i skalabilan dizajn rutera, čime je olakšano da operateri koji instaliraju rutere mogu lako da prilagode dotične rutere svojim potrebama i takoñe mogu veoma lako da ih nadograñuju i unapreñuju. 2.1. Tipovi arhitektura rutera Ova teza se bavi paketskim procesiranjem u ruteru, koje se implementira u ravni podataka. Paketsko procesiranje se odnosi na obradu korisničkih paketa u ravni podataka u koje izmeñu ostalog spadaju provera ispravnosti paketa, ispitivanje IP zaglavlja i njegova modifikacija, filtriranje paketa, odbacivanje paketa, rasporeñivanje paketa za slanje i dr. Samo paketsko procesiranje će biti detaljno opisano u sledećem poglavlju. Meñutim, sa stanovišta implementacije paketskog procesiranja neophodno je poznavati arhitekturu rutera. Pod arhitekturom rutera se podrazumeva način na koji se paketi prosleñuju sa ulaznih portova na izlazne. Arhitektura rutera dominantno utiče na performanse i kvalitet rada rutera. Loša arhitektura može dovesti do slučajeva blokade. Pod blokadom se podrazumeva da u slučaju odreñenih saobraćajnih obrazaca doñe do zagušenja u odreñenim delovima rutera i usled toga odbacivanja paketa iako nijedan izlazni port nije preopterećen. Pod pojmom preopterećenja se podrazumeva da zbirni saobraćaj sa svih ulaznih portova namenjen odreñenom izlaznom portu prevazilazi njegov kapacitet. Očigledno je da u slučaju preopterećenja izlaznog porta mora doći do odbacivanja paketa jer izlazni kapacitet dotičnog porta ne može da opsluži sve pakete. Meñutim, neke arhitekture rutera mogu biti blokirajuće čime i u regularnim uslovima kada nijedan izlazni port rutera nije preopterećen ipak dolazi do odbacivanja. Takoñe, veoma je važno da arhitektura rutera bude skalabilna tako da podržava širok raspon broja portova. U suprotnom, ako arhitektura nije skalabilna to predstavlja potencijalni problem za operatera koji bi koristio takve rutere jer bi bio ograničen u proširenju broja portova na takvim ruterima, što bi značilo da bi morali da se koriste dodatni ruteri na lokacijama koje se trebaju proširiti dodatnim portovima što predstavlja skupo i komplikovano rešenje. 8 Deo u ruteru koji fizički vrši komutaciju paketa sa ulaznih na izlazne portove se naziva paketski svič. Arhitektura rutera je definisana načinom rada paketskog sviča. Predloženo je i razvijeno nekoliko realizacija paketskog sviča [7]: • paketski svičevi sa baferima na izlazu [12]-[15] • paketski svičevi sa zajedničkim baferom [16]-[18] • paketski svičevi sa baferima na ulazu [1]-[2], [19]-[24] • Birkhoff-Von Neumann paketski svičevi [25]-[26] • torusni paketski svičevi [27] • Klosovi paketski svičevi [28]-[30] Slika 2.1.1. – Paketski svič sa baferima na izlazu Paketski svič sa baferima na izlazu je prikazan na slici 2.1.1. Paket sa ulaznog porta se upisuje u bafer izlaznog porta kome je namenjen. Meñutim, istovremeno može da postoji više ulaznih portova koji šalju pakete ka istom izlazu. Otuda bafer na izlaznom portu mora da bude dovoljno brz tj. da ima dovoljno velik protok da primi sve te pakete. U najgorem slučaju svi ulazni portovi istovremeno šalju paket ka istom izlaznom portu. Otuda bafer na izlaznom portu mora da ima dovoljan protok da bude sposoban da prima pakete sa svih  ulaznih portova istovremeno i da iščitava jedan paket koji se šalje na izlazni link. Očigledno je da protok bafera predstavlja ograničenje u pogledu skalabilnosti ovakvog paketskog sviča, čime ovakvi svičevi nisu pogodni za implementaciju rutera velikih kapaciteta koji sadrže velik broj brzih portova. S druge strane, s obzirom da se svi paketi odmah prosleñuju na izlazni port bez zadrške, veoma je lako implementirati podršku za kvalitet servisa poput rezervacije kapaciteta, klasa 9 prioriteta u prosleñivanju, fer servisa u slučaju preopterećenja, pošto su samo paketi tokova koji izlaze na dati izlazni port u istom baferu. Slika 2.1.2. – Paketski svič sa zajedničkim baferom Paketski svič sa zajedničkim baferom prikazan na slici 2.1.2. pokušava da optimizuje memorijske resurse u odnosu na paketski svič sa baferima na izlazu, a da pri tom zadrži iste osobine kao i paketski svič sa baferima na izlazu. Veličina bafera na izlaznom portu u slučaju paketskog sviča sa baferima na izlazu mora da se dimenzioniše da podrži prijem paketa i u slučaju kratkotrajnih preopterećenja na izlaznom portu. Meñutim, ne mogu istovremeno svi izlazni portovi biti preopterećeni pa samim tim memorijski resursi nisu optimalno korišćeni jer su neki baferi prepunjeni, a neki su samo delimično popunjeni. Samim tim je efikasnije koristiti memorijske resurse kada svi izlazni portovi dele jedan zajednički bafer. Svi ulazni portovi upisuju svoje pakete u zajednički bafer, a izlazni portovi čitaju pakete koje šalju na izlazni link iz istog tog bafera. To znači da protok zajedničkog bafera mora da podrži istovremeni upis paketa sa svih  ulaznih portova, kao i iščitavanje paketa sa svih  izlaznih portova, tj. potreban je čak i veći protok nego u slučaju paketskog sviča sa izlazima jer postoji veći broj čitanja iz bafera zbog činjenice da svi izlazni portovi koriste isti bafer. To znači da i dalje postoji problem sa skalabilnošću. Takoñe, dobre osobine u pogledu podrške za kvalitet servisa važe i za ovu arhitekturu, jer sa stanovišta izlaznih portova ništa nije izmenjeno tj. i dalje su paketi tokova za isti izlazni port izolovani od drugih paketa jer imaju svoj izlaz, a ulazni portovi bez zadrške prosleñuju pakete u zajednički bafer pa su oni odmah na raspolaganju. 10 Slika 2.1.3. – Paketski svič sa baferima na ulazu Paketski svič sa baferima na ulazu prikazan na slici 2.1.3 rešava problem skalabilnosti koji imaju paketski svič sa baferima na izlazu i paketski svič sa zajedničkim baferom. Paketi se čuvaju u baferima na ulaznim portovima pre prosleñivanja ka izlaznim portovima. Sami paketi se prosleñuju ka izlaznom portu kroz komutator koji se naziva krosbar. Radom paketskog sviča sa baferima na ulazu upravlja algoritam rasporeñivanja tj. rasporeñivač. On definiše uparivanja ulaznih portova sa izlaznim portovima tako da ulazni port može da pošalje paket kroz krosbar ka izlaznom portu sa kojim je uparen. Krosbar i rasporeñivač je lakše implementirati kada su paketi fiksne dužine [7]. Kod unikast krosbarova, svaki ulaz može biti povezan sa najviše jednim izlazom, i svaki izlaz može biti povezan sa najviše jednim ulazom. Pošto su IP paketi promenljive dužine, onda se na ulaznim portovima vrši segmentacija paketa na jedinice fiksne dužine koje se nazivaju ćelije, pa se zatim ćelije rasporeñuju za slanje kroz krosbar, te se prema izračunatom rasporedu ćelije i prosleñuju kroz krosbar. Poznati algoritmi rasporeñivanja su PIM (Parallel Iterative Matching) [19], iSLIP [20] i SGS (Sequential Greedy Scheduler) [22]-[24]. Protok bafera više ne ograničava protok rutera, jer baferi moraju da podrže samo istovremeni upis jedne ćelije i čitanje jedne ćelije. Otuda protok bafera ne zavisi od broja portova rutera, pa je ruter zasnovan na paketskom sviču sa baferima na ulazu skalabilniji od prethodne dve arhitekture. Meñutim, pošto paketi svih tokova namenjenih istom izlaznom portu nisu odmah 11 prisutni na izlaznom portu već se nalaze u baferima na ulaznim portovima, podrška kvalitetu servisa je znatno komplikovanija jer su paketi smešteni u različitim baferima. Naime, paketi se bore za resurse i sa paketima koji dolaze na isti ulaz, i sa paketima koji idu na isti izlaz. To je ujedno najveća mana paketskih svičeva sa baferima na ulazu. Sva tri navedena paketska sviča (sa baferima na izlazu, sa zajednički baferom, sa baferima na ulazu) spadaju u tzv. jednostepene paketske svičeve jer se fizički prenos paketa sa ulaznog porta na izlazni port vrši u jednom koraku. Paketski svičevi sa baferima na ulazu se smatraju najboljom jednostepenom arhitekturom jer podržavaju najveće kapacitete komutiranja [7]. Slika 2.1.4. – Birkhoff-von Neumann paketski svič BN (Birkhoff-von Neumann) paketski svič je prikazan na slici 2.1.4. BN paketski svič koristi TDM (Time Division Multiplex) svič na ulazu i na izlazu. Zbog upotrebe TDM svičeva, na ulaznom portu se vrši segmentacija IP paketa na ćelije fiksne dužine. Kroz TDM svič na ulazu, ulazni portovi prosleñuju ćelije u memoriju (bafer) koja je podeljena na banke da bi se omogućio istovremeni upis više ćelija. Ulazni TDM svičevi omogućuju svakom ulaznom portu u svakom slotu pristup jednoj banci za upis ćelije, pri čemu svaki ulazni port u istom slotu pristupa različitoj banci. Kroz  slotova ulazni port će pristupiti svim bankama. Izlazni portovi odlučuju kad će da šalju neki paket na izlazni link i tada preko TDM sviča na izlazu čitaju ćelije dotičnog paketa. Isto kao i kod ulaznih TDM svičeva, izlazni TDM svičevi omogućuju svakom izlaznom portu u svakom slotu pristup jednoj banci za čitanje ćelije, pri čemu svaki izlazni port u istom 12 slotu pristupa različitoj banci. Kroz  slotova izlazni port će pristupiti svim bankama. Ideja BN sviča je da TDM svič na ulazu rasporedi ćelije svakog paketa ravnomerno po bankama, tako da izlaz putem izlaznog TDM sviča kojim pristupa svaki put drugoj banci uvek ima ćelije za čitanje i time neprestano prosleñuje pakete na izlazni link (dok ih naravno ima na raspolaganju za prosleñivanje). Meñutim, veoma lako može da se konstruiše slučaj gde se sve ćelije sa svih ulaznih portova namenjene istom izlazu rasporede u istu banku, čime protok tog izlaznog porta drastično opada (preciznije  puta) jer izlazni port pristupa istoj banci tek u svakom -tom slotu izlaznog TDM sviča. Ovo predstavlja ozbiljnu manu BN svičeva. Slika 2.1.5. – Torusni paketski svič Torusni paketski svičevi se baziraju na strukturi torusa kao što je prikazano na slici 2.1.5. Ideja je da svaka tačka u torusu predstavlja mali ruter koji ima šest internih portova i jedan eksterni port. Interni portovi omogućavaju konekciju sa susednih šest malih rutera kao što je prikazano na slici 2.1.5, a eksterni port predstavlja ulazno/izlazni port preko koga se ruter povezuje sa eksternom mrežom (Internetom). Na slici 2.1.5. eksterni portovi su prikazani sa debljim linijama, a konekcije izmeñu internih portova 13 tanjim linijama. Kada paket doñe preko eksternog porta u ruter, odreñuje se pozicija izlaznog porta u torusu i unapred se definiše putanja kojom paket mora ići kroz torus do dotičnog izlaznog porta. Kroz torusni paketski svič se prosleñuju jedinice fiksne dužine tzv. flitovi, pa je po ulazu IP paketa neophodno izvršiti njegovu segmentaciju na flitove. Za svaki par ulazni/izlazni port postoji više potencijalnih putanja kroz torus pa se često radi balansiranje saobraćaja po putanjama da bi se izbeglo potencijalno zagušenje putanja u torusu. U istu svrhu se nekad koristi i tehnika adaptivnog rutiranja koje se prilagoñava trenutnom stanju saobraćaja u torusu, ali ono komplikuje implementaciju. U svakom slučaju, mogu se konstruisati slučajevi gde dolazi do zagušenja pojedinih deonica u torusu iako nijedan od izlaznih portova nije preopterećen. Zagušenje se u tim slučajevima može izbeći samo ako se značajno podignu kapaciteti svih deonica u torusu što je tehnički nepraktično, jer su u slučajevima velikog broja ulaznih/izlaznih portova kapaciteti potrebni za izbegavanje zagušenja preveliki. Takoñe, problem je što u slučaju velikih torusa tj. torusa sa velikim brojem malih rutera, kašnjenje za neke parove ulazni/izlazni port može biti veoma veliko usled velikog broja deonica u torusu kroz koje paket mora proći. S druge strane, veoma dobro svojstvo rutera baziranih na torusnom paketskom sviču je velika skalabilnost i jednostavna proširivost, pošto je potrebno samo dodati mali ruter u torus kada se želi dodati novi port. U opštem slučaju je potrebno više koraka da paket sa ulaznog porta stigne na odgovarajući izlazni port, pa torusni paketski svič spada u višestepene paketske svičeve. Slika 2.1.6. – Klosov paketski svič Klosovi (eng. Clos) paketski svičevi se zasnivaju na trostepenoj strukturi. Klosova struktura podrazumeva da svaki komutacioni element bude povezan jednom 14 linijom sa svakim od komutacionih elemenata iz sledećeg nivoa (stepena). Klosov paketski svič je prikazan na slici 2.1.6. Ukupan broj ulaznih, odnosno izlaznih portova je  · , gde je  broj komutacionih elemenata u prvom nivou, odnosno trećem nivou, a  broj ulaza u jedan komutacioni element prvog nivoa, odnosno broj izlaza iz jednog komutacionog elementa trećeg nivoa. Ideja je da se koristi neblokirajuća Klosova struktura za postizanje neblokirajućeg paketskog sviča velikog kapaciteta. Naravno postoji razlika u odnosu na principe komutacije kola gde je originalno primenjena Klosova struktura. U komutaciji kola se za uspostavu veze nekog ulaza i izlaza, zauzimao put kroz Klosovu strukturu i ti resursi su bili zauzeti dok veza traje, nezavisno od trajanja drugih veza. Meñutim, u Klosovoj strukturi sa komutacijom paketa resursi se zauzimaju u trajanju vremenskih slotova jednake dužine. U suprotnom, komutacija paketa promenljive dužine bi komplikovala konfiguraciju i upravljanje Klosovim paketskim svičem. Otuda se i ovde paketi na ulazu u ruter segmentiraju na ćelije fiksne dužine. U svakom slotu se vrši rekonfigurcija komutacionih elemenata Klosove strukture. Pokazano je da je Klosov paketski svič neblokirajući ako se primeni adekvatno balansiranje saobraćaja [28]. Broj komutacionih elemenata srednjeg nivoa  mora da zadovolji nejednačinu    da bi Klosov paketski svič bio neblokirajući. Klosov paketski svič se koristi u slučaju kad je potrebno ostvariti najveće kapacitete paketskog sviča sa velikim brojem portova. U ovoj tezi će biti korišćena jednostepena arhitektura jer je njena izrada ekonomičnija. Pri tome će biti korišćena arhitektura bazirana na paketskom sviču sa baferima na ulazu jer je ta arhitektura skalabilna i omogućava ostvarivanje velikih kapaciteta, odnosno podršku velikog broja portova. Za upravljanje radom paketskog sviča koristiće se SGS algoritam rasporeñivanja zbog njegovih naprednih karakteristika i dokazane osobine neblokiranja [22]-[24]. 15 3. FPGA IMPLEMENTACIJA PAKETSKIH PROCESORA Kao što je istaknuto u uvodnom delu ove teze, Internet danas praktično spada u elementarna prava pojedinca u razvijenim društvima. Internet je nezamenjiv segment u svim aspektima današnjeg života, poslovnom, socijalnom, zabavnom, informativnom itd. Otuda dolazi do neprestanog razvoja novih servisa, pri čemu mnogi od njih imaju veoma striktne zahteve po pitanju kvaliteta servisa što zahteva značajne resurse Internet mreže. Usled razvoja novih zahtevnih servisa nastaje potreba da se kapaciteti infrastrukture Interneta unapreñuju u cilju obezbeñivanja podrške novim servisima. Unapreñenje kapaciteta se postiže povećanjem kapaciteta linkova kao i instalacijom novih linkova i rutera. Meñutim, povećanje kapaciteta linkova dovodi do većeg opterećenja rutera koji sada moraju da obrañuju veće količine informacija u jedinici vremena da bi izvršili svoju osnovnu namenu – prosleñivanje informacija (IP paketa) ka krajnjem korisniku. Takoñe, i multikast servisi postaju sve prisutniji. Kod multikast servisa, ruter mora da saobraćaj sa jednog svog ulaza distribuira na više svojih izlaza. To dovodi do potencijalnih problema zagušenja u ruteru ako arhitektura rutera nije prilagoñena multikast saobraćaju, već samo unikast saobraćaju. Otuda arhitektura rutera mora da pruži kvalitetnu podršku multikast saobraćaju da ne bi dolazilo do zagušenja rutera i pada njegovih performansi [31]-[32]. U okviru projekta ‘Sistemska integracija Internet rutera’ podržanog od strane Ministarstva nauke i tehnološkog razvoja Srbije je razvijen Internet ruter u okviru kojega su implementirana napredna rešenja koja ispunjavaju zahteve modernih rutera velikih kapaciteta [5]-[6]. Jedan od delova projekta je bio implementacija i analiza funkcija paketskog procesora, i rezultati rada na tom delu projekta su prezentovani u okviru ove teze. Realizovani paketski procesori uz krosbar čine osnovu ravni podataka samog rutera. Za implementaciju ravni podataka su korišćeni FPGA čipovi umesto ASIC (Application-Specific Integrated Circuit) čipova. ASIC čipovi iako tipično daju bolje performanse i optimalnu implementaciju, nisu fleksibilni i potencijalne 16 modifikacije implementacije zahtevaju novi ASIC čip. Otuda ASIC čipovi nisu pogodni sa istraživačkog stanovišta gde je cilj implementirati raznovrsne algoritme i uporeñivati njihove performanse. S druge strane FPGA čipovi nude visok stepen fleksibilnosti čime je moguće bez promene čipa vršiti promene dizajna implementacije i testirati raznovrsna rešenja. Krajnji cilj rada na projektovanju i integrisanju Internet rutera je razvoj komercijalnog proizvoda. Meñutim, pored komercijalnog aspekta, postoje i veoma značajni edukativni i istraživački aspekt. S jedne strane implementacija rutera omogućava studentima lakše razumevanje unutrašnje arhitekture rutera i njenog funkcionisanja. Takoñe, studenti mogu da implementiraju delove rutera i testiraju ih u razvijenom prototipu čime stiču i praktična znanja. Sličan edukativni cilj imaju NetFPGA platforme [33]-[34]. U okviru NetFPGA projekta realizovana je otvorena platforma koja sadrži FPGA čip na kome se mogu implementirati raznovrsne mrežne funkcije i algoritmi, pri čemu se oni mogu testirati, kao i u našem slučaju, u realnom okruženju. Prednost našeg rešenja proističe iz činjenice da naš prototip sadrži krosbar za razliku od NetFPGA čime je omogućeno testiranje svih funkcija rutera sa ulaznim baferima. Pored edukativnog, značajni su i istraživački potencijali našeg prototipa. S obzirom da komercijalni ruteri nisu otvoreni, naročito na nivou hardverske ravni podataka, nemoguće je u okviru njih implementirati nova napredna rešenja i testirati ih. To značajno otežava razvoj novih algoritama i rešenja jer je teško izvršiti njihovo testiranje u realnim uslovima. Otuda naš razvijeni ruter dobija i na istraživačkom značaju, jer postavlja osnove u okviru kojih se nova rešenja lako dodaju i testiraju u realnom okruženju. Nova rešenja mogu da se dodaju kako u ravni podataka, tako i u kontrolnoj ravni. U ravni podataka je to omogućeno upotrebom FPGA čipova, a u kontrolnoj ravni korišćenjem otvorenog softvera koji se može modifikovati i unapreñivati. Razvoj ravni podataka je prvi doprinos ove teze i on postavlja osnovu rutera, razvijenog u okviru projekta ‘Sistemska integracija Internet rutera’, koja omogućava prethodno navedene aspekte. U ovom poglavlju biće prezentovana implementacija funkcija paketskog procesiranja koje uz krosbar čine kompletnu ravan podataka. Najpre će biti objašnjena arhitektura samog rutera i njegovo funkcionisanje da bi se bolje shvatila pozicija paketskog procesora u okviru rutera. Biće izložena opšta arhitektura paketskog 17 procesora, a zatim će biti objašnjeni i pojedini delovi paketskog procesora pri čemu će biti data i analiza njihove skalabilnosti. Na kraju će biti izloženi tehnički podaci o hardverskoj implementaciji i iskorišćenim resursima. 3.1. Arhitektura prototipa rutera Ruteri velikih kapaciteta moraju imati modularnu strukturu da bi bili ekonomski isplativi kako proizvoñaču tako i korisniku. Modularnom strukturom se omogućava bolja skalabilnost i veći kapacitet rutera, ali isto tako i fleksibilnost u pogledu konfiguracije koja bi zadovoljila specifične potrebe korisnika. Osnovni moduli rutera su linijski modul, procesorski modul i krosbar (komutacioni modul). Linijski moduli su najbrojniji i oni povezuju ruter sa njegovom okolinom (drugim ruterima i korisničkim mrežama), a njihova primarna funkcija je paketsko procesiranje. Tipično, proizvoñači nude veći broj različitih linijskih modula radi mogućnosti povezivanja rutera na različite tipove mreže, kao što su eternet, POS (Packet Over SDH) i drugi. Na ovaj način korisnik može konfigurisati ruter prema svojim potrebama birajući one linijske module koji mu omogućavaju konekciju sa mrežama sa kojima ruter treba da se poveže. Procesorski modul koncentriše u sebi funkcije kontrolne ravni. On implementira protokole rutiranja, kao što su OSPF (Open Shortest Path First), BGP (Border Gateway Protocol), RIP (Routing Information Protocol), menadžment protokole kao što je SNMP (Simple Network Management Protocol), a omogućava i administraciju tj. konfigurisanje rutera od strane administratora mreže. Krosbar predstavlja komutator koji vrši prosleñivanje paketa sa ulaznih na odgovarajuće izlazne portove rutera. Prototip Internet rutera koga smo razvili sadrži pomenuta tri modula – procesorski modul, krosbar modul i linijski modul. Ova tri modula su rasporeñena na dve štampane ploče. Na jednoj štampanoj ploči je procesorski modul. Jedan od učesnika na projektu je bio i Institut Iritel. Otuda je štampana ploča na kojoj je smešten procesorski modul standardna procesorska ploča koju Iritel koristi u svojim SDH (Synchronous Digital Hierarchy) sistemima. Pri tome je softverski deo ploče prilagoñen funkcionalnostima Internet rutera i implementira protokole kontrolne ravni. Druga štampana ploča je razvijena u okviru projekta i sadrži krosbar modul i linijski modul. Ova varijanta je adekvatna za prvu verziju prototipa rutera jer je ekonomičnija, a sa stanovišta testiranja funkcionalnosti nema značajnih razlika. U budućim verzijama 18 prototip rutera će sadržati ova dva modula na odvojenim štampanim pločama, a takoñe će biti i više linijskih modula radi ostvarivanja i testiranja većih kapaciteta. Obe štampane ploče se postavljaju u standardni rek koji se koristi u Iritelovim SDH sistemima, i povezane su bekplejnom. U okviru linijskog modula vrše se funkcije paketskog procesiranja u koje spadaju: detekcija eternet okvira na ulaznom portu, provera ispravnosti eternet okvira, filtriranje eternet okvira po MAC adresi i enkapsuliranom protokolu, provera ispravnosti IP zaglavlja, modifikacija IP zaglavlja, lukap, segmentacija IP paketa na ćelije fiksne dužine, rasporeñivanje ćelija za slanje kroz krosbar, baferisanje ćelija, rekonstrukcija IP paketa na izlaznom portu, formiranje i slanje eternet okvira. Krosbar vrši prosleñivanje ćelija sa ulaznih na odgovarajuće izlazne portove. U okviru procesorskog modula se vrše funkcije kontrolne ravni i kontroliše se rad ravni podataka (npr. u lukap tabelu na ravni podataka prosleñuje nove podatke u slučaju promena u topologiji mreže). Otuda se svi kontrolni paketi (npr. OSPF paketi) namenjeni ruteru prosleñuju direktno sa ulaznih portova na linijskom modulu ka procesorskom modulu koristeći procesorski interfejs. Na isti način kontrolna ravan šalje svoje generisane kontrolne pakete u mrežu. Ona preko procesorskog interfejsa prosleñuje svoje kontrolne pakete ka odgovarajućem izlaznom portu linijskog modula koji ih zatim šalje na izlazni link tj. u mrežu. Uprošćena blok-shema razvijenog prototipa rutera je prikazana na slici 3.1.1. Slika 3.1.1. – Struktura prototipa rutera razvijenog u okviru projekta ‘Sistemska integracija Internet rutera’ 19 Procesorski modul je sa hardverskog stanovišta identičan već postojećoj procesorskoj ploči koju koristi Iritel u svojim sistemima, a razlika je samo sa softverskog stanovišta, pošto je on prilagoñen funkcijama Internet rutera. Konekcija sa linijskim i krosbar modulom je ostvarena procesorskim interfejsom, koji omogućava procesoru, upis i čitanje 32-bitnih podataka ka periferiji, odnosno linijskom i krosbar modulu. Na procesorskom modulu se nalazi PowerQUICC II procesor. Slika 3.1.2. – Procesorski interfejs Procesorski interfejs je prikazan na slici 3.1.2. On se sastoji od 32-bitne magistrale podataka, 26-bitne adresne magistrale, kontrolnih signala za selektovanje čipova, kontrolnih signala za aktiviranje upisa i čitanja i prekidne linije za izazivanje prekida u procesoru. Postoje tri kontrolna signala za selektovanje čipova u zavisnosti od karakteristika čipa (CS8, CS16, CS32) tj. tipa podataka koje podržava: 8-bitne, 16-bitne ili 32-bitne. Implementirani linijski i krosbar moduli podržavaju 32-bitni prenos. Ukoliko procesor upisuje podatak tada se aktiviraju kontrolni signali (WE1-WE4) za upis koji predstavljaju četiri signala za omogućavanje upisa – svaki za po jedan bajt 32- bitnog podatka na magistrali podataka. U slučaju čitanja, aktivira se kontrolni signal (OE) koji aktivira trostatičke bafere kojima se omogućava adresiranom modulu da izbaci tražene podatke na magistralu podataka ka procesoru na procesorskom modulu. Da bi se omogućilo krosbar modulu ili linijskom modulu signaliziranje nekog važnog dogañaja procesorskom modulu, koristi se prekidna linija čijom aktivacijom se izaziva pokretanje prekidne rutine u radu procesora. Pošto procesor pristupa većem broju modula tj. čipova, adresni prostor je podeljen po modulima. Otuda su u modulima kreirani adresni dekoderi koji prepoznaju da li ih je procesor adresirao ili ne. Ukoliko su adresirani onda znaju da procesor želi da ostvari komunikaciju sa njima. Takoñe, na 20 procesorskom modulu je omogućena i funkcija udaljenog pristupa, pa tako administrator rutera može dinamički pristupati ruteru u cilju podešavanja ili modifikovanja konfiguracije rutera ili očitavanja statusa rutera. Ovakav način pristupa je realizovan preko eternet porta na procesorskom modulu. Na slici 3.1.3 je prikazana blok-shema štampane ploče koja sadrži linijski i krosbar modul. Ona sadrži tri FPGA čipa (Xilinx Virtex5 LX110T čipovi [35]). Jedan FPGA čip se koristi za implementaciju krosbar modula, dok se druga dva koriste za implementaciju paketskih procesora u okviru linijskog modula. Pri tome svaki FPGA čip linijskog modula sadrži po četiri paketska procesora. Dobra osobina korišćenih FPGA čipova je što imaju četiri ugrañena eternet bloka čime je značajno olakšana implementacija funkcija paketskog procesiranja drugog sloja OSI modela. Svaki FPGA čip linijskog modula je povezan sa jednom SRAM (Static Random Access Memory) memorijom (Cypress SRAM konfiguracije 512Kx32b [36]) i jednom DDR2 SDRAM (Double Data Rate Synchronous Dynamic Random Access Memory) memorijom (Micron SODIMM 1GB DDR2-800 [37]). SRAM memorija sadrži lukap tabelu koja se koristi u okviru lukapa za odreñivanje izlaznog porta na koji treba usmeriti IP paket. DDR2 SDRAM memorija se koristi za baferisanje ćelija. Obe ove memorije koriste tj. dele sva četiri paketska procesora smeštena na istom FPGA čipu. Svi paketski procesori su povezani preko krosbara, tj. preko krosbara se prosleñuju ćelije sa ulaznih portova na odgovarajuće izlazne portove. Za povezivanje paketskih procesora i krosbara se koriste multigigabitski linkovi pošto su neophodne velike brzine prenosa ćelija izmeñu paketskih procesora i krosbara. I linijski i krosbar modul, odnosno FPGA čipovi u okviru kojih su oni implementirani, su povezani sa procesorskim modulom preko procesorskog interfejsa. Pošto je sistem digitalan neophodni su izvori takta tj. oscilatori da bi linijski modul i krosbar mogli ispravno funkcionisati. Na FPGA čipove koji implementiraju funkcije paketskog procesora su povezani oscilatori frekvencija 100MHz i 125MHz na osnovu kojih se generišu svi taktovi neophodni za ispravan rad ravni podataka. Oscilator od 100MHz se koristi za formiranje takta od 200MHz koji se koristi na fizičkom interfejsu ka DDR2 SDRAM memoriji. Oscilator od 125MHz se koristi za formiranje taktova od 125MHz koji se koriste u celokupnom paketskom procesoru izuzimajući već pomenuti fizički interfejs ka DDR2 SDRAM memoriji. 21 Paketski procesori 1..4 Paketski procesori 5..8 Krosbar Multigigabitski linkovi 4 4 Gigabitski eternet portovi 1..4 OSC 100Mhz OSC 125Mhz OSC 100Mhz OSC 125Mhz DDR2 DDR2 SRAMSRAM Procesorski interfejs Gigabitski eternet portovi 5..8 Multigigabitski linkovi Slika 3.1.3. – Blok-shema štampane ploče koja sadrži linijski i krosbar modul 3.2. Implementacija paketskog procesora Ovo potpoglavlje sadrži opis implementacije paketskog procesora u linijskom modulu prototipa rutera koga smo razvili. Radi povećanja fleksibilnosti i modularnosti implementacije korišćen je FPGA čip. Na ovaj način je omogućeno jednostavno menjanje dizajna implementacije i probanje različitih rešenja tokom razvoja funkcija paketskog procesora. Isto tako FPGA implementacija omogućava jednostavno dodavanje novih funkcija paketskog procesiranja u slučaju potrebe. Unutar ovog potpoglavlja će biti prezentovana arhitektura implementiranog paketskog procesora i biće dat pregled osnovnih funkcionalnosti koje paketski procesor treba da podrži. Nakon toga će u narednim odeljcima biti dat opis pojedinih delova paketskog procesora, pri čemu će biti izvršena analiza njihove skalabilnosti, odnosno mogućnosti da podrže povećanje kapaciteta linkova i broja portova rutera. Osnovni zadatak ravni podataka je da prosledi (komutira) pakete sa ulaznih portova na odgovarajuće izlazne portove. Paketsko procesiranje se izvršava u okviru linijskih modula rutera i uključuje obradu paketa na fizičkom sloju, sloju linka podataka i mrežnom sloju, odnosno na prva tri sloja OSI modela. Na slici 3.2.1 je prikazana blok- shema implementacije paketskog procesora, pri čemu se na jedan FPGA čip smeštaju četiri paketska procesora koji odgovaraju gigabitskim eternet portovima. Fizički sloj se 22 tipično implementira primenom specijalizovanih čipova prilagoñenih radu sa tehnologijom odgovarajuće mreže. Kao što se vidi sa slike 3.2.1 u ovoj implementaciji su korišćeni SFP (Small Form-factor Pluggable Transceiver) moduli koji vrše funkcije fizičkog sloja gigabitskog eterneta [38]. Takoñe, sa slike 3.2.1 se može videti da se funkcije sloja linka podataka i mrežnog sloja vrše u okviru FPGA čipa. Slika 3.2.1. – Blok-shema implementiranog paketskog procesora Primljeni eternet okviri se obrañuju u okviru ulaznog modula sloja linka. Ulazni modul sloja linka detektuje okvire, proverava njihovu ispravnost, vrši filtriranje okvira na osnovu odredišne MAC adrese i enkapsuliranog protokola i izdvaja IP pakete iz okvira. Izdvojeni korisnički IP paketi se prosleñuju ulaznom mrežnom modulu. Kontrolni okviri i paketi se prosleñuju procesorskom modulu na obradu. Mrežni sloj, za razliku od prva dva sloja, je tehnološki nezavisan što je uostalom i omogućilo razvoj i globalizaciju Interneta. Implementacija mrežnog sloja rutera u najvećoj meri utiče na njegove performanse, pa ona unosi najveći stepen slobode prilikom izgradnje rutera, odnosno njegove ravni podataka. Kao što se može videti sa slike 3.2.1 u implementaciju mrežnog sloja spadaju blokovi: ulazni mrežni modul, lukap modul, SGS rasporeñivač, DDR2 kontroler, SERDES modul i izlazni mrežni modul. Ulazni mrežni modul prihavata IP pakete od ulaznog modula sloja linka i obavlja sledeće funkcije: provera ispravnosti IP zaglavlja, ažuriranje TTL (Time To Live) polja i polja za proveru ispravnosti u IP zaglavlju, prosleñivanje odredišne IP adrese lukap modulu, segmentacija IP paketa u ćelije fiksne dužine, prosleñivanje ćelija SGS rasporeñivaču zajedno sa informacijom kom izlaznom portu su ćelije namenjene. 23 Lukap modul izvršava lukap, odnosno vrši pretragu lukap tabele da bi odredio izlazni port na koji treba usmeriti IP paket sa odredišnom IP adresom za koju se vrši pretraga. Lukap tabela je smeštena u eksternu SRAM memoriju. Lukap modul koriste sva četiri porta tj. paketska procesora. Konačni rezultat lukapa se vraća ulaznom mrežnom modulu koji tu informaciju zajedno sa ćelijama odgovarajućeg paketa prosleñuje SGS rasporeñivaču. Rasporeñivač vrši rasporeñivanje ćelija za slanje ka odgovarajućim izlaznim portovima preko krosbara, pri čemu se ćelije smeštaju u ulazni bafer dok čekaju na svoj red za slanje. Rasporeñivanje zavisi od arhitekture rutera. U našem slučaju, korišćena je arhitektura rutera sa baferima na ulazu jer ona omogućava najveću skalabilnost u slučaju jednostepenih rutera [7]. Pri tome je korišćen sekvencijalni pohlepni rasporeñivač (SGS – Sequential Greedy Scheduler) za koji je matematički dokazano da je neblokirajući kad se koristi ubrzanje   2. Ubrzanje je koeficijent povećanja brzine internih linkova (koji spajaju paketske procesore sa krosbarom) u odnosu na eksterne linkove rutera (linkovi koji spajaju ruter sa mrežom) [7], [22]. Zbog toga SGS rasporeñivač omogućava podršku za garanciju protoka i kašnjenja kroz ruter što je od velikog značaja u modernim ruterima s obzirom na povećanje udela saobraćaja koji ima striktne zahteve u pogledu kvaliteta servisa poput multimedijalnih aplikacija. Rasporeñivač prima ćelije i informaciju ka kojem izlaznom portu treba proslediti paket, odnosno njegove ćelije, od ulaznog mrežnog modula. Rasporeñivač vrši proračun redosleda slanja ćelija. Ćelije se smeštaju u ulazni bafer dok čekaju na svoj red za slanje ka odgovarajućem izlaznom portu preko krosbara. Ulazni bafer je smešten u DDR2 SDRAM memoriju koja ima veliki kapacitet i time mogućnost smeštanja velikog broja ćelija. DDR2 kontroler obezbeñuje pristup DDR2 SDRAM memoriji, odnosno obezbeñuje operacije upisa i čitanja. Pri tome sva četiri paketska procesora koriste, odnosno dele istu DDR2 SDRAM memoriju za svoje ulazne bafere. Paketski procesori se povezuju preko krosbara koji vrši komutaciju ćelija sa ulaznih na odgovarajuće izlazne portove. Za ostvarivanje velikih brzina multigigabitskih linkova koristi se diferencijalni serijski prenos koji omogućava visoke protoke [39]. Otuda se u paketskim procesorima koriste SERDES (SERializer/DESerializer) blokovi koji vrše konverziju paralelnog prenosa ćelija u serijski prenos prilikom slanja, odnosno 24 obrnutu konverziju prilikom prijema ćelija u komunikaciji sa krosbarom. SERDES modul primljene ćelije prosleñuje izlaznom mrežnom modulu. Na izlaznom portu se u okviru izlaznog mrežnog modula ćelije prikupljaju i smeštaju privremeno u izlazni bafer dok se ne prikupe sve ćelije jednog paketa. Kompletirani paketi (paketi čije su sve ćelije stigle na izlazni port) se u izlaznom mrežnom modulu rekonstruišu iz primljenih ćelija u originalne IP pakete koji se prosleñuju drugom sloju tj. izlaznom modulu sloja linka. Izlazni baferi sva četiri paketska procesora su kao i ulazni baferi smešteni u istu DDR2 SDRAM memoriju. U izlaznom modulu sloja linka IP paketi se enkapsuliraju u okvire koji se prosleñuju SFP modulu za slanje na izlazni link. Pošto je neophodna komunikacija sa kontrolnom ravni, odnosno procesorskim modulom implementiran je interfejs ka procesorskom modulu preko koga se razmenjuju informacije i podaci sa procesorskim modulom. Tako se kontrolni paketi namenjeni procesorskom modulu prosleñuju preko ovog interfejsa procesorskom modulu kao što su ARP (Address Resolution Protocol) zahtevi, OSPF paketi itd. U suprotnom smeru, procesorski modul šalje svoje kontrolne pakete u mrežu. Time je omogućen ispravan rad kontrolne ravni, odnosno komunikacija rutera u mreži. Npr. razmena OSPF paketa omogućava uspostavljanje susedstva sa drugim OSPF ruterima u mreži. Preko ovog interfejsa, procesorski modul može da ažurira lukap tabelu u slučaju promena topologije mreže. U okviru ažuriranja lukap tabele procesorski modul vrši brisanje postojećih prefiksa onih mreža koje ruteru više nisu dostupne i dodavanje novih prefiksa onih mreža koje su ruteru postale dostupne. Takoñe u slučaju kada nekoj mreži postane povoljnije pristupiti preko nekog drugog izlaznog porta vrši se modifikacija izlaznog porta pridruženog odgovarajućem mrežnom prefiksu u lukap tabeli. Sve navedene promene u lukap tabeli se izvršavaju tako što procesorski modul šalje parove adresa- podatak lukap modulu preko interfejsa ka procesorskom modulu. Adresa označava lokaciju u SRAM memoriji na koju treba upisati dati podatak. Pored toga procesorski modul može slati komande za aktivaciju i deaktivaciju porta. Kad je port deaktiviran, ne šalju se i ne primaju se eternet okviri. Nakon ovog opisa generalnog rada implementacije paketskog procesora u sledećim odeljcima će biti opisani delovi paketskog procesora. Pri tome će biti data i 25 analiza funkcija koje predstavljaju potencijalno usko grlo, odnosno mogu da ograniče povećanje broja portova i povećanje kapaciteta tj. brzina portova. 3.2.1. Ulazni modul sloja linka Sloj linka podataka je implementiran koristeći ugrañeni MAC (Media Access Control) blok u okviru korišćenog FPGA čipa (Xilinx Virtex5 LX110T). Postoje ukupno četiri ugrañena MAC bloka, tako da svaki od četiri paketska procesora na FPGA čipu koristi po jedan. Ugrañeni MAC blok vrši funkcije MAC podsloja. U prijemnom (ulaznom) smeru u te funkcije spadaju odreñivanje početka okvira, odstranjivanje preambule i SFD (Start Frame Delimiter) polja iz okvira, provera ispravnosti okvira u prijemnom smeru, filtriranje okvira po odredišnoj MAC adresi. Kao rezultat rada ugrañenog MAC bloka u prijemnom smeru dobija se okvir iz koga su odstranjena polja koja ne nose informacije: preambula, SFD polje, FCS (Frame Check Sequence) polje. Ulazni modul sloja linka pored ugrañenog MAC bloka sadrži i blok koji vrši ispitivanje protokola koji je enkapsuliran unutar okvira i filtriranje okvira. U slučaju da protokol koji je enkapsuliran nije prepoznat, okvir se odmah odbacuje. U slučaju da je enkapsuliran IP protokol vrši se filtriranje odredišne IP adrese. Ovo je moguće pošto se unapred zna njena pozicija u eternet okviru. Ako je ova adresa jednaka nekoj od IP adresa u filtru (npr. u pitanju je IP adresa nekog od portova rutera, multikast IP adresa na koju se šalju OSPF ‘Hello’ paketi i sl.), okvir se prosleñuje direktno ka procesorskom modulu preko interfejsa ka procesorskom modulu. U trenutnoj verziji prototipa, procesorski modul je konfigurisan za rad sa eternet okvirima. Otuda se procesorskom modulu moraju prosleñivati eternet okviri koji sadrže kontrolne pakete, a ne izdvojeni kontrolni paketi. Iz tog razloga se u ulaznom modulu sloja linka vrši preusmeravanje takvih eternet okvira ka procesorskom modulu. Naravno, filtriranje odredišne IP adrese i preusmeravanje IP paketa ka procesorskom modulu se može implementirati na nivou mrežnog sloja onog trenutka kada se omogući da procesorski modul prima direktno IP pakete. U slučaju da odredišna IP adresa nije u filtru, IP paket se izdvaja i prosleñuje ulaznom mrežnom modulu kao što je prikazano na slici 3.2.1. U slučaju drugih enkapsuliranih protokola, okviri se usmeravaju ka procesorskom modulu, pošto samo IP paketi treba da prolaze kroz ostatak ravni podataka. Ulazni modul sloja linka ne predstavlja potencijalno usko grlo, pošto ne zavisi od broja portova i obuhvata jednostavne funkcije. 26 3.2.2. Ulazni mrežni modul Slika 3.2.2.1. – Struktura ulaznog mrežnog modula Struktura ulaznog mrežnog modula je prikazana na slici 3.2.2.1 Osnovne funkcije ovog modula su provera ispravnosti IP zaglavlja, modifikacija IP zaglavlja (dekrementiranje TTL polja i usled toga upis nove vrednosti u polje za proveru) i segmentacija IP paketa u ćelije fiksne dužine. Modul je podeljen na dva bloka – blok za procesiranje IP zaglavlja i blok za segmentaciju IP paketa. Blok za procesiranje IP zaglavlja vrši deo funkcija ulaznog modula u kome se vrši ispitivanje i modifikacija IP zaglavlja, dok blok za segmentaciju IP paketa vrši formiranje ćelija fiksne dužine. U bloku za procesiranje IP zaglavlja se IP paket kasni za trajanje zaglavlja, jer se u tom periodu vrši ispitivanje validnosti zaglavlja. Kašnjenje se vrši pomoću memorije za kašnjenje. Ukoliko je IP zaglavlje neispravno, IP paket se odbacuje. Prva provera ispravnosti je verifikacija polja verzije u IP zaglavlju. Pošto je trenutno podržana samo verzija 4 IP protokola, IP zaglavlje je neispravno ukoliko se u polju verzije nalazi bilo koja vrednost različita od 4. Druga provera ispravnosti je provera vrednosti TTL polja. Ukoliko TTL polje ima vrednost 0, IP paketu je isteklo tzv. vreme života i mora se odbaciti da bi se sprečilo njegovo potencijalno kruženje u mreži. Ukoliko TTL polje ima vrednost veću od 0, onda se ta vrednost dekrementira. Poslednja provera ispravnosti IP zaglavlja je provera ispravnosti polja za proveru. Ukoliko proračunata vrednost polja za proveru primljenog IP zaglavlja nije jednaka vrednosti koja se nalazi u polju za proveru IP zaglavlja, IP paket se odbacuje. Paket se odbacuje tako što se sadržaj neispravnog paketa upisanog u memoriju za kašnjenje briše iz nje, dok se ostatak paketa ignoriše. Dok se vrši provera IP zaglavlja, istovremeno se vrši i računanje nove vrednosti polja za proveru zbog izvršenog dekrementiranja TTL polja. Ukoliko je IP 27 zaglavlje ispravno vrši se njegovo čitanje iz memorije za kašnjenje i prosleñivanje ka modulu za modifikaciju polja za proveru. Ovaj modul vrši prosleñivanje IP paketa ka bloku za segmentaciju IP paketa, pri čemu umesto stare vrednosti polja za proveru upisuje novu. Nova vrednost polja za proveru se upisuje tek ovde jer se polje za proveru u IP zaglavlju ne nalazi na njegovom kraju. Takoñe, kada se utvrdi validnost IP zaglavlja, vrši se prosleñivanje odredišne IP adrese lukap modulu koji treba da odredi na koji izlazni port treba usmeriti dotični IP paket. Pored odredišne IP adrese i druga polja IP zaglavlja se mogu izdvojiti na isti način u slučaju potrebe poput izvorišne IP adrese, ToS (Type of Service) polja i drugih. Blok za segmentaciju IP paketa vrši formiranje ćelija fiksne dužine neophodne za efikasan rad SGS algoritma za rasporeñivanje, i time omogućava komutiranje velikih kapaciteta [40]-[41]. Deo za formiranje ćelija prima IP paket i od njega formira ćelije pri čemu svakoj ćeliji dodaje zaglavlje. Zaglavlje ćelije sadrži: identifikaciju izvorišnog porta na kom je ćelija formirana, identifikaciju odredišnog porta na koji ćelija treba da se prosledi, bit indikacije prve ćelije paketa, i bit indikacije poslednje ćelije paketa. Identifikacija izvorišnog porta omogućava izlaznom portu da razlikuje tokove ćelija. Identifikacija odredišnog porta se koristi kao informacija za krosbar da zna na koji port treba da usmeri ćeliju. Na ovaj način je izbegnuto korišćenje posebnih linija ka krosbaru kojima bi se on konfigurisao, a koje bi predstavljale problem u slučaju velikog broja portova jer bi tada broj tih linija bio prevelik pa bi bilo problematično njihovo efikasno provoñenje kroz bekplejn rutera, pošto bi tada krosbar bio na zasebnoj štampanoj ploči. Bitovi indikacije prve i poslednje ćelije IP paketa olakšavaju lakšu detekciju prve i poslednje ćelije paketa na izlaznom portu, a samim tim i lakše odreñivanje ćelija koje pripadaju datom paketu. Pored navedenih polja u zaglavlju ćelije potencijalno mogu da se dodaju i druga polja poput tipa servisa ukoliko je potrebno uvesti podršku za kvalitet servisa. U slučaju omogućavanja kvaliteta servisa, polje tip servisa bi se koristilo u kombinaciji sa identifikacijom izvorišnog porta za razlikovanje tokova po prioritetima za opsluživanje [40]-[41]. U trenutnoj verziji prototipa, tip servisa se ne stavlja u zaglavlje. Zaglavlje je veličine 32 bita da bi se omogućila podrška velikog broja portova, ali i ostavila mogućnost za definisanje dodatnih polja. Veličina same ćelije treba biti pažljivo odabrana. Što je ćelija duža to je iskorišćenost internih linkova veća jer je 28 procenat udela zaglavlja ćelije manji. Takoñe, krosbar ima više vremena za vršenje komutacije tj. periodi izmeñu uzastopnih konfigurisanja krosbara su duži pa je implementacija krosbara lakša. Meñutim, ako su ćelije preduge, postoji opasnost slabog iskorišćenja ćelije u slučaju kratkih IP paketa jer bi samo mali deo ćelije nosio koristan sadržaj. S druge strane, ako su ćelije prekratke, onda je potencijalni problem komutacija takvih ćelija pošto bi vreme za komutaciju moglo biti prekratko za uspešnu implementaciju komutatora. Takoñe bi tada procenat udela zaglavlja ćelije bio prevelik pa bi bila mala iskorišćenost internih linkova koji povezuju paketske procesore i krosbar. Izabrana veličina ćelije je 512b, koja pokušava da balansira navedena dva oprečna zahteva. Pošto se ćelije moraju proslediti SGS rasporeñivaču sa informacijom o izlaznom portu kome su one namenjene, neophodno je sačekati rezultat lukap modula. Otuda se ćelije smeštaju u privremeni bafer. Čim se od lukap modula primi identifikacija izlaznog porta kome su ćelije namenjene vrši se prosleñivanje ćelija ka SGS rasporeñivaču zajedno sa identifikacijom izlaznog porta kome su dotične ćelije namenjene. Sve navedene funkcije nisu kompleksne i ne troše mnogo vremena, a pri tome ne zavise od broja portova ili tokova, pa samim tim ulazni mrežni modul ne predstavlja potencijalno usko grlo u pogledu skalabilnosti rutera. 3.2.3. Lukap modul Lukap jeste odreñivanje izlaznog porta na koji treba usmeriti IP paket na osnovu njegove odredišne IP adrese. Lukap tabela sadrži mrežne adrese i za svaku mrežnu adresu čuva identifikaciju (ID) izlaznog porta na koji treba treba usmeriti IP paket namenjen dotičnoj mreži. Pored mrežnih adresa u lukap tabeli mogu da se nalaze i agregacije mrežnih adresa koje se koriste radi smanjenja broja zapisa u lukap tabelama. Mrežne adrese i agregacije mrežnih adresa se označavaju terminom prefiks. Prilikom pretrage lukap tabele se može naći više prefiksa koji odgovaraju odredišnoj IP adresi za koju se vrši pretraga i tada se mora primeniti LPM (Longest Prefix Matching) pravilo koje odreñuje da se za konačno rešenje uzima prefiks koji ima najduže poklapanje sa odredišnom IP adresom za koju se vrši pretraga. IP lukap mora da se izvrši u vremenu trajanja IP paketa. Otuda sa stanovišta najgoreg slučaja, IP lukap mora da se kompletira u vremenu trajanja najkraćeg IP paketa. S obzirom da trajanje IP paketa opada sa porastom brzine linkova, odnosno portova, očigledno je da kompleksnost lukapa 29 značajno zavisi od brzine porta. Takoñe, kompleksnost lukapa zavisi i od broja zapisa u lukap tabeli, kao i od dužine IP adrese. S obzirom da su IPv4 adrese potrošene, neminovan je prelazak na duže IPv6 adrese. Samim tim adresni prostor koji treba pretražiti je značajno veći pa je i kompleksnost lukapa takoñe veća u slučaju dužih IPv6 adresa. Brzina lukapa se povećava korišćenjem pajplajn tehnike i paralelizacije koje troše značajne hardverske resurse. Otuda je značajno da se lukap algoritam izvršava dovoljno brzo, a da pri tome troši što manje hardverskih resursa. U slučaju gigabitskog eterneta, brzina linka, odnosno porta je  1Gb/s, a dužina najkraćeg okvira je   64B. Lukap za najkraći okvir u tom slučaju mora da se izvrši u okviru / ·   128ns, pri čemu je  broj portova koji dele jedan lukap modul. U našoj implementaciji četiri paketska procesora tj. porta dele jedan lukap modul pa je   4. Vreme od 128ns ne zahteva naročito brz lukap algoritam, te će implementacija takvog algoritma trošiti malo resursa FPGA čipa. U okviru radnog prototipa je implementiran algoritam zasnovan na tehnici m-arnog stabla koji je korišćen u Intelovim mrežnim procesorima [42]-[43]. Lukap počinje pretragom po prefiksima dužim od 15 bita, a u slučaju neuspeha te pretrage vrši se pretraga po prefiksima kraćim od 16 bita. U slučaju pretrage po prefiksima dužim od 15 bita koriste se strajdovi dužine 16-4-4-4-4, a u slučaju pretrage po prefiksima kraćim od 16 bita se koriste strajdovi dužine 8-4-4. Strajd predstavlja broj bita IP adrese koji se razmatra u jednom koraku pretrage. Tako npr. 16-4-4-4-4 označava da se u prvom koraku razmatra prvih 16 bita odredišne IP adrese, pa potom se u svakom sledećem koraku razmatra narednih 4 bita dok se ne iskoriste svi biti odredišne IP adrese ili se pretraga okonča pre toga dolaskom do kraja m-arnog stabla. Svaki korak zahteva jedan pristup lukap tabeli koja je smeštena u eksternoj SRAM memoriji, pa je u najgorem slučaju potrebno osam pristupa eksternoj memoriji. To znači da maksimalno vreme pristupa eksternoj memoriji može da iznosi 128ns/8  16ns, i imajući u vidu da standardne SRAM memorije imaju tipična vremena pristupa 8-10ns očigledno je da implementirani lukap algoritam zadovoljava zahteve u pogledu brzine izvršavanja lukapa u najgorem slučaju (trajanje najkraćeg okvira). 30 Slika 3.2.3.1. – Struktura lukap tabele Struktura lukap tabele je prikazana na slici 3.2.3.1. Dva početna bloka memorije se rezervišu za početne tabele za pretragu po dužim, odnosno kraćim prefiksima. Pretraga po dužim prefiksima počinje od lokacije u početnoj tabeli za pretragu po dužim prefiksima koju odreñuju prvih 16 bita odredišne IP adrese za koju se vrši pretraga. Slično, pretraga po kraćim prefiksima počinje od lokacije u početnoj tabeli za pretragu po kraćim prefiksima koju odreñuju prvih 8 bita odredišne IP adrese za koju se vrši pretraga. Ostatak lukap tabele sadrži blokove koji se sastoje od 16 sukcesivnih memorijskih lokacija. Svaka memorijska lokacija u lukap tabeli predstavlja jedan čvor m-arnog stabla i sadrži dva polja – ID izlaznog porta pridruženog dotičnom čvoru i pokazivač na decu čvora. Pošto se koriste, sem u prvom koraku, strajdovi dužine 4 bita, svaki čvor ima šesnaestoro dece i ona se smeštaju u sukcesivne lokacije tj. u jedan blok pa pokazivač na decu pokazuje na početak bloka tj. na prvo dete. Na ovaj način je značajno redukovan broj pokazivača (umesto 16 koristi se samo 1), čime je značajno smanjena veličina jednog čvora i omogućeno je da veličina memorijske lokacije bude prihvatljiva za implementaciju u eksternoj memoriji, što ne bi bio slučaj da je korišćeno svih 16 pokazivača. Naravno, cena koja se plaća je da se zauzimaju resursi za svu decu iako možda sva deca ne postoje. Lukap modul koji vrši pretragu lukap tabele je veoma jednostavan i sastoji se u kretanju kroz m-arno stablo koje zahteva čitanje odgovarajućih lokacija eksterne SRAM memorije. Smer kretanja zavisi od bita odredišne IP adrese. Pri tome se ispita svaki čvor koji se pročita. Ako je njegov ID izlaznog porta validan, on se pamti kao trenutno 31 najbolje rešenje. Ukoliko je pokazivač validan onda se kreće na sledeći čvor čija adresa ima ofset u odnosu na pokazivač jednak vrednosti sledeća četiri bita odredišne IP adrese za koju se vrši pretraga. Ako pokazivač nije validan onda je pretraga stigla do kraja m- arnog stabla. U slučaju neuspešne pretrage po dužim prefiksima vrši se pretraga po kraćim prefiksima po istom principu kao i po dužim prefiksima. Rezultat pretrage je identifikacija izlaznog porta na koji treba da se usmeri IP paket i ona se prosleñuje ulaznom mrežnom modulu koji je prosleñuje SGS rasporeñivaču zajedno sa ćelijama dotičnog paketa. Ako se uzme u obzir da najveći broj prefiksa za slučaj IPv4 adresa pada u opseg 16-24 bita dužine [44], najveći broj pretraga će sadržati 1-3 pristupa eksternoj SRAM memoriji. Kao što se vidi, implementirani lukap je zadovoljavajući u slučaju gigabitskih portova, pri čemu ga karakteriše mala potrošnja FPGA resursa. Implementirani algoritam nije, meñutim, adekvatan za brze portove i IPv6 adresiranje jer bi u tim slučajevima zahtevao prevelik broj pristupa eksternoj memoriji. Npr. u slučaju da lukap modul mora da podrži četiri 10G eternet porta vreme izvršenja lukapa bi bilo 10 puta kraće nego u slučaju gigabitskih eternet portova tj. svega 12.8ns. To znači da bi bio dozvoljen samo jedan pristup eksternoj memoriji tokom jednog izvršenja lukapa, a taj uslov opisani algoritam ne zadovoljava. Dakle mora se dizajnirati složeniji i brži lukap algoritam, koji će biti opisan u poglavlju 5. Lukap je jedna od najkritičnijih funkcija zbog svoje kompleksnosti, te ograničava brzinu portova. Isto tako lukap se komplikuje sa porastom dužine IP adrese, odnosno sa prelazom na IPv6 adrese koje su četiri puta duže od IPv4 adresa. Kompleksnost lukapa raste sa brojem zapisa u lukap tabeli, i loša organizacija lukap tabele može dovesti do prevelikih memorijskih zahteva koji se ne mogu implementirati. Otuda je neophodan razvoj naprednog lukap algoritma čija će implementacija omogućiti podršku portova velikih brzina kao i velik broj zapisa u lukap tabeli, u slučaju IPv4 i IPv6 adresa. 32 3.2.4. SGS rasporeñivač Slika 3.2.4.1. – Struktura SGS rasporeñivača Arhitektura implementiranog rutera je zasnovana na arhitekturi sa baferima na ulazu. U slučaju ove arhitekture, ćelije IP paketa se smeštaju u bafere na ulaznom portu, a rasporeñivač vrši proračun redosleda slanja ćelija kroz krosbar ka odgovarajućim izlaznim portovima. Algoritam rasporeñivanja definiše način rada rasporeñivača, tj. način proračunavanja redosleda slanja ćelija. Postoji više algoritama rasporeñivanja, a najpoznatiji su PIM [19], iSLIP [20]-[21] i SGS [22]-[24]. Za SGS algoritam je matematički dokazano da komutira saobraćaj bez blokiranja u slučaju kada krosbar ima ubrzanje   2 [22]-[24]. Odnosno, kada nijedan izlazni port nije preopterećen sav saobraćaj prolazi kroz ruter bez gubitaka ukoliko se paketi rasporeñuju prema SGS algoritmu. Zahvaljujući ovoj osobini, SGS obezbeñuje garancije protoka i kašnjenja [22], a takoñe se lako modifikuje da podrži i multikast saobraćaj bez blokiranja [31]- [32]. Ove osobine daju dobru podršku multimedijalnom saobraćaju koji ima sve veće učešće u ukupnom Internet saobraćaju. Iz navedenih razloga SGS je izabran kao algoritam rasporeñivanja i on je korišćen u okviru implementacije paketskog procesora. Kao što je rečeno rasporeñivač odreñuje redosled slanja ćelija ka odgovarajućim izlaznim portovima preko krosbara. Struktura SGS rasporeñivača je prikazana na slici 3.2.4.1. Na svakom ulaznom portu se formiraju tzv. izlazni redovi čekanja koji sadrže ćelije za odgovarajuće izlazne portove. Vektor zahteva je binarni vektor u kome se smešta binarna indikacija koji izlazni redovi za čekanje imaju ćelije za slanje, a koji su prazni. Vektor zahteva se čuva u registru. Ulazni mrežni modul prosleñuje ćelije ka SGS rasporeñivaču zajedno sa identifikacijom izlaznog porta kome su te ćelije namenjene. Po prijemu svake ćelije se utvrñuje kom izlaznom portu je ona namenjena i upisuje se u odgovarajući izlazni red za čekanje koji sadrži ćelije namenjene dotičnom 33 izlaznom portu. Takoñe u slučaju da je dotični izlazni red za čekanje bio prazan vrši se ažuriranje vektora zahteva tako da binarna indikacija, koja odgovara dotičnom izlaznom redu za čekanje, označava da postoje ćelije za slanje u dotičnom izlaznom redu za čekanje. Izlazni redovi za čekanje su smešteni u DDR2 kontroleru i DDR2 SDRAM memoriji i njihova implementacija će biti objašnjena u sledećem odeljku. SGS rasporeñivači svih portova su vezani u lanac. Svaki SGS rasporeñivač dobija od prethodnog SGS rasporeñivača u lancu koji izlazni portovi su slobodni tj. nisu zauzeti od nekog od prethodnih SGS rasporeñivača u lancu. Informacija o slobodnim izlaznim portovima se dobija u vidu vektora slobodnih izlaza koji u binarnom vidu daje informaciju o zauzetim i slobodnim izlaznim portovima. Prvi SGS rasporeñivač u lancu dobija vektor slobodnih izlaza u okviru kojega su svi izlazni portovi označeni kao slobodni. Izmeñu vektora zahteva i vektora slobodnih izlaza se vrši operacija ‘logičko I’ 'i kao rezultat se dobija binarni vektor u kome su označeni samo oni izlazni portovi koji su slobodni i za koje dati SGS rasporeñivač ima ćelije. Ovaj rezultujući vektor se vodi na ulaz ‘one-hot’ dekodera koji kao rezultat daje identifikaciju izlaznog reda za čekanje čija je ćelija rasporeñena za slanje. SGS rasporeñivač prosleñuje sledećem SGS rasporeñivaču u lancu ažurirani vektor slobodnih izlaza u kome je izlazni port za koga je rasporeñeno slanje ćelije označen kao zauzet. Rasporeñene ćelije se šalju iz svog izlaznog reda za čekanje preko krosbara ka svom izlaznom portu u onom vremenskom slotu za koji su rasporeñene. Istovremeno SGS rasporeñivač mora da pošalje ka krosbaru i informaciju na koji izlazni port ta ćelija treba da se prosledi. Ova informacija je neophodna da bi se krosbar mogao adekvatno konfigurisati. Postoje dva načina za slanje ove konfiguracione informacije. Jedan način je da se one šalju posebnim linijama koje bi povezivale SGS rasporeñivač i krosbar, a drugi način je da se ova informacija doda u zaglavlje ćelije. U prvom slučaju bi bile neophodne zasebne linije izmeñu svakog SGS rasporeñivača i krosbara, što u slučaju velikog broja portova rutera predstavlja problem jer bi postojao velik broj takvih linija kroz bekplejn s obzirom da su SGS rasporeñivači na štampanim pločama linijskih modula, a krosbar na svojoj štampanoj ploči. Otuda ovo rešenje limitira skalabilnost rutera jer se kroz bekplejn može postaviti ograničen broj interkonekcionih linija. U drugom slučaju se ovaj problem prevazilazi jer nema dodatnih linija koje bi se koristile za prenos konfiguracionih informacija ka krosbaru, već bi ta informacija bila uneta u 34 zaglavlje ćelije odakle bi je krosbar mogao izvući. Ova varijanta ima manu što povećava zaglavlje. Na osnovu prethodnog razmatranja, u okviru implementacije je izabrano drugo rešenje jer je skalabilnije. Kao što je rečeno u prethodnom poglavlju ruteri sa arhitekturom sa ulaznim baferima predstavljaju najskalabilniju jednostepenu arhitekturu. Takoñe, u ovom odeljku se moglo videti da je interna struktura SGS rasporeñivača jednostavna za implementaciju i lako proširiva. Otuda SGS rasporeñivač ne predstavlja potencijalno usko grlo za proširenje kapaciteta Internet rutera. 3.2.5. DDR2 kontroler Ćelije koje dolaze u ruter se rasporeñuju za slanje kroz krosbar prema SGS algoritmu, a dok čekaju na svoj red za slanje se smeštaju u bafere. Isto tako, na izlaznom portu pristigle ćelije se moraju čuvati u baferima dok se čeka na kompletiranje paketa kome dotične ćelije pripadaju, ili da se postojeći paketi pošalju jer krosbar ima ubrzanje u odnosu na izlaz. Da bi se obezbedila mogućnost smeštanja velikog broja ćelija u slučajevima privremenih zagušenja, neophodno je realizovati bafere velikih kapaciteta. Otuda se za realizaciju bafera često koriste eksterne DRAM (Dynamic Random Access Memory) memorije koje imaju velike kapacitete [45]-[49]. U realizovanoj implementaciji je korišćena DDR2 SDRAM memorija jer obezbeñuje velike brzine i kapacitete, a cene tih memorija su ekonomične. Meñutim, generalni problem DRAM memorija je nedeterministički protok u slučaju kada se pristupa lokacijama po slučajnom principu, usled procesa aktivacije banaka i redova, ali i periodičnog osvežavanja memorijskih blokova koji se moraju vršiti da bi se zadržao integritet upisanih podataka. To znači da u slučaju sukcesivnog upisa (ili čitanja) ćelija u različite banke ili redove DRAM memorije, ostvareni protok može značajno da opadne. Jedini način da se u radu sa DRAM memorijom postigne velik i približno deterministički protok je da se vrši upis dovoljno dugih burstova ćelija u sukcesivne memorijske lokacije i time što više izbegne negativni uticaj procesa aktivacije banaka, odnosno redova. 35 Prednji deo internog bafera Zadnji deo internog bafera Prednji deo internog bafera Zadnji deo internog bafera Rasporeñena ćelija Pročitani burst ćelija Burst ćelija za upis Nova ćelija Interni bafer reda za čekanje 1 Interni bafer reda za čekanje NQ Slika 3.2.5.1. – Struktura internog bafera Najefikasniji menadžment memorijskog prostora se ostvaruje primenom virtuelnih redova za čekanje jer se time obezbeñuje dinamičko alociranje memorijskog prostora redovima za čekanje u skladu sa njihovim potrebama [22], [49]. Na taj način se memorijski prostor maksimalno efikasno koristi jer se lako prilagoñava trenutnim veličinama redova za čekanje koje mogu biti veoma promenljive tokom vremena. Meñutim, tehnika virtuelnih redova za čekanje zahteva memorije sa determinističkim vremenom pristupa bilo kojoj memorijskoj lokaciji, odnosno deterministički protok u slučaju slučajnog pristupa memorijskim lokacijama. Otuda ova tehnika nije pogodna za primenu u DRAM memorijama. Zato se umesto virtuelnih redova za čekanje koristila ideja predložena u [45]-[46]. Ona se zasniva na dodeljivanju jednog internog bafera FPGA čipa svakom redu za čekanje. Oni se koriste za prikupljanje dovoljno velike količine ćelija da oformi burst ćelija koje bi bile upisane u sukcesivne lokacije u DRAM memoriji. Takoñe, u suprotnom smeru kad ćelije treba da se pročitaju, čita se burst ćelija koji se smešta takoñe u interni bafer. Struktura internog bafera je prikazana na slici 3.2.5.1. Interni bafer smešta dolazne i odlazne burstove ćelija. Kao što je rečeno baferi na ulaznim portovima čuvaju ćelije koje čekaju svoj redosled na slanje kroz krosbar do odgovarajućeg izlaznog porta. S druge strane, na izlaznim portovima se čuvaju ćelije nekompletiranih paketa koje čekaju na pristizanje svih ćelija paketa da bi mogla da otpočne rekonstrukcija originalnog IP paketa iz ćelija i njegovo slanje na izlazni link. U oba slučaja struktura internog bafera je ista. Interni bafer se sastoji iz dva dela – prednjeg i zadnjeg dela. Oba dela su istog kapaciteta koji je jednak veličini bursta ćelija koji se upisuje u eksternu DRAM memoriju. Na ulaznom portu tokovi su identifikovani po izlaznom portu kome 36 su ćelije namenjene, a na izlaznom portu po identifikaciji ulaznog porta sa kog su ćelije došle. Kada pristigne nova ćelija ona se upisuje u prednji deo internog bafera ukoliko je ukupan broj ćelija tog toka manji od kapaciteta prednjeg dela internog bafera. U suprotnom se ćelija upisuje u zadnji deo bafera. Onog momenta kad se zadnji deo bafera napuni burst sastavljen od ćelija iz zadnjeg dela internog bafera se upisuje u eksternu DRAM memoriju. Ćelije koje treba da se pročitaju iz internog bafera radi slanja ka krosbaru (ulazni port) ili rekonstrukcije kompletiranog paketa (izlazni port) se jednostavno čitaju po FIFO (First In First Out) principu iz prednjeg dela internog bafera. Svaki put kad se isprazni prednji deo bafera u njega se upisuje burst ćelija iz eksterne DRAM memorije ili ako on ne postoji onda ćelije iz zadnjeg dela bafera. U okviru implementiranog DDR2 kontrolera je realizovan i memorijski interfejs koji omogućava operacije upisa i čitanja burstova ćelija ka eksternoj DDR2 SDRAM memoriji. S obzirom da izabrana DDR2 SDRAM memorija radi na spoljašnjem taktu od 200MHz, a moduli paketskog procesora zbog brzine gigabitskog eterneta na 125MHz (8 bita na 125MHz je ekvivalentno protoku od 1Gb/s) u okviru DDR2 kontrolera su implementirana i dva FIFO bafera – jedan za operacije upisa i jedan za operacije čitanja. Oni se koriste za omogućavanje prelaza izmeñu različitih takt oblasti od kojih jedna radi na 200MHz, a druga na 125MHz unutar DDR2 kontrolera. Interni baferi rade na taktu na kom rade i ostali moduli paketskog procesora (125MHz), dok u oblast takta od 200MHz u okviru DDR2 kontrolera spada samo fizički deo memorijskog interfejsa ka eksternoj DDR2 SDRAM memoriji. Opisana struktura internih bafera u radu sa eksternom DRAM memorijom omogućava upis i čitanje dovoljno dugih burstova čime se postiže visok protok i približno determinističko vreme pristupa. Naravno, cena koja je plaćena je značajna upotreba internih memorijskih resursa FPGA čipa za implementaciju internih bafera. Veličina jednog internog bafera je 2 ·  · , gde je  veličina bursta ćelija u bitima, a  broj portova rutera tj. broj redova za čekanje na ulaznom portu, odnosno izlaznom portu. Kao što se vidi ukupni zahtevani interni memorijski resursi FPGA čipa za realizaciju internih bafera linearno rastu sa porastom broja portova rutera. Isto tako povećanje brzine linkova zahteva i povećanje brzine pristupa memorijskim lokacijama jer su vremenski slotovi kraći. Na osnovu navedenog može se zaključiti da implementacija paketskih bafera predstavlja ozbiljan problem i može biti usko grlo koje 37 ograničava skalabilnosti rutera. Stoga je važno izvršiti analizu eksternih memorijskih čipova na tržištu i utvrditi koji od njih je najbolji za realizaciju bafera ćelija pre svega imajući u vidu omogućavanje što veće skalabilnosti rutera. 3.2.6. SERDES modul Za povezivanje paketskih procesora sa krosbarom se koriste multigigabitski linkovi koji koriste serijski diferencijalni prenos. Diferencijalni prenos se koristi zbog povećanja otpornosti na šum. Da bi se ćelije koje se razmenjuju sa krosbarom prilagodile za prenos preko multigigabitskih linkova koristi se SERDES modul koji vrši proces konverzije paralelnog prenosa ćelija u serijski u smeru slanja ćelija ka krosbaru i obrnutu konverziju u suprotnom smeru. Primljene ćelije iz krosbara se prosleñuju izlaznom mrežnom modulu. SERDES modul je implementiran upotrebom GTP blokova koji postoje u Xilinx FPGA čipovima i koji omogućuju korišćenje multigigabitskih linkova [35]. GTP blokovi su konfigurabilni i omogućavaju implementaciju fizičkog sloja različitih standarda za multigigabitski prenos poput PCI-Express [50], RapidIO [51], SATA [52] i dr. Takoñe je moguće konfigurisati GTP blok za implementaciju sopstvenog rešenja fizičkog sloja u slučaju potrebe. Struktura GTP bloka je prikazana na slici 3.2.6.1. GTP blokovi imaju podršku za linijsko kodovanje i dekodovanje, elastični bafer u prijemnom smeru, ekstrakciju takta i dr. PLL (Phase-Locked Loop) generiše takt neophodan za rad svih delova GTP bloka. PLL ima izbor izmeñu više izvora na koje može da se sinhroniše i u okviru konfigurisanja GTP bloka se definiše koja opcija će se koristiti: eksterni diferencijalni takt, interni takt doveden iz unutrašnjosti FPGA čipa, takt doveden iz susednog GTP bloka. Maksimalna brzina koju podržava GTP blok je 3.125Gb/s. U implementaciji paketskog procesora, GTP blokovi su konfigurisani da rade kao fizički sloj PCI-Express standarda, pri čemu je podešena brzina od 2.5Gb/s zbog trenutnih tehničkih mogućnosti bekplejna. Pošto je prenos diferencijalni postoje četiri linije za podatke na multigigabitskom linku, po dve za svaki smer prenosa (Tx+ i Tx- za predajni smer, i Rx+ i Rx- za prijemni smer). Linijsko kodovanje koje se koristi je 8B/10B linijsko kodovanje, pa je brzina korisničkog saobraćaja na multigigabitskim linkovima 2Gb/s (  · 2.5Gb/s  2Gb/s). 38 Slika 3.2.6.1. – Struktura GTP bloka 3.2.7. Izlazni mrežni modul Izlazni mrežni modul prikazan na slici 3.2.7.1 prima ćelije pristigle iz krosbara od SERDES modula. Ove ćelije se smeštaju u izlazne redove za čekanje koji se nalaze u eksternoj DDR2 SDRAM memoriji i internim baferima DDR2 kontrolera, i organizovani su kako je opisano u odeljku 3.2.5. Izlazni redovi za čekanje se razlikuju na osnovu identifikacije ulaznog porta na kom su nastale tj. sa kog su pristigle, pri čemu je ova informacija inkorporirana u zaglavlje svake ćelije pa se lako odreñuje kom redu za čekanje ćelija pripada. Izlazni redovi za čekanje su neophodni za privremeno smeštanje ćelija dok se ne kompletira paket kome pripadaju (tj. pristignu sve ćelije dotičnog paketa). Takoñe, zbog ubrzanja linkova iz krosbara u slučaju privremenog preopterećenja izlaznog linka može da se desi da protok ćelija koje pristižu sa ulaznih portova prevazilazi kapacitet izlaznog linka. Pošto su sve kontrolne informacije o ćeliji smeštene u njenom zaglavlju, ćelije po ulazu u izlazni mrežni modul prolaze kroz blok za procesiranje zaglavlja ćelije. Ovaj blok ispituje zaglavlje ćelije i na osnovu njega izvršava odgovarajuće akcije. Prvo se odreñuje kom izlaznom redu za čekanje ćelija pripada i ćelija se upisuje u taj izlazni red za čekanje. Izlazni red za čekanje kom ćelija pripada se odreñuje na osnovu identifikacije ulaznog porta sa kog je ćelija došla, a koja se nalazi u zaglavlju ćelije. Takoñe, na osnovu zaglavlja ćelije se odreñuje poslednja ćelija paketa na osnovu bita indikacije poslednje ćelije paketa koji se nalazi u zaglavlju ćelije. Kada se detektuje poslednja ćelija paketa, to onda znači da je paket kome ta ćelija pripada kompletiran. Tada se vrši ažuriranje liste kompletiranih paketa koja je smeštena u FIFO memoriju. Lista kompletiranih paketa je uvedena pošto može da se desi da istovremeno postoji 39 više kompletiranih paketa. Lista kompletiranih paketa sadrži samo identifikaciju izlaznog reda za čekanje kome kompletirani paket pripada. Kompletirani paketi se šalju po FIFO principu. Prilikom slanja kompletiranog paketa vrši se njegova rekonstrukcija tako što se čitaju ćelije dotičnog paketa iz DDR2 kontrolera. Sa ćelija se skida zaglavlje i njihov korisni sadržaj se lepi jedan za drugim. U slučaju poslednje ćelije paketa se uzima samo onaj deo ćelije koji pripada rekonstruisanom IP paketu, pošto korisni deo poslednje ćelije ne mora biti popunjen do kraja bajtovima IP paketa. U prvoj ćeliji se nalazi IP zaglavlje paketa u okviru koga se nalazi 16-bitni podatak o ukupnoj dužini paketa u bajtovima koji se upisuje u brojač pročitanih bajtova paketa. Ovaj brojač se dekrementira za svaki pročitani bajt paketa. Vrednost brojača na početku obrade poslednje ćelije paketa je jednaka broju preostalih bajtova paketa i na osnovu toga se zna koji deo poslednje ćelije sadrži bajtove paketa. Rekonstruisani IP paket se prosleñuje izlaznom modulu sloja linka za formiranje okvira i dalje slanje na izlazni link. Treba napomenuti da se u slučaju podrške saobraćaja različitih nivoa kvaliteta servisa pored identifikacije ulaznog porta sa kog je ćelija došla, koristi i ToS vrednost u zaglavlju ćelije za razlikovanje izlaznih redova za čekanje. Takoñe, za svaki nivo kvaliteta servisa, odnosno vrednost ToS polja, se formira zasebna lista kompletiranih paketa čime je omogućeno slanje paketa u skladu sa zahtevanim prioritetima tj. lako je realizovati mehanizam kvaliteta servisa [40]-[41]. Kako se može videti implementacija izlaznog mrežnog modula ne obavlja složene operacije tako da ovaj modul ne predstavlja usko grlo odnosno ne ograničava skalabilnost rutera. Slika 3.2.7.1. – Struktura izlaznog mrežnog modula 40 3.2.8. Izlazni modul sloja linka Izlazni modul sloja linka na primljeni IP paket dodaje eternet okvir i šalje formirani okvir fizičkom sloju (SFP modulu) za slanje na izlazni link. Kao što je već rečeno u odeljku 3.2.1, sloj linka podataka je implementiran koristeći ugrañene MAC blokove korišćenog FPGA čipa. Ugrañeni MAC blok dodaje kontrolne delove zaglavlja (preambulu, SFD i FCS polje) i takoñe reguliše IFG (InterFrame Gap) koji predstavlja razmak izmeñu uzastopnih okvira. Takoñe je uz ugrañeni MAC blok implementiran i blok koji vrši dodavanje ostalih delova eternet zaglavlja: izvorišne i odredišne MAC adrese, i informacije o enkapsuliranom protokolu u okviru. Pored okvira u koje su enkapsulirani korisnički IP paketi, izlazni modul sloja linka takoñe prosleñuje i okvire koje šalje procesorski modul u mrežu. Pošto procesorski modul kreira zaglavlje okvira sem preambule, SFD i FCS polja, onda se okvir dobijen od procesorskog modula direktno prosleñuje ugrañenom MAC bloku. Kao što je već rečeno u odeljku 3.2.1. izlazni modul sloja linka ne predstavlja ograničenje u pogledu skalabilnosti rutera. 3.2.9. Interfejs ka procesorskom modulu Interfejs ka procesorskom modulu ne spada u deo paketskog procesiranja, ali će ipak biti ukratko objašnjena njegova uloga, kao i koji se sve podaci razmenjuju preko ovog interfejsa. Interfejs ka procesorskom modulu omogućava povezivanje kontrolne ravni i ravni podataka. Preko ovog interfejsa je omogućeno slanje i prijem kontrolnih paketa kao što su ARP okviri, OSPF paketi i dr. U slučaju kada pristigne kontrolni paket namenjen ruteru vrši se njegovo prosleñivanje iz ulaznog modula sloja linka ka procesorskom modulu preko ovog interfejsa. Isto tako kad procesorski modul treba da pošalje kontrolni paket ili okvir preko nekog izlaznog porta on preko interfejsa ka procesorskom modulu prosleñuje formirani okvir ka izlaznom modulu sloja linka odgovarajućeg izlaznog porta za slanje na izlazni link. Pored kontrolnih paketa, ovaj interfejs se koristi i za slanje komandi procesorskog modula ka paketskom procesoru, kao i za prijem statusnih informacija od paketskog procesora. U komande spada aktivacija i deaktivacija porta, kao i ažuriranje lukap tabele. Ažuriranje lukap tabele predstavlja rezultat rada protokola rutiranja u okviru procesorskog modula i neophodno je za održavanje tačnih informacija u lukap tabeli neophodnih za pravilno usmeravanje paketa [43]. Komande ažuriranja se prosleñuju u parovima adresa-podatak, gde adresa definiše lokaciju u SRAM memoriji na koju se upisuje dati podatak. Na ovaj način je 41 omogućeno brisanje postojećih prefiksa, dodavanje novih prefiksa ili modifikacija ID-a izlaznog porta pridruženog postojećem prefiksu. U očitavanje statusa spada provera prisutnosti konekcije (tj. da li je kabl priključen ili ne). Trenutno se koristi paralelni procesorski interfejs prikazan na slici 3.1.2, pošto je taj interfejs korišćen u Iritelovim sistemima, a procesorski modul koristi procesorsku ploču iz Iritelovih sistema kao što je već rečeno [5]-[6]. U sledećoj verziji prototipa rutera, namera je da se preñe na neki od brzih serijskih interfejsa ka centralnom procesoru poput PCI-Express ili RapidIO koji omogućavaju veće brzine komunikacije. Interfejs ka procesorskom modulu tipično ne predstavlja potencijalno usko grlo u skalabilnosti rutera jer je intezitet komunikacije znatno manji u odnosu na protok paketa kroz ravan podataka. Meñutim, sa razvojem novih servisa i funkcionalnosti, ovaj interfejs može ograničiti skalabilnost rutera. 3.2.10. Performanse implementacije paketskog procesora Kao što je navedeno u potpoglavlju 3.1, u okviru jednog FPGA čipa je implementirano četiri paketska procesora. Korišćen je Xilinx-ov Virtex5 LX110T čip [35]. Sva četiri paketska procesora koriste isti lukap modul i lukap tabelu za izvršenje lukapa. Lukap tabela je smeštena u SRAM memoriju kapaciteta 2MB, pri čemu je konfiguracija memorije 512Kx32b, a korišćen je čip firme Cypress [36]. Baferi u koji se smeštaju ćelije su realizovani u okviru internih bafera FPGA čipa koji su alocirani DDR2 kontroleru, kao i u eksternoj DDR2 SDRAM memoriji kapaciteta 1GB. Micron SODIMM DDR2-800 memorija je korišćena u okviru implementacije [37]. DDR2 kontroler i DDR2 SDRAM memoriju koriste sva četiri paketska procesora. Svi delovi paketskog procesora rade na taktu od 125MHz, sem dela DDR2 kontrolera koji radi na 200MHz kako je i navedeno u odeljku 3.2.5. Iskorišćeni resursi FPGA čipa za implementaciju paketskih procesora su dati u tabeli 3.2.10.1. Svih modula ima po četiri koliko ima i paketskih procesora, samo modula koje dele paketski procesori ima po jedan (lukap modul i DDR2 kontroler). Resursi za ulazne i izlazne module linka podataka su dati zajedno pošto njih nije bilo moguće razdvojiti zbog upotrebe ugrañenih MAC blokova. Iz tabele 3.2.10.1 se može videti da je memorija najkritičniji interni resurs FPGA čipa. Najviše memorije zauzimaju baferi u FPGA memoriji koji su deo DDR2 kontrolera, pri čemu je bitno naglasiti da bi oni dodatno rasli za slučaj da broj portova raste (trenutno su veličine internih bafera dimenzionisane za podršku 16 portova). Tako izmeñu različitih domena takta. Slika 3.2.10.1. Opisana implementacija predstavlja osnovu paketskog procesiranja podataka prototipa Internet rutera, FPGA čip moguće je na jednostavan na procesiranja, ali i modifikovati i unapre Na ovaj način je obezbeñ podataka rutera, tako i kontrolne ravni. Prototip rutera prikazan na slici 3.2.10.1 je testiran povezivanjem sa softverskim r ploča (izvučena iz prototipa rutera) prikazana na slici 3.2.10.1 predstavlja linijski i krosbar modul jer, kako je i navedeno u ova dva modula smeštena na istoj štampanoj plo Tabela 3.2.10.1. – Iskorišć Modul Broj modula Ulazni i izlazni modul sloja linka Ulazni mrežni modul Izlazni mrežni modul Lukap modul DDR2 kontroler SGS rasporeñivač SERDES modul Ukupno ñe su implementirani i FIFO baferi koji služe kao most – Realizovani prototip rutera i predstavlja prvi doprinos ove teze. Pošto je koriš čin dodavati nove funkcije paketskog ñivati postojeće funkcije paketskog p ena platforma za dalja istraživanja kako funkcija ravni uterima, kao i Cisco ruterima potpoglavlju 3.1, u prvoj ver či iz ekonomskih razloga. eni resursi FPGA čipa za implementaciju paketskih procesora Logički elementi Registri 4 970 6020 4 572 1015 4 976 4753 1 103 171 1 451 4118 4 740 3862 4 182 1463 - 3994 (6%) 21402 (31%) 42 unutar ravni ćen rocesiranja. [53]. Štampana ziji prototipa su Memorija 288Kb 144Kb 144Kb 0Kb 1404Kb 0Kb 144Kb 2124Kb (40%) 43 S obzirom na planove našeg istraživačkog tima da se implementiraju i veće brzine portova, kao i da se poveća ukupan broj portova rutera, u okviru ovog poglavlja izvršena je analiza u cilju prepoznavanja potencijalnih uskih grla pri povećanju kapaciteta rutera. Prvo potencijalno usko grlo je lukap koji značajno zavisi od brzine portova, ali i od dužine IP adrese i broja zapisa u lukap tabeli. Drugo potencijalno usko grlo su baferi koji čuvaju ćelije. Njihova implementacija zavisi i od broja portova i od brzine portova, pa je potrebno izvršiti adekvatnu analizu uzimajući u obzir tipove postojećih memorija i njihove performanse. Drugi deo teze je posvećen rešavanju problema lukapa. Cilj drugog dela teze je da predloži rešenja koja bi se implementirala u okviru prototipa rutera sa portovima velikih brzina (10Gb/s i više). U drugom delu teze će biti predloženi novi lukap algoritmi koji su namenjeni za primenu u slučaju veoma brzih portova i lukap tabela sa velikim brojem zapisa, pri čemu će biti podržane i IPv4 i IPv6 adrese. Predloženi novi lukap algoritmi predstavljaju drugi doprinos teze. 44 4. PREGLED LUKAP ALGORITAMA Kao što je već navedeno u prethodnom poglavlju, lukap predstavlja jedno od potencijalnih uskih grla u daljem razvoju Internet rutera te je stoga potrebno obratiti posebnu pažnju na ovu funkciju. Prvo će biti objašnjen sam lukap i aspekti koji ga čine veoma komplikovanim i zahtevnim za realizaciju. Takoñe će biti navedeni zahtevi koje moderni lukap algoritmi moraju da ispune. Potom će biti data klasifikacija lukap algoritama, gde će biti navedene i prezentovane klase lukap algoritama. Pri tome će za svaku klasu biti navedeni najpoznatiji lukap algoritmi iz dotične klase, kao i analiza njihovih performansi. 4.1. Lukap Ruteri predstavljaju osnovnu gradivnu jedinicu Internet mreže. Njihova osnovna funkcija je rutiranje, tj. usmeravanje paketa ka njihovom odredištu na osnovu njihove IP adrese. Proces odreñivanja izlaznog porta rutera na koji treba usmeriti pristigli paket se naziva lukap. Da bi lukap mogao da se izvrši neophodno je da ruter zna topologiju mreže tj. da zna gde se koje odredište nalazi. IP adresa se sastoji iz dva dela – mrežnog dela i host dela. Ruter vrši usmeravanje na osnovu mrežnog dela IP adrese čime usmerava paket ka odredišnoj mreži gde se nalazi host kome je paket namenjen. U samoj odredišnoj mreži usmeravanje se dalje vrši koristeći host deo adrese. Otuda je neophodno da ruter poznaje samo mrežne delove IP adresa, tj. da za svaku mrežu zna gde se ona nalazi i preko kog porta mu je dostupna. Da bi prikupio ove informacije neophodno je da ruteri meñusobno komuniciraju i razmenjuju informacije, čime ruter uči topologiju mreže u kojoj se nalazi. Protokoli rutiranja poput OSPF [54], BGP [55], RIP [56] i dr. se koriste za razmenu tih informacija. Kao rezultat rada protokola rutiranja, ruter formira tzv. lukap tabelu koja za svaku mrežnu adresu definiše koji izlazni port rutera predstavlja najkraću putanju do mreže koja je definisana tom mrežnom adresom. Za svaki pristigli paket se prema definisanom lukap algoritmu, vrši 45 pretraga lukap tabele na osnovu IP adrese paketa, i odreñuje se na koji izlazni port rutera paket treba da se usmeri. Slika 4.1.1. – Primer agregacije mrežnih adresa U početku se na Internetu koristilo klasno adresiranje gde su za unikast IP adrese definisane tri klase – A, B i C, u kojima su mrežni delovi IP adrese sadržali prvih 8, 16 i 24 bita, respektivno. Klasno adresiranje nije racionalno koristilo adresni prostor pa se ubrzo prešlo na besklasno adresiranje gde je granica izmeñu mrežnog i host dela adrese bila proizvoljna, čime je omogućena racionalnija upotreba adresnog prostora. Takoñe, besklasno adresiranje je omogućilo ruterima da vrše agregaciju više mrežnih adresa u jedan zapis koji bi oglašavali drugim ruterima putem protokola rutiranja, čime se smanjuje ukupan broj unosa u lukap tabelama rutera. Jedan takav primer je pokazan na slici 4.1.1 gde ruter R1 agregira 16 mrežnih adresa u jedan zapis koji oglašava ruteru R2. Na ovaj način ruter R2 u lukap tabelu smešta samo jedan zapis umesto 16 zapisa da nije korišćena agregacija. U primeru sa slike 4.1.1 agregacija je idealna jer se opseg agregiranog zapisa u potpunosti poklapa sa kompletnim opsegom mrežnih adresa koje su agregirane. Meñutim, agregacija ne mora da bude idealna. U tom slučaju agregirani zapis može da obuhvati i neke mrežne adrese koje nisu ušle u proces agregacije. Na slici 4.1.2 je prikazan takav primer, gde ruter R1 formira agregirani zapis od 15 mrežnih adresa i prosleñuje ga ruteru R2, a ruter R3 prosleñuje ruteru R2 informaciju o mrežnoj adresi 196.0.1.0/24. Mrežna adresa 196.0.1.0/24 je obuhvaćena agregiranim zapisom iako nije bila uključena u proces agregacije u ruteru R1. Otuda će lukap u ruteru R2 za pakete namenjene hostovima u mreži 196.0.1.0/24 da nañe dva rešenja – jedno koje odgovara 46 agregiranom zapisu dobijenom od rutera R1 i koje kazuje da ti paketi treba da se usmere ka ruteru R1 i drugo koje odgovara zapisu dobijenom od rutera R3 i koje kazuje da te pakete treba usmeriti ka ruteru R3. Pošto lukap može da nañe više rešenja, usvojeno je pravilo najdužeg poklapanja koje odreñuje da se za konačno rešenje usvoji zapis koji se najduže poklapa sa IP adresom za koju se vrši lukap. Ovo pravilo se naziva LPM pravilo. Pošto se u lukap tabeli mogu nalaziti mrežne adrese, ali i agregacije mrežnih adresa, usvojen je termin prefiks koji označava oba slučaja i u nastavku rada će se koristiti ovaj termin. Primenom LPM pravila, ruter R2 će sve pakete namenjene hostovima iz mreže 196.0.1.0/24 pravilno usmeravati ka ruteru R3. Slika 4.1.2. – Primer agregacije mrežnih adresa koja nije idealna Kao što se moglo videti iz prethodnih primera agregacija značajno smanjuje broj zapisa u lukap tabelama i samim tim njihovu veličinu, ali dovodi do pojave da za jednu IP adresu može da postoji više rešenja. Ova pojava značajno doprinosi kompleksnosti lukapa jer prilikom nalaženja rešenja neophodno je biti siguran i da je ono najbolje rešenje jer u suprotnom može doći do grešaka u usmeravanju. Tako u primeru sa slike 4.1.2. u procesu lukapa u ruteru R2 za paket koji je namenjen hostu iz mreže 196.0.1.0/24, ako je prvo nañeno rešenje ono koje odgovara agregiranom zapisu 196.0.0.0/20 i ako se pretraga okonča odmah po nalaženju prvog rešenja došlo bi do greške u usmeravanju paketa jer umesto ka ruteru R3 paketi bi se usmeravali ka ruteru R1. Otuda lukap koji na prvi pogled izgleda jednostavan postaje veoma komplikovan jer nije dovoljno samo naći rešenje, nego je i potrebno biti siguran da je ono zaista najbolje. 47 Dodatni problemi prilikom realizacije lukapa su tehnički zahtevi. Linkovi koji se instaliraju u mreži dostižu i 100Gb/s. Lukap mora da nañe rešenje za vreme trajanja IP paketa jer u suprotnom bi dolazilo do gomilanja paketa na ulazu, usled čekanja na rezultat lukapa koji treba da odredi na koji izlaz rutera paketi treba da se usmere, i samim tim i gubitaka paketa. Prilikom dizajna lukapa uzima se u obzir najgori slučaj. Najgori slučaj je da u ruter pristižu paketi minimalne dužine jer oni najkraće traju i lukap ima najmanje vremena na raspolaganju u tom slučaju. Najmanja dužina IP paketa je 40B, u kome se prenosi samo osnovno zaglavlje IP paketa. U tabeli 4.1.1 je dat prikaz vremena za koji lukap treba da se izvrši za različite brzine linkova. Prilikom proračuna se mora uzeti u obzir i činjenica da drugi sloj (sloj linka podataka) dodaje svoja polja na IP paket, pa se za minimalnu dužinu paketa u proračunu u stvari uzima minimalna dužina okvira na drugom sloju, a ne dužina najkraćeg IP paketa bez polja drugog sloja. U proračunu prikazanom u tabeli 4.1.1 je smatrano da se koristi eternet tehnologija i da je najkraće trajanje okvira 64B. Može se videti da, pri velikim brzinama linkova, lukap mora da se izvrši za veoma kratko vreme – svega 5.12ns za slučaj 100Gb/s linka. Tabela 4.1.1. – Vreme izvršavanja lukapa za različite brzine linkova Brzina linka Trajanje najkraćeg okvira (vreme za koje lukap mora da se izvrši) 100Mb/s 5120ns 1Gb/s 512ns 10Gb/s 51.2ns 40Gb/s 12.8ns 100Gb/s 5.12ns Imajući u vidu da lukap tabela mora da se smesti u neku memoriju i da prilikom izvršavanja lukapa mora da se pristupa tim podacima jasno je da je broj pristupa lukap tabeli veoma ograničen pri velikim brzinama linkova. Očigledno je da zahtevane (i velike) brzine lukap algoritama zahtevaju hardversku realizaciju lukapa pri čemu mora da se posebno vodi računa o organizaciji podataka (zapisa) u lukap tabeli i samoj pretrazi lukap tabele da bi se postigle zahtevane performanse, a da se ne potroše veliki hardverski resursi. Zahtevi za visokom brzinom izvršavanja lukapa dodatno doprinose kompleksnosti realizacije lukapa. Usled toga se često koriste dodatni protokoli poput MPLS (Multi-Protocol Label Switching) [57] i GMPLS (Generalized Multi-Protocol Label Switching) [58] protokola, koji omogućavaju efikasnije usmeravanje na bazi labela umesto IP adresa u jezgru Internet mreže, gde su i najveće brzine linkova. 48 Meñutim, MPLS i GMPLS protokoli zahtevaju dodatnu kompleksnost u ravni podataka, i na kontrolnoj ravni. Takoñe, IP lukap se ne može u potpunosti izbeći jer ruteri na ulazu u MPLS mrežu moraju odrediti prvu MPLS labelu i izlazni port na osnovu IP adrese. Topologija mreže se neprestano menja usled dodavanja novih linkova, rutera, ali isto tako i usled otkaza linkova, rutera itd. Protokoli rutiranja obaveštavaju sve rutere u mreži o nastalim promenama. Na osnovu ovih informacija, centralni procesor rutera izračunava novu lukap tabelu i spušta je na paketske procesore rutera. Proces promene sadržaja lukap tabele se naziva proces ažuriranja u okviru koga se dodaju novi prefiksi, menja informacija o izlaznom portu za postojeće prefikse ili brišu postojeći prefiksi. Proces ažuriranja je znatno sporiji od procesa pretrage tj. lukapa, jer se lukap vrši za svaki paket, a ažuriranje značajno reñe, samo kada doñe do promene u mreži. Meñutim, neophodno je da se promene brzo unose u lukap tabele da bi što reñe dolazilo do grešaka u usmeravanju podataka usled zastarelosti i netačnosti podataka u lukap tabeli, pa je neophodno da se proces ažuriranja lukap tabele izvršava u realnom vremenu. S obzirom na već pomenute zahteve za brzim lukapom, lukap algoritmi često koriste razne vidove komprimovanja podataka u lukap tabelama što s druge strane otežava efikasno ažuriranje takvih struktura. Otuda je prilikom implementacije lukapa potrebno voditi računa o ovim oprečnim zahtevima, s jedne strane treba što bolje komprimovati lukap tabelu da bi se postigla velika brzina lukapa, a sa druge strane kompresija ne sme da dovede do toga da proces ažuriranja ne može da se izvrši u realnom vremenu. Ovi oprečni zahtevi dodatno doprinose složenosti problema IP lukapa. Dodatni problem u realizaciji lukapa predstavlja i velik broj prefiksa koje lukap tabela može da sadrži. Najveće lukap tabele sadrže i do 400000 prefiksa [44] pa samim tim lukap tabele postaju veoma velike čime je lukap dodatno otežan jer je neophodno efikasno smestiti i pretražiti veliku količinu podataka. Prvobitno su se koristile IPv4 adrese, ali s obzirom da je IPv4 adresni prostor potrošen, neminovan je prelaz na duže IPv6 adrese, što dodatno komplikuje lukap jer je sada prostor pretrage znatno povećan [59]-[60]. Rezimirajmo zahteve koje IP lukap treba da zadovolji. Lukap mora da podržava efikasnu pretragu i za slučaj IPv4 i IPv6 adresa. Mora da podrži rad sa velikim lukap tabelama koje sadrže nekoliko stotina hiljada prefiksa. Lukap algoritam treba da se 49 izvršava veoma brzo – u vremenu nekoliko nanosekundi za slučaj veoma brzih linkova. Pored toga ažuriranje lukap tabele mora da bude dovoljno efikasno da može da se izvršava u realnom vremenu i time uspešno prati promene topologije mreže. 4.2. Klasifikacija lukap algoritama Lukap algoritmi su došli u fokus istraživača krajem devedesetih godina prošlog veka, kad je besklasno adresiranje bilo široko u upotrebi i kad su lukap tabele dobile značajnije dimenzije, a pri tome brzine linkova bile u porastu [7]. Pre toga, lukap je u ruteru za sve portove bio izvršavan u centralnom procesoru rutera. Meñutim, kako su rasle brzina portova, veličina lukap tabela i broj samih portova, postalo je nemoguće izvršavati lukap u centralnom procesoru koji je pored toga morao izvršavati i druge zadatke kao npr. izvršavanje protokola rutiranja (OSPF, BGP), obavljanje funkcija menadžmenta i dr. Stoga je lukap izmešten na same portove pa je svaki port dobio svoju lukap tabelu i na svakom portu se izvršavao lukap algoritam prema kome se pretraživala odgovarajuća kopija lukap tabele. S takvim razvojem situacije, postalo je neophodno razviti efikasne hardverske implementacije lukapa koje bi koristile što manje hardverske resurse i time bile ekonomičnije za implementaciju. Razvijen je velik broj veoma različitih lukap algoritama, pa se često vrše klasifikacije tih realizacija radi lakšeg pregleda postojećih rešenja. Lukap algoritam definiše strukturu lukap tabele i odreñuje kako se vrši pretraga lukap tabele. Takoñe definiše i način na koji se vrši ažuriranje lukap tabele. Samim tim lukap algoritam definiše u potpunosti način izvršavanja lukapa i njegovu implementaciju. Postoje razne klasifikacije lukap algoritama. Tako se po jednoj klasifikaciji razlikuju softverski i hardverski lukap algoritmi. Meñutim, ova klasifikacija danas nije adekvatna usled tehničkih zahteva u modernim ruterima, jer lukap mora da se implementira u hardveru. Po drugoj klasifikaciji razlikujemo da li se proces ažuriranja vrši u kontrolnoj ravni (centralnom procesoru) ili ravni podataka. Češća varijanta je da se proces ažuriranja vrši u kontrolnoj ravni iz više razloga. Prvi razlog je taj što se u centralnom procesoru izvršavaju protokoli rutiranja koji daju podatke za ažuriranje lukap tabele. Drugi razlog je što svi portovi koriste istu lukap tabelu, pa je pogodno da centralni procesor izračuna tabelu i pošalje je paketskim procesorima u vidu parova (adresa, podatak) koji definišu na koju lokaciju u lukap tabeli treba upisati dati podatak. 50 Na taj način se izbegava angažovanje dodatnih resursa na svakom portu u ravni podataka za ažuriranje [43]. Time se postiže ekonomičnija izrada i cena rutera. Meñutim, ni ova klasifikacija ne daje nikakve podatke o samoj strukturi lukap algoritama i načinu njihovog rada. Otuda je najbitnija klasifikacija koja se bazira na principima rada lukap algoritama i grupiše ih u odgovarajuće klase. Postoje tri glavne klase lukap algoritama koje obuhvataju sve postojeće lukap algoritme. Prva klasa obuhvata lukap algoritme bazirane na strukturi stabla [59]-[78]. Druga klasa obuhvata lukap algoritme bazirane na specijalnim TCAM (Ternary Content Addressable Memory) memorijama [79]-[85]. Treća klasa obuhvata algoritme bazirane na principu heširanja [86]-[90]. Veoma često se dešava da lukap algoritmi kombinuju tehnike i dobre osobine iz više različitih klasa radi postizanja što boljih performansi. Prve dve navedene klase obuhvataju najveći broj lukap algoritama. U sledećim potpoglavljima će biti dat opis i analiza svake klase, pri čemu će se u svakoj klasi analizirati karakteristični i poznati predstavnici lukap algoritama iz dotične klase. Prilikom analize lukap algoritama, analiziraće se pre svega memorijski resursi jer se oni najviše troše radi smeštanja velikog broja zapisa u slučaju velikih lukap tabela. Pri tome će se prvo analizirati memorijski resursi pojedinih delova lukap algoritama, a zatim će biti data analiza internih memorijskih zahteva. Interni memorijski zahtevi se moraju razmatrati pošto oni značajno utiču na protok lukap algoritama. Interne memorije (memorije koje se nalaze u okviru integrisanog čipa) su brže od eksternih, ali imaju manji kapacitet jer dele prostor čipa sa logikom koja implementira algoritme. Pošto su interni memorijski resursi ograničeni neophodno je da interni memorijski zahtevi lukap algoritama budu mali da bi mogli da stanu unutar jednog integrisanog čipa. Eksterne memorije imaju veće kapacitete od internih memorija, ali su u slučaju brzih eksternih memorija ti kapaciteti takoñe ograničeni (tipično nekoliko MB), pa ukupni memorijski zahtevi lukap algoritama takoñe ne smeju da budu preveliki. Interni memorijski zahtevi će biti analizirani za tri slučaja kada je na raspolaganju jedna, dve i tri eksterne memorije pri čemu je za eksterne memorije stavljeno ograničenje od 144 bita na dužinu magistrale podataka kao u [79]. Veći broj eksternih memorija neće biti razmatran pošto on ne bi bio praktičan za implementaciju zbog prostora na štampanoj ploči. 51 4.3. Algoritmi zasnovani na strukturi stabla Binarno stablo predstavlja prirodnu strukturu kojom može da se predstavi lukap tabela jer se svaki prefiks može predstaviti čvorom stabla pri čemu vrednost prefiksa odreñuje poziciju čvora u stablu tako što definiše put od korena stabla do dotičnog čvora [67], [73]. Uzimajući bit po bit IP adrese, pretraga lukap tabele se vrši kretanjem kroz stablo tako što vrednost ‘0’ uzetog bita odreñuje smer levo u stablu, a vrednost ‘1’ smer desno. Pri tome oni čvorovi stabla koji odgovaraju unetim prefiksima u lukap tabelu sadrže i informaciju o izlaznom portu na koji treba usmeriti pakete čija se odredišna IP adresa poklapa sa datim prefiksom (preciznije čija odredišna IP adresa ima najduže poklapanje u skladu sa LPM pravilom). Informacija o izlaznom portu predstavlja u stvari identifikaciju (ID) izlaznog porta. Prikaz jedne male lukap tabele u vidu binarnog stabla je dat na slici 4.3.1. Svaki čvor u stablu mora da ima polja za pokazivače levo i desno neophodna za kretanje kroz stablo i polje za smeštanje ID-a izlaznog porta jer on predstavlja konačni rezultat pretrage. Na slici 4.3.1 neosenčeni čvorovi ne sadrže validan ID izlaznog porta i oni su prisutni da bi se omogućilo kretanje kroz stablo do čvorova koji sadrže validni ID izlaznog porta. Osenčeni čvorovi sadrže validan ID izlaznog porta. Binarno stablo predstavlja veoma jednostavnu strukturu. Pretraživanje takve strukture se svodi na kretanje kroz stablo na bazi bita IP adrese dok se ne doñe do kraja stabla, a kao konačno rešenje pretrage se uzima poslednji čvor sa validnim ID-em izlaznog porta koji je posećen. Ažuriranje strukture stabla je takoñe jednostavno. Proces dodavanja novog prefiksa se svodi na kretanje kroz stablo i upis ID-a izlaznog porta u odgovarajući čvor, pri čemu se u slučaju da neki čvorovi na putu ne postoje, oni tada kreiraju. Brisanje prefiksa je takoñe jednostavno. Ono se svodi na brisanje ID-a izlaznog porta u dotičnom čvoru i eventualno brisanje tog čvora u slučaju da taj čvor ne poseduje naslednike. U slučaju da se dotični čvor briše, onda se brišu i njegovi prethodnici dok se ne doñe do prvog čvora koji ima validan ID izlaznog porta ili se grana. Ova jednostavnost je doprinela popularnosti strukture stabla za primenu u lukapu. Meñutim, kako su zahtevi za brzinom lukapa rasli, binarno stablo nije moglo da ispuni te nove zahteve. Naime, ukupna dubina binarnog stabla je jednaka dužini IP adrese u najgorem slučaju, 32 bita za IPv4, odnosno 128 bita za IPv6. To znači da ako se svi čvorovi smeste u istu memoriju u najgorem slučaju potrebno je 32 pristupa za slučaj IPv4 52 adresa, a još više za IPv6 slučaj. Sa stanovišta današnjih zahteva da se lukap izvrši u nekoliko desetina nanosekundi ili čak svega nekoliko nanosekundi, tako velik broj pristupa memoriji je neprihvatljiv. Ovo ograničenje može da se reši tako da se svaki nivo stabla smesti u zasebnu memoriju, pa da se primeni pajplajn tehnika tako što se pretraga za narednu IP adresu vrši na nekom nivou kada se pretraga za prethodnu IP adresu preseli na sledeći nivo. Meñutim, ni to nije praktično rešenje jer je zahtevani broj memorija jednak broju nivoa stabla, odnosno dužini najdužeg prefiksa, i samim tim prevelik za praktičnu implementaciju. Iz tog razloga razvijene su različite tehnike kojima se unapreñuje lukap algoritam zasnovan na binarnom stablu, istovremeno zadržavajući dobre osobine binarnog stabla u što je većoj meri moguće. Ove tehnike će biti opisane u narednim odeljcima. 0 00 0 0 1 11 1 1 Prefiks * 00* 01* 11* 001* 10010* ID izl. porta ID1 ID2 ID3 ID4 ID5 ID6 Slika 4.3.1. – Lukap tabela u vidu binarnog stabla 4.3.1. Kompresija putanje Prva tehnika koja se koristi je kompresija putanje u binarnom stablu [71], [73]. Ova tehnika se zasniva kompresiji putanja bez grananja i validnih ID-eva izlaznih portova. Na takvim putanjama nema korisnih odluka – nema validnih ID-eva izlaznih portova koje bi trebalo zapamtiti kao trenutno najbolja rešenja u toku pretrage, a takoñe nema ni grananja koje bi moglo da utiče na smer pretrage. Otuda je najbolje takve čvorove komprimovati, odnosno izbaciti ih iz stabla čime se pretraga koja ide tom putanjom skraćuje za broj komprimovanih čvorova. Meñutim, ova tehnika zahteva uvoñenje dodatnih polja u okviru čvorova stabla. Jedno dodatno polje mora da definiše broj preskočenih (komprimovanih) čvorova – u slučaju da nema preskočenih čvorova ovo polje će imati vrednost 0. Drugo dodatno polje mora da sadrži vrednost komprimovanog puta i ta vrednost se uporeñuje sa odgovarajućim bitima iz IP adrese za koju se vrši pretraga. U primeru sa slike 4.3.1.1 je korišćena lukap tabela prikazana na 53 slici 4.3.1 i komprimovana je putanja za prefiks 10010*. Tako, ako IP adresa za koju se vrši pretraga počinje bitima '10abc', pretraga će od korena krenuti do njegovog desnog deteta, a potom će od tog čvora da skrene ulevo. Pošto je ova putanja komprimovana u ovom čvoru će biti utvrñeno da su preskočena tri čvora i porediće se vrednost 'abc' iz IP adrese sa vrednošću '010' koja odgovara komprimovanoj putanji. Ako se poklapaju onda će se uzeti ID izlaznog porta iz tog čvora kao rezultat pretrage. U suprotnom će biti uzet ID izlaznog porta iz korena stabla, pošto jedino taj čvor sadrži validan ID izlaznog porta na putanji definisanoj IP adresom koja počinje bitima '10abc'. Ruteri su devedesetih godina koristili lukap algoritam PATRICIA koji se zasnivao na strukturi binarnog stabla sa komprimovanim putanjama [71], [73]. Meñutim, ova tehnika ne predstavlja dovoljno unapreñenje. U opštem slučaju maksimalna dubina stabla ostaje ista kao i u slučaju binarnog stabla bez kompresije. Takoñe, kod veoma velikih tabela, koje mogu sadržati i do 400K prefiksa u IPv4 slučaju [44], broj komprimovanih putanja nije značajan i samim tim ova tehnika ne doprinosi značajnom unapreñenju originalnog binarnog stabla. Slika 4.3.1.1. – Primer kompresije putanje 4.3.2. Guranje prefiksa u listove stabla Druga tehnika je guranje prefiksa tj. njihovih ID-eva izlaznih portova u listove stabla [66], [74]. List stabla je onaj čvor koji nema dece. Na ovaj način se izbegava pamćenje ID-a izlaznog porta prilikom kretanja kroz stabla i uzima se ID izlaznog porta iz lista stabla u kom je pretraga okončana, pošto je ovom tehnikom obezbeñeno da se sve pretrage moraju okončati u listovima stabla. Pored toga, postoji i modifikacija ove tehnike gde se prefiksi guraju na odreñene nivoe stabla i koja se koristi u slučaju kada želimo da smanjimo ukupan broj nivoa stabla koji sadrže ID-eve izlaznih portova [61], [65]. 54 4.3.3. Multibitska stabla Slika 4.3.3.1. – Formiranje multibitskog stabla sa strajdom dužine 3 Pošto je osnovni problem binarnog stabla velik broj pristupa memoriji usled velikog broja nivoa stabla, može se izvršiti transformacija binarnog stabla u multibitsko stablo tj. m-arno stablo [63], [66], [69]-[70], [73], [75], [77]. Ova tehnika podrazumeva da se pri kretanju kroz stablo ne koristi samo jedan bit, već  bita, pri čemu se tih  bita označava terminom strajd, a parametar  predstavlja dužinu strajda. Na ovaj način se maksimalan broj nivoa stabla smanjuje. Preciznije, multibitsko stablo sa strajdom dužine  ima  puta manje nivoa u odnosu na binarno stablo. Multibitsko stablo ne mora da ima konstantnu vrednost strajda, već ona može da bude promenljiva duž nivoa stabla. Na slici 4.3.3.1 je prikazano formiranje jednog nivoa multibitskog stabla od binarnog stabla pri čemu je strajd dužine 3. Kao što se sa slike može videti, umesto tri koraka da se doñe do čvorova iz poslednjeg nivoa prikazanog binarnog stabla, potreban je samo jedan korak u prikazanom multibitskom stablu. Na ovaj način se prevazilazi problem broja nivoa binarnog stabla, odnosno broja pristupa memoriji, pa je multibitsko stablo u osnovi svih lukap algoritama baziranih na strukturi stabla. Ali, postoje i novi problemi koje uvodi multibitsko stablo. Prvi problem je smanjena granularnost stabla. Kao što se može videti i sa slike 4. čvorovi) originalnog binarnog stabl izlaznih portova koji su sadržan portova iz tih, sada nevidljivih, tehnikom guranja prefiksa tj. Slika 4.3.3.2. – Primer maskiranja prefiksa i pomeranja prefiksa iz 3.3.1, čvorovi iz prvog i drugog nivoa a se ne vide, pa se samim tim ne vide i u njima. Otuda je neophodno pomeriti čvorova u čvorove multibitskog stabla ve ID-eva izlaznih portova. čvorova binarnog stabla u čvorove multibitskog stabla 55 (neosenčeni ni ID-evi ID-eve izlaznih ć navedenom 56 Primer pomeranja ID-eva izlaznih portova je prikazan na slici 4.3.3.2. Guranje prefiksa potencijalno može da dovede i do povećanja memorijskih zahteva u slučaju reñe popunjenih stabala. Razlog je formiranje velikog broja novih čvorova u vidljivim nivoima multibitskog stabla koji nisu postojali u binarnom stablu. Kod reñe popunjenih stabala broj novoformiranih čvorova u multibitskom stablu može da bude značajno veći u odnosu na broj nevidljivih čvorova naročito u slučaju dugih strajdova. Meñutim, kod m-arnih stabala, ažuriranje postaje komplikovanije zbog maskiranja pojedinih ID-eva izlaznih portova usled toga što su čvorovi na koje ti ID-evi treba da se pomere zauzeti dužim prefiksima tj. njihovim ID-evima izlaznih portova. Tako je u primeru sa slike 4.3.3.2 maskiran prefiks 1*. Naime, usled formiranja multibitskog stabla u primeru sa slike 4.3.3.2 ID-evi izlaznih portova prefiksa 01*, 1* i 10* se moraju pomeriti u čvorove koji će postojati i u multibitskom stablu. Otuda se ID izlaznog porta prefiksa 01* pomera u čvorove koji odgovaraju prefiksima 010* i 011* kao na slici 4.3.3.2. ID izlaznog porta prefiksa 10* se pomera samo u čvor koji odgovara prefiksu 101*, jer se u čvoru koji odgovara prefiksu 100* nalazi ID izlaznog porta dužeg prefiksa - 100*. ID izlaznog porta prefiksa 1* bi trebao da se pomeri u čvorove koji odgovaraju prefiksima 100*, 101*, 110* i 111*. Meñutim, u svim tim čvorovima su smešteni ID-evi dužih prefiksa pa se ID izlaznog porta prefiksa 1* ne vidi u rezultujućem multibitskom stablu. Ta pojava se označava maskiranjem prefiksa 1*, pošto je on maskiran dužim prefiksima 100*, 10*, 110* i 111*. U slučaju brisanja nekih ID-eva izlaznih portova iz čvorova koji odgovaraju maskiranom prefiksu, ID izlaznog porta koji odgovara dotičnom maskiranom prefiksu mora da se smesti u te čvorove koji su se ispraznili. Isto tako prilikom brisanja prefiksa mora da se vodi računa u kojim čvorovima se nalazi ID izlaznog porta koji odgovara datom prefiksu da bi se izvršilo pravilno brisanje. Drugi problem je što se dužina strajda ne može neograničeno povećavati. Razlog je što je broj dece jednog čvora jednak 2! u slučaju multibitskog stabla sa strajdom dužine . To znači da su povećani memorijski resursi za čuvanje jednog čvora, jer on sad mora da čuva 2! pokazivača umesto dva pokazivača kao u slučaju binarnog stabla. Tako npr. ako bi u slučaju IPv4 hteli smanjiti stablo na samo jedan nivo potrebno je postaviti   32, ali je tada broj dece korena jednak 2#$ što zahteva prevelike memorijske resurse za čuvanje pokazivača na tu decu. Takoñe treba uzeti u 57 obzir da jedan nevidljivi čvor u najgorem slučaju može da postavi svoj ID izlaznog porta u 2!% čvorova. Tako da u slučaju kada treba postaviti/promeniti/obrisati ID izlaznog porta u tim čvorovima, potreban je velik broj memorijskih pristupa pa je i ažuriranje nepraktično u tom slučaju. 4.3.4. Bitmap tehnika Da bi se prevazišli problemi multibitskih stabala navedenih u prethodnom odeljku i postigle optimalne performanse lukapa uvedene su dodatne tehnike koje unapreñuju lukap algoritme bazirane na multibitskim stablima. Jedna od najvažnijih tehnika je bitmap tehnika [59]-[61], [63]-[66], [69], [72]. Bitmap tehnika podrazumeva da se informacije mapiraju u odreñeni memorijski prostor, a njihova validnost, odnosno postojanje mapira binarnim vektorom, gde '0' na i-toj poziciji vektora označava nevalidnost/nepostojanje &-te informacije, dok '1' označava validnost/postojanje &-te informacije. Pored binarnog vektora, koji se naziva bitmap vektor, čuva se i jedan pokazivač koji pokazuje na početak memorijskog bloka gde su smeštene informacije na koje se odnosi vektor. Pozicija &-te informacije se računa kao &-ti ofset, odnosno, &-ta lokacija od početka memorijskog bloka. Tipična primena bitmap tehnike u multibitskim stablima je čuvanje pokazivača na decu [63], [66], [69], [72] – slika 4.3.4.1.a. Umesto čuvanja 2! pokazivača, čuva se jedan bitmap vektor dužine 2! bita i samo jedan pokazivač. Bitmap vektor se koristi za odreñivanje da li traženo dete postoji ili ne, dok pokazivač pokazuje na početak memorijskog bloka gde se sukcesivno čuvaju deca dotičnog čvora. Ako dete postoji onda se ide na lokaciju dotičnog deteta, a ta lokacija se računa kao ofset u odnosu pokazivač, gde je ofset jednak poziciji deteta u bitmap vektoru. Na ovaj način se vrši značajna ušteda memorijskih resursa za stablo koje se pretražuje, jer je memorijski resurs jednog čvora u stablu značajno manji. Dodatna optimizacija je da se čuvaju samo deca koja postoje, a da u računanje ofseta ulaze samo postojeća deca, a ne pozicija deteta u vektoru (kada u ofset ulaze i nepostojeća deca). Ova dodatna optimizacija obezbeñuje minimalne memorijske resurse, ali po cenu komplikovanijeg menadžmenta memorije jer memorijski blokovi u kojima se čuvaju deca jednog čvora nisu konstantne veličine. Pored toga bitmap tehnika se može koristiti i za mapiranje delova stabala – tzv. podstabala (slika 4.2.1.4.b) [59]-[61], [64]. Tada se u bloku memorije čuvaju ID-evi izlaznih portova čvorova iz dotičnog podstabla, a bitmap vektor se koristi za 58 označavanje koji čvorovi sadrže validan ID izlaznog porta, a koji ne, dok jedan pokazivač pokazuje na početak memorijskog bloka. I ovde mogu da se čuvaju memorijski blokovi konstantne dužine koji obuhvataju sve čvorove iz bitmapa ili promenljive dužine koji obuhvataju samo čvorove sa validnim ID-em izlaznog porta. Na ovaj način se takoñe štede memorijski resursi, ali se i omogućava da se u jednom koraku proveri podstablo u cilju odreñivanja da li postoji čvor od interesa koji sadrži ID izlaznog porta, umesto da se vrši kretanje kroz podstablo koje zahteva više koraka. U multibitskom stablu se na ovaj način mogu mapirati nevidljivi čvorovi iz binarnog stabla [63], [66], [69]. Time se mogu izbeći problemi koji se javljaju sa guranjem prefiksa, poput voñenja računa o maskiranim prefiksima, problema pri ažuriranju kada treba modifikovati veći broj čvorova koji odgovaraju nevidljivom prefiksu koji je gurnut i dr. a) b) Slika 4.3.4.1. – a) Primena bitmap tehnike u multibitskom stablu; b) Primena bitmap tehnike za delove stabla 59 4.3.5. Kompresija nivoa Slika 4.3.5.1. – Primer tehnike kompresije nivoa Tehnika kompresije nivoa se koristi za optimizaciju strukture binarnog stabla tako što se popunjeni delovi stabla zamene multibitskom strukturom [75]. Na ovaj način se vrši kompresija veoma popunjenih delova stabla. Pri tome, da bi ova tehnika proizvela bolje efekte kompresije, uvodi se prag popunjenosti dela stabla umesto da se zahteva kompletna popunjenost dela stabla. Pa ako je stablo popunjeno iznad praga zamenjuje se multibitskom strukturom. Ova tehnika proizvodi multibitsku strukturu gde je vrednost strajda promenljiva i prilagoñava se trenutnoj strukturi binarnog stabla. Problem ove tehnike je u ažuriranju takve strukture, pošto je neophodno neprestano pratiti popunjenost delova stabla i u skladu s tim vršiti kompresije/dekompresije delova stabla što je vremenski zahtevan proces. Na slici 4.3.5.1 je prikazan primer kompresije 60 nivoa, gde su osenčenim čvorovima označeni delovi stabla koji su zamenjeni multibitskom strukturom. U prikazanom primeru prva tri nivoa su zamenjena jednim multibitskim pri čemu je dužina strajda tri bita (svetlije osenčeni čvorovi), a takoñe je deo stabla ispod čvora koji odgovara prefiksu 101* zamenjen multibitskom strukturom dužine strajda od dva bita (tamnije osenčeni čvorovi). 4.3.6. Paralelizacija i pajplajn Tehnike paralelizacije i pajplajna se koriste za povećanje protoka lukapa koji se meri brojem obavljenih lukapa u jedinici vremena [59]-[62]. One se mogu primeniti u svim klasama lukap algoritama. Tehnika paralelizacije podrazumeva pronalaženje delova algoritma koji mogu da se izvršavaju istovremeno, i oni se implementiraju u odvojenim hardverskim celinama da bi se algoritam ubrzao. U slučaju algoritama zasnovanim na stablima, paralelizacija se sastoji iz razdvajanja delova stabla u posebne hardverske celine čime se omogućava paralelno pretraživanje više delova stabla odjednom i samim tim brže nalaženje rešenja. Pajplajn tehnika se zasniva na tehnici pokretne trake. Ideja je da se lukap modul podeli u hardverske celine kroz koje se lukap obavlja etapno. Cilj je da se iskorišćenje hardverskih resursa maksimizuje tako što će svaka hardverska celina biti zauzeta u svakom trenutku izvršavanjem odgovarajuće etape lukapa za jednu IP adresu. Na taj način hardverske resurse istovremeno koristi više IP paketa čime se značajno povećava protok lukap modula. Tipičan primer paralelizacije i pajplajna je da se svaki nivo stabla smesti u zasebnu memoriju, tako da se pretraga vrši krećući se iz memorije u memoriju [62]. Time čim jedna pretraga za neki paket preñe na sledeću memoriju, sledeća pretraga, za naredni paket, može da koristi trenutnu memoriju kao što je prikazano na slici 4.3.6.1. Slika 4.3.6.1. – Primer pajplajn tehnike 61 4.3.7. Predstavnici lukap algoritama zasnovanih na strukturi stabla Kao što je već napomenuto postoji velik broj lukap algoritama koji se zasnivaju na strukturi stabla i u okviru ovog odeljka će biti navedeni i ukratko opisani neki od karakterističnih i poznatih lukap algoritama iz ove klase. U sledećem poglavlju ovi algoritmi će biti poreñeni po performansama sa lukap algoritmima koji su predloženi i implementirani u okviru ove teze. Stoga će u nastavku ovog odeljka biti ukratko opisan rad izabranih lukap algoritama, a biće i date opšte formule kojima se karakterišu njihove performanse i koje će se koristiti u sledećem poglavlju za poreñenje performansi više lukap algoritama. i) FIPL algoritam FIPL (Fast Internet Protocol Lookup) algoritam je zasnovan na tzv. TB (Tree Bitmap) tehnici [63], [66]. Ideja TB tehnike je da prevaziñe problem nevidljivih internih čvorova tj. čvorova iz nivoa koji se ne vide u m-arnom stablu tako što će u svakom čvoru m-arnog stabla čuvati i tzv. interni bitmap koji odgovara tim čvorovima. Time se izbegava i guranje tih čvorova u vidljive nivoe m-arnog stabla. Na slici 4.3.7.1.1 je prikazana struktura jednog čvora. Čvor sadrži dva bitmapa – interni i eksterni. Interni bitmap definiše koji od internih (nevidljivih) čvorova sadrži validan ID izlaznog porta. Osim internih čvorova u interni bitmap se uključuje i sam posmatrani čvor. Uz interni bitmap se čuva i ID pokazivač koji pokazuje na početak bloka memorijskih lokacija u izlaznoj memoriji koja čuva ID-eve izlaznih portova. Taj blok sadrži onoliko memorijskih lokacija koliko ima internih čvorova, pri čemu je svakom internom čvoru dodeljena jedna lokacija u koju se smešta eventualan validan ID izlaznog porta tog čvora. Eksterni bitmap čuva informaciju o postojanju dece dotičnog čvora i uz njega je vezan pokazivač na decu. Deca se čuvaju u sukcesivnim lokacijama, pri čemu pokazivač pokazuje na prvo dete tj. prvu lokaciju memorijskog bloka gde su smeštena deca. Ukoliko nijedno dete ne postoji pokazivač ima tzv. NULL vrednost kojom se označava da deca ne postoje. Ukoliko postoji bar jedno dete rezervišu se resursi za svu decu, tj. veličina rezervisanog memorijskog bloka je jednaka 2! čvorova. FIPL koristi strajd dužine   4 bita, i za svaki podatak u čvoru (interni bitmap, eksterni bitmap, ID pokazivač, pokazivač na decu) koristi 2!  16 bita. Pretraga se sastoji u kretanju kroz m-arno stablo i u svakom čvoru se ispituje interni bitmap u cilju nalaženja čvora sa validnim ID-em izlaznog porta koji se najduže poklapa sa IP adresom za koju se vrši 62 pretraga. Kada se završi pretraga m-arnog stabla, pristupa se lokaciji u izlaznoj memoriji koja odgovara čvoru sa najdužim poklapanjem da bi se pročitao ID izlaznog porta koja predstavlja konačni rezultat lukap funkcije. Slika 4.3.7.1.1. – Struktura jednog čvora u FIPL algoritmu Protok lukap funkcije zavisi od načina implementacije. Ukoliko se svi čvorovi m-arnog stabla nalaze u istoj memoriji onda je protok lukap modula / lukapa po ciklusu takta, gde je  dužina strajda, a  dužina IP adrese, jer je u najgorem slučaju neophodno pristupiti / puta memoriji koja sadrži čvorove m-arnog stabla. Ukoliko se koristi više memorija, tako da svaka od njih čuva jedan nivo m-arnog stabla, onda je moguće implementirati optimalni pajplajn i tada je garantovani protok lukap funkcije jedan lukap po ciklusu takta. Memorijski resursi neophodni za smeštanje čvorova m-arnog stabla ('!() iznose: '!(  ) · 2! · 4 · 2! (4.3.7.1.1) gde je ) broj postojećih nizova od 2! čvorova jer ako bar jedno dete nekog čvora postoji rezerviše se prostor za svu decu. Kao što je rečeno svi podaci čvora (interni bitmap, eksterni bitmap, ID pokazivač, pokazivač na decu) su iste dužine (2!) i ima ih četiri, pa je broj bita koje koristi jedan čvor 4 · 2!. Svaki čvor čiji interni bitmap ukazuje na postojanje bar jednog čvora sa validnim ID-em izlaznog porta rezerviše blok od 2! + 1 lokacija u izlaznoj memoriji, pošto toliko ima internih čvorova kao što se vidi sa slike 4.3.7.1.1. Otuda su memorijski zahtevi izlazne memorije (',-): ',-  . · 2! + 1 · / (4.3.7.1.2) gde je . broj čvorova čiji interni bitmap ukazuje na postojanje bar jednog čvora sa validnim ID-em izlaznog porta, a / predstavlja dužinu ID-a izlaznog porta. 63 U slučaju da postoje eksterni memorijski čipovi na raspolaganju, u prvi eksterni memorijski čip se smešta izlazna memorija jer je ona najveća. U eventualne preostale eksterne memorijske čipove se smeštaju redom smeštaju nivoi m-arnog stabla koji zauzimaju najveće memorijske resurse. Otuda su interni memorijski zahtevi (',)0, ): ',)0,  1 '020 + ',- , &  1 '020 + ',- + 4 ')5,%56 , & 7 1 8 (4.3.7.1.3) pri čemu & predstavlja broj eksternih memorijskih čipova na raspolaganju, '020 predstavlja ukupne memorijske resurse, ')5 je veličina memorije nivoa 9 pri čemu su memorije nivoa sortirane u opadajućem redosledu po veličini, pa tako indeks 9  1 odgovara nivou sa najvećom memorijom. Ukupni memorijski resursi '020 iznose: '020  '!( : ',- (4.3.7.1.4) Iz (4.3.7.1.1) se vidi da je veličina memorije jednog nivoa ')5 : ')5  )5 · 2! · 4 · 2! (4.3.7.1.5) gde je )5 broj postojećih nizova od 2! čvorova nivoa 9. ii) EHAF algoritam EHAF (Efficient Hardware Architecture for Fast IP Lookup) algoritam je prilagoñen za IPv4 adrese i zasnovan je na podeli binarnog stabla na nivoe koji se pretražuju u paraleli [64]. Pri tome je dubina svih nivoa jednaka i iznosi ;  8. pa je ukupan broj nivoa četiri. Svaki nivo sadrži podstabla čiji bitmap vektori definišu koji od čvorova sadrže validan ID izlaznog porta. ID-evi izlaznih portova se čuvaju u izlaznoj memoriji. Arhitektura EHAF algoritma je prikazana na slici 4.3.7.2.1. Prvi nivo sadrži dva podstabla dubine ;<  7, pri čemu se na osnovu vrednosti prvog bita IP adrese odreñuje koje će se od njih pretraživati. Drugi nivo sadrži 2>? podstabala dubine ;<  7 pri čemu se na osnovu prvih ; : 1 bita IP adrese odreñuje koje će se pretraživati. U slučaju prvog i drugog nivoa čuvaju se sva podstabla bez obzira da li je neko od njih prazno, tj. ne sadrži nijedan čvor sa validnim ID-em izlaznog porta. 64 '1' Pok. Bitmap vektor postojanja podstabala Vektor pokazivača '1' Pok. Bitmap vektor postojanja podstabala Vektor pokazivača '1' Pok. Bitmap vektor postojanja grupe podstabala Vektor pokazivača na grupu NIVO 1 NIVO 2 NIVO 3 NIVO 4 Selektor Izlazna memorija Slika 4.3.7.2.1. – EHAF arhitektura U trećem i četvrtom nivou nije ekonomično čuvati sva podstabla (koja su, isto kao i u prva dva nivoa, dubine ;<  7) s obzirom da je njihov broj isuviše velik, pa se onda čuvaju samo neprazna podstabla. Otuda se za podstabla čuva bitmap vektor dužine 2$>? koji definiše postojanje/nepostojanje svih podstabala na trećem nivou. Uz ovaj vektor se čuva i vektor pokazivača koji čuva pokazivače na podstabla trećeg nivoa, u slučaju da podstablo ne postoji onda pokazivač ima NULL vrednost. U slučaju trećeg nivoa se na osnovu prvih 2; : 1 bita odreñuje pozicija u oba vektora i čitaju se podaci na tim pozicijama. Ukoliko se na osnovu pročitanog bita bitmap vektora utvrdi postojanje podstabla onda se ide na lokaciju koja je odreñena pročitanim pokazivačem iz vektora pokazivača na kojoj se nalazi interni bitmap dotičnog podstabla. U slučaju četvrtog nivoa se čuva bitmap vektor dužine 2$>? koji odreñuje postojanje grupe 65 podstabala četvrtog nivoa koja sadrže čvorove sa istih početnih 2; : 1 bita. Takoñe se čuva i vektor pokazivača koji pokazuju na lokacije koje čuvaju bitmape podstabala u okviru grupe. Uz bitmap koji definiše postojanje/nepostojanje podstabala u okviru grupe se čuva i vektor pokazivača na lokacije koje čuvaju neprazna podstabla (ona koja imaju bar jedan čvor sa validnim ID-em izlaznog porta). U slučaju četvrtog nivoa se pretraga vrši tako što se prvo ispita, na osnovu prvih 2; : 1 IP adrese, postojanje grupe podstabala u koju spada podstablo od interesa, pa onda ako grupa postoji se ispita njen bitmap postojanja/nepostojanja podstabala. Ako podstablo postoji onda se preko pokazivača pristupa lokaciji koja sadrži bitmap dotičnog podstabla koje se potom ispituje. Treba primetiti da u slučaju prvog i drugog nivoa nisu korišćeni pokazivači pošto se sva podstabla čuvaju pa su resursi neophodni za smeštanje bitmapa podstabala i ID-eva izlaznih portova unapred rezervisani. Rezultati pretraga svih nivoa se vode na selektor koji selektuje pozitivan rezultat najdubljeg nivoa. Potom se pristupa izlaznoj memoriji da bi se pročitao ID izlaznog porta koji predstavlja konačni rezultat lukapa. Maksimalni i garantovani protok lukapa je jedan rezultat lukapa po jednom ciklusu takta pošto se pajplajn lako implementira u EHAF arhitekturi. Zahtevani memorijski resursi po nivoima ('), ) iznose: ')  2 · 2> + 1 (4.3.7.2.1) ')$  2>? · 2> + 1 (4.3.7.2.2) ')#  2$>? · @1 : Alog$ <2E# FG : <2E# · 2> + 1 (4.3.7.2.3) ')H  2$>? · @1 : Alog$ I<2EH FG : I<2EH · 2> · @1 : Alog$ <2EH FG : :<2EH · 2> + 1 (4.3.7.2.4) gde su <2E# i <2EH broj nepraznih podstabala na nivoima 3 i 4, respektivno, I<2EH predstavlja broj grupa podstabala četvrtog nivoa koja sadrže bar jedno neprazno podstablo. Zahtevani memorijski resursi za izlaznu memoriju (',-) iznose: ',-  J2 : 2>? : <2E# : <2EH K · 2> + 1 · / (4.3.7.2.5) gde je / dužina ID-a izlaznog porta. U slučaju da postoje eksterni memorijski čipovi na raspolaganju, u prvi eksterni memorijski čip se smešta izlazna memorija jer je ona najveća. U eventualne preostale eksterne memorijske čipove se redom smeštaju vektori pokazivača na podstabla trećeg 66 nivoa i grupe podstabala četvrtog nivoa, respektivno. Memorije koje sadrže bitmape podstabala zahtevaju prevelike magistrale podataka pa se zato one ne izmeštaju u eksterne memorije. Otuda su interni memorijski zahtevi (',)0, ): ',)0,  L '020 + ',- , &  1 '020 + ',- + '? · @1 : Alog$ <2E# FG (4.3.7.2.8) Iz (4.3.7.2.4) se vidi da je veličina memorije pokazivača na grupe podstabala četvrtog nivoa '? · @1 : Alog$ I<2EH FG. (4.3.7.2.9) iii) POLP algoritam POLP (Parallelized Optimal Linear Pipeline) algoritam se zasniva na upotrebi tehnika pajplajna i paralelizacije kao što se i vidi iz njegovog naziva [62]. Arhitektura POLP algoritma je prikazana na slici 4.3.7.3.1. Ideja POLP algoritma je da čvorovi binarnog stabla na dubini ; predstavljaju korene podstabala originalnog binarnog stabla. Zatim se tako definisana podstabla rasporede po pajplajnovima kojih ima N, tako da svaki pajplajn sadrži podjednak broj čvorova. Svaki pajplajn se sastoji od O faza kroz koje prolazi pretraga u okviru pajplajna. Svaka faza sadrži memoriju koja čuva čvorove podstabala. Da bi memorije po fazama imale jednake kapacitete, što olakšava implementaciju, vrši se rasporeñivanje čvorova podstabala rasporeñenih u dotični pajplajn tako da svaka faza sadrži podjednak broj čvorova. Pri tome je jedino važno da deca jednog čvora mogu da budu smeštena samo u fazama posle faze u kojoj je smešten dotični čvor. Pri tome deca ne moraju da budu u prvoj sledećoj fazi, već mogu da budu smeštena i u neku udaljeniju fazu i ta osobina omogućava ravnomerno rasporeñivanje 67 čvorova po fazama. Jedna memorijska lokacija predstavlja jedan čvor podstabla. U okviru memorijske lokacije tj. čvora se čuvaju pokazivač na decu i binarni indikator da li taj čvor sadrži validan ID izlaznog porta ili ne. Pokazivač se sastoji od dve informacije – faza u kojoj se nalaze deca i adresa lokacije u memoriji te faze gde se nalazi prvo dete (drugo dete je smešteno na sukcesivnu lokaciju). Svakom pajplajnu je pridružena jedna izlazna memorija kao što je prikazano na slici 4.3.7.3.1 radi ostvarivanja maksimalnog protoka lukapa. Izlazne memorije čuvaju ID-eve izlaznih portova čvorova podstabala smeštenih u odgovarajućim pajplajnovima. Prefiksi kraći od ; bita se guraju u čvorove nivoa ;, tj. korene odgovarajućih podstabala. Slika 4.3.7.3.1. – Arhitektura POLP algoritma Pretraga se vrši na sledeći način. Odredišna IP adresa se propušta kroz jedan od usmeravača koji na osnovu prvih ; bita IP adrese odreñuje u kom pajplajnu se nalazi podstablo od interesa. Zatim se preostali biti IP adrese prosleñuju ka redu za čekanje odgovarajućeg pajplajna. Red za čekanje je neophodan pošto može doći do kolizije tj. da dva ili više usmeravača istovremeno usmere pretragu u isti pajplajn. Otuda je broj usmeravača jednak N jer veći broj bi sigurno doveo do kolizija, a manji bi ostvarivao manji maksimalan protok lukap funkcije. Pretraga u pajplajnu se zasniva na kretanju kroz binarno podstablo koje se odvija prolaskom kroz faze. Kroz faze se prolazi besposleno ukoliko one ne sadrže čvor od interesa, a u suprotnom se čvor od interesa ispituje i odreñuje da li sadrži validan ID izlaznog porta i da li postoje deca čvora. Na kraju se u izlaznoj memoriji koja čuva ID-eve izlaznih portova pristupa lokaciji koja odgovara zadnjem ispitanom čvoru, koji sadrži validan ID izlaznog porta, iz pajplajna. Kada pretraga preñe iz jedne faze u narednu, sledeća pretraga dolazi u datu fazu pa je pajplajn optimalan, a pri tome svi pajplajnovi mogu da se pretražuju istovremeno u paraleli, što znači da N pretraga može da otpočne u isto vreme. Maksimalan protok 68 lukap funkcije je N rezultata pretrage po jednom ciklusu takta. Ali, u najgorem slučaju svi usmeravači mogu da prosleñuju pretrage u isti pajplajn pa je u najgorem slučaju protok lukap modula jednak jedan lukap po jednom ciklusu takta. Što se tiče memorijskih resursa svi blokovi u POLP arhitekturi sadrže memorije. U usmeravačima, njihove memorije čuvaju za svako podstablo informaciju u koji pajplajn je ono rasporeñeno. Broj podstabala je 2>, a broj bita neophodan za identifikaciju pajplajna je Plog$ NQ, gde P Q označava prvi veći ceo broj. Tako su zahtevani memorijski resursi u usmeravačima ('R): 'R  N · 2> · Plog$ NQ (4.3.7.3.1) Memorija u okviru jedne faze pajplajna se dimenzioniše prema najgorem slučaju tj. najvećem broju čvorova . rasporeñenih u okviru jedne faze pri čemu se u obzir uzimaju sve faze svih pajplajnova. Kao što je rečeno jedna memorijska lokacija sadrži pokazivač i binarnu indikaciju o tome da li je čvoru pridružen validan ID izlaznog porta. Pokazivač se sastoji od dva dela pa dužina pokazivača iznosi Plog$O + 1Q :Plog$ .Q, pri čemu prvi član zbira adresira fazu (pošto prva faza ne mora da se adresira jer se od nje kreće, onda je potrebno adresirati samo sledeće faze), a drugi deo zbira adresira lokaciju u memoriji dotične faze. Otuda su zahtevani memorijski resursi neophodni za realizaciju pajplajnova ('<): '<  N · O · . · Plog$O + 1Q : Plog$ .Q : 1 (4.3.7.3.2) Memorije na izlazu pajplajna (izlazne memorije) čuvaju ID-eve izlaznih portova, pri čemu broj lokacija jedne izlazne memorije mora biti jednak broju čvorova u okviru pajplajna za koji je vezana. Pošto bilo koja lokacija u memoriji faze može biti zauzeta nekim čvorom podstabla i pošto svaki čvor podstabla može da sadrži validan ID izlaznog porta, memorijski resursi izlaznih memorija (',-) iznose: ',-  N · O · . · / (4.3.7.3.3) gde je / dužina ID-a izlaznog porta. Prilikom razmatranja internih memorijskih resursa, neophodno je prvo utvrditi koje je memorijske blokove najbolje izmestiti u raspoložive eksterne memorijske čipove. U slučaju POLP-a najbolje je izmestiti izlazne memorije u eksterne čipove pošto su one najveće. U slučaju da je broj eksternih memorijskih čipova veći od broja izlaznih memorija onda se sledeće izmeštaju memorije unutar pojedinih faza, pri čemu treba 69 napomenuti da to izmeštanje neće značajno uštediti interne memorijske resurse. Razlog je što su memorije unutar faza znatno manjih kapaciteta u odnosu na izlazne memorije. Interni memorijski zahtevi (',)0, ) iznose: ',)0,  S'020 + & · ',- , & T N '020 + ',- + & + N'U , & 7 N 8 (4.3.7.3.4) pri čemu & predstavlja broj eksternih memorijskih čipova na raspolaganju, '020 predstavlja ukupne memorijske resurse, ',- je veličina jedne izlazne memorije, a 'U predstavlja veličinu memorije jedne faze. Ukupni memorijski resursi '020 iznose: '020  'R : '< : ',- (4.3.7.3.5) Iz (4.3.7.3.3) se vidi da je: ',-  O · . · / (4.3.7.3.6) Iz (4.3.7.3.2) se vidi da je: 'U  . · Plog$O + 1Q : Plog$ .Q : 1 (4.3.7.3.7) iv) Stablo sa prioritetima Stablo sa prioritetima je zasnovano na ideji da se prazni čvorovi u podstablima popune sa nekim od čvorova sa validnim ID-em izlaznog porta koji predstavljaju njihove potomke [76]. Pri tome, selektuje se onaj potomak sa validnim ID-em izlaznog porta koji se nalazi na najvećoj dubini stabla jer on ima najveći prioritet tj. ako se IP adresa poklopi sa njim pretraga se može okončati. Na ovaj način se smanjuje ukupna dubina binarnog stabla i izbegava se problem praznih čvorova koji se koriste samo za prolaz kroz stablo tj. formiranje puta kroz stablo. Meñutim, sada čvorovi pored ID-a izlaznog porta i dva pokazivača (na levo i desno dete) moraju da sadrže i dodatne podatke. Jedan podatak je binarni indikator da li je u pitanju pomereni čvor (tzv. čvor sa prioritetom) ili ne, a drugi podatak je vrednost samog prefiksa. Pošto se može desiti da se pomeri i čvor sa najveće dubine binarnog stabla mora se rezervisati  bita za čuvanje prefiksa, gde je  dužina prefiksa. Primer formiranja stabla sa prioritetima je prikazan na slici 4.3.7.4.1, pri čemu su sa tamnijom bojom prikazani čvorovi sa prioritetom (tj. premešteni čvorovi). 70 Slika 4.3.7.4.1. – Formiranje stabla sa prioritetima Stablo sa prioritetima se formira na jednostavan način. Ide se redom po nivoima binarnog stabla. Za svaki prazan čvor na koji se naiñe traži se njegov potomak sa validnim ID-em izlaznog porta koji se nalazi na najvećoj dubini, a takav potomak sigurno mora da postoji jer u suprotnom dotični prazni čvor ne bi ni postojao u stablu. Tako npr. za prazan čvor koji odgovara poziciji prefiksa 0* potomak sa validnim ID-em izlaznog porta koji je na najvećoj dubini je čvor koji odgovara prefiksu 01001* i on se pomera u prazan čvor. Na sličan način se popunjavaju i ostali prazni čvorovi. Prazni čvorovi koji ostanu da vise tj. nemaju potomaka sa validnim ID-em izlaznog porta zbog premeštanja se takoñe brišu iz stabla. Na ovaj način se optimizuje ukupan broj čvorova u binarnom stablu, a i smanjuje se broj nivoa. Pretraga se vrši kretanjem kao po binarnom stablu pri čemu ukoliko se utvrdi da je trenutni čvor onaj sa prioritetom vrši se poreñenje prefiksa sa IP adresom. Ako se nañe poklapanje onda je to kraj pretrage pošto boljeg poklapanja ne može da bude u stablu (jer bi se u suprotnom taj čvor sa 71 boljim poklapanjem nalazio na mestu ispitivanog čvora sa prioritetom) – otuda i naziv čvor sa prioritetom. Na ovaj način se takoñe smanjuje prosečno vreme pretrage. U slučaju kada su svi čvorovi u istoj memoriji protok lukap funkcije u najgorem slučaju iznosi 1/ rezultat lukap funkcije po jednom ciklusu takta, pošto u slučaju da postoji jedna putanja do najveće dubine binarnog stabla na kojoj su svi čvorovi sa validnim ID-em izlaznog porta onda nijedan od tih čvorova ne može biti čvor sa prioritetom pa otuda svi ostaju na svom mestu i mora se proći kroz sve njih ako se vrši pretraga za IP adresu koja odgovara tom putu. Naravno, verovatnoća ovog dogañaja je zanemarljivo mala, ali je sa teoretskog stanovišta garantovani protok 1/. Optimalni pajplajn može da se izvrši u slučaju da se čvorovi svakog nivoa smeštaju u zasebnu memoriju i tada on iznosi jedan rezultat lukapa po jednom ciklusu takta (ali je tada u najgorem slučaju potrebno  memorija). Memorijski resursi neophodni za smeštanje svih čvorova '<( (jedan čvor sadrži ID izlaznog porta, dva pokazivača (jedan na levo i jedan na desno dete), vrednost prefiksa i binarnu indikaciju da li je u pitanju čvor sa prioritetom) iznose: '<(  . · / : 2 · Plog$ .Q :  : 1 (4.3.7.4.1) gde je . ukupan broj čvorova prioritetnog stabla (tj. broj prefiksa u lukap tabeli), a / dužina ID-a izlaznog porta. Broj nivoa stabla sa prioritetom koji utiče na protok lukap funkcije zavisi od rasporeda čvorova originalnog binarnog stabla i njihovog ravnomernog rasporeda po stablu jer npr. videli smo da je dovoljna samo jedna putanja čiji svi čvorovi imaju validan ID izlaznog porta pa da se nijedan čvor sa te putanje ne može premestiti. Da bi se ostvario optimalan pajplajn neophodno je svaki nivo prioritetnog stabla smestiti u zasebnu memoriju, pa u slučaju da postoje eksterni memorijski čipovi na raspolaganju u njih se redom smeštaju nivoi stabla koji zauzimaju najveće memorije. Otuda su interni memorijski zahtevi (',)0, ): ',)0,  '<( + 4 ')5,56 (4.3.7.4.2) pri čemu & predstavlja broj eksternih memorijskih čipova na raspolaganju, ')5 je veličina memorije nivoa 9 pri čemu su memorije nivoa sortirane u opadajućem 72 redosledu po veličini, pa tako indeks 9  1 odgovara nivou sa najvećom memorijom. Iz (4.3.7.3.1) se vidi da je veličina memorije jednog nivoa ')5 : ')5  .5 · / : 2 · Plog$ .Q :  : 1 (4.3.7.4.3) gde je .5 broj čvorova nivoa 9. 4.4. TCAM algoritmi U ovu klasu algoritama spadaju svi oni lukap algoritmi koji koriste TCAM memorije [79]-[85]. TCAM memorije su specijalizovani čipovi razvijeni upravo za primenu u lukapu, kao i inspekciji paketa koja je veoma slična lukapu. Logička šema TCAM memorije je prikazana na slici 4.4.1. Slika 4.4.1. – Logička šema strukture TCAM memorije TCAM memorija se sastoji od niza lokacija, pri čemu se svaka lokacija sastoji od zapisa i komparatora. Ulazni signal se poredi istovremeno na svakoj lokaciji tako što se u komparatoru porede ulazni signal i zapis. Izlaz lokacije predstavlja rezultat komparacije u vidu binarnog signala čija vrednost ‘0’ kazuje da nema poklapanja, odnosno ‘1’ da ima poklapanja. Pošto više zapisa može da se poklapa sa ulaznim signalima, rezultati komparacije sa svih lokacija se vode na koder sa prioritetom koji na svoj izlaz izbacuje indeks lokacije sa poklapanjem najvišeg prioriteta. U slučaju lukapa ulazni signal je ustvari IP adresa, a zapis je ustvari prefiks. TCAM memorija je specifična po tome što bit u zapisu može da ima jednu od tri vrednosti: ‘0’, ‘1’ i ‘X’, pri čemu ‘X’ vrednost predstavlja tzv. ‘don’t care’ vrednost koja u komparaciji uvek daje poklapanje sa ulaznim signalom na poziciji na kojoj se nalazi. Pošto TCAM memorija ima veoma usko polje primene često proizvoñači ne nude samo TCAM memoriju 73 proizvoñačima rutera i svičeva, već složene integrisane čipove koji u sebi, pored TCAM memorije, sadrže i kompletnu logiku za izvršavanje lukapa tj. čipove koji predstavljaju kompletno rešenje. Osnovna implementacija lukapa baziranog na TCAM memoriji je prikazana na slici 4.4.2. U ovoj osnovnoj varijanti u TCAM memoriji se čuvaju svi prefiksi lukap tabele, dok se ID-evi izlaznih portova čuvaju u običnoj memoriji – tipično SRAM memoriji. Pri tome, broj lokacija obe memorije je identičan pa ako je prefiks na lokaciji & TCAM memorije, onda je njegov ID izlaznog porta na lokaciji & SRAM memorije. Lukap se obavlja tako što se IP adresa dovodi na ulaz TCAM memorije, koja nalazi prefiks sa najdužim poklapanjem i vraća indeks lokacije gde je smešten ID izlaznog porta koji odgovara tom prefiksu. Čitanjem dotične lokacije se nalazi ID izlaznog porta kao konačan rezultat pretrage tj. lukapa. Treba napomenuti da su biti prefiksa predstavljeni * upisani sa vrednostima ‘X’ u TCAM memoriju. Kao što se vidi upotreba TCAM memorije je veoma jednostavna i veoma brzo se nalazi rezultat lukapa. Meñutim, postoje i odreñeni problemi u upotrebi TCAM memorija. Prvi problem je cena. TCAM memorije su značajno skuplje od SRAM memorija koje se inače koriste u drugim vrstama lukap algoritama. Takoñe, kapacitet TCAM memorija je mali tako da je problematično smeštanje velikih lukap tabela pošto u osnovnoj varijanti ona treba da smesti sve prefikse, a pri tome širina lokacije mora biti minimalno jednaka dužini IP adrese. Pošto upotreba TCAM memorije podrazumeva istovremenu proveru svih lokacija i njihovo poreñenje sa IP adresom, potrošnja ovakvih čipova je velika i može da ide i preko 10W što predstavlja veliko opterećenje za rutere [82]. Zelene tehnologije su savremeni trend koje imaju za cilj smanjenje potrošnje svih elektronskih ureñaja, samim tim i mrežnih ureñaja. Na primer, u Cisco ruterima velik deo ukupne potrošnje ide na lukap upravo zbog upotrebe TCAM memorija [80]. S druge strane SRAM memorije troše znatno manje snage (manje od 1W), pa su samim tim poželjnije za upotrebu u odnosu na TCAM memorije sa stanovišta potrošnje. Dodatni problem TCAM memorija je sortiranje prefiksa u TCAM memoriji tako da duži prefiksi idu na lokacije višeg prioriteta. U suprotnom, da se ne vrši sortiranje moglo bi doći do grešaka u rezultatima TCAM memorije. Na primer, da je na slici 4.4.2 prefiks 10* stavljen na lokaciju višeg prioriteta u odnosu na prefiks 101*, došlo bi do greške u rezultatu TCAM memorije za sve IP adrese koje počinju sa 101 jer bi se vraćao 74 ID izlaznog porta koji odgovara kraćem prefiksu 10* pošto bi koder sa prioritetom selektovao lokaciju 10* jer je višeg prioriteta. Problem sortiranja može da utiče na efikasno ažuriranje prilikom upisa novih prefiksa ako prefiksi u TCAM memoriji nisu dobro rasporeñeni. Razvijena su brojna unapreñenja osnovne implementacije lukap algoritama baziranih na TCAM memoriji. Unapreñenja za osnovni cilj imaju rešavanje dva osnovna problema TCAM memorije na koja se može uticati – mali kapacitet i velika potrošnja. Otuda lukap algoritmi bazirani na TCAM memoriji imaju za cilj unapreñenje u vidu smanjenja potrošnje ili smanjenja potrebne veličine TCAM memorije. Slika 4.4.2. – Osnovna šema lukap modula baziranog na TCAM memoriji 4.4.1. Optimizacija potrošnje Potrošnja se može smanjiti tako što se ne porede svi prefiksi u lukap tabeli sa IP adresom, već samo deo prefiksa čime se smanjuje ukupna potrošnja jer je samo deo lukap tabele (tj. TCAM memorije) aktiviran prilikom pretrage [79], [81]-[85]. Ovo se postiže podelom prefiksa u tzv. kofe, a kriterijum podele je takav da je svaka kofa definisana sa jednim ili više tzv. pokrivajućih prefiksa. Pokrivajući prefiks je onaj najduži prefiks koji je zajednički grupi prefiksa u kofi koji su predstavljeni dotičnim pokrivajućim prefiksom. Drugim rečima, ako bismo tu grupu prefiksa predstavili u vidu binarnog stabla, njihov pokrivajući prefiks bi bio zajednički predak te grupe prefiksa koji se nalazi na najvećoj dubini stabla. Grupa prefiksa predstavlja deo podstabla originalnog binarnog stabla. Lukap tabela je u ovom slučaju organizovana kao na slici 4.4.1.1. U prvoj fazi se nalazi par TCAM-SRAM memorija, gde se u TCAM memoriji nalaze pokrivajući prefiksi, a u SRAM se nalaze identifikacije kofa koje sadrže grupe prefiksa koje su pokrivene tim pokrivajućim prefiksima. Cilj pretrage u prvoj fazi je da 75 se odredi kofa od interesa koja sadrži prefikse koji predstavljaju kandidate za poklapanje sa datom IP adresom. Druga faza takoñe sadrži par TCAM-SRAM memorija, ali se sada u TCAM memoriji nalaze kofe sa prefiksima, dok SRAM memorija sadrži ID-eve izlaznih portova. Rezultat druge faze predstavlja konačno rešenje lukapa – ID izlaznog porta. Pošto se prva faza koristi za odreñivanje indeksa kofe koja treba da se pretraži, onda se memorije prve faze označavaju sa ITCAM (Index TCAM) i ISRAM (Index SRAM) [79]. Druga faza sadrži krajnji rezultat lukapa pa se memorije druge faze označavaju sa DTCAM (Data TCAM) i DSRAM (Data SRAM) [79]. Navedeni nazivi memorija će se koristiti u nastavku teze. 0 0 0 0 1 11 1 1 1 10 Pokrivajući prefiks Pokrivajući prefiks Pokrivajući prefiks Prefiks * 0* 1* 01* 11* 001* 1001* 1010* 1011* ID izl. porta ID1 ID2 ID3 ID4 ID5 ID6 ID7 ID8 ID9 10* 0* * 0,4 4,3 7,3 1001* 1010* 1011* 10* 001* 01* 0* 11* 1* * ID7 ID8 ID9 ID3 ID6 ID4 ID2 ID5 ID3 ID1 Kofa 1 Kofa 2 Kofa 3 FAZA 1 FAZA 2 ITCAM ISRAM DTCAM DSRAM Slika 4.4.1.1. – Primer organizacije lukap tabele sa TCAM memorijom podeljenom na kofe promenljive veličine DTCAM memorija se može implementirati na dva načina. Prvi način je da se koristi jedna TCAM memorija koja ima osobinu da mogu da se aktiviraju samo pojedini 76 njeni delovi koji ustvari predstavljaju kofe. Drugi način je da se koristi više TCAM memorija manjeg kapaciteta pri čemu svaka ta mala TCAM memorija predstavlja jednu kofu. Kofe se mogu definisati da budu fiksne veličine ili promenljive veličine. U slučaju kada su kofe fiksne veličine, kofe se redom pune prefiksima tako da su u tom slučaju sve kofe sem eventualno poslednje potpuno pune. Iz tog razloga u ovom slučaju jedna kofa može da sadrži više grupa prefiksa tj. da u prvoj fazi postoji više pokrivajućih prefiksa koji pokazuju na istu kofu. Naravno, forsiranje da sve kofe budu potpuno pune može da utiče na povećanje broja pokrivajućih prefiksa u prvoj fazi jer podela na grupe najčešće nije idealna zbog tako strogog kriterijuma, pa neki od predloženih algoritama često ublaže kriterijum popunjavanja kofe do kraja pre prelaska na sledeću. U slučaju kofa promenljive veličine one se projektuju tako da se u svakoj kofi nalazi samo jedna grupa prefiksa tj. u prvoj fazi svaki pokrivajući prefiks pokazuje na različitu kofu. Pri tome se definiše maksimalna veličina kofe kao ograničenje, da bi se unapred definisalo koliko prefiksa može maksimalno ići u jednu kofu. Prilikom rada TCAM algoritama sa kofama postoji mogućnost da ako se pretraga usmeri na neku grupu prefiksa, da se ne nañe rešenje tj. poklapanje, ali da se poklapanje moglo naći u nekoj drugoj grupi prefiksa koja sadrži kraće prefikse i koja se nalazi u nekoj drugoj kofi. Ukoliko grupi prefiksa pripada i pokrivajući prefiks, onda tako nešto ne može da se desi. Otuda se svakoj grupi kojoj ne pripada pokrivajući prefiks (tj. pokrivajući prefiks ne sadrži validan ID izlaznog porta) veštački dodaje pokrivajući prefiks, a njemu se pridružuje ID izlaznog porta prvog njegovog pretka sa validnim ID- em izlaznog porta na putu od dotičnog pokrivajućeg prefiksa do korena stabla u originalnom binarnom stablu. U primeru sa slike 4.4.1.1 su formirane tri kofe, pri čemu je uzeto da su kofe promenljive veličine tako da svakoj kofi odgovara samo jedan pokrivajući prefiks. ISRAM memorija sadrži podatak o početnoj lokaciji kofe i veličini kofe. Pokrivajući prefiks 10* nema validan ID izlaznog porta tako da se njemu veštački pridružuje ID izlaznog porta njegovog pretka 1*, jer se, u suprotnom, za slučaj IP adrese čiji su početni biti 1000 u kofi čiji je pokrivajući prefiks 10* ne bi našlo rešenje, a ono postoji u drugoj kofi koja sadrži prefiks 1*. Može se videti da se u najgorem slučaju aktiviraju maksimalno 4 lokacije u DTCAM memoriji. Imajući u vidu da u primeru postoji 9 prefiksa, osnovna TCAM varijanta bi imala aktivaciju 9 lokacija, pa je ušteda očigledna 77 i u ovom malom primeru. Naravno, ako uzmemo u obzir da se u toku jedne pretrage aktiviraju i 3 lokacije u ITCAM memoriji onda imamo ukupnu aktivaciju od 7 lokacija u toku jedne pretrage u najgorem slučaju. Vidimo da je ostvarena ušteda u odnosu na osnovno rešenje oko 22%. Naravno, u slučaju većih tabela odnos veličina ITCAM memorije i kofa je znatno povoljniji u odnosu na osnovnu varijantu pa su i uštede značajnije i idu i do nekoliko puta manje potrošnje snage u odnosu na osnovnu varijantu. 4.4.2. Optimizacija kapaciteta Pored smanjenja potrošnje lukap algoritama zasnovanih na TCAM memoriji, neophodno je smanjiti i njihov zahtevani kapacitet, pošto je kapacitet TCAM memorije ograničen. Kao što se moglo videti u primeru iz prethodnog odeljka, smanjenje potrošnje ima za cilj smanjenje aktiviranih delova TCAM memorije, ali ukupna veličina je i dalje ista kao i u osnovnoj varijanti. Štaviše, može čak i da bude veća zbog dodavanja pokrivajućih prefiksa ukoliko je to potrebno kao i u primeru sa slike 4.4.4.1 gde je dodat prefiks 10* čime je DTCAM memorija veća nego što bi bila da je korišćena osnovna varijanta. Otuda je bitno voditi računa i o smanjenju traženog kapaciteta TCAM memorije pošto je u pitanju skup resurs. Smanjenje potrebnog kapaciteta TCAM memorije je jedino moguće ako se deo prefiksa smesti van TCAM memorije npr. u SRAM memoriju [79]. Dakle, SRAM memorija bi pored ID-eva izlaznih portova trebalo da čuva i druge informacije. Samim tim neophodne su SRAM memorije koje sadrže duže lokacije. Iz lokacija se podaci čitaju jednim pristupom, pa one omogućavaju brzo čitanje tih dodatnih informacija. Današnje SRAM memorije mogu da imaju i 144b dugačke lokacije [79]. U tom slučaju bi se u TCAM memoriji čuvali pokrivajući prefiksi, a u SRAM memoriji bi se čuvali sami prefiksi zajedno sa svojim ID-evima izlaznih portova. Prefiksi se ne čuvaju u kompletnom formatu, već samo u vidu sufiksa u odnosu na pokrivajući prefiks. Tako da bi svaki prefiks bio predstavljen u vidu: broj bita u sufiksu, konkretna vrednost sufiksa i ID izlaznog porta koji odgovara dotičnom prefiksu. Naravno, pored ovih informacija morala bi da se čuva i informacija o ukupnom broju prefiksa koji su smešteni u lokaciji. Na ovaj način se može značajno smanjiti ukupan kapacitet TCAM memorije. Ako kao primer uzmemo da može biti maksimalno 5 sufiks bita i da ID izlaznog porta sadrži 16 bita, onda je za predstavu jednog prefiksa u SRAM potrebno 16+5+3=24 bita, 78 gde je 3 bita neophodno za kodiranje broja sufiks bita. U tom slučaju za 5 prefiksa je neophodno 120 bita, i pri tome je još neophodno 3 bita za kodiranje ukupnog broja prefiksa u lokaciji. To znači da sa ukupno 123b možemo smestiti 5 prefiksa po lokaciji, što je tehnički ostvarljivo. Tako bi u idealnom slučaju ukupan kapacitet TCAM memorije mogao da se smanji i do 5 puta. Primer ovog metoda je prikazan na slici 4.4.2.1, pri čemu je korišćena ista lukap tabela kao u primeru sa slike 4.4.1.1. U primeru je uzeto da se može smestiti do 4 prefiksa po jednoj lokaciji tako da su pokrivajući prefiksi isti kao i u primeru sa slike 4.4.1.1. Takoñe je uzeto 3 bita za kodiranje dužine sufiksa. U SRAM lokacijama su prikazane samo informacije od značaja, neiskorišćeni biti na krajevima lokacija nisu prikazani. Važna napomena je da i ovde kao u slučaju algoritama zasnovanih na TCAM, a koji se bave uštedom potrošnje snage, ukoliko pokrivajući prefiks nema validan ID izlaznog porta onda mora da se doda u SRAM lokaciju pri čemu mu se pridružuje ID izlaznog porta od njegovog najbližeg pretka sa validnim ID-em izlaznog porta. Kombinacijom prethodno izloženih tehnika za uštedu potrošnje snage i smanjenja potrebnog kapaciteta TCAM memorija se unapreñuju njihove performanse u oba aspekta - potrošnji snage i zahtevanim memorijskim resursima. Slika 4.4.2.1. – Primer organizacije lukap tabele zasnovane na TCAM gde su prefiksi smešteni u SRAM memoriju 4.4.3. Predstavnici TCAM lukap algoritama U okviru ovog odeljka će biti predstavljeni i analizirani najpoznatiji predstavnici TCAM lukap algoritama. Pri tome treba napomenuti da su TCAM memorijski resursi tretirani kao interni memorijski resursi jer TCAM memorije u stvari predstavljaju specijalizovane integrisane čipove poput ASIC-a. i) Osnovni TCAM algoritam Implementacija osnovnog TCAM algoritma je bila prikazana na slici 4.4.2. Najpre se TCAM memorija koristi za odreñivanje prefiksa koji se najduže poklapa sa 79 zadatom IP adresom, a onda se u SRAM memoriji pročita ID izlaznog porta koji je pridružen dotičnom prefiksu. Pri tome je adresa lokacije u SRAM memoriji kojoj se pristupa jednaka adresi lokacije u TCAM gde je nañeno najduže poklapanje. Protok lukap modula je jedan lukap po jednom ciklusu takta jer se može implementirati optimalni pajplajn. Broj zapisa u TCAM memoriji je jednak broju prefiksa u lukap tabeli. Pri tome se širina jedne lokacije u TCAM memoriji mora dimenzionisati prema najgorem slučaju, odnosno mora biti jednaka dužini IP adrese koja iznosi  bita. SRAM sadrži samo ID-eve izlaznih portova pa je širina lokacije u SRAM memoriji jednaka dužini ID- a izlaznog porta /. Na osnovu toga zahtevani memorijski resursi TCAM memorije ('0) iznose: '0  < ·  (4.4.3.1.1) gde je < broj postojećih prefiksa u lukap tabeli. Zahtevani memorijski resursi SRAM memorije ('() iznose: '(  < · / (4.4.3.1.2) Sa slike 4.4.2 se može videti da je potreban samo jedan eksterni memorijski čip koji bi smeštao ID-eve izlaznih portova i tada su interni memorijski zahtevi ',)0, jednaki zahtevanom kapacitetu TCAM memorije '0: ',)0,  '0 , &  1 (4.4.3.1.3) gde je & broj eksternih memorijskih čipova na raspolaganju. Očigledno je iz (4.4.3.1.3), odnosno slike 4.4.2, da u osnovnom TCAM algoritmu nema smisla uvoditi više od jednog eksternog memorijskog čipa, pošto se TCAM memorija zbog svoje složenosti tretira kao interna memorija, kao što je rečeno u uvodnom delu odeljka 4.4.3. ii) TCAM algoritam sa kofama promenljive veličine Primer rada ovog algoritma je prikazan na slici 4.4.1.1. Cilj algoritma je smanjenje potrošnje koju izaziva upotreba TCAM memorije tako što će se broj lokacija koje se aktiviraju u TCAM memoriji smanjiti [79], [82], [84]. Taj efekat se postiže smeštanjem prefiksa u kofe sa prefiksima koji se zajedno aktiviraju, a koje su u ovom slučaju promenljive veličine. Pri tome se definiše maksimalna veličina kofe V koja definiše maksimalan broj prefiksa po kofi. U ovom algoritmu postoje dve faze pretrage, pri čemu svaka faza sadrži po jednu TCAM i SRAM memoriju. ITCAM memorija čuva 80 tzv. pokrivajuće prefikse koji identifikuju kofe, a ISRAM memorija čuva pokazivače na kofe koji se sastoje od dve informacije – pokazivač na početak kofe i veličina kofe. Rezultat pretrage u prvoj fazi daje pokazivač na kofu koju treba pretražiti. U drugoj fazi, DTCAM memorija sadrži kofe sa prefiksima, i pretražuje se samo ona kofa koja je odreñena rezultatom pretrage u prvoj fazi. Kao rezultat pretrage kofe dobija se adresa u DSRAM memoriji koja sadrži ID izlaznog porta koji odgovara najdužem poklapajućem prefiksu i koja predstavlja konačni rezultat lukapa. Maksimalna moguća dužina pokrivajućeg prefiksa << je odreñena maksimalnom veličinom kofe. Najgori slučaj je kada se na dnu binarnog stabla nalazi potpuno popunjeno podstablo dubine ;. Tada to podstablo ima ukupno (uključujući i koren) 2>? + 1 čvorova. Da bi ovo podstablo stalo u kofu čiji bi pokrivajući prefiks bio koren dotičnog podstabla neophodno je da bude ispunjen uslov V  2>? + 1, odnosno ; T log$V : 1 + 1, pri čemu treba uzeti u obzir da je ; ceo broj. To znači da čvorovi iz poslednjih ; + 1 nivoa originalnog binarnog stabla nikako ne mogu biti pokrivajući prefiksi. Otuda je maksimalna dužina pokrivajućeg prefiksa <<: <<   + Wlog$V : 1 + 1X : 1 (4.4.3.2.1) pri čemu W X označava prvi ceo broj manji ili jednak od proračunate vrednosti. Iz toga sledi da je širina lokacije u ITCAM jednaka <<, dok je širina jedne lokacije u DTCAM i dalje  jer ona čuva prefikse unete u lukap tabelu. Otuda zahtevani memorijski resursi za ITCAM i DTCAM memorije (',0 i 'E0, respektivno) iznose: ',0  M · << 'E0   · 4 <,YZ,6 (4.4.3.2.2) gde je M broj kofa (odnosno pokrivajućih prefiksa), a <, broj prefiksa u kofi &. Pri tome treba imati na umu da broj prefiksa u DTCAM memoriji može da bude veći od ukupnog broja prefiksa unetih u lukap tabelu zbog toga što se mogu u DTCAM memoriju dodati i neki pokrivajući prefiksi koji ne pripadaju skupu prefiksa unetih u lukap tabelu. SRAM memorije imaju isti broj lokacija kao i TCAM memorije s kojima su upareni u okviru odgovarajuće faze. Zahtevani memorijski resursi za ISRAM i DSRAM memorije (',( i 'E(, respektivno) iznose: 81 ',(  M · [\log$ 4 <,YZ,6 ] : Plog$ VQ^ 'E(  / · 4 <,YZ,6 (4.4.3.2.3) gde je / dužina ID-a izlaznog porta. Jedna memorijska lokacije ISRAM memorije sadrži pokazivač na početak kofe u DTCAM memoriji i veličinu same kofe, a veličine ovih delova su redom članovi sume u zagradi izraza za ',(. DSRAM čuva samo ID-eve izlaznih portova pa je širina jedne njene lokacije /. Iz date analize se vidi da su potrebna dva eksterna memorijska čipa za izmeštanje svih memorijskih resursa koji nisu obuhvaćeni TCAM memorijama. U slučaju da je na raspolaganju samo jedan eksterni memorijski čip tada se u njega izmešta DSRAM pošto on zahteva veći kapacitet, a ISRAM bi se morao implementirati u okviru integrisanog čipa u kom je smeštena kontrolna logika algoritma. Na osnovu navedenog interni memorijski resursi (',)0, ) su: ',)0,  _',0 : 'E0 : ',(, &  1 ',0 : 'E0 , &  2 8 (4.4.3.2.4) iii) M-12Wb algoritam Cilj M-12Wb (Many-1 2-Level TCAM with Wide Memory Lookup) algoritma je da se minimizuju TCAM memorijski resursi, a da pri tome i potrošnja bude smanjena u odnosu na osnovnu TCAM arhitekturu [79]. Kao što smo videli u prethodno opisana dva algoritma, svi postojeći prefiksi se smeštaju u TCAM memoriju. Štaviše, u TCAM algoritmu sa kofama promenljive veličine su ti resursi čak i veći jer se pored postojećih prefiksa u TCAM memorije smeštaju i pokrivajući prefiksi. Ovde se primenjuje koncept prikazan na slici 4.4.2.1 prema kome se deo prefiksa smešta u SRAM memoriju sa dugačkim lokacijama. Arhitektura M-12Wb algoritma je prikazana na slici 4.4.3.3.1. Ideja je da se originalno binarno stablo podeli na podstabla, pri čemu se formiraju grupe podstabala. Svaka grupa podstabala je predstavljena pokrivajućim prefiksom koji predstavlja zajedničkog pretka na najvećoj dubini svih podstabala iz grupe. Pokrivajući prefiksi se smeštaju u ITCAM memoriju, a koreni podstabala se smeštaju u ISRAM memoriju. U ISRAM memoriji je svakom korenu podstabla pridružena i identifikacija kofe u 82 DTCAM memoriji. Cilj pretrage prve faze je odreñivanje kofe u DTCAM memoriji koja sadrži prefikse podstabla u kom treba da se izvrši pretraga za prefiksom koji se najduže poklapa sa datom IP adresom. DTCAM memorija je podeljena na kofe fiksne veličine. Podstabla se mapiraju na kofe, pri čemu više podstabala može da bude mapirano na istu kofu. U kofi se čuvaju korenovi delova podstabala koji su mapirani na kofu, a u odgovarajućim DSRAM lokacijama se čuvaju sami prefiksi u vidu sufiksa u odnosu na odgovarajuće korene delova podstabala. Pri tome se uz prefikse u DSRAM čuvaju i ID-evi izlaznih portova koji i predstavljaju konačni rezultat lukapa. Prilikom pretrage odgovarajuće kofe u DTCAM memoriji se odreñuje deo podstabla u kom se nalazi najduži poklapajući prefiks, a zatim se u odgovarajućoj lokaciji DSRAM memorije nalazi najduže poklapajući prefiks i njegov ID izlaznog porta koji predstavlja konačni rezultat lukapa. Današnje SRAM memorije mogu da imaju i do 144b dugačke lokacije [79]. Dugačke lokacije omogućavaju smeštanje veće količine informacija. ISRAM u svakoj svojoj lokaciji čuva nekoliko korena podstabala, čime se smanjuje kapacitet ITCAM memorije. DSRAM u svakoj svojoj lokaciji čuva nekoliko čvorova, pa je samim tim smanjen kapacitet DTCAM memorije. Očigledno, upotrebom SRAM memorija dugačkih lokacija je značajno smanjena veličina TCAM memorija, pri čemu je izvršena i ušteda po pitanju potrošnje. Širina lokacije ITCAM memorije je jednaka maksimalnoj dužini pokrivajućeg prefiksa << i može se koristiti izraz (4.4.3.2.1) izveden u prethodnom pododeljku 4.4.3.2. Za širinu lokacije DTCAM memorije <<$ se može koristiti sličan izraz: <<$   + Wlog$. : 1 + 1X : 1 (4.4.3.3.1) gde je . minimalan broj čvorova koji stanu u jednu lokaciju DSRAM memorije. Sa stanovišta dužine SRAM lokacije (, što je duža to će više korena podstabala stati u nju u prvoj fazi, odnosno prefiksa u drugoj fazi pa će samim tim biti i manji memorijski resursi TCAM memorija. Naravno, ograničenje širine lokacije SRAM memorije je tehničke prirode. Zahtevani memorijski resursi za ITCAM i DTCAM memorije (',0 i 'E0, respektivno) iznose: ',0  << · << 'E0  M · V · <<$ (4.4.3.3.2) 83 gde je << broj pokrivajućih prefiksa, a M broj kofa u TCAM memoriji druge faze. Zahtevani memorijski resursi za ISRAM i DSRAM memorije (',( i 'E(, respektivno) iznose: ',(  << · ( 'E(  M · V · ( (4.4.3.3.3) Slika 4.4.3.3.1. – Arhitektura M-12Wb algoritma Iz date analize se vidi da su potrebna dva eksterna memorijska čipa za izmeštanje svih memorijskih resursa koji nisu obuhvaćeni TCAM memorijama. U slučaju da je na raspolaganju samo jedan eksterni memorijski čip tada se u njega izmešta DSRAM pošto on zahteva veći kapacitet. Na osnovu navedenog interni memorijski resursi (',)0, ) su: ',)0,  _',0 : 'E0 : ',(, &  1 ',0 : 'E0 , &  2 8 (4.4.3.3.4) pri čemu & predstavlja broj eksternih memorijskih čipova na raspolaganju. Očigledno je iz (4.4.3.3.4), odnosno slike 4.4.3.3.1, da u slučaju M-12Wb algoritma nema smisla uvoditi više od dva eksterna memorijska čipa, pošto se TCAM memorije zbog svoje složenosti tretiraju kao interne memorije, kao što je rečeno u uvodnom delu odeljka 4.4.3. 4.5. Algoritmi bazirani na heširanju Heš funkcije vrše kompresiju podataka. One se koriste za preslikavanje podataka iz prostora veće dimenzije u prostor manje dimenzije. Spektar primene heš funkcija je veoma širok. One se koriste npr. u bazama podataka, za mapiranje rečnika, u kriptografiji, itd. U zavisnosti od primene varira i njihova kompleksnost. Kompleksnost 84 heš algoritama je najveća u slučaju kriptografske primene. S druge strane, u slučaju lukap algoritama mogu da se koriste i jednostavne heš funkcije, po cenu njihovih lošijih performansi. Zahtevi koje heš funkcija mora da zadovoljava u slučaju lukap algoritama su: • svi biti ulaznog podatka treba da se koriste unutar heš funkcije • sve izlazne vrednosti moraju da imaju podjednaku verovatnoću pojavljivanja • ulazni podaci bliskih vrednosti ne smeju da daju izlazne rezultate bliskih vrednosti Prvi uslov sprečava da prefiksi koji se razlikuju samo u pozicijama bita koji se ne koriste, ne mapiraju na isti izlazni rezultat heš funkcije. Pri tome je važno napomenuti da ulazni podatak mora da bude konstantne dužine. U suprotnom, ako su podaci različite (promenljive) dužine prvi uslov ne bi bio ispunjen ili heš funkcija ne bi mogla da se izračuna. U slučaju ulaznog podatka čiji je broj bita veći od broja bita koji ulaze u proračun heš funkcije onda svi njegovi biti ne bi bili iskorišćeni pa prvi uslov ne bi bio ispunjen. S druge strane, ako bi se heš funkcija dimenzionisala po ulaznom podatku sa najvećim brojem bita, onda se javlja problem da u slučaju kraćih ulaznih podataka pojedini biti nisu definisani pa heš funkcija ne može da se izračuna. Drugi uslov je bitan da se prefiksi pravilno rasporede po izlaznom prostoru. S obzirom da se ulazni prostor komprimuje na manji izlazni prostor, očigledno je da postoji verovatnoća da se više ulaznih podataka mapira na isti izlazni rezultat. Ovaj dogañaj da za dva različita ulazna podatka heš funkcija generiše isti izlazni rezultat se naziva kolizija. Drugi uslov minimizuje verovatnoću kolizije. Treći uslov je bitan pošto su često ulazni podaci meñusobno bliski pa je bitno da u izlaznom prostoru budu meñusobno udaljeniji da bi se smanjila verovatnoća kolizije. Osnovna varijanta lukap algoritma baziranom na heš funkciji je data na slici 4.5.1 [86]. Pošto postoji zahtev da ulazni podatak bude konstantne dužine, mora da se definiše heš funkcija za svaku moguću dužinu prefiksa. U primeru sa sike 4.5.1 je prikazan deo lukap tabele koja sadrži prefikse dužine ,. Heš funkcija kao ulaz uzima odgovarajući broj početnih bita IP adrese (u primeru sa slike 4.5.1 prvih , bita) i računa lokaciju početka liste prefiksa koji su mapirani na isti heš. Jedna memorijska lokacija može da sadrži jedan ili više mapiranih prefiksa, u cilju povećanja brzine pretraživanja liste. Na slici 4.5.1.a je prikazan slučaj gde je u jednoj lokaciji smešten samo jedan 85 prefiks sa svojim ID-em izlaznog porta uz pokazivač na sledećeg člana liste. Memorija je podeljena na dva dela, prvi deo je rezervisan za prve članove liste koji su indeksirani rezultatom heš funkcije, a drugi deo sadrži ostale članove listi na koje pokazuju pokazivači članova liste koji im prethode. a) b) Slika 4.5.1. – a) Osnovni lukap heš algoritam; b) Lukap heš algoritam kod kojeg su izdvojeni pokazivači na prve članove liste Da bi se smanjio broj kolizija, neophodno je da prostor koji adresira heš funkcija bude značajno veći od broja prefiksa. U tom slučaju velik broj lokacija u delu memorije rezervisanom za početne članove listi neće biti iskorišćen. Stoga je efikasnije sa stanovišta ukupnih memorijskih resursa koristiti dve memorije. Prvu memoriju adresira heš funkcija i u njoj se čuvaju samo pokazivači na prve članove listi. Druga memorija se koristi za čuvanje samih članova liste. Ovaj slučaj sa dve memorije je prikazan na slici 4.5.1.b. Na ovaj način je izbegnuto nepotrebno trošenje memorijskih resursa tako što je smanjena širina lokacija koje se ne bi uopšte koristile, a pri tome njihov broj ostaje isti kao u primeru sa slike 4.5.1.a, pa je ušteda očigledna. U primeru sa slike 4.5.1 se podrazumeva da se sve dužine prefiksa ispituju u paraleli. To podrazumeva da za svaku 86 dužinu prefiksa postoji posebna memorija sa listama mapiranih prefiksa odgovarajućih dužina. Taj broj memorija može da predstavlja problem, pa se u nekim varijantama sve liste svih dužina prefiksa čuvaju u istoj memoriji. Tada se po principu binarne pretrage pretražuju dužine pojedinačno dok se ne doñe do rešenja (u najgorem slučaju posle log$  pokušaja, gde je  dužina IP adrese tj. maksimalna moguća dužina prefiksa). U ovom slučaju se uz postojeće prefikse moraju zapisivati i pomoćne informacije koje usmeravaju pretragu na veću ili manju dužinu, što uz usporavanje pretrage predstavlja dodatan problem jer se povećavaju memorijski zahtevi. Pomoćne informacije su neophodne jer u slučaju neuspeha pretrage na nekoj dužini , treba znati da li da se pretraga usmeri ka većim ili manjim dužinama prefiksa. Dobra osobina heš funkcija je što se u jednom koraku dobija rezultat heš funkcije, ali mana je što postoji mogućnost kolizije pa je potrebno čuvati kompletnu vrednost prefiksa da bi bili sigurni da traženi prefiks zaista i postoji, što povećava memorijske zahteve. Takoñe, zbog mogućnosti kolizije potrebno je u najgorem slučaju i više memorijskih pristupa da bi ispitali sve mapirane prefikse koji su u koliziji što usporava pretragu, i otežava uvoñenje tehnika poput pajplajna za ubrzanje lukapa. Veliki problem je i što se mora formirati heš funkcija za svaku dužinu prefiksa, a njih ima mnogo, naročito u IPv6 slučaju. Otuda se često koristi tehnika guranja prefiksa na odreñeni manji skup dužina da bi se smanjio broj potrebnih heš funkcija i memorija [88]. Meñutim, posledica guranja je povećanje broja prefiksa koje treba mapirati čime se značajno povećavaju i memorijski zahtevi, ali i verovatnoća kolizija. Otuda se heš funkcije često koriste u kombinaciji sa drugim klasama lukap algoritama, da bi se s jedne strane iskoristila dobra osobina jednostavnog i brzog računanja heš funkcije, a s druge strane da bi se osobinama drugih klasa smanjile mane heš funkcija [89]. 4.5.1. Blum filtri Da bi se prevazišli problemi kolizije u osnovnoj varijanti lukap algoritma baziranog na heš funkciji, uvedeni su lukap algoritmi bazirani na tzv. Blum filtrima [86], [90]. Blum filtre je prvi predložio Burton Howard Bloom, pa su po njemu i dobili naziv [91]. Blum filtri su memorijski efikasna struktura koja se koristi za ispitivanje da li je neki element član skupa [92]. Osnovna ideja Blum filtara je da se koristi `U heš funkcija koje treba da daju `U indeksa. Kada se upisuje podatak u takvu strukturu na 87 svaku od `U proračunatih pozicija (indeksa) se upisuje binarna 1. Otuda Blum filtar daje strukturu koja veoma brzo proverava postojanje nekog podatka u tabeli, što je osnovna prednost Blum filtara. Naime, kad se želi proveriti postojanje nekog podatka, samo se proračuna `U indeksa i ukoliko se na svakoj od pozicija nalazi binarna jedinica onda je velika verovatnoća da dotični podatak postoji u tabeli. U slučaju kada je unet velik broj podataka u tabelu može da doñe do generisanja ’lažno pozitivno’ rezultata, koji kaže da podatak postoji u tabeli, a u suštini on se ne nalazi u tabeli. Ovo se dešava zato što drugi podaci koji su uneti u tabelu generišu binarne jedinice na pozicijama koje odgovaraju dotičnom podatku za koji je dobijen ’lažno pozitivan’ rezultat. S druge strane, ukoliko se bar na jednoj poziciji nalazi binarna 0, onda podatak sigurno ne postoji. Blum filtri su popularni jer daju efikasnu strukturu po pitanju memorijskih zahteva. Pri tome u zavisnosti od očekivanog broja podataka koji će se uneti u tabelu treba projektovati broj heš funkcija i broj lokacija (indeksa) koje predstavljaju rezultat tih heš funkcija. Kvalitetnim izborom tih parametara se verovatnoća generisanja ’lažno pozitivnog’ rezultata može smanjiti na prihvatljivu vrednost, a da pri tome memorijski zahtevi ostanu prihvatljivi. Meñutim, problem predstavlja brisanje podataka koje je praktično nemoguće, sem ako se ne čuvaju dodatne informacije. Iz tog razloga se u lukap algoritmima koriste tzv. Blum filtri sa brojanjem [86]. U slučaju Blum filtara sa brojanjem se umesto binarnih vrednosti koriste brojači za odreñivanje postojanja podataka u tabeli. Svakom indeksu je dodeljen brojač umesto binarne vrednosti. Svaki put kad se upisuje novi podatak brojači na proračunatim lokacijama se inkrementiraju, a sam podatak se dodaje u listu svake lokacije. Na slici 4.5.1.1 je prikazan primer dodavanja tri prefiksa, pri čemu je u primeru uzeto da je `U  3. Kada se vrši pretraga, prvo se ispituje da li su brojači na svim proračunatim lokacijama različiti od 0. Ako jesu onda se vrši pretraga u listi koja odgovara lokaciji sa najmanjom vrednošću brojača, jer ta lista ima minimalan broj elemenata. Problem ovakve realizacije je što svakom prefiksu odgovara `U kopija u tabeli, pri čemu se za svaki element u suštini vrši pretraga samo jedne liste u kojoj je smešten (ona sa najmanjom vrednošću brojača), što predstavlja neefikasno korišćenje memorijskih resursa. Otuda je uvedena modifikacija gde se samo jedan primerak prefiksa smešta i to u onu listu kojoj odgovara najmanja vrednost brojača od proračunatih lokacija, kao što 88 Slika 4.5.1.1. – Primer upisa prefiksa u lukap tabelu zasnovanu na Blum filtru sa brojanjem je prikazano u primeru sa slike 4.5.1.2. Meñutim, ova metoda, iako optimizuje memorijske resurse, ne optimizuje i dubinu listi, pa je zbog toga predloženo menjanje vrednosti brojača u cilju minimizovanja veličina listi čime se ubrzava pretraga tj. lukap. Naravno, posledica je otežano ažuriranje takve strukture pošto se mora voditi računa koji brojači su menjani. Kod korišćenja brojača je takoñe nezgodno što treba da se unapred predvidi koliko prefiksa može maksimalno da se smesti po jednoj listi da bi se znalo koliko bita treba da se koristi za formiranje brojača. Takoñe, i dalje ostaje problem da strukture sa Blum filtrima treba implementirati i pretraživati na svim dužinama. Otuda se i u ovom slučaju često koristi tehnika guranja prefiksa, sa sličnim problemom povećanja broja prefiksa kod originalnog lukap algoritma baziranog na heširanju. 89 Osnovna prednost heširanja sa Blum filtrima je što se pomoću Blum filtara odmah utvrdi da li prefiks date dužine postoji ili ne, bez ispitivanja samih članova liste, te se značajno ubrzava odreñivanje dužine prefiksa. Naravno, postoji i verovatnoća ’lažno pozitivno’ dogañaja da utvrdimo da postoji prefiks putem ispitivanja brojača, a da se taj prefiks ne nalazi u listi. Meñutim, kako je već rečeno, pravilnim izborom parametara Blum filtra ovu verovatnoću je moguće svesti na malu vrednost. Takoñe, dobrim izborom parametara je moguće optimizovati i veličine listi tako da se pretrage listi skrate. Meñutim, ostaje da je, zbog problema ’lažno pozitivno’ dogañaja i zbog toga što liste ipak mogu da sadrže različit broj elemenata, teško uvesti tehnike poput pajplajna za ubrzavanje lukapa. Stoga se često Blum filtri koriste na dužinama koje sadrže najveći procenat prefiksa u lukap tabeli, a za ostale dužine se koriste neke druge metode pretrage [90]. 2 1 1 1 2 0 0 Heš 1 Heš 2 Heš 3 2 x1 ID x1 NULL Brojači Liste sa prefiksima x2 ID x2 NULL x3 ID x3 NULL Ulaz Slika 4.5.1.2. – Primer čuvanja samo jednog zapisa po prefiksu u lukap tabeli zasnovanoj na Blum filtru 4.5.2. Predstavnici lukap algoritama baziranih na heširanju U narednim pododeljcima će biti analizirani osnovni lukap heš algoritam, kao i jedan karakterističan predstavnik lukap algoritama baziranih na Blum filtrima. i) Osnovni lukap heš algoritam Osnovni lukap heš algoritam je prikazan na slici 4.5.1. pri čemu će u okviru ovog pododeljka biti analizirana varijanta prikazana na 4.5.1.b. Da bi se smanjila verovatnoća kolizije prefiksa neophodno je da rezultujući prostor heš funkcije bude dovoljno veći od broja prefiksa koji se hešira odnosno unosi u lukap tabelu. Otuda je varijanta prikazana pod 4.5.1.b memorijski efikasnija jer se u celokupnom prostoru koji adresira heš funkcija čuvaju samo pokazivači na potrebne informacije (prefiks, ID izlaznog porta, pokazivač na sledećeg člana liste) koje se nalaze u posebnoj memoriji. Ta druga 90 memorija čuva podatke samo za heširane prefikse tj. samo za one prefikse koji su uneti u lukap tabelu. Zato se koriste dve memorije. Jedan član liste sadrži tri podatka: vrednost prefiksa, ID izlaznog porta i pokazivač na sledećeg člana liste. Pri tome treba imati na umu da struktura prikazana na slici 4.5.1.b postoji za svaku moguću dužinu prefiksa tj. ima  takvih struktura koje rade u paraleli. Memorijski zahtevi memorije pokazivača ('<) i memorije listi ('a) iznose: '<  4!, · Alog$ <, Fb,6  'a  4J<, · @& : / : Alog$ <, FGKb,6 (4.5.2.1.1) gde je <, broj prefiksa dužine & unetih u lukap tabelu, !, ukupan broj različitih memorijskih lokacija koje mogu da se dobiju heš funkcijom koja se vrši nad prefiksima dužine &, / dužina ID-a izlaznog porta. Kao što je već rečeno primena heš funkcija ne omogućava laku implementaciju pajplajna zbog varijabilne dužine listi. Otuda je garantovani protok lukap modula obrnuto proporcionalan maksimalnoj dužini liste gledano po svim dužinama prefiksa. U slučaju i IPv4 i IPv6 adresa je tipično da je jedna dužina prefiksa dominantna u odnosu na druge u pogledu broja prefiksa. Tako npr. kod IPv4 adresa najveći broj prefiksa ima dužinu 24, a kod IPv6 najeveći broj prefiksa ima dužinu 48. Samim tim u slučaju upotrebe eksternih memorijskih čipova prvo se izmeštaju memorije za dužinu prefiksa koja sadrži najveći broj prefiksa. Pri tome se u zavisnosti od odnosa <, i !, selektuje koja od memorija se prvo izmešta - memorija pokazivača ili memorija listi. Tipično je memorija pokazivača veća jer da bi se značajno smanjio broj kolizija neophodno je da važi !, c <, . Na osnovu navedenog interni memorijski resursi (',)0, ) su: ',)0,  S'020 + max @',6 (5.1.1.1) gde je `(, broj balansiranih stabala u nivou &, a ., broj čvorova u jednom balansiranom stablu u nivou &. Očigledno je da mora da važi `(, · .,  <2E, , gde je <2E, broj nepraznih podstabala nivoa &. Registarski resursi bloka za pretragu pokazivača na podstabla (j`() koji se koriste za čuvanje opsega balansiranih stabala iznose: j`(  4@`(, · 2 · & + 1 · ;Gb/>,6 (5.1.1.2) U bloku za nalaženje prefiksa razlikujemo tri vrste internih memorija – početnu memoriju sa indeksima prvih ∆ nepraznih čvorova, dodatne memorije koje čuvaju indekse narednih popunjenih čvorova i dodatnu memoriju koja čuva kompletne bitmape gusto popunjenih podstabala. Broj lokacija početnih memorija nekog nivoa je jednak broju nepraznih podstabala tog nivoa, pri čemu svaka lokacija čuva ∆ indeksa čvorova i pokazivač na dodatnu memoriju. Broj bita potreban za čuvanje jednog indeksa iznosi ; : 1. Stoga su zahtevani memorijski resursi za početne memorije svih nivoa (',6 (5.1.1.3) gde je E!, dužina pokazivača na dodatnu memoriju u nivou &. Pokazivač na dodatnu memoriju se sastoji iz dva dela – jedan deo odreñuje koja od n : 1 dodatne memorije je 105 u pitanju, a drugi deo odreñuje lokaciju u okviru odgovarajuće dodatne memorije. Otuda se dužina pokazivača na dodatnu memoriju E!, može predstaviti kao: E!,  Plog$n : 1Q : rlog$ max56..M? !,,5s (5.1.1.4) gde je max56..M? !,,5 broj lokacija najveće od dodatnih memorija u nivou & (najveća u smislu najvećeg broja lokacija). U lokacijama dodatne memorije koja može da čuva 9 · ∆ indeksa dodatnih popunjenih čvorova čuvaju se samo ti indeksi pa je dužina jedne lokacije 9 · ∆ · ; : 1. Zahtevani memorijski resursi dodatnih memorija koje čuvaju indekse popunjenih čvorova svih nivoa ('E!..M) iznose: 'E!..M  4 4 !,,5 · 9 · ∆ · ; : 1M56 b/> ,6 (5.1.1.5) gde je !,,5 broj lokacija u dodatnoj memoriji 9 nivoa &. Zahtevani memorijski resursi ('E!M?) dodatnih memorija koje čuvaju kompletne bitmap vektore, dužine 2>? + 2, gusto popunjenih podstabala svih nivoa iznose: 'E!M?  4 !,,M? · 2>? + 2b/>,6 (5.1.1.6) gde je !,,M? broj lokacija u dodatnoj memoriji koja čuva kompletne bitmape gusto popunjenih podstabala nivoa &. Izlazna memorija čuva ID-eve izlaznih portova. Pri tome početne memorije i dodatne memorije svih nivoa imaju unapred dodeljen prostor u okviru izlazne memorije tj. koristi se statičko adresiranje. Tako da su zahtevani memorijski resursi za izlaznu memoriju (',-): ',-  / · 4 t@`(, · ., · ∆G : 4@!,,5 · 9 · ∆GM56 : !,,M? · 2>? + 2u b/> ,6 (5.1.1.7) gde je / dužina ID-a izlaznog porta. Kada se koriste eksterni memorijski čipovi prvo se izmešta izlazna memorija jer je najveća. Potom se izmeštaju početna memorija i dodatna memorija sa ∆ prefiksa bloka za nalaženje prefiksa najgušće popunjenog nivoa jer su one sledeće najveće memorije. Otuda su interni memorijski resursi (',)0, ): 106 ',)0,  L '020 + ',- , &  1 '020 + ',- + ',6 ^ · ∆ · ; : 1 : E! : / (5.1.2.1) gde je E! dužina pokazivača na dodatne memorije. Pri tome važi sličan proračun za E! kao i u slučaju BPFL-a samo što treba uzeti u obzir da su dodatne memorije sada deljene izmeñu nepraznih podstabala svih nivoa. Otuda se dužina pokazivača na dodatnu memoriju E! može predstaviti kao: E!  Plog$n : 1Q : rlog$ max56..M? !5 s (5.1.2.2) gde je max56..M? !5 broj lokacija najveće od dodatnih memorija u bloku za nalaženje prefiksa (najveća u smislu najvećeg broja lokacija). 112 Dodatne memorije imaju istu strukturu kao i u originalnom BPFL-u, samo što sada sadrže popunjene čvorove podstabala različitih nivoa. Zahtevani memorijski resursi dodatnih memorija koje čuvaju indekse popunjenih čvorova ('E!..M) iznose: 'E!..M  4 !5 · 9 · ∆ · ; : 1M56 (5.1.2.3) gde je !5 broj lokacija u dodatnoj memoriji 9. U dodatnoj memoriji koja čuva kompletan bitmap čuvaju se kompletni bitmapi gusto popunjenih podstabala, pri čemu je dužina bitmapa 2>? + 2. Zahtevani memorijski resursi dodatne memorije koja čuva kompletne bitmape gusto popunjenih podstabala ('E!M?) iznose: 'E!M?  !M? · 2>? + 2 (5.1.2.4) gde je !M? broj lokacija u dodatnoj memoriji koja čuva kompletne bitmape gusto popunjenih podstabala. Izlazna memorija čuva ID-eve izlaznih portova, pri čemu početne memorije i dodatne memorije imaju unapred dodeljen prostor u okviru izlazne memorije tj. koristi se statičko adresiranje. Tako da su zahtevani memorijski resursi za izlaznu memoriju (',-): ',-  / · t4@`(, · ., · ∆Gb/>,6 : 4@!5 · 9 · ∆G M 56 : !M? · 2>? + 2u (5.1.2.5) gde je / dužina ID-a izlaznog porta. Kada se koriste eksterni memorijski čipovi prvo se izmešta izlazna memorija jer je najveća. Potom se izmeštaju početna memorija i dodatna memorija sa ∆ prefiksa bloka za nalaženje prefiksa jer su one sledeće najveće memorije. Otuda su interni memorijski resursi (',)0, ): ',)0,  L '`( : 'E!..M? : ', gde je , dužina IP adrese, a ; veličina jednog nivoa tj. dubina podstabla na jednom nivou. Dakle, kompleksnost ažuriranja u najgorem slučaju se pogoršala za BPFLSM algoritam u odnosu na BPFL algoritam. Ali, u praksi kompleksnost ovakvog slučaja je znatno manja, jer obično postojeći prefiksi koji imaju decu predstavljaju agregaciju drugih postojećih prefiksa, pa je broj podstabala na koja neki prefiks može da utiče tipično znatno manji od broja čvorova svih balansiranih stabala nekog nivoa. 5.1.3. BPFLSS Kao što smo videli u prethodnom odeljku, BPFLSM je omogućio udruživanje blokova za nalaženje prefiksa, a samim tim i njihovih memorijskih resursa. Udruživanjem memorijskih resursa je omogućeno da se najveća memorija u bloku za nalaženje prefiksa - početna memorija izmesti u eksterni memorijski čip i time značajno smanje interni memorijski zahtevi. BPFLSS dodatno unapreñuje memorijsku organizaciju bloka za nalaženje prefiksa BPFLSM-a. Umesto višestrukih dodatnih memorija koristi se samo jedna čime je omogućeno da se kompletni interni memorijski resursi bloka za nalaženje prefiksa izmeste u dva eksterna memorijska čipa i time dodatno smanje interni memorijski zahtevi. Upotreba samo jedne dodatne memorije je omogućena podelom podstabala na dva nivoa. 114 Slika 5.1.3.1. – Blok za nalaženje prefiksa u BPFLSS Opšta arhitektura BPFLSS-a je identična arhitekturi BPFLSM-a prikazanoj na slici 5.1.2.1. Suštinska razlika izmeñu BPFLSS-a i BPFLSM-a je u organizaciji memorijskih resursa za čuvanje podstabala u bloku za nalaženje prefiksa. Struktura bloka za nalaženje prefiksa BPLFSS-a je prikazana na slici 5.1.3.1. Kao što se može videti postoje samo dve memorije i obe mogu da se izmeste u eksterne memorijske čipove. Važno je napomenuti da se i u BPFLSS uz svako neprazno podstablo čuva i dodatni ID izlaznog porta kao i kod BPFLSM-a, čime je omogućeno formiranje zajedničkog bloka za nalaženje prefiksa. Slika 5.1.3.2. – Podela podstabla na gornji i donji nivo U BPFLSS-u se čuvaju samo indeksi popunjenih čvorova za veoma retko popunjena podstabla (ona koja sadrže maksimalno ∆ prefiksa). Indeksi popunjenih čvorova podstabla se, uz dodatni ID izlaznog porta, čuvaju u odgovarajućoj lokaciji početne memorije. Svakom indeksu popunjenog čvora je statički dodeljena jedna lokacija u izlaznoj memoriji gde se čuva ID izlaznog porta tog čvora. Struktura lokacije početne memorije u slučaju veoma retko popunjenih podstabala je prikazana na slici 5.1.3.3. U slučaju podstabala sa više od ∆ prefiksa, podstabla su podeljena na dva nivoa - gornji i donji. Gornji nivo sadrži samo jedno podstablo, a donji nivo sadrži 2>/$ 115 podstabala, kao na slici 5.1.3.2. Bitmap podstabla gornjeg nivoa se čuva u početnoj memoriji, a bitmapi podstabala donjeg nivoa koja sadrže bar jedan popunjen čvor se čuvaju u dodatnoj memoriji. Bitmapi podstabala donjeg nivoa koja ne sadrže nijedan popunjen čvor se ne čuvaju. Struktura lokacije početne memorije za slučaj podstabala sa više od ∆ prefiksa je prikazana na slici 5.1.3.3. Dodatni ID izlaznog porta se čuva i u ovom slučaju jer i dalje postoji mogućnost da se ne nañe prefiks u pretraživanom podstablu. Slika 5.1.3.3. – Struktura lokacije u početnoj memoriji Bitmap postojanja podstabala definiše koja podstabla donjeg nivoa su neprazna i na osnovu njega se utvrñuje da li uopšte treba pristupiti dodatnoj memoriji za datu IP adresu. Pokazivač na dodatnu memoriju daje lokaciju prvog nepraznog podstabla donjeg nivoa, a lokacije ostalih nepraznih podstabala se odreñuju kao ofset u odnosu na prvo neprazno podstablo. Pri računanju ofseta se u obzir uzimaju samo neprazna podstabla donjeg nivoa. U izlaznoj memoriji je dinamički dodeljen memorijski blok za ID-eve izlaznih portova popunjenih čvorova. Na početak memorijskog bloka ukazuje pokazivač na izlaznu memoriju. Brojač maksimalnog broja popunjenih čvorova po podstablu definiše broj lokacija u izlaznoj memoriji koje su dodeljene jednom nepraznom podstablu gornjeg/donjeg nivoa. Brojač dostiže maksimalnu vrednost u slučaju kad je bar jedno podstablo gornjeg ili donjeg nivoa maksimalno popunjeno i tada brojač ima vrednost 2>/$? + 2 (broj čvorova u jednom podstablu gornjeg/donjeg nivoa). Početak bloka dodeljen jednom nepraznom podstablu se računa kao ofset u odnosu na pokazivač na izlaznu memoriju, pri čemu u proračun ulaze samo neprazna podstabla tj. njihov broj lokacija. Unutar tako odreñenog bloka lokacija, pozicija odgovarajućeg ID-a izlaznog porta se računa kao redni broj popunjenog čvora u podstablu uzimajući u obzir samo popunjene čvorove tog podstabla. Tip strukture lokacije u početnoj memoriji je odreñen vrednošću prvog bita kao što se može videti sa slike 5.1.3.3. 116 Sa stanovišta ažuriranja postoje dodatne razlike u odnosu na BPFLSM. U BPFLSS može doći do potencijalnih premeštanja u izlaznoj memoriji usled promene broja nepraznih podstabala ili usled promene maksimalnog broja popunjenih čvorova po jednom podstablu, pri čemu se pod podstablom misli na podstablo gornjeg/donjeg nivoa. U najgorem slučaju broj premeštanja je 2>? + 2 što predstavlja ukupan broj čvorova jednog podstabla. Takoñe, promena broja nepraznih podstabala može da izazove i premeštanje u dodatnoj memoriji. U najgorem slučaju broj premeštanja je jednak broju podstabala donjeg nivoa 2>/$. Oba navedena slučaja su povoljnija od najgoreg slučaja koji se javljao u BPFL i BPFLSM, a to je pomeranje svih čvorova svih balansiranih stabala u bloku za nalaženje podstabla u nivou sa najvećim brojem podstabala. Pošto je struktura bloka za nalaženje podstabla ista u sva tri algoritma (BPFL, BPFLSM i BPFLSS), najgori slučaj ažuriranja je identičan u sva tri predložena lukap algoritma. Što se tiče proračuna memorijskih resursa za BPFLSS, osnovne razlike u odnosu na originalni BPFL su udruživanje blokova za nalaženje prefiksa i promena načina čuvanja informacija o internoj strukturi podstabala. Otuda za memorijske i registarske resurse blokova za nalaženje podstabla i dalje važe (5.1.1.1) i (5.1.1.2). U početnoj memoriji su dodeljene lokacije za sva neprazna podstabla svih nivoa, pri čemu se dužina lokacije dimenzioniše za slučaj kada podstablo ima više od ∆ prefiksa (prema toj dužini se proračunava vrednost ∆ tj. koliko indeksa stane u lokaciju). Bitmap podstabla gornjeg nivoa mora da bude dužine 2>/$? + 2 da bi indeksirao sve čvorove. Na osnovu dužine tog bitmapa se vidi koliko ima čvorova po podstablu gornjeg/donjeg nivoa, pa je lako zaključiti da je za brojač (slika 5.1.3.3) neophodno ;/2 : 1 bita. Bitmap postojanja podstabala donjeg nivoa mora da bude dužine 2>/$ da bi ih sve indeksirao. Stoga, u BPFLSS zahtevani memorijski resursi početne memorije ' ,6 x y · · @1 : / : 2>/$? + 2 : 2>/$ : E! : ,! : ;/2 : 1G (5.1.3.1) 117 gde su E! i ,! dužine pokazivača na dodatnu memoriju i izlaznu memoriju, respektivno. Dodatna memorija se deli na blokove veličine 2>/$ lokacija radi lakšeg menadžmenta memorije i ažuriranja, pa je: E!  Alog$@>/$ · 2>/$GF (5.1.3.2) gde je >/$ potreban broj blokova veličine 2>/$ u dodatnoj memoriji za smeštanje bitmapa nepraznih podstabala donjeg nivoa gušće popunjenih podstabala (onih podstabala koji imaju više od ∆ popunjenih čvorova). Dinamički alociran deo izlazne memorije je podeljen na blokove veličine 2>? radi lakšeg menadžmenta memorije i ažuriranja, pa je: ,!  Plog$>? · 2>?Q (5.1.3.3) gde je >? broj blokova veličine 2>? u dinamički alociranom delu izlazne memorije. U skladu sa datom definicijom za >/$ zahtevani memorijski resursi za dodatnu memoriju ('E!) iznose: 'E!  >/$ · 2>/$ · @2>/$? + 2G (5.1.3.4) Imajući u vidu statički dodeljeni prostor u izlaznoj memoriji od ∆ lokacija za svaku lokaciju u početnoj memoriji i definiciju za >?, zahtevani memorijski resursi za izlaznu memoriju (',-) iznose: ',-  / · t[4@`(, · .,Gb/>,6 ^ · ∆ : >? · 2>?u (5.1.3.5) gde je / dužina ID-a izlaznog porta. Kada se koriste eksterni memorijski čipovi prvo se izmešta izlazna memorija jer je najveća, pa potom početna memorija i dodatna memorija bloka za nalaženje prefiksa. Otuda su interni memorijski resursi (',)0, ): ',)0,  L '`( : 'E! : '/$ (broj blokova veličine 2>/$ u dodatnoj memoriji za smeštanje bitmapa nepraznih podstabala donjeg nivoa) i >? (broj blokova veličine 2>? u dinamički alociranom delu izlazne memorije). Memorijski resursi se ne razlikuju u značajnoj meri u odnosu na BPFLSM, ali je dodatna prednost što postoji samo jedna dodatna memorija pa ona kao i početna memorija u slučaju potrebe može da se izmesti u eksternu memoriju, što pruža dodatni stepen fleksibilnosti BPFLSS-u. Takoñe, interesantno je da BPFLSS u slučaju IPv4 tabela ima manje memorijske zahteve za izlaznu memoriju, dok je u slučaju IPv6 tabela obrnuta situacija. Razlog je u razlici struktura podstabala u IPv4 i IPv6 slučaju. U IPv6 tabelama je manji udeo gušće popunjenih podstabala, pa kod BPFL i BPFLSM u IPv6 slučaju dolazi do rezervisanja manjeg broja neiskorišćenih lokacija u izlaznoj memoriji. Sa stanovišta najgoreg slučaja u BPFL i BPFLSM po pitanju neiskorišćenih lokacija je formiranje kompletnog bitmapa za veoma gusta stabla jer on rezerviše lokacije u 165 izlaznoj memoriji za sve čvorove koji su indeksirani u bitmapu. Bitmap adresira 510 čvorova u konkretnom slučaju za ;  8, a veoma retko broj popunjenih čvorova u podstablu bude veći od 200, tako da se u IPv4 tabelama na taj način rezerviše velik broj neiskorišćenih lokacija u izlaznoj memoriji. U IPv6 slučaju se takva situacija reñe dešava pa je samim tim i manje neiskorišćenih lokacija što se može videti po zahtevanim resursima za izlaznu memoriju u tabeli A.2.1.3. S druge strane ponašanje BPFLSS je konzistentnije tj. isto je ponašanje i za IPv4 i za IPv6 tabele pa samim tim dobijamo manje zahtevane resurse za izlaznu memoriju u IPv4 slučaju, a veće u IPv6 slučaju u odnosu na BPFL i BPFLSM. Tabela A.2.1.4. – Vrednosti parametara BPFL i BPFLSM algoritama za IPv6 lukap tabele Veličina tabele 105K 130K 153K 175K 210K 241K 274K 308K 349K 365K Parametri N½¿# 1 2 1 4 2 1 2 2 5 3 N­# 3 3 3 3 3 3 3 3 3 3 Nº#, 0 0 0 1 2 0 0 3 3 2 Nº#,$ 0 1 0 1 1 0 2 0 4 2 Nº#,# 0 1 0 1 0 0 0 0 4 0 Nº#,H 0 0 0 1 0 0 0 0 1 0 Nº#,› 1 1 1 0 1 3 3 2 1 5 N½¿H 7 7 7 8 10 11 11 12 12 13 N­H 31 31 31 31 31 31 31 31 31 31 NºH, 25 31 21 32 52 57 49 45 46 68 NºH,$ 24 20 27 27 28 38 38 45 53 47 NºH,# 19 18 10 21 30 33 32 35 39 38 NºH,H 19 11 18 19 23 28 25 32 34 31 NºH,› 69 82 91 91 91 108 105 113 122 132 N½¿› 55 73 81 89 104 117 119 132 142 146 N­› 63 63 63 63 63 63 63 63 63 63 Nº›, 509 667 778 935 1126 1305 1440 1614 1771 1859 Nº›,$ 73 109 157 188 249 311 344 428 485 488 Nº›,# 19 19 25 40 55 63 100 106 133 155 Nº›,H 3 5 7 5 9 8 25 22 35 42 Nº›,› 1 1 1 2 1 4 11 11 16 14 N½¿œ 63 75 85 95 109 122 131 144 159 163 N­œ 255 255 255 255 255 255 255 255 255 255 Nºœ, 2230 2737 3397 3899 4681 5506 6316 7035 8142 8506 Nºœ,$ 366 509 652 846 1066 1265 1546 1879 2143 2295 Nºœ,# 68 75 123 156 203 273 399 510 616 678 Nºœ,H 8 16 26 32 49 73 110 137 196 192 Nºœ,› 1 2 5 8 12 13 31 42 49 80 N½¿ 1 4 1 4 29 9 14 17 46 51 N­ 63 63 63 63 63 63 63 63 63 63 Nº, 0 0 0 0 0 0 0 0 0 0 166 Nº,$ 0 0 0 0 0 0 0 0 0 0 Nº,# 0 0 0 0 0 0 0 0 0 0 Nº,H 0 0 0 0 0 0 0 0 0 0 Nº,› 0 0 0 0 0 0 0 0 0 0 N½¿ 3 6 2 3 18 27 64 80 18 15 N­ 31 31 31 31 31 31 31 31 31 31 Nº, 0 0 0 0 0 0 0 0 0 0 Nº,$ 0 0 0 0 0 0 0 0 0 0 Nº,# 0 0 0 0 0 0 0 0 0 0 Nº,H 0 0 0 0 0 0 0 0 0 0 Nº,› 0 0 0 0 0 0 0 0 0 0 Tabela A.2.1.5. – Zahtevani memorijski resursi BPFLSS algoritma za IPv4 lukap tabele Veličina tabele ‘ª/ƒ ‘ª?‚ »¼–}¼ ”¼–}”— ”Ÿ•}”— ”¡•}”— ”¤¥}”— 104779 1387 387 3696 0.0127 0.0805 0.0794 0.4799 130287 1645 481 4768 0.0158 0.0992 0.0941 0.5954 153126 1900 568 4880 0.0173 0.1104 0.1087 0.6932 175399 2109 654 5952 0.0199 0.1274 0.1207 0.7970 210039 2447 779 11456 0.0269 0.1636 0.1400 0.9641 240958 2771 898 8448 0.0256 0.1659 0.1586 1.0831 273791 3100 1024 9824 0.0288 0.1816 0.1774 1.2256 307915 3402 1152 10560 0.0311 0.1981 0.1947 1.3689 348866 3803 1310 16336 0.0385 0.2364 0.2176 1.5703 365309 3960 1376 16640 0.0395 0.2428 0.2266 1.6426 Tabela A.2.1.6. – Zahtevani memorijski resursi BPFLSS algoritma za IPv6 lukap tabele Veličina tabele ‘ª/ƒ ‘ª?‚ »¼–}¼ ”¼–}”— ”Ÿ•}”— ”¡•}”— ”¤¥}”— 104779 1404 253 9456 0.0918 0.2373 0.0803 0.5508 130287 2116 257 12128 0.1121 0.2965 0.1211 0.6231 153126 2581 337 12672 0.1242 0.3298 0.1477 0.7430 175399 2691 420 14528 0.1397 0.3701 0.1540 0.8746 210039 3791 458 20720 0.1726 0.4505 0.2169 1.0126 240958 3768 628 21728 0.1863 0.4940 0.2156 1.2271 273791 5197 686 27232 0.2072 0.5469 0.2974 1.3431 307915 6469 743 31200 0.2306 0.6071 0.3702 1.4727 348866 5990 978 28976 0.2489 0.6612 0.3428 1.7689 365309 5782 1160 29712 0.2559 0.6866 0.3308 1.9698 167 B. MRT FORMAT LUKAP TABELA RUTERA Da bi se obezbedila efikasna analiza rada Internet mreže, istraživačima je trebalo omogućiti da imaju uvid u razmene poruka protokola rutiranja, kao i uvid u sadržaj lukap tabela Internet rutera, pri čemu je trebalo omogućiti da istim podacima može da pristupa i da ih koristi velik broj istraživača. Usled postojanja navedenih potreba istraživača, razvijen je MRT format koji standardizuje prikaz rada protokola rutiranja u vidu razmene poruka, kao i prikaz sadržaja lukap tabele [94]. U okviru ove teze su korišćeni MRT zapisi lukap tabela dostupni u vidu fajlova za preuzimanje na [93]. Cilj ovog priloga je da izloži strukturu MRT zapisa lukap tabela. Jedan fajl sadrži više MRT zapisa. Struktura zaglavlja jednog MRT zapisa je data na slici B.1. Polje Timestamp označava trenutak formiranja zapisa i dužine je 4 bajta. Polje Type predstavlja tip zapisa i dužine je dva bajta. Polje Subtype, dužine dva bajta, predstavlja podtip zapisa koji se koristi u sprezi sa poljem Type radi preciznijeg odreñivanja prirode zapisa, odnosno njegove strukture. Polje Length odreñuje dužinu zapisa u bajtovima, pri čemu se bajtovi zaglavlja ne uzimaju u obzir. Polje Length je dužine četiri bajta. Polje Message sadrži sam zapis. Timestamp (4B) Type (2B) Subtype (2B) Length (4B) Message (~) Slika B.1. – Zaglavlje MRT zapisa Kao što je rečeno polje Type definiše tip zapisa. U preporuci [94] je definisano devet tipova, pri čemu je svakom tipu dodeljena odgovarajuća vrednost polja Type. U tabeli B.1 su navedeni svi definisani tipovi zapisa sa odgovarajućim vrednostima polja Type. 168 Tabela B.1. – Definisani tipovi MRT zapisa Vrednost polja Type Tip MRT zapisa 11 OSPFv2 12 TABLE_DUMP 13 TABLE_DUMP_V2 16 BG4MP 17 BG4MP_ET 32 ISIS 33 ISIS_ET 48 OSPFv3 49 OSPFv3_ET Tipovi TABLE_DUMP i TABLE_DUMP_V2 predstavljaju zapise u kojima se čuva sadržaj lukap tabele. Preporučuje se upotreba novijeg tipa TABLE_DUMP_V2 za prikaz strukture lukap tabele rutera. Meñutim, na sajtu [93] gde su dostupni sadržaji lukap tabela rutera u MRT formatu, fajlovi koji čuvaju veoma stare sadržaje lukap tabela (osam godina i više) koriste stariji TABLE_DUMP tip, pa će stoga oba tipa biti izložena u nastavku. Stariji TABLE_DUMP tip ima dve moguće vrednosti za polje Subtype. Ukoliko polje Subtype ima vrednost 1, tada MRT zapis sadrži IPv4 prefiks, a ukoliko polje Subtype ima vrednost 2, tada MRT zapis sadrži IPv6 prefiks. Struktura jednog MRT zapisa za TABLE_DUMP tip je data na slici B.2. Prefix (4B ili 16B) Prefix Length (1B) Status (1B) Originated Time (4B) BGP Attribute (~) View (2B) Sequence Number (2B) Peer IP Address (4B ili 16B) Peer AS (2B) Attribute Length (2B) Slika B.2. – Struktura jednog MRT zapisa za TABLE_DUMP tip Polje View, dužine dva bajta, ima tipično vrednost 0 u većini slučajeva. Ovo polje je namenjeno za slučaj višestrukih lukap tabela, poput servera ruta, da bi se različite lukap tabele iz istog ureñaja mogle meñusobno razlikovati. Polje Sequence 169 Number, dužine dva bajta, predstavlja redni broj zapisa u lukap tabeli. U slučaju da je broj zapisa veći od 216, polje Sequence Number koristi kružni princip brojanja, po kome se svaki put nakon dostizanja maksimalne vrednosti ponovo broji od nule. Polje Prefix predstavlja prefiks iz lukap tabele. Ovo polje ima dužinu četiri bajta za slučaj IPv4 prefiksa, odnosno, šesnaest bajtova za slučaj IPv6 prefiksa. Polje Prefix Length, dužine jedan bajt, odreñuje dužinu prefiksa, odnosno, broj bita od interesa iz polja Prefix koji zaista i čine prefiks. Očigledno je da predstava prefiksa nije optimalna u slučaju TABLE_DUMP tipa, pošto se uvek čuva onoliko bita kolika je dužina IP adrese (32b za IPv4, odnosno 128b za IPv6 prefikse). Videćemo u nastavku da TABLE_DUMP_V2 tip nema takvu manu. Polje Status, dužine jedan bajt, se ne koristi i ovo polje je uvek postavljeno na vrednost 1. Polje Originated Time, dužine četiri bajta, predstavlja vreme kada je dotični zapis prvi put kreiran u lukap tabeli. Polje Peer IP Address, predstavlja IP adresu ’peer’ rutera od kog je dobijen podatak o dotičnom prefiksu. Dužina ovog polja je četiri ili šesnaest bajtova, u zavisnosti da li je u pitanju IPv4 ili IPv6 adresa. Polje Peer AS, dužine dva bajta, predstavlja adresu autonomnog sistema kome pripada ’peer’ ruter od kog je dobijeno obaveštenje o prefiksu. Polje Attribute Length, dužine dva bajta, odreñuje dužinu BGP atributa koji je smešten u polje BGP Attribute. Noviji TABLE_DUMP_V2 tip ima šest mogućih vrednosti za polje Subtype i one su date u tabeli B.2. Tabela B.2. – Vrednosti Subtype polja za TABLE_DUMP_V2 tip Vrednost polja Subype Naziv podtipa 1 PEER_INDEX_TABLE 2 RIB_IPV4_UNICAST 3 RIB_IPV4_MULTICAST 4 RIB_IPV6_UNICAST 5 RIB_IPV6_MULTICAST 6 RIB_GENERIC Podtip PEER_INDEX_TABLE predstavlja listu indeksiranih ’peer’ rutera. MRT zapis sa ovim podtipom se obično stavlja na početak liste MRT zapisa u jednom fajlu. Indeksi ’peer’ rutera se koriste potom u zapisima ostalih podtipova navedenih u tabeli B.2. Na ovaj način je izbegnuto dupliranje informacija o ’peer’ ruterima koje se javlja u slučaju starijeg TABLE_DUMP tipa. Sada se sve informacije o ’peer’ ruterima nalaze na samo jednom mestu, a potom se u ostalim zapisima koriste indeksi za identifikovanje ’peer’ rutera koji su mnogo kraći. Podtip RIB_IPV4_UNICAST predstavlja zapis koji 170 odgovara IPv4 unikast prefiksu. Podtip RIB_IPV4_MULTICAST predstavlja zapis koji odgovara IPv4 multikast prefiksu. Podtip RIB_IPV6_UNICAST predstavlja zapis koji odgovara IPv6 unikast prefiksu. Podtip RIB_IPV6_MULTICAST predstavlja zapis koji odgovara IPv6 multikast prefiksu. Podtip RIB_GENERIC se koristi za sva slučajeve koji nisu pokriveni nekim od prethodno navedena četiri podtipa i njega nećemo razmatrati u nastavku. Zapisi podtipova RIB_IPV4_UNICAST, RIB_IPV4_MULTICAST, RIB_IPV6_UNICAST, RIB_IPV6_MULTICAST imaju dodatno zaglavlje tzv. zaglavlje unosa prikazano na slici B.3. Slika B.3. – Zaglavlje unosa Polje Sequence Number, dužine četiri bajta, predstavlja redni broj zapisa u lukap tabeli. Polje Prefix Length, dužine jedan bajt, predstavlja dužinu odgovarajućeg prefiksa iz lukap tabele. Polje Prefiks predstavlja vrednost prefiksa, pri čemu ovo polje ima onoliko bita koliko je dugačak sam prefiks. Kao što vidimo ovde nema čuvanja bita koji ne ulaze u prefiks, kao što je to bilo kod starijeg TABLE_DUMP tipa. Polje Entry Count, dužine dva bajta, predstavlja broj unosa koji odgovaraju dotičnom prefiksu. Naime, u starijem TABLE_DUMP tipu je za svaki prefiks moglo da postoji više zapisa, npr. ako je ruter dobio informaciju o istom prefiksu od više ’peer’ rutera ili ima više navedenih BGP atributa u lukap tabeli. Ovakav način čuvanja nije bio naročito efikasan, pa je uveden noviji TABLE_DUMP_V2 tip koji znatno efikasnije čuva informacije o lukap tabeli. U okviru TABLE_DUMP_V2 tipa za isti prefiks se može formirati više tzv. unosa koji se čuvaju u okviru samo jednog zapisa, onog koji odgovara dotičnom prefiksu. Polje RIB Entries je promenljive dužine i sadrži same unose. 171 Struktura jednog unosa je data na slici B.4. Polje Peer Index, dužine dva bajta, sadrži indeks ’peer’ rutera od koga je dobijen unos. Polje Originated Time, dužine četiri bajta, predstavlja vreme kada je unos prvi put kreiran u lukap tabeli. Polje Attribute Length, dužine dva bajta, predstavlja dužinu svih BGP atributa, koji se čuvaju u polju BGP Attributes. Slika B.4. – Struktura jednog unosa 172 BIOGRAFIJA Čiča Zoran je roñen 18.3.1979. u Zagrebu. Osnovno obrazovanje je započeo u Zagrebu. Zbog rata, 1991. je izbegao u Srbiju, u Sremsku Mitrovicu gde je završio osnovnu školu, a potom i gimnaziju. 1997. godine je upisao Elektrotehnički fakultet u Beogradu i diplomirao 27.5.2002. sa ukupnom srednjom ocenom 9.50, na diplomskom ispitu ocena 10. Tokom studija honorarno radio kao demonstrator u Laboratoriji za elektroniku Elektrotehničkog fakulteta u Beogradu. Postdiplomske studije - smer Telekomunikacione i računarske mreže na Elektrotehničkom fakultetu je upisao 2002. Ispite na postdiplomskim studijama položio je sa prosečnom ocenom 10. Magistarsku tezu „Primena determinističke teorije servisnih sistema u planiranju transportnih mreža“, čiji je mentor bio redovni profesor dr Petrović Grozdan, odbranio je decembra 2007. godine. U 2002. stekao je zvanje asistenta-pripravnika na Elektrotehničkom fakultetu u Beogradu. U 2008. je stekao zvanje asistenta. Držao je računske i lab vežbe iz predmeta Telekomunikacione mreže, Projektovanje digitalnih telefonskih centrala, Računarske telekomunikacije. Trenutno je angažovan na predmetima Računarske osnove i primene Interneta, Komutacioni sistemi, Projektovanje komunikacionog hardvera, Internet programiranje, Arhitektura svičeva i rutera. Takoñe je bio angažovan kao asistent na predmetu Računarske mreže i komunikacije na Vojno-tehničkoj akademiji. Učestvovao je na nekoliko projekata finansiranih od strane Ministarstva za nauku. Zoran Čiča je autor više radova na konferencijama i časopisima, od kojih su dva bila nagrañena kao Najbolji radovi mladih autora na konferencijama ETRAN 2007 i 2009. Jedan rad je objavljen u časopisu sa SCI liste - IET Electronics Letters sa impakt faktorom 1.004. Zoran Čiča je bio i recenzent za meñunarodne časopise IEEE Communication Letters i IEEE Transactions on Communications, za meñunarodnu konferenciju IEEE Workshop on High Performance Switching and Routing, kao i za domaće konferencije ETRAN i TELFOR. U 2010. dobio je priznanje Exemplary reviewer za časopis IEEE Communication Letters. 173 174 175