Multiple packet paths to improve reliability in an IP network

• US 6,831,898 B1
• Filed: 08/16/2000
• Issued: 12/14/2004
• Est. Priority Date: 08/16/2000
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Systems, Inc.
• Inventors: Gai, Silvano, Hang, Soei-Shin, Edsall, Thomas J.
• Primary Examiner(s): Wilson, Robert W.
• Application Number:
  US09/593,566
• Time in Patent Office: 1,581 Days
• Field of Search: 370/389, 370/390, 370/394, 370/351, 370/352, 370/400, 370/401
• US Class Current: 370/256
• 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/16 Multipoint routing
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 47/2416 Real-time traffic
• CPC Class Codes: H04L 47/34 ensuring sequence integrity, e.g. using sequence numbers

Abstract

The invention replicates a packet requiring high availability and transmits it from two or more ports of a switch, for example a wiring closet Layer 2 switch. The parent packet carries a unique sequence number. The copies of the packet each carry the parent packet'"'"'s unique sequence number. Each copy of the packet then travels on separate pathways through routers (Layer 3 network devices). The pathways are maintained separate by assigning high costs in a LSP routing sense to links connecting the two paths, and by assigning low costs to links along the desired paths. The two identical packets converge on the destination station. The destination station accepts the first packet with a particular sequence number, and discards any later packets with the same sequence number. In the event that a link in one path has a catastrophic failure, then the packet travelling along the other path reaches the destination station and service remains operative without interruption. The lost path is then recomputed by the a router (if any) still receiving the lost packet. A new non-converging path may be selected if any are available, depending upon the topology. After the disruption is repaired, the original dual pathways may once again be established.

Claims

1. A computer network having improved reliability in data transmissions, comprising:

an interpreter in a switch for interpreting a special multicast address in a packet received by said switch, said switch in response to receipt of a packet having said special multicast address, replicating said packet by transmitting identical copies of said packet on a plurality of ports of said switch;

a first router for receiving a first copy of said packet having said special multicast address transmitted from a first port of said plurality of ports of said switch, and a second router for receiving a second copy of said packet having said special multicast address, said second packet transmitted by a second port of said plurality of ports of said switch;

a first plurality of subsequent routers connected to said first router along an intended path for said first copy of said packet, said intended path having a plurality of links, and said links assigned a low cost in a Link State Packet Routing sense; and

a second plurality of routers connected to said second router along an intended path for said second copy of said packet, said intended path having a plurality of links, and said links assigned a low cost in a Link State Packet Routing sense, said first plurality of routers connected to said second plurality of routers by links having assigned high costs in a Link State Packet Routing sense.

2. A network device for forwarding voice packets on a computer network, comprising:

an input port for receiving said voice packet;

a plurality of output ports assigned for transmitting said voice packet out of said network device in the event that a received packet carries a special multicast address in a layer 2 destination address field of said received packet; and

a circuit to read said layer 2 destination address field of said received packet, and in the event that said special multicast address is found in said layer 2 destination address field of said received packet, to interpret said special multicast address as indicating that said received packet is said voice packet, and to transfer said voice packet to said plurality of output ports for transmission of replica packets of said voice packets through different paths in said computer network, said paths having a low cost, in a Link State Protocol (LSP) sense, said paths also having a high cost to links that would connect each of said different paths to each other, said high cost effectively maintaining a non-converging separateness between said different paths.

3. The apparatus of claim 2, further comprising:

said network device is a layer 2 switch.

4. The apparatus of claim 2, further comprising:

said network device is a router.

5. A method of improving reliability in data communications over a computer network, comprising:

receiving a voice data packet by a network device, replicating said voice data packet, and transmitting replica packets onto a first link and a second link;

assigning low cost to links, including said first link, in a first desired path through said computer network, said cost used by Link State Packet Routing protocol (LSP protocol) to select a route through said network;

assigning low cost to links, including said second link, in a second desired path, through said computer network; and

assigning high costs to links between said first desired path and said second desired path, so that in response to assigning low costs to links in said first and second desired paths, LSP protocol selects said first and second desired paths for transmitting said replica packets through said network, respectively, and in response to high costs assigned to said links between said first and second desired paths, LSP does not select links that would create a convergence of said first and second desired paths.

6. The method of claim 5 wherein LSP routing selects links that would create a convergence of said first and second desired paths upon failure of a link in either said first and second desired paths.

7. A method of improving reliability in data communications over a computer network, comprising:

receiving a voice data packet by a network device, replicating said voice data packet, and transmitting replica packets onto a first link and a second link;

