Các biện pháp chống routing loop trong distance vector

Routing loop trong distance vector xảy ra khi có sự cố về đường mạng hay khi có sự thay đổi đường mạng làm cho bảng định tuýên của router không kịp cập nhật thông tin do độ hội tụ chậm nên vịêc truyền gói tin đi bị loop. Có 5 cách để chống loopefining a maximum count ,split horizon, Route poisoning,triggered updates ,holddown timers
1)Defining a maximum count:

- Distance vector routing algorithms are self-correcting, but a routing loop problem can require a count to infinity. To avoid this prolonged problem, distance vector protocols define infinity as a specific maximum number. This number refers to a routing metric which may simply be the hop count.
- With this approach, the routing protocol permits the routing loop to continue until the metric exceeds its maximum allowed value.*The graphic shows the metric value as 16 hops. This exceeds the distance vector default maximum of 15 hops so the packet is discarded by the router. In any case, when the metric value exceeds the maximum value, Network 1 is considered unreachable.
2) split horizon

- Another possible source for a routing loop occurs when incorrect information that has been sent back to a router contradicts the correct information that the router originally distributed. Here is how this problem occurs:
- Router A passes an update to Router B and Router D, indicating that Network 1 is down. Router C, however, transmits an update to Router B, indicating that Network 1 is available at a distance of 4, by way of Router D. This does not violate split-horizon rules.
- Router B concludes, incorrectly, that Router C still has a valid path to Network 1, although at a much less favorable metric. Router B sends an update to Router A advising Router A of the new route to Network 1.
- Router A now determines that it can send to Network 1 by way of Router B; Router B determines that it can send to Network 1 by way of Router C; and Router C determines that it can send to Network 1 by way of Router D. Any packet introduced into this environment will loop between routers.
- Split-horizon attempts to avoid this situation. If a routing update about Network 1 arrives from Router A, Router B or Router D cannot send information about Network 1 back to Router A. Split-horizon thus reduces incorrect routing information and reduces routing overhead
3) Route poisoning
[/B]

- Route poisoning is used by various distance vector protocols in order to overcome large routing loops and offer explicit information when a subnet or network is not accessible. This is usually accomplished by setting the hop count to one more than the maximum.
One way to avoid inconsistent updates is route poisoning. When Network 5 goes down, Router E initiates route poisoning by making a table entry for Network 5 as 16, or unreachable. By this poisoning of the route to Network 5, Router C is not susceptible to incorrect updates about the route to Network 5. When Router C receives a router poisoning from Router E, it sends an update, called a poison reverse, back to Router E. This makes sure all routes on the segment have received the poisoned route information.
When route poisoning is used with triggered updates it will speed up convergence time because neighboring routers do not have to wait 30 seconds before advertising the poisoned route.
Route poisoning causes a routing protocol to advertise infinite-metric routes for a failed route. Route poisoning does not break split horizon rules. Split horizon with poison reverse is essentially route poisoning, but specifically placed on links that split horizon would not normally allow routing information to flow across. In either case, the result is that failed routes are advertised with infinite metrics.
4)triggered updates :

-New routing tables are sent to neighboring routers on a regular basis. For example, RIP updates occur every 30 seconds. However a triggered update is sent immediately in response to some change in the routing table. The router that detects a topology change immediately sends an update message to adjacent routers that, in turn, generate triggered updates notifying their adjacent neighbors of the change. When a route fails, an update is sent immediately rather than waiting on the update timer to expire. Triggered updates, used in conjunction with route poisoning, ensure that all routers know of failed routes before any holddown timers can expire. Triggered updates go ahead and send updates because routing information has changed not waiting for the timer to expire. The router sends another routing update on its other interfaces rather than waiting on the routing update timer to expire. This causes the information about the status of the route that has changed, to be forwarded and starts the holddown timers more rapidly on the neighboring routers. The wave of updates propagates throughout the network.
Issuing a triggered update Router C announces that network 10.4.0.0 is unreachable. Upon receipt of this information, Router B announces through interface S0/1 that network 10.4.0.0 is down. In turn, Router A sends an update out interface Fa0/0.
5) holddown timers:
[/B]

-A count to infinity problem can be avoided by using holddown timers:
When a router receives an update from a neighbor indicating that a previously accessible network is now inaccessible, the router marks the route as inaccessible and starts a hold-down timer.
If at any time during hold-down timer an update is received from
The same neighbor indicating that the network is again accessible, the router marks the network as accessible and removes the hold-down timer.
A different neighboring router with a better metric than originally recorded for the network, the router marks the network as accessible and removes the hold-down timer.*
A different neighboring router with a poorer metric, the update is ignored.

CƠ CHẾ HOẠT ĐỘNG CỦA CÁC GIẢI PHÁP NHẰM TRÁNH "LOOP" TRONG GIẢI THUẬT DISTANCE VECTOR

I. Routing Loop là gì?



Trước khi network 1 bị down thì thì tất cả router đều xem đường route tới network là tốt. Router C nhận định rằng muốn tới network 1 thì fải qua router B với metric là 3 (ví dụ ta chạy RIP).

Khi network 1 bị down xuống thì router E mới gửi 1 bản update tới A là: N1 down rồi nhưng router B, C, D không biết. Nhưng B và D có thể nhận biết được N1 down 1 cách nhanh chóng vì nó connect trực tiếp tới A nên nhận update nhanh hơn. Tuy nhiên do C không nhận được update là N1 down nến vẫn gửi 1 bản update tới B và D là đường tới N1 vẫn tồn tại. Và như thế B và D update lại bản routing table của mình là N1 vẫn tốt. Muốn đến N1 hãy đi qua C. Như thế là sai và quá trình này cứ lặp đi lặp lại (vì A sẽ gửi lại 1 update nói với B và D rằng la N1 vẫn good) ===> routing loop

Nguyên nhân:

B và D có thể nhận được update từ A còn C thì không , bởi vì 1 "HÔI TỤ CHẬM" ( SLOW CONVERGENCE)

