Routing in packet switching networks

Routing:

-Пакетууд олон дундын төхөөрөмжөөр дайрч төгсгөлийн төхөөрөмжид хүрнэ.

-Packet-switching сүлжээнд пакетын дамжигдах замыг ямар нэгэн чиглүүлэлтийн алгоритмаар шийдэж өгдөг.

Чиглүүлэлт гэж юу вэ?

Пакетийн сүлжээгээр дамжин төгсгөлийн төхөөрөмжид хүрэх олон замуудаас хамгийн боломжит нэг зам-ын дизайн юм.

Чиглүүлэлтийн алгоритмын шинж чанар:

-Correctness and Simplicity:  Зөв дамжуулалт, хэт ярвигтай биш

-Robustness (Ухаалаг):  Сүлжээнд алдаа гарсан үед сүлжээ нь пакетын замыг өөрчилж боломжит замаар хүлээн авагчид хүргэдэг байх (Failure, Congestion)

-Stability(Баталгаа):  Алгоритм нь сүлжээний нөхцөлд зохицон өөрчлөгдөж, тэнцвэржүүлдэг байх

-Optimality:  Хамгийн сайн зохион байгуулалттай байх

-Efficiency:  Боломжит минимум нэмэлт мэдээлэлтэй байх (Minimum overhead)

Чиглүүлэлтийн параметр:

-Performance Criteria:  Number of hops, Cost, Delay, Throughput

-Decision Time: Per packet (Datagram), per session (Virtual-circuit)

-Decision Place:  Each node (distributed), Central node (centralized), Originated node (source)

-Network Information Source:  None, Local, Adjacent node, Nodes along route, All nodes

-Update Timing:  Fixed, Adaptive, Continuous, Periodic, Network topology change

Чиглүүлэлт хийх 2 төрлийн арга байдаг:

-Static

-Dynamic

Static Routing

Хэрхэн дараагийн төхөөрөмжийг сонгох вэ?

-Cost:  хамгийн үр ашигтай зам (Best Path)-ыг сонгох хэмжигдэхүүн

- Bandwidth:  их багтаамжтай шугамаар хурдан дамжиж Destination-д хүрэх

- Hop Count:  хамгийн цөөн дундын төрөөрөмж (Router)-өөр дамжиж Destination-д хүрэх

Дурын 2 төгсгөлийн төхөөрөмж хоорондын чиглүүлэлт нь Least-cost- хамгийн бага үнэлгээтэй байхаар сонгогдоно.

Хамгийн боломжит замыг тодорхойлох алгоритм :

-Dijkstra’s algorithm

 -Bellman-Ford algorithm

Пакетын давхардлыг арилгах

Hop-count:  Hop counter мэдээлэл нь пакетын толгой мэдээлэлд байх бөгөөд дундын төхөөрөмж бүрт хасагдах ба тоолуур тэг болоход пакетыг хаяна. Илгээгч төхөөрөмж тоолуурын мэдээллийг тодорхойлно. Хэрэв тодорхойлж чадахгүй бол subnet-ийн хязгаараар тодорхойлно.

Sequence number:  Пакетын замыг давхардуулахгүйн тулд дугаарлана. Дахин дамжуулахаас зайлсхийнэ.

Selective Flooding:  Замчлагч төхөөрөмж (Router)ирсэн пакетыг бүх интерфейсүүдээрээ бус зөвхөн төгсгөлийн төхөөрөмжид хөтлөх шугам руу гаргана.

Dynamic Routing

Packet-switching сүлжээнд ашиглагдана.  Сүлжээний өөрчлөлтөөр чиглүүлэлтийн шийдвэр өөрчлөгдөнө.

Замчлалын шийдвэрийг өөрчлөх хоёр хүчин зүйл:

 -Failure (Гэмтэл): Төхөөрөмжийн болон шугамын гэмтлээс болж чиглүүлэлтийг өөрчлөх шаардлагатай. -Congestion (Бөөгнөрөл):  Сүлжээний аль нэг хэсэгт өгөгдлийн урсгалын бөөгнөрөл үүссэн нөхцөлд чиглүүлэлтийг өөрчлөх шаардлагатай.

