Thuật toán DUAL

[trungtruc82]

Có ai biết rõ về cách thức hoạt động của thuật toán DUAL làm ơn giúp em với

Em cám ơn nhiều

[dangquangminh]

Trước khi tìm hiểu hoạt động của DUAL ta hãy làm quen với các khái niệm sau:

- Quan hệ láng giềng trong EIGRP (Adjacency): khi khởi động tiến trình EIGRP, router sử dụng các gói Hello để khám phá động các router láng giềng neighbor. Sau khi đã thiết lập được quan hệ với các router láng giềng neighbor, router sẽ nhận được các thông tin cập nhật từ các router láng giềng. Thông tin update bao gồm tất cả tuyến đường mà neighbor biết được và metric của tất cả các tuyến đó. Đối với mỗi tuyến, router sẽ tính được distance dựa trên những thông số mà router neighbor đã quảng cáo.

- Feasible distance (FD): là metric nhỏ nhất để tới đích.

- Feasibility condition(FC): là điều kiện mà giá trị AD advertised distance của neighbor phải nhỏ hơn FD.

- Feasible successor: nếu router neighbor quảng bá giá trị AD advertised distance của nó thấp hơn FC thì neighbor đó sẽ trở thành Feasible successor. Tất cả các Feasible successor được lưu trong topology table.

- Successor: từ topology table, router sẽ tìm route nào có metric nhỏ nhất và lưu nó vào routing table. Và router láng giềng neighbor quảng bá route đó sẽ là Successor.

Thuật toán DUAL

- The DUAL Finite State Machine

Khi một router không thực hiện thuật toán DUAL diffusing computations thì mỗi route sẽ ở trạng thái passive state (cần lưu ý trạng thái passive là trạng thái ổn định - trạng thái OK). Router tính toán lại danh sách Feasible successor cho một route bất cứ khi nào một sự kiện (input event) xảy ra.

Input event có thể là:

+ Sự thay đổi cost của một link nối trực tiếp.
+ Sự thay đổi trạng thái (up hay down) của link nối trực tiếp.
+ Khi nhận một update packet.
+ Khi nhận một query packet.
+ Khi nhận một reply packet.

Nếu distance tới destination sẽ được tính toán lại với bước đầu tiên là: local computation.

Có thể xảy ra các trường hợp như sau:

- FS khác có distance nhỏ nhất sẽ trở thành successor.
- Nếu distance mới nhỏ hơn FD thì FD sẽ được cập nhật.
- Nếu distance mới khác với distance đang tồn tại, update sẽ gửi tới tất cả các neighbor.

Trong khi đang thực hiện local computation thì những route còn lại vẫn ở trạng thái passive state. Nếu một FS được tìm thấy update sẽ được gửi tới tất cả các neighbor nhưng state không đổi. Nếu không tìm thấy FS trong topology table thì router thực hiện diffusing computations và route sẽ chuyển trạng thái sang active state. Cho đến khi diffusing computations chạy xong và route sẽ quay trở về trạng thái passive state. Chú ý router không thể thực hiện được những việc sau:

- Thay đổi successor của route.
- Thay đổi distance mà nó qung bá cho route đó.
- Thay đổi FD của route.

Chú ý là khi route chuyển sang active state nó sẽ khởi tạo active timer nếu hết thời gian này mà route vẫn không chuyển được về passtive state thì route sẽ được công bố là Suck-in-active(SIA).

[dothanhkhanh]

Anh Minh cho em hỏi là: - Feasibility condition(FC): là điều kiện mà giá trị AD advertised distance của neighbor phải nhỏ hơn FD.
nhưng khi em DEMO bài lap EIGRP và khi show Router R1 thì như sau:

R1#show ip eigrp topology
IP-EIGRP Topology Table for AS 100

Codes: P - Passive, A - Active, U - Update, Q - Query, R - Reply,
r - Reply status