Vậy convergence là gì : sau khi topology change thì tất cả router cần 1 time để tính toán lại các đường route của mình, và quá trình và thời gian đó gọi là TIME TO CONVERGENCE

II. CÁC GIẢI PHÁP ĐỂ TRÁNH LOOP

1. SPLIT HORIZON:

Router B và D nhận update về N1(down) sẽ không gửi lại update về N1 (up, sau khi nhận được từ C) tới cho router A.

Split horizon được sử dụng để đảm bảo rằng thông tin về một route do một router phát ra không quay lại chính nó. Ví dụ, khi network 1 chưa down, router E gửi thông tin update đến router A. Router A sẽ không gửi lại thông tin update đến N1 quay lại E vì nếu làm như thế, đương nhiên E sẽ không dùng thông tin đó ==> lãng phí. Còn trong trường hợp route bị poison ==> Do có Split horizon, thông tin về route đến N1 không bị lặp đi lặp lại trên link giữa A và E (count-to-infinite)
Split horizon with Poison reverse : Bình thường, A không gửi lại cho E thông tin về route đến N1. Nhưng khi A nhận được bản tin update nói rằng route đến N1 là unreachable --> A gửi lại cho E thông tin về route đến N1 với metric là infinite.


2. HOLD DOWN TIMER :

Khi router nhận được thông tin về một route là unreachable, router sẽ đánh dấu route đó và đặt nó vào trạng thái hold-down (Router đặt bộ định thời = thời gian hold-down). Trong thời gian hold-down, router vẫn tiếp tục dùng route đó để forward gói tin, nhưng sẽ bỏ qua tất cả các thông tin về route với thông số metric bằng hoăc xấu hơn metric router đang có về route đó .

Hold-down timer bị reset khi thời gian hold-down đã hết, hoặc router nhận được thông tin về route với metric tốt hơn metric nó đang giữ.
Ví dụ: Khi A nhận được thông tin route đến N1 bị down, hold-down timer cho route đó được thiết lập. Tương tự với B, D. Do đó khi D nhận được update từ C, vì metric mà C gửi lớn hơn (xấu hơn) metric D đang có về route N1 nên D bỏ qua ==> Không còn loop

3. POSION REVERSE UPDATE :

Là bản update đặc biệt được gửi từ router connect với 1 network down tới các router neighbor của mình ( khong bao gồm router có network bị down ) rằng đường route tới network đó là infinity.

Khi một router phát hiện ra một route R bị down (router không nhận được bản tin update từ router neighbor mà từ đó nó học được route R), router sẽ đặt giá trị metric của route R bằng giá trị không xác định (infinite) và gửi đi trong bản tin cập nhật định tuyến để thông báo với các router trên mạng rằng route R unreachable.
Trong hình vẽ, router E không nhận được thông tin về route đến N1, nó đặt metric của route đến N1 là infinite rồi gửi đi trong bản tin định tuyến. Đồng thờ, E hủy bỏ route đến N1 trong bảng định tuyến của nó.

4. TRIGGER UPDATE:

Trigger updates là bản update được gửi ngay khi có route bị fail, không cần chờ đến thời gian định kỳ để gửi update.

Giới thiệu về các giao thức định tuyến

A. Đại cương về định tuyến

I. Thuật ngữ

I. 1. Routing Protocol

Routing protocol: là ngôn ngữ để một router trao đổi với router khác để chia sẻ thông tin định tuyến về khả năng đến được cũng như trạng thái của mạng.

Được cài đặt tại các Router, chúng được sử dụng để: xây dựng nên bảng định tuyến để đảm bảo rằng tất cả các Router đều có bảng “Routing table ” tương thích nhau cũng như đường đi đến các mạng phải được xác định trong “Routing Table”.

I. 2. Routed Protocol

Nó sử dụng các bảng “Routing Table” mà Routing Protocol xây dựng lên để đảm bảo việc truyền dữ liệu qua mạng một cách tin cậy. Ví dụ: IP và IPX.
I. 3. Vùng tự trị AS (Autonomous System)

Mạng Internet được chia thành các vùng nhỏ hơn gọi là các vùng tự trị (Autonomous System – AS ). AS bao gồm một tập hợp các mạng con được kết nối với nhau bởi Router. Một hệ thống AS thông thường thuộc quyền sử hữu của một công ty hay nhà cung cấp dịch vụ Internet (ISP). Và để các hệ thống AS này kết nối được với nhau, nhà quản lý phải đăng ký với cơ quan quản trị mạng trên Internet (Inter NIC) để lấy được một số nhận dạng AS cho riêng mình. Bên trong mỗi AS, các nhà quản lý có quyền quyết định loại Router cũng như giao thức định tuyến cho hệ thống của mình.

I. 4. Bảng định tuyến

Một host hay một Router phải xem xét bảng định tuyến của mình trước khi chuyển gói tin đến địa chỉ ở xa. Bảng này được gán tương ứng mỗi địa chỉ đích với một địa chỉ Router cần đến ở chặng tiếp theo.Bảng địa chỉ đích trong bảng có thể bao gồm các địa chỉ mạng, mạng con, các hệ thống độc lập. Trong bảng định tuyến có thể bao gồm một tuyến mặc định, được biểu diễn bằng địa chỉ 0.0.0.0.

Bảng định tuyến của mỗi giao thức định tuyến là khác nhau, nhưng có thể bao gồm nhữnh thông tin sau :

Địa chỉ đích của mạng, mạng con hoặc hệ thống.

Địa chỉ IP của Router chặng kế tiếp phải đến.

Giao tiếp vật lý phải sử dụng để đi đến Router kế tiếp.

Mặt nạ mạng của địa chỉ đích.

Khoảng cách đến đích (thí dụ : số lượng chặng để đến đích).

Thời gian (tính theo giây) từ khi Router cập nhật lần cuối.

I. 5. Khoảng cách quản lý (Administrative Distance (AD))

