《计算机网络》课程教学资源（参考文献）Interdomain Internet Routing

Copyright Hari Balakrishnan, 2001-2005, and Nick Feamster, 2005. All rights reserved Please do not redistribute without permission ECTURE 4 Interdomain Internet Routing he goal of this lecture is to explain how routing between different administrative do- mains works in the Internet. We discuss how Internet Service Providers(ISPs) change routing information(and packets)between each other, and how the way in which they buy service from and sell service to each other and their customers influences the technical research agenda of Internet routing in the real-world. we discuss the salient fea- tures of the Border Gateway Protocol, Version 4(BGP4), the current interdomain routing protocol in the Internet 4.1 Autonomous Systems An abstract, highly idealized view of the Internet is shown in Figure 4-1, where end-hosts hook up to routers, which hook up with other routers to form a nice connected graph of essentially"peer"routers that cooperate nicely using routing protocols that exchange shortest-path"or similar information and provide global connectivity. The same view posits that the graph induced by the routers and their links has a large amount of re- dundancy and the Internet's routing algorithms are designed to rapidly detect faults and problems in the routing substrate and route around them. Some would even posit that the same routing protocols today perform load-sensitive routing to dynamically shed load away from congested paths on to less-loaded path Unfortunately, while simple, this abstraction is actually quite misleading. TI of the Internet routing infrastructure is that the Internet service is provided by a large number of commercial enterprises, generally in competition with each other. Coopera tion, required for global connectivity, is generally at odds with the need to be a profitable commercial enterprise, which often occurs at the expense of ones competitors-the same people with whom one needs to cooperate. How this is achieved in practice(although there's lots of room for improvement), and how we might improve things, is an interest ing and revealing study of how good technical research can be shaped and challenged by commercial realities A second pass at developing a good picture of the Internet routing substrate is shown in Figure 4-2, which depicts a group of Internet Service Providers(ISPs)somehow cooper-

Copyright Hari Balakrishnan, 2001-2005, and Nick Feamster, 2005. All rights reserved. Please do not redistribute without permission. LECTURE 4 Interdomain Internet Routing The goal of this lecture is to explain how routing between different administrative do￾mains works in the Internet. We discuss how Internet Service Providers (ISPs) ex￾change routing information (and packets) between each other, and how the way in which they buy service from and sell service to each other and their customers influences the technical research agenda of Internet routing in the real-world. We discuss the salient fea￾tures of the Border Gateway Protocol, Version 4 (BGP4), the current interdomain routing protocol in the Internet. ! 4.1 Autonomous Systems An abstract, highly idealized view of the Internet is shown in Figure 4-1, where end-hosts hook up to routers, which hook up with other routers to form a nice connected graph of essentially “peer” routers that cooperate nicely using routing protocols that exchange “shortest-path” or similar information and provide global connectivity. The same view posits that the graph induced by the routers and their links has a large amount of re￾dundancy and the Internet’s routing algorithms are designed to rapidly detect faults and problems in the routing substrate and route around them. Some would even posit that the same routing protocols today perform load-sensitive routing to dynamically shed load away from congested paths on to less-loaded paths. Unfortunately, while simple, this abstraction is actually quite misleading. The real story of the Internet routing infrastructure is that the Internet service is provided by a large number of commercial enterprises, generally in competition with each other. Coopera￾tion, required for global connectivity, is generally at odds with the need to be a profitable commercial enterprise, which often occurs at the expense of one’s competitors—the same people with whom one needs to cooperate. How this is achieved in practice (although there’s lots of room for improvement), and how we might improve things, is an interest￾ing and revealing study of how good technical research can be shaped and challenged by commercial realities. A second pass at developing a good picture of the Internet routing substrate is shown in Figure 4-2, which depicts a group of Internet Service Providers (ISPs) somehow cooper- 1

