ns3switch

Design and Implementation of Switch Module for NS-3 XIA Yu School of Info. Science & Tech. Southwest Jiaotong University Chengdu 610031, China rainsia@gmail.com ZENG Huaxin School of Info. Science & Tech. Southwest Jiaotong University Chengdu 610031, China huaxinzeng1@126.com SHEN Zhijun School of Info. Science & Tech. Southwest Jiaotong University Chengdu 610031, China shensljx@sina.com ABSTRACT In this paper, we first show the importance of switch module to NS-3. And then, we design a switch module for NS-3, to do so, some principles are first proposed. Based on these principles, an abstract switch module is designed and implemented for NS-3. By extending this abstract module, many specific switches using different switch architectures and arbitration or scheduling algorithms can be implemented. Two specific switches are implemented in this paper as examples. One is based on crossbar and uses iSLIP as its scheduling algorithm, the other is the CICB (Combined Input and Crosspoint Buffered) switch which uses the simplest round-robin as its input and output arbitration algorithm. Finally, several simulations are done, to verify the correctness of our switch module. By comparing the results to that within the original papers, we say that our designs and implementations are correct, and the switch module can be used for both the switch and network simulations. Then based on the switch module, some simulations are designed to show the network performance with different switches. Keywords switch module, NS-3, network simulation, traffic source 1. INTRODUCTION Packet switches/routers have been the key components that significantly affect network performance more than any other components. The performance analysis of packet switches is important to network design. However, the performance analysis fully based on mathematics is complicated, and is only feasible when traffic sources are simple and can be represented as stochastic processes. When the traffic source itself becomes complex, for example the self-similar traffic [1], the analysis becomes impossibly hard. Thus simulation plays a dominant role in this area. Some software kits are designed for packet switch simulations such as the famous SIM [2] by Stanford University. However, it is dedicated for crossbar switches with fixed-length packets, and can simulate only the switches in isolation. In most of the situations, we would like to put our switch into a real-world network topology and to evaluate its performance with the interacting between network components. Some researchers choose to write switch simulation modules with general purpose programming languages (such as C/C++ and Java) from scratch, it is free to choose switch architectures, but the above mentioned drawbacks still exist and are even worse. NS-2 [3] is a well-developed network simulator. It is widely used by the academia and industry in the past decade. It has been one of the most successful open- source projects in the past ten years. NS-3 [4] is designed to replace NS-2 with its elegantly designed architecture and many easy-to-use features. Both NS-2 and NS-3 can conveniently build network simulations which have complex network topologies and environments. Unfortunately, neither NS-2 nor NS-3 has a build- in switch module. The forwarding node of NS-2/3, by default, is equal to an Output-Queued (OQ) packet switch which is proven to be not implementable in modern high-speed network environment because of the low access rate of commercial static memories [5]. For the above reasons, we designed a packet switch module for NS-3. For switch designers, their switch structures can be involved into a more real network environment to test the performance with many complicated traffic models or even real traffic traces. For network designers, instead of using OQ switches, more concrete switch architectures can be used to estimate the performance of the networks, which makes the results more accurate and more reliable. The rest of this paper is organized as follows: Section 2 analyses the pros and cons of the main stream packet switch simulation methods and why do we need a switch module in NS-3. In Section 3 we first design a generic switch model, and then implement, as examples, two specific switches based on this generic module. Section 4 describes how to integrate our switch module into the forwarding node of NS-3 so that it can be placed into a network topology. Several simulations are done in Section 5 to verify our designs and implementations and to demonstrate the use of switch module in network scenarios. Section 6 concludes this paper. 2. THE NEED OF SWITCH MODULE There are mainly three ways to simulate packet switches: 1) To use a switch simulation software kit; 2) To build a simulation module with general purpose programming languages; 3) To use existing network simulators. The advantages of the first method are obvious, both the underlying code of the simulation architecture, switch architectures and some simple traffic models are already implemented, the users only need to add their own algorithms and configurations to complete a simulation. But most of these Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. NSTools 2009, October, 19th 2009 - Pisa, Italy. Copyright 2009 ICST 978-963-9799-70-7/00/0004 $5.00 Digital Object Identifier: 10.4108/ICST.VALUETOOLS2009.7658 http://dx.doi.org/10.4108/ICST.VALUETOOLS2009.7658 software kits only provide the ability to simulate a single node switch. Furthermore, they are usually independent of protocol stacks and the states of the networks. The second method allows users to freely choose switch architectures and traffic models as they want. However, there are a lot of things to care about: simulation architecture, statistics collecting framework, switch architectures, scheduling algorithms, traffic generating, and so on. It is time-consuming to implement all of these, and hard to make sure that they are correctly coded. There are a lot of network simulators, such as NS-2/3 and OPNET [6], which provide advanced simulation architectures. With these simulators, users can build complicated network topologies conveniently as they want, use existing traffic generating modules or even import the real traffic traces. Future more, some of them also provide easy-to-use statistics collection and analysis frameworks. Some projects are done to add switch simulation functions to network simulators, such as in reference [7], but those works are not able to seamlessly integrate packet switches into network topologies and take full advantage of the existing protocol stacks, routing algorithms and other useful components of the simulators. The forwarding node in NS-2/3, by default, is equal to an OQ switch, which is not commonly used in current network design. And as we can see later by simulation, the performance of OQ switch is quite different from that of other popular switches. So a generic packet switch framework with some popular packet switches is needed in NS-3 not only for the switch designers but also for the network designers. Switch designers can extend our framework to provide more switch architectures and scheduling algorithms, and then test the new architectures or algorithms in a real network environment including network traffic, protocol stacks, routing algorithms and the interactions between each node. Network designers can seamlessly integrate appropriate switches into their network topology instead of just using OQ switch, since OQ switch shows the best performance, which is very different from other switch architecture, especially when the AQM (Active Queue Management) and congestion control mechanisms are involved. So if more realistic switches are used to estimate the performance of the networks, the results should be more accurate and reliable. As the very reasons, we design a switch module for NS-3, which will make NS-3 more suitable for either switch simulation or network simulation. 3. GENERIC SWITCH MODULE FOR NS-3 3.1 The Principles of Adding New Modules Before we start designing our switch module, we should first describe our principles of adding new modules into NS-3. First, we should never modify existing code of NS-3. If we want to extend any functionality of NS-3, we always choose to add new code. There are two obvious benefits of this principle: the extension can be easily migrated to a new version of NS-3 by simply copying the new code to that new version; other existing modules or especially the third-party modules which depend on some of the modules we want to change will not fail. Second, for any module, we first design a highly abstract super class, and then extend it by inhering to add new functions into the sub classes. Thus, other people can extend our module to implement their own functions in a much easier way. Finally, for some common modules, such as traffic sources, we want them to be highly reusable. In ordinary, traffic modules are coupled with applications, which means we cannot reuse them between different applications. To avoid these modules becoming application dependent, we have tried to separate core functions from those application-related modules to make them reusable for any other applications. 3.2 Generic Packet Switch An packet switch, as shown in Figure 1, has input units and output units. The input ports and output ports have the same data rate, and are interconnected by the switch fabric. The switch fabric usually processes fixed-length packets (called cells). For packets with variable-length, an ISM (Input Segmentation Module) in Input Unit should segment them into fixed-length cells. In an output unit of the switch, cells belonging to the same packet are reassembled by an ORM (Output Reassembly Module) before they are sent out. The switch fabric may transfer cells faster than the data rate of input ports. In this case, we say that the switch fabric has a speedup. The time slot is defined as the time used to receive a cell from an input port. With a speedup ratio “1” (i.e. without speedup), only one packet may arrive at an output unit every time slot, so queuing is only needed at the input side, this kind of switches are called Input-Queued (IQ) switches. When the speedup ratio is greater than 1 and less than N, there might be more than one cell arriving at an output port every time slot, so packets may need to be queued at both IP IQ Switch Fabric OQ OP A rriv a l P ro c e ss e s D e p a rtu re P ro c e s s e s ISM ORM IP: Input Port ISM: Input Segmentation Module IQ: Input Queue OQ: Output Queue ORM: Output Reassembly Module OP: Output Port Figure 1. A generic concept model of the packet switch Digital Object Identifier: 10.4108/ICST.VALUETOOLS2009.7658 http://dx.doi.org/10.4108/ICST.VALUETOOLS2009.7658 input and output sides. We call these switches Combined Input and Output Queued (CIOQ) switches. When the speedup ratio is equal to N, each packet can be forwarded to the corresponding output unit as soon as it arrives. Consequently, input queuing is unnecessary while output queuing is needed, and in this case, the switch is called Output Queued (OQ) switch. According to our principle, we should first design an abstract class for the generic switch. The class diagramÈ which specifies the roles of the switch,in a network is shown in Figure 2. A brief description of the members in AbstractSwitch class is shown in Table 1.�� Table 1. Description of members of the AbstractSwitch class m_ports The number of ports of a switch. m_port_rate The data rate of each input/output port. m_cell_size The cell size processed by the switch, Note that: timeslot=m_cell_size/m_port_rate m_send_callback_list A list of callback, the callbacks will be invoked when there is a packet being transmitted. Initialize() Initialize the switch parameters. StartSwitch() Start the switch. StopSwitch() Stop the switch. RegisterSendCallback() Add a send callback to the list. UnregisterSendCallback( ) Remove a send callback from the list. PacketArrive() Pure abstract method. Is called when there is a packet arriving at any input port. DoDispose() Used to clear up when destroying. SechduleArbitrate() Schedule a call to Arbitrate() every time slot. Arbitrate() Call DoArbitrate() to run arbitration algorithm and ScheduleArbitrate() to schedule a call to itself next time slot. DoArbitrate() Pure abstract method. Will be implemented by its subclasses to provide various arbitration algorithms. Send() Send packet out from an output port. 3.3 Implementation of Two Specific Switches Based on AbstractSwitch we can design and implement many different switch architectures and the corresponding scheduling algorithms. In this subsection, we are going to design and implement two different switch architectures: one is the most widely used crossbar switch, and the other is the most promising Combined Input and Crosspoint Buffered (CICB) switch. 3.3.1 Crossbar Switch The crossbar switch architecture is the most widely used switch architecture. In such a switch, the switch fabric is crossbar, which connects input ports and output ports and is able to provide parallel connections in the same time slot. By suffering from the HoL (Head-of-Line) blocking problem, the switch has very poor performance, until VOQ (Virtual Output Queue) is introduced [8]. With VOQ, each input port maintains a separate logical queue for each output port, the cells from the same input port and destined to different output ports are enqueued into different VOQs. A concept model of the VOQ/Crossbar switch is illustrated in Figure 3. With VOQ, within a time slot, each input port has at most cells Figure 2. Class diagram of Abstract Switch IP VOQ Crossbar OP A rriv a l P ro c e s s e s D e p a rtu re P ro c e s s e s Figure 3. The concept model of the VOQ/Crossbar switch Figure 4. Class diagram of VOQCrossbarSwitch Digital Object Identifier: 10.4108/ICST.VALUETOOLS2009.7658 http://dx.doi.org/10.4108/ICST.VALUETOOLS2009.7658 waiting to be sent, and each output port also has at most cells are destined for it. Thus additional scheduling algorithms are needed to solve the contention at the input ports and output ports. The design of high-performance scheduling algorithm for VOQ/Crossbar was once and continues to be a hot topic of switch design. Many famous algorithms have been proposed such as PIM (Parallel Iterative Matching) [9], RRM (Round-Robin Matching), SLIP [10], DRRM (Dual Round-Robin Matching) [11], etc. These algorithms are all consist of two or three steps, namely request, grant and accept (DRRM do not need an accept step). In order to find a maximal matching, most algorithms need to run for several iterations [12]. VOQCrossbarSwitch, whose class diagram is shown in Figure 4, is designed to represent a crossbar switch with VOQs as its input side queuing, and it is a subclass of AbstractSwitch. VOQCrossbarSwitch add some member variables and member functions to its base class, which are described in Table 2. Table 2 Description of members of the VOQCrossbarSwitch class Note that VOQCrossbarSwitch is still an abstract class since no scheduling algorithms are defined. Scheduling algorithms can be added by inheriting, for example SLIPSwitch and DRRMSwitch can be implemented by overriding the methods Request(), Grant() and Accept(). 3.3.2 Buffered Crossbar Switch As the transmission rate becomes higher and higher and the cell length is unlikely to change, the time slot becomes shorter and shorter. The time needed for running complicated scheduling algorithms becomes very tight especially for iterative scheduling algorithms. The VOQ/Crossbar switch architecture is no longer a suitable choice for modern high-speed switches. Once, the buffered crossbar switch was considered to be the solution for high-speed switches since it can fully emulate an OQ switch. However, under current VLSI technology, only a small number of memories can be embedded into a crossbar, which are not enough to buffer all the incoming packets. Later, Combined Input and Crosspoint Buffered (CICB) switch architecture is proposed [13], and is proven to have very good performance, especially when the input side adopts VOQs. Only a very simple scheduling algorithm is need for a VOQ/CICB switch to achieve an average delay similar to that of an OQ switch [14]. An abstract class VOQCICBSwitch, which is a subclass of AbstractSwitch, is designed to represent VOQ/CICB switch. Its class diagram is shown in Figure 5, and the description of its members is in Table 3. Table 3. Description of members of the VOQCICBSwitch class m_voq_list A list of VOQs. m_crosspoint A matrix of crosspoint buffers. m_eligible_input Indicates which crosspoint buffers are not full, and the corresponding input ports can send packets to them. m_eligible_output Indicates which crosspoint buffers are not empty, so that they can send packets to idle output ports. m_output_pointer Which crosspoint is chosen for each output port at the previous time slot. m_input_pointer Which crosspoint is chosen for each input port at the previous time slot. InputArbitrate() Pure abstract method. The scheduling algorithm for each input port. OutputArbitrate() Pure abstract method. The scheduling algorithm for each output port. A lot of algorithms are proposed for input and output side. The simplest one is Round-Robin, which is shown to have very good performance especially under uniform traffic [15]. For each algorithm, we only need to inherit the VOQCICBSwitch class and override InputArbitrate() and OutputArbitrate() methods. For example, we can implement a class called CICB_1_RR_RRSwitch, which means the switch can hold only Figure 5. Class diagram of VOQ/CICB Switch m_voq_list A list of virtual output queues. m_iteration How many iterations have been invoked. m_request The request matrix. m_grant The grant matrix m_accept_array The accept array. m_output_matching The input-output matching. m_grant_pointer A list of the grant pointer for each output port [10]. m_accept_pointer A list of the accept pointer for each input port [10]. PacketArrive() When a packet arrives from some input port, its destination port is retrieved, and then it is enqueued into the corresponding VOQ at that input port. DoArbitrate() Call the following four methods. Request() Pure abstract method. To send requests to each output port. Grant() Pure abstract method. To grant the requests of input ports. Accept() Pure abstract method. To accept the grants from output ports. Forward() Send the corresponding packets of matched input ports to related output ports. Digital Object Identifier: 10.4108/ICST.VALUETOOLS2009.7658 http://dx.doi.org/10.4108/ICST.VALUETOOLS2009.7658 one cell at each crosspoint and use Round-Robin as its input and output arbitration algorithm. 4. INTEGRATING SWITCH MODULE INTO FORWARDING NODE