Administrative Distance được sử dụng để đánh giá độ tin cậy của thông tin định tuyến mà Router nhận từ Router hàng xóm. AD là một số nguyên biến đổi từ : 0 đến 255; 0 tương ứng với độ tin cậy cao nhất và 255 có nghĩa là không có lưu lượng đi qua tuyến này (tức là tuyến này không được sử dụng để vận chuyển thông tin của người sử dụng). Tức là khi một Router nhận được một thông tin định tuyến, thông tin này được đánh giá và một tuyến hợp lệ được đưa vào bảng định tuyến của Router. Thông tin định tuyến được đánh giá dựa vào AD, giả sử Router được cài đặt nhiều hơn một giao thức định tuyến thì giao thức định tuyến nào có AD nhỏ hơn sẽ được Router sử dụng.

Mối giao thức định tuyến có tưng ứng một giá trị AD:
Directly 0
Static route 1
RIP 120
OSPF 110
IGRP 100

II. Nguyên tắc định tuyến

Các giao thưc định tuyến phi đạt được các yêu cầu đồng thời sau:

Khám phá động một topo mạng.

Xây dựng các đường ngắn nhất.

Kiểm soát tóm tắt thông tin về các mạng bên ngoài, có thể sử dụng các metric khác nhau trong mạng cục bộ.

Phản ứng nhanh với sự thay đổi topo mạng và cập nhật các cây đường ngắn nhất.

Làm tất cả các điều trên theo định kỳ thời gian.

III. Các thành phần của định tuyến (Components of Routing Data)

Routing là quá trình chuyển tiếp packet từ một mạng này sang mạng khác.
Chúng chuyển tiếp packet như thế nào?

Thứ nhất: bạn cần phải biết logical address là gì? Địa chỉ logic được sử dụng để xác định host thuộc mạng nào.

Thứ hai: Sau khi nhận packet từ một interface nó sẽ quyết định đẩy packet ra interface tương ứng, để chuyển tiếp packet đi.

Để đưa ra quyết định chính xác router phải thực hiện được 3 nhiệm vụ sau:
Router xác định xem lưu lượng mà nhận hoặc gửi chạy giao thức lớp mạng nao? IP, IPX hay AppleTalk.

Tiếp theo sẽ kiểm tra xem địa chỉ mạng đích có trong routing table hay không. Nếu không tìm thấy đường đến mạng đích đó trong routing table, router sẽ discard packet đó và gửi một gói ICMP network unreachable về host nguồn đã gửi packet.

Nếu tìm thấy trong routing table tuyến đường tới mạng đích router sẽ forward packet ra interface tưng ứng. Router sẽ đẩy packet đó ra buffer của interface đó. Tiếp theo kiểu encapsulation (đóng gói) của frame lớp 2 của interface đó. Nếu là Ethernet thì chạy ARP để lấy địa chỉ lớp 2 là MAC, còn nếu là Frame-Relay thì chạy Inverse ARP hoặc static map để tìm DLCI. Cuối cùng Outbound interface sẽ đưa frame xuống phương tiện truyền dẫn và forward thông tin đến next hop.
Packet sẽ tiếp tục được sử lý cho đến đích cuối cùng.

1. Routing tables

Routing table là một bảng chứa các tuyến đường đến các mạng mà người quản trị cấu hình. Các bảng này được tạo ra bằng tay theo ý muốn của người quản trị hay bằng cách trao đổi thông tin định tuyến với các router khác.

Để nhìn thấy routing table trên router, chúng ta sử dụng câu lệnh: show ip route.



Đoạn Code: xác định cách mà tuyến đường được học.

Dòng Gateway of last resort is not set: cho biết routing table không có default gateway, nếu router nhận được một packet mà địa mạng đích không tìm thấy trong routing table thì router sẽ drop packet và gửi một bản tin ICMP network unreachable tới nơi gửi packet đó.

Xét dòng thông tin sau:
R 175.21.0.0/16 [120/1] via 10.10.10.1, 00:00:18, Serial0
R: có nghĩa tuyến đường được học bằng giao thức RIP.
175.21.0.0/16: Địa chỉ mạng và số bit 1 trong subnetmask của mạng đích.
[120/1]: 120 là administrative distance của tuyến đường, 1 là metric của tuyến đường. Với RIP thì đây là hop count.
via 10.10.10.1: là địa chỉ next-hop của tuyến. Đây là đỉa chỉ mà packet cần phải gửi tới để gửi packet tới đích.
00:00:18: khảong thời gian kể từ khi tuyến đường được update. Trong trường hợp này là 18 second.
Serial0: là interface mà tuyến đường được học qua đó. Đồng thời đó cũng là interface mà packet được gửi qua để tới đích.

2. Xây dựng bảng định tuyến (Populating the Routing Table)
Trước khi tuyến đường được đưa vào bảng định tuyến, router pảhi học về những tuyến đường đó. Có hai cách để học tuyến đường:
+ Statically defining a route
+ Dynamically learning a route

a/ Statically Defined Routes
Statically defined route: bằng cách này tuyến đường được nhập bằng tay vào router. Static route được nhập vào router với cú pháp như sau ở global configuration mode:
ip route prefix mask {address|interface} distance
prefix = IP route prefix for the destination.
mask = Prefix mask for the destination.
address = IP address of the next hop that can be used to reach the destination.
interface = Network interface to use.
distance = (Optional) Administrative distance.

Nếu bạn muốn cấu hình default route, thì phần prefix = 0.0.0.0 và mask = 0.0.0.0. Default route sữ gửi bất cứ packet nào mà địa chỉ mạng đích tưng ứng không tìm thấy trong bảng định tuyến.

Ưu điểm của static route là ngưởi quản trị có toàn quyền điều khiển thông tin lưu trong routing table và phải lãng phí băng thông để xây dựng nên routing table.

