ಡ್ಯುಯಲ್ ಡಿಫ್ಯೂಸ್ ಅಪ್ಡೇಟ್ ಅಲ್ಗಾರಿದಮ್

ನೀವು ಈ ಲೇಖನವನ್ನು ಓದುವ ಮೊದಲು, ಬೆಲ್ಮನ್ - ಫೋರ್ಡ್ ಅಲ್ಗಾರಿದಮ್ನ ಪ್ರಕಾರ ಹಾದಿಯನ್ನು ಲೆಕ್ಕಾಚಾರದ ಬಗ್ಗೆ ವಸ್ತುಗಳೊಂದಿಗೆ ನಿಮ್ಮನ್ನು ಪರಿಚಯಿಸಲು ನಾವು ಸಲಹೆ ನೀಡುತ್ತೇವೆ.

ಡಿಫ್ಯೂಷನ್ ಅಪ್ಡೇಟ್ ಅಲ್ಗಾರಿದಮ್ (ಡಿಫ್ಯೂಷನ್ ಅಪ್ಡೇಟ್ ಅಲ್ಗಾರಿದಮ್ -ಡೌಲ್) ಇಲ್ಲಿ ಚರ್ಚಿಸಲಾದ ಎರಡು ಕ್ರಮಾವಳಿಗಳಲ್ಲಿ ಒಂದಾಗಿದೆ, ಇಲ್ಲಿ ವಿತರಿಸಲಾದ ನೆಟ್ವರ್ಕ್ನಲ್ಲಿ ಅನುಷ್ಠಾನಕ್ಕೆ ಉದ್ದೇಶಿಸಲಾಗಿದೆ. ಅಲ್ಗಾರಿದಮ್ನ ಅಂತಿಮ ಸ್ವಯಂಚಾಲಿತವಾಗಿ ಒಳಗೊಂಡಿರುವ ಸಾಕುತನ ಮತ್ತು ಟೋಪೋಲಜಿಯ ಬಗ್ಗೆ ಮಾಹಿತಿಯನ್ನು ತೆಗೆದುಹಾಕುವುದು ಇದರಲ್ಲಿ ಅನನ್ಯವಾಗಿದೆ. ಇಲ್ಲಿ ಚರ್ಚಿಸಲಾದ ಇತರ ಕ್ರಮಾವಳಿಗಳು ಪ್ರೋಟೋಕಾಲ್ನ ಅನುಷ್ಠಾನದ ವಿವೇಚನೆಯಿಂದ ಮಾಹಿತಿಯನ್ನು ತೆಗೆಯುವುದನ್ನು ಬಿಟ್ಟುಬಿಡುತ್ತವೆ ಮತ್ತು ಅಲ್ಗಾರಿದಮ್ನಲ್ಲಿ ಅಲ್ಗಾರಿದಮ್ನ ಕೆಲಸದ ಈ ಅಂಶವನ್ನು ಪರಿಗಣಿಸುವುದಿಲ್ಲ.

1993 ರ ಹೊತ್ತಿಗೆ, ಬೆಲ್ಮನ್-ಫೋರ್ಡ್ ಮತ್ತು ಡಿಜ್ಕ್ಸ್ಟ್ರಾವನ್ನು ಹಲವಾರು ರೂಟಿಂಗ್ ಪ್ರೋಟೋಕಾಲ್ಗಳಲ್ಲಿ ವಿತರಿಸಿದ ಕ್ರಮಾವಳಿಗಳಾಗಿ ಅಳವಡಿಸಲಾಯಿತು. ಈ ಆರಂಭಿಕ ಅನುಷ್ಠಾನಗಳು ಮತ್ತು ನಿಯೋಜನೆಗಳ ಪರಿಣಾಮವಾಗಿ ಪಡೆದ ಅನುಭವವು ನೆಟ್ವರ್ಕ್ ಸ್ವಿಚಿಂಗ್ ನೆಟ್ವರ್ಕ್ಗಳಲ್ಲಿ ರೂಟಿಂಗ್ನ ಸಮಸ್ಯೆಗೆ "ಎರಡನೇ ತರಂಗ" ಸಂಶೋಧನೆ ಮತ್ತು ಪ್ರತಿಬಿಂಬಕ್ಕೆ ಕಾರಣವಾಯಿತು, ಇದು ಪಥ ವೆಕ್ಟರ್ ಮತ್ತು ಡ್ಯುಯಲ್ನ ನೋಟಕ್ಕೆ ಕಾರಣವಾಯಿತು.

