INTERNET DRAFT Author: Wolfgang Fritsche Expires in six months IABG 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. 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 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. 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. 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. Author's Address: M. Wolfgang Fritsche Industrieanlagen-Betriebsgesellschaft mbH Department: CC31 Einsteinstr. 20 Ottobrunn, 85521 GERMANY wfritsch@iabg.de