3. The Communication Network Model

In this paper, we focus on irregular topology connection-less networks with an IP-like network layer (in the ISO-OSI terminology) and a very simple transport layer. In particular, we focus on wide-area networks (WAN). In these cases, hierarchical organization schemes are adopted. Roughly speaking, sub-networks are seen as single host nodes connected to interface nodes called gateways. Gateways perform fairly sophisticated network layer tasks, including routing. Groups of gateways, connected by an arbitrary topology, dene logical areas. Inside each area, all the gateways are at the same hierarchical level and "flat" routing is performed among them. Areas communicate only by means of area border gateways. In this way, the computational complexity of the routing problem, as seen by each gateway, is much reduced (e.g., in the Internet, OSPF areas typically group 10 to 300 gateways), while the complexity of the design and management of the routing protocol is much increased.

The instance of our communication network is mapped on a directed weighted graph with N processing/forwarding nodes. All the links are viewed as bit pipes characterized by a bandwidth (bit/sec) and a transmission delay (sec), and are accessed following a statistical multiplexing scheme. For this purpose, every node, of type store-and-forward, holds a buer space where the incoming and the outgoing packets are stored. This buer is a shared resource among all the queues attached to every incoming and outgoing link of the node. All the traveling packets are subdivided in two classes: data and routing packets. All the packets in the same class have the same priority, so they are queued and served on the basis of a first-in-first-out policy, but routing packets have a greater priority than data packets. The workload is dened in terms of applications whose arrival rate is dictated by a selected probabilistic model. By application (or session, or connection in the following), we mean a process sending data packets from an origin node to a destination node. The number of packets to send, their sizes and the intervals between them are assigned according to some dened stochastic process. We didn't make any distinction among nodes, they act at the same time as hosts (session end-points) and gateways/routers (forwarding elements). The adopted workload model incorporates a simple ow control mechanism implemented by using a xed production window for the session's packets generation. The window determines the maximum number of data packets waiting to be sent. Once sent, a packet is considered to be acknowledged. This means that the transport layer neither manages error control, nor packet sequencing, nor acknowledgements and retransmissions.

For each incoming packet, the node's routing component uses the information stored in the local routing table to assign the outgoing link to be used to forward the packet toward its target node. When the link resources are available, they are reserved and the transfer is set up. The time it takes to move a packet from one node to a neighboring one depends on the packet size and on the link transmission characteristics. If, on a packet's arrival, there is not enough buffer space to hold it, the packet is discarded. Otherwise, a service time is stochastically generated for the newly arrived packet. This time represents the delay between the packet arrival time and the time when it will be put in the buer queue of the outgoing link the local routing component has selected for it.

Situations causing a temporary or steady alteration of the network topology or of its physical characteristics are not taken into account (link or node failure, adding or deleting of network components, etc.).

We developed a complete network simulator in C++. It is a discrete event simulator using as its main data structure an event list, which holds the next future events. The simulation time is a continuous variable and is set by the currently scheduled event. The aim of the simulator is to closely mirror the essential features of the concurrent and distributed behavior of a generic communication network without sacricing efficiency and exibility in code development.

We end this section with some remarks concerning two features of the model.

First, we chose not to implement a "real" transport layer for a proper management of error, flow, and congestion control. In fact, each additional control component has a considerable impact on the network performance, making very difficult to evaluate and to study the properties of each control algorithm without taking in consideration the complex way it interacts with all the other control components. Therefore, we chose to test the behavior of our algorithm and of its competitors in conditions such that the number of interacting components is minimal and the routing component can be evaluated in isolation, allowing a better understanding of its properties. To study routing in conjunction with error,ow and congestion control, all these components should be designed at the same time, to allow a good match among their characteristics to produce a synergetic effect.

Second, we chose to work with connection-less and not with connection-oriented networks because connection-oriented schemes are mainly used in networks able to deliver Quality of Service (QoS) (Crawley, Nair, Rajagopalan, & Sandick, 1996).4 In this case, suitable admission control algorithms have to be introduced, taking into account many economic and technological factors (Sandick & Crawley, 1997). But, again, as a first step we think that it is more reasonable to try to check the validity of a routing algorithm by reducing the number of components heavily in uencing the network behavior.