Acknowledgments

1. Introduction

In worldwide demand about computer network such like Internet. Routing protocols plays the core role in the whole network control system. Which are responsible for choosing the best way for delivering data packets in conjunction with performance in term of delay, throughput, etc. The performance of a route changes with the difference of network traffic condition (for example, the amount of the data flow through the links), so the routing algorithm should consider those facts and adapt the information store in the route. The routing algorithms implemented in this project, SPF and AntNet are both Next-hop routing. Each node maintains for each destination a neighbor node id (next-hop). Each data packet stores information about destination node id. When a node receives a packet it forwards the packet to destination node. But how to choose an optimal path to forward the packet is the key point to evaluate the routing algorithm. To achieve this, next-hop routing do the following functions: (1) each node keeps a topology table for its outgoing links, a dynamic link cost is updated regularly according to the traffic flowing through the link. (2) link cost information is spread regularly to nodes of the network; (3) each node update topology table regularly based on the link cost information. The testbed built is called CuRS, which is developed as a modified and extended version of MaRS.

AntNet, the adaptive and distributed routing algorithm we evaluated in this project is a mobile agent-based, online Monte Carlo technique which takes inspiration from real ants' behavior in finding the shortest paths using magic chemical substance deposited by other ants, and this technique been applied to optimization problems. The amazing routing algorithm, AntNet is using a set of concurrent distributed agents to collect information and update the previous information to create a more optimal solution for the adaptive routing problem while agents exploring the network. We compare AntNet with SPF algorithm using the CuRS (Carleton University Routing Simulator) as testbed to evaluate. AntNet shows the better performance.

2. Design and Implementation of the Simulator

2.1 Features and Implementation Considerations

The dynamics of the network is very complex. A testbed is essential to understanding the complex dynamics of routing systems. Ideally, we would like the testbed to accurately model features that are important to routing performance. However, it is not clear which features are important for routing performance. So CuRS still keeps the capabilities of the MaRS by having easily extendible modules to represent these features.

1. The testbed should be modular. That is, adding new routing algorithms or new kinds of workload nodes, links should be easy. Such additions require programming.
2. It is easy for user to build kinds of network topologies and define different workload distributions without programming.
3. The user can specify kinds of topology changes such like be able to fail and repair a link at a specified time and see if and how it affect the system and how the system converges to a new steady state.
4. It provides standard performance measures such as average delay, average throughput, average load, and so on. It also has average and instantaneous versions of these measures.

CuRS is a discrete-event simulator. The target system is characterized by discrete states and by state transitions (events) occurring at discrete time instants. For every class events, there is a corresponding eventListener. When an event fires, the corresponding method of the associated eventListener is called. Which updates the system state and cause other event occur. Discrete-event simulation is more flexible than other simulation (for example process emulation), so it can offer the greatest flexibility in modeling the target system. After checking the available discrete-event simulator MaRS for a while, I found MaRS is suitable for the purposes of my project. So I consider to develop my Java simulator based on the MaRS-Version 1.0 (C language), and extend to include AntNet.

2.2 Structure of CuRS

CuRS has the same structure as MaRS: a simulation engine, user interface (GUI, command line options and files), and a set of components that simulate physical network, workload, and transport protocols. But current version of CuRS is implemented GUI.

The simulation engine manages the event list and user interface. (GUI is not implemented in this project). When the CuRS starts, the simulation engine processes command line options (including reading any files), and then goes into the simulator loop. If GUI was added in the future, the simulation engine will process inputs from the keyboard and mouse, execute the next event from the event list, and update the graphical user display.

I use Observer/Observable design pattern (which is Object Oriented design) to design this testbed. I let Event as Observable which maintains an eventListener instance variable. There are four kinds of eventListener, all of then are Observers. All Observer objects watch the Observable object. If the specific event is fired, the associated Observer object's related method will be called. There are four different classes of event occurring in the CuRS: command type events EV_CLASS_CMD, event type events EV_CLASS_EVENT, private type events EV_CLASS_PRIVATE, and record type events EV_CLASS_RECORD. I defined an Event class as an Abstract class, which has enqueueEvent(int type, Component src,Component dest,long time,Packet pkt,Object arg) method to create a new event and places it in the event queue to be fired at the proper time. And also has fire () method. The four classes events are four concrete classes, and each of them has its own eventListener and its fire() method which invokes the eventListener's specific method depending on what kind of event type it is.

