Routing Algorithms
This week I learned about how routers find the correct path to send packets across the internet. Two types of routing algorithms are the link-state algorithm (LS) and the distance vector algorithm (DV). The LS algorithm uses Dijkstra's algorithm to find the least-cost path from source to destination. Costs are determined by the network administrator and can represent anything, such as distance, speed, or monetary cost. This algorithm is considered centralized because it requires global state information, or information about all links on the network. The DV algorithm, in contrast, is decentralized and does not use Dikjstra's algorithm. Routers using DV only have link-state information about their directly attached neighbors (and any information that their neighbors share). Nodes provide their neighbors with least-cost estimates from themselves to all other nodes that they know about. However, the shortest path is not always available. Policy issues can prevent forwarding of traffic from one organization to another. For example, one ISP may not want traffic getting a "free ride" through its network if neither the source nor destination addresses are customers.
It is up to network administrators to decide what routing algorithm to use. A network under the control of the same administration is called an autonomous system (AS). All autonomous systems on the internet run the border gateway protocol (BGP) for inter-AS communication. BGP is also often used to implement the IP-anycast service, which is commonly used for DNS Servers. Since DNS servers have duplicate content, network administrators can assign the same IP address to all of them. BGP routers select the best route to the IP address, which ends up being the closest (cheapest) server. Although CDNs also have duplicate-content servers, they tend not to use IP-anycast because BGP routing changes can result in different packets of the same TCP connection arriving at different versions of the server.
No comments:
Post a Comment