Oct 21 2009

Layer 2 Multicast Addresses

Network Interface cards can accept Ethernet frames destined towards the following MAC addresses.

  • BIA (Mac Address of the NIC)
  • 0xFFFF.FFFF.FFFF (Broadcast Address)
  • A range of multicast Address

In this post we will discuss the range of multicast addresses.

Ethernet Multicast Addresses

An Ethernet multicast address consists of the

  • The IANA owned OUI MAC address 01:00:5e (24 bits) – which includes a multicast bit.
  • IANA owns the OUI MAC address 01:00:5e, therefore multicast packets are delivered by using the Ethernet MAC address range 01:00:5e:00:00:00 – 01:00:5e:7f:ff:ff.
  • The lower 23 bits of the multicast IP address are mapped into the remaining 23 bits of available ethernet address space.

The multicast addresses are in the range is 224.0.0.0 through 239.255.255.255. Therefore we can conclude the following:

  • All multicast addresses have the first four bits in the first octet set to 1110.
  • Therefore 28 bits remaining in the IP address to identify a unique multicast address.

The Diagram below illustrates the multicast MAC address range as well as an example of a Multicast Layer 3 Address encoding.

Layer-2-multicast

Multicast IP Address Encoding

When encoding layer 3 multicast addresses, the following observations can be seen.

  • The first octect In the layer 3 address ie 239 in our example is not encoded.
  • As all layer multicast addresses begin with 1110 as the first octect.
  • As the remaining four bits in the 1st octet of the multicast IP address are not encoded, we can say that 4 configurable bits are lost.
  • We can also note that as the 4th Octet in the Multicast MAC address has an upper limit of 7F, only 7 bits are available to encode the 2nd octet of the multicast IP addresses which means an additional configurable bit is lost in encoding.
  • Therefore a total of 5 configurable bits are lost during multicast IP to MAC encoding.
  • The net result here is that 32 unique Multicast IP addresses when encoded will result in the same Multicast MAC address.

The diagram below illustrates how 32 Multicast Layer 3 addresses are encoded into 1 Multicast MAC Address.

Layer-2-multicast-encoding

By Zarar • CCIE, CCIE SP, Multicast • 1 • Tags: , ,

Oct 14 2009

Electing an RP (in brief)

The PIMv2 RFC states:

“This specification does not mandate the use of a single mechanism to provide routers with the information to perform the group-to-RP mapping. Currently four mechanisms are possible, and all four have associated problems:

  1. Static Configuration: A PIM router MUST support the static configuration of group-to-RP mappings. Such a mechanism is not robust to failures, but does at least provide a basic interoperability mechanism.
  2. Embedded-RP: Embedded-RP defines an address allocation policy in which the address of the Rendezvous Point (RP) is encoded in an IPv6 multicast group address.
  3. Cisco’s Auto-RP: Auto-RP uses a PIM Dense-Mode multicast group to announce group-to-RP mappings from a central location.
  4. BootStrap Router (BSR): RFC 2362 specifies a bootstrap mechanism based on the automatic election of a bootstrap router (BSR). Any router in the domain that is configured to be a possible RP reports its candidacy to the BSR, and then a domain-wide flooding mechanism distributes the BSR’s chosen set of RPs throughout the domain.

In this post we will look briefly at 1,3 and 4.

Static Configuration

Configuring a Static RP is fairly straight forward. The same RP is configured on each router in the multicast domain. There are some variations here where you can assign groups to different RPs to distributre the multicast load in the network.

Auto-RP

Auto-RP makes use of two multicast groups ie 224.0.1.39 and 224.0.1.40. The first address is 224.0.1.39 is used by the candidate RPs to announce their availability to be the RP for all or some multicast groups. The mapping agents listen for the candidate RP announcements and then send out group to RP mappings to the multicast group 224.0.1.40 address.

BSR

