HTTP/1.1 200 OK Date: Mon, 08 Apr 2002 23:59:28 GMT Server: Apache/1.3.20 (Unix) Last-Modified: Tue, 17 Mar 1998 16:32:00 GMT ETag: "2e6e04-3d95f-350ea580" Accept-Ranges: bytes Content-Length: 252255 Connection: close Content-Type: text/plain INTERNET DRAFT Wolfgang Fritsche Expires May 1998 IABG Hartmut Seifert IABG 3 November 1997 Dynamical routing (unicast and multicast)for the IPv6 protocol Status of this Memo This document is an Internet-Draft. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet- Drafts as reference material or to cite them other than as "work in progress." To view the entire list of current Internet-Drafts, please check the "1id-abstracts.txt" listing contained in the Internet-Drafts Shadow Directories on ftp.is.co.za (Africa), ftp.nordu.net (Europe), munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or ftp.isi.edu (US West Coast). Abstract Future communication networks will be based more and more on a dynamically changing network topology. Therefore it is advantageous, to have routing mechanisms, which will dynamically adapt their routing decisions to these topology changes. This document describes a set of network protocols, which realize such a dynamical routing of unicast and multicast packets within communication networks based on IPv6. All used routing algorithms will be immediately executed at the occurrence of any topology changes and will therefore have already complete routing information at the receipt of data packets. For the unicasting the Shortest Path First (SPF) routing algorithm has be chosen. This algorithm calculates the shortest, and therefore the optimal routing paths within the routing area, by which it is sufficient for a router, to compute a single routing tree for the whole area. For the multicasting the Minimum Spanning Tree (MST) routing algorithm has been chosen. This distributed algorithm prevents the occurrence of endless routing loops, offers for distributed Address Groups nearly optimal results in saving network bandwidth, and needs also only a single routing tree for the whole area. This version 02 of the draft mainly corrects some minor errors of version 01. Fritsche, Seifert Expires May 1998 [Page 1]INTERNET DRAFT Dynamical routing for IPv6 November 1997 Table of Contents 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . 4 2 Terminology . . . . . . . . . . . . . . . . . . . . . . . . 8 3 Neighbour Discovery for IPv6 . . . . . . . . . . . . . . . . 9 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . 9 3.2 ICMPv6 Neighbour Discovery message formats . . . . . . . . 10 3.2.1 Router Solicitation Message Format . . . . . . . . . . . . 10 3.2.2 Router Advertisement Message Format . . . . . . . . . . . 11 3.2.3 Neighbour Solicitation Message Format . . . . . . . . . . 14 3.2.4 Host Advertisement Message Format . . . . . . . . . . . . 15 3.2.5 Redirect Message Format . . . . . . . . . . . . . . . . . 17 3.2.6 Options Formats . . . . . . . . . . . . . . . . . . . . . 18 3.2.6.1 Source / Target Link-Layer Address . . . . . . . . . . . . 19 3.2.6.2 Prefix Information . . . . . . . . . . . . . . . . . . . . 20 3.2.6.3 Redirected Header . . . . . . . . . . . . . . . . . . . . 21 3.2.6.4 MTU . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.2.6.5 LSA information . . . . . . . . . . . . . . . . . . . . . 23 3.3 Validation of the used ICMPv6 messages . . . . . . . . . . 23 3.3.1 Validation of Router Solicitations . . . . . . . . . . . . 24 3.3.2 Validation of Router Advertisements . . . . . . . . . . . 24 3.3.3 Validation of Neighbour Solicitations . . . . . . . . . . 25 3.3.4 Validation of Host Advertisements . . . . . . . . . . . . 25 3.3.5 Validation of Redirect Messages . . . . . . . . . . . . . 26 3.4 Functions of the Neighbour Discovery . . . . . . . . . . . 27 3.4.1 Router Discovery . . . . . . . . . . . . . . . . . . . . . 27 3.4.2 Stateless Address Autoconfiguration . . . . . . . . . . . 27 3.4.3 Neighbour Detection . . . . . . . . . . . . . . . . . . . 29 3.4.4 Neighbour Unreachability Detection . . . . . . . . . . . . 30 3.4.5 Redirect . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.5 Neighbour Discovery on non-multicast-capable links . . . . 31 4 Dynamical routing of unicast packets in IPv6 . . . . . . . 33 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . 33 4.2 ICMPv6 Routing Information message formats . . . . . . . . 35 4.2.1 Link State Advertisement Message Format . . . . . . . . . 35 4.2.2 Options Formats . . . . . . . . . . . . . . . . . . . . . 37 4.2.2.1 Router Neighbours . . . . . . . . . . . . . . . . . . . . 38 4.2.2.2 Host Neighbours . . . . . . . . . . . . . . . . . . . . . 39 4.3 Validation of the used ICMPv6 messages . . . . . . . . . . 40 4.3.1 Validation of Link State Advertisements . . . . . . . . . 40 4.4 Functions for the Routing Information distribution . . . . 41 4.4.1 Sending Link State Advertisements . . . . . . . . . . . . 41 4.4.2 Receiving Link State Advertisements . . . . . . . . . . . 43 4.4.3 Ageing of Routing Information . . . . . . . . . . . . . . . 45 4.5 Routing Information on non-multicast-capable links . . . . 45 4.6 Unicast Routing Algorithm . . . . . . . . . . . . . . . . 47 4.6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . 47 4.6.2 Overview of the algorithm . . . . . . . . . . . . . . . . 48 4.6.3 Steps of the algorithm . . . . . . . . . . . . . . . . . . 49 5 Dynamical routing of multicast packets in IPv6 . . . . . . 51 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . 51 5.2 Functions needed for multicasting in IPv6 . . . . . . . . 53 Fritsche, Seifert Expires May 1998 [Page 2]INTERNET DRAFT Dynamical routing for IPv6 November 1997 5.2.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . 53 5.2.2 Create Address Group Function . . . . . . . . . . . . . . 53 5.2.2.1 Create Address Group Function for hosts . . . . . . . . . 53 5.2.2.2 Create Address Group Function for routers . . . . . . . . 54 5.2.3 Modify Address Group Function . . . . . . . . . . . . . . 54 5.2.3.1 Modify Address Group Function for hosts . . . . . . . . . 55 5.2.3.2 Modify Address Group Function for routers . . . . . . . . 55 5.2.4 Delete Address Group Function . . . . . . . . . . . . . . 55 5.2.4.1 Delete Address Group Function for hosts . . . . . . . . . 56 5.2.4.2 Delete Address Group Function for routers . . . . . . . . 56 5.2.5 Join Address Group Function . . . . . . . . . . . . . . . 57 5.2.5.1 Join Address Group Function for hosts . . . . . . . . . . 57 5.2.5.2 Join Address Group Function for routers . . . . . . . . . 57 5.2.6 Leave Address Group Function . . . . . . . . . . . . . . . 58 5.2.6.1 Leave Address Group Function for hosts . . . . . . . . . . 58 5.2.6.2 Leave Address Group Function for routers . . . . . . . . . 59 5.2.7 Record Host Group Membership Query Function . . . . . . . 59 5.2.8 Record Router Group Membership Report Function . . . . . . 60 5.2.9 Record Router Group Distribution Message Function . . . . 61 5.2.10 Summary . . . . . . . . . . . . . . . . . . . . . . . . . 62 5.3 ICMPv6 Informational Group Messages . . . . . . . . . . . 64 5.3.1 Host Group Membership Query . . . . . . . . . . . . . . . 64 5.3.2 Router Group Membership Report . . . . . . . . . . . . . . 66 5.3.3 Router Group Distribution Message . . . . . . . . . . . . 68 5.4 Multicast Routing Algorithm . . . . . . . . . . . . . . . 70 5.4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . 70 5.4.2 Description of the algorithm . . . . . . . . . . . . . . . 71 5.4.2.1 Tiebreaker for unequivocal link metrics . . . . . . . . . 71 5.4.2.2 Overview . . . . . . . . . . . . . . . . . . . . . . . . . 72 5.4.2.3 Steps of the algorithm . . . . . . . . . . . . . . . . . . 73 5.4.3 Time of the algorithm execution . . . . . . . . . . . . . 74 5.4.4 Complexity of the algorithm . . . . . . . . . . . . . . . 74 5.4.5 Resume . . . . . . . . . . . . . . . . . . . . . . . . . . 75 5.4.6 Example . . . . . . . . . . . . . . . . . . . . . . . . . 75 5.5 Routing of packets addressed to a group . . . . . . . . . 78 5.5.1 Acceptance of multicast packets . . . . . . . . . . . . . 79 5.5.2 Determination of the forwarding adjacencies . . . . . . . 79 5.5.3 Forwarding of multicast packets . . . . . . . . . . . . . 81 6 Routing beyond the routing area . . . . . . . . . . . . . 82 6.1 Unicast routing beyond the routing area . . . . . . . . . 82 6.2 Multicast routing beyond the multicast routing area . . . 84 7 Quality of service aspects in dynamical routing . . . . . 86 8 Security Considerations . . . . . . . . . . . . . . . . . 87 9 References . . . . . . . . . . . . . . . . . . . . . . . . 87 10 Author's Addresses . . . . . . . . . . . . . . . . . . . . 88 Fritsche, Seifert Expires May 1998 [Page 3]INTERNET DRAFT Dynamical routing for IPv6 November 1997 1 Introduction Future communication networks will change more and more from a static topology to a dynamically changing topology. This effect becomes obviously by considering the following examples: - In the last time the interconnection of different network architectures has a high significance in the modern world of communication. To these architectures also belong radio networks, which enable the communication with mobile users and routers. Since these users and routers will permanently change their geographical location, the network topology will also change. - Even on non-radio networks there is often the demand to disconnect from the communication network and to access it again at a different location. - Since the number of communication network users is rapidly increasing, it is necessary to permanently adapt the network architecture to the newly arising demands. Examples would be the adding of network servers and more efficiently routers, the connection of new network parts and also the connection of new network users itself. - It is obviously, that not all parts of a communication network, for example routers and especially hosts, are available the whole time. The increase of networks with changing topologies causes a more difficult administration of these networks. It is necessary, to be always informed, which resources and users are available at a certain point of time, and at which access point of the network they can be reached. To deal with these high demands of a dynamically changing network topology requires a dynamical mechanism of detecting any changes within the network, and also dynamical routing algorithms, which make use of the collected topology information. The intention of this document is to specify a complete set of network protocols, which execute the dynamical routing administration of communication networks running IPv6. In more detail it describes mechanisms how to collect and dynamically update information about the own environment within the network, how to distribute this information within the routing area and how to use it for dynamical routing algorithms, which can be applied especially for the intra- domain-routing of IPv6 data packets destined to an unicast or multicast IPv6 network address residing within the routing area. Since routing algorithms always need certain information about the network topology for the calculation of their routes, the problem of the dynamical collection of this information has to be solved first. For this purpose this document basically uses the functionality defined RFC 1970 'Neighbor Discovery for IP Version 6 (IPv6)' [3] and performs modifications where necessary. In more detail between neighbouring routers and hosts a kind of life messages has to be exchanged periodically. By receiving these life messages each node is informed about all its reachable neighbours. Missing life messages of certain neighbours enables a node to dynamically Fritsche, Seifert Expires May 1998 [Page 4]INTERNET DRAFT Dynamical routing for IPv6 November 1997 recognize the unreachability of these neighbours. The time interval for the periodical retransmission of the life messages has to be chosen very carefully. A too short interval produces a lot of control information on the network, a too long interval decreases the dynamic of the detection of any changes. The Neighbour Discovery mechanism is specified in chapter 3 of this document. The life messages mentioned above are only exchanged between neighbouring nodes, that is using this mechanism enables each node to collect information about all its reachable neighbouring nodes on all its connected network links. Since for the execution of routing algorithms routers have to be informed about the topology of the whole routing area, and not only about the topology in their own environment, it is necessary, to distribute the local information collected in the Neighbour Discovery mechanism among all routers within the routing area. For this purpose all routers in one area periodically exchange their local information using so called Link State Advertisements. For choosing the time interval for the periodical retransmission of these advertisements also a compromise between dynamic and costs has to be found. The distribution of the locally collected routing information is closer described in chapter 4. Using the Neighbour Discovery mechanism and the distribution of the collected information within the routing area enables now each router to build up a detailed picture of the network topology within the own routing area. Based on this information the routers can execute suitable routing algorithms. The hosts have only the detailed information about their own local environment, that is about all reachable neighbouring nodes, but this information is sufficient for hosts to locate a neighbouring router, which will route their data packets. Because of the periodical exchanged routing information the dynamical routing mechanism specified in this document is especially suitable for intra-domain-routing within domains, which show the characteristics of a dynamical changing network topology. With some minor modifications the mechanisms specified herein can also be used for inter-domain-routing. Chapter 6 shortly discusses these aspects. Having solved the problem of the collection and distribution of the information about the local environment this document specifies the use of it within dynamical routing algorithms. Since the routing of data packets destined for unicast and multicast addresses have different demands to the routing algorithm, each router has to run an own algorithm for unicasting and multicasting. The results of these both algorithms are stored in the routers unicast and multicast forwarding database. If a router receives an IPv6 data packet, it first checks by examining the destination address, if the destination is an unicast or a multicast address. After this check it looks up the next hop for the packet in the respective forwarding database and forwards the packet. Fritsche, Seifert Expires May 1998 [Page 5]INTERNET DRAFT Dynamical routing for IPv6 November 1997 For the unicast routing algorithm this document specifies an implementation of Dijkstra's Shortest Path First (SPF) algorithm. Executing this algorithm each router constructs a routing tree with itself as root and all reachable nodes within the routing area as leaves. This algorithm has be chosen, since - routing along the SPF routing tree guarantees, that each node within the routing area will be reached on the shortest possible way, that is an optimal routing is performed, - routing along the SPF routing tree guarantees, that no endless routing loops will occur, - it is sufficient for routers to construct a single routing tree for the whole routing area, what means less time has to be spent for the calculation, and - it can be run immediately at the occurrence of new information about the network topology, that is at the receipt of data packets the algorithm is already finished and its results can be used for routing the packets without any delay. A closer specification of the unicast routing algorithm is contained in chapter 4. Before having a more detailed look to a suitable routing algorithm for multicasting, the principle of Address Groups shall be shortly explained. Within the routing area more nodes can be summarized within an Address Group. Each of these Address Groups can be identified by a different multicast IPv6 address, that is data packets addressed to all members of such a group have to use the multicast address as destination address in the IPv6 header. To execute a proper routing of multicast packets, the information about the composition of such Address Groups has to be distributed among all router within the routing area. Since it is allowed for nodes to join or to leave Address Groups, also this Address Group modification information has to be dynamically distributed. To save as much network bandwidth as possible, the information about Address Groups is distributed by event, and not periodically, that is there is only information distributed, if there was really a modification. The dynamical generation, modification and deletion of such Address Groups is described in chapter 5 and makes some modifications to RFC 1885 'Internet Control Message Protocol (ICMPv6) for the Internet Protocol Version 6 (IPv6)'. The main intention of multicasting in this paper is the saving of often limited and expensive network bandwidth. The idea behind this is to send a data packet destined for a group of N receivers not N times as an unicast packet, but one time as a multicast packet. Each router, which receives such a multicast packet, shall examine, if it is necessary for reaching all receivers to send a copy of the packet on more links. On this way the packet is only transmitted on the network links from the source to all receivers and contrary to unicasting separately one packet to each receiver it is guaranteed, that on no link more than one copy of the packet is transmitted. Fritsche, Seifert Expires May 1998 [Page 6]INTERNET DRAFT Dynamical routing for IPv6 November 1997 The selection of a suitable algorithm, which generates a routing tree for multicast packets, is much more difficult than for unicasting. Using for example the SPF algorithm also for multicasting would demonstrable result in the occurrence of endless routing loops. It can be shown, that this loops will not occur, if each router in the routing area constructs an identical routing tree. The algorithm chosen in this document is the Minimum Spanning Tree (MST) routing algorithm, which contains all reachable nodes of the routing area. For the following reasons this algorithm is quite suitable for multicasting on networks with dynamical topology changes: - The MST avoids the occurrence of endless loops during the routing of multicast packets. - The MST algorithm needs for its routing tree calculation only the information, which is also used by the SPF algorithm, that is there is no additional control information to be distributed over the network. - The MST algorithm can be run immediately at the occurrence of new information about the network topology, that is at the receipt of data packets the algorithm is already finished and its results can be used for routing the packet without any delay. Other routing algorithms, like the Multicast Open Shortest Path First (MOSPF) algorithm start the tree calculation first at the occurrence of data packets. - The execution of the MST is distributed equally over the routing area, that is each router constructs independently the same MST. Therefore there are no routers with special functionality, like the group's core router in the Core Based Trees (CBT) multicasting or the rendezvous points in the Protocol Independent Multicasting (PIM). The disadvantage of those special routers are the difficulties for the election of them, and the problems occurring if such a special router breaks down. - The MST algorithm is a shared based tree algorithm, which also has the advantage that each router only has to construct a single routing tree for the whole routing area. This is much less expenditure as it is needed within source based tree algorithms, for example the MOSPF algorithm, where a separate routing tree is calculated for each (source ; Address Group) pair. - There are no periodical messages to be exchanged for keeping the forwarding information received from the calculation of the MST. For this purpose the CBT algorithm needs to exchange periodically the so called ECHO REQUEST messages, the Distance Vector Multicast Routing Protocol (DVMRP) algorithm has to send its periodical prune messages. - Multicast data packets are transmitted along the MST only on those links, which are absolutely necessary to reach all receivers. Within the (DVMRP) algorithm data packets to new multicast groups are flooded on all links until the occurrence of prune messages build up the multicast routing tree. Fritsche, Seifert Expires May 1998 [Page 7]INTERNET DRAFT Dynamical routing for IPv6 November 1997 2 Terminology IPv6 Internet Protocol Version 6. The detailed description of this protocol is contained in [1]. ICMPv6 Internet Message Control Protocol for the Internet Protocol Version 6. The detailed description of this protocol is contained in [2]. node A device that implements IP. router A node that forwards IP packets not explicitly addressed to itself. host Any node that is not a router. link A communication facility or medium over which nodes can communicate at the link layer, i.e., immediately below IP. Examples are Ethernets (simple or bridged), PPP links, Frame Relay, or ATM networks as well as internet (or higher) layer tunnels, such as tunnels over IPv4 or IPv6 itself. circuit Used as a synonym for link. interface A node's attachment to a link. neighbours Nodes attached to the same link. adjacencies Used as a synonym for neighbours. address An IP-layer identifier for an interface or a set of interfaces. In the latter case an address can be an IP-layer identifier for a single node. unicast address An identifier for a single interface or node. A packet sent to a unicast address is delivered to the interface or node identified by that address. multicast address An IP-layer identifier for a set of interfaces (typically belonging to different nodes) or nodes. A packet sent to a multicast address is delivered to all interfaces or nodes identified by that address. Address Group A set of interfaces or nodes belonging to a particular multicast address. packet An IP header plus payload. unicast packet A packet, which destination address is a unicast address. multicast packet A packet, which destination address is a multicast address. Fritsche, Seifert Expires May 1998 [Page 8]INTERNET DRAFT Dynamical routing for IPv6 November 1997 3 Neighbour Discovery for IPv6 3.1 Introduction Before executing a routing algorithm, the necessary information for this algorithm has to be collected by the router. This can be done in two main steps: - First each node has to use a mechanism to dynamically discover its own environment. This step is closer described in the remaining part of this chapter. - Second each router has to distribute the collected knowledge about its own environment to the other routers of the routing area. This enables each router to dynamically generate a clear picture of the present network structure and to localise all nodes connected to this network. This distribution is described in the next chapter. In order to react on changes in the network topology or in a single node's state the information listed above has to be updated dynamically. [3] contains already a proposal, how the nodes could collect information about their environment. This proposal would be sufficient for hosts, since the Router Advertisements specified in [3] are sent periodically to the multicast address of all nodes on a particular link. Using this advertisements each node can exactly determine, which router would be available at a certain point of time. Nevertheless a router could break down unforeseen without being able to inform the attached nodes about this event. In this case all of its neighbours will notice this by stopping receiving the periodical advertisements of this router. Using the routing algorithm of this proposal a similar possibility would be also advantageous for routers, that is host should also distribute periodical messages. For this purpose the Neighbour Advertisements in [3] are used as so called Host Advertisements, which are transmitted periodically to all nodes on a particular link. This enables routers to keep dynamically track of all neighbouring nodes, routers and hosts, connected to one of their attached links. This information about the local environment is then distributed by a router in so called Link State Advertisements (LSAs) to all other routers of the routing area. These other routers have to be able to assign a received LSA unequivocally to a single router. This can be done using the IPv6 address, on behalf of which the router has sent its LSAs. Since a router could easily have more IPv6 addresses assigned, there must be a way for its neighbouring routers to detect, which of these addresses it will use for LSAs. In the newly added option LSA information contained in Router Advertisements each router can inform its neighbours about the proper IPv6 address. Fritsche, Seifert Expires May 1998 [Page 9]INTERNET DRAFT Dynamical routing for IPv6 November 1997 These are the main modifications concerning the routing algorithm, which have been done in the Neighbour Discovery mechanism of [3]. The next section contains the detailed format of all used ICMPv6 packets. In 3.4 the modified Neighbour Discovering functions using these ICMPv6 packet are shortly summarized. For the detailed description [3] and [4] can often be used as reference, if no modification affects the respective functionality. The whole Neighbour Discovering mechanism is restricted to multicast-capable subnetworks, like IEEE 802 links. Section 3.5 discusses the possibilities of using a restricted mechanism on non-multicast- capable links, for example certain WAN links, without adding new functionality or ICMPv6 packet formats. 3.2 ICMPv6 Neighbour Discovery message formats 3.2.1 Router Solicitation Message Format Hosts send out Router Solicitations in order to prompt routers to generate Router Advertisements quickly. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +---------------+---------------+-------------------------------+ | Type | Code | Checksum | +---------------+---------------+-------------------------------+ | Reserved | +---------------------------------------------------------------+ | Options | IPv6 Fields: Source Address: An IPv6 address assigned to the sending interface, or the unspecified address, if no address is assigned to the sending interface. Destination Address: Typically the all-routers multicast address. Hop Limit: 255 Priority: 15 Authentication Header: If a Security Association for the IP Authentication Header exists between the source and the destination address, then the source shall include this header. ICMPv6 Fields: Type: 133 - Router Solicitation Message Code: 0 Checksum: The ICMPv6 checksum. See [2]. Reserved: This field is unused. It must be initialised to zero by the sender and must be ignored by Fritsche, Seifert Expires May 1998 [Page 10]INTERNET DRAFT Dynamical routing for IPv6 November 1997 the receiver. Valid Options: Source link-layer address: The link-layer address of the sender, if known. Future versions of this protocol may define new option types. Receivers must silently ignore any options they do not recognize and continue processing the message. 3.2.2 Router Advertisement Message Format Routers send out Router Advertisement messages periodically, in response to an other Router or Host Advertisement message generated by a newly detected node, or in the case, that a router expects some of its interface addresses becoming unreachable. Finally a Router Advertisement is sent in response to a Router or Neighbour Solicitation message. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +---------------+---------------+-------------------------------+ | Type | Code | Checksum | +---------------+-+-+-+---------+-------------------------------+ | Cur Hop Limit |M|O|S|Reserved | Router Lifetime | +---------------+-+-+-+---------+-------------------------------+ | Retrans Timer | +---------------------------------------------------------------+ | Holding Time | +---------------------------------------------------------------+ | Options | IPv6 Fields: Source Address: 128-bit IPv6 address of the originator of the packet. If all interfaces of the router have assigned one single IPv6 address, that is an address is not assigned to each interface, but to the router as whole, this address shall be used. Destination Address: If this message is sent periodically due to expiration of the local Router Advertisement transmission timer or in response to a Router or Neighbour Solicitation message containing the unspecified address as Source Address, this field contains the all-nodes multicast address. If it is sent in response to a previously received Router or Host Fritsche, Seifert Expires May 1998 [Page 11]INTERNET DRAFT Dynamical routing for IPv6 November 1997 Advertisement message or to a Router or Neighbour Solicitation message containing a unicast Source Address different from the unspecified address, this field contains the IPv6 address specified as Source Address in the respective message. Hop Limit: 255 Priority: 15 Authentication Header: If a Security Association for the IP Authentication Header exists between the source and the destination address, then the source shall include this header. ICMPv6 Fields: Type: 134 - Router Advertisement Message Code: 0 Checksum: The ICMPv6 checksum. See [2]. Cur Hop Limit: 8-bit unsigned integer. This field is examined only by hosts receiving this message. It specifies the default value that should be placed in the Hop Count field of the IPv6 header for outgoing IP packets. A value of zero means unspecified (by this router). M: 1-bit Managed address configuration flag. This bit is examined only by hosts receiving this message. When set, hosts use the administered (stateful) protocol for address autoconfiguration in addition to any addresses autoconfigured using stateless address autoconfiguration. The use of this flag is described in [4]. O: 1-bit Other stateful configuration flag. This bit is examined only by hosts receiving this message. When set, hosts use the administered (stateful) protocol for autoconfiguration of other (non-address) information. The use of this flag is described in [4]. S: Solicited Flag. When set, the S-bit indicates that the advertisement was sent in response to a Neighbour Solicitation. Reserved: A 6-bit unused field. It must be initialised to zero by the sender and must be ignored by the receiver. Router Lifetime: 16-bit unsigned integer. This field is examined only by hosts receiving this message and shall be interpreted as the lifetime associated with the default router in units of seconds. The maximum value corresponds to 18.2 hours. A lifetime of 0 indicates, that the router is not a default router and should not appear on the default router list. The Fritsche, Seifert Expires May 1998 [Page 12]INTERNET DRAFT Dynamical routing for IPv6 November 1997 router lifetime applies only to the router's usefulness as a default router; it does not apply to information contained in other message fields or options. Options that need limits for their information include their own lifetime fields. Retrans Timer: 32-bit unsigned integer. The time, in milliseconds, which shall be waited by hosts for example between retransmission of Neighbour Solicitation messages for Neighbour Unreachability Detection. This value is also used for separating the transmission of Neighbour Solicitation messages for the detection of duplicate addresses. A value of zero means unspecified (by this router). Holding Time: 32-bit unsigned integer. The time, in seconds, how long the router shall be seen as reachable by its connected neighbours, which have received this message. If during this period no next Router Advertisement message is received from the respective router, it shall be deleted from the adjacency databases of its neighbours. Therefore it is recommendable for routers, to set this value at least two times the value for the retransmission interval. In this case the loss of a single Router Advertisement message wouldn't cause the deletion of the router from its neighbour's adjacency databases. Valid Options: Source link-layer address: The link-layer address of the interface from which the Router Advertisement is sent. This is only used on link layers that have addresses. This option can, but shall not be omitted in messages sent in response to a previously received Neighbour Solicitation message, which is used for Neighbour Unreachability Detection. In all other cases this option must be present. MTU: Shall be sent on links that have a variable MTU. It may be also sent on other links. Prefix Information: These options specify the prefixes that are on-link and/or are used for address autoconfiguration. A router should include all its on-link prefixes (except the link- local prefix) so that multihomed hosts have complete prefix information about on-link destinations for the links to which they attach. If complete information is lacking, a Fritsche, Seifert Expires May 1998 [Page 13]INTERNET DRAFT Dynamical routing for IPv6 November 1997 multihomed host may not be able to chose the correct outgoing interface when sending traffic to its neighbours. LSA information: This option is examined only by routers receiving this message and specifies the IPv6 address, on behalf of which the router will generate Link State Advertisements. This option can be omitted only, if this IPv6 address is the same as the one used as Source Address for this packet. Future versions of this protocol may define new option types. Receivers must silently ignore any options they do not recognize and continue processing the message. 3.2.3 Neighbour Solicitation Message Format Hosts send Neighbour Solicitations during their stateless address autoconfiguration process to check, whether any other node already uses this tentative address. Also all nodes use Neighbour Solicitations for the execution of the Neighbour Unreachability Detection function. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +---------------+---------------+-------------------------------+ | Type | Code | Checksum | +---------------+---------------+-------------------------------+ | Reserved | +---------------------------------------------------------------+ | Options | IPv6 Fields: Source Address: If used for Duplicate Address Detection this field contains the unspecified address, since only hosts having no address assigned to their interface are allowed to send this message for the purpose of checking, whether the tentative address exists already. Else if used for the execution of the Neighbour Unreachability Detection function, the IPv6 address of the sending interface shall be used. Destination Address: If used for Duplicate Address Detection this field contains the tentative address the host wants to use for this interface. This must not be a multicast address. Else it contains the address of the peer node, for which the Neighbour Unreachability Detection function is Fritsche, Seifert Expires May 1998 [Page 14]INTERNET DRAFT Dynamical routing for IPv6 November 1997 executed. Hop Limit: 255 Priority: 15 Authentication Header: If a Security Association for the IP Authentication Header exists between the source and the destination address, then the source shall include this header. ICMPv6 Fields: Type: 135 - Neighbour Solicitation Message Code: 0 Checksum: The ICMPv6 checksum. See [2]. Reserved: This field is unused. It must be initialised to zero by the sender and must be ignored by the receiver. Valid Options: Source link-layer address: The link-layer address of the sender. On link layers that have addresses this option must be included. Future versions of this protocol may define new option types. Receivers must silently ignore any options they do not recognize and continue processing the message. 3.2.4 Host Advertisement Message Format A host sends Host Advertisements periodically, in response to an other Router or Host Advertisement message generated by a newly detected node, or in the case, that a host expects some of its interface addresses becoming unreachable. Finally a Host Advertisement is sent in response to a Neighbour Solicitation message. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +---------------+---------------+-------------------------------+ | Type | Code | Checksum | +-+-------------+---------------+-------------------------------+ |S| Reserved | Holding Time | +-+-------------+-----------------------------------------------+ | Options | IPv6 Fields: Source Address: 128-bit IPv6 address of the interface from which the advertisement is sent. If all Fritsche, Seifert Expires May 1998 [Page 15]INTERNET DRAFT Dynamical routing for IPv6 November 1997 interfaces of the host have assigned one single IPv6 address, that is an address is not assigned to each interface, but to the host as whole, this address shall be used. Destination Address: If this message is sent periodically due to expiration of the local Host Advertisement transmission timer or in response to a Neighbour Solicitation message containing the unspecified address as Source Address, this field contains the all-nodes multicast address. If it is sent in response to a previously received Router or Host Advertisement message or to a Neighbour Solicitation message containing a unicast Source Address different from the unspecified address, this field contains the IPv6 address specified as Source Address in the respective message. Hop Limit: 255 Priority: 15 Authentication Header: If a Security Association for the IP Authentication Header exists between the source and the destination address, then the source shall include this header. ICMPv6 Fields: Type: 136 - Host Advertisement Message Code: 0 Checksum: The ICMPv6 checksum. See [2]. S: Solicited Flag. When set, the S-bit indicates that the advertisement was sent in response to a Neighbour Solicitation. Reserved: This field is unused. It must be initialised to zero by the sender and must be ignored by the receiver. Holding Time: 24-bit unsigned integer. The time, in seconds, how long the host shall be seen as reachable by its connected neighbours, which have received this message. If during this period no next Host Advertisement message is received from the respective host, it shall be deleted from the adjacency databases of its neighbours. Therefore it is recommendable for hosts, to set this value at least two times the value for the retransmission interval. In this case the loss of a single Host Advertisement message wouldn't cause the deletion of the host from its neighbour's adjacency databases. Valid Options: Fritsche, Seifert Expires May 1998 [Page 16]INTERNET DRAFT Dynamical routing for IPv6 November 1997 Source link-layer address: The link-layer address of the sender. On link layers that have addresses this option must be included. Future versions of this protocol may define new option types. Receivers must silently ignore any options they do not recognize and continue processing the message. 3.2.5 Redirect Message Format Routers send Redirect packets to inform a host of a better first-hop node on the path to a destination. Hosts can be redirected to a better first-hop router, but can also be informed by a redirect that the destination is in fact a neighbour. The latter is accomplished by setting the ICMPv6 Target Address equal to the ICMPv6 Destination Address. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +---------------+---------------+-------------------------------+ | Type | Code | Checksum | +---------------+---------------+-------------------------------+ | Reserved | +---------------------------------------------------------------+ | | | Target Address | | | | | +---------------------------------------------------------------+ +---------------------------------------------------------------+ | | | Destination Address | | | | | +---------------------------------------------------------------+ | Options | IPv6 Fields: Source Address: Must be the IPv6 link-local address assigned to the interface from which this message is sent. Destination Address: The Source Address of the packet that triggered the redirect. Hop Limit: 255 Priority: 15 Authentication Header: If a Security Association for the IP Authentication Header exists between the source and the destination address, then the Fritsche, Seifert Expires May 1998 [Page 17]INTERNET DRAFT Dynamical routing for IPv6 November 1997 source shall include this header. ICMPv6 Fields: Type: 137 - Redirect Message Code: 0 Checksum: The ICMPv6 checksum. See [2]. Reserved: This field is unused. It must be initialised to zero by the sender and must be ignored by the receiver. Target Address: An IPv6 address, that is a better first hop to use for the ICMPv6 Destination Address. If the target is the actual endpoint of communication, i.e., the destination is a neighbour, the Target Address field must contain the same value as the ICMPv6 Destination Address field. Otherwise the target is a better first-hop router and the Target Address must be the router's link-local address so that hosts can uniquely identify routers. Destination Address: The IPv6 address of the destination which is redirected to the target. This address must not be a multicast address. Valid Options: Target link-layer address: The link-layer address for the target. It should be included (if known). Note that on NBMA links, hosts may rely on the presence of the Target Link-Layer Address option in Redirect messages as the means for determining the link-layer addresses of neighbours. In such cases, the option must be included in Redirect messages. Redirected Header: As much as possible of the IP packet that triggered the sending of the Redirect without making the redirect packet exceed 576 octets. Future versions of this protocol may define new option types. Receivers must silently ignore any options they do not recognize and continue processing the message. 3.2.6 Options Formats Neighbour Discovery messages include zero or more options, some of which may appear multiple times in the same message. All options are of the form: Fritsche, Seifert Expires May 1998 [Page 18]INTERNET DRAFT Dynamical routing for IPv6 November 1997 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +---------------+---------------+-------------------------------+ | Type | Length | ... | +---------------+---------------+-------------------------------+ | ... | Fields: Type: 8-bit identifier of the type of option. The options defined here for Neighbour Discovery ICMPv6 messages are: Option Name Type Source Link-Layer Address 1 Target Link-Layer Address 2 Prefix Information 3 Redirected Header 4 MTU 5 LSA information 6 Length: 8-bit unsigned integer. The length of the option in units of 8 octets. The value 0 is invalid. Nodes must silently discard a Neighbour Discovery packet that contains an option with length zero. 3.2.6.1 Source / Target Link-Layer Address 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +---------------+---------------+-------------------------------+ | Type | Length | Link-Layer Address | +---------------+---------------+-------------------------------+ Fields: Type: 1 Source Link-Layer Address 2 Target Link-Layer Address Length: The length of the option in units of 8 octets. For example, the length for IEEE 802 addresses is 1 (one octet for the Type field, one octet for the Length field, and six octets for the IEEE 802 address). Link-Layer Address: The variable length link-layer address. The content and format of this field (including byte and bit ordering)is expected to be specified in specific documents that describe Fritsche, Seifert Expires May 1998 [Page 19]INTERNET DRAFT Dynamical routing for IPv6 November 1997 how IPv6 operates over different link layers. Description: The Source Link-Layer Address option contains the link-layer address of the sender of the packet. It is used in the Neighbour Solicitation, Router Solicitation, Host Advertisement and Router Advertisement packets. The Target Link-Layer Address option contains the link-layer address of the target. It is used only in Redirect packets. These options must be silently ignored for other Neighbour Discovery messages. 3.2.6.2 Prefix Information 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +---------------+---------------+---------------+-+-+-----------+ | Type | Length | Prefix Length |L|A| Reserved1 | +---------------+---------------+---------------+-+-+-----------+ | Valid Lifetime | +---------------------------------------------------------------+ | Preferred Lifetime | +---------------------------------------------------------------+ | Reserved2 | +---------------------------------------------------------------+ | | | Prefix | | | | | +---------------------------------------------------------------+ Fields: Type: 3 Length: 4 Prefix Length: 8-bit unsigned integer. The number of leading bits in the Prefix that are valid. The value ranges from 0 to 128. L: 1-bit on-link flag. When set, indicates that this prefix can be used for on-link determination. When not set the advertisement makes no statement about on-link or off-link properties of the prefix. For instance, the prefix might be used for address configuration with some of the addresses belonging to the prefix being on-link and others being off- link. A: 1-bit autonomous address-configuration flag. When set indicates that this prefix can be Fritsche, Seifert Expires May 1998 [Page 20]INTERNET DRAFT Dynamical routing for IPv6 November 1997 used for autonomous address configuration as specified in [4]. Reserved1: 6-bit unused field. It must be initialised to zero by the sender and must be ignored by the receiver. Valid Lifetime: 32-bit unsigned integer. The length of time in seconds (relative to the time the packet is sent) that the prefix is valid for the purpose of on-link determination. A value of all one bits (0xffffffff) represents infinity. The Valid Lifetime is also used by [4]. Preferred Lifetime: 32-bit unsigned integer. The length of time in seconds (relative to the time the packet is sent) that addresses generated from the prefix via stateless address autoconfiguration remain preferred [4]. A value of all one bits (0xffffffff) represents infinity. See [4]. Reserved2: This field is unused. It must be initialised to zero by the sender and must be ignored by the receiver. Prefix: An IPv6 address or a prefix of an IPv6 address. The Prefix Length field contains the number of valid leading bits in the prefix. The bits in the prefix after the prefix length are reserved and must be initialised to zero by the sender and ignored by the receiver. A router should not send a prefix option for the link-local prefix and a host should ignore such a prefix option. Description: The Prefix Information option provide hosts with on-link prefixes and prefixes for Address Autoconfiguration. The Prefix Information option appears in Router Advertisement packets and must be silently ignored for other messages. 3.2.6.3 Redirected Header 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +---------------+---------------+-------------------------------+ | Type | Length | Reserved | +---------------+---------------+-------------------------------+ | Reserved | +---------------------------------------------------------------+ | | | IPv6 header + data | | ... | +---------------------------------------------------------------| Fritsche, Seifert Expires May 1998 [Page 21]INTERNET DRAFT Dynamical routing for IPv6 November 1997 Fields: Type: 4 Length: The length of the option in units of 8 octets. Reserved: These fields are unused. They must be initialised to zero by the sender and must be ignored by the receiver. IP header + data: The original packet truncated to ensure that the size of the redirect message does not exceed 576 octets. Description: The Redirected Header option is used in Redirect messages and contains all or part of the packet that is being redirected. This option must be silently ignored for other Neighbour Discovery messages. 3.2.6.4 MTU 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +---------------+---------------+-------------------------------+ | Type | Length | Reserved | +---------------+---------------+-------------------------------+ | MTU | +---------------------------------------------------------------+ Fields: Type: 5 Length: 1 Reserved: This field is unused. It must be initialised to zero by the sender and must be ignored by the receiver. MTU: 32-bit unsigned integer. The recommended MTU for the link. Description: The MTU option is used in Router Advertisement messages to insure that all nodes on a link use the same MTU value in those cases where the link MTU is not well known. This option must be silently ignored for other Neighbour Discovery messages. In configurations in which heterogeneous technologies are bridged together, the maximum supported MTU may differ from one segment to another. If the bridges do not generate ICMP Packet Too Big messages, communicating nodes will be unable to use Path MTU to dynamically determine the appropriate MTU on a per- neighbour basis. In such cases, routers use the MTU option to specify an MTU value Fritsche, Seifert Expires May 1998 [Page 22]INTERNET DRAFT Dynamical routing for IPv6 November 1997 supported by all segments. 3.2.6.5 LSA information 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +---------------+---------------+-------------------------------+ | Type | Length | Reserved | +---------------+---------------+-------------------------------+ | Reserved | +---------------------------------------------------------------+ | | | LSA IPv6 Address | | ... | +---------------------------------------------------------------| Fields: Type: 6 Length: 3 Reserved: These fields are unused. They must be initialised to zero by the sender and must be ignored by the receiver. LSA IPv6 Address: The LSA information option is present only in Router Advertisement messages. It informs other routers receiving this advertisement, on behalf of which IPv6 address this router will generate its Link State Advertisements. If a router uses more than one IPv6 address on its interfaces, this knowledge is necessary for the neighbouring routers in the routing area to assign the proper LSAs to this router during the execution of the routing algorithm. If a router has assigned only one IPv6 address, this option doesn't have to be present, since this single address must be contained in the Source Address field of the Router Advertisement. This option must be silently ignored for other Neighbour Discovery messages. 3.3 Validation of the used ICMPv6 messages This section describes the vality checks, which have to be executed by the nodes receiving those Neighbour Discovery messages. Fritsche, Seifert Expires May 1998 [Page 23]INTERNET DRAFT Dynamical routing for IPv6 November 1997 3.3.1 Validation of Router Solicitations Hosts must silently discard any received Router Solicitation Messages. A router must silently discard any received Router Solicitation messages that do not satisfy all of the following validity checks: - The IP Hop Limit field has a value of 255, i.e., the packet could not possibly have been forwarded by a router. - If the message includes an IPv6 Authentication Header, the message authenticates correctly. - ICMPv6 Checksum is valid. - ICMPv6 Code is 0. - ICMPv6 length (derived from the IPv6 length) is 8 or more octets. - All included options have a length that is greater than zero. The contents of the Reserved field, and of any unrecognized options, must be ignored. Future, backward-compatible changes to the protocol may specify the contents of the Reserved field or add new options; backward-incompatible changes may use different Code values. The contents of any defined options that are not specified to be used with Router Solicitation messages must be ignored and the packet processed as normal. The only defined option that may appear is the Source Link-Layer Address option. A solicitation that passes the validity checks is called a "valid solicitation". 3.3.2 Validation of Router Advertisements A node must silently discard any received Router Advertisement messages that do not satisfy all of the following validity checks: - IPv6 Source Address is an unicast address. Routers must use as the source for Router Advertisements and Redirect messages the address of their sending interface or, if all interfaces have the same address, that is an address is not assigned to each interface, but to the router as whole, the address assigned to the router as whole. This enables hosts to uniquely identify routers. - The IPv6 Hop Limit field has a value of 255, i.e., the packet could not possibly have been forwarded by a router. - If the message includes an IPv6 Authentication Header, the message authenticates correctly. - ICMPv6 Checksum is valid. - ICMPv6 Code is 0. - ICMPv6 length (derived from the IPv6 length) is 16 or more octets. - All included options have a length that is greater than zero. The contents of the Reserved field, and of any unrecognized options, must be ignored. Future, backward-compatible changes to the protocol may specify the contents of the Reserved field or add new options; backward-incompatible changes may use different Code values. Fritsche, Seifert Expires May 1998 [Page 24]INTERNET DRAFT Dynamical routing for IPv6 November 1997 The contents of any defined options that are not specified to be used with Router Advertisement messages must be ignored and the packet processed as normal. The only defined options that may appear are the Source Link-Layer Address, Prefix Information, LSA information and MTU options. An advertisement that passes the validity checks is called a "valid advertisement". 3.3.3 Validation of Neighbour Solicitations A node must silently discard any received Neighbour Solicitation messages that do not satisfy all of the following validity checks: - The IPv6 Hop Limit field has a value of 255, i.e., the packet could not possibly have been forwarded by a router. - If the message includes an IPv6 Authentication Header, the message authenticates correctly. - IPv6 Destination Address must not be a multicast address. - ICMPv6 Checksum is valid. - ICMPv6 Code is 0. - ICMPv6 length (derived from the IPv6 length) is 8 or more octets. - All included options have a length that is greater than zero. The contents of the Reserved field, and of any unrecognized options, must be ignored. Future, backward-compatible changes to the protocol may specify the contents of the Reserved field or add new options; backward-incompatible changes may use different Code values. The contents of any defined options that are not specified to be used with Neighbour Solicitation messages must be ignored and the packet processed as normal. The only defined option that may appear is the Source Link-Layer Address option. A Neighbour Solicitation that passes the validity checks is called a "valid solicitation". 3.3.4 Validation of Host Advertisements A node must silently discard any received Host Advertisement messages that do not satisfy all of the following validity checks: - The IPv6 Hop Limit field has a value of 255, i.e., the packet could not possibly have been forwarded by a router. - If the message includes an IPv6 Authentication Header, the message authenticates correctly. - ICMPv6 Checksum is valid. - ICMPv6 Code is 0. - ICMPv6 length (derived from the IPv6 length) is 8 or more octets. - All included options have a length that is greater than zero. The contents of the Reserved field, and of any unrecognized options, Fritsche, Seifert Expires May 1998 [Page 25]INTERNET DRAFT Dynamical routing for IPv6 November 1997 must be ignored. Future, backward-compatible changes to the protocol may specify the contents of the Reserved field or add new options; backward-incompatible changes may use different Code values. The contents of any defined options that are not specified to be used with Host Advertisement messages must be ignored and the packet processed as normal. The only defined option that may appear is the Source Link-Layer Address option. A Host Advertisement that passes the validity checks is called a "valid advertisement". 3.3.5 Validation of Redirect Messages A host must silently discard any received Redirect message that does not satisfy all of the following validity checks: - IPv6 Source Address is an unicast address. Routers must use as the source for Router Advertisements and Redirect messages the address of their sending interface or, if all interfaces have the same address, that is an address is not assigned to each interface, but to the router as whole, the address assigned to the router as whole. This enables hosts to uniquely identify routers. - The IPv6 Hop Limit field has a value of 255, i.e., the packet could not possibly have been forwarded by a router. - If the message includes an IPv6 Authentication Header, the message authenticates correctly. - ICMPv6 Checksum is valid. - ICMPv6 Code is 0. - ICMPv6 length (derived from the IPv6 length) is 40 or more octets. - The IPv6 Source Address of the Redirect is the same as the current first-hop router for the specified ICMPv6 Destination Address. - The ICMPv6 Destination Address field in the redirect message does not contain a multicast address. - The ICMPv6 Target Address is either an address of a router interface on that link (when redirected to a router) or the same as the ICMPv6 Destination Address (when redirected to a destination connected to this link). - All included options have a length that is greater than zero. The contents of the Reserved field, and of any unrecognized options must be ignored. Future, backward-compatible changes to the protocol may specify the contents of the Reserved field or add new options; backward-incompatible changes may use different Code values. The contents of any defined options that are not specified to be used with Redirect messages must be ignored and the packet processed as normal. The only defined options that may appear are the Target Link-Layer Address option and the Redirected Header option. A host must not consider a redirect invalid just because the Target Address of the redirect is not covered under one of the link's Fritsche, Seifert Expires May 1998 [Page 26]INTERNET DRAFT Dynamical routing for IPv6 November 1997 prefixes. Part of the semantics of the Redirect message is that the Target Address is connected to the link. A redirect that passes the validity checks is called a "valid redirect". 3.4 Functions of the Neighbour Discovery This section will shortly summarize the functionality of the modified Neighbour Discovery mechanism. The functions described herein can only be applied on multicast-capable links. 3.4.1 Router Discovery Hosts, which newly connect to a subnetwork, can send Router Solicitations to the all-router multicast address. Using this mechanism the hosts don't have to wait for the periodically sent Router Advertisements, but can explicitly ask the connected routers to send their advertisements earlier. The Source Address of these solicitations must be the unspecified address for hosts, which havn't already configured an IPv6 address for their interfaces. All other hosts must use the address assigned to the sending interface. If a router receives a Router Solicitation message, it shall send out its normally periodically retransmitted Router Advertisement. Since sending many Router Advertisements simultaneously can cause a burst on the subnetwork, each router shall randomly delay its own advertisement. In order to receive these advertisements, the host generating the Router Solicitations previously joins the all-nodes multicast address on all multicast-capable interfaces. Receiving the information contained in the Router Advertisements the host is informed about the relevant parameters on that link. If it has not already configured IPv6 addresses for its interfaces, it can now continue with the stateless address autoconfiguration. Once a host receives solicited Router Advertisements, it has to stop sending Router Solicitations. If no advertisements have been received by the host after transmission of MAX_RTR_SOLICITATIONS [3], the host concludes, that there is no router present on the link. In this case the host must attempt to use stateful autoconfiguration to obtain addresses and other configuration information. Nevertheless the host will continue listening for Router Advertisements for the case, that a router appears on the link. 3.4.2 Stateless Address Autoconfiguration A host, which has newly connected to a link and has already received Fritsche, Seifert Expires May 1998 [Page 27]INTERNET DRAFT Dynamical routing for IPv6 November 1997 Router Advertisements, can initiate the stateless address autoconfiguration for its interface on that link. Before it assigns a tentative IPv6 address derived from the respective prefixes contained in the Router Advertisements to its interface, it has to make sure, that no duplicate address exists already on that link. It is recommended, that for each assigned unicast address, regardless whether it is obtained through stateless, stateful or manual configuration, this check is executed. This is done by sending up to DupAddrDetectTransmits [3] Neighbour Solicitations destined for the tentative address on the interface to be configured. The solicitation shall be separated by Retrans Timer milliseconds, and their Source Addresses have to be the unspecified address. If the tentative address exists already on the link, the respective node will receive these solicitations. If this node is a router, it must send immediately a Router Advertisement message for the tentative address, if the node is a host, a Host Advertisement message has to be transmitted. Both advertisements have to be destined for the all-node multicast address, and have to set their Solicited Flag. A host executing the Duplicate Address Detection by sending Neighbour Solicitation messages has to receive on that interface all Router and Host Advertisement messages addressed to the all-node multicast address. If it receives one solicited advertisement, which Source Address is equal to the tentative address of the host's interface, the host can be sure, that the tentative address is already in use on that link. In this case the host has to use an other mechanism for the configuration of its interface address, for example a manual configuration. In order to detect even other hosts executing simultaneously the Duplicate Address Detection for the same tentative address, a host receives during this process also Neighbour Solicitation messages destined for the tentative address it wants to use for its interface. If it detects on this way, that another host is also trying to use this address, the host has to use an other mechanism for the address configuration. If after DupAddrDetectTransmits sent Neighbour Solicitations no duplicate address is indicated by the receipt of the respective Neighbour Solicitations or Router or Host Advertisements, the host can assign this address to its interface. If this address has been configured by stateless address autoconfiguration, that is it is composed of a prefix distributed by Router Advertisements and an appended locally used token, all addresses generated from the same token will also be unique. This shall be true, since subnet prefixes are assumed to be assigned correctly. Therefore the uniqueness of an IPv6 address depends only on the uniqueness of the used token, what means, if one address generated from this token is unique, all other Fritsche, Seifert Expires May 1998 [Page 28]INTERNET DRAFT Dynamical routing for IPv6 November 1997 addresses generated from the same token are also unique. Nevertheless it shall be mentioned, that this mechanism of Duplicate Address Detection is not completely reliable. In the case of a partitioned link during the execution of this mechanism, a duplicate address in the other partition cannot be detected. Therefore a host after having an address assigned to one of its interfaces shall continue looking for indications of existing duplicate addresses. Such an indication could be for example a received Host Advertisement containing a Source Address assigned to one of its own interfaces. 3.4.3 Neighbour Detection This functionality is newly added in this proposal. Having an address assigned to one of their interfaces, router send periodically Router Advertisements, and hosts Host Advertisements on this interface. Both advertisements are addressed to the all-node multicast address and contain as Source Address the address of the respective interface. The Holding Time of these advertisements specifies, how long this message shall cause the sender to be seen as reachable neighbour at the receiving nodes. Using this method each node can build up a local database, in the following referred to as adjacency database, which contains the IPv6 addresses and also the link-layer addresses of all connected nodes on a particular link. Additionally the information is provided, if the neighbour is a router or a host. If a router receives a Router Advertisement from a neighbouring router, and the advertisement contains a LSA information option, the receiving router will also store the IPv6 address contained in this option in its local adjacency database. This address is also assigned to an interface of the neighbouring router and is later used for the execution of the routing algorithm. Storing the Holding Time with each database entry enables the detection of a node becoming unreachable. In this case no next advertisement has been received from the node within the specified Holding Time. Here the considerations done in chapter 1 become more clearly. Sending of periodical signs of life by the single nodes, here in form of Router and Host Advertisement messages, is the only way a node can keep track with the state of its neighbours. On that way all changes of any neighbours are automatically recognized at the latest within the next Holding Time seconds. This is an absolutely necessary requirement for the implementation of a dynamical routing algorithm. It is obviously, that the more often those advertisements are sent, the more dynamical is the distribution of any changes of the respective neighbours, but also the more bandwidth and therefore costs are needed for the distribution of this control information. It is up to the network administrator to find a suitable compromise of dynamic and costs on each particular link. Fritsche, Seifert Expires May 1998 [Page 29]INTERNET DRAFT Dynamical routing for IPv6 November 1997 There is also a mechanism defined, which enables a newly connected host to get the life signs of its neighbours before the expiration of their retransmission timers. As mentioned above a newly connected node starts, after having configured its interface address, the periodical transmission of advertisements. Receiving the first advertisement of such a new node the neighbours will send back their own advertisements explicitly to the Source Address of this node instead to the all-nodes multicast address. To avoid a burst of advertisements sent by all neighbours of the new node at the same time, each message shall be randomly delayed. Finally a node, which knows, that some of its interface addresses will be unreachable the next time, shall send advertisements for these addresses with the respective Holding Time set to the time the interface will still be reachable. This causes a deletion of the interface in the adjacency databases of all neighbours exactly at the time the interface would become unavailable, and not at the time the Holding Timer of the periodical advertisements sent by the interface would normally expire. In both cases described at last, advertisements are sent triggered by an event (new node or an address becoming unreachable), and not by expiration of the retransmission timer. Sending advertisements for these events improves the dynamic of the information distribution without the necessity to decrease the time between periodical retransmission. 3.4.4 Neighbour Unreachability Detection Using the Neighbour Detection functionality each node on the link is informed by the receipt of periodical advertisements, from which neighbour nodes itself can be reached, but it doesn't know, if itself can also reach these neighbours. The Neighbour Detection functionality provides only a statement about unidirectional reachability. In most cases this information is enough, like for the execution of a routing algorithm. Sometimes, for example if a node supposes, that its data packets don't reach a neighbour, although this neighbour is stored as reachable in the local adjacency database, it could be helpful to have a mean to examine the bi-directional reachability between two nodes. This is done by the Neighbour Unreachability Detection function. A node, which executes this function, sends Neighbour Solicitation messages to the respective peer node. The Destination Address of these solicitations is set to the peer node's unicast address and the Source Address is set to the unicast address configured for the sending interface. If the peer node receives a solicitation containing a Source Address other than the unspecified address, it sends back an own advertisement addressed to the unicast address of the initiator of the Neighbour Unreachability Detection instead of the all-nodes multicast address. The Solicitation Flag of this Fritsche, Seifert Expires May 1998 [Page 30]INTERNET DRAFT Dynamical routing for IPv6 November 1997 advertisement must be set. If this response is received at the initiator node, it knows, that there exists a bi-directional reachability between itself and the checked peer node. 3.4.5 Redirect This functionality remains as specified in [3]. Redirect messages are sent by routers to redirect a host to a better first-hop router for a specific destination or to inform hosts that a destination is in fact a neighbour (i.e., connected to the same link). The latter is accomplished by having the ICMPv6 Target Address be equal to the ICMPv6 Destination Address in the respective Redirect message. 3.5 Neighbour Discovery on non-multicast-capable links The functions specified in the previous section, are not fully applicable on subnetworks without multicast-capabilities. For example by executing the Router Discovery function a host sends Router Solicitations to the all-router multicast address. Such an address doesn't exist on non-multicast-capable networks , what is easy to understand, since for example the group consisting of all routers connected to a non-multicast-capable WAN link would be much larger than a group on an IEEE 802 link, and addressing of such large groups would significantly decrease the available bandwidth of the network. Therefore some modifications have to be done to implement the Neighbour Discovery mechanism. Because of the lack of multicast addresses a newly connected host has no chance to receive configuration information from a router. This means that the Router Discovery function and therefore also the Stateless Address Autoconfiguration functions are not applicable. The necessary parameters and interface addresses of a new node have to be configured manually. Connected to the link the new node have no information, to which possible neighbours it shall send its advertisements. Setting the Destination Address to a multicast address isn't possible on these networks, and information about unicast interface addresses of neighbouring nodes cannot be received from their advertisements, since these advertisements are not transmitted to the momentary still unknown new node. Therefore also this problem can be solved only by a manual configuration. Each node must have a list of all neighbour nodes, which are possibly reachable over the link. For each neighbour the list has to contain its IPv6 address along with its link-layer address on the respective link. If a node is now newly connected to the link, it sends its own advertisement to each of the neighbours contained in this list. The Fritsche, Seifert Expires May 1998 [Page 31]INTERNET DRAFT Dynamical routing for IPv6 November 1997 Source Address of the advertisement is the address of the sending interface, and the Destination Address is set to the IPv6 address specified for the respective neighbour in the list. For each addressed neighbour an entry in the new node's adjacency database is created and marked as "initialising". If one of the neighbour nodes receive in this way the advertisement of the new node, the new node is stored as reachable neighbour in the neighbouring node's adjacency database and an own advertisement is sent back to the address contained in the Source Address field of the received message. If this returned advertisement reaches the newly connected node, the peer node marked as "initialialising" in the local adjacency database is now stored as reachable neighbour. Once this handshake has been executed successfully, advertisements can be exchanged periodically between these both nodes in the same way, as it is done on multicast-capable links. The only difference is, that on non-multicast-capable links also the periodically exchanged advertisements have to be addressed to an unicast address instead of a multicast address. The advantage of this modification is, that the Neighbour Unreachability Detection function is not longer needed on those circuits, since exchanging the advertisements in pairs always guarantees a bi-directional reachability between the peer nodes. Unfortunately this method uses more bandwidth than the one on multicast-capable circuits, since now a host has to send one advertisement periodically to each neighbour compared with sending altogether only one advertisement periodically to a multicast address. This disadvantage can be lessened by using longer retransmission intervals on those links, but of course this will also decrease the dynamic of the routing algorithm. Summarizing all these aspects this is a suitable mechanism to deal with the difficulties on non-multicast-capable links, and it offers an appropriate solution for the integration of those links into the dynamical routing area. Fritsche, Seifert Expires May 1998 [Page 32]INTERNET DRAFT Dynamical routing for IPv6 November 1997 4 Dynamical routing of unicast packets in IPv6 4.1 Introduction After having a suitable mechanism of dynamically discovering the own neighbours, there are still two problems to be solved before a router is able to execute its routing algorithm. One of these aspects has already be mentioned in the previous chapter. Each router is now able to produce a detailed picture of the network in its own environment, but it still has no information about the constellation of the routing area on links, to which it has no connection. Therefore each router has to exchange with all other routers of the routing area the information, which it has locally collected about its own environment. For this purpose ICMPv6 packets called Link State Advertisements are used. These packets contain all nodes, routers and hosts, which are neighbours of the router generating the LSA, that is all nodes, which are contained in the local adjacency database. Additionally each of those nodes is marked as router or host. These Link State Advertisements are exchanged both, periodically and triggered by events. The periodical transmission ensures, that in the case of the loss of a certain LSA the contents of this packet is retransmitted. The transmission triggered by events helps to improve the dynamic of the distribution of routing information, since for example in the case of a new router has been detected on a link, all routing information could be sent immediately to this new node without waiting for the expiration of the retransmission timer. The distribution mechanism of Link State Advertisements is flooding, that means a router receiving a LSA will send the LSA to all its neighbouring routers except to these ones, which are located on the link from which the LSA has been received. This link is excluded from the transmission list, since the router supposes, that the preceding router has already flooded the LSA on that link. Each router stores each received LSA in a local database, the so called Link State database. The contents of this database is later used during the execution of the routing algorithm. If there are loops present on a network, LSAs could theoretically be forwarded infinitely on this loops until the Hop Limit value of the IPv6 packet reaches zero. In practice this undesirable effect is avoided by the use of a Sequence Number present in each LSA. This number represents the topicality of the respective LSA. If the LSA is generated the first time, the originating router sets this number to 1. Each time the LSA is retransmitted, the value is increased by 1, that is the higher the Sequence Number the newer is the LSA. If a router receives a LSA with a Sequence Number lower or equal to the number of the already stored LSA version, it will not further forward this LSA, since if there is already a newer or the same version of Fritsche, Seifert Expires May 1998 [Page 33]INTERNET DRAFT Dynamical routing for IPv6 November 1997 this LSA stored, the stored version has been already forwarded at the time it was received. On this way the creation of infinite loops during the flooding of LSAs is successfully prevented. Each LSA also contains a Holding Time field. The use of this field is similar to the use of the Holding Time in Router and Host Advertisements. All routers decrement continuously the Holding Time of all LSAs stored in their local Link State database. If a Holding Timer expires before a new version of the respective LSA has been received, the stored LSA is deleted from the database and its contents will not be used in the next execution of the routing algorithm. Therefore a router has to make sure, that it retransmits its LSAs before their Holding Times expire in the databases of the other routers. To be sure, that even in the case, that a single retransmitted LSA gets lost, all other routers still keep the contents of this LSA in their databases, it is recommendable, to set the Holding Time to at least two times the retransmission interval for the own LSAs. To easy indicate to the other routers, that a LSA is retransmitted unchanged, or that its contents have really changed, each LSA contains a so called Change flag. If this flag is set to 1, each receiving router knows, that it has to replace completely the stored LSA version with the received one. If the flag is set to zero, and the Sequence Number of the received LSA is equal to the Sequence Number of the stored LSA version increased by 1, that is the router has continuously received all generated LSA versions, the receiving router only has to reset the Holding Time and update the Sequence Number. If there is one LSA version missing, the router has to compare the contents of the stored and the received LSA and to decide after that, if the contents have really changed. The second problem to be solved is the definition of a metric. A dynamical routing algorithm can only be used efficiently, if each of the links in the routing area has assigned at least one metric. Evaluating this metric an algorithm can select the best path in the network from a given source to a given destination. Since the chosen path is only optimal with regard to the used metric, it is an important consideration to define, what physical size a used metric shall represent. Some examples could be metrics, which represent the different costs on the links or the bit error probabilities. In this case an algorithm would be able, to select the way from a source to a destination with the lowest costs or the lowest probability of delivering an incorrect packet. If there are more metrics in use on a network the routing algorithm has to be run separately for each metric. Also there must be an unequivocally indicator with an IPv6 packet, which determines, which metric should be used for routing this packet. See chapter 7 for a closer look on this aspect. The next section defines the packet format, which is used for the Fritsche, Seifert Expires May 1998 [Page 34]INTERNET DRAFT Dynamical routing for IPv6 November 1997 distribution of routing information between the routers of a single routing area. 4.2 ICMPv6 Routing Information message formats 4.2.1 Link State Advertisement Message Format Routers belonging to the same routing area exchange among themselves within Link State Advertisements the dynamically collected routing information of their connected links. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +---------------+---------------+-------------------------------+ | Type | Code | Checksum | +---------------+---------------+-------------------------------+ | Holding Time | +---------------------------------------------------------------+ | Sequence Number | +-------------------------------+-+-------------+---------------+ | |C| Reserved | Reserved | +-------------------------------+-+-------------+---------------| | Options | IPv6 Fields: Source Address: The IPv6 address on behalf of which the router will generate all its Link State Advertisements. This address has been told all the neighbouring routers by the LSA information option contained in the Router Advertisements (this option is only present, if this address differs from the Source Address of the advertisements). The respective address must be a unicast address and valid the whole lifetime of the router to ensure an unequivocally identification of the LSAs belonging to a particular router. Destination Address:Either the all-routers multicast address, or the unicast address of a particular router on a connected link. Hop Limit: Set to 255 by the originator of the Link State Advertisement. This value is decremented by 1 at each router, which forwards the packet. Priority: 15 Authentication Header:If a Security Association for the IP Authentication Header exists between the source and the destination address, then the source shall include this header. Fritsche, Seifert Expires May 1998 [Page 35]INTERNET DRAFT Dynamical routing for IPv6 November 1997 ICMPv6 Fields: Type: 138 - Link State Advertisement Message Code: 0 Checksum: The ICMPv6 checksum. See [2]. Holding Time: 32-bit unsigned integer. The time, in seconds, how long a router receiving a Link State Advertisement shall store its contents in its Link State database. If during this period no newer Link State Advertisement message, that is a Link State Advertisement with the same LSA Number, but with a higher Sequence Number, is received from the same router, then the router shall delete the LSA from its local Link State database. Therefore it is recommendable for routers, to set this value to at least two times the value for the retransmission interval of Link State Advertisements. In the case of the loss of a single advertisement its contents wouldn't be deleted from the Link State databases of the other routers. Sequence Number: 32-bit unsigned integer. This number is used to identify the topicality of a single Link State Advertisement. If there are two LSAs from the same router with the same LSA Number the LSA with the higher Sequence Number is seen as newer. A router, which generates a certain LSA for the first time, shall set the Sequence Number of this LSA to 1. Each time the router either periodically retransmits this LSA or updates the contents of the LSA, it shall increase the Sequence Number by 1. This ensures, that all other routers receiving this LSA detect, that it is a newer version. LSA Number: 16-bit unsigned integer. Probably not all local routing information of a router will fit into a single Link State Advertisement, but has to be distributed in more LSAs. To unequivocally identify a certain LSA of its locally generated set, the originating router assigns a number to each advertisement. Therefore the Source Address of a LSA and its LSA Number both together identify a single LSA unequivocally in the whole network. C: Change flag. This flag set to 1 means, that the contents of this Link State Advertisement have been modified by the originating router. If a router receives a newer LSA with the Change flag set to one, it can replace the stored contents of this LSA with the received Fritsche, Seifert Expires May 1998 [Page 36]INTERNET DRAFT Dynamical routing for IPv6 November 1997 ones without first comparing both packets, else it shall only reset the Holding Time and update the Sequence Number. If the Sequence Number of a received LSA is more than 1 higher than the one stored in the local Link State database, that is one LSA version didn't reach this router, the receiving router always has to compare both contents to decide, if they have changed. This is necessary, since the router has no knowledge, if the Change flag of the missing LSA has been set or not. Reserved: These fields are unused. They must be initialised to zero by the sender and must be ignored by the receiver. Valid Options: Router Neighbours: If the router originating the Link State Advertisement has neighbouring routers on one of its connected links, and the information about these adjacencies shall be distributed within this LSA, the Router Neighbours option has to be present. This option can appear several times within one LSA. Host Neighbours: If the router originating the Link State Advertisement has neighbouring hosts on one of its connected links, and the information about these adjacencies shall be distributed within this LSA, the Host Neighbours option has to be present. This option can appear several times within one LSA. Future versions of this protocol may define new option types. Receivers must silently ignore any options they do not recognize and continue processing the message. 4.2.2 Options Formats Routing Information messages include zero or more options, some of which may appear multiple times in the same message. Like in Neighbour Discovery messages also in Routing Information messages all options are of the form: 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +---------------+---------------+-------------------------------+ | Type | Length | ... | +---------------+---------------+-------------------------------+ | ... | Fritsche, Seifert Expires May 1998 [Page 37]INTERNET DRAFT Dynamical routing for IPv6 November 1997 Fields: Type: 8-bit identifier of the type of option. The options defined here for Routing Information ICMPv6 messages are: Option Name Type Router Neighbours 7 Host Neighbours 8 Length: 8-bit unsigned integer. The length of the option in units of 8 octets. The value 0 is invalid. Nodes must silently discard a Routing Information packet that contains an option with length zero. 4.2.2.1 Router Neighbours 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +---------------+---------------+---------------+---------------+ | Type | Length |Num. of Routers| Reserved | +-+-------------+-+-------------+-+-------------+-+-------------+ |S| metric_1 |S| metric_2...|S| metric_3 |S| metric_4 | +-+-------------+-+-------------+-+-------------+-+-------------+ | | | Router_1 | | | | | +---------------------------------------------------------------+ | | | Router_2 | Fields: Type: 7 Length: The length of the option in units of 8 octets. There must be at least one router present in this option. Therefore the minimal value for this field is 3. Number of Routers: 8-bit unsigned integer. The value of this field specifies the number of routers contained in this option. Reserved: This field is unused. It must be initialised to zero by the sender and must be ignored by the receiver. S: Supported flag. If this flag is set to 1, the router originating this Link State Advertisement supports the following metric Fritsche, Seifert Expires May 1998 [Page 38]INTERNET DRAFT Dynamical routing for IPv6 November 1997 for the neighbouring routers contained in this option, else not. metric_i: If the Supported flag assigned to this metric is set to one, metric_i with i =1, 2, 3, 4 contains a 7-bit unsigned integer, which specifies the metric value, over which all routers contained in this option are reachable from the router originating the respective Link State Advertisement. It is not defined in this document, which physical sizes shall be represented by metric_i. One possibility could be default metric, delay metric, cost metric and error metric. It only has to be guaranteed, that all router in the routing area use the same metric interpretation. Router_i: This option contains the IPv6 addresses of the respective neighbouring routers, on behalf of which these routers will distribute their Link State Advertisements. These addresses are contained in the LSA information option of the Router Advertisements of these neighbours, or, if this option is not present, they are the same addresses, which are contained as Source Addresses in the Router Advertisements and which are stored in the local adjacency database. All routers listed here are reachable from this node over the metrics specified in this option. Also a router lists herein all IPv6 unicast addresses, which itself has assigned to any of its interfaces. Since these are local addresses, all metric values have to be zero. 4.2.2.2 Host Neighbours 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +---------------+---------------+---------------+---------------+ | Type | Length | Num. of Hosts | Reserved | +-+-------------+-+-------------+-+-------------+-+-------------+ |S| metric_1 |S| metric_2...|S| metric_3 |S| metric_4 | +-+-------------+-+-------------+-+-------------+-+-------------+ | | | Host_1 | | | | | +---------------------------------------------------------------+ | | | Host_2 | Fritsche, Seifert Expires May 1998 [Page 39]INTERNET DRAFT Dynamical routing for IPv6 November 1997 Fields: Type: 8 Length: The length of the option in units of 8 octets. There must be at least one host present in this option. Therefore the minimal value for this field is 3. Number of Hosts: 8-bit unsigned integer. The value of this field specifies the number of hosts contained in this option. Reserved: This field is unused. It must be initialised to zero by the sender and must be ignored by the receiver. S: Supported flag. If this flag is set to 1, the router originating this Link State Advertisement supports the following metric for the neighbouring hosts contained in this option, else not. metric_i: If the Supported flag assigned to this metric is set to one, metric_i with i =1, 2, 3, 4 contains a 7-bit unsigned integer, which specifies the metric value, over which all hosts contained in this option are reachable from the router originating the respective Link State Advertisement. It is not defined in this document, which physical sizes shall be represented by metric_i. One possibility could be default metric, delay metric, cost metric and error metric. It only has to be guaranteed, that all router in the routing area use the same metric interpretation. Host_i: The IPv6 addresses of the respective neighbouring hosts. These are the same addresses, which are contained as Source Addresses in the Host Advertisements from these neighbours and which are stored in the local adjacency database. All hosts listed here are reachable from this node over the metrics specified in this option. 4.3 Validation of the used ICMPv6 messages This section describes the vality checks, which have to be executed by the nodes receiving those Routing Information messages. 4.3.1 Validation of Link State Advertisements A router must silently discard any received Link State Advertisement message that does not satisfy all of the following validity checks: - IPv6 Source Address is an unicast address. Routers must use as the Fritsche, Seifert Expires May 1998 [Page 40]INTERNET DRAFT Dynamical routing for IPv6 November 1997 source the IPv6 address, which they specify in the LSA information option of their Router Advertisements. This enables all other routers in the routing area to uniquely assign a received LSA to the originating router. - The IPv6 Hop Limit field has a value of 255 or lower. Each time a router forwards a Link State Advertisement, this field is decremented by 1. If a router receives a LSA with this value set to zero, the packet isn't further forwarded. - If the message includes an IPv6 Authentication Header, the message authenticates correctly. - ICMPv6 Checksum is valid. - ICMPv6 Code is 0. - ICMPv6 length (derived from the IPv6 length) is 16 or more octets. - All included options have a length that is greater than zero. The contents of the Reserved field, and of any unrecognized options must be ignored. Future, backward-compatible changes to the protocol may specify the contents of the Reserved field or add new options; backward-incompatible changes may use different Code values. The contents of any defined options that are not specified to be used with Link State Advertisement messages must be ignored and the packet processed as normal. The only defined options that may appear are the Router Neighbours option and the Host Neighbours option. A Link State Advertisement that passes the validity checks is called a "valid advertisement". 4.4 Functions for the Routing Information distribution This section will shortly summarize the functionality of the defined Routing Information distribution mechanism. The functions described herein can only be applied on multicast-capable links. 4.4.1 Sending Link State Advertisements Each router in the routing area has to execute this function. For this purpose the router first has to locally determine, on behalf of which of the IPv6 addresses assigned to its interfaces it will generate and distribute Link State Advertisements. The chosen address has to be existent for the whole lifetime of the router. After that the router will inform all its neighbours about its selection by including the selected IPv6 address in the LSA information option of its Router Advertisements. If this option isn't present in an advertisement, a receiving neighbouring router supposes, that the originating router will generate LSAs on behalf of the address contained as Source Address in the advertisement. Once a router has selected one of its IPv6 addresses, this address has to be used as Source Address in each LSA the router generates. Fritsche, Seifert Expires May 1998 [Page 41]INTERNET DRAFT Dynamical routing for IPv6 November 1997 The reason for the use of Link State Advertisements is the need of a possibility to distribute the information collected by a router about the own local environment. Therefore a LSA has to contain all reachable neighbour addresses of a router, the metric over which they are reachable and the information, if the address resides in a host or in a router. In detail the following addresses have to be distributed in LSAs: - All reachable IPv6 interface addresses of neighbouring hosts. A router is informed about these addresses by the receipt of Host Advertisement messages on its connected links and will have stored them in the local adjacency database. They are marked as host addresses by including them in the Host Neighbours option of a LSA. The metric values for these addresses could be specified separately for each of them or there is a single set of metrics assigned to all addresses reachable from the router on a particular link. - All own IPv6 addresses assigned to any of the router's interfaces. This set consists of all unicast addresses, for which the router will receive IPv6 packets, and for which it will send Router Advertisements to its connected neighbours. One of these addresses is the address on behalf of which the router generates its LSAs. They are marked as router addresses by including them in the Router Neighbours option of a LSA. The metric values for these addresses are all set to 0, since they are direct reachable within the router itself. - All IPv6 addresses, on behalf of which neighbouring routers will generate their Link State Advertisements. A router is informed about these addresses by examining the LSA information option contained in the received Router Advertisements of its neighbouring routers, or, in the absence of this option, by using the address contained in the Source Address field of these advertisements. It is not necessary to include in the own LSAs all reachable IPv6 addresses of a neighbouring router, because this information is already present in the LSAs of this neighbour. Therefore it is sufficient, to include only the one address of the neighbouring router, which unequivocally helps to locate the LSAs generated from this neighbour. This address is exactly the one distributed in the LSA information option of the neighbour's Router Advertisements. The metric values for these addresses could be specified separately for each of them or there is a single set of metrics assigned to all addresses reachable from the router on a particular link. If not all of these addresses fit into a single Link State Advertisement, the router has to generate more of them, which can all be distinguished by having a different value for the LSA Number assigned. If the router retransmits a LSA, the value for the LSA Number has to remain unchanged. Each of the addresses contained in the preceding LSA version , which is still reachable by the router, also have to be present in any retransmitted LSA version. Newly discovered addresses have to be added to a LSA, which has still enough space for an additional Neighbour option. If all existing LSAs are already full, a new LSA having a still unused LSA Number assigned, has to be generated. If there was a change in the contents Fritsche, Seifert Expires May 1998 [Page 42]INTERNET DRAFT Dynamical routing for IPv6 November 1997 of a LSA or if the LSA is transmitted the first time, the router has to set the Change flag to 1, else this flag shall be 0. To mark its actual version, a LSA contains a Sequence Number. This number is set to 1, if the LSA is transmitted the first time. Each time it is retransmitted, this number has to be increased by 1, that is the higher the Sequence Number of a LSA the newer is its contents. Therefore it is important, that all routers keep track with the Sequence Numbers of all LSAs they receive, since this is the only possibility to determine, if the received LSA version shall replace the stored one or not. In the following circumstances a router has to transmit its locally generated LSAs: - If a node starts to act as a router, it has to generate and transmit own LSAs containing all its reachable neighbour addresses. Each time the retransmission timer of these LSAs expires, the router has to flood all of them on each connected circuit. This flooding could be done either by addressing the LSAs to the all-router multicast address on a circuit, where this is possible, or by sending the LSAs separately to each reachable address on the circuit, which resides in a neighbouring router. - If the contents of a single LSA change, that is for example a new neighbour is included in this LSA or the metric of an already existing neighbour has changed, this LSA has to be flooded on all circuits. - If a router knows, that it will stop acting as a router in some time, it shall flood all its LSAs with the Holding Time set to its remaining lifetime. This mechanism accelerates the deletion of LSAs generated by a not longer existent router in the databases of the other routers. Additionally a router, which discovers a new neighbouring router, has to send all stored LSAs, that is the own LSAs and the ones generated by other routers, to this new adjacency in order to enable a fast synchronisation of the new node. In this case and in some of the cases listed above it could be advantageous to delay the immediate transmission of LSAs in order to avoid bursts on the particular circuits. A detailed mechanism for delaying these transmissions is not scope of this document. To avoid unnecessary sending of LSAs, a router can decide to transmit a LSA only on those circuits, on which it has already discovered reachable router adjacencies. 4.4.2 Receiving Link State Advertisements A router receiving a Link State Advertisement first has to execute the validation checks for this message. If it has received a valid advertisement, it has to examine, if the LSA contains newer information than the one stored in the local Link State database. Fritsche, Seifert Expires May 1998 [Page 43]INTERNET DRAFT Dynamical routing for IPv6 November 1997 This would be true in the following cases: - There is no version of a Link State Advertisement from the same Source Address with the same LSA Number stored in the local database. If the Holding Time of the LSA is 0, the router shall discard the advertisement. Else the router has to store a copy of this advertisement along with the specified Source Address in its database and flood the received LSA on all connected circuits except the one, from which it has been received. - There is already a version of a LSA from the same Source Address with the same LSA Number stored in the local database, the Sequence Number of the received version is higher than the one of the stored, and the Holding Time of the received LSA is 0. The router shall flood the received LSA on all connected circuits except the one, from which it has been received. Afterwards it shall delete the stored LSA version. - There is already a version of a LSA from the same Source Address with the same LSA Number stored in the local database, and the Sequence Number of the received version is equal to the number of the stored version increased by 1. If the Change flag of the received version is set to one, the router has to replace the stored LSA with the received one, else it only has to replace the Holding Time and the Sequence Number of the stored LSA with the one contained in the received version. Independent from the value of the Change flag the router has to flood the received LSA on all connected circuits except the one, from which it has been received. - There is already a version of a LSA from the same Source Address with the same LSA Number stored in the local database, and the Sequence Number of the received version is higher than the number of the stored version increased by 1. In this case the router has to compare the contents of the options part of both LSA versions octet for octet. If it has changed, the router has to replace the stored LSA with the received one, else it only has to replace the Holding Time and the Sequence Number of the stored LSA with the one contained in the received version. Independent from the result of the comparison the router has to flood the received LSA on all connected circuits except the one, from which it has been received. In all other cases the Sequence Number of the stored version is equal or higher than the one of the received LSA, that is the received version contains no newer information. Therefore a router has to discard the LSA. If the Sequence Number of the stored LSA is really higher, a router can decide to flood a copy of its stored newer information on the circuit, on which the older LSA version has been received. If a LSA has been forwarded by a router, the Hop Limit field has to be decremented and the Destination Address shall be modified appropriately. Also the router shall decrement the Holding Time of the LSA by the amount of time in seconds, which is estimated to be needed by the LSA on its way from this router to the next hop. All other contents of the LSA have to remain unchanged. Fritsche, Seifert Expires May 1998 [Page 44]INTERNET DRAFT Dynamical routing for IPv6 November 1997 To avoid unnecessary sending of LSAs, a router can decide to transmit a LSA only on those circuits, on which it has already discovered reachable router adjacencies. 4.4.3 Ageing of Routing Information Every router decrements continuously the Holding Times of all LSAs stored in its local Link State database, which it has received from the neighbouring routers. If the Holding Time of a single LSA becomes zero, the router shall increment the Sequence Number of this LSA by 1 and flood the advertisement on all connected circuits. After this procedure the LSA shall be deleted from the local database. This mechanism helps to synchronize the deletion of LSAs throughout the routing area. 4.5 Routing Information on non-multicast-capable links For the distribution of Routing Information on non-multicast-capable links the mechanism described in the previous section has to be modified a little bit. This section discusses one possibility, which would realize this. Since there is no all-routers multicast address on these links, the flooding of a Link State Advertisement means the transmission of a copy of the respective LSA to each router on the link, which is stored as reachable neighbour in the local adjacency database. As Destination Address of the LSA the IPv6 address of the neighbouring router on that link shall be used. These addresses have to be specified in a manual configured list as described above in "Neighbour Discovery on non-multicast-capable links". A second modification affects the periodical retransmission of LSAs. If there are for example some routers of the routing area connected over non-multicast-capable links, each periodically retransmitted LSA from any router in the area also has to be transmitted over these links. In an area with a large number of routers this would cause these links to remain permanently in the busy state and to produce therefore monetary costs, even in the case, if there were no topology changes in the routing area and the transmitted LSAs contain no new information. One way to avoid these unnecessary costs is to transmit a LSA over a non-multicast-capable link only in the case, if the information contained in the LSA is really new, that is LSAs are transmitted over these links only triggered by event and not periodically. Such an event occurs, if - a LSA is transmitted for the first time, that is the LSA isn't already stored in the local Link State database, and the Holding Time isn't 0. - the Sequence Number of the LSA is equal to the Sequence Number of Fritsche, Seifert Expires May 1998 [Page 45]INTERNET DRAFT Dynamical routing for IPv6 November 1997 the already stored version increased by 1, and the Change flag is 1. - the Sequence Number of the LSA is higher than the Sequence Number of the already stored version increased by 1, and the contents of the LSA have really changed. Using this mechanism the Holding Time of a LSA, which has been transmitted at least one time over a non-multicast-capable link, could mistakenly expire, because only versions of the LSA, which contain really new information, will be retransmitted over the non-multicast-capable links and cause a resetting of the Holding Time. To avoid this effect each LSA, which has been at least one time transmitted over a nonmulticast-capable link, must be marked. A router must not decrement the Holding Time of any marked LSA, which is stored in its local database. Such a LSA can only be deleted from a database by receiving explicitly a version of this LSA with higher Sequence Number and a Holding Time set to 0. Nevertheless there remains a problem, if the explicit deletion of a LSA, that is the advertisement with the Holding Time set to 0, cannot be received in particular parts of the routing area. This effect can occur in a temporary partitioned network. If in the temporary unreachable part the expired LSA was marked as transmitted over non-multicast-capable links, the Holding Time will not be locally decremented. Since the explicit deletion has not been received, this LSA mistakenly remains in the respective databases. The probability of this unwanted effect is very low for networks with not too high transmission errors. To remove also these residual errors, it would be possible, that some of the periodically retransmitted LSAs of a router are also transmitted over nonmulticast-capable links, independent if they contain new information or not. For example a router could mark a retransmitted LSA version each Nth retransmission interval. Other routers receiving these marked versions must flood them also on non-multicast capable links. Therefore routers having LSAs stored in their databases, which have been at least one time transmitted over a non-multicast-capable link, can now also use the Holding Time field of these advertisements. The only modification is, that these LSAs are only allowed to be deleted from the database, if the Holding Timer has expired the Nth time without receiving a new version of the LSA. Summarizing all these aspects there is also a way for the distribution of Routing Information on non-multicast-capable links using the same ICMPv6 packet formats and very similar procedures as for multicast-capable links. Therefore each node in the routing area, independent over which kind of link it is connected to the network, will be able to store the same dynamically updated information about the routing area. This condition is absolutely Fritsche, Seifert Expires May 1998 [Page 46]INTERNET DRAFT Dynamical routing for IPv6 November 1997 necessary for the use of efficient dynamical routing algorithms. 4.6 Unicast Routing Algorithm 4.6.1 Introduction The algorithm used herein for the calculation of a routing tree for IPv6 unicast addresses was invented by Dijkstra and is called "shortest path first" (SPF) algorithm. The algorithm uses the information obtained from the Neighbour Discovery and stored in the adjacency database and also the information obtained from the Routing Information distribution and stored in the Link State database. It is executed separately from each router and for each supported routing metric. As result it offers a so called forwarding database for the executing router. This database contains for each reachable IPv6 address residing in a router or a host of the routing area the next hop, which shall be used by the executing router to transmit a data packet on the shortest path to this node. Normally the original SPF algorithm does not support load splitting over multiple paths, but on demand it can be modified to permit load splitting by identifying a set of equal cost paths to each destination node rather than a single least cost path. During the execution of the algorithm the following two databases are used: - PATHS: This represents an acyclic directed graph of shortest paths from the router S performing the calculation. It is stored as a set of triples of the form , where o N is a reachable IPv6 unicast address residing in the routing area. This could be the address of a whole node, or of a single interface of a node. o d(N) is N's distance from S, that is the total metric from S to N. o Adj(N) is the reachable adjacency, that S may use for forwarding to N. Adj(N) has to be the node N itself, or it has to be another router, since host adjacencies cannot be used for forwarding to other destinations. At this place it would be also possible, to store a set of reachable adjacencies to be used from S for reaching N with the same costs. If a node is placed on PATHS, the path designated by its position in the graph is guaranteed to be a shortest path. Therefore PATHS can be used after finishing the execution of the routing algorithm as forwarding database. - TENT: This is a list of triples of the form , where N, d(N), Adj(N) are as defined above for PATHS. TENT can intuitively be thought of as tentative placement of a node in PATHS. In other words, the triple in TENT means that if N were placed in PATHS, d(N) would be x, but N cannot be placed in PATHS until it is guaranteed, that no path Fritsche, Seifert Expires May 1998 [Page 47]INTERNET DRAFT Dynamical routing for IPv6 November 1997 shorter than x exists. This algorithm is a quite good solution for routing unicast packets, because - it is a dynamical routing algorithm, - the calculation of the routing algorithm is not centralized, - it avoids the generation of infinite loops during the routing of unicast packets, - it doesn't have a too high computing complexity, and - it calculates the optimal (shortest) path from a source to a destination for a given metric. 4.6.2 Overview of the algorithm The basic algorithm, which builds PATHS from scratch, starts by putting all unicast addresses of the node doing the computation on PATHS, since there could be no shorter path to SELF. TENT is then preloaded from the local adjacency database. Note, that a node is not placed in PATHS unless no shorter path to that node exists. When a node N is placed in PATHS, the path to each neighbour M of N, through N, is examined, as the path to N plus the link from N to M. If is already in PATHS, this new paths will be longer, and thus ignored. If is in TENT, and the new path is shorter, the old entry is removed from TENT and the new path is placed in TENT. If the new path has the same length as the one in TENT, or if it is longer, the old entry shall be kept unchanged in TENT. If load splitting would be supported, and there would be a path with equal length in TENT, then the set of possible adjacencies to M {Adj(M)} would be the union of the old set in TENT and the new set {Adj(N)}. If M is not in TENT, the path is now added to TENT. Next the algorithm finds the triple in TENT, with minimal x. For this step it is recommendable, to keep the entries of TENT stored in a sorted order, starting with the entry with the lowest distance x. N is placed in PATHS. Here the executing router knows, that no path to N can be shorter than x at this point, because all paths through nodes already in PATHS have already been considered, and paths through nodes in TENT will have to be greater than x, because x is minimal in TENT. When TENT is empty, PATHS is complete and can be used as forwarding database. Fritsche, Seifert Expires May 1998 [Page 48]INTERNET DRAFT Dynamical routing for IPv6 November 1997 4.6.3 Steps of the algorithm There are three main steps of the algorithm separable: o Initialisation (Step 0) o Evaluation of the LSAs (Step 1) o Selection of the shortest distance (Step 2). In the following the single steps are described in more detail. Step 0: a) Initialise TENT and PATHS as empty. b) Add to PATHS, where SELF are the IPv6 addresses of the computing router and W is a special value indicating traffic to SELF is passed up to the Transport Layer. c) Now pre-load TENT with all neighbour nodes N of SELF. This could be done by reading the local adjacency database. If the node N is a router, the IPv6 address on behalf of which N will generate its LSAs (contained as LSA information option in the Router Advertisements of N) is stored for N. If N is a host, the Source Address of the Host Advertisements, which caused the creation of the adjacency, is used. The distance x to the neighbour N is the metric stored with the respective adjacency. Adj(N) is the adjacency itself to the neighbour node N, that is the adjacency, which has been stored in the adjacency database as result of the receipt of an advertisement. Each entry made to TENT must be marked as being either a router or a host to enable the check at the end of Step 2 to be made correctly. d) If a neighbour node is already in TENT, compare the distance of the old and the new entry and keep only the entry with the shorter distance. e) If a neighbour node is not in TENT, then place it now. f) If all neighbour nodes contained in the local adjacency database are examined, go to Step 2. Step 1: a) Now examine all neighbour nodes N listed in all LSAs of P, the node just placed in PATHS (P has been placed in PATHS during the last execution of Step 2). The distance x of a node N to the executing router SELF is the metric of the link from P to N plus the distance from SELF to P. The adjacency to N, Adj(N), is the same as the one to P, Adj(P), because N could be reached from the computing router over P. b) If a neighbour node is already in PATHS, then do nothing. c) If a neighbour node is already in TENT, compare the distances of the old and the new entry and keep only the entry with the shorter distance. d) If a neighbour node is not in TENT, then place it now. Step 2: a) If TENT is empty, then stop the computation (now all reachable nodes of the routing area are placed in PATHS). b) Else find the element for which the distance x from the executing router SELF is the shortest among all entries in Fritsche, Seifert Expires May 1998 [Page 49]INTERNET DRAFT Dynamical routing for IPv6 November 1997 TENT. c) Remove P from TENT. d) Add to PATHS, with d(n) = x. e) If the node just added to PATHS was a host, then go back to Step 2, else go to Step 1. In the second case of e) a router has been added to PATHS. Before searching the next nearest node to the executing router, the adjacencies of the just added router P have to be examined by checking P's LSAs. When the algorithm is finished, PATHS can be used as a unicast forwarding database containing all the nodes of the routing area, which are reachable from the computing router. Fritsche, Seifert Expires May 1998 [Page 50]INTERNET DRAFT Dynamical routing for IPv6 November 1997 5 Dynamical routing of multicast packets in IPv6 5.1 Introduction The main goal for the use of multicasting in a network is to save bandwidth when transmitting data from a source to a group of receivers. Using unicasting the source would have to transmit a single copy of each data packet to each of the receivers. Many of these copies probably would be transmitted unnecessarily over the same circuits. This waste of bandwidth can be avoided, if the data is addressed to a multicast address instead of a set of unicast addresses. Each router, which receives such a multicast packet, has to decide locally, if the data has to be sent over only one circuit towards the intended receivers, or if the packet has to be copied and transmitted over more circuits. This method guarantees, that on each circuit only one copy of a packet with the same content is transmitted. To do this local decision, each router has to be informed about the contents of a multicast address, that is it has to know exactly, which set of IPv6 unicast addresses are member of an Address Group specified by a particular multicast address. This proposal defines three ICMPv6 packet formats, which can be used for the modification of these Address Groups and their distribution over the network. These are Host Group Membership Queries, which are used to send group information from hosts to routers, Router Group Membership Reports, which transmit group information from routers to hosts, and Router Group Distribution Messages, which distribute group information among the routers themselves. The exact format of these packets and their use is described in detail later in this chapter. All those packets aren't transmitted periodically, but only by event, that is there must be a modification of an Address Group. This is done in order to use not to much of the bandwidth saved by multicasting for additional necessary control information. Also this proposal defines two different modes of distributing group information, the mandatory and the optional mode. In the mandatory mode hosts have only the possibility, to join or to leave an existing Address Group. They are not informed by means of this proposal about the Address Groups existing at a particular moment and their members, that is hosts don't store group information in a local database. This knowledge is only present in routers. Also Host Group Membership Queries, Router Group Membership Reports and Router Group Distribution Messages don't carry the new complete composition of a modified Address Group, but only the changes between the new and the old group version. Executing the mandatory mode restricts the security aspects of hosts, since they have no Fritsche, Seifert Expires May 1998 [Page 51]INTERNET DRAFT Dynamical routing for IPv6 November 1997 information about the possible receivers of a packet destined for a multicast address. Additionally this mode increases the risk of different group information stored in the group databases of the routers. If there is one time a difference in a group composition between two databases, this difference probably will continue, since all following ICMPv6 packets referring to this particular group contain only new modifications, but no complete composition of the Address Group itself. The advantage of the mandatory mode is, that only this information is exchanged, which is absolutely necessary for enabling the correct routing of multicast packets, and therefore the maximum amount of bandwidth is saved. In the optional mode hosts and routers have the same possibilities of modifying Address Groups. Host Group Membership Queries, Router Group Membership Reports and Router Group Distribution Messages always contain a complete composition of the modified Address Group, what enables a synchronisation of all group databases referring to the Address Group specified in the respective ICMPv6 packet. Also routers exchange with hosts the same group information as among themselves. Therefore hosts are fully informed about all existing Address Groups and their composition, and know exactly, which group of receivers a multicast packet probably will receive. To provide the interoperability between nodes exchanging ICMPv6 group information it has to be guaranteed, that all nodes participating in this exchange support the same mode. To mark in an ICMPv6 group information packet, if it contains a complete group composition, or only one or more changes of an already existing Address Group, a so called Modification Flag is present in each packet. This flag can have one of the following values: - 0: 0 means, that the respective ICMPv6 packet contains a complete group composition. In the optional mode only packets with the Modification Flag set to this value are exchanged. - 1: 1 means, that the respective ICMPv6 packet contains one or more IPv6 addresses, which want to join to an existing Address Group. In the mandatory mode between hosts and routers only packets with the Modification Flag set to 1 or 2 are exchanged. Routers exchange in this mode among themselves also packets with the Modification Flag set to 0 for the creation of new Address Groups and the deletion of existing ones, but they do not use this flag set to zero for the modification of existing groups. - 2: 2 means, that the respective ICMPv6 packet contains one or more IPv6 addresses, which want to leave an existing Address Group. In the mandatory mode between hosts and routers only packets with the Modification Flag set to 1 or 2 are exchanged. Routers exchange in this mode among themselves also packets with the Modification Flag set to 0 for the creation of new Address Groups and the deletion of existing ones, but they do not use this flag set to zero for the Fritsche, Seifert Expires May 1998 [Page 52]INTERNET DRAFT Dynamical routing for IPv6 November 1997 modification of existing groups. 5.2 Functions needed for multicasting in IPv6 5.2.1 Overview This section lists the new functions needed by routers and hosts to support the distribution of Address Group information. As mentioned above, the distribution takes place by exchanging ICMPv6 packets between nodes, which contain information about a particular Address Group. The format of these control packets is specified in the next section. Each packet contains the IPv6 Multicast Address of the group, to which this information refers, and a Sequence Number, which indicates the topicality of the information, that is information with higher Sequence Number replaces information with lower one. Also each control packet includes a Modification Flag, which specifies, if there is a complete composition of an Address Group present in a control packet (Modification Flag is 0), or only a part of group members, which newly joined (Modification Flag is 1) or left (Modification Flag is 2) an existing group. Which of the functions described in this chapter are supported by routers and hosts depends on the respective mode, in which the distribution of multicast information is executed in a particular node. All nodes in the area, in which Group Address information shall be distributed, have to do this in the same mode. If a node receives control packets indicating, that the originator supports an other mode, it shall discard these information. 5.2.2 Create Address Group Function This function is executed by hosts supporting the optional mode and by routers supporting either the optional or the mandatory mode. If a node is informed about the new generation of an Address Group, it distributes the information over its connected subnetworks by executing the Create Address Group Function. A creation of a new group is detected, either if information about an Address Group, which isn't locally stored, has been received from an other node, and this group isn't empty, or if the group creation is initiated explicitly by the local management. 5.2.2.1 Create Address Group Function for hosts If a host receives by means of its management the information about the generation of a new Address Group, it transmits the group composition using a Host Group Membership Query to one of its Fritsche, Seifert Expires May 1998 [Page 53]INTERNET DRAFT Dynamical routing for IPv6 November 1997 connected routers. In this query the Sequence Number is set to 1 and the packet contains the complete composition of the group, why the Modification Flag is set to 0. The Number of Group Members field contains the number of all members of this Address Group. The transmitted Host Group Membership Query will be acknowledged by a Router Group Membership Report from the addressed router with the same informational contents. 5.2.2.2 Create Address Group Function for routers A router can be informed about a newly generated group by means of its management, by the receipt of a Router Group Distribution Message or in the optional mode also by the receipt of a Host Group Membership Query. Supporting the mandatory mode a router distributes this information to all its connected neighbour routers by Router Group Distribution Messages. If the router itself has received the information by an other Router Group Distribution Message, it doesn't send back a message to the originating router. Supporting the optional mode a router additionally distributes the newly created Address Group to all its connected hosts using Router Group Membership Reports. If the router itself was informed about the group by a Host Group Membership Query, the return of a Router Group Membership Report with the same contents also back to the originator of the query can be seen as an acknowledgement. In Router Group Distribution Messages as well as in Router Group Membership Reports the Sequence Number is set to 1 and the packet contains the complete composition of the group, why the Modification Flag is set to 0. The Number of Group Members field contains the number of all members of this Address Group. 5.2.3 Modify Address Group Function This function is executed by hosts and routers supporting the optional mode. If a node is informed about the modification of an already stored Address Group, it distributes the information over its connected subnetworks by executing the Modify Address Group Function. A modification of an existing group is detected, either if the Sequence Number of a stored group version is lower than the Sequence Number of a newly received group version from an other node, and this new group version isn't empty, or if the group modification is initiated explicitly by the local management. Fritsche, Seifert Expires May 1998 [Page 54]INTERNET DRAFT Dynamical routing for IPv6 November 1997 5.2.3.1 Modify Address Group Function for hosts If a host receives by means of its management the information about the modification of an already stored Address Group, it transmits the modified group composition using a Host Group Membership Query to one of its connected routers. In this query the Sequence Number is set to the value of the Sequence Number locally stored for this group increased by 1, and the packet contains the complete composition of the group, why the Modification Flag is set to 0. The Number of Group Members field contains the number of all members of this modified Address Group. The transmitted Host Group Membership Query will be acknowledged by a Router Group Membership Report from the addressed router with the same informational contents. 5.2.3.2 Modify Address Group Function for routers Only a router supporting the optional mode can be informed about a modified group by means of its management, by the receipt of a Router Group Distribution Message or by the receipt of a Host Group Membership Query. A router distributes this information to all its connected neighbour routers by Router Group Distribution Messages. If the router itself has received the information by an other Router Group Distribution Message, it doesn't send back a message to the originating router. Additionally a router transmits the modified Address Group to all its connected hosts using Router Group Membership Reports. If the router itself was informed about the modification by a Host Group Membership Query, the return of a Router Group Membership Report with the same contents also back to the originator of the query can be seen as an acknowledgement. In Router Group Distribution Messages as well as in Router Group Membership Reports the Sequence Number is set to the new value of the Sequence Number or, in the case of group modification by the local management, to the value locally stored for the old group version increased by 1. The packet contains the complete new composition of the group, why the Modification Flag is set to 0. The Number of Group Members field contains the number of all members of this Address Group. 5.2.4 Delete Address Group Function This function is executed by hosts supporting the optional mode and by routers supporting either the optional or the mandatory mode. If a node is informed about the deletion of an Address Group, it distributes the information over its connected subnetworks by Fritsche, Seifert Expires May 1998 [Page 55]INTERNET DRAFT Dynamical routing for IPv6 November 1997 executing the Delete Address Group Function. A deletion of a group is detected, either if the Sequence Number of a stored group version is lower than the Sequence Number of a newly received group version from an other node, and the new group version is empty, or if the group deletion is initiated explicitly by the local management. 5.2.4.1 Delete Address Group Function for hosts If a host receives by means of its management the information about the deletion of an already stored Address Group, it transmits the information about this event using a Host Group Membership Query to one of its connected routers. In this query the Sequence Number is set to the value of the Sequence Number locally stored for this group increased by 1, and the packet contains the complete composition of the group, why the Modification Flag is set to 0. Of course, in this case the group composition consists only of the IPv6 Multicast Address of the Address Group. The Number of Group Members field contains the number of all members of the deleted group, that is here zero. The transmitted Host Group Membership Query will be acknowledged by a Router Group Membership Report from the addressed router with the same informational contents. 5.2.4.2 Delete Address Group Function for routers A router can be informed about a deleted group by means of its management, by the receipt of a Router Group Distribution Message or in the optional mode also by the receipt of a Host Group Membership Query. Supporting the mandatory mode a router distributes this information to all its connected neighbour routers by Router Group Distribution Messages. If the router itself has received the information by an other Router Group Distribution Message, it doesn't send back a message to the originating router. Supporting the optional mode a router additionally distributes the information about the deleted Address Group to all its connected hosts using Router Group Membership Reports. If the router itself was informed about the deletion by a Host Group Membership Query, the return of a Router Group Membership Report with the same contents also back to the originator of the query can be seen as an acknowledgement. In Router Group Distribution Messages as well as in Router Group Membership Reports the Sequence Number is set to the new value of the Sequence Number or, in the case of group modification by the local management, to the value locally stored for the old group version increased by 1. The packet contains the complete composition of the Fritsche, Seifert Expires May 1998 [Page 56]INTERNET DRAFT Dynamical routing for IPv6 November 1997 group, why the Modification Flag is set to 0. Of course, in this case the group composition consists only of the IPv6 Multicast Address of the Address Group. The Number of Group Members field contains the number of all members of this Address Group, that is here zero. 5.2.5 Join Address Group Function This function is executed only by routers and hosts supporting the mandatory mode. If a node has the information about some IPv6 addresses, which want to join to an existing Address Group, it distributes the information over its connected subnetworks by executing the Join Address Group Function. The joining to a group is detected, either if the Sequence Number of a stored group version is lower than the Sequence Number of a newly received Router Group Distribution Message from an other router about some new IPv6 addresses, which want to become member of the stored group, or if a Host Group Membership Query has been received containing one or more joining group members (in this case the Sequence Number is not important, since hosts have no knowledge about the actual value in this mode), or finally if the group joining is initiated explicitly by the local management. 5.2.5.1 Join Address Group Function for hosts If a host receives by means of its management the information about some IPv6 addresses, which want to join to an already stored Address Group, it transmits the information about this event using a Host Group Membership Query to one of its connected routers. In this query the Sequence Number is set to zero, since hosts don't store any information about groups in the mandatory mode. The packet contains only the IPv6 addresses of the joining group members, why the Modification Flag is set to 1. Of course, additionally the IPv6 Multicast Address itself is present like in any Host Group Membership Query. The Number of Group Members field contains the number of all members, which are newly added to the respective group. The transmitted Host Group Membership Query will be acknowledged by a Router Group Membership Report from the addressed router with the same informational contents. 5.2.5.2 Join Address Group Function for routers A router can be informed about one or more IPv6 addresses, which want to join to an already stored Address Group, by means of its management, by the receipt of a Router Group Distribution Message or by the receipt of a Host Group Membership Query. A router distributes this information to all its connected neighbour Fritsche, Seifert Expires May 1998 [Page 57]INTERNET DRAFT Dynamical routing for IPv6 November 1997 routers by Router Group Distribution Messages. If the router itself has received the information by an other Router Group Distribution Message, it doesn't send back a message to the originating router. If the router has received the information by a Host Group Membership Query, it additionally transmits the information about the newly joining group members back to the originator of the query using a Router Group Membership Report, what can be seen as an acknowledgement. In all other cases hosts are not informed about new members, since in the mandatory mode a host doesn't store any group information. In Router Group Distribution Messages the Sequence Number is set to the new value of the Sequence Number or, in the case of initiating the joining of new group members by the local management, to the value locally stored for the old group version increased by 1. In Router Group Membership Reports the Sequence Number is set to zero, since it is not used from hosts. The distribution message and the membership report packets contain only the IPv6 addresses of the joining group members, why the Modification Flag is set to 1. Of course, additionally the IPv6 Multicast Address itself is present like in any packet. The Number of Group Members field contains the number of all members, which are newly added to the respective group. 5.2.6 Leave Address Group Function This function is executed only by routers and hosts supporting the mandatory mode. If a node has the information about some IPv6 addresses, which want to leave an existing Address Group, it distributes the information over its connected subnetworks by executing the Leave Address Group Function. The leaving from a group is detected, either if the Sequence Number of a stored group version is lower than the Sequence Number of a newly received Router Group Distribution Message from an other router about some IPv6 addresses, which want to leave the stored group, or if a Host Group Membership Query has been received containing one or more leaving group members (in this case the Sequence Number is not important, since hosts have no knowledge about the actual value in this mode), or finally if the group leaving is initiated explicitly by the local management. 5.2.6.1 Leave Address Group Function for hosts If a host receives by means of its management the information about some IPv6 addresses, which want to leave an already stored Address Group, it transmits the information about this event using a Host Group Membership Query to one of its connected routers. In this query the Sequence Number is set to zero, since hosts don't store any information about groups in the mandatory mode. The packet contains only the IPv6 addresses of the leaving group members, why the Modification Flag is set to 2. Of course, additionally the IPv6 Fritsche, Seifert Expires May 1998 [Page 58]INTERNET DRAFT Dynamical routing for IPv6 November 1997 Multicast Address itself is present like in any Host Group Membership Query. The Number of Group Members field contains the number of all members, which want to leave the respective group. The transmitted Host Group Membership Query will be acknowledged by a Router Group Membership Report from the addressed router with the same informational contents. 5.2.6.2 Leave Address Group Function for routers A router can be informed about one or more IPv6 addresses, which want to leave an already stored Address Group, by means of its management, by the receipt of a Router Group Distribution Message or by the receipt of a Host Group Membership Query. A router distributes this information to all its connected neighbour routers by Router Group Distribution Messages. If the router itself has received the information by an other Router Group Distribution Message, it doesn't send back a message to the originating router. If the router has received the information by a Host Group Membership Query, it additionally transmit the information about the leaving group members back to the originator of the query using a Router Group Membership Report, what can be seen as an acknowledgement. In all other cases hosts are not informed about leaving members, since in the mandatory mode a host doesn't store any group information. In Router Group Distribution Messages the Sequence Number is set to the new value of the Sequence Number or, in the case of initiating the leaving of group members by the local management, to the value locally stored for the old group version increased by 1. In Router Group Membership Reports the Sequence Number is set to zero, since it is not used from hosts. The distribution message and the membership report packets contain only the IPv6 addresses of the leaving group members, why the Modification Flag is set to 2. Of course, additionally the IPv6 Multicast Address itself is present like in any packet. The Number of Group Members field contains the number of all members, which want to leave the respective group. 5.2.7 Record Host Group Membership Query Function The Record Host Group Membership Query function is executed only from routers. It receives the group information, which is distributed from hosts within Host Group Membership Queries, and updates the information in the local group database. A query is only processed by a router, if it was generated from a host supporting the same mode as the router. This condition is kept in the following two cases: - The router supports the mandatory mode, and the received query Fritsche, Seifert Expires May 1998 [Page 59]INTERNET DRAFT Dynamical routing for IPv6 November 1997 contains information about one or more IPv6 addresses joining or leaving a locally stored Address Group, that is the Modification Flag of the query is set to 1 or 2. - The router supports the optional mode, and the received query contains information about the creation, the modification or the deletion of an Address Group, that is the Modification Flag is set to 0. If no one of these both conditions is kept, the query will be discarded without further action. If the router decides to process the query, it checks in the next step, whether the group information contained in this packet is newer than the one stored in the local group database. This applies in the following four cases: - The query contains information about the creation of a group, which isn't already stored in the local group database. - The query contains information about the modification or deletion of an already locally stored group, and the Sequence Number of the query is higher than the one stored for this group. - The query contains information about one or more IPv6 addresses, which want to join to a locally stored Address Group. If the addresses are already members of this group, the query isn't further processed. - The query contains information about one or more IPv6 addresses, which want to leave a locally stored Address Group. If the addresses aren't member of this group, the query isn't further processed. If no one of these four conditions is kept, the query will be discarded without further action. Otherwise this new group composition information is locally stored in the group database. If the router supports the mandatory mode, the query is acknowledged by sending a Router Group Membership Report with the same contents back to the host, which generated the query, and a Router Group Distribution Message containing the joining or leaving members is sent to all connected neighbouring routers. If the router supports the optional mode, a Router Group Membership Report with the same contents is sent to all hosts on the subnetwork the query was received, and a Router Group Distribution Message containing the complete new group composition is sent to all connected neighbouring routers. In this way also the host, which has generated the query, receives a copy of the Router Group Membership Report as an acknowledgement. 5.2.8 Record Router Group Membership Report Function The Record Router Group Membership Report function is executed only from hosts. It receives the group composition information, which is distributed from routers within Router Group Membership Reports, and Fritsche, Seifert Expires May 1998 [Page 60]INTERNET DRAFT Dynamical routing for IPv6 November 1997 updates the information in the local group database. A report is only processed by a host, if it was generated from a router supporting the same mode as the host. This condition is kept in the following two cases: - The host supports the mandatory mode, and the received report contains information about one or more IPv6 addresses joining or leaving a locally stored Address Group, that is the Modification Flag of the report is set to 1 or 2. This report has been sent by the router as an acknowledgement for a previously sent Host Group Membership Query. - The host supports the optional mode, and the received report contains information about the creation, the modification or the deletion of an Address Group, that is the Modification Flag is set to 0. If no one of these both condition is kept, the report will be discarded without further action. If the host decides to process the report, it checks in the next step, if the group composition information contained in this packet is newer than the one stored in the local group database. This is only possible, if the host supports the optional mode. In the mandatory mode such reports contain never new group composition information, but an acknowledgement for a previously sent Host Group Membership Query. Therefore only in the following two cases newer group composition information is received: - The report contains information about the creation of a group, which isn't already stored in the local group database. - The report contains information about the modification or deletion of an already locally stored group, and the Sequence Number of the report is higher than the one stored for this group. If no one of these both conditions is kept, the report will be discarded without further action. Otherwise this new group composition information is locally stored in the group database. 5.2.9 Record Router Group Distribution Message Function The Record Router Group Distribution Message function is executed only from routers. It receives the group information, which is distributed from other routers within Router Group Distribution Messages, and updates the information in the local group database. A message is only processed by a router, if it was generated from an other router supporting the same mode. This condition is kept in the following two cases: - The receiving router supports the mandatory mode, and the received message contains either information about one or more IPv6 Fritsche, Seifert Expires May 1998 [Page 61]INTERNET DRAFT Dynamical routing for IPv6 November 1997 addresses joining or leaving a locally stored Address Group, that is the Modification Flag of the message is set to 1 or 2, or it contains information about the creation or the deletion of an Address Group, that is the Modification Flag is 0. - The receiving router supports the optional mode, and the received message contains information about the creation, the modification or the deletion of an Address Group, that is the Modification Flag is set to 0. If no one of these both conditions is kept, the message will be discarded without further action. If the router decides to process the message, it checks in the next step, whether the group information contained in this packet is newer than the one stored in the local group database. This applies in the following four cases: - The message contains information about the creation of a group, which isn't already stored in the local group database. - The message contains information about the modification or deletion of an already locally stored group, and the Sequence Number of the message is higher than the one stored for this group. - The message contains information about one or more IPv6 addresses, which want to join to a locally stored Address Group, and the Sequence Number of the message is higher than the one stored for this group. - The message contains information about one or more IPv6 addresses, which want to leave a locally stored Address Group, and the Sequence Number of the message is higher than the one stored for this group. If no one of these four conditions is kept, the message will be discarded without further action. Otherwise this new group composition information is locally stored in the group database. If the router supports the mandatory mode, this message is further forwarded to all neighbouring routers except the one it was received from, that is there is no acknowledgement mechanism for Router Group Distribution Messages. If the router supports the optional mode, additionally a Router Group Membership Report containing the modifications of the Address Group is sent to all hosts connected to the router. 5.2.10 Summary Finally the following two tables shall give an overview, which of the functions specified above have to be executed by routers and hosts in each of the two possible modes. Fritsche, Seifert Expires May 1998 [Page 62]INTERNET DRAFT Dynamical routing for IPv6 November 1997 +-------------------------------------------------------------------+ | Functionality | Mode |Modification| Contents of packet | | | | Flag | | +----------------------+---------+------------+---------------------+ |Create Address Group |Mandatory| 0 |Multicast Address and| | |Optional | |IPv6 addresses of all| | | | | members | |Modify Address Group |Optional | 0 |Multicast Address and| | | | |IPv6 addresses of all| | | | | members | |Delete Address Group |Mandatory| 0 | Multicast Address | | |Optional | | | |Join Address Group |Mandatory| 1 |Multicast Address and| | | | |IPv6 addresses of all| | | | | added members | |Leave Address Group |Mandatory| 2 |Multicast Address and| | | | |IPv6 addresses of all| | | | | added members | |Record Host Group |Mandatory| --- | --- | |Membership Query |Optional | | | |Record Router Group |Mandatory| --- | --- | |Distribution Message |Optional | | | +----------------------+---------+------------+---------------------+ Table: Functionality supported by routers +-------------------------------------------------------------------+ | Functionality | Mode |Modification| Contents of packet | | | | Flag | | +----------------------+---------+------------+---------------------+ |Create Address Group |Optional | 0 |Multicast Address and| | | | |IPv6 addresses of all| | | | | members | |Modify Address Group |Optional | 0 |Multicast Address and| | | | |IPv6 addresses of all| | | | | members | |Delete Address Group |Optional | 0 | Multicast Address | |Join Address Group |Mandatory| 1 |Multicast Address and| | | | |IPv6 addresses of all| | | | | added members | |Leave Address Group |Mandatory| 2 |Multicast Address and| | | | |IPv6 addresses of all| | | | | added members | |Record Router Group |Mandatory| --- | --- | |Membership Report |Optional | | | +----------------------+---------+------------+---------------------+ Table: Functionality supported by hosts Fritsche, Seifert Expires May 1998 [Page 63]INTERNET DRAFT Dynamical routing for IPv6 November 1997 5.3 ICMPv6 Informational Group Messages This section defines the encoding of the three ICMPv6 packets, which are used for the distribution of group information. 5.3.1 Host Group Membership Query Host Group Membership Queries are used by hosts to advertise to one of their connected routers, that they want to modify an Address Group. These queries aren't sent periodically, but by an event. A host can execute two different modes of Group Address modification: - Mandatory mode: In this mode a host can only advertise to a router by using these queries, that it will join or leave an Address Group. - Optional mode: In this mode a host can advertise to a router by using these queries, that it will create, delete or completely modify an Address Group. These queries can also be used for transmitting all stored Address Group information to newly connected routers. Which host is authenticated to execute which Address Group modifications is not scope of this proposal. The following figure shows the format of a Host Group Membership Query: 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +---------------+---------------+-------------------------------+ | Type | Code | Checksum | +---------------+---------------+-------------------------------+ | Modific. Flag | Unused | Unused | +---------------+---------------+-------------------------------+ | Sequence Number | +---------------------------------------------------------------+ | Number of Group Members | +---------------------------------------------------------------+ | Multicast Address | +---------------------------------------------------------------+ | Address of Group Member | +---------------------------------------------------------------+ ... +---------------------------------------------------------------+ | Address of Group Member | +---------------------------------------------------------------+ IPv6 Fields: Source Address: 128-bit address of the originator of the packet. Fritsche, Seifert Expires May 1998 [Page 64]INTERNET DRAFT Dynamical routing for IPv6 November 1997 Destination Address: 128-bit address of the "nearest" router attached to the link, over which this query is transmitted. The nearest router is always the one reachable with the lowest metric. If two routers are reachable with the same metric, the query messages shall be transmitted to the one with the numerically lower IPv6 address. Hop Limit: 255 Priority: 15 Authentication Header: If a Security Association for the IP Authentication Header exists between the source and the destination address, then the source shall include this header. ICMPv6 Fields: Type: 130 - Group Membership Information Code: 1 - Host Group Membership Query Modification Flag: The Modification Flag describes the kind of modification of an Address Group. This flag can have one of the following three values: 0: This message contains a complete composition of the Address Group specified by the Multicast Address, that is an Address Group is newly created, completely modified or deleted (optional mode). 1: This message contains only the addresses of one host, which wants to become a member of the Address Group specified by the Multicast Address (mandatory mode). 2: This message contains only the addresses of one host, which wants to leave the Address Group specified by the Multicast Address (mandatory mode). Sequence Number: This number describes the topicality of the group modification contained in this Host Group Membership Query. Information with higher Sequence Numbers replace information with lower ones. If a host supports the mandatory mode, it has no information about the composition of an Address Group. Therefore it will set this field to zero. Number of Group Members: Running the optional mode this field contains the number of all members of the Address Group. In the mandatory mode it contains only the number of the members, which shall be added or deleted from the Address Group. Multicast Address: The IPv6 Multicast Address of the Address Group, to which this Host Group Membership Fritsche, Seifert Expires May 1998 [Page 65]INTERNET DRAFT Dynamical routing for IPv6 November 1997 Query refers. Address of Group Member: In the optional mode the Host Group Membership Query contains the IPv6 addresses of all members of the Address Group. In the mandatory mode only the addresses of those members are contained, which are newly added or deleted from the respective group. 5.3.2 Router Group Membership Report Router Group Membership Reports are used by routers either to advertise to their connected hosts, that an Address Group has been modified, or to acknowledge a previously received Host Group Membership Query. These reports aren't sent periodically, but by an event. A router can execute two different modes of Address Group modification: - Mandatory mode: In this mode a router uses these reports only to acknowledge previously received Host Group Membership Queries, which contained the information, that a host has joined or left an Address Group. This report is sent only to the originator of the Host Group Membership Query. - Optional mode: In this mode a router can advertise to all of its connected hosts by using these queries, that an Address Group has been created, deleted or completely modified. This modification could have been initiated by a router or a host. These reports can also be used for transmitting all stored Address Group information to newly connected hosts. The following figure shows the format of a Router Group Membership Report: 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +---------------+---------------+-------------------------------+ | Type | Code | Checksum | +---------------+---------------+-------------------------------+ | Modific. Flag | Unused | Unused | +---------------+---------------+-------------------------------+ | Sequence Number | +---------------------------------------------------------------+ | Number of Group Members | +---------------------------------------------------------------+ | Multicast Address | +---------------------------------------------------------------+ | Address of Group Member | +---------------------------------------------------------------+ ... +---------------------------------------------------------------+ | Address of Group Member | +---------------------------------------------------------------+ Fritsche, Seifert Expires May 1998 [Page 66]INTERNET DRAFT Dynamical routing for IPv6 November 1997 IPv6 Fields: Source Address: 128-bit address of the originator of the packet. Destination Address: Running the mandatory mode this Router Group Membership Report is only an acknowledgement for a previously received Host Group Membership Query. Therefore the Destination Address is copied from the Source Address field of the respective Host Group Membership Query. Running the optional mode, the modification of an Address Group is distributed to all hosts connected to a particular link. Therefore the Destination Address is set to the all-hosts multicast address of this link. Hop Limit: 255 Priority: 15 Authentication Header: If a Security Association for the IP Authentication Header exists between the source and the destination address, then the source shall include this header. ICMPv6 Fields: Type: 130 - Group Membership Information Code: 2 - Router Group Membership Report Modification Flag: The Modification Flag describes the kind of modification of an Address Group. This flag can have one of the following three values: 0: This message contains a complete composition of the Address Group specified by the Multicast Address, that is an Address Group is newly created, completely modified or deleted (optional mode). 1: This message contains only the addresses of one host, which has required to become a member of the Address Group specified by the Multicast Address (mandatory mode). 2: This message contains only the addresses of one host, which has required to leave the Address Group specified by the Multicast Address (mandatory mode). Sequence Number: This number describes the topicality of the group modification contained in this Router Group Membership Report. Information with higher Sequence Numbers replace information with lower ones. If a router supports the mandatory mode, this field is set to zero, Fritsche, Seifert Expires May 1998 [Page 67]INTERNET DRAFT Dynamical routing for IPv6 November 1997 since the addressed host has no information about the composition of an Address Group or the actual Sequence Number. Number of Group Members: Running the optional mode this field contains the number of all members of the Address Group. In the mandatory mode it contains only the number of the members, which shall be newly added or deleted from the Address Group. Multicast Address: The IPv6 Multicast Address of the Address Group, to which this Router Group Membership Report refers. Address of Group Member: In the optional mode the Router Group Membership Report contains the IPv6 addresses of all members of the Address Group. In the mandatory mode only the addresses of those members are contained, which have requested to be newly added or deleted from the respective group. 5.3.3 Router Group Distribution Message Router Group Distribution Messages are used among routers to distribute Address Group modification information. These messages aren't sent periodically, but by an event. A router can execute two different modes of Address Group modification: - Mandatory mode: In this mode a router uses these messages to transmit to its connected routers the information, that one or more hosts have newly joined or left an Address Group. Therefore in this case the message contains no complete Address Group composition, but only the respective hosts. Also in this mode a router can transmit the information, that an Address Group has been created or deleted, what requires a message containing a complete group composition. - Optional mode: In this mode a router uses these messages to transmit to its connected routers the information, that an Address Group has been created, deleted or completely modified. Therefore in this case the message contains always a complete Address Group composition. In both modes all stored Address Group information is transmitted to newly connected routers. The following figure shows the format of a Router Group Distribution Message: Fritsche, Seifert Expires May 1998 [Page 68]INTERNET DRAFT Dynamical routing for IPv6 November 1997 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +---------------+---------------+-------------------------------+ | Type | Code | Checksum | +---------------+---------------+-------------------------------+ | Modific. Flag | Unused | Unused | +---------------+---------------+-------------------------------+ | Sequence Number | +---------------------------------------------------------------+ | Number of Group Members | +---------------------------------------------------------------+ | Multicast Address | +---------------------------------------------------------------+ | Address of Group Member | +---------------------------------------------------------------+ ... +---------------------------------------------------------------+ | Address of Group Member | +---------------------------------------------------------------+ IPv6 Fields: Source Address: 128-bit address of the originator of the packet. Destination Address: Since Router Group Distribution Messages are used to distribute the information of a group composition throughout a routing area, this message is addressed to the all-router multicast address of the link, over which it is transmitted. Hop Limit: 255 Priority: 15 Authentication Header: If a Security Association for the IP Authentication Header exists between the source and the destination address, then the source shall include this header. ICMPv6 Fields: Type: 130 - Group Membership Information Code: 3 - Router Group Distribution Message Modification Flag: The Modification Flag describes the kind of modification of an Address Group. This flag can have one of the following three values: 0: This message contains a complete composition of the Address Group specified by the Multicast Address, that is an Address Group is newly created or deleted (optional or mandatory mode), or it has been completely modified (optional mode). Fritsche, Seifert Expires May 1998 [Page 69]INTERNET DRAFT Dynamical routing for IPv6 November 1997 1: This message contains only the addresses of one node, which has required to become a member of the Address Group specified by the Multicast Address (mandatory mode). 2: This message contains only the addresses of one node, which has required to leave the Address Group specified by the Multicast Address (mandatory mode). Sequence Number: This number describes the topicality of the group modification contained in this Router Group Distribution Message. Information with higher Sequence Numbers replace information with lower ones. Since Router Group Distribution Messages are only exchanged between routers, this field is never set to zero, because routers keep track with the respective Sequence Numbers of Address Groups. Number of Group Members: Running the optional mode this field contains the number of all members of the Address Group. In the mandatory mode it contains only the number of the members, which shall be newly added or deleted from the Address Group, if the Modification Flag is set to 1 or 2. If this flag is set to 0 (creation or deletion of an Address Group), this field contains the number of all members. Multicast Address: The IPv6 Multicast Address of the Address Group, to which this Router Group Distribution Message refers. Address of Group Member: In the optional mode the Router Group Distribution Message contains the IPv6 addresses of all members of the Address Group. In the mandatory mode with the Modification Flag set to 1 or 2 only the addresses of those members are contained, which have requested to be newly added or deleted from the respective group. If the Modification Flag is set to 0, this field contains the addresses of all members. 5.4 Multicast Routing Algorithm 5.4.1 Introduction Since using the unicast routing algorithms like the shortest path first SPF for multicast packets can result in packets being forwarded on infinite loops, it is necessary to use a separate algorithm for this case. It is possible to guarantee, that no loops will occur Fritsche, Seifert Expires May 1998 [Page 70]INTERNET DRAFT Dynamical routing for IPv6 November 1997 during the routing of multicast packets, if all routers in a multicast routing area construct an identical tree containing all the nodes of the area and use this tree for creating their multicast forwarding database. The tree used in this algorithm is the minimum spanning tree (MST) of the multicast routing area. It would be optimal in saving bandwidth if a packet is transmitted to all nodes in the multicast routing area. If the packet is only addressed to a part of all nodes there may exists a better tree with regard to saving bandwidth during the transmission, but this tree, the MST which only contains the originator and all receivers of the packet, has a too high computing complexity for bigger networks [5]. Therefore this algorithm is a quite good alternative for the optimal algorithm, especially if the members of an Address Group are distributed within the multicast routing area. The MST routing algorithm is based on the available LSA and adjacency information. Therefore the multicast routing area is the area, in which routers exchange their Link State Information among each other. The routing of multicast packets outside of this multicast routing area is shortly discussed in chapter 6, but not scope of this proposal. 5.4.2 Description of the algorithm 5.4.2.1 Tiebreaker for unequivocal link metrics To ensure that all routers in the multicast routing area construct an identical MST, it is required, that all of them have to use the same distances for all links. If there are links with equal distances a tiebreaker must be used to get an unequivocal order of the link metrics. In this algorithm the following tiebreaker is used: a) Routers are included into the Minimum Spanning Tree before hosts. b) The link with the lower metric assigned has the shorter distance. c) If there are still two links with equal distances compute the sum of the IPv6 addresses of the two nodes connected by the respective link. The link causing the lower sum has the shorter distance. d) If there are still two links with equal distances examine the IPv6 addresses of the two nodes connected by the respective links separately. The link connecting the node with the numerically lowest IPv6 address shall have the shorter distance. e) If there are still two links with equal distances we have the situation that two nodes are connected by more than one link with each of them having the same metric. In this case any link can be selected as the one with the shortest distance, because this cannot result in the construction of different MSTs by the routers of the multicast routing area. However, this situation will probably never appear in real networks. Fritsche, Seifert Expires May 1998 [Page 71]INTERNET DRAFT Dynamical routing for IPv6 November 1997 5.4.2.2 Overview After making sure that all links in the area have different distances it is possible for each router to construct a MST in the multicast routing area, which is identical with the tree constructed by all other routers, and which contains all nodes of the area. For this tree calculation every router needs two databases. One of them, called PATHS, is used after finishing the computation of the tree as forwarding database for packets addressed to multicast addresses. The entries of this database are couples of the form , with: o N: IPv6 address of the node N Note: If the IPv6 addresses of all nodes in the multicast routing area start with the same prefix, N could consist of the rest of the IPv6 address following the prefix. N has to keep only the condition to identify unequivocally a node in the multicast routing area. o Adj(N): adjacency that the computing router should use for forwarding to N. The second database, called TENT, is used only during the computation of the tree. The entries of this database are triples of the form < N, d(N), Adj (N)> with: o N: IPv6 address of the node N Note: If the IPv6 addresses of all nodes in the multicast routing area start with the same prefix, N could consist of the rest of the IPv6 address following the prefix. N has to keep only the condition to identify unequivocally a node in the multicast routing area. o d(N): shortest possible distance of a single link, which would connect the node N to the tree, which already exists at this time of the computation. If the connection of N to the tree over a single link is impossible the triple with the IPv6 address of N is not present in TENT. o Adj(N): adjacency that the computing system S should use for forwarding to N. TENT can intuitively be thought of as a tentative placement of a node N in PATHS, but the explicit placement in PATHS can first be done if it is sure, that no node has a shorter distance to the tree than N. Additionally each node entry in TENT has to be marked as router or host and has to keep information about the previous node over which it was reached. Later in the algorithm this information will be used to make a correct decision. Each computing router in the area starts the algorithm by putting first its own IPv6 addresses in PATHS. TENT is then pre-loaded from the local adjacency database of this node. Afterwards it has to be calculated, which node has the shortest distance to the existing tree (at this point of time the tree only comprises the computing node itself). This node is then added to PATHS. If it was a router its Fritsche, Seifert Expires May 1998 [Page 72]INTERNET DRAFT Dynamical routing for IPv6 November 1997 neighbour nodes are examined by looking at its LSAs. This is done until all nodes are placed in PATHS and no one remains in TENT. 5.4.2.3 Steps of the algorithm There are three main steps of the algorithm separable: o Initialisation (Step 0) o Evaluation of the LSAs (Step 1) o Selection of the shortest distance (Step 2). In the following the single steps are described in more detail. Step 0: a) Initialise TENT and PATHS as empty. b) Add to PATHS, where SELF are the IPv6 addresses of the computing router and W is a special value indicating traffic to SELF is passed up to the Transport Layer. c) Now pre-load TENT with all neighbour nodes N of SELF. This could be done by reading the local adjacency database. If the node N is a router, the IPv6 address on behalf of which N will generate its LSAs (contained as LSA information option in the Router Advertisements of N) is stored for N. If N is a host, the Source Address of the Host Advertisements, which caused the creation of the adjacency, is used. The distance x to the neighbour N is the metric stored with the respective adjacency. Adj(N) is the adjacency itself to the neighbour node N, that is the adjacency, which has been stored in the adjacency database as result of the receipt of an advertisement. Each entry made to TENT must be marked as being either a router or a host to enable the check at the end of Step 2 to be made correctly. d) If a neighbour node is already in TENT, compare the distance of the old and the new entry and keep only the entry with the shorter distance. e) If a neighbour node is not in TENT, then place it now. f) If all neighbour nodes contained in the local adjacency database are examined, go to Step 2. Step 1: a) Now examine all neighbour nodes N listed in all LSAs of P, the node just placed in PATHS (P has been placed in PATHS during the last execution of Step 2). The distance d(N) is the metric of the link from P to N and the adjacency to N, Adj(N), is the same as the one to P, Adj(P), because N could be reached from the computing router over P. b) If a neighbour node is already in PATHS, then do nothing. c) If a neighbour node is already in TENT, compare the distances of the old and the new entry and keep only the entry with the shorter distance. d) If a neighbour node is not in TENT, then place it now. Fritsche, Seifert Expires May 1998 [Page 73]INTERNET DRAFT Dynamical routing for IPv6 November 1997 Step 2: a) If TENT is empty, then stop the computation (now all reachable nodes of the multicasting routing area are placed in PATHS). b) Else find the element for which the distance d(P) to the existing tree is the shortest among all entries in TENT. c) Remove P from TENT. d) Add to PATHS. e) If the node just added to PATHS was a host, then go back to Step 2, else go to Step 1. In the last case of e) a router has been added to PATHS. Before searching the next nearest node to the tree, the adjacencies of the just added router P have to be examined by checking P's LSAs). When the algorithm is finished, PATHS can be used as a multicast forwarding database containing all the nodes of the multicast routing area, which are reachable from the computing router. 5.4.3 Time of the algorithm execution The algorithm has to be executed if the network topology, the status of a node or a metric changes. This could be detected for example by receiving a modified LSA from the router next to the respective location. Therefore a reliable tool examining all received and locally generated LSAs is needed, which indicates that a network modification has occurred and that this shall result in a new execution of the multicast routing algorithm. 5.4.4 Complexity of the algorithm To make a fast selection of the node P in TENT having the shortest distance d(P) to the existing tree (Step 2 of the algorithm) it is useful, to keep TENT sorted with regard to the node's distances to the already existing tree. So if a new node shall be added to TENT, the following two steps have to be executed: a) Search TENT and check if the node is already present. b) Search TENT for the appropriate place to insert the new node or the entry of the node with the shorter distance, if there was already an entry in TENT. These two steps have to be executed one time for each connection of two nodes of the network. So we can approximate the complexity of the computation as 2 * L database searching cycles where L is the number of connections between nodes within the whole multicast routing area and the database comprises at the most V entries where V is the number of nodes in the multicast routing area. In the most cases the number of entries in TENT will be much more Fritsche, Seifert Expires May 1998 [Page 74]INTERNET DRAFT Dynamical routing for IPv6 November 1997 smaller than V. The memory necessary for saving the routing information obtained by using this algorithm must only have the size of the forwarding database PATHS. PATHS contains after finishing the algorithm at the most V (if all nodes are reachable) couples of an IPv6 address and the appropriate forwarding adjacency. 5.4.5 Resume Summarizing all its attributes this algorithm is a quite good solution for routing multicast packets, because - it is a dynamical routing algorithm, - the calculation of the routing information is not centralized, - it avoids the generation of infinite loops when routing multicast packets, - it doesn't have a too high computing complexity, - it doesn't require the distribution of additional routing information than the one distributed already for the SPF routing algorithm used for unicast packets, and - it is for distributed group members a good approach to the optimal algorithm in saving bandwidth. 5.4.6 Example The following example should illustrate the execution of the algorithm. The picture shows the structure of a network: +-+ +-+ |6|-------1-------(1)--4--(2)--4--(5)-------1-------|7| +-+ \ | /| +-+ \ | / | 3 1 1 2 \ | / | \ | / | \ | / | +-+ (3)--2--(4)-------1-------|8| +-+ Figure : Example for computing the MST algorithm The number in brackets represent here routers, the ones in rectangles hosts. Both number are used here as a symbolic representation of the nodes IPv6 addresses. Here each node shall have assigned only one IPv6 address. The entries of TENT are not listed here in a sorted order referring to the distances to the existing tree. In this example node 4 should be the computing router, but every other router would construct the same minimum spanning tree. The large number at each link represents the distance of two nodes connected by the respective link. Additionally a mechanism is needed to unequivocally mark the adjacencies of the computing router number Fritsche, Seifert Expires May 1998 [Page 75]INTERNET DRAFT Dynamical routing for IPv6 November 1997 4 within this example. This is done by the following numbering scheme: - the adjacency of router 4 to router 5 shall be adjacency number 1 - the adjacency of router 4 to host 8 shall be adjacency number 2 - the adjacency of router 4 to router 3 shall be adjacency number 3 In the following description of applying the algorithm to this example network the parameter m is used to show how many times the loop of the algorithm was executed. m = 1: Step 0: PATHS: <4, W> TENT: <3, 2, 3>, <5, 2, 1>, <8, 1, 2> Step 2: Routers are preferred to hosts: Router 3 and 5 have the same distance. The sum of the IPv6 addresses of node 3 and 4 is 7 and therefore lower than the sum of the IPv6 addresses of node 5 and 4 which is 9. So node 3 is selected to be placed on PATHS. PATHS: <4, W> <3, 3> TENT: <5, 2, 1> <8, 1, 2> P = 3 is a router, so continue with Step 1 m = 2: Step 1: Node 3 was selected as the node P with shortest distance; 3 was removed from TENT and placed in PATHS. Since node 3 is a router, the LSAs of node 3 have to be examined. PATHS: <4, W>, <3, 3> TENT: <1, 3, 3>, <2, 1, 3>, <5, 1, 3>, <8, 1, 2> Step 2: Routers are preferred to hosts: Router 2 and 5 have the same distance. The sum of the IPv6 addresses of node 2 and 3 is 5 and therefore lower than the sum of the IPv6 addresses of node 3 and 5 which is 8. So node 2 is selected to be placed on PATHS. PATHS: <4, W>, <2, 3>, <3, 3> TENT: <1, 3, 3>, <5, 1, 3>, <8, 1, 2> P = 2 is a router, so continue with Step 1 m = 3: Step 1: Node 2 was selected as the node P with shortest distance; 2 was removed from TENT and placed in PATHS. Since node 2 is a router, the LSAs of node 2 have to be examined. PATHS: <4, W>, <2, 3>, <3, 3> TENT: <1, 3, 3>, <5, 1, 3>, <8, 1, 2> Step 2: Routers are preferred to hosts: Selection of node 5 as P, as it has the shortest distance among Fritsche, Seifert Expires May 1998 [Page 76]INTERNET DRAFT Dynamical routing for IPv6 November 1997 all routers. PATHS: <4, W>, <2, 3>, <3, 3>, <5, 3> TENT: <1, 3, 3>, <8, 1, 2> P = 5 is a router, so continue with Step 1. m = 4: Step 1: Node 5 was selected as the node P with shortest distance; 5 was removed from TENT and placed in PATHS. Since node 5 is a router, the LSAs of node 5 have to be examined. PATHS: <4, W>, <2, 3>, <3, 3>, <5, 3> TENT: <1, 3, 3>, <7, 1, 3 >, <8, 1, 2> Step 2: Routers are preferred to hosts: Selection of node 1 as P PATHS: <4, W>, <1, 3>, <2, 3>, <3, 3>, <5, 3> TENT: <7, 1, 3>, <8, 1, 2> P = 1 is a router, so continue with Step 1. m = 5: Step 1: Node 1 was selected as the node P; 1 was removed from TENT and placed in PATHS. Since node 1 is a router, the LSAs of node 1 have to be examined. PATHS: <4, W>, <1, 3>, <2, 3>, <3, 3>, <5, 3> TENT: <6, 1, 3>, <7, 1, 3>, <8, 1, 2> Step 2: Nodes 6, 7 and 8 have the same distance. The sum of the IPv6 addresses of node 1 and 6 is 7 and therefore lower than the sum of the IPv6 addresses of node 5 and 7 which is 12 or the sum of the IPv6 addresses of node 4 and 8, which is also 12. So node 6 is selected to be placed on PATHS. PATHS: <4, W>, <1, 3>, <2, 3>, <3, 3>, <5, 3>, <6, 3> TENT: <7, 1, 3>, <8, 1, 2> P = 6 is a host, so continue with Step 2 m = 6: Step 2: Nodes 7 and 8 have the same distance. The sum of the IPv6 addresses of node 5 and 7 is 12, and therefore equal to the sum of the IPv6 addresses of node 4 and 8, which is also 12. So node 8 is selected, since node 4 has the lowest IPv6 address (see criteria d) of tiebreaker). PATHS: <4, W>, <1, 3>, <2, 3>, <3, 3>, <5, 3>, <6, 3>, <8, 2> TENT: <7, 1, 3> P = 8 is a host, so continue with Step 2 m = 7: Step 2: Selection of node 7 as P PATHS: <4, W>, <1, 3>, <2, 3>, <3, 3>, <5, 3>, <6, 3>, <7, 3>, <8, 2> Fritsche, Seifert Expires May 1998 [Page 77]INTERNET DRAFT Dynamical routing for IPv6 November 1997 TENT: Empty m = 8: Step 2: TENT is empty, so the algorithm has finished. All reachable nodes are now contained in PATHS. The minimum spanning tree constructed by this algorithm has the following structure: +-+ +-+ |6|---------------(1) (2) (5)---------------|7| +-+ \ | / +-+ \ | / \ | / \ | / \ | / \ | / +-+ (3)-----(4)---------------|8| +-+ Figure 5: Minimum spanning tree for the given example network Since with using the tiebreakers all distances are different, it is guaranteed that all routers of the multicast routing area construct the same tree. Router 4 can now use the database PATHS as multicast forwarding database. For example it would transmit a packet destined for an Address Group consisting of the nodes 6 and 7 to the adjacency 3, that is the next hop of this packet is node 3. Node 3 is again a router and would have constructed the same MST as router 4. Therefore 3 would transmit a copy to router 5 for the destination node 7 and also to router 2 for the destination node 6. Obviously this is not absolutely the shortest possible path for example to node 7 (the path from node 4 straight over node 5 would be shorter), but it is the path which every other router expects router 4 to send a packets to node 7, and this attribute ensures to avoid the generation of loops during routing. 5.5 Routing of packets addressed to a group This section describes a mechanism for the routing of data packets destined for a multicast address using the MST routing algorithm specified above. The intention of the introduction of multicast addresses is the saving of bandwidth on the network. Without multicast addresses a packet, which should be transmitted to a group of N receiving nodes, had to be sent to each of the IPv6 unicast addresses of all group members. Fritsche, Seifert Expires May 1998 [Page 78]INTERNET DRAFT Dynamical routing for IPv6 November 1997 Now this packet has only to be sent one time to the appropriate multicast address. To save bandwidth as much as possible, the following conditions have to be kept: - It has to be ensured, that a packet destined for an Address Group is forwarded by a router only on those circuits, which have to be used to reach at least one member of the group. - It also has to be ensured, that over each circuit connected to a router maximum one copy of this packet is sent. - Finally the packet shall not be forwarded on the circuit, which would be used for the transmission of a packet back to the node generating the received multicast packet (backward routing). To avoid the introduction of routing loops it is also necessary, that each router in the multicast routing area constructs the same routing tree used for forwarding multicast packets. This is done successfully by the use of the minimum spanning tree (MST) routing algorithm for multicast packets, since there is always exactly one MST for each multicast routing area. In the following the handling of received multicast packets by a router is described in more detail. 5.5.1 Acceptance of multicast packets For multicast packets the following additional acceptance tests have to be performed: - In a received multicast packet the Routing header will not be processed. This header normally is specified by the IPv6 source of the packet and contains the partial or complete description of the way the packet shall take from the source to the destination node. Since multicast packets can, and mostly will be addressed to more destination nodes, it would make no sense to use this extension header. - If the source address of the multicast packet isn't in this multicast routing area, the packet has to be discarded. To avoid backward routing, the next hop back to the source of the packet has to be excluded from the list of possible forwarding neighbours. If the source address is outside the multicast routing area, this hop cannot be determined using the multicast routing algorithm. This problem has to be solved, when in a next step a mechanism is specified, which enables the routing of multicast packets beyond the border of the multicast routing area. - If there is no valid entry stored for the multicast address in the own group database, there is no routing of this packet possible. In this case the packet also has to be discarded. 5.5.2 Determination of the forwarding adjacencies This section specifies a possible way for the determination of these adjacencies, to which a router must transmit a copy of a received Fritsche, Seifert Expires May 1998 [Page 79]INTERNET DRAFT Dynamical routing for IPv6 November 1997 multicast packet in order to receive each member of the respective Address Group. The main goals in doing this are the prevention of transmitting more than one copy to the same adjacency and routing back a copy to the adjacency, from which the packet was received. For this purpose at first a sendlist is allocated by the router, which has received a multicast packet. This list is later used to mark all adjacencies, which already have received a copy of the respective packet. Therefore it contains an entry for each adjacency of the router. Each entry is initialised with the value zero, what means, that on principle it is allowed, to transmit a copy of the multicast packet to this adjacency. Later some of these entries can be set to one, what means, that no copy of the packet shall be sent to the appropriate adjacency. In the next step the router receiving the multicast packet tries to locate, from which of its adjacencies the packet has been received. This happens in the way, that the router tries to find out using its forwarding database for multicast packets to which adjacency it would forward a packet back to the originator of the received one. Since the multicast routing tree is not a directed graph, the router assumes, that from the same adjacency the multicast packet also has been received. If this adjacency is a router, it is marked with one in the sendlist to prevent backward routing, if it is a host, the sendlist entry is not set to one. This different action between routers and hosts is necessary, since routers compute a routing tree for multicast packets, but hosts not. Therefore a host transmits a packet addressed to a group to one of its connected routers in order to cause the router to execute the appropriate routing of this multicast packet. The router then will also send a copy of the packet back to this host, if it is a member of the respective group. The multicast destination IPv6 address is substituted in this case with the unicast IPv6 address of the host. Therefore hosts aren't required to listen on multicast addresses they have joined, since this is done for them by their connected routers. If the adjacency, from which the multicast packet has been received, is now located, the router has a look on each single member of the group. For each of them it tries to find out using its forwarding database for multicast packets, to which adjacency it should forward a copy of the packet designed to this member. If this adjacency is marked already with one in the sendlist, the processing of this group member is interrupted, and it is continued with the next member. If the adjacency is marked with zero, a copy of this packet is forwarded to it, and the appropriate entry in the sendlist is set to one after transmission to prevent another copy being transmitted the same way. By the use of a sendlist it is possible, that each packet addressed Fritsche, Seifert Expires May 1998 [Page 80]INTERNET DRAFT Dynamical routing for IPv6 November 1997 to a group is only transmitted over those circuits, which are absolutely necessary to reach single group members. In this case the maximum possible bandwidth in the application of the MST routing algorithm can be saved. 5.5.3 Forwarding of multicast packets For the forwarding of a packet destined for an Address Group three cases can be distinguished: - If the packet is forwarded to another router, the multicast address is used as the destination IPv6 address. This is necessary, because the next router also needs this information to execute the routing procedure for multicast addresses. The Hop Limit field of the packet is decremented by 1. - If the packet is forwarded to a host, the unicast IPv6 address is used instead of the multicast IPv6 address as the destination address of the packet. Doing this address substitution enables a host joining multicast addresses without listening explicitly for packets destined for these Address Groups. This work is easily done for the hosts by their connected routers. Applying this substitution of the destination IPv6 address a host can't distinguish, if a single packet was addressed only to itself, or if it was addressed to a certain group, which contains the host as one of its members. The Hop Limit field of the packet is decremented by 1. - If the packet is forwarded to the local transport layer, that is the processing router itself has joined the respective group, the multicast destination IPv6 address is also substituted by the unicast IPv6 address of this router. So receivers of the packet have the same information about the destination address, independently if they are located in hosts or routers. The Hop Limit field doesn't have to be decremented in this case. Fritsche, Seifert Expires May 1998 [Page 81]INTERNET DRAFT Dynamical routing for IPv6 November 1997 6 Routing beyond the routing area The algorithms proposed in this document for the dynamically routing of unicast and multicast packets, are only used within a certain area, the routing area or the multicast routing area. The restriction to a limited area is done, because the information used for the execution of the algorithms, for example LSAs or Router Group Distribution Messages, cannot be exchanged in the whole network. This would mean an intolerable high load on the network. Therefore it is necessary, to specify a certain area, in which the detailed routing information shall be distributed. The specification of such an area can be done in many ways. For example one method would be the use of the assigned IPv6 addresses. In this case the administrator shall assign all nodes residing in the same area IPv6 addresses, which have all the same prefix. By the means of the Neighbour Discovery a node is informed about the IPv6 addresses of its neighbours. Using this information the node can decide, if control packets, which shall be distributed only within an area, have to be forwarded to a certain neighbour or not. Another method of marking off an area is to inform all routers of the area, which also have at least one connection to nodes outside the area, that they are area border routers. Along with this information the network administrator has to specify the interfaces of the routers, which are connected to neighbours outside the area. On this way an area border router knows exactly, on which of its interfaces it has to forward control packets, which shall be distributed only within the area. The advantage of this method is, that the IPv6 addresses can be assigned arbitrary, without considering any prefix restrictions. Although it is necessary to limit the distribution of certain control packets to a single area, nevertheless there is often a demand, to use the unicast and multicast routing features also beyond the borders of single areas. For this purpose border protocols have to be defined. In the following there is no such protocol specified in detail, but mechanisms for possible solutions shall be discussed. 6.1 Unicast routing beyond the routing area One way to perform routing of unicast packets beyond routing areas is the specification of at least one area border router for each area. This border router must have both, a connection to at least one area and a connection to the backbone network connecting the different areas. The routers of the backbone network, that is also the area border routers, have to exchange among themselves the information, which IPv6 addresses are reachable over which area border router. For this purpose each border router have to collect this information about its own connected areas, and distribute it using control packets within the backbone network. For this mechanism the following two aspects shall be considered for the assignment of IPv6 Fritsche, Seifert Expires May 1998 [Page 82]INTERNET DRAFT Dynamical routing for IPv6 November 1997 addresses: - The advantage of a totally free assignment of IPv6 addresses within a particular area is, that there are no restrictions, which prefix has to be used for an unicast address of the area. Each IPv6 unicast address, which is not already in use, can be assigned to any interface or node. If a node changes from one area to another, it can keep its address and is therefore easily to identify in the new area. The disadvantages of this procedure is the difficult administration of the address assignment and the amount of information, which has to be distributed within the backbone. Since there are no prefixes in use within an area, an area border router has to distribute within the backbone the information about each single assigned IPv6 address residing in its connected areas. For larger areas the amount of this information would become intolerable high. - If all unicast IPv6 addresses within one area have to use certain prefixes, it is not possible for a node changing into another area, to keep its old address. This could cause the difficulty for other nodes to identify this node with its newly assigned address. The big advantages of this address assigning procedure are the much easier administration of the assigned IPv6 addresses and the less amount of information, which has to be exchanged within the backbone. If it is ensured, that an address prefix is exclusively used within a single area, it is sufficient for the area border routers, to distribute within the backbone all prefixes, which are used for the assignment of unicast addresses within its connected areas. Therefore the routing of a generated unicast packet beyond a single area can be separated in three steps: - Routing of the packet using the SPF algorithm within the area, in which the source of the packet is located. If the destination of the packet isn't located in this area, it has to be forwarded to the nearest area border router. This means, that each router within an area has to be informed of each area border router of its area. This information can be distributed by the area border routers by setting in their Link State Advertisements a flag, which indicates, that they will act as border router. - The area border router of the source area will forward the packet within the backbone to the nearest border router, which has distributed within the backbone the information, that one of its connected areas assigns IPv6 unicast addresses matching the destination address of the routed unicast packet. For the routing of the unicast packets within the backbone the routers of the backbone must also use a routing algorithm suitable for unicasting. For this case the SPF algorithm would also be applicable. - The border router of the remote area can now forward the unicast packet using the SPF algorithm to the destination of the packet. The advantage of the method described herein for routing beyond routing areas is, that there is no big modification of the protocol behaviour necessary within an area. The only additional information Fritsche, Seifert Expires May 1998 [Page 83]INTERNET DRAFT Dynamical routing for IPv6 November 1997 to be distributed within the area is the location of routers acting as area border routers. This could be easily done by setting a particular flag in the Link State Advertisements of these routers and will therefore not use additional bandwidth. Also a unicast packet will not be forwarded automatically to a border router, but only in the case, if the destination address of the packet is not present in the own area. The only condition, that a router can be configured as area border router, is, that it has a connection to both, to at least one area and to the backbone. If more areas together constitute an autonomous system, the routing of unicast packets between more autonomous systems can be done in the same way as between more areas. In this case the used protocol is called "exterior gateway protocol". 6.2 Multicast routing beyond the multicast routing area One possible way to use the dynamical multicast routing also beyond the multicast routing area is, to specify in each area at least one multicast area border router. All the border router of the different areas are connected by the backbone network. A multicast area border router shall distribute within the backbone the information, from which Address Groups members reside in one of its connected areas. Since a multicast area border router is connected to both, to the backbone and to at least one multicast routing area, it is informed by the receipt of Group Distribution Messages about all Address Groups, for which nodes in its connected areas have declared an interest. Using this knowledge it can inform all routers connected to the backbone, and therefore all area border routers of the different multicast routing areas, about the multicast addresses, for which nodes of its connected areas have declared an interest. To limit the amount of exchanged control information, it shall only distribute the multicast addresses of these Address Groups, but not their detailed composition. If a multicast area border router receives from a border router of another multicast routing area, that this router is connected to an area containing nodes, which declare an interest for a multicast address also present in its own area, it shall immediately join this Address Group in the own area. This causes data packets, which are generated in its area and destined for this multicast address, also being forwarded to itself. These multicast packets it can then forward to the border routers of all other multicast routing areas, which has distributed in the backbone the information, that they are connected to areas containing nodes, which also have declared an interest for the respective Address Groups. Received by these border routers, they can forward the multicast packet to the members of the Address Group located in their area. Fritsche, Seifert Expires May 1998 [Page 84]INTERNET DRAFT Dynamical routing for IPv6 November 1997 Therefore the routing of a generated multicast packet beyond a single area can be separated in three steps: - Routing of the packet using the MST algorithm within the area, in which the source of the packet is located. If there are also members of the Address Group outside this area, that is in any remote area, the multicast area border router of this area has also joined this Address Group and therefore will also receive a copy of the packet. - The multicast area border router of the source area will forward the packet within the backbone to all other border routers, which have also joined the Address Group, since there are members of this group located in at least one of their connected areas. For the routing of the multicast packets within the backbone the routers of the backbone must use a routing algorithm suitable for multicasting. For this case the MST algorithm would also be applicable. - The border router of these remote areas can now forward the multicast packet using the MST algorithm to the members of the Address Group, which are located in their connected areas. One advantage of the method described herein for routing beyond multicast routing areas is, that there is no modification of the protocol behaviour necessary within an area. The nodes of an area don't have to know, if there is any area border router present for their area, it is sufficient to inform the border router itself about this fact. Also a multicast packet will not be forwarded automatically to a border router, this is done only in the case, that there are also members of the Address Group in any other area and therefore the border router of this area has also joined the respective group. The routing of a multicast packet within the backbone could happen in the same way, as it does within an area, that is the same control information and the same routing algorithm can be used. The only difference is, that within the backbone no information about the composition of any Address Group is exchanged between the routers. They distribute only the multicast addresses, for which any node in one of their connected areas has declared an interest. The only condition, that a router can be configured as a multicast area border router, is, that it has a connection to both, to at least one area and to the backbone. If more areas together constitute an autonomous system, the routing of multicast packets between more autonomous systems can be done in the same way as between more areas. In this case the used protocol is called "exterior gateway protocol". Fritsche, Seifert Expires May 1998 [Page 85]INTERNET DRAFT Dynamical routing for IPv6 November 1997 7 Quality of service aspects in dynamical routing For the computation of the routing trees both algorithms, the Shortest Path First (SPF) algorithm and the Minimum Spanning Tree (MST) algorithm, use a metric for each circuit of the network during the execution of the algorithm. Evaluating this metric it is decided, if the respective circuit is included in the routing tree or not. Therefore at least one metric, the default metric, has to be specified for each circuit of the network. If the default metric is the only available metric, the influence of a chosen quality of service for a data packet on the way of this packet from the source to its destination(s) is very restricted. A router can only make the decision to route this packet along the tree computed with the use of the default metric, or it has to discard the packet, since the required quality of service is not represented by the use of the default metric. Therefore it is recommendable for an efficient use of these routing algorithms, to use more metrics for the single links of a network. It would be also an advantage, if these metrics represent already different quality of service aspects. For example there could be a delay metric derived from the possible transfer rate on a particular circuit. This metric would be a representation of the delay time requirements of a packet. As another metric an error metric could be derived from the bit error probability of the single circuits. This metric could be used to represent the security aspects of the quality of service requirements. Each of those metrics has to be configured manually, or a mechanism has to be defined, which allows a router, to derive the values for the single metrics automatically. Since all this metric values are distributed in LSAs among all routers within the routing area, a change in one specific metric value causes a fast recomputation of the respective routing trees. Therefore changing of the metric values can be used by network administrators as an appropriate method to influence the routing of IPv6 data packets with a particular aim in mind. Finally there must be the possibility for a router to decide, which metric shall be used for the routing of a data packet. It is also necessary to guarantee, that all routers apply the same routing metric. f this condition isn't kept, the use of different routing trees by the single routers can cause the introduction of infinite routing loops. Looking at the IPv6 protocol [1] there are two possibilities shown for deriving the appropriate metric used for routing a single data packet. One way is to use the Flow Label field contained in each IPv6 packet. In this case the source has to inform the router before the first transmission of a packet with a particular Flow Label, Fritsche, Seifert Expires May 1998 [Page 86]INTERNET DRAFT Dynamical routing for IPv6 November 1997 which special handling the source intends for all packets of this flow. This could be done by a control protocol, such as the resource reservation protocol. Using the information about this special handling a router must be able to decide unequivocally, which metric is used for those packets. The other way is to add an option to the data packets Hop-by-Hop Header, which carries information about the metric to be used for routing this packet. Since the Hop-by-Hop Header must be examined by every node along a packets delivery path, it is guaranteed, that each router receives this information. The detailed description of these control protocols and Hop-by-Hop header options or other possible mechanisms of the determination of the appropriate routing metric is not scope of this proposal. 8 Security Considerations Security issues are not discussed in this document. 9 References [1] S. Deering, R.Hinden; Internet Protocol, Version 6 (IPv6) Specification; RFC 1883; December 1995 [2] A. Conta, S. Deering; Internet Control Message Protocol (ICMPv6) for the Internet Protocol Version 6 (IPv6) Specification; RFC 1885; December 1995 [3] T. Narten, E. Nordmark, W. Simpson; Neighbor Discovery for IP Version 6 (IPv6); RFC 1970; August 1996 [4] S. Thompson, T. Narten; IPv6 Stateless Address Autoconfiguration; RFC 1971; August 1996 [5] C.-H. Chow; On Multicast Path Finding Algorithms; Proc. of Infocom. 1991; pp 1274 - 1283 Fritsche, Seifert Expires May 1998 [Page 87]INTERNET DRAFT Dynamical routing for IPv6 November 1997 10 Author's Addresses Wolfgang Fritsche IABG Einsteinstr. 20 85521 Ottobrunn Germany Phone: +49 89 6088 2897 EMail: wfritsch@iabg.de Hartmut Seifert IABG Einsteinstr. 20 85521 Ottobrunn Germany Phone: +49 89 6088 4021 EMail: seifert@iabg.de Fritsche, Seifert Expires May 1998 [Page 88]