LECTURE 4. INTER End-host structure Figure 4-1: This is a rather misleading abstraction of the Internet routing layer. g to provide global connectivity to end-customers. This picture is closer to the truth, but the main thing it's missing is that not all ISPs are created equal. Some are bigger and more"connected"than others, and still others have global reachability in their routing tables. There are names given to these"small, ""large, "and"really huge" ISPs: Tier-3 ISPs are ones that have a small number of usually localized (in geography )end-customers Tier-2 ISPs generally have regional scope(e. g, state-wide, region-wide, or non-US country wide), while Tier-1 ISPs, of which there are a handful, have global scope in the sense that ting tables actually have routes to all currently reachable Internet prefixes(i.e they have no default routes). This organization is shown in Figure 4-3. The current wide-area routing protocol, which exchanges reachability information about routeable IP-address prefixes between routers at the boundary between ISPs, is BGP(Bor der Gateway Protocol, Version 4)[13, 14]. More precisely, the wide-area routing architec ture is divided into autonomous systems(ASes)that exchange reachability information.An AS is owned and administered by a single commercial entity, and implements some set of policies in deciding how to route its packets to the rest of the Internet, and how to export its routes(its own, those of its customers, and other routes it may have learned from other ASes)to other ASes. Each As is identified by a unique 16-bit number A different routing protocol operates within each AS. These routing protocols are called Interior Gateway Protocols(IGPs), and include protocols like Routing Information Protocol (RIP)[8]. Open Shortest Paths First(OSPF)[11], Intermediate System-Intermediate System (IS-IS)[12], and E-IGRP. In contrast, interdomain protocols like BGP are also called EGPs (Exterior Gateway Protocols). Operationally, a key difference between EGPs like BGP and IGPs is that the former is concerned with providing reachability information and facilitating routing policy implementation in a scalable manner, whereas the latter are typically con- cerned with optimizing a path metric. Scalability is typically not a major concern in the design of IGPs(and all known IGPs don' t scale as well as BGP does The rest of this lecture is in two parts: first, we will look at inter-AS relationships(transit and peering); then, we will study some salient features of BGP. We dont have time to

2 LECTURE 4. INTERDOMAIN INTERNET ROUTING A B C D “Internet” End-hosts Routers connected in a fault-tolerant structure E Figure 4-1: This is a rather misleading abstraction of the Internet routing layer. ating to provide global connectivity to end-customers. This picture is closer to the truth, but the main thing it’s missing is that not all ISPs are created equal. Some are bigger and more “connected” than others, and still others have global reachability in their routing tables. There are names given to these “small,” “large,” and “really huge” ISPs: Tier-3 ISPs are ones that have a small number of usually localized (in geography) end-customers; Tier-2 ISPs generally have regional scope (e.g., state-wide, region-wide, or non-US country￾wide), while Tier-1 ISPs, of which there are a handful, have global scope in the sense that their routing tables actually have routes to all currently reachable Internet prefixes (i.e., they have no default routes). This organization is shown in Figure 4-3. The current wide-area routing protocol, which exchanges reachability information about routeable IP-address prefixes between routers at the boundary between ISPs, is BGP (Bor￾der Gateway Protocol, Version 4) [13, 14]. More precisely, the wide-area routing architec￾ture is divided into autonomous systems (ASes) that exchange reachability information. An AS is owned and administered by a single commercial entity, and implements some set of policies in deciding how to route its packets to the rest of the Internet, and how to export its routes (its own, those of its customers, and other routes it may have learned from other ASes) to other ASes. Each AS is identified by a unique 16-bit number. A different routing protocol operates within each AS. These routing protocols are called Interior Gateway Protocols (IGPs), and include protocols like Routing Information Protocol (RIP) [8]. Open Shortest Paths First (OSPF) [11], Intermediate System-Intermediate System (IS-IS) [12], and E-IGRP. In contrast, interdomain protocols like BGP are also called EGPs (Exterior Gateway Protocols). Operationally, a key difference between EGPs like BGP and IGPs is that the former is concerned with providing reachability information and facilitating routing policy implementation in a scalable manner, whereas the latter are typically con￾cerned with optimizing a path metric. Scalability is typically not a major concern in the design of IGPs (and all known IGPs don’t scale as well as BGP does). The rest of this lecture is in two parts: first, we will look at inter-AS relationships (transit and peering); then, we will study some salient features of BGP. We don’t have time to

