Distance Vector and Link State: Bellman-Ford and Dijkstraمەودای ئاڕاستە و بارودۆخی بەستەر: بێڵمان-فۆرد و دایکسترا

Almost every interior routing protocol belongs to one of two families, and they differ in what a router knows. In a distance-vector protocol a router knows only what its neighbours tell it: for each network, how far it is and which way to send. In a link-state protocol every router learns the whole map of its area and works out the routes itself. The first is like asking for directions at every junction; the second is like everyone holding the same city map.

نزیکەی هەموو پرۆتۆکۆڵەکانی ڕێدۆزیی ناوخۆیی سەر بە یەکێک لە دوو بنەماڵەن و جیاوازییان لەوەدایە کە ڕێدۆز چی دەزانێت. لە پرۆتۆکۆڵێکی مەودای ئاڕاستەـدا ڕێدۆز تەنیا ئەوە دەزانێت کە دراوسێکانی پێی دەڵێن: بۆ هەر ڕایەڵەیەک (Network)، چەند دوورە و بە کام لادا بنێرێت. لە پرۆتۆکۆڵێکی بارودۆخی بەستەرـدا هەموو ڕێدۆزێک نەخشەی تەواوی ناوچەکەی فێر دەبێت و خۆی ڕێگەکان حیساب دەکات. یەکەمیان وەک پرسیارکردنی ڕێگایە لە هەموو چواڕیانێک؛ دووەمیان وەک ئەوەیە کە هەمووان هەمان نەخشەی شاریان پێ بێت.

OSPF and IS-IS are link-state protocols; RIP is the classic distance-vector protocol. The family tree with EIGRP and BGP is in Routing protocols.

OSPF و ⁦IS-IS⁩ پرۆتۆکۆڵەکانی بارودۆخی بەستەرن؛ RIP نموونەی کلاسیکی مەودای ئاڕاستەیە. داری بنەماڵەکە لەگەڵ EIGRP و BGP لە پرۆتۆکۆڵەکانی ڕێدۆزیدایە.

The name says it. For every network a distance-vector router keeps a distance — the cost of the path, measured for example in hops or in delay — and a vector, a direction: the next hop and the interface towards it. It does not have a map; it asks its neighbours for directions and believes their answers. Every router sends its whole routing table to its neighbours at regular times — RIP every 30 seconds — even when nothing has changed, and builds its own table from what they send. The news moves through the network one neighbour at a time.

ناوەکە خۆی دەیڵێت. ڕێدۆزێکی مەودای ئاڕاستە بۆ هەر ڕایەڵەیەک مەودایەک هەڵدەگرێت — تێچووی ڕێگاکە، بۆ نموونە بە باز (Hop) یان بە دواکەوتن (Latency) دەپێورێت — و ئاڕاستەیەک ⁦(vector)⁩: بازی دواتر (Next hop) و ئەو نێوبەستەیەی (Interface (network)) بەرەو ئەو دەچێت. نەخشەی نییە؛ داوای ڕێنمایی لە دراوسێکانی دەکات و باوەڕ بە وەڵامەکانیان دەکات. هەموو ڕێدۆزێک لە کاتی دیاریکراودا هەموو خشتەی ڕێدۆزییەکەی (Routing table) بۆ دراوسێکانی دەنێرێت — RIP هەموو ⁦30⁩ چرکە جارێک — تەنانەت ئەگەر هیچ شتێک نەگۆڕابێت. خشتەی خۆیشی لەوەی ئەوان دەینێرن دروست دەکات. هەواڵ دراوسێ بە دراوسێ بە ڕایەڵەدا دەڕوات.

Three routers A – B – C sit between four networks, 10.1.0.0/16 to 10.4.0.0/16. At the start each router knows only its two connected networks (0 hops). After the first exchange every router has heard its neighbours’ networks and added them with the neighbour’s hops + 1. After the second exchange news from two routers away arrives: for example B tells C “I know 10.1, 10.2 and 10.3”, and C adds 10.1 (2 hops) and keeps 10.2 (1 hop). Now every table lists all four networks — the network has converged.

سێ ڕێدۆز، ⁦A – B – C⁩، لە نێوان چوار ڕایەڵەدان، ⁦10.1.0.0/16⁩ تا ⁦10.4.0.0/16⁩. لە سەرەتادا هەر ڕێدۆزێک تەنیا دوو ڕایەڵەیە بەستراوەکەی خۆی دەزانێت (⁦0⁩ باز). دوای یەکەم ئاڵوگۆڕ، هەموو ڕێدۆزێک ڕایەڵەکانی دراوسێکانی بیستووە و بە ژمارەی بازەکانی دراوسێ + 1 زیادی کردوون. دوای ئاڵوگۆڕی دووەم هەواڵی دوو ڕێدۆز دوورتر دەگات: بۆ نموونە B بە C دەڵێت «⁦10.1⁩، ⁦10.2⁩ و ⁦10.3⁩ دەناسم» و C ڕێگەی ⁦10.1 (2⁩ باز) زیاد دەکات و ⁦10.2 (1⁩ باز) دەهێڵێتەوە. ئێستا هەموو خشتەیەک هەر چوار ڕایەڵەکەی تێدایە — ڕایەڵەکە گەیشتووەتە پێکگەیشتن (Convergence (routing)).

Distance-vector protocols compute their routes with the Bellman-Ford algorithm, a piece of mathematics from the 1950s (Richard Bellman and Lester Ford). Its rule is short: my distance to a network is the smallest value of “a neighbour’s distance to it + the cost of my link to that neighbour”. Each router applies it to the tables its neighbours send, again and again, until nothing changes.

پرۆتۆکۆڵەکانی مەودای ئاڕاستە ڕێگەکانیان بە ئەلگۆریزمی بێڵمان-فۆرد (Bellman-Ford algorithm) حیساب دەکەن، کە بیرۆکەیەکی بیرکاریی دەیەی ⁦1950⁩ـە (ڕیچارد بێڵمان و لێستەر فۆرد). یاساکەی کورتە: مەودای من بۆ ڕایەڵەیەک بچووکترین بەهای «مەودای دراوسێیەک بۆی + تێچووی بەستەرەکەم بۆ ئەو دراوسێیە»ـیە. هەر ڕێدۆزێک ئەم یاسایە بەسەر ئەو خشتانەدا جێبەجێ دەکات کە دراوسێکانی دەینێرن، دووپاتە و دووپاتە، تا هیچ شتێک ناگۆڕێت.

Here is a small network with link costs: A–B 5, A–C 2, C–B 1 and B–D 4. We compute every distance from A in rounds; in each round every node uses the values its neighbours had at the end of the round before, just as routers use the last table they received.

ئەمە ڕایەڵەیەکی بچووکە بە تێچووی بەستەرەکانەوە: ⁦A–B 5⁩، ⁦A–C 2⁩، ⁦C–B 1⁩ و ⁦B–D 4⁩. هەموو مەوداکان لە Aـەوە بە چەند گەڕێک حیساب دەکەین؛ لە هەر گەڕێکدا هەر نۆدێک (Node) ئەو بەهایانە بەکار دەهێنێت کە دراوسێکانی لە کۆتایی گەڕی پێشوودا هەیانبوو، وەک چۆن ڕێدۆزەکان دوایین خشتەی وەرگیراو بەکار دەهێنن.

Two lessons hide in the table. First, a path with more links can be cheaper: B is reached through C for 3, not directly for 5. Second, good news needs several rounds to travel — D’s best value, 7, appears only in round 3. In routing all link costs are positive; Bellman-Ford can also handle negative costs, but metrics are never negative.

دوو وانە لە خشتەکەدا شاراونەتەوە. یەکەم، ڕێگایەک بە بەستەری زیاتر دەتوانێت هەرزانتر بێت: B بە 3 لە ڕێی Cـەوە دەگەیەنرێت، نەک ڕاستەوخۆ بە 5. دووەم، هەواڵی باش چەند خولێکی پێویستە بۆ گەیشتن — باشترین بەهای D (کە 7ـە) تەنیا لە گەڕی 3دا دەردەکەوێت. لە ڕێدۆزیدا (Routing) هەموو تێچوویەکی بەستەر ئەرێنییە؛ بێڵمان-فۆرد دەتوانێت تێچووی نەرێنیش چارەسەر بکات، بەڵام پێوانەکان (Metric (routing)) هەرگیز نەرێنی نین.

Distance vector is simple and needs little memory or CPU, but it has two weaknesses. Changes spread slowly: news crosses one router per exchange, and each exchange may wait for the 30-second timer. And because a router believes distances it cannot check, old news can create routing loops and counting to infinity, which need extra rules to stop (the five cures). That is why large and complex networks use link-state protocols such as OSPF and IS-IS.

مەودای ئاڕاستە سادەیە و بیرگە و CPUـی کەمی پێویستە، بەڵام دوو لاوازیی هەیە. گۆڕانەکان بە خاوی بڵاو دەبنەوە: هەواڵ لە هەر ئاڵوگۆڕێکدا تەنیا یەک ڕێدۆز دەبڕێت و لەوانەیە هەر ئاڵوگۆڕێک چاوەڕێی تایمەری (Timer) ⁦30⁩ چرکەیی بکات. هەروەها چونکە ڕێدۆز باوەڕ بەو مەودایانە دەکات کە ناتوانێت بیانپشکنێت، هەواڵی کۆن دەتوانێت ئەڵقەکانی ڕێدۆزی و ژماردن تا بێسنوور (Infinity) دروست بکات، کە پێویستیان بە یاسای زیاترە بۆ وەستاندنیان (پێنج چارەسەرەکە). لەبەر ئەوە ڕایەڵەکانی گەورە و ئاڵۆز پرۆتۆکۆڵەکانی بارودۆخی بەستەر وەک OSPF و ⁦IS-IS⁩ بەکار دەهێنن.

“Link” means a connection between two devices, wired or wireless; “state” means its condition — up or down, and its cost. A link-state router therefore knows the state of every link in its area. It gets there in three steps. 1. It meets its neighbours with small hello messages. 2. It describes its own links in a link-state advertisement (LSA) and floods it: every router passes each new LSA on to its other neighbours, so all routers in the area collect the same LSAs into the same link-state database (LSDB) — the map. 3. Each router runs Dijkstra’s algorithm, also called SPF (shortest path first), on that map, with itself as the root, and puts the result into its own routing table.

«بەستەر» ⁦(link)⁩ واتە پەیوەندییەک لە نێوان دوو ئامێردا، بە وایەر یان بێ وایەر؛ «بارودۆخ» ⁦(state)⁩ واتە دۆخەکەی — کارایە یان پچڕاوە — لەگەڵ تێچووەکەی. بۆیە ڕێدۆزێکی بارودۆخی بەستەر بارودۆخی هەموو بەستەرێکی ناوچەکەی دەزانێت. بە سێ هەنگاو دەگاتە ئەوێ. 1. بە پەیامی بچووکی سڵاو دراوسێکانی دەناسێت. 2. بەستەرەکانی خۆی لە LSAـیەکدا ⁦(link-state advertisement)⁩ وەسف دەکات و لافاوکردنی (Flooding) دەکات: هەموو ڕێدۆزێک هەر LSAـیەکی نوێ بۆ دراوسێکانی تری دەنێرێت، بۆیە هەموو ڕێدۆزەکانی ناوچەکە هەمان LSAـەکان لە هەمان LSDBـدا کۆ دەکەنەوە — نەخشەکە. 3. هەر ڕێدۆزێک ئەلگۆریزمی دایکسترا، کە پێی دەگوترێت ⁦SPF (shortest path first)⁩، بە خۆی وەک ڕەگ لەسەر ئەو نەخشەیە جێبەجێ دەکات و ئەنجامەکە دەخاتە ناو خشتەی ڕێدۆزییەکەی خۆیەوە.

When a link changes, only that news is flooded, at once — not whole tables every 30 seconds — and every router recalculates in parallel. So link state converges quickly. OSPF’s version of these three steps, with its LSAs, areas and cost, is in OSPF concepts.

کاتێک بەستەرێک دەگۆڕێت، تەنیا ئەو هەواڵە یەکسەر بڵاو دەکرێتەوە — نەک هەموو خشتەکان لە هەر ⁦30⁩ چرکەیەکدا — و هەموو ڕێدۆزێک هاوکات دووپاتە حیساب دەکاتەوە. بۆیە بارودۆخی بەستەر خێرا دەگاتە پێکگەیشتن. ئەم سێ هەنگاوە لە OSPFـدا، لەگەڵ LSA، ناوچەکان (Area (OSPF)) و تێچووەکەی، لە چەمکەکانی OSPFدایە.

Dijkstra’s algorithm finds the shortest paths from one node of a graph to all the others. The Dutch computer scientist Edsger Wybe Dijkstra worked it out in 1956 and published it in 1959. Each link of the graph carries a number, its weight, which can mean different things: the travel time between two places on a city map, how crowded a road is, or, in a social network such as Facebook, how strong a friendship is. In networking the weight is the metric: OSPF’s cost.

ئەلگۆریزمی دایکسترا کورتترین ڕێگەکان (Shortest path) لە یەک نۆدی گرافێکەوە (Graph) بۆ هەموو ئەوانی تر دەدۆزێتەوە. کۆمپیوتەرزانی هۆڵەندی ئێدسخەر ویبە دایکسترا ⁦(Edsger Wybe Dijkstra)⁩ لە ساڵی ⁦1956⁩دا دایهێنا و لە ⁦1959⁩دا بڵاوی کردەوە. هەر بەستەرێکی گرافەکە ژمارەیەکی لەسەرە، کێشەکەی ⁦(weight)⁩، کە دەتوانێت واتای جیاوازی هەبێت: کاتی گەشت لە نێوان دوو شوێن لەسەر نەخشەی شارێک، ئاستی قەرەباڵغیی ڕێیەک، یان لە تۆڕێکی کۆمەڵایەتیی وەک فەیسبووکدا، بەهێزیی هاوڕێیەتییەک. لە ڕایەڵەدا کێشەکە پێوانەکەیە: تێچووی OSPF.

Dijkstra’s algorithm runs inside OSPF and IS-IS. In AI the same algorithm is called uniform-cost search, and A* search adds a guess of the remaining distance.

ئەلگۆریزمی دایکسترا لە ناو OSPF و ⁦IS-IS⁩ـدا کار دەکات. لە ژیریی دەستکرددا هەمان ئەلگۆریزم (Algorithm) پێی دەگوترێت گەڕانی کەمترین کۆست و گەڕانی ⁦A*⁩ مەزەندەیەکی دووری تا ئامانج زیاد دەکات.

Find the shortest path from B to F in a small graph with the weights B–E 6, B–D 5, D–E 3, E–F 1 and D–F 2. Watch the table: green rows are finished, the orange row is the node being visited.

کورتترین ڕێگە لە Bـەوە بۆ F بدۆزەرەوە لە گرافێکی بچووکدا بە کێشەکانی ⁦B–E 6⁩، ⁦B–D 5⁩، ⁦D–E 3⁩، ⁦E–F 1⁩ و ⁦D–F 2⁩. سەیری خشتەکە بکە: دێڕە سەوزەکان تەواون، دێڕە پرتەقاڵییەکە ئەو نۆدەیە کە سەردانی دەکرێت.

So the shortest path from B to F costs 7: B–D–F (5 + 2). Look closely, though: B–E–F (6 + 1) costs 7 too. There are two shortest paths. Dijkstra’s algorithm keeps the first one it found unless told otherwise; OSPF would put both into the routing table and share the traffic between them (equal-cost paths).

کەواتە کورتترین ڕێگە لە Bـەوە بۆ F تێچووی 7ـە: ⁦B–D–F (5 + 2)⁩. بەڵام وردتر سەیر بکە: ⁦B–E–F (6 + 1)⁩ـیش 7ـە. دوو کورتترین ڕێگە هەن. ئەلگۆریزمی دایکسترا یەکەمیان دەهێڵێتەوە مەگەر بە شێوەیەکی تر پێی بگوترێت؛ OSPF هەردووکیان دەخاتە ناو خشتەی ڕێدۆزییەوە و هاتوچۆ لە نێوانیاندا دابەش دەکات (ڕێگەی تێچوو یەکسان).

The same idea guides map and navigation apps — Google Maps, Apple Maps, Maps.me, Sygic — as well as transport planning and the sharing out of resources. Real map apps use faster relatives of it, such as A* and pre-computed shortcuts, because a country’s road map is huge.

هەمان بیرۆکە ئەپەکانی نەخشە و ڕێنیشاندانیش ڕێنمایی دەکات — Google Maps، Apple Maps، ⁦Maps.me⁩، Sygic — هەروەها پلاندانانی گواستنەوە و دابەشکردنی سەرچاوەکان. ئەپە ڕاستەقینەکانی نەخشە خزمە خێراترەکانی بەکار دەهێنن، وەک ⁦A*⁩ و کورتەڕێی پێشوەختە حیسابکراو، چونکە نەخشەی ڕێگاکانی وڵاتێک زۆر گەورەیە.

The picture is a small road map. Each number is how crowded that road is — the weight. Use Dijkstra’s algorithm to find the least crowded way from home to school.

وێنەکە نەخشەیەکی بچووکی ڕێگاکانە. هەر ژمارەیەک ئاستی قەرەباڵغیی ئەو ڕێیەیە — کێشەکە. ئەلگۆریزمی دایکسترا بەکار بهێنە بۆ دۆزینەوەی کەمترین ڕێی قەرەباڵغ لە ماڵەوە بۆ قوتابخانە.

University courses compare the two families on the same points. The short version: link state means having a complete, accurate map; distance vector means sharing distances with your neighbours.

لە زانکۆکاندا هەردوو بنەماڵەکە لەسەر هەمان خاڵەکان بەراورد دەکرێن. کورتەکەی: بارودۆخی بەستەر واتە هەبوونی نەخشەیەکی تەواو و ورد؛ مەودای ئاڕاستە واتە بەشکردنی مەوداکان لەگەڵ دراوسێکانت.

BGP is not a distance-vector protocol. It is a path-vector protocol: every route carries the list of autonomous systems it has passed through (the AS path). A router that finds its own AS number in that list refuses the route, so BGP cannot loop the way RIP does, and each network chooses routes by its own policy. EIGRP learns routes from its neighbours like a distance-vector protocol, but its DUAL algorithm keeps a loop-free backup route (a feasible successor) ready, so it switches at once when the best path fails. It is an advanced distance-vector protocol — not a link-state one.

BGP پرۆتۆکۆڵێکی مەودای ئاڕاستە نییە. پرۆتۆکۆڵێکی ڕێڕەوی ئاڕاستەیە: هەر ڕێگەیەک لیستی هەموو سیستەمە سەربەخۆکانی (Autonomous system) سەر ڕێگاکەی هەڵدەگرێت (ڕێڕەوی AS). ڕێدۆزێک کە ژمارەی ASـی خۆی لەو لیستەدا ببینێت ڕێگەکە ڕەت دەکاتەوە، بۆیە BGP ناتوانێت وەک RIP بسووڕێتەوە و هەر ڕایەڵەیەک بەپێی سیاسەتی خۆی ڕێگەکان هەڵدەبژێرێت. EIGRP وەک پرۆتۆکۆڵێکی مەودای ئاڕاستە ڕێگەکان لە دراوسێکانییەوە فێر دەبێت، بەڵام ئەلگۆریزمی DUALـی ڕێگەیەکی یەدەگی بێ ئەڵقە (feasible successor) ئامادە دەهێڵێتەوە، بۆیە کاتێک باشترین ڕێگە دەپچڕێت یەکسەر دەگۆڕێت. پرۆتۆکۆڵێکی مەودای ئاڕاستەی پێشکەوتوو+ە — نەک بارودۆخی بەستەر.

Both are taught in their own lessons: EIGRP and DUAL and BGP and autonomous systems.

هەردووکیان لە وانەی خۆیاندا دەخوێنرێن: EIGRP و DUAL و BGP و سیستەمە سەربەخۆکان.

Next: the distance-vector protocol you will configure — RIP.

دواتر: ئەو پرۆتۆکۆڵی مەودای ئاڕاستەیەی ڕێکی دەخەیت — RIP.