Routing
Routing
Computer networks allow messages to be exchanged between computers in different parts of the world. These messages may contain e-mails, requests for web pages, or the contents of a web page. When traveling from the source computer to the destination computer, messages typically pass through a number of other computers on the network. Routing is the function of choosing which computers a message should pass through on its way from source to destination. Some computers in the network, called routers, exist only to route messages onward in the network. Routing must be performed in large networks such as the Internet as well as in smaller networks such as within a university.
When a message is received from the network, the computer that receives the message—unless it is the intended recipient—must perform a routing action. Routing the message means choosing which of the connected computers should receive the forwarded message.
Each message includes the address of its intended destination, and this address is used to choose the route of the message. To route a message, the computer does not need to know anything about where the destination computer is. It merely needs to know in which direction to send the message. This is similar to the way addresses are used on normal letters. If U.S. Postal Service workers receive a letter for someone in France, they will probably not know anything about the exact location of the person that is to receive the letter. Despite this, the U.S. Postal Service can still route the letter by simply forwarding the letter to France. Then the French postal network takes care of routing the letter to its final destination.
In a global network such as the Internet, there are many possible routes for a message to take between a source and destination computer. The overwhelming number of possibilities makes routing messages very complicated. Also, the structure of the network is not fixed; computers or connections may be temporarily unavailable, in which case a route must be chosen to bypass the unavailable part of the network.
It is best to route the messages as directly as possible. One option is to choose the route so that the message passes through the minimum number of computers on its way from its source to destination. It is also possible to take into account other factors, such as the speed of the connections between computers on the route. By choosing a route with faster connections, the message will reach its destination faster, even though it may pass through more computers on its way. Another factor to consider when routing is the current state of the network. If parts of the network become overloaded, then messages routed through these parts of the network will suffer delays. Routing messages around the overloaded parts of the network will speed up the delivery of the messages and avoid adding to an already overloaded network.
Static Routing
The simplest approach to routing is static routing. In this case each computer on the network has a fixed routing table. When a message is received, the computer checks the address of the message against the routing table and then forwards the message to whichever computer is indicated by the routing table. The routing table may include alternative entries to deal with the case where part of the network is currently unavailable.
Static routing requires very little processing power, which is considered an advantage. However, this simple solution has the disadvantage that it cannot adapt to current situations in the network. For example, parts of the network may become overloaded if too many messages are being transmitted. With static routing, no change will be made to the routing algorithm to take into account the overloading. It is possible to adapt to such an overload situation and route messages away from the overloaded part of the network with what is known as dynamic routing.
Dynamic Routing
In the simplest form of dynamic routing, each computer can adapt its routing based on its current situation. Thus, none of the computers knows about the overall state of the network; each computer adapts its routing based solely on its own situation. Messages are put in a queue before being transmitted. If the queue for a connection grows too big, this indicates that the connection is becoming overloaded. The computer can adapt its routing to avoid, where possible, the connections with large queues. This approach allows the computer to balance the load on its connections but the computer has no knowledge of the state of the rest of the network. Therefore, although the computer can prevent its own outgoing connections from becoming overloaded, it may still be sending messages to overloaded parts of the network.
A second form of dynamic routing is where computers share information about their current state with each other. This gives each computer a better understanding of the overall situation in the network so it can route messages away from overloaded parts of the network. One approach is for each computer to send information about the state of its connections to all directly connected computers. Each computer combines the incoming status information with its own current state to generate status messages, which are then sent to connected computers. This allows each computer to build up a picture of which parts of the network are overloaded, allowing it to route messages away from the overloaded parts of the network. With this solution, it is critical to find a balance between sending too many status messages, which themselves may cause overloading, and too few status messages, in which case the network may adapt too slowly to an overload situation.
The choice of routing strategy will depend on the network. Static routing may be suitable for small local networks, but for a large global network, such as the Internet, dynamic routing is necessary to avoid overloading parts of the network.
see also Asynchronous Transfer Mode (ATM); Bandwidth; Network Design; Networks.
Declan P. Kelly
Bibliography
Sportack, Mark A. IP Routing Fundamentals. New York: Macmillan, 1998.
Tannenbaum, Andrew S. Computer Networks. Upper Saddle River, NJ: Prentice Hall, 1996.