All CuRS objects have to react to the command class events. These events establish the basic operations of the simulator and execute in the simulator engine. Event class events are defined globally in a central location. Sending of a packet from a node to a link is kind of event type event. Private class events are only defined internally within an object, and they are called within that component. Record class events are used to record events in a record file. Each class event has different types of events. For specific meaning of each type of event, the reader can find them in the programmer or user's manual of MaRS-Version 1.0.

Figure 1: the relationship between Events and EventLsiteners

Figure 2: the relationship between EventLsiteners and Component

Figure 3: The relationship between Components

The components are used for modeling the target system and certain simulation functions. Each component is object which has its states and behaviors. In MaRS every component has its action routine associated with different events specified in the MaRS version 1.0. When an event occurs, each component's action routine is invoked for that event. Actually it uses function point in C to achieve this. While there is not function point available In Java. So in CuRS I use Observer/Observable Pattern to achieve this. Figure 1, 2, 3 shows the relationship of components Diagrams. Component was designed as Interface to represent all components in the target system. Such as Node, Link, LinkCostFunction component, Routing component, Workload component (FTP) and performance monitor. Component Interface extends four kinds of EventListener Interface which has different methods for different types events and also has association with one of four classes' event. Every concrete component implements its associated methods to override the methods defined in the AbstractComponent. Each component is an Object. The target system consists of a set of objects. By interconnecting multiple objects of various types of components, a target system of arbitrary topology, routing protocol, and workload can be obtained.

The components schedule events for each other. Also, a component can schedule an event for itself. The time of this event to happen depends on the link propagation delay. Each component has methods to update system state and may schedule other events depending on the type of the event received by the component.

Figure 4: The example network

Figure 4 shows a target system of seven nodes and eight links objects. Each link is connected to exactly two nodes. A node models the physical aspects of a store and forward entity such as a host or a switch. Each node is connected to an SPF routing algorithm and zero or more workload components. Each workload component is either a source or a sink of FTP. For each source object, there is a corresponding "peer" sink object. There is one link-cost function object which is not connected to any one.

I briefly describe each type of object in the following.

Link

A link object models a bidirectional transmission channel between two node objects. I use the same data structure to implement Link class as Link Component in the MaRS. Each link object contains two LinkedLists of packets, each representing the packets in the transit in one direction. A link can be subject to failure and fails. When a link fails, all packets that are in transit are lost.

The input parameters of link are Propagation delay[microseconds], Bandwidth [bytes/second], Distribution of interfailure times, Distribution of repair times; The output parameters are Link status(up/down), Instantaneous workload utilization for each direction, Instantaneous routing utilization for each direction. Link cost function

The link cost function is used to maintain and periodically update a cost for each link in the network. When the cost is updated, the link cost value is calculated by applying a transformation to a statistic cost "raw cost" which is obtained on the link during the previous update period. Hop-count, utilization, delay, and hop-normalized delay are the row cost supported by CuRS.

There should be only one LCostFcn object. So I use Singleton pattern to ensure only one instance of Link cost function exist in the target system. There is a static variable costFcn and a static method named "getCostFcn()" in the LcostFcn.java. Link cost function is not a part of the network so do not connect it to a component in the network. If an interaction is needed between link cost function and components, link cost function object obtained from LcostFcn.getCostFcn ()".

Routing

I define Routet as abstract class to represent the common things of each routing algorithm; Routet is also a kind of component. Every specific routing object is the concrete class of Routet and executes a routing algorithm. At each node, the attached routing object builds and maintains a routing table, which specifies a next-hop for each destination. The routing object exchanges information by routing packets, more precisely, a routing object passes a routing packet to its local node, which then sends it to a neighboring node, which then passes it to its local routing object. In the current version, I just implemented two types of routing components corresponding to two routing algorithms: SPF and AntNet.

The input parameters of SPF are Mean and standard deviation of topology broadcast period [milliseconds]; The output parameters are Global topology table (adjacency matrix), local topology table, and Routing table.

Workload

