Friday, January 23, 2009

BSCI: IP Multicast - PIM Routing Protocol

  • PIM stands for Protocol Independent Multicast.
  • The “protocol independent” part of the name refers to the fact that PIM uses the unicast routing protocol table to locate unicast addresses, regardless of how the table learned the addresses.
    • That is, the table could be formed by any unicast routing protocol such as EIGRP, OSPF, etc. and it does not have any bearings about its relationship with PIM.
  • Unlike some unicast routing protocols, however, no routing updates are sent between PIM routers.
  • Keep in mind that unicast routing protocols use multicast packets (or broadcast in some cases) to send their routing update traffic.

Terminologies

Distribution Trees

  • When forwarding multicast packets, multicast-enabled routers use PIM to dynamically create distribution trees that control the path that IP multicast traffic takes through the network to deliver the packets to all receivers
  • 2 Types of Distribution Trees
    • Source Tree
      • A source tree is created for each source router sending to each multicast group.
      • The root is at the source and has branches through the network to the receivers.
      • It is also know as source-routed or shortest path trees (SPTs) because the tree uses the most direct and shortest path to the receivers.
    • Shared Tree
      • A shared tree has one path or tree that is shared between all sources for each multicast group.
      • The shared tree uses one single common root called a rendezvous point (RP).
      • Sources would initially send their packets to the RP. From there the data is forwarded through the shared tree to the destination members.

Reverse Path Forwarding (RPF)

  • This refers to the forwarding of multicast traffic away from the source, rather than forwarding to the receiver. It is the opposite operation of unicast routing.
  • For multicast, the source IP address refers to the known source, and the destination IP address denotes a group of unknown receivers.
  • RPF avoids routing loops by using the unicast routing table to determine the upstream (toward the source) and downstream (away from the source) neighbors and ensures that only one interface on the router is considered to be an incoming interface for data from a specific source.
  • RPF check procedure:
    • Step 1. Router looks up the source address in the unicast routing table to determine if it has arrived on the interface that is on the reverse path back to the source.
    • Step 2. If packet has arrived on the interface leading back to the source, the RPF check is successful and the packet will be forwarded.
    • Step 3. If the RPF check in 2 fails, the packet is dropped.
  • RPF is a fundamental concept in multicast routing that enables routers to correctly forward multicast traffic down the distribution tree. RPF makes use of the existing unicast routing table to determine the upstream and downstream neighbors. A router will only forward a multicast packet if it is received on the upstream interface. This RPF check helps to guarantee that the distribution tree will be loop free.

PIM Modes

  • There are 2 main PIM modes:
    • Sparse Mode (PIM-SM)
      • Sparse mode uses a “pull” model to send multicast traffic.
      • Uses shared tree distribution, therefore an RP is required.
      • Sources register with RP.
      • When active receivers actively request to join a specific multicast group, routers along the path of these receivers register to join that group.
        • Using unicast routing table, these routers calculate whether they have a better metric to the RP or to the source itself.
        • Whichever device has a better metric, the join message is forwarded to that device.
    • Dense Mode (PIM-DM)
      • Dense mode uses a “push” model to flood multicast traffic to the entire network.
      • Uses source trees.
      • In this mode, routers that have no need for the data (because they are not connected to receivers that want the data or to other routers that want it) request that the tree is pruned so that they no longer receive the data.
  • PIM Sparse-Dense mode is a hybrid of the 2 main PIM modes.

Multicast Distribution Trees

Source Distribution Trees

  • Source trees are the simplest form of a multicast distribution tree.
  • The root of the tree is at the source.
  • It is also called a shortest path tree because it uses the shortest path through a network.

multicastsourcetree

  • In the above diagram, it illustrates an example of a shortest path tree (SPT) for group 224.1.1.1.
  • The root is the source (Host A).
  • Packets are forwarded according to the source and group address pair along the tree.
  • The forwarding state associated with the source tree is referred to by the notation (S, G), pronounced “S comma G“.
    • S is the IP address of the source and G is the multicast group address.
    • Using this notation, the SPT for the example above is (192.1.1.1, 224.1.1.1)
  • The (S, G) notation implies that a separate SPT exists for each individual source sending to each group.
    • For example, if Host B is also sending traffic to group 224.1.1.1 and Hosts A and C are receivers, the a separate (S, G) SPT would exist.
    • In the case of Host B being the source, the notation is (192.2.2.2, 224.1.1.1)

With source trees, a separate tree is built for every source S sending to group G.

Shared Distribution Trees

  • Unlike source trees whose root is at the source, shared trees has a single common root placed at some chosen point in the network.
  • This shared root is called a Rendezvous Point (RP).

multicastsharedtree

  • In the figure above, the root is located at Router D for multicast group 224.2.2.2.
  • Sources send their traffic to the root and the traffic is forwarded down the share tree to reach all receivers.
    • In the example above, multicast traffic from the sources (Hosts A and D) travels to the root (Router D) and then is forwarded down the shared tree to the receivers (Hosts B and C).
  • Because all sources in the multicast group use a common shared tree, the forwarding state for the shared tree is identified with the notation (*, G), pronounced “star comma G.
    • * means all sources, and G represents the multicast group.
    • Therefore, the shared tree in the figure above is notated as (*, 224.2.2.2).

Comparison

  • Shortest Path Trees
    • Have the advantage of creating the optimal path between the source and receivers. This will guarantee the minimum amount of network latency for forwarding multicast traffic.
    • However, because routers must maintain path information for each source, they use more memory and processing power.
  • Shared Trees
    • Have the advantage of requiring the minimum amount of state in each router. This will lower the overall memory requirements for a network that only allows shared trees.
    • The disadvantage of shared trees is that under certain circumstances the paths between the source and receivers might not be the optimal paths. This could lead to some latency in packet delivery.

PIM Modes

PIM Dense Mode (PIM-DM)

  • PIM-DM initially floods multicast traffic to all parts of the network.
  • The traffic is sent out of all non-RPF interfaces where there is another PIM-DM neighbor on a directly connected member of the group.
  • In figure 1 below:
    • multicast traffic is flooded throughout the entire network.
    • Traffic is received via each router’s RPF interface (interface in the direction of the source).
    • Multicast traffic is sent out each router’s non-RPF interface to all of its PIM-DM neighbors.
    • This flooding also results in some traffic arriving via the non-RPF interfaces as is the case for Routers A, B, C, and D.
    • Packets arriving via the non-PRF interfaces are discarded.

Figure 1: PIM-DM Initial Flooding

pim-dm1

  • In Figure 2 below:
    • PIM-DM prune messages (in red dotted arrows) are sent to stop unwanted traffic.
    • Prune messages are sent on an RPF interface only when the router has no downstream receivers for multicast traffic from the specific source.
    • In the example below, there is only one receiver, therefore all other paths are pruned.
    • Prune messages are also sent on non-RPF interfaces to shut off the flow of multicast traffic because it is arriving via an interface that is not on the shortest path to the source.

Figure 2: PIM-DM Pruning Unwanted Traffic

pim-dm2

  • The next illustration shows the result of pruning the unwanted multicast traffic:

Figure 3: PIM-DM Results After Pruning

pim-dm3

  • Although the flow of multicast traffic is no longer reaching most of the routers in the network, the (S, G) state still remains in all of them and will remain there until the source stops sending.
  • In PIM-DM, all prune messages expire in 3 minutes.
    • After that, the multicast traffic is flooded again to all the routers.

PIM-Sparse Mode (PIM-SM)

  • PIM-SM is described in RFC 2362, Protocol Independent Multicast-Sparse Mode (PIM-SM).
  • Uses shared distribution trees, but it may also switch to use source distribution trees.
  • Based on a pull model, traffic is forwarded only to those parts of the network that need it.
  • PIM-SM uses an RP to coordinate forwarding of multicast traffic from a source to receivers.
  • Senders register with the RP and send a single copy of multicast data through the RP to the registered receivers.
  • Group members are joined to the shared tree by their local designated router (DR).
  • A shared tree that is built this way is always rooted at the RP.
  • It is preferred over PIM-DM for all production networks regardless of size and membership density.

pim-sm

  • In the above diagram, an active receiver wants to join multicast group G.
  • The last hop router (router attached to the Receiver) knows the IP address of the RP router for group G.
    • It sends a (*, G) join for this group toward the RP.
    • The (*, G) join travels hop-by-hop toward the RP building a branch of the shared tree that extends from the RP to the last-hop router directly connected to the receiver.
    • At this point, group G traffic may flow down the shared tree to the receiver.

1 comment:

Anonymous said...

Genial dispatch and this enter helped me alot in my college assignement. Say thank you you as your information.