Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Alternate path routing
Reexamination Certificate
1998-01-28
2001-08-07
Rinehart, Mark (Department: 2756)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Alternate path routing
C709S238000, C709S243000
Reexamination Certificate
active
06272548
ABSTRACT:
BACKGROUND TO THE INVENTION
1. Field of the Invention
The present invention relates to a method of routing packets on a network, and to networks and nodes adapted to implement the method.
2. Related Art
Packet routing networks may be used, for example, to interconnect the different processors of a multi-processor computer, or as the basis of a LAN interconnecting a number of different computers. In the future, it is envisaged that such networks might be used for distributed processing applications such as the provision of shared virtual-reality environments—“virtual meeting places”—or for fast complex visualisation of data, for example in financial institutions. Such a network might also be used for the internal architecture of a packet switch used, for example, in a telecommunications network.
All the examples discussed above will benefit from networks capable of operating at ultrafast speeds, e.g 10 GBit/s or more. To achieve such speeds, it is essential that there is efficient routing of packets to minimise transit times from source to destination and without the process of making routing decisions itself providing a bottleneck. It has previously been proposed to use a class of techniques known as “self-routing”, as described, for example, in the present applicant's copending international application PCT/GB 95/01176.
Self-routing is a method of navigation through a packet-switched network in which the onward route at each node is determined locally without consulting a network database in a centralised or distributed form (for a formal definition of self-routing, reference is made to the paper by Baransel et al cited below as reference [
14
]). The routing decision is made based on information (usually the destination address) extracted from the packet header. In such a network, the time required to make a routing decision must be no longer than the transmission time for a single packet. If this condition is not observed the system becomes unstable since the ratio of the packet arrival rate to the service rate at a node can become greater than 1, so that queue lengths can grow indefinitely. For high transmission speeds, or for short packet lengths, this stability criterion is more difficult to satisfy. It becomes a very severe constraint in the case of ultra-high speed networks operating at multi-Gbit/s transmission rates, particularly when the transmission format uses fixed-length packets or cells of at most a few tens of bytes in length.
Assuming, for example, the 53-byte length of ATM cells and a peak bit rate of 100 Gbit/s [
1
], a node has only a few nanoseconds to perform the following tasks for each cell that arrives: select the appropriate output link on which the cell should be transmitted; and resolve contention. The situation can be alleviated by breaking these tasks into a number of separate procedures which are performed in pipe-line mode. Nevertheless it is essential for ultrafast networks that the procedures used for routing and contention resolution should be as simple as possible to minimise the processing time.
A further motivation for simplifying the routing and contention-resolution procedures in ultrafast networks is the technology limitations of photonic devices. Recent experiments have demonstrated the potential for photonic networks to carry data at single-wavelength, single-channel rates approaching 100 Gbit/s and beyond [
2
]. In these networks the transmission bit-rate is higher that the speed capability of electronic devices. However, the procedures for routing involve combinations of processes at two distinct levels of granularity—the bit level and the packet level [
1
]. For ultrafast networks, processes at the bit level require photonic devices with response times at least as fast as the bit period (picosecond scale), whereas processing at the packet level can be performed using high-speed electronics at the packet rate (nanosecond scale). Photonic logic devices are much less developed than electronic ones, they have primitive functionality and are relatively poorly integrated, power hungry and costly and are unlikely to achieve a comparable level of development for many years to come. Therefore a further requirement for ultrafast self-routing networks is that the number and complexity of bit-level processes should be reduced to the absolute minimum.
U.S. Pat. No. 5,105,424 discloses one example of a routing scheme, intended for use within an integrated electronic massively parallel processor. The scheme involves determining at the source of a packet the entire path that the packet should follow from the source to the destination. The path is defined as a sequence of relative addresses and is added to the message packet in the form of a header. Routing is carried out by routing automata which are associated with the different computing nodes. The direction in which the packet is to be output is determined at the automate by referring to the relative address in the header, and the header is updated by deleting the parts that relate to the previous portion of the path. This has the disadvantage that the address has to be read, processed and modified at every node. This imposes a significant overhead of complex bit-level processing. Also, since this approach does not allow for deflection from the predetermined path, deflection routing cannot be used. This makes it necessary for the nodes to include large buffers to resolve contention under conditions of heavy traffic load.
The paper by T Y Chung published in Phoenix Conference on Computers and Communications, March 1989, USA, pages 214-218, discloses a routing scheme which, like that in the U.S. patent discussed above, fully determines the route of the packet at the source, and programs this route in the header of the packet. It differs however in that the route is determined using a numerical algorithm rather than from a look-up table at the source. But as in the above scheme, the intermediate routing nodes, termed in this paper “tandem nodes”, simply read the routing information and act upon it, rather than making an autonomous routing decision. The approach adopted in this paper still requires that all the routing information coded into the packet header must be read bit-by-bit, updated, and the packet header must be overwritten with the updated routing information. Again, this amount of bit-level processing is a significant disadvantage in the context of the system intended to operate at high bit rates. Although the paper makes reference to the possibility of deflection routing, the routing scheme, because of its deterministic nature, is not well adapted for such an approach. In this scheme, if deflection occurs, then the deflecting node has to recompute the routing information for the entire onward path leading to the packets destination, just as though the deflecting node which effects the deflection was itself the original source of the packet. Since these methods use predetermined routes encoded in the packet header, neither is a self-routing method.
SUMMARY OF THE INVENTION
According to a first aspect of the present invention, there is provided a method of routing a packet carried on a network having a generally regular topology comprising:
(a) receiving a packet at a node;
(b) reading a destination address and a directional flag, both of which are carried with the packet, the directional flag indicating explicitly a preferred direction of onward travel for the packet;
(c) making a local routing decision according to the value of the directional flag; and
(d) outputting the packet from the node in a direction selected in accordance with the routing decision.
The term “directional flag” as used herein denotes a simple unit of data which indicates a preferred direction of travel of a packet from its source to its destination without fully determining the path, that is the specific sequence of links and routing nodes followed by the packet, from the source of the packet to the destination. It may comprise just a single bit for each dimension of
Cotter David
Tatham Martin C
British Telecommunications public limited company
Cardone Jason D.
Nixon & Vanderhye P.C.
Rinehart Mark
LandOfFree
Dead reckoning routing of packet data within a network of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Dead reckoning routing of packet data within a network of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dead reckoning routing of packet data within a network of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2491119