Performing multicast communication in computer networks by using overlay routing

• US 6,611,872 B1
• Filed: 06/01/1999
• Issued: 08/26/2003
• 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): CALDWELL, ANDREW T
• Application Number:
  US09/323,869
• Time in Patent Office: 1,547 Days
• Field of Search: 709/238-244, 370/390
• 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. An overlay routing processor for transferring information over a computer network, wherein the computer network has a native routing protocol that defines computers as members of native groups for purposes of routing information among members of a given native group, the overlay routing processor comprising

instructions for associating computers on the network with a given overlay group;

instructions for determining whether received information is associated with the given overlay group;

instructions for routing the received information to the computers associated with the given overlay group by using the native routing protocol;

instructions for identifying a specific native group as an efficient distribution channel for the given overlay group,

wherein the instructions for routing include instructions for using the specific native group to perform the routing and wherein the instructions for identifying a specific native group include instructions for using a hash function to perform the identification.

2. An overlay routing processor for transferring information over a computer network, wherein the computer network has a native routing protocol that defines computers as members of native groups for purposes of routing information among members of a given native group, wherein multiple overlay processors are coupled together over the network, the overlay routing processor comprising

instructions for associating computers on the network with a given overlay group,

instructions for associating computers on the network with a given overlay group;

instructions for determining whether received information is associated with the given overlay group;

instructions for routing the received information to the computers associated with the given overlay group by using the native routing protocol;

instructions for identifying a specific native group as an efficient distribution channel for the given overlay group,

wherein the instructions for routing include instructions for using the specific native group to perform the routing;

a data table accessed by the processor for defining peer relationships between overlay processors; and

wherein the instructions for routing include instructions for using the defined peer relationships between overlay processors to perform the routing.

3. An overlay routing processor for transferring information over a computer network, wherein the computer network has a native routing protocol, wherein an end-user computer is coupled to the network, wherein a first media information source is coupled to the network for sending media information to the network, the overlay routing processor comprising

instructions for associating computers on the network with a given overlay group;

instructions for determining whether received information is associated with the given overlay group;

instructions for routing the received information to the computers associated with the given overlay group by using the native routing protocol;

a data structure associating the media information with a first overlay channel identifier;

instructions for receiving a request from the end-user computer to receive the media information;

instructions for retrieving the first overlay channel identifier from the data structure and for associating the first overlay channel identifier with the request; and

instructions for routing all or a portion of the media information received by the overlay routing processor to the end-user computer.

4. The overlay routing processor of claim 3, wherein a second media information source is coupled to the network for sending media information to the network, the overlay routing processor further comprising

instructions for indicating an error condition if a second overlay channel identifier associated with the second media information source is the same as the first overlay channel identifier.

5. An overlay routing processor for transferring information over a computer network, wherein the computer network has a native routing protocol that defines computers as members of native groups for purposes of routing information among members of a given native group, comprising

instructions for associating computers on the network with a given overlay group;

instructions for determining whether received information is associated with the given overlay group;

instructions for routing the received information to the computers associated with the given overlay group by using the native routing protocol;

instructions for identifying a specific native group as an efficient distribution channel for the given overlay group,

wherein the instructions for routing include instructions for using the specific native group to perform the routing;

instructions for associating a native group with an overlay group; and

instructions for changing the association between an overlay group and a native group.

6. The overlay routing processor of claim 5, wherein the association between an overlay group and a native group includes defining a range of native multicast addresses.

7. The overlay routing processor of claim 6, wherein the range of native multicast addresses is defined as an IP₄ Class D address and a prefix length.