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

OLSR Multi Point Relay - MPR

Giriş
Açıklaması şöyle

The OLSR backbone for message flooding is composed of Multipoint Relays. Each node must select MPRs from among its symmetric neighbor nodes such that a message emitted by a node and repeated by the MPR nodes will be received by all nodes two hops away. In fact, in order to achieve a network-wide broadcast, a broadcast transmission needs only be repeated by just a subset of the neighbors: this subset is the MPR set of the node. Hence only MPR nodes relay TC, MID, and HNA messages.

OLSR, MANET'lerde broadcast paketlerin flood edilmesini asgariye indirmeye çalışır. Her katılımcı bir MPR - yani kendisi için röle - seçer. MPR'ın görevi broadcast paketleri hem kendisi için işlemek, hem de ağa tekrar göndermektir. Böylece broadcast paketler tüm ağa daha verimli bir şekilde yayılır. Yani flooding yapan katılımcı sayısı azaltılır.

MPR seçimi yapabilmek için Two Hop Neighbor List'in elimizde olması ön koşuldur.


Yöntem 1
MPR seçmek için bir katılımcı 2 hop uzaklıktaki tüm komşularının listesini alır. Sonra bu listedeki her katılımcıya ulaşmak için shortest path'i hesaplar. Shortest path'in ilk düğümü olan kendim komşularımın distinct kümesini alırsak MPR seçimini yapmış oluruz.

2 hop uzaklıktaki komşuları bulmanın kolay bir yolu şöyle. Eğer "routing" hesabı yaparken bir düğüme nasıl gideceğim bilgisi + nereden geldiğim bilgisini saklarsam şöyle yaparız.

foreach node :
  if (nextHop == prevHop) then node is 2 hop neighbor

Yöntem 1 İçin Basit Kodlama
1. Topoloji değişirse MPR hesaplaması en baştan yapılır. Eğer bir katılımcıdan güncelleme alınır ancak topoloji değişmezse MPR hesaplaması yapmaya gerek yoktur.

2. OLSR bir subnette çalışıyorsa en fazla 255 katılımcı olabilir.

3. MPR seçimi için basitçe tüm katılımcılara olan next hop bilgisini bir set'e doldurmak yeterli.

Node isimli bir yapı olsun. Her Node kendi içinde komşularını bilsin. Ayrıca bu düğüme erişmenin maliyet olsun.

Route isimli bir yapı olsun. Bu yapıda Toplam Maliyet, Toplam Hop Sayısı , Next Hop, Previous Hop bilgileri olsun

Önce kendi Node nesnemi gezip- visited - olarak işaretlerim.

Daha sonra erişim maliyeti en küçük olan düğümden başlayarak gezerim. Bu düğüm ilk başta kendi komşum olacaktır. Komşum olduğu icin next hop degeri kendisi olacaktır.

Bir düğümün tüm komşularına olan "toplam " maliyeti hesaplarım. Bu düğümü visited olarak işaretlerim.

A->B->C->D olsun.

A kendisini visited olarak işaretler. B için next hop olarak tabloya B yazar.

Maliyeti en küçük olan B seçilir. B'nin tüm komşuları dolaşılır ve "toplam" maliyet hesaplanır. Ayrıca her komşu için next hop olarak B'ye gidiş next hop değeri yazılır.

Yani C'ye gidiş için next hop B'dir.

Maliyeti en küçük C seçilir. C'nin tüm komşuları dolaşılır ve "toplam" maliyet hesaplanır. Her komşu için next hop olarak C'ye gidiş next hop değeri yazılır. C için next hop B idi. Yani D'ye gidiş için next hop B'dir.

Yöntem 2
2 hop ötedeki komşuluk graph'ını oluştur.
Bottom-up ilerleyerek tek atası olan komşuları MPR seç. Bu komşuları graph'tan sil
Ulaşmak için çok atası olan komşuları seç. Bağlantı sayısı en çok fazla olanı MPR seç.

MPR Örnekleri
Şöyle bir Routing tablomuz şöyle olsun.

6<--> 3<-->Ben >-->1 <--> 4
                                        |->5

4 'e erişmek için  : 1
5 'e erişmek için  : 1
6'ya erişmek için  : 3
kullanırız.
1,1,3 nolu katılımcıların distinct listesi 1 ve 3'tür. Dolayısıyla benim MPR'larım 1 ve 3'tür.

Şimdi şöyle bir ağ düşünelim

           A
           / \
          B   C
         / \
        D   E
           / \
          F   G

A MPR olarak B'yi seçer. B MPR olarak E'yi seçer. A bir paketi broadcast eder. B bu paketi alır. Kendisi işler, sonra tekrar broadcast ederi. E çıkış noktası A olan paketi alır. Kendisi işler ve broadcast eder. F ve G bu paketi alır ve işleler. Böylece tüm ağ broadcast paketini duyar.

Daha karışık bir ağ düşünelim

-------A---------
|    |     |   |    |   |
B  C  D  E  F  G
  \/   \/  \/  \/  \/
  H  I    J   K  L

Bu ağda MPR olarak C,E,F veya C,E,G MPR seçilebilir.