Network Simulator

The World Wide Web is growing at an enormous rate. New strategies are required to support the growth and keep the latency of document retrieval within limits. Many simulators have been developed to simulate the internet at great detail (ns2 , real5 ). Our aim is to design a network simulator which simulates the internet at a high level and depicts it’s usage analytically.

Overall Description

Our aim is to have a simulator which can show the effects of data transfer

over a given network topology. We generate streams of requests for the topology and output the logged data to a visualizer, whose interfacing is done through a file.

Environment Characteristics

Hardware/Software: Any platform which supports GNU C++ , LEDA libraries and has a Java Virtual Machine (required for the visualizer).

Peripherals: None

Interfaces

Interface with User: The user shall not directly interface with the simulator. All user interfaces are handled by the visualizer software.

Interface with Visualizer: This shall be the primary interface with the simulator. All inputs , intermediary and final outputs and details shall be exchanged via files. The visualizer shall initiate the simulator via a system execute command.

Constraints

The network topology is simple and static, which is represented by a simple undirected graph

The links are full duplex.

Simulation of errors including packet losses, retransmission and noise bursts are handled analytically.

There are primarily three types of nodes in the network which represent the Origin, Caching and Proxy servers. All origin servers are caching servers but not proxy servers.

All pages in this system are partitioned into classes according to their request rates. These request rates obey Zipf distribution.

Routing in the network is fixed.

Pages are basic units of transmission and not further broken down into packets. All pages are equal in size.

Functional Requirements

Functional Partitioning

The modules are partitioned as specified below:

Input Module: This module will handle all the input data as received from the visualizer (via a file). It contains the GML parser to parse the input data.

Event Generator: This module generates the initial stream of requests and distributes them according to their load characteristics.

Simulator: This is the heart of the entire system. The module decodes and executes all events residing in the event queue.

Logging: The logging module will take a snapshot of the system at the given time by recording all relevant data.

Functional Description

0.1 Generate Requests

Input: Information of the request rate of all the pages.

Output: Requests for the pages distributed in time and among all the proxy servers.

Procedure: For each page existing on any origin server requests are distributed among all the servers for each such server model the inter-request arrival time and generate corresponding events.

0.2 Simulator sub-system

Input: The event queue, the network topology, the policy numbers.

Output: The simulation results

Procedure: For each event in the event queue, effect on the network is simulated.

When the queue is empty or simulation time runs out, the results are collected from the nodes and output.

0.1.1 Distribute Requests.

Input: Information of the aggregate request rate for a page.

Output: The request rate points at every server for the page.

Procedure: The aggregate request rate of every page is distributed normally among all the servers.(We assume that the request rate for a page is a step-wise linear curve and use the value at t1 to distribute requests among the servers in the interval t1.)

0.1.2 Generate Inter-request arrival time

Input: The request rate for a page at different times at a server.

Output: The events for the page from the server distributed in time.

Procedure: The requests for a page are distributed using a Poisson distribution along the time axis. The mean of the distribution in the interval of time being the request rate in the time interval.

0.2.1 Initialize

Input: The Network Topology, the cache policy and diffusion policy.

Output: All parts of the network instantiated . (A LEDA graph for the topology).

Procedure: Instantiate each node , link and their encapsulated attributes.

0.2.2 Event handler

Input: The instantiated network, the event queue.

Output: The logs of the simulation.

Procedure: While the queue is not empty extract the event at the front of the stack simulate the event on the simulator and record its effect.

0.2.2.1 Process event

Input: An event.

Output: A response event for the stimulus event.

Procedure: For the event at the head of the queue ,process the event with regard to which network component it deals with and invoke the corresponding handler. If the event is associated with a node, it invokes the node event handler with the node.If the event is associated with a link, it invokes the link event handler with the link .The corresponding event created on processing the events are inserted into the event queue according to their temporal order.

0.2.2.2 Node Event Handler.

Input : An event.

Output: A response event for the stimulus event.

Procedure : Process the event and replicate its effect in the network.The method invokes the search cache if the event is a request event; or invokes the store cache or diffuse method according to the data received and the destination of the request.

0.2.2.3 Link Event Handle.

Input : An event.

Output: A response event for the stimulus event.

Procedure: Process the event and replicate its effect in the network. Errors are modeled in the link and packets delayed accordingly. An event with the node at the receiving end is generated after the delay time. The buffer of the transmitting node is adjusted.

0.2.2.3.1 Transmit

Input : An event.

Output: A response event for the stimulus event.

Procedure: Errors in the link are modeled by calling the isTransmitted method and accordingly the delay-time generated for a packet. After the delay time, an event is generated in the node at the receiving end. Correspondingly, a method to adjust the buffer of the transmitting node is invoked.

0.2.2.3.2 isTransmitted

Input: null

Output: A boolean value [yes/no]

Procedure: Using a random generator having a normal distribution,we decide whether the packet has a delay (error) added to it’s transmission time.

0.2.2.3.3 adjustQueues

Input : The packets delayed and the time by which they were delayed.

Output: null

Procedure: Invoke the corresponding method of the node to make the required changes in the time stamp.

0.2.2.2.1 Search Cache

Input : A request for a page

Output: Another request or transmit event to the corresponding server.

Procedure: Search the cache for the availability of the page. If the page is available in cache then create a transmit event in the node where the node where the request was originally generated and update the page properties of the page.

If the page is not present then propogate the request towards the origin server.The queue handler of the node is invoked with either event , which in turn positions the event in the event queue.

0.2.2.2.2 Data Arrive

Input : A transmit event for a page

Output: An event to propogate the packet received , and an event to propagate the page properties of the pages replaced towards their origin servers.

Procedure: If this node is the one requesting this page, then the node tries to cache the page.

If not, then an event, to transmit the packet towards the node where the request originated, is generated. The node tries to cache the page .

In both cases, the pages replaced are sent to the diffuse method to determine where to cache them subsequently.

0.2.2.2.3 Store Cache

Input: A page ID

Output: A list of page IDs and properties of the pages replaced.

Procedure: Invoke the cache replacement method corresponding to the policy being followed and replace (some) pageIDs with the pageID received. Set the page properties of those page(s) replaced and the one inserted.

0.2.2.2.4 Diffuse

Input : The page IDs and page properties of the pages.

Output : Events whose action is to send the page properties towards their origin server.

Procedure: Create corresponding events and transmit them towards the next node by invoking the queue handler.

0.2.2.2.5 Route

Input : The IPAddress of the destination of the packet.

Output : The link to send the packet through.

Procedure : Look up into the routing table and return the required link ID.

Control Description

The following steps show the flow of control within the program.

The network topology will be given to simulator either from a file which will include the necessary details (such as cache size, link bandwidth etc ) required to setup the network.

The initial page requests will also be given to simulator either from a file or generated internally by a separate module.

All the objects will be instantiated with the given parameters and options.

The event manager will begin the simulation by executing the events residing in the event queue. To decode and execute an event , it will lookup a global event table which shows the correspondence between the events and the methods to call to simulate this event.

In the process of executing events , further events may be generated which will be directly stored in the event queue by the object generating the event. The event manager does not play a role here.

At particular time intervals , every object may flush their logs to either standard output or a file.

The simulation will stop either when we run out of events or we reach the simulation end time.