Research Paper on Routing Algorithms

Before a message can be passed to its target, it has to be formed; the message is enveloped inside a packet, which is formed by putting the address information of the target as a header of the actual message, so that the destination of the message and its size etc. can be read before the actual message is received. The actual message is then encoded in order to lessen transmittal time. This finalized packet is what gets "pushed out of the door". Now our message is ready to be routed to its destination node. Routing is the act of moving a message from a source node or other network entity to its destination. A routing technique is a way of handling the message as it passes through individual nodes. A routing algorithm is a rule set for determining where to send a message next. There are several routing techniques used by entities accessing the Internet lets explore some of these routing techniques and algorithms. Dijkstra's least cost algorithm finds all possible paths between two locations. After identifying all possible paths, it also identifies the least cost path. The algorithm can be applied to determine the least cost path between any pair of nodes; this is the basic principal of routing messages. Lets examine some interesting and notable aspects of routing.

Order a custom research paper on Routing Algorithms now! 

E-cube routing A message routing algorithm used on binary hypercubes. Hypercube is a topology used by early American multiprocessors where each node is the vertex of a d-Dimensional cube. If <|Sn-1...S0|> and <|Dn-1...D0|> are the binary co-ordinates of the source and destination of the message, and <|Xn-1...X0>| their difference, then the e-cube algorithm routes the message along links parallel to the axes corresponding to 1's in <|Xn-1...X0|>, in order from highest to lowest. In a hypercube, e-cube routing (or dimension-order routing) routes a message from source to destination by traversing the differing dimensions in right-to-left order (or left-to-right: the specific order is irrelevant, as long as all routers use the same ordering). All edges of the hypercube are viewed as being 2 links, one in each direction.

Interval routing - A routing algorithm that assigns an integer identifier to each possible destination and then labels the outgoing links of each node with a single contiguous interval or window so that a message can be routed simply by sending it out the link in whose interval its destination identifier falls. Linear Interval Routing is a space-efficient routing method for point-to-point communication networks. It is a restricted variant of Interval Routing where the routing range associated with every link is represented by an interval with no wrap-around. Interval routing is a space-efficient routing scheme; this scheme is attractive because of its simplicity. Interval routing is one among several compact routing techniques for distributed networks. An interval routing scheme substantially reduces the space requirements of routers in the network provided the nodes and the edges of the network together admit an interval labeling scheme: the scheme essentially determines the precise route taken by a message from a source to a destination in the network.

Metropolis routing - A routing algorithm for meshes, in which an ordering is imposed on axes, and messages are sent as far along the most significant axis as they need to go, then as far along the next most significant axis, and so on until they reach their destination. A mesh is that topology in which nodes form a regular acyclic or open structured d-dimensional grid, and each edge is parallel to a grid axis and joins two nodes that are adjacent along that axis. The architecture of many multicomputers is a two or three-dimensional mesh; each node represents a point on the mesh, and the edges define the neighbors of a node.

Virtual cut-through routing - A technique for routing messages in which the head and tail of the message both proceed as rapidly as possible. If the head is blocked because a link it wants to cross is being used by some other message, the tail continues to advance, and the message's contents are put into buffers on intermediate nodes for reassembly later at the destination entity. Virtual cut-through routing reserves no resources in advance and breaks up the packet into several smaller chunks; the pieces of the packet are then transmitted one by one. The virtual cut-through routing scheme has the distinct advantage of not wasting allocated resources. This scheme does however require the use of large buffers to hold the entire packet. This technique addresses the flow control needs of routing.

Wormhole routing - A technique for routing messages in which the head of the message establishes a path, which is reserved for the message until the tail has passed through it. Unlike virtual cut-through routing, the tail proceeds at a rate dictated by the progress of the head, which reduces the demand for intermediate buffering but also slows overall data transmission rate. In wormhole routing, packets are divided into smaller parts of equal size called flits, which are then transmitted one by one, instead of transmitting the packet as a whole. All the flits of the same packet follow the same path and cannot overtake each other. Nodes on the packets path can contain only one flit of that packet and will always try to transmit it to the next node. Because the movement of the packets throught the data path resembles the movement of a worm, the packets themselves are sometimes called worms. It is also noteworthy in wormhole routing it is impossible for flits of another packet to cross the path of the current packet. This means, that even if a node is empty, flits of the other packet cannot use this node, unless the last flit of the current packet has passed it. This characteristic of wormhole routing introduces a problem called deadlock. Deadlock is the situation in which each possible activity is blocked, waiting on some other blocked activity.

Routing data is the most essential element in bringing data our home from the information superhighway. The interconnection of computers has spawned these algorithms, schemes and techniques to forward data from node to node. Without these essential ingredients the Internet would not exist.

__________________________________________________________________________

This is a free research paper on Routing Algorithms topic. Keep in mind that all free research papers and research proposals are taken from open sources – they are plagiarized and cannot be used as your own research project. If you need a qualitative custom research paper on Routing Algorithms for college, university, Master's or PhD degree – you are welcome to contact professional research paper writing company to have your paper written online by academic research writers.

__________________________________________________________________________

__________________________________________________________________________
________________Enjoy our custom research paper writing service!__________________