SECTION 4.2. INTER-AS RELATIONSHIPS: TRANSIT AND PEERING ISP romers linked to routers in other ISPs) ISP Figure 4-2: The Internet is actually composed of many competing Internet Service Providers (IsPs)that co- operate to provide global connectivity. This picture suggests that all ISPs are"equal, " which isn't actually survey IGPs in this lecture, but you should be familiar with the more well-known ones like RIP and OSPF (or at least with distance-vector and link-state protocols). To learn more about IGPs if you're not familiar with them, read a standard networking textbook (e. 8, Peterson Davie, Kurose Ross, Tanenbaum) or a book on routing protocols(e.g Huitema) 4.2 Inter-As Relationships: Transit and peering The Internet is composed of many different types of ASes, from universities to corpora tions to regional Internet Service Providers(ISPs) to nationwide ISPs. Smaller ASes(e.g universities, corporations, etc. typically purchase Internet connectivity from ISPs. Smaller regional ISPs, in turn, purchase connectivity from larger ISPs with"backbone"networks Consider the picture shown in Figure 4-4. It shows an ISP, with AS number X, directly connected to a provider(from whom it buys Internet service) and a few customers( to whom it sells Internet service). In addition, the figure shows two other ISPs to whom it is directly connected, with whom X exchanges routing information via BGP. The different types of ASes lead to different types of business relationships between them, which in turn translate to different policies for exchanging and selecting routes There are two prevalent forms of As-As interconnection. The first form is provider-customer transit(aka"transit), wherein one ISP(the"provider" P in Figure 4-4)provides access to all (or most)destinations in its routing tables. Transit almost always is meaningful in an inter-AS relationship where financial settlement is involved; the provider charges its customers for Internet access, in return for forwarding packets on behalf of customers to destinations(and in the opposite direction in many cases). Another example of a transit relationship in Figure 4-4 is between X and its customers(the Cis) The second prevalent form is called peering. Here, two ASes(typically ISPs) provide

SECTION 4.2. INTER-AS RELATIONSHIPS: TRANSIT AND PEERING 3 “ISP” ISP network (some routers linked to routers in other ISP’s) ISP ISP ISP ISP End-hosts (ISP customers) Figure 4-2: The Internet is actually composed of many competing Internet Service Providers (ISPs) that co￾operate to provide global connectivity. This picture suggests that all ISPs are “equal,” which isn’t actually true. survey IGPs in this lecture, but you should be familiar with the more well-known ones like RIP and OSPF (or at least with distance-vector and link-state protocols). To learn more about IGPs if you’re not familiar with them, read a standard networking textbook (e.g., Peterson & Davie, Kurose & Ross, Tanenbaum) or a book on routing protocols (e.g., Huitema). ! 4.2 Inter-AS Relationships: Transit and Peering The Internet is composed of many different types of ASes, from universities to corpora￾tions to regional Internet Service Providers (ISPs) to nationwide ISPs. Smaller ASes (e.g., universities, corporations, etc.) typically purchase Internet connectivity from ISPs. Smaller regional ISPs, in turn, purchase connectivity from larger ISPs with “backbone” networks. Consider the picture shown in Figure 4-4. It shows an ISP, with AS number X, directly connected to a provider (from whom it buys Internet service) and a few customers (to whom it sells Internet service). In addition, the figure shows two other ISPs to whom it is directly connected, with whom X exchanges routing information via BGP. The different types of ASes lead to different types of business relationships between them, which in turn translate to different policies for exchanging and selecting routes. There are two prevalent forms of AS-AS interconnection. The first form is provider-customer transit (aka “transit”), wherein one ISP (the “provider” P in Figure 4-4) provides access to all (or most) destinations in its routing tables. Transit almost always is meaningful in an inter-AS relationship where financial settlement is involved; the provider charges its customers for Internet access, in return for forwarding packets on behalf of customers to destinations (and in the opposite direction in many cases). Another example of a transit relationship in Figure 4-4 is between X and its customers (the Cis). The second prevalent form is called peering. Here, two ASes (typically ISPs) provide

LECTURE 4. INTER End-hosts (ISP customers) Tier3 ISP (“ Local”) Tier-2 ISP Provider Tier-2 ISP Customer -Provider (“ Regional or CDefault-free”; Has global reachability info) nother)Tier-I ISP Tier 2 ISP Figure 4-3: A more accurate picture of the wide-area Internet routing infrastructure, with various types of ISPs defined by their respective reach. Tier-1 ISPs have"default-free"routing tables (i.e. they don' t have any default routes), and typically have global reachability information. There are a handful of these today (about five or so) mutual access to a subset of each others'routing tables. The subset of interest here is their own transit customers(and the ISPs own internal addresses). Like transit, peering is a business deal, but it may not involve financial settlement. While paid peering is common in some parts of the world, in many cases they are reciprocal agreements. As long as the traffic ratio between the concerned ASs is not highly asymmetric(e.g, 4: 1 is a commonly believed and quoted ratio), there's usually no financial settlement. Peering deals are almost always under non-disclosure and are confidential 4.2.1 Peering v. Transit a key point to note about peering relationships is that they are often between business competitors. The common reason for peering is the observation by each party that a non- trivial fraction of the packets emanating from each one is destined for the others direct transit customers. Of course, the best thing for each of the ISPs to try to do would be to wean away the others customers, but that may be hard to do. The next best thing, which would be in their mutual interest, would be to avoid paying transit costs to their respective providers, but instead set up a transit-free link between each other to forward packets for their direct customers. In addition, this approach has the advantage that this more direct path would lead to better end-to-end performance(in terms of latency, packet loss rate, and throughput)for their customers. It's also worth noticing that a Tier-1 ISP usually will find it essential to be involved in peering relationships with other ISPs(especially other Tier-1 ISPs)to obtain global routing information in a default-free manner. Balancing these potential benefits are some forces against peering. Transit relationships generate revenue; peering relationships usually don't. Peering relationships typically need

4 LECTURE 4. INTERDOMAIN INTERNET ROUTING Tier-1 ISP (“Default-free”; Has global reachability info) Tier-3 ISP (“Local”) Tier-2 ISP (“Regional or country-wide) Tier-2 ISP End-hosts (ISP customers) (Another) Tier-1 ISP Customer Provider Customer Provider Tier-2 ISP Figure 4-3: A more accurate picture of the wide-area Internet routing infrastructure, with various types of ISPs defined by their respective reach. Tier-1 ISPs have “default-free” routing tables (i.e., they don’t have any default routes), and typically have global reachability information. There are a handful of these today (about five or so). mutual access to a subset of each others’ routing tables. The subset of interest here is their own transit customers (and the ISPs own internal addresses). Like transit, peering is a business deal, but it may not involve financial settlement. While paid peering is common in some parts of the world, in many cases they are reciprocal agreements. As long as the traffic ratio between the concerned ASs is not highly asymmetric (e.g., 4:1 is a commonly believed and quoted ratio), there’s usually no financial settlement. Peering deals are almost always under non-disclosure and are confidential. ! 4.2.1 Peering v. Transit A key point to note about peering relationships is that they are often between business competitors. The common reason for peering is the observation by each party that a non￾trivial fraction of the packets emanating from each one is destined for the other’s direct transit customers. Of course, the best thing for each of the ISPs to try to do would be to wean away the other’s customers, but that may be hard to do. The next best thing, which would be in their mutual interest, would be to avoid paying transit costs to their respective providers, but instead set up a transit-free link between each other to forward packets for their direct customers. In addition, this approach has the advantage that this more direct path would lead to better end-to-end performance (in terms of latency, packet loss rate, and throughput) for their customers. It’s also worth noticing that a Tier-1 ISP usually will find it essential to be involved in peering relationships with other ISPs (especially other Tier-1 ISPs) to obtain global routing information in a default-free manner. Balancing these potential benefits are some forces against peering. Transit relationships generate revenue; peering relationships usually don’t. Peering relationships typically need

SECTION 4.2. INTER-AS RELATIONSHIPS: TRANSIT AND PEERING 5 Transit(SSS) Peering Transit(SSS) tTransit(S) Transit(sS Transit(5s) Z's cusTom Y's customers Figure 4-4: Inter-AS relationships; transit and peer to be renegotiated often, and asymmetric traffic ratios require care to handle in a way thats mutually satisfactory. Above all, these relationships are often between competitors vying for the same customer base the discussion so far, we have implicitly used an important property of current in terdomain routing: A route advertisement from B to A for a destination prefix is an agreement by b that it will forward packets sent via a destined for any destination in the prefix. This(im plicit)agreement implies that one way to think about Internet economics is to view iSPs as charging customers for entries in their routing tables. Of course, the data rate of the interconnection is also crucial, and is the major determinant of an ISP's pricing policy 4.2.2 Exporting Routes: Route Filtering Each As(ISP)needs to make decisions on which routes to export to its neighboring ISPs using BGP. The reason why export policies are important is that no iSP wants to act as transit for packets that it isn' t somehow making money on. Because packets flow in the opposite direction to the(best) route advertisement for any destination, an As should ad vertise routes to neighbors with care Transit customer routes. To an ISP, its customer routes are likely the most important, because the view it provides to its customers is the sense that all potential senders in the Internet can reach them. It is in the isP's best interest to advertise routes to its transit customers to as many other connected ASes as possible. The more traffic that an ISp car- ries on behalf of a customer, the"fatter"the pipe that the customer would need implying igher revenue for the ISP. Hence, if a destination were advertised from multiple neigh ors, an ISP should prefer the advertisement made from a customer over all other choices (in particular, over peers and transit providers

SECTION 4.2. INTER-AS RELATIONSHIPS: TRANSIT AND PEERING 5 C1 X Z ISP Y C2 C3 Peering Peering Transit ($$$) Transit ($$) Transit ($) Transit ($$) Z’s customers Y’s customers P C’P Transit ($$) Peering Transit ($$$) ISP Figure 4-4: Inter-AS relationships; transit and peering. to be renegotiated often, and asymmetric traffic ratios require care to handle in a way that’s mutually satisfactory. Above all, these relationships are often between competitors vying for the same customer base. In the discussion so far, we have implicitly used an important property of current in￾terdomain routing: A route advertisement from B to A for a destination prefix is an agreement by B that it will forward packets sent via A destined for any destination in the prefix. This (im￾plicit) agreement implies that one way to think about Internet economics is to view ISPs as charging customers for entries in their routing tables. Of course, the data rate of the interconnection is also crucial, and is the major determinant of an ISP’s pricing policy. ! 4.2.2 Exporting Routes: Route Filtering Each AS (ISP) needs to make decisions on which routes to export to its neighboring ISPs using BGP. The reason why export policies are important is that no ISP wants to act as transit for packets that it isn’t somehow making money on. Because packets flow in the opposite direction to the (best) route advertisement for any destination, an AS should ad￾vertise routes to neighbors with care. Transit customer routes. To an ISP, its customer routes are likely the most important, because the view it provides to its customers is the sense that all potential senders in the Internet can reach them. It is in the ISP’s best interest to advertise routes to its transit customers to as many other connected ASes as possible. The more traffic that an ISP car￾ries on behalf of a customer, the “fatter” the pipe that the customer would need, implying higher revenue for the ISP. Hence, if a destination were advertised from multiple neigh￾bors, an ISP should prefer the advertisement made from a customer over all other choices (in particular, over peers and transit providers)