Shortest Path Routing - a type of routing algorithm

- The usage of the re-configurable logic has been increasing day by day both in scope as well as number. 

- Re-configurable computing combines both the hardware speed and the flexibility of the software. 

- This is the result of the combination of the highspeed computing and re-configurability.

- Tough requirements are posed up on the routing in a network by the increased QoS i.e., the quality of service. 

- This increase in the complexity of the computational capabilities bears an exponential relation with the increased QoS. 

- However, additional computational resources are needed for achieving a network performance level that is acceptable. 

- Re-configurable computing offers a promising solution to the issues of the computations in the routing process.

There are 3 major aspects of the shortest path routing as mentioned below:

Ø Path selection: This involves the various algorithms such as the Dijkstra’s and bellman – ford algorithms and shortest path and minimum – hop routing.

Ø Topology change: Changes in the topology are detected using the beacons.

Ø  Routing protocols: This involves routing protocols such as the link state routing protocols and distance vector protocols.

- Forwarding and routing are two different things. 

- In forwarding, the data packet is directed towards an outgoing link and an individual router is used that also maintains a forwarding table.

- Routing computes the paths that have to be followed by the packets. 

- Routers exchange the path information between themselves and the forwarding table is created by each and every router in the chain.

Routing is important for the following three main reasons:

Ø  End-to-end performance: The user performance is affected by the path quality, throughput, packet loss and delay in propagation.

Ø  Use of the network resources: The traffic has to be balanced between the several links and routers. The traffic is directed towards the links that are lightly loaded for avoiding the congestion.

Ø  Transient disruptions during changes: These disruptions include the load balancing problems, maintenance, failures etc. the packet loss as well as the delay has to be limited while the changes take effect.

- Shortest path routing is based up on a path selection model that gives more preference to the destination. 

- This type of routing is insensitive to load as in it involves the static link weights.

- Here, either the sum of the link weights or the minimum hope is considered. 

- In a shortest path problem, the link costs are given for a network topology. 

- For example, C(x,y) denotes the cost of the node x to node y. 

- If the two nodes x and y are not adjacent to each other the cost is taken to be infinity. 

- The least cost paths linking all the nodes are computed from a node taken as the source. 

- Dijkstra’s shortest path algorithm is one of the algorithms used in the shortest path routing. 

- A central role is played by the problems involving finding the shortest paths in the designing and the analyzation of the networks.

- A majority of the routing problems can be taken as the shortest path problems and solved if each link in the network has appropriate cost assigned to it. 

- This cost even reflects the bandwidth as well as the bit error ratio if required. - A number of algorithms are available for computing the shortest path.

- But these algorithms are applicable only if a single non – negative additive metric characterizes every edge in the network.

- Out of these algorithms, the Dijkstra’s algorithm is the most famous one. 

- This algorithm find its use in the OSPF (open shortest path first) routing procedure of the internet. 

- In this algorithm the number of operations carried out are proportional to the number of nodes in the network and the iteration is carried for n-1 times. 

Bus Network Topology

A bus network is an arrangement in a local area network (LAN) in which each node (workstation or other device) is connected to a main cable or link called the bus. Bus networks are the simplest way to connect multiple clients, but may have problems when two clients want to transmit at the same time on the same bus. A true bus network is passive – the computers on the bus simply listen for a signal; they are not responsible for moving the signal along.
The bus topology makes the addition of new devices straightforward. The term used to describe clients is station or workstation in this type of network. Bus network topology uses a broadcast channel which means that all attached stations can hear every transmission and all stations have equal priority in using the network to transmit data.



Advantages :
* Easy to implement and extend.
* Well-suited for temporary or small networks not requiring high speeds (quick setup).
* Cheaper than other topologies.
* Cost effective; only a single cable is used.
* Easy identification of cable faults.
* Reduced weight due to fewer wires.

Disadvantages :
* Limited cable length and number of stations.
* If there is a problem with the cable, the entire network goes down.
* Maintenance costs may be higher in the long run.
* Performance degrades as additional computers are added or on heavy traffic.
* Proper termination is required.
* Significant Capacitive Load.
* It works best with limited number of nodes.
* It is slower than the other topologies.