assigning low cost to links, including said first link, in a first desired path through said computer network, said cost used by Link State Packet Routing protocol (LSP protocol) to select a route through said network;

assigning low cost to links, including said second link, in a second desired path through said computer network;

assigning high costs to links between said first desired path and said second desired path, so that in response to assigning low costs to links in said first and second desired paths, LSP protocol selects said first and second desired paths for transmitting said replica packets through said network, respectively, and in response to high costs assigned to said links between said first and second desired paths, LSP does not select links that would create a convergence of said first and second desired paths;

transmitting a voice data packet by a first digital telephone to a first network device;

transmitting, by said first network device, a replica packet of said voice data packet onto said first link for transmission through said first desired path through said computer network to a second network device;

transmitting, by said first network device, a replica packet of said voice data packet onto said second link for transmission through said second desired path through said computer network to said second network device; and

converting by a second digital telephone a first replica packet of said voice data packet received by said second network device into audible sound, and discarding any subsequently received replica packets of said voice data packet.

8. The method of claim 7 further comprising:

selecting said first replica packet of said voice data packet by said second network device.

9. The method of claim 7 further comprising:

selecting said first replica packet of said voice data packet by said second digital telephone.

10. The method of claim 7 further comprising:

selecting said first network device to be a layer 2 switch.

11. The method of claim 7 further comprising:

selecting said first network device to be a router.

12. The method of claim 7 further comprising:

writing a sequence number into said voice data packet by said first digital telephone;

writing said sequence number into each said replica packet; and

using said sequence number to determine the first received replica of said voice data packet by said second network device.

13. A computer readable device having instructions written thereon for practicing a method of,

receiving a voice data packet by a network device, replicating said voice data packet, and transmitting replica packets onto a first link and a second link;

assigning low cost to links, including said first link, in a first desired path through said computer network, said cost used by Link State Packet Routing protocol (LSP protocol) to select a route through said network;

assigning low cost to links, including said second link, in a second desired path through said computer network; and

assigning high costs to links between said first desired path and said second desired path, so that in response to assigning low costs to links in said first and second desired paths, LSP protocol selects said first and second desired paths for transmitting said replica packets through said network, respectively and in response to high costs assigned to said links between said first and second desired paths, LSP does not select links that would create a convergence of said first and second desired paths.

14. Electromagnetic signals travelling on a computer network, said electromagnetic signals carrying instructions for execution on a processor for practicing a method of,

receiving a voice data packet by a network device, replicating said voice data packet, and transmitting replica packets onto a first link and a second link;

assigning low cost to links, including said first link, in a first desired path through said computer network, said cost used by Link State Packet Routing protocol (LSP protocol) to select a route through said network;

assigning low cost to links, including said second link, in a second desired path through said computer network; and

assigning high costs to links between said first desired path and said second desired path, so that in response to assigning low costs to links in said first and second desired paths, LSP protocol selects said first and second desired paths for transmitting said replica packets through said network, respectively, and in response to high costs assigned to said links between said first and second desired paths, LSP does not select links that would create a convergence of said first and second desired paths.

15. A method for use with transmitting a packet from a source to a destination, said method comprising the steps of:

assigning a low cost, in a Link State Packet (LSP) routing sense, to links on two or more packet paths from said source to said destination; and

assigning a high cost, in an LSP routing sense, to links that would connect each of said two or more packet paths to each other, said high cost effectively maintaining a non-converging separateness between said two or more packet paths.

16. The method as in claim 15, further comprising the steps of:

assigning a unique sequence number to said packet;

replicating said packet into two or more packets, each of said two or more packets carrying the same unique sequence number;

transmitting said two or more packets over said low cost two or more packet paths, respectively;

accepting, at said destination, a first of said two or more packets to arrive at said destination; and

discarding, at said destination, any of said two or more packets to arrive at said destination after said first packet.

17. The method as in claim 16, wherein said steps of replicating and transmitting are performed on a network device.

18. The method as in claim 17, wherein said step of transmitting is performed over two or more ports of said network device.

19. The method as in claim 17, wherein said network device is a switch.

20. The method as in claim 17, wherein said network device is a router.

21. The method as in claim 15, wherein said packet originates from a digital telephone.

22. The method as in claim 15, wherein said packet terminates at a digital telephone.

23. The method as in claim 15, wherein said packet is a voice packet.

24. A system for use with transmitting a packet from a source to a destination, said system comprising:

a source network device having circuitry for;

(i) assigning a unique sequence number to said packet,

