Method and apparatus for transmitting data frames between switches in a meshed data network

• US 6,301,257 B1
• Filed: 03/19/1997
• Issued: 10/09/2001
• Est. Priority Date: 03/19/1997
• Status: Expired due to Term

• Current Assignee: Avaya Management L.P. (Avaya Incorporated)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Johnson, Bobby, Yip, Michael, Ferguson, Earl, Goguen, Michael L.
• Primary Examiner(s): Chin, Wellington
• Assistant Examiner(s): NGUYEN, STEVEN H D
• Application Number:
  US08/820,948
• Time in Patent Office: 1,665 Days
• Field of Search: 370/400, 370/401, 370/402, 370/406, 370/409, 370/404, 370/351, 370/355, 370/254, 370/255, 370/386, 370/389, 370/397, 370/398, 370/396, 370/399, 370/390, 370/391, 370/392, 370/474, 370/432, 370/555, 370/410, 379/219, 379/220, 379/224, 379/225, 379/272, 395/200.33, 709/227, 709/238
• US Class Current: 370/406
• CPC Class Codes: H04L 2012/5617 Virtual LANs; Emulation of LANs
• CPC Class Codes: H04L 2012/562 Routing
• CPC Class Codes: H04L 2012/5627 Fault tolerance and recovery
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

In a data network, a source node transmits a data packet to a destination node across interconnected switches whereby a switch, upon receiving the data packet from the source node, queries other switches in the network for the appropriate switch and port on the switch out which to forward the data packet to the destination node. The appropriate switch responds to the query with its switch number and the port number of the port out which the data packet should be sent to reach the destination node. The querying switch caches the switch number and port number and prepends a destination tag to subsequent data packets it receives which are destined to the same destination node, thereby providing a distributed system among the switches in the network for maintaining detailed information regarding the appropriate switch and port out which to forward data packets received by a source node in the network.

Claims

1. In a network comprising a plurality of switches interconnected to form a meshed network topology for transmitting a data packet from a first node to a second node, a method comprising:

receiving a data packet at a first switch coupled to the first node;

in response to receiving the data packet, checking in a cache of the first switch for a destination tag, the destination tag identifying a second switch and a port of the second switch to which the second node is coupled; and

if the destination tag is in the cache of the first switch, then

prepending the destination tag to the data packet to form a modified data packet for transmission to the second switch.

2. The method of claim 1, further comprising:

if the destination tag identifying the second switch and the port of the second switch to which the second node is connected is not in the cache of the first switch, then

broadcasting the data packet from the first switch to the plurality of switches;

transmitting a query packet from the first switch to the plurality of switches to determine the second switch and the port on the second switch to which the second node is connected in order to generate the destination tag;

receiving from the second switch a response packet in response to the query packet specifying the second switch and the port of the second switch to which the second node is connected to generate the destination tag; and

storing the destination tag in the cache of the first switch.

3. The method of claim 1 further comprising:

transmitting the modified data packet from the first switch to the second switch identified by the destination tag;

receiving the modified data packet at the second switch;

parsing the destination tag prepended to the data packet from the modified data packet; and

transmitting the data packet out the port identified by the destination tag.

4. The method of claim 3, further comprising:

prior to transmitting the data packet out the port identified by the destination tag,

stripping the destination tag prepended to the data packet.

5. The method of claim 1, wherein

the destination tag comprises a switch number and a port number;

and

prepending the destination tag to the data packet comprises prepending the switch number and the port number to the data packet.

6. The method of claim 2 further comprising:

receiving a second data packet at the first switch coupled to the first node;

checking in the cache of the first switch coupled to the first node;

checking in the cache of the first switch and finding the destination tag previously created associated with the first and second data packets; and

prepending the destination tag to the second data packet to form a second modified data packet and transmitting the second modified data packet from the first switch to the second node.

7. The method of claim 2 further comprising:

in response to the query packet,

determining if a node is coupled to a port of a switch associated with the destination address of the broadcasted data packet.

8. The method of claim 7 further comprising:

generating a response packet due to determining that the second node is coupled to a port of the second switch associated with the destination address of the broadcasted data packet, the response packet including the switch number and the port number coupled to the second node; and

transmitting the response packet to the first switch.

