the IP module.
5.4 Modifications of modules in the process model
Modifications of routing protocol modules (in fact all of the modules
in the process model) are made transparently throughout the network
using the OPNET Simulation tools. An addition or modification of a
routing module in any subnet will reflect on all the subnets.
6. OSPF and MOSPF Models
OSPF and MOSPF models [5] are implemented in the OSPF model
containing fourteen states. They only exist on routers. Figure 10
shows the process model. The following processing takes place in the
indicated modules.
6.1 init
This state initializes all the router variables. Default transition
to idle state.
6.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, BCMospfLsa, hello_pks state. In future versions, links
coming up or down will also cause a transition.
6.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.
[Figure 10: OSPF and MOSPF process model on routers]
6.4 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.
6.5 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. OspfPkPro: Depending on the type of 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 an 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.
6.6 hello_pks
Hello packets are created and sent with destination address of
AllSPFRouters. Default transition to idle state.
6.7 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.
b. MospfCandAddPro: The vertex link is examined and if the other end
of the link is not a stub network 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.
6.8 ospfspfcalc
The following functions are used in this state to calculate the
shortest path tree and using this information the routing table.
Transition to ospfspfcalc state on ospfcalc condition. This is 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 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 until 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.
6.9 upstr_node
This state does not do anything in the present model. It transitions
to DABRA state.
6.10 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.
7. DVMRP Model
The DVMRP model is implemented based on reference [6], DVMRP version
3. There are nine states. The DVMRP process only exists on Routers.
Figure 11 shows the states of the DVMRP process.
7.1 Init
Initialize all variables, routing table and forwarding table and load
the simulation parameters. It will transit to the Idle state after
completing all the initializations.
7.2 Idle
The simulation waits for the next scheduled event or remotely invoked
event in the Idle State and transit to the state accordingly. In the
DVMRP model, Idle State has transitions to Probe_Send, Report_Send,
Prune_Send, Graft_Send, Arr_Pkt, Route_Calc and Timer states.
[Figure 11. DVMRP process on routers]
7.3 Probe_Send State
A DVMRP router sends Probe messages periodically to inform other
DVMRP routers that it is operational. A DVMRP router lists all its
known neighbors' addresses in the Probe message and sends it to All-
DVMRP-Routers address. The routers will not process any message that
comes from an unknown neighbor.
7.4 Report_Send
To avoid sending Report at the same time for all DVMRP routers, the
interval between two Report messages is uniformly distributed with
average 60 seconds. The router lists source router's address,
upstream router's address and metric of all sources into the Report
message and sends it to All-DVMRP-Routers address.
7.5 Prune_Send
The transition to this state is triggered by the local IGMP process.
When a host on the subnetwork drops from a group, the IGMP process
asks DVMRP to see if the branch should be pruned.
The router obtains the group number from IGMP and checks the IP
Multicast membership table to find out if there is any group member
that is still in the group. If the router determines that the last
host has resigned, it goes through the entire forwarding table to
locate all sources for that group. The router sends Prune message,
containing source address, group address and prune lifetime,
separately for each (source, group) pair and records the row as
pruned in the forwarding table.
7.6 Graft_Send
The transition to this state is triggered by the local IGMP process.
Once a multicast delivery has been pruned, Graft messages are
necessary when a host in the local subnetwork joins into the group. A
Graft message sent to the upstream router should be acknowledged hop
by hop to the root of the tree guaranteeing end-to-end delivery.
The router obtains the group number from IGMP and go through the
forwarding table to locate all traffic sources for that group. A
Graft message will be sent to the upstream router with the source
address and group address for each (source, group) pair. The router
also setups a timer for each Graft message waiting for an
acknowledgement.
7.7 Arr_Pkt
All DVMRP control messages will be sent up to DVMRP layer by IP. The
function performed by the DVMRP layer depends upon the type of the
message received.
a. Probe message: The router checks the neighbors' list in Probe
message, update its their status to indicate the availability of its
neighbors.
b. Report message: Based on exchanging report messages, the routers
can build the Multicast delivery tree rooted at each source. A
function called ReportPkPro will be called to handle all possible
situations when receiving a report message. If the message is a
poison reverse report and not coming from one of the dependent
downstreams, the incoming interface should be added to the router's
downstream list. If the message is not a poison reverse report but it
came from one of the downstreams, this interface should be deleted
from the downstreams list. And then, the router compared the metric
got from the message with the metric of the current upstream, if the
new metric is less than the older one, the router's upstream
interface should be updated.
c. Prune message: The router extracts the source address, group
address and prune lifetime, marks the incoming interface as pruned in
the dependent downstream list of the (source, group) pair. If all
downstream interfaces have been pruned, the router will send a prune
message to its upstream.
d. Graft message: The router extracts the source and group address,
active the incoming interface in the dependent downstream list of the
(source, group) pair. If the (source, group) pair has been pruned,
the router will reconnect the branch by sending a graft message to
its upstream interface.
e. Graft Acknowledge message: The router extracts the source and
group address, clear the graft message timer of the (source, group)
pair in the forwarding table.
7.8 Route_Calc
The transition to this state is triggered by the local IP process.
Once the IP receives a packet, it will fire a remote interrupt to the
DVMRP and ask the DVMRP to prepare the outgoing interfaces for the
packet. The DVMRP process obtains the packet's source address and
group address from the IP and checks the (source, group) pairs in the
forwarding table to decide the branches that have the group members
on the Multicast delivery tree. The Group Membership Table on IP will
be updated based on this knowledge.
7.9 Timer
This state is activated once every second. It checks the forwarding
table, if the Graft message acknowledgment timer is expired, The
router will retransmit the Graft message to the upstream. If the
prune state lifetime timer is expired, the router will graft this
interface so that the downstream router can receive the packets to
the group again. The router also checks if the (source, group) pair
is pruned by the upstream router, if so, it will send a graft message
to the upstream interface.
8. Simulation performance
Our simulations of three network models with MOSPF routing have
showed good Scalability of the protocol. The running platform we used
is a SGI Octane Station with 512 MB main memory and MIPS R10000 CPU,
Rev 2.7. Here we list the real running time of each model along with
its major elements and the packet inter-arrival times for the streams
generated in the hosts.
Simulated Debug Model Intermediate Model Large Model
time 11 Routers 42 routers 86 routers
12 Hosts 48 hosts 96 hosts
Reserve Data Reserve Data Reserve Data
0.01s 0.02s 0.02s
Best-effort Data Best-effort Data Best-effort Data
0.01s 0.025s 0.025s
100 s 3 hours 14 hours 30 hours
200 s 7 hours 30 hours - - -
9. Future work
We hope to receive assistance from the IPmc/RSVP development
community within the IETF in validating and refining this model. We
believe it will be a useful tool for predicting the behavior of
RSVP-capable systems.
10. Security Considerations
This RFCraises no security considerations.
11. References
[1] Deering, S., "Host Requirements for IP Multicasting", STD 5,
RFC1112, August 1989.
[2] Braden, R., Zhang, L., Berson, S., Herzog, S. and S. Jamin,
"Resource Reservation Protocol (RSVP) -- Version 1 Functional
Specification", RFC2205, September 1997.
[3] Wroclawski, J., "The Use of RSVP with IETF Integrated Services",
RFC2210, September 1997.
[4] MIL3 Inc., "OPNET Modeler Tutorial Version 3", Washington, DC,
1997
[5] Moy, J., "Multicast Extensions to OSPF", RFC1584, March 1994.
[6] Pusateri, T., "Distance Vector Multicast Routing Protocol", Work
in Progress.
Authors' Addresses
J. Mark Pullen
C3I Center/Computer Science
Mail Stop 4A5
George Mason University
Fairfax, VA 22032
EMail: mpullen@gmu.edu
Ravi Malghan
3141 Fairview Park Drive, Suite 700
Falls Church VA 22042
EMail: rmalghan@bacon.gmu.edu
Lava K. Lavu
Bay Networks
600 Technology Park Dr.
Billerica, MA 01821
EMail: llavu@bacon.gmu.edu
Gang Duan
Oracle Co.
Redwood Shores, CA 94065
EMail: gduan@us.oracle.com
Jiemei Ma
Newbridge Networks Inc.
593 Herndon Parkway
Herndon, VA 20170
EMail: jma@newbridge.com
Hoon Nah
C3I Center
Mail Stop 4B5
George Mason University
Fairfax, VA 22030
EMail: hnah@bacon.gmu.edu
Full Copyright Statement
Copyright (C) The Internet Society (1999). All Rights Reserved.
This document and translations of it may be copied and furnished to
others, and derivative works that comment on or otherwise explain it
or assist in its implementation may be prepared, copied, published
and distributed, in whole or in part, without restriction of any
kind, provided that the above copyright notice and this paragraph are
included on all such copies and derivative works. However, this
document itself may not be modified in any way, such as by removing
the copyright notice or references to the Internet Society or other
Internet organizations, except as needed for the purpose of
developing Internet standards in which case the procedures for
copyrights defined in the Internet Standards process must be
followed, or as required to translate it into languages other than
English.
The limited permissions granted above are perpetual and will not be
revoked by the Internet Society or its successors or assigns.
This document and the information contained herein is provided on an
"AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING
BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION
HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF
MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.