In a ring network, every device has exactly two neighbors for communication purposes. All messages travel through a ring in the same direction (effectively either "clockwise" or "counterclockwise"). A failure in any cable or device breaks the loop and can take down the entire network. To implement a ring network we use the Token Ring technology. A Token is passed from one computer to another which enables each computer to have equal access to the network.
Because a ring topology provides only one pathway between any two nodes, ring networks may be disrupted by the failure of a single link. A node failure or cable break might isolate every node attached to the ring. Each packet is sent around the ring until it reaches its final destination. Today, the ring topology is seldom used.



Advantages of Ring Network :
* Very orderly network where every device has access to the token and the opportunity to transmit.
* Performs better than a star topology under heavy network load.
* Can create much larger network using Token Ring.
* Does not require network server to manage the connectivity between the computers.

Disadvantages of Ring Network :
* One malfunctioning workstation can create problems for the entire network.
* Moves, adds and changes of devices can affect the network.
* Much slower than an Ethernet network under normal load.

Star Network Topology

Star Topology is the most common type of network topology that is used in homes and offices. In the Star Topology there is a central connection point called the hub which is a computer hub or sometimes just a switch.
In local area networks where the star topology is used, each machine is connected to a central hub. In contrast to the bus topology, the star topology allows each machine on the network to have a point to point connection to the central hub. All of the traffic which transverses the network passes through the central hub.



Advantages of Star Topology :
- A Star Network Topology is very easy to manage because of its simplicity in functionality.
- The problems can be easily located logically in a Star Topology and therefore is easy to troubleshoot also.
- The Star Topology is very simple in format so it is very easy to expand on the Star Topology.

Disadvantages of Star Topology :
- The Star Topology is fully dependent on the hub and the entire working of the network depends on the hub or the switch.
- If there are many nodes and the cable is long then the network may slow down.

Extended Star Network :
A type of network topology in which a network that is based upon the physical star topology has one or more repeaters between the central node and the peripheral or 'spoke' nodes, the repeaters being used to extend the maximum transmission distance of the point-to-point links between the central node and the peripheral nodes.

Distributed Star Topology :
A type of network topology that is composed of individual networks that are based upon the physical star topology connected together in a linear fashion – i.e., 'daisy-chained' – with no central or top level connection point (e.g., two or more 'stacked' hubs, along with their associated star connected nodes or 'spokes').

Hierarchical or Tree Network Topology

In its simplest form, only hub devices connect directly to the tree bus, and each hub functions as the "root" of a tree of devices. This bus/star hybrid approach supports future expandability of the network much better than a bus (limited in the number of devices due to the broadcast traffic it generates) or a star (limited by the number of hub connection points) alone.
This type of topology suffers from the same centralization flaw as the Star Topology. If the device that is on top of the chain fails, consider the entire network down.Obviously this is impractical and not used a great deal in real applications.Each node in the network having a specific fixed number, of nodes connected to it at the next lower level in the hierarchy, the number, being referred to as the 'branching factor' of the hierarchical tree.

- A network that is based upon the physical hierarchical topology must have at least three levels in the hierarchy of the tree, since a network with a central 'root' node and only one hierarchical level below it would exhibit the physical topology of a star.
- The total number of point-to-point links in a network that is based upon the physical hierarchical topology will be one less than the total number of nodes in the network.
- If the nodes in a network that is based upon the physical hierarchical topology are required to perform any processing upon the data that is transmitted between nodes in the network, the nodes that are at higher levels in the hierarchy will be required to perform more processing operations on behalf of other nodes than the nodes that are lower in the hierarchy. Such a type of network topology is very useful and highly recommended.

Topology in Distributed systems

The sites in the system can be connected physically in a variety of ways. While choosing a topology, following criteria should be kept in mind : Basic cost, Communication cost and Reliability.

Mesh Networks : The value of fully meshed networks is proportional to the exponent of the number of subscribers, assuming that communicating groups of any two endpoints, up to and including all the endpoints.

- Fully Connected Networks
The fully-connected connected network topology, also referred to as a mesh topology, requires that all the terminals be connected to all the other terminals, as it's name implies.
Advantages: A fault in one terminal on the network will not effect the rest, as the data has multiple redundancy paths, depending on the size of the network, that are open to it.When network usage is high, data packets can be transmitted via different cables, thereby reducing network clogging - keeping data transfer rates at an acceptable level.
Disadvantage : A large amount of cabling is required.



- Partially connected Networks
The type of network topology in which some of the nodes of the network are connected to more than one other node in the network with a point-to-point link – this makes it possible to take advantage of some of the redundancy that is provided by a physical fully connected mesh topology without the expense and complexity required for a connection between every node in the network.
In most practical networks that are based upon the physical partially connected mesh topology, all of the data that is transmitted between nodes in the network takes the shortest path (or an approximation of the shortest path) between nodes, except in the case of a failure or break in one of the links, in which case the data takes an alternative path to the destination.

Hybrid networks use a combination of any two or more topologies in such a way that the resulting network does not exhibit one of the standard topologies (e.g., bus, star, ring, etc.).
A standard hybrid network uses something called a hybrid access point, a networking device that both broadcasts a wireless signal and contains wired access ports. The most common hybrid access point is a hybrid router. The typical hybrid router broadcasts a Wi-Fi signal using 802.11 a, b or g and contains four Ethernet ports for connecting wired devices. The hybrid router also has a port for connecting to a cable or DSL modem via Ethernet cable.
There are several different possible network configurations for a hybrid network. The most basic configuration has all the wired devices plugged into the Ethernet ports of the hybrid router. Then the wireless devices communicate with the wired devices via the wireless router.
Computers aren't the only devices that can be linked over a hybrid network. You can now buy both wired and wireless peripheral devices like printers, Web cams and fax machines.

Hybrid network are: star ring network and star bus network
* A Star ring network consists of two or more star topologies connected using a multi-station access unit (MAU) as a centralized hub.
* A Star Bus network consists of two or more star topologies connected using a bus trunk (the bus trunk serves as the network's backbone).

While grid networks have found popularity in high-performance computing applications, some systems have used genetic algorithms to design custom networks that have the fewest possible hops in between different nodes. Some of the resulting layouts are nearly incomprehensible, although they function quite well.

Quick Tech Explanation: Local Area Networks - LANs

Local Area networks, generally called LANs, are privately owned networks within a single building or campus of up to a few kilometers in size. Most local area networks are built with relatively inexpensive hardware such as Ethernet cables, network adapters, and hubs. Wireless LAN and other more advanced LAN hardware options also exist as a part of modern LANs.
The most common type of local area network is an Ethernet LAN. If you look at size of LAN's, the smallest home LAN can have exactly two computers; a large LAN can accommodate many thousands of computers. Many of the larger LANs are divided into logical groups called subnets.

LANs are distinguished from other kinds of networks by three characteristics:
1. Size: LANs have a size limit and cannot expand beyond this size, essentially meaning that it is possible to plan and design for the worst case transmission time.
2. Topology: This is the geometric arrangement of devices on the network. For example, devices can be arranged in a ring or in a straight line. In a bus network, one machine is master and is allowed to transmit. An arbitration mechanism is needed to resolve conflicts when two or more machines want to transmit simultaneously.
In ring network, each bit propgates around on its own, not waiting for the rest of the packet to which it belongs.
3. Protocols: The rules and encoding specifications for sending data. The protocols also determine whether the network uses a peer-to-peer or client/server architecture.
4. Media: Devices can be connected by twisted-pair wire, coaxial cables, or fiber optic cables. Some networks do without connecting media altogether, communicating instead via radio waves.

Most LANs connect workstations and personal computers. Each node (individual computer) in a LAN has its own CPU with which it executes programs, but it also is able to access data and devices anywhere on the LAN. This means that many users can share expensive devices, such as laser printers, as well as data. Users can also use the LAN to communicate with each other, by sending e-mail or engaging in chat sessions.

LANs are capable of transmitting data at very fast rates, much faster than data can be transmitted over a telephone line; but the distances are limited, and there is also a limit on the number of computers that can be attached to a single LAN.