9. An article of manufacture, comprising:

a computer useable medium having computer readable program code embodied therein for transmitting a data packet received from a first node to a second node through a network comprising a plurality of switches interconnected to form a meshed network topology, the computer useable medium including,

computer readable program code to receive the data packet at a first switch coupled to the first node;

computer readable program code to check in a cache of the first switch for a destination tag in response to receiving the data packet, the destination tag identifying a second switch and a port of the second switch to which the second node is coupled; and

if the destination tag is in the cache of the first switch, then

computer readable program code to prepend the destination tag to the data packet to form a modified data packet.

10. The article of manufacture of claim 9, further comprising if the destination tag identifying the second switch and the port of the second switch to which the second node is coupled is not in the cache of the first switch:

computer readable program code to

i) broadcast the data packet from the first switch to the plurality of switches;

ii) transmit a query packet from the first switch to the plurality of switches to determine the second switch and the port of the second switch to which the second node is coupled;

iii) receive from the second switch a response packet in response to the query packet that specifies the destination tag identifying the second switch and the port of the second switch to which the second node is coupled; and

iv) store the destination tag in the cache of the first switch.

11. The article of manufacture of claim 9 further comprising:

computer readable program code to transmit the modified data packet from the first switch to the second switch identified by the destination tag;

computer readable program code to receive the modified data packet at the second switch;

computer readable program code to parse the destination tag prepended to the data packet from the modified data packet; and

computer readable program code to transmit the data packet out the port identified by the destination tag.

12. The article of manufacture of claim 11, further comprising computer readable program code to strip the destination tag prepended to the data packet prior to transmitting the data packet out the port identified by the destination tag.

13. The article of manufacture of claim 9, wherein the destination tag comprises a switch number and a port number and wherein the computer readable program code to prepend the destination tag to the data packet includes computer readable program code to prepend the switch number and the port number to the data packet if the destination tag is in the cache.

14. The article of manufacture of claim 9 wherein the computer useable medium is one or more of the set of magnetic storage medium, optical storage medium, or semiconductor storage medium.

15. A method of transmitting data packets between a node of a first network to a node of a second network over a meshed network of switches, without decoding the data packets at every switch to determine the destination address, the method comprising:

maintaining a table of destination tags in each of the switches of the meshed network of switches, the table of destination tags identifying the switches and ports of the switches to which the nodes of the first and second networks are coupled;

prepending a destination tag to the data packets forming modified data packets, the destination tag associated with the destination of the data packets through the meshed network of switches; and

transmitting the modified data packets through the meshed network of switches between the first and second networks in response to the destination tag.

16. The method of claim 15 for transmitting data packets, the method further comprising:

prior to prepending the destination tag to the data packets, receiving the data packets from the first or second network for transmission to the second or first network respectively.

17. The method of claim 15 for transmitting data packets, the method further comprising:

parsing the destination tag and the data packets from the modified data packets, transmitting the data packets to the first or second network in response to the destination tag.

18. The method of claim 15 for transmitting data packets, the method further comprising:

prior to maintaining the table of destination tags in each of the switches of the meshed network of switches, generating the table of destination tags in a switch of the meshed network of switches by transmitting broadcast type destination tags from the switch to each other switch in the meshed network of switches and receiving a response packet indicating the switch and port number of the switch to which the first or second network is coupled.

19. A computer data signal embodied in a bit stream between a node of a first network and a node of a second network in a meshed network of switches, the computer data signal comprising:

at least one byte indicating a switch number of a switch to which a node of the first or second network is coupled, and

at least one byte indicating a port number of a port of the switch to which the node of the first or second network is coupled,

the at least one byte indicating the switch number and the at least one byte indicating the port number preceding a data packet to form a modified data packet for communication over the meshed network of switches.

20. The computer data signal of claim 19 wherein the data packet includes

a destination address and a source address of the data packet, and

data.

21. The computer data signal of claim 19 wherein the at least one byte indicating a switch number and the at least one byte indicating a port number are a destination tag prepended to the data packet to form the modified data packet.

22. The computer data signal of claim 19 wherein the bit stream is communicated over network media.

23. The computer data signal of claim 22 wherein the network media is one of the set of cable, wireless carrier waves, and optical fiber.