Malloc Working Group Roger Kermode
Internet Engineering Task Force Motorola
INTERNET-DRAFT 29 April 1999
Expires 29 October 1999
MADCAP Multicast Scope Nesting State Option
<draft-ietf-malloc-madcap-nest-opt-01.txt>
Status of this Memo
This document is an Internet-Draft and is in full conformance
with all provisions of Section 10 of RFC2026.
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."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
Abstract
This document defines a new option to the Multicast Address Dynamic
Client Allocation Protocol (MADCAP) to support nested scoping. The
new option's purpose is to allow clients to learn which scopes nest
inside each other, and hence may be used for expanding scope searches
or hierarchical multicast transport.
Copyright Notice
Copyright (C) The Internet Society (1999). All Rights Reserved.
Expires 29 October 1999 [Page 1]
DRAFT <draft-ietf-malloc-madcap-nest-opt-01.txt> 22 April 1999
Contents
Abstract. . . . . . . . . . . . . . . . . . . . . . . . . 1
1. Introduction. . . . . . . . . . . . . . . . . . . . . 3
1.1 Time-To-Live (TTL) Scoping Split Horizon Effect. . 3
1.2 Eliminating the Split Horizion Effect with
Administrative Scoping . . . . . . . . . . . . . 4
1.3 Terminology. . . . . . . . . . . . . . . . . . . . 5
2. Nested Scope Discovery. . . . . . . . . . . . . . . . 5
2.1 MADCAP processing of MZAP messages . . . . . . . . 6
2.1.1 Zone Nesting State . . . . . . . . . . . . . 6
2.1.2 Updating Scope Nesting State via the
observation of NIMs. . . . . . . . . . . . . 7
2.1.3 Updating Scope Nesting State due to
Timer Expiration . . . . . . . . . . . . . . 7
2.2 Multicast Scope List Option. . . . . . . . . . . . 8
2.3 Multicast Scope Nesting State Option . . . . . . . 8
2.3.1 Representing the Multicast
Scope Nesting State. . . . . . . . . . . . . 8
2.3.2 Multicast Scope Nesting State Option Usage . 10
3. Multicast Scope Nesting State Option Format . . . . . 10
4. Constants . . . . . . . . . . . . . . . . . . . . . . 11
5. Security Considerations . . . . . . . . . . . . . . . 11
6. IANA Considerations . . . . . . . . . . . . . . . . . 11
7. Acknowledgements. . . . . . . . . . . . . . . . . . . 11
8. References. . . . . . . . . . . . . . . . . . . . . . 12
9. Author's Address. . . . . . . . . . . . . . . . . . . 12
10. Full Copyright Statement. . . . . . . . . . . . . . . 12
Expires 29 October 1999 [Page 2]
DRAFT <draft-ietf-malloc-madcap-nest-opt-01.txt> 22 April 1999
1. Introduction
The Multicast Address Dynamic Client Allocation Protocol (MADCAP)
[MADCAP] affords client applications the ability to request multicast
address allocation services from multicast address allocation
servers. As part of the Multicast Address Allocation Architecture
[MAAA], MADCAP gives clients the ability to reserve, request, and
extend leases on multicast addresses.
A new MADCAP option, the "Multicast Scope Nesting State" option is
proposed to allow clients to learn not only which scopes exist via
the existing "Multicast Scope List" option, but how these scopes nest
inside each other. This new option will also afford clients the
ability to make better scope selections for a given session and also
to construct hierarchies of administratively scoped zones. These
hierarchies may then be used to perform expanding scope searches
instead of the expanding ring or increasing-TTL searches. Expanding
scope searches do not suffer from the Split-Horizon Effect present in
expanding ring searches, and therefore both simplify protocol design
and provide better localization.
1.1 Time-To-Live (TTL) Scoping Split Horizon Effect
Multicast searching and localized recovery transport techniques that
rely on TTL scoping are known to suffer when deployed in a wide scale
manner. The failing lies in the split horizon effect shown below in
Figure 1. Here a requestor and responder must each use a TTL that is
sufficiently large that they will reach the other. When they are
separated by many hops the TTL becomes large and the number of
receivers within the multicast tree that only receive either the
request or the response can become very large.
....... *******
... *** *** A Only hears S
.. ** .. ** B hears S and R
. * . * C Only hears R
. * . *
. S<------->R * . TTL Boundary for S
. * . * * TTL Boundary for R
. A * B . C *
.. ** .. **
... *** ***
....... *******
Figure 1 : Split Horizon Problem from TLL scoping
Expires 29 October 1999 [Page 3]
DRAFT <draft-ietf-malloc-madcap-nest-opt-01.txt> 22 April 1999
1.2 Eliminating the Split Horizon Effect with Administrative Scoping
Ideally, a mechanism that either eliminates or minimizes the size of
the A and C regions in Figure 1. as shown in Figure 2. is needed to
solve this problem. One mechanism that affords this ability is
administrative scoping [RFC2365], in which routers prevent the
passing of packets within a certain range of multicast addresses.
Routers that have this feature can be configured to provide a
perimeter around a region of the network. This perimeter is said to
encompass an administratively scoped zone inside of which traffic
sent to that particular range of multicast addresses can neither
leave nor enter. Routers can construct and manage administratively
scoped zones using the MZAP [MZAP] protocol.
........................
. .
. many hops .
.S<------------------------>R.
. .
. .
........................
Figure 2 : Eliminating the Split Horizon Effect
MZAP also includes the ability to determine whether or not
administratively scoped regions nest inside one another. This allows
hierarchies such as that shown in Figure 1. to be constructed.
. . . . . . . . . . . . . . . . . .
. scope a . Scope Boundaries
. . . = scope a
. _______________ ________________ . - = scopes b,c
. / scope b \ / scope c \ . # = scopes d,e,f, & g
.| | | |.
.| ##### ##### | | ##### ##### |.
.| #scope# #scope#| | #scope# #scope# |.
.\ # d # # e #| | # f # # g # /.
.\ #### #####/ \ ##### #### /.
.\____________/ \_____________/.
. . . . . . . . . . . . . . . . .
Figure 3 : Admin Scope Zone Nesting Hierarchy example
A generic expanding scope search algorithm [KERM] that exploits the
existence of a hierarchy of administratively scoped zones is:
Expires 29 October 1999 [Page 4]
DRAFT <draft-ietf-malloc-madcap-nest-opt-01.txt> 22 April 1999
1) Starting with the smallest known scope for the session, a
requestor in that session issues a request and waits for a reply.
2) If a node within that scope hears a request at a certain scope
that it can satisfy it sends a response at that same scope,
possibly after some random delay to reduce duplicate responses.
3) Nodes that receive a response to a particular request while
waiting to send a response to that request, suppress their own
response.
4) If a requestor issues a request to a scope, and does not hear a
response after specified amount of time, it retransmits its
request at the same scope a small number of additional times.
Should these retries fail to elicit a response, the requestor
increases the scope to the next largest scope and tries
again.
5) Requestors increase the scope of the request according to
step 4 until either a response is received, or the largest
legal scope for the session is reached. Should attempts to
elicit a response at the largest possible scope for the
session fail to yield a response, the requestor may conclude
that the request cannot be met.
1.3. Terminology
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and"OPTIONAL" in this
document are to be interpreted as described in RFC 2119 [RFC2119].
Throughout the rest of this document, the words "server" or "MADCAP
server" refer to a host providing multicast address allocation
services via MADCAP. The words "client" or "MADCAP client" refer to a
host requesting multicast address allocation services via MADCAP.
2. Nested Scope Discovery
The "Multicast Scope Nesting State" option is proposed to augment the
"Multicast Scope List" option within the MADCAP protocol by providing
additional information to applications about how scopes nest. MADCAP
servers shall learn this additional information for their clients by
noting the contents of Zone Not Inside Messages (ZNIM) that are
periodically transmitted by the Zone Border Routers that enforce the
boundaries of administratively scoped zones.
Expires 29 October 1999 [Page 5]
DRAFT <draft-ietf-malloc-madcap-nest-opt-01.txt> 22 April 1999
2.1 MADCAP Server processing of MZAP messages
MADCAP servers listen to MZAP traffic originated by ZBRs to learn
which scopes exist (via Zone Announcement Messages, ZAMs) and which
of these scopes do not nest (via Not Inside Messages, NIMs). This
state must be cached within the MADCAP server.
2.1.1 Scope Nesting State
Two scopes, X and Y, can be related in one of four possible ways.
1) X nests inside Y,
2) Y nests inside X,
3) X and Y do not nest (the overlap case), and
4) X and Y nest inside each other.
The fourth case SHOULD be interpreted as meaning that X and Y have
exactly the same border. This does not mean that X and Y are the same
scope since X and Y may correspond to different ranges of the
multicast address space.
This state MUST be stored in the MADCAP servers which MUST allow the
state to be updated as network conditions change. Each MADCAP server
SHOULD therefore define two pieces of state that describe whether
"scope X nests in scope Y" or vice versa. For the remainder of this
document the nesting relationship shall be denoted as the "/" where
X/Y defines the relation "X nests inside Y". This relation shall be
understood to take one of the values "true", or "false." Nesting
relationship state that is indeterminate is considered to be "false."
Since the decision as to whether one scope nests inside another must
be made in a collective fashion by all the routers for a scope,
MADCAP servers MUST include mechanisms to allow for:
a) whether the nesting decision is still under consideration or
can be considered definitive, and therefore be announced to
MADCAP clients.
b) whether one or both scopes for a particular nesting state entry
have been destroyed, and hence whether the nesting state should
therefore be discarded.
c) whether the scope boundaries have changed so that whereas scope
X did or did not nest inside scope Y, the opposite is now true.
Expires 29 October 1999 [Page 6]
DRAFT <draft-ietf-malloc-madcap-nest-opt-01.txt> 22 April 1999
To realize a) and b) MADCAP servers MUST implement the following two
timers; NEST_NO_NIM_TIMER, SCOPES_EXIST_TIMER.
The first timer, NEST_NO_NIM_TIMER, is used to mark time between a
MADCAP server's first hearing of a scope and making a decision about
its relationship to other zones. Up until the time this timer expires
MADCAP servers MUST NOT conclude that the scope nests within another.
The NEST_NO_NIM_TIMER timer will also be used to timeout X/Y =
"false" state to allow X/Y to be reset to true in the event that the
boundaries for zone X and zone Y change so that zone X now nests
inside zone Y.
The second timer SCOPES_EXIST_TIMER will be used to timeout the
internal state between two scopes in the event that one or both
scopes are destroyed.
2.1.2 Updating Scope Nesting State via the observation of NIMs
When a MADCAP server S receives a NIM from a ZBR containing
information that scope X does not nest in scope Y, it MUST update its
internal state in the following manner.
1) S SHOULD update its internal X/Y state to "false".
2) S SHOULD restart NEST_NO_NIM_TIMER for the newly updated
X/Y state.
2.1.3 Updating Scope Nesting State due to timer expiration.
MADCAP servers will also update X/Y nesting state upon the expiration
of timers.
o If the NEST_NO_NIM_TIMER expires for a state entry X/Y AND no
NIMs have been received that indicate scope X does not nest
inside scope Y, a MADCAP Server, S, MAY conclude that scope X
nests inside scope Y. As a result S will change X/Y from "false"
to "true".
When a state change from "false" to "true" occurs for X/Y, S must
also start the ZONES_EXIST_TIMER timer for X/Y. The
ZONES_EXIST_TIMER should only reset when a ZAM has been received
for both zone X and zone Y since the last time it was restarted.
This ensures that both zone X and zone Y are known to still exist.
o If the ZONES_EXIST_TIMER expires for a state entry X/Y, S
SHOULD conclude that either zone Y or zone X no longer exists and
hence that both X/Y and Y/X state should be destroyed.
Expires 29 October 1999 [Page 7]
DRAFT <draft-ietf-malloc-madcap-nest-opt-01.txt> 22 April 1999
2.2 Multicast Scope List Option
To understand the "Multicast Scope Nesting State" option one must
first understand the the "Multicast Scope List" option.
The Multicast Scope List option in MADCAP is used by MADCAP servers
to inform MADCAP clients of which zones are visible. Visible scopes
are enumerated inside the option as successive tuples, where each
tuple consists of the following information:
o Scope ID:
The smallest address for the range of multicast addresses
covered by this scop
o Last Address:
The largest address for the range of multicast addresses
covered by this scope.
o TTL:
The TTL to be used when sending message to this scope.
o Name(s):
One or more languages specific name for the scope.
2.3 Multicast Scope Nesting State Option
Given a Multicast Scope List containing descriptions for n scopes one
can form n(n-1)/2 pairings. As was shown in section 2.1.1 each
pairing can take on one of four possible states. Thus, for a list of
n scopes there exists 2 pieces of information for each pairing for a
total of n(n-1) pieces of information regarding which scopes do and
do not nest inside each other. This information is most easily and
efficiently conveyed in the a compressed bit matrix as shown in
section 2.4.
2.3.1 Representing the Multicast Scope Nesting State
As was stated in section 2.3, the Multicast Nesting State option must
convey a total of n(n-1) pieces of state, where n is the number of
scopes listed in the preceding Multicast Scope List Option. This
information will be sparse, since at most only a few scopes will
nest.
Expires 29 October 1999 [Page 8]
DRAFT <draft-ietf-malloc-madcap-nest-opt-01.txt> 22 April 1999
There are several ways to represent this information using full
matricies, sparse-matricies, and using lists of variable length
lists. In the interests of maximal efficiency and flexibility, the
Multicast Nesting State Option uses a bit-packed matrix approach. In
this approach a matrix constructed for each piece of X/Y state where
X is the row and Y is the column. A "1" in the matrix means that the
relationship "row nests inside column" is true, while a "0" means
that this relationship is wither false or indeterminate. The
diagonal of the matrix is removed, since this is the case where X is
the same as Y, and each row is then zero-padded to the next byte
boundary to give the final representation.
An example of how a matrix would be constructed for the following
scope nestings S1/S2, S2/S3, S2/S4, S3/S5, S4/S5, S5/S6, and S6/S7.
Note that a number of additional nesting relationships are implied
from this set. ________________________________
/............ \ \ \
/.S3 _________._____ \ \ \
|. /+--+ \ . \ | | |
|. | |S1| S2 | . S4 | S5 | S6 | S7 |
|. \+--+ / . | | | |
\. \______/ . | | | |
\....\....... / / / /
\ \___________/ / / /
\___________________/ / /
\ Y \______________________/ /
X \ 1 2 3 4 5 6 7 \_________________________/
+-+-+-+-+-+-+-+
1 |1 1 1 1 1 1 1| *111111 1111 1100 0xfc
2 |0 1 1 1 1 1 1| 0*11111 0111 1100 0x7c
3 |0 0 1 0 1 1 1| 00*0111 0001 1100 0x1c
4 |0 0 0 1 1 1 1| => 000*111 => 0001 1100 => 0x1c
5 |0 0 0 0 1 1 1| 0000*11 0000 1100 0x0c
6 |0 0 0 0 0 1 1| 00000*1 0000 0100 0x04
7 |0 0 0 0 0 0 1| 000000* 0000 0000 0x00
+-+-+-+-+-+-+-+ ^^
* = X/Y where zero padding
X == Y
Final Representation: 0xfc 0x7c 0x1c 0x1c 0x0c 0x04 0x00
Figure 4. Scope Nesting Example
Expires 29 October 1999 [Page 9]
DRAFT <draft-ietf-malloc-madcap-nest-opt-01.txt> 22 April 1999
2.3.2 Multicast Scope Nesting State Option Usage
The "Multicast Scope Nesting State" option is dependent upon the
"Multicast Scope List" option. This decision was made according to
the following reasoning. The Multicast Nest State Option requires
that the scopes be identified along with their nesting properties.
Since the information needed to describe a scope is contained in the
Multicast Scope List option and this information can change, the
MADCAP messages that contain the Multicast Scope Nesting State option
must be atomic and therefore must include the "Multicast Scope List
Option."
Thus, the "Multicast Scope Nesting State" option MAY only be used in
messages that carry the "Multicast Scope List" option, specifically:
DISCOVER, OFFER, ACK (in response to RENEW)
The "Multicast Scope Nesting State" option MUST NOT be used in
messages that do not carry the "Multicast Scope List" option,
specifically:
INFORM, ACK (in response to INFORM), RENEW, RELEASE,
ACK (in response to RELEASE), NAK,
any DISCOVER/OFFER/ACK (in response to RENEW) that
does not carry the "Multicast Scope List"
Since the Multicast Nest State option is dependent upon the Multicast
Scope List option, it MUST follow, and NEVER precede, the Multicast
Scope List option.
3. Multicast Scope Nesting State Option Format
Code Len Count Nest State Matrix
+-----+-----+-----+-----+-----+-----+-...-+-----+
| OPTID | p | m | N1 | | Nm |
+-----+-----+-----+-----+-----+-----+-...-+-----+
Code: 16 bits
Option identifier (OPTID), to be assigned by IANA.
Len: 16 bits
The length of the option in bytes.
Count: 8 bits
The number of zones present in the Nest State Matrix. This value
MUST be identical to the Count field in the preceding Multicast
State List option.
Expires 29 October 1999 [Page 10]
DRAFT <draft-ietf-malloc-madcap-nest-opt-01.txt> 22 April 1999
Nest State Matrix:
The compressed bit-packed representation of the matrix, derived
in the same manner as shown in Figure 4. Note for N scopes
the compressed matrix will be Nxceil((N-1)/8) bytes long. The
scopes corresponding to the rows and columns of this matrix
list in the same order as they appear in the Multicast Scope
List Option.
4. Constants
[OPTID] The option identifier for the Mutlicast Scope Nesting State
option, to be assigned by IANA.
5. Security Considerations
Since this draft proposes an extension to the MADCAP protocol via the
addition of a new option, the same set of security concerns apply.
In addition to these concerns are those that would arise were the
information in the Multicast Scope Nesting State option to be
falsified. In this case the clients would be misinformed as to which
scopes nest inside one another. In this event, the client would then
make incorrect decisions regarding the order in which to use the
scopes. The effect of this would be to use larger scopes than
necessary, which would effectively flatten any scope hierarchy
present and nullify the advantage afforded by the hierarchy's
presence.
Thus a malformed or tampered Multicast Scope Nesting option may cause
protocols that rely upon the existence of a scoping hierarchy to
scale less well, but it would not prevent them from working.
6. IANA Considerations
The Multicast Nesting State Option will require the assignment of an
additional option code to the MADCAP [MADCAP] protocol.
7. Acknowledgments
The Author would like to acknowledge Mark Handley and Dave Thaler for
the helpful discussions and feedback which helped shape and refine
this document.
Expires 29 October 1999 [Page 11]
DRAFT <draft-ietf-malloc-madcap-nest-opt-01.txt> 22 April 1999
8. References
[KERM] Kermode, R., "Smart Network Caches: Localized Content
and Application Negotiated Recovery Mechanisms for
Multicast Media Distribution", Ph.D. Thesis, MIT
Media Laboratory, June 1998.
[MAAA] Handley, M., Thaler, D., and D. Estrin, "The Internet
Multicast Address Allocation Architecture", Internet
Draft, December 1997.
[MADCAP] Patel. B.V., Shah, M., Hanna, S.R., "Multicast Address
Dynamic Client Allocation Protocol (MADCAP)", Internet
Draft, draft-ietf-malloc-madcap-03.txt
[MZAP] Handley, M., Thaler, D., Kermode, R., "Multicast-Scope
Zone Announcement Protocol (MZAP)",
draft-ietf-mboned-mzap-03.txt, Internet-Draft, February,
1999.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP, RFC 2119, March 1997.
[RFC2365] Meyer, D., "Administratively Scoped IP Multicast", BCP,
RFC 2365, July 1998.
9. Author's Address
Roger Kermode
Motorola Australian Research Centre
12 Lord St,
Botany, NSW 2091
Australia
Email: Roger_Kermode@email.mot.com
10. Full Copyright Statement
Copyright (C) The Internet Society (1999). All Rights Reserved.
This document and translations of it may be copied and furnished to
others, and derivative works that comment on or otherwise explain it
or assist in its implementation may be prepared, copied, published
and distributed, in whole or in part, without restriction of any
kind, provided that the above copyright notice and this paragraph are
included on all such copies and derivative works. However, this
document itself may not be modified in any way, such as by removing
the copyright notice or references to the Internet Society or other
Internet organizations, except as needed for the purpose of
Expires 29 October 1999 [Page 12]
DRAFT <draft-ietf-malloc-madcap-nest-opt-01.txt> 22 April 1999
developing Internet standards in which case the procedures for
copyrights defined in the Internet languages other than English.
The limited permissions granted above are perpetual and will not be
revoked by the Internet Society or its successors or assigns.
This document and the information contained herein is provided on an
"AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING
BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION
HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF
MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE."
Expires 29 October 1999 [Page 13]
