ਇਸ ਲੇਖ ਨੂੰ ਪੜ੍ਹਨ ਦੀ ਸ਼ੁਰੂਆਤ ਕਰਨ ਤੋਂ ਪਹਿਲਾਂ, ਅਸੀਂ ਤੁਹਾਨੂੰ ਆਪਣੇ ਆਪ ਨੂੰ ਸਲਾਹ ਦਿੰਦੇ ਹਾਂ ਕਿ ਬੇਲਮੈਨ - ਫੋਰਡ ਐਲਗੋਰਿਥਮ ਦੇ ਅਨੁਸਾਰ ਪਾਥ ਦੀ ਗਣਨਾ ਬਾਰੇ ਆਪਣੇ ਆਪ ਨੂੰ ਜਾਣੂ ਕਰੋ.
ਫੈਲਾਅ ਅਪਡੇਟ ਐਲਗੋਰਿਦਮ (ਫੈਲਣ ਨਾਲ ਅਪਡੇਟ ਐਲਗੋਰਿਥਮ-ਡੁਦਾਮ) ਇੱਥੇ ਇਕ ਡਿਸਟ੍ਰੀਬਿਡ ਕੀਤੇ ਨੈਟਵਰਕ ਵਿੱਚ ਲਾਗੂ ਕਰਨ ਲਈ ਵਿਚਾਰ ਵਟਾਂਦਰੇ ਲਈ ਗਏ ਦੋ ਐਲਗੋਰਿਦਮ ਵਿਚੋਂ ਇਕ ਹੈ. ਇਹ ਵਿਲੱਖਣ ਹੈ ਕਿ ਇਹ ਪ੍ਰਾਪਤੀਯੋਗਤਾ ਅਤੇ ਟੋਪੋਲੋਜੀ ਬਾਰੇ ਵੀ ਜਾਣਕਾਰੀ ਨੂੰ ਵੀ ਸ਼ਾਮਲ ਕਰਦਾ ਹੈ ਜੋ ਕਿ ਐਲਗੋਰਿਦਮ ਦੀ ਅੰਤਮ ਆਟੌਲਤਾ ਵਿੱਚ ਹੈ. ਪ੍ਰੋਟੋਕੋਲ ਬਾਰੇ ਜਾਣਕਾਰੀ ਦੇ ਹੋਰ ਐਲਗੋਰਿਦਮ ਨੂੰ ਹਟਾਉਣ ਦੇ ਧਿਆਨ ਵਿੱਚ ਰੱਖਣ ਦੇ ਧਿਆਨ ਵਿੱਚ ਜਾਣਕਾਰੀ ਨੂੰ ਹਟਾਉਣ, ਅਤੇ ਐਲਗੋਰਿਦਮ ਦੇ ਕੰਮ ਦੇ ਇਸ ਪਹਿਲੂ ਨੂੰ ਆਪਣੇ ਆਪ ਵਿਚ ਨਹੀਂ ਮੰਨਦੇ.
1993 ਤਕ, ਬੇਲਮੈਨ-ਫੋਰਡ ਅਤੇ ਡਿਜਕਸਤੜਾ ਕਈ ਰਾ ressing ਂਟਰ ਪ੍ਰੋਟੋਕੋਲ ਵਿਚ ਵੰਡਿਆ ਐਲਗੋਰਿਥਮ ਵਜੋਂ ਲਾਗੂ ਕੀਤਾ ਗਿਆ ਸੀ. ਇਹ ਤਜ਼ੁਰਬਾ ਇਨ੍ਹਾਂ ਮੁ early ਲੇ ਲਾਗੂ ਕਰਨ ਦੇ ਨਤੀਜੇ ਵਜੋਂ ਪ੍ਰਾਪਤ ਹੋਇਆ ਅਤੇ ਤੈਨਾਤਾਂ ਨੇ ਖੋਜ ਅਤੇ ਤਹਿ ਕਰਨ ਦੀ ਅਗਵਾਈ ਕੀਤੀ ਕਿ ਨੈਟਵਰਕ ਸਵਿਚਿੰਗ ਨੈਟਵਰਕਸ ਵਿੱਚ ਰੂਟਿੰਗ ਦੀ ਸਮੱਸਿਆ ਦਾ ਐਲਾਨ ਕੀਤਾ ਗਿਆ.
ਕਿਉਂਕਿ ਦੋਹਰਾ ਇੱਕ ਵੰਡਿਆ ਐਲਗੋਰਿਦਮ ਦੇ ਰੂਪ ਵਿੱਚ ਤਿਆਰ ਕੀਤਾ ਗਿਆ ਹੈ, ਨੈਟਵਰਕ ਤੇ ਉਸਦੇ ਕੰਮ ਦਾ ਵਰਣਨ ਕਰਨਾ ਸਭ ਤੋਂ ਵਧੀਆ ਹੈ. ਇਸ ਉਦੇਸ਼ ਲਈ, ਅੰਕੜੇ 8 ਅਤੇ 9 ਵਰਤੇ ਗਏ ਹਨ. ਦੋਹਰੀ ਸਮਝਾਉਣ ਲਈ, ਇਹ ਉਦਾਹਰਣ ਇਕੋ ਮੰਜ਼ਿਲ ਦੀਆਂ ਚੀਜ਼ਾਂ ਲਈ ਉਪਲਬਧਤਾ ਵਾਲੀਆਂ ਚੀਜ਼ਾਂ ਵਿੱਚ ਸੰਸਾਧਿਤ ਕੀਤੀ ਜਾਏਗੀ. ਪਹਿਲੀ ਉਦਾਹਰਣ ਵਿਚ, ਕੇਸ 'ਤੇ ਵਿਚਾਰ ਕੀਤਾ ਜਾਵੇਗਾ ਜਦੋਂ ਕੋਈ ਬਦਲਵਾਂ ਰਸਤਾ ਹੈ, ਪਰ ਹੇਠਾਂ ਕੋਈ ਥੱਲੇ ਵਾਲਾ ਗੁਆਂ neighbor ੀ ਨਹੀਂ, ਜਦੋਂ ਇਕ ਵਿਕਲਪਕ ਮਾਰਗ ਅਤੇ ਨੀਵਾਂ ਵਾਲਾ ਗੁਆਂ .ੀ ਹੈ.
ਚਿੱਤਰ 8 ਵਿੱਚ, ਬਿੰਦੂ ਦੇ ਦ੍ਰਿਸ਼ ਤੋਂ ਅਧਿਐਨ ਏ:
- ਇੱਕ ਨੂੰ ਡੀ ਲਈ ਦੋ ਤਰੀਕੇ ਸਿਖਦਾ ਹੈ:
- ਏ ਬੀ ਦੁਆਰਾ ਪਾਥ ਨੂੰ ਨਹੀਂ ਪਛਾਣਦਾ, ਕਿਉਂਕਿ ਬੀ ਇਸ ਦੇ ਉਤਰਾਧਿਕਾਰੀ ਵਜੋਂ ਵਰਤਦਾ ਹੈ:
- ਇੱਕ ਉਪਲੱਬਧ ਮਾਰਗਾਂ ਦੀ ਤੁਲਨਾ ਕਰੋ ਅਤੇ ਲੂਪਸ ਤੋਂ ਬਿਨਾਂ ਸਭ ਤੋਂ ਛੋਟਾ ਰਸਤਾ ਚੁਣਦਾ ਹੈ:
- ਇਹ ਨਿਰਧਾਰਤ ਕਰਨ ਲਈ ਬਾਕੀ ਮਾਰਗਾਂ ਦੀ ਜਾਂਚ ਕਰਦਾ ਹੈ ਕਿ ਕੀ ਉਨ੍ਹਾਂ ਵਿੱਚੋਂ ਕੋਈ ਥੀਂਹ ਦੇ ਗੁਆਂ .ੀਆਂ ਹਨ:
ਇਹ ਇਸ ਨੂੰ ਜਾਣਦਾ ਹੈ ਕਿਉਂਕਿ ਸੀ ਨੇ ਇਸ ਦੇ ਸਥਾਨਕ ਮੈਟ੍ਰਿਕ ਦੇ ਬਰਾਬਰ 3 ਦੇ ਨਾਲ ਰਸਤੇ ਦਾ ਐਲਾਨ ਕੀਤਾ.
ਇੱਕ ਸਥਾਨਕ ਮੈਟ੍ਰਿਕ ਟੇਬਲ ਵਿੱਚ ਇੱਕ ਸਥਾਨਕ ਮੈਟ੍ਰਿਕ ਸੀ ਨੂੰ ਰੱਖਦਾ ਹੈ.
ਸਿੱਟੇ ਵਜੋਂ, ਸਿਰਫ ਸੀ ਅਤੇ ਸਥਾਨਕ ਮੁੱਲ ਵਿੱਚ ਸਥਾਨਕ ਮੁੱਲ ਨੂੰ ਜਾਣਦਾ ਹੈ.
- 3 (ਸੀ ਵਿਚ ਕੀਮਤ) = 3 (ਏ ਵਿਚ ਕੀਮਤ), ਇਸ ਲਈ ਇਹ ਰਸਤਾ ਲੂਪ ਹੋ ਸਕਦਾ ਹੈ, ਇਸ ਲਈ, ਸੀ ਮਿਹਨਤੀਯੋਗਤਾ ਦੀ ਸਥਿਤੀ ਨੂੰ ਪੂਰਾ ਨਹੀਂ ਕਰਦਾ. ਸੀ ਨੂੰ ਹੇਠਾਂ ਦੇ ਗੁਆਂ .ੀਆਂ ਵਜੋਂ ਲੇਬਲ ਕੀਤਾ ਗਿਆ ਹੈ.
ਦੋਹਰੇ ਦੇ ਗੁਆਂ neighbors ੀਆਂ ਨੂੰ ਦੋਹਰੇ ਵਿਚ ਸੰਭਾਵਤ ਉਤਰਾਧਿਕਾਰੀ ਕਹਾਉਂਦੇ ਹਨ. ਮੰਨ ਲਓ ਕਿ ਚੈਨਲ [ਏ, ਐਚ] ਕੰਮ ਨਹੀਂ ਕਰਦਾ. ਦੋਹਰੀ ਅਪਡੇਟਾਂ 'ਤੇ ਨਿਰਭਰ ਨਹੀਂ ਕਰਦਾ, ਇਸ ਲਈ ਭਰੋਸੇਮੰਦ ਜਾਣਕਾਰੀ ਨਾਲ ਕਿਸੇ ਹੋਰ ਅਪਡੇਟ ਦੀ ਉਡੀਕ ਨਹੀਂ ਕਰ ਸਕਦਾ. ਇਸ ਦੀ ਬਜਾਏ, ਏ ਨੂੰ ਸਰਗਰਮੀ ਨਾਲ ਇਕ ਵਿਕਲਪਿਕ ਮਾਰਗ ਦੀ ਪਾਲਣਾ ਕਰਨੀ ਚਾਹੀਦੀ ਹੈ. ਇਸ ਤਰ੍ਹਾਂ, ਇਹ ਵਿਕਲਪਕ ਮਾਰਗ ਦੀ ਇਕ ਵੱਖਰੀ ਖੋਜ ਪ੍ਰਕਿਰਿਆ ਹੈ. ਜੇ ਚੈਨਲ [ਏ, ਐਚ] ਕੰਮ ਨਹੀਂ ਕਰਦਾ, ਸਿਰਫ ਡੀ ਤੇ ਵਿਚਾਰ ਕਰਦਾ ਹੈ:
- ਸੰਭਾਵਤ ਉਤਰਾਧਿਕਾਰੀ (ਥੱਲੇ ਵੱਲ ਗੁਆਂ .ੀਆਂ) ਲਈ ਤੁਹਾਡਾ ਸਥਾਨਕ ਟੇਬਲ ਚੈੱਕ ਕਰਦਾ ਹੈ.
- ਕੋਈ ਸੰਭਵ ਉਤਸਫਾ ਨਹੀਂ ਹਨ, ਇਸ ਲਈ ਏ ਨੂੰ ਡੀ ਤੋਂ ਬਿਨਾਂ ਕਿਸੇ ਵਿਕਲਪ ਦਾ ਰਸਤਾ ਲੱਭਣਾ ਚਾਹੀਦਾ ਹੈ (ਜੇ ਇਹ ਮੌਜੂਦ ਹੈ).
- ਹਰ ਇੱਕ ਨੇਬਰ ਨੂੰ ਇਹ ਨਿਰਧਾਰਤ ਕਰਨ ਲਈ ਬੇਨਤੀ ਭੇਜਦਾ ਹੈ ਕਿ ਕੀ ਡੀ ਲਈ ਲੂਪ ਦੇ ਕੋਈ ਵਿਕਲਪਕ ਮਾਰਗ ਹੈ ਜਾਂ ਨਹੀਂ.
- ਸੀ:
- ਵਿੱਚ ਬੀ:
- ਇਹ ਜਵਾਬ ਪ੍ਰਾਪਤ ਕਰਦਾ ਹੈ:
ਚਿੱਤਰ 9 ਵਿੱਚ, ਮੰਜ਼ਿਲ (ਡੀ) ਆਈਟਮ H ਨੂੰ H ਤੋਂ ਹਿਲਾ ਦਿੱਤੀ ਗਈ ਸੀ. ਇਹ ਦੂਜੀ ਉਦਾਹਰਣ ਵਿੱਚ ਵਰਤੀ ਜਾਏਗੀ.
ਇਸ ਉਦਾਹਰਣ ਵਿੱਚ, ਇੱਥੇ ਇੱਕ ਸੰਭਾਵਤ ਉਤਸਤ (ਥੱਲੇ ਵੱਲ) ਹੈ.
ਦ੍ਰਿਸ਼ਟੀਕੋਣ ਤੋਂ ਡੀ:
- ਇੱਕ ਨੂੰ ਡੀ ਲਈ ਦੋ ਤਰੀਕੇ ਸਿਖਦਾ ਹੈ:
- ਏ ਬੀ ਦੁਆਰਾ ਕਿਸੇ ਵੀ ਤਰੀਕੇ ਨਾਲ ਨਹੀਂ ਪਛਾਣਦਾ:
- ਇੱਕ ਉਪਲੱਬਧ ਮਾਰਗਾਂ ਦੀ ਤੁਲਨਾ ਕਰੋ ਅਤੇ ਲੂਪਸ ਤੋਂ ਬਿਨਾਂ ਸਭ ਤੋਂ ਛੋਟਾ ਰਸਤਾ ਚੁਣਦਾ ਹੈ:
- ਇਹ ਨਿਰਧਾਰਤ ਕਰਨ ਲਈ ਬਾਕੀ ਮਾਰਗਾਂ ਦੀ ਜਾਂਚ ਕਰਦਾ ਹੈ ਕਿ ਕੀ ਉਨ੍ਹਾਂ ਵਿੱਚੋਂ ਕੋਈ ਥੀਂਹ ਦੇ ਗੁਆਂ .ੀਆਂ ਹਨ:
ਜੇ ਚੈਨਲ [ਏ, ਸੀ] ਕੰਮ ਨਹੀਂ ਕਰਦਾ, ਸਿਰਫ ਏ ਨੂੰ ਮੰਨਣਾ:
- ਇੱਕ ਸੰਭਾਵਤ ਉਤਰਾਧਿਕਾਰੀ ਲਈ ਸਥਾਨਕ ਟੋਪੋਲੋਜੀ ਦਾ ਆਪਣਾ ਟੇਬਲ ਚੈੱਕ ਕਰਦਾ ਹੈ.
- ਸੰਭਾਵਤ ਉਤਰਾਧਿਕਾਰੀ ਐਚ ਦੇ ਅੰਦਰ ਮੌਜੂਦ ਹਨ.
- ਇੱਕ ਬਦਲਣਾ HY ਉੱਤੇ ਸਭ ਤੋਂ ਵਧੀਆ way ੰਗ ਨਾਲ ਬਦਲਦਾ ਹੈ.
- ਇਸ ਦੇ ਗੁਆਂ neighbors ੀਆਂ ਨੂੰ ਅਪਡੇਟ ਭੇਜਦਾ ਹੈ, ਇਹ ਨੋਟ ਕਰਨਾ ਕਿ ਇਸ ਦੀ ਪ੍ਰਾਪਤੀ ਦੀ ਲਾਗਤ 3 ਤੋਂ 4 ਤੋਂ ਬਦਲ ਗਈ ਹੈ.
ਜਿਵੇਂ ਕਿ ਤੁਸੀਂ ਵੇਖ ਸਕਦੇ ਹੋ, ਪ੍ਰੋਸੈਸਿੰਗ ਕਰਦੇ ਸਮੇਂ ਜਦੋਂ ਇਸ ਤੋਂ ਬਿਨਾਂ ਕੋਈ ਤੇਜ਼ ਅਤੇ ਸੌਖਾ ਹੋਵੇ. ਨੈਟਵਰਕ ਵਿੱਚ ਜਿੱਥੇ ਰੂਟਿੰਗ ਪ੍ਰੋਟੋਕੋਲ ਦੋਹਰਾ ਵਰਤਦਾ ਸੀ (ਖਾਸ ਤੌਰ 'ਤੇ, ਈਇਗਰਪ) ਵਿੱਚੋਂ ਇੱਕ, ਮੁੱਖ ਡਿਜ਼ਾਈਨ ਦੇ ਕਿਸੇ ਵੀ ਬੇਨਤੀ ਦੀ ਅਣਹਾਂਖੀ ਵਿੱਚ ਪੈਦਾ ਹੋਈਆਂ ਕਿਸੇ ਵੀ ਬੇਨਤੀਆਂ ਨੂੰ ਸੀਮਿਤ ਕਰਨਗੀਆਂ. ਬੇਨਤੀ ਖੇਤਰ ਮੁੱਖ ਨਿਰਣਾਇੰਗ ਕਾਰਕ ਹੈ ਕਿ ਡਬਲ ਐਲਗੋਰਿਦਮ ਕਿਵੇਂ ਤੇਜ਼ੀ ਨਾਲ ਪੂਰਾ ਹੋ ਗਿਆ ਹੈ ਅਤੇ ਇਸ ਲਈ, ਕਿੰਨੀ ਜਲਦੀ ਨੈਟਵਰਕ ਨੂੰ ਬਦਲਦਾ ਹੈ.
ਚਿੱਤਰ 10 ਮੁ with ਲੀ ਐਕਸ਼ਨਡ ਡਿ ual ਲ ਮਸ਼ੀਨ ਨੂੰ ਦਰਸਾਉਂਦਾ ਹੈ.
ਰਸਤੇ ਵਿੱਚ ਸ਼ਾਮਲ ਚੀਜ਼ਾਂ ਬਦਤਰ ਹੁੰਦੀਆਂ ਹਨ (ਰਸਤੇ ਦਾ ਵਿਗਾੜ) ਹੋ ਸਕਦਾ ਹੈ:
- ਜੁੜੇ ਚੈਨਲ ਜਾਂ ਗੁਆਂ neighbor ੀ ਦੀ ਅਸਫਲਤਾ
- ਇੱਕ ਉੱਚ ਮੀਟਰਕੀ ਦੇ ਨਾਲ ਇੱਕ ਰਸਤੇ ਲਈ ਅਪਡੇਟ ਪ੍ਰਾਪਤ ਕਰਨਾ
- ਮੌਜੂਦਾ ਉਤਰਾਧਿਕਾਰੀ ਤੋਂ ਪੁੱਛਗਿੱਛ ਪ੍ਰਾਪਤ ਕਰਨਾ
- ਕਿਸੇ ਗੁਆਂ neighbor ੀ ਤੋਂ ਨਵਾਂ ਰਸਤਾ ਪ੍ਰਾਪਤ ਕਰਨਾ
- ਇੱਕ ਨਵਾਂ ਸਰੂਬਰ ਪਾਇਆ ਗਿਆ ਸੀ, ਦੇ ਨਾਲ ਨਾਲ ਰਸਤੇ, ਜਿਸ ਦੁਆਰਾ ਇਹ ਪ੍ਰਾਪਤ ਕਰ ਸਕਦਾ ਹੈ
- ਜਦੋਂ ਰਸਤਾ ਵਿਗੜਦਾ ਹੈ ਤਾਂ ਗੁਆਂ neighbors ੀਆਂ ਨੂੰ ਭੇਜੀ ਗਈ ਸਾਰੀਆਂ ਬੇਨਤੀਆਂ ਪ੍ਰਾਪਤ ਕਰਨਾ
