---[ Phrack Magazine Volume 8, Issue 53 July 8, 1998, article 05 of 15 -------------------------[ Introduction and Overview of Internet Routing --------[ krnl ----[ Routing Overview: The process of routing can be quickly summarized as a node finding the path to every possible destination. Routing is present in everything from layer 1 (the physical layer) on up. The routing that most people are familiar with, however, occurs at layer 3 (the network layer) and as such, we will only reference layer 3 (and more specifically) Internet Protocol (IP) routing in this document. Protocols for exchange of routing information connect multiple routers around the world to provide them with a common view of the network through their heterogeneous, though generally consistent routing tables. Routing tables store all information necessary for the router to reach every destination on the network irrespective of size (i.e. the network could be j.random LAN with one ip router and two hosts off of an ethernet port or it could be the Internet proper). ----[ Routing Protocols: There are a wide variety of routing protocols used to contribute to the routing tables across a network. Protocols such as BGP, OSPF, RIP and ISIS help to convey a correct and coherent picture of the network to all network switches (routers). ----[ Routing Goals: You can imagine that if each router has to store information that would allow it to reach every destination on the network, there is the possibility for it to amass a large routing table. Large routing tables are difficult (and sometimes impossible) for routers to process because of physical constraints (cpu, memory or a combination). Therefore, we would like to minimize the routing table space without sacrificing the ability to reach every destination on the network. For example, if the router is connected to the Internet via one DS1 link to another router, the router could store routing table information for each destination on the Internet or it could just default non-local information out that serial link. What defaulting means is that if the router does not have a specific entry in its table for the destination that the packet is trying to find, it sends it out the default link. The router towards which a router sends defaulted packets is sometimes called the 'gateway of last resort'. This simple trick allows many routing tables to save a number of entries on the 30th order of magnitude. Routing information should not be exchanged between routers in a spurious fashion. Frequent churn in the routing table puts unnecessary stresses on the scare memory and cpu of any given router. Information propagation should not interfere with the forwarding operations of the router. Though this means that you should not send routing updates every nanosecond, it does not mean that routing information should only be exchanged and updated weekly. One of the important goals of routing is that it provide the host with a table which accurately reflects the current status of the network. The most important aspect of a router's operation is sending packets from input to correct output. Misrouting packets could cause a loss of data. Routing table inconsistencies could also cause routing loops whereby a packet is passed between two adjacent interfaces ad infinitum. It is desirous for routers to have quick convergence. Convergence can be informally defined as a metric which gauges the speed at which routers arrive at a consistent view of the network. It would be ideal to have infinitesimal convergence times because that would ensure that each router on the network can accurately reflect the current topology even after a drastic change (link failure). When the network is changing, each router must propagate data which will aid other routers in converging to the correct picture of the network status. Problems with quick convergence are found in the routing updates. If a link is flapping (changing line status from up to down) rapidly, it can generate numerous installation and withdrawal requests. Therefore, that one link can end up consuming the resources of every router on the network because the other routers are forced to install and withdraw the route in rapid succession. While convergence is an important goal of routing protocols, it is not a panacea to network woes. ----[ Distance Vector Routing Distance vector routing protocols distribute a list of tuples to all of the router's neighbors. These tuples assign a cost to reach every other node of the network. It is important to note that this routing information is only distributed to routers which are assigned as neighbors to the originating router. These neighbors are often physical, but can be logical in the case of eBGP multihop. That cost is the sum of the link costs for the router to reach a destination. Routers periodically send their neighbors distance vector updates; the neighbor then compares the received distance vector to its current distance vector. If the received values are lower, the router sends output to the destination in the distance vector over the link that it received the vector over. The count to infinity problem is a problem with many distance vector implementations. We will assume that all links have a unit cost and that each hop corresponds to a unit. For example, if router X is connected to router Y and router Y is connected to router Z, we can demonstrate this problem (see fig 1). Y knows a 1 hop path to Z and X knows a 2 hop path to Z. Assume that link YZ goes down and the cost of that route is increased to infinity (fig 2). Now, Y knows an infinite cost route to Z because it knows the link is down so it propagates this distance vector to X. Suppose X has sent an update to Y which advertises a 2 hop distance vector. Now, Y will think that it can get to Z through X, so it sends X an update that says it can get to Z in three hops (fig 3). Note that X has no idea that the distance vector being advertised to it was originated from X. This is a serious flaw in distance vectors. In their unmodified form, they do not contain the full path information that the route has traversed. As illustrated above, the router alternates states of advertising a path to Z and advertising infinity to Z. They keep this exchange up forever or until they have reached some internally defined infinity count (say 15 as in the case of RIP). Count to Infinity problem: X--------------------Y--------------------Z Y:1 X:1 X:2 Z:2 Z:1 Y:1 [ fig 1 ] All links are up, below each node we note the destination and hopcount from each respective node. X--------------------Y--------* *---------Z Y:1 <------------- Z:infinity Z:2 -------------> X:1 [ fig 2 ] The link Y - Z breaks. Node X advertises Z:2 to node Y. X--------------------Y--------* *---------Z Z:infinity(frm Y) -> X:1 Y:1 <------------- Z:3 [ fig 3 ] Node Y sends its Z distance vector to X _before_ it recieves node X's infinity. Once node Y receives node X's infinity, it sets its distance to infinity. A path vector is an easy way to defeat the count-to-infinity problem. Basically, each distance vector also includes the router path that it traversed (fig 4). The router rejects an update from its neighbor if the path included in the update includes the router receiving the update (fig 5). The Border Gateway Protocol (which is used to exchange routing information between Autonomous Systems on the Internet) incorporates the path vector to stop the count-to-infinity problem. Obviously, you have to incorporate more information in the routing table if you want to include the AS path information that the route has traversed. The designers of BGP decided that it was optimal to sacrifice storage space and processing power for the robustness that the path vector affords the routing protocol. Path Vector Solution: X--------------------Y--------------------Z Y:1 (Y) X:1 (X) X:2 (YX) Z:2 (YZ) Z:1 (Z) Y:1 (Y) [ fig 4 ] All links are up, below each node we note the destination, hopcount and path vector from each respective node. X--------------------Y--------* *---------Z Y:1 (Y) X:1 (X) Z:2 (Y Z) Z:infinity [ fig 5 ] The link Y - Z breaks. Node Y knows to ignore Xs advertisement of Z because Y is the path vector. The avoids the count-to-infinity problem. Another way to counter this problem is the split horizon. Basically, this means that a router shouldn't advertise a path to a neighbor if that neighbor is the next hop to the destination. This solves the problem presented in the example above because the path to Z from X through Y would not have been advertised to Y because Y is the neighbor _and_ the next hop to the destination (Z). A variation called split horizon with poisonous reverse has router X advertise an infinite cost to get to destination Z. Under a split horizon, router X would not advertise that it could get to router Z. ----[ Link State Routing A router using a link state routing protocol distributes the distance to its neighbors to every other router on the network. This allows each router on the network to make a routing table without knowing the full cost to the destination from any one source. The problems of loops are avoided because each router contains the full topology of the network. Basically, the router makes a 3 tuple containing the source router (itself) the neighbor and the cost to its neighbor. Therefore, if router A is connected to Router B over a link of cost 3 and router A is connected to router C over link cost 5, then router A would advertise the Link State Packets (LSPs) and to all routers on this network. Each router on the network would evaluate all of the LSPs that it receives and calculate a shortest path to every destination on the network. Obviously, the LSP is an integral part of the convergence process. If someone could inject false LSPs into the network, it could result in misrouted information (a packet taking a longer path than it should) or even in the blackholing of a router on the network. This is not necessary a malicious attack of a network, however. Router C could advertise a link to its neighbor D with the 3 tuple and then withdraw the announcement when the link goes down. Unfortunately, if the LSP advertising the link having an infinite cost arrives before the LSP advertising the cost of that link being 6, the routing table will not reflect the topology of the network and will be in that state until another LSP comes to correct the problem. To combat this, a sequence number is introduced into the LSP. Therefore, all of the routers on the network would initialize their sequence number to some starting value and then start advertising their LSPs. This solves the above problem in that the LSP advertising the link of infinite cost would have a higher sequence number than the LSP advertising the link as having cost 6. Some problems encountered when using sequences numbers are finite sequence space, sequence initialization, and aging. It is in the best interest of a robust link state protocol needs to protect its LSPs as well as choose a sequence space which is sufficiently large to accommodate updates. The sequence space that the LSPs can use is set to some finite value. Therefore, when the sequence numbers reach the top of the space, they must wrap around towards the smallest sequence number. This presents a problem because when a router compares link state updates, the greater sequence number takes preference. To combat this problem, you can define a maximum age of the LSP. Therefore, if you have not received an update in X ticks, you discard the current LSP information and wait for a further update. It must be noted that this invalidates the path information to a destination. For example, if router Y advertises a cost to its neighbor router Z where router Y is connected by one link to a meshed network, when the link between the mesh and router Y breaks, the other routers in the mesh have preserved link state information that will allow them to find a path towards Z. If they receive no updates in MAX_AGE, then they will assume that the link to Y is unreachable. This will allow each router to converge its table and allow it to advertise an infinite LSP for Y and Z. Sequence initialization is also an important facet of this problem. Say router Y crashed and is rebooting while the network is recalculating paths to it. When it starts its link state protocol back up, it must somehow indicate that it needs to reinitialize its sequence number to the last number it gave all of the other routers to allow for coherence. Therefore, it can announce paths with a sequence number in a special "initialization set". This initialization set will tell the other routers that this router needs the sequence where it left off. This is the "lollipop sequence" idiom. The sequence space really resembles a lollipop in that the normal sequence number keep churning around the finite sequence space while reinitialization takes place in a short linear sequence space (comparable to the stick :). Great pains are taken to ensure the integrity of LSPs. In fact, this entire routing algorithm depends on the LSP being digested in a coherent method to guarantee that each router has the correct view of the network topology. The question still remains how the root node router computes the distance to each destination. Because of the general nature of a link state protocol, you have various nodes of the network advertising the distance to get to their neighbors to every other node on the network. Thus each node has a collection of neighbor distances from various routers on the network. The routing table is basically 'grown' outward from the root node to all of the network extremities. This will be explained in a slightly rigorous fashion in the next section. ----[ Dijkstra's Algorithm This algorithm is a simple and elegant way to determine network topology. Basically, there are two distinct sets of destinations on the network. Destinations in set K are known routes for which a shortest path has been computed. Destinations in set U are routers for which the best path to that router is not currently known. In this set, paths are being considered as candidates to be the best path to that destination. To start off, add the current node p into the set K. Then add all of its neighbors into the set U with path/cost associations. If there is another path to one of the neighbors in the U set, then choose the path which costs the least. When the neighbors N* are added to U make sure that they indicate the cost through p as well as p's ID . Once this has been done for the set U, then pick the neighbor n to p which has the smallest cost to reach p. This is assuming that the neighbor has not already been installed in K. This algorithm stops when set U is equivalent to the empty set. When set U is null, it is implied that all destinations are in set K and have the shortest cost from the root node P on which this algorithm is running. Note, that each step evaluates adds ONE neighbor into K. That neighbor is the router with the smallest cost to reach p. ----[ Distance Vector vs. Link State We are left with these protocols like BGP which uses path vector and OSPF which uses link state. Why do they occupy such orthogonal space? When a link state protocol is working correctly, it guarantees that there will be no routing loops in the network. The link state protocol also guarantees fast convergence when there is a change in the topology of the network because the link state is distributed on a flat routing space. Since link state protocols contain these inherent advantages, why do protocols like BGP chose to employ the path vector approach? Taking a cross-section of routing protocols that are employed on the internet, one finds that the majority of large providers use OSPF to resolve routing information on their internal network and BGP to talk to other distinct networks (or autonomous systems) at their borders of administration. What suits BGP as an external protocol and OSPF for an internal routing protocol? One issue, which will be discussed in the next section, is hierarchy. BGP provides a mechanism for a routing hierarchy which enables it to greatly reduce the space of its table. OSPF, which is a link state protocol, provides a flat routing table whereby any internal router knows the full hop by hop path to any destination within the autonomous system. Furthermore, distance vector protocols understand that different areas can have different views of the network where link state protocols require that each node independently compute a consistent view of the network. This saves the DV protocol the overhead of maintaining a correct LSP database. BGP also has another 'advantage' in that it is layered on top of the Transmission Control Protocol (TCP). Therefore, in the 'best-effort' service of IP networks, BGP has assurance (to the level that TCP can guarantee) that routing information will be propagated. Whereas, you can (or should) be able to govern the status of your internal network, the nebulous exterior past your border routers confers no delivery guarantee on your routing information. Each type of routing algorithm is suited for its function. Link State protocols provide the quick convergence that is essential to an internal network while distance vector protocols provide external reachability. Hierarchy is not something that is inherent in distance vector protocols, but the implementation of a hierarchy has made BGP a widely used exterior gateway protocol. ----[ Routing Hierarchy Routing hierarchy is an oft fought debate that borders on religion. There are constantly questions about how hierarchy should be implemented (if at all) in the free form state of the current global network. Hierarchy imposes a tree of authority with the overall authority at the top of the tree and branching down to regional authorities, local authorities ad infinitum. Hierarchy simplifies routing because if a destination is not locally routable (or under your section of the tree). You can iterate up towards the top tree to try and deliver that information. As you move towards the top, the routing information contained in the routers becomes less and less specific until you reach the root node which is the least specific. It does, however, know how to route information to every possible destination on the network. It may help you to envision the hierarchy of the telephone network (built under one collective). If a call cannot be placed within a central office, it is handed to either another central office in the area code or a wide area link. The wide area link understands how to route to each area code in a full national mesh whilst the local 5ess switch only knows routing information for more specific prefixes. As the phone number becomes less specific (from right to left), the routing decision moves further up the strict hierarchy. This similar to how the domain name system (DNS) works on the internet (fig 6). You provide local records for domains that you host. When your nameserver receives a query for a record, it either returns the fact that it has authority for that record or points toward the root nameserver. The root nameserver knows the delegations of .com, .net, .org et al. and then points towards the site responsible for that top level domain. That site then points towards the site that has authority for the specific second level domain. Domain names take the form of most specific -> least specific; i.e. microsoft.com is more specific than just .com. Likewise gates.house.microsoft.com is more specific than microsoft.com. DNS Hierarchy: ___ . ___ / | \ .com. .org. .edu. / | \ microsoft.com. eff.org. isi.edu. / | \ billy.microsoft.com. x0r.eff.org. rs.isi.edu. [ fig 6 ] Each level in the hierarchy is responsible for levels of greater specificity. Root authority is controlled by the Internet Assigned Numbers Authority (IANA). It provides the top of the hierarchy in a "centrally" managed database (in fact, there are multiple root servers distributed across the county which maintain a consistent database). This is the closest example of strict hierarchy that can be found on the internet. With IP addresses, specificity increases in the opposite direction. IP addresses (version 4) are 32-bits. The rightmost bit signifies the greatest amount of specificity and the leftmost, the least. IP routing authority information is not maintained in a centralized database. Routing information is exchanged between autonomous systems via the BGP protocol. Routes take preference in order of most specific -> least specific. In this way, there is some type of hierarchy in the system (even though it is more loose than the DNS example). Generally, larger providers control larger parts of the total IPv4 space ((2^32) - 3 addresses). The converse is also true. Classless Inter-Domain Routing (CIDR) also helped to decrease the size of routing tables and increase the appearance of hierarchy. Now, instead of Sprint announcing routes to 130.4.0.0 through 130.20.0.0 (on the classical B space boundary) it could announce 130.4.0.0/12 which encompasses that entire 16 class B range. The classful ranges, subnetworking and the like are discussed in my "introduction to IP" page and are therefore not included in this document. ----[ Routing Hierarchy and Aggregation BBN divides their 8/8 network into two subnetworks and advertises reachability to the aggregate to save table space. Once inside an AS, routing obeys a fairly strict hierarchy. Router A is responsible for the entire 131.103/16. It divides it into two /17. Likewise, Router D in AS1 is responsible for 8/8 and chooses to divide it into 8.0/9 and 8.128/9 and divides responsibility for these networks to Routers E and F respectively (fig 7). Routers B, C, E, and F can further choose to subdivide their networks in a hierarchical fashion. Because of the binary nature of subnetting, networks can only be divided in half. Routing Hierarchy and Aggregation: BGP 131.169.0.0/16 <--------------------> 8.0.0.0/8 A (AS1239) D (AS1) / \ / \ B / \ C E / \ F / \ / \ 131.169.0.0/17 131.169.128.0/17 8.0/9 8.128/9 [ fig 7 ] In the internet, there is no strict routing hierarchy. There are simply large networks which peer via BGP to distribute aggregated routing information. The national backbone is populated by few nodes (when compared to the end nodes). Most national providers are one or two router hops away from every large network. Through aggregation in networks below, national providers provide fully (or at least we hope) aggregated routing information. In a strict hierarchy, only one router on any given hierarchy level can advertise reachability to a specific portion of the network. In the current state of the Internet, multiple routers can advertise reachability information. For example, Sprint announces 131.169.0.0/16 out to Digex, MCI, and BBN. Though this breaks some of the benefits of a strict hierarchy, it confers other benefits. This scheme allows for distributed control of routing information instead of depending on the node above. Also, nodes on the same level are often interconnected to aid in the dissemination of routing information. ----[ Aggregation As discussed slightly before, aggregation allowed the internet to reduce the size of its external reachability tables. Before, the granularity of route announcements allowed for only /8, /16, and /24 (octet boundaries). Now, with CIDR you could use variable length subnet masks. The only requirement was that they fall on one of the 32-bit boundaries of the IP address. Classless routing not only allows us to minimize routing table space, it also allows us to divide up large chunks of unused space into manageable pieces. Much of the Class A space is terribly under-utilized. With this scheme one can more efficiently allocate IP addresses to providers/netizens. The American Registry of Internet Numbers (ARIN) controls the allocation of IP addresses within the United States. Aggregation helps alleviate the problems of not being in a strict hierarchical structure. It allows the least amount of route table specificity at each level (assuming the routers on that level choose to fully aggregate their announcements.) The less specific aggregates do not necessarily indicate the position of a router in the hierarchy. For example, a university may announce a /8 and be 3 hops away from the national backbone. A problem with aggregates can be found when we examine candidate route specificity. If ISP A only has address space from within the allocated block to their parent P, then aggregation could cause problems if ISP A wanted to multihome to parent Q. The problem comes in that ISP A is obligated to advertise reachability only to their space. This would constitute them announcing their address space to Parent Q. Assume that parent P aggregates ISP A's space into a /16 for the sake of saving route announcements. Now, ISP A would seem to have better reachability only through parent Q because of the specificity of the route announcement (remember that more specific routes take precedence over less specific routes). This would nullify the benefits of multihoming in an attempt to distribute load over the two lines. In this case, ISP A would ask parent P to announce a more specific destination which has a length matching the length of the aggregate assigned to ISP A. Therefore, to the world above parent P and parent Q, the path to ISP A looks equally appealing. ----[ Exterior/Interior It is important to look at how routing information is disseminated throughout the network. It has already been discussed that we use separate routing protocols (with their respective benefits/costs) to talk to the internal and external world. However, these protocols cannot take orthogonal views on routing information. In fact, the interplay between interior and exterior routing protocols is what allows data to be effectively relayed to a destination external to the network as well as to distribute external routing information to all nodes on the internal network. There are a few ways to ensure that each router has a consistent view of the network. One is to distribute the external protocol into the internal protocol. Thereby, the internal protocol instantly has routing information injected in it for the best path to every external destination. Note that the router which talks eBGP (or comparable protocol) only redistributes the route that it installs in its routing table and not the other candidate routes which may have been advertised to it. Another approach is to inject the interior protocol into the exterior protocol. Of course, this necessitates filtering at the entrance point to the exterior protocol to prevent the announcement of all internal specifics. You can accomplish internal routing dissemination inside an Interior Gateway Protocol mesh. Because of the specifics of protocols like BGP, externally learned routing information will only be propagated one logical hop within the network. Therefore, every router that must know this external reachability information, must be fully meshed with the eBGP speaking routers. Also, if other routers are injecting information into the Exterior Gateway Protocol, the router should be logically fully meshed with them. ----[ Multicast Routing Overview What we have been talking about above is unicast routing. In unicast routing, you assume that each packet has a single destination address. Assuming infinite resources being available, unicast is a feasible solution for every situation. However, there are situations when it would be advantageous to send a packet to multiple destinations from a single source (point to multipoint) or from multiple sources to multiple recipients (multipoint to multipoint). The point of multicast is to provide a multicast group to which hosts can subscribe and get the specific multicast feed. The multicast group is a single IP address in class D space. Therefore, the senders and receivers are only associated by a given multicast group address. Thus, the senders move their data towards the multicast group address and the receivers specify that they want to receive information from a given group address. In fact, the sender is not required to know any information about the hosts that are receiving the feed. ----[ Multicast vs. Unicast If one was sending packets from a single source to a set of destinations, it is important to investigate how multicast and unicast handle the distribution. Assume that router A is sending data to routers B, D and E. A is at the top of the hierarchy, B and C are at the second level of the hierarchy, and D and E are below router B. With multiple unicast (fig 8), router A makes 3 copies of the packet and sends them down link AB. Router B then sends one packet to a host off of its ethernet and forwards the last two packets to routers D and E whereupon those routers send the packets to the their respective hosts in the multicast group. Therefore, this transmission takes up 3 packets per second on link AB and 1 pps on links B->Host(b), router D and router E. In a multicast routing implementation, assuming the same topology, we will have less packets. The difference is that router A sends _one_ packet over link AB. Router B then triplicates the packet and sends it to Host(b), router D and router E (fig 9). One way for triplicating the packet is to simultaneously close crossbars on a fully crossed switch fabric, thus sending data from one input to three outputs simultaneously. As long as there is route redundancy, multicast is very efficient because it minimizes redundant packets traveling to the same next-hop. Simply, as long as there is route redundancy for the distributed session (for example, an audio feed) you will see an advantage with multicast over unicast. Multicast Overview Example: Multiple Unicast: A A sends 3 packets to B. / \ / \ 3 / \ C B B sends 1 packet to each to D and E. / \ 1 / \ 1 / \ D E D and E send 1 packet to their respective hosts. [ fig 8 ] Multicast: A A sends 1 packet to B / \ / \ 1 / \ C B B duplicates the packet for its host; / \ therefore, there is 1 packet (at most) on 1 / \ 1 each link. / \ D E [ fig 9 ] This is a multicast topology rooted at node A. There is also a shortest path from A to every destination in the multicast group. This is called the shortest path multicast tree rooted in A. Data would like to shortest path on the network layer. One problem with multicast sessions is that recipients join and leave during a multicast session. This requires pruning of the multicast "tree" so that packets do not clutter a link on which there is no one requesting data from a given multicast group. To detect if there are hosts on a particular broadcast LAN that are interested in a multicast group, the router sends out Internet Group Management Protocol (IGMP) messages. Each packet has a random reply time from which the host will express interest. This is to prevent all hosts on a broadcast LAN from responding at the same time to an IGMP query. Once one host desires to receive data destined for a particular multicast groups, all other hosts which desire to be in the multicast group can discard their replies because the router knows to multicast all incoming packets destined for that group. The host then configures its adapter to answer for the MAC address corresponding to that group. Multicast must also be functional outside of the broadcast LAN. A simple solution to the problem is to give each router for which multicast is enabled the multicast packet. This is called flooding. Basically, it functions by forwarding the packet to every interface other than the one that the packet arrived on. The inherent flaws in this approach is that there is packet duplication as well as packets being sent to routers which have no hosts subscribed to the multicast group. To clarify the duplication statement, if Router A is physically meshed with routers B, C, and D and linked to its upstream via serial, when router A receives the multicast packet, it floods it out the interfaces to routers B, C, and D. These routers then flood the packet out the interface other than the one they received the packet on (namely the interface that connects them to A). This results in each of these routers receiving two copies of the packet (other than the one they received from A) in this exchange. A solution to this problem can be found in a technique called Reverse Path Forwarding (RPF). RPF specifies that the router forwards a packet with a source address of X only if the interface which the router receives the packet on corresponds to the shortest path that router has to source X (fig 10). Therefore, in the above example, each of the meshed routers _still_ receives 2 duplicate packets in the second step, but they refuse to forward them because only the packet received from the interface directly connected to A will be forwarded. As noted, RPF does not completely solve the problem of packet duplication. To solve this, we must introduce pruning. The idea is simplistic: inform neighbors that you do not wish to receive multicast packets from source X to multicast group Y. You can also specify prunes to a particular group. If a router tells its neighbors that it did not desire to receive packets for group Y and then has a host which desires to receive group Y, it sends a graft message to its neighbors specifying that it be added into the multicast tree. As a unicast aside, RPF can also be used to eliminate source address spoofing in that the router will only forward packets from source Y if it is receiving it on the interface which is the shortest path to source Y. Thus, if the router receives packets from an external link which say their saddr == saddr(y), the router will not forward them because its shortest path to Y is not from the external link. RPF Example: | <-- Point of ingress. | A-----------C |\ /| | \_______/ | | / \ | |/ \| B-----------D [ fig 10 ] ABCD are physically meshed. When A distributes a packet to BCD, there is no problem. Now, in the next step, B, C,and D forward the packet to each of their respective neighbors (for B it would be C and D and ! A because it received the packet from A). This results in C and D receiving 2 packets in this entire exchange. Note that C and D now do _not_ forward the packet they have received from A through B because that is not their shortest path to A. Their shortest path is their direct link. ----[ The Multicast Backbone (MBONE) It would be myopic to assume that every router on the internet supports multicast. Thus, when a router needed to find the shortest path to a destination (for forwarding of a multicast packet) it could look in the unicast routing table. Unfortunately (or fortunately depending on your perspective) most routers on the Internet do not support multicast or do not have it enabled by default. Therefore, until most routers support multicast, it has been "layered" over IP and tunneled from multicast router to multicast router (more specifically, the multicast header and data is encapsulated in a unicast IP header). The tunnel (which bridges the gap of unicast only routers between multicast routers) informs each end that some packets will contain a multicast group in their payload. This allows data to be routed by using unicast forwarding tables while at the same time preserving the integrity of the multicast group id. Because these multicast routers are not necessarily connected physically (though they are tunneled logically), they must be connected by a multicast routing protocol. This is necessary because the closest path via multicast may not correspond to the shortest path over unicast only routers. Distance Vector Multicast Routing Protocol (DVMRP) is an initial foray into this realm. DVMRP distributes "unicast" routes to facilitate the construction of shortest path trees. DVMRP uses the flood and prune method discussed above to discover /maintain multicast trees. There is also a link state foray into this arena. Multicast Open Shortest Path First (MOSPF) takes the LSP approach and calculates shortest absolute path. One host off of a multicast router can request to be in a multicast group. That router then distributes an LSP over the network. Of course, MOSPF (being a link state protocol) runs into salability problems. It is computationally expensive for a router to compute reachability information for each end node router. Core based trees (CBT) are an attempt to alleviate the problems that DVMRP and MOSPF experience. The concept is that multicast routers send join requests to core routers of arbitrary designation. When a router learns of a host which wishes to join a specific multicast group, it forwards a packet to the core multicast router. Every router along the way forwards the packet towards the core router and marks the interface on which the packet arrives so that it knows where to forward the multicast packets from the core. This solves the problem of having to communicate topology among all of the endpoints. The choice of a core multicast router is a non-trivial because all multicast traffic for multicast routers branching off of it _must_ pass through the core router. ----[ Protocol Independent Multicast Protocol independent multicast (PIM). Pim is a balance between flood and prune and CBT. When there are many multicast routers on a given network, it is more efficient to use the flood-and-prune method. This network environment is called "dense". On the contrary, sparse mode defines networks where there are few multicast routers. In sparse mode, it is more efficient to use CBT because the core router is not weighted in an environment when it 'polices' few multicast routers. When most of network is comprised of multicast routers, it is not prudent to require all sessions to be coordinated (and routed through) a core. Sparse mode PIM has been adapted from CBT to allow data to reach its destination via the core or through the shortest path tree. Currently, the operator must define whether groups are sparse or dense instead of leaving it up to the protocol. cisco systems' implementation of pim also supports a middle ground called 'sparse-dense' mode. ----[ Border Gateway Protocol There has been some mention of the Border Gateway Protocol (BGP) in this document. BGP was groomed as the successor to the Exterior Gateway Protocol (EGP). BGP is mainly an exterior routing protocol. It is used to communicate with systems outside of the operator's control and both distribute and receive network layer reachability information (NRLI) from the neighboring routers. BGP must be a robust protocol which has the capability of quick convergence while at the same time, not being influenced by frequent shifts in topology. When you use BGP to receive routing information, you are depending on the other networks to distribute correct information to your network. A BGP speaking router communicates with its peers via TCP. TCP over IP is a mechanism for guaranteeing the transmission of data over a best effort service at the IP layer. The choice of TCP as the distribution mechanism for BGP information is a point of contention. While TCP provides inherent checksums, acknowledgments, retransmissions and duplicate suppression mechanisms for received packets, it does not guarantee packet order or packet path. This can lead to headaches for the router receiving this information. BGP peers communicate with a variety of message formats. BGP speakers use the OPEN message to establish a peering relationship with other speakers. BGP speakers use the UPDATE message to transfer routing information between peers. Update information includes all routes and their associated attributes. KEEPALIVE messages assure that BGP peers are active. NOTIFICATION messages inform peers of error conditions. ----[ BGP path selection It is important that we understand the messages that constitute the Border Gateway Protocol, but we are still left with the question of how BGP works on the internet. One important area of clarification is in the BGP path selection algorithm. This algorithm is how BGP decides which route to prefer and attempt to install in the routing table. This algorithm is employed when there are multiple paths to a destination. As a failsafe, the first selection looks at the next hop and determines if it is accessible. If the next hop is not accessible, it is important not to consider that route as a candidate path to a destination because all data sent to its next_hop will be blackholed. The second selection mechanism is the weight of the route. Weight is a proprietary implementation to cisco Systems routers and is analogous to local preference. If two routes have different weights, the route with the largest weight is selected. Notice that the selection mechanism is basically a logical if->then chain. If candidate paths differ at a level of the selection algorithm, then the favorable path is selected and the algorithm ceases trying to decide which path to prefer. The next level is the local_pref attribute. This is a well known mandatory BGP attribute. Much like weight, the path with the highest local_pref is preferred. After local preference, the router selects the path that it originated. If the router didn't originate the paths, then the path with the shortest AS_PATH length should be selected. AS path length gauges the number of autonomous systems that this routing information has traveled through. The purpose of this selection relies in the assumption that the less ASNs the route has passed through, the closer the destination. If all of the above attributes are identical, then prefer path origin in this fashion IGP > EGP > Incomplete. If the path origins are the same, prefer the path with the lowest value MULTI_EXIT_DESCRIMINATOR (MED). MEDs are commonly used to distinguish between multiple exit points to the same peer AS. If none of these attributes are dissimilar, then prefer the path through the closest IGP neighbor. If that fails, the tiebreaker is preferring the path with the lowest IP address specified in the BGP router-id section discussed above. This selection algorithm allows effective establishment of routing policy. If I wanted to prefer routes from a certain AS over routes to another AS, I could establish a route-map at both entry points of external routing information and assign a higher LOCAL_PREF to the routes from the AS I want to favor. Unfortunately, this does not provide much granularity. This means that all traffic will be routed to the favorable AS and does not allow us to balance the load over our multiple connections. If you allow path selection to progress to the AS path length decision level, then you will get decent (though not 50-50) load balancing to destinations. This of course is assuming that you have providers with comparable customer routes and connectivity. If you have a DS3 to MCI and a DS3 to the local BFE provider, nearly all traffic will move out the MCI pipe if the BGP decision is allowed to progress down to the AS path length category. At earlier selections, you can change the preference of routes by using AS path access lists to select routes based on as path regular expressions. For example, if you wanted to select all routes that traversed UUnet and send them out your BFE provider, you could use a route map to match an AS path access list which contained _701_ and set the local_pref to 100 (or some value higher than the UUwho traversed paths from MCI). This will force all traffic destined for UUwho to exit your AS over your BFE DS3. While this affords you some granularity in load balancing, it is often not optimal. Basically, you are forcing traffic out a path that it would not normally select. If that BFE provider has many hops before it can reach UUnet, you are forcing the traffic you send out that link to traverse all of those hops and be subject to (possibly) more link congestion, latency, etc. Routing policy is something that requires the tweaking of many knobs. Much of the tweaking I have described above pertains to cisco Systems routers. It is important to understand that you must think through routing policy before you implement it. You must evaluate what load balancing you want, what traffic symmetry you want, and what general quality of service your traffic will receive because of your decisions. For information more specific than this, read the BGP RFC or current BGPv4 internet draft [1]. ----[ Open Shortest Path First v2 (OSPFv2) We are not going into great detail about OSPF. It is a link state routing algorithm. As noted above, link state algorithms route on flat space (no hierarchy). OSPF is an improvement over the vanilla LS protocol because it provides areas of maintenance for hierarchy purposes. Areas distribute full information internally by running a separate OSPF process with its area ID. Each router has an identical link state database with other routers within its area, but not with external routers. Each area operates in an autonomous state and transfers inter-area information at junction routers called area border routers. These routers are in two or more areas and help distribute information between these areas. The router has separate link state databases for each area to which it is connected. OSPFv2's main advantage is that it supports Variable Length Subnet Masks (VLSM). This means that a router can advertise reachability with more granularity than a scheme which advertised host reachability. Therefore, if the router can distribute packets to all hosts from 206.4.4.1 -> 206.4.5.254 it advertises reachability to 206.4.4.0/23 instead of each classful network separately or each host separately. This obviously saves immensely on link state database size and processing power required. For information more specific than this, read the current OSPFv2 RFC or internet draft [2]. ----[ References [1] Rehkter, Y., Li, T., " A Border Gateway Protocol 4 (BGP-4)", draft-ietf-idr-bgp4-07.txt, February 1998. [2] Moy, J., "OSPF Version 2", draft-ietf-ospf-vers2-02.txt, January 1998. ----[ EOF