Algoritmo di selezione del miglior percorso BGP

Introduzione

In questo documento viene descritto il funzionamento dell'algoritmo del protocollo Border Gateway Protocol (BGP) con cui viene scelto il percorso migliore. 

Premesse

I router BGP di norma ricevono più percorsi alla stessa destinazione. L'algoritmo del percorso BGP migliore stabilisce il percorso migliore da inserire nella tabella di routing IP e da utilizzare per l'inoltro del traffico.

Perché i router ignorano i percorsi

Si supponga che tutti i percorsi ricevuti da un router con un particolare prefisso siano organizzati in un elenco. L'elenco è simile all'output del comando show ip bgp long-prefix. Alcuni percorsi non sono ritenuti idonei per diventare percorsi migliori. Nell'output del comando show ip bgp longer-prefixes, tali percorsi in genere non hanno il contrassegno "valido". I percorsi vengono ignorati nei seguenti casi:

• Percorsi contrassegnati come not synchronized (non sincronizzato) nell'output del comando show ip bgp longer-prefixes.

  Se la sincronizzazione BGP è abilitata, affinché un percorso BGP interno (iBGP) sia considerato valido, il suo prefisso deve essere presente nella tabella di routing IP. In Cisco IOS^{® Software, la sincronizzazione BGP è abilitata per impostazione predefinita.} Se la route corrispondente viene appresa da un router adiacente OSPF (Open Shortest Path First), il relativo ID router OSPF deve corrispondere all'ID router BGP del router adiacente iBGP. La maggior parte degli utenti preferisce disabilitare la sincronizzazione utilizzando il sottocomando BGP no synchronization.

  Nota: La sincronizzazione è disabilitata per impostazione predefinita nel software Cisco IOS® versione 12.2(8)T e successive.

• Percorsi che non possono accedere al NEXT_HOP.

  Accertarsi che sia presente una route IGP (Interior Gateway Protocol) diretta al NEXT_HOP e associata al percorso.

• Percorsi provenienti da un router BGP esterno (eBGP) vicino in caso il sistema autonomo (AS) locale sia presente in AS_PATH. 

  Questi percorsi vengono rifiutati durante l'ingresso nel router e non vengono neanche installati nel database di informazioni di routing BGP (RIB). Lo stesso vale per qualsiasi percorso rifiutato da una policy di routing implementata tramite accesso, prefisso, AS_PATH o elenchi di comunità, a meno che non sia stato configurato il comando neighbor soft-reconfiguration inbound per il router vicino.

• Il comando bgp enforce-first-as è stato abilitato e nel messaggio UPDATE l'AS del nodo vicino non risulta essere il primo identificativo AS nella sequenza AS_SEQUENCE.

  In questo caso, il router invia una notifica e chiude la sessione.

• Percorsi contrassegnati come (solo ricevuti) nell'show ip bgp longer-prefixesoutput

  I percorsi sono stati rifiutati dalla policy. Tuttavia, il router ha archiviato i percorsi perché è stata eseguita la configurazione soft-reconfiguration inbound per il router adiacente che invia il percorso.

Logica dell'algoritmo del percorso migliore

Il protocollo BGP designa come percorso migliore il primo percorso valido. Quindi, lo confronta con il percorso successivo nell'elenco, scorrendo fino alla fine l'elenco dei percorsi validi. Nell'elenco vengono indicate le regole da utilizzare per determinare il percorso migliore:

1. Preferire il percorso con l'attributo WEIGHT più alto. 

   Nota: WEIGHT è un parametro Cisco ed è specifico del router su cui è configurato.

2. Preferire il percorso con l'attributo LOCAL_PREF più alto.

   Nota: Per un percorso senza LOCAL_PREF, il valore è impostato con il comando bgp default local-priority oppure è impostato sul valore predefinito 100.

3. Preferire il percorso originato localmente con il sottocomando BGP network o aggregate o tramite una ridistribuzione da IGP.

   I percorsi locali originati dai comandi network o redistribute sono preferiti rispetto agli aggregati locali originati dal comando aggregate-address.

   Nota: tenere presente quanto segue:
   
   - Se AIGP è configurato E il comando bgp bestpath aigp ignore non è configurato, viene presa in considerazione la metrica AIGP. Per ulteriori informazioni, vedere Configurazione dell'attributo AIGP Metric per BGP.