Nhược điểm của static route là độ phức tạp của việc cấu hình tăng lên khi kích thước của mạng tăng lên. Giả sử một mạng có N router thì người quản trị cần phải cấu hình (N-1)*N câu lệnh trên tất cả các router. Một nhược điểm nữa của static route là không có khả năng thích ứng với những mạng có cấu trúc thay đổi.

b/Dynamically Learned Routes
Dynamic routing là quá trình mà trong đó giao thức định tuyến phải tìm ra đường tốt nhất trong mạng và duy trì chúng. Có rất nhiều cách để xây dựng lên bảng định tuyến một cách động. Nhưng tất cả đều thực hiện theo quy tắc sau: nó sẽ khám tất cả các tuyến đường đến đích có thể và thực hiện một số quy tắc đã định trước để xác định ra đường tốt nhất đến đích.
Ưu điểm của dynamic routing là đơn giản trong việc cấu hình và tự động tìm ra những tuyến đường thay thế nếu như mạng thay đổi.

Nhược điểm của dynamic routing là yêu cầu xử lý của CPU của router cao hơn là static route. Tiêu tốn một phần băng thông trên mạng để xây dựng lên bảng định tuyến.

b.1. Distance-Vector Routing

Distance-vector routing được chia làm hai phần: distance và vector. Distance là metric để tới đích (tiêu chuẩn về khoảng cách để tới đích). Vector là hướng để tới đích nó được xác định bởi next-hop của tuyến đường.

Các giao thức định tuyến Distance-vector cập nhật và update bảng định tuyến của mình bằng cách thường xuyên gửi thông điệp update liên tục theo chu kỳ dưới dạng Broadcast. Thông điệp Broadcast đó bao gồm toàn bộ bảng định tuyến. Tuy nhiên một vấn đề chung xảy ra đối với các giao thức định tuyến Distance-Vector đó chính là “Routing Loop ”. Do các Router không được update ngay lập tức( mà theo chu kỳ), chính điều đó đã khiến cho các Router xây dựng lên bảng định tuyến không đúng. Dẫn đến các gói tin đi trên đường mà nó đã đi qua rồi, kết quả là gói tin đi lòng vòng trên mạng. Hiện tượng “Routing Loop ” đã làm phát sinh lưu lượng mạng vô ích gây lãng phí băng thông.

Chính vì vậy người ta đã đưa vào các giao thức định tuyến theo khoảng cách các phương pháp để tránh loop đó là:

b.1.1. Route Poisoning

Một trong những phương pháp người ta đưa vào các giao thức định tuyến để tránh loop đó là “Route poisoning”. Route poisoning bắt đầu hoạt động khi Router nhận thấy một mạng nối tới nó bị down. Nó sẽ quảng bá tới tất cả các Router lân cận nó rằng: Mạng đó là không thể tới được. Ví dụ với RIP: nó sẽ gửi thông báo tới các Router lân cận của nó với hop count = 16. Kết quả là mạng đó sẽ được xoá khỏi bảng định tuyến.

b.1.2. Split Horizon

Tuy nhiên trong một số trường hợp thì Route Poisoning không thể giải quyết được. Như trường hợp dưới đây :



Người ta đã đưa ra phương pháp Split Horizon, tránh các Router không gửi lại các thông tin định tuyến quay trở lại Router mà nó đã “học” được đường đi từ Rouer đó (vẫn có thể xảy ra với cấu trúc mạng vòng).

b.1.3.Hold-Down Timer

Để giải quyết trường hợp mà Split Horizon không giải quyết được người ta đưa ra phương pháp Hold-Down Timer. Tránh việc thay đổi tuyến được thực hiện trước khi mạng hội tụ từ sự thay đổi đó. Tránh cập nhật thông tin từ việc thiết lập lại các thông tin không đúng. Khi một Router nhận được một cập nhật mà chứa một cấu trúc thay đổi, hold-down timer sẽ bắt đầu. Bất cứ cập nhật nào trong thời gian này sẽ bị huỷ bỏ. Thời gian hold-timer được đặt ít nhất phi lớn hơn 3 lần thời gian cập nhật thông tin toàn bộ tuyến trong mạng.

b.1.4. Triggered (Flash) Updates

Để ngăn chặn tình trạng hết thời gian hold-timer mà thông tin update mới tới. Người ta đưa ra phưng pháp Triggered (Flash) Updates tức là ngay sau khi nhậnđược thông cập nhật mà chứa một cấu trúc thay đổi nó sẽ gửi ngay lập tức broadcast update tới các Router lân cận.

b.2. Link-State Routing

Khác với Distance-vector routing protocol, router chỉ biết được next-hop để gửi packet đi tới đích. Đối với Link-state routing protocol mỗi router đều xác định được chính xác topology của mạng. Chính vì vậy router sẽ đưa ra quyết định để đưa packet đến đích tốt hơn. Mỗi router trong mạng sẽ báo cáo trạng thái của nó, các link nối trực tiếp và trạng thái của mỗi link. Router sẽ nhân bản thông tin này tới tất cả các router trên mạng. Cuối cùng tất cả các rouer trên mạng đều có cái nhìn giống nhau về topo mạng.
Một điểm khác nữa đối với distance-vector routing protocol là các router không gửi toàn bộ routing table mà chỉ gửi sự thay đổi xảy ra hay một bản tin hello với kích thước nhỏ gọn nếu như mạng không có sự thay đổi theo những chu ky nhất định. Nên link-state có một ưu điểm nữa là tốn ít băng thông hơn distance-vector để xây dựng nên routing table.

Nhược điểm của link-state protocol là phức tạp hơn trong cấu hình so với distace-vector routing protocol và yêu cầu phần cứng của router cao hơn khi sử dụng distance-vector routing protocol.

Tóm lại hoạt động của link-state routing protocol có thể chia làm 4 bước sau:

