Internet DRAFT - draft-fritsche-ipv6-multicast

draft-fritsche-ipv6-multicast



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

                 <draft-fritsche-ipv6-multicast-02.txt>


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 <N, d(N), Adj(N)>, 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 <N, d(N), Adj(N)>,
     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 <N, x, A> 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 <M, *, *> is already in PATHS, this new paths
   will be longer, and thus ignored.

   If <M, *, *> 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 <N, x, Adj(N)> 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 <SELF, 0, W> 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 <P, x, Adj(P)> 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 <P, d(N), Adj(P)> 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 <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 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 <SELF, 0, W> 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 <P, d(P), Adj(P)> 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 <P, Adj(P)> 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]