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.