1. Các router tìm neighbors của mình từ các router nối trực tiếp.
2. Sau khi tìm được neighbors xong, router gửi các LSA tới các neighbor của nó. Sau khi nhận và copy thông tin từ LSA, router sẽ forward hay flood LSA tới các neighbor của nó.
3. Tất cả các router lưu LSA trong database của nó. Điều đó có nghĩa là tất c các router đều có một cái nhìn giống nhau về topo mạng.
4. Mỗi router sử dụng thuật toán Dijkstra để tính toán ra đường tốt nhất để đưa vào routing table.

c/Quyết định tuyến đường nào sẽ được lưu vào Routing table (The Final Decision on What Routes Populate the Routing Table)
Administrative distance và metric là hai nhân tố quyết định tuyến đường nào sẽ được lưu vào routing table. Nhân tố đầu tiên xét đến là AD, AD là độ tin cậy của routing protocol mà tìm ra tuyến đường. Nếu có nhiều hơn tuyến đường tới đích thì tuyến đường nào có AD nhỏ hơn sẽ được đưa vào routing table. Nếu các tuyến đường đó có cùng AD thì nhân tố thứ 2 được xét đến chình là metric.

Metric là giá trị của tuyến đường cụ thể của một giao thức định tuyến nào đó. Nếu có nhiều hơn một tuyến đường đến đích có cùng AD (cung giao thức định tuyến) thì tuyến nào có metric tốt hơn sẽ được đưa vào routing table. Nếu chúng có cùng AD và metric thì tuỳ từng routing protocol cụ thể mà số lượng tuyến đường được đưa vào routing table là khác nhau.

3. Reaching the Destination
Sau khi router nhận packet, the router sẽ gỡ bỏ header lớp 2 để tìm địa chỉ đích lớp 3. Sau khi đọc xong địa chỉ đích lớp 3 nó tìm kiếm trong routing table cho địa chỉ đích đó. Giả sử đỉa chỉ đích đó có trong routing table, router sẽ xác định địa chỉ của next-hop. Sau đó packet bị đẩy ra buffer của interface tương ứng, router sẽ khám phá loại encapsulation lớp 2 nào được sử dụng giữa out going interface và next-hop. Packet được đóng gói xuống lớp 2 rồi đưa xuống môi trường truyền dẫn dưới dạng bit, tín hiệu điện, quang…Quá trình này sẽ tiếp tục cho đến khi packet được đưa đến đích thì thôi.

IV. Hội tụ (Convergence)
Thời gian hội tụ (convergence time) là thời gian mà tất c router đồng ý về topo mạng sau một sự thay đổi của mạng. Các router phải đồng bộ routing table của chúng.

Routing Protocols

1. RIP v1 (Routing Information Protocol) :


- Rip là 1 distance vector

- Rip là một classful protocol

- Rip process dùng UDP port 520; tất cả Rip messages được encapsulate trong 1 UDP segment với port source và destination là 520

- Rip định nghĩa 2 messages là : Request messages và Response messages.(Request message dùng để yêu cầu những neighbors gởi Update, Response message mang update.

- Rip gởi routing information của nó mỗi 30 giây (default)

- Invalid timer là 180s (default)

- Hold-down timer là 180 giây (default)

- Flushed timer là 240s

- Rip dùng thuật toán Bellman-ford

- Rip metric dựa vào hop count (maximum là 15)

- Rip có AD (administrative Distance) là 120 (default)

- Rip có khả năng load balancing (cân bằng tải) với maximum 6 đường có metric bằng nhau (Six parallel equal-cost paths), Cisco Router (default) chỉ hổ trợ 4 đường bằng nhau.
Ví dụ : Ruoter1(config-router)#maximum-paths 5 : cho phép load balancing tối đa là 5
đường

- Không hổ trợ Discontiguous Network (mạng gián đoạn)

· Discontiguous network là một mạng chính (Major network) bị phân cách bởi major network khác.

Ví dụ :



) Bất cứ khi nào RIP quảng bá 1 network qua 1 major network boundary khác, Rip summaries netowk được quảng bá tại major network boundary như ở hình trên.

Các bước ROUTER 1 thực hiện trước khi gởi Update đến ROUTER 2 :

+ Net 131.108.5.0/24 có cùng major network với 137.99.88.0/24 ?




+ Không trùng, ROUTER 1 summarizes 131.108.5.0/24 và quảng bá route
131.108.0.0/16



Các bước thực hiện của ROUTER 2 trước khi chấp nhận update từ ROUTER 1 :

+ Major network đã nhận (131.108.0.0) có cùng major network 137.99.88.0

+ Không trùng, trong routing table có bất kỳ subnet nào thuộc major network này chưa

+ Có rồi, ROUTER 2 bỏ qua không update.



- Không hổ trợ VLSM (Variable-Length Subnet Mask) : Rip và igrp không có khả năng mang subnet mask information trong khi gởi update. Trước khi nó quảng bá, nó thực hiện 1 kiểm
tra dựa vào subnetmask của interface mà nó gởi update. Nếu 2 subnet không đúng thí nó sẽ
drop



Các bước thực hiện của ROUTER 1 trước khi gởi update đến ROUTER 2

+ ROUTER 1 kiểm tra xem, nếu 131.108.5.0/24 có cùng major network
131.108.6.0/30 không ?

+ Cùng major network. ROUTER 1 xác định 131.108.5.0/24 có cùng subnet mask
131.108.6.0/30 không ?

+ Bởi vì 2 subnet không trùng nên ROUTER 1 drop mạng 131.108.0.0 /16 và không quảng bá route

+ ROUTER 1 xác định 131.108.7.0/30 là cùng major network với 131.108.6.0/30
không ?

+ Cùng major network. ROUTER 1 xác định tiếp 131.108.7.0/30 có cùng subnet mask với 131.108.6.0/30 không ?

+ Vì cả 2 subnet mask giống nhau nên ROUTER 1 quảng bá network
131.108.7.0/30 đến ROUTER 2.

- Default Routes : Khi RIP thấy 1 default route trong routing table của nó, nó sẽ tự động quảng
bá default route này trong RIP update.

