Communications network

Details Communications network Communications network

1999-02-25

2004-03-30

Ton, Dang (Department: 2666)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S408000, C370S256000, C370S389000, C370S392000, C359S199200

Reexamination Certificate

active

06714552

ABSTRACT:

BACKGROUND TO THE INVENTION
1. Field of the Invention
2. Related Art
The present invention relates to a communications network, and in particular to the routing of packets in a network.
There is a need for high speed packet networks for use, for example, in local area networks for interconnecting computer systems, or for use as part of the internal infrastructure of a multiprocessor computer. It has been proposed to implement such networks using ultrafast photonic technology. In implementing the network, the provision of an appropriate routing mechanism for the packets has proved to be a particularly critical design problem. There are a number of potentially conflicting requirements which have to be satisfied by any routing mechanism. In particular, it is desirable that the processing overhead at each node should be kept low: otherwise, the time required to process the packet limits the throughput of the node and hence of the network. However, it is also desirable to ensure that the routing mechanism is as efficient as possible in selecting the shortest paths for packets from a source to a given destination. If the efficiency of the routing mechanism is poor, then congestion in the network rises. This again serves to limit the throughput of the network.
Many different approaches to packet routing have been proposed and studied [1-3]. By selecting a suitable network topology the decision making associated with routing can be greatly simplified. This then meets the first of the requirements identified above, by ensuring a low processing overhead. Some network topologies allow “one-dimensional” routing. For example, in a uni-directional ring the source simply places a packet onto the ring and the packet eventually reaches its destination without requiring any routing decision by intermediate nodes. One-dimensional routing may also be used, for example, on buses or rings with bi-directional links. However, although one dimensional routing offers a number of attractive features, it suffers a serious limitation in that there is poor scaling of the relative routing efficiency and maximum throughput of the network as the number of nodes in the network is increased.
As an alternative to the use of one-dimensional network topologies, multi-dimensional networks may be used. The main advantage of using a multi-dimensional network, such as a two-dimensional torus network, is that there is a multiplicity of paths available between any pair of nodes on the network. It is therefore possible to adopt a routing method that selects the shortest available path, and such a method in general will have a higher relative routing efficiency and a higher value for the maximum throughput. However, existing methods of routing on multi-dimensional networks have their own serious drawbacks. Because the routing methods can select from a multiplicity of paths through the network it is possible for two or more packets to attempt to occupy the same link simultaneously. The method therefore needs to be capable of resolving the contention that arises in this case. This may be done either by using buffering within the network to store one or more of the packets until the link is free, or by deflecting one or more packets away from its optimal path, the technique known as deflection routing [1,7] Buffering can successfully maintain the packets in their correct sequence during their journey across the network. Buffering is however an unattractive solution for high-speed networks, because it introduces variable and unpredictable delay and adds to the control complexity and cost. In the case of photonic networks, there are severe technological limitations to the construction of buffers. Deflection routing does not suffer these technological limitations and is much easier to control, but deflection also causes packets to suffer variable and unpredictable delays. The packets may therefore be delivered to the destination in an incorrect sequence. A further limitation of conventional multi-dimensional networks and routing mechanisms is that it is difficult to achieve broadcasting to the nodes without using higher level transport control layers. The use of higher level transport control layers is undesirable as it introduces substantial processing delays.
The paper by Yener, B. et al., PROCEEDINGS OF THE GLOBAL TELECOMMUNICATIONS CONFERENCE (GLOBECOM), SAN FRANSISCO, NOV. 28 DEC. 2, 1994, vol. 1 of 3, IEEE, pp 169-175, and patent U.S. Pat. No. 5,297,137, discuss the use of multiple spanning trees to enhance the fault tolerance of a switch-based network. The use of two virtual rings is proposed. Each ring is embodied by an edge-disjoint spanning tree of the network and each virtual ring therefore spans every node of the network. It is therefore not possible to. route a packet efficiently simply by choosing one of the virtual rings at the outset. As a packet passes through the network, routing is carried out in a conventional fashion by making a local routing decision at intermediate nodes.
The paper by ZHENSHENG ZHANG et al, published in NETWORKING IN THE NINETIES, Bal Harbour, Apr. 7-11, 1991, vol. 3, 7 April 1991, IEEE, pp 1012-1021 discloses a network which is synchronised so that the transmissions of all the nodes begin in the start of a time slot. However, although the switching of nodes is to this extent pre-scheduled, the switching between different states is not predetermined. That is to say, it is not possible to predict in advance that a certain switch will be in a certain state at a given instant. Rather, whether or not a switch changes from one state to another in a given time slot is determined by a local routing decision made using a hot potato algorithm. The switch state therefore depends on local traffic conditions.
SUMMARY OF THE INVENTION
According to a first aspect of the present invention, there is provided a method of routing a packet in a communications network which comprises a multiplicity of nodes and links, and in which the nodes and links are configured as a multiplicity of directed trails, each directed trail linking some only of the multiplicity of nodes and the directed trails in combination spanning every node of the network, the method comprising:
a) selecting a directed trail T from the multiplicity of directed trails in dependence upon the destination of a packet, the selected trail including the source node and destination node of the packet; and
b) outputting the packet at the source node onto the selected one of the ultiplicity of directed trails.
The present invention provides a fundamentally new approach to packet routing in multi-dimensional communications networks. It potentially offers all the advantage of one-dimensional routing, whilst overcoming the crucial disadvantage of poor scalability of routing efficiency and of the maximum throughput. It also completely avoids the need for contention resolution within the network.
The invention uses a method termed by the inventor “directed trail routing”. This takes advantage of the fact that a network having an appropriate topology, as further described below, can be divided into a set of distinct trails, such that no one single trail spans all of the network, but there is always one trail which leads from a given source node to a given destination node. Routing can then be carried out simply by selecting the appropriate trail linking a source node to the desired destination node. Once on the trail, the packet can be routed in a quasi-one-dimensional fashion. As in one-dimensional routing, and by contrast with the prior art approaches in the papers by Yener et al. and Zhang et al., the source node selects the entire trail from the source to the destination before sending the packet.
Preferred implementations of the invention offer the advantages of very simple processing and routing nodes which may be based on simple header-word recognition. Message delivery time is dominated by the speed of light delay. No contention is required within the network, there is no need for buffering within the network and the network i

Affiliated with

Also associated with

Rating

Communications network does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Communications network, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Communications network will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3200173