P 172.16.1.0/24, 1 successors, FD is 28160
via Connected, FastEthernet0/0
P 192.168.11.0/24, 1 successors, FD is 28160
via Connected, FastEthernet0/1
P 172.16.3.0/30, 1 successors, FD is 40512000
via Connected, Serial0/0/0
P 172.16.2.0/24, 1 successors, FD is 3526400
via 192.168.10.6 (3526400/3014400), Serial0/0/1
via 172.16.3.2 (4294967295/28160), Serial0/0/0
P 192.168.10.8/30, 1 successors, FD is 3523840
via 192.168.10.6 (3523840/3011840), Serial0/0/1
via 172.16.3.2 (4294967295/3011840), Serial0/0/0
P 192.168.0.0/22, 1 successors, FD is 3523840
via 192.168.10.6 (3523840/3011840), Serial0/0/1
via 172.16.3.2 (4294967295/3523840), Serial0/0/0
P 192.168.10.4/30, 1 successors, FD is 2169856
via Connected, Serial0/0/1

Ở đây route 192.168.0.0/22 có 1 Successor 192.168.10.6(R3) và 1 FC 172.16.3.2(R2)
nhưng trên hình cho thấy RD(của R2)= FD(R3)= 3523840
vậy điều kiện = ở đây được thỏa. có điều gì đó không đúng ở đây??????
Mong anh giải thích giúp!
Thanks!

[phamminhtuan]

Anh Minh cho em hỏi là: - Feasibility condition(FC): là điều kiện mà giá trị AD advertised distance của neighbor phải nhỏ hơn FD.
nhưng khi em DEMO bài lap EIGRP và khi show Router R1 thì như sau:

R1#show ip eigrp topology
IP-EIGRP Topology Table for AS 100

Codes: P - Passive, A - Active, U - Update, Q - Query, R - Reply,
r - Reply status

P 172.16.1.0/24, 1 successors, FD is 28160
via Connected, FastEthernet0/0
P 192.168.11.0/24, 1 successors, FD is 28160
via Connected, FastEthernet0/1
P 172.16.3.0/30, 1 successors, FD is 40512000
via Connected, Serial0/0/0
P 172.16.2.0/24, 1 successors, FD is 3526400
via 192.168.10.6 (3526400/3014400), Serial0/0/1
via 172.16.3.2 (4294967295/28160), Serial0/0/0
P 192.168.10.8/30, 1 successors, FD is 3523840
via 192.168.10.6 (3523840/3011840), Serial0/0/1
via 172.16.3.2 (4294967295/3011840), Serial0/0/0
P 192.168.0.0/22, 1 successors, FD is 3523840
via 192.168.10.6 (3523840/3011840), Serial0/0/1
via 172.16.3.2 (4294967295/3523840), Serial0/0/0
P 192.168.10.4/30, 1 successors, FD is 2169856
via Connected, Serial0/0/1

Ở đây route 192.168.0.0/22 có 1 Successor 192.168.10.6(R3) và 1 FC 172.16.3.2(R2)
nhưng trên hình cho thấy RD(của R2)= FD(R3)= 3523840
vậy điều kiện = ở đây được thỏa. có điều gì đó không đúng ở đây??????
Mong anh giải thích giúp!
Thanks!

Chào bạn,

Nếu được thì bạn có thể post mô hình của bạn lên cho mọi người cùng tham khảo được không.
show ip eigrp topology thì hiện tất cả các successors và feasible successors. Và điều kiện ở đây là nhỏ hơn chứ không có bằng (tuy có một số sách vẫn nói có bằng), lúc thi cử thì cũng chỉ chọn nhỏ hơn mà thôi.

Khi có từ khóa all-link thì nó sẽ hiện lên tất cả các route tới đích, lúc này thì bằng sẽ thấy.
R1#sh ip ei topology
IP-EIGRP Topology Table for AS(1)/ID(10.1.103.1)

Codes: P - Passive, A - Active, U - Update, Q - Query, R - Reply,
r - reply Status, s - sia Status