Within each multicast domain at least one of the routers must be configured as a candidate-BSR. The candidate BSR(s) each send Boot Strap Messages(BSM) out of all its interfaces to the ALL-PIM-ROUTERS (224.0.0.13) address. When a router receives Bootstrap message sent to `ALL-PIM-ROUTERS’ it performs the following:

  1. If the message was not sent by the RPF neighbor towards the BSR address included, the message is dropped. (ie if a PIM router receives a message from the BSR on an interface which is not the route back to the BSR, the BSM is dropped.)
  2. If the BSM is received on an interface which is the outgoing interface back towards the BSR then forwarded out all PIM interfaces, excluding the one over which the message arrived, to `ALL-PIM-ROUTERS’ group, with a TTL of 1.

The original messages sent out by the BSR do not contain any RP information as the candidate-RP has yet to be configured. Once a candidate-RP has been configured it sends a unicast candidate-RP advertisement to the BSR which in turn sends out a BSM containing the RP information to all the routers in the multicast domain.

The BSR collects the information from all candidate RPs. It places the information for all candidate RPs into subsequent Bootstrap messages. The BSR performs the election of the active RP of each group range only for its own use. Each router in the domain is responsible for running the RP-selection hash algorithm on the candidate RP information contained in the Bootstrap messages.

Note:

BSR differs from Auto-RP in that BSR does not create or require that any state is maintained in the mroute table. When using Auto-RP a method must be implemented to dense-flood the RP information throughout the multicast domain. This can be done in one of two ways, either implement PIM-Sparse-Dense mode or use the Auto-RP listener feature.

By Zarar • CCIE, CCIE SP, Multicast, PIM-DM, PIM-SM • 4 • Tags: , , ,

Oct 14 2009

PIM Assert Messages

Where multiple PIM routers peer over a shared LAN, it is possible for more than one upstream router to have valid forwarding state for a packet, which can lead to packet duplication. PIM does not attempt to prevent this from occurring. Instead, it detects when this has happened and elects a single forwarder amongst the upstream routers to prevent further duplication. This election is performed using PIM Assert messages. Assert messages are also received by downstream routers on the LAN, and these cause subsequent Join/Prune messages to be sent to the upstream router that won the Assert.

The above content was taken from RFC 4601

By Zarar • CCIE, CCIE SP, Multicast, PIM-SM • 0 • Tags: , , ,

Oct 13 2009

Building the shared and shortest path Tree

The Shared tree is rooted at the RP and the shortest path tree is rooted at the Source of the multicast traffic.

The following processes will be discussed.

  1. Building the shared tree between the receivers and the RP
  2. Forwarding unicast PIM Register packets from the source to the RP
  3. Building the shortest Path tree between the RP and the source
  4. Building the Shortest-Path Tree between the Source and Receiver

Building the shared tree between the receivers and the RP

  1. A multicast receiver expresses its interest in receiving traffic destined for a multicast group. Typically, it does this using IGMP or MLD.
  2. One of the receiver’s local routers is elected as the Designated Router (DR) for that subnet.
  3. On receiving the receiver’s expression of interest, the DR then sends a PIM Join message towards the RP for that multicast group.
  4. This Join message is known as a (*,G) Join because it joins group G for all sources to that group.
  5. The (*,G) Join travels hop-by-hop towards the RP for the group, and in each router it passes through, a multicast tree state for group G is instantiated.
  6. Eventually, the (*,G) Join either reaches the RP or reaches a router that already has (*,G) Join state for that group.
  7. When many receivers join the group, their Join messages converge on the RP and form a distribution tree for group G that is rooted at the RP.
  8. This is known as the RP Tree (RPT), and is also known as the shared tree because it is shared by all sources sending to that group.
  9. Join messages are resent periodically so long as the receiver remains in the group.
  10. When all receivers on a leaf-network leave the group, the DR will send a PIM (*,G) Prune message towards the RP for that multicast group.
  11. However, if the Prune message is not sent for any reason, the state will eventually time out.

