Project Report
Simulation and Performance Analysis of QoS extensions to OSPF.
Submitted in partial fulfilment of requirements for the degree, Master of Science in Computer Science by
Lava K Lavu
Dr. Mark Pullen, Project Advisor
George Mason University
Fairfax, Virginia
Contents
1. Introduction
2. Simulation Environment
2.1 Network Layer
2.2 Node Layer
2.3 Process Layer
3. Node Level Description of Network Elements
3.1 FDDI Host
3.2 FDDI Gateway
3.3 Backbone Router
4. Description of Protocols
4.1 QOSPF
4.2 RSVP
5. Process Models
5.1 Reserved Multicast Traffic Generating Application
5.2 RSVP on Hosts
5.3 RSVP on Routers
5.4 QOSPF
6. Performance Tests
6.1 Small Network
6.2 Intermediate Network
6.3 Big Network
7. Future Work
8. Conclusions
9. References
Appendix A : Acronyms used in this report
Appendix B : Source Code
1. Introduction
The project was intended to study the scaling behavior of QOSPF for large scale
networks. The reference used to implement QOSPF[1] was draft-zhang-qos-ospf-00.txt[1]. The RSVP[2] protocol was used for setting up the QoS flows and passing the QoS information to the QOSPF daemon. The traffic chosen to test the network behavior is Best-effort unicast, best-effort multicast and QoS multicast flows. To have the unicast and multicast routing OSPF[3] and MOSPF[4] behavior is also simulated. The overall simulation was a team effort; IP and IGMP[5] simulations were by Ravi Malghan. Extensions were added to this code to handle the required functionality for having the QOSPF and RSVP running.
OPNET[6] was used to simulate these protocols. Three test networks with number of routers ranging from five to eighty-six are used to test the simulation. This project report will explain the details of the simulation, tests done and the work that can be done in the further.
Real-world traffic parameters and structures were provided by E-Systems which supported part of the work to create the models. Additional suggestions were provided by Eric Crawley of Bay Networks.
2. Simulation Environment
OPNET was used as the simulation tool for this project. OPNET is a layered approach that is top down layer from the network to the process layer. This layered approach is not in any way related to the layered model of the internet. The highest layer in the OPNET is Network layer, the next one is node layer and the last one is process layer.
2.1 Network Layer
Network layer represents the network that is being simulated. The network was built using the OPNET network editor. The network topology includes backbone routers, area border routers, and FDDI subnets where each subnet has a FDDI gateway and 2 hosts. Each of these network elements is interconnected using a pair of simplex links that enables the bi-directional traffic. Figure 1 shows the top layer of network.
The network layer also shows the structure of the subnet. The subnet we have simulated is FDDI subnet that has two hosts and gateway connected in a ring topology. The gateway acts as a router that routes the packets from/to the hosts in the subnet to/from the external network. Figure 2 shows the subnet structure.
Figure 1 : Top layer of the model's network
Figure 2 : FDDI Ring Structure
The attributes of the elements of the network layer are
- Area Border Routers, Backbone Routers :
- IP address of each active interface
- Service rate at the IP layer(packets/sec)
- Area to which the router belongs to
- Transmission speeds of each active interface(bits/sec)
- Subnets :
- IP address of each active interface of the gateway of the subnet
- IP address of each host on the subnet
- Area to which the subnet belongs to
- Service rate at the IP layer
- Simplex links :
- Propagation delay in the links
- Process model used for simulating the simplex link behavior
The network elements simulated are
- Routers
- FDDI Gateway
- FDDI hosts
2.2 Node Layer
This layer was built using Node editor. This layer represents the internal structure of the routers and hosts. The basic blocks of the node level structure are
- Process nodes : These nodes are used to simulate the behavior of the various protocols which process the incoming packets and routes the outgoing packets. Some of the process nodes are IGMP, QOSPF, RSVP and so on.
- Queue nodes : Queue nodes are capable of storing packets in addition to the capability of processing the packets. In this node one or more number of queues can be simulated. The queuing behavior of the network is simulated in these nodes. The only Queue node is IP.
- Transmitter nodes : These nodes are used to simulate the transmitting behavior of the packet and the attribute of these nodes is transmission speed which in turn along with the receiver speed effects the transmission delay of the packet.
- Receiver nodes : These nodes simulate the effect of packet reception. The attribute for this node is receiver speed.
- Streams : These are used to interconnect the above nodes and to convey information from one node to other node. Also the packets that are needed to travel between various nodes are sent over these streams.
2.3 Process Layer
The process layer will have the states of each process being simulated. Each state will have arrival and exit executives which take the form of the code written for simulating the process or protocol. The code is written in C and does have some OPNET related calls that are provided by the OPNET library. Variables and functions are defined in this layer. The following blocks are used
- Header block used for definitions of the structures and preprocessor commands
- State variable block used for defining the variables that are accessible for all the states in the process model
- Temporary variable block used to define the variables that are accessible to a particular state
- Function block used to write the functions that are used by the process.
3. Node Level Description of the network elements
3.1 FDDI Host
The elements of the node structure of the FDDI hosts are :
- MAC Queue Node
- Address Translation Processor Node
- IP Queue Node
- IGMP Processor Node
- RSVP Processor Node
- Unicast Application Processor Node
- Multicast Application Processor Node
- Reservable Multicast Application Processor Node
Figure 3 represents the node level structure of the FDDI Host.
Figure 3 : Node Level structure of FDDI host
MAC Queue Node :
The MAC node is connected to transmitter, receiver and IP node. When a frame arrives to the MAC layer and if the frame is destined to that node it destroys the frame, if the frame is destined for this host it makes a copy, decapsulates the frame and sends the packet to IP layer and the copied frame to next host in the ring. If the owner of the frame is any other host and the frame is not destined to this host then the frame is sent to the adjacent host.
Address Translation Processor Node :
This layer provides the address translation from IP address to physical interface address. It accepts packets from the IP layer which have the next node information, maps the next node information on to the physical interface and forwards the packet for transmission. This service is done in between when the packet is going from IP layer to MAC.
IP Queue Node :
The IP layer provides service to the higher layer protocols by utilizing the services provided by the MAC layer. The IP layer receives packets from MAC layer and the higher protocols that are on the top of it (IGMP, RSVP and applications). If it receives from the MAC layer it forwards this packet to the higher layer depending upon the protocol id in the IP header of the packet. If the packet is from the upper layer protocols or applications then it calculates the next node information depending on the packet's destination address and its routing table entry, encapsulates the packet with the IP header and forwards the packet to address translation node.
IGMP Processor Node :
This node simulates the IGMP protocol at the host. The following are the functions performed by this process model. It accepts a join group request from the multicast applications, if the host is already a member of this group this does not need to send any messages to any nodes and if the host is not a member of this group it sends a join request for this group to the IP layer. If a query is received from the nearest router it sends a response indicating to which groups the host is registered to. This information is obtained by looking up a multicast membership table that is maintained by this node. If the application layer sends a terminate request for a group, the IGMP node will remove the entry for this application on that group and does not send a response for a query on this group.
RSVP Processor Node :
This node receives packet from the reservable traffic generating application. The functionality of this node is explained in more detail later in the report in section 5 with state transition diagrams. The following is brief description of the functionality of this node. When it receives a session call from the application it generates and session id for the session and sends this session id to the application through an upcall. If it receives a sender call from the application, it creates the path message that needed to be send by getting the information from the sender call it received from the application and send the Path message to the IP layer for further transmission. If it receives a reserve call from the application it creates and fills the Resv message from the information obtained through the reserve call by the application. It sends the Resv message to IP layer. When it gets a release call from the application it creates PathTear or ResvTear message depending upon
the application and sends the message to IP layer.
Unicast Best Effort Traffic Generating Application Processor Node :
This traffic generating application generates packets that are destined to a unicast node which is selected randomly. The packet size is of 576 bytes and the packets are generated at a rate of 30 pps. This traffic was generated in order to generate background traffic for performance analysis of QOSPF.
Multicast Best Effort Traffic Generating Application Processor Node :
This traffic generator generates multicast traffic destined for a multicast group that is randomly generated from a number between 0 and maximum number of groups. The application sends or receives the multicast packets for a specific period of time that is a uniform distribution ranging from session minimum time and session maximum time. The session inter arrival time is an exponential distribution with a mean of Session IAT. The data packet is of 576 bytes size and they are generated at a rate of 30 pps.
Reservable Multicast Traffic Generating Application Processor Node :
This application generates multicast traffic. It makes a session call to the local RSVP daemon and gets the session id of the session that it wants to initiate. Once the session was initiated if the application is a sender then it makes a sender call to the local RSVP daemon and sends a join request to the local IGMP daemon. If the application is a receiver it makes a reserve call to the RSVP daemon and sends join call to IGMP daemon. If the application wants to leave the session it sends a release call to the local RSVP daemon and terminate call to IGMP daemon. It logs all the session information in a global directory called session directory so that the IP layer of all the routers can look into this directory and see if the packet destined for a particular group is a reservable packet or a best effort packet. This process was explained in more detail with state transition diagrams in section 5.
Size of data packet sent is 576 bytes and they are generated at a rate of 60 pps. Each application stays in a session for a random amount of time selected uniformly between Session Minimum (10 secs) and Session Maximum (20 Secs). The session inter arrival time is 20 secs.
3.2 FDDI Gateway :
The elements of the node level structure of the FDDI gateway are
- MAC Queue Node
- Address Resolution Processor Node
- Transmitter phy_tx
- Receiver phy_rx
- IP Queue Node
- IGMP Processor Node
- QOSPF Processor Node
- RSVP Processor Node
Figure 4 represents the node level structure of the FDDI gateway
Figure 4 : Node Level Structure of FDDI Gateway
MAC Queue Node :
This node does have the same functionality as that of host node layers MAC node. This process accepts all the multicast packets whereas the MAC layer in a host accepts only the multicast packets for which the host is a member of.
Address Resolution Processor Node :
This does have the same functionality of the Address Resolution processor node of the host that is explained previously.
IP Queue Node :
This layer provides services to the upper layer protocols and also performs routing based upon the information in its routing table. The routing information is obtained from two routing tables that are maintained at this node. Unicast routing information is obtained from a Unicast routing table that is updated by the QOSPF on calculation of the shortest routes. Multicast routing information is obtained from a multicast routing table that is a two dimensional array which says given the multicast address, on which the interfaces the packet needs to be sent. This table is also updated by the upper layer QOSPF protocol.
The IP layer also sends a remote interrupt to the QOSPF daemon whenever a multicast packet is obtained and this remote interrupt is sent to calculate either multicast paths or the QoS sensitive paths depending upon the destination and source address of the packet that needs to be routed. This node also maintains a group membership table that stores the group membership information of all the interfaces.
The IP layer has 3 sub queues built in it. Each sub queue has an index and the queue that has lowest index has highest priority. The control packets are queued in sub queue indexed 0, reservable traffic is queued in sub queue indexed 1 and the best effort traffic is queued in the sub queue indexed 2. These queues are made finite and any type of packets that are received when its queue is full are dropped.
IGMP Processor Node :
This layer simulates the IGMP protocol as specified by RFC 1112 and the process for this node is developed by Ravi Malghan. The IGMP process at the router sends queries at regular intervals on all of its interfaces. When it receives a response to the queries sent it updates the group membership table that is maintained at the IP node. When it receives a query the IGMP process creates the response for each of the groups it is a member of on all the interfaces except the one through which the query was received. Every time the IGMP sends a query, it also updates the multicast group membership table at the IP node if no response is received on for any group on any interface, indicating that an interface is no longer a member of a specific group.
QOSPF Processor Node :
This layer simulates the QOSPF protocol which was proposed in the Internet Draft draft-ietf-zhang-qos-ospf-00.txt. In order to have the QOSPF running we need to have OSPF and MOSPF whose behavior was also simulated at this layer.
This layer sends OSPF Link State Advertisement's(LSA) (Router, network and summary LSA's), MOSPF LSA's(Group membership LSA's) and QOSPF LSA's (Resource and Reservation) periodically. It also sends these LSA's whenever there is a change in the information carried by them. When it a receives a remote interrupt from the IGMP layer(when it was joining to a new group) it sends a group membership lsa and if it gets a remote interrupt from RSVP layer(when a reservation on a link is made) it sends out the reservation LSA's.
All the LSA's are packed into a Link State Update packet and this packet is sent to the IP layer. The destination address of this packet is AllSPFRouters which means that this packet should not be forwarded more than one hop. It also sends hello packet to form adjacencies. When it receives a hello packet or link state update packets it updates the database of the router to store the information received from these packets. Also, in the case of link state update packet it makes the transition to corresponding shortest path calculations depending upon the type of the link state advertisements that are in the link state update packet.
RSVP Processor Node :
This processor node simulates the behavior of the RSVP protocol that is specified in the RSVP functional specification internet draft. Only fixed filter style was simulated. A more detail explanation of this process with state transition diagram is given in section 5.
This processor node handles the Path, Resv, ResvTear, PathTear and ResvConf messages that are obtained from the other routers. When a Path message is received, after consistency checks it will check if the PathStateBlock(PSB) corresponding to the received Path message exists or not, if it exists and its Tspec are different from the one in the Path message it updates the PSB and sends a PathRefresh message. If the corresponding PSB doesn't exist it creates a new one and sends a PathRefresh message. Also, it checks for the Reservation State Block(RSB) whose filter spec matches the sender template of PSB and if a matching RSB is found then a ResvRefresh message is sent update traffic control sequence is executed. PathRefresh creates the Path message and sends the Path message through the outgoing interfaces that are specified by the PSB.
When a Resv message is received after the consistency checks it checks for a matching PSB for the sender information. If such a PSB is found it checks for a matching RSB and if no such RSB is found it creates a new one and send ResvRefresh message. If a matching RSB is found update traffic control sequence is executed. The update traffic control functions calculates the effective kernel traffic control flowspec for all the RSB's. It checks for a matching TCSB whose session object and outgoing interface matches those of input RSB. If no such TCSB is found new TCSB is created and if such a TCSB is found then its reservations are modified. A remote interrupt is send to QOSPF layer that there a new reservation is made.
When a PathTear message is received then it searches for a matching PSB and if one is found it was removed and a PathTear message is sent through all the outgoing interfaces that are listed in PSB. When a ResvTear message is arrived it searches for a matching RSB and if one is found it sends a ResvTear message to all previous hops listed in Refresh PHOP list.
3.3 Backbone Router :
The backbone router will also have the same elements as that of FDDI gateways except that it doesn't have MAC node. The functionality provided by each element is also same as that of the FDDI gateways.
Figure 5 represents the node level structure of the router.
Figure 5 : Node Level Structure of Backbone Router
5. Process Models
5.1 Reserved Multicast Traffic Generating Application
Figure 6 shows the process model diagram of the Reservable Multicast Traffic Generating Application. This application generates multicast traffic and also requests the RSVP daemon that is running on the host to reserve resources for this traffic.
Figure 6 : State diagram of RSVP Application
Each states function is explained in detail below :
Init :
Initialize all variables and load the distribution functions for Multicast Group IDs, termination of the session. Transits to Idle state after completing all the initializations.
Idle :
This state has transitions to four states, Arr, Join, Data_Send and EndSim. It transits to Arr state upon Packet Arrival, transit to Join state when the Join interrupt was true, transit to Data_Send state when the Send_Data interrupt was true, transit to EndSim state when simulation ends.
Arr :
In this state if a data packet arrives the application will increment the Data Received counter, and if a Session message from Local RSVP daemon arrives it update it's Registered Session directory. After completing these functions it will return to the idle state.
Join :
The Application will send a session call to local RSVP daemon and once it receives the session Id from the Local daemon it makes a sender or receiver call. The multicast group id is selected randomly from a uniform distribution. While doing a sender call the application will write all its sender information in a global session directory.
If the application is acting as a receiver it will check for the sender information in the session directory for the multicast group that it wants to join to and makes a receive call to the local RSVP daemon. Along with these two calls it makes a IGMP join call.
If the application chooses to terminate the session it was registered to, it will send a release call to the local RSVP daemon and a terminate call to IGMP daemon.
After completing these functions it will return to the idle state.
Data_Send :
Creates a data packet and send it multicast destination that it selects. It updates a counter to keep track of how many packets that it has sent. This state on default returns to Idle state.
EndSim :
This state gives statistics of how many packets have received and how many packets have been sent.
5.2 RSVP On Hosts
Figure 7 shows the process model of RSVP on hosts. This process simulates the behavior of the RSVP on hosts. This state creates and sends sender, session, reserve, release messages depending on the upcall that it has received from the applications.
Figure 7 : State transition diagram of RSVP on hosts
The following describes each state function in detail :
Init :
Initializes all the variables. Default transition to idle state.
idle :
This state transit to the Arr state on packet arrival.
Arr :
This state calls the appropriate functions depending on the type of message received. Default transition to idle state.
- MakeSessionCall : This function is called from the Arr state whenever a Session call is received from the local application.
- Search for the Session Information.
- If one is found return the corresponding Session Id.
- If the session information is not found assign a new session Id to the session to the corresponding session.
- Make an UpCall to the local application with this Session Id.
- MakeSenderCall : This function is called from the Arr state whenever a Sender call is received from the local application.
- Get the information corresponding to the Session Id and create a Path message corresponding to this session.
- This packet is sent to the IP layer.
- MakeReserveCall : This function is called from the Arr state whenever a Reserve call is received from the local application. This function will create and send a Resv message.
- MakeReleaseCall : This function is called from the Arr state whenever a Release call is received from the local application. This function will generate a PathTear message if the local application is sender or generates a ResvTear message if the local application is receiver.
EndSim :
This state does not do anything, it exists to terminate the simulation.
Session :
This state's function is performed by the MakeSessionCall function. (see above)
Sender :
This state's function is handled by the MakeSenderCall function. (see above)
Reserve :
This state's function is performed by the MakeReserveCall function. (see above)
Release :
This state's function is performed by the MakeReleaseCall function. (see above)
5.3 RSVP On Router
Figure 8 shows the process model diagram of the RSVP on router. This process implements RSVP on router and makes the reservations that are needed for the reservable traffic if resources are present or it will let the application know if the reservation request fails at any point in the path of the traffic.
Figure 8 : State transition diagram of RSVP on router
Each states functionality is explained in detail below:
Init :
This state calls a function called RouterInitialize that will initialize all the router variables. This state will go to Idle state after completing these functions.
Idle :
Idle state transit to Arr state upon receiving a packet.
Arr :
This state checks for the type of the packet arrived and calls the appropriate function depending on the type of message received.
- PathMsgPro: This function was invoked by the Arr state when a path message is received. It does the following steps.
- It first checks for a Path state block that has a matching destination Address and if the sender port or sender address or destination port does not match the values of the Session object of the Path state block, it sends a path error message and returns. (At present in our application we are not sending any error messages, we are printing this error message on to console.)
- If a PSB is found whose Session Object and Sender Template Object matches with
that of the path message received, the current PSB is made as forwarding PSB.
- Search for the PSB whose session and sender template match the corresponding
objects in the path message and whose incoming interface matches the
IncInterface. If such a PSB is found and the if the Previous Hop Address, Next
Hop Address, and SenderTspec Object doesn't match that of path message then
the values of path message are copied into the path state block and Path Refresh
Needed flag is turned on. If the Previous Hop Address, Next Hop Address of PSB
differs from the path message then the Resv Refresh Needed flag is also turned on,
and the Current PSB is made equal to this PSB.
- If a matching PSB is not found then a new PSB is created and Path Refresh
Needed Flag is turned on, and the Current PSB is made equal to this PSB.
- If Path Refresh Needed Flag is on, Current PSB is copied into forwarding PSB and
Path Refresh Sequence is executed. To execute this function called PathRefresh is
used. Path Refresh is sent to every interface that is in the outgoing interfaces list
of forwarding path state block.
- Search for a Reservation State Block whose filter spec object matches with the Sender Template Object of the forwarding PSB and whose Outgoing Interface matches one of the entry in the forwarding PSB's outgoing interface list. If found then a ResvRefresh message to the Previous Hop Address in the forwarding PSB and execute the Update Traffic Control sequence.
- PathRefresh: This function is called from PathMsgPro. It creates the Path message sends the message through the outgoing interface that is specified by the PathMsgPro.
- ResvMsgPro: This function was invoked by the Arr state when a Resv message is received.
- Determine the outgoing interface and check for the PSB whose Source Address and Session Objects match the ones in the Resv message.
- If such a PSB is not found then send a ResvErr message saying that No Path Information is available (At present we are not implementing this message and just printing this error message on to console).
- Check for the incompatible styles and process the flow descriptor list to make reservations, checking the PSB list for the sender information. If no sender information is available in the PSB list then send an Error message saying that No Sender information is available. For all the matching PSB's found, if the Refresh PHOP list doesn't have the Previous Hop Address of the PSB then add the Previous Hop Address to the Refresh PHOP list.
- Check for matching Reservation State Block (RSB) whose Session and Filter Spec Object matches that of Resv messages. If no such RSB is found then create a new RSB from the Resv Message and set the NeworMod flag On. Call this RSB as activeRSB. Turn on the ResvRefresh Needed Flag.
- If a matching RSB is found, call this as activeRSB and if the FlowSpec and Scope objects of this RSB differ from that of Resv Message copy the Resv message Flowspec and Scope objects to the ActiveRSB and set the NeworMod flag On.
- Call the Update Traffic Control Sequence. This is done by calling the function UpdateTrafficControl
- If Resv Refresh Needed Flag is On then send a ResvRefresh message for each
Previous Hop in the Refresh PHOP List. This is done by calling the ResvRefresh
function for every Previous Hop in the Refresh PHOP List.
- ResvRefresh : This function is called by both PathMsgPro and ResvMsgPro with RSB and Previous Hop as input. The function constructs the Resv Message from the RSB and sends the message to the Previous Hop.
- PathTearPro : This function is invoked by the Arr state when a PathTear message is received.
- Search for PSB whose Session Object and Sender Template Object matches that of the arrived PathTear message.
- If such a PSB is not found do nothing and return.
- If a matching PSB is found, a PathTear message is sent to all the outgoing interfaces that is listed in the Outgoing Interface list of the PSB.
- Search for all the RSB whose Filter Spec Object matches the Sender Template Object of the PSB and if the Outgoing Interface of this RSB is listed in the PSB's Outgoing interface list delete the RSB.
- Delete the PSB and return.
- ResvTearPro : This function is invoked by the Arr state when a ResvTear message is received.
- Determine the Outgoing Interface.
- Process the flow descriptor list of the arrived ResvTear message.
- Check for the RSB whose Session Object, Filter Spec Object matches that of
ResvTear message and if there is no such RSB return.
- If such an RSB is found and Resv Refresh Needed Flag is on send ResvTear
message to all the Previous Hops that are in Refresh PHOP List.
- Finally delete the RSB.
- ResvConfPro : This function is invoked by the Arr state when a ResvConf message is received. The Resv Confirm is forwarded to the IP address that was in the Resv Confirm Object of the received ResvConf message.
- UpdateTrafficControl : This function is called by PathMsgPro and ResvMsgPro and input to this function is RSB.
- The RSB list is searched for a matching RSB that matches the Session Object, and Filter Spec Object with the input RSB.
- Effective Kernel TC_Flowspec are computed for all these RSB's.
- If the Filter Spec Object of the RSB doesn't match the one of the Filter Spec Object in the TC Filter Spec List then add the FilterSpec Object to the TC Filter Spec List.
- If the FlowSpec Object of the input RSB is greater than the TC_Flowspec then turn on the Is_Biggest flag.
- Search for the matching Traffic Control State Block(TCSB) whose Session
Object, Outgoing Interface, and Filter Spec Object match with those of the Input RSB.
- If such a TCSB is not found then create a new TCSB.
- If matching TCSB is found modify the reservations.
- If Is_Biggest flag is on turn on the ResvRefreshNeededFlag flag, else send a ResvConf Message to the IP address in the ResvConfirm Object of the input RSB.
pathmsg :
The functions to be done by this state are done through the function call PathMsgPro described above.
resvmsg :
The functions that would be done by this state are done through the function call ResvMsgPro described above.
ptearmsg :
The functions that would be done by this state are done through the function call PathTearPro described above.
rtearmsg :
The functions that would be done by this state are done through the function call ResvTearPro described above.
rconfmsg :
The functions that would be done by this state are done through the function call ResvConfPro described above.
5.4 QOSPF
Figure 9 shows the process model diagram of the QOSPF process. This process simulates the behavior of the QOSPF and the required functionality of OSPF and MOSPF. This process broadcasts OSPF, MOSPF and QOSPF LSA's and calculates the best effort unicast, best effort multicast and QoS sensitive multicast routing tables from the input obtained through the LSA's and other protocol processes at that node.
Figure 9 : State transition diagram of QOSPF
The following processing takes place in the indicated states.
init :
This state initializes all the router variables. Default transition to idle state.
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.
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 timeout occurs. This state will create Router, Network, Summary Link State Advertisements and pack all of them into a Link State Update packet. The Link State Update Packet is sent to the IP layer with a destination address of AllSPFRouters.
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.
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.
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.
- QospfPkPro : Depending on the type of QOSPF/OSPF/MOSPF packet received the function calls the following functions.
- 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.
- 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.
- MospfLsUpdatePk_pro : This function is called when a MOSPF LSA update packet is received. It updates the router's group membership link state database. The function also turns on the trigger mospfspfcalc that is the condition for the transition from arr state to mospfspfcalc. In future versions, network topology changes will also trigger this state.
- 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.
- 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.
- Path_Msg_pro: This function gets the source and destination information, sender transmission specs and sets the trigger qospfcalc on.
- 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 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.
- 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.
qospfspfcalc :
This function is used to calculate the QOSPF routing table. Resource LSAs are used to discover the neighbors and RRAs 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, and RRA/DABRA) only cause recalculation of affected entries.
- 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.
- 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.
- 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.
hello_pks :
Hello packets are created and sent with destination address of AllSPFRouters. Default transition to idle state.
mospfspfcalc :
The following functions are used to calculate the shortest path tree and routing table. This state transit to upstr_node upon detupstrnode condition.
- CandListInit : Depending upon the SourceNet of the datagram the candidate lists are initialized.
- 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.
- 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.
- MCRoutetableCalc : Multicast routing table is calculated using the information of the MOSPF shortest Path tree.
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 is set to zero after processing all functions in the state.
- 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.
- 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.
- OspfStubLinkPro : In this procedure the stub networks are added to shortest path tree.
- 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.
- RoutingTableCalc : This function updates the routing table by examining the shortest path tree data structure.
upstr_node :
This state does not do anything in the present model. It transitions to DABRA state.
DABRA :
If the router is an Area Border Router and the area is the source area then a Determinstic Area Border Router Advertisement(DABRA) message is constructed and send to all the downstream areas. Default transition to idle state.
6. Tests Performed
Several tests are performed on the three network models to analyze the performance of the QOSPF protocol. Two internet drafts are written and presented to Internet community at 37th IETF meeting held at San Jose. The Internet drafts are
-
draft-pullen-qospf-model-01[7] : This draft explains the QOSPF model and the results that are obtained for the simualted networks.
-
draft-pullen-ipv4-rsvp-01[8] : This draft expalins in general about the simulation of RSVP using multicast protocols.
For more information about these drafts visit the web site http://nac.gmu.edu/qosip
6.1 Small Network
Figure 10 shows the small network that has been simulated. Some sample runs are taken on this network to see if the simulation is functioning properly or not. Validation of this model with a real system developed by E-Systems is on going.
Figure 10 : Small network model
6.2 Intermediate Network
Figure 11 shows the intermediate network that has been simulated and tested. Several probes are written using the OPNET library to measure the performance metrics.
Figure 11 : Intermediate network model
T1 Link. -- Small network model.
Some of the probes that are written are
- Cumulative Number of LSA's Received by a Router. This is measured in QOSPF module.
- Queue depth in each queue. This is in packets and is measured at output queue that connects the IP module with the transmitter.
- Cumulative Number of bits serviced by the IP module.
- Average Service rate of IP module in bits per sec
- Cumulative Number of packets sent by each application. This is measured at each application.
During the testing of the network these probes are placed on each area border router, a fddi gateway and host. Below figures are some of the results that we have obtained.
Graph 1 : Cummulative Number of LSA's Receieved by an Area Border Router
The above graph represents the number of Link State Advertisments(includes
Router, Summary, Network, Group Membership, Resource, Reservation
Advertisments) that are received by the Area Border Router. This number
increased rapidly during the first 10 secs and then remained almost constant
for a period of 20 secs and then received again a large number of LSA's at an
interval of 20 sec. This can be explained by the facts that the during the
first 10 secs of the simulation all the routers gets intialized and send the
LSA update packets to all the other routers in the network, so the routers
recieve a large number of LSA's during this period. During the next 20 secs
(between 10 and 30 secs of simulation), the router doesn't send any LSA's
except Group membership LSA and RRA's which are few when compared to the scale,
so the graph seems to be constant during this time of simulation. Again at 30
sec a large number of LSA's are received because the refresh period for sending
LSA's is set to 20 sec from the intialization time(Intialization time is
10 sec in this case). The same fact also explains the number of LSA's received
at 50 sec.
Graph 2 : Cummulative Number of bit's Serviced by an Area Border Router
The above graph represents the cummulative number of bits serviced by the IP module of an Area Border Router. During the first 10 secs the number of bits serviced increased gradually and all this data is due to the LSA traffic that is going through the network during the initialization period. From 10 to 20 secs the curve remains constant because there is no traffic during this period (since the intialization time is 10 sec and the data generators are not turned on till 20 sec). After 20 sec all the data generators are turned on and the traffic that is serviced by the IP module increases rapidly. The ramp that is starting 20 sec is due to the traffic that is generated by the applications (data generators).
Graph 3 : Mean Queue Length at IP layer of F1 ring's FDDI Gateway
The above graph represents the Mean Queue length at IP layer of the FDDI
gateway. It can be seen that the queue length increases during the first 10
secs due to the LSA traffic during the intialization time and once the network
is initialized(can also be said as stabilized) and the data generators are
turned on the queue length remains constant.
More output graphs obtained for this model can be found at the web site http://nac.gmu.edu/qosip/Results/IntrNet
6.3 Large Network
Figure 12 shows the large network model that we have developed.
Figure 12 : Large network model
T1 Link. T3 Link. -- Small network model used section 6.1
The same probes that are used in the intermediate size network are used in the large network also for performance and other calculations. These probes are placed on each backbone router, two area border routers, a fddi gateway and a couple of hosts. The following are some of the output graphs that are obtained.
Graph 1 : Cummulative Number of LSA Update Packet's Receieved by an Backbone Router
The above graph represents the cummulative number of LSA update packets that
are received by an backbone router. The LSA update packets infact will
transmit the LSA's through out the network. So there is constant increase in
the number of LSA update packets received during the the network
initialization time. Again it receives a large number of LSA update packets at
30 sec which is are the LSA update packets that are sent by other routers in
the network at the refresh period.
Graph 2 : Queue Length at q2 of an Area Border Router
The above graoh represents the queue length at one of the queues of an Area
Border Router. The queue length remains almost constant until the data
generators are turned on and once they are turned on the queue lenght
increases constanly. This constant increase in the queue length suggests that
the IP layer may not be dropping the packets even when the buffer is full.
More output graphs obtained for this model can be found at the web site http://nac.gmu.edu/qosip/Results/BigNet
7. Future Work
Some of the future work that can be done on this model is
- Make the Explicit Routing functional
- Develop RSVP for all other reservation styles
- Complete the two left over RSVP messages
- Test the model to its fullest extent and validate it.
- Make the QOSPF sensitive to the link failure
- Run a bigger simulation
8. Conclusions
This model was intended to provide some feedback to the development of the
QOSPF and the model is itself an acheivement in doing this. The model tried to
address issues that are concerned to the QOSPF like scalability. The QOSPF
protocol is in the development stage and the model is an excellent start in
trying the simulate and predict the behaviour and performance of the this
protocol.
For all the tests that are performed Explicit routing is not used and
still the network is initialized within 10 sec and all the routing is being
done correctly after all the data generators were turned on. There is no
problem with respect to the transmission of the RRA's or storing the RRA's
received. So far from the above reason we say that the QOSPF is scalable even
without having the Explicit Routing. To obtain more details on this a longer
simulation needs to be performed and more probes are needed to measure the
number of RRA's that are being flodded in the network. More tests are also
needed to be performed to get more conclusions and more information about the
number of QOSPF LSA's (Resource and RRA) flodded in the network, and see the
overhead caused by the QOSPF functionality.
Two internet drafts are written describing this model
- draft-pullen-ipv4-rsvp-01 by Mark Pullen, Ravi Malghan, Lava K Lavu. This draft describes the multicast model with RSVP
- draft-pullen-qospf-model-01 by Mark Pullen, Lava K. Lavu, Eric Crawley and Hai Nguyen. This draft describes the QOSPF model along with the multicast and RSVP
9. References
[1] Zhang et. al., "Quality of service Extensions to OSPF",
work in progress (draft-zhang-qos-ospf-00.txt), June 1996
[2] Braden et. al., "Resource Reservation Protocol Vesion1 Functional Specification",
work in progress (draft-ietf-rsvp-spec-12), June 1996
[3] Moy, "OSPF Specification", RFC 1131, October 1989
[4] Moy, "MOSPF: Analysis and Experience", RFC 1585, March 1994
[5] Deering, "Host Requirements for IP multicasting", RFC 1112, August 1989
[6] MIL3 Inc., OPNET : Optimized Network Engineering Tools, manuals,
November 1991
[7] Mark Pulllen et. al., "A simulation of QOSPF Multicasting for a Large Area",
work in progress (draft-pullen-qospf-model-01), December 1996
[8] Mark Pullen et. al., "A Simulation Model for IP Multicast with RSVP",
work in progress (draft-pullen-ipv4-rsvp-01), December 1996
Appendix A
Acronyms used in this report
IGMP Internet Group Membership Protocol
IP Internet Protocol
LSA Link State Advertisement
MAC Medium Access Control
MOSPF Multicast Open Short Path First
OPNET Optimized Network Engineering Tools
OSPF Open Short Path First
QoS Quality of Service
QOSPF Quality of Service Path First
RSVP Resource Reservation Protocol