ಡ್ಯುಯಲ್ ವಿತರಿಸಿದ ಅಲ್ಗಾರಿದಮ್ ಆಗಿ ವಿನ್ಯಾಸಗೊಳಿಸಲ್ಪಟ್ಟಿರುವುದರಿಂದ, ನೆಟ್ವರ್ಕ್ನಲ್ಲಿ ಅವರ ಕೆಲಸವನ್ನು ವಿವರಿಸಲು ಉತ್ತಮವಾಗಿದೆ. ಈ ಉದ್ದೇಶಕ್ಕಾಗಿ, 8 ಮತ್ತು 9 ಅಂಕಿಗಳನ್ನು ಬಳಸಲಾಗುತ್ತದೆ. ಡ್ಯುಯಲ್ ಅನ್ನು ವಿವರಿಸಲು, ಈ ಉದಾಹರಣೆಯನ್ನು ಮೂರು ಸ್ಥಳಗಳ ಸ್ಟ್ರೀಮ್ನಲ್ಲಿ ಪತ್ತೆಹಚ್ಚಲಾಗುತ್ತದೆ, ತದನಂತರ ಅದೇ ಗಮ್ಯಸ್ಥಾನದ ಐಟಂಗಳಿಗಾಗಿ ಲಭ್ಯತೆ ಸ್ಥಿತಿಯಲ್ಲಿ ಬದಲಾವಣೆಗಳನ್ನು ಪ್ರಕ್ರಿಯೆಗೊಳಿಸಲಾಗುತ್ತದೆ. ಮೊದಲ ಉದಾಹರಣೆಯಲ್ಲಿ, ಪರ್ಯಾಯ ಮಾರ್ಗವಿದ್ದಾಗ ಈ ಪ್ರಕರಣವನ್ನು ಪರಿಗಣಿಸಲಾಗುತ್ತದೆ, ಆದರೆ ಕೆಳಮಟ್ಟದ ನೆರೆಹೊರೆ ಇಲ್ಲ, ಎರಡನೆಯ ಪರ್ಯಾಯ ಮಾರ್ಗ ಮತ್ತು ಕೆಳಭಾಗದ ನೆರೆಹೊರೆಯಲ್ಲಿ ಎರಡನೆಯದು ಸಂಭವಿಸುತ್ತದೆ.

ಚಿತ್ರ 8 ರಲ್ಲಿ, ದೃಷ್ಟಿಕೋನದಿಂದ ಅಧ್ಯಯನ ಡಿ:

1. ಡಿ ಗೆ ಎರಡು ಮಾರ್ಗಗಳು ಕಲಿಯುತ್ತವೆ:

1. ಬಿ ಮೂಲಕ ಬೌ ಮೂಲಕ ಮಾರ್ಗವನ್ನು ಗುರುತಿಸುವುದಿಲ್ಲ, ಏಕೆಂದರೆ ಬಿ ಅದರ ಉತ್ತರಾಧಿಕಾರಿಯಾಗಿ ಬಳಸುತ್ತದೆ:
2. ಲಭ್ಯವಿರುವ ಮಾರ್ಗಗಳನ್ನು ಹೋಲಿಸುತ್ತದೆ ಮತ್ತು ಲೂಪ್ ಇಲ್ಲದೆ ಕಡಿಮೆ ಮಾರ್ಗವನ್ನು ಆಯ್ಕೆ ಮಾಡುತ್ತದೆ:
3. ಅವುಗಳಲ್ಲಿ ಯಾವುದಾದರೂ ಡೌನ್ಸ್ಟ್ರೀಮ್ ನೆರೆಯವರು ಇದ್ದರೆ ನಿರ್ಧರಿಸಲು ಉಳಿದ ಮಾರ್ಗಗಳನ್ನು ಪರಿಶೀಲಿಸುತ್ತದೆ:

ಇದು ತಿಳಿದಿದೆ ಏಕೆಂದರೆ ಸಿ ಮಾರ್ಗವನ್ನು ಅದರ ಸ್ಥಳೀಯ ಮೆಟ್ರಿಕ್ 3 ಕ್ಕೆ ಸಮಾನವಾಗಿ ಘೋಷಿಸುತ್ತದೆ.

ಅದರ ಟೋಪೋಲಜಿ ಟೇಬಲ್ನಲ್ಲಿ ಸ್ಥಳೀಯ ಮೆಟ್ರಿಕ್ ಸಿ ನಿರ್ವಹಿಸುತ್ತದೆ.

ಪರಿಣಾಮವಾಗಿ, ಸಿ ಮತ್ತು ಸ್ಥಳೀಯ ಮೌಲ್ಯದಲ್ಲಿ ಸ್ಥಳೀಯ ಮೌಲ್ಯವನ್ನು ತಿಳಿದಿರುತ್ತದೆ.

1. 3 (C ನಲ್ಲಿ C) = 3 (ವೆಚ್ಚದಲ್ಲಿ), ಆದ್ದರಿಂದ ಈ ಮಾರ್ಗವು ಲೂಪ್ ಆಗಿರಬಹುದು, ಆದ್ದರಿಂದ, ಸಿ ಕಾರ್ಯಸಾಧ್ಯತೆಯ ಸ್ಥಿತಿಯನ್ನು ಪೂರೈಸುವುದಿಲ್ಲ. ಸಿ ಕೆಳಗಿರುವ ನೆರೆಹೊರೆಯವರಂತೆ ಲೇಬಲ್ ಮಾಡಲಾಗಿಲ್ಲ.

ಡ್ಯುಯಲ್ನಲ್ಲಿ ಡೌನ್ಸ್ಟ್ರೀಮ್ ನೆರೆಹೊರೆಯವರು ಸಂಭವನೀಯ ಉತ್ತರಾಧಿಕಾರಿಗಳನ್ನು ಕರೆಯಲಾಗುತ್ತದೆ. ಚಾನಲ್ [ಎ, ಎಚ್] ಕೆಲಸ ಮಾಡುವುದಿಲ್ಲ ಎಂದು ಭಾವಿಸೋಣ. ಡ್ಯುಯಲ್ ಆವರ್ತಕ ನವೀಕರಣಗಳನ್ನು ಅವಲಂಬಿಸಿಲ್ಲ, ಆದ್ದರಿಂದ ವಿಶ್ವಾಸಾರ್ಹ ಮಾಹಿತಿಯೊಂದಿಗೆ ಮತ್ತೊಂದು ಅಪ್ಡೇಟ್ಗಾಗಿ ಕಾಯಲು ಸಾಧ್ಯವಿಲ್ಲ. ಬದಲಿಗೆ, ಒಂದು ಪರ್ಯಾಯ ಮಾರ್ಗವನ್ನು ಸಕ್ರಿಯವಾಗಿ ಅನುಸರಿಸಬೇಕು. ಹೀಗಾಗಿ, ಇದು ಪರ್ಯಾಯ ಪಥದ ಪ್ರಸರಣ ಪತ್ತೆ ಪ್ರಕ್ರಿಯೆಯಾಗಿದೆ. ಚಾನಲ್ [ಎ, ಎಚ್] ಕೆಲಸ ಮಾಡುವುದಿಲ್ಲ, ಕೇವಲ ಡಿ ಪರಿಗಣಿಸಿ:

1. ಸಂಭವನೀಯ ಉತ್ತರಾಧಿಕಾರಿಗಳಿಗೆ (ಡೌನ್ಸ್ಟ್ರೀಮ್ ನೆರೆಹೊರೆಯವರು) ನಿಮ್ಮ ಸ್ಥಳೀಯ ಟೇಬಲ್ ಅನ್ನು ಪರಿಶೀಲಿಸುತ್ತದೆ.
2. ಸಂಭವನೀಯ ಉತ್ತರಾಧಿಕಾರಿಗಳಿಲ್ಲ, ಆದ್ದರಿಂದ ಡಿ (ಅದು ಅಸ್ತಿತ್ವದಲ್ಲಿದ್ದರೆ) ಇಲ್ಲದೆ ಪರ್ಯಾಯ ಮಾರ್ಗವನ್ನು ಕಂಡುಹಿಡಿಯಬೇಕು.
3. ಡಿ ಗೆ ಲೂಪ್ ಇಲ್ಲದೆ ಯಾವುದೇ ಪರ್ಯಾಯ ಮಾರ್ಗವಿದ್ದಲ್ಲಿ ನಿರ್ಧರಿಸಲು ಪ್ರತಿ ನೆರೆಯವರಿಗೆ ವಿನಂತಿಯನ್ನು ಕಳುಹಿಸುತ್ತದೆ.
4. ಸಿ:
5. ಬಿ:
6. ಎ ಈ ಉತ್ತರಗಳನ್ನು ಪಡೆಯುತ್ತದೆ:

ಚಿತ್ರ 9 ರಲ್ಲಿ, ಗಮ್ಯಸ್ಥಾನ (ಡಿ) ಐಟಂ ಅನ್ನು H ಗೆ ಸ್ಥಳಾಂತರಿಸಲಾಯಿತು. ಇದನ್ನು ಎರಡನೇ ಉದಾಹರಣೆಯಲ್ಲಿ ಬಳಸಲಾಗುವುದು.

ಈ ಉದಾಹರಣೆಯಲ್ಲಿ, ಸಂಭವನೀಯ ಉತ್ತರಾಧಿಕಾರಿ (ಡೌನ್ಸ್ಟ್ರೀಮ್ ನೆರೆಹೊರೆ) ಇರುತ್ತದೆ.

ಅಧ್ಯಯನ ಡಿ ದೃಷ್ಟಿಕೋನದಿಂದ ಎ:

1. ಡಿ ಗೆ ಎರಡು ಮಾರ್ಗಗಳು ಕಲಿಯುತ್ತವೆ:
2. ಎ ಮೂಲಕ ಯಾವುದೇ ರೀತಿಯಲ್ಲಿ ಗುರುತಿಸುವುದಿಲ್ಲ:
3. ಲಭ್ಯವಿರುವ ಮಾರ್ಗಗಳನ್ನು ಹೋಲಿಸುತ್ತದೆ ಮತ್ತು ಲೂಪ್ ಇಲ್ಲದೆ ಕಡಿಮೆ ಮಾರ್ಗವನ್ನು ಆಯ್ಕೆ ಮಾಡುತ್ತದೆ:
4. ಅವುಗಳಲ್ಲಿ ಯಾವುದಾದರೂ ಡೌನ್ಸ್ಟ್ರೀಮ್ ನೆರೆಯವರು ಇದ್ದರೆ ನಿರ್ಧರಿಸಲು ಉಳಿದ ಮಾರ್ಗಗಳನ್ನು ಪರಿಶೀಲಿಸುತ್ತದೆ:

ಚಾನಲ್ [ಎ, ಸಿ] ಕೆಲಸ ಮಾಡುವುದಿಲ್ಲ, ಕೇವಲ ಒಂದು ಪರಿಗಣಿಸಿ:

1. ಸಂಭವನೀಯ ಉತ್ತರಾಧಿಕಾರಿಗಾಗಿ ಸ್ಥಳೀಯ ಟೋಪೋಲಜಿಯ ಟೇಬಲ್ ಅನ್ನು ಪರಿಶೀಲಿಸುತ್ತದೆ.
2. ಸಂಭವನೀಯ ಉತ್ತರಾಧಿಕಾರಿ ಎಚ್ ಮೂಲಕ ಅಸ್ತಿತ್ವದಲ್ಲಿದೆ.
3. ಅದರ ಸ್ಥಳೀಯ ಟೇಬಲ್ ಅನ್ನು ಎಚ್ನಲ್ಲಿ ಉತ್ತಮ ರೀತಿಯಲ್ಲಿ ಸ್ವಿಚ್ ಮಾಡುತ್ತದೆ.
4. ಅದರ ನೆರೆಹೊರೆಯವರಿಗೆ ಒಂದು ಅಪ್ಡೇಟ್ ಅನ್ನು ಕಳುಹಿಸುತ್ತದೆ, ಅದರ ಸಾಧನೆಯ ವೆಚ್ಚವು 3 ರಿಂದ 4 ರವರೆಗೆ ಬದಲಾಗಿದೆ ಎಂದು ಸೂಚಿಸುತ್ತದೆ.

