As per Relevance of the word relation, we have this rfc below:
Network Working Group R.
Request for Comments: 2907
Category: Standards Track September 2000
MADCAP Multicast Scope Nesting State
Status of this
This document specifies an Internet standards track protocol for
Internet community, and requests discussion and suggestions
improvements. Please refer to the current edition of the "
Official Protocol Standards" (STD 1) for the standardization
and status of this protocol. Distribution of this memo is unlimited
Copyright
Copyright (C) The Internet Society (2000). All Rights Reserved
This document defines a new option to the Multicast Address
Client Allocation Protocol (MADCAP) to support nested scoping.
new option's purpose is to allow clients to learn which scopes
inside each other, and hence it may be used for expanding
searches or hierarchical multicast transport
Table of
1. Introduction. . . . . . . . . . . . . . . . . . . . . 2
1.1 Time-To-Live (TTL) Scoping Split Horizon Effect. 2
1.2 Eliminating the Split Horizon Effect
Administrative Scoping . . . . . . . . . . . . . 3
1.3 Terminology. . . . . . . . . . . . . . . . . . . 4
2. Multicast Nested Scoping State. . . . . . . . . . . . 5
3. Multicast Scope Nesting State Option. . . . . . . . . 5
3.1 Multicast Scope List Option . . . . . . . . . . 5
3.2 Representing the Multicast Scope Nesting State . 6
3.3 Multicast Scope Nesting State Option Usage . . . 7
4. Managing Dynamic Nested Scopes. . . . . . . . . . . . 8
4.1 MADCAP Server processing of MZAP messages. . . . 9
4.2 Updating State for Dynamic Nested Scopes due
Timer Expiration . . . . . . . . . . . . . . 9
5. Multicast Scope Nesting State Option Format . . . . . 9
6. Constants . . . . . . . . . . . . . . . . . . . . . . 10
7. Security Considerations . . . . . . . . . . . . . . . 11
8. IANA Considerations . . . . . . . . . . . . . . . . . 11
9. Acknowledgements. . . . . . . . . . . . . . . . . . . 11
Kermode Standards Track [Page 1]
RFC 2907 MADCAP Multicast Scope Nesting State Option September 2000
10. References. . . . . . . . . . . . . . . . . . . . . . 11
11. Author's Address. . . . . . . . . . . . . . . . . . . 12
12. Full Copyright Statement. . . . . . . . . . . . . . . 13
1.
The Multicast Address Dynamic Client Allocation Protocol (MADCAP
[RFC2730] affords client applications the ability to
multicast address allocation services from multicast
allocation servers. As part of the Multicast Address
Architecture [RFC2908], MADCAP gives clients the ability to reserve
request, and extend leases on multicast addresses
A new MADCAP option, the "Multicast Scope Nesting State" option
proposed to allow clients to learn not only which scopes exist
the existing "Multicast Scope List" option, but how these scopes
inside each other. This new option will also afford clients
ability to make better scope selections for a given session and
to construct hierarchies of administratively scoped zones.
hierarchies may then be used to perform expanding scope
instead of the expanding ring or increasing-TTL searches.
scope searches do not suffer from the Split-Horizon Effect present
expanding ring searches, and therefore both simplify protocol
and provide better localization
1.1 Time-To-Live (TTL) Scoping Split Horizon
Multicast searching and localized recovery transport techniques
rely on TTL scoping are known to suffer when deployed in a wide
manner. The failing lies in the split horizon effect shown below
Figure 1. Here a requestor and responder must each use a TTL that
sufficiently large that they will reach the other. When they
separated by many hops the TTL becomes large and the number
receivers within the multicast tree that only receive either
request or the response can become very large
Kermode Standards Track [Page 2]
RFC 2907 MADCAP Multicast Scope Nesting State Option September 2000
....... *******
... *** *** A Only hears
.. ** .. ** B hears S and
. * . * C Only hears
. * . *
. S<------->R * . TTL Boundary for
. * . * * TTL Boundary for
. A * B . C *
.. ** .. **
... *** ***
....... *******
Figure 1 : Split Horizon Problem from TTL
1.2 Eliminating the Split Horizon Effect with Administrative
Ideally, a mechanism that either eliminates or minimizes the size
the A and C regions in Figure 1. as shown in Figure 2. is needed
solve this problem. One mechanism that affords this ability
administrative scoping [RFC2365], in which routers prevent
passing of packets within a certain range of multicast addresses
Routers that have this feature can be configured to provide
perimeter around a region of the network. This perimeter is said
encompass an administratively scoped zone inside of which
sent to that particular range of multicast addresses can
leave nor enter. Routers can construct and manage
scoped zones using the MZAP [RFC2776] protocol
........................
. .
. many hops .
.S<------------------------>R
. .
. .
........................
Figure 2 : Eliminating the Split Horizon
MZAP also includes the ability to determine whether or
administratively scoped regions nest inside one another. This
hierarchies such as that shown in Figure 1. to be constructed
Kermode Standards Track [Page 3]
RFC 2907 MADCAP Multicast Scope Nesting State Option September 2000
. . . . . . . . . . . . . . . . . .
. scope a . Scope
. . . = scope
. _______________ ________________ . - = scopes b,
. / scope b \ / scope c \ . # = scopes d,e,f, &
.| | | |.
.| ##### ##### | | ##### ##### |.
.| #scope# #scope#| | #scope# #scope# |.
.\ # d # # e #| | # f # # g # /.
.\ #### #####/ \ ##### #### /.
.\____________/ \_____________/.
. . . . . . . . . . . . . . . . .
Figure 3 : Admin Scope Zone Nesting Hierarchy
A generic expanding scope search algorithm [KERM] that exploits
existence of a hierarchy of administratively scoped zones is
1) Starting with the smallest known scope for the session,
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
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
waiting to send a response to that request, suppress their
response
4) If a requestor issues a request to a scope, and does not hear
response after a specified amount of time, it retransmits
request at the same scope a small number of additional times
Should these retries fail to elicit a response, the
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
for the session is reached. Should attempts to elicit a
at the largest possible scope for the session fail to yield
response, the requestor may conclude that the request cannot
met
1.3.
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and"OPTIONAL" in
document are to be interpreted as described in RFC 2119 [RFC2119].
Kermode Standards Track [Page 4]
RFC 2907 MADCAP Multicast Scope Nesting State Option September 2000
Throughout the rest of this document, the words "server" or "
server" refer to a host providing multicast address
services via MADCAP. The words "client" or "MADCAP client" refer to
host requesting multicast address allocation services via MADCAP
2. Multicast Nested Scoping
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),
4) X and Y nest inside each other
The fourth case SHOULD be interpreted as meaning that X and Y
exactly the same border. This does not mean that X and Y are the
scope since X and Y may correspond to different ranges of
multicast address space
This state MUST be stored in the MADCAP servers which MUST allow
state to be updated as network conditions change. Each MADCAP
SHOULD therefore define two pieces of state that describe
"scope X nests in scope Y" and vice versa. For the remainder of
document the nesting relationship shall be denoted as the "/"
X/Y defines the relation "X nests inside Y". This relation shall
understood to take one of the values "true", or "false".
relationship state that is indeterminate is considered to be "false".
3 Multicast Scope Nesting State
The "Multicast Scope Nesting State" option is proposed to augment
"Multicast Scope List" option within the MADCAP protocol by
additional information to applications about how scopes nest.
proposed option is OPTIONAL, that is MADCAP servers MAY
this new option, however they are not required to
MADCAP servers shall learn this additional nesting information
means of static configuration or via some other protocol such as
[RFC2776] that manages administrative scopes in a dynamic fashion
3.1 Multicast Scope List
To understand the "Multicast Scope Nesting State" option one
first understand the "Multicast Scope List" option
Kermode Standards Track [Page 5]
RFC 2907 MADCAP Multicast Scope Nesting State Option September 2000
The Multicast Scope List option in MADCAP is used by MADCAP
to inform MADCAP clients of which zones are visible. Visible
are enumerated inside the option as successive tuples, where
tuple consists of the following information
o Scope ID
The smallest address for the range of multicast
covered by this scope
o Last Address
The largest address for the range of multicast
covered by this scope
o TTL
The TTL to be used when sending messages to this scope
o Name(s):
One or more language specific names for the scope
3.2 Representing the Multicast Scope Nesting
Given a Multicast Scope List containing descriptions for n scopes
can form n(n-1)/2 pairings. As was shown in section 2 each
can take on one of four possible states. Thus, for a list of n
there exists 2 pieces of information for each pairing for a total
n(n-1) pieces of information regarding which scopes do and do
nest inside each other
There are several ways to represent this state using full matrices
sparse-matrices, and using lists of variable length lists. In
interests of maximal efficiency and flexibility, the
Nesting State Option uses a bit-packed matrix approach. In
approach a matrix is constructed using pieces of X/Y state where X
the row and Y is the column. A "1" in the matrix means that
relationship "row nests inside column" is true, while a "0"
that this relationship is either false or indeterminate.
diagonal of the matrix is removed, since this is the case where X
the same as Y, and each row is then zero-padded to the next
boundary to give the final representation
An example of how a matrix would be constructed for the
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
from this set
Kermode Standards Track [Page 6]
RFC 2907 MADCAP Multicast Scope Nesting State Option September 2000
________________________________
/............ \ \ \
/.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 0
2 |0 1 1 1 1 1 1| 0*11111 0111 1100 0x7
3 |0 0 1 0 1 1 1| 00*0111 0001 1100 0x1
4 |0 0 0 1 1 1 1| => 000*111 => 0001 1100 => 0x1
5 |0 0 0 0 1 1 1| 0000*11 0000 1100 0x0
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
X ==
Final Representation: 0xfc 0x7c 0x1c 0x1c 0x0c 0x04 0x00
Figure 4. Scope Nesting
3.3 Multicast Scope Nesting State Option
The "Multicast Scope Nesting State" option is dependent upon
"Multicast Scope List" option. This decision was made according
the following reasoning. The Multicast Nest State Option
that the scopes be identified along with their nesting properties
Since the information needed to describe a scope is contained in
Multicast Scope List option and this information can change,
MADCAP messages that contain the Multicast Scope Nesting State
must be atomic and therefore must include the "Multicast Scope
Option".
Thus, the "Multicast Scope Nesting State" option MUST only be used
messages that carry the "Multicast Scope List" option, specifically
ACK (in response to GETINFO
Since the Multicast Nest State option is dependent upon the
Scope List option, it MUST NOT be included without the
Scope List option
Kermode Standards Track [Page 7]
RFC 2907 MADCAP Multicast Scope Nesting State Option September 2000
Clients that need to explicitly learn the nesting
between scopes should therefore send a GETINFO message to the
with the "Multicast Scope List" AND "Multicast Scope Nesting State
option codes listed in an Option Request option
4. Managing Dynamically Nested
Scopes can either be manually or automatically configured.
scopes are manually configured the relationships between them
also be static, assuming that network does not partition due
router failure. Should the network partition or heal after
partition it is highly likely that the nesting relationships
change. Scope nesting relationships will also change as a network
brought up or when a change is deliberately made to a router
through manual reconfiguration or by some automatic means
To ensure that nesting relationships are correctly determined
scope boundaries undergo change MADCAP servers MUST include
mechanism that allow for
a) whether the nesting decision is still under consideration
can be considered definitive, and therefore be announced
MADCAP clients
b) whether one or both scopes for a particular nesting state
have been destroyed, and hence whether the nesting state
therefore be discarded
c) whether the scope boundaries have changed so that whereas
X did or did not nest inside scope Y, the opposite is now true
To realize a) and b) MADCAP servers MUST implement the following
timers; NEST_NO_DECISION_TIMER, ZONES_EXIST_TIMER
The first timer, NEST_NO_DECISION_TIMER, is used to mark time
a MADCAP server's first hearing of a scope and making a
about its relationship to other zones. Up until the time this
expires MADCAP servers MUST NOT conclude that the scope nests
another
The NEST_NO_DECISION_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
boundaries for zone X and zone Y change so that zone X now
inside zone Y
The second timer ZONES_EXIST_TIMER will be used to timeout
internal state between two scopes in the event that one or
scopes are destroyed
Kermode Standards Track [Page 8]
RFC 2907 MADCAP Multicast Scope Nesting State Option September 2000
4.1 MADCAP Server processing of MZAP
When MZAP is used to discover the nesting relationship between
MADCAP servers will eavesdrop into the MZAP messages that
periodically transmitted by the Zone Border Routers (ZBR) during
normal course of administrative scope boundary maintenance. In
way they will be able to learn which scopes exist (via
Announcement Messages, ZAMs) and which of these scopes do not
(via Not Inside Messages, NIMs). This state must be cached within
MADCAP server
When a MADCAP server S receives a NIM from a ZBR
information that scope X does not nest in scope Y, it MUST update
internal state in the following manner
1) S MUST update its internal X/Y state to "false".
2) S MUST restart NEST_NO_DECISION_TIMER for the newly
X/Y state
4.2 Updating State for Dynamic Scopes due to timer expiration
MADCAP servers will update X/Y nesting state upon the expiration
timers in the following manner
o If the NEST_NO_DECISION_TIMER expires for a state entry X/Y AND
MADCAP messages have been received that indicate scope X does
nest inside scope Y, a MADCAP Server, S, MUST conclude that
X nests inside scope Y. As a result S will change X/Y
"false" to "true".
When a state change from "false" to "true" occurs for X/Y, S
also start the ZONES_EXIST_TIMER timer for X/Y.
ZONES_EXIST_TIMER should only reset when a Zone
Message (ZAM) has been received for both zone X and zone Y
the last time it was restarted. This ensures that both zone X
zone Y are known to still exist
o If the ZONES_EXIST_TIMER expires for a state entry X/Y,
SHOULD conclude that either zone Y or zone X no longer exists
hence that both X/Y and Y/X state should be destroyed
5. Multicast Scope Nesting State Option
Code Len Count Nest State
+-----+-----+-----+-----+-----+-----+-...-+-----+
| 17 | p | m | N1 | | Nm |
+-----+-----+-----+-----+-----+-----+-...-+-----+
Kermode Standards Track [Page 9]
RFC 2907 MADCAP Multicast Scope Nesting State Option September 2000
Code: 16
Option identifier 17.
Len: 16
The length of the option in bytes
Count: 8
The number of zones present in the Nest State Matrix. This
MUST be identical to the Count field in the preceding
State List option. If this is not the case the scope
state information MUST BE ignored
Nest State Matrix
The compressed bit-packed representation of the matrix,
in the same manner as shown in Figure 4. Note for N
the compressed matrix will be N times ceil((N-1)/8) bytes long
where ceil() is the function that rounds up to the nearest integer
The scopes corresponding to the rows and columns of this
list in the same order as they appear in the Multicast
List Option
6.
[NEST_NO_DECISION_TIMER] The time after which a MADCAP server
client can assume that a message announcing that two
do not nest should not be received. The length of this
is dependent upon the zone announcement protocol used
inform the MADCAP router of which zones currently exist
When MZAP [RFC2776] is used this value should be greater
the MZAP timeout value NIM-INTERVAL +30%. This
to a timeout value of 1800 + 30% = 2340 seconds (39 minutes).
[ZONES_EXIST_TIMER] The time after which a MADCAP server or
should assume that the zone in question does not exist
zones are detected dynamically. The length of this timer
dependent upon the zone announcement protocol used to
the MADCAP router of which zones currently exist. When
[RFC2776] is used this value should be no less than the
timeout value NIM-HOLDTIME, which has a default
5460 seconds (91 minutes).
Kermode Standards Track [Page 10]
RFC 2907 MADCAP Multicast Scope Nesting State Option September 2000
7. Security
Since this document proposes an extension to the MADCAP protocol
the addition of a new option, the same set of security
apply
In addition to these concerns are those that would arise were
information in the Multicast Scope Nesting State option to
falsified. In this case the clients would be misinformed as to
scopes nest inside one another. In this event, the client would
make incorrect decisions regarding the order in which to use
scopes. The effect of this would be to use larger scopes
necessary, which would effectively flatten any scope
present and nullify the advantage afforded by the hierarchy'
presence
Thus a malformed or tampered Multicast Scope Nesting option may
protocols that rely upon the existence of a scoping hierarchy
scale less well, but it would not prevent them from working
8. IANA
The Multicast Nesting State Option has been assigned MADCAP
code 17 by the IANA [RFC2730].
9.
The Author would like to acknowledge Mark Handley and Dave Thaler
the helpful discussions and feedback which helped shape and
this document
10.
[KERM] Kermode, R., "Smart Network Caches: Localized Content
Application Negotiated Recovery Mechanisms for
Media Distribution", Ph.D. Thesis, MIT Media Laboratory
June 1998.
[RFC2119] Bradner, S., "Key words for use in RFCs to
Requirement Levels", BCP 14, RFC 2119, March 1997.
[RFC2365] Meyer, D., "Administratively Scoped IP Multicast", BCP 23,
RFC 2365, July 1998.
Kermode Standards Track [Page 11]
RFC 2907 MADCAP Multicast Scope Nesting State Option September 2000
[RFC2730] Patel, B.V., Shah, M. and S.R. Hanna, "Multicast
Dynamic Client Allocation Protocol (MADCAP)", RFC 2730,
December 1999.
[RFC2776] Handley, M., Thaler, D. and R. Kermode, "Multicast-
Zone Announcement Protocol (MZAP)", RFC 2776,
2000.
[RFC2908] Handley, M., Thaler, D. and D. Estrin, "The
Multicast Address Allocation Architecture", RFC 2908,
September 2000.
11. Author's
Roger
Motorola Australian Research
Locked Bag 5028
Botany, NSW 1455
EMail: Roger.Kermode@motorola.
Kermode Standards Track [Page 12]
RFC 2907 MADCAP Multicast Scope Nesting State Option September 2000
12. Full Copyright
Copyright (C) The Internet Society (2000). All Rights Reserved
This document and translations of it may be copied and furnished
others, and derivative works that comment on or otherwise explain
or assist in its implementation may be prepared, copied,
and distributed, in whole or in part, without restriction of
kind, provided that the above copyright notice and this paragraph
included on all such copies and derivative works. However,
document itself may not be modified in any way, such as by
the copyright notice or references to the Internet Society or
Internet organizations, except as needed for the purpose
developing Internet standards in which case the procedures
copyrights defined in the Internet Standards process must
followed, or as required to translate it into languages other
English
The limited permissions granted above are perpetual and will not
revoked by the Internet Society or its successors or assigns
This document and the information contained herein is provided on
"AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET
TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED,
BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE
HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES
MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE
Funding for the RFC Editor function is currently provided by
Internet Society
Kermode Standards Track [Page 13]
if you see any problems within the linking, don't worry be happy,
this is version 0.1 of the Relevance System and you gotta expect some crappy subroutines sometimes,
just be content we did not write this in Java, which would have made this "bigger and better" HAHAHHA.
RFC documents can be found at I.E.T.F.
Relevance System Copyright © 2002 Spectrum WorldResearch
other technical nosh by ServerMasters Corporation
collaboration of BobX
