Abstract:
Multicast addresses on a computer network are dynamically assigned to a temporary node task. In particular, a server dynamically assigns a multicast address to a data stream in response to a request for the data stream from a client. The server assigns the multicast address in cooperation with other servers from a pool of network-allocated but unassigned multicast addresses. Once the data stream is terminated, the assigned multicast address is deassigned and returned to the pool of unassigned multicast addresses for possible reuse by the nodes.

Description:
RELATED APPLICATION  
       [0001]    This application is a divisional of U.S. Application Ser. No. 09/480,904, filed Jan. 11, 2000, which is also a continuation of U.S. Application Ser. No. 07/981,274, filed Nov. 25, 1992, the entire teachings of which are incorporated herein by reference in their entirety. 
     
    
     
       BACKGROUND OF THE INVENTION  
         [0002]    In computer networks, it is often desirable for one node to transmit data over a network so the data can be received by all other nodes connected to the network. To accomplish the transmitting, a pool of multicast (group) addresses may be allocated to each network by a network standards body, such as the Institute of Electrical and Electronic Engineers (IEEE) or the American National Standards Institute (ANSI). Any node on the network can read data being transmitted on a multicast address. The standards body guarantees that allocated multicast addresses do not overlap between networks.  
           [0003]    Traditionally, multicast addresses were assigned from the pool one at a time, each multicast address serving a specific purpose or function. For example, there are specific multicast addresses assigned for Ethernet end-station “hello” messages, LAT service announcements, and Fiber Distributed Data Interface (FDDI) status reporting frames. Each assigned multicast address serves one explicit function. To prevent a node that is receiving one data stream from being inundated by other data streams, a unique multicast address is required for each unique data stream.  
           [0004]    A problem with the traditional assignment method is that each multicast address on a network is assigned for a single specific purpose or function. As the number of specific functions on the network increases, more multicast addresses from the network&#39;s allocated pool are assigned to meet the need. Once the network&#39;s pool of allocated multicast addresses is depleted, the network must be allocated an additional pool of multicast addresses. This in turn depletes more addresses from the finite set of addresses that are available to be allocated to the various networks.  
           [0005]    While many multicast addresses may be allocated to a network and assigned by the network for specific functions, only a relatively few multicast addresses may be in use on the network at any one time. Indeed, many multicast addresses may be used infrequently because the associated functions are in low demand. Networks are thus expanding their pool of multicast addresses while not using all multicast addresses already allocated to the networks.  
         SUMMARY OF THE INVENTION  
         [0006]    There are effectively an infinite number of arbitrary individual data streams available for transmitting over a network. For example, in a computer network accessing video programs, there may be one data stream for each movie, television program, and video image available to the public. Therefore, it is impractical to assign a unique multicast address for every possible data stream. A mechanism to assign a unique multicast address from a finite set of addresses for the duration of the data stream is an ideal solution. The preferred approach is completely distributed and lacks a central agent for assigning the multicast addresses. Therefore, this approach is reliable as nodes join and leave a local area network (LAN).  
           [0007]    In addition, it is highly desirable not to force interested nodes on the network to receive unwanted data streams. At the same time, for those nodes that do want to receive a data stream, it is desirable that only the data stream in which the node is interested be received.  
           [0008]    The invention provides a general mechanism in which a node on a network can dynamically assign a single multicast address from a network-wide pool of unassigned multicast addresses, and subsequently use that assigned address for the node&#39;s own purposes. When the assigned address is no longer needed, it is returned to the pool. This dynamic assignment permits networks to use fewer multicast addresses then would be required if they were assigned in a more traditional basis where a unique address is assigned for each possible function.  
           [0009]    The invention pertains to a computer network having a transmitter node for transmitting a particular data stream to at least one receiver node. A node&#39;s classification as a transmitter or receiver may vary based on the data stream being transmitted or the network protocol. A data stream is transmitted to a dynamically assigned multicast address by first selecting a candidate multicast address that is not being used by any node on the network. An announcement is transmitted at a dedicated announcement multicast address to notify potential receiver nodes and other transmitter nodes that the candidate multicast address has been assigned. Finally, the transmitter node transmits the data stream at the candidate multicast address.  
           [0010]    Prior to transmission of a service data stream, available services may be identified on the announcement multicast address. Nodes may forward commands to the transmitter node to initialize transmission on candidate addresses. Transmitter nodes may also automatically transmit a particular data stream without receiving a command for that data stream. Thereafter, the services are identified on the announcement address with their candidate addresses so that any node may receive the transmitted data streams.  
           [0011]    The transmitter nodes also monitor the dedicated multicast address to identify conflicts between the selected candidate address and addresses announced by other nodes and to resolve the conflicts by selecting new candidate addresses.  
           [0012]    In particular, a preferred system for transmitting video data streams over a computer network is described. The system comprises video sources, each video source having access to at least one video program. On the computer network are client nodes and server nodes. A user on a client node may have an interest in various video programs. The server nodes are in communication with the video sources and respond to commands received from the client nodes. Specifically, the server nodes select particular video programs from the video sources, either automatically or in response to client node commands for the particular video program. There are a plurality of multicast addresses allocated to the computer network. One such multicast address is used cooperatively by the server nodes to announce information regarding available video programs to all client nodes. The remaining pool of multicast addresses is used by the server nodes to transmit video programs to any and all interested client nodes. The server nodes cooperatively manage the dynamic assignment of multicast addresses so that multicast addresses are exclusively assigned to a single video program while that video program is being transmitted. After the video program transmission terminates, the assigned multicast address is deassigned and returned to the pool of unassigned multicast addresses for possible reassignment. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0013]    The foregoing and other objects, features and advantages of the invention will be apparent from the following more particular description of preferred embodiments of the drawings in which like reference characters refer to the same parts throughout the different views.  
         [0014]    [0014]FIG. 1 is a schematic block diagram of computer network adapted for transmitting video data streams.  
         [0015]    [0015]FIG. 2 is a block diagram of the multicast addresses A 1 -A N  available on network  10  of FIG. 1.  
         [0016]    [0016]FIG. 3 is a schematic block diagram of the announcement address A 1  of FIG.  
         [0017]    [0017]FIG. 4 is a schematic block diagram of a transmission address A n  of FIG. 2.  
         [0018]    [0018]FIGS. 5A and 5B are a flow chart showing the steps performed by a client node  30  of FIG. 1.  
         [0019]    [0019]FIG. 6 is a flow chart showing the steps performed by a server node  20  of FIG. 1. 
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0020]    [0020]FIG. 1 is a schematic block diagram of a typical computer network adapted for accessing video data streams. The network comprises a network structure  10 , server nodes  20   a - x , and client nodes  30   a - m . The network structure  10  may be any applicable network configuration, such as a star-wired or a bus topology. Server nodes  20 a-x perform tasks for the network. The server nodes  20   a - x  are connected to the network structure  10  by respective cabling  12   a - x . Likewise, the client nodes  30   a - m  are connected to the network structure  10  by respective cabling  13   a - m . The client nodes  30   a - m  are operated by users accessing the network. The network may be compatible with any network protocol supporting multicast addresses, including Ethernet, IEEE 802.3, and FDDI (ANSI X3T9.5). Although a preferred embodiment is described in terms of video data streams, the invention applies to computer networks for transmitting any data streams between nodes.  
         [0021]    The network  10  is allocated at least one block of N multicast addresses A 1 -A n  according to the particular network protocol. One of the allocated multicast address A 1  is an announcement address. Each server  20   a - x  periodically transmits announcement messages on the announcement address A 1 . The selection of the announcement interval is a trade-off between announcing frequently so that clients  30   a - m  can rapidly access data and avoiding an unnecessary load on the network  10  and the servers  20   a - x . In a preferred embodiment of the invention, the announcement interval is on the order of a few seconds. The remaining allocated multicast addresses A 2 -A n  are considered to be in either a pool of unassigned multicast addresses  12  or a table of assigned multicast addresses  14 . These remaining multicast addresses A 2 -A n  are cooperatively assigned by the servers  20   a - x  and readable by all servers  20   a - x  and all clients  30   a - m  on the network  10 .  
         [0022]    In a preferred embodiment, the cooperation between the servers is entirely distributed. Instead of using a central database, each server node  20   a - x  on the network  10  maintains a view of the multicast addresses A 1 -A n .The server nodes  20   a - x  maintain respective views  24   a - x , the views are maintained in the respective node&#39;s local address space. Assignment information is shared between the nodes on the network  10 . Changes in the assignment status of the multicast addresses are tracked by the server nodes  20   a - x . From the announcement address A 1 , the client nodes  30   a - m  may track the data streams being transmitted on the assigned multicast addresses. On a steady-state network  10 , all server views  24   a - x  are synchronized to be identical.  
         [0023]    In a preferred embodiment of the invention, the server nodes  20   a - x  service video data for the client nodes  30   a - m . Connected to the server nodes  20   a - x  may be such devices as tuners  21  and video players  23 . Tuners  21  may collect TV video signals from local broadcasts or satellites. Video players  23  may be video cassette players or CD ROMs connected to a video library  25 . For simplicity and clarity of description, each server node  20  is shown connected to one video device. A server node  20  may have access to more than one video device, and each video device may in turn be of a separate type.  
         [0024]    The server nodes  20   a - x  typically compress video signals into video data streams for transmission over the network structure  10 . Client nodes  30   a - m  receive the video data streams. The client nodes  30   a - m  may then manipulate the video data streams, decompress the video data streams into video signals for display or recording, or otherwise process the video data streams.  
         [0025]    Server nodes  20   a - x  transmit the video data streams over the network  10  by using multicast addresses. FIG. 2 shows the address assignments for the N multicast addresses allocated to the network. Address A 1  is the announcement address. A single announcement address A 1  on the network is used by all servers  20   a - x  to supply video program information to all clients  30   a - m . Addresses A 2 -A n  are assignable transmission addresses. The servers  20   a - x  use the assignable transmission addresses A 2 -A n  to transmit the video data streams to the clients  30   a - m.    
         [0026]    [0026]FIG. 3 shows the relevant fields of the data packets  16  available at the announcement address A 1 . Each announcement packet  16  contains fields for the server name A 1 a, the network address of the server A 1 b, the description of data streams being transmitted by the server A 1 c, the multicast address where the video data is being transmitted A 1 d, and a list of data streams available from the server A 1 e. The description of a data stream is unique for that data stream, regardless of the network on which the data stream is available. The use of unique descriptions promotes conflict resolution as networks are linked together. In addition to the identified fields, the announcement packet  16  may have additional fields. FIG. 3 does not limit the, number nor the size of fields available in the announcement packet  16 . For example, the announcement packet  16  may supply a database address where the client  30  can randomly access pertinent information, such as an index of available video programs cross-referenced to servers capable of providing the video program and servers currently transmitting the video program over the network.  
         [0027]    [0027]FIG. 4 shows the relevant fields of a data packet  18  available at a transmission address A n . The transmission packet  18  contains a header field A n h for identifying such information as the sending server and the data stream and a field A n b containing a frame of the data stream. FIG. 4 does not limit the number of fields available in the transmission packet  18  nor the size of the fields.  
         [0028]    [0028]FIGS. 5A and 5B provide a flow chart of the processing performed by the client nodes  30   a - m . Client processing begins at step  300  of FIG. 5A. As shown at step  305 , the client  30  monitors the announcement address A 1 . By monitoring the announcement packets  16  at announcement address A 1 , the client  30  can generate a list of all video programs being transmitted by each server  20  and all available video programs that the servers  20   a - x  are capable of transmitting. At step  310 , the client  30  selects a video data stream in which a user is interested. To continue, the client  30  must determine whether the selected video data stream is already being transmitted by a server  20 , as shown at step  315 .  
         [0029]    If the selected video data stream is not currently being transmitted, the client  30  must cause a server  20  to transmit the video data stream. At step  320 , the client  30  sends a request over the network to an appropriate server  20  having access to the desired video data stream. The request instructs the server  20  to transmit over the network the video data stream from its video source. The client  30  then waits for an announcement from the server  20 , shown at  325 . The announcement for the video data stream will contain the transmission address A n  for the video data stream in the transmission address field A 1 d.  
         [0030]    After reviewing the request sent by a client at  320 , the server  20  determines a transmission address A n  from available addresses as discussed below and announces that transmission address A n . in the transmission address field A 1 d at announcement address A 1  The server  20  then transmits a video data stream comprising frames of data at the transmission address A n . To read the data stream, a client  30  reads continuous data packets  18  at the transmission address A n .  
         [0031]    Turning to step  330  of FIG. 5B, the client  30  reads data from a transmission packet  18 . In the header A n h of each transmission packet  18  is information indicating the identity of the server  20  sending the video data and a description of the video data. As shown at step  335 , if the client  30  does not read an expected header from the transmission address, then the client  30  may have lost the video data stream. In the case of a lost data stream, the client  30  waits for a new announcement at step  325 . As discussed below, the transmission address A n  for the video data stream may be changed by the server  20  because of conflicts between servers over the transmission address A n .  
         [0032]    In an alternative embodiment of the invention, the client  30  monitors the announcement address A 1  for any new announcements related to video programs in which the users are interested. Upon detecting a change in the transmission address A n , the client  30  switches to a new transmission address A n  to read the video data stream.  
         [0033]    If the client  30  reads a proper transmission packet  18 , then the client  30  processes the data frame A n b at step  340 . Processing the data frame A n b may involve manipulating the data or decompressing the data to create a video image.  
         [0034]    The steps of reading and processing transmission packets  18  continues until the client  30  is finished with the video data stream. Periodically, the client  30  sends a keep-alive message to the server  20 . For example, the client  30  sends a keep-alive message at rate T/ 2 , where T is the server timeout period (described below). The keep-alive message informs the server  20  that the client  30  is still reading the video data stream. As long as a client  30  is reading the data, the server  20  will continue to transmit the video data stream on the transmission address A n . The step of sending the periodic keep-alive message is shown at step  350 . A client  30  that does not send periodic keep-alive messages may read the video data steam, but that client  30  risks having the data stream terminate without notice. When the client  30  finishes reading the video data stream, processing ends and the routine returns at step  355 .  
         [0035]    In an alternative embodiment of the invention, the client  30  sends a message to a server  20  whenever the client  30  starts to read a data stream from a transmission address A n  assigned to that server  20 . The client  30  then sends a message to the transmitting server  20  when it stops reading from the transmission address A n . The server  20  continues to transmit the data stream at the transmission address A n  until the count of clients  30   a - m  reading the transmission address A n  becomes zero. Unfortunately, the server  20  is not guaranteed to receive either the start or stop message. If a start message is not received by the server  20 , then the server  20  may terminate a transmission while a client  30  is reading the data stream. If a stop message is not received by the server  20 , then the server  20  may continue to transmit a data stream indefinitely. Consequently, this alternative embodiment is less desirable than the keep-alive embodiment.  
         [0036]    In an alternative embodiment of the invention, a client  30  may generate the list of video programs by scanning the multicast addresses A 2 -A n  and sampling transmission packets  18 . Active transmissions can be identified by the existence of a transmission packet  18  at a multicast address A n . By reading the header A n h of the transmission packet  18 , the client  30  can determine the contents of the transmission on that transmission address. From the header A n h of the transmission packet  18 , the client  30  can generate a list of video programs on assigned multicast addresses without accessing an announcement address A 1 .  
         [0037]    Similarly, the announcement address may only provide clients  30   a - m  with assigned multicast addresses A 1 d without a description of the data stream A 1 c. In that case, the client  30  can generate a list of assigned multicast addresses. By using the list of assigned multicast addresses, instead of the larger set of allocated multicast addresses A 2 -A n , the client  30  can reduce the scanning time.  
         [0038]    [0038]FIG. 6 is a flow chart of the server  20  processing steps. At network initialization, all non-dedicated multicast addresses A 2 -A n  are unassigned and are in the pool of unassigned multicast addresses  12 . The processing is initiated by a client request for a video data stream that is not being transmitted over the network  10 . Alternatively, the server  20  may automatically transmit particular video data streams independent of client requests. For example, a server  20  may transmit the particular video data stream during the duration of that data stream&#39;s availability (e.g. news broadcasts, network programming, etc.). After the video data stream is selected, the server  20  must select a multicast address for transmitting the particular video data stream.  
         [0039]    Upon entry at step  200 , the server  20  selects a candidate transmission address A n  from the pool of unassigned multicast addresses  12 , as shown in step  210 . In a preferred embodiment of the invention, the server  20  selects addresses from the pool of unassigned multicast addresses  12  in a random fashion. In an alternative embodiment of the invention, the server  20  sequentially selects the next available address from the pool of unassigned multicast addresses  12 . Once a candidate transmission address A n  is selected, the server  20  must notify the client  30  and other servers  20   a - x  of the selection.  
         [0040]    The server  20  notifies the clients  30   a - m  and the other servers  20   a - x  by sending an announcement message at step  220 . The announcement is sent over the announcement address A 1  as shown in FIG. 3. To facilitate rapid recognition by the clients  30   a - m  and other servers  20   a - x , the announcement message is queued to the announcement address A 1  immediately. In a preferred embodiment of the invention, two announcement messages are sent in succession at step  220 . Preferably, the announcement message is sent twice during the currently active announcement interval. After the announcement messages have been queued to the announcement address A 1 , the server  20  is ready to transmit the video data stream.  
         [0041]    The server  20  transmits the video data stream at step  230 . The video data stream is transmitted at the transmission address A n . In a preferred embodiment, there is only one video data stream being transmitted at a transmission address A n  during steady state. However, it is possible that multiple servers  20   a - x  may simultaneously select an identical candidate transmission address A n  from the pool of unassigned multicast addresses  12 . In that case, there would be a conflict over a selected transmission address A n . Until the conflict is resolved, there may be multiple servers  20 a-x transmitting on a single transmission address A n . Because clients  30   a - m  read only data frames carrying requested information, the system can tolerate short-term conflicts over a multicast address. However, to promote network efficiency, conflicts over a multicast address are resolved so that only one data stream is transmitted per multicast address.  
         [0042]    The servers  20   a - x  are responsible for resolving conflicts over transmission addresses. Each server  20  monitors the announcement address A 1  as shown at step  240 . By monitoring the announcement address A 1 , each server  20  maintains a local table of assigned multicast addresses  14  in a local view  24 . Alternatively, the table may be cooperatively maintained in a shared database. In particular, the server  20  recognizes conflicts between itself and other servers  20   a - x  over a transmission address A n .  
         [0043]    Once a conflict is detected, as shown at step  250 , the servers  20   a - x  resolve the conflict. In a preferred embodiment of the invention, a priority system is used to resolve the conflict as shown at step  260 . In a preferred embodiment of the invention, a server&#39;s priority is based on the server&#39;s network address. In particular, a server  20  having a numerically higher-valued network address has priority over a server  20  having a numerically lower-valued network address. The server  20  with the highest numeric network address will keep the selected transmission address A n .  
         [0044]    Alternatively, numerically lower-valued network addresses could provide priority over numerically higher-valued network addresses. All other servers  20  that conflict with the priority server  20 , will select another candidate transmission address A n , from the pool of unassigned multicast addresses  12  and continue at step  210 .  
         [0045]    If no conflict is detected or if the server  20  has the highest priority, the selected candidate transmission address A n  becomes assigned to the server  20 . The processing then returns to the calling routine at  270 .  
         [0046]    Typically, the assignment and transmitting continue until there are no clients  30   a - m  signaling an interested in the data stream to the server  20 . In a preferred embodiment, the server  20  terminates the transmission and deassigns the multicast address when no keep-alive messages are received within a time-out period, T. A reasonable time-out period is ten minutes (T=10 min). In an alternative embodiment of the invention, the server  20  terminates the transmission and deassigns the multicast address when the count of clients  30   a - m  reading the data stream becomes zero. If the data stream is being automatically transmitted, then the server  20  may automatically terminate the transmission, such as at the end of a transmission duration.  
       EQUIVALENTS  
       [0047]    Those skilled in the art will know, or be able to ascertain using no more than routine experimentation many equivalents to specific embodiments to the invention described herein.  
         [0048]    These and all other equivalents are intended to be encompassed by the following claims.