2. RIP V2 : Rip v2 có 1 vài cải tiến của Rip v1



- Gởi routing update dùng multicast 224.0.0.9

- Route tag : có thể pass thông tin về những routes học được từ source bên ngoài và được redistributed vào RIP. Route tag được dùng để phân biệt những routes RIP học từ bên ngoài

- Subnet mask

- Next-hop metric

- Multicast capability

- Authentication (clear text hoặc mã hóa MD5)



3. IGRP (Interior Gateway Routing Protocol) :


- Là 1 distance vector

- Là 1 classful protocol

- Gởi routing information của nó mỗi 90 giây (default)

- Hold-down timer là 280 giây (default)

- Dùng thuật toán Bellman-ford

- Maximum hop count là 255
- Metric dựa vào Bandwidth, delay, reliable, Load và MTU (maximum là 224), default chỉ lệ
thuộc vào Bandwidthigrp + Delayigrp.
) BWigrp = 107/BW

) Delayigrp = Delay/10

- AD (administrative Distance) là 100 (default)

- Bandwidth : Lấy BW nhỏ nhất trong quảng đường đi đến route đó

- Delay : Tổng các delay trong quảng đường đi đến mạng đó

- Có khả năng load balancing (cân bằng tải) với maximum 6 đường có metric bằng nhau (Six parallel equal-cost paths), Cisco Router (default) chỉ hổ trợ 4 đường bằng nhau và load balacing với cost không bằng nhau.

) Ví dụ :

ƒ Ruoter1(config-router)#maximum-paths 5 : cho phép load balancing tối đa là
5 đường bằng nhau.

ƒ Ruoter1(config-router)# variance 4 : là sẽ load balacing với những đường có metric nhỏ hơn 4 lần metric nhỏ nhất.

- Không hổ trợ Discontiguous Network (mạng gián đoạn)

- Không hổ trợ VLSM

4. EIGRP : Enhanced Interior Gateway Routing Protocol



- Giống như Distance vector protocol, EIGRP nhận update từ những neighbor.

- Giống như Link-state protocol, nó giữ 1 bảng topology nhưng biết gì về toàn mạng, nó chỉ
phụ thuộc vào nhưng quảng bá của neighbor của nó.

- Là Hybrid routing protocol : EIGRP đôi khi được mô tả như là distance vertor nhưng cơ
chế hoạt động như là link state protocol.

- EIGRP dùng 1 hệ thống tính toán phức tạp (Diffusing)

- EIGRP gởi những update qua địa chỉ multicast 224.0.0.10

- AD (administrative Distance) là 90 (default)

- Không giống IGRP, EIGRP phải thiết lập mối quan hệ trước khi gởi update. Hello packet dùng để thiết lập neighbor và thời gian gởi hello packet lệ thuộc vào môi trường truyền :

) Môi trường Broadcast như Ethernet, Token Ring, FDDI : Hello là gởi multicast cứ
mỗi 5 giây

) Môi trường X.25, Framerelay và ATM interface với tốc độ đường truyền là thấp hơn hoặc bằng T1 : Hello là gởi unicast cứ mỗi 60 giây.

) Hello interval có thể thay đổi được trên interface với câu lệnh như sau :

ƒ R1(config-if)#ip hello-interval eigrp

- Thời gian hội tụ nhanh nhưng vẫn chống được loop trong mọi trường hợp nào.

- EIGRP update không theo chu kỳ (nonperiodic), chỉ 1 phần (partial) và giới hạn (bounded) Nonperiodic : Không gởi theo gởi theo chu kỳ như igrp là 90 giây
Partial : Là sự cập nhật chỉ bao gồm những routes thay đổi

Bounded : Là sự cập nhật chỉ được gởi đến những Router cùng chạy EIGRP

- EIGRP dùng ít Bandwidth hơn Distance Vector

- EIGRP chiếm không quá 50% của Bandwidth để update bởi default (IOS mới sau này cho phép thay đổi bằng lệnh : ip bandwidth-percent eigrp).

- Là Classless protocol

- Hổ trợ VLSM

- Với IOS version 11.3 trở đi, những EIGRP packet có thể được xác thực dùng mã hóa kiểu
MD5

- EIGRP có thể với IP, IPX và Apple Talk.

- Cách tính metric giống như IGRP nhưng nhân thêm 256 bởi vì chiều dài metric = 32 bits

- EIGRP có 4 thành phần chính :

) Protocol-Dependent Modules (PDM): Giữ nhiệm vụ phân tách những việc routing 1
cách rõ ràng như : IP, IPX, AppleTalk.



) Reliable Transport Protocol (RTP) : Quản lý việc phát (delivery) và nhận
(reception) những gói EIGRP.

ƒ Reliable delivery : Sự cấp phát được bảo đảm và những gói đó sẽ được cấp phát hợp lệ.

) Neighbor Discovery / Recovery : Bởi vì EIGRP update không theo chu kỳ, nên nó cần phải có 1 xử lý bởi những neighbor.

) Diffusing Update Algorithm (DUAL) :

5. OSPF (Open Shortest Path First)
- Được phát triển bởi IETF (Internet Engineer Task Force : Nhóm KS Internet) để khắc phục những vấn để của RIP

- Thuộc Interior Gateway Protocol (IGP)

- Là Link state protocol

- Dùng Thuật toán Đường ngắn nhất của Dijkstra và là mở (Open) không phải của riêng hãng nào, có thể được dùng cho thiết bị của tất cả các hãng. Version 1 (RFC 1131), Version 2 (RFC 2328). Version 3 (RFC 2740)

- AD (administrative Distance) là 110 (default)

- Những ưu điểm của OSPF với Distance Vector

) Hội tụ nhanh

) Scalability mạng lớn

Những đặc điểm khác của OSPF

- Phân vùng (Area) để giảm tác động đối với CPU và RAM (chứa và xử lý routing protocol traffic) và tạo ra network có phân cấp