The workload component model the user traffic in the target system. In each workload source-sink pair, the source component produces workload packets and passes them to its node component. These packets are then forwarded by the node components until they reach their destination node, where they are consumed by the sink component. Input parameters of FTP_Source and FTP_Sink are Initial source-sink status (on/off), Number of connections between the specified FTP_Source and FTP_Sink, Average number of packets per connection, Packet length [bytes], Average delay between connections [milliseconds], Delay between packets [milliseconds], Produce window size [packets], Send window size [packets]; The output parameters are Source-sink status(on/off), Number of the current connection, Number of packets in the current connection, Number of the current packet in the current connection, Number of packets produced, Number of packets sent, Number of packets acknowledged, Number of packets received, Number of packets retransmitted, Roundtrip time estimate [microseconds], Instantaneous sent rate, Instantaneous acked rate, Instantaneous retransmission rate, Instantaneous delay per packet [milliseconds].

Node

A node has a separate LinkedList to store packets for each outgoing link, and a single common LinkedList for all routing packets received on its incoming links. The node passes the routing packets to the local routing object. For the incoming workload packet that is not destined for a local sink, the node consults the local routing table and appends the packet to appropriate outgoing LinkedList. A node can also be subject to failure and repair. When a node fails, all packets stored are lost.

The input parameters of node are Delay to process a packet [microseconds], Total available buffer space [bytes], Distribution of interfailure times, Distribution of repair times; The output parameters are Node status 9up/down), Amount of buffer space currently used [bytes], Maximum amount of occupied node buffer space so far in the simulation, Number of workload and routing packets dropped by the node in the simulation, Instantaneous packet drop rate, Current buffer utilization, Queue length [packets].

Performance monitor

The performance monitor is used to collect and evaluate statistics about the network. There are two ways to update the performance measures: periodically-updated and event-updated. Updating periodically at time instants called "update period" is periodically-updated performance measure. An event-updated performance measure is updated whenever a related event occurs. A performance measure can be either an average measure or an instantaneous measure. An average measure is computed based on statistics collected after a specified "startup interval" from the beginning of the simulation. An instantaneous measure is computed based on current state or statistics collected during the last update period.

When a target system is built to evaluate one routing algorithm, there should be only one performance monitor object. So I use Singleton pattern to ensure only one instance of Performance Monitor exist in the target system. There is a static variable performanceMonitor and a static method named "getPmt()" in the Pmt.java. Performance monitor not a part of the network so do not connect it to a component in the network. If an interaction is needed between performance monitor and components, Performance Monitor object obtained from Pmt.getPmt() is called in an event driven way like pm(link, LINK, LINK_DOWN,0,0,0) or poll at start time the component should issue pm(component, compTtype, NEW_COMPONENT), so the pm knows the component. The output parameters of the performance monitor are Average network throughput, Instantaneous network throughput, Average delay per packet, Instantaneous delay per packet, Maximum packet delay, Current number of connections in the network, Average number of packets per FTP connection, Average life-time of an FTP connection, Current number of failed links, Total number of dropped workload packets, Total number of routing packets, Average data load, Instantaneous data load, Average routing load, Instantaneous routing load, Buffer usage statistics.

Stopper

The stopper component enables the user to define a termination condition for the simulation, based on the input parameters and the statistics collected by performance monitor.

The input parameters of the stopper are Number of intervals, Interval length [microseconds], Error bound [percentage].

2.3 Parameters and packets

Parameter is an object used to store any information about a component that needs to be displayed on the screen, logged to disk, or saved in a network file. The instance variables of a Parameter object are as follows:

Private String name;
private int displayType;
private int flags;
private double scale;
private int logType;
private Object value;

The actual value of a parameter object is stored in the value variable. Because it is Object type, so it can be an Integer, Double, a LinkedList, a String or something else depending on what kind of type value an Component object want to store in that parameter. And flags describe how to save and/or display the parameter. It will be used when the GUI was added to the CuRS. A component object can have as many parameters as needed. They are stored in the LinkedList named params which is defined in the AbstractComponent class.

The target system is a message passing system. Messages are passed in the packets. There are two main types packets in the simulator: TR_PACKET is the application/transport part of the packet. ROUTE_PACKET is the routing part of the packet. Routing packet has higher priority than the data packet.

Оригинал статьи можно найти по этой ссылке: http://www.scs.carleton.ca/~arpwhite/documents/honoursProjects/chunyan-ma-2002.pdf