4. Preferire il percorso con l'attributo AS_PATH più breve.

   Nota: tenere presente quanto segue:
   - Questo passaggio può essere ignorato se è stato configurato il comando bgp bestpath as-path ignore.
   - Un attributo AS_SET vale sempre 1, a prescindere dal numero di AS impostati.
   - Gli attributi AS_CONFED_SEQUENCE e AS_CONFED_SET non sono inclusi nella lunghezza di AS_PATH.

5. Preferire il percorso con il tipo di origine più basso.

   Nota: il protocollo IGP è più basso del protocollo EGP (Exterior Gateway Protocol), il protocollo EGP è più basso di INCOMPLETE.

6. Preferire il percorso con il valore più basso per l'attrbuto multi-exit discriminator (MED).

   Nota: tenere presente quanto segue:
   
   - Questo confronto viene effettuato solo se il primo sistema autonomo (AS) (vicino) è lo stesso nei due percorsi. Qualsiasi AS secondario della confederazione viene ignorato.
   In altre parole, i MED vengono confrontati solo se il primo AS nella sequenza AS_SEQUENCE è uguale per più percorsi. Qualsiasi AS_CONFED_SEQUENCE che precede viene ignorata.
   
   - Se il comando bgp always-compare-med è stato abilitato, vengono confrontati i MED di tutti i percorsi.
   Disabilitare questa opzione sull'intero AS. In caso contrario, potrebbero verificarsi dei loop di routing.
   
   - Se il comando bgp bestpath med-confed è stato abilitato, vengono confrontati i MED di tutti i percorsi composti solo da AS_CONFED_SEQUENCE.
   Questi percorsi sono originati all'interno della confederazione locale.
   
   - I MED dei percorsi ricevuti da un router vicino il cui MED è 4.294.967.295 vengono modificati prima di essere inseriti nella tabella BGP. Il MED diventa 4.294.967.294.
   
   - I MED dei percorsi ricevuti da un router vicino il cui MED è 4.294.967.295 vengono considerati validi e inseriti nella tabella BGP con effetto sui codici risolti dell'ID bug Cisco CSCef34800.
   
   - Ai percorsi che ne sono privi, viene assegnato un MED pari a 0, a meno che non sia stato abilitato il comando bgp bestpath med missing-as-worst.
   Se l'opzione bgp bestpath med missing-as-worst è abilitata, ai percorsi viene assegnato un MED di 4.294.967.294.
   Se l'opzione bgp bestpath med missing-as-worst è abilitata, ai percorsi viene assegnato un MED di 4,294,967,295 con effetto sui codici corretti per l'ID bug Cisco CSCef34800.
   
   - Anche il comando bgp deterministic-med può influire su questo passaggio.
   Per una dimostrazione, fare riferimento a Uso dell'attributo Multi-Exit Discriminator da parte dei router BGP per la scelta del percorso migliore.

7. Preferire i percorsi eBGP anziché i percorsi iBGP.

   Se è selezionato bestpath, andare al passo 9 (multipath).

   Nota: i percorsi che contengono gli attributi AS_CONFED_SEQUENCE e AS_CONFED_SET sono interni alla confederazione. Pertanto, vengono trattati come percorsi interni. Non vi è alcuna distinzione tra confederazione esterna e confederazione interna.

8. Preferire il percorso al successivo hop BGP con la metrica IGP più bassa.

   Proseguire, anche se bestpath è già selezionato.

9. Decidere se inserire percorsi multipli nella tabella di routing per la funzionalità BGP Multipath.

   Proseguire, anche se bestpath non è ancora selezionato.

10. Quando entrambi i percorsi sono esterni, scegliere il percorso ricevuto per primo (il più vecchio).

    Questo passaggio riduce al minimo l'instabilità dell'annuncio della route; infatti il vecchio percorso non viene sostituito dal nuovo, anche se quest'ultimo costituirebbe la route preferita in base ai criteri decisionali discussi più avanti (passaggi 11, 12 e 13).

    Ignorare questo passaggio se una di queste affermazioni è vera:

    • Il comando bgp best path compare-routerid è stato abilitato.

      Nota: Il software Cisco IOS® versioni 12.0.11S, 12.0.11SC, 12.0.11S3, 12.1.3, 12.1.3AA, 12.1.3.T e 12.1.3.E ha introdotto questo comando.

    • Poiché le route sono state ricevute dallo stesso router, l'ID del router è lo stesso per più percorsi.

    • Al momento non esiste un percorso migliore.

      Il percorso considerato al momento migliore può andare perduto se si perde il collegamento al router che lo offre.

