Ospf anatomy of an internet routing protocol free download

Early Internet routers simply started discarding excess packets instead of queuing them onto already full transmit queues; these routers were eventually termed drop-tail gateways. However, this discard behavior was found to be unfair, favoring applications that send larger and more bursty data streams. Algorithms also have been developed that allow routers to organize their transmit queues so as to give resource guarantees to certain classes of traffic or to specific applications.

A protocol called RSVP [] has been developed that allows hosts to dynamically signal to routers which applications should get special queuing treatment. However, RSVP has not yet been deployed, with some people arguing that queuing preference could more simply be indicated by using the precedence bits in the IP header [45]. The reason for modifying the routers is usually that there are fewer routers than hosts, and router software is typically much easier to upgrade.

Companies often put a router between their company network and the Internet and then configure the router to prevent unauthorized access to the company's resources from the Internet. This configuration may consist of certain patterns for example, source and destination address and TCP port whose matching packets should not be forwarded or of more complex rules to deal with protocols that vary their port numbers over time, such as the File Transfer Protocol FTP [].

Such routers are called firewalls [41]. Similarly, Internet Service Providers often configure their routers to verify the source address in all packets received from the ISP's customers. This foils certain security attacks and makes other attacks easier to trace back to their source. Packet tracing. People often use their routers to collect packet traces, in order to diagnose network problems.

Statistics collection. Some people collect traffic statistics on their routers: how many packets and bytes are forwarded per each IP source and destination combination. This may be too fine a granularity, and statistics may be kept instead per source and destination Autonomous System AS, the administrative groupings of routers within the Internet, as described in Section 2. These statistics are used for future capacity planning. However, in the future, such statistics may be used by ISPs to implement usage-based charging schemes for their customers or as a way to implement settlement schemes between the ISPs themselves.

However, to get the ball rolling, the source host must find a router to send the packet to in the first place. This has always been a weak spot in the IP protocol suite. IP does not have a good way to find the best first-hop router to use for a particular destination and for a long time had no way to dynamically find any router. Let us first step back a bit. How does a host determine whether a router has to get involved at all? The host checks to see whether the destination belongs to one of its directly attached network segments.

For example, suppose that a host has a single interface onto a network segment with address of This means that all hosts with addresses Packets can be sent directly to these hosts without using a router. However, if the host wants to send a packet to Traditionally a host would have a configured set of one or more default gateways gateway being the previous term for what we now call a router to send the packet to.

However, the configured default, or discovered, router may not be the best router to use for the given destination. For example, in Figure 1. If the host's default router is The default router, realizing that it is forwarding the packet back onto the segment where it originated, sends an ICMP Redirect message back to the host The host then stores this information in its routing table. Such redirect information must be timed out and refreshed periodically lest the disappearance of the first-hop router which possibly could be detected by ICMP router discovery, or ping cause the destination to be permanently unreachable.

ICMP Redirect messages remove extra router hops. Unfortunately redirect timeouts are often quite long, causing transport connections to fail before old redirect information is removed.

For this reason, router vendors have developed protocols whereby another router can take the place of the failed router assuming its IP and MAC addresses without the host's knowledge. One such example is Cisco Systems' "hot standby router protocol" []. This protocol introduces the concept of a "virtual IP address.

Another common method for finding the best router for a particular destination is to have the host participate in the IP routing protocols sometimes referred to as wire-tapping, since the host is really only eavesdropping on the routers' routing protocols , although this solution is discouraged by IP purists. IP addresses are generally represented in dotted decimal notation: the decimal value of each byte of the address, separated by periods.

For example, the IP address whose hexadecimal value is Oxc is written as By looking at the IP address, a router can determine quickly whether it is a unicast, broadcast, or multicast address, as shown in Table 1. The address space is broken into three chunks: the majority used for unicast, a range of multicast addresses see Chapter 9, Internet Multicast Routing , and a small portion at the top of the address space that is reserved for future applications.

There are also some special-purpose addresses. A host uses 0. Packets sent onto a network segment with IP destination set to the broadcast address Table 1.

