Kenji FUJIKAWA <email@example.com>
Katsuo IKEDA <firstname.lastname@example.org>
We propose resource reservation protocol (RSVP) integrated multicast (RIM), which is a protocol based on the resource reservation mechanism of RSVP, and on the multicast mechanism of protocol-independent multicast (PIM).
Multicast routing protocols such as PIM and CBT consume more routing entries proportional to multicast groups than unicasting does. Thus, since it is reasonable to charge a multicast user for the allocated entries, we first employed RSVP with PIM/CBT. However, this combination results in route flapping. Therefore, we use RSVP solely for multicasting, adding some modifications to it, and call this method RIM.
RIM creates both best-effort and quality-of-service multicast trees by itself without the route-flapping problem. In addition, it provides robustness for rendezvous point failures by employing multiple rendezvous points and supports multicasting with broadcast satellites.
Multicast technology in the Internet is shifting from Distance Vector Multicast Routing Protocol (DVMRP)[DVMR1988] to Protocol-Independent Multicast (PIM)[PIM1994] or Core-Based Tree (CBT)[CBT1993], which is based on a RendezVous Point (RVP) or a core. Either of those models consumes less routing table entries than DVMRP. However, PIM/CBT still consumes more entries in proportion to multicast groups than unicasting. Thus, one serious problem emerges: whether it is fair that users of multicasting are charged the same amount as users of unicasting.
We first employed resource ReSerVation Protocol (RSVP) [RSVP1997] with PIM or CBT to restrict the extra consumption of routing entries. RSVP was originally developed to reserve a resource such as bandwidth. Thus, RSVP was expected to restrict the consumption by means of handling a routing entry as one kind of resource.
However, another new severe problem arises when RSVP and PIM/CBT simultaneously work. A route created by PIM/CBT becomes unstable and inappropriate for RSVP under a Quality of Service (QoS) routing environment. This causes route flapping. Therefore, we have decided to use RSVP solely (i.e., to use RSVP for multicasting without PIM/CBT).
We propose RSVP Integrated Multicast (RIM), which is a multicast protocol integrated to RSVP. RIM handles a routing entry as one kind of resource such as bandwidth, and clarifies the cost for routing entries. RIM solves the problem of consuming multicast routing entries excessively, and also solves the route-flapping problem explained above. RIM achieves a QoS multicast routing, which must be one of the next generation Internet goals.
Other prominent features of RIM include the following: Receivers determine RVPs by Domain Name System (DNS). Introducing multiple RVPs, RIM reduces multicast routing entries, establishes efficient multicast trees with less redundant paths, and improves robustness to failures. RIM also supports multicasting with broadcast satellites.
A route-flapping problem occurs when RSVP and PIM/CBT are simultaneously used.
Figure I1 is an example. Receiver R1 is requesting RVP P1 to forward multicast data. Assuming that a best-effort path is P1-T1-T4-R1, then a bandwidth-satisfying path (QoS path) should be P1-T2-T3-T4-R1.
Figure I1: Route Flapping Caused by PIM Join Message and RSVP Resv Message
Router T4 sends a PIM Join message to T1, because it receives an Internet Group Management Protocol (IGMP) Join message from R1. T1 is the next hop for best-effort data to reach P1. T4 must forward an RSVP Resv message from R1 to T3 in order to satisfy the requested bandwidth. Thus, a best-effort path and a QoS path may differ in a QoS routing environment. This fact causes the instability of multicast routes. The path flaps every time a Join message or a Resv message is thrown.
A PIM Join message that is forwarded in a different direction from a Resv message should be ignored when a QoS path is demanded. In addition, it is useless, even when it is forwarded in the same direction, because a Resv message is enough to specify a QoS path.
Consequently, we have decided to use RSVP solely as a signaling protocol for QoS and multicast routing and call the signaling protocol an RSVP Integrated Multicast (RIM). RIM adopts the RSVP message formats and mechanisms, and is also based on the PIM multicast protocol (i.e., the RVP model). RIM determines a QoS path for each flow, considering a several QoS parameters such as bandwidth, delay, and charge.
RIM requires some QoS Link-State Advertisement Protocol (QoSLSAP) in order to be applied to an actual network.
QoSLSAP is a protocol that advertises link-states including QoS parameters, maintains a topology database of the whole network, and calculates the best paths by means of Dijkstra's algorithm. QOSPF [QOSPF] is an instance of applicable QoSLSAP. (However, RIM requires states just for each link, not for each flow. In this sense, QOSPF is overspecification, because it advertises information on flows as well as link-states.)
RIM assumes existence of a certain QoSLSAP in a network through the following discussion.
The original RSVP mechanisms are modified at the following points in RIM:
This section explains the basic procedure of creating a resource-reserved multicast tree using RIM.
The process of creating best-effort and QoS multicast trees is described in two parts: Sender-RVP and RVP-Receivers. Examples are shown later.
PQC is omitted in the explained procedure for the purpose of simplifying the procedure. The procedure of PQC is explained in the succeeding examples.
Each router admits a reservation, when it receives a Resv message, and after that, it receives a corresponding Path message.
Procedure Sender-RVP can almost be applied to procedure RVP-Receivers when the term "sender" is replaced by "RVP," and "RVP" by "receiver(s)." The other differences are as follows:
We make use of the notation as follows:
A network consists of one multicast sender S1, two receivers R1 and R2, one RVP P1 and six routers T1 to T6 in Figure B1. The bandwidth between each sender/receiver and an adjacent router is sufficient, and either the delay or charge is zero in the following discussion.
Figure B1: Initial Link-States
When sender S1 sends best-effort multicast data, which are IP-unicast-encapsulated, to RVP P1, P1 considers a QoS path and sends a Resv message with bandwidth of 1 and delay preference according to the QoS it knows (see Figure B2). Here, an RVP is statically configured by a multicast group manager, and is aware of the required QoS, that bandwidth is 2 and senders allowed to send data. The Resv message is forwarded along path T2-T1-S1, because link T1-P1 does not have enough bandwidth.
Figure B2: Multicast Data from S1 to P1 and Resv Message from P1 to S1
Multicast data and Path messages are forwarded along the reverse path of the Resv message (See Figure B3).
Figure B3: Multicast Data and Path Message from S1 to P1
Subsequently, receivers R1 and R2 have to join a multicast address first, so they search an RVP (i.e., P1 from the multicast address using DNS [explained in a later section]). Then, R1 and R2 request bandwidth of 1 with delay preference (see Figure B4).
Figure B4: Resv Messages from R1 and R2
Each router that received a Resv message calculates the shortest path tree (SPT) from an RVP to itself, and forwards the Resv message along the reverse path from the RVP to itself, which becomes a part of the tree. Links that do not satisfy requested bandwidth are pruned when calculating the SPT. In Figure B4, router T5 forwards a Resv message from R1 to T3.
Router T5 also merges Resv messages from R1 and from R2-T6 as the original RSVP does.
RVP P1, which has received a Resv message, sends a Path message and multicast data that are not encapsulated to T3, and each router forwards it along the reverse path along which the Resv message has come (see Figure B4).
Figure B5: Multicast Data and Path Message from P1
Figure B6 shows new link information after the reservation is established and the bandwidth is allocated.
Figure B6: New Link-States
Consequently, a sender can send multicast data to receivers via an RVP solely with the RSVP messages.
Next, we will describe a procedure of rerouting when a request is changed.
Receiver R2 changed the previous bandwidth request (1) into bandwidth of 2 in Figure C1. In this case, the Path message must indicate the maximum-allowable bandwidth of 2 or more. Router T5 has to change the direction to which it forwards a Resv message, from T3 into T4, since link T3-T5 does not have enough bandwidth.
Figure C1: Changed Request
The information on links announced by QoSLSAP shows that the bandwidth on each link as Figure B6. Thus, T5 will think that link P1-T3 is short of bandwidth as well as T3-T5, and that the request is not acceptable according to this information. The reservation will fail.
PQC is introduced in order to avoid this type of failure. A Path message progressively conveys the information about the bandwidth to be available at a link if the reservation did not exist (see Figure C2). T5 can get information that link P1-T3 is available, since a Path message with PQC restores the link-states as Figure C3. Thus, T5 forwards a Resv message to T4. Note that though T5 cannot get correct information about downstream links, this fact does not affect the decision of T5.
Figure C2: Path Message with PQC
Figure C3: Restored Link-States by PQC
T5 forwards a Resv message with PQC so that T4 can find the best path as T5 does and the Resv message is forwarded along path T5-T4-T3-P1 (see Figure C4).
Figure C5 shows the changed multicast tree that satisfies both requests of R1 and R2.
Figure C5: Changed Multicast Tree
Assuming that receiver R2 wants to receive data with charge preference, R2 changes a Resv message into one with charge preference (see Figure P1). Router T5 has to decide which request to give priority to. This decision is done by the policy of a Path message. A request type of a Path message polices request types of Resv messages. T5 decides to forward a Resv message with charge preference upstream, since it receives a Path message with request type charge in Figure P1. Router T5 forwards the Resv message to T4, because it calculates the shortest path P1-T3-T4-T5.
Figure P1: Changed Request with Charge Preference
As a result, the path becomes like one in Figure P2.
Figure P2: Multicast Tree with Charge Preference
One of QoS elements, charge is defined by three parameters:
The following expression shows the charge of a link for each CTU:
BC + PC * (Requested packet per second)
For example, assuming that CTU = 6 seconds, BC = 1 Japanese Yen (JPY), and PC = 0.001 JPY at a certain link. The charge for every 6 seconds is 1 JPY in the case of best-effort multicasting, and 1 + 0.001 * 1K = 2 JPY in the case of 1-Kpps QoS multicasting (1 Kpps corresponds to about 10 Mbps when the MTU size is 1,280 bytes).
Thus, an amount to be charged at each link is calculated. This calculation handles both best-effort multicasting and QoS multicasting. Charging for both types of multicasting prevents excess consumption of routing entries.
Next, we will explain how to sum up the total charge of a multicast tree, which consists of multiple links.
It is difficult for receivers to know the total charge of the tree, while it is straightforward for an RVP to know it. We add a new parameter charge (chg) to a Resv message, which indicates the total sum of charges at the links the Resv message comes through. A Resv message progressively collects a charged amount at each link by this parameter. The total charges of downstream sub-trees are added when Resv messages are merged.
The charge of each link is calculated from the above three parameters as shown in Figure Y1. The total sum of charges of Resv T6-T5 is calculated to 1, since the charge of the downstream link T6-R2 is 1. The sum indicated by Resv T5-T3 is calculated to 3 by summing the charges of link T5-R1, link T5-T6 and Resv T6-T5. Consequently, RVP P1 can know the total charge of 7.
Figure Y1: Summing up a Charge by Resv Messages
Charging for the manager of an RVP is the simplest way of collecting money. This method is similar to the current broadcasting systems such as radio and television, where a manager of such a system bears the cost of communication.
RIM adopts DNS as a mechanism of finding the address of an RVP. Receivers can obtain the address of an RVP the same as obtaining the address of a multicast address. For instance, if receivers are given the multicast address name "mcast.real-internet.org," then they will obtain the RVP address "184.108.40.206," as well as the multicast address "220.127.116.11."
This mechanism is further discussed in [STML1998].
RIM is able to use multiple RVPs for each multicast group.
An RVP is statically configured with the location information of the other RVPs. It acts as both multicast sender and receiver towards the others. That is, it sends multicast data received from senders to the others, and receives multicast data from the others by means of IP-unicast-encapsulation. It also forwards the multicast data received from the others to normal receivers. A host sends data to and receives from just one of the RVPs.
A multicast manager is responsible for the places of RVPs. Generally, the manager is expected to know about the tendencies of the multicast group, such as the location where senders and receivers gather. Therefore, the manager will not have any trouble deciding on the location of RVPs.
This mechanism cuts the total cost of trees. In addition, it improves robustness to the failure of RVPs. A host just re-selects another RVP if the RVP it uses fails.
RIM assigns one multicast address to one channel of satellite multicast, and also assigns a private RVP address to every broadcast satellite tuner in households.
For example, users get multicast address "18.104.22.168" and private RVP address "10.130.54.23" by looking up the name "bs.real-internet.org." Every tuner that can receive multicast data of a certain channel is assigned the private RVP address of a channel in advance. Terminals in a household receive the multicast data from the tuner by sending Resv messages to the tuner.
In the case that a user makes contract with a CATV company, the user gets the private RVP address towards the CATV company by DNS, and can receive the forwarded satellite multicast data from the CATV company.
Thus, the application of RIM to satellite multicast is easily achieved.
We proposed RSVP Integrated Multicast (RIM) as a QoS/multicast signaling protocol in the Internet. RIM is based on the reservation mechanism of RSVP and the shared-tree mechanism of PIM. It provides simple methods for multicasting, resource reservation, and charging by itself. It can also be applied to satellite multicast. The charging system in RIM restricts the excess number of reservations and retains scalability in the Internet as Plain Old Telephone System (POTS) does so.