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]
