Figure 1
Yukinori Goto <yuki@k-isit.or.jp>
Kyushu University
Japan
Masataka Ohta <mohta@necom830.cc.titech.ac.jp>
Tokyo Institute of Technology
Japan
Keijiro Araki <araki@dontaku.csce.kyushu-u.ac.jp>
Kyushu University
Japan
Path QoS collection is a fully distributed soft-state mechanism for quality of service (QoS) routing to accumulate QoS information on links within a field of Path_msg of RSVP (Resource Reservation Protocol). Using link state information distributed with some QoS routing protocol along with Path QoS Collection, receivers and intermediate routers can choose the best route with the required QoS, hop-by-hop, in a distributed and scaleable manner for unicast and multicast communications over the Internet.
Keywords: path QoS collection, QoS routing, RSVP, resource reservation, QoSLSAP, IP multicast.
To use real-time interactive multimedia communications such as voice and videoconferencing over the Internet, quality of service (QoS) must be assured. RSVP [1, 2], a protocol for QoS assurance, is discussed in IETF (Internet Engineering Task Forces). However, RSVP today relies on a best-effort routing protocol and may not find a path with required QoS.
We discuss a QoS routing protocol and a QoS route determination method that finds the best path to satisfy the required QoS using RSVP. We also propose Path QoS collection for stable hop-by-hop QoS routing.
Figure 1 illustrates a network and its link states. When the sender S communicates with receiver R0, the shortest best-effort protocols don't consider QoS and select the path S-C-B-A-R0. If the receiver R0 requires 9 megabits per second (Mbps) of bandwidth and the shortest path with RSVP, the path S-C-B-A-R0 would again be used. However, if R0 requires 15 Mbps of bandwidth and the shortest path, then a different path must be used. In this case, the path S-F-E-D-A-R0 should be selected to satisfy the requirement. This process is called QoS route determination [3, 4, 5].
Figure 1
In this paper, we use the following terminologies.
RSVP is a protocol that installs a QoS requirement on routers to reserve network resources for a flow from sender to receivers. Its features are as follows:
The important feature of RSVP is that it is receiver oriented. This means that a receiver can specify certain network resources as the QoS required for the flow, and a sender can accommodate requests from a large number of receivers. RSVP maintains a soft state in order to support dynamic changes of membership and QoS and to adapt a route automatically.
RSVP provides three reservation styles to support various models:
RSVP has two messages to negotiate resource reservation for each link between a sender and a receiver. One is a path message (Path_msg), and the other is a reservation message (Resv_msg).
The reservation steps are as follows:
These messages are sent along the route decided by the route determination process because RSVP does not support such a function. Therefore, the path may not satisfy the desired QoS.
The routers in the network must know each link's QoS state to decide the QoS route; therefore, QoS routing protocol should adopt QoSLSAP. The QoS link state is the set of link resources available for each router. QoS link states are advertised to all routers by QoSLSAP. The route for the desired QoS is decided by route determination, which uses the link states indicated by the QoS routing protocol. Then a problem occurs.
For example, in Figure 1, when receiver R0 requires 9 Mbps and the shortest path to sender S, the path S-C-B-A-R0 is computed by QoSLSAP and Dijkstra's algorithm and network resources are reserved along the route. Then link states of Figure 1 change to those of Figure 2. Based on the new link states, each router computes a new route. The path S-F-E-D-A-R0 is selected, and link states change from Figure 2 to Figure 3. Then each router computes a route again, the path S-C-B-A-R0 is selected, and link states change from Figure 3 to Figure 2. This rerouting is repeated forever. Therefore, an important goal of QoS routing is to make decisions stable and unaffected by their own resource consumption. Route pinning, discussed below, is proposed for this solution.
Figure 2
Figure 3
QOSPF [4] is a proposed QoS routing protocol that extends OSPF and MOSPF to notify QoS link states to all routers. QOSPF is based on two messages, the RES-LSA (Link Resource Advertisement message) [4] and the RRA (Resource Reservation Advertisement message) [4].
The purpose of the RES-LSA message is to advertise QoS link states in the network. These states are used to compute the route. When a new router is added on the network, or when network resource consumption or link state changes, the new QoS link states are advertised by RES-LSAs.
The purpose of the RRA is to indicate the resources used by a flow. By RRA, each router is notified about resources and paths used by the flow. QOSPF computes the route for each flow by Dijkstra's algorithm. The number of RRAs can easily become large as the number or length of reserved flows increase, which presents a scaling issue. One solution is explicit routing [4], which computes the route for the desired QoS in advance and sends it to other routers; that is, QOSPF uses source routing to indicate the route. QOSPF uses route pinning [4] to make the route stable. Route pinning means that an existing route with a reservation will not be replaced by a better route unless the first route is no longer usable. However, both source routing and route pinning cause problems for QOSPF.
The first problem is RRA. RRA advertises resources that are reserved by the flow to every router. When RRA is used in a large network and there are a number of flows, flooding RRAs in the network causes heavy network load.
The second problem is that QOSPF adopts route pinning to make a route sticky. When a new route, better than the existing route for the flow, is found by change of link states the flow cannot use the new route because route pinning fixes the existing route.
Let's assume that a receiver decides the route using source routing. Then the receiver can reserve resources it requires for itself. When R0 communicates with S using IP multicast and requesting 9 Mbps for QoS, the path S-C-B-A-R0 is selected by QOSPF as shown in Figure 2. If R1 joins this multicast group requesting 15 Mbps, R1 would select the path S-F-E-D-A-B-R1 for the desired QoS according to the link states of Figure 2. When the path S-F-E-D-A-B-R1 is selected, Resv_msg of R0 and Resv_msg of R1 should be merged on router A and router B. However, routers A and B cannot merge Resv_msg of R0 and Resv_msg of R0 because the path S-C-B-A-R0 is pinned, as shown in Figure 4. If router A or router B merge these Resv_msgs forcibly, the path S-F-E-D-A-R0 would be selected for the multicast group. However, it isn't consistent with R0's idea of its path (S-C-B-A-R)0, which may cause instability. Therefore, route pinning isn't effective for IP multicast.
Figure 4
We propose the path QoS collection method (PQC) to solve these problems.
PQC is a mechanism to let Path_msg collect information about resources used by the flow. Using this information, each router updates generic QoS link states flooded by some QoSLSAP for each flow and performs Dijkstra's algorithm to select the route for the desired QoS. There is no feedback loop and route determination is stable because QoS link states are corrected by PQC to remove the effect of the flow's own traffic.
PQC works as follows.
For example, when receiver R0 requires 9 Mbps and the shortest path in Figure 5 to join a multicast group g with a sender of S, the path S-C-B-A-R0 is selected by QoSLSAP and Dijkstra's algorithm, the link states of the network change to those shown in Figure 6.
Figure 5
Figure 6
The information collected by Path_msg for each link along the path S-C-B-A-R0 is as follows:
Figure 7
The link states of the path S-C-B-A-R0 are corrected from Figure 6 to Figure 5 by using this information. When each router computes the route for the flow, each router uses the modified link state.
Next, in Figure 6, receiver R1 joins the multicast group g and requires 15 Mbps and the shortest path. Each router finds the path S-F-E-D-A-B-R1 for the flow on Figure 5, which is corrected from the link states of Figure 6. R1 sends a Resv_msg. The Resv_msgs are merged at router B and then on router A. Router A selects the path S-F-E-D-A for the flow of g and releases the existing path S-C-B-A because PQC adopts hop-by-hop routing, as shown in Figure 8.
Figure 8
Then information is collected by Path_msg for each link as follows:
Figure 9
When R0 starts resource reservation, if Path_msg arrives at R0 before the QoSLSAP message the link state of A-R0 would be corrected from 30 to 39 (= 30 + 9), which is a mistake. To solve this problem, Path_msg and the QoSLSAP message need to have time stamps.
When RSVP is used with PQC, the reverse path method using Path_msg isn't necessary because downstream routers and receivers decide the route with QoSLSAP, Dijkstra's algorithm, and PQC.
We consider the quantity of information that indicates the resources used by a flow. For QOSPF, the quantity of information is (h - 1) * l where h is the number of hosts in the network and l is the number of links reserved by the flow. Quantity of the information for PQC is l * (l + 1)/2. Therefore, the quantity of information for PQC is less than the quantity of information for QOSPF because l < h.
Our proposed QoS routing protocol also solves the "killer reservation problem." A killer reservation problem occurs when too many network resources are requested by a malicious or badly behaving receiver and other receivers whose requests are merged with the killer reservation can't make reservations. When the too-large request is made, PQC-based routing simply denies the request without merging it with other moderate requests, because even the downstream routers know if the network has enough resources to warrant the request.
PQC enables us to reserve network resources with hierarchical routing beyond areas defined by OSPF. When a sender is out of the receiver's local area, the receiver can know the link resources available for flows by Summary LSAs [4, 6] extended to advertise link resources. Information about resources used by the flow on each out-of-area link is summarized by an area-border router and collected by PQC. The summary information collected by PQC is used to correct the general link state advertised by QoSLSAP and make the route stable.
First, we will consider MOSPF as a multicast routing protocol [7, 8]. MOSPF is an IP multicast routing protocol extended from OSPF for IP multicast. For each pair of sources or groups, MOSPF makes the shortest path tree whose vertex is a source host. In Figure 10, source host S makes the shortest path tree, which is represented by a solid line using MOSPF, and receiver R0 and R2 don't require QoS. If R1 doesn't require QoS, the shortest path tree would be the solid line in Figure 10. When R1 requires QoS for this multicast flow, if the path S1-A-C-E-R1 is computed by QoSLSAP and Dijkstra's algorithm for the desired QoS, then router E would forward Resv_msg to router C. However, even if router C reserves resources to warrant QoS on link C-E, the datagram of this group won't be forwarded over the link C-E if router E doesn't forward an IGMP message to router C. Router E should forward an IGMP message to router C to stream the datagram on the link C-E. Therefore, when a receiver requires QoS for multicast flow, upstream routers must forward the IGMP message in the same direction they forwarded Resv_msg, and the link used by the multicast group is shut down, as shown in Figure 11.
Figure 10
Figure 11
Next, assume that a sender S2 joins this multicast group in Figure 11, as shown in Figure 12. S2 has the shortest path for the multicast group to R1 through C.
Figure 12
When R1 requires QoS for both S1's flow and a S2's flow with FF (fixed-filter style), each flow's network resource is reserved separately. Receiver R1 sends Resv_msg to upstream next hop and it arrives at each sender along the route computed by QoSLSAP and Dijkstra's algorithm. Path_msg for each sender sends to downstream next hop.
When the multicast route between S1 and R1 is already established with an SE (shared-explicit style) filter in Figure 12, and R1 requires QoS for the flow of sender S2 used by SE, R1 computes the route using QoSLSAP and Dijkstra's algorithm. Then R1 uses link states corrected by information collected by Path_msg, but for link C-E, the link states are corrected by only one Path_msg because resources reserved for flow of S1 are also used by the flow of S2 to SE. When using WF (wildcard filter style), a similar thing is done.
Lastly, we must discuss the use of PIM (Protocol Independent Multicast) [8] with PQC. PIM has rendezvous points (RP) [8]. The datagrams are forwarded to receivers via the RP and adopt the core-based tree (CBT) [8]. Therefore, a receiver requiring QoS sends a Resv_msg to the RP along the route computed by QoSLSAP and Dijkstra's algorithm. When an RP receives Resv_msgs, RP computes the route to a sender. Path_msgs sent by senders collect information on resources, which are reserved by flow with PQC and forwarded to each receiver via RP.
This paper proposes path QoS collection for stable hop-by-hop QoS routing. PQC collects information on resources reserved by a flow. Flooded generic QoS link states are corrected with the information collected by PQC in order to remove the effect of the flow's own traffic upstream. Consequently no feedback loop is formed and route determination is sticky. PQC adopts hierarchical routing. When senders and receivers are located in different areas of ASes (autonomous systems), PQC can collect the aggregated summary information of resources reserved by the flow, and aggregated or summary QoS link states between areas or ASes are corrected by PQC. PQC is adaptable to various IP multicasts and solves the killer reservation problem.