"Many networks exist in the world, often with different hardware and software. People connected to one network often want to communicate with people attached to a different one. This desire requires connecting together different, and frequently incompatible networks, sometimes by using machines called gateways to make the connection and provide the necessary translation, both in terms of hardware and software. A collection of interconnected networks is called an inter - network or just Internet.” [Tanenbaum, pg 16]
There are various topologies available for LAN’s, the most common are shown below.
We must consider that even though a network can be structured in such a way as to maintain itself and evade problems, these will arise with the overuse of the network or with the expansion of itself. The mayor problems a network can encounter are listed below; the scope of this project is to propose an alternative to try to solve one of the many problems that can arise in a network, in this case to optimize routing with swarm intelligence. Swarm intelligence can also be applied to some other areas to optimize solutions but these will just be mentioned, since they are out of the scope of the project.
As we know, packet switched networks depend heavily on routers. Routers can be either hardware or software, although most hardware routers have a defined routing algorithm. A routing algorithm must direct the traffic in the network. Its main goal is to balance the network loads to improve performance. A good and efficient routing algorithm will balance shortest routes against congestions. The routing algorithm should be able to deal with unexpected changes in the topology of the network without aborting too many hosts or rebooting the entire system. To measure performance we usually take into account both throughput and average packet delay. Throughput is the measure of the quantity of service that the network can offer at a certain time. Average packet delay defines the quality of service produces at the same time. Many networks try to minimize the number of hops a packet must take from its source to the destination, since by doing it, you can improve the delay and reduce the bandwidth consumed, thus improving the total throughput of the system.
· Non - adaptive algorithms: these algorithms base their decisions on predefined values stored in tables. Routing decisions are made off line and computed in advance and do not take considerations of traffic and networks problems (unavailable servers, congestions, etc). Sometimes non - adaptive algorithms are called "static algorithms" since they cannot be changed "online". A mayor flaw in these type of algorithms is that they view the network as either a static object or a perfect object. Networks can have serious problems, servers can collapse, congestion might occur and these routers do not take into consideration none of this events. They just consult their predefined paths and route accordingly.
· Adaptive algorithms: these algorithms base their decisions on both table values as well as dynamic adaptations due to network performance. Adaptive algorithms get their information from a wide variety of sources (locally, adjacent routers or all routers). These algorithms can be implemented in various ways and can differ not only on source gatherings but also in the metrics they will use to achieve optimal performance. A drawback of these algorithms is that they sometimes can lead to oscillations in the selected paths (they can cause circular paths or can lead to inconsistent situations). Adaptive Routers can be broken down into two categories:
1. Minimal: allow packets to choose minimal cost paths
2. Non-Minimal: allow packets to choose from all available paths.
Network Routing Algorithms
Shortest Path First (SPF )
The second static algorithm that we will look at is flooding. Flooding uses an interesting technique, although it wastes large amounts of bandwidth. In this routing method, every incoming packet is sent out on every outgoing channel except on the one it came from. This obviously generates a large amount of duplicate packets. In order to minimize these effects, a “hop” counter can be introduced into the header of the packet. At each “hop” the counter is decremented. Once the counter reaches cero, the packet is discarded.
Dynamic Routing Algorithms
Distance Vector Routing
The basic principle behind distance vector routing is that each router has a table (vector table), which contains the best-known distances to each destination, including the route to the destination (the line to take) from the router. It is the job of the router to maintain as actualized as possible this routing table. How can these tables be updated? In difference with static routing algorithms, dynamic ones “talk” with their neighbors. The routers probe the network constantly and interchange information.
Link State Routing
Another widely used routing technique is the link state routing. In this routing algorithm, the routers talk with the neighbors in two different ways. They send a special packet called the "Hello" packet which identifies the neighbors to the router. Then an ICMP/ECHO packet is sent to measure time delay. Afterwards a special packet is constructed by the router and sent to all the neighbors. Finally SPF is applied to route the data.
Below is a short summary of the steps:
Advantages of Link State Routing
The advantages of Link State
routing over Dynamic Vector Routing are the following:
A datagram is an independent packet of a connectionless system organization.
Copyright 2001: Ivan A. Escobar Broitman