Transcript PPT
Global Internet Part II Neil Tang 11/07/2008 CS440 Computer Networks 1 Overview Scalability Issues CIDR Autonomous System (AS) Inter-Domain Routing Routing Area CS440 Computer Networks 2 Scalability Issues Scalability of Routing: The number of network addresses carried around by the protocol messages and stored in the routing table needs to be minimized. Address Utilization: The limited IP address space needs to be used efficiently. CS440 Computer Networks 3 Classless Inter-Domain Routing (CIDR) The subnetting can not completely solve the scaling problem. For example, suppose there are 16 networks, each of which has 255 hosts. CIDR is a technique proposed to reduce routing table sizes by aggregating routes if the above situation happens. CS440 Computer Networks 4 Classless Inter-Domain Routing (CIDR) Internet will include a large number of class C networks. Based on CIDR, a set of closely located class C networks will be assigned a set of continuous addresses. E.g., 192.4.16-192.4.31 share a common 20bit prefix 11000000 00000100 0001. A routing message or a routing table usually include a tuple composed of such a virtual network addresses and a mask which indicates how many bits in the network prefix. A routing table may include “overlapping” entries. E.g., an entry corresponds to “171.69.0.0/16 ” and another entry corresponds to “171.69.10.0/24”. In this case, the packet will be forwarded based on the entry providing longest match. CS440 Computer Networks 5 Interdomain Routing Internet is organized as Autonomous Systems (AS, a.k.a routing domain), each of which is under control of an administrative entity. Intradomain routing protocols deal with routing between routers in a single domain, e.g., RIP, OSPF. Interdomain routing protocols deal with routing between autonomous systems, e.g., BGP. CS440 Computer Networks 6 Autonomous System Stub AS: An AS has only a single connection to one other AS., e.g., small corporation. Multihomed AS: An AS has connections to more than one other AS but refuses to carry transit (relay) traffic, e.g., large corporation. Transit AS: An AS has connections to more than one other AS and is designed to carry local and transit traffic, e.g., backbone provider. Large corporation “Consumer”ISP Peering point Backbone service provider “Consumer”ISP Large corporation Peering point “Consumer”ISP Small corporation CS440 Computer Networks 7 Border Gateway Protocol (BGP) The administrator of each AS picks at least one router to be the BGP speaker. It will establish sessions with other BGP speakers to exchange reachability information. In addition to a BGP speaker, there are one or more border gateways which are used to forward packets between ASs. CS440 Computer Networks 8 Border Gateway Protocol (BGP) BGP speakers advertise the complete path as an enumerated list of ASs to reach a particular network. For example, the BGP speaker AS1 advertises the networks 128.96, 192.4.153, 192.4.32 and 192.4.3 can be reached along the path (AS1, AS2) Customer P (AS 4) 128.96 192.4.153 Customer Q (AS 5) 192.4.32 192.4.3 Customer R (AS 6) 192.12.69 Customer S (AS 7) 192.4.54 192.4.23 Regional provider A (AS 2) Backbone netw ork (AS 1) Regional provider B (AS 3) CS440 Computer Networks 9 Border Gateway Protocol (BGP) BGP can use different routing policies to choose “good” paths. E.g., policies could be “Use the path that crosses the fewest number of ASs” or “Use AS x in preference to AS y”. The 16-bit AS ID is assigned by a central authority to guarantee uniqueness. The negative advertisement message known as withdrawn route is used to notify the link/node failures. CS440 Computer Networks 10 Inter/Intra-Domain Routing The complexity of interdomain routing is on the order of the number of ASs, and the complexity of intradomain routing is on the order of the number of networks in a single AS. A packet destined for a network outside the AS the source belongs to will be forwarded to a border gateway. If an AS is connected to more than one other ASs through multiple border gateways, a protocol called iBGP is used to redistribute the reachability information and enable the routers in an AS to learn the best border gateway for a particular destination network. CS440 Computer Networks 11 Routing Area A routing domain can be further divided to multiple routing areas. There is a special routing area called backbone area which is used to connect other non-backbone areas. A router in both a backbone area and a non-backbone area is called an Area Border Router (ABR) CS440 Computer Networks 12 Routing in Multiple Areas Routing advertisement information from non-ABR routers will never leave the area it is originated. Area 3 Area 1 Area 0 R9 An ABR advertises the routing information it learned from a routing area, say Area X to routers in the other areas such as they think all routers in Area X are directly connected with R1. CS440 Computer Networks R7 R8 R3 R1 R4 R2 Area 2 R6 R5 13 Optimality and Scalability Strength: Scalability is improved because the routing information which needs to be advertised and maintained, is dramatically reduced. Weakness: All packets need to go through ABRs, which may not be the optimal solution, i.e, two routers in different areas may be able to directly communicate with each other via a low-cost path not including an ABR. CS440 Computer Networks 14