1105.5449v1

# Unknown Title Journal of Arti/cial Intelligence Research /9 /(/1/9/9/8/) /3/1/7/-/3/6/5 Submitted /5///9/8/; published /1/2///9/8 ## AntNet/: Distributed Stigmergetic Control for Gianni Di Caro /5/0/, Communications Networks Marco Dorigo IRIDIA/, Universit/ e Libre de Bruxelles mdorigo/@ulb/.ac/.be av/. F/. Roosevelt/, CP /1/9/4///6/, /1/0/5/0 /- Brussels/, Belgium Abstract This paper introduces AntNet/, a novel approach to the adaptive learning of routing tables in communications networks/. AntNet is a distributed/, mobile agents based Monte Carlo system that was inspired by recent work on the ant colony metaphor for solving optimization problems/. AntNet/'s agents concurrently explore the network and exchange collected information/. The communication among the agents is indirect and asynchronous/, mediated by the network itself/. This form of communication is typical of social insects and is called stigmergy/. We compare our algorithm with six state/-of/-the/-art routing algo/rithms coming from the telecommunications and machine learning /elds/. The algorithms/' performance is evaluated over a set of realistic testbeds/. We run many experiments over real and arti/cial IP datagram networks with increasing number of nodes and under sev/eral paradigmatic spatial and temporal tra/c distributions/. Results are very encouraging/. AntNet showed superior performance under all the experimental conditions with respect to its competitors/. We analyze the main characteristics of the algorithm and try to explain the reasons for its superiority/. /1/. Introduction Worldwide demand and supply of communications networks services are growing exponen/tially/. Techniques for network control /(i/.e/./, online and o//-line monitoring and management of the network resources/) play a fundamental role in best exploiting the new transmission to continue their travel towards the destination node/. Routing protocols and policies have to accommodate con/ icting objectives and con/straints imposed by technologies and user requirements rapidly evolving under commercial and scienti/c pressures/. Novel routing approaches are required to e/ciently manage dis/tributed multimedia services/, mobile users and networks/, heterogeneous inter/-networking/, service guarantees/, point/-to/-multipoint communications/, etc/. /(Sandick /& Crawley/, /1/9/9/7/; and switching technologies to meet user/'s requests/. Routing is at the core of the whole network control system/. Routing/, in conjunction with the admission/, / ow/, and congestion control components/, determines the overall network performance in terms of both quality and quantity of delivered service /(Walrand /& Varaiya/, /1/9/9/6/)/. Routing refers to the distributed activity of building and using routing tables/, one for each node in the network/, which tell incoming data packets which outgoing link to use The ATM Forum/, /1/9/9/6/)/. The adaptive and distributed routing algorithm we propose in this paper is a mobile/- c inspired by previous work on / /1/9/9/8 AI Access Foundation and Morgan Kaufmann Publishers/. All rights reserved/. arti/cial ant gdicaro/@iridia/.ulb/.ac/.be Di Caro /& Dorigo colonies and/, more generally/, by the notion of stigmergy /(Grass/ e/, /1/9/5/9/)/, that is/, the in/direct communication taking place among individuals through modi/cations induced in of information they collect while exploring the network/. To ensure a meaningful validation of our algorithm performance we devised a realistic simulation environment in terms of network characteristics/, communications protocol and tra/c patterns/. We focus on IP /(Internet Protocol/) datagram networks with irregular topology and consider three real and arti/cial topologies with an increasing number of nodes and several paradigmatic temporal and spatial tra/c distributions/. We report on the behavior of AntNet as compared to some e/ective static and adaptive state/-of/-the/-art routing algorithms /(vector/-distance and link/-state shortest paths algorithms /(Steenstrup/, their environment/. Algorithms that take inspiration from real ants/' behavior in /nding shortest paths /(Goss/, Aron/, Deneubourg/, /& Pasteels/, /1/9/8/9/; Beckers/, Deneubourg/, /& Goss/, /1/9/9/2/) using as infor/mation only the trail of a chemical substance /(called pheromone/) deposited by other ants/, have recently been successfully applied to several discrete optimization problems /(Dorigo/, Maniezzo/, /& Colorni/, /1/9/9/1/; Dorigo/, /1/9/9/2/; Dorigo/, Maniezzo/, /& Colorni/, /1/9/9/6/; Dorigo /& Gambardella/, /1/9/9/7/; Schoonderwoerd/, Holland/, Bruten/, /& Rothkrantz/, /1/9/9/6/; Schoonderwo/erd/, Holland/, /& Bruten/, /1/9/9/7/; Costa /& Hertz/, /1/9/9/7/)/. In all these algorithms a set of arti/cial ants collectively solve the problem under consideration through a cooperative e/ort/. This e/ort is mediated by indirect communication of information on the problem structure the ants concurrently collect while building solutions by using a stochastic policy/. Similarly/, in AntNet/, the algorithm we propose in this paper/, a set of concurrent distributed agents collectively solve the adaptive routing problem/. Agents adaptively build routing tables and local models of the network status by using indirect and non/-coordinated communication /1/9/9/5/)/, and recently introduced algorithms based on machine learning techniques/)/. AntNet shows the best performance and the most stable behavior for all the considered situations/. In many experiments its superiority is striking/. We discuss the results and the research/. main properties of our algorithm/, as compared with its competitors/. The paper is organized as follows/. In Section /2 the de/nition/, taxonomy and charac/teristics of the routing problem are reported/. In Section /3 we describe the communication network model we used/. Section /4 describes in detail AntNet/, our novel routing algorithm/, while in Section /5 we brie/ y describe the algorithms with which we compared AntNet/. In Section /6/, the experimental settings are reported in terms of tra/c/, networks and algorithm parameters/. Section /7 reports several experimental results/. In Section /8 we discuss these results and try to explain AntNet/'s superior performance/. Finally/, in Section /9/, we discuss related work/, and in Section /1/0/, we draw some conclusions and outline directions for future /2/. Routing/: De/nition and Characteristics Routing in distributed systems can be characterized as follows/. Let G /= /(V/; E/) be a directed weighted graph/, where each node in the set V represents a processing//queuing and//or for/warding unit and each edge is a transmission system/. The main task of a routing algorithm is to direct data / ow from source to destination nodes maximizing network performance/. /3/1/8 AntNet/: Distributed Stigmergetic Control for Communications Networks In the problems we are interested in/, the data / ow is not statically assigned and it follows performance objectives/, and /(iii/) the forwarding of user tra/c along the selected routes/. The way the above three functionalities are implemented strongly depends on the un/derlying network switching and transmission technology/, and on the features of the other interacting software layers/. Concerning point /(iii/)/, two main forwarding paradigms are in use/: circuit and packet/-switching /(also indicated with the terms connection/-oriented and connection/-less/)/. In the circuit/-switching approach/, a setup phase looks for and reserves the resources that will be assigned to each incoming session/. In this case/, all the data packets belonging to the same session will follow the same path/. Routers are required to keep state information about active sessions/. In the packet/-switching approach/, there is no reservation phase/, no state information is maintained at routers and data packets can follow di/erent paths/. In each intermediate node an autonomous decision is taken concerning the node/'s a stochastic pro/le that is very hard to model/. In the speci/c case of communications networks /(Steenstrup/, /1/9/9/5/; Bertsekas /& Gallager/, /1/9/9/2/)/, the routing algorithm has to manage a set of basic functionalities and it tightly interacts with the congestion and admission control algorithms/, with the links/' queuing policy/, and with the user/-generated tra/c/. The core of the routing functions is /(i/) the acquisition/, organization and distribution of information about user/-generated tra/c and network states/, /(ii/) the use of this information to generate feasible routes maximizing the outgoing link that has to be used to forward the data packet toward its destination/. In the work described in this paper/, we focus on the packet/-switching paradigm/, but the technique developed here can be used also to manage circuit/-switching and we expect /2/./1 A Broad Taxonomy A common feature of all the routing algorithms is the presence in every network node of a data structure/, called routing table/, holding all the information used by the algorithm to make the local forwarding decisions/. The routing table is both a local database and a local model of the global network status/. The type of information it contains and the way this information is used and updated strongly depends on the algorithm/'s characteristics/. A ## to have qualitatively similar results/. broad classi/cation of routing algorithms is the following/: / static versus adaptive/. In centralized algorithms/, a main controller is responsible for updating all the node/'s routing tables and//or to make every routing decision/. Centralized algorithms can be used only in particular cases and for small networks/. In general/, the delays necessary to gather information about the network status and to broadcast the decisions//updates make them infeasible in practice/. Moreover/, centralized systems are not fault/-tolerant/. In this work/, - / centralized versus distributed/; we will consider exclusively distributed routing/. In distributed routing systems/, the computation of routes is shared among the network nodes/, which exchange the necessary information/. The distributed paradigm is currently on the basis of its source and destination/, without regard to the current network state/. This used in the majority of network systems/. In static /(or oblivious/) routing systems/, the path taken by a packet is determined only /3/1/9 Di Caro /& Dorigo path is usually chosen as the shortest one according to some cost criterion/, and it can be connection/-oriented networks /(Bertsekas /& Gallager/, /1/9/9/2/)/. Another interesting way of looking at routing algorithms is from an optimization per/- changed only to account for faulty links or nodes/. Adaptive routers are/, in principle/, more attractive/, because they can adapt the rout/ing policy to time and spatially varying tra/c conditions/. As a drawback/, they can cause oscillations in selected paths/. This fact can cause circular paths/, as well as large / uctu/ations in measured performance/. In addition/, adaptive routing can lead more easily to inconsistent situations/, associated with node or link failures or local topological changes/. These stability and inconsistency problems are more evident for connection/-less than for - spective/. In this case the main paradigms are/: / optimal routing versus shortest path routing/. Minimal routers allow packets to choose only minimal cost paths/, while non/-minimal algorithms allow choices among all the available paths following some heuristic strategies - / minimal routing versus non/-minimal routing/; /(Bolding/, Fulgham/, /& Snyder/, /1/9/9/4/)/. Optimal routing has a network/-wide perspective and its objective is to optimize a func/tion of all individual link / ows /(usually this function is a sum of link costs assigned on the called distance/-vector and link/-state /(Steenstrup/, /1/9/9/5/)/. Optimal routing is static /(it can be seen as the solution of a multicommodity / ow prob/lem/) and requires the knowledge of all the tra/c characteristics/. Shortest paths algorithms are more / exible/, they don/'t require a priori knowledge about the tra/c patterns and they basis of average packet delays/) /(Bertsekas /& Gallager/, /1/9/9/2/)/. Shortest path routing has a source/-destination pair perspective/: there is no global cost function to optimize/. Its objective is to determine the shortest path /(minimum cost/) between two nodes/, where the link costs are computed /(statically or adaptively/) following some statistical description of the link states/. This strategy is based on individual rather than group rationality /(Wang /& Crowcroft/, /1/9/9/2/)/. Considering the di/erent content stored in each routing table/, shortest path algorithms can be further subdivided into two classes are the most widely used routing algorithms/. In appendix A/, a more detailed description of the properties of optimal and shortest ## not their usual implementation paradigms /(as depicted in appendix A/)/. path routing algorithms is reported/. In Section /4/, we introduce a novel distributed adaptive method/, AntNet/, that shares the same optimization perspective as /(minimal or non/-minimal/) shortest path algorithms but /2/./2 Main Characteristics of the Routing Problem The main characteristics of the routing problem in communications networks can be sum/- and status information propagation delays are not negligible with respect to the user/'s - marized in the following way/: / Intrinsically distributed with strong real/-time constraints/: in fact/, the database and the decision system are completely distributed over all the network nodes/, and failures /3/2/0 AntNet/: Distributed Stigmergetic Control for Communications Networks tra/c patterns/. It is impossible to get complete and up/-to/-date knowledge of the dis/tributed state/, that remains hidden/. At each decision node/, the routing algorithm can only make use of local/, up/-to/-date information/, and of non/-local/, delayed information - framework/)/. / Multi/-objective/: several con/ icting performance measures are usually taken into ac/count/. The most common are throughput /(bit//sec/) and average packet delay /(sec/)/. The former measures the quantity of service that the network has been able to o/er in a certain amount of time /(amount of correctly delivered bits per time unit/)/, while the latter de/nes the quality of service produced at the same time/. Citing Bertsekas and Gallager /(/1/9/9/2/)/, page /3/6/7/: /\the e/ect of good routing is to increase throughput for the same value of average delay per packet under high o/ered load conditions and to decrease average delay per packet under low and moderate o/ered load conditions/"/. Other performance measures consider the impact of the routing algorithm on the net/work resources in terms of memory/, bandwidth and computation/, and the algorithm - coming from the other nodes/. / Stochastic and time/-varying/: the session arrival and data generation process is/, in the general case/, non/-stationary and stochastic/. Moreover/, this stochastic process interacts recursively with the routing decisions making it infeasible to build a work/ing model of the whole system /(to be used for example in a dynamic programming - simplicity/, / exibility/, etc/. / Multi/-constraint/: constraints are imposed by the underlying network technology/, the network services provided and the user services requested/. In general/, users ask for low/-cost/, high/-quality/, reliable/, distributed multimedia services available across hetero/geneous static and mobile networks/. Evaluating technological and commercial factors/, network builders and service providers try to accommodate these requests while max/imizing some pro/t criteria/. Moreover/, a high level of fault/-tolerance and reliability is requested in modern high/-speed networks/, where user sessions can formulate precise requests for network resources/. In this case/, once the session has been accepted/, the system should be able to guarantee that the session gets the resources it needs/, under and of its constraints/, the complete state of the network is hidden to each agent/. any recoverable fault event/. It is interesting to note that the above characteristics make the problem of routing belong to the class of reinforcement learning problems with hidden state /(Bertsekas /& Tsitsiklis/, /1/9/9/6/; Kaelbling/, Littman/, /& Moore/, /1/9/9/6/; McCallum/, /1/9/9/5/)/. Adistributed system of agents/, the components of the routing algorithm in each node/, determine a continual and online learning of the best routing table values with respect to network/'s performance criteria/. An exact measure of evaluation that scores forwarding decisions is not available/, neither online nor in the form of a training set/. Moreover/, because of the distributed nature of the problem /3/. The Communication Network Model In this paper/, we focus on irregular topology connection/-less networks with an IP/-like net/work 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 /3/2/1 Di Caro /& Dorigo are adopted/. /1 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 /\/ at/" 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 /1/0 to /3/0/0 gateways/)/, while control/, nor packet sequencing/, nor acknowledgements and retransmissions/. /2 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 bu/er 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 bu/er queue of the 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 bu/er space where the incoming and the outgoing packets are stored/. This bu/er 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 /rst/-in/-/rst/-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 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 /1/. A hierarchical structure is adopted on the Internet/, organized in hierarchical Autonomous Systems and multiple routing areas inside each Autonomous System /(Moy/, /1/9/9/8/)/. /2/. This choice is the same as in the /\Simple Tra/c/" model in the MaRS network simulator /(Alaettino/ glu/, Shankar/, Dussa/-Zieger/, /& Matta/, /1/9/9/2/)/. It can be seen as a very basic form of File Transfer Protocol /3/2/2 of network components/, etc/./)/. /(FTP/)/. AntNet/: Distributed Stigmergetic Control for Communications Networks 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 e/ciency and / exibility allow a good match among their characteristics to produce a synergetic e/ect/. Second/, we chose to work with connection/-less and not with connection/-oriented net/works because connection/-oriented schemes are mainly used in networks able to deliver Quality of Service /(QoS/) /(Crawley/, Nair/, Rajagopalan/, /& Sandick/, /1/9/9/6/)/. /4 In this case/, suitable admission control algorithms have to be introduced/, taking into account many economic and technological factors /(Sandick /& Crawley/, /1/9/9/7/)/. But/, again/, as a /rst step we think that it is more reasonable to try to check the validity of a routing algorithm by 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/, / ow/, and congestion control/. In fact/, each additional control component has a considerable impact on the network performance/, /3 making very di/cult 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 ## reducing the number of components heavily in/ uencing the network behavior/. /4/. AntNet/: An Adaptive Agent/-based Routing Algorithm The characteristics of the routing problem /(discussed in Section /2/./2/) make it well suited to be solved by a mobile multi/-agent approach /(Stone /& Veloso/, /1/9/9/6/; Gray/, Kotz/, Nog/, Rus/, /& Cybenko/, /1/9/9/7/)/. This processing paradigm is a good match for the distributed and non/-stationary /(in topology and tra/c patterns/) nature of the problem/, presents a high level of redundancy and fault/-tolerance/, and can handle multiple objectives and constraints /1/9/9/6/; Dorigo /& Gambardella/, /1/9/9/7/) and telephone network routing /(Schoonderwoerd et al/./, /3/. As an example/, some authors reported an improvement ranging from /2 to /3/0/% in various performance measures for real Internet tra/c /(Danzig/, Liu/, /& Yan/, /1/9/9/4/) by changing from the Reno version to the Vegas version of the TCP /(Peterson /& Davie/, /1/9/9/6/) /(the current Internet Transport Control Protocol/)/, in a / exible way/. AntNet/, the routing algorithm we propose in this paper/, is a mobile agents system show/ing some essential features of parallel replicated Monte Carlo systems /(Streltsov /& Vakili/, /1/9/9/6/)/. AntNet takes inspiration from previous work on arti/cial ant colonies techniques to solve combinatorial optimization problems /(Dorigo et al/./, /1/9/9/1/; Dorigo/, /1/9/9/2/; Dorigo et al/./, and other authors even claimed improvements ranging from /4/0 to /7/0/% /(Brakmo/, O/'Malley/, /& Peterson/, /1/9/9/4/)/. /4/. This is not the case for the current Internet/, where the IP bearer service is of /\best/-e/ort/" type/, meaning that it does the best it can do but no guarantees of service quality in terms of delay or bandwidth or /3/2/3 jitter/, etc/./, can be assured/. Di Caro /& Dorigo /1/9/9/6/, /1/9/9/7/)/. The core ideas of these techniques /(for a review see Dorigo/, Di Caro/, and Gambardella/, /1/9/9/8/) are /(i/) the use of repeated and concurrent simulations carried out by a population of arti/cial agents called /\ants/" to generate new solutions to the problem/, /(ii/) the use by the agents of stochastic local search to build the solutions in an incremental way/, and /(iii/) the use of information collected during past simulations to direct future search for of social insects /(Grass/ e/, /1/9/5/9/)/. In AntNet/, we retain the core ideas of the arti/cial ant colony paradigm/, and we apply better solutions/. In the arti/cial ant colony approach/, following an iterative process/, each ant builds a solution by using two types of information locally accessible/: problem/-speci/c information /(for example/, distance among cities in a traveling salesman problem/)/, and information added by ants during previous iterations of the algorithm/. In fact/, while building a solution/, each ant collects information on the problem characteristics and on its own performance/, and uses this information to modify the representation of the problem/, as seen locally by the other ants/. The representation of the problem is modi/ed in such a way that information contained in past good solutions can be exploited to build new better solutions/. This form of indirect communication mediated by the environment is called stigmergy/, and is typical them to solve in an adaptive way the routing problem in datagram networks/. Informally/, the AntNet algorithm and its main characteristics can be summarized as - / At regular intervals/, and concurrently with the data tra/c/, from each network node mobile agents are asynchronously launched towards randomly selected destination follows/. - nodes/. / Agents act concurrently and independently/, and communicate in an indirect way/, - / Each agent searches for a minimum cost path joining its source and destination nodes/. / Each agent moves step/-by/-step towards its destination node/. At each intermediate node a greedy stochastic policy is applied to choose the next node to move to/. The policy makes use of /(i/) local agent/-generated and maintained information/, /(ii/) local - through the information they read and write locally to the nodes/. - problem/-dependent heuristic information/, and /(iii/) agent/-private information/. / While moving/, the agents collect information about the time length/, the congestion - by moving along the same path as before but in the opposite direction/. / During this backward travel/, local models of the network status and the local routing table of each visited node are modi/ed by the agents as a function of the path they - status and the node identi/ers of the followed path/. / Once they have arrived at the destination/, the agents go back to their source nodes - followed and of its goodness/. plicated and discussed/, and a more detailed description of the algorithm is given/. / Once they have returned to their source node/, the agents die/. In the following subsections the above scheme is explained/, all its components are ex/- /3/2/4 /5/. AntNet/: Distributed Stigmergetic Control for Communications Networks /4/./1 Algorithm Description and Characteristics AntNet is conveniently described in terms of two sets of homogeneous mobile agents /(Stone /& Veloso/, /1/9/9/6/)/, called in the following forward and backward ants/. Agents /5 in each set possess the same structure/, but they are di/erently situated in the environment/; that is/, they can sense di/erent inputs and they can produce di/erent/, independent outputs/. They can be broadly classi/ed as deliberative agents/, because they behave reactively retrieving a pre/-compiled set of behaviors/, and at the same time they maintain a complete internal state description/. Agents communicate in an indirect way/, according to the stigmergy paradigm/, through the information they concurrently read and write in two data structures stored in each network node k /(see Figure /1/)/: Figure /1/: Node structures used by mobile agents in AntNet for the case of a node with L neighbors and a network with N nodes/. The routing table is organized as in vector/-distance algorithms/, but the entries are probabilistic values/. The structure containing statistics about the local tra/c plays the role of a local adaptive model <details> <summary>Image 1 Details</summary>  ### Visual Description \n ## Diagram: Network Node Internal Structure and Data Flow ### Overview The image is a conceptual diagram illustrating the internal components of a generic "Network Node" and its data relationships with broader network structures. It uses a color-coded scheme (yellow for routing-related elements, cyan for statistics-related elements) and connecting lines to show information flow. The diagram is schematic and does not contain numerical data or quantitative trends. ### Components/Axes The diagram is divided into three main spatial regions: 1. **Left Region (Primary Focus):** A large pink circle labeled **"Network Node"**. Inside this circle are two primary components: * A yellow rectangle labeled **"Routing Table"**. * A cyan rectangle labeled **"Local Traffic Statistics"**. 2. **Top-Right Region:** A large yellow grid labeled **"Network Nodes"** at the top. The grid is structured as a matrix: * **Rows:** Labeled on the left side as **"Outgoing Links"**. There are `L` rows, indexed from 1 to `L`. * **Columns:** Represent different destination network nodes, indexed from 1 to `N`. * **Cell Content:** Each cell contains a label `P` with two subscripts, `P_ij`, where `i` is the row (link) index and `j` is the column (node) index. The grid shows the first two rows (`P_11, P_12, ..., P_1N` and `P_21, P_22, ..., P_2N`) and the last row (`P_L1, P_L2, ..., P_LN`), with vertical ellipses (`⋮`) indicating intermediate rows. 3. **Bottom-Right Region:** A horizontal cyan bar labeled **"Network Nodes"** above it. This bar is segmented into cells labeled **"Stat (1)"**, **"Stat (2)"**, ..., **"Stat(N)"**. **Connections (Lines):** * A line connects the **"Routing Table"** (inside the node) to the top-left corner of the yellow **"Network Nodes"** grid. * A line connects the **"Local Traffic Statistics"** (inside the node) to the left side of the cyan **"Network Nodes"** statistics bar. ### Detailed Analysis * **Routing Table Component:** The yellow "Routing Table" is depicted as the source of information that populates or defines the larger yellow matrix. The matrix represents routing parameters (denoted by `P`) for each combination of an outgoing link (`i`) and a destination network node (`j`). The notation `P_ij` strongly suggests these are probabilities, costs, or weights associated with sending traffic from link `i` to node `j`. * **Local Traffic Statistics Component:** The cyan "Local Traffic Statistics" component is shown as the source for the segmented statistics bar. This implies that local data collected at the individual node is aggregated or reported into a broader set of statistics (`Stat(1)` to `Stat(N)`), likely corresponding to metrics for each of the `N` network nodes. * **Spatial Grounding:** The legend is effectively the color coding itself: **Yellow** = Routing/Forwarding Plane, **Cyan** = Statistics/Monitoring Plane. The primary "Network Node" circle (pink) acts as a container, isolating the node's internal functions from the external network-wide data structures (the grid and the stats bar) it interacts with. ### Key Observations 1. **Dual-Function Node:** The diagram explicitly separates a network node's function into two distinct planes: a **routing decision plane** (yellow) and a **traffic monitoring plane** (cyan). 2. **Matrix Representation of Routing:** The routing information is not shown as a simple list but as a 2D matrix (`L` links x `N` nodes), indicating a comprehensive mapping of next-hop choices for all possible destinations across all available interfaces. 3. **Aggregation of Statistics:** The "Local Traffic Statistics" do not remain local; they feed into a network-wide view, as shown by the connection to the bar containing statistics for all `N` nodes. 4. **Abstract Notation:** The use of variables (`L`, `N`, `i`, `j`, `P`, `Stat`) instead of concrete numbers indicates this is a general model applicable to networks of varying sizes and topologies. ### Interpretation This diagram provides a **Peircean investigative** model of a network node's role within a larger system. It moves beyond a simple "black box" view to expose the internal logic: * **What it demonstrates:** It illustrates the fundamental separation of concerns in network element design. The node must simultaneously solve two problems: **"Where do I send packets?"** (handled by the Routing Table and its matrix of `P_ij` values) and **"What is happening on the network?"** (handled by Local Traffic Statistics, which are aggregated for network-wide analysis). * **How elements relate:** The flow is cyclical and interdependent. The routing decisions (influenced by the `P_ij` matrix) directly generate the traffic patterns that are then measured by the statistics module. Conversely, the aggregated statistics (`Stat(1)...Stat(N)`) are likely used as input to update or optimize the routing table's `P_ij` values in a real system, creating a feedback loop for adaptive routing. * **Notable Anomalies/Insights:** The diagram's most significant insight is the **explicit visual linkage between local action and global state**. The line from "Local Traffic Statistics" to the network-wide statistics bar is a powerful representation of how distributed systems build a collective understanding from local observations. The absence of a direct line from the statistics back to the routing table within the node is notable; it suggests that in this model, routing updates might be computed centrally or through a distributed protocol that uses the aggregated statistics as input, rather than being a purely local, autonomous adjustment. </details> for the tra/c toward each possible destination/. - i/) A routing table Tk /, organized as in vector/-distance algorithms /(see Appendix A/)/, but with probabilistic entries/. Tk de/nes the probabilistic routing policy currently adopted at node k/: for each possible destination d and for each neighbor node n/, T k stores a probability value P nd expressing the goodness /(desirability/)/, under the current network/-wide routing policy/, of choosing n as next node when the destination node - n/2Nk ii/) An array Mk /(/ d /; / d /2 /; Wd/)/, of data structures de/ning a simple parametric statistical model for the tra/c distribution over the network as seen by the local node k/. The model is adaptive and described by sample means and variances computed over the trip times experienced by the mobile agents/, and by a moving observation window W d is d/: $$\sum _ { n \in N _ { k } } P _ { n d } = 1 , d \in [ 1 , N ] , N _ { k } = \{ neighbors ( k ) \} .$$ used to store the best value W bestd of the agents/' trip time/. In the following/, we will use interchangeably the terms ant and agent/. /3/2/5 exponential model/: /6 Di Caro /& Dorigo For each destination d in the network/, an estimated mean and variance/, / d and / d /2 /, give a representation of the expected time to go and of its stability/. We used arith/metic/, exponential and windowed strategies to compute the statistics/. Changing strat/egy does not a/ect performance much/, but we observed the best results using the $$\sigma ^ { 2 } _ { i } \leftarrow \sigma ^ { 2 } _ { i } + n ( \sigma _ { i } - \sigma _ { j } ) ^ { 2 } -$$ d from the current node/. T and M can be seen as memories local to nodes capturing di/erent aspects of the network dynamics/. The model M maintains absolute distance//time estimates to all the nodes/, while the routing table gives relative probabilistic goodness measures for each link/- / d /2 / / d /2 /+ //(/(o k/!d /BnZr / d /) /2 /BnZr / d /2 /)/; /(/1/) where o k/!d is the new observed agent/'s trip time from node k to destination d/. /7 The moving observation window Wd is used to compute the value W bestd of the best agents/' trip time towards destination d as observed in the last w samples/. After each new sample/, w is incremented modulus jWj max /, and jWj max is the maximum allowed size of the observation window/. The value Wbestd represents a short/-term memory expressing a moving empirical lower bound of the estimate of the time to go to node destination pair under the current routing policy implemented over all the network/. $$\sum _ { d = 1 } ^ { N } f _ { s d }$$ - The AntNet algorithm is described as follows/. /1/. At regular intervals /
t from every network node s/, a mobile agent /(forward ant/) F s/!d is launched toward a destination node d to discover a feasible/, low/-cost path to that node and to investigate the load status of the network/. Forward ants share the same queues as data packets/, so that they experience the same tra/c loads/. Destinations are locally selected according to the data tra/c patterns generated by the local workload/: if f sd is a measure /(in bits or in number of packets/) of the data / ow s /! d/, then the d /0 /=/1 In this way/, ants adapt their exploration activity to the varying data tra/c distribu/- stack S s/!d /(k/)/. - tion/. /2/. While traveling toward their destination nodes/, the agents keep memory of their paths and of the tra/c conditions found/. The identi/er of every visited node k and the time elapsed since the launching time to arrive at this k/-th node are pushed onto a memory /6/. This is the same model as used by the Jacobson//Karels algorithm to estimate retransmission timeouts in the Internet TCP/(Peterson /& Davie/, /1/9/9/6/)/. /7/. The factor / weights the number of most recent samples that will really a/ect the average/. The weight of the ti/-th sample used to estimate the value of /d after j samplings/, with j /> i/, is/: //(/1 /BnZr //) j/BnZri /. In this way/, for example/, if / /= /0/:/1/, approximately only the latest /5/0 observations will really in/ uence the estimate/, for / /= /0/:/0/5/, the latest /1/0/0/, and so on/. Therefore/, the number of e/ective observations is /3/2/6 / /5/(/1/=//)/. AntNet/: Distributed Stigmergetic Control for Communications Networks - /3/. At each node k/, each traveling agent headed towards its destination d selects the node n to move to choosing among the neighbors it did not already visit/, or over all the neighbors in case all of them had been previously visited/. The neighbor n is selected with a probability /(goodness/) P /0 nd computed as the normalized sum of the probabilistic entry P nd of the routing table with a heuristic correction factor l n taking into account /1 /+ //(jN k j /BnZr /1/) The heuristic correction l n is a /[/0/,/1/] normalized value proportional to the length q n /(in bits waiting to be sent/) of the queue of the link connecting the node k with its $$\rho _ { n d } = \frac { P _ { n d } + \alpha l _ { n } } { 1 + \alpha ( | N _ { k } | - 1 ) ^ { \prime } }$$ neighbor n/: n /0 /=/1 The value of / weights the importance of the heuristic correction with respect to the probability values stored in the routing table/. l n re/ ects the instantaneous state of the node/'s queues/, and assuming that the queue/'s consuming process is almost stationary or slowly varying/, l n gives a quantitative measure associated with the queue waiting time/. The routing tables values/, on the other hand/, are the outcome of a continual learning process and capture both the current and the past status of the whole network as seen by the local node/. Correcting these values with the values of l allows the system to be more /\reactive/"/, at the same time avoiding following all the network / uctuations/. Agent/'s decisions are taken on the basis of a combination of a long/-term $$l _ { n } = 1 - \frac { q _ { n } } { \sum _ { n = 1 } ^ { N _ { k } } q _ { n } ^ { k } } .$$ learning process and an instantaneous heuristic prediction/. In all the experiments we ran/, we observed that the introduced correction is a very e/ective mechanism/. Depending on the characteristics of the problem/, the best value to assign to the weight / can vary/, but if / ranges between /0/./2 and /0/./5/, performance doesn/'t change appreciably/. For lower values/, the e/ect of l is vanishing/, while for higher values the resulting routing tables oscillate and/, in both cases/, performance - to update the routing tables /(see below/)/. /5/. When the destination node d is reached/, the agent Fs/!d generates another agent - degrades/. /4/. If a cycle is detected/, that is/, if an ant is forced to return to an already visited node/, the cycle/'s nodes are popped from the ant/'s stack and all the memory about them is destroyed/. If the cycle lasted longer than the lifetime of the ant before entering the cycle/, /(that is/, if the cycle is greater than half the ant/'s age/) the ant is destroyed/. In fact/, in this case the agent wasted a lot of time probably because of a wrong sequence of decisions and not because of congestion states/. Therefore/, the agent is carrying an old and misleading memory of the network state and it is counterproductive to use it /(backward ant/) B d/!s /, transfers to it all of its memory/, and dies/. /3/2/7 Di Caro /& Dorigo - /6/. The backward ant takes the same path as that of its corresponding forward ant/, but in the opposite direction/. /8 At each node k along the path it pops its stack S s/!d /(k/) to know the next hop node/. Backward ants do not share the same link queues as data packets/; they use higher priority queues/, because their task is to quickly propagate to - described with respect to a generic /\destination/" node d /0 /2 S k/!d /. i/) Mk is updated with the values stored in the stack memory S s/!d /(k/)/. The time elapsed to arrive /(for the forward ant/) to the destination node d /0 starting from the current node is used to update the mean and variance estimates/, / d /0 and / d /0 /2 /, and the best value over the observation window W d /0/. In this way/, a parametric model of the traveling time to destination d /0 is maintained/. The mean value of this time and its dispersion can vary strongly/, depending on the tra/c conditions/: a poor time /(path/) under low tra/c load can be a very good one under heavy tra/c load/. The statistical model has to be able to capture this variability and to follow in a robust way the / uctuations of the tra/c/. This model plays a critical role in the routing table updating process /(see item /(ii/) below/)/. Therefore/, we investigated several ways to build e/ective and computationally inexpensive - the routing tables the information accumulated by the forward ants/. /7/. Arriving at a node k coming from a neighbor node f/, the backward ant updates the two main data structures of the node/, the local model of the tra/c M k and the rout/ing table T k /, for all the entries corresponding to the /(forward ant/) destination node d/. With some precautions/, updates are performed also on the entries corresponding to every node k /0 /2 S k/!d /; k /0 /6/= d on the /\sub/-paths/" followed by ant F s/!d after visit/ing the current node k/. In fact/, if the elapsed trip time of a sub/-path is statistically /\good/" /(i/.e/./, it is less than / /+ I/(//; //)/, where I is an estimate of a con/dence interval for //)/, then the time value is used to update the corresponding statistics and the routing table/. On the contrary/, trip times of sub/-paths not deemed good/, in the same statistical sense as de/ned above/, are not used because they don/'t give a correct idea of the time to go toward the sub/-destination node/. In fact/, all the forward ant routing decisions were made only as a function of the destination node/. In this perspective/, sub/-paths are side e/ects/, and they are intrinsically sub/-optimal because of the local variations in the tra/c load /(we can/'t reason with the same perspective as in dynamic programming/, because of the non/-stationarity of the problem representation/)/. Obvi/ously/, in case of a good sub/-path we can use it/: the ant discovered/, at zero cost/, an additional good route/. In the following two items the way M and T are updated is - models/, as described in the following Section /4/./2/. ii/) The routing table T k is changed by incrementing the probability P fd /0 /(i/.e/./, the probability of choosing neighbor f when destination is d /0 /) and decrementing/, by normalization/, the other probabilities P nd /0/. The amount of the variation in the probabilities depends on a measure of goodness we associate with the trip time Tk/!d /0 experienced by the forward ant/, and is given below/. This time represents the only available explicit feedback signal to score paths/. It gives a clear indica/- a reasonable assumption/. tion about the goodness r of the followed route because it is proportional to its /8/. This assumption requires that all the links in the network are bi/-directional/. In modern networks this is /3/2/8 AntNet/: Distributed Stigmergetic Control for Communications Networks length from a physical point of view /(number of hops/, transmission capacity of the used links/, processing speed of the crossed nodes/) and from a tra/c congestion The probability P fd /0 point of view /(the forward ants share the same queues as data packets/)/. The time measure T/, composed by all the sub/-paths elapsed times/, cannot be associated with an exact error measure/, given that we don/'t know the /\optimal/" trip times/, which depend on the whole network load status/. /9 Therefore/, T can only be used as a reinforcement signal/. This gives rise to a credit assignment problem typical of the reinforcement learning /eld /(Bertsekas /& Tsitsiklis/, /1/9/9/6/; Kaelbling et al/./, /1/9/9/6/)/. We de/ne the reinforcement r / r/(T/; M k /) to be a function of the goodness of the observed trip time as estimated on the basis of the local tra/c model/. r is a dimensionless value/, r /2 /(/0/; /1/]/, used by the current node k as a positive reinforcement for the node f the backward ant B d/!s comes from/. r takes into account some average of the so far observed values and of their dispersion to score the goodness of the trip time T /, such that the smaller T is/, the higher r is /(the exact de/nition of r is discussed in the next subsection/)/. Pfd /0 / P fd /0 /+ r/(/1 /BnZr P fd /0 /)/: /(/5/) In this way/, the probability P fd /0 will be increased by a value proportional to the reinforcement received and to the previous value of the node probability /(that is/, given a same reinforcement/, small probability values are increased proportionally more than big probability values/, favoring in this way a quick exploitation of new/, $$P _ { f d } ^ { r } P _ { f d } ^ { r } + r ( 1 - P _ { f d } ^ { r } ) .$$ and good/, discovered paths/)/. Probabilities P nd /0 for destination d /0 of the other neighboring nodes n implicitly receive a negative reinforcement by normalization/. That is/, their values are Pnd /0 / P nd /0 /BnZr rPnd /0/; n /2 N k /; n /6/= f/: /(/6/) It is important to remark that every discovered path receives a positive reinforce/ment in its selection probability/, and the reinforcement is /(in general/) a non/-linear function of the goodness of the path/, as estimated using the associated trip time/. In this way/, not only the /(explicit/) assigned value r plays a role/, but also the /(implicit/) ant/'s arrival rate/. This strategy is based on trusting paths that receive either high reinforcements/, independent of their frequency/, or low and frequent reinforcements/. In fact/, for any tra/c load condition/, a path receives one or more high reinforcements only if it is much better than previously explored paths/. On the other hand/, during a transient phase after a sudden increase in network load all paths will likely have high traversing times with respect to those learned by the model M in the preceding/, low congestion/, situation/. Therefore/, in this case $$\frac { P _ { n d } + } { P _ { n d } - r P _ { n d } , n \in N _ { k } , n \neq f . }$$ good paths can only be di/erentiated by the frequency of ants/' arrivals/. /9/. When the network is in a congested state/, all the trip times will score poorly with respect to the times observed in low load situations/. Nevertheless/, a path with a high trip time should be scored as a good path if its trip time is signi/cantly lower than the other trip times observed in the same congested /3/2/9 situation/. Di Caro /& Dorigo Assigning always a positive/, but low/, reinforcement value in the case of paths with high traversal time allows the implementation of the above mechanism based on the frequency of the reinforcements/, while/, at the same time/, avoids giving we set / to /1/./2/)/. Figure /2 gives a high/-level description of the algorithm in pseudo/-code/, while Figure /3 illustrates a simple example of the algorithm behavior/. A detailed discussion of the characteristics of the algorithm is postponed to Section /8/, after the performance of the algorithm has been analyzed with respect to a set of competitor algorithms/. In this way/, the characteristics of AntNet can be meaningfully evaluated and compared to those of other excessive credit to paths with high traversal time due to their poor quality/. The use of probabilistic entries is very speci/c to AntNet and we observed it to be e/ective/, improving the performance/, in some cases/, even by /3/0/%/-/4/0/%/. Routing tables are used in a probabilistic way not only by the ants but also by the data packets/. This has been observed to improve AntNet performance/, which means that the way the routing tables are built in AntNet is well matched with a probabilistic distribution of the data packets over all the good paths/. Data packets are prevented from choosing links with very low probability by re/mapping the T /'s entries by means of a power function f/(p/) /= p / /; / /> /1/, which emphasizes high probability values and reduces lower ones /(in our experiments ## state/-of/-the/-art algorithms/. stability and adaptivity/. We investigated several ways to assign the r values trying to take into account the above /4/./2 How to Score the Goodness of the Ant/'s Trip Time The reinforcement r is a critical quantity that has to be assigned by considering three main aspects/: /(i/) paths should receive an increment in their selection probability proportional to their goodness/, /(ii/) the goodness is a relative measure/, which depends on the tra/c conditions/, that can be estimated by means of the model M/, and /(iii/) it is important not to follow all the tra/c / uctuations/. This last aspect is particularly important/. Uncontrolled oscillations in the routing tables are one of the main problems in shortest paths routing /(Wang /& Crowcroft/, /1/9/9/2/)/. It is very important to be able to set the best trade/-o/ between - three requirements/: / The simplest way is to set r /= constant/: independently of the ant/'s /\experiment outcomes/"/, the discovered paths are all rewarded in the same way/. In this simple but meaningful case/, what is at work is the implicit reinforcement mechanism due to the di/erentiation in the ant arrival rates/. Ants traveling along faster paths will arrive at a higher rate than other ants/, hence their paths will receive a higher cumulative reward/. /1/0 The obvious problem of this approach lies in the fact that/, although ants following longer paths arrive delayed/, they will nevertheless have the same e/ect on communicating by means of pheromone trails /(Goss et al/./, /1/9/8/9/; Beckers et al/./, /1/9/9/2/)/. the routing tables as the ants who followed shorter paths/. /1/0/. In this case/, the core of the algorithm is based on the capability of /\real/" ants to discover shortest paths /3/3/0 AntNet/: Distributed Stigmergetic Control for Communications Networks ``` ``` with the ants/. end foreach Figure /2/: AntNet/'s top/-level description in pseudo/-code/. All the described actions take place in a completely distributed and concurrent way over the network nodes /(while/, in the text/, AntNet has been described from an individual ant/'s perspective/)/. All the constructs at the same level of indentation inside the context of the statement in parallel are executed concurrently/. The processes of data generation and forwarding are not described/, but they can be thought as acting concurrently /3/3/1 Di Caro /& Dorigo Figure /3/: Example of AntNet behavior/. The forward ant/, F/1/!/4 /, moves along the path /1 /! /2 /! /3 /! /4 and/, arrived at node /4/, launches the backward ant B/4/!/1 that will travel in the opposite direction/. At each node k/; k /= /3/; /: /: /: /; /1/, the backward ant will use the stack contents S /1/!/4 /(k/) to update the values for M k /(/ /4 /; / /4 /2 /; W/4 /)/, and/, in case of good sub/-paths/, to update also the values for M k /(/ i /; / i /2 /; Wi/)/; i /= k /+ /1/; /: /: /: /; /3/. At the same time the routing table will be updated by incrementing the goodness Pj/4 /, j /= k /+ /1/, of the last node k /+ /1 the ant B/4/!/1 came from/, for the case of node i /= k /+ /1/; /: /: /: /; /4 as destination node/, and decrementing the values of P for the other neighbors /(here not shown/)/. The increment will be a function of the trip time experienced by the forward ant going from node k to destination node i/. As for M/, the routing table is always updated for the case of node /4 as destination/, while the other nodes i /0 /= k /+ /1/; /: /: /: /; /3 on the sub/-paths are taken in consideration as destination nodes only if the trip time associated to <details> <summary>Image 2 Details</summary>  ### Visual Description ## Diagram: Bidirectional Ant Process Flow ### Overview The image displays a linear, bidirectional process diagram consisting of four numbered nodes connected by curved arrows. The diagram illustrates two opposing directional flows between the nodes, labeled as "Forward Ant" and "Backward Ant." ### Components/Axes * **Nodes:** Four circular nodes, numbered sequentially from left to right: `1`, `2`, `3`, `4`. * **Arrows (Forward Flow):** Three curved arrows pointing from left to right, connecting: * Node 1 to Node 2 * Node 2 to Node 3 * Node 3 to Node 4 * **Arrows (Backward Flow):** Three curved arrows pointing from right to left, connecting: * Node 4 to Node 3 * Node 3 to Node 2 * Node 2 to Node 1 * **Labels:** * **Top Label (Forward Ant):** Positioned above the forward arrows. Text: `Forward Ant (1 → 4)`. A small right-pointing arrow (`→`) is placed to the right of this text. * **Bottom Label (Backward Ant):** Positioned below the backward arrows. Text: `(1 ← 4) Backward Ant`. A small left-pointing arrow (`←`) is placed to the left of this text. ### Detailed Analysis The diagram defines a closed-loop system with four states or stages. 1. **Forward Process:** The "Forward Ant" initiates at Node 1 and progresses sequentially through Node 2 and Node 3, terminating at Node 4. This is represented by the top set of arrows and the label `(1 → 4)`. 2. **Backward Process:** The "Backward Ant" initiates at Node 4 and progresses in reverse sequence through Node 3 and Node 2, terminating at Node 1. This is represented by the bottom set of arrows and the label `(1 ← 4)`. 3. **Spatial Layout:** The nodes are arranged in a straight horizontal line. The forward arrows arc above the central line connecting the nodes, while the backward arrows arc below it, creating a symmetrical, elliptical pattern of flow. ### Key Observations * The system is perfectly symmetrical and reversible. The path from 1 to 4 is the exact inverse of the path from 4 to 1. * Each node (except the endpoints 1 and 4) serves as both a destination and an origin for both forward and backward flows. * The terminology "Ant" suggests this may model a process in computer science (e.g., ant colony optimization algorithms), biology (e.g., neural pathways), or logistics (e.g., bidirectional transport). ### Interpretation This diagram represents a **bidirectional, sequential process**. It models a system where an entity (an "Ant") can traverse a series of stages in one direction and then return along the same path in the opposite direction. The core concept is **reversibility**. * **What it demonstrates:** It visually defines two complementary processes that share the same pathway but have opposite directions and endpoints. It emphasizes that the system state at Node 1 is the start for the forward process and the end for the backward process, and vice versa for Node 4. * **Relationships:** The elements relate through strict sequential order and directional dependency. The forward flow is dependent on completing the previous step (1→2→3→4), and the backward flow is its precise mirror (4→3→2→1). * **Notable Pattern:** The most significant feature is the **closed loop**. While not drawn as a circle, the combination of the forward and backward paths creates a complete cycle: 1→2→3→4→3→2→1. This implies the process can repeat indefinitely. * **Potential Context:** In algorithmic contexts, this could represent a two-pass process (e.g., a forward pass for computation and a backward pass for error propagation in neural networks). In logistics, it could model a delivery route and its return journey. The diagram abstracts the specific nature of the "Ant" and the nodes, focusing purely on the directional relationship between them. </details> the corresponding sub/-path of the forward ant is statistically good/. In the experiments we ran with this strategy/, the algorithm showed moderately good performance/. These results suggest that the /\implicit/" component of the algorithm/, based on the ant arrival rate/, plays a very important role/. Of course/, to compete with and that we used in the reported experiments/: - state/-of/-the/-art algorithms/, the available information about path costs has to be used/. / More elaborate approaches de/ne r as a function of the ant/'s trip time T /, and of the parameters of the local statistical model M/. We tested several alternatives/, by using di/erent linear/, quadratic and hyperbolic combinations of the T and M values/. In the following we limit the discussion to the functional form that gave the best results/, $$r = c _ { 1 } ( \frac { W _ { best } } { T } ) + c _ { 2 } ( \frac { I _ { sup } - I _ { in } } { ( I _ { sup } - I _ { in } ) } ) .$$ observations/, with the short/-term mean evaluated over a fraction c of the samples used for T /(I sup /BnZr I inf /) /+ /(T /BnZr I inf /) In Equation /7/, Wbest is the best trip time experienced by the ants traveling toward the destination d/, over the last observation window W/. The maximum size of the window /(the maximum number of considered samples before resetting the W best value/) is assigned on the basis of the coe/cient / of Equation /1/. As we said/, / weights the number of samples e/ectively giving a contribution to the value of the / estimate/, de/ning a sort of moving exponential window/. Following the expression for the number of e/ective samples as reported in footnote /7/, we set jWjmax /= /5/(c/=//)/, with c /< /1/. In this way/, the long/term exponential mean and the short/-term windowing are referring to a comparable set of /3/3/2 AntNet/: Distributed Stigmergetic Control for Communications Networks the long/-term one/. I sup and I inf are convenient estimates of the limits of an approximate con/dence interval for //. I inf is set to Wbest /, while I sup /= / /+ z/(//= p jWj/)/, with z /= /1/= p /(/1 /BnZr / /) where / gives the selected con/dence level/. /1/1 There is some level of arbitrariness in our computation of the con/dence interval/, because we set it in an asymmetric way and / and / are not arithmetic estimates/. Anyway/, what we need is a quick/, raw estimate of the mean value and of the dispersion of the values /(for example/, a local bootstrap procedure could have been applied to extract a meaningful con/dence interval/, but such a choice is incredibly varied in terms of tra/c/, topologies/, switch and transmission characteristics/, etc/. The value r obtained from Equation /7 is /nally transformed by means of a squash not reasonable from a CPU time/-consuming perspective/)/. The /rst term in Equation /7 simply evaluates the ratio between the current trip time and the best trip time observed over the current observation window/. This term is corrected by the second one/, that evaluates how far the value T is from I inf in relation to the extension of the con/dence interval/, that is/, considering the stability in the latest trip times/. The coe/cients c /1 and c/2 weight the importance of each term/. The /rst term is the most important one/, while the second term plays the role of a correction/. In the current implementation of the algorithm we set c /1 /= /0/:/7 and c /2 /= /0/:/3/. We observed that c /2 shouldn/'t be too big /(/0/./3/5 is an upper limit/)/, otherwise performance starts to degrade appreciably/. The behavior of the algorithm is quite stable for c /2 values in the range /0/./1/5 to /0/./3/5 but setting c /2 below /0/./1/5 slightly degrades performance/. The algorithm is very robust to changes in / /, which de/nes the con/dence level/: varying the con/dence level in the range from /7/5/% to /9/5/% changes performance little/. The best results have been obtained for values around /7/5/%//8/0/%/. We observed that the algorithm is very robust to its internal parameter settings and we didn/'t try to /\adapt/" the set of parameters to the problem instance/. All the di/erent experiments were carried out with the same /\reasonable/" settings/. We could surely improve the performance by means of a /ner tuning of the parameters/, but we didn/'t because we were interested in implementing a robust system/, considering that the world of networks is function s/(x/)/: $$s ( x ) = ( 1 + e ^ { x p } ( - \frac { a } { x } ) ) ^ { - 1 } , x \in (0,1), a \in [ N _ { k } ]$$ $$r ^ { s ( r ) } \frac { s ( 1 ) } { r }$$ way an emphasis is put on good results/, while bad results play a minor role/. /1/1/. The expression is obtained by using the Tchebyche/ inequality that allows the de/nition of a con/dence interval for a random variable following any distribution /(Papoulis/, /1/9/9/1/) Usually/, for speci/c probability densities the Tchebyche/ bound is too high/, but here we can conveniently use it because /(i/) we want to avoid to make assumptions on the distribution of / and/, /(ii/) we need only a raw estimate of the /3/3/3 s/(/1/) Squashing the r values allows the system to be more sensitive in rewarding good /(high/) values of r/, while having the tendency to saturate the rewards for bad /(near to zero/) r values/: the scale is compressed for lower values and expanded in the upper part/. In such a con/dence interval/. of neighbor nodes/. Di Caro /& Dorigo The coe/cient a/=jN k j determines a parametric dependence of the squashed reinforcement value on the number jNk j of neighbors of the reinforced node k/: the greater the number of neighbors/, the higher the reinforcement /(see Fig/ure /4/)/. The reason to do this is that we want to have a similar/, strong/, e/ect of good results on the probabilistic rout/ing tables/, independent of the number <details> <summary>Image 3 Details</summary>  ### Visual Description ## Line Chart: Normalized Similarity Function s(r)/s(1) vs. Distance r ### Overview The image is a 2D line chart plotting a normalized function, `s(r)/s(1)`, against a variable `r`. The chart displays four distinct curves, each corresponding to a different number of "neighbors" (2, 3, 4, and 5). All curves originate near the origin (0,0) and converge at the point (1,1), exhibiting a monotonic, S-shaped (sigmoidal) increase. The chart is presented in grayscale with different line styles to differentiate the data series. ### Components/Axes * **Chart Type:** 2D Line Chart. * **X-Axis:** * **Label:** `r` * **Scale:** Linear, ranging from 0 to 1. * **Major Ticks:** 0, 0.2, 0.4, 0.6, 0.8, 1.0. * **Y-Axis:** * **Label:** `s(r)/s(1)` * **Scale:** Linear, ranging from 0 to 1. * **Major Ticks:** 0, 0.2, 0.4, 0.6, 0.8, 1.0. * **Legend:** * **Position:** Top-left corner of the plot area. * **Entries (from top to bottom):** 1. `5 neighbors` - Represented by a solid line. 2. `4 neighbors` - Represented by a dashed line. 3. `3 neighbors` - Represented by a dotted line. 4. `2 neighbors` - Represented by a dash-dot line. ### Detailed Analysis The chart compares the behavior of the function `s(r)/s(1)` for different neighbor counts as `r` increases from 0 to 1. * **General Trend:** All four curves are monotonically increasing. They start with a shallow slope near `r=0`, steepen in the middle range of `r`, and then flatten as they approach the convergence point at (1,1). * **Series-Specific Behavior (from highest to lowest curve at a given `r`):** 1. **5 neighbors (Solid Line):** This curve is the highest for all `r` values between 0 and 1. It begins its noticeable ascent earliest (around `r=0.1`) and maintains the steepest slope through the middle range. 2. **4 neighbors (Dashed Line):** This curve lies just below the "5 neighbors" line. Its trajectory is very similar but slightly delayed and less steep. 3. **3 neighbors (Dotted Line):** This curve is positioned below the "4 neighbors" line. It shows a more pronounced delay in its ascent compared to the higher neighbor counts. 4. **2 neighbors (Dash-Dot Line):** This is the lowest curve. It remains close to zero for the longest duration (until approximately `r=0.3`) and has the most gradual slope, resulting in the latest approach to the value of 1. * **Convergence:** All lines meet precisely at the coordinate (1, 1), indicating that `s(r)/s(1) = 1` when `r = 1`, regardless of the neighbor count. ### Key Observations 1. **Monotonic Ordering:** There is a strict, consistent ordering of the curves. For any given `r` between 0 and 1, the value of `s(r)/s(1)` increases with the number of neighbors: `5 neighbors > 4 neighbors > 3 neighbors > 2 neighbors`. 2. **Sigmoidal Shape:** The curves are not linear; they exhibit an S-shape, suggesting a phase of slow initial growth, rapid transition, and then saturation. 3. **Convergence Point:** The forced convergence at (1,1) is a defining feature, implying `s(1)` is the normalization factor for the function `s(r)`. 4. **Line Style Clarity:** The use of distinct line styles (solid, dashed, dotted, dash-dot) effectively differentiates the series in a monochrome format. ### Interpretation This chart likely illustrates a concept from machine learning, statistics, or spatial analysis, specifically related to **k-Nearest Neighbors (k-NN)** or a similar distance-based similarity metric. * **What `r` and `s(r)` represent:** `r` is almost certainly a **normalized distance** (e.g., distance divided by the maximum distance in the dataset or to the k-th neighbor). `s(r)` is a **similarity or affinity function** that decreases with distance. The plot shows `s(r)` normalized by its value at `r=1` (`s(1)`), which is the similarity at the maximum considered distance. * **The Role of "Neighbors":** The parameter (2, 3, 4, 5 neighbors) is `k`. The chart demonstrates how the **effective similarity profile** changes with `k`. * **Core Insight:** The data suggests that **increasing `k` (the number of neighbors) makes the similarity function `s(r)` more "aggressive" or "confident."** For the same normalized distance `r`, a query point is considered more similar to its neighborhood when that neighborhood is larger (higher `k`). This is because with more neighbors, the distance to the farthest one (`r=1`) is relatively larger, so intermediate distances represent a smaller fraction of the total neighborhood spread, warranting a higher similarity score. * **Practical Implication:** In a k-NN classifier or regressor, using a higher `k` would mean that points need to be relatively closer (smaller `r`) to be considered highly similar, but the similarity score for points at a medium distance would be higher compared to a lower `k` setting. This affects decision boundaries and smoothing. The chart provides a visual, quantitative comparison of this effect for small values of `k`. </details> r Figure /4/: Examples of squash functions with a variable number of node neighbors/. /5/. Routing Algorithms Used for Comparison To evaluate the performance of AntNet/, we compared it with state/-of/-the/-art routing algo/rithms from the telecommunications and machine learning /elds/. The following algorithms/, belonging to the various possible combinations of static and adaptive/, distance/-vector and and on/-/eld knowledge they have about tra/c workloads/. SPF /(adaptive/, link/-state/)/: is the prototype of link/-state algorithms with dynamic met/ric for link costs evaluations/. A similar algorithm was implemented in the second version of ARPANET /(McQuillan/, Richer/, /& Rosen/, /1/9/8/0/) and in its successive revi/sions /(Khanna /& Zinky/, /1/9/8/9/)/. Our implementation uses the same / ooding algorithm/, while link costs are assigned over a discrete scale of /2/0 values by using the ARPANET hop/-normalized/-delay metric /1/2 /(Khanna /& Zinky/, /1/9/8/9/) and the the statistical win/dow average method described in /(Shankar/, Alaettino/ glu/, Dussa/-Zieger/, /& Matta/, /1/9/9/2a/)/. Link costs are computed as weighted averages between short and long/-term link/-state classes /(see Appendix A/)/, have been implemented and used to run comparisons/. OSPF /(static/, link state/)/: is our implementation of the current Interior Gateway Pro/tocol /(IGP/) of Internet /(Moy/, /1/9/9/8/)/. Being interested in studying routing under the assumptions described in Section /3/, the routing protocol we implemented does not mirror the real OSPF protocol in all its details/. It only retains the basic features of OSPF/. Link costs are statically assigned on the basis of their physical characteristics and routing tables are set as the result of the shortest /(minimum time/) path com/putation for a sample data packet of size /5/1/2 bytes/. It is worth remarking that this choice penalizes our version of OSPF with respect to the real one/. In fact/, in the real Internet link costs are set by network administrators who can use additional heuristic real/-valued statistics re/ ecting the delay /(e/.g/./, utilization/, queueing and//or transmis//1/2/. The transmitting node monitors the average packet delay d /(queuing and transmission/) and the average packet transmission time t over /x observation windows/. From these measures/, assuming an M//M///1 queueing model /(Bertsekas /& Gallager/, /1/9/9/2/)/, a link utilization cost measure is calculated as /1 /BnZr t/=d/. /3/3/4 AntNet/: Distributed Stigmergetic Control for Communications Networks sion delay/, etc/./) over /xed time intervals/. Obtained values are rescaled and saturated by a linear function/. We tried several additional discrete and real/-valued metrics but the discretized hop/-normalized/-delay gave the best results in terms of performance and stability/. Using a discretized scale reduces the sensitivity of the algorithm but at - to that of the basic adaptive Bellman/-Ford/. Q/-R /(adaptive/, distance/-vector/)/: is the Q/-Routing algorithm as proposed by Boyan and Littman /(/1/9/9/4/)/. This is an online asynchronous version of the Bellman/-Ford algorithm/. Q/-R learns online the values Q k /(d/; n/)/, which are estimates of the time to reach node d from node k via the neighbor node n/. Upon sending a packet P from k to neighbor node n with destination d/, a back packet P back is immediately generated from n to k/. Pback carries the information about the current time estimate t n/!d /= min n /0 /2Nn Qn/(d/; n /0 /) held at node n about the time to go for destination d/, and the sum t Pk/!n of the queuing and transmission time experienced by P since its arrival at node k/. The sum Qnew/(d/; n/) /= t n/!d /+ t P k/!n is used to compute the variation - the same time reduces also undesirable oscillations/. BF /(adaptive/, distance/-vector/)/: is an implementation of the asynchronous distributed Bellman/-Ford algorithm with dynamic metrics /(Bertsekas /& Gallager/, /1/9/9/2/; Shankar et al/./, /1/9/9/2a/)/. The algorithm has been implemented following the guidelines of Ap/pendix A/, while link costs are assigned in the same way as described for SPF above/. Vector/-distance Bellman/-Ford/-like algorithms are today in use mainly for intra/-domain routing/, because they are used in the Routing Information Protocol /(RIP/) /(Malkin /& Steenstrup/, /1/9/9/5/) supplied with the BSD version of Unix/. Several enhanced ver/sions of the basic adaptive Bellman/-Ford algorithm can be found in the literature /(for example the Merlin/-Segall /(Merlin /& Segall/, /1/9/7/9/) and the Extended Bellman/-Ford /(Cheng/, Riley/, Kumar/, /& Garcia/-Luna/-Aceves/, /1/9/8/9/) algorithms/)/. They focus mainly on reducing the information dissemination time in case of link failures/. When link failures are not a major issue/, as in this paper/, their behavior is in general equivalent - /
Qk /(d/; n/) /= //(Q new /(d/; n/) /BnZr Q k /(d/; n/)/) of the Q/-learning/-like value Q k /(d/; n/)/. PQ/-R /(adaptive/, distance/-vector/)/: is the Predictive Q/-Routing algorithm /(Choi /& Ye/ung/, /1/9/9/6/)/, an extension of Q/-Routing/. In Q/-routing the best link /(i/.e/./, the one with the lowest Qk/(d/; n/)/) is deterministically chosen by packets/. Therefore/, a link that happens to have a high expected Q k /(d/; n/)/, for example because of a temporary load condition/, will never be used again until all the other links exiting from the same node have a worse/, that is higher/, Q k /(d/; n/)/. PQ/-R learns a model of the rate of variation of links/' queues/, called the recovery rate/, and uses it to probe those links that/, although network and then calculating instantaneous /\real/" costs for all the links and assigning - not having the lowest Q k /(d/; n/)/, have a high recovery rate/. Daemon /(adaptive/, optimal routing/)/: is an approximation of an ideal algorithm/. It de/nes an empirical bound on the achievable performance/. It gives some informa/tion about how much improvement is still possible/. In the absence of any a priori assumption on tra/c statistics/, the empirical bound can be de/ned by an algorithm possessing a /\daemon/" able to read in every instant the state of all the queues in the /3/3/5 hop/. Di Caro /& Dorigo paths on the basis of a network/-wide shortest paths re/-calculation for every packet b l b l b l /; where d l is the transmission delay for link l/, b l is its bandwidth/, S p is the size /(in bits/) of the data packet doing the hop/, S Q/(l/) is the size /(in bits/) of the queue of link l/, / SQ/(l/) is the exponential mean of the size of links queue and it is a correction to the actual size of the link queue on the basis of what observed until that moment/. This correction is weighted by the / value set to /0/./4/. Of course/, given the arbitrariness we introduced in calculating C l /, it could be possible to de/ne an even better Daemon $$\begin{array}{ll} C _ { l } = d _ { 1 } + \frac { S _ { p } } { b _ { 1 } } + \frac { S _ { q ( l ) } } { b _ { 1 } } + \frac { S _ { q ( l ) } } { b _ { 1 } } , \end{array}$$ ## algorithm/. /6/. Experimental Settings The functioning of a communication network is governed by many components/, which may interact in nonlinear and unpredictable ways/. Therefore/, the choice of a meaningful testbed ## are explained/. to compare competing algorithms is no easy task/. A limited set of classes of tunable components is de/ned and for each class our choices /6/./1 Topology and physical properties of the net Topology can be de/ned on the basis of a real net instance or it can de/ned by hand/, to better analyze the in/ uence of important topological features /(like diameter/, connectivity/, For both/, fault probability distributions should be de/ned/. In our experiments/, we used three signi/cant net instances with increasing numbers of nodes/. For all of them we describe the main characteristics and we summarize the topological properties by means of a triple of numbers /(//, //, N/) indicating respectively the mean shortest path distance/, in terms of hops/, between all pairs of nodes/, the variance of this average/, and the total number of nodes/. From these three numbers we can get an idea about the degree of connectivity and balancing of the network/. The di/culty of the routing etc/./)/. Nodes are mainly characterized by their bu/ering and processing capacity/, whereas links are characterized by their propagation delay/, bandwidth and streams multiplexing scheme/. - problem roughly increases with the value of these numbers/. / SimpleNet /(/1/./9/, /0/./7/, /8/) is a small network speci/cally designed to study some aspects of the behavior of the algorithms we compare/. Experiments with SimpleNet were designed to closely study how the di/erent algorithms manage to distribute the load on the di/erent possible paths/. SimpleNet is composed of /8 nodes and /9 bi/-directional links with a bandwidth of /1/0 Mbit//s and propagation delay of /1 msec/. The topology composed of /1/4 nodes and /2/1 bi/-directional links with a bandwidth of /1/./5 Mbit//s/. - is shown in Figure /5/. / NSFNET /(/2/./2/, /0/./8/, /1/4/) is the old USA T/1 backbone /(/1/9/8/7/)/. NSFNET is a WAN /3/3/6 Its AntNet/: Distributed Stigmergetic Control for Communications Networks Figure /5/: SimpleNet/. Numbers within circles are node identi/ers/. Shaded nodes have a special interpretation in our experiments/, described later/. Each edge in the graph represents a pair of directed links/. Link bandwidth is /1/0 Mbit//sec/, propagation <details> <summary>Image 4 Details</summary>  ### Visual Description ## Directed Graph Diagram: Numbered Node Network ### Overview The image displays a directed graph (network diagram) consisting of 9 numbered nodes connected by directed edges (arrows). Three nodes (1, 6, and 9) are highlighted in yellow, while the remaining nodes (2, 3, 4, 5, 7, 8) are white. The diagram illustrates a complex set of relationships and pathways between the nodes. ### Components * **Nodes:** 9 circular nodes, each containing a unique integer from 1 to 9. * **Yellow Nodes:** 1, 6, 9 * **White Nodes:** 2, 3, 4, 5, 7, 8 * **Edges:** Directed lines (arrows) connecting nodes, indicating a one-way relationship or flow from the source node to the target node. * **Spatial Layout:** * Node 1 is positioned at the top-center. * Node 9 is to the right of Node 1. * Node 8 is to the left of Node 1. * The graph generally flows downward from Node 1, with Nodes 2, 3, 4, 5, 6, and 7 forming a central column or network. * Node 7 is at the bottom-center. ### Detailed Analysis: Connectivity and Flow The following describes all directed connections (edges) visible in the diagram: 1. **From Node 1 (Yellow):** * Arrow points to Node 2 (top-right). * Arrow points to Node 3 (directly below). * Arrow points to Node 8 (top-left). 2. **From Node 2:** Arrow points to Node 4 (below and slightly right). 3. **From Node 3:** Arrow points to Node 5 (below). 4. **From Node 4:** Arrow points to Node 5 (below and slightly left). 5. **From Node 5:** Arrow points to Node 6 (Yellow, below). 6. **From Node 6 (Yellow):** Arrow points to Node 7 (below). 7. **From Node 7:** Arrow points to Node 8 (above-left). 8. **From Node 8:** Arrow points back to Node 1 (above-right), completing a cycle. 9. **From Node 9 (Yellow):** * Arrow points to Node 1 (left). * Arrow points to Node 4 (below-left). **Flow Summary:** The graph contains multiple interconnected paths and cycles. A primary cycle exists: `1 → 3 → 5 → 6 → 7 → 8 → 1`. Another path is `1 → 2 → 4 → 5 → 6 → 7 → 8 → 1`. Node 9 acts as an external input, feeding into both Node 1 and Node 4. ### Key Observations * **Node 1 is a major hub:** It has the highest out-degree (3 outgoing edges to nodes 2, 3, 8) and is part of multiple cycles. * **Node 5 is a convergence point:** It receives directed edges from both Node 3 and Node 4. * **Cyclic Structure:** The graph contains at least two distinct cycles, indicating feedback loops or repetitive processes within the system it represents. * **Highlighted Nodes:** The yellow highlighting on Nodes 1, 6, and 9 may indicate they are of particular importance—such as start/end points, critical states, or external interfaces—though the specific meaning is not defined in the image. * **Bidirectional Relationship between 1 and 8:** While not a single bidirectional edge, the path `1 → 8` and `8 → 1` creates a two-step loop. ### Interpretation This diagram likely models a system where entities (nodes) have directed influences or transitions between them. The structure suggests: * **Process or Workflow:** It could represent stages in a process where work flows from one step to another, with cycles indicating review loops or iterative steps (e.g., `5→6→7→8→1→3→5`). * **State Machine:** Nodes could be states, and edges could be transitions triggered by events. The cycles represent possible state sequences that can repeat. * **Network Topology:** It might depict a communication or dependency network where information or resources flow along the arrows. Node 9's connections suggest it is an external controller or data source influencing two key parts of the network (Node 1 and Node 4). * **System Robustness/Complexity:** The multiple pathways between nodes (e.g., to reach Node 5 from Node 1, one can go via Node 3 or via Node 2→4) imply redundancy or alternative routes, which can be a sign of a robust or complex system design. The absence of a legend or descriptive labels means the specific domain (e.g., software architecture, organizational chart, biological pathway) cannot be determined. The yellow nodes are the most salient visual feature, prompting the viewer to consider their unique role within the network's dynamics. </details> delay is /1 msec/. topology is shown in Figure /6/. Propagation delays range from /4 to /2/0 msec/. NSFNET is a well balanced network/. Figure /6/: NSFNET/. Each edge in the graph represents a pair of directed links/. Link band/- <details> <summary>Image 5 Details</summary>  ### Visual Description ## Network Diagram: Unlabeled Graph Structure ### Overview The image displays an undirected network graph consisting of nodes (vertices) and edges (connections). There is no textual information, labels, titles, legends, or numerical data present in the image. The graph is purely structural, composed of gray circular nodes connected by black lines against a white background. ### Components/Axes * **Nodes:** 15 gray circles of uniform size and color. They are distributed across the plane with no apparent coordinate system or axis. * **Edges:** Straight black lines connecting pairs of nodes. The lines have uniform thickness and color. * **Labels/Text:** None. No node identifiers, edge weights, titles, or annotations are present. * **Legend:** None. * **Language:** No textual content is present in any language. ### Detailed Analysis **Spatial Grounding & Component Isolation:** The graph can be segmented into approximate regions for analysis: * **Left Cluster (Approx. 5 nodes):** A relatively dense grouping on the left side. One node at the far left connects to two others, forming a small triangle. Another node slightly inward connects to multiple nodes across the graph. * **Central Chain (Approx. 4 nodes):** A loose, horizontal chain of nodes runs through the center, connecting the left and right clusters. * **Right Cluster (Approx. 6 nodes):** A more complex and densely interconnected grouping on the right. This area contains the highest degree of connectivity, with several nodes acting as local hubs. * **Peripheral Nodes:** A few nodes are positioned at the top, bottom, and far right edges, connected by one or two edges to the main structure. **Connectivity & Flow:** * The graph is fully connected; there are no isolated nodes or separate components. * There is no indicated directionality (arrows), so all connections are bidirectional. * Node connectivity (degree) varies. Some nodes (e.g., one in the central chain and one in the right cluster) appear to have 4-5 connections, acting as local hubs. Others on the periphery have only 1-2 connections. ### Key Observations 1. **Absence of Metadata:** The complete lack of labels, keys, or scales makes it impossible to assign specific meaning, identity, or quantitative value to any element. 2. **Structural Patterns:** The graph exhibits small-world properties, with local clusters (left and right) connected by a few bridging nodes in the center. 3. **Visual Uniformity:** All nodes and edges are visually identical, implying no differentiation by type, weight, or capacity based on the visual information alone. 4. **Non-Planar Layout:** The edges cross each other multiple times, indicating the graph is not drawn in a planar fashion (where no edges cross). This is a common layout choice for readability rather than a property of the graph itself. ### Interpretation This image is a pure representation of a **network topology**. Its meaning is entirely dependent on external context not provided in the image. * **What it Demonstrates:** It shows a set of entities (nodes) and the relationships or connections between them (edges). The structure suggests a system where some entities are more central or influential (higher-degree nodes) than others. * **Potential Analogies:** Without labels, this could represent countless systems: a social network, a computer network, a neural pathway, a chemical interaction map, a transportation grid, or an organizational chart. * **Notable Anomalies:** The primary "anomaly" is the complete absence of explanatory data. For a technical document, this graph is a skeleton awaiting annotation. Its utility is in illustrating connectivity patterns, clustering, and network density in the abstract. * **Peircean Investigation:** The image is an **icon** (it resembles a network) and a **symbol** (its meaning is conventional, requiring learned interpretation). It lacks an **index** (a direct physical or causal link to a specific real-world system) because there are no labels to ground it. To be informative, it must be paired with a legend or accompanying text that defines what the nodes and edges represent. **Conclusion for Documentation:** This diagram effectively conveys the abstract structure of a connected network with 15 nodes and visible clustering. However, for it to serve as a technical document, it requires the addition of a key defining node identities, edge meanings, and possibly node/edge attributes (e.g., size for importance, color for type). As provided, it is a template of relationships without semantic content. </details> width is /1/./5 Mbit//sec/, propagation delays range from /4 to /2/0 msec/. - / NTTnet /(/6/./5/, /3/./8/, /5/7/) is the major Japanese backbone/. NTTnet is the NTT /(Nippon Telephone and Telegraph company/) /ber/-optic corporate backbone/. NTTnet is a /5/7 nodes/, /1/6/2 bi/-directional links network/. Link bandwidth is of /6 Mbit//sec/, while propagation delays range around /1 to /5 msec/. The topology is shown in Figure /7/. NTTnet is not a well balanced network/. Figure /7/: NTTnet/. Each edge in the graph represents a pair of directed links/. Link band/- <details> <summary>Image 6 Details</summary>  ### Visual Description ## Network Diagram: Unlabeled Graph Structure ### Overview The image displays a complex, unlabeled network diagram or graph structure. It consists of numerous nodes (vertices) connected by edges (links) against a plain white background. There is no textual information, labels, titles, legends, or numerical data present in the image. The diagram appears to represent a topological map, a network topology, or a graph theory visualization. ### Components/Axes * **Nodes:** Represented as small, solid green circles. There are approximately 60-70 nodes in total. * **Edges:** Represented as thin, gray lines connecting the nodes. The connections form a non-planar graph with multiple intersecting paths. * **Layout:** The graph is arranged in a roughly horizontal orientation, stretching from the left to the right side of the image. It is not organized into a standard grid or hierarchical tree. * **Text/Labels:** **None.** The diagram contains no axis titles, node labels, legend, or any form of textual annotation. ### Detailed Analysis * **Spatial Distribution:** The network is not uniformly dense. * **Left Region:** Features a relatively dense, interconnected cluster of nodes with many short connections, forming a mesh-like substructure. * **Central Region:** The density decreases slightly, with nodes forming longer, more linear chains that bridge the left and right sections. * **Right Region:** The structure becomes more elongated and sparse. A prominent feature is a long, winding chain of nodes that extends upward and to the right, resembling a "tail" or a primary backbone. This chain has several small offshoots. * **Connectivity Patterns:** * Most nodes have a degree (number of connections) between 2 and 4. * There are no obvious isolated nodes; the entire structure appears to be a single connected component. * The graph contains multiple cycles (closed loops) of varying sizes, particularly in the denser left region. * The long chain on the right has a more linear, path-like structure with fewer cycles. ### Key Observations 1. **Absence of Metadata:** The most significant observation is the complete lack of identifying information. The purpose, subject, and scale of the network are entirely undefined. 2. **Structural Heterogeneity:** The graph exhibits clear regional variation in density and connectivity, suggesting it may model a real-world system with different functional zones (e.g., a core cluster and peripheral branches). 3. **Visual Style:** The use of uniform green nodes and gray edges is simple and functional, prioritizing the display of connections over node differentiation. ### Interpretation * **What the Data Suggests:** Without labels, the diagram is an abstract representation of relationships. It demonstrates a system where entities (nodes) are interconnected in a complex, non-hierarchical web. The structure implies information flow, dependency, or connection paths that are not centralized. * **How Elements Relate:** The relationships are defined solely by the edges. The proximity of nodes in the layout may imply stronger connectivity or a shared function, but this is a visual artifact of the graph-drawing algorithm, not an explicit data point. The dense left cluster could represent a core network, while the extended right chain could represent a peripheral or access network. * **Notable Anomalies:** The primary anomaly is the lack of context. For a technical document, this diagram is incomplete. It serves only as a visual template of a network's shape. To be informative, it would require: * A title defining the network's nature (e.g., "Server Network Topology," "Neural Network Layer," "Social Graph Cluster"). * Node labels or a legend explaining what the green circles represent. * Edge labels or weights if the connections have varying properties. * A key for any color coding (though only one color is used here). **Conclusion for Technical Documentation:** This image provides a **structural template** of a complex network but contains **zero extractable factual data, labels, or textual information**. Its value is purely in illustrating the topology's shape—for a complete technical description, it must be accompanied by external explanatory text or labels that are not present in the image itself. </details> width is /6 Mbit//sec/, propagation delays range from /1 to /5 msec/. /3/3/7 ## sec/. Di Caro /& Dorigo All the networks are simulated with zero link/-fault and node/-fault probabilities/, local node bu/ers of /1 Gbit capacity/, and data packets maximum time to live /(TTL/) set to /1/5 /6/./2 Tra/c patterns Tra/c is de/ned in terms of open sessions between pairs of di/erent nodes/. Tra/c patterns can show a huge variety of forms/, depending on the characteristics of each session and on of service should be used to completely characterize a session/. Sessions over the network can be characterized by their inter/-arrival time distribution and by their geographical distribution/. The latter is controlled by the probability assigned their distribution from geographical and temporal points of view/. Each single session is characterized by the number of transmitted packets/, and by their size and inter/-arrival time distributions/. More generally/, priority/, costs and requested quality to each node to be selected as a session start or end/-point/. We considered three basic patterns for the temporal distribution of the sessions/, and three for their spatial distribution/. - new sessions/, i/.e/./, sessions inter/-arrival times are negative exponentially distributed/. / Fixed /(F/)/: at the beginning of the simulation/, for each node/, a /xed number of one/- - Temporal distributions/: / Poisson /(P/)/: for each node a Poisson process is de/ned which regulates the arrival of - to/-all sessions is set up and left constant for the remainder of the simulation/. / Temporary /(TMPHS/)/: a temporary/, heavy load/, tra/c condition is generated turning - Spatial distributions/: / Uniform /(U/)/: the assigned temporal characteristics for session arrivals are set identi/- on some nodes that act like hot spots /(see below/)/. - cally for all the network nodes/. / Random /(R/)/: in this case/, the assigned temporal characteristics for session arrivals are the other nodes/. General tra/c patterns have been obtained combining the above temporal and spatial characteristics/. Therefore/, for example/, UP tra/c means that/, for each node/, an identical Poisson process is regulating the arrival of new sessions/, while in the RP case the process is di/erent for each node/, and UP/-HS means that a Hot Spots tra/c model is superimposed - set in a random way over the network nodes/. / Hot Spots /(HS/)/: some nodes behave as hot spots/, concentrating a high rate of in/put//output tra/c/. A /xed number of sessions are opened from the hot spots to all to a UP tra/c/. Concerning the shape of the bit stream generated by each session/, we consider two basic compression standard/, which converts a video signal in a stream of /1/./5 Mbit//sec/. - types/: / Constant Bit Rate /(CBR/)/: the per/-session bit rate is maintained /xed/. Examples of applications of CBR streams are the voice signal in a telephone network/, which is converted into a stream of bits with a constant rate of /6/4 Kbit//sec/, and the MPEG/1 /3/3/8 AntNet/: Distributed Stigmergetic Control for Communications Networks - / Generic Variable Bit Rate /(GVBR/)/: the per/-session generated bit rate is time varying/. The term GVBR is a broad generalization of the VBR term normally used to designate a bit stream with a variable bit rate but with known average characteristics and expected//admitted / uctuations/. /1/3 Here/, a GVBR session generates packets whose sizes and inter/-arrival times are variable and follow a negative exponential distribution/. The information about these characteristics is never directly used by the routing ## generate a meaningful subset of real tra/c patterns/. algorithms/, like in IP/-based networks/. The values we used in the experiments to shape tra/c patterns are /\reasonable/" values for session generations and data packet production taking into consideration current network usage and computing power/. The mean of the packet size distribution has been set to /4/0/9/6 bits in all the experiments/. Basic temporal and spatial distributions have been chosen to be representative of a wide class of possible situations that can be arbitrarily composed to /6/./3 Metrics for performance evaluation Depending on the type of services delivered on the network and on their associated costs/, many performance metrics could be de/ned/. We focused on standard metrics for per/formance evaluation/, considering only sessions with equal costs/, bene/ts and priority and without the possibility of requests for special services like real/-time/. In this framework/, the measures we are interested in are/: throughput /(correctly delivered bits//sec/)/, delay distri/bution for data packets /(sec/)/, and network capacity usage /(for data and routing packets/)/, /6/./4 Routing algorithms parameters All the algorithms used have a collection of parameters to be set/. Common parameters are routing packet size and elaboration time/. Settings for these parameters are shown expressed as the sum of the used link capacities divided by the total available link capacity/. in table /1/. These parameters have been assigned to values used in previous simulation Packet size /(byte/) | | | | Q/-R PQ/-R | |--------|-------------|----|--------------| | AntNet | OSPF /& SPF | BF | /& | /2/4 /+ /8N h /6/4 /+ /8jN n j node n/, and N is the number of network nodes/. Packet elaboration time /(msec/) /3 /6 /2 /3 Table /1/: Routing packets characteristics for the implemented algorithms /(except for the Daemon algorithm/, which does not generate routing packets/)/. Nh is the incremen/tal number of hops made by the forward ant/, jN n j is the number of neighbors of works /(Alaettino/ glu et al/./, /1/9/9/2/) and//or on the basis of heuristic evaluations taking into /1/3/. The knowledge about the characteristics of the incoming CBR or VBR bit streams is of fundamental importance in networks able to deliver Quality of Service/. It is only on the basis of this knowledge that the network can accept//refuse the session requests/, and/, in case of acceptance/, allocate//reserve necessary /3/3/9 resources/. /2/4 /+ /1/2N /1/2 Di Caro /& Dorigo consideration information encoding schemes and currently available computing power /(e/.g/./, the size for forward ants has been determined as the same size of a BF packet plus /8 bytes for each hop to store the information about the node address and the elapsed time/)/. Concerning the other main parameters/, speci/c for each algorithm/, for the AntNet competitors we used the best settings we could /nd in the literature and//or we tried to tune the parameters as much as possible to obtain better results/. For OSPF/, SPF/, and BF/, the length of the time interval between consecutive routing information broadcasts and the length of the time window to average link costs are the same/, and they are set to /0/./8 or /3 seconds/, depending on the experiment for SPF and BF/, and to /3/0 seconds for OSPF/. Link costs inside each window are assigned as the weighted sum between the arithmetic average over the window and the exponential average with decay factor equal to /0/./9/. The obtained values are discretized over a linear scale saturated between /1 and /2/0/, with slope set to /2/0 and maximum admitted variation equal to /1/. For Q/-R and PQ/-R the transmission of routing information is totally data/-driven/. The learning and adaptation rate we used were the same as used by the equal to /1/./7/0/, meaning a con/dence level of approximately /0/./9/5/. algorithm/'s authors /(Boyan /& Littman/, /1/9/9/4/; Choi /& Yeung/, /1/9/9/6/)/. Concerning AntNet/, we observed that the algorithm is very robust to internal parameters tuning/. We did not /nely tune the parameter set/, and we used the same set of values for all the di/erent experiments we ran/. Most of the settings we used have been previously given in the text at the moment the parameter was discussed and they are not reported in this section/. The ant generation interval at each node was set to /0/./3 seconds/. In Section /7/./4 it will be shown the robustness of AntNet with respect to this parameter/. Regarding the parameters of the statistical model/, the value of //, weighting the number of the samples considered in the model /(Equation /1/)/, has been set to /0/./0/0/5/, the c factor for the expression of jWj max /(sect/. /4/./2/) has been put equal to /0/./3/, and the con/dence level factor z /(sect/. /4/./2/) /7/. Results Experiments reported in this section compare AntNet with the competing routing algo/rithms described in Section /5/. We studied the performance of the algorithms for increasing tra/c load/, examining the evolution of the network status toward a saturation condition/, - hard to assess whether an algorithm is signi/cantly better than another or not/. / Under high/, near saturation/, loads/, all the tested algorithms are able to deliver the o/ered throughput in a quite similar way/, that is/, in most of the cases all the gener/ated tra/c is routed without big losses/. On the contrary/, the study of packet delay distributions shows remarkable di/erences among the di/erent algorithms/. To present simulation results regarding packet delays we decided either to report the whole em/pirical distribution or to use the /9/0/-th percentile statistic/, which allows one to compare the algorithms on the basis of the upper value of delay they were able to keep the /9/0/% of the correctly delivered packets/. In fact/, packet delays can be spread over a wide range of values/. This is an intrinsic characteristics of data networks/: packet delays - and for temporary saturation conditions/. / Under low load conditions/, all algorithms tested have similar performance/. In this case/, also considering the huge variability in the possible tra/c patterns/, it is very can range from very low values for sessions open between adjacent nodes connected by /3/4/0 AntNet/: Distributed Stigmergetic Control for Communications Networks fast links/, to much higher values in the case of sessions involving nodes very far apart connected by many slow links/. Because of this/, very often the empirical distribution of packet delays cannot be meaningfully parametrized in terms of mean and variance/, and the /9/0/-th percentile statistic/, or still better the whole empirical distribution/, are algorithms to tra/c loads causing only a temporary saturation/. All reported data are averaged over /1/0 trials lasting /1/0/0/0 virtual seconds of simulation time/. One thousand seconds represents a time interval long enough to expire all transients and to get enough statistical data to evaluate the behavior of the routing algorithm/. Before being fed with data tra/c/, the algorithms are given /5/0/0 preliminary simulation seconds with no data tra/c to build initial routing tables/. In this way/, each algorithm builds the routing tables according to its own /\vision/" about minimum cost paths/. Results for throughput are reported as average values without an associated measure of variance/. The inter/-trial - much more meaningful/. / Under saturation there are packet losses and//or packet delays that become too big/, cause all the network operations to slow down/. Therefore/, saturation has to be only a temporary situation/. If it is not/, structural changes to the network characteristics/, like adding new and faster connection lines/, rather than improvements of the routing algorithm/, should be in order/. For these reasons/, we studied the responsiveness of the variability is in fact always very low/, a few percent of the average value/. Parameter values for tra/c characteristics are given in the Figure captions with the following meaning /(see also previous section/)/: MSIA is the mean of the sessions inter/-arrival time distribution for the Poisson /(P/) case/, MPIA stands for the mean of the packet inter/arrival time distribution/. In the CBR case/, MPIA indicates the /xed packet production rate/. HS is the number of hot/-spots nodes and MPIA/-HS is the equivalent of MPIA for the hot/-spot sessions/. In the following/, when not otherwise explicitly stated/, the shape of the utilization are reported in Section /7/./4/. session bit streams is assumed to be of GVBR type/. Results for throughput and packet delays for all the considered network topologies are described in the three following subsections/. Results concerning the network resources /7/./1 SimpleNet Experiments with SimpleNet were designed to study how the di/erent algorithms manage to distribute the load on the di/erent possible paths/. In these experiments/, all the tra/c/, of F/-CBR type/, is directed from node /1 to node /6 /(see Figure /5/)/, and the tra/c load has been set to a value higher than the capacity of a single link/, so that it cannot be routed poorly/, stabilizing on values of about /3/0/% inferior to those provided by AntNet/. e/ciently on a single path/. Results regarding throughput /(Figure /8a/) in this case strongly discriminate among the algorithms/. The type of the tra/c workload and the small number of nodes determined signi/cant di/erences in throughput/. AntNet is the only algorithm able to deliver almost all the generated data tra/c/: its throughput after a short transient phase approaches very closely the level of that delivered by the Daemon algorithm/. PQ/-R attains a steady value approximately /1/5/% inferior to that obtained by AntNet/. The other algorithms behave very /3/4/1 In this Di Caro /& Dorigo case/, it is rather clear that AntNet is the only algorithm able to exploit at best all the three available paths /(/1/-/8/-/7/-/6/, /1/-/3/-/5/-/6/, /1/-/2/-/4/-/5/-/6/) to distribute the data tra/c without inducing counterproductive oscillations/. The utilization of the routing tables in a probabilistic way also by data packets in this case plays a fundamental role in achieving higher quality re/sults/. Results for throughput are con/rmed by those for packet delays/, reported in the graph of Figure /8b/. The di/erences in the empirical distributions for packet delays re/ ect <details> <summary>Image 7 Details</summary>  ### Visual Description \n ## Line Graphs: Network Protocol Performance Comparison ### Overview The image contains two side-by-side line charts, labeled (a) and (b), comparing the performance of seven network routing protocols over a simulation. Chart (a) plots throughput against simulation time, while chart (b) shows the empirical cumulative distribution function (CDF) of packet delay. The protocols compared are OSPF, SPF, BF, Q-R, PCAL, AntNet, and Daemon. ### Components/Axes **Chart (a) - Left Graph:** * **Title/Label:** (a) at the bottom center. * **X-Axis:** "Simulation Time (sec)". Scale: 0 to 1000, with major ticks every 100 seconds. * **Y-Axis:** "Throughput (10^6 bit/sec)". Scale: 9.5 to 14.0, with major ticks every 0.5 units. * **Legend:** Located in the upper-right quadrant. Lists seven protocols with corresponding line styles: * OSPF: Dashed line (`---`) * SPF: Dotted line (`...`) * BF: Dash-dot line (`-.-.`) * Q-R: Solid line (`---`) * PCAL: Dotted line (`...`) - *Note: Appears visually similar to SPF's style.* * AntNet: Dashed line (`---`) - *Note: Appears visually similar to OSPF's style.* * Daemon: Dash-dot line (`-.-.`) - *Note: Appears visually similar to BF's style.* **Chart (b) - Right Graph:** * **Title/Label:** (b) at the bottom center. * **X-Axis:** "Packet Delay (sec)". Scale: 0 to 0.2, with major ticks every 0.05 seconds. * **Y-Axis:** "Empirical Distribution". Scale: 0.0 to 1.0, with major ticks every 0.2 units. * **Legend:** Located in the upper-right quadrant. Identical list of seven protocols with line styles matching those in chart (a). ### Detailed Analysis **Chart (a) - Throughput vs. Simulation Time:** * **Trend Verification & Data Points:** * **OSPF (Dashed):** Starts at ~12.5, rises sharply to plateau at ~13.5 by t=100s, remains stable. * **SPF (Dotted):** Starts at ~10.0, rises gradually to plateau at ~11.6 by t=600s, remains stable. * **BF (Dash-dot):** Starts at ~10.3, rises sharply to plateau at ~13.7 by t=50s, remains stable. This is the highest sustained throughput. * **Q-R (Solid):** Starts at ~10.3, drops quickly to ~10.0 by t=50s, remains stable at the lowest level. * **PCAL (Dotted):** Starts at ~10.3, rises to ~10.5 by t=50s, then very slowly increases to ~10.6 by t=1000s. * **AntNet (Dashed):** Starts at ~10.3, drops to ~10.0 by t=100s, remains stable, closely overlapping Q-R. * **Daemon (Dash-dot):** Shows a unique, sharp initial spike to ~10.5 at t=0, then drops rapidly to ~10.0 by t=50s, remaining stable and overlapping Q-R and AntNet. **Chart (b) - Empirical Distribution of Packet Delay (CDF):** * **Trend Verification & Data Points:** * **OSPF (Dashed):** Steepest curve. Reaches a distribution of 1.0 (100% of packets) at a delay of ~0.04 sec. Indicates consistently very low delay. * **SPF (Dotted):** Rises steeply after 0.03 sec, reaches 1.0 at ~0.06 sec. Low delay, slightly higher than OSPF. * **BF (Dash-dot):** Rises steeply after 0.08 sec, reaches 1.0 at ~0.10 sec. Moderate delay. * **Q-R (Solid):** Rises steeply after 0.09 sec, reaches 1.0 at ~0.11 sec. Slightly higher delay than BF. * **PCAL (Dotted):** Rises more gradually starting at ~0.03 sec, reaches 1.0 at ~0.11 sec. Shows a wider spread of delay values. * **AntNet (Dashed):** Rises steeply after 0.09 sec, reaches 1.0 at ~0.11 sec. Very similar to Q-R. * **Daemon (Dash-dot):** Rises steeply after 0.09 sec, reaches 1.0 at ~0.11 sec. Very similar to Q-R and AntNet. ### Key Observations 1. **Performance Clustering:** The protocols form distinct performance clusters. In throughput (a), BF is highest, OSPF is second, SPF is third, and the remaining four (Q-R, AntNet, Daemon, PCAL) are clustered at the bottom. In delay (b), OSPF is best (lowest delay), SPF is second, BF is third, and the remaining four are clustered with higher delay. 2. **Stability:** All protocols reach a stable performance state within the first 100-600 seconds of simulation time and maintain it. 3. **Daemon Anomaly:** The Daemon protocol exhibits a unique, brief initial spike in throughput not seen in any other protocol. 4. **Inverse Relationship:** There is a clear inverse relationship between the two charts for the top performers. BF has the highest throughput but moderate delay. OSPF has slightly lower throughput than BF but the best (lowest) delay. This suggests a potential trade-off between maximizing raw throughput and minimizing packet latency. ### Interpretation This data demonstrates a comparative analysis of routing protocol efficiency in a simulated network environment. The charts reveal that protocol selection involves a fundamental trade-off between **throughput** (data volume successfully delivered) and **latency** (time for packet delivery). * **BF (Bellman-Ford?)** appears optimized for **maximum data volume**, achieving the highest sustained throughput but at the cost of higher packet delay. This could be suitable for bulk data transfer applications where latency is less critical. * **OSPF (Open Shortest Path First?)** is optimized for **low latency**, delivering packets with the fastest and most consistent delay, albeit with slightly lower overall throughput than BF. This is ideal for real-time applications like VoIP or video conferencing. * **SPF (Shortest Path First?)** offers a middle-ground performance. * The cluster of **Q-R, AntNet, Daemon, and PCAL** shows lower throughput and higher delay in this simulation, suggesting they may be less efficient under these specific test conditions or are designed for different network constraints (e.g., dynamic or adversarial environments) not captured by these metrics alone. * The **Daemon** protocol's initial throughput spike could indicate an aggressive startup or route discovery phase that is not sustained. The investigation suggests that the "best" protocol is entirely dependent on the application's priority: **throughput vs. latency**. The data provides a quantitative basis for making that engineering decision. </details> approximatively the same proportions as evidenced in the throughput case/. /(a/) /(b/) Figure /8/: SimpleNet/: Comparison of algorithms for F/-CBR tra/c directed from node /1 to node /6 /(MPIA /= /0/./0/0/0/3 sec/)/. /(a/) Throughput/, and /(b/) packet delays empirical distribution/. /7/./2 NSFNET We carried out a wide range of experiments on NSFNET using UP/, RP/, UP/-HS and TMPHS/UP tra/c patterns/. In all the cases considered/, di/erences in throughput are of minor importance with respect to those shown by packet delays/. For each one of the UP/, RP and UP/-HS cases we ran /ve distinct groups of ten trial experiments/, gradually increasing the generated workload /(in terms of reducing the session inter/-arrival time/)/. As explained above/, we studied the behavior of the algorithms when moving the tra/c load towards a while OSPF behaves slightly better than these last ones/. Concerning delays /(Figure /9b/) the /1/4/. It is worth remarking that in these and in some of the experiments presented in the following/, PQ/-R/'s performance is slightly worse than that of Q/-R/. This seems to be in contrast with the results presented by the PQ/-R/'s authors in the article where they introduced PQ/-R /(Choi /& Yeung/, /1/9/9/6/)/. We think that this behavior is due to the fact that /(i/) their link recovery rate matches a discrete/-time system while in our simulator time is a continuous variable/, and /(ii/) the experimental and simulation conditions are rather di/erent /(in their article it is not speci/ed the way they produced tra/c patterns and they did /3/4/2 saturation region/. In the UP case/, di/erences in throughput /(Figure /9a/) are small/: the best performing algorithms are BF and SPF/, which can attain performance of only about /1/0/% inferior to those of Daemon and of the same amount better than those of AntNet/, Q/-R and PQ/-R/, /1/4 not implement a realistic network simulator/)/. AntNet/: Distributed Stigmergetic Control for Communications Networks situation is rather di/erent/, as can be seen by the fact that all the algorithms but AntNet have been able to produce a slightly higher throughput at the expenses of much worse results for packet delays/. This trend in packet delays was con/rmed by all the experiments we ran/. OSPF/, Q/-R and PQ/-R show really poor results /(delays of order /2 or more seconds are very high values/, even if we are considering the /9/0/-th percentile of the distribution/)/, while BF and SPF behave in a similar way with performance of order /5/0/% worse than those <details> <summary>Image 8 Details</summary>  ### Visual Description ## Bar Charts: Network Protocol Performance Comparison ### Overview The image contains two side-by-side bar charts, labeled (a) and (b), comparing the performance of seven network routing protocols or algorithms across five different parameter settings. The charts share a common legend and x-axis categories but measure different performance metrics. ### Components/Axes **Common Elements:** * **Legend:** Positioned at the top center of each chart. It defines five data series, each corresponding to a numerical parameter value, represented by a distinct color: * `2.4`: Light blue * `2.3`: Maroon/Dark red * `2.2`: Light yellow/cream * `2.1`: Light cyan/aqua * `2`: Dark purple * **X-Axis (Both Charts):** Lists seven network protocols/algorithms. From left to right: `AntNet`, `OSPF`, `SPF`, `BF`, `Q-R`, `PQ-R`, `Daemon`. * **Chart (a) - Left:** * **Title/Y-Axis Label:** `Throughput (10^6 bit/sec)` * **Y-Axis Scale:** Linear scale from 0 to 18, with major tick marks every 2 units. * **Chart (b) - Right:** * **Title/Y-Axis Label:** `90-th percentile of packet delays (sec)` * **Y-Axis Scale:** Linear scale from 0.0 to 4.5, with major tick marks every 0.5 units. ### Detailed Analysis **Chart (a): Throughput (10^6 bit/sec)** For every protocol, throughput shows a consistent upward trend as the parameter value decreases from 2.4 to 2. The dark purple bar (parameter `2`) is always the tallest within each group. * **AntNet:** Throughput increases from ~11.5 (2.4) to ~13.5 (2). * **OSPF:** Throughput increases from ~12.0 (2.4) to ~14.5 (2). * **SPF:** Throughput increases from ~12.8 (2.4) to ~15.0 (2). * **BF:** Throughput increases from ~12.5 (2.4) to ~15.0 (2). * **Q-R:** Throughput increases from ~11.5 (2.4) to ~13.5 (2). * **PQ-R:** Throughput increases from ~11.8 (2.4) to ~13.2 (2). * **Daemon:** Shows the highest overall throughput, increasing from ~13.8 (2.4) to ~16.5 (2). **Chart (b): 90th Percentile of Packet Delays (sec)** For six of the seven protocols (all except Daemon), delay shows a consistent upward trend as the parameter value decreases from 2.4 to 2. The dark purple bar (parameter `2`) is the tallest within these groups. Daemon exhibits the inverse trend. * **AntNet:** Delay increases from ~0.6 (2.4) to ~1.0 (2). * **OSPF:** Delay increases from ~1.7 (2.4) to ~2.6 (2). * **SPF:** Delay increases from ~1.0 (2.4) to ~1.6 (2). * **BF:** Delay increases from ~1.2 (2.4) to ~1.7 (2). * **Q-R:** Delay increases from ~2.9 (2.4) to ~3.8 (2). * **PQ-R:** Delay increases from ~3.0 (2.4) to ~4.3 (2). * **Daemon:** Shows the lowest overall delays and an inverse trend. Delay *decreases* from ~0.9 (2.4) to ~0.3 (2). ### Key Observations 1. **Inverse Relationship:** There is a clear inverse relationship between the two metrics for most protocols. As the parameter value decreases (2.4 -> 2), throughput increases but so does the 90th percentile packet delay. 2. **Daemon's Anomaly:** The `Daemon` protocol is a significant outlier. It achieves the highest throughput *and* the lowest packet delays. Furthermore, its delay trend is opposite to all others: delays improve (decrease) as the parameter value decreases. 3. **Performance Hierarchy:** In terms of throughput, the general hierarchy from lowest to highest is: AntNet/Q-R/PQ-R < OSPF/SPF/BF < Daemon. For delay (excluding Daemon), the hierarchy from lowest to highest is: AntNet/SPF/BF < OSPF < Q-R < PQ-R. 4. **Parameter Sensitivity:** The `PQ-R` protocol shows the greatest sensitivity in delay to the parameter change, with its 90th percentile delay increasing by approximately 1.3 seconds from parameter 2.4 to 2. ### Interpretation The data suggests a fundamental trade-off in network routing optimization for the tested protocols (AntNet through PQ-R): tuning the system for higher throughput (by moving from parameter 2.4 to 2) comes at the cost of increased tail latency (90th percentile delay). This is a classic performance trade-off in networking. The `Daemon` protocol breaks this trade-off. Its superior performance on both metrics and its inverse delay trend suggest it employs a fundamentally different, and more effective, routing or scheduling algorithm under these test conditions. It manages to increase throughput while simultaneously reducing worst-case packet delays as the parameter is adjusted. The parameter (labeled 2.4, 2.3, etc.) is likely a key configuration variable, such as a weight, timer, or threshold. The consistent directional trends across multiple protocols indicate it has a predictable and significant impact on system behavior. The charts effectively demonstrate that protocol choice (`Daemon`) can overcome the throughput-delay trade-off that constrains the other algorithms. </details> obtained by AntNet and of order /6/5/% worse than Daemon/. /(a/) /(b/) Figure /9/: NSFNET/: Comparison of algorithms for increasing load for UP tra/c/. The load is increased reducing the MSIA value from /2/./4 to /2 seconds /(MPIA /= /0/./0/0/5 sec/)/. /(a/) Throughput/, and /(b/) /9/0/-th percentile of the packet delays empirical distribution/. In the RP case /(Figure /1/0a/)/, throughputs generated by AntNet/, SPF and BF are very similar/, although AntNet has a slightly better performance/. OSPF and PQ/-R behave only slightly worse while Q/-R is the worst algorithm/. Daemon is able to obtain only slightly better results than AntNet/. Again/, looking at packet delays results /(Figure /1/0b/) OSPF/, Q/-R and PQ/-R perform very badly/, while SPF shows results a bit better than those of BF but of order /4/0/% worse than those of AntNet/. Daemon is in this case far better/, which which/, again/, indicates the testbed was rather di/cult/. The last graph for NSFNET shows how the algorithms behave in the case of a TMPHS/UP situation /(Figure /1/2/)/. At time t /= /4/0/0 four hot spots are turned on and superimposed to the existing light UP tra/c/. The transient is kept on for /1/2/0 seconds/. In this case/, only indicates that the testbed was very di/cult/. For the case of UP/-HS load/, throughputs /(Figure /1/1a/) for AntNet/, SPF/, BF/, Q/-R and Daemon are very similar/, while OSPF and PQ/-R clearly show much worse results/. Again /(Figure /1/1b/)/, packet delays results for OSPF/, Q/-R and PQ/-R are much worse than those of the other algorithms /(they are so much worse that they do not /t in the scale chosen to make clear di/erences among the other algorithms/)/. AntNet is still the best performing algorithm/. In this case/, di/erences with SPF are of order /2/0/% and of /4/0/% with respect to BF/. Daemon performs about /5/0/% better than AntNet and scales much better than AntNet/, one/, typical/, situation is reported in detail to show the answer curves/. /3/4/3 Reported values Di Caro /& Dorigo <details> <summary>Image 9 Details</summary>  ### Visual Description ## Bar Charts: Network Protocol Performance Comparison ### Overview The image displays two side-by-side grouped bar charts, labeled (a) and (b), comparing the performance of seven network routing/forwarding protocols or algorithms across five different configurations or scenarios. The charts measure two distinct performance metrics: throughput and packet delay. ### Components/Axes **Common Elements:** * **Legend:** Positioned at the top center of the entire figure. It defines five data series, labeled with numerical identifiers, each associated with a unique color: * **2.8:** Blue * **2.7:** Maroon/Dark Red * **2.6:** Light Yellow/Cream * **2.5:** Light Blue/Cyan * **2.4:** Purple * **X-Axis (Both Charts):** Lists seven categories (protocols/algorithms). From left to right: `AntNet`, `OSPF`, `SPF`, `BF`, `Q-R`, `PQ-R`, `Daemon`. * **Chart Labels:** `(a)` is centered below the left chart. `(b)` is centered below the right chart. **Chart (a) - Left:** * **Title/Y-Axis Label:** `Throughput (10^6 bit/sec)` (Millions of bits per second). * **Y-Axis Scale:** Linear scale from 0 to 12, with major tick marks every 2 units (0, 2, 4, 6, 8, 10, 12). **Chart (b) - Right:** * **Title/Y-Axis Label:** `90-th percentile of packet delays (sec)` (Seconds). * **Y-Axis Scale:** Linear scale from 0.0 to 4.0, with major tick marks every 0.5 units (0.0, 0.5, 1.0, 1.5, 2.0, 2.5, 3.0, 3.5, 4.0). ### Detailed Analysis **Chart (a): Throughput Analysis** * **General Trend:** For most protocols, throughput generally increases as the legend value decreases (from 2.8 to 2.4). The purple bar (2.4) is consistently the tallest within each group. * **Protocol-Specific Data Points (Approximate values in 10^6 bit/sec):** * **AntNet:** Shows a steady increase. Blue (2.8) ≈ 10.0, Maroon (2.7) ≈ 10.5, Yellow (2.6) ≈ 10.8, Light Blue (2.5) ≈ 11.0, Purple (2.4) ≈ 11.5. * **OSPF:** Similar increasing trend but slightly lower overall than AntNet. Blue ≈ 9.5, Maroon ≈ 10.0, Yellow ≈ 10.5, Light Blue ≈ 10.8, Purple ≈ 11.0. * **SPF:** Bars are relatively close in height. Blue ≈ 10.0, Maroon ≈ 10.2, Yellow ≈ 10.5, Light Blue ≈ 10.8, Purple ≈ 11.2. * **BF:** Clear increasing trend. Blue ≈ 9.8, Maroon ≈ 10.0, Yellow ≈ 10.5, Light Blue ≈ 10.8, Purple ≈ 11.2. * **Q-R:** Shows a dip in the middle bars. Blue ≈ 9.2, Maroon ≈ 9.5, Yellow ≈ 9.8, Light Blue ≈ 10.0, Purple ≈ 10.5. * **PQ-R:** Steady increase. Blue ≈ 9.8, Maroon ≈ 10.0, Yellow ≈ 10.5, Light Blue ≈ 10.8, Purple ≈ 11.0. * **Daemon:** Highest overall throughput. Blue ≈ 10.2, Maroon ≈ 10.5, Yellow ≈ 11.0, Light Blue ≈ 11.5, Purple ≈ 11.9. **Chart (b): 90th Percentile Packet Delay Analysis** * **General Trend:** There is no uniform trend across all protocols. Some show increasing delay with lower legend values (e.g., OSPF, Q-R), while others are more stable or show mixed patterns. * **Protocol-Specific Data Points (Approximate values in seconds):** * **AntNet:** Low delay, slight increase. Blue ≈ 0.65, Maroon ≈ 0.75, Yellow ≈ 0.85, Light Blue ≈ 0.90, Purple ≈ 1.00. * **OSPF:** Significant increase. Blue ≈ 1.90, Maroon ≈ 2.05, Yellow ≈ 2.25, Light Blue ≈ 2.40, Purple ≈ 2.60. * **SPF:** Moderate increase. Blue ≈ 1.10, Maroon ≈ 1.15, Yellow ≈ 1.25, Light Blue ≈ 1.35, Purple ≈ 1.45. * **BF:** Similar to SPF, slightly higher. Blue ≈ 1.25, Maroon ≈ 1.30, Yellow ≈ 1.40, Light Blue ≈ 1.50, Purple ≈ 1.60. * **Q-R:** Highest delays, strong increase. Blue ≈ 3.10, Maroon ≈ 3.30, Yellow ≈ 3.50, Light Blue ≈ 3.80, Purple ≈ 3.90. * **PQ-R:** High delays, increase. Blue ≈ 2.10, Maroon ≈ 2.20, Yellow ≈ 2.60, Light Blue ≈ 2.95, Purple ≈ 3.30. * **Daemon:** Very low delay, minimal variation. All bars are below 0.5. Blue ≈ 0.15, Maroon ≈ 0.18, Yellow ≈ 0.22, Light Blue ≈ 0.28, Purple ≈ 0.35. ### Key Observations 1. **Performance Trade-off:** There is a clear inverse relationship between throughput and delay for several protocols. `Daemon` achieves the highest throughput *and* the lowest delay, making it the top performer in both metrics. Conversely, `Q-R` has moderate throughput but suffers from the highest packet delays. 2. **Impact of Configuration (Legend):** The configuration labeled `2.4` (purple) consistently yields the highest throughput for all protocols. However, its effect on delay is protocol-dependent: it increases delay significantly for `OSPF`, `Q-R`, and `PQ-R`, but only marginally for `AntNet` and `Daemon`. 3. **Protocol Clustering:** Protocols can be loosely grouped: * **High-Throughput, Low-Delay:** `Daemon`. * **High-Throughput, Moderate/High-Delay:** `AntNet`, `SPF`, `BF`, `PQ-R`. * **Moderate-Throughput, High-Delay:** `Q-R`. * **Lower-Throughput, Moderate-Delay:** `OSPF`. 4. **Anomaly:** The `Q-R` protocol in chart (a) shows a non-monotonic trend where the middle configurations (2.7, 2.6) have slightly lower throughput than the extremes (2.8, 2.4), which is not seen in other protocols. ### Interpretation This data likely comes from a simulation or experimental study evaluating routing algorithms under different network conditions or parameter settings (represented by the legend values 2.4-2.8). The findings suggest: * **`Daemon` is the most efficient protocol** in this test, excelling in both moving data quickly (throughput) and delivering it promptly (low delay). This could indicate an optimized, perhaps centralized or highly adaptive, algorithm. * **`Q-R` and `PQ-R` (possibly Queue-based or Predictive Queue-based Routing) prioritize throughput but at a significant cost to latency.** This might be acceptable for bulk data transfer but problematic for real-time applications. The high 90th percentile delay indicates tail latency issues, meaning a significant fraction of packets experience very long delays. * **Traditional protocols like `OSPF` (Open Shortest Path First) and `SPF` (Shortest Path First) show middling performance,** which is expected as they are designed for stability and simplicity rather than peak performance under all conditions. * The **legend values (2.4-2.8) likely represent a key system parameter** such as network load, traffic burstiness, or a configuration threshold. The general trend of higher throughput at `2.4` suggests this setting might correspond to a less congested or more favorable operating point for these algorithms. In summary, the charts provide a multi-metric comparison that reveals critical performance trade-offs, highlighting `Daemon` as a superior solution and exposing the latency weaknesses of queue-based approaches (`Q-R`, `PQ-R`) in the tested scenarios. </details> Throughput/, and /(b/) /9/0/-th percentile of the packet delays empirical distribution/. /(a/) /(b/) Figure /1/0/: NSFNET/: Comparison of algorithms for increasing load for RP tra/c/. The load is increased reducing the MSIA value from /2/./8 to /2/./4 seconds /(MPIA /= /0/./0/0/5 sec/)/. /(a/) <details> <summary>Image 10 Details</summary>  ### Visual Description ## Comparative Performance Analysis: Throughput and Packet Delay ### Overview The image displays two side-by-side bar charts, labeled (a) and (b), comparing the performance of seven different network routing or management protocols across five software versions. The protocols are AntNet, OSPF, SPF, BF, Q-R, PQ-R, and Daemon. The software versions are 2.4, 2.3, 2.2, 2.1, and 2. Chart (a) measures throughput, while chart (b) measures the 90th percentile of packet delays. ### Components/Axes **Common Elements:** * **X-Axis (Both Charts):** Lists seven protocol categories: `AntNet`, `OSPF`, `SPF`, `BF`, `Q-R`, `PQ-R`, `Daemon`. * **Legend (Top Center of Each Chart):** A horizontal legend identifies five data series by color and version number: * Blue: `2.4` * Maroon: `2.3` * Yellow: `2.2` * Light Cyan: `2.1` * Dark Purple: `2` **Chart (a) - Left:** * **Title/Label:** `(a)` is centered below the chart. * **Y-Axis Label:** `Throughput (10^6 bit/sec)`. * **Y-Axis Scale:** Linear scale from 0 to 18, with major tick marks every 2 units. **Chart (b) - Right:** * **Title/Label:** `(b)` is centered below the chart. * **Y-Axis Label:** `90-th percentile of packet delays (sec)`. * **Y-Axis Scale:** Linear scale from 0.0 to 0.5, with major tick marks every 0.1 seconds. ### Detailed Analysis #### Chart (a): Throughput (10^6 bit/sec) **Trend Verification:** For most protocols, throughput generally increases from version 2.4 (blue) to version 2 (dark purple), with version 2 often being the highest. The exception is OSPF, where version 2.4 is the highest. **Data Points (Approximate Values):** * **AntNet:** Shows a steady increase. v2.4 ≈ 15.2, v2.3 ≈ 15.8, v2.2 ≈ 16.2, v2.1 ≈ 16.8, v2 ≈ 17.5. * **OSPF:** Shows a decrease then increase. v2.4 ≈ 13.8, v2.3 ≈ 13.5, v2.2 ≈ 14.0, v2.1 ≈ 14.2, v2 ≈ 14.5. * **SPF:** Shows a steady increase. v2.4 ≈ 15.5, v2.3 ≈ 16.0, v2.2 ≈ 16.5, v2.1 ≈ 17.0, v2 ≈ 17.5. * **BF:** Shows a steady increase. v2.4 ≈ 15.5, v2.3 ≈ 16.0, v2.2 ≈ 16.5, v2.1 ≈ 17.0, v2 ≈ 17.5. * **Q-R:** Shows a steady increase. v2.4 ≈ 15.2, v2.3 ≈ 15.8, v2.2 ≈ 16.2, v2.1 ≈ 16.8, v2 ≈ 17.2. * **PQ-R:** Shows a steady increase. v2.4 ≈ 14.2, v2.3 ≈ 14.5, v2.2 ≈ 14.8, v2.1 ≈ 15.0, v2 ≈ 15.2. * **Daemon:** Shows a steady increase. v2.4 ≈ 15.5, v2.3 ≈ 16.0, v2.2 ≈ 16.5, v2.1 ≈ 17.0, v2 ≈ 17.5. #### Chart (b): 90th Percentile of Packet Delays (sec) **Trend Verification:** Delay trends are more varied. Some protocols (OSPF, Q-R) show very high delays (capped at 0.5 sec) for multiple versions. Others (AntNet, Daemon) show consistently low delays with a slight increasing trend. SPF and BF show a clear increasing trend in delay across versions. **Data Points (Approximate Values):** * **AntNet:** Low and slightly increasing. v2.4 ≈ 0.10, v2.3 ≈ 0.12, v2.2 ≈ 0.14, v2.1 ≈ 0.15, v2 ≈ 0.20. * **OSPF:** Very high, at or near the 0.5 sec cap for all versions except v2.3 (≈0.5) and v2 (≈0.5). v2.4, v2.2, v2.1 appear to be exactly at 0.5. * **SPF:** Clear increasing trend. v2.4 ≈ 0.11, v2.3 ≈ 0.14, v2.2 ≈ 0.16, v2.1 ≈ 0.18, v2 ≈ 0.26. * **BF:** Clear increasing trend. v2.4 ≈ 0.13, v2.3 ≈ 0.15, v2.2 ≈ 0.18, v2.1 ≈ 0.20, v2 ≈ 0.33. * **Q-R:** Very high, at or near the 0.5 sec cap for all versions. v2.4, v2.3, v2.2, v2.1 appear to be exactly at 0.5. v2 is slightly lower, ≈0.5. * **PQ-R:** Very high, at or near the 0.5 sec cap for all versions. All five bars appear to be exactly at 0.5. * **Daemon:** Lowest overall, slightly increasing. v2.4 ≈ 0.04, v2.3 ≈ 0.05, v2.2 ≈ 0.06, v2.1 ≈ 0.07, v2 ≈ 0.08. ### Key Observations 1. **Throughput vs. Delay Trade-off:** Protocols with the highest throughput (e.g., SPF, BF, Daemon in later versions) do not necessarily have the lowest packet delay. Daemon achieves both high throughput and the lowest delay. 2. **Performance Extremes:** * **Best Overall:** `Daemon` shows excellent performance: high, improving throughput and the lowest, most stable packet delays. * **Worst for Delay:** `OSPF`, `Q-R`, and `PQ-R` exhibit severe packet delay issues, with their 90th percentile often hitting the 0.5-second cap, which could indicate congestion or poor queue management. 3. **Version Impact:** For throughput, newer versions (2, 2.1) generally perform better. For delay, the impact is protocol-specific; newer versions sometimes increase delay (SPF, BF, AntNet) while for others (OSPF, Q-R) the delay is consistently poor. 4. **Anomaly:** `OSPF`'s throughput is an outlier in trend, being highest in the oldest version (2.4) and lower in subsequent versions before recovering slightly. ### Interpretation This data suggests a comparative study of routing protocol implementations across software releases. The key takeaway is that **protocol choice has a more significant impact on performance than incremental version updates.** * **Daemon** appears to be the most robust and efficient protocol in this test, scaling well in throughput while maintaining minimal latency. * The high, capped delays for **OSPF, Q-R, and PQ-R** are a major red flag. In a real network, a 90th percentile delay of 0.5 seconds would severely impact real-time applications like VoIP or video streaming. This could be due to algorithmic complexity, inefficient packet processing, or poor handling of network load in these specific implementations. * The general trend of increasing delay for **SPF and BF** as throughput increases suggests these protocols may be pushing the system closer to its saturation point, where queuing delays become significant. * The charts effectively highlight that optimizing for a single metric (like throughput) is insufficient. A holistic view, including latency metrics like the 90th percentile delay, is crucial for selecting a protocol suitable for performance-sensitive applications. The `Daemon` protocol demonstrates that high throughput and low latency can be achieved simultaneously. </details> empirical distribution/. /(a/) /(b/) Figure /1/1/: NSFNET/: Comparison of algorithms for increasing load for UP/-HS tra/c/. The load is increased reducing the MSIA value from /2/./4 to /2/./0 seconds /(MPIA /= /0/./3 sec/, HS /= /4/, MPIA/-HS /= /0/./0/4 sec/)/. /(a/) Throughput/, and /(b/) /9/0/-th percentile of the packet delays are the /\instantaneous/" values for throughput and packet delays computed as the average over /5 seconds moving windows/. All algorithms have a similar very good performance as far as throughput is concerned/, except for OSPF and PQ/-R/, which lose a few percent of the packets during the transitory period/. The graph of packet delays con/rms previous results/: SPF and BF have a similar behavior/, about /2/0/% worse than AntNet and /4/5/% worse than Daemon/. The other three algorithms show a big out/-of/-scale jump/, being not able to properly dump the sudden load increase/. /3/4/4 AntNet/: Distributed Stigmergetic Control for Communications Networks Figure /1/2/: NSFNET/: Comparison of algorithms for transient saturation conditions with TMPHS/-UP tra/c /(MSIA /= /3/./0 sec/, MPIA /= /0/./3 sec/, HS /= /4/, MPIA/-HS /= /0/./0/4/)/. /(a/) Throughput/, and /(b/) packet delays averaged over /5 seconds moving <details> <summary>Image 11 Details</summary>  ### Visual Description ## Dual-Axis Line Chart: Network Routing Protocol Performance Under Load ### Overview The image displays a technical performance comparison of seven network routing protocols over a simulated time period. It consists of two vertically stacked line charts sharing a common x-axis (Simulation Time). The top chart measures network throughput, and the bottom chart measures packet delay. A significant event, likely a congestion or failure scenario, occurs between approximately 400 and 520 seconds, causing dramatic changes in the performance metrics for most protocols. ### Components/Axes * **Chart Type:** Dual-axis line chart (two subplots). * **X-Axis (Shared):** Label: `Simulation Time (sec)`. Scale: Linear, from 200 to 1000 seconds, with major ticks every 100 seconds. * **Top Subplot Y-Axis:** Label: `Throughput (10^6 bit/sec)`. Scale: Linear, from 6.0 to 16.0, with major ticks every 2.0 units. * **Bottom Subplot Y-Axis:** Label: `Packet Delay (sec)`. Scale: Linear, from 0.03 to 0.06, with major ticks every 0.01 seconds. * **Legend:** Positioned in the bottom-right corner of the *bottom subplot*. It lists seven protocols with corresponding line styles: * `OSPF`: Dashed line (`---`) * `SPF`: Solid line (`—`) * `BF`: Dash-dot line (`-.-.`) * `Q-R`: Dotted line (`...`) * `PQ-R`: Dash-dot-dot line (`-..-..`) * `AntNet`: Densely dotted line (finer dots than Q-R) * `Daemon`: Long-dashed line (`- - -`) ### Detailed Analysis **1. Top Subplot: Throughput Analysis** * **General Trend (200-400 sec):** All protocols show a gradual, nearly identical increase in throughput from ~7.0 to ~8.8 Mbit/sec. * **Event Period (400-520 sec):** A sharp, near-vertical increase occurs for all protocols. * **OSPF & SPF:** Reach the highest plateau, approximately 14.2 - 14.5 Mbit/sec. * **Other Protocols (BF, Q-R, PQ-R, AntNet, Daemon):** Plateau at a slightly lower level, approximately 13.5 - 14.0 Mbit/sec. * **Post-Event (520-1000 sec):** Throughput for all protocols drops sharply and stabilizes at a new, higher baseline than the pre-event period, around 9.5 - 9.8 Mbit/sec. The lines are tightly clustered, showing minimal difference between protocols in this phase. **2. Bottom Subplot: Packet Delay Analysis** * **General Trend (200-400 sec):** Delays are low and stable, clustered between 0.030 and 0.035 seconds. `OSPF` and `SPF` are at the lower end of this range. * **Event Period (400-520 sec):** A dramatic spike in delay occurs, with significant differentiation between protocols. * **OSPF & SPF:** Exhibit the highest and most volatile delays, spiking to the chart's upper limit of 0.06 sec and fluctuating heavily between ~0.048 and 0.06 sec. * **BF, Q-R, PQ-R:** Show a moderate increase, stabilizing around 0.040 - 0.043 sec. * **AntNet & Daemon:** Show the smallest increase, remaining relatively stable near 0.035 - 0.037 sec. * **Post-Event (520-1000 sec):** Delays for all protocols drop and converge to a narrow band between 0.030 and 0.035 sec, similar to the pre-event state. `OSPF` and `SPF` remain slightly higher than the others. ### Key Observations 1. **Correlated Event:** A system-wide event at t=400 sec triggers a simultaneous, massive increase in throughput and packet delay, indicating a period of high load or congestion. 2. **Protocol Differentiation Under Stress:** The primary performance differentiation between protocols occurs *during* the high-load event (400-520 sec), not during normal operation. 3. **Throughput vs. Delay Trade-off:** Protocols achieving the highest throughput during the event (`OSPF`, `SPF`) also suffer the highest and most unstable packet delays. Protocols with more moderate throughput increases (`AntNet`, `Daemon`) maintain much lower and more stable delays. 4. **Recovery and New Equilibrium:** All protocols successfully recover after the event (t=520 sec) and settle into a new stable state with higher throughput than the initial phase, but with delays returning to near-initial levels. ### Interpretation This data visualizes a classic network performance trade-off under stress. The event between 400-520 seconds likely simulates a sudden surge in traffic or a link failure that forces rerouting. * **OSPF and SPF** appear to be aggressive, throughput-optimizing protocols. They successfully maximize bandwidth utilization during the crisis (high throughput) but at the severe cost of increased latency and jitter (high, volatile delay), which could be detrimental to real-time applications. * **AntNet and Daemon** demonstrate a more conservative or balanced approach. They sacrifice some peak throughput to maintain significantly better and more stable latency performance during congestion, suggesting better Quality of Service (QoS) guarantees. * **BF, Q-R, and PQ-R** occupy a middle ground. * The post-event convergence suggests that once the acute stressor is removed, the network's capacity and routing tables stabilize, allowing all protocols to perform similarly well, albeit at a higher throughput level than the initial state (possibly due to learned routes or cached paths). **Conclusion:** The chart effectively argues that protocol choice is critical during network anomalies. There is no single "best" protocol; the optimal choice depends on whether the application prioritizes maximum raw throughput (favoring OSPF/SPF) or low, stable latency (favoring AntNet/Daemon) during periods of high load. </details> windows/. /7/./3 NTTnet The same set of experiments run on the NSFNET have been repeated on NTTnet/. In this case the results are even sharper than those obtained with NSFNET/: AntNet performance BF/, Q/-R and PQ/-R perform poorly and OSPF completely collapses/. In the UP and RP cases /(Figures /1/3b and /1/4b/) SPF and BF performs similarly/, even if SPF is much better that of all its competitors/. For the UP/, RP and UP/-HS cases/, di/erences in throughput are not signi/cant /(Figures /1/3a/, /1/4a and /1/5a/)/. All the algorithms/, with the OSPF exception/, practically behave in the same way as the Daemon algorithm/. Concerning delays /(Figures /1/3b/, /1/4b and /1/5b/)/, di/erences between AntNet and each of its competitors are of one order of magnitude/. AntNet keeps delays at low values/, very close to those obtained by Daemon/, while SPF/, shows slightly better results/, and about /5/0/% better than Q/-R and PQ/-R/. In the UP/-HS case/, again/, SPF and BF show similar results/, while Q/-R performs compa/rably but in a much more irregular way and PQ/-R can keep delays about /3/0/% lower/. OSPF/, which is the worse algorithm in this case/, shows an interesting behavior/. The increase in the generated data throughput determines a decrease or a very slow increase in the delivered throughput while delays decrease /(Figure /1/5a and /1/5b/)/. In this case the load was too high for the algorithm and the balance between the two/, con/ icting/, objectives/, throughput and /3/4/5 Di Caro /& Dorigo <details> <summary>Image 12 Details</summary>  ### Visual Description ## Bar Charts: Network Protocol Performance Comparison ### Overview The image displays two side-by-side bar charts, labeled (a) and (b), comparing the performance of seven different network routing protocols or algorithms across five distinct configurations or versions (labeled 3.1, 3, 2.9, 2.8, 2.7). Chart (a) measures throughput, while chart (b) measures packet delay. The overall visual suggests a performance trade-off analysis. ### Components/Axes **Common Elements:** * **Legend:** Positioned at the top center of each chart. It defines five data series by color: * **3.1:** Light blue * **3:** Dark red/maroon * **2.9:** Light yellow/cream * **2.8:** Light green * **2.7:** Dark purple * **X-Axis (Both Charts):** Lists seven network protocols/algorithms. From left to right: `AntNet`, `OSPF`, `SPF`, `BF`, `Q-R`, `PQ-R`, `Daemon`. * **Chart Labels:** The charts are labeled `(a)` and `(b)` in the bottom-left corner of each respective plot area. **Chart (a) Specifics:** * **Title/Y-Axis Label:** `Throughput (10^6 bit/sec)` * **Y-Axis Scale:** Linear scale from 0 to 45, with major gridlines at intervals of 5. **Chart (b) Specifics:** * **Title/Y-Axis Label:** `90-th percentile of packet delays (sec)` * **Y-Axis Scale:** Linear scale from 0.0 to 10.0, with major gridlines at intervals of 1.0. ### Detailed Analysis **Chart (a): Throughput Analysis** * **Trend Verification:** For nearly all protocols, throughput shows a consistent upward trend from configuration `3.1` to `2.7`. The bars get progressively taller from left (light blue) to right (dark purple) within each protocol group. * **Data Points (Approximate Values in 10^6 bit/sec):** * **AntNet:** 3.1≈37, 3≈39, 2.9≈41, 2.8≈42, 2.7≈43 * **OSPF:** 3.1≈35, 3≈36, 2.9≈37, 2.8≈37, 2.7≈37 * **SPF:** 3.1≈37, 3≈39, 2.9≈41, 2.8≈42, 2.7≈43 * **BF:** 3.1≈37, 3≈39, 2.9≈41, 2.8≈42, 2.7≈43 * **Q-R:** 3.1≈37, 3≈39, 2.9≈41, 2.8≈42, 2.7≈43 * **PQ-R:** 3.1≈36, 3≈38, 2.9≈40, 2.8≈41, 2.7≈42 * **Daemon:** 3.1≈38, 3≈40, 2.9≈42, 2.8≈43, 2.7≈44 * **Key Observation:** `Daemon` achieves the highest throughput across all configurations, peaking at ~44. `OSPF` shows the least improvement across configurations and has the lowest throughput for most, except for `3.1` where it is comparable to others. **Chart (b): 90th Percentile Packet Delay Analysis** * **Trend Verification:** The trend is highly protocol-dependent. `OSPF` shows a dramatic, non-linear increase in delay from `3.1` to `2.7`. All other protocols show a very slight, gradual increase. * **Data Points (Approximate Values in seconds):** * **AntNet:** All values are very low, < 0.2 sec. * **OSPF:** 3.1≈5.6, 3≈5.3, 2.9≈6.3, 2.8≈9.2, 2.7≈10.0 * **SPF:** 3.1≈0.4, 3≈0.5, 2.9≈0.6, 2.8≈0.7, 2.7≈0.8 * **BF:** 3.1≈0.5, 3≈0.6, 2.9≈0.7, 2.8≈0.8, 2.7≈0.9 * **Q-R:** 3.1≈1.0, 3≈1.1, 2.9≈1.2, 2.8≈1.3, 2.7≈1.4 * **PQ-R:** 3.1≈1.1, 3≈1.2, 2.9≈1.3, 2.8≈1.4, 2.7≈1.7 * **Daemon:** All values are extremely low, near 0.0 sec. * **Key Observation:** `OSPF` is a massive outlier, with delays 5-100 times higher than other protocols, especially in configurations `2.8` and `2.7`. `Daemon` and `AntNet` exhibit the best (lowest) delay performance. ### Interpretation The data demonstrates a clear performance dichotomy between the `OSPF` protocol and the others tested. 1. **Performance Trade-off:** `OSPF` appears to be optimized for a different metric not shown here (perhaps stability or simplicity), as it suffers from significantly higher latency (chart b) while also delivering the lowest throughput (chart a) in most configurations. The other protocols (`AntNet`, `SPF`, `BF`, `Q-R`, `PQ-R`, `Daemon`) form a cluster with high throughput and low delay. 2. **Configuration Impact:** The configuration parameter (3.1 to 2.7) has a predictable, positive effect on throughput for all protocols. However, its effect on delay is protocol-specific. For `OSPF`, moving to configurations `2.8` and `2.7` causes a catastrophic increase in delay, suggesting these configurations may introduce complexity or overhead that `OSPF` handles poorly. For other protocols, the same configuration changes cause only a minor, linear increase in delay. 3. **Top Performer:** The `Daemon` protocol consistently shows the best combined performance: the highest throughput and the lowest packet delay across all configurations. `AntNet` is a close second in delay performance. 4. **Anomaly:** The `OSPF` delay for configuration `3` (≈5.3s) is slightly lower than for `3.1` (≈5.6s), breaking the otherwise strict increasing trend. This could be a measurement artifact or indicate a non-monotonic relationship for this specific protocol. **Conclusion:** The charts strongly suggest that for the measured workloads, protocols like `Daemon` and `AntNet` are superior to `OSPF` in both throughput and latency. The choice of configuration (3.1-2.7) involves a trade-off: higher-numbered configurations (e.g., 2.7) maximize throughput but may incur a small latency penalty for most protocols, and a severe one for `OSPF`. </details> Throughput/, and /(b/) /9/0/-th percentile of the packet delays empirical distribution/. /(a/) /(b/) Figure /1/3/: NTTnet/: Comparison of algorithms for increasing load for UP tra/c/. The load is increased reducing the MSIA value from /3/./1 to /2/./7 seconds /(MPIA /= /0/./0/0/5 sec/)/. /(a/) <details> <summary>Image 13 Details</summary>  ### Visual Description \n ## Bar Charts: Throughput and Packet Delay Comparison of Network Routing Algorithms ### Overview The image displays two side-by-side bar charts, labeled (a) and (b), comparing the performance of seven network routing algorithms across five different software or protocol versions (3.1, 3, 2.9, 2.8, 2.7). Chart (a) measures throughput, while chart (b) measures the 90th percentile of packet delays. The charts share the same x-axis categories and legend. ### Components/Axes * **Chart (a) - Left:** * **Title/Y-axis Label:** "Throughput (10⁶ bit/sec)" * **Y-axis Scale:** Linear scale from 0 to 45, with major gridlines every 5 units. * **X-axis Categories (Algorithms):** AntNet, OSPF, SPF, BF, Q-R, PQ-R, Daemon. * **Legend:** Located at the top center. Colors and labels: * Blue: 3.1 * Red: 3 * Yellow: 2.9 * Cyan: 2.8 * Purple: 2.7 * **Chart (b) - Right:** * **Title/Y-axis Label:** "90-th percentile of packet delays (sec)" * **Y-axis Scale:** Linear scale from 0.0 to 10.0, with major gridlines every 1.0 unit. * **X-axis Categories (Algorithms):** Identical to chart (a): AntNet, OSPF, SPF, BF, Q-R, PQ-R, Daemon. * **Legend:** Identical to chart (a), located at the top center. ### Detailed Analysis **Chart (a) - Throughput Analysis:** * **General Trend:** For every algorithm, throughput generally increases from version 3.1 (blue) to version 2.7 (purple). The purple bar (2.7) is consistently the tallest within each algorithm group. * **Algorithm Performance (Approximate Values in 10⁶ bit/sec):** * **AntNet:** 3.1≈37, 3≈39, 2.9≈40, 2.8≈42, 2.7≈43. * **OSPF:** 3.1≈35, 3≈34, 2.9≈36, 2.8≈37, 2.7≈36.5. (Note: Slight dip for version 3). * **SPF:** 3.1≈37, 3≈39, 2.9≈40, 2.8≈42, 2.7≈43. * **BF:** 3.1≈37, 3≈38, 2.9≈39, 2.8≈41, 2.7≈42.5. * **Q-R:** 3.1≈37, 3≈38, 2.9≈39, 2.8≈41, 2.7≈42.5. * **PQ-R:** 3.1≈37, 3≈38, 2.9≈39, 2.8≈41, 2.7≈42.5. * **Daemon:** 3.1≈37, 3≈38, 2.9≈40, 2.8≈41, 2.7≈43. **Chart (b) - Packet Delay Analysis:** * **General Trend:** Most algorithms maintain very low delays (under 2.0 sec) across all versions. The major exception is OSPF, which shows extremely high delays for versions 3.1 and 3. * **Algorithm Performance (Approximate 90th Percentile Delay in sec):** * **AntNet:** All versions ≈ 0.1 sec or less. * **OSPF:** 3.1≈9.2, 3≈10.0 (off-chart, estimated), 2.9≈10.0 (off-chart, estimated), 2.8≈0.7, 2.7≈1.1. (Note: Dramatic drop from version 3 to 2.8). * **SPF:** 3.1≈0.8, 3≈0.9, 2.9≈1.0, 2.8≈1.2, 2.7≈1.3. * **BF:** 3.1≈0.9, 3≈1.0, 2.9≈1.1, 2.8≈1.3, 2.7≈1.4. * **Q-R:** 3.1≈1.7, 3≈1.8, 2.9≈1.9, 2.8≈2.0, 2.7≈2.1. * **PQ-R:** 3.1≈1.5, 3≈1.6, 2.9≈1.7, 2.8≈1.8, 2.7≈1.9. * **Daemon:** All versions ≈ 0.1 sec or less. ### Key Observations 1. **OSPF Anomaly:** OSPF exhibits a severe performance trade-off. In versions 3.1 and 3, it achieves moderate throughput but suffers from catastrophic packet delays (near or at the 10-second ceiling). In versions 2.8 and 2.7, its delay drops to a reasonable level (~0.7-1.1 sec), and its throughput improves slightly. 2. **Consistent High Performers:** AntNet and Daemon consistently show the best overall performance: high throughput (among the top) and negligible packet delay across all versions. 3. **Version Trend:** There is a clear, consistent trend where newer version numbers (moving from 3.1 to 2.7) correlate with higher throughput for all algorithms. The impact on delay is algorithm-specific. 4. **Delay Hierarchy:** In terms of delay (excluding the OSPF anomaly), the algorithms can be roughly ordered from lowest to highest delay: AntNet/Daemon ≈ 0.1s < SPF ≈ 1.0s < BF ≈ 1.2s < PQ-R ≈ 1.7s < Q-R ≈ 1.9s. ### Interpretation The data suggests a comparative study of routing algorithm implementations, likely under simulated network conditions. The "versions" (3.1 to 2.7) may represent different parameter tunings, protocol revisions, or generations of the algorithms. * **Performance Trade-off:** The charts highlight the classic networking trade-off between throughput and latency. OSPF in early versions appears optimized for throughput at a severe cost to latency, while later versions seem to rebalance this. AntNet and Daemon appear to achieve an excellent balance. * **Algorithm Suitability:** For latency-sensitive applications, AntNet or Daemon are the clear choices. For throughput-dominated tasks where occasional high latency is acceptable, most algorithms (except early OSPF) are viable, with version 2.7 being optimal. * **Investigative Insight:** The dramatic change in OSPF's delay profile between versions 3 and 2.8 is the most significant finding. This likely indicates a major algorithmic change, bug fix, or configuration shift that resolved a critical latency issue. A technical document would need to investigate the changelog between these versions to understand the cause. * **Data Limitation:** The charts show aggregated 90th percentile and throughput metrics. They do not reveal the distribution of delays, jitter, or performance under varying load conditions, which would be necessary for a complete assessment. </details> Throughput/, and /(b/) /9/0/-th percentile of the packet delays empirical distribution/. packet delays/, showed an inverse dynamics/: having a lot of packet losses made it possible /(a/) /(b/) Figure /1/4/: NTTnet/: Comparison of algorithms for increasing load for RP tra/c/. The load is increased reducing the MSIA value from /3/./1 to /2/./7 seconds /(MPIA /= /0/./0/0/5 sec/)/. /(a/) for the surviving packets to obtain lower trip delays/. The TMPHS/-UP experiment /(Figure /1/6/)/, concerning sudden load variation/, con/rms the previous results/. OSPF is not able to follow properly the variation both for throughput and delays/. All the other algorithms are able to follow the sudden increase in the o/ered throughput/, but only AntNet /(and Daemon/) show a very regular behavior/. Di/erences in packet delays are striking/. AntNet performance is very close to those obtained by Daemon /(the curves are practically superimposed at the scale used in the Figure/)/. Among the other algorithms/, SPF and BF are the best ones/, although their response is rather irregular and/, in any case/, much worse than AntNet/'s/. OSPF and Q/-R are out/-of/-scale and show a very PQ/-R/, after a huge jump/, which takes the graph out/-of/-scale in /3/4/6 delayed recovering curve/. AntNet/: Distributed Stigmergetic Control for Communications Networks <details> <summary>Image 14 Details</summary>  ### Visual Description ## Bar Charts: Throughput and Packet Delay Comparison of Network Protocols ### Overview The image contains two side-by-side bar charts, labeled (a) and (b), comparing the performance of seven network protocols or methods across five different versions or parameter settings. Chart (a) measures throughput, while chart (b) measures the 90th percentile of packet delays. ### Components/Axes **Chart (a) - Left Chart:** * **Title/Label:** (a) at the bottom center. * **Y-Axis:** Labeled "Throughput (10⁶ bits/sec)". Scale ranges from 0 to 50 in increments of 5. * **X-Axis:** Lists seven categories: AntNet, OSPF, SPF, BF, Q-R, PQ-R, Daemon. * **Legend:** Positioned at the top center of the chart area. Contains five colored squares with corresponding labels: * Blue square: "4.1" * Red square: "4" * Yellow square: "3.9" * Cyan square: "3.8" * Purple square: "3.7" **Chart (b) - Right Chart:** * **Title/Label:** (b) at the bottom center. * **Y-Axis:** Labeled "90-th percentile of packet delays (sec)". Scale ranges from 0.0 to 7.0 in increments of 1.0. * **X-Axis:** Lists the same seven categories as chart (a): AntNet, OSPF, SPF, BF, Q-R, PQ-R, Daemon. * **Legend:** Identical to chart (a), positioned at the top center. ### Detailed Analysis **Chart (a) - Throughput Analysis:** * **Trend Verification:** For most protocols (AntNet, SPF, BF, Q-R, PQ-R, Daemon), the throughput bars are relatively flat and high, showing minimal variation across the five versions (4.1 to 3.7). The OSPF protocol shows a distinctly lower throughput compared to the others. * **Data Points (Approximate Values in 10⁶ bits/sec):** * **AntNet:** All versions cluster between ~42 and ~45. Blue (4.1) ~43, Red (4) ~44, Yellow (3.9) ~44, Cyan (3.8) ~45, Purple (3.7) ~45. * **OSPF:** All versions cluster between ~34 and ~35. Blue (4.1) ~35, Red (4) ~34, Yellow (3.9) ~34, Cyan (3.8) ~34, Purple (3.7) ~34. * **SPF, BF, Q-R, PQ-R, Daemon:** All show very similar profiles to AntNet, with values consistently in the ~42 to ~45 range across all versions. **Chart (b) - Packet Delay Analysis:** * **Trend Verification:** The OSPF protocol shows a dramatic, descending stair-step pattern where delay decreases significantly as the version number decreases (from 4.1 to 3.7). All other protocols show consistently low delays with minor variations. * **Data Points (Approximate Values in seconds):** * **AntNet:** All versions are very low, near 0.0 to 0.1 sec. * **OSPF:** Shows the most significant variation. Blue (4.1) ~6.1, Red (4) ~4.0, Yellow (3.9) ~3.0, Cyan (3.8) ~1.6, Purple (3.7) ~1.1. * **SPF:** All versions are low, between ~0.8 and ~1.0. * **BF:** All versions are low, between ~0.8 and ~1.0. * **Q-R:** Shows a slight peak for Yellow (3.9) at ~1.1, others between ~0.6 and ~0.9. * **PQ-R:** All versions are low, between ~0.3 and ~0.5. * **Daemon:** All versions are extremely low, near 0.0 to 0.05 sec. ### Key Observations 1. **OSPF Performance Anomaly:** OSPF is a clear outlier in both metrics. It has the lowest throughput (Chart a) and, for versions 4.1 and 4, the highest packet delays by a large margin (Chart b). 2. **Version Sensitivity:** The performance of OSPF is highly sensitive to the version/parameter setting, especially for packet delay, which improves (decreases) by approximately 82% from version 4.1 to 3.7. Other protocols show minimal sensitivity. 3. **High-Performing Cluster:** AntNet, SPF, BF, Q-R, PQ-R, and Daemon form a high-performance cluster with high, stable throughput and low packet delays. 4. **Daemon's Delay:** The Daemon method achieves the lowest packet delays of all, near zero, across all versions. ### Interpretation This data suggests a performance comparison of network routing or management algorithms. The "Daemon" and "AntNet" methods appear to be the most efficient, offering high throughput and minimal latency. The OSPF protocol, a standard link-state routing protocol, demonstrates a significant performance trade-off: its throughput is lower, and its latency can be very high under certain configurations (version 4.1). The strong version-dependency of OSPF's delay implies that its performance is highly tunable or sensitive to specific operational parameters. The charts effectively argue that the alternative methods (AntNet, Daemon, etc.) can outperform OSPF in both throughput and latency under the tested conditions. The near-identical performance of many protocols in chart (a) suggests the throughput metric may be less discriminating than the delay metric for this specific evaluation. </details> empirical distribution/. the /rst /4/0 seconds after hot spots are turned on/, shows a trend approaching those of BF /(a/) /(b/) Figure /1/5/: NTTnet/: Comparison of algorithms for increasing load for UP/-HS tra/c/. The load is increased reducing the MSIA value from /4/./1 to /3/./7 seconds /(MPIA /= /0/./3 sec/, HS /= /4/, MPIA/-HS /= /0/./0/5 sec/)/. /(a/) Throughput/, and /(b/) /9/0/-th percentile of the packet delays and SPF/. Figure /1/6/: NTTnet/: Comparison of algorithms for transient saturation conditions with TMPHS/-UP tra/c /(MSIA /= /4/./0 sec/, MPIA /= /0/./3 sec/, HS /= /4/, MPIA/-HS /= /0/./0/5/)/. /(a/) Throughput/, and /(b/) packet delays averaged over /5 seconds moving <details> <summary>Image 15 Details</summary>  ### Visual Description ## Dual-Axis Line Chart: Network Routing Algorithm Performance Comparison ### Overview The image displays a dual-axis line chart comparing the performance of seven network routing algorithms over a simulated time period. The chart is divided into two vertically stacked subplots sharing a common x-axis. The top subplot measures network throughput, while the bottom subplot measures packet delay. The simulation runs from 200 to 1000 seconds, with a notable event or change in network conditions occurring around the 400-second mark. ### Components/Axes * **Chart Type:** Dual-axis line chart (two subplots). * **Shared X-Axis:** * **Label:** `Simulation Time (sec)` * **Range:** 200 to 1000 seconds. * **Major Tick Marks:** At 200, 300, 400, 500, 600, 700, 800, 900, 1000. * **Top Subplot Y-Axis:** * **Label:** `Throughput (10^6 bit/sec)` (Megabits per second). * **Range:** 15.0 to 55.0. * **Major Tick Marks:** At 15.0, 25.0, 35.0, 45.0, 55.0. * **Bottom Subplot Y-Axis:** * **Label:** `Packet Delay (sec)`. * **Range:** 0.0 to 0.8 seconds. * **Major Tick Marks:** At 0.0, 0.2, 0.4, 0.6, 0.8. * **Legend:** * **Position:** Located in the bottom-right corner of the lower subplot. * **Content:** Lists seven algorithms with corresponding line styles. 1. `OSPF` - Dashed line (`---`) 2. `SPF` - Solid line (`—`) 3. `BF` - Dash-dot line (`-.-.`) 4. `Q-R` - Dotted line (`...`) 5. `PQ-R` - Dash-dot-dot line (`-..-..`) 6. `AntNet` - Densely dotted line (finer dots than Q-R) 7. `Daemon` - Long-dash line (`-- --`) ### Detailed Analysis #### Top Subplot: Throughput Analysis * **General Trend:** All algorithms show a similar pattern: a gradual increase from 200s to ~400s, a sharp spike and plateau between ~400s and ~520s, followed by a drop and stabilization from ~550s onward. * **Pre-Spike (200s - 400s):** Throughput for all algorithms rises steadily from approximately 20-22 Mbps to about 25-27 Mbps. * **Spike & Plateau (400s - 520s):** * A dramatic increase occurs at ~400s. * **OSPF & SPF:** Show the highest throughput, peaking near 50 Mbps and maintaining a plateau around 45-47 Mbps. * **BF, Q-R, PQ-R, AntNet, Daemon:** Plateau at a lower level, approximately 35-40 Mbps. The `BF` line appears slightly lower than the others in this group during the plateau. * **Post-Spike (520s - 1000s):** * Throughput drops sharply at ~520s. * All algorithms converge and stabilize at a nearly identical throughput of approximately 28-30 Mbps for the remainder of the simulation (600s to 1000s). The lines are tightly clustered, showing minimal difference. #### Bottom Subplot: Packet Delay Analysis * **General Trend:** Delay is very low and stable for all algorithms until ~400s. A significant disruption occurs between 400s and ~620s, after which delays return to near-zero levels. * **Pre-Disruption (200s - 400s):** Packet delay for all algorithms is negligible, hovering just above 0.0 seconds (likely < 0.05 sec). * **Disruption Period (400s - 620s):** * **OSPF & SPF:** Experience a moderate increase in delay, fluctuating between approximately 0.2 and 0.55 seconds. Their patterns are very similar. * **BF:** Shows the most severe degradation. Delay spikes to the maximum of 0.8 sec at ~420s, remains highly volatile between 0.4 and 0.8 sec until ~520s, then drops but remains elevated (~0.2-0.4 sec) until a final drop at ~620s. * **Q-R, PQ-R, AntNet, Daemon:** Exhibit a sharp, short-lived spike in delay to ~0.6-0.8 sec at ~400s, but quickly recover to lower levels (0.1-0.3 sec) by ~450s. They maintain this moderately elevated delay until ~520s, then drop back to near-zero. * **Post-Disruption (620s - 1000s):** All algorithms return to and maintain a very low packet delay, similar to the pre-disruption state (≈0.0 sec). ### Key Observations 1. **Correlated Event:** A major network event (e.g., link failure, traffic surge) at T=400s triggers a simultaneous response in both throughput and delay metrics. 2. **Performance Clustering:** Algorithms fall into distinct performance groups during the disruption: * **High-Throughput/Moderate-Delay:** OSPF, SPF. * **Lower-Throughput/Lower-Delay:** Q-R, PQ-R, AntNet, Daemon. * **Lower-Throughput/High-Delay:** BF (an outlier in delay performance). 3. **Convergence:** After the disruption ends (~T=600s), all algorithms converge to nearly identical performance in both throughput and delay, suggesting the network returns to a stable, possibly under-utilized state. 4. **BF Anomaly:** The `BF` algorithm demonstrates significantly worse and more persistent packet delay compared to all others during the disruption period, despite having throughput similar to the Q-R group. ### Interpretation This chart likely evaluates the resilience and adaptability of different routing algorithms under stress. The event at 400 seconds simulates a network disturbance. * **What the data suggests:** OSPF and SPF (likely traditional link-state algorithms) prioritize maintaining high data flow (throughput) during the event, at the cost of increased packet latency. Algorithms like Q-R, PQ-R, AntNet, and Daemon (possibly heuristic or adaptive algorithms) sacrifice some peak throughput to achieve lower and more stable delays. The `BF` (Bellman-Ford?) algorithm appears poorly suited for this scenario, suffering severe and prolonged latency issues. * **How elements relate:** The inverse relationship between throughput and delay during the disruption (400-520s) highlights a fundamental trade-off in network routing: maximizing data rate can lead to congestion and queuing delays. The post-600s convergence indicates that once the stressor is removed, the choice of routing algorithm becomes less critical for these metrics. * **Notable patterns/anomalies:** The near-perfect synchronization of the performance shift at 400s and recovery at 520s/600s across all algorithms is striking, indicating a controlled, scripted simulation event. The outlier behavior of `BF` is the most significant anomaly, suggesting it may have a slower convergence time or be more susceptible to routing loops under the tested conditions. </details> /3/4/7 windows/. increasing load series/. Di Caro /& Dorigo /7/./4 Routing Overhead Table /2 reports results concerning the overhead generated by routing packets/. For each algorithm the network load generated by the routing packets is reported as the ratio between the bandwidth occupied by the routing packets and the total available network bandwidth/. Each row in the table refers to a previously discussed experiment /(Figs/. /8 to /1/1 and /1/3 to /1/5/)/. Routing overhead is computed for the experiment with the heaviest load in the | | AntNet | OSPF | SPF | BF | Q/-R | PQ/-R | |---------------------|-------------------|-------------------|-------------------|-------------------|-------------------|-------------------| | SimpleNet /- F/-CBR | | /0/./0/1 | /0/./1/0 | /0/./0/7 | /1/./4/9 | | | NSFNET /- UP | /0/./3/3 /2/./3/9 | | /0/./8/6 | /1/./1/7 | | /2/./0/1 /9/./9/3 | | NSFNET /- RP | /2/./6/0 | /0/./1/5 /0/./1/5 | /1/./0/7 | /1/./1/7 | /6/./9/6 /5/./2/6 | /7/./7/4 | | UP/-HS | | | | | | | | NSFNET /- | /1/./6/3 | /0/./1/5 /0/./1/4 | /1/./1/4 /3/./6/8 | /1/./1/7 /1/./3/9 | /7/./6/6 /3/./7/2 | /8/./4/6 /6/./7/7 | | NTTnet /- UP | /2/./8/5 | | | | | | NTTnet /- RP /4/./4/1 /0/./1/4 /3/./0/2 /1/./1/8 /3/./3/6 /6/./3/7 and the total available network bandwidth/. All data are scaled by a factor of /1/0 /BnZr/3 /. All data are scaled by a factor of /1/0 /BnZr/3 /. The data in the table show that the routing overhead is negligible for all the algorithms with respect to the available bandwidth/. Among the adaptive algorithms/, BF shows the lowest overhead/, closely followed by SPF/. AntNet generates a slightly bigger consumption of network resources/, but this is widely compensated by the much higher performance it provides/. Q/-R and PQ/-R produce an overhead a bit higher than that of AntNet/. The routing load caused by the di/erent algorithms is a function of many factors/, speci/c of each algorithm/. Q/-R and PQ/-R are data/-driven algorithms/: if the number of data packets and//or the length of the followed paths /(because of topology or bad routing/) grows/, so will the number of generated routing packets/. BF/, SPF and OSPF have a more predictable behavior/: the generated overhead is mainly function of the topological properties of the network and of the generation rate of the routing information packets/. AntNet produces a routing overhead depending on the ants generation rate and NTTnet /- UP/-HS /3/./8/1 /0/./1/4 /4/./5/6 /1/./3/9 /3/./0/9 /4/./8/1 Table /2/: Routing Overhead/: ratio between the bandwidth occupied by the routing packets on the length of the paths they travel/. The ant tra/c can be roughly characterized as a collection of additional tra/c sources/, one for each network node/, producing very small packets /(and related acknowledgement packets/) at constant bit rate with destinations matching the o/ered data tra/c/. On average ants will travel over rather /\short/" paths and their size will grow of only /8 bytes at each hop/. Therefore/, each /\ant routing tra/c source/" represents a very light additional tra/c source with respect to network resources when the ant launching rate is not excessively high/. In scale ranging from about /0/./0/0/6 to /2/5 seconds/. Figure /1/7/, the sensitivity of AntNet with respect to the ant launching rate is reported/. For a sample case of a UP data tra/c model on NSFNET /(previously studied in Figure /9/) the interval /
g between two consecutive ant generations is progressively decreased /(/
g is the same for all nodes/)/. /
g values are sampled at constant intervals over a logarithmic /3/4/8 The lower/, dashed/, curve interpolates the AntNet/: Distributed Stigmergetic Control for Communications Networks Figure /1/7/: AntNet normalized power vs/. routing overhead/. Power is de/ned as the ratio <details> <summary>Image 16 Details</summary>  ### Visual Description ## Line Graph: AntNet Normalized Power vs. Routing Overhead ### Overview The image is a technical line graph plotting two performance metrics of an "AntNet" system against a time interval parameter. The graph uses a semi-logarithmic scale (logarithmic x-axis, linear y-axis) to show how "Normalized Power" and "Routing Overhead" change as the interval between consecutive ant generations increases. Both data series include error bars, indicating variability or confidence intervals for the measurements. ### Components/Axes * **Chart Title:** None explicitly shown above the plot area. * **Y-Axis:** * **Label:** "AntNet Normalized Power Vs. Routing Overhead" * **Scale:** Linear, ranging from 0.0 to 1.0. * **Major Ticks:** 0.0, 0.2, 0.4, 0.6, 0.8, 1.0. * **X-Axis:** * **Label:** "Interval Δg Between Two Consecutive Ants Generations (sec)" * **Scale:** Logarithmic (base 10). * **Major Ticks (labeled):** 0.001, 0.01, 0.1, 1, 10, 100. * **Minor Ticks:** Present between major ticks, following a logarithmic distribution. * **Legend:** * **Position:** Top-right quadrant of the plot area, slightly overlapping the grid. * **Entry 1:** "Normalized Power" - Represented by a solid line with square markers (□). * **Entry 2:** "Routing Overhead" - Represented by a dashed line with 'x' markers (×). * **Grid:** A fine, dotted grid is present for both major and minor ticks on both axes. ### Detailed Analysis **1. Normalized Power (Solid line, □ markers):** * **Trend:** The line shows a clear unimodal (single-peak) trend. It rises sharply from a low value, reaches a maximum, and then gradually declines. * **Data Points (Approximate, reading from graph):** * At Δg ≈ 0.005 sec: Value ≈ 0.48 (with error bar from ~0.45 to ~0.51). * At Δg ≈ 0.01 sec: Value ≈ 0.68. * **Peak:** At Δg ≈ 0.03 sec: Value ≈ 0.95 (the highest point on the graph). * At Δg ≈ 0.1 sec: Value ≈ 0.83. * At Δg ≈ 1 sec: Value ≈ 0.53. * At Δg ≈ 10 sec: Value ≈ 0.41. * At Δg ≈ 20 sec: Value ≈ 0.38 (the last data point). * **Error Bars:** The error bars are most pronounced around the peak (Δg ≈ 0.01 to 0.1 sec) and become smaller as Δg increases beyond 1 sec. **2. Routing Overhead (Dashed line, × markers):** * **Trend:** The line shows a steep, monotonic decay. It starts very high and rapidly approaches zero. * **Data Points (Approximate, reading from graph):** * At Δg ≈ 0.005 sec: Value ≈ 0.85 (the highest point for this series). * At Δg ≈ 0.01 sec: Value ≈ 0.52. * At Δg ≈ 0.02 sec: Value ≈ 0.22. * At Δg ≈ 0.05 sec: Value ≈ 0.08. * At Δg ≈ 0.1 sec: Value ≈ 0.03. * At Δg ≈ 1 sec: Value ≈ 0.005 (very close to zero). * For Δg > 1 sec: The value remains at or extremely close to 0.0. * **Error Bars:** Error bars are visible for the first few data points (Δg < 0.1 sec) but are very small, indicating low variability in the overhead measurement. ### Key Observations 1. **Inverse Relationship at Low Intervals:** For very small generation intervals (Δg < 0.03 sec), Routing Overhead is high while Normalized Power is still climbing. They cross at approximately Δg = 0.008 sec, where both values are around 0.6. 2. **Optimal Operating Point:** The system achieves its peak Normalized Power (~0.95) at an interval of Δg ≈ 0.03 sec. At this point, the Routing Overhead has already dropped significantly to ~0.15. 3. **Diminishing Returns:** Beyond the peak (Δg > 0.03 sec), increasing the interval further causes Normalized Power to decline steadily, while Routing Overhead remains negligible. This suggests a trade-off where longer intervals reduce power efficiency without providing further meaningful reduction in overhead. 4. **Asymptotic Behavior:** Routing Overhead effectively becomes zero for intervals greater than 1 second. Normalized Power appears to be approaching an asymptotic value somewhere between 0.3 and 0.4 as Δg increases towards 100 seconds. ### Interpretation This graph illustrates a fundamental performance trade-off in the AntNet system, likely a bio-inspired routing algorithm for networks. The "Interval Δg" is a key control parameter. * **What the data suggests:** There is a clear "sweet spot" for the generation interval. Setting Δg too low (frequent ant generations) creates excessive network control traffic (high Routing Overhead), which consumes resources and reduces the net "Normalized Power" (likely a measure of useful throughput or efficiency). Setting Δg too high (infrequent generations) reduces overhead to near zero but also reduces the system's responsiveness and adaptability, leading to a gradual decline in power. * **How elements relate:** The two metrics are coupled. The initial sharp drop in overhead is the primary driver for the initial sharp rise in power. After the overhead is minimized, further increases in Δg only negatively impact power, indicating the system is becoming too sluggish. * **Notable Anomaly/Insight:** The peak in power occurs *before* the overhead is fully minimized. This indicates that the optimal operating point is not at the minimum overhead, but at a point where a small, non-zero amount of overhead is tolerated to maintain sufficient network adaptation and achieve maximum useful performance. The error bars suggest that performance (power) is most variable precisely around this optimal region, which could be important for system stability considerations. </details> between delivered throughput and packet delay/. generated routing overhead expressed/, as before/, as the fraction of the available network bandwidth used by routing packets/. The upper/, solid/, curve plots the data for the obtained power normalized to its highest value/, where the power is de/ned as the ratio between the delivered throughput and the packet delay/. The value used for delivered throughput is the throughput value at time /1/0/0/0 averaged over ten trials/, while for packet delay we used the robustness of AntNet/'s internal parameter settings/. /9/0/-th percentile of the empirical distribution/. In the /gure/, we can see how an excessively small /
g causes an excessive growth of the routing overhead/, with consequent reduction of the algorithm power/. Similarly/, when /
g is too big/, the power slowly diminishes and tends toward a plateau because the number of ants is not enough to generate and maintain up/-to/-date statistics of the network status/. In the middle of these two extreme regions a wide range of /
g intervals gives raise to similar/, very good power values/, while/, at the same time/, the routing overhead quickly falls down toward negligible values/. This /gure strongly con/rms our previous assertion about the /8/. Discussion In AntNet/, the continual on/-line construction of the routing tables is the emergent result of a collective learning process/. In fact/, each forward/-backward agent pair is complex enough to /nd a good route and to adapt the routing tables for a single source/-destination path/, but it cannot solve the global routing optimization problem/. It is the interaction between the agents that determines the emergence of a global e/ective behavior from the network performance point of view/. Ants cooperate in their problem/-solving activity by communicating in an indirect and non/-coordinated way/. Each agent acts independently/. by applying a policy /3/4/9 Good routes are discovered that is a function of the information Di Caro /& Dorigo accessed through the network nodes visited/, and the information collected about the route is eventually released on the same nodes/. Therefore/, the inter/-agent communication is mediated in an explicit and implicit way by the /\environment/"/, that is/, by the node/'s data structures and by the tra/c patterns recursively generated by the data packets/' utilization of the routing tables/. This communication paradigm/, called stigmergy/, matches well the intrinsically distributed nature of the routing problem/. Cooperation among agents goes on at two levels/: /(a/) by modi/cations of the routing tables/, and /(b/) by modi/cations of local models that determine the way the ants/' performance is evaluated/. Modi/cations of the routing tables directly a/ect the routing decisions of following ants towards the same destination/, as well as the routing of data/, which/, in turn/, in/ uences the rate of arrival of other ants towards any destination/. It is interesting to remark that the used stigmergy paradigm makes the AntNet/'s mobile agents very / exible from a software engineering point of view/. In this perspective/, once the interface with the node/'s data structure is de/ned/, the internal policy of the agents can be transparently updated/. Also/, the agents could be exploited to carry out multiple concurrent tasks /(e/.g/./, collecting information for distributed - main aspects/: / AntNet can be seen as a particular instance of a parallel Monte Carlo simulation system with biased exploration/. All the other algorithms either do not explore the network management using an SNMP/-like protocol or for Web data/-mining tasks/)/. As shown in the previous section/, the results we obtained with the above stigmergetic model of computation are excellent/. In terms of throughput and average delay/, AntNet performs better than both classical and recently proposed routing algorithms on a wide range of experimental conditions/. Although this is very interesting per se/, in the following we try to justify AntNet superior performance by highlighting some of its characteristics and by comparing them with those of the competing algorithms/. We focus on the following - net or their exploration is local and tightly connected to the / ux of data packets/. / The information AntNet maintains at each node is more complete and organized in a - do/. This mechanism makes the algorithm more robust to locally wrong estimates/. / AntNet uses probabilistic routing tables/, which have the triple positive e/ect of bet/ter redistributing data tra/c on alternative routes/, of providing ants with a built/-in exploration mechanism and of allowing the exploitation of the ants/' arrival rate to - less critical way than that managed by the other algorithms/. / AntNet does not propagate local estimates to other nodes/, while all its competitors - assign cumulative reinforcements/. / It was experimentally observed that AntNet is much more robust than its competitors a departure of AntNet from the structure of classical RL algorithms/. - to the frequency with which routing tables are updated/. / The structure of AntNet allows one to draw some parallels with some well/-known reinforcement learning /(RL/) algorithms/. The characteristics of the routing problem/, that can be seen as a distributed time/-varying RL problem /(see sect/. /2/./2/)/, determines These aspects of AntNet are discussed in more detail in the following/. /3/5/0 AntNet/: Distributed Stigmergetic Control for Communications Networks /8/./1 AntNet as an on/-line Monte Carlo system with biased exploration The AntNet routing system can be seen as a collection of mobile agents collecting data about the network status by concurrently performing on/-line Monte Carlo simulations /(Ru/bistein/, /1/9/8/1/; Streltsov /& Vakili/, /1/9/9/6/)/. In Monte Carlo methods/, repeated experiments with stochastic transition components are run to collect data about the statistics of in/terest/. Similarly/, in AntNet ants explore the network by performing random experiments /(i/.e/./, building paths from source to destination nodes using a stochastic policy dependent on the past and current network states/)/, and collect on/-line information on the network status/. A built/-in variance reduction e/ect is determined /(i/) by the way ants/' destinations are assigned/, biased by the most frequently observed data/'s destinations/, and /(ii/) by the way the ants/' policy makes use of current and past tra/c information /(that is/, inspection of the local queues/' status and probabilistic routing tables/)/. In this way/, the explored paths match the most interesting paths from a data tra/c point of view/, which results in a very e/cient variance reduction e/ect in the stochastic sampling of the paths/. Di/erently from usual o//-line Monte Carlo systems/, in AntNet the state space sampling is performed on/-line/, that is/, the sampling of the statistics and the controlling of the non/-stationary tra/c process are ## exploring ants is negligible for a wide range of values/, allowing very good performance/. performed concurrently/. This way of exploring the network concurrently with data tra/c is very di/erent from what happens in the other algorithms where/, either there is no exploration at all /(OSPF/, SPF and BF/)/, or exploration is both tightly coupled to data tra/c and of a local nature /(Q/-R and PQ/-R/)/. Conveniently/, as was shown in Section /7/./4/, the extra tra/c generated by /8/./2 Information management at each network node Key characteristics of routing algorithms are the type of information used to build//update routing tables and the way this information is propagated/. All the algorithms /(except the static OSPF/) make use at each node of two main components/: a local model M of some cost measures and a routing table T /. SPF and BF use M to estimate smoothed averages of the local link costs/, that is/, of the distances to the neighbor nodes/. In this case/, Mis a local model maintaining estimates of only local components/. In Q/-R the local model is /ctitious because the raw transition time is directly used as a value to update T /. PQ/-R uses a slightly more sophisticated model with respect to Q/-R/, storing also a measure of the link utilization/. All these algorithms propagate part of their local information to the other nodes/, which/, in turn/, make use of it to update their routing tables and to build a global view of the network/. In SPF and BF the content of each T is updated/, at regular intervals/, by a /\memoryless strategy/"/: the new entries do not depend on the old values/, that are discarded/. Therefore/, the whole adaptive component of the routing system is represented by the model M/. Otherwise/, in Q/-R and PQ/-R the adaptive content of M is almost negligible and the adaptive component of the algorithm is represented by the smoothed average carried out by the Q/-learning/-like rule/. AntNet shows characteristics rather di/erent from its competitors/: its model M contains a memory/-based local perspective of the global status of the network/. The content of M allow the reinforcements to be weighted on the basis of a rich statistical description of the network dynamics as seen by the local node/. These reinforcements are used to update the routing table/, the other adaptive component /3/5/1 ## of all the estimates and decisions/. Di Caro /& Dorigo maintained at the node/. The T updates are carried out in an asynchronous way and as a function of their previous values/. Moreover/, while T is used in a straightforward probabilistic way by the data packets/, traveling ants select the next node by using both T /, that is/, an adaptive representation of the past policy/, and a model of the current local link queues/, that is/, an instantaneous representation of the node status/. It is evident that AntNet builds and uses more information than its competitors/: two di/erent memory/-based components and an instantaneous predictor are used and combined at di/erent levels/. Moreover/, in this way AntNet robustly redistributes among these completely local components the criticality /8/./3 AntNet/'s robustness to wrong estimates As remarked above/, AntNet/, di/erently from its competitors/, does not propagate local estimates to other nodes/. Each node routing table is updated independently/, by using local information and the ants/' experienced trip time/. Moreover/, /(i/) each ant experiment a/ects only one entry in the routing table of the visited nodes/, the one relative to the ant/'s destination/, and/, /(ii/) the local information is built from the /\global/" information collected by traveling ants/, implicitly reducing in this way the variance in the estimates/. These characteristics make AntNet particularly robust to wrong estimates/. On the contrary/, in all the other algorithms a locally wrong estimate will be propagated to all other nodes and will be used to compute estimates to many di/erent destinations/. How bad this is for the algorithm performance depends on how long the wrong estimate e/ect lasts/. In particular/, this will be a function of the time window over which estimates are computed for SPF and /8/./4 AntNet/'s probabilistic use of routing tables to route data packets All the tested algorithms but AntNet use deterministic routing tables/. /1/5 In these algorithms/, entries in the routing tables contain distance//time estimates to the destinations/. These estimates can provide misleading information if the algorithm is not fast enough to follow the tra/c / uctuations/, as can be the case under heavy load conditions/. Instead/, AntNet routing tables have probabilistic entries that/, although re/ ecting the goodness of a particular path choice with respect to the others available/, do not force the data packets to choose the perceived best path/. This has the positive e/ect of allowing a better balancing of the tra/c load on di/erent paths/, with a resulting better utilization of the resources /(as was shown in particular in the experiments with the SimpleNet/)/. As remarked at the end of Section /4/./1/, the intrinsic probabilistic structure of the routing tables and the way they are updated allow AntNet to exploit the ant/'s arrival rate as a way to assign implicit /(cumulative/) reinforcements to discovered paths/. It is not obvious how the same e/ect could be obtained by using routing tables containing distance//time estimates and using ## BF/, and of the learning parameters for Q/-R and PQ/-R/. this estimates in a probabilistic way/. In fact/, in this case each new trip time sample would /1/5/. Singh/, Jaakkola/, and Jordan /(/1/9/9/4/) showed that stochastic policies can yield higher performance than deterministic policies in the case of an incomplete access to the state information of the environment/. In /(Jaakkola/, Singh/, /& Jordan/, /1/9/9/5/)/, the same authors developed a Monte/-Carlo/-based stochastic policy evaluation algorithm/, con/rming the usefulness of the Monte/-Carlo approach/, used in AntNet too/, to deal with incomplete information problems/. /3/5/2 AntNet/: Distributed Stigmergetic Control for Communications Networks modify the statistical estimate that would simply oscillate around its expected value without ## whole environment plays a key/, active role in learning good state/-action pairs/. inducing an arrival/-dependent cumulative e/ect/. Probabilistic routing tables provide some remarkable additional bene/ts/: /(a/) they give to the ants a built/-in exploration method in discovering new/, possibly better/, paths/, and /(b/) since ants and data routing are independent in AntNet/, the exploration of new routes can continue while/, at the same time/, data packets can exploit previously learned/, reliable information/. It is interesting to note that the use of probabilistic routing tables whose entries are learned in an adaptive way by changing on positive feedback and ignoring negative feedback/, is reminiscent of older automata approaches to routing in telecommunications networks/. In these approaches/, a learning automaton is usually placed on each network node/. An automaton is de/ned by a set of possible actions and a vector of associated probabilities/, a continuous set of inputs and a learning algorithm to learn input/-output associations/. Automata are connected in a feedback con/guration with the environment /(the whole network/)/, and a set of penalty signals from the environment to the actions is de/ned/. Routing choices and modi/cations to the learning strategy are carried out in a probabilistic way and according to the network conditions /(see for example /(Nedzelnitsky /& Narendra/, /1/9/8/7/; Narendra /& Thathachar/, /1/9/8/0/)/)/. The main di/erence lies in the fact that in AntNet the ants are part of the environment itself/, and they actively direct the learning process towards the most interesting regions of the search space/. That is/, the /8/./5 AntNet robustness to routing table update frequency In BF and SPF the broadcast frequency of routing information plays a critical role/, particu/larly so for BF/, which has only a local representation of the network status/. This frequency is unfortunately problem dependent/, and there is no easy way to make it adaptive/, while/, at the same time/, avoiding large oscillations/. In Q/-R and PQ/-R/, routing tables updating is data driven/: only those Q/-values belonging to pairs /(i/; j/) of neighbor nodes visited by packets are updated/. Although this is a reasonable strategy given that the exploration of new routes could cause undesired delays to data packets/, it causes delays in discovering new good routes/, and is a great handicap in a domain where good routes could change all the time/. In OSPF/, in which routing tables are not updated/, we set static link costs on the basis of their physical characteristics/. This lack of an adaptive metric is the main reason of the poor performance of OSPF /(as remarked in Section /5/, we slightly penalized OSPF with respect to its real implementations/, where additional heuristic knowledge about tra/c patterns is used by network administrators to set link costs/)/. In AntNet/, we experimentally observed the robustness to changes in the ants/' generation rate/: for a wide range of genera/tion rates/, rather independent of the network size/, the algorithm performance is very good /8/./6 AntNet and reinforcement learning The characteristics of the routing problem allow one to interpret it as a distributed/, stochas/tic time/-varying RL problem/. This fact/, as well as the structure of AntNet/, make it natural to draw some parallels between AntNet and classical RL approaches/. It is worth remarking ## and the routing overhead is negligible /(see Section /7/./4/)/. that those RL problems that have been most studied/, and for which algorithms have been de/- /3/5/3 Di Caro /& Dorigo veloped/, are problems where/, unlike routing/, assumptions like Markovianity or stationarity of the process considered are satis/ed/. The characteristics of the adaptive routing problem make it very di/cult and not well suited to be solved with usual RL algorithms/. This fact/, and rather simple/, to meet computational requirements/. Another way of seeing AntNet as a classical RL system is related to its interpretation as a parallel replicated Monte Carlo /(MC/) system/. As was shown by Singh and Sutton /(/1/9/9/6/)/, a /rst/-visit MC /(only the /rst visit to a state is used to estimate its value during a trial/) simulation system is equivalent to a batch temporal di/erence /(TD/) method with replacing traces and decay parameter //=/1/. Although AntNet is a /rst/-visit MC simulation system/, there are some important di/erences with the type of MC used by Singh and Sutton /(and in other RL works/)/, mainly due to the di/erences in the considered class of problems/. In AntNet/, outcomes of experiments are both used to update local models able to capture the variability of the whole network status /(only partially observable/) and to generate a sequence of stochastic policies/. On the contrary/, in the MC system considered by Singh and Sutton/, outcomes of the experiments are used to compute /(reduced/) maximum/-likelihood estimates of the expected mean and variance of the states/' returns /(i/.e/./, the total reward following a visit of a state/) of a Markov chain/. In spite of these di/erences/, the weak parallel with TD/(//) methods is rather interesting/, and allows to highlight an important di/erence between AntNet and its competitors /(and general TD methods/)/: in AntNet/, following the generation of a stochastic transition chain by the forward ant/, there is no back/-chaining of the information from one state /(i/.e/./, a triple fcurrent node/, destination node/, next hop nodeg/) to its predecessors/. Each state is rewarded only on the basis of the ant/'s trip time information strictly relevant to it/. This approach is completely di/erent from that followed by /(TD methods/) Q/-R/, PQ/-R/, BF and/, in a di/erent perspective/, by SPF/. In fact/, these algorithms build the distance estimates at each node by using the predictions made at other nodes/. In particular/, Q/-R and PQ/-R/, which propagate the estimation information only one step back/, are precisely distributed versions of the TD/(/0/) class of algorithms/. They could be transformed into generic TD/(//)/, /0 /< / / /1/, by transmitting backward to all the previously visited nodes the information collected by the routing packet generated after each data hop/. Of course/, this would greatly increase the routing tra/c generated/, because it has to be done after each hop of each data packet/, making the approach at least very costly/, if feasible as we explain below/, determines a departure of AntNet from classical RL algorithms/. A /rst way to relate the structure of AntNet to that of a /(general/) RL algorithm is connected to the way the outcomes of the experiments/, the trip times T k/!d /, are processed/. The transformation from the raw values T k/!d to the more re/ned reinforcements r are reminiscent of what happens in Actor/-Critic systems /(Barto/, Sutton/, /& Anderson/, /1/9/8/3/)/: the raw reinforcement signal is processed by a critic module/, which is learning a model /(the node/'s component M/) of the underlying process/, and then is fed to the learning system /(the routing table T /) transformed into an evaluation of the policy followed by the ants/. In our case/, the critic is both adaptive/, to take into account the variability of the tra/c process/, at all/. In general/, using temporal di/erences methods in the context of routing presents an impor/tant problem/: the key condition of the method/, the self/-consistency between the estimates /1/6/. For instance/, the prediction made at node k about the time to/-go to the destination node d should be of successive states /1/6 may not be strictly satis/ed in the general case/. This is due to the /3/5/4 AntNet/: Distributed Stigmergetic Control for Communications Networks fact that /(i/) the dynamics at each node are related in a highly non/-linear way to the dy/namics of all its neighbors/, /(ii/) the tra/c process evolves concurrently over all the nodes/, and /(iii/) there is a recursive interaction between the tra/c patterns and the control actions /(that is/, the modi/cations of the routing tables/)/. This aspect can explain in part the poor performance of the pure TD/(/0/) algorithms Q/-R and PQ/-R/. /9/. Related Work Algorithms based on the ant colony metaphor were inspired by the ant colony foraging behavior /(Beckers et al/./, /1/9/9/2/)/. These were /rst proposed by Dorigo /(/1/9/9/2/)/, Colorni et al/. /(/1/9/9/1/) and Dorigo et al/. /(/1/9/9/1/, /1/9/9/6/) and were applied to the traveling salesman problem /(TSP/)/. Apart from the natural metaphor/, the idea behind that /rst application was similar to the one presented in this paper/: a set of agents that repeatedly run Monte Carlo experiments whose outcomes are used to change the estimates of some variables used by subsequent ants to build solutions/. In ant/-cycle/, one of the /rst ant/-based algorithms/, a value called /\pheromone trail/" is associated to each edge of the graph representing the TSP/. Each ant builds a tour by exploiting the pheromone trail information as follows/. When in node i an ant chooses the next node j to move to among those not visited yet with a probability P ij that is a function of the amount of pheromone trail on the edge connecting i to j /(as well as of a local heuristic function/; the interested reader can /nd a detailed description of ant/-cycle elsewhere /(Dorigo/, /1/9/9/2/; Dorigo et al/./, /1/9/9/6/)/)/. The value of the pheromone trails is updated once all ants have built their tours/. Each ant adds to all visited edges a quantity of pheromone trail proportional to the quality of the tour generated /(the shorter the tour/, the higher the quantity of pheromone trail added/)/. This has an e/ect very similar to AntNet/'s increase of routing tables probabilities/, since a higher pheromone trail on a particular edge will increase its probability of being chosen in the future/. There are obviously many di/erences between ant/-cycle and AntNet/, mostly due to the very di/erent types of problems to which they have been applied/, a combinatorial completely bi/-directional/. The path n/0 /; n /1 /; n /2 /; /: /: /: /; nk connecting n /0 and n k will exhibit the additively related to the prediction for the same destination from each one of k/'s neighbors/, being each /3/5/5 optimization problem versus a distributed/, stochastic/, time varying/, real/-time problem/. Though the majority of previous applications of ant colony inspired algorithms con/cern combinatorial optimization problems/, there have been recent applications to routing/. Schoonderwoerd et al/. /(/1/9/9/6/, /1/9/9/7/) were the /rst to consider routing as a possible applica/tion domain for ant colony algorithms/. Their ant/-based control /(ABC/) approach/, which is applied to routing in telephone networks/, di/ers from AntNet in many respects/. The main di/erences are a direct consequence of the di/erent network model they considered/, which has the following characteristics /(see Figure /1/8/)/: /(i/) connection links potentially carry an in/nite number of full/-duplex/, /xed bandwidth channels/, and /(ii/) transmission nodes are crossbar switches with limited connectivity /(that is/, there is no necessity for queue manage/ment in the nodes/)/. In such a model/, bottlenecks are put on the nodes/, and the congestion degree of a network can be expressed in terms of connections still available at each switch/. As a result/, the network is cost/-symmetric/: the congestion status over available paths is neighbor one of the ways to go to d/. Di Caro /& Dorigo same level of congestion in both directions because the congestion depends only on the state <details> <summary>Image 17 Details</summary>  ### Visual Description ## Diagram: Network Link Interconnection ### Overview The image is a technical schematic diagram illustrating a network or switching architecture where four primary communication links (Link 1, Link 2, Link 3, Link 4) converge at a central interconnection point. The diagram emphasizes the relationship between the number of channels available on each link and the number of possible cross-connections within the central fabric. ### Components/Axes The diagram is composed of the following labeled elements: 1. **Links (Peripheral Components):** * **Link 1:** A vertical rectangular block positioned at the top center, extending downwards. * **Link 2:** A horizontal rectangular block positioned at the right center, extending leftwards. * **Link 3:** A vertical rectangular block positioned at the bottom center, extending upwards. * **Link 4:** A horizontal rectangular block positioned at the left center, extending rightwards. * **Visual Texture:** All four link blocks are filled with a pattern of small, evenly spaced dots. 2. **Central Interconnection Fabric:** * A square grid located at the geometric center of the diagram where all four links intersect. * The grid is composed of horizontal and vertical lines, creating a mesh pattern distinct from the dotted pattern of the links. 3. **Annotations and Labels:** * **"N bidirectional channels":** Text located to the left of Link 4. A curved arrow originates from this text and points directly to the dotted pattern of Link 4, indicating that each link (exemplified by Link 4) contains N bidirectional communication channels. * **"n << N possible connections":** Text located below and to the right of the central grid. A straight arrow originates from this text and points to the central grid area. The mathematical notation "n << N" signifies that the number of actual connections (`n`) established within the central fabric is much less than the total number of channels (`N`) available across all links. ### Detailed Analysis * **Spatial Relationships:** The four links are arranged orthogonally (top, bottom, left, right) around the central grid, suggesting a symmetric, cross-connect architecture. The central grid is the sole point of intersection for all links. * **Flow and Connection:** The diagram implies that communication channels from any link can be connected to channels on any other link via the central grid. The arrow from "N bidirectional channels" to Link 4 serves as a representative label for all links. * **Quantitative Relationship:** The core technical message is captured in the annotation "n << N possible connections." This indicates a system where the switching or connection capacity (`n`) is a small subset of the aggregate raw channel capacity (`N * 4 links`). This is a common design in non-blocking or partially blocking switch fabrics. ### Key Observations 1. **Symmetry and Abstraction:** The diagram is highly abstract and symmetric, focusing on logical connectivity rather than physical implementation. The use of identical dotted patterns for all links reinforces their functional equivalence. 2. **Critical Notation:** The inequality `n << N` is the most significant data point. It defines the system's scalability or constraint, highlighting that not all potential channel pairings can be simultaneously active. 3. **Visual Hierarchy:** The central grid, with its distinct line-based pattern, is visually set apart from the dotted links, emphasizing its role as the active switching element versus the passive transport channels. ### Interpretation This diagram represents a fundamental model for a communication switch, router, or cross-connect system. The four links could represent ports facing different network segments, line cards, or directions (North, South, East, West). The key insight is the **resource disparity**: while each link provides a large pool of raw capacity (`N` channels each), the central interconnecting fabric has a much more limited capacity to create active paths (`n` connections). This suggests: * **Efficiency or Cost Design:** The system is designed under the assumption that not all channels will be used simultaneously, allowing for a smaller, cheaper, or faster central fabric. * **Potential for Blocking:** If `n` is insufficient for the traffic demand, the system may experience blocking, where some connection requests are denied despite available channels on the links. * **Scalability Challenge:** To increase total throughput, one must scale both the link capacity (`N`) *and* the central fabric's connection capacity (`n`), with the latter being the more critical and potentially limiting factor. The diagram succinctly communicates the architectural trade-off between edge capacity and core connectivity in a network node. </details> of the nodes in the path/. Moreover/, Figure /1/8/: Network node in the telecommunications network model of Schoonderwoerd et dealing with telephone networks/, each call occupies exactly one physical channel across the path/. Therefore/, /\calls/" are not multiplexed over the links/, but they can be accepted or refused/, de/pending on the possibility of reserving a physical circuit connecting the caller and the receiver/. All of these modeling assumptions make the prob/lem of Schoonderwoerd et al/. very di/erent from the cost/-asymmetric routing problem for data networks we presented in this paper/. This dif/ference is re/ ected in many algorithmic di/er/ences between ABC and AntNet/, the most im/portant of which is that in ABC ants update pheromone trails after each step/, without waiting for the completion of an experiment as done in AntNet/. This choice/, which is reminiscent of the by the cost/-symmetry assumption made by the authors/. Other di/erences are that ABC does not use local models to score the ants trip times/, nor local heuristic information and ant/-private memory to improve the ants decision policies/. Also/, it does not recover from cycles and does not use the information contained in all the al/. /(/1/9/9/6/)/. pheromone trail updating strategy implemented in ant/-density/, another of the /rst ant colony based algorithms /(Dorigo et al/./, /1/9/9/1/; Dorigo/, /1/9/9/2/; Colorni et al/./, /1/9/9/1/)/, makes ABC behavior closer to real ants/'/, and was made possible ant sub/-paths/. Because of the di/erent network model used and of the many implementation details tightly bound to the network model/, it was impossible for us to re/-implement and compare ## very often not met/. the ABC algorithm with AntNet/. Subramanian/, Druschel/, and Chen /(/1/9/9/7/) have proposed an ant/-based algorithm for packet/-switched nets/. Their algorithm is a straightforward extension of Schoonderwoerd et al/. system by adding so/-called uniform ants/, an additional exploration mechanism that should avoid a rapid sub/-optimal convergence of the algorithm/. A limitation of Subramanian et al/. work is that/, although the algorithm they propose is based on the same cost/-symmetry hypothesis as ABC/, they apply it to packet/-switched networks where this requirement is /1/0/. Conclusions and Future Work In this paper/, we have introduced AntNet/, a novel distributed approach to routing in packet/switched communications networks/. We compared AntNet with /6 state/-of/-the/-art routing algorithms on a variety of realistic testbeds/. AntNet showed superior performance and robustness to internal parameter settings for almost all the experiments/. AntNet/'s most innovative aspect is the use of stigmergetic communication to coordinate the actions of a set of agents that cooperate to build adaptive routing tables/. Although this is not the /rst application of stigmergy/-related concepts to optimization problems /(e/.g/./, Dorigo et al/./, /3/5/6 AntNet/: Distributed Stigmergetic Control for Communications Networks /1/9/9/1/; Dorigo/, /1/9/9/2/; Dorigo et al/./, /1/9/9/6/; Bonabeau/, Dorigo/, /& Th/ eraulaz/, /1/9/9/9/)/, the appli/cation presented here is unique in many respects/. First/, in AntNet/, stigmergy/-based control is coupled to a model/-building activity/: information collected by ants is used not only to modify routing tables/, but also to build local models of the network status to be used to better direct the routing table modi/cations/. Second/, this is the /rst attempt to evaluate stigmergy/-based control on a realistic simulator of communications networks/: the used sim/ulator retains many of the basic components of a real routing system/. An interesting step forward/, in the direction of testing the applicability of the idea presented to real networks/, would be to rerun the experiments presented here using a complete Internet simulator/. Third/, this is also the /rst attempt to evaluate stigmergy/-based control by comparing a stigmergetic algorithm to state/-of/-the/-art algorithms on a realistic set of benchmark prob/lems/. It is very promising that AntNet turned out to be the best performing in all the - which are listed below/. /1/) A /rst/, natural/, extension of the current work would consider the inclusion in the simulator of / ow and congestion control components /(with re/-transmissions and error man/agement/)/. This inclusion will require a paired tuning of the routing and / ow/-congestion tested conditions/. There are obviously a number of directions in which the current work could be extended/, - components/, to select the best matching between their dynamics/. /2/) In AntNet/, each forward ant makes a random experiment/: it builds a path from a source node s to a destination node d/. The path is built exploiting the information contained in the probabilistic routing tables and the status of the queues of the visited nodes/. While building the path/, the ant collects information on the status of the network/. This is done by sharing link queues with data packets/, and by measuring waiting times of queues and traversal times that will be used as raw reinforcements by backward ants/. Since forward ants share queues with data packets/, the time required to run an experiment depends on the network load/, and is approximately the same as the time T s/!d required for a packet to go from the same source node s to the same destination node d/. This delays the moment the information collected by forward ants can be distributed by backward ants/, and makes it less up/-to/-date than it could be/. A possible improvement in this schema would be to add a model of link/-queue depletion to nodes/, and to let forward ants use high priority queues to reach their destinations without storing crossing times /(for a /rst step in this direction see Di Caro /& Dorigo/, /1/9/9/8/)/. Backward ants would then make the same path/, in the opposite direction/, as forward ants/, but use the queue local models they /nd on their way to estimate local /\virtual/" queueing and crossing times/. Raw reinforcements/, used to update the routing tables/, are then computed using these estimates/. Clearly/, here there is a trade/-o/ between delayed but real information and more recent but estimated information/. It will be interesting to see which scheme works better/, although we are con/dent that the local queue models should allow the backward ants to build estimates accurate enough to make the improved system more e/ective than the current AntNet/, at a cost of a little of our work would therefore be to study versions of AntNet closer to TD/(//) algorithms/. - increase in computational complexity at the nodes/. /3/) As we discussed in Section /8/, AntNet is missing one of the main components of classical RL//TD algorithms/: there is no back/-chaining of information from a state to previous ones/, each node policy is learned by using a complete local perspective/. An obvious extension /3/5/7 Di Caro /& Dorigo In this case each node should maintain Q/-values expressing the estimate of the distance to each destination via each neighbor/. These estimates should be updated by using both the ant trip time outcome and the estimates coming from successive nodes /(closer to the as a routing algorithm/. /5/) In AntNet/, whenever an ant uses a link its desirability /(probability/) is incremented/. Although this strategy/, which /nds its roots in the ant colony biological metaphor that inspired our work/, allowed us to obtain excellent results/, it would be interesting to investigate the use of negative reinforcements/, even if it can potentially lead to stability problems/, as observed by people working on older automata systems/. As discussed before/, AntNet di/ers from automata systems because of the active role played by the ants/. Therefore/, the use of negative reinforcements could show itself to be e/ective/, for example/, in reducing the destination node/) that could be also carried by the backward ant/. /4/) In this paper we applied AntNet to routing in datagram communications networks/. It is reasonable to think that AntNet could be easily adapted to be used for the generation of real/-time car route guidance in Dynamic Tra/c Assignment /(DTA/) systems /(see for example Yang/, /1/9/9/7/)/. DTA systems exploit currently available and emerging computer/, communi/cation/, and vehicle sensing technologies to monitor/, manage and control the transportation system /(the attention is now focused mainly on highway systems/) and to provide various levels of information and advice to system users so that they can make timely and informed travel decisions/. Therefore/, adaptive routing of vehicle tra/c presents very similar features to the routing of data packets in communications networks/. Moreover/, vehicle tra/c control systems have the interesting property of a very simpli/ed /\transport/" layer/. In fact/, many activities that interfere with routing and that are implemented in the transport layer of communications networks do not exist/, or exist only to a limited extent/, in vehicles tra/c control algorithms/. For example/, typical transport layer activities like data acknowledge/ment and retransmission cannot be implemented with real vehicles/. Other activities/, like / ow control/, have strong constraints /(e/.g/./, people would not be happy to be forbidden to leave their o/ces for/, say/, one hour on the grounds that there are already too many cars on the streets/!/)/. This makes AntNet still more interesting since it can express its full potential probability of choosing a given link if the ant that used it performed very badly/. Acknowledgements This work was supported by a Madame Curie Fellowship awarded to Gianni Di Caro /(CEC/TMR Contract N/. ERBFMBICT /9/6/1/1/5/3/)/. Marco Dorigo is a Research Associate with the FNRS/. We gratefully acknowledge the help received from Tony Bagnall/, Nick Bradshaw and George Smith/, who proofread and commented an earlier draft of this paper/, as well as the many useful comments provided by the three anonymous referees and by Craig Boutilier/, the associate editor who managed the review process/. Appendix A/. Optimal and Shortest Path Routing In this appendix/, the characteristics of the two most used routing paradigms/, optimal and shortest path routing /(introduced in Section /2/./1/) are summarized/: /3/5/8 AntNet/: Distributed Stigmergetic Control for Communications Networks A/./1 Optimal routing Optimal routing /(Bertsekas /& Gallager/, /1/9/9/2/) has a network/-wide perspective and its ob/- conservation constraint can be explicitly stated only if the tra/c arrival rate is known/. The routing policy consists of splitting any source/-target tra/c pair at strategic points/, then shifting tra/c gradually among alternative routes/. This often results in the use of jective is to optimize a function of all individual link / ows/. Optimal routing models are also called / ow models because they try to optimize the total mean / ow on the network/. They can be characterized as multicommodity / ow problems/, where the commodities are the tra/c / ows between the sources and the destinations/, and the cost to be optimized is a function of the / ows/, subject to the constraints of / ow con/servation at each node and positive / ow on every link/. It is worth observing that the / ow multiple paths for a same tra/c / ow between an origin/-destination pair/. Implicit in optimal routing is the assumption that the main statistical characteristics of the tra/c are known and not time/-varying/. Therefore/, optimal routing can be used for static and centralized//decentralized routing/. It is evident that this kind of solution su/ers all the problems of static routers/. A/./2 Shortest path routing Shortest path routing /(Wang /& Crowcroft/, /1/9/9/2/) has a source/-destination pair perspective/. As opposed to optimal routing/, there is no global cost function to be optimized/. Instead/, the route between each node pair is considered by itself and no a priori knowledge about the tra/c process is required /(although of course such knowledge could be fruitfully used/)/. If costs are assigned in a dynamic way/, based on statistical measures of the link congestion state/, a strong feedback e/ect is introduced between the routing policies and the tra/c patterns/. This can lead to undesirable oscillations/, as has been theoretically predicted and observed in practice /(Bertsekas /& Gallager/, /1/9/9/2/; Wang /& Crowcroft/, /1/9/9/2/)/. Some very popular cost metrics take into account queuing and transmission delays/, link usage/, link capacity and various combination of these measures/. The way costs are updated usually involves attempting to reduce big variations considering both long/-term and short/-term statistics of link congestion states /(Khanna /& Zinky/, /1/9/8/9/; Shankar/, Alaettino/ glu/, Dussa/- assumptions about the tra/c patterns are strongly violated in practice/. Considering the di/erent content stored in each routing table/, shortest path algorithms can be further subdivided in two classes called distance/-vector and link/-state /(Steenstrup/, /1/9/9/5/; Shankar et al/./, /1/9/9/2b/)/. The common behavior of most shortest path algorithms can be Zieger/, /& Matta/, /1/9/9/2b/)/. On the other hand/, if the costs are static/, they will re/ ect both some measure of the expected//wished tra/c load over the links and their transmission capacity/. Of course/, serious loss of e/ciency could arise in case of non/-stationary conditions or when the a priori - depicted as follows/. /1/. Each node assigns a cost to each of its outgoing links/. This cost can be static or dynamic/. In the latter case/, it is updated in presence of a link failure or on the basis of some observed link/-tra/c statistics averaged over a de/ned time/-window/. /3/5/9 Di Caro /& Dorigo - /2/. Periodically and without a required inter/-node synchronization/, each node sends to all of its neighbors a packet of information describing its current estimates about some - executes some class/-speci/c actions/. /4/. Routing decisions can be made in a deterministic way/, choosing the best path indicated by the information stored in the routing table/, or adopting a more / exible strategy which uses all the information stored in the table to choose some randomized or - quantities /(link costs/, distance from all the other nodes/, etc/./)/. /3/. Each node/, upon receiving the information packet/, updates its local routing table and alternative path/. A/./2/./1 Distance/-vector Distance/-vector algorithms make use of routing tables consisting of a set of triples of the form /(Destination/, Estimated Distance/, Next Hop/)/, de/ned for all the destinations in the network and for all the neighbor nodes of the considered switch/. /1/7 In this case/, the required topological information is represented by the list of the reachable nodes identi/ers/. The average per node memory occupation is of order O/(Nn/)/, where N is the number of nodes in the network and n is the average connectivity degree /(i/.e/./, the average number of neighbor In the following/, the main features speci/c to each class are described/. nodes considered over all the nodes/)/. The algorithm works in an iterative/, asynchronous and distributed way/. The information that every node sends to its neighbors is the list of its last estimates of the distances from itself to all the other nodes in the network/. After receiving this information from a neighbor node j/, the receiving node i updates its table of distance estimates overwriting the entry relationship/: corresponding to node j with the received values/. Routing decisions at node i are made choosing as next hop node the one satisfying the $$\arg \min _ { j \in N } \{ a _ { j } + D _ { j } \}$$ the estimated shortest distance from node j to the destination/. It can be shown that this process converges in /nite time to the shortest paths with respect to the used metric if no link cost changes after a given time /(Bertsekas /& Gallager/, j/2Ni where dij is the assigned cost to the link connecting node i with its neighbor j and D j is /1/9/9/2/)/. The above brie/ y described algorithm is known in literature as distributed Bellman/-Ford /(Bellman/, /1/9/5/8/; Ford /& Fulkerson/, /1/9/6/2/; Bertsekas /& Gallager/, /1/9/9/2/) and it is based on the principles of dynamic programming /(Bellman/, /1/9/5/7/; Bertsekas/, /1/9/9/5/)/. It is the prototype and the ancestor of a wider class of distance/-vector algorithms /(Malkin /& Steenstrup/, /1/9/9/5/) developed with the aim of reducing the risk of circular loops and of the destinations only/. accelerating the convergence in case of rapid changes in link costs/. /1/7/. In some cases/, only the best estimates are kept at nodes/. Therefore/, the above triples are de/ned for all /3/6/0 AntNet/: Distributed Stigmergetic Control for Communications Networks A/./2/./2 Link/-state Link/-state algorithms make use of routing tables containing much more information than that used in vector/-distance algorithms/. In fact/, at the core of link/-state algorithms there is a distributed and replicated database/. This database is essentially a dynamic map of the whole network/, describing the details of all its components and their current interconnections/. Using this database as input/, each node calculates its best paths using an appropriate algorithm like Dijkstra/'s /(/1/9/5/9/) algorithm /(a wide variety of alternative e/cient algorithms are available/, as described for example in Cherkassky/, Goldberg/, /& Radzik/, /1/9/9/4/)/. The minimize the number of re/-transmissions/. As in the case of vector/-distance/, the described algorithm is a general template and a variety of di/erent versions have been implemented to make the algorithm behavior more memory requirements for each node in this case are O/(N /2 /)/. In the most common form of link/-state algorithm/, each node acts autonomously/, broad/casting information about its link costs and states and computing shortest paths from itself to all the destinations on the basis of its local link costs estimates and of the estimates received from other nodes/. Each routing information packet is broadcast to all the neighbor nodes that in turn send the packet to their neighbors and so on/. A distributed / ooding mechanism /(Bertsekas /& Gallager/, /1/9/9/2/) supervises this information transmission trying to robust and e/cient /(Moy/, /1/9/9/8/)/. - References Alaettino/ glu/, C/./, Shankar/, A/. U/./, Dussa/-Zieger/, K/./, /& Matta/, I/. /(/1/9/9/2/)/. Design and imple/mentation of MaRS/: A routing testbed/. Tech/. rep/. UMIACS/-TR/-/9/2/-/1/0/3/, CS/-TR/-/2/9/6/4/, Institute for Advanced Computer Studies and Department of Computer Science/, Uni/- - Cybernetics/, SMC/-/1/3/, /8/3/4/{/8/4/6/. Beckers/, R/./, Deneubourg/, J/. L/./, /& Goss/, S/. /(/1/9/9/2/)/. Trails and U/-turns in the selection of the - versity of Maryland/, College Park /(MD/)/. Barto/, A/. G/./, Sutton/, R/. S/./, /& Anderson/, C/. W/. /(/1/9/8/3/)/. Neuronlike adaptive elements that can solve di/cult learning control problems/. IEEE Transaction on Systems/, Man and - shortest path by the ant Lasius Niger/. Journal of Theoretical Biology/, /1/5/9/, /3/9/7/{/4/1/5/. - Bellman/, R/. /(/1/9/5/8/)/. On a routing problem/. Quarterly of Applied Mathematics/, /1/6/(/1/)/, /8/7/{/9/0/. - Bellman/, R/. /(/1/9/5/7/)/. Dynamic Programming/. Princeton University Press/. - Bertsekas/, D/. /(/1/9/9/5/)/. Dynamic Programming and Optimal Control/. Athena Scienti/c/. - Bertsekas/, D/./, /& Tsitsiklis/, J/. /(/1/9/9/6/)/. Neuro/-Dynamic Programming/. Athena Scienti/c/. Bolding/, K/./, Fulgham/, M/. L/./, /& Snyder/, L/. /(/1/9/9/4/)/. The case for chaotic adaptive routing/. Tech/. rep/. CSE/-/9/4/-/0/2/-/0/4/, Department of Computer Science/, University of Washington/, /3/6/1 - Bertsekas/, D/./, /& Gallager/, R/. /(/1/9/9/2/)/. Data Networks/. Prentice/-Hall/. Seattle/. Di Caro /& Dorigo - Bonabeau/, E/./, Dorigo/, M/./, /& Th/ eraulaz/, G/. /(/1/9/9/9/)/. From Natural to Arti/cial Swarm - /6 /(NIPS/6/)/, pp/. /6/7/1/{/6/7/8/. San Francisco/, CA/:Morgan Kaufmann/. Brakmo/, L/. S/./, O/'Malley/, S/. W/./, /& Peterson/, L/. L/. /(/1/9/9/4/)/. TCP vegas/: New techniques for congestion detection and avoidance/. ACM Computer Communication Review /(SIG/- - Intelligence/. Oxford University Press/. Boyan/, J/./, /& Littman/, M/. /(/1/9/9/4/)/. Packet routing in dinamically changing networks/: A rein/forcement learning approach/. In Advances in Neural Information Processing Systems - COMM/'/9/4/)/, /2/4 /(/4/)/. Cheng/, C/./, Riley/, R/./, Kumar/, S/. P/. R/./, /& Garcia/-Luna/-Aceves/, J/. J/. /(/1/9/8/9/)/. A loop/-free extended bellman/-ford routing protocol without bouncing e/ect/. ACM Computer - VA/. ACM Press/. Choi/, S/./, /& Yeung/, D/./-Y/. /(/1/9/9/6/)/. Predictive Q/-routing/: A memory/-based reinforcement learning approach to adaptive tra/c control/. In Advances in Neural Information - Communication Review /(SIGCOMM /'/8/9/)/, /1/8/(/4/)/, /2/2/4/{/2/3/6/. Cherkassky/, B/. V/./, Goldberg/, A/. V/./, /& Radzik/, T/. /(/1/9/9/4/)/. Shortest paths algorithms/: Theory and experimental evaluation/. In Sleator/, D/. D/. /(Ed/./)/, Proceedings of the /5th Annual ACM/-SIAM Symposium on Discrete Algorithms /(SODA /9/4/)/, pp/. /5/1/6/{/5/2/5 Arlington/, - Processing Systems /8 /(NIPS/8/)/, pp/. /9/4/5/{/9/5/1/. MIT Press/. Colorni/, A/./, Dorigo/, M/./, /& Maniezzo/, V/. /(/1/9/9/1/)/. Distributed optimization by ant colonies/. In Proceedings of the European Conference on Arti/cial Life /(ECAL /9/1/)/, pp/. /1/3/4/{/1/4/2/. - Society/, /4/8/, /2/9/5/{/3/0/5/. Crawley/, E/./, Nair/, R/./, Rajagopalan/, B/./, /& Sandick/, H/. /(/1/9/9/6/)/. A framework for QoS/-based routing in the internet/. Internet Draft /(expired in September/, /1/9/9/7/) draft/-ietf/-qosr/- - Elsevier/. Costa/, D/./, /& Hertz/, A/. /(/1/9/9/7/)/. Ants can colour graphs/. Journal of the Operational Research - framework/-/0/0/, Internet Engineering Task Force /(IEFT/)/. Danzig/, P/. B/./, Liu/, Z/./, /& Yan/, L/. /(/1/9/9/4/)/. An evaluation of TCP Vegas by live emulation/. Tech/. rep/. UCS/-CS/-/9/4/-/5/8/8/, Computer Science Department/, University of Southern - IASTED//ACTA Press/. Dijkstra/, E/. W/. /(/1/9/5/9/)/. A note on two problems in connection with graphs/. Numer/. Math/./, - California/, Los Angeles/. Di Caro/, G/./, /& Dorigo/, M/. /(/1/9/9/8/)/. Two ant colony algorithms for best/-e/ort routing in datagram networks/. In Proceedings of the Tenth IASTED International Confer/ence on Parallel and Distributed Computing and Systems /(PDCS/'/9/8/)/, pp/. /5/4/1/{/5/4/6/. - /1/, /2/6/9/{/2/7/1/. Dorigo/, M/. /(/1/9/9/2/)/. Optimization/, Learning and Natural Algorithms /(in Italian/)/. Ph/.D/. thesis/, Dipartimento di Elettronica e Informazione/, Politecnico di Milano/, IT/. /3/6/2 AntNet/: Distributed Stigmergetic Control for Communications Networks - Dorigo/, M/./, Di Caro/, G/./, /& Gambardella/, L/. M/. /(/1/9/9/8/)/. Ant algorithms for distributed discrete optimization/. Tech/. rep/. /9/8/-/1/0/, IRIDIA/, Universit/ e Libre de Bruxelles/. Sub/- - Computation/, /1/(/1/)/, /5/3/{/6/6/. Dorigo/, M/./, Maniezzo/, V/./, /& Colorni/, A/. /(/1/9/9/1/)/. Positive feedback as a search strategy/. - mitted to Arti/cial Life/. Dorigo/, M/./, /& Gambardella/, L/. M/. /(/1/9/9/7/)/. Ant colony system/: A cooperative learning approach to the traveling salesman problem/. IEEE Transactions on Evolutionary - Tech/. rep/. /9/1/-/0/1/6/, Dipartimento di Elettronica/, Politecnico di Milano/, IT/. Dorigo/, M/./, Maniezzo/, V/./, /& Colorni/, A/. /(/1/9/9/6/)/. The ant system/: Optimization by a colony of cooperating agents/. IEEE Transactions on Systems/, Man/, and Cybernetics/{Part - Ford/, L/./, /& Fulkerson/, D/. /(/1/9/6/2/)/. Flows in Networks/. Prentice/-Hall/. Goss/, S/./, Aron/, S/./, Deneubourg/, J/. L/./, /& Pasteels/, J/. M/. /(/1/9/8/9/)/. Self/-organized shortcuts in - B/, /2/6 /(/1/)/, /2/9/{/4/1/. - the Argentine ant/. Naturwissenschaften/, /7/6/, /5/7/9/{/5/8/1/. Grass/ e/, P/. P/. /(/1/9/5/9/)/. La reconstruction du nid et les coordinations interindividuelles chez bellicositermes natalensis et cubitermes sp/. La th/ eorie de la stigmergie/: essai d/'interpr/ etation du comportement des termites constructeurs/. Insectes Sociaux/, /6/, - Computer Society Press/. Jaakkola/, T/./, Singh/, S/. P/./, /& Jordan/, M/. I/. /(/1/9/9/5/)/. Reinforcement learning algorithm for partially observable Markov decision problems/. In Advances in Neural Information - /4/1/{/8/1/. Gray/, R/./, Kotz/, D/./, Nog/, S/./, Rus/, D/./, /& Cybenko/, G/. /(/1/9/9/7/)/. Mobile agents/: The next generation in distributed computing/. In Proceedings of the Second Aizu International Symposium on Parallel Algorithms//Architectures Synthesis /(pAs /'/9/7/)/, pp/. /8/{/2/4/. IEEE - Processing Systems /7/, pp/. /3/4/5/{/3/5/2/. MIT Press/. Kaelbling/, L/. P/./, Littman/, M/. L/./, /& Moore/, A/. W/. /(/1/9/9/6/)/. Reinforcement learning/: A survey/. - Computer Communication Review/, /1/9/(/4/)/, /4/5/{/5/6/. Malkin/, G/. S/./, /& Steenstrup/, M/. E/. /(/1/9/9/5/)/. Distance/-vector routing/. In Steenstrup/, M/. E/. - Journal of Arti/cial Intelligence Research/, /4/, /2/3/7/{/2/8/5/. Khanna/, A/./, /& Zinky/, J/. /(/1/9/8/9/)/. The revised ARPANET routing metric/. ACM SIGCOMM - /(Ed/./)/, Routing in Communications Networks/, chap/. /3/, pp/. /8/3/{/9/8/. Prentice/-Hall/. McCallum/, A/. K/. /(/1/9/9/5/)/. Reinforcement learning with selective perception and hidden state/. Ph/.D/. thesis/, Department of Computer Science/, University of Rochester/, Rochester ARPANET/. IEEE Transactions on Communications/, /2/8/, /7/1/1/{/7/1/9/. - /(NY/)/. McQuillan/, J/. M/./, Richer/, I/./, /& Rosen/, E/. C/. /(/1/9/8/0/)/. The new routing algorithm for the /3/6/3 Di Caro /& Dorigo - Merlin/, P/./, /& Segall/, A/. /(/1/9/7/9/)/. A failsafe distributed routing protocol/. IEEE Transactions - Moy/, J/. T/. /(/1/9/9/8/)/. OSPF Anatomy of an Internet Routing Protocol/. Addison/-Wesley/. Narendra/, K/. S/./, /& Thathachar/, M/. A/. /(/1/9/8/0/)/. On the behavior of a learning automa/ton in a changing environment with application to telephone tra/c routing/. IEEE - on Communications/, COM/-/2/7/(/9/)/, /1/2/8/0/{/1/2/8/7/. - Transactions on Systems/, Man/, and Cybernetics/, SMC/-/1/0/(/5/)/, /2/6/2/{/2/6/9/. Nedzelnitsky/, O/. V/./, /& Narendra/, K/. S/. /(/1/9/8/7/)/. Nonstationary models of learning automata routing in data communication networks/. IEEE Transactions on Systems/, Man/, and - McGraw/-Hill/. Peterson/, L/. L/./, /& Davie/, B/. /(/1/9/9/6/)/. Computer Networks/: A System Approach/. Morgan - Cybernetics/, SMC/-/1/7/, /1/0/0/4/{/1/0/1/5/. Papoulis/, A/. /(/1/9/9/1/)/. Probability/, Random Variables and Stochastic Process /(Third edition/)/. - Kaufmann/. - Draft/, Internet Engineering Task Force /(IEFT/)/. Schoonderwoerd/, R/./, Holland/, O/./, /& Bruten/, J/. /(/1/9/9/7/)/. Ant/-like agents for load balancing in telecommunications networks/. In Proceedings of the First International Conference - Rubistein/, R/. Y/. /(/1/9/8/1/)/. Simulation and the Monte Carlo Method/. John Wiley /& Sons/. Sandick/, H/./, /& Crawley/, E/. /(/1/9/9/7/)/. QoS routing /(qosr/) working group report/. Internet - on Autonomous Agents/, pp/. /2/0/9/{/2/1/6/. ACM Press/. Schoonderwoerd/, R/./, Holland/, O/./, Bruten/, J/./, /& Rothkrantz/, L/. /(/1/9/9/6/)/. Ant/-based load - ACM Computer Communication Review/, /2/2/(/5/)/, /3/9/{/5/2/. Shankar/, A/. U/./, Alaettino/ glu/, C/./, Dussa/-Zieger/, K/./, /& Matta/, I/. /(/1/9/9/2b/)/. Transient and steady/-state performance of routing protocols/: Distance/-vector versus link/-state/. Tech/. rep/. UMIACS/-TR/-/9/2/-/8/7/, CS/-TR/-/2/9/4/0/, Institute for Advanced Computer Studies and - balancing in telecommunications networks/. Adaptive Behavior/, /5/(/2/)/, /1/6/9/{/2/0/7/. Shankar/, A/. U/./, Alaettino/ glu/, C/./, Dussa/-Zieger/, K/./, /& Matta/, I/. /(/1/9/9/2a/)/. Performance comparison of routing protocols under dynamic and static /le transfer connections/. - Department of Computer Science/, University of Maryland/, College Park /(MD/)/. Singh/, S/. P/./, /& Sutton/, R/. S/. /(/1/9/9/6/)/. Reinforcement learning with replacing eligibility traces/. - Machine Learning Conference/, pp/. /2/8/4/{/2/9/2/. New Brunswick/, NJ/: Morgan Kaufmann/. - Machine Learning/, /2/2/, /1/2/3/{/1/5/8/. Singh/, S/. P/./, Jaakkola/, T/./, /& Jordan/, M/. I/. /(/1/9/9/4/)/. Learning without state estimation in partially observable Markovian decision processes/. In Proceedings of the Eleventh - Steenstrup/, M/. E/. /(Ed/./)/. /(/1/9/9/5/)/. Routing in Communications Networks/. Prentice/-Hall/. Stone/, P/./, /& Veloso/, M/. M/. /(/1/9/9/6/)/. Multiagent systems/: A survey from a machine learning Tech/. rep/. CMU/-CS/-/9/7/-/1/9/3/, Carnegie Mellon University/, Pittsburgh/, PA/. /3/6/4 persective/. AntNet/: Distributed Stigmergetic Control for Communications Networks - Streltsov/, S/./, /& Vakili/, P/. /(/1/9/9/6/)/. Variance reduction algorithms for parallel replicated simulation of uniformized Markov chains/. Discrete Event Dynamic Systems/: Theory - Joint Conference on Arti/cial Intelligence/, pp/. /8/3/2/{/8/3/8/. Morgan Kaufmann/. - and Applications/, /6/, /1/5/9/{/1/8/0/. Subramanian/, D/./, Druschel/, P/./, /& Chen/, J/. /(/1/9/9/7/)/. Ants and reinforcement learning/: A case study in routing in dynamic networks/. In Proceedings of IJCAI/-/9/7/, International - The ATM Forum /(/1/9/9/6/)/. Private Network/-Network Interface Speci/cation/: Version /1/./0/. Walrand/, J/./, /& Varaiya/, P/. /(/1/9/9/6/)/. High/-performance Communication Networks/. Morgan - network environment/. ACM Computer Communication Review/, /2/2/(/2/)/. Yang/, Q/. /(/1/9/9/7/)/. A Simulation Laboratory for Evaluation of Dynamic Tra/c Manage/ment Systems/. Ph/.D/. thesis/, Department of Civil and Environmental Engineering/, - Kaufmann/. Wang/, Z/./, /& Crowcroft/, J/. /(/1/9/9/2/)/. Analysis of shortest/-path routing algorithms in a dynamic Massachusetts Institute of Technology /(MIT/)/. /3/6/5