ನೀವು ನೋಡುವಂತೆ, ಸಂಭವನೀಯ ಉತ್ತರಾಧಿಕಾರಿಯಾದಾಗ, ಅದು ಇಲ್ಲದೆಯೇ ಹೆಚ್ಚು ವೇಗವಾಗಿ ಮತ್ತು ಸುಲಭವಾಗಿರುತ್ತದೆ. ರೂಟಿಂಗ್ ಪ್ರೋಟೋಕಾಲ್ ಅನ್ನು ದ್ವಿಗುಣ (ನಿರ್ದಿಷ್ಟವಾಗಿ, iigrp) ಬಳಸಿಕೊಂಡು, ಪ್ರಮುಖ ವಿನ್ಯಾಸದ ಉದ್ದೇಶಗಳಲ್ಲಿ ಒಂದಾದ ಸಂಭಾವ್ಯ ಉತ್ತರದ ಅನುಪಸ್ಥಿತಿಯಲ್ಲಿ ಉತ್ಪತ್ತಿಯಾಗುವ ಯಾವುದೇ ವಿನಂತಿಗಳ ಪರಿಮಾಣವನ್ನು ಮಿತಿಗೊಳಿಸುತ್ತದೆ. ವಿನಂತಿಯ ಪ್ರದೇಶವು ಎರಡು ಅಲ್ಗಾರಿದಮ್ ತ್ವರಿತವಾಗಿ ಪೂರ್ಣಗೊಂಡಿದೆ ಮತ್ತು, ಆದ್ದರಿಂದ, ಜಾಲಬಂಧವು ಎಷ್ಟು ಬೇಗನೆ ಒಮ್ಮುಖವಾಗಿರುತ್ತದೆ ಎಂಬುದರ ಮುಖ್ಯ ನಿರ್ಣಯ ಅಂಶವಾಗಿದೆ.

ಚಿತ್ರ 10 ಮೂಲ ಮುಗಿದ ದ್ವಂದ್ವ ಯಂತ್ರವನ್ನು ತೋರಿಸುತ್ತದೆ.

ಮಾರ್ಗದಲ್ಲಿ ಒಳಗೊಂಡಿರುವ ವಿಷಯಗಳು ಕೆಟ್ಟದಾಗಿದೆ (ಮಾರ್ಗದ ಅವನತಿ) ಇರಬಹುದು:

• ಸಂಪರ್ಕಿತ ಚಾನಲ್ ಅಥವಾ ನೆರೆಯವರ ವೈಫಲ್ಯ
• ಹೆಚ್ಚಿನ ಮೆಟ್ರಿಕ್ನ ಮಾರ್ಗಕ್ಕಾಗಿ ನವೀಕರಣವನ್ನು ಪಡೆಯುವುದು
• ಪ್ರಸ್ತುತ ಉತ್ತರಾಧಿಕಾರಿಯಿಂದ ಪ್ರಶ್ನೆಯನ್ನು ಪಡೆಯುವುದು
• ನೆರೆಯವರಿಂದ ಹೊಸ ಮಾರ್ಗವನ್ನು ಪಡೆಯುವುದು
• ಹೊಸ ನೆರೆಯವರು ಕಂಡುಬಂದರು, ಹಾಗೆಯೇ ಅದು ಪಡೆಯುವ ಮಾರ್ಗಗಳು
• ಮಾರ್ಗವು ಹದಗೆಟ್ಟಾಗ ಎಲ್ಲ ವಿನಂತಿಗಳನ್ನು ನೆರೆಹೊರೆಯವರಿಗೆ ಕಳುಹಿಸಲಾಗಿದೆ