IGMP simulation on OPNET
Catherine Chun Jin
There are three fundamental types of IPv4 addresses: unicast, broadcast, and multicast. A unicast address is designed to transmit a packet to a single destination. A broadcast address is used to send a datagram to an entire subnetwork. A multicast address is designed to enable the delivery of datagrams to a set of hosts that have been configured as members of a multicast group in various scattered subnetworks.
Multicasting is not connection oriented. A multicast datagram is delivered to destination group members with the same "best-effort" reliability as a standard unicast IP datagram. This means that a multicast datagram is not guaranteed to reach all members of the group, or arrive in the same order relative to the transmission of other packets.
Instead of a Class A, B, or C IP address, multicasting employs a Class D address format (224.0.0.0 - 239.255.255.255).
Individual hosts are free to join or leave a multicast group at any time. There are no restrictions on the physical location or the number of members in a multicast group. A host may be a member of more than one multicast group at any given time and does not have to belong to a group to send messages to members of a group
A group membership protocol is employed by routers to learn about the presence of group members on their directly attached subnetworks. When a host joins a multicast group, it transmits a group membership protocol message for the group(s) that it wishes to receive, and sets its IP process and network interface card to receive frames addressed to the multicast group. This receiver-initiated join process has excellent scaling properties since, as the multicast group increases in size, it becomes ever more likely that a new group member will be able to locate a nearby branch of the multicast distribution tree.
Multicast IP conserves bandwidth by forcing the network to do packet replication only when necessary, and offers an attractive alternative to unicast transmission for the delivery of network ticker tapes, live stock quotes, multiparty video, conferencing and shared whiteboard applications, among others. Multicast IP can also play an important role in large distributed commercial networks.
IP Multicast technologies are quickly moving into real production systems. Several large companies are building multicast-based infrastructures to support multimedia, conferencing, or general multicast-based applications. However, for large scale and highly available networks, the implications of utilizing IP multicast technologies are not well understood. One way of measuring the performance characteristics of IP Multicast technologies is by building simulation models, and executing series of. OPNET is a widely used network simulation tool that allows one to develop detailed protocol models, execute simulations, and gather performance statistics. Furthermore, within the tools, one can inject switch, router, link, or host failures and measure the fault recovery behavior.
In multicast, when the sender and receivers are members of the same (LAN) subnetwork, the transmission and reception of multicast frames is a relatively simple process. The source station simply addresses the IP packet to the multicast group, the network interface card maps the Class D address to the corresponding IEEE-802 multicast address, and the frame is sent. Receivers that wish to capture the frame notify their IP layer that they want to receive datagrams addressed to the group.
Things become much more complicated when the sender is attached to one subnetwork and receivers reside on different subnetworks. In this case, the routers are required to implement a multicast routing protocol that permits the construction of multicast delivery trees and supports multicast data packet forwarding. In addition, each router needs to implement a group membership protocol that allows it to learn about the existence of group members on its directly attached subnetworks.
The Internet Group Management Protocol (IGMP) runs between hosts and their immediately-neighboring multicast routers. The mechanisms of the protocol allow a host to inform its local router that it wishes to receive transmissions addressed to a specific multicast group. Also, routers periodically query the LAN to determine if known group members are still active. Based on the group membership information learned from the IGMP, a router is able to determine which (if any) multicast traffic needs to be forwarded to each of its "leaf" subnetworks. Multicast routers use this information, in conjunction with a multicast routing protocol, to support IP multicasting across the Internet.
As showed above, IGMP is only concerned with the forwarding of multicast traffic from the local router to group members on directly-attached subnetworks, not concerned with the delivery of multicast packets between neighboring routers or across an internetwork.
To provide an Internet-wide delivery service, it is necessary to define multicast routing protocols. A multicast routing protocol is responsible for the construction of multicast packet delivery trees and performing multicast packet forwarding. There are a number of different algorithms that may potentially be employed by multicast routing protocols: Flooding, Spanning Trees, Reverse Path Broadcasting (RPB), Truncated Reverse Path Broadcasting (TRPB), Reverse Path Multicasting (RPM), Core Based Trees. These algorithms are implemented in several prevalent multicast routing protocols in the Internet: Distance Vector Multicast Routing Protocol (DVMRP), Multicast OSPF (MOSPF), Protocol-Independent Multicast (PIM).
In an IP multicast simulation project developed by Internet Real-Time Laboratory in Columbia University, OPNET is used the simulation tool. All models and codes are developed in this environment. Protocol-Independent Multicast (PIM) is served as the multicast routing protocol. IGMP is also developed to coordinate with PIM to get local memberships. Correspondently, unicast IP layer is modified to support multicast routing by hosting both PIM and IGMP. IGMP communicates with PIM, informing PIM of local memberships change whenever it happens.
This document addresses the IGMP implementation as a part of the project, including detailed design, data structures and implementation, along with the modification of IP to host IGMP, and communication between IGMP and PIM.
The Internet Group Management Protocol (IGMP) is used by IP hosts to report their multicast group memberships to any immediately-neighboring multicast routers.
Like ICMP, IGMP is an integral part of IP. It is required to be implemented by all hosts wishing to receive IP multicasts. IGMP messages are encapsulated in IP datagrams, with an IP protocol number of 2. All IGMP messages are sent with IP TTL 1.
Message type
There are three types of IGMP messages of concern to the host-router interaction:
Multicast routers use IGMP to learn which groups have members on each of their attached physical networks. A multicast router keeps a list of multicast group memberships for each attached network, and a timer for each membership. "Multicast group memberships" means the presence of at least one member of a multicast group on a given attached network, not a list of all of the members. With respect to each of its attached networks, a multicast router may assume one of two roles: Querier or Non-Querier. There is normally only one Querier per physical network. All multicast routers start up as a Querier on each attached network. If a multicast router hears a Query message from a router with a lower IP address, it MUST become a Non-Querier on that network. If a router has not heard a Query message from another router for [Other Querier Present Interval], it resumes the role of Querier. Routers periodically [Query Interval] send a General Query on each attached network for which this router is the Querier, to solicit membership information. On startup, a router SHOULD send [Startup Query Count] General Queries spaced closely together [Startup Query Interval] in order to quickly and reliably determine membership information. A General Query is addressed to the all-systems multicast group (224.0.0.1), has a Group Address field of 0, and has a Max Response Time of [Query Response Interval].
When a host receives a General Query, it sets delay timers for each group (excluding the all-systems group) of which it is a member on the interface from which it received the query. Each timer is set to a different random value, using the highest clock granularity available on the host, selected from the range (0, Max Response Time] with Max Response Time as specified in the Query packet. When a host receives a Group-Specific Query, it sets a delay timer to a random value selected from the range (0, Max Response Time] as above for the group being queried if it is a member on the interface from which it received the query. If a timer for the group is already running, it is reset to the random value only if the requested Max Response Time is less than the remaining value of the running timer. When a group's timer expires, the host multicasts a Version 2 Membership Report to the group, with IP TTL of 1. If the host receives another host's Report (version 1 or 2) while it has a timer running, it stops its timer for the specified group and does not send a Report, in order to suppress duplicate Reports.
When a router receives a Report, it adds the group being reported to the list of multicast group memberships on the network on which it received the Report and sets the timer for the membership to the [Group Membership Interval]. Repeated Reports refresh the timer. If no Reports are received for a particular group before this timer has expired, the router assumes that the group has no local members and that it need not forward remotely-originated multicasts for that group onto the attached network.
When a host joins a multicast group, it should immediately transmit an unsolicited Membership Report for that group, in case it is the first member of that group on the network. To cover the possibility of the initial Membership Report being lost or damaged, it is recommended that it be repeated once or twice after short delays [Unsolicited Report Interval]. (A simple way to accomplish this is to send the initial Version 2 Membership Report and then act as if a Group-Specific Query was received for that group, and set a timer appropriately).
When a host leaves a multicast group, if it was the last host to reply to a Query with a Membership Report for that group, it SHOULD send a Leave Group message to the all-routers multicast group (224.0.0.2). If it was not the last host to reply to a Query, it MAY send nothing as there must be another member on the subnet. This is an optimization to reduce traffic; a host without sufficient storage to remember whether or not it was the last host to reply MAY always send a Leave Group message when it leaves a group. Routers SHOULD accept a Leave Group message addressed to the group being left, in order to accommodate implementations of an earlier version of this standard. Leave Group messages are addressed to the all-routers group because other group members have no need to know that a host has left the group, but it does no harm to address the message to the group.
When a Querier receives a Leave Group message for a group that has group members on the reception interface, it sends [Last Member Query Count] Group-Specific Queries every [Last Member Query Interval] to the group being left. These Group-Specific Queries have their Max Response time set to [Last Member Query Interval]. If no Reports are received after the response time of the last query expires, the routers assume that the group has no local members, as above. Any Querier to non-Querier transition is ignored during this time; the same router keeps sending the Group-Specific Queries.
Non-Queriers MUST ignore Leave Group messages, and Queriers SHOULD ignore Leave Group messages for which there are no group members on the reception interface.
When a non-Querier receives a Group-Specific Query message, if its existing group membership timer is greater than [Last Member Query Count] times the Max Response Time specified in the message, it sets its group membership timer to that value.
Environment Introduction
This project is a part of simulation of several multicast protocols with OPNET. Before we begin the project, we already have a network model on which the simulation works, along with node models and process models. It has 12 routers, some of them linking to both broadcast network and other routers, some only linking to other routers. There are several hosts attached to different subnet. See Fig.1.
All routers use the same node model, seeing Fig 2., while host uses the different. A host sending multicast data packets uses model, seeing Fig 3., while a host only receives multicast data packets uses model, seeing Fig 4.
These 3 kinds of node model all include the same IP_ENCAP, IP and lower layer process models, respectively. And they also include the same UDP, TCP, RIP, etc. See Fig 2., Fig 3., Fig 4.
To support multicast, we need to add more protocol process models into the node models. Ms. Xin Wang and others have done PIM, OSPF. We add IGMP to the models. See Fig 2., Fig 3., Fig 4.
What should be done?
The purpose of IGMP is to let multicast routers learn which groups have members on each of their attached physical networks, such that their IP will forward correspondent multicast data packets to the networks. And the information will also be used by PIM to forwarding multicast data packets between routers. To implement this, IGMP router-side needs to advertise its table, such that other process, IP, PIM, etc. will be able to access its information. IGMP also notifies PIM whenever its table changes, such that PIM is able to modify its own table in time.
IGMP should be implemented in both multicast routers and host, and each router and host. All routers have the same IGMP router-side implementation (process model name is igmprouter), while the hosts share the other one (process name is igmphost). See Fig. 2.
For simulation, host need to join and leave groups, therefore, we implement one more process model data packet receiver (igmp_app), which just randomly generates join and leave group messages and sent them to igmphost. See Fig 2., Fig 3.
To see whether the host is able to receive multicast data packet, we implement a process model (mcast_rec) derived from a data packet generator. But mcast_rec only receives data packet, not sends.
Furthermore, to see how IGMP work, as it involves not only interaction between router and host, between routers, but also between hosts, we modify network models on which simulation works, adding more hosts onto different subnets. Among all these hosts, only one has data packet generator, all others have data packet receiver (igmp_rec). All hosts have igmp_app and igmphost.
Data structure
Igmprouter, igmphost and igmp_app need to maintain their information in tables, respectively. Refer process reports for more details (these are not included in the document).
Router-side data structure
In igmprouter, it needs to maintain an interface table. This table only includes broadcast interfaces. Each interface has a subtable, which remember all groups interested for that interface.
Following is the structure of an entry in the interface table:
typedef struct IGMP_Interface{
IpT_Address interface_address; /* Interface address */
int querier_flag; /* Whether the router is querier for this interface k*/
int waiting_gquery; /* Remaining query count*/
float querytimer; /* Timer for sending query*/
List grp_tab; /* Groups interested by the interface */
float other_q_present_interval; /* Timer of other querier presentation */
/* only valid when the router is not a querier */
}IGMP_Interface;
See that grp_tab is a sublist, which contain group information for that interface. Following is the structure of an entry in the group subtable.
typedef struct grp_tab_node{
IpT_Address grp_ip; /* Group IP address interested on this interface */
int waiting_squery; /* Remaining specific query count */
float non_report_rec_timer; /* Timer that report not received for this group */
float querytimer; /* Timer for sending query for this group */
}grp_tab_node;
Host-side data structure
In igmphost, it needs to maintain only a group table, each entry of which is a group that host has interest in. The group of each entry is unique. If different applications join the same group, or a same application joins the same group one than one time, they send join message to igmphost each time they join. But igmphost need not insert the same group into its table more than once. However, it need to know how many times the group is been joined(with app_cnt), such that when all applications leave that group, igmphost is able to remove that group from the table.
Following is the structure of an entry in the igmphost group table:
typedef struct grp_tab_node{
IpT_Address grp_ip; /* Group IP address */
int app_cnt; /* How many applications in the host joining the group */
float rptimer; /* Timer for sending report */
int lastrp_flag; /* Whether the host send the last report for this group */
}grp_tab_node;
Application data structure
In igmp_app, it needs to maintain a group table, each entry of which is a group that application is joining. In this table, different entries may have the same group. We need to use this process model to simulate different applications which may join the same group at different time and stay joining with different length of time. Therefore, each entry represent a join to a group, and each entry has its own group living time which specify when the group be left for that join.
Following is the structure of an entry in the imgp_app group table:
typedef struct app_grp_node{
IpT_Address grp_ip; /* Group IP address */
float leave_time; /* Timer for leaving the group */
}app_grp_node;
Configurable parameters
For easy testing and flexibility, we made several parameters configurable in router or host models. All IGMP standard defined configurable parameters for toning IGMP performance are configurable in the router IGMP model. In host, there are several parameters configurable in igmp_app process model to tone application joining and leaving behavior. Refer attached README for more details.
How they work
How IGMP in router works
Igmprouter first initializes variables, registers the protocol, creates and advertises the igmp interface table. See Fig 5.
It then go into Startup_Query state to send general query startup_query_count times with interval startup_query_interval. Each time it runs, it searches the igmp interface table, sends general query for each interface on which it is a querier. This is invoked at the end of init state, and done in Startup_query state. This state schedule self interrupt to itself if the startup query times doesn’t reach the startup_query_count yet, otherwise, it schedule self interrupt to go into G_Query state.
G_Query state schedule self interrupt to itself regularly according to Query_Interval. This state will be regularly run after it is invoked by Startup_Query state. Each time it runs, it searches the igmp interface table, sends general query for each interface on which it is a querier.
If the router receives an igmp message whose dest_addr is 224.0.0.2, IP will forward it to igmprouter. Igmprouter processes the reception of packet in state REV_IP. All igmp messages have the same packet format, which specifies group, type (report, query, or leave), max response time (only valid in query). It also gets the interface from which the packet was received, and searches it in the igmp interface table.
If the message is a query from another router, and the router is a querier for that interface from which the packet was received, it compares the IP address of the source interface and that of its own interface. If the source interface’s address is lower than its own, it will resign the querier role, set the querier flag for that interface as false, and set the Other_q_present_interval timer for that interface.
If the message is a query from another router, and the router isn’t a querier for that interface from which the packet was received, it just refreshed the Other_q_present_interval timer for that interface. This means that the router keeps supervising the status of the querier, because once the Other_q_present_interval timer for that interface expires, the router assume the non-existence of the querier for that interface, so as to resume its querier role on the interface.
If the message is a leave for a certain group, it then searches the group on that interface. If not find it, just ignores the message. If find it, set waiting_squery and query_timer, and schedule self interrupt to invoke S_Query to send specific query for that group to that interface. Either this would solicit still remained group membership report from that interface, so as just refresh the membership in the router, or waiting_squery timer expires with no reports received, then the leave message is quite right for a last member on that interface, then that group would be removed from that interface.
If the message is a report from a host, it searches the group on that interface. If not find it, then the group is a new group, it insert it into the group table attached to that interface, and set the non report timer for it. If find it, it just refreshes the non report timer for the group.
S_Query state, as we know, is invoked by receiving an igmp leave for a group. When it gets run, it goes through the igmp interface table, searching for the group which should have specific query sent based on the waiting_squery and query_timer, and then send specific query for that group.
Leaving state is invoked by the self scheduled non report timer. When it gets run, it goes through the igmp interface table, searching for the group which haven’t receive report for . Then it removes the group from that interface.
How IGMP in host works
Igmphost first initializes variables, registers the protocol in init state. Then goes into idle state, waiting for packets from either IP layer or from application. See Fig 6.
APP_INF state is invoked by receiving a message from the application. This message specifies type (join, leave), group.
If the message is join, igmphost search for the group to be joined in the group table. If not find, igmphost insert this group into the group table, set app_cnt as 1 which means that there is one application joining it. In case this is the first join to the group on the subnet, it sends a unsolicited report immediately. To be safe, it will send a report again after Unsolicited_Report_interval. The way is sending a specific query for the group to itself(no other host or router will receive it), then host will goes into date_decap to response the query. If find the group in the table, just increment app_cnt by 1 which means that one more application joining the group.
If the message is leave, igmphost search for the group to be left in the group table. If not find, just ignore the message. If find, and app_cnt is larger than 1, just decrement app_cnt by 1 which means that one more application leaving the group. If app_cnt is 1, remove the group from the group table, if the last_report_flag is set which means the host sent report for the group for the last query, host will send a leave to the router.
data_decap state is invoked by receiving a message from IP. This is an igmp message. Its might be report, query or leave. Besides type, the message also specifies group and max response time(only valid in query).
Igmphost ignores leave message from other host.
If the message is a general query from the router, it goes through the group table, setting response timer with a random time less than max response time for each group. If the timer is already running, timer will be reset only when the remaining time is longer than the max response time specified in the query.
If the message is a specific query from the router, it searches the group in the group table. If it is in the table, host sets response timer with a random time less than max response time for that group. If the timer is already running, timer will be reset only when the remaining time is longer than the max response time specified in the query.
If the message is a report from another host, it searches the group in the group table. If it is in the table and there is response timer running for that group, host will cancel that timer to relieve traffic.
RESPON state is invoked by self scheduled response timer which is set in date_decap to response either a general query or a specific query. It goes through the group table, checks which group’s timer expires, and sends report for that group.
How application in host works
Igmp_app resides in all hosts. It is an application simulation. It randomly creates join to some group, and set leaving timer for that group. When join created, it sends a join message to igmphost. When leaving timer expires for some group, it sends a leave message to igmphost. It uses a list to maintain this information(joined group, leaving timer, etc.). See Fig 7.
Working as part of multicast simulation
Modification in IP
Original IP model is modified to host IGMP. See Fig 11.
For a host to receive multicast data packets, IP needs to forward these packets to higher layer (IP_ENCAP). Satisfying condition is that the dest_addr of the packet is a multicast address but not a reserved one, the packet is from lower layer, and gateway status is host. This modification is in IP model svc_compl state.
For a host to receive IGMP messages, IP in host needs to forward these messages to higher layer (IP_ENCAP). Satisfying condition is that the det_addr is IGMP reserved address, the packet is from lower layer, and the gateway status is host. This modification is in IP model svc_compl state.
For router to forward multicast data packets to its interested subnet, IP in router needs to forward these packets according to Mlocol table(I use IGMP interface table directly). For a multicast data packet, router searches the IGMP interface table. Router will forward the data packet to each interface which is interested in that group. This modification is in IP model svc_compl state.
Communication with PIM and Modification in PIM
As discussed above, IGMP is served as a part of a large multicast routing model. It provides the final step in a multicast packet delivery service since it is only concerned with the forwarding of multicast traffic from the local router to group members on directly-attached subnetworks. While it provides local membership information to multicast routing protocols, such as PIM in this project. See Fig 10.
Forwarding multicast data packets among routers is handled by PIM. PIM needs IGMP interface table to dynamically modify its own table for routing. Therefore, each time the IGMP interface table changed, igmprouter will notify PIM for the change. There are several methods of communicaiton between IGMP and PIM, according to the data structure. As IGMP and PIM utilize different information even for the same group membership, they employ different data structures to store the membership information. While, to save time for searching the difference, IGMP just sends to PIM model a message in which specify which interface changed, the group, join or leave. Then PIM can easily change its own routing table only upon the message received, without other efforts.
And therefore, PIM needs to process the reception of IGMP notification. This is a piece of code inserted into Message state in PIM model.
It took me quite some time to get familiar with the coding style and functions in opnet. Fortunately, I got much help from Xin Wang and from her code.
To test functionality of IGMP, I checked whether a host can receive a multicast data packet and print out the router interface table, host group table, and application table. Testing result shows that IGMP functions well. All testing results satisfy the following statements. If a group G is joined by the app in host H with n times, then the group G must be in the group table of igmphost H with app_cnt equaling n. If a group G is in the group table of igmphost in host H, then the group must be in correspondent interface tables of those routers which have broadcast interface attaching to the subnet. For each subnet, there is only one interface which is a querier and that interface has the lowest IP address.
With the coordination of IGMP and PIM_DM(developed by Ms. Xin Wang), hosts are able to receive multicast data packets properly. This includes the following situations.
When both multicast data packets sender for a certain group and the host interested in the group (receiver) are on the same subnet, the host can receive the packets properly.
When the sender and the receiver are on different subnets, connected by one or more routers, the receiver is still able to receive the packets properly, but perhaps with first a few packets lost because there is some delay for IGMP and PIM to establish new routing table.
Sometimes, there are groups in the router interface tables but they have been left by all hosts on that subnet. This is because igmprouter has some delay to remove the group from the table in order to make sure that no other host joins the group by sending specific query and waiting for the response.
As a package to be easily installed under OPNET, we wrapped all IGMP models, PIM models and correspondent modified models provided by Mil3, each under a directory, under a upper directory, which was gziped and tared. A sample env_db3.5 is also enclosed in the package. Refer README for more details on installation.
Coding and functionality testing for IGMP in OPNET has been finished. It restrictly follows the protocol. Functionality is fulfilled. The testing of IGMP as a part of the large simulation model has also been done.
IGMP README
To utilize the IGMP implementation enclosed in this package, follow the steps as showing below, supposing that OPNET3.5 along with models provided by Mil3 are installed and one has get license for using OPNET:
1. Copy all four directories and set paths for these directories in configuration file env_db3.5 (a sample env_db3.5 is provided, one can just modify correspondent paths according to where he copied them).
2. Modify correpondent Mil3 provided models' paths set in sample env_db3.5 according to user's specific installation of OPNET.
3. Run OPNET, under Network Editor, read in A1_cj_igmp_net. This is the network model on which IGMP developed and tested. And then, user can get into Node Editor and Process Editor to view detailed node models and process models developed.
4. Under Simulation Tool, read in A1_cj_igmp_net. This is the simulation file that simulates on above network. Press the excute button, OPNET simulates the running of the network model, in which IGMP, PIM and IP are all active.
To be flexible, we made several parameters to be configurable in models. Under router, there are following parameters that can be configured to tone IGMP performance (These are restrictly defined according to the IGMP standard as well as their names.):
--Other Querier Present Interval
--Query Interval
--Startup Query Count
--Startup Query Interval
--Query Responsce Interval
--Group Membership Interval
--Last Member Query Count
--Last Member Query Interval
--Max Response Time
Under host, there are some parameters in igmp_app that can be configured to tone the behavier of application:
--Max 2joins Interval ( Maximum interval between 2 joins)
--Max Group Living Interval ( Maximum time for staying intrested in
a group)
--First Group IP 3 Parts ( The first 24 digits of the group that is
joined at very first simulation, e.g. "239.255.0." )
--First Group IP Last Part ( The last 8 digits of the group that is
joined at very first simulation, e.g. "1". combined with above example,
the group that is joined at very first simulation is "239.255.0.1")
