Performing multicast communication in computer networks by using overlay routing

• US 7,080,157 B2
• Filed: 11/18/2002
• Issued: 07/18/2006
• Est. Priority Date: 01/11/1999
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: FastForward Networks, Inc. (Apollo Global Management, Inc.)
• Inventors: McCanne, Steven
• Primary Examiner(s): Donaghue, Larry D.
• Application Number:
  US10/299,676
• Publication Number:
  US 20030088696A1
• Time in Patent Office: 1,338 Days
• Field of Search: 709227-229, 709238-244, 709/248, 370/392
• US Class Current: 709/238
• CPC Class Codes: H04L 12/1836 with heterogeneous network architecture
• CPC Class Codes: H04L 12/185 with management of multicast group membership
• CPC Class Codes: H04L 12/1886 with traffic restrictions for efficiency improvement, e.g. involving subnets or subdomains
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 65/1101 Session protocols
• CPC Class Codes: H04L 65/403 Arrangements for multi-party communication, e.g. for conferences data switching systems for conference H04L12/18; arrangements for connecting several subscribers to a common circuit, i.e. affording conference facilities H04M3/56; television conferencing systems H04N7/15
• CPC Class Codes: H04L 65/611 for multicast or broadcast systems for broadcast or conference H04L12/18; arrangements for broadcast or distribution combined with broadcast H04H20/00; arrangements for broadcast applications with a direct linkage to broadcast information or to broadcast space-time H04H60/00; selective distribution of broadcast services, e.g. multimedia broadcast multicast service [MBMS], H04W4/06

Abstract

An overlay protocol and system for allowing multicast routing in the Internet to be performed at the application level. The overlay protocol uses “native” Internet multicast and multicast routing protocols to route information, according to overlay routing tables. Overlay groups are mapped to native multicast groups to exploit native multicasting in regional or local forwarding domains. Use of the overlay protocol allows overlay distribution to be handled in a more intelligent and bandwidth-managed fashion. Overlay routers are placed at each of several local area networks, Internet service provider'"'"'s point of presence, enterprise, or other cohesively-managed locations. The overlay computers are configured according to bandwidth and security policies, and perform application-level multicast distribution across the otherwise disjoint multicast networks by using the overlay routing. The result is an overlay multicast network that is effectively managed according to local network management policies. Application-level control can be applied to the transferred data at the overlay routers.

Claims

1. A method for performing overlay routing, comprising:

upon receiving a packet at a first router, determining (a) whether the packet contains an overlay header, and (b) whether the packet is to be sent, by the first router, to a destination computer or to a second router;

if the packet does not contain an overlay header and the packet is to be sent, by the first router, to the second router, then the first router performing the steps of;

(a) generating an overlay header for the packet, wherein the overlay header identifies an overlay address, and

(b) routing, to the second router, the packet based on the overlay address, contained in the overlay header, using a first protocol associated with an application layer;

if the packet contains an overlay header and the packet is to be sent to the destination computer, then the first router performing the steps of;

(a) creating a modified packet by stripping the overlay header off the packet and using the overlay network address identified by the overlay header to determine a network layer address to route the packet to the destination computer, and

(b) routing, to the destination computer, the modified packet based on the network layer address using a second protocol associated with a network layer.

2. The method of claim 1, wherein the overlay header is situated between the UDP header of the packet and the application payload of the packet.

3. The method of claim 1, wherein the packet is one of a plurality of packets constituting a data stream, and wherein the first protocol may be used to modify content of the datastream, at the first router, without the first router dropping any packets of the plurality of packets.

4. The method of claim 1, wherein the packet is one of a plurality of packets constituting a datastream, and the method further comprises:

receiving notification, from the destination computer, that the destination computer is interested in receiving the datastream.

5. The method of claim 4, wherein the notification comprises delivery data that describes how the first router is to transmit the datastream to the destination computer.

6. The method of claim 5, wherein the delivery data includes either (a) one or more transport connection parameters or (b) application-level information for use by the first router in optimizing the delivery of the datastream to the destination computer.

7. The method of claim 1, further comprising:

maintaining data identifying a set of destination computers, wherein each of the set of destination computers is interested in receiving packets that constitute a datastream, and wherein the packet is one of said packets constituting the datastream.

8. The method of claim 1, wherein the step of routing the packet based on the overlay address further comprises:

multicasting the packet to two or more destination computers.

9. The method of claim 1, wherein the step of routing the modified packet based on the network layer address further comprises:

multicasting the packet to two or more destination computers.

10. The method of claim 1, further comprising:

upon consulting an administrative policy, determining whether a particular source may send packets using the first protocol.

22. The method of claim 1, wherein the overlay header is situated between the UDP header of the packet and the application payload of the packet.

11. A machine-readable medium carrying one or more sequences of instructions for performing overlay routing, wherein execution of the one or more sequences of instructions by one or more processors cause:

upon receiving a packet at a first router, determining (a) whether the packet contains an overlay header, and (b) whether the packet is to be sent, by the first router, to a destination computer or to a second router;

