INTERNET DRAFT J.M.Pullen
Expiration: 25 April 1997 George Mason U.
Lava K. Lavu
George Mason U.
Hai Nguyen
ESystems Falls Church
Eric Crawley
Baynetworks
25 November 1996
A Simulation of QOSFP Multicasting for a Large Area
<draft-pullen-qospf-model-00.txt>
Status of this Memo
This document is an Internet-Draft. Internet-Drafts are working
documents of the Internet Engineering Task Force (IETF), its
areas, and its working groups. Note that other groups may also
distribute working documents as Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six
months and may be updated, replaced, or obsoleted by other
documents at any time. It is inappropriate to use Internet-
Drafts as reference material or to cite them other than as
``work in progress''
To learn the current status of any Internet-Draft, please check
the ``1id-abstracts.txt'' listing contained in the Internet-
Drafts Shadow Directories on ftp.is.co.za (Africa), nic.nordu.net
(Europe), munnari.oz.au (Pacific Rim), ds.internic.net (US East
Coast), or ftp.isi.edu (US West Coast).
Abstract
This document describes a detailed simulation model of a sizable
IPmc/RSVP network using the Quality of Service Extensions to OSPF
and the performance predictions produced by the model. The model
was developed using the OPNET simulation package with procedures
defined in the C language. The model was developed to allow
investigation of scaling characteristics of QoS routing by the
Internet multicast/resource reservation community. We are making
our model publicly available for this purpose.
1. Background
The purpose of this document is to describe a simulation model
designed to help in understanding the scaling characteristics
of the QOSPF protocol in networks of significant size.
The successful deployment of IP multicasting [1] and its
availability in the Mbone has led to continuing increase in real-
time multimedia Internet applications. Because the Internet has
traditionally supported only a best-effort quality of service,
there is considerable interest to create mechanisms that will
allow adequate resources to be reserve in networks using the
Internet protocol suite, such that the quality of real-time
traffic such as video and voice can be sustained at specified
levels. The RSVP protocol [2] has been developed for this
purpose and is the subject of considerable ongoing implementation
efforts.
RSVP is does not provide routing, but relies on routing protocols
to be available in its working environment. One school of
thought argues that, to be effective, this routing must be aware
of quality of service (QOS) capabilities of network components
through which the RSVP paths and reservations are to be routed.
A proposal has been put forward for QOS-sensitive routing (QOSPF)
based on the well-known OSPF routing protocol [4] and its
multicast derivative, MOSPF [5]. However, serious questions have
been raised about the scalability of such a protocol. The
simulation described in this document is intended to provide a
tool to examine the behavior of a sizable QOSPF-routed network
with Ipmc and RSVP, handling large numbers of resource-reserved,
real-time multicast applications. A companion paper describes
the simulation models for IPmc and RSVP that support the QOSPF
simulation. Each of these models is available for use of the
IETF comunity.
2. The OPNET Simulation Environment
The Optimized Network Engineering Tools (OPNET) is a commercial
simulation product of the MIL3 Company, Arlington, VA. It
employs a Discrete Event Simulation approach that allows large
numbers of closely-spaced events in a sizable network to be
represented accurately and efficiently. OPNET uses a modeling
approach where networks are built of components interconnected by
perfect links (which can be degraded at will). Each component's
behavior is modeled as a state-transition diagram. The process
that takes place in each state is described by a program in the C
language. We believe this makes the OPNET-based models
relatively easy to port to other modeling environments. Perhaps
more importantly, given the widespread availability of OPNET,
it makes them sufficiently efficient that an extended period of
network behavior can be simulated in considerable detail, even for
large networks.
The following sections describe the state-transition models and
process code for the QOSPF model we have created using OPNET.
3. QOSPF Model
The state-transition diagrams for the QOSPF model can be found at
http://bacon.gmu.edu/qosip/qospf/rtr-states.html.
The following processing takes place in the indicated modules.
3.1 init
This state initializes all the router variables. Default
transition to idle state.
3.2 idle
This state has several transitions. If a packet arrives it
transits to arr state. Depending on interrupts received it will
transit to BCOspfLsa, BCQospfLsa, BCMospfLsa, hello_pks state.
In future versions, links coming up or down will also cause a
transition.
3.3 BCOspfLsa
Transition to this state from idle state is executed whenever the
condition send_ospf_lsa is true, which happens when the network is
being initialized, and when ospf_lsa_refresh_timout occurs. This
state will create Router, Network, Summary Link State
Advertisements and pack all of them into an Link State Update
packet. The Link State Update Packet is sent to the IP layer with a
destination address of AllSPFRouters.
3.4 BCQospfLsa
Transition to this state from the idle state is executed whenever
the condition send_qospf_lsa is true. This state will create Link
Resource Advertisement and Resource Reservation Advertisement and
pack them into a Qospf Link State Update Packet. This Qospf Link
State Update Packet is sent to IP layer with a destination
address of AllSPFRouters.
3.5 BCMospfLsa
Transition to this state from idle state is executed whenever the
condition send_mospf_lsa is true. This state will create Group
Membership Link State Advertisement and pack them into Mospf Link
State Update Packet. This Mospf Link State Update Packet is sent
to IP layer with a destination address of AllSPFRouters.
3.6 arr
The arr state checks the type of packet that is received upon a
packet arrival. It calls the following functions depending on the
protocol Id of the packet received.
a. QospfPkPro: Depending on the type of QOSPF/OSPF/MOSPF packet
received the function calls the following functions.
1. HelloPk_pro: This function is called whenever a hello packet is
received. This function updates the router's neighbor information,
which is later used while sending the different LSAs.
2. OspfLsUpdatePk_pro: This function is called when a OSPF LSA update
packet is received (router LSA, network LSA, or summary LSA). If
the Router is an Area Border Router or if the LSA belongs to the
Area whose Area Id is the Routers Area Id, then it is searched to
determine whether this LSA already exists in the Link State
database. If it exists and if the existing LSA's LS Sequence
Number is less than the received LSA's LS Sequence Number the
existing LSA was replaced with the received one. The function
processes the Network LSA only if it is a designated router or
Area Border Router. It processes the Summary LSA only if the
router is a Area Border Router. The function also turns on the
trigger ospfspfcalc which is the condition for the transition from
arr state to ospfspfcalc.
3. MospfLsUpdatePk_pro: This function is called when a MOSPF LSA
update packet is received. It updates the group membership link
state database of the router. The function also turns on the
trigger mospfspfcalc which is the condition for the transition
from arr state to mospfspfcalc. In future versions, network
topology changes will also trigger this state.
4. QospfLsUpdatePk_pro: This function is called when a QOSPF LSA
update packet is received. It updates the resource link state
database of the router. It turns on the trigger qospfcalc which is
used as a transition condition from arr state to qospfspfcalc
state.
b. RsvpPkPro: This function is invoked whenever a packet is received
by the arr state from the RSVP daemon. RSVP will send a packet to
QOSPF daemon whenever the RSVP daemon receives an initial path
message, or a reservation for a source is successful. This function
calls one of the following two functions depending on the type of
packet received by the QOSPF arr state.
1. Path_Msg_pro: This function gets the source and destination
information, sender transmission specs and sets the trigger
qospfcalc on.
2. Resv_Msg_Pro: This function gets the resources reserved
information from the TCSB of the RSVP daemon and makes the trigger
send_rralsa true, which will in turn turn on the send_qospf_lsa
trigger on. send_qospf_lsa is used to send the send the Qospf LSA
update packets, thereby sending the Resource Reservation
Advertisement with the new information.
3. IgmpPkPro: This function will make the trigger send_grpmbrlsa true
which in turn activates the send_mospf_lsa trigger. send_mospf_lsa
is used to send the MOSPF LSA update packets. This is a trigger
from IGMP so that QOSPF examines all new group joins.
3.7 qospfspfcalc
This function is used to calculate the QOSPF routing table.
Resource LSA's are used to discover the neighbors and RRA's are
used to check for the available resources on the link. This state
transit to upstr_node on detupstrnode condition. Only topology
changes (indicated by router LSA, network LSA, resource LSA)) will
trigger recalculation of all flows, other changes (summary LSA,
group change, amd RRA/DABRA) only cause recalculation of affected
entries.
a. QospfCandidateAddPro: Each vertex's neighbors are checked for
inclusion into the candidate list by examining the Resource-LSA. If
the existing reservation for the flow (for this source destination
pair) or the available bandwidth on this link meets the QOS
requirements of the flow then the other end of the link is considered
for inclusion in the candidate list. The delay from the source to
this vertex(the other end of the link) is calculated and if this
vertex is not on the candidate list it is added to the candidate
list. Route pinning is used. When adding the vertex if the
parent of vertex has a reservation for the flow it is marked
reserved.
b. QospfSPFTreeCalc: While the candidate list is not empty the
candidate that is closest to the root is deleted and added to the
shortest path tree, and the Resource-LSA of this candidate is used to
check for possible inclusion of the other end of the links into the
candidate list. A vertex marked reserved is chosen first in
building the Shortest Path Tree.
c. QospfRouteTableCalc: Using the shortest path tree information
obtained from the shortest path tree database route table is
calculated. The IP layer uses this information to route the QOS
flows.
3.8 hello_pks
Hello packets are created and sent with destination address of
AllSPFRouters. Default transition to idle state.
3.9 mospfspfcalc
The following functions are used to calculate the shortest path
tree and routing table. This state transit to upstr_node upon
detupstrnode condition.
a. CandListInit: Depending upon the SourceNet of the datagram the
candidate lists are initialized.A
b. MospfCandAddPro: The vertex link is examined and if the other end
of the link is not a stub networks and is not already in the
candidate list it is added to the candidate list after calculating
the cost to that vertex. If this other end of the link is already on
the shortest path tree and the calculated cost is less than the one
that shows in the shortest path tree entry update the shortest path
tree to show the calculated cost.
c. MospfSPFTreeCalc: The vertex that is closest to the root that is
in the candidate list is added to the shortest path tree and its link
is considered for possible inclusions in the candidate list.
d. MCRoutetableCalc: Multicast routing table is calculated using the
information of the MOSPF shortest Path tree.
3.10 ospfspfcalc
The following functions are used in this state to calculate the
shortest path tree and using this information the routing table.
Transition to qospfspfcalc state on qospfcalc condition. This was
set to one after processing all functions in the state.
a. OspfCandidateAddPro: This function initializes the candidate list
by examining the link state advertisement of the the Router. For each
link in this advertisement, if the other end of the link is a router
or transit network and if it is not already in the shortest-path
tree then calculate the distance between these vertices. If the
other end of this link is not already on the candidate list or if
the distance calculated is less than the value that appears for
this other end add the other end of the link to candidate list.
b. OspfSPTreeBuild: This function pulls each vertex from the
candidate list that is closest to the root and adds it to the
shortest path tree. In doing so it deletes the vertex from the
candidate list. This function continues to do this till the candidate
list is empty.
c. OspfStubLinkPro: In this procedure the stub networks are added to
shortest path tree.
d. OspfSummaryLinkPro: If the router is an Area Border Router the
summary links that it has received is examined. The route to the Area
border router advertising this summary LSA is examined in the routing
table. If one is found a routing table update is done by adding the
route to the network specified in the summary LSA and the cost to
this route is sum of the cost to area border router advertising this
and the cost to reach this network from that area border router.
e. RoutingTableCalc: This function updates the routing table by
examining the shortest path tree data structure.
3.11 upstr_node
This state does not do anything in the present model. It transitions
to DABRA state.
3.12 DABRA
If the router is an Area Border Router and the area is the source
area then a DABRA message is constructed and send to all the
downstream areas. Default transition to idle state.
4. Performance Predictions
The purpose for generating the model was to use it to predict
performance of a large IPmc-RSVP systems using QOSPF routing.
We describe results of the simulation below.
4.1 small-scale test network and model calibration
A 5-router test Network has been created in a lab environment to
study the behavior of the Quality-of-Service Open Shortest Path First
(QOSPF) routing protocol. The test network is made up of Bay
Networks Backbone Link Node-2 (BLN-2) routers, Silicon Graphics Inc.
(SGI) workstations, and Audio Host Processors. Routers are
interconnected via Crossover cables that perform as T1 links.
Workstations and Hosts are nodes on Fiber Distributed Data Interface
(FDDI) Local Area Networks (LANs). A diagram of the test network is
shown in:
http://bacon.gmu.edu/qosip/qospf/ss-cal-net.html
4.1.1 Hardware and Software Configuration
a. Backbone Link Node-2 Routers: The routers are running BayNetworks
Image 11.0 Release with the addition of QOSPF, IGMP v2.0, and a
subset of RSVP based on Internet Draft (ID) 8.0. For RSVP, fixed
filter reservation style using raw RSVP I/O is supported. The ADspec
object is not supported. Router alert IP option is used. Integrated
services Controlled-Load is supported (as specified in the draft-
ietf-intserv-ctrl-load-svc-03.txt). In addition, a protocol
prioritization mechanism is used to control the queuing delay and
dropping of QOSPF and RSVP messages.
b. Silicon Graphics Inc. Workstations: These are Indy Workstations
with Sysconnect FDDI card (12501) running IRIX v5.1 operating system.
Custom UDP Test traffic generator (both Unicast and Multicast) is
included.
c. Audio Host Processors: These are E-Systems proprietary 6U VMEbus
boxes consisting of Motorola 68040 processor (MVME167-033B), Cyclone
i960 processors (CVM964), and Rockwell FDDI interface card (125010).
Each Host has an internal Ethernet network for processor to processor
communication. The units are running ISI pSOS+ v1.3 real time
operating system. Audio applications use Xpress Transfer Protocol
(XTP) v4.0 as its Transport layer. IGMP v2.0, RIP v1.0 and a subset
of RSVP based on ID 8.0 are also supported.
4.1.2 Test Network Description
The BLN-2 Routers are connected via serial synchronous links acting
as T1 links. Each link has a line bandwidth of 1.25 Mbits/sec.
This is the clock speed closest to the 1.544 Mbits/sec T1 rate that
the routers can source. For each link, the Reservable bandwidth is
set at 1.075 Mbits/sec, and the Best Effort (BE) bandwidth is set at
175 Kbits/sec.
a. Reserved Flows Characteristics: Audio flows are provided with a
Controlled-Load service. The RSVP Tspec has a burst of 5,120 bytes
(10 datagrams) and a rate of 77 Kbytes/sec. Audio data packet size
is 512 bytes. IP datagram packet size is 584 bytes (includes data,
XTP header, IP header and a second encapsulating IP header). Based
on the configured reservable bandwidth of 1.075 Mbits/sec, a maximum
of 13 audio flows can be allocated per link. This does include a 7%
inflation factor.
b. BE Traffic Characteristics: Data packet size is 500 bytes. UDP
IP datagram size is 528 bytes.
4.1.3 Test Scenarios
4.1.3.1 Test Case 1 - Reserved Flows with BE Traffic
a. Test Scenario: Host1 is the source for Audio multicast group
#1-13. Host2 is the source for Audio multicast group #14-26. Host3
joins and starts receiving Audio multicast group #1-26. There are 90
Kbits/sec of BE UDP traffic from Workstation2 to Workstation3.
b. Observation: All Reserved flows and BE traffic from R2-R5-R3 are
contained within a single link. Similarly, only one link is utilized
from R1-R4-R3. Host3 receives all datagrams from Audio multicast
group #1-26. Workstation3 receives 90 Kbit/sec of UDP traffic from
Workstation2 via R2-R5-R3. No packets are clipped, since the link
bandwidth is greater than that consumed by both the Reserved flows
and BE traffic.
4.1.3.2 Test Case 2 - Reserved Flows with BE Traffic and Links break
a. Test Scenario: Same as Test Case 1. Both Reserved flows and BE
traffic are flowing from R1-R4-R3 and R2-R5-R3. The Links connecting
R2 and R5 are disconnected.
b. Observation: Host3 is receiving all Reserved flows from Host1 via
R1-R4-R3, and Host2 via R2-R5-R3. Workstation3 is receiving all BE
UDP traffic from Workstation 2 via R2-R5-R3. After the links between
R2 and R5 are removed, the Reserved flows from Host2 and BE traffic
from Workstation2 are re-routed to OSPF area 3 via R2-R1-R4-R3. The
rerouted traffic, originating from OSPF area2, now utilizes the
second link between R1&R4 and R4&R3.
4.1.3.3 Test Case 3 - Reserved Flows with Heavy BE Traffic
a. Test Scenario: Same as Test Case 1, except that the BE UDP
traffic from Workstation2 to Workstation3 is increased from 90
Kbits/sec to 902.4 Kbits/sec, causing link overload. Note that on
this scenario the BE traffic are exceeding the BE available
bandwidth.
b. Observation: Host3 is receiving all of the Reserved flows from
Host1 via R1-R4-R3, and Host2 via R2-R5-R3. Workstation3 is
receiving in the average 257.15 Kbits/sec of BE UDP traffic from
Workstation 2 via R2-R5-R3. In the average 71.6 packets/sec of BE UDP
packets are clipped at R2 since the available BE bandwidth is much
less than the actual BE traffic. The Reserved flows are not effected
by the heavy BE traffic on the same links.
4.1.4 Calibration
Calibration of the small-scale network simulation against the
behavior or the physical model is ongoing.
4.2 Behavior of the scaled-up QOSPF network
The major purpose for this simulation effort was to examine in
detail the projected performance of a large QOSPF-based autonomous
system. Accordingly we have generated a system of 84 routers
that we believe is representative of the sort of environment where
QOSPF would be used.
4.2.1 Nature of the scaled-up network
The scaled-up network can be seen at:
http://bacon.gmu.edu/qosip/network_model/future_model
The network consist of four areas, each constructed from four
copies of the small-scale network. The areas are cross-linked
such that each small-scale network is connected to two area
routers. Further, the area routers are connected to backbone
routers and cross-linked for redundancy. The intention is to
represent a corporate network with high performance and reliability
requirements, where each of the small-scale networks might
represent a department and each area router a geographic area.
4.2.2 Simulation results from the scaled-up network.
We are still early in the process of understanding just what is
happening inside our complex target environment. In particular we
have been grappling with a series of problems associated with
scaling up the protocols, which appear to be working in the
small-scale network. We are running session generators at moderate
levels (at most one new session per router per second) and working
to verify the validity of the simulation results. Thus far we
have found the target environment is fully able to break any naive
simulation we try, either by demanding amounts of memory beyond
the virtual memory space of Unix, or by running so slowly that
hundreds of hours of wall-clock time would be required to represent
one hour of simulated time. We are making good progress and expect
to have validated simulation statistics within a month. Meanwhile we
are releasing this interim report to the Internet community with the
expectation that this will result in a thorough review and
theoretical validation, or indication where further work is needed,
for the model elements described here.
5. Future Work
We expect to perform further simulations of the QOSPF protocol
to allow it to be defined in such as way as to be most effective.
We welcome participation in this process by the Internet
community.
6. References
[1] Deering, "Host Requirements for IP Multicasting", RFC 1112,
August 1989
[2] Braden et. al., "Resource Reservation Protocol Version 1
Functional Specification", work in progress (draft-ietf-rsvp-
spec-14), November 1996
[3] Zhang et. al., "Quality of Service Extensions to OSPF or
Quality of Service First Path Routing (QOSPF)", work in progress
(draft-zhang-qos-qospf-00.txt), June 1996
[4] Moy, "OSPF Specification", RFC 1131, October 1989
[5] Moy, "MOSPF: Analysis and Experience", RFC 1585, March 1994
[6] MIL3 Inc., OPNET: Optimized Network Engineering Tools,
Simulation Kernel Manual, November 1991
Authors' Addresses
J. Mark Pullen
Computer Science/4A5
George Mason University
Fairfax, VA 22032
mpullen@gmu.edu
Lava K. Lavu
C3I Center/4B5
George Mason University
Fairfax, VA 22030
llavu@bacon.gmu.edu
Hai H. Nguyen
Raytheon E-Systems, Falls Church Division
7700 Arlington Blvd, N201
Falls Church, VA 22046
hai_nguyen@fallschurch.esys.com
Eric Crawley
BayNetworks Milstop 3FS-1302
3 Federal St.
Billerica, MA 01821
esc@baynetworks.com
Expiration: 25 April 1997