Forwarding unicast PIM Register packets to the RP

  1. A multicast data sender just starts sending data destined for a multicast group.
  2. The sender’s local router (DR) takes those data packets, unicast-encapsulates them, and sends them directly to the RP.
  3. The RP receives these encapsulated data packets, decapsulates them, and forwards them onto the shared tree.
  4. The packets then follow the (*,G) multicast tree state in the routers on the RP Tree being replicated wherever the RP Tree branches, and eventually reaching all the receivers for that multicast group.
  5. The process of encapsulating data packets to the RP is called registering, and the encapsulation packets are known as PIM Register packets.
  6. At this stage, multicast traffic is flowing encapsulated to the RP, and then natively over the RP tree to the multicast receivers.

Building the shortest Path tree between the RP and the source

  1. Register-encapsulation of data packets is inefficient for two reasons:
    1. Encapsulation and decapsulation may be relatively expensive operations for a router to perform, depending on whether or not the router has appropriate hardware for these tasks.
    2. Traveling all the way to the RP, and then back down the shared tree may result in the packets traveling a relatively long distance to reach receivers that are close to the sender. For some applications, this increased latency or bandwidth consumption is undesirable
  2. Therefore when the RP receives a register-encapsulated data packet from source S on group G, it will normally initiate an (S,G) source-specific Join towards S.
  3. This Join message travels hop-by-hop towards S, instantiating (S,G) multicast tree state in the routers along the path.
  4. (S,G) multicast tree state is used only to forward packets for group G if those packets come from source S.
  5. Eventually the Join message reaches S’s subnet or a router that already has (S,G) multicast tree state.
  6. Packets from S start to flow following the (S,G) tree state towards the RP.
  7. While the RP is in the process of joining the source-specific tree for S, the data packets will continue being encapsulated to the RP.
  8. When packets from S also start to arrive natively at the RP, the RP will be receiving two copies of each of these packets.
  9. At this point, the RP starts to discard the encapsulated copy of these packets.
  10. The RP then sends a Register-Stop message back to S’s DR to prevent the DR from unnecessarily encapsulating the packets.
  11. At this stage, traffic will be flowing natively from S along a source-specific tree to the RP, and from there along the shared tree to the receivers.
  12. Where the two trees intersect, traffic may transfer from the source-specific tree to the RP tree and thus avoid taking a long detour via the RP.

Building the Shortest-Path Tree between the Source and Receiver

  1. Although having the RP join back towards the source removes the encapsulation overhead, it does not completely optimize the forwarding paths.
  2. For many receivers, the route via the RP may involve a significant detour when compared with the shortest path from the source to the receiver.
  3. To obtain lower latencies or more efficient bandwidth utilization, a router on the receiver’s LAN, typically the DR, may initiate a transfer from the shared tree to a source-specific shortest-path tree (SPT).
  4. To do this, it issues an (S,G) Join towards S.
  5. This instantiates state in the routers along the path to S.
  6. Eventually, this join either reaches S’s subnet or reaches a router that already has (S,G) state.
  7. When this happens, data packets from S start to flow following the (S,G) state until they reach the receiver.
  8. At this point, the receiver (or a router upstream of the receiver) will be receiving two copies of the data: one from the SPT and one from the RPT.
  9. When the first traffic starts to arrive from the SPT, the DR or upstream router starts to drop the packets for G from S that arrive via the RP tree.
  10. In addition, it sends an (S,G) Prune message towards the RP. This is known as an (S,G,rpt) Prune.
  11. The Prune message travels hop-by-hop, instantiating state along the path towards the RP indicating that traffic from S for G should NOT be forwarded in this direction.
  12. The prune is propagated until it reaches the RP or a router that still needs the traffic from S for other receivers.
  13. By now, the receiver will be receiving traffic from S along the shortest-path tree between the receiver and S.
  14. In addition, the RP is receiving the traffic from S, but this traffic is no longer reaching the receiver along the RP tree.
  15. As far as the receiver is concerned, this is the final distribution tree.