- Các xử lý classless hoàn toàn, loại trừ những vấn đề classful như mạng gián đoạn

- Hổ trợ VLSM và supernetting (CIDR)
- Metric không bị giới hạn (metric=cost=108/BW)

- Cân bằng tải với cost bằng nhau

- Dùng địa chỉ Multicast để giảm tác động đến những thiết bị non-OSPF.

- Hổ trợ authentication (MD5)

- Dùng route tagging để theo dõi những mạng bên ngoài được redistribute vào OSPF

- Hoạt Động của OSPF :

- OSPF-speaking routers gởi những Hello packets ra tất cả các interfaces chạy OSPF. Nếu 2 routers cùng chung 1 data-link thống nhất những tham số nào đó được xác định trong những hello packets tương ứng, chúng sẽ trở thành những láng giềng (neighbors).

- Adjacency : Có thể được xem như kết nối ảo point-to-point, được tạo thành những Routers với nhau.



- Mỗi Router gởi những quảng bá trạng thái kết nối (LSA – Link state advertisement) đến tất
cả adjacency. LSAs mô tả tất cả link của router hoặc những interface và trạng thái của những link. Những link này có thể là stub networks (là network với không có 1 router nào được gắn vào), những OSPF routers khác hoặc những networks trong những vùng khác, hoặc những mạng bên ngoài (network học từ routing khác). Vì những kiểu của thông tin link state biến
đổi nên OSPF định nghĩa nhiều kiểu LSA.

RIR có đặt điểm sau:

• Distance vector protocol.
• Uses UDP port 520.
• Classful protocol (no support for VLSM or CIDR).
• Metric is router hop count.
• Maximum hop count is 15; unreachable routes have a metric of 16.
• Periodic route updates broadcast every 30 seconds.
• 25 routes per RIP message.
• Implements split horizon with poison reverse.
• Implements triggered updates.
• No support for authentication.
• Administrative distance for RIP is 120.

OSPF có đặc điểm sau:

• Link-state routing protocol.
• Uses IP protocol 89.
• Classless Protocol (supports VLSMs).
• Metric is cost (based on interface bandwidth) by default.
• Sends partial route updates only when there are changes.
• Routes labeled as intra-area, interarea, external Type 1, or external Type 2.
• Supports authentication.
• Uses Dijkstra algorithm to calculate SPF tree.
• Default administrative distance is 110.
• Uses multicast 224.0.0.5 (ALLSPFrouters).
• Uses multicast 224.0.0.6 (ALLDRrouters).

Với các đặc điểm này khi thiết kế mạng RIP thường dùng cho mạng nhỏ, OSPF dùng cho mạng lớn.
Mạng lớn hay nhỏ khi liệt kê các yêu cầu cần thiết lập, sẽ có một list các đặc điểm, từ đó xem với các đặc điểm yêu cầu này giao thức định tuyến nào có thể giải quyết được (tất nhiên giao thức định tuyến chỉ mới là 1 phần).

Phan biet path-vector voi linkstate protocol!

-Distance vector: Gửi update định kì, router trao đổi toàn bộ sơ đồ đường đi của mình với router liền kề.
Ưu: đơn giản, dễ cấu hình, cấu hình router không cần mạnh. Thiết lập định tuyến cũng đơn giản.
Nhược: Vì phụ thuộc hoàn toàn vào router cận kề nên thông tin thiếu chính xác, có các vấn đề về loop, hội tụ chậm.

-LinkState: Nhận thông tin về trạng thái chính xác, do các router trong vùng gửi để tập hợp thành một bảng cơ sở dữ liệu. Sau đó giao thức dùng bảng này để tự xây dựng sơ đồ đường đi tối ưu cho riêng mình bằng giải thuật của chính giao thức đó [vd: với OSPF thì là SPF, Shortest Path Frist].
Ưu: Tự chọn đường đi cho mình nên tốc độ hội tụ nhanh, không loop. Ngày nay sử dụng nhiều.
Nhược: Cấu hình khó hơn, phần cứng mạnh.


Bên trên là những giao thức hầu hết chỉ chạy bên trong AS [IGP]. Vì bên trong AS mục đích chính là cần mạng hội tụ nhanh.

-Path-vector protocol: cụ thể ở đây chủ yếu là BGP.
Những giao thức bên trên thì chỉ có khả năng xử lí vài ngàn tuyến là hết chịu nổi nên ra đời giao thức Path-vector có khả năng xử lí rất lớn đến hơn hàng trăm ngàn tuyến.
Đối với BGP thì chủ yếu không phải để mạng hội tụ nhanh mà mục đích chính của nó là gửi số lượng tuyến nhiều nhất trong dung lượng update ít nhất có thể.

Giao thức path vector không chọn đường chủ yếu chỉ dựa vào metric mà nó phụ thuộc vào thuộc chủ yếu vào thuộc tính của route đó.
vd: thuộc tính AS-Path dùng xác định đường đi tối ưu và tránh loop khi các route được quảng bá đi chu du qua các AS.
Một số thuộc tính cần bắt buộc phải có nếu sản phẩm có hỗ trợ BGP: AS_Path, Origin, Next-hop.

Giao thức ICMP.

Thuật ngữ ICMP được viết tắt bởi Internetwork Control Message Protocol là một giao thức hoạt động trên layer 2 - Internetwork trong mô hình TCP/IP hoặc layer 3 - Network trong mô hình OSI cho phép kiểm tra

và xác định lỗi của Layer 3 Internetwork trong mô hình TCP/IP bằng cách định nghĩa ra các loại thông điệp có thể sử dụng để xác định xem mạng hiện tại có thể truyền được gói tin hay không. Trong thực tế, ICMP cần các thành phần của mọi gói tin IP để có thể hoạt động được.
- Thỉnh thoảng một gateway hoặc một máy đích sẽ liên lạc với máy nguồn để đưa ra những thông điệp lỗi về tiến trình xử lý các gói tin. Đó là mục đích chính của giao thức này. ICMP sử dụng với một mục đích đơn giản là hỗ trợ cho sự hoạt động của giao thức IP.
- Trong khi truyền các gói tin Ping, cũng được biết đến như các gói tin ICMP echo requests, và ICMP echo replies. ICMP bao gồm rất nhiều các loại thông điệp khác nhau cho những mục đích đa dạng khác nhau. Bảng 1.1 sẽ là danh sách các loại thông điệp quan trọng và thường sử dụng:

