[Search] [txt|pdf|bibtex] [Tracker] [Email] [Nits]

Versions: 00                                                            
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