The above content was taken from RFC 4601

By Zarar • CCIE, CCIE SP, Multicast, PIM-SM • 0 • Tags: , , ,

Oct 12 2009

Pim Packet Formats

The following information was taken from the RFCs below.

  • RFC 4601(Obsoletes RFC 2362) — Protocol Independent Multicast – Sparse Mode (PIM-SM)
  • RFC 5059 — Bootstrap Router (BSR) Mechanism for Protocol Independent Multicast (PIM)

To read the RFCs please visit the links below.

ftp://ftp.rfc-editor.org/in-notes/rfc4601.txt

ftp://ftp.rfc-editor.org/in-notes/rfc5059.txt

The following PIM packets formats are described within rfc 4601 and 5059.

RFC 4601 PIM Packet Formats

  • Hello Message Format
  • Register Message Format
  • Register-Stop Message Format
  • Join/Prune Message Format
  • Assert Message Format

RFC 5059 PIM Packet Formats

  • Bootstrap Message Format
  • Candidate-RP-Advertisement Message Format

PIM Packet Header

All PIM control messages have IP protocol number 103. PIM messages are either unicast (e.g., Registers and Register-Stop) or multicast with TTL 1 to the ‘ALL-PIM-ROUTERS’ group (e.g., Join/Prune, Asserts, etc.). Candidate-RP-Advertisement messages are unicast to a BSR. Usually, Bootstrap messages are multicast with TTL 1 to the ALL-PIM-ROUTERS group, but in some circumstances (described in section 3.5.2 RFC 5059) Bootstrap messages may be unicast to a specific PIM neighbor.

The source address used for unicast messages is a domain-wide reachable address; the source address used for multicast messages is the link-local address of the interface on which the message is being sent.

The IPv4 ‘ALL-PIM-ROUTERS’ group is ’224.0.0.13′. The IPv6 ‘ALL-PIM-ROUTERS’ group is ‘ff02::d’.

All the PIM Packets have the common header below.

PIM-Common-header

The Pim Version is 2.

The Message type is one of those listed in the table below.

Message Type Destination
0 = Hello Multicast to ALL-PIM-ROUTERS
1 = Register Unicast to RP
2 = Register-Stop Unicast to Source of Register Packet
3 = Join/Prune Multicast to ALL-PIM-ROUTERS
4 = Bootstrap Multicast to ALL-PIM-ROUTERS
5 = Assert Multicast to ALL-PIM-ROUTERS
6 = Graft (Used in PIM-DM only) Unicast to RPF’ (S)
7 = Graft-Ack (Used in PIM-DM only) Unicast to Source of Graft Packet
8 = Candidate-RP-Advertisement Unicast to Domain’s BSR

The “Reserved” field is set to zero on transmission and ignored upon receipt.

The “Checksum” is a standard IP checksum.

PIM Hello Packet

The PIM Hello packet contains the PIM common header as described above as well as a series of optional fields namely. Optiontype, OptionLength and OptionValue. Multiple Options triplets can be transmitted in the hello packet.

PIM-hello

The OptionType is one of those listed in the table below.

Option Type Optiontype Description
OptionType 1 Holdtime
OptionType 2 LAN Prune Delay
OptionType 3 to 16 reserved to be defined in future versions of this document
OptionType 18 deprecated and should not be used
OptionType 19 DR Priority
OptionType 20 Generation ID
OptionType 24 Address List

Whether all of these options are implemented in IOS will be examined in subsequent posts.

Register Message Format

A Register message is sent by the DR to the RP when a multicast packet needs to be transmitted on the RP-tree. The IP source address is set to the address of the DR, the destination address to the RP’s address. The IP TTL of the PIM packet is the system’s normal unicast TTL.

PIM-register

Field Description
B The border bit – If the router is a DR for a source that it is directly connected to, it sets the B bit to 0.
N The Null-Register bit – Set to 1 by a DR that is probing the RP before expiring its local Register-Suppression Timer. Set to 0 otherwise.
Reserved2 Transmitted as zero, ignored on receipt.
Multicast Data Packet The original packet sent by the source.

The Register-Stop packet format

A Register-Stop is unicast from the RP to the sender of the Register message. The IP source address is the address to which the register was addressed. The IP destination address is the source address of the register message.

PIM-register-stop

Field Description
Group Address The group address from the multicast data packet in the original Register message sent to the RP
Source Address The host address of the source from the multicast data packet in the original Register message sent to the RP.

Join/Prune Message Format

A Join/Prune message is sent by routers towards upstream sources and RPs. Joins are sent to build shared trees (RP trees) or source trees (SPT). Prunes are sent to prune source trees when members leave groups as well as sources that do not use the shared tree.

PIM-join-prune

Field Description
Upstream Neighbor Address The address of the upstream neighbor that is the target of the message. For IPv6 the source address used for multicast messages is the link-local address of the interface on which the message is being sent. For IPv4, the source address is the primary address associated with that interface.
Reserved Transmitted as Zero, ignored on receipt.
Holdtime The amount of time a receiver must keep the Join/Prune state alive, in seconds.
Number of Groups The number of multicast group sets contained in the message
Multicast group address For format description, see Section 4.9.1. in RFC 4601
Number of Joined Sources Number of joined source addresses listed for a given group
Joined Source Address 1 .. n This list contains the sources for a given group that the sending router will forward multicast datagrams from if received on the interface on which the Join/Prune message is sent.
Number of Pruned Sources Number of pruned source addresses listed for a group
Pruned Source Address 1 .. n This list contains the sources for a given group that the sending router does not want to forward multicast datagrams from when received on the interface on which the Join/Prune message is sent.

Assert Message Format

The Assert message is used to resolve forwarder conflicts between routers on a link. It is sent when a router receives a multicast data packet on an interface on which the router would normally have forwarded that packet. Assert messages may also be sent in response to an Assert message from another router.

PIM-Assert

Field Description
Group Address The group address for which the router wishes to resolve the

forwarding conflict.
Source Address Source address for which the router wishes to resolve the

forwarding conflict. The source address MAY be set to zero for (*,G) asserts (see below).
R RPT-bit is a 1-bit value. The RPT-bit is set to 1 for Assert(*,G) messages and 0 for Assert(S,G) messages.
Metric Preference Preference value assigned to the unicast routing protocol that provided the route to the multicast source or Rendezvous-Point.
Metric The unicast routing table metric associated with the route used to reach the multicast source or Rendezvous-Point. The metric is in units applicable to the unicast routing protocol used.

By Zarar • CCIE, CCIE SP, Multicast, PIM-SM • 2 • Tags: , , ,

Oct 11 2009

Multicast posts

In the next few weeks, time permitting I will try and cover the following range of subjects around multicast.

  • PIM-V2
  • PIM-SM
  • PIM-SSM
  • PIM-bidir
  • Inter-domain Multicast
  • MVPN
  • Inter-As MVPN

To begin with here is a list of some important reserved multicast addresses.

Multicast Address Usage
224.0.0.1 All Multicast Hosts
224.0.0.2 All Multicast Routers
224.0.0.4 DVMRP Routers
224.0.0.5 All OSPF Routers
224.0.0.6 OSPF Designated Routers
224.0.0.9 RIPv2 Routers
224.0.0.10 EIGRP Routers
224.0.0.13 PIM Routers
224.0.0.22 IGMPv3
224.0.0.25 RGMP
224.0.1.39 Cisco-RP-Announce
224.0.1.40 Cisco-RP-Discovery

By Zarar • CCIE SP, Multicast • 3 • Tags: , , ,