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
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-тэй
холбогдсоноор дуусна.
Routing in packet switching networks
Reviewed by Unknown
on
17 November
Rating:
No comments: