Networks

Home Next

 

Computer Networks

 

"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]

Topologies

 

           LAN (Local Area Networks): privately owned networks stored within a single area.

MAN (Metropolitan Area Networks): like LAN, can be used to connect corp. offices or a small city.

WAN (Wide Area Networks):  Large Geographical Area, Country or continent.

 

There are various topologies available for LAN’s, the most common are shown below.

 
 

 

 

 

 

              

Broadcast Networks (BUS and RING). [Tanenbaum, pg 9]

Back to Top

 

Network Problems

 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.

Improper Load Balancing.
Congestion.
Server Failures.
Network Scaling.
Alternative Routings.

Routing

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. 

  In the OSI (Open Systems Interconnect) model, routing is performed by a special layer called the Network layer.  Its main goal is to route packages from a source machine to a destination machine.  The routing algorithm is responsible for transmitting datagrams[1] and organizing traffic control.  We will focus our analysis on packet switched networks which are simpler to simulate and most accessible at this time. 

  Routing algorithms can be divided into two main classes:

·        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.

 

Back to Top

 

Network Routing Algorithms

 

Static Routing Algorithms

Shortest Path First (SPF)

  This type of routing algorithm is based on a pair of source destination.  Its main goal is to find, as its name implies, the “shortest” path between two nodes.  A very efficient way of measuring the length of a path is by counting the number of hops from source to destination.  Another and very important metric is to calculate the geographic distance in kilometers.  These two are not the only metrics available.  For example you could label each arc in the path with the mean queuing and transmission delay for a standard test package.  Then you can calculate these values for the transmitted data and compare them with scheduled test runs

 

Flooding

 

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 (RIP)

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:

 

  1. Discover neighbors and learn network addresses:(Hello Packet)
  2. Measure delay and costs to neighbors. (ECHO)
  3. Construct a packet with the information obtained. (start header, seq num, age)
  4. Send packet to all the other routers.(via flooding)
  5. Compute the shortest path route (SPF)

 

Advantages of Link State Routing

 

The advantages of Link State routing over Dynamic Vector Routing are the following: 

Faster Conversion times:  one of the mayor problems of distance vector routing is that the conversion time of the algorithm is quite large.  Bad news in these type of algorithms spread pretty quickly but good news take a long time to reach all the nodes in the network.  On the other hand, in Link State Routing, due to the state of the algorithm, the convergence times are pretty quick.

Line Bandwidth: in difference with DV routing, Link State routing takes into account the bandwidth of the line before assigning routes.

 


[1]A datagram is an independent packet of a connectionless system organization.

 
Back to Top

Copyright 2001: Ivan A. Escobar Broitman
For problems or questions regarding this web contact ivan@escobarb.fsnet.co.uk
Last updated: August 20, 2001.