Reliable transport protocol for internetwork routing

• US 5,519,704 A
• Filed: 04/21/1994
• Issued: 05/21/1996
• Est. Priority Date: 04/21/1994
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Systems, Inc.
• Inventors: Albrightson, Robert, Farinacci, Dino
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): HOM, SHICK C
• Application Number:
  US08/231,619
• Time in Patent Office: 761 Days
• Field of Search: 370/85.13, 370/60, 370/94.1, 370/85.3, 370/85.5, 370/85.6, 370/32, 370/60.1
• US Class Current: 370/402
• CPC Class Codes: H04L 12/1868 Measures taken after transmission, e.g. acknowledgments
• CPC Class Codes: H04L 12/1881 with schedule organisation, e.g. priority, sequence management
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/026 Details of "hello" or keep-alive messages
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/52 Multiprotocol routers

Abstract

A reliable transport protocol, suitable for routing protocols, that works with unicast transmission and multicast transmission, and an improved routing protocol based thereon. Multicast transmissions can be interspersed with unicast transmissions in situations where some of the receivers have received all of the packets sent to them and others have not. A mechanism to deliver multicast packets quickly to some receivers, even when there are unacknowledged packets pending for other receivers. When a packet is multicast from a sender node to all of its neighbors, the sender puts the packet on a queue for each neighbor and retransmits the packet if an acknowledgement has not been received within a predetermined period of time. If the packet is retransmitted, it is transmitted as a unicast. The invention takes advantage of the fact that the sender already has to maintain state information to determine who has not received its packets. A technique for distributing routing information gathered by a router outside an autonomous system of routers using the same routing protocol. A metric calculated by an identical routing protocol or a different routing protocol may be distributed and used by routers in a different autonomous system. Packets may be labeled with authentication information or with an administrative tag that specifies a method of routing in response to policy considerations.

Claims

1. A method of reliably receiving, at a device having a recipient identifier, multicast packets and unicast packets in a network, comprising

upon receiving a first packet having a sequence number from a source, transmitting an acknowledgment to said source, said acknowledgment indicating said recipient identifier;

upon receiving a second packet having an indicator representative of a set of destinations for which an acknowledgment was not received, entering a conditional-receive mode if said indicator is not representative of said recipient identifier; and

upon receiving a third packet having an indicator representative of conditional receipt, receiving said third packet only when in said conditional-receive mode.

2. A method as in claim 1, further comprising discarding said sequence number of said first packet after transmitting said acknowledgment.

3. A method as in claim 1, further comprising exiting said conditional-receive mode after receiving said third packet.

4. A method of reliably transmitting multicast packets and unicast packets in a network, comprising

multicasting a first packet having a sequence number to a plurality of destinations;

recording a set of ones of said plurality of destinations for which an acknowledgment is not received;

when said set is nonempty, multicasting a second packet having an indicator representative of said set;

multicasting a third packet having an indicator representative of conditional receipt, whereby destinations in said set ignore said third multicast packet; and

unicasting said first packet and said third packet to each destination in said set.

5. A method as in claim 4, further comprising waiting for an acknowledgment to said first packet from each destination in said set before said step of recording.

6. A method as in claim 4, wherein multicasting said first packet comprises transmitting said first packet to all of said one destinations.

7. A method as in claim 4, wherein multicasting said first packet comprises transmitting said first packet to all of said one destinations simultaneously over a common communication link.

8. A method as in claim 4, wherein said destinations are a set of neighbors to a router in said network.

9. A method as in claim 4, wherein said first packet comprises an update packet or a query packet in a routing protocol, said routing protocol comprising a finite state machine substantially equivalent to the DUAL finite state machine.

10. A method as in claim 4, wherein said indicator comprises a list of said one destinations that are members of said set.

11. A method as in claim 4, wherein said third packet comprises an update packet or a query packet in a routing protocol, said routing protocol comprising a finite state machine substantially equivalent to the DUAL finite state machine.

12. A method as in claim 4, wherein unicasting said first packet to each said one destination in said set comprises transmitting said first packet to each said one destination in said set.

13. A method as in claim 4, wherein unicasting said first packet to each said one destination in said set comprises transmitting said first packet to each said one destination in said set simultaneously over a common communication link.

14. A device for routing packets in a network, comprising

means for reliably transmitting multicast packets and unicast packets in a network, said means for reliably transmitting comprising

(a) means for multicasting a first packet having a sequence number to a plurality of destinations, (b) means for recording a set of ones of said plurality of destinations for which an acknowledgment is not received, (c) means, when said set is nonempty, for multicasting a second packet having an indicator representative of said set, (d) means for multicasting a third packet having an indicator representative of conditional receipt, whereby destinations in said set ignore said third packet, and (e) means for unicasting said first packet and said third packet to each destination in said set;

and

means for reliably receiving multicast packets and unicast packets in a network, said means for reliably receiving comprising

(a) a recipient identifier, (b) means, upon receiving a packet having a sequence number from a source, for transmitting an acknowledgment to said source, said acknowledgment indicating said recipient identifier, (c) means, upon receiving a packet having an indicator representative of a set of destinations for which an acknowledgment was not received, for entering a conditional-receive mode if said indicator is not representative of said recipient identifier, and (d) means, for receiving a packet having an indicator representative of conditional receipt only when in said conditional-receive mode.

