BGP and How the Internet works in the real world
Each ISP would have ~[公式] routers. Companies also put servers within IXPs, (though IXPs at the beginning were there for housing routers)
BGP: does not use Bellman-Ford or Dijkstra
Each BGP router advertise routes to their neighbors {a prefix + a list of AS’s to reach that a prefix through this router}
Each BGP router selects one or more paths of AS’s based on its own preference (by local policies chosen by the AS administrator)
Loops can be detected (duplicate AS in the path)
Why path in BGP?
A router may dislike a certain AS (e.g. security reason, geo-political issue, etc.)
There is a “trust” relationship between an end-host and the border gateway router that host connects to. Therefore,it is hard to detect lies about the AS paths since BGP protocol is based on a mutual trust between two connected border gateway routers, (although there exist algorithms/techniques to verify whether the path being advertised is valid).
BGP details
BGP neighbors establish a TCP connection, and send a “keep alive” message every 60 seconds
Also called “path vector” algorithm
Commercial Internet: customer-provider relationship
Customers pay providers for carrying packets, but how should providers charge each other?
Stub AS – transit AS — transit AS — transit AS — stub AS: who pay the center transit AS? There were agreements and settlements between ISPs for dealing these situations (which would make them “peers”), and the center transit AS only carries the traffic if such settlements exist (i.e. if they are “peers”).
But this agreement situation needs to stop at a “top-level”, i.e., “Tier-1” providers. “Tier 1” network are peers with all other “Tier 1” network.
Tier 1 ISP has access to the entire Internet Region. Each Internet Region has its own Tier 1 ISPs, and an ISP only gets promoted to “Tier 1” if it is big enough (carries large enough traffic, which means the ISP has invested a lot in its infrastructure). And Tier 1 ISP does not charge each other (since they are of similar large size).
For non Tier 1 ISPs, if an advertised path goes through a non-peer AS, it would not select the path, but would select the path that goes to “Tier 1”.
Multicast: single-source, multi-destination
A portion of IP v4 address is reserved for Group ID. Sending packets to such IP v4 address would send the packet to each members of the group.
For broadcasting from a source, the paths form a spanning tree rooted at the source, and therefore by reversing the routing table for the source as the destination, you get the required spanning tree. This is called Reverse Path Broadcasting.
RPB + pruning gives RPF