8.5. Additional Routing Protocols for IPv6
The final section of this chapter is focused on two additional routing protocols, IS-IS and EIGRP. Both protocols have quite a broad implementation base with IPv4, and migrations to IPv6 are expected. This chapter provides only an overview for these protocols.
At the end of this chapter, multicast routing is discussed briefly to complete the routing picture.
8.5.1. Routing IPv6 with IS-IS
IPv6 support with IS-IS is defined in draft-ietf-isis-ipv6-05.txt. This document is based on the specifications for integrated IS-IS as defined in RFC 1195. Without in-depth knowledge of integrated IS-IS, the IPv6 extension cannot be understood.
184.108.40.206. Integrated IS-IS
Unlike the previous routing protocol discussions, this section gives only a very brief overview of integrated IS-IS. IS-IS originally defines the exchange of routing information between Intermediate Systems (ISes, otherwise known as routers) for the OSI network layer protocols CLNP (connectionless network protocol) and CONP (connection-oriented network protocol). Other protocols use other routing protocols. Having separate routing protocols for each network layer is sometimes referred to as "ships in the night." Each routing protocol uses (or maybe wastes) its own resources, such as CPU and memory. A misbehaving routing protocol can destabilize another routing protocol.
An integrated routing protocol uses resources efficiently and is more stable, as it introduces a single process for routing control. That is the idea behind integrated IS-IS (i/IS-IS), in which the routing protocol has been adapted to carry concurrently routing information for the OSI network protocols and for IPv4. This is achieved by introducing variable-length data fields in the form <Type, Length, Value> (TLVs). Each network layer protocol can use the TLVs according to its addressing syntax. Each supported network layer protocol is specified by its Network Layer Protocol Identifier (NLPID), assigned by ISO.
Integrated IS-IS is an interior routing protocol based on link state updates. OSPF and IS-IS have many similarities: if you know one, the other is easy to grasp. We have already explained OSPF in detail, so we can briefly compare OSPF features with i/IS-IS. OSPF runs within an AS, and i/IS-IS runs within a routing domain. An i/IS-IS routing domain can be further split into multiple areas with a common central area. Routers within the central area are called Level 2 intermediate systems, or L2 routers. Routers in all other areas are called Level 1 intermediate systems or L1 routers. In most cases, L2 routers are L1 routers as well, such as ABR in OSPF. Each area is identified by the first 13 bytes of the ISO NSAP address assigned to the router. Routers keep adjacencies with each other, initiated and maintained by IS-IS Hello packets. Routers can become adjacent only if they are on the same level. Once they have become adjacent, they advertise level 1 or level 2 Link State PDU (L1-LSP or L2-LSP). L1 routers originate L1-LSP advertising their local addresses. L2 routers originate L2-LSP advertising their local address, routes learned from directly attached areas, and external routes. Only L2 routers can advertise routes external to the routing domain, called ASBR in OSPF. To synchronize and acknowledge the most recent LSP, the routers use Sequence Number PDU (SNP), again for level 1 and level 2. An L1 router knows L1 routes in its area by calculating an SPF tree to all destinations. L1 routers have no knowledge about any route outside their own area. Anything outside the area is reached via the closest L2 router. L2 routers, however, know all the internal and external routes to the routing domain. In addition, transit links are handled in i/IS-IS by implementing pseudonodes. The designated router of a transit link originates LSP on behalf of the pseudonode.
220.127.116.11. Routing IPv6 with IS-IS
Integrated IS-IS provides for the inclusion of variable-length fields (TLVs) in all IS-IS packets (Hello, LSP, and SNP). Relevant addressing information is stored in TLV fields. Hello packets and LSP packets carry a field specifying the network layer protocols. Each supported network layer protocol is specified by its NLPID, assigned by ISO. The value of the IPv6 NLPID is 142 (0x8E).
The Internet draft proposes two new TLVs for IPv6. They are described in the following list. Remember that this is only a draft document; some of this information may change, or additional information may be added. However, interoperating implementations already exist.
8.5.2. EIGRP for IPv6
Enhanced Interior Gateway Protocol (EIGRP) is an interior routing protocol (IGP) developed by Cisco Systems, Inc. It runs in an autonomous system called EIGRP domain. The main objective of EIGRP was to eliminate limitations of a distance vector routing protocol (see the discussion of RIP, earlier in this chapter) without developing another link state based protocol. Link state protocols with their complexity and database demand higher CPU performance and more memory of the routers. EIGRP was therefore developed as a hybrid protocol combining the best of both worlds. It uses a so-called Diffuse Update Algorithm (DUAL) to calculate the routes. It allows for fast convergence and ensures loop-free operations at every instant throughout route computation. Only routers affected by a change are involved.
EIGRP has the following components: protocol dependent modules, EIGRP message protocol and its packet types, neighbor relations, and the actual algorithm (DUAL). A specialty of EIGRP is its calculation of the path costs. A mixed metric is being used. It takes the following characteristics into consideration: bandwidth, delay, load, and reliability. These parameters can be configured on each EIGRP interface. A complex formula that includes a weight factor for each parameter produces a metric for each interface. The metrics are added to get the overall path costs.
18.104.22.168. Protocol-dependent modules
EIGRP has always supported different network layer protocols. For each network layer protocol, EIGRP runs a separate instance in a "ships in the night" fashion. There are modules for IPv4, IPX, Appletalk, and now also for IPv6. The basic functions for all protocols are the same. The semantics of the the different protocols are implemented using protocol-dependent TLVs (type, length, value) fields. The TLVs will be explained further later in the chapter.
22.214.171.124. EIGRP packet types
EIGRP packets are directly encapsulated in IPv6 specified by protocol number 88 in the Next Header field of the IPv6 header. EIGRP introduces a mechanism for reliable packet delivery. It guarantees that EIGRP packets arrive in the right sequence. The EIGRP header contains a sequence and acknowledgement field to accommodate this reliable transport mechanism. EIGRP packets can be sent as either a unicast packet to a particular router or as a multicast packet to multiple routers. The multicast IPv6 address in the latter case is set to FF02::A. Acknowledgments are always sent as unicast. For efficiency reasons, reliable transport is provided only when necessary. Certain messages do not use reliable transport. In this case, the sequence number is not used and no acknowledgments are sent.
EIGRP distinguishes between the following packet types:
With reliable transport, unacknowledged packets are sent againin this case, always as a unicast packet. After 16 unsuccessful retries, the neighbor is declared dead. The waiting time for an acknowledgment depends on the transmission type (multicast or unicast). With multicast, the timer is called multicast flow timer; with unicast, it is called retransmission time-out. Both depend on the overall smooth round trip time (SRTT). The SRTT is the average time in milliseconds for a packet to travel to the neighbor and back.
126.96.36.199. EIGRP neighbors
Unlike RIP, which sends periodic updates, EIGRP sends only changes. It is of utmost importance to discover all neighbors and to rediscover them in case of temporary failures. Hello packets ensure discovery and rediscovery. They are sent at periodic intervals out of all interfaces configured for EIGRP. The Hello interval depends on the bandwidth of the network. Normally it is set to 5 seconds for LAN-like bandwidth and 60 sec for WAN-like bandwidth. The EIGRP router expects periodic Hello packets from its neighbors as well and keeps a neighbor table. This table keeps certain information about each neighbor, including up time and hold time. The hold time defines a maximum waiting time for a valid packet from this neighbor. If this time expires, the neighbor is declared unreachable and the DUAL process is informed about the loss of this neighbor. The default value of the hold time is three times the Hello time. If a packet from the neighbor arrives, the hold time is reset.
A neighbor can send a goodbye message to indicate its shutdown. In this case, the routers don't have to wait for the hold time to expire.
188.8.131.52. The Diffuse Update Algorithm (DUAL)
DUAL handles all route computations in EIGRP. Its main objective is to maintain a table of loop-free paths to every route. If a loop-free path is not found in the table, a route recomputation must occur, during which DUAL queries its neighbors, who, in turn, may query their neighbors. This characteristic gives the algorithm its name, as in "diffuse update." E. W. Dijkstra and C. S. Scholten first proposed the algorithm. The most important contribution to DUAL, however, came from J. J. Garcia-Luna-Aceves. DUAL is based on a few fundamental principles. The reliable transport mechanism of EIGRP enables the fulfillment of these principles. These principles are as follows:
DUAL keeps a topology table. The topology table keeps not only the least cost instance of a route (as does RIP, for example), but also all feasible instances of a route. However, only the least cost routes are copied to the routing table.
For DUAL to work properly, the neighbor connections must be established. These connections are being used for the exchange of routing information. During the initial setup of the neighbor connection, all known EIGRP routes are passed to each other using one or more update packets. The routing information received by the neighbors contains, among other information, the reported distance RD (metric) for each route, indicating the path cost from the neighbor to the destination. The receiving router calculates the total distance for each route by adding the metric of the receiving interface to the RD. The least cost instance (called feasible distance, or FD) of each route is entered into the EIGRP topology table and is named the successor. In case a particular route has more than one instance (i.e., has been received from several neighbors), the routes with an RD smaller than the FD are added to the topology table as well. They are called feasible successors (FS). This situation is called feasibility condition (FC). The feasibility condition is a test for a loop-free route. If the FC is met, the neighbor advertising the RD must have a path to the destination not through this router. If the neighbor would route through this router, the RD would have to be higher than the FD.
Each route in the topology table contains the following information:
If there is a change (e.g., an update from a neighbor, a change in the metric of a directly connected interface, or a transition in the state of a directly connected interface, such as a shut down), the router must reevaluate the topology table. DUAL first tries to find a feasible successor locally. After recalculating the metrics, it checks for feasible successors. If a feasible successor is found, the successor is determined. If the FD has changed, it will be replaced and an update is sent to all neighbors. During this phase, the route has stayed in passive state, indicating that the route is good. If a feasible successor cannot be found in the local topology table, the route will transition to the active state. During the active state, the route is "on hold" and no changes are allowed. The router sends queries to its neighbors to find feasible successors. If the neighbor doesn't have a feasible successor, it forwards the query to its neighbors. The query thus propagates (diffuses) until a reply is received. DUAL has only finished its calculations when all queries have been answered. If no feasible successor has been found, the route is set to unreachable. Otherwise, the successor is determined and the route is put back to passive. To avoid being stuck in active state, a waiting timer is introduced. If a neighbor does not reply within this time, the reply is assumed to be "no successor found" (the route is unreachable).
A complex finite state machine for DUAL governs the query and reply exchanges, and it is not explained further in this chapter.
184.108.40.206. EIGRP packet format
All EIGRP packets have a standard 20-byte EIGRP header consisting of the following fields:
The EIGRP Header is followed by one or more TLV fields. Each TLV contains a type field (2 bytes), a length field (2 bytes), and finally the actual value or data field. The value field has a length specified in the length field. There are two categories of TLV:
220.127.116.11. EIGRP support for IPv6
At the time of this writing, Cisco Systems has not yet officially released EIGRP for IPv6. It is currently available only on test releases. There will be an additional EIGRP protocol module for IPv6, along with the IPv6-specific TLVs.
8.5.3. Multicast Routing for IPv6
Until now, we have looked only at unicast routing. This section briefly outlines the general basics of multicast routing and how IPv6 makes use of it.
Multicast routing forwards IPv6 datagrams addressed to a multicast IPv6 address, from now on called multicast packets . Multicast packets are used for data streams originated from a source (called a sender) to a group of receivers. Each group is addressed using a specific multicast IPv6 address. Some of these addresses can be officially registered. With multicast, routing data packets do not have to be sent individually to each receiver. A single multicast packet can reach all receivers and therefore reduces the number of packets significantly, especially with a large number of receivers. Each multicast data stream is uniquely identified by its Source address (IPv6 unicast address) and its group or multicast IPv6 address. Multicast routing ensures packet delivery from the sender to all receivers. It must be enabled on all routers between the sender and the receivers. The router receives the multicast packet on the receiving interface and forwards it out over all other interfaces with registered receivers. The tricky part is to avoid duplication of multicast packets and the process of receivers joining a multicast group. Next I explain how it works.
For each multicast data stream, only a single receiving interface is allowed on any given router. If a data stream were accepted over multiple interfaces, packet duplication would occur. The receiving interface is selected as the interface having the least cost path back to the sender. This ensures that the data has reached this router over the shortest path. In order to determine the least cost path, the router examines the local unicast routing table and looks up the route to the sender. The next hop interface of this route will be the receiving interface, also called the reverse path forwarding (RPF) interface. If multiple least cost paths exist, an arbitration mechanism ensures that only one RPF interface is selected. Each incoming multicast datagram is now checked for whether it has arrived over its RPF interface. This is called the RPF check. Datagrams failing the RPF check are rejected. The first part of the puzzle is now solved. But how does the router know where the receivers are? It could simply not care and forward the multicast packets out every interface except the RPF interface, but this would not be very efficient. To avoid this flooding of packets, receiver registration is introduced. Receivers wanting to receive a multicast data stream register themselves with the local router using the Multicast Listener Discovery (MLD) protocol. These routers keep a list of registered receivers for each multicast group, or in case of a more granular registration, for each data stream (sender/group). They also add the outgoing interface to reach the receivers to this list. This information must now be passed to other multicast routers using a multicast routing protocol. The most important multicast routing protocol in use today is called PIM (protocol independent multicast), which is specified in RFC 2362. PIM basically distributes information about multicast groups and their receivers. Many multicast features requiring special IPv6 consideration are still in draft.
As just mentioned, MLD defines mechanisms for end-systems to join and leave multicast groups or multicast data streams (sender/group).
Now we have all the information within a multicast routing table. Each entry represents a multicast data stream defined by its sender address and the multicast group address. Each maintains the RPF interface and all outgoing interfaces (where there are receivers).
This was a brief introduction into multicast functionality. To fully understand multicast routing, the protocols MLD and PIM should be studied in-depth.