15. A device as in claim 14, wherein said destinations are a set of neighbors to a router in said network.

16. A device as in claim 14, wherein said first packet comprises an update packet or a query packet in a routing protocol, said routing protocol comprising a finite state machine substantially equivalent to the DUAL finite state machine.

17. A device as in claim 14, wherein said indicator comprises a list of said one destinations that are members of said set.

18. A device as in claim 14, wherein said means for multicasting said first packet comprises means for transmitting said first packet to all of said one destinations.

19. A device as in claim 14, wherein said means for multicasting said first packet comprises means for transmitting said first packet to all of said one destinations simultaneously over a common communication link.

20. A device as in claim 14, wherein said means for reliably receiving comprises means for discarding said sequence number of said fourth packet after transmitting said acknowledgment.

21. A device as in claim 14, wherein said means for reliably receiving comprises means for exiting said conditional-receive mode after receiving said packet having an indicator representative of conditional receipt.

22. A device as in claim 14, wherein said means for reliably transmitting comprises means for waiting for an acknowledgment to said first packet from each said one destination before activating said means for recording.

23. A device as in claim 14, wherein said means for unicasting said first packet to each said one destination in said set comprises means for transmitting said first packet to each said one destination in said set.

24. A device as in claim 14, wherein said means for unicasting said first packet to each said one destination in said set comprises means for transmitting said first packet to each said one destination in said set simultaneously over a common communication link.

25. A device as in claim 14, wherein said third packet comprises an update packet or a query packet in a routing protocol, said routing protocol comprising a finite state machine substantially equivalent to the DUAL finite state machine.

26. A method of routing packets in a network, comprising

receiving a packet, said packet comprising an external header, said external header comprising a value representative of an external routing protocol, a metric assigned by said external routing protocol, a value representative of an autonomous system of routers, and a value representative of an administrative tag;

routing said packet in response to said metric assigned by said external routing protocol; and

routing said packet in response to an administrative policy indicated by said administrative tag.

27. A method as in claim 26, wherein said administrative policy is a security policy, a financial policy, a reliability policy, or a network lag policy.

28. A method as in claim 27, wherein said administrative policy is an application-specific policy.

29. Apparatus for reliably receiving multicast packets and unicast packets in a network, said apparatus comprising

a recipient identifier;

means for transmitting an acknowledgment to a source, said acknowledgment indicating said recipient identifier, upon receiving a packet having a sequence number from said source;

means for entering a conditional-receive mode upon receiving a second packet having an indicator representative of a set of destinations for which an acknowledgment was not received, if said indicator is not representative of said recipient identifier; and

means for receiving a packet having an indicator representative of conditional receipt only when in said conditional-receive mode.

30. Apparatus as in claim 29, further comprising means for discarding said sequence number after transmitting said acknowledgment.

31. Apparatus as in claim 29, further comprising means for exiting said conditional-receive mode after receiving said packet having an indicator representative of conditional receipt.

32. Apparatus for reliably transmitting multicast packets and unicast packets in a network, said apparatus comprising

means for multicasting a first packet having a sequence number to a plurality of destinations;

means for recording a set of ones of said plurality of destinations for which an acknowledgment is not received;

means responsive to said set for multicasting a second packet having an indicator representative of said set;

means for multicasting a third packet having an indicator directing destinations in said set to ignore said third multicast packet; and

means for unicasting said first packet and said third packet to each destination in said set.

33. Apparatus as in claim 32, further comprising means for waiting for an acknowledgment to said first packet from each destination in said set, and for delaying said means for recording while waiting.

34. Apparatus as in claim 32, wherein said means for multicasting said first packet is coupled to all of said one destinations simultaneously with a common communication link.

35. Apparatus as in claim 32, wherein said first packet comprises an update packet or a query packet in a routing protocol, said routing protocol comprising a finite state machine substantially equivalent to the DUAL finite state machine.

36. Apparatus as in claim 32, wherein said indicator comprises a list of said one destinations that are members of said set.

37. Apparatus as in claim 32, wherein said third packet comprises an update packet or a query packet in a routing protocol, said routing protocol comprising a finite state machine substantially equivalent to the DUAL finite state machine.

38. Apparatus as in claim 32, wherein said means for unicasting said first packet is coupled to each said one destination in said set simultaneously with a common communication link.

39. Apparatus for routing packets in a network, said apparatus comprising

means for receiving a packet, said packet comprising an external header, said external header comprising a value representative of an external routing protocol, a metric assigned by said external routing protocol, a value representative of an autonomous system of routers, and a value representative of an administrative tag;

means for routing said packet in response to said metric assigned by said external routing protocol; and

means for routing said packet in response to an administrative policy indicated by said administrative tag.

40. Apparatus as in claim 39, wherein said administrative policy is a security policy, a financial policy, a reliability policy, or a network lag policy.

41. Apparatus as in claim 39, wherein said administrative policy is an application-specific policy.