P 3.0.0.0/8, 1 successors, FD is 2297856
via 10.1.103.3 (2297856/128256), Serial1/1
P 10.1.103.0/29, 1 successors, FD is 2169856
via Connected, Serial1/1
P 10.1.102.0/29, 1 successors, FD is 2169856
via Connected, Serial1/0
P 10.1.203.0/29, 2 successors, FD is 2681856
via 10.1.103.3 (2681856/2169856), Serial1/1
via 10.1.102.2 (2681856/2169856), Serial1/0

R1#sh ip ei topology all-links
IP-EIGRP Topology Table for AS(1)/ID(10.1.103.1)

Codes: P - Passive, A - Active, U - Update, Q - Query, R - Reply,
r - reply Status, s - sia Status

P 3.0.0.0/8, 1 successors, FD is 2297856, serno 17
via 10.1.103.3 (2297856/128256), Serial1/1
via 10.1.102.2 (2809856/2297856), Serial1/0
P 10.1.103.0/29, 1 successors, FD is 2169856, serno 14
via Connected, Serial1/1
P 10.1.102.0/29, 1 successors, FD is 2169856, serno 13
via Connected, Serial1/0
P 10.1.203.0/29, 2 successors, FD is 2681856, serno 18
via 10.1.103.3 (2681856/2169856), Serial1/1
via 10.1.102.2 (2681856/2169856), Serial1/0

[dothanhkhanh]

Chào bạn,

Nếu được thì bạn có thể post mô hình của bạn lên cho mọi người cùng tham khảo được không.
show ip eigrp topology thì hiện tất cả các successors và feasible successors. Và điều kiện ở đây là nhỏ hơn chứ không có bằng (tuy có một số sách vẫn nói có bằng), lúc thi cử thì cũng chỉ chọn nhỏ hơn mà thôi.

Khi có từ khóa all-link thì nó sẽ hiện lên tất cả các route tới đích, lúc này thì bằng sẽ thấy.
R1#sh ip ei topology
IP-EIGRP Topology Table for AS(1)/ID(10.1.103.1)

Codes: P - Passive, A - Active, U - Update, Q - Query, R - Reply,
r - reply Status, s - sia Status

P 3.0.0.0/8, 1 successors, FD is 2297856
via 10.1.103.3 (2297856/128256), Serial1/1
P 10.1.103.0/29, 1 successors, FD is 2169856
via Connected, Serial1/1
P 10.1.102.0/29, 1 successors, FD is 2169856
via Connected, Serial1/0
P 10.1.203.0/29, 2 successors, FD is 2681856
via 10.1.103.3 (2681856/2169856), Serial1/1
via 10.1.102.2 (2681856/2169856), Serial1/0

R1#sh ip ei topology all-links
IP-EIGRP Topology Table for AS(1)/ID(10.1.103.1)

Codes: P - Passive, A - Active, U - Update, Q - Query, R - Reply,
r - reply Status, s - sia Status

P 3.0.0.0/8, 1 successors, FD is 2297856, serno 17
via 10.1.103.3 (2297856/128256), Serial1/1
via 10.1.102.2 (2809856/2297856), Serial1/0
P 10.1.103.0/29, 1 successors, FD is 2169856, serno 14
via Connected, Serial1/1
P 10.1.102.0/29, 1 successors, FD is 2169856, serno 13
via Connected, Serial1/0
P 10.1.203.0/29, 2 successors, FD is 2681856, serno 18
via 10.1.103.3 (2681856/2169856), Serial1/1
via 10.1.102.2 (2681856/2169856), Serial1/0

Cám ơn bạn đã sure cho mình vấn đề này. Khi đọc trong sách của CiscoPress thì cũng chỉ nhỏ hơn.
Bây giờ thì mình đã chắc chắn vấn đề.
Còn về bài Lab do mình làm DEMO trên PacketTracer nên mình ko tin vào thằng này lắm! Nhất là khi chạy STP nó rất cùi..... :))
Tiện đây, về EIGRP mình xin hỏi bạn thêm câu này:

Refer to the exhibit, How may paths can be used by the EIGRP routing process to forward packets from RouterA to a neighbor router?

RouterA>show ip protocols
Routing Protocol is "eigrp 1 "
Outgoing update filter list for all interfaces is not set
Incoming update filter list for all interfaces is not set
Default networks flagged in outgoing updates
Default networks accepted from incoming updates
EIGRP metric weight K1=1, K2=0, K3=1, K4=0, K5=0
EIGRP maximum hopcount 100
EIGRP maximum metric variance 3
Redistributing: eigrp 1
Automatic network summarization is not in effect
Automatic address summarization:
Maximum path: 4
Routing for Networks:
20.10.10.0/24
172.30.10.0/24
192.168.1.0
Routing Information Sources:
Gateway Distance Last Update
192.168.1.1 90 93
172.16.10.2 90 4954
Distance: internal 90 external 170

a. two equal-cost paths
b. three unequal-cost paths
c. four equal-cost paths
d. four unequal-cost paths(*)

Theo như trên hình thấy thì variance 3 tức là nó cho phép unequal-cost load balancing thêm những route nào có Metric nhỏ hơn so với 3 lần Metric tốt nhất(theo mình hiểu là như vậy).
Còn cái Maximum path: 4 này là giá trị default của EIGRP, với câu hỏi trên thì phương án c và d đều có thể đúng chứ nhỉ???(theo ý mình là vậy)
Theo như đáp án là d(và ko có giải thích gì thêm [-( )....
Mình thì nghĩ c cũng đúng bởi giả sử có 4 route cùng có best Metric thì sao!!!

Nhờ bạn giúp mình sure hơn về vấn đề này. Thank a lot!!!

P/S: kiến thức về unequal-cost load balancing là của CCNP vậy mà trong P4***(v8.17) lại hỏi?:-SS
Không biết đây là câu hỏi của đề thì CISCO hay là của bên p4*** tự nghĩ ra nữa...... :))
Tiện mình up cái DEMO bài lab EIGRP file .ptk để bạn xem giúp mình.
Thanks phát nữa! :D

[phamminhtuan]

Chào bạn,
Về Maximum path: 4, thì c và d đều đúng. Khi nói về loadbalance với EIGRP thì hầu hết mọi tài liệu chỉ đề cập đến unequal-cost. Còn equal-cost thì giao thức nào cũng có chứ không chỉ riêng EIGRP, nên chọn D.
Và mấy câu hỏi như vậy không chỉ demo đâu. Vì CCNA sẽ phải biết và lên CCNP sẽ sâu thêm.

Còn về lab của bạn mình có xem qua, khi show lên mình thấy dùng lí thuyết, chứ ko như lúc đầu bạn đề cập.
R1#sh ip eigrp topology all-links
IP-EIGRP Topology Table for AS 100

Codes: P - Passive, A - Active, U - Update, Q - Query, R - Reply,
r - Reply status

P 172.16.1.0/24, 1 successors, FD is 28160
via Connected, FastEthernet0/0
P 192.168.11.0/24, 1 successors, FD is 28160
via Connected, FastEthernet0/1
P 192.168.10.4/30, 1 successors, FD is 2169856
via Connected, Serial0/0/1
P 172.16.3.0/30, 1 successors, FD is 40512000
via Connected, Serial0/0/0
P 172.16.2.0/24, 1 successors, FD is 3526400
via 192.168.10.6 (3526400/3014400), Serial0/0/1
via 172.16.3.2 (4294967295/28160), Serial0/0/0
P 192.168.10.8/30, 1 successors, FD is 3523840
via 192.168.10.6 (3523840/3011840), Serial0/0/1
via 172.16.3.2 (4294967295/3011840), Serial0/0/0
P 192.168.0.0/22, 1 successors, FD is 2681856
via 192.168.10.6 (2681856/2169856), Serial0/0/1

