The Design of the USC PIM Simulator (pimsim)
Contents
1. refreshes the joins e Mcast_trfc_timer_expire Processes expired timers for this receiver 8 of 10 The Design of the USC PIM Simulator pimsim Implementation Details 3 3 2 3 3 3 3 3 4 3 3 5 3 4 pim_processing Pim_processing processes all incoming PIM routing messages It consists of a big switch based on the packet type and calls one of the following packet processing func tions pim_join_prune_processing pim_rcv_register pim_rp_reachable_proess ing and pim_rcv_query pim_refresh pim_refreshQ periodically calculates the join prune messages and send them toward the right neighbor nodes It first calculates the number of entries relevant to each interface then reserve the memory space for each interface It constructs the join prune blocks for each multicast group Then all packets are sent out to the respective interface Note that for a multi access LAN with more than 2 nodes attached the pim refresh may need to construct a distinct PIM join prune packet for each of the other attached node As an optimization all PIM join prune packets destined to different next hop nodes on a LAN are chained together and sent to the multi access LAN with one event after all they were generated at the same time Another PIM_REFRESH event is scheduled in the end pim_periodic_query pim_periodic_query periodically sends PIM query message out all interfaces When a PIM module receives a PIM query2. a PIM routing module attached All arriving PIM mesages are processed by this module It updates the corresponding multicast rout ing entries and computes generates PIM messages to its neighbors periodically or on event triggered basis There is a data structure Pimt type associated with each PIM router It contains the uni cast routing table multicast routing table and local topology table in addition to other configuration information Please refer to the comments in the header files under the include directory for further details of the PIM router and multicast routing table data structure Multicast source and multicast receiver The multicast source module and multicast receiver module must be attached to a node component instead of a link component Each multicast source generates PIM register messages and directly sends them to the RP Each multicast sink generates periodically JOIN messages and sends them to its attached node component Each multicast receiver can be configured to either stay on the RP tree or switch to the SPT when data packets from new sources have been received When the SPT flag is set 1 RP see section 2 6 for RP actions 4 of 10 The Design of the USC PIM Simulator pimsim Simulating Components of a Network Please refer to the demo file for the syntax of configuration statements To begin simu lation middle click the START button on the righthand side of the window The si
3. message it will mark the interface which it received the message as a NON_LEAF network If a router hasn t heard a PIM query message from an interface for 3 query intervals it sets that interface to LEAF status If a pim module is configured as dead or changed to the status of dead during the simulation it will stop generating the periodic query messages pim_timer_expire It processes all timer expiration event related to a particular PIM routing module instance The timer types include oif timer RP_REACHABLE timer and SOURCE timer All of the above functions subsection 3 3 1 3 3 5 are called from the pim_action routine Node The node component is based on the node component supplied with the MaRS package The node module in pimsim has the following changes e The nd_reset routine for pimsim also puts the attached multicast receivers and multicast senders in its local topology table e The node component has counters that count the numbers of multicast data packets sent and number of data packets dropped o It marks the prev_comp field with its own address in a packet so that the link knows who sent this packet e Ifthe packet is a multicast data packet the node would lookup the multicast routing table If an entry is found it would forward according to its oif list If there is no entry found and all interfaces are sparse mode configured the incoming packet is The Design of the USC PIM Simulator
4. pimsim 7 of 10 Implementation Details 3 1 3 2 3 3 3 3 1 The maximum number of nodes supported by PIMSIM can be increased or decreased by changing the value of MAX_NO_OF_NODES include route h file current default to 25 The default maximum number of links attached to a node is 10 This can be changed by editting the value of MAX_LINKS_PER_NODE in include component h The initialization of the global topology table After finishing loading the configuration file the smulator would initialize the adjan cency matrix adjancency matrix_structure_name and calculate the all pair shortest pathes for the network The structure of the adjancency matrix Installation of the local topology table Packets The simulator recognizes two packet types multicast data packet and PIM routing pack ets These packet types are defined in a MaRS compatible way For PIM join prune messages the variable length address blocks which contain the join prune lists are stored in the packet payload area i e in the area pointed to by field tail A new Packet field tailsize is added to indicate the size of the variable join prune address list For all packets the pk_prev_comp field points to the last component that sent this packet This field is used by the multi access link component A multi access link would produce a duplicate copy of the packet for all attached nodes except the previous one which generated this packet Other pa
5. References 2 D Estrin S Deering Dino Farinacci Van Jacobson Ching gung Liu and Liming Wei Protocol Independent Multicast PIM Protocol Specification working draft Oct 1994 3 C Alaettinoglu A U Shankar K Dussa Zieger and I Mata Design and Implemen tation of MaRS A Routing Testbed Technical Report CS TR 2964 Department of Computer Science University of Maryland Sept 1992 3 C Alaettinoglu K Dussa Zieger I Matta A U Shankar MaRS Maryland Routing Simulator Version 1 0 User s Manual Technical Report CS TR 2687 Department of Computer Science University of Maryland June 1991 4 C Alaettinoglu K Dussa Zieger I Matta O Gudmundsson and A U Shankar MaRS Maryland Routing Simulator Version 1 0 Programmer s Manual Techni cal Report CS TR 2723 Department of Computer Science University of Maryland July 1991 10 of 10 The Design of the USC PIM Simulator pimsim The implementation status 4 0 The implementation status 5 0 The current simulator has implemented almost all PIM protocol mechanisms At this moment there are still two protocol related areas needing updates 1 2 Dense mode outgoing interface state handling The current simulator only simulates two states of an outgoing interface for dense mode pruned or in oif list An inter face is added to the outgoing interface list when the first data packet is flooded and remains there u
6. access link it will only check one packet queue for packets For a point to point link still use standard MaRS stuff e link_receive needs to deal with multi access LANs and the chained PIM packets for different receivers Multicast Source A source component has to be attached to a node component The Mcast_source_ac tion routine contains all standard MaRS functions plus the following PIM functions e Mcast_set_rp sets the RP address for this source e Mcast_produce_register generates PIM register messages toward the RP e Mcast_src_receive receives any PIM messages e g PIM registor stop e Mcast_refresh handles PIM register refreshes e Mcast_trfc_timer_expire processes all timer expirations of the multicast source component Multicast Receiver A multicast receiver component also has to be attached to a node component It is implementated and treated as if it is just another interface of the node it will appear as an oif in the proper multicast routing table entry and packets will be forwarded to it The difference from a real interface or link is that it terminates all packets received The Mcast_sink_action routine contains the following PIM functions e Mcast_set_rpQ e Mcast_produce_join produces PIM G join messages If this receiver has it SPT bit flag set it will switch to SPT when it receives a data packet e Mcast_receive receives RP reachable message discards it e Mcast_refreshQ
7. cket types such as MTRACE_REQUEST and MTRACE_RESPONSE are defined in the packet h file for reference and to facilitate extensions They are not recog nized by any modules in pimsim now PIM routing module Pimt The pim routing module consists of the common MaRS functions and following mainly PIM related C funtions pim_start pim_processing pim_refresh pim_periodic_ query and pim_timer_expire pim_start Pim_start initializes the particular PIM instance and its multicast routing table plus various counters It initializes its cache about all interfaces to LEAF status and each such interface would remain in the leaf network status until a PIM query is heard from 1t Pim_start also initiates the periodic PIM_REFRESH L and PIM_SEND_QUERY events 1 This makes the code simple to understand and with very little more overhead To avoid starting the PIM_REFRESH event here we can do it when the first new multicast routing entry is estab lished 6 of 10 The Design of the USC PIM Simulator pimsim Implementation Details 2 6 2 7 2 8 3 0 in the receiver configuration the receiver will send S G joins in response to new data packets Rendezvous Point RP As stated in the PIM protocol specification any PIM router in the simulated network can act as an RP It does not need any prior configuration Multicast Data Packets Multicast data packets are sent from the multicast source components an
8. d are only pro cessed by the node components It is used to simulate the data driven events such as RP tree to SPT switch dense mode flood and prune resolution of duplicate packets and routing loops over multiaccess LANs PIM protocol routing packets Look at the packet h file for the list of all relevant message types Currently it recog nizes the following PIM message types corresponding to code values in the spec e PIM_QUERY e PIM_REGISTER e PIM_REGISTER_STOP e PIM_JOIN_PRUN E e PIM_RP_REACHABLE e PIM_ASSERT e PIM_GRAFT e PIM_GRAFT_ACK Each time a PIM join prune message is generated it is assumed that the message size can be arbitrarily large only one packet is generated for arbitrarily many groups and source RP addresses Implementation Details This section describes in more detail the operations of each component and how the simulator initializes the important data structures and how components interact with each other Pimsim keeps one copy of the global topology table the adjancency and shortest path matrix All local topology tables are filled in when the simulator is started Two standard routines rpf_inf and rpf_nnd are provided to calculate the reverse shortest path next hop interface and next hop node PIM routing modules Multicast sources and sinks all have the standard portions of MaRS parameters The Design of the USC PIM Simulator pimsim 5 of 10 Simulating Componen
9. imulator is an integrated Sparse Mode and Dense Mode PIM 1 2 sim ulator It simulates the detailed protocol actions over both point to point and multi access networks All links can be configured as dense mode or sparse mode It is based on the MaRS Maryland Routing Simulator package which provides a nice X based user interface and an efficient event queue handler The topology and components of the network can be displayed graphically on screen The status of various parts of the net work can be examined by middle clicking the components or other appropriate places This document only deals with the PIM simulation related parts For more details about the user interface and the event driven simulator engine please see the MaRS architec ture 3 and user documents 4 The PIM simulator package can be obtained via anonymous ftp on catarina usc edu pub lwei pimsim tar gz MaRS is available from ftp cs umd edu MaRS It is recom manded that the machine running this simulator have at least 24Mbytes of memory Starting the Simulator The tar file has an executable file pim for the sun4 architecture and a sample configu ration file demo under subdirectory etc for a 14 node network To sun the simulator with the sample configuration type the following pim etc demo To see all available command line options type pim h on the command line Once the simulator is started it should pop up a window showing the sa
10. mple 14 node network and a column of control buttons with a clock on the right handside The sample network topology is shown in figure 1 1 of 10
11. mu lation can be paused by middle clicking the CONTINUES button which changes the simulator into EVENT STEP mode To inspect the status parameters of a component middle click that component Figure 2 shows a simulator window displaying status for multicast router pim4 Middle clicking the left most box in the row labelled Multi cast Routing Table will bring up another window showing the multicast routing table entries in pim4 See figure 3 FIGURE 3 Middle clicking the left most box on Multicast Routing Table shows the multicast routing table Sor 27 o ikea 2 1k2 4250190 Ik4 19t40167 2 Hrouter State ALIVE IEADCOA 0 Global topology table Local topology table 2 0 Simulating Components of a Network This section describes all components entities that are simulated by pimsim and their functional behaviors in the simulator The simulated components include node link PIM routing module Multicast source and multicast receiver The Design of the USC PIM Simulator pimsim 3 of 10 Starting the Simulator FIGURE 1 Sample Network topologies file demo and components FIGURE 2 Status display of PIM router pim4 2 of 10 The Design of the USC PIM Simulator pimsim January 28 1995 1 0 The Design of the USC PIM Simulator pimsim Liming Wei A user s guide and a document about the Implementation of the simulator The USC PIM s
12. ntil either 1 it is pruned off and turns into pruned state or 2 the whole entry is timed out after data pakcets stopped arriving Since the specification also specifies that an outgoing interface in the oif list can be timed out when there is no data traffic and each interface can potentially have differ ent timers due to the scalable timer mechanisms each outgoing interface in the oif list may be timed out at a different time Hence in a dense mode entry an interface may be in one of the following 3 states Pruned in oif list Timed out A pruned interface will time out and change to in oif list state an interface in the oif list will time out when there is no data packets being forwarded for a certain period of time Iam waiting for this part of the specification to stablize before changing the bi state oif into tri state oif for dense mode groups We will also update the rules used for asserts on multiaccess LANs The following is a tentative list of functionalities to be added to a future pimsim release 3 Dynamic change of network topology Add the instruments to allow modification of topology on the fly This involves a rewriting of the global topology table b recompute the unicast routing table for all nodes c maintenance of existing net work states GUI based pause action based on user specified events It was projected that most pimsim users would be programmers this function is now performed in a C deb
13. ts of a Network 2 1 2 2 2 3 2 4 2 5 Unicast routing Since PIM is independent of unicast routing protocols and only uses the shortest path information from the unicast routing table no unicast routing protocol is simulated The unicast routing table is precomputed at simulation startup time and statically installed When simulating topology changes the simulator directly recomputes the global rout ing table and recalculates unicast routing tables on all nodes Subsequent PIM protocol actions will get the new unicast routes Node A node stores and forwards packets according to its unicast routing table When a proto col control message is received it is immediately passed to its attached PIM routing module When data packet is received on a node with DM links interfaces the packet is fowarded according to the multicast routing entry if there exists one or it will be flooded by the node component and correct protocol state will be installed Link A link can be point to point type or multi access type For example Ik1 3 in figure 1 is a point 2 point type link but Ik7 10 is a multi access type link When a packet both control and data is sent to a multi access LAN it is duplicated in the link compo nent and delivered to all nodes attached to the link component A link can also be con figured as sparse mode SM or dense mode DM PIM routing module Each node inside the network must have
14. ug ger such as gdb or dbx Automatic loop detection instruments This involves addition of mechanisms to keep the state for all data packets passing by and to recognize a packet going through the same interface twice or more times Acknowledgment 6 0 The author would like to thank the authors of MaRS for providing such a useful routing test bed and Deborah Estrin Lee Breslau for their helpful suggestions and comments References 1 D Estrin S Deering Dino Farinacci Van Jacobson Ching gung Liu and Liming Wei Protocol Independent Multicast PIM Motivation and Architecture working draft Oct 1994 The Design of the USC PIM Simulator pimsim 9 of 10 Implementation Details 3 5 3 6 3 7 silently dropped However if any interface is dense mode configured it call the dm_pim_data_action function to flood the packet according to the dense mode specifications The SPT flag handling when doing RPT to SPT switch is also done here Link The link component is based on that supplied with the MaRS package The link compo nent in pimsim differs in the following e It has anew type parameter link_subtype which can be point to point or multi access e link_start would not reject the setup of more than 2 attachment points for a multi access link e It has anew mode parameter smdm_mode which can take the value of either Sparse mode or Dense mode e In link_sendO if it is a multi
Download Pdf Manuals
Related Search