programs run by the users. The development of this open standard has encouraged the adoption by different
developers of standardized compatible systems interfaces. The figure shows the seven layers of OSI/RM. Each
layer is self-contained, so that it can be modified without unduly affecting other layers. The Transport Layer
provides error detection and correction. Routing and flow control are performed in the Network Layer. The
Physical Layer represents the actual hardware communication link interconnections. The Applications Layer
represents programs run by users.
Routing. Since a distributed network has multiple nodes and services many messages, and each node is a shared
resource, many decisions must be made. There may be multiple paths from the source to the destination. Therefore,
message routing is an important topic. The main performance measures affected by the routing scheme are
throughput (quantity of service) and average packet delay (quality of service). Routing schemes should also avoid
both deadlock and livelock (see below).
Routing methods can be fixed (i.e. pre-planned), adaptive, centralized, distributed, broadcast, etc. Perhaps the
simplest routing scheme is the token ring [Smythe 1999]. Here, a simple topology and a straightforward fixed
protocol result in very good reliability and precomputable QoS. A token passes continuously around a ring
topology. When a node desires to transmit, it captures the token and attaches the message. As the token passes, the
destination reads the header, and captures the message. In some schemes, it attaches a ‘message received’ signal to
the token, which is then received by the original source node. Then, the token is released and can accept further
messages. The token ring is a completely decentralized scheme that effectively uses TDMA. Though this scheme is
very reliable, one can see that it results in a waste of network capacity. The token must pass once around the ring
for each message. Therefore, there are various modifications of this scheme, including using several tokens, etc.
Fixed routing schemes often use Routing Tables that dictate the next node to be routed to, given the current
message location and the destination node. Routing tables can be very large for large networks, and cannot take into
account real-time effects such as failed links, nodes with backed up queues, or congested links.
Adaptive routing schemes depend on the current network status and can take into account various performance
measures, including cost of transmission over a given link, congestion of a given link, reliability of a path, and time
of transmission. They can also account for link or node failures.
Routing algorithms can be based on various network analysis and graph theoretic concepts in Computer Science
(e.g. A-star tree search), or in Operations Research [Bronson 1997] including shortest-route, maximal flow, and
minimum-span problems. Routing is closely associated with dynamic programming and the optimal control
problem in feedback control theory [Lewis and Syrmos 1995]. Shortest Path routing schemes find the shortest path
from a given node to the destination node. If the cost, instead of the link length, is associated with each link, these
algorithms can also compute minimum cost routes. These algorithms can be centralized (find the shortest path from
a given node to all other nodes) or decentralized (find the shortest path from all nodes to a given node). There are
certain well-defined algorithms for shortest path routing, including the efficient Dijkstra algorithm [Kumar 2001],
which has polynomial complexity. The Bellman-Ford algorithm finds the path with the least number of hops
[Kumar 2001]. Routing schemes based on competitive game theoretic notions have also been developed [Altman et
al. 2002].
Deadlock and Livelock. Large-scale communication networks contain cycles (circular paths) of nodes. Moreover,
each node is a shared resource that can handle multiple messages flowing along different paths. Therefore,
communication nets are susceptible to deadlock, wherein all nodes in a specific cycle have full buffers and are
waiting for each other. Then, no node can transmit because no node can get free buffer space, so all transmission in
that cycle comes to a halt. Livelock, on the other hand, is the condition wherein a message is continually transmitted
around the network and never reaches its destination. Livelock is a deficiency of some routing schemes that route
the message to alternate links when the desired links are congested, without taking into account that the message
should be routed closer to its final destination. Many routing schemes are available for routing with deadlock and
livelock avoidance [e.g. Duato 1996].
Flow Control. In queuing networks, each node has an associated queue or buffer that can stack messages. In such
networks, flow control and resource assignment are important. The objectives of flow control are to protect the
network from problems related to overload and speed mismatches, and to maintain QoS, efficiency, fairness, and
freedom from deadlock. If a given node A has high priority, its messages might be preferentially routed in every
case, so that competing nodes are choked off as the traffic of A increases. Fair routing schemes avoid this. There
are several techniques for flow control: In buffer management, certain portions of the buffer space are assigned for
certain purposes. In choke packet schemes, any node sensing congestion sends choke packets to other nodes telling
them to reduce their transmissions. Isarithmic schemes have a fixed number of ‘permits’ for the network. A
message can be sent only if a permit is available. In window or kanban schemes, the receiver grants ‘credits’ to the
sender only if it has free buffer space. Upon receiving a credit, the sender can transmit a message. In Transmission
4