RRAS Routing and Remote Access Service (Farsi User Guide)
Resource: Windows 2000 Server Resource kit Internetworking Guide

Winteacher.com > Part2 > RRAS > Step2 > OSPF > OSPF Operation

OSPF Operation

فرایند و یا مراحل کاری  یک OSPF Protocol  در زیر شرح داده شده .

  1. Compiling the LSDB.

  2. Calculating the Shortest Path First (SPF) Tree.

  3. Creating the routing table entries.

 
Compiling the LSDB

کلیه ROUTER های مجاور هم در یک AS شروع به ارسال  LSAs Traffic می کنند تا LSDB های خود را به یکدیگر معرفی کنند در این زمان طوفانی از LSAs Traffic در Internetwork ایجاد می شود

در این زمان کلیه External Route LSAs ها و نیز Valid LSAs ها نیز برای تمامی ROUTER ها شناخته می شود .تا همه LSDB های موجود در کلیه ROUTER ها یکسان و همگرا شود .

Figure 3.11 OSPF Link State Database (LSDB)

زمانی که این مرحله به پایان رسید کلیه LSDB های شبکه ها همگرا می شوند .برای دیدن اطلاعات موجود در LSDB می توانید مراحل زیر را انجام دهید .

 
You can view the current OSPF link state database by right-clicking the OSPF routing protocol and clicking Show Link State Database in the Routing and Remote Access snap-in.
 

Example 1 LSDB Table

در شکل Example 2 می توانید اجزا  شبکه نسبت به LSDB تشکیل شده در Example 1 را مشاهده کنید .

 

Example 2 Network Infrastructure for LSDB Table

Router ID

هر ROUTER در شبکه یک ID دارد که این ID با IP Address موجود بر روی Interface های آن ROUTER متفاوت می باشد . البته به دلیل اینکه هر ROUTER یک IP Address ثابت دارد

به همین دلیل باید دارای ROUTER ID ثابت باشد .ترافیک بین ROUTER ها نیازی به ROUTER ID ندارد و با IP Address هر Router فعالیت می کند .

 
 

Calculating the Shortest Path First (SPF) Tree

Once the LSDB is compiled, each OSPF router performs a least cost path calculation called the Dijkstra algorithm on the information in the LSDB and creates a tree of shortest paths to each other router and network with themselves as the root. This tree is known as the SPF Tree and contains a single, least cost path to each router and network in the AS. Because the least cost path calculation is performed by each router with itself as the root of the tree, the SPF tree is different for each router in the AS.

The Dijkstra algorithm is from a branch of mathematics called graph theory and is an efficient method of calculating a set of least cost paths relative to a source node.

To Calculate the SPF Tree Using the Dijkstra Algorithm

The result of the Dijkstra algorithm is the set SPF{}, a cost sorted list of least cost paths containing the path (the series of nodes and links) and its accumulated cost from the source node S.

  1. Define the set E{} to be the set of nodes (routers) that have been evaluated.

  2. Define the set R{} to be the set of nodes (routers) that are remaining (have not been evaluated).

  3. Define the set O{} to be a cost-sorted list of ordered paths between nodes. An ordered path can consist of multiple nodes connected together in a multi-hop configuration (they do not have to be neighboring).

  4. Define the set SPF{} to be a cost-sorted list of least cost paths containing the path and its accumulated cost.

  5. Initialize the set E{} to contain the source node S and the set R{} to contain all other nodes. Initialize the set O{} to be the cost-sorted list of directly connected paths from S. Initialize the set SPF{} to be the empty set.

  6. If O{} is empty or the first path in O{} has an infinite metric, mark all the nodes in R as unreachable and terminate the algorithm.

  7. From the set O{}, examine P, the shortest ordered path in O{}. Remove P from O{}. Let V be the last node on the ordered path of P.

    If V is already a member of E{}, return to step 6.

    – Or –

    If P is the shortest path to V, move V from R{} to E{}. Add a member to the set SPF{} consisting of P and its accumulated cost from S.

  8. Build a new set of paths by concatenating P and each of the links adjacent to V. The cost of these paths is the sum of the cost of P and the metric of the link appended to P. Insert the new links in the set O{} and sort by cost. Return to step 6.

Calculating the Routing Table Entries from the SPF Tree

The OSPF routing table entries are created from the SPF tree, and a single entry for each network in the AS is produced. The metric for the routing table entry is the OSPF-calculated cost, not a hop count.

To calculate the IP routing table entries from the SPF Tree, the resulting set SPF{} is analyzed. The result of the analysis is a series of OSPF routes containing the IP destination (the network ID) and its network mask (subnet mask), the forwarding IP address of the appropriate neighboring router, the interface over which the neighboring router is reachable, and the OSPF-calculated cost to the network. The OSPF routes are added to the IP routing table.

 
 
Example of OSPF Operation

در یک Internetwork  کلیه ROUTER ها بعد از اینکه مرحله اول یعنی  Compiling the LSDB   را انجام دادند در مرحله بعد شرع به ساختن Routing Table خود و دادن ارزش به هر Route

می کنند . ارزش دهی به هر Route بر اساس Bandwidth و Delay و تغییرات Admin مشخص می شود .یعنی هر Net ID در Routing Table  دارای موقعیت خوبی در این موارد باشد در نتیجه ارزش

بالا تری دارد .تذکر ارزش بالاتر بعنی Metric کمتر .

Figure 3.12 AS with Link State Database Information

زمانی که LSAs Traffic بین Intermediate systems  ها به پایان رسید یک جور همگرایی بین ROUTER ها ایجاد شده در این زمان LSDB موجود در ROUTER ها همانند جدول  زیر می شود .

 
Router Attached Networks and Costs
R1 Net 1-Cost 2, Net 3-Cost 5, Net 4-Cost 2
R2 Net 1-Cost 1, Net 2-Cost 4, Net 6-Cost 2
R3 Net 2-Cost 4, Net 3-Cost 2, Net 5-Cost 3, Net 7-Cost 2
R4 Net 4-Cost 3, Net 5-Cost 2
R5 Net 6-Cost 2, Net 7-Cost 3

Table 3.1 Link State Database

 
Calculating the SPF Tree

در مرحله بعد Intermediate Systems شروع به کارمی کند  توسط Dijkstra's الگوریتم یرای ایجاد  یک SPF Tree برای آشنایی بیشتر با SPF Tree به قسمت

Calculating the Shortest Path First (SPF) Tree مراجعه کنید .

در شکل زیر نتیجه کار را مشاهده می کنید در اینجا ROUTER 4 به عنوان Root  در این SPF Tree شناخته شده .

Figure 3.13 SPF Tree

شکل 3.13 یک SPF Tree از Internetwork ما در شکل 3.12 می باشد . ارزشی که برای شبکه های متفاوت مشخص شده ارزشهایی مب باشند که R4 در LSDB خود در نظر گرفته .

 
Creating Routing Table Entries

ساختن  یک Routing Table در آخر بر اساس SPF Tree ساخته می شود همانند شکل زیر .

 

Figure 3.14 Routing Table Entries

 
RRAS Routing and Remote Access Service (Farsi User Guide)

LastUpdate:2005/04/05

Winteacher.com > Part2 > RRAS > Step2 > OSPF > OSPF Operation