Nếu bạn có ý định học lên cao nữa thì bạn nên dùng GNS3, dễ xài và là IOS thật.
Còn packet tracer chỉ là soft giả lập thôi, nên thiếu lệnh rất nhiều và nhiều lúc chạy sai, hay bị lỗi khi bạn dấu loop.

[dothanhkhanh]

Ý, sao khi show R1 kết quả của bạn là vậy nhỉ, cái route 192.168.0.0/22 khi bạn show có thêm option all-link là:
P 192.168.0.0/22, 1 successors, FD is 2681856
via 192.168.10.6 (2681856/2169856), Serial0/0/1
trong khi mình show là:
R1#show ip eigrp topology all-links
IP-EIGRP Topology Table for AS 100

Codes: P - Passive, A - Active, U - Update, Q - Query, R - Reply,
r - Reply status

P 172.16.1.0/24, 1 successors, FD is 28160
via Connected, FastEthernet0/0
P 192.168.11.0/24, 1 successors, FD is 28160
via Connected, FastEthernet0/1
P 172.16.3.0/30, 1 successors, FD is 40512000
via Connected, Serial0/0/0
P 192.168.10.4/30, 1 successors, FD is 2169856
via Connected, Serial0/0/1
P 172.16.2.0/24, 1 successors, FD is 3526400
via 192.168.10.6 (3526400/3014400), Serial0/0/1
via 172.16.3.2 (4294967295/28160), Serial0/0/0
P 192.168.10.8/30, 1 successors, FD is 3523840
via 192.168.10.6 (3523840/3011840), Serial0/0/1
via 172.16.3.2 (4294967295/3011840), Serial0/0/0
P 192.168.0.0/22, 1 successors, FD is 3523840
via 192.168.10.6 (3523840/3011840), Serial0/0/1
via 172.16.3.2 (4294967295/3523840), Serial0/0/0
FD của mình show là 3523840 cơ mà, thêm nữa bạn đã thử show ip eigrp topology ko có option all-link chưa vậy?
Mà mình nghĩ vấn đề ở đây là do PC cùi bắp nên có sai sót thôi!
Anyway, Thanks alot!

[phamminhtuan]

Chào bạn,
Bây giờ show thì nó lại hiện như bạn nói đó. Do đó, có thể nói soft này dở lắm.
Làm trên GNS3 bảo đảm đúng như thật.

R1#sh ip eigrp topology
IP-EIGRP Topology Table for AS 100

Codes: P - Passive, A - Active, U - Update, Q - Query, R - Reply,
r - Reply status

P 172.16.1.0/24, 1 successors, FD is 28160
via Connected, FastEthernet0/0
P 192.168.11.0/24, 1 successors, FD is 28160
via Connected, FastEthernet0/1
P 192.168.10.4/30, 1 successors, FD is 2169856
via Connected, Serial0/0/1
P 172.16.3.0/30, 1 successors, FD is 40512000
via Connected, Serial0/0/0
P 192.168.10.8/30, 1 successors, FD is 3523840
via 192.168.10.6 (3523840/3011840), Serial0/0/1
via 172.16.3.2 (41024000/3011840), Serial0/0/0
P 192.168.0.0/22, 1 successors, FD is 3523840
via 192.168.10.6 (3523840/3011840), Serial0/0/1
via 172.16.3.2 (41536000/3523840), Serial0/0/0
P 172.16.2.0/24, 1 successors, FD is 3526400
via 192.168.10.6 (3526400/3014400), Serial0/0/1
via 172.16.3.2 (40514560/28160), Serial0/0/0

R1#sh ip eigrp topology all-links
IP-EIGRP Topology Table for AS 100

Codes: P - Passive, A - Active, U - Update, Q - Query, R - Reply,
r - Reply status