Hosts and router interfaces attaching to the segment are then assigned unicast addresses from the set. For example, the network segment in Figure 1. This is also sometimes written as the address, mask pair [ The host and two routers in Figure 1.

The highest address in the prefix is assigned as the broadcast address for the segment. For example, A packet sent to this address will be delivered to all hosts and routers attached to the segment. When forwarding a packet, a router looks in its routing table see Section 2. However, it is more correct to say that routers route to prefixes. Routers cannot possibly keep track of every segment in the Internet. Instead a segment's addressing information is aggregated into shorter prefixes at points in the Internet.

It is routes to these shorter prefixes, which may have been aggregated up to three or four times from the original segment prefixes, that are kept in the router's routing table. An example of aggregation is shown in Figure 1. Router G is aggregating the addresses of the four segments on its right This means that routers A—F are not aware of the four segments to G's right but instead have a single routing table entry for Prior to , prefixes were forced into a small number of fixed-sized lengths, based on address class see Section 1.

When this restriction was lifted, allowing arbitrary prefix lengths, much more aggressive aggregation became possible, allowing for greater conservation of IP address space and a slowing of the growth rate of the Internet core routers' routing tables see Section 2. Termed provider addressing, this procedure encourages address aggregation; the ISP can aggregate its customer's addresses and advertise only the larger address blocks to other ISPs. A side effect of provider addressing occurs when a customer wants to change ISPs.

To maintain address aggregation, the customer is encouraged to give back its old addresses and to renumber its network segments into one of its new ISP's address blocks []. Hence the assignment of addresses from ISPs to their customers is termed address lending. As one example, the loopback address However, even when using these private, nonunique addresses, private internets may be attached to the public Internet through Network Address Translation NAT [79] devices.

These devices convert the addresses in packets destined for the public Internet, substituting dynamically assigned globally unique addresses for all private addresses appearing within the packet.

A Short History of Internet Addressing Internet unicast addresses were not always assigned as arbitrary-length prefixes. In the beginning, the Internet address space was carved up into fixed networks of three sizes: Class A, B, and C networks. Class A networks, which we would now call a CIDR prefix of length 8, could contain more than 16 million hosts. Whether any particular address belonged to a Class A, B, or C network could be determined quickly by looking at the address's first byte, as shown in Table 1.

Class D addresses were later assigned for IP multicast, with Class E remaining reserved for future use. How often would several thousand hosts be attached to a single Ethernet segment? Also, assigning each physical network segment a separate network number would force the Internet's routing table to grow linearly with the number of segments. To avoid these problems, subnetting was invented [], adding another level of hierarchy to the Internet's routing and addressing.

With subnetting, each Class A, B, or C network number could be broken up into fixed-sized pieces called subnets, with each subnet assigned to a different physical segment.

Take, for example, the Class B network If the third byte were used for this purpose, In this way, a single Class B network could be used to address hundreds of segments, a Class A network thousands. Outside of the subnetted network, all of the segments would be covered by a single Class A, B, or C routing table entry. In the presence of subnets, additional broadcast addresses were defined in RFC []. Setting all of a subnet's host bits to 1 resulted in the subnet's directed-broadcast address. This address could be used to send a packet to all hosts on the subnet, even when the packet was originated from a distant segment.

For the subnetted network, setting both the subnet and the host bits to 1 resulted in the all-subnets-broadcast address. Although never widely implemented, a packet sent to this address was supposed to be delivered to all hosts on all subnets of the given Class A, B, or C network. Using the earlier example of the Class B network Forwarding of IP broadcasts is described in Section 9.

So in the previous example, Eventually the restriction that all subnets be the same size was found too limiting. Subnet size was driven by the segment having the largest number of hosts, wasting addresses on the smaller segments. In our example, if the To solve this problem, people began dividing their Class A, B, and C networks into subnets of varying sizes; this has been called variablelength subnet masks, or VLSMs.

As just one combination, With VLSMs, schemes were developed allowing subnet masks to be adjusted as the host population of segments changed, without renumbering hosts []. Subnet numbers usually were assigned to immediately follow the network prefix.

If there was a gap between the network prefix and the subnet number, the subnet mask was termed discontiguous. An example of a discontiguous subnet mask is using the fourth byte of a Class B network to indicate the subnet number, resulting in a subnet mask of The combination of VLSMs and discontiguous subnet masks was a bad one, for two reasons.

First, certain assignments of discontiguous subnet masks could result in multiple subnets matching the same number of bits, making the concept of best match ambiguous! Second, common routing table lookup algorithms, such as Patricia see Section 2. Discontiguous subnet masks are now prohibited by the latest router-requirements RFC [12].

In , concern grew over the possibility of the Internet address space becoming exhausted. A good percentage of the Class B addresses had already been assigned, and the Internet number authorities wanted to start assigning multiple Class C networks instead. However, since each Class A, B, and C network appeared as individual entries in the Internet core routers, assigning multiple Class Cs ran the risk of exhausting the table space of the Internet's routers.

The idea of using a single routing table entry to represent routes to a collection of class C networks led to CIDR and the current prefix-based, classless Internet routing paradigm. For example, the prefix Such an entry is sometimes referred to as a supernet. Tunneling Suppose that routers A and B know how to forward datagrams addressed to the IP destination X but that the intervening routers between A and B do not.

In order to deliver packets to X, a tunnel is configured between routers A and B: When A receives a packet destined for X, it alters that packet to look as though the destination is really router B, in essence tricking the intervening routers to forward the packet. When B receives the packet, it returns the packet to its original state possibly altering its TTL; see [] and forwards it on toward X. Why would the intervening routers between routers A and B not know how to forward to X?

DVMRP calculates paths for multicast datagrams. As another example, in many regions of the Internet, only those routers participating in BGP see Section In order to forward data traffic to certain destinations, tunnels must be configured between BGP routers.

Two separate mechanisms may be used to implement such a tunnel. The first is the source route option. When forwarding datagrams addressed to X, router A puts router B's address into the IP header as destination address and moves address X into a loose source route option. The second mechanism is to encapsulate the packet by a complete extra IP header. This IP header is again addressed to router B, and the protocol number in this header is set to 4, telling B that it should strip the IP header and forward the encapsulated packet [].

The second mechanism is usually preferred, due to the significant performance degradation seen in most Internet routers when IP options are employed. Although tunnels are sometimes necessary, they are usually to be avoided. The process of adding and stripping information be it source routes or extra IP headers at the tunnel end points routers A and B decreases forwarding performance in those routers.

The additional information also makes it more likely that fragmentation will be necessary, although hosts can avoid fragmentation by using the Path MTU discovery algorithm [], which can take tunneling into account.

Worst of all, tunneling can subvert firewalls and in general make traffic monitoring more difficult; the real destination is buried in the options field or in additional IP headers. IPv6 Prompted by the fear of exhausting the Internet's address space, designers began work in on a new version of IP with larger addresses. This culminated in with the publication of a full set of network-layer protocol specifications the other layers of the protocol stack remaining unchanged for IPv6 [49], [61], [99], [], with the Internet's currently deployed IP being referred to in comparison as IPv4.

We touch only briefly on IPv6 in this book. Mainly because IPv6 is not all that much different from IPv4. IPv6 has made a number of incremental improvements over IPv4 yet can be summarized roughly as "IPv4 with bit addresses. IPv6 also has not been widely deployed, probably for several reasons.

First, the original fear that IPv4's address space soon may be exhausted now seems an overreaction. The deployment of CIDR has improved the efficiency of address usage, and fear has now shifted to the routing tables' expanding beyond the capacity of the Internet's core routers—a problem that IPv6 does not solve. The possibility of organizations using the private Internet address space see Section 1. Since IPv6 does not enable any new classes of network applications, conversion of the large base of routers and hosts running IPv4 is likely to be delayed until IPv4 address exhaustion again seems imminent.

IPv6 can be thought of as an attempt to capture current IPv4 usage in protocol specifications. Those IPv4 features that are either unused for example, TOS-based routing or discouraged such as fragmentation by intermediate routers have been deleted from the IPv6 protocol specifications. IPv6 has made mandatory several IPv4 features that are desirable but have yet to see widespread deployment: IP multicast and security.

In addition, address scoping has been made an initial part of the IPv6 addressing architecture [99], building on IPv4 experience with private internet addresses [] and proposals for IPv4 multicast address scope []. Address scoping is a way of dropping the globaluniqueness requirement for certain addresses. IPv6 supports link-local unique only on a given segment and site-local unique only within a certain "site" address scopes, as well as the usual globally unique addresses.

In IPv6, addresses are no longer written in dotted decimal notation. Instead the IPv6 address is broken into eight bit pieces, and each piece is then expressed in hexadecimal, with the pieces separated by colons. As a shortcut, the longest string of bit 0s within an address can be abbreviated as :: but only one string within an address, to avoid ambiguities ; our example address can also be written as cCC:A Because of the increase in address size, the IPv6 packet header is somewhat larger than IPv4's header, with the minimum size IPv6 header twice the size of the minimum IPv4 header.

The IPv6 network layer header is depicted in Figure 1. The IPv6 network-layer packet header. All of the fields in the IPv6 header were also present in IPv4, with the exception of the Flow Label, although some fields have been renamed. The Version field is, of course, set to 6.

The Priority field carries similar semantics to IPv4's precedence field, carrying an indication of a packet's transmission queuing priority, although IPv6 allows this field to be rewritten at each router hop. The Payload Length is simply the length of the packet in bytes. The Next Header field is the same as IPv4's Protocol field, even going so far as to use the same encodings.

For example, a Next Header field of 6 see Figure 1. Use of the Flow Label in IPv6 has not yet been completely determined, although the general idea is to provide a forwarding hint to routers for particular packet streams. IPv6 uses different data-link encapsulations than IPv4 does. Although the Version field would in theory allow both IPv4 and IPv6 to use the same data-link encapsulations, experience with the ST2 protocol an experimental flow-oriented network-layer protocol that was assigned IP version number 5; see [63] indicated that many IPv4 implementations do not bother to check the Version field and would get very confused on receiving an IPv6 packet.

Defining new data-link encapsulations is mostly an administrative task; for example, IPv6 has been assigned the Ethernet type of 0x86DD [52], as opposed to IPv4's Ethernet types 0x IPv6 has distilled and simplified IPv4's packet-forwarding process.

The Header Checksum field has also disappeared; those applications that include the IPv6 source and destination addresses as part of their connection identifier must include part of the IPv6 header in an application checksum much as is done for TCP in IPv4 or risk having corrupted packets associated with the wrong connections.

Routers also do not fragment packets, something always thought best avoided in IPv4. Instead they simply send an error back to the source when they are unable to fit the packet onto the next data link.

IPv6 supports header options as IPv4 does, such as source routing. In IPv6, however, options are encoded as a separate header between the IPv6 header and application data. Additional headers may also be inserted before the application data, to implement authentication, security, and source-packet fragmentation. Each header indicates the function of the next-in-line encapsulated header by proper setting of the Next Header field.

IPv6 does not use ARP. In addition, IPv6 neighbor discovery implements two functions not present in IPv4: address autoconfiguration and duplicateaddress detection. See, for example, the papers by Leiner et al. Bertsekas and Gallagher's text Data Networks [20] is a thorough introduction to data communications for the theoretically inclined.

Anyone looking just for a survey of networking protocols may be more comfortable with Tanenbaum []. The router-requirements RFC [12] is necessary reading for anyone designing or implementing an IP router. The RFC provides many years of collected wisdom on what one should and should not do when building a router.

Books on IPv6 are just starting to come out. The collection of essays edited by Bradner and Mankin [26] provides insight into the requirements and design decisions that resulted in the IPv6 protocols.

For general information on IPv6 protocols, see Huitema's book []. Chapter 2. Internet Routing Protocols In this chapter, we explore the Internet's dynamic routing protocols. Before getting to the routing protocols themselves, we first discuss the database that all routing protocols produce: the router's routing table. We end the chapter with a description of the two main routing technologies in use today: Distance Vector and link state.

As the network changes—leased lines fail, new leased lines are provisioned, routers crash, and so on—the routing protocols continually reevaluate prefix reachability and the next hop to use for each prefix. The process of finding the new next hop after the network changes is called convergence. We prefer routing protocols that find the new next hop quickly, that is, protocols having a short convergence time.

However, for any routing protocol, as the size and complexity of the network increase, so does convergence time. A router's routing table instructs the router how to forward packets. Given a packet, the router performs a routing table lookup, using the packet's IP destination address as key. This lookup returns the best-matching routing table entry, which tells the router which interface to forward the packet out of and the IP address of the packet's next hop.

There is a separate routing table entry for each address prefix that the router knows about. Entries in the routing table are also commonly referred to as routes. For example, Figure 1.

The next hop of "self" for prefix Note that although there is a network segment with the prefix Similarly router G on the right of Figure 1. Table 2. The Routing Table of Figure 1. In our example, the entry for In our example, many destinations do not have a matching entry— If router C receives a packet addressed to any of these destinations, it simply throws the packet away and attempts to send an ICMP Destination Unreachable message back to the packet's source to inform it about the error.

In Table 2. This is not at all uncommon. In these cases, the entry with the longest prefix, One way that multiple matches can occur is when the provider addressing model is being used. An organization takes a range of addresses from its Internet Service Provider and later on changes providers but does not wish to change addresses. The new ISP then ends up advertising a more specific route for a piece of the old provider's address space this is now officially discouraged by the address lending policy, which would instead force the organization to renumber when changing providers; see [].

Many routers have a default route in their routing table. The default route matches every destination, although it is overridden by all more specific prefixes. For example, suppose that an organization's intranet has one router attaching itself to the public Internet.

All of the organization's other routers can then use a default route pointing to the Internet connection rather than knowing about all of the public Internet's routes.

Each router has a different routing table, reflecting its unique position within the Internet. From router to router, not only do the next hops of routing table entries change, but even the prefixes that each router knows can be different, as addresses are aggregated into large prefixes. In Figure 1. Routers at the edge of the Internet may rely heavily on the default routing table entry, with only a few hundred or more specific entries in their routing table.

Core routers in the Internet, however, have upwards of 45, entries. These routers, which do not use a default route, are said to hold the full Internet routing table. The size trend of the full Internet routing table is shown in Figure 2. Figure 2. Size increases in the Internet's routing tables logarithmic scale. In our example, we have been assuming that router C is building its routing table through the use of dynamic routing protocols—the aggregates Dynamic routing protocols are certainly the norm, although they do not need to be used.

Instead routing table entries can be explicitly configured, called static routing, by a network operator.

For example, to install the route to Running an entire network via static routing is too difficult to manage, requiring modification of static routes as the network changes or even during network failures. In our example, if the link between routers C and D fails, the operator would have to tell router C to route packets destined to However, static routes are still used today in the Internet to augment dynamic routing. For example, two organizations may not trust each other enough to run dynamic routing at the interorganization boundary, relying instead on a set of configured static routes.

Therefore makers of routers try to arrange their routers' routing tables so that the best match operation can be performed as quickly as possible. A common routing table arrangement is a Patricia tree see [] and [] —a special kind of radix tree that minimizes bit comparisons and, when used as a routing table, requires only a single mask-and-match operation.

These trees are binary trees, whereby the tree traversal depends on a sequence of single-bit comparisons in the key, the destination IP address. A Patricia tree that might be used to implement the lookup for the routing table in Table 2. Suppose that the router is trying to route a packet to the destination The router starts at the top of the Patricia tree, testing bit 13 in the destination address bits are numbered starting at 0 for the most significant bit of the address.

Since this bit is 0, the router branches left, testing in sequence bits 14 which is a 1 , 15 a 0 and 21 a 1. This ends up at the entry specifying no bit comparison, so the tree traversal stops; traversal would also stop if the new bit to test were less than or equal to the last bit tested.

When the traversal stops, the destination is compared to the prefix in the entry to see whether there is a match.

In our example, The router must then check for matches against shorter prefixes of Patricia-tree implementation of routing table lookup. With a routing table containing 45, entries, the router will perform on average 16 bit comparisons for each lookup. However, the performance of Patricia is somewhat data dependent. With a particularly unfortunate collection of prefixes in the routing table, the lookup of certain addresses can take as many as 32 bit comparisons, one for each bit of the destination IP address.

For example, the OSPF implementation in the companion book to this book uses a balanced binary tree see []. Another way to speed up the routing table lookup is to try to avoid it entirely.

The routing table lookup provides the next hop for a given IP destination. Some routers cache this IP destination-to-next-hop association in a separate database that is consulted before the routing table lookup one might say as the front end to the routing table.

Finding a particular destination in this database is easier because you are doing an exact match instead of the more expensive best-match operation of the routing table. As a concrete example, this front-end database might be organized as a hash table see []. If the hash function were the sum of the third and fourth bytes of the IP destination, a couple of buckets within the hash table might look as in Figure 2. Now if the router sees any of these destinations again a cache hit , their lookup will be very quick.

Packets to new destinations will be slower, however, because the cost of a failed hash lookup will have to be added to the normal routing table lookup.

Hash-table front end to a routing table. Front-end caches to the routing table can work well at the edge of the Internet or within organizations. However, cache schemes do not seem to work well in the Internet's core. The large number of packet destinations seen by the core routers can cause caches to overflow or for their lookup to become slower than the routing table lookup itself. For example, cache schemes are not really a win when the hash bucket size—the number of destinations that hash to the same value—starts getting large.

Also, the frequent routing changes seen in the core routers can force them to invalidate their caches frequently, leading to a small number of cache hits. Although IP addressing has been around for more than 20 years, new routing table lookup algorithms are still being developed in attempts to build ever faster routers.

Each AS consists of a collection of routers under the control of a single administrative entity—for example, all the routers belonging to a particular Internet Service Provider, corporation, or university. The collection of ASs is organized in a rough hierarchical fashion.

The closer to the top of the hierarchy—the core of the Internet—the more routes appear in the AS. At the same time, the individual prefixes within the routers' routing tables get shorter. The ASs at the core of the Internet carry the complete routing table, currently 45, routes, and do not use a default route they are in the so-called default-free zone.

All other ASs use a default route, pointing up the hierarchy, enabling them to carry only a subset of the Internet's routes. This arrangement of ASs is pictured in Figure 2. Organization of the Internet into Autonomous Systems. Solid lines indicate peering relationships. The arrows indicate the direction of the default route.

The network operators that configure and manage the interconnection of ISPs have a language all their own. When two providers connect, they usually establish a peering agreement. If the two providers are at the same level of the hierarchy, this is simply an agreement to exchange routing information.

However, when one AS is lower in the hierarchy downstream , this AS is sometimes entering into a customer relationship with the upstream provider. This means that the upstream provider will advertise the downstream's addresses to the rest of the Internet and will forward the downstream's packets to other providers and their customers as appropriate—that is, the upstream provider provides transit for the downstream provider.

Internet prefixes are now assigned to achieve the best aggregation under CIDR. Providers that are large enough can get assigned their own address prefixes, also referred to as CIDR blocks. Other smaller providers and their customers must use addresses from the CIDR blocks of their upstream provider s.

The identity of the ASs at the Internet's core has changed over the years. Dozens of providers may connect at a single exchange point. The ISPs connecting to the exchange, and those they are peering with, is often public knowledge.

Some exchanges also supply a specially instrumented router to ease the distribution of routing information between connected providers. Instead of each provider establishing a routing protocol session with every other, a provider instead establishes a single session with the Route Server. The Route Server then redistributes the information learned to the other providers at the exchange.

Two providers may also peer directly over a private connection, such as a high-speed leased line or an ATM circuit.

This kind of private peering is becoming common between the top-level ISPs making up the Internet core. Free download Unlit Star. Book and CD. Free download Visor! Free download Welcome To Home-Based Business Computing. Free Ebook An Introduction to Python.

Free Ebook Blog, Inc. Free Ebook Breakers Book 1. Free Ebook Compiling with Continuations. Free Ebook Congo. Free Ebook Delphi Handbook. Free Ebook Download Akka Concurrency. Programming is Easy Book 2. Free Ebook Download Fashion 2. Free Ebook Download Programming Python. Free Ebook Download Windows 8. Navy's Elite Seal Team Two. Free Ebook iPod touch Made Simple. Free Ebook Matplotlib Plotting Cookbook.

Free Ebook Metrowerks Codewarrior Programming. Free Ebook Online E-Moderating. Free Ebook Online mindmemo Lernposter. Free Ebook Online My Droid. Free Ebook Online Operations Management.

Free Ebook Online Salesforce. Free Ebook Online Upgrading Your Modem's Internet Guide for Seniors. The book also offers side-by-side comparisons of all the unicast and multicast routing protocols currently in use in the Internet. You will come away from this book with a sophisticated understanding of Internet routing and of the OSPF protocol in particular. Moreover, the book's practical focus will enable you to put this deeper understanding to work in your network environment.

Computers - Networking. ISBN Your tags:. Send-to-Kindle or Email Please login to your account first Need help? Please read our short guide how to send a book to Kindle. The file will be sent to your email address. It may take up to minutes before you receive it. The file will be sent to your Kindle account.