一個主機(jī)通常與一臺路由器相連接，該路由器即為主機(jī)的默認(rèn)路由器。
源主機(jī)的默認(rèn)路由器稱作源路由器，目的主機(jī)的默認(rèn)路由器稱作目的路由器。
一個分組從源主機(jī)到目的主機(jī)的路由選擇問題即從源路由器到目的路由器的路由選擇問題。
路由選擇算法可分為：
- 全局式路由選擇算法：所有路由器掌握完整的網(wǎng)絡(luò)拓?fù)浜玩溌焚M用信息，例如鏈路狀態(tài)（LS）路由算法
- 分散式路由選擇算法：路由器只掌握物理相連的鄰居以及鏈路費用，例如距離向量（DV）路由算法
下面主要介紹鏈路狀態(tài)路由算法（Link-stage）中的一種典型算法OSPF算法。
一、OSPF是什么
Open Shortest Path First, 開放最短路徑優(yōu)先協(xié)議，是一種開源的使用最短路徑優(yōu)先（SPF）算法的內(nèi)部網(wǎng)關(guān)協(xié)議（IGP）。常用于路由器的動態(tài)選路。
二、OSPF常見的幾個概念
- 鄰居（Neighbor）：宣告OSPF的路由器（也可能是通過quagga軟件配置的普通服務(wù)器）從所有啟動OSPF協(xié)議的接口上發(fā)出Hello數(shù)據(jù)包。如果兩臺路由器位于同一條數(shù)據(jù)鏈路上，并且它們根據(jù)互相的hello消息中指定的某些信息（比如id等）協(xié)商成功，那么它們就成為了鄰居（Neighbor）。
- 鄰接關(guān)系（Adjacency）：兩臺鄰居路由器之間構(gòu)成的一條點到點的虛鏈路，鄰接關(guān)系的建立是由交換hello信息的路由器類型和網(wǎng)絡(luò)類型決定的。
- 鏈路狀態(tài)通告（Link State Advertisement，LSA）：每一臺路由器都會在所有形成鄰接關(guān)系的鄰居之間發(fā)送鏈路狀態(tài)通告LSA。LSA描述了路由器所有的鏈路、接口、鄰居等信息。ospf定義了許多不同的LSA類型。
- 鏈路狀態(tài)數(shù)據(jù)庫（LSDB）：每一臺收到來自鄰居路由器發(fā)出的LSA的路由器都會把這些LSA信息記錄在它的LSDB中，并且發(fā)送一份LSA的拷貝給該路由器的其他所有鄰居。這樣當(dāng)LSA傳播到整個區(qū)域后，區(qū)域內(nèi)所有的路由器都會形成同樣的LSDB。
三、OSPF的基本原理
OSPF算法是讓每個路由器中的數(shù)據(jù)庫儲存整個網(wǎng)絡(luò)的拓?fù)鋱D，即每個路由器掌握了全局的信息，此時這個網(wǎng)絡(luò)趨于穩(wěn)定，便可以使用單源最短路徑（Dijkstra）來選擇路由。
每個路由器與其鄰居的通信行為有以下幾種：
1.保持聯(lián)系
整個自治系統(tǒng)中，每個路由器都有唯一標(biāo)識RouterID(32-bit). 與其每個鄰居間隔30s，發(fā)送一次Hello 報文，意思就是你還活著嗎？
二者相互通信發(fā)送Hello，并收到對方回應(yīng)Hello。雙方會周期性將自己的路由數(shù)據(jù)摘要發(fā)送給對方，一般30min，平時，
雙方只是聯(lián)系感情，直到對方?jīng)]有掛。
2.告知現(xiàn)今情況
如圖，R1會周期性地將自己的路由摘要發(fā)送給所有鄰居。比如對R6路由器，R1會發(fā)送
稱為DD報文的包，里面會說自己認(rèn)識R6,R2,R4,R5,R6對比自己的信息庫發(fā)現(xiàn)
除了自己R1的朋友它一個都不認(rèn)識，于是就發(fā)送請求報文，請求告知這些不認(rèn)識的
路由詳情。這個請求報文稱為LSR(鏈路狀態(tài)請求報文)報文。
R1收到之后，直到R6還不認(rèn)識自己另外三個朋友，于是發(fā)送LSU報文（鏈路狀態(tài)更新）告知R6詳情。R6收到之后，給R1個確認(rèn)-LSAck報文。兩個人現(xiàn)在認(rèn)識的路由器一樣多了，此時兩個人是好基友了-全毗鄰關(guān)系。
四、Dijkstra算法
Dijkstra算法是典型的LS路由算法，可計算在網(wǎng)絡(luò)中從一個節(jié)點到所有其他節(jié)點的最短路徑。
之前在數(shù)據(jù)結(jié)構(gòu)課上已經(jīng)初步學(xué)習(xí)過這個算法，代碼直接給出。
#include "stdio.h"
#include"stdlib.h"
#define MAX 30000
int n;
int Arraya[100][100];
int BeginningPath()//說明初始化的路由連接信息
{
int i,j,t;
printf("請輸入節(jié)點的個數(shù)：");
scanf("%d",&n);//一共有n個節(jié)點
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
printf("從第%d個節(jié)點到第%d個節(jié)點的費用：",i,j);
scanf("%d",&t);
if(t==-1) t=40000; //-1表示 ∞
Arraya[j][i]=t;
Arraya[i][j]=t;
}
Arraya[i][i]=0;
}
printf("\n\n在交換路由之前 : \n");
for(i=0;i<n;i++)//顯示初始化的數(shù)據(jù)
{
printf("\t");
for(j=0;j<n;j++)
{
if(Arraya[i][j]==40000)
printf("∞ ");
else
printf("%d ",Arraya[i][j]);
}
printf("\n");
}
return 0;
}
void Dijkstra(int s) //求以s為源點到各點的最小路徑及花費
{
int flag[100],d[100]={0},next[100]={0}; //已知節(jié)點集合，距離矢量，下一跳
int i,j;
for(i=0;i<n;i++)//初始化
{
d[i]=Arraya[s][i];
flag[i]=0;
next[i]=i;
}
flag[s]=1; //把源節(jié)點加入已知最短路徑距離節(jié)點的集合
int k=s,min;
for(i=0;i<n;i++)
{
min=MAX;
for(j=0;j<n;j++)//找出最小值d[k]
if(d[j]<min&&flag[j]==0)
{
min=d[j]; //尋找節(jié)點i的鄰居中最近的節(jié)點，記錄最小值及節(jié)點序號
k=j;
}
if(k==s) return ; //k值沒有改變說明沒有鄰居
flag[k]=1;//標(biāo)志是否放入集合
for(j=0;j<=n;j++)//松弛鄰邊（以新的已知集合構(gòu)造新的與未知集合節(jié)點的距離）
if(d[j]>Arraya[k][j]+d[k]&&flag[j]==0)
{
d[j]=Arraya[k][j]+d[k];
next[j]=next[k]; //到j(luò)節(jié)點的路徑下一跳為中間點k，即到k的路徑的下一跳
}
}
printf("r%d next cost\n",s);
for(i=0;i<n;i++)
{
if(i==s)
continue;
printf("%d : %d %d\n",i,next[i],d[i]);
}
}
int main()
{
int i;
BeginningPath();
for(i=0;i<n;i++)
Dijkstra(i);
return 0;
}
假如我通過OSPF形成的網(wǎng)絡(luò)拓?fù)鋱D如下圖，則可通過Dijkstra算法計算結(jié)果。
運行結(jié)果如圖
參考鏈接：
OSPF的基本原理
OSPF路由算法-Zoom in
LS鏈路狀態(tài)路由算法
路由選擇算法 LS DV
