Subject: Handling of JOIN messages

From: Frédéric Larbre <[email-masked]>
Date: Thu, 26 Apr 2001 14:59:21 +0200

Hi all,

I am trying to understand how the JOIN messages are handled by BGMP.
The Internet draft is sometimes not clear enough to me, so I tried to
resume the section 5.3.1 into an algorithm that is described below.
I am wondering if I am on the good way, and I'd like to get some comments
about my understanding...

Thanks,
-- Frederic Larbre

////////////////////////////////////////////////////////////////////////////
////////////////////////
// when the local BGMP component receives a JOIN message, it searches the
tree
// state table for a matching entry
entry_found, entry = lookupEntry(tree_state_table, join_request);
if(entry_found)

	// there is a matching entry in the tree state table

	if((SOURCE_OF(join_request) == ALL_SOURCES) and SOURCE_OF(entry) ==
ALL_SOURCES) {
		// the JOIN request is for a (*,G) state and there is already an
		// entry in the tree state table for the (*,G) state with the same G

		if(!isInTargetList(entry, join_initiator)) {
			// the join initiator is not listed in the target list. The
			// target from which the JOIN request was received is then
			// added to the target list of the matching entry
			addToTargetList(entry, join_initiator);
		}

		end.

	} elseif((SOURCE_OF(join_request) == ALL_SOURCES) and (SOURCE_OF(entry) !=
ALL_SOURCES)) {
		// the JOIN request is for a (*,G) state and there is already an
		// entry in the tree state table for the (S,G) state with the same G

		S = SOURCE_OF(entry);
		G = GROUP_OF(entry);
		NRG = NOMINAL_ROOT_OF_G(entry);

		next_hop_towards_S    = lookupNextHop(S);
		next_hop_towards_nr_G = lookupNextHop(NRG);
		if(next_hop_towards_S != next_hop_towards_nr_G) {
			// the next hop peers toward S and the nominal root of G are
			// different
			// send a (S,G) PRUNE message towards the source S
			sendPRUNE(next_hop_towards_S, S, G);

			// clear the SPT bit on the (S,G) entry
			clearSPT(tree_state_table, entry);
		}
	}

} else {
	// no entry was found, one must be created

	if(SOURCE_OF(join_request) == ALL_SOURCES) {
		// the JOIN request is not source-specific, an (*,G) entry must be
		// created
		entry = createGroupForwardingStateEntry(ALL_SOURCES,
                                        GROUP_OF(join_request));

		// the local BGMP component retrieves the next hop towards the
		// nominal root of G according to the Multicast RIB of the EGP
		next_hop = lookupNextHop(NOMINAL_ROOT_OF_G(join_request));

		if(isInternalPeer(next_hop)) {
			// the next hop towards the nominal root of G is an
			// internal peer. The target list of the newly created
			// entry must be initialized to contain the MIGP
			// component owning the next hop interface
			migp_component_interface = getMIGPComponentInterface(next_hop);
			addToTargetList(entry, migp_component_interface);

		} else {
			// the next hop towards the nominal root of G is an external
			// peer or the next hop component. The target list of the
			// entry – created above – must be initialized to contain it.

			addToTargetList(entry, next_hop);
		}

		// the target from which the JOIN request was received is then added
		// to the target list of the newly created entry
		addToTargetList(entry, join_initiator);

	} else {
		// the JOIN request is source-specific, an (S,G) entry must be
		// created

		S = SOURCE_OF(join_request);
		G = GROUP_OF(join_request);
		NRG = NOMINAL_ROOT_OF_G(join_request);

		entry = createSourceForwardingStateEntry(S, G);

		if(isAnInternalSource(S)) {
			// the source is internal to the BGMP speaker’s domain. The
			// “Poison Reverse” (PR-bit) must be set.
			setPR(entry);
		}

		// the target from which the JOIN request was received is then added
		// to the target list of the newly created entry
		addToTargetList(entry, join_initiator);

		if(isInternalPeer(join_initiator) {
			// the join initiator is an internal peer
			// The target list of the newly created  entry must be contain
			// the MIGP component interface towards the peer that initiates
			// the JOIN.
			migp_component_interface = getMIGPComponentInterface(join_initiator);
			addToTargetList(entry, migp_component_interface);

			entry_found, e = lookupEntry(tree_state_table, <(S,G)>);
				if(entry_found and isPR(e)) {
					// a (S,G) state exists with the PR-bit set

					next_hop, isPeer = lookupNextHop(NRG);
					if(isThroughMIGPComponent(next_hop)) {
						// the next hop is through the MIGP component
						// interface

						// send a POISON_REVERSE message
						sendPOISON_REVERSE(join_initiator, S, G);
					}
				}

		} else {
			// the join initiator is an external peer

			entry_found, e = lookupEntry(tree_state_table, <(S,G)>);
			if(entry_found and then (isPR(e) and isBestExit(NRG))) {
				// a (S,G) state exists with the PR-bit set. The local
				// BGMP speaker is the best exit for the nominal root of G

				next_hop = lookupNextHop(NRG);
				if(getComponentInterface(next_hop) ==
getComponentInterface(join_initiator)) {
					// the next hop towards the nominal root of G is
					// through the interface towards the external peer

					// send a POISON_REVERSE message
					sendPOISON_REVERSE(join_initiator, S, G);
				}
			}
		}
	}

	// the entry can now be added to the tree state table
	addEntry(tree_state_table, entry);
}

S = SOURCE_OF(entry);
G = GROUP_OF(entry);
NRG = NOMINAL_ROOT_OF_G(entry);

if(S == ALL_SOURCES) {
	// the entry is not source-specific, it’s an (*,G) entry

	// find the next hop EGP peer towards the nominal root of G in the
	// Multicast RIB
	next_hop, isPeer = lookupNextHop(NRG);
} else {
	// the entry is source-specific, it’s an (S,G) entry

	// find the next hop EGP peer towards S in the Multicast RIB
	next_hop, isPeer = lookupNextHop(S);
}

if(!isNull(getTargetListWithoutNextHop(entry, next_hop)) {
	// the target list is not inclluding the next hop is non-null

	if(isPeer) {
		// the next hop peer exists

		if(!isInternalPeer(next_hop)) {
			// the next hop peer towards the nominal root of G is an
			// external peer

			// send a (*,G) or (S,G) JOIN message towards the next hop
			if(S == ALL_SOURCES) {
				sendJOIN(next_hop, S, G);

			} else {
				entry_found, e = lookupEntry(tree_state_table, <(*,G)>);
				if(!entry_found) {
					// the router does not have any (*,G) state
					// matching the entry

					// send a (S,G) JOIN message unicast to the
					// external peer
					sendJOIN(next_hop, S, G);
				}

			}

		} else {
			// the next hop peer towards the nominal root of G is an
			// internal peer

			// retrieves the MIGP component owning the next hop interface
			migp_component_interface = getMIGPComponentInterface(next_hop);

			// send a (S,G) or (*,G) JOIN message unicast to the interface
			sendJOIN(migp_component_interface, S, G);
		}

	} else {
		// the next hop peer does not exist

		// retrieves the MIGP component owning the next hop interface
		migp_component_interface = getMIGPComponentInterface(next_hop);

		// send a (S,G) or (*,G) JOIN message unicast to the interface
		sendJOIN(migp_component_interface, S, G);
	}
}
////////////////////////////////////////////////////////////////////////////
////////////////////////