P 172.16.1.0/24, 1 successors, FD is 28160
via Connected, FastEthernet0/0
P 192.168.11.0/24, 1 successors, FD is 28160
via Connected, FastEthernet0/1
P 192.168.10.4/30, 1 successors, FD is 2169856
via Connected, Serial0/0/1
P 172.16.3.0/30, 1 successors, FD is 40512000
via Connected, Serial0/0/0
P 192.168.10.8/30, 1 successors, FD is 3523840
via 192.168.10.6 (3523840/3011840), Serial0/0/1
via 172.16.3.2 (41024000/3011840), Serial0/0/0
P 192.168.0.0/22, 1 successors, FD is 3523840
via 192.168.10.6 (3523840/3011840), Serial0/0/1
via 172.16.3.2 (41536000/3523840), Serial0/0/0
P 172.16.2.0/24, 1 successors, FD is 3526400
via 192.168.10.6 (3526400/3014400), Serial0/0/1
via 172.16.3.2 (40514560/28160), Serial0/0/0

[dothanhkhanh]

chào Tuấn!
rất cám ơn vì bạn đã nhiệt tình trả lời giúp mình! >:D<
Mình cũng dùng GNS3 nhưng vì máy cấu hình không cao lắm nên ngại dùng GNS3, với lại mình dùng PT làm cho tiện ý mà :D.
Tiện đây mình muốn Tuấn tư vấn giúp nếu mình muốn tự học CCNP thì chỉ dùng GNS3 thôi không có đủ DEMO Các bài LAB của 4 course CCNP ko vậy?.
(Tại học phí CCNP cao quá nên chưa thể học ngay được :( )

[phamminhtuan]

chào Tuấn!
rất cám ơn vì bạn đã nhiệt tình trả lời giúp mình! >:D<
Mình cũng dùng GNS3 nhưng vì máy cấu hình không cao lắm nên ngại dùng GNS3, với lại mình dùng PT làm cho tiện ý mà :D.
Tiện đây mình muốn Tuấn tư vấn giúp nếu mình muốn tự học CCNP thì chỉ dùng GNS3 thôi không có đủ DEMO Các bài LAB của 4 course CCNP ko vậy?.
(Tại học phí CCNP cao quá nên chưa thể học ngay được :( )

Chào bạn,
Nếu không có điều kiện thì đợi khi đi làm có tiền rồi học sau, vì tự học dễ đi lệch hướng, nếu không có quyết tâm cao và cũng mau chán. Lệch hướng rồi thì khó sửa.
Nếu tự học và bên Hà Nội thì mua mấy cuốn sách labpro của Vnpro về ngồi xem lí thuyết và lab cũng ok lắm.

Về GNS3 thì theo mình nghĩ đủ demo:
BSCI:90% cource này ai nói dễ chứ mình thấy nó không dễ đâu. Nền tảng cho mấy cource sau.
BCMSN: 60% Ứng dụng nhiều trong công ty đã và đang triển khai.
ISCW: 80% Ứng dụng được nhiều nhất nếu đi triển khai.
ONT: 40% Làm mạng tối ưu hơn.

Về độ khó thì BSCI>ISCW>ONT>=BCMSN

[dothanhkhanh]

:)
Hì, rất cám ơn những lời khuyên chân thành của Tuấn, mình sẽ cân nhắc kỹ vấn đề này!
Nhưng mình thấy với chỉ CCNA(bằng đại học thì có rồi) mà xin đi làm thì rất khó xin được việc làm về bên Network này...mình thấy chỗ nào cũng hầu như đòi có CCNP không thì CCNA cũng phải có ít nhất 1năm kinh nghiệm, nản luôn! :( . Mà học cái này quan trọng nhất là kinh nghiệm thức tế, chứ cứ ngồi ôm sách không thôi chẳng ăn thua....
Mà Tuấn bảo ở ngoài này cũng có bán sách Lab của VNPro cơ ah???
Tuấn có thể chỉ rõ hơn ở chỗ nào bán không?
Giá như mình ở trong đó thì tốt, nếu đi học CCNP chắc chắn mình tới VNPro! :D
Mình là mình rất kết các Instructor của VNPro rất nhiệt tình và Pro, :113:

[phamminhtuan]

Chào bạn,

Về sách thì bạn liên hệ thử xem,

http://vnpro.org/forum/showthread.php?p=113494#post113494