if the packet does not contain an overlay header and the packet is to be sent, by the first router, to the second router, then the first router performing the steps of;

(a) generating an overlay header for the packet, wherein the overlay header identifies an overlay address, and

(b) routing, to the second router, the packet based on the overlay address, contained in the overlay header, using a first protocol associated with an application layer;

if the packet contains an overlay header and the packet is to be sent to the destination computer, then the first router performing the steps of;

(a) creating a modified packet by stripping the overlay header off the packet and using the overlay network address identified by the overlay header to determine a network layer address to route the packet to the destination computer, and

(b) routing, to the destination computer, the modified packet based on the network layer address using a second protocol associated with a network layer.

12. The machine-readable medium of claim 11, wherein the overlay header is situated between the UDP header of the packet and the application payload of the packet.

13. The machine-readable medium of claim 11, wherein the packet is one of a plurality of packets constituting a datastream, and wherein the first protocol may be used to modify content of the datastream, at the first router, without the first router intentionally dropping any packets of the plurality of packets.

14. The machine-readable medium of claim 11, wherein the packet is one of a plurality of packets constituting a data stream, and wherein execution of the one or more sequences of instructions by the one or more processors further cause:

receiving notification, from the destination computer, that the destination computer is interested in receiving the datastream.

15. The machine-readable medium of claim 14, wherein the notification comprises delivery data that describes how the first router is to transmit the datastream to the destination computer.

16. The machine-readable medium of claim 15, wherein the delivery data includes either (a) one or more transport connection parameters or (b) application-level information for use by the first router in optimizing the delivery of the datastream to the destination computer.

17. The machine-readable medium of claim 11, wherein execution of the one or more sequences of instructions by the one or more processors further cause:

maintaining data identifying a set of destination computers, wherein each of the set of destination computers is interested in receiving packets that constitute a datastream, and wherein the packet is one of said packets constituting the datastream.

18. The machine-readable medium of claim 11, wherein the step of routing the packet based on the overlay address further comprises:

multicasting the packet to two or more destination computers.

19. The machine-readable medium of claim 11, wherein the step of routing the modified packet based on the network layer address further comprises:

multicasting the packet to two or more destination computers.

20. The machine-readable medium of claim 11, wherein execution of the one or more sequences of instructions by the one or more processors further cause:

upon consulting an administrative policy, determining whether a particular source may send packets using the first protocol.

21. An apparatus for performing overlay routing, comprising:

one or more processors; and

a machine-readable medium carrying one or more sequences of instructions for performing overlay routing, wherein execution of the one or more sequences of instructions by the one or more processors cause;

upon receiving a packet at a first router, determining (a) whether the packet contains an overlay header, and (b) whether the packet is to be sent, by the first router, to a destination computer or to a second router;

if the packet does not contain an overlay header and the packet is to be sent, by the first router, to the second router, then the first router performing the steps of;

(a) generating an overlay header for the packet, wherein the overlay header identifies an overlay address, and

(b) routing, to the second router, the packet based on the overlay address, contained in the overlay header, using a first protocol associated with an application layer;

if the packet contains an overlay header and the packet is to be sent to the destination computer, then the first router performing the steps of;

(a) creating a modified packet by stripping the overlay header off the packet and using the overlay network address identified by the overlay header to determine a network layer address to route the packet to the destination computer, and

(b) routing, to the destination computer, the modified packet based on the network layer address using a second protocol associated with a network layer.

23. The apparatus of claim 21, wherein the packet is one of a plurality of packets constituting a data stream, and wherein the first protocol may be used to modify content of the datastream, at the first router, without the first router intentionally dropping any packets of the plurality of packets.

24. The apparatus of claim 21, wherein the packet is one of a plurality of packets constituting a data stream, and wherein execution of the one or more sequences of instructions by the one or more processors further cause:

receiving notification, from the destination computer, that the destination computer is interested in receiving the datastream.

25. The apparatus of claim 24, wherein the notification comprises delivery data that describes how the first router is to transmit the datastream to the destination computer.

26. The apparatus of claim 25, wherein the delivery data includes either (a) one or more transport connection parameters or (b) application-level information for use by the first router in optimizing the delivery of the datastream to the destination computer.

27. The apparatus of claim 21, wherein execution of the one or more sequences of instructions by the one or more processors further cause:

maintaining data identifying a set of destination computers, wherein each of the set of destination computers is interested in receiving packets that constitute a datastream, and wherein the packet is one of said packets constituting the datastream.

28. The apparatus of claim 21, wherein the step of routing the packet based on the overlay address further comprises:

multicasting the packet to two or more destination computers.

29. The apparatus of claim 21, wherein the step of routing the modified packet based on the network layer address further comprises:

multicasting the packet to two or more destination computers.

30. The apparatus of claim 21, wherein execution of the one or more sequences of instructions by the one or more processors further cause:

upon consulting an administrative policy, determining whether a particular source may send packets using the first protocol.