11. Preferire la route che proviene dal router BGP con l'ID router più basso.

    L'ID router è l'indirizzo IP più alto del router, con preferenza data agli indirizzi di loopback. Inoltre, è possibile usare il comando bgp router-id per impostare manualmente l'ID del router.

    Nota: se un percorso contiene gli attributi Route Reflector (RR), l'ID del nodo di origine viene sostituito con l'ID del router nel processo di scelta del percorso.

12. Se l'ID del nodo di origine o l'ID del router coincidono per più percorsi, scegliere il percorso con l'elenco cluster più corto.

    Questo elenco è presente solo negli ambienti BGP RR. Consente ai client di eseguire il peering con gli RR o i client di altri cluster. In questo scenario, il client deve conoscere l'attributo BGP specifico di RR.

13. Preferire il percorso proveniente dal router vicino con l'indirizzo più basso.

    Questo indirizzo è l'indirizzo IP utilizzato nella neighbor configurazione BGP. L'indirizzo corrisponde al peer remoto usato nella connessione TCP al router locale.

Esempio: Scelta del percorso BGP migliore

Nell'esempio, sono disponibili 9 percorsi per la rete 10.30.116.0/23. Il comando show ip bgp network visualizza le voci nella tabella di routing BGP per la rete in questione.

Router R1#show ip bgp vpnv4 rd 1100:1001 10.30.116.0/23
BGP routing table entry for 1100:1001:10.30.116.0/23, version 26765275
Paths: (9 available, best #6, no table)
  Advertised to update-groups:
     1          2          3         
  (65001 64955 65003) 65089, (Received from a RR-client)
    172.16.254.226 (metric 20645) from 172.16.224.236 (172.16.224.236)
      Origin IGP, metric 0, localpref 100, valid, confed-internal
      Extended Community: RT:1100:1001
      mpls labels in/out nolabel/362
  (65008 64955 65003) 65089
    172.16.254.226 (metric 20645) from 10.131.123.71 (10.131.123.71)
      Origin IGP, metric 0, localpref 100, valid, confed-external
      Extended Community: RT:1100:1001
      mpls labels in/out nolabel/362
  (65001 64955 65003) 65089
    172.16.254.226 (metric 20645) from 172.16.216.253 (172.16.216.253)
      Origin IGP, metric 0, localpref 100, valid, confed-external
      Extended Community: RT:1100:1001
      mpls labels in/out nolabel/362
  (65001 64955 65003) 65089
    172.16.254.226 (metric 20645) from 172.16.216.252 (172.16.216.252)
      Origin IGP, metric 0, localpref 100, valid, confed-external
      Extended Community: RT:1100:1001
      mpls labels in/out nolabel/362
  (64955 65003) 65089
    172.16.254.226 (metric 20645) from 10.77.255.57 (10.77.255.57)
      Origin IGP, metric 0, localpref 100, valid, confed-external
      Extended Community: RT:1100:1001
      mpls labels in/out nolabel/362
  (64955 65003) 65089
    172.16.254.226 (metric 20645) from 10.57.255.11 (10.57.255.11)
      Origin IGP, metric 0, localpref 100, valid, confed-external, best
      Extended Community: RT:1100:1001
      mpls labels in/out nolabel/362

!--- BGP selects this as the Best Path on comparing 
!--- with all the other routes and selected based on lower router ID.

  (64955 65003) 65089
    172.16.254.226 (metric 20645) from 172.16.224.253 (172.16.224.253)
      Origin IGP, metric 0, localpref 100, valid, confed-internal
      Extended Community: RT:1100:1001
      mpls labels in/out nolabel/362
  (65003) 65089
    172.16.254.226 (metric 20645) from 172.16.254.234 (172.16.254.234)
      Origin IGP, metric 0, localpref 100, valid, confed-external
      Extended Community: RT:1100:1001
      mpls labels in/out nolabel/362
  65089, (Received from a RR-client)
    172.16.228.226 (metric 20645) from 172.16.228.226 (172.16.228.226)
      Origin IGP, metric 0, localpref 100, valid, confed-internal
      Extended Community: RT:1100:1001
      mpls labels in/out nolabel/278

BGP seleziona il percorso migliore tra questi 9 percorsi prendendo in considerazione i vari attributi spiegati in questo documento. Nell'output mostrato di seguito, BGP confronta i percorsi disponibili e seleziona il percorso 6 come miglior percorso in base all'ID del router inferiore.

Comparing path 1 with path 2:
	Both paths have reachable next hops
	Both paths have a WEIGHT of 0
	Both paths have a LOCAL_PREF of 100
	Both paths are learned
	Both paths have AS_PATH length 1
	Both paths are of origin IGP
	The paths have different neighbor AS's so ignoring MED
	Both paths are internal
	  (no distinction is made between confed-internal and confed-external)
	Both paths have an IGP metric to the NEXT_HOP of 20645
Path 2 is better than path 1 because it has a lower Router-ID.

Comparing path 2 with path 3:
	Both paths have reachable next hops
	Both paths have a WEIGHT of 0
	Both paths have a LOCAL_PREF of 100
	Both paths are learned
	Both paths have AS_PATH length 1
	Both paths are of origin IGP
	Both paths have the same neighbor AS, 65089, so comparing MED.
	Both paths have a MED of 0
	Both paths are confed-external
	Both paths have an IGP metric to the NEXT_HOP of 20645
Path 2 is better than path 3 because it has a lower Router-ID.

Comparing path 2 with path 4:
	Both paths have reachable next hops
	Both paths have a WEIGHT of 0
	Both paths have a LOCAL_PREF of 100
	Both paths are learned
	Both paths have AS_PATH length 1
	Both paths are of origin IGP
	Both paths have the same neighbor AS, 65089, so comparing MED.
	Both paths have a MED of 0
	Both paths are confed-external
	Both paths have an IGP metric to the NEXT_HOP of 20645
Path 2 is better than path 4 because it has a lower Router-ID.

Comparing path 2 with path 5:
	Both paths have reachable next hops
	Both paths have a WEIGHT of 0
	Both paths have a LOCAL_PREF of 100
	Both paths are learned
	Both paths have AS_PATH length 1
	Both paths are of origin IGP
	Both paths have the same neighbor AS, 65089, so comparing MED.
	Both paths have a MED of 0
	Both paths are confed-external
	Both paths have an IGP metric to the NEXT_HOP of 20645
Path 5 is better than path 2 because it has a lower Router-ID.

Comparing path 5 with path 6:
	Both paths have reachable next hops
	Both paths have a WEIGHT of 0
	Both paths have a LOCAL_PREF of 100
	Both paths are learned
	Both paths have AS_PATH length 1
	Both paths are of origin IGP
	Both paths have the same neighbor AS, 65089, so comparing MED.
	Both paths have a MED of 0
	Both paths are confed-external
	Both paths have an IGP metric to the NEXT_HOP of 20645
Path 6 is better than path 5 because it has a lower Router-ID.

Comparing path 6 with path 7:
	Both paths have reachable next hops
	Both paths have a WEIGHT of 0
	Both paths have a LOCAL_PREF of 100
	Both paths are learned
	Both paths have AS_PATH length 1
	Both paths are of origin IGP
	Both paths have the same neighbor AS, 65089, so comparing MED.
	Both paths have a MED of 0
	Both paths are internal
	  (no distinction is made between confed-internal and confed-external)
	Both paths have an IGP metric to the NEXT_HOP of 20645
Path 6 is better than path 7 because it has a lower Router-ID.

Comparing path 6 with path 8:
	Both paths have reachable next hops
	Both paths have a WEIGHT of 0
	Both paths have a LOCAL_PREF of 100
	Both paths are learned
	Both paths have AS_PATH length 1
	Both paths are of origin IGP
	Both paths have the same neighbor AS, 65089, so comparing MED.
	Both paths have a MED of 0
	Both paths are confed-external
	Both paths have an IGP metric to the NEXT_HOP of 20645
Path 6 is better than path 8 because it has a lower Router-ID.

Comparing path 6 with path 9:
	Both paths have reachable next hops
	Both paths have a WEIGHT of 0
	Both paths have a LOCAL_PREF of 100
	Both paths are learned
	Both paths have AS_PATH length 1
	Both paths are of origin IGP
	The paths have different neighbor AS's so ignoring MED
	Both paths are internal
	  (no distinction is made between confed-internal and confed-external)
	Both paths have an IGP metric to the NEXT_HOP of 20645
Path 6 is better than path 9 because it has a lower Router-ID.
The best path is #6

Personalizzazione del processo di scelta del percorso

L'attributo della comunità estesa, chiamato BGP Cost Community, permette di personalizzare il processo di scelta del percorso migliore. All'algoritmo descritto nella sezione Logica dell'algoritmo del percorso migliore, viene aggiunto un ulteriore passaggio, ossia il confronto delle comunità di costi. Nell'algoritmo, questo passaggio viene dopo il passaggio richiesto per il punto di inserimento. Viene scelto il percorso con i costi più bassi. 

Nota: tenere presente quanto segue:

- Se è stato usato il comando bgp bestpath cost-community ignore, questo passaggio viene ignorato.

- La clausola per impostare la comunità di costi viene configurata con un ID di comunità (0 – 255) e un valore costi (0 – 4.294.967.295). Il valore costi determina il percorso da scegliere. Viene preferito il percorso con il valore costi più basso. Ai percorsi che non sono configurati in modo specifico con il valore del numero di costo viene assegnato un valore predefinito del numero di costo pari a 2.147.483.647. Questo valore rappresenta il punto centrale compreso tra 0 e 4.294.967.295. Questi percorsi vengono quindi valutati in base al miglior processo di selezione dei percorsi. Se due percorsi hanno lo stesso valore costi, il percorso scelto sarà quello con l'ID di comunità più basso. Se i percorsi hanno comunità di costi pre-bestpath diverse, viene scelto il percorso con la comunità di costi pre-bestpath più bassa.

- ABSOLUTE_VALUE è considerato il primo passo per determinare il grado di preferenza di un percorso. Ad esempio, quando si ridistribuisce EIGRP su una rete VPNv4 BGP, l'attributo ABSOLUTE_VALUE viene usato per la comunità di costi. Dopo aver confrontato la distanza interna (IGP) al successivo hop, viene preso in considerazione l'attributo IGB_Cost. Ciò significa che le comunità di costi con punto di inserimento IGP_COST vengono prese in considerazione dopo il passaggio 8 dell'algorimento descritto nella sezione Logica dell'algoritmo del percorso migliore.

BGP Multipath

La funzionalità BGP Multipath permette di inserire nella tabella di routing IP più percorsi BGP con medesima destinazione. Questi percorsi sono inseriti nella tabella insieme al percorso migliore per la ripartizione del carico. BGP Multipath non influisce sulla scelta del percorso migliore. Ad esempio, un router continua a designare uno dei percorsi come miglior percorso, in base all'algoritmo, e annuncia questo miglior percorso ai propri vicini.

Di seguito sono riportate le caratteristiche della funzionalità BGP Multipath:

• eBGP Multipath - maximum-paths n

• iBGP Multipath - maximum-paths ibgp n

• eiBGP Multipath - maximum-paths eibgp

Per poter applicare tale funzionalità, i percorsi con la stessa destinazione devono essere avere le stesse caratteristiche del percorso migliore:

• Peso

• Preferenza locale

• Lunghezza AS-PATH

• Origine

• MED

• Una di queste caratteristiche:

  • AS vicino o AS secondario (prima che venga aggiunta la funzione eiBGP Multipath)

  • AS-PATH (dopo che è stata aggiunta la funzione eiBGP Multipath)

Per alcune funzionalità BGP Multipath, i percorsi devono avere ulteriori requisiti.

Di seguito sono elencati i requisiti aggiuntivi richiesti per eBGP Multipath:

• Il percorso deve essere appreso da un router adiacente esterno o confederazione-esterno (eBGP).

• La metrica IGP per l'hop successivo BGP deve essere uguale alla metrica IGP del miglior percorso.

Di seguito sono elencati i requisiti aggiuntivi richiesti per iBGP Multipath:

• Il percorso deve essere appreso da un sistema adiacente interno (iBGP).

• La metrica IGP per l'hop successivo BGP deve essere uguale alla metrica IGP del miglior percorso, a meno che il router non sia configurato per percorsi multipli iBGP a costi diversi.

Il protocollo BGP inserisce fino a n percorsi ricevuti recentemente dai candidati al multipath nella tabella di routing IP. Il valore massimo di n è attualmente 6. Il valore predefinito, quando multipath è disabilitato, è 1.

Per un bilanciamento del carico quando i costi sono diversi, è possibile usare anche la larghezza di banda del collegamento BGP. 

Nota: il next-hop-self equivalente viene eseguito sul percorso migliore scelto tra i multipath eBGP prima di essere inoltrato ai peer interni.

Informazioni correlate

• Risoluzione dei problemi BGP
• Uso dell'attributo Multi-Exit Discriminator da parte dei router BGP per la scelta del percorso migliore
• Configurazione di BGP
• Pagina di supporto BGP
• Documentazione e supporto tecnico – Cisco Systems