Hình 1.1: ICMP Message Type.

- Mỗi thông điệp của ICMP có chứa một trường Type và một trường Code. Trường Type là trường biểu diễn các loại thông điệp - xem trong bảng 1.1, còn trường Code chứa các thông điệp con (subtype). Cho ví dụ, có nhiều người cho rằng có hai loại thông điệp được đưa ra khi sử dụng câu lệnh Ping như: ICMP Echo Request và ICMP echo Reply, nhưng thực tế, hai loại thông điệp đó thuộc cùng một loại thông điệp là Echo và khác Code (Request và Reply). Các bạn có thể được giới thiệu chi tiết hơn về các loại thông điệp của ICMP như sau:

1. ICMP Unreachable
- Khi một thiết bị thực hiện việc truyền một gói tin đến máy đích nhưng không thực hiện được thì thiết bị đó sẽ gửi lại một thông điệp là ICMP Unreachable. Để trợ giúp cho việc xác định nguyên nhân chính của việc gói tin đó không thể gửi được, thì thông điệp ICMP Unreachable sẽ bao gồm một trọng năm giá trị Code để biểu diễn nguyên nhân việc truyền dữ liệu không thành công. Cho ví dụ: hình 1.2 máy VNE_1 đang cố gắng kết nối đến Web server, Web server này được gọi là Web. Bảng 1.3 sẽ đưa ra danh sách những loại Code của thông điệp ICMP Unreachable

Hình 1.2: Sample Network for ICMP Unreachable Examples

Bảng 1.3: ICMP Unreachable Codes

2. Time Exceeded ICMP Message.

- Thông điệp ICMP Time Exceeded đưa ra thông báo cho một máy nguồn khi một gói tin mà nó gửi bị hủy bỏ bởi vì thời gian truyền gói tin quá dài. Khi truyền dữ liệu trên mạng thì các gói tin truyền cần phải được định nghĩa thời gian truyền, để ngăn cản việc gói tin đó được truyền mãi sẽ gây ra lặp vòng, mỗi một gói tin đều có một IP header trong đó có một trường được gọi là TTL (Time to Live) - trường này sẽ định nghĩa ra một giá trị hop (tức là số router) mà gói tin có thể đi qua. Khi gói tin đi qua một router thì giá trị trường TTL này sẽ được giảm đi 1, cứ như vậy cho đến khi nào gói tin đó bị router giảm giá trị trường TTL xuống giá trị 0 thì gói tin đó sẽ bị hủy và router thực hiện việc hủy gói tin đó sẽ gửi một thông điệp ICMP Time Exceeded cho máy nguồn.
- Dùng câu lệnh Trace - Cisco IOS để xác định thông điệp Time Exceeded và trường IP TTL. Câu lệnh Trace sẽ gửi đi 3 gói tin, mỗi gói tin có trương TTL được đưa vào giá trị là 1, kết quả là một thông điệp ICMP Time Exceeded được trả lại bởi router đầu tiên trong đường đi đó. Câu lệnh Trace sau đó sẽ tiếp tục gửi 3 gói tin tiếp theo với trường TTL được đưa vào giá trị là 2, sau đó lại 3 gói tin khác được truyền đi với trường TTL được đưa vào giá trị là 3, và cứ tiếp tục như vậy, cho đến khi nó được trả lời bởi máy đích.

- Ví dụ: hình 1.4 ICMP debug trên Router B, Khi đang chạy câu lệnh Trace trên Router A.

3. ICMP Redirect

Thông điệp ICMP Redirect cho phép một router gateway nói cho một máy nào đó biết về một router tốt hơn có thể được sử dụng trong quá trình truyền dữ liệu đến một máy đích nào đó. Để có thể thực hiện được điều đó, một ICMP Redirect sẽ được gửi từ router gateway đến máy đó và nói cho máy đó biết về địa chỉ IP về router tốt hơn kia. Cho ví dụ, hình 1.5 một PC dùng địa chỉ IP của rRouter B như là default gateway của nó, nhưng Router A có một đường đi đến mạng 10.1.4.0/24 có chi phí tốt hơn của Router B. Khi đó Router B sẽ đưa ra một thông điệp ICMP Redirect cho PC đó theo các bước như sau:
- PC gửi một gói tin, máy đích thuộc mạng 10.1.4.0/24, qua Router B (Vì router B là default gatewary của PC này)
- Router B sẽ chuyển gói tin đó dựa vào bảng định tuyến của chính nó.
- Router B gửi một thông điệp ICMP Redirect đến PC đó, và nói cho PC đó biết rằng lần sau khi gửi dữ liệu đến mạng 10.1.4.0/24 thì gửi qua Router A (vì trong bảng định tuyến của RouterA cũng chứa đường đi tới mạng 10.1.4.0/24 và đường đi này có chi phí tốt hơn của Router B).
- Những gói tin tiếp theo được gửi từ PC đó đến mạng 10.1.4.0/24 sẽ được gửi trực tiếp qua Router A

Hình 1.5: Ví dụ về một ICMP Redirect


Với những kiến thức về các loại thông điệp của ICMP sẽ giúp các bạn có thể kiểm tra và sửa lỗi hệ thống mạng được tốt hơn.

các trang web học network

1-http://cisco-ccna-exploration-4.blogspot.com/
2-http://testccna-4u.blogspot.com/
3-http://allsoft247.blogspot.com/2009/03/ccna-all-answer-100100.html
4-http://babymilu.net/blog/index.php
5-http://certexam.blogspot.com/