Method for directing the route of a cell transmitting a network

• US 6,654,369 B1
• Filed: 05/28/1999
• Issued: 11/25/2003
• Est. Priority Date: 05/28/1999
• Status: Expired due to Term

• Current Assignee: Micron Technology, Inc.
• Original Assignee: Intel Corporation
• Inventors: Pelisster, Joseph E., Swortwood, William H.
• Primary Examiner(s): VANDERPUYE, KENNETH N
• Application Number:
  US09/322,152
• Time in Patent Office: 1,642 Days
• Field of Search: 370/389, 370/351, 370/392, 370/395-3, 370/401, 370/428
• US Class Current: 370/389
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/34 Source routing
• CPC Class Codes: H04L 45/566 Routing instructions carried by the data packet, e.g. active networks

Abstract

A method for routing a cell through a network using explicit routing or destination routing, or a combination of both routing techniques. A directed route for a cell can include an explicit route portion and a destination address routing portion. An address in the cell can indicate the technique that should be used to route the cell. Explicit routing is used if the address is equal to a predetermined global address or an address of the device and the cell has not reached the end of the explicit route. Otherwise, destination address routing is used based on a final destination address.

Claims

1. A method of routing a cell along a directed route comprising the steps of:

receiving the cell including a first address and a final destination address;

explicitly routing the cell if the first address is a predetermined global address or the address of a device; and

destination address routing the cell based on the final destination address if the first address is not equal to the predetermined global address or the address of the device.

2. The method of claim 1, further comprising the step of providing a copy of the first address to a forwarding database to obtain routing instructions, the routing instructions identifying a destination port for sending the cell for destination address routing if the first address is not equal to the predetermined global address or the address of the device, the routing instructions identifying a management entity at the device for receiving and explicit route processing the cell if the first address is a predetermined global address or the address of the device.

3. The method of claim 1 wherein said received cell also includes information specifying an explicit route for the cell to traverse and a Hop Pointer identifying the position of the cell in the explicit route.

4. The method of claim 3 wherein said step of explicitly routing the cell comprises the steps of:

determining if the cell is at the end of the explicit route based on the hop pointer;

adjusting the hop pointer; and

routing the cell to the next device in the explicit route if the cell is not at the end of the explicit route.

5. The method of claim 4 wherein said information specifying an explicit route for the cell comprises information identifying destination ports to be used for forwarding the cell along the explicit route.

6. The method of claim 5 wherein said step of routing the cell to the next device in the explicit route comprises the step of using the hop pointer to identify the appropriate destination port for routing the cell using the information identifying destination ports.

7. The method of claim 1 wherein said cell includes information identifying an explicit outbound path for an initial cell.

8. The method of claim 7 wherein information identifying an explicit inbound path for a return cell is populated by devices along the explicit outbound path of a corresponding initial cell.

9. A method of routing a cell along a directed route through a network, the directed route including a destination address route portion and an explicit route portion, the method comprising the steps of:

receiving a cell at a device, the cell including a first address, a final destination address, and information specifying the explicit route portion;

determining if the first address is equal to a predetermined global address or the address of the device;

explicitly routing the cell to a next device of the explicit route portion if the first address is the predetermined global address or the address of the device and the device is not at the end of the explicit route portion; and

destination address routing the cell based on the final destination address if the first address is not equal to the predetermined global address or the address of the device.

10. The method of claim 9 wherein said step of destination address routing comprises the step of destination address routing the cell based on the final destination address if the first address is not equal to the predetermined global address or the address of the device, or if cell is at the end of the explicit route portion.

11. The method of claim 9 wherein said cell is an initial cell.

12. The method of claim 9 wherein said cell is a cell sent as a return cell sent in reply to an initial cell that traverses a directed route including an explicit path, wherein the information describing the explicit route for the return cell is generated by devices along the explicit route portion of the initial cell, the explicit route portion for the return cell being a reverse path of the explicit route portion of the initial cell.

13. A device for routing cells in a network using either explicit routing or destination address routing, each cell including a first address and a final destination address, the device comprising:

a plurality of ports, each port connected to a link;

a receive queue and a transmit queue coupled to each port;

a forwarding database storing cell routing information corresponding to each of a plurality of addresses;

a relay entity coupled to the queues and the forwarding database, the relay entity obtaining routing information from the forwarding database based upon the first address and relaying the cell to the port specified by the routing information if the first address is not a global address or an address of the device;

a management entity coupled to the relay entity, the relay entity relaying the cell to the management entity for explicit routing if the first address in the cell is a predetermined global address or the address of the device.

14. The device of claim 13 wherein the cell also includes information describing an explicit route for the cell and a final destination address, the management entity routing the cell to the next device in the explicit route if the cell has not reached the end of the explicit route.

15. The device of claim 14 wherein management entity comprises a switch manager.

16. The device of claim 13 wherein the relay entity copies the cell from a receive queue to a transmit queue corresponding to the port specified by the routing information if the first address is not a global address or an address of the device.

17. A device for routing cells in a network using either explicit routing or destination address routing, each cell including a first address and a final destination address, the device comprising:

a relay entity obtaining routing information based upon the first address in the cell and destination address routing the cell if the first address is not a global address or an address of the device;

a management entity coupled to the relay entity, the relay entity relaying the cell to the management entity for explicit route processing if the first address in the cell is a predetermined global address or the address of the device.

18. A device for routing cells in a network along a directed route including a destination address route portion and an explicit route portion, each cell including a first address and a final destination address and information specifying the explicit route portion, the device comprising:

a relay entity obtaining routing information based upon the first address in the cell and destination address routing the cell if the first address is not a global address or an address of the device; and

a management entity coupled to the relay entity, the management entity explicitly routing the cell to a next device of the explicit route portion if the first address is the predetermined global address or the address of the device and the device is not at the end of the explicit route portion, and the management entity destination address routing the cell based on the final destination address if the first address is not equal to the predetermined global address or the address of the device.

19. A computer program encoded on a computer readable medium for routing a cell, the computer program causing the following to be performed when executed by a computer:

receiving the cell including a first address and a final destination address;

explicitly routing the cell if the first address is a predetermined global address or the address of a device; and

destination address routing the cell based on the final destination address if the first address is not equal to the predetermined global address or the address of the device.

20. In a data network comprising a plurality of interconnected nodes for routing data cells/packets along a directed route, each data cell/packet including a first address and a final destination address, each node comprising:

a plurality of ports, each port connected to a link;

a receive queue and a transmit queue coupled to each port;

a forwarding database to store routing information corresponding to each of a plurality of addresses;

a relay entity to obtain routing information from the forwarding database based upon the first address of an incoming data cell/packet, and relay the data cell/packet to the port specified by the routing information if the first address is not a predetermined global address or an address of the node; and

a management entity to process explicit routing if the first address in the incoming data cell/packet is the predetermined global address or the address of the node.

21. The node as claimed in claim 20, wherein each data cell/packet further includes information describing an explicit route for the data cell/packet and a final destination address, the management entity routing the data cell/packet to a next node in the data network in the explicit route if the data cell/packet has not reached the end of the explicit route.

22. The node as claimed in claim 21, wherein the relay entity copies the data cell/packet from the receive queue to the transmit queue corresponding to the port specified by the routing information if the first address is not the predetermined global address or the address of the node.

23. The node as claimed in claim 20, wherein the data cell/packet further includes information specifying an explicit route for the data cell/packet to traverse and a hop pointer identifying the position of the data cell/packet in the explicit route.

24. The node as claimed in claim 23, wherein the explicit routing of the incoming data cell/packet is processed by:

determining if the data cell/packet is at the end of the explicit route based on the hop pointer;

adjusting the hop pointer; and

routing the data cell/packet to a next node in the data network in the explicit route if the data cell/packet is not at the end of the explicit route.

25. The node as claimed in claim 24, wherein the information specifying an explicit route for the data cell/packet comprises information identifying destination ports to be used for forwarding the data cell/packet along the explicit route.

26. The node as claimed in claim 25, wherein the data cell/packet routed to the next node in the explicit route comprises using the hop pointer to identify the appropriate destination port for routing the data cell/packet using the information identifying destination ports.