OLSR

Giriş
Link State Routing (LSR) aslında bir başlık veya aile gibi düşünülebilir. Bu başlık altında  OLSR,  IS-IS gibi yönlendirme protokolleri bulunuyor. Tüm bu protokollerin ortak ve kendine mahsus özellikleri var.
LSR protokollerinin ortak özelliklerinden birisi, tüm ağ için bir topoloji oluşturulması ve kendilerini topolojinin başlangıç düğümü olarak görmeleri.

Link-state routing protocols, such as OSPF and IS-IS, create a topology of the network and place themselves at the root of the tree.

Bir başka sınıflandırma şöyle 
Proactive Routing : DSDV, OLSR, STAR
Reactive Routing : AODV, DSR
Hybrid Routing : ZRP

OLSR Nedir?
Optimized Link State Routing (OLSR) Mobile Ad Hoc Network (MANET) veya Mesh ağlarında paket yönlendirmek için kullanılan yönlendirme algoritmalarından bir tanesi.

OLSRv1
OLSRv1 RFC3626 ile tanımlı.
Mobile Ad Hoc Networks RFC2501 ile tanımlı.

OLSRv2
OLSRv2 RFC7181 ile tanımlı.
OLSRv2 için Link Metrics RFC7185 ile tanımlı.

802.11 Ad Hoc Nedir?
MANET denilince kafalarda farklı şeyler oluşuyor. İçinde en çok MANET geçen konulardan bir tanesi de 802.11 ailesi. Bu yüzden bu başlığı yazma lüzumunu duydum.

802.11'de tanımlı olan MANET ağı, bu yazıdaki MANET ağından biraz daha farklı. 802.11'de normalde bir Access Point aracılığıyle iletişim kurulur. Buna Infrastructure Mode denir. Ad Hoc mod'da ise A cihazı B cihazı ile Access Point olmadan konuşabilir.

Ancak routing mantığı yoktur. Eğer A cihazı B cihazının kapsamasına giriyorsa, C ise A'dan uzakta ancak B'nin kapsama alanında ise A ve C iletişim kuramazlar. Yani peer to peer çalışır.

Diğer Ad Hoc Yönlendirme Algoritmaları Nelerdir?
Yönlendirme Algoritmaları şöyle sınıflandırılıyor.


Reactive Yönlendirmek Algoritması Nedir?
Reactive Yönlendirme Algoritmaları belli aralıklarla değil sadece gerekince ağı keşfetmeye çalışırlar.

With reactive protocols, a node discovers routes on-demand and maintains only active ones. Thus, a route is discovered whenever a source node needs to communicate with a destination node for which a route is not available. This discovery mechanism is based on pure flooding [1] in the network. Two reactive protocols are on the standard track or established RFCs: AODV and DSR.

Proactive Yönlendirmek Algoritması Nedir?

OLSR Proactive(table driven) başlığı altına düşüyor. Proactive çalışmak belli aralıklarla veya ağda değişiklik tespit edilince, elindeki bilgileri ağa yayınlamak anlamına gelir.

OLSR (Optimized Link State Routing) is a proactive routing protocol that is now an RFC. It provides the advantage of having routes immediately available in each node for all destinations in the network. Periodic control packets are in charge of monitoring the network topology. This class of protocol is particularly well suited for applications where all nodes can use the topology knowledge discovered by the routing protocol. Moreover, proactive routing protocols can be used without modification in the network protocol stack.

Bir başka a açıklama şöyle 
Proactive routing protocols are based on shortest path algorithns. It maintains and updates information on routing among all nodes of a given network at all times even if the paths are not currently being used. Thus, even if some paths are never used updates regarding such paths are constantly broadcasted among nodes. Route updates are periodically performed regardless of network load,  bandwidth constraints. 

Ben bu algoritmaları biraz ARP'a benzetiyorum. Nasıl ki ARP tam IP için MAC adresi gerektiğinde yapılıyor, bu algoritmalar da aynen routing bilgisi gerektiğinde yapılıyor.

OLSR Gerçekleştirimleri

NRL  olsrd, QOLSR, UniK olsrd gibi birden fazla OLSR gerçekleştirimi var.

OLSR Layer 3'tedir
OLSR forwarding ve  routing yeteneği sağlar. OSI modelinde Layer 3'tedir. OLSR'da Layer 2 kavramı yoktur. OLSR UDP ile çalışır ve Hello paketlerini 255.255.255.255 adresine ve 698 numaralı port'a gönderir.

OLSR ve İşletim Sistemi Yönlendirme Tabloları (Routing Table)
OLSR hesapladığı yolları işletim sistminin yönlendirme tablolarına gönderir. Linux'ta bu iş için Net Link Socket kullanır. Diğer Unix sistemlerinde ioctl ve SIOCADDRT seçeneğini kullanır.

Tüm Katılımcılar Bir Router'dır
OLSR'da tüm katılımcılar aynı zamanda birer router'dır.

Every node is potentially a router in a MANET, while most nodes in traditional wired networks do not route packets. Nodes transmit and receive their own packets and, also, forward packets for other nodes

Next Hop Nedir
Detaylara girmeden önce bazı kavramlara bakalım. Next Hop bir paketin gerçek hedefine (destination) ulaşması için kullanılması gereken katılımcıdır. Her katılımcı, diğer katılımcılara ulaşmak için kullanması gereken next hop katılımcıyı sürekli hesaplar.

Duplicate Detection Nedir
Döngü (Loop) static yönlendirme protokollerinde bile kazara yapılabiliyor. OLSR gibi daha dinamik ortamlarda olması zaten beklenen bir şey.

Döngülerden kaçınmak için OLSR belli bir süre geçmişi hatırlar. Örneğin 1 saniye veya x sayıda paket. Daha önce aldığı bir paket broadcast yüzünden tekrar kendisine gelirse duplicate detection bu paketi yakar ve işlemez.

Duplicate detection yönlendirme algoritmasının ilk adımı olabilir.

OLSR'da 3 Tablo Kullanılır
Bu tablolar mantıksal olarak 3 tanedir. Programlama yaparken belki tek bir veri yapısı bile yeterli olabilir.

1. Neighbor Sensing - One Hop Neigbor List
Her katılımcı kendi one hop komşularını sürekli takip eder. Komşuları symmetric veya asymmetric olarak sınıflandırır ve ağa söyler. Neighbor Sensing için Hello mesajları kullanılır.

The Hello messages are received by all one-hop neighbors, but are not forwarded

Hello mesajları her 2 saniyede bir gönderilir. Eğer bir katılımcıdan 3 Hello gönderim aralığında güncelleme alınmazsa komşuluk bilgisi değişir.

2. Two Hop Neighbor List
OLSR ağlarında tüm katılımcılar 1-hop ve 2-hop komşularını bilirler. Bu tablo MPR seçiminde kullanılır. Two Hop Neighbor List oluşturmak için Hello mesajı ve mesajın içindeki komşuluk bilgileri listesi kullanılır.

A node maintains information (obtained from the HELLO messages) about its one hop neighbors, the status of the link with these neighbors, a list of 2-hop neighbors that these one hop neighbors
give access to, and an associated holding time.

3. Ağ Topolojisi - Topology List
Routing işlemi için bazı bilgilerin katılımcılar arasında paylaşılması gerekir. OLSR Link State Routing mantığını kullanıyor. Bu mantıkta Link State çalıştıran routerlar tüm ağın topoloji bilgisine sahiptirler. Yani Link State routing tabloları herkeste aynıdır. Programlarken her router kendisinin root olduğu bir ağaç veya graph yapısı kullanır.

Each router within the area builds a topology tree of the area, with shortest paths to all other links/routers with itself as the root.

Tüm verinin eşzamanlı olması için proaktif bir yöntem izlenir ve düğümler belli aralıklarla kendi tablolarını yayınlarlar. Her satırda router komşusuna erişim maliyetini belirtir.

Böylece yukarıda bahsedilen gönderilmek istenen paket için Next Hop kolayca bulunur.

Ağ topolojisini oluşturmak için Topology Control (TC) mesajları kullanılır. TC mesajları tüm ağa broadcast edilir. TC mesajını alan bir MPR bu mesajı ileriye doğru forward eder.

Multi Point Relay - MPR
MPR broadcast için. Multi Point Relay yazısına taşıdım.

Multicast
OLSR ile multicast için 3 yöntem var.

1. SMOLSR : Simple Multicast OLSR
2. MOLSR : Multicast OLSR
3. MOST : Multicast Overlay Mininum Spanning Tree