(ii) replicating said packet into two or more packets, each of said two or more packets carrying the same unique sequence number,

(iii) assigning a low cost, in a Link State Packet (LSP) routing sense, to links on two or more packet paths from said source to said destination,

(iv) assigning a high cost, in an LSP routing sense, to links that would connect each of said two or more packet paths to each other, said high cost effectively maintaining a non-converging separateness between said two or more packet paths, and

(v) transmitting said two or more packets over said low cost two or more packet paths, respectively;

at least one subsequent network device on each of said two or more packet paths having circuitry for forwarding said packet along said respective packet path according to said low cost link arrangement in an LSP routing sense; and

a destination network device having circuitry for;

(i) accepting a first of said two or more packets to arrive at said destination network device, and

(ii) discarding any of said two or more packets to arrive at said destination network device after said first packet.

25. The system as in claim 24, wherein said initiating network device is a switch.

26. The system as in claim 24, wherein said initiating network device is a router.

27. The system as in claim 24, wherein said packet originates from a digital telephone.

28. The system as in claim 24, wherein said packet terminates at a digital telephone.

29. The system as in claim 24, wherein said packet is a voice packet.

30. A network device for use in sending packets from a source to a destination, comprising:

an input port for receiving packets from a source;

a processor for assigning a low cost, in a Link State Packet (LSP) routing sense, to links on two or more packet paths from said source to said destination, and assigning a high cost, in an LSP routing sense, to links that would connect each of said two or more packet paths to each other, said high cost effectively maintaining a non-converging separateness between said two or more packet paths; and

two or more output ports for transmitting said packets to a destination over said two or more packet paths.

31. An initiating network device, comprising:

an input port for receiving a packet; and

at least two output ports for transmitting said packet, a first output port of said two output ports to transmit said packet over a first packet path and a second output port of said two output ports to transmit said packet over a second packet path, said first packet path and said second packet path leading to a single destination, said first packet path and second packet path having a low cost in a Link State Packet (LSP) routing sense, each of said first packet path and said second packet path also maintaining a non-converging separateness between each other by having a high cost, in an LSP routing sense, assigned to links that would connect each of said first packet path and said second packet path to each other.

32. A destination network device, comprising:

at least two input ports, a first input port of said at least two input ports to receive a plurality of packets over a first packet path and a second input port of said at least two input ports to receive a plurality of packets over a second packet path, said first packet path and said second packet path leading to a single destination, said first packet path and said second packet path each having a low cost in a Link State Packet (LSP) routing sense, each of said first packet path and said second packet path also maintaining a non-converging separateness between each other by having a high cost, in an LSP routing sense, assigned to links that would connect each of said plurality of packet paths to each other;

circuitry for reading a unique sequence number on each received packet, said circuitry accepting a first of said plurality of packets received with a unique sequence number and discarding any other of said plurality of packets received with the same unique sequence number after said first packet has been received; and

an output port for transmitting said packet to a terminating destination.

33. A system for use with transmitting a packet from a source to a destination, said system comprising:

means for assigning a low cost, in a Link State Packet (LSP) routing sense, to links on two or more packet paths from said source to said destination; and

means for assigning a high cost, in an LSP routing sense, to links that would connect each of said two or more packet paths to each other, said high cost effectively maintaining a non-converging separateness between said two or more packet paths.

34. The system as in claim 33, further comprising:

means for assigning a unique sequence number to said packet;

means for replicating said packet into two or more packets, each of said two or more packets carrying the same unique sequence number;

means for transmitting said two or more packets over said low cost two or more packet paths, respectively;

means for accepting, at said destination, a first of said two or more packets to arrive at said destination; and

means for discarding, at said destination, any of said two or more packets to arrive at said destination after said first packet.

35. A computer readable device having instructions written thereon for practicing a method of,

assigning a low cost, in a Link State Packet (LSP) routing sense, to links on two or more packet paths from said source to said destination;

and

assigning a high cost, in an LSP routing sense, to links that would connect each of said two or more packet paths to each other, said high cost effectively maintaining a non-converging separateness between said two or more packet paths.

36. Electromagnetic signals travelling on a computer network, said electromagnetic signals carrying instructions for execution on a processor for practicing a method of,

assigning a low cost, in a Link State Packet (LSP) routing sense, to links on two or more packet paths from said source to said destination;

and

assigning a high cost, in an LSP routing sense, to links that would connect each of said two or more packet paths to each other, said high cost effectively maintaining a non-converging separateness between said two or more packet paths.