Чиглүүлэлтийг өөрчлөх нөхцөл ньмэдээллийн цугларснаас хамаарч ангилна:

-Local- Тухайн төхөөрөмж өөрийн мэдээлэлдээ тулгуурлан чиглүүлэлт хийнэ. Хамгийн бага пакетын дараалалтай шугам руу чиглүүлнэ.

 -Adjacent(хөрш) nodes- Directly connected хөршүүдээс цугларсан мэдээлэлд тулгуурлан чиглүүлэлт хийнэ.

-All nodes- Бүх төхөөрөмжүүдээс цугларсан мэдээлэлд тулгуурлан чиглүүлэлт хийнэ.

Динамик чиглүүлэлтийн протокол

Динамик чиглүүлэлтийн протокол нь рутер хооронд чиглүүлэлтийн мэдээллийг дамжуулахыг хялбарчилж өгдөг. Тэдгээр нь сүлжээ тус бүрийн хамгийн сайн боломжит замыг олж өөрийн чиглүүлэлтийн хүснэгтэндээ бүртгэн бусад рутерууд руу мэдээллээ дамжуулж байдаг.

Динамик чиглүүлэлтийн протокол ашигласнаар хамгийн гол үр дүн нь сүлжээний топологи, бүтэц өөрчлөгдөхөд автоматаар түүнийг мэдэх явдал юм. Иймд эдгээр протоколуудыг ихэвчлэн том сүлжээнд хэрэглэдэг бөгөөд сүлжээний удирдлага, үйл ажиллагааг хялбаршуулахын тулд ашигладаг.  

Давуу тал нь:

-          Сүлжээ нэмэх болон хасахад сүлжээний администратор бичиж өгөх шаардлагагүй

-          Сүлжээний өөрчлөлтийг протокол бүрэн хариуцдаг

-          Тохиргооны ямар нэгэн алдаа гарахгүй

Дутагдалтай тал нь:

-          Рутерт ачаалал бий болгоно.

-          Тохиргоо болон хяналтыг хийхэд администратораас илүү мэдлэг шаардана.

Динамик чиглүүлэлтийн аргууд

Distance vector routing:

-          Distance Vector Routing Protocol нь хол ойрын хэмжээг тодорхойлдог бөгөөд хол ойрын хэмжээ нь метрик гэсэн ухагдахуунаар тодорхойлогдох ба Энэ нь hop-уудыг тоолдог бөгөөд өгөгдлийн чиглүүлэлт нь дараагийн hop байна. Энэ төрлийн протоколууд нь хамгийн сайн замыг илрүүлэх BellmanFord алгоритмыг хэрэглэдэг.

Link state routing:

-          Link-State Routing Protocol-ууд нь бусад рутеруудээс ирсэн чиглүүлэлтийн тухай мэдээлэл дээр тулгуурлан сүлжээний бүтэц топологийг гаргадаг. Тэгээд хүлээн авах тал хүртлэх бүх боломжит сүлжээнүүдээс хамгийн сайн боломжит зам сүлжээгээ сонгодог.

Метрик ба замчлалын протокол

Чиглүүлэлтийн протоколууд нь өөр хоорондоо ялгаатай ба ашиглах метрик нь ч бас өөр байдаг бөгөөд дараах  метрикуудыг ашигладаг.

-          Хопын тоо – энэ нь энгийн метрик бөгөөд шаардлагатай рутеруудыг тоолдог.

-          Зурвасын өргөн – энэ нь илүү зурвасын өргөнтэй замыг нь сонгодог.

-          Ачаалал – замын ашиглалтыг тооцоолох

-          Саатал – замын багцыг зөөх хугацааг тооцоолох

-          Найдвартай байдал – холболт болон интерфэйсд гарах алдааг тооцоолох

-          Үнэлгээ – сүлжээний администратор чиглүүлэлтийг үнэлэх, хамгийн сайн боломжит замаар хамгийн бага үнэлгээтэй замыг сонгодог. 

Least Cost-ыг тооцоолох алгоритм

Чиглүүлэлтийн шийдвэрийн хэмжигдэхүүн (Cost) нь дайран өнгөрөх төхөөрөмжийн тоотой шууд харин шугамын багтаамжтай урвуу хамааралтай байна.

-          Сүлжээний төхөөрөмжүүд хоёр урсгалт шугамд холбогдоно

-          Шугамын хэмжигдэхүүн чиглэл бүрт өөр өөр байна

-          Шугамын хэмжигдэхүүн : Урсгал бүрийн шугамын хэмжигдэхүүний нийлбэр байна

-          Төхөөрөмж хооронд хамгийн бага шугамын хэмжигдэхүүнтэй замыг хамгийн сайн зам гэж үзнэ

Dijkstra’s Algorithm

Тухайн төхөөрөмжөөс бусад төхөөрөмж хүрэх хамгийн богино замыг, замын уртыг нэмэгдүүлэх зарчмаар олно.

 N=Сүлжээн дэх дундын төхөөрөмжүүдийн тоо

 s =Source node

T =Алгоритмаар нэгтгэгдсэн төхөөрөмжүүдийн олонлог

 w(i, j)=i төхөөрөмжөөс j төхөөрөмж хүрэх link cost 

–w(i, i) = 0

 –w(i, j) = хязгааргүй, хоёр төхөөрөмж холбогдоогүй үед 

–w(i, j) >=0, хоёр төхөөрөмж холбогдсон үед

L(n)нь s төхөөрөмжөөс n төхөөрөмж хүрэх least-cost бүхий яг одоогийн илэрсэн замын шугамын хэмжигдэхүүн.

Dijkstra’s Algorithm ажиллагаа

Step 1 [Эхлэл]

 –T = {s}Source Node ба түүнтэй холбогдох бусад төхөөрөмжүүдийн олонлог

                –L(n) = w(s, n) for n ≠ s

–Эхлэлийн замын Cost нь хөрш төхөөрөмжүүдэй холбогдох шугамын хэмжигдэхүүнээр тодорхойлогдоно

 Step 2[Дараагийн төхөөрөмжийг нэгтгэх]

–‘s’төхөөрөмжтэй шууд холбогдсон төхөөрөмжүүдийн хөршүүдийг илрүүлнэ

–Илэрсэн хөрш төхөөрөмжүүдийг Т олонлогт нэгтгэнэ.

–Т олонлогт нэгтгэгдсэн төхөөрөмжүүдийн замыг мөн тооцоолно.

 Step 3[Least-Cost замыг шинэчлэнэ]

–L(n) = min[L(n), L(x) + w(x, n)]for all n харьяалагдах T

–Хэрэв сүүлд илрүүлэгдсэн замын хэмжигдэхүүн бага бол өмнө олдсон замыг шинэчилнэ.

Бүх төхөөрөмж Т олонлогт багтсанаар алгоритм дуусна.

Bellman-Ford Algorithm

Сүлжээний топологи, шугамын хэмжигдэхүүн тогтмол

Тухайн төхөөрөмжөөс ерөнхий замын тоонд багтаан хамгийн богино замыг олно.

s =source node

 w(i, j)=I төхөөрөмжөөс j төхөөрөмж хүрэх link cost 

–w(i, i) = 0 

–w(i, j) = хязгааргүй, хоёр төхөөрөмж холбогдоогүй үед 

–w(i, j) >=0, хоёр төхөөрөмж холбогдсон үед

h =алгоритмын шатлал дахь зөвшөөрөгдөх хамгийн их шугамын тоо

Lh(n)=нь s төхөөрөмжөөс n төхөөрөмж хүрэх least-cost бүхий h-ээс ихгүй шугам багтсан замын шугамын хэмжигдэхүүн.

Bellman-Ford Algorithm ажиллагаа

Step 1 [Эхлэл] 

–L0(n) = хязгааргүй, for all n = биш s

  –Lh(s) = 0, for all h

 Step 2 [Update]

  h >=0 бүрт:

 –n ≠ s үед Lh+1(n)=minj[Lh(j)+w(j,n)]

-n төхөөрөмж өмнөх j төхөөрөмжтэй хамгийн бага cost-оор холбогдоно.

 -n-ийн одоогийн зам өмнө тодорхойлогдсон замыг шинэчилнэ.

-Эхлэлийн s ба n төхөөрөмжийн зам j